基础工具库¶

基础工具库（misc）提供内核开发的基础设施：类型定义、数据结构、字符串操作、日志系统等。它是所有其他模块的基石。

设计理念¶

为什么需要独立的基础库？¶

内核不能使用标准 C 库（libc），因为：

libc 依赖系统调用：但内核本身就是提供系统调用的
libc 假设有操作系统支持：内核运行在裸机环境
libc 太庞大：内核只需要很小的子集

所以内核必须实现自己的基础库。

基础库的原则¶

最小依赖：不依赖其他内核模块
自包含：每个头文件功能独立
高效：内核代码频繁使用，必须高效
标准兼容：尽量遵循 C 标准，方便理解

类型系统：内核的语言基础¶

为什么不直接用 int、long？¶

不同平台上 int、long 的大小不同：

32 位系统：int = 4 字节, long = 4 字节
64 位系统：int = 4 字节, long = 8 字节

内核代码需要精确控制大小，所以定义自己的类型：

u8  = unsigned char (1 字节)
u16 = unsigned short (2 字节)
u32 = unsigned int (4 字节)
u64 = unsigned long (8 字节，在 64 位系统)

类型大小的重要性¶

硬件寄存器通常有固定宽度：

32 位寄存器：必须用 u32 访问
64 位寄存器：必须用 u64 访问

用错误的类型会导致数据截断或对齐问题。

指针大小的处理¶

指针大小与地址空间相关：

32 位系统：指针 = 4 字节
64 位系统：指针 = 8 字节

uintptr_t 是可以容纳指针的整数类型，用于地址计算。

双向链表：内核最常用的数据结构¶

为什么需要特殊的链表实现？¶

传统链表在每个节点中嵌入数据：

struct node {
    struct node *next;
    struct node *prev;
    int data;  // 数据嵌入节点
};

问题：不同数据类型需要不同的链表节点类型。

Linux 风格的侵入式链表¶

NoobKernel 采用 Linux 的设计：链表节点嵌入数据结构：

struct proc {
    int pid;
    struct list_head runq;  // 链表节点嵌入
};

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

container_of 宏的魔法¶

如何从链表节点找到包含它的结构？

已知 struct list_head *pos
求 struct proc *

ptr = container_of(pos, struct proc, runq)

原理：计算成员在结构中的偏移量，从成员地址减去偏移量：

结构地址 = 成员地址 - 偏移量

链表的优势¶

通用：同一套链表操作可用于任何结构
高效：不需要额外分配节点
灵活：一个结构可以有多个链表节点（多个链表）

位图：紧凑的标志集合¶

什么是位图？¶

位图是用位表示布尔值的数组：

位图：10110010
含义：位 1, 3, 4, 7 为真

为什么用位图？¶

节省空间：1 字节可以存储 8 个布尔值。

在内核中，位图用于： - 页面分配状态 - 进程 ID 分配 - Slab 对象状态

位图操作的原子性¶

单字节的位操作可以是原子的（取决于硬件），但多字节不一定。如果需要原子性，应该用原子操作。

字符串操作：与 C 标准的差异¶

为什么不用标准库实现？¶

标准库实现考虑了各种边界情况，但内核环境不同：

无错误处理：内核代码假设参数有效
无边界检查：性能优先
简化的实现：不需要所有特性

常用的字符串函数¶

memset：填充内存
memcpy：复制内存
memcmp：比较内存
strlen：计算长度

这些是内核最常用的操作。

注意事项¶

内核代码经常假设： - 指针非空 - 长度合理 - 内存可访问

这与用户态代码不同，用户态必须防御性编程。

日志系统：调试的利器¶

为什么需要日志？¶

内核运行在特权模式，很难使用传统调试器（断点可能破坏时序）。日志是最有效的调试手段。

日志级别的设计¶

不同级别的日志用于不同场景：

级别	用途	颜色
DEBUG	详细调试信息	绿色
INFO	一般信息	蓝色
WARN	警告	黄色
ERROR	错误	红色
PANIC	致命错误	红色 + 关机

为什么用颜色？¶

终端支持 ANSI 颜色码，颜色可以快速识别日志类型： - 绿色：正常调试信息 - 黄色：需要注意 - 红色：有问题

panic 的设计¶

panic 不只是打印错误，还会关机。这防止系统在错误状态继续运行，可能导致数据损坏。

日志的开销¶

日志涉及 I/O（UART 输出），有性能开销。生产环境应该： - 降低日志级别 - 条件编译移除调试日志

哈希表：快速查找¶

为什么需要哈希表？¶

链表查找是 O(n)，哈希表查找平均是 O(1)。

内核中用于： - dentry 缓存 - inode 缓存 - 进程查找

哈希表的设计¶

哈希函数：name → hash 值
桶数组：hash 值 % 桶数 → 链表

哈希冲突通过链表解决。

桶数的选择¶

桶数应该是质数，减少哈希冲突。NoobKernel 使用较小的质数（17），因为数据量不大。

基数树：索引的利器¶

什么是基数树？¶

基数树是一种压缩的前缀树，用于高效索引长整数键。

应用场景¶

Linux 用基数树管理： - 页缓存（页号 → 页结构） - ID 分配（ID → 对象）

为什么不用哈希表？¶

基数树的优势： - 无哈希冲突 - 支持范围查询 - 内存效率高（压缩前缀）

编译器扩展：利用 GCC 能力¶

likely/unlikely¶

告诉编译器分支概率：

if (likely(ptr != NULL)) {
    // 常见路径，编译器优化
}

if (unlikely(error)) {
    // 罕见路径
}

编译器会将常见路径的代码放在连续位置，提高缓存效率。

属性¶

GCC 提供属性控制编译行为：

__attribute__((packed))：取消对齐
__attribute__((aligned(64)))：指定对齐
__attribute__((noreturn))：函数不返回

内置函数¶

GCC 提供许多内置函数：

__builtin_expect：分支预测
__builtin_clz：前导零计数
__builtin_popcount：位计数

这些通常编译为高效指令。

设计权衡¶

为什么不用更高效的数据结构？¶

内核数据结构的选择标准：

简单可靠：优先选择简单实现
可预测：避免最坏情况
调试友好：容易检查状态

红黑树、跳表等更高效，但实现复杂，容易出错。

为什么自己实现而不是移植？¶

学习目的：自己实现能深入理解原理。

生产内核应该优先使用成熟的实现，避免重复造轮子。

思考题¶

为什么 list_head 只有 prev 和 next，没有数据指针？
位图如何实现原子操作？
日志系统如何避免在中断上下文中造成性能问题？
为什么内核代码可以假设指针非空？

下一步¶

内存管理：理解链表和位图在内存分配中的应用
进程管理：理解链表在进程管理中的应用
文件系统：理解哈希表在 dentry 缓存中的应用