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