The Linux Memory Manager3장

vmalloc free tree에서 주소 하나를 꺼내는 과정

Lorenzo Stoakes의 책을 바탕으로 한 독립 학습 노트

빈 virtual space가 요청 크기보다 길다는 사실만으로 allocation이 성공하지는 않습니다. 시작을 alignment에 맞추느라 앞쪽 공간을 버릴 수 있고, caller가 허용한 주소 끝을 넘을 수도 있습니다. 후보를 찾는 일, 실제 범위를 확정하는 일, 남은 hole을 tree에 돌려놓는 일은 서로 다른 단계입니다.

이 글은 upstream Linux v6.18의 global free-tree 경로를 따라갑니다. 현재 allocator에는 vmap-node pool도 있으므로 모든 요청이 아래 tree를 처음부터 검색한다고 가정하지 않습니다. code는 mm/vmalloc.c의 GPL-2.0-only 전체 함수와 enum입니다. 각 정의의 출처·line 범위, GPL-2.0 text를 함께 제공합니다. kernel 내부 의존성이 필요한 code이며 실행하지 않았습니다.

후보의 길이와 요청의 길이

free interval은 주소순 red-black tree와 list로 관리합니다. 각 subtree에는 가장 큰 hole 길이를 요약한 subtree_max_size가 있습니다. 요청을 담을 수 없는 subtree를 내려가지 않기 위한 augmentation입니다. tree의 회전으로 높이 균형을 유지하는 일과, 회전·구간 변경 뒤 길이 요약을 갱신하는 일은 별개의 불변식입니다.

__alloc_vmap_area()는 큰 alignment에 대해 검색 길이를 늘릴지 먼저 고릅니다. page-aligned hole에 align <= PAGE_SIZE인 요청을 넣을 때에는 추가 padding이 필요하지 않습니다. 반대로 요청 크기가 caller의 [vstart, vend) 전체와 정확히 같으면 최악 padding을 무조건 더해 검색할 수 없습니다. 그 보수적인 길이 때문에 유일하게 가능한 interval도 놓칠 수 있기 때문입니다.

__alloc_vmap_area.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 *  Copyright (C) 1993  Linus Torvalds
 *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
 *  SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
 *  Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
 *  Numa awareness, Christoph Lameter, SGI, June 2005
 *  Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019
 */
/*
 * Linux v6.18, mm/vmalloc.c:1816-1849
 * Source: https://github.com/torvalds/linux/blob/v6.18/mm/vmalloc.c
 * Complete function: __alloc_vmap_area
 * Body unchanged. Kernel dependencies are not bundled.
 * License text: GPL-2.0.txt
 */

static __always_inline unsigned long
__alloc_vmap_area(struct rb_root *root, struct list_head *head,
	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;

	/*
	 * 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(root, size, align, vstart, adjust_search_size);
	if (unlikely(!va))
		return -ENOENT;

	nva_start_addr = va_alloc(va, root, head, size, align, vstart, vend);

#if DEBUG_AUGMENT_LOWEST_MATCH_CHECK
	if (!IS_ERR_VALUE(nva_start_addr))
		find_vmap_lowest_match_check(root, head, size, align);
#endif

	return nva_start_addr;
}

함수의 반환값은 주소 또는 encoded negative error입니다. 책의 예전 구현이 실패 시 vend를 반환한 것과 다릅니다. 현재는 후보가 없으면 -ENOENT, 뒤의 bound 검사가 실패하면 -ERANGE가 나올 수 있고, 상위에서는 IS_ERR_VALUE()로 이를 구별합니다. debug 비교는 성공한 주소에만 실행하는 조건입니다.

정렬 뒤에도 들어가는지 검사합니다

예를 들어 hole이 [0x1000, 0x7000)이고 요청 크기가 0x4000, alignment가 0x4000이면 시작을 0x4000으로 올려야 합니다. 끝은 0x8000이 되어 hole을 넘습니다. 단순 길이 0x6000만 비교하면 이 실패를 놓칩니다.

is_within_this_va()는 hole 시작과 vstart 중 더 높은 쪽을 정렬합니다. 이어 시작+크기의 wrap, 정렬 결과가 vstart보다 낮아진 wrap을 거절하고 hole의 exclusive end 안인지 검사합니다. 이것은 caller의 vend 검사와 다릅니다. 이 단계에는 그 인자가 없습니다.

is_within_this_va.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 *  Copyright (C) 1993  Linus Torvalds
 *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
 *  SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
 *  Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
 *  Numa awareness, Christoph Lameter, SGI, June 2005
 *  Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019
 */
/*
 * Linux v6.18, mm/vmalloc.c:1523-1540
 * Source: https://github.com/torvalds/linux/blob/v6.18/mm/vmalloc.c
 * Complete function: is_within_this_va
 * Body unchanged. Kernel dependencies are not bundled.
 * License text: GPL-2.0.txt
 */

static __always_inline bool
is_within_this_va(struct vmap_area *va, unsigned long size,
	unsigned long align, unsigned long vstart)
{
	unsigned long nva_start_addr;

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

	/* Can be overflowed due to big size or alignment. */
	if (nva_start_addr + size < nva_start_addr ||
			nva_start_addr < vstart)
		return false;

	return (nva_start_addr + size <= va->va_end);
}

모든 helper가 이 validation을 처음부터 반복하는 것은 아닙니다. 후속 fit 분류는 이미 유효한 후보를 받는 내부 계약을 전제로 합니다. 함수 하나를 잘라 임의 입력을 넣는 userspace 범용 interval API처럼 사용할 수 없습니다.

왼쪽 검색이 막히면 되돌아갑니다

find_vmap_lowest_match()는 충분한 크기가 있을 수 있고 vstart 제약도 만족하는 왼쪽 subtree를 먼저 봅니다. 그렇지 않으면 현재 node의 정렬된 interval을 검사하고, 실패하면 길이 요약을 이용해 오른쪽 subtree로 갑니다. 검색 길이는 필요할 때 size + align - 1로 늘려 최악의 앞쪽 padding을 고려합니다.

오른쪽도 가망이 없다고 해서 전체 tree에 hole이 없다는 뜻은 아닙니다. 부모로 되돌아가 아직 검사하지 않은 후보와 오른쪽 가지를 찾습니다. 이미 실패한 subtree를 다시 진입하지 않도록 vstart를 부모의 시작+1로 올리는 분기가 핵심입니다. 낮은 주소의 적합 구간을 찾는 first-fit 정책이지, 모든 alignment와 workload에서 fragmentation을 없애는 최적 배치 알고리즘은 아닙니다.

find_vmap_lowest_match.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 *  Copyright (C) 1993  Linus Torvalds
 *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
 *  SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
 *  Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
 *  Numa awareness, Christoph Lameter, SGI, June 2005
 *  Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019
 */
/*
 * Linux v6.18, mm/vmalloc.c:1549-1611
 * Source: https://github.com/torvalds/linux/blob/v6.18/mm/vmalloc.c
 * Complete function: find_vmap_lowest_match
 * Body unchanged. Kernel dependencies are not bundled.
 * License text: GPL-2.0.txt
 */

static __always_inline struct vmap_area *
find_vmap_lowest_match(struct rb_root *root, unsigned long size,
	unsigned long align, unsigned long vstart, bool adjust_search_size)
{
	struct vmap_area *va;
	struct rb_node *node;
	unsigned long length;

	/* Start from the root. */
	node = root->rb_node;

	/* Adjust the search size for alignment overhead. */
	length = adjust_search_size ? size + align - 1 : size;

	while (node) {
		va = rb_entry(node, struct vmap_area, rb_node);

		if (get_subtree_max_size(node->rb_left) >= length &&
				vstart < va->va_start) {
			node = node->rb_left;
		} else {
			if (is_within_this_va(va, size, align, vstart))
				return va;

			/*
			 * Does not make sense to go deeper towards the right
			 * sub-tree if it does not have a free block that is
			 * equal or bigger to the requested search length.
			 */
			if (get_subtree_max_size(node->rb_right) >= length) {
				node = node->rb_right;
				continue;
			}

			/*
			 * OK. We roll back and find the first right sub-tree,
			 * that will satisfy the search criteria. It can happen
			 * due to "vstart" restriction or an alignment overhead
			 * that is bigger then PAGE_SIZE.
			 */
			while ((node = rb_parent(node))) {
				va = rb_entry(node, struct vmap_area, rb_node);
				if (is_within_this_va(va, size, align, vstart))
					return va;

				if (get_subtree_max_size(node->rb_right) >= length &&
						vstart <= va->va_start) {
					/*
					 * Shift the vstart forward. Please note, we update it with
					 * parent's start address adding "1" because we do not want
					 * to enter same sub-tree after it has already been checked
					 * and no suitable free block found there.
					 */
					vstart = va->va_start + 1;
					node = node->rb_right;
					break;
				}
			}
		}
	}

	return NULL;
}

후보를 얻은 va_alloc()은 시작을 확정하고 caller의 vend를 검사합니다. 허용 주소 window보다 뒤에 있는 적합 hole은 이 단계에서 거절됩니다. 그 뒤 free interval을 실제로 잘라 내며, 실패한 metadata 준비를 성공 주소처럼 반환하지 않습니다.

va_alloc.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 *  Copyright (C) 1993  Linus Torvalds
 *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
 *  SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
 *  Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
 *  Numa awareness, Christoph Lameter, SGI, June 2005
 *  Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019
 */
/*
 * Linux v6.18, mm/vmalloc.c:1786-1810
 * Source: https://github.com/torvalds/linux/blob/v6.18/mm/vmalloc.c
 * Complete function: va_alloc
 * Body unchanged. Kernel dependencies are not bundled.
 * License text: GPL-2.0.txt
 */

static unsigned long
va_alloc(struct vmap_area *va,
		struct rb_root *root, struct list_head *head,
		unsigned long size, unsigned long align,
		unsigned long vstart, unsigned long vend)
{
	unsigned long nva_start_addr;
	int ret;

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

	/* Update the free vmap_area. */
	ret = va_clip(root, head, va, nva_start_addr, size);
	if (WARN_ON_ONCE(ret))
		return ret;

	return nva_start_addr;
}

남은 hole은 네 가지 모양입니다

분류에는 요청 시작과 끝이 원래 free interval의 양 끝에 각각 닿는지만 필요합니다. full fit은 node 전체 제거, left-edge fit은 free 시작을 오른쪽으로 이동, right-edge fit은 free 끝을 왼쪽으로 이동합니다. 어느 끝에도 닿지 않는 middle allocation은 두 개의 남은 hole을 만듭니다.

fit_type.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 *  Copyright (C) 1993  Linus Torvalds
 *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
 *  SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
 *  Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
 *  Numa awareness, Christoph Lameter, SGI, June 2005
 *  Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019
 */
/*
 * Linux v6.18, mm/vmalloc.c:1652-1658
 * Source: https://github.com/torvalds/linux/blob/v6.18/mm/vmalloc.c
 * Complete enum: fit_type
 * Body unchanged. Kernel dependencies are not bundled.
 * License text: GPL-2.0.txt
 */

enum fit_type {
	NOTHING_FIT = 0,
	FL_FIT_TYPE = 1,	/* full fit */
	LE_FIT_TYPE = 2,	/* left edge fit */
	RE_FIT_TYPE = 3,	/* right edge fit */
	NE_FIT_TYPE = 4		/* no edge fit */
};

classify_va_fit_type.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 *  Copyright (C) 1993  Linus Torvalds
 *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
 *  SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
 *  Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
 *  Numa awareness, Christoph Lameter, SGI, June 2005
 *  Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019
 */
/*
 * Linux v6.18, mm/vmalloc.c:1660-1684
 * Source: https://github.com/torvalds/linux/blob/v6.18/mm/vmalloc.c
 * Complete function: classify_va_fit_type
 * Body unchanged. Kernel dependencies are not bundled.
 * License text: GPL-2.0.txt
 */

static __always_inline enum fit_type
classify_va_fit_type(struct vmap_area *va,
	unsigned long nva_start_addr, unsigned long size)
{
	enum fit_type type;

	/* Check if it is within VA. */
	if (nva_start_addr < va->va_start ||
			nva_start_addr + size > va->va_end)
		return NOTHING_FIT;

	/* Now classify. */
	if (va->va_start == nva_start_addr) {
		if (va->va_end == nva_start_addr + size)
			type = FL_FIT_TYPE;
		else
			type = LE_FIT_TYPE;
	} else if (va->va_end == nva_start_addr + size) {
		type = RE_FIT_TYPE;
	} else {
		type = NE_FIT_TYPE;
	}

	return type;
}

책에서 adjust_va_to_fit_type()이라는 이름으로 보이는 역할은 v6.18에서 va_clip()이 담당합니다. 이름뿐 아니라 error 표현과 주변 경로도 달라졌습니다. full fit에서는 free node를 unlink한 뒤 metadata를 반환합니다. 그 밖에는 interval 길이를 바꾼 뒤 augmentation을 위로 전파합니다.

middle fit에서는 왼쪽 잔여 구간을 담을 새 node가 필요합니다. per-CPU preload node를 먼저 가져오며, 없으면 GFP_NOWAIT로 제한된 allocation을 시도합니다. percpu 초기 allocation이나 preload가 없는 드문 경로도 여기로 올 수 있습니다. 이때 실패하면 -ENOMEM으로 빠져 아직 interval을 잘라 놓지 않습니다. preload에서 얻은 node는 왼쪽을, 기존 node는 오른쪽을 나타내도록 구성합니다. free-tree lock 아래서 sleepable allocation을 무제한 실행하지 않기 위한 장치입니다.

va_clip.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 *  Copyright (C) 1993  Linus Torvalds
 *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
 *  SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
 *  Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
 *  Numa awareness, Christoph Lameter, SGI, June 2005
 *  Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019
 */
/*
 * Linux v6.18, mm/vmalloc.c:1686-1784
 * Source: https://github.com/torvalds/linux/blob/v6.18/mm/vmalloc.c
 * Complete function: va_clip
 * Body unchanged. Kernel dependencies are not bundled.
 * License text: GPL-2.0.txt
 */

static __always_inline int
va_clip(struct rb_root *root, struct list_head *head,
		struct vmap_area *va, unsigned long nva_start_addr,
		unsigned long size)
{
	struct vmap_area *lva = NULL;
	enum fit_type type = classify_va_fit_type(va, nva_start_addr, size);

	if (type == FL_FIT_TYPE) {
		/*
		 * No need to split VA, it fully fits.
		 *
		 * |               |
		 * V      NVA      V
		 * |---------------|
		 */
		unlink_va_augment(va, root);
		kmem_cache_free(vmap_area_cachep, va);
	} else if (type == LE_FIT_TYPE) {
		/*
		 * Split left edge of fit VA.
		 *
		 * |       |
		 * V  NVA  V   R
		 * |-------|-------|
		 */
		va->va_start += size;
	} else if (type == RE_FIT_TYPE) {
		/*
		 * Split right edge of fit VA.
		 *
		 *         |       |
		 *     L   V  NVA  V
		 * |-------|-------|
		 */
		va->va_end = nva_start_addr;
	} else if (type == NE_FIT_TYPE) {
		/*
		 * Split no edge of fit VA.
		 *
		 *     |       |
		 *   L V  NVA  V R
		 * |---|-------|---|
		 */
		lva = __this_cpu_xchg(ne_fit_preload_node, NULL);
		if (unlikely(!lva)) {
			/*
			 * For percpu allocator we do not do any pre-allocation
			 * and leave it as it is. The reason is it most likely
			 * never ends up with NE_FIT_TYPE splitting. In case of
			 * percpu allocations offsets and sizes are aligned to
			 * fixed align request, i.e. RE_FIT_TYPE and FL_FIT_TYPE
			 * are its main fitting cases.
			 *
			 * There are a few exceptions though, as an example it is
			 * a first allocation (early boot up) when we have "one"
			 * big free space that has to be split.
			 *
			 * Also we can hit this path in case of regular "vmap"
			 * allocations, if "this" current CPU was not preloaded.
			 * See the comment in alloc_vmap_area() why. If so, then
			 * GFP_NOWAIT is used instead to get an extra object for
			 * split purpose. That is rare and most time does not
			 * occur.
			 *
			 * What happens if an allocation gets failed. Basically,
			 * an "overflow" path is triggered to purge lazily freed
			 * areas to free some memory, then, the "retry" path is
			 * triggered to repeat one more time. See more details
			 * in alloc_vmap_area() function.
			 */
			lva = kmem_cache_alloc(vmap_area_cachep, GFP_NOWAIT);
			if (!lva)
				return -ENOMEM;
		}

		/*
		 * Build the remainder.
		 */
		lva->va_start = va->va_start;
		lva->va_end = nva_start_addr;

		/*
		 * Shrink this VA to remaining size.
		 */
		va->va_start = nva_start_addr + size;
	} else {
		return -EINVAL;
	}

	if (type != FL_FIT_TYPE) {
		augment_tree_propagate_from(va);

		if (lva)	/* type == NE_FIT_TYPE */
			insert_vmap_area_augment(lva, &va->rb_node, root, head);
	}

	return 0;
}

busy tree에 게시하는 위치

주소를 차지한 새 vmap_area는 busy 구조에 들어갑니다. find_va_links()는 새 interval 끝이 기존 시작 이하이면 왼쪽, 새 시작이 기존 끝 이상이면 오른쪽으로 갑니다. 둘 다 아니라면 overlap이며 WARN 후 NULL을 반환합니다. 주석에 BUG라는 표현이 남아 있어도 실제 현재 분기는 이 WARN과 반환값으로 읽어야 합니다.

빈 root는 실패가 아닙니다. parent를 NULL로 두고 root slot의 주소를 돌려주면 caller가 거기에 첫 node를 연결할 수 있습니다. 이미 존재하는 subtree에서 시작하는 내부 호출은 from을 사용하며 그 입력 전제도 따로 있습니다. 반환된 link는 entry 자체가 아니라 새 node를 연결할 pointer slot입니다.

find_va_links.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 *  Copyright (C) 1993  Linus Torvalds
 *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
 *  SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
 *  Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
 *  Numa awareness, Christoph Lameter, SGI, June 2005
 *  Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019
 */
/*
 * Linux v6.18, mm/vmalloc.c:1161-1206
 * Source: https://github.com/torvalds/linux/blob/v6.18/mm/vmalloc.c
 * Complete function: find_va_links
 * Body unchanged. Kernel dependencies are not bundled.
 * License text: GPL-2.0.txt
 */

static __always_inline struct rb_node **
find_va_links(struct vmap_area *va,
	struct rb_root *root, struct rb_node *from,
	struct rb_node **parent)
{
	struct vmap_area *tmp_va;
	struct rb_node **link;

	if (root) {
		link = &root->rb_node;
		if (unlikely(!*link)) {
			*parent = NULL;
			return link;
		}
	} else {
		link = &from;
	}

	/*
	 * Go to the bottom of the tree. When we hit the last point
	 * we end up with parent rb_node and correct direction, i name
	 * it link, where the new va->rb_node will be attached to.
	 */
	do {
		tmp_va = rb_entry(*link, struct vmap_area, rb_node);

		/*
		 * During the traversal we also do some sanity check.
		 * Trigger the BUG() if there are sides(left/right)
		 * or full overlaps.
		 */
		if (va->va_end <= tmp_va->va_start)
			link = &(*link)->rb_left;
		else if (va->va_start >= tmp_va->va_end)
			link = &(*link)->rb_right;
		else {
			WARN(1, "vmalloc bug: 0x%lx-0x%lx overlaps with 0x%lx-0x%lx\n",
				va->va_start, va->va_end, tmp_va->va_start, tmp_va->va_end);

			return NULL;
		}
	} while (*link);

	*parent = &tmp_va->rb_node;
	return link;
}

insert_vmap_area.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 *  Copyright (C) 1993  Linus Torvalds
 *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
 *  SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
 *  Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
 *  Numa awareness, Christoph Lameter, SGI, June 2005
 *  Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019
 */
/*
 * Linux v6.18, mm/vmalloc.c:1379-1389
 * Source: https://github.com/torvalds/linux/blob/v6.18/mm/vmalloc.c
 * Complete function: insert_vmap_area
 * Body unchanged. Kernel dependencies are not bundled.
 * License text: GPL-2.0.txt
 */

static void
insert_vmap_area(struct vmap_area *va,
	struct rb_root *root, struct list_head *head)
{
	struct rb_node **link;
	struct rb_node *parent;

	link = find_va_links(va, root, NULL, &parent);
	if (link)
		link_va(va, root, parent, link, head);
}

insert_vmap_area()는 link를 찾은 경우에만 link_va()로 tree와 list에 연결합니다. 이 함수 자체가 allocation의 lock을 전부 획득해 주는 것은 아닙니다. 바로 위 caller가 어느 busy tree와 lock을 선택했는지 확인해야 합니다.

retry가 보장하는 것과 보장하지 않는 것

상위 alloc_vmap_area()는 size가 0인지, page 단위인지, alignment가 power of two인지 검사합니다. 책의 해당 자리에는 BUG_ON()들이 있지만 현재는 ERR_PTR(-EINVAL)을 반환합니다. 초기화 전이면 -EBUSY, metadata가 부족하면 -ENOMEM입니다. 우선 node pool을 시도하고 필요할 때 global free-tree lock 아래 위 검색을 수행합니다. cond_resched()는 그 느린 경로에서 lock을 놓은 뒤 실행합니다.

성공하면 주소·크기·vm pointer를 결합하고 주소에 맞는 vmap-node의 busy lock 아래 게시합니다. KASAN shadow 준비가 실패하면 이미 얻은 VA를 반환하고 그 error를 돌려줍니다. 일반 주소 검색 실패에서는 reclaim·purge 후 한 번 더 시도하고, 여전히 실패하면 blocking notifier가 freed > 0을 보고했는지 봅니다. 반환된 자원이 있으면 purge 상태를 초기화하고 다시 시도합니다. 결국 실패하면 NOWARN·rate-limit 조건에 맞게 경고하고 metadata를 반환한 뒤 -EBUSY로 끝납니다.

alloc_vmap_area.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 *  Copyright (C) 1993  Linus Torvalds
 *  Support of BIGMEM added by Gerhard Wichert, Siemens AG, July 1999
 *  SMP-safe vmalloc/vfree/ioremap, Tigran Aivazian <tigran@veritas.com>, May 2000
 *  Major rework to support vmap/vunmap, Christoph Hellwig, SGI, August 2002
 *  Numa awareness, Christoph Lameter, SGI, June 2005
 *  Improving global KVA allocator, Uladzislau Rezki, Sony, May 2019
 */
/*
 * Linux v6.18, mm/vmalloc.c:2009-2127
 * Source: https://github.com/torvalds/linux/blob/v6.18/mm/vmalloc.c
 * Complete function: alloc_vmap_area
 * Body unchanged. Kernel dependencies are not bundled.
 * License text: GPL-2.0.txt
 */

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,
				unsigned long va_flags, struct vm_struct *vm)
{
	struct vmap_node *vn;
	struct vmap_area *va;
	unsigned long freed;
	unsigned long addr;
	unsigned int vn_id;
	int purged = 0;
	int ret;

	if (unlikely(!size || offset_in_page(size) || !is_power_of_2(align)))
		return ERR_PTR(-EINVAL);

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

	/* Only reclaim behaviour flags are relevant. */
	gfp_mask = gfp_mask & GFP_RECLAIM_MASK;
	might_sleep();

	/*
	 * If a VA is obtained from a global heap(if it fails here)
	 * it is anyway marked with this "vn_id" so it is returned
	 * to this pool's node later. Such way gives a possibility
	 * to populate pools based on users demand.
	 *
	 * On success a ready to go VA is returned.
	 */
	va = node_alloc(size, align, vstart, vend, &addr, &vn_id);
	if (!va) {
		va = kmem_cache_alloc_node(vmap_area_cachep, gfp_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);
	}

retry:
	if (IS_ERR_VALUE(addr)) {
		preload_this_cpu_lock(&free_vmap_area_lock, gfp_mask, node);
		addr = __alloc_vmap_area(&free_vmap_area_root, &free_vmap_area_list,
			size, align, vstart, vend);
		spin_unlock(&free_vmap_area_lock);

		/*
		 * This is not a fast path.  Check if yielding is needed. This
		 * is the only reschedule point in the vmalloc() path.
		 */
		cond_resched();
	}

	trace_alloc_vmap_area(addr, size, align, vstart, vend, IS_ERR_VALUE(addr));

	/*
	 * If an allocation fails, the error value is
	 * returned. Therefore trigger the overflow path.
	 */
	if (IS_ERR_VALUE(addr))
		goto overflow;

	va->va_start = addr;
	va->va_end = addr + size;
	va->vm = NULL;
	va->flags = (va_flags | vn_id);

	if (vm) {
		vm->addr = (void *)va->va_start;
		vm->size = va_size(va);
		va->vm = vm;
	}

	vn = addr_to_node(va->va_start);

	spin_lock(&vn->busy.lock);
	insert_vmap_area(va, &vn->busy.root, &vn->busy.head);
	spin_unlock(&vn->busy.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, gfp_mask);
	if (ret) {
		free_vmap_area(va);
		return ERR_PTR(ret);
	}

	return va;

overflow:
	if (!purged) {
		reclaim_and_purge_vmap_areas();
		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("vmalloc_node_range for size %lu failed: Address range restricted to %#lx - %#lx\n",
				size, vstart, vend);

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

retry는 허용 window의 길이를 늘리거나 alignment를 무시해 주지 않습니다. RAM이 넉넉해도 특정 주소 구간 안에 적합 hole이 없으면 실패할 수 있습니다. 주소 검색, metadata, backing page와 page-table allocation을 나누어 보아야 실패 지점도 정확히 분류할 수 있습니다.

참고 자료