[Linux] 동적 메모리 할당자 : slab, slub, slob

출처 : http://studyfoss.egloos.com/5332580

오랜 동안 커널의 동적 메모리 할당자는 slab이었다.
slab은 일반적인 환경에서 무난한 성능을 보여주었기 때문에 널리 사용되었지만
메모리 자원에 상당한 제한을 받는 임베디드 환경에서나 매우 높은 확장성이 요구되는 서버 환경에서는
용납하기 힘든 overhead를 지니고 있기 때문에 새로운 할당 알고리즘이 사용되고 있다.

slob과 slub 할당자는 각각 2.6.16과 2.6.22 버전에서 추가된 것으로
단 1KiB의 메모리도 아쉬운 제한적인 임베디드 환경에서는 slob을,
많은 수의 CPU와 (메모리) 노드로 구성된 서버 환경에서는 slub을 사용할 수 있다.
(2.6.23 버전 이후로는 x86에서 기본 할당자로 slab 대신 slub이 설정되어 있다.)

많은 커널 서적에서 이미 자세히 설명하고 있지만
먼저 slab 할당자의 구조에 대해서 간략하게 살펴본 후에 slub과 slob에 대해서도 살펴보기로 하자.

사실 slab 할당자는 일반적인 할당자가 아니라 특정한 객체(자료 구조)에 대해서만 할당을 수행하기 때문에
slab을 이용하기 위해서는 먼저 해당 slab이 어떤 객체를 다룰지 지정해 주어야 한다.
다르게 표현하면, slab이 해당 객체에 대한 캐시를 관리해주는 역할을 한다고 볼 수 있으므로
먼저 객체에 대한 캐시를 만들어 두고 이 후에 필요할 때 캐시에서 객체를 할당받을 수 있는 것이다.

따라서 slab 할당자는 주어진 객체의 크기에 따라 커널의 buddy system으로부터 적당한 수의 페이지를 할당받고
이를 하나로 묶어 여러 객체를 저장할 수 있는 단위로 관리하는데 이것이 바로 slab이다.
아래는 2개의 페이지로 구성된 하나의 slab을 나타낸 그림이다.

각 slab은 실제 객체 이외에도 slab 자체에 대한 메타 정보를 포함하는 헤더와
slab 내의 모든 객체에 대한 할당 정보를 포함하는 테이블을 포함한다.
(이는 객체의 크기에 따라 slab 외부에 존재할 수도 있다.)

이렇게 만들어진 slab은 객체가 사용된 정도에 따라 3가지로 구분되는데 (full, partial, empty)
이는 또한 kmem_list3라는 구조체를 통해 (페이지 할당을 관리하는 단위인) 노드 별로 관리된다.

하지만 이러한 slab은 성능 상의 이유로 메모리 할당 시 직접 접근하지 않고
각 CPU 별로 할당된 array_cache 구조체를 통해 객체 단위로 캐시된다.

이 외에도 kmem_list3에는 각 노드 별로 공유하는 array_cache 구조체를 두어
CPU 별 캐시 부족 시 공유 캐시로부터 CPU 별 캐시를 다시 채울 수 있도록 2차 캐시로 사용하며,
메모리 부족 시 해당 CPU가 속한 노드가 아닌 외부 노드에서 할당한 객체가 있다면
해당 객체를 해지할 때 이를 별도의 array_cache에 저장해 두었다가 해당 노드의 slab으로 돌려준다.
이를 alien 캐시라고 하며 이는 각 kmem_list3 당 모든 노드 별로 존재한다.

따라서 slab 할당자는 기본적으로 실제 할당 시 사용되는 slab (page) 외에도
각 CPU 별 캐시 및 노드의 공유 캐시와 alien 캐시를 가지므로
최대 NR_CPUS + MAX_NUMNODES + MAX_NUMNODES^2 개의 array_cache가 필요하다.

array_cache는 limit 개로 구성된 객체 포인터 배열을 가지고 있으며
부족 시 batchcount 개의 객체 포인터를 공유 캐시 혹은 slab으로부터 채운다.
공유 캐시는 최대 shared(factor) * batchcount 개의 객체 포인터를 유지하게 된다.
(즉, 공유 캐시를 구성하는 array_cache의 limit 값은 shared * batchcount이다.)
이들은 /proc/slabinfo 파일을 통해 확인 및 변경이 가능하다. (tunables 항목)

아래는 array_cache 구조체의 구조를 나타낸 그림이다.

이렇듯 slab 할당자는 많은 캐시와 (그에 따른) 메타 정보를 필요로하기 때문에
적지 않은 양의 메모리를 단지 slab을 관리하기 위한 용도로 낭비(?)하게 된다.

slub 할당자는 이러한 낭비를 없애 메모리 활용을 더욱 효율적으로 하기 위해 개발되었으며
slab 할당자와 동일한 API를 제공하므로 단지 커널 빌드 시 slub을 사용하도록 선택하였다면
아무런 소스 변경 없이 곧바로 slub 할당자를 이용할 수 있다.

slub으로 할당된 객체들은 동일 slub 내의 다음 (free) 객체에 대한 포인터를 직접 포함한다.
이는 RCU, 생성자(ctor), 디버깅 기능 사용 유무에 따라 객체 내에 있을 수도 있고 밖에 있을 수도 있다.
페이지 내의 이용 가능한 첫 객체는 page 구조체 내의 freelist 필드가 가리키도록 하였다.
slub의 메타 정보들은 모두 page 구조체 내에 포함되어 있으므로 별도의 메모리를 낭비하지 않는다.
(대신 page 구조체가 많은 union들로 인해 복잡해지고 말았다..)

또한 slub은 기본적으로 (거의) 동일한 크기의 객체에 대한 캐시는 통합(merge)하여 관리하기 때문에
이로 인한 메타 정보 및 중복된 캐시를 크게 줄일 수 있으므로 메모리 효율을 높이게 되었다.
현재 사용 중인 시스템에서 /sys/kernel/slab 디렉터리에 생성된 모든 slub 정보가 표시되는데
128 바이트 크기의 slub의 경우 총 10개의 객체를 관리하고 있는 것을 볼 수 있다.

$ ls -l /sys/kernel/slab/ | grep 00128
drwxr-xr-x 2 root root 0 2010-06-04 12:10 :t-0000128
lrwxrwxrwx 1 root root 0 2010-06-04 12:10 bip-1 -> :t-0000128
lrwxrwxrwx 1 root root 0 2010-06-04 12:10 ecryptfs_key_tfm_cache -> :t-0000128
lrwxrwxrwx 1 root root 0 2010-06-04 12:10 ecryptfs_open_req_cache -> :t-0000128
lrwxrwxrwx 1 root root 0 2010-06-04 12:10 eventpoll_epi -> :t-0000128
lrwxrwxrwx 1 root root 0 2010-06-04 12:10 ip_mrt_cache -> :t-0000128
lrwxrwxrwx 1 root root 0 2010-06-04 12:10 kmalloc-128 -> :t-0000128
lrwxrwxrwx 1 root root 0 2010-06-04 12:10 pid -> :t-0000128
lrwxrwxrwx 1 root root 0 2010-06-04 12:10 request_sock_TCP -> :t-0000128
lrwxrwxrwx 1 root root 0 2010-06-04 12:10 scsi_sense_cache -> :t-0000128
lrwxrwxrwx 1 root root 0 2010-06-04 12:10 uid_cache -> :t-0000128

참고로 /proc/slabinfo 파일에서는 실제로 생성된 캐시에 대한 정보 만을 보여주기 때문에
이렇게 merge된 객체(alias)들에 대한 정보는 표시되지 않는다.

slub 할당자도 성능을 향상시키기 위한 CPU 별 캐시가 존재하지만
(slab의 array_cache처럼) 직접 객체의 포인터를 배열에 저장하는 것이 아니라,
해당 페이지의 첫 객체 포인터 만을 참조하며 slub 내의 (포인터) 정보를 재활용한다.
또한 노드 별로는 예전처럼 3개의 리스트 대신 partial (slub)의 리스트 만을 관리하고
공유 캐시 및 alien 캐시도 유지하지 않는다.

마지막으로 slob은 이러한 slub의 overhead마저도 부담스러운 경우 사용할 수 있는데
페이지를 작은 단위(SLOB_UNIT)로 나누고 이를 블럭으로 묶어 할당을 수행한다.
(페이지 크기에 따라 다르지만 대부분의 경우 SLOB_UNIT은 2 바이트 크기의 구조체이다.)

slob 할당자는 위의 slab이나 slob처럼 특정 객체를 위해서만 사용되는 것이 아니라
일정한 크기 범위 내의 객체의 할당 요청을 모두 처리하는 범용 할당자이다.
다만 페이지 크기 이상의 객체는 직접 할당할 수 없으므로 buddy system을 이용한다.

구체적으로는 first-fit 알고리즘을 이용하는데
먼저 (새로운) 페이지를 하나의 블럭으로 구성한 뒤 요청받은 크기만큼 할당해주고
나머지 영역은 다시 새로운 블럭으로 구성한다.
중간에 할당되었던 블럭이 해지되면 블럭의 크기와 다음 free 블럭까지의 offset 정보를
각각 0번과 1번 unit에 저장하여 free block list를 구성한다.
만일 블럭이 1개의 unit으로만 구성되었다면 offset 정보를 음수로 저장한다.
(따라서 SLOB_UNIT은 s16 타입의 필드 하나로 구성된다.)

kmalloc/kfree의 경우는 약간 다른데
일반적으로 slab이나 slub은 kmalloc/kfree를 해당 크기의 캐시를 생성하여 구현하는데
slob에서는 그렇지 않고 약간 다른 구현을 사용하였다.
어차피 slob이 범용 메모리 할당자로 동작하기 때문에 직접 내부 알고리즘을 이용하는데
문제는 (kmem_cache_create() 함수로) 캐시를 생성하면 항상 해당 요청에 대한 크기를 알 수 있지만
(kmalloc()으로 할당받은 메모리를) kfree()할 때는 그 크기를 알 수 없다는 것이다.
따라서 kmalloc()으로 할당 시에는 정렬 기준값(align) 만큼의 메모리를 더 할당하여
앞쪽의 4바이트(unsigned int 타입)에 요청한 크기를 저장해 둔다.

slob에서 사용하는 페이지들을 관리하기 위해서 slub과 마찬가지로 page 구조체의 필드들을
다른 용도로 이용해야 하는데, slub에서처럼 page 구조체의 정의 자체를 바꾸어 버리는 대신
slob_page 구조체를 새로 생성하여 기존의 page 구조체와 통째로 union 형식으로 구성하고
(slob에서) 필요한 필드만 새로운 이름으로 접근할 수 있도록 하였다.
(덕분에 page 구조체의 정의가 더 이상 지저분해지지 않을 수 있었다..;;)

slob은 메모리 할당 요청을 처리하는 페이지를 요청의 크기에 따라
free_slob_small/medium/large의 3개의 (전역) 리스트로 구분하여 관리하는데
아마도 (internal) fragmentation을 최소화하기 위한 것으로 생각된다.
(다시 말하지만 slob은 페이지 크기 이상의 할당 요청은 (직접) 처리하지 않는다.)

slob은 캐시 디스크립터에도 최소한의 정보 만을 유지하며
할당된 메모리 영역에도 메타 정보를 필요로 하지않고 (kmalloc/kfree는 예외)
CPU 별 캐시나 노드 별 리스트 및 캐시를 전혀 사용하지 않으므로
실제 동적 메모리 할당을 위한 것이 아닌 메타 정보를 위한 메모리 사용량을 거의 없앨 수 있다.