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" 1355e95b16Srtm 1455e95b16Srtm struct run { 1555e95b16Srtm struct run *next; 1655e95b16Srtm int len; // bytes 1755e95b16Srtm }; 1855e95b16Srtm struct run *freelist; 1955e95b16Srtm 2055e95b16Srtm void ktest(); 2155e95b16Srtm 2255e95b16Srtm /* 2355e95b16Srtm * initialize free list of physical pages. this code 2455e95b16Srtm * cheats by just considering the one megabyte of pages 2555e95b16Srtm * after _end. 2655e95b16Srtm */ 2755e95b16Srtm void 2855e95b16Srtm kinit() 2955e95b16Srtm { 3055e95b16Srtm extern int end; 3155e95b16Srtm unsigned mem; 3255e95b16Srtm char *start; 3355e95b16Srtm 3455e95b16Srtm start = (char *) &end; 3555e95b16Srtm start = (char *) (((unsigned)start + PAGE) & ~(PAGE-1)); 3655e95b16Srtm mem = 256; // XXX 3755e95b16Srtm cprintf("mem = %d\n", mem * PAGE); 3855e95b16Srtm kfree(start, mem * PAGE); 3955e95b16Srtm ktest(); 4055e95b16Srtm } 4155e95b16Srtm 4255e95b16Srtm void 4355e95b16Srtm kfree(char *cp, int len) 4455e95b16Srtm { 4555e95b16Srtm struct run **rr; 4655e95b16Srtm struct run *p = (struct run *) cp; 4755e95b16Srtm struct run *pend = (struct run *) (cp + len); 48*8b4e2a08Srtm int i; 4955e95b16Srtm 5055e95b16Srtm if(len % PAGE) 5155e95b16Srtm panic("kfree"); 5255e95b16Srtm 53*8b4e2a08Srtm // XXX fill with junk to help debug 54*8b4e2a08Srtm for(i = 0; i < len; i++) 55*8b4e2a08Srtm cp[i] = 1; 56*8b4e2a08Srtm 5755e95b16Srtm rr = &freelist; 5855e95b16Srtm while(*rr){ 5955e95b16Srtm struct run *rend = (struct run *) ((char *)(*rr) + (*rr)->len); 6055e95b16Srtm if(p >= *rr && p < rend) 6155e95b16Srtm panic("freeing free page"); 6255e95b16Srtm if(pend == *rr){ 6355e95b16Srtm p->len = len + (*rr)->len; 6455e95b16Srtm p->next = (*rr)->next; 6555e95b16Srtm *rr = p; 6655e95b16Srtm return; 6755e95b16Srtm } 6855e95b16Srtm if(pend < *rr){ 6955e95b16Srtm p->len = len; 7055e95b16Srtm p->next = *rr; 7155e95b16Srtm *rr = p; 7255e95b16Srtm return; 7355e95b16Srtm } 7455e95b16Srtm if(p == rend){ 7555e95b16Srtm (*rr)->len += len; 7655e95b16Srtm if((*rr)->next && (*rr)->next == pend){ 7755e95b16Srtm (*rr)->len += (*rr)->next->len; 7855e95b16Srtm (*rr)->next = (*rr)->next->next; 7955e95b16Srtm } 8055e95b16Srtm return; 8155e95b16Srtm } 8255e95b16Srtm rr = &((*rr)->next); 8355e95b16Srtm } 8455e95b16Srtm p->len = len; 8555e95b16Srtm p->next = 0; 8655e95b16Srtm *rr = p; 8755e95b16Srtm } 8855e95b16Srtm 8955e95b16Srtm /* 9055e95b16Srtm * allocate n bytes of physical memory. 9155e95b16Srtm * returns a kernel-segment pointer. 9255e95b16Srtm * returns 0 if there's no run that's big enough. 9355e95b16Srtm */ 9455e95b16Srtm char * 9555e95b16Srtm kalloc(int n) 9655e95b16Srtm { 9755e95b16Srtm struct run **rr; 9855e95b16Srtm 9955e95b16Srtm if(n % PAGE) 10055e95b16Srtm panic("kalloc"); 10155e95b16Srtm 10255e95b16Srtm rr = &freelist; 10355e95b16Srtm while(*rr){ 10455e95b16Srtm struct run *r = *rr; 10555e95b16Srtm if(r->len == n){ 10655e95b16Srtm *rr = r->next; 10755e95b16Srtm return (char *) r; 10855e95b16Srtm } 10955e95b16Srtm if(r->len > n){ 11055e95b16Srtm char *p = (char *)r + (r->len - n); 11155e95b16Srtm r->len -= n; 11255e95b16Srtm return p; 11355e95b16Srtm } 11455e95b16Srtm rr = &(*rr)->next; 11555e95b16Srtm } 11655e95b16Srtm return 0; 11755e95b16Srtm } 11855e95b16Srtm 11955e95b16Srtm void 12055e95b16Srtm ktest() 12155e95b16Srtm { 12255e95b16Srtm char *p1, *p2, *p3; 12355e95b16Srtm 12455e95b16Srtm // test coalescing 12555e95b16Srtm p1 = kalloc(4 * PAGE); 12655e95b16Srtm kfree(p1 + 3*PAGE, PAGE); 12755e95b16Srtm kfree(p1 + 2*PAGE, PAGE); 12855e95b16Srtm kfree(p1, PAGE); 12955e95b16Srtm kfree(p1 + PAGE, PAGE); 13055e95b16Srtm p2 = kalloc(4 * PAGE); 13155e95b16Srtm if(p2 != p1) 13255e95b16Srtm panic("ktest"); 13355e95b16Srtm kfree(p2, 4 * PAGE); 13455e95b16Srtm 13555e95b16Srtm // test finding first run that fits 13655e95b16Srtm p1 = kalloc(1 * PAGE); 13755e95b16Srtm p2 = kalloc(1 * PAGE); 13855e95b16Srtm kfree(p1, PAGE); 13955e95b16Srtm p3 = kalloc(2 * PAGE); 14055e95b16Srtm kfree(p2, PAGE); 14155e95b16Srtm kfree(p3, 2 * PAGE); 14255e95b16Srtm 14355e95b16Srtm // test running out of memory 14455e95b16Srtm p1 = 0; 14555e95b16Srtm while(1){ 14655e95b16Srtm p2 = kalloc(PAGE); 14755e95b16Srtm if(p2 == 0) 14855e95b16Srtm break; 14955e95b16Srtm *(char **)p2 = p1; 15055e95b16Srtm p1 = p2; 15155e95b16Srtm } 15255e95b16Srtm while(p1){ 15355e95b16Srtm p2 = *(char **)p1; 15455e95b16Srtm kfree(p1, PAGE); 15555e95b16Srtm p1 = p2; 15655e95b16Srtm } 15755e95b16Srtm p1 = kalloc(PAGE * 20); 15855e95b16Srtm if(p1 == 0) 15955e95b16Srtm panic("ktest2"); 16055e95b16Srtm kfree(p1, PAGE * 20); 16155e95b16Srtm 16255e95b16Srtm cprintf("ktest ok\n"); 16355e95b16Srtm } 164