void kinit() { for (int i = 0; i < NCPU; i++) { // Call initlock for each of your locks, and pass a name that starts with "kmem". char *name = kmem_lock_name[i]; snprintf(name, LOCK_NAME_LEN - 1, "kmem_cpu_%d", i); initlock(&kmem[i].lock, name); } // Let freerange give all free memory to the CPU running freerange. freerange(end, (void *)PHYSTOP); }
// Free the page of physical memory pointed at by v, // add the page to CPU's list with given cpuid. void kfree_cpu(void *pa, int cpuid) { structrun *r;
// Free the page of physical memory pointed at by pa, // add the page to current CPU's free list voidkfree(void *pa) { push_off(); int cpu = cpuid(); pop_off(); kfree_cpu(pa, cpu); }
// Allocate one 4096-byte page of physical memory. // Returns a pointer that the kernel can use. // Returns 0 if the memory cannot be allocated. void * kalloc(void) { structrun *r;
push_off(); int cpu = cpuid(); pop_off(); acquire(&kmem[cpu].lock); r = kmem[cpu].freelist; if(r) { // if current cpu freelist is not empty kmem[cpu].freelist = r->next; release(&kmem[cpu].lock); } else { //else steal from other cpu's freelist release(&kmem[cpu].lock); for (int i = 0; i < NCPU; i++) { // traverse each cpu's freelist except current one if (i == cpu) { continue; } acquire(&kmem[i].lock); r = kmem[i].freelist; if(r) { // if node found, no need to search for next cpu's freelist, just break kmem[i].freelist = r->next; release(&kmem[i].lock); break; } release(&kmem[i].lock); } }
if(r) memset((char*)r, 5, PGSIZE); // fill with junk return (void*)r; }
测试
现在我们在主目录下运行make clean; make qemu，然后在xv6下尝试运行kalloctest和usertests sbrkmuch，看一下结果：
// 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. structbufhead; } bcache;
structbuf { int valid; // has data been read from disk? int disk; // does disk "own" buf? uint dev; uint blockno; structsleeplocklock; uint refcnt; structbuf *prev;// LRU cache list structbuf *next; uchar data[BSIZE]; };
// 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. structbufhead; } bcache;
structbuf { int valid; // has data been read from disk? int disk; // does disk "own" buf? uint dev; uint blockno; structsleeplocklock; uint refcnt; structbuf *prev;// LRU cache list structbuf *next; uchar data[BSIZE]; };
// 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); b->refcnt--; if (b->refcnt == 0) { // 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; } release(&bcache.lock); }
// Look through buffer cache for block on device dev. // If not found, allocate a buffer. // In either case, return locked buffer. staticstruct buf* bget(uint dev, uint blockno) { structbuf *b;
acquire(&bcache.lock);
// 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; } }
// Not cached. // Recycle the least recently used (LRU) unused buffer. for(b = bcache.head.prev; b != &bcache.head; b = b->prev){ if(b->refcnt == 0) { b->dev = dev; b->blockno = blockno; b->valid = 0; b->refcnt = 1; release(&bcache.lock); acquiresleep(&b->lock); return b; } } panic("bget: no buffers"); }
structbuf { int valid; // has data been read from disk? int disk; // does disk "own" buf? uint dev; uint blockno; structsleeplocklock; uint refcnt; structbuf *next; uchar data[BSIZE]; uint timestamp; };
// Release a locked buffer and update the timestamp void brelse(struct buf *b) { if(!holdingsleep(&b->lock)) panic("brelse");
releasesleep(&b->lock);
int index = hash(b->dev, b->blockno); acquire(&bcache.hashtable[index].lock); b->refcnt--; if (b->refcnt == 0) { // no one is waiting for it. b->timestamp = ticks; } release(&bcache.hashtable[index].lock); }
bpin/bunpin计数加减实现
这块原理同上brelse，我们每次直接锁对应bucket即可：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
void bpin(struct buf *b) { int index = hash(b->dev, b->blockno); acquire(&bcache.hashtable[index].lock); b->refcnt++; release(&bcache.hashtable[index].lock); }
void bunpin(struct buf *b) { int index = hash(b->dev, b->blockno); acquire(&bcache.hashtable[index].lock); b->refcnt--; release(&bcache.hashtable[index].lock); }
// Look through buffer cache for block on device dev. // If not found, allocate a buffer. // In either case, return locked buffer. staticstruct buf* bget(uint dev, uint blockno) { structbuf *b, *prev_replace_buf; structbucket *bucket, *prev_bucket, *cur_bucket;
int index = hash(dev, blockno); bucket = bcache.hashtable + index;
// Is the block already cached? acquire(&bucket->lock); for (b = bucket->head.next; b; b = b->next) { if(b->dev == dev && b->blockno == blockno){ b->refcnt++; release(&bucket->lock); acquiresleep(&b->lock); return b; } } release(&bucket->lock);
// Acquire evict-lock, serialize the evict action acquire(&bcache.lock);
// Check on current bucket again. // If another eviction happened between release of bucket-lock and acquire of evict-lock // There is chance that block has cached in current bucket but the process is unaware. // Without the check, blocks with same blockno could exist in the bucket. acquire(&bucket->lock); for (b = bucket->head.next; b; b = b->next) { if(b->dev == dev && b->blockno == blockno){ b->refcnt++; release(&bucket->lock); release(&bcache.lock); acquiresleep(&b->lock); return b; } } release(&bucket->lock);
// Not cached. // Recycle the least recently used (LRU) unused buffer. // Traverse each bucket and each buffer, pick the least recently used buffer prev_replace_buf = (void*)0; // the prev node of the buf to evict prev_bucket = (void*)0; // prev locked bucket, null initially for (cur_bucket = bcache.hashtable; cur_bucket < bcache.hashtable + NBUCKET; cur_bucket++) { acquire(&cur_bucket->lock); int found = 0; for (b = &cur_bucket->head; b->next; b = b->next) { if (b->next->refcnt == 0 && (!prev_replace_buf || b->next->timestamp < prev_replace_buf->next->timestamp)) { found = 1; prev_replace_buf = b; } } if (!found) { release(&cur_bucket->lock); } else { // if smaller time stamp found in the bucket, consider releasing prev holding bucket, // which is no longer needed if (prev_bucket) { release(&prev_bucket->lock); } prev_bucket = cur_bucket; } } if (!prev_replace_buf) { panic("bget: no buffers"); } b = prev_replace_buf->next;
if (prev_bucket != bucket) { // Delete the buf to evict from its bucket, prev_replace_buf->next = b->next; release(&prev_bucket->lock); // Add the buf to bucket acquire(&bucket->lock); b->next = bucket->head.next; bucket->head.next = b; }
