# Buddy Allocator (페이지 할당자)

Linux 7.0 메모리 관리 분석 시리즈

---

개요 (Overview)

Buddy Allocator는 리눅스 커널의 물리 메모리 할당을 담당하는 핵심 하위 시스템입니다. 시스템 부팅 시 memblock 할당자가 확보한 물리 페이지 프레임을 Buddy Allocator가 관리하며, 이후 모든 물리 페이지 할당은 이 할당자를 통해 이루어집니다. kmalloc()과 같은 slab 할당자는 내부적으로 Buddy Allocator의 alloc_pages()를 호출합니다.

Buddy 시스템의 핵심 아이디어는 2의 거듭제곱(order) 크기 블록을 관리하는 것입니다. 각 order의 빈 블록은 해당 migratetype별 free list로 관리되며, 요청 order보다 큰 블록이 있으면 expand()로 분할(split)하고, 반대로 반환 시 인접 buddy 블록이 자유롭면 병합(coalesce)하여 더 큰 블록을 만듭니다. 이를 통해 외부 단편화를 완화합니다.

일상 비유

Buddy Allocator는 큰 주차장을 항상 1칸, 2칸, 4칸, 8칸처럼 2의 거듭제곱 크기 구역으로만 나누는 관리자와 비슷합니다. 2칸짜리 공간이 필요한데 비어 있지 않으면 4칸짜리 구역을 반으로 쪼개 한쪽을 내주고, 나머지 2칸은 다시 빈 구역 목록에 보관합니다.

반대로 차가 빠져 두 인접 구역이 모두 비면 둘을 다시 합쳐 더 큰 구역으로 복원합니다. 이 규칙 덕분에 인접한 짝(buddy)을 빠르게 찾을 수 있고, 작은 빈 구역이 흩어져 큰 연속 메모리를 못 만드는 외부 단편화를 줄일 수 있습니다.

이 할당자는 사용자 공간의 mmap()이나 malloc()을 직접 처리하지는 않지만, 그 아래에서 handle_mm_fault() → do_anonymous_page() / do_wp_page() → alloc_pages()로 이어지는 물리 페이지 연결을 받쳐 줍니다. 익명 페이지의 첫 접근은 demand paging이고, fork() 뒤 private mapping의 쓰기 fault는 COW로 분기한 뒤 결국 같은 Buddy 경로에서 페이지가 나옵니다.

소스 파일 경로:

mm/page_alloc.c           ← 할당/해제 핵심 로직 (7856줄)
include/linux/mmzone.h    ← struct zone, free_area, pglist_data 정의
include/linux/mm_types.h  ← struct page 정의
mm/internal.h             ← 내부 헬퍼 함수, GFP 마스크 상수

---

빠른 점검 명령

# 시스템의 물리 메모리 레이아웃 확인
cat /proc/pagetypeinfo

# 기본 페이지 크기 확인
getconf PAGE_SIZE

# 각 존의 프리 페이지 통계
cat /proc/vmstat | grep -E "nr_free_pages|nr_free_cma"

# zone별 워터마크 및 free area 정보
cat /proc/zoneinfo | head -100

# Buddy 프리 리스트 분포 (order별 프리 페이지 수)
cat /proc/buddyinfo

# 메모리 단편화 상태 확인
cat /proc/extfraginfo

# per-CPU 페이지 리스트(PCP) 상태 확인
cat /proc/vmstat | grep pcp

# Slab 캐시와 Buddy의 상호작용 확인
cat /proc/slabinfo | head -5

# 페이지 폴트와 COW 징후 확인
ps -o pid,minflt,majflt -p $$

# 현재 시스템의 메모리 노드/존 구조
lstopo 2>/dev/null || numactl --hardware

추가 진단 수집 명령

# 전체 메모리와 page allocator 증상 동시 수집
cat /proc/meminfo | head -30

# 물리/가상 메모리 맵 확인
cat /proc/iomem
sudo cat /proc/vmallocinfo | head -20

# page allocation failure, OOM, compaction 관련 커널 로그 확인
dmesg | grep -Ei "page allocation failure|oom|compact|kswapd" | tail -50

# compaction, reclaim, allocation stall 카운터 확인
cat /proc/vmstat | grep -E "compact|allocstall|pgscan|pgsteal|pgalloc|pgfree"

# PSI 메모리 압력 확인 (커널 4.20+)
cat /proc/pressure/memory

# zoneinfo에서 PCP pageset과 워터마크 주변 정보 확인
cat /proc/zoneinfo | grep -E "Node|zone|pagesets|count:|high:|batch:|low|min|high" | head -120

---

핵심 자료구조

1. `struct page` — 물리 페이지 설명자

모든 물리 페이지 프레임에는 하나의 struct page가 존재합니다. Buddy Allocator에서 사용되는 필드는 다음과 같습니다:

// include/linux/mm_types.h:79-190
struct page {
memdesc_flags_t flags;      // 페이지 상태 비트 (PG_buddy, PG_head 등)
union {
struct {
union {
struct list_head lru;       // LRU 리스트
struct list_head buddy_list; // ← Buddy free list 연결
struct list_head pcp_list;   // ← PCP 리스트 연결
struct llist_node pcp_llist; // ← NMI-safe PCP 리스트
};
struct address_space *mapping;
union {
pgoff_t __folio_index;
unsigned long share;
};
unsigned long private;  // Buddy 시스템에서 order 저장 (PageBuddy일 때)
};
// ... 생략
};
union {
unsigned int page_type;  // typed folio용
atomic_t _mapcount;      // 매핑 카운트
};
atomic_t _refcount;          // 참조 카운트
// ...
};

핵심 포인트:

buddy_list: free 상태의 페이지가 free_area의 free_list에 연결되는 리스트 헤드

private: PageBuddy(page)가 설정된 경우 page_private(page)로 order 값 저장

flags.f: PG_buddy, PG_head, PG_tail 비트로 compound page/buddy 상태 추적

2. `struct free_area` — order별 free 리스트

// include/linux/mmzone.h:138-141
struct free_area {
struct list_head    free_list[MIGRATE_TYPES];  // migratetype별 연결 리스트
unsigned long       nr_free;                    // 총 프리 블록 수
};

각 zone은 NR_PAGE_ORDERS(보통 11, order 0~10)개의 free_area 배열을 가집니다. 각 free_area는 MIGRATE_TYPES개의 free list를 가지며, 각 list는 해당 migratetype과 order의 프리 블록들을 buddy_list로 연결합니다.

3. `struct zone` — 메모리 존

// include/linux/mmzone.h:879-1060
struct zone {
// 워터마크
unsigned long _watermark[NR_WMARK];   // MIN, LOW, HIGH, PROMO
unsigned long watermark_boost;

// 존 영역 정보
unsigned long zone_start_pfn;
atomic_long_t managed_pages;    // buddy가 관리하는 페이지 수
unsigned long spanned_pages;
unsigned long present_pages;

// 프리 에어리어 배열 (핵심!)
struct free_area free_area[NR_PAGE_ORDERS];

// 동시성 제어
spinlock_t lock;                // free_area 보호

// NUMA 관련
struct pglist_data *zone_pgdat;
struct per_cpu_pages __percpu *per_cpu_pageset;  // PCP

// 통계
atomic_long_t vm_stat[NR_VM_ZONE_STAT_ITEMS];
};

핵심 포인트:

free_area[NR_PAGE_ORDERS]: order 0부터 MAX_PAGE_ORDER까지의 free area 배열

lock: free_area 접근 시 필요 (zone->lock)

_watermark[]: 할당 가능 여부 판단 기준 (MIN/LOW/HIGH)

per_cpu_pageset: per-CPU 캐시 페이지 리스트 (PCP)

4. `struct pglist_data` (pg_data_t) — NUMA 노드

// include/linux/mmzone.h:1381-1498
typedef struct pglist_data {
struct zone node_zones[MAX_NR_ZONES];        // 이 노드의 존 배열
struct zonelist node_zonelists[MAX_ZONELISTS]; // 할당 순서 목록
int nr_zones;

unsigned long node_start_pfn;
unsigned long node_present_pages;
unsigned long node_spanned_pages;
int node_id;

// kswapd 관련
wait_queue_head_t kswapd_wait;
struct task_struct *kswapd;
int kswapd_order;
// ...
} pg_data_t;

5. `struct per_cpu_pages` (PCP) — Per-CPU 페이지 캐시

// include/linux/mmzone.h:744-760
struct per_cpu_pages {
spinlock_t lock;
int count;          // 현재 리스트의 페이지 수
int high;           // high 워터마크 (이 넘으면 드레인)
int high_min;
int high_max;
int batch;          // buddy에서 가져올/보낼 배치 크기
u8 alloc_factor;    // allocate 시 batch 스케일링 팩터
short free_count;   // 연속 free 카운트
struct list_head lists[NR_PCP_LISTS];  // migratetype × order 리스트
};

핵심 포인트:

NR_PCP_LISTS = MIGRATE_PCPTYPES × (PAGE_ALLOC_COSTLY_ORDER + 1) + NR_PCP_THP

order 0~3 × Unmovable/Movable/Reclaimable + THP 2개 = 14개 리스트

high: 이 값 초과 시 zone lock 하에서 buddy로 반환

batch: 한 번에 buddy에서 가져올/보낼 페이지 수

6. Migratetype

// include/linux/mmzone.h:64-90
enum migratetype {
MIGRATE_UNMOVABLE,    // 이동 불가 (kernel allocations)
MIGRATE_MOVABLE,      // 이동 가능 (user pages)
MIGRATE_RECLAIMABLE,  // 회수 가능 (inode cache 등)
MIGRATE_PCPTYPES,     // PCP lists의 수 (3)
MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
MIGRATE_CMA,          // CMA 영역 (CONFIG_CMA)
MIGRATE_ISOLATE,      // 격리 (CONFIG_MEMORY_ISOLATION)
MIGRATE_TYPES
};

Fallback 순서:

// mm/page_alloc.c:1951-1955
static int fallbacks[MIGRATE_PCPTYPES][MIGRATE_PCPTYPES - 1] = {
[MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE   },
[MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE },
[MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE   },
};

---

핵심 함수

1. `__alloc_pages_noprof()` — 메모리 할당 메인 엔트리

// mm/page_alloc.c:5279-5289
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;
}

역할: alloc_pages() 매크로의 최종 구현. frozen 페이지를 할당한 후 refcount=1로 설정합니다.

분기 로직:

__alloc_frozen_pages_noprof() 호출 → 실패 시 NULL 반환

2. `__alloc_frozen_pages_noprof()` — 할당 핵심 로직

// mm/page_alloc.c:5214-5277
struct page *__alloc_frozen_pages_noprof(gfp_t gfp, unsigned int order,
int preferred_nid, nodemask_t *nodemask)
{
struct alloc_context ac = { };
unsigned int alloc_flags = ALLOC_WMARK_LOW;
gfp_t alloc_gfp;

if (WARN_ON_ONCE_GFP(order > MAX_PAGE_ORDER, gfp))
return NULL;

gfp &= gfp_allowed_mask;
gfp = current_gfp_context(gfp);
alloc_gfp = gfp;

if (!prepare_alloc_pages(gfp, order, preferred_nid, nodemask, &ac,
&alloc_gfp, &alloc_flags))
return NULL;

alloc_flags |= alloc_flags_nofragment(zonelist_zone(ac.preferred_zoneref), gfp);

/* 1차 시도: fast path */
page = get_page_from_freelist(alloc_gfp, order, alloc_flags, &ac);
if (likely(page))
goto out;

alloc_gfp = gfp;
ac.spread_dirty_pages = false;

/* 2차 시도: slow path (direct reclaim, OOM 등) */
page = __alloc_pages_slowpath(alloc_gfp, order, &ac);

out:
if (memcg_kmem_online() && (gfp & __GFP_ACCOUNT) && page &&
unlikely(__memcg_kmem_charge_page(page, gfp, order) != 0)) {
free_frozen_pages(page, order);
page = NULL;
}

trace_mm_page_alloc(page, order, alloc_gfp, ac.migratetype);
kmsan_alloc_page(page, order, alloc_gfp);

return page;
}

분기 로직:

1. order > MAX_PAGE_ORDER → 경고 후 NULL 반환

2. prepare_alloc_pages() 실패 → NULL 반환

3. get_page_from_freelist() 성공 → 바로 반환 (fast path)

4. 실패 → __alloc_pages_slowpath() 진입 (slow path)

- kswapd wake, direct reclaim, compaction, OOM 순서로 시도

3. `get_page_from_freelist()` — 존 순회 및 할당

// mm/page_alloc.c:3808-4003
static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
const struct alloc_context *ac)
{
struct zoneref *z;
struct zone *zone;

retry:
no_fallback = alloc_flags & ALLOC_NOFRAGMENT;
z = ac->preferred_zoneref;

// zonelist 순회
for_next_zone_zonelist_nodemask(zone, z, ac->highest_zoneidx,
ac->nodemask) {
// cpuset 체크
// dirty limit 체크
// fragmentation avoidance 체크

check_alloc_wmark:
// 워터마크 검사
mark = wmark_pages(zone, alloc_flags & ALLOC_WMARK_MASK);
if (!zone_watermark_fast(zone, order, mark,
ac->highest_zoneidx, alloc_flags,
gfp_mask)) {
// watermarks 미충족 시 node_reclaim 시도
continue;
}

try_this_zone:
// 실제 할당 시도
page = rmqueue(zonelist_zone(ac->preferred_zoneref), zone, order,
gfp_mask, alloc_flags, ac->migratetype);
if (page) {
prep_new_page(page, order, gfp_mask, alloc_flags);
if (unlikely(alloc_flags & ALLOC_HIGHATOMIC))
reserve_highatomic_pageblock(page, order, zone);
return page;
}
}

// fallback: NOFRAGMENT 해제 후 재시도
if (no_fallback && !defrag_mode) {
alloc_flags &= ~ALLOC_NOFRAGMENT;
goto retry;
}
return NULL;
}

상위 page fault 연결

page fault
└─ handle_mm_fault()      [mm/memory.c:6589]
├─ do_anonymous_page() [mm/memory.c:5217]  ← 첫 접근의 익명 페이지
└─ do_wp_page()        [mm/memory.c:4149]  ← COW / write-protect fault
└─ alloc_page(GFP_KERNEL)

// mm/memory.c:6589-6624
vm_fault_t handle_mm_fault(struct vm_area_struct *vma, unsigned long address,
unsigned int flags, struct pt_regs *regs)
{
...
if (unlikely(is_vm_hugetlb_page(vma)))
ret = hugetlb_fault(vma->vm_mm, vma, address, flags);
else
ret = __handle_mm_fault(vma, address, flags);
...
}

// mm/memory.c:5217-5267
static vm_fault_t do_anonymous_page(struct vm_fault *vmf)
{
...
if (!(vmf->flags & FAULT_FLAG_WRITE) &&
!mm_forbids_zeropage(vma->vm_mm)) {
...
entry = pte_mkspecial(pfn_pte(my_zero_pfn(vmf->address),
vma->vm_page_prot));
...
}
...
folio = alloc_anon_folio(vmf);
...
}

// mm/memory.c:4149-4241
static vm_fault_t do_wp_page(struct vm_fault *vmf)
{
...
if (folio && folio_test_anon(folio) &&
(PageAnonExclusive(vmf->page) || wp_can_reuse_anon_folio(folio, vma))) {
...
wp_page_reuse(vmf, folio);
return 0;
}
...
return wp_page_copy(vmf);
}

분기 로직:

1. zonelist 순회: preferred zone → fallback zone 순

2. 각 zone마다:

- cpuset 허용 여부

- dirty limit 초과 여부

- 워터마크 충족 여부 (fast check → full check)

- watermarks 미충족 시: _deferred_grow_zone() 또는 node_reclaim() 시도

3. rmqueue() 성공 시: prep_new_page() 후 반환

4. 모든 zone 실패 시: NOFRAGMENT 플래그 해제 후 retry

4. `__rmqueue()` — free list에서 페이지 제거

// mm/page_alloc.c:2477-2540
static __always_inline struct page *
__rmqueue(struct zone *zone, unsigned int order, int migratetype,
unsigned int alloc_flags, enum rmqueue_mode *mode)
{
// CMA 밸런싱: CMA free가 50% 초과 시 CMA에서 먼저 할당
if (alloc_flags & ALLOC_CMA &&
zone_page_state(zone, NR_FREE_CMA_PAGES) >
zone_page_state(zone, NR_FREE_PAGES) / 2) {
page = __rmqueue_cma_fallback(zone, order);
if (page) return page;
}

// fallback 모드 순차 시도
switch (*mode) {
case RMQUEUE_NORMAL:
page = __rmqueue_smallest(zone, order, migratetype);  // 1순위
if (page) return page;
fallthrough;
case RMQUEUE_CMA:
page = __rmqueue_cma_fallback(zone, order);            // 2순위
if (page) { *mode = RMQUEUE_CMA; return page; }
fallthrough;
case RMQUEUE_CLAIM:
page = __rmqueue_claim(zone, order, migratetype, alloc_flags); // 3순위
if (page) { *mode = RMQUEUE_NORMAL; return page; }
fallthrough;
case RMQUEUE_STEAL:
if (!(alloc_flags & ALLOC_NOFRAGMENT)) {
page = __rmqueue_steal(zone, order, migratetype);  // 4순위
if (page) { *mode = RMQUEUE_STEAL; return page; }
}
}
return NULL;
}

분기 로직 (4단계 fallback):

1. NORMAL: 같은 migratetype의 free list에서 직접 할당

2. CMA: CMA free list에서 할당 (MOVABLE만)

3. CLAIM: 다른 migratetype의 free list에서 페이지블록을 claim (migratetype 변경)

4. STEAL: 다른 migratetype에서 페이지를 steal (단편화 허용 시)

5. `__rmqueue_smallest()` — 최소 order에서 할당

// mm/page_alloc.c:1919-1942
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
int migratetype)
{
unsigned int current_order;
struct free_area *area;
struct page *page;

// 요청 order부터 MAX_PAGE_ORDER까지 상위 order 탐색
for (current_order = order; current_order < NR_PAGE_ORDERS; ++current_order) {
area = &(zone->free_area[current_order]);
page = get_page_from_free_area(area, migratetype);
if (!page)
continue;

// 큰 블록을 필요 order로 분할
page_del_and_expand(zone, page, order, current_order, migratetype);
return page;
}
return NULL;
}

분기 로직:

order ~ MAX_PAGE_ORDER 범위에서 free 블록 탐색

큰 블록 발견 시 page_del_and_expand()로 분할 후 반환

6. `expand()` — 블록 분할 (Split)

// mm/page_alloc.c:1732-1758
static inline unsigned int expand(struct zone *zone, struct page *page, int low,
int high, int migratetype)
{
unsigned int size = 1 << high;
unsigned int nr_added = 0;

while (high > low) {
high--;
size >>= 1;

// guard page 설정 시 skip
if (set_page_guard(zone, &page[size], high))
continue;

// 상위 half를 free list에 추가
__add_to_free_list(&page[size], zone, high, migratetype, false);
set_buddy_order(&page[size], high);
nr_added += size;
}
return nr_added;
}

분기 로직:

high → low까지 반복

각 단계에서 상위 half를 free list에 추가

guard page( CONFIG_DEBUG_PAGEALLOC) 설정 시 해당 블록 skip

7. `__free_one_page()` — 페이지 반환 및 버디 병합

// mm/page_alloc.c:978-1064
static inline void __free_one_page(struct page *page,
unsigned long pfn, struct zone *zone, unsigned int order,
int migratetype, fpi_t fpi_flags)
{
unsigned long buddy_pfn = 0;
unsigned long combined_pfn;

account_freepages(zone, 1 << order, migratetype);

// order < MAX_PAGE_ORDER까지 버디 병합 시도
while (order < MAX_PAGE_ORDER) {
int buddy_mt = migratetype;

// compaction capture 체크
if (compaction_capture(capc, page, order, migratetype)) {
account_freepages(zone, -(1 << order), migratetype);
return;
}

// 인접 버디 찾기
buddy = find_buddy_page_pfn(page, pfn, order, &buddy_pfn);
if (!buddy)
goto done_merging;

// pageblock_order 이상에서는 migratetype 일치 확인
if (unlikely(order >= pageblock_order)) {
buddy_mt = get_pfnblock_migratetype(buddy, buddy_pfn);
if (migratetype != buddy_mt &&
(!migratetype_is_mergeable(migratetype) ||
!migratetype_is_mergeable(buddy_mt)))
goto done_merging;
}

// 버디를 free list에서 제거하고 병합
__del_page_from_free_list(buddy, zone, order, buddy_mt);
combined_pfn = buddy_pfn & pfn;
page = page + (combined_pfn - pfn);
pfn = combined_pfn;
order++;
}

done_merging:
set_buddy_order(page, order);
__add_to_free_list(page, zone, order, migratetype, to_tail);
}

분기 로직:

1. compaction capture: compaction 중이면 해당 페이지를 캡처

2. find_buddy_page_pfn(): 인접 버디 페이지 검색

3. order ≥ pageblock_order: migratetype 호환성 확인 후 병합

4. 버디 병합: combined_pfn = buddy_pfn & pfn으로 병합된 base pfn 계산

5. 병합된 블록을 free list에 추가

8. `__alloc_pages_slowpath()` — Slow Path (할당 실패 시 대응)

// mm/page_alloc.c:4710-4994
static inline struct page *
__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
struct alloc_context *ac)
{
bool can_direct_reclaim = gfp_mask & __GFP_DIRECT_RECLAIM;
bool can_compact = can_direct_reclaim && gfp_compaction_allowed(gfp_mask);
bool nofail = gfp_mask & __GFP_NOFAIL;
const bool costly_order = order > PAGE_ALLOC_COSTLY_ORDER;
struct page *page = NULL;
unsigned int alloc_flags;
unsigned long did_some_progress;
enum compact_priority compact_priority;
enum compact_result compact_result;
int compaction_retries;
int no_progress_loops;

restart:
compaction_retries = 0;
no_progress_loops = 0;
compact_result = COMPACT_SKIPPED;
compact_priority = DEF_COMPACT_PRIORITY;

// costly/high-order 할당 시 compaction 우선 시도
if (can_compact && (costly_order || (order > 0 &&
ac->migratetype != MIGRATE_MOVABLE))) {
compact_first = true;
compact_priority = INIT_COMPACT_PRIORITY;
}

alloc_flags = gfp_to_alloc_flags(gfp_mask, order);

retry:
// kswapd wake
if (alloc_flags & ALLOC_KSWAPD)
wake_all_kswapds(order, gfp_mask, ac);

// 재시도: watermarks 재검사
page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
if (page)
goto got_pg;

// pfmemalloc 플래그 확인 (긴급 할당)
reserve_flags = __gfp_pfmemalloc_flags(gfp_mask);
if (reserve_flags) {
alloc_flags = gfp_to_alloc_flags_cma(gfp_mask, reserve_flags) |
(alloc_flags & ALLOC_KSWAPD);
if (can_retry_reserves) {
can_retry_reserves = false;
goto retry;
}
}

// 직접 회수 불가능하면 실패
if (!can_direct_reclaim)
goto nopage;

// 직접 회수 시도
if (!compact_first) {
page = __alloc_pages_direct_reclaim(gfp_mask, order, alloc_flags,
ac, &did_some_progress);
if (page)
goto got_pg;
}

// 직접 compaction 시도
page = __alloc_pages_direct_compact(gfp_mask, order, alloc_flags, ac,
compact_priority, &compact_result);
if (page)
goto got_pg;

// compact_first 후 retry
if (compact_first) {
compact_first = false;
goto retry;
}

// 회수/compaction 재시도 검사
if (should_reclaim_retry(gfp_mask, order, ac, alloc_flags,
did_some_progress > 0, &no_progress_loops))
goto retry;

if (did_some_progress > 0 && can_compact &&
should_compact_retry(ac, order, alloc_flags,
compact_result, &compact_priority,
&compaction_retries))
goto retry;

// NOFRAGMENT 해제 후 재시도
if (defrag_mode && (alloc_flags & ALLOC_NOFRAGMENT)) {
alloc_flags &= ~ALLOC_NOFRAGMENT;
goto retry;
}

// OOM Killer 발동
page = __alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress);
if (page)
goto got_pg;

// NOFAIL 처리
if (unlikely(nofail)) {
page = __alloc_pages_cpuset_fallback(gfp_mask, order,
ALLOC_MIN_RESERVE, ac);
if (page)
goto got_pg;
cond_resched();
goto retry;
}

nopage:
warn_alloc(gfp_mask, ac->nodemask,
"page allocation failure: order:%u", order);
got_pg:
return page;
}

분기 로직 (단계별 대응):

1. kswapd wake: 백그라운드 회수 트리거

2. watermark 재검사: ALLOC_MIN_RESERVE 적용 후 재시도

3. pfmemalloc: 긴급 시 ALLOC_NO_WATERMARKS 적용

4. 직접 회수: try_to_free_pages() → LRU 페이지 회수

5. 직접 compaction: 메모리 조각 모음으로 큰 블록 확보

6. 회수/compaction 재시도: MAX_RECLAIM_RETRIES(16회)까지 반복

7. NOFRAGMENT 해제: 단편화 허용 후 재시도

8. OOM Killer: out_of_memory() → 프로세스 종료

9. NOFAIL: 무한 재시도 (조건부)

9. `__free_frozen_pages()` — PCP를 통한 페이지 반환

// mm/page_alloc.c:2964-3020
static void __free_frozen_pages(struct page *page, unsigned int order,
fpi_t fpi_flags)
{
unsigned long UP_flags;
struct per_cpu_pages *pcp;
struct zone *zone;
unsigned long pfn = page_to_pfn(page);
int migratetype;

// PCP 허용 order가 아니면 buddy로 직접 반환
if (!pcp_allowed_order(order)) {
__free_pages_ok(page, order, fpi_flags);
return;
}

if (!__free_pages_prepare(page, order, fpi_flags))
return;

// ISOLATE 타입은 즉시 free_one_page()
zone = page_zone(page);
migratetype = get_pfnblock_migratetype(page, pfn);
if (unlikely(migratetype >= MIGRATE_PCPTYPES)) {
if (unlikely(is_migrate_isolate(migratetype))) {
free_one_page(zone, page, pfn, order, fpi_flags);
return;
}
migratetype = MIGRATE_MOVABLE;
}

// PCP에 추가
pcp = pcp_spin_trylock(zone->per_cpu_pageset, UP_flags);
if (pcp) {
free_frozen_page_commit(zone, pcp, page, migratetype,
order, fpi_flags, &UP_flags);
pcp_spin_unlock(pcp, UP_flags);
} else {
// PCP lock 실패 시 buddy로 직접 반환
free_one_page(zone, page, pfn, order, fpi_flags);
}
}

분기 로직:

1. PCP 허용 order 초과 → __free_pages_ok() (buddy 직접 반환)

2. ISOLATE 타입 → free_one_page() (즉시 buddy 반환)

3. PCP lock 성공 → free_frozen_page_commit() (PCP에 추가)

4. PCP lock 실패 → free_one_page() (buddy 직접 반환)

10. `free_frozen_page_commit()` — PCP 반환 및 드레인

// mm/page_alloc.c:2859-2959
static bool free_frozen_page_commit(struct zone *zone,
struct per_cpu_pages *pcp, struct page *page, int migratetype,
unsigned int order, fpi_t fpi_flags, unsigned long *UP_flags)
{
int high, batch;
int to_free, to_free_batched;
int pindex;

// PCP 할당 팩터 절반으로 감소
pcp->alloc_factor >>= 1;

// PCP 리스트에 추가
pindex = order_to_pindex(migratetype, order);
list_add(&page->pcp_list, &pcp->lists[pindex]);
pcp->count += 1 << order;

// high-order 페이지 드레인 검사
if (order && order <= PAGE_ALLOC_COSTLY_ORDER) {
free_high = (pcp->free_count >= (batch + pcp->high_min / 2) &&
(pcp->flags & PCPF_PREV_FREE_HIGH_ORDER) &&
(!(pcp->flags & PCPF_FREE_HIGH_BATCH) ||
pcp->count >= batch));
pcp->flags |= PCPF_PREV_FREE_HIGH_ORDER;
} else if (pcp->flags & PCPF_PREV_FREE_HIGH_ORDER) {
pcp->flags &= ~PCPF_PREV_FREE_HIGH_ORDER;
}

// PCP high 초과 시 드레인
high = nr_pcp_high(pcp, zone, batch, free_high);
if (pcp->count < high)
return true;

// 초과분을 buddy로 반환
to_free = nr_pcp_free(pcp, batch, high, free_high);
while (to_free > 0 && pcp->count > 0) {
to_free_batched = min(to_free, batch);
free_pcppages_bulk(zone, to_free_batched, pcp, pindex);
to_free -= to_free_batched;
}

// ZONE_BELOW_HIGH 해제 검사
if (test_bit(ZONE_BELOW_HIGH, &zone->flags) &&
zone_watermark_ok(zone, 0, high_wmark_pages(zone),
ZONE_MOVABLE, 0)) {
clear_bit(ZONE_BELOW_HIGH, &zone->flags);
}

return true;
}

분기 로직:

1. alloc_factor 절반으로 감소 (할당 빈도 억제)

2. PCP 리스트에 페이지 추가

3. high-order 페이지 연속 드레인 검사

4. PCP high 초과 시 free_pcppages_bulk()로 buddy에 반환

5. 존 워터마크 충족 시 ZONE_BELOW_HIGH 플래그 해제

---

데이터 구조 계층

호출 흐름

Slow Path 상세 흐름

PCP (Per-CPU Pages) 흐름

alloc_pages(gfp, order)
└─ __alloc_pages_noprof()              [mm/page_alloc.c:5279]
└─ __alloc_frozen_pages_noprof()   [mm/page_alloc.c:5214]
├─ prepare_alloc_pages()
├─ get_page_from_freelist()    [mm/page_alloc.c:3808]  ← Fast Path
│   └─ for_each_zone_zonelist_nodemask()
│       ├─ zone_watermark_fast()
│       └─ rmqueue()
│           └─ __rmqueue()     [mm/page_alloc.c:2477]
│               ├─ __rmqueue_smallest()   ← 1순위
│               │   └─ get_page_from_free_area()
│               │   └─ page_del_and_expand()
│               │       └─ expand()       ← 분할
│               ├─ __rmqueue_cma_fallback() ← 2순위
│               ├─ __rmqueue_claim()       ← 3순위
│               └─ __rmqueue_steal()       ← 4순위
│   └─ prep_new_page()
└─ __alloc_pages_slowpath()    ← Slow Path (fast 실패 시)
├─ wake_all_kswapds()       ← kswapd 백그라운드 회수 트리거
├─ __alloc_pages_direct_reclaim()  ← 직접 회수
│   ├─ __perform_reclaim()
│   │   └─ try_to_free_pages()
│   └─ get_page_from_freelist()
├─ __alloc_pages_direct_compact()  ← 직접 compaction
└─ __alloc_pages_may_oom()         ← OOM Killer 발동

free_pages(addr, order)
└─ __free_pages()                      [mm/page_alloc.c:5367]
└─ ___free_pages()
└─ __free_frozen_pages()       [mm/page_alloc.c:2964]
├─ pcp_allowed_order() 체크
│   └─ 초과 시 → __free_pages_ok() (buddy 직접 반환)
├─ get_pfnblock_migratetype()
│   └─ ISOLATE → free_one_page() (즉시 반환)
└─ pcp_spin_trylock()
├─ 성공 → free_frozen_page_commit()  ← PCP에 추가
│   ├─ pcp->alloc_factor 절반으로 감소
│   ├─ PCP 리스트에 추가
│   ├─ PCP high 초과 시 → free_pcppages_bulk()
│   └─ 존 워터마크 충족 시 → ZONE_BELOW_HIGH 해제
└─ 실패 → free_one_page() (buddy 직접 반환)
└─ __free_one_page()   [mm/page_alloc.c:978]
└─ while (order < MAX_PAGE_ORDER)
├─ find_buddy_page_pfn()
├─ __del_page_from_free_list()
└─ __add_to_free_list()  ← 병합 후 추가

---

조건별 비교

할당 플래그 (GFP)별 동작

GFP 플래그	워터마크	direct reclaim	compaction	OOM	PCP 사용
`GFP_KERNEL`	LOW	O	O	O	O
`GFP_ATOMIC`	MIN (예약 접근)	X	X	X	X
`GFP_NOWAIT`	LOW	X	X	X	O
`GFP_NOIO`	LOW	O (I/O 제외)	O	O	O
`GFP_NOFS`	LOW	O (FS 제외)	O	O	O
`GFP_DMA`	MIN	O	O	O	O

Migratetype Fallback 순서

요청 타입	1차 fallback	2차 fallback
UNMOVABLE	RECLAIMABLE	MOVABLE
MOVABLE	RECLAIMABLE	UNMOVABLE
RECLAIMABLE	UNMOVABLE	MOVABLE

Zone Watermark 동작

조건	동작
free ≥ HIGH	정상 할당 가능
LOW ≤ free < HIGH	kswapd wake (background reclaim)
MIN ≤ free < LOW	direct reclaim 발생 가능
free < MIN	OOM 또는 할당 실패

외부/내부 단편화 비교

종류	원인	대표 지표	커널 대응
외부 단편화	free 공간이 작은 조각으로 흩어짐	`/proc/buddyinfo`, `/proc/extfraginfo`	buddy 병합, compaction
내부 단편화	요청보다 큰 블록을 할당	`/proc/slabinfo`, `kmalloc-*` 사용률	SLUB size class, cache reuse

---

Buddy 관련 API 계층

API	반환 형태	물리 연속성	내부 경로	주 용도
`alloc_page(gfp)`	`struct page *`	1 page 연속	`alloc_pages(gfp, 0)`	단일 페이지 할당
`alloc_pages(gfp, order)`	`struct page *`	`2^order` pages 연속	Buddy 직접	고차 페이지/compound page 기반
`__get_free_pages(gfp, order)`	`unsigned long` 주소	`2^order` pages 연속	`alloc_pages()` + `page_address()`	커널 선형 주소가 필요한 저수준 경로
`kmalloc(size, gfp)`	`void *`	물리 연속	SLUB → Buddy	작은 커널 오브젝트
`vmalloc(size)`	`void *`	물리 불연속, 가상 연속	페이지별 Buddy → vmap	큰 버퍼, 물리 연속 불필요

GFP 컨텍스트 제약

호출 컨텍스트	권장 GFP	슬립 가능	Buddy 동작상 의미
일반 프로세스 컨텍스트	`GFP_KERNEL`	O	direct reclaim, compaction, OOM까지 진입 가능
인터럽트/hardirq	`GFP_ATOMIC`	X	예약 메모리 접근은 가능하지만 실패 가능성이 높음
softirq/timer	`GFP_ATOMIC`	X	reclaim으로 잠들 수 없으므로 fast/긴급 경로 위주
spinlock 보유 중	`GFP_ATOMIC`	X	`GFP_KERNEL` 사용 시 scheduling while atomic 위험
block I/O 내부	`GFP_NOIO`	O	회수는 가능하지만 I/O 재귀를 막음
파일시스템 내부	`GFP_NOFS`	O	FS 재진입을 막고 회수 범위를 제한

증상별 진단 표

증상	우선 점검	Buddy 관점 해석	후속 조치
`page allocation failure: order:N`	`dmesg`, `/proc/buddyinfo`	총 free는 있어도 해당 order 이상의 연속 블록 부족	compaction 상태, THP/CMA 요청, migratetype 오염 확인
고차 order가 계속 0	`/proc/buddyinfo`, `/proc/extfraginfo`	외부 단편화 또는 MOVABLE 부족	`compact_*` vmstat, `compact_memory`, THP defrag 정책 확인
`allocstall` 증가	`/proc/vmstat`	fast path 실패 후 direct reclaim 빈번	reclaim 병목, working set, memcg limit 확인
PCP count 과대/불균형	`/proc/zoneinfo` pagesets	CPU별 캐시에 free page가 머물러 zone free list 가시성이 낮음	drain 동작, CPU hotplug, zone pressure 확인
OOM 전 `kswapd` 과활성	`dmesg`, PSI, `pgscan/pgsteal`	watermark 아래로 떨어져 회수와 할당이 경합	slab/page cache 증가, swap/zswap, memcg 이벤트 확인

---

Linux 7.0 원문 상세

Buddy PFN 계산과 검증

buddy_pfn = pfn ^ (1 << order) 공식은 mm/internal.h에 그대로 구현되어 있습니다. 같은 order에서 한 비트만 뒤집으면 같은 상위 블록을 공유하는 인접 buddy를 O(1)에 찾을 수 있습니다.

// mm/internal.h:755-759
static inline unsigned long
__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
{
	return page_pfn ^ (1 << order);
}

// mm/internal.h:775-788
static inline struct page *find_buddy_page_pfn(struct page *page,
			unsigned long pfn, unsigned int order, unsigned long *buddy_pfn)
{
	unsigned long __buddy_pfn = __find_buddy_pfn(pfn, order);
	struct page *buddy;

	buddy = page + (__buddy_pfn - pfn);
	if (buddy_pfn)
		*buddy_pfn = __buddy_pfn;

	if (page_is_buddy(page, buddy, order))
		return buddy;
	return NULL;
}

분할(split) 원문

expand()는 상위 order 블록을 낮은 order로 내리면서 뒤쪽 half를 free list에 추가합니다. set_page_guard()가 true이면 debug guard page로 남기고 free list 추가를 건너뜁니다.

// mm/page_alloc.c:1732-1758
static inline unsigned int expand(struct zone *zone, struct page *page, int low,
				  int high, int migratetype)
{
	unsigned int size = 1 << high;
	unsigned int nr_added = 0;

	while (high > low) {
		high--;
		size >>= 1;
		VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);

		/*
		 * Mark as guard pages (or page), that will allow to
		 * merge back to allocator when buddy will be freed.
		 * Corresponding page table entries will not be touched,
		 * pages will stay not present in virtual address space
		 */
		if (set_page_guard(zone, &page[size], high))
			continue;

		__add_to_free_list(&page[size], zone, high, migratetype, false);
		set_buddy_order(&page[size], high);
		nr_added += size;
	}

	return nr_added;
}

병합(coalescing) 원문

해제 경로는 같은 order의 buddy가 free인지 확인하고, 병합 가능한 migratetype이면 기존 buddy를 free list에서 제거한 뒤 order를 하나씩 올립니다.

// mm/page_alloc.c:998-1059
	while (order < MAX_PAGE_ORDER) {
		int buddy_mt = migratetype;

		if (compaction_capture(capc, page, order, migratetype)) {
			account_freepages(zone, -(1 << order), migratetype);
			return;
		}

		buddy = find_buddy_page_pfn(page, pfn, order, &buddy_pfn);
		if (!buddy)
			goto done_merging;

		if (unlikely(order >= pageblock_order)) {
			/*
			 * We want to prevent merge between freepages on pageblock
			 * without fallbacks and normal pageblock. Without this,
			 * pageblock isolation could cause incorrect freepage or CMA
			 * accounting or HIGHATOMIC accounting.
			 */
			buddy_mt = get_pfnblock_migratetype(buddy, buddy_pfn);

			if (migratetype != buddy_mt &&
			    (!migratetype_is_mergeable(migratetype) ||
			     !migratetype_is_mergeable(buddy_mt)))
				goto done_merging;
		}

		/*
		 * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
		 * merge with it and move up one order.
		 */
		if (page_is_guard(buddy))
			clear_page_guard(zone, buddy, order);
		else
			__del_page_from_free_list(buddy, zone, order, buddy_mt);

		if (unlikely(buddy_mt != migratetype)) {
			/*
			 * Match buddy type. This ensures that an
			 * expand() down the line puts the sub-blocks
			 * on the right freelists.
			 */
			change_pageblock_range(buddy, order, migratetype);
		}

		combined_pfn = buddy_pfn & pfn;
		page = page + (combined_pfn - pfn);
		pfn = combined_pfn;
		order++;
	}

done_merging:
	set_buddy_order(page, order);

	if (fpi_flags & FPI_TO_TAIL)
		to_tail = true;
	else if (is_shuffle_order(order))
		to_tail = shuffle_pick_tail();
	else
		to_tail = buddy_merge_likely(pfn, buddy_pfn, page, order);

	__add_to_free_list(page, zone, order, migratetype, to_tail);

PCP 할당 원문

Linux 7.0의 rmqueue()는 pcp_allowed_order(order)이면 먼저 per-CPU list를 시도하고, 실패하거나 PCP 대상 order가 아니면 buddy 경로(rmqueue_buddy)로 내려갑니다.

// mm/page_alloc.c:3336-3363
struct page *__rmqueue_pcplist(struct zone *zone, unsigned int order,
			int migratetype,
			unsigned int alloc_flags,
			struct per_cpu_pages *pcp,
			struct list_head *list)
{
	struct page *page;

	do {
		if (list_empty(list)) {
			int batch = nr_pcp_alloc(pcp, zone, order);
			int alloced;

			alloced = rmqueue_bulk(zone, order,
					batch, list,
					migratetype, alloc_flags);

			pcp->count += alloced << order;
			if (unlikely(list_empty(list)))
				return NULL;
		}

		page = list_first_entry(list, struct page, pcp_list);
		list_del(&page->pcp_list);
		pcp->count -= 1 << order;
	} while (check_new_pages(page, order));

	return page;
}

// mm/page_alloc.c:3417-3425
	if (likely(pcp_allowed_order(order))) {
		page = rmqueue_pcplist(preferred_zone, zone, order,
				       migratetype, alloc_flags);
		if (likely(page))
			goto out;
	}

	page = rmqueue_buddy(preferred_zone, zone, order, alloc_flags,
							migratetype);

Slow path 핵심 분기 원문

slow path는 먼저 조정된 alloc_flags로 다시 fast path를 시도하고, 실패하면 direct reclaim, direct compaction, 재시도 판단, OOM, __GFP_NOFAIL 처리 순서로 진행합니다.

// mm/page_alloc.c:4796-4807
retry:
	/* 루프하는 동안 kswapd가 실수로 잠들지 않도록 보장 */
	if (alloc_flags & ALLOC_KSWAPD)
		wake_all_kswapds(order, gfp_mask, ac);

	/*
	 * The adjusted alloc_flags might result in immediate success, so try
	 * that first
	 */
	page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
	if (page)
		goto got_pg;

// mm/page_alloc.c:4844-4856
	/* 직접 회수를 시도한 후 할당 */
	if (!compact_first) {
		page = __alloc_pages_direct_reclaim(gfp_mask, order, alloc_flags,
							ac, &did_some_progress);
		if (page)
			goto got_pg;
	}

	/* 직접 컴팩션을 시도한 후 할당 */
	page = __alloc_pages_direct_compact(gfp_mask, order, alloc_flags, ac,
					compact_priority, &compact_result);
	if (page)
		goto got_pg;

// mm/page_alloc.c:4906-4925
	if (should_reclaim_retry(gfp_mask, order, ac, alloc_flags,
				 did_some_progress > 0, &no_progress_loops))
		goto retry;

	/*
	 * It doesn't make any sense to retry for the compaction if the order-0
	 * reclaim is not able to make any progress because the current
	 * implementation of the compaction depends on the sufficient amount
	 * of free memory (see __compaction_suitable)
	 */
	if (did_some_progress > 0 && can_compact &&
			should_compact_retry(ac, order, alloc_flags,
				compact_result, &compact_priority,
				&compaction_retries))
		goto retry;

	/* 회수/컴팩션으로 대체를 방지하지 못함 */
	if (defrag_mode && (alloc_flags & ALLOC_NOFRAGMENT)) {
		alloc_flags &= ~ALLOC_NOFRAGMENT;
		goto retry;
	}

// mm/page_alloc.c:4936-4939
	/* 회수에 실패함, 프로세스 종료 시작 */
	page = __alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress);
	if (page)
		goto got_pg;

// mm/page_alloc.c:4966-4987
	if (unlikely(nofail)) {
		/*
		 * Lacking direct_reclaim we can't do anything to reclaim memory,
		 * we disregard these unreasonable nofail requests and still
		 * return NULL
		 */
		if (!can_direct_reclaim)
			goto fail;

		/*
		 * Help non-failing allocations by giving some access to memory
		 * reserves normally used for high priority non-blocking
		 * allocations but do not use ALLOC_NO_WATERMARKS because this
		 * could deplete whole memory reserves which would just make
		 * the situation worse.
		 */
		page = __alloc_pages_cpuset_fallback(gfp_mask, order, ALLOC_MIN_RESERVE, ac);
		if (page)
			goto got_pg;

		cond_resched();
		goto retry;
	}

---

관련 문서

메모리 관리 개요

SLUB 할당자

Memblock 할당자

페이지 회수 (vmscan)

Compaction

CMA

OOM Killer