133965Sjdp/* objalloc.c -- routines to allocate memory for objects 233965Sjdp Copyright 1997 Free Software Foundation, Inc. 333965Sjdp Written by Ian Lance Taylor, Cygnus Solutions. 433965Sjdp 533965SjdpThis program is free software; you can redistribute it and/or modify it 633965Sjdpunder the terms of the GNU General Public License as published by the 733965SjdpFree Software Foundation; either version 2, or (at your option) any 833965Sjdplater version. 933965Sjdp 1033965SjdpThis program is distributed in the hope that it will be useful, 1133965Sjdpbut WITHOUT ANY WARRANTY; without even the implied warranty of 1233965SjdpMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1333965SjdpGNU General Public License for more details. 1433965Sjdp 1533965SjdpYou should have received a copy of the GNU General Public License 1633965Sjdpalong with this program; if not, write to the Free Software 17218822SdimFoundation, 51 Franklin Street - Fifth Floor, 18218822SdimBoston, MA 02110-1301, USA. */ 1933965Sjdp 20218822Sdim#include "config.h" 2133965Sjdp#include "ansidecl.h" 2277298Sobrien 2333965Sjdp#include "objalloc.h" 2433965Sjdp 2533965Sjdp/* Get a definition for NULL. */ 2633965Sjdp#include <stdio.h> 2733965Sjdp 2833965Sjdp#if VMS 2933965Sjdp#include <stdlib.h> 3033965Sjdp#include <unixlib.h> 3133965Sjdp#else 3233965Sjdp 3333965Sjdp/* Get a definition for size_t. */ 3433965Sjdp#include <stddef.h> 3533965Sjdp 3677298Sobrien#ifdef HAVE_STDLIB_H 3777298Sobrien#include <stdlib.h> 3877298Sobrien#else 3933965Sjdp/* For systems with larger pointers than ints, this must be declared. */ 40218822Sdimextern PTR malloc (size_t); 41218822Sdimextern void free (PTR); 4233965Sjdp#endif 4333965Sjdp 4477298Sobrien#endif 4577298Sobrien 4633965Sjdp/* These routines allocate space for an object. Freeing allocated 4733965Sjdp space may or may not free all more recently allocated space. 4833965Sjdp 4933965Sjdp We handle large and small allocation requests differently. If we 5033965Sjdp don't have enough space in the current block, and the allocation 5133965Sjdp request is for more than 512 bytes, we simply pass it through to 5233965Sjdp malloc. */ 5333965Sjdp 5433965Sjdp/* The objalloc structure is defined in objalloc.h. */ 5533965Sjdp 5633965Sjdp/* This structure appears at the start of each chunk. */ 5733965Sjdp 5833965Sjdpstruct objalloc_chunk 5933965Sjdp{ 6033965Sjdp /* Next chunk. */ 6133965Sjdp struct objalloc_chunk *next; 6233965Sjdp /* If this chunk contains large objects, this is the value of 6333965Sjdp current_ptr when this chunk was allocated. If this chunk 6433965Sjdp contains small objects, this is NULL. */ 6533965Sjdp char *current_ptr; 6633965Sjdp}; 6733965Sjdp 6833965Sjdp/* The aligned size of objalloc_chunk. */ 6933965Sjdp 7033965Sjdp#define CHUNK_HEADER_SIZE \ 7133965Sjdp ((sizeof (struct objalloc_chunk) + OBJALLOC_ALIGN - 1) \ 7233965Sjdp &~ (OBJALLOC_ALIGN - 1)) 7333965Sjdp 7433965Sjdp/* We ask for this much memory each time we create a chunk which is to 7533965Sjdp hold small objects. */ 7633965Sjdp 7733965Sjdp#define CHUNK_SIZE (4096 - 32) 7833965Sjdp 7933965Sjdp/* A request for this amount or more is just passed through to malloc. */ 8033965Sjdp 8133965Sjdp#define BIG_REQUEST (512) 8233965Sjdp 8333965Sjdp/* Create an objalloc structure. */ 8433965Sjdp 8533965Sjdpstruct objalloc * 86218822Sdimobjalloc_create (void) 8733965Sjdp{ 8833965Sjdp struct objalloc *ret; 8933965Sjdp struct objalloc_chunk *chunk; 9033965Sjdp 9133965Sjdp ret = (struct objalloc *) malloc (sizeof *ret); 9233965Sjdp if (ret == NULL) 9333965Sjdp return NULL; 9433965Sjdp 9533965Sjdp ret->chunks = (PTR) malloc (CHUNK_SIZE); 9633965Sjdp if (ret->chunks == NULL) 9733965Sjdp { 9833965Sjdp free (ret); 9933965Sjdp return NULL; 10033965Sjdp } 10133965Sjdp 10233965Sjdp chunk = (struct objalloc_chunk *) ret->chunks; 10333965Sjdp chunk->next = NULL; 10433965Sjdp chunk->current_ptr = NULL; 10533965Sjdp 10633965Sjdp ret->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE; 10733965Sjdp ret->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE; 10833965Sjdp 10933965Sjdp return ret; 11033965Sjdp} 11133965Sjdp 11233965Sjdp/* Allocate space from an objalloc structure. */ 11333965Sjdp 11433965SjdpPTR 115218822Sdim_objalloc_alloc (struct objalloc *o, unsigned long len) 11633965Sjdp{ 11733965Sjdp /* We avoid confusion from zero sized objects by always allocating 11833965Sjdp at least 1 byte. */ 11933965Sjdp if (len == 0) 12033965Sjdp len = 1; 12133965Sjdp 12233965Sjdp len = (len + OBJALLOC_ALIGN - 1) &~ (OBJALLOC_ALIGN - 1); 12333965Sjdp 12433965Sjdp if (len <= o->current_space) 12533965Sjdp { 12633965Sjdp o->current_ptr += len; 12733965Sjdp o->current_space -= len; 12833965Sjdp return (PTR) (o->current_ptr - len); 12933965Sjdp } 13033965Sjdp 13133965Sjdp if (len >= BIG_REQUEST) 13233965Sjdp { 13333965Sjdp char *ret; 13433965Sjdp struct objalloc_chunk *chunk; 13533965Sjdp 13633965Sjdp ret = (char *) malloc (CHUNK_HEADER_SIZE + len); 13733965Sjdp if (ret == NULL) 13833965Sjdp return NULL; 13933965Sjdp 14033965Sjdp chunk = (struct objalloc_chunk *) ret; 14133965Sjdp chunk->next = (struct objalloc_chunk *) o->chunks; 14233965Sjdp chunk->current_ptr = o->current_ptr; 14333965Sjdp 14433965Sjdp o->chunks = (PTR) chunk; 14533965Sjdp 14633965Sjdp return (PTR) (ret + CHUNK_HEADER_SIZE); 14733965Sjdp } 14833965Sjdp else 14933965Sjdp { 15033965Sjdp struct objalloc_chunk *chunk; 15133965Sjdp 15233965Sjdp chunk = (struct objalloc_chunk *) malloc (CHUNK_SIZE); 15333965Sjdp if (chunk == NULL) 15433965Sjdp return NULL; 15533965Sjdp chunk->next = (struct objalloc_chunk *) o->chunks; 15633965Sjdp chunk->current_ptr = NULL; 15733965Sjdp 15833965Sjdp o->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE; 15933965Sjdp o->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE; 16033965Sjdp 16133965Sjdp o->chunks = (PTR) chunk; 16233965Sjdp 16333965Sjdp return objalloc_alloc (o, len); 16433965Sjdp } 16533965Sjdp} 16633965Sjdp 16733965Sjdp/* Free an entire objalloc structure. */ 16833965Sjdp 16933965Sjdpvoid 170218822Sdimobjalloc_free (struct objalloc *o) 17133965Sjdp{ 17233965Sjdp struct objalloc_chunk *l; 17333965Sjdp 17433965Sjdp l = (struct objalloc_chunk *) o->chunks; 17533965Sjdp while (l != NULL) 17633965Sjdp { 17733965Sjdp struct objalloc_chunk *next; 17833965Sjdp 17933965Sjdp next = l->next; 18033965Sjdp free (l); 18133965Sjdp l = next; 18233965Sjdp } 18333965Sjdp 18433965Sjdp free (o); 18533965Sjdp} 18633965Sjdp 18733965Sjdp/* Free a block from an objalloc structure. This also frees all more 18833965Sjdp recently allocated blocks. */ 18933965Sjdp 19033965Sjdpvoid 191218822Sdimobjalloc_free_block (struct objalloc *o, PTR block) 19233965Sjdp{ 19333965Sjdp struct objalloc_chunk *p, *small; 19433965Sjdp char *b = (char *) block; 19533965Sjdp 19633965Sjdp /* First set P to the chunk which contains the block we are freeing, 19733965Sjdp and set Q to the last small object chunk we see before P. */ 19833965Sjdp small = NULL; 19933965Sjdp for (p = (struct objalloc_chunk *) o->chunks; p != NULL; p = p->next) 20033965Sjdp { 20133965Sjdp if (p->current_ptr == NULL) 20233965Sjdp { 20333965Sjdp if (b > (char *) p && b < (char *) p + CHUNK_SIZE) 20433965Sjdp break; 20533965Sjdp small = p; 20633965Sjdp } 20733965Sjdp else 20833965Sjdp { 20933965Sjdp if (b == (char *) p + CHUNK_HEADER_SIZE) 21033965Sjdp break; 21133965Sjdp } 21233965Sjdp } 21333965Sjdp 21433965Sjdp /* If we can't find the chunk, the caller has made a mistake. */ 21533965Sjdp if (p == NULL) 21633965Sjdp abort (); 21733965Sjdp 21833965Sjdp if (p->current_ptr == NULL) 21933965Sjdp { 22033965Sjdp struct objalloc_chunk *q; 22133965Sjdp struct objalloc_chunk *first; 22233965Sjdp 22333965Sjdp /* The block is in a chunk containing small objects. We can 22433965Sjdp free every chunk through SMALL, because they have certainly 22533965Sjdp been allocated more recently. After SMALL, we will not see 22633965Sjdp any chunks containing small objects; we can free any big 22733965Sjdp chunk if the current_ptr is greater than or equal to B. We 22833965Sjdp can then reset the new current_ptr to B. */ 22933965Sjdp 23033965Sjdp first = NULL; 23133965Sjdp q = (struct objalloc_chunk *) o->chunks; 23233965Sjdp while (q != p) 23333965Sjdp { 23433965Sjdp struct objalloc_chunk *next; 23533965Sjdp 23633965Sjdp next = q->next; 23733965Sjdp if (small != NULL) 23833965Sjdp { 23933965Sjdp if (small == q) 24033965Sjdp small = NULL; 24133965Sjdp free (q); 24233965Sjdp } 24333965Sjdp else if (q->current_ptr > b) 24433965Sjdp free (q); 24533965Sjdp else if (first == NULL) 24633965Sjdp first = q; 24733965Sjdp 24833965Sjdp q = next; 24933965Sjdp } 25033965Sjdp 25133965Sjdp if (first == NULL) 25233965Sjdp first = p; 25333965Sjdp o->chunks = (PTR) first; 25433965Sjdp 25533965Sjdp /* Now start allocating from this small block again. */ 25633965Sjdp o->current_ptr = b; 25733965Sjdp o->current_space = ((char *) p + CHUNK_SIZE) - b; 25833965Sjdp } 25933965Sjdp else 26033965Sjdp { 26133965Sjdp struct objalloc_chunk *q; 26233965Sjdp char *current_ptr; 26333965Sjdp 26433965Sjdp /* This block is in a large chunk by itself. We can free 26533965Sjdp everything on the list up to and including this block. We 26633965Sjdp then start allocating from the next chunk containing small 26733965Sjdp objects, setting current_ptr from the value stored with the 26833965Sjdp large chunk we are freeing. */ 26933965Sjdp 27033965Sjdp current_ptr = p->current_ptr; 27133965Sjdp p = p->next; 27233965Sjdp 27333965Sjdp q = (struct objalloc_chunk *) o->chunks; 27433965Sjdp while (q != p) 27533965Sjdp { 27633965Sjdp struct objalloc_chunk *next; 27733965Sjdp 27833965Sjdp next = q->next; 27933965Sjdp free (q); 28033965Sjdp q = next; 28133965Sjdp } 28233965Sjdp 28333965Sjdp o->chunks = (PTR) p; 28433965Sjdp 28533965Sjdp while (p->current_ptr != NULL) 28633965Sjdp p = p->next; 28733965Sjdp 28833965Sjdp o->current_ptr = current_ptr; 28933965Sjdp o->current_space = ((char *) p + CHUNK_SIZE) - current_ptr; 29033965Sjdp } 29133965Sjdp} 292