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