blob: c159cae7359292ff7b6e3ce144b79b0f721e0af2 [file] [log] [blame]
rjw1f884582022-01-06 17:20:42 +08001/*
2 * Copyright (c) 2008-2015 Travis Geiselbrecht
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files
6 * (the "Software"), to deal in the Software without restriction,
7 * including without limitation the rights to use, copy, modify, merge,
8 * publish, distribute, sublicense, and/or sell copies of the Software,
9 * and to permit persons to whom the Software is furnished to do so,
10 * subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
19 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
20 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
21 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 */
23#include <lib/heap.h>
24
25#include <trace.h>
26#include <debug.h>
27#include <assert.h>
28#include <stdlib.h>
29#include <string.h>
30#include <err.h>
31#include <list.h>
32#include <kernel/spinlock.h>
33#include <lib/console.h>
34#include <lib/page_alloc.h>
35
36#define LOCAL_TRACE 0
37
38/* heap tracing */
39#if LK_DEBUGLEVEL > 0
40static bool heap_trace = false;
41#else
42#define heap_trace (false)
43#endif
44
45/* delayed free list */
46struct list_node delayed_free_list = LIST_INITIAL_VALUE(delayed_free_list);
47spin_lock_t delayed_free_lock = SPIN_LOCK_INITIAL_VALUE;
48
49#if WITH_LIB_HEAP_MINIHEAP
50/* miniheap implementation */
51#include <lib/miniheap.h>
52
53static inline void *HEAP_MALLOC(size_t s) { return miniheap_alloc(s, 0); }
54static inline void *HEAP_REALLOC(void *ptr, size_t s) { return miniheap_realloc(ptr, s); }
55static inline void *HEAP_MEMALIGN(size_t boundary, size_t s) { return miniheap_alloc(s, boundary); }
56#define HEAP_FREE miniheap_free
57static inline void *HEAP_CALLOC(size_t n, size_t s) {
58 size_t realsize = n * s;
59
60 void *ptr = miniheap_alloc(realsize, 0);
61 if (likely(ptr))
62 memset(ptr, 0, realsize);
63 return ptr;
64}
65static inline void HEAP_INIT(void) {
66 /* start the heap off with some spare memory in the page allocator */
67 size_t len;
68 void *ptr = page_first_alloc(&len);
69 miniheap_init(ptr, len);
70}
71#define HEAP_DUMP miniheap_dump
72#define HEAP_TRIM miniheap_trim
73
74/* end miniheap implementation */
75#elif WITH_LIB_HEAP_CMPCTMALLOC
76/* cmpctmalloc implementation */
77#include <lib/cmpctmalloc.h>
78
79#define HEAP_MEMALIGN(boundary, s) cmpct_memalign(s, boundary)
80#define HEAP_MALLOC cmpct_alloc
81#define HEAP_REALLOC cmpct_realloc
82#define HEAP_FREE cmpct_free
83#define HEAP_INIT cmpct_init
84#define HEAP_DUMP cmpct_dump
85#define HEAP_TRIM cmpct_trim
86static inline void *HEAP_CALLOC(size_t n, size_t s)
87{
88 size_t realsize = n * s;
89
90 void *ptr = cmpct_alloc(realsize);
91 if (likely(ptr))
92 memset(ptr, 0, realsize);
93 return ptr;
94}
95
96/* end cmpctmalloc implementation */
97#elif WITH_LIB_HEAP_DLMALLOC
98/* dlmalloc implementation */
99#include <lib/dlmalloc.h>
100
101#define HEAP_MALLOC(s) dlmalloc(s)
102#define HEAP_CALLOC(n, s) dlcalloc(n, s)
103#define HEAP_MEMALIGN(b, s) dlmemalign(b, s)
104#define HEAP_REALLOC(p, s) dlrealloc(p, s)
105#define HEAP_FREE(p) dlfree(p)
106static inline void HEAP_INIT(void) {}
107
108static inline void HEAP_DUMP(void) {
109 struct mallinfo minfo = dlmallinfo();
110
111 printf("\tmallinfo (dlmalloc):\n");
112 printf("\t\tarena space 0x%zx\n", minfo.arena);
113 printf("\t\tfree chunks 0x%zx\n", minfo.ordblks);
114 printf("\t\tspace in mapped regions 0x%zx\n", minfo.hblkhd);
115 printf("\t\tmax total allocated 0x%zx\n", minfo.usmblks);
116 printf("\t\ttotal allocated 0x%zx\n", minfo.uordblks);
117 printf("\t\tfree 0x%zx\n", minfo.fordblks);
118 printf("\t\treleasable space 0x%zx\n", minfo.keepcost);
119
120 printf("\theap block list:\n");
121 void dump_callback(void *start, void *end, size_t used_bytes, void *arg) {
122 printf("\t\tstart %p end %p used_bytes %zu\n", start, end, used_bytes);
123 }
124
125 dlmalloc_inspect_all(&dump_callback, NULL);
126}
127
128static inline void HEAP_TRIM(void) { dlmalloc_trim(0); }
129
130/* end dlmalloc implementation */
131#else
132#error need to select valid heap implementation or provide wrapper
133#endif
134
135static void heap_free_delayed_list(void)
136{
137 struct list_node list;
138
139 list_initialize(&list);
140
141 spin_lock_saved_state_t state;
142 spin_lock_irqsave(&delayed_free_lock, state);
143
144 struct list_node *node;
145 while ((node = list_remove_head(&delayed_free_list))) {
146 list_add_head(&list, node);
147 }
148 spin_unlock_irqrestore(&delayed_free_lock, state);
149
150 while ((node = list_remove_head(&list))) {
151 LTRACEF("freeing node %p\n", node);
152 HEAP_FREE(node);
153 }
154}
155
156void heap_init(void)
157{
158 HEAP_INIT();
159}
160
161void heap_trim(void)
162{
163 // deal with the pending free list
164 if (unlikely(!list_is_empty(&delayed_free_list))) {
165 heap_free_delayed_list();
166 }
167
168 HEAP_TRIM();
169}
170
171void *malloc(size_t size)
172{
173 LTRACEF("size %zd\n", size);
174
175 // deal with the pending free list
176 if (unlikely(!list_is_empty(&delayed_free_list))) {
177 heap_free_delayed_list();
178 }
179
180 void *ptr = HEAP_MALLOC(size);
181 if (heap_trace)
182 printf("caller %p malloc %zu -> %p\n", __GET_CALLER(), size, ptr);
183 return ptr;
184}
185
186void *memalign(size_t boundary, size_t size)
187{
188 LTRACEF("boundary %zu, size %zd\n", boundary, size);
189
190 // deal with the pending free list
191 if (unlikely(!list_is_empty(&delayed_free_list))) {
192 heap_free_delayed_list();
193 }
194
195 void *ptr = HEAP_MEMALIGN(boundary, size);
196 if (heap_trace)
197 printf("caller %p memalign %zu, %zu -> %p\n", __GET_CALLER(), boundary, size, ptr);
198 return ptr;
199}
200
201void *calloc(size_t count, size_t size)
202{
203 LTRACEF("count %zu, size %zd\n", count, size);
204
205 // deal with the pending free list
206 if (unlikely(!list_is_empty(&delayed_free_list))) {
207 heap_free_delayed_list();
208 }
209
210 void *ptr = HEAP_CALLOC(count, size);
211 if (heap_trace)
212 printf("caller %p calloc %zu, %zu -> %p\n", __GET_CALLER(), count, size, ptr);
213 return ptr;
214}
215
216void *realloc(void *ptr, size_t size)
217{
218 LTRACEF("ptr %p, size %zd\n", ptr, size);
219
220 // deal with the pending free list
221 if (unlikely(!list_is_empty(&delayed_free_list))) {
222 heap_free_delayed_list();
223 }
224
225 void *ptr2 = HEAP_REALLOC(ptr, size);
226 if (heap_trace)
227 printf("caller %p realloc %p, %zu -> %p\n", __GET_CALLER(), ptr, size, ptr2);
228 return ptr2;
229}
230
231void free(void *ptr)
232{
233 LTRACEF("ptr %p\n", ptr);
234 if (heap_trace)
235 printf("caller %p free %p\n", __GET_CALLER(), ptr);
236
237 HEAP_FREE(ptr);
238}
239
240/* critical section time delayed free */
241void heap_delayed_free(void *ptr)
242{
243 LTRACEF("ptr %p\n", ptr);
244
245 /* throw down a structure on the free block */
246 /* XXX assumes the free block is large enough to hold a list node */
247 struct list_node *node = (struct list_node *)ptr;
248
249 spin_lock_saved_state_t state;
250 spin_lock_irqsave(&delayed_free_lock, state);
251 list_add_head(&delayed_free_list, node);
252 spin_unlock_irqrestore(&delayed_free_lock, state);
253}
254
255static void heap_dump(void)
256{
257 HEAP_DUMP();
258
259 printf("\tdelayed free list:\n");
260 spin_lock_saved_state_t state;
261 spin_lock_irqsave(&delayed_free_lock, state);
262 struct list_node *node;
263 list_for_every(&delayed_free_list, node) {
264 printf("\t\tnode %p\n", node);
265 }
266 spin_unlock_irqrestore(&delayed_free_lock, state);
267}
268
269static void heap_test(void)
270{
271#if WITH_LIB_HEAP_CMPCTMALLOC
272 cmpct_test();
273#else
274 void *ptr[16];
275
276 ptr[0] = HEAP_MALLOC(8);
277 ptr[1] = HEAP_MALLOC(32);
278 ptr[2] = HEAP_MALLOC(7);
279 ptr[3] = HEAP_MALLOC(0);
280 ptr[4] = HEAP_MALLOC(98713);
281 ptr[5] = HEAP_MALLOC(16);
282
283 HEAP_FREE(ptr[5]);
284 HEAP_FREE(ptr[1]);
285 HEAP_FREE(ptr[3]);
286 HEAP_FREE(ptr[0]);
287 HEAP_FREE(ptr[4]);
288 HEAP_FREE(ptr[2]);
289
290 HEAP_DUMP();
291
292 int i;
293 for (i=0; i < 16; i++)
294 ptr[i] = 0;
295
296 for (i=0; i < 32768; i++) {
297 unsigned int index = (unsigned int)rand() % 16;
298
299 if ((i % (16*1024)) == 0)
300 printf("pass %d\n", i);
301
302// printf("index 0x%x\n", index);
303 if (ptr[index]) {
304// printf("freeing ptr[0x%x] = %p\n", index, ptr[index]);
305 HEAP_FREE(ptr[index]);
306 ptr[index] = 0;
307 }
308 unsigned int align = 1 << ((unsigned int)rand() % 8);
309 ptr[index] = HEAP_MEMALIGN(align, (unsigned int)rand() % 32768);
310// printf("ptr[0x%x] = %p, align 0x%x\n", index, ptr[index], align);
311
312 DEBUG_ASSERT(((addr_t)ptr[index] % align) == 0);
313// heap_dump();
314 }
315
316 for (i=0; i < 16; i++) {
317 if (ptr[i])
318 HEAP_FREE(ptr[i]);
319 }
320
321 HEAP_DUMP();
322#endif
323}
324
325
326#if LK_DEBUGLEVEL > 1
327#if WITH_LIB_CONSOLE
328
329#include <lib/console.h>
330
331static int cmd_heap(int argc, const cmd_args *argv);
332
333STATIC_COMMAND_START
334STATIC_COMMAND("heap", "heap debug commands", &cmd_heap)
335STATIC_COMMAND_END(heap);
336
337static int cmd_heap(int argc, const cmd_args *argv)
338{
339 if (argc < 2) {
340notenoughargs:
341 printf("not enough arguments\n");
342usage:
343 printf("usage:\n");
344 printf("\t%s info\n", argv[0].str);
345 printf("\t%s trace\n", argv[0].str);
346 printf("\t%s trim\n", argv[0].str);
347 printf("\t%s alloc <size> [alignment]\n", argv[0].str);
348 printf("\t%s realloc <ptr> <size>\n", argv[0].str);
349 printf("\t%s free <address>\n", argv[0].str);
350 return -1;
351 }
352
353 if (strcmp(argv[1].str, "info") == 0) {
354 heap_dump();
355 } else if (strcmp(argv[1].str, "test") == 0) {
356 heap_test();
357 } else if (strcmp(argv[1].str, "trace") == 0) {
358 heap_trace = !heap_trace;
359 printf("heap trace is now %s\n", heap_trace ? "on" : "off");
360 } else if (strcmp(argv[1].str, "trim") == 0) {
361 heap_trim();
362 } else if (strcmp(argv[1].str, "alloc") == 0) {
363 if (argc < 3) goto notenoughargs;
364
365 void *ptr = memalign((argc >= 4) ? argv[3].u : 0, argv[2].u);
366 printf("memalign returns %p\n", ptr);
367 } else if (strcmp(argv[1].str, "realloc") == 0) {
368 if (argc < 4) goto notenoughargs;
369
370 void *ptr = realloc(argv[2].p, argv[3].u);
371 printf("realloc returns %p\n", ptr);
372 } else if (strcmp(argv[1].str, "free") == 0) {
373 if (argc < 2) goto notenoughargs;
374
375 free(argv[2].p);
376 } else {
377 printf("unrecognized command\n");
378 goto usage;
379 }
380
381 return 0;
382}
383
384#endif
385#endif
386
387