1
0

heap_raw_realloc.c 6.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238
  1. #include <string.h>
  2. #include <assert.h>
  3. #include "private.h"
  4. /*--------------------------------------------------------- */
  5. lub_heap_status_t
  6. lub_heap_raw_realloc(lub_heap_t * this,
  7. char **ptr,
  8. size_t requested_size, lub_heap_align_t alignment)
  9. {
  10. lub_heap_status_t result = LUB_HEAP_FAILED;
  11. lub_heap_block_t *block = NULL;
  12. words_t words;
  13. char *new_ptr = NULL;
  14. const size_t MIN_SIZE = sizeof(lub_heap_free_block_t);
  15. /* make the minimum alignment leave enough space for
  16. * (sizeof(lub_heap_free_block_t) + sizeof(lub_heap_alloc_block_t) + sizeof(lub_heap_node_t))
  17. * approx 72 bytes on 64-bit architecture
  18. */
  19. const lub_heap_align_t MIN_ALIGN_NON_NATIVE = LUB_HEAP_ALIGN_2_POWER_7;
  20. size_t size = requested_size;
  21. do {
  22. if (NULL == ptr)
  23. break; /* The client MUST give us a pointer to play with */
  24. if (LUB_HEAP_ZERO_ALLOC == *ptr) {
  25. *ptr = NULL;
  26. }
  27. if (*ptr
  28. && (BOOL_FALSE == lub_heap_validate_pointer(this, *ptr))) {
  29. /* This is not a valid pointer */
  30. result = LUB_HEAP_INVALID_POINTER;
  31. break;
  32. }
  33. /* check the heap integrity */
  34. if (BOOL_FALSE == lub_heap_check_memory(this)) {
  35. result = LUB_HEAP_CORRUPTED;
  36. break;
  37. }
  38. if (size) {
  39. /* make sure we get enough space for the header/tail */
  40. size += sizeof(lub_heap_alloc_block_t);
  41. /* make sure we are at least natively aligned */
  42. size += (LUB_HEAP_ALIGN_NATIVE - 1);
  43. size &= ~(LUB_HEAP_ALIGN_NATIVE - 1);
  44. if (size < MIN_SIZE) {
  45. /*
  46. * we must ensure that any allocated block is at least
  47. * large enough to hold a free block node when it is released
  48. */
  49. size = MIN_SIZE;
  50. }
  51. if (LUB_HEAP_ALIGN_NATIVE != alignment) {
  52. if (alignment < MIN_ALIGN_NON_NATIVE) {
  53. /*
  54. * ensure that we always leave enough space
  55. * to be able to collapse the block to the
  56. * right size
  57. */
  58. alignment = MIN_ALIGN_NON_NATIVE;
  59. }
  60. /* add twice the alignment */
  61. size += (alignment << 1);
  62. }
  63. }
  64. words = (size >> 2);
  65. if (requested_size > size) {
  66. /* the size has wrapped when accounting for overheads */
  67. break;
  68. }
  69. if (NULL != *ptr) {
  70. /* get reference to the current block */
  71. block = lub_heap_block_from_ptr(*ptr);
  72. /* first of all check this is an allocated block */
  73. if (1 == block->alloc.tag.free) {
  74. result = LUB_HEAP_DOUBLE_FREE;
  75. break;
  76. }
  77. /* first of all check this is an allocated block */
  78. if (BOOL_FALSE == lub_heap_block_check(block)) {
  79. result = LUB_HEAP_CORRUPTED;
  80. break;
  81. }
  82. /* is the current block large enough for the request */
  83. if (words && (block->alloc.tag.words >= words)) {
  84. lub_heap_block_t *next_block =
  85. lub_heap_block_getnext(block);
  86. words_t delta =
  87. (block->alloc.tag.words - words);
  88. lub_heap_tag_t *tail;
  89. result = LUB_HEAP_OK;
  90. new_ptr = *ptr;
  91. if (delta && (NULL != next_block)) {
  92. /* can we graft this spare memory to a following free block? */
  93. if (1 == next_block->free.tag.free) {
  94. block->alloc.tag.words = words;
  95. tail =
  96. lub_heap_block__get_tail
  97. (block);
  98. tail->words = words;
  99. tail->free = 0;
  100. tail->segment = 0;
  101. lub_heap_graft_to_bottom(this,
  102. next_block,
  103. &tail
  104. [1],
  105. delta,
  106. BOOL_FALSE,
  107. BOOL_FALSE);
  108. this->stats.alloc_bytes -=
  109. (delta << 2);
  110. break;
  111. }
  112. }
  113. /* Is there enough space to turn the spare memory into a free block? */
  114. if (delta >=
  115. (sizeof(lub_heap_free_block_t) >> 2)) {
  116. tail = lub_heap_block__get_tail(block);
  117. lub_heap_init_free_block(this,
  118. &tail[1 -
  119. delta],
  120. (delta << 2),
  121. BOOL_FALSE,
  122. tail->segment);
  123. block->alloc.tag.words = words;
  124. tail = lub_heap_block__get_tail(block);
  125. tail->words = words;
  126. tail->free = 0;
  127. tail->segment = 0;
  128. this->stats.alloc_bytes -= (delta << 2);
  129. }
  130. break;
  131. } else if (words) {
  132. /* can we simple extend the current allocated block? */
  133. if ((BOOL_TRUE ==
  134. lub_heap_extend_upwards(this, &block,
  135. words))
  136. || (BOOL_TRUE ==
  137. lub_heap_extend_downwards(this, &block,
  138. words))
  139. || (BOOL_TRUE ==
  140. lub_heap_extend_both_ways(this, &block,
  141. words))) {
  142. result = LUB_HEAP_OK;
  143. new_ptr = (char *)block->alloc.memory;
  144. break;
  145. }
  146. }
  147. }
  148. if (words && (LUB_HEAP_FAILED == result)) {
  149. /* need to reallocate and copy the data */
  150. new_ptr = lub_heap_new_alloc_block(this, words);
  151. if (NULL != new_ptr) {
  152. result = LUB_HEAP_OK;
  153. if (NULL != block) {
  154. /* now copy the old contents across */
  155. memcpy(new_ptr,
  156. (const char *)block->alloc.
  157. memory,
  158. (block->alloc.tag.words << 2) -
  159. sizeof(lub_heap_alloc_block_t));
  160. }
  161. } else {
  162. /* couldn't find the space for the request */
  163. break;
  164. }
  165. }
  166. /* now it's time to release the memory of the old block */
  167. if (NULL != block) {
  168. words_t old_words = block->alloc.tag.words;
  169. bool_t done = BOOL_FALSE;
  170. /* combine with the next block */
  171. if (LUB_HEAP_OK ==
  172. lub_heap_merge_with_next(this, block)) {
  173. done = BOOL_TRUE;
  174. }
  175. /* combine with the previous block */
  176. if (LUB_HEAP_OK ==
  177. lub_heap_merge_with_previous(this, block)) {
  178. done = BOOL_TRUE;
  179. }
  180. if (BOOL_FALSE == done) {
  181. /* create a new free block */
  182. lub_heap_new_free_block(this, block);
  183. }
  184. result = LUB_HEAP_OK;
  185. --this->stats.alloc_blocks;
  186. this->stats.alloc_bytes -= (old_words << 2);
  187. this->stats.alloc_bytes +=
  188. sizeof(lub_heap_alloc_block_t);
  189. this->stats.alloc_overhead -=
  190. sizeof(lub_heap_alloc_block_t);
  191. }
  192. } while (0);
  193. if (LUB_HEAP_OK == result) {
  194. unsigned delta;
  195. /* align the block as required */
  196. if (LUB_HEAP_ALIGN_NATIVE != alignment) {
  197. lub_heap_align_block(this, alignment, &new_ptr, &size);
  198. }
  199. /* revert to client space available */
  200. size -= sizeof(lub_heap_alloc_block_t);
  201. *ptr = new_ptr;
  202. delta = (size - requested_size);
  203. if (*ptr && requested_size && (0 < delta)) {
  204. /* make sure that any excess memory is tainted */
  205. lub_heap_taint_memory(*ptr + requested_size,
  206. LUB_HEAP_TAINT_ALLOC, delta);
  207. }
  208. } else if ((LUB_HEAP_FAILED == result)
  209. && (0 == requested_size)
  210. && (NULL == *ptr)) {
  211. /* freeing zero is always OK */
  212. result = LUB_HEAP_OK;
  213. }
  214. return result;
  215. }
  216. /*--------------------------------------------------------- */