pool 8.4 KB

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