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