idr_init_cache()

 

idr_init_cache()

lib/idr.c

void __init idr_init_cache(void)
{
        idr_layer_cache = kmem_cache_create("idr_layer_cache",
                                sizeof(struct idr_layer), 0, SLAB_PANIC, NULL);
}

idr_layer 구조체를 할당하기 위한 전용 slub 캐시를 생성한다.

  • 이후 idr_layer 구조체를 할당할 때마다 idr_layer_cache를 사용하여 할당받는다.

 

참고

IDR(integer ID 관리)

radix tree를 사용하여 정수 ID를 관리하고 이에 연결된 포인터 값을 반환한다. 다음은 리눅스 IDR의 특징이다.

  • ID 관리
    • Radix tree를 사용하여 레이어 단계 마다 256(0x100)배 단위로 ID를 관리할 수 있다.
      • 32 bit 시스템에서 사용하는 레이어의 수에 따라
        • 1 레이어: 0 ~ 0xff ID 관리
        • 2 레이어: 0 ~ 0xffff ID 관리
        • 3 레이어: 0 ~ 0xffffff ID 관리
        • 4 레이어: 0 ~ 0x7fffffff ID 관리
      • 64 bit 시스템에서사용하는 레이어의 수에 따라
        • 1 레이어: 0 ~ 0xff ID 관리
        • 2 레이어: 0 ~ 0xffff ID 관리
        • 3 레이어: 0 ~ 0xffffff ID 관리
        • 4 레이어: 0 ~ 0xffffffff ID 관리
        • 5 레이어: 0 ~ 0xff_ffffffff ID 관리
        • 6 레이어: 0 ~ 0xffff_ffffffff ID 관리
        • 7 레이어: 0 ~ 0xffffff_ffffffff ID 관리
        • 8 레이어: 0 ~ 0x7fffffff_ffffffff ID 관리
    • 큰 번호의 ID를 요구하는 경우 레이어 관리 단계가 커져 cost가 더 많이 소모된다.
  • IDR preload 버퍼
    • idr_layer 구조체 할당은 slub 캐시를 통해 전달되는데 이를 미리 몇 개를 할당받아 IDR 레이어가 횡 또는 종으로 확장될 때 빠르게 공급할 수 있도록 설계되었다.

 

다음 그림은 IDR이 레이어별로 관리되는 모습을 보여준다.

idr-2

 

다음 그림은 256~511까지의 ID와 1025의 ID가 할당되어 관리되는 모습을 보여준다.

idr-1

 

static IDR 선언 및 초기화

DEFINE_IDR()

include/linux/idr.h

#define DEFINE_IDR(name)        struct idr name = IDR_INIT(name)

주어진 이름으로 idr 구조체를 선언하고 초기화한다.

 

IDR_INIT()

include/linux/idr.h

#define IDR_INIT(name)                                                  \
{                                                                       \
        .lock                   = __SPIN_LOCK_UNLOCKED(name.lock),      \
}

주어진 이름의 idr 구조체를 초기화한다.

 

dynamic IDR 초기화

idr_init()

/**     
 * idr_init - initialize idr handle
 * @idp:        idr handle
 *
 * This function is use to set up the handle (@idp) that you will pass
 * to the rest of the functions.
 */
void idr_init(struct idr *idp)
{
        memset(idp, 0, sizeof(struct idr));
        spin_lock_init(&idp->lock);
}
EXPORT_SYMBOL(idr_init);

idr 구조체 멤버 변수를 모두 0으로 초기화하고 lock 멤버만 spinlock 초기화한다.

 

IDR 할당

  • 기존(old) 방법으로 ID를 할당하는 경우 다음 2개의 API를 연달아 사용했었다.
    • int idr_pre_get(struct idr *idp, gfp_t gfp_mask);
    • int idr_get_new(struct idr *idp, void *ptr, int *id);
  • 새로운(new) 방법으로 ID를 할당하는 경우 다음 3개의 API를 연달아 사용한다.

 

idr_preload()

lib/idr.c

/**
 * idr_preload - preload for idr_alloc()
 * @gfp_mask: allocation mask to use for preloading
 *
 * Preload per-cpu layer buffer for idr_alloc().  Can only be used from
 * process context and each idr_preload() invocation should be matched with
 * idr_preload_end().  Note that preemption is disabled while preloaded.
 *
 * The first idr_alloc() in the preloaded section can be treated as if it
 * were invoked with @gfp_mask used for preloading.  This allows using more
 * permissive allocation masks for idrs protected by spinlocks.
 *
 * For example, if idr_alloc() below fails, the failure can be treated as
 * if idr_alloc() were called with GFP_KERNEL rather than GFP_NOWAIT.
 *
 *      idr_preload(GFP_KERNEL);
 *      spin_lock(lock);
 *
 *      id = idr_alloc(idr, ptr, start, end, GFP_NOWAIT);
 *
 *      spin_unlock(lock);
 *      idr_preload_end();
 *      if (id < 0)
 *              error;
 */
void idr_preload(gfp_t gfp_mask)
{
        /*
         * Consuming preload buffer from non-process context breaks preload
         * allocation guarantee.  Disallow usage from those contexts.
         */
        WARN_ON_ONCE(in_interrupt());
        might_sleep_if(gfp_mask & __GFP_WAIT);

        preempt_disable();

        /*
         * idr_alloc() is likely to succeed w/o full idr_layer buffer and
         * return value from idr_alloc() needs to be checked for failure
         * anyway.  Silently give up if allocation fails.  The caller can
         * treat failures from idr_alloc() as if idr_alloc() were called
         * with @gfp_mask which should be enough.
         */
        while (__this_cpu_read(idr_preload_cnt) < MAX_IDR_FREE) {
                struct idr_layer *new;

                preempt_enable();
                new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);
                preempt_disable();
                if (!new)
                        break;

                /* link the new one to per-cpu preload list */
                new->ary[0] = __this_cpu_read(idr_preload_head);
                __this_cpu_write(idr_preload_head, new);
                __this_cpu_inc(idr_preload_cnt);
        }
}
EXPORT_SYMBOL(idr_preload);

idr preload 버퍼에 8(32bit 시스템 기준)개의 idr_layer 엔트리를 미리 할당해둔다. 이 idr 프리로드 버퍼는 idr_alloc() 함수가 필요로하는 idr_layer를 미리 준비하여 필요할 때마다 최대한 짧은 시간에 제공하여 preemption disable 구간에서 동작하는 idr_alloc() 함수를 위해 preemption disable 기간을 최대한 줄이기 위해 사용된다.

  • might_sleep_if(gfp_mask & __GFP_WAIT);
    • __GFP_WAIT 플래그가 주어진 경우 현재 태스크보다 더 높은 우선순위의 처리할 태스크가 있는 경우 선점될 수 있다. 즉 sleep 가능하다.
  • preempt_disable();
    • 여기서 부터는 선점되지 않도록 한다.
  • while (__this_cpu_read(idr_preload_cnt) < MAX_IDR_FREE) {
    • 현재 cpu에서 idr_preload_cnt가 MAX_IDR_FREE(최대 레벨의 2배)보다 적은 경우 루프를 계속 수행한다.
      • MAX_IDR_FREE(최대 레벨의 2배) 수 만큼 idr 캐시를 미리 할당해두려는 목적이다.
  • preempt_enable(); new = kmem_cache_zalloc(idr_layer_cache, gfp_mask); preempt_disable(); if (!new) break;
    • preemption을 enable한 상태로 idr_layer_cache를 통해 idr_layer 구조체 영역을 할당받고 실패한 경우 루프를 탈출한다.
  • new->ary[0] = __this_cpu_read(idr_preload_head); __this_cpu_write(idr_preload_head, new);
    • 할당 받은 new idr_layer 구조체를 idr preload 버퍼 리스트에 추가한다.
      • idr_preload_head 리스트에서 idr_layer들은 ary[0]을 이용하여 다음 엔트리가 연결되어 있는 구조이다.
  • __this_cpu_inc(idr_preload_cnt);
    • 추가하였으므로 idr_preload_cnt를 증가시킨다.

 

다음 그림은 idr_preload() 함수를 idr preload 버퍼에 미리 8(32bit 시스템)개의 idr_layer 구조체들을 할당해놓은 것을 보여준다.

idr_preload-1

 

idr_preload_end()

include/linux/idr.h

/**
 * idr_preload_end - end preload section started with idr_preload()
 *
 * Each idr_preload() should be matched with an invocation of this
 * function.  See idr_preload() for details.
 */
static inline void idr_preload_end(void)
{
        preempt_enable();
}

idr_alloc()이 끝났으므로 preemption을 enable하여 이제 선점 가능한 상태도 바꾼다.

 

idr_alloc()

lib/idr.c

/**
 * idr_alloc - allocate new idr entry
 * @idr: the (initialized) idr
 * @ptr: pointer to be associated with the new id
 * @start: the minimum id (inclusive)
 * @end: the maximum id (exclusive, <= 0 for max)
 * @gfp_mask: memory allocation flags
 *
 * Allocate an id in [start, end) and associate it with @ptr.  If no ID is
 * available in the specified range, returns -ENOSPC.  On memory allocation
 * failure, returns -ENOMEM. 
 *
 * Note that @end is treated as max when <= 0.  This is to always allow
 * using @start + N as @end as long as N is inside integer range.
 *
 * The user is responsible for exclusively synchronizing all operations
 * which may modify @idr.  However, read-only accesses such as idr_find()
 * or iteration can be performed under RCU read lock provided the user
 * destroys @ptr in RCU-safe way after removal from idr.
 */
int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
{
        int max = end > 0 ? end - 1 : INT_MAX;  /* inclusive upper limit */
        struct idr_layer *pa[MAX_IDR_LEVEL + 1];
        int id;

        might_sleep_if(gfpflags_allow_blocking(gfp_mask));

        /* sanity checks */
        if (WARN_ON_ONCE(start < 0))
                return -EINVAL;
        if (unlikely(max < start))
                return -ENOSPC;

        /* allocate id */
        id = idr_get_empty_slot(idr, start, pa, gfp_mask, NULL);
        if (unlikely(id < 0))
                return id;
        if (unlikely(id > max))
                return -ENOSPC;

        idr_fill_slot(idr, ptr, id, pa);
        return id;
}
EXPORT_SYMBOL_GPL(idr_alloc);

start ~ (end-1) 정수 범위내에서 빈 id를 찾아 ptr을 저장하고 id를 반환한다. end가 0인 경우 시스템 최대 정수값인 INT_MAX로 지정된다.

  • might_sleep_if(gfp_mask & __GFP_WAIT);
    • 선점 가능한 상태에서 __GFP_WAIT 플래그가 요청된 경우 높은 순위이 태스크가 선점 요청한 경우 sleep 한다.
  • id = idr_get_empty_slot(idr, start, pa, gfp_mask, NULL);
    • start ~ end-1 까지 비어있는 ID를 찾아 반환한다. 이 과정에서 만일 레이어 확장이 필요한 경우 생성하게한다.
  • if (unlikely(id < 0)) return id;
    • 음수를 반환하는 경우 ID를 할당받지 못하여 에러로 리턴한다.
  • if (unlikely(id > max)) return -ENOSPC;
    • 요청 범위내에서 할당이 불가능한 경우 할당할 공간이 없다고 -ENOSPC 에러를 반환한다.
  • idr_fill_slot(idr, ptr, id, pa);
    • id에 해당하는 각 레이어들을 업데이트한다.

 

다음 그림은 0~65535 ID까지 full되어 2단계 레이어로 관리되고 있는 상태에서 65536번의 IDR이 추가 할당되어 3단계 레이어로 확장되는 모습을 보여준다.

idr_alloc-1

 

idr_get_empty_slot()

lib/idr.c

static int idr_get_empty_slot(struct idr *idp, int starting_id,
                              struct idr_layer **pa, gfp_t gfp_mask,
                              struct idr *layer_idr)
{
        struct idr_layer *p, *new;
        int layers, v, id;
        unsigned long flags;

        id = starting_id;
build_up:
        p = idp->top;
        layers = idp->layers;
        if (unlikely(!p)) {
                if (!(p = idr_layer_alloc(gfp_mask, layer_idr)))
                        return -ENOMEM;
                p->layer = 0;
                layers = 1;
        }
        /*
         * Add a new layer to the top of the tree if the requested
         * id is larger than the currently allocated space.
         */
        while (id > idr_max(layers)) {
                layers++;
                if (!p->count) {
                        /* special case: if the tree is currently empty,
                         * then we grow the tree by moving the top node
                         * upwards.
                         */
                        p->layer++;
                        WARN_ON_ONCE(p->prefix);
                        continue;
                }
                if (!(new = idr_layer_alloc(gfp_mask, layer_idr))) {
                        /*
                         * The allocation failed.  If we built part of
                         * the structure tear it down.
                         */
                        spin_lock_irqsave(&idp->lock, flags);
                        for (new = p; p && p != idp->top; new = p) {
                                p = p->ary[0];
                                new->ary[0] = NULL;
                                new->count = 0;
                                bitmap_clear(new->bitmap, 0, IDR_SIZE);
                                __move_to_free_list(idp, new);
                        }
                        spin_unlock_irqrestore(&idp->lock, flags);
                        return -ENOMEM;
                }
                new->ary[0] = p;
                new->count = 1;
                new->layer = layers-1;
                new->prefix = id & idr_layer_prefix_mask(new->layer);
                if (bitmap_full(p->bitmap, IDR_SIZE))
                        __set_bit(0, new->bitmap);
                p = new;
        }
        rcu_assign_pointer(idp->top, p);
        idp->layers = layers;
        v = sub_alloc(idp, &id, pa, gfp_mask, layer_idr);
        if (v == -EAGAIN)
                goto build_up;
        return(v);
}

start ~ end-1 까지 비어있는 ID를 찾아 반환한다. 이 과정에서 만일 레이어 확장(tree depth)이 필요한 경우 생성하게한다.

  • build_up: p = idp->top; layers = idp->layers;
    • idr 구조체의 top이 가리키는 노드를 지정하고, 사용하는 레이어 계층 수를 알아온다.
  • if (unlikely(!p)) { if (!(p = idr_layer_alloc(gfp_mask, layer_idr))) return -ENOMEM;
    • 적은 확률로 노드가 지정되지 않은 경우이면서 idr_layer 구조체를 할당 받지 못한 경우 -ENOMEM 에러를 반환한다.
  • p->layer = 0; layers = 1;
    • leaf 노드이므로 layer 멤버 변수에 0을 대입하고, 레이어 수는 1로 대입한다.
  • while (id > idr_max(layers)) {
    • 요청한 id 값이 현재 idr 레이어가 처리할 수 있는 최대 수를 초과하는 경우 루프를 돈다.
  • if (!(new = idr_layer_alloc(gfp_mask, layer_idr))) {
    • 상위 레이어를 확장(tree depth)하다 할당이 실패하는 경우
  • for (new = p; p && p != idp->top; new = p) { p = p->ary[0]; new->ary[0] = NULL; new->count = 0; bitmap_clear(new->bitmap, 0, IDR_SIZE); __move_to_free_list(idp, new); }
    • 이미 레이어 확장을 위해 만들어 놓은 idr_layer들을 모두 id_free 리스트로 옮긴다.
  • new->ary[0] = p; new->count = 1; new->layer = layers-1; new->prefix = id & idr_layer_prefix_mask(new->layer); if (bitmap_full(p->bitmap, IDR_SIZE)) __set_bit(0, new->bitmap); p = new;
    • 새로 만들어진 레이어의 ary[0]이 기존 레이어를 향하도록 대입하고, 1개의 count를 갖게 대입한다.
    • prefix 값도 지정하고 기존 레이어의 비트맵이 full된 경우 새로 만들어진 bitmap의 처음 비트를 1로 full 설정한다.
  • rcu_assign_pointer(idp->top, p);
    • idr 구조체의 top이 p 노드를 가리킬 수 있도록 대입한다.
  • idp->layers = layers;
    • idr 구조체의 layers를 갱신한다.
  • v = sub_alloc(idp, &id, pa, gfp_mask, layer_idr);
    • 상위 레이어 tree depth 확장은 위 while 문에서 완료되었고 여기에서는 ID를 할당하되 레이어의 depth를 변경하지 않고 그 범위 내의 하위 레이어 중 할당이 필요한 레이어들을 할당한다.
  • if (v == -EAGAIN) goto build_up;
    • ID  할당이 실패한 경우 build_up부터 다시 시작한다.

 

idr_layer_alloc()

lib/idr.c

/**
 * idr_layer_alloc - allocate a new idr_layer
 * @gfp_mask: allocation mask
 * @layer_idr: optional idr to allocate from
 *
 * If @layer_idr is %NULL, directly allocate one using @gfp_mask or fetch
 * one from the per-cpu preload buffer.  If @layer_idr is not %NULL, fetch
 * an idr_layer from @idr->id_free.
 *
 * @layer_idr is to maintain backward compatibility with the old alloc
 * interface - idr_pre_get() and idr_get_new*() - and will be removed
 * together with per-pool preload buffer.
 */
static struct idr_layer *idr_layer_alloc(gfp_t gfp_mask, struct idr *layer_idr)
{
        struct idr_layer *new;

        /* this is the old path, bypass to get_from_free_list() */
        if (layer_idr)
                return get_from_free_list(layer_idr);

        /*
         * Try to allocate directly from kmem_cache.  We want to try this
         * before preload buffer; otherwise, non-preloading idr_alloc()
         * users will end up taking advantage of preloading ones.  As the
         * following is allowed to fail for preloaded cases, suppress
         * warning this time.
         */
        new = kmem_cache_zalloc(idr_layer_cache, gfp_mask | __GFP_NOWARN);
        if (new)
                return new;

        /*
         * Try to fetch one from the per-cpu preload buffer if in process
         * context.  See idr_preload() for details.
         */
        if (!in_interrupt()) {
                preempt_disable();
                new = __this_cpu_read(idr_preload_head);
                if (new) {
                        __this_cpu_write(idr_preload_head, new->ary[0]);
                        __this_cpu_dec(idr_preload_cnt);
                        new->ary[0] = NULL;
                }
                preempt_enable();
                if (new)
                        return new;
        }

        /*
         * Both failed.  Try kmem_cache again w/o adding __GFP_NOWARN so
         * that memory allocation failure warning is printed as intended.
         */
        return kmem_cache_zalloc(idr_layer_cache, gfp_mask);
}

idr preload 버퍼 또는 idr_layer_cache에서 idr_layer 구조체를 할당받아온다.

  • if (layer_idr) return get_from_free_list(layer_idr);
    • 이 함수의 2번째 인수인 layer_idr이 null 값이 아닌 경우 기존 할당 방식을 호환하기 위해 idr 구조체의 id_free 멤버에서 idr_layer를 가져온다.
    • idr preload 버퍼를 사용하는 새로운 방법은 layer_idr 값에 null이 인입되어 이 루틴을 skip 한다.
  • new = kmem_cache_zalloc(idr_layer_cache, gfp_mask | __GFP_NOWARN); if (new) return new;
    • idr_preload() 함수 없이 idr_alloc() 함수를 사용하는 경우를 배려하기 위해 idr preload 버퍼가 아닌 idr_layer_cache로 부터 직접 idr_layer 구조체를 할당받아온다.
      • idr_preload() 함수를 사용한 경우 이 함수를 진행시켜 에러가 발생하면 __GFP_NOWARN 옵션에 의해 경고 메시지가 출력되지 않도록 하였다.
  • if (!in_interrupt()) { preempt_disable();
    • 인터럽트 핸들러에서 호출된 경우가 아니면 idr preload 버퍼를 사용하기 위해 선점을 막아둔다.
  • new = __this_cpu_read(idr_preload_head);  if (new) { __this_cpu_write(idr_preload_head, new->ary[0]); __this_cpu_dec(idr_preload_cnt); new->ary[0] = NULL; }
    • idr_preload_head 리스트에서 idr_layer 구조체를 가져오고 리스트에서 제거한다.
  • preempt_enable(); if (new) return new;
    • 다시 선점 가능 상태로 돌리고 할당이 성공한 경우 반환한다.
  • return kmem_cache_zalloc(idr_layer_cache, gfp_mask);
    • 모두 실패한 경우 마지막으로 다시 한 번 idr_layer_cache로부터 직접 시도한다. 이 때에는 실패 시 경고 메시지가 출력된다.

 

get_from_free_list()

lib/idr.c

static struct idr_layer *get_from_free_list(struct idr *idp)
{
        struct idr_layer *p;
        unsigned long flags;

        spin_lock_irqsave(&idp->lock, flags);
        if ((p = idp->id_free)) {
                idp->id_free = p->ary[0];
                idp->id_free_cnt--;
                p->ary[0] = NULL;
        }
        spin_unlock_irqrestore(&idp->lock, flags);
        return(p);
}

id_free 리스트에 엔트리가 있는 경우 리스트에서 엔트리를 제거하고 그 엔트리를 반환한다.

 

idr_max()

lib/idr.c

/* the maximum ID which can be allocated given idr->layers */
static int idr_max(int layers)
{
        int bits = min_t(int, layers * IDR_BITS, MAX_IDR_SHIFT);

        return (1 << bits) - 1;
}

주어진 레이어에서 할당받을 수 있는 max ID(positive integer)를 알아온다.

  • 예) 32bit 시스템
    • 1단계 레이어: 0xff (8bit)
    • 2단계 레이어: 0xffff (16bit)
    • 3단계 레이어: 0xff_ffff (24bit)
    • 4단계 레이어: 0x7fff_ffff (positive integer, 31bit로 제한)

 

__move_to_free_list()

lib/idr.c

/* only called when idp->lock is held */
static void __move_to_free_list(struct idr *idp, struct idr_layer *p)
{
        p->ary[0] = idp->id_free;
        idp->id_free = p;
        idp->id_free_cnt++;
}

엔트리를 id_free 리스트에 추가한다.

 

idr_layer_prefix_mask()

lib/idr.c

/*
 * Prefix mask for an idr_layer at @layer.  For layer 0, the prefix mask is
 * all bits except for the lower IDR_BITS.  For layer 1, 2 * IDR_BITS, and
 * so on.
 */
static int idr_layer_prefix_mask(int layer)
{
        return ~idr_max(layer + 1);
}

요청 layer에 대한 prefix 값을 반환한다.

  • 예) layer 0을 요청하는 경우 0xffffff00을 반환한다.

 

sub_alloc()

lib/idr.c

/**
 * sub_alloc - try to allocate an id without growing the tree depth
 * @idp: idr handle
 * @starting_id: id to start search at
 * @pa: idr_layer[MAX_IDR_LEVEL] used as backtrack buffer
 * @gfp_mask: allocation mask for idr_layer_alloc()
 * @layer_idr: optional idr passed to idr_layer_alloc()
 *
 * Allocate an id in range [@starting_id, INT_MAX] from @idp without
 * growing its depth.  Returns
 *
 *  the allocated id >= 0 if successful,
 *  -EAGAIN if the tree needs to grow for allocation to succeed,
 *  -ENOSPC if the id space is exhausted,
 *  -ENOMEM if more idr_layers need to be allocated.
 */
static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa,
                     gfp_t gfp_mask, struct idr *layer_idr)
{
        int n, m, sh;
        struct idr_layer *p, *new;
        int l, id, oid;

        id = *starting_id;
 restart:
        p = idp->top;
        l = idp->layers;
        pa[l--] = NULL;
        while (1) {
                /*
                 * We run around this while until we reach the leaf node...
                 */
                n = (id >> (IDR_BITS*l)) & IDR_MASK;
                m = find_next_zero_bit(p->bitmap, IDR_SIZE, n);
                if (m == IDR_SIZE) {
                        /* no space available go back to previous layer. */
                        l++;
                        oid = id;
                        id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;

                        /* if already at the top layer, we need to grow */
                        if (id > idr_max(idp->layers)) {
                                *starting_id = id;
                                return -EAGAIN;
                        }
                        p = pa[l];
                        BUG_ON(!p);

                        /* If we need to go up one layer, continue the
                         * loop; otherwise, restart from the top.
                         */
                        sh = IDR_BITS * (l + 1);
                        if (oid >> sh == id >> sh)
                                continue;
                        else
                                goto restart;
                }

ID를 할당하되 레이어의 depth를 변경하지 않고 그 범위 내의 하위 레이어 중 할당이 필요한 레이어들을 할당한다. 출력 인수 pa 포인터 배열에는 최상위 레이어부터 id에 해당하는 레이어까지 idr_layer의 포인터 주소를 담는다.

  • pa[0]가 가장 하단 레이어를 가리키고 그 다음 배열은 id와 관련된 상위 레이어로 증가하면서 최상위 레이어까지 간다음 마지막에는 null로 종결한다.

 

  • id = *starting_id;
    • starting_id 부터 준비한다.
  • restart: p = idp->top;
    • 처음부터 다시 수행해야 할 때 여기 restart: 레이블로 이동해와서 idr 구조체의 top에 연결된 최상위 노드를 준비한다.
  • l = idp->layers; pa[l–] = NULL;
    • l은 사용하는 레이어 수를 알아오고 처리할 마지막 pa[] 배열의 끝에 null을 대입한다.
  • while (1) { n = (id >> (IDR_BITS*l)) & IDR_MASK; m = find_next_zero_bit(p->bitmap, IDR_SIZE, n);
    • 루프를 돌며 n은 id 값을 현재 레이어 값 x 8로 나눈 몫에서 IDR_MASK한 값으로 bitmap 인덱스 n에 대입하고, bitmap에서 n값 뒤로 0으로 설정된 비트 위치를 m에 알아온다. 못 찾은 경우 IDR_SIZE 값을 반환한다.
    • 예) 전체 레이어가 3단계이고, 현재 레벨에서 마지막 남은 ID를 할당받고자 할 때
      • id=0, bitmap=0x7fffffff_ffffffff_ffffffff_ffffffff_ffffffff_ffffffff_ffffffff_ffffffff, l=2
        • n=0, m=0xff
  • if (m == IDR_SIZE) {
    • 지정된 번호 뒤로 빈 곳이 없는 경우는 현재 노드에 처리할 ID 공간이 없다는 것을 의미한다.
  • l++; old = id; id = (id | ((1 << (IDR_BITS * l)) – 1)) + 1;
    • 다시 상위 레이어로 돌아가기 위해 l을 증가시키고, 현재 id를 백업하며 다음 빈자리를 찾기 위해 현재 레이어에서 우측 형제 레이어의 첫 id를 지정한다.
  • if (id > idr_max(idp->layers)) { *starting_id = id; return -EAGAIN; }
    • 현재 레이어 레벨 구조로 더 이상 ID를 할당할 공간이 없는 경우 starting_id에 id값을 대입하고, -EAGAIN을 반환하여 레이어의 레벨을 확장하도록 요청한다.
  • p = pa[l];
    • 상위 레이어를 지정한다.
  • sh = IDR_BITS * (l + 1); if (oid >> sh == id >> sh) continue; else goto restart;
    • 새로 배정한 id가 상위 노드에서 처리 가능한 경우 계속 루프를 돌고 그렇지 않은 경우 restart 레이블로 이동하여 다시 처음부터 처리한다.
  • if (m != n) { sh = IDR_BITS*l;  id = ((id >> sh) ^ n ^ m) << sh; }
    • 예) id=0, n=0, m=0xff, l=2
      • id=0xff0000
  • if ((id >= MAX_IDR_BIT) || (id < 0)) return -ENOSPC;
    • id 값이 positive 정수 범위를 벗어나는 경우 시스템이 처리할 수 없어서 -ENOSPC 에러를 반환한다.
  • if (l == 0) break;
    • 마지막 leaf 노드 레이어까지 처리한 경우 루프를 빠져나간다.
  • if (!p->ary[m]) { new = idr_layer_alloc(gfp_mask, layer_idr); if (!new) return -ENOMEM;
    • 하위 노드가 없는(missing) 경우 만든다.
  • new->layer = l-1; new->prefix = id & idr_layer_prefix_mask(new->layer); rcu_assign_pointer(p->ary[m], new); p->count++;
    • 하위 노드의 layer 및 prefix를 지정하고 현재 노드의 ary[]에 연결한다음 count를 증가시킨다.

 

                if (m != n) {
                        sh = IDR_BITS*l;
                        id = ((id >> sh) ^ n ^ m) << sh;
                }
                if ((id >= MAX_IDR_BIT) || (id < 0))
                        return -ENOSPC;
                if (l == 0)
                        break;
                /*
                 * Create the layer below if it is missing.
                 */
                if (!p->ary[m]) {
                        new = idr_layer_alloc(gfp_mask, layer_idr);
                        if (!new)
                                return -ENOMEM;
                        new->layer = l-1;
                        new->prefix = id & idr_layer_prefix_mask(new->layer);
                        rcu_assign_pointer(p->ary[m], new);
                        p->count++;
                }
                pa[l--] = p;
                p = p->ary[m];
        }

        pa[l] = p;
        return id;
}
  • if (m != n) { sh = IDR_BITS*l; id = ((id >> sh) ^ n ^ m) << sh; }
    • m과 n이 다른 경우 빈 자리의 id를 찾는다.
  • if ((id >= MAX_IDR_BIT) || (id < 0)) return -ENOSPC;
    • id 값이 범위 밖이면 할당할 공간이 없다고 에러를 반환한다.
  • if (l == 0) break;
    • 최하위 레이어까지 내려온 경우 루프를 빠져나간다.
  • if (!p->ary[m]) { new = idr_layer_alloc(gfp_mask, layer_idr); if (!new) return -ENOMEM;
    • 만일 할당할 id 번호를 관리하는 하위 레이어 노드가 없는 경우 레이어를 할당받아온다.
  • new->layer = l-1; new->prefix = id & idr_layer_prefix_mask(new->layer); rcu_assign_pointer(p->ary[m], new); p->count++;
    • 할당 받아온 레이어의 번호와 prefix, count 등을 업데이트 하고 ary[m]에 할당한 레이어를 가리키게 한다.
  • pa[l–] = p; p = p->ary[m]; }
    • 다음 아래 레이어를 처리하기 위해 감소시켜 지정하고 계속 루프를 돈다.
  • pa[l] = p; return id;
    • 마지막 pa[0]를 갱신하고 id를 리턴한다.

 

idr_fill_slot()

lib/idr.c

/*
 * @id and @pa are from a successful allocation from idr_get_empty_slot().
 * Install the user pointer @ptr and mark the slot full.
 */
static void idr_fill_slot(struct idr *idr, void *ptr, int id,
                          struct idr_layer **pa)
{
        /* update hint used for lookup, cleared from free_layer() */
        rcu_assign_pointer(idr->hint, pa[0]);

        rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], (struct idr_layer *)ptr);
        pa[0]->count++;
        idr_mark_full(pa, id);
}

마지막에 ID를 할당한 leaf 노드의 주소를 idr 구조체의 hint 멤버에 대입하고, ary[]배열에 ptr을 저장하고, count를 증가시킨 후 full이된 레이어들의 bitmap을 1로 설정한다.

  • rcu_assign_pointer(idr->hint, pa[0]);
    • 마지막에 ID를 할당한 leaf 노드의 주소를 idr 구조체의 hint 멤버에 저장한다.
    • idr_find() 함수에서 id로 검색시 hint가 가리키는 레이어가 요청하는 id를 커버하는 경우 빠르게 처리하기 위해 사용한다.
  • rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], (struct idr_layer *)ptr);
    • 마지막에 ID를 할당한 leaf 노드의 id에 해당하는 ary[] 배열에 ptr 값을 저장한다.
  • pa[0]->count++;
    • 마지막에 ID를 할당한 leaf 노드의 카운터를 증가시킨다.
  • idr_mark_full(pa, id);
    • 마지막에 ID를 할당한 leaf 노드의 bitmap에 id에 해당하는 비트를 1로 설정하여 ID가 할당되었음을 표시한 후, 그 노드부터 최상위 노드중 full된 노드의 상위 노드 bitmap에 해당 비트를 1로 설정한다.

 

idr_mark_full()

lib/idr.c

static void idr_mark_full(struct idr_layer **pa, int id)
{
        struct idr_layer *p = pa[0];
        int l = 0;

        __set_bit(id & IDR_MASK, p->bitmap);
        /*
         * If this layer is full mark the bit in the layer above to
         * show that this part of the radix tree is full.  This may
         * complete the layer above and require walking up the radix
         * tree.
         */
        while (bitmap_full(p->bitmap, IDR_SIZE)) {
                if (!(p = pa[++l]))
                        break;
                id = id >> IDR_BITS;
                __set_bit((id & IDR_MASK), p->bitmap);
        }
}

마지막에 ID를 할당한 leaf 노드의 bitmap에 id에 해당하는 비트를 1로 설정하여 ID가 할당되었음을 표시한 후, 그 노드부터 최상위 노드중 full된 노드의 상위 노드 bitmap에 해당 비트를 1로 설정한다.

  • struct idr_layer *p = pa[0];
    • 최하위 leaf 노드
  • __set_bit(id & IDR_MASK, p->bitmap);
    • 해당 idr_layer 노드의 bitmap에서 id에 해당하는 포지션을 1로 설정하여 ID가 할당되었음을 표시한다.
  • while (bitmap_full(p->bitmap, IDR_SIZE)) {
    • 노드가 full인 경우 계속 루프를 돈다.
  • if (!(p = pa[++l])) break;
    • 상위 노드가 지정되지 않은 경우 루프를 탈출한다.
  • id = id >> IDR_BITS;
    • id 값을 256으로 나눈다.
  • __set_bit((id & IDR_MASK), p->bitmap);
    • 현재 노드의 bitmap에서 id에 해당하는 포지션을 1로 설정하여 하위 노드가 full이 되었음을 표시한다.

 

다음 그림은 0xffffff ID를 할당받은 후 idr_mark_full() 함수에 의해 각 bitmap에 full 처리되는 모습을 보여준다.

idr_mark_full-1

 

 

IDR 해제

idr_remove()

lib/idr.c

/**
 * idr_remove - remove the given id and free its slot
 * @idp: idr handle
 * @id: unique key
 */
void idr_remove(struct idr *idp, int id)
{
        struct idr_layer *p;
        struct idr_layer *to_free;

        if (id < 0)
                return;

        if (id > idr_max(idp->layers)) {
                idr_remove_warning(id);
                return;
        }

        sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
        if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
            idp->top->ary[0]) {
                /*
                 * Single child at leftmost slot: we can shrink the tree.
                 * This level is not needed anymore since when layers are
                 * inserted, they are inserted at the top of the existing
                 * tree.
                 */
                to_free = idp->top;
                p = idp->top->ary[0];
                rcu_assign_pointer(idp->top, p);
                --idp->layers;
                to_free->count = 0;
                bitmap_clear(to_free->bitmap, 0, IDR_SIZE);
                free_layer(idp, to_free);
        }
}
EXPORT_SYMBOL(idr_remove);

할당한 id를 제거하고, 제거하는 중에 empty된 레이어들은 제거된다. 필요에 따라 레이어 depth 까지도 줄어든다.

 

  • if (id < 0) return; if (id > idr_max(idp->layers)) { idr_remove_warning(id); return; }
    • IDR에서 처리할 수 있는 id 범위를 벗어난 경우 그냥 빠져나간다.
  • sub_remove(idp, (idp->layers – 1) * IDR_BITS, id);
    • tree depth를 줄이지 않은 상태에서 삭제할 id에 관여되는 레이어들 중 empty되는 레이어들을 연결에서 제거하여 id_free로 대입한다.
  • if (idp->top && idp->top->count == 1 && (idp->layers > 1) && idp->top->ary[0]) {
    • 최상위 레이어의 count가 1이면서 하위 레이어를 가리키는 경우
  • to_free = idp->top; p = idp->top->ary[0]; rcu_assign_pointer(idp->top, p);
    • 삭제 준비를 위해 최상위 레이어를 to_free에 대입하고, 최상위 레이어로 그 하위 레이어를 지정하게 한다.
  • –idp->layers; to_free->count = 0; bitmap_clear(to_free->bitmap, 0, IDR_SIZE); free_layer(idp, to_free);
    • 레이어 수(tree depth)를 줄이고, 삭제할 레이어의 count, bitmap을 clear한 후 해제한다.

 

다음 그림은 3단계의 레이어에서 65536번 id를 삭제하면서 레이어들이 삭제되고 tree depth가 줄어드는 과정을 보여준다.

idr_remove-1a

 

sub_remove()

lib/idr.c

static void sub_remove(struct idr *idp, int shift, int id)
{
        struct idr_layer *p = idp->top;
        struct idr_layer **pa[MAX_IDR_LEVEL + 1];
        struct idr_layer ***paa = &pa[0];
        struct idr_layer *to_free;
        int n;

        *paa = NULL;
        *++paa = &idp->top;

        while ((shift > 0) && p) {
                n = (id >> shift) & IDR_MASK;
                __clear_bit(n, p->bitmap);
                *++paa = &p->ary[n];
                p = p->ary[n];
                shift -= IDR_BITS;
        }
        n = id & IDR_MASK;
        if (likely(p != NULL && test_bit(n, p->bitmap))) {
                __clear_bit(n, p->bitmap);
                RCU_INIT_POINTER(p->ary[n], NULL);
                to_free = NULL;
                while(*paa && ! --((**paa)->count)){
                        if (to_free)
                                free_layer(idp, to_free);
                        to_free = **paa;
                        **paa-- = NULL;
                }
                if (!*paa)
                        idp->layers = 0;
                if (to_free)
                        free_layer(idp, to_free);
        } else
                idr_remove_warning(id);
}

tree depth를 줄이지 않은 상태에서 삭제할 id에 관여되는 레이어들 중 empty되는 레이어들을 연결에서 제거하고 할당을 해제한다.

  • struct idr_layer ***paa = &pa[0]; *paa = NULL; *++paa = &idp->top;
    • pa[0]에 null을 대입하고 pa[1]에 top 레이어를 담는다.
  • while ((shift > 0) && p) { n = (id >> shift) & IDR_MASK; __clear_bit(n, p->bitmap); *++paa = &p->ary[n]; p = p->ary[n]; shift -= IDR_BITS; }
    • 하위 leaf 레이어 전까지 내려가면서 pa[]에 각 레이어를 저장하고 bitmap의 연관 비트들을 clear한다.
  • n = id & IDR_MASK;
    • 하위 leaf 레이어에서 bit 위치
  • if (likely(p != NULL && test_bit(n, p->bitmap))) { __clear_bit(n, p->bitmap); RCU_INIT_POINTER(p->ary[n], NULL); to_free = NULL;
    • 많은 확률로 leaf 레이어의 bitmap이 설정되어 있는 경우 비트를 clear 하고 ary[n]도 rcu를 사용하여 null로 대입한다.
  • while(*paa && ! –((**paa)->count)){ if (to_free) free_layer(idp, to_free); to_free = **paa; **paa– = NULL; }
    • pa[] 배열에 저장된 레이어를 다시 거꾸로 루프를 돌면서 해당 레이어의 count를 감소시켜 0인 경우 to_free에 지정된 레이어가 있는 경우 해제한다. 그리고 현재 레이어를 to_free에 담아두고 pa[]에 null을 저장하고 다음 감소시킨 pa[]를 지정한다.
  • if (!*paa) idp->layers = 0;
    • 마지막인 경우 idp->layers에 0을 대입하여 어떠한 하위 레이어도 없음을 나타내게 한다.
  • if (to_free) free_layer(idp, to_free);
    • to_free 레이어를 해제한다.

 

static inline void free_layer(struct idr *idr, struct idr_layer *p)
{
        if (idr->hint == p)
                RCU_INIT_POINTER(idr->hint, NULL);
        call_rcu(&p->rcu_head, idr_layer_rcu_free);
}

idr->hint가 삭제할 p를 가리키는 경우 hint에 null을 대입한다 그런 후 rcu 기법으로 idr_layer_rcu_free 함수를 호출하여 해당 레이어를 해제하게 한다.

 

idr_layer_rcu_free()

lib/idr.c

static void idr_layer_rcu_free(struct rcu_head *head)
{
        struct idr_layer *layer;

        layer = container_of(head, struct idr_layer, rcu_head);
        kmem_cache_free(idr_layer_cache, layer);
}

요청된 idr_layer를 해제한다.

 

IDR 소거

 

idr_destroy()

lib/idr.c

/**
 * idr_destroy - release all cached layers within an idr tree
 * @idp: idr handle
 *
 * Free all id mappings and all idp_layers.  After this function, @idp is
 * completely unused and can be freed / recycled.  The caller is
 * responsible for ensuring that no one else accesses @idp during or after
 * idr_destroy().
 *
 * A typical clean-up sequence for objects stored in an idr tree will use
 * idr_for_each() to free all objects, if necessary, then idr_destroy() to
 * free up the id mappings and cached idr_layers.
 */
void idr_destroy(struct idr *idp)
{
        __idr_remove_all(idp);

        while (idp->id_free_cnt) {
                struct idr_layer *p = get_from_free_list(idp);
                kmem_cache_free(idr_layer_cache, p);
        }
}
EXPORT_SYMBOL(idr_destroy);

모든 idr 레이어를 삭제시키고 id_free 리스트에 담겨있는 할당 대기중인 레이어들을 해제한다.

 

__idr_remove_all()

lib/idr.c

static void __idr_remove_all(struct idr *idp)
{
        int n, id, max;
        int bt_mask;
        struct idr_layer *p;
        struct idr_layer *pa[MAX_IDR_LEVEL + 1];
        struct idr_layer **paa = &pa[0];

        n = idp->layers * IDR_BITS;
        *paa = idp->top;
        RCU_INIT_POINTER(idp->top, NULL);
        max = idr_max(idp->layers);

        id = 0;
        while (id >= 0 && id <= max) {
                p = *paa;
                while (n > IDR_BITS && p) {
                        n -= IDR_BITS;
                        p = p->ary[(id >> n) & IDR_MASK];
                        *++paa = p;
                }

                bt_mask = id;
                id += 1 << n;
                /* Get the highest bit that the above add changed from 0->1. */
                while (n < fls(id ^ bt_mask)) {
                        if (*paa)
                                free_layer(idp, *paa);
                        n += IDR_BITS;
                        --paa;
                }
        }
        idp->layers = 0;
}

idr 레이어를 모두 해제한다.

  • n = idp->layers * IDR_BITS;
    • 처리할 최대 비트 수
    • 예) layer=3이면 n=24
  • *paa = idp->top;
    • pa[0]에 최상위 레이어를 대입한다.
  • RCU_INIT_POINTER(idp->top, NULL);
    • idp->top에 null을 대입하여 idr_layer가 하나도 등록되지 않았음을 나타내게 한다.
  • max = idr_max(idp->layers);
    • 최대 처리 가능한 id 값
  • id = 0; while (id >= 0 && id <= max) { p = *paa; while (n > IDR_BITS && p) { n -= IDR_BITS;  p = p->ary[(id >> n) & IDR_MASK]; *++paa = p; }
    • 마지막 leaf 레이어가 아닌 경우 pa[] 배열에 레이어를 추가해 나간다.
  • bt_mask = id; id += 1 << n;
    • id를 보관하고 id를 횡방향의 다음 레이어가 관리하는 id의 시작 번호로 대입한다.
  • while (n < fls(id ^ bt_mask)) { if (*paa) free_layer(idp, *paa); n += IDR_BITS; –paa; }
    • 가장 마지막에 존재하는 레이어를 해제한다.

 

구조체 및 주요 상수

idr_layer

include/linux/idr.h

struct idr_layer {
        int                     prefix; /* the ID prefix of this idr_layer */
        int                     layer;  /* distance from leaf */
        struct idr_layer __rcu  *ary[1<<IDR_BITS];
        int                     count;  /* When zero, we can release it */
        union {
                /* A zero bit means "space here" */
                DECLARE_BITMAP(bitmap, IDR_SIZE);
                struct rcu_head         rcu_head;
        };
};
  • prefix
    • 각 레이어가 관리하는 id를 제외한 비트들만 사용되는 마스크
    • 예) 32bit 시스템
      • 0 layer (leaf 노드) -> 0xffffff00
      • 1 layer -> 0xffff0000
      • 2 layer -> 0xff000000
      • 3 layer -> 0x80000000
  • layer
    • 레이어 번호(based 0)
      • leaf 노드는 0
  • ary[256]
    • leaf 노드가 아닌 경우 하위 레이어를 가리키고, leaf 노드인 경우 유저 포인터 값을 담아두는데 사용한다.
  • count
    • leaf 노드에서는 ID가 할당되어 사용중인 수가 담기고 leaf 노드가 아닌 경우 연결된 하위 노드의 수를 담아둔다.
    • 이 값이 0이면 레이어는 해제될 수 있다.
  • bitmap
    • leaf 노드에서는 ID가 할당된 경우 1로 설정되고, leaf 노드가 아닌 경우 하위 노드가 full인 경우 1로 설정된다.
  • rcu_head
    • bitmap과 union으로 사용되는데 노드를 rcu 기법으로 삭제할 때 사용한다.

 

idr

include/linux/idr.h

struct idr {
        struct idr_layer __rcu  *hint;  /* the last layer allocated from */
        struct idr_layer __rcu  *top;
        int                     layers; /* only valid w/o concurrent changes */
        int                     cur;    /* current pos for cyclic allocation */
        spinlock_t              lock;
        int                     id_free_cnt;
        struct idr_layer        *id_free;
};
  • hint
    • 마지막 ID가 할당된 노드
  • top
    • 가장 상위 노드
  • layers
    • 운용되는 레이어 단계(tree depth)로 최대 ID 값에 따라 증감되며 운용된다.
    • 0인 경우 어떠한 레이어도 없고 노드도 사용되지 않는다.
    • 32bit 시스템에서 0~4까지 운용되고, 64bit 시스템에서는 0~8까지 운용될 수 있다.
    • 예) 최대 id가 255인 경우layers=1
  • cur
    • 1
  • lock
    • 레이어를 관리하기 위한 lock
  • id_free_cnt
    • 기존 id 할당 방식을 호환하기 위해 캐시역할로 미리 할당된 idr_layer 엔트리 갯수가 담긴다.
  • id_free
    • 기존 id 할당 방식을 호환하기 위해 캐시역할로 미리 할당된 idr_layer 엔트리가 이 리스트에 등록된다.

 

IDR_BITS

  • #define IDR_BITS 8
    • 이 값은 기존 5(32bit 시스템) 또는 6(64bit 시스템)에서 2013년 커널 v3.9-rc1에서 8로 증가되었다.
    • 참고: idr: make idr_layer larger

 

IDR_SIZE

  • #define IDR_SIZE (1 << IDR_BITS)
    • 256

 

IDR_MASK

  • IDR_MASK ((1 << IDR_BITS)-1)
    • 255

 

 MAX_IDR_SHIFT

  • #define MAX_IDR_SHIFT           (sizeof(int) * 8 – 1)
    • 부호를 제외한 정수에 사용되는 비트 수
    • 31 (32bit 시스템)
    • 63 (64bit 시스템)

 

MAX_IDR_BIT

  • #define MAX_IDR_BIT             (1U << MAX_IDR_SHIFT)
    • 부호를 제외한 정수 최대수
    • 2^31 (32bit 시스템)
    • 2^63 (64bit 시스템)

 

MAX_IDR_LEVEL

  • #define MAX_IDR_LEVEL ((MAX_IDR_SHIFT + IDR_BITS – 1) / IDR_BITS)
    • MAX_IDR_SHIFT 값을 IDR_BITS 단위로 round up 한 수로 최대 확장될 수 있는 레벨
    • 4 레벨 (32bit 시스템)
    • 8 레벨 (64bit 시스템)

 

MAX_IDR_FREE

  • #define MAX_IDR_FREE (MAX_IDR_LEVEL * 2)
  • 8 (32bit 시스템)
  • 16 (64bit 시스템)

 

참고

Vmap

<kernel v5.0>

Vmap

커널에서는 단편화 문제를 유발하는 high order 페이지 할당의 사용을 매우 꺼려한다. 따라서 사이즈가 큰 페이지 할당이 필요하지만 빈번한 할당/해제를 하지 않는 경우에 한해 여러 개의 싱글(order 0) 페이지들을 사용하여 연속된 가상 주소 공간에 모아 매핑하는 방법을 사용한다. 이러한 매핑 방법을 vmap(Virtually contiguous memory area mapping)이라고 한다.

 

vmap을 사용하여 다음 2가지의 주소 공간에 메모리를 할당하는 api는 다음과 같다.

  • vmalloc()
    • 요청 size 만큼의 페이지를 할당하여 vmalloc address space 공간에 매핑
  • module_alloc()
    • 요청 size 만큼의 페이지를 할당하여 module address space 공간에 매핑

 

VM 영역 관리

VMALLOC 가상 주소 공간의 빈 공간 검색을 위해 RB 트리 및 리스트 자료 구조를 동시에 사용한다.

  • RB 트리
  • 리스트

 

다음 그림은 vmalloc 가상 주소 공간내에서 VM 영역들이 RB 트리 및 리스트에서 관리되고 있는 모습을 보여준다.

 

관리 항목

위의 자료 구조를 사용하여 vmalloc의 공간을 관리하는 항목은 다음과 같다.

  • 사용 공간 관리
    • vmap_area_root
    • vmap_area_list
  • 빈 공간 관리
  • lazy free 관리
    • purge_vmap_area_root
    • purge_vmap_area_list

 

Lazy TLB Flushing(Free)

  • vunmap()을 수행하면 다음과 같은 처리항목이 수행되어야 하는데 즉각 처리되는 항목과 나중에 모아 처리할 항목을 분류한다.
    • 즉각 처리
      • 페이지 테이블에서 매핑 해제
      • 캐시 flush
    • 지연 처리
      • RB tree 및 리스트에서 지연된 vmap_area의 제거
      • 모든 cpu의 TLB flush
        • cpu가 많은 시스템에서 arm64의 경우 inner 영역의 cpu들에 대해 일괄적으로 TLB flush를 수행하게 할 수 있어 arm32보다는 조금 더 낳은 요건이 있다. 이에 비해 arm32 시스템의 경우 IPI(Inter Process Interrupt) 콜을 사용하여 각 cpu로 인터럽트를 발생시킨 후 처리하게 하여 더욱 처리 성능을 떨어뜨리는 요인이 된다.
  • 삭제할 vma를 처리하지 않고 놔두었다가 일정량을 초과하거나 메모리 부족 시 한꺼번에 purge 처리하여 처리 성능을 높인다.
    • 이러한  해지를 유보하는 방법을 사용하여 vmap_area의 관리를 약 20배 이상 빠르게 처리를 하는 구현을 적용하였다.
  • lazy TLB free 상태를 표현하는 플래그 비트는 다음과 같다.
    • VM_LAZY_FREE (0x1)
      • 삭제 요청된 상태
    • VM_LAZY_FREEING (0x2)
      • purge 진행중인 상태
    • VM_VM_AREA (0x4)
      • 할당 상태

 

다음 그림은 VM 영역이 vunmap()에 의해 Lazy TLB 플러시 상태로 변화하고, 그 후 purge될 때 실제 TLB 플러시 처리되는 과정을 보여준다.

 

관련 API

  • vmap()
  • vunmap()

 

대체 API

vmap() 대체 api로 per-cpu map 기반의 api들이 소개되었다. 이 API는 아직 많은 드라이버에 적용되어 사용하지는 않고 일부 드라이버들 에서만 사용하고 있다.

  • vm_map_ram()
  • vm_unmap_ram()

 


vmap 매핑

vmap() 함수를 사용하기 위해서 매핑에 사용할 싱글(order 0) 페이지 단위의 물리 메모리 정보들을 페이지 디스크립터 배열로 구성하여 요청한다. 그러면 vmalloc 가상 주소 공간의 빈 자리를 찾아 페이지들을 주어진 매핑 속성으로 매핑하고 매핑된 가상 시작 주소를 반환한다.

  • 보다 빠른 할당/해제를 위해 캐시 노드와 몇 개의 변수들을 사용한다.
    • free_vmap_cache
      • 빈 공간에 대한 검색을 빠르게 하기 위해 가장 최근에 등록하여 사용한 vmap_area 또는 가장 최근에 free 한 vmap_area의 이전(prev) vmap_area가 보관된다.
    • cached_hole_size
      • 캐시의 바로 앞 hole의 크기를 기억한다.
      • 이 값이 0이면 캐시를 사용하지 않고 처음부터 검색을 수행한다.
    • cached_vstart
      • 캐시된 시작 가상 주소
    • cached_align
      • 캐시된 align 값
  • per-cpu에서 사용하는 변수
    • vmap_area_pcpu_hole
      • per-cpu의 할당 시작 주소로 vmalloc 공간의 끝 부터 시작한다. (초기값은 VMALLOC_END)
      • vmalloc()이 vmalloc 공간의 처음 주소부터 할당하지만, per-cpu는 그 반대이다.

 

다음 그림은 vmap() 함수에 대해 연관 함수들과의 처리 흐름을 보여준다.

 

vmap()

mm/vmalloc.c

/**
 *      vmap  -  map an array of pages into virtually contiguous space
 *      @pages:         array of page pointers
 *      @count:         number of pages to map
 *      @flags:         vm_area->flags
 *      @prot:          page protection for the mapping
 *
 *      Maps @count pages from @pages into contiguous kernel virtual
 *      space.
 */
void *vmap(struct page **pages, unsigned int count,
                unsigned long flags, pgprot_t prot)
{
        struct vm_struct *area;
        unsigned long size;             /* In bytes */

        might_sleep();

        if (count > totalram_pages())
                return NULL;

        size = (unsigned long)count << PAGE_SHIFT;
        area = get_vm_area_caller(size, flags, __builtin_return_address(0));
        if (!area)
                return NULL;

        if (map_vm_area(area, prot, pages)) {
                vunmap(area->addr);
                return NULL;
        }

        return area->addr;
}
EXPORT_SYMBOL(vmap);

연속된 가상 주소 공간에 요청한 물리 페이지들을 매핑하고 매핑한 가상 주소를 반환한다. 실패 시 null을 반환한다.

  • 코드 라인 7에서 CONFIG_PREEMPT_VOLUNTARY 커널 옵션을 사용하는 경우 preempt point로 긴급히 리스케쥴링 요청한 태스크가 있는 경우 sleep 한다.
  • 코드 라인 9~10에서 전체 메모리 페이지보다 더 많은 페이지를 요구하는 경우 처리를 포기하고 null을 반환한다.
  • 코드 라인 12~15에서 VM 할당을 위해, vmap_area 및 vm_struct 정보를 구성한다. 실패하는 경우 null을 반환한다.
  • 코드 라인 17~20에서 vm_struct 정보로 페이지들의 매핑을 시도하고 실패한 경우 해제 후 null을 반환한다.
  • 코드 라인 22에서 매핑한 가상 주소 공간의 시작 주소를 반환한다.

 

다음 그림은 요청한 물리 페이지들에 대해 VMALLOC 가상 주소 공간에서 빈 공간을 찾아 매핑을 하는 모습을 보여준다.

 

VM(가상 주소 영역)  할당

get_vm_area_caller()

mm/vmalloc.c

struct vm_struct *get_vm_area_caller(unsigned long size, unsigned long flags,
                                const void *caller)
{
        return __get_vm_area_node(size, 1, flags, VMALLOC_START, VMALLOC_END,
                                  NUMA_NO_NODE, GFP_KERNEL, caller);
}

요청한 size(페이지 단위로 정렬된 byte 단위)로 VMALLOC 가상 주소 공간에서 빈 공간을 찾아 VM(vm_area 및 vm_struct) 정보를 구성해온다.

 

__get_vm_area_node()

mm/vmalloc.c

static struct vm_struct *__get_vm_area_node(unsigned long size,
                unsigned long align, unsigned long flags, unsigned long start,
                unsigned long end, int node, gfp_t gfp_mask, const void *caller)
{
        struct vmap_area *va;
        struct vm_struct *area;

        BUG_ON(in_interrupt());
        size = PAGE_ALIGN(size);
        if (unlikely(!size))
                return NULL;

        if (flags & VM_IOREMAP)
                align = 1ul << clamp_t(int, get_count_order_long(size),
                                       PAGE_SHIFT, IOREMAP_MAX_ORDER);

        area = kzalloc_node(sizeof(*area), gfp_mask & GFP_RECLAIM_MASK, node);
        if (unlikely(!area))
                return NULL;

        if (!(flags & VM_NO_GUARD))
                size += PAGE_SIZE;

        va = alloc_vmap_area(size, align, start, end, node, gfp_mask);
        if (IS_ERR(va)) {
                kfree(area);
                return NULL;
        }

        setup_vmalloc_vm(area, va, flags, caller);

        return area;
}

@start ~ @end 가상 주소 공간에서 @align 조건의 @size 만큼의 빈 영역을 찾아 vm을 할당 구성한 후 반환한다.

  • 코드 라인 9~11에서 페이지 단위로 사이즈를 정렬한다.
  • 코드 라인 13~15에서 ioremap이 요청된 경우 사이즈를 order 단위로 변환한 align 값을 사용한다. 단 ioremap 최대 order 페이지 수 만큼으로 제한한다.
    • IOREMAP_MAX_ORDER
      • ARM32 pmd 단위(16M) 비트 수 => 24
      • ARM64 4K 페이지를 사용하는 경우 pud 단위(1G) 비트 수 => 30
      • ARM64 16K 페이지를 사용하는 경우 pmd 단위(32M) 비트 수 => 25
      • ARM64, 64K 페이지를 사용하는 경우 pmd 단위 (512M) 비트 수 => 29
  • 코드 라인 17~19에서 vm_struct를 할당한다.
  • 코드 라인 21~22에서 no guard 요청이 없으면 가드 페이지를 위해 1페이지를 추가한다.
  • 코드 라인 24~28에서 요청한 가상 주소 범위에서 빈 매핑 공간을 찾아 vmap_area를 할당 구성하고 RB트리 및 리스트에 insert한 후 엔트리 정보를 반환한다.
  • 코드 라인 30에서 vm_struct & vm_area 구조체를 구성한다.
  • 코드 라인 32에서 구성한 vm_struct 구조체 포인터를 반환한다.

 

공간 검색 후 vmap_area 할당

alloc_vmap_area()

mm/vmalloc.c -1/2-

/*
 * Allocate a region of KVA of the specified size and alignment, within the
 * vstart and vend.
 */
static struct vmap_area *alloc_vmap_area(unsigned long size,
                                unsigned long align,
                                unsigned long vstart, unsigned long vend,
                                int node, gfp_t gfp_mask)
{
        struct vmap_area *va;
        struct rb_node *n;
        unsigned long addr;
        int purged = 0;
        struct vmap_area *first;

        BUG_ON(!size);
        BUG_ON(offset_in_page(size));
        BUG_ON(!is_power_of_2(align));

        might_sleep();

        va = kmalloc_node(sizeof(struct vmap_area),
                        gfp_mask & GFP_RECLAIM_MASK, node);
        if (unlikely(!va))
                return ERR_PTR(-ENOMEM);

        /*
         * Only scan the relevant parts containing pointers to other objects
         * to avoid false negatives.
         */
        kmemleak_scan_area(&va->rb_node, SIZE_MAX, gfp_mask & GFP_RECLAIM_MASK);

retry:
        spin_lock(&vmap_area_lock);
        /*
         * Invalidate cache if we have more permissive parameters.
         * cached_hole_size notes the largest hole noticed _below_
         * the vmap_area cached in free_vmap_cache: if size fits
         * into that hole, we want to scan from vstart to reuse
         * the hole instead of allocating above free_vmap_cache.
         * Note that __free_vmap_area may update free_vmap_cache
         * without updating cached_hole_size or cached_align.
         */
        if (!free_vmap_cache ||
                        size < cached_hole_size ||
                        vstart < cached_vstart ||
                        align < cached_align) {
nocache:
                cached_hole_size = 0;
                free_vmap_cache = NULL;
        }
        /* record if we encounter less permissive parameters */
        cached_vstart = vstart;
        cached_align = align;

        /* find starting point for our search */
        if (free_vmap_cache) {
                first = rb_entry(free_vmap_cache, struct vmap_area, rb_node);
                addr = ALIGN(first->va_end, align);
                if (addr < vstart)
                        goto nocache;
                if (addr + size < addr)
                        goto overflow;

        } else {
                addr = ALIGN(vstart, align);
                if (addr + size < addr)
                        goto overflow;

                n = vmap_area_root.rb_node;
                first = NULL;

                while (n) {
                        struct vmap_area *tmp;
                        tmp = rb_entry(n, struct vmap_area, rb_node);
                        if (tmp->va_end >= addr) {
                                first = tmp;
                                if (tmp->va_start <= addr)
                                        break;
                                n = n->rb_left;
                        } else
                                n = n->rb_right;
                }

                if (!first)
                        goto found;
        }

요청한 가상 주소 범위에서 빈 공간을 찾아 va(vmap_area)를 할당 및 구성하고, RB트리 및 리스트에 insert한 후 va(vmap_area)를 반환한다.

  • vmap 캐시에서 먼저 검색하여 재사용할 수 있는지 확인한다.
    • 최종 등록한 vm 또는 최종 free한 vm의 이전(prev)vm부터 검색하면 빠른 성공을 기대할 수 있다.
  • 캐시에서 찾지 못한 경우 RB 트리로 구성된 전역 vmap_area_root에서 요청 시작 범위 바로 위에 있는 엔트리를 찾고
  • 이어서 리스트로 구성한 vmap_area_list에서 빈 공간을 찾는다.
  • 찾은 빈 공간에 별도로 메모리 할당 받은 vmap_area를 구성하고 insert 한다.
  • 만일 한 번의 검색에서 공간을 찾지 못하는 경우 해지를 유보(lazy)한 vmap_area를 flush한 후 다시 검색하여 공간을 찾는다.

 

  • 코드 라인 18~21에서 vmap_area 구조체를 구성하기 위해 reclaim 관련 플래그만 사용하여 할당을 받고 할당 에러인 경우 -ENOMEM을 반환한다.
  • 코드 라인 29~47에서 retry: 레이블이다. spin-lock을 얻고 캐시된 노드 위치를 사용할 수  없는 조건인 경우 이 번 검색에 캐시를 사용하지 못하게 한다. 조건은 다음과 같다.
    • 캐시 바로 이전(prev) 공간에 있는 hole이 새로 요청하는 size를 커버할 수 있는 경우
    • 시작 요청 범위가 캐시 사용 시의 요청 범위보다 작은 경우
    • 요청 align 값이 캐시된 align 값 보다 작은 경우
  • 코드 라인 53~59에서 free_vmap_cache 캐시가 가리키는 rb 노드를 first에 대입하고, 그 노드의 끝 주소를 addr에 대입하여 여기서 부터 검색할 준비를 한다.
    • 최종 등록하였거나 최근 free 시킨 va(vmap_area) 이전(prev) va를 보관한 free_vmap_cache에서 vm 엔트리를 가져온다.
    • 만일 first 엔트리의 끝 주소가 요청 범위를 벗어난 경우 캐시를 사용하지 않게 하기 위해 nocache 레이블로 이동한다.
    • 또한 first 엔트리의 끝 주소에 size를 더해서 범위를 초과한 경우 overflow 레이블로 이동한다.
  • 코드 라인 61~83에서 free_vmap_cache 캐시에 없는 경우 전역 vmap_area_root RB 트리를 통해 요청 범위에서 가장 첫 va를 찾아 first에 대입한다.
    • free_vmap_cache를 사용할 수 없는 경우 first 엔트리의 끝 주소에 size를 더해서 범위를 초과한 경우 overflow 레이블로 이동한다.

 

mm/vmalloc.c -2/2-

        /* from the starting point, walk areas until a suitable hole is found */
        while (addr + size > first->va_start && addr + size <= vend) {
                if (addr + cached_hole_size < first->va_start)
                        cached_hole_size = first->va_start - addr;
                addr = ALIGN(first->va_end, align);
                if (addr + size < addr)
                        goto overflow;

                if (list_is_last(&first->list, &vmap_area_list))
                        goto found;

                first = list_next_entry(first, list);
        }

found:
        if (addr + size > vend)
                goto overflow;

        va->va_start = addr;
        va->va_end = addr + size;
        va->flags = 0;
        __insert_vmap_area(va);
        free_vmap_cache = &va->rb_node;
        spin_unlock(&vmap_area_lock);

        BUG_ON(!IS_ALIGNED(va->va_start, align));
        BUG_ON(va->va_start < vstart);
        BUG_ON(va->va_end > vend);

        return va;

overflow:
        spin_unlock(&vmap_area_lock);
        if (!purged) {
                purge_vmap_area_lazy();
                purged = 1;
                goto retry;
        }

        if (gfpflags_allow_blocking(gfp_mask)) {
                unsigned long freed = 0;
                blocking_notifier_call_chain(&vmap_notify_list, 0, &freed);
                if (freed > 0) {
                        purged = 0;
                        goto retry;
                }
        }

        if (!(gfp_mask & __GFP_NOWARN) && printk_ratelimit())
                pr_warn("vmap allocation for size %lu failed: use vmalloc=<size> to increase size\n",
                        size);
        kfree(va);
        return ERR_PTR(-EBUSY);
}
  • 코드 라인 2~13에서 전역 first va(vmap_area)부터 리스트의 끝까지 요청 범위 내에서 size가 들어갈 수 있는 빈 공간을 찾는다.
  • 코드 라인 15~30에서 found: 레이블이다. 적절한 공간을 찾은 경우 RB 트리 및 리스트에 insert 하고, 영역을 반환한다.
  • 코드 라인 32~47에서 overflow: 레이블이다. 빈 공간을 찾을 수 없는 경우 lazy TLB flush 된 상태의 free 상태의 vm 엔트리들을 모두 purge 처리하여 삭제한 후 한 번만 다시 시도한다.

 

다음 그림은 매핑을 위해 요청 가상 주소 범위내에서 빈 공간을 찾을 때 먼저 free_vmap_cache 부터 size가 들어갈 빈공간을 검색하는 모습을 보여준다.

 

다음 그림은 매핑을 위해 요청 가상 주소 범위내에서 빈 공간을 찾을 때 RB 트리로 first vmap_area를 찾고 다시 리스트를 사용하여 size가 들어갈 빈공간을 검색하는 모습을 보여준다.

 

다음 그림은 free_vmap_cache와 cached_hole_size의 변화를 보여준다.

  • cached_hole_size는 캐시의 바로 앞 hole의 크기만을 기억한다.

 

vmap_area 추가

__insert_vmap_area()

mm/vmalloc.c

static void __insert_vmap_area(struct vmap_area *va)
{
        struct rb_node **p = &vmap_area_root.rb_node;
        struct rb_node *parent = NULL;
        struct rb_node *tmp;

        while (*p) {
                struct vmap_area *tmp_va;

                parent = *p;
                tmp_va = rb_entry(parent, struct vmap_area, rb_node);
                if (va->va_start < tmp_va->va_end)
                        p = &(*p)->rb_left;
                else if (va->va_end > tmp_va->va_start)
                        p = &(*p)->rb_right;
                else
                        BUG();
        }

        rb_link_node(&va->rb_node, parent, p);
        rb_insert_color(&va->rb_node, &vmap_area_root);

        /* address-sort this list */
        tmp = rb_prev(&va->rb_node);
        if (tmp) {
                struct vmap_area *prev;
                prev = rb_entry(tmp, struct vmap_area, rb_node);
                list_add_rcu(&va->list, &prev->list);
        } else
                list_add_rcu(&va->list, &vmap_area_list);
}

전역 vmap_area_root RB 트리와 전역 vmap_area_list에 vmap_area 엔트리를 insert 한다.

  • 코드 라인 7~18에서 vmap_area_root RB 트리에서 insert 할 leaf 노드를 찾는다.
  • 코드 라인 20~21에서 leaf 노드에 엔트리를 연결하고, RB 트리의 밸런스를 균형있게 맞춘다.
  • 코드 라인 24~30에서 마지막으로 rcu를 사용하여 vmap_area_list에 vmap_area 엔트리를 끼워 넣는다.
    • RB 트리에 insert한 엔트리를 RB 트리를 이용하여 rb_prev()를 사용하는 경우 바로 앞에 있는 노드를 알아내어 리스트 연결에 끼워넣을 수 있다.

 

다음 그림은 vmap_area 엔트리를 추가할 때의 모습을 보여준다.

 


vm_area 매핑

map_vm_area()

mm/vmalloc.c

int map_vm_area(struct vm_struct *area, pgprot_t prot, struct page **pages)
{
        unsigned long addr = (unsigned long)area->addr;
        unsigned long end = addr + get_vm_area_size(area);
        int err;

        err = vmap_page_range(addr, end, prot, pages);

        return err > 0 ? 0 : err;
}
EXPORT_SYMBOL_GPL(map_vm_area);

요청한 vm_struct 정보에 담긴 가상 주소 범위에 매핑한다.

 

get_vm_area_size()

include/linux/vmalloc.h

static inline size_t get_vm_area_size(const struct vm_struct *area)
{
        if (!(area->flags & VM_NO_GUARD))
                /* return actual size without guard page */
                return area->size - PAGE_SIZE;
        else
                return area->size;

}

영역이 사용하는 페이지 수를 반환한다.

 

vmap_page_range()

mm/vmalloc.c

static int vmap_page_range(unsigned long start, unsigned long end,
                           pgprot_t prot, struct page **pages)
{
        int ret;

        ret = vmap_page_range_noflush(start, end, prot, pages);
        flush_cache_vmap(start, end);
        return ret;
}

요청한 가상 주소 범위를 매핑하고 그 공간을 flush한다.

 

vmap_page_range_noflush()

mm/vmalloc.c

/*
 * Set up page tables in kva (addr, end). The ptes shall have prot "prot", and
 * will have pfns corresponding to the "pages" array.
 *
 * Ie. pte at addr+N*PAGE_SIZE shall point to pfn corresponding to pages[N]
 */
static int vmap_page_range_noflush(unsigned long start, unsigned long end,
                                   pgprot_t prot, struct page **pages)
{
        pgd_t *pgd;
        unsigned long next;
        unsigned long addr = start;
        int err = 0;
        int nr = 0;

        BUG_ON(addr >= end);
        pgd = pgd_offset_k(addr);
        do {
                next = pgd_addr_end(addr, end);
                err = vmap_p4d_range(pgd, addr, next, prot, pages, &nr);
                if (err)
                        return err;
        } while (pgd++, addr = next, addr != end);

        return nr;
}

요청 가상 주소 범위에 해당하는 커널 페이지 테이블을 **pages 와 속성 정보를 사용하여 매핑한다.

  • pgd -> p4d -> pud -> pmd -> pte 테이블 순으로 population해가며 마지막 pte 테이블의 해당 엔트리에 매핑한다.

 

flush_cache_vmap() – ARM32

arch/arm/include/asm/cacheflush.h()

/*
 * flush_cache_vmap() is used when creating mappings (eg, via vmap,
 * vmalloc, ioremap etc) in kernel space for pages.  On non-VIPT
 * caches, since the direct-mappings of these pages may contain cached
 * data, we need to do a full cache flush to ensure that writebacks
 * don't corrupt data placed into these pages via the new mappings.
 */
static inline void flush_cache_vmap(unsigned long start, unsigned long end)
{
        if (!cache_is_vipt_nonaliasing())
                flush_cache_all();
        else
                /*
                 * set_pte_at() called from vmap_pte_range() does not
                 * have a DSB after cleaning the cache line.
                 */
                dsb(ishst);
}

요청한 가상 주소 범위에 대해 flush를 한다.

  • 아키텍처가 pipt 캐시를 사용하고나 vipt nonaliasing을 지원하는 경우 flush를 할 필요가 없어서 성능이 크게 개선된다.

 

flush_cache_vmap() – ARM64

arch/arm64/include/asm/cacheflush.h

/*
 * Not required on AArch64 (PIPT or VIPT non-aliasing D-cache).
 */
static inline void flush_cache_vmap(unsigned long start, unsigned long end)
{
}

ARM64 에서는 vmap 매핑을 위해 캐시를 flush하지 않는다.

 

vm_struct 설정

setup_vmalloc_vm()

mm/vmalloc.c

static void setup_vmalloc_vm(struct vm_struct *vm, struct vmap_area *va,
                              unsigned long flags, const void *caller)
{
        spin_lock(&vmap_area_lock);
        vm->flags = flags;
        vm->addr = (void *)va->va_start;
        vm->size = va->va_end - va->va_start;
        vm->caller = caller;
        va->vm = vm;
        va->flags |= VM_VM_AREA;
        spin_unlock(&vmap_area_lock);
}

vm_struct 및 vmap_area에 정보를 설정한다.

 


vmap 매핑 해제

vunmap()

mm/vmalloc.c

/**
 *      vunmap  -  release virtual mapping obtained by vmap()
 *      @addr:          memory base address
 *
 *      Free the virtually contiguous memory area starting at @addr,
 *      which was created from the page array passed to vmap().
 *
 *      Must not be called in interrupt context.
 */
void vunmap(const void *addr)
{
        BUG_ON(in_interrupt());
        might_sleep();
        if (addr)
                __vunmap(addr, 0);
}
EXPORT_SYMBOL(vunmap);

vmap() 함수로 vmalloc 주소 공간에 매핑한 가상 주소 영역의 매핑을 해제한다. 다만 물리 페이지는 할당 해제하지 않는다.

 

다음 그림은 vunmap() 함수에 대해 연관 함수들과의 처리 흐름을 보여준다.

 

다음 그림은 vummap() 함수가 요청한 가상 주소로 vmap_area()를 찾아 그에 해당하는 매핑을 삭제하는 모습을 보여준다.

vunmap-1b

 

__vunmap()

mm/vmalloc.c

static void __vunmap(const void *addr, int deallocate_pages)
{
        struct vm_struct *area;

        if (!addr)
                return;

        if (WARN(!PAGE_ALIGNED(addr), "Trying to vfree() bad address (%p)\n",
                        addr))
                return;

        area = find_vmap_area((unsigned long)addr)->vm;
        if (unlikely(!area)) {
                WARN(1, KERN_ERR "Trying to vfree() nonexistent vm area (%p)\n",
                                addr);
                return;
        }

        debug_check_no_locks_freed(area->addr, get_vm_area_size(area));
        debug_check_no_obj_freed(area->addr, get_vm_area_size(area));

        remove_vm_area(addr);
        if (deallocate_pages) {
                int i;

                for (i = 0; i < area->nr_pages; i++) {
                        struct page *page = area->pages[i];

                        BUG_ON(!page);
                        __free_pages(page, 0);
                }

                kvfree(area->pages);
        }

        kfree(area);
        return;
}

요청 가상 주소로 vm 정보를 찾아 매핑을 제거하고 요청에 따라 각 페이지들을 해제하여 버디 시스템으로 돌려준다.

  • RB 트리 vmap_area_root에 등록되어 있는 vmap_area 정보에서 요청 가상 주소를  검색하여 매치된 vmap_area 및 vm_struct 정보를 제거하고 매핑을 해제한 다. 만일 @deallocate_pages 인수의 요청 여부에 따라 물리 페이지들을 해제한다.

 

  • 코드 라인 12~17에서 RB 트리 vmap_area_root에 등록되어 있는 vmap_area 정보에서 요청 가상 주소로 vm을 검색한다.
  • 코드 라인 22에서 vm을 RB 트리 및 리스트에서 제거하고, 매핑 해제 요청한 후 vm을 반환한다.
  • 코드 라인 23~34에서 @deallocate_pages 인수 요청이 설정된 경우 등록된 모든 페이지들을 해제하여 버디 시스템으로 돌려준다.
  • 코드 라인 36~37에서 vm_area 구조체 정보를 할당 해제한다.

 

vmap_area  삭제 및 매핑 해제 요청

remove_vm_area()

mm/vmalloc.c

/**
 *      remove_vm_area  -  find and remove a continuous kernel virtual area
 *      @addr:          base address
 *
 *      Search for the kernel VM area starting at @addr, and remove it.
 *      This function returns the found VM area, but using it is NOT safe
 *      on SMP machines, except for its size or flags.
 */
struct vm_struct *remove_vm_area(const void *addr)
{
        struct vmap_area *va;

        might_sleep();

        va = find_vmap_area((unsigned long)addr);
        if (va && va->flags & VM_VM_AREA) {
                struct vm_struct *vm = va->vm;

                spin_lock(&vmap_area_lock);
                va->vm = NULL;
                va->flags &= ~VM_VM_AREA;
                va->flags |= VM_LAZY_FREE;
                spin_unlock(&vmap_area_lock);

                kasan_free_shadow(vm);
                free_unmap_vmap_area(va);

                return vm;
        }
        return NULL;
}

요청 가상 주소를 RB 트리 vmap_area_root에 등록되어 있는 vmap_area 정보에서 검색하여 매치된 vmap_area 정보를 제거하고 매핑을 해제 요청한 후 vm_struct 정보를 알아온다.

  • 메모리 매핑은 해제하는데 vm_area는 VM_VM_AREA 플래그를 삭제하고 VM_LAZY_FREE 플래그를 추가하기만 한다.
  • 실제 삭제는 vmap_lazy_nr 갯수가 일정량을 초과하거나 메모리 부족 시 VM_LAZY_FREE 설정된 vma들을 한꺼번에 purge 처리한다.
    • vmalloc address space의 매핑이 해지되거나 수정되는 경우 모든 core에서 TLB 플러쉬가 발생되어야 하는데 이를 매 번 수행하는 경우 성능이 현저하게 저하되므로 삭제될 항목을 모아 두었다가  한꺼번에 삭제하는 방식을 취한다. 이를 Lazy TLB flushing이라 부른다.

 

 

vmap_area 검색

find_vmap_area()

mm/vmalloc.c

static struct vmap_area *find_vmap_area(unsigned long addr)
{
        struct vmap_area *va;

        spin_lock(&vmap_area_lock);
        va = __find_vmap_area(addr);
        spin_unlock(&vmap_area_lock);

        return va;
}

vmap_area lock으로 보호한 후 요청 가상 주소로 vmap_area 정보를 찾아온다. 못찾은 경우 null을 반환한다.

 

__find_vmap_area()

mm/vmalloc.c

static struct vmap_area *__find_vmap_area(unsigned long addr)
{
        struct rb_node *n = vmap_area_root.rb_node;

        while (n) {
                struct vmap_area *va;

                va = rb_entry(n, struct vmap_area, rb_node);
                if (addr < va->va_start)
                        n = n->rb_left;
                else if (addr >= va->va_end)
                        n = n->rb_right;
                else
                        return va;
        }

        return NULL;
}

요청 가상 주소로 vmap_area 정보를 찾아온다. 못찾은 경우 null을 반환한다.

  • 요청 가상 주소를 RB 트리 vmap_area_root에 등록되어 있는 vmap_area 정보에서 검색하여 매치된 vmap_area 정보를 찾아온다.

 


vmap_area 매핑 해제

free_unmap_vmap_area()

mm/vmalloc.c

/*
 * Free and unmap a vmap area
 */
static void free_unmap_vmap_area(struct vmap_area *va)
{
        flush_cache_vunmap(va->va_start, va->va_end);
        unmap_vmap_area(va);
        if (debug_pagealloc_enabled())
                flush_tlb_kernel_range(va->va_start, va->va_end);

        free_vmap_area_noflush(va);
}

아키텍처에 따라 지정된 가상 주소 범위의 데이타 캐시를 비운후 해당 영역의 매핑을 해제한다.

 

flush_cache_vunmap() – ARM32

arch/arm/include/asm/cacheflush.h

static inline void flush_cache_vunmap(unsigned long start, unsigned long end)
{
        if (!cache_is_vipt_nonaliasing())
                flush_cache_all();
}

아키텍처의 데이타 캐시가 vivt 타입이거나 vipt aliasing인 경우 캐시를 모두 비우게 한다.

  • 데이타 캐시가 pipt 타입이거나 vipt nonaliasing 타입인 경우 캐시를 비우지 않아도 되므로 성능이 향상된다.

 

flush_cache_vunmap() – ARM64

arch/arm64/include/asm/cacheflush.h

static inline void flush_cache_vunmap(unsigned long start, unsigned long end)
{
}

ARM64 에서는 vmap 매핑 해제를 위해 캐시를 flush하지 않는다.

 

free_unmap_vmap_area_noflush()

mm/vmalloc.c

/*
 * Free and unmap a vmap area, caller ensuring flush_cache_vunmap had been
 * called for the correct range previously.
 */
static void free_unmap_vmap_area_noflush(struct vmap_area *va)
{       
        unmap_vmap_area(va);
        free_vmap_area_noflush(va);
}

vmap_area가 사용하는 가상 주소 영역의 매핑을 커널 페이지 테이블에서 해제한다. 그런 후 vmap_area를 곧바로 삭제하지 않고 purge_list에 추가한다.

  • vmap_area가 재활용되는 경우 시간 소모가 큰 TLB 캐시를 flush 하지 않아도 되기 때문에 성능이 매우 좋아진다.

 

페이지 테이블 매핑 해제

unmap_vmap_area()

mm/vmalloc.c

/*
 * Clear the pagetable entries of a given vmap_area
 */
static void unmap_vmap_area(struct vmap_area *va)
{
        vunmap_page_range(va->va_start, va->va_end);
}

vmap_area의 가상 주소 영역의 매핑을 커널 페이지 테이블에서 해제한다.

 

vunmap_page_range()

mm/vmalloc.c

static void vunmap_page_range(unsigned long addr, unsigned long end)
{
        pgd_t *pgd;
        unsigned long next;

        BUG_ON(addr >= end);
        pgd = pgd_offset_k(addr);
        do {
                next = pgd_addr_end(addr, end);
                if (pgd_none_or_clear_bad(pgd))
                        continue;
                vunmap_p4d_range(pgd, addr, next);
        } while (pgd++, addr = next, addr != end);
}

요청 가상 주소 범위의 매핑을 커널 페이지 테이블에서 해제한다.

  • pgd -> p4d -> pud -> pmd -> pte 테이블 순으로 찾아가면 마지막 pte 테이블의 해당 엔트리를 언매핑한다.

 

lazy TLB Flush 요청

free_vmap_area_noflush()

mm/vmalloc.c

/*
 * Free a vmap area, caller ensuring that the area has been unmapped
 * and flush_cache_vunmap had been called for the correct range
 * previously.
 */
static void free_vmap_area_noflush(struct vmap_area *va)
{
        int nr_lazy;

        nr_lazy = atomic_add_return((va->va_end - va->va_start) >> PAGE_SHIFT,
                                    &vmap_lazy_nr);

        /* After this point, we may free va at any time */
        llist_add(&va->purge_list, &vmap_purge_list);

        if (unlikely(nr_lazy > lazy_max_pages()))
                try_purge_vmap_area_lazy();
}

vmap_area를 곧바로 삭제하지 않고 VM_LAZY_FREE 플래그를 설정하여 lazy TLB 플러시 요청한다.  그 후 페이지 수가 일정량을 초과하는 경우 purge 처리를 수행한다.

lazy_max_pages()

mm/vmalloc.c

/*
 * lazy_max_pages is the maximum amount of virtual address space we gather up
 * before attempting to purge with a TLB flush.
 *
 * There is a tradeoff here: a larger number will cover more kernel page tables
 * and take slightly longer to purge, but it will linearly reduce the number of
 * global TLB flushes that must be performed. It would seem natural to scale
 * this number up linearly with the number of CPUs (because vmapping activity
 * could also scale linearly with the number of CPUs), however it is likely
 * that in practice, workloads might be constrained in other ways that mean
 * vmap activity will not scale linearly with CPUs. Also, I want to be
 * conservative and not introduce a big latency on huge systems, so go with
 * a less aggressive log scale. It will still be an improvement over the old
 * code, and it will be simple to change the scale factor if we find that it
 * becomes a problem on bigger systems.
 */
static unsigned long lazy_max_pages(void)
{
        unsigned int log;

        log = fls(num_online_cpus());

        return log * (32UL * 1024 * 1024 / PAGE_SIZE);
}

TLB lazy된 페이지들의 purge 처리를 위해 필요한 페이지 수를 산출한다.

  • 32M에 해당하는 페이지 수 * log2(online cpu) + 1에 비례하는 페이지 수를 반환한다.
  • cpu가 많아지는 경우 TLB flush는 시스템의 전체적인 성능을 떨어뜨리므로 cpu 수가 많아질 수록 lazy_max_pages 수는 더 커져야 한다.

 

lazy TLB vmap_area들의 Purge 처리

try_purge_vmap_area_lazy()

mm/vmalloc.c

/*
 * Kick off a purge of the outstanding lazy areas. Don't bother if somebody
 * is already purging.
 */
static void try_purge_vmap_area_lazy(void)
{
        if (mutex_trylock(&vmap_purge_lock)) {
                __purge_vmap_area_lazy(ULONG_MAX, 0);
                mutex_unlock(&vmap_purge_lock);
        }
}

Lazy TLB 플러시 요청된 vmap_area들을 제거하고 전체 가상 주소 범위의 TLB flush를 수행한다.

 

__purge_vmap_area_lazy()

mm/vmalloc.c

/*
 * Purges all lazily-freed vmap areas.
 */
static bool __purge_vmap_area_lazy(unsigned long start, unsigned long end)
{
        struct llist_node *valist;
        struct vmap_area *va;
        struct vmap_area *n_va;
        bool do_free = false;

        lockdep_assert_held(&vmap_purge_lock);

        valist = llist_del_all(&vmap_purge_list);
        llist_for_each_entry(va, valist, purge_list) {
                if (va->va_start < start)
                        start = va->va_start;
                if (va->va_end > end)
                        end = va->va_end;
                do_free = true;
        }

        if (!do_free)
                return false;

        flush_tlb_kernel_range(start, end);

        spin_lock(&vmap_area_lock);
        llist_for_each_entry_safe(va, n_va, valist, purge_list) {
                int nr = (va->va_end - va->va_start) >> PAGE_SHIFT;

                __free_vmap_area(va);
                atomic_sub(nr, &vmap_lazy_nr);
                cond_resched_lock(&vmap_area_lock);
        }
        spin_unlock(&vmap_area_lock);
        return true;
}

Lazy TLB 플러시 요청된 vmap_area들을 모두 제거하고 @start ~ @end 범위의 TLB flush를 수행한다.

  • 코드 라인 10~17에서 purge 리스트에 있는 vmap_area 들의 최초 시작 주소와 마지막 끝 주소를 반영하여 flush할 시작 주소와 끝 주소를 갱신한다.
  • 코드 라인 22에서 갱신된 start ~ end 범위의 가상 주소 영역에 대해 TLB 플러시를 수행한다.
  • 코드 라인 24~32에서 purge 리스트에 있는 모든 vmap_area들을 할당 해제한다.
  • 코드 라인 33에서 성공 true를 반환한다.

 

vmap_area 삭제

__free_vmap_area()

mm/vmalloc.c

static void __free_vmap_area(struct vmap_area *va)
{
        BUG_ON(RB_EMPTY_NODE(&va->rb_node));

        if (free_vmap_cache) {
                if (va->va_end < cached_vstart) {
                        free_vmap_cache = NULL;
                } else {
                        struct vmap_area *cache;
                        cache = rb_entry(free_vmap_cache, struct vmap_area, rb_node);
                        if (va->va_start <= cache->va_start) {
                                free_vmap_cache = rb_prev(&va->rb_node);
                                /*
                                 * We don't try to update cached_hole_size or
                                 * cached_align, but it won't go very wrong.
                                 */
                        }
                }
        }
        rb_erase(&va->rb_node, &vmap_area_root);
        RB_CLEAR_NODE(&va->rb_node);
        list_del_rcu(&va->list);

        /*
         * Track the highest possible candidate for pcpu area
         * allocation.  Areas outside of vmalloc area can be returned
         * here too, consider only end addresses which fall inside
         * vmalloc area proper.
         */
        if (va->va_end > VMALLOC_START && va->va_end <= VMALLOC_END)
                vmap_area_pcpu_hole = max(vmap_area_pcpu_hole, va->va_end);

        kfree_rcu(va, rcu_head);
}

요청한 vmap_area를 RB 트리 vmap_area_root와 vmap_area_list에서 제거한 후 해제한다.

 

참고

 

Vmalloc

<kernel v5.0>

Vmalloc 할당자

커널에서 주로 큰 사이즈의 연속된 가상 주소 공간을 할당 받아 사용한다. 물리적으로 연속되지 않는 공간이므로 dma 버퍼로는 사용할 수 없다.

 

특징

가상 주소가 연속된 큰 사이즈의 커널 메모리의 할당이 필요한 경우 사용된다. vmalloc을 이용한 커널 메모리의 할당은 다음과 같은 특징이 있다.

  • 메모리를 할당할 때마다 vmalloc 가상 주소 공간에 매핑하여 사용할 수 있으므로 매핑/해제에 cost가 많이 소모된다.
  • vmalloc 가상 주소 공간에 매핑하는 메모리 페이지는 버디 시스템을 사용하는 페이지 할당자로 부터 필요한 만큼 order 0인 싱글 페이지만을 할당받아 사용하므로 fragment 관리에 매우 적합하다.
  • 물리적으로 연속된 메모리를 사용하지 않으므로 DMA 용으로 사용될 수 없다.
    • 참고: iommu 장치를 사용하여 dynamic 매핑을 하는 경우 물리적으로 연속되지 않은 메모리에 대해 디바이스가 이 영역을 dma 버퍼로 사용할 방법은 있다. 현재는 모바일 시스템에서 gpu 등의 디바이스가 arm社의 smmu(iommu)를 사용하고 있고, 점점 그 수가 늘어날 전망이다.

 

API

할당 및 해제 관련한 주요 API는 다음과 같다.

  • vmalloc()
  • vfree()

 

vmalloc 가상 주소 공간

버디 시스템을 사용하는 페이지 할당자로 부터 vmalloc() 함수가 요청한 size가 들어갈 수 있을만큼 싱글 페이지들을 할당받아 이를 모아 vmalloc 가상 주소 공간의 빈 공간을 찾아 각 싱글 페이지를 순차적으로 빈 자리에 매핑하고 그 매핑된 가상 주소를 반환한다.

 

다음 그림은 vmalloc 가상 주소 공간의 위치를 보여준다.

 

vmalloc() 함수를 통해 요청한 사이즈가 들어갈 수 있는 싱글 페이지들을 가져와 vmalloc 가상 주소 영역의 빈자리를 찾아 연속되도록 한꺼번에 매핑하는 모습을 보여준다.

 


vmalloc 초기화

커널이 사용하는 연속된 가상 주소 메모리를 할당 받는 메커니즘을 위해 초기화를 수행한다.

  • vmalloc() & vfree()
    • 연속된 가상 주소 메모리 할당과 메모리 해제
  • vmap() & vunmap()
    • 가상 주소 공간에 페이지를 매핑과 해제
      • 현재 이용할 수 있는 가상 주소 공간으로 vmalloc 가상 주소 공간과 module 가상 주소 공간이 있다.

 

다음 그림은 vmalloc_init() 함수의 처리 흐름을 보여준다.

vmalloc_init-1

 

vmalloc_init()

mm/vmalloc.c

void __init vmalloc_init(void)
{
        struct vmap_area *va;
        struct vm_struct *tmp;
        int i;

        for_each_possible_cpu(i) {
                struct vmap_block_queue *vbq;
                struct vfree_deferred *p;

                vbq = &per_cpu(vmap_block_queue, i);
                spin_lock_init(&vbq->lock);
                INIT_LIST_HEAD(&vbq->free);
                p = &per_cpu(vfree_deferred, i);
                init_llist_head(&p->list);
                INIT_WORK(&p->wq, free_work);
        }

        /* Import existing vmlist entries. */
        for (tmp = vmlist; tmp; tmp = tmp->next) {
                va = kzalloc(sizeof(struct vmap_area), GFP_NOWAIT);
                va->flags = VM_VM_AREA;
                va->va_start = (unsigned long)tmp->addr;
                va->va_end = va->va_start + tmp->size; 
                va->vm = tmp;
                __insert_vmap_area(va);
        }

        vmap_area_pcpu_hole = VMALLOC_END;

        vmap_initialized = true;
}

vmalloc 공간을 이용할 수 있도록 초기화한다.

  • 코드 라인 7~17에서 possible cpu 수 만큼 루프를 돌며 per-cpu vmap_block_queue 및 per-cpu vfree_deferred를 초기화한다.
    • per-cpu vmap_block_queue
      • 할당 및 flushing 목적으로 free 및 dirty vmap block 큐로 사용된다.
    • per-cpu vfree_deferred
      • 인터럽트 처리 중에 vfree() 처리를 지연시킬 목적으로 사용되는 대기 리스크
  • 코드 라인 20~27에서 전역 vmlist에 등록되어 있는 수 만큼 vmap_area 구조체를 할당 받아 초기화하여 vmap_area에 추가한다.
    • vmlist
      • vm_area_register_early() 함수를 통해 vm이 등록되는데 pcpu_page_first_chunk()를 만들 때 사용된다.
        • 그 외 x86에서 xen ops 드라이버에서 호출 될때에도 사용된다.
  • 코드 라인 29~31에서 per-cpu가 vmalloc 공간의 최상단부터 아래 방향으로 사용될 예정이다. vmap을 사용할 준비가 되었음을 알린다.

 


vmalloc 할당

vmalloc()

mm/vmalloc.c

/**
 *      vmalloc  -  allocate virtually contiguous memory
 *      @size:          allocation size
 *      Allocate enough pages to cover @size from the page level
 *      allocator and map them into contiguous kernel virtual space.
 *
 *      For tight control over page level allocator and protection flags
 *      use __vmalloc() instead.
 */
void *vmalloc(unsigned long size)
{
        return __vmalloc_node_flags(size, NUMA_NO_NODE,
                                    GFP_KERNEL);
}
EXPORT_SYMBOL(vmalloc);

커널을 위해 @size 만큼의 연속된 가상 주소 공간을 할당받는다.  __vmalloc_node_flags() 함수를 이어 호출한다.

 

다음 그림은 vmalloc() 함수와 관련 함수들간의 처리 흐름을 보여준다.

 

__vmalloc_node_flags()

mm/vmalloc.c

static inline void *__vmalloc_node_flags(unsigned long size,
                                        int node, gfp_t flags)
{
        return __vmalloc_node(size, 1, flags, PAGE_KERNEL,
                                        node, __builtin_return_address(0));
}

커널을 위해 요청 노드에서 연속된 가상 메모리를 할당한다.

 

__vmalloc_node()

mm/vmalloc.c

/**
 *      __vmalloc_node  -  allocate virtually contiguous memory
 *      @size:          allocation size
 *      @align:         desired alignment
 *      @gfp_mask:      flags for the page level allocator
 *      @prot:          protection mask for the allocated pages
 *      @node:          node to use for allocation or NUMA_NO_NODE
 *      @caller:        caller's return address
 *
 *      Allocate enough pages to cover @size from the page level
 *      allocator with @gfp_mask flags.  Map them into contiguous
 *      kernel virtual space, using a pagetable protection of @prot.
 *
 *      Reclaim modifiers in @gfp_mask - __GFP_NORETRY, __GFP_RETRY_MAYFAIL
 *      and __GFP_NOFAIL are not supported
 *
 *      Any use of gfp flags outside of GFP_KERNEL should be consulted
 *      with mm people.
 *
 */
static void *__vmalloc_node(unsigned long size, unsigned long align,
                            gfp_t gfp_mask, pgprot_t prot,
                            int node, const void *caller)
{
        return __vmalloc_node_range(size, align, VMALLOC_START, VMALLOC_END,
                                gfp_mask, prot, 0, node, caller);
}

커널을 위해 @node에서 연속된 가상 메모리를 할당하되 가상 주소는 VMALLOC address space의 빈 공간을 사용하여 가상 주소를 매핑하게 한다.

 

__vmalloc_node_range()

mm/vmalloc.c

/**
 *      __vmalloc_node_range  -  allocate virtually contiguous memory
 *      @size:          allocation size
 *      @align:         desired alignment
 *      @start:         vm area range start
 *      @end:           vm area range end
 *      @gfp_mask:      flags for the page level allocator
 *      @prot:          protection mask for the allocated pages
 *      @vm_flags:      additional vm area flags (e.g. %VM_NO_GUARD)
 *      @node:          node to use for allocation or NUMA_NO_NODE
 *      @caller:        caller's return address
 *
 *      Allocate enough pages to cover @size from the page level
 *      allocator with @gfp_mask flags.  Map them into contiguous
 *      kernel virtual space, using a pagetable protection of @prot.
 */
void *__vmalloc_node_range(unsigned long size, unsigned long align,
                        unsigned long start, unsigned long end, gfp_t gfp_mask,
                        pgprot_t prot, unsigned long vm_flags, int node,
                        const void *caller)
{
        struct vm_struct *area;
        void *addr;
        unsigned long real_size = size;

        size = PAGE_ALIGN(size);
        if (!size || (size >> PAGE_SHIFT) > totalram_pages)
                goto fail;

        area = __get_vm_area_node(size, align, VM_ALLOC | VM_UNINITIALIZED |
                                vm_flags, start, end, node, gfp_mask, caller);
        if (!area)
                goto fail;

        addr = __vmalloc_area_node(area, gfp_mask, prot, node);
        if (!addr)
                return NULL;

        /*
         * In this function, newly allocated vm_struct has VM_UNINITIALIZED
         * flag. It means that vm_struct is not fully initialized.
         * Now, it is fully initialized, so remove this flag here.
         */
        clear_vm_uninitialized_flag(area);

        /*
         * A ref_count = 2 is needed because vm_struct allocated in
         * __get_vm_area_node() contains a reference to the virtual address of
         * the vmalloc'ed block.
         */
        kmemleak_vmalloc(area, size, gfp_mask);

        return addr;

fail:
        warn_alloc_failed(gfp_mask, NULL,
                          "vmalloc: allocation failure: %lu bytes\n", real_size);
        return NULL;
}

요청 노드에서 연속된 가상 메모리를 할당하되 가상 주소는 지정된 범위 이내의 빈 공간을 사용한 가상 주소를 매핑하게 한다.

  • 코드 라인 10~12에서 size를 페이지 단위로 정렬하고 그 size가 0이거나 전체 메모리보다 큰 경우 fail 레이블을 경유해 null을 반환한다.
  • 코드 라인 14~17에서 요청 가상 주소 범위에서 요청 size가 들어갈 수 있는 빈 자리를 찾아 그 가상 주소로 vmap_area와 vm_struct 정보를 구성하여 반환한다.
    • 참고: Vmap | 문c
  • 코드 라인 19~21에서 vm_struct 정보가 요청하는 가상 주소 영역 만큼 page descriptor 테이블을 할당받고 order 0 페이지들을 요청 수 만큼 할당하여 연결하고  페이지 테이블에 매핑한다.
  • 코드 라인 28에서 vm에 대해 uninitialized 플래그를 클리어하여 vm이 초기화 되었음을 나타낸다.
  • 코드 라인 37에서 할당한 가상 주소 공간을 반환한다.

 

다음 그림은 vmap_area와 vm_struct가 할당받아 구성되고 필요한 물리 페이지 수 만큼 page descriptor 배열을 할당 받고 그 수 만큼 order 0 페이지들을 할당받아 연결하고 매핑되는 모습을 보여준다.

 

__vmalloc_area_node()

mm/vmalloc.c

static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
                                 pgprot_t prot, int node)
{
        struct page **pages;
        unsigned int nr_pages, array_size, i;
        const gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO;
        const gfp_t alloc_mask = gfp_mask | __GFP_NOWARN;
        const gfp_t highmem_mask = (gfp_mask & (GFP_DMA | GFP_DMA32)) ?
                                        0 :
                                        __GFP_HIGHMEM;

        nr_pages = get_vm_area_size(area) >> PAGE_SHIFT;
        array_size = (nr_pages * sizeof(struct page *));

        area->nr_pages = nr_pages;
        /* Please note that the recursion is strictly bounded. */
        if (array_size > PAGE_SIZE) {
                pages = __vmalloc_node(array_size, 1, nested_gfp|highmem_mask,
                                PAGE_KERNEL, node, area->caller);
        } else {
                pages = kmalloc_node(array_size, nested_gfp, node);
        }
        area->pages = pages;
        if (!area->pages) {
                remove_vm_area(area->addr);
                kfree(area);
                return NULL;
        }

        for (i = 0; i < area->nr_pages; i++) {
                struct page *page;

                if (node == NUMA_NO_NODE)
                        page = alloc_page(alloc_mask|highmem_mask);
                else
                        page = alloc_pages_node(node, alloc_mask|highmem_mask, 0);

                if (unlikely(!page)) {
                        /* Successfully allocated i pages, free them in __vunmap() */
                        area->nr_pages = i;
                        goto fail;
                }
                area->pages[i] = page;
                if (gfpflags_allow_blocking(gfp_mask|highmem_mask))
                        cond_resched();
        }

        if (map_vm_area(area, prot, pages))
                goto fail;
        return area->addr;

fail:
        warn_alloc(gfp_mask, NULL,
                          "vmalloc: allocation failure, allocated %ld of %ld bytes",
                          (area->nr_pages*PAGE_SIZE), area->size);
        vfree(area->addr);
        return NULL;
}

vm_struct 정보가 요청하는 가상 주소 영역 만큼 page 디스크립터 배열을 할당받고 싱글 페이지들을 요청 수 만큼 할당하여 연결하고  페이지 테이블에 매핑한다.

  • 코드 라인 6에서 페이지 회수와 관련된 플래그만 남기고 __GFP_ZERO를 추가한다.
  • 코드 라인 7에서 gfp_mask에 __GFP_NOWARN을 추가한다.
  • 코드 라인 8~10에서 dma 및 dma32 존에 대한 요청이 없는 경우 highmem 존 마스크를 준비한다.
  • 코드 라인 12에서 영역이 사용하는 페이지 수를 알아오고 만들 page descriptor들이 사용할 배열의 크기를 구한다.
  • 코드 라인 15에서 vm에 사용될 페이지 수를 기록한다.
  • 코드 라인 17~19에서 페이지 디스크립터 배열 할당을 위한 array_size가 1 페이지를 초과하는 경우 해당 노드의 highmem을 포함한 zone에서 array_size 만큼의 공간을 할당받는다.
    • vmalloc() 함수가 진행 중에 nest되어 호출되는 상황이다.
    • area의 플래그 정보에 VM_VPAGES를 설정하여 할당 받은 page descriptor 배열이 있다는 것을 나타낸다.
  • 코드 라인 20~22에서 array_size가 array_size가 1페이지 이내인 경우 kmalloc_node() 함수를 사용하여 슬랩 object를 할당받아 page 디스크립터 배열을 구성하게 한다.
  • 코드 라인 23~28에서 area가 사용하는 페이지 디스크립터 배열을 가리키게 한다.(vm 전용 mem_map)
  • 코드 라인 30~46에서 페이지 수 만큼 루프를 돌며 버디 시스템을 사용하는 페이지 할당자로 부터 1개의 싱글 페이지를 할당 받고, 페이지 디스크립터 배열에 할당 받은 각 페이지를 연결한다.
  • 코드 라인 48~50에서 area의 매핑을 수행한 후 그 가상 주소를 반환한다. 만일 실패하는 경우 fail 레이블로 이동한다.

 

clear_vm_uninitialized_flag()

mm/vmalloc.c

static void clear_vm_uninitialized_flag(struct vm_struct *vm)
{
        /*
         * Before removing VM_UNINITIALIZED,
         * we should make sure that vm has proper values.
         * Pair with smp_rmb() in show_numa_info().
         */
        smp_wmb();
        vm->flags &= ~VM_UNINITIALIZED;
}

vm 설정이 완료되었음을 나타내기 위해 VM_UNINITIALIZED 플래그를 제거한다.

 


vmalloc 할당 해제

vfree()

mm/vmalloc.c

/**
 *      vfree  -  release memory allocated by vmalloc()
 *      @addr:          memory base address
 *
 *      Free the virtually continuous memory area starting at @addr, as
 *      obtained from vmalloc(), vmalloc_32() or __vmalloc(). If @addr is
 *      NULL, no operation is performed.
 *
 *      Must not be called in NMI context (strictly speaking, only if we don't
 *      have CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG, but making the calling
 *      conventions for vfree() arch-depenedent would be a really bad idea)
 *
 *      May sleep if called *not* from interrupt context.
 *
 *      NOTE: assumes that the object at @addr has a size >= sizeof(llist_node)
 */
void vfree(const void *addr)
{
        BUG_ON(in_nmi());

        kmemleak_free(addr);

        might_sleep_if(!in_interrupt());

        if (!addr)
                return;
        if (unlikely(in_interrupt()))
                __vfree_deferred(addr);
        else
                __vunmap(addr, 1);
}
EXPORT_SYMBOL(vfree);

vmalloc()에 의해 할당되고 매핑된 연속된 가상 주소 메모리를 해제한다.

  • 인터럽트 핸들러를 통해 호출되는 경우 당장 매핑된 연속된 가상 주소 메모리를 해제할 수 없으므로 지연 처리를 위해 per-cpu vfree_deferred에 추가한 후 워크큐에 등록된 free_work() 함수를 스케쥴 한다.

 

다음 그림은 vfree() 함수와 관련 함수의 흐름을 보여준다.

 

free_work()

mm/vmalloc.c

static void free_work(struct work_struct *w)
{
        struct vfree_deferred *p = container_of(w, struct vfree_deferred, wq);
        struct llist_node *t, *llnode;

        llist_for_each_safe(llnode, t, llist_del_all(&p->list))
                __vunmap((void *)llnode, 1);
}

per-cpu vfree_deferred 리스트에 있는 모든 vm(연속된 가상 주소에 매핑된 메모리)들을 해제한다.

 

참고