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