페이지 할당자 (Buddy Allocator)

Linux 커널의 Buddy Allocator는 물리 메모리(Physical Memory)를 페이지(Page) 단위(4KB)로 관리하는 1차 할당자입니다. 2^n 블록 할당, Buddy Coalescing, Zone 관리, GFP 플래그 체계를 종합적으로 다룹니다.

# Buddy Allocator 상태 확인
cat /proc/buddyinfo                        # Zone별 order 0~10 프리 블록 수
cat /proc/pagetypeinfo                     # 이동성 그룹별 상세
cat /proc/zoneinfo | head -80              # Zone 워터마크·통계
cat /proc/vmstat | grep pgalloc            # 할당 카운터

개요 (Overview)

Buddy Allocator는 1963년 Kenneth C. Knowlton이 제안한 알고리즘을 기반으로 합니다. 리눅스 커널에서는 물리 메모리 관리의 1차 할당자(primary allocator)로 사용되며, mm/page_alloc.c에 핵심 구현이 있습니다. Slab Allocator, vmalloc, Huge Pages 등 모든 상위 할당자가 최종적으로 Buddy Allocator를 통해 물리 페이지를 확보합니다.

• 물리 메모리 조직 — Node → Zone → Free Lists (order 0~10)
• 할당 단위 — 페이지 프레임(4KB on x86, 16KB on ARM64 optional)
• 분할과 병합 — 큰 블록을 쪼개고(split), 작은 블록을 합침(coalesce)
• MAX_ORDER — 기본값 11(order 0~10), 최대 블록 크기 2^10 = 1024 pages = 4MB
• 이동성 그룹 — 외부 단편화 방지를 위해 페이지를 UNMOVABLE/MOVABLE/RECLAIMABLE로 분류

/* mm/page_alloc.c — Buddy Allocator 핵심 진입점 (커널 6.x 기준) */

/* 페이지 할당: 모든 상위 할당자의 최종 경로 */
struct page *__alloc_pages(gfp_t gfp, unsigned int order,
                           int preferred_nid, nodemask_t *nodemask)
{
    struct alloc_context ac = { };
    struct page *page;

    /* 1) GFP 플래그 → Zone, 이동성 타입 결정 */
    gfp &= gfp_allowed_mask;
    prepare_alloc_pages(gfp, order, preferred_nid, nodemask, &ac);

    /* 2) Fast Path: Zonelist 순회하며 워터마크 충족 Zone에서 할당 */
    page = get_page_from_freelist(gfp, order, alloc_flags, &ac);
    if (likely(page))
        return page;

    /* 3) Slow Path: 회수/컴팩션/OOM 시도 */
    return __alloc_pages_slowpath(gfp, order, &ac);
}

/* 페이지 해제: buddy 합병까지 수행 */
void __free_pages(struct page *page, unsigned int order)
{
    if (put_page_testzero(page))
        free_the_page(page, order);
    /* → free_unref_page() → __free_one_page()에서 buddy coalesce */
}

NUMA Zonelist 구성

NUMA 시스템에서 각 Node는 자체 Zonelist를 가지며, get_page_from_freelist()는 이 리스트를 순회하면서 워터마크가 충족되는 첫 번째 Zone에서 페이지를 할당합니다. Zonelist는 로컬 Node의 상위 Zone부터 시작하여, 원격 Node의 Zone까지 폴백(fallback) 순서로 구성됩니다.

Buddy Allocator의 시간 복잡도는 다음과 같습니다:

자료구조 (Data Structures)

Free Area

Buddy Allocator의 핵심 자료구조는 free_area 배열입니다. 각 Zone은 MAX_ORDER개의 free_area 엔트리를 가지며, 각 엔트리는 해당 order의 빈 블록들을 Migrate Type별로 분리한 링크드 리스트로 관리합니다.

/* include/linux/mmzone.h */
struct free_area {
    struct list_head free_list[MIGRATE_TYPES]; /* migrate type별 리스트 */
    unsigned long nr_free;                     /* 이 order의 총 free 블록 수 */
};

/* zone 구조체 내 free_area 배열 */
struct zone {
    /* Watermarks */
    unsigned long _watermark[NR_WMARK];
    unsigned long watermark_boost;

    /* Lowmem reserve: 상위 zone 요청이 하위 zone을 고갈시키는 것 방지 */
    long lowmem_reserve[MAX_NR_ZONES];

    /* Per-CPU page cache */
    struct per_cpu_pages __percpu *per_cpu_pageset;

    /* Buddy free area: order 0~10 */
    struct free_area free_area[MAX_ORDER];

    /* Zone 통계 */
    unsigned long zone_start_pfn;     /* 시작 PFN */
    unsigned long spanned_pages;       /* 포함하는 전체 페이지 수 (구멍 포함) */
    unsigned long present_pages;       /* 실제 존재하는 페이지 수 */
    unsigned long managed_pages;       /* Buddy가 관리하는 페이지 수 */

    const char *name;                  /* "DMA", "Normal" 등 */
    /* ... */
};

메모리 Zone

리눅스 커널은 물리 메모리를 여러 Zone으로 분류합니다. 이는 하드웨어 제약(DMA 주소 범위)과 소프트웨어 정책(메모리 핫플러그(Hotplug))에 기반합니다. NUMA 시스템에서는 각 Node가 독립적인 Zone 집합을 가집니다.

Migrate Type

외부 단편화를 줄이기 위해 Buddy Allocator는 페이지를 이동 가능성에 따라 구분합니다. 같은 종류의 페이지끼리 모아두면 Memory Compaction이 훨씬 효율적으로 작동합니다:

/* include/linux/mmzone.h */
enum migratetype {
    MIGRATE_UNMOVABLE,   /* 이동 불가: 커널 모듈, kmalloc */
    MIGRATE_MOVABLE,     /* 이동 가능: 유저 프로세스 페이지 */
    MIGRATE_RECLAIMABLE, /* 회수 가능: 파일 페이지 캐시 */
    MIGRATE_PCPTYPES,    /* Per-CPU 캐시 대상 (위 3가지) */
    MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES, /* GFP_ATOMIC 긴급 예비 */
    MIGRATE_CMA,         /* CMA 연속 메모리 (카메라/동영상 DMA) */
    MIGRATE_ISOLATE,     /* 격리 중 (Compaction / Offlining) */
    MIGRATE_TYPES,
};

Zone 아키텍처

Zone은 단순한 주소 범위 분류가 아닙니다. 각 Zone은 독립적인 워터마크(Watermark), Per-CPU 캐시, 통계 카운터, 그리고 free_area[] 배열을 유지합니다. 할당 요청 시 Zone fallback 리스트를 따라 여러 Zone을 순회하며 페이지를 찾습니다.

Zone 워터마크와 lowmem_reserve

각 Zone은 lowmem_reserve[] 배열을 통해 상위 Zone의 요청이 하위 Zone을 고갈시키는 것을 방지합니다. 예를 들어, ZONE_NORMAL 요청이 ZONE_DMA32로 fallback할 때, DMA32의 lowmem_reserve[ZONE_NORMAL]만큼의 페이지는 예약되어 DMA32 전용 요청을 위해 보호됩니다.

/* mm/page_alloc.c - zone_watermark_fast (6.x 단순화) */
static inline bool zone_watermark_fast(
    struct zone *z, unsigned int order,
    unsigned long mark, int highest_zoneidx,
    unsigned int alloc_flags, gfp_t gfp_mask)
{
    long free_pages = zone_page_state(z, NR_FREE_PAGES);
    long min = mark;

    /* lowmem_reserve 추가: 하위 zone 보호 */
    min += z->lowmem_reserve[highest_zoneidx];

    /* CMA 영역은 MOVABLE 요청에만 사용 가능 */
    if (!(alloc_flags & ALLOC_CMA))
        free_pages -= zone_page_state(z, NR_FREE_CMA_PAGES);

    /* order 0 fast check */
    if (free_pages > min + z->_watermark[WMARK_LOW])
        return true;

    /* order > 0: 해당 order 이상의 블록이 존재하는지 확인 */
    return __zone_watermark_ok(z, order, mark,
        highest_zoneidx, alloc_flags, free_pages);
}

/* lowmem_reserve 계산: /proc/sys/vm/lowmem_reserve_ratio로 조정 */
/* 기본값: 256 256 32 (DMA:DMA32 비율, DMA32:Normal 비율, ...) */

# lowmem_reserve 현재 값 확인
cat /proc/zoneinfo | grep -A2 "protection"
# protection: (0, 2831, 15789, 15789)
# → DMA zone은 DMA32용 2831 pages, Normal용 15789 pages를 예약

# lowmem_reserve_ratio 조정
cat /proc/sys/vm/lowmem_reserve_ratio
# 256    256    32

버디 알고리즘 분할(Split) 상세

Buddy Allocator에서 요청한 order의 free 블록이 없으면, 상위 order의 블록을 찾아 재귀적으로 이진 분할(binary split)합니다. 이 과정은 __rmqueue() → __rmqueue_smallest() → expand() 함수 체인으로 구현됩니다.

/* mm/page_alloc.c - expand(): 상위 order 블록을 분할 */
static inline void expand(
    struct zone *zone, struct page *page,
    int low, int high,       /* low=요청 order, high=실제 블록 order */
    struct free_area *area,
    int migratetype)
{
    unsigned long size = 1 << high;

    while (high > low) {
        high--;
        size >>= 1;              /* 블록 크기 절반 */
        area--;                      /* 하위 order의 free_area로 이동 */

        /* 상위 절반(buddy)을 해당 order의 free list에 추가 */
        add_to_free_list(
            &page[size],             /* buddy page (후반부) */
            zone, high, migratetype);
        area->nr_free++;

        /* buddy의 private에 order 기록 (합병 시 사용) */
        set_buddy_order(&page[size], high);
    }
    /* 남은 page가 요청한 order의 블록 → 할당됨 */
}

/* mm/page_alloc.c - __rmqueue_smallest(): 최소 order에서 블록 찾기 */
static __always_inline 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_ORDER-1까지 순회 */
    for (current_order = order;
         current_order < MAX_ORDER; current_order++) {
        area = &(zone->free_area[current_order]);
        page = get_page_from_free_area(area, migratetype);
        if (!page)
            continue;  /* 이 order에 free 블록 없음 */

        /* free list에서 제거 */
        del_page_from_free_list(page, zone, current_order);
        /* 필요한 만큼만 분할 */
        expand(zone, page, order, current_order, area, migratetype);
        set_pcppage_migratetype(page, migratetype);
        return page;
    }
    return NULL;  /* 모든 order에서 실패 */
}

버디 알고리즘 합체(Coalesce) 상세

페이지가 해제되면 Buddy Allocator는 해당 블록의 buddy가 free인지 확인하고, free이면 두 블록을 합쳐서 한 단계 큰 order의 블록으로 만듭니다. 이 과정을 buddy coalescing이라 하며, __free_one_page() 함수에서 구현됩니다.

Buddy 주소 계산

/* include/linux/mmzone.h - buddy PFN 계산 */
static inline unsigned long __find_buddy_pfn(
    unsigned long page_pfn, unsigned int order)
{
    /*
     * buddy pfn = page_pfn ^ (1 << order)
     *
     * 예: page_pfn=0x100, order=2
     *     buddy = 0x100 ^ 0x4 = 0x104
     *
     * 예: page_pfn=0x104, order=2
     *     buddy = 0x104 ^ 0x4 = 0x100
     *
     * → XOR은 대칭적이므로 A의 buddy의 buddy는 항상 A
     */
    return page_pfn ^ (1 << order);
}

/* buddy가 합병 가능한지 확인 */
static inline bool page_is_buddy(
    struct page *page, struct page *buddy,
    unsigned int order)
{
    /* 1. buddy가 free_area의 free list에 있는가? */
    if (!page_is_guard(buddy) &&
        !PageBuddy(buddy))       /* PG_buddy 플래그 */
        return false;

    /* 2. buddy의 order가 같은가? */
    if (buddy_order(buddy) != order)
        return false;

    /* 3. 같은 zone에 속하는가? */
    if (page_zone_id(page) != page_zone_id(buddy))
        return false;

    return true;
}

합체 과정 (Coalescing Loop)

/* mm/page_alloc.c - __free_one_page() 핵심 로직 (단순화) */
static inline void __free_one_page(
    struct page *page, unsigned long pfn,
    struct zone *zone, unsigned int order,
    int migratetype)
{
    unsigned long buddy_pfn;
    struct page *buddy;

    while (order < MAX_ORDER - 1) {
        /* buddy PFN 계산 (XOR) */
        buddy_pfn = __find_buddy_pfn(pfn, order);
        buddy = page + (buddy_pfn - pfn);

        /* buddy가 합병 가능한지 확인 */
        if (!page_is_buddy(page, buddy, order))
            break;  /* buddy가 사용 중이거나 다른 order */

        /* buddy를 현재 free list에서 제거 */
        del_page_from_free_list(buddy, zone, order);

        /* 합병: 작은 주소가 새 블록의 시작 */
        unsigned long combined_pfn = buddy_pfn & pfn;
        page = page + (combined_pfn - pfn);
        pfn = combined_pfn;

        order++;  /* 한 단계 큰 order */
    }

    /* 최종 블록을 해당 order의 free list에 추가 */
    add_to_free_list(page, zone, order, migratetype);
    area->nr_free++;
    set_buddy_order(page, order);
}

페이지 해제 전체 흐름

__free_pages() 호출 시 order에 따라 PCP(Per-CPU Page) 캐시 또는 Buddy 시스템으로 반환되는 전체 경로입니다.

페이지 이동성 그룹 (Page Mobility)

외부 단편화의 핵심 원인은 이동 불가능한(unmovable) 페이지가 연속 영역 중간에 박혀 있는 것입니다. 리눅스 커널은 이를 해결하기 위해 물리 메모리를 pageblock 단위(보통 2MB, huge page 크기)로 나누고, 각 pageblock에 이동성 유형을 부여합니다.

/* include/linux/mmzone.h */
#define MIGRATE_UNMOVABLE     0  /* 이동 불가: 커널 slab, 모듈, DMA 버퍼 */
#define MIGRATE_MOVABLE       1  /* 이동 가능: 유저 프로세스 페이지, 파일 맵 */
#define MIGRATE_RECLAIMABLE   2  /* 회수 가능: 페이지 캐시, dentry 캐시 */
#define MIGRATE_PCPTYPES      3  /* PCP가 캐시하는 타입 수 (위 3개) */
#define MIGRATE_HIGHATOMIC    3  /* GFP_ATOMIC 전용 예비 (= PCPTYPES) */
#define MIGRATE_CMA           4  /* CMA 연속 영역 (DMA용) */
#define MIGRATE_ISOLATE       5  /* 격리 중 (offlining, compaction) */

/* pageblock_order: 이동성 그룹의 단위 (보통 huge page order) */
/* x86_64: pageblock_order = 9 (512 pages = 2MB) */
/* ARM64 4K: pageblock_order = 9 (2MB) */
/* ARM64 64K: pageblock_order = 13 (512MB, 아키텍처 의존) */

Fallback 배열

/* mm/page_alloc.c - fallback 순서 */
static int fallbacks[MIGRATE_TYPES][3] = {
    [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
    [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
    [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
};

/*
 * UNMOVABLE 요청 시:
 *   1. UNMOVABLE free list에서 시도
 *   2. 실패 → RECLAIMABLE에서 steal
 *   3. 실패 → MOVABLE에서 steal
 *
 * Steal 시 가능하면 전체 pageblock을 전환 (단편화 최소화)
 */

__rmqueue_fallback() Steal 메커니즘 상세

요청한 migrate type의 free list가 비어 있으면 __rmqueue_fallback()이 호출되어 다른 migrate type에서 페이지를 빌려옵니다(steal). 이때 find_suitable_fallback()이 fallback 테이블을 순회하면서 적절한 소스를 찾습니다. 핵심 전략은 가장 큰 order부터 시도하는 것입니다. 큰 블록을 통째로 steal하면 남은 조각이 줄어 단편화를 최소화할 수 있기 때문입니다.

/* mm/page_alloc.c - find_suitable_fallback() */
static int find_suitable_fallback(struct free_area *area,
    unsigned int order, int migratetype,
    bool only_stealable, bool *can_steal)
{
    int i;
    int fallback_mt;
    /* 가장 큰 order부터 시도: 큰 블록을 steal하면 단편화 최소 */
    if (area->nr_free == 0)
        return -1;
    /* fallbacks[] 테이블 순회 */
    *can_steal = false;
    for (i = 0; i < MIGRATE_PCPTYPES; i++) {
        fallback_mt = fallbacks[migratetype][i];
        if (fallback_mt == MIGRATE_TYPES)
            break;
        if (!free_area_empty(area, fallback_mt)) {
            /* pageblock 크기 이상이면 전체 전환 가능 */
            if (can_steal_fallback(order, migratetype))
                *can_steal = true;
            return fallback_mt;
        }
    }
    return -1;
}

steal_suitable_fallback()은 실제 steal 작업을 수행합니다. Pageblock stealing이 핵심인데, steal하려는 블록의 order가 pageblock_order(보통 order-9, 2MB) 이상이거나, 해당 pageblock 내 대부분의 free 페이지가 이미 요청 type이면 pageblock 전체의 migrate type을 변경합니다. 이렇게 하면 이후 같은 type의 할당이 같은 pageblock에서 이루어져 장기적으로 단편화가 줄어듭니다.

API (Application Programming Interface)

페이지 할당

/* include/linux/gfp.h */
struct page *alloc_pages(gfp_t gfp_mask, unsigned int order);
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order);
unsigned long get_zeroed_page(gfp_t gfp_mask);

/* 사용 예 */
struct page *page = alloc_pages(GFP_KERNEL, 2);  /* 2^2 = 4 pages = 16KB */
void *addr = page_address(page);

페이지 해제

void __free_pages(struct page *page, unsigned int order);
void free_pages(unsigned long addr, unsigned int order);

/* 사용 예 */
__free_pages(page, 2);

NUMA 인식 할당 API

/* include/linux/gfp.h - NUMA 노드 지정 할당 */
struct page *alloc_pages_node(int nid, gfp_t gfp_mask, unsigned int order);
struct page *alloc_pages_current(gfp_t gfp_mask, unsigned int order);

/* Migrate Type 명시 할당 (내부 API) */
struct page *alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
    int preferred_nid, nodemask_t *nodemask);

/* 현재 CPU가 속한 NUMA 노드에서 할당 */
struct page *page = alloc_pages_node(numa_node_id(), GFP_KERNEL, 0);

/* GFP_THISNODE: 지정 노드에서만 할당, 실패 시 NULL 반환 */
page = alloc_pages_node(target_nid, GFP_KERNEL | __GFP_THISNODE, 0);

GFP 플래그 완전 분류

GFP(Get Free Pages) 플래그는 Buddy Allocator의 할당 정책을 제어하는 비트마스크입니다. 복합 플래그(compound flags)와 기본 비트 플래그(__GFP_ prefix)로 나뉩니다. 올바른 GFP 플래그 선택은 시스템 안정성에 직결됩니다.

복합 GFP 플래그 (Compound Flags)

기본 __GFP 비트 플래그

/* GFP 플래그 사용 예제: 컨텍스트별 올바른 선택 */

/* 1) 프로세스 컨텍스트 — 가장 일반적 */
buf = kmalloc(4096, GFP_KERNEL);

/* 2) 인터럽트/softirq 컨텍스트 — 대기 불가 */
skb = alloc_skb(ETH_FRAME_LEN, GFP_ATOMIC);

/* 3) 블록 I/O 레이어 — I/O 재귀 교착 방지 */
page = alloc_page(GFP_NOIO | __GFP_ZERO);

/* 4) 파일시스템 레이어 — FS 재귀 교착 방지 */
folio = filemap_alloc_folio(GFP_NOFS, 0);

/* 5) 유저 페이지 (이동·컴팩션 가능) */
page = alloc_pages(GFP_HIGHUSER_MOVABLE, 0);

/* 6) 대형 할당 (실패 허용, OOM 미발동) */
pages = alloc_pages(GFP_KERNEL | __GFP_RETRY_MAYFAIL | __GFP_NOWARN, 4);

/* 7) 반드시 성공해야 하는 할당 (극도로 주의) */
page = alloc_page(GFP_KERNEL | __GFP_NOFAIL);

알고리즘 (Algorithm)

블록 분할 (Split)

요청: order 1 (2 pages)
가용: order 3 (8 pages) 하나만 존재

1. order 3 블록을 꺼냄 (8 pages)
2. 반으로 쪼갬: 2개의 order 2 블록 (4 pages each)
3. 하나를 다시 쪼갬: 2개의 order 1 블록 (2 pages each)
4. 하나는 할당, 나머지는 free list에 반환

결과:
- 할당: order 1 (2 pages)
- 반환: order 1 (2 pages), order 2 (4 pages)

블록 병합 (Coalesce)

반환: order 1 블록 (주소 0x1000)

1. Buddy 주소 계산: 0x1000 XOR (2 << 12) = 0x3000
2. Buddy가 free이고 같은 order인가? → YES
3. 두 블록을 병합하여 order 2 생성
4. 재귀적으로 반복 (order 2의 buddy 확인)

결과: 최대한 큰 블록으로 병합되어 외부 단편화 감소

시각적 이해: 분할 과정

할당 Fast Path vs Slow Path

alloc_pages() 호출은 두 단계로 처리됩니다. Fast Path에서 즉시 성공하면 Slow Path의 대기 비용을 치르지 않습니다. Fast Path는 WMARK_LOW를 기준으로, Slow Path는 WMARK_MIN까지 허용하며 메모리 회수/압축을 시도합니다:

Fast Path

/* mm/page_alloc.c - 단순화한 흐름 */
struct page *__alloc_pages(gfp_t gfp, unsigned int order,
    int preferred_nid, nodemask_t *nodemask)
{
    struct alloc_context ac = {};
    struct page *page;

    /* order 0: Per-CPU 캐시에서 lock-free 할당 시도 */
    if (likely(order == 0)) {
        page = get_page_from_freelist(gfp, 0, ALLOC_WMARK_LOW, &ac);
        if (likely(page))
            return page;
    }

    /* 일반 Free List에서 시도 (WMARK_LOW 이상인 경우) */
    page = get_page_from_freelist(gfp, order, ALLOC_WMARK_LOW, &ac);
    if (likely(page))
        return page;

    /* Fast path 실패 → Slow path */
    return __alloc_pages_slowpath(gfp, order, &ac);
}

get_page_from_freelist() 상세

Fast Path와 Slow Path 모두 get_page_from_freelist()를 호출합니다. 이 함수는 Zone fallback 리스트를 순회하며, 워터마크 검사를 통과하는 Zone에서 페이지를 할당합니다.

/* mm/page_alloc.c - get_page_from_freelist() 핵심 로직 (단순화) */
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;
    struct page *page;

    /* Zone fallback 리스트 순회 */
    for_next_zone_zonelist_nodemask(zone, z,
        ac->highest_zoneidx, ac->nodemask) {

        /* NUMA: cpuset 제한 확인 */
        if (cpusets_enabled() &&
            (alloc_flags & ALLOC_CPUSET) &&
            !__cpuset_zone_allowed(zone, gfp_mask))
            continue;

        /* 워터마크 검사 */
        if (!zone_watermark_fast(zone, order,
            min_wmark_pages(zone) +
            z->lowmem_reserve[ac->highest_zoneidx],
            ac->highest_zoneidx, alloc_flags, gfp_mask))
            continue;

        /* 이 Zone에서 할당 시도 */
        page = rmqueue(ac->preferred_zoneref->zone,
            zone, order, gfp_mask, alloc_flags,
            ac->migratetype);
        if (page) {
            prep_new_page(page, order, gfp_mask, alloc_flags);
            return page;
        }
    }
    return NULL;
}

/* rmqueue(): order에 따라 PCP 또는 Buddy에서 할당 */
static inline struct page *rmqueue(...)
{
    if (likely(order == 0)) {
        /* order 0: PCP 캐시에서 할당 */
        page = rmqueue_pcplist(...);
    } else {
        /* order > 0: Zone lock 잡고 Buddy freelist에서 할당 */
        spin_lock_irqsave(&zone->lock, flags);
        page = __rmqueue(zone, order, migratetype, alloc_flags);
        spin_unlock_irqrestore(&zone->lock, flags);
    }
    return page;
}

Slow Path

/* mm/page_alloc.c - __alloc_pages_slowpath 핵심 로직 */
static struct page *__alloc_pages_slowpath(gfp_t gfp_mask,
    unsigned int order, struct alloc_context *ac)
{
    /* 1단계: kswapd 깨우기 (비동기 메모리 회수 시작) */
    wake_all_kswapds(order, gfp_mask, ac);

    /* 2단계: ALLOC_WMARK_MIN으로 낮춰서 재시도 */
    page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
    if (page)
        goto got_pg;

    /* 3단계: 메모리 Compaction 후 재시도 */
    page = __alloc_pages_direct_compact(gfp_mask, order,
        alloc_flags, ac, compact_priority, &compact_result);
    if (page)
        goto got_pg;

    /* 4단계: 직접 메모리 회수 (프로세스 차단) */
    page = __alloc_pages_direct_reclaim(gfp_mask, order,
        alloc_flags, ac, &did_some_progress);
    if (page)
        goto got_pg;

    /* 5단계: OOM Killer 호출 (최후 수단) */
    if (!(gfp_mask & __GFP_NORETRY)) {
        page = __alloc_pages_may_oom(gfp_mask, order, ac,
            &did_some_progress);
    }

got_pg:
    return page;
}

Slow Path 상세 동작 순서

각 단계에서 성공하면 즉시 반환합니다. __GFP_NORETRY가 설정된 경우 단계 4 이후 포기합니다. __GFP_RETRY_MAYFAIL은 여러 번 반복하되 무한 루프는 피합니다. __GFP_NOFAIL은 성공할 때까지 무한 반복합니다 (극히 주의).

prep_new_page(): 할당 후 페이지 준비

Buddy Allocator가 free list에서 페이지를 꺼낸 후, 호출자에게 반환하기 전에 prep_new_page()가 여러 초기화 작업을 수행합니다. 이 단계에서 페이지의 상태 플래그를 정리하고, 보안과 디버깅을 위한 검증 및 초기화가 이루어집니다.

/* mm/page_alloc.c - prep_new_page() 핵심 로직 */
static int prep_new_page(struct page *page, unsigned int order,
                         gfp_t gfp_flags, unsigned int alloc_flags)
{
    /* 1. 페이지 상태 검증: PG_locked, PG_lru 등 설정되어 있으면 BUG */
    if (unlikely(check_new_pages(page, order)))
        return 1;

    /* 2. post_alloc_hook(): 할당 후 처리 */
    post_alloc_hook(page, order, gfp_flags);

    /* 3. __GFP_ZERO 플래그 시 페이지 내용 0으로 초기화 */
    if (gfp_flags & __GFP_ZERO)
        for (i = 0; i < (1 << order); i++)
            clear_highpage(page + i);

    /* 4. _refcount을 1로 설정 (이제부터 사용 중) */
    set_page_refcounted(page);

    return 0;
}

/* post_alloc_hook()이 수행하는 작업들 */
static void post_alloc_hook(struct page *page, unsigned int order,
                            gfp_t gfp_flags)
{
    set_page_private(page, 0);          /* private 필드 초기화 */
    set_page_refcounted(page);          /* _refcount = 1 */
    arch_alloc_page(page, order);       /* 아키텍처별 후처리 */
    kernel_init_pages(page, 1 << order); /* init_on_alloc=1 시 zeroing */
    kernel_poison_pages(page, 1 << order); /* PAGE_POISONING 검증 */
    set_page_owner(page, order, gfp_flags); /* page_owner 추적 */
    page_table_check_alloc(page, order);  /* 페이지 테이블 무결성 */
}

각 단계의 역할을 정리하면 다음과 같습니다.

부팅 시 Buddy 초기화

시스템 부팅 과정(Boot Process)에서 Buddy Allocator는 다음 순서로 초기화됩니다. 이 과정이 완료되어야 alloc_pages()가 동작합니다.

/* 부팅 초기화 순서 (아키텍처별로 약간 다름) */

/* 1. memblock에서 물리 메모리 레이아웃 파악 */
memblock_add(base, size);     /* 펌웨어가 보고한 메모리 영역 등록 */
memblock_reserve(base, size); /* 커널 이미지, initrd 등 예약 */

/* 2. Node/Zone 구조 초기화 */
free_area_init();              /* zone별 free_area, watermark 초기화 */

/* 3. memblock에서 Buddy로 페이지 이관 */
memblock_free_all();           /* 미예약 영역의 페이지를 Buddy에 추가 */
  /* → __free_pages_core() → __free_one_page() */
  /* → 가능한 한 큰 order로 합체하여 free_area에 추가 */

/* 4. Per-CPU 페이지 캐시 초기화 */
setup_per_cpu_pageset();       /* 각 CPU의 per_cpu_pages 구조체 설정 */

/* 5. 워터마크 계산 */
init_per_zone_wmark_min();     /* min_free_kbytes 기반 워터마크 설정 */

/* dmesg에서 확인 가능한 메시지 */
/* "Zone ranges:" → Zone별 PFN 범위 */
/* "Movable zone start for each node" */
/* "Early memory node ranges" */
/* "Memory: 16384000K/16777216K available" → Buddy에 이관된 메모리 */

# 부팅 시 Buddy 초기화 로그 확인
dmesg | grep -E "(Zone ranges|free_area_init|Memory:)"
# [    0.000000] Zone ranges:
# [    0.000000]   DMA      [mem 0x0000000000001000-0x0000000000ffffff]
# [    0.000000]   DMA32    [mem 0x0000000001000000-0x00000000ffffffff]
# [    0.000000]   Normal   [mem 0x0000000100000000-0x00000003ffffffff]
# [    0.000000] Memory: 16127744K/16777216K available
# → (16777216 - 16127744) KB = 약 634MB가 커널/예약으로 사용됨

# memblock 레이아웃 확인 (부팅 시에만)
dmesg | grep -E "(memblock|reserve)" | head -n 20

부팅 초기화 순서

커널 부팅 시 물리 메모리는 다음 단계를 거쳐 Buddy Allocator로 이관됩니다. 초기에는 memblock이 모든 메모리를 관리하고, 부팅이 완료되면 Buddy 시스템이 인계받습니다.

Zone 워터마크 (Zone Watermark)

각 Zone은 세 가지 워터마크를 유지합니다. 여유 페이지가 워터마크 아래로 떨어지면 메모리 회수가 시작됩니다:

/* include/linux/mmzone.h */
enum zone_watermarks {
    WMARK_MIN,
    WMARK_LOW,
    WMARK_HIGH,
    WMARK_PROMO,  /* 6.1+: promotion threshold */
    NR_WMARK
};

/* 워터마크 검사 (mm/page_alloc.c) */
static inline bool zone_watermark_ok(struct zone *z,
    unsigned int order, unsigned long mark,
    int highest_zoneidx, unsigned int alloc_flags)
{
    long min = mark;
    long free_pages = zone_page_state(z, NR_FREE_PAGES);
    return free_pages >= min + z->lowmem_reserve[highest_zoneidx];
}

# 현재 워터마크 확인
cat /proc/zoneinfo | grep -A8 "zone   Normal"
# pages free     45321
#       min      1440     ← WMARK_MIN
#       low      1800     ← WMARK_LOW
#       high     2160     ← WMARK_HIGH

# 워터마크 조정 (vm.min_free_kbytes가 WMARK_MIN 기준)
sysctl vm.min_free_kbytes
# vm.min_free_kbytes = 67584

# 즉시 메모리 Compaction 강제 실행
echo 1 > /proc/sys/vm/compact_memory

Watermark 시스템 상세

워터마크는 각 Zone의 메모리 압박 수준을 정량적으로 표현하는 임계값입니다. 워터마크 값은 부팅 시 vm.min_free_kbytes로부터 계산되며, 런타임에 watermark_boost로 동적 조정됩니다.

워터마크 계산

/* mm/page_alloc.c - __setup_per_zone_wmarks() */
/*
 * 계산 공식:
 *   WMARK_MIN = min_free_kbytes / PAGE_SIZE / zone 수 (비율)
 *   WMARK_LOW = WMARK_MIN + WMARK_MIN / 4   (= 1.25 × MIN)
 *   WMARK_HIGH = WMARK_MIN + WMARK_MIN / 2  (= 1.5 × MIN)
 *
 * watermark_scale_factor (/proc/sys/vm/watermark_scale_factor)
 * → 0.1% ~ 10% 범위로 LOW/HIGH 간격 조정
 */

static void __setup_per_zone_wmarks(void)
{
    unsigned long pages_min = min_free_kbytes >> (PAGE_SHIFT - 10);

    for_each_zone(zone) {
        unsigned long min_pages, tmp;

        /* managed_pages 비율로 분배 */
        tmp = (u64)pages_min * zone_managed_pages(zone);
        do_div(tmp, total_managed);
        min_pages = tmp;

        zone->_watermark[WMARK_MIN] = min_pages;

        /* LOW = MIN + (MIN/4) 또는 watermark_scale_factor 기반 */
        tmp = max(min_pages / 4,
            mult_frac(zone_managed_pages(zone),
                watermark_scale_factor, 10000));
        zone->_watermark[WMARK_LOW] = min_pages + tmp;

        /* HIGH = MIN + (MIN/2) 또는 2배 scale */
        zone->_watermark[WMARK_HIGH] = min_pages + tmp * 2;

        zone->watermark_boost = 0;
    }
}

Watermark Boost

커널 5.0+에서 도입된 watermark_boost는 외부 단편화가 감지되면 (migrate type fallback 발생 시) 해당 Zone의 HIGH 워터마크를 일시적으로 상향하여 kswapd가 더 적극적으로 메모리를 회수하도록 유도합니다.

/* mm/page_alloc.c - boost_watermark() */
static void boost_watermark(struct zone *zone)
{
    unsigned long max_boost;

    if (!watermark_boost_factor)
        return;

    /* boost 상한: WMARK_HIGH의 watermark_boost_factor배 */
    max_boost = mult_frac(zone->_watermark[WMARK_HIGH],
        watermark_boost_factor, 10000);

    /* pageblock 단위만큼 boost 증가 */
    if (zone->watermark_boost < max_boost)
        zone->watermark_boost += pageblock_nr_pages;
}

/* boost된 워터마크 읽기 */
static inline unsigned long wmark_pages(
    const struct zone *z, enum zone_watermarks w)
{
    return z->_watermark[w] + z->watermark_boost;
}

PCP (Per-CPU Page) 캐싱 상세

Order 0 (단일 페이지) 할당은 리눅스 커널에서 가장 빈번하게 발생합니다 (전체 할당의 90% 이상). 매번 Zone lock을 잡고 Buddy free list에 접근하면 심각한 경합이 발생하므로, 커널은 CPU별 페이지 캐시(PCP, Per-CPU Pages)를 유지합니다.

/* mm/page_alloc.c - PCP 관련 구조체 (6.x) */
struct per_cpu_pages {
    spinlock_t lock;          /* local lock (CPU 전환 방지) */
    int  count;                /* 현재 캐시된 총 페이지 수 */
    int  high;                 /* 상한: 초과 시 free_pcppages_bulk() */
    int  high_min;             /* 최소 high 값 */
    int  high_max;             /* 최대 high 값 (동적 조절 상한) */
    int  batch;                /* Buddy로 한 번에 교환할 페이지 수 */
    short free_count;          /* free_pcppages_bulk 카운터 */
    struct list_head lists[NR_PCP_LISTS]; /* migrate type별 리스트 */
};

/* NR_PCP_LISTS = MIGRATE_PCPTYPES * (pcp_order_max + 1)
 * 기본: 3 × 1 = 3 (order 0만)
 * CONFIG_TRANSPARENT_HUGEPAGE: 3 × (THP_order + 1) */

/* PCP에서 할당 (order 0) */
static struct page *rmqueue_pcplist(
    struct zone *preferred_zone,
    struct zone *zone,
    gfp_t gfp_flags,
    int migratetype,
    unsigned int alloc_flags)
{
    struct per_cpu_pages *pcp;
    struct list_head *list;

    pcp = this_cpu_ptr(zone->per_cpu_pageset);
    list = &pcp->lists[order_to_pindex(migratetype, 0)];

    if (list_empty(list)) {
        /* 캐시 고갈: Buddy에서 batch만큼 보충 */
        int nr = rmqueue_bulk(zone, 0,
            READ_ONCE(pcp->batch),
            list, migratetype, alloc_flags);
        pcp->count += nr;
    }

    page = list_first_entry(list, struct page, pcp_list);
    list_del(&page->pcp_list);
    pcp->count--;

    /* high 초과 시 batch만큼 Buddy에 반환 */
    if (pcp->count >= pcp->high)
        free_pcppages_bulk(zone,
            READ_ONCE(pcp->batch),
            pcp, migratetype);

    return page;
}

컴팩션 (Compaction)

메모리 Compaction은 흩어진 free 페이지를 한쪽으로 모아 연속 영역을 만드는 과정입니다. 고차 할당(order 1 이상)이 실패할 때 Slow Path에서 호출되며, 별도 커널 스레드 kcompactd가 백그라운드에서도 수행합니다.

/* mm/compaction.c - compact_zone() 핵심 로직 (단순화) */
static enum compact_result compact_zone(
    struct compact_control *cc)
{
    /*
     * 두 스캐너가 양끝에서 중앙으로 이동:
     *   - migrate_scanner: zone 시작에서 → (사용 중인 MOVABLE 페이지 수집)
     *   - free_scanner: zone 끝에서 ← (free 페이지 수집)
     * 두 스캐너가 만나면 완료
     */

    while (cc->migrate_pfn < cc->free_pfn) {
        /* 1. 이동 대상 페이지 수집 (MOVABLE만) */
        nr_migrated = isolate_migratepages(cc);
        if (!nr_migrated)
            continue;

        /* 2. free 페이지 수집 (목적지) */
        nr_freepages = isolate_freepages(cc);
        if (!nr_freepages) {
            putback_movable_pages(&cc->migratepages);
            break;
        }

        /* 3. 페이지 이동 (migrate_pages) */
        err = migrate_pages(&cc->migratepages,
            compaction_alloc, compaction_free,
            (unsigned long)cc, cc->mode,
            MR_COMPACTION);

        /* 4. 충분한 고차 블록이 생겼는지 확인 */
        if (compact_zone_order_suitable(cc))
            return COMPACT_SUCCESS;
    }
    return cc->result;
}

# compaction 통계 확인
cat /proc/vmstat | grep compact
# compact_stall 1234          ← direct compaction 호출 횟수
# compact_success 890          ← 성공 횟수
# compact_fail 344             ← 실패 횟수
# compact_daemon_wake 567      ← kcompactd 기동 횟수
# compact_migrate_scanned 45678 ← 스캔한 페이지 수
# compact_free_scanned 89012   ← free 스캔 페이지 수

# kcompactd 상태 확인
ps aux | grep kcompactd
# root  ... [kcompactd0]  ← Node 0의 compaction 데몬

# 수동 compaction 트리거
echo 1 > /proc/sys/vm/compact_memory

struct page와 folio

struct page는 리눅스 커널에서 모든 물리 페이지 프레임의 메타데이터를 담는 기본 자료구조입니다. 시스템의 모든 물리 페이지마다 하나의 struct page가 존재하며, mem_map[] 배열로 관리됩니다. Buddy Allocator는 이 구조체(Struct)의 여러 필드를 활용합니다.

/* include/linux/mm_types.h - struct page (주요 필드만, 6.x) */
struct page {
    unsigned long flags;       /* PG_locked, PG_buddy, PG_slab, ... */

    union {
        struct {                /* Buddy allocator 사용 시 */
            union {
                struct list_head buddy_list;  /* free list 연결 */
                struct list_head pcp_list;    /* PCP list 연결 */
            };
            unsigned long private;   /* buddy order (PG_buddy 시) */
        };

        struct {                /* Page cache / anon page 사용 시 */
            struct list_head lru;        /* LRU list 연결 */
            struct address_space *mapping; /* 소속 address_space */
            pgoff_t index;                /* 매핑 내 오프셋 */
            unsigned long private;        /* buffer_head 등 */
        };

        struct {                /* Slab allocator 사용 시 */
            struct kmem_cache *slab_cache;
            void *freelist;
            union {
                unsigned long counters;
                struct { unsigned inuse:16; unsigned objects:15; };
            };
        };

        struct {                /* Compound page (tail page) */
            unsigned long compound_head;  /* head page 포인터 + 1 */
        };
    };

    union {
        atomic_t _mapcount;        /* 페이지 테이블 매핑 수 (-1 = 미매핑) */
        unsigned int page_type;    /* PageBuddy, PageOffline 등 */
    };

    atomic_t _refcount;            /* 참조 카운트 (0이면 free 가능) */
};

vmemmap과 struct page 배열 매핑

리눅스 커널은 모든 물리 페이지 프레임(Page Frame)에 대응하는 struct page 배열을 vmemmap 영역에 매핑합니다. 이를 통해 PFN(Page Frame Number)에서 struct page 포인터로의 변환이 O(1) 상수 시간에 이루어집니다. x86_64에서 struct page는 64바이트이므로, pfn_to_page(pfn)은 단순히 vmemmap + pfn으로 계산됩니다.

Compound Page와 Folio

/* Compound Page: order > 0 할당 시 생성 (__GFP_COMP 사용) */
/*
 * order 2 compound page (4 pages):
 *   page[0]: head page (PG_head set)
 *     - compound_dtor: destructor 인덱스
 *     - compound_order: order 값
 *     - compound_nr: 총 페이지 수 (1 << order)
 *   page[1..3]: tail pages
 *     - compound_head = &page[0] | 1  (최하위 비트로 tail 표시)
 */

/* include/linux/page-flags.h */
static inline bool PageCompound(struct page *page)
{
    return test_bit(PG_head, &page->flags) ||
           READ_ONCE(page->compound_head) & 1;
}

/* include/linux/mm_types.h - folio (6.x) */
/*
 * struct folio = compound page의 head page를 타입 안전하게 감싼 것
 * page cache, file-backed page에서 점차 struct page를 대체
 */
struct folio {
    union {
        struct {
            unsigned long flags;
            union {
                struct list_head lru;
                struct { void *__filler; unsigned int mlock_count; };
            };
            struct address_space *mapping;
            pgoff_t index;
            void *private;
            atomic_t _mapcount;
            atomic_t _refcount;
        };
        struct page page;  /* struct page와 메모리 호환 */
    };
};

/* folio ↔ page 변환 */
struct folio *page_folio(struct page *page);
struct page *folio_page(struct folio *folio, size_t n);
size_t folio_size(struct folio *folio);
size_t folio_nr_pages(struct folio *folio);

메모리 핫플러그 연동

메모리 핫플러그(Memory Hotplug)는 시스템 운영 중에 물리 메모리를 추가/제거하는 기능입니다. 클라우드 환경, 가상화(Virtualization), DIMM 교체 등에서 사용됩니다. Buddy Allocator는 핫플러그된 메모리를 ZONE_MOVABLE에 배치하여 나중에 안전하게 제거할 수 있도록 합니다.

/* mm/memory_hotplug.c - 온라인 경로 (단순화) */
int online_pages(unsigned long pfn, unsigned long nr_pages,
    struct zone *zone, struct memory_group *group)
{
    /* 1. 페이지를 Buddy에 등록 */
    move_pfn_range_to_zone(zone, pfn, nr_pages, NULL, MIGRATE_ISOLATE);

    /* 2. memmap 초기화 */
    memmap_init_range(nr_pages, nid, zone_idx(zone), pfn,
        MEMINIT_HOTPLUG, NULL, MIGRATE_MOVABLE);

    /* 3. 페이지를 Buddy free list에 추가 */
    for (pfn = start; pfn < end; pfn += pageblock_nr_pages) {
        set_pageblock_migratetype(
            pfn_to_page(pfn), MIGRATE_MOVABLE);
    }

    /* 4. Zone 통계 업데이트 */
    zone->present_pages += nr_pages;
    zone->managed_pages += nr_pages;
    setup_per_zone_wmarks();  /* 워터마크 재계산 */

    return 0;
}

/* mm/memory_hotplug.c - 오프라인 경로 (단순화) */
int offline_pages(unsigned long start_pfn, unsigned long nr_pages,
    struct zone *zone)
{
    /* 1. 해당 영역의 pageblock을 MIGRATE_ISOLATE로 변경 */
    start_isolate_page_range(start_pfn, end_pfn,
        MIGRATE_MOVABLE, MEMORY_OFFLINE);

    /* 2. 사용 중인 페이지를 다른 영역으로 이동 */
    do {
        ret = scan_movable_pages(pfn, end_pfn, &pfn);
        if (!ret)
            do_migrate_range(pfn, end_pfn);  /* compaction과 유사 */
    } while (!ret);

    /* 3. Buddy에서 페이지 해제 */
    dissolve_free_huge_pages(start_pfn, end_pfn);
    undo_isolate_page_range(start_pfn, end_pfn, MIGRATE_MOVABLE);

    /* 4. Zone 통계 업데이트 */
    zone->present_pages -= nr_pages;
    zone->managed_pages -= nr_pages;
    setup_per_zone_wmarks();

    return 0;
}

# 메모리 블록 상태 확인
ls /sys/devices/system/memory/
# memory0  memory1  memory2  ... memory255

cat /sys/devices/system/memory/memory32/state
# online

# 메모리 블록 오프라인 (이동 가능한 페이지만 포함된 경우)
echo offline > /sys/devices/system/memory/memory32/state

# 메모리 블록 온라인 (ZONE_MOVABLE에 배치)
echo online_movable > /sys/devices/system/memory/memory32/state

# ZONE_MOVABLE 범위 확인 (커널 부트 파라미터)
# kernelcore=4G → 4GB는 ZONE_NORMAL, 나머지는 ZONE_MOVABLE
# movablecore=8G → 8GB를 ZONE_MOVABLE로 설정
cat /proc/zoneinfo | grep -A5 "zone  Movable"

CMA (Contiguous Memory Allocator)

CMA는 디바이스 드라이버가 필요로 하는 대형 연속 물리 메모리를 보장하기 위한 할당자입니다. 부팅 시 특정 영역을 CMA용으로 예약하지만, 평소에는 MOVABLE 페이지에 사용할 수 있어 메모리 낭비를 최소화합니다.

/* drivers/dma-buf/dma-alloc.c (이전: mm/cma.c) */

/* CMA 영역 선언 (Device Tree 또는 커널 파라미터) */
/* cma=256M  → 기본 CMA 영역 256MB 예약 */
/* cma=256M@0-4G  → 4GB 이내에서 256MB 예약 */

/* CMA 할당 API */
struct page *cma_alloc(struct cma *cma,
    size_t count,       /* 요청 페이지 수 */
    unsigned int align, /* 정렬 (order) */
    bool no_warn);

bool cma_release(struct cma *cma,
    const struct page *pages, unsigned int count);

/* 일반적인 사용: dma_alloc_coherent() 내부에서 CMA 호출 */
void *dma_alloc_coherent(struct device *dev,
    size_t size, dma_addr_t *dma_handle, gfp_t gfp);

/* CMA 동작 과정:
 * 1. CMA 영역에서 요청 크기의 연속 PFN 범위 찾기 (bitmap 검색)
 * 2. 해당 범위의 pageblock을 MIGRATE_ISOLATE로 변경
 * 3. 사용 중인 MOVABLE 페이지를 다른 영역으로 이주 (migrate_pages)
 * 4. 연속 free 영역 확보 → 호출자에게 반환
 */

# CMA 영역 확인
cat /proc/meminfo | grep Cma
# CmaTotal:        262144 kB   ← 예약된 CMA 영역
# CmaFree:         245760 kB   ← 현재 사용 가능 (MOVABLE로 사용 중일 수 있음)

# CMA 할당 디버깅
echo 1 > /sys/kernel/debug/tracing/events/cma/cma_alloc_start/enable
echo 1 > /sys/kernel/debug/tracing/events/cma/cma_alloc_finish/enable
cat /sys/kernel/debug/tracing/trace_pipe

# 커널 부트 파라미터로 CMA 크기 지정
# cma=256M          → 기본 CMA 256MB
# cma=0             → CMA 비활성화
# hugetlb_cma=1G    → CMA를 통한 huge page 할당

모니터링 (Monitoring)

buddyinfo

cat /proc/buddyinfo
# Node 0, zone      DMA      0      0      0      1      2      1      1      0      1      1      3
# Node 0, zone    DMA32   1029    537    243    108     34     12      3      1      0      1      1
# Node 0, zone   Normal  45321  12890   3210    823    211     52     13      3      1      0      0
#                         ^                                                            ^
#                     order 0 (4KB)                                              order 10 (4MB)
#
# 해석 방법:
# - 왼쪽(order 0)이 크면 정상 (소형 블록 충분)
# - 오른쪽(order 8~10)이 0이면 고차 할당 실패 가능 → 외부 단편화
# - 총 free 페이지 = sum(count[i] * 2^i)
#   예: Normal = 45321*1 + 12890*2 + 3210*4 + 823*8 + 211*16 + 52*32 + 13*64 + 3*128 + 1*256

pagetypeinfo

cat /proc/pagetypeinfo
# Free pages count per migrate type at order  0  1  2  3  4  5  6  7  8  9 10
# Node 0, zone   Normal, type    Unmovable  102 47 12  3  1  0  0  0  0  0  0
# Node 0, zone   Normal, type      Movable 4021 980 245 62 15  4  1  0  0  0  0
# Node 0, zone   Normal, type  Reclaimable  890 321  87 21  5  1  0  0  0  0  0
# Node 0, zone   Normal, type   HighAtomic   23   5   1  0  0  0  0  0  0  0  0
# Node 0, zone   Normal, type          CMA    0   0   0  0  0  0  0  0  0  0  0
# Node 0, zone   Normal, type      Isolate    0   0   0  0  0  0  0  0  0  0  0
#
# 핵심 분석:
# - Unmovable 고차 블록이 0이면 커널 할당에 단편화 영향
# - Movable에 고차 블록 존재 → compaction 불필요
# - HighAtomic이 비어 있으면 GFP_ATOMIC 할당 위험

vmstat 핵심 카운터

# 할당/해제 카운터
cat /proc/vmstat | grep -E "^(pgalloc|pgfree|pgactivate|pgdeactivate)"
# pgalloc_normal 12345678   ← ZONE_NORMAL에서 할당된 총 페이지 수
# pgfree 12340000            ← 해제된 총 페이지 수
# pgalloc - pgfree ≈ 현재 사용 중인 페이지 수

# Compaction 카운터
cat /proc/vmstat | grep compact
# compact_stall 45          ← direct compaction으로 인한 stall 횟수
# compact_fail 12           ← compaction 실패 횟수
# compact_success 33        ← 성공률: 33/(33+12) = 73%

# Reclaim 카운터
cat /proc/vmstat | grep -E "^(allocstall|pgscan|pgsteal)"
# allocstall_normal 89      ← ZONE_NORMAL에서 direct reclaim stall
# pgscan_kswapd 567890      ← kswapd가 스캔한 페이지 수
# pgsteal_kswapd 345678     ← kswapd가 회수한 페이지 수
# pgscan_direct 12340       ← direct reclaim 스캔 (높으면 문제)

# OOM 카운터
cat /proc/vmstat | grep oom
# oom_kill 0                ← OOM killer 발동 횟수 (0이 정상)

zoneinfo 상세 분석

# Zone 상세 정보 (Normal zone 예시)
cat /proc/zoneinfo | grep -A30 "zone   Normal"
# Node 0, zone   Normal
#   pages free     45321
#         boost    0          ← watermark_boost 현재 값
#         min      1440      ← WMARK_MIN
#         low      3600      ← WMARK_LOW
#         high     5760      ← WMARK_HIGH
#         spanned  4194304   ← zone이 포함하는 전체 PFN 범위
#         present  4128768   ← 실제 존재하는 페이지 수 (구멍 제외)
#         managed  3932160   ← Buddy가 관리하는 페이지 수
#         cma      65536     ← CMA 예약 페이지 수
#         protection: (0, 0, 0, 0)  ← lowmem_reserve
#   pagesets
#     cpu: 0
#       count: 47
#       high:  186
#       batch: 31
#       ...
#
# 건강 상태 판단:
# free > high → 정상
# low < free < high → kswapd 활동 중
# min < free < low → direct reclaim 가능
# free < min → 위험 (OOM 가능)

성능 최적화 (Performance)

Buddy Allocator의 성능은 크게 두 가지 요소에 좌우됩니다: (1) PCP 캐시 hit rate와 (2) Zone lock 경합 수준입니다. 대부분의 할당은 order 0이므로, PCP 최적화가 전체 성능에 가장 큰 영향을 미칩니다.

할당/해제 성능 비교

Per-CPU 페이지 캐시 (PCP)

/* mm/page_alloc.c */
struct per_cpu_pages {
    int  count;          /* 현재 캐시된 페이지 수 */
    int  high;           /* 고수위 (초과 시 batch만큼 반환) */
    int  batch;          /* Buddy로 한 번에 채우거나 반환할 크기 */
    struct list_head lists[MIGRATE_PCPTYPES]; /* Migrate Type별 리스트 */
};

/* order 0 할당: Per-CPU 캐시 → lock-free 경로 */
static struct page *rmqueue_pcplist(struct zone *preferred_zone,
    struct zone *zone, gfp_t gfp_flags,
    enum migratetype migratetype)
{
    struct per_cpu_pages *pcp;
    struct list_head *list;
    struct page *page;

    local_lock(&pagesets.lock);          /* CPU-local lock만 필요 */
    pcp = this_cpu_ptr(zone->per_cpu_pageset);
    list = &pcp->lists[migratetype];

    if (list_empty(list)) {
        /* 캐시 고갈 시 Buddy에서 batch 단위로 보충 */
        pcp->count += rmqueue_bulk(zone, 0, pcp->batch, list, migratetype);
    }
    page = list_first_entry(list, struct page, lru);
    list_del(&page->lru);
    pcp->count--;
    local_unlock(&pagesets.lock);
    return page;
}

단편화 문제 (Fragmentation)

Buddy Allocator의 가장 큰 적은 외부 단편화(external fragmentation)입니다. 전체 free 메모리는 충분하지만 연속된 큰 블록이 없어 고차 할당이 실패하는 현상입니다. 이는 시간이 지남에 따라 UNMOVABLE 페이지가 여기저기 박히면서 악화됩니다.

단편화 유형 비교

단편화 정도 측정

mm/vmstat.c의 단편화 지수(extfrag_index) 계산 방식입니다. 범위는 -1 ~ 1000입니다:

-1

할당 실패가 메모리 부족 때문입니다 (단편화 아님)

0

완벽한 연속 (단편화 없음)

500

extfrag_threshold 기본값 (compaction 트리거)

1000

극심한 단편화

계산 공식: free_blocks = order 이상의 총 free 블록 수, total_free = 전체 free 페이지 수, required = 1 << order로 하면, total_free < required일 때 -1(메모리 부족)을 반환하고, 그 외에는 index = 1000 - (1000 * free_blocks * required / total_free)로 계산합니다.

/sys/kernel/debug/extfrag/extfrag_index 출력 예:

Node 0, zone   Normal  -1 -1 -1 -1  0   0  512  750  890  950  980
                        ^              ^                          ^
                      order 0         order 4                  order 10
→ order 6 이상에서 단편화 시작, order 10은 심각

# 단편화 정도를 파악하는 종합 명령

# 1. 단편화 지수 (order별)
cat /sys/kernel/debug/extfrag/extfrag_index

# 2. 비정상적 단편화 경고 (unusual_extfrag)
cat /sys/kernel/debug/extfrag/unusable_index

# 3. compaction 효과 측정 (전후 비교)
cat /proc/buddyinfo > /tmp/before_compact
echo 1 > /proc/sys/vm/compact_memory
cat /proc/buddyinfo > /tmp/after_compact
diff /tmp/before_compact /tmp/after_compact

# 4. vmstat에서 compaction 관련 통계
cat /proc/vmstat | grep -E "compact|pgmigrate|allocstall"
# compact_stall: direct compaction 호출 횟수 (높으면 문제)
# compact_success: 성공률 확인
# compact_fail: 실패율 확인
# pgmigrate_success: 이동 성공 페이지 수
# pgmigrate_fail: 이동 실패 페이지 수
# allocstall_normal: ZONE_NORMAL direct reclaim stall 횟수

해결책 정리:

• 메모리 Compaction — MOVABLE 페이지를 이동하여 빈 공간 통합 (echo 1 > /proc/sys/vm/compact_memory)
• Anti-fragmentation — Migrate type별 분리 (Unmovable/Movable/Reclaimable pageblock)
• Huge Pages 사전 예약 — 부팅 시 hugepage를 미리 확보하여 런타임 고차 할당 회피
• CMA 영역 설정 — DMA용 연속 영역을 사전 예약하여 필요 시 보장
• min_free_kbytes 조정 — 여유 메모리 확보로 단편화 발생 가능성 감소
• watermark_scale_factor 증가 — kswapd가 더 일찍/적극적으로 회수

디버깅(Debugging) 및 진단 (Debugging)

단편화 상태 확인

# 1. Buddy Allocator 상태 확인
cat /proc/buddyinfo
# Node 0, zone   Normal  10   5   3   2   1   1   0   0   0   0   0
# → 큰 order(오른쪽)의 값이 0이면 외부 단편화 심각

# 2. Migrate Type별 블록 분포 확인
cat /proc/pagetypeinfo

# 3. Zone 워터마크 수준 확인
cat /proc/zoneinfo | grep -E "(zone|pages free|min|low|high)"

# 4. 외부 단편화 지수 (0=완벽, 1000=최악)
cat /sys/kernel/debug/extfrag/extfrag_index

# 5. 즉시 Compaction 강제 실행
echo 1 > /proc/sys/vm/compact_memory

할당 실패 추적 (ftrace)

# mm_page_alloc_extfrag: Migrate Type Fallback 발생 시 기록
echo 1 > /sys/kernel/debug/tracing/events/kmem/mm_page_alloc_extfrag/enable
cat /sys/kernel/debug/tracing/trace_pipe
# 출력 예: mm_page_alloc_extfrag: page=... alloc_order=2
#          alloc_migratetype=0 fallback_migratetype=1 change_ownership=1

# mm_page_alloc: 모든 페이지 할당 추적
echo 1 > /sys/kernel/debug/tracing/events/kmem/mm_page_alloc/enable

커널 트레이스포인트

/* include/trace/events/kmem.h */

/* 페이지 할당 성공 시 발생 */
TRACE_EVENT(mm_page_alloc,
    TP_PROTO(struct page *page, unsigned int order,
        gfp_t gfp_flags, enum migratetype migratetype),
    ...
);

/* Migrate Type Fallback 시 발생 → 단편화 악화 신호 */
TRACE_EVENT(mm_page_alloc_extfrag,
    TP_PROTO(struct page *page,
        int alloc_order, int fallback_order,
        int alloc_migratetype, int fallback_migratetype),
    ...
);

Buddy 단편화 대응 플레이북

Buddy allocator 장애의 핵심은 "총 메모리는 충분한데 고차 블록이 없는 상태"입니다. 따라서 free memory 총량보다 order별 가용량을 우선 분석해야 합니다.

진단 단계

1. 증상 확인: dmesg | grep -i "page allocation failure"로 할당 실패 확인
2. 고차 블록 확인: /proc/buddyinfo에서 order 8~10이 0인지 확인
3. Migrate Type 분포: /proc/pagetypeinfo에서 UNMOVABLE이 과다한지 확인
4. fallback 빈도 확인: mm_page_alloc_extfrag tracepoint로 steal 빈도 확인
5. 회수/압축 상태 확인: /proc/vmstat에서 compact_stall/success/fail 비율 점검
6. 요청 특성 조정: 큰 연속 물리 메모리 요청 경로(CMA, hugepage) 재검토

대응 조치 우선순위

# 종합 단편화 진단 스크립트
echo "=== 1. 할당 실패 이력 ==="
dmesg | grep -i "page allocation failure" | tail -5

echo "=== 2. buddyinfo (고차 블록 확인) ==="
cat /proc/buddyinfo

echo "=== 3. Migrate Type 분포 ==="
cat /proc/pagetypeinfo | head -n 30

echo "=== 4. 단편화 지수 ==="
cat /sys/kernel/debug/extfrag/extfrag_index 2>/dev/null || echo "(debugfs 미마운트)"

echo "=== 5. Compaction 통계 ==="
cat /proc/vmstat | grep -E "compact|allocstall"

echo "=== 6. 워터마크 상태 ==="
cat /proc/zoneinfo | grep -E "(^Node|zone |pages free|min |low |high )"

echo "=== 7. OOM 이력 ==="
dmesg | grep -i "oom" | tail -5

# order 2 이상 할당 추적 (실시간)
bpftrace -e 'tracepoint:kmem:mm_page_alloc /args->order >= 2/ {
  printf("pid=%d comm=%s order=%d gfp=0x%x\n",
    pid, comm, args->order, args->gfp_flags);
}'

# migrate type fallback 추적
bpftrace -e 'tracepoint:kmem:mm_page_alloc_extfrag {
  printf("order=%d alloc_mt=%d fallback_mt=%d\n",
    args->alloc_order, args->alloc_migratetype,
    args->fallback_migratetype);
}'

성능 최적화 가이드

Buddy Allocator의 성능은 대부분의 워크로드에서 충분히 빠르지만, 특정 시나리오에서는 튜닝이 필요합니다.

시나리오별 최적화

PCP 튜닝 상세

# 현재 PCP 상태 확인 (CPU별)
cat /proc/zoneinfo | grep -A5 "cpu:"
# cpu: 0
#   count: 47        ← 현재 캐시된 페이지
#   high:  186       ← 상한
#   batch: 31        ← 교환 단위

# PCP high를 Zone managed 페이지의 1/8로 설정
echo 8 > /proc/sys/vm/percpu_pagelist_high_fraction
# → high = managed_pages / 8 / num_online_cpus

# 기본 자동 조정으로 되돌리기
echo 0 > /proc/sys/vm/percpu_pagelist_high_fraction

# PCP 강제 비우기 (진단용)
# 커널 내부: drain_all_pages(NULL)
# 유저 공간에서 직접 접근 불가, CPU offline/online으로 간접 trigger

커널 빌드 관련 CONFIG 옵션

# PAGE_OWNER 활성화 시 페이지 할당 추적
# 부트 파라미터: page_owner=on
cat /sys/kernel/debug/page_owner | head -n 50
# Page allocated via order 0, mask 0x1100cca(GFP_HIGHUSER_MOVABLE|__GFP_ZERO)
#  PFN 262144 type Movable Block 512 type Movable
#  [page_owner_save_stack+0x38/0x60]
#  [post_alloc_hook+0x1c8/0x200]
#  [__alloc_pages+0x2d4/0x350]
#  ...

# 상위 할당자별 페이지 사용량 요약
cat /sys/kernel/debug/page_owner | sort | uniq -c | sort -rn | head -20

# __alloc_pages 호출 빈도 및 시간 측정
perf stat -e 'kmem:mm_page_alloc' -a sleep 10
# → 10초간 페이지 할당 횟수

# zone lock 경합 확인
perf lock record -a sleep 5
perf lock report

sysctl/proc 레퍼런스

Buddy Allocator 관련 주요 sysctl 매개변수와 /proc 파일을 종합적으로 정리합니다.

# Buddy Allocator 상태 종합 진단 스크립트
echo "=== buddyinfo ==="
cat /proc/buddyinfo

echo "=== Zone Watermarks ==="
cat /proc/zoneinfo | grep -E "(^Node|zone |pages free|min |low |high |managed)"

echo "=== VM Statistics (allocation) ==="
cat /proc/vmstat | grep -E "(pgalloc|pgfree|pgsteal|compact|allocstall)"

echo "=== CMA ==="
grep Cma /proc/meminfo

echo "=== PCP per zone ==="
cat /proc/zoneinfo | grep -A3 "cpu:" | head -n 40

echo "=== Key sysctl values ==="
sysctl vm.min_free_kbytes vm.watermark_scale_factor vm.watermark_boost_factor

커널 소스 분석 (Kernel Source Analysis)

이 섹션은 Buddy Allocator의 핵심 함수들을 소스 코드 수준에서 분석합니다. 호출 체인(Call Chain)인 alloc_pages() → get_page_from_freelist() → __alloc_pages_slowpath()의 흐름과 함께 핵심 자료구조인 struct zone, struct free_area의 각 필드를 상세히 설명합니다.

struct zone 필드별 분석

struct zone은 Buddy Allocator의 메모리 영역 기본 단위입니다. include/linux/mmzone.h에 정의되며, 워터마크·잠금·통계·PCP·free_area 등 Zone 관리에 필요한 모든 정보를 담습니다.

/* include/linux/mmzone.h - struct zone 주요 필드 */
struct zone {
    /* ── 워터마크 (Watermark) ─────────────────────── */
    unsigned long _watermark[NR_WMARK]; /* [0]=MIN [1]=LOW [2]=HIGH */
    unsigned long watermark_boost;      /* 외부 단편화 시 동적으로 올린 추가 수위 */
    unsigned long nr_reserved_highatomic;/* MIGRATE_HIGHATOMIC 예약 페이지 수 */

    /* ── Lowmem 예약 ──────────────────────────────── */
    long lowmem_reserve[MAX_NR_ZONES];  /* 상위 zone 요청으로부터 보호할 페이지 수 */

    /* ── NUMA 노드 참조 ──────────────────────────── */
    int node;                            /* 이 Zone이 속한 NUMA 노드 번호 */
    struct pglist_data *zone_pgdat;     /* 소속 node descriptor (pglist_data) */

    /* ── Per-CPU 페이지 캐시 ─────────────────────── */
    struct per_cpu_pages __percpu *per_cpu_pageset; /* CPU별 order-0 캐시 (lock-free 경로) */
    struct per_cpu_zonestat __percpu *per_cpu_zonestats; /* CPU별 통계 카운터 */
    int pageset_high;                    /* PCP 배치 임계값(high watermark) */
    int pageset_batch;                   /* PCP 일괄 보충/반환 단위 크기 */

    /* ── Buddy Free List ─────────────────────────── */
    struct free_area free_area[MAX_ORDER]; /* order 0~10 버디 프리 리스트 배열 */

    /* ── Zone 잠금 ───────────────────────────────── */
    spinlock_t lock;                     /* free_area 접근 보호 스핀락 */

    /* ── 페이지 수 통계 ──────────────────────────── */
    unsigned long zone_start_pfn;       /* Zone 시작 PFN(Page Frame Number) */
    atomic_long_t managed_pages;        /* Buddy가 실제 관리하는 페이지 수 */
    unsigned long spanned_pages;        /* hole 포함 전체 PFN 범위 */
    unsigned long present_pages;        /* 실제 존재하는 페이지 수 */

    /* ── Zone 이름 ───────────────────────────────── */
    const char   *name;                 /* "DMA", "DMA32", "Normal", ... */

    /* ── 컴팩션 관련 ─────────────────────────────── */
    unsigned long compact_cached_free_pfn; /* 마지막 컴팩션 free 스캔 위치 */
    unsigned long compact_cached_migrate_pfn[2]; /* 마이그레이션 스캔 위치 [sync/async] */
    unsigned int  compact_considered;   /* 컴팩션 대기/쿨다운 카운터 */
} ____cacheline_internodealigned_in_smp;

struct free_area 필드별 분석

struct free_area는 특정 order의 버디 블록 집합을 나타냅니다. Migrate Type별로 분리된 이중 연결 리스트(Doubly Linked List)와 전체 블록 수 카운터로 구성됩니다.

/* include/linux/mmzone.h */
struct free_area {
    struct list_head free_list[MIGRATE_TYPES]; /* Migrate Type별 버디 블록 리스트 */
    unsigned long    nr_free;                  /* 이 order의 총 free 블록 수 (모든 타입 합산) */
};

호출 체인 심층 분석: alloc_pages → get_page_from_freelist

실제 커널 소스에서 alloc_pages()는 매크로/인라인 래퍼로 시작하여 __alloc_pages() → get_page_from_freelist() → rmqueue() → __rmqueue() 순으로 내려갑니다. 아래는 각 함수의 핵심 로직과 설계 의도를 분석합니다.

/* include/linux/gfp.h - alloc_pages() 진입점 */
static inline struct page *alloc_pages(gfp_t gfp_mask, unsigned int order)
{
    return alloc_pages_node(numa_node_id(), gfp_mask, order);
}

/* alloc_pages_node() → __alloc_pages() 로 연결 */
static inline struct page *alloc_pages_node(int nid,
    gfp_t gfp_mask, unsigned int order)
{
    if (unlikely(order >= MAX_ORDER))   /* order ≥ 11이면 즉시 실패 */
        return NULL;
    return __alloc_pages(gfp_mask, order, nid, NULL);
}

/* mm/page_alloc.c - __alloc_pages() 핵심 흐름 */
struct page *__alloc_pages(gfp_t gfp, unsigned int order,
    int preferred_nid, nodemask_t *nodemask)
{
    struct page *page;
    unsigned int alloc_flags = ALLOC_WMARK_LOW;
    struct alloc_context ac = {
        .order          = order,
        .gfp_mask       = gfp,
        .preferred_nid  = preferred_nid,
        .nodemask       = nodemask,
    };

    prepare_alloc_pages(gfp, order, preferred_nid,  /* ac 초기화: zonelist, migratetype 결정 */
                        nodemask, &ac, &alloc_flags);

    /* ① Fast path: WMARK_LOW 기준으로 즉시 시도 */
    page = get_page_from_freelist(gfp, order, alloc_flags, &ac);
    if (likely(page))
        goto out;

    /* ② Slow path: 회수·압축·OOM을 동반한 재시도 */
    gfp = current_gfp_context(gfp);   /* 태스크 컨텍스트에 따른 GFP 보정 */
    page = __alloc_pages_slowpath(gfp, order, &ac);
out:
    trace_mm_page_alloc(page, order, gfp, ac.migratetype);
    return page;
}

__rmqueue()와 __free_one_page() 내부 구현

__rmqueue()는 특정 Zone의 Buddy Free List에서 요청된 order의 블록을 꺼냅니다. 요청 order의 블록이 없으면 더 큰 블록을 split하여 사용합니다. __free_one_page()는 반대로 페이지를 반환하면서 인접한 버디와 coalesce를 반복합니다.

/* mm/page_alloc.c - __rmqueue() 핵심 로직 */
static __always_inline struct page *
__rmqueue(struct zone *zone, unsigned int order,
          int migratetype, unsigned int alloc_flags)
{
    struct page *page;

    /* ① 먼저 요청한 migratetype의 free list에서 시도 */
    page = __rmqueue_smallest(zone, order, migratetype);
    if (unlikely(!page)) {
        /* ② 실패 시 CMA 영역에서 폴백 (GFP_MOVABLE이면) */
        if (migratetype_is_movable(migratetype) &&
            cma_page_list_available(zone, order))
            page = __rmqueue_cma_fallback(zone, order);

        /* ③ 여전히 실패 시 다른 migratetype에서 스틸(steal) */
        if (!page)
            page = __rmqueue_fallback(zone, order, migratetype,
                                        alloc_flags);
    }
    trace_mm_page_alloc_zone_locked(page, order, migratetype);
    return page;
}

/* __rmqueue_smallest(): 가장 작은 적합 블록을 split하며 할당 */
static inline 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_ORDER-1까지 올라가며 빈 블록 탐색 */
    for (current_order = order; current_order < MAX_ORDER; current_order++) {
        area = &zone->free_area[current_order];
        page = get_page_from_free_area(area, migratetype); /* list 첫 항목 꺼냄 */
        if (!page)
            continue;
        del_page_from_free_list(page, zone, current_order); /* 리스트에서 제거, nr_free 감소 */
        expand(zone, page, order, current_order, migratetype); /* 나머지 조각을 하위 order에 삽입 */
        set_pcppage_migratetype(page, migratetype);
        return page;
    }
    return NULL;
}

/* mm/page_alloc.c - __free_one_page(): 버디 coalesce 핵심 */
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;
    struct page *buddy;

    while (order < MAX_ORDER - 1) {
        /* ① 버디 PFN 계산: XOR로 같은 order 내 버디 위치 결정 */
        buddy_pfn = __find_buddy_pfn(pfn, order); /* pfn ^ (1 << order) */
        buddy = page + (buddy_pfn - pfn);

        /* ② 버디가 free 상태이고 같은 order인지 확인 */
        if (!page_is_buddy(page, buddy, order))
            break;                              /* 합체 불가 → 루프 종료 */

        /* ③ 버디를 프리 리스트에서 제거 */
        del_page_from_free_list(buddy, zone, order);

        /* ④ 결합: 낮은 PFN이 새 블록의 시작 */
        combined_pfn = buddy_pfn & pfn;         /* AND로 정렬된 상위 블록 시작 PFN */
        page = page + (combined_pfn - pfn);
        pfn  = combined_pfn;
        order++;                                /* 한 단계 위 order로 합체 */
    }

    /* ⑤ 최종 블록을 적절한 프리 리스트에 삽입 */
    add_to_free_list(page, zone, order, migratetype);
    set_buddy_order(page, order);               /* page->private = order, PG_buddy 설정 */
}

__alloc_pages_slowpath() 내부 단계별 분석

Slow Path는 Fast Path가 실패한 후 단계적으로 메모리를 확보합니다. 각 단계에서 성공하면 즉시 반환하며, GFP 플래그에 따라 일부 단계를 건너뜁니다.

/* mm/page_alloc.c - __alloc_pages_slowpath() 주요 단계 (단순화) */
static struct page *
__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
                       struct alloc_context *ac)
{
    struct page *page = NULL;
    unsigned int alloc_flags;
    enum compact_priority compact_priority = DEF_COMPACT_PRIORITY;
    enum compact_result compact_result;
    int compaction_retries = 0;
    int no_progress_loops = 0;
    unsigned long did_some_progress;

    /* ① ALLOC_HARDER: 예약 풀(MIGRATE_HIGHATOMIC) 접근 여부 결정 */
    alloc_flags = gfp_to_alloc_flags(gfp_mask, order);

    /* ② kswapd 깨우기: 비동기 메모리 회수 시작 */
    wake_all_kswapds(order, gfp_mask, ac);

    /* ③ WMARK_MIN으로 낮춰서 재시도 (GFP_ATOMIC이면 HIGHATOMIC 풀 허용) */
    page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
    if (page)
        goto got_pg;

    /* ④ 차단 불가 컨텍스트(GFP_ATOMIC)에서는 여기서 중단 */
    if (!can_direct_reclaim())
        goto nopage;

    /* ⑤ 직접 Compaction → 재할당 반복 루프 */
    for (;;) {
        page = __alloc_pages_direct_compact(gfp_mask, order,
                   alloc_flags, ac, compact_priority, &compact_result);
        if (page)
            goto got_pg;

        /* ⑥ 직접 메모리 회수(Direct Reclaim) → 재할당 */
        page = __alloc_pages_direct_reclaim(gfp_mask, order,
                   alloc_flags, ac, &did_some_progress);
        if (page)
            goto got_pg;

        /* ⑦ 진행 없이 반복 횟수 초과 → OOM 또는 포기 */
        if (should_reclaim_retry(gfp_mask, order, ac,
                alloc_flags, did_some_progress > 0,
                &no_progress_loops))
            continue;

        if (should_compact_retry(ac, order, alloc_flags,
                compact_result, &compact_priority,
                &compaction_retries))
            continue;

        /* ⑧ OOM Killer 호출 (최후 수단) */
        page = __alloc_pages_may_oom(gfp_mask, order, ac,
                   &did_some_progress);
        if (page)
            goto got_pg;

        if (!(gfp_mask & __GFP_NOFAIL))
            goto nopage;           /* NOFAIL이 아니면 NULL 반환 */
        /* __GFP_NOFAIL: schedule() 후 처음부터 재시도 (무한 루프) */
        cond_resched();
    }

got_pg:
    return page;
nopage:
    warn_alloc(gfp_mask, ac->nodemask, /* WARN_ON + OOM 정보 출력 */
               "page allocation failure: order:%u", order);
    return NULL;
}

커널 소스 및 참고 자료

주요 소스 파일

외부 참고 자료

• Kernel Documentation: Memory Management (admin-guide)
• Kernel Documentation: Memory Allocation Guide
• Kernel Documentation: Page Allocator
• LWN: Anti-fragmentation (Mel Gorman, 2006)
• LWN: Memory Compaction (Mel Gorman, 2010)
• LWN: Folio pages (Matthew Wilcox, 2021)
• LWN: CMA (Contiguous Memory Allocator)
• Mel Gorman, Understanding the Linux Virtual Memory Manager (kernel.org)
• LWN: A memory zone for device memory (2005) — ZONE_DEVICE 개념의 초기 논의
• LWN: CMA and compaction (2016) — CMA와 메모리 압축의 상호작용
• LWN: Page allocation performance (2023) — 페이지 할당 성능 최적화
• mmap(2) — 메모리 매핑을 통한 페이지 할당 인터페이스
• mm/page_alloc.c (Bootlin) — Buddy allocator 핵심 소스
• include/linux/gfp.h (Bootlin) — GFP 플래그 정의 헤더

관련 문서

• 메모리 관리(Memory Management) 개요 — 물리 메모리 계층 개요
• Slab Allocator — 2차 할당자 (소형 객체 캐싱)
• Memory Compaction — 외부 단편화 해결
• NUMA — Node 기반 할당 전략
• Huge Pages — 대형 페이지 사전 예약
• CMA (연속 메모리 할당자(Memory Allocator)) — DMA용 연속 메모리
• OOM Killer — 메모리 고갈 대응
• Page Fault — 가상 주소 → 물리 페이지 매핑
• Page Cache — 파일 시스템 페이지 캐싱
• vmalloc — 가상 연속 메모리 할당
• 메모리 관리 개요 — 고급 메모리 주제
• MMU & TLB — 주소 변환(Address Translation)과 TLB 관리