1 cfa37a7b 2004-04-10 devnull .TH POOL 3
3 cfa37a7b 2004-04-10 devnull poolalloc, poolfree, poolmsize, poolrealloc, poolcompact, poolcheck, poolblockcheck,
4 cfa37a7b 2004-04-10 devnull pooldump \- general memory management routines
5 cfa37a7b 2004-04-10 devnull .SH SYNOPSIS
6 cfa37a7b 2004-04-10 devnull .B #include <u.h>
8 cfa37a7b 2004-04-10 devnull .B #include <libc.h>
10 cfa37a7b 2004-04-10 devnull .B #include <pool.h>
13 cfa37a7b 2004-04-10 devnull void* poolalloc(Pool* pool, ulong size)
16 cfa37a7b 2004-04-10 devnull void poolfree(Pool* pool, void* ptr)
19 cfa37a7b 2004-04-10 devnull ulong poolmsize(Pool* pool, void* ptr)
22 cfa37a7b 2004-04-10 devnull void* poolrealloc(Pool* pool, void* ptr, ulong size)
25 cfa37a7b 2004-04-10 devnull void poolcompact(Pool* pool)
28 cfa37a7b 2004-04-10 devnull void poolcheck(Pool *pool)
31 cfa37a7b 2004-04-10 devnull void poolblockcheck(Pool *pool, void *ptr)
34 cfa37a7b 2004-04-10 devnull void pooldump(Pool *pool);
35 cfa37a7b 2004-04-10 devnull .SH DESCRIPTION
36 cfa37a7b 2004-04-10 devnull These routines provide a general memory management facility.
37 cfa37a7b 2004-04-10 devnull Memory is retrieved from a coarser allocator (e.g.
39 cfa37a7b 2004-04-10 devnull or the kernel's
40 cfa37a7b 2004-04-10 devnull .IR xalloc )
41 cfa37a7b 2004-04-10 devnull and then allocated to callers.
42 cfa37a7b 2004-04-10 devnull The routines are locked and thus may safely be used in
43 cfa37a7b 2004-04-10 devnull multiprocess programs.
45 cfa37a7b 2004-04-10 devnull .I Poolalloc
46 cfa37a7b 2004-04-10 devnull attempts to allocate a block of size
47 cfa37a7b 2004-04-10 devnull .BR size ;
48 cfa37a7b 2004-04-10 devnull it returns a pointer to the block when successful and nil otherwise.
50 cfa37a7b 2004-04-10 devnull .B "poolalloc(0)
51 cfa37a7b 2004-04-10 devnull returns a non-nil pointer.
52 cfa37a7b 2004-04-10 devnull .I Poolfree
53 cfa37a7b 2004-04-10 devnull returns an allocated block to the pool.
54 cfa37a7b 2004-04-10 devnull It is an error to free a block more than once or to free a
55 cfa37a7b 2004-04-10 devnull pointer not returned by
56 cfa37a7b 2004-04-10 devnull .IR poolalloc .
58 cfa37a7b 2004-04-10 devnull .B "poolfree(nil)
59 cfa37a7b 2004-04-10 devnull is legal and is a no-op.
60 cfa37a7b 2004-04-10 devnull .I Poolrealloc
61 cfa37a7b 2004-04-10 devnull attempts to resize to
63 cfa37a7b 2004-04-10 devnull bytes the block associated with
64 cfa37a7b 2004-04-10 devnull .BR ptr ,
65 cfa37a7b 2004-04-10 devnull which must have been previously returned by
66 cfa37a7b 2004-04-10 devnull .I poolalloc
68 cfa37a7b 2004-04-10 devnull .IR poolrealloc .
69 cfa37a7b 2004-04-10 devnull If the block's size can be adjusted, a (possibly different) pointer to the new block is returned.
70 cfa37a7b 2004-04-10 devnull The contents up to the lesser of the old and new sizes are unchanged.
71 cfa37a7b 2004-04-10 devnull After a successful call to
72 cfa37a7b 2004-04-10 devnull .IR poolrealloc ,
73 cfa37a7b 2004-04-10 devnull the return value should be used rather than
75 cfa37a7b 2004-04-10 devnull to access the block.
76 cfa37a7b 2004-04-10 devnull If the request cannot be satisfied,
77 cfa37a7b 2004-04-10 devnull .I poolrealloc
78 cfa37a7b 2004-04-10 devnull returns nil, and the old pointer remains valid.
80 cfa37a7b 2004-04-10 devnull When blocks are allocated, there is often some extra space left at the end
81 cfa37a7b 2004-04-10 devnull that would usually go unused.
82 cfa37a7b 2004-04-10 devnull .IR Poolmsize
83 cfa37a7b 2004-04-10 devnull grows the block to encompass this extra space and returns the new size.
86 cfa37a7b 2004-04-10 devnull .I poolblockcheck
88 cfa37a7b 2004-04-10 devnull .I poolcheck
89 cfa37a7b 2004-04-10 devnull routines validate a single allocated block or the entire pool, respectively.
90 cfa37a7b 2004-04-10 devnull They call
92 cfa37a7b 2004-04-10 devnull (see below)
93 cfa37a7b 2004-04-10 devnull if corruption is detected.
94 cfa37a7b 2004-04-10 devnull .I Pooldump
95 cfa37a7b 2004-04-10 devnull prints a summary line for every block in the
96 cfa37a7b 2004-04-10 devnull pool, using the
98 cfa37a7b 2004-04-10 devnull function (see below).
102 cfa37a7b 2004-04-10 devnull structure itself provides much of the setup interface.
105 cfa37a7b 2004-04-10 devnull .ta \w'\fL 'u +\w'\fLulong 'u +\w'\fLlastcompact; 'u
106 cfa37a7b 2004-04-10 devnull typedef struct Pool Pool;
107 cfa37a7b 2004-04-10 devnull struct Pool {
108 cfa37a7b 2004-04-10 devnull char* name;
109 cfa37a7b 2004-04-10 devnull ulong maxsize; /* of entire Pool */
110 cfa37a7b 2004-04-10 devnull ulong cursize; /* of Pool */
111 cfa37a7b 2004-04-10 devnull ulong curfree; /* total free bytes in Pool */
112 cfa37a7b 2004-04-10 devnull ulong curalloc; /* total allocated bytes in Pool */
113 cfa37a7b 2004-04-10 devnull ulong minarena; /* smallest size of new arena */
114 cfa37a7b 2004-04-10 devnull ulong quantum; /* allocated blocks should be multiple of */
115 cfa37a7b 2004-04-10 devnull ulong minblock; /* smallest newly allocated block */
116 cfa37a7b 2004-04-10 devnull int flags;
117 cfa37a7b 2004-04-10 devnull int nfree; /* number of calls to free */
118 cfa37a7b 2004-04-10 devnull int lastcompact; /* nfree at time of last poolcompact */
119 cfa37a7b 2004-04-10 devnull void* (*alloc)(ulong);
120 cfa37a7b 2004-04-10 devnull int (*merge)(void*, void*);
121 cfa37a7b 2004-04-10 devnull void (*move)(void* from, void* to);
122 cfa37a7b 2004-04-10 devnull void (*lock)(Pool*);
123 cfa37a7b 2004-04-10 devnull void (*unlock)(Pool*);
124 cfa37a7b 2004-04-10 devnull void (*print)(Pool*, char*, ...);
125 cfa37a7b 2004-04-10 devnull void (*panic)(Pool*, char*, ...);
126 cfa37a7b 2004-04-10 devnull void (*logstack)(Pool*);
127 cfa37a7b 2004-04-10 devnull void* private;
129 cfa37a7b 2004-04-10 devnull .ta \w'\fL 'u +\w'POOL_ANTAGONISM 'u
130 cfa37a7b 2004-04-10 devnull enum { /* flags */
131 cfa37a7b 2004-04-10 devnull POOL_ANTAGONISM = 1<<0,
132 cfa37a7b 2004-04-10 devnull POOL_PARANOIA = 1<<1,
133 cfa37a7b 2004-04-10 devnull POOL_VERBOSITY = 1<<2,
134 cfa37a7b 2004-04-10 devnull POOL_DEBUGGING = 1<<3,
135 cfa37a7b 2004-04-10 devnull POOL_LOGGING = 1<<4,
136 cfa37a7b 2004-04-10 devnull POOL_TOLERANCE = 1<<5,
137 cfa37a7b 2004-04-10 devnull POOL_NOREUSE = 1<<6,
141 cfa37a7b 2004-04-10 devnull The pool obtains arenas of memory to manage by calling the the given
142 cfa37a7b 2004-04-10 devnull .B alloc
143 cfa37a7b 2004-04-10 devnull routine.
144 cfa37a7b 2004-04-10 devnull The total number of requested bytes will not exceed
145 cfa37a7b 2004-04-10 devnull .BR maxsize .
146 cfa37a7b 2004-04-10 devnull Each allocation request will be for at least
147 cfa37a7b 2004-04-10 devnull .B minarena
150 cfa37a7b 2004-04-10 devnull When a new arena is allocated, the pool routines try to
151 cfa37a7b 2004-04-10 devnull merge it with the surrounding arenas, in an attempt to combat fragmentation.
153 cfa37a7b 2004-04-10 devnull .B merge
154 cfa37a7b 2004-04-10 devnull is non-nil, it is called with the addresses of two blocks from
155 cfa37a7b 2004-04-10 devnull .B alloc
156 cfa37a7b 2004-04-10 devnull that the pool routines suspect might be adjacent.
157 cfa37a7b 2004-04-10 devnull If they are not mergeable,
158 cfa37a7b 2004-04-10 devnull .B merge
159 cfa37a7b 2004-04-10 devnull must return zero.
160 cfa37a7b 2004-04-10 devnull If they are mergeable,
161 cfa37a7b 2004-04-10 devnull .B merge
162 cfa37a7b 2004-04-10 devnull should merge them into one block in its own bookkeeping
163 cfa37a7b 2004-04-10 devnull and return non-zero.
165 cfa37a7b 2004-04-10 devnull To ease fragmentation and make
166 cfa37a7b 2004-04-10 devnull block reuse easier, the sizes requested of the pool routines are rounded up to a multiple of
167 cfa37a7b 2004-04-10 devnull .B quantum
169 cfa37a7b 2004-04-10 devnull the carrying out requests.
170 cfa37a7b 2004-04-10 devnull If, after rounding, the block size is still less than
171 cfa37a7b 2004-04-10 devnull .B minblock
173 cfa37a7b 2004-04-10 devnull .B minblock
174 cfa37a7b 2004-04-10 devnull will be used as the block size.
176 cfa37a7b 2004-04-10 devnull .I Poolcompact
177 cfa37a7b 2004-04-10 devnull defragments the pool, moving blocks in order to aggregate
178 cfa37a7b 2004-04-10 devnull the free space.
179 cfa37a7b 2004-04-10 devnull Each time it moves a block, it notifies the
181 cfa37a7b 2004-04-10 devnull routine that the contents have moved.
182 cfa37a7b 2004-04-10 devnull At the time that
184 cfa37a7b 2004-04-10 devnull is called, the contents have already moved,
187 cfa37a7b 2004-04-10 devnull should never be dereferenced.
190 cfa37a7b 2004-04-10 devnull routine is supplied (i.e. it is nil), then calling
191 cfa37a7b 2004-04-10 devnull .I poolcompact
192 cfa37a7b 2004-04-10 devnull is a no-op.
194 cfa37a7b 2004-04-10 devnull When the pool routines need to allocate a new arena but cannot,
195 cfa37a7b 2004-04-10 devnull either because
196 cfa37a7b 2004-04-10 devnull .B alloc
197 cfa37a7b 2004-04-10 devnull has returned nil or because doing so would use more than
198 cfa37a7b 2004-04-10 devnull .B maxsize
200 cfa37a7b 2004-04-10 devnull .I poolcompact
201 cfa37a7b 2004-04-10 devnull is called once to defragment the memory
202 cfa37a7b 2004-04-10 devnull and the request is retried.
204 cfa37a7b 2004-04-10 devnull .I Pools
205 cfa37a7b 2004-04-10 devnull are protected by the pool routines calling
207 cfa37a7b 2004-04-10 devnull (when non-nil)
208 cfa37a7b 2004-04-10 devnull before modifying the pool, and
210 cfa37a7b 2004-04-10 devnull .B unlock
211 cfa37a7b 2004-04-10 devnull when finished.
213 cfa37a7b 2004-04-10 devnull When internal corruption is detected,
214 cfa37a7b 2004-04-10 devnull .B panic
215 cfa37a7b 2004-04-10 devnull is called with a
216 bf8a59fa 2004-04-11 devnull .IR print (3)
217 cfa37a7b 2004-04-10 devnull style argument that specifies what happened.
218 cfa37a7b 2004-04-10 devnull It is assumed that
219 cfa37a7b 2004-04-10 devnull .B panic
220 cfa37a7b 2004-04-10 devnull never returns.
221 cfa37a7b 2004-04-10 devnull When the pool routines wish to convey a message
222 cfa37a7b 2004-04-10 devnull to the caller (usually because logging is turned on; see below),
223 cfa37a7b 2004-04-10 devnull .B print
224 cfa37a7b 2004-04-10 devnull is called, also with a
225 bf8a59fa 2004-04-11 devnull .IR print (3)
226 cfa37a7b 2004-04-10 devnull style argument.
228 cfa37a7b 2004-04-10 devnull .B Flags
229 cfa37a7b 2004-04-10 devnull is a bit vector that tweaks the behavior of the pool routines
230 cfa37a7b 2004-04-10 devnull in various ways.
231 cfa37a7b 2004-04-10 devnull Most are useful for debugging in one way or another.
233 cfa37a7b 2004-04-10 devnull .B POOL_ANTAGONISM
235 cfa37a7b 2004-04-10 devnull .I poolalloc
236 cfa37a7b 2004-04-10 devnull fills blocks with non-zero garbage before releasing them to the user,
238 cfa37a7b 2004-04-10 devnull .I poolfree
239 cfa37a7b 2004-04-10 devnull fills the blocks on receipt.
240 cfa37a7b 2004-04-10 devnull This tickles both user programs and the innards of the allocator.
241 cfa37a7b 2004-04-10 devnull Specifically, each 32-bit word of the memory is marked with a pointer value exclusive-or'ed
242 cfa37a7b 2004-04-10 devnull with a constant.
243 cfa37a7b 2004-04-10 devnull The pointer value is the pointer to the beginning of the allocated block
244 cfa37a7b 2004-04-10 devnull and the constant varies in order to distinguish different markings.
245 cfa37a7b 2004-04-10 devnull Freed blocks use the constant
246 cfa37a7b 2004-04-10 devnull .BR 0xF7000000 ,
247 cfa37a7b 2004-04-10 devnull newly allocated blocks
248 cfa37a7b 2004-04-10 devnull .BR 0xF9000000 ,
249 cfa37a7b 2004-04-10 devnull and newly created unallocated blocks
250 cfa37a7b 2004-04-10 devnull .BR 0xF1000000 .
251 cfa37a7b 2004-04-10 devnull For example, if
252 cfa37a7b 2004-04-10 devnull .B POOL_ANTAGONISM
253 cfa37a7b 2004-04-10 devnull is set and
254 cfa37a7b 2004-04-10 devnull .I poolalloc
255 cfa37a7b 2004-04-10 devnull returns a block starting at
256 cfa37a7b 2004-04-10 devnull .BR 0x00012345 ,
257 cfa37a7b 2004-04-10 devnull each word of the block will contain the value
258 cfa37a7b 2004-04-10 devnull .BR 0xF90012345 .
259 cfa37a7b 2004-04-10 devnull Recognizing these numbers in memory-related crashes can
260 cfa37a7b 2004-04-10 devnull help diagnose things like double-frees or dangling pointers.
263 cfa37a7b 2004-04-10 devnull .B POOL_PARANOIA
264 cfa37a7b 2004-04-10 devnull causes the allocator to walk the entire pool whenever locking or unlocking itself,
265 cfa37a7b 2004-04-10 devnull looking for corruption.
266 cfa37a7b 2004-04-10 devnull This slows runtime by a few orders of magnitude
267 cfa37a7b 2004-04-10 devnull when many blocks are in use.
269 cfa37a7b 2004-04-10 devnull .B POOL_VERBOSITY
271 cfa37a7b 2004-04-10 devnull the entire pool structure is printed
273 cfa37a7b 2004-04-10 devnull .BR print )
274 cfa37a7b 2004-04-10 devnull each time the pool is locked or unlocked.
275 cfa37a7b 2004-04-10 devnull .B POOL_DEBUGGING
276 cfa37a7b 2004-04-10 devnull enables internal
277 cfa37a7b 2004-04-10 devnull debugging output,
278 cfa37a7b 2004-04-10 devnull whose format is unspecified and volatile.
279 cfa37a7b 2004-04-10 devnull It should not be used by most programs.
281 cfa37a7b 2004-04-10 devnull .B POOL_LOGGING
282 cfa37a7b 2004-04-10 devnull is set, a single line is printed via
283 cfa37a7b 2004-04-10 devnull .B print
284 cfa37a7b 2004-04-10 devnull at the beginning and end of each pool call.
286 cfa37a7b 2004-04-10 devnull .B logstack
287 cfa37a7b 2004-04-10 devnull is not nil,
288 cfa37a7b 2004-04-10 devnull it will be called as well.
289 cfa37a7b 2004-04-10 devnull This provides a mechanism for external programs to search for leaks.
291 cfa37a7b 2004-04-10 devnull .IR leak (1)
292 cfa37a7b 2004-04-10 devnull for one such program.)
294 cfa37a7b 2004-04-10 devnull The pool routines are strict about the amount of space callers use.
295 cfa37a7b 2004-04-10 devnull If even a single byte is written past the end of the allotted space of a block, they
296 cfa37a7b 2004-04-10 devnull will notice when that block is next used in a call to
297 cfa37a7b 2004-04-10 devnull .I poolrealloc
300 cfa37a7b 2004-04-10 devnull (or at the next entry into the allocator, when
301 cfa37a7b 2004-04-10 devnull .B POOL_PARANOIA
302 cfa37a7b 2004-04-10 devnull is set),
304 cfa37a7b 2004-04-10 devnull .B panic
305 cfa37a7b 2004-04-10 devnull will be called.
306 cfa37a7b 2004-04-10 devnull Since forgetting to allocate space for the
307 cfa37a7b 2004-04-10 devnull terminating NUL on strings is such a common error,
309 cfa37a7b 2004-04-10 devnull .B POOL_TOLERANCE
310 cfa37a7b 2004-04-10 devnull is set and a single NUL is found written past the end of a block,
311 cfa37a7b 2004-04-10 devnull .B print
312 cfa37a7b 2004-04-10 devnull will be called with a notification, but
313 cfa37a7b 2004-04-10 devnull .B panic
314 cfa37a7b 2004-04-10 devnull will not be.
317 cfa37a7b 2004-04-10 devnull .B POOL_NOREUSE
319 cfa37a7b 2004-04-10 devnull .B poolfree
320 cfa37a7b 2004-04-10 devnull fills the passed block with garbage rather than
321 cfa37a7b 2004-04-10 devnull return it to the free pool.
322 cfa37a7b 2004-04-10 devnull .SH SOURCE
323 cfa37a7b 2004-04-10 devnull .B /sys/src/libc/port/pool.c
324 cfa37a7b 2004-04-10 devnull .SH SEE ALSO
325 bf8a59fa 2004-04-11 devnull .IR malloc (3),
326 bf8a59fa 2004-04-11 devnull .IR brk (3)
328 cfa37a7b 2004-04-10 devnull .B /sys/src/libc/port/malloc.c
329 cfa37a7b 2004-04-10 devnull is a complete example.
