Ryotta's Linux 7.0 MM

# 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)별 동작

Migratetype Fallback 순서

Zone Watermark 동작

외부/내부 단편화 비교

---

Buddy 관련 API 계층

GFP 컨텍스트 제약

증상별 진단 표

---

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