Virtual Memory: vmalloc(), vm_map_ram() 분석

vmalloc(), vfree()란

커널에는 메모리를 할당하는 다양한 방법이 있다. 페이지 할당자는 물리적으로 연속적인 페이지 프레임을 할당하며, 슬랩 할당자는 order-n 페이지 하나를 같은 크기로 쪼개서 슬랩 객체를 할당한다. 페이지 할당자와 슬랩 모두 물리적으로 연속적인 메모리를 할당한다. 다만 물리 주소로 접근하지는 않고, direct map 영역의 주소를 사용하여 접근한다.

하지만 항상 물리적으로 연속적인 메모리를 할당할 수는 없는데, 할당하려는 메모리의 크기가 클 수록, 메모리가 단편화될 수록 물리적으로 연속적인 메모리를 할당하기가 어려워진다. vmalloc()은 물리적으로 연속적인 메모리를 할당하는 대신, 물리적으로 흩어진 메모리들을 가상 주소 상으로 연속적이도록 페이지 테이블을 초기화한다. vmalloc()으로 할당된 객체는 direct map 영역이 아니라 vmalloc 전용의 가상 주소 공간을 사용한다. [x86_64 memory map, kernel doc]

vmalloc()은 가상 주소 상으로 연속된 메모리를 할당하는 함수, vfree()는 vmalloc()으로 할당한 객체를 해제하는 함수이다. 당연하게도 이 함수들은 물리적으로 연속된 메모리가 필요할 때는 사용해서는 안된다.

vmap(), vunmap()

vmalloc이 1) 메모리를 할당하고 2) 할당된 메모리가 가상 주소 공간 상으로 연속되도록 매핑 하는 기능이라면, vmap()은 이미 할당된 메모리에 대하여 2)만 수행한다. vunmap()은 vmap()으로 생성했던 매핑을 제거한다.

들어가기 전에

이 글에서는 vmalloc 서브시스템에서 사용하는 자료구조를 살펴본 후, vmalloc(), vfree()의 큰 그림을 먼저 살펴본다. 그 다음 vmalloc에서 알아야 할 주제들을 (lazy TLB flushing, huge vmalloc mapping, direct map reset) 간단하게 언급하고 top-down 방식으로 코드를 분석한다. kmemleak이나 KASAN에 관하여는 자세히 다루지 않는다.

자료구조

vmap_area, vm_struct

struct vmap_area {
	unsigned long va_start;
	unsigned long va_end;

	struct rb_node rb_node;         /* address sorted rbtree */
	struct list_head list;          /* address sorted list */

	/*
	 * The following two variables can be packed, because
	 * a vmap_area object can be either:
	 *    1) in "free" tree (root is free_vmap_area_root)
	 *    2) or "busy" tree (root is vmap_area_root)
	 */
	union {
		unsigned long subtree_max_size; /* in "free" tree */
		struct vm_struct *vm;           /* in "busy" tree */
	};
};

vmap_area는 vmalloc, vmap, ioremap 등의 API에서 사용하는 가상 주소 공간을 관리하기 위한 용도이다. vmap_area는 linked list와 red-black tree로 동시에 관리되며, vmap_area가 할당된 공간을 나타내는 경우 vmap_area_root/vmap_area_list에 존재하며, 해제된 공간을 나타내는 경우 free_map_area_root/free_vmap_area_list에 존재한다.

static DEFINE_SPINLOCK(vmap_area_lock);
static DEFINE_SPINLOCK(free_vmap_area_lock);
/* Export for kexec only */
LIST_HEAD(vmap_area_list);
static struct rb_root vmap_area_root = RB_ROOT;
static bool vmap_initialized __read_mostly;

/*
 * This linked list is used in pair with free_vmap_area_root.
 * It gives O(1) access to prev/next to perform fast coalescing.
 */
static LIST_HEAD(free_vmap_area_list);

/*
 * This augment red-black tree represents the free vmap space.
 * All vmap_area objects in this tree are sorted by va->va_start
 * address. It is used for allocation and merging when a vmap
 * object is released.
 *
 * Each vmap_area node contains a maximum available free block
 * of its sub-tree, right or left. Therefore it is possible to
 * find a lowest match of free area.
 */
static struct rb_root free_vmap_area_root = RB_ROOT;

static struct rb_root purge_vmap_area_root = RB_ROOT;
static LIST_HEAD(purge_vmap_area_list);
static DEFINE_SPINLOCK(purge_vmap_area_lock);

/*
 * This kmem_cache is used for vmap_area objects. Instead of
 * allocating from slab we reuse an object from this cache to
 * make things faster. Especially in "no edge" splitting of
 * free block.
 */
static struct kmem_cache *vmap_area_cachep;

purge_vmap_area_list와 purge_vmap_area_root는 flush할 vmap_area의 목록을 저장해두었다가 한꺼번에 처리하는 용도이다.

struct vm_struct {
	struct vm_struct	*next;
	void			*addr;
	unsigned long		size;
	unsigned long		flags;
	struct page		**pages;
#ifdef CONFIG_HAVE_ARCH_HUGE_VMALLOC
	unsigned int		page_order;
#endif
	unsigned int		nr_pages;
	phys_addr_t		phys_addr;
	const void		*caller;
};

vmap_area는 주소 공간에 대한 정보만 갖고있다. 반면 vm_struct는 vmap_area가 사용중일 때, 할당된 물리 메모리에 관한 정보를 담는 용도이다.

vmap_block, vmap_block_queue

#define VMALLOC_PAGES		(VMALLOC_SPACE / PAGE_SIZE)
#define VMAP_MAX_ALLOC		BITS_PER_LONG	/* 256K with 4K pages */
#define VMAP_BBMAP_BITS_MAX	1024	/* 4MB with 4K pages */
#define VMAP_BBMAP_BITS_MIN	(VMAP_MAX_ALLOC*2)
#define VMAP_MIN(x, y)		((x) < (y) ? (x) : (y)) /* can't use min() */
#define VMAP_MAX(x, y)		((x) > (y) ? (x) : (y)) /* can't use max() */
#define VMAP_BBMAP_BITS		\
		VMAP_MIN(VMAP_BBMAP_BITS_MAX,	\
		VMAP_MAX(VMAP_BBMAP_BITS_MIN,	\
			VMALLOC_PAGES / roundup_pow_of_two(NR_CPUS) / 16))

#define VMAP_BLOCK_SIZE		(VMAP_BBMAP_BITS * PAGE_SIZE)

struct vmap_block_queue {
	spinlock_t lock;
	struct list_head free;
};

struct vmap_block {
	spinlock_t lock;
	struct vmap_area *va;
	unsigned long free, dirty;
	unsigned long dirty_min, dirty_max; /*< dirty range */
	struct list_head free_list;
	struct rcu_head rcu_head;
	struct list_head purge;
};

vmap_block은 크기가 VMAP_BLOCK_SIZE인 vmap_area를 쪼개서 사용하기 위한 구조체이다. vmap_block_queue는 여러 개의 vmap_block을 저장하는 큐이며 CPU별로 존재한다.

vmap_block을 처음 할당하면 VMAP_BLOCK_SIZE 만큼의 가상 주소 공간이 free 상태이다. free는 단위가 페이지의 수이므로 VMAP_BBMAP_BITS 만큼의 free 페이지가 존재한다. dirty는 사용이 끝난 후 아직 TLB에서 flush하지 않은 페이지의 수인데, 처음에는 0이다. dirty_min, dirty_max는 vmap_block 내에서 dirty한 페이지들의 범위를 나타낸다.

/*
 * XArray of vmap blocks, indexed by address, to quickly find a vmap block
 * in the free path. Could get rid of this if we change the API to return a
 * "cookie" from alloc, to be passed to free. But no big deal yet.
 */
static DEFINE_XARRAY(vmap_blocks);

vmap_block들은 연결 리스트로 연결되어있지만, vmap_block을 해제할 때는 이 리스트를 순회하는 대신 vmap_blocks라는 xarray가 주소를 해당하는 vmap_block으로 변환한다.

vmalloc_init()

vmalloc_init()은 메모리 서브시스템을 초기화할 때 호출되며, vmalloc은 페이지 할당자와 슬랩 할당자가 초기된 이후에 초기화된다.

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

	/*
	 * Create the cache for vmap_area objects.
	 */
	vmap_area_cachep = KMEM_CACHE(vmap_area, SLAB_PANIC);

vmap_area 할당을 위한 캐시를 만든다.

	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);
	}

CPU별 자료구조를 초기화한다. vmap_block_queue는 CPU별로 사용 가능한 vmap_block을 관리하며, vfree_deferred는 atomic context에서 바로 free하지 않고 work queue를 통해서 free하는 데 사용된다.

	/* Import existing vmlist entries. */
	for (tmp = vmlist; tmp; tmp = tmp->next) {
		va = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT);
		if (WARN_ON_ONCE(!va))
			continue;

		va->va_start = (unsigned long)tmp->addr;
		va->va_end = va->va_start + tmp->size;
		va->vm = tmp;
		insert_vmap_area(va, &vmap_area_root, &vmap_area_list);
	}

vmalloc은 개별 서브시스템 혹은 아키텍처가 vmap_area를 별도로 등록할 필요가 있는 경우 vm_area_register_early()나 vm_area_add_early()로 등록하도록 하며, 그렇게 등록한 영역들을 위 코드를 통해서 vmap_area_root/vmap_area_list에 삽입한다.

	/*
	 * Now we can initialize a free vmap space.
	 */
	vmap_init_free_space();
	vmap_initialized = true;
}

vmap_init_free_space()는 위에서 등록한 vmap_area를 바탕으로 vmalloc을 초기화한다.

vmap_init_free_space()

static void vmap_init_free_space(void)
{
	unsigned long vmap_start = 1;
	const unsigned long vmap_end = ULONG_MAX;
	struct vmap_area *busy, *free;

 

vmap_init_free_space()는 위에서 등록한 vmap_area들을 제외한 나머지 여역을 free_vmap_area_root/free_vmap_area_list에 추가한다. 주소 공간이 [1, ULONG_MAX)으로 되어있는데, 실제로 이 주소 공간 전체를 vmalloc에 사용하지는 않는다. 실제로 할당할 때는 [VMALLOC_START, VMALLOC_END) 사이에서만 할당하도록 인자를 넘긴다.

	/*
	 *     B     F     B     B     B     F
	 * -|-----|.....|-----|-----|-----|.....|-
	 *  |           The KVA space           |
	 *  |<--------------------------------->|
	 */
	list_for_each_entry(busy, &vmap_area_list, list) {
		if (busy->va_start - vmap_start > 0) {
			free = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT);
			if (!WARN_ON_ONCE(!free)) {
				free->va_start = vmap_start;
				free->va_end = busy->va_start;

				insert_vmap_area_augment(free, NULL,
					&free_vmap_area_root,
						&free_vmap_area_list);
			}
		}

		vmap_start = busy->va_end;
	}

이 부분은 미리 등록한 vmap_area의 사이 사이에 비어있는 공간을 free_vmap_area_root/free_vmap_area_list에 추가하는  코드이다. 아래 사진에서 초록색 부분을 할당한다고 할 수 있다.

	if (vmap_end - vmap_start > 0) {
		free = kmem_cache_zalloc(vmap_area_cachep, GFP_NOWAIT);
		if (!WARN_ON_ONCE(!free)) {
			free->va_start = vmap_start;
			free->va_end = vmap_end;

			insert_vmap_area_augment(free, NULL,
				&free_vmap_area_root,
					&free_vmap_area_list);
		}
	}
}

위 코드는 미리 등록한 vmap_area 사이 사이의 빈 공간을 추가한 이후 마지막 부분에 주소 공간이 남으면 추가한다. 사진으로 표현했을 때 초록색 부분을 추가한다.

요약: vmalloc_init()이 끝나면 vmalloc에 미리 등록된 주소 공간은 vmap_area_root/vmap_area_list에 등록된다. 사용 가능한 주소 공간들은 모두 free_vmap_area_root/free_vmap_area_list에 추가된다. 그리고 CPU별 자료구조도 초기화한다.

vmalloc_init() 이후 vmalloc 주소 공간의 모습

큰 흐름

vmalloc()의 큰 흐름

vmalloc()은 크게 세 가지 일을 한다. 1) vmalloc()으로 할당받은 객체가 사용할 가상 주소 공간(vmap_area)을 확보하는 것이다. 2) 그 다음에는 요청된 사이즈 만큼의 물리적으로 불연속된 메모리를 페이지 할당자에서 할당한다. 3) 마지막으로 2)에서 할당한, 물리적으로는 불연속적인 메모리들이 1)에서 확보한 가상 주소 공간 상에서 연속적이도록 페이지 테이블을 갱신하는 것이다.

Scability 이슈

vmalloc에 존재했던 확장성 이슈가 몇 가지 있다. 1) vmalloc()으로 할당한 객체를 free할 때 매번 TLB flush를 해주었던 점, 2)  주소 공간을 확보할 때 vmap_area_lock이라는 글로벌한 락을 사용한 점 3)  vmap area에 대한 정보를 linked list로 관리했다는 점이다.

2008년 Nick Piggin의 vmap rework으로 1) vfree/vunmap시에 해제된 vmap_area에 대하여 lazy하게 TLB를 flush해서 오버헤드를 줄였고 2) vm_map_ram()/vm_unmap_ram()라는 새로운 API를 통해서 CPU별로 vmap_block_queue에서 주소 공간을 할당해 글로벌 락으로 인한 확장성 이슈를 일부 해결했으며 3) vmap area를 linked list가 아니라 red-black tree로도 관리해서 시간 복잡도도 개선했다.

Huge vmalloc mappings

얼마전까지만 해도 vmalloc으로 할당하는 페이지들은 모두 order-0 페이지였다. 따라서 페이지 테이블 상에서도 PTE 단위로 매핑을 해줬는데, 최근에 Nicholas Piggin이 PMD 크기의 페이지 프레임을 할당하고 매핑할 수 있도록 huge vmalloc mapping 지원을 추가했다. 해당 패치 시리즈 덕분에 vmalloc 주소 공간에 대해서도 TLB 엔트리와 페이지 테이블에 필요한 메모리 절약할 수 있게 되었다. [mail: [PATCH v13 00/14] huge vmalloc mappings] 물론 아직 모든 아키텍처가 지원하지도 않고, vmalloc으로 할당된 페이지 프레임이 order-0이라고 가정을 한 코드가 있어서 아직 커널의 많은 파트에서 사용하지는 않는다. [lwn: The BPF allocator runs into trouble]

vfree의 큰 흐름

vfree()를 할 때 TLB를 flush할 영역들을 purge_vmap_area_list에 추가한 후, lazy하게 free하는 vmap_area의 수가 일정 숫자를 넘으면 workqueue를 통해서 purge_vmap_area_list상의 모든 vmap_area를 포함하는 주소 공간에 대하여 TLB를 한꺼번에 flush한다.

VM_RESET_PERMS

VM_RESET_PERMS는 vmalloc()으로 할당한 주소 공간의 permission을 수정할 필요가 있을 때 사용한다. 예를 들어 모듈이나 BPF 프로그램의 텍스트 섹션을 할당할 때는 실행 권한을 주어야 하므로 vmalloc()으로 할당한 후에 페이지 테이블을 수정해야한다. VM_RESET_PERMS와 함께 할당된 객체는 vfree()를 할 때 direct map상의 permission을 기본 값으로초기화해준다. vmap()/vunmap()에서도 마찬가지다.

배경을 좀 더 설명하자면 vmalloc()으로 할당된 객체를 free할 때, 주소 공간에 대한 TLB flush는 나중에 하지만 페이지 자체는 즉시 해제된다. 2019년 즈음에 Rick Edgecombe는 해제된 페이지가 사용자 프로세스에게 할당된 경우, 사용자 프로세스가 수정할 수 있는 페이지가 커널이 실행 가능하도록 TLB 상에 캐시되는 기간이 생기는 점을 지적했다. 잠재적인 보안 이슈라고 할 수 있다. [mail: Don’t leave executable TLB entries to freed pages]

다만 필자는 아직 해당 시리즈에서 말하는 보안 위협이 실존했는지는 의문이다. x86_64 기준으로 Rick의 시리즈 이전에도 vmalloc() 이후 vfree()를 하기 전에 vmalloc, direct map 영역의 페이지에 대하여 permission을 원래대로 복구하고 TLB flush까지 했었다. 이게 아키텍처에 따라 다른 부분인지 모르겠다. 이 부분은 좀 더 생각해봐야겠다.

해당 시리즈의 이후 버전에서는 VM_RESET_PERMS라는 플래그를 추가한 후, 해당 플래그로 할당된 객체는 lazy TLB flush에 관계 없이 vfree()를 할 때 permission을 기본 값으로 초기화한 후 direct map, vmalloc 영역에 대한 TLB를 즉시 flush하도록 바뀌었다.

코드 분석

큰 그림을 그려봤으니 이제 코드를 분석해보자. vmap()은 vmalloc()과 다를 바가 없으므로 이 글에서 따로 분석하지 않는다. vmalloc()을 분석하기에 앞서 vm_map_ram()/vm_unmap_ram()을 먼저 분석해보자. 그래야 vfree()가 이해가 쉽다.

Per-CPU locking

앞서 잠깐 언급했듯, vmap/vmalloc에서 사용하는 vmap_area_lock, free_vmap_area_lock 락이 글로벌한 락이기 때문에 vmalloc을 많이 사용하는 워크로드에서는 확장성이 떨어진다. (물론 필자가 알기로는 vmap/vmalloc-intensive한 상황은 많지 않다)

vm_map_ram()/vm_unmap_ram()은 CPU별로 존재하는 자료구조인 vmap_block_queue를 사용해서 글로벌 락으로 인한 지연시간을 줄이기 위한 API이다. vmap()은 글로벌한 락을 사용하도록 그대로 두고 별도의 API를 만든 이유는 vmalloc 주소 공간의 외부 단편화 때문이다. (특히 32비트에서) vm_map_ram()/vm_unmap_ram()은 크기가 작고 생애 주기가 짧은 객체에 대해서만 사용하는 것이 좋다. 

vm_map_ram()

vm_map_ram()은 vmap()보다 빠르지만 그 구현은 매우 단순하다.

/**
 * vm_map_ram - map pages linearly into kernel virtual address (vmalloc space)
 * @pages: an array of pointers to the pages to be mapped
 * @count: number of pages
 * @node: prefer to allocate data structures on this node
 *
 * If you use this function for less than VMAP_MAX_ALLOC pages, it could be
 * faster than vmap so it's good.  But if you mix long-life and short-life
 * objects with vm_map_ram(), it could consume lots of address space through
 * fragmentation (especially on a 32bit machine).  You could see failures in
 * the end.  Please use this function for short-lived objects.
 *
 * Returns: a pointer to the address that has been mapped, or %NULL on failure
 */
void *vm_map_ram(struct page **pages, unsigned int count, int node)
{
	unsigned long size = (unsigned long)count << PAGE_SHIFT;
	unsigned long addr;
	void *mem;

	if (likely(count <= VMAP_MAX_ALLOC)) {
		mem = vb_alloc(size, GFP_KERNEL);
		if (IS_ERR(mem))
			return NULL;
		addr = (unsigned long)mem;

vm_map_ram()은 order-0 페이지 프레임의 수(count)가 BITS_PER_LONG (32 or 64) 이하인 경우 vb_alloc()으로 주소 공간을 할당한다. vb_alloc()은 free_vmap_area_root/free_vmap_area_list가 아니라 현재 CPU의 vmap_block_queue에서 주소 공간을 할당한다.

	} else {
		struct vmap_area *va;
		va = alloc_vmap_area(size, PAGE_SIZE,
				VMALLOC_START, VMALLOC_END, node, GFP_KERNEL);
		if (IS_ERR(va))
			return NULL;

		addr = va->va_start;
		mem = (void *)addr;
	}

만약 사이즈가 크다면 alloc_map_area()로 vmap_area를 할당하는데, 이 경우에는 글로벌 락을 사용한다.

	if (vmap_pages_range(addr, addr + size, PAGE_KERNEL,
				pages, PAGE_SHIFT) < 0) {
		vm_unmap_ram(mem, count);
		return NULL;
	}

	/*
	 * Mark the pages as accessible, now that they are mapped.
	 * With hardware tag-based KASAN, marking is skipped for
	 * non-VM_ALLOC mappings, see __kasan_unpoison_vmalloc().
	 */
	mem = kasan_unpoison_vmalloc(mem, size, KASAN_VMALLOC_PROT_NORMAL);

	return mem;
}
EXPORT_SYMBOL(vm_map_ram);

vmap_block에서 vmap_area 하나를 쪼개서 주소 공간을 할당했든, alloc_vmap_area()로 vmap_area를 할당했든 가상 주소 공간을 확보한 후에는 vmap_pages_range()로 주소 공간에 대하여 페이지 프레임들이 가상 주소 공간 상에서 연속적이도록 매핑한다.

vb_alloc()

 

vb_alloc()은 vmap_block_queue에서 vmap_block를 찾은 후 쪼개서 사용한다. vmap_block 하나는 여러 객체에 대해 사용될 수 있다. 그래서 주소 공간을 할당할 때는 vmap_block에서 몇 개의 페이지가 사용 가능한지 (vb->free), 몇 개의 페이지프레임이 사용 중인지를(VMAP_BBMAP_BITS - vb->free) 기록해야 한다.

static void *vb_alloc(unsigned long size, gfp_t gfp_mask)
{
	struct vmap_block_queue *vbq;
	struct vmap_block *vb;
	void *vaddr = NULL;
	unsigned int order;

	BUG_ON(offset_in_page(size));
	BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC);
	if (WARN_ON(size == 0)) {
		/*
		 * Allocating 0 bytes isn't what caller wants since
		 * get_order(0) returns funny result. Just warn and terminate
		 * early.
		 */
		return NULL;
	}

vb_alloc()은 size가 0이면 NULL을 반환한다.

	order = get_order(size);

	rcu_read_lock();
	vbq = &get_cpu_var(vmap_block_queue);
	list_for_each_entry_rcu(vb, &vbq->free, free_list) {
		unsigned long pages_off;

		spin_lock(&vb->lock);
		if (vb->free < (1UL << order)) {
			spin_unlock(&vb->lock);
			continue;
		}

그 다음 vmap_block_queue를 순회하면서 vb->free가 (1 << order) 이상인 vmap_block을 찾는다.

		pages_off = VMAP_BBMAP_BITS - vb->free;
		vaddr = vmap_block_vaddr(vb->va->va_start, pages_off);
		vb->free -= 1UL << order;
		if (vb->free == 0) {
			spin_lock(&vbq->lock);
			list_del_rcu(&vb->free_list);
			spin_unlock(&vbq->lock);
		}

		spin_unlock(&vb->lock);
		break;
	}

	put_cpu_var(vmap_block_queue);
	rcu_read_unlock();

적절한 vmap_block을 찾으면 va->va_start +  (VMAP_BBMAP_BITS - vb->free) << PAGE_SHIFT를 주소로 사용하고, vb->free를 (1 << order)만큼 감소시킨다.

	/* Allocate new block if nothing was found */
	if (!vaddr)
		vaddr = new_vmap_block(order, gfp_mask);

	return vaddr;
}

vmap_block_queue에 적절한 vmap_block이 없으면 new_vmap_block()으로 새로 할당한다.

vm_unmap_ram()

/**
 * vm_unmap_ram - unmap linear kernel address space set up by vm_map_ram
 * @mem: the pointer returned by vm_map_ram
 * @count: the count passed to that vm_map_ram call (cannot unmap partial)
 */
void vm_unmap_ram(const void *mem, unsigned int count)
{
	unsigned long size = (unsigned long)count << PAGE_SHIFT;
	unsigned long addr = (unsigned long)kasan_reset_tag(mem);
	struct vmap_area *va;

	might_sleep();
	BUG_ON(!addr);
	BUG_ON(addr < VMALLOC_START);
	BUG_ON(addr > VMALLOC_END);
	BUG_ON(!PAGE_ALIGNED(addr));

	kasan_poison_vmalloc(mem, size);

	if (likely(count <= VMAP_MAX_ALLOC)) {
		debug_check_no_locks_freed(mem, size);
		vb_free(addr, size);
		return;
	}

	va = find_vmap_area(addr);
	BUG_ON(!va);
	debug_check_no_locks_freed((void *)va->va_start,
				    (va->va_end - va->va_start));
	free_unmap_vmap_area(va);
}
EXPORT_SYMBOL(vm_unmap_ram);

vm_unmap_free()는 주소 공간이 vb_alloc()으로 할당된 경우 vb_free()로 해제하고, alloc_vmap_area()로 할당된 경우 find_vmap_area()로 vmap_area()를 찾아 free_unmap_vmap_area()로 해제한다.

vb_free()

static void vb_free(unsigned long addr, unsigned long size)
{
	unsigned long offset;
	unsigned int order;
	struct vmap_block *vb;

	BUG_ON(offset_in_page(size));
	BUG_ON(size > PAGE_SIZE*VMAP_MAX_ALLOC);

	flush_cache_vunmap(addr, addr + size);

flush_cache_vunmap()은 vunmap을 하기 전에 주소 공간에 대해서 캐시를 flush한다. 이걸 하는 이유는 virtually indexed 방식의 캐시에서 aliasing을 방지하기 위함이다. 자세한 건 이 글을 참조.

	order = get_order(size);
	offset = (addr & (VMAP_BLOCK_SIZE - 1)) >> PAGE_SHIFT;
	vb = xa_load(&vmap_blocks, addr_to_vb_idx(addr));

	vunmap_range_noflush(addr, addr + size);

offset은 addr에 대한 vmap_block 내에서의 페이지 단위의 오프셋이다.

offset을 계산한 다음 xarray로 addr을 사용해서 vmap_block을 찾는다. 

	if (debug_pagealloc_enabled_static())
		flush_tlb_kernel_range(addr, addr + size);

	spin_lock(&vb->lock);

	/* Expand dirty range */
	vb->dirty_min = min(vb->dirty_min, offset);
	vb->dirty_max = max(vb->dirty_max, offset + (1UL << order));

	vb->dirty += 1UL << order;

vmap_block 내의 dirty 페이지 수와 dirty_min, dirty_max를 갱신한다.

	if (vb->dirty == VMAP_BBMAP_BITS) {
		BUG_ON(vb->free);
		spin_unlock(&vb->lock);
		free_vmap_block(vb);
	} else
		spin_unlock(&vb->lock);
}

만약 vmap_block 내의 모든 페이지가 dirty라면 free_vmap_block()으로 vmap_block을 해제한다.

free_vmap_block()

static void free_vmap_block(struct vmap_block *vb)
{
	struct vmap_block *tmp;

	tmp = xa_erase(&vmap_blocks, addr_to_vb_idx(vb->va->va_start));
	BUG_ON(tmp != vb);

	free_vmap_area_noflush(vb->va);
	kfree_rcu(vb, rcu_head);
}

free_vmap_block은 vmap_block을 xarray 상에서 지운 후, free_vmap_area_noflush()로 vmap_area를 해제한다. 그 다음 RCU로 vmap_block을 해제한다.

free_vmap_area_noflush()

이 함수는 vmap_area를 해제하는 함수이다.

/*
 * 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)
{
	unsigned long nr_lazy;

	spin_lock(&vmap_area_lock);
	unlink_va(va, &vmap_area_root);
	spin_unlock(&vmap_area_lock);

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

	/*
	 * Merge or place it to the purge tree/list.
	 */
	spin_lock(&purge_vmap_area_lock);
	merge_or_add_vmap_area(va,
		&purge_vmap_area_root, &purge_vmap_area_list);
	spin_unlock(&purge_vmap_area_lock);

	/* After this point, we may free va at any time */
	if (unlikely(nr_lazy > lazy_max_pages()))
		schedule_work(&drain_vmap_work);
}

free_vmap_area_noflush()는 vmap_area를 vmap_area_root/vmap_area_list에서 제거한 후, vmap_area를 purge_vmap_area_root/purge_vmap_area_list에 삽입한다. lazy하게 flush하는 페이지의 수 (nr_lazy)가 lazy_max_pages()보다 많아지면 workqueue로 purge_vmap_area_root/purge_vmap_area_list에 있는 vmap_area들을 한꺼번에 해제한다.

vmalloc()

vmalloc()은 __vmalloc_node_range()에 대한 래퍼 함수이다.

/**
 * 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.
 *
 * Return: pointer to the allocated memory or %NULL on error
 */
void *vmalloc(unsigned long size)
{
	return __vmalloc_node(size, 1, GFP_KERNEL, NUMA_NO_NODE,
				__builtin_return_address(0));
}
EXPORT_SYMBOL(vmalloc);

vmalloc()은 __vmalloc_node()를 호출하고,

/**
 * __vmalloc_node - allocate virtually contiguous memory
 * @size:	    allocation size
 * @align:	    desired alignment
 * @gfp_mask:	    flags for the page level allocator
 * @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.
 *
 * 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.
 *
 * Return: pointer to the allocated memory or %NULL on error
 */
void *__vmalloc_node(unsigned long size, unsigned long align,
			    gfp_t gfp_mask, int node, const void *caller)
{
	return __vmalloc_node_range(size, align, VMALLOC_START, VMALLOC_END,
				gfp_mask, PAGE_KERNEL, 0, node, caller);
}

__vmalloc_node()는 __vmalloc_node_range()를 호출한다.

__vmalloc_node_range()

/**
 * __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. Please note that the full set of gfp
 * flags are not supported. GFP_KERNEL, GFP_NOFS and GFP_NOIO are all
 * supported.
 * Zone modifiers are not supported. From the reclaim modifiers
 * __GFP_DIRECT_RECLAIM is required (aka GFP_NOWAIT is not supported)
 * and only __GFP_NOFAIL is supported (i.e. __GFP_NORETRY and
 * __GFP_RETRY_MAYFAIL are not supported).
 *
 * __GFP_NOWARN can be used to suppress failures messages.
 *
 * Map them into contiguous kernel virtual space, using a pagetable
 * protection of @prot.
 *
 * Return: the address of the area or %NULL on failure
 */
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 *ret;
	kasan_vmalloc_flags_t kasan_flags = KASAN_VMALLOC_NONE;
	unsigned long real_size = size;
	unsigned long real_align = align;
	unsigned int shift = PAGE_SHIFT;

	if (WARN_ON_ONCE(!size))
		return NULL;

	if ((size >> PAGE_SHIFT) > totalram_pages()) {
		warn_alloc(gfp_mask, NULL,
			"vmalloc error: size %lu, exceeds total pages",
			real_size);
		return NULL;
	}

size가 0이거나 size가 총 메모리의 크기보다 큰 경우에는 할당이 실패한다.

	if (vmap_allow_huge && (vm_flags & VM_ALLOW_HUGE_VMAP)) {
		unsigned long size_per_node;

		/*
		 * Try huge pages. Only try for PAGE_KERNEL allocations,
		 * others like modules don't yet expect huge pages in
		 * their allocations due to apply_to_page_range not
		 * supporting them.
		 */

		size_per_node = size;
		if (node == NUMA_NO_NODE)
			size_per_node /= num_online_nodes();
		if (arch_vmap_pmd_supported(prot) && size_per_node >= PMD_SIZE)
			shift = PMD_SHIFT;
		else
			shift = arch_vmap_pte_supported_shift(size_per_node);

		align = max(real_align, 1UL << shift);
		size = ALIGN(real_size, 1UL << shift);
	}

아키텍처가 huge vmalloc mapping을 지원하고, VM_ALLOW_HUGE_VMAP 플래그가 켜진 경우, PMD 하나가 매핑하는 페이지의 크기나 아키텍처에서 제공한 크기에 대해 정렬되도록 align과 size를 갱신한다.

again:
	area = __get_vm_area_node(real_size, align, shift, VM_ALLOC |
				  VM_UNINITIALIZED | vm_flags, start, end, node,
				  gfp_mask, caller);

__get_vm_area_node()는 [start, end)에 대하여 적절한 가상 주소 공간을 찾는다. (이 함수는 사용 가능한 vmap_area를 확보한 후, vmap_area에 연결된 vm_struct를 반환한다.)

	if (!area) {
		bool nofail = gfp_mask & __GFP_NOFAIL;
		warn_alloc(gfp_mask, NULL,
			"vmalloc error: size %lu, vm_struct allocation failed%s",
			real_size, (nofail) ? ". Retrying." : "");
		if (nofail) {
			schedule_timeout_uninterruptible(1);
			goto again;
		}
		goto fail;
	}

적절한 가상 주소 공간을 찾지 못한 경우에는 당연히 실패한다. 다만 __GFP_NOFAIL 플래그가 설정된 경우에는 성공할 때까지 다시 시도한다.

	/*
	 * Prepare arguments for __vmalloc_area_node() and
	 * kasan_unpoison_vmalloc().
	 */
	if (pgprot_val(prot) == pgprot_val(PAGE_KERNEL)) {
		if (kasan_hw_tags_enabled()) {
			/*
			 * Modify protection bits to allow tagging.
			 * This must be done before mapping.
			 */
			prot = arch_vmap_pgprot_tagged(prot);

			/*
			 * Skip page_alloc poisoning and zeroing for physical
			 * pages backing VM_ALLOC mapping. Memory is instead
			 * poisoned and zeroed by kasan_unpoison_vmalloc().
			 */
			gfp_mask |= __GFP_SKIP_KASAN_UNPOISON | __GFP_SKIP_ZERO;
		}

		/* Take note that the mapping is PAGE_KERNEL. */
		kasan_flags |= KASAN_VMALLOC_PROT_NORMAL;
	}

KASAN, kmemleak 파트에 대한 자세한 분석은 생략한다.

	/* Allocate physical pages and map them into vmalloc space. */
	ret = __vmalloc_area_node(area, gfp_mask, prot, shift, node);
	if (!ret)
		goto fail;

__vmalloc_area_node()는 물리 메모리를 할당한 후 이전에 확보한 vmap_area가 나타내는 주소 공간에 연속적이도록 매핑한다. 그 다음에는 KASAN, kmemleak 관련 함수를 호출하고 __vmalloc_area_node()에서 할당된 주소를 반환한다.

	/*
	 * Mark the pages as accessible, now that they are mapped.
	 * The init condition should match the one in post_alloc_hook()
	 * (except for the should_skip_init() check) to make sure that memory
	 * is initialized under the same conditions regardless of the enabled
	 * KASAN mode.
	 * Tag-based KASAN modes only assign tags to normal non-executable
	 * allocations, see __kasan_unpoison_vmalloc().
	 */
	kasan_flags |= KASAN_VMALLOC_VM_ALLOC;
	if (!want_init_on_free() && want_init_on_alloc(gfp_mask))
		kasan_flags |= KASAN_VMALLOC_INIT;
	/* KASAN_VMALLOC_PROT_NORMAL already set if required. */
	area->addr = kasan_unpoison_vmalloc(area->addr, real_size, kasan_flags);
    
	/*
	 * 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);
    
    	size = PAGE_ALIGN(size);
	if (!(vm_flags & VM_DEFER_KMEMLEAK))
		kmemleak_vmalloc(area, size, gfp_mask);

	return area->addr;

fail:
	if (shift > PAGE_SHIFT) {
		shift = PAGE_SHIFT;
		align = real_align;
		size = real_size;
		goto again;
	}

	return NULL;
}

__get_vm_area_node()

앞서 설명했듯 __get_vm_area_node()는 free_vmap_area_root에서 사용 가능한 vmap_area를 확보한 후, 확보한 vmap_area 가 나타내는 주소 공간에 대하여 할당된 메모리에 대한 정보를 저장할 vm_struct를 반환한다.

static struct vm_struct *__get_vm_area_node(unsigned long size,
		unsigned long align, unsigned long shift, 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;
	unsigned long requested_size = size;

	BUG_ON(in_interrupt());
	size = ALIGN(size, 1ul << shift);
	if (unlikely(!size))
		return NULL;

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

먼저 size를 (1 << shift)에 대하여 정렬하며, ioremap에 사용할 주소 공간을 찾는 경우 align을 갱신한다.

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

이후 vm_struct 를 위한 공간을 kzalloc_node()로 할당하고, alloc_vmap_area()로 vmap_area를 확보한 후에 setup_vmalloc_vm()으로 vmap_area와 vm_struct를 초기화해준다.

	/*
	 * Mark pages for non-VM_ALLOC mappings as accessible. Do it now as a
	 * best-effort approach, as they can be mapped outside of vmalloc code.
	 * For VM_ALLOC mappings, the pages are marked as accessible after
	 * getting mapped in __vmalloc_node_range().
	 * With hardware tag-based KASAN, marking is skipped for
	 * non-VM_ALLOC mappings, see __kasan_unpoison_vmalloc().
	 */
	if (!(flags & VM_ALLOC))
		area->addr = kasan_unpoison_vmalloc(area->addr, requested_size,
						    KASAN_VMALLOC_PROT_NORMAL);

	return area;
}

alloc_vmap_area()

앞서서 alloc_vmap_area()가 하는 일이 vmalloc()에 사용할 가상 주소 공간(vmap_area)를 확보하는 것이라고 했다. 이 과정은 구체적으로는 free_vmap_area_root/free_vmap_area_list에 존재하는 vmap_area를 찾은 후, 이를 일부 쪼개서 vmap_area_root/vmap_area_list에 삽입하는 것이다.

/*
 * 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;
	unsigned long freed;
	unsigned long addr;
	int purged = 0;
	int ret;

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

	if (unlikely(!vmap_initialized))
		return ERR_PTR(-EBUSY);

	might_sleep();
	gfp_mask = gfp_mask & GFP_RECLAIM_MASK;

	va = kmem_cache_alloc_node(vmap_area_cachep, gfp_mask, node);
	if (unlikely(!va))
		return ERR_PTR(-ENOMEM);

우선 free_vmap_area_list/free_vmap_area_root 상의 vmap_area를 2개로 쪼개려면 vmap_area가 하나 더 생겨야 하므로 kmem_cache_alloc_node()로 메모리를 할당받는다.

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

retry:
	preload_this_cpu_lock(&free_vmap_area_lock, gfp_mask, node);
	addr = __alloc_vmap_area(size, align, vstart, vend);
	spin_unlock(&free_vmap_area_lock);

	/*
	 * If an allocation fails, the "vend" address is
	 * returned. Therefore trigger the overflow path.
	 */
	if (unlikely(addr == vend))
		goto overflow;

free_vmap_area_list/free_vmap_area_root 상의 vmap_area를 쪼개는 것은 __alloc_vmap_area()에서 처리한다.

실패한 경우에는 적당한 주소 공간이 없는 것이므로 다시 시도한다.

	va->va_start = addr;
	va->va_end = addr + size;
	va->vm = NULL;

	spin_lock(&vmap_area_lock);
	insert_vmap_area(va, &vmap_area_root, &vmap_area_list);
	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);

	ret = kasan_populate_vmalloc(addr, size);
	if (ret) {
		free_vmap_area(va);
		return ERR_PTR(ret);
	}

	return va;

성공한 경우에는 vmap_area를 초기화 한 후 반환한다.

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

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

	kmem_cache_free(vmap_area_cachep, va);
	return ERR_PTR(-EBUSY);
}

주소 공간 확보에 실패한 경우에는 해제할 수 있는 vmap_area를 모두 해제한 후 다시 시도해본다.

__alloc_vmap_area()

/*
 * Returns a start address of the newly allocated area, if success.
 * Otherwise a vend is returned that indicates failure.
 */
static __always_inline unsigned long
__alloc_vmap_area(unsigned long size, unsigned long align,
	unsigned long vstart, unsigned long vend)
{
	bool adjust_search_size = true;
	unsigned long nva_start_addr;
	struct vmap_area *va;
	enum fit_type type;
	int ret;

	/*
	 * Do not adjust when:
	 *   a) align <= PAGE_SIZE, because it does not make any sense.
	 *      All blocks(their start addresses) are at least PAGE_SIZE
	 *      aligned anyway;
	 *   b) a short range where a requested size corresponds to exactly
	 *      specified [vstart:vend] interval and an alignment > PAGE_SIZE.
	 *      With adjusted search length an allocation would not succeed.
	 */
	if (align <= PAGE_SIZE || (align > PAGE_SIZE && (vend - vstart) == size))
		adjust_search_size = false;

	va = find_vmap_lowest_match(size, align, vstart, adjust_search_size);
	if (unlikely(!va))
		return vend;

find_vmap_lowest_match()는 free_vmap_area_root 상의 vmap_area 중 [vstart, vstart + size)를 포함하는 vmap_area를 찾는다.

	if (va->va_start > vstart)
		nva_start_addr = ALIGN(va->va_start, align);
	else
		nva_start_addr = ALIGN(vstart, align);

	/* Check the "vend" restriction. */
	if (nva_start_addr + size > vend)
		return vend;

그리고 찾은 vmap_area의 시작 주소 대신, 시작 주소를 align에 맞게 정렬한 nva_start_addr을 계산한다.

	/* Classify what we have found. */
	type = classify_va_fit_type(va, nva_start_addr, size);
	if (WARN_ON_ONCE(type == NOTHING_FIT))
		return vend;

	/* Update the free vmap_area. */
	ret = adjust_va_to_fit_type(va, nva_start_addr, size, type);
	if (ret)
		return vend;

찾은 vmap_area가 [vstart, vstart + end)를 포함하는 경우는 4가지 경우가 있다. classify_va_fit_type()으로 4가지 경우 중 어떤 경우인지를 알아낸 후 adjust_va_to_fit_type()으로 경우에 따라서 vmap_area의 주소와 크기 등을 갱신해준다.

#if DEBUG_AUGMENT_LOWEST_MATCH_CHECK
	find_vmap_lowest_match_check(size, align);
#endif

	return nva_start_addr;
}

자. 여기까지 해서 어떻게 주소 공간을 확보하는지 분석했다. 이제 어떻게 vmalloc()에 필요한 메모리를 할당하는지 알아보자.

__vmalloc_area_node()

static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
				 pgprot_t prot, unsigned int page_shift,
				 int node)
{
	const gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO;
	bool nofail = gfp_mask & __GFP_NOFAIL;
	unsigned long addr = (unsigned long)area->addr;
	unsigned long size = get_vm_area_size(area);
	unsigned long array_size;
	unsigned int nr_small_pages = size >> PAGE_SHIFT;
	unsigned int page_order;
	unsigned int flags;
	int ret;

	array_size = (unsigned long)nr_small_pages * sizeof(struct page *);
	gfp_mask |= __GFP_NOWARN;
	if (!(gfp_mask & (GFP_DMA | GFP_DMA32)))
		gfp_mask |= __GFP_HIGHMEM;

	/* Please note that the recursion is strictly bounded. */
	if (array_size > PAGE_SIZE) {
		area->pages = __vmalloc_node(array_size, 1, nested_gfp, node,
					area->caller);
	} else {
		area->pages = kmalloc_node(array_size, nested_gfp, node);
	}

물리적으로 연속적이지 않은 페이지들을 할당할 것이므로 이를 저장할 배열을 배열의 크기에 따라서 vmalloc이나 kmalloc으로 할당해준다. 이때 vmalloc으로 할당하면 재귀로 할당하게 되는데, 보통 커널에서 재귀를 잘 사용하지 않으나 이 경우에는 재귀의 깊이가 아주 제한적이다.

	if (!area->pages) {
		warn_alloc(gfp_mask, NULL,
			"vmalloc error: size %lu, failed to allocated page array size %lu",
			nr_small_pages * PAGE_SIZE, array_size);
		free_vm_area(area);
		return NULL;
	}

	set_vm_area_page_order(area, page_shift - PAGE_SHIFT);
	page_order = vm_area_page_order(area);
    area->nr_pages = vm_area_alloc_pages(gfp_mask | __GFP_NOWARN,
    node, page_order, nr_small_pages, area->pages);

실질적으로 페이지들을 할당하는 함수는 vm_area_alloc_pages()이다.

	atomic_long_add(area->nr_pages, &nr_vmalloc_pages);
	if (gfp_mask & __GFP_ACCOUNT) {
		int i;

		for (i = 0; i < area->nr_pages; i++)
			mod_memcg_page_state(area->pages[i], MEMCG_VMALLOC, 1);
	}

	/*
	 * If not enough pages were obtained to accomplish an
	 * allocation request, free them via __vfree() if any.
	 */
	if (area->nr_pages != nr_small_pages) {
		warn_alloc(gfp_mask, NULL,
			"vmalloc error: size %lu, page order %u, failed to allocate pages",
			area->nr_pages * PAGE_SIZE, page_order);
		goto fail;
	}

할당 후에는 시스템 전체 vmalloc 사용량, cgroup 내에서의 vmalloc 사용량 등 통계 정보를 갱신한다. 메모리 할당에 실패한 경우에는 __vfree()로 해제한다.

	/*
	 * page tables allocations ignore external gfp mask, enforce it
	 * by the scope API
	 */
	if ((gfp_mask & (__GFP_FS | __GFP_IO)) == __GFP_IO)
		flags = memalloc_nofs_save();
	else if ((gfp_mask & (__GFP_FS | __GFP_IO)) == 0)
		flags = memalloc_noio_save();

	do {
		ret = vmap_pages_range(addr, addr + size, prot, area->pages,
			page_shift);
		if (nofail && (ret < 0))
			schedule_timeout_uninterruptible(1);
	} while (nofail && (ret < 0));

	if ((gfp_mask & (__GFP_FS | __GFP_IO)) == __GFP_IO)
		memalloc_nofs_restore(flags);
	else if ((gfp_mask & (__GFP_FS | __GFP_IO)) == 0)
		memalloc_noio_restore(flags);

이후 할당된 페이지를 앞서 확보한 vmap_area가 나타내는 주소 공간에서 연속적이도록 vmap_pages_range()로 매핑해준다. 이 때, 원래 페이지 테이블을 할당할 때는 __GFP_FS와 __GFP_IO가 무시되는데, 무시되지 않도록 memalloc_{nofs,noio}_{save,restore}() API를 호출해준다.

	if (ret < 0) {
		warn_alloc(gfp_mask, NULL,
			"vmalloc error: size %lu, failed to map pages",
			area->nr_pages * PAGE_SIZE);
		goto fail;
	}

	return area->addr;

fail:
	__vfree(area->addr);
	return NULL;
}

vm_area_alloc_pages()

이 함수는 vmalloc()에서 사용할 페이지 프레임들을 할당한다. 함수에서 생각할 부분은 order-0인 페이지 프레임만 할당을 하느냐, high order 페이지 프레임으로 할당을 하느냐이다.

static inline unsigned int
vm_area_alloc_pages(gfp_t gfp, int nid,
		unsigned int order, unsigned int nr_pages, struct page **pages)
{
	unsigned int nr_allocated = 0;
	struct page *page;
	int i;

	/*
	 * For order-0 pages we make use of bulk allocator, if
	 * the page array is partly or not at all populated due
	 * to fails, fallback to a single page allocator that is
	 * more permissive.
	 */
	if (!order) {
		gfp_t bulk_gfp = gfp & ~__GFP_NOFAIL;

		while (nr_allocated < nr_pages) {
			unsigned int nr, nr_pages_request;

			/*
			 * A maximum allowed request is hard-coded and is 100
			 * pages per call. That is done in order to prevent a
			 * long preemption off scenario in the bulk-allocator
			 * so the range is [1:100].
			 */
			nr_pages_request = min(100U, nr_pages - nr_allocated);

			/* memory allocation should consider mempolicy, we can't
			 * wrongly use nearest node when nid == NUMA_NO_NODE,
			 * otherwise memory may be allocated in only one node,
			 * but mempolcy want to alloc memory by interleaving.
			 */
			if (IS_ENABLED(CONFIG_NUMA) && nid == NUMA_NO_NODE)
				nr = alloc_pages_bulk_array_mempolicy(bulk_gfp,
							nr_pages_request,
							pages + nr_allocated);

			else
				nr = alloc_pages_bulk_array_node(bulk_gfp, nid,
							nr_pages_request,
							pages + nr_allocated);

			nr_allocated += nr;
			cond_resched();

			/*
			 * If zero or pages were obtained partly,
			 * fallback to a single page allocator.
			 */
			if (nr != nr_pages_request)
				break;
		}
	}

우선 order가 0인 경우에는 페이지 할당자의 bulk allocation API를 사용한다. 이 때 어느 노드에서 할당할지는 NUMA 할당 정책을 따르거나 별도로 지정한 노드(nid)에서 할당한다.

	/* High-order pages or fallback path if "bulk" fails. */

	while (nr_allocated < nr_pages) {
		if (fatal_signal_pending(current))
			break;

		if (nid == NUMA_NO_NODE)
			page = alloc_pages(gfp, order);
		else
			page = alloc_pages_node(nid, gfp, order);
		if (unlikely(!page))
			break;
		/*
		 * Higher order allocations must be able to be treated as
		 * indepdenent small pages by callers (as they can with
		 * small-page vmallocs). Some drivers do their own refcounting
		 * on vmalloc_to_page() pages, some use page->mapping,
		 * page->lru, etc.
		 */
		if (order)
			split_page(page, order);

bulk API로 전부 할당하지 못한 경우, 또는 order > 0인 경우에는 alloc_pages{,_node}()로 페이지 프레임을 하나씩 할당한다. 이 때 high order 페이지 프레임을 할당한 경우라도 high order 페이지 프레임 하나가 아니라 order-0 page frame이 여러개인 것처럼 취급해야 하므로 split_page()로 high-order 페이지 프레임을 여러 개로 나눠준다.

		/*
		 * Careful, we allocate and map page-order pages, but
		 * tracking is done per PAGE_SIZE page so as to keep the
		 * vm_struct APIs independent of the physical/mapped size.
		 */
		for (i = 0; i < (1U << order); i++)
			pages[nr_allocated + i] = page + i;

		cond_resched();
		nr_allocated += 1U << order;
	}

	return nr_allocated;
}

vfree()

이제 vfree()를 분석해보자. 

/**
 * vfree - Release memory allocated by vmalloc()
 * @addr:  Memory base address
 *
 * Free the virtually continuous memory area starting at @addr, as obtained
 * from one of the vmalloc() family of APIs.  This will usually also free the
 * physical memory underlying the virtual allocation, but that memory is
 * reference counted, so it will not be freed until the last user goes away.
 *
 * If @addr is NULL, no operation is performed.
 *
 * Context:
 * May sleep if called *not* from interrupt context.
 * Must not be called in NMI context (strictly speaking, it could be
 * if we have CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG, but making the calling
 * conventions for vfree() arch-dependent would be a really bad idea).
 */
void vfree(const void *addr)
{
	BUG_ON(in_nmi());

	kmemleak_free(addr);

	might_sleep_if(!in_interrupt());

	if (!addr)
		return;

	__vfree(addr);
}
EXPORT_SYMBOL(vfree);

.vfree()는 nmi context에서 호출할 수 없으며, interrupt context인 경우에는 sleep을 할 수도 있다.

static void __vfree(const void *addr)
{
	if (unlikely(in_interrupt()))
		__vfree_deferred(addr);
	else
		__vunmap(addr, 1);
}

__vfree()는 interrupt context인 경우 __vfree_deferred()로 workqueue를 사용해서 __vunmap()을 호출한다. 프로세스 컨텍스트인 경우에는 __vunmap()을 바로 호출한다.

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_vm_area(addr);
	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));

	kasan_poison_vmalloc(area->addr, get_vm_area_size(area));

	vm_remove_mappings(area, deallocate_pages);

__vunmap()은 find_vm_area()로 주소에 대한 vm_struct를 찾은 후 vm_remove_mappings()로 vmap_area를 해제한다.

	if (deallocate_pages) {
		int i;

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

			BUG_ON(!page);
			mod_memcg_page_state(page, MEMCG_VMALLOC, -1);
			/*
			 * High-order allocs for huge vmallocs are split, so
			 * can be freed as an array of order-0 allocations
			 */
			__free_pages(page, 0);
			cond_resched();
		}
		atomic_long_sub(area->nr_pages, &nr_vmalloc_pages);

		kvfree(area->pages);
	}

	kfree(area);
}

deallocate_pages가 0이 아닌 경우 (vmap()이 아니라 vfree()가 호출된 경우) vm_struct가 가리키는 페이지 프레임들과 이를 담는 배열을 해제한다.

vm_remove_mappings()

/* Handle removing and resetting vm mappings related to the vm_struct. */
static void vm_remove_mappings(struct vm_struct *area, int deallocate_pages)
{
	unsigned long start = ULONG_MAX, end = 0;
	unsigned int page_order = vm_area_page_order(area);
	int flush_reset = area->flags & VM_FLUSH_RESET_PERMS;
	int flush_dmap = 0;
	int i;

	remove_vm_area(area->addr);

	/* If this is not VM_FLUSH_RESET_PERMS memory, no need for the below. */
	if (!flush_reset)
		return;

vm_remove_mappings()에는 기본적으로 remove_vm_area를 호출하며, vm_struct->flags에 VM_FLUSH_RESET_PERMS가 설정된 경우에 direct map 상의 permission을 초기화한다.

	/*
	 * If not deallocating pages, just do the flush of the VM area and
	 * return.
	 */
	if (!deallocate_pages) {
		vm_unmap_aliases();
		return;
	}

vmalloc()이 아니라 vmap()을 VM_FLUSH_RESET_PERMS로 호출한 경우에는 메모리를 바로 해제하지 않으므로 direct map 영역은 건드리지 않는다.

	/*
	 * If execution gets here, flush the vm mapping and reset the direct
	 * map. Find the start and end range of the direct mappings to make sure
	 * the vm_unmap_aliases() flush includes the direct map.
	 */
	for (i = 0; i < area->nr_pages; i += 1U << page_order) {
		unsigned long addr = (unsigned long)page_address(area->pages[i]);
		if (addr) {
			unsigned long page_size;

			page_size = PAGE_SIZE << page_order;
			start = min(addr, start);
			end = max(addr + page_size, end);
			flush_dmap = 1;
		}
	}

여기까지 실행되면 VM_FLUSH_RESET_PERMS로 할당했던 메모리를 vfree()하는 것이다. vm_struct 구조체의 pages 배열에 있는 모든 페이지를 포함하도록 start와 end를 구해서 flush할 범위를 지정한다.

	/*
	 * Set direct map to something invalid so that it won't be cached if
	 * there are any accesses after the TLB flush, then flush the TLB and
	 * reset the direct map permissions to the default.
	 */
	set_area_direct_map(area, set_direct_map_invalid_noflush);
	_vm_unmap_aliases(start, end, flush_dmap);
	set_area_direct_map(area, set_direct_map_default_noflush);
}

set_direct_map_invalid_noflush()로 우선 페이지 테이블 상에서 invalid하도록 설정해주어서 TLB 상에 캐시되지 않도록 한다. 그 다음 _vm_unmap_aliases()로 TLB를 flush한 후 set_direct_map_default_noflush()로 direct map의 기본 permission으로 초기화해준다. 이 때 _vm_unmap_aliases()에서 TLB를 flush 하는 범위는 인자로 넘긴 direct map 영역상의 주소와 vmalloc 영역 상의 주소를 모두 포함한다.

원래는 free된 vmap_area에 대한 TLB flush는 lazy하게 flush하는 페이지가 많은 경우에만 workqueue로 한꺼번에 처리하지만, VM_RESET_PERMS가 설정된 경우에 즉시 flush를 하게 된다.

remove_vm_area()

/**
 * 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.
 *
 * Return: the area descriptor on success or %NULL on failure.
 */
struct vm_struct *remove_vm_area(const void *addr)
{
	struct vmap_area *va;

	might_sleep();

	spin_lock(&vmap_area_lock);
	va = __find_vmap_area((unsigned long)addr);
	if (va && va->vm) {
		struct vm_struct *vm = va->vm;

		va->vm = NULL;
		spin_unlock(&vmap_area_lock);

		kasan_free_module_shadow(vm);
		free_unmap_vmap_area(va);

		return vm;
	}

	spin_unlock(&vmap_area_lock);
	return NULL;
}

remove_vm_area()는 __find_vmap_area()로 주소에 대한 vmap_area()를 찾은 후 free_unmap_vmap_area()로 vmap_area()를 해제한다.

free_unmap_vmap_area()

/*
 * 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);
	vunmap_range_noflush(va->va_start, va->va_end);
	if (debug_pagealloc_enabled_static())
		flush_tlb_kernel_range(va->va_start, va->va_end);

	free_vmap_area_noflush(va);
}

free_unmap_vmap_area()는 캐시를 flush하고 페이지 테이블 상에서 vmap_area에 대한 매핑을 제거한 후에 아까 살펴봤던 free_vmap_area_noflush()를 호출한다.

vm_unmap_aliases()

/**
 * vm_unmap_aliases - unmap outstanding lazy aliases in the vmap layer
 *
 * The vmap/vmalloc layer lazily flushes kernel virtual mappings primarily
 * to amortize TLB flushing overheads. What this means is that any page you
 * have now, may, in a former life, have been mapped into kernel virtual
 * address by the vmap layer and so there might be some CPUs with TLB entries
 * still referencing that page (additional to the regular 1:1 kernel mapping).
 *
 * vm_unmap_aliases flushes all such lazy mappings. After it returns, we can
 * be sure that none of the pages we have control over will have any aliases
 * from the vmap layer.
 */
void vm_unmap_aliases(void)
{
	unsigned long start = ULONG_MAX, end = 0;
	int flush = 0;

	_vm_unmap_aliases(start, end, flush);
}
EXPORT_SYMBOL_GPL(vm_unmap_aliases);

_vm_unmap_aliases()

static void _vm_unmap_aliases(unsigned long start, unsigned long end, int flush)
{
	int cpu;

	if (unlikely(!vmap_initialized))
		return;

	might_sleep();

	for_each_possible_cpu(cpu) {
		struct vmap_block_queue *vbq = &per_cpu(vmap_block_queue, cpu);
		struct vmap_block *vb;

		rcu_read_lock();
		list_for_each_entry_rcu(vb, &vbq->free, free_list) {
			spin_lock(&vb->lock);
			if (vb->dirty && vb->dirty != VMAP_BBMAP_BITS) {
				unsigned long va_start = vb->va->va_start;
				unsigned long s, e;

				s = va_start + (vb->dirty_min << PAGE_SHIFT);
				e = va_start + (vb->dirty_max << PAGE_SHIFT);

				start = min(s, start);
				end   = max(e, end);

				flush = 1;
			}
			spin_unlock(&vb->lock);
		}
		rcu_read_unlock();
	}

위 코드는 일부만 dirty한 vmap_block들을 모두 포함하는 주소 공간 [start, end)를 계산한다. vb->dirty == VMAP_BBMAP_BITS인 vmap_block의 영역은 포함하지 않는데, 이는 vmap_block은 RCU로 free되지만 vmap_area은 바로 free되기 때문에, free된 vmap_block의 vmap_area를 해제 후 접근하는 경우를 방지하기 위함이다.

처음에는 이 부분을 읽고 왜 모두 dirty한 vmap_block은 flush하지 않지? 라고 오해했지만 정상적인 경우 모두 dirty한 vmap_block은 vb_free()에 의해 vmap_block_queue에 존재하지 않고 purge_vmap_area_root/purge_vmap_area_list에 vmap_area가 존재해야 한다.

	mutex_lock(&vmap_purge_lock);
	purge_fragmented_blocks_allcpus();

purge_fragmented_blocks_allcpus()는 모든 CPU에 대하여 할당 중인 주소 공간이 없는 vmap_block들을 free_vmap_block()으로 모두 해제한다. (결과적으로 vmap_area가 purge_vmap_area_list/purge_vmap_area_root에 삽입된다.)

	if (!__purge_vmap_area_lazy(start, end) && flush)
		flush_tlb_kernel_range(start, end);
	mutex_unlock(&vmap_purge_lock);
}

__purge_vmap_area_lazy()가 true를 반환하면 주소 공간 [start, end)을 포함하면서 purge_vmap_area_list 상의 모든 vmap_area를 포함하는 주소 공간에 대한 TLB가 flush된 것이다.

만약 __purge_vmap_area_lazy()가 false를 반환했지만 flush가 0이 아니면 [start, end)에 대해서만 TLB를 flush한다.

__purge_vmap_area_lazy()

/*
 * Purges all lazily-freed vmap areas.
 */
static bool __purge_vmap_area_lazy(unsigned long start, unsigned long end)
{
	unsigned long resched_threshold;
	struct list_head local_pure_list;
	struct vmap_area *va, *n_va;

	lockdep_assert_held(&vmap_purge_lock);

	spin_lock(&purge_vmap_area_lock);
	purge_vmap_area_root = RB_ROOT;
	list_replace_init(&purge_vmap_area_list, &local_pure_list);
	spin_unlock(&purge_vmap_area_lock);

	if (unlikely(list_empty(&local_pure_list)))
		return false;

	start = min(start,
		list_first_entry(&local_pure_list,
			struct vmap_area, list)->va_start);

	end = max(end,
		list_last_entry(&local_pure_list,
			struct vmap_area, list)->va_end);

	flush_tlb_kernel_range(start, end);
	resched_threshold = lazy_max_pages() << 1;

__purge_vmap_area_lazy()는 purge_vmap_area_list 상의 모든 vmap_area를 주소를 포함하는 주소 공간 [start, end)에 대하여 TLB를 flush한다. TLB를 flush한 경우 true, purge_vmap_area_list가 비어있는 경우 false를 리턴한다.

	spin_lock(&free_vmap_area_lock);
	list_for_each_entry_safe(va, n_va, &local_pure_list, list) {
		unsigned long nr = (va->va_end - va->va_start) >> PAGE_SHIFT;
		unsigned long orig_start = va->va_start;
		unsigned long orig_end = va->va_end;

		/*
		 * Finally insert or merge lazily-freed area. It is
		 * detached and there is no need to "unlink" it from
		 * anything.
		 */
		va = merge_or_add_vmap_area_augment(va, &free_vmap_area_root,
				&free_vmap_area_list);

		if (!va)
			continue;

		if (is_vmalloc_or_module_addr((void *)orig_start))
			kasan_release_vmalloc(orig_start, orig_end,
					      va->va_start, va->va_end);

		atomic_long_sub(nr, &vmap_lazy_nr);

		if (atomic_long_read(&vmap_lazy_nr) < resched_threshold)
			cond_resched_lock(&free_vmap_area_lock);
	}
	spin_unlock(&free_vmap_area_lock);
	return true;
}

flush한 다음에는 free_vmap_area_list/free_vmap_area_root에 vmap_area들을 삽입하거나 병합이 가능한 경우 이미 존재하는 vmap_area와 병합한다.

The end

분석이 생각보다 오래 걸렸다. 생각했던 것보다 vmalloc subsystem의 구조가 복잡했다.

글을 쓸 때마다 느끼지만 페이지와 페이지 프레임을 구분해서 쓰기가 어렵다. 자주 틀리는 것 같다.