diff options
Diffstat (limited to 'docs/specs/slab.md')
| -rw-r--r-- | docs/specs/slab.md | 233 |
1 files changed, 0 insertions, 233 deletions
diff --git a/docs/specs/slab.md b/docs/specs/slab.md deleted file mode 100644 index dc6953a..0000000 --- a/docs/specs/slab.md +++ /dev/null @@ -1,233 +0,0 @@ -# SLUB 分配器 (SLUB Allocator) - -## 1. 目标 (Objective) - -在物理内存管理器 (PMM) 之上,为内核提供高效的字节级内存分配器。采用 **SLUB** 设计(Simple List of Unfull Blocks),通过复用 PMM 的 `Frame` 描述符存储 per-page 元数据、将空闲链表嵌入对象体内、以及 Per-CPU 活跃页机制,实现低碎片、低锁竞争的小对象分配。本模块是内核 `operator new` 的直接后端。 - -**为何选择 SLUB 而非经典 Slab:** -- `Frame` 结构已包含 `cache` 指针和 `obj_count` 字段,无需额外的 per-page `struct Slab` 头部。 -- 省去 full/partial/empty 三链表管理,仅需一个 partial 链表。 -- Per-CPU 缓存仅需一个"当前活跃页"指针,无需动态分配对象数组(避免 slab_init 的鸡生蛋问题)。 -- Linux 自 2.6.23 起默认 SLUB,6.8 已完全移除经典 Slab。 - -## 2. 前置依赖 (Dependencies) - -- **全局初始化契约 (`global_init.md`):** `slab_init()` 在 `pmm_init()` 之后、`vmm_init()` 之前被 BSP 调用。 -- **物理内存契约 (`pmm.md`):** 依赖 `pmm_alloc_frame()` / `pmm_free_frame()` 以及 `Frame` 描述符中的 `slab.cache` 和 `slab.obj_count` 字段。还依赖 `pa_to_frame()` / `frame_to_pa()` 进行地址转换。 -- **并发同步契约 (`spinlock.md`):** 依赖 `Spinlock` 保护全局 partial 链表。 -- **架构抽象契约 (`arch_abstraction.md`):** 依赖 `arch::cpu::id()` 访问 Per-CPU 缓存;依赖 `arch::cpu::intr_off()/intr_on()` 保护 Per-CPU 操作免受中断重入。 -- **项目约定 (`00_conventions.md`):** 遵循所有命名和类型规范。 - -## 3. 核心数据结构 (Data Structures) - -### 3.1 空闲对象链表(嵌入式) - -空闲对象的前 `sizeof(void*)` 字节存储下一个空闲对象的指针。对象被分配后,该区域归用户使用。因此**最小对象尺寸 = `sizeof(void*)` = 8 字节**。 - -``` -[ Free Object ] [ Free Object ] [ Free Object ] -+-------------+ +-------------+ +-------------+ -| next ---------.------->| next ---------.------->| next = NULL | -| (unused) | | (unused) | | (unused) | -+-------------+ +-------------+ +-------------+ -``` - -### 3.2 Frame 描述符中的 Slab 元数据 - -复用 `include/lume/frame.h` 中已有的字段(无需新增结构体): - -```cpp -// 当 Frame.state == FrameState::Slab 时有效 -struct { - KmemCache* cache; // 此页属于哪个 KmemCache - uint32 obj_count; // 此页上已分配的对象数量 -} slab; -``` - -- 此外,需要在 `Frame` 的 `free` union 成员中增加一个 `void* freelist` 字段,或者直接将 freelist 头指针嵌入 union。为保持 Frame 结构简洁,**freelist 头指针存储在页面固定偏移处(页起始的前 8 字节)**,不侵入 Frame 结构。 - -**修正方案:** 在 `Frame` 的 `slab` union 成员中增加 `void* freelist` 字段: - -```cpp -struct { - KmemCache* cache; // 所属缓存 - uint32 obj_count; // 已分配对象数 - void* freelist; // 页内空闲对象链表头 -} slab; -``` - -### 3.3 Per-CPU 活跃页 - -每个 CPU 对每个 KmemCache 维护一个"当前活跃页"(cpu_slab)。分配时优先从此页的 freelist 弹出对象,无需获取全局锁。 - -```cpp -// 定义于 mm/slab.h (模块私有) -struct PerCpuSlab { - Frame* active; // 当前 CPU 正在使用的 slab 页(可能为 nullptr) -}; -``` - -### 3.4 内核内存缓存 (`class KmemCache`) - -```cpp -// 定义于 mm/slab.h -class KmemCache { -public: - KmemCache() = default; - void init(const char* name, uint32 obj_size, uint32 obj_align); - - void* alloc(); - void free(void* obj); - -private: - Frame* get_partial(); // 从 partial 链表取一个页 - void put_partial(Frame* f); // 将页放入 partial 链表 - Frame* new_slab(); // 从 PMM 申请新页并格式化 - - Spinlock lock_; // 保护 partial 链表 - list_node partial_; // 部分填充的 slab 页链表 - - PerCpuSlab cpu_slab_[kMaxCPUs]; // Per-CPU 活跃页 - - const char* name_ = "uninit"; - uint32 obj_size_ = 0; // 对齐后的对象尺寸 - uint32 obj_align_ = 0; // 对齐要求 - uint32 objs_per_slab_ = 0; // 每页可容纳的对象数 -}; -``` - -### 3.5 通用尺寸缓存 - -```cpp -// 预创建的 2^N 尺寸缓存: 8, 16, 32, 64, 128, 256, 512, 1024, 2048 -inline constexpr int kNumSizeClasses = 9; -inline constexpr uint32 kSizeClasses[kNumSizeClasses] = { - 8, 16, 32, 64, 128, 256, 512, 1024, 2048 -}; - -extern KmemCache g_size_caches[kNumSizeClasses]; -``` - -## 4. 公共 API (Public APIs) - -```cpp -// === 初始化 === -void slab_init(); // 初始化所有通用尺寸缓存 - -// === 对象缓存 API === -void kmem_cache_init(KmemCache* cache, const char* name, - uint32 size, uint32 align); -void* kmem_cache_alloc(KmemCache* cache); -void kmem_cache_free(KmemCache* cache, void* obj); - -// === 通用分配 API === -void* kmalloc(uint32 size); // 自动选择尺寸缓存 -void kfree(void* ptr); // 通过 Frame 反查 cache,自动归还 - -// === C++ Runtime === -void* operator new(size_t size); -void* operator new[](size_t size); -void operator delete(void* ptr) noexcept; -void operator delete[](void* ptr) noexcept; -void operator delete(void* ptr, size_t) noexcept; -void operator delete[](void* ptr, size_t) noexcept; -``` - -## 5. 并发与锁契约 (Concurrency & Locks) - -- **持有锁:** 每个 `KmemCache` 持有一把 `Spinlock lock_`。 - -- **锁的作用域:** `lock_` **仅保护** `partial_` 链表。 - -- **Per-CPU 保护:** 访问 `cpu_slab_[cpu_id]` 时必须关闭中断(同 PMM 的 PCP 策略),防止中断重入。 - -- **快速路径(关中断,无锁):** 从当前 CPU 的 `active` 页的 `freelist` 弹出/压入对象。 - -- **慢速路径(需要锁):** - - alloc:当 `active` 页无空闲对象时,获取 `lock_` 从 `partial_` 取页(或调用 PMM 新建)。 - - free:当归还对象使一个页变为完全空闲时,获取 `lock_` 归还 PMM。 - -- **与 PMM 交互:** `new_slab()` 调用 `pmm_alloc_frame()` 时**不持有** `lock_`(先释放锁,申请页,再获取锁挂入链表),避免 Slab lock → PMM lock 嵌套。 - -## 6. 错误路径 (Error Paths) - -- **初始化失败:** `slab_init()` 若 PMM 无法提供页面,`kernel_panic()`。 - -- **分配失败:** `kmalloc()` / `kmem_cache_alloc()` 在 OOM 时返回 `nullptr`。 - -- **释放错误:** `kfree(nullptr)` 为 no-op。传入非法指针(不属于任何 slab 页)时 `kernel_panic()`。 - -## 7. 状态机 / 时序图 (State Machine / Sequence) - -### 7.1 `kmem_cache_alloc` 时序 - -``` -[kmem_cache_alloc(cache) on CPU X] - │ - ├─> 1. 关中断 - ├─> 2. active = cache->cpu_slab_[X].active - │ - ├─> 3. if (active && active->slab.freelist != NULL) ? - │ ├── [是 (Fast Path)] - │ │ ├─ obj = active->slab.freelist - │ │ ├─ active->slab.freelist = *(void**)obj - │ │ ├─ active->slab.obj_count++ - │ │ ├─ 恢复中断 - │ │ └─ return obj - │ │ - │ └── [否 (Slow Path)] - │ ├─ 4.1 将 active (若满) 从 cpu_slab 移出 - │ ├─ (满页不需要跟踪,但其 Frame 中 cache 指针仍有效) - │ ├─ 4.2 恢复中断 - │ ├─ 4.3 LockGuard guard(cache->lock_) - │ ├─ 4.4 new_active = get_partial() // 从 partial 链表取 - │ │ └─ 若无,释放锁 → new_slab() → 重新获取锁 - │ ├─ 4.5 释放锁 - │ ├─ 4.6 关中断 - │ ├─ 4.7 cache->cpu_slab_[X].active = new_active - │ ├─ 4.8 从 new_active->slab.freelist 弹出 obj - │ ├─ 4.9 恢复中断 - │ └─ return obj - │ - ▼ -[返回 obj* 或 nullptr] -``` - -### 7.2 `kfree` 时序 - -``` -[kfree(ptr)] - │ - ├─> 1. pa = ptr 的物理地址 (对于 identity/higher-half,减去偏移) - ├─> 2. frame = pa_to_frame(pa & ~(kPageSize-1)) - ├─> 3. cache = frame->slab.cache - │ - ├─> 4. 关中断 - ├─> 5. 将 obj 压入 frame->slab.freelist - ├─> 6. frame->slab.obj_count-- - │ - ├─> 7. if (obj_count == 0) ? - │ ├── [是:页完全空闲] - │ │ ├─ 若此页是当前 CPU 的 active,清除 active - │ │ ├─ 恢复中断 - │ │ ├─ LockGuard: 从 partial_ 链表移除 (如果在链表中) - │ │ └─ pmm_free_frame(frame) // 归还 PMM - │ │ - │ └── [否] - │ ├─ 若此页不是任何 CPU 的 active 且不在 partial, - │ │ 则需获取锁放入 partial (满→部分满的过渡) - │ └─ 恢复中断 - │ - ▼ -[完成] -``` - -## 8. 已知缺陷与未来挑战 - -### 8.1 缓存收缩 - -当前不主动收缩 partial 链表。未来可增加 `kmem_cache_shrink()` 供内存回收线程调用。 - -### 8.2 大对象分配 - -大于 2048 字节的分配直接退化为 `pmm_alloc_frames()`。当前由 `kmalloc` 透明处理。 |
