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