libiberty/objalloc.c

   1 /* objalloc.c -- routines to allocate memory for objects
   2    Copyright 1997 Free Software Foundation, Inc.
   3    Written by Ian Lance Taylor, Cygnus Solutions.
   4
   5 This program is free software; you can redistribute it and/or modify it
   6 under the terms of the GNU General Public License as published by the
   7 Free Software Foundation; either version 2, or (at your option) any
   8 later version.
   9
  10 This program 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
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; if not, write to the Free Software
  17 Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  18
  19 #include "ansidecl.h"
  20 #include "objalloc.h"
  21
  22 /* Get a definition for NULL.  */
  23 #include <stdio.h>
  24
  25 #if VMS
  26 #include <stdlib.h>
  27 #include <unixlib.h>
  28 #else
  29
  30 #ifdef ANSI_PROTOTYPES
  31 /* Get a definition for size_t.  */
  32 #include <stddef.h>
  33 #endif
  34
  35 /* For systems with larger pointers than ints, this must be declared.  */
  36 extern PTR malloc PARAMS ((size_t));
  37 extern void free PARAMS ((PTR));
  38 #endif
  39
  40 /* These routines allocate space for an object.  Freeing allocated
  41    space may or may not free all more recently allocated space.
  42
  43    We handle large and small allocation requests differently.  If we
  44    don't have enough space in the current block, and the allocation
  45    request is for more than 512 bytes, we simply pass it through to
  46    malloc.  */
  47
  48 /* The objalloc structure is defined in objalloc.h.  */
  49
  50 /* This structure appears at the start of each chunk.  */
  51
  52 struct objalloc_chunk
  53 {
  54   /* Next chunk.  */
  55   struct objalloc_chunk *next;
  56   /* If this chunk contains large objects, this is the value of
  57      current_ptr when this chunk was allocated.  If this chunk
  58      contains small objects, this is NULL.  */
  59   char *current_ptr;
  60 };
  61
  62 /* The aligned size of objalloc_chunk.  */
  63
  64 #define CHUNK_HEADER_SIZE                                       \
  65   ((sizeof (struct objalloc_chunk) + OBJALLOC_ALIGN - 1)        \
  66    &~ (OBJALLOC_ALIGN - 1))
  67
  68 /* We ask for this much memory each time we create a chunk which is to
  69    hold small objects.  */
  70
  71 #define CHUNK_SIZE (4096 - 32)
  72
  73 /* A request for this amount or more is just passed through to malloc.  */
  74
  75 #define BIG_REQUEST (512)
  76
  77 /* Create an objalloc structure.  */
  78
  79 struct objalloc *
  80 objalloc_create ()
  81 {
  82   struct objalloc *ret;
  83   struct objalloc_chunk *chunk;
  84
  85   ret = (struct objalloc *) malloc (sizeof *ret);
  86   if (ret == NULL)
  87     return NULL;
  88
  89   ret->chunks = (PTR) malloc (CHUNK_SIZE);
  90   if (ret->chunks == NULL)
  91     {
  92       free (ret);
  93       return NULL;
  94     }
  95
  96   chunk = (struct objalloc_chunk *) ret->chunks;
  97   chunk->next = NULL;
  98   chunk->current_ptr = NULL;
  99
 100   ret->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
 101   ret->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
 102
 103   return ret;
 104 }
 105
 106 /* Allocate space from an objalloc structure.  */
 107
 108 PTR
 109 _objalloc_alloc (o, len)
 110      struct objalloc *o;
 111      unsigned long len;
 112 {
 113   /* We avoid confusion from zero sized objects by always allocating
 114      at least 1 byte.  */
 115   if (len == 0)
 116     len = 1;
 117
 118   len = (len + OBJALLOC_ALIGN - 1) &~ (OBJALLOC_ALIGN - 1);
 119
 120   if (len <= o->current_space)
 121     {
 122       o->current_ptr += len;
 123       o->current_space -= len;
 124       return (PTR) (o->current_ptr - len);
 125     }
 126
 127   if (len >= BIG_REQUEST)
 128     {
 129       char *ret;
 130       struct objalloc_chunk *chunk;
 131
 132       ret = (char *) malloc (CHUNK_HEADER_SIZE + len);
 133       if (ret == NULL)
 134         return NULL;
 135
 136       chunk = (struct objalloc_chunk *) ret;
 137       chunk->next = (struct objalloc_chunk *) o->chunks;
 138       chunk->current_ptr = o->current_ptr;
 139
 140       o->chunks = (PTR) chunk;
 141
 142       return (PTR) (ret + CHUNK_HEADER_SIZE);
 143     }
 144   else
 145     {
 146       struct objalloc_chunk *chunk;
 147
 148       chunk = (struct objalloc_chunk *) malloc (CHUNK_SIZE);
 149       if (chunk == NULL)
 150         return NULL;
 151       chunk->next = (struct objalloc_chunk *) o->chunks;
 152       chunk->current_ptr = NULL;
 153
 154       o->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
 155       o->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
 156
 157       o->chunks = (PTR) chunk;
 158
 159       return objalloc_alloc (o, len);
 160     }
 161 }
 162
 163 /* Free an entire objalloc structure.  */
 164
 165 void
 166 objalloc_free (o)
 167      struct objalloc *o;
 168 {
 169   struct objalloc_chunk *l;
 170
 171   l = (struct objalloc_chunk *) o->chunks;
 172   while (l != NULL)
 173     {
 174       struct objalloc_chunk *next;
 175
 176       next = l->next;
 177       free (l);
 178       l = next;
 179     }
 180
 181   free (o);
 182 }
 183
 184 /* Free a block from an objalloc structure.  This also frees all more
 185    recently allocated blocks.  */
 186
 187 void
 188 objalloc_free_block (o, block)
 189      struct objalloc *o;
 190      PTR block;
 191 {
 192   struct objalloc_chunk *p, *small;
 193   char *b = (char *) block;
 194
 195   /* First set P to the chunk which contains the block we are freeing,
 196      and set Q to the last small object chunk we see before P.  */
 197   small = NULL;
 198   for (p = (struct objalloc_chunk *) o->chunks; p != NULL; p = p->next)
 199     {
 200       if (p->current_ptr == NULL)
 201         {
 202           if (b > (char *) p && b < (char *) p + CHUNK_SIZE)
 203             break;
 204           small = p;
 205         }
 206       else
 207         {
 208           if (b == (char *) p + CHUNK_HEADER_SIZE)
 209             break;
 210         }
 211     }
 212
 213   /* If we can't find the chunk, the caller has made a mistake.  */
 214   if (p == NULL)
 215     abort ();
 216
 217   if (p->current_ptr == NULL)
 218     {
 219       struct objalloc_chunk *q;
 220       struct objalloc_chunk *first;
 221
 222       /* The block is in a chunk containing small objects.  We can
 223          free every chunk through SMALL, because they have certainly
 224          been allocated more recently.  After SMALL, we will not see
 225          any chunks containing small objects; we can free any big
 226          chunk if the current_ptr is greater than or equal to B.  We
 227          can then reset the new current_ptr to B.  */
 228
 229       first = NULL;
 230       q = (struct objalloc_chunk *) o->chunks;
 231       while (q != p)
 232         {
 233           struct objalloc_chunk *next;
 234
 235           next = q->next;
 236           if (small != NULL)
 237             {
 238               if (small == q)
 239                 small = NULL;
 240               free (q);
 241             }
 242           else if (q->current_ptr > b)
 243             free (q);
 244           else if (first == NULL)
 245             first = q;
 246
 247           q = next;
 248         }
 249
 250       if (first == NULL)
 251         first = p;
 252       o->chunks = (PTR) first;
 253
 254       /* Now start allocating from this small block again.  */
 255       o->current_ptr = b;
 256       o->current_space = ((char *) p + CHUNK_SIZE) - b;
 257     }
 258   else
 259     {
 260       struct objalloc_chunk *q;
 261       char *current_ptr;
 262
 263       /* This block is in a large chunk by itself.  We can free
 264          everything on the list up to and including this block.  We
 265          then start allocating from the next chunk containing small
 266          objects, setting current_ptr from the value stored with the
 267          large chunk we are freeing.  */
 268
 269       current_ptr = p->current_ptr;
 270       p = p->next;
 271
 272       q = (struct objalloc_chunk *) o->chunks;
 273       while (q != p)
 274         {
 275           struct objalloc_chunk *next;
 276
 277           next = q->next;
 278           free (q);
 279           q = next;
 280         }
 281
 282       o->chunks = (PTR) p;
 283
 284       while (p->current_ptr != NULL)
 285         p = p->next;
 286
 287       o->current_ptr = current_ptr;
 288       o->current_space = ((char *) p + CHUNK_SIZE) - current_ptr;
 289     }
 290 }