3 * Allocation of known-size blocks
5 * (c) 1998 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of the mLib utilities library.
12 * mLib is free software; you can redistribute it and/or modify
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.
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
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with mLib; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 /*----- The big idea ------------------------------------------------------*
30 * This file provides an extra layer over @malloc@. It provides fast
31 * turnover for small blocks, and tries to minimize the per-block overhead.
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.
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.
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
57 /*----- Header files ------------------------------------------------------*/
59 /* --- ANSI headers --- */
66 /* --- Local headers --- */
72 /*----- Configuration tweaks ----------------------------------------------*/
74 /* #define SUBARENA_TRIVIAL */
76 /*----- Static variables --------------------------------------------------*/
78 static size_t sizes
[SUB_BINS
];
80 /*----- Global variables --------------------------------------------------*/
84 #ifdef SUBARENA_TRIVIAL
86 typedef struct sub_link
{
87 struct sub_link
*next
;
94 /*----- Main code ---------------------------------------------------------*/
96 /* --- @subarena_create@ --- *
98 * Arguments: @subarena *s@ = pointer to arena to initialize
99 * @arena *a@ = pointer to underlying arena block
103 * Use: Initialize a suballocation arena based on an underlying large
107 void subarena_create(subarena
*s
, arena
*a
)
109 #ifdef SUBARENA_TRIVIAL
115 for (i
= 0; i
< SUB_BINS
; i
++)
121 /* --- @subarena_destroy@ --- *
123 * Arguments: @subarena *s@ = pointer to arena to destroy
127 * Use: Destroys a suballocation arena, freeing all of the memory it
128 * contains back to the underlying large blocks arena.
131 void subarena_destroy(subarena
*s
)
133 #ifdef SUBARENA_TRIVIAL
137 for (l
= s
->bin
[0]; l
; l
= ll
) {
147 for (i
= 0; i
< SUB_BINS
; i
++) {
160 /* --- @subarena_alloc@ --- *
162 * Arguments: @subarena *s@ = pointer to arena
163 * @size_t s@ = size of chunk wanted
165 * Returns: Pointer to a block at least as large as the one wanted.
167 * Use: Allocates a small block of memory from the given pool. The
168 * exception @EXC_NOMEM@ is raised if the underlying arena is
172 void *subarena_alloc(subarena
*s
, size_t sz
)
174 #ifdef SUBARENA_TRIVIAL
180 subarena_create(s
, arena_global
);
182 if ((l
= a_alloc(s
->a
, sizeof(*l
))) == 0)
184 if ((p
= a_alloc(s
->a
, sz
)) == 0) {
199 /* --- Ensure that everything is initialized --- */
202 subarena_create(s
, arena_global
);
204 /* --- Handle oversize blocks --- */
207 if (bin
>= SUB_BINS
) {
208 void *p
= A_ALLOC(s
->a
, sz
);
214 /* --- If the bin is empty, find some memory --- */
219 p
= A_ALLOC(s
->a
, sizes
[bin
]);
231 *(void **)q
= q
+ sz
;
237 /* --- Extract the first block in the list --- */
240 s
->bin
[bin
] = *(void **)p
;
246 /* --- @subarena_free@ --- *
248 * Arguments: @subarena *s@ = pointer to arena
249 * @void *p@ = address of block to free
250 * @size_t s@ = size of block
254 * Use: Frees a block allocated by @subarena_alloc@.
257 void subarena_free(subarena
*s
, void *p
, size_t sz
)
259 #ifdef SUBARENA_TRIVIAL
261 sub_link
*lh
= s
->bin
[0], **l
, *ll
;
263 for (l
= &lh
; *l
&& (*l
)->p
!= p
; l
= &(*l
)->next
)
267 assert(ll
->sz
== sz
);
275 int bin
= SUB_BIN(sz
);
280 *(void **)p
= s
->bin
[bin
];
287 /*----- Compatibility stuff -----------------------------------------------*/
289 /* --- @sub_alloc@ --- *
291 * Arguments: @size_t s@ = size of chunk wanted
293 * Returns: Pointer to a block at least as large as the one wanted.
295 * Use: Allocates a small block of memory from the @sub_global@ pool.
298 void *(sub_alloc
)(size_t sz
) { return sub_alloc(sz
); }
300 /* --- @sub_free@ --- *
302 * Arguments: @void *p@ = address of block to free
303 * @size_t s@ = size of block
307 * Use: Frees a block allocated by @sub_alloc@.
310 void (sub_free
)(void *p
, size_t sz
) { sub_free(p
, sz
); }
312 /* --- @sub_init@ --- *
318 * Use: Initializes the magic allocator.
323 #ifndef SUBARENA_TRIVIAL
326 /* --- Initialize the sizes bins --- */
328 for (i
= 1; i
< SUB_BINS
; i
++) {
329 sizes
[i
] = ((SUB_CHUNK
+ SUB_BINSZ(i
) - 1) /
330 SUB_BINSZ(i
) * SUB_BINSZ(i
));
335 /*----- Debugging code ----------------------------------------------------*/
340 #define SIZE_MAX 2048
341 #define ITERATIONS 500000
345 static void *block
[BLOCKS
];
346 static size_t size
[BLOCKS
];
353 for (count
= 0; count
< ITERATIONS
; count
++) {
356 sub_free(block
[i
], size
[i
]);
360 block
[i
] = sub_alloc(size
[i
] =
361 rand() % (SUB_MAXBIN
- 128) + 128);
363 memset(block
[i
], 0, size
[i
]); /* trample allocated storage */
372 /*----- That's all, folks -------------------------------------------------*/