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()

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(연속된 가상 주소에 매핑된 메모리)들을 해제한다.

 

참고

• Kmalloc vs Vmalloc | 문c
• Kmalloc | 문c
• Vmalloc | 문c – 현재 글
• Vmap() | 문c

 

• Red–black tree | wikipedia
• Reworking vmap() | LWN.net
• mm: rewrite vmap layer
• mm:rewrite vmap layer | Barrios
• Red/Black Tree Visualization