Linux kernel memory management - 2

Slab Layer

1)    범용 자료구조의 cache layer

2)    빈번한 할당과 해제 작업이 용이하게 개발자들은 해제 리스트(free list)를 많이 사용

3)    새로 memory를 할당하고 그 memory에 자료구조를 준비하는 대신 해제 list에 들어 있는자료구조를 바로 사용

   

object cache 기법

 

1)    Kernel 내에서 free list를 사용하는데 가장 큰 문제점은 전체적인 제어 방법이 없다는 것.

2)    전체적인 system memory 부족 시 해제 list의 cache 크기를 줄여서memory를 확보할 방법이 없음

3)    커널은 어떤 해제 list를 선택 해야 할 지알 수 없음

   

그래서

1)    이런 부분을 처리하는 layer로서 slab layer를 만듦

2)    slab layer는 범용 자료구조 cache layer임

   

slab layer의 설계 원칙

1)    자주 사용하는 자료구조는 할당 및 해제가 빈번하므로cache함

2)    빈번한 할당/해제 작업은 메모리 단편화를 유발.

이를 막기 위해 free list는 연속된순서대로 정리함

3)    free list를 사용하여 할당/해제 성능 향상

4)    할당자가 객체의 크기, page의 크기, 전체 cache 크기 등의 정보를 알아서 정교한 control 수행

5)    일부 cache가 processor 단위로 동작 가능

6)    NUMA 지원 할당자의 경우 memory를 요청한 node에 있는 memory를 할당해 줄 수 있음

7)    여러 객체가 같은 cache에 섞여 들어가지않게, 저장되는 객체에 표시할 수 있어야 함

 

슬랩 계층 설계

    slablayer는 각 객체를 유형별로 객체를 저장하는 cache에 분류

    객체별로 하나의 cache가 존재

   

    process 기술자를위한 cache(task_struct용) 하나

    inode용하나 이런 식

   

    kmallocinterface는 여러 개의 범용 cache를 사용하는slab layer위에 구현됨

        ->즉 kmalloc도 slab layer를 사용

   

    각 slab에는 cache 할 자료구조에 해당하는 객체가 여러 개 들어감

    slab의상태는 모두 사용, 부분 사용, 미사용 3가지 중 하나

   

        모두 사용 -> 해제된객체가 없음

        미사용    -> 할당된 객체가 없음

   

    커널에서새로운 객체를 요청하면, 부분 사용 상태인 slab이 있는경우 이를 사용

    없으면, 미사용 사용

    미사용도없으면, 새로운 slab을 생성

   

slab 사용 이유

        ex.

       memory 상에서 disk inode를 나타내는 inode struct의 경우

        이구조체는 빈번하게 할당 및 해제되므로, slab 할당자를 이용해 관리하는 것이 합리적

       

       struct inode 구조체는 inode_cachep cache를이용해 할당.

 

+-------+            +------+              +--------+        | cache | -+----> | slab  |---+---> | object |        +-------+   |        +------+     |       +--------+                        |                          |                        |                          +-----> ...                        |     +------+                        +-->| slab  | -----------> ....                              +------+

 

       slab에 객체가 없다면 이는 미사용 slab

    각 cache 항목은 kmem_cache 구조체를사용해서 표현

    구조체안에 slabs_full, slabs_partial, slabs_empty 세 list가 저장된 kmem_list3 구조체가 존재

   mm/slab.c 에 정의 되어 있음

   

kmem_cache      +- slabs_full          <-- slab 객체 list      +- slabs_partial      +- slabs_empty

 

struct slab {         struct list_head list;      /* full, partial, or empty list */         unsigned long colouroff;    /* offset for the slab coloring */         void *s_mem;                  /* first object in the slab */         unsigned int inuse;          /* allocated objects in the slab */         kmem_bufctl_t free;          /* first free object, if any */ };

 

   slab할당자는 __get_free_pages() 저수준 커널 페이지 할당 함수를 사용해 새로운 slab을 만듦

 

static void *kmem_getpages(struct kmem_cache *cachep, gfp_t flags, int nodeid) {         ...         addr = (void*)__get_free_pages(flags, cachep->gfporder);         ...         page = virt_to_page(addr);         .... or page = alloc_pages_node(nodeid, flags, cachep->gfporder);         addr = page_address(page);                ...                 while (i--) {             SetPageSlab(page);             page++;         }         return addr; }

 

    2의거듭 제곱 형태인 할당 크기 값은 cachep->gfporder에 저장됨

    할당자가 NUMA를 지원해야 하므로 생각보다 코드가 복잡해 보임

    nodeid가 -1 이 아닌 경우, 할당자는 할당을 요청한 장비와 같은 노드의 메모리할당을 시도

 

NUMA 지원 간단 삭제 코드

static inline void * kmem_getpages(struct kmem_cache *cachep, gfp_t flags) {             void *addr;             flags |= cachep->gfpflags;             addr = (void*) __get_free_pages(flags, cachep->gfporder);             return addr; }

 

    할당한 memory는 kmem_freepages()함수를 이용해 해제됨

    물론 slab 계층은 페이지 할당 및 해제를 최대한 자제함

    slab 계층은지정한 cache에 대해 부분 사용 또는 미사용 slab이없는 경우에만

à page 할당 함수를 호출

 

kmem_free의 호출 경우

        1.system 유휴 메모리를 확보하려는 경우

        2.cache가 명시적으로 삭제되는 경우

 

Slab Allocator Interface

struct kmem_cache * kmem_cache_create(const char *name,         size_t size,         size_t align,         unsigned long flags,         void (*ctor)(void *));

 

    위 함수를사용해서 새로운 cache를 생성할 수 있음

 

flags인자

       SLAB_HWCACHE_ALIGN : 각 객체들을 cache line에 맞춰정렬

            false-sharing 현상을 막음

            대신 memory 사용량이 증가

            성능이 중요한 경우 사용

 

       SLAB_POISON: 미리 정해진 값(a5a5a5a5)으로 slab을 재움

            à 초기화하지 않고 사용되는 memory 버그를 잡기 위함

       SLAB_RED_ZONE: 버퍼 경계 넘침 현상을 감지할 수 있게 slab 계층은할당된 memory

양측에 적색지대를 끼워 넣음

       SLAB_PANIC: memory 할당이 fail 시 slab 계층은 치명적 오류(panic)을 발생

(일찍 죽이기 위해서 사용)

       SLAB_CACHE_DMA : slab 계층은 DMA 처리 가능한 memory에 slab을 사용

 

 

   마지막 인자인 ctor는 cache 생성자임

   위 함수는 휴면 가능함 (즉interrupt context에서 사용 불가)

 

   int kmem_cache_destroy(struct kmem_cache *cachep)

       cache 제거

 

destroy 조건

       . cache의 모든 slab이 비어 있어야 함

       . kmem_cache_destroy() 함수를 호출하는 동안(호출 이후에도)

cache 접근 경우가 있어서는 안됨

         함수를 호출하는 쪽에서 동기화를 보장해야 함

 

Allocating from the Cache

   

    void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags)

   

        cache내부의 객체를 얻음

        지정한캐시에 들어 있는 객체의 포인터를 반환

   

    voidkmem_cache_free(struct kmem_cache *cachep, void *objp)

        객체를해제하고 slab에 반환

 

Example of Using the Slab Allocator

   task_struct_cachep = kmem_cache_create(“task_struct”,

                        sizeof(structtask_struct),

                        ARCH_MIN_TASKALIGN,

                        SLAB_PANIC |SLAB_NOTRACK,

                        NULL);

       

       task_struct 용 cache의 사용

   

       생성된 객체의 slab 내부 offset 값은 ARCH_MIN_TASKALIGN byte임

       이 전처리 macro 값은 arch.에좌우

       L1 cache 바이트 크기인 L1_CACHE_BYTES 값으로로 정해짐

 

       실패하면 panic() 호출

 

   fork 호출 시 do_fork 호출 여기서dup_task_struct()가 불리는데 여기서 cache 사용

   

   

       struct task_struct *tsk;

       tsk = kmem_cache_alloc(task_struct_cachep, GFP_KERNEL);

       if (!tsk)

            return NULL;

       

       

   task 종료 후 대기중인 child process가 없다면, process descriptor가 해제되어

   task_struct_cachep에 반환됨

   free_task_struct에서

       kmem_cache_free(task_struct_cachep, tsk); 를 호출

 

   process descriptor는 kernel의 핵심 중 하나이기에 task_struct_cachep는 절대로 비 해제됨

   명시적 해제를 만약 한다면 다음과 같이 사용

 

err = kmem_cache_destroy(task_struct_cachep); if (err)     /* error destroying cache */

 

   같은 형의 객체를 빈번하게 많이 생성해야 한다면, slab cache 사용을고려

   절대 자체적인 free list를 별도로 구현하지 않도록 함

 

스택에 정적으로 할당

    사용자공간은 동적으로 크기가 확장되는 커다란 stack을 사용

    커널은고정된 작은 크기의 stack 사용   

    전통적으로 process별로 두 page의 커널 stack 사용

 

Single-Page Kernel Stacks

   

    각 process의 전체 연쇄 호출 정보가 커널 스택에 들어 있어야 함

    그런데전통적으로 interrupt 처리 시 Interrupt handler도 process의 kernel stack을 사용

    커널스택에는 이 정보도 들어갈 수 있어야 함   

        ->stack 사용 량이 많아짐

 

    stack을한 page로 만들면, 더 이상 interrupt handler는 들어갈 수 없음

    이 문제를바로잡기 위해 kernel 개발자들은 interrupt stack이라는새로운 기능을 구현

   

    interruptstack은 interrupt handler가 사용하는processor 별 존재하는 1 page크기의stack임   

    -->kernel stack은 compile 시 옵션에 따라 하나 혹은 두 개의 page로 구성

 

공정하게 stack 사용

   큰 배열이나 구조체 등을 선언하는 커다란 stack 정적 할당 작업은 위험함

   kernel에는 stack 관리 기능이 없어서 stack 경계 넘침 현상이 발생하면, 초과된 분량의 data는 stack의 끝의 경계 너머에 뭐가 있던지 넘쳐 흐름.

 

상위 memory 연결

   상위 memory에 있는 page는고정된 kernel 주소 공간 값이 없을 수 있음

   즉, __GFP_HIGHMEM flag를 지정하고 alloc_pages() 함수를 호출해서 얻은 page에는 논리적주소가 없을 수 있음

   

   x86 processor가 4GB 영역의(PAE  기능의 존재 시64GB) 물리적 주소를 다룰 수 있지만,

   x86 architecture에서는 896MB 경계 너머의 모든 물리적 메모리는 상위 메모리로 간주하고, 이영역의 page는 커널 주소 공간에 자동으로 연결되지 않고 고정된 값이 할당되지도 않음

   

   x86에서 상위 memory의 page는 3GB에서 4GB사이 영역에map.

 

 

고정 연결

   주어진 page 구조체를 커널 주소 공간에 연결

   

   <linux/highmem.h>:

   void *kmap(struct page *page)

   

   페이지가 상위 memory에 있으면, 고정연결을 만들고, 그 주소를 반환

   kmap은 휴면 가능

 

 

임시 연결

   context가 휴면 불가능한 상황을 위해

   kernel은 temporary mapping기능을 제공

   

   void *kmap_atomic(struct page *page, enum km_type type)

   

   type 인자에는 임시 연결의 목적을 설정

enum km_type {             KM_BOUNCE_READ,             KM_SKB_SUNRPC_DATA,             KM_SKB_DATA_SOFTIRQ,             KM_USER0,             KM_USER1,             KM_BIO_SRC_IRQ,             KM_BIO_DST_IRQ,             KM_PTE0,             KM_PTE1,             KM_PTE2,             KM_IRQ0,             KM_IRQ1,             KM_SOFTIRQ0,             KM_SOFTIRQ1,             KM_SYNC_ICACHE,             KM_SYNC_DCACHE,             KM_UML_USERCOPY,             KM_IRQ_PTE,             KM_NMI,             KM_NMI_PTE,             KM_TYPE_NR };

 

   연결 해제의 경우   

   void kunmap_atomic(void *kvaddr, enum km_type type)

   

CPU별 할당

  CPU별 data를 사용하는 경우

  보통 CPU별 data는 배열에저장

  

  배열의 각 항목이 system의 각processor에 대응되는 방식

  

   1. 선언

       unsigned long my_percpu[NR_CPUS];

 

   2. 접근

int cpu;         cpu = get_cpu();  // get current processor and disable kernel preemption my_percpu[cpu]++;   /* ... or whatever */         printk(“my_percpu on cpu=%d is %lu\n”, cpu, my_percpu[cpu]); put_cpu();              /* enable kernel preemption */

 

   현재 processor에서만 사용하는data이므로 lock이 필요하지 않음

   CPU별 data를 다룰 때 주의는 커널 선점 뿐

   커널 선점이 일으킬 수 있는 문제

       . 코드 선점 후 다른 processor에서re-schedule 시 cpu 변수가 엉뚱한 processor를가리켜서 cpu 값이 무의미 --> processor 선점문제

       . 다른 작업이 현재 코드 선점 시, my_percpu 값에 동시 접근 하기에경쟁 조건 발생 --> process 선점 문제

 

   하지만, get_cpu() 함수를 호출하면 현재 processor 번호를 반환하면서 커널 선점도 비활성화 시키기에

   이런 걱정은 불필요!!

   

   이에 대응하는 put_cpu를 호출하면 커널 선점이 활성화

   

   smp_processor_id()를 호출하면 현재 processor의 번호를얻고, 커널 선점이 비활성화 되지 않음에 주의함!

 

 

새로운 percpu interface

   CPU 별 data를 생성하고 관리하는percpu가 2.6에 도입

 

   <linux/percpu.h> 에 함수 선언

   mm/slab.c, <asm/percpu.h>에 실제 구현 존재

 

 

컴파일 시점의 CPU별 data

 

   CPU별 data를 선언하는 방법

   

       DEFINE_PER_CPU(type, name);

 

   다른 곳에서 사용 하는 경우

   

       DECLARE_PER_CPU(type, name);

 

   get_cpu_var(), put_cpu_var()를 사용

   

   get_cpu_var(name)++;        /*increment name on this processor */  선점비활성화

   put_cpu_var(name);          /* done; enable kernel preemption */    선점 활성화

 

   

   다른 processor의 값 얻기

   

   per_cpu(name, cpu)++;   /*increment name on the given processor */

 

 

   per_cpu()를 사용하는 방법은 커널 선점을 비활성화시키지도 않고 어떤 종류의 잠금 장치도 사용하지 않으므로 조심

   해당 data를 현재 processor에서만조작한다는 것이 보장된 경우에만 유효

 

실행 시점의 CPU별 data

 

   CPU별 data를 생성시 kmalloc과유사한 할당자가 존재

   

       void *alloc_percpu(type); /* a macro */

       void *__alloc_percpu(size_t size, size_t align);

       void free_percpu(const void *);

 

   allco_percpu() macro

       지정한 형식의 객체를 system의 각processor별로 생성

       __alloc_percpu()함수의 wrapper임

   

   ex.

       struct rabid_cheetah = alloc_percpu(struct rabid_cheetah);

       

       이 코드는 다음 코드와 같음

       

            struct rabid_cheetah =__alloc_percpu(sizeof (struct rabid_cheetah),

                                __alignof__(struct rabid_cheetah));

 

   __alignof__ 지시자는 지정한 형이나 lvalue를 정렬 상태로 만들기위해 필요한 byte 값

   (정렬 상태가 필수가 아닌 별난 architecture인 경우 추천하는 byte 값)을 찾아주는 gcc 기능

 

   x86의 경우 4를 리턴

   

        __alignof__ (unsigned long)

 

   lvalue를 지정한 경우에는 해당 lvaleu가 정렬 상태가 되기 위해 필요한최대 값을 반환

   lvaleu가 구조체 내부에 있다면, 구조체가 정렬 상태에 있어야 하는 조건으로인해, 구조체 외부의 같은 형

   변수보다 정렬 상태에 필요한 byte 값이 더 클 수 있음

   

   alloc_percpu() 함수나 __alloc_percpu()한수는 동적으로생성된 CPU별 data를 간접적으로 참조할 수 있는 포인터를반환

   커널은 간접 참조를 도와주는 함수를 제공

   

   get_cpu_var(ptr); /* return a void pointer to this processor’s copy ofptr */

   put_cpu_var(ptr); /* done; enable kernel preemption */

 

   ex.

       void *percpu_ptr;

       unsigned long *foo;

       percpu_ptr = alloc_percpu(unsigned long);

       if (!ptr)

       /* error allocating memory .. */

       foo = get_cpu_var(percpu_ptr);

       /* manipulate foo .. */

       put_cpu_var(percpu_ptr);

 

 

CPU별 data를사용하는이유

   CPU별 data를 사용하는 몇 가지 장점

   

   1. 락 사용 필요 없음

   2. cache invalidation을 줄여줌

       processor가 cache 동기화 상태를 유지하는 시도 횟수를 줄임

       processor가 다른 processor의cache에 저장된 data를 조작하고자 한다면,

processor는 자신의 cache를 비우거나 갱신해야 함

       cache invalidation가 지속적으로 일어나는 상황:

 cache 털림 현상(trashing the cache)라고 부름

       이는 system 성능을 무자비하게 떨어뜨림

   

   CPU별 data를 사용하는 데 필요한 안전 장치는 lock보다 휠씬 부담이 적은

à 커널 선점 비활성화!!

   

   CPU별 data는 interruptcontext와 process context모두에서 안전하게 사용할 수 있음

   하지만, CPU별 data에 접근하는동안에는 휴면 상태로 전환될 수 없다는 점을 주의 하자!

   (휴명 상태로 전환됐다가는 다른 processor로 가 버를 수 있음)

   

   커널 코드에서 CPU별 data를사용하기로 했다면, 새로운 interface의 사용을 고려

 

할당 방법 선택

 

    kmalloc

        물리적으로연속된 page가 필요한 경우

 

       GFP_ATOMIC

           interrupt handler나 휴면 상태로 전환할 수 없는 context에서사용

       

       GFP_KERNEL

            요청한 memory가 할당하기 위해 필요한 경우 휴면 상태 전환 가능

 

    alloc_pages()

        상위 memory (HIGH MEM ZONE 내 memory) 할당이 필요한경우

        논리적주소를 가리키는 포인터가 아닌 struct page 구조체를 반환       

        실제 pointer를 얻기 위해서는

kmap함수를 사용해 상위 memory를 커널의 논리 주소 공간에 연결

 

    vmalloc

        가상적으로연속된, 하지만 물리적으로는 연속되지 않을 수도 있는 커널 메모리를 할당

 

    slab cache

        큰자료구조를 다량으로 생성하고 해제하는 경우