1 /*
2 * region-allocator.c -- region based memory allocator.
3 *
4 * Copyright (c) 2001-2006, NLnet Labs. All rights reserved.
5 *
6 * See LICENSE for the license.
7 *
8 */
9
10 #include "config.h"
11
12 #include <assert.h>
13 #include <stdlib.h>
14 #include <string.h>
15 #include <limits.h>
16
17 #include "region-allocator.h"
18 #include "util.h"
19
20 /** This value is enough so that x*y does not overflow if both < than this */
21 #define REGION_NO_OVERFLOW ((size_t)1 << (sizeof(size_t) * 4))
22
23 #ifdef ALIGNMENT
24 #undef ALIGNMENT
25 #endif
26 #ifndef PACKED_STRUCTS
27 #define REGION_ALIGN_UP(x, s) (((x) + s - 1) & (~(s - 1)))
28 #if SIZEOF_OFF_T > SIZEOF_VOIDP
29 #define ALIGNMENT (sizeof(off_t))
30 #else
31 #define ALIGNMENT (sizeof(void *))
32 #endif
33 #else
34 #define REGION_ALIGN_UP(x, s) ((x)<SIZEOF_VOIDP?SIZEOF_VOIDP:(x))
35 #define ALIGNMENT 1
36 #endif /* PACKED_STRUCTS */
37 /* #define CHECK_DOUBLE_FREE 0 */ /* set to 1 to perform expensive check for double recycle() */
38
39 typedef struct cleanup cleanup_type;
40 struct cleanup
41 {
42 void (*action)(void *);
43 void *data;
44 };
45
46 struct recycle_elem {
47 struct recycle_elem* next;
48 };
49
50 struct large_elem {
51 struct large_elem* next;
52 struct large_elem* prev;
53 };
54
55 struct region
56 {
57 size_t total_allocated;
58 size_t small_objects;
59 size_t large_objects;
60 size_t chunk_count;
61 size_t unused_space; /* Unused space due to alignment, etc. */
62
63 size_t allocated;
64 char *initial_data;
65 char *data;
66
67 void *(*allocator)(size_t);
68 void (*deallocator)(void *);
69
70 size_t maximum_cleanup_count;
71 size_t cleanup_count;
72 cleanup_type *cleanups;
73 struct large_elem* large_list;
74
75 size_t chunk_size;
76 size_t large_object_size;
77
78 /* if not NULL recycling is enabled.
79 * It is an array of linked lists of parts held for recycle.
80 * The parts are all pointers to within the allocated chunks.
81 * Array [i] points to elements of size i. */
82 struct recycle_elem** recycle_bin;
83 /* amount of memory in recycle storage */
84 size_t recycle_size;
85 };
86
87
88 static region_type *
alloc_region_base(void * (* allocator)(size_t size),void (* deallocator)(void *),size_t initial_cleanup_count)89 alloc_region_base(void *(*allocator)(size_t size),
90 void (*deallocator)(void *),
91 size_t initial_cleanup_count)
92 {
93 region_type *result = (region_type *) allocator(sizeof(region_type));
94 if (!result) return NULL;
95
96 result->total_allocated = 0;
97 result->small_objects = 0;
98 result->large_objects = 0;
99 result->chunk_count = 1;
100 result->unused_space = 0;
101 result->recycle_bin = NULL;
102 result->recycle_size = 0;
103 result->large_list = NULL;
104
105 result->allocated = 0;
106 result->data = NULL;
107 result->initial_data = NULL;
108
109 result->allocator = allocator;
110 result->deallocator = deallocator;
111
112 assert(initial_cleanup_count > 0);
113 result->maximum_cleanup_count = initial_cleanup_count;
114 result->cleanup_count = 0;
115 result->cleanups = (cleanup_type *) allocator(
116 result->maximum_cleanup_count * sizeof(cleanup_type));
117 if (!result->cleanups) {
118 deallocator(result);
119 return NULL;
120 }
121
122 result->chunk_size = DEFAULT_CHUNK_SIZE;
123 result->large_object_size = DEFAULT_LARGE_OBJECT_SIZE;
124 return result;
125 }
126
127 region_type *
region_create(void * (* allocator)(size_t size),void (* deallocator)(void *))128 region_create(void *(*allocator)(size_t size),
129 void (*deallocator)(void *))
130 {
131 region_type* result = alloc_region_base(allocator, deallocator,
132 DEFAULT_INITIAL_CLEANUP_SIZE);
133 if(!result)
134 return NULL;
135 result->data = (char *) allocator(result->chunk_size);
136 if (!result->data) {
137 deallocator(result->cleanups);
138 deallocator(result);
139 return NULL;
140 }
141 result->initial_data = result->data;
142
143 return result;
144 }
145
146
region_create_custom(void * (* allocator)(size_t),void (* deallocator)(void *),size_t chunk_size,size_t large_object_size,size_t initial_cleanup_size,int recycle)147 region_type *region_create_custom(void *(*allocator)(size_t),
148 void (*deallocator)(void *),
149 size_t chunk_size,
150 size_t large_object_size,
151 size_t initial_cleanup_size,
152 int recycle)
153 {
154 region_type* result = alloc_region_base(allocator, deallocator,
155 initial_cleanup_size);
156 if(!result)
157 return NULL;
158 assert(large_object_size <= chunk_size);
159 result->chunk_size = chunk_size;
160 result->large_object_size = large_object_size;
161 if(result->chunk_size > 0) {
162 result->data = (char *) allocator(result->chunk_size);
163 if (!result->data) {
164 deallocator(result->cleanups);
165 deallocator(result);
166 return NULL;
167 }
168 result->initial_data = result->data;
169 }
170 if(recycle) {
171 result->recycle_bin = allocator(sizeof(struct recycle_elem*)
172 * result->large_object_size);
173 if(!result->recycle_bin) {
174 region_destroy(result);
175 return NULL;
176 }
177 memset(result->recycle_bin, 0, sizeof(struct recycle_elem*)
178 * result->large_object_size);
179 }
180 return result;
181 }
182
183
184 void
region_destroy(region_type * region)185 region_destroy(region_type *region)
186 {
187 void (*deallocator)(void *);
188 if (!region)
189 return;
190
191 deallocator = region->deallocator;
192
193 region_free_all(region);
194 deallocator(region->cleanups);
195 deallocator(region->initial_data);
196 if(region->recycle_bin)
197 deallocator(region->recycle_bin);
198 if(region->large_list) {
199 struct large_elem* p = region->large_list, *np;
200 while(p) {
201 np = p->next;
202 deallocator(p);
203 p = np;
204 }
205 }
206 deallocator(region);
207 }
208
209
210 size_t
region_add_cleanup(region_type * region,void (* action)(void *),void * data)211 region_add_cleanup(region_type *region, void (*action)(void *), void *data)
212 {
213 assert(action);
214
215 if (region->cleanup_count >= region->maximum_cleanup_count) {
216 cleanup_type *cleanups = (cleanup_type *) region->allocator(
217 2 * region->maximum_cleanup_count * sizeof(cleanup_type));
218 if (!cleanups)
219 return 0;
220
221 memcpy(cleanups, region->cleanups,
222 region->cleanup_count * sizeof(cleanup_type));
223 region->deallocator(region->cleanups);
224
225 region->cleanups = cleanups;
226 region->maximum_cleanup_count *= 2;
227 }
228
229 region->cleanups[region->cleanup_count].action = action;
230 region->cleanups[region->cleanup_count].data = data;
231
232 ++region->cleanup_count;
233 return region->cleanup_count;
234 }
235
236 void
region_remove_cleanup(region_type * region,void (* action)(void *),void * data)237 region_remove_cleanup(region_type *region, void (*action)(void *), void *data)
238 {
239 size_t i;
240 for(i=0; i<region->cleanup_count; i++) {
241 if(region->cleanups[i].action == action &&
242 region->cleanups[i].data == data) {
243 region->cleanup_count--;
244 region->cleanups[i] =
245 region->cleanups[region->cleanup_count];
246 return;
247 }
248 }
249 }
250
251 void *
region_alloc(region_type * region,size_t size)252 region_alloc(region_type *region, size_t size)
253 {
254 size_t aligned_size;
255 void *result;
256
257 if (size == 0) {
258 size = 1;
259 }
260 aligned_size = REGION_ALIGN_UP(size, ALIGNMENT);
261
262 if (aligned_size >= region->large_object_size) {
263 result = region->allocator(size + sizeof(struct large_elem));
264 if (!result)
265 return NULL;
266 ((struct large_elem*)result)->prev = NULL;
267 ((struct large_elem*)result)->next = region->large_list;
268 if(region->large_list)
269 region->large_list->prev = (struct large_elem*)result;
270 region->large_list = (struct large_elem*)result;
271
272 region->total_allocated += size;
273 ++region->large_objects;
274
275 return (char *)result + sizeof(struct large_elem);
276 }
277
278 if (region->recycle_bin && region->recycle_bin[aligned_size]) {
279 result = (void*)region->recycle_bin[aligned_size];
280 region->recycle_bin[aligned_size] = region->recycle_bin[aligned_size]->next;
281 region->recycle_size -= aligned_size;
282 region->unused_space += aligned_size - size;
283 return result;
284 }
285
286 if (region->allocated + aligned_size > region->chunk_size) {
287 void *chunk = region->allocator(region->chunk_size);
288 size_t wasted;
289 if (!chunk)
290 return NULL;
291
292 wasted = (region->chunk_size - region->allocated) & (~(ALIGNMENT-1));
293 if(
294 #ifndef PACKED_STRUCTS
295 wasted >= ALIGNMENT
296 #else
297 wasted >= SIZEOF_VOIDP
298 #endif
299 ) {
300 /* put wasted part in recycle bin for later use */
301 region->total_allocated += wasted;
302 ++region->small_objects;
303 region_recycle(region, region->data+region->allocated, wasted);
304 region->allocated += wasted;
305 }
306 ++region->chunk_count;
307 region->unused_space += region->chunk_size - region->allocated;
308
309 if(!region_add_cleanup(region, region->deallocator, chunk)) {
310 region->deallocator(chunk);
311 region->chunk_count--;
312 region->unused_space -=
313 region->chunk_size - region->allocated;
314 return NULL;
315 }
316 region->allocated = 0;
317 region->data = (char *) chunk;
318 }
319
320 result = region->data + region->allocated;
321 region->allocated += aligned_size;
322
323 region->total_allocated += aligned_size;
324 region->unused_space += aligned_size - size;
325 ++region->small_objects;
326
327 return result;
328 }
329
330 void *
region_alloc_init(region_type * region,const void * init,size_t size)331 region_alloc_init(region_type *region, const void *init, size_t size)
332 {
333 void *result = region_alloc(region, size);
334 if (!result) return NULL;
335 memcpy(result, init, size);
336 return result;
337 }
338
339 void *
region_alloc_zero(region_type * region,size_t size)340 region_alloc_zero(region_type *region, size_t size)
341 {
342 void *result = region_alloc(region, size);
343 if (!result) return NULL;
344 memset(result, 0, size);
345 return result;
346 }
347
348 void *
region_alloc_array_init(region_type * region,const void * init,size_t num,size_t size)349 region_alloc_array_init(region_type *region, const void *init, size_t num,
350 size_t size)
351 {
352 if((num >= REGION_NO_OVERFLOW || size >= REGION_NO_OVERFLOW) &&
353 num > 0 && SIZE_MAX / num < size) {
354 log_msg(LOG_ERR, "region_alloc_array_init failed because of integer overflow");
355 exit(1);
356 }
357 return region_alloc_init(region, init, num*size);
358 }
359
360 void *
region_alloc_array_zero(region_type * region,size_t num,size_t size)361 region_alloc_array_zero(region_type *region, size_t num, size_t size)
362 {
363 if((num >= REGION_NO_OVERFLOW || size >= REGION_NO_OVERFLOW) &&
364 num > 0 && SIZE_MAX / num < size) {
365 log_msg(LOG_ERR, "region_alloc_array_zero failed because of integer overflow");
366 exit(1);
367 }
368 return region_alloc_zero(region, num*size);
369 }
370
371 void *
region_alloc_array(region_type * region,size_t num,size_t size)372 region_alloc_array(region_type *region, size_t num, size_t size)
373 {
374 if((num >= REGION_NO_OVERFLOW || size >= REGION_NO_OVERFLOW) &&
375 num > 0 && SIZE_MAX / num < size) {
376 log_msg(LOG_ERR, "region_alloc_array failed because of integer overflow");
377 exit(1);
378 }
379 return region_alloc(region, num*size);
380 }
381
382 void
region_free_all(region_type * region)383 region_free_all(region_type *region)
384 {
385 size_t i;
386 assert(region);
387 assert(region->cleanups);
388
389 i = region->cleanup_count;
390 while (i > 0) {
391 --i;
392 assert(region->cleanups[i].action);
393 region->cleanups[i].action(region->cleanups[i].data);
394 }
395
396 if(region->recycle_bin) {
397 memset(region->recycle_bin, 0, sizeof(struct recycle_elem*)
398 * region->large_object_size);
399 region->recycle_size = 0;
400 }
401
402 if(region->large_list) {
403 struct large_elem* p = region->large_list, *np;
404 void (*deallocator)(void *) = region->deallocator;
405 while(p) {
406 np = p->next;
407 deallocator(p);
408 p = np;
409 }
410 region->large_list = NULL;
411 }
412
413 region->data = region->initial_data;
414 region->cleanup_count = 0;
415 region->allocated = 0;
416
417 region->total_allocated = 0;
418 region->small_objects = 0;
419 region->large_objects = 0;
420 region->chunk_count = 1;
421 region->unused_space = 0;
422 }
423
424
425 char *
region_strdup(region_type * region,const char * string)426 region_strdup(region_type *region, const char *string)
427 {
428 return (char *) region_alloc_init(region, string, strlen(string) + 1);
429 }
430
431 void
region_recycle(region_type * region,void * block,size_t size)432 region_recycle(region_type *region, void *block, size_t size)
433 {
434 size_t aligned_size;
435
436 if(!block || !region->recycle_bin)
437 return;
438
439 if (size == 0) {
440 size = 1;
441 }
442 aligned_size = REGION_ALIGN_UP(size, ALIGNMENT);
443
444 if(aligned_size < region->large_object_size) {
445 struct recycle_elem* elem = (struct recycle_elem*)block;
446 /* we rely on the fact that ALIGNMENT is void* so the next will fit */
447 assert(aligned_size >= sizeof(struct recycle_elem));
448
449 #ifdef CHECK_DOUBLE_FREE
450 if(CHECK_DOUBLE_FREE) {
451 /* make sure the same ptr is not freed twice. */
452 struct recycle_elem *p = region->recycle_bin[aligned_size];
453 while(p) {
454 assert(p != elem);
455 p = p->next;
456 }
457 }
458 #endif
459
460 elem->next = region->recycle_bin[aligned_size];
461 region->recycle_bin[aligned_size] = elem;
462 region->recycle_size += aligned_size;
463 region->unused_space -= aligned_size - size;
464 return;
465 } else {
466 struct large_elem* l;
467
468 /* a large allocation */
469 region->total_allocated -= size;
470 --region->large_objects;
471
472 l = (struct large_elem*)((char*)block-sizeof(struct large_elem));
473 if(l->prev)
474 l->prev->next = l->next;
475 else region->large_list = l->next;
476 if(l->next)
477 l->next->prev = l->prev;
478 region->deallocator(l);
479 }
480 }
481
482 void
region_dump_stats(region_type * region,FILE * out)483 region_dump_stats(region_type *region, FILE *out)
484 {
485 fprintf(out, "%lu objects (%lu small/%lu large), %lu bytes allocated (%lu wasted) in %lu chunks, %lu cleanups, %lu in recyclebin",
486 (unsigned long) (region->small_objects + region->large_objects),
487 (unsigned long) region->small_objects,
488 (unsigned long) region->large_objects,
489 (unsigned long) region->total_allocated,
490 (unsigned long) region->unused_space,
491 (unsigned long) region->chunk_count,
492 (unsigned long) region->cleanup_count,
493 (unsigned long) region->recycle_size);
494 if(region->recycle_bin) {
495 /* print details of the recycle bin */
496 size_t i;
497 for(i=0; i<region->large_object_size; i++) {
498 size_t count = 0;
499 struct recycle_elem* el = region->recycle_bin[i];
500 while(el) {
501 count++;
502 el = el->next;
503 }
504 if(i%ALIGNMENT == 0 && i!=0)
505 fprintf(out, " %lu", (unsigned long)count);
506 }
507 }
508 }
509
region_get_recycle_size(region_type * region)510 size_t region_get_recycle_size(region_type* region)
511 {
512 return region->recycle_size;
513 }
514
region_get_mem(region_type * region)515 size_t region_get_mem(region_type* region)
516 {
517 return region->total_allocated;
518 }
519
region_get_mem_unused(region_type * region)520 size_t region_get_mem_unused(region_type* region)
521 {
522 return region->unused_space;
523 }
524
525 /* debug routine */
526 void
region_log_stats(region_type * region)527 region_log_stats(region_type *region)
528 {
529 char buf[10240], *str=buf;
530 int strl = sizeof(buf);
531 int len;
532 snprintf(str, strl, "%lu objects (%lu small/%lu large), %lu bytes allocated (%lu wasted) in %lu chunks, %lu cleanups, %lu in recyclebin",
533 (unsigned long) (region->small_objects + region->large_objects),
534 (unsigned long) region->small_objects,
535 (unsigned long) region->large_objects,
536 (unsigned long) region->total_allocated,
537 (unsigned long) region->unused_space,
538 (unsigned long) region->chunk_count,
539 (unsigned long) region->cleanup_count,
540 (unsigned long) region->recycle_size);
541 len = strlen(str);
542 str+=len;
543 strl-=len;
544 if(region->recycle_bin) {
545 /* print details of the recycle bin */
546 size_t i;
547 for(i=0; i<region->large_object_size; i++) {
548 size_t count = 0;
549 struct recycle_elem* el = region->recycle_bin[i];
550 while(el) {
551 count++;
552 el = el->next;
553 }
554 if(i%ALIGNMENT == 0 && i!=0) {
555 snprintf(str, strl, " %lu", (unsigned long)count);
556 len = strlen(str);
557 str+=len;
558 strl-=len;
559 }
560 }
561 }
562 log_msg(LOG_INFO, "memory: %s", buf);
563 }
564