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