哈希表

修完 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) 均摊： ...