1 /*
2 * Copyright (c) 2008-2015 Travis Geiselbrecht
3 *
4 * Use of this source code is governed by a MIT-style
5 * license that can be found in the LICENSE file or at
6 * https://opensource.org/licenses/MIT
7 */
8 #include <lib/heap.h>
9
10 #include <lk/trace.h>
11 #include <lk/debug.h>
12 #include <assert.h>
13 #include <stdlib.h>
14 #include <string.h>
15 #include <lk/err.h>
16 #include <lk/list.h>
17 #include <kernel/spinlock.h>
18 #include <lk/console_cmd.h>
19 #include <lib/page_alloc.h>
20
21 #define LOCAL_TRACE 0
22
23 /* heap tracing */
24 #if LK_DEBUGLEVEL > 0
25 static bool heap_trace = false;
26 #else
27 #define heap_trace (false)
28 #endif
29
30 /* delayed free list */
31 struct list_node delayed_free_list = LIST_INITIAL_VALUE(delayed_free_list);
32 spin_lock_t delayed_free_lock = SPIN_LOCK_INITIAL_VALUE;
33
34 #if WITH_LIB_HEAP_MINIHEAP
35 /* miniheap implementation */
36 #include <lib/miniheap.h>
37
HEAP_MALLOC(size_t s)38 static inline void *HEAP_MALLOC(size_t s) { return miniheap_alloc(s, 0); }
HEAP_REALLOC(void * ptr,size_t s)39 static inline void *HEAP_REALLOC(void *ptr, size_t s) { return miniheap_realloc(ptr, s); }
HEAP_MEMALIGN(size_t boundary,size_t s)40 static inline void *HEAP_MEMALIGN(size_t boundary, size_t s) { return miniheap_alloc(s, boundary); }
41 #define HEAP_FREE miniheap_free
HEAP_CALLOC(size_t n,size_t s)42 static inline void *HEAP_CALLOC(size_t n, size_t s) {
43 size_t realsize = n * s;
44
45 void *ptr = miniheap_alloc(realsize, 0);
46 if (likely(ptr))
47 memset(ptr, 0, realsize);
48 return ptr;
49 }
HEAP_INIT(void)50 static inline void HEAP_INIT(void) {
51 /* start the heap off with some spare memory in the page allocator */
52 size_t len;
53 void *ptr = page_first_alloc(&len);
54 miniheap_init(ptr, len);
55 }
56 #define HEAP_DUMP miniheap_dump
57 #define HEAP_TRIM miniheap_trim
58
59 /* end miniheap implementation */
60 #elif WITH_LIB_HEAP_CMPCTMALLOC
61 /* cmpctmalloc implementation */
62 #include <lib/cmpctmalloc.h>
63
64 #define HEAP_MEMALIGN(boundary, s) cmpct_memalign(s, boundary)
65 #define HEAP_MALLOC cmpct_alloc
66 #define HEAP_REALLOC cmpct_realloc
67 #define HEAP_FREE cmpct_free
68 #define HEAP_INIT cmpct_init
69 #define HEAP_DUMP cmpct_dump
70 #define HEAP_TRIM cmpct_trim
HEAP_CALLOC(size_t n,size_t s)71 static inline void *HEAP_CALLOC(size_t n, size_t s) {
72 size_t realsize = n * s;
73
74 void *ptr = cmpct_alloc(realsize);
75 if (likely(ptr))
76 memset(ptr, 0, realsize);
77 return ptr;
78 }
79
80 /* end cmpctmalloc implementation */
81 #elif WITH_LIB_HEAP_DLMALLOC
82 /* dlmalloc implementation */
83 #include <lib/dlmalloc.h>
84
85 #define HEAP_MALLOC(s) dlmalloc(s)
86 #define HEAP_CALLOC(n, s) dlcalloc(n, s)
87 #define HEAP_MEMALIGN(b, s) dlmemalign(b, s)
88 #define HEAP_REALLOC(p, s) dlrealloc(p, s)
89 #define HEAP_FREE(p) dlfree(p)
HEAP_INIT(void)90 static inline void HEAP_INIT(void) {}
91
HEAP_DUMP(void)92 static inline void HEAP_DUMP(void) {
93 struct mallinfo minfo = dlmallinfo();
94
95 printf("\tmallinfo (dlmalloc):\n");
96 printf("\t\tarena space 0x%zx\n", minfo.arena);
97 printf("\t\tfree chunks 0x%zx\n", minfo.ordblks);
98 printf("\t\tspace in mapped regions 0x%zx\n", minfo.hblkhd);
99 printf("\t\tmax total allocated 0x%zx\n", minfo.usmblks);
100 printf("\t\ttotal allocated 0x%zx\n", minfo.uordblks);
101 printf("\t\tfree 0x%zx\n", minfo.fordblks);
102 printf("\t\treleasable space 0x%zx\n", minfo.keepcost);
103
104 printf("\theap block list:\n");
105 void dump_callback(void *start, void *end, size_t used_bytes, void *arg) {
106 printf("\t\tstart %p end %p used_bytes %zu\n", start, end, used_bytes);
107 }
108
109 dlmalloc_inspect_all(&dump_callback, NULL);
110 }
111
HEAP_TRIM(void)112 static inline void HEAP_TRIM(void) { dlmalloc_trim(0); }
113
114 /* end dlmalloc implementation */
115 #else
116 #error need to select valid heap implementation or provide wrapper
117 #endif
118
heap_free_delayed_list(void)119 static void heap_free_delayed_list(void) {
120 struct list_node list;
121
122 list_initialize(&list);
123
124 spin_lock_saved_state_t state;
125 spin_lock_irqsave(&delayed_free_lock, state);
126
127 struct list_node *node;
128 while ((node = list_remove_head(&delayed_free_list))) {
129 list_add_head(&list, node);
130 }
131 spin_unlock_irqrestore(&delayed_free_lock, state);
132
133 while ((node = list_remove_head(&list))) {
134 LTRACEF("freeing node %p\n", node);
135 HEAP_FREE(node);
136 }
137 }
138
heap_init(void)139 void heap_init(void) {
140 HEAP_INIT();
141 }
142
heap_trim(void)143 void heap_trim(void) {
144 // deal with the pending free list
145 if (unlikely(!list_is_empty(&delayed_free_list))) {
146 heap_free_delayed_list();
147 }
148
149 HEAP_TRIM();
150 }
151
malloc(size_t size)152 void *malloc(size_t size) {
153 LTRACEF("size %zd\n", size);
154
155 // deal with the pending free list
156 if (unlikely(!list_is_empty(&delayed_free_list))) {
157 heap_free_delayed_list();
158 }
159
160 void *ptr = HEAP_MALLOC(size);
161 if (heap_trace)
162 printf("caller %p malloc %zu -> %p\n", __GET_CALLER(), size, ptr);
163 return ptr;
164 }
165
memalign(size_t boundary,size_t size)166 void *memalign(size_t boundary, size_t size) {
167 LTRACEF("boundary %zu, size %zd\n", boundary, size);
168
169 // deal with the pending free list
170 if (unlikely(!list_is_empty(&delayed_free_list))) {
171 heap_free_delayed_list();
172 }
173
174 void *ptr = HEAP_MEMALIGN(boundary, size);
175 if (heap_trace)
176 printf("caller %p memalign %zu, %zu -> %p\n", __GET_CALLER(), boundary, size, ptr);
177 return ptr;
178 }
179
calloc(size_t count,size_t size)180 void *calloc(size_t count, size_t size) {
181 LTRACEF("count %zu, size %zd\n", count, size);
182
183 // deal with the pending free list
184 if (unlikely(!list_is_empty(&delayed_free_list))) {
185 heap_free_delayed_list();
186 }
187
188 void *ptr = HEAP_CALLOC(count, size);
189 if (heap_trace)
190 printf("caller %p calloc %zu, %zu -> %p\n", __GET_CALLER(), count, size, ptr);
191 return ptr;
192 }
193
realloc(void * ptr,size_t size)194 void *realloc(void *ptr, size_t size) {
195 LTRACEF("ptr %p, size %zd\n", ptr, size);
196
197 // deal with the pending free list
198 if (unlikely(!list_is_empty(&delayed_free_list))) {
199 heap_free_delayed_list();
200 }
201
202 void *ptr2 = HEAP_REALLOC(ptr, size);
203 if (heap_trace)
204 printf("caller %p realloc %p, %zu -> %p\n", __GET_CALLER(), ptr, size, ptr2);
205 return ptr2;
206 }
207
free(void * ptr)208 void free(void *ptr) {
209 LTRACEF("ptr %p\n", ptr);
210 if (heap_trace)
211 printf("caller %p free %p\n", __GET_CALLER(), ptr);
212
213 HEAP_FREE(ptr);
214 }
215
216 /* critical section time delayed free */
heap_delayed_free(void * ptr)217 void heap_delayed_free(void *ptr) {
218 LTRACEF("ptr %p\n", ptr);
219
220 /* throw down a structure on the free block */
221 /* XXX assumes the free block is large enough to hold a list node */
222 struct list_node *node = (struct list_node *)ptr;
223
224 spin_lock_saved_state_t state;
225 spin_lock_irqsave(&delayed_free_lock, state);
226 list_add_head(&delayed_free_list, node);
227 spin_unlock_irqrestore(&delayed_free_lock, state);
228 }
229
heap_dump(void)230 static void heap_dump(void) {
231 HEAP_DUMP();
232
233 printf("\tdelayed free list:\n");
234 spin_lock_saved_state_t state;
235 spin_lock_irqsave(&delayed_free_lock, state);
236 struct list_node *node;
237 list_for_every(&delayed_free_list, node) {
238 printf("\t\tnode %p\n", node);
239 }
240 spin_unlock_irqrestore(&delayed_free_lock, state);
241 }
242
heap_test(void)243 static void heap_test(void) {
244 #if WITH_LIB_HEAP_CMPCTMALLOC
245 cmpct_test();
246 #else
247 void *ptr[16];
248
249 ptr[0] = HEAP_MALLOC(8);
250 ptr[1] = HEAP_MALLOC(32);
251 ptr[2] = HEAP_MALLOC(7);
252 ptr[3] = HEAP_MALLOC(0);
253 ptr[4] = HEAP_MALLOC(98713);
254 ptr[5] = HEAP_MALLOC(16);
255
256 HEAP_FREE(ptr[5]);
257 HEAP_FREE(ptr[1]);
258 HEAP_FREE(ptr[3]);
259 HEAP_FREE(ptr[0]);
260 HEAP_FREE(ptr[4]);
261 HEAP_FREE(ptr[2]);
262
263 HEAP_DUMP();
264
265 int i;
266 for (i=0; i < 16; i++)
267 ptr[i] = 0;
268
269 for (i=0; i < 32768; i++) {
270 unsigned int index = (unsigned int)rand() % 16;
271
272 if ((i % (16*1024)) == 0)
273 printf("pass %d\n", i);
274
275 // printf("index 0x%x\n", index);
276 if (ptr[index]) {
277 // printf("freeing ptr[0x%x] = %p\n", index, ptr[index]);
278 HEAP_FREE(ptr[index]);
279 ptr[index] = 0;
280 }
281 unsigned int align = 1 << ((unsigned int)rand() % 8);
282 ptr[index] = HEAP_MEMALIGN(align, (unsigned int)rand() % 32768);
283 // printf("ptr[0x%x] = %p, align 0x%x\n", index, ptr[index], align);
284
285 DEBUG_ASSERT(((addr_t)ptr[index] % align) == 0);
286 // heap_dump();
287 }
288
289 for (i=0; i < 16; i++) {
290 if (ptr[i])
291 HEAP_FREE(ptr[i]);
292 }
293
294 HEAP_DUMP();
295 #endif
296 }
297
298
299 #if LK_DEBUGLEVEL > 1
300
301 static int cmd_heap(int argc, const console_cmd_args *argv);
302
303 STATIC_COMMAND_START
304 STATIC_COMMAND("heap", "heap debug commands", &cmd_heap)
305 STATIC_COMMAND_END(heap);
306
cmd_heap(int argc,const console_cmd_args * argv)307 static int cmd_heap(int argc, const console_cmd_args *argv) {
308 if (argc < 2) {
309 notenoughargs:
310 printf("not enough arguments\n");
311 usage:
312 printf("usage:\n");
313 printf("\t%s info\n", argv[0].str);
314 printf("\t%s trace\n", argv[0].str);
315 printf("\t%s trim\n", argv[0].str);
316 printf("\t%s alloc <size> [alignment]\n", argv[0].str);
317 printf("\t%s realloc <ptr> <size>\n", argv[0].str);
318 printf("\t%s free <address>\n", argv[0].str);
319 return -1;
320 }
321
322 if (strcmp(argv[1].str, "info") == 0) {
323 heap_dump();
324 } else if (strcmp(argv[1].str, "test") == 0) {
325 heap_test();
326 } else if (strcmp(argv[1].str, "trace") == 0) {
327 heap_trace = !heap_trace;
328 printf("heap trace is now %s\n", heap_trace ? "on" : "off");
329 } else if (strcmp(argv[1].str, "trim") == 0) {
330 heap_trim();
331 } else if (strcmp(argv[1].str, "alloc") == 0) {
332 if (argc < 3) goto notenoughargs;
333
334 void *ptr = memalign((argc >= 4) ? argv[3].u : 0, argv[2].u);
335 printf("memalign returns %p\n", ptr);
336 } else if (strcmp(argv[1].str, "realloc") == 0) {
337 if (argc < 4) goto notenoughargs;
338
339 void *ptr = realloc(argv[2].p, argv[3].u);
340 printf("realloc returns %p\n", ptr);
341 } else if (strcmp(argv[1].str, "free") == 0) {
342 if (argc < 2) goto notenoughargs;
343
344 free(argv[2].p);
345 } else {
346 printf("unrecognized command\n");
347 goto usage;
348 }
349
350 return 0;
351 }
352
353 #endif
354
355
356