Commit | Line | Data |
---|---|---|
0875b58f | 1 | /* -*-c-*- |
2 | * | |
0875b58f | 3 | * Allocation of known-size blocks |
4 | * | |
5 | * (c) 1998 Straylight/Edgeware | |
6 | */ | |
7 | ||
d4efbcd9 | 8 | /*----- Licensing notice --------------------------------------------------* |
0875b58f | 9 | * |
10 | * This file is part of the mLib utilities library. | |
11 | * | |
12 | * mLib is free software; you can redistribute it and/or modify | |
c846879c | 13 | * it under the terms of the GNU Library General Public License as |
14 | * published by the Free Software Foundation; either version 2 of the | |
15 | * License, or (at your option) any later version. | |
d4efbcd9 | 16 | * |
0875b58f | 17 | * mLib is distributed in the hope that it will be useful, |
18 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
c846879c | 20 | * GNU Library General Public License for more details. |
d4efbcd9 | 21 | * |
c846879c | 22 | * You should have received a copy of the GNU Library General Public |
0bd98442 | 23 | * License along with mLib; if not, write to the Free |
24 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, | |
25 | * MA 02111-1307, USA. | |
0875b58f | 26 | */ |
27 | ||
0875b58f | 28 | /*----- The big idea ------------------------------------------------------* |
29 | * | |
30 | * This file provides an extra layer over @malloc@. It provides fast | |
8c6d948b | 31 | * turnover for small blocks, and tries to minimize the per-block overhead. |
0875b58f | 32 | * |
33 | * To do its job, @alloc@ must place an extra restriction on you: you must | |
34 | * know the size of a block when you free it. Usually you'll have this | |
35 | * information encoded in some way either in the block or in the thing that | |
36 | * referenced it, so this isn't a hardship. | |
37 | * | |
38 | * It works fairly simply. If a request for a big block (as defined by the | |
39 | * constants below) comes in, it gets sent on to @malloc@ unmolested. For | |
40 | * small blocks, it goes straight to a `bin' -- a list containing free blocks | |
41 | * of exactly that size, or the nearest bigger size we can manage. If the | |
42 | * bin is empty, a `chunk' is allocated from @malloc@: this has enough room | |
43 | * for lots of blocks of the requested size, so it ets split up and each | |
44 | * individual small block is added to the bin list. The first block in the | |
45 | * bin list is then removed and given to the caller. In this way, @malloc@ | |
46 | * only stores its information once for lots of little blocks, so we save | |
47 | * memory. Because I know where the correct bin is just from the block size, | |
48 | * and I don't need to do any searching at all in the usual case (because the | |
49 | * list isn't empty) I can get a speed advantage too. | |
50 | * | |
51 | * This code is almost certainly not ANSI conformant, although I'm not | |
52 | * actually sure. If some kind soul would let me know how seriously I've | |
53 | * violated the standard, and whether this is easily fixable, I'd be | |
54 | * grateful. | |
55 | */ | |
56 | ||
57 | /*----- Header files ------------------------------------------------------*/ | |
58 | ||
b1a20bee MW |
59 | #include "config.h" |
60 | ||
0875b58f | 61 | /* --- ANSI headers --- */ |
62 | ||
ba1916b5 | 63 | #include <assert.h> |
0875b58f | 64 | #include <stdio.h> |
65 | #include <stdlib.h> | |
66 | #include <string.h> | |
67 | ||
b1a20bee MW |
68 | /* --- External headers --- */ |
69 | ||
70 | #ifdef HAVE_VALGRIND_VALGRIND_H | |
71 | # include <valgrind/valgrind.h> | |
72 | # include <valgrind/memcheck.h> | |
73 | # define VG(x) x | |
74 | #else | |
75 | # define VG(x) | |
76 | #endif | |
77 | ||
0875b58f | 78 | /* --- Local headers --- */ |
79 | ||
0fd574c3 | 80 | #include "arena.h" |
81 | #include "exc.h" | |
82 | #include "sub.h" | |
0875b58f | 83 | |
ba1916b5 | 84 | /*----- Configuration tweaks ----------------------------------------------*/ |
85 | ||
86 | /* #define SUBARENA_TRIVIAL */ | |
87 | ||
b1a20bee MW |
88 | #define REDZONE_SIZE (2*SUB_GRANULE) |
89 | ||
0fd574c3 | 90 | /*----- Static variables --------------------------------------------------*/ |
0875b58f | 91 | |
0fd574c3 | 92 | static size_t sizes[SUB_BINS]; |
b1a20bee MW |
93 | VG( static unsigned flags; ) |
94 | #define SF_VALGRIND 1u | |
0875b58f | 95 | |
0fd574c3 | 96 | /*----- Global variables --------------------------------------------------*/ |
0875b58f | 97 | |
0fd574c3 | 98 | subarena sub_global; |
0875b58f | 99 | |
ba1916b5 | 100 | #ifdef SUBARENA_TRIVIAL |
101 | ||
102 | typedef struct sub_link { | |
103 | struct sub_link *next; | |
104 | void *p; | |
105 | size_t sz; | |
106 | } sub_link; | |
107 | ||
b1a20bee MW |
108 | #else |
109 | ||
110 | union sub_header { | |
111 | void *next; | |
112 | union align _a; | |
113 | }; | |
114 | ||
ba1916b5 | 115 | #endif |
116 | ||
0fd574c3 | 117 | /*----- Main code ---------------------------------------------------------*/ |
0875b58f | 118 | |
0fd574c3 | 119 | /* --- @subarena_create@ --- * |
0875b58f | 120 | * |
0fd574c3 | 121 | * Arguments: @subarena *s@ = pointer to arena to initialize |
122 | * @arena *a@ = pointer to underlying arena block | |
0875b58f | 123 | * |
0fd574c3 | 124 | * Returns: --- |
125 | * | |
126 | * Use: Initialize a suballocation arena based on an underlying large | |
127 | * blocks arena. | |
0875b58f | 128 | */ |
129 | ||
0fd574c3 | 130 | void subarena_create(subarena *s, arena *a) |
131 | { | |
ba1916b5 | 132 | #ifdef SUBARENA_TRIVIAL |
133 | s->bin[0] = 0; | |
134 | #else | |
0fd574c3 | 135 | size_t i; |
b1a20bee MW |
136 | |
137 | if (!sizes[1]) sub_init(); | |
138 | for (i = 0; i < SUB_BINS; i++) s->bin[i] = 0; | |
139 | VG( VALGRIND_CREATE_MEMPOOL(s, REDZONE_SIZE, 0); ) | |
ba1916b5 | 140 | #endif |
0fd574c3 | 141 | s->a = a; |
142 | } | |
0875b58f | 143 | |
0fd574c3 | 144 | /* --- @subarena_destroy@ --- * |
0875b58f | 145 | * |
0fd574c3 | 146 | * Arguments: @subarena *s@ = pointer to arena to destroy |
147 | * | |
148 | * Returns: --- | |
149 | * | |
150 | * Use: Destroys a suballocation arena, freeing all of the memory it | |
151 | * contains back to the underlying large blocks arena. | |
0875b58f | 152 | */ |
153 | ||
0fd574c3 | 154 | void subarena_destroy(subarena *s) |
155 | { | |
ba1916b5 | 156 | #ifdef SUBARENA_TRIVIAL |
157 | ||
158 | sub_link *l, *ll; | |
159 | ||
160 | for (l = s->bin[0]; l; l = ll) { | |
161 | ll = l; | |
162 | a_free(s->a, l->p); | |
163 | a_free(s->a, l); | |
164 | } | |
165 | s->bin[0] = 0; | |
166 | ||
167 | #else | |
168 | ||
b1a20bee MW |
169 | union sub_header *p, *q; |
170 | ||
171 | for (p = s->bin[0]; p; p = q) { q = p->next; A_FREE(s->a, p); } | |
172 | VG( VALGRIND_DESTROY_MEMPOOL(s); ) | |
ba1916b5 | 173 | |
174 | #endif | |
0fd574c3 | 175 | } |
0875b58f | 176 | |
0fd574c3 | 177 | /* --- @subarena_alloc@ --- * |
0875b58f | 178 | * |
d4efbcd9 | 179 | * Arguments: @subarena *s@ = pointer to arena |
0fd574c3 | 180 | * @size_t s@ = size of chunk wanted |
0875b58f | 181 | * |
d4efbcd9 | 182 | * Returns: Pointer to a block at least as large as the one wanted. |
0875b58f | 183 | * |
d4efbcd9 | 184 | * Use: Allocates a small block of memory from the given pool. The |
0fd574c3 | 185 | * exception @EXC_NOMEM@ is raised if the underlying arena is |
186 | * full. | |
0875b58f | 187 | */ |
188 | ||
0fd574c3 | 189 | void *subarena_alloc(subarena *s, size_t sz) |
0875b58f | 190 | { |
ba1916b5 | 191 | #ifdef SUBARENA_TRIVIAL |
192 | ||
193 | sub_link *l; | |
194 | void *p; | |
195 | ||
b1a20bee | 196 | if (!s->a) subarena_create(s, arena_global); |
ba1916b5 | 197 | |
b1a20bee MW |
198 | if ((l = a_alloc(s->a, sizeof(*l))) == 0) return (0); |
199 | if ((p = a_alloc(s->a, sz)) == 0) { a_free(s->a, l); return (0); } | |
200 | l->p = p; l->sz = sz; l->next = s->bin[0]; s->bin[0] = l; | |
ba1916b5 | 201 | return (p); |
202 | ||
203 | #else | |
204 | ||
b1a20bee MW |
205 | unsigned char *p, *q; |
206 | union sub_header *h; | |
207 | size_t bin, chsz, redsz; | |
0875b58f | 208 | |
0fd574c3 | 209 | /* --- Ensure that everything is initialized --- */ |
210 | ||
b1a20bee | 211 | if (!s->a) subarena_create(s, arena_global); |
0fd574c3 | 212 | |
0875b58f | 213 | /* --- Handle oversize blocks --- */ |
214 | ||
ba1916b5 | 215 | bin = SUB_BIN(sz); |
0fd574c3 | 216 | if (bin >= SUB_BINS) { |
b1a20bee | 217 | p = A_ALLOC(s->a, sz); if (!p) THROW(EXC_NOMEM); |
0fd574c3 | 218 | return (p); |
219 | } | |
0875b58f | 220 | |
221 | /* --- If the bin is empty, find some memory --- */ | |
222 | ||
0fd574c3 | 223 | if (!s->bin[bin]) { |
b1a20bee MW |
224 | redsz = 0; VG( if (flags&SF_VALGRIND) redsz = REDZONE_SIZE; ) |
225 | chsz = SUB_BINSZ(bin) + redsz; | |
226 | h = A_ALLOC(s->a, sizes[bin]); if (!h) THROW(EXC_NOMEM); | |
227 | h->next = s->bin[0]; s->bin[0] = h; | |
228 | p = (unsigned char *)(h + 1); | |
229 | q = (unsigned char *)h + sizes[bin] - redsz - chsz; *(void **)q = 0; | |
230 | while (q > p) { q -= chsz; *(void **)q = q + chsz; } | |
231 | s->bin[bin] = q; | |
232 | VG( VALGRIND_MAKE_MEM_NOACCESS(p, sizes[bin]); ) | |
0875b58f | 233 | } |
234 | ||
235 | /* --- Extract the first block in the list --- */ | |
236 | ||
0fd574c3 | 237 | p = s->bin[bin]; |
b1a20bee MW |
238 | VG( if (flags&SF_VALGRIND) { |
239 | VALGRIND_MAKE_MEM_DEFINED(p, sizeof(void *)); | |
240 | s->bin[bin] = *(void **)p; | |
241 | VALGRIND_MEMPOOL_ALLOC(s, p, sz); | |
242 | } else ) | |
0fd574c3 | 243 | s->bin[bin] = *(void **)p; |
0875b58f | 244 | return (p); |
ba1916b5 | 245 | |
246 | #endif | |
0875b58f | 247 | } |
248 | ||
0fd574c3 | 249 | /* --- @subarena_free@ --- * |
0875b58f | 250 | * |
d4efbcd9 | 251 | * Arguments: @subarena *s@ = pointer to arena |
0fd574c3 | 252 | * @void *p@ = address of block to free |
d4efbcd9 | 253 | * @size_t s@ = size of block |
0875b58f | 254 | * |
d4efbcd9 | 255 | * Returns: --- |
0875b58f | 256 | * |
d4efbcd9 | 257 | * Use: Frees a block allocated by @subarena_alloc@. |
0875b58f | 258 | */ |
259 | ||
0fd574c3 | 260 | void subarena_free(subarena *s, void *p, size_t sz) |
0875b58f | 261 | { |
ba1916b5 | 262 | #ifdef SUBARENA_TRIVIAL |
263 | ||
264 | sub_link *lh = s->bin[0], **l, *ll; | |
265 | ||
b1a20bee MW |
266 | for (l = &lh; *l && (*l)->p != p; l = &(*l)->next) ; |
267 | ll = *l; assert(ll); assert(ll->sz == sz); | |
ba1916b5 | 268 | *l = ll->next; |
b1a20bee | 269 | a_free(s->a, ll); a_free(s->a, p); s->bin[0] = lh; |
ba1916b5 | 270 | |
271 | #else | |
272 | ||
b1a20bee | 273 | size_t bin = SUB_BIN(sz); |
0875b58f | 274 | |
275 | if (bin >= SUB_BINS) | |
0fd574c3 | 276 | A_FREE(s->a, p); |
0875b58f | 277 | else { |
b1a20bee MW |
278 | *(void **)p = s->bin[bin]; s->bin[bin] = p; |
279 | VG( if (flags&SF_VALGRIND) VALGRIND_MEMPOOL_FREE(s, p); ) | |
0875b58f | 280 | } |
ba1916b5 | 281 | |
282 | #endif | |
0875b58f | 283 | } |
284 | ||
0fd574c3 | 285 | /*----- Compatibility stuff -----------------------------------------------*/ |
286 | ||
287 | /* --- @sub_alloc@ --- * | |
288 | * | |
d4efbcd9 | 289 | * Arguments: @size_t s@ = size of chunk wanted |
0fd574c3 | 290 | * |
d4efbcd9 | 291 | * Returns: Pointer to a block at least as large as the one wanted. |
0fd574c3 | 292 | * |
d4efbcd9 | 293 | * Use: Allocates a small block of memory from the @sub_global@ pool. |
0fd574c3 | 294 | */ |
295 | ||
296 | void *(sub_alloc)(size_t sz) { return sub_alloc(sz); } | |
297 | ||
298 | /* --- @sub_free@ --- * | |
299 | * | |
d4efbcd9 MW |
300 | * Arguments: @void *p@ = address of block to free |
301 | * @size_t s@ = size of block | |
0fd574c3 | 302 | * |
d4efbcd9 | 303 | * Returns: --- |
0fd574c3 | 304 | * |
d4efbcd9 | 305 | * Use: Frees a block allocated by @sub_alloc@. |
0fd574c3 | 306 | */ |
307 | ||
308 | void (sub_free)(void *p, size_t sz) { sub_free(p, sz); } | |
309 | ||
0875b58f | 310 | /* --- @sub_init@ --- * |
311 | * | |
d4efbcd9 | 312 | * Arguments: --- |
0875b58f | 313 | * |
d4efbcd9 | 314 | * Returns: --- |
0875b58f | 315 | * |
d4efbcd9 | 316 | * Use: Initializes the magic allocator. |
0875b58f | 317 | */ |
318 | ||
319 | void sub_init(void) | |
320 | { | |
ba1916b5 | 321 | #ifndef SUBARENA_TRIVIAL |
b1a20bee | 322 | size_t n, sz; |
0875b58f | 323 | int i; |
324 | ||
b1a20bee MW |
325 | /* Find out if we're running under Valgrind --- */ |
326 | ||
327 | VG( if (RUNNING_ON_VALGRIND) flags |= SF_VALGRIND; ) | |
328 | ||
8c6d948b | 329 | /* --- Initialize the sizes bins --- */ |
0875b58f | 330 | |
331 | for (i = 1; i < SUB_BINS; i++) { | |
b1a20bee MW |
332 | sz = SUB_BINSZ(i); |
333 | n = (SUB_CHUNK + sz - 1)/sz; | |
334 | sz = sizeof(union sub_header) + n*sz; | |
335 | VG( if (flags&SF_VALGRIND) sz += (n + 1)*REDZONE_SIZE; ) | |
336 | sizes[i] = sz; | |
0875b58f | 337 | } |
ba1916b5 | 338 | #endif |
0875b58f | 339 | } |
340 | ||
341 | /*----- Debugging code ----------------------------------------------------*/ | |
342 | ||
343 | #ifdef TEST_RIG | |
344 | ||
345 | #define BLOCKS 1024 | |
346 | #define SIZE_MAX 2048 | |
347 | #define ITERATIONS 500000 | |
348 | ||
349 | int main(void) | |
350 | { | |
351 | static void *block[BLOCKS]; | |
352 | static size_t size[BLOCKS]; | |
353 | size_t allocced = 0; | |
354 | int i; | |
355 | long count; | |
356 | ||
357 | sub_init(); | |
358 | ||
359 | for (count = 0; count < ITERATIONS; count++) { | |
360 | i = rand() % BLOCKS; | |
361 | if (block[i]) { | |
362 | sub_free(block[i], size[i]); | |
363 | block[i] = 0; | |
364 | allocced -= size[i]; | |
365 | } else { | |
366 | block[i] = sub_alloc(size[i] = | |
367 | rand() % (SUB_MAXBIN - 128) + 128); | |
368 | allocced += size[i]; | |
369 | memset(block[i], 0, size[i]); /* trample allocated storage */ | |
370 | } | |
371 | } | |
372 | ||
373 | return (0); | |
374 | } | |
375 | ||
376 | #endif | |
377 | ||
378 | /*----- That's all, folks -------------------------------------------------*/ |