3 * $Id: sub.c,v 1.3 1999/05/06 19:51:35 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.3 1999/05/06 19:51:35 mdw
34 * Reformatted the LGPL notice a little bit.
36 * Revision 1.2 1999/05/05 18:50:31 mdw
37 * Change licensing conditions to LGPL.
39 * Revision 1.1.1.1 1998/06/17 23:44:42 mdw
40 * Initial version of mLib
44 /*----- The big idea ------------------------------------------------------*
46 * This file provides an extra layer over @malloc@. It provides fast
47 * turnover for small blocks, and tries to minimise the per-block overhead.
49 * To do its job, @alloc@ must place an extra restriction on you: you must
50 * know the size of a block when you free it. Usually you'll have this
51 * information encoded in some way either in the block or in the thing that
52 * referenced it, so this isn't a hardship.
54 * It works fairly simply. If a request for a big block (as defined by the
55 * constants below) comes in, it gets sent on to @malloc@ unmolested. For
56 * small blocks, it goes straight to a `bin' -- a list containing free blocks
57 * of exactly that size, or the nearest bigger size we can manage. If the
58 * bin is empty, a `chunk' is allocated from @malloc@: this has enough room
59 * for lots of blocks of the requested size, so it ets split up and each
60 * individual small block is added to the bin list. The first block in the
61 * bin list is then removed and given to the caller. In this way, @malloc@
62 * only stores its information once for lots of little blocks, so we save
63 * memory. Because I know where the correct bin is just from the block size,
64 * and I don't need to do any searching at all in the usual case (because the
65 * list isn't empty) I can get a speed advantage too.
67 * This code is almost certainly not ANSI conformant, although I'm not
68 * actually sure. If some kind soul would let me know how seriously I've
69 * violated the standard, and whether this is easily fixable, I'd be
73 /*----- Header files ------------------------------------------------------*/
75 /* --- ANSI headers --- */
81 /* --- Local headers --- */
83 #undef TRACK_ENABLE /* Can't track suballoc routines */
86 /*----- Configuration and tuning ------------------------------------------*/
88 /* --- The largest block I'll handle here --- *
90 * Anything larger will be handed on to @malloc@.
93 #define SUB_MAXBIN 256
95 /* --- Preferred chunk size --- *
97 * When a bin is empty, I'll allocate a large chunk of approximately this
98 * size and divvy it up into small bin-sized blocks.
101 #define SUB_CHUNK 4096
103 /*----- Other useful macros -----------------------------------------------*/
105 /* --- The granularity of bin buffers --- *
107 * All blocks allocated by the binner are a multiple of this size. I've
108 * chosen @void *@ because I need to store @void *@ things in here.
111 #define SUB_GRANULE sizeof(void *)
113 /* --- Finding the right bin for a given size --- *
115 * This chooses the correct bin for an allocation. Input is the size of
116 * block wanted; result is the bin index.
119 #define SUB_BIN(x) (((x) + SUB_GRANULE - 1) / SUB_GRANULE)
121 /* --- Convert a bin back to the block size --- *
123 * This gives the size of block contained in a given bin.
126 #define SUB_BINSZ(x) ((x) * SUB_GRANULE)
128 /* --- Number of bins required --- */
130 #define SUB_BINS (SUB_MAXBIN / SUB_GRANULE + 1)
132 /*----- Static variables --------------------------------------------------*/
134 static void *sub__bins[SUB_BINS];
135 static size_t sub__sizes[SUB_BINS];
137 /*----- Main code ---------------------------------------------------------*/
139 /* --- @sub_alloc@ --- *
141 * Arguments: @size_t s@ = size of chunk wanted
143 * Returns: Pointer to a block at least as large as the one wanted.
145 * Use: Allocates a small block of memory. If there is no more
146 * memory left, the exception @EXC_NOMEM@ is raised.
149 void *sub_alloc(size_t s)
151 int bin = SUB_BIN(s);
154 /* --- Handle oversize blocks --- */
159 /* --- If the bin is empty, find some memory --- */
161 if (!sub__bins[bin]) {
164 p = xmalloc(sub__sizes[bin]);
165 q = p + sub__sizes[bin];
180 /* --- Extract the first block in the list --- */
183 sub__bins[bin] = *(void **)p;
187 /* --- @sub_free@ --- *
189 * Arguments: @void *p@ = address of block to free
190 * @size_t s@ = size of block
194 * Use: Frees a block allocated by @sub_alloc@.
197 void sub_free(void *p, size_t s)
199 int bin = SUB_BIN(s);
204 *(void **)p = sub__bins[bin];
209 /* --- @sub_init@ --- *
215 * Use: Initialises the magic allocator.
222 /* --- Initialise the sizes bins --- */
224 for (i = 1; i < SUB_BINS; i++) {
225 sub__sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) /
226 SUB_BINSZ(i) * SUB_BINSZ(i));
230 /*----- Debugging code ----------------------------------------------------*/
235 #define SIZE_MAX 2048
236 #define ITERATIONS 500000
240 static void *block[BLOCKS];
241 static size_t size[BLOCKS];
248 for (count = 0; count < ITERATIONS; count++) {
251 sub_free(block[i], size[i]);
255 block[i] = sub_alloc(size[i] =
256 rand() % (SUB_MAXBIN - 128) + 128);
258 memset(block[i], 0, size[i]); /* trample allocated storage */
267 /*----- That's all, folks -------------------------------------------------*/