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