1/*
2 * regional.c -- region based memory allocator.
3 *
4 * Copyright (c) 2001-2006, NLnet Labs. All rights reserved.
5 *
6 * Copyright (c) 2007, NLnet Labs. All rights reserved.
7 *
8 * This software is open source.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 *
14 * Redistributions of source code must retain the above copyright notice,
15 * this list of conditions and the following disclaimer.
16 *
17 * Redistributions in binary form must reproduce the above copyright notice,
18 * this list of conditions and the following disclaimer in the documentation
19 * and/or other materials provided with the distribution.
20 *
21 * Neither the name of the NLNET LABS nor the names of its contributors may
22 * be used to endorse or promote products derived from this software without
23 * specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
28 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
29 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
30 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
31 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 */
37
38/**
39 * \file
40 * Regional allocator. Allocates small portions of of larger chunks.
41 */
42
43#include "config.h"
44#include "util/log.h"
45#include "util/regional.h"
46
47#ifdef ALIGNMENT
48#  undef ALIGNMENT
49#endif
50/** increase size until it fits alignment of s bytes */
51#define ALIGN_UP(x, s)     (((x) + s - 1) & (~(s - 1)))
52/** what size to align on; make sure a char* fits in it. */
53#define ALIGNMENT          (sizeof(uint64_t))
54
55/** Default reasonable size for chunks */
56#define REGIONAL_CHUNK_SIZE         8192
57#ifdef UNBOUND_ALLOC_NONREGIONAL
58/** All objects allocated outside of chunks, for debug */
59#define REGIONAL_LARGE_OBJECT_SIZE  0
60#else
61/** Default size for large objects - allocated outside of chunks. */
62#define REGIONAL_LARGE_OBJECT_SIZE  2048
63#endif
64
65struct regional*
66regional_create(void)
67{
68	return regional_create_custom(REGIONAL_CHUNK_SIZE);
69}
70
71/** init regional struct with first block */
72static void
73regional_init(struct regional* r)
74{
75	size_t a = ALIGN_UP(sizeof(struct regional), ALIGNMENT);
76	r->data = (char*)r + a;
77	r->available = r->first_size - a;
78	r->next = NULL;
79	r->large_list = NULL;
80	r->total_large = 0;
81}
82
83/**
84 * Create a new region, with custom first block and large-object sizes.
85 * @param size: length of first block.
86 * @param large_object_size: outside of chunk allocation threshold.
87 * @return: newly allocated regional.
88 */
89static struct regional*
90regional_create_custom_large_object(size_t size, size_t large_object_size)
91{
92	struct regional* r;
93	size = ALIGN_UP(size, ALIGNMENT);
94	r = (struct regional*)malloc(size);
95	log_assert(sizeof(struct regional) <= size);
96	if(!r) return NULL;
97	r->first_size = size;
98	r->large_object_size = large_object_size;
99	regional_init(r);
100	return r;
101}
102
103struct regional*
104regional_create_custom(size_t size)
105{
106	if(size < sizeof(struct regional))
107		size = sizeof(struct regional);
108	return regional_create_custom_large_object(size,
109		REGIONAL_LARGE_OBJECT_SIZE);
110}
111
112struct regional*
113regional_create_nochunk(size_t size)
114{
115	return regional_create_custom_large_object(size, 0);
116}
117
118void
119regional_free_all(struct regional *r)
120{
121	char* p = r->next, *np;
122	while(p) {
123		np = *(char**)p;
124		free(p);
125		p = np;
126	}
127	p = r->large_list;
128	while(p) {
129		np = *(char**)p;
130		free(p);
131		p = np;
132	}
133	regional_init(r);
134}
135
136void
137regional_destroy(struct regional *r)
138{
139	if(!r) return;
140	regional_free_all(r);
141	free(r);
142}
143
144void *
145regional_alloc(struct regional *r, size_t size)
146{
147	size_t a;
148	void *s;
149	if(
150#if SIZEOF_SIZE_T == 8
151		(unsigned long long)size >= 0xffffffffffffff00ULL
152#else
153		(unsigned)size >= (unsigned)0xffffff00UL
154#endif
155		)
156		return NULL; /* protect against integer overflow in
157			malloc and ALIGN_UP */
158	a = ALIGN_UP(size, ALIGNMENT);
159	/* large objects */
160	if(a > r->large_object_size) {
161		s = malloc(ALIGNMENT + size);
162		if(!s) return NULL;
163		r->total_large += ALIGNMENT+size;
164		*(char**)s = r->large_list;
165		r->large_list = (char*)s;
166		return (char*)s+ALIGNMENT;
167	}
168	/* create a new chunk */
169	if(a > r->available) {
170		s = malloc(REGIONAL_CHUNK_SIZE);
171		if(!s) return NULL;
172		*(char**)s = r->next;
173		r->next = (char*)s;
174		r->data = (char*)s + ALIGNMENT;
175		r->available = REGIONAL_CHUNK_SIZE - ALIGNMENT;
176	}
177	/* put in this chunk */
178	r->available -= a;
179	s = r->data;
180	r->data += a;
181	return s;
182}
183
184void *
185regional_alloc_init(struct regional* r, const void *init, size_t size)
186{
187	void *s = regional_alloc(r, size);
188	if(!s) return NULL;
189	memmove(s, init, size);
190	return s;
191}
192
193void *
194regional_alloc_zero(struct regional *r, size_t size)
195{
196	void *s = regional_alloc(r, size);
197	if(!s) return NULL;
198	memset(s, 0, size);
199	return s;
200}
201
202char *
203regional_strdup(struct regional *r, const char *string)
204{
205	return (char*)regional_alloc_init(r, string, strlen(string)+1);
206}
207
208/**
209 * reasonably slow, but stats and get_mem are not supposed to be fast
210 * count the number of chunks in use
211 */
212static size_t
213count_chunks(struct regional* r)
214{
215	size_t c = 1;
216	char* p = r->next;
217	while(p) {
218		c++;
219		p = *(char**)p;
220	}
221	return c;
222}
223
224/**
225 * also reasonably slow, counts the number of large objects
226 */
227static size_t
228count_large(struct regional* r)
229{
230	size_t c = 0;
231	char* p = r->large_list;
232	while(p) {
233		c++;
234		p = *(char**)p;
235	}
236	return c;
237}
238
239void
240regional_log_stats(struct regional *r)
241{
242	/* some basic assertions put here (non time critical code) */
243	log_assert(ALIGNMENT >= sizeof(char*));
244	log_assert(REGIONAL_CHUNK_SIZE > ALIGNMENT);
245	log_assert(REGIONAL_CHUNK_SIZE-ALIGNMENT > r->large_object_size);
246	log_assert(REGIONAL_CHUNK_SIZE >= sizeof(struct regional));
247	/* debug print */
248	log_info("regional %u chunks, %u large",
249		(unsigned)count_chunks(r), (unsigned)count_large(r));
250}
251
252size_t
253regional_get_mem(struct regional* r)
254{
255	return r->first_size + (count_chunks(r)-1)*REGIONAL_CHUNK_SIZE
256		+ r->total_large;
257}
258