/[ascend]/trunk/base/generic/general/pool.h
ViewVC logotype

Contents of /trunk/base/generic/general/pool.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 59 - (show annotations) (download) (as text)
Sun Oct 30 01:38:20 2005 UTC (18 years, 7 months ago) by jds
File MIME type: text/x-chdr
File size: 16826 byte(s)
- prototype unit test suite based on CUnit added.
- unit tests for base/generic/general and base/generic/utilites added.
- 2nd manual rework of doxygen documentation in general and utilities.
- bug fixes (mostly general & utilities) found during test development.
- added asc_assert prototype to redirect failures to Asc_Panic() and enable decoupling assertions from NDEBUG.
- some modifications of interface & implementation to facilitate testing.
- utilities/ascPrint & utilities/ascMalloc functions now always included in base libs to minimize recompilation when an interface chooses different options.
1 /*
2 * Ascend Pooled Memory Manager
3 * by Benjamin Andrew Allan
4 * Created: 2/96
5 * Version: $Revision: 1.1 $
6 * Version control file: $RCSfile: pool.h,v $
7 * Date last modified: $Date: 1997/07/18 11:37:02 $
8 * Last modified by: $Author: mthomas $
9 *
10 * This file is part of the Ascend Language Interpreter.
11 *
12 * Copyright (C) 1996 Benjamin Andrew Allan
13 *
14 * The Ascend Language Interpreter is free software; you can redistribute
15 * it and/or modify it under the terms of the GNU 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.
18 *
19 * The Ascend Language Interpreter is distributed in hope that it will be
20 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22 * General Public License for more details.
23 *
24 * You should have received a copy of the GNU General Public License
25 * along with the program; if not, write to the Free Software Foundation,
26 * Inc., 675 Mass Ave, Cambridge, MA 02139 USA. Check the file named
27 * COPYING.
28 *
29 */
30
31 /** @file
32 * Ascend Pooled Memory Manager.
33 * <pre>
34 * Contents: Pool Memory module
35 *
36 * Authors: Benjamin Andrew Allan
37 *
38 * Dates: 05/95 - original version: utilities/mem.[ch]
39 * nearly generic element allocation routines.
40 * 02/96 - copied to compiler and swapped pool for mem in
41 * names. deleted all the Karl foo of mem.c.
42 * 03/96 - retuned some of the parameters for compiler.
43 *
44 * Description: This generic element memory manager is yet another
45 * implementation of a fixed byte size malloc system
46 * that is more efficient than most standard mallocs. This
47 * is possible because we make the fixed size assumption.
48 * The idea is clearly not original.
49 * For best results, you must understand your memory
50 * usage pattern and tune the pool_create_store() parameters
51 * accordingly.
52 *
53 * This has similar functionality to free_store.[ch] but
54 * is a rather more efficient implementation with a better
55 * interface. The mem_ implementation of this code
56 * remains in utilities/ because the solvers (which may
57 * also stand alone) need to be able to link without the
58 * compiler goop.
59 *
60 * Detailed Description:
61 *
62 * The following definitions provide a generic and reasonably efficient memory
63 * allocation system for situations where many many objects of the same size
64 * need to be "allocated and deallocated" rapidly and stored efficiently:
65 * that is to say when normal malloc is too slow and expensive.
66 * This scheme does not play reference count games. Instead any elements that
67 * have been created and then used and subsequently "freed" go on a list
68 * and are handed out again at the next opportunity. The list is run LIFO.
69 * The list is associated with the pool_store_t.
70 *
71 * There is one restriction on the elements: they will be a multiple of the
72 * size of a pointer, even if you specify otherwise. If this is too large,
73 * write your own allocator. Think about how your elements align. On many
74 * architectures doubles should only be stored at addresses that are
75 * multiples of 8 bytes.
76 * There is the implicit restriction on a store that it must contain
77 * no more than MAXINT elements. If this is too small, write your own
78 * allocator.
79 *
80 * Even More Details
81 *
82 * If you specify an element size that is not a nice multiple of your machine
83 * word length, you are *very* likely to get data alignment (bus) errors.
84 * E.g., if your element is not a convenient multiple of
85 * sizeof(double) in size, double data are likely to die.
86 *
87 * The allocation scheme looks like so:
88 * [struct pool_store_header | ]
89 * __________________|
90 * |
91 * V
92 * pool _____________________________________________________
93 * | b | b | b | b | b | b | b | b | b | b | b | b | b |
94 * -----------------------------------------------------
95 * where each b is a pointer to an array of size 'width' of elements.
96 *
97 * The size characteristics of this scheme are tunable at run time so that
98 * it can be scaled well when the number of elements and likely amount
99 * of expansion required are known.
100 *
101 * When #including pool.h, make sure these files are #included first:
102 * #include <stdio.h>
103 * #include "utilities/ascConfig.h"
104 * #include "compiler.h"
105 * </pre>
106 */
107
108 #ifndef __pool_h_seen__
109 #define __pool_h_seen__
110
111 typedef struct pool_store_header *pool_store_t;
112 /**<
113 * The token for this memory system. Internal details of the
114 * implementation are private. Do not dereference or free this
115 * pointer.
116 */
117
118 /**
119 * Memory pool statistics data structure.
120 * This is the reporting structure for a pool_store_header query.
121 */
122 struct pool_statistics {
123 double p_eff; /**< bytes in use / bytes allocated */
124 double p_recycle; /**< avg reuses per element */
125 int elt_total; /**< current elements existing in store*/
126 int elt_taken; /**< fresh elements handed out */
127 int elt_inuse; /**< elements the user currently has */
128 int elt_onlist; /**< elements awaiting reuse */
129 int elt_size; /**< bytes/element, as mem sees it */
130 int str_len; /**< length of active pool. */
131 int str_wid; /**< elements/pointer in pool. */
132 };
133
134 extern void pool_get_stats(struct pool_statistics *p_stats,
135 pool_store_t ps);
136 /**<
137 * Get statistics about a pool store.
138 * Stuffs the user's interface structure, p_stats, with info
139 * derived from ps given.
140 * If pool_LIGHTENING (see below) is TRUE, no statistics
141 * except elt_total, elt_taken, elt_onlist, and elt_size are
142 * available.
143 *
144 * @param p_stats Pointer to a pool_statistics struct to receive
145 * the info. If p_stats is NULL, an error message
146 * is printed and the function returns.
147 * @param ps Pointer to the pool store to query.
148 */
149
150 extern pool_store_t pool_create_store(int length,
151 int width,
152 size_t eltsize,
153 int deltalen,
154 int deltapool);
155 /**<
156 * Creates and returns a new pool store. The returned pool_store_t
157 * contains all the necessary accounting information, but in particular
158 * the eltsize is fixed at creation. All elements requested from ps
159 * will be pointers to eltsize bytes of memory.
160 * Returns NULL if a store of the requested length*width*eltsize
161 * cannot be initially allocated.<br><br>
162 *
163 * The user may request more than length*width elements from the store:
164 * this will cause it to grow. It will grow (internally) in chunks of
165 * deltalen*width elements. The pool vector above grows in chunks of
166 * deltapool, the extra pointers in it being NULL until needed.<br><br>
167 *
168 * @param length The initial number of width*eltsize blocks that the
169 * new pool store will contain. If length < 1, an error
170 * message is printed and NULL is returned.
171 *
172 * @param width Number of elements in each block.
173 * Width should (for some architectures) be such that
174 * width*eltsize = 2^n - 32 for some n fairly large
175 * (heuristic: n= 9..13). Widths that are too large may
176 * be prone to causing excess page faults, though the
177 * process cpu time reported by the clock() can be much
178 * better for extremely large sizes. If width < 1, an
179 * error message is printed and NULL is returned.<br><br>
180 * Widths that are too small will result in an excessive
181 * number of pool expansions, which may severely limit
182 * performance on some VM systems. See deltapool below
183 * about pool expansions.<br><br>
184 * If you know something about the page size of your
185 * architecture, fiddling with width may help you reduce
186 * your page fault or cache miss count in some uses.
187 *
188 * @param eltsize Element size maintained by the pool.
189 * For maximum efficiency, eltsize should be an integer
190 * multiple of sizeof(void *). If it is not, elts will be
191 * padded so that this is the case. This is to avoid
192 * pointer data misalignment. This restriction may or
193 * may not help avoid alignment problems with items inside
194 * the user's element structure.
195 *
196 * @param deltalen Number of additional pointers in the pool that will be
197 * allocated when more elements are needed than are
198 * available internally. deltalen must be at least 1 or
199 * creation of the new pool will fail.
200 *
201 * @param deltapool Size change of the pool array when expanded. It should
202 * be as large as you are willing to tolerate. The pool
203 * array starts out completely filled (all pointers allocated).
204 * When the pool needs more pointers it gets them in chunks of
205 * at least deltapool. These additional pointers will not
206 * automatically have elements allocated to them; rather,
207 * they will be initialized to NULL and filled in only as the
208 * chunks of deltalen*width elements are required.
209
210 * @return A pointer to the newly created pool store, NULL if an error occurred.
211 */
212
213 extern void *pool_get_element(pool_store_t ps);
214 /**<
215 * Get a usable element from the pool.
216 * Returns a void pointer to a blob of memory of the eltsize
217 * set when ps was created. You must cast it appropriately.
218 * The blob data is not initialized in any particular way.
219 *
220 * @param ps The pool store from which to retrieve an element.
221 * If ps is NULL, then an error message is printed
222 * and NULL is returned.
223 * @return A pointer to the usable element, or NULL iff ps is NULL or
224 * store growth is required and the operating system is unable
225 * to allocate the required memory.
226 */
227
228 extern void pool_get_element_list(pool_store_t ps,
229 int len,
230 void **ellist);
231 /**<
232 * NOT IMPLEMENTED.
233 *
234 * Takes the pointer array, ellist, of length len provided by the user
235 * and fills it with pointers to elements from the store.
236 * There is not necessarily any relation (memory map wise) between the
237 * locations pointed to by successive entries in the ellist returned.
238 * Ellist should point to an array with enough space for len pointers.
239 * Returns NULL in ellist[0] iff store growth is required and the operating
240 * system is unable to allocate the required memory.<br><br>
241 *
242 * The user is reminded that if he knows how many elements he needs
243 * ahead of time, he is probably better off mallocing the array himself.
244 *
245 * @todo Implement general/pool.c:pool_get_element_list() of remove
246 * it from pool.h.
247 */
248
249 #define pool_DEBUG FALSE
250 /**<
251 * Flag controlling extra checking of the pool management routines.
252 * Setting pool_DEBUG to TRUE causes the pool_store routines to do
253 * some RATHER expensive checking. It should be set to FALSE.
254 */
255 #define pool_LIGHTENING FALSE
256 /**<
257 * Flag controlling extent of internal sanity checking.
258 * Setting pool_LIGHTENING to TRUE causes pool_store routines to assume
259 * the user is perfect: i.e. no sanity checks are at all necessary and most
260 * internal accounting can be disabled. No one with an ounce of sanity
261 * would ever set this flag to TRUE unless the code using the
262 * pool module was proven bug free. It makes the allocator smaller
263 * and faster, though, by ~15%. <br><br>
264 *
265 * This flag exists to make it easy to test the theory that the
266 * accounting overhead in this code is not of significant cost.
267 * Below 1e5 elements it really isn't bad enough to justify the
268 * assumption that the user is perfect.
269 */
270
271 #if pool_DEBUG
272 #define pool_free_element(ps,eltpointer) pool_free_elementF((ps),(eltpointer),__FILE__)
273 #else
274 #define pool_free_element(ps,eltpointer) pool_free_elementF((ps),(eltpointer))
275 #endif
276 /**<
277 * Releases an element back to the store.
278 * If you return the same pointer twice, we will have
279 * no qualms about returning it to you twice. We won't necessarily
280 * return it to you twice, though.<br><br>
281 *
282 * If pool_DEBUG is TRUE, eltpointer will be checked for belonging
283 * to ps. If you call pool_free_element() with a pointer the ps does
284 * not recognize, it will not be freed and a message will be
285 * sent to ASCERR.<br><br>
286 *
287 * If pool_DEBUG is FALSE, eltpointer will be assumed to belong
288 * with the ps in question. The implications of handing
289 * pool_free_element() an element of the wrong size or from the
290 * wrong ps (bearing in mind the LIFO reuse of elements) should be
291 * obvious. If they are not, stop using these routines.<br><br>
292 *
293 * If at any time the number of elements freed exceeds the number
294 * handed out, we will whine (unless pool_LIGHTENING). If ps is
295 * NULL, and error message is printed and the function returns.
296 * If eltpointer is NULL, we will ignore it completely.
297 *
298 * @param ps pool_store_t, the pool store to modify.
299 * @param eltpointer void*, the element to return to the pool.
300 * @return No return value.
301 * @see pool_free_elementF()
302 */
303
304 extern void pool_free_elementF(pool_store_t ps, void * eltpointer
305 #if pool_DEBUG
306 ,CONST char *file
307 #endif
308 );
309 /**<
310 * Implementation function for pool_free_element().
311 * Do not call this function directly - use pool_free_element() instead.
312 */
313
314 #if pool_DEBUG
315 #define pool_clear_store(ps) pool_clear_storeF((ps),__FILE__)
316 #else
317 #define pool_clear_store(ps) pool_clear_storeF(ps)
318 #endif
319 /**<
320 * Clears the books in ps. That is, we reset the ps to think
321 * that __all__ elements are freshly available and have never
322 * been handed out. If ps is NULL, an error message is printed
323 * and the function returns.<br><br>
324 *
325 * If pool_DEBUG is TRUE, it first verifies that all elements have
326 * been pool_freed first and whines if not.
327 * Get and free calls will be balanced to see if spurious elements
328 * have been handed in. (This is a heuristic check).
329 * The clear process will cause any spurious pointers that were
330 * turned in via pool_free_element() to be forgotten about.<br><br>
331 *
332 * Clearing a store is not necessary for pool_destroy_store().
333 * Recycling is faster from the recycle list than from a cleared store, ~2%.
334 * Clear is provided for users who want to obtain elements with a higher
335 * probability of successive elements being near each other.
336 *
337 * @param ps pool_store_t, the pool store to clear.
338 * @return No return value.
339 * @see pool_clear_storeF()
340 */
341
342 extern void pool_clear_storeF(pool_store_t ps
343 #if pool_DEBUG
344 , CONST char *file
345 #endif
346 );
347 /**<
348 * Implementation function for pool_clear_store().
349 * Do not call this function directly - use pool_clear_store() instead.
350 */
351
352 extern void pool_destroy_store(pool_store_t ps);
353 /**<
354 * Deallocates everything associated with the ps.
355 * If pool_DEBUG is TRUE, it first verifies that all elements
356 * have been pool_freed first and whines if not.
357 * If pool_DEBUG is FALSE, just nukes everything unconditionally.
358 * If ps is NULL, an error message is printed and the function
359 * returns.
360 *
361 * @param ps The pool store to destroy.
362 */
363
364 extern void pool_print_store(FILE *fp, pool_store_t ps, unsigned detail);
365 /**<
366 * Prints statistics about a pool_store_t to the file stream given.
367 * Which stats get printed depends on detail.
368 * - If detail 0, displays just summary statistics.
369 * - If detail 1, just internal statistics.
370 * - If detail >1, displays both.
371 *
372 * @param fp The open file stream on which to print the report.
373 * @param ps The pool store on which to report.
374 * @param detail The level of detail to print:
375 * 0 = summary, 1 = internal stats, >1 = both.
376 */
377
378 extern size_t pool_sizeof_store(pool_store_t ps);
379 /**<
380 * Retrieves the current total byte usage of the store.
381 * Returns 0 if an invalid pool store is specified.
382 *
383 * @param ps pool_store_t, the pool store to query.
384 * @return The total bytes currently used by the pool store.
385 */
386
387 #endif /* __pool_h_seen__ */
388

john.pye@anu.edu.au
ViewVC Help
Powered by ViewVC 1.1.22