| blob | e8835b5b8239023c312afb53027b62d8e988496c |
2 BGET -- Memory Allocator
3 ==========================
5 by John Walker
6 kelvin@fourmilab.ch
7 http://www.fourmilab.ch/
9 BGET is a comprehensive memory allocation package which is easily
10 configured to the needs of an application. BGET is efficient in both
11 the time needed to allocate and release buffers and in the memory
12 overhead required for buffer pool management. It automatically
13 consolidates contiguous space to minimise fragmentation. BGET is
14 configured by compile-time definitions, Major options include:
16 * A built-in test program to exercise BGET and
17 demonstrate how the various functions are used.
19 * Allocation by either the "first fit" or "best fit"
20 method.
22 * Wiping buffers at release time to catch code which
23 references previously released storage.
25 * Built-in routines to dump individual buffers or the
26 entire buffer pool.
28 * Retrieval of allocation and pool size statistics.
30 * Quantisation of buffer sizes to a power of two to
31 satisfy hardware alignment constraints.
33 * Automatic pool compaction, growth, and shrinkage by
34 means of call-backs to user defined functions.
36 Applications of BGET can range from storage management in ROM-based
37 embedded programs to providing the framework upon which a multitasking
38 system incorporating garbage collection is constructed. BGET
39 incorporates extensive internal consistency checking using the
40 <assert.h> mechanism; all these checks can be turned off by compiling
41 with NDEBUG defined, yielding a version of BGET with minimal size and
42 maximum speed.
44 The basic algorithm underlying BGET has withstood the test of time; more
45 than 25 years have passed since the first implementation of this code.
46 And yet, it is substantially more efficient than the native allocation
47 schemes of many operating systems: the Macintosh and Microsoft Windows
48 to name two, on which programs have obtained substantial speed-ups by
49 layering BGET as an application level memory manager atop the underlying
50 system's.
52 BGET has been implemented on the largest mainframes and the lowest of
53 microprocessors. It has served as the core for multitasking operating
54 systems, multi-thread applications, embedded software in data network
55 switching processors, and a host of C programs. And while it has
56 accreted flexibility and additional options over the years, it remains
57 fast, memory efficient, portable, and easy to integrate into your
58 program.
61 BGET IMPLEMENTATION ASSUMPTIONS
62 ===============================
64 BGET is written in as portable a dialect of C as possible. The only
65 fundamental assumption about the underlying hardware architecture is
66 that memory is allocated is a linear array which can be addressed as a
67 vector of C "char" objects. On segmented address space architectures,
68 this generally means that BGET should be used to allocate storage within
69 a single segment (although some compilers simulate linear address spaces
70 on segmented architectures). On segmented architectures, then, BGET
71 buffer pools may not be larger than a segment, but since BGET allows any
72 number of separate buffer pools, there is no limit on the total storage
73 which can be managed, only on the largest individual object which can be
74 allocated. Machines with a linear address architecture, such as the
75 VAX, 680x0, Sparc, MIPS, or the Intel 80386 and above in native mode,
76 may use BGET without restriction.
79 GETTING STARTED WITH BGET
80 =========================
82 Although BGET can be configured in a multitude of fashions, there are
83 three basic ways of working with BGET. The functions mentioned below
84 are documented in the following section. Please excuse the forward
85 references which are made in the interest of providing a roadmap to
86 guide you to the BGET functions you're likely to need.
88 Embedded Applications
89 ---------------------
91 Embedded applications typically have a fixed area of memory dedicated to
92 buffer allocation (often in a separate RAM address space distinct from
93 the ROM that contains the executable code). To use BGET in such an
94 environment, simply call bpool() with the start address and length of
95 the buffer pool area in RAM, then allocate buffers with bget() and
96 release them with brel(). Embedded applications with very limited RAM
97 but abundant CPU speed may benefit by configuring BGET for BestFit
98 allocation (which is usually not worth it in other environments).
100 Malloc() Emulation
101 ------------------
103 If the C library malloc() function is too slow, not present in your
104 development environment (for example, an a native Windows or Macintosh
105 program), or otherwise unsuitable, you can replace it with BGET.
106 Initially define a buffer pool of an appropriate size with
107 bpool()--usually obtained by making a call to the operating system's
108 low-level memory allocator. Then allocate buffers with bget(), bgetz(),
109 and bgetr() (the last two permit the allocation of buffers initialised
110 to zero and [inefficient] re-allocation of existing buffers for
111 compatibility with C library functions). Release buffers by calling
112 brel(). If a buffer allocation request fails, obtain more storage from
113 the underlying operating system, add it to the buffer pool by another
114 call to bpool(), and continue execution.
116 Automatic Storage Management
117 ----------------------------
119 You can use BGET as your application's native memory manager and
120 implement automatic storage pool expansion, contraction, and optionally
121 application-specific memory compaction by compiling BGET with the BECtl
122 variable defined, then calling bectl() and supplying functions for
123 storage compaction, acquisition, and release, as well as a standard pool
124 expansion increment. All of these functions are optional (although it
125 doesn't make much sense to provide a release function without an
126 acquisition function, does it?). Once the call-back functions have been
127 defined with bectl(), you simply use bget() and brel() to allocate and
128 release storage as before. You can supply an initial buffer pool with
129 bpool() or rely on automatic allocation to acquire the entire pool.
130 When a call on bget() cannot be satisfied, BGET first checks if a
131 compaction function has been supplied. If so, it is called (with the
132 space required to satisfy the allocation request and a sequence number
133 to allow the compaction routine to be called successively without
134 looping). If the compaction function is able to free any storage (it
135 needn't know whether the storage it freed was adequate) it should return
136 a nonzero value, whereupon BGET will retry the allocation request and,
137 if it fails again, call the compaction function again with the
138 next-higher sequence number.
140 If the compaction function returns zero, indicating failure to free
141 space, or no compaction function is defined, BGET next tests whether a
142 non-NULL allocation function was supplied to bectl(). If so, that
143 function is called with an argument indicating how many bytes of
144 additional space are required. This will be the standard pool expansion
145 increment supplied in the call to bectl() unless the original bget()
146 call requested a buffer larger than this; buffers larger than the
147 standard pool block can be managed "off the books" by BGET in this mode.
148 If the allocation function succeeds in obtaining the storage, it returns
149 a pointer to the new block and BGET expands the buffer pool; if it
150 fails, the allocation request fails and returns NULL to the caller. If
151 a non-NULL release function is supplied, expansion blocks which become
152 totally empty are released to the global free pool by passing their
153 addresses to the release function.
155 Equipped with appropriate allocation, release, and compaction functions,
156 BGET can be used as part of very sophisticated memory management
157 strategies, including garbage collection. (Note, however, that BGET is
158 *not* a garbage collector by itself, and that developing such a system
159 requires much additional logic and careful design of the application's
160 memory allocation strategy.)
163 BGET FUNCTION DESCRIPTIONS
164 ==========================
166 Functions implemented by BGET (some are enabled by certain of the
167 optional settings below):
169 void bpool(void *buffer, bufsize len);
171 Create a buffer pool of <len> bytes, using the storage starting at
172 <buffer>. You can call bpool() subsequently to contribute additional
173 storage to the overall buffer pool.
175 void *bget(bufsize size);
177 Allocate a buffer of <size> bytes. The address of the buffer is
178 returned, or NULL if insufficient memory was available to allocate the
179 buffer.
181 void *bgetz(bufsize size);
183 Allocate a buffer of <size> bytes and clear it to all zeroes. The
184 address of the buffer is returned, or NULL if insufficient memory was
185 available to allocate the buffer.
187 void *bgetr(void *buffer, bufsize newsize);
189 Reallocate a buffer previously allocated by bget(), changing its size to
190 <newsize> and preserving all existing data. NULL is returned if
191 insufficient memory is available to reallocate the buffer, in which case
192 the original buffer remains intact.
194 void brel(void *buf);
196 Return the buffer <buf>, previously allocated by bget(), to the free
197 space pool.
199 void bectl(int (*compact)(bufsize sizereq, int sequence),
200 void *(*acquire)(bufsize size),
201 void (*release)(void *buf),
202 bufsize pool_incr);
204 Expansion control: specify functions through which the package may
205 compact storage (or take other appropriate action) when an allocation
206 request fails, and optionally automatically acquire storage for
207 expansion blocks when necessary, and release such blocks when they
208 become empty. If <compact> is non-NULL, whenever a buffer allocation
209 request fails, the <compact> function will be called with arguments
210 specifying the number of bytes (total buffer size, including header
211 overhead) required to satisfy the allocation request, and a sequence
212 number indicating the number of consecutive calls on <compact>
213 attempting to satisfy this allocation request. The sequence number is 1
214 for the first call on <compact> for a given allocation request, and
215 increments on subsequent calls, permitting the <compact> function to
216 take increasingly dire measures in an attempt to free up storage. If
217 the <compact> function returns a nonzero value, the allocation attempt
218 is re-tried. If <compact> returns 0 (as it must if it isn't able to
219 release any space or add storage to the buffer pool), the allocation
220 request fails, which can trigger automatic pool expansion if the
221 <acquire> argument is non-NULL. At the time the <compact> function is
222 called, the state of the buffer allocator is identical to that at the
223 moment the allocation request was made; consequently, the <compact>
224 function may call brel(), bpool(), bstats(), and/or directly manipulate
225 the buffer pool in any manner which would be valid were the application
226 in control. This does not, however, relieve the <compact> function of
227 the need to ensure that whatever actions it takes do not change things
228 underneath the application that made the allocation request. For
229 example, a <compact> function that released a buffer in the process of
230 being reallocated with bgetr() would lead to disaster. Implementing a
231 safe and effective <compact> mechanism requires careful design of an
232 application's memory architecture, and cannot generally be easily
233 retrofitted into existing code.
235 If <acquire> is non-NULL, that function will be called whenever an
236 allocation request fails. If the <acquire> function succeeds in
237 allocating the requested space and returns a pointer to the new area,
238 allocation will proceed using the expanded buffer pool. If <acquire>
239 cannot obtain the requested space, it should return NULL and the entire
240 allocation process will fail. <pool_incr> specifies the normal
241 expansion block size. Providing an <acquire> function will cause
242 subsequent bget() requests for buffers too large to be managed in the
243 linked-block scheme (in other words, larger than <pool_incr> minus the
244 buffer overhead) to be satisfied directly by calls to the <acquire>
245 function. Automatic release of empty pool blocks will occur only if all
246 pool blocks in the system are the size given by <pool_incr>.
248 void bstats(bufsize *curalloc, bufsize *totfree,
249 bufsize *maxfree, long *nget, long *nrel);
251 The amount of space currently allocated is stored into the variable
252 pointed to by <curalloc>. The total free space (sum of all free blocks
253 in the pool) is stored into the variable pointed to by <totfree>, and
254 the size of the largest single block in the free space pool is stored
255 into the variable pointed to by <maxfree>. The variables pointed to by
256 <nget> and <nrel> are filled, respectively, with the number of
257 successful (non-NULL return) bget() calls and the number of brel()
258 calls.
260 void bstatse(bufsize *pool_incr, long *npool,
261 long *npget, long *nprel,
262 long *ndget, long *ndrel);
264 Extended statistics: The expansion block size will be stored into the
265 variable pointed to by <pool_incr>, or the negative thereof if automatic
266 expansion block releases are disabled. The number of currently active
267 pool blocks will be stored into the variable pointed to by <npool>. The
268 variables pointed to by <npget> and <nprel> will be filled with,
269 respectively, the number of expansion block acquisitions and releases
270 which have occurred. The variables pointed to by <ndget> and <ndrel>
271 will be filled with the number of bget() and brel() calls, respectively,
272 managed through blocks directly allocated by the acquisition and release
273 functions.
275 void bufdump(void *buf);
277 The buffer pointed to by <buf> is dumped on standard output.
279 void bpoold(void *pool, int dumpalloc, int dumpfree);
281 All buffers in the buffer pool <pool>, previously initialised by a call
282 on bpool(), are listed in ascending memory address order. If
283 <dumpalloc> is nonzero, the contents of allocated buffers are dumped; if
284 <dumpfree> is nonzero, the contents of free blocks are dumped.
286 int bpoolv(void *pool);
288 The named buffer pool, previously initialised by a call on bpool(), is
289 validated for bad pointers, overwritten data, etc. If compiled with
290 NDEBUG not defined, any error generates an assertion failure. Otherwise 1
291 is returned if the pool is valid, 0 if an error is found.
293 BGET CONFIGURATION
294 ==================
296 #define TestProg 20000 /* Generate built-in test program
297 if defined. The value specifies
298 how many buffer allocation attempts
299 the test program should make. */
301 #define SizeQuant 4 /* Buffer allocation size quantum:
302 all buffers allocated are a
303 multiple of this size. This
304 MUST be a power of two. */
306 #define BufDump 1 /* Define this symbol to enable the
307 bpoold() function which dumps the
308 buffers in a buffer pool. */
310 #define BufValid 1 /* Define this symbol to enable the
311 bpoolv() function for validating
312 a buffer pool. */
314 #define DumpData 1 /* Define this symbol to enable the
315 bufdump() function which allows
316 dumping the contents of an allocated
317 or free buffer. */
319 #define BufStats 1 /* Define this symbol to enable the
320 bstats() function which calculates
321 the total free space in the buffer
322 pool, the largest available
323 buffer, and the total space
324 currently allocated. */
326 #define FreeWipe 1 /* Wipe free buffers to a guaranteed
327 pattern of garbage to trip up
328 miscreants who attempt to use
329 pointers into released buffers. */
331 #define BestFit 1 /* Use a best fit algorithm when
332 searching for space for an
333 allocation request. This uses
334 memory more efficiently, but
335 allocation will be much slower. */
337 #define BECtl 1 /* Define this symbol to enable the
338 bectl() function for automatic
339 pool space control. */