uClibc/libc/stdlib/malloc/heap.h

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