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