umalloc.c

   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 }