3 * $Id: sub.c,v 1.1 1998/06/17 23:44:42 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 General Public License as published by
16 * the Free Software Foundation; either version 2 of the License, or
17 * (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 General Public License for more details.
24 * You should have received a copy of the GNU General Public License
25 * along with mLib; if not, write to the Free Software Foundation,
26 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
29 /*----- Revision history --------------------------------------------------*
32 * Revision 1.1 1998/06/17 23:44:42 mdw
37 /*----- The big idea ------------------------------------------------------*
39 * This file provides an extra layer over @malloc@. It provides fast
40 * turnover for small blocks, and tries to minimise the per-block overhead.
42 * To do its job, @alloc@ must place an extra restriction on you: you must
43 * know the size of a block when you free it. Usually you'll have this
44 * information encoded in some way either in the block or in the thing that
45 * referenced it, so this isn't a hardship.
47 * It works fairly simply. If a request for a big block (as defined by the
48 * constants below) comes in, it gets sent on to @malloc@ unmolested. For
49 * small blocks, it goes straight to a `bin' -- a list containing free blocks
50 * of exactly that size, or the nearest bigger size we can manage. If the
51 * bin is empty, a `chunk' is allocated from @malloc@: this has enough room
52 * for lots of blocks of the requested size, so it ets split up and each
53 * individual small block is added to the bin list. The first block in the
54 * bin list is then removed and given to the caller. In this way, @malloc@
55 * only stores its information once for lots of little blocks, so we save
56 * memory. Because I know where the correct bin is just from the block size,
57 * and I don't need to do any searching at all in the usual case (because the
58 * list isn't empty) I can get a speed advantage too.
60 * This code is almost certainly not ANSI conformant, although I'm not
61 * actually sure. If some kind soul would let me know how seriously I've
62 * violated the standard, and whether this is easily fixable, I'd be
66 /*----- Header files ------------------------------------------------------*/
68 /* --- ANSI headers --- */
74 /* --- Local headers --- */
76 #undef TRACK_ENABLE /* Can't track suballoc routines */
79 /*----- Configuration and tuning ------------------------------------------*/
81 /* --- The largest block I'll handle here --- *
83 * Anything larger will be handed on to @malloc@.
86 #define SUB_MAXBIN 256
88 /* --- Preferred chunk size --- *
90 * When a bin is empty, I'll allocate a large chunk of approximately this
91 * size and divvy it up into small bin-sized blocks.
94 #define SUB_CHUNK 4096
96 /*----- Other useful macros -----------------------------------------------*/
98 /* --- The granularity of bin buffers --- *
100 * All blocks allocated by the binner are a multiple of this size. I've
101 * chosen @void *@ because I need to store @void *@ things in here.
104 #define SUB_GRANULE sizeof(void *)
106 /* --- Finding the right bin for a given size --- *
108 * This chooses the correct bin for an allocation. Input is the size of
109 * block wanted; result is the bin index.
112 #define SUB_BIN(x) (((x) + SUB_GRANULE - 1) / SUB_GRANULE)
114 /* --- Convert a bin back to the block size --- *
116 * This gives the size of block contained in a given bin.
119 #define SUB_BINSZ(x) ((x) * SUB_GRANULE)
121 /* --- Number of bins required --- */
123 #define SUB_BINS (SUB_MAXBIN / SUB_GRANULE + 1)
125 /*----- Static variables --------------------------------------------------*/
127 static void *sub__bins[SUB_BINS];
128 static size_t sub__sizes[SUB_BINS];
130 /*----- Main code ---------------------------------------------------------*/
132 /* --- @sub_alloc@ --- *
134 * Arguments: @size_t s@ = size of chunk wanted
136 * Returns: Pointer to a block at least as large as the one wanted.
138 * Use: Allocates a small block of memory. If there is no more
139 * memory left, the exception @EXC_NOMEM@ is raised.
142 void *sub_alloc(size_t s)
144 int bin = SUB_BIN(s);
147 /* --- Handle oversize blocks --- */
152 /* --- If the bin is empty, find some memory --- */
154 if (!sub__bins[bin]) {
157 p = xmalloc(sub__sizes[bin]);
158 q = p + sub__sizes[bin];
173 /* --- Extract the first block in the list --- */
176 sub__bins[bin] = *(void **)p;
180 /* --- @sub_free@ --- *
182 * Arguments: @void *p@ = address of block to free
183 * @size_t s@ = size of block
187 * Use: Frees a block allocated by @sub_alloc@.
190 void sub_free(void *p, size_t s)
192 int bin = SUB_BIN(s);
197 *(void **)p = sub__bins[bin];
202 /* --- @sub_init@ --- *
208 * Use: Initialises the magic allocator.
215 /* --- Initialise the sizes bins --- */
217 for (i = 1; i < SUB_BINS; i++) {
218 sub__sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) /
219 SUB_BINSZ(i) * SUB_BINSZ(i));
223 /*----- Debugging code ----------------------------------------------------*/
228 #define SIZE_MAX 2048
229 #define ITERATIONS 500000
233 static void *block[BLOCKS];
234 static size_t size[BLOCKS];
241 for (count = 0; count < ITERATIONS; count++) {
244 sub_free(block[i], size[i]);
248 block[i] = sub_alloc(size[i] =
249 rand() % (SUB_MAXBIN - 128) + 128);
251 memset(block[i], 0, size[i]); /* trample allocated storage */
260 /*----- That's all, folks -------------------------------------------------*/