3 * $Id: sub.c,v 1.8 2003/10/12 14:44:46 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 /*----- Revision history --------------------------------------------------*
33 * Revision 1.8 2003/10/12 14:44:46 mdw
36 * Revision 1.7 2003/05/18 15:10:20 mdw
37 * Add debugging mode which just uses the underlying arena.
39 * Revision 1.6 2000/06/17 10:35:51 mdw
40 * Major overhaul for arena support.
42 * Revision 1.5 1999/05/19 20:27:11 mdw
43 * Change naming to match newer mLib conventions.
45 * Revision 1.4 1999/05/13 22:48:55 mdw
46 * Change `-ise' to `-ize' throughout.
48 * Revision 1.3 1999/05/06 19:51:35 mdw
49 * Reformatted the LGPL notice a little bit.
51 * Revision 1.2 1999/05/05 18:50:31 mdw
52 * Change licensing conditions to LGPL.
54 * Revision 1.1.1.1 1998/06/17 23:44:42 mdw
55 * Initial version of mLib
59 /*----- The big idea ------------------------------------------------------*
61 * This file provides an extra layer over @malloc@. It provides fast
62 * turnover for small blocks, and tries to minimize the per-block overhead.
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.
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.
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
88 /*----- Header files ------------------------------------------------------*/
90 /* --- ANSI headers --- */
97 /* --- Local headers --- */
103 /*----- Configuration tweaks ----------------------------------------------*/
105 /* #define SUBARENA_TRIVIAL */
107 /*----- Static variables --------------------------------------------------*/
109 static size_t sizes[SUB_BINS];
111 /*----- Global variables --------------------------------------------------*/
115 #ifdef SUBARENA_TRIVIAL
117 typedef struct sub_link {
118 struct sub_link *next;
125 /*----- Main code ---------------------------------------------------------*/
127 /* --- @subarena_create@ --- *
129 * Arguments: @subarena *s@ = pointer to arena to initialize
130 * @arena *a@ = pointer to underlying arena block
134 * Use: Initialize a suballocation arena based on an underlying large
138 void subarena_create(subarena *s, arena *a)
140 #ifdef SUBARENA_TRIVIAL
146 for (i = 0; i < SUB_BINS; i++)
152 /* --- @subarena_destroy@ --- *
154 * Arguments: @subarena *s@ = pointer to arena to destroy
158 * Use: Destroys a suballocation arena, freeing all of the memory it
159 * contains back to the underlying large blocks arena.
162 void subarena_destroy(subarena *s)
164 #ifdef SUBARENA_TRIVIAL
168 for (l = s->bin[0]; l; l = ll) {
178 for (i = 0; i < SUB_BINS; i++) {
191 /* --- @subarena_alloc@ --- *
193 * Arguments: @subarena *s@ = pointer to arena
194 * @size_t s@ = size of chunk wanted
196 * Returns: Pointer to a block at least as large as the one wanted.
198 * Use: Allocates a small block of memory from the given pool. The
199 * exception @EXC_NOMEM@ is raised if the underlying arena is
203 void *subarena_alloc(subarena *s, size_t sz)
205 #ifdef SUBARENA_TRIVIAL
211 subarena_create(s, arena_global);
213 if ((l = a_alloc(s->a, sizeof(*l))) == 0)
215 if ((p = a_alloc(s->a, sz)) == 0) {
230 /* --- Ensure that everything is initialized --- */
233 subarena_create(s, arena_global);
235 /* --- Handle oversize blocks --- */
238 if (bin >= SUB_BINS) {
239 void *p = A_ALLOC(s->a, sz);
245 /* --- If the bin is empty, find some memory --- */
250 p = A_ALLOC(s->a, sizes[bin]);
262 *(void **)q = q + sz;
268 /* --- Extract the first block in the list --- */
271 s->bin[bin] = *(void **)p;
277 /* --- @subarena_free@ --- *
279 * Arguments: @subarena *s@ = pointer to arena
280 * @void *p@ = address of block to free
281 * @size_t s@ = size of block
285 * Use: Frees a block allocated by @subarena_alloc@.
288 void subarena_free(subarena *s, void *p, size_t sz)
290 #ifdef SUBARENA_TRIVIAL
292 sub_link *lh = s->bin[0], **l, *ll;
294 for (l = &lh; *l && (*l)->p != p; l = &(*l)->next)
298 assert(ll->sz == sz);
306 int bin = SUB_BIN(sz);
311 *(void **)p = s->bin[bin];
318 /*----- Compatibility stuff -----------------------------------------------*/
320 /* --- @sub_alloc@ --- *
322 * Arguments: @size_t s@ = size of chunk wanted
324 * Returns: Pointer to a block at least as large as the one wanted.
326 * Use: Allocates a small block of memory from the @sub_global@ pool.
329 void *(sub_alloc)(size_t sz) { return sub_alloc(sz); }
331 /* --- @sub_free@ --- *
333 * Arguments: @void *p@ = address of block to free
334 * @size_t s@ = size of block
338 * Use: Frees a block allocated by @sub_alloc@.
341 void (sub_free)(void *p, size_t sz) { sub_free(p, sz); }
343 /* --- @sub_init@ --- *
349 * Use: Initializes the magic allocator.
354 #ifndef SUBARENA_TRIVIAL
357 /* --- Initialize the sizes bins --- */
359 for (i = 1; i < SUB_BINS; i++) {
360 sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) /
361 SUB_BINSZ(i) * SUB_BINSZ(i));
366 /*----- Debugging code ----------------------------------------------------*/
371 #define SIZE_MAX 2048
372 #define ITERATIONS 500000
376 static void *block[BLOCKS];
377 static size_t size[BLOCKS];
384 for (count = 0; count < ITERATIONS; count++) {
387 sub_free(block[i], size[i]);
391 block[i] = sub_alloc(size[i] =
392 rand() % (SUB_MAXBIN - 128) + 128);
394 memset(block[i], 0, size[i]); /* trample allocated storage */
403 /*----- That's all, folks -------------------------------------------------*/