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