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