第五章 从零实现一个文件系统——KnotFS

5.1 KnotFS项目概述——教学级异步日志结构化文件系统

你手里有一块64KB的虚拟Flash，没有操作系统

假设你是一名嵌入式工程师新人，被分配了一个任务：在一个只有64KB NOR Flash的单片机上，实现一个能安全读写的文件系统。

没有FreeRTOS。没有DMA。没有中断。没有硬件。

你的工位上只有一台笔记本电脑，上面装着GCC，还有一本铺满咖啡渍的C语言编程指南。

你开始想：文件系统得有什么？超级块、inode、目录、读写接口、原子写入、掉电保护、磨损均衡……每一个词背后都藏着几千行C代码和几十年工程实践积累的坑。

你现在是什么感觉？困惑？不知所措？还是兴奋？

别担心。这就是KnotFS存在的意义。

KnotFS是一个教学级文件系统。它的目标不是跑在真实的Cortex-R5上，而是跑在你的大脑里。它用约1760行纯C代码（核心约1150行），不依赖任何外部库（除了libc），在一块用RAM数组模拟的64KB NOR Flash上，完整地实现了一个异步、日志结构化、掉电安全的文件系统。

你可以在一分钟内编译它，在十秒内跑完它的12个自测用例，然后——慢慢读它的源码。每一行，都值得你停下来想一想。

KnotFS是什么

KnotFS的全称是“Knot Filesystem“——“绳结“文件系统。这个名字不是随便起的。

还记得我们第一章讲过的结绳记事吗？绳结是最原始的信息编码系统。KnotFS是这个编码系统在现代C语言中的化身：它把信息（你的文件）用数据块（绳结）编入一个线性地址空间（绳子），用元数据（绳结的位置和大小规则）组织检索，用校验和（印加人的校验绳结）保护完整性。

KnotFS是本书的“教学伴侣“。 你读到的每一个概念——超级块双副本、Log追加、Copy-on-Write、磨损均衡——在KnotFS里都有直截了当的实现。你不需要交叉编译工具链，不需要JTAG调试器，甚至不需要Linux内核源码。

你需要的东西只有三样：

KnotFS源码结构
==================

knotfs.h          (132行)  —— 公共接口、常量定义、类型声明
knotfs.c          (1150行) —— 核心实现：状态机×8、Flash模拟器、CRC32
knotfs_test.c     (474行)  —— 12个自测用例，包括掉电恢复
Makefile          (71行)   —— 单文件编译，支持x86/ARM64/ARM32三架构

总共约1670行代码。如果你有C语言基础，一个下午就能通读一遍。但理解它为什么这样写——为什么状态机要这么设计，为什么超级块要存两份，为什么compact要在50%满时触发——这需要你读完本章剩下的几节。

构建和运行：一分钟上手

在终端里敲三行命令：

$ cd knotfs
$ make
$ make test

你会看到这样的输出：

  _  __            _   _____ ____
 | |/ /_ __   ___ | |_|  ___/ ___|
 | ' /| '_ \ / _ \| __| |_  \___ \
 | . \| | | | (_) | |_|  _|  ___) |
 |_|\_\_| |_|\___/ \__|_|   |____/

  Teaching File System — Async + Log-Structured + Power-Loss Safe
  Simulated NOR Flash: 64 KB

============================================================
  Test 1: Format & Mount  (64 KB NOR Flash)
============================================================
  Flash layout: 16 blocks x 4096 B = 65536 bytes
  Data region: blocks 2–15  (56 KB)
  [format]     tick 15...    tick 30...    tick 45...
    tick 48... done
  [mount] OK
  [stats] OK

注意那个tick 15... tick 30...。这就是异步文件系统的“心跳“——每15个tick打印一次进度，让你“看到“Flash操作在慢慢推进。如果没有这个tick模拟，现代CPU会在0.1毫秒内跑完全部操作，你什么也看不到。

KnotFS故意的“慢“，是为了让你看清异步的本质。

Makefile是怎么做到零依赖的？看这几行：

// knotfs.h — 唯一的系统头文件
#include <stdint.h>
#include <stdbool.h>

就这两个。<string.h>在knotfs.c中用于memcpy和memset。没有<stdio.h>，没有<stdlib.h>，没有<pthread.h>。KnotFS是一个纯计算单元——它只管理数据和元数据，把所有I/O都抽象成对flash[]数组的读写。

Makefile支持三种架构：

# Makefile:14-25 — 多架构支持
ARCH    ?= native

ifeq ($(ARCH),arm64)
    CC    = aarch64-linux-gnu-gcc
    CFLAGS += -static
else ifeq ($(ARCH),arm32)
    CC    = arm-linux-gnueabihf-gcc
    CFLAGS += -static
else ifeq ($(ARCH),arm32-lite)
    CC    = arm-linux-gnueabi-gcc
    CFLAGS += -static
endif

这意味着同一个源码，可以在你的x86笔记本上跑、在树莓派上跑、在ARM Cortex-A上跑。如果安装了交叉编译器，甚至可以在一个Makefile里编译出三个平台的二进制（make all-arch）。

KnotFS的“可移植性“不是“我们适配了多个平台“，而是“我们根本没有依赖任何平台“。

异步架构：事件循环 + 状态机

KnotFS的核心架构只有两个概念：事件循环和状态机。

事件循环是knotfs_run()：

// knotfs.c — 事件循环的核心
bool knotfs_run(void) {
  fdev_tick();

  /* handle compact completion */
  if (comp_wait && fdev_idle()) {
    comp_wait = false;
  }

  if (!fdev_idle())
    return true;

  /* if current request done, dequeue next */
  if (cur.op != OP_NONE && (cur.st == ST_OK || cur.st == ST_ERR)) {
    if (!q_empty())
      q_pop(&cur);
    else
      cur.op = OP_NONE;
  }

  /* dequeue if idle */
  if (cur.op == OP_NONE && !q_empty()) {
    q_pop(&cur);
    prog = 0;
    subst = 0;
    memset(scratch, 0, sizeof(scratch));
  }

  /* advance state machine */
  if (cur.op != OP_NONE && cur.st != ST_OK && cur.st != ST_ERR) {
    switch (cur.op) {
    case OP_FMT: do_format(); break;
    case OP_MNT: do_mount();  break;
    case OP_WRT: do_write();  break;
    case OP_RD:  do_read();   break;
    case OP_APP: do_append(); break;
    case OP_DEL: do_delete(); break;
    case OP_LS:  do_list();   break;
    case OP_ST:  do_stats();  break;
    default:     break;
    }
  }

  return !knotfs_is_idle();
}

这个函数就像老式游戏机的主循环——每一“帧“（tick），检查输入、更新状态、渲染输出。区别是游戏机渲染的是像素，KnotFS渲染的是文件系统操作。

状态机呢？每个文件系统操作（format、mount、write、read、append、delete、list、stats）都是一个switch(cur.st)的巨型分支：

// knotfs.c — 操作类型和状态常量
typedef enum {
  OP_NONE = 0,
  OP_FMT,
  OP_MNT,
  OP_WRT,
  OP_RD,
  OP_APP,
  OP_DEL,
  OP_LS,
  OP_ST,
} knot_op_t;

typedef enum {
  /* format */
  ST_FMT_ERASE = 10,
  ST_FMT_ERASE_WAIT = 11,
  ST_FMT_WR_SB1 = 12,
  ST_FMT_DONE = 13,
  /* mount */
  ST_MNT_RD_SB0 = 20,
  ST_MNT_RD_SB1 = 21,
  ST_MNT_SEL = 22,
  ST_MNT_REPLAY = 23,
  /* write */
  ST_WRT_INIT = 30,
  ST_WRT_ALLOC = 31,
  ST_WRT_DATA = 32,
  ST_WRT_META = 33,
  ST_WRT_META_FLUSH = 34,
  ST_WRT_COMPACT = 35,
  /* ... */
  ST_OK = 90,
  ST_ERR = 91,
} knot_st_t;

每一个状态只做一件事，然后返回事件循环，等待下一次被调用。这看起来“慢“，但这是嵌入式系统中唯一可行的方式——你不能在Flash擦除的100毫秒里阻塞CPU，因为你还有一个CAN总线要响应、一个电机要控制、一个串口要收发。

KnotFS让你在笔记本电脑上用while(knotfs_run())模拟这个场景。每一次函数返回，就相当于一次任务切换。你看着tick数字增长，渐渐理解：哦，原来异步不是多线程，是把一个长操作切成了很多个小步骤。

保留了哪些生产级特性？

KnotFS虽然简单，但它从生产级方案中保留了五个核心设计：

1. 双超级块 + 日志结构化元数据

超级块（Superblock）是文件系统的“馆藏总目录“，记录了Flash上所有块的分配情况、文件目录、磨损计数。KnotFS存了两份：SB0在块0，SB1在块1。元数据的变更不是原地更新，而是以8字节的Log记录追加到超级块的末尾。这保证了“在最坏的情况下——写入过程中断电——你总能找到一份完好的超级块“。

2. Copy-on-Write原子写入

当你覆盖一个文件时，KnotFS不会直接修改原数据块。它分配新的块、写入新数据、然后才更新元数据指向新块。原子性由此实现：要么新数据写入元数据更新（成功），要么旧数据没被动过（失败），永远不会出现“一半新一半旧“的中间态。

3. 磨损均衡（Wear Leveling）

NOR Flash的每个块有擦写寿命（典型值约10万次）。如果反复在同一个块上写文件，那块会提前报废。KnotFS的find_free_block（在KnotFS中叫pick_lowest_wear）总是选择磨损次数最少的空闲块，让写操作均匀分布。

4. CRC32元数据校验

Flash上的数据可能因为掉电、老化、辐射而发生比特翻转。KnotFS用CRC32保护每一个超级块和每一条Log记录。挂载时，CRC校验不通过的超级块会被丢弃——就像奇普鉴定员跳过磨损的绳结。

5. 请求队列 + 异步完成

上层应用程序可以连续提交格式、写、读、删除等操作，而不用等待前一个完成。KnotFS内部维护一个容量为4的请求队列，由事件循环逐个消费。

相比生产级方案，KnotFS 简化了什么？

生产级方案预估在数千到一万行，跑在真正的 Cortex-R5 上。KnotFS 简化了以下五个方面：

以下是每个简化点的详细解释。

1. 无FreeRTOS → 事件循环

生产级方案运行在FreeRTOS上，disk操作由独立的DiskAsync任务执行，文件系统操作由主任务执行，两者通过队列通信，优先级不同（DiskAsync优先级3，主任务优先级1）。KnotFS将所有操作序列化在一个事件循环中，knotfs_run()一次只能做一件事。

2. 无真实Flash → RAM数组 + tick延迟

生产级方案会调用AUTOSAR FLS驱动去擦写真实的NOR Flash——擦除需要约100ms，写入需要约1ms，读取需要约1μs。KnotFS用一个static uint8_t flash[16 * 4096]数组替代Flash，用计数器模拟延迟（读1 tick、写2 tick、擦3 tick）。第5.3节会详细展开。

3. 无间接块 → 32KB文件上限

生产级方案会支持间接块（indirect block），每个文件可以有远超8个数据块。KnotFS去掉了间接块机制，每个文件最多8个直接块（KNOTFS_DIRECT_BLKS = 8），即32KB（8 × 4096）。这个限制对于教学来说足够了——大部分测试文件只有几十到几百字节。

4. 无独立文件表 → FT合并到SB

这是KnotFS最显著的简化。生产级方案会有独立的File Table（FT），存放在固定的块2和块3，每个FT有自己的Log追加日志。文件条目的修改只需在FT Log中追加一条记录，不需要重写整个FT块。

KnotFS把文件条目（nodes[8]）直接放在超级块里。这意味着每次文件创建、删除、大小变更，都必须通过compact重写整个超级块，而不能只追加一条Log。这导致SB槽位的擦写次数比生产级设计高约200倍——我们会在5.7节详细讨论。

5. 无网络终端 → 纯API

生产级方案会通过终端服务提供了TCP终端——端口8004用于交互式命令（mount、read、write、delete、list、stats、format），端口8005用于文件传输。KnotFS只提供C API，通过knotfs_test.c自测程序驱动。

为什么要读KnotFS源码？

因为KnotFS做了一件很罕见的事：它把嵌入式文件系统的核心思想——异步状态机、日志结构化、Copy-on-Write、双副本冗余——从生产级设计理念中提炼出来，压缩到一千多行，同时保留了全部关键设计。

你读的不只是C代码。你读的是一个工程师在说：“你看，文件系统其实没那么神秘。你看这个超级块的结构——它就是一个C结构体。你看这个状态机——它就是一个switch语句。你看这个compact——它就是一次memcpy加一次erase。”

当你理解完这约1670行代码后，再看生产级方案的设计，你会惊讶地发现：它们的内核是一样的。 生产级方案多出来的代码，大部分是集成胶水（FreeRTOS任务管理、AUTOSAR驱动调用、缓存一致性维护），而不是文件系统逻辑本身。

而这，就是KnotFS作为“教学伴侣“的终极价值。

⚠️ 教学简化提示：KnotFS的目标是让读者在没有硬件的情况下理解异步文件系统的设计。它不适合直接用于生产环境。KnotFS缺少以下生产级特性：DMA驱动的Flash I/O中断处理、间接块支持大文件、独立的FT Log减少SB磨损、FreeRTOS任务优先级调度、缓存一致性维护（arch_clean_cache_range/arch_invalidate_cache_range）、以及网络终端服务。

下集预告

你看到了knotfs.h中的常量：KNOTFS_BLOCK_SIZE = 4096、KNOTFS_BLOCK_COUNT = 16、KNOTFS_SB0_BLK = 0……这些数字不是随便选的。它们定义了一个16×4KB的“棋盘“——块0和块1是馆藏总目录，块2到块15是书架。下一节，我们摊开这张棋盘，看看每一格放了什么，以及为什么KnotFS选择把超级块存两份。

悬念留给：16个块中只有14个能被你用。那两个被“偷走“的块，是你的最后一道保险。