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
| 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 LIMITED
27 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
29 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 * POSSIBILITY OF SUCH DAMAGE.
| 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
83struct regional*
84regional_create_custom(size_t size)
85{
86 struct regional* r = (struct regional*)malloc(size);
87 log_assert(sizeof(struct regional) <= size);
88 if(!r) return NULL;
89 r->first_size = size;
90 regional_init(r);
91 return r;
92}
93
94void
95regional_free_all(struct regional *r)
96{
97 char* p = r->next, *np;
98 while(p) {
99 np = *(char**)p;
100 free(p);
101 p = np;
102 }
103 p = r->large_list;
104 while(p) {
105 np = *(char**)p;
106 free(p);
107 p = np;
108 }
109 regional_init(r);
110}
111
112void
113regional_destroy(struct regional *r)
114{
115 if(!r) return;
116 regional_free_all(r);
117 free(r);
118}
119
120void *
121regional_alloc(struct regional *r, size_t size)
122{
123 size_t a = ALIGN_UP(size, ALIGNMENT);
124 void *s;
125 /* large objects */
126 if(a > REGIONAL_LARGE_OBJECT_SIZE) {
127 s = malloc(ALIGNMENT + size);
128 if(!s) return NULL;
129 r->total_large += ALIGNMENT+size;
130 *(char**)s = r->large_list;
131 r->large_list = (char*)s;
132 return (char*)s+ALIGNMENT;
133 }
134 /* create a new chunk */
135 if(a > r->available) {
136 s = malloc(REGIONAL_CHUNK_SIZE);
137 if(!s) return NULL;
138 *(char**)s = r->next;
139 r->next = (char*)s;
140 r->data = (char*)s + ALIGNMENT;
141 r->available = REGIONAL_CHUNK_SIZE - ALIGNMENT;
142 }
143 /* put in this chunk */
144 r->available -= a;
145 s = r->data;
146 r->data += a;
147 return s;
148}
149
150void *
151regional_alloc_init(struct regional* r, const void *init, size_t size)
152{
153 void *s = regional_alloc(r, size);
154 if(!s) return NULL;
155 memcpy(s, init, size);
156 return s;
157}
158
159void *
160regional_alloc_zero(struct regional *r, size_t size)
161{
162 void *s = regional_alloc(r, size);
163 if(!s) return NULL;
164 memset(s, 0, size);
165 return s;
166}
167
168char *
169regional_strdup(struct regional *r, const char *string)
170{
171 return (char*)regional_alloc_init(r, string, strlen(string)+1);
172}
173
174/**
175 * reasonably slow, but stats and get_mem are not supposed to be fast
176 * count the number of chunks in use
177 */
178static size_t
179count_chunks(struct regional* r)
180{
181 size_t c = 1;
182 char* p = r->next;
183 while(p) {
184 c++;
185 p = *(char**)p;
186 }
187 return c;
188}
189
190/**
191 * also reasonably slow, counts the number of large objects
192 */
193static size_t
194count_large(struct regional* r)
195{
196 size_t c = 0;
197 char* p = r->large_list;
198 while(p) {
199 c++;
200 p = *(char**)p;
201 }
202 return c;
203}
204
205void
206regional_log_stats(struct regional *r)
207{
208 /* some basic assertions put here (non time critical code) */
209 log_assert(ALIGNMENT >= sizeof(char*));
210 log_assert(REGIONAL_CHUNK_SIZE > ALIGNMENT);
211 log_assert(REGIONAL_CHUNK_SIZE-ALIGNMENT > REGIONAL_LARGE_OBJECT_SIZE);
212 log_assert(REGIONAL_CHUNK_SIZE >= sizeof(struct regional));
213 /* debug print */
214 log_info("regional %u chunks, %u large",
215 (unsigned)count_chunks(r), (unsigned)count_large(r));
216}
217
218size_t
219regional_get_mem(struct regional* r)
220{
221 return r->first_size + (count_chunks(r)-1)*REGIONAL_CHUNK_SIZE
222 + r->total_large;
223}
| 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
83struct regional*
84regional_create_custom(size_t size)
85{
86 struct regional* r = (struct regional*)malloc(size);
87 log_assert(sizeof(struct regional) <= size);
88 if(!r) return NULL;
89 r->first_size = size;
90 regional_init(r);
91 return r;
92}
93
94void
95regional_free_all(struct regional *r)
96{
97 char* p = r->next, *np;
98 while(p) {
99 np = *(char**)p;
100 free(p);
101 p = np;
102 }
103 p = r->large_list;
104 while(p) {
105 np = *(char**)p;
106 free(p);
107 p = np;
108 }
109 regional_init(r);
110}
111
112void
113regional_destroy(struct regional *r)
114{
115 if(!r) return;
116 regional_free_all(r);
117 free(r);
118}
119
120void *
121regional_alloc(struct regional *r, size_t size)
122{
123 size_t a = ALIGN_UP(size, ALIGNMENT);
124 void *s;
125 /* large objects */
126 if(a > REGIONAL_LARGE_OBJECT_SIZE) {
127 s = malloc(ALIGNMENT + size);
128 if(!s) return NULL;
129 r->total_large += ALIGNMENT+size;
130 *(char**)s = r->large_list;
131 r->large_list = (char*)s;
132 return (char*)s+ALIGNMENT;
133 }
134 /* create a new chunk */
135 if(a > r->available) {
136 s = malloc(REGIONAL_CHUNK_SIZE);
137 if(!s) return NULL;
138 *(char**)s = r->next;
139 r->next = (char*)s;
140 r->data = (char*)s + ALIGNMENT;
141 r->available = REGIONAL_CHUNK_SIZE - ALIGNMENT;
142 }
143 /* put in this chunk */
144 r->available -= a;
145 s = r->data;
146 r->data += a;
147 return s;
148}
149
150void *
151regional_alloc_init(struct regional* r, const void *init, size_t size)
152{
153 void *s = regional_alloc(r, size);
154 if(!s) return NULL;
155 memcpy(s, init, size);
156 return s;
157}
158
159void *
160regional_alloc_zero(struct regional *r, size_t size)
161{
162 void *s = regional_alloc(r, size);
163 if(!s) return NULL;
164 memset(s, 0, size);
165 return s;
166}
167
168char *
169regional_strdup(struct regional *r, const char *string)
170{
171 return (char*)regional_alloc_init(r, string, strlen(string)+1);
172}
173
174/**
175 * reasonably slow, but stats and get_mem are not supposed to be fast
176 * count the number of chunks in use
177 */
178static size_t
179count_chunks(struct regional* r)
180{
181 size_t c = 1;
182 char* p = r->next;
183 while(p) {
184 c++;
185 p = *(char**)p;
186 }
187 return c;
188}
189
190/**
191 * also reasonably slow, counts the number of large objects
192 */
193static size_t
194count_large(struct regional* r)
195{
196 size_t c = 0;
197 char* p = r->large_list;
198 while(p) {
199 c++;
200 p = *(char**)p;
201 }
202 return c;
203}
204
205void
206regional_log_stats(struct regional *r)
207{
208 /* some basic assertions put here (non time critical code) */
209 log_assert(ALIGNMENT >= sizeof(char*));
210 log_assert(REGIONAL_CHUNK_SIZE > ALIGNMENT);
211 log_assert(REGIONAL_CHUNK_SIZE-ALIGNMENT > REGIONAL_LARGE_OBJECT_SIZE);
212 log_assert(REGIONAL_CHUNK_SIZE >= sizeof(struct regional));
213 /* debug print */
214 log_info("regional %u chunks, %u large",
215 (unsigned)count_chunks(r), (unsigned)count_large(r));
216}
217
218size_t
219regional_get_mem(struct regional* r)
220{
221 return r->first_size + (count_chunks(r)-1)*REGIONAL_CHUNK_SIZE
222 + r->total_large;
223}
|