heap.h 8.2 KB

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