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
65 struct regional*
regional_create(void)66 regional_create(void)
67 {
68 return regional_create_custom(REGIONAL_CHUNK_SIZE);
69 }
70
71 /** init regional struct with first block */
72 static void
regional_init(struct regional * r)73 regional_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 */
89 static struct regional*
regional_create_custom_large_object(size_t size,size_t large_object_size)90 regional_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
103 struct regional*
regional_create_custom(size_t size)104 regional_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
112 struct regional*
regional_create_nochunk(size_t size)113 regional_create_nochunk(size_t size)
114 {
115 return regional_create_custom_large_object(size, 0);
116 }
117
118 void
regional_free_all(struct regional * r)119 regional_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
136 void
regional_destroy(struct regional * r)137 regional_destroy(struct regional *r)
138 {
139 if(!r) return;
140 regional_free_all(r);
141 free(r);
142 }
143
144 void *
regional_alloc(struct regional * r,size_t size)145 regional_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
184 void *
regional_alloc_init(struct regional * r,const void * init,size_t size)185 regional_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 memcpy(s, init, size);
190 return s;
191 }
192
193 void *
regional_alloc_zero(struct regional * r,size_t size)194 regional_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
202 char *
regional_strdup(struct regional * r,const char * string)203 regional_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 */
212 static size_t
count_chunks(struct regional * r)213 count_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 */
227 static size_t
count_large(struct regional * r)228 count_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
239 void
regional_log_stats(struct regional * r)240 regional_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
252 size_t
regional_get_mem(struct regional * r)253 regional_get_mem(struct regional* r)
254 {
255 return r->first_size + (count_chunks(r)-1)*REGIONAL_CHUNK_SIZE
256 + r->total_large;
257 }
258