summaryrefslogtreecommitdiff
path: root/bio.c
diff options
context:
space:
mode:
authorrtm <rtm>2006-08-12 22:34:13 +0000
committerrtm <rtm>2006-08-12 22:34:13 +0000
commitcd93074e5bed8fdbc84f2960c3219c7cf791b020 (patch)
tree1c08629ac66cb608ed03601ca0edce0170f71546 /bio.c
parent22bac2cb9d0b8050573a4b5c6cb5d8f460ee4167 (diff)
downloadxv6-labs-cd93074e5bed8fdbc84f2960c3219c7cf791b020.tar.gz
xv6-labs-cd93074e5bed8fdbc84f2960c3219c7cf791b020.tar.bz2
xv6-labs-cd93074e5bed8fdbc84f2960c3219c7cf791b020.zip
LRU disk cache replacement
Diffstat (limited to 'bio.c')
-rw-r--r--bio.c37
1 files changed, 28 insertions, 9 deletions
diff --git a/bio.c b/bio.c
index 2db9694..e344343 100644
--- a/bio.c
+++ b/bio.c
@@ -10,27 +10,41 @@
struct buf buf[NBUF];
struct spinlock buf_table_lock;
+// linked list of all buffers, through prev/next.
+// bufhead->next is most recently used.
+// bufhead->tail is least recently used.
+struct buf bufhead;
+
void
binit(void)
{
+ struct buf *b;
+
initlock(&buf_table_lock, "buf_table");
+
+ bufhead.prev = &bufhead;
+ bufhead.next = &bufhead;
+ for(b = buf; b < buf+NBUF; b++){
+ b->next = bufhead.next;
+ b->prev = &bufhead;
+ bufhead.next->prev = b;
+ bufhead.next = b;
+ }
}
struct buf *
getblk(uint dev, uint sector)
{
struct buf *b;
- static struct buf *scan = buf;
- int i;
acquire(&buf_table_lock);
while(1){
- for(b = buf; b < buf+NBUF; b++)
+ for(b = bufhead.next; b != &bufhead; b = b->next)
if((b->flags & (B_BUSY|B_VALID)) && b->dev == dev && b->sector == sector)
break;
- if(b < buf+NBUF){
+ if(b != &bufhead){
if(b->flags & B_BUSY){
sleep(buf, &buf_table_lock);
} else {
@@ -39,10 +53,7 @@ getblk(uint dev, uint sector)
return b;
}
} else {
- for(i = 0; i < NBUF; i++){
- b = scan++;
- if(scan >= buf+NBUF)
- scan = buf;
+ for(b = bufhead.prev; b != &bufhead; b = b->prev){
if((b->flags & B_BUSY) == 0){
b->flags = B_BUSY;
b->dev = dev;
@@ -64,8 +75,9 @@ bread(uint dev, uint sector)
extern struct spinlock ide_lock;
b = getblk(dev, sector);
- if(b->flags & B_VALID)
+ if(b->flags & B_VALID){
return b;
+ }
acquire(&ide_lock);
c = ide_start_rw(dev & 0xff, sector, b->data, 1, 1);
@@ -99,6 +111,13 @@ brelse(struct buf *b)
acquire(&buf_table_lock);
+ b->next->prev = b->prev;
+ b->prev->next = b->next;
+ b->next = bufhead.next;
+ b->prev = &bufhead;
+ bufhead.next->prev = b;
+ bufhead.next = b;
+
b->flags &= ~B_BUSY;
wakeup(buf);