5.6 块管理与磨损均衡——选最年轻的书架

选格子算法：pick_lowest_wear

第三章已经讲了磨损均衡的原理。这里直接看代码：KnotFS采用动态磨损均衡——只在分配新块时选择磨损最少的空闲块。

// knotfs.c — 选择磨损最少的空闲块
static uint32_t pick_lowest_wear(void) {
  uint32_t best = KNOTFS_BLOCK_COUNT;
  uint32_t best_w = 0xFFFFFFFFU;

  for (uint32_t i = KNOTFS_DATA_START; i < KNOTFS_BLOCK_COUNT; i++) {
    if (!(sb.free_map & (1U << i)) && sb.wear[i] < best_w) {
      best_w = sb.wear[i];
      best = i;
    }
  }
  return best;
}

算法步骤：

只扫描数据块区域（块2到块15）
跳过已使用的块（free_map中bit=1的块）
在空闲块中，选一个wear计数最小的
如果所有空闲块都相同（第一次使用前都是0），返回第一个扫描到的块（这里自然返回块2）

如果返回值是KNOTFS_BLOCK_COUNT（即16），说明没有空闲块了。调用者应该报错：

// knotfs.c — write操作中检查无空闲块
uint32_t blk = pick_lowest_wear();
if (blk >= KNOTFS_BLOCK_COUNT) {
  cur.result = ERR_NO_BLK;
  cur.st = ST_ERR;
  return;
}

这个算法的核心哲学是：永远选“最年轻“（被清空次数最少）的书架格子。

第一次使用：所有14个数据格的wear都是0 → 选格2。

下一次分配：格2的wear变成了1，格3~15的wear还是0 → 选格3。

再下一次：格2和格3的wear都是1，格4~15的wear还是0 → 选格4。

以此类推。使用的磨损从格2到格15均匀推进，像一把梳子从一端梳到另一端。到格15被用过之后，格2~15的wear都是1了——下一个分配又从格2开始（因为所有人的wear相等时，第一个被扫描到的格子优先）。

最终效果：所有14个数据格的清空次数偏差不超过1。

free_map：一张16位的目录速查表

free_map是一个uint32_t，但KnotFS只用到了它的低16位——每个bit对应一个块：

free_map 位图对照表
====================

bit  15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
块号 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0

bit=1 → 块已被占用
bit=0 → 块空闲可用

三个操作函数：

// knotfs.c
static void mark_free(uint32_t b) { sb.free_map &= ~(1U << b); }
static void mark_used(uint32_t b) { sb.free_map |= (1U << b); }
static bool is_free(uint32_t b) { return !(sb.free_map & (1U << b)); }

mark_free用位清除操作：&= ~(1U << b)。例如释放块5：free_map &= ~(1U << 5) = free_map &= ~0x20 → bit 5清零。

mark_used用位设置操作：|= (1U << b)。例如占用块5：free_map |= 0x20 → bit 5置1。

is_free用位测试操作：如果free_map & (1U << b)为0则空闲。

这些操作在分配块时被调用：

// knotfs.c — write操作分配块后标记为已用
uint32_t blk = pick_lowest_wear();
if (blk >= KNOTFS_BLOCK_COUNT) {
  cur.result = ERR_NO_BLK;
  cur.st = ST_ERR;
  return;
}
mark_used(blk);
sb.wear[blk]++;
nd->blocks[subst] = blk;

注意这三步的顺序：先选块（pick_lowest_wear）、再标记已用（mark_used）、再增加磨损（wear[blk]++）、最后记录到文件条目。这个顺序不是随意的——如果先记录到文件条目再标记已用，那么在掉电后replay Log时，可能会因为Log中只记录了标记而已用但没有记录块号，造成块号丢失。先标记后记录文件条目，确保了两个操作在Log中的记录是原子可见的。

在释放旧块时（文件覆盖或删除）调用mark_free，同时记录一条LT_BITMAP Log：

// knotfs.c — write操作中释放旧块
for (i = 0; i < oldcnt && i < KNOTFS_DIRECT_BLKS; i++) {
  uint32_t blk = scratch[SCR_OLD_BLK(i)];
  if (blk < KNOTFS_BLOCK_COUNT) {
    log_push(LT_BITMAP, (uint8_t)blk, 0);
    mark_free(blk);
  }
}

这里blk < KNOTFS_BLOCK_COUNT的检查看起来多余——块号怎么可能超出范围？这是一个防御性编程。如果SB被损坏、文件条目中的块号字段出现了一个非法值（例如0xFFFFFFFF），不加检查地mark_free会导致free_map被破坏。

wear[]：每个书架格子的体检报告

wear数组有16个元素，每个是一个uint32_t，记录对应块的累计清空次数：

uint32_t wear[KNOTFS_BLOCK_COUNT];  // 16 × 4字节 = 64字节

每次分配一个块时，wear+1。在pick_lowest_wear返回后立即执行：

sb.wear[blk]++;

关键问题：wear计数何时持久化到Flash？

KnotFS的答案是：只在compact时。 wear数组是knot_sb_t的一部分（第7个字段），在compact时随整个超级块一起写入Flash：

// knotfs.c — compact_write中复制当前SB（包含wear）
static void compact_write(void) {
  memcpy(&compact_buf, &sb, sizeof(knot_sb_t));
  compact_buf.sequence = sb.sequence + 1;
  compact_buf.log_offset = SB_HEADER_SZ;
  compact_buf.log_count = 0;
  compact_buf.crc32 = sb_checksum(&compact_buf);

  uint32_t tgt = inactive_sb_slot();
  fdev_write(tgt, &compact_buf, 0, sizeof(knot_sb_t));
}

mount时，wear计数随SB一起被读回。replay_log中的Log回放会重新执行块分配（mark_used），但不会恢复wear计数——因为LT_BITMAP Log中没有wear增量信息。这意味着如果在compact后掉了电，那些在掉电前被分配但未被compact持久化的块的wear增量会丢失。

对于教学场景（总共几十次操作），这不是问题。KnotFS的12个测试用例总共产生不到50次分配，即使全部wear增量丢失，对磨损均衡的影响微乎其微。

⚠️ 教学简化提示：KnotFS的wear计数只在compact时持久化到Flash。这意味着如果在两次compact之间掉电，最近几次分配操作对应的wear增量会丢失。对于教学场景（总共几十次操作），这不是问题。但在更健壮的设计中，可以考虑Wear Log机制——每次擦除一个块时，在SB Log中追加一条LT_WEAR记录，持久化该块的磨损增量。这避免了短运行场景下的磨损数据丢失。

磨损均衡的边界情况：冷数据的盲区

上一节的悬念问到了关键：pick_lowest_wear 能解决冷数据占坑的问题吗？

不能。

pick_lowest_wear 只在分配新块时做决策——它从 free_map 中标记为“空闲“的块里选 wear 最小的。但如果有一个块从写入后文件就再也没被修改过，它在 free_map 中永远是“已占用“状态，pick_lowest_wear 永远不会考虑它。

比如：你有一个配置文件 “factory_calib.bin”，出厂时写进去之后永远不动。它占了块 2，wear 停在 3。同时，日志文件 “run.log” 每 5 秒 append 一次，每次 append 触发 CoW 分配新块、释放旧块。块 3、4、5……反复分配→擦除→分配→擦除。最终，日志涉及的块擦到了 8 万次，而块 2 还是 3 次。

动态磨损均衡的盲区
=======================

块2 (冷数据):  █  wear=3    ← "永远年轻"，但被占用，无法参与均衡
块3 (热数据):  ████████████████████  wear=80000
块4 (热数据):  ███████████████████   wear=75000
块5 (热数据):  ████████████████████  wear=82000
...

这不是 pick_lowest_wear 的 bug——这是动态磨损均衡的天花板。它只能保证“每次分配新块时选最公平的那一个“，但无法把冷数据从低磨损块上搬走，释放它让它参与轮换。

要解决这个问题，需要静态磨损均衡：主动检测 wear 差异，把冷数据强制迁移到高磨损块，把低磨损块释放给热数据。这需要 GC（垃圾回收）模块——而 KnotFS 没有 GC。

对于 16 块、100K 擦写寿命的教学场景，冷数据问题不构成实际威胁——整个系统的写入总量远达不到寿命上限。但当你把系统扩展到真实车载 ECU 时（15 年寿命、数百万次日志写入），这就是绕不开的问题。3.7 节已经讨论了静态磨损均衡的理论基础——主动检测 wear 差异、搬迁冷数据、释放低磨损块。至于如何在生产级版本中落地，那是留给读者（和未来的你）的思考题。

图书馆隐喻：选最年轻的书架格子

罗马的图书馆管理员在编目古希腊的卷轴时，面临一个问题：书架格子都是天然的，有的来自新砍的橡木，有的来自已经用了百年的老木头。哪种更耐用？

答案是：新木头。它们的结构还没有被温度和湿气侵蚀。用了百年的老木头虽然表面光滑好看，内部可能已经干裂了。

Flash的磨损就像木头老化。被清空过很多次的格子，其浮栅晶体管保持电荷的能力会下降——数据保存时间变短，出错概率上升。

pick_lowest_wear做的是同一件事：挑被“使用磨耗“最少的格子来存放新书。你把它用了一次之后，它的“年龄“增加1（wear++），下次就会优先选它的邻居——直到所有邻居都和它一样“老“。

这排书架（14个数据格），一起慢慢变老。

下集预告

你写了文件、分配了块、标记了状态。但这一切只是在你内存中的sb结构体里发生了。直到compact——重写整个超级块到Flash——你做的所有修改才真正“落盘“。

compact是什么？它像图书管理员的一个工作日：把过去几周所有的借阅登记变更整理成一份新的馆藏总目录，然后注销旧总目录。

下一节，我们走进compact的缓慢而庄严的仪式——从擦除目标块，到写出新SB，再到最后的“剪彩“。

悬念留给：compact不是免费的。每次compact烧掉一条Flash块的一次擦写寿命。KnotFS的compact触发得太频繁——这是教学级的缺陷，还是有意为之的“代价展示“？

Keyboard shortcuts

汽车电子七部曲