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