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