1169695Skan/* objalloc.c -- routines to allocate memory for objects 2301976Spfg Copyright 1997-2012 Free Software Foundation, Inc. 3169695Skan Written by Ian Lance Taylor, Cygnus Solutions. 4169695Skan 5169695SkanThis program is free software; you can redistribute it and/or modify it 6169695Skanunder the terms of the GNU General Public License as published by the 7169695SkanFree Software Foundation; either version 2, or (at your option) any 8169695Skanlater version. 9169695Skan 10169695SkanThis program is distributed in the hope that it will be useful, 11169695Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 12169695SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13169695SkanGNU General Public License for more details. 14169695Skan 15169695SkanYou should have received a copy of the GNU General Public License 16169695Skanalong with this program; if not, write to the Free Software 17169695SkanFoundation, 51 Franklin Street - Fifth Floor, 18169695SkanBoston, MA 02110-1301, USA. */ 19169695Skan 20169695Skan#include "config.h" 21169695Skan#include "ansidecl.h" 22169695Skan 23169695Skan#include "objalloc.h" 24169695Skan 25169695Skan/* Get a definition for NULL. */ 26169695Skan#include <stdio.h> 27169695Skan 28169695Skan#if VMS 29169695Skan#include <stdlib.h> 30169695Skan#include <unixlib.h> 31169695Skan#else 32169695Skan 33169695Skan/* Get a definition for size_t. */ 34169695Skan#include <stddef.h> 35169695Skan 36169695Skan#ifdef HAVE_STDLIB_H 37169695Skan#include <stdlib.h> 38169695Skan#else 39169695Skan/* For systems with larger pointers than ints, this must be declared. */ 40169695Skanextern PTR malloc (size_t); 41169695Skanextern void free (PTR); 42169695Skan#endif 43169695Skan 44169695Skan#endif 45169695Skan 46169695Skan/* These routines allocate space for an object. Freeing allocated 47169695Skan space may or may not free all more recently allocated space. 48169695Skan 49169695Skan We handle large and small allocation requests differently. If we 50169695Skan don't have enough space in the current block, and the allocation 51169695Skan request is for more than 512 bytes, we simply pass it through to 52169695Skan malloc. */ 53169695Skan 54169695Skan/* The objalloc structure is defined in objalloc.h. */ 55169695Skan 56169695Skan/* This structure appears at the start of each chunk. */ 57169695Skan 58169695Skanstruct objalloc_chunk 59169695Skan{ 60169695Skan /* Next chunk. */ 61169695Skan struct objalloc_chunk *next; 62169695Skan /* If this chunk contains large objects, this is the value of 63169695Skan current_ptr when this chunk was allocated. If this chunk 64169695Skan contains small objects, this is NULL. */ 65169695Skan char *current_ptr; 66169695Skan}; 67169695Skan 68169695Skan/* The aligned size of objalloc_chunk. */ 69169695Skan 70169695Skan#define CHUNK_HEADER_SIZE \ 71169695Skan ((sizeof (struct objalloc_chunk) + OBJALLOC_ALIGN - 1) \ 72169695Skan &~ (OBJALLOC_ALIGN - 1)) 73169695Skan 74169695Skan/* We ask for this much memory each time we create a chunk which is to 75169695Skan hold small objects. */ 76169695Skan 77169695Skan#define CHUNK_SIZE (4096 - 32) 78169695Skan 79169695Skan/* A request for this amount or more is just passed through to malloc. */ 80169695Skan 81169695Skan#define BIG_REQUEST (512) 82169695Skan 83169695Skan/* Create an objalloc structure. */ 84169695Skan 85169695Skanstruct objalloc * 86169695Skanobjalloc_create (void) 87169695Skan{ 88169695Skan struct objalloc *ret; 89169695Skan struct objalloc_chunk *chunk; 90169695Skan 91169695Skan ret = (struct objalloc *) malloc (sizeof *ret); 92169695Skan if (ret == NULL) 93169695Skan return NULL; 94169695Skan 95169695Skan ret->chunks = (PTR) malloc (CHUNK_SIZE); 96169695Skan if (ret->chunks == NULL) 97169695Skan { 98169695Skan free (ret); 99169695Skan return NULL; 100169695Skan } 101169695Skan 102169695Skan chunk = (struct objalloc_chunk *) ret->chunks; 103169695Skan chunk->next = NULL; 104169695Skan chunk->current_ptr = NULL; 105169695Skan 106169695Skan ret->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE; 107169695Skan ret->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE; 108169695Skan 109169695Skan return ret; 110169695Skan} 111169695Skan 112169695Skan/* Allocate space from an objalloc structure. */ 113169695Skan 114169695SkanPTR 115301976Spfg_objalloc_alloc (struct objalloc *o, unsigned long original_len) 116169695Skan{ 117301976Spfg unsigned long len = original_len; 118301976Spfg 119169695Skan /* We avoid confusion from zero sized objects by always allocating 120169695Skan at least 1 byte. */ 121169695Skan if (len == 0) 122169695Skan len = 1; 123169695Skan 124169695Skan len = (len + OBJALLOC_ALIGN - 1) &~ (OBJALLOC_ALIGN - 1); 125169695Skan 126301976Spfg /* CVE-2012-3509: Check for overflow in the alignment operation above 127301976Spfg * and then malloc argument below. */ 128301976Spfg if (len + CHUNK_HEADER_SIZE < original_len) 129301976Spfg return NULL; 130301976Spfg 131169695Skan if (len <= o->current_space) 132169695Skan { 133169695Skan o->current_ptr += len; 134169695Skan o->current_space -= len; 135169695Skan return (PTR) (o->current_ptr - len); 136169695Skan } 137169695Skan 138169695Skan if (len >= BIG_REQUEST) 139169695Skan { 140169695Skan char *ret; 141169695Skan struct objalloc_chunk *chunk; 142169695Skan 143169695Skan ret = (char *) malloc (CHUNK_HEADER_SIZE + len); 144169695Skan if (ret == NULL) 145169695Skan return NULL; 146169695Skan 147169695Skan chunk = (struct objalloc_chunk *) ret; 148169695Skan chunk->next = (struct objalloc_chunk *) o->chunks; 149169695Skan chunk->current_ptr = o->current_ptr; 150169695Skan 151169695Skan o->chunks = (PTR) chunk; 152169695Skan 153169695Skan return (PTR) (ret + CHUNK_HEADER_SIZE); 154169695Skan } 155169695Skan else 156169695Skan { 157169695Skan struct objalloc_chunk *chunk; 158169695Skan 159169695Skan chunk = (struct objalloc_chunk *) malloc (CHUNK_SIZE); 160169695Skan if (chunk == NULL) 161169695Skan return NULL; 162169695Skan chunk->next = (struct objalloc_chunk *) o->chunks; 163169695Skan chunk->current_ptr = NULL; 164169695Skan 165169695Skan o->current_ptr = (char *) chunk + CHUNK_HEADER_SIZE; 166169695Skan o->current_space = CHUNK_SIZE - CHUNK_HEADER_SIZE; 167169695Skan 168169695Skan o->chunks = (PTR) chunk; 169169695Skan 170169695Skan return objalloc_alloc (o, len); 171169695Skan } 172169695Skan} 173169695Skan 174169695Skan/* Free an entire objalloc structure. */ 175169695Skan 176169695Skanvoid 177169695Skanobjalloc_free (struct objalloc *o) 178169695Skan{ 179169695Skan struct objalloc_chunk *l; 180169695Skan 181169695Skan l = (struct objalloc_chunk *) o->chunks; 182169695Skan while (l != NULL) 183169695Skan { 184169695Skan struct objalloc_chunk *next; 185169695Skan 186169695Skan next = l->next; 187169695Skan free (l); 188169695Skan l = next; 189169695Skan } 190169695Skan 191169695Skan free (o); 192169695Skan} 193169695Skan 194169695Skan/* Free a block from an objalloc structure. This also frees all more 195169695Skan recently allocated blocks. */ 196169695Skan 197169695Skanvoid 198169695Skanobjalloc_free_block (struct objalloc *o, PTR block) 199169695Skan{ 200169695Skan struct objalloc_chunk *p, *small; 201169695Skan char *b = (char *) block; 202169695Skan 203169695Skan /* First set P to the chunk which contains the block we are freeing, 204169695Skan and set Q to the last small object chunk we see before P. */ 205169695Skan small = NULL; 206169695Skan for (p = (struct objalloc_chunk *) o->chunks; p != NULL; p = p->next) 207169695Skan { 208169695Skan if (p->current_ptr == NULL) 209169695Skan { 210169695Skan if (b > (char *) p && b < (char *) p + CHUNK_SIZE) 211169695Skan break; 212169695Skan small = p; 213169695Skan } 214169695Skan else 215169695Skan { 216169695Skan if (b == (char *) p + CHUNK_HEADER_SIZE) 217169695Skan break; 218169695Skan } 219169695Skan } 220169695Skan 221169695Skan /* If we can't find the chunk, the caller has made a mistake. */ 222169695Skan if (p == NULL) 223169695Skan abort (); 224169695Skan 225169695Skan if (p->current_ptr == NULL) 226169695Skan { 227169695Skan struct objalloc_chunk *q; 228169695Skan struct objalloc_chunk *first; 229169695Skan 230169695Skan /* The block is in a chunk containing small objects. We can 231169695Skan free every chunk through SMALL, because they have certainly 232169695Skan been allocated more recently. After SMALL, we will not see 233169695Skan any chunks containing small objects; we can free any big 234169695Skan chunk if the current_ptr is greater than or equal to B. We 235169695Skan can then reset the new current_ptr to B. */ 236169695Skan 237169695Skan first = NULL; 238169695Skan q = (struct objalloc_chunk *) o->chunks; 239169695Skan while (q != p) 240169695Skan { 241169695Skan struct objalloc_chunk *next; 242169695Skan 243169695Skan next = q->next; 244169695Skan if (small != NULL) 245169695Skan { 246169695Skan if (small == q) 247169695Skan small = NULL; 248169695Skan free (q); 249169695Skan } 250169695Skan else if (q->current_ptr > b) 251169695Skan free (q); 252169695Skan else if (first == NULL) 253169695Skan first = q; 254169695Skan 255169695Skan q = next; 256169695Skan } 257169695Skan 258169695Skan if (first == NULL) 259169695Skan first = p; 260169695Skan o->chunks = (PTR) first; 261169695Skan 262169695Skan /* Now start allocating from this small block again. */ 263169695Skan o->current_ptr = b; 264169695Skan o->current_space = ((char *) p + CHUNK_SIZE) - b; 265169695Skan } 266169695Skan else 267169695Skan { 268169695Skan struct objalloc_chunk *q; 269169695Skan char *current_ptr; 270169695Skan 271169695Skan /* This block is in a large chunk by itself. We can free 272169695Skan everything on the list up to and including this block. We 273169695Skan then start allocating from the next chunk containing small 274169695Skan objects, setting current_ptr from the value stored with the 275169695Skan large chunk we are freeing. */ 276169695Skan 277169695Skan current_ptr = p->current_ptr; 278169695Skan p = p->next; 279169695Skan 280169695Skan q = (struct objalloc_chunk *) o->chunks; 281169695Skan while (q != p) 282169695Skan { 283169695Skan struct objalloc_chunk *next; 284169695Skan 285169695Skan next = q->next; 286169695Skan free (q); 287169695Skan q = next; 288169695Skan } 289169695Skan 290169695Skan o->chunks = (PTR) p; 291169695Skan 292169695Skan while (p->current_ptr != NULL) 293169695Skan p = p->next; 294169695Skan 295169695Skan o->current_ptr = current_ptr; 296169695Skan o->current_space = ((char *) p + CHUNK_SIZE) - current_ptr; 297169695Skan } 298169695Skan} 299