path: root/docs/specs/slab.md

# 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` 透明处理。