kmalloc()

Kmalloc()

 

다음 그림은 kmalloc() 함수가 사이즈에 따라 호출되는 함수들을 보여준다. 할당 요청 사이즈가 클 때에는 페이지 할당자에 요구하고, 작을 때에는 slab(slub) 캐시에 요청한다.

kmalloc-1b

 

kmalloc()에서 사용하는 GFP 플래그

  • GFP_USER
    • user의 요청에 의한 메모리 할당이며 sleep될 수 있다.
  • GFP_KERNEL
    • kernel의 요청에 의한 메모리 할당이며 sleep될 수 있다.
  • GFP_ATOMIC
    • sleep되면 안될 때 사용되며 인터럽트 핸들러 등에서 사용한다.
  • GFP_HIGHUSER
    • highmem(high memory)에 우선 페이지 할당을 한다.
  • GFP_NOIO
    • 메모리 할당을 하는 동안 어떠한 I/O 처리를 수행하지 않는다.
  • GFP_NOFS
    • 메모리 할당을 하는 동안 어떠한 File System calls을 수행하지 않는다.
  • GFP_NOWAIT
    • 메모리 할당을 하는 동안 sleep을 허용하지 않을 떄 사용한다.
  • __GFP_THISNODE
    • 지정된 노드에서만 할당을 허용한다.
  • GFP_DMA – Allocation suitable for DMA.
    • DMA zone에 메모리 할당 요청한다.
  • __GFP_COLD
    • 메모리 파편화에 영향을 덜 주도록 hot 페이지 대신 cold 페이지에서 할당받도록 요청한다.
  • __GFP_HIGH
    • 높은 우선 순위에서 처리되도록 요청할 때 사용한다.
  • __GFP_NOFAIL
    • 실패를 허용하지 않고, 메모리 할당 요청에 대해 성공할 때까지 처리하도록 요청할 때 사용한다.
  • __GFP_NORETRY
    • 메모리 할당 요청에 대해 실패 시 재시도 하지 않는다.
  • __GFP_NOWARN
    • 메모리 할당이 실패할 때 어떠한 경고도 처리하지 않도록 한다.
  • __GFP_REPEAT
    • 메모리 할당이 처음 실패하는 경우 한 번 더 시도하도록 요청할 때 사용한다.

 

kmalloc()

include/mm/slab.h

/**
 * kmalloc - allocate memory
 * @size: how many bytes of memory are required.
 * @flags: the type of memory to allocate.
 *
 * kmalloc is the normal method of allocating memory
 * for objects smaller than page size in the kernel.
 *
 * The @flags argument may be one of:
 *
 * %GFP_USER - Allocate memory on behalf of user.  May sleep.
 *
 * %GFP_KERNEL - Allocate normal kernel ram.  May sleep.
 *
 * %GFP_ATOMIC - Allocation will not sleep.  May use emergency pools.
 *   For example, use this inside interrupt handlers.
 *
 * %GFP_HIGHUSER - Allocate pages from high memory.
 *
 * %GFP_NOIO - Do not do any I/O at all while trying to get memory.
 *
 * %GFP_NOFS - Do not make any fs calls while trying to get memory.
 *
 * %GFP_NOWAIT - Allocation will not sleep.
 *
 * %__GFP_THISNODE - Allocate node-local memory only.
 *
 * %GFP_DMA - Allocation suitable for DMA.
 *   Should only be used for kmalloc() caches. Otherwise, use a
 *   slab created with SLAB_DMA.
 *
 * Also it is possible to set different flags by OR'ing
 * in one or more of the following additional @flags:
 *
 * %__GFP_COLD - Request cache-cold pages instead of
 *   trying to return cache-warm pages.
 *
 * %__GFP_HIGH - This allocation has high priority and may use emergency pools.
 *
 * %__GFP_NOFAIL - Indicate that this allocation is in no way allowed to fail
 *   (think twice before using).
 *
 * %__GFP_NORETRY - If memory is not immediately available,
 *   then give up at once.
 *
 * %__GFP_NOWARN - If allocation fails, don't issue any warnings.
 *
 * %__GFP_REPEAT - If allocation fails initially, try once more before failing.
 *
 * There are other flags available as well, but these are not intended
 * for general use, and so are not documented here. For a full list of
 * potential flags, always refer to linux/gfp.h.
 */

 

static __always_inline void *kmalloc(size_t size, gfp_t flags)
{
        if (__builtin_constant_p(size)) {
                if (size > KMALLOC_MAX_CACHE_SIZE)
                        return kmalloc_large(size, flags);
#ifndef CONFIG_SLOB
                if (!(flags & GFP_DMA)) {
                        int index = kmalloc_index(size);

                        if (!index)
                                return ZERO_SIZE_PTR;

                        return kmem_cache_alloc_trace(kmalloc_caches[index],
                                        flags, size);
                }
#endif
        }
        return __kmalloc(size, flags);
}

커널로부터 메모리 할당 요청에 대해 할당 요청 사이즈가 크거나 상수가 아닌 경우 버디 시스템을 사용하는 페이지 할당자에 요청하고, 그렇지 않은 경우에는 slub을 사용하는 kmalloc kmem 캐시에 요청한다.

  • 요청 사이즈가 상수이면서 KMALLOC_MAX_CACHE_SIZE를 초과하는 경우 직접 버디 시스템을 사용하는 페이지 할당자로 요청한다.
    • KMALLOC_MAX_CACHE_SIZE
      • slub을 사용하는 경우 2 개 페이지 수로 4K 페이지를 사용하는 경우 8K이다.
  • 요청 사이즈가 상수이고 GFP_DMA 요청이 아닌 경우 사이즈에 따른 kmalloc kmem 캐시를 선택하여 slub object를 할당 받는다.
    • size 값으로 kmalloc_caches[] 배열의 인덱스를 알아온다.
  • size에 변수를 사용하였거나 GFP DMA 플래그를 사용한 경우 kmalloc을 사용하는 kmem 캐시를 선택하여 slub object를 할당 받는다.

 

kmalloc_large()

include/linux/slab.h

static __always_inline void *kmalloc_large(size_t size, gfp_t flags)
{
        unsigned int order = get_order(size);
        return kmalloc_order_trace(size, flags, order);
}

size에 필요한 order를 결정한 후 버디 시스템을 사용하는 페이지 할당자로부터 페이지를 할당 받는다.

 

kmalloc_order_trace()

mm/slab_common.c

#ifdef CONFIG_TRACING
void *kmalloc_order_trace(size_t size, gfp_t flags, unsigned int order)
{
        void *ret = kmalloc_order(size, flags, order);
        trace_kmalloc(_RET_IP_, ret, size, PAGE_SIZE << order, flags);
        return ret;
}
EXPORT_SYMBOL(kmalloc_order_trace);
#endif

버디 시스템을 사용하는 페이지 할당자로부터 order 만큼의 페이지를 할당 받는다.

 

kmalloc_order()

mm/slab_common.c

/*
 * To avoid unnecessary overhead, we pass through large allocation requests
 * directly to the page allocator. We use __GFP_COMP, because we will need to
 * know the allocation order to free the pages properly in kfree.
 */
void *kmalloc_order(size_t size, gfp_t flags, unsigned int order)
{
        void *ret;
        struct page *page;

        flags |= __GFP_COMP;
        page = alloc_kmem_pages(flags, order);
        ret = page ? page_address(page) : NULL;
        kmemleak_alloc(ret, size, 1, flags);
        kasan_kmalloc_large(ret, size);
        return ret;
}
EXPORT_SYMBOL(kmalloc_order);

큰 페이지에 대한 할당 요청이므로 __GFP_COMP 플래그를 추가하고 버디 시스템을 사용하는 페이지 할당자로부터 order 만큼의 페이지를 할당 받는다.

 

alloc_kmem_pages()

mm/page_alloc.c

/*
 * alloc_kmem_pages charges newly allocated pages to the kmem resource counter
 * of the current memory cgroup.
 *
 * It should be used when the caller would like to use kmalloc, but since the
 * allocation is large, it has to fall back to the page allocator.
 */
struct page *alloc_kmem_pages(gfp_t gfp_mask, unsigned int order) 
{
        struct page *page;
        struct mem_cgroup *memcg = NULL;

        if (!memcg_kmem_newpage_charge(gfp_mask, &memcg, order))
                return NULL;
        page = alloc_pages(gfp_mask, order);
        memcg_kmem_commit_charge(page, memcg, order);
        return page;
}

memcg를 통해 허용된 사이즈 이내인 경우 버디 시스템을 사용하는 페이지 할당자로부터 order 만큼의 페이지 할당을 받는다. 할당 후 memcg에 할당 받은 order를 보고한다.

 

kmalloc_index()

include/linux/slab.h

#ifndef CONFIG_SLOB
/*
 * Figure out which kmalloc slab an allocation of a certain size
 * belongs to.
 * 0 = zero alloc
 * 1 =  65 .. 96 bytes
 * 2 = 120 .. 192 bytes
 * n = 2^(n-1) .. 2^n -1
 */
static __always_inline int kmalloc_index(size_t size)
{
        if (!size)
                return 0;

        if (size <= KMALLOC_MIN_SIZE)
                return KMALLOC_SHIFT_LOW;

        if (KMALLOC_MIN_SIZE <= 32 && size > 64 && size <= 96)
                return 1;
        if (KMALLOC_MIN_SIZE <= 64 && size > 128 && size <= 192)
                return 2;
        if (size <=          8) return 3;
        if (size <=         16) return 4;
        if (size <=         32) return 5;
        if (size <=         64) return 6;
        if (size <=        128) return 7;
        if (size <=        256) return 8;
        if (size <=        512) return 9;
        if (size <=       1024) return 10;
        if (size <=   2 * 1024) return 11;
        if (size <=   4 * 1024) return 12;
        if (size <=   8 * 1024) return 13;
        if (size <=  16 * 1024) return 14;
        if (size <=  32 * 1024) return 15;
        if (size <=  64 * 1024) return 16;
        if (size <= 128 * 1024) return 17;
        if (size <= 256 * 1024) return 18;
        if (size <= 512 * 1024) return 19;
        if (size <= 1024 * 1024) return 20;
        if (size <=  2 * 1024 * 1024) return 21;
        if (size <=  4 * 1024 * 1024) return 22;
        if (size <=  8 * 1024 * 1024) return 23;
        if (size <=  16 * 1024 * 1024) return 24;
        if (size <=  32 * 1024 * 1024) return 25;
        if (size <=  64 * 1024 * 1024) return 26;
        BUG();

        /* Will never be reached. Needed because the compiler may complain */
        return -1;
}
#endif /* !CONFIG_SLOB */ 

0~64M 이하의 요청 사이즈에 따른 index를 0~23 까지의 수로 반환한다. 64M를 초과하는 경우 에러로 -1을 반환한다.

  • 요청 사이즈에 따른 index 값
    • 0 = 할당 없음 (zero alloc)
    • 1 = 65 .. 96 bytes
    • 2 = 120 .. 192 bytes
    • n = 2^(n-1) .. 2^n -1
      • 3 = 1 .. 8
      • 4 = 9 .. 16
      • 5 = 17 .. 32
      • 6 = 33 .. 64
      • 26 = 32M-1 .. 64M
    • 단, size가 1~KMALLOC_MIN_SIZE인 경우 KMALLOC_SHIFT_LOW를 반환한다.
      • rpi2 예) KMALLOC_MIN_SIZE=64, KMALLOC_SHIFT_LOW=6
      • arm64예) KMALLOC_MIN_SIZE=128, KMALLOC_SHIFT_LOW=7

 

kmem_cache_alloc_node_trace()

include/linux/slab.h

#ifdef CONFIG_TRACING
void *kmem_cache_alloc_trace(struct kmem_cache *s, gfp_t gfpflags, size_t size)
{
        void *ret = slab_alloc(s, gfpflags, _RET_IP_);
        trace_kmalloc(_RET_IP_, ret, size, s->size, gfpflags);
        kasan_kmalloc(s, ret, size);
        return ret;
}
EXPORT_SYMBOL(kmem_cache_alloc_trace);
#endif

지정된 slub 캐시에서 slub object를 할당 받는다.

 

__kmalloc()

mm/slub.c

void *__kmalloc(size_t size, gfp_t flags)
{
        struct kmem_cache *s;
        void *ret;

        if (unlikely(size > KMALLOC_MAX_CACHE_SIZE))
                return kmalloc_large(size, flags);

        s = kmalloc_slab(size, flags);

        if (unlikely(ZERO_OR_NULL_PTR(s)))
                return s;

        ret = slab_alloc(s, flags, _RET_IP_);

        trace_kmalloc(_RET_IP_, ret, size, s->size, flags);

        kasan_kmalloc(s, ret, size);

        return ret;
}
EXPORT_SYMBOL(__kmalloc);

size 값이 변수이거나 GFP_DMA 플래그 옵션을 사용하여 메모리 할당을 요청한 경우 다음과 같이 처리한다.

  • size가 KMALLOC_MAX_CACHE_SIZE를 초과하는 경우 kmalloc_large() 함수를 통해 버디 시스템을 사용한 페이지 할당자로 부터 페이지를 할당 받는다.
  • size에 따른 적절한 인덱스를 결정하고 미리 만들어 둔 kmalloc_caches[인덱스]  캐시에서 slub object를 할당 받는다.
    • 적절한 인덱스
      • size가 1~192인 경우 size_index[]를 사용한다.
      • size가 93~KMALLOC_MAX_SIZE인 경우 필요 비트 수를 산출한다.

 

kmalloc_slab()

mm/slab_common.c

/*
 * Find the kmem_cache structure that serves a given size of
 * allocation
 */
struct kmem_cache *kmalloc_slab(size_t size, gfp_t flags)
{
        int index;
        
        if (unlikely(size > KMALLOC_MAX_SIZE)) {
                WARN_ON_ONCE(!(flags & __GFP_NOWARN));
                return NULL;
        }
 
        if (size <= 192) {
                if (!size)
                        return ZERO_SIZE_PTR;

                index = size_index[size_index_elem(size)];
        } else
                index = fls(size - 1);

#ifdef CONFIG_ZONE_DMA
        if (unlikely((flags & GFP_DMA)))
                return kmalloc_dma_caches[index];

#endif
        return kmalloc_caches[index];
}

size 값으로 적절한 kmalloc_caches[] 배열에 사용할 인덱스 값을 산출한다.

  • size가 KMALLOC_MAX_SIZE를 초과하는 경우 null을 반환한다.
    • arm, arm64, 4k 페이지 slub 예) =8M
  • size가 1 ~ 192인 경우 이미 만들어진 size_index[] 테이블을 활용한다.
  • size가 193 ~ KMALLOC_MAX_SIZE인 경우 필요 비트 수를 산출하여 반환한다.
    • 193 ~ 256 → 8
    • 257 ~ 512 → 9
    • 4M+1 ~ 8M → 23

 

size_index_elem()

mm/slab_common.c

static inline int size_index_elem(size_t bytes)
{
        return (bytes - 1) / 8;
}

size_index[] 테이블은 인덱스 당 8바이트 범위를 사용한다. 따라서 요청 bytes-1을 8로 나눈 몫을 반환한다.

  • 1 ~ 8 → 0
  • 9 ~ 16 → 1
  • 17 ~ 24 → 2
  • 25 ~ 32 → 3
  • 33 ~ 40 → 4
  • 41 ~ 48 → 5

 

참고

답글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다.