heap.h 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231
  1. /*
  2. * libc/stdlib/malloc/heap.h -- heap allocator used for malloc
  3. *
  4. * Copyright (C) 2002,03 NEC Electronics Corporation
  5. * Copyright (C) 2002,03 Miles Bader <miles@gnu.org>
  6. *
  7. * This file is subject to the terms and conditions of the GNU Lesser
  8. * General Public License. See the file COPYING.LIB in the main
  9. * directory of this archive for more details.
  10. *
  11. * Written by Miles Bader <miles@gnu.org>
  12. */
  13. #include <features.h>
  14. /* On multi-threaded systems, the heap includes a lock. */
  15. #ifdef __UCLIBC_HAS_THREADS__
  16. # include <bits/uClibc_mutex.h>
  17. # define HEAP_USE_LOCKING
  18. # define __heap_lock(heap_lock) __UCLIBC_MUTEX_LOCK_CANCEL_UNSAFE(*(heap_lock))
  19. # define __heap_unlock(heap_lock) __UCLIBC_MUTEX_UNLOCK_CANCEL_UNSAFE(*(heap_lock))
  20. #else
  21. # define __heap_lock(heap_lock)
  22. # define __heap_unlock(heap_lock)
  23. #endif
  24. /* The heap allocates in multiples of, and aligned to, HEAP_GRANULARITY.
  25. HEAP_GRANULARITY must be a power of 2. Malloc depends on this being the
  26. same as MALLOC_ALIGNMENT. */
  27. #define HEAP_GRANULARITY_TYPE double __attribute_aligned__ (HEAP_GRANULARITY)
  28. #define HEAP_GRANULARITY \
  29. (__alignof__ (double) > sizeof (size_t) ? __alignof__ (double) : sizeof (size_t))
  30. /* The HEAP_INIT macro can be used as a static initializer for a heap
  31. variable. The HEAP_INIT_WITH_FA variant is used to initialize a heap
  32. with an initial static free-area; its argument FA should be declared
  33. using HEAP_DECLARE_STATIC_FREE_AREA. */
  34. # define HEAP_INIT 0
  35. # define HEAP_INIT_WITH_FA(fa) &fa._fa
  36. /* A free-list area `header'. These are actually stored at the _ends_ of
  37. free areas (to make allocating from the beginning of the area simpler),
  38. so one might call it a `footer'. */
  39. struct heap_free_area
  40. {
  41. size_t size;
  42. struct heap_free_area *next, *prev;
  43. };
  44. /* Return the address of the end of the frea area FA. */
  45. #define HEAP_FREE_AREA_END(fa) ((void *)(fa + 1))
  46. /* Return the address of the beginning of the frea area FA. FA is
  47. evaulated multiple times. */
  48. #define HEAP_FREE_AREA_START(fa) ((void *)((char *)(fa + 1) - (fa)->size))
  49. /* Return the size of the frea area FA. */
  50. #define HEAP_FREE_AREA_SIZE(fa) ((fa)->size)
  51. /* This rather clumsy macro allows one to declare a static free-area for
  52. passing to HEAP_INIT_WITH_FA initializer macro. This is only use for
  53. which NAME is allowed. */
  54. #define HEAP_DECLARE_STATIC_FREE_AREA(name, size) \
  55. static struct \
  56. { \
  57. HEAP_GRANULARITY_TYPE aligned_space; \
  58. char space[HEAP_ADJUST_SIZE(size) \
  59. - sizeof (struct heap_free_area) \
  60. - HEAP_GRANULARITY]; \
  61. struct heap_free_area _fa; \
  62. } name = { (HEAP_GRANULARITY_TYPE)0, "", { HEAP_ADJUST_SIZE(size), 0, 0 } }
  63. /* Rounds SZ up to be a multiple of HEAP_GRANULARITY. */
  64. #define HEAP_ADJUST_SIZE(sz) \
  65. (((sz) + HEAP_GRANULARITY - 1) & ~(HEAP_GRANULARITY - 1))
  66. /* The minimum allocatable size. */
  67. #define HEAP_MIN_SIZE HEAP_ADJUST_SIZE (sizeof (struct heap_free_area))
  68. /* The minimum size of a free area; if allocating memory from a free-area
  69. would make the free-area smaller than this, the allocation is simply
  70. given the whole free-area instead. It must include at least enough room
  71. to hold a struct heap_free_area, plus some extra to avoid excessive heap
  72. fragmentation (thus increasing speed). This is only a heuristic -- it's
  73. possible for smaller free-areas than this to exist (say, by realloc
  74. returning the tail-end of a previous allocation), but __heap_alloc will
  75. try to get rid of them when possible. */
  76. #define HEAP_MIN_FREE_AREA_SIZE \
  77. HEAP_ADJUST_SIZE (sizeof (struct heap_free_area) + 32)
  78. /* branch-prediction macros; they may already be defined by libc. */
  79. #ifndef likely
  80. #if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 96)
  81. #define likely(cond) __builtin_expect(!!(int)(cond), 1)
  82. #define unlikely(cond) __builtin_expect((int)(cond), 0)
  83. #else
  84. #define likely(cond) (cond)
  85. #define unlikely(cond) (cond)
  86. #endif
  87. #endif /* !likely */
  88. /* Define HEAP_DEBUGGING to cause the heap routines to emit debugging info
  89. to stderr when the variable __heap_debug is set to true. */
  90. #ifdef HEAP_DEBUGGING
  91. extern int __heap_debug;
  92. #define HEAP_DEBUG(heap, str) (__heap_debug ? __heap_dump (heap, str) : 0)
  93. #else
  94. #define HEAP_DEBUG(heap, str) (void)0
  95. #endif
  96. /* Output a text representation of HEAP to stderr, labelling it with STR. */
  97. extern void __heap_dump (struct heap_free_area *heap, const char *str);
  98. /* Do some consistency checks on HEAP. If they fail, output an error
  99. message to stderr, and exit. STR is printed with the failure message. */
  100. extern void __heap_check (struct heap_free_area *heap, const char *str);
  101. /* Delete the free-area FA from HEAP. */
  102. static __inline__ void
  103. __heap_delete (struct heap_free_area **heap, struct heap_free_area *fa)
  104. {
  105. if (fa->next)
  106. fa->next->prev = fa->prev;
  107. if (fa->prev)
  108. fa->prev->next = fa->next;
  109. else
  110. *heap = fa->next;
  111. }
  112. /* Link the free-area FA between the existing free-area's PREV and NEXT in
  113. HEAP. PREV and NEXT may be 0; if PREV is 0, FA is installed as the
  114. first free-area. */
  115. static __inline__ void
  116. __heap_link_free_area (struct heap_free_area **heap, struct heap_free_area *fa,
  117. struct heap_free_area *prev,
  118. struct heap_free_area *next)
  119. {
  120. fa->next = next;
  121. fa->prev = prev;
  122. if (prev)
  123. prev->next = fa;
  124. else
  125. *heap = fa;
  126. if (next)
  127. next->prev = fa;
  128. }
  129. /* Update the mutual links between the free-areas PREV and FA in HEAP.
  130. PREV may be 0, in which case FA is installed as the first free-area (but
  131. FA may not be 0). */
  132. static __inline__ void
  133. __heap_link_free_area_after (struct heap_free_area **heap,
  134. struct heap_free_area *fa,
  135. struct heap_free_area *prev)
  136. {
  137. if (prev)
  138. prev->next = fa;
  139. else
  140. *heap = fa;
  141. fa->prev = prev;
  142. }
  143. /* Add a new free-area MEM, of length SIZE, in between the existing
  144. free-area's PREV and NEXT in HEAP, and return a pointer to its header.
  145. PREV and NEXT may be 0; if PREV is 0, MEM is installed as the first
  146. free-area. */
  147. static __inline__ struct heap_free_area *
  148. __heap_add_free_area (struct heap_free_area **heap, void *mem, size_t size,
  149. struct heap_free_area *prev,
  150. struct heap_free_area *next)
  151. {
  152. struct heap_free_area *fa = (struct heap_free_area *)
  153. ((char *)mem + size - sizeof (struct heap_free_area));
  154. fa->size = size;
  155. __heap_link_free_area (heap, fa, prev, next);
  156. return fa;
  157. }
  158. /* Allocate SIZE bytes from the front of the free-area FA in HEAP, and
  159. return the amount actually allocated (which may be more than SIZE). */
  160. static __inline__ size_t
  161. __heap_free_area_alloc (struct heap_free_area **heap,
  162. struct heap_free_area *fa, size_t size)
  163. {
  164. size_t fa_size = fa->size;
  165. if (fa_size < size + HEAP_MIN_FREE_AREA_SIZE)
  166. /* There's not enough room left over in FA after allocating the block, so
  167. just use the whole thing, removing it from the list of free areas. */
  168. {
  169. __heap_delete (heap, fa);
  170. /* Remember that we've alloced the whole area. */
  171. size = fa_size;
  172. }
  173. else
  174. /* Reduce size of FA to account for this allocation. */
  175. fa->size = fa_size - size;
  176. return size;
  177. }
  178. /* Allocate and return a block at least *SIZE bytes long from HEAP.
  179. *SIZE is adjusted to reflect the actual amount allocated (which may be
  180. greater than requested). */
  181. extern void *__heap_alloc (struct heap_free_area **heap, size_t *size);
  182. /* Allocate SIZE bytes at address MEM in HEAP. Return the actual size
  183. allocated, or 0 if we failed. */
  184. extern size_t __heap_alloc_at (struct heap_free_area **heap, void *mem, size_t size);
  185. /* Return the memory area MEM of size SIZE to HEAP.
  186. Returns the heap free area into which the memory was placed. */
  187. extern struct heap_free_area *__heap_free (struct heap_free_area **heap,
  188. void *mem, size_t size);
  189. /* Return true if HEAP contains absolutely no memory. */
  190. #define __heap_is_empty(heap) (! (heap))