xv6

port of xv6 to x86-64
git clone http://frotz.net/git/xv6.git
Log | Files | Refs | README | LICENSE

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 }