1
0

private.h 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451
  1. /*
  2. * private.h
  3. */
  4. #include "lub/heap.h"
  5. #include "lub/bintree.h"
  6. #include "lub/types.h"
  7. #include "lub/dblockpool.h"
  8. #include "lub/size_fmt.h"
  9. /**********************************************************
  10. * PRIVATE TYPES
  11. ********************************************************** */
  12. typedef struct _lub_heap_node lub_heap_node_t;
  13. typedef struct _lub_heap_context lub_heap_context_t;
  14. typedef struct _lub_heap_cache lub_heap_cache_t;
  15. typedef enum {
  16. LUB_HEAP_TAINT_INITIAL = 0xBB,
  17. LUB_HEAP_TAINT_FREE = 0xFF,
  18. LUB_HEAP_TAINT_ALLOC = 0xAA
  19. } lub_heap_taint_t;
  20. typedef struct _lub_heap_stackframe stackframe_t;
  21. /**********************************************************
  22. * PRIVATE TYPES
  23. ********************************************************** */
  24. /* type to indicate the number of long words in a block */
  25. typedef unsigned long words_t;
  26. typedef struct lub_heap_tag_s lub_heap_tag_t;
  27. typedef struct lub_heap_segment_s lub_heap_segment_t;
  28. typedef union lub_heap_block_u lub_heap_block_t;
  29. typedef struct lub_heap_alloc_block_s lub_heap_alloc_block_t;
  30. /*
  31. * a special type which hold both a size and block type
  32. */
  33. struct lub_heap_tag_s {
  34. unsigned free:1; /* indicates whether free/alloc block */
  35. unsigned segment:1; /* indicates boundary of segment */
  36. unsigned words:30; /* number of 4 byte words in block */
  37. };
  38. typedef struct lub_heap_key_s lub_heap_key_t;
  39. struct lub_heap_key_s {
  40. words_t words;
  41. const lub_heap_free_block_t *block;
  42. };
  43. /*
  44. * A specialisation of a generic block to hold free block information
  45. */
  46. struct lub_heap_free_block_s {
  47. lub_heap_tag_t tag;
  48. /*
  49. * node to hold this block in the size based binary tree
  50. */
  51. lub_bintree_node_t bt_node;
  52. /* space holder for the trailing tag */
  53. lub_heap_tag_t _tail;
  54. };
  55. /*
  56. * A specialisation of a generic block to hold free block information
  57. */
  58. struct lub_heap_alloc_block_s {
  59. lub_heap_tag_t tag;
  60. /* space holder for trailing tag */
  61. lub_heap_tag_t memory[1];
  62. };
  63. /* a generic block instance */
  64. union lub_heap_block_u {
  65. lub_heap_alloc_block_t alloc;
  66. lub_heap_free_block_t free;
  67. };
  68. /*
  69. * This is the control block for a segment
  70. */
  71. struct lub_heap_segment_s {
  72. lub_heap_segment_t *next;
  73. words_t words;
  74. lub_bintree_node_t bt_node;
  75. };
  76. /*
  77. * This is the control block assigned to represent the heap instance
  78. */
  79. struct lub_heap_s {
  80. /*
  81. * A cache control block if one exists
  82. */
  83. lub_heap_cache_t *cache;
  84. /*
  85. * A binary tree of free blocks
  86. */
  87. lub_bintree_t free_tree;
  88. /*
  89. * This is used to supress leak tracking
  90. */
  91. unsigned long suppress;
  92. /*
  93. * statistics for this heap
  94. */
  95. lub_heap_stats_t stats;
  96. /*
  97. * reference to next heap in the system
  98. */
  99. struct lub_heap_s *next;
  100. /*
  101. * reference to next segment (this must be last in the structure)
  102. */
  103. lub_heap_segment_t first_segment;
  104. };
  105. /*---------------------------------------------------------
  106. * PRIVATE META DATA
  107. *--------------------------------------------------------- */
  108. /*
  109. * a pointer to the start of data segment
  110. */
  111. extern char *lub_heap_data_start;
  112. /*
  113. * a pointer to the end of data segment
  114. */
  115. extern char *lub_heap_data_end;
  116. /*---------------------------------------------------------
  117. * PRIVATE META FUNCTIONS
  118. *--------------------------------------------------------- */
  119. /*
  120. * This operation sends to STDOUT the textual representation
  121. * of the provided address in memory.
  122. */
  123. extern void lub_heap_symShow(
  124. /*
  125. * The address of the function name to resolve
  126. */
  127. unsigned address);
  128. /*
  129. * This operation indicates whether the function represented by the
  130. * specified address contains the specified string.
  131. */
  132. extern bool_t lub_heap_symMatch(
  133. /*
  134. * The address of the function name to resolve
  135. */
  136. unsigned address,
  137. /*
  138. * The substring to match against
  139. */
  140. const char *substring);
  141. /*
  142. * This operation fills out the current stackframe
  143. */
  144. extern void lub_heap__get_stackframe(stackframe_t * stack, unsigned max);
  145. /*
  146. * A platform implementation should scan the BSS section
  147. * for any memory references.
  148. */
  149. extern void lub_heap_scan_bss(void);
  150. /*
  151. * A platform implementation should scan the DATA section
  152. * for any memory references.
  153. */
  154. extern void lub_heap_scan_data(void);
  155. /*
  156. * If possible a platform implementation should scan the current
  157. * stack for any memory references.
  158. * NB. if a platform happens to have allocated it stack from the
  159. * BSS or DATA section then this doesn't need to do anything.
  160. */
  161. extern void lub_heap_scan_stack(void);
  162. /*
  163. * This function fills out the specified memory with tainted
  164. * bytes if tainting is enabled for the system.
  165. */
  166. extern void lub_heap_taint_memory(
  167. /*
  168. * a pointer to the start of the memory to taint
  169. */
  170. char *ptr,
  171. /*
  172. * the type of tainting to perform
  173. */
  174. lub_heap_taint_t type,
  175. /*
  176. * the number of bytes to taint
  177. */
  178. size_t size);
  179. /*
  180. * If possible a platform implementation should
  181. * take this oportunity to write the value 0xCC
  182. * to all the stacks between the high water mark
  183. * and the current stack pointer.
  184. * This prevents any pointer droppings from hiding
  185. * memory leaks.
  186. */
  187. extern void lub_heap_clean_stacks(void);
  188. /*---------------------------------------------------------
  189. * PRIVATE METHODS
  190. *--------------------------------------------------------- */
  191. /*
  192. * This operation is the raw interface for allocating/releasing memory
  193. * to/from the dynamic heap. Memory allocated by this call will not be
  194. * monitored by the leak detection code.
  195. *
  196. * It changes the size of the object referenced by a passed in
  197. * pointer to "size". The contents will be unchanged up to the minimum of the old
  198. * and new sizes. If the new size is larger, the new space is uninitialised.
  199. *
  200. * \pre
  201. * - The heap needs to have been created with an initial memory segment.
  202. * - If "*ptr" contains a non-NULL value then this MUST have
  203. * been allocated using this operation, from the same heap instance.
  204. *
  205. * \return
  206. * - the status of the operation.
  207. *
  208. * \post
  209. * - The client takes responsiblity for releasing any allocated memory when they
  210. * are finished with it.
  211. * - If *ptr contains a non-NULL value, then after a succesfull call, the
  212. * initial memory referenced by it may have been released for reuse,
  213. * and the pointer modified to reference some new memory.
  214. * - *ptr may contain NULL in which case no memory will be released back to the
  215. * heap for reuse, and the pointer is filled out with the allocated memory.
  216. * - (size == 0) No new memory will be allocated, *ptr will be set to NULL,
  217. * and any original memory referenced by it will have been released.
  218. */
  219. extern lub_heap_status_t lub_heap_raw_realloc(
  220. /*
  221. * The heap instance.
  222. */
  223. lub_heap_t * instance,
  224. /*
  225. * A reference to the client pointer which was previously handed out.
  226. */
  227. char **ptr,
  228. /*
  229. * The size of the requested memory
  230. */
  231. size_t size,
  232. /*
  233. * The alignment of the requested memory
  234. */
  235. lub_heap_align_t
  236. alignment);
  237. /*
  238. * This is called before an actual realloc operation runs.
  239. * It provides the opportunity for the leak detector to release
  240. * any previous details and to modify the size and pointer to account
  241. * for its internal overheads.
  242. *
  243. * \return
  244. * The number of bytes which should be allocated by the realloc call.
  245. *
  246. * \post
  247. * - the 'node' currently held in the database will be removed, potentially
  248. * deleting the 'context' in the process.
  249. * - the leak_detector will note the fact that it is wrapping a realloc
  250. * call and any further calls which are invoked during the process will
  251. * NOT be monitored.
  252. */
  253. extern void lub_heap_pre_realloc(
  254. /*
  255. * The heap instance.
  256. */
  257. lub_heap_t * instance,
  258. /*
  259. * A reference to the client pointer which was previously handed out.
  260. */
  261. char **ptr,
  262. /*
  263. * A reference to the size of the requested memory
  264. */
  265. size_t * size);
  266. /*
  267. * This is called after a realloc has been done, just before the results
  268. * are returned to the client.
  269. * It provides the opportunity for the leak detector to store details
  270. * on the allocation and track it.
  271. *
  272. * \return
  273. * The pointer which should be returned to the client. This will skip any
  274. * housekeeping details which will have been added to the start of the
  275. * block.
  276. *
  277. * \post
  278. * - the 'node' currently will be added into the database, creating a
  279. * context if appropriate.
  280. * - the leak_detector will note the fact that the wrapping of a realloc()
  281. * call has completed and will start to monitor further calls again.
  282. */
  283. extern void lub_heap_post_realloc(
  284. /*
  285. * The heap instance
  286. */
  287. lub_heap_t * instance,
  288. /*
  289. * A reference to the client pointer which has been allocated.
  290. */
  291. char **ptr);
  292. /*
  293. * This function clears all the current leak information from the heap
  294. *
  295. * It is also used to define the number of stack frames which are
  296. * used to specify a context.
  297. *
  298. */
  299. void lub_heap_clearAll(
  300. /*
  301. * The heap instance
  302. */
  303. lub_heap_t * instance,
  304. /*
  305. * The number of stack frames to account for when evaluating
  306. * a context. A value of zero means "don't change"
  307. */
  308. unsigned frames);
  309. /*
  310. * This allows the tracking of allocation failures.
  311. */
  312. void lub_heap_alloc_failed(lub_heap_context_t * instance);
  313. /*
  314. * This allows the tracking of free failures.
  315. */
  316. void lub_heap_free_failed(void);
  317. /*
  318. * This method slices the specified number of words off the
  319. * bottom of the specified free block.
  320. * The original block is then shrunk appropriately and the
  321. * address of the new free block updated accordingly.
  322. * The result returned is a pointer to the requested memory.
  323. * If the slice cannot be taken then NULL is returned and the
  324. * free block is unaltered.
  325. *
  326. * It is assumed that the free block has been removed from the
  327. * tree prior to calling this method.
  328. */
  329. extern void *lub_heap_slice_from_bottom(lub_heap_t * instance,
  330. lub_heap_free_block_t ** ptr_block,
  331. words_t * words, bool_t seg_start);
  332. /*
  333. * This method slices the specified number of words off the
  334. * top of the current free block.
  335. * The block is then shrunk appropriately and the assigned memory
  336. * is returned. The client's free block pointer is updated accordingly
  337. * e.g. if the request absorbs all of the free_block the client's
  338. * pointer is set to NULL.
  339. * If there is insufficient space to slice this free block then
  340. * NULL is returned and the free block is unaltered.
  341. */
  342. extern void *lub_heap_slice_from_top(lub_heap_t * instance,
  343. lub_heap_free_block_t ** ptr_block,
  344. words_t * words, bool_t seg_end);
  345. /*
  346. * This method initialises a free block from some specified memory.
  347. */
  348. extern void
  349. lub_heap_init_free_block(lub_heap_t * instance,
  350. void *ptr,
  351. size_t size, bool_t seg_start, bool_t seg_end);
  352. /*
  353. * This method takes an existing allocated block and extends it by
  354. * trying to take memory from a free block immediately
  355. * above it
  356. */
  357. extern bool_t
  358. lub_heap_extend_upwards(lub_heap_t * instance,
  359. lub_heap_block_t ** block, words_t words);
  360. /*
  361. * This method takes an existing allocated block and extends it by
  362. * trying to take memory from a free block immediately
  363. * below it
  364. */
  365. extern bool_t
  366. lub_heap_extend_downwards(lub_heap_t * instance,
  367. lub_heap_block_t ** block, words_t words);
  368. /*
  369. * This method takes an existing allocated block and extends it by
  370. * trying to take memory from free blocks immediately
  371. * above and below it.
  372. */
  373. extern bool_t
  374. lub_heap_extend_both_ways(lub_heap_t * instance,
  375. lub_heap_block_t ** block, words_t words);
  376. /*
  377. * This method creates a new alloc block from the specified heap
  378. */
  379. extern void *lub_heap_new_alloc_block(lub_heap_t * instance, words_t words);
  380. extern void
  381. lub_heap_graft_to_top(lub_heap_t * instance,
  382. lub_heap_block_t * free_block,
  383. void *ptr,
  384. words_t words, bool_t seg_end, bool_t other_free_block);
  385. extern void
  386. lub_heap_graft_to_bottom(lub_heap_t * instance,
  387. lub_heap_block_t * free_block,
  388. void *ptr,
  389. words_t words,
  390. bool_t seg_start, bool_t other_free_block);
  391. extern lub_heap_status_t
  392. lub_heap_merge_with_next(lub_heap_t * instance, lub_heap_block_t * block);
  393. extern lub_heap_status_t
  394. lub_heap_merge_with_previous(lub_heap_t * instance, lub_heap_block_t * block);
  395. extern lub_heap_status_t
  396. lub_heap_new_free_block(lub_heap_t * instance, lub_heap_block_t * block);
  397. /*
  398. * Given a block reference find the trailing tag
  399. */
  400. extern lub_heap_tag_t *lub_heap_block__get_tail(lub_heap_block_t * block);
  401. /*
  402. * Find the first block reference in the specified segment
  403. */
  404. lub_heap_block_t *lub_heap_block_getfirst(const lub_heap_segment_t * seg);
  405. /*
  406. * Given a block reference find the next one
  407. */
  408. extern lub_heap_block_t *lub_heap_block_getnext(lub_heap_block_t * block);
  409. /*
  410. * Given a block reference find the previous one
  411. */
  412. extern lub_heap_block_t *lub_heap_block_getprevious(lub_heap_block_t * block);
  413. /*
  414. * This checks the integrity of the current block
  415. * If the header and trailer values are different then
  416. * some form of memory corruption must have occured.
  417. */
  418. extern bool_t lub_heap_block_check(lub_heap_block_t * block);
  419. extern void
  420. lub_heap_block_getkey(const void *clientnode, lub_bintree_key_t * key);
  421. extern void lub_heap_scan_all(void);
  422. extern bool_t lub_heap_check_memory(lub_heap_t * instance);
  423. extern lub_heap_block_t *lub_heap_block_from_ptr(char *ptr);
  424. extern const lub_heap_segment_t *lub_heap_segment_findnext(const void *address);
  425. extern void
  426. lub_heap_align_block(lub_heap_t * this,
  427. lub_heap_align_t alignment, char **ptr, size_t * size);
  428. lub_heap_status_t
  429. lub_heap_cache_realloc(lub_heap_t * this, char **ptr, size_t requested_size);
  430. void lub_heap_cache_show(lub_heap_cache_t * this);