155e95b16Srtm /* 255e95b16Srtm * physical memory allocator, intended to be used to allocate 355e95b16Srtm * memory for user processes. allocates in 4096-byte "pages". 455e95b16Srtm * free list is sorted and combines adjacent pages into 555e95b16Srtm * long runs, to make it easier to allocate big segments. 655e95b16Srtm * one reason the page size is 4k is that the x86 segment size 755e95b16Srtm * granularity is 4k. 855e95b16Srtm */ 955e95b16Srtm 1055e95b16Srtm #include "param.h" 1155e95b16Srtm #include "types.h" 1255e95b16Srtm #include "defs.h" 13*4e8f237bSrtm #include "spinlock.h" 14*4e8f237bSrtm 15*4e8f237bSrtm struct spinlock kalloc_lock; 1655e95b16Srtm 1755e95b16Srtm struct run { 1855e95b16Srtm struct run *next; 1955e95b16Srtm int len; // bytes 2055e95b16Srtm }; 2155e95b16Srtm struct run *freelist; 2255e95b16Srtm 2355e95b16Srtm void ktest(); 2455e95b16Srtm 2555e95b16Srtm /* 2655e95b16Srtm * initialize free list of physical pages. this code 2755e95b16Srtm * cheats by just considering the one megabyte of pages 2855e95b16Srtm * after _end. 2955e95b16Srtm */ 3055e95b16Srtm void 3155e95b16Srtm kinit() 3255e95b16Srtm { 3355e95b16Srtm extern int end; 3455e95b16Srtm unsigned mem; 3555e95b16Srtm char *start; 3655e95b16Srtm 3755e95b16Srtm start = (char *) &end; 3855e95b16Srtm start = (char *) (((unsigned)start + PAGE) & ~(PAGE-1)); 3955e95b16Srtm mem = 256; // XXX 4055e95b16Srtm cprintf("mem = %d\n", mem * PAGE); 4155e95b16Srtm kfree(start, mem * PAGE); 4255e95b16Srtm ktest(); 4355e95b16Srtm } 4455e95b16Srtm 4555e95b16Srtm void 4655e95b16Srtm kfree(char *cp, int len) 4755e95b16Srtm { 4855e95b16Srtm struct run **rr; 4955e95b16Srtm struct run *p = (struct run *) cp; 5055e95b16Srtm struct run *pend = (struct run *) (cp + len); 518b4e2a08Srtm int i; 5255e95b16Srtm 5355e95b16Srtm if(len % PAGE) 5455e95b16Srtm panic("kfree"); 5555e95b16Srtm 568b4e2a08Srtm // XXX fill with junk to help debug 578b4e2a08Srtm for(i = 0; i < len; i++) 588b4e2a08Srtm cp[i] = 1; 598b4e2a08Srtm 60*4e8f237bSrtm acquire(&kalloc_lock); 61*4e8f237bSrtm 6255e95b16Srtm rr = &freelist; 6355e95b16Srtm while(*rr){ 6455e95b16Srtm struct run *rend = (struct run *) ((char *)(*rr) + (*rr)->len); 6555e95b16Srtm if(p >= *rr && p < rend) 6655e95b16Srtm panic("freeing free page"); 6755e95b16Srtm if(pend == *rr){ 6855e95b16Srtm p->len = len + (*rr)->len; 6955e95b16Srtm p->next = (*rr)->next; 7055e95b16Srtm *rr = p; 71*4e8f237bSrtm goto out; 7255e95b16Srtm } 7355e95b16Srtm if(pend < *rr){ 7455e95b16Srtm p->len = len; 7555e95b16Srtm p->next = *rr; 7655e95b16Srtm *rr = p; 77*4e8f237bSrtm goto out; 7855e95b16Srtm } 7955e95b16Srtm if(p == rend){ 8055e95b16Srtm (*rr)->len += len; 8155e95b16Srtm if((*rr)->next && (*rr)->next == pend){ 8255e95b16Srtm (*rr)->len += (*rr)->next->len; 8355e95b16Srtm (*rr)->next = (*rr)->next->next; 8455e95b16Srtm } 85*4e8f237bSrtm goto out; 8655e95b16Srtm } 8755e95b16Srtm rr = &((*rr)->next); 8855e95b16Srtm } 8955e95b16Srtm p->len = len; 9055e95b16Srtm p->next = 0; 9155e95b16Srtm *rr = p; 92*4e8f237bSrtm 93*4e8f237bSrtm out: 94*4e8f237bSrtm release(&kalloc_lock); 9555e95b16Srtm } 9655e95b16Srtm 9755e95b16Srtm /* 9855e95b16Srtm * allocate n bytes of physical memory. 9955e95b16Srtm * returns a kernel-segment pointer. 10055e95b16Srtm * returns 0 if there's no run that's big enough. 10155e95b16Srtm */ 10255e95b16Srtm char * 10355e95b16Srtm kalloc(int n) 10455e95b16Srtm { 10555e95b16Srtm struct run **rr; 10655e95b16Srtm 10755e95b16Srtm if(n % PAGE) 10855e95b16Srtm panic("kalloc"); 10955e95b16Srtm 110*4e8f237bSrtm acquire(&kalloc_lock); 111*4e8f237bSrtm 11255e95b16Srtm rr = &freelist; 11355e95b16Srtm while(*rr){ 11455e95b16Srtm struct run *r = *rr; 11555e95b16Srtm if(r->len == n){ 11655e95b16Srtm *rr = r->next; 117*4e8f237bSrtm release(&kalloc_lock); 11855e95b16Srtm return (char *) r; 11955e95b16Srtm } 12055e95b16Srtm if(r->len > n){ 12155e95b16Srtm char *p = (char *)r + (r->len - n); 12255e95b16Srtm r->len -= n; 123*4e8f237bSrtm release(&kalloc_lock); 12455e95b16Srtm return p; 12555e95b16Srtm } 12655e95b16Srtm rr = &(*rr)->next; 12755e95b16Srtm } 128*4e8f237bSrtm release(&kalloc_lock); 12955e95b16Srtm return 0; 13055e95b16Srtm } 13155e95b16Srtm 13255e95b16Srtm void 13355e95b16Srtm ktest() 13455e95b16Srtm { 13555e95b16Srtm char *p1, *p2, *p3; 13655e95b16Srtm 13755e95b16Srtm // test coalescing 13855e95b16Srtm p1 = kalloc(4 * PAGE); 13955e95b16Srtm kfree(p1 + 3*PAGE, PAGE); 14055e95b16Srtm kfree(p1 + 2*PAGE, PAGE); 14155e95b16Srtm kfree(p1, PAGE); 14255e95b16Srtm kfree(p1 + PAGE, PAGE); 14355e95b16Srtm p2 = kalloc(4 * PAGE); 14455e95b16Srtm if(p2 != p1) 14555e95b16Srtm panic("ktest"); 14655e95b16Srtm kfree(p2, 4 * PAGE); 14755e95b16Srtm 14855e95b16Srtm // test finding first run that fits 14955e95b16Srtm p1 = kalloc(1 * PAGE); 15055e95b16Srtm p2 = kalloc(1 * PAGE); 15155e95b16Srtm kfree(p1, PAGE); 15255e95b16Srtm p3 = kalloc(2 * PAGE); 15355e95b16Srtm kfree(p2, PAGE); 15455e95b16Srtm kfree(p3, 2 * PAGE); 15555e95b16Srtm 15655e95b16Srtm // test running out of memory 15755e95b16Srtm p1 = 0; 15855e95b16Srtm while(1){ 15955e95b16Srtm p2 = kalloc(PAGE); 16055e95b16Srtm if(p2 == 0) 16155e95b16Srtm break; 16255e95b16Srtm *(char **)p2 = p1; 16355e95b16Srtm p1 = p2; 16455e95b16Srtm } 16555e95b16Srtm while(p1){ 16655e95b16Srtm p2 = *(char **)p1; 16755e95b16Srtm kfree(p1, PAGE); 16855e95b16Srtm p1 = p2; 16955e95b16Srtm } 17055e95b16Srtm p1 = kalloc(PAGE * 20); 17155e95b16Srtm if(p1 == 0) 17255e95b16Srtm panic("ktest2"); 17355e95b16Srtm kfree(p1, PAGE * 20); 17455e95b16Srtm } 175