lib/malloclib/malloc.c

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