*** empty log message ***
[mmondor.git] / mmsoftware / mmlib / mmpool.c
CommitLineData
85707533 1/* $Id: mmpool.c,v 1.12 2004/05/19 13:10:19 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
38
39#include <sys/types.h>
40#include <stdlib.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
50
d4aaa170 51MMCOPYRIGHT("@(#) Copyright (c) 2001-2004\n\
7a56f31f 52\tMatthew Mondor. All rights reserved.\n");
85707533 53MMRCSID("$Id: mmpool.c,v 1.12 2004/05/19 13:10:19 mmondor Exp $");
7a56f31f
MM
54
55
56
57
ed581bf0
MM
58/* Initializes a memory pool for efficient management of fixed sized nodes.
59 * returns TRUE on success or FALSE on failure.
60 */
7a56f31f
MM
61bool pool_init(pool_t *pool, void *(*mallocfunc)(size_t),
62 void (*freefunc)(void *), size_t nodesize, u_int32_t nodesperpage,
63 u_int32_t minpages, u_int32_t maxpages)
64{
65 bool ok = FALSE;
66
67 if (pool != NULL && mallocfunc != NULL && freefunc != NULL &&
68 nodesize != 0 && nodesperpage > 0) {
69 register size_t bps = (size_t)OALIGN_CEIL(sizeof(bpage_t), long);
70 register size_t ns = (size_t)OALIGN_CEIL(nodesize, long);
71 register size_t ps = (bps + ((nodesperpage + 1) * ns));
72
73 pool->magic = 0;
74 pool->malloc = mallocfunc;
75 pool->free = freefunc;
76 pool->nodesize = ns;
77 pool->minpages = minpages;
78 pool->maxpages = maxpages;
79 pool->nodesperpage = nodesperpage;
80 pool->pagesize = ps;
81 pool->avgtotal = pool->avgcnt = minpages;
d2558e27
MM
82 DLIST_INIT(&pool->pages);
83 DLIST_INIT(&pool->fpages);
84 DLIST_INIT(&pool->nodes);
7a56f31f
MM
85 /* Allocate minimum number of pages, if needed */
86 for (; minpages > 0; minpages--) {
87 register bpage_t *p;
88
89 if ((p = mallocfunc(ps)) != NULL) {
90 register u_int8_t *ptr, *toptr;
91
92 p->pool = pool;
93 p->magic = MAGIC_PAGE;
94 p->pnodes = nodesperpage;
d2558e27 95 DLIST_APPEND(&pool->pages, (node_t *)p);
7a56f31f
MM
96 for (ptr = toptr = (u_int8_t *)p, ptr += bps, toptr += ps;
97 ptr + ns < toptr; ptr += ns) {
98 ((pnode_t *)ptr)->page = p;
99 ((pnode_t *)ptr)->magic = 0;
d2558e27 100 DLIST_APPEND(&pool->nodes, (node_t *)ptr);
7a56f31f
MM
101 }
102 } else
103 break;
104 }
105 pool->magic = MAGIC_POOL;
106 if (minpages == 0)
107 ok = TRUE;
108 else if (minpages < pool->minpages) {
109 pool_destroy(pool);
460b991b 110 DPRINTF("pool_init", "Out of memory");
7a56f31f
MM
111 }
112 } else
460b991b 113 DPRINTF("pool_init", "Invalid parameters");
7a56f31f
MM
114
115 return ok;
116}
117
118
ed581bf0
MM
119/* Destroys a pool which previously has been created by pool_init(), and frees
120 * any resources it uses (all the nodes it created become invalid).
121 * Returns TRUE on success, or FALSE if the pool pointer is invalid.
122 */
7a56f31f
MM
123bool pool_destroy(pool_t *pool)
124{
125 bool ok = FALSE;
126
127 if (POOL_VALID(pool)) {
128 register node_t *p, *t;
129
d2558e27
MM
130 for (p = DLIST_TOP(&pool->pages); p != NULL; p = t) {
131 t = DLIST_NEXT(p);
7a56f31f
MM
132 ((bpage_t *)p)->magic = 0;
133 pool->free(p);
134 }
d2558e27
MM
135 for (p = DLIST_TOP(&pool->fpages); p != NULL; p = t) {
136 t = DLIST_NEXT(p);
7a56f31f
MM
137 ((bpage_t *)p)->magic = 0;
138 pool->free(p);
139 }
140 pool->magic = 0;
141 ok = TRUE;
142 } else
460b991b 143 DPRINTF("pool_destroy", "Invalid pool_t pointer (%p)", pool);
7a56f31f
MM
144
145 return ok;
146}
147
148
ed581bf0
MM
149/* Allows to very efficiently allocate a single node from the specified pool,
150 * optionally initializing it's memory to zeros. Returns the newly allocated
151 * node pointer on success, or NULL on error.
152 */
7a56f31f
MM
153pnode_t *pool_alloc(pool_t *pool, bool zero)
154{
155 pnode_t *pnode = NULL;
156
157 if (POOL_VALID(pool)) {
158 register pnode_t *pn;
159
160 /* If there are pre-buffered nodes, simply return the first one. */
d2558e27
MM
161 if ((pn = DLIST_TOP(&pool->nodes)) != NULL) {
162 DLIST_UNLINK(&pool->nodes, (node_t *)pn);
7a56f31f
MM
163 pn->page->pnodes--;
164 if (zero) {
165 register bpage_t *p;
166
167 p = pn->page;
168 mm_memclr(pn, pool->nodesize);
169 pn->page = p;
170 }
171 pn->magic = MAGIC_PNODE;
172 pnode = pn;
173 } else {
174 register bpage_t *p = NULL;
175
176 /* No pnode_t left, we need to allocate a new bpage_t to grow and
177 * initialize the new bnode_t objects. First verify if there is
178 * any available page already in our cache, which pool_free()
179 * maintains using statistics, to minimize calls to page
180 * primitives functions. If there are none, allocate a new bpage_t.
181 */
a92b6ea0
MM
182 if (pool->maxpages == 0 ||
183 DLIST_NODES(&pool->pages) < pool->maxpages) {
d2558e27
MM
184 if ((p = DLIST_TOP(&pool->fpages)) != NULL)
185 DLIST_UNLINK(&pool->fpages, (node_t *)p);
7a56f31f
MM
186 else
187 p = pool->malloc(pool->pagesize);
188 if (p != NULL) {
189 register u_int8_t *ptr, *toptr;
190 register size_t ns = pool->nodesize;
191 register size_t ps = pool->pagesize;
192 register size_t bps = (size_t)OALIGN_CEIL(sizeof(bpage_t),
193 long);
194
195 p->pool = pool;
196 p->magic = MAGIC_PAGE;
197 p->pnodes = pool->nodesperpage;
d2558e27 198 DLIST_APPEND(&pool->pages, (node_t *)p);
7a56f31f
MM
199 for (ptr = toptr = (u_int8_t *)p, ptr += bps, toptr += ps;
200 ptr + ns < toptr; ptr += ns) {
201 ((pnode_t *)ptr)->page = p;
202 ((pnode_t *)ptr)->magic = 0;
d2558e27 203 DLIST_APPEND(&pool->nodes, (node_t *)ptr);
7a56f31f
MM
204 }
205 /* Now grab first pnode_t */
206 pn = (pnode_t *)pool->nodes.top;
d2558e27 207 DLIST_UNLINK(&pool->nodes, (node_t *)pn);
7a56f31f
MM
208 p->pnodes--;
209 if (zero)
210 mm_memclr(pn, ns);
211 pn->magic = MAGIC_PNODE;
212 pn->page = p;
213 pnode = pn;
214 } else
460b991b 215 DPRINTF("pool_alloc", "Out of memory");
f36e2a66 216 }
7a56f31f
MM
217 }
218 } else
460b991b 219 DPRINTF("pool_alloc", "Invalid pool_t pointer (%p)", pool);
7a56f31f
MM
220
221 return pnode;
222}
223
224
ed581bf0
MM
225/* Efficiently frees the specified node back to the pool it was allocated from.
226 * Returns NULL. Uses heuristics keeping statistics to determine when to
227 * actually shrink the memory blocks internally used by the pool, so that
228 * frequently growing and shrinking pools will remain large for scalability.
229 */
7a56f31f
MM
230pnode_t *pool_free(pnode_t *pnode)
231{
232 if (PNODE_VALID(pnode)) {
233 register bpage_t *p = pnode->page;
234 register pool_t *pool = p->pool;
85707533 235 register int exceeding;
7a56f31f
MM
236
237 /* Efficiently return this node in the free list. Insert it so that
238 * we favor reusing recently used ones.
239 */
240 pnode->magic = 0;
d2558e27 241 DLIST_INSERT(&pool->nodes, (node_t *)pnode);
7a56f31f
MM
242 p->pnodes++;
243 if ((pool->minpages < pool->maxpages) ||
244 (pool->minpages == 0 && pool->maxpages == 0)) {
a92b6ea0 245 register u_int32_t pages = DLIST_NODES(&pool->pages);
7a56f31f
MM
246
247 /* This is a pool_t which can shrink, book-keep statistics on
248 * average pages usage.
249 */
250 pool->avgtotal += pages;
251 pool->avgcnt++;
252 if (pool->avgcnt > pool->nodesperpage * 3) {
253 pool->avgcnt = 1;
254 pool->avgtotal = pages;
255 }
256
257 if (p->pnodes == pool->nodesperpage && pool->minpages < pages) {
258 register u_int8_t *ptr, *toptr;
259 register size_t ns = pool->nodesize;
260
261 /* All pnode_t objects belonging to this bpage_t were freed.
262 * Swap the page to the cache to be freed. We also need
263 * to sequencially unlink all the pnode_t objects this page
264 * supplied in the free nodes list_t.
265 */
266 for (ptr = toptr = (u_int8_t *)p,
267 ptr += (size_t)OALIGN_CEIL(sizeof(bpage_t), long),
268 toptr += pool->pagesize; ptr + ns < toptr;
269 ptr += ns)
d2558e27 270 DLIST_UNLINK(&pool->nodes, (node_t *)ptr);
7a56f31f
MM
271 /* Insert to preferably reuse recently used pages */
272 p->magic = 0;
d2558e27 273 DLIST_SWAP(&pool->fpages, &pool->pages, (node_t *)p, TRUE);
7a56f31f
MM
274 }
275 /* Do statistics suggest that we should shrink the pool? If so,
276 * free pages from our cache back to the system.
277 */
a92b6ea0
MM
278 if ((exceeding = (DLIST_NODES(&pool->pages) +
279 DLIST_NODES(&pool->fpages)) -
7a56f31f
MM
280 (pool->avgtotal / pool->avgcnt)) > 0) {
281 register list_t *fpages = &pool->fpages;
282 register node_t *n;
283
284 /* Preferably free pages which haven't been used recently */
d2558e27 285 for (; exceeding > 0 && (n = DLIST_BOTTOM(fpages)) != NULL;
7a56f31f 286 exceeding--) {
d2558e27 287 DLIST_UNLINK(fpages, n);
dfc4384a 288 pool->free(n);
7a56f31f
MM
289 }
290 }
291 }
292 } else
460b991b 293 DPRINTF("pool_free", "Invalid pnode_t pointer (%p)", pnode);
7a56f31f
MM
294
295 return NULL;
296}