相关数据结构如下：
此数据结构在/src/fs/buf.h中
struct buf {
/* Data portion of the buffer. */
union {/*公用体，可用来普通存储数据，目录，i节点，位图*/
char b__data[BLOCK_SIZE]; /* ordinary user data */
struct direct b__dir[NR_DIR_ENTRIES]; /* directory block */
zone1_t b__v1_ind[V1_INDIRECTS]; /* V1 indirect block */
zone_t b__v2_ind[V2_INDIRECTS]; /* V2 indirect block */
d1_inode b__v1_ino[V1_INODES_PER_BLOCK]; /* V1 inode block */
d2_inode b__v2_ino[V2_INODES_PER_BLOCK]; /* V2 inode block */
bitchunk_t b__bitmap[BITMAP_CHUNKS]; /* bit map block */
} b;
/* Header portion of the buffer. */
struct buf *b_next; /* used to link all free bufs in a chain */
struct buf *b_prev; /* used to link all free bufs the other way */
struct buf *b_hash; /* used to link bufs on hash chains ，用于连接属于同一hash的链
*/
block_t b_blocknr; /* block number of its (minor) device */
dev_t b_dev; /* major | minor device where block resides */
char b_dirt; /* CLEAN or DIRTY */
char b_count; /* number of users of this buffer */
} buf[NR_BUFS]；/*目前此数目为80*/
struct buf *buf_hash[NR_BUF_HASH]; /* the buffer hash table 哈希表，大小为128个*/
struct buf *front; /* points to least recently used free block 指向最近不久不会使用的
块*/
struct buf *rear; /* points to most recently used free block 指向最近不久会使用的块*/
当文件系统需要新的块时，先去上述缓存区中查找，如果找到则将块的指针返回，如果未找到，则从front中替换出一个块出去，从磁盘上加载一个块，放入此缓冲区中。当文件系统用完该块，系统先将该块挂入front和rear指针指向的空闲缓冲区中。目前普通数据块的大小为1024字节。
文件系统需要一块时会调用get_block(),文件系统不需要该块时调用put_block()将块放入空闲缓冲区,调用rm_lru()函数将块从空闲缓冲区中删除。
具体代码如下： 代码位于/src/fs/cache.c
PUBLIC struct buf *get_block(dev, block, only_search)
register dev_t dev; /* on which device is the block? */
register block_t block; /* which block is wanted? */
int only_search; /* if NO_READ, don't read, else act normal */
{
/* Check to see if the requested block is in the block cache. If so, return
* a pointer to it. If not, evict some other block and fetch it (unless
* 'only_search' is 1). All the blocks in the cache that are not in use
* are linked together in a chain, with 'front' pointing to the least recently
* used block and 'rear' to the most recently used block. If 'only_search' is
* 1, the block being requested will be overwritten in its entirety, so it is
* only necessary to see if it is in the cache; if it is not, any free buffer
* will do. It is not necessary to actually read the block in from disk.
* If 'only_search' is PREFETCH, the block need not be read from the disk,
* and the device is not to be marked on the block, so callers can tell if
* the block returned is valid.
* In addition to the LRU chain, there is also a hash chain to link together
* blocks whose block numbers end with the same bit strings, for fast lookup.
*/
int b;
register struct buf *bp, *prev_ptr;
/* Search the hash chain for (dev, block). Do_read() can use
* get_block(NO_DEV ...) to get an unnamed block to fill with zeros when
* someone wants to read from a hole in a file, in which case this search
* is skipped
*/
if (dev != NO_DEV) {
b = (int) block & HASH_MASK; /*此处HASH_MASK的值为127，即1111111*/
bp = buf_hash[b]; /*取到其hash表中的表项入口*/
while (bp != NIL_BUF) {
if (bp->b_blocknr == block && bp->b_dev == dev) {
/* Block needed has been found. */
if (bp->b_count == 0) rm_lru(bp); /*如果此表项在空闲缓冲链表中，则将其从其中删除*/
bp->b_count++; /* record that block is in use 使用计数器加1*/
return(bp);
} else {
/* This block is not the one sought. ，遍历同属一hash值的链表，查找需要的块*/
bp = bp->b_hash; /* move to next block on hash chain */
}
}
}
/* Desired block is not on available chain. Take oldest block ('front'). */
if ((bp = front) == NIL_BUF) panic("all buffers in use", NR_BUFS);
rm_lru(bp); /*未找到需要的块，如果空闲链表不为空，则从其中摘除一项，用于接下来加载新的块*/
/* Remove the block that was just taken from its hash chain. */
b = (int) bp->b_blocknr & HASH_MASK;
prev_ptr = buf_hash[b];
if (prev_ptr == bp) {/*将摘除的空闲块从其目前所属的hash表中摘除*/
buf_hash[b] = bp->b_hash;
} else {
/* The block just taken is not on the front of its hash chain. */
while (prev_ptr->b_hash != NIL_BUF)
if (prev_ptr->b_hash == bp) {
prev_ptr->b_hash = bp->b_hash; /* found it，查找摘除的空闲块的具体位置 */
break;
} else {
prev_ptr = prev_ptr->b_hash; /* keep looking */
}
}
/* If the block taken is dirty, make it clean by writing it to the disk.
* Avoid hysteresis by flushing all other dirty blocks for the same device.
*/
if (bp->b_dev != NO_DEV) {
if (bp->b_dirt == DIRTY) flushall(bp->b_dev);/*如果空闲块为脏，则回写到磁盘*/
#if ENABLE_CACHE2
put_block2(bp);
#endif
}
/* Fill in block's parameters and add it to the hash chain where it goes. */
bp->b_dev = dev; /* fill in device number */
bp->b_blocknr = block; /* fill in block number */
bp->b_count++; /* record that block is being used */
b = (int) bp->b_blocknr & HASH_MASK;
bp->b_hash = buf_hash[b];/*将原hash链中的第一块链接到当前块后面*/
buf_hash[b] = bp; /* add to hash list 加入到hash表中*/
/* Go get the requested block unless searching or prefetching. */
if (dev != NO_DEV) {
#if ENABLE_CACHE2
if (get_block2(bp, only_search)) /* in 2nd level cache */;
else
#endif
if (only_search == PREFETCH) bp->b_dev = NO_DEV;
else
if (only_search == NORMAL) rw_block(bp, READING);
}
return(bp); /* return the newly acquired block */
}
/*===========================================================================*
* put_block *
*===========================================================================*/
PUBLIC void put_block(bp, block_type)/*将块加入到LRU链中*/
register struct buf *bp; /* pointer to the buffer to be released */
int block_type; /* INODE_BLOCK, DIRECTORY_BLOCK, or whatever */
{
/* Return a block to the list of available blocks. Depending on 'block_type'
* it may be put on the front or rear of the LRU chain. Blocks that are
* expected to be needed again shortly (e.g., partially full data blocks)
* go on the rear; blocks that are unlikely to be needed again shortly
* (e.g., full data blocks) go on the front. Blocks whose loss can hurt
* the integrity of the file system (e.g., inode blocks) are written to
* disk immediately if they are dirty.
*/
if (bp == NIL_BUF) return; /* it is easier to check here than in caller */
bp->b_count--; /* there is one use fewer now */
if (bp->b_count != 0) return; /* block is still in use */
bufs_in_use--; /* one fewer block buffers in use */
/* Put this block back on the LRU chain. If the ONE_SHOT bit is set in
* 'block_type', the block is not likely to be needed again shortly, so put
* it on the front of the LRU chain where it will be the first one to be
* taken when a free buffer is needed later.
*/
if (block_type & ONE_SHOT) {
/* Block probably won't be needed quickly. Put it on front of chain.
* It will be the next block to be evicted from the cache.
*/
bp->b_prev = NIL_BUF;
bp->b_next = front;
if (front == NIL_BUF)
rear = bp; /* LRU chain was empty */
else
front->b_prev = bp;
front = bp;
} else {
/* Block probably will be needed quickly. Put it on rear of chain.
* It will not be evicted from the cache for a long time.
*/
bp->b_prev = rear;
bp->b_next = NIL_BUF;
if (rear == NIL_BUF)
front = bp;
else
rear->b_next = bp;
rear = bp;
}
/* Some blocks are so important (e.g., inodes, indirect blocks) that they
* should be written to the disk immediately to avoid messing up the file
* system in the event of a crash.
*/
if ((block_type & WRITE_IMMED) && bp->b_dirt==DIRTY && bp->b_dev != NO_DEV)
rw_block(bp, WRITING);
}
PRIVATE void rm_lru(bp)/*将块从LRU链中删除，简单的链表操作*/
struct buf *bp;
{
/* Remove a block from its LRU chain. */
struct buf *next_ptr, *prev_ptr;
bufs_in_use++;
next_ptr = bp->b_next; /* successor on LRU chain */
prev_ptr = bp->b_prev; /* predecessor on LRU chain */
if (prev_ptr != NIL_BUF)
prev_ptr->b_next = next_ptr;
else
front = next_ptr; /* this block was at front of chain */
if (next_ptr != NIL_BUF)
next_ptr->b_prev = prev_ptr;
else
rear = prev_ptr; /* this block was at rear of chain */
}
