1 /*
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
40 static bool heap_trace = false;
41 #else
42 #define heap_trace (false)
43 #endif
44
45 #if WITH_LIB_HEAP_MINIHEAP
46 /* miniheap implementation */
47 #include <lib/miniheap.h>
48
HEAP_MALLOC(size_t s)49 static inline void *HEAP_MALLOC(size_t s) { return miniheap_malloc(s); }
HEAP_REALLOC(void * ptr,size_t s)50 static inline void *HEAP_REALLOC(void *ptr, size_t s) { return miniheap_realloc(ptr, s); }
HEAP_MEMALIGN(size_t boundary,size_t s)51 static inline void *HEAP_MEMALIGN(size_t boundary, size_t s) { return miniheap_memalign(boundary, s); }
52 #define HEAP_FREE miniheap_free
HEAP_CALLOC(size_t n,size_t s)53 static inline void *HEAP_CALLOC(size_t n, size_t s)
54 {
55 size_t realsize = n * s;
56
57 void *ptr = miniheap_malloc(realsize);
58 if (likely(ptr))
59 memset(ptr, 0, realsize);
60 return ptr;
61 }
HEAP_INIT(void)62 static inline void HEAP_INIT(void)
63 {
64 /* start the heap off with some spare memory in the page allocator */
65 size_t len;
66 void *ptr = page_first_alloc(&len);
67 if (!ptr) {
68 panic("heap init failed");
69 }
70 miniheap_init(ptr, len);
71 }
72 #define HEAP_DUMP miniheap_dump
73 #define HEAP_TRIM miniheap_trim
74
75 /* end miniheap implementation */
76 #elif WITH_LIB_HEAP_CMPCTMALLOC
77 /* cmpctmalloc implementation */
78 #include <lib/cmpctmalloc.h>
79
80 #define HEAP_MEMALIGN(boundary, s) cmpct_memalign(s, boundary)
81 #define HEAP_MALLOC cmpct_alloc
82 #define HEAP_REALLOC cmpct_realloc
83 #define HEAP_FREE cmpct_free
84 #define HEAP_INIT cmpct_init
85 #define HEAP_DUMP cmpct_dump
86 #define HEAP_TRIM cmpct_trim
HEAP_CALLOC(size_t n,size_t s)87 static inline void *HEAP_CALLOC(size_t n, size_t s)
88 {
89 size_t realsize = n * s;
90
91 void *ptr = cmpct_alloc(realsize);
92 if (likely(ptr))
93 memset(ptr, 0, realsize);
94 return ptr;
95 }
96
97 /* end cmpctmalloc implementation */
98 #elif WITH_LIB_HEAP_DLMALLOC
99 /* dlmalloc implementation */
100 #include <lib/dlmalloc.h>
101
102 #define HEAP_MALLOC(s) dlmalloc(s)
103 #define HEAP_CALLOC(n, s) dlcalloc(n, s)
104 #define HEAP_MEMALIGN(b, s) dlmemalign(b, s)
105 #define HEAP_REALLOC(p, s) dlrealloc(p, s)
106 #define HEAP_FREE(p) dlfree(p)
HEAP_INIT(void)107 static inline void HEAP_INIT(void) {}
108
dump_callback(void * start,void * end,size_t used_bytes,void * arg)109 static void dump_callback(void *start, void *end, size_t used_bytes, void *arg) {
110 printf("\t\tstart %p end %p used_bytes %zu\n", start, end, used_bytes);
111 }
112
HEAP_DUMP(void)113 static inline void HEAP_DUMP(void)
114 {
115 struct mallinfo minfo = dlmallinfo();
116
117 printf("\tmallinfo (dlmalloc):\n");
118 printf("\t\tarena space 0x%zx\n", minfo.arena);
119 printf("\t\tfree chunks 0x%zx\n", minfo.ordblks);
120 printf("\t\tspace in mapped regions 0x%zx\n", minfo.hblkhd);
121 printf("\t\tmax total allocated 0x%zx\n", minfo.usmblks);
122 printf("\t\ttotal allocated 0x%zx\n", minfo.uordblks);
123 printf("\t\tfree 0x%zx\n", minfo.fordblks);
124 printf("\t\treleasable space 0x%zx\n", minfo.keepcost);
125
126 printf("\theap block list:\n");
127 dlmalloc_inspect_all(&dump_callback, NULL);
128 }
129
HEAP_TRIM(void)130 static inline void HEAP_TRIM(void) { dlmalloc_trim(0); }
131
132 /* end dlmalloc implementation */
133 #else
134 #error need to select valid heap implementation or provide wrapper
135 #endif
136
HEAP_POSIX_MEMALIGN(void ** res,size_t align,size_t size)137 static inline int HEAP_POSIX_MEMALIGN(void **res, size_t align, size_t size)
138 {
139 if (align < sizeof(void *)) {
140 LTRACEF("Invalid alignment requested\n");
141 return ERR_INVALID_ARGS;
142 }
143 if (res == NULL) {
144 LTRACEF("Invalid result pointer\n");
145 return ERR_INVALID_ARGS;
146 }
147 void *mem = HEAP_MEMALIGN(align, size);
148 if (mem == NULL) {
149 LTRACEF("Insufficient memory\n");
150 return ERR_NO_MEMORY;
151 }
152 *res = mem;
153 return NO_ERROR;
154 }
155
heap_init(void)156 void heap_init(void)
157 {
158 HEAP_INIT();
159 }
160
heap_trim(void)161 void heap_trim(void)
162 {
163 HEAP_TRIM();
164 }
165
malloc(size_t size)166 void *malloc(size_t size)
167 {
168 LTRACEF("size %zd\n", size);
169
170 void *ptr = HEAP_MALLOC(size);
171 if (heap_trace)
172 printf("caller %p malloc %zu -> %p\n", __GET_CALLER(), size, ptr);
173 return ptr;
174 }
175
memalign(size_t boundary,size_t size)176 void *memalign(size_t boundary, size_t size)
177 {
178 LTRACEF("boundary %zu, size %zd\n", boundary, size);
179
180 void *ptr = HEAP_MEMALIGN(boundary, size);
181 if (heap_trace)
182 printf("caller %p memalign %zu, %zu -> %p\n", __GET_CALLER(), boundary, size, ptr);
183 return ptr;
184 }
185
posix_memalign(void ** res,size_t align,size_t size)186 int posix_memalign(void **res, size_t align, size_t size)
187 {
188 LTRACEF("res %p, align %zu, size %zd\n", res, align, size);
189
190 int rc = HEAP_POSIX_MEMALIGN(res, align, size);
191 if (heap_trace) {
192 printf("caller %p posix_memalign %p, %zu, %zu -> %d\n", __GET_CALLER(),
193 res, align, size, rc);
194 }
195 return rc;
196 }
197
calloc(size_t count,size_t size)198 void *calloc(size_t count, size_t size)
199 {
200 LTRACEF("count %zu, size %zd\n", count, size);
201
202 void *ptr = HEAP_CALLOC(count, size);
203 if (heap_trace)
204 printf("caller %p calloc %zu, %zu -> %p\n", __GET_CALLER(), count, size, ptr);
205 return ptr;
206 }
207
realloc(void * ptr,size_t size)208 void *realloc(void *ptr, size_t size)
209 {
210 LTRACEF("ptr %p, size %zd\n", ptr, size);
211
212 void *ptr2 = HEAP_REALLOC(ptr, size);
213 if (heap_trace)
214 printf("caller %p realloc %p, %zu -> %p\n", __GET_CALLER(), ptr, size, ptr2);
215 return ptr2;
216 }
217
free(void * ptr)218 void free(void *ptr)
219 {
220 LTRACEF("ptr %p\n", ptr);
221 if (heap_trace)
222 printf("caller %p free %p\n", __GET_CALLER(), ptr);
223
224 HEAP_FREE(ptr);
225 }
226
heap_dump(void)227 static void heap_dump(void)
228 {
229 HEAP_DUMP();
230 }
231
heap_test(void)232 static void heap_test(void)
233 {
234 #if WITH_LIB_HEAP_CMPCTMALLOC
235 cmpct_test();
236 #else
237 void *ptr[16];
238
239 ptr[0] = HEAP_MALLOC(8);
240 ptr[1] = HEAP_MALLOC(32);
241 ptr[2] = HEAP_MALLOC(7);
242 ptr[3] = HEAP_MALLOC(0);
243 ptr[4] = HEAP_MALLOC(98713);
244 ptr[5] = HEAP_MALLOC(16);
245
246 HEAP_FREE(ptr[5]);
247 HEAP_FREE(ptr[1]);
248 HEAP_FREE(ptr[3]);
249 HEAP_FREE(ptr[0]);
250 HEAP_FREE(ptr[4]);
251 HEAP_FREE(ptr[2]);
252
253 HEAP_DUMP();
254
255 int i;
256 for (i=0; i < 16; i++)
257 ptr[i] = 0;
258
259 for (i=0; i < 32768; i++) {
260 unsigned int index = (unsigned int)rand() % 16;
261
262 if ((i % (16*1024)) == 0)
263 printf("pass %d\n", i);
264
265 // printf("index 0x%x\n", index);
266 if (ptr[index]) {
267 // printf("freeing ptr[0x%x] = %p\n", index, ptr[index]);
268 HEAP_FREE(ptr[index]);
269 ptr[index] = 0;
270 }
271 unsigned int align = 1 << ((unsigned int)rand() % 8);
272 ptr[index] = HEAP_MEMALIGN(align, (unsigned int)rand() % 32768);
273 // printf("ptr[0x%x] = %p, align 0x%x\n", index, ptr[index], align);
274
275 DEBUG_ASSERT(((addr_t)ptr[index] % align) == 0);
276 // heap_dump();
277 }
278
279 for (i=0; i < 16; i++) {
280 if (ptr[i])
281 HEAP_FREE(ptr[i]);
282 }
283
284 HEAP_DUMP();
285 #endif
286 }
287
288
289 #if LK_DEBUGLEVEL > 1
290 #if WITH_LIB_CONSOLE
291
292 #include <lib/console.h>
293
294 static int cmd_heap(int argc, const cmd_args *argv);
295
296 STATIC_COMMAND_START
297 STATIC_COMMAND("heap", "heap debug commands", &cmd_heap)
298 STATIC_COMMAND_END(heap);
299
cmd_heap(int argc,const cmd_args * argv)300 static int cmd_heap(int argc, const cmd_args *argv)
301 {
302 if (argc < 2) {
303 notenoughargs:
304 printf("not enough arguments\n");
305 usage:
306 printf("usage:\n");
307 printf("\t%s info\n", argv[0].str);
308 printf("\t%s trace\n", argv[0].str);
309 printf("\t%s trim\n", argv[0].str);
310 printf("\t%s alloc <size> [alignment]\n", argv[0].str);
311 printf("\t%s realloc <ptr> <size>\n", argv[0].str);
312 printf("\t%s free <address>\n", argv[0].str);
313 return -1;
314 }
315
316 if (strcmp(argv[1].str, "info") == 0) {
317 heap_dump();
318 } else if (strcmp(argv[1].str, "test") == 0) {
319 heap_test();
320 } else if (strcmp(argv[1].str, "trace") == 0) {
321 heap_trace = !heap_trace;
322 printf("heap trace is now %s\n", heap_trace ? "on" : "off");
323 } else if (strcmp(argv[1].str, "trim") == 0) {
324 heap_trim();
325 } else if (strcmp(argv[1].str, "alloc") == 0) {
326 if (argc < 3) goto notenoughargs;
327
328 void *ptr = memalign((argc >= 4) ? argv[3].u : 0, argv[2].u);
329 printf("memalign returns %p\n", ptr);
330 } else if (strcmp(argv[1].str, "realloc") == 0) {
331 if (argc < 4) goto notenoughargs;
332
333 void *ptr = realloc(argv[2].p, argv[3].u);
334 printf("realloc returns %p\n", ptr);
335 } else if (strcmp(argv[1].str, "free") == 0) {
336 if (argc < 2) goto notenoughargs;
337
338 free(argv[2].p);
339 } else {
340 printf("unrecognized command\n");
341 goto usage;
342 }
343
344 return 0;
345 }
346
347 #endif
348 #endif
349
350
351