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
39typedef struct cleanup cleanup_type;
40struct cleanup
41{
42	void (*action)(void *);
43	void *data;
44};
45
46struct recycle_elem {
47	struct recycle_elem* next;
48};
49
50struct large_elem {
51	struct large_elem* next;
52	struct large_elem* prev;
53};
54
55struct 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
88static region_type *
89alloc_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
127region_type *
128region_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
147region_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
184void
185region_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
210size_t
211region_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
236void
237region_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
251void *
252region_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
330void *
331region_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
339void *
340region_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
348void *
349region_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
360void *
361region_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
371void *
372region_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
382void
383region_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
425char *
426region_strdup(region_type *region, const char *string)
427{
428	return (char *) region_alloc_init(region, string, strlen(string) + 1);
429}
430
431void
432region_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
482void
483region_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
510size_t region_get_recycle_size(region_type* region)
511{
512	return region->recycle_size;
513}
514
515size_t region_get_mem(region_type* region)
516{
517	return region->total_allocated;
518}
519
520size_t region_get_mem_unused(region_type* region)
521{
522	return region->unused_space;
523}
524
525/* debug routine */
526void
527region_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