1150 lines
17 KiB
Markdown
1150 lines
17 KiB
Markdown
好，这个问题就进入**“malloc 和 OS 的交界面”**了，本质就是一句话：
|
||
|
||
> **用户态是不能“直接拿虚拟内存”的，必须通过系统调用向内核要。**
|
||
|
||
但你现在要的不是这句废话，而是**完整机制 + 实际路径 + 细节差异**，我直接给你一条从上到下打通。
|
||
|
||
---
|
||
|
||
# 一、总流程（先建立全局模型）
|
||
|
||
当你写：
|
||
|
||
```c
|
||
void* p = malloc(1000);
|
||
```
|
||
|
||
底层发生的是：
|
||
|
||
```text
|
||
malloc
|
||
↓（不够用）
|
||
向 OS 要内存（系统调用）
|
||
↓
|
||
OS 修改进程虚拟内存布局（VMA）
|
||
↓
|
||
返回一段“合法虚拟地址”
|
||
↓
|
||
malloc 切 chunk 管理
|
||
```
|
||
|
||
关键点：
|
||
|
||
> **OS 给你的不是“物理内存”，而是“虚拟地址范围的使用权”**
|
||
|
||
---
|
||
|
||
# 二、malloc 向 OS 要内存的两种方式（核心）
|
||
|
||
现代 Linux（glibc）主要用两种：
|
||
|
||
---
|
||
|
||
## 1️⃣ `brk / sbrk` —— 扩展 heap（传统主力）
|
||
|
||
这是最经典的方式。
|
||
|
||
### 本质：
|
||
|
||
👉 **把 heap 顶部往上“推高”**
|
||
|
||
---
|
||
|
||
### 内存布局（非常关键）
|
||
|
||
```text
|
||
低地址
|
||
│
|
||
├── 程序代码（text）
|
||
├── 数据段（data）
|
||
├── BSS
|
||
├── heap ←（这里往上长）
|
||
│ ↑
|
||
│ 当前 brk
|
||
│
|
||
│ （未使用虚拟空间）
|
||
│
|
||
├── mmap 区域（往下长）
|
||
│
|
||
├── 栈（stack）
|
||
│
|
||
高地址
|
||
```
|
||
|
||
---
|
||
|
||
### 系统调用：
|
||
|
||
```c
|
||
brk(new_end);
|
||
```
|
||
|
||
或：
|
||
|
||
```c
|
||
sbrk(increment);
|
||
```
|
||
|
||
---
|
||
|
||
### 举个实际过程：
|
||
|
||
```text
|
||
当前 heap 结束：0x10000
|
||
malloc 想要 4KB
|
||
|
||
→ 调用 sbrk(4096)
|
||
|
||
内核做：
|
||
- 修改 VMA（虚拟内存区域）
|
||
- 更新 brk → 0x11000
|
||
|
||
返回：0x10000（新空间起点）
|
||
```
|
||
|
||
---
|
||
|
||
### 特点总结：
|
||
|
||
* ✔ 连续内存
|
||
* ✔ 适合小块分配
|
||
* ❌ 只能“向上长”
|
||
* ❌ 不容易归还给 OS（碎片问题）
|
||
|
||
---
|
||
|
||
## 2️⃣ `mmap` —— 单独映射（现代关键）
|
||
|
||
当 malloc 发现：
|
||
|
||
> “这个块太大了”
|
||
|
||
就不会走 heap，而是直接 mmap
|
||
|
||
---
|
||
|
||
### 系统调用：
|
||
|
||
```c
|
||
mmap(NULL, size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
|
||
```
|
||
|
||
---
|
||
|
||
### 本质：
|
||
|
||
👉 **让内核在虚拟地址空间中找一块空地，直接映射一段**
|
||
|
||
---
|
||
|
||
### 内存结构：
|
||
|
||
```text
|
||
heap ↑
|
||
（空洞）
|
||
mmap ↓
|
||
```
|
||
|
||
👉 mmap 区域是**独立的，不挨着 heap**
|
||
|
||
---
|
||
|
||
### 特点：
|
||
|
||
* ✔ 可以在任意地址分配
|
||
* ✔ 可以独立释放（munmap）
|
||
* ✔ 适合大块内存
|
||
* ❌ 系统调用开销更高
|
||
|
||
---
|
||
|
||
## malloc 的策略（glibc）
|
||
|
||
大致是：
|
||
|
||
```text
|
||
小块（< 128KB 左右） → brk
|
||
大块（>= 128KB） → mmap
|
||
```
|
||
|
||
（具体阈值可调）
|
||
|
||
---
|
||
|
||
# 三、OS 到底“分配了什么”？
|
||
|
||
这点你必须彻底理解，否则会一直模糊。
|
||
|
||
---
|
||
|
||
## ❗关键结论：
|
||
|
||
> **OS 分配的是“虚拟地址范围 + 映射关系”，不是立即分配物理内存**
|
||
|
||
---
|
||
|
||
### 举个例子：
|
||
|
||
```c
|
||
p = malloc(1GB);
|
||
```
|
||
|
||
发生：
|
||
|
||
* OS：✔ 给你 1GB 虚拟地址
|
||
* OS：❌ 不会马上给你 1GB 物理内存
|
||
|
||
---
|
||
|
||
### 什么时候才分配物理内存？
|
||
|
||
👉 **当你真正访问（触发 page fault）**
|
||
|
||
---
|
||
|
||
### 过程：
|
||
|
||
```text
|
||
访问 p[0]
|
||
↓
|
||
页表无映射
|
||
↓
|
||
触发 page fault
|
||
↓
|
||
内核分配物理页（4KB）
|
||
↓
|
||
建立映射
|
||
```
|
||
|
||
---
|
||
|
||
👉 这叫：
|
||
|
||
> **按需分配（lazy allocation）**
|
||
|
||
---
|
||
|
||
# 四、free 之后发生什么？
|
||
|
||
你刚才已经问到 free list，这里补完整闭环：
|
||
|
||
---
|
||
|
||
## 情况 1：heap（brk）
|
||
|
||
```c
|
||
free(p);
|
||
```
|
||
|
||
* ✔ 进入 free list
|
||
* ❌ 不还给 OS（大多数情况）
|
||
|
||
👉 只是 malloc 内部复用
|
||
|
||
---
|
||
|
||
## 情况 2：mmap
|
||
|
||
```c
|
||
free(p);
|
||
```
|
||
|
||
* ✔ 直接调用 `munmap`
|
||
* ✔ 归还 OS
|
||
|
||
---
|
||
|
||
# 五、再抽象一层（你这个水平该理解这个）
|
||
|
||
整个系统是三层：
|
||
|
||
---
|
||
|
||
## 层级结构
|
||
|
||
```text
|
||
[用户程序]
|
||
↓ malloc/free
|
||
[glibc malloc]
|
||
↓ brk / mmap
|
||
[Linux 内核]
|
||
↓ 页表管理
|
||
[物理内存]
|
||
```
|
||
|
||
---
|
||
|
||
## 每层职责
|
||
|
||
### malloc：
|
||
|
||
* 管 chunk
|
||
* 管 free list
|
||
* 做复用
|
||
|
||
---
|
||
|
||
### OS：
|
||
|
||
* 管虚拟地址空间（VMA）
|
||
* 管页表
|
||
* 处理缺页
|
||
|
||
---
|
||
|
||
### 硬件：
|
||
|
||
* MMU 做地址转换
|
||
|
||
---
|
||
|
||
# 六、一个你必须能回答的问题（我帮你提前补）
|
||
|
||
> 为什么不直接让 malloc 管整个虚拟空间？
|
||
|
||
因为：
|
||
|
||
* 用户态**不能修改页表**
|
||
* 用户态**不能分配物理页**
|
||
* 安全性（隔离）
|
||
|
||
👉 所以必须 syscall
|
||
|
||
---
|
||
|
||
# 七、终极一句话总结（面试级）
|
||
|
||
> malloc 通过 brk 扩展 heap 或通过 mmap 建立独立映射向操作系统申请虚拟地址空间；操作系统仅分配虚拟地址并延迟分配物理内存，malloc 再在这块空间上切分 chunk 并通过 free list 进行管理和复用。
|
||
|
||
---
|
||
|
||
# 八、如果你要继续深入（强烈建议）
|
||
|
||
下一步你应该问的是：
|
||
|
||
1. **VMA（vm_area_struct）到底怎么管理？**
|
||
2. **page fault 具体怎么走（中断 → 内核 → 分配页）**
|
||
3. **tcache / fastbin 是怎么优化 malloc 的？**
|
||
4. **为什么会产生内存碎片？怎么解决？**
|
||
|
||
---
|
||
|
||
你要的话，我可以给你画一张：
|
||
|
||
> **从 malloc → brk/mmap → 页表 → page fault → 物理内存 的完整执行路径图（带地址变化）**
|
||
|
||
那个是“真正打通虚拟内存”的关键一步。
|
||
|
||
---
|
||
|
||
好，这一块你要是搞清楚了，**虚拟内存这一整套基本就打通了**。我直接给你从“结构 → 查找 → 修改 → 触发路径”一条链讲透，尽量贴近 Linux 内核真实实现。
|
||
|
||
---
|
||
|
||
# 一、先给你一个本质定义（非常关键）
|
||
|
||
> **VMA（Virtual Memory Area）= 一段“连续虚拟地址区间 + 统一属性”的描述结构**
|
||
|
||
也就是说：
|
||
|
||
* 它不是内存
|
||
* 不是页表
|
||
* 而是：**内核对一段虚拟地址的“规则说明”**
|
||
|
||
---
|
||
|
||
# 二、VMA 长什么样（内核结构）
|
||
|
||
在 Linux 里核心结构是：
|
||
|
||
```c
|
||
struct vm_area_struct {
|
||
unsigned long vm_start; // 起始地址
|
||
unsigned long vm_end; // 结束地址
|
||
|
||
struct mm_struct *vm_mm; // 所属进程
|
||
|
||
unsigned long vm_flags; // 权限（读/写/执行等）
|
||
|
||
struct file *vm_file; // 如果是文件映射（mmap文件）
|
||
|
||
struct vm_area_struct *vm_next; // 链表
|
||
struct rb_node vm_rb; // 红黑树节点
|
||
};
|
||
```
|
||
|
||
你重点抓三个东西就够：
|
||
|
||
```text
|
||
[vm_start, vm_end) → 管哪一段地址
|
||
vm_flags → 这段能干嘛（RWX）
|
||
vm_file → 是否映射文件
|
||
```
|
||
|
||
---
|
||
|
||
# 三、一个进程里 VMA 长啥样（全局视图）
|
||
|
||
一个进程不是一个 VMA，而是：
|
||
|
||
> **很多个 VMA 组成整个虚拟地址空间**
|
||
|
||
比如：
|
||
|
||
```text
|
||
低地址
|
||
│
|
||
├── [text 段] r-x
|
||
├── [data 段] rw-
|
||
├── [heap] rw-
|
||
├── [mmap 区域1] rw-
|
||
├── [mmap 区域2] r--
|
||
│
|
||
├── [stack] rw-
|
||
│
|
||
高地址
|
||
```
|
||
|
||
👉 每一段，都是一个 VMA
|
||
|
||
---
|
||
|
||
# 四、VMA 存在哪？（核心）
|
||
|
||
在进程控制结构里：
|
||
|
||
```c
|
||
struct mm_struct {
|
||
struct vm_area_struct *mmap; // VMA 链表头
|
||
struct rb_root mm_rb; // 红黑树根
|
||
};
|
||
```
|
||
|
||
👉 也就是说：
|
||
|
||
一个进程：
|
||
|
||
```text
|
||
task_struct
|
||
↓
|
||
mm_struct
|
||
↓
|
||
VMA 集合（链表 + 红黑树）
|
||
```
|
||
|
||
---
|
||
|
||
# 五、为什么既用链表又用红黑树？
|
||
|
||
这是一个很经典的设计点。
|
||
|
||
---
|
||
|
||
## 1️⃣ 链表（vm_next）
|
||
|
||
👉 用于：
|
||
|
||
* 顺序遍历（比如 /proc/pid/maps）
|
||
|
||
优点：
|
||
|
||
* 简单
|
||
* 按地址排序
|
||
|
||
缺点：
|
||
|
||
* 查找慢（O(n)）
|
||
|
||
---
|
||
|
||
## 2️⃣ 红黑树（mm_rb）
|
||
|
||
👉 用于：
|
||
|
||
* **快速查找某个地址属于哪个 VMA**
|
||
|
||
复杂度：
|
||
|
||
```text
|
||
O(log n)
|
||
```
|
||
|
||
---
|
||
|
||
👉 所以：
|
||
|
||
> **链表负责“遍历”，红黑树负责“查找”**
|
||
|
||
---
|
||
|
||
# 六、核心操作：查找 VMA（最关键路径）
|
||
|
||
当程序访问一个地址：
|
||
|
||
```c
|
||
*p = 10;
|
||
```
|
||
|
||
如果触发 page fault：
|
||
|
||
---
|
||
|
||
## 内核会做：
|
||
|
||
```text
|
||
1. 获取 fault address（比如 0x123456）
|
||
2. 在 VMA 红黑树里查找
|
||
↓
|
||
find_vma(mm, addr)
|
||
3. 判断：
|
||
addr ∈ [vm_start, vm_end) ?
|
||
```
|
||
|
||
---
|
||
|
||
## 如果找不到：
|
||
|
||
👉 直接：
|
||
|
||
```text
|
||
Segmentation Fault（段错误）
|
||
```
|
||
|
||
---
|
||
|
||
## 如果找到了：
|
||
|
||
继续：
|
||
|
||
```text
|
||
检查 vm_flags（有没有写权限）
|
||
```
|
||
|
||
* 没权限 → segfault
|
||
* 有权限 → 分配物理页
|
||
|
||
---
|
||
|
||
# 七、VMA 是怎么创建的？
|
||
|
||
主要三种来源：
|
||
|
||
---
|
||
|
||
## 1️⃣ 程序加载（exec）
|
||
|
||
比如 ELF：
|
||
|
||
* 代码段 → 一个 VMA（r-x）
|
||
* 数据段 → 一个 VMA（rw-）
|
||
|
||
---
|
||
|
||
## 2️⃣ malloc（间接）
|
||
|
||
### 小块：
|
||
|
||
```text
|
||
malloc → brk → 扩展 heap VMA
|
||
```
|
||
|
||
👉 heap 通常是：
|
||
|
||
> **一个 VMA 不断变大**
|
||
|
||
---
|
||
|
||
### 大块：
|
||
|
||
```text
|
||
malloc → mmap → 新建 VMA
|
||
```
|
||
|
||
👉 每个 mmap：
|
||
|
||
> **一个独立 VMA**
|
||
|
||
---
|
||
|
||
## 3️⃣ 用户 mmap
|
||
|
||
```c
|
||
mmap(...)
|
||
```
|
||
|
||
👉 直接创建 VMA
|
||
|
||
---
|
||
|
||
# 八、VMA 的合并（非常重要，容易考）
|
||
|
||
内核会做优化：
|
||
|
||
---
|
||
|
||
## 如果两个 VMA：
|
||
|
||
```text
|
||
地址连续 + 权限相同 + 类型相同
|
||
```
|
||
|
||
👉 会合并
|
||
|
||
---
|
||
|
||
### 举例：
|
||
|
||
```text
|
||
[0x1000 - 0x2000] rw-
|
||
[0x2000 - 0x3000] rw-
|
||
```
|
||
|
||
👉 合并成：
|
||
|
||
```text
|
||
[0x1000 - 0x3000] rw-
|
||
```
|
||
|
||
---
|
||
|
||
👉 目的：
|
||
|
||
* 减少 VMA 数量
|
||
* 提高查找效率
|
||
|
||
---
|
||
|
||
# 九、VMA 删除（释放）
|
||
|
||
---
|
||
|
||
## 情况 1：munmap
|
||
|
||
```c
|
||
munmap(addr, size);
|
||
```
|
||
|
||
内核：
|
||
|
||
```text
|
||
1. 找到对应 VMA
|
||
2. 删除或裁剪
|
||
3. 更新红黑树
|
||
4. 解除页表映射
|
||
```
|
||
|
||
---
|
||
|
||
## 情况 2：进程退出
|
||
|
||
👉 直接：
|
||
|
||
```text
|
||
销毁整个 mm_struct
|
||
→ 所有 VMA 全部释放
|
||
```
|
||
|
||
---
|
||
|
||
# 十、你必须理解的关键区别（非常重要）
|
||
|
||
> **VMA ≠ 页表 ≠ 物理内存**
|
||
|
||
---
|
||
|
||
## 三者关系：
|
||
|
||
```text
|
||
VMA（逻辑区域）
|
||
↓ 描述
|
||
页表（地址映射）
|
||
↓ 指向
|
||
物理页（真实内存）
|
||
```
|
||
|
||
---
|
||
|
||
👉 举个例子：
|
||
|
||
```text
|
||
malloc 1GB
|
||
```
|
||
|
||
* ✔ VMA：立刻存在（1GB范围）
|
||
* ❌ 页表：还没完全建立
|
||
* ❌ 物理内存：还没分配
|
||
|
||
---
|
||
|
||
👉 访问时才：
|
||
|
||
```text
|
||
page fault → 建页表 → 分配物理页
|
||
```
|
||
|
||
---
|
||
|
||
# 十一、一个完整访问路径（你要掌握这个）
|
||
|
||
```text
|
||
用户访问 addr
|
||
↓
|
||
MMU 查页表
|
||
↓
|
||
没有映射 → page fault
|
||
↓
|
||
内核：
|
||
find_vma(addr)
|
||
↓
|
||
检查权限
|
||
↓
|
||
分配物理页
|
||
↓
|
||
建立页表映射
|
||
↓
|
||
返回用户态继续执行
|
||
```
|
||
|
||
---
|
||
|
||
# 十二、终极总结（压缩版）
|
||
|
||
> VMA 是内核对进程虚拟地址空间的区间描述结构，存储在 mm_struct 中，通过红黑树实现 O(log n) 查找；在 page fault 时，内核通过 VMA 判断地址是否合法及权限，再决定是否分配物理页并建立页表映射。
|
||
|
||
---
|
||
|
||
# 十三、你下一步应该问（我帮你规划）
|
||
|
||
你现在已经到一个很关键的门槛了，接下来建议你继续打这几个点：
|
||
|
||
1. **page fault 详细流程（中断级别）**
|
||
2. **页表结构（多级页表到底怎么走）**
|
||
3. **COW（写时复制）怎么用 VMA 实现**
|
||
4. **匿名映射 vs 文件映射**
|
||
|
||
---
|
||
|
||
如果你要，我下一步可以给你讲一个特别关键的东西：
|
||
|
||
> **“fork 之后 VMA 和页表是怎么复制的（COW全过程）”**
|
||
|
||
这个一旦搞懂，你对操作系统内存模型就基本碾压大多数人了。
|
||
|
||
---
|
||
|
||
好，我按你要求来：**不碎片、不聊天式解释，直接给你一条从硬件→内核→malloc→free list 的完整闭环模型**，你可以当“总纲+复习材料”。
|
||
|
||
---
|
||
|
||
# 一、最底层：硬件 + 地址转换（你必须当作起点）
|
||
|
||
程序执行时访问的是**虚拟地址 VA**，不是物理地址 PA：
|
||
|
||
```text
|
||
CPU发出 VA
|
||
↓
|
||
MMU（硬件）
|
||
↓ 查页表
|
||
得到 PA
|
||
↓
|
||
访问物理内存
|
||
```
|
||
|
||
如果页表里没有映射：
|
||
|
||
```text
|
||
→ 触发 page fault（缺页异常，中断）
|
||
→ 进入内核
|
||
```
|
||
|
||
---
|
||
|
||
# 二、内核层：虚拟内存的“逻辑描述”（VMA）
|
||
|
||
内核不会直接给你“内存块”，它先维护：
|
||
|
||
> **VMA = 一段虚拟地址区间 + 权限 + 类型**
|
||
|
||
本质结构（抽象）：
|
||
|
||
```c
|
||
struct vm_area_struct {
|
||
vm_start, vm_end
|
||
vm_flags（r/w/x）
|
||
vm_file（是否文件映射）
|
||
}
|
||
```
|
||
|
||
一个进程的虚拟空间：
|
||
|
||
```text
|
||
多个 VMA 拼起来：
|
||
[text][data][heap][mmap...][stack]
|
||
```
|
||
|
||
存储方式：
|
||
|
||
```text
|
||
mm_struct：
|
||
红黑树（按地址索引）→ 查找 O(log n)
|
||
链表（顺序） → 遍历
|
||
```
|
||
|
||
---
|
||
|
||
# 三、page fault 的核心决策逻辑（必须背下来）
|
||
|
||
当访问一个 VA：
|
||
|
||
```text
|
||
1. MMU 查页表 → miss
|
||
2. 内核接管（page fault handler）
|
||
3. 在 VMA 红黑树中找：
|
||
find_vma(addr)
|
||
|
||
4. 判断：
|
||
addr ∈ VMA ?
|
||
否 → SEGFAULT
|
||
是 → 检查权限（R/W/X）
|
||
|
||
5. 合法 → 分配物理页 + 建页表映射
|
||
6. 返回用户态继续执行
|
||
```
|
||
|
||
关键结论：
|
||
|
||
> **VMA 决定“这地址是否合法”，页表决定“映射到哪”**
|
||
|
||
---
|
||
|
||
# 四、OS 如何“分配内存”（你问的核心）
|
||
|
||
注意：OS 从来不“直接给物理内存”，而是：
|
||
|
||
> **给虚拟地址范围（VMA）+ 延迟物理分配**
|
||
|
||
两种系统调用路径：
|
||
|
||
---
|
||
|
||
## 1️⃣ brk / sbrk（heap 扩展）
|
||
|
||
```text
|
||
作用：扩展 heap VMA 的末尾
|
||
```
|
||
|
||
过程：
|
||
|
||
```text
|
||
原 heap end = 0x10000
|
||
sbrk(4096)
|
||
→ 内核：
|
||
修改 VMA：heap end → 0x11000
|
||
（不分配物理页）
|
||
```
|
||
|
||
特点：
|
||
|
||
* 连续
|
||
* 只能向上增长
|
||
* 小块分配主力
|
||
|
||
---
|
||
|
||
## 2️⃣ mmap（独立映射）
|
||
|
||
```c
|
||
mmap(NULL, size, ...)
|
||
```
|
||
|
||
过程：
|
||
|
||
```text
|
||
内核：
|
||
在地址空间找一段空洞
|
||
创建新 VMA
|
||
```
|
||
|
||
特点：
|
||
|
||
* 任意位置
|
||
* 独立 VMA
|
||
* 可单独释放（munmap）
|
||
* 大块内存使用
|
||
|
||
---
|
||
|
||
## malloc 的策略（关键）
|
||
|
||
```text
|
||
小块 → brk（heap）
|
||
大块 → mmap（独立 VMA）
|
||
```
|
||
|
||
---
|
||
|
||
# 五、从 OS 到 malloc：控制权转移
|
||
|
||
到这里：
|
||
|
||
```text
|
||
OS：
|
||
管 VMA（地址是否合法）
|
||
管页表（地址映射）
|
||
```
|
||
|
||
但：
|
||
|
||
> **OS 不管“你怎么用这块内存”**
|
||
|
||
于是：
|
||
|
||
```text
|
||
malloc 接管 heap 内存
|
||
```
|
||
|
||
---
|
||
|
||
# 六、malloc 的世界：heap → chunk
|
||
|
||
malloc 拿到一大块虚拟空间（heap），然后：
|
||
|
||
```text
|
||
切成很多 chunk
|
||
```
|
||
|
||
每个 chunk：
|
||
|
||
```c
|
||
[ header | payload | (footer) ]
|
||
|
||
header:
|
||
size
|
||
alloc bit
|
||
```
|
||
|
||
heap 结构：
|
||
|
||
```text
|
||
[A][F][A][F][F][A]
|
||
```
|
||
|
||
A = allocated
|
||
F = free
|
||
|
||
---
|
||
|
||
# 七、问题核心：如何找到空闲块？
|
||
|
||
这就是你看到的：
|
||
|
||
> 隐式 / 显式空闲链表
|
||
|
||
---
|
||
|
||
## 1️⃣ 隐式空闲链表（implicit）
|
||
|
||
结构：
|
||
|
||
```text
|
||
所有 chunk 按顺序排列
|
||
```
|
||
|
||
查找：
|
||
|
||
```text
|
||
从头扫：
|
||
if free && size够 → 用
|
||
```
|
||
|
||
复杂度：
|
||
|
||
```text
|
||
O(n)
|
||
```
|
||
|
||
问题：
|
||
|
||
* heap 越大越慢
|
||
|
||
---
|
||
|
||
## 2️⃣ 显式空闲链表（explicit）
|
||
|
||
结构：
|
||
|
||
```text
|
||
只把 free chunk 串起来：
|
||
|
||
heap:
|
||
[A][F][A][F][F]
|
||
|
||
free list:
|
||
F <-> F <-> F
|
||
```
|
||
|
||
free chunk 结构：
|
||
|
||
```c
|
||
[ header | prev | next | payload ]
|
||
```
|
||
|
||
查找：
|
||
|
||
```text
|
||
遍历 free list
|
||
```
|
||
|
||
复杂度：
|
||
|
||
```text
|
||
O(空闲块数量)
|
||
```
|
||
|
||
---
|
||
|
||
# 八、free 的完整行为（关键闭环）
|
||
|
||
```c
|
||
free(p);
|
||
```
|
||
|
||
发生：
|
||
|
||
```text
|
||
1. 标记 chunk = free
|
||
2. 向前/向后检查是否也是 free
|
||
3. 合并（coalescing）
|
||
4. 插入 free list
|
||
```
|
||
|
||
---
|
||
|
||
## 合并机制（核心）
|
||
|
||
```text
|
||
[ F ][ 当前 ][ F ]
|
||
→ 合并成一个大 F
|
||
```
|
||
|
||
依赖：
|
||
|
||
* header（当前）
|
||
* footer（前一个）
|
||
|
||
---
|
||
|
||
# 九、为什么 free 不还给 OS？
|
||
|
||
因为：
|
||
|
||
```text
|
||
brk 区域：
|
||
只能整体收缩
|
||
中间空洞无法归还
|
||
|
||
→ 留在 free list 复用
|
||
```
|
||
|
||
但：
|
||
|
||
```text
|
||
mmap：
|
||
free → munmap → 直接还 OS
|
||
```
|
||
|
||
---
|
||
|
||
# 十、现代 malloc（真实情况）
|
||
|
||
实际不会只用一个 free list，而是：
|
||
|
||
```text
|
||
tcache（线程本地）
|
||
fastbin（小块）
|
||
smallbin
|
||
largebin
|
||
unsorted bin
|
||
```
|
||
|
||
本质：
|
||
|
||
> **多组“显式空闲链表”，按大小分类**
|
||
|
||
优化目标：
|
||
|
||
```text
|
||
减少查找时间
|
||
减少锁竞争
|
||
提高局部性
|
||
```
|
||
|
||
---
|
||
|
||
# 十一、完整路径（你必须能在脑子里跑一遍）
|
||
|
||
```text
|
||
malloc(1000)
|
||
↓
|
||
malloc 查 tcache / bin
|
||
↓ 没找到
|
||
向 OS 要：
|
||
brk 或 mmap
|
||
↓
|
||
OS 创建/扩展 VMA
|
||
↓
|
||
返回虚拟地址
|
||
↓
|
||
malloc 切 chunk
|
||
↓
|
||
返回 pointer
|
||
|
||
（访问时）
|
||
↓
|
||
MMU 查页表
|
||
↓
|
||
没有映射 → page fault
|
||
↓
|
||
内核：
|
||
find_vma
|
||
检查权限
|
||
分配物理页
|
||
建页表
|
||
↓
|
||
继续执行
|
||
```
|
||
|
||
---
|
||
|
||
# 十二、最核心的三层模型（压缩记忆版）
|
||
|
||
```text
|
||
【OS层】
|
||
VMA：这段地址能不能用
|
||
页表：这段地址映射到哪
|
||
|
||
【malloc层】
|
||
heap：一大块空间
|
||
chunk：切出来的小块
|
||
|
||
【算法层】
|
||
free list：
|
||
隐式（扫所有）
|
||
显式（只扫空闲）
|
||
```
|
||
|
||
---
|
||
|
||
# 十三、一句话终极总结（你要能秒说出来）
|
||
|
||
> 操作系统通过 brk 或 mmap 为进程分配虚拟地址区间（VMA），并在访问时按需建立页表与物理内存映射；malloc 在这些区间内切分 chunk 并通过显式或隐式空闲链表管理空闲块，实现用户级内存分配与复用。
|
||
|
||
---
|
||
|
||
如果你下一步要继续压深度，最值得打的两个点是：
|
||
|
||
* **page fault 从中断入口到分配物理页的完整路径（含寄存器/内核栈）**
|
||
* **COW（fork 时 VMA + 页表如何共享 + 写时复制触发机制）**
|
||
|
||
这两个一旦吃透，你对操作系统内存这一块就是“工程级理解”了。
|