heap.h 8.4 KB

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