lib/libc/ansi/malloc.c

   1 /* $Header$ */
   2
   3 /* replace undef by define */
   4 #define  DEBUG          /* check assertions */
   5 #define  SLOWDEBUG      /* some extra test loops (requires DEBUG) */
   6
   7 #ifndef DEBUG
   8 #define NDEBUG
   9 #endif
  10
  11 #include        <stdlib.h>
  12 #include        <string.h>
  13 #include        <errno.h>
  14 #include        <assert.h>
  15
  16 #if _EM_WSIZE == _EM_PSIZE
  17 #define ptrint          int
  18 #else
  19 #define ptrint          long
  20 #endif
  21
  22 #if     _EM_PSIZE == 2
  23 #define BRKSIZE         1024
  24 #else
  25 #define BRKSIZE         4096
  26 #endif
  27 #define PTRSIZE         ((int) sizeof(void *))
  28 #define Align(x,a)      (((x) + (a - 1)) & ~(a - 1))
  29 #define NextSlot(p)     (* (void **) ((p) - PTRSIZE))
  30 #define NextFree(p)     (* (void **) (p))
  31
  32 /*
  33  * A short explanation of the data structure and algorithms.
  34  * An area returned by malloc() is called a slot. Each slot
  35  * contains the number of bytes requested, but preceeded by
  36  * an extra pointer to the next the slot in memory.
  37  * '_bottom' and '_top' point to the first/last slot.
  38  * More memory is asked for using brk() and appended to top.
  39  * The list of free slots is maintained to keep malloc() fast.
  40  * '_empty' points the the first free slot. Free slots are
  41  * linked together by a pointer at the start of the
  42  * user visable part, so just after the next-slot pointer.
  43  * Free slots are merged together by free().
  44  */
  45
  46 extern void *_sbrk(int);
  47 extern int _brk(void *);
  48 static void *_bottom, *_top, *_empty;
  49
  50 static int grow(size_t len)
  51 {
  52   register char *p;
  53
  54   assert(NextSlot((char *)_top) == 0);
  55   if ((char *) _top + len < (char *) _top
  56       || (p = (char *)Align((ptrint)_top + len, BRKSIZE)) < (char *) _top ) {
  57         errno = ENOMEM;
  58         return(0);
  59   }
  60   if (_brk(p) != 0)
  61         return(0);
  62   NextSlot((char *)_top) = p;
  63   NextSlot(p) = 0;
  64   free(_top);
  65   _top = p;
  66   return 1;
  67 }
  68
  69 void *
  70 malloc(size_t size)
  71 {
  72   register char *prev, *p, *next, *new;
  73   register unsigned len, ntries;
  74
  75   if (size == 0)
  76         return NULL;
  77
  78   for (ntries = 0; ntries < 2; ntries++) {
  79         if ((len = Align(size, PTRSIZE) + PTRSIZE) < 2 * PTRSIZE) {
  80                 errno = ENOMEM;
  81                 return NULL;
  82         }
  83         if (_bottom == 0) {
  84                 if ((p = _sbrk(2 * PTRSIZE)) == (char *) -1)
  85                         return NULL;
  86                 p = (char *) Align((ptrint)p, PTRSIZE);
  87                 p += PTRSIZE;
  88                 _top = _bottom = p;
  89                 NextSlot(p) = 0;
  90         }
  91 #ifdef SLOWDEBUG
  92         for (p = _bottom; (next = NextSlot(p)) != 0; p = next)
  93                 assert(next > p);
  94         assert(p == _top);
  95 #endif
  96         for (prev = 0, p = _empty; p != 0; prev = p, p = NextFree(p)) {
  97                 next = NextSlot(p);
  98                 new = p + len;  /* easily overflows!! */
  99                 if (new > next || new <= p)
 100                         continue;               /* too small */
 101                 if (new + PTRSIZE < next) {     /* too big, so split */
 102                         /* + PTRSIZE avoids tiny slots on free list */
 103                         NextSlot(new) = next;
 104                         NextSlot(p) = new;
 105                         NextFree(new) = NextFree(p);
 106                         NextFree(p) = new;
 107                 }
 108                 if (prev)
 109                         NextFree(prev) = NextFree(p);
 110                 else
 111                         _empty = NextFree(p);
 112                 return p;
 113         }
 114         if (grow(len) == 0)
 115                 break;
 116   }
 117   assert(ntries != 2);
 118   return NULL;
 119 }
 120
 121 void *
 122 realloc(void *oldp, size_t size)
 123 {
 124   register char *prev, *p, *next, *new;
 125   char *old = oldp;
 126   register size_t len, n;
 127
 128   if (old == 0)
 129         return malloc(size);
 130   if (size == 0) {
 131         free(old);
 132         return NULL;
 133   }
 134   len = Align(size, PTRSIZE) + PTRSIZE;
 135   next = NextSlot(old);
 136   n = (int)(next - old);                        /* old length */
 137   /*
 138    * extend old if there is any free space just behind it
 139    */
 140   for (prev = 0, p = _empty; p != 0; prev = p, p = NextFree(p)) {
 141         if (p > next)
 142                 break;
 143         if (p == next) {        /* 'next' is a free slot: merge */
 144                 NextSlot(old) = NextSlot(p);
 145                 if (prev)
 146                         NextFree(prev) = NextFree(p);
 147                 else
 148                         _empty = NextFree(p);
 149                 next = NextSlot(old);
 150                 break;
 151         }
 152   }
 153   new = old + len;
 154   /*
 155    * Can we use the old, possibly extended slot?
 156    */
 157   if (new <= next && new >= old) {              /* it does fit */
 158         if (new + PTRSIZE < next) {             /* too big, so split */
 159                 /* + PTRSIZE avoids tiny slots on free list */
 160                 NextSlot(new) = next;
 161                 NextSlot(old) = new;
 162                 free(new);
 163         }
 164         return old;
 165   }
 166   if ((new = malloc(size)) == NULL)             /* it didn't fit */
 167         return NULL;
 168   memcpy(new, old, n);                          /* n < size */
 169   free(old);
 170   return new;
 171 }
 172
 173 void
 174 free(void *ptr)
 175 {
 176   register char *prev, *next;
 177   char *p = ptr;
 178
 179   if (p == 0)
 180         return;
 181
 182 #ifdef SLOWDEBUG
 183   {
 184         int found;
 185         char *curr;
 186
 187         /* block must be in block list */
 188         assert(_bottom);
 189         found = 0;
 190         for (curr = _bottom; (next = NextSlot(curr)) != 0; curr = next) {
 191                 assert(next > curr);
 192                 if (curr == p) found = 1;
 193         }
 194         if (curr == p) found = 1;
 195         assert(found);
 196
 197         /* block must not be in free list */
 198         if (_empty) {
 199                 found = 0;
 200                 for (curr = _empty; (next = NextFree(curr)) != 0; curr = next) {
 201                         assert(next > curr);
 202                         if (curr == p) found = 1;
 203                 }
 204                 if (curr == p) found = 1;
 205                 assert(!found);
 206         }
 207   }
 208 #endif
 209
 210   assert((char *) NextSlot(p) > p);
 211   for (prev = 0, next = _empty; next != 0; prev = next, next = NextFree(next))
 212         if (p < next)
 213                 break;
 214   NextFree(p) = next;
 215   if (prev)
 216         NextFree(prev) = p;
 217   else
 218         _empty = p;
 219   if (next) {
 220         assert((char *) NextSlot(p) <= next);
 221         if (NextSlot(p) == next) {              /* merge p and next */
 222                 NextSlot(p) = NextSlot(next);
 223                 NextFree(p) = NextFree(next);
 224         }
 225   }
 226   if (prev) {
 227         assert((char *) NextSlot(prev) <= p);
 228         if (NextSlot(prev) == p) {              /* merge prev and p */
 229                 NextSlot(prev) = NextSlot(p);
 230                 NextFree(prev) = NextFree(p);
 231         }
 232   }
 233 }