memblock: buddy 이전의 물리 메모리 장부

무엇을 관리하는가

memblock은 부팅 초기에 사용하는 물리 메모리 구간 관리자다. 이 시점에는 buddy allocator가 아직 사용 가능한 모든 struct page와 zone을 준비하지 못했고, slab allocator도 정상적인 커널 heap 역할을 할 수 없다. 그런데 page table, NUMA 자료구조, sparse memory metadata, initrd 처리에는 이미 메모리가 필요하다. memblock은 이 짧은 공백을 메운다.

일반적인 free-list allocator처럼 “남은 블록 목록”을 직접 보관하지 않는다는 점이 가장 중요하다. memblock은 펌웨어에서 확인한 RAM을 memory 배열에, 현재 쓰면 안 되는 물리 구간을 reserved 배열에 기록한다. 할당 가능한 구간은 두 배열의 차집합으로 그때그때 계산한다.

소스 코드 위치

아래 줄 번호는 Greg Kroah-Hartman의 Linux v6.18.37 tag를 기준으로 한다. 코드가 다른 stable patch level이라면 함수 이름은 같아도 줄 번호는 조금 달라질 수 있다.

자료구조와 불변 조건

전역 객체 memblock 안에는 memory와 reserved라는 두 memblock_type이 들어 있다. 각 type은 memblock_region의 연속 배열을 가리킨다. linked list가 아니라 배열이므로 binary search와 순차 순회에는 유리하고, 중간 삽입·삭제에는 memmove()가 필요하다. 부팅 초기에 region 수가 비교적 작다는 전제에 맞춘 선택이다.

arm64 부팅 경로

arm64에서는 DTB를 확인하는 순간부터 memblock이 쓰인다. setup_machine_fdt()는 DTB 자체의 물리 구간을 먼저 예약하고, early_init_dt_scan()이 memory node를 읽어 memblock_add()로 RAM bank를 등록한다. 이후 arm64_memblock_init()이 CPU의 물리 주소 폭과 linear map 크기에 맞지 않는 RAM을 잘라 내고 kernel image와 initrd를 예약한다.

핵심 원본 코드

긴 함수를 통째로 옮기기보다 알고리즘이 갈리는 부분을 발췌했다. 각 코드 아래의 라인별 주석은 발췌문 내부 번호와 실제 source 위치를 함께 읽도록 구성했다.

struct memblock_region {
	phys_addr_t base;
	phys_addr_t size;
	enum memblock_flags flags;
#ifdef CONFIG_NUMA
	int nid;
#endif
};

struct memblock_type {
	unsigned long cnt;
	unsigned long max;
	phys_addr_t total_size;
	struct memblock_region *regions;
	char *name;
};

struct memblock {
	bool bottom_up;
	phys_addr_t current_limit;
	struct memblock_type memory;
	struct memblock_type reserved;
};

BUG_ON(type->cnt >= type->max);
memmove(rgn + 1, rgn, (type->cnt - idx) * sizeof(*rgn));
rgn->base = base;
rgn->size = size;
rgn->flags = flags;
memblock_set_region_node(rgn, nid);
type->cnt++;
type->total_size += size;

if (!nr_new)
	return 0;

if (!insert) {
	while (type->cnt + nr_new > type->max)
		if (memblock_double_array(type, obase, size) < 0)
			return -ENOMEM;
	insert = true;
	goto repeat;
} else {
	memblock_merge_regions(type, start_rgn, end_rgn);
	return 0;
}

if (rbase < base) {
	rgn->base = base;
	rgn->size -= base - rbase;
	type->total_size -= base - rbase;
	memblock_insert_region(type, idx, rbase, base - rbase,
			       memblock_get_region_node(rgn), rgn->flags);
} else if (rend > end) {
	rgn->base = end;
	rgn->size -= end - rbase;
	type->total_size -= end - rbase;
	memblock_insert_region(type, idx--, rbase, end - rbase,
			       memblock_get_region_node(rgn), rgn->flags);
}

r = &type_b->regions[idx_b];
r_start = idx_b ? r[-1].base + r[-1].size : 0;
r_end = idx_b < type_b->cnt ? r->base : PHYS_ADDR_MAX;

if (r_start >= m_end)
	break;
if (m_start < r_end) {
	if (out_start)
		*out_start = max(m_start, r_start);
	if (out_end)
		*out_end = min(m_end, r_end);
	return;
}

for_each_free_mem_range_reverse(i, nid, flags, &this_start,
					&this_end, NULL) {
	this_start = clamp(this_start, start, end);
	this_end = clamp(this_end, start, end);

	if (this_end < size)
		continue;

	cand = round_down(this_end - size, align);
	if (cand >= this_start)
		return cand;
}

found = memblock_find_in_range_node(size, align, start, end, nid,
				    flags);
if (found && !__memblock_reserve(found, size, nid,
					MEMBLOCK_RSRV_KERN))
	goto done;

if (numa_valid_node(nid) && !exact_nid) {
	found = memblock_find_in_range_node(size, align, start, end,
					    NUMA_NO_NODE, flags);
	if (found && !memblock_reserve_kern(found, size))
		goto done;
}

memblock_add(base, size);
memblock_clear_nomap(base, size);
memblock_reserve(base, size);

memblock_reserve(__pa_symbol(_text), _end - _text);
if (IS_ENABLED(CONFIG_BLK_DEV_INITRD) && phys_initrd_size) {
	initrd_start = __phys_to_virt(phys_initrd_start);
	initrd_end = initrd_start + phys_initrd_size;
}

early_init_fdt_scan_reserved_mem();

for_each_free_mem_range(i, NUMA_NO_NODE, MEMBLOCK_NONE,
			&start, &end, NULL)
	count += __free_memory_core(start, end);

void __init memblock_free_all(void)
{
	unsigned long pages;

	free_unused_memmap();
	reset_all_zones_managed_pages();
	pages = free_low_memory_core_early();
	totalram_pages_add(pages);
}

구간 추가와 예약

memblock_add()와 memblock_reserve()는 모두 내부적으로 memblock_add_range()를 사용한다. 차이는 어느 type에 넣느냐뿐이다. 전자는 memblock.memory, 후자는 memblock.reserved를 대상으로 한다.

기존 구간과 겹치면 새 속성으로 덮어쓰지 않는다

새 구간은 기존 region과 겹쳐도 허용된다. 그러나 겹친 부분의 기존 flags와 node ID를 바꾸지는 않는다. 아직 어떤 기존 region에도 포함되지 않은 조각만 새 entry로 삽입한다. 이 규칙 덕분에 먼저 등록된 더 구체적인 속성이 뒤의 넓은 범위 추가로 사라지지 않는다.

왜 먼저 세고 나중에 삽입하는가

memblock_add_range()는 최악의 경우 새 구간 하나가 기존 region 사이의 여러 빈틈을 모두 채워 많은 entry를 만들 수 있다. 배열 공간이 충분하다고 확정할 수 없으면 첫 순회에서 필요한 entry 수 nr_new만 센다. 공간이 부족하면 memblock_double_array()가 더 큰 배열을 확보하고 기존 내용을 복사한 뒤, 두 번째 순회에서 실제로 삽입한다.

reserved 배열을 키우는 메모리 자체도 아직 memblock에서 가져올 수 있다. 새로 예약하려던 구간과 region 배열 저장 공간이 겹치면 예약 정보가 자기 자신을 덮게 된다. 그래서 memblock_double_array()는 new_area_start와 new_area_size를 받아 그 구간을 피해 새 배열을 놓고, 배열을 옮긴 뒤 그 저장 공간도 MEMBLOCK_RSRV_KERN으로 예약한다.

병합 조건

하나라도 다르면 두 region을 유지한다. 반대로 겹침이 남아 있다면 BUG_ON(this->base + this->size > next->base)가 발생한다. 즉, merge 함수는 정렬·비중첩 불변 조건을 확인하는 방어선이기도 하다.

분할·제거·해제

배열 중간의 일부만 지우려면 바로 entry를 삭제할 수 없다. 먼저 요청 범위의 시작과 끝이 region 경계가 되도록 memblock_isolate_range()가 자른다. 그 결과 [start_rgn, end_rgn) index 범위에는 삭제 대상만 남고, memblock_remove_range()가 뒤에서 앞으로 entry를 제거한다.

memblock_remove()와 memblock_free()는 대상 배열이 다르다

free range 계산

for_each_free_mem_range()는 __next_mem_range()에 memory를 포함 집합 type_a로, reserved를 제외 집합 type_b로 넘긴다. 함수는 memory entry의 index를 64-bit iterator 하위 32-bit에, reserved 사이 빈 공간의 index를 상위 32-bit에 보관한다.

두 배열이 모두 주소 순으로 정렬되어 있기 때문에 이미 끝난 구간으로 되돌아갈 필요가 없다. memory 끝이 먼저 오면 memory index를, 빈 공간 끝이 먼저 오면 reserved-gap index를 전진시킨다. 따라서 모든 entry를 한 번씩 훑는 선형 순회가 가능하다.

flags와 NUMA 조건은 교집합 계산 전에 should_skip_region()에서 memory region 단위로 적용된다. 따라서 “주소상 free”여도 NOMAP이거나 다른 NUMA node인 구간은 요청 조건에 따라 건너뛸 수 있다.

물리 주소 배정

allocation은 두 단계다. 먼저 free iterator에서 후보 주소를 찾고, 그 물리 범위를 reserved 배열에 넣어 다음 요청이 재사용하지 못하게 한다. 후보 탐색 성공과 reserve 성공이 모두 성립해야 할당 성공이다.

top-down과 bottom-up

반환형을 보고 API 계열을 구분한다

memblock_alloc_internal()은 physical allocation 결과를 phys_to_virt()로 변환한다. 또한 max_addr를 current_limit보다 높게 사용할 수 없게 자르고, 선호한 min_addr 위에서 실패하면 0부터 다시 시도한다. 이 fallback 때문에 min_addr를 절대 하한으로 해석하면 안 된다.

memblock_find_in_range_node()는 시작 주소를 최소 PAGE_SIZE로 올린다. 성공값 0을 실패 표시로 사용하므로 물리 주소 0의 첫 page를 allocation 후보에서 의도적으로 제외한다.

주소 계산 예제

다음은 32 MiB RAM을 가진 단순 보드에서 kernel, DTB, initrd를 예약한 뒤 1 MiB를 2 MiB 정렬로 top-down 할당하는 예다. 실제 보드의 주소는 다르지만 계산 방법은 같다.

flags와 NUMA

flags는 단순 표식이 아니라 region 병합 가능 여부와 allocation 후보 선택을 바꾼다. should_skip_region()은 memory type을 순회할 때 요청 flags와 region 속성을 비교한다.

NUMA node 선택

memblock_add_node()는 region에 node ID를 바로 넣는다. 뒤늦게 node 정보를 알게 되면 memblock_set_node()가 대상 범위를 isolate한 후 내부 region의 nid를 바꾸고 다시 병합한다. 즉, node 경계가 기존 region 한가운데를 통과하면 region이 여러 entry로 나뉜다.

memblock_alloc_range_nid()의 exact_nid가 거짓이면 지정 node에서 실패한 뒤 NUMA_NO_NODE로 전체 memory를 다시 찾는다. 반대로 exact 요청은 다른 node로 넘어가지 않는다. bring-up 중 특정 node에 RAM이 없는 구성에서는 이 차이가 early allocation 실패 여부를 바꾼다.

buddy allocator 인계

bootmem_init()은 이름과 달리 모든 free page를 즉시 buddy에 넣는 함수가 아니다. arm64에서는 PFN 범위 설정, NUMA 초기화, sparse memory, zone size, CMA와 crashkernel 예약 등을 수행한다. 이 과정의 여러 함수가 여전히 memblock allocation을 사용한다.

실제 인계는 generic mm_core_init() 안의 memblock_free_all()에서 일어난다. 먼저 사용하지 않는 memmap 영역을 정리하고 zone의 managed page 수를 다시 계산할 준비를 한다. 이어서 for_each_free_mem_range()가 반환한 각 byte range를 PFN_UP(start)과 PFN_DOWN(end)로 page 경계 안쪽에 맞춘 뒤 __free_pages_memory()를 통해 buddy에 넣는다.

CONFIG_ARCH_KEEP_MEMBLOCK이 꺼진 일반 구성에서는 초기화가 끝난 뒤 memblock 배열을 폐기할 수 있다. memblock API를 slab 준비 뒤에 실수로 호출하면 memblock_alloc_range_nid()가 WARN_ON_ONCE(slab_is_available())로 잡고 kzalloc_node() fallback을 사용한다. 이는 정상 사용 경로라기보다 init-only API 오용을 드러내기 위한 방어다.

부팅 로그로 확인

memblock의 핵심 작업은 tracefs가 준비되기 전에 일어난다. 따라서 런타임 function tracer보다 kernel command line의 memblock=debug와 earlycon이 먼저다.

console=ttyAMA0,115200 earlycon memblock=debug loglevel=8

early_memblock()은 memblock 인자에 debug 문자열이 있으면 전역 memblock_debug를 켠다. 이후 memblock_dbg()가 add, reserve, remove, allocation의 주소와 caller를 출력하고, arm64 bootmem_init() 끝의 memblock_dump_all()이 전체 배열을 보여 준다.

MEMBLOCK configuration:
memory size =
reserved size =
memblock_add:
memblock_reserve:
memblock_alloc_range_nid:

자주 틀리는 부분

코드 검토 항목

• 새 RAM bank와 reservation이 모두 byte overflow 없이 [base, base + size)로 표현되는가?
• 새 구간 추가 후 region 배열이 base 오름차순이고 같은 type 내부에 겹침이 남지 않는가?
• 서로 붙은 region의 flags와 NUMA node가 같은 경우 병합되는가?
• 배열 resize 전에 firmware reserved-memory와 initrd 위치를 충분히 알고 있는가?
• allocation 후보를 찾은 뒤 반드시 같은 범위를 reserved에 넣는가?
• 호출자가 원하는 값이 물리 주소인지 linear-map virtual pointer인지 반환형으로 확인했는가?
• min_addr, current_limit, NUMA fallback, mirror fallback 중 어느 조건이 절대 조건이고 어느 조건이 선호 조건인지 구분했는가?
• arm64의 physical address width와 linear map 크기로 잘려 나가는 RAM이 있는가?
• kernel, DTB, initrd, page table, CMA, crashkernel, reserved-memory가 buddy 인계 전에 모두 예약되어 있는가?
• 초기 free와 late free를 구분하고 buddy가 준비되기 전 page allocator API를 호출하지 않는가?