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