3 * $Id: sub.c,v 1.9 2004/04/08 01:36:13 mdw Exp $
5 * Allocation of known-size blocks
7 * (c) 1998 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of the mLib utilities library.
14 * mLib is free software; you can redistribute it and/or modify
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.
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
22 * GNU Library General Public License for more details.
24 * You should have received a copy of the GNU Library General Public
25 * License along with mLib; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
30 /*----- The big idea ------------------------------------------------------*
32 * This file provides an extra layer over @malloc@. It provides fast
33 * turnover for small blocks, and tries to minimize the per-block overhead.
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.
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.
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
59 /*----- Header files ------------------------------------------------------*/
61 /* --- ANSI headers --- */
68 /* --- Local headers --- */
74 /*----- Configuration tweaks ----------------------------------------------*/
76 /* #define SUBARENA_TRIVIAL */
78 /*----- Static variables --------------------------------------------------*/
80 static size_t sizes[SUB_BINS];
82 /*----- Global variables --------------------------------------------------*/
86 #ifdef SUBARENA_TRIVIAL
88 typedef struct sub_link {
89 struct sub_link *next;
96 /*----- Main code ---------------------------------------------------------*/
98 /* --- @subarena_create@ --- *
100 * Arguments: @subarena *s@ = pointer to arena to initialize
101 * @arena *a@ = pointer to underlying arena block
105 * Use: Initialize a suballocation arena based on an underlying large
109 void subarena_create(subarena *s, arena *a)
111 #ifdef SUBARENA_TRIVIAL
117 for (i = 0; i < SUB_BINS; i++)
123 /* --- @subarena_destroy@ --- *
125 * Arguments: @subarena *s@ = pointer to arena to destroy
129 * Use: Destroys a suballocation arena, freeing all of the memory it
130 * contains back to the underlying large blocks arena.
133 void subarena_destroy(subarena *s)
135 #ifdef SUBARENA_TRIVIAL
139 for (l = s->bin[0]; l; l = ll) {
149 for (i = 0; i < SUB_BINS; i++) {
162 /* --- @subarena_alloc@ --- *
164 * Arguments: @subarena *s@ = pointer to arena
165 * @size_t s@ = size of chunk wanted
167 * Returns: Pointer to a block at least as large as the one wanted.
169 * Use: Allocates a small block of memory from the given pool. The
170 * exception @EXC_NOMEM@ is raised if the underlying arena is
174 void *subarena_alloc(subarena *s, size_t sz)
176 #ifdef SUBARENA_TRIVIAL
182 subarena_create(s, arena_global);
184 if ((l = a_alloc(s->a, sizeof(*l))) == 0)
186 if ((p = a_alloc(s->a, sz)) == 0) {
201 /* --- Ensure that everything is initialized --- */
204 subarena_create(s, arena_global);
206 /* --- Handle oversize blocks --- */
209 if (bin >= SUB_BINS) {
210 void *p = A_ALLOC(s->a, sz);
216 /* --- If the bin is empty, find some memory --- */
221 p = A_ALLOC(s->a, sizes[bin]);
233 *(void **)q = q + sz;
239 /* --- Extract the first block in the list --- */
242 s->bin[bin] = *(void **)p;
248 /* --- @subarena_free@ --- *
250 * Arguments: @subarena *s@ = pointer to arena
251 * @void *p@ = address of block to free
252 * @size_t s@ = size of block
256 * Use: Frees a block allocated by @subarena_alloc@.
259 void subarena_free(subarena *s, void *p, size_t sz)
261 #ifdef SUBARENA_TRIVIAL
263 sub_link *lh = s->bin[0], **l, *ll;
265 for (l = &lh; *l && (*l)->p != p; l = &(*l)->next)
269 assert(ll->sz == sz);
277 int bin = SUB_BIN(sz);
282 *(void **)p = s->bin[bin];
289 /*----- Compatibility stuff -----------------------------------------------*/
291 /* --- @sub_alloc@ --- *
293 * Arguments: @size_t s@ = size of chunk wanted
295 * Returns: Pointer to a block at least as large as the one wanted.
297 * Use: Allocates a small block of memory from the @sub_global@ pool.
300 void *(sub_alloc)(size_t sz) { return sub_alloc(sz); }
302 /* --- @sub_free@ --- *
304 * Arguments: @void *p@ = address of block to free
305 * @size_t s@ = size of block
309 * Use: Frees a block allocated by @sub_alloc@.
312 void (sub_free)(void *p, size_t sz) { sub_free(p, sz); }
314 /* --- @sub_init@ --- *
320 * Use: Initializes the magic allocator.
325 #ifndef SUBARENA_TRIVIAL
328 /* --- Initialize the sizes bins --- */
330 for (i = 1; i < SUB_BINS; i++) {
331 sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) /
332 SUB_BINSZ(i) * SUB_BINSZ(i));
337 /*----- Debugging code ----------------------------------------------------*/
342 #define SIZE_MAX 2048
343 #define ITERATIONS 500000
347 static void *block[BLOCKS];
348 static size_t size[BLOCKS];
355 for (count = 0; count < ITERATIONS; count++) {
358 sub_free(block[i], size[i]);
362 block[i] = sub_alloc(size[i] =
363 rand() % (SUB_MAXBIN - 128) + 128);
365 memset(block[i], 0, size[i]); /* trample allocated storage */
374 /*----- That's all, folks -------------------------------------------------*/