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 #include <bits/uClibc_mutex.h>
17 #ifdef __UCLIBC_HAS_THREADS__
18 # define HEAP_USE_LOCKING
19 #endif
20 
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 
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 
31 
32 
33 /* The HEAP_INIT_WITH_FA variant is used to initialize a heap
34    with an initial static free-area; its argument FA should be declared
35    using HEAP_DECLARE_STATIC_FREE_AREA.  */
36 # define HEAP_INIT_WITH_FA(fa)	&fa._fa
37 
38 /* A free-list area `header'.  These are actually stored at the _ends_ of
39    free areas (to make allocating from the beginning of the area simpler),
40    so one might call it a `footer'.  */
41 struct heap_free_area
42 {
43 	size_t size;
44 	struct heap_free_area *next, *prev;
45 };
46 
47 /* Return the address of the end of the frea area FA.  */
48 #define HEAP_FREE_AREA_END(fa) ((void *)(fa + 1))
49 /* Return the address of the beginning of the frea area FA.  FA is
50    evaulated multiple times.  */
51 #define HEAP_FREE_AREA_START(fa) ((void *)((char *)(fa + 1) - (fa)->size))
52 /* Return the size of the frea area FA.  */
53 #define HEAP_FREE_AREA_SIZE(fa) ((fa)->size)
54 
55 /* This rather clumsy macro allows one to declare a static free-area for
56    passing to HEAP_INIT_WITH_FA initializer macro.  This is only use for
57    which NAME is allowed.  */
58 #define HEAP_DECLARE_STATIC_FREE_AREA(name, size)			      \
59   static struct								      \
60   {									      \
61     HEAP_GRANULARITY_TYPE aligned_space;				      \
62     char space[HEAP_ADJUST_SIZE(size)					      \
63 	       - sizeof (struct heap_free_area)				      \
64 	       - HEAP_GRANULARITY];					      \
65     struct heap_free_area _fa;						      \
66   } name = { (HEAP_GRANULARITY_TYPE)0, "", { HEAP_ADJUST_SIZE(size), 0, 0 } }
67 
68 
69 /* Rounds SZ up to be a multiple of HEAP_GRANULARITY.  */
70 #define HEAP_ADJUST_SIZE(sz)  \
71    (((sz) + HEAP_GRANULARITY - 1) & ~(HEAP_GRANULARITY - 1))
72 
73 
74 /* The minimum allocatable size.  */
75 #define HEAP_MIN_SIZE	HEAP_ADJUST_SIZE (sizeof (struct heap_free_area))
76 
77 /* The minimum size of a free area; if allocating memory from a free-area
78    would make the free-area smaller than this, the allocation is simply
79    given the whole free-area instead.  It must include at least enough room
80    to hold a struct heap_free_area, plus some extra to avoid excessive heap
81    fragmentation (thus increasing speed).  This is only a heuristic -- it's
82    possible for smaller free-areas than this to exist (say, by realloc
83    returning the tail-end of a previous allocation), but __heap_alloc will
84    try to get rid of them when possible.  */
85 #define HEAP_MIN_FREE_AREA_SIZE  \
86   HEAP_ADJUST_SIZE (sizeof (struct heap_free_area) + 32)
87 
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 attribute_hidden;
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 
97 /* Output a text representation of HEAP to stderr, labelling it with STR.  */
98 extern void __heap_dump (struct heap_free_area *heap, const char *str) attribute_hidden;
99 
100 /* Do some consistency checks on HEAP.  If they fail, output an error
101    message to stderr, and exit.  STR is printed with the failure message.  */
102 extern void __heap_check (struct heap_free_area *heap, const char *str) attribute_hidden;
103 
104 
105 /* Delete the free-area FA from HEAP.  */
106 static __inline__ void
__heap_delete(struct heap_free_area ** heap,struct heap_free_area * fa)107 __heap_delete (struct heap_free_area **heap, struct heap_free_area *fa)
108 {
109   if (fa->next)
110     fa->next->prev = fa->prev;
111   if (fa->prev)
112     fa->prev->next = fa->next;
113   else
114     *heap = fa->next;
115 }
116 
117 
118 /* Link the free-area FA between the existing free-area's PREV and NEXT in
119    HEAP.  PREV and NEXT may be 0; if PREV is 0, FA is installed as the
120    first free-area.  */
121 static __inline__ void
__heap_link_free_area(struct heap_free_area ** heap,struct heap_free_area * fa,struct heap_free_area * prev,struct heap_free_area * next)122 __heap_link_free_area (struct heap_free_area **heap, struct heap_free_area *fa,
123 		       struct heap_free_area *prev,
124 		       struct heap_free_area *next)
125 {
126   fa->next = next;
127   fa->prev = prev;
128 
129   if (prev)
130     prev->next = fa;
131   else
132     *heap = fa;
133   if (next)
134     next->prev = fa;
135 }
136 
137 /* Update the mutual links between the free-areas PREV and FA in HEAP.
138    PREV may be 0, in which case FA is installed as the first free-area (but
139    FA may not be 0).  */
140 static __inline__ void
__heap_link_free_area_after(struct heap_free_area ** heap,struct heap_free_area * fa,struct heap_free_area * prev)141 __heap_link_free_area_after (struct heap_free_area **heap,
142 			     struct heap_free_area *fa,
143 			     struct heap_free_area *prev)
144 {
145   if (prev)
146     prev->next = fa;
147   else
148     *heap = fa;
149   fa->prev = prev;
150 }
151 
152 /* Add a new free-area MEM, of length SIZE, in between the existing
153    free-area's PREV and NEXT in HEAP, and return a pointer to its header.
154    PREV and NEXT may be 0; if PREV is 0, MEM is installed as the first
155    free-area.  */
156 static __inline__ struct heap_free_area *
__heap_add_free_area(struct heap_free_area ** heap,void * mem,size_t size,struct heap_free_area * prev,struct heap_free_area * next)157 __heap_add_free_area (struct heap_free_area **heap, void *mem, size_t size,
158 		      struct heap_free_area *prev,
159 		      struct heap_free_area *next)
160 {
161   struct heap_free_area *fa = (struct heap_free_area *)
162     ((char *)mem + size - sizeof (struct heap_free_area));
163 
164   fa->size = size;
165 
166   __heap_link_free_area (heap, fa, prev, next);
167 
168   return fa;
169 }
170 
171 
172 /* Allocate SIZE bytes from the front of the free-area FA in HEAP, and
173    return the amount actually allocated (which may be more than SIZE).  */
174 static __inline__ size_t
__heap_free_area_alloc(struct heap_free_area ** heap,struct heap_free_area * fa,size_t size)175 __heap_free_area_alloc (struct heap_free_area **heap,
176 			struct heap_free_area *fa, size_t size)
177 {
178   size_t fa_size = fa->size;
179 
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 
192   return size;
193 }
194 
195 
196 /* Allocate and return a block at least *SIZE bytes long from HEAP.
197    *SIZE is adjusted to reflect the actual amount allocated (which may be
198    greater than requested).  */
199 extern void *__heap_alloc (struct heap_free_area **heap, size_t *size) attribute_hidden;
200 
201 /* Allocate SIZE bytes at address MEM in HEAP.  Return the actual size
202    allocated, or 0 if we failed.  */
203 extern size_t __heap_alloc_at (struct heap_free_area **heap, void *mem, size_t size) attribute_hidden;
204 
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_free_area **heap,
208 					   void *mem, size_t size) attribute_hidden;
209 
210 /* Return true if HEAP contains absolutely no memory.  */
211 #define __heap_is_empty(heap) (! (heap))
212