xref: /netbsd-src/external/gpl3/binutils/dist/libiberty/objalloc.c (revision dd7241df2fae9da4ea2bd20a68f001fa86ecf909)
12a6b7db3Sskrll /* objalloc.c -- routines to allocate memory for objects
2*dd7241dfSchristos    Copyright (C) 1997-2024 Free Software Foundation, Inc.
32a6b7db3Sskrll    Written by Ian Lance Taylor, Cygnus Solutions.
42a6b7db3Sskrll 
52a6b7db3Sskrll This program is free software; you can redistribute it and/or modify it
62a6b7db3Sskrll under the terms of the GNU General Public License as published by the
72a6b7db3Sskrll Free Software Foundation; either version 2, or (at your option) any
82a6b7db3Sskrll later version.
92a6b7db3Sskrll 
102a6b7db3Sskrll This program is distributed in the hope that it will be useful,
112a6b7db3Sskrll but WITHOUT ANY WARRANTY; without even the implied warranty of
122a6b7db3Sskrll MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
132a6b7db3Sskrll GNU General Public License for more details.
142a6b7db3Sskrll 
152a6b7db3Sskrll You should have received a copy of the GNU General Public License
162a6b7db3Sskrll along with this program; if not, write to the Free Software
172a6b7db3Sskrll Foundation, 51 Franklin Street - Fifth Floor,
182a6b7db3Sskrll Boston, MA 02110-1301, USA.  */
192a6b7db3Sskrll 
202a6b7db3Sskrll #include "config.h"
212a6b7db3Sskrll #include "ansidecl.h"
222a6b7db3Sskrll 
232a6b7db3Sskrll #include "objalloc.h"
242a6b7db3Sskrll 
252a6b7db3Sskrll /* Get a definition for NULL.  */
262a6b7db3Sskrll #include <stdio.h>
272a6b7db3Sskrll 
282a6b7db3Sskrll #if VMS
292a6b7db3Sskrll #include <stdlib.h>
302a6b7db3Sskrll #include <unixlib.h>
312a6b7db3Sskrll #else
322a6b7db3Sskrll 
332a6b7db3Sskrll /* Get a definition for size_t.  */
342a6b7db3Sskrll #include <stddef.h>
352a6b7db3Sskrll 
362a6b7db3Sskrll #ifdef HAVE_STDLIB_H
372a6b7db3Sskrll #include <stdlib.h>
382a6b7db3Sskrll #else
392a6b7db3Sskrll /* For systems with larger pointers than ints, this must be declared.  */
4003f5171aSchristos extern void *malloc (size_t);
4103f5171aSchristos extern void free (void *);
422a6b7db3Sskrll #endif
432a6b7db3Sskrll 
442a6b7db3Sskrll #endif
452a6b7db3Sskrll 
462a6b7db3Sskrll /* These routines allocate space for an object.  Freeing allocated
472a6b7db3Sskrll    space may or may not free all more recently allocated space.
482a6b7db3Sskrll 
492a6b7db3Sskrll    We handle large and small allocation requests differently.  If we
502a6b7db3Sskrll    don't have enough space in the current block, and the allocation
512a6b7db3Sskrll    request is for more than 512 bytes, we simply pass it through to
522a6b7db3Sskrll    malloc.  */
532a6b7db3Sskrll 
542a6b7db3Sskrll /* The objalloc structure is defined in objalloc.h.  */
552a6b7db3Sskrll 
562a6b7db3Sskrll /* This structure appears at the start of each chunk.  */
572a6b7db3Sskrll 
582a6b7db3Sskrll struct objalloc_chunk
592a6b7db3Sskrll {
602a6b7db3Sskrll   /* Next chunk.  */
612a6b7db3Sskrll   struct objalloc_chunk *next;
622a6b7db3Sskrll   /* If this chunk contains large objects, this is the value of
632a6b7db3Sskrll      current_ptr when this chunk was allocated.  If this chunk
642a6b7db3Sskrll      contains small objects, this is NULL.  */
652a6b7db3Sskrll   char *current_ptr;
662a6b7db3Sskrll };
672a6b7db3Sskrll 
682a6b7db3Sskrll /* The aligned size of objalloc_chunk.  */
692a6b7db3Sskrll 
702a6b7db3Sskrll #define CHUNK_HEADER_SIZE					\
712a6b7db3Sskrll   ((sizeof (struct objalloc_chunk) + OBJALLOC_ALIGN - 1)	\
722a6b7db3Sskrll    &~ (OBJALLOC_ALIGN - 1))
732a6b7db3Sskrll 
742a6b7db3Sskrll /* We ask for this much memory each time we create a chunk which is to
752a6b7db3Sskrll    hold small objects.  */
762a6b7db3Sskrll 
772a6b7db3Sskrll #define CHUNK_SIZE (4096 - 32)
782a6b7db3Sskrll 
792a6b7db3Sskrll /* A request for this amount or more is just passed through to malloc.  */
802a6b7db3Sskrll 
812a6b7db3Sskrll #define BIG_REQUEST (512)
822a6b7db3Sskrll 
832a6b7db3Sskrll /* Create an objalloc structure.  */
842a6b7db3Sskrll 
852a6b7db3Sskrll struct objalloc *
objalloc_create(void)862a6b7db3Sskrll objalloc_create (void)
872a6b7db3Sskrll {
882a6b7db3Sskrll   struct objalloc *ret;
892a6b7db3Sskrll   struct objalloc_chunk *chunk;
902a6b7db3Sskrll 
912a6b7db3Sskrll   ret = (struct objalloc *) malloc (sizeof *ret);
922a6b7db3Sskrll   if (ret == NULL)
932a6b7db3Sskrll     return NULL;
942a6b7db3Sskrll 
9503f5171aSchristos   ret->chunks = (void *) malloc (CHUNK_SIZE);
962a6b7db3Sskrll   if (ret->chunks == NULL)
972a6b7db3Sskrll     {
982a6b7db3Sskrll       free (ret);
992a6b7db3Sskrll       return NULL;
1002a6b7db3Sskrll     }
1012a6b7db3Sskrll 
1022a6b7db3Sskrll   chunk = (struct objalloc_chunk *) ret->chunks;
1032a6b7db3Sskrll   chunk->next = NULL;
1042a6b7db3Sskrll   chunk->current_ptr = NULL;
1052a6b7db3Sskrll 
1062a6b7db3Sskrll   ret->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
1072a6b7db3Sskrll   ret->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
1082a6b7db3Sskrll 
1092a6b7db3Sskrll   return ret;
1102a6b7db3Sskrll }
1112a6b7db3Sskrll 
1122a6b7db3Sskrll /* Allocate space from an objalloc structure.  */
1132a6b7db3Sskrll 
11403f5171aSchristos void *
_objalloc_alloc(struct objalloc * o,unsigned long original_len)115d18545deSdrochner _objalloc_alloc (struct objalloc *o, unsigned long original_len)
1162a6b7db3Sskrll {
117d18545deSdrochner   unsigned long len = original_len;
118d18545deSdrochner 
1192a6b7db3Sskrll   /* We avoid confusion from zero sized objects by always allocating
1202a6b7db3Sskrll      at least 1 byte.  */
1212a6b7db3Sskrll   if (len == 0)
1222a6b7db3Sskrll     len = 1;
1232a6b7db3Sskrll 
1242a6b7db3Sskrll   len = (len + OBJALLOC_ALIGN - 1) &~ (OBJALLOC_ALIGN - 1);
1252a6b7db3Sskrll 
126d18545deSdrochner   /* Check for overflow in the alignment operation above and the
127d18545deSdrochner      malloc argument below. */
128d18545deSdrochner   if (len + CHUNK_HEADER_SIZE < original_len)
129d18545deSdrochner     return NULL;
130d18545deSdrochner 
1312a6b7db3Sskrll   if (len <= o->current_space)
1322a6b7db3Sskrll     {
1332a6b7db3Sskrll       o->current_ptr += len;
1342a6b7db3Sskrll       o->current_space -= len;
13503f5171aSchristos       return (void *) (o->current_ptr - len);
1362a6b7db3Sskrll     }
1372a6b7db3Sskrll 
1382a6b7db3Sskrll   if (len >= BIG_REQUEST)
1392a6b7db3Sskrll     {
1402a6b7db3Sskrll       char *ret;
1412a6b7db3Sskrll       struct objalloc_chunk *chunk;
1422a6b7db3Sskrll 
1432a6b7db3Sskrll       ret = (char *) malloc (CHUNK_HEADER_SIZE + len);
1442a6b7db3Sskrll       if (ret == NULL)
1452a6b7db3Sskrll 	return NULL;
1462a6b7db3Sskrll 
1472a6b7db3Sskrll       chunk = (struct objalloc_chunk *) ret;
1482a6b7db3Sskrll       chunk->next = (struct objalloc_chunk *) o->chunks;
1492a6b7db3Sskrll       chunk->current_ptr = o->current_ptr;
1502a6b7db3Sskrll 
15103f5171aSchristos       o->chunks = (void *) chunk;
1522a6b7db3Sskrll 
15303f5171aSchristos       return (void *) (ret + CHUNK_HEADER_SIZE);
1542a6b7db3Sskrll     }
1552a6b7db3Sskrll   else
1562a6b7db3Sskrll     {
1572a6b7db3Sskrll       struct objalloc_chunk *chunk;
1582a6b7db3Sskrll 
1592a6b7db3Sskrll       chunk = (struct objalloc_chunk *) malloc (CHUNK_SIZE);
1602a6b7db3Sskrll       if (chunk == NULL)
1612a6b7db3Sskrll 	return NULL;
1622a6b7db3Sskrll       chunk->next = (struct objalloc_chunk *) o->chunks;
1632a6b7db3Sskrll       chunk->current_ptr = NULL;
1642a6b7db3Sskrll 
1652a6b7db3Sskrll       o->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE;
1662a6b7db3Sskrll       o->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE;
1672a6b7db3Sskrll 
16803f5171aSchristos       o->chunks = (void *) chunk;
1692a6b7db3Sskrll 
1702a6b7db3Sskrll       return objalloc_alloc (o, len);
1712a6b7db3Sskrll     }
1722a6b7db3Sskrll }
1732a6b7db3Sskrll 
1742a6b7db3Sskrll /* Free an entire objalloc structure.  */
1752a6b7db3Sskrll 
1762a6b7db3Sskrll void
objalloc_free(struct objalloc * o)1772a6b7db3Sskrll objalloc_free (struct objalloc *o)
1782a6b7db3Sskrll {
1792a6b7db3Sskrll   struct objalloc_chunk *l;
1802a6b7db3Sskrll 
1812a6b7db3Sskrll   l = (struct objalloc_chunk *) o->chunks;
1822a6b7db3Sskrll   while (l != NULL)
1832a6b7db3Sskrll     {
1842a6b7db3Sskrll       struct objalloc_chunk *next;
1852a6b7db3Sskrll 
1862a6b7db3Sskrll       next = l->next;
1872a6b7db3Sskrll       free (l);
1882a6b7db3Sskrll       l = next;
1892a6b7db3Sskrll     }
1902a6b7db3Sskrll 
1912a6b7db3Sskrll   free (o);
1922a6b7db3Sskrll }
1932a6b7db3Sskrll 
1942a6b7db3Sskrll /* Free a block from an objalloc structure.  This also frees all more
1952a6b7db3Sskrll    recently allocated blocks.  */
1962a6b7db3Sskrll 
1972a6b7db3Sskrll void
objalloc_free_block(struct objalloc * o,void * block)19803f5171aSchristos objalloc_free_block (struct objalloc *o, void *block)
1992a6b7db3Sskrll {
2002a6b7db3Sskrll   struct objalloc_chunk *p, *small;
2012a6b7db3Sskrll   char *b = (char *) block;
2022a6b7db3Sskrll 
2032a6b7db3Sskrll   /* First set P to the chunk which contains the block we are freeing,
2042a6b7db3Sskrll      and set Q to the last small object chunk we see before P.  */
2052a6b7db3Sskrll   small = NULL;
2062a6b7db3Sskrll   for (p = (struct objalloc_chunk *) o->chunks; p != NULL; p = p->next)
2072a6b7db3Sskrll     {
2082a6b7db3Sskrll       if (p->current_ptr == NULL)
2092a6b7db3Sskrll 	{
2102a6b7db3Sskrll 	  if (b > (char *) p && b < (char *) p + CHUNK_SIZE)
2112a6b7db3Sskrll 	    break;
2122a6b7db3Sskrll 	  small = p;
2132a6b7db3Sskrll 	}
2142a6b7db3Sskrll       else
2152a6b7db3Sskrll 	{
2162a6b7db3Sskrll 	  if (b == (char *) p + CHUNK_HEADER_SIZE)
2172a6b7db3Sskrll 	    break;
2182a6b7db3Sskrll 	}
2192a6b7db3Sskrll     }
2202a6b7db3Sskrll 
2212a6b7db3Sskrll   /* If we can't find the chunk, the caller has made a mistake.  */
2222a6b7db3Sskrll   if (p == NULL)
2232a6b7db3Sskrll     abort ();
2242a6b7db3Sskrll 
2252a6b7db3Sskrll   if (p->current_ptr == NULL)
2262a6b7db3Sskrll     {
2272a6b7db3Sskrll       struct objalloc_chunk *q;
2282a6b7db3Sskrll       struct objalloc_chunk *first;
2292a6b7db3Sskrll 
2302a6b7db3Sskrll       /* The block is in a chunk containing small objects.  We can
2312a6b7db3Sskrll 	 free every chunk through SMALL, because they have certainly
2322a6b7db3Sskrll 	 been allocated more recently.  After SMALL, we will not see
2332a6b7db3Sskrll 	 any chunks containing small objects; we can free any big
2342a6b7db3Sskrll 	 chunk if the current_ptr is greater than or equal to B.  We
2352a6b7db3Sskrll 	 can then reset the new current_ptr to B.  */
2362a6b7db3Sskrll 
2372a6b7db3Sskrll       first = NULL;
2382a6b7db3Sskrll       q = (struct objalloc_chunk *) o->chunks;
2392a6b7db3Sskrll       while (q != p)
2402a6b7db3Sskrll 	{
2412a6b7db3Sskrll 	  struct objalloc_chunk *next;
2422a6b7db3Sskrll 
2432a6b7db3Sskrll 	  next = q->next;
2442a6b7db3Sskrll 	  if (small != NULL)
2452a6b7db3Sskrll 	    {
2462a6b7db3Sskrll 	      if (small == q)
2472a6b7db3Sskrll 		small = NULL;
2482a6b7db3Sskrll 	      free (q);
2492a6b7db3Sskrll 	    }
2502a6b7db3Sskrll 	  else if (q->current_ptr > b)
2512a6b7db3Sskrll 	    free (q);
2522a6b7db3Sskrll 	  else if (first == NULL)
2532a6b7db3Sskrll 	    first = q;
2542a6b7db3Sskrll 
2552a6b7db3Sskrll 	  q = next;
2562a6b7db3Sskrll 	}
2572a6b7db3Sskrll 
2582a6b7db3Sskrll       if (first == NULL)
2592a6b7db3Sskrll 	first = p;
26003f5171aSchristos       o->chunks = (void *) first;
2612a6b7db3Sskrll 
2622a6b7db3Sskrll       /* Now start allocating from this small block again.  */
2632a6b7db3Sskrll       o->current_ptr = b;
2642a6b7db3Sskrll       o->current_space = ((char *) p + CHUNK_SIZE) - b;
2652a6b7db3Sskrll     }
2662a6b7db3Sskrll   else
2672a6b7db3Sskrll     {
2682a6b7db3Sskrll       struct objalloc_chunk *q;
2692a6b7db3Sskrll       char *current_ptr;
2702a6b7db3Sskrll 
2712a6b7db3Sskrll       /* This block is in a large chunk by itself.  We can free
2722a6b7db3Sskrll          everything on the list up to and including this block.  We
2732a6b7db3Sskrll          then start allocating from the next chunk containing small
2742a6b7db3Sskrll          objects, setting current_ptr from the value stored with the
2752a6b7db3Sskrll          large chunk we are freeing.  */
2762a6b7db3Sskrll 
2772a6b7db3Sskrll       current_ptr = p->current_ptr;
2782a6b7db3Sskrll       p = p->next;
2792a6b7db3Sskrll 
2802a6b7db3Sskrll       q = (struct objalloc_chunk *) o->chunks;
2812a6b7db3Sskrll       while (q != p)
2822a6b7db3Sskrll 	{
2832a6b7db3Sskrll 	  struct objalloc_chunk *next;
2842a6b7db3Sskrll 
2852a6b7db3Sskrll 	  next = q->next;
2862a6b7db3Sskrll 	  free (q);
2872a6b7db3Sskrll 	  q = next;
2882a6b7db3Sskrll 	}
2892a6b7db3Sskrll 
29003f5171aSchristos       o->chunks = (void *) p;
2912a6b7db3Sskrll 
2922a6b7db3Sskrll       while (p->current_ptr != NULL)
2932a6b7db3Sskrll 	p = p->next;
2942a6b7db3Sskrll 
2952a6b7db3Sskrll       o->current_ptr = current_ptr;
2962a6b7db3Sskrll       o->current_space = ((char *) p + CHUNK_SIZE) - current_ptr;
2972a6b7db3Sskrll     }
2982a6b7db3Sskrll }
299