lib/sysutil/kmalloc.c

   1 /*      malloc(), realloc(), free() - simple memory allocation routines
   2  *
   3  * This is a very small and simple minded malloc        Author: Kees J. Bot
   4  * implementation.  Ideal for things like a                     29 Jan 1994
   5  * bootstrap program, or for debugging.  Six times
   6  * slower than any good malloc.
   7  */
   8 #define nil 0
   9
  10 #define sbrk _sbrk
  11 #include <stddef.h>
  12 #include <stdlib.h>
  13 #include <unistd.h>
  14 #include <string.h>
  15 #include <limits.h>
  16 #if !DEBUG
  17 #define NDEBUG  1
  18 #define debug(expr)     ((void) 0)
  19 #else
  20 #define debug(expr)     expr
  21 #endif
  22 #include <assert.h>
  23
  24 typedef struct cell {
  25         size_t          size;           /* Size of a malloc()'ed object. */
  26 #if DEBUG
  27         unsigned        magic;          /* To recognize a cell. */
  28 #endif
  29         struct cell     *next;          /* Next cell on the free list. */
  30 #if DEBUG
  31         unsigned        sacred;         /* Don't touch while unallocated. */
  32 #endif
  33 } cell_t;
  34
  35 #if UINT_MAX <= 0xFFFF
  36 #define MAGIC   0x537B
  37 #else
  38 #define MAGIC   0x537BC0D8
  39 #endif
  40
  41 /* Size of the header of an object. */
  42 #define HDR_SIZE        offsetof(cell_t, next)
  43
  44 /* An offset from a cell pointer to a next cell. */
  45 #define offset(cp, size)        ((cell_t *) ((char *) (cp) + (size)))
  46
  47 /* Address of the object in a cell and back. */
  48 #define cell2obj(cp)            ((void *) ((char *) (cp) + HDR_SIZE))
  49 #define obj2cell(op)            ((cell_t *) ((char *) (op) - HDR_SIZE))
  50
  51 /* The free list. */
  52 static cell_t *freelist;
  53
  54 void *malloc(size_t size)
  55 /* Allocate an object of at least the given size. */
  56 {
  57         cell_t **pcp, *cp;
  58
  59         size += HDR_SIZE;
  60         if (size < sizeof(cell_t)) size= sizeof(cell_t);
  61
  62         /* Align to a word.  Use a real malloc if you need better alignment. */
  63         size= (size + sizeof(int) - 1) & ~(sizeof(int) - 1);
  64
  65         /* Space for a magic number at the end of the chunk. */
  66         debug(size += sizeof(unsigned));
  67
  68         for (;;) {
  69                 /* Do a first fit search. */
  70                 pcp= &freelist;
  71                 while ((cp= *pcp) != nil) {
  72                         cell_t *next= cp->next;
  73
  74                         assert(cp->magic == MAGIC);
  75                         assert(cp->sacred == MAGIC);
  76
  77                         if (offset(cp, cp->size) == next) {
  78                                 /* Join adjacent free cells. */
  79                                 assert(next->magic == MAGIC);
  80                                 assert(next->sacred == MAGIC);
  81
  82                                 cp->size+= next->size;
  83                                 cp->next= next->next;
  84
  85                                 continue;               /* Try again. */
  86                         }
  87                         if (size <= cp->size) break;    /* Big enough. */
  88
  89                         /* Next cell. */
  90                         pcp= &cp->next;
  91                 }
  92
  93                 if (cp != nil) break;   /* Found a big enough chunk. */
  94
  95                 /* Allocate a new chunk at the break. */
  96                 if ((cp= (cell_t *) sbrk(size)) == (cell_t *) -1) {
  97                         return nil;
  98                 }
  99
 100                 cp->size= size;
 101                 cp->next= nil;
 102                 debug(cp->magic= MAGIC);
 103                 debug(cp->sacred= MAGIC);
 104                 *pcp= cp;
 105         }
 106
 107         /* We've got a cell that is big enough.  Can we break it up? */
 108         if (cp->size >= size + sizeof(cell_t)) {
 109                 cell_t *next= offset(cp, size);
 110
 111                 next->size= cp->size - size;
 112                 next->next= cp->next;
 113                 debug(next->magic= MAGIC);
 114                 debug(next->sacred= MAGIC);
 115                 cp->size= size;
 116                 cp->next= next;
 117         }
 118
 119         /* Unchain the cell we've found and return an address in it. */
 120         *pcp= cp->next;
 121         debug(memset(cell2obj(cp), 0xAA, cp->size - HDR_SIZE));
 122         debug(((unsigned *) offset(cp, cp->size))[-1]= MAGIC);
 123
 124         return cell2obj(cp);
 125 }
 126
 127 void free(void *op)
 128 /* Deallocate an object. */
 129 {
 130         cell_t **prev, *next, *cp;
 131
 132         if (op == nil) return;          /* Aaargh. */
 133
 134         cp= obj2cell(op);
 135         assert(cp->magic == MAGIC);
 136         assert(((unsigned *) offset(cp, cp->size))[-1] == MAGIC);
 137         debug(cp->sacred= MAGIC);
 138
 139         /* Find the spot where the object belongs. */
 140         prev= &freelist;
 141         while ((next= *prev) != nil && next < cp) {
 142                 assert(next->magic == MAGIC);
 143                 assert(next->sacred == MAGIC);
 144                 prev= &next->next;
 145         }
 146
 147         /* Put the new free cell in the list. */
 148         *prev= cp;
 149         cp->next= next;
 150
 151 #if DEBUG
 152         /* Check the rest of the list. */
 153         while (next != nil) {
 154                 assert(next->magic == MAGIC);
 155                 assert(next->sacred == MAGIC);
 156                 next= next->next;
 157         }
 158 #endif
 159 }
 160
 161 void *realloc(void *op, size_t size)
 162 /* Change the size of an object.  Don't bother being smart, just copy it. */
 163 {
 164         size_t oldsize;
 165         void *new;
 166
 167         oldsize= op == nil ? 0 : obj2cell(op)->size - HDR_SIZE;
 168
 169         new= malloc(size);
 170         memcpy(new, op, oldsize > size ? size : oldsize);
 171         free(op);
 172         return new;
 173 }
 174
 175 /*
 176  * $PchId: malloc.c,v 1.4 1996/02/22 09:15:56 philip Exp $
 177  */