Week 2 - Buddy System

Posted on Edited on In

本文章涵蓋基礎 Buddy system 和記憶體管理。

Memory management

Linux 將記憶體分成 node, zone, page 三層次管理。
da8c137666f4903d1a64a23796a50076.png

在 NUMA 架構下，不同 NUMA node 用 QPI 等方式交換資料，由 Linux node 層次負責。
截圖 2025-02-26 上午10.07.09.png

Zone 是 Linux 相容不同系統和記憶體大小，開發出來的記憶體分區機制。

  • ZONE_DMA
    部分 ISA 設備只支援 24-bit 位址線，僅能存取 0-16MB 的記憶體，因此 kernel 畫出一片區域給這些設備使用。
  • ZONE_DMA32
    供 32-bit PCI 設備使用，道理與 ZONE_DMA 相同。
  • ZONE_NORMAL
    存放 kernel 可直接存取的記憶體，像是 stack, kmalloc 分配的區域, page tables 等。
    在 32-bit 系統上，會留 128MB 給 I/O 記憶體和 kernel 結構，因此只能映射 16MB-896MB 的物理記憶體。
  • ZONE_HIGHMEM
    記憶體超過 4GB 時，32-bit kernel 無法直接映射高於 896MB 的部分，只能透過額外的方法存取。64-bit 無此 zone。
  • ZONE_MOVABLE
    允許被遷移，用於防止物理 fragmentation。
  • ZONE_DEVICE
    供特殊記憶體使用。

截圖 2025-02-26 上午10.09.39.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
struct zone {
    /* Read-mostly fields */

    // zone 的「水位線」,系統啟動時計算 WMARK_MIN, WMARK_LOW, WMARK_HIGH
    // kswapd 做 swap 時會用到
    unsigned long _watermark[NR_WMARK];
    unsigned long watermark_boost;

    unsigned long nr_reserved_highatomic;

    // 預留物理記憶體
    long lowmem_reserve[MAX_NR_ZONES];

#ifdef CONFIG_NUMA
    int node; // 指向所屬的 node
#endif
    struct pglist_data    *zone_pgdat;
    struct per_cpu_pageset __percpu *pageset; // 每個 CPU 維護一個 page list
    int pageset_high;
    int pageset_batch;

#ifndef CONFIG_SPARSEMEM
    unsigned long        *pageblock_flags;
#endif /* CONFIG_SPARSEMEM */

    unsigned long        zone_start_pfn;

    atomic_long_t        managed_pages;
    unsigned long        spanned_pages;
    unsigned long        present_pages;

    const char        *name;

#ifdef CONFIG_MEMORY_ISOLATION
    unsigned long        nr_isolate_pageblock;
#endif

#ifdef CONFIG_MEMORY_HOTPLUG
    seqlock_t        span_seqlock;
#endif

    int initialized;

    ZONE_PADDING(_pad1_)

    struct free_area    free_area[MAX_ORDER]; // 空閒記憶體，用於實現 buddy system

    unsigned long        flags;

    spinlock_t        lock;

    ZONE_PADDING(_pad2_)

    unsigned long percpu_drift_mark;

#if defined CONFIG_COMPACTION || defined CONFIG_CMA
    unsigned long        compact_cached_free_pfn;
    unsigned long        compact_cached_migrate_pfn[ASYNC_AND_SYNC];
    unsigned long        compact_init_migrate_pfn;
    unsigned long        compact_init_free_pfn;
#endif

#ifdef CONFIG_COMPACTION
    unsigned int        compact_considered;
    unsigned int        compact_defer_shift;
    int            compact_order_failed;
#endif

#if defined CONFIG_COMPACTION || defined CONFIG_CMA
    bool            compact_blockskip_flush;
#endif

    bool            contiguous;

    ZONE_PADDING(_pad3_)
    atomic_long_t        vm_stat[NR_VM_ZONE_STAT_ITEMS];
    atomic_long_t        vm_numa_stat[NR_VM_NUMA_STAT_ITEMS];
} ____cacheline_internodealigned_in_smp;

2808745cef57649ccaea0fae074ba279.png

struct page 為了節省空間，使用大量 union 結構。

  • index 在 virtual address 的偏移量
  • private 用於管理此 page 的資料，像是 buddy system
  • _mapcount 該 page 被多少 process 映射
  • _refcount 該 page 現正被多少 process 使用
  • lru 與 zone->__lruvec 組成 link list

Buddy system

buddy system 分配記憶體都以 page 為單位，可申請 2^n page 大小的記憶體。
申請和釋放時，buddy system 維護 free_area 的結構，進行 page 拆分或合併。
/proc/buddyinfo 得知各 order 中 free page 數。
sOwdI5YMNUjLSib.png

alloc_pages 可向 buddy system 申請記憶體，order 表示區塊大小。

1
static inline struct page *alloc_pages(gfp_t gfp_mask, unsigned int order)

__get_free_pages 多了呼叫 page_address 得到 virtual address 的動作。

  • __GFP_DMA 從 ZONE_DMA 分配
  • __GFP_MOVABLE 記憶體調整時可以遷移或回收 page
  • __GFP_ATOMIC 允許分配最低 watermark 的預留區域
  • __GFP_ZERO 內容填充為 0
  • __GFP_KERNEL 分配時可被 block

若有 GFP_THISNODE 限制在 local node 分配，則使用默認分配策略。
若當前策略是 MPOL_INTERLEAVE，就必須跨 node 分配，否則走 UMA 照常分配。
4c05d7cef091c9e36813f0d53ede13d0.png

__alloc_page_nodemask 分配又分 fast path 和 slow path，fast path 從 buddy system 抓 page，slow path 會進行 swap, memory compaction 等操作。
free_area 在 zone 結構底下，free_list 是好幾個 link list，用 page->lru 串起來，一個 page 不會同時在 lru 和 buddy system。

1
2
3
4
struct free_area {
	struct list_head	free_list[MIGRATE_TYPES];
	unsigned long		nr_free;
};

migration 是減少物理 external fragmentation 機制，不同 migrate type 代表 migration 可做的動作，free_area 為每個 type 創建一個 free_list。

  • MIGRATE_UNMOVABLE 不能移動
  • MIGRATE_MOVABLE 可隨意移動
  • MIGRATE_RECLAIMABLE 不能直接移動，但可以刪除，例如映射自文件的 page
  • MIGRATE_PCPTYPES 遷移僅限於同一節點內
  • MIGRATE_ISOLATE 不能從該 list 分配頁面，用於跨 NUMA 節點進行移動

釋放時用 free_pages。

參考資料