mmlib/mmat: replace some variables by literal constants
[mmondor.git] / mmsoftware / mmlib / mmpool.c
CommitLineData
b232bd02 1/* $Id: mmpool.c,v 1.30 2007/12/05 23:47:56 mmondor Exp $ */
7a56f31f
MM
2
3/*
b232bd02 4 * Copyright (C) 2001, 2004, 2007, Matthew Mondor
7a56f31f
MM
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. All advertising materials mentioning features or use of this software
16 * must display the following acknowledgement:
d4aaa170 17 * This product includes software developed by Matthew Mondor.
7a56f31f
MM
18 * 4. The name of Matthew Mondor may not be used to endorse or promote
19 * products derived from this software without specific prior written
20 * permission.
d4aaa170
MM
21 * 5. Redistribution of source code may not be released under the terms of
22 * any GNU Public License derivate.
7a56f31f
MM
23 *
24 * THIS SOFTWARE IS PROVIDED BY MATTHEW MONDOR ``AS IS'' AND ANY EXPRESS OR
25 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
26 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
27 * IN NO EVENT SHALL MATTHEW MONDOR BE LIABLE FOR ANY DIRECT, INDIRECT,
28 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
30 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
33 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 */
35
b232bd02
MM
36/*
37 * TODO:
38 * - The usage average statistics should be based on time rather than on a
39 * number of recent operations. A function should probably be provided for
40 * user code to call at regular intervals.
41 */
7a56f31f
MM
42
43
b232bd02
MM
44#include <stdbool.h>
45#include <stdint.h>
7a56f31f 46#include <stdlib.h>
b232bd02 47#include <string.h>
ed396790 48#include <syslog.h>
7a56f31f
MM
49
50#include <mmtypes.h>
7a56f31f
MM
51#include <mmlist.h>
52#include <mmpool.h>
2556ec01 53#include <mmlog.h>
7a56f31f
MM
54
55
d4aaa170 56MMCOPYRIGHT("@(#) Copyright (c) 2001-2004\n\
7a56f31f 57\tMatthew Mondor. All rights reserved.\n");
b232bd02 58MMRCSID("$Id: mmpool.c,v 1.30 2007/12/05 23:47:56 mmondor Exp $");
7a56f31f
MM
59
60
343b3a6c
MM
61/* DEFINITIONS */
62
109627ac 63#define BPAGE_SIZE ((size_t)OALIGN_CEIL(sizeof(bpage_t), long))
343b3a6c 64
ed396790
MM
65/* Define MMPOOLDEBUG and DEBUG for extremely verbose diagnostics */
66#ifdef MMPOOLDEBUG
cea243ac 67#define POOL_DEBUG DEBUG_PRINTF
ed396790 68#else
a95888ea 69#define POOL_DEBUG(s...) ;
ed396790
MM
70#endif
71
343b3a6c 72
343b3a6c
MM
73/* STATIC FUNCTION PROTOTYPES */
74
b232bd02
MM
75static bpage_t *pool_page_create(const char *, pool_t *);
76static bpage_t *pool_page_destroy(bpage_t *);
343b3a6c
MM
77
78
79/* STATIC FUNCTIONS */
80
b232bd02
MM
81/*
82 * Creates a new page of objects, and calls the constructor function for each
83 * object of the new page if needed. Returns NULL on failure, or the new
343b3a6c
MM
84 * bpage_t pointer on success.
85 */
b8fd7c98
MM
86static bpage_t *
87pool_page_create(const char *func, pool_t *pool)
343b3a6c 88{
b232bd02
MM
89 register size_t nodesize = pool->nodesize;
90 register uint8_t *ptr, *toptr;
91 register bpage_t *page;
92 register list_t *list;
93
94 if ((page = pool->malloc(pool->pagesize)) == NULL) {
95 syslog(LOG_NOTICE,
96 "%s - Out of memory allocating page for pool_t (%s)",
97 func, pool->label);
98 return NULL;
343b3a6c 99 }
b232bd02
MM
100
101 /* Initialize bpage_t */
102 page->magic = MAGIC_PAGE;
103 page->pool = pool;
104 DLIST_INIT(&page->objects);
105
106 /*
107 * Create all objects of that bpage_t, inserting them into its list_t.
108 * If any object creation fails (its optional construtor function can
109 * fail), destroy the page and return NULL.
110 */
111 if (pool->create != NULL) {
112 for (ptr = toptr = (uint8_t *)page, ptr += BPAGE_SIZE,
113 toptr += pool->pagesize, list = &page->objects;
114 ptr + nodesize < toptr; ptr += nodesize) {
115 ((pnode_t *)ptr)->magic = 0;
116 ((pnode_t *)ptr)->page = page;
117 if (!pool->create((pnode_t *)ptr)) {
118 syslog(LOG_NOTICE,
119 "%s - Page object constructor function "
120 "returned error for pool_t (%s)",
121 func, pool->label);
122 return pool_page_destroy(page);
123 }
124 DLIST_APPEND(list, (node_t *)ptr);
125 }
126 } else {
127 for (ptr = toptr = (uint8_t *)page, ptr += BPAGE_SIZE,
128 toptr += pool->pagesize, list = &page->objects;
129 ptr + nodesize < toptr; ptr += nodesize) {
130 ((pnode_t *)ptr)->magic = 0;
131 ((pnode_t *)ptr)->page = page;
132 DLIST_APPEND(list, (node_t *)ptr);
133 }
343b3a6c 134 }
343b3a6c 135
b232bd02 136 return page;
343b3a6c
MM
137}
138
b232bd02
MM
139/*
140 * Destroys a page previously created using pool_page_create(), calling the
141 * destructor function for each object of the page if necessary.
142 * Returns NULL.
343b3a6c 143 */
b8fd7c98
MM
144static bpage_t *
145pool_page_destroy(bpage_t *page)
343b3a6c 146{
b232bd02
MM
147 register pnode_t *pnode;
148 register void (*destroy)(pnode_t *);
343b3a6c 149
b232bd02
MM
150 if ((destroy = (page->pool->destroy)) != NULL) {
151 /* We need to destroy all objects */
152 DLIST_FOREACH(&page->objects, pnode)
153 destroy(pnode);
154 }
343b3a6c 155
b232bd02 156 page->pool->free(page);
343b3a6c 157
b232bd02 158 return NULL;
343b3a6c
MM
159}
160
161
343b3a6c 162/* PUBLIC FUNCTIONS */
7a56f31f 163
b232bd02
MM
164/*
165 * Initializes a memory pool for efficient management of fixed sized nodes.
166 * returns true on success or false on failure.
ed581bf0 167 */
b8fd7c98
MM
168bool
169pool_init(pool_t *pool, const char *label, void *(*mallocfunc)(size_t),
b232bd02
MM
170 void (*freefunc)(void *), bool (*create)(pnode_t *),
171 void (*destroy)(pnode_t *), size_t nodesize, uint32_t nodesperpage,
172 uint32_t minpages, uint32_t maxpages)
7a56f31f 173{
b232bd02
MM
174 bool ok = false;
175 register size_t ns, ps;
7a56f31f 176
b232bd02
MM
177 if (DEBUG_FALSE(POOL_VALID(pool))) {
178 DEBUG_PRINTF("Pool already initialized (%p = %s)",
179 pool, pool->label);
180 return false;
181 }
fb5bbc21 182
b232bd02
MM
183 if (DEBUG_FALSE(pool == NULL || mallocfunc == NULL ||
184 freefunc == NULL || ((create == NULL || destroy == NULL) &&
185 (void *)create != (void *)destroy) || nodesize == 0 ||
186 nodesperpage == 0)) {
187 DEBUG_PRINTF("Invalid parameters");
188 return false;
189 }
190
191 ns = (size_t)OALIGN_CEIL(nodesize, long);
192 ps = (BPAGE_SIZE + ((nodesperpage + 1) * ns));
7a56f31f
MM
193
194 pool->magic = 0;
ed396790 195 pool->label = label;
7a56f31f
MM
196 pool->malloc = mallocfunc;
197 pool->free = freefunc;
343b3a6c
MM
198 pool->create = create;
199 pool->destroy = destroy;
7a56f31f
MM
200 pool->nodesize = ns;
201 pool->minpages = minpages;
202 pool->maxpages = maxpages;
203 pool->nodesperpage = nodesperpage;
204 pool->pagesize = ps;
205 pool->avgtotal = pool->avgcnt = minpages;
d2558e27
MM
206 DLIST_INIT(&pool->pages);
207 DLIST_INIT(&pool->fpages);
343b3a6c
MM
208 DLIST_INIT(&pool->epages);
209
b232bd02
MM
210 /*
211 * Allocate minimum number of pages, if needed. We insert them into
343b3a6c
MM
212 * the empty pages list, but minpages will be honored as such to
213 * never free pages below it.
214 */
7a56f31f 215 for (; minpages > 0; minpages--) {
b232bd02 216 register bpage_t *p;
7a56f31f 217
b232bd02
MM
218 if ((p = pool_page_create("pool_init", pool)) == NULL)
219 break;
220 DLIST_APPEND(&pool->epages, (node_t *)p);
7a56f31f 221 }
343b3a6c
MM
222
223 /* Validate this pool */
7a56f31f 224 pool->magic = MAGIC_POOL;
343b3a6c 225
b232bd02
MM
226 /*
227 * Have we failed to allocate any needed pages? If so, destroy pool
228 * and return false.
343b3a6c 229 */
7a56f31f 230 if (minpages == 0)
b232bd02 231 ok = true;
343b3a6c 232 else if (minpages < pool->minpages)
b232bd02 233 (void) pool_destroy(pool);
7a56f31f 234
b232bd02
MM
235 if (ok)
236 POOL_DEBUG("(%p = %s) initialized", pool, pool->label);
ed396790 237
b232bd02 238 return ok;
7a56f31f
MM
239}
240
b232bd02
MM
241/*
242 * Destroys a pool which previously has been created by pool_init(), and frees
ed581bf0 243 * any resources it uses (all the nodes it created become invalid).
b232bd02 244 * Returns true on success, or false if the pool pointer is invalid.
ed581bf0 245 */
b8fd7c98
MM
246bool
247pool_destroy(pool_t *pool)
7a56f31f 248{
b8fd7c98 249 register bpage_t *p, *t;
7a56f31f 250
b232bd02
MM
251 /* Make sure pool_t is valid */
252 if (DEBUG_FALSE(!POOL_VALID(pool))) {
253 DEBUG_PRINTF("Invalid pool_t pointer (%p)", pool);
254 return false;
255 }
256
257 POOL_DEBUG("(%p = %s) destroying", pool, pool->label);
ed396790 258
343b3a6c 259 /* Destroy all pages of all lists */
d2558e27 260 for (p = DLIST_TOP(&pool->pages); p != NULL; p = t) {
b232bd02
MM
261 t = DLIST_NEXT(p);
262 (void) pool_page_destroy(p);
7a56f31f 263 }
d2558e27 264 for (p = DLIST_TOP(&pool->fpages); p != NULL; p = t) {
b232bd02
MM
265 t = DLIST_NEXT(p);
266 (void) pool_page_destroy(p);
343b3a6c
MM
267 }
268 for (p = DLIST_TOP(&pool->epages); p != NULL; p = t) {
b232bd02
MM
269 t = DLIST_NEXT(p);
270 (void) pool_page_destroy(p);
7a56f31f 271 }
343b3a6c
MM
272
273 /* Invalidate pool_t */
7a56f31f 274 pool->magic = 0;
343b3a6c 275
b232bd02 276 return true;
7a56f31f
MM
277}
278
b232bd02
MM
279/*
280 * Allows to very efficiently allocate a single node from the specified pool,
281 * optionally initializing it's memory to zeros. Returns the newly allocated
ed581bf0
MM
282 * node pointer on success, or NULL on error.
283 */
b8fd7c98
MM
284pnode_t *
285pool_alloc(pool_t *pool, bool zero)
7a56f31f 286{
b232bd02
MM
287 pnode_t *pnode = NULL;
288 register bpage_t *page;
7a56f31f 289
b232bd02
MM
290 if (DEBUG_FALSE(!POOL_VALID(pool))) {
291 DEBUG_PRINTF("Invalid pool_t pointer (%p)", pool);
292 return NULL;
293 }
294
295 if (DEBUG_FALSE(zero && pool->create != NULL)) {
296 DEBUG_PRINTF("Will not zero a constructed object of pool (%s)",
297 pool->label);
298 return NULL;
299 }
343b3a6c 300
b232bd02
MM
301 /* Are there any partially used pages? */
302 if ((page = DLIST_TOP(&pool->pages)) == NULL) {
303 /*
304 * No, we thus attempt to move a page from our empty pages
305 * cache back into our usable pages list. The order of the
343b3a6c
MM
306 * usable page list becomes irrelevant at DLIST_SWAP() since
307 * it will be the only node.
308 */
b232bd02 309 POOL_DEBUG("(%p = %s) No usable page", pool, pool->label);
343b3a6c 310 if ((page = DLIST_TOP(&pool->epages)) == NULL) {
b232bd02
MM
311 /*
312 * No more free pages in our cache either.
313 * If maxpages is set and not yet reached, we need to
314 * create a new page.
315 * If we can't, return NULL for error.
316 */
317 POOL_DEBUG("(%p = %s) No empty page",
318 pool, pool->label);
319 if (pool->maxpages == 0 ||
ed396790 320 DLIST_NODES(&pool->fpages) < pool->maxpages) {
b232bd02
MM
321 POOL_DEBUG(
322 "(%p = %s) Creating new usable page",
323 pool, pool->label);
324 if ((page = pool_page_create("pool_alloc",
325 pool)) == NULL)
326 return NULL;
327 DLIST_APPEND(&pool->pages, (node_t *)page);
328 } else
329 return NULL;
ed396790 330 } else {
b232bd02
MM
331 POOL_DEBUG("(%p = %s) swapping page (%p) from empty "
332 "to usable", pool, pool->label, page);
333 DLIST_SWAP(&pool->pages, &pool->epages,
334 (node_t *)page, false);
ed396790 335 }
b232bd02
MM
336 } else {
337 POOL_DEBUG("(%p = %s) Allocating from usable page",
338 pool, pool->label);
339 }
340
341 /*
342 * <page> now points to a page we know we can at least get a free
343 * object node from. Obtain one and unlink it.
344 */
345 pnode = DLIST_TOP(&page->objects);
346 DLIST_UNLINK(&page->objects, (node_t *)pnode);
347
348 /*
349 * Have we obtained the last available object from this page?
350 * If so, move the page to the full pages list. The order of the
351 * full pages list nodes is irrelevant, since we don't know which
352 * of those pages are more likely to be swapped to the usable
353 * pages list first, and we won't run through that list, except at
354 * pool_destroy().
355 */
356 if (DLIST_NODES(&page->objects) == 0) {
357 POOL_DEBUG("(%p = %s) swapping page (%p) from usable to "
358 "full list", pool, pool->label, page);
343b3a6c 359 DLIST_SWAP(&pool->fpages, &pool->pages, (node_t *)page,
b232bd02
MM
360 false);
361 }
7a56f31f 362
b232bd02
MM
363 /*
364 * If requested, zero object. This is stupid if a constructor and
365 * destructor are used, but can be useful otherwise.
366 */
367 if (zero) {
343b3a6c 368 page = pnode->page;
b232bd02 369 (void) memset(pnode, 0x00, pool->nodesize);
343b3a6c 370 pnode->page = page;
b232bd02 371 }
ed396790 372
b232bd02
MM
373 /* Mark this node as a valid allocated object */
374 pnode->magic = MAGIC_PNODE;
ed396790 375
b232bd02
MM
376 POOL_DEBUG("(%p = %s) got object (%p) from page (%p)",
377 pool, pool->label, pnode, page);
7a56f31f 378
b232bd02 379 return pnode;
7a56f31f
MM
380}
381
b232bd02
MM
382/*
383 * Efficiently frees the specified node back to the pool it was allocated from.
384 * Returns NULL. Uses heuristics keeping statistics to determine when to
ed581bf0
MM
385 * actually shrink the memory blocks internally used by the pool, so that
386 * frequently growing and shrinking pools will remain large for scalability.
9316d0ce 387 * This also makes a big difference when constructors and destructors are used
05bafc6f 388 * and need to execute a significant amount of code.
ed581bf0 389 */
b8fd7c98
MM
390pnode_t *
391pool_free(pnode_t *pnode)
7a56f31f 392{
b232bd02
MM
393 register bpage_t *page;
394 register pool_t *pool;
395 register uint32_t count;
b8fd7c98 396
b232bd02
MM
397 if (DEBUG_FALSE(!PNODE_VALID(pnode))) {
398 DEBUG_PRINTF("Invalid pnode_t pointer (%p)", pnode);
399 return NULL;
400 }
7a56f31f 401
b232bd02
MM
402 page = pnode->page;
403 pool = page->pool;
404
405 POOL_DEBUG("(%p = %s) freeing object (%p) from page (%p)",
406 pool, pool->label, pnode, page);
ed396790 407
343b3a6c 408 /* Invalidate object */
7a56f31f 409 pnode->magic = 0;
343b3a6c 410
b232bd02
MM
411 /*
412 * Record how many nodes there currently are in our page's object
413 * list, to be used later on.
343b3a6c
MM
414 */
415 count = DLIST_NODES(&page->objects);
416
b232bd02
MM
417 /*
418 * Add node back to it's page's object list. Insert it so that we
343b3a6c
MM
419 * favor reuse of recently used objects soon.
420 */
421 DLIST_INSERT(&page->objects, (node_t *)pnode);
422
b232bd02
MM
423 /*
424 * Was this page full before we inserted our node? If so, page is in
425 * full pages list, move it to the usable pages list. Insert it to
ed396790
MM
426 * favor reuse of recently used pages soon (this page will soon return
427 * back to the full pages list).
343b3a6c 428 */
ed396790 429 if (count == 0) {
b232bd02 430 POOL_DEBUG(
ed396790
MM
431 "(%p = %s) swapping page (%p) from full to usable list",
432 pool, pool->label, page);
b232bd02 433 DLIST_SWAP(&pool->pages, &pool->fpages, (node_t *)page, true);
ed396790 434 } else {
b232bd02
MM
435 /*
436 * Did we cause our node insertion to totally free back the
437 * page? If so, the page is on the usable free list, move it
438 * back to the empty pages list. Insert it to favor reuse of
439 * recently used pages soon (this page will be the first to
440 * get used again when the usable pages list needs pages).
441 */
442 if (++count == pool->nodesperpage) {
443 POOL_DEBUG("(%p = %s) swapping page (%p) from usable "
444 "to empty list", pool, pool->label, page);
445 DLIST_SWAP(&pool->epages, &pool->pages, (node_t *)page,
446 true);
447 }
343b3a6c
MM
448 }
449
7a56f31f 450 if ((pool->minpages < pool->maxpages) ||
b232bd02
MM
451 (pool->minpages == 0 && pool->maxpages == 0)) {
452 register int exceeding;
453
454 /*
455 * This pool_t is allowed to shrink. Maintain average pages
456 * usage to prevent destroying our pages in the empty pages
457 * list unless we should.
458 */
459 count = DLIST_NODES(&pool->pages) + DLIST_NODES(&pool->fpages);
460 pool->avgtotal += count;
461 pool->avgcnt++;
462
463 /*
464 * Using * 8 here means that pool_free() needs to at least be
465 * called to release as much objects as can fit into eight full
466 * pages in order to execute the following block. But of
467 * course, this does not mean that eight pages will recently
468 * have been freed, since allocations probably also occured
469 * meanwhile.
470 * XXX
471 * It would actually be nice to use a time delay here instead
472 * of this. However, since nodes can be freed quite often,
473 * it would be a burden to use a syscall all the time. What we
474 * could do, however, is update the current time every second
475 * via setitimer(2) or such, however this can clobber
476 * application timers. We perhaps could let the application
477 * call a function to update the time once in a while when it
478 * judges it adequate.
ed396790 479 */
b232bd02
MM
480 if (pool->avgcnt > pool->nodesperpage * 8) {
481 /*
482 * Do statistics suggest that we should shrink the
483 * pool? If so, free pages from our empty pages cache
484 * back to the system, destroying their objects if
485 * necessary. We'll make sure to at least leave a one
486 * page hysterisis for better performance.
487 */
488 if ((exceeding = (count + DLIST_NODES(&pool->epages)
489 - 1) - (pool->avgtotal / pool->avgcnt)) > 0) {
490 register list_t *epages = &pool->epages;
491
492 POOL_DEBUG(
493 "(%p = %s) Destroying %d exceeding pages",
494 pool, pool->label, exceeding);
495
496 /*
497 * Preferably free pages which haven't been
498 * used recently, thus, those at the bottom
499 * of the list.
500 */
501 for (; exceeding > 0 &&
502 (page = DLIST_BOTTOM(epages)) != NULL;
503 exceeding--) {
504 POOL_DEBUG(
505 "(%p = %s) destroying page (%p)",
506 pool, pool->label, page);
507 DLIST_UNLINK(epages, (node_t *)page);
508 (void) pool_page_destroy(page);
509 }
510 }
511 /* Reset statistics */
512 pool->avgcnt = 1;
513 pool->avgtotal = count;
ed396790 514 }
7a56f31f 515 }
7a56f31f 516
b232bd02 517 return NULL;
7a56f31f 518}