SLUB

linux: v4.9-rc8

SLUB

figure

SLUB 할당자는 할당 메모리 사이즈를 기준으로(사이즈별로) 캐시를 관리한다. 캐시는 슬랩으로 구성된다. 슬랩은 동일한 사이즈로 구획된 오브젝트로 다시 세분화된다. 그리고 슬랩 할당자는 per-cpu 방식으로 동작한다.

슬랩 내의 각 free 오브젝트들은 (옵션에 따라 위치가 다른-kmem_cache.offset)포인터로 서로 연결되어 있다. 슬랩 할당자의 per-cpu는 이 링크를 통해 freelist를 관리한다. 할당된 object는 연결정보를 잃는다(옵션에 따라 잃지 않을 수도 있다).

주목할만 한 사항은 struct page 자료구조를 사용해 메타 데이터 공간을 절약한다는 점, cmpxchg로 인터럽트 조작을 최소화한다는 점, per-cpu방식으로 locking 오버헤드를 줄였다는 점이다.

슬랩내 오브젝트 갯수가 많을수록(페이지 크기가 클수록), 슬랩의 갯수와 node partial에서 cpu partial로 전환하는 횟수가 적어진다. 즉, locking 오버헤드가 작아진다. 반면, 오브젝트 크기가 클수록 슬랩은 여러개의 페이지로 구성될 것이고, 이러한 슬랩을 partial에 많이 유지하는 것은 외부 파편화를 유발할 수 있을 것이다.

관련 자료구조는 다음과 같다:

struct kmem_cache {
	align : 오브젝트 정렬단위
	cpu_partial : per-cpu(partial list)가 가질수 있는 오브젝트의 최대 갯수
	min_partial : node partial에 유지할 slab의 최소 갯수(슬랩내 오브젝트 갯수가 적은 경우 새로운 슬랩 즉, 페이지 할당자 버디를 호출하는 경우가 잦아질 것이므로 이 변수를 통해 완충지를 만듬)
	offset : 오브젝트 메타정보(free 오브젝트 링크) 위치
	oo : 페이지 order 값과 페이지 내에 들어갈 수 있는 object 갯수
	refcount : 참조 카운터, 캐시 생성시 1로 설정. 부트업시 생성된 kmem_cache와 kmem_cache_node 캐시는 -1로 unmergeble 하고 지울수도 없다
	size : 메타 데이터를 포함한 오브젝트 사이즈
}

struct kmem_cache_node {
	nr_partial : 노드내 슬랩 갯수
	partial : 슬랩 리스트
}

struct page {
	freelist : 첫 free object 위치(실제 가상주소)
	slab_cache : kmem_cache 구조체 포인터
	
	union {
		counters :
		struct {
			inuse : 사용중인(할당된) 오브젝트 갯수(실제 사용자에게 할당된 것 뿐만 아니라 per-cpu로 위임된 오브젝트 역시 포함. 할당은 per-cpu를 통할 수 밖에 없으므로)
			objects : 페이지(슬랩: compound이기 때문)내 할당 가능한 오브젝트 갯수
			frozen : full 또는 empty가 아닌, per-cpu 에서 사용되는 page(슬랩)인 경우
		}
	}
	
	union {
		lru : node partial list
		struct {
			next : cpu partial list
			pages : per-cpu에 남아있는 슬랩 갯수
		}
	}
}

할당

freelist 앞쪽부터 할당 시작. cpu freelist를 사용할 수 있다면 cmpxchg로 재빠르게 할당이 수행된다. freelist가 비어있는 경우 cpu partial에서 하나의 슬랩을 가져오기 위해 인터럽트를 조작해야 한다. cpu partial 역시 비어있는 경우 node partial에서 슬랩을 가져오기 위해 lock을 조작해야 한다. node partial마저 비어있는 경우 페이지 할당자를 호출해야 한다.

per-cpu는 자기 노드의 슬랩을 가져오도록 되어 있지만, 자기 노드에 슬랩이 없는 경우 다른 노드의 슬랩을 가져온다. 하지만 매번 슬랩의 소속이 자기노드인지 확인한 후 자기 노드의 슬랩이 아닌 경우 자기 노드의 슬랩으로 대체하기 위해 노력한다.

해제와 달리 node partial에서 cpu partial로 슬랩을 가져올 때는 node partial의 수용력을 해치지 않기 위해 cpu_partial의 반만 가져온다(그렇지 않다면 슬랩으로 변환된 페이지(페이지 할당자를 호출하는 경우)가 많아질 것이고, 그 횟수만큼 느려질 것이다).

- kmalloc()
  - kmem_cache_alloc()
    - slab_alloc()
      - slab_alloc_node()
        - __slab_alloc() <- slow path, 인터럽트 조작!
            - new_slab_objects()
              - get_partial() <- 더 느림
                - get_partial_node() <- lock 발생!
              - new_slab() <- 더 더 느림, 페이지 할당자 호출

좀 더 코멘트

- kmem_cache_alloc_node()
  - slab_alloc_node()
    - per-cpu freelist에 free object가 없는 경우 새로운 freelist를 가져옴
      - __slab_alloc()
        - 인터럽트 금지
        - per-cpu page가(사용중인 슬랩이) 비어있는 경우 partial에서 슬랩을 가져옴
        - new_slab_objects()
          - get_partial()
            - get_partial_node()
              - 노드 락
              - acquire_slab()
                - 노드의 partial 리스트에서 슬랩 하나를 가져옴
                - frozen = 1로 per-cpu 사용을 나타냄
                - page 구조체의 freelist는 null로 설정
                - 노드의 partial 리스트에서 해당 슬랩을 제거
              - per-cpu의 page가 비어있다면 page에 새로운 슬랩을 할당하고 아니면, per-cpu partial에 새로운 슬랩을 추가
              - per-cpu partial이 비어있거나, 새로 얻은 슬랩의 free 오브젝트 갯수가 per-cpu freelist가 가질 수 있는 최대 오브젝트 갯수의 반이 안되면 반이 될때까지 추가적인 partial 리스트를 확보
            - get_any_partial()
              - per-cpu에 유지해야 하는 최소한의 슬랩의 갯수(min_partial)보다 더 많은 슬랩을 가진 노드에서 슬랩을 가져온다(가용 노드가 있는 경우 동일한 get_partial_node() 루틴을 탄다). 하지만 할당할 때마다 현재 per-cpu에 사용중인 슬랩이 외부 노드로부터 온 것인지 확인하고 외부 노드라면 되돌려준다. 즉, 최대한 자기 노드에서 슬랩을 가져오려하며 그렇지 않은 경우 가까운 노드 순으로 취급한다
          - per-cpu partial(슬랩 리스트)마저 비어있는 경우 페이지 할당자에서 새로운 슬랩을 할당
      - per-cpu의 tid가 변화하는 시점은 per-cpu의 freelist가 새로이 load된(변화하는) 경우

해제

freelist 앞쪽에 해제. kfree() 흐름을 타고가면 늘 하나의 오브젝트만 해제하지만, tail을 지정하여 bulk로 해제할 수 있다.

해제하는 오브젝트의 슬랩이 per-cpu에서 관리되고 있지 않다면(!frozen), 해당 슬랩은 cpu partial로 복귀하거나 node partial로 반환된다. 혹은, 해체(페이지 할당자로 흡수)된다. cpu partial로 복귀할 때는 partial list의 앞쪽에 추가된다. cpu partial로 추가되는 경우는 full에서 처음으로 free가 일어난 경우인데, 이말인즉 SLUB은 빈 오브젝트가 적은 슬랩일수록 가능한 빨리 소진해버리려고 한다는 것이다(아마도 locality와 유휴 공유(노드) 슬랩을 확보하기 위해. 빈 오브젝트가 많을수록 버디로 돌려보낼 수 있는 확률도 높고).

해제는 cpu partial에서 node partial, 그리고 버디로 라는 순차적인 흐름을 타지 않는다. 할당으로 freelist를 모두 소진하므로써 per-cpu와 연결을 잃은 (고아 또는 자유?)슬랩이 처음으로 free 오브젝트를 얻을 때 다시 cpu partial로 링크(frozen)되는데, 이때 모든 cpu partials들은 node partial로 반환되거나 버디로 해체되거나 아니면 cpu partial에 유지된다. cpu partial에서 node partial로 갈 수 있는 경로는 이 한가지다.

2778 static void __slab_free()
...
2796         do {    
2797                 if (unlikely(n)) {
2798                         spin_unlock_irqrestore(&n->list_lock, flags);
2799                         n = NULL;
2800                 }
2801                 prior = page->freelist;
2802                 counters = page->counters;
2803                 set_freepointer(s, tail, prior);
2804                 new.counters = counters;
2805                 was_frozen = new.frozen;
2806                 new.inuse -= cnt;
2807                 if ((!new.inuse || !prior) && !was_frozen) {
2809                         if (kmem_cache_has_cpu_partial(s) && !prior) {
2817                                 new.frozen = 1;
2819                         } else {
2821                                 n = get_node(s, page_to_nid(page));
2830                                 spin_lock_irqsave(&n->list_lock, flags);
2832                         }
2833                 }       
2835         } while (!cmpxchg_double_slab());
...
2840         if (likely(!n)) {
2846                 if (new.frozen && !was_frozen) {
2847                         put_cpu_partial(s, page, 1);
2848                         stat(s, CPU_PARTIAL_FREE);
2849                 }
...
2856                 return;
2857         }

초기화

초기화해야할 자료구조는 캐시용 kmem_cache와 노드용 keme_cache_node 그리고 per-cpu용 kmem_cache_cpu 이다. per-cpu용 자료구조는 이미 사용준비가 끝난 per-cpu 할당자를 사용하면 되지만, 다른 두개의 자료구조를 위한 메모리는 페이지 단위의 페이지 할당자(버디)를 사용할 수 밖에 없다. 그로인한 메모리 낭비를 줄이기 위해 커널은 초기화 동안 사용할 정적 영역 메모리를 확보한 뒤 나중에 복사 & 반환한다(bootstrap()).

slab_state == FULL 상태는 sysfs에 등록될 때 활성된다(slab_sysfs_init()).

호출 함수 관계도:

start_kernel()
  - kmem_cache_init()
    - create_boot_cache()
      - calculate_alignment()
      - slab_init_memcg_params()
      - __kmem_cache_create()
        - kmem_cache_open()
          - init_kmem_cache_nodes()
            - early_kmem_cache_node_alloc()
            - kmem_cache_alloc_node()
          - alloc_kmem_cache_cpus()

오브젝트의 갯수와 슬랩의 크기

페이지 할당자, 버디의 외부 파편화를 완화하기 위해 order 0을 선호한다. 하지만 오브젝트 사이즈가 큰 경우 페이지에 낭비공간이 발생하게 된다. 따라서 낭비가 일정수준(최대 1/4)을 넘어서게 되면 higer order 페이지를 할당한다.

order 0의 경우 버디의 파편화 문제를 신경쓰지 않아도 되기 때문에 여러개의 오브젝트를 유지하도록 되어 있지만, 상위 order의 경우엔 최소한의 오브젝트만 유지해서 partial list에서 메모리가 낭비되거나 파편화를 조장하는 일이 없도록 한다.

3196 static inline int slab_order()
3198 {
...
3203         if (order_objects(min_order, size, reserved) > MAX_OBJS_PER_PAGE)
3204                 return get_order(size * MAX_OBJS_PER_PAGE) - 1;
3205 
3206         for (order = max(min_order, get_order(min_objects * size + reserved));
3207                         order <= max_order; order++) {
3208 
3209                 unsigned long slab_size = PAGE_SIZE << order;
3210 
3211                 rem = (slab_size - reserved) % size;
3212 
3213                 if (rem <= slab_size / fract_leftover)
3214                         break;
3215         }
3216                                                                                                  
3217         return order;                                                                            
3218 } 
...
3220 static inline int calculate_order()
3221 {
...
3241         while (min_objects > 1) {                                                                
3242                 fraction = 16;
3243                 while (fraction >= 4) {
3244                         order = slab_order(size, min_objects,
3245                                         slub_max_order, fraction, reserved);                     
3246                         if (order <= slub_max_order)                                             
3247                                 return order;                                                    
3248                         fraction /= 2;                                                           
3249                 }
3250                 min_objects--;                                                                   
3251         } 
  1. 현재는 페이지 단위로 할당할 수 밖에 없다. ↩︎

  2. kmem_cache_node = &boot_kmem_cache_nodekmem_cache = &boot_kmem_cache ↩︎