umalloc.c (1652B)
1 #include "types.h" 2 #include "stat.h" 3 #include "user.h" 4 #include "param.h" 5 6 // Memory allocator by Kernighan and Ritchie, 7 // The C programming Language, 2nd ed. Section 8.7. 8 9 typedef long Align; 10 11 union header { 12 struct { 13 union header *ptr; 14 uint size; 15 } s; 16 Align x; 17 }; 18 19 typedef union header Header; 20 21 static Header base; 22 static Header *freep; 23 24 void 25 free(void *ap) 26 { 27 Header *bp, *p; 28 29 bp = (Header*)ap - 1; 30 for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr) 31 if(p >= p->s.ptr && (bp > p || bp < p->s.ptr)) 32 break; 33 if(bp + bp->s.size == p->s.ptr){ 34 bp->s.size += p->s.ptr->s.size; 35 bp->s.ptr = p->s.ptr->s.ptr; 36 } else 37 bp->s.ptr = p->s.ptr; 38 if(p + p->s.size == bp){ 39 p->s.size += bp->s.size; 40 p->s.ptr = bp->s.ptr; 41 } else 42 p->s.ptr = bp; 43 freep = p; 44 } 45 46 static Header* 47 morecore(uint nu) 48 { 49 char *p; 50 Header *hp; 51 52 if(nu < 4096) 53 nu = 4096; 54 p = sbrk(nu * sizeof(Header)); 55 if(p == (char*)-1) 56 return 0; 57 hp = (Header*)p; 58 hp->s.size = nu; 59 free((void*)(hp + 1)); 60 return freep; 61 } 62 63 void* 64 malloc(uint nbytes) 65 { 66 Header *p, *prevp; 67 uint nunits; 68 69 nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1; 70 if((prevp = freep) == 0){ 71 base.s.ptr = freep = prevp = &base; 72 base.s.size = 0; 73 } 74 for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){ 75 if(p->s.size >= nunits){ 76 if(p->s.size == nunits) 77 prevp->s.ptr = p->s.ptr; 78 else { 79 p->s.size -= nunits; 80 p += p->s.size; 81 p->s.size = nunits; 82 } 83 freep = prevp; 84 return (void*)(p + 1); 85 } 86 if(p == freep) 87 if((p = morecore(nunits)) == 0) 88 return 0; 89 } 90 }