sev1n75's Tech Blog

路漫漫其修远兮，吾将上下而求索

Linux-Kernel 学习笔记

  1. | 0 | 前言
  2. | 1 | Understanding the Linux Virtual Memory Manager, online book by Mel Gorman, 2007.
    1. | 1.1 | 组织物理内存(1-4.5章)
    2. | 1.2 | 缺页异常(4.6章)
    3. | 1.3 | 内存分配(5-8章)
    4. | 1.4 | 其他(9-13章)
  3. | 2 | Kernel Exploring, richardweiyang
    1. | 2.1 | 内核加载全流程
    2. | 2.2 | 内存管理
      1. | 2.2.1 | 内核页表成长记
      2. | 2.2.2 | 自底向上话内存
      3. | 2.2.3 | 虚拟内存空间
  4. | 3 | arttnba3 -【OS.0x02-0x04】Linux 内核内存管理-页、区、节点，Buddy System，Slub Allocator

| 0 | 前言

Linux Kernel 学习笔记。

✅ 最近一次更新：2024-5-8

Todo:(以后遇到了再详细补充到笔记里)

| 1 | Understanding the Linux Virtual Memory Manager, online book by Mel Gorman, 2007.

这本书主要介绍 i386 架构下的 v2.4.22 内核，比较久远。所以主要是从宏观上整体熟悉 Linux 内核管理内存的基本流程即可，没必要在老版本纠结细节。当需要熟悉细节内容(通常是目前最新的内核)时，有了整体的把握能够更轻松。（完全不会）

当然这么老且经典的书应该是有翻译的 🔗 翻译版。

大佬的笔记 🔗 linux-gorman-book-notes, Lorenzo Stoakes。

第一章简单介绍了 Configure&Build，Managing the Source，Browsing the Code，三个方面。

现在的方法和十几年前有一些区别：

  • 配置和编译：以前使用 autoconf 工具加上 configure 脚本。现在通过基于 Makefile 的 Kconfig + Kbuild。
  • 管理源码：这本书应该是 03，04 年写的，Linus 还没开发 Git。书上介绍了 Diff+Patch。现在基本使用 Git 管理源码。
  • 浏览代码：书上推荐 vim+ctags，或者 LXR。人生苦短，我用 neovim+telescope+ctags (make cscope/tags 即可生成 cscope/ctags 文件)。在线网站 elixir bootlin

后续内容就主要看 Lorenzo Stoakes 的笔记了。重点记录宏观的内容，和自己的理解，细节部分比如某些结构体域的意义之类的就没必要照抄了，原文里都有。

| 1.1 | 组织物理内存(1-4.5章)

2.3 zone 初始化: zone_size_init()，之前还要调用 setup_memory() 计算 zone 的大小

1
2
3
4
5
6
7
8
9
// i386
start_kernel()
    setup_arch()
        setup_memory() 
        paging_init()
            pagetable_init()
            zone_sizes_init()
                free_area_init()
                    free_area_init_core()

2.6 page 到 zone 的映射关系

1
2
3
// linclude/linux/mm.h:344 set_page_zone()
page->flags &= ~(~0UL << ZONE_SHIFT);   // 留下了低 ZONE_SHIFT 给 flag
page->flags |= zone_num << ZONE_SHIFT;  // 高位存放 zone_num

3.2 描述页表项(Page Tabel Entry)

  • 两个需要注意的标志(flag):

    • _PAGE_PRESENT: 表示该页仍在内存中，没有被换出(swapped out)。
    • _PAGE_PROTNONE: 表示 non-present 页，用来区别被换出的页。

  • pte_present(x): 当该页被换出时返回0。(存在 _PAGE_PRESENT 没设置而 _PAGE_PROTNONE 被设置的情况吗)

3.6 分页(paging)初始化: pagetable_init()

  • arch/i386/kernel/head.S:44 startup_32 初始化页表，包含两个页(pg0, pg1)
  • 调用 pagetable_init()（调用链见上面 2.3 节笔记） 初始化访问 ZONE_DMA 和 ZONE_NORMAL 所需的页表。

| 1.2 | 缺页异常(4.6章)

  • 有两种：严重(major)和轻微(miner)。当必须从磁盘读数据的时缺页错误是严重(major)的错误。

  • 缺页错误的几种情况：

    序号. 程度 - 描述 - 解决方法

    1. 轻微 - 地址在内存区域(memory region/VMA)有效，但页面未分配 - 分配页。
    2. 轻微 - 地址在内存区域无效，但位于可扩展区域（如栈）旁边 - 扩展区域并分配页。
    3. 轻微 - 页面已被换出(swapped out)，但存在于交换缓存(swap cache)中 - 在进程页表中重新建立页面并删除对该缓存的引用计数(ref count)。
    4. 严重 - 页面交换到后备存储(backing storage)中 - 找到该页，然后从磁盘读出来。
    5. 轻微 - 写一个只读的页 - 如果该页是 COW 页，则复制然后标记为可写分配给进程，否则发送 SIGSEGV。
    6. 错误 - 地址所在内存区域无效或进程无权访问 - 发送 SIGSEGV。
    7. 轻微 - 异常地址位于内核地址空间 - 如在 vmalloc 区域，则当前进程页表将根据 init_mm 保存的页表进行更新。同时这是有效的内核缺页异常。
    8. 错误 - 在内核模式下，缺页地址位于用户地址空间 - 这不应该发生，如果发生意味着内核代码未正确使用来自从用户空间的地址从而导致缺页异常。需要非常严肃地对待。

处理缺页异常

  • 缺页异常的顶层函数(page fault handler) do_page_fault():

    负责确定发生了哪种类型的异常，判断正确性(比如如果内存区域无效，但是符合情况 2.，则会调用 expand_stack(vma, address))然后调用 handle_mm_fault()。

    依赖不同的 CPU 架构。

    🔗 函数处理流程图

  • handel_mm_fault()

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    handle_mm_fault() --------> handel_pte_fault()
                                     |
                                    /|\
                                   / | \
                                  /  |  \
                                 +   |   \
                                 |   |    \
                                 v   |     \
                       do_no_page()  |      \
                                     v       +
                          do_swap_page()     | 
                                             v
                                   do_wp_page()

    handel_pte_fault() 解决了以下几种异常：

    • 页面不存在: do_no_page()
      • 1. 6. 7. 8.
    • 页面被换出: do_swap_page()
      • 3. 4.
    • 页面不可读: do_wp_page()
      • 5. 6.
    • 当页面在内存中且可读时也会遇到错误，这种情况发生在某些没有 3 级页表的体系结构中

  • 注意：

    • 内核通过该区域的 VMA 是否可写判断 COW 页面，无需 PTE_C 标识位(flag)
    • VMA 可以通过 v_op 注册 nopage() 特殊的处理函数。默认 do_anonymous_page()

| 1.3 | 内存分配(5-8章)

5. Boot Memory Allocator

  • 在内核启动阶段，内存还没有被初始化，同时其他的内存分配器也需要一些内存来初始化自己，所以 Boot Memory Allocator 就是负责在内核启动的早期简单分配内存的。

    但是这个机制大概在 v4 版本的内核被 Memblock 技术取代了。🔗 参考链接

6. Buddy System 物理内存分配

  • 分配(alloc): __alloc_pages()
  • 释放(free): __free_pages_ok()
  • GFP(Get Free Page) Flags:
    • 决定 allocator 和 kswapd 在分配和释放页的行为。
    • GFP 分为三组：zone modifiers, action modifiers, high-level action modifiers (低级 action modifiers 的组合)

7. 虚拟连续但物理非连续内存分配

  • ____VMALLOC_RESERVE = 128 << 20 表示 vmalloc() 能分配的最小大小。
  • 由于 vmalloc() 的特性限制，其在内核中很少使用。
  • 通过 vm_struct 结构体表示

8. Slab Allocator 缓存层

| 1.4 | 其他(9-13章)

后补

  • 9 Highmem 管理

    64 位不涉及

  • 10-11 换页

  • 12 共享内存虚拟文件系统

  • 13 内存不足(OOM)管理

| 2 | Kernel Exploring, richardweiyang

| 2.1 | 内核加载全流程

  • Boot loader 把压缩内核镜像（bzImage）加载到内核

    Boot loader 按照协议把 bzImage 加载到内存，分为（setup.bin, vmlinux.bin）两部分。

    不同的 Boot loader 启动时，会动态的向 bzImage 的 Type_of_loader 字段写入信息(0xTV)，参考内核文档。

    加载后控制流到 arch/x86/boot/header.S 中的 _start。

  • 从实模式进入保护模式

    _start: 从 start_of_setup: 标号后完成设置段寄存器、设置堆和栈、设置 .bss 段，然后跳转到 main 函数 calll main，跳转到 arch/x86/boot/main.c 的 main()。

    main(): 将启动参数拷贝到”zeropage”，控制台初始化，堆初始化，检查CPU类型，内存分布侦测···，最后调用 go_to_protected_mode()，跳转 arch/x86/boot/compressed/head_64.S 中的 startup_32。

  • 过渡到 64 位模式

    startup_32: 做一些包括进入 64 位的准备工作在内的初始化后，跳转 startup_64。

  • 解压 bzImage（bzImage => vmlinux)

    startup_64 调用 extract_kernel 解压新内核，返回 vmlinux 入口地址，保存在 rax 中，然后 jmp *%rax。

    在没有配置 CONFIG_RELOCATABLE 的时候，我们目标将把压缩的内核解压缩到 CONFIG_PHYSICAL_START 这个地址。这个地址的默认配置是 0x1000000。

    0x1000000 即 ehdr.e_entry，通过 readelf -h vmlinux 查看。

  • 补充：加载之后

    vmlinux 入口对应 arch/x86/kernel/head_64.S 的 startup_64。

    startup_64 最后 jmp 0x1f，根据调试会跳转到 secondary_startup_64 中间位置。在设置好页表后 jmp *%rax 跳转到虚拟地址（如0xffffffff810000bf），实际上就是下一行指令（如物理地址 0x10000bf），相当于继续执行，只是设置了 cr3 寄存器，开始分页。

    最后跳转到 initial_code 即 x86_64_start_kernel。

    1
    2
    3
    4
    5
    6
    7
    // v6.2 arch/x86/kernel/head_64.S
    355 movq  initial_code(%rip), %rax
    356 pushq $__KERNEL_CS  # set correct cs
    357 pushq %rax    # target address in negative space
    358 lretq
    //...
    418 SYM_DATA(initial_code,  .quad x86_64_start_kernel)

    剩下的内容留在初始化时再细看。

| 2.2 | 内存管理

| 2.2.1 | 内核页表成长记

后补

| 2.2.2 | 自底向上话内存

e820 从硬件获取内存分布

e820 是 x86 平台用于检测物理内存分布的硬件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// https://richardweiyang-2.gitbook.io/kernel-exploring/nei-cun-guan-li/00-memory_a_bottom_up_view/01-e820_retrieve_memory_from_hw
/* Retrieve the e820 table from BIOS */
main(), arch/x86/boot/main.c, called from arch/x86/boot/header.S
      detect_memory()
           detect_memory_e820(), save bios info to boot_params.e820_entries

/* store and sort e820 table to kernel area */
start_kernel()
      setup_arch()
           e820__memory_setup(),
                 x86_init.resources.memory_setup() -> e820__memory_setup_default(), store and sort e820 table
                 e820__print_table()
           e820__reserve_setup_data();
           e820__finish_early_params();
           e820_add_kernel_range();
           e820__memblock_setup();

memblock 分配初期内存

SPARSEMEM 内存模型

我的理解，内存模型就是定义了 struct page 结构体以何种方式保存，用于映射 page 结构体与物理内存机制。

在没有使用 SPARSEMEM 前，page 结构体是一个连续数组。也就是说如果整个系统最大会支持多少内存，都得预先分配好空间。哪怕中间有一段物理内存是空的，也得留着。

SPARSEMEM 引入 section 概念，x86_64 平台上，section 大小是 (2^27) = 128M。也就是把 2^(27-12）个 page 结构体放在一起保存。

内核通过 __pfn_to_page() __page_to_pfn() 两个宏进行转化。

NUMA 信息获取

Node-Zone-Page 结构

Buddy system 

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
// https://richardweiyang-2.gitbook.io/kernel-exploring/nei-cun-guan-li/00-memory_a_bottom_up_view/05-node_zone_page
      struct zone
      +------------------------------+      The buddy system
      |free_area[MAX_ORDER]  0...10  |
      |   (struct free_area)         |
      |   +--------------------------+
      |   |nr_free                   |  number of available pages
      |   |(unsigned long)           |  in this zone
      |   |                          |
      |   +--------------------------+
      |   |                          |           free_area[0]
      |   |free_list[MIGRATE_TYPES]  |  Order0   +-----------------------+
      |   |(struct list_head)        |  Pages    |free_list              |
      |   |                          |           |  (struct list_head)   |
      |   | enum migratetype(        |           +-----------------------+
      |   | include/linux/mmzone.h)  |
      |   |                          |           free_area[1]
      |   |                          |  Order1   +-----------------------+
      |   |                          |  Pages    |free_list              |
      |   |                          |           |  (struct list_head)   |
      |   |                          |           +-----------------------+
      |   |                          |
      |   |                          |              .
      |   |                          |              .
      |   |                          |              .
      |   |                          |
      |   |                          |
      |   |                          |           free_area[10]
      |   |                          |  Order10  +-----------------------+
      |   |                          |  Pages    |free_list              |
      |   |                          |           |  (struct list_head)   |
      |   |                          |           +-----------------------+
      |   |                          |
      +---+--------------------------+
  • Compound Page

GFP (include/linux/gfp_types.h)，基本可以分成下面三类：

  • ___GFP_xxx: Plain integer GFP bitmasks.

  • __GFP_xxx: 基本上就是对 ___GFP_xxx 的包装。

    1
    #define __GFP_ATOMIC	((__force gfp_t)___GFP_ATOMIC)

  • GFP_xxx: 对 __GFP_xxx 的组合，用于表示更通常的情况。

per_cpu_pageset

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
// include/linux/mmzone.h

/*
* @count: 链表里还剩的页
* @high: 链表保存的页数量的最大值
* @batch: 如果没有页了，从 buddy 里取 batch 个页
*/
struct per_cpu_pages {
	spinlock_t lock;	/* Protects lists field */
	int count;		/* number of pages in the list */
	int high;		/* high watermark, emptying needed */
	int high_min;		/* min high watermark */
	int high_max;		/* max high watermark */
	int batch;		/* chunk size for buddy add/remove */
	u8 flags;		/* protected by pcp->lock */
	u8 alloc_factor;	/* batch scaling factor during allocate */
#ifdef CONFIG_NUMA
	u8 expire;		/* When 0, remote pagesets are drained */
#endif
	short free_count;	/* consecutive free count */

	/* Lists of pages, one per migrate type stored on the pcp-lists */
	struct list_head lists[NR_PCP_LISTS];
} ____cacheline_aligned_in_smp;

//...

struct zone {
//...
    struct per_cpu_pages	__percpu *per_cpu_pageset;  // 注意这里是一个指针，结构体保存在其他地方
    struct per_cpu_zonestat	__percpu *per_cpu_zonestats;
//...
}

slub 的理念

  • 分类

  • 预取

| 2.2.3 | 虚拟内存空间

后补

| 3 | arttnba3 -【OS.0x02-0x04】Linux 内核内存管理-页、区、节点，Buddy System，Slub Allocator

后补

讲的太细节了，感觉不太适合刚开始看。

a3 前两篇用的 v5.11 版本的内核，后一篇用的 v6.2。

Linux KernelOSMemory Managementnote