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 (void *md, size_t size)
 113 {
 114   struct mdesc *mdp;
 115   void* result;
 116   size_t block, blocks, lastblocks, start;
 117   register size_t i;
 118   struct list *next;
 119   register size_t log;
 120
 121   if (size == 0)
 122     {
 123       return (NULL);
 124     }
 125
 126   mdp = MD_TO_MDP (md);
 127
 128   if (mdp -> mmalloc_hook != NULL)
 129     {
 130       return ((*mdp -> mmalloc_hook) (md, size));
 131     }
 132
 133   if (!(mdp -> flags & MMALLOC_INITIALIZED))
 134     {
 135       if (!initialize (mdp))
 136         {
 137           return (NULL);
 138         }
 139     }
 140
 141   if (size < sizeof (struct list))
 142     {
 143       size = sizeof (struct list);
 144     }
 145
 146   /* Determine the allocation policy based on the request size.  */
 147   if (size <= BLOCKSIZE / 2)
 148     {
 149       /* Small allocation to receive a fragment of a block.
 150          Determine the logarithm to base two of the fragment size. */
 151       log = 1;
 152       --size;
 153       while ((size /= 2) != 0)
 154         {
 155           ++log;
 156         }
 157
 158       /* Look in the fragment lists for a
 159          free fragment of the desired size. */
 160       next = mdp -> fraghead[log].next;
 161       if (next != NULL)
 162         {
 163           /* There are free fragments of this size.
 164              Pop a fragment out of the fragment list and return it.
 165              Update the block's nfree and first counters. */
 166           result = (void*) next;
 167           next -> prev -> next = next -> next;
 168           if (next -> next != NULL)
 169             {
 170               next -> next -> prev = next -> prev;
 171             }
 172           block = BLOCK (result);
 173           if (--mdp -> heapinfo[block].busy.info.frag.nfree != 0)
 174             {
 175               mdp -> heapinfo[block].busy.info.frag.first =
 176                 RESIDUAL (next -> next, BLOCKSIZE) >> log;
 177             }
 178
 179           /* Update the statistics.  */
 180           mdp -> heapstats.chunks_used++;
 181           mdp -> heapstats.bytes_used += 1 << log;
 182           mdp -> heapstats.chunks_free--;
 183           mdp -> heapstats.bytes_free -= 1 << log;
 184         }
 185       else
 186         {
 187           /* No free fragments of the desired size, so get a new block
 188              and break it into fragments, returning the first.  */
 189           result = mmalloc (md, BLOCKSIZE);
 190           if (result == NULL)
 191             {
 192               return (NULL);
 193             }
 194
 195           /* Link all fragments but the first into the free list.  */
 196           for (i = 1; i < (size_t) (BLOCKSIZE >> log); ++i)
 197             {
 198               next = (struct list *) ((char*) result + (i << log));
 199               next -> next = mdp -> fraghead[log].next;
 200               next -> prev = &mdp -> fraghead[log];
 201               next -> prev -> next = next;
 202               if (next -> next != NULL)
 203                 {
 204                   next -> next -> prev = next;
 205                 }
 206             }
 207
 208           /* Initialize the nfree and first counters for this block.  */
 209           block = BLOCK (result);
 210           mdp -> heapinfo[block].busy.type = log;
 211           mdp -> heapinfo[block].busy.info.frag.nfree = i - 1;
 212           mdp -> heapinfo[block].busy.info.frag.first = i - 1;
 213
 214           mdp -> heapstats.chunks_free += (BLOCKSIZE >> log) - 1;
 215           mdp -> heapstats.bytes_free += BLOCKSIZE - (1 << log);
 216           mdp -> heapstats.bytes_used -= BLOCKSIZE - (1 << log);
 217         }
 218     }
 219   else
 220     {
 221       /* Large allocation to receive one or more blocks.
 222          Search the free list in a circle starting at the last place visited.
 223          If we loop completely around without finding a large enough
 224          space we will have to get more memory from the system.  */
 225       blocks = BLOCKIFY(size);
 226       start = block = MALLOC_SEARCH_START;
 227       while (mdp -> heapinfo[block].free.size < blocks)
 228         {
 229           block = mdp -> heapinfo[block].free.next;
 230           if (block == start)
 231             {
 232               /* Need to get more from the system.  Check to see if
 233                  the new core will be contiguous with the final free
 234                  block; if so we don't need to get as much.  */
 235               block = mdp -> heapinfo[0].free.prev;
 236               lastblocks = mdp -> heapinfo[block].free.size;
 237               if (mdp -> heaplimit != 0 &&
 238                   block + lastblocks == mdp -> heaplimit &&
 239                   mdp -> morecore (mdp, 0) == ADDRESS(block + lastblocks) &&
 240                   (morecore (mdp, (blocks - lastblocks) * BLOCKSIZE)) != NULL)
 241                 {
 242                   /* Which block we are extending (the `final free
 243                      block' referred to above) might have changed, if
 244                      it got combined with a freed info table.  */
 245                   block = mdp -> heapinfo[0].free.prev;
 246
 247                   mdp -> heapinfo[block].free.size += (blocks - lastblocks);
 248                   mdp -> heapstats.bytes_free +=
 249                       (blocks - lastblocks) * BLOCKSIZE;
 250                   continue;
 251                 }
 252               result = morecore(mdp, blocks * BLOCKSIZE);
 253               if (result == NULL)
 254                 {
 255                   return (NULL);
 256                 }
 257               block = BLOCK (result);
 258               mdp -> heapinfo[block].busy.type = 0;
 259               mdp -> heapinfo[block].busy.info.size = blocks;
 260               mdp -> heapstats.chunks_used++;
 261               mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
 262               return (result);
 263             }
 264         }
 265
 266       /* At this point we have found a suitable free list entry.
 267          Figure out how to remove what we need from the list. */
 268       result = ADDRESS(block);
 269       if (mdp -> heapinfo[block].free.size > blocks)
 270         {
 271           /* The block we found has a bit left over,
 272              so relink the tail end back into the free list. */
 273           mdp -> heapinfo[block + blocks].free.size
 274             = mdp -> heapinfo[block].free.size - blocks;
 275           mdp -> heapinfo[block + blocks].free.next
 276             = mdp -> heapinfo[block].free.next;
 277           mdp -> heapinfo[block + blocks].free.prev
 278             = mdp -> heapinfo[block].free.prev;
 279           mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
 280             = mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
 281               = mdp -> heapindex = block + blocks;
 282         }
 283       else
 284         {
 285           /* The block exactly matches our requirements,
 286              so just remove it from the list. */
 287           mdp -> heapinfo[mdp -> heapinfo[block].free.next].free.prev
 288             = mdp -> heapinfo[block].free.prev;
 289           mdp -> heapinfo[mdp -> heapinfo[block].free.prev].free.next
 290             = mdp -> heapindex = mdp -> heapinfo[block].free.next;
 291           mdp -> heapstats.chunks_free--;
 292         }
 293
 294       mdp -> heapinfo[block].busy.type = 0;
 295       mdp -> heapinfo[block].busy.info.size = blocks;
 296       mdp -> heapstats.chunks_used++;
 297       mdp -> heapstats.bytes_used += blocks * BLOCKSIZE;
 298       mdp -> heapstats.bytes_free -= blocks * BLOCKSIZE;
 299     }
 300
 301   return (result);
 302 }
 303
 304 /* When using this package, provide a version of malloc/realloc/free built
 305    on top of it, so that if we use the default sbrk() region we will not
 306    collide with another malloc package trying to do the same thing, if
 307    the application contains any "hidden" calls to malloc/realloc/free (such
 308    as inside a system library).
 309    FIXME: disabled for now */
 310
 311 //void* malloc (size_t size) {
 312 //  void* result;
 313 //  result = mmalloc (NULL, size);
 314 //  return (result);
 315 //}