3 * $Id: sub.c,v 1.6 2000/06/17 10:35:51 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.6 2000/06/17 10:35:51 mdw
34 * Major overhaul for arena support.
36 * Revision 1.5 1999/05/19 20:27:11 mdw
37 * Change naming to match newer mLib conventions.
39 * Revision 1.4 1999/05/13 22:48:55 mdw
40 * Change `-ise' to `-ize' throughout.
42 * Revision 1.3 1999/05/06 19:51:35 mdw
43 * Reformatted the LGPL notice a little bit.
45 * Revision 1.2 1999/05/05 18:50:31 mdw
46 * Change licensing conditions to LGPL.
48 * Revision 1.1.1.1 1998/06/17 23:44:42 mdw
49 * Initial version of mLib
53 /*----- The big idea ------------------------------------------------------*
55 * This file provides an extra layer over @malloc@. It provides fast
56 * turnover for small blocks, and tries to minimize the per-block overhead.
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.
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.
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
82 /*----- Header files ------------------------------------------------------*/
84 /* --- ANSI headers --- */
90 /* --- Local headers --- */
96 /*----- Static variables --------------------------------------------------*/
98 static size_t sizes
[SUB_BINS
];
100 /*----- Global variables --------------------------------------------------*/
104 /*----- Main code ---------------------------------------------------------*/
106 /* --- @subarena_create@ --- *
108 * Arguments: @subarena *s@ = pointer to arena to initialize
109 * @arena *a@ = pointer to underlying arena block
113 * Use: Initialize a suballocation arena based on an underlying large
117 void subarena_create(subarena
*s
, arena
*a
)
122 for (i
= 0; i
< SUB_BINS
; i
++)
127 /* --- @subarena_destroy@ --- *
129 * Arguments: @subarena *s@ = pointer to arena to destroy
133 * Use: Destroys a suballocation arena, freeing all of the memory it
134 * contains back to the underlying large blocks arena.
137 void subarena_destroy(subarena
*s
)
140 for (i
= 0; i
< SUB_BINS
; i
++) {
150 /* --- @subarena_alloc@ --- *
152 * Arguments: @subarena *s@ = pointer to arena
153 * @size_t s@ = size of chunk wanted
155 * Returns: Pointer to a block at least as large as the one wanted.
157 * Use: Allocates a small block of memory from the given pool. The
158 * exception @EXC_NOMEM@ is raised if the underlying arena is
162 void *subarena_alloc(subarena
*s
, size_t sz
)
167 /* --- Ensure that everything is initialized --- */
170 subarena_create(s
, arena_global
);
173 /* --- Handle oversize blocks --- */
175 if (bin
>= SUB_BINS
) {
176 void *p
= A_ALLOC(s
->a
, sz
);
182 /* --- If the bin is empty, find some memory --- */
187 p
= A_ALLOC(s
->a
, sizes
[bin
]);
199 *(void **)q
= q
+ sz
;
205 /* --- Extract the first block in the list --- */
208 s
->bin
[bin
] = *(void **)p
;
212 /* --- @subarena_free@ --- *
214 * Arguments: @subarena *s@ = pointer to arena
215 * @void *p@ = address of block to free
216 * @size_t s@ = size of block
220 * Use: Frees a block allocated by @subarena_alloc@.
223 void subarena_free(subarena
*s
, void *p
, size_t sz
)
225 int bin
= SUB_BIN(sz
);
230 *(void **)p
= s
->bin
[bin
];
235 /*----- Compatibility stuff -----------------------------------------------*/
237 /* --- @sub_alloc@ --- *
239 * Arguments: @size_t s@ = size of chunk wanted
241 * Returns: Pointer to a block at least as large as the one wanted.
243 * Use: Allocates a small block of memory from the @sub_global@ pool.
246 void *(sub_alloc
)(size_t sz
) { return sub_alloc(sz
); }
248 /* --- @sub_free@ --- *
250 * Arguments: @void *p@ = address of block to free
251 * @size_t s@ = size of block
255 * Use: Frees a block allocated by @sub_alloc@.
258 void (sub_free
)(void *p
, size_t sz
) { sub_free(p
, sz
); }
260 /* --- @sub_init@ --- *
266 * Use: Initializes the magic allocator.
273 /* --- Initialize the sizes bins --- */
275 for (i
= 1; i
< SUB_BINS
; i
++) {
276 sizes
[i
] = ((SUB_CHUNK
+ SUB_BINSZ(i
) - 1) /
277 SUB_BINSZ(i
) * SUB_BINSZ(i
));
281 /*----- Debugging code ----------------------------------------------------*/
286 #define SIZE_MAX 2048
287 #define ITERATIONS 500000
291 static void *block
[BLOCKS
];
292 static size_t size
[BLOCKS
];
299 for (count
= 0; count
< ITERATIONS
; count
++) {
302 sub_free(block
[i
], size
[i
]);
306 block
[i
] = sub_alloc(size
[i
] =
307 rand() % (SUB_MAXBIN
- 128) + 128);
309 memset(block
[i
], 0, size
[i
]); /* trample allocated storage */
318 /*----- That's all, folks -------------------------------------------------*/