302 lines
7.6 KiB
C
302 lines
7.6 KiB
C
// Buffer cache.
|
|
//
|
|
// The buffer cache is a linked list of buf structures holding
|
|
// cached copies of disk block contents. Caching disk blocks
|
|
// in memory reduces the number of disk reads and also provides
|
|
// a synchronization point for disk blocks used by multiple processes.
|
|
//
|
|
// Interface:
|
|
// * To get a buffer for a particular disk block, call bread.
|
|
// * After changing buffer data, call bwrite to write it to disk.
|
|
// * When done with the buffer, call brelse.
|
|
// * Do not use the buffer after calling brelse.
|
|
// * Only one process at a time can use a buffer,
|
|
// so do not keep them longer than necessary.
|
|
|
|
|
|
#include "types.h"
|
|
#include "param.h"
|
|
#include "spinlock.h"
|
|
#include "sleeplock.h"
|
|
#include "riscv.h"
|
|
#include "defs.h"
|
|
#include "fs.h"
|
|
#include "buf.h"
|
|
|
|
|
|
// TODO: use sleeplock instead of spinlock
|
|
|
|
struct {
|
|
struct spinlock lock;
|
|
struct buf buf[NBUF];
|
|
#define NHASH 233
|
|
// struct hash_t{
|
|
// uint pos;
|
|
// struct hash_t *nxt;
|
|
// }hash[NHASH];
|
|
uint hash_head[NHASH];
|
|
uint nxt[NBUF];
|
|
struct spinlock hashlock[NHASH];
|
|
uint freelist_head[NCPU];
|
|
// Linked list of all buffers, through prev/next.
|
|
// Sorted by how recently the buffer was used.
|
|
// head.next is most recent, head.prev is least.
|
|
// struct buf head;
|
|
struct spinlock freelistlock[NCPU];
|
|
} bcache;
|
|
|
|
uint hasher(uint dev,uint blockno){
|
|
return ((uint64)dev<<32|blockno)%NHASH;
|
|
}
|
|
|
|
int hash_get(uint dev,uint blockno){
|
|
const uint hash_pos=hasher(dev, blockno);
|
|
int pos=-1;
|
|
// acquire(&bcache.hashlock[hash_pos]);
|
|
for(int cur=bcache.hash_head[hash_pos];cur!=-1;cur=bcache.nxt[cur])
|
|
if(bcache.buf[cur].dev==dev && bcache.buf[cur].blockno==blockno){
|
|
pos=cur;
|
|
goto RET;
|
|
}
|
|
|
|
RET:
|
|
|
|
// release(&bcache.hashlock[hash_pos]);
|
|
// printf("%u\n",pos);
|
|
return pos;
|
|
}
|
|
|
|
void hash_add(uint dev,uint blockno,uint buf_pos){
|
|
const uint hash_pos=hasher(dev, blockno);
|
|
// acquire(&bcache.hashlock[hash_pos]);
|
|
bcache.nxt[buf_pos]=bcache.hash_head[hash_pos];
|
|
bcache.hash_head[hash_pos]=buf_pos;
|
|
// release(&bcache.hashlock[hash_pos]);
|
|
}
|
|
|
|
void hash_del(uint dev,uint blockno){
|
|
const uint hash_pos=hasher(dev, blockno);
|
|
push_off();
|
|
const uint cpu=cpuid();
|
|
pop_off();
|
|
acquire(&bcache.hashlock[hash_pos]);
|
|
for(int cur=bcache.hash_head[hash_pos],pre=-2;cur!=-1;cur=bcache.nxt[cur]){
|
|
if(bcache.buf[cur].dev==dev && bcache.buf[cur].blockno==blockno){
|
|
struct buf *b=&bcache.buf[cur];
|
|
--b->refcnt;
|
|
if (b->refcnt == 0) {
|
|
if(pre==-2){// the head is what we are looking for
|
|
bcache.hash_head[hash_pos]=bcache.nxt[cur];
|
|
}else{
|
|
bcache.nxt[pre]=bcache.nxt[cur];
|
|
}
|
|
bcache.nxt[cur]=-1;
|
|
for(int i=cpu;;i=(i+1)%NCPU){
|
|
push_off();
|
|
if(holding(&bcache.freelistlock[i])){
|
|
pop_off();
|
|
continue;
|
|
}
|
|
pop_off();
|
|
acquire(&bcache.freelistlock[i]);
|
|
const int pos=b-bcache.buf;
|
|
// printf("%d\n",pos);
|
|
bcache.nxt[pos]=bcache.freelist_head[i];
|
|
bcache.freelist_head[i]=pos;
|
|
|
|
// DEBUG();
|
|
// printf("%u\n",bcache.freelist_head);
|
|
|
|
release(&bcache.freelistlock[i]);
|
|
break;
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
pre=cur;
|
|
}
|
|
release(&bcache.hashlock[hash_pos]);
|
|
}
|
|
|
|
void
|
|
binit(void)
|
|
{
|
|
struct buf *b;
|
|
|
|
initlock(&bcache.lock, "bcache");
|
|
for(int i=0;i<NHASH;i++){
|
|
initlock(&bcache.hashlock[i], "bcache_hashtable");
|
|
bcache.hash_head[i]=-1;
|
|
}
|
|
for(int i=0;i<NCPU;++i){
|
|
bcache.freelist_head[i]=-1;
|
|
initlock(&bcache.freelistlock[i], "bcache_freelist");
|
|
}
|
|
// Create linked list of buffers
|
|
// bcache.head.prev = &bcache.head;
|
|
// bcache.head.next = &bcache.head;
|
|
int which=0;
|
|
for(b = bcache.buf; b < bcache.buf+NBUF; b++){
|
|
// b->next = bcache.head.next;
|
|
// b->prev = &bcache.head;
|
|
initsleeplock(&b->lock, "buffer");
|
|
const uint cur=b-bcache.buf;
|
|
bcache.nxt[cur]=bcache.freelist_head[which];
|
|
bcache.freelist_head[which]=cur;
|
|
which=(which+1)%NCPU;
|
|
// bcache.head.next->prev = b;
|
|
// bcache.head.next = b;
|
|
}
|
|
}
|
|
|
|
// Look through buffer cache for block on device dev.
|
|
// If not found, allocate a buffer.
|
|
// In either case, return locked buffer.
|
|
static struct buf*
|
|
bget(uint dev, uint blockno)
|
|
{
|
|
struct buf *b;
|
|
// acquire(&bcache.lock);
|
|
const uint hash_pos=hasher(dev, blockno);
|
|
acquire(&bcache.hashlock[hash_pos]);
|
|
const int pos=hash_get(dev, blockno);
|
|
// Is the block already cached?
|
|
// for(b = bcache.head.next; b != &bcache.head; b = b->next){
|
|
// if(b->dev == dev && b->blockno == blockno){
|
|
// b->refcnt++;
|
|
// release(&bcache.lock);
|
|
// acquiresleep(&b->lock);
|
|
// return b;
|
|
// }
|
|
// }
|
|
if(pos>=0){
|
|
b=&bcache.buf[pos];
|
|
// acquire(&bcache.hashlock[hash_pos]);
|
|
++bcache.buf[pos].refcnt;
|
|
release(&bcache.hashlock[hash_pos]);
|
|
acquiresleep(&b->lock);
|
|
// release(&bcache.lock);
|
|
return b;
|
|
}
|
|
push_off();
|
|
const uint cpu=cpuid();
|
|
pop_off();
|
|
// Not cached.
|
|
// Recycle the least recently used (LRU) unused buffer.
|
|
for(int i=cpu;;i=(i+1)%NCPU){
|
|
push_off();
|
|
if(holding(&bcache.freelistlock[i])){
|
|
pop_off();
|
|
continue;
|
|
}
|
|
pop_off();
|
|
acquire(&bcache.freelistlock[i]);
|
|
if(bcache.freelist_head[i]==-1){
|
|
release(&bcache.freelistlock[i]);
|
|
continue;
|
|
}
|
|
// DEBUG();
|
|
// for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
|
|
// if(b->refcnt == 0) {
|
|
// hash_add(dev, blockno, b-bcache.buf);
|
|
// b->dev = dev;
|
|
// b->blockno = blockno;
|
|
// b->valid = 0;
|
|
// b->refcnt = 1;
|
|
// release(&bcache.lock);
|
|
// acquiresleep(&b->lock);
|
|
// return b;
|
|
// }
|
|
// }
|
|
// for(uint cur=bcache.freelist_head;cur!=-1;cur=bcache.nxt[cur])
|
|
// DEBUG();
|
|
// printf("%u\n",bcache.freelist_head);
|
|
b=&bcache.buf[bcache.freelist_head[i]];
|
|
const int ori=bcache.freelist_head[i];
|
|
bcache.freelist_head[i]=bcache.nxt[bcache.freelist_head[i]];
|
|
hash_add(dev,blockno,ori);
|
|
release(&bcache.hashlock[hash_pos]);
|
|
b->dev=dev;
|
|
b->blockno=blockno;
|
|
b->valid=0;
|
|
b->refcnt=1;
|
|
release(&bcache.freelistlock[i]);
|
|
acquiresleep(&b->lock);
|
|
// release(&bcache.lock);
|
|
return b;
|
|
}
|
|
panic("bget: no buffers");
|
|
}
|
|
|
|
// Return a locked buf with the contents of the indicated block.
|
|
struct buf*
|
|
bread(uint dev, uint blockno)
|
|
{
|
|
struct buf *b;
|
|
|
|
b = bget(dev, blockno);
|
|
if(!b->valid) {
|
|
virtio_disk_rw(b, 0);
|
|
b->valid = 1;
|
|
}
|
|
return b;
|
|
}
|
|
|
|
// Write b's contents to disk. Must be locked.
|
|
void
|
|
bwrite(struct buf *b)
|
|
{
|
|
if(!holdingsleep(&b->lock))
|
|
panic("bwrite");
|
|
virtio_disk_rw(b, 1);
|
|
}
|
|
|
|
// Release a locked buffer.
|
|
// Move to the head of the most-recently-used list.
|
|
void
|
|
brelse(struct buf *b)
|
|
{
|
|
|
|
if(!holdingsleep(&b->lock))
|
|
panic("brelse");
|
|
|
|
releasesleep(&b->lock);
|
|
|
|
// acquire(&bcache.lock);
|
|
|
|
hash_del(b->dev, b->blockno);
|
|
// no one is waiting for it.
|
|
// b->next->prev = b->prev;
|
|
// b->prev->next = b->next;
|
|
// b->next = bcache.head.next;
|
|
// b->prev = &bcache.head;
|
|
// bcache.head.next->prev = b;
|
|
// bcache.head.next = b;gi
|
|
|
|
|
|
|
|
// release(&bcache.lock);
|
|
}
|
|
|
|
void
|
|
bpin(struct buf *b) {
|
|
// acquire(&bcache.lock);
|
|
const uint hash_pos=hasher(b->dev, b->blockno);
|
|
acquire(&bcache.hashlock[hash_pos]);
|
|
b->refcnt++;
|
|
release(&bcache.hashlock[hash_pos]);
|
|
// release(&bcache.lock);
|
|
}
|
|
|
|
void
|
|
bunpin(struct buf *b) {
|
|
// acquire(&bcache.lock);
|
|
const uint hash_pos=hasher(b->dev, b->blockno);
|
|
acquire(&bcache.hashlock[hash_pos]);
|
|
b->refcnt--;
|
|
release(&bcache.hashlock[hash_pos]);
|
|
// release(&bcache.lock);
|
|
}
|
|
|
|
|