1
0

node.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507
  1. /*
  2. * node.c
  3. */
  4. #include <stdio.h>
  5. #include <string.h>
  6. #include <assert.h>
  7. #include "private.h"
  8. #include "context.h"
  9. #include "node.h"
  10. int lub_heap_leak_verbose = 0;
  11. /*--------------------------------------------------------- */
  12. int
  13. lub_heap_node_compare(const void *clientnode,
  14. const void *clientkey)
  15. {
  16. const lub_heap_node_t * node = clientnode;
  17. const lub_heap_node_key_t * key = clientkey;
  18. return ((long)node - (long)key->node);
  19. }
  20. /*--------------------------------------------------------- */
  21. /* we simply use the node address as the index */
  22. void
  23. lub_heap_node_getkey(const void *clientnode,
  24. lub_bintree_key_t *key)
  25. {
  26. lub_heap_node_key_t clientkey;
  27. clientkey.node = clientnode;
  28. memcpy(key,&clientkey,sizeof(lub_heap_node_key_t));
  29. }
  30. /*--------------------------------------------------------- */
  31. static void
  32. lub_heap_node_meta_init(void)
  33. {
  34. static bool_t initialised = BOOL_FALSE;
  35. if(BOOL_FALSE == initialised)
  36. {
  37. lub_heap_leak_t *leak = lub_heap_leak_instance();
  38. initialised = BOOL_TRUE;
  39. /* initialise the node tree */
  40. lub_bintree_init(&leak->m_node_tree,
  41. offsetof(lub_heap_node_t,bt_node),
  42. lub_heap_node_compare,
  43. lub_heap_node_getkey);
  44. /* initialise the clear node tree */
  45. lub_bintree_init(&leak->m_clear_node_tree,
  46. offsetof(lub_heap_node_t,bt_node),
  47. lub_heap_node_compare,
  48. lub_heap_node_getkey);
  49. lub_heap_leak_release(leak);
  50. }
  51. }
  52. /*--------------------------------------------------------- */
  53. void
  54. lub_heap_node_init(lub_heap_node_t * this,
  55. lub_heap_context_t * context)
  56. {
  57. lub_heap_node_meta_init();
  58. /* initialise the control blocks */
  59. lub_bintree_node_init(&this->bt_node);
  60. lub_heap_node__set_context(this,context);
  61. lub_heap_node__set_leaked(this,BOOL_FALSE);
  62. lub_heap_node__set_partial(this,BOOL_FALSE);
  63. lub_heap_node__set_next(this,NULL);
  64. lub_heap_node__set_scanned(this,BOOL_FALSE);
  65. this->prev = NULL;
  66. {
  67. lub_heap_leak_t *leak = lub_heap_leak_instance();
  68. /* add this to the node tree */
  69. lub_bintree_insert(context ? &leak->m_node_tree : &leak->m_clear_node_tree,this);
  70. lub_heap_leak_release(leak);
  71. }
  72. if(context)
  73. {
  74. /* add ourselves to this context */
  75. lub_heap_context_insert_node(context,this);
  76. /* maintain the leak statistics */
  77. ++context->allocs;
  78. context->alloc_bytes += lub_heap_node__get_size(this);
  79. context->alloc_overhead += lub_heap_node__get_overhead(this);
  80. }
  81. }
  82. /*--------------------------------------------------------- */
  83. void
  84. lub_heap_node_fini(lub_heap_node_t * this)
  85. {
  86. /* remove this node from this context */
  87. lub_heap_node_clear(this,0);
  88. {
  89. lub_heap_leak_t *leak = lub_heap_leak_instance();
  90. /* remove this from the clear_node tree */
  91. lub_bintree_remove(&leak->m_clear_node_tree,this);
  92. lub_heap_leak_release(leak);
  93. }
  94. }
  95. /*--------------------------------------------------------- */
  96. size_t
  97. lub_heap_node__get_instanceSize(void)
  98. {
  99. return sizeof(lub_heap_node_t);
  100. }
  101. /*--------------------------------------------------------- */
  102. size_t
  103. lub_heap_node__get_size(const lub_heap_node_t *this)
  104. {
  105. size_t size = lub_heap__get_block_size(lub_heap_node__get_context(this)->heap,this);
  106. size -= sizeof(lub_heap_node_t);
  107. return size;
  108. }
  109. /*--------------------------------------------------------- */
  110. size_t
  111. lub_heap_node__get_overhead(const lub_heap_node_t *this)
  112. {
  113. size_t overhead;
  114. overhead = lub_heap__get_block_overhead(lub_heap_node__get_context(this)->heap,
  115. lub_heap_node__get_ptr(this));
  116. overhead += sizeof(lub_heap_node_t);
  117. return overhead;
  118. }
  119. /*--------------------------------------------------------- */
  120. char *
  121. lub_heap_node__get_ptr(const lub_heap_node_t *this)
  122. {
  123. return (char*)&this[1];
  124. }
  125. /*--------------------------------------------------------- */
  126. bool_t
  127. lub_heap_validate_pointer(lub_heap_t *this,
  128. char *ptr)
  129. {
  130. bool_t result = BOOL_FALSE;
  131. do
  132. {
  133. lub_heap_segment_t *seg;
  134. if((0 < lub_heap_frame_count))
  135. {
  136. /*
  137. * When leak detection is enabled we can perform detailed
  138. * validation of pointers.
  139. */
  140. lub_heap_node_t *node = lub_heap_node_from_start_of_block_ptr(ptr);
  141. if(NULL != node)
  142. {
  143. lub_heap_context_t *context = lub_heap_node__get_context(node);
  144. /* we've found a context so can give a definative answer */
  145. if(this == context->heap)
  146. {
  147. result = BOOL_TRUE;
  148. }
  149. break;
  150. }
  151. }
  152. /* iterate around each of the segments belonging to this heap */
  153. for(seg = &this->first_segment;
  154. seg;
  155. seg = seg->next)
  156. {
  157. char *start = (char*)&seg[1];
  158. if(ptr >= start)
  159. {
  160. char *end = start + (seg->words << 2);
  161. if(ptr < end)
  162. {
  163. /* we've found a parent segment for this pointer */
  164. result = BOOL_TRUE;
  165. break;
  166. }
  167. }
  168. }
  169. } while(0);
  170. ptr = 0; /* don't leave a pointer on the stack */
  171. return result;
  172. }
  173. /*--------------------------------------------------------- */
  174. static lub_heap_node_t *
  175. _lub_heap_node_from_ptr(lub_bintree_t *tree,
  176. const char *ptr,
  177. bool_t start_of_block)
  178. {
  179. lub_heap_node_t *result = 0;
  180. if(tree->root)
  181. {
  182. lub_heap_node_key_t key;
  183. /* search for the node which comes immediately before this pointer */
  184. key.node = (lub_heap_node_t *)ptr;
  185. result = lub_bintree_findprevious(tree,&key);
  186. if(NULL != result)
  187. {
  188. char *tmp = lub_heap_node__get_ptr(result);
  189. /* ensure that the pointer is within the scope of this node */
  190. if(start_of_block)
  191. {
  192. if(ptr != tmp)
  193. {
  194. /*
  195. * this should be an exact match and isn't
  196. */
  197. result = NULL;
  198. }
  199. }
  200. else if(ptr < tmp)
  201. {
  202. /*
  203. * this is referencing part of the node header
  204. */
  205. result = NULL;
  206. }
  207. else
  208. {
  209. /* compare with the end of the allocated memory */
  210. tmp += lub_heap_node__get_size(result);
  211. /* ensure that the pointer is within the scope of this node */
  212. if(ptr >= tmp)
  213. {
  214. /* out of range of this node */
  215. result = NULL;
  216. }
  217. }
  218. tmp = 0; /* don't leave a pointer on the stack */
  219. }
  220. }
  221. ptr = 0; /* don't leave a pointer on the stack */
  222. return result;
  223. }
  224. /*--------------------------------------------------------- */
  225. lub_heap_node_t *
  226. lub_heap_node_from_start_of_block_ptr(char *ptr)
  227. {
  228. lub_heap_node_t *result = 0;
  229. if(lub_heap_leak_query_node_tree())
  230. {
  231. lub_heap_leak_t *leak = lub_heap_leak_instance();
  232. result = _lub_heap_node_from_ptr(&leak->m_node_tree,ptr,BOOL_TRUE);
  233. lub_heap_leak_release(leak);
  234. }
  235. if((0 == result) && lub_heap_leak_query_clear_node_tree())
  236. {
  237. lub_heap_leak_t *leak = lub_heap_leak_instance();
  238. result = _lub_heap_node_from_ptr(&leak->m_clear_node_tree,ptr,BOOL_TRUE);
  239. lub_heap_leak_release(leak);
  240. }
  241. ptr = 0; /* don't leave a pointer on the stack */
  242. return result;
  243. }
  244. /*--------------------------------------------------------- */
  245. void
  246. lub_heap_node__set_context(lub_heap_node_t *this,
  247. lub_heap_context_t *value)
  248. {
  249. unsigned long mask = ((unsigned long)value & ~(LEAKED_MASK | PARTIAL_MASK));
  250. this->_context = (lub_heap_context_t *)mask;
  251. }
  252. /*--------------------------------------------------------- */
  253. lub_heap_context_t *
  254. lub_heap_node__get_context(const lub_heap_node_t *this)
  255. {
  256. unsigned long mask = (unsigned long)this->_context & ~(LEAKED_MASK | PARTIAL_MASK);
  257. return (lub_heap_context_t *)mask;
  258. }
  259. /*--------------------------------------------------------- */
  260. void
  261. lub_heap_node__set_next(lub_heap_node_t *this,
  262. lub_heap_node_t *value)
  263. {
  264. unsigned long mask = ((unsigned long)value & ~(SCANNED_MASK));
  265. this->_next = (lub_heap_node_t *)mask;
  266. }
  267. /*--------------------------------------------------------- */
  268. lub_heap_node_t *
  269. lub_heap_node__get_next(const lub_heap_node_t *this)
  270. {
  271. unsigned long mask = (unsigned long)this->_next & ~(SCANNED_MASK);
  272. return (lub_heap_node_t *)mask;
  273. }
  274. /*--------------------------------------------------------- */
  275. bool_t
  276. lub_heap_node__get_leaked(const lub_heap_node_t *this)
  277. {
  278. return ((unsigned long)this->_context & LEAKED_MASK) ? BOOL_TRUE : BOOL_FALSE;
  279. }
  280. /*--------------------------------------------------------- */
  281. bool_t
  282. lub_heap_node__get_partial(const lub_heap_node_t *this)
  283. {
  284. return ((unsigned long)this->_context & PARTIAL_MASK) ? BOOL_TRUE : BOOL_FALSE;
  285. }
  286. /*--------------------------------------------------------- */
  287. bool_t
  288. lub_heap_node__get_scanned(const lub_heap_node_t *this)
  289. {
  290. return ((unsigned long)this->_next & SCANNED_MASK) ? BOOL_TRUE : BOOL_FALSE;
  291. }
  292. /*--------------------------------------------------------- */
  293. void
  294. lub_heap_node__set_leaked(lub_heap_node_t *this, bool_t value)
  295. {
  296. unsigned long mask = (unsigned long)this->_context;
  297. if(BOOL_TRUE == value)
  298. {
  299. mask |= LEAKED_MASK;
  300. }
  301. else
  302. {
  303. mask &= ~LEAKED_MASK;
  304. }
  305. this->_context = (lub_heap_context_t *)mask;
  306. }
  307. /*--------------------------------------------------------- */
  308. void
  309. lub_heap_node__set_partial(lub_heap_node_t *this, bool_t value)
  310. {
  311. unsigned long mask = (unsigned long)this->_context;
  312. if(BOOL_TRUE == value)
  313. {
  314. mask |= PARTIAL_MASK;
  315. }
  316. else
  317. {
  318. mask &= ~PARTIAL_MASK;
  319. }
  320. this->_context = (lub_heap_context_t *)mask;
  321. }
  322. /*--------------------------------------------------------- */
  323. void
  324. lub_heap_node__set_scanned(lub_heap_node_t *this, bool_t value)
  325. {
  326. unsigned long mask = (unsigned long)this->_next;
  327. if(BOOL_TRUE == value)
  328. {
  329. mask |= SCANNED_MASK;
  330. }
  331. else
  332. {
  333. mask &= ~SCANNED_MASK;
  334. }
  335. this->_next = (lub_heap_node_t *)mask;
  336. }
  337. /*--------------------------------------------------------- */
  338. void
  339. lub_heap_foreach_node(void (*fn)(lub_heap_node_t *,void*),
  340. void *arg)
  341. {
  342. lub_heap_leak_t *leak = lub_heap_leak_instance();
  343. lub_heap_node_t *node;
  344. lub_heap_node_key_t key;
  345. for(node = lub_bintree_findfirst(&leak->m_node_tree);
  346. node;
  347. node = lub_bintree_findnext(&leak->m_node_tree,&key))
  348. {
  349. lub_heap_leak_release(leak);
  350. lub_heap_node_getkey(node,(lub_bintree_key_t*)&key);
  351. /* invoke the specified method on this node */
  352. fn(node,arg);
  353. leak = lub_heap_leak_instance();
  354. }
  355. lub_heap_leak_release(leak);
  356. }
  357. /*--------------------------------------------------------- */
  358. void
  359. lub_heap_node_clear(lub_heap_node_t *this,
  360. void *arg)
  361. {
  362. /* clearing a node removes it from it's context */
  363. lub_heap_context_t *context = lub_heap_node__get_context(this);
  364. if(NULL != context)
  365. {
  366. lub_heap_leak_t *leak = lub_heap_leak_instance();
  367. /* remove from the node tree and place into the clear tree */
  368. lub_bintree_remove(&leak->m_node_tree,this);
  369. lub_bintree_insert(&leak->m_clear_node_tree,this);
  370. lub_heap_leak_release(leak);
  371. /* maintain the leak statistics */
  372. --context->allocs;
  373. context->alloc_bytes -= lub_heap_node__get_size(this);
  374. context->alloc_overhead -= lub_heap_node__get_overhead(this);
  375. lub_heap_node__set_context(this,NULL);
  376. lub_heap_node__set_leaked(this,BOOL_FALSE);
  377. lub_heap_node__set_partial(this,BOOL_FALSE);
  378. lub_heap_context_remove_node(context,this);
  379. }
  380. }
  381. /*--------------------------------------------------------- */
  382. #define RELEASE_COUNT 2048
  383. void
  384. lub_heap_scan_memory(const void *mem,
  385. size_t size)
  386. {
  387. size_t bytes_left = size;
  388. typedef const void *void_ptr;
  389. void_ptr *ptr,last_ptr = 0;
  390. lub_heap_leak_t *leak = lub_heap_leak_instance();
  391. unsigned release_count = RELEASE_COUNT;
  392. if(lub_heap_leak_verbose)
  393. {
  394. printf("lub_heap_scan_memory(%p,%"SIZE_FMT")\n",mem,size);
  395. }
  396. ++leak->m_stats.scanned;
  397. /* scan all the words in this allocated block of memory */
  398. for(ptr = (void_ptr*)mem;
  399. bytes_left;
  400. )
  401. {
  402. if(0 == --release_count)
  403. {
  404. /* make space for other memory tasks to get in... */
  405. lub_heap_leak_release(leak);
  406. leak = lub_heap_leak_instance();
  407. release_count = RELEASE_COUNT;
  408. }
  409. if(*ptr != last_ptr)
  410. {
  411. lub_heap_node_t *node;
  412. lub_heap_node_key_t key;
  413. /* search for a node */
  414. key.node = (lub_heap_node_t *)ptr;
  415. node = lub_bintree_find(&leak->m_node_tree,&key);
  416. if(NULL != node)
  417. {
  418. /*
  419. * If we stumble across a node don't scan it's contents as this could cause
  420. * false negatives. This situation could occur if an allocated block of memory
  421. * was used as a heap in it's own right.
  422. */
  423. char *tmp = lub_heap_node__get_ptr(node);
  424. size_t node_size = lub_heap_node__get_size(node);
  425. /* skip forward past the node contents */
  426. ptr = (void_ptr*)(tmp + node_size);
  427. bytes_left -= (node_size + sizeof(lub_heap_node_t));
  428. tmp = 0; /* don't leave pointers on our stack */
  429. last_ptr = 0;
  430. continue;
  431. }
  432. /*
  433. * see whether this is a reference to a node
  434. * NB. we only resolve a node if the pointer lies
  435. * within the memory allocated to the client; any direct
  436. * references to nodes will not resolve to a node
  437. * object.
  438. */
  439. node = _lub_heap_node_from_ptr(&leak->m_node_tree,*ptr,BOOL_FALSE);
  440. if( (NULL != node))
  441. {
  442. /* this looks like a valid node */
  443. lub_heap_context_t *context = lub_heap_node__get_context(node);
  444. size_t node_size = lub_heap_node__get_size(node);
  445. size_t node_overhead = lub_heap_node__get_overhead(node);
  446. char *tmp = lub_heap_node__get_ptr(node);
  447. if(tmp == *ptr)
  448. {
  449. /* reference to start of block */
  450. if(BOOL_TRUE == lub_heap_node__get_partial(node))
  451. {
  452. lub_heap_node__set_partial(node,BOOL_FALSE);
  453. if(NULL != context)
  454. {
  455. --context->partials;
  456. context->partial_bytes -= node_size;
  457. context->partial_overhead -= node_overhead;
  458. }
  459. }
  460. }
  461. tmp = 0; /* don't leave pointers on our stack */
  462. /* this is definately not a leak */
  463. if(BOOL_TRUE == lub_heap_node__get_leaked(node))
  464. {
  465. lub_heap_node__set_leaked(node,BOOL_FALSE);
  466. if(NULL != context)
  467. {
  468. --context->leaks;
  469. context->leaked_bytes -= node_size;
  470. context->leaked_overhead -= node_overhead;
  471. --leak->m_stats.leaks;
  472. leak->m_stats.leaked_bytes -= node_size;
  473. leak->m_stats.leaked_overhead -= node_overhead;
  474. }
  475. }
  476. }
  477. }
  478. last_ptr = *ptr++;
  479. bytes_left -= sizeof(void*);
  480. }
  481. lub_heap_leak_release(leak);
  482. last_ptr = ptr = 0; /* don't leave pointers on the stack */
  483. }
  484. /*--------------------------------------------------------- */