5.12 CRC32——信任但要验证
每一比特都是承诺，但有些承诺会过期
你把超级块写进Flash。668字节（sizeof(knot_sb_t)），每一个比特都是你精心计算的结果——magic=0x4B4E4653，sequence号递增，free_bitmap精确标记每一块的状态，8个file entry里是用户花时间写的文件信息。
1毫秒后，比特翻转了。也许是宇宙射线，也许是NOR Flash的read disturb，也许只是运气不好。SB里的某个比特从0变成1。这个变化对于文件系统来说是致命的——它可能导致一个本来被占用的块突然被标记为FREE，下一次pick_lowest_wear选中它，覆盖掉用户的数据。
你需要的不是“相信数据没问题“，而是“验证数据没问题“。
CRC32（Cyclic Redundancy Check，循环冗余校验）是一个轻量级的错误检测码。它不是加密算法（任何人都可以伪造一个CRC），也不是纠错码（它不能修复错误），但它能以极高的概率检测出数据的意外损坏——对于32位CRC，随机损坏不被检测到的概率是 1/2³² ≈ 1/43亿。
多项式0xEDB88320
KnotFS使用的CRC32多项式和Ethernet、gzip、PKZIP、PNG文件格式完全一致：
多项式: 0xEDB88320 (反射形式)
原始多项式: x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹
+ x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1
位宽: 32位
初始化值: 0xFFFFFFFF
最终异或值: 0xFFFFFFFF
反射输入/输出: 是
让我们看KnotFS的实现：
/* knotfs.c: k_crc32 — polynomial 0xEDB88320 */
static uint32_t k_crc32(const void *data, uint32_t len) {
uint32_t c = 0xFFFFFFFFU;
const uint8_t *p = (const uint8_t *)data;
for (uint32_t i = 0; i < len; i++) {
c ^= p[i];
for (int j = 0; j < 8; j++)
c = (c >> 1) ^ ((c & 1U) ? 0xEDB88320U : 0U);
}
return c ^ 0xFFFFFFFFU;
}
这个实现使用的是逐位计算法，O(n×8)复杂度。对于KnotFS来说，校验的数据量小（超级块668字节，每条log记录8字节），逐位计算足够快速。但如果你在生产级部署中对大文件做CRC32校验，应该使用查表法（256个uint32的查找表），把复杂度降到O(n)。
两个校验函数：sb_checksum 和 log_checksum
KnotFS有两种需要校验的数据结构：超级块（knot_sb_t）和Log记录（knot_log_t）。两种校验函数的结构相同——对整个结构体做CRC32，但排除结构体末尾的crc32字段本身：
/* SB校验：CRC32 over 整个SB，排除最后一个字段(crc32) */
static uint32_t sb_checksum(const knot_sb_t *sb) {
return k_crc32(sb, sizeof(knot_sb_t) - sizeof(uint32_t));
}
/* Log记录校验：CRC32 over 整个log_entry，排除最后一个字段(crc32) */
static uint32_t log_checksum(const knot_log_t *e) {
return k_crc32(e, sizeof(knot_log_t) - sizeof(uint32_t));
}
为什么排除crc32字段？因为crc32字段存储的是“其他字段的校验值“。如果你把crc32字段也纳入计算，就陷入了循环依赖——校验值取决于校验值本身，永远无法匹配。这在所有带checksum的数据结构中都是标准做法。
sizeof(knot_sb_t) - sizeof(uint32_t)等于664字节（668 - 4）。sizeof(knot_log_t) - sizeof(uint32_t)等于4字节（8 - 4）——只校验log记录的tag、blk、val三个字段。
校验发生的时机
时机一：mount选择SB时。
/* knotfs.c: ST_MNT_SEL — mount时验证两个SB的CRC */
case ST_MNT_SEL: {
bool ok0 = (sb.magic == KNOTFS_MAGIC && sb.crc32 == sb_checksum(&sb));
bool ok1 =
(sb_alt.magic == KNOTFS_MAGIC && sb_alt.crc32 == sb_checksum(&sb_alt));
if (!ok0 && !ok1) {
cur.result = ERR_MNT_FAIL;
cur.st = ST_ERR;
return;
}
if (!ok0)
memcpy(&sb, &sb_alt, sizeof(sb));
else if (ok1 && sb_alt.sequence > sb.sequence)
memcpy(&sb, &sb_alt, sizeof(sb));
cur.st = ST_MNT_REPLAY;
return;
}
这里同时做了两道检查：magic校验和CRC校验。如果两个SB都通过magic+CRC，则选择sequence号大的那个（更新的副本）。如果只有一个通过，就用通过的那个。如果两个都不通过——mount失败，返回错误码-10。这意味着Flash上的超级块信息已经不可恢复地损坏了。对于KnotFS的教学环境来说，这意味着“格式化从头来过“。对于生产级部署来说，这意味着需要向外界报告不可恢复的介质错误。
时机二：log replay时。
/* knotfs.c: replay_log — 回放Log时逐条校验CRC */
static void replay_log(void) {
knot_log_t e;
for (uint32_t i = 0; i < sb.log_count; i++) {
uint32_t pos = SB_HEADER_SZ + i * LOG_ENTRY_SZ;
memcpy(&e, ((uint8_t *)&sb) + pos, sizeof(e));
if (e.tag == 0xFF)
break;
if (e.crc32 != log_checksum(&e))
break;
if (e.tag == LT_BITMAP) {
if (e.val)
mark_used(e.blk);
else
mark_free(e.blk);
}
}
}
log_replay逐条读取log记录，每条记录都做CRC校验。如果一条记录的CRC不匹配，replay立即停止（break）。这意味着损坏记录之后的所有记录都被丢弃。这是一个保守的策略——宁可丢失一些后续的元数据更新，也不冒险回放一条损坏的记录（它可能会错误地释放或占用块）。
另外注意 if (e.tag == 0xFF) break——这是在处理Flash的特有行为。NOR Flash擦除后是全1（0xFF）。如果一个log_slot是0xFF，说明它从未被写入过——这是Log区域的尾部，应该停止回放。tag == 0xFF的检查和CRC校验的顺序保证了：我们不会尝试对一个全FF的slots做CRC校验（那一定是错的）。
为什么是CRC32而不是更简单的校验
你可能会问：为什么不用一个简单的异或校验和（XOR checksum）？它只占1个字节，计算速度是CRC32的32倍。
答案是：检测能力。
XOR checksum（8位）：
误判概率 = 1/256 ≈ 0.39%
对于10000次操作来说，预期有39次损坏被漏掉
CRC32（32位）：
误判概率 = 1/2³² ≈ 2.33 × 10⁻⁸%
对于10000次操作来说，预期漏检次数≈0
CRC16（16位）：
误判概率 = 1/65536 ≈ 0.0015%
适合512字节以内的短数据包
对于超级块（668字节），32位CRC是标准选择。16位CRC不足以覆盖1000+字节的数据——随着数据变长，碰撞概率不够低。对于8字节的log记录，16位CRC其实就够了，但为了代码统一和实现简单，KnotFS对SB和log都用了32位。
CRC失败时发生了什么
让我们模拟一个具体的场景：
场景1：SB0的CRC失败，SB1正常
→ mount选择SB1，正常启动
→ 用户感觉不到任何问题
场景2：两个SB的CRC都失败
→ mount返回 -10
→ 文件系统不可用
→ 需要 format 从头来过
场景3：Log replay中第7条记录的CRC失败
→ replay在第7条处break
→ 第1~6条的bitmap更新被应用
→ 第7条及之后的更新丢失
→ 文件系统可能处于一致但"缺少最近几次更新"的状态
场景3是最微妙的。它不会导致mount失败，但可能导致部分文件更新丢失。比如用户追加了500字节到文件，对应的log记录是第7条——如果它在写入中途损坏，mount后文件恢复到追加前的大小。用户的数据没丢（旧数据还在），但最近一次操作的结果丢失了。
这种“丢失最近操作但不破坏一致性“的特性，正是log-structured文件系统的设计目标。它本质上是一个“只追加不破坏“的数据结构——最坏情况下只是丢失尾部日志，不会破坏已有的元数据。
CRC的局限性
CRC32检测随机比特翻转的能力很强，但它不能防止所有类型的损坏：
-
系统性损坏：如果Flash控制器本身有问题，它可能把数据的所有比特都翻转。CRC32对这种损坏无能为力——它只能检测“意外“翻转。
-
恶意篡改：CRC32不是密码学哈希。任何人都可以在修改数据后重新计算CRC32，让校验“通过“。如果你的使用场景需要防篡改，应该用SHA-256而不是CRC32。
-
硅寿命末期的大规模位翻转：当NOR Flash接近磨损极限时，单个块的比特翻转率会急剧上升。CRC32的设计假设是“独立随机比特翻转“，而磨损末期的翻转是相关的（集中于某几个位）。
对于KnotFS的教学环境和嵌入式场合来说，CRC32足够了。NOR Flash的MTBF（平均故障间隔）在正常使用下足够长，CRC32可以覆盖绝大多数意外损坏。
⚠️ 教学简化提示：这里KnotFS只用CRC32保护了元数据（SB和Log记录）。生产级方案除了SB CRC还有文件内容CRC32校验——mount时对可校验文件逐块计算CRC32并记录到信任表中。下载时如果文件的块CRC和记录不一致，文件会被标记为
UNTRUSTED，拒绝下载。此外，它的FT（File Table）块也有独立的CRC32校验——因为FT和SB是分离的。KnotFS砍掉了文件内容校验（只保留了元数据CRC），将file entry嵌入SB避开了FT的复杂性。
CRC32的查表优化（课外阅读）
逐位计算的CRC32每次处理1位，共8次内循环。生产级版本中标准做法是用一个256项的查找表，每次处理1字节：
/* CRC32 lookup table (polynomial 0xEDB88320) */
static const uint32_t crc32_table[256] = {
0x00000000U, 0x77073096U, 0xEE0E612CU, 0x990951BAU, /* ... 256 entries ... */
};
static uint32_t crc32_fast(const uint8_t *data, uint32_t len) {
uint32_t c = 0xFFFFFFFFU;
for (uint32_t i = 0; i < len; i++)
c = crc32_table[(c ^ data[i]) & 0xFF] ^ (c >> 8);
return c ^ 0xFFFFFFFFU;
}
查找表占用1KB的ROM空间。对于嵌入式系统来说，1KB的查找表是可接受的代价——它把CRC32的速度提升了约8倍。在Cortex-R5上，DWT（数据观察点）可以在硬件上加速CRC32计算——但那是另一个话题了。
如果你来设计
试着回答：如果一个log记录的CRC校验正确，但它的blk字段意外的指向了一个已经被占用的块（比如Flash上的比特翻转改变了blk的值，但CRC32也同时被“碰巧“匹配了），会发生什么？
答案：这种情况的概率约为2.33×10⁻⁸%，但确实可能在极端情况下发生。如果发生，log_replay会尝试对一个已经被占用的块执行mark_free——这会把一个无辜文件的块释放掉。这会导致“双占用“问题——两个file entry指向同一个块。幸运的是，由于log记录的tag字段也会参与CRC校验，而tag只有两个合法值（LT_BITMAP=0, LT_USED=1），一个被翻转的tag大概率变成非法的tag值（被replay中的if (e.tag == LT_BITMAP)跳过），从而限制了损坏的影响面。
下集预告
CRC32保证了每一次mount时元数据的可验证性。但文件系统的日常运转不只依赖mount——每一次操作（写、追加、删除）都需要排队、调度、按顺序执行。KnotFS没有多线程，没有抢占——它是怎么做到“提交请求立刻返回、不阻塞、过后再轮询结果“的非阻塞风格的？答案在它的心跳里——knotfs_run()，一个每次只推进一步状态机的事件循环，一个只有4个槽位的请求队列，一条永远不会被同时执行的管道。协作式非阻塞调度——事件循环。