1 // Physical memory allocator, intended to allocate 2 // memory for user processes. Allocates in 4096-byte pages. 3 // Free list is kept sorted and combines adjacent pages into 4 // long runs, to make it easier to allocate big segments. 5 // This combining is not useful now that xv6 uses paging. 6 7 #include "types.h" 8 #include "defs.h" 9 #include "param.h" 10 #include "mmu.h" 11 #include "spinlock.h" 12 13 struct run { 14 struct run *next; 15 int len; // bytes 16 }; 17 18 struct { 19 struct spinlock lock; 20 struct run *freelist; 21 } kmem; 22 23 int nfreemem; 24 25 // Initialize free list of physical pages. 26 void 27 kinit(char *p, uint len) 28 { 29 initlock(&kmem.lock, "kmem"); 30 nfreemem = 0; 31 kfree(p, len); 32 } 33 34 // Free the len bytes of memory pointed at by v, 35 // which normally should have been returned by a 36 // call to kalloc(len). (The exception is when 37 // initializing the allocator; see kinit above.) 38 void 39 kfree(char *v, int len) 40 { 41 struct run *r, *rend, **rp, *p, *pend; 42 43 if(len <= 0 || len % PGSIZE) 44 panic("kfree"); 45 46 // Fill with junk to catch dangling refs. 47 memset(v, 1, len); 48 49 acquire(&kmem.lock); 50 nfreemem += len; 51 p = (struct run*)v; 52 pend = (struct run*)(v + len); 53 for(rp=&kmem.freelist; (r=*rp) != 0 && r <= pend; rp=&r->next){ 54 rend = (struct run*)((char*)r + r->len); 55 if(r <= p && p < rend) { 56 cprintf("freeing a free page: r = 0x%x p = 0x%x rend = 0x%x\n", 57 r, p, rend); 58 panic("freeing free page"); 59 } 60 if(rend == p){ // r before p: expand r to include p 61 r->len += len; 62 if(r->next && r->next == pend){ // r now next to r->next? 63 r->len += r->next->len; 64 r->next = r->next->next; 65 } 66 goto out; 67 } 68 if(pend == r){ // p before r: expand p to include, replace r 69 p->len = len + r->len; 70 p->next = r->next; 71 *rp = p; 72 goto out; 73 } 74 } 75 // Insert p before r in list. 76 p->len = len; 77 p->next = r; 78 *rp = p; 79 80 out: 81 release(&kmem.lock); 82 } 83 84 // Allocate n bytes of physical memory. 85 // Returns a kernel-segment pointer. 86 // Returns 0 if the memory cannot be allocated. 87 char* 88 kalloc(int n) 89 { 90 char *p; 91 struct run *r, **rp; 92 93 if(n % PGSIZE || n <= 0) 94 panic("kalloc"); 95 96 acquire(&kmem.lock); 97 for(rp=&kmem.freelist; (r=*rp) != 0; rp=&r->next){ 98 if(r->len >= n){ 99 r->len -= n; 100 p = (char*)r + r->len; 101 if(r->len == 0) 102 *rp = r->next; 103 nfreemem -= n; 104 release(&kmem.lock); 105 return p; 106 } 107 } 108 release(&kmem.lock); 109 return 0; 110 } 111 112