1*f5527388Srsc // Physical memory allocator, intended to allocate 2*f5527388Srsc // memory for user processes. Allocates in 4096-byte "pages". 3*f5527388Srsc // Free list is kept sorted and combines adjacent pages into 4*f5527388Srsc // long runs, to make it easier to allocate big segments. 5*f5527388Srsc // One reason the page size is 4k is that the x86 segment size 6*f5527388Srsc // granularity is 4k. 755e95b16Srtm 855e95b16Srtm #include "param.h" 955e95b16Srtm #include "types.h" 1055e95b16Srtm #include "defs.h" 118148b6eeSrtm #include "param.h" 128148b6eeSrtm #include "mmu.h" 138148b6eeSrtm #include "proc.h" 144e8f237bSrtm #include "spinlock.h" 154e8f237bSrtm 165be0039cSrtm struct spinlock kalloc_lock; 1755e95b16Srtm 1855e95b16Srtm struct run { 1955e95b16Srtm struct run *next; 2055e95b16Srtm int len; // bytes 2155e95b16Srtm }; 2255e95b16Srtm struct run *freelist; 2355e95b16Srtm 24*f5527388Srsc // Initialize free list of physical pages. 25*f5527388Srsc // This code cheats by just considering one megabyte of 26*f5527388Srsc // pages after _end. Real systems would determine the 27*f5527388Srsc // amount of memory available in the system and use it all. 2855e95b16Srtm void 2984d79573Srsc kinit(void) 3055e95b16Srtm { 3155e95b16Srtm extern int end; 32b5ee5165Srsc uint mem; 3355e95b16Srtm char *start; 3455e95b16Srtm 355be0039cSrtm initlock(&kalloc_lock, "kalloc"); 3655e95b16Srtm start = (char*) &end; 37b5ee5165Srsc start = (char*) (((uint)start + PAGE) & ~(PAGE-1)); 3882537b71Srtm mem = 256; // assume 256 pages of RAM 3955e95b16Srtm cprintf("mem = %d\n", mem * PAGE); 4055e95b16Srtm kfree(start, mem * PAGE); 4155e95b16Srtm } 4255e95b16Srtm 4355e95b16Srtm void 4455e95b16Srtm kfree(char *cp, int len) 4555e95b16Srtm { 4655e95b16Srtm struct run **rr; 4755e95b16Srtm struct run *p = (struct run*) cp; 4855e95b16Srtm struct run *pend = (struct run*) (cp + len); 498b4e2a08Srtm int i; 5055e95b16Srtm 5155e95b16Srtm if(len % PAGE) 5255e95b16Srtm panic("kfree"); 5355e95b16Srtm 548b4e2a08Srtm // XXX fill with junk to help debug 558b4e2a08Srtm for(i = 0; i < len; i++) 568b4e2a08Srtm cp[i] = 1; 578b4e2a08Srtm 584e8f237bSrtm acquire(&kalloc_lock); 594e8f237bSrtm 6055e95b16Srtm rr = &freelist; 6155e95b16Srtm while(*rr){ 6255e95b16Srtm struct run *rend = (struct run*) ((char*)(*rr) + (*rr)->len); 6355e95b16Srtm if(p >= *rr && p < rend) 6455e95b16Srtm panic("freeing free page"); 6555e95b16Srtm if(pend == *rr){ 6655e95b16Srtm p->len = len + (*rr)->len; 6755e95b16Srtm p->next = (*rr)->next; 6855e95b16Srtm *rr = p; 694e8f237bSrtm goto out; 7055e95b16Srtm } 7155e95b16Srtm if(pend < *rr){ 7255e95b16Srtm p->len = len; 7355e95b16Srtm p->next = *rr; 7455e95b16Srtm *rr = p; 754e8f237bSrtm goto out; 7655e95b16Srtm } 7755e95b16Srtm if(p == rend){ 7855e95b16Srtm (*rr)->len += len; 7955e95b16Srtm if((*rr)->next && (*rr)->next == pend){ 8055e95b16Srtm (*rr)->len += (*rr)->next->len; 8155e95b16Srtm (*rr)->next = (*rr)->next->next; 8255e95b16Srtm } 834e8f237bSrtm goto out; 8455e95b16Srtm } 8555e95b16Srtm rr = &((*rr)->next); 8655e95b16Srtm } 8755e95b16Srtm p->len = len; 8855e95b16Srtm p->next = 0; 8955e95b16Srtm *rr = p; 904e8f237bSrtm 914e8f237bSrtm out: 924e8f237bSrtm release(&kalloc_lock); 9355e95b16Srtm } 9455e95b16Srtm 95*f5527388Srsc // Allocate n bytes of physical memory. 96*f5527388Srsc // Returns a kernel-segment pointer. 97*f5527388Srsc // Returns 0 if the memory cannot be allocated. 9855e95b16Srtm char* 9955e95b16Srtm kalloc(int n) 10055e95b16Srtm { 10155e95b16Srtm struct run **rr; 10255e95b16Srtm 10355e95b16Srtm if(n % PAGE) 10455e95b16Srtm panic("kalloc"); 10555e95b16Srtm 1064e8f237bSrtm acquire(&kalloc_lock); 1074e8f237bSrtm 10855e95b16Srtm rr = &freelist; 10955e95b16Srtm while(*rr){ 11055e95b16Srtm struct run *r = *rr; 11155e95b16Srtm if(r->len == n){ 11255e95b16Srtm *rr = r->next; 1134e8f237bSrtm release(&kalloc_lock); 11455e95b16Srtm return (char*) r; 11555e95b16Srtm } 11655e95b16Srtm if(r->len > n){ 11755e95b16Srtm char *p = (char*)r + (r->len - n); 11855e95b16Srtm r->len -= n; 1194e8f237bSrtm release(&kalloc_lock); 12055e95b16Srtm return p; 12155e95b16Srtm } 12255e95b16Srtm rr = &(*rr)->next; 12355e95b16Srtm } 1244e8f237bSrtm release(&kalloc_lock); 1252aa4c3bcSrtm cprintf("kalloc: out of memory\n"); 12655e95b16Srtm return 0; 12755e95b16Srtm } 128