Block-Cache

修完 static 缓冲区的 bug 之后，发现加载 busybox 明显变慢了——因为 kmalloc/kfree 在每次 ext2 读取时都要分配释放缓冲区，调用次数多了开销就出来了。 更根本的问题是块缓存（bcache）效率太低：64 个槽位，每次查找都要线性扫描。 这章做两个性能优化。 bcache：哈希表替代线性扫描 原来的实现 uint8_t *bcache_get(uint32_t lba) { for (int i = 0; i < BCACHE_SLOTS; i++) { // O(n) 扫描 if (slots[i].valid && slots[i].lba == lba) { slots[i].lru_time = clock; return slots[i].data; } } // cache miss... } 64 个槽位，命中率低，每次 miss 还要再扫一遍找 LRU victim，加载 busybox 要读几百个 sector，扫描次数非常多。 改造：256 桶哈希表 #define BCACHE_SLOTS 512 // 槽位 64 → 512 #define BCACHE_HASH_SIZE 256 #define BCACHE_HASH(lba) ((lba) & (BCACHE_HASH_SIZE - 1)) typedef struct bcache_slot { uint32_t lba; uint8_t *data; // 改为指针，pmm_alloc 独立分配 int valid, dirty; uint64_t lru_time; struct bcache_slot *hash_next; // 哈希链表 } bcache_slot_t; static bcache_slot_t *hash_table[BCACHE_HASH_SIZE]; 查找变成 O(1) 均摊： ...

Linux 内核里有个叫 page cache（以前叫 buffer cache）的东西，所有磁盘 IO 都要经过它。为什么？因为磁盘太慢了——ATA PIO 读一个扇区要等几毫秒，而内存访问只要几纳秒。把最近访问过的扇区留在内存里，下次再访问直接从内存读，速度提升几千倍。 这一章给我们的 ext2 文件系统加上这层缓存，同时顺手修了一个隐藏很深的调度器 bug。 设计：LRU write-back 缓存 最简单够用的设计：固定 64 个 slot，每个 slot 缓存一个 512 字节扇区，LRU 淘汰，write-back 写回。 typedef struct { uint32_t lba; uint8_t data[512]; uint8_t valid; uint8_t dirty; uint32_t lru_time; } bcache_slot_t; static bcache_slot_t slots[64]; static uint32_t clock = 0; lru_time 用一个全局 clock 计数器实现——每次访问 clock++，命中的 slot 拿到最新值，淘汰时找 lru_time 最小的那个。 bcache_get(lba) uint8_t *bcache_get(uint32_t lba) { clock++; // 命中？ for (int i = 0; i < 64; i++) { if (slots[i].valid && slots[i].lba == lba) { slots[i].lru_time = clock; return slots[i].data; } } // 找 LRU victim int victim = 0; for (int i = 1; i < 64; i++) { if (!slots[i].valid) { victim = i; break; } if (slots[i].lru_time < slots[victim].lru_time) victim = i; } // victim 是 dirty 的？先写回磁盘 if (slots[victim].valid && slots[victim].dirty) ata_write_sector(slots[victim].lba, slots[victim].data); // 读新扇区 ata_read_sector(lba, slots[victim].data); slots[victim] = (bcache_slot_t){ lba, ..., valid=1, dirty=0, lru_time=clock }; return slots[victim].data; } 返回的是指向缓存数据的指针，调用方可以直接读写这块内存。写完后调 bcache_dirty(lba) 标记为脏。 ...