1 /*
2 * Copyright (C) 2008 The Android Open Source Project
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in
12 * the documentation and/or other materials provided with the
13 * distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
18 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
19 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
21 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
22 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
23 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
25 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28 #include <errno.h>
29 #include <pthread.h>
30 #include <stdio.h>
31 #include <arpa/inet.h>
32 #include <sys/socket.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include <unistd.h>
36 #include <errno.h>
37 #include <stddef.h>
38 #include <stdarg.h>
39 #include <fcntl.h>
40 #include <unwind.h>
41 #include <dlfcn.h>
43 #include <sys/socket.h>
44 #include <sys/un.h>
45 #include <sys/select.h>
46 #include <sys/types.h>
47 #include <sys/system_properties.h>
49 #include "dlmalloc.h"
50 #include "logd.h"
51 #include "malloc_debug_common.h"
53 // This file should be included into the build only when
54 // MALLOC_LEAK_CHECK, or MALLOC_QEMU_INSTRUMENT, or both
55 // macros are defined.
56 #ifndef MALLOC_LEAK_CHECK
57 #error MALLOC_LEAK_CHECK is not defined.
58 #endif // !MALLOC_LEAK_CHECK
60 // Global variables defined in malloc_debug_common.c
61 extern int gMallocLeakZygoteChild;
62 extern pthread_mutex_t gAllocationsMutex;
63 extern HashTable gHashTable;
64 extern const MallocDebug __libc_malloc_default_dispatch;
65 extern const MallocDebug* __libc_malloc_dispatch;
67 // =============================================================================
68 // log functions
69 // =============================================================================
71 #define debug_log(format, ...) \
72 __libc_android_log_print(ANDROID_LOG_DEBUG, "malloc_leak_check", (format), ##__VA_ARGS__ )
73 #define error_log(format, ...) \
74 __libc_android_log_print(ANDROID_LOG_ERROR, "malloc_leak_check", (format), ##__VA_ARGS__ )
75 #define info_log(format, ...) \
76 __libc_android_log_print(ANDROID_LOG_INFO, "malloc_leak_check", (format), ##__VA_ARGS__ )
78 static int gTrapOnError = 1;
80 #define MALLOC_ALIGNMENT 8
81 #define GUARD 0x48151642
82 #define DEBUG 0
84 // =============================================================================
85 // Structures
86 // =============================================================================
87 typedef struct AllocationEntry AllocationEntry;
88 struct AllocationEntry {
89 HashEntry* entry;
90 uint32_t guard;
91 };
94 // =============================================================================
95 // Hash Table functions
96 // =============================================================================
97 static uint32_t get_hash(intptr_t* backtrace, size_t numEntries)
98 {
99 if (backtrace == NULL) return 0;
101 int hash = 0;
102 size_t i;
103 for (i = 0 ; i < numEntries ; i++) {
104 hash = (hash * 33) + (backtrace[i] >> 2);
105 }
107 return hash;
108 }
110 static HashEntry* find_entry(HashTable* table, int slot,
111 intptr_t* backtrace, size_t numEntries, size_t size)
112 {
113 HashEntry* entry = table->slots[slot];
114 while (entry != NULL) {
115 //debug_log("backtrace: %p, entry: %p entry->backtrace: %p\n",
116 // backtrace, entry, (entry != NULL) ? entry->backtrace : NULL);
117 /*
118 * See if the entry matches exactly. We compare the "size" field,
119 * including the flag bits.
120 */
121 if (entry->size == size && entry->numEntries == numEntries &&
122 !memcmp(backtrace, entry->backtrace, numEntries * sizeof(intptr_t))) {
123 return entry;
124 }
126 entry = entry->next;
127 }
129 return NULL;
130 }
132 static HashEntry* record_backtrace(intptr_t* backtrace, size_t numEntries, size_t size)
133 {
134 size_t hash = get_hash(backtrace, numEntries);
135 size_t slot = hash % HASHTABLE_SIZE;
137 if (size & SIZE_FLAG_MASK) {
138 debug_log("malloc_debug: allocation %zx exceeds bit width\n", size);
139 abort();
140 }
142 if (gMallocLeakZygoteChild)
143 size |= SIZE_FLAG_ZYGOTE_CHILD;
145 HashEntry* entry = find_entry(&gHashTable, slot, backtrace, numEntries, size);
147 if (entry != NULL) {
148 entry->allocations++;
149 } else {
150 // create a new entry
151 entry = (HashEntry*)dlmalloc(sizeof(HashEntry) + numEntries*sizeof(intptr_t));
152 entry->allocations = 1;
153 entry->slot = slot;
154 entry->prev = NULL;
155 entry->next = gHashTable.slots[slot];
156 entry->numEntries = numEntries;
157 entry->size = size;
159 memcpy(entry->backtrace, backtrace, numEntries * sizeof(intptr_t));
161 gHashTable.slots[slot] = entry;
163 if (entry->next != NULL) {
164 entry->next->prev = entry;
165 }
167 // we just added an entry, increase the size of the hashtable
168 gHashTable.count++;
169 }
171 return entry;
172 }
174 static int is_valid_entry(HashEntry* entry)
175 {
176 if (entry != NULL) {
177 int i;
178 for (i = 0 ; i < HASHTABLE_SIZE ; i++) {
179 HashEntry* e1 = gHashTable.slots[i];
181 while (e1 != NULL) {
182 if (e1 == entry) {
183 return 1;
184 }
186 e1 = e1->next;
187 }
188 }
189 }
191 return 0;
192 }
194 static void remove_entry(HashEntry* entry)
195 {
196 HashEntry* prev = entry->prev;
197 HashEntry* next = entry->next;
199 if (prev != NULL) entry->prev->next = next;
200 if (next != NULL) entry->next->prev = prev;
202 if (prev == NULL) {
203 // we are the head of the list. set the head to be next
204 gHashTable.slots[entry->slot] = entry->next;
205 }
207 // we just removed and entry, decrease the size of the hashtable
208 gHashTable.count--;
209 }
212 // =============================================================================
213 // stack trace functions
214 // =============================================================================
216 typedef struct
217 {
218 size_t count;
219 intptr_t* addrs;
220 } stack_crawl_state_t;
223 /* depends how the system includes define this */
224 #ifdef HAVE_UNWIND_CONTEXT_STRUCT
225 typedef struct _Unwind_Context __unwind_context;
226 #else
227 typedef _Unwind_Context __unwind_context;
228 #endif
230 static _Unwind_Reason_Code trace_function(__unwind_context *context, void *arg)
231 {
232 stack_crawl_state_t* state = (stack_crawl_state_t*)arg;
233 if (state->count) {
234 intptr_t ip = (intptr_t)_Unwind_GetIP(context);
235 if (ip) {
236 state->addrs[0] = ip;
237 state->addrs++;
238 state->count--;
239 return _URC_NO_REASON;
240 }
241 }
242 /*
243 * If we run out of space to record the address or 0 has been seen, stop
244 * unwinding the stack.
245 */
246 return _URC_END_OF_STACK;
247 }
249 static inline
250 int get_backtrace(intptr_t* addrs, size_t max_entries)
251 {
252 stack_crawl_state_t state;
253 state.count = max_entries;
254 state.addrs = (intptr_t*)addrs;
255 _Unwind_Backtrace(trace_function, (void*)&state);
256 return max_entries - state.count;
257 }
259 // =============================================================================
260 // malloc check functions
261 // =============================================================================
263 #define CHK_FILL_FREE 0xef
264 #define CHK_SENTINEL_VALUE 0xeb
265 #define CHK_SENTINEL_HEAD_SIZE 16
266 #define CHK_SENTINEL_TAIL_SIZE 16
267 #define CHK_OVERHEAD_SIZE ( CHK_SENTINEL_HEAD_SIZE + \
268 CHK_SENTINEL_TAIL_SIZE + \
269 sizeof(size_t) )
271 static void dump_stack_trace()
272 {
273 intptr_t addrs[20];
274 int c = get_backtrace(addrs, 20);
275 char buf[16];
276 char tmp[16*20];
277 int i;
279 tmp[0] = 0; // Need to initialize tmp[0] for the first strcat
280 for (i=0 ; i<c; i++) {
281 snprintf(buf, sizeof buf, "%2d: %08x\n", i, addrs[i]);
282 strlcat(tmp, buf, sizeof tmp);
283 }
284 __libc_android_log_print(ANDROID_LOG_ERROR, "libc", "call stack:\n%s", tmp);
285 }
287 static int is_valid_malloc_pointer(void* addr)
288 {
289 return 1;
290 }
292 static void assert_log_message(const char* format, ...)
293 {
294 va_list args;
296 pthread_mutex_lock(&gAllocationsMutex);
297 {
298 const MallocDebug* current_dispatch = __libc_malloc_dispatch;
299 __libc_malloc_dispatch = &__libc_malloc_default_dispatch;
300 va_start(args, format);
301 __libc_android_log_vprint(ANDROID_LOG_ERROR, "libc",
302 format, args);
303 va_end(args);
304 dump_stack_trace();
305 if (gTrapOnError) {
306 __builtin_trap();
307 }
308 __libc_malloc_dispatch = current_dispatch;
309 }
310 pthread_mutex_unlock(&gAllocationsMutex);
311 }
313 static void assert_valid_malloc_pointer(void* mem)
314 {
315 if (mem && !is_valid_malloc_pointer(mem)) {
316 assert_log_message(
317 "*** MALLOC CHECK: buffer %p, is not a valid "
318 "malloc pointer (are you mixing up new/delete "
319 "and malloc/free?)", mem);
320 }
321 }
323 /* Check that a given address corresponds to a guarded block,
324 * and returns its original allocation size in '*allocated'.
325 * 'func' is the capitalized name of the caller function.
326 * Returns 0 on success, or -1 on failure.
327 * NOTE: Does not return if gTrapOnError is set.
328 */
329 static int chk_mem_check(void* mem,
330 size_t* allocated,
331 const char* func)
332 {
333 char* buffer;
334 size_t offset, bytes;
335 int i;
336 char* buf;
338 /* first check the bytes in the sentinel header */
339 buf = (char*)mem - CHK_SENTINEL_HEAD_SIZE;
340 for (i=0 ; i<CHK_SENTINEL_HEAD_SIZE ; i++) {
341 if (buf[i] != CHK_SENTINEL_VALUE) {
342 assert_log_message(
343 "*** %s CHECK: buffer %p "
344 "corrupted %d bytes before allocation",
345 func, mem, CHK_SENTINEL_HEAD_SIZE-i);
346 return -1;
347 }
348 }
350 /* then the ones in the sentinel trailer */
351 buffer = (char*)mem - CHK_SENTINEL_HEAD_SIZE;
352 offset = dlmalloc_usable_size(buffer) - sizeof(size_t);
353 bytes = *(size_t *)(buffer + offset);
355 buf = (char*)mem + bytes;
356 for (i=CHK_SENTINEL_TAIL_SIZE-1 ; i>=0 ; i--) {
357 if (buf[i] != CHK_SENTINEL_VALUE) {
358 assert_log_message(
359 "*** %s CHECK: buffer %p, size=%lu, "
360 "corrupted %d bytes after allocation",
361 func, buffer, bytes, i+1);
362 return -1;
363 }
364 }
366 *allocated = bytes;
367 return 0;
368 }
371 void* chk_malloc(size_t bytes)
372 {
373 char* buffer = (char*)dlmalloc(bytes + CHK_OVERHEAD_SIZE);
374 if (buffer) {
375 memset(buffer, CHK_SENTINEL_VALUE, bytes + CHK_OVERHEAD_SIZE);
376 size_t offset = dlmalloc_usable_size(buffer) - sizeof(size_t);
377 *(size_t *)(buffer + offset) = bytes;
378 buffer += CHK_SENTINEL_HEAD_SIZE;
379 }
380 return buffer;
381 }
383 void chk_free(void* mem)
384 {
385 assert_valid_malloc_pointer(mem);
386 if (mem) {
387 size_t size;
388 char* buffer;
390 if (chk_mem_check(mem, &size, "FREE") == 0) {
391 buffer = (char*)mem - CHK_SENTINEL_HEAD_SIZE;
392 memset(buffer, CHK_FILL_FREE, size + CHK_OVERHEAD_SIZE);
393 dlfree(buffer);
394 }
395 }
396 }
398 void* chk_calloc(size_t n_elements, size_t elem_size)
399 {
400 size_t size;
401 void* ptr;
403 /* Fail on overflow - just to be safe even though this code runs only
404 * within the debugging C library, not the production one */
405 if (n_elements && MAX_SIZE_T / n_elements < elem_size) {
406 return NULL;
407 }
408 size = n_elements * elem_size;
409 ptr = chk_malloc(size);
410 if (ptr != NULL) {
411 memset(ptr, 0, size);
412 }
413 return ptr;
414 }
416 void* chk_realloc(void* mem, size_t bytes)
417 {
418 char* buffer;
419 int ret;
420 size_t old_bytes = 0;
422 assert_valid_malloc_pointer(mem);
424 if (mem != NULL && chk_mem_check(mem, &old_bytes, "REALLOC") < 0)
425 return NULL;
427 char* new_buffer = chk_malloc(bytes);
428 if (mem == NULL) {
429 return new_buffer;
430 }
432 if (new_buffer) {
433 size_t size = (bytes < old_bytes)?(bytes):(old_bytes);
434 memcpy(new_buffer, mem, size);
435 chk_free(mem);
436 }
438 return new_buffer;
439 }
441 void* chk_memalign(size_t alignment, size_t bytes)
442 {
443 // XXX: it's better to use malloc, than being wrong
444 return chk_malloc(bytes);
445 }
447 // =============================================================================
448 // malloc fill functions
449 // =============================================================================
451 void* fill_malloc(size_t bytes)
452 {
453 void* buffer = dlmalloc(bytes);
454 if (buffer) {
455 memset(buffer, CHK_SENTINEL_VALUE, bytes);
456 }
457 return buffer;
458 }
460 void fill_free(void* mem)
461 {
462 size_t bytes = dlmalloc_usable_size(mem);
463 memset(mem, CHK_FILL_FREE, bytes);
464 dlfree(mem);
465 }
467 void* fill_realloc(void* mem, size_t bytes)
468 {
469 void* buffer = fill_malloc(bytes);
470 if (mem == NULL) {
471 return buffer;
472 }
473 if (buffer) {
474 size_t old_size = dlmalloc_usable_size(mem);
475 size_t size = (bytes < old_size)?(bytes):(old_size);
476 memcpy(buffer, mem, size);
477 fill_free(mem);
478 }
479 return buffer;
480 }
482 void* fill_memalign(size_t alignment, size_t bytes)
483 {
484 void* buffer = dlmemalign(alignment, bytes);
485 if (buffer) {
486 memset(buffer, CHK_SENTINEL_VALUE, bytes);
487 }
488 return buffer;
489 }
491 // =============================================================================
492 // malloc leak functions
493 // =============================================================================
495 #define MEMALIGN_GUARD ((void*)0xA1A41520)
497 void* leak_malloc(size_t bytes)
498 {
499 // allocate enough space infront of the allocation to store the pointer for
500 // the alloc structure. This will making free'ing the structer really fast!
502 // 1. allocate enough memory and include our header
503 // 2. set the base pointer to be right after our header
505 void* base = dlmalloc(bytes + sizeof(AllocationEntry));
506 if (base != NULL) {
507 pthread_mutex_lock(&gAllocationsMutex);
509 intptr_t backtrace[BACKTRACE_SIZE];
510 size_t numEntries = get_backtrace(backtrace, BACKTRACE_SIZE);
512 AllocationEntry* header = (AllocationEntry*)base;
513 header->entry = record_backtrace(backtrace, numEntries, bytes);
514 header->guard = GUARD;
516 // now increment base to point to after our header.
517 // this should just work since our header is 8 bytes.
518 base = (AllocationEntry*)base + 1;
520 pthread_mutex_unlock(&gAllocationsMutex);
521 }
523 return base;
524 }
526 void leak_free(void* mem)
527 {
528 if (mem != NULL) {
529 pthread_mutex_lock(&gAllocationsMutex);
531 // check the guard to make sure it is valid
532 AllocationEntry* header = (AllocationEntry*)mem - 1;
534 if (header->guard != GUARD) {
535 // could be a memaligned block
536 if (((void**)mem)[-1] == MEMALIGN_GUARD) {
537 mem = ((void**)mem)[-2];
538 header = (AllocationEntry*)mem - 1;
539 }
540 }
542 if (header->guard == GUARD || is_valid_entry(header->entry)) {
543 // decrement the allocations
544 HashEntry* entry = header->entry;
545 entry->allocations--;
546 if (entry->allocations <= 0) {
547 remove_entry(entry);
548 dlfree(entry);
549 }
551 // now free the memory!
552 dlfree(header);
553 } else {
554 debug_log("WARNING bad header guard: '0x%x'! and invalid entry: %p\n",
555 header->guard, header->entry);
556 }
558 pthread_mutex_unlock(&gAllocationsMutex);
559 }
560 }
562 void* leak_calloc(size_t n_elements, size_t elem_size)
563 {
564 size_t size;
565 void* ptr;
567 /* Fail on overflow - just to be safe even though this code runs only
568 * within the debugging C library, not the production one */
569 if (n_elements && MAX_SIZE_T / n_elements < elem_size) {
570 return NULL;
571 }
572 size = n_elements * elem_size;
573 ptr = leak_malloc(size);
574 if (ptr != NULL) {
575 memset(ptr, 0, size);
576 }
577 return ptr;
578 }
580 void* leak_realloc(void* oldMem, size_t bytes)
581 {
582 if (oldMem == NULL) {
583 return leak_malloc(bytes);
584 }
585 void* newMem = NULL;
586 AllocationEntry* header = (AllocationEntry*)oldMem - 1;
587 if (header && header->guard == GUARD) {
588 size_t oldSize = header->entry->size & ~SIZE_FLAG_MASK;
589 newMem = leak_malloc(bytes);
590 if (newMem != NULL) {
591 size_t copySize = (oldSize <= bytes) ? oldSize : bytes;
592 memcpy(newMem, oldMem, copySize);
593 leak_free(oldMem);
594 }
595 } else {
596 newMem = dlrealloc(oldMem, bytes);
597 }
598 return newMem;
599 }
601 void* leak_memalign(size_t alignment, size_t bytes)
602 {
603 // we can just use malloc
604 if (alignment <= MALLOC_ALIGNMENT)
605 return leak_malloc(bytes);
607 // need to make sure it's a power of two
608 if (alignment & (alignment-1))
609 alignment = 1L << (31 - __builtin_clz(alignment));
611 // here, aligment is at least MALLOC_ALIGNMENT<<1 bytes
612 // we will align by at least MALLOC_ALIGNMENT bytes
613 // and at most alignment-MALLOC_ALIGNMENT bytes
614 size_t size = (alignment-MALLOC_ALIGNMENT) + bytes;
615 void* base = leak_malloc(size);
616 if (base != NULL) {
617 intptr_t ptr = (intptr_t)base;
618 if ((ptr % alignment) == 0)
619 return base;
621 // align the pointer
622 ptr += ((-ptr) % alignment);
624 // there is always enough space for the base pointer and the guard
625 ((void**)ptr)[-1] = MEMALIGN_GUARD;
626 ((void**)ptr)[-2] = base;
628 return (void*)ptr;
629 }
630 return base;
631 }