Memory · Linux 6.18.37 LTS · source + diagram note

buddy allocator

최신 LTS 기준: kernel.org longterm 6.18.37 기준으로 파일 위치와 링크를 맞춘 원본 코드 분석 노트입니다. zone, free_area, order 기반 page 할당.

전체 흐름

Buddy allocator는 가상 주소 변환이 아니라 물리 페이지 블록을 zone별·order별로 관리합니다. order n의 블록은 연속된 2^n pages입니다. GFP·NUMA/cpuset 제약과 watermark 정책에 따라 후보 zone을 훑습니다.

그림 1. 요청, 후보 저장소, 첫 시도 실패 후의 분기
요청__alloc_pages_noprof()GFP·order와 이용 가능한 zone 결정
첫 시도PCP 또는 zone.free_area허용 order는 per-CPU pageset에 적중할 수 있고, buddy list에서는 더 큰 블록을 분할할 수 있음
실패한 경우__alloc_pages_slowpath()조건에 따라 재시도·reclaim·compaction·실패. 모든 단계를 항상 거치지는 않음

할당 뒤 해제까지는 caller의 사용과 참조 종료가 있습니다. 할당 함수가 해제 함수를 곧바로 호출한다는 그림이 아닙니다.

고정 mm/page_alloc.c SHA-256 4274e384a11c5a74fecc48adec30fd324bc2427bc3d1033c6ffd6ceef9a18fd2. 내부 할당: 5203–5264 · buddy 후보: 1927–1949. 그림과 PFN은 설명용 예시입니다.

소스 코드 위치

먼저 확인할 Linux 6.18.37 LTS 소스 파일

원본 코드:
Linux 6.18.37 LTS: mm/page_alloc.c
Linux 6.18.37 LTS: include/linux/mmzone.h
Linux 6.18.37 LTS: include/linux/page-flags.h

읽는 순서: mm/page_alloc.c에서 할당의 get_page_from_freelist()·rmqueue()와 반환의 PCP·buddy 분기를 먼저 대조합니다. mmzone.h에서는 zone, free_area, per-CPU pageset의 자료구조를, page flag 정의에서는 free block 표시를 확인합니다.

대표 코드: 공개 호출과 실제 구현

__alloc_pages() 매크로와 구현

원본 코드: include/linux/gfp.h, 225–227행
struct page *__alloc_pages_noprof(gfp_t gfp, unsigned int order, int preferred_nid,
		nodemask_t *nodemask);
#define __alloc_pages(...)			alloc_hooks(__alloc_pages_noprof(__VA_ARGS__))
원본 코드: mm/page_alloc.c, 5268–5278행
struct page *__alloc_pages_noprof(gfp_t gfp, unsigned int order,
		int preferred_nid, nodemask_t *nodemask)
{
	struct page *page;

	page = __alloc_frozen_pages_noprof(gfp, order, preferred_nid, nodemask);
	if (page)
		set_page_refcounted(page);
	return page;
}
EXPORT_SYMBOL(__alloc_pages_noprof);

확인 사항: 공개 이름 __alloc_pages는 alloc_hooks()로 구현 함수 __alloc_pages_noprof()를 감싸는 매크로입니다. 구현은 __alloc_frozen_pages_noprof()의 결과가 있으면 set_page_refcounted()를 호출합니다. 그 아래 경로는 get_page_from_freelist()의 첫 시도와 slowpath:5228–5264를 따릅니다. 반환된 page는 caller가 소유하며, free list의 블록 존재가 함수의 사후 조건은 아닙니다.

__free_pages() 이후의 PCP / buddy 갈림길

원본 코드: mm/page_alloc.c, 5356–5359행
void __free_pages(struct page *page, unsigned int order)
{
	___free_pages(page, order, FPI_NONE);
}
원본 코드: mm/page_alloc.c, 2934–2946행
static void __free_frozen_pages(struct page *page, unsigned int order,
				fpi_t fpi_flags)
{
	unsigned long __maybe_unused UP_flags;
	struct per_cpu_pages *pcp;
	struct zone *zone;
	unsigned long pfn = page_to_pfn(page);
	int migratetype;

	if (!pcp_allowed_order(order)) {
		__free_pages_ok(page, order, fpi_flags);
		return;
	}
원본 코드: mm/page_alloc.c, 2973–2982행
	pcp_trylock_prepare(UP_flags);
	pcp = pcp_spin_trylock(zone->per_cpu_pageset);
	if (pcp) {
		free_frozen_page_commit(zone, pcp, page, migratetype, order, fpi_flags);
		pcp_spin_unlock(pcp);
	} else {
		free_one_page(zone, page, pfn, order, fpi_flags);
	}
	pcp_trylock_finish(UP_flags);
}

확인 사항: __free_pages()는 ___free_pages()를 호출합니다. 5311–5333행에서 put_page_testzero(page)가 참이면 내부 free helper로 가고, 거짓이어도 non-compound high-order의 !head 경로는 tail page들을 따로 반환할 수 있습니다. pcp_allowed_order()가 거짓이면 바로 __free_pages_ok()로 갑니다. 일반적인 허용 order 경로에서는 PCP lock 획득 시 per-CPU list, 실패 시 free_one_page()로 가지만, MIGRATE_ISOLATE와 PREEMPT_RT/NMI 예외:2958–2971는 lock 이전에 별도 분기합니다. free_frozen_pages()는 2984–2987행의 별도 진입이며 __free_pages()가 직접 호출하는 이름은 아닙니다.

위 발췌는 고정 v6.18.37 원문과 행 단위로 대조했습니다. mm/page_alloc.c SHA-256: 4274e384a11c5a74fecc48adec30fd324bc2427bc3d1033c6ffd6ceef9a18fd2; include/linux/gfp.h SHA-256: 3a42404c7d5daabe13d27e21972b7d649c0d6a5db4a7be469e6db436ea4e25e2.

함수별 분석

아래 행은 한 직선의 함수 체인이 아니라 조건부 경로와 별도 해제 시점을 구분합니다.

함수 경계와 관찰할 상태
경로역할판별점
__alloc_pages_noprof()제약을 준비하고 get_page_from_freelist()의 첫 시도 후 필요하면 slowpath로 이동성공한 page를 caller에 반환; free block 존재는 사후 조건이 아님
rmqueue()PCP 또는 해당 zone의 buddy free list에서 요청 order의 블록 확보PCP 적중 여부와 대상 zone·migratetype 확인
page_del_and_expand() / expand()큰 order를 꺼낸 경우 남는 절반 블록을 낮은 order list에 등록모든 요청에서 split하지 않음
__alloc_pages_slowpath()조건부 재시도·reclaim·compactionGFP의 __GFP_DIRECT_RECLAIM, gfp_compaction_allowed(), order, 조기 종료 분기 확인
__free_pages() → ___free_pages()caller가 사용을 마친 뒤 PCP 보관 또는 직접 buddy 병합 시도PCP에 있으면 free_area에 즉시 나타나지 않음

__alloc_pages는 계측용 매크로이고 __alloc_pages_noprof()가 구현 함수입니다. __free_pages()는 ___free_pages()를 호출합니다. 내부 __free_frozen_pages()와 별도 진입 함수 free_frozen_pages()를 같은 직접 호출 체인으로 읽지 않습니다.

고정 mm/page_alloc.c SHA-256 4274e384a11c5a74fecc48adec30fd324bc2427bc3d1033c6ffd6ceef9a18fd2. 분할 후보: 1927–1949 · PCP 해제: 2934–2982 · slowpath: 4672–4881. 그림과 PFN은 설명용 예시입니다.

위 도식은 성공해 반환된 페이지의 사용 생애를 구분합니다. 실제 첫 할당·slowpath는 __alloc_frozen_pages_noprof()가 수행하고 __alloc_pages_noprof()는 성공한 페이지의 참조 수를 설정합니다. 내부 메모리 계정 부과가 실패하면 free_frozen_pages()로 되돌린 뒤 NULL을 반환하므로, 할당 함수 안의 오류 정리가 없는 것은 아닙니다. 할당 구현과 참조 수 설정

구조체와 필드

네 이름은 실행 순서가 아니라 서로 다른 저장·분류 정보입니다.

free block을 읽을 때 구분할 정보
자료뜻주의
zone.free_area[order]order별 free_list[migratetype]와 nr_freenr_free는 page 수가 아니라 그 order의 모든 migratetype list의 free 블록 수
page->private / PageBuddybuddy free list 블록 head의 order와 free 표시할당 page나 PCP 보관 page에 일반화하지 않음
pageblock migratetypepageblock의 이동성·격리 분류; fallback과 병합 경계에 관여블록 크기 지수인 order와 다름
per-CPU pageset (PCP)허용 order의 per-CPU free page 보관소/proc/buddyinfo의 order별 수치만으로 판단 불가

고정 mm/page_alloc.c SHA-256 4274e384a11c5a74fecc48adec30fd324bc2427bc3d1033c6ffd6ceef9a18fd2. 표시·리스트: 752–909 · 병합: 978–1059. 그림과 PFN은 설명용 예시입니다.

실행 단계와 상태 변화

한 zone의 MIGRATE_MOVABLE order 3 free block이 PFN 256–263에 하나만 있다고 가정합니다. order 0 요청이 PFN 256을 얻는 경우이며 guard page·PCP·타입 fallback은 이 작은 예시에서 제외합니다.

8 pages 한 블록 → 1 page 할당 → 직접 buddy 해제
시점free block 배치order 3 / 2 / 1 / 0의 nr_free
처음PFN 256–263 한 블록1 / 0 / 0 / 0
PFN 256 할당 후260–263, 258–259, 257이 free; 256은 caller 소유0 / 1 / 1 / 1
PFN 256 직접 반환, 모두 병합 가능257 → 258–259 → 260–263과 차례로 병합1 / 0 / 0 / 0

마지막 행은 __free_one_page()까지 직접 도착하고 같은 order buddy가 모두 free이며 병합 제약을 통과한 경우입니다. PCP에 보관되거나 buddy가 사용 중·다른 order·병합 불가 타입이면 그 지점에서 멈춥니다. 할당 후 free page 수는 4 + 2 + 1 = 7; nr_free 값만 더해 구하지 않습니다.

아래 free_area 계수와 병합 중단 도해는 같은 예시를 리스트 슬롯별로 더 자세히 풉니다.

고정 mm/page_alloc.c SHA-256 4274e384a11c5a74fecc48adec30fd324bc2427bc3d1033c6ffd6ceef9a18fd2. 병합: 978–1059 · 분할: 1740–1777 · 후보: 1927–1949. 그림과 PFN은 설명용 예시입니다.

free_area의 계수 변화

위의 그림 1은 할당 요청과 후보 저장소를 구분하고, 상태표는 분할·반환의 숫자를 요약합니다. 여기서는 리스트 슬롯·nr_free의 전후 변화와 병합 중단 조건을 확인합니다. PFN 256–263 한 블록만 있는 zone에서 order 0 하나를 할당하는 가상 예시이며, 이 zone에는 다른 free block이 없고 한 migratetype(MIGRATE_MOVABLE)의 list만 채워진 것으로 가정합니다.

그림을 가로로 이동해 읽거나 free list 계수·중단 조건 도해 크게 열기 ↗

가상 PFN 256–263의 order 3 한 블록을 order 0 하나로 할당하면 order 3의 nr_free는 1에서 0, order 2·1·0은 각각 0에서 1로 바뀐다. 직접 buddy 경로에서 다시 모두 합쳐지면 역전된다. buddy가 PageBuddy도 guard도 아니거나 order가 다르거나 pageblock 타입이 병합 불가능할 때는 현재 order에서 멈춘다.
도해 · free list 원장과 병합의 세 정지 조건. nr_free badge는 해당 order의 블록 수입니다. 빈 칸, 색상, PFN은 설명용이며 실제 메모리 배치나 실행 trace가 아닙니다.
직접 buddy 해제 경로에서 한 order마다 확인할 조건
검사 결과코드 분기free list와 nr_free 결과
buddy가 일반 할당 pagePageBuddy도 guard도 아니면 조회 실패로 find_buddy_page_pfn() == NULLbuddy list를 제거하지 않고 현재 order의 블록을 등록; 그 order의 nr_free + 1
buddy의 order가 다름같은 order buddy가 아니므로 조회 실패; if (!buddy)에서 병합 중단다른 order의 기존 블록을 건드리지 않고 현재 order 블록만 등록
pageblock 경계의 타입 충돌order >= pageblock_order, migratetype이 다르고 한쪽이 병합 불가능하면 goto done_mergingbuddy는 자신의 migratetype list에 남고, 현재 블록은 현재 타입의 list에 등록
모든 검사 통과buddy를 해당 order의 list에서 제거한 뒤 order++로 재검사제거한 order의 nr_free − 1; 마지막에 더 큰 order list에 블록 하나 등록

free_area[order].nr_free는 해당 order의 모든 migratetype list를 합친 free block 수입니다. 위 도해에서만 list 하나로 제한했으므로 슬롯의 블록 수와 badge가 같습니다. 할당 전은 8 page짜리 블록 하나, 할당 후는 4 + 2 + 1 = 7 page짜리 블록 세 개, 전부 병합한 후는 다시 8 page짜리 블록 하나입니다. nr_free 값들을 그대로 더해 자유 page 수로 읽지 않습니다. set_buddy_order()는 free block head의 page->private와 PageBuddy를 설정하고, list 제거는 이를 지웁니다.

마지막 열은 PFN 256이 per-CPU pageset을 거치지 않고 __free_one_page()에 도달하고 세 buddy가 모두 병합 가능한 경우만 나타냅니다. 실제 order 0 해제는 per-CPU pageset을 먼저 거칠 수 있고, compaction capture·guard page·fallback 같은 다른 경로도 있습니다. 표의 첫 두 행은 같은 order의 free buddy가 있어야 한다는 조회 조건을 풀어 쓴 예시이며, 세 번째 행은 이 버전의 pageblock 경계 분기를 그대로 옮긴 것입니다.

소스 근거: 고정 Linux v6.18.37 mm/page_alloc.c (SHA-256 4274e384a11c5a74fecc48adec30fd324bc2427bc3d1033c6ffd6ceef9a18fd2). free block 표시:752–756, list·nr_free 증감:832–909, 병합 중단·재등록:978–1059, 분할·회계:1740–1777, 후보 조회:1927–1949. buddy 검사는 mm/internal.h:639–709의 page_is_buddy()/find_buddy_page_pfn()도 대조합니다. 이 파일의 SHA-256은 16659eab691d9c9a05f7350bdf5b51e5945812a6daea63a3efac9d743b45ad69입니다. DUJINLABS 자체 제작 도해.

불변 조건과 실패 사례

블록 회계

free_area[order].nr_free는 이 order의 블록 수입니다. free page 수에는 order별 가중치를 적용합니다.

병합 조건

XOR로 찾은 buddy가 같은 order의 free block이어야 합칩니다. pageblock 경계 타입, guard와 compaction capture도 확인합니다.

PCP 가시성

반환 page는 PCP에 먼저 머물 수 있어 buddy list 숫자가 즉시 늘지 않을 수 있습니다.

high-order 실패

총 free page가 충분해도 연속 블록, zone, watermark 또는 GFP 제약으로 실패할 수 있습니다.

계측과 검증

요청 order, GFP, 대상 zone, migratetype, PCP 여부를 먼저 구분합니다. 지표마다 보는 범위가 달라 한 수치만으로 실패 원인을 단정하지 않습니다.

관찰 지점과 한계
도구확인할 것한계
kmem:mm_page_alloc반환 page·order·GFP·migratetypeslowpath 내부의 모든 재시도는 보여주지 않음
/proc/buddyinfonode·zone별 order free block countPCP와 migratetype별 분류는 직접 나타나지 않음
/proc/pagetypeinfomigratetype·order별 free list 분포한 시점의 집계; 특정 caller의 실패 원인을 단독 증명하지 않음
page_owner (활성화 시)할당 page의 보유 기록커널 설정과 부팅 인자에 의존

추가 확인 사항

  • 같은 order에 블록이 있어도 GFP·zonelist·watermark·migratetype 제약 때문에 이 요청에는 쓸 수 없는가?
  • 요청 order가 PCP 허용 범위인가? 반환 page는 PCP에 머물렀나, buddy list까지 갔나?
  • 한 블록을 분할할 때 order별 nr_free와 총 free page 수가 각각 어떻게 변하는가?
  • high-order 실패 뒤 direct reclaim·compaction·조기 실패 중 어느 분기가 이 GFP/order에 허용되는가?