Garden of John

lab 2

12分钟阅读

buddy system :分离适配的一个特例，每个大小类都是2的幂。

  • 基本思路：假设一个堆大小2^m个字，为每一个块大小为2^k维护一个分离空闲链表。请求块大小向上舍入到最接近的2的幂。
  • 最开始只有一个大小为2^m个字的空闲块。
  • 优点：快速合并和快速搜索
  • 缺点：要求块大小为2的幂导致显著的内存碎片。

-检查一个数x是否是2的幂。在计算机科学中，2的幂的数在二进制表示中只有一个1，其余位都是0。例如，2的幂有1（1）、2（10）、4（100）、8（1000）等。

现在，看看宏的逻辑：!((x) & ((x)-1))。

  • define MAX(a,b)((a)>(b)?(a):(b))在宏定义中为什么每个变量都要加上括号呢？
  • 在C/C++宏定义中，由于宏展开是简单的文本替换，如果不加括号，可能会导致运算符优先级问题，从而产生意想不到的结果。
    以MAX(a,b)为例，如果定义为 define MAX(a,b) a>b?a:b，那么当在表达式中使用宏时，可能会因为运算符优先级而错误计算。
    例如：考虑 MAX(1,2) + 3，展开后为 1>2?1:2+3，这相当于 1>2?1:(2+3)，因为加法运算符的优先级高于条件运算符。所以结果是5，而不是我们期望的(1>2?1:2)+3=3。
    同样，如果参数是表达式，比如 MAX(i++, j++)，展开后为 i++>j++?i++:j++，这会导致变量自增两次，而不是一次。

因此，为了安全，每个参数和整个表达式都应该用括号括起来。
正确的定义： define MAX(a,b) ((a) > (b) ? (a) : (b))

这样，MAX(1,2)+3 展开为 ((1) > (2) ? (1) : (2)) + 3，条件运算符的优先级较低，所以先计算条件表达式，然后再加3，结果正确。

但是，即使这样，仍然不能避免参数多次求值的问题（例如，当参数是自增表达式时）。因此，在C++中，通常建议使用内联函数来代替宏，以避免此类问题。

总结：加括号是为了确保宏展开后的表达式运算顺序与预期一致，防止因运算符优先级导致的错误。

  • . 数学证明

对于任意正整数 n，设其最高位1在第 k 位，那么：

  • 执行 n |= n >> 1 后，第 k-1 位变成1

  • 执行 n |= n >> 2 后，第 k-2 到 k-3 位变成1

  • 以此类推，经过 log₂(字长) 次操作后，第0到第k位全部变成1

最后 n + 1 就得到了 2^(k+1)，即大于原数的最小2的幂。

命令./start_qemu4.sh

  • 哭，docker 配置
  • docker start -ai qemu4

  • entry.s做了什么

    • 保存硬件传入的hartid和dtb物理地址到全局符号，共c代码阅读。
    • 启用sv39分页，将预制的三级页表的物理页号写入satp,并使用Sfence,vma1刷新
    • 切换到高地址虚拟空间，设置内核栈指针sp
    • 跳转到C入口
    • 数据段提供：内核引导栈空间 预制三级页表内存 用于保存boot_hartid/boot_dtb的全局变量

  • 硬件进入引导入口 → entry.S:kern_entry 执行低级初始化。

  • 准备虚拟内存环境：

  • 使用预制的 1GiB 大页映射：将高半地址 0xffffffffc0000000 段映射到物理 0x80000000（OpenSBI 后的 DRAM 起点），方便“高半内核”直接访问内核与物理内存。

  • 写 satp 为 Sv39 模式 + 预制页表物理页号，并刷新 TLB。

  • 切栈并跳转到 kern_init()（C 世界）：

  • C 端清 BSS、解析 DTB（获取实际物理内存布局）、初始化控制台、初始化物理内存管理（选择策略并建自由链/伙伴树）、自检。

  • 有关页表：

    • 每级 512 项（4KiB/8B）。

    • 叶子判断：V=1 且 (R|W|X)!=0。

page_init函数

为什么首地址向上，尾地址向下？不理解

Thoughtfor 3s

[MODE: RESEARCH]

因为要保证交给物理页分配器的区间正好由“完整页框”组成，既不覆盖已占用的碎片，也不越界到无效区域。设区间是半开区间 [begin, end)：

  • 首地址向上对齐 ROUNDUP(begin, PGSIZE)

  • 若 begin 落在某页的中间，页前半部分可能已被“内核镜像/元数据”占用，不能把这页剩余部分当作空闲整页使用，所以必须跳到“下一页的起点”。

  • 尾地址向下对齐 ROUNDDOWN(end, PGSIZE)

  • 若 end 落在某页的中间，这一页后半部分不足一整页，不能算作一个可分配页框，必须截断到“这一页的起点”，排除尾部碎片。

高地址 →
┌───────────────────────────────────────────┐
│ 内核镜像 (.text .rodata .data .bss ... ) │
│                 直到符号 end              │
└─────────────── end ───────────────────────┘
                │
                │  向上页对齐 ROUNDUP(end, PGSIZE)
                ▼
          pages (VA)  ← 页描述符数组的起始虚拟地址
                │
                │  数量 = (npage - nbase)
                │  总字节 = sizeof(struct Page) * (npage - nbase)
                ▼
pages + sizeof(Page)*(npage-nbase) (VA)  ← 元数据数组末尾的“下一个地址”
                │
                └─ 这还在 VA，需要用 PADDR 转为物理地址
                
                
低地址 →
┌───────────────────────────────────────────┐
│    物理内存中被内核镜像占用的区域         │  (映射到上图“内核镜像”)
└───────────────────────────────────────────┘
┌───────────────────────────────────────────┐
│   物理中存放 struct Page[] 数组的区域     │  (映射到上图 pages..pages+size)
└───────────────────────────────────────────┘
↑
│
freemem = PADDR(pages + sizeof(Page)*(npage-nbase))  ← 元数据之后的第一个可用物理地址
│
└─ 接下来会对齐到页边界：mem_begin = ROUNDUP(freemem, PGSIZE)

Buddy System 的核心机制

1. 数据结构基础

Buddy System 使用完全二叉树而不是链表：

  • 树节点：每个节点记录”该子树中最大可用块的大小”

  • 数组存储：用数组 buddy_longest[2*buddy_size-1] 存储二叉树

  • 索引关系：节点 i 的左孩子是 2i+1，右孩子是 2i+2

2. 内存布局图

 
Apply to lab2.md
 
物理内存布局：
 
┌─────────────────────────────────────────────────────────────┐
 
│                   原始内存区域 base..base+n                  │
 
├─────────────────────────────────────────────────────────────┤
 
│  元数据页区域    │        可分配数据区域                      │
 
│ meta_base       │        buddy_base_page                     │
 
│ (存储longest树) │        (实际可分配内存)                     │
 
│                 │                                            │
 
│ buddy_longest[] │  [块0] [块1] [块2] [块3] [块4] [块5] [块6] │
 
│ (2*buddy_size-1)│                                            │
 
└─────────────────────────────────────────────────────────────┘

3. 伙伴树结构图

 
Apply to lab2.md
 
完全二叉树结构 (buddy_size = 4 为例)：
 
                    根节点(0)
 
                   longest[0] = 4
 
                  /              \
 
                 /                \
 
           左子树(1)              右子树(2)
 
         longest[1] = 2        longest[2] = 2
 
         /          \           /          \
 
        /            \         /            \
 
   叶节点(3)      叶节点(4)  叶节点(5)    叶节点(6)
 
longest[3]=1   longest[4]=1 longest[5]=1 longest[6]=1
 
对应的内存块：
 
┌─────┬─────┬─────┬─────┐
 
│块0  │块1  │块2  │块3  │
 
│1页  │1页  │1页  │1页  │
 
└─────┴─────┴─────┴─────┘

4. 分配过程图解

请求分配 3 页（实际分配 4 页）：

 
Apply to lab2.md
 
步骤1: 向上取整
 
请求: 3页 → 实际分配: 4页 (2^2)
 
步骤2: 树中查找路径
 
根节点(0): longest[0]=4 >= 4 ✓
 
├─ 左子树(1): longest[1]=2 < 4 ✗
 
└─ 右子树(2): longest[2]=2 < 4 ✗
 
   但右子树是唯一选择，继续向下
 
步骤3: 到达叶节点
 
最终到达叶节点(6)，对应块3
 
标记: longest[6] = 0 (占用)
 
步骤4: 更新祖先
 
向上回溯更新所有祖先节点的longest值

5. 释放过程图解

释放块3（4页）：

 
Apply to lab2.md
 
步骤1: 定位节点
 
通过偏移计算找到叶节点(6)
 
步骤2: 标记空闲
 
longest[6] = 1 (空闲)
 
步骤3: 向上合并
 
检查父节点(2)的左右子树：
 
- 左子树(5): longest[5] = 1
 
- 右子树(6): longest[6] = 1
 
- 相等且都为空闲 → 合并！
 
- longest[2] = 2 (合并为2页块)
 
继续向上检查根节点(0)

6. 模块架构图

 
 
Buddy System 模块架构：
 
┌─────────────────────────────────────────────────────────────┐
 
│                    Buddy System 模块                        │
 
├─────────────────────────────────────────────────────────────┤
 
│  全局状态管理                                                │
 
│  ┌─────────────────────────────────────────────────────────┐ │
 
│  │ buddy_base_page: 可分配区域基址                         │ │
 
│  │ buddy_longest:   伙伴树数组指针                         │ │
 
│  │ buddy_size:      管理总页数(2的幂)                      │ │
 
│  │ nr_free:         当前空闲页数                            │ │
 
│  └─────────────────────────────────────────────────────────┘ │
 
├─────────────────────────────────────────────────────────────┤
 
│  工具函数层                                                  │
 
│  ┌─────────────────────────────────────────────────────────┐ │
 
│  │ IS_POWER_OF_2(): 判断2的幂                              │ │
 
│  │ roundup_pow2():  向上取整到2的幂                        │ │
 
│  │ floor_pow2():    向下取整到2的幂                        │ │
 
│  │ page_kva():      页到虚拟地址转换                       │ │
 
│  └─────────────────────────────────────────────────────────┘ │
 
├─────────────────────────────────────────────────────────────┤
 
│  核心算法层                                                  │
 
│  ┌─────────────────────────────────────────────────────────┐ │
 
│  │ buddy_init():          初始化全局状态                   │ │
 
│  │ buddy_init_memmap():   建立伙伴树结构                   │ │
 
│  │ buddy_alloc_pages():   树中查找+分配                   │ │
 
│  │ buddy_free_pages():    树中定位+合并                   │ │
 
│  │ buddy_nr_free_pages(): 返回空闲页数                    │ │
 
│  └─────────────────────────────────────────────────────────┘ │
 
├─────────────────────────────────────────────────────────────┤
 
│  接口适配层                                                  │
 
│  ┌─────────────────────────────────────────────────────────┐ │
 
│  │ buddy_pmm_manager: 符合pmm_manager接口的结构体         │ │
 
│  │ .name = "buddy_pmm_manager"                            │ │
 
│  │ .init = buddy_init                                     │ │
 
│  │ .init_memmap = buddy_init_memmap                       │ │
 
│  │ .alloc_pages = buddy_alloc_pages                       │ │
 
│  │ .free_pages = buddy_free_pages                         │ │
 
│  │ .nr_free_pages = buddy_nr_free_pages                   │ │
 
│  │ .check = buddy_check                                   │ │
 
│  └─────────────────────────────────────────────────────────┘ │
 
└─────────────────────────────────────────────────────────────┘

7. 与 First/Best Fit 的根本区别

特性First/Best FitBuddy System
数据结构双向链表完全二叉树(数组)
分配策略线性搜索树形搜索
块大小任意大小必须是2的幂
时间复杂度O(n)O(log n)
合并机制相邻块合并伙伴块合并
碎片类型外部碎片内部碎片

8. 关键设计思想

  1. 2的幂约束：所有分配都向上取整到2的幂，简化管理

  2. 伙伴关系：只有”同层同大小且地址相邻”的块才能合并

  3. 树形管理：用二叉树快速定位和更新，避免线性搜索

  4. 元数据分离：伙伴树存储在独立页中，避免被分配

总结：Buddy System 完全摒弃了链表管理，改用二叉树+数组的高效数据结构，通过2的幂约束和伙伴合并机制，实现了 O(log n) 的快速分配和自动合并，是现代操作系统内存管理的重要算法。

Footnotes

    • sfence: 代表 “Store Fence”，即存储屏障。它确保在屏障之前的所有存储（写）操作，在屏障之后的任何操作看来，都已经完成。
    • vma: 代表 “Virtual Memory Address”。这指明了这条屏障指令的特定用途——与虚拟内存地址转换有关。 所以，sfence.vma 合起来的意思是：确保所有在它之前发出的、与页表（Page Table）相关的存储操作，对后续的指令地址转换是可见的。
    ↩

关系图谱