Slab Memory Allocator -1- (구조)

<kernel v5.0>

Slab Memory Allocator

슬랩(Slab, Slub, Slob) object는 커널이 사용하는 정규 메모리 할당의 최소 단위이다. 커널은 다음과 같이 3가지 중 하나를 선택하여 빌드되어 사용된다. 서로에 대한 차이점을 알아본다. 차이점을 구분하지 않고 설명할 때에는 한글로 슬랩으로 표현한다. 또한 구조 및 소스 분석은 모두 Slub 구현만 분석한다.

 

Slab

• 커널 메모리 관리의 핵심으로 2007~8년까지 default로 사용해 왔었다.
• 배열로 된 Slab object 큐가 CPU와 노드에서 사용된다.
• 메타 데이터 조각이 앞쪽에 배치되어 오브젝트의 정렬이 어려워 메모리 부족으로 캐시를 클리닝하는 경우 매우 복잡한 처리가 필요하다.
• 처음 생성된 slab은 full 리스트에서 관리되다가 object가 하나라도 사용되는 경우 그 slab은 partial 리스트로 이동되어 관리된다. 다 사용하는 경우 다시 이동되어 empty 리스트에서 관리된다.
• slab은 성능을 향상시키기 위해 노드별(per-node) 및 cpu별(per-cpu)로 각각 관리된다.

 

Slub

• 2007~8년부터 메모리가 충분히 있는 임베디드 시스템뿐만 아니라 PC나 서버에서 사용되며, 현재 default로 사용한다.
• Slab과 다르게 메모리 오버헤드를 줄이기 위해  Slab object 큐 대신 단순히 한 페이지의 slub page를 지정하여 사용한다.
• Slab과 다르게 freelist 관리에 대한 공간을 별도로 사용하지 않는다.
• Slab과 다르게 처음 생성된 slub은 object 사용 개수가 0으로 시작하고 partial 리스트로 관리된다. 만일 object가 다 사용되는 경우 slub은 partial 리스트에서 제거되고 관리 매커니즘에서 제외된다. 그러나 그 slub이 하나의 object라도 free 되는 경우 다시 partial 리스트에 추가되어 관리된다.
• Slub 역시 slab과 동일하게 성능을 향상시키기 위해 노드(per-node) 및 cpu별(per-cpu)로 각각 관리된다.
• Slab에 비해 slub을 사용하면서 시스템 내의 slab 캐시가 줄었고(50% 정도), slab 할당자의 지역성(locality)이 향샹되었으며, slab 메모리의 단편화가 줄어들었다.

 

Slob

• low memory footprint를 갖는 임베디드 리눅스에서 선택하여 사용한다.
• 속도는 가장 느리지만 메모리 소모가 가장 적다.

 

슬랩 구조

슬랩 object는 1 개 이상의 페이지 프레임에 배치되는데, 지정된 object 사이즈만큼씩 배치되어 사용된다. 디버그 정보를 위해 object에 메타 정보들이 포함될 수도 있다.

 

슬랩 페이지 내 object 배치

슬랩 object 사이즈에 맞춰 산출된 order 페이지를 버디 시스템으로 부터 할당 받아 1개의 슬랩 페이지를 구성한다. 슬랩 페이지는 동일한 슬랩 object 사이즈로 모두 채운다. 산출된 order는 디폴트로 0~3까지 사용한다.

 

다음 그림은 버디 시스템에서 order-N 페이지를 사용하여 슬랩 페이지를 구성하고, 이 슬랩 페이지에서 할당 가능한 슬랩 object를 배치한 모습을 보여준다.

 

슬랩 캐시

다음 그림과 1개 이상의 슬랩 페이지가 모여 슬랩 캐시가 구성된다. 즉 슬랩 캐시내의 모든 object들은 동일한 사이즈만을 제공한다.

 

다음 그림과 같이 필요한 object 사이즈가 다른 경우 각각의 object 사이즈별로 슬랩 캐시를 만들어 구성할 수 있다. 커널에서 특정 구조체를 많이 사용하는 경우 이렇게 슬랩 캐시를 미리 등록하여 준비한다.

• 예) page, anon_vma, vm_area_struct, task_struct, dentry, skb, …

 

per-node 및 per-cpu 관리 지원

• per-node
  • 노드별로 메모리 접근 속도가 다르므로 슬랩 페이지들을 노드별로 나눠 관리한다.
• per-cpu
  • lock-less를 사용한 빠른 슬랩 캐시 할당을 위해 cpu별로 나눠 관리한다. per-cpu 슬랩 캐시에는 partial 리스트와 1 개의 page가 지정된다.

 

다음 그림은 슬랩 페이지들이 노드별 및 cpu별로 관리되는 모습을 보여준다.

• cpu별로 할당/회수에 관련된 슬랩 페이지가 지정되고, 나머지는 partial 리스트에서 관리한다.

 

Freelist

per-cpu 슬랩 페이지에서 free object의 처음을 가리킨다. 각 free object들은 다음 free object들을 가리키므로 하나의 free object 리스트로 사용된다. 이 freelist에는 해당 cpu 전담으로 할당 가능하고, 해제는 다른 어떠한 cpu들도 사용 가능하다.

 

다음 그림은 cpu별로 슬랩 페이지를 지정하고, freelist를 통해 지정된 슬랩 페이지의 free object를 가리키고 있는 모습을 보여준다.

 

다음 그림은 freelist가 첫 free 슬랩 object를 가리키고, 각 free object끼리 순서대로 연결되는 모습을 보여준다.

 

슬랩 Object 내부 항목

슬랩 Object를 구성하는 항목은 다음과 같다.

Object 영역

• 슬랩 object의 최소 사이즈는 32비트 시스템에서 4 바이트이고, 64비트 시스템에서 8 바이트이다.

 

FP(Free Pointer)

• 페이지 프레임 내에 존재하는 각 object들이 free 상태일 때 object의 선두에 있는 FP(Free Pointer)를 통해 다음 free object를 가리키게한다. object를 디버깅하는 경우 object를 사용하지 않아도 object의 모든 데이터가 uninitialized poison 데이터로 설정되고 이를 모니터하여 혹시 침해를 입지 않는지 확인하는데 사용한다. 따라서 이러한 경우에는 FP(Free Pointer)를 object의 뒤로 이동시켜 사용한다. 그 다음에 owner track 필드와 red zone 필드가 추가되어 디버깅에 사용된다.
• free object들은 offset를 0으로 하여 object의 가장 선두에 FP(Free Pointer)를 사용해 다음 free object의 주소를 가리키고 있다. 다만 SLAB_DESTROY_BY_RCU 및 SLAB_POISON 플래그 옵션을 사용하였거나 생성자를 사용한 경우 offset에 object_size를 대입하여 FP(Free Pointer)를 object_size 만큼 뒤로 이동시킨다.
• 보안 향상을 위해 CONFIG_SLAB_FREELIST_HARDENED 커널 옵션을 사용하여 free 포인터 값들을 encaptualation하여 숨길 수 있다.

 

Poison

• 데이터 주소 침범 등을 검출하기 위해 사용한다.
• 슬랩 object의 소멸 후에 object_size에 해당하는 공간에 poison 값을 기록하고, 슬랩 object의 생성 시 이 값이 변경되는 것을 검출하여 에러 출력으로 리포트한다.
• poison 값은 다음과 같다.
  • 슬랩 object가 사용 중이지만 초기화되지 않은 경우 0x5a=’Z’ 값으로 채운다.
  • 슬랩 object가 사용되지 않을 때 0x6b=’k’ 값으로 채우고 마지막 바이트만 0xa5를 기록한다.
• “slub_debug=P” 커널 파라미터를 사용하여 poison 디버깅을 할 수 있다.
• 디버깅 관련 참고:
  • slub_debug: Detect Kernel heap memory corruption | TechVolve
  • Short users guide for SLUB (2015, Documentation/vm/slub.txt)| Kernel.org

   

Red-Zone

• 데이터 주소 침범 등을 검출하기 위해 사용한다.
• object_size의 좌우에 red-zone 값을 기록한 후 슬랩 object의 생성과 소멸 시에 이 값이 변경되는 것을 검출하여 에러 출력으로 리포트한다.
• red zone 값은 다음과 같다.
  • inactive 상태일 때 0xbb 값으로 채운다.
  • active 상태일 때 0xcc 값으로 채운다.
• “slub_debug=Z” 커널 파라미터를 사용하여 Red-zone 디버깅을 할 수 있다.

 

Owner(User) Track

• 슬랩 object의 생성과 소멸 시 호출한 함수를 각각 최대 16개까지 출력하는 기능이다.
• “slub_debug=U” 커널 파라미터를 사용하여 유저 추적을 할 수 있다.

 

Padding

• Align 정렬에 따른 패딩 값으로 0x5a=’Z’를 채운다.

 

슬랩 Object 내부 구조

주의: 아래 그림에서 FP의 위치는 object_size의 포인터 사이즈 정렬 단위를 사용하여 중앙으로 이동하였다.

• 참고:
  • slub: relocate freelist pointer to middle of object (2020, v5.7-rc1)
  • mm/slub: fix redzoning for small allocations (2021, v5.13-rc7)
  • mm/slub: actually fix freelist pointer vs redzoning (2021, v5.13-rc7)

 

1) 메타 정보 없는 slub object

• 전체 사이즈는 실제 object 사이즈 + align 단위로 정렬한 패딩을 포함한다.
  • 예) object_size=22, align=8
    • inuse=24, size=24
  • 예) object_size=22, align=64
    • inuse=24, size=64
• FP를 가리키는 offset은 0이다.
• 최소 정렬 사이즈는 워드(32bit=4, 64bit=8) 단위를 사용한다.
  • 예) object_size=22, align=0
    • size=24
• SLAB_HWCACHE_ALIGN GPF 플래그를 사용 시 L1 캐시 라인 사이즈보다 작은 경우 캐시 라인 바운싱을 최소화 시키기 위해 align 단위를 2의 차수  단위로 줄인 수에 맞게 사용한다.
  • 예: …, 64, 32, 16, 8
• 예) object_size=22, align=22, flags=SLAB_SWCACHE_ALIGN
  • size=32

 

2) red-zone 정보가 포함된 slub object

• 이전 object가 overwrite 하여도 다음 object를 보호하기 위해 red_left_pad 공간을 추가하였다.
• object 우측에 인접하여 최소 1~최대 워드사이즈(32bit=4, 64bit=8)인 red zone이 들어간다.
  • object 사이즈가 워드 단위로 이미 정렬되어 redzone 자리가 없는 경우 redzone 자리로 워드 사이즈 길이만큼 추가한다.
  • 또한 노란색 공간 즉 사용자용 object 시작 위치는 align 정렬되고, 전체 object 사이즈도 align 정렬된다.

 

3) fp 이동(poison, rcu, ctor)이 포함된 slub object

• object 위치에 별도의 정보를 기록해야 하는 poison 디버깅, rcu를 사용한 free object 지원 또는 생성자를 사용하는 슬랩 캐시들은 FP(Free Pointer) 위치를 object 다음으로 옮겨야 한다. FP(Free Pointer)를 가리키는 offset은 inuse와 동일하다.
• 다음은 FP를 옮겨야 하는 3 가지 항목이다.
  • SLAB_POISON 플래그를 사용한 경우 다음 두 경우에 poison 데이터를 기록한다.
    • object가 free 상태
    • object가 할당되었지만 초기화되지 않은 상태
  • SLAB_TYPESAFE_BY_RCU 플래그를 사용한 경우 rcu를 사용한 free 함수 포인터가 저장된다.
  • 생성자가 사용된 슬랩 캐시의 경우 생성자 함수 포인터를 기록한다.

 

4) owner track 정보가 포함된 slub object

• object 할당/해제하는 사용자를 추적하기 위해 owner track 정보를 추가하였다.
  • SLAB_STORE_USER 플래그 사용 시 owner track 정보를 위해 track 구조체를 두 개 사용한다.

 

5) red-zone + fp 이동 + owner-track 정보가 포함된 slub object

• 그림에는 표기하지 않았지만 KASAN 디버깅을 하는 경우 owner track 뒤에 KASAN 관련 정보가 추가된다.

 

---

구조체

kmem_cache 구조체 (slub)

include/linux/slub_def.h

/*
 * Slab cache management.
 */

struct kmem_cache {
        struct kmem_cache_cpu __percpu *cpu_slab;
        /* Used for retriving partial slabs etc */
        slab_flags_t flags;
        unsigned long min_partial;
        unsigned int size;      /* The size of an object including meta data */
        unsigned int object_size;/* The size of an object without meta data */
        unsigned int offset;    /* Free pointer offset. */
#ifdef CONFIG_SLUB_CPU_PARTIAL
        /* Number of per cpu partial objects to keep around */
        unsigned int cpu_partial;
#endif
        struct kmem_cache_order_objects oo;

        /* Allocation and freeing of slabs */
        struct kmem_cache_order_objects max;
        struct kmem_cache_order_objects min;
        gfp_t allocflags;       /* gfp flags to use on each alloc */
        int refcount;           /* Refcount for slab cache destroy */
        void (*ctor)(void *);
        unsigned int inuse;             /* Offset to metadata */
        unsigned int align;             /* Alignment */
        unsigned int red_left_pad;      /* Left redzone padding size */
        const char *name;       /* Name (only for display!) */
        struct list_head list;  /* List of slab caches */
#ifdef CONFIG_SYSFS
        struct kobject kobj;    /* For sysfs */
        struct work_struct kobj_remove_work;
#endif
#ifdef CONFIG_MEMCG
        struct memcg_cache_params memcg_params;
        /* for propagation, maximum size of a stored attr */
        unsigned int max_attr_size;
#ifdef CONFIG_SYSFS
        struct kset *memcg_kset;
#endif
#endif

#ifdef CONFIG_SLAB_FREELIST_HARDENED
        unsigned long random;
#endif

#ifdef CONFIG_NUMA
        /*
         * Defragmentation by allocating from a remote node.
         */
        unsigned int remote_node_defrag_ratio;
#endif

#ifdef CONFIG_SLAB_FREELIST_RANDOM
        unsigned int *random_seq;
#endif

#ifdef CONFIG_KASAN
        struct kasan_cache kasan_info;
#endif

        unsigned int useroffset;        /* Usercopy region offset */
        unsigned int usersize;          /* Usercopy region size */

        struct kmem_cache_node *node[MAX_NUMNODES];
};

슬랩 캐시를 관리한다.

• cpu_slab
  • per-cpu 캐시
• flags
  • 캐시 생성 시 적용된 플래그 옵션
• min_partial
  • 캐시에서 유지할 최소 partial 슬랩 페이지 수
• size
  • object 및 메타 데이터를 포함하고 align된 사이즈
• object_size
  • 메타 데이터를 제외한 object의 사이즈
• offset
  • 오브젝트 내에서 FP(Free Pointer)의 위치 오프셋
  • SLAB_POISON 및 SLAB_DESTROY_BY_RCU를 사용하지 않는 경우 0
• cpu_partial
  • per-cpu partial 리스트에서 유지 가능한 최대 슬랩 object 수
• oo
  • 슬랩 페이지 생성 시 적용할 권장 order
  • 메모리 부족 상황이 아닌 경우에는 권장 order로 슬랩 페이지를 할당한다.
• max
  • 슬랩 페이지 생성 시 최대 order
• min
  • 슬랩 페이지 생성 시 최소 order
  • 메모리 부족 상황에서는 min order로 슬랩 페이지를 할당한다.
• allocflags
  • object 할당 시 사용할 GFP 플래그
• refcount
  • 슬랩 캐시를 삭제하기 위해 사용할 참조 카운터로 alias 캐시 생성 시 계속 증가한다.
• (*ctor)
  • object 생성자
• inuse
  • 메타 데이터로 인해 추가된 공간을 제외한 실제 사이즈(actual size)
  • 메타 데이터(SLAB_POISON, SLAB_DESTROY_BY_RCU, SLAB_STORE_USER, KASAN)를 사용하지 않을 경우의 size와 동일하다.
• align
  • 정렬할 바이트 수
• red_left_pad
  • 좌측 red-zone 패딩 사이즈
• reserved
  • slub object의 끝에 reserve 시켜야 할 바이트 수
• *name
  • 오직 출력을 위해 사용되는 이름
• list
  • 슬랩 캐시들을 연결할 때 사용되는 리스트 노드
• kobj
  • sysfs에 생성할 때 사용할 디렉토리 정보
• kobj_remove_work
  • 슬랩 캐시 삭제 시 워크를 통해 연동되어 sysfs에 생성한 슬랩 캐시명의 디렉토리를 제거한다.
• memcg_param
  • 메모리 cgroup에서 사용하는 파라메터
• max_attr_size
  • 속성이 저장될 최대 사이즈
• *memcg_kset
  • 메모리 cgroup에서 사용하는 kset
• random
  • CONFIG_SLAB_FREELIST_HARDENED 커널 옵션 사용 시 보안을 목적으로 FP(Free Pointer)를 encaptualization 하여 알아볼 수 없게 숨기기 위한 랜덤 값이다.
• remote_node_defrag_ratio
  • 할당할 slub object가 로컬노드의 partial 리스트에서 부족한 경우 리모트 노드의 partail 리스트에서 시도할 확률
  • 0~1023 (100=로컬노드의 partial 리스트에서 slub object를 할당할 수 없을 때 약 10%의 확률로 리모트 노드에서 시도)
• *random_seq
  • CONFIG_SLAB_FREELIST_RANDOM 커널 옵션을 사용 시 heap 오버플로우 침입에 대한 보안 강화를 목적으로 free object들의 순서를 섞기 위한 배열이 할당된다.
• kasan_info
  • CONFIG_KASAN 커널 옵션을 사용 시 KASAN(Kernel Address SANitizer) 런타임 디버거를 사용할 수 있다.
• useroffset
  • 유저 copy 영역 offset
• usersize
  • 유저 copy 영역 사이즈
• *node
  • 노드별 partial 리스트를 관리하는 kmem_cache_node 배열 포인터

 

kmem_cache_cpu 구조체 (slub)

include/linux/slub_def.h

struct kmem_cache_cpu {
        void **freelist;        /* Pointer to next available object */
        unsigned long tid;      /* Globally unique transaction id */
        struct page *page;      /* The slab from which we are allocating */
#ifdef CONFIG_SLUB_CPU_PARTIAL
        struct page *partial;   /* Partially allocated frozen slabs */
#endif
#ifdef CONFIG_SLUB_STATS
        unsigned stat[NR_SLUB_STAT_ITEMS];
#endif
};

per-cpu로 관리되는 슬랩 캐시

•  **freelist
  • 아래 page 멤버 중 할당 가능한 free object를 가리키는 포인터
• tid
  • 글로벌하게 유니크한 트랜잭션 id
• *page
  • 할당/해제에 사용 중인 슬랩 캐시 페이지
• *partial
  • 일부 object가 사용(in-use)된 frozen 슬랩 페이지 리스트
• stat
  • 슬랩 캐시 통계

 

kmem_cache_node 구조체 (slab, slub)

mm/slab.h

#ifndef CONFIG_SLOB
/*      
 * The slab lists for all objects.
 */     

struct kmem_cache_node {
        spinlock_t list_lock;
#ifdef CONFIG_SLUB
        unsigned long nr_partial;
        struct list_head partial;
#ifdef CONFIG_SLUB_DEBUG
        atomic_long_t nr_slabs;
        atomic_long_t total_objects;
        struct list_head full;
#endif
#endif
};

per-node로 관리하는 슬랩 캐시

•  list_lock
  • spin lock에서 사용
• nr_partial
  • 유지할 partial 리스트의 수
• partial
  • 해당 노드에서 partial된 슬랩 페이지 리스트
  • 단 slab과 다르게 slub은 특별히 partial 상태를 구별하지 않는다.
• nr_slabs
  • 디버그용 슬랩 페이지 수
• total_objects
  • 디버그용 슬랩 object의 총 갯수
• full
  • 디버그용 다 사용된(in-use) slub 페이지 리스트

 

page 구조체에서 slub 용도로 사용되는 멤버

include/linux/mm_types.h

struct page {
...
                struct {        /* slab, slob and slub */
                        union {
                                struct list_head slab_list;     /* uses lru */
                                struct {        /* Partial pages */
                                        struct page *next;
#ifdef CONFIG_64BIT
                                        int pages;      /* Nr of pages left */
                                        int pobjects;   /* Approximate count */
#else
                                        short int pages;
                                        short int pobjects;
#endif
                                };
                        };
                        struct kmem_cache *slab_cache; /* not slob */
                        /* Double-word boundary */
                        void *freelist;         /* first free object */
                        union {
                                void *s_mem;    /* slab: first object */
                                unsigned long counters;         /* SLUB */
                                struct {                        /* SLUB */
                                        unsigned inuse:16;
                                        unsigned objects:15;
                                        unsigned frozen:1;
                                };
                        };
                };
...

슬랩 페이지에 사용되는 페이지 디스크립터이다.

• slab_list
  • per-cpu 캐시 또는 per-node의 partial 리스트에 연결 시 사용될 노드
• *next
  • 다음 partial 페이지를 가리킨다.
• pages
  • 남은 partial 페이지 수
• pobjects
  • 대략 남은 object 수
• *slab_cache
  • 슬랩 캐시
• *freelist
  • 첫 번째 free object를 가리키는 포인터
• counters
  • 다음 정보를 담고 있다.
    • inuse:16
      • 사용중인 object의 총 갯수
      • counters[15:0]
    • objects:15
      • object의 총 갯수
      • counters[30:16]
    • frozen:1
      • frozen 여부를 나타낸다.
      • counters[31]

 

슬랩 페이지의 frozen 상태

• 슬랩 페이지가 특정 cpu가 전용으로 사용할 수 있는 상태가 frozen 상태이다.
  • c->page에 연결된 슬랩 페이지이거나, c->partial에 연결된 슬랩 페이지들이 frozen 상태에 있다.
• 노드별 partial 리스트 관리에 있는 슬랩 페이지들은 un-frozen 상태이다.
  • node[]->partial에 연결된 슬랩 페이지들이 un-frozen 상태에 있다.
• 전담 cpu는 frozen된 페이지가 가진 freelist에서 슬랩 object 탐색과 할당/해제가 가능하다.
• 전담 cpu가 아닌 다른 cpu는 freelist에서 슬랩 object의 탐색 및 할당이 불가능하고 오직 슬랩 object의 할당 해제만 허용된다.

 

kmem_cache_order_objects 구조체

include/linux/slub_def.h

/*
 * Word size structure that can be atomically updated or read and that
 * contains both the order and the number of objects that a slab of the
 * given order would contain.
 */

struct kmem_cache_order_objects {
        unsigned long x;
};

• x[15:0]
  • slub 페이지를 만들 때 사용할 최대 object 수
• x[31:16]
  • slub 페이지를 만들 때 사용할 order

 

참고

• Slab Memory Allocator -1- (구조) | 문c – 현재 글
• Slab Memory Allocator -2- (캐시 초기화) | 문c
• Slub Memory Allocator -3- (캐시 생성) | 문c
• Slub Memory Allocator -4- (Order 계산) | 문c
• Slub Memory Allocator -5- (Slub 할당) | 문c
• Slub Memory Allocator -6- (Object 할당) | 문c
• Slub Memory Allocator -7- (Object 해제) | 문c
• Slub Memory Allocator -8- (Drain/Flash 캐시) | 문c
• Slub Memory Allocator -9- (캐시 Shrink) | 문c
• Slub Memory Allocator -10- (Slub 해제) | 문c
• Slub Memory Allocator -11- (캐시 삭제) | 문c
• Slub Memory Allocator -12- (Slub 디버깅) | 문c
• Slub Memory Allocator -13- (slabinfo) | 문c
• Kmalloc | 문c

 

• Slab allocators in the Linux Kernel: SLAB, SLOB, SLUB (Rev. 2014) | Christoph Lameter – pdf 다운로드
• A Heap of Trouble (Exploiting the Linux Kernel SLOB Allocator) | Dan Rosenberg – pdf 다운로드
• How does the SLUB allocator work | 김준수 – pdf 다운로드
• [Linux] 동적 메모리 할당자 : slab, slub, slob | F/OSS
• The SLUB Allocator | LWN.net
• Kernel dynamic memory analysis | elinux.org
• SLUB: Support for statistics to help analyze allocator behavior | LWN.net
• Cramming more into struct page | LWN.net
• debug with Linux slub allocator | thinkiii
• slub_debug: Detect Kernel heap memory corruption | TechVolve
• Short users guide for SLUB (2015, Documentation/vm/slub.txt)| Kernel.org