chiark / gitweb /
Infrastructure: Split the files into subdirectories.
[mLib] / mem / sub.c
CommitLineData
0875b58f 1/* -*-c-*-
2 *
0875b58f 3 * Allocation of known-size blocks
4 *
5 * (c) 1998 Straylight/Edgeware
6 */
7
d4efbcd9 8/*----- Licensing notice --------------------------------------------------*
0875b58f 9 *
10 * This file is part of the mLib utilities library.
11 *
12 * mLib is free software; you can redistribute it and/or modify
c846879c 13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
d4efbcd9 16 *
0875b58f 17 * mLib is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
c846879c 20 * GNU Library General Public License for more details.
d4efbcd9 21 *
c846879c 22 * You should have received a copy of the GNU Library General Public
0bd98442 23 * License along with mLib; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25 * MA 02111-1307, USA.
0875b58f 26 */
27
0875b58f 28/*----- The big idea ------------------------------------------------------*
29 *
30 * This file provides an extra layer over @malloc@. It provides fast
8c6d948b 31 * turnover for small blocks, and tries to minimize the per-block overhead.
0875b58f 32 *
33 * To do its job, @alloc@ must place an extra restriction on you: you must
34 * know the size of a block when you free it. Usually you'll have this
35 * information encoded in some way either in the block or in the thing that
36 * referenced it, so this isn't a hardship.
37 *
38 * It works fairly simply. If a request for a big block (as defined by the
39 * constants below) comes in, it gets sent on to @malloc@ unmolested. For
40 * small blocks, it goes straight to a `bin' -- a list containing free blocks
41 * of exactly that size, or the nearest bigger size we can manage. If the
42 * bin is empty, a `chunk' is allocated from @malloc@: this has enough room
43 * for lots of blocks of the requested size, so it ets split up and each
44 * individual small block is added to the bin list. The first block in the
45 * bin list is then removed and given to the caller. In this way, @malloc@
46 * only stores its information once for lots of little blocks, so we save
47 * memory. Because I know where the correct bin is just from the block size,
48 * and I don't need to do any searching at all in the usual case (because the
49 * list isn't empty) I can get a speed advantage too.
50 *
51 * This code is almost certainly not ANSI conformant, although I'm not
52 * actually sure. If some kind soul would let me know how seriously I've
53 * violated the standard, and whether this is easily fixable, I'd be
54 * grateful.
55 */
56
57/*----- Header files ------------------------------------------------------*/
58
59/* --- ANSI headers --- */
60
ba1916b5 61#include <assert.h>
0875b58f 62#include <stdio.h>
63#include <stdlib.h>
64#include <string.h>
65
66/* --- Local headers --- */
67
0fd574c3 68#include "arena.h"
69#include "exc.h"
70#include "sub.h"
0875b58f 71
ba1916b5 72/*----- Configuration tweaks ----------------------------------------------*/
73
74/* #define SUBARENA_TRIVIAL */
75
0fd574c3 76/*----- Static variables --------------------------------------------------*/
0875b58f 77
0fd574c3 78static size_t sizes[SUB_BINS];
0875b58f 79
0fd574c3 80/*----- Global variables --------------------------------------------------*/
0875b58f 81
0fd574c3 82subarena sub_global;
0875b58f 83
ba1916b5 84#ifdef SUBARENA_TRIVIAL
85
86typedef struct sub_link {
87 struct sub_link *next;
88 void *p;
89 size_t sz;
90} sub_link;
91
92#endif
93
0fd574c3 94/*----- Main code ---------------------------------------------------------*/
0875b58f 95
0fd574c3 96/* --- @subarena_create@ --- *
0875b58f 97 *
0fd574c3 98 * Arguments: @subarena *s@ = pointer to arena to initialize
99 * @arena *a@ = pointer to underlying arena block
0875b58f 100 *
0fd574c3 101 * Returns: ---
102 *
103 * Use: Initialize a suballocation arena based on an underlying large
104 * blocks arena.
0875b58f 105 */
106
0fd574c3 107void subarena_create(subarena *s, arena *a)
108{
ba1916b5 109#ifdef SUBARENA_TRIVIAL
110 s->bin[0] = 0;
111#else
0fd574c3 112 size_t i;
113 if (!sizes[1])
114 sub_init();
115 for (i = 0; i < SUB_BINS; i++)
116 s->bin[i] = 0;
ba1916b5 117#endif
0fd574c3 118 s->a = a;
119}
0875b58f 120
0fd574c3 121/* --- @subarena_destroy@ --- *
0875b58f 122 *
0fd574c3 123 * Arguments: @subarena *s@ = pointer to arena to destroy
124 *
125 * Returns: ---
126 *
127 * Use: Destroys a suballocation arena, freeing all of the memory it
128 * contains back to the underlying large blocks arena.
0875b58f 129 */
130
0fd574c3 131void subarena_destroy(subarena *s)
132{
ba1916b5 133#ifdef SUBARENA_TRIVIAL
134
135 sub_link *l, *ll;
136
137 for (l = s->bin[0]; l; l = ll) {
138 ll = l;
139 a_free(s->a, l->p);
140 a_free(s->a, l);
141 }
142 s->bin[0] = 0;
143
144#else
145
0fd574c3 146 size_t i;
147 for (i = 0; i < SUB_BINS; i++) {
148 void *p = s->bin[i];
149 while (p) {
150 void *q = p;
151 p = *(void **)q;
152 A_FREE(s->a, q);
153 }
c5775f49 154 s->bin[i] = 0;
0fd574c3 155 }
ba1916b5 156
157#endif
0fd574c3 158}
0875b58f 159
0fd574c3 160/* --- @subarena_alloc@ --- *
0875b58f 161 *
d4efbcd9 162 * Arguments: @subarena *s@ = pointer to arena
0fd574c3 163 * @size_t s@ = size of chunk wanted
0875b58f 164 *
d4efbcd9 165 * Returns: Pointer to a block at least as large as the one wanted.
0875b58f 166 *
d4efbcd9 167 * Use: Allocates a small block of memory from the given pool. The
0fd574c3 168 * exception @EXC_NOMEM@ is raised if the underlying arena is
169 * full.
0875b58f 170 */
171
0fd574c3 172void *subarena_alloc(subarena *s, size_t sz)
0875b58f 173{
ba1916b5 174#ifdef SUBARENA_TRIVIAL
175
176 sub_link *l;
177 void *p;
178
179 if (!s->a)
180 subarena_create(s, arena_global);
181
182 if ((l = a_alloc(s->a, sizeof(*l))) == 0)
183 return (0);
184 if ((p = a_alloc(s->a, sz)) == 0) {
185 a_free(s->a, l);
186 return (0);
187 }
188 l->p = p;
189 l->sz = sz;
190 l->next = s->bin[0];
191 s->bin[0] = l;
192 return (p);
193
194#else
195
0fd574c3 196 int bin;
0875b58f 197 void *p;
198
0fd574c3 199 /* --- Ensure that everything is initialized --- */
200
201 if (!s->a)
202 subarena_create(s, arena_global);
0fd574c3 203
0875b58f 204 /* --- Handle oversize blocks --- */
205
ba1916b5 206 bin = SUB_BIN(sz);
0fd574c3 207 if (bin >= SUB_BINS) {
208 void *p = A_ALLOC(s->a, sz);
209 if (!p)
210 THROW(EXC_NOMEM);
211 return (p);
212 }
0875b58f 213
214 /* --- If the bin is empty, find some memory --- */
215
0fd574c3 216 if (!s->bin[bin]) {
0875b58f 217 char *p, *q;
218
0fd574c3 219 p = A_ALLOC(s->a, sizes[bin]);
220 if (!p)
221 THROW(EXC_NOMEM);
ff0f0220 222 q = p + sizes[bin];
0875b58f 223
0fd574c3 224 sz = SUB_BINSZ(bin);
0875b58f 225
0fd574c3 226 q -= sz;
0875b58f 227 *(void **)q = 0;
228
229 while (q > p) {
0fd574c3 230 q -= sz;
231 *(void **)q = q + sz;
0875b58f 232 }
233
0fd574c3 234 s->bin[bin] = p;
0875b58f 235 }
236
237 /* --- Extract the first block in the list --- */
238
0fd574c3 239 p = s->bin[bin];
240 s->bin[bin] = *(void **)p;
0875b58f 241 return (p);
ba1916b5 242
243#endif
0875b58f 244}
245
0fd574c3 246/* --- @subarena_free@ --- *
0875b58f 247 *
d4efbcd9 248 * Arguments: @subarena *s@ = pointer to arena
0fd574c3 249 * @void *p@ = address of block to free
d4efbcd9 250 * @size_t s@ = size of block
0875b58f 251 *
d4efbcd9 252 * Returns: ---
0875b58f 253 *
d4efbcd9 254 * Use: Frees a block allocated by @subarena_alloc@.
0875b58f 255 */
256
0fd574c3 257void subarena_free(subarena *s, void *p, size_t sz)
0875b58f 258{
ba1916b5 259#ifdef SUBARENA_TRIVIAL
260
261 sub_link *lh = s->bin[0], **l, *ll;
262
263 for (l = &lh; *l && (*l)->p != p; l = &(*l)->next)
264 ;
265 ll = *l;
266 assert(ll);
267 assert(ll->sz == sz);
268 *l = ll->next;
269 a_free(s->a, ll);
270 a_free(s->a, p);
271 s->bin[0] = lh;
272
273#else
274
0fd574c3 275 int bin = SUB_BIN(sz);
0875b58f 276
277 if (bin >= SUB_BINS)
0fd574c3 278 A_FREE(s->a, p);
0875b58f 279 else {
0fd574c3 280 *(void **)p = s->bin[bin];
281 s->bin[bin] = p;
0875b58f 282 }
ba1916b5 283
284#endif
0875b58f 285}
286
0fd574c3 287/*----- Compatibility stuff -----------------------------------------------*/
288
289/* --- @sub_alloc@ --- *
290 *
d4efbcd9 291 * Arguments: @size_t s@ = size of chunk wanted
0fd574c3 292 *
d4efbcd9 293 * Returns: Pointer to a block at least as large as the one wanted.
0fd574c3 294 *
d4efbcd9 295 * Use: Allocates a small block of memory from the @sub_global@ pool.
0fd574c3 296 */
297
298void *(sub_alloc)(size_t sz) { return sub_alloc(sz); }
299
300/* --- @sub_free@ --- *
301 *
d4efbcd9
MW
302 * Arguments: @void *p@ = address of block to free
303 * @size_t s@ = size of block
0fd574c3 304 *
d4efbcd9 305 * Returns: ---
0fd574c3 306 *
d4efbcd9 307 * Use: Frees a block allocated by @sub_alloc@.
0fd574c3 308 */
309
310void (sub_free)(void *p, size_t sz) { sub_free(p, sz); }
311
0875b58f 312/* --- @sub_init@ --- *
313 *
d4efbcd9 314 * Arguments: ---
0875b58f 315 *
d4efbcd9 316 * Returns: ---
0875b58f 317 *
d4efbcd9 318 * Use: Initializes the magic allocator.
0875b58f 319 */
320
321void sub_init(void)
322{
ba1916b5 323#ifndef SUBARENA_TRIVIAL
0875b58f 324 int i;
325
8c6d948b 326 /* --- Initialize the sizes bins --- */
0875b58f 327
328 for (i = 1; i < SUB_BINS; i++) {
ff0f0220 329 sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) /
0875b58f 330 SUB_BINSZ(i) * SUB_BINSZ(i));
331 }
ba1916b5 332#endif
0875b58f 333}
334
335/*----- Debugging code ----------------------------------------------------*/
336
337#ifdef TEST_RIG
338
339#define BLOCKS 1024
340#define SIZE_MAX 2048
341#define ITERATIONS 500000
342
343int main(void)
344{
345 static void *block[BLOCKS];
346 static size_t size[BLOCKS];
347 size_t allocced = 0;
348 int i;
349 long count;
350
351 sub_init();
352
353 for (count = 0; count < ITERATIONS; count++) {
354 i = rand() % BLOCKS;
355 if (block[i]) {
356 sub_free(block[i], size[i]);
357 block[i] = 0;
358 allocced -= size[i];
359 } else {
360 block[i] = sub_alloc(size[i] =
361 rand() % (SUB_MAXBIN - 128) + 128);
362 allocced += size[i];
363 memset(block[i], 0, size[i]); /* trample allocated storage */
364 }
365 }
366
367 return (0);
368}
369
370#endif
371
372/*----- That's all, folks -------------------------------------------------*/