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 // One reason the page size is 4k is that the x86 segment size 6 // granularity is 4k. 7 8 #include "types.h" 9 #include "defs.h" 10 #include "param.h" 11 #include "mmu.h" 12 #include "spinlock.h" 13 14 struct run { 15 struct run *next; 16 int len; // bytes 17 }; 18 19 struct { 20 struct spinlock lock; 21 struct run *freelist; 22 } kmem; 23 24 int nfreemem; 25 26 static void 27 printfreelist(void) 28 { 29 struct run *r, **rp; 30 cprintf("freelist:\n"); 31 for(rp=&kmem.freelist; (r=*rp) != 0; rp=&r->next){ 32 cprintf("0x%x %d=0x%x\n", r, r->len, r->len); 33 } 34 } 35 36 // Initialize free list of physical pages. 37 // This code cheats by just considering one megabyte of 38 // pages after end. Real systems would determine the 39 // amount of memory available in the system and use it all. 40 void 41 kinit(char *p, uint len) 42 { 43 initlock(&kmem.lock, "kmem"); 44 cprintf("end 0x%x free = %d(0x%x)\n", p, len); 45 nfreemem = 0; 46 kfree(p, len); 47 } 48 49 // Free the len bytes of memory pointed at by v, 50 // which normally should have been returned by a 51 // call to kalloc(len). (The exception is when 52 // initializing the allocator; see kinit above.) 53 void 54 kfree(char *v, int len) 55 { 56 struct run *r, *rend, **rp, *p, *pend; 57 58 if(len <= 0 || len % PGSIZE) 59 panic("kfree"); 60 61 // Fill with junk to catch dangling refs. 62 memset(v, 1, len); 63 64 acquire(&kmem.lock); 65 nfreemem += len; 66 p = (struct run*)v; 67 pend = (struct run*)(v + len); 68 for(rp=&kmem.freelist; (r=*rp) != 0 && r <= pend; rp=&r->next){ 69 rend = (struct run*)((char*)r + r->len); 70 if(r <= p && p < rend) { 71 cprintf("freeing a free page: r = 0x%x p = 0x%x rend = 0x%x\n", 72 r, p, rend); 73 panic("freeing free page"); 74 } 75 if(rend == p){ // r before p: expand r to include p 76 r->len += len; 77 if(r->next && r->next == pend){ // r now next to r->next? 78 r->len += r->next->len; 79 r->next = r->next->next; 80 } 81 goto out; 82 } 83 if(pend == r){ // p before r: expand p to include, replace r 84 p->len = len + r->len; 85 p->next = r->next; 86 *rp = p; 87 goto out; 88 } 89 } 90 // Insert p before r in list. 91 p->len = len; 92 p->next = r; 93 *rp = p; 94 95 out: 96 release(&kmem.lock); 97 } 98 99 // Allocate n bytes of physical memory. 100 // Returns a kernel-segment pointer. 101 // Returns 0 if the memory cannot be allocated. 102 char* 103 kalloc(int n) 104 { 105 char *p; 106 struct run *r, **rp; 107 108 if(n % PGSIZE || n <= 0) 109 panic("kalloc"); 110 111 acquire(&kmem.lock); 112 for(rp=&kmem.freelist; (r=*rp) != 0; rp=&r->next){ 113 if(r->len >= n){ 114 r->len -= n; 115 p = (char*)r + r->len; 116 if(r->len == 0) 117 *rp = r->next; 118 nfreemem -= n; 119 release(&kmem.lock); 120 return p; 121 } 122 } 123 release(&kmem.lock); 124 125 cprintf("kalloc: out of memory\n"); 126 return 0; 127 } 128 129