跳至主要內容

FIRSTFIT 算法

学习阁2026/7/16大约 56 分钟内核组件内核内存管理FIRSTFIT

FIRSTFIT 算法

📚 本节导读

学习时长: 约 20 分钟
难度级别: ⭐⭐⭐☆☆
前置知识: 4.4.1 堆内存管理、链表数据结构

FIRSTFIT（首次适应）算法是 OneOS 支持的一种经典内存分配算法。它通过维护空闲块链表，在分配时从链表头部开始扫描，找到第一个足够大的空闲块即进行分配。该算法实现简单、分配速度快，是嵌入式系统的常用选择。

🎯 学习目标

  • 理解 FIRSTFIT 算法的核心思想和工作流程
  • 了解 FIRSTFIT 的内部数据结构（chunk、bucket）
  • 掌握 FIRSTFIT 的优缺点
  • 明确 FIRSTFIT 的适用场景

一、配置

#define OS_USING_ALG_FIRSTFIT

当定义了 OS_USING_ALG_FIRSTFIT 且未定义 OS_USING_ALG_BUDDY 时，OS_MEM_ALG_DEFAULT 将使用 FIRSTFIT 算法。

源文件：kernel/source/os_mem_firstfit.c

二、算法原理

2.1 核心思想

FIRSTFIT 维护一个按大小分桶的空闲块链表。分配时，从对应大小的桶开始扫描，找到第一个满足请求大小的空闲块即进行分配。

2.2 分配策略

FIRSTFIT 的分配采用近似最佳匹配策略：

  1. 优先尝试精确桶：从请求大小对应的 bucket 开始，最多尝试 CONFIG_SYS_HEAP_ALLOC_LOOPS（默认为 8）个块
  2. 回退到更大桶：如果精确桶中找不到合适的块，从更大的桶中取最小可用块
  3. 切分剩余空间：如果找到的块大于请求大小，将其切分为已分配块和剩余空闲块，剩余部分重新加入空闲链表

2.3 释放与合并

释放内存时，FIRSTFIT 尝试与相邻空闲块合并：

释放前：  [已用块A] [空闲块B] [已用块C]
释放A：   [空闲块A] [空闲块B] [已用块C]
         ↓ 合并
合并后：  [空闲块A+B(更大)] [已用块C]

合并策略：先尝试与右侧空闲块合并，再尝试与左侧空闲块合并。

三、内部数据结构

3.1 Chunk（内存块）

FIRSTFIT 以 chunk 为基本管理单位，每个 chunk 大小为 CHUNK_UNIT（8 字节）。所有 chunk 从堆起始地址开始连续编号。

每个 chunk 包含以下字段：

  • LEFT_SIZE：左侧相邻 chunk 的大小（chunk 单位），用于反向遍历
  • SIZE_AND_USED：当前 chunk 的大小（chunk 单位），最低位为使用标志（1 = 已用，0 = 空闲）
  • FREE_PREV / FREE_NEXT：空闲链表中的前驱和后继指针（仅空闲块有效）
  • TASK_ID：分配该块的当前任务指针（仅当 OS_USING_MEM_TRACE 启用时）

3.2 Bucket 桶

空闲块按大小分桶管理，每个桶是一个双向循环链表。相关类型和结构体定义在 kernel/source/os_mem_firstfit.c 中：

来源：kernel/source/os_mem_firstfit.c

字段含义：

struct z_heap_bucket 字段：

字段含义
next桶中第一个空闲块的 chunk ID（该桶双向循环链表的入口）

struct z_heap 字段：

字段含义
chunk0_hdr_areachunk0 的头部存储区（与最大头部匹配，用于管理元数据）
len总 chunk 数（堆的总容量，以 8 字节为单位）
avail_buckets桶非空位图：第 N 位为 1 表示第 N 个桶有内容（用于 O(1) 找最小非空桶）
buckets桶数组：buckets[i].next 指向第 i 个桶链表的第一个空闲块

补充：chunkid_t 是 chunk 的 ID 类型（即 os_size_t），用偏移量（8 字节单位）标识 chunk 在堆中的位置；CHUNK_UNIT 为基本单位大小（= 8 字节），所有 chunk 大小是它的整数倍。

关键点 —— 桶数组与内存布局：

① 内存布局：struct z_heap + buckets 连续存放

堆的起始地址 addr 直接强转成 struct z_heap *，z_heap 结构和桶数组 buckets 连续存放在堆的开头，共同构成 chunk0（id=0 的元数据 chunk）：

  • buckets 指针计算：addr + CHUNK_UNIT * _k_chunksz(sizeof(struct z_heap))——先算 z_heap 占多少个 8 字节 chunk，再偏移到桶数组。
  • 一个桶就是 struct z_heap_bucket（只含一个 chunkid_t next），桶数组共 nb_buckets 个。

② 桶索引计算：__builtin_clz 实现 O(1) 定位

桶按大小指数级分档（第 0 桶最小、第 1 桶 2×、第 2 桶 4×…）。_k_bucket_idx 用 __builtin_clz（前导零计数）直接算出请求落在哪个 2 的幂区间：

usable_sz = (sz - _k_min_chunk_size(h) + 1);
b_idx     = (31 - __builtin_clz(usable_sz));

具体演算（假设 _k_min_chunk_size = 2，usable_sz = sz - 2 + 1）：

请求 chunk 数 szusable_sz二进制__builtin_clz桶索引 31-clz
210...01310
320...10301
430...11301
540...100292
870...111292
16150...1111283

结论：usable_sz 越大，前导 0 越少，桶索引越大。__builtin_clz 一条指令就得出桶索引，O(1) 复杂度，无需遍历所有桶。

③ avail_buckets 位图 + _k_ctz32 找最小非空桶

avail_buckets 是位图：第 N 位 = 1 表示第 N 个桶非空。精确桶没找到时，源码：

bmask = h->avail_buckets & ~((1 << (bi + 1)) - 1);   /* 只保留"比 bi 大"的位 */
minbucket = _k_ctz32(bmask & h->avail_buckets);      /* 最低位1的位置=最小非空桶 */

具体演算（假设 avail_buckets = 0b10110（桶 1、2、4 非空），请求桶 bi = 1）：

步骤值
avail_buckets0b10110（桶1、2、4非空）
(1 << (bi+1)) - 1 = (1<<2)-10b00011
~(0b00011)0b...11100
bmask = 0b10110 & 0b...111000b10100（桶2、4）
_k_ctz32(0b10100)2（最低位1在bit2）
最小非空桶桶 2

为什么"最小非空桶"最合适：FIRSTFIT 想找"刚好够大"的块。大于 bi 的最小非空桶中的块是能满足请求的最小尺寸块，避免拿超大块造成更多碎片。

④ 三个关键点串起来（完整分配寻块流程）

三个关键点的分工：

关键点作用复杂度
struct z_heap + buckets元数据布局：堆头 + 桶数组连续存放—
__builtin_clz从"请求大小"算目标桶索引O(1)
avail_buckets + _k_ctz32从"非空桶位图"找最小可用桶O(1)

正是 __builtin_clz 和 _k_ctz32 两个位操作，让 FIRSTFIT 的桶定位和最小非空桶查找都是 O(1)，配合"精确桶限 8 次尝试"，保证了分配的整体高效。

chunk 字段说明（内存中的 chunk 布局）：

字段含义
LEFT_SIZE左侧相邻 chunk 的大小（chunk 单位），用于反向遍历
SIZE_AND_USED当前 chunk 的大小（chunk 单位），最低位为使用标志（1=已用，0=空闲）
FREE_PREV空闲链表前驱 chunk ID（仅空闲块有效）
FREE_NEXT空闲链表后继 chunk ID（仅空闲块有效）
TASK_ID分配该块的任务指针（仅 OS_USING_MEM_TRACE 启用时）

字段宽度自适应：_k_big_heap() 判断堆大小，小堆（≤256KB）用 16 位字段、大堆用 32 位字段，节省元数据开销。

3.3 大小端适配

FIRSTFIT 根据堆大小自动选择字段宽度：

堆大小字段宽度最大支持
≤ 256KB16 位0x7FFF 个 chunk
> 256KB32 位约 16GB 堆空间

由 _k_big_heap() 函数自动判断。

四、优缺点分析

4.1 优点

优点说明
分配速度快从桶中直接取第一个足够大的块，常数时间操作
实现简单代码结构清晰，易于理解和维护
内存利用率高切分大块，剩余部分可继续使用
自动合并释放时自动与相邻空闲块合并，减少碎片
自适应字段宽度根据堆大小自动选择 16 位或 32 位字段，节省元数据开销

4.2 缺点

缺点说明
外部碎片长时间运行后，频繁分配/释放不同大小的块可能产生碎片
非确定性分配时间最坏情况下可能需要扫描多个桶
元数据开销每个 chunk 至少需要 4~8 字节的头部信息

五、适用场景

FIRSTFIT 算法适合以下场景：

  • ✅ 通用嵌入式应用：内存分配模式多样化，不要求最坏情况确定性
  • ✅ 内存资源有限：字段宽度自适应，节省元数据存储
  • ✅ 简单应用：不需要复杂的碎片管理策略
  • ✅ 快速原型开发：实现简单，调试方便

以下场景建议考虑 BUDDY 算法：

  • ❌ 频繁分配和释放小块内存
  • ❌ 对内存碎片非常敏感的系统
  • ❌ 需要更可预测的分配行为

六、内部工作流程

6.1 前置：最小块与桶索引

初始化第五步要调用 _k_bucket_idx 计算桶数，而它又依赖 _k_min_chunk_size（最小块基准）；_k_min_chunk_size 又取决于头部大小，头部大小由大小堆 _k_big_heap 决定。这三者环环相扣，且是分配/释放反复用到的核心函数。先把它们讲透，再看 6.2 初始化流程，否则流程会被大段函数剖析打断。

6.1.1 最小 chunk 数 _k_min_chunk_size

_k_min_chunk_size 表示"最小合法 chunk 数"，是 FIRSTFIT 分桶的基准。完整源码（kernel/source/os_mem_firstfit.c，与项目逐字一致）：

来源：kernel/source/os_mem_firstfit.c

OS_INLINE int32_t _k_min_chunk_size(struct z_heap *h)
{
#ifdef OS_USING_MEM_TRACE
    return _k_bytes_to_chunksz(h, 0);
#else
    return _k_bytes_to_chunksz(h, 1);
#endif
}

它依赖另外三个函数：

_k_min_chunk_size 分步讲解：

第一步：算头部字节 _k_chunk_header_bytes(h)

每个 chunk 都需要在开头存一段元数据头部（存块大小、是否已用、前后块指针等）。头部大小取决于配置：

  • OS_USING_MEM_TRACE（内存追踪开启）时头部更大，因为还要存任务指针 sizeof(os_task_t *)。
  • 小堆（非 big heap）头部 4 字节；大堆（_k_big_heap）头部 8 字节。
  • 默认（不追踪、小堆）= 4 字节。

第二步：算"头部 + 若干用户字节"换算成的 chunk 数 _k_bytes_to_chunksz(h, bytes)

_k_chunksz(bytes) 是把字节数向上取整到 8 字节倍数再除以 8，得到 chunk 数（(bytes + 7) / 8）。_k_bytes_to_chunksz 则是 _k_chunksz(头部 + 用户字节)——即"一个 chunk 从头部开始到用户数据结尾，一共占多少个 8 字节单元"。

第三步：_k_min_chunk_size 取两个值之一

  • OS_USING_MEM_TRACE 时 = _k_bytes_to_chunksz(h, 0) = 只装头部、0 用户字节的 chunk 数。
  • 否则 = _k_bytes_to_chunksz(h, 1) = 装头部 + 至少 1 字节用户数据的 chunk 数。

为什么要"至少 1 字节用户"？—— _k_min_chunk_size 的定义是"最小可分配块"

  • 非追踪（取 1 字节）：_k_min_chunk_size 衡量的是能被分配出去的最小块。一个块分配出去若连 1 字节用户数据都放不下，那它毫无分配价值。所以非追踪模式要求"头部 + 至少 1 字节用户"，保证每个最小 chunk 至少能真的分给用户 1 个字节。
  • 追踪（取 0 字节）：追踪模式头部本身巨大（8 + sizeof(os_task_t *)，如 12 或 16 字节），向上取整到 8 字节倍数后已占满整个 chunk，用户字节无从安放。此时限制因素是"头部要多大的 chunk 才装得下"，用户字节已无意义，故归 0——纯粹看头部大小。

一句话：非追踪时"最小块 = 能装下头部 + 1 字节载荷"；追踪时"最小块 = 能装下头部"。二者都保证 chunk 不会比头部还小。

数值演算（默认配置：不追踪、小堆，_k_chunk_header_bytes = 4）：

项计算结果
_k_chunk_header_bytes(h)默认小堆4 字节
无追踪时用户字节11 字节
头部 + 用户4 + 15 字节
_k_chunksz(5)(5 + 7) / 81 chunk
_k_min_chunk_size(h)_k_bytes_to_chunksz(h, 1)1 chunk

注意：_k_min_chunk_size 并不固定为 2。实际取哪个值由头部大小决定，本质是"能容纳头部 + 最小载荷"的 chunk 数。

为什么需要它做基准？ FIRSTFIT 里所有 chunk 都带头部，所以最小合法块不是 1 个裸 chunk，而是能装下头部 + 至少 1 字节的那个 chunk 数。桶 0 就应当容纳这个最小块。_k_min_chunk_size 就是拿来充当这个"最小档位"的基准，供 _k_bucket_idx 减去做偏移。

6.1.2 大小堆判断 _k_big_heap

_k_big_heap 不是靠配置开关，而是根据堆的实际大小和平台位宽自动判断的。相关源码（kernel/source/os_mem_firstfit.c，与项目逐字一致）：

来源：kernel/source/os_mem_firstfit.c

判断依据：_k_big_heap_chunks(chunks)，满足任一条即为大堆：

  1. sizeof(void *) > 4U：指针宽度大于 4 字节，即 64 位平台。只要在 64 位平台，无论堆多小都按大堆处理。
  2. chunks > 0x7fffU：chunk 总数超过 0x7fff = 32767。这是堆特别大的情况——32 位下若堆超过约 32767 × 8 字节 ≈ 256KB，16 位索引装不下块大小，必须升级到 32 位字段。

先理解前提：为什么 sizeof(void *) > 4 就代表 64 位平台？

  • 指针存的就是地址：void * 是指向任意地址的指针，它保存的是一个内存地址。
  • 地址位数 = 平台位数：32 位 CPU 的寄存器与地址总线都是 32 位，一个地址用 32 位（4 字节）表示 → sizeof(void *) = 4；64 位 CPU 同理 → sizeof(void *) = 8。
  • sizeof(void *) 是编译器编译期就确定的常量，直接等于目标平台的地址宽度，只有两种常见取值：4（32 位）或 8（64 位），不存在 5/6/7 字节的平台。

数值对照表：

平台地址宽度sizeof(void *)sizeof(void *) > 4U
32 位32 bit4 字节假（False）
64 位64 bit8 字节真（True）

因为取值只有 4 或 8，"大于 4"唯一等价于"等于 8"，即 64 位平台。为什么代码写 > 4U 而不写 == 8U？ 语义更稳：只要地址宽度超过 32 位（未来即便出现 128 位地址也能覆盖）就按"宽字段"处理，比硬编码 == 8 更通用、更健壮。

为什么 64 位平台一定判大堆？ 要理解这一点，得先看 chunk 头部里到底存什么、用什么宽度存。chunkid_t 是 chunk 的 ID 类型（typedef os_size_t chunkid_t），用于索引和 free 链表指针：

typedef os_size_t chunkid_t;   /* 32 位平台 os_size_t=4 字节，64 位平台=8 字节 */

头部字段（LEFT_SIZE、SIZE_AND_USED、FREE_PREV/FREE_NEXT）的存取宽度由大小堆决定：

  • 小堆用 uint16_t（2 字节）存字段 → 头部 4 字节（LEFT_SIZE+SIZE_AND_USED 各 16 位）。
  • 大堆用 uint32_t（4 字节）存字段 → 头部 8 字节。

64 位平台必须按大堆，原因有三：

  • ① chunkid_t 本身是 64 位：free 链表的 FREE_PREV/FREE_NEXT 存的是 chunkid_t（chunk ID）。64 位下它是 8 字节，若仍用小堆的 16 位字段存取，一个 64 位的 chunk ID 根本塞不进 2 字节，必然溢出、丢失高位，链表指针会错乱。所以必须用 32 位字段（大堆）。
  • ② 地址空间和堆容量：64 位平台可寻址空间巨大，堆大小理论上远超 32 位能表达的 0x7fff 上限。用 32 位字段才能表示足够大的块大小和索引，避免溢出。
  • ③ 一致性与对齐：64 位平台要求 8 字节对齐。头部若含 sizeof(os_task_t *)（追踪模式下为 8 字节指针），头部必须 8 字节对齐、大小是 8 的倍数——正好用 32 位字段拼出 8 字节头部。更重要的是，统一按大堆可避免"同一套代码里有的堆 16 位、有的堆 32 位"带来的复杂度与潜在 bug。

数值演算（chunkid_t 与头部字段宽度的关系）：

平台chunkid_t（os_size_t）大小堆头部字段宽度头部字节数
32 位4 字节小堆16 位（uint16_t）4
32 位4 字节大堆（堆>256KB）32 位（uint32_t）8
64 位8 字节大堆32 位（uint32_t）8

可见 64 位下 chunkid_t 是 8 字节，而头部字段统一用 32 位（4 字节）。这是"够用且统一"的折中：32 位字段已能表示 0~0xFFFFFFFF 的块大小（约 34GB），足以覆盖绝大多数 64 位堆，同时保持字段宽度一致、代码简单。

如何取值：判断用的是当前堆的 h->len（总 chunk 数）：

  • _k_big_heap(h) 用于 _k_chunk_header_bytes 等读写头部的场景，它查 h->len。
  • _k_big_heap_bytes(size) 用于 _k_heap_footer_bytes 等按字节数判断的场景，它把字节数先除以 8 换成 chunk 数再查。

为什么要分大小堆？ 这是空间换容量的取舍：

  • 小堆用 16 位（2 字节）字段存块大小/索引，头部仅 4 字节，内存紧凑、节省元数据开销。
  • 大堆（堆大或 64 位）必须用 32 位（4 字节）字段，头部 8 字节，才能表示更大的块大小和索引，避免溢出。

数值演算：

平台堆总 chunk 数 h->len_k_big_heap 结果原因
32 位1000（≈8KB）小堆sizeof(void*)=4 不>4，且 1000 ≤ 0x7fff
32 位0x8000 = 32768（≈256KB）大堆32768 > 0x7fff
64 位任意大堆sizeof(void*)=8 > 4

注意：头部大小是同一个堆内统一的（由 h->len 一次性决定），不会同一堆里有的块 4 字节、有的块 8 字节。初始化 _k_firstfit_mem_init 时就确定了 h->len，此后 _k_big_heap(h) 结果固定。

举例：一个 chunk 在内存里到底长什么样？

每个 chunk 是 8 字节的整数倍，头部紧挨在用户数据之前。以默认配置（小堆、不追踪，头部 4 字节）为例，一个最小 chunk（1 个 chunk = 8 字节）布局如下：

内存地址偏移  0    1    2    3    4    5    6    7        （单位：字节）
           ┌─────────────────────────┬─────────────────────┐
chunk 0    │  头部 4 字节（元数据）   │  用户数据 4 字节      │
           └─────────────────────────┴─────────────────────┘
           ←──────────── 1 个 chunk = 8 字节 ─────────────→
  • 头部 4 字节用来存 chunk_size（块大小）、used（是否已用）、前后块指针等。
  • 用户申请到的 mem 指针返回的是头部之后的地址（偏移 4 处），用户数据最多可写 4 字节，正好凑满 8 字节。
  • 若头部是 8 字节（大堆），则最小 chunk（8 字节）就被头部占满、容不下任何用户字节，所以此时 _k_min_chunk_size 取 _k_bytes_to_chunksz(h, 0)（0 用户字节），即至少 1 个 chunk 只放头部。

数值演算：不同配置下头部字节数与"最小 chunk 数"的对应关系：

配置_k_big_heap头部字节数最小 chunk 数 _k_min_chunk_size
不追踪、小堆否4_k_chunksz(4+1)=1
不追踪、大堆是8_k_chunksz(8+1)=2
追踪、小堆否4 + sizeof(os_task_t*)（=4/8）视指针宽度而定

以"不追踪、大堆"为例：头部 8 字节 + 至少 1 字节用户 = 9 字节，_k_chunksz(9) = (9+7)/8 = 2 chunk。这就是为什么配置不同时 _k_min_chunk_size 可能是 1、也可能是 2 或更大。

6.1.3 桶索引 _k_bucket_idx

_k_bucket_idx 是 FIRSTFIT 最核心的位运算函数：它用一条指令 __builtin_clz（前导零计数）算出"某个 chunk 数落在哪个 2 的幂桶"，O(1) 定位，无需遍历所有桶。完整源码（kernel/source/os_mem_firstfit.c，与项目逐字一致）：

来源：kernel/source/os_mem_firstfit.c

分步详解：

第一步：把请求大小换算成"从 1 开始的相对大小" usable_sz（无条件执行）

    usable_sz = (sz - _k_min_chunk_size(h) + 1);

sz 从哪来？—— 它是"含头部的绝对 chunk 数"

sz 不是用户直接报的字节数，而是经过上层 _k_bytes_to_chunksz 换算后的 chunk 数，且已经含头部。换算链路（默认小堆、不追踪，头部 4 字节）：

OS_INLINE os_size_t _k_bytes_to_chunksz(struct z_heap *h, os_size_t bytes)
{
    return _k_chunksz(_k_chunk_header_bytes(h) + bytes);   /* (头部 + 用户字节) 向上取整到 8 字节倍数，再 /8 */
}

数值演算：用户申请 bytes = 12 字节时：

项计算结果
头部默认小堆4 字节
头部 + 用户字节4 + 1216 字节
_k_chunksz(16) = (16 + 7) / 8向上取整到 8 倍数再 /82 chunk
sz_k_bytes_to_chunksz(h, 12)2 chunk

所以 sz 表示"这个请求连同头部一共占几个 8 字节单元"。它总是 ≥ _k_min_chunk_size（因为至少包含一个最小块）。

为什么减 _k_min_chunk_size？—— 把"绝对 chunk 数"平移成"相对最小块的倍数"

_k_min_chunk_size 是最小合法块（= 能装下头部 + 1 字节的 chunk 数，见 6.1.1）。所有请求都"至少"这么大，所以 sz - _k_min_chunk_size 得到的是相对最小块"多出几个 chunk"：

  • 最小块自身：sz = _k_min_chunk_size，sz - _k_min_chunk_size = 0（不多出任何 chunk）。
  • 更大的块：多出的 chunk 数依次递增。

这一步的实质是把绝对刻度（chunk 编号）换成相对刻度（以最小块为 0 起点），这样桶 0 就能精确对应"最小块"这一档。

为什么还要 +1？—— 两个作用

  • ① 保证 __builtin_clz 输入 ≥ 1：最小块减完是 0，而 __builtin_clz(0) 是未定义行为（0 没有"最高位 1"）。+1 后最小块 usable_sz = 1，__builtin_clz(1) = 31 有定义。
  • ② 让"相对大小"从 1 开始计：usable_sz 表示"最小块的 1 倍、2 倍、3 倍…"，从 1 起，正好和 floor(log2) 的桶号从 0 起对齐。

三点串起来看（数值演算，_k_min_chunk_size = 1，即最小块 = 1 chunk）：

请求 sz（含头部）绝对含义sz - 1（相对最小块多出）usable_sz = (sz-1)+1相对大小桶索引 floor(log2)
1（最小块）头部+1字节01最小块 1 倍0
22 chunk122 倍1
33 chunk233 倍1
44 chunk344 倍2
55 chunk455 倍2

观察要点：

  • usable_sz 恰好 = 请求是"最小块的几倍"。
  • 最小块（sz = 1）→ usable_sz = 1 → 桶 0；2、3 → 桶 1；4、5 → 桶 2。最小块被精确锁定在桶 0。
  • 若换成 _k_min_chunk_size = 2 的配置，最小块 sz = 2，同样 usable_sz = 2 - 2 + 1 = 1 落桶 0。公式不依赖具体基准值，基准变了结果依然正确。

为什么桶索引要这样"错位"？ 桶 0 必须能容纳最小块（含头部），而不是 1 个裸 chunk。若直接对 sz 取 floor(log2)，最小块（sz = min，如 min = 1）会落到桶 0，但 sz = 2、3 这些更大但仍属小块的请求会提前落入高位桶，浪费桶空间并加剧碎片。-min+1 让桶 0 精确对应 [min, 2·min) 这个最小档位，之后每档 2 倍，分档更贴合实际分配需求。

第二步：31 - __builtin_clz(usable_sz) 算出桶索引 b_idx（无条件执行）

    b_idx = (31 - __builtin_clz(usable_sz));

__builtin_clz 是什么？

  • __builtin_clz(x) 是 GCC/Clang 编译器的内置函数（builtin），不是库函数，无需 #include 任何头文件，编译时直接被编译器识别。
  • 语义：前导零计数（count leading zeros）——返回 unsigned int 类型 x 的 32 位二进制表示中，最高位 1 之前连续 0 的个数。
  • 结果范围：x ≥ 1 时，结果在 0 ~ 31；x = 0 时结果未定义（0 没有最高位 1），这正是前面第一步"+1 保证 usable_sz ≥ 1"的原因。
  • 效率：它在底层映射为一条硬件指令（ARM 上的 CLZ、x86 上的 LZCNT），一条指令完成，因此是 O(1) 的。

__builtin_clz 数值演算（32 位，高位省略为 0...）：

xx 的 32 位二进制（示意）前导 0 个数 __builtin_clz(x)
10...000131
20...001030
30...001130
40...010029
80...100028
5110...11111111123

规律：x 越大、最高位越靠左，前导 0 越少；__builtin_clz 恰好定位到"最高位 1 的位置"。

为什么 31 - __builtin_clz(usable_sz) = floor(log2(usable_sz))？

32 位二进制有 31~0 共 32 个位。最高位 1 之前有 clz 个 0，则最高位 1 在第 31 - clz 位（从 0 计）。第 n 位的权值是 2^n，而"最高位 1 所在的位数"正是 floor(log2(x))：

  • usable_sz = 8：二进制 0...01000，前导 0 共 28 个，最高位在 31-28 = 3 位，权值 2^3 = 8，floor(log2(8)) = 3。
  • usable_sz = 5：二进制 0...0101，前导 0 共 29 个，最高位在 31-29 = 2 位，权值 2^2 = 4，floor(log2(5)) = 2。

它如何完成指数分档？

floor(log2(usable_sz)) 把 usable_sz 分到 [2^k, 2^(k+1)) 区间，区间号 b_idx = k，正好对应桶的指数分档——同区间（同桶）内的请求大小相差不超过 2 倍，桶号由最高位唯一决定，一条指令算出，无需遍历任何桶或查表。

第三步：if (b_idx < 0) 越界兜底（条件执行）

    if (b_idx < 0)
    {
        os_kprintf("warning, invalid bucket_idx:%d sz:%d\r\n", b_idx, sz);
        b_idx = 0;
    }

__builtin_clz 返回无符号数，理论上 b_idx 不会为负；这里把 b_idx 声明为 int32_t，仅当 usable_sz 因异常为 0（此时 clz 行为未定义，极端情况可能得到 32，使 b_idx = 31-32 = -1）时，才打印告警并强制归到桶 0，防止数组越界访问 h->buckets[-1]。它是防御性保护，正常路径不触发。

条件走向总结（树状图）：

数值演算（假设 buf_sz = 512，_k_min_chunk_size = 2）：

buf_sz 中文含义：堆总 chunk 数，即对齐后整堆按 8 字节切分的单元总数，也是堆能表示的最大请求大小（(end - addr) / CHUNK_UNIT）。_k_min_chunk_size = 最小合法 chunk 数（桶 0 的基准，能装下头部 + 最小载荷的 chunk 数）。

逐步推导：

步骤计算结果说明
① usable_sz512 - 2 + 1511把整堆 chunk 数 512 平移到"相对最小块（2 chunk）"，得到 511
② __builtin_clz(511)511 的 32 位二进制 0b...0111111111（高 23 位全 0）23最高位 1 在第 8 位，之前有 23 个前导 0
③ _k_bucket_idx(h, 512)31 - 238最高位 1 位置 = floor(log2(511)) = 8，即最大桶索引
④ nb_buckets8 + 19桶索引从 0 起，共 9 个桶

511 为什么前导 0 是 23？ 511 = 2^9 - 1 = 0b0111111111（9 个 1）。32 位下最高位 1 在第 8 位，其前面 9~31 位共 23 个 0，所以 __builtin_clz(511) = 23；31 - 23 = 8，最高位位置即 floor(log2(511)) = 8。

9 个桶的区间映射（关键）：每个桶不是恰好对应一个 2 的幂单点，而是覆盖一个大小区间。由于 _k_min_chunk_size = 2，桶 k 容纳"相对最小块多出 [2^k, 2^(k+1)) 个 chunk"的请求：

桶索引 k相对多出范围 usable_sz请求 chunk 数 sz 范围覆盖的 2 的幂级别（示意）
0[1, 2)2 ~ 22
1[2, 4)3 ~ 44
2[4, 8)5 ~ 88
3[8, 16)9 ~ 1616
4[16, 32)17 ~ 3232
5[32, 64)33 ~ 6464
6[64, 128)65 ~ 128128
7[128, 256)129 ~ 256256
8[256, 512)257 ~ 512512

上面的"对应 2、4、8、…512"应理解为每个桶区间所容纳的最大 2 的幂（桶 k 的最大可达 2^k 级别的块），而非桶只装一个精确大小。例如桶 2 实际容纳 sz = 5~8 的所有请求。

验证边界：

  • 最小请求：sz = _k_min_chunk_size = 2 → usable_sz = 2 - 2 + 1 = 1 → floor(log2(1)) = 0 → 桶 0 ✓
  • 最大请求：sz = buf_sz = 512 → usable_sz = 511 → floor(log2(511)) = 8 → 桶 8 ✓

为什么桶数 = 最大索引 + 1：每个桶覆盖一个 2 的幂大小区间，必须能覆盖从最小块（桶 0）到最大可能请求（整个堆 buf_sz，桶 _k_bucket_idx(h, buf_sz)）的所有大小。索引从 0 开始，所以桶总数 = 最大索引 + 1。9 个桶恰好覆盖 sz ∈ [2, 512] 全部 9 个 2 的幂档位。

6.2 初始化

完整源码（kernel/source/os_mem_firstfit.c，与项目一致）：

分步详解：

第一步：创建并发保护信号量（无条件执行）

    os_semaphore_create(&h_mem->sem_id, "mem_f_sem", 1, 1);

进入本步的条件：调用 _k_firstfit_mem_init() 时无条件执行。创建名为 "mem_f_sem" 的二值信号量（初始值 1，最大值 1），用于保护后续分配/释放的互斥（对应 struct heap_mem.sem_id）。

为什么要创建并发保护信号量？

① 堆是共享资源，分配/释放可能被并发调用

堆是所有任务共用的全局内存池。任意任务都可能随时调用 os_malloc / os_free 来分配或释放内存，而这些调用最终都落到同一个堆（同一个 struct heap_mem）。也就是说，多个任务可能同时执行堆的分配/释放。

② 分配/释放不是原子操作

_k_alloc_chunk / _k_free_chunk 涉及对空闲链表、桶、chunk 头部等多处共享状态的读写，是一段非原子的多步操作。例如：

  • 分配时要：查桶 → 从链表移除块 → 更新 h->avail_buckets → 改 chunk 头部。
  • 这些步骤之间若被其他任务打断，会出现竞态（race condition）。

③ 不保护会出什么问题（竞态危害）

场景后果
两个任务同时分配，都读到同一个空闲块同一个块被分配两次（重复分配）
一个任务移除块时，另一个任务也在改链表链表指针错乱、损坏空闲链表
分配与释放交错统计信息 mem_used 不准，甚至堆内存损坏

④ 信号量如何解决

二值信号量（初始值 1）在这里当作互斥锁：

  • 任务在分配/释放开始时 os_semaphore_wait（把信号量从 1 减到 0）。
  • 此时其他任务再 wait 会阻塞，直到持有者 os_semaphore_post（恢复到 1）。
  • 保证同一时刻只有一个任务在操作堆，实现互斥。
任务 A                            任务 B
  │                                │
  ├─ wait（信号量 1→0，获取锁）      │
  ├─ 分配内存（独占）               │
  │                                ├─ wait（信号量为 0，阻塞等待）
  ├─ post（信号量 0→1，释放锁）      │
  │                                ├─ 被唤醒，获取锁，继续分配
  └─                                └─ post

⑤ 为什么用二值信号量（初始 1、最大 1）而非其他

  • 这里是"一次只允许一个"，本质是互斥量语义，所以初始值和最大值都是 1。
  • 若用计数信号量（值 > 1），会允许多个任务同时进堆，就无法保证互斥了。
  • 整个堆只有一把锁，覆盖所有分配/释放操作，简单可靠。

⑥ 关键点：这个信号量是在初始化时创建一次，之后整个堆生命周期都复用它。它存在 struct heap_mem.sem_id 里，分配（_k_firstfit_mem_alloc）、释放（_k_firstfit_mem_free）、realloc 等函数都会 wait/post 这把锁来保证互斥。

第二步：参数校验（条件：堆大小合法）—— 不满足则断言崩溃

    OS_ASSERT_EX(bytes / CHUNK_UNIT <= 0xffffffffU, "mem size is too big");
    OS_ASSERT_EX(bytes > _k_heap_footer_bytes(bytes), "mem size is too small");
    bytes -= _k_heap_footer_bytes(bytes);

进入本步的条件：第一步完成。

  • OS_ASSERT_EX(bytes / CHUNK_UNIT <= 0xffffffffU, "mem size is too big")：条件堆大小除以 8 不超过 32 位计数范围（不能太大）。
  • OS_ASSERT_EX(bytes > _k_heap_footer_bytes(bytes), "mem size is too small")：条件堆大小大于结尾标记 chunk 的头部（不能太小）。
  • 减去结尾标记 chunk 的头部大小：bytes -= _k_heap_footer_bytes(bytes)——预留最后一个标记 chunk 的空间。

第三步：地址对齐 + 计算 chunk 数（无条件执行）

    addr   = ROUND_UP(mem, CHUNK_UNIT);
    end    = ROUND_DOWN((uint8_t *)mem + bytes, CHUNK_UNIT);
    buf_sz = (end - addr) / CHUNK_UNIT;

    CHECK(end > addr);
    FIRSTFIT_MEM_INFO_INIT(h_mem, buf_sz * CHUNK_UNIT);
    OS_ASSERT_EX(buf_sz > _k_chunksz(sizeof(struct z_heap)), "mem size is too small");

进入本步的条件：第二步完成。

  • addr = ROUND_UP(mem, CHUNK_UNIT)：起始地址向上对齐到 8 字节边界。
  • end = ROUND_DOWN(mem+bytes, CHUNK_UNIT)：结束地址向下对齐。
  • buf_sz = (end - addr) / CHUNK_UNIT：总 chunk 数。
  • FIRSTFIT_MEM_INFO_INIT：初始化 h_mem 的 mem_total（= buf_sz * 8）、mem_used = 0、mem_maxused = 0。
  • 条件 buf_sz 必须大于 struct z_heap 所需的 chunk 数（太小无法容纳元数据）。

第四步：初始化 z_heap 结构体（无条件执行）

    h                  = (struct z_heap *)addr;
    h->chunk0_hdr_area = 0;
    h->len             = buf_sz;
    h->avail_buckets   = 0;
    h->buckets         = (void *)(addr + CHUNK_UNIT * _k_chunksz(sizeof(struct z_heap)));
    h_mem->header      = h;

进入本步的条件：第三步完成。

  • h = (struct z_heap *)addr：堆起始地址即 struct z_heap（z_heap 占用 chunk0）。
  • h->len = buf_sz：记录总 chunk 数。
  • h->avail_buckets = 0：初始无非空桶。
  • h->buckets = addr + CHUNK_UNIT * _k_chunksz(sizeof(struct z_heap))：桶数组紧随 z_heap。
  • h_mem->header = h：把 h_mem->header 指向 struct z_heap（供 alloc/free 使用）。

第五步：计算桶数和 chunk0 大小（无条件执行）

    nb_buckets  = _k_bucket_idx(h, buf_sz) + 1;
    chunk0_size = _k_chunksz(sizeof(struct z_heap)) + _k_chunksz(nb_buckets * sizeof(struct z_heap_bucket));

    OS_ASSERT_EX(chunk0_size + _k_min_chunk_size(h) < buf_sz, "mem size is too small");

    for (i = 0; i < nb_buckets; i++)
    {
        h->buckets[i].next = 0;
    }

进入本步的条件：第四步完成。本步要回答三个问题：桶要开多少个？chunk0 占多大？桶是否够装所有大小？

第一行：nb_buckets = _k_bucket_idx(h, buf_sz) + 1 —— 计算桶数量

    nb_buckets = _k_bucket_idx(h, buf_sz) + 1;

_k_bucket_idx 是 FIRSTFIT 最核心的位运算函数：它用一条指令 __builtin_clz（前导零计数）算出"某个 chunk 数落在哪个 2 的幂桶"，O(1) 定位，无需遍历所有桶。其完整源码、_k_min_chunk_size（最小块基准）与 _k_big_heap（大小堆）的逐一详解，已在前面 6.1.1~6.1.3 讲过，此处不再重复。 这里只说明在"算桶数"场景下的作用：

  • 传入 buf_sz（整堆的 chunk 数，也就是能表示的最大请求大小），_k_bucket_idx(h, buf_sz) 算出最大桶索引。
  • 桶索引从 0 开始，所以桶总数 = 最大索引 + 1，即 nb_buckets = _k_bucket_idx(h, buf_sz) + 1。

数值演算：假设 buf_sz = 512、_k_min_chunk_size = 2 时，_k_bucket_idx(h, 512) = 8，故 nb_buckets = 8 + 1 = 9 个桶（索引 0~8，覆盖 sz ∈ [2, 512] 的 9 个 2 的幂档位）。完整分步推导与桶区间映射表见 6.1.3，此处不重复。

为什么桶数 = 最大索引 + 1：每个桶覆盖一个 2 的幂大小区间，必须能覆盖从最小块（桶 0）到最大可能请求（整个堆 buf_sz，桶 _k_bucket_idx(h, buf_sz)）的所有大小，所以桶索引要延伸到 _k_bucket_idx(h, buf_sz)。

第二行：chunk0_size —— 计算 chunk0 占用大小

    chunk0_size = _k_chunksz(sizeof(struct z_heap)) + _k_chunksz(nb_buckets * sizeof(struct z_heap_bucket));
  • _k_chunksz(n)：把字节数 n 向上取整到 chunk 数（(n + CHUNK_UNIT - 1) / CHUNK_UNIT）。
  • _k_chunksz(sizeof(struct z_heap))：struct z_heap 占的 chunk 数。
  • _k_chunksz(nb_buckets * sizeof(struct z_heap_bucket))：整个桶数组占的 chunk 数。
  • 两者相加 = chunk0 的总大小（z_heap + 桶数组），单位是 chunk。

数值演算（沿用上例，nb_buckets = 9）：

项计算结果
sizeof(struct z_heap)假设 24 字节24
_k_chunksz(24)(24+7)/83 chunk
sizeof(struct z_heap_bucket)sizeof(chunkid_t) = 4 字节4
nb_buckets * 49 * 436 字节
_k_chunksz(36)(36+7)/85 chunk
chunk0_size3 + 58 chunk

chunk0_size = 8 chunk（= 64 字节），它既容纳 struct z_heap，也容纳 9 个桶。

第三行：OS_ASSERT_EX —— 校验堆是否够大

    OS_ASSERT_EX(chunk0_size + _k_min_chunk_size(h) < buf_sz, "mem size is too small");
  • 条件 chunk0_size + _k_min_chunk_size(h) < buf_sz：chunk0（元数据）+ 最少一个可用 chunk 必须小于总 chunk 数。
  • 若不满足 → 断言崩溃 mem size is too small（堆太小，装下元数据后连一个可分配的最小 chunk 都放不下）。

为什么要有这个校验：堆至少要能容纳"chunk0 元数据 + 1 个最小空闲块 + 1 个结尾标记"。若 chunk0_size 已接近 buf_sz，剩下的空间不足以提供任何可用内存，初始化无意义。

第四行：清空所有桶 —— 初始化空闲链表为空

    for (i = 0; i < nb_buckets; i++)
    {
        h->buckets[i].next = 0;
    }
  • 遍历所有桶，把每个桶的 next 初始化为 0（chunk ID 0 表示空链表）。
  • 此刻堆还没加入任何空闲块，所以所有桶都是空。后续 _k_free_list_add 才会把空闲块挂到对应桶。

本步与内存布局的关系（图解）：

关键结论：本步确定了桶数量（覆盖最大块大小）、chunk0 大小（z_heap + 桶数组）、并校验堆足够大、清空所有桶。这为第六步创建 chunk0 和初始空闲块铺好基础。

补充：桶到底是怎么"创建"出来的？

桶不是动态分配（malloc）的，而是堆初始化时，从堆内存头部分出一块连续区域作为桶数组。整个过程在 _k_firstfit_mem_init 里完成：

  • 第 1 步（第五步）：nb_buckets = _k_bucket_idx(h, buf_sz) + 1 算出桶总数（覆盖最大请求的档位，见 6.1.3）。
  • 第 2 步（第四步）：h->buckets = addr + CHUNK_UNIT * _k_chunksz(sizeof(struct z_heap))——让 h->buckets 指向紧跟在 z_heap 结构之后的地址，这块区域就是桶数组。一个桶 = struct z_heap_bucket（只含一个 chunkid_t next，4 字节）。
  • 第 3 步（第五步）：for 循环把每个桶的 next 置 0，初始化为空链表。

数值演算（沿用 buf_sz = 512、nb_buckets = 9）：

项计算结果
单个桶大小sizeof(struct z_heap_bucket)4 字节
桶数组总字节9 × 436 字节
桶数组起始位置addr + 8 × _k_chunksz(sizeof(z_heap))紧邻 z_heap 之后
桶数组占 chunk 数_k_chunksz(36) = (36+7)/85 chunk

关键点：桶数组的大小由堆大小 buf_sz 在初始化时一次性算好，划在堆头（chunk0 元数据区），运行期桶的数量固定不变——分配/释放只会改变桶里挂的链表（next 指针），不会增减桶。桶数组不占用额外堆外内存，它是堆自己的一部分。

第六步：创建 chunk0 和初始空闲 chunk（无条件执行）

进入本步的条件：第五步完成。

  • chunk0（id=0）：大小 = chunk0_size，标记为已用（容纳 z_heap + 桶数组），计入 mem_used。
  • 初始空闲 chunk（id=chunk0_size）：大小 = buf_sz - chunk0_size，其 LEFT_SIZE = chunk0_size（左邻是 chunk0）。
  • 结尾标记 chunk（id=buf_sz）：大小 = 0，LEFT_SIZE = 剩余大小，标记为已用（防止越界）。
  • _k_free_list_add(h, chunk0_size)：把初始空闲 chunk 加入空闲链表。

关键点：初始化后堆布局为 [chunk0(已用,z_heap+桶)] [大空闲chunk] [标记chunk(已用)]。mem_used 记录的是已用的 chunk0，空闲大块待分配。

初始化流程速览：

_k_firstfit_mem_init() 流程：
├── ① 创建信号量 sem_id（保护并发）
├── ② 校验堆大小（不能太大/太小），预留结尾标记头部
├── ③ 地址对齐 → 计算总 chunk 数 buf_sz，初始化 mem_total
├── ④ 堆起始作为 z_heap，设 len/avail_buckets/buckets
├── ⑤ 计算桶数 nb_buckets 和 chunk0_size，清空桶
├── ⑥ 建 chunk0(已用) + 初始空闲 chunk + 结尾标记，初始空闲块入链表

6.3 分配流程

_k_firstfit_mem_alloc 完整源码（kernel/source/os_mem_firstfit.c，与项目一致）：

分步详解（_k_firstfit_mem_alloc）：

第一步：参数判断（条件：bytes != 0）—— 分配非零大小才进入

    mem = OS_NULL;
    if (0U != bytes)
    {
        h        = h_mem->header;
        chunk_sz = _k_bytes_to_chunksz(h, bytes);

        (void)os_semaphore_wait(&h_mem->sem_id, OS_WAIT_FOREVER);

进入本步的条件：bytes != 0（请求分配非零大小）。

  • chunk_sz = _k_bytes_to_chunksz(h, bytes)：把字节数换算成 chunk 数（含头部）。
  • os_semaphore_wait(&h_mem->sem_id, OS_WAIT_FOREVER)：获取信号量（进入临界区，阻止并发分配/释放）。

第二步：调用 _k_alloc_chunk 找空闲块（条件：存在合适块）—— 无块则释放信号量返回 OS_NULL

        c = _k_alloc_chunk(h, chunk_sz);
        if (0U == c)
        {
            /* no suitable mem. */
            (void)os_semaphore_post(&h_mem->sem_id);
        }

进入本步的条件：第一步信号量获取成功。

  • c = _k_alloc_chunk(h, chunk_sz)：调用 _k_alloc_chunk 在堆里寻找并取出一个合适的空闲块，返回其 chunk ID c（不是内存指针）。若找不到合适块则返回 0。
  • 子分支 A：条件 c == 0（_k_alloc_chunk 返回 0，没有合适的空闲块）→ 释放信号量，返回 OS_NULL（分配失败）。

_k_alloc_chunk 的完整源码、逐块解释、分步详解与条件走向，已单独整理到后面"6.4 核心辅助函数 _k_alloc_chunk"小节，此处不展开。

第三步：切分多余空间（条件：c 的 chunk 数 > 所需 chunk_sz）—— 剩余部分放回空闲链表

        else
        {
            if (_k_chunk_size(h, c) > chunk_sz)
            {
                _k_split_chunks(h, c, c + chunk_sz);
                _k_free_list_add(h, c + chunk_sz);
            }

进入本步的条件：c != 0（分配到块）。

  • 子分支：条件 _k_chunk_size(h, c) > chunk_sz（找到的块比需要的大）→ _k_split_chunks(h, c, c + chunk_sz) 把大块切分为"需要的部分 + 剩余部分"，剩余部分 _k_free_list_add 放回空闲链表。

第四步：标记已用 + 记录任务（条件：见前）—— 返回数据指针

进入本步的条件：第三步完成（无论是否切分）。

  • FIRSTFIT_MEM_USED_INC：增加 mem_used（并更新 mem_maxused 峰值）。
  • _k_set_chunk_task：记录分配该块的任务（仅 OS_USING_MEM_TRACE）。
  • _k_set_chunk_used(h, c, OS_TRUE)：标记 chunk 为已用。
  • os_semaphore_post：释放信号量（离开临界区）。
  • mem = _k_chunk_mem(h, c)：返回数据区指针（跳过 chunk 头部）。

_k_firstfit_mem_alloc 的 if-else 条件走向总结：

完整分配流程数值演算示例：

场景：默认小堆（头部 4 字节）、_k_min_chunk_size = 2。初始化完成后，桶 8 里挂着整块堆（初始空闲块 chunk ID = 100，大小 300 chunk），其余桶全空。现在调用 os_malloc(40) 申请 40 字节。

第一步：字节数 → chunk 数 + 获取信号量

项计算结果
头部 + 用户字节4 + 4044 字节
chunk_sz = _k_chunksz(44)(44 + 7) / 86 chunk
获取信号量os_semaphore_wait进入临界区

第二步：_k_alloc_chunk(h, 6) 找块

步骤计算结果
① 算桶usable_sz = 6 - 2 + 1 = 5，floor(log2(5)) = 2桶 2
② 精确桶尝试桶 2 的 b->next？0（桶 2 空）→ 跳过
③ 回退更大桶bmask = avail_buckets & ~((1<<3)-1)avail_buckets 只有桶 8 置位 → 命中桶 8
④ 取块_k_free_list_remove_bidx(h, 100, 8)取出块 100，返回 c = 100

因为精确桶（桶 2）是空的，_k_alloc_chunk 用 _k_ctz32 找到大于桶 2 的最小非空桶 = 桶 8，取其首块（ID 100，大小 300）。

第三步：切分多余空间

项计算结果
判断_k_chunk_size(100) = 300 > chunk_sz = 6？是
切分_k_split_chunks(h, 100, 100 + 6)拆成块 100（用 6 chunk）+ 块 106（余 294 chunk）
剩余入桶_k_free_list_add(h, 106)块 106（大小 294）挂回桶（桶索引按 294 算，仍是大桶）
切分前：  块100（空闲，300 chunk）│
切分后：  块100（6 chunk，待用）│ 块106（294 chunk，空闲挂回桶）│

第四步：标记已用 + 返回数据指针

项计算结果
统计FIRSTFIT_MEM_USED_INC(h_mem, 6 * 8)mem_used += 48 字节
标记_k_set_chunk_used(h, 100, OS_TRUE)块 100 标记已用
释放信号量os_semaphore_post离开临界区
返回_k_chunk_mem(h, 100)返回块 100 的数据区指针（跳过 4 字节头部）

内存状态变化示意：

分配前：  [z_heap+桶数组] [ 块100：整块堆空闲（300 chunk，挂在桶8） ]
分配后：  [z_heap+桶数组] [ 块100：已用（6 chunk） ] [ 块106：空闲（294 chunk，挂桶） ]
                                        ↑
                              os_malloc(40) 返回这里（块100的数据区）

要点：

  • 精确桶（桶 2）空时，通过位图 O(1) 回退到最小非空桶（桶 8），FIRSTFIT 总能找到"足够大"的块。
  • 找到的块比需要的大 → 切分，剩余部分挂回空闲链表，不浪费。
  • 返回的是数据区指针（跳过头部），用户拿到后直接使用。

6.4 核心辅助函数 _k_alloc_chunk

_k_alloc_chunk 是 FIRSTFIT 分配的核心寻块函数：它从桶里找到一个足够大的空闲块并取出来。它在持锁（信号量已 wait）前提下被调用，全程独占堆。下面完整讲解。

完整源码（kernel/source/os_mem_firstfit.c，与项目逐字一致）：

来源：kernel/source/os_mem_firstfit.c

逐行/逐块解释：

  • bi = _k_bucket_idx(h, sz)：算 sz 落在哪个桶（详见 6.1.3）；b = &h->buckets[bi]：b 指向该桶。
  • ret_c = 0：先假设失败，只有真正找到块才改 ret_c。
  • if (bi > _k_bucket_idx(h, h->len))：请求超过堆能表示的最大桶索引 → 非法请求，走空的 if 分支，ret_c 保持 0，返回 0。
  • else：合法请求，先尝试精确桶（if (b->next)），若未找到再回退更大桶（if (0 == ret_c)）。
  • _k_free_list_remove_bidx(h, c, bi)：把块 c 从桶 bi 的空闲链表摘下（这个块就被"取出"了）。
  • CHECK(_k_chunk_size(h, c) >= sz)：断言确认取出的块确实够大（若不够说明堆已损坏）。
  • return ret_c：返回找到的 chunk ID；若一直没找到，返回 0（表示失败）。

分步详解：

第一步：计算桶索引（无条件执行）

    bi = _k_bucket_idx(h, sz);
    b  = &h->buckets[bi];

进入本步的条件：调用 _k_alloc_chunk() 时无条件执行。_k_bucket_idx 用 __builtin_clz 计算 sz 对应的桶索引，b 指向该桶。

第二步：桶索引合法判断（条件：bi <= _k_bucket_idx(h, h->len)）—— 非法则返回 0

    if (bi > _k_bucket_idx(h, h->len))
    {
        /* Invaild.*/
    }

进入本步的条件：调用后判断。此处只贴非法分支（if）——if 分支体在源码中本就是空的（仅注释 /* Invaild.*/）；合法分支（else）内的"精确桶有限尝试"与"更大桶回退"逻辑，分别在下方第三步、第四步完整展开。

  • 条件 bi > _k_bucket_idx(h, h->len)（请求超过堆的最大容量桶）→ if 分支体为空、不执行任何操作，ret_c 保持 0，返回 0（分配失败）。

第三步：在精确桶中有限尝试（条件：b->next != 0，桶非空）—— 最多尝试 8 个块

进入本步的条件：桶索引合法且 b->next != 0（该桶非空）。

  • 从桶首开始，最多尝试 CONFIG_SYS_HEAP_ALLOC_LOOPS（=8）个块：

疑问：初始化时桶不都是空的吗？为什么这里 b->next != 0？

需要区分初始化过程中和初始化完成后两个时间点：

  • 初始化过程中（_k_firstfit_mem_init 的 for 循环把每个桶 next 置 0）桶确实全空。
  • 初始化最后一步 _k_free_list_add(h, chunk0_size) 会把整块剩余的堆（初始大空闲块）挂到对应桶！所以初始化一结束，堆里就已经有一个非空桶，并不是全空的。

而 _k_alloc_chunk 是运行期分配函数，它在初始化之后、堆开始被反复分配/释放时才被调用。此时 b->next != 0 完全可能成立，来源有两个：

  1. 初始化时挂入的初始大空闲块（第一次分配时它通常就在某个桶里）。
  2. 后续 os_free 释放回来的块——每次 _k_free_chunk / _k_free_list_add 都会把释放的块放回对应桶，桶里会不断累积空闲块。

所以"桶非空"是运行期常态，只有堆刚初始化完、且还没来得及放任何块时才会出现所有桶都空的情况。

  • 子分支：条件 _k_chunk_size(h, c) >= sz（该空闲块足够大）→ _k_free_list_remove_bidx 把它从空闲链表移除，ret_c = c，break。
  • 否则（该块太小）→ 移动到下一个空闲块 b->next = _k_next_free_chunk(h, c)，继续尝试。

为什么只试 8 个：源码注释说明——统计上，只要块大小近似均匀分布，试 3 个就有 7/8 概率命中；试 8 个能保证常数时间内大概率找到匹配块，从而保持"常数时间"复杂度，避免长时间扫描。

第四步：从更大桶取最小可用块（条件：精确桶未找到 ret_c == 0 且有更大非空桶）—— O(1) 用位图定位

进入本步的条件：ret_c == 0（精确桶 8 次尝试都未找到）且存在比当前桶更大的非空桶。

  • bmask = h->avail_buckets & ~((1 << (bi+1)) - 1)：把大于当前桶索引的所有桶的位保留。
  • _k_ctz32 找最小非空桶（位图最低位 1）。
  • 取该桶首块 c，_k_free_list_remove_bidx 移除，CHECK 确认足够大，ret_c = c。

_k_alloc_chunk 的 if-else 条件走向总结：

6.5 释放流程

_k_firstfit_mem_free 完整源码（kernel/source/os_mem_firstfit.c，与项目一致）：

分步详解（_k_firstfit_mem_free）：

第一步：指针判空（条件：mem != OS_NULL）—— 空指针则跳过

进入本步的条件：mem != OS_NULL（要释放的指针非空）。mem == OS_NULL 时释放是空操作（等价标准库 free(NULL) 安全）。

此处贴出 if (mem) 完整 if 块（含内部全部逻辑，逐字一致）；其内部的"地址校验 → 获取信号量 → double-free 检测 → 溢出检测 → 标记空闲并合并 → 释放信号量"六个环节，分别在下方第二步 ~ 第五步逐一详解。

第二步：内存地址合法性校验（无条件执行）—— 指针必须在堆范围内

        OS_ASSERT_EX((mem >= h_mem->header) && (((os_ubase_t)mem - (os_ubase_t)h_mem->header) <= h_mem->mem_total),
                     "unexpected mem addr (invalid addr?) for memory at %p",
                     mem);

        h = h_mem->header;
        c = _k_mem_to_chunkid(h, mem);

进入本步的条件：mem != OS_NULL。

  • 条件 mem 不在堆范围 [header, header+mem_total] 内 → 断言崩溃（mem 不是本堆的指针）。
  • c = _k_mem_to_chunkid(h, mem)：把指针换算成 chunk ID。

第三步：获取信号量 + 检测 double-free（无条件执行）—— 已空闲则断言

        (void)os_semaphore_wait(&h_mem->sem_id, OS_WAIT_FOREVER);
        OS_ASSERT_EX(_k_chunk_used(h, c), "unexpected mem state (double-free? or invalid addr?) for memory at %p", mem);

进入本步的条件：第二步校验通过。

  • os_semaphore_wait：获取信号量（进入临界区）。
  • 条件 _k_chunk_used(h, c) 为假（该 chunk 已被标记为空闲）→ 断言崩溃（double-free 检测）。

第四步：检测缓冲区溢出（无条件执行）—— 前后 chunk 边界不一致则断言

        OS_ASSERT_EX(_k_left_chunk(h, _k_right_chunk(h, c)) == c,
                     "corrupted mem bounds (buffer overflow?) for memory at %p",
                     mem);

进入本步的条件：第三步通过。

  • 条件 _k_left_chunk(h, _k_right_chunk(h, c)) != c（右侧 chunk 的"左邻"不是本 chunk）→ 断言崩溃——说明本 chunk 的头部或右侧边界被改写，通常是缓冲区溢出越界写导致。

第五步：更新统计 + 标记空闲 + 合并（无条件执行）—— 释放并合并相邻空闲块

        FIRSTFIT_MEM_USED_DEC(h_mem, _k_chunk_size(h, c) * CHUNK_UNIT);

        _k_set_chunk_used(h, c, OS_FALSE);
        _k_free_chunk(h, c);

        (void)os_semaphore_post(&h_mem->sem_id);
    }
}

进入本步的条件：第四步通过。

  • FIRSTFIT_MEM_USED_DEC：减少 mem_used。
  • _k_set_chunk_used(h, c, OS_FALSE)：标记该 chunk 为空闲。
  • _k_free_chunk(h, c)：尝试与相邻空闲块合并，然后加入空闲链表。其完整源码、分步详解见下方"6.6 核心辅助函数 _k_free_chunk"。
  • os_semaphore_post：释放信号量（离开临界区）。

_k_firstfit_mem_free 的 if-else 条件走向总结：

完整释放流程数值演算示例：

场景：延续 6.3 分配例子的结果——块 100（6 chunk）已用，块 106（294 chunk）空闲且挂在桶里（两个块相邻，_k_right_chunk(100) = 106）。现在 os_free(ptr100) 释放块 100，其中 ptr100 是块 100 的数据区指针。

第一步：指针判空 + 地址校验 + 获取信号量

项计算结果
判空if (mem) 即 ptr100非空，进入
地址校验ptr100 在堆范围内通过（在 [header, header+mem_total] 内）
取 chunk IDc = _k_mem_to_chunkid(h, ptr100)c = 100
获取信号量os_semaphore_wait进入临界区

第二步：double-free 检测 + 溢出检测

检测计算结果
double-free_k_chunk_used(h, 100)？块 100 是已用 → 通过（OS_TRUE）
溢出检测_k_left_chunk(h, _k_right_chunk(h, 100)) == 100？右邻是 106，左邻 106 的左是 100 → 通过

若块 100 已被释放（used = OS_FALSE），_k_chunk_used 返回假 → 断言崩溃，报 double-free；若左右边界不一致 → 报缓冲区溢出。

第三步：标记空闲 + 统计 + 合并

项计算结果
统计FIRSTFIT_MEM_USED_DEC(h_mem, 6 * 8)mem_used -= 48 字节
标记_k_set_chunk_used(h, 100, OS_FALSE)块 100 标记空闲
调用_k_free_chunk(h, 100)开始合并

_k_free_chunk(h, 100) 内部合并（条件：左右邻是否空闲）：

分支条件结果
右邻合并_k_chunk_used(h, 106)？块 106 空闲 → 走合并
右邻移除_k_free_list_remove(h, 106)把块 106 从桶里摘出
右邻合并_k_merge_chunks(h, 100, 106)块 100 和 106 合并成一个大块
左邻合并_k_chunk_used(h, 左邻)？块 100 左邻是 chunk0（元数据，非空闲）→ 不合并
入桶_k_free_list_add(h, 100)合并后的块挂回桶

合并后块大小：

项计算结果
合并块大小6 + 294300 chunk
合并块 chunk ID从块 100 起c = 100（重新入桶）
入哪个桶_k_bucket_idx(h, 300)最大桶（如桶 8）

内存状态变化示意：

释放前：  [z_heap+桶数组] [ 块100：已用（6 chunk） ] [ 块106：空闲（294 chunk，挂桶） ]
释放后：  [z_heap+桶数组] [ 合并块（300 chunk，空闲，挂桶） ]
                            ↑
                    块100 与右邻块106 合并成一个整块

要点：

  • os_free 拿的是数据区指针，_k_mem_to_chunkid 把它换算回 chunk ID。
  • double-free 和溢出检测在改状态前完成，一旦发现就断言，避免堆损坏扩散。
  • 释放时主动与相邻空闲块合并（本例子合并右邻 106），避免产生过多碎片，这正是 FIRSTFIT 保持堆整洁的关键。
  • 合并后的大块重新入桶，可继续被分配切分，形成"分配切分 → 释放合并"的完整闭环。

6.6 核心辅助函数 _k_free_chunk

_k_free_chunk 是释放时的合并函数：它把被释放的块与相邻空闲块合并，避免产生过多碎片，然后放回空闲链表。它在持锁前提下被调用。完整源码（kernel/source/os_mem_firstfit.c，与项目逐字一致）：

来源：kernel/source/os_mem_firstfit.c

分步详解：

第一步：与右侧空闲块合并（条件：右邻 chunk 空闲）—— 移除右块并合并

    if (!_k_chunk_used(h, _k_right_chunk(h, c)))
    {
        _k_free_list_remove(h, _k_right_chunk(h, c));
        _k_merge_chunks(h, c, _k_right_chunk(h, c));
    }

进入本步的条件：调用 _k_free_chunk() 时执行。

  • 条件 _k_right_chunk(h, c)（右邻）为空闲 → _k_free_list_remove 把右块从空闲链表移除，_k_merge_chunks(h, c, 右块) 合并为一个大空闲块（c 的大小 += 右块大小）。

第二步：与左侧空闲块合并（条件：左邻 chunk 空闲）—— 合并后 c 指向合并块

    if (!_k_chunk_used(h, _k_left_chunk(h, c)))
    {
        _k_free_list_remove(h, _k_left_chunk(h, c));
        _k_merge_chunks(h, _k_left_chunk(h, c), c);
        c = _k_left_chunk(h, c);
    }

进入本步的条件：第一步完成。

  • 条件 _k_left_chunk(h, c)（左邻）为空闲 → 移除左块、合并（左块 + c），并把 c 更新为左块（合并后的大块起点在左）。

第三步：加入空闲链表（无条件执行）

    _k_free_list_add(h, c);

进入本步的条件：第一步/第二步完成。把合并后（或未合并的）空闲块 c 加入空闲链表（按大小入桶）。

6.7 核心辅助函数 _k_free_list_add

_k_free_list_add 是把空闲块挂进对应桶的空闲链表的函数。分配切分后的剩余块、释放合并后的块，最终都要通过它入桶。完整源码（kernel/source/os_mem_firstfit.c，与项目逐字一致）：

来源：kernel/source/os_mem_firstfit.c

真正入链表的是它调用的 _k_free_list_add_bidx：

其中 _k_solo_free_header 用于判断"这个块是不是只放头部的孤立块"：

OS_INLINE os_bool_t _k_solo_free_header(struct z_heap *h, chunkid_t c)
{
    return (_k_big_heap(h) && _k_chunk_size(h, c) == 1U);
}

分步详解：

第一步：判断是否是"孤立头部块"（条件：_k_solo_free_header）

    if (!_k_solo_free_header(h, c))
    {
        bidx = _k_bucket_idx(h, _k_chunk_size(h, c));
        _k_free_list_add_bidx(h, c, bidx);
    }
  • _k_solo_free_header(h, c) = 大堆 且 块大小恰为 1 chunk。这种块只有头部、没有用户数据（在 6.1 讲过，大堆头部 8 字节占满最小 chunk），它不值得入桶（分配出去也没用）。
  • 条件 !_k_solo_free_header（不是孤立头部块）→ 算出该块大小对应的桶 bidx，调用 _k_free_list_add_bidx 真正入桶。
  • 条件 _k_solo_free_header 为真（是孤立头部块）→ 直接跳过，不入桶。

第二步：入桶 —— 分"空桶"和"非空桶"两种情况（条件：b->next == 0U）

  • 子分支 A：b->next == 0U（该桶为空）——这是该桶的第一个空闲块：
    • CHECK：确认 avail_buckets 里该桶位确实为 0（桶空则位图位应为 0）。
    • h->avail_buckets |= (1 << bidx)：置位该桶对应的位图位，标记"桶非空"（供 _k_ctz32 O(1) 找最小非空桶）。
    • b->next = c：桶链表头指向 c。
    • _k_set_prev_free_chunk(h, c, c) / _k_set_next_free_chunk(h, c, c)：c 的前驱和后继都指向自己，形成单节点循环链表。

第三步：非空桶 —— 插入到"next 指针之前"（条件：b->next != 0U）

  • 子分支 B：b->next != 0U（桶非空）——把 c 插到 b->next（即 second）之前：
    • second = b->next：取桶链表头 second；first = _k_prev_free_chunk(h, second)：取 second 的前驱 first。
    • 于是 first ⇄ second，把 c 插到中间：
      • c 的 prev = first，c 的 next = second
      • first 的 next = c，second 的 prev = c
    • 结果 first ⇄ c ⇄ second，c 成功入链（循环链表仍是循环的）。

综合数值演算示例（两种入桶情况用一个例子贯穿）：

下面的阶段一对应第二步的子分支 A（空桶），阶段二对应第三步的子分支 B（非空桶）。假设 _k_min_chunk_size = 2，观察桶 2（容纳 sz = 5~8 的空闲块）的链表变化。

阶段一（子分支 A：空桶）—— 桶 2 为空，释放块 A（chunk ID = 5，大小 5 chunk）入桶

步骤计算/操作结果
① 算桶_k_bucket_idx(h, 5)usable_sz=4 → floor(log2(4))=2 → 桶 2
② 判空b->next == 0U（桶 2 空）走子分支 A
③ 置位图avail_buckets |= (1<<2)avail_buckets 第 2 位置 1
④ 头指针b->next = 5桶 2 头指向块 A
⑤ 建环A 的 prev = A、A 的 next = A单节点循环链表
入桶前（桶 2 空）:  buckets[2].next = 0          avail_buckets 第2位 = 0
入桶后（桶 2 一个块）:
    buckets[2].next = 5
      5 ──► 5        ←  A.prev = A, A.next = A（自己指自己，循环链表）

阶段二（子分支 B：非空桶）—— 桶 2 已有块 A，再释放块 B（chunk ID = 8，大小 8 chunk）入桶

步骤计算/操作结果
① 算桶_k_bucket_idx(h, 8)usable_sz=7 → floor(log2(7))=2 → 桶 2（与 A 同桶）
② 判空b->next == 5（不为 0，桶非空）走子分支 B（else）
③ 取节点second = b->next = 5（块 A）；first = A.prev = 5此刻 first=second=5（单节点）
④ 插块把 B 插到 first 和 second 之间first ⇄ B ⇄ second，即 A ⇄ B ⇄ A
⑤ 更新A.next = 8，B.prev = 8，B.next = 5，A.prev = 5桶 2 变为两个节点
插入前（桶 2 有块 A）:  5 ──► 5        （A.prev=5, A.next=5）
插入后（桶 2 有 A、B）:  5 ──► 8 ──► 5
                        ↑           │
                        └───────────┘    （A.next=8, B.prev=8, B.next=5, A.prev=5）
                      buckets[2].next 仍指向 5（A）

注意：阶段二走的是子分支 B（非空桶），因为此时桶 2 里已有块 A，b->next 已非 0。插入后 buckets[2].next 仍指向 A（5），因为插到的是"next 指针之前"。下次 _k_alloc_chunk 从 b->next（A）开始扫描，保证不遗漏。

条件走向总结（树状图）：

为什么插入到"next 之前"而不是"next 之后"？ 这样每次新块都插在桶链表头附近，配合"分配时从 b->next 开始扫描"，保证最近释放的块最容易被再次分配（LIFO 局部性），提高缓存命中率。

关键点：入桶时必须同步维护两样东西——①桶链表指针（b->next、块的 prev/next），②位图 avail_buckets（桶是否非空）。只有两者一致，_k_alloc_chunk 才能用 _k_ctz32 位图 O(1) 找到最小非空桶。

补充：初始化时如何把初始空闲 chunk 加入空闲链表

初始化第六步在创建好 chunk0 后，调用了 _k_free_list_add(h, chunk0_size)，把"chunk0 之后整块剩余的堆"作为第一个初始空闲块挂进桶。这是堆里第一个空闲块，也正是它让"初始化一结束堆里就有一个非空桶"（解答了 6.4 中 b->next != 0 的疑问）。

这个初始空闲块有多大、进哪个桶？

  • 块大小：chunk0_size 是 z_heap + 桶数组占的 chunk 数（元数据区），所以"初始空闲块" = buf_sz - chunk0_size（整堆 chunk 数减去元数据区），是堆里最大的一块。
  • 进的桶：_k_free_list_add 里 bidx = _k_bucket_idx(h, _k_chunk_size(h, c))，即按这个最大块的大小，算出它落在哪个桶——通常是最高编号的桶（最大档位）。

数值演算（沿用 buf_sz = 512、nb_buckets = 9）：

项计算结果
初始空闲块大小buf_sz - chunk0_size = 512 - chunk0_size接近 512 的最大块
桶索引_k_bucket_idx(h, 约500)最大桶索引 8
入桶_k_free_list_add_bidx(h, c, 8)桶 8 从空变为单节点

过程演示（用 _k_free_list_add 的逻辑）：

初始时所有桶都空（for 循环清空），avail_buckets = 0。
执行 _k_free_list_add(h, chunk0_size)：
  ├─ _k_solo_free_header？ 否（这是整块大块，非孤立头部）
  ├─ bidx = _k_bucket_idx(最大块大小) = 8
  └─ _k_free_list_add_bidx(h, c, 8)：
       ├─ 桶 8 空（b->next == 0）→ 走子分支 A
       ├─ avail_buckets |= (1<<8)   （标记桶 8 非空）
       ├─ buckets[8].next = c       （桶 8 头指向初始大块）
       └─ c 的 prev/next 都指向自己（单节点循环链表）

结果：初始化完成后，avail_buckets 只置了桶 8 的位（其余桶仍空），桶 8 里挂着整块堆。第一次分配时，_k_alloc_chunk 若精确桶找不到块，就用 _k_ctz32 找到桶 8，从这块大空闲块上切出所需大小，剩余部分再 _k_free_list_add 挂回——这就开始了堆的第一次分配。

📝 本节小结

核心要点回顾

本节围绕 FIRSTFIT 首次适应算法展开，核心要点如下：

1. 核心思想

  • 以 chunk（8 字节） 为基本管理单位，空闲块按大小分桶（buckets），每个桶是双向循环链表。
  • 分配时从精确桶开始扫描，找到第一个足够大的块即分配；用 avail_buckets 位图 + _k_ctz32 实现 O(1) 找最小非空桶。

2. 分配流程（_k_alloc_chunk）

  • 精确桶最多尝试 CONFIG_SYS_HEAP_ALLOC_LOOPS（8）个块。
  • 精确桶找不到 → 从更大桶取最小可用块。
  • 找到的块过大 → _k_split_chunks 切分，剩余放回空闲链表。

3. 释放与合并（_k_free_chunk）

  • 释放时先与右邻合并，再与左邻合并（_k_merge_chunks），合并后入空闲链表。
  • 释放前做 double-free 检测和缓冲区溢出检测（断言）。

4. 字段宽度自适应

  • _k_big_heap() 判断堆大小：小堆（≤256KB）用 16 位字段，大堆用 32 位，节省元数据。

5. 并发保护

  • 每个内存区域用二值信号量（sem_id）保护分配/释放的互斥。

关键易错点速查

易错点正确做法
释放非 FIRSTFIT 堆分配的指针地址校验断言崩溃，必须释放本区域 k_alloc 返回的指针
重复释放同一块（double-free）_k_chunk_used 检测断言崩溃，禁止二次释放
缓冲区溢出越界写边界校验断言崩溃，分配时确保写入不超过请求大小
bytes == 0 的分配直接返回 OS_NULL，不进入分配流程
分配后未检查 OS_NULL_k_alloc_chunk 无合适块返回 0，调用方必须检查
混淆 chunk 数与字节数chunk 大小是 8 的整数倍，换算用 _k_chunksz/_k_bytes_to_chunksz

下一步

本节掌握了 FIRSTFIT 算法的原理与实现。接下来请学习下一小节：

OneOS-Lite 文档 | 学习阁
Copyright © 2026 学习阁