slab allocator

쉽게 설명하자면...  task_struct 나 bio, bio_vec 같이 linux kenrel 에서 굉장히 빈번하게 사용되는 자료 구조들을 효율적으로 할당 / 해제 관리를 위한 메모리 관리 알고리즘이다.

특별한 함수가 있는것이 아니라..

kcalloc, kmalloc 에서 호출해서 사용한다.

SLAB Allocator

 - 1994년 Sun Microsystems의 Solaris 2.4 운영체제에 처음 적용된 이후 리눅스를 포함한

    대부분의 UNIX 계통의 운영체제에서 사용하는 메모리 할당 정책.

 - 일정량의 내부 단편화 현상을 허용하는 trade off을 통해 외부 단편화 현상을 해결한 메모리

    관리 기법임.

 - 10년이 넘도록 이러한 메모리 관리 기법을 대체할 만한 대안이 존재하지 않았음.

 - SLAB allocator (sitting on top of the low-level page allocator) manages caches of objects of a specific size, allowing for fast and space-efficient allocations. (http://lwn.net/Articles/229984/)

 - "The Slab Allocator: An Object-Caching Kernel Memory Allocator (1994)" by  Jeff Bonwick

 - coloring :  

 

SLOB Allocator

 - 리눅스 커널 2.6.15 부터 지원됨

 - 임베디드 관련 커널 config 항목에 포함되어 있음

 - SLAB 할당자를 운용하기 위한 복잡한 자료구조들을 diet하고 metadata를 없애는등 

    최대한 메모리의 사용량을 줄이도록 접근한 방식임

 

SLUB Allocator

  - 리눅스 커널 2.6.22 부터 포함

  - http://lwn.net/Articles/229984/

  - SLAB을 대체하기 위함.

  - TO BE RESOLVED

[출처] Beyond SLAB Allocator|작성자 라키시스

이중 linux 에서 사용되고 있는 slab 을 본격적으로 보자.

- slab

http://www.cyworld.com/amitabul00/3969337

Slab Allocator

 “슬라브”라고 들어봤나? 공사장에서 쓰는 회색에 돌판지도 아니고 나무판자도 아닌 그런게 있다. 단어 뜻은 석판, 널판지 정도가 된다.

 리눅스에서도 이 널판지가 있는데 그놈이 slab이다. slab의 역할로 보면 캐시에 들어가는 각 object라고 보면 되겠다. 보통 캐시라고 하면 저 멀리서 정보를 가져왔다가 사용하고 바로 반납하는게 아니고 특정 공간에 넣어 두고 다시 같은 정보가 필요할 때 저 멀리서 다시 같은 정보를 가져오는게 다시 꺼내 쓸 수 있도록 한것이 캐시 시스템이다. 근데 요놈은 역할은 같긴한데 정보를 저장한다기 보다 빈공간을 캐시한다고 해야하나? slab할당자는 빈공간을 캐시하고 있다가 공간 요청이 들어오면 그 공간을 꺼내주는 역할을 하고 있다.

 구조는 cache 리스트가 있고 cache 안에 slab들이 있고 각 slab 들은 object라는 놈과 연결되어 사용할 수 있게 된다. slab들의 상태에 따라 cache 상태가 정해지고 그 종류는 full(모든 객체가 사용중), free(모든 객체가 사용가능), partial(부분적으로 사용중)로 구분된다.

 

slab의 최소 크기는 32Bytes 이며 2의 승수 크기의 128KBytes 크기까지 유지한다. 각 slab은 물리적으로 연속된 공간이다. 최대 128Kbytes 까지 물리적 연속된 공간을 할당해줄 수 있다. 만약 캐시가 부족할 경우 버디할장자로부터 페이지 프레임을 할당받는다.

kmalloc() 함수를 통해 할당받을 수 있다.

슬랩 할당자(Slab Allocator)

http://timewizhan.tistory.com/42

커널은 메모리의 단편화를 조금이나 해결하기 위해 다양한 방법을 사용한다. 그 중에 현재 커널은 버디 시스템과 슬랩 할당자를 사용하는데..
외부 단편화를 해결하기 위해서는 버디 시스템, 내부 단편화를 해결하기 위해서는 슬랩 할당자를 사용한다. 그래서.... 오늘은 내부 단편화를 해결하는 슬랩 할당자에 대해서 공부해 보자.~~

i

위 그림과 같이 슬랩 할당자의 구조는 다음과 같다.
각각의 kmem_cache는 연결된 리스트로써 서로서로를 연결하고 있다.
또한 하나의 kmem_cache는 slab를 가지고 있으며 slab은 full, partial, empty로 나뉜다. 
partial slab은 해당 페이지와 연결되 있고, 해당 페이지는 페이지를 참조하는 여러 object들을 가지고 있다.

이렇듯... 슬랩 할당자는 꼬리에 꼬리를 무는.. 예를 들어 이런거랄까나..a->b->c->d->... 구조체의 연속을 타고있는.. ;;;;

그러면 자료 구조를 봐보자.

i

i

먼저 kmem_cache와 kmem_list3 자료 구조이다.
kmem_cache가 kmem_list3을 참조하여 슬랩 객체들 관리를 kmem_list3에게 맡긴다.
그래서 slabs_partial, slabs_full, slabs_free를 통해 슬랩 객체를 관리한다.

i

kmem_list3에서 관리하는 슬랩 자료 구조는 위 그림과 같다.

그래서 밑의 그림을 보면 구조는 다음과 같이 진행 된다.

i

한가지! struct slab를 생성할 때 저장되는 공간이 2가지 영역이 있다.
1. 외부 슬랩 디스크립터로써 일반 캐시에.:
2. 내부 슬랩 디스크립터로써 슬랩에 할당한 첫 번째 페이지 프레임의 시작 부분에..
이는.. 객체의 크기에 따라 결정되는데 객체가 512바이트보다 작을 경우와 슬랩, 객체 디스크립터를 저장할 공간이 있을 경우에 2번을 따른다.

i

그래서 위 그림에서 보이는 것처럼 
1. 외부 객체로 저장될 때에는 kmem_cache의 slabp_cache 필드가 가르키는 일반 캐시에 저장한다.
2. 내부 객체로 저장될 때에는 슬랩 내부에 그냥 저장한다..~

그리고. 잠시만 struct slab의 필드를 살펴보면 좀 더 쉽게 다가올 것이다.
colouroff : 페이지에서 현재 사용 중인 슬랩의 위치
s_mem : 슬랩에서 첫 번째 객체가 시작하는 위치
inuse : 현재 사용 중인 객체 수
free : 현재 사용하지 않는 공간 (type이 kmem_bufctl_t 인데.. unsigned int로 typedef 된 것이다.)

cat slabinfo 를 보면

# cat slabinfo 

slabinfo - version: 2.1

# name            <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables <limit> <batchcount> <sharedfactor> : slabdata <active_slabs> <num_slabs> <sharedavail>

dm_crypt_io            0      0    152   26    1 : tunables    0    0    0 : slabdata      0      0      0

kvm_vcpu               0      0  14608    2    8 : tunables    0    0    0 : slabdata      0      0      0

ip6_dst_cache         75     75    320   25    2 : tunables    0    0    0 : slabdata      3      3      0

...

task_struct          416    460   5888    5    8 : tunables    0    0    0 : slabdata     92     92      0

anon_vma           10218  10248     72   56    1 : tunables    0    0    0 : slabdata    183    183      0

shared_policy_node  15687  15895     48   85    1 : tunables    0    0    0 : slabdata    187    187      0

numa_policy         1360   1360     24  170    1 : tunables    0    0    0 : slabdata      8      8      0

radix_tree_node    23370  23380    568   28    4 : tunables    0    0    0 : slabdata    835    835      0

idr_layer_cache      840    840    544   30    4 : tunables    0    0    0 : slabdata     28     28      0

dma-kmalloc-8192       0      0   8192    4    8 : tunables    0    0    0 : slabdata      0      0      0

dma-kmalloc-4096       0      0   4096    8    8 : tunables    0    0    0 : slabdata      0      0      0

dma-kmalloc-2048       0      0   2048   16    8 : tunables    0    0    0 : slabdata      0      0      0

dma-kmalloc-1024       0      0   1024   32    8 : tunables    0    0    0 : slabdata      0      0      0

dma-kmalloc-512        0      0    512   32    4 : tunables    0    0    0 : slabdata      0      0      0

dma-kmalloc-256        0      0    256   32    2 : tunables    0    0    0 : slabdata      0      0      0

dma-kmalloc-128        0      0    128   32    1 : tunables    0    0    0 : slabdata      0      0      0

dma-kmalloc-64         0      0     64   64    1 : tunables    0    0    0 : slabdata      0      0      0

dma-kmalloc-32         0      0     32  128    1 : tunables    0    0    0 : slabdata      0      0      0

dma-kmalloc-16         0      0     16  256    1 : tunables    0    0    0 : slabdata      0      0      0

dma-kmalloc-8          0      0      8  512    1 : tunables    0    0    0 : slabdata      0      0      0

dma-kmalloc-192        0      0    192   21    1 : tunables    0    0    0 : slabdata      0      0      0

dma-kmalloc-96         0      0     96   42    1 : tunables    0    0    0 : slabdata      0      0      0

kmalloc-8192         112    112   8192    4    8 : tunables    0    0    0 : slabdata     28     28      0

kmalloc-4096         197    240   4096    8    8 : tunables    0    0    0 : slabdata     30     30      0

kmalloc-2048        1040   1040   2048   16    8 : tunables    0    0    0 : slabdata     65     65      0

kmalloc-1024        1241   1312   1024   32    8 : tunables    0    0    0 : slabdata     41     41      0

kmalloc-512         1905   1952    512   32    4 : tunables    0    0    0 : slabdata     61     61      0

보기에는  system 에 관련된 몇몇 struct 들을 slab allockator 로 할당해서 관리하는 것 같다.

모든 struct 들이 저런식으로 커널에서 관리되는것은 아니겠지...

task_struct 의 slab size 는 5888(0x1700) 인데... 시작주소를 찍어보면 저 숫자의 배수로 주소가 증가한다고 한다.

http://daehee87.tistory.com/253

slab allocator는 새로운 slab을 만들때  keme_getpages() 함수를 호출하는데, 이함수의 내부를 보면 alloc_pages 를 통해 page 를 할당받는다.

결국, slab allocator 는 buddy system 으로 부터 page 단위의 메모리를 받아서, 그 이하 size 의 새부 메모리를 관리하는 것으로 보입니다.

마찬가지로 해지할때는 kmem_freepages 함수를 호출하는데 내부적으로 free_pages 를 호출하고 있다.

(참조 : 리눅스커널의 이해 8장 메모리 관리 345p)

궁금한것

- task_struct 를 비롯한 주요 struct 와 kmalloc 는 slab allocator로 관리되는 것으로 보인다.

-> kernel 에서 slab_alloc 을 호출하는 함수들

kcalloc->__kmalloc->slab_alloc,

kmalloc->__do_kmalloc->...->__cache_alloc->kmemcheck_slab_alloc

- slab 를 쓰는 bio 의 할당하는 함수 추적

blk-barrier.c

bio = bio_alloc(GFP_KERNEL, 0);

-> bio_alloc_bioset()

-> mempool_alloc()

-> element = pool->alloc(gfp_temp, pool->pool_data);

init_bio()

-> mempool_create_kmalloc_pool()

-> mempool_create()

-> mempool_create_node()

pool->alloc = alloc_fn; //alloc_fn == mempool_kmalloc

void *mempool_kmalloc(gfp_t gfp_mask, void *pool_data)

{

size_t size = (size_t)pool_data;

return kmalloc(size, gfp_mask);

}

즉, bio 의 할당은 kmalloc 로 하게 되고, kmalloc 는 slab alloc 를 사용한다.

- malloc 은 어떨까?

-> 아래 "Virtual Memory 전반에 관한 좋은 강좌"를 읽어보면 malloc 할당에 대한 자세한 이야기는 안나오지만, kmalloc 만 slab allocator 를 사용하는 것으로 보인다.

- slab allocator 를 사용함으로써 얻을 수 있는 이득에 대한 글

http://blog.naver.com/lache96?Redirect=Log&logNo=140051474432

- Virtual Memory 전반에 관한 좋은 강좌

https://www.linux.co.kr/home2/board/subbs/board.php?bo_table=lecture&wr_id=1641