blob: 2f06ab17ca63bcdab7bd0c6edd97b268774b840f [file] [log] [blame]
lh9ed821d2023-04-07 01:36:19 -07001/*
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'. */
48struct 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
111extern 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. */
118extern 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. */
122extern void __heap_check (struct heap_free_area *heap, const char *str);
123
124
125/* Delete the free-area FA from HEAP. */
126static __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. */
141static __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). */
160static __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. */
176static __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). */
194static __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). */
219extern 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. */
223extern 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. */
227extern 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))