4.5 Block Allocator——lookahead与磨损均衡
你如何在一个4MB的Flash上找一块空地？
想象你现在正在LittleFS的内部。CTZ跳表刚决定要追加一个数据块——它调用lfs_alloc(lfs, &new_block)，说：“给我一个空闲块。”
你现在有1024个4KB的块。其中有些已经被目录和数据占用了，有些是空闲的。你必须在有界RAM的前提下（不能扫描1024个块并构建一个1024位的位图——等等，1024位是多少？128字节。但如果是8192个块呢？1024字节。如果是131072个块（512MB）呢？16KB。）——总之，LittleFS不能假设设备多小。它必须为任意大的设备提供O(1)内存的分配方案。
你的选择是什么？
选项A：在盘上维护一个空闲块位图。每次分配时读取它，每次释放时更新它。 → 问题：掉电时位图更新可能中断，导致“已分配的块被记录为空闲“（块泄漏）或“空闲块被记录为已分配“（永久丢失空间）。
选项B：在挂载时扫描一次全盘，构建一个内存中的位图。 → 问题：RAM占用与设备大小线性增长，违反有界RAM原则。而且扫描一次全盘在大型设备上可能要数秒。
选项C：完全不维护空闲块信息。每次需要空闲块时，遍历整个文件系统树，找到所有被引用的块，剩下的就是空闲的。每次从头开始选一个。 → 问题：O(n²)的分配时间，在大型设备上不可接受。
LittleFS选择了选项D——lookahead缓冲区。
Lookahead：一个在空闲块上滑动的窗口
Lookahead的核心思想是：用一个固定大小的位图——比如16字节（128位）——来缓存“当前区域“的空闲/占用状态。当这个区域里的空闲块用完后，扫描文件系统找到下一个区域，更新位图，继续分配。
Lookahead Buffer 工作示意
=========================================================
设备（128个块，用 0 表示空闲，1 表示占用）：
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
│1 │0 │1 │1 │1 │0 │0 │1 │0 │1 │0 │0 │1 │0 │1 │0 │0 │0 │1 │0 │ ...
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
\____________________/ \___________________________________/
lookahead 位图 还未扫描的区域
(32位 = 跟踪32个块)
// lfs_t 中的 lookahead 结构体
struct lfs_lookahead {
lfs_block_t start; // 当前窗口的起始块号
lfs_block_t size; // 窗口中还有多少blocks要检查
lfs_block_t next; // 窗口内的下一个位置
lfs_block_t ckpoint; // 距上次checkpoint以来检查过的块数
uint8_t *buffer; // 指向位图缓冲区的指针
};
lookahead位图的每一位对应一个物理块。“0“表示该块是空闲的（未被文件系统引用），“1“表示该块被占用。当你需要分配一个空闲块时，从next位置开始扫描位图，找到第一个值为0的位。
以16字节（128位）的lookahead缓冲区在128块（512KB）的设备上运行示例：
boot... lookahead:
fs blocks: fffff9fffffffffeffffffffffff0000
scanning... lookahead: fffff9ff ← 扫描找到一批空闲块
fs blocks: fffff9fffffffffeffffffffffff0000
alloc = 21 lookahead: fffffdff ← 分配了block 21
fs blocks: fffffdfffffffffeffffffffffff0000
alloc = 22 lookahead: ffffffff ← 分配了block 22
fs blocks: fffffffffffffffeffffffffffff0000
scanning... lookahead: fffffffe ← 窗口前移，重新扫描
fs blocks: fffffffffffffffeffffffffffff0000
alloc = 63 lookahead: ffffffff ← 分配了block 63
fs blocks: ffffffffffffffffffffffffffff0000
scanning... lookahead: ffffffff ← 扫描中……
scanning... lookahead: ffffffff ← 继续扫描
scanning... lookahead: ffff0000 ← 最后一段
alloc = 112 lookahead: ffff8000
fs blocks: ffffffffffffffffffffffffffff8000
当lookahead窗口中的空闲块用完时，lfs_alloc_scan被调用——它会遍历整个文件系统，在下一次扫描窗口内标记哪些块被占用。窗口在设备上不断向前滑动，形成一个环形扫描模式。
lfs_alloc：分配一个块的完整过程
// lfs.c:666-715 — lfs_alloc 的完整逻辑
static int lfs_alloc(lfs_t *lfs, lfs_block_t *block) {
while (true) {
// 1. 在当前lookahead窗口中找空闲块
while (lfs->lookahead.next < lfs->lookahead.size) {
if (!(lfs->lookahead.buffer[lfs->lookahead.next / 8]
& (1U << (lfs->lookahead.next % 8)))) {
// 找到了！这个块是空闲的
*block = (lfs->lookahead.start + lfs->lookahead.next)
% lfs->block_count;
// 提前找到下一个空闲块位置（优化后续分配）
while (true) {
lfs->lookahead.next += 1;
lfs->lookahead.ckpoint -= 1;
if (lfs->lookahead.next >= lfs->lookahead.size
|| !(lfs->lookahead.buffer[lfs->lookahead.next / 8]
& (1U << (lfs->lookahead.next % 8)))) {
return 0;
}
}
}
lfs->lookahead.next += 1;
lfs->lookahead.ckpoint -= 1;
}
// 2. 检查是否整个设备都扫描过了
if (lfs->lookahead.ckpoint <= 0) {
LFS_ERROR("No more free space 0x%"PRIx32,
(lfs->lookahead.start + lfs->lookahead.next)
% lfs->block_count);
return LFS_ERR_NOSPC;
}
// 3. 当前窗口用完了，需要扫描下一个窗口
int err = lfs_alloc_scan(lfs);
if(err) {
return err;
}
}
}
而lfs_alloc_scan的实现展示了lookahead窗口如何移动：
// lfs.c:641-662 — lfs_alloc_scan：填充lookahead缓冲区
static int lfs_alloc_scan(lfs_t *lfs) {
// 移动lookahead窗口到下一个位置
lfs->lookahead.start = (lfs->lookahead.start + lfs->lookahead.next)
% lfs->block_count;
lfs->lookahead.next = 0;
lfs->lookahead.size = lfs_min(
8*lfs->cfg->lookahead_size, // 位图能追踪的最大块数
lfs->lookahead.ckpoint); // 但不能超过剩余块数
// 初始化为全0（全空闲），然后标记已被占用的块
memset(lfs->lookahead.buffer, 0, lfs->cfg->lookahead_size);
// 遍历整个文件系统树，标记被占用的块
int err = lfs_fs_traverse_(lfs, lfs_alloc_lookahead, lfs, true);
if (err) {
lfs_alloc_drop(lfs);
return err;
}
return 0;
}
lfs_alloc_lookahead是一个回调函数，对每个被文件系统占用的块，它在lookahead位图中标记其为“1“：
// lfs.c:627-637 — 标记被占用的块
static int lfs_alloc_lookahead(void *p, lfs_block_t block) {
lfs_t *lfs = (lfs_t*)p;
lfs_block_t off = ((block - lfs->lookahead.start)
+ lfs->block_count) % lfs->block_count;
if (off < lfs->lookahead.size) {
lfs->lookahead.buffer[off / 8] |= 1U << (off % 8);
}
return 0;
}
遍历的开销： 每次lfs_alloc_scan会调用lfs_fs_traverse_遍历整个文件系统树——包括所有目录的metadata pair和所有文件的CTZ跳表。这个遍历本身的复杂度是O(已用块数)。但因为lookahead窗口一次性填充了多个空闲块，每次遍历的平摊成本是：O(已用块数 / lookahead可以追踪的块数)。
对于典型的配置（lookahead_size=16字节→128位，设备有1024块），一次扫描填充128个块的信息，每128次分配才需要一次全盘扫描。对于小设备的日常使用，这通常意味着只需要一到两次扫描。
checkpoint机制：防止无限循环
考虑一个边界情况：如果文件系统快满了，每次lfs_alloc_scan都找不到空闲块，lfs_alloc会不会一直绕圈扫描直到地老天荒？
答案是不会——因为有ckpoint（检查点）计数器。
// lfs.c:614-616 — 设置检查点
static void lfs_alloc_ckpoint(lfs_t *lfs) {
lfs->lookahead.ckpoint = lfs->block_count;
}
lfs_alloc_ckpoint在一次完整的、无等待的分配操作序列开始前被调用。它把ckpoint设置为总块数。每次扫描过一个块，ckpoint减1。如果ckpoint降到0，说明lookahead已经转了一圈，没有空闲块了——返回LFS_ERR_NOSPC（空间不足）。
这保证了分配器不会无限自旋。即使磁盘满了，它最多扫描一轮就会明确报告错误。
磨损均衡：藏在分配器里的隐形福利
LittleFS的磨损均衡是统计式的动态磨损均衡——它不主动追踪每个块的擦除次数（那需要按块存储擦除计数，代价是O(n)的内存），而是利用分配模式的自然随机性来近似均匀分布。
具体来说：
1. 线性循环分配（设备上电期间）。
lookahead窗口在设备上以线性循环的方式移动。每次lfs_alloc_scan都把窗口向前推进一段距离。这意味着在一次运行中，块按物理顺序被分配——块0、块1、块2……直到绕回。这已经提供了一层磨损分布：热点不会集中在某一块。
2. 随机起始偏移（每次挂载时）。
如果每次上电都从块0开始分配，那块0会比块1023经历更多次擦除。LittleFS通过在挂载时确定一个随机起始偏移来解决这个问题：
// 每次挂载时的随机种子生成（来自 DESIGN.md）
//
// ┌────────┐ \ probably random
// ┌│metadata│ | ^
// ││ │ +→ crc ───────────────────────→ xor
// ││ │ | ^
// │└────────┘ / │
// └───│──│──┘ │
// ┌─┘ └─────────────────────────┐ │
// │ │ │
// │ ┌──────────────→ xor ────────────→ xor
// │ │ ^ │ ^
// v crc crc v crc
// ┌────────┐ \ ^ ┌────────┐ \ ^ ┌────────┐ \ ^
// ┌│metadata│─│──│→│metadata│ │ │ ┌│metadata│ │ │
// ││ │ └──┘ ││ │ └──┘ ││ │ └──┘
// ││ │ │ ││ │ │ ││ │ │
// │└────────┘ / │└────────┘ / │└────────┘ /
// └──│──│──┘ └────│───┘ └──│──│──┘
随机数不是来自硬件RNG——而是整个文件系统所有metadata pair的CRC值依次异或的结果。 这非常巧妙：文件系统上的数据本身就是熵源——文件内容、创建时间、元数据排列……都在CRC中体现。只要文件系统在上次运行中被修改过，这次挂载时的CRC异或结果就会与前次不同，从而产生不同的分配起始偏移。
挂载时的seed被lfs_mount_设置为所有遍历过的metadata block的CRC的异或值。随后，lfs_alloc在第一次分配时用这个seed确定lookahead的起始位置。
3. 基于block_cycles的静态磨损级别。
除了动态磨损均衡，LittleFS还提供了一种基于擦除计数的“弱静态磨损均衡“：block_cycles参数。
当metadata pair的revision计数达到block_cycles的整数倍时，LittleFS会强制搬迁（relocate）这个metadata pair到两个全新的块上。这防止了一个频繁更新的目录把它的metadata block擦写穿。
// lfs.c:1940-1947 — 检查是否需要搬迁
static bool lfs_dir_needsrelocation(lfs_t *lfs, lfs_mdir_t *dir) {
// 如果 dir->rev+1 是 (block_cycles+1)|1 的倍数，触发搬迁
return (lfs->cfg->block_cycles > 0
&& ((dir->rev + 1) % ((lfs->cfg->block_cycles+1)|1) == 0));
}
|1是为了确保除数奇数，避免边界条件。如果block_cycles设为100，那么每100次compaction就会把metadata搬迁到新块上。对于root目录这种高频更新的metadata pair，这个机制非常重要。
坏块处理：检测+驱逐
LittleFS的坏块处理策略是“检测即驱逐“：
写入时检测： 每次写入后，lfs_bd_prog（带validate=true参数）会立即回读数据并比较。如果不一致，返回LFS_ERR_CORRUPT。
// lfs.c:228-272 — lfs_bd_prog 中的 validation
static int lfs_bd_prog(lfs_t *lfs,
lfs_cache_t *pcache, lfs_cache_t *rcache, bool validate,
lfs_block_t block, lfs_off_t off,
const void *buffer, lfs_size_t size) {
// ...
if (validate) {
// 写入后立即回读校验
lfs_cache_drop(lfs, rcache);
int res = lfs_bd_cmp(lfs, NULL, rcache, diff,
pcache->block, pcache->off, pcache->buffer, diff);
if (res != LFS_CMP_EQ) {
return LFS_ERR_CORRUPT; // 数据不匹配 → 坏块
}
}
// ...
}
驱逐： 在上层代码中，看到LFS_ERR_CORRUPT后跳转到relocate标签。在这个标签里，分配一个新块、把数据写到新块、旧块被遗弃——不再被文件系统引用，自然就变成了空闲块。
坏块检测与驱逐流程
=========================================================
┌──────┐
│ root │
└──────┘
v─┘ └──────────v
┌──────┐ ┌──────┐
│ A │ │ B │
└──────┘ └──────┘
. . v─┘ .
. . ┌──────┐.
. . │ C │.
. . │ │.
. . └──────┘.
. . . . .
写入C时发现坏块：
┌──────┐
│ root │
└──────┘
v─┘ └──────────v
┌──────┐ ┌──────┐
│ A │ │ B │
└──────┘ └──────┘
. . v─┘ .
. . ┌──────┐. ┌──────┐
. . │ bad │. │ C' │ ← 把数据重写到新块
. . │ blck │. │ │
. . └──────┘. └──────┘
更新B的指针指向C'：
┌──────┐
│ root │
└──────┘
v─┘ └──────────v
┌──────┐ ┌──────┐
│ A │ │ B' │ ← B也需要COW
└──────┘ └──────┘
. . . │ . └──────────v
. . . └──────┐ ┌──────┐
. . . . │ │ C' │
. . . . │ │ │
└──────┘ └──────┘
更新root指向B'：
┌──────┐
│ root │ ← root也需要COW
└──────┘
v─┘ └──v
┌──────┐ ┌──────┐
│ A │ │ B' │
└──────┘ └──────┘
. . . └───────────v
. . . . ┌──────┐
. . . . │ C' │
└──────┘
坏块成为垃圾，等待compaction回收
这个过程展示了COW结构的另一优势：坏块驱逐和COW搬迁可以用同一套机制处理——都只是“分配新块+写数据+更新父节点指针“的三步曲。
与KnotFS的块管理对比
KnotFS 块管理 vs LittleFS 块管理
===============================================================
块数量 16个（固定） 理论上不限（实际受设备大小限制）
空闲块查找 扫描free_bitmap（O(n)） lookahead位图（O(1)平摊）
只有16个块，开销很低 对于大设备是必要的
磨损均衡 显式wear_count数组 统计式动态磨损均衡
每块1个uint32（64 bytes） 不需要每块计数器
块回收 compact时释放 垃圾块不主动回收
通过free_bitmap标记 通过"drop on floor"策略
坏块处理 未实现 写入校验+自动重分配
===============================================================
KnotFS的块管理非常简单——因为它只有16个块。维护一个16位的free_bitmap和一个16×4=64字节的wear_count数组在RAM中是微不足道的。每次分配时扫描16个位，找到第一个空闲块，然后选其中wear_count最小的。这是把问题简化到极致。
LittleFS面对的块数量可能是KnotFS的100倍、1000倍。它必须在保持O(1)内存的前提下提供可接受的分配性能。lookahead方案是一个精妙的折中——它不是最快的，但它在任何设备大小下都能工作，且平摊性能在大多数场景下是O(1)。
垃圾回收的哲学：Drop it on the floor
LittleFS的块回收策略可以用一句话概括：不主动回收垃圾块。
当一个文件被删除时，它的CTZ跳表块和metadata pair块不会立即被“标记为空闲“。它们只是不再被任何metadata pair引用——文件系统树上没有路径能到达它们了。在COW操作的日常过程中，compaction自然会把不再被引用的块排除在外。下一次lfs_alloc_scan扫描时，这些块因为没有被文件系统树引用，会被视为空闲块。
这被称为“drop it on the floor“（丢在地上不理）策略。它的好处是：
- 不需要维护free list（免去掉电安全问题）
- 释放操作是O(1)（什么都不做）
- 坏块自然被遗忘（只要没人引用它）
代价是：已删除的空间不会立即可用——必须等到下一轮lookahead扫描经过那个区域。
一段关于熵的沉思
LittleFS的熵源——用CRC异或生成随机种子——是一个让人会心一笑的设计。
随机数在任何计算机系统中都是一个难题。在嵌入式系统上尤其如此：没有硬件RNG，没有操作系统提供的熵池，没有网络时间戳。上电后CPU寄存器的状态虽然是随机的，但你没法保证CRC在编译后不依赖那些初始化状态。
LittleFS的解决方案是：用文件系统自身的数据作为熵源。 每个metadata pair在挂载时被遍历，它的CRC被读取并异或到一个累加器中。这个累加器的最终值取决于所有metadata pair的内容——而metadata pair的内容取决于文件系统的历史修改序列。只要在设备的上一次运行中有过任何写操作，这次挂载时的CRC异或结果就几乎不可能与上一次相同。
这个设计的哲学含义是：文件系统本身就是它最可靠的随机源——因为它“记住了“自己的历史。 一个文件系统之所以需要磨损均衡，恰恰是因为它被使用过；而一个被使用过的文件系统，恰好携带着能使磨损均衡工作所需的“使用痕迹“。
这是一种自举式的优雅：问题创造了它自己的答案。
KnotFS 的块分配器比 lookahead 简单得多：只有 16 个块，一个 free_map 位图就够，不需要滑动窗口。KnotFS 的磨损均衡也比 LittleFS 更朴素——pick_lowest_wear 直接从所有空闲块中遍历选 wear 最小的，没有 block_cycles 的强制搬迁机制。LittleFS 的 lookahead 是为“块数可能上千、RAM 只有几 KB“的极端约束设计的；KnotFS 受益于教学场景的小规模——块数少到可以全量扫描，磨损跟踪不需要随机化的起始偏移。这两种设计的差异再一次说明：同一个问题，同一个理论基础，不同的约束会产生完全不同的实现。
下集预告
Metadata Pair 存元数据，CTZ Skip-List 存文件数据，Block Allocator 管空间分配——LittleFS 的三根支柱已经立起来了。但还有一个问题：文件是怎么组织的？目录树、文件名、路径解析——这些用户最直观感受到的东西，LittleFS 是怎么实现的？
下一节，我们进入 LittleFS 的目录系统。你会发现一个反直觉的事实：目录就是文件。 lfs_mkdir 和 lfs_file_open 在底层调的是同一个函数——区别只是一个 tag 类型。以及：threaded linked-list 如何让目录遍历在掉电后还能继续？
悬念留给：如果你的目录里有一万个文件，遍历到第 5000 个时突然断电——重启后遍历指针应该指向哪里？