lib/libc/ansi/malloc.c

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