pool 8.4 KB

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