Memory Allocation Mechanism

< Structure of the Buddy System >

struct zone {
 
    ...
 
    struct free_list[MAX_ORDER];
 
    // buddy 를 위한 order 별 free page 들의 list
 
    ...
 
}

node 내의 각 zone 을 struct zone 통해 관리하며 struct zone 마다 order 별 할당가능한 free page 를 관리하는 struct free_list 를 가지고 있다. 

 

struct free_area {
 
    struct list_head    free_list[MIGRATE_TYPES];
 
    // free page 를 page block type 별로 묶기 위해 
 
    // migrate type 별로 free page block 을 연결한 것
 
    // migrate type 단위 page block 관리를 통해 MOVABLE, NON_MOVABLE 을
 
    // 분리하여 user domain 의 page 와 kernel domain 의 page 를 따로 관리하기 위함
 
    // 하지만 각 domain 의 page block 부족시 다른 domain 으로 fall back 가능
 
    // fall back order : MIGRATE_UNMOVABLE -> MIGRATE_RECLAIMABLE -> MIGRATE_MOVABLE
 
    //                   MIGRATE_MOVABLE -> MIGRATE_RECLAIMABLE -> MIGRATE_UNMOVABLE
 
    unsigned long       nr_free;
 
    // 현재 order 의 모든 page type 들의 free page 의 수
    // ...
 
};

struct free_area 는 연속적인 page 들을 page block 별로 free_list 를 통해 관리하며 nr_free 를 통해 각 order 에 현재 몇개의 page block 이 사용가능한지 나타낸다. order 에 해당하는 free 한 연속적 물리 memory 공간이 연결되고 node 의 각 zone 마다 free_list 를 가지고 있으며 현재 zone 에서 page 할당이 불가능 할 시, struct pglist_data 의 node_zonelist 이름의 struct zoneref 에 설정된 ZONELIST_FALLBACK 또는 ZONELIST_NOFALLBACK 에 따라 각각 다른 node 에서 free page 를 할당받을 수 있다.

// performance 이유로 각 node 는 node 별 CPU 에 해당하는 local node 에 memory 를 
// 할당하려 하지만 local 에 할당이 실패할 경우를 대비하여 memory allocation 을 위한 
// alternative node 의 list 를 가진다.
// zonelist  배열에서 뒷 entry 일수록 할당 우선순위가 낮음  
 
// UMA 의 경우.. fallback list 의 초기화 결과
//  NODE : A, B, C (A->B->C)
//  ZONE : ZONE_HIGHMEM-2, ZONE_NORMAL-1, ZONE_DMA-0
//   위와 같다고할 때... 
 
//  node A 의 fallback list 할당 상태는...   
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[0] = A2
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[1] = A1
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[2] = A0
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[3] = B2
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[4] = B1
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[5] = B0
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[6] = C2
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[7] = C1
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[8] = C0
 
 
// NUMA 의 경우 ... 
//  node A 의 할당 순서가 C,B,D 라고 할때...
//      1
//   A ---- C
// 2 |      | 2
//   |      |
//   B ---- D
//      1
//                        |         32bit        |         64bit        |
//                        -----------------------------------------------
// current_zonelist_order | ZONELIST_ORDER_ZONE  |  ZONELIST_ORDER_NODE |
 
// < 32 bit 는... default 로 ZONELIST_ORDER_ZONE 
// 
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[0]  = A HIGHMEM
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[1]  = C HIGHMEM
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[2]  = B HIGHMEM
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[3]  = D HIGHMEM 
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[4]  = A NORMAL
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[5]  = C NORMAL
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[6]  = B NORMAL
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[7]  = D NORMAL
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[8]  = A DMA
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[9]  = C DMA
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[10] = B DMA
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[11] = D DMA
//      node_zonelist[ZONELIST_NOFALLBACK]->_zonerefs[0] = A HIGHMEM
//      node_zonelist[ZONELIST_NOFALLBACK]->_zonerefs[1] = A NORMAL
//      node_zonelist[ZONELIST_NOFALLBACK]->_zonerefs[2] = A DMA
 
 
// < 64 bit 는... default 로 ZONELIST_ORDER_NODE >
//
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[0]  = A NORMAL
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[1]  = A DMA
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[2]  = C NORMAL
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[3]  = C DMA
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[4]  = B NORMAL
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[5]  = B DMA
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[6]  = D NORMAL
//      node_zonelist[ZONELIST_FALLBACK]->_zonerefs[7]  = D DMA 
//      node_zonelist[ZONELIST_NOFALLBACK]->_zonerefs[0] = A NORMAL
//      node_zonelist[ZONELIST_NOFALLBACK]->_zonerefs[1] = A DMA
 
typedef struct pglist_data {
 
    struct zone node_zones[MAX_NR_ZONES];
 
    // 현재 node 에서 각 zone 에 해당하는 zone struct 배열 
    // DMA,DMA32,NORMAL,HIGHMEM,(MOVABLE)
 
    struct zonelist node_zonelists[MAX_ZONELISTS];
 
    // 두가지 zonelist 를 가지고 있음
    // 1. fallback 상황을 위해 다른 node 에 할당하기 위한 zonelist 
    //    현재 zone 에 memory 가 할당 불가능 할 때, 다른 node 에 memory 를 할당하기 위한
    //    우선순위 node list 이며 그 각 node 에 해당하는 zone 정보도 가지고 있음(fallback order) 
    // 2. fallback 이 없는 zonelist  
    //    현재 node 내에서의 zone type 별 fallback list
 
    int nr_zones;
 
    // 현재 node 가 가진 zone 의 수
 
    ...
 
}
 
 
 
struct zonelist {
 
    struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1]; 
    // +1 은 list 의 end 를 위한 null pointer
 
};  
 
 
 
struct zonelist {
 
    struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1]; 
    // +1 은 list 의 end 를 위한 null pointer
 
};  
 
```

< Avoiding Fragmentation >

kernel 은 fragmentation 을 피하기 위해 defragmentation, anti-fragmentation 의 방법을 사용한다. defragmentation 은 kcompactd 같은 kernel thread 에 의해 migrate scanner, free scanner 가 각각 memory 영역의 bottom, top 영역에서 부터 scan 을 수행해 page 를 migration 해줌으로써 연속적인 영역을 확보하는 것이고, anti-fragmentation 은 page 가 user domain 의 page, kernel domain 의 page 가 있기 때문에 kernel domain 의 page 의 경우엔 위치가 고정되어 migration 을 수행할 수 없으므로 애초에 user domain 의 page, kernel domain 의 page 를 각각 따로 관리하는 것이다. 즉. defragmentation 은 fragmentation 이 일어났을 때의 치료라고 볼 수 있고, anti-fragmentation 은 fragmentation 을 미연에 방지하기 위한 예방이라고 볼 수 있다. 

enum {
 
    MIGRATE_UNMOVABLE,
    // memory 내에서 위치가 변경될 수 없고, 회수도 불가능한 page block
    // kernel domain page 들 중 core 부분의 page 에 속함. 
 
    MIGRATE_MOVABLE,
    // memory 내에서 위치 변경 가능 및 회수 가능한 page
    // user application 에 의해 할당된 page table 을 통해 mapping 되는 page block
    // page table 내의 mapping 정보 변경을 통해 위치가 변경 될 수 있음
 
    MIGRATE_RECLAIMABLE,
    // memory 내에서 이동이 불가능하지만, kswapd 등에 의해 page 회수가 가능한 page block
 
    MIGRATE_PCPTYPES,   /* the number of types on the pcp lists */
    // per-CPU cache 가 가진 migrate type 까지를 나타내기 위한 기준점
 
    MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
    // MIGRATE_RESERVE 가 삭제되고 추가된 것으로 high-order atomic allocation 을 위한 
    // page 들을 예약해둠(최대 전체 zone 의 1%)
 
#ifdef CONFIG_CMA
 
    MIGRATE_CMA,
    // 연속적 물리 memory 를 할당하는 CMA allocator 에 의해 관리되는 page block
 
#endif
 
#ifdef CONFIG_MEMORY_ISOLATION
 
    MIGRATE_ISOLATE,    /* can't allocate from here */
    // memory 회수 등의 작업이 진행되는 동안  기존 page list 에서 일단 
    // 분리시켜 놓기 위한 virtual page type
 
#endif
    MIGRATE_TYPES
 
};  

page 는 종류에 따라 나뉠 수있는데, page table, slab cache 등의 고정된 위치의 migration 이 될 수 없는 kernel page 들은 MIGRATE_UNMOVABLE 에 속하고, page table 을 통해 mapping 되어 단순 기존 page 의 내용을 복사하고, pte 의 mapping 정보를 바꾸어 줌으로써 migration 가능한 user page 는 MIGRATE_MOVABLE 에 속한다. 이외에도 CMA 할당자에서 사용하는 MIGRATE_CMA,  kcompactd 에 의해 migration 수행하는 작업 등 LRU 에서 page 를 분리해야 할 필요가 있을 시, 사용하기위한 MIGRATE_ISOLATE , 지금은 MIGRATE_UNMOVABLE 처럼 migration 될 수 없지만 page 회수 후 가능 한 MIGRATE_RECLAIMABLE 등이 있다. 

// 각 MIGRATETYPE 별 해당 free list 에서 page 를 얻을 수 없을 시, 
// 다른 MIGRATETYPE 에서 받아오게 되는 순서(fallback list)
 
static int fallbacks[MIGRATE_TYPES][4] = {
 
    [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
    [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
    [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
#ifdef CONFIG_CMA
    [MIGRATE_CMA]         = { MIGRATE_TYPES }, /* Never used */
 
#endif
 
#ifdef CONFIG_MEMORY_ISOLATION
    [MIGRATE_ISOLATE]     = { MIGRATE_TYPES }, /* Never used */
 
#endif
 
};

stuct zone 내에 각 migration type 별로 free list 를 가지며 할당하려는 page block type 에 order 를 만족하는 page 가 없을 때, 다른 migration type 에 속한 page block 으로부터 page 를 받아오게 되며(fallback) 위와 같은 fallbacks 에 명시된 순서로 각 migrate type 에 따라 다른 순서로 fallback 이 진행된다. 

#ifdef CONFIG_HUGETLB_PAGE
#ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE
 
/* Huge page sizes are variable */
extern unsigned int pageblock_order;
#else /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
#define pageblock_order     HUGETLB_PAGE_ORDER
 
// page block order 
#endif /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */
 
#else /* CONFIG_HUGETLB_PAGE */
 
/* If huge pages are not used, group by MAX_ORDER_NR_PAGES */
 
#define pageblock_order     (MAX_ORDER-1)
 
// page block order
 
#endif /* CONFIG_HUGETLB_PAGE */
 
#define pageblock_nr_pages  (1UL <<pageblock_order)

migration type 에 속한 하나의 page block 크기는 pageblock_order 와 같은 크기로 즉 order 9 이므로 base page 512 개로 구성된다.(2MB)  

#define ___GFP_MOVABLE      0x08u 
// movable type 의 free_list 에 할당 요청
 
#define ___GFP_RECLAIMABLE  0x10u 
// reclaimable type 의 free list 에 할당 요청 
 
#define __GFP_MOVABLE   ((__force gfp_t)___GFP_MOVABLE) 
#define __GFP_RECLAIMABLE ((__force gfp_t)___GFP_RECLAIMABLE)

kernel 은 memory allocation 시에 gfp lag 에 설정된 allocation mask 를 통해 free page 를 할당받아야 할 때 어느 migration type 의 free list 에 할당 요청을 할지 구분하게 되며. __GFP_MOVABLE , __GFP_RECLAIMABLE 을 통해 migrate type 을 알 수 있다.(gfp 란 get free page 의 약자이다.)

 

// memory 할당 요청이 어느 migration type 에 해당되어야 하는지 확인
static inline int gfpflags_to_migratetype(const gfp_t gfp_flags)
 
{
 
    VM_WARN_ON((gfp_flags &GFP_MOVABLE_MASK) == GFP_MOVABLE_MASK);
    BUILD_BUG_ON((1UL <<GFP_MOVABLE_SHIFT) != ___GFP_MOVABLE);
    BUILD_BUG_ON((___GFP_MOVABLE >>GFP_MOVABLE_SHIFT) != MIGRATE_MOVABLE);
 
 
 
    if (unlikely(page_group_by_mobility_disabled))
 
        return MIGRATE_UNMOVABLE;
    // mobility grouping 을 지원안할 시, 모든 free page 들을 MIGRATE_UNMOVABLE 의 
    // free list 를 통해 하나로 관리되기 때문에 MIGRATE_UNMOVABLE 반환
 
    /* Group based on mobility */
    return (gfp_flags &GFP_MOVABLE_MASK) >>GFP_MOVABLE_SHIFT;
    // MOVABLE 또는 RECLAIMABLE 인지 검사
}

gfpflags_to_migratetype 함수에서 통해 현재의 gfp flag 에 어느 migrate type 에서 free page 를 구하라고 설정해 놓았는지 구할 수 있다.. __GFP_MOVABLE 일 경우 MIGRATE_MOVABLE, __GFP_RECLAIMABLE 일 경우MIGRATE_RECLAIMABLE 로 인지하며 둘다 설정되어 있지 않다면 MIGRATE_UNMOVABLE 로 인식한다.

 

struct zone {
 
     // ...
 
     unsigned long       *pageblock_flags;
 
     // ...
 
}

struct zone   은 pageblock_nr_page 크기의 page block 들의 migrate type 을 관리하기 위해 pageblock_flags 필드를 가지고 있으며 zone 을 구성하는 migration type 별 page block 들의 상태가 pageblock_flags 에 kernel initialization 시에 구성된다. 또한 ZONE_DMA , ZONE_NORMAL , ZONE_HIGHMEM 등 외에도 fragmentation 을 방지하기 위한 anti-fragmentation 기법으로 user 가 설정할 수 있는 ZONE_MOVABLE 이 있는데 설정해 놓을 시, virtual zone 인 ZONE_MOVABLE 을 지정하여 하나의 zone 내에 MIGRATE_MOVABLE page 만 모아 관리 할 수 있도록 virtual zone 을 구성할 수 있으며,  highest physical zone 에서 page 를 받아 ZONE_MOVABLE 을 구성한다. 즉 ZONE_MOVABLE 은 현재 물리 zone 들중 가장 상위 zone 부터 구성된다.

 

< Initializing the Zone and Node Data Structure >

 

// arch/x86/mm/init_64.c
void __init paging_init(void)
 
{
 
    sparse_memory_present_with_active_regions(MAX_NUMNODES);
    sparse_init();
 
    /*
     * clear the default setting with node 0
     * note: don't use nodes_clear here, that is really clearing when
     *   numa support is not compiled in, and later node_set_state
     *   will not set it back.
     */
 
    node_clear_state(0, N_MEMORY);
 
    if (N_MEMORY != N_NORMAL_MEMORY)
        node_clear_state(0, N_NORMAL_MEMORY);
 
    zone_sizes_init(); 
    // 각 zone 의 page frame 경계설정 및 free page list 구성 등 수행
 
}
 
 
 
// arch/x86/mm/init.c
void __init zone_sizes_init(void)
{
    unsigned long max_zone_pfns[MAX_NR_ZONES];
 
    memset(max_zone_pfns, 0, sizeof(max_zone_pfns));
 
#ifdef CONFIG_ZONE_DMA
    max_zone_pfns[ZONE_DMA]     = min(MAX_DMA_PFN, max_low_pfn);
    // ZONE_DMA 경계 page frame 설정 
    //  - max_low_pfn 은 setup_arch 에서 초기화된 end-of-memory
 
#endif
 
#ifdef CONFIG_ZONE_DMA32
    max_zone_pfns[ZONE_DMA32]   = min(MAX_DMA32_PFN, max_low_pfn);
    // ZONE_DMA32 경계 page frame 설정
 
#endif
    max_zone_pfns[ZONE_NORMAL]  = max_low_pfn;
    // ZONE_NORMAL 경계 page frame 설정
 
#ifdef CONFIG_HIGHMEM
    max_zone_pfns[ZONE_HIGHMEM] = max_pfn;  
 
#endif
 
    free_area_init_nodes(max_zone_pfns);
    // zone 과 pglist_dat 초기화 (node, zone 초기화)
 
}   

kernel 이 booting 될 때, 각 page frame 들의 어디부터 어디까지가 각 zone 에 해당하는지, node 는 어느 page frame 까지 해당하는지 초기화 수행된다. kernel 이 초기화 되는 start_kernel 함수에서 호출되는 paging_init 함수에서 각 zone 의 경계설정하는 함수인 zone_size_init 함수가 호출되며 이를 통해 ZONE_DMA , ZONE_DMA32 , ZONE_NORMAL , ZONE_HIGHMEM 들 중 현재 설정된 ZONE 들에 대한 경계 page frame 을 설정한다.

책에서 나온 node 별 page frame 분배 관련 필드인 early_node_map 는 bootmem 이 아닌 memblock 이 사용되며 [patch](https://patchwork.kernel.org/patch/1043952) 되어 없어진 것으로 보인다. 각 zone 의 boundary 정보를 초기화 한 후, struct zone 과 struct pglist_data 구조체를 초기화하기 위해(node, zone 정보를 초기화 수행) free_area_init_nodes 함수가 수행된다. 

static unsigned long __meminitdata arch_zone_lowest_possible_pfn[MAX_NR_ZONES];
// zone 마다의 시작 page frame number
 
static unsigned long __meminitdata arch_zone_highest_possible_pfn[MAX_NR_ZONES];
// zone 마다의 끝 page frame number
 
static unsigned long __meminitdata zone_movable_pfn[MAX_NUMNODES];
// node 마다의 ZONE_MOVABLE 시작 page frame

 

먼저 kernel 에는 각 zone 들의 시작 page frame number 를 의미하는 arch_zone_lowest_possible_pfn , 각 zone 들의 끝 page frame number 를 의미하는 arch_zone_highest_possible_pfn , movable zone 이 있을 시 movable zone 의 시작 page frame number 를 의미하는 zone_movable_pfn 정보를 전역 변수로 가지고 있으며, free_area_init_nodes 함수를 통해 node, zone 관련 정보를 초기화 해준다. 

 

// node, zone 관련 구조체 초기화 함수 
//  - max_zone_pfn : 각 zone 의 배열로 구성된 zoen 별 page  frame 끝 number
void __init free_area_init_nodes(unsigned long *max_zone_pfn)
{
 
    unsigned long start_pfn, end_pfn;
    int i, nid;
   
    /* Record where the zone boundaries are */
    memset(arch_zone_lowest_possible_pfn, 0,
                sizeof(arch_zone_lowest_possible_pfn));
    memset(arch_zone_highest_possible_pfn, 0,
                sizeof(arch_zone_highest_possible_pfn));
 
    // zone 별로 arch_zone_lowest_possible_pfn, arch_zone_highest_possible_pfn 
    // 전역 변수를 두어 각 zone 의 start ~ end page frame 을 나타냄
    start_pfn = find_min_pfn_with_active_regions();
 
    // node 에서의 첫 page frame 
    for (i = 0; i <MAX_NR_ZONES; i++) {
        if (i == ZONE_MOVABLE)
            continue;
 
        end_pfn = max(max_zone_pfn[i], start_pfn);
        arch_zone_lowest_possible_pfn[i] = start_pfn;
        arch_zone_highest_possible_pfn[i] = end_pfn;
        start_pfn = end_pfn;
 
    }   
 
    // zone 별 start page frame, end page frame 초기화 
    /* Find the PFNs that ZONE_MOVABLE begins at in each node */
    memset(zone_movable_pfn, 0, sizeof(zone_movable_pfn));
 
    find_zone_movable_pfns_for_nodes();
    // ZONE_MOVABLE 의 start page frame 를 NODE 만큼 구성된 ZONE_MOVABLE 의
    // 배열에 초기화 즉 node 별 ZONE_MOVABLE 의 시작 page frame 구하고 각 node 별 
    // page frame 영역 정해줌
    /* Print out the zone ranges */
 
    pr_info("Zone ranges:\n");
 
    for (i = 0; i <MAX_NR_ZONES; i++) {
 
        if (i == ZONE_MOVABLE)
            continue;
 
        pr_info("  %-8s ", zone_names[i]);
 
        if (arch_zone_lowest_possible_pfn[i] ==
                arch_zone_highest_possible_pfn[i])
            pr_cont("empty\n");
        else
            pr_cont("[mem %#018Lx-%#018Lx]\n",
                (u64)arch_zone_lowest_possible_pfn[i]
                    <<PAGE_SHIFT,
                ((u64)arch_zone_highest_possible_pfn[i]
                    <<PAGE_SHIFT) - 1);
    }
 
 
 
    /* Print out the PFNs ZONE_MOVABLE begins at in each node */
    pr_info("Movable zone start for each node\n");
 
    for (i = 0; i <MAX_NUMNODES; i++) {
        if (zone_movable_pfn[i])
            pr_info("  Node %d: %#018Lx\n", i,
                   (u64)zone_movable_pfn[i] <<PAGE_SHIFT);
 
    }
 
    /* Print out the early node map */
 
    pr_info("Early memory node ranges\n");
    for_each_mem_pfn_range(i, MAX_NUMNODES, &start_pfn, &end_pfn, &nid)
        pr_info("  node %3d: [mem %#018Lx-%#018Lx]\n", nid,
            (u64)start_pfn <<PAGE_SHIFT,
            ((u64)end_pfn <<PAGE_SHIFT) - 1);
 
    /* Initialise every node */
 
    mminit_verify_pageflags_layout();
    setup_nr_node_ids();
    // 전역변수 nr_node_ids 에 node 개수정보 기록
 
    for_each_online_node(nid) {
 
        pg_data_t *pgdat = NODE_DATA(nid);
        free_area_init_node(nid, NULL,
                find_min_pfn_for_node(nid), NULL);
 
        // node 별 struct 초기화함수
        // find_min_pfn_for_node 그 node 의 사용가능 최소 page frame
 
        /* Any memory on that node */
        if (pgdat->node_present_pages)
            node_set_state(nid, N_MEMORY);
        // node 의 상태를 나타내는 배욜인 nodemask_t node_states[NR_NODE_STATES] 의
        // 현재 NODE 에 N_MEMORY 즉 N_HIGH_MEMORY (같은 번호) 를 마킹하여 현재 node 에
        // page 가 있음 즉 normal or high memory 가 있음을 나타냄 
        check_for_memory(pgdat, nid);
 
    }
 
}

책에서 나온 sort_node_map() 함수는 위와 같은 [patch](https://patchwork.kernel.org/patch/1043952/) 로 없어진 것으로 생각되어 pass 하고 kernel 내부의 sort 가있다는 것만 알고 해당 부분은 넘어간다.(책에나온 kernel 이 lib/sort.c 위치에 heap sort implementation 을 제공하며 sort 라는 함수를 통해 사용하면 됨, 이외에도 alignment 검사 함수, swap 함수등 제공하고 sort 함수는 xfs, btrfs, perf tool 등등에서 사용되는 것으로 확인)  

free_area_init_nodes 함수에서는 각 node 의 시작과 끝 page frame number 를 의미하는 arch_zone_lowest_possible_pfn 과 arch_zone_highest_possible_pfn 을 각각 처음에 0으로 초기화 후, find_min_pfn_with_active_regions 함수를 통해 가장 작은 page frame number 를 가져와 각 zone 의 최소, 최대 page frame number 정보를 초기화 해주며 ZONE_MOVABLE 영역의 page frame 을 설정해 주기 위해 find_zone_movable_pfn_for_nodes 함수에서 현재 설정되어 있는 kernel parameter 등을 확인하여 movable zone page frame 을 현재 node 의 zone_movable_pfn 에 설정한다. 그 후, 초기화한 정보를 출력하고 node 의 struct pglsit_data , struct zone 정보를 free_area_init_node 함수를 통해 마저 초기화 해준다. 

 

unsigned long __init find_min_pfn_with_active_regions(void)
 
{   
    return find_min_pfn_for_node(MAX_NUMNODES);
}   
 
 
 
/* Find the lowest pfn for a node */
static unsigned long __init find_min_pfn_for_node(int nid)
 
{
    unsigned long min_pfn = ULONG_MAX;
    unsigned long start_pfn;
    int i;
 
    for_each_mem_pfn_range(i, nid, &start_pfn, NULL, NULL)
        min_pfn = min(min_pfn, start_pfn);
    // nid 까지의 node 들 에서의 각 page frame 중 최소값을 구함
    // MAX_NUMNODES 로 nid 가 설정 된 경우에는, 모든 node 들의 
    // start page frame 중 최소값을 가져옴 
 
    if (min_pfn == ULONG_MAX) {
        pr_warn("Could not find start_pfn for node %d\n", nid);
 
        return 0;
    }
 
    return min_pfn;
 
}

find_min_pfn_for_node 함수를 통해 초소 page frame 번호를 구함. 

 

 
static void __init find_zone_movable_pfns_for_nodes(void)
 
{
 
    int i, nid; 
    unsigned long usable_startpfn;
    unsigned long kernelcore_node, kernelcore_remaining;
 
    /* save the state before borrow the nodemask */
    nodemask_t saved_node_state = node_states[N_MEMORY];
    // node_states 즉 현재 node 에 movable zone 이 있는지, highmem zone 
    // 까지 있는지, memory 자체가 없는지 등의 상태를 나타냄 
 
    unsigned long totalpages = early_calculate_totalpages();
    // 모든 node 의 전체 page frame 수를 가져옴
 
    int usable_nodes = nodes_weight(node_states[N_MEMORY]);
    // N_MEMORY 까지 있는지 즉, ZONE_NORMAL or ZONE_HIGHMEM 까지 있는지 검사 
    // node 의 상태별 전체 node 의 정보를 나타내는 bitmap 인 nodemask_t 배열에 대해
    // N_MEMORY state 에 대한 index  에 해당하는 bitmap  에 bit 설정된 node 가 몇개인지 
    // 가져옴
    struct memblock_region *r;
 
 
 
    /* Need to find movable_zone earlier when movable_node is specified. */
    find_usable_zone_for_movable(); 
 
    // memory 를 가진 마지막 ZONE 의 index 를  movable_zone 아리는 전역 변수에 설정
    /*
     * If movable_node is specified, ignore kernelcore and movablecore
     * options.
     */
 
    if (movable_node_is_enabled()) {
        // kernel 옵션 CONFIG_MOVABLE_NODE 설정을 통해 movable_node_enabled 
        // 가 설정되어 있는지 검사 
 
        for_each_memblock(memory, r) {
            // memblock 전체를 scan
            if (!memblock_is_hotpluggable(r))
                continue;
            // memblock 영역의 hotplug 설정이 없다면 넘어감
 
            nid = r->nid;
 
            usable_startpfn = PFN_DOWN(r->base);
            zone_movable_pfn[nid] = zone_movable_pfn[nid] ?
                min(usable_startpfn, zone_movable_pfn[nid]) :
                usable_startpfn;
            // hotplugging 기능 설정된 경우, 시작 page frame 을 
            // zone_movable_pfn 에 저장
        }
 
        goto out2;
    }
 
    /*
     * If kernelcore=mirror is specified, ignore movablecore option
     */
 
    if (mirrored_kernelcore) {
 
        // v4.6 에 추가 address range memory mirroring 기법이 사용되는 지 검사
        // 즉 kernel parameter 로 "kernelcore=mirror" 가 설정되어 있을경우에 
        // 해당하며, ZONE_MOVABLE 영역은 mirroring 이 수행되지 않고, ZONE_NORMAL 등의 일반 
        // 영역은 mirroring 이 수행되도록 함.
 
        bool mem_below_4gb_not_mirrored = false;
 
        for_each_memblock(memory, r) {
 
            if (memblock_is_mirror(r))
                continue;
 
            // memblock 에서 mirror 가 설정되어 있는 부분 즉 ZONE_MOVABLE 에
            // 해당되는 부분이면 넘어감     
 
            nid = r->nid;
 
            usable_startpfn = memblock_region_memory_base_pfn(r);
            // mirror 가 설정되어 있지 않은 부분 즉 ZONE_MOVABLE 에 해당되어야 할
            // 부분이라면 해당 memblock 의 base address 를 pf 단위 올림하여
 
            if (usable_startpfn <0x100000) {
                // 1G 보다 아래에 있는 memblock 에 대해 ZONE_MOVABLE 속성이 
                // 설정될 거라면... pass
 
                mem_below_4gb_not_mirrored = true;
 
                continue;
            }
 
            zone_movable_pfn[nid] = zone_movable_pfn[nid] ?
                min(usable_startpfn, zone_movable_pfn[nid]) :
                usable_startpfn;
                // ZONE_MOVABLE 시작 page frame 설정
        }
 
 
 
        if (mem_below_4gb_not_mirrored)
            pr_warn("This configuration results in unmirrored kernel memory.");
 
        goto out2;
 
    }
 
 
 
    /*
     * If movablecore=nn[KMG] was specified, calculate what size of
     * kernelcore that corresponds so that memory usable for
     * any allocation type is evenly spread. If both kernelcore
     * and movablecore are specified, then the value of kernelcore
     * will be used for required_kernelcore if it's greater than
     * what movablecore would have allowed.
     */
 
    if (required_movablecore) {
        // kernel parameter 로 movablecore 옵션이 사용된 경우
        unsigned long corepages;
 
        /*
         * Round-up so that ZONE_MOVABLE is at least as large as what
         * was requested by the user
         */
 
        // e.g. totalpages : 10 , MAX_ORDER_NR_PAGES : 2  
        //        - 여기서 toal page 는 가용 모든 node 의 total paage
        //      required_kernelcor  : 7
        //      required_movablecore : 1
        required_movablecore =
            roundup(required_movablecore, MAX_ORDER_NR_PAGES);
        // kernmel paramter 로 ZONE_MOVABLE 에 할당할 page 갯수를 1024 단위 올림  
        //
        // e.g. totalpages : 10 , MAX_ORDER_NR_PAGES : 2
        //      required_movablecore : 4 
        //      required_kernelcore  : 1
        //
 
        required_movablecore = min(totalpages, required_movablecore);
        // e.g. totalpages : 10 , MAX_ORDER_NR_PAGES : 2
        //      required_movablecore : 4
       //      required_kernelcore  : 1
 
        corepages = totalpages - required_movablecore;
        // 전체 page frame 개수에서 요청된 movable page 빼고 얼마나?
        // e.g. totalpages : 10 , MAX_ORDER_NR_PAGES : 2
        //      required_movablecore : 4
        //      corepages : 6 
        //      required_kernelcore  : 6
 
        required_kernelcore = max(required_kernelcore, corepages);
    }
 
 
 
    /*
     * If kernelcore was not specified or kernelcore size is larger
     * than totalpages, there is no ZONE_MOVABLE.
     */
 
    if (!required_kernelcore || required_kernelcore >= totalpages)
        goto out;
 
 
 
    /* usable_startpfn is the lowest possible pfn ZONE_MOVABLE can be at */
    usable_startpfn = arch_zone_lowest_possible_pfn[movable_zone];
    // 일단 ZONE_MOVABLE 이 속해야 될 마지막 ZONE 에 대한 index 인 movable_zone 을 통해
    // ZONE_MOVABLE 이 될 수 있는 첫 page frame 을 가져옴
 
restart:
 
    /* Spread kernelcore memory as evenly as possible throughout nodes */
    kernelcore_node = required_kernelcore / usable_nodes;
    // 모든 node 의 kernel memory page 가 될 page 들의 합인 required_kernelcore 에서 
    // 현재 memory 가 있는 가용 node 인 usable_nodes 값을 나누어 kernel memory page 를 
    // node 별로 몇개씩 분배하면 좋을지 결정 
 
    // ...
 
}

find_zone_movable_pfns_for_nodes 함수를 통해 모든 node 들의 전체 paage frame 의 수를 가져와 totalpages 에 저장하고, 가용 memory 가 있는 node 의 수를 usable_nodes 에 넣는다. 그 후 ZONE_MOVABLE 의 영역을 설정하기 위해 즉 ZONE_MOVABLE 의 시작 page frame 을 결정하기 위한 작업 시작하며 먼저 2가지 경우의 수에 대하여 거른다. 

find_usable_zone_for_movable 함수를 통해 usable memory 를 가진 마지막 ZONE 의 index 를 movable_zone 이라는 전역 변수에 저장한 후, 첫번 째 거르는 조건으로 CONFIG_MOVABLE_NODE 라는 옵션을 통해 하나의 노드에 그냥 ZONE_MOVABLE 다 때력박는 옵션이 있는 검사한다. 옵션설정이 되어 있고 memory hot plugging 의 설정이 없다면 kernel memory 로 주어야 하므로(kernel memory 마음대로 껏다 켰다 하면안되서 그러듯), 넘어가고 아니면 ZONE_MOVABLE 의 시작 page frame 을 설정한다. 그 다음 거르는 조건으로 address range memory mirroring 기능이 설정되있는지 검사한다. [Address Range Memory Mirroring](https://www.fujitsu.com/jp/documents/products/software/os/linux/catalog/LinuxConJapan2016-Izumi.pdf) 은 user memory error 의 경우 단순히 process 를 종료해 버리면 되지만  kernel code execution 도중 발생 할 수 있는 error 는 전체 system 의 crash 를 유발할 수 있기 때문에 이에 대한 recovery path 를 제공하기 위해 kernel data write 시 mirroring 하는 기법으로 kernel v4.6 부터 address range mirroring 으로 도입된 kernel fault recovery path system 이다. 전체 memory 영역에 대해(user memory page, kernel memory page) 모두 mirroring 을 수행하는 것은 memory 소모량이 큰 단점이 있을 수 있으므로, kernel memory page 에 대하여만 mirroring 을 수행하며, 이를 위한 기법으로 기존의 ZONE_MOVABLE 을 사용한다. ZONE_MOVABLE 은 kernel boot parameter option 으로 "kernelcore=크기" 또는 "movablecore=크기" 옵션을 주어 생성한 ZONE_MOVABLE 에 user memory page 만 할당하며, ZONE_MOVABLE 이 아닌 기존의 ZONE 들에 kernel memory page 를 할당하게 된다. 이를 활용하여 "kernelcore=mirror" 를 kernel parameter 로 주어, non-mirrored memory range 를 ZONE_MOVABLE 영역에 놓아 kernel memory 에 대한 mirroring 만 독립적으로 수행이 될 수있도록 하는 기법이다. 따라서 mirror 가 설정되어 있다면 kernel memory page 로 사용해야 하므로 넘어가고 아니라면, ZONE_MOVABLE 의 start page frame 을 기록한다. 

두가지 거르는 조건 검사를 통과하게 되면 kernel parameter 로 ZONE_NORMAL 의 크기 or  ZONE_MOVABLE 이 아닌 부분의 크기가 미리 설정되어 있다면, 둘의 합이 전체 space 보다 작을 경우, kernel 이 사용 할 수 있도록 해주고, 전체 kernel memory page 를 가용 memory 가 있는 node 의 개수로 나누어 ZONE_MOVABLE 에 해당하지 않는 page 가 잘 분배되도록 한다. 

이하 생략.

 

// 각 noge, zone 의 data structure 를 초기화 
void __paginginit free_area_init_node(int nid, unsigned long *zones_size,
 
        unsigned long node_start_pfn, unsigned long *zholes_size)
 
{
    pg_data_t *pgdat = NODE_DATA(nid);
    unsigned long start_pfn = 0;
    unsigned long end_pfn = 0;
 
    /* pg_data_t should be reset to zero when it's allocated */
    WARN_ON(pgdat->nr_zones || pgdat->kswapd_classzone_idx);
    // node id, 시작 page frame , cpu set 등 초기화 수행
 
    reset_deferred_meminit(pgdat);
    pgdat->node_id = nid;
    pgdat->node_start_pfn = node_start_pfn;
    pgdat->per_cpu_nodestats = NULL;
 
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
 
    // node 의 start page frame number, end page frame number 가져옴
    get_pfn_range_for_nid(nid, &start_pfn, &end_pfn);
    pr_info("Initmem setup node %d [mem %#018Lx-%#018Lx]\n", nid,
        (u64)start_pfn <<PAGE_SHIFT,
        end_pfn ? ((u64)end_pfn <<PAGE_SHIFT) - 1 : 0);
 
#else
 
    start_pfn = node_start_pfn;
 
#endif
 
    // spanned 영역을 고려하여 각 zone 의 page 개수 계산
    calculate_node_totalpages(pgdat, start_pfn, end_pfn,
                  zones_size, zholes_size);
    // 각 node 의 zone 으로부터 정보를 읽어들여 node 의 spanned pages, 
    // real total pages 를 계산하여 node 에 채움
    alloc_node_mem_map(pgdat);
 
#ifdef CONFIG_FLAT_NODE_MEM_MAP
 
    printk(KERN_DEBUG "free_area_init_node: node %d, pgdat %08lx, node_mem_map %08lx\n",
        nid, (unsigned long)pgdat,
        (unsigned long)pgdat->node_mem_map);
 
#endif
 
    // struct zone, struct pglist_data 초기화
    free_area_init_core(pgdat);
 
}

free_area_init_node 함수를 통해 위의 free_area_init_nodes 에서 설정한 page frame 경계들을 기반으로 각 node 의 struct zone , struct pglist_data 를 초기화 수행. struct pglist_data 에 node id, node 의 시작 page frame, cpu set 등을 초기화 하고 get_pfn_range_for_nid 함수에서 현재 node 의 start page frame, end page frame 을 가져오며, calculate_node_tatalpages 함수를 통해 각 struct zone 에 존재할 수있는 hole page 들을 포함한 전체 page 의 수인 spanned_page , hole page 들을 제외한 page 들 의수인 present_pages 등의 정보를 초기화 해준다. alloc_node_mem_map 함수를 통해 node 내의 page frame 개수만큼 page descriptor 들인 struct page 들을 초기화 해주며, free_area_init_core 함수를 통해 struct pglist_data 의 hugepage split queue ( split_queue ), numa balancing 정보, wait queue 들(swapper thread 의 wait queue 인 kswapd_wait , page allocation 을 대기중인 task 의 wait queue 인 pfmemalloc_wait ...) 초기화, init_currently_empty_zone 함수를 통해 zone 의 migrate type 별 free_area 초기화, set_pageblock_order 함수에서 통해 zone 별 per-CPU cache 인 per_cpu_pageset 초기화, 각 zone 별 reserved page frame( struct page 배열을 위한 page frame, dma 를 위한 page frame)을 제외한 free page frame 정보 초기화 및 memmap_init 함수에서 zone 에 해당하는 struct page 초기화 등의 작업을 수행해 준다. 

 

< Allocator API >

buddy 에 의하여 2^n 단위의 page 가 할당되고 더 작은 단위의 할당은 slab 에 의해 할당되며 page 를 할당/해제하는 API 는 아래와 같은 것들이 있다.

• alloc_page, get_zeroed_page, __get_free_page, __get_dma_pages, page_cache_alloc, page_cache_alloc_cold

• free_page, __free_page, free_pages ...

 

page 할당 API 들은 모두 __alloc_pages_nodemask 함수를 호출하게 되고, page 해제 API들은 모두 free_pages 를 호출하게 된다. 또한 buddy system function 기반이지만 buddy system 에는 속하지 않는 할당 함수로 vmalloc 도 있으며 연속되지 않은 물리 메모리 공간을 연속적인 kernel virtual address 에 mapping 하여 관리하기 위해 사용된다. 또한 kmalloc 을 통해 기본 page size 보다 작은 크기에 대해 할당을 해줄 수도 있다. 

page 를 할당 받을 때, 물리 memory 에서 할당 받을 page frame 의 위치 및 종류에 대한 정보(ZONE, MIGRATE type)들 과 page 할당 요청이 어떻게 처리되어야 할지에 대한 정보(page 할당에 대한 정보 즉 할당 요청중 선점 가능한지... zeroed page 가 필요한건지... 현재 node ) 나타내기 위해 gfp(get free pages 의 약자.) 등을 나타내기 위해 gfp flag 가 사용된다.  

#define ___GFP_DMA      0x01u 
// ZONE_DMA 영역에 할당 요청함
#define ___GFP_HIGHMEM      0x02u 
// ZONE_HIGHMEM 영역에 할당 요청함
#define ___GFP_DMA32        0x04u 
// ZONE_DMA32 영역에 할당 요청함
#define ___GFP_MOVABLE      0x08u 
// ZONE_MOVABLE 이 이용가능하다면 이 영역에 할당 요청한다
// page migration 가능하도록 할당 요청
#define ___GFP_RECLAIMABLE  0x10u 
// 회수 가능한 page 로 할당 요청 
// ...

할당 위치 및 종류를 나타내는 기본 gfp flag 들은 위와 같은 것들이 있다.

#define ___GFP_DMA      0x01u 
// ZONE_DMA 영역에 할당 요청함
#define ___GFP_HIGHMEM      0x02u 
// ZONE_HIGHMEM 영역에 할당 요청함
#define ___GFP_DMA32        0x04u 
// ZONE_DMA32 영역에 할당 요청함
#define ___GFP_MOVABLE      0x08u 
// MOVABLE page block 의 free_list 에서 할당 요청
#define ___GFP_RECLAIMABLE  0x10u 
// RECLAIMABLE page block 의 free_list 에서 할당 요청
#define ___GFP_HIGH     0x20u
// 현재 page 요청이 되게 중요함(우선순위 높음)
// 이거 안되면 system crash 날지도 모름
#define ___GFP_IO       0x40u
// page 요청 중, I/O 가능 e.g. swap 가능
#define ___GFP_FS       0x80u
// VFS 연산 가능
#define ___GFP_COLD     0x100u 
// CPU cache 에 있지 않은 cold page 가 필요함
#define ___GFP_NOWARN       0x200u 
// page 할당 실패해도 warning 띄우지 않음
#define ___GFP_REPEAT       0x400u 
// 실패시 몇번 더 할당 시도해보다 말음
#define ___GFP_NOFAIL       0x800u
// 실패시 성공할 때 까지 계속 시도
#define ___GFP_NORETRY      0x1000u 
// 실패시 재시도 안함
#define ___GFP_MEMALLOC     0x2000u 
// 비상 예약 영역을 사용하여 할당해도 되도록 허용 
// 즉 모든 memory 영역 사용 허용
#define ___GFP_COMP     0x4000u
// 연속된 compound page 로 할당해야 한다. e.g. THP
#define ___GFP_ZERO     0x8000u
// 0 으로 초기화된 page 필요함
#define ___GFP_NOMEMALLOC   0x10000u
// 비상 예약 영역에서 할당을 못하도록함
#define ___GFP_HARDWALL     0x20000u 
// process 가 assign 된 CPU 에 해당하는 NODE 
// 에서만 page 할당 가능
#define ___GFP_THISNODE     0x40000u 
// 지정된 node 에서만 할당 허용 즉 fal back 안됨
#define ___GFP_ATOMIC       0x80000u 
// page 요청을 page 회수, sleep 등 허용안되고 
// 높은 우선순위로 처리한다.
#define ___GFP_ACCOUNT      0x100000u 
// kmemcg 의 통제 안받고 page 할당되도록 허용
// (memory control group)
#define ___GFP_NOTRACK      0x200000u 
// kmemcheck 를 통한 디버그 트래킹 허용 안함.
#define ___GFP_DIRECT_RECLAIM   0x400000u 
// page 요청시 실패할 경우, direct reclaim 하여 
// 할당 요청시 바로 free page 확보해주고 현재 요청 처리한다. 
#define ___GFP_WRITE        0x800000u
// dirty page 할당 요청 
#define ___GFP_KSWAPD_RECLAIM   0x1000000u 
// page 할당 시, WMARK_LOW 에 접근하는 경우 kswapd 를 깨워 WMARK_HIGH 에 
// 도달할 때 까지 page 회수하도록 함. 
// ...

또한 page 요청 시, 어떻게 동작할 것인지 제한 또는 설정하는 기본 gfp flag 등에는 위와 같은 것들이 있다. 

#define GFP_ATOMIC  (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM) 
// 메모리가 있으면 할당, 없으면 NULL, 휴면불가능
#define GFP_KERNEL  (__GFP_RECLAIM | __GFP_IO | __GFP_FS) 
// kernel memory 를 위한 page 를 할당한다.
// page 요청이 실패하게 되면 kswapd 또는 kcompactd 에 의해 page 를 확보하며 
// page 할당 도중 IO 수행 및 VFS 관련 call 호출이 가능하다.
#define GFP_KERNEL_ACCOUNT (GFP_KERNEL | __GFP_ACCOUNT)
#define GFP_NOWAIT  (__GFP_KSWAPD_RECLAIM)
#define GFP_NOIO    (__GFP_RECLAIM)
#define GFP_NOFS    (__GFP_RECLAIM | __GFP_IO)
#define GFP_TEMPORARY   (__GFP_RECLAIM | __GFP_IO | __GFP_FS | \
             __GFP_RECLAIMABLE)
#define GFP_USER    (__GFP_RECLAIM | __GFP_IO | __GFP_FS | __GFP_HARDWALL)
// user memory 를 위한 page 를 할당한다.
// process 가 assign 된 CPU 에 해당하는 cpuset 정책이 사용될 수 있도록 한다. 
#define GFP_DMA     __GFP_DMA 
// ZONE_DMA 영역에서 page 를 할당하낟. 
#define GFP_DMA32   __GFP_DMA32
// ZONE_DMA32 에서 page 를 할당한다. 
#define GFP_HIGHUSER    (GFP_USER | __GFP_HIGHMEM)
// ZONE_HIGHMEM 영역에서 user memory 를 위한 page 를 할당한다. 
#define GFP_HIGHUSER_MOVABLE    (GFP_HIGHUSER | __GFP_MOVABLE) 
// ZONE_HIGHMEM 영역의 MIGRATE_MOVABLE 에서 user memory 를 위한 page 를 할당한다. 
#define GFP_TRANSHUGE_LIGHT ((GFP_HIGHUSER_MOVABLE | __GFP_COMP | \
             __GFP_NOMEMALLOC | __GFP_NOWARN) &~__GFP_RECLAIM)
// THP 관련되어 page fault 과정에 설정되는 flag
// 비상용도로 예약된 영역은 사옹하지 못하도록 하여 ZONE_HIGHMEM 의 
// ZONE_MOVABLE 에서 compound huge page 를 할당하며, huge page 할당 실패하면 
// 그냥 base page 할당하면 되기 때문에 할당이 실패해도 경고를 띄우지 않으고 
// kswapd 또는 kcompactd 에 의한 memory compaction 을 수행하지 않도록 page 할당을 수행한다. 
#define GFP_TRANSHUGE   (GFP_TRANSHUGE_LIGHT | __GFP_DIRECT_RECLAIM) 
// khugepaged 에 의해 base page 가 THP 로 promote 될 때 설정되는 flag
// THP 할당이 실패하게 되면 CPU stall 하고 kcompactd 에 의해 연속적 memory 공간 확보 후, 
// THP 를 할당을 수행한다.
// ...

특정상황에 사용할 수 있도록 위의 기본 gfp flag 들을 조합하여 위와같은 특정 gfp flag set 들을 만들어 놓아 사용하며 이외에도 다양한 GFP flag 들이 있다. 

 

< 3.5.5 Reserving Pages >

buddy allocator 의 핵심 함수인 alloc_pages_nodemask 를 통해 page 를 할당 할 때 page 할당에 대한 경계값 정보인 watermark 는 WMARK_MIN, WMARK_LOW, WMARK_HIGH 가 있다. 

/* The ALLOC_WMARK bits are used as an index to zone->watermark */
#define ALLOC_WMARK_MIN     WMARK_MIN 
// zone->watermark[0] 사용
#define ALLOC_WMARK_LOW     WMARK_LOW
// zone->watermark[1] 사용
#define ALLOC_WMARK_HIGH    WMARK_HIGH
// zone->watermark[2] 사용
#define ALLOC_NO_WATERMARKS 0x04 /* don't check watermarks at all */
/* Mask to get the watermark bits */
#define ALLOC_WMARK_MASK    (ALLOC_NO_WATERMARKS-1)
#define ALLOC_HARDER        0x10 /* try to alloc harder */ 
// 할당 watermark 의 기준값에 대한 rule 
// 이값 설정시, WMARK_MIN 값을 기존 min의 1/4 감소
#define ALLOC_HIGH      0x20 /* __GFP_HIGH set */
// 할당 watermark 의 기준값에 대한 rule 
// 이값 설정시, WMARK_MIN 값을 기존 min의 1/2 감소
#define ALLOC_CPUSET        0x40 /* check for correct cpuset */ 
// memory 를 cpuset 설정된 CPU 에 달린 영역에서 가져와야됨
// 즉 cgroup 의 cpu subsystem 에서 설정한 정책 사용
#define ALLOC_CMA       0x80 /* allow allocations from CMA areas */
// memory 를 CMA 영역에서 가져와야 한다. 

위와 같은 water mark flag 등을 통해 struct zone->watermark 라는 배열에서 현재 page 요청에 대한 가능여부 판단 또는 할당 후 처리 등을 수행 할 때, 어느 watermark 를 사용할 것인지 정할 수 있으며 default 값은 WMARK_HIGH 이다. 현재 free page 의 수가 WMARK_LOW 보다 낮아지게 되면 kswapd 가 깨어나 비동기적으로 clean unmapped cache 관련 page 를 회수하며 WMARK_MIN 보다 낮아지게 되면 page 를 할당하기 위해 동기적으로 page reclaim, swap 등을 수행한다. kswapd kernel thread 는 free page 의 상태가 WMARK_HIGH 에 도달하게 될 때 까지 계속 비동기적으로 수행되고 도달하게 되면 다시 sleep 된다. order 에 해당하는 page 요청이 이러한 경계 기준값을 벗어나는지 판단하기 위해 zone_watermark_ok 를 사용한다. 

struct alloc_context {
    struct zonelist *zonelist;
    // page 할당 실패시 다음 free_area 를 찾을 fallback list 
    nodemask_t *nodemask;
    // gfp 값과 mempolicy 에 의해 설정된 nodemask 로 
    // page 할당 가능한 node
    struct zoneref *preferred_zoneref;
    // fast path 를 위해 사용?  
    int migratetype;
    // page 를 받아올 migrate type
    enum zone_type high_zoneidx;
    // 할당 요청이 들어온 ZONE
    bool spread_dirty_pages;
    // gfp flag 에 __GFP_WRITE 설정 되었는지 여부
    // write 용 file page cache 할당 요청인지
}; 

struct alloc_context 는 __alloc_pages_nodemask 에서 page 를 할당 받기 위해 내부적으로 사용하는 자료구조이다.

 
// buddy allocator 핵심 함수로 page 를 할당하는 함수
struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
            struct zonelist *zonelist, nodemask_t *nodemask)
{
    struct page *page;
    unsigned int alloc_flags = ALLOC_WMARK_LOW;
    gfp_t alloc_mask = gfp_mask; /* The gfp_t that was actually used for allocation */
    struct alloc_context ac = { };
 
    gfp_mask &= gfp_allowed_mask;
    // gfp flag 에서 허용되는 flag bit 만 가져온다. 
    // (__GFP_RECLAIM, __GFP_IO, __GFP_FS 제거)  
    if (!prepare_alloc_pages(gfp_mask, order, zonelist, nodemask, &ac, &alloc_mask, &alloc_flags))
        return NULL;
    // alloc_context 초기화, fauult injection 검사 
 
    finalise_ac(gfp_mask, order, &ac);
    // alloc_context 마저 초기화(dirty page 할당받을지, 현재 zone 을 preferred zone 으로 설정)
 
    /* First allocation attempt */
    page = get_page_from_freelist(alloc_mask, order, alloc_flags, &ac);
    // page 할당 시도
 
    if (likely(page))
        goto out;
 
    // fast path 로 할당 성공하면 out. 
    //  - fastpath : 
    //    1. watermark 를 검사하여 넘는지 안넘는지 검사
    //       필요시 node reclaim 하고 다시 watermark 검사 
    //    2. buddy 및 per-CPU cache 로부터 요청 migrate type에 할당 시도
    //    3. 자신의 migrate type 에서 할당 실패하게 되면 
    //       fallback 으로 다른 type 에 할당 시도    
    //
    // 위의 memory 할당 시도가 실패한다면 연속적 가용 memory 가 없으므로 여기부터 slowpath 로 동작
 
    /*
     * Runtime PM, block IO and its error handling path can deadlock
     * because I/O on the device might not complete.
     */
 
    alloc_mask = memalloc_noio_flags(gfp_mask);
    ac.spread_dirty_pages = false;
 
    /*
     * Restore the original nodemask if it was potentially replaced with
     * &cpuset_current_mems_allowed to optimize the fast-path attempt.
     */
 
    if (unlikely(ac.nodemask != nodemask))
        ac.nodemask = nodemask;
 
    page = __alloc_pages_slowpath(alloc_mask, order, &ac);
 
    // ...
 
}

__alloc_pages_nodemask 함수는 page 를 할당받는 핵심 함수로 gfp_mask, order 요청에 맞는 page 를 지정된 nodemask 내의 free_list 로부터, zonelist 의 fallback 의 순서에 따라 fallback 되어 할당한다. 

• prepare_alloc_pages 함수와 finalise_ac 함수를 통해 page 할당 함수 내부적으로 사용할 struct alloc_context 를 초기화 및 page 할당 전초과정을 수행하고

• get_page_from_freelist 함수를 통해 zone fallback list 들을 순회하며 할당하려는 page 의 order 에 맞는 개수의 page 를 할당하려 시도한다.

• __alloc_pages_slowpath 함수에서는 get_page_from_freelist 함수를 통해 page 를 할당받을 수 없을 경우(watermark 보다 남은 free page 의 수가 적거나, buddy 로부터 연속적인 order 개수의 page를 할당 받을 수 없는 등의 경우 등), kswapd 또는 kcompactd 등을 통해 synchronous 하게 free page 를 확보 한 후, page 할당이 다시 수행되게 된다. 

// struct alloc_context 의 초기화 수행
 
static inline bool prepare_alloc_pages(gfp_t gfp_mask, unsigned int order,
        struct zonelist *zonelist, nodemask_t *nodemask,
        struct alloc_context *ac, gfp_t *alloc_mask,
        unsigned int *alloc_flags)
{       
    ac->high_zoneidx = gfp_zone(gfp_mask);
    // 할당 요청 들어온 ZONE
    ac->zonelist = zonelist;
    // zone falback list
    ac->nodemask = nodemask;
    // mempolicy nodemask
 
    ac->migratetype = gfpflags_to_migratetype(gfp_mask);
    // 할당 받을 page type
 
    if (cpusets_enabled()) {
        // page allocation 과정 내부에서 사용될 alloc_context 구조체 초기화
 
        *alloc_mask |= __GFP_HARDWALL; 
        // assign 된 CPU 관련 memory 에서만 할당가능 하도록 gfp flag 추가
 
        if (!ac->nodemask)
            ac->nodemask = &cpuset_current_mems_allowed;
        // 따로 설정된 mempolicy nodemask 가 없다면.. 
        else
            *alloc_flags |= ALLOC_CPUSET;
        // allocation rule 설정
    }   
 
    lockdep_trace_alloc(gfp_mask);
    might_sleep_if(gfp_mask &__GFP_DIRECT_RECLAIM);
    // swap, kcompactd 등에 의해 free page 확보하고 수행 가능되기 위해
    // mightsleep 설정
 
    if (should_fail_alloc_page(gfp_mask, order))
        return false;
    // page 할당이 실패할 조건 검사 
    // order 가 1일 때.. __GFP_NOFAIL 설정되어 있을 때 등등..
    // fault injection 검사
 
    if (IS_ENABLED(CONFIG_CMA) &&ac->migratetype == MIGRATE_MOVABLE)
        *alloc_flags |= ALLOC_CMA;
    // CMA 가 설정되어 있고, 현재MIGRATE_MOVABLE 이라면 추후 migrate fallback
    // 을 통한 page 요청 시, MOVABLE 이라면 CMA 에서 받아 올 수 있도록 설정
 
    return true;
 
}   

prepare_alloc_pages 에서는 page 할당 요청하기 전 내부에서 사용될 구조체 초기화 및 page 할당 전의 전초 과정 및 초기화 등을 수행한다.  

• 먼저 page 할당에 사용될 struct alloc_context 의 초기화를 수행해 준다.

• gfpflags_to_migratetype 함수를 통해 gfp_mask 에서 migrate type 관련 gfp flag 를 검사하여 어떤 migrate type 인지 정보를 설정한다. 

• 아래와 같은 gfp flag 들중 어떤 flag 가 선택되었는지에 따라 어떤 migrate type 인지 결정된다. MOVABLE 또는 RECLAIMABLE 에 속하지 않는다면 UNMOVABLE 이며 page groupe by mobility 기능이 설정되어 있지 않아 user page, kernel page 를 구분하지 않는 경우, 모든 page 가 UNMOVABLE 로 설정된다.

    #define ___GFP_MOVABLE      0x08u 
    // MOVABLE page block 의 free_list 에서 할당 요청
    #define ___GFP_RECLAIMABLE  0x10u
    // RECLAIMABLE page block 의 free list 에서 할당 요청

• cpuset 설정여부를 검사한다. 

•   cpuset 이 설정되어 있을 경우, 각 cpuset 들과 관련된 node 에서만 memory 를 할당 받을 수 있도록 allocation mask 를 추가한다. 

    #define ___GFP_HARDWALL     0x20000u 
    // 현재 TASK 에 cpuset memory 할당정책이 설정되어 있다면
    // process 가 assign 된 CPU 에 해당하는 NODE 
    // 에서만 page 할당 가능 

• 또한 might_sleep_if 함수를 통해 gfp flag 를 검사하여 stall 되고 page fault 가 수행되어야 할 경우, might sleep 를 설정하여 다른 task 가 scheduling 될 수 있도록 해주고

  #define ___GFP_DIRECT_RECLAIM   0x400000u 
  // page 요청시 실패할 경우, direct reclaim 하여 
  // 할당 요청시 바로 free page 확보해주고 현재 요청 처리한다. 
  // kcompactd

• should_fail_alloc_page 함수를 통해 CONFIG_FAIL_PAGE_ALLOC 이 설정되어 있을 경우 buddy 로부터 page 를 받아오기 전에 미리 설정된 fault injection 의 조건(e.g. max stack depth, virtual address 범위)에 걸리는지 검사한다. 

• 또한 CMA 기능이 설정되어 있을 경우, user page 에 대한 page fault 라면 MIGRATE_MOVABLE 에서 할당 요청 실패가 되어 migrate type 에 대한 fallback 으로 page 할당 요청 시, CMA 영역을 찾아 볼 수 있도록, allocation flag 를 추가한다. 

// zone fallback list 들을 순회하며 page 할당 가능한 zone 을 찾아 page 할당
//
//    1. watermark 를 검사하여 넘는지 안넘는지 검사
//       필요시 node reclaim 하고 다시 watermark 검사 
//    2. buddy 및 per-CPU cache 로부터 요청 migrate type에 할당 시도
//    3. 자신의 migrate type 에서 할당 실패하게 되면 
//       fallback 으로 다른 type 에 할당 시도    
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 = ac->preferred_zoneref;
    struct zone *zone;
    struct pglist_data *last_pgdat_dirty_limit = NULL;
    // fallback list 가장 최근순회한 node 중 dirty limit 에 도달한 node
 
    /*
     * Scan zonelist, looking for a zone with enough free.
     * See also __cpuset_node_allowed() comment in kernel/cpuset.c.
     */
 
    for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,
                                ac->nodemask) {
 
        // 현재 zone 및 모든 fallback list 들의 zone 을 순회
        struct page *page;
        unsigned long mark;
        
        if (cpusets_enabled() &&
            (alloc_flags &ALLOC_CPUSET) &&
            !__cpuset_zone_allowed(zone, gfp_mask))
                continue;
        // cpuset 이 설정되어 있다면 page 할당 요청할 zone 이 포함되어 있는지 검사
       
        if (ac->spread_dirty_pages) {
            // write 용도로 page cache 에 page 를 할당하는 것이라면... 
            // dirty limit 에 도달하지 않은 node 에서 할당을 하여 한 node 에
            // dirty page 들이 몰리지 않도록 함.           
            if (last_pgdat_dirty_limit == zone->zone_pgdat)
                continue;
 
            // 현재 page 할당하려는 zone 의 node 가 이미 dirty limit 도달한 node 라면 
            // 다음 zone 으로 계속 순회
            // 즉.. ZONELIST_ORDER_ZONE 이라면..
            //  node A 의 ZONE_HIGHMEM ... node A 의 ZONE_NORMAL ... node B 의 ZONE_HIGHMEM .. node B 의 ZONE_NORMAL 
            //  의 순서로 순회하는데 이때 ZONE_HIGHMEM 에서 이미 현재 node 의 dirty 가 limit 도달했다고 설정되면 그 node 의 
            //  ZONE_NORMAL 을 확인하지 않음 다음 node 로 넘어감
 
            if (!node_dirty_ok(zone->zone_pgdat)) {
                // page 할당 받으려는 node 가 dirty limit 넘어간지 아닌지 모른다면 검사해봄 
                // vm_dirty_ratio, vm_dirty_bytes 등의 kernel parameter 를 통해 계산한 limit 값보다 크다면 
                // 현재 node 가 limit 넘는다고 마킹해 놓고 다음 zone 검사
                last_pgdat_dirty_limit = zone->zone_pgdat;
 
                continue;
            }   
        }   
 
        mark = zone->watermark[alloc_flags &ALLOC_WMARK_MASK];
        // WMARK_HIGH, WMARK_LOW, WMARK_MIN 중 현재 allocation mask 에 해당되는 값을 가져옴 
        //
        // watermark 값 검사 수행 
        // order 0 인 page 요청에 대해 fast 로 검사 및 다른 요청 그냥 검사 
 
        if (!zone_watermark_fast(zone, order, mark,
                       ac_classzone_idx(ac), alloc_flags)) {
            // order 요청하면 mark 값보다 free page 가 작아지게 되는 경우...
 
            int ret;
 
            /* Checked here to keep the fast path fast */
            BUILD_BUG_ON(ALLOC_NO_WATERMARKS <NR_WMARK);
 
            if (alloc_flags &ALLOC_NO_WATERMARKS)
                goto try_this_zone;
 
            // mark 보다 작을 때, 일단 조치 취하기 전에 검사한 값이 
            // WMARK_MIN, WMARK_LOW, WMARK_HIGH 의 세가지 기준값으로 비교한게 아니라면 
            // 그냥 현재 zone 에서 page 할당
 
            if (node_reclaim_mode == 0 ||
                !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
                continue;
 
            // node_reclaim_mode 가 0 이거나 watermark 값보다 작다고 
            // 판단된 zone 이 속한 node 의 distance 가 기준값인 RECLAIM_DISTANCE 보다 멀다면 
            // 그냥 다음 노드 검사
            // 즉 wmark 값보다 작아도 reclaim 하지 않도록 설정되어 있거나 reclaim 하기 너무 멀면  
            // 그냥 다음 node 에서  page 요청하도록 넘어감           
            // node_reclaim_mode 는 /proc/sys/vm/zone_reclaim_mode 에서 설정가능(이름만 zone)  
            //  0 : page alloc 시 wmark 보다 작을 때, reclaim 수행 안함. 
            //  1 : zone reclaim on
            //  2 : zone reclaim writes dirty pages out
            //  4 : zone reclaim swaps pages
 
            ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
            // 해당 zone 에 해당 page reclaim 을 수행 
            // XXX -> node_reclaim 은 분석안하고 넘어감 
 
            switch (ret) {
            case NODE_RECLAIM_NOSCAN:
                /* did not scan */
                continue;
 
            case NODE_RECLAIM_FULL:
                /* scanned but unreclaimable */
                continue;
 
            default:
 
                /* did we reclaim enough */
                // page reclaim 후, watermark 다시 검사
                if (zone_watermark_ok(zone, order, mark,
                        ac_classzone_idx(ac), alloc_flags))
                    goto try_this_zone;
                    // 현재 zone 가능하다면 할당해주고 불가능 하면 다음 zone 검사
                continue;
            }
        }
 
 
 
try_this_zone:
 
        // 현재 zone 에서 page 를 할당할 수 있으니 buddy allocator page 요청 
        // 아직 free page 의 수를 통해 할당이 가능할 것이라는 것만 알고 order 에 맞는
        // 연속적인 page 가 가능한지는 모름
        page = rmqueue(ac->preferred_zoneref->zone, zone, order,
                gfp_mask, alloc_flags, ac->migratetype);
 
        if (page) {
            // order 에 해당하는 연속적 page 가 있어서 할당 해 줄 수 있는 경우
            prep_new_page(page, order, gfp_mask, alloc_flags);
            // 할당해줄 연속된 page 를 반환하기 전 점검 및 page allocation 후, 
            // _refcount, page clearing, compound page 설정 등 
 
            /*
             * If this is a high-order atomic allocation then check
             * if the pageblock should be reserved for the future
             */
 
            if (unlikely(order &&(alloc_flags &ALLOC_HARDER)))
                reserve_highatomic_pageblock(page, zone, order);
            return page;
 
        }
    }
 
 
    return NULL;
 
}

get_page_from_freelist 함수에서는 watermark 를 검사하고 buddy 할당자로부터 page 를 받는 등의 일을 수행한다. 

• order 승수의 page 할당 요청을 해줄 때, watermark 값을 넘지 않는지 검사하여 page 할당을 요청할 zone 을 찾아내기 위해 for_next_zone_zonelist_nodemask 매크로 함수를 통해 fallback list zone 들을 순회한다. 

• ALLOC_CPUSET 등의 allocation mask 등이 설정되어 cpuset 설정된 CPU 가 달린 node 에서만 page 를 할당해 주어야 할 경우, 현재 검사하는 zone 이 포한된 node 가 해당이 되는지 검사하여 해당이되지 않을 경우 다음 node 를 검사한다. 

• page cache page 를 할당해주는 page fault 일 경우 

• node_dirty_ok 함수의 계산 과정에서 발생할 수 있는 overhead 를 줄이기 위해 최근 dirty page limit 을 넘은 node 에 대한 정보를 last_page_dirty_limit 에 가지고 있는다. 

• 현재 node 가 node 별 최대 dirty page 비율을 넘어갔는지 검사하며 이를 검사하기 위해 node_dirty_ok 함수를 수행하며 제한값을 넘어 갔을 경우 다른 zone 으로 넘어가 검사를 수행한다. 

• allocation flag 에 따라 struct zone 에서 기준값으로 현재 zone 의 free page 수와 비교할 WMARK_HIGH, WMARK_LOW, WMARK_MIN 중 하나의 watermark 값을 가져온다. 

    #define ALLOC_WMARK_MIN     WMARK_MIN 
    // zone->watermark[0] 사용
    #define ALLOC_WMARK_LOW     WMARK_LOW
    // zone->watermark[1] 사용
    #define ALLOC_WMARK_HIGH    WMARK_HIGH
    // zone->watermark[2] 사용 
    #define ALLOC_NO_WATERMARKS 0x04 /* don't check watermarks at all */  

• zone_watermark_fast 함수를 통해 설정된 zone 의 free page 양이 order 승수의 page 만큼의 요청를 충족 시킬 수 있는지 즉 mark 값보다 작은지 검사한다. 

• zone 의 free page 수가 mark 값보다 작을 경우, 먼저 WMARK_HIGH, WMARK_LOW,WMARK_MIN 의 세가지 기준값으로 검사한 것이 아니라면 현재 zone 에서 할당을 수행한다. 

• NUMA 일 경우(NUMA 가 아니라면 node_reclaim_mode 는 0 임), kernel parameter 인 node_reclaim_mode

 ( zone_reclaim_mode 에서 node_reclaim_mode 로 변경됨)이 설정되어 있지 않거나 zone_allows_reclaim 함수를 통해 memory 를 할당받으려는 zone이 속한 node 와의 distance 가 기준값인 RECLAIM_DISTANCE (default : 30) 보다 작다면 할당 받을 다른 node 및 zone을 찾는다. 

• node_reclaim_mode 은 page fault 시에 memory pressure 가 높을 경우 즉 free page 가 watermark 값보다 작을 경우, page reclaim 의 동작 여부를 정해 줄 수 있는 kernel parameter 이며 아래와 같은 값들의 조합으로 사용할 수 있다. 

        * 0 : node reclaim 수행 하지 않음

        * 1 : node reclaim 수행

        * 2 : dirty page 을 write back 해주어 node reclaim 수행

        * 4 : page 를 swap 해주어 node reclaim 수행

• 현재 node 에서 reclaim 하도록 설정되어 있거나 node distance 가 너무 먼 경우, 현재 node 에서 node_reclaim 함수를 통해 page reclaim 을 수행해 준다. 

• page reclaim 이 정상적으로 수행 된 경우, zone_watermark_ok 함수를 통해 mark 값을 다시 검사하여 현재 zone 에 page 할당 가능 여부를 검사한다. 

• watermark 검사를 통해 order 에 맞는 page 를 할당해 줄 수 있는 free page 가 충분히 존재 할 경우, rmqueue 함수를 통해 per-CPU cache 또는 buddy allocator 로부터 page 를 할당받는다. (free page 가 충분히 있어도 order 에 맞는 연속적인 page 가 있다는 것은 아직 알 수 없으므로 rmqueue 로부터의 page 할당이 실패할 수 있다.)

• page 할당이 성공한 경우 page 를 반환하기 전에 필요한 page 정보 필드들을 초기화 해준다.  (buddy 로부터 할당받은 page 라는 것, compound page 일 경우 추가 설정 등.)

// node 의 dirty page 가 최대 제한을 넘어가는지 확인하여 반환
bool node_dirty_ok(struct pglist_data *pgdat)
{
 
    unsigned long limit = node_dirty_limit(pgdat);
    // pgdat 노드의 dirty page 최대 제한값을 구함.
    // (kernel parameter 로 설정된 vm_dirty_ratio , vm_dirty_bytes 에 따라 달라짐 )
 
    unsigned long nr_pages = 0;
 
    nr_pages += node_page_state(pgdat, NR_FILE_DIRTY);
    nr_pages += node_page_state(pgdat, NR_UNSTABLE_NFS);
    nr_pages += node_page_state(pgdat, NR_WRITEBACK);
    // node 의 vm_stat 에서 dirty page 관련 정보를 가져온다. 
 
    return nr_pages <= limit;
}

node_dirty_ok 함수에서는 현재 node 의 dirty page 가 최대 제한 값을 넘는지 확인한다. 

• node_dirty_limit 함수를 통해 node 의 최대 제한 dirty page 값을 계산한다. 

• node_page_stat 함수를 통해 node 별 통계 정보를 관리하는 vm_stat 에서 NR_FILE_DIRTY, NR_UNSTABLE_NFS, NR_WRITEBACK 에 해당되는 page 의 수를 가져와 더하고, 최대 제한값을 넘는지 검사한다. 

// node 의 최대 dirty page 제한값을 계산하여 반환 
// (LRU 가 per-node 이기 때문에dirty page 도 node 별로 관리됨)
static unsigned long node_dirty_limit(struct pglist_data *pgdat)
{
    unsigned long node_memory = node_dirtyable_memory(pgdat);
    // (NR_FREE_PAGES - lowmem reserve) + NR_ACTIVE_FILE + NR_INACTIVE_FILE 값 
    // 즉 현재 dirty page + dirtyable free page
    struct task_struct *tsk = current;
    unsigned long dirty;
 
    if (vm_dirty_bytes)
        dirty = DIV_ROUND_UP(vm_dirty_bytes, PAGE_SIZE) *
            node_memory / global_dirtyable_memory();
    // vm_dirty_bytes 가 설정되어 있다면 비율이 아닌 절대값으로 처리  
    else
        dirty = vm_dirty_ratio * node_memory / 100;
    // 설정되어 있지 않다면 비율로 처리
 
 
    if (tsk->flags &PF_LESS_THROTTLE || rt_task(tsk))
        dirty += dirty / 4;
    // task 가 real time task 즉 100 이하의 priority 가지는 task 라면 
    // 25 % 정도 추가해줌
 
    return dirty;
 
}

node_dirty_limit 함수는 kernel parameter 에 따라 node 의 file-backed page 로 사용될 수 있는 page 들의 최대 dirty page 제한값을 계산한다. 

• node_dirtyable_memory 함수를 통해 node 내의 가용 dirtyable page(free page - reserve page + file-backed page) 의 수를 계산한다. 

• vm_dirty_bytes 가 설정되어 있는 경우, 최대 dirty 가능 page 를 전체 노드의 dirty 가능 page (전체 system 의 free page - reserve page + file-backed page) 에서 vm_dirty_bytes 만큼 dirtyable 하므로 현재 노드의 node_memory 대비 dirtyable 을 계산한다. 

•   vm_diray_bytes : global_dirtyable_memory = dirty(구해야 하는 최대 값) : node_memory

• vm_dirty_bytes 가 설정되어 있지 않은 경우, 비율로 최대 dirty 가능 page 의 수를 계산한다. 

    * vm_dirty_ratio : 100 = dirty(구해야 하는 최대값) : node_dirty

• real time task 또는 task 에 PF_LESS_THROTTLE 이 설정된 경우, 급하게 처리되어야 하는 값이므로 최대 경계값을 1/4 만큼 증가시켜준다. 

    * real time task 는 task->prio 가 MAX_RT_PRIO 보다 작은(100보다 작은) 의 값을 가진다. 

// node 내의 dirty page cache 에 사용될 수 있는 page 들의 수 반환
static unsigned long node_dirtyable_memory(struct pglist_data *pgdat)                                                         
{   
    unsigned long nr_pages = 0;                                                                                               
    int z;                                                                                                                    
 
    for (z = 0; z <MAX_NR_ZONES; z++) {
        // node_zones 에서 z 를 더하며 순회 즉 node 내의                                                                      
        // 모든 zone 을 순회                                                                                                  
        struct zone *zone = pgdat->node_zones + z;
 
        if (!populated_zone(zone))                                                                                            
            continue;
        // 해당 zone 에 가용 page 가 없는 상태라면 즉 전체 page frame 개수 중                                                 
        // hole 을 제외한 page frame 이 없다면 다음 zone 검사                                                                 
    
        nr_pages += zone_page_state(zone, NR_FREE_PAGES);                                                                     
        // zone 별 각종 state 의 통계를 관리하는 vm_stat 배열에 저장된 
        // NR_FREE_PAGES 에 해당되는 값 가져옴 즉 현재 검사하는 ZONE 의 free page                                             
        // 수를 가져와 더함                                                                                                   
    }
 
    
    /*
     * Pages reserved for the kernel should not be considered                                                                 
     * dirtyable, to prevent a situation where reclaim has to                                                                 
     * clean pages in order to balance the zones.                                                                             
     */                                                                                                                       
 
    nr_pages -= min(nr_pages, pgdat->totalreserve_pages);
    // free page 수 에서 OOM 막기 위해 최소한 node 가                                                                         
    // 가지고 있어햐 하는 free page 수는 제외함                                                                               
    nr_pages += node_page_state(pgdat, NR_INACTIVE_FILE);
    // file backed page 용으로 사용중인 victim candidate page 를 더함
    nr_pages += node_page_state(pgdat, NR_ACTIVE_FILE);
    // file backed  page 용으로 사용중인 working set hot page 를 더함 
 
    return nr_pages;
 
}

node_dirtyable_memory 함수는 현재 node 의 dirty 가 될 수 있는 memory 즉 file-backed page 용도의 page 와 free page 의 합을 반환한다. 

• node 가 가진 zone 들을 순회한다. 

• 순회중인 zone 이 가용 page 즉 hole 을 제외한 present_page 가 없는 zone 이라면 다음 zone 을 검사한다. 

• zone_page_state 함수를 통해 각 zone 의 통계정보를 관리하는 vm_stat 로 부터 현재 zone 의 free page 수를 받아온다. 

• 계산한 node 내의 전체 free page 에서 OOM 을 막기 위해 미리 예약된 free page 의 수를 빼준다. 

• node_page_state 함수를 통해 node 의 통계정보를 관리하는 vm_stat 로부터 file-backed page 의 수를 free page 의 수에 더해준다.  

// 현재 zone 인 z 의 free page 가 order 요청이 와도 mark 값보다 작아지게 되는지 검사 
// order-0 인 page 요청에 대해 fast path 수행
static inline bool zone_watermark_fast(struct zone *z, unsigned int order,
        unsigned long mark, int classzone_idx, unsigned int alloc_flags)
{
    long free_pages = zone_page_state(z, NR_FREE_PAGES);
    // 현재 zone 의 free page 수 
    long cma_pages = 0;
 
#ifdef CONFIG_CMA
    /* If allocation can't use CMA areas don't use free CMA pages */
    if (!(alloc_flags &ALLOC_CMA))
        cma_pages = zone_page_state(z, NR_FREE_CMA_PAGES);
    // CMA 영역에서 page 를 받아와야 하는 경우가 아니라면 
    // CMA 용도의 free page 는 빼주어야 하므로
    // 현재 zone 의 일반 free page 가 아닌 CMA 영역에 남은 free page 를 가져옴 
 
#endif
 
    if (!order &&(free_pages - cma_pages) >mark + z->lowmem_reserve[classzone_idx])
        return true;
    // order 이 0 인 경우 즉 page 1 개에 대한 요청일때에 대하여 검사  
    // (전체 free page 수 - CMA 를 위한 free page) >(watermark 값) + (현재 zone 의 reserve free page) 
    return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,
                    free_pages);
 
} 

zone_watermark_fast 함수를 통해 order 이 0 인 경우와 아닌 경우를 구분하여 watermark 값인 mark 보다 free page 가 적은지 검사한다. 

• zone_page_state 함수를 통해 zone 의 통계정보를 관리하는 vm_stat 로부터 file-backed page 의 수를 free page 의 수에 더해준다.  

• ALLOC_CMA 가 설정되어 있어 CMA 영역을 통해 free page 를 받아와야 하는 것이 아니라면 CMA 영역의 free page 는 배제하여야 하므로 CMA 영역의 free page 의 수를 받아온다. 

• order 가 0 일 때, watermark 값보다 커서 할당이 가능한지 구한다. 

• 전체 free page - CMA free page - zone 의 reserved page 

•  __zone_watermark_ok 함수를 통해 order 이 1 이상인 경우 및 0 에서 wmark 보다 작은 경우에 대해 검사를 수행한다. 

// 현재 zone 의 free page 가 mark 의 기준 경계값 벗어나는지 검사
bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,
             int classzone_idx, unsigned int alloc_flags,
             long free_pages)
{            
    long min = mark;
    int o;
    const bool alloc_harder = (alloc_flags &ALLOC_HARDER);
    
    /* free_pages may go negative - that's OK */
    free_pages -= (1 <<order) - 1;
    // order 요청에 맞게 free_pages 감소
    if (alloc_flags &ALLOC_HIGH)
        min -= min / 2;
    // ALLOC_HIGH 설정시 WMARK_MIN  감소 
    
    if (likely(!alloc_harder))
        free_pages -= z->nr_reserved_highatomic;
    else
        min -= min / 4;
    // 설정시 WMARK_MIN 감소 
 
#ifdef CONFIG_CMA
 
    /* If allocation can't use CMA areas don't use free CMA pages */
    if (!(alloc_flags &ALLOC_CMA))
        free_pages -= zone_page_state(z, NR_FREE_CMA_PAGES);
    // ALLOC_CMA 설정 시, CMA 영역의 free page 수 감소
 
#endif
 
    if (free_pages <= min + z->lowmem_reserve[classzone_idx])
        return false; 
    // free_page 의 양이 OOM 막기 위해 예약된 lowmem_reserve 를 제외한 min 보다 작다면 
    // 기준 watermark 보다 작게 되므로 false 반환
    //
 
    /* If this is an order-0 request then the watermark is fine */
    if (!order)
        return true;
 
    /* For a high-order request, check at least one suitable page is free */
    for (o = order; o <MAX_ORDER; o++) {
        // 현재 요청 order 보다 상위 order 의 free_area 순회 
        struct free_area *area = &z->free_area[o];
        int mt;
        
        if (!area->nr_free)
            continue;
 
        // 상위 order 에 free 없다면 계속 위로
        if (alloc_harder)
            return true;
 
        for (mt = 0; mt <MIGRATE_PCPTYPES; mt++) {
            if (!list_empty(&area->free_list[mt]))
                return true;
        }
        // pcp list 에도 없는지 검사 
 
 
 
#ifdef CONFIG_CMA
 
        if ((alloc_flags &ALLOC_CMA) &&
            !list_empty(&area->free_list[MIGRATE_CMA])) {
            return true;
        }
 
#endif
 
    }
 
    return false;
 
}

__zone_watermark_ok 함수는 order 의 page 를 할당하였을 때, mark 값을 벗어나는지 검사한다.

• ALLOC_HARDER 또는 ALLOC_HIGH flag가 설정되어 있을 경우, 비교할 watermark min 의 값을 각각 50% 와 25% 줄여주어 현재 할당이 될 수 있도록 기준값을 낮추어 준다. 

• 현재 zone 의 OOM 막기 위한 reserve 값 + watermark min 의 값이 free page 보다 많은지 비교하여 zone 에 존재하는 전체 free page가 할당해 주면 안되는 상태인지 검사한다. 

• 요청 order 부터 상위 order 로 이동하며 각 order 의 free_area 에 해당하는 모든 migrate type 들 중 order 만큼의 크기를 가진 free page 가 있는지 검사한다. 

// 현재 zone 에서 order 에 맞는 page 를 할당 할 수 있으므로 alloc_flags 와 migratetype 에 맞는 page  할당해줌 
// buddy allcator 에서 직접적으로 받아오는 핵심 함수
static inline
struct page *rmqueue(struct zone *preferred_zone,
            struct zone *zone, unsigned int order,
            gfp_t gfp_flags, unsigned int alloc_flags,
            int migratetype)
{
    unsigned long flags;
    struct page *page;
 
    if (likely(order == 0)) {
        // order-0 에 대한 page 요청이라면 즉 1 개의 page 만 요청이 왔다면 
        // per-CPU page cache 에서 page 할당. 
        page = rmqueue_pcplist(preferred_zone, zone, order,
                gfp_flags, migratetype);
 
        goto out;
    }
 
 
    WARN_ON_ONCE((gfp_flags &__GFP_NOFAIL) &&(order >1));
    // order 가 0이 아닌 즉 2 개 이상의 page 요청에 대한 경우 
    // per-CPU cache 가 아닌 buddy allocator 에서 처리
 
    spin_lock_irqsave(&zone->lock, flags);
 
    do {
        page = NULL;
        if (alloc_flags &ALLOC_HARDER) {
            page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
            // 반드시 할당되어야 하는 경우 MIGRATE_HIGHATOMIC 으로 예약된
            // free_list 로부터 page 할당 수행
 
            if (page)
                trace_mm_page_alloc_zone_locked(page, order, migratetype);
        }
 
        if (!page)
            page = __rmqueue(zone, order, migratetype);
        // ALLOC_HARDER 설정되어도 buddy 의 MIGRATE_HIGHATOMIC 으로 할당이 실패하거나        
        // ALLOC_HARDER 가 설정되어 있지 않은 경우 ...
        // fallback 이 가능한 __rmqueue 호출 
 
    } while (page &&check_new_pages(page, order));
    // 원래 자신의 migratetype 에서 받은 거든 fallback 을 통해 받은 거든 
    // bad page 인지 검사
 
    spin_unlock(&zone->lock);
    // buddy 에서 받아오기 끝. lock 풀기
 
    if (!page)
        goto failed;
 
    __mod_zone_freepage_state(zone, -(1 <<order),
                  get_pcppage_migratetype(page));
 
    __count_zid_vm_events(PGALLOC, page_zonenum(page), 1 <<order);
    zone_statistics(preferred_zone, zone);
    local_irq_restore(flags);
 
out:
 
    VM_BUG_ON_PAGE(page &&bad_range(zone, page), page);
    return page;
 
failed:
    local_irq_restore(flags);
    return NULL;
 
}

rmqueue 함수는 page 를 할당할 zone 을 골랐으므로 zone 에서 alloc_flags 와 migrate type 에 맞는 page 를 할당해주는 일을 수행한다. 

• order 가 0 인지 즉 page 1 개에 대한 요청인지 검사한다.  

• 맞다면 rmqueue_pcplist 함수를 통해 per-CPU cache 로부터 page 를 할당해 주며 per-CPU cache 가 비게 되면 buddy 로부터 다시 채워준다. 

• buddy 에 접근하기 위해 현재의 interrupt context 를 저장 해 놓고,  zone 의 lock 을 잡는다. 

• allocation flag 에 ALLOC_HARDER 가 설정되어 있다면

• 기존 migrate type 이 아닌 MIGRATE_HIGHATOMIC 의 migrate type 을 통해 미리 high atomic 용으로 예약된 free list 로부터 할당을 받는다. 

    * MIGRATE_HIGHATOMIC

      enum {
          //...
          MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
          // MIGRATE_RESERVE 가 삭제되고 추가된 것으로 high-order atomic allocation 을 위한 
          // page 들을 예약해둠(최대 전체 zone 의 1%) 
          // 즉 반드시 바로 buddy 에서 할당받을 수 있어야 하는 예약된 page 들
      };

• __rmqueue 함수를 통해ALLOC_HARDER 가 설정되어 있지 않거나, HIGH_ATOMIC 으로도 할당이 안된 경우, 원래 자신의 migrate type 에 맞는 page 요청 및 migratetype fallback page 요청을 수행한다. 

• 함수가 할당성공하게 되면 check_new_pages 함수를 통해 bad page 인지 즉 할당해도 되는 page 인지 검사한다. 

• buddy allocator 에 접근을 끝냈으므로 lock 반환 및 interrupt context 복원을 하고 page 할당된 사항을 zone 의 vm_stat 통계에 추가하는 일등을 수행한다. 

// 현재 zone 의 per-CPU cache 로부터 migrate type 에 맞는 page 1 개를 받아옴
static struct page *rmqueue_pcplist(struct zone *preferred_zone,
            struct zone *zone, unsigned int order,
            gfp_t gfp_flags, int migratetype)
{
    struct per_cpu_pages *pcp;
    // per-CPU cache
    struct list_head *list;
    bool cold = ((gfp_flags &__GFP_COLD) != 0);
    // cold page 요청이 들어온 경우 설정
    // (이후에 별로 사용하지 않을 것으로 예상될 때) 
    struct page *page;
    unsigned long flags;
 
    local_irq_save(flags);
    pcp = &this_cpu_ptr(zone->pageset)->pcp;
    // 현재 zone 의 per-CPU cache 가져옴
    list = &pcp->lists[migratetype];
    // 현재 migrate type 에 맞는 per-CPU page list 가져옴
    page = __rmqueue_pcplist(zone,  migratetype, cold, pcp, list);
    // per-CPU cache 에서 1 개의 page 를 받아옴
 
    if (page) {
        __count_zid_vm_events(PGALLOC, page_zonenum(page), 1 <<order);
        zone_statistics(preferred_zone, zone);
    }
 
    local_irq_restore(flags);
 
    return page;
 
}

rmqueue_pcplist 함수는 per-CPU cache 에서 page 할당을 수행하고 migrate type 에 맞는 page 1 개를 반환한다. 

• gfp flag 를 확인하여 cold page 를 할당받으려 요청된 것인지 확인한다. 

  #define ___GFP_COLD     0x100u 
  // 이후에 별로 다시 page 를 사용하지 않을 것 
  // 같으므로 cold page 가 필요함 
  // per-CPU cache 에 cold page 를 요청

• per-CPU cache 에서의 할당을 위해 interrupt 정보를 저장해 놓고, 현재 CPU 의 interrupt 를 disable 한다. 

• this_cpu_ptr 함수를 통해 현재 CPU 의 struct per_cpu_pageset 를 가져와 struct per_cpu_pages 를 가져온다. 

 
  //  
  // +---------------------------------------------+
  // | +--------+ +--------+ +--------+ +--------+ |
  // | |  CPU 0 | |  CPU 1 | |  CPU 2 | |  CPU 3 | |
  // | +--------+ +--------+ +--------+ +--------+ |
  // | +-----------------------------------------+ |
  // | |                   8 MB                  | |
  // | +-----------------------------------------+ |
  // +-------------------NODE 0--------------------+
  //                       
  //  
  //  
  // node - ZONE_DMA     - per_cpu_pages  
  //                           |                                      hot          cold
  //                           |      --- CPU0 - MIGRATE_UNMOVABLE   - p0-p0-p0-...
  //                           |      |          MIGRATE_MOVABLE     - p0-p0-p0-...
  //                           |      |          MIGRATE_RECLAIMABLE - p0-p0-p0-...
  //                           |      |
  //                           |      --- CPU1 - MIGRATE_UNMOVABLE   - p0-p0-p0-...
  //                           |      |          MIGRATE_MOVABLE     - p0-p0-p0-...
  //                           |      |          MIGRATE_RECLAIMABLE - p0-p0-p0-...
  //                           |      |
  //                           |      --- CPU2 - MIGRATE_UNMOVABLE   - p0-p0-p0-...
  //                           |      |          MIGRATE_MOVABLE     - p0-p0-p0-...
  //                           |      |          MIGRATE_RECLAIMABLE - p0-p0-p0-...
  //                           |      |
  //                           |      --- CPU3 - MIGRATE_UNMOVABLE   - p0-p0-p0-...
  //                           |      |          MIGRATE_MOVABLE     - p0-p0-p0-...
  //                           |      |          MIGRATE_RECLAIMABLE - p0-p0-p0-...
  //                           |      |
  //                           +      |
  //                         buddy  order 0 
  //                                order 1
  //                                order 2
  //                                ...
  //      
  //        ZONE_NORMAL  - per_cpu_pages  same as ZONE_NORMAL
  //                           |
  //                           +
  //                         buddy
  //  
  //        ZONE_HIGHMEM - per_cpu_pages  same as ZONE_HIGHMEM
  //                           | 
  //                           + 
  //                         buddy 
 
  // per page cache 로 buddy 애래서 order-0 요청의 page 에 대해 처리 
 
  struct per_cpu_pages {
 
      int count;      /* number of pages in the list */
      // list 의 page 수
      int high;       /* high watermark, emptying needed */
      // count 가 넘으면 안되는 값 즉 count <high 이어야 함
      // high 를 넘게될 경우, batch 만큼 buddy 에게 다시 돌려줌(lazy coalescing)
      int batch;      /* chunk size for buddy add/remove */
      // list 가 비게 될 때, buddy 로부터 한번에 받아올 page pool 내의 
      // page 개수
            
      /* Lists of pages, one per migrate type stored on the pcp-lists */
      struct list_head lists[MIGRATE_PCPTYPES];
      // MIGRATE_UNMOVABLE 
      // MIGRATE_MOVABLE 
      // MIGRATE_RECLAIMABLE 
      // 3 가지 type 의 order 0 개수의 page list 존재     
      // list 에서 뒤에 있을수록(last entry) cold page 이고, 
      // 앞에 있을 수록(first entry) hot page 임
 
  };      

• per-CPU page list 로부터 현재의 migrate type 에 맞는 1 page list 를 가져온다. 

• __rmqueue_pcplist 함수를 통해 해당 per-CPU list 로부터 migrate type 의 cold 여부의 page 를 하나 가져온다. 

• per-CPU list 에 대한 접근을 끝내고 interrupt 복원하며 lock 을 놓는다. 

// 현재 zone 의 per-CPU cache 로부터 migrate type 에 맞는 page 1 개를 받아오며 
// 필요시(per-CPU cache 가 비어있게 되면) page 를 buddy 에서 받아 per-CPU cache 채움
static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype,
            bool cold, struct per_cpu_pages *pcp,
            struct list_head *list)
{
    struct page *page;
 
    do {
        if (list_empty(list)) {
            // 해당 migrate type 의 per-CPU cache 에 할당 가능한 page 가 없다면 
            // 즉 per-CPU cahce 가 비어있다면 buddy 에서 가져와 해당 type 에 채워줌
            pcp->count += rmqueue_bulk(zone, 0,
                    pcp->batch, list,
                    migratetype, cold);
            // migrate typ order-0 의 page 1 개 batch 개를 buddy 로부터 받아 list 에 추가
            // buddy 에서 받아온 page 수만큼 pcp->count 수 증가
 
            if (unlikely(list_empty(list)))
                return NULL;
        }
 
        // 이제 per-CPU cache 로부터 cold 여부에 따라 page 1 개 가져옴
        if (cold)
            page = list_last_entry(list, struct page, lru);
        // cold 일 경우 list 의 뒤에서 받아옴
        else
            page = list_first_entry(list, struct page, lru);
        // hot 일 경우 list 의 앞에서 받아옴
 
        list_del(&page->lru);
        pcp->count--;
 
    } while (check_new_pcp(page));
    // per-CPU cache 로부터 받은 page 의 사용가능 여부 검사 
    // 즉 H/W corrupted 등의 여부 검사
 
    return page;
 
}

__rmqueue_pcplist 함수는 per-CPU cache 에서 page 를 받고 per-CPU 가 비게 되면 batch 만큼 buddy 로부터 page 를 받아 per-CPU에 채우는 일을 수행한다. 

•  현재 per-CPU list 가 비어있는지 검사한다. 

• 비어있다면 rmqueue_bulk 함수를 통해 buddy 로부터 migrate type 의 cold 여부 page 를 order 0 의 page 를 batch 만큼 받아 per-CPU 에 채운다. 

• 현재 할당이 cold page 할당인지 검사하여 cold page 라면 per-CPU list 의 뒤에서 page 를 받아오고 cold page 요청이 아니라면 per-CPU list 의 앞에서 page 를 가져온다. 

• 해당 page 를 per-CPU list 에서 떼어내고 pcp 에 page 수를 하나 감소시킨다. 

• check_new_pcp 함수를 통해 현재 page 에 대한 bad page 검사를 한다. 

// 한번에 많은 양만큼 buddy 에서 free page 받아옴
// buddy 에서 migratetype 의 free_list 에서 order 크기의 
// cold 여부의 연속 page 를 count 만큼(2^order * count) list 에 넣어줌
static int rmqueue_bulk(struct zone *zone, unsigned int order,
            unsigned long count, struct list_head *list,
            int migratetype, bool cold)
{
 
    int i, alloced = 0;
 
    spin_lock(&zone->lock);
 
    for (i = 0; i <count; ++i) {
        // 2^order 크기의 연속된 page 를 count 번만큼 buddy 에서 받아옴
        struct page *page = __rmqueue(zone, order, migratetype);
 
        if (unlikely(page == NULL))
            break;
        // page 받아오는 것이 실패하면 더이상 그만큼 연속 memory 가 없는 것이므로 out
 
        if (unlikely(check_pcp_refill(page)))
            continue;
        // bad page 검사         
 
 
        if (likely(!cold))
            list_add(&page->lru, list);
        // cold 요청이 아닐 경우, per-CPU page list 의 선두에 마지막에 추가해 준다. 
        else
            list_add_tail(&page->lru, list);
        // cold 요청일 경우, per-CPU page list 의 마지막에 page 를 추가한다. 
 
        list = &page->lru;
        // 다음 추가를 위해 list 주소 현재 추가한 page 의 page->lru 로 update
 
        alloced++;
 
        if (is_migrate_cma(get_pcppage_migratetype(page)))
            __mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
                          -(1 <<order));
    }
 
 
    __mod_zone_page_state(zone, NR_FREE_PAGES, -(i <<order));
    // zone 의 stete 나타내는 vm_stat 에 할당한 정보 수정
 
    spin_unlock(&zone->lock);
 
    return alloced;
 
}

rmqueue_bulk 함수는 buddy 의 order 내의 migrate type 에 해당하는 free_list 로부터 page 를 count 개 받아 list 에 채우는 역할을 수행한다. 

• buddy 에대한 접근이므로 zone 의 lock 을 잡고

• count 만큼 반복한다. 

• __rmqueue 함수를 통해 buddy 로부터 page 를 받는다. 

• cold page 라면 list 의 뒤에 채우고, cold page 가 아니라면 list 의 앞에 채운다. 

// buddy 로부터 migratetype 의 2^order 크기 연속된 page 받아옴 
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;
 
    /* Find a page of the appropriate size in the preferred list */
    for (current_order = order; current_order <MAX_ORDER; ++current_order) {
        // 현재 요청 order 부터 하여 연속된 page 를 찾음 
        area = &(zone->free_area[current_order]);
        page = list_first_entry_or_null(&area->free_list[migratetype],
                            struct page, lru);
 
        if (!page)
            continue;
 
        // 현재 order 의 free page 가 없다면 상위 order 로 이동
        list_del(&page->lru);
        // 현재 order 의 free_list 에서 page 제거 
        //
        //  free_area[1] <--> p1 <--> pk <--> pn <--> ...
        //                    |       |       |   
        //                    p2      pk+1    pn+1 
        //
        //  free_area[1] <--> pk <--> pn <--> ...
        //                    |       |   
        //                    pk+1    pn+1 
        //
        //                    p2 -- p1
        // 
 
        rmv_page_order(page);
        // 할당해줄 page 의 order, _mapcount 를 초기화 
 
        area->nr_free--;
        // 연속적 page 수 감소
 
        expand(zone, page, order, current_order, area, migratetype);
        // 현재 할당해 줄 current_order 가  요청받은 order 보다 
        // 큰 상태일 수 있음  
        // 2^current_order 크기으 page 에서 2^order 빼고 나머지를 각각의 
        // order 내의 migratetype 에 맞는 free_list 에 추가 
        //
 
        set_pcppage_migratetype(page, migratetype);
        // 할당해줄 page 의 migratetype 정보를 초기화
 
        return page;
    }
 
    return NULL;
}

__rmqueue_smallest 함수는 zone 에서 migrate type 의 order 요청에 대해 상위 order 를 순회하며 할당가능 page 를 주고 나머지를 잘라 다시 요청 migrate type 의 free list 에 넣어주는 일을 수행한다. 

• 요청 order 부터 MAX_ORDER 까지 순회하며 현재 order 에 요청 page 만큼의 연속된 page 없을 시 상위 ordr 로 이동한다. 

•   * 해당 order 의 struct free_area   를 받아 migrate type 에 해당하는 free_list 가 비었는지 확인한다. 

  struct free_area {
      struct list_head    free_list[MIGRATE_TYPES];
      // free page 를 page block type 별로 묶기 위해 
      // migrate type 별로 free page block 을 연결한 것 
      // migrate type 단위 page block 관리를 통해 MOVABLE, NON_MOVABLE 을
      // 분리하여 user domain 의 page 와 kernel domain 의 page 를 따로 관리하기 위함
      // 하지만 각 domain 의 page block 부족시 다른 domain 으로 fall back 가능
      // fall back order : MIGRATE_UNMOVABLE -> MIGRATE_RECLAIMABLE -> MIGRATE_MOVABLE -> MIGRATE_RESERVE
      //                          MIGRATE_MOVABLE -> MIGRATE_RECLAIMABLE -> MIGRATE_UNMOVABLE -> MIGRATE_RESERVE       
      // 
      // free_list 에 연결된 page 중 앞에 있을수록 hot page 이며 뒤에 있을 수록 cold 한 page
 
      unsigned long       nr_free;
      // 현재 order 의 모든 page type 들의 free page 의 수 
      // 즉 해당 order 의 연속적인 page 의 수
  };  

           

• page 를 할당해 줄 수 있을 경우, buddy 내의 해당 free list 에서 그 연속된 page 를 뺀다. 

• rmv_page_order 함수를 통해 page 의 order 정보, _mapcount 정보를 초기화 하여 해당 page 가 buddy 의 free list 에서 나와 할당되었음을 설정한다. 

• expand 함수를 통해 원래 요청 order 보다 상위의 order 에서 할당이 된 경우, 원래 요청된 oder 를 제외하고 나머지 free page 를 즉 buddy page 들을 각각의 order 에 맞는 free list 에 추가한다. 

• set_pcppage_migratetype 함수를 통해 할당해줄 연속적 page 의 맨 첫번째 page 에 page 가 속한 migrate type 정보를 추가한다. 

// page 가 buddy 로부터 할당되기 전 struct page 내에 
// 가지고 있던 order 정보 삭제 및 buddy free 빠져나갓다는 flag 값 설저
static inline void rmv_page_order(struct page *page)
{
    __ClearPageBuddy(page);
    // struct page 의 _mapcount 의 buddy free page 를 나타내는 
    // PAGE_BUDDY_MAPCOUNT_VALUE 를 버리고 -1 으로 설정
 
    set_page_private(page, 0);
    // struct page 의 private 를 0 으로 초기화 
}

rmv_page_order 함수를 통해 할당해줄 page 가 buddy 의 free list 에서 빠지기 위한 초기화 작업을 수행한다. 

• page struct 내에는 아래와 같이 buddy 의 free list 로부터의 할당 여부를 나타내기 위한 _mapcount 와 private 등의 필드가 있다. 

struct page {
 
     //...
    union {
        unsigned counters;
        struct {
            union {
                atomic_t _mapcount;
                // 해당 page 을 가리키고 있는 pte 의 수를 의미
                // page 를 가리키는 pte 가 없을 시, -1 값을 가짐 
                // 즉 초기에는 -1 값이며 reverse mapping 에 추가 
                // 될 때마다 1씩 증가
                // e.g. 두개의 process 에서 해당 page를 사용 중일 시,
                //      이 값은 1임
                // page를 사용중인 process 의 수를 알 수 있음  
                //
                // buddy allocator 에서 ....
                //  - buddy allocator 의 free list 에 추가되게 될 때,
                //    __SetPageBuddy 함수를 통해 -128 값인 
                //    PAGE_BUDDY_MAPCOUNT_VALUE 로 설정
                //  
                //  - buddy allocator 로부터 할당되어 빠져나갈 때,
                //    __ClearPageBuddy 함수를 통해 -1 로 설정됨                
                //
 
                unsigned int active;        /* SLAB */
 
                struct {            /* SLUB */
                    unsigned inuse:16;
                    unsigned objects:15;
                    unsigned frozen:1;
                };
 
                int units;          /* SLOB */
 
            };
 
            atomic_t _refcount;
            // page reference count
            // 할당될 때, 1 로 초기화 됨.
        };
 
    };
 
    //...
 
    union {
 
        unsigned long private;      
        //  - page 가 free list 에 있을 때는 
        //    buddy 에서의 order slot 번호를 가짐 
        //    (해당 order 의 연속된 pageg 의 첫번째 page 가 가짐)
        //  - page 가 할당되게 되면 0 으로 초기화되어 시작 
        //    swap-entry 를 가지기도 함
        struct kmem_cache *slab_cache;  /* SL[AU]B: Pointer to slab */
     }
 
     //...
 
  }

• __ClearPageBuddy 를 매크로로 수행하여 buddy free list 에 있을 때 page 의 _mapcount 필드에 기록되어 있던 PAGE_BUDDY_MAPCOUNT_VALUE 대신 -1 로 초기화 한다. 

• set_page_private 함수를 수행하여 buddy free list 에 있을 때 해당 page 로부터 연속적인 free page 정보 즉 order 를 나타내고 있던 private 필드를 0 으로 초기화한다. 

// buddy allocator 에서 현재 요청 order 보다 상위 order 의 free_area 에서  
// page 를 할당 해 주어야 할 경우, 할당하고 남은 page 들을 하위 free_area 
// 에 넣어주기 위한 함수.
static inline void expand(struct zone *zone, struct page *page,
    int low, int high, struct free_area *area,
    int migratetype)
{   
 
    unsigned long size = 1 <<high;
    // page 를 할당 해줄 order (요청 order 가 아님) 의 page 개수 
    // struct free_area 또한 지금은 high order 에 대한 free_area 임 
    //
    //                      e.g. page order 3 인 요청에 대해 order 5 인 
    //                           free_list 에서 할당해준 경우
    //
    //                             1st
    //                      high : 5, low : 3, size : 32
    //
    while (high >low) {//             2nd     3rd
        area--;         //      area    4       3                 
        high--;         //      high    4       3
        size >>= 1;     //      size   16       8  
   
        VM_BUG_ON_PAGE(bad_range(zone, &page[size]), &page[size]);    
 
        if (set_page_guard(zone, &page[size], high, migratetype))
            continue;
                    
        list_add(&page[size].lru, &area->free_list[migratetype]);
        // page 위치부터 size 만큼 떨어진 page 를 free_area 에 추가
 
        area->nr_free++;
        // 추가된 area 의 연속된 page 수 증가 
 
        set_page_order(&page[size], high);
        // buddy free list 에 추가된 것이므로 order 정보 추가
        //
        //  x : free_area 에 들어감
        //  * : page 할당될 것
        //
        //  1st 
        //  |                               |
        //  |               |               |
        //  |       |       |       |       |
        //  |   |   |   |   |   |   |   |   | 
        // 
        //  page
        //
        //  2nd
        //  |                               |
        //  |               |               |
        //  |       |       |       |       |
        //  |   |   |   |   |   |   |   |   | 
        //  xxxxxxxxxxxxxxxx
        //  page             free_area[4]->free_list[migratetype] 에 추가
 
        //
        //  3rd
        //  |                               |
        //  |               |               |
        //  |       |       |       |       |
        //  |   |   |   |   |   |   |   |   | 
        //  xxxxxxxx
        //  page     free_area[3]->free_list[migratetype] 에 추가
 
    }
 
}

expand 함수를 통해 buddy 에서 받은 연속적인 page 가 원래 low 크기 order 요청이 었으나 high 크기의 order 에서 할당 된 경우, low 크기의 연속적 page 를 제외한 나머지 free page 를migrate type 의 free list 에 도로 넣어주는 일을 수행한다. 

• 현재 buddy 로부터 받은 연속적 page 의 크기인 size 를 high order 만큼으로 초기화 하여 놓는다. 

• high order 부터 원래 요청 크기인 low order 까지 순회하며 각 order 크기의 page 를 free list 에 넣는다. 

• high, area, size 를 감소시키며 buddy 로부터 받은 연속된 page 의 바로 하위 order 부터 시작하여 free page 에 넣을 수 있는 연속된 free page 를 찾는다. 

• page 로부터 size 만큼 떨어진 위치로부터 그 order 에 해당하는 area 의 free list 에 추가하고 nr_free 를 증가시키며 다시 buddy 에 들어가게 되었으므로 set_page_order 함수를 통해 struct page   private 필드에 order 정보를 다시 저장한다. 

// buddy 로부터 page 가 할당되게 되면 현재 page 가 어느 migratetype 에 속해 
// 있는지 정보를 초기화 해줌
static inline void set_pcppage_migratetype(struct page *page, int migratetype)
{
    page->index = migratetype;
}

 

set_pcppage_migratetype 함수를 통해 할당해준 page 의 migrate type 정보를 저장한다. 

• page struct 내에는 아래와 같이 buddy 의 free list 로부터의 할당된 page 의 migrate type 을 나타내기 위한 index 필드가 있다.

    struct page {
    //...
    /* Second double word */
    union {
        pgoff_t index;      /* Our offset within mapping. */
        // mmap 에서의 즉 struct page 배열에서의 page frame offset 
        //
        // buddy allocator 로부터 page 가 할당되면 
        // 현재 page 가 속한 migrate type 번호가 들어감
        void *freelist;     /* sl[aou]b first free object */
        /* page_deferred_list().prev    -- second tail page */
    };
    //...
  }

• struct page 의 index 에 migrate type 정보를 초기화한다. 

// 해당 zone 의 free_are 에 migratetype 의 free_list 로부터 2^order 만큼의 
// page 를 할당해 반환시도 후, page 할당 불가능 할 시, migrate type 
// fallback 되어 시도
static struct page *__rmqueue(struct zone *zone, unsigned int order,
                int migratetype)
{
    struct page *page;
 
    page = __rmqueue_smallest(zone, order, migratetype);
    // 현재 migratetype 으로 page 할당 시도
 
    if (unlikely(!page)) {
        // 원래 migratetype 에 free page 가 없으니 다른 migratetype 으로 
        // fallback 하여 page 할당 수행
 
        if (migratetype == MIGRATE_MOVABLE)
            page = __rmqueue_cma_fallback(zone, order);
        // migratetype 이 MIGRATE_MOVABLE 인 경우, CMA 가 설정되어 있다면 
        // MIGRATE_RECLAIMABLE, MIGRATE_RECLAIMABLE 로 이동 전에
        // 먼저 CMA 영역에서 할당 시도
 
        if (!page)
            page = __rmqueue_fallback(zone, order, migratetype);
        // fallback 하여 다른 type 의 page block 에서 page 받으며 
        // 필요시 order 만큼 할당하고 남은 free page 들도 migratetype 으로
        // 바꾸어 버림
 
    }
 
    trace_mm_page_alloc_zone_locked(page, order, migratetype);
 
    return page;
 
}

__rmqueue 함수를 통해 buddy 로부터 원래의 요청인 migrate type 에 해당하는 page 를 요청하며 해당 migrate type 에서 free page 를 받지 못할 시, 다른 migrate type 으로부터 page 를 요청한다. 

• kernel 에는 user 가 요청한 page 와 kernel 이 요청한 page 를 구분하여 관리하기 위해 각각의 page block 을두어 분리하려 한다. 이를 위해 page 마다 migrate type 을 가지고 있으며 아래와 같은 flag 를 통해 구분될 수 있다. 

  enum { 
      MIGRATE_UNMOVABLE,  
      // memory 내에서 위치가 변경될 수 없고, 회수도 불가능한 page block
      // kernel domain page 들 중 core 부분의 page 에 속함. 
      MIGRATE_MOVABLE,
      // memory 내에서 위치 변경 가능 및 회수 가능한 page
      // user application 에 의해 할당된 page table 을 통해 mapping 되는 page block
      // page table 내의 mapping 정보 변경을 통해 위치가 변경 될 수 있음
      MIGRATE_RECLAIMABLE,
      // memory 내에서 이동이 불가능하지만, kswapd 등에 의해 page 회수가 가능한 page block
      MIGRATE_PCPTYPES,   /* the number of types on the pcp lists */
      // per-CPU cache 에 존재하는 migrate type 까지를 나타내기 위한 flag
      MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
      // MIGRATE_RESERVE 가 삭제되고 추가된 것으로 high-order atomic allocation 을 위한 
      // page 들을 예약해둠(최대 전체 zone 의 1%) 
      // 즉 반드시 바로 buddy 에서 할당받을 수 있어야 하는 예약된 page 들
  #ifdef CONFIG_CMA
      MIGRATE_CMA,
      // 연속적 물리 memory 를 할당하는 CMA allocator 에 의해 관리되는 page block
  #endif
 
  #ifdef CONFIG_MEMORY_ISOLATION
      MIGRATE_ISOLATE,    /* can't allocate from here */
      // memory 회수 등의 작업이 진행되는 동안  기존 page list 에서 일단 
      // 분리시켜 놓기 위한 virtual page type
  #endif      
 
    MIGRATE_TYPES
  };  

• __rmqueue_smallest 함수를 통해 기존의 migrate type 으로 buddy 에 할당을 시도한다. 

• 기존 migrate type 에서 page 를 받지 못할 경우, 어쩔수 없이 다른 migrate type 으로부터 할당을 시도한다. (e.g. kernel page 가 user page block 에 free page 가 남았는지 요청)

• 그 전에 먼저 user page block 인 경우 즉 MIGRATE_MOVABLE  인 경우, CMA 가 설정되어 있다면 kernel page block 과 섞이는 것을 막기 위해  __rmqueue_cma_fallback 함수를 통해 CMA 영역에서 page 할당을 시도한다. 

• user page 요청이(MIGRATE_MOVABLE) 이 CMA 영역에서도 free page 를 못찾거나 kernel page (MIGRATE_UNMOVABLE) 이 자신의 migrate type 에 해당하는 free page 를 찾지 못하였을 경우, 어쩔수 없이 fallback 하여 __rmqueue_fallback 함수를 통해 page 할당 요청을 한다. 

// 기본 page allocation 함수인 __rmqueue_smallest 와 달리, high order 부터 
// 검사하며 다른 migratetype 까지 모무 검사
static inline struct page *
__rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
{
    struct free_area *area;
    unsigned int current_order;
    struct page *page;
    int fallback_mt;
    bool can_steal;
 
    /* Find the largest possible block of pages in the other list */
    for (current_order = MAX_ORDER-1;
                current_order >= order &&current_order <= MAX_ORDER-1;
                --current_order) {
        // fallback 전 page 할당시도 때와 달리 상위 order 부터 
        // free page 검색 수행 
        // 다른 migratetype 의 free list 에서 할당을 수행할 것이기 때문에 
        // 비교적  할당될 확률이 적은 high order 부터 free block 을 찾아 
        // page 할당 시도.
        // (but.. THP 상황에서는 대부분 그냥 2^9 개의 page 할당 시도 즉 
        //  high order 부터 allocate 되기 때문에 결국 섞이게됨.)
 
        area = &(zone->free_area[current_order]);
        // current_order 에 해당하는 free_are 가져옴
 
        fallback_mt = find_suitable_fallback(area, current_order,
                start_migratetype, false, &can_steal);
        // free page 를 찾아볼 migrate type 검사 및 fallback allcation 후 
        // 처리 방법 결정(page block steal 여부)
 
        if (fallback_mt == -1)
            continue;
 
        // current_order 에 해당하는 free page 가 없다면 다음 order 검사
        //
 
        page = list_first_entry(&area->free_list[fallback_mt],
                        struct page, lru);
        // 해당 fallback migratetype 에서 free page 가져옴
 
        if (can_steal &&
            get_pageblock_migratetype(page) != MIGRATE_HIGHATOMIC)
            steal_suitable_fallback(zone, page, start_migratetype);
        // page block steal 해야 될 경우 start_migratetype 으로 steal 
        // steal 이란...
        // page 가 속한 page block 의 free page 들을 즉 fallback page block 
        // 의 free page 들을 start_migratetype 의 free_list 로 옮김
        //
 
        /* Remove the page from the freelists */
        area->nr_free--;
 
        // fall back page 의 free_are 에 free 수 감소
        list_del(&page->lru);
 
        rmv_page_order(page);
        // fallback page block 에서 받은 page 에서 order 지워주고
 
        expand(zone, page, order, current_order, area,
                    start_migratetype);
 
        // current_order 에서 order 빼고 남은 것들을 start_migratetype 
        // 의 free list 에 채워줌 
 
        set_pcppage_migratetype(page, start_migratetype);
        // page 의 migratetype 초기화
 
        trace_mm_page_alloc_extfrag(page, order, current_order,
            start_migratetype, fallback_mt);
 
        return page;
 
    }
 
    return NULL;
 
}

__rmqueue_fallback 함수를 통해 미리 정해진  각 migrate type 별 fallback list 에 따라 다른 migrate type 의 free list 에서 page 할당을 시도한다. 

• __rmqueue_smallest 함수와는 달리 __rmqueue_fallback 함수에서는 다른 migrate type 의 page block 에서 page 를 요청하므로 최대한 free page 가 많이 남아있는 page 를 찾아 아얘 그 page block 을 현재 page 를 요청한 migrate type 용도로 steal 해버리려 한다. 이를 위해 요청 order 부터가 아닌 MAX_ORDER 부터 거꾸로 순회하며 free page 가 있는지 확인한다. 

• struct free_area 를 가져오고, find_suitable_fallback 함수를 통해 현재 page 요청한 migrate type 의 fallback list 를 읽어와  현재 거꾸로 순회중인 order 크기의 free list 를 가지고 있는 할당요청할 다른 migrate type 의 index 를 받아온다. 

• fallback migrate type 의 free list 에서 page 를 받아오기 위해 그 free list 에서 빼내온다. 

• page block steal 이 가능한 경우 steal_suitable_fallback 함수를 통해 전체 page block 을 뺏어온다. 

• page 를 free lsit 에서 삭제 및 free count 감소 등을 수행하며 원래 요청 order 를 제외하고 남은 free page 들을 expand 함수를 통해 fallback page  block 의 migrate type 이 아니라, page 를 요청한 migrate type 의 free list 에 넣어준다. 

• set_pcppage_migratetype 함수를 통해 할당한 page 의 migrate type 을 page 요청한 migrate type 으로 설정해 준다. 

// 원래 기존 page migratetype 에서 다른 migratetype 으로 fallback 요청이
// 수행되어야 할 때, 어느 migratetype 에 요청할지 선택 및 그 migratetype 에서
// page 받고 나머지 page 도 현재 요청용도로 뺏어버릴지 결정
int find_suitable_fallback(struct free_area *area, unsigned int order,
            int migratetype, bool only_stealable, bool *can_steal)
{
    int i;
    int fallback_mt;
 
 
    if (area->nr_free == 0)
        return -1;
    // order 에 free page 자체가 없다면 바로 다음 order 로 넘어가 
    // migrate 선택 할 수 있도록 종료 
 
    *can_steal = false;
    // 현재 order 에 free page 가 남아 있을 경우     
 
    for (i = 0;; i++) {
        fallback_mt = fallbacks[migratetype][i];
        // migratetype 의 fallback 순서대로 falback list 의 
        // 다음 migratetype 가져옴
 
        if (fallback_mt == MIGRATE_TYPES)
            break;
        // fallback list 모두 검사하였다면 빠져나감 
 
        if (list_empty(&area->free_list[fallback_mt]))
            continue;
        // fallback migratetype 에 free page 없다면 다음 fallback 구하기 계속
 
        if (can_steal_fallback(order, migratetype))
            *can_steal = true;
        // fallback migratetype 에 free page 가 남아있는 경우 
        // fallback 시, streal 가능 여부 설정.
        //  user page 를 kernel page block 에서 할당 요청시... 
        //  order 4 이상 일 때 steal
        //  kernel page 를 user page block 에서 할당 요청 시...
        //  page block 내에 최대 free block 다 뺏어옴
 
        if (!only_stealable)
            return fallback_mt;
 
        if (*can_steal)
            return fallback_mt;
    }
 
    return -1;
}

find_suitable_fallback 함수를 통해 page 를 요청한 migrate type 의 fallback list 를 참고하여 order 크기의 free page 를 가진 migrate type 을 반환한다. 

• order 에 free page 가 있나 먼저 확인해 본다. (아직 어떤 migrate type 이 될지는 미선택) 

• fallbacks 라는 migrate type 의 fallback list 를 순회하며 free page 를 가진 migrate type 을 찾는다. 

• fallbacks 라는 배열로 각 migrate type 에 맞는 fallback list 를 가지고 있다. 

  // 각 MIGRATETYPE 별 해당 free list 에서 page 를 얻을 수 없을 시, 
  // 다른 MIGRATETYPE 에서 받아오게 되는 순서(fallback list)
  static int fallbacks[MIGRATE_TYPES][4] = {
      [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
      [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
      [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
      // ...
  };

• can_steal_fallback 함수를 통해 현재 page 요청이 해당 fallback  migrate type 의 남은 free page 들을 다 뺏어 올 수 있는 조건인지 검사한다. 

// 원래 기존 page migratetype 에서 다른 migratetype 으로 fallback 요청이
// 수행되어야 할 때, 어느 migratetype 에 요청할지 선택 및 그 migratetype 에서
// page 받고 나머지 page 도 현재 요청용도로 뺏어버릴지 결정
static bool can_steal_fallback(unsigned int order, int start_mt)
{
 
    if (order >= pageblock_order)
        return true;
    // page 할당 하려는 page order 가 512 개의 page 요청이거나 
    // 1024 개의 page 요청인 경우 둘다 그냥 page block 이 
    // 통채로 필요하므로 strealing 은 당연한 것임. streal 가능함을 반환
 
    if (order >= pageblock_order / 2 ||
        start_mt == MIGRATE_RECLAIMABLE ||
        start_mt == MIGRATE_UNMOVABLE ||
        page_group_by_mobility_disabled)
        return true;
 
    // page 요청이 page block 전체 크기인 512 개의 page 중 ...
    //
    //  - MIGRATE_MOVABLE type 의 page 가 다른 fallback migratetype 
    //    으로 page 요청하는 경우에는 할당시도하려는 order 가 4 이삳
    //    일 경우 steal 허용
    //    -> user page 가 kernel page block 에서 page 를 받아야 한다면
    //       order 4 이상 요청일 때만 kernel page block 내에서 user page 
    //       용도로 할당하고 남은 page 도 user page 용도로 예약해 놓음
    //
    //  - MIGRATE_UNMOVABLE 또는 MIGRATE_RECLAIMABLE 의 page 가 다른 
    //    fallback migratetype 으로 page 요청하는 경우에는 그냥 steal 허용  
    //    -> kernel page 가 user page block 에서 page 를 받아야 한다면 
    //       할당하고 남은것 다 kernel 용도로 예약 해 놓음
 
    return false;
 
}

can_steal_fallback 함수를 통해 fallback migrate page block 내의 나머지 page 들을 모두 뺏어갈 수 있는지 검사한다. 

• 할당 요청이 page block 의 크기보다 큰 경우 

• page block 의 크기는 512 개의 page 이므로 order 9 or 10 의 경우에 해당된다. 

• user page block 으로의 kernel page 요청인 경우(MIGRATE_UNMOVABLE page 가 MIGRATE_MOVABLE page 로 요청) 추후의 단편화 방지를 위해 steal 을 허용한다. 

// order 에 맞는 연속적 page 들을 할당 할 수 있을 때, 할당하기로한 page 들이 
// 문제가 있는지 검사 및 조치처리등 수행
// (e.g. _refcount, page clearing, compound page 설정)
static void prep_new_page(struct page *page, unsigned int order, gfp_t gfp_flags,
                            unsigned int alloc_flags)
{
    int i;
    bool poisoned = true;
 
    for (i = 0; i <(1 <<order); i++) {
        struct page *p = page + i;
 
        if (poisoned)
            poisoned &= page_is_poisoned(p);
        // order 에 맞는 page 수 만큼 struct page 에 해당하는 page_ext 에 
        // poisoned flag 가 설정되어 있는지 검사 
        // 설정되어 있다면 poisoned pattern 을 검사 해 주어야 함
    }
 
    post_alloc_hook(page, order, gfp_flags);
    // 할당해줄 page 를 반환하기 전에 page 관련 속성 및 필드 초기화 
    //  e.g. _refcount, private 초기화, page extention 기능 설정 시, 
    //  owner 초기화 등 수행
 
    if (!free_pages_prezeroed(poisoned) &&(gfp_flags &__GFP_ZERO))
        for (i = 0; i <(1 <<order); i++)
            clear_highpage(page + i);
    // page clear 해주어야 될 시, zero filling 수행
 
    if (order &&(gfp_flags &__GFP_COMP))
        prep_compound_page(page, order);
    // compound page 에 대한 요청 상황이라면 즉 THP 등의 할당이라면 
    // order 정보, dtor 정보등 초기화 및 나머지 tail page 초기화 수행
 
 
    if (alloc_flags &ALLOC_NO_WATERMARKS)
        set_page_pfmemalloc(page);
    else
        clear_page_pfmemalloc(page);
 
}

pgrep_new_page 함수를 통해 buddy 에서 할당받은 page 의 후 처리를 해준다. 

• 먼저 order 만큼의 page 개수를 순회하며 page poisoning 설정 여부를 검사한다. 

•  post_alloc_hook 함수를 통해 order 정보 지우고 _refcount 를 1 로 초기화 하고 page poisoning 이 설정되어 있을 경우 page_is_poisoned 함수를 통해 page 를 free 해줄때 채워주었던 poisoned pattenr 을 검사한다. 또한 page owner 정보를 설정해야 될 경우, struct page_ext 에 추가한다. 

• gfp flag 에 zero flag 가 있을 경우 clear_highpage 함수를 통해 page 를 zero filling 해준다. 

• gfp flag 에 __GFP_COMP 가 설정되어 있어 compound page 일 경우, prep_compound_page 함수를 통해 order 설정 destructor 설정 PG_head 플래그 설정 등을 수행해 준다. 

// CONFIG_PAGE_POISONING 이 설정되어 있을 경우에 해당
bool page_is_poisoned(struct page *page)
{
    struct page_ext *page_ext;
 
    page_ext = lookup_page_ext(page);
    // CONFIG_PAGE_EXTENSION 이 설정되어 있는 경우..
    // page_ext 배열에서 struct page 에 해당하는  
    // struct page_ext entry 를 가져옴
 
    if (unlikely(!page_ext))
        return false;
 
    return test_bit(PAGE_EXT_DEBUG_POISON, &page_ext->flags);
    // page_ext 에 PAGE_EXT_DEBUG_POISON 이 설정되어 있는지 검사. 
    // 설정되어 있다면 page allocation 시, poisoned pattern 을 
    // 검사 해 주어야 한다. 
 
}

page_is_poisoned 함수는 CONFIG_PAGE_POISONING 이 설정되어 있지 않다면 단순 false 를 반환하지만, 설정되어 있다면 현재 page 가 poisoning 이 되어 있는지 검사를 수행한다. 

• lookup_page_ext 함수를 통해 parameter 로 주어진 page 에해당하는 struct page_ext 를 찾는다. ( struct page 에 대한 부가적인 정보를 나타내기 위해 사용용)

•  page 에 대한 struct page_ext 가 없다면 false 를 반환하고 있다면, PAGE_EXT_DEBUG_POISON bit 가 설정되어 있는지 검사한다. 

 
// 할당할 page 내의 flag 정보 초기화 수행 및 검사
inline void post_alloc_hook(struct page *page, unsigned int order,
                gfp_t gfp_flags)
{
    set_page_private(page, 0);
    // struct page 의 private  을 0 으로 초기화
    // 할당 되기 전 free list 에서 관리될 때는 private 에 order 정보 저장
 
    set_page_refcounted(page);
    // struct page 의 _refcount 를 1 로 초기화 
 
    arch_alloc_page(page, order);
    // page 할당 관련 arch 별 함수 수행
    // (s390 arch 만 해당 함수에서 뭔가 함)
 
    kernel_map_pages(page, 1 <<order, 1);
    // CONFIG_DEBUG_PAGEALLOC 이 설정 된 경우..
 
    kernel_poison_pages(page, 1 <<order, 1);
    // CONFIG_PAGE_POISONING 설정 된 경우 
    // poisoned pattern 의 변경 여부를 확인하여 
    // single bit error or page corruption 여부를 검사하고 poisoned flag 지움  
 
    kasan_alloc_pages(page, order);
 
    set_page_owner(page, order, gfp_flags);
    // CONFIG_PAGE_OWNER 가 설정되어 있을 경우... 
    // struct page 에 해당하는 struct page_ext 로부터 offset 만큼 떨어진 위치의 
    // page_owner 를 가져와 order, gfp_flags 등의 정보들 저장
 
}

post_alloc_hook 함수는 buddy 로부터 받은 page 를 할당해 주어 user 또는 kernel 이 사용하기 전에 필요한 초기화 및 검사를 수행한다. 

• set_page_private 함수를 통해 buddy 에 page 가 있을때 order 정보를 나타내던 struct page 의 private 필드를 0 으로 초기화 해준다. 

• set_page_refcounted 함수를 통해 현재 page 를 할당해주어 사용할 것이므로 struct page 의 _refcount 필드를 1로 초기화 해준다. 

• arch_alloc_pages 함수를 통해 architecture 별 page 할당 관련 mechanism 을 수행한다. (v4.11 에서는 s390 만 수행)

• kernel_map_pages 는 ... pass..

• kernel_poison_pages 함수를 통해 CONFIG_PAGE_POISONING 설정 시, buddy 로 부터 받은 page 에 대해 poisoning 검사를 수행하여 해당 page 가 그전에 free 될때, write 된 poison pattern 을 기반으로 bit error / memory corruption 을 검사한다. 

• kasan_alloc_pages 함수는 kernel address space 의 kasan address space 의 shadow memory 내에 현재 할당하려는 page 영역에 기록된 KASAN_FREE_PAGE 를 새로운 page 할당이 될 것으므로 0 으로 초기화 해주는 역할을 수행한다. 

• set_page_owner 함수를 통해 CONFIG_PAGE_OWNER 가 설정되어 있을 시, struct page 에 해당하는 아래와 같은 추가 정보를 가질

  struct page_owner 를 struct pglist_data 로부터 찾아 struct page_owner 가 들어있는 위치에서 offset 만큼 이동하여 struct page_ext 를 찾고, 할당될 때의 gfp flag 정보, order 정보 등의 debugging 정보를 설정한다. 

// compound page 에 필요한 order, free functino 등 설정 
void prep_compound_page(struct page *page, unsigned int order)
{
    int i;
    int nr_pages = 1 <<order;
 
    set_compound_page_dtor(page, COMPOUND_PAGE_DTOR);
    // 첫번째 tail page 에 compound page 가 free 될 때 호출될 page destructor      
    // 함수에 대한 index 를 COMPOUND_PAGE_DTOR 로 설정하여 
    // compound_page_dtor 형 함수포인터 배열 compound_page_dtors 내의 
    // 두번째 함수가 호출 되도록 한다. 
    // (THP,HUGETLBFS 등과는 다름. THP 는 index 3 번, HUGETLBFS 는 2 번임)
 
    set_compound_order(page, order);
    // 첫번째 tail pagedp 할당할 page 의 order 정보 설정
 
    __SetPageHead(page);
    // page flag 에 head page 임을 나타내는 PG_head 설정 
 
    for (i = 1; i <nr_pages; i++) {
        // head page 정보 설정하고, dtor, order 정보 설정했으니 나머지 
        // 기본적 초기화 다해줌        
 
        struct page *p = page + i;
 
        set_page_count(p, 0);
        // _refcount 0 으로 초기화
 
        p->mapping = TAIL_MAPPING;
 
        set_compound_head(p, page);
        // tail page 들이 head page 의 주소를 가리킬 수 있도록 해줌
 
    }
 
    atomic_set(compound_mapcount_ptr(page), -1);
    // 첫번째 tail page 에 compound page 의 mapcount 초기화
 
}

pgrep_compound_page 함수를 통해 compound page 라면 설정되어야 할 값들을 초기화 해준다. 

• set_compound_page_dtor 함수를 통해 compound page 내의 하나의 page 가 free 되거나 mlock 등의 이유로 page attribute 가 변경되어야 할 때, compound page 가 destruct 되어야 하므로 호출될 destructor 함수를 첫번째 tail page 에 설정한다.

• set_compound_order 함수를 통해 첫번째 tail page 에 해당 compound page 의 order 정보를 기록한다. 

• __SetPageHead 함수를 통해 compound page 에서의 head page 임을 나타내는 플래그인 PG_head 를 head page 에 설정한다. 

• compound page 이므로 page 의 수만큼 순회하며 tail page 에 공통적으로 초기화되어야 할 정보들을 추가한다. 

• set_page_count 함수를 통해 compound page 는 하나로 사용되어 head page 의 reference count 를 증가시켜 주었으므로, tail page 들의 reference count 는 0 으로 초기화하며 마찬가지로 하나로 사용되므로 struct address_space 또는 struct anon_vma 용도로 사용되지 않을 mapping 정보를 TAIL_MAPPING 으로 설정해 준다. 

• set_compound_head 함수를 통해 tail page 들이 head page 의 주소를 알 수 있도록 각 tail page 의 struct page 의 compound_head 라는 필드에 head page 로의 주소를 write 해준다. 

• 각 tail page 들의 공통적인 정보를 초기화 해준 후, compound_mapcount_ptr 함수를 통해 compound page 의 mapcount 를 -1 로 초기화해준다. pte 에 mapping 된 수를 나타내는 mapcount 는 compound page 의 경우 struct page 의 mapcount 가 아닌 첫번재 tail page 의 compound_mapcount 필드에 초기화해준다. 

// compound page 의 첫번째 tail page 에  free 될 때 호출될 
// page destructor  함수에 대한 index 설정
static inline void set_compound_page_dtor(struct page *page,
        enum compound_dtor_id compound_dtor)
{   
 
    VM_BUG_ON_PAGE(compound_dtor >= NR_COMPOUND_DTORS, page);
 
    page[1].compound_dtor = compound_dtor;
    // 첫번째 tail page 에 destructor index 정보 저장
}   

set_compound_page_dtor 함수를 통해 struct page 의 destructor 함수를 등록해 준다. 

•  base page 가아닌 compound page 와 같은 형식의 transparent huge page, hugetlbfs 등은 각자의 고유한 destructor 함수를 첫번째 tail page 함수에 등록해 주며, 등록할 destructor 의 종류는 아래와 같이 enum compound_dtor_id 로 전달되며 

 enum compound_dtor_id {
      NULL_COMPOUND_DTOR,
      // NULL 
      COMPOUND_PAGE_DTOR,
      // free_compound_page 의 base page 전환 함수
  #ifdef CONFIG_HUGETLB_PAGE
      HUGETLB_PAGE_DTOR,
      // free_huge_page 의 base page 전환 함수
  #endif
  #ifdef CONFIG_TRANSPARENT_HUGEPAGE
      TRANSHUGE_PAGE_DTOR,
      // free_transhuge_page 의 base page 전환 함수
  #endif
      NR_COMPOUND_DTORS,
  };
 
 
  typedef void compound_page_dtor(struct page *);
  // compound page 형들인 THP, hugetlbfs, compound page 의 경우 각각 
  // 다른 free mechanism 을 가지며 각각 page allocation 될 때 어떤 
  // destructor 함수가 설정될지 page->compound_dtor 에 아래 함수들로의 
  // index 가 설정됨
 
  compound_page_dtor * const compound_page_dtors[] = {
      NULL,
      free_compound_page,
  #ifdef CONFIG_HUGETLB_PAGE
      free_huge_page,
  #endif
  #ifdef CONFIG_TRANSPARENT_HUGEPAGE
      free_transhuge_page,
  #endif
  };

 

  전달된 destructor 함수 index 에 따라 compound_page_dtor 형 함수포인터 배열인 compound_page_dtors[] 에 설정된 함수가 등록된다.

// compound page 의 첫번째 tail page 에 compound page 의 order 정보 설정
static inline void set_compound_order(struct page *page, unsigned int order)
{        
    page[1].compound_order = order;
}        
 
// tail page 들에 head  page 의 주소 설정 및 tail page bit 설정
static __always_inline void set_compound_head(struct page *page, struct page *head)
{   
    WRITE_ONCE(page->compound_head, (unsigned long)head + 1);
    // 여기서 1 추가하는 것은 tail page bit
}   

set_compound_order 함수와 set_compound_head 함수를 통해 compound page 의 tail page 임을 나타내는 방법인 order 정보를 기록하고 head page 의 주소설정 및 0-bit 를 설정하여 초기화 한다. 

< 3.5.6 Freeing Pages >

per-CPU Cache 또는 buddy allocator 로부터 받은 page 를 다시 per-CPU cache, buddy allocator 에게 반환하는 과정은 __free_pages 를 통해 수행된다. 

// order 크기의 struct page 를 할당해제하여 
// buddy 또는 per-CPU cache 에 돌려줌
void __free_pages(struct page *page, unsigned int order)
{           
    if (put_page_testzero(page)) {
    // free 해주려는 page 의 reference count 가 0 인지 검사. 
    // _refcount 를 1 감소한 값이 0이라면 true
    // (현재 page struct 에 대한 사용자가 없는지 검사)
 
        if (order == 0)
            free_hot_cold_page(page, false);
        // page 가 1개라면 per-CPU cache 에 page 돌려주며 
        // 다시 쓰일 가능성 높은 hot 으로 돌려줌
        else
            __free_pages_ok(page, order);
        // page 가 2개 이상이라면 buddy 에게 page 돌려줌
    }
}

__free_pages 함수를 통해 할당해제할 page 를 per-CPU 또는 buddy allocator 에게 반환한다. 

• put_page_testzero 함수를 통해 reference count 를 1 감소한 값이 0 인지 검사하여 0 이라면

• page 1 개 반환일 경우, free_hot_cold_page 함수를 통해 per-CPU cache 에게 page 를 반환한다. 

• page 2 개 이상 반환일 경우, __free_pages_ok 함수를 통해 buddy allocator 에게 반환하는 free_one_page 함수를 호출한다. 

// 할당되어 있던 1 개의 page 를 per-CPU cache 에 돌려줌 
// per-CPU 의 page 가 high 제한을 넘으면 buddy 에게 batch 만큼 돌려줌
void free_hot_cold_page(struct page *page, bool cold)
{
    struct zone *zone = page_zone(page);
    struct per_cpu_pages *pcp;
    unsigned long flags; 
    unsigned long pfn = page_to_pfn(page);
    int migratetype;
   
    if (!free_pcp_prepare(page))
        return;
    // page free 수행 전 page 에 대해 bad page 여부 검사
 
    migratetype = get_pfnblock_migratetype(page, pfn);
    // page 가 속한 page block 의 migrate type 을 가져옴
 
    set_pcppage_migratetype(page, migratetype);
    // struct page 의 index 에 page 가 속해있던 page block 의 
    // migratetype 을 설정
 
    local_irq_save(flags);
    __count_vm_event(PGFREE);
 
    
    if (migratetype >= MIGRATE_PCPTYPES) {
        // per-CPU cache 에서 관리되는 migratetype 의 범위를 벗어난다면 
 
        if (unlikely(is_migrate_isolate(migratetype))) {
            // MIGRATE_ISOLATE 라면 buddy 로 들어가게됨 
 
            free_one_page(zone, page, pfn, 0, migratetype);
 
            goto out;
 
        }   
        // CONFIG_CMA 라면 MIGRATE_MOVABLE 이라고 재설정
 
        migratetype = MIGRATE_MOVABLE;
    }   
   
    pcp = &this_cpu_ptr(zone->pageset)->pcp;
    // per-CPU cache struct 인 struct per_cpu_pages 를 가져와서
 
    if (!cold)
        list_add(&page->lru, &pcp->lists[migratetype]);
        // hot free 일 경우, list 의 앞에 추가해 주고
    else
        list_add_tail(&page->lru, &pcp->lists[migratetype]);
        // cold free 일 경우, list 의 뒤에 추가해 줌 
 
    pcp->count++;
    // 현재 per-CPU 가 가진 free page 수 증가
 
    if (pcp->count >= pcp->high) {
        // free page limit 보다 높게 된다면..
        unsigned long batch = READ_ONCE(pcp->batch);
        // batch 값만큼의 page 를 buddy 에게 돌려줌
        free_pcppages_bulk(zone, batch, pcp);
        pcp->count -= batch;
        // free page 수 감소
    }
 
out:
 
    local_irq_restore(flags);
 
}

free_hot_cold_pages 함수를 통해 1 개의 page 를 per-CPU cache 에 반환하며 per-CPU cache 내의 page 가 설정해둔 제한값인 high

 보다 커지게 되면 batch 만큼의 page 를 buddy 에게 돌려준다. 

• free_pcp_prepare 함수를 통해 per-CPU cache 로 반환하기 전 single bit error, memory corruption 등의 bad page 검사를 수행한다. 

• per-CPU cache 에서 관리하는 migrate type 보다 큰 migrate type 의 반환일 경우(MIGRATE_ISOLATE 또는 MIGRATE_CMMA)

• MIGRATE_ISOLATE 의 page 반환이라면 per-CPU cache 에 주지 않고, free_one_page 함수를 통해 바로 buddy allocator 에게 반환한다.

• MIGRATE_CMA 일 경우, page 를 MIGRATE_MOVABLE 로 반환할 수 있도록 migratetype 을 재설정 한다. 

• per-CPU cache 인 struct per_cpu_pages 를 가져와 hot page 일 경우, list 의 앞에 추가해 주고, cold 일 경우 끝에 추가해 주고 counter 를 증가시킨다. 

• 추가한 결과 per-CPU cache 가 가진 page 의 수가 limit 값인 high 보다 높아진다면 free_pages_bulk 함수를 통해 batch 만큼의 page 를 buddy allocator 에게 돌려준다. 

// per-CPU cache 인 pcp 에서 count 만큼의 page 를 migratetype 별로 
// RR 방식으로 buddy 에게 돌려줌
static void free_pcppages_bulk(struct zone *zone, int count,
                    struct per_cpu_pages *pcp)
{
    int migratetype = 0;
    int batch_free = 0;
    unsigned long nr_scanned;
    bool isolated_pageblocks;
 
    spin_lock(&zone->lock);
 
    isolated_pageblocks = has_isolate_pageblock(zone);
    // zone 에 isolate 된 page block 있는지 여부
 
    nr_scanned = node_page_state(zone->zone_pgdat, NR_PAGES_SCANNED);
    // vm_stat 에서 최근 page reclaim 된 후, scan 된 page 의 수를 알아옴 
 
    if (nr_scanned)
        __mod_node_page_state(zone->zone_pgdat, NR_PAGES_SCANNED, -nr_scanned);
        // scan 된 page 있을 경우.. counter 값을 다시 빼줌.
 
    while (count) {
        // batch 수의 page 를 per-CPU cache 에서 buddy 로 옮기는데 
        // MIGRATE_PCPTYPES 까지의  수 즉 per-CPU 에서 관리되는 migratetype 만큼 
        // round-robin 방식으로 buddy 에게 돌려줌
 
        struct page *page;
        struct list_head *list;
 
        do {
            batch_free++;
 
            if (++migratetype == MIGRATE_PCPTYPES)
                migratetype = 0;
 
            list = &pcp->lists[migratetype];
            // migratetype 에 해당되는 per-CPU cache 를 순회 
            // MIGRATE_MOVABLE 부터 per-CPU cache 가져오고 비어있지 않다면 buddy 로 옮김 
            //              MIGRATE_MOVABLE -> MIGRATE_RECLAIMABLE -> MIGRATE_PCPTYPES=>MIGRATE_UNMOVABLE
            // migratetype         1                  2                      3=>0
 
        } while (list_empty(list));
 
 
        if (batch_free == MIGRATE_PCPTYPES)
            batch_free = count;
 
        do {
            int mt; /* migratetype of the to-be-freed page */
 
            page = list_last_entry(list, struct page, lru);
            // per-CPU list 에서 cold page 를 가져와
            /* must delete as __free_one_page list manipulates */
            list_del(&page->lru);
            // list 에서 제거
            mt = get_pcppage_migratetype(page);
            // 제거할 page 의 migratetype
            /* MIGRATE_ISOLATE page should not go to pcplists */
            VM_BUG_ON_PAGE(is_migrate_isolate(mt), page);
            /* Pageblock could have been isolated meanwhile */
            if (unlikely(isolated_pageblocks))
 
                mt = get_pageblock_migratetype(page);
                // isolated_pageblocks 설정 시, page 가 속한 page block 의 
                // migrate type 을 받아옴
 
            if (bulkfree_pcp_prepare(page))
                continue;
                // CONFIG_DEBUG_VM 설정 시, free 해줄 page 에 대해 
                // bad page 검사 수행
 
            __free_one_page(page, page_to_pfn(page), zone, 0, mt);
            // mt 의 migratetype 인 order-0 짜리 page 를 buddy 로 돌려줌 
 
            trace_mm_page_pcpu_drain(page, 0, mt);
 
        } while (--count &&--batch_free &&!list_empty(list));
 
        // free 해주어야 할 page 가 남아있고, list 가 비어있지 않으며 
        // batch_free 에 따라 이 list에서 계속 free 할지 결정. 
        //  - batch_free : 앞의 list 가 비어있어서 넘아갔다면 현재의 list 가 
        //    비지 않았을 시, 앞의 list 에서 free 해줄 몫까지 free 해줌 
        //  => batch 가 9 개이고, migratetype 이 각각 아래와 같이 free per-CPU page 
        //     있다고 할 시...
        // MIGRATE_UNMOVABLE    : 3 개
        // MIGRATE_MOVABLE      : 6 개 
        // MIGRATE_RECLAIMABLE  : 0 개
        //
        // MIGRATE_UNMOVABLE      | 2  3 | 5    | X   
        // MIGRATE_MOVABLE      1 | 4    | 6  7 | 8  9
        // MIGRATE_RECLAIMABLE  X | X    | X    | X
    }
 
    spin_unlock(&zone->lock);
 
}

free_batches_bulk 함수를 통해 count 만큼의 page 를 pcp 로부터 zone 의 free_area 즉 buddy allocator 에게 반환하며 Round Robin 방식으로 여러 migrate type 의 page 들이 골고루 반환될 수 있도록 한다. 

• zone 에 isolated 된 page 가 있는지 검사 및 vm_stat 의 counter 를 reset 해주고

• buddy 로 반환할 count 만큼 loop 를 돈다.

• count 만큼의 page 를 반환 할 때, per-CPU 에서 관리되는 MIGRATE_MOVABLE, MIGRATE_UNMOVABLE, MIGRATE_RECLAIMABLE 의 세가지 type 의 비어있지 않은 list 를 순서대로 찾는다. 

• batch_free 는 한 migrate type 의 list 에 page 가 없을 시(list 가 비어있게 되면) 다음 migrate type 들이 그전 비어서 반환하지 못하게 되는 migrate type 의 몫까지 반환해 줄 수 있도록 해주는 변수로, list 를 모두 검사 하였는데, MIGRATE_PCPTYPES 와 같게 된다면 추후 그 list 에서 count 값만큼 모두 page 를 반환하도록 해주기 위해 batch_free 값을 반환할 page 수인 count 로 초기화 한다. 

• per-CPU cache 의 list 에서 page 를 받아와 연결고리를 삭제하고, 반환할 page 가 속한 page block 의 migrate type 의 buddy free list 로 반환할 수 있도록 mt 를 먼저 설정한다.

• isolated page block 이 있다면 mt 값을 page block 의 migrate type 이 아니라 그 page 가 속한 migrate type 으로 재설정 한다. 

• bulk_pcp_prepare 함수를 통해 buddy 로 반환할 page 의 bad page 검사를 수행하고

• __free_one_page 함수를 통해 1 개의 order-0 page 를 mt type 의 migrate type 으로 반환한다. 

// buddy allocator 의 core free function 
// migratetype 의 buddy free list 로 반환하며 freebuddy page 가 있다면 
// 상위 order 와 merging 해주어 반환 수행
static inline void __free_one_page(struct page *page,
        unsigned long pfn,
        struct zone *zone, unsigned int order,
        int migratetype)
{
    unsigned long combined_pfn;
    unsigned long uninitialized_var(buddy_pfn);
    // uninitialised 되어있다고 미리 알림. 즉 warning 없앰
    struct page *buddy;
    unsigned int max_order;
 
    max_order = min_t(unsigned int, MAX_ORDER, pageblock_order + 1);
 
    VM_BUG_ON(!zone_is_initialized(zone));
    VM_BUG_ON_PAGE(page->flags &PAGE_FLAGS_CHECK_AT_PREP, page);
    VM_BUG_ON(migratetype == -1);
 
    if (likely(!is_migrate_isolate(migratetype)))
        __mod_zone_freepage_state(zone, 1 <<order, migratetype);
        // MIGRATE_ISOLATE 가 아닌 경우, vm_stat 증가
 
    VM_BUG_ON_PAGE(pfn &((1 <<order) - 1), page);
    VM_BUG_ON_PAGE(bad_range(zone, page), page);
 
continue_merging:
 
    while (order <max_order - 1) {
        buddy_pfn = __find_buddy_pfn(pfn, order);
        // 할당 해제 하려는 order 크기 page 의
        // pfn 에 해당하는 buddy page pfn 찾음
 
        buddy = page + (buddy_pfn - pfn);
        // buddy page frame 에 해당되는 struct page 를 구함
        // (buddy_pfn - pfn 이 음수일 수도 있음) 
        //
        // CONFIG_HOLES_IN_ZONE 이 설정되어 있다면 
        // 즉 ZONE 안에 hole 이 있을 수 있다면
 
        if (!pfn_valid_within(buddy_pfn))
 
            goto done_merging;
            // buddy 가 hole 가지고 있음 더이상 merging 불가능
 
        // hole 있는 page 도 아니니 free page 인지 검사
        if (!page_is_buddy(page, buddy, order))
            goto done_merging;
            // buddy page frame 이 buddy 가 아님 
            // 즉 free page frame 이 아님 더이상 merging 불가능
  
        // buddy page 가 hole 도아니고, buddy allocator 에 있는 free page 임 
        if (page_is_guard(buddy)) {
            // buddy 가 guard page 라면..
            clear_page_guard(zone, buddy, order, migratetype);
            // guard page 나타내는 bit clear 및 
            // buddy 에 기록된 order 정보 0 으로 초기화
        } else {
            // guard page 가 아니라 그냥 buddy page 라면 
            list_del(&buddy->lru);
            // free page list 에서 제거 
            zone->free_area[order].nr_free--;
            // free page list 에서의 free page group 수 감소
            rmv_page_order(buddy);
            // buddy 에 PG_buddy bit clear 및 order 정보 clear  
            // 즉 buddy page 가 buddy allocator 에 속해있다는 flag 들 삭제
        }
 
        combined_pfn = buddy_pfn &pfn;
        // 두 buddy 의 leading page frame 구함
        page = page + (combined_pfn - pfn);
        // leading page frame 의 struct page 구함
        pfn = combined_pfn;
 
        order++;
        // 합쳐주기 위해 order 증가
    }
 
    if (max_order <MAX_ORDER) {
        
        if (unlikely(has_isolate_pageblock(zone))) {
            // isolated 된 pageblock 이 있다면.. pass
            int buddy_mt;
 
            buddy_pfn = __find_buddy_pfn(pfn, order);
            buddy = page + (buddy_pfn - pfn);
            buddy_mt = get_pageblock_migratetype(buddy);
 
            if (migratetype != buddy_mt
 
                    &&(is_migrate_isolate(migratetype) ||
 
                        is_migrate_isolate(buddy_mt)))
 
                goto done_merging;
        }
 
        max_order++;
 
        goto continue_merging;
 
    }
 
 
done_merging:
 
    set_page_order(page, order);
    // 증가된 새로운 order 정보 기록하고.
   
 
    if ((order <MAX_ORDER-2) &&pfn_valid_within(buddy_pfn)) {
 
        struct page *higher_page, *higher_buddy;
        combined_pfn = buddy_pfn &pfn;
        higher_page = page + (combined_pfn - pfn);
        buddy_pfn = __find_buddy_pfn(combined_pfn, order + 1);
        higher_buddy = higher_page + (buddy_pfn - combined_pfn);
 
        if (pfn_valid_within(buddy_pfn) &&
            page_is_buddy(higher_page, higher_buddy, order + 1)) {
            list_add_tail(&page->lru,
                &zone->free_area[order].free_list[migratetype]);
            // 상위에 또 합칠 수 있는 page 가 발견된면 cold page 로 추가
 
            goto out;
        }
    }
 
    list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
    // hot page 로 free list 에 page 추가
 
out:
 
    zone->free_area[order].nr_free++;
 
}

__free_one_page 함수를 통해 page 반환 시, order 가 1 이상일 경우, 또는 per-CPU cache 에서 buddy 로 page 를 반환하는 경우에 대해 반환할 migratetype 의 order 크기 page 를 free buddy page 여부를 확인하여 merging 해주어 가능한 큰 연속적인 free page list 로 구성하여 buddy 에 반환해준다.

• 반환할 order 에 MAX_ORDER 는 merging 해줄 필요가 없으므로 order 최대값 - 1 까지 증가하며 합칠 수 있는 buddy page frame 이 있는지 확인한다. 

• __find_buddy_pfn 함수를 통해 반환할 pfn 에 대한 buddy page frame 을 구해와 그에 해당하는 struct page 를 설정한다. 

• zone 내에 hole 이 있을 경우, buddy page frmae 이 그 hole 에 해당한다면 merging 해줄 수 없으므로 더이상 merging 검사하지 않는다. 

• page_is_buddy 함수를 통해 buddy page 가 할당해제 요청온 page 와 같은 order 크기의 free page 이며, PG_buddy 가 설정되어 buddy allocator 의 free page 가 맞는지 확인한다. buddy page 가 아니거나 같은 order 가 아니면 더이상 merging 검사하지 않는다.

• page_is_guard 함수를 통해 buddy page 가 guard page 일 경우, guard page bit 를 clear 해주고 guard page 가 아니라 그냥 free buddy page 일 경우, buddy 의 free list 에서 삭제하고, 해당 free list 의 counter 감소 해주며, buddy page 가 이제 page 와 합쳐질 것이므로 order 정보 및 PG_buddy 를 clear 해준다. 

• 또한 상위 order 에 대해 검사 가능한 경우, 한번더 검사를 수행하여 또 merging 이 가능하면 buddy 의 cold page 로 추가해 주어 list 의 끝에 추가해 주고, 불가능하다면 hot page 로 buddy list 에 추가해 준다. 

// page_pfn 에 대한 order 단위 buddy page frame 을 구하는 함수. 
// XOR 연산을 활용하여 buddy 구함
//  - 나머지 bit 그대로 두고 order 크기의 bit 가 설정되어 있다면 
//    꺼주고 설정되어 있지 않다면 켜줌으로써 buddy 를 구함 
//    e.g. 
//         order 1 0000 0001 에 대해 on/off 
//         pfn 0  ... 0000 0000 -> buddy_pfn 1  ... 0000 0001
//         pfn 1  ... 0000 0001 -> buddy_pfn 0  ... 0000 0000
//  
//         order 3 0000 1000 에 대해 on/off
//         pfn 16 ... 0001 0000 -> buddy_pfn 24 ... 0001 1000
//         pfn 24 ... 0001 1000 -> buddy_pfn 16 ... 0001 0000
//      
 
static inline unsigned long
__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
{   
    return page_pfn ^ (1 <<order);
    // order 위치의 bit 를 set/unset 하여 buddy pfn 구함
}     

      

__find_buddy_pfn 함수에서는 order 에 맞는 bit 를 set/unset 해줌으로써 page 에 대한 buddy 를 찾을 수 있다. 

 

## 3.5.7 Allocation of Discontiguous Pages in the Kernel

## 3.5.8 Kernel Mappings