Memory · Linux v6.6 · source + diagram note

buddy allocator

zone, free_area, order 기반 page 할당.

전체 흐름

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

그림 1. 요청, 후보 저장소, 첫 시도 실패 후의 분기
요청__alloc_pages()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 388801345d63d1363c0f322d351026ebf39b2b6cc0d651495447c44128611c6b. 할당 진입: 4390–4453 · buddy 후보: 1564–1588. 그림과 PFN은 설명용 예시입니다.

소스 코드 위치

먼저 확인할 Linux v6.6 소스 파일

원본 코드:
Linux v6.6: mm/page_alloc.c
Linux v6.6: include/linux/mmzone.h
Linux v6.6: 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_cpuset_fallback()와 __alloc_pages_may_oom() 일부

원본 코드: mm/page_alloc.c, 3248행 부근
	dump_stack();
	warn_alloc_show_mem(gfp_mask, nodemask);
}

static inline struct page *
__alloc_pages_cpuset_fallback(gfp_t gfp_mask, unsigned int order,
			      unsigned int alloc_flags,
			      const struct alloc_context *ac)
{
	struct page *page;

	page = get_page_from_freelist(gfp_mask, order,
			alloc_flags|ALLOC_CPUSET, ac);
	/*
	 * fallback to ignore cpuset restriction if our nodes
	 * are depleted
	 */
	if (!page)
		page = get_page_from_freelist(gfp_mask, order,
				alloc_flags, ac);

	return page;
}

static inline struct page *
__alloc_pages_may_oom(gfp_t gfp_mask, unsigned int order,
	const struct alloc_context *ac, unsigned long *did_some_progress)
{
	struct oom_control oc = {
		.zonelist = ac->zonelist,
		.nodemask = ac->nodemask,
		.memcg = NULL,
		.gfp_mask = gfp_mask,
		.order = order,
	};
	struct page *page;

	*did_some_progress = 0;

	/*

발췌 범위: __alloc_pages() 본문이 아닙니다. 앞 함수의 끝에서 __alloc_pages_cpuset_fallback()와 __alloc_pages_may_oom() 시작으로 이어지는 중간 발췌입니다. 실제 할당 진입은 4390–4453행을 보세요.

free_the_page()와 compound page 준비 일부

원본 코드: mm/page_alloc.c, 557행 부근
}

static inline void free_the_page(struct page *page, unsigned int order)
{
	if (pcp_allowed_order(order))		/* Via pcp? */
		free_unref_page(page, order);
	else
		__free_pages_ok(page, order, FPI_NONE);
}

/*
 * Higher-order pages are called "compound pages".  They are structured thusly:
 *
 * The first PAGE_SIZE page is called the "head page" and have PG_head set.
 *
 * The remaining PAGE_SIZE pages are called "tail pages". PageTail() is encoded
 * in bit 0 of page->compound_head. The rest of bits is pointer to head page.
 *
 * The first tail page's ->compound_order holds the order of allocation.
 * This usage means that zero-order pages may not be compound.
 */

void prep_compound_page(struct page *page, unsigned int order)
{
	int i;
	int nr_pages = 1 << order;

	__SetPageHead(page);
	for (i = 1; i < nr_pages; i++)
		prep_compound_tail(page, i);

	prep_compound_head(page, order);
}

void destroy_large_folio(struct folio *folio)
{
	if (folio_test_hugetlb(folio)) {
		free_huge_folio(folio);
		return;
	}

발췌 범위: free_unref_page() 본문이 아닙니다. free_the_page()가 PCP 허용 order와 직접 buddy 경로를 고르는 부분, 이어지는 compound page 준비의 시작입니다. 실제 free_unref_page()는 2397–2434행을 보세요.

함수별 분석

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

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

v6.6 rmqueue()는 허용 order에서 PCP를 먼저 시도하고 실패하면 buddy로 갑니다. free_unref_page()도 PCP lock 획득 여부에 따라 per-CPU list 또는 free_one_page()로 갈라집니다.

고정 mm/page_alloc.c SHA-256 388801345d63d1363c0f322d351026ebf39b2b6cc0d651495447c44128611c6b. 분할 후보: 1564–1588 · PCP 해제: 2397–2434 · slowpath: 3898–4064. 그림과 PFN은 설명용 예시입니다.

위 도식은 성공해 반환된 페이지의 사용 생애를 구분합니다. __alloc_pages() 내부에서도 메모리 계정 부과가 실패하면 확보한 페이지를 __free_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 388801345d63d1363c0f322d351026ebf39b2b6cc0d651495447c44128611c6b. 표시·리스트: 605–710 · 병합: 763–837. 그림과 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 값만 더해 구하지 않습니다.

고정 mm/page_alloc.c SHA-256 388801345d63d1363c0f322d351026ebf39b2b6cc0d651495447c44128611c6b. 병합: 763–837 · 분할: 1389–1411 · 후보: 1564–1588. 그림과 PFN은 설명용 예시입니다.

불변 조건과 실패 사례

블록 회계

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에 허용되는가?