1
0

pool 7.9 KB

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