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