src/xbt/mmalloc/mmalloc.c

   1 /* Memory allocator `malloc'.
   2    Copyright 1990, 1991, 1992 Free Software Foundation
   3
   4    Written May 1989 by Mike Haertel.
   5    Heavily modified Mar 1992 by Fred Fish for mmap'd version.
   6
   7 The GNU C Library is free software; you can redistribute it and/or
   8 modify it under the terms of the GNU Library General Public License as
   9 published by the Free Software Foundation; either version 2 of the
  10 License, or (at your option) any later version.
  11
  12 The GNU C Library is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 Library General Public License for more details.
  16
  17 You should have received a copy of the GNU Library General Public
  18 License along with the GNU C Library; see the file COPYING.LIB.  If
  19 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.
  21
  22    The author may be reached (Email) at the address mike@ai.mit.edu,
  23    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  24
  25 #include <string.h>     /* Prototypes for memcpy, memmove, memset, etc */
  26 #include <stdio.h>
  27 #include "mmprivate.h"
  28
  29 /* Prototypes for local functions */
  30
  31 static int initialize (struct mdesc *mdp);
  32 static void* morecore (struct mdesc *mdp, size_t size);
  33 static void* align (struct mdesc *mdp, size_t size);
  34
  35 /* Aligned allocation.  */
  36
  37 static void*
  38 align (struct mdesc *mdp, size_t size)
  39 {
  40   void* result;
  41   unsigned long int adj;
  42
  43   result = mdp -> morecore (mdp, size);
  44   adj = RESIDUAL (result, BLOCKSIZE);
  45   if (adj != 0)
  46     {
  47       adj = BLOCKSIZE - adj;
  48       mdp -> morecore (mdp, adj);
  49       result = (char*) result + adj;
  50     }
  51   return (result);
  52 }
  53
  54 /* Set everything up and remember that we have.  */
  55
  56 static int
  57 initialize (struct mdesc *mdp)
  58 {
  59   mdp -> heapsize = HEAP / BLOCKSIZE;
  60   mdp -> heapinfo = (malloc_info *)
  61     align (mdp, mdp -> heapsize * sizeof (malloc_info));
  62   if (mdp -> heapinfo == NULL)
  63     {
  64       return (0);
  65     }
  66   memset ((void*)mdp -> heapinfo, 0, mdp -> heapsize * sizeof (malloc_info));
  67   mdp -> heapinfo[0].free.size = 0;
  68   mdp -> heapinfo[0].free.next = mdp -> heapinfo[0].free.prev = 0;
  69   mdp -> heapindex = 0;
  70   mdp -> heapbase = (void*) mdp -> heapinfo;
  71   mdp -> flags |= MMALLOC_INITIALIZED;
  72   return (1);
  73 }
  74
  75 /* Get neatly aligned memory, initializing or
  76    growing the heap info table as necessary. */
  77
  78 static void*
  79 morecore (struct mdesc *mdp, size_t size)
  80 {
  81   void* result;
  82   malloc_info *newinfo, *oldinfo;
  83   size_t newsize;
  84
  85   result = align (mdp, size);
  86   if (result == NULL)
  87     {
  88       return (NULL);
  89     }
  90
  91   /* Check if we need to grow the info table.  */
  92   if ((size_t) BLOCK ((char*) result + size) > mdp -> heapsize)
  93     {
  94       newsize = mdp -> heapsize;
  95       while ((size_t) BLOCK ((char*) result + size) > newsize)
  96         {
  97           newsize *= 2;
  98         }
  99       newinfo = (malloc_info *) align (mdp, newsize * sizeof (malloc_info));
 100       if (newinfo == NULL)
 101         {
 102           mdp -> morecore (mdp, -size);
 103           return (NULL);
 104         }
 105       memset ((void*) newinfo, 0, newsize * sizeof (malloc_info));
 106       memcpy ((void*) newinfo, (void*) mdp -> heapinfo,
 107               mdp -> heapsize * sizeof (malloc_info));
 108       oldinfo = mdp -> heapinfo;
 109       newinfo[BLOCK (oldinfo)].busy.type = 0;
 110       newinfo[BLOCK (oldinfo)].busy.info.size
 111         = BLOCKIFY (mdp -> heapsize * sizeof (malloc_info));
 112       mdp -> heapinfo = newinfo;
 113       __mmalloc_free (mdp, (void*)oldinfo);
 114       mdp -> heapsize = newsize;
 115     }
 116
 117   mdp -> heaplimit = BLOCK ((char*) result + size);
 118   return (result);
 119 }
 120
 121 /* Allocate memory from the heap.  */
 122
 123 void*
 124 mmalloc (md, size)
 125   void* md;
 126   size_t size;
 127 {
 128   struct mdesc *mdp;
 129   void* result;
 130   size_t block, blocks, lastblocks, start;
 131   register size_t i;
 132   struct list *next;
 133   register size_t log;
 134
 135   if (size == 0)
 136     {
 137       return (NULL);
 138     }
 139
 140   mdp = MD_TO_MDP (md);
 141
 142   if (mdp -> mmalloc_hook != NULL)
 143     {
 144       return ((*mdp -> mmalloc_hook) (md, size));
 145     }
 146
 147   if (!(mdp -> flags & MMALLOC_INITIALIZED))
 148     {
 149       if (!initialize (mdp))
 150         {
 151           return (NULL);
 152         }
 153     }
 154
 155   if (size < sizeof (struct list))
 156     {
 157       size = sizeof (struct list);
 158     }
 159
 160   /* Determine the allocation policy based on the request size.  */
 161   if (size <= BLOCKSIZE / 2)
 162     {
 163       /* Small allocation to receive a fragment of a block.
 164          Determine the logarithm to base two of the fragment size. */
 165       log = 1;
 166       --size;
 167       while ((size /= 2) != 0)
 168         {
 169           ++log;
 170         }
 171
 172       /* Look in the fragment lists for a
 173          free fragment of the desired size. */
 174       next = mdp -> fraghead[log].next;
 175       if (next != NULL)
 176         {
 177           /* There are free fragments of this size.
 178              Pop a fragment out of the fragment list and return it.
 179              Update the block's nfree and first counters. */
 180           result = (void*) next;
 181           next -> prev -> next = next -> next;
 182           if (next -> next != NULL)
 183             {
 184               next -> next -> prev = next -> prev;
 185             }
 186           block = BLOCK (result);
 187           if (--mdp -> heapinfo[block].busy.info.frag.nfree != 0)
 188             {
 189               mdp -> heapinfo[block].busy.info.frag.first =
 190                 RESIDUAL (next -> next, BLOCKSIZE) >> log;
 191             }
 192
 193           /* Update the statistics.  */
 194           mdp -> heapstats.chunks_used++;
 195           mdp -> heapstats.bytes_used += 1 << log;
 196           mdp -> heapstats.chunks_free--;
 197           mdp -> heapstats.bytes_free -= 1 << log;
 198         }
 199       else
 200         {
 201           /* No free fragments of the desired size, so get a new block
 202              and break it into fragments, returning the first.  */
 203           result = mmalloc (md, BLOCKSIZE);
 204           if (result == NULL)
 205             {
 206               return (NULL);
 207             }
 208
 209           /* Link all fragments but the first into the free list.  */
 210           for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i)
 211             {
 212               next = (struct list *) ((char*) result + (i << log));
 213               next -> next = mdp -> fraghead[log].next;
 214               next -> prev = &mdp -> fraghead[log];
 215               next -> prev -> next = next;
 216               if (next -> next != NULL)
 217                 {
 218                   next -> next -> prev = next;
 219                 }
 220             }
 221
 222           /* Initialize the nfree and first counters for this block.  */
 223           block = BLOCK (result);
 224           mdp -> heapinfo[block].busy.type = log;
 225           mdp -> heapinfo[block].busy.info.frag.nfree = i - 1;
 226           mdp -> heapinfo[block].busy.info.frag.first = i - 1;
 227
 228           mdp -> heapstats.chunks_free += (BLOCKSIZE >> log) - 1;
 229           mdp -> heapstats.bytes_free += BLOCKSIZE - (1 << log);
 230           mdp -> heapstats.bytes_used -= BLOCKSIZE - (1 << log);
 231         }
 232     }
 233   else
 234     {
 235       /* Large allocation to receive one or more blocks.
 236          Search the free list in a circle starting at the last place visited.
 237          If we loop completely around without finding a large enough
 238          space we will have to get more memory from the system.  */
 239       blocks = BLOCKIFY(size);
 240       start = block = MALLOC_SEARCH_START;
 241       while (mdp -> heapinfo[block].free.size < blocks)
 242         {
 243           block = mdp -> heapinfo[block].free.next;
 244           if (block == start)
 245             {
 246               /* Need to get more from the system.  Check to see if
 247                  the new core will be contiguous with the final free
 248                  block; if so we don't need to get as much.  */
 249               block = mdp -> heapinfo[0].free.prev;
 250               lastblocks = mdp -> heapinfo[block].free.size;
 251               if (mdp -> heaplimit != 0 &&
 252                   block + lastblocks == mdp -> heaplimit &&
 253                   mdp -> morecore (mdp, 0) == ADDRESS(block + lastblocks) &&
 254                   (morecore (mdp, (blocks - lastblocks) * BLOCKSIZE)) != NULL)
 255                 {
 256                   /* Which block we are extending (the `final free
 257                      block' referred to above) might have changed, if
 258                      it got combined with a freed info table.  */
 259                   block = mdp -> heapinfo[0].free.prev;
 260
 261                   mdp -> heapinfo[block].free.size += (blocks - lastblocks);
 262                   mdp -> heapstats.bytes_free +=
 263                       (blocks - lastblocks) * BLOCKSIZE;
 264                   continue;
 265                 }
 266               result = morecore(mdp, blocks * BLOCKSIZE);
 267               if (result == NULL)
 268                 {
 269                   return (NULL);
 270                 }
 271               block = BLOCK (result);
 272               mdp -> heapinfo[block].busy.type = 0;
 273               mdp -> heapinfo[block].busy.info.size = blocks;
 274               mdp -> heapstats.chunks_used++;
 275               mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
 276               return (result);
 277             }
 278         }
 279
 280       /* At this point we have found a suitable free list entry.
 281          Figure out how to remove what we need from the list. */
 282       result = ADDRESS(block);
 283       if (mdp -> heapinfo[block].free.size > blocks)
 284         {
 285           /* The block we found has a bit left over,
 286              so relink the tail end back into the free list. */
 287           mdp -> heapinfo[block + blocks].free.size
 288             = mdp -> heapinfo[block].free.size - blocks;
 289           mdp -> heapinfo[block + blocks].free.next
 290             = mdp -> heapinfo[block].free.next;
 291           mdp -> heapinfo[block + blocks].free.prev
 292             = mdp -> heapinfo[block].free.prev;
 293           mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
 294             = mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
 295               = mdp -> heapindex = block + blocks;
 296         }
 297       else
 298         {
 299           /* The block exactly matches our requirements,
 300              so just remove it from the list. */
 301           mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
 302             = mdp -> heapinfo[block].free.prev;
 303           mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
 304             = mdp -> heapindex = mdp -> heapinfo[block].free.next;
 305           mdp -> heapstats.chunks_free--;
 306         }
 307
 308       mdp -> heapinfo[block].busy.type = 0;
 309       mdp -> heapinfo[block].busy.info.size = blocks;
 310       mdp -> heapstats.chunks_used++;
 311       mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
 312       mdp -> heapstats.bytes_free -= blocks * BLOCKSIZE;
 313     }
 314
 315   return (result);
 316 }
 317
 318 /* When using this package, provide a version of malloc/realloc/free built
 319    on top of it, so that if we use the default sbrk() region we will not
 320    collide with another malloc package trying to do the same thing, if
 321    the application contains any "hidden" calls to malloc/realloc/free (such
 322    as inside a system library). */
 323
 324 void*
 325 malloc (size_t size)
 326 {
 327   void* result;
 328   result = mmalloc (NULL, size);
 329   return (result);
 330 }