Slab Allocator 내용
- http://jake.dothome.co.kr/slub/
- https://wogh8732.tistory.com/418

kmem_cache_init()
- 함수 debug_guardpage_minorder()는 CONFIG_DEBUG_PAGEALLOC = no이므로 0을 리턴한다
- 함수 __slub_debug_enabled()는 CONFIG_SLUB_DEBUG = y이고 CONFIG_SLUB_DEBUG_ON = n이므로 static key 변수 slub_debug_enabled = false이다. 따라서 false를 리턴한다 (default = false). 만약 true인 경우에는 함수 no_hash_pointers_enable()로 경고를 출력한다. 경고는 커널 메모리 주소가 로그 등으로 출력되어 보안상 문제가 될 수 있다는 내용이다. 즉 디버깅 용으로만 사용해야 한다.
- 전역 변수 kmem_cache 구조체 포인터 kmem_cache_node가 static 변수 boot_kmem_cache_node를 가리키게 하고, 전역 변수 kmem_cache 구조체 포인터 kmem_cache는 static 변수 boot_kmem_cache를 가리키게 한다.
- 모든 normal memory를 가지는 node에 대해서 루프를 돌면서 slab nodes bitmask를 set한다
- 함수 create_boot_cache() <— 진행 중

debug_guardpage_minorder()
- CONFIG_DEBUG_PAGEALLOC = y일 경우 전역 변수 _debug_guardpage_minorder를 리턴한다
- _debug_guardpage_minorder는 static key 변수로 default는 false이다
- _debug_guardpage_minorder = true이면 전역 변수 slub_max_order를 0으로 세팅한다
- 전역 변수 slub_max_order는 default로 PAGE_ALLOC_COSTLY_ORDER = 3으로 초기화되어 있다
- PAGE_ALLOC_COSTLY_ORDER = 3은 reclaim 경계를 정의한다. 3 이하 order의 메모리 요청이 들어오면 reclaim을 해서 메모리를 반환해주지만 3보다 큰 경우는 메모리가 없으면 그냥 메모리 요청이 실패한다

create_boot_cache()
- 인자로 kmem_cache s, name, size, slab flags, user offset, user size를 받는다
- slab flags는 SLAB_HWCACHE_ALIGN, user offset과 user size는 0으로 들어왔다
- align = ARCH_KMALLOC_MINALIGN = ARCH_DMA_MINALIGN = 128이다
- s->name과 s->size, s->object_size를 각각 name, size 인자로 입력한다
- size가 power of 2가 아니면 align을 align과 size의 max로 잡는다. 현재 세팅으로는 128이 된다
- 함수 calculate_alignment()로 s->align을 계산한다. 현재값은 128
- s->useroffset, s->usersize를 인자값으로 세팅한다
- 함수 __kmem_cache_create() <— 진행 중

calculate_alignment()
- flags가 SLAB_HWCACHE_ALIGN이므로 cpu cache size를 구해서 align을 재계산한다
- 재계산된 align이 8B보다 작으면 8B로 잡는다
- 계산된 align을 8B align시켜 리턴한다

__kmem_cache_create()
- 인자로 kmem_cache, slub flags를 받는다
- 함수 kmem_cache_open()를 수행한다 <— 진행 중

kmem_cache_open()
- 함수 kmem_cache_flags()로 command line의 slub_debug string을 parsing하여 slub flags를 업데이트한다
- CONFIG_SLAB_FREELIST_HARDENED = y인 경우 함수 get_random_long()으로 s->random을 세팅한다

- 함수 calculate_sizes()로 slab page의 order 및 slab object의 형태와 크기를 flag에 따라 결정한다
- 전역 변수 disable_higher_order_debug  = 1이면 메타 데이터에 의해 slab page의 order가 증가하는 것을 허용하지 않는다. 즉, s->size의 order가 s->object_size의 order보다 크면 모든 meta data flags (redzone, poison, owner)를 s->flags에서 제거한다. 그리고 함수 calculate_sizes()를 재호출하여 slab page를 재설정한다
- 전역 변수 disable_higher_order_debug는 함수 parse_slub_debug_flags()에서 command line parsing을 통해 slub_debug option에서 ‘o’가 들어오면 1로 세팅된다

- slab page의 debug flags 중에서 SLAB_CONSISTENCY_CHECKS, SLAB_STORE_USER, SLAB_TRACE는 cmpxchg 명령어를 사용하면 consistency 문제가 있다
- 그러나 현재 s->flags에 해당 debug flags가 없고 현 시스템 cpu가 cmpxchg double 명령어를 가지고 있으면 s->flags에 __CMPXCHG_DOUBLE를 추가하여 mpxchg double 명령어를 사용하여 성능을 향상시키도록 한다

- s->min_partial을 s->size에 맞게 세팅한다 (log 값의 절반)
- s->min_partial은 partial list에 들어가는 slab page의 수이다. 최소 5이고 최대 10이다.

- s->cpu_partial을 s->size에 따라 세팅한다. size에 따라 2, 6, 13, 30을 가질 수 있고 size가 크면 작은 값이 할당된다. 이 값은 cpu partial list에서 관리되는 object의 수이다
- slub_debug_enabled = 0이면 0으로 세팅된다. 즉 cpu partial을 쓰지 않는다

- s->remote_node_defrag_ratio = 1000 으로 세팅한다

- slab_state >= UP이면 함수 init_cache_random_seq()로 list 순서를 randomize한다 <— 진행 중

calculate_sizes()
- 인자로 kmem_cache s와 force_order를 인자로 받는다

- s->object_size를 8B align에 맞추어서 size 지역 변수를 계산한다
- flags에 SLAB_POISON이 설정되어 있고 SLAB_TYPESAFE_BY_RCU flag는 off, s->ctor도 NULL인 경우 s->flags에 __OBJECT_POISON을 추가한다. 아니면 __OBJECT_POISON을 flags에서 제거한다
- size == s->object_size이고 flags에 SLAB_RED_ZONE이 set되어 있으면 size를 1B 증가시켜 우측 redzone 공간을 만든다
- object size와 right red zone 크기를 더해서 s->inuse를 정한다

- flags에 RCU 또는 POISON 옵션이 있거나 constructor가 설정되어 있거나 flags에 RED ZONE 옵션이 있고 object size가 word size보다 작으면 s->offset을 size로 설정하여 free pointer 위치를 object 다음으로 옮긴다. 그리고 size를 1 word만큼 증가시킨다
- free pointer 위치를 object 뒤에 붙이지 않는 경우에는 object의 중간 위치에 word align down시켜 free pointer 위치를 정한다
- flags에 SLAB_STORE_USER가 on인 경우 size에 call stack 정보 저장을 위한 track 구조체의 2배 크기를 더한다
- flags에 RED ZONE 설정이 되어 있는 경우 s->red_left_pad에 word size를 s->align만큼 align시켜 설정한다. 그리고 size를 red_left_pad만큼 증가시킨다. 추가로 overwrite catch를 위해 size를 1 byte 증가시킨다

- size를 s->align에 맞추고 s->size에 저장한다
- Montgomery division을 위한 메타데이터 reciprocal_size를 계산해서 s->reciprocal_size에 저장한다
- 인자 forced_order >= 0 이면 order를 forced_order로 설정한다. 아니면 함수 calculate_order()로 size로부터 order를 계산한다
- order < 0이면 0을 리턴한다

- order > 0 이면 s->allocflags에 __GFP_COMP 추가
- s->flags에 SLAB_CACHE_DMA가 있으면 s->allocflags에 GFP_DMA 추가
- s->flags에 SLAB_CACHE_DMA32가 있으면 s->allocflags에 GFP_DMA32 추가
- s->flags에SLAB_RECLAIM_ACCOUNT가 있으면 s->allocflags에 __GFP_RECLAIMABLE 추가

- order와 size로부터 order object를 계산한다. order object는 상위 16비트에 order가 저장되고 하위 16비트에 number of objects per slab page = slab page / size 가 저장된다. slab page 크기는 PAGE SIZE << order이다.
- 계산한 order object를 s->oo에 저장한다
- object를 저장하기 위한 최소 page order를 계산하고 최소 page order와 size로부터 order object를 계산, s->min에 저장한다
- s->max에 s->oo를 저장한다
- s->oo에서 object부분이 유효하면 1, 아니면 0을 리턴한다

calculate_order()
- slab page의 order를 인자로 들어온 size로부터 계산한다

- 전역 변수 slub_min_objects = 0이면 현재 present cpu의 개수로부터 min_objects를 초기화한다. 대략 log2(nr_cpus)x4에 해당하는 값이다. 만약 slub_min_objects != 0이면 해당 값을 그대로 초기값으로 사용한다
- 전역 변수 slub_max_order = PAGE_ALLOC_COSTLY_ORDER = 3으로부터 max_objects를 slub page가 max order일 때 들어갈 수 있는 object의 최대 개수로 계산한다
- min_objects가 max_objects보다 크면 같도록 재조정한다

- 루프를 돌면서 min_object와 낭비될 수 있는 메모리 공간 비율 (fraction)을 조정하면서 slab page의 order를 산출한다
1) 현재의 min_objects 값에서 order 산출을 시도하고, 실패하면 min_objects를 1 감소시킨다. min_objects = 1이 되면 루프를 중단한다
2) 주어진 min_objects 값에서 fraction은 1/16에서 시작하여 order 산출을 시도한다. 실패하면 fraction을 2배씩 허용한다. 최대 1/4에서도 실패하면 현재 min_objects 값에서는 order 산출을 실패한 것으로 보고 min_objects를 1 감소시킨다
3) 주어진 min_objects/fraction 값에서 order 산출을 시도한다. order 계산은 함수 slab_order()를 사용한다. 계산된 order가 slub_max_order보다 같거나 작으면 order 산출을 성공한 것으로 보고 해당 order를 리턴한다. 아니면 order 산출을 실패한 것으로 보고 fraction을 2배 증가시킨다

- 리턴되지 않으면 order 산출이 min_objects = 2에서도 실패한 것이다
- min_objects = 1에 대해, max_order = slub_max_order, fraction = 100%로 놓고 함수 slab_order()로 order를 재산출한다. 나온 값이 slub_max_order 이하이면 성공으로 해당 값을 리턴한다
- 여기서도 실패하면 min_objects = 1, max_order = MAX_ORDER, fraction = 100%로 놓고 함수 slab_order()로 order를 재산출한다. 나온 값이 slub_max_order 이하이면 성공으로 해당 값을 리턴한다
- 여기서도 실패하면 에러를 리턴한다

slab_order()
- 인자로 주어진 object size, min_object, max_order, fraction을 가지고 최적의 slab order를 산출하여 리턴한다

- 기본적으로 작은 order가 내부 단편화를 막기 때문에 선호하나 object 크기가 크면 외부 단편화가 발생하기 때문에 1/16보다 메모리 낭비가 발생하면 order를 증가시킨다
- 최소한 인자로 들어온 min_object 만큼의 object 수는 slab page에 들어오도록 order를 정한다. 이는 성능 문제로, 최소한 일정 수의 object가 한 slab page 안에 있어야 partial list 업데이트가 너무 빈번하게 발생하지 않기 때문이다. partial list update는 list lock이 필요하여 성능에 부하가 된다
- 인자로 들어온 max_order보다 큰 order는 고려하지 않는다
- slab minimum order 요청이 너무 크게 들어오면 2^14개의 object가 들어갈 수 있는 order를 리턴해준다
- 2^12 x 2^3 (PAGE_ALLOC_COSTLY_ORDER) = 2^15

- 전역 변수 slub_min_order로부터 계산된 slab page 내의 object 수가 2^15보다 크면 2^14개의 object가 들어갈 수 있는 order를 리턴한다
- order를 최소값부터 1씩 증가시켜 max_order까지 루프를 돌면서 order를 산출한다
- 최소값은 slub_min_order와 인자로 들어온 min_object 만큼의 object를 포함할 수 있는 order 중 큰 값이다
- 루프에서 계산된 order에 대해 아래와 같이 메모리 낭비 비율 (fraction)을 산출하여 인자로 들어온 fraction보다 메모리 낭비가 크지 않으면 해당 order를 리턴하고 아니면 다시 루프를 돌린다. 만약 max_order에서도 메모리 낭비가 크면 그냥 max_order를 리턴한다
- 산출된 order를 리턴한다

init_cache_random_seq()
- 함수 cache_random_seq_create() 내의 freelist_randomize()에서 Fisher-Yates 알고리즘으로 list 순서를 random하게 변경한다
- https://daheenallwhite.github.io/programming/algorithm/2019/06/27/Shuffle-Algorithm-Fisher-Yates/

Left redzone 관련 패치
- https://github.com/torvalds/linux/commit/d86bd1bece6fc41d59253002db5441fe960a37f6

min_partial 관련 패치
- https://github.com/torvalds/linux/commit/5595cffc8248e4672c5803547445e85e4053c8fc