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*8148b6eeSrtm #include "param.h" 14*8148b6eeSrtm #include "mmu.h" 15*8148b6eeSrtm #include "proc.h" 164e8f237bSrtm #include "spinlock.h" 174e8f237bSrtm 184e8f237bSrtm struct spinlock kalloc_lock; 1955e95b16Srtm 2055e95b16Srtm struct run { 2155e95b16Srtm struct run *next; 2255e95b16Srtm int len; // bytes 2355e95b16Srtm }; 2455e95b16Srtm struct run *freelist; 2555e95b16Srtm 2655e95b16Srtm void ktest(); 2755e95b16Srtm 2855e95b16Srtm /* 2955e95b16Srtm * initialize free list of physical pages. this code 3055e95b16Srtm * cheats by just considering the one megabyte of pages 3155e95b16Srtm * after _end. 3255e95b16Srtm */ 3355e95b16Srtm void 3455e95b16Srtm kinit() 3555e95b16Srtm { 3655e95b16Srtm extern int end; 3755e95b16Srtm unsigned mem; 3855e95b16Srtm char *start; 3955e95b16Srtm 4055e95b16Srtm start = (char *) &end; 4155e95b16Srtm start = (char *) (((unsigned)start + PAGE) & ~(PAGE-1)); 4255e95b16Srtm mem = 256; // XXX 4355e95b16Srtm cprintf("mem = %d\n", mem * PAGE); 4455e95b16Srtm kfree(start, mem * PAGE); 4555e95b16Srtm ktest(); 4655e95b16Srtm } 4755e95b16Srtm 4855e95b16Srtm void 4955e95b16Srtm kfree(char *cp, int len) 5055e95b16Srtm { 5155e95b16Srtm struct run **rr; 5255e95b16Srtm struct run *p = (struct run *) cp; 5355e95b16Srtm struct run *pend = (struct run *) (cp + len); 548b4e2a08Srtm int i; 5555e95b16Srtm 5655e95b16Srtm if(len % PAGE) 5755e95b16Srtm panic("kfree"); 5855e95b16Srtm 598b4e2a08Srtm // XXX fill with junk to help debug 608b4e2a08Srtm for(i = 0; i < len; i++) 618b4e2a08Srtm cp[i] = 1; 628b4e2a08Srtm 634e8f237bSrtm acquire(&kalloc_lock); 644e8f237bSrtm 6555e95b16Srtm rr = &freelist; 6655e95b16Srtm while(*rr){ 6755e95b16Srtm struct run *rend = (struct run *) ((char *)(*rr) + (*rr)->len); 6855e95b16Srtm if(p >= *rr && p < rend) 6955e95b16Srtm panic("freeing free page"); 7055e95b16Srtm if(pend == *rr){ 7155e95b16Srtm p->len = len + (*rr)->len; 7255e95b16Srtm p->next = (*rr)->next; 7355e95b16Srtm *rr = p; 744e8f237bSrtm goto out; 7555e95b16Srtm } 7655e95b16Srtm if(pend < *rr){ 7755e95b16Srtm p->len = len; 7855e95b16Srtm p->next = *rr; 7955e95b16Srtm *rr = p; 804e8f237bSrtm goto out; 8155e95b16Srtm } 8255e95b16Srtm if(p == rend){ 8355e95b16Srtm (*rr)->len += len; 8455e95b16Srtm if((*rr)->next && (*rr)->next == pend){ 8555e95b16Srtm (*rr)->len += (*rr)->next->len; 8655e95b16Srtm (*rr)->next = (*rr)->next->next; 8755e95b16Srtm } 884e8f237bSrtm goto out; 8955e95b16Srtm } 9055e95b16Srtm rr = &((*rr)->next); 9155e95b16Srtm } 9255e95b16Srtm p->len = len; 9355e95b16Srtm p->next = 0; 9455e95b16Srtm *rr = p; 954e8f237bSrtm 964e8f237bSrtm out: 974e8f237bSrtm release(&kalloc_lock); 9855e95b16Srtm } 9955e95b16Srtm 10055e95b16Srtm /* 10155e95b16Srtm * allocate n bytes of physical memory. 10255e95b16Srtm * returns a kernel-segment pointer. 10355e95b16Srtm * returns 0 if there's no run that's big enough. 10455e95b16Srtm */ 10555e95b16Srtm char * 10655e95b16Srtm kalloc(int n) 10755e95b16Srtm { 10855e95b16Srtm struct run **rr; 10955e95b16Srtm 11055e95b16Srtm if(n % PAGE) 11155e95b16Srtm panic("kalloc"); 11255e95b16Srtm 1134e8f237bSrtm acquire(&kalloc_lock); 1144e8f237bSrtm 11555e95b16Srtm rr = &freelist; 11655e95b16Srtm while(*rr){ 11755e95b16Srtm struct run *r = *rr; 11855e95b16Srtm if(r->len == n){ 11955e95b16Srtm *rr = r->next; 1204e8f237bSrtm release(&kalloc_lock); 12155e95b16Srtm return (char *) r; 12255e95b16Srtm } 12355e95b16Srtm if(r->len > n){ 12455e95b16Srtm char *p = (char *)r + (r->len - n); 12555e95b16Srtm r->len -= n; 1264e8f237bSrtm release(&kalloc_lock); 12755e95b16Srtm return p; 12855e95b16Srtm } 12955e95b16Srtm rr = &(*rr)->next; 13055e95b16Srtm } 1314e8f237bSrtm release(&kalloc_lock); 13255e95b16Srtm return 0; 13355e95b16Srtm } 13455e95b16Srtm 13555e95b16Srtm void 13655e95b16Srtm ktest() 13755e95b16Srtm { 13855e95b16Srtm char *p1, *p2, *p3; 13955e95b16Srtm 14055e95b16Srtm // test coalescing 14155e95b16Srtm p1 = kalloc(4 * PAGE); 14255e95b16Srtm kfree(p1 + 3*PAGE, PAGE); 14355e95b16Srtm kfree(p1 + 2*PAGE, PAGE); 14455e95b16Srtm kfree(p1, PAGE); 14555e95b16Srtm kfree(p1 + PAGE, PAGE); 14655e95b16Srtm p2 = kalloc(4 * PAGE); 14755e95b16Srtm if(p2 != p1) 14855e95b16Srtm panic("ktest"); 14955e95b16Srtm kfree(p2, 4 * PAGE); 15055e95b16Srtm 15155e95b16Srtm // test finding first run that fits 15255e95b16Srtm p1 = kalloc(1 * PAGE); 15355e95b16Srtm p2 = kalloc(1 * PAGE); 15455e95b16Srtm kfree(p1, PAGE); 15555e95b16Srtm p3 = kalloc(2 * PAGE); 15655e95b16Srtm kfree(p2, PAGE); 15755e95b16Srtm kfree(p3, 2 * PAGE); 15855e95b16Srtm 15955e95b16Srtm // test running out of memory 16055e95b16Srtm p1 = 0; 16155e95b16Srtm while(1){ 16255e95b16Srtm p2 = kalloc(PAGE); 16355e95b16Srtm if(p2 == 0) 16455e95b16Srtm break; 16555e95b16Srtm *(char **)p2 = p1; 16655e95b16Srtm p1 = p2; 16755e95b16Srtm } 16855e95b16Srtm while(p1){ 16955e95b16Srtm p2 = *(char **)p1; 17055e95b16Srtm kfree(p1, PAGE); 17155e95b16Srtm p1 = p2; 17255e95b16Srtm } 17355e95b16Srtm p1 = kalloc(PAGE * 20); 17455e95b16Srtm if(p1 == 0) 17555e95b16Srtm panic("ktest2"); 17655e95b16Srtm kfree(p1, PAGE * 20); 17755e95b16Srtm } 178