Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

5.11 追加与删除——文件的变与灭

追加：在书架上接着放书

你有一排已经放满了一半的书架。现在你想接着放新书。你不能把书架清空重来——成本太高。你只能找到最后一排的最末尾，从那里开始继续放。

这就是文件的追加（append）。它和“写新文件“（write）的区别在于：write是一次性的整体替换（CoW全量覆盖），append是增量修改（在原文件末尾接着写）。 在POSIX语义里，write(oflag=O_TRUNC)替换，write(oflag=O_APPEND)追加。KnotFS把这两种语义分成了两个独立的API：knotfs_write和knotfs_append。

但append有一个write不需要面对的复杂性：Read-Modify-Write（RMW，读-改-写）。

为什么append需要RMW？

文件布局：
  ┌─────────块0────────┐ ┌─────────块1────────┐
  │ 已有数据(4096字节)   │ │ 已有数据(1000字节)   │ │ 空白(3096字节)
  └────────────────────┘ └────────────────────┘

现在追加500字节。新数据要写到哪里？
  → 块1的偏移1000处。

直觉上，直接往偏移1000写500字节就行了。
但 Flash 驱动的编程接口有对齐约束：起始地址和写入长度必须满足硬件要求的边界（比如按编程页对齐、按字对齐）。
当追加的起点不在对齐边界上，或者长度不整——你就不能直接"发一条带偏移的写命令"。

所以必须用 RMW：先把块1全部读到 `tmp`，
在内存里把新500字节拼接到偏移1000处——对齐的问题在 RAM 中解决——再把拼接好的完整内容写回块1。
（实际上真实的flash可能是按字对齐，不一定需要读取整个块1，knotfs中只是为了说明这个概念，仅教学演示。）

这就是RMW模式。它比单纯写操作多了一步：先读。因为追加操作必须保持块中已有的数据不丢失。KnotFS的append状态机有6个状态：

ST_APP_LOOKUP → ST_APP_ALLOC → ST_APP_RD_BLK → ST_APP_DATA → ST_APP_META → ST_APP_COMPACT

第一状态：ST_APP_LOOKUP —— 算好从哪里接着写

case ST_APP_LOOKUP:
    nd = find_node(cur.name);
    if (!nd) {
      nd = alloc_node(cur.name);
      if (!nd) {
        cur.result = ERR_APP_NOFILE;
        cur.st = ST_ERR;
        return;
      }
    }
    last_used = nd->size;
    if (last_used + cur.a_sz > KNOTFS_FILE_LIMIT) {
      cur.result = ERR_APP_OVF;
      cur.st = ST_ERR;
      return;
    }
    nd->size = last_used + cur.a_sz;

    if (nd->block_count == 0) {
      scratch[SCR_APP_LAST_BLK] = 0;
      scratch[SCR_APP_LEFT] = KNOTFS_BLOCK_SIZE;
    } else {
      uint32_t li = nd->block_count - 1;
      last_blk = nd->blocks[li];
      free_in_last = KNOTFS_BLOCK_SIZE - (last_used % KNOTFS_BLOCK_SIZE);
      if (last_used % KNOTFS_BLOCK_SIZE == 0)
        free_in_last = 0;
      scratch[SCR_APP_LAST_BLK] = last_blk;
      scratch[SCR_APP_LEFT] = free_in_last;
    }
    scratch[SCR_APP_OFF] = last_used;
    subst = 0;
    prog = 0;
    cur.st = ST_APP_ALLOC;
    return;

这段代码的密集计算集中在一个地方：最后一个块还剩多少空间？

last_used = nd->size;                              // 文件当前大小，比如5000
last_blk  = nd->blocks[ nd->block_count - 1 ];      // 最后一个块的块号
free_in_last = KNOTFS_BLOCK_SIZE - (last_used % KNOTFS_BLOCK_SIZE);
             = 4096 - (5000 % 4096)
             = 4096 - 904
             = 3192                                // 最后一个块还剩3192字节

if (last_used % KNOTFS_BLOCK_SIZE == 0) free_in_last = 0;
  // 如果文件大小正好是块大小的整数倍，最后一个块已满，需要新块

这个计算决定了append的后续走向：

  • 如果free_in_last > 0：最后一个块有剩余空间，新数据可以直接追到那个块里
  • 如果free_in_last == 0：最后一个块已满，需要分配一个新块

scratch[2] = last_used记录的是追加前的文件大小——它是新数据写入的文件绝对偏移起点。

第二状态：ST_APP_ALLOC —— 需要的话，分一块新书架格子

case ST_APP_ALLOC:
    if (scratch[SCR_APP_LEFT] == 0) {
      nd = find_node(cur.name);
      if (nd->block_count >= KNOTFS_DIRECT_BLKS) {
        cur.result = ERR_APP_MAXBLK;
        cur.st = ST_ERR;
        return;
      }
      new_blk = pick_lowest_wear();
      if (new_blk >= KNOTFS_BLOCK_COUNT) {
        cur.result = ERR_APP_NOBLK;
        cur.st = ST_ERR;
        return;
      }
      mark_used(new_blk);
      sb.wear[new_blk]++;
      nd->blocks[nd->block_count] = new_blk;
      nd->block_count++;
      scratch[SCR_APP_LAST_BLK] = new_blk;
      scratch[SCR_APP_LEFT] = KNOTFS_BLOCK_SIZE;
    }
    /* read existing block first to merge append data */
    fdev_read(scratch[SCR_APP_LAST_BLK], tmp, KNOTFS_BLOCK_SIZE);
    cur.st = ST_APP_RD_BLK;
    return;

如果scratch[1] == 0（最后一个块已满），就分配一个新块。然后把目标块读到tmp——无论是旧块还是新块，RMW的第一步都是读，因为你需要块中已有的数据来和新追加内容拼接。

第三、四状态：ST_APP_RD_BLK + ST_APP_DATA —— 拼接并写回

case ST_APP_RD_BLK: {
    uint32_t blk = scratch[SCR_APP_LAST_BLK];
    write_off = scratch[SCR_APP_OFF] % KNOTFS_BLOCK_SIZE;
    uint32_t space = KNOTFS_BLOCK_SIZE - write_off;
    uint32_t n = (cur.a_sz - prog < space) ? cur.a_sz - prog : space;

    const uint8_t *s = (const uint8_t *)cur.a_buf + prog;
    memcpy(tmp + write_off, s, n);
    fdev_write(blk, tmp, 0, KNOTFS_BLOCK_SIZE);
    prog += n;
    scratch[SCR_APP_OFF] += n;
    cur.st = ST_APP_DATA;
    return;
}

case ST_APP_DATA:
    if (prog >= cur.a_sz) {
      log_reset();
      log_push(LT_BITMAP, (uint8_t)scratch[SCR_APP_LAST_BLK], 1);
      log_flush();
      compact_erase();
      comp_wait = true;
      cur.st = ST_APP_META;
      return;
    }
    scratch[SCR_APP_LEFT] = 0;
    cur.st = ST_APP_ALLOC;
    return;

关键运算：

write_off = scratch[2] % KNOTFS_BLOCK_SIZE
          = last_used % 4096
          = 写入起点在当前块内的偏移

space = KNOTFS_BLOCK_SIZE - write_off
      = 当前块还能装多少字节

n = min(cur.a_sz - prog, space)
  = 本次写入的字节数（可能被块边界截断）

然后memcpy(tmp + write_off, s, n)把新数据拼接到tmp的正确位置。如果用户要追加的数据跨越块边界（比如最后一个块只剩100字节，用户追加了1000字节），那么ST_APP_DATA会检测到prog < cur.a_sz，设置scratch[1] = 0触发分配新块，然后跳回ST_APP_ALLOC进入下一轮循环。

跨越块边界的追加示例：

文件当前5000字节，块0满了(4096)，块1有904字节已用(4096~4999)
追加1500字节：

轮次1（块1，偏移904）：
  write_off = 5000 % 4096 = 904
  space = 4096 - 904 = 3192
  n = min(1500, 3192) = 1500
  memcpy(tmp+904, buf, 1500)  → 全写进块1了，没跨越边界
  prog = 1500 ≥ cur.a_sz → 完成

如果追加4000字节：
轮次1（块1，偏移904）：
  n = min(4000, 3192) = 3192
  memcpy(tmp+904, buf, 3192)  → 块1装满
  prog = 3192 < 4000 → 回到 ST_APP_ALLOC

轮次2（新块2）：
  write_off = (5000+3192) % 4096 = 0
  space = 4096
  n = min(4000-3192, 4096) = 808
  memcpy(tmp, buf+3192, 808)
  prog = 4000 ≥ cur.a_sz → 完成

第五、六状态：ST_APP_META + ST_APP_COMPACT —— 元数据落地

case ST_APP_META:
    compact_write();
    cur.st = ST_APP_COMPACT;
    return;

case ST_APP_COMPACT:
    compact_finish();
    log_commit();
    cur.st = ST_OK;
    return;

append的meta阶段比write简单——不需要释放旧块（因为没有CoW替换，只是增量），只需要把新的file entry（更新后的nd->size和可能新增的nd->blocks[]）通过compact持久化到Flash。

删除：抹去一个文件的所有痕迹

删除是文件系统中最朴素的操作。它不需要读写任何数据块——只需要做两件事：

  1. 释放文件所有块（归还free_bitmap）
  2. 清除file entry（让slot可以被新文件复用）

KnotFS的delete用三个状态完成：

case ST_DEL_LOOKUP:
    nd = find_node(cur.name);
    if (!nd) {
      cur.result = ERR_DEL_NOFILE;
      cur.st = ST_ERR;
      return;
    }
    log_reset();
    for (i = 0; i < nd->block_count && i < KNOTFS_DIRECT_BLKS; i++) {
      if (nd->blocks[i] < KNOTFS_BLOCK_COUNT) {
        log_push(LT_BITMAP, (uint8_t)nd->blocks[i], 0);
        log_push(LT_USED, (uint8_t)nd->blocks[i], 0);
        mark_free(nd->blocks[i]);
      }
    }
    memset(nd, 0, sizeof(knode_t));
    log_flush();
    compact_erase();
    comp_wait = true;
    cur.st = ST_DEL_META;
    return;

注意这里每条块做了两次log_push：一次LT_BITMAP标记free，一次LT_USED清零used_bytes。为什么需要两次？

LT_BITMAP负责free_map——标记块是否被占用。LT_USED负责block_used_bytes——记录块中的有效数据字节数。在KnotFS的简化设计中，LT_USED对删除的意义不太大（因为块被free后used_bytes不再被关注），但它是log结构的完整性要求——每一次free_bitmap的变更都应该伴随used_bytes的变更，以便log_replay能完整恢复状态。

然后memset(nd, 0, sizeof(knode_t))直接把file entry清零。nd->size = 0后，这个slot在alloc_node看来就是可复用的。

删除操作的精简流程：

ST_DEL_LOOKUP:
  ① 找文件 → ② log_reset
  ③ 遍历所有块: log_push(BITMAP, blk, 0) + log_push(USED, blk, 0) + mark_free
  ④ memset(nd, 0, sizeof(knode_t))   ← file entry 清零
  ⑤ log_flush + compact_erase → 跳转

ST_DEL_META:
  compact_write → 跳转

ST_DEL_COMPACT:
  compact_finish + log_commit → ST_OK

⚠️ 教学简化提示：这里KnotFS的delete通过memset(nd, 0, sizeof(knode_t))直接清零entry。生产级方案的delete涉及间接块的复杂处理——需要判断间接块（indirect block）是否被释放、是否被其他文件引用。此外，它不会直接清零file entry，而是通过FT Log（文件表日志）标记entry为DELETED，在compact时才回收。而且它的process_delete_file在释放块时还需调用is_old_block()检查块是否在压缩过程中被标记为待释放，防止释放一个正在被SB compact引用的块。

append与write的语义分界线

你可能问：为什么要分两个API？把append设计成write的变体不行吗？

在KnotFS里，knotfs_write是全量替换——它不管文件之前存不存在，CoW一份全新的。knotfs_append是增量修改——保持已有数据不变，在末尾追加。

这两种语义在POSIX系统调用里是通过open的flag控制的：

open("file", O_WRONLY | O_TRUNC);  // 截断写 → 对应 knotfs_write
open("file", O_WRONLY | O_APPEND); // 追加写 → 对应 knotfs_append

在嵌入式文件系统里，把两种语义分开有两个好处：

  1. 性能差异：append只需要RMW最后一个块，write需要全部重新分配。分开可以避免在write里做不必要的读操作。
  2. 元数据更新量：append只更新file entry的size和可能新增的一个blocks[]；write需要更新所有blocks[]。compact的工作量不同。

如果你来设计

试着回答：如果用户在append过程中断电（比如追加了500字节，已经写了200字节到Flash），下次mount会看到什么？

答案：有两种可能。①如果compact还没做——旧SB仍然指向追加前的文件状态（size=旧值），追加的新数据虽然在Flash上，但不在任何file entry的范围内。mount后文件恢复到追加前的大小，追加的200字节丢失。②如果compact已经写入新SB但compact_finish还没执行——mount会选择sequence大的那个SB，如果是新SB，文件size=旧值+500。但Flash上只有200字节是有效追加数据，剩余的300字节是不可预测的（0xFF或残留数据）。所以，append的原子性弱于write——write是CoW全量替换，要么看到完整的旧版本，要么看到完整的新版本。append的中间状态是“文件变大了但数据不完整“。这是log-structured文件系统需要额外处理的问题，在生产级方案中通过FT Log的原子commit来保证。

下集预告

append的RMW、write的CoW、read的偏移裁剪、delete的log_push……每一个状态机都在和Flash的数据打交道。但数据可能损坏——NOR Flash上的比特可能翻转，超级块的write可能中途断电导致校验和不匹配。下一节，我们讨论KnotFS如何用32位CRC保护每一条元数据——多项式0xEDB88320，一个来自以太网时代的校验码，如何成为嵌入式文件系统的最后防线。