1/*
2 * Copyright (C) 2012 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
29#include <errno.h>
30#include <pthread.h>
31#include <time.h>
32#include <stdio.h>
33#include <arpa/inet.h>
34#include <sys/socket.h>
35#include <stdlib.h>
36#include <string.h>
37#include <unistd.h>
38#include <errno.h>
39#include <stddef.h>
40#include <stdarg.h>
41#include <fcntl.h>
42#include <unwind.h>
43#include <dlfcn.h>
44#include <stdbool.h>
45
46#include <sys/types.h>
47#include <sys/system_properties.h>
48
49#include "dlmalloc.h"
50#include "logd.h"
51
52#include "malloc_debug_common.h"
53#include "malloc_debug_check_mapinfo.h"
54
55static mapinfo *milist;
56
57/* libc.debug.malloc.backlog */
58extern unsigned int malloc_double_free_backlog;
59
60#define MAX_BACKTRACE_DEPTH 15
61#define ALLOCATION_TAG      0x1ee7d00d
62#define BACKLOG_TAG         0xbabecafe
63#define FREE_POISON         0xa5
64#define BACKLOG_DEFAULT_LEN 100
65#define FRONT_GUARD         0xaa
66#define FRONT_GUARD_LEN     (1<<5)
67#define REAR_GUARD          0xbb
68#define REAR_GUARD_LEN      (1<<5)
69
70static void log_message(const char* format, ...) {
71    extern const MallocDebug __libc_malloc_default_dispatch;
72    extern const MallocDebug* __libc_malloc_dispatch;
73    extern pthread_mutex_t gAllocationsMutex;
74
75    va_list args;
76    {
77        ScopedPthreadMutexLocker locker(&gAllocationsMutex);
78        const MallocDebug* current_dispatch = __libc_malloc_dispatch;
79        __libc_malloc_dispatch = &__libc_malloc_default_dispatch;
80        va_start(args, format);
81        __libc_android_log_vprint(ANDROID_LOG_ERROR, "libc", format, args);
82        va_end(args);
83        __libc_malloc_dispatch = current_dispatch;
84    }
85}
86
87struct hdr_t {
88    uint32_t tag;
89    hdr_t* prev;
90    hdr_t* next;
91    intptr_t bt[MAX_BACKTRACE_DEPTH];
92    int bt_depth;
93    intptr_t freed_bt[MAX_BACKTRACE_DEPTH];
94    int freed_bt_depth;
95    size_t size;
96    char front_guard[FRONT_GUARD_LEN];
97} __attribute__((packed));
98
99struct ftr_t {
100    char rear_guard[REAR_GUARD_LEN];
101} __attribute__((packed));
102
103static inline ftr_t* to_ftr(hdr_t* hdr) {
104    return reinterpret_cast<ftr_t*>(reinterpret_cast<char*>(hdr + 1) + hdr->size);
105}
106
107static inline void* user(hdr_t* hdr) {
108    return hdr + 1;
109}
110
111static inline hdr_t* meta(void* user) {
112    return reinterpret_cast<hdr_t*>(user) - 1;
113}
114
115static unsigned num;
116static hdr_t *tail;
117static hdr_t *head;
118static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
119
120static unsigned backlog_num;
121static hdr_t *backlog_tail;
122static hdr_t *backlog_head;
123static pthread_mutex_t backlog_lock = PTHREAD_MUTEX_INITIALIZER;
124
125extern __LIBC_HIDDEN__ int get_backtrace(intptr_t* addrs, size_t max_entries);
126
127static void print_backtrace(const intptr_t *bt, unsigned int depth) {
128    const mapinfo *mi;
129    unsigned int cnt;
130    unsigned int rel_pc;
131    intptr_t self_bt[MAX_BACKTRACE_DEPTH];
132
133    if (!bt) {
134        depth = get_backtrace(self_bt, MAX_BACKTRACE_DEPTH);
135        bt = self_bt;
136    }
137
138    log_message("*** *** *** *** *** *** *** *** *** *** *** *** *** *** *** ***\n");
139    for (cnt = 0; cnt < depth && cnt < MAX_BACKTRACE_DEPTH; cnt++) {
140        mi = pc_to_mapinfo(milist, bt[cnt], &rel_pc);
141        log_message("\t#%02d  pc %08x  %s\n", cnt,
142                   mi ? (intptr_t)rel_pc : bt[cnt],
143                   mi ? mi->name : "(unknown)");
144    }
145}
146
147static inline void init_front_guard(hdr_t *hdr) {
148    memset(hdr->front_guard, FRONT_GUARD, FRONT_GUARD_LEN);
149}
150
151static inline bool is_front_guard_valid(hdr_t *hdr) {
152    for (size_t i = 0; i < FRONT_GUARD_LEN; i++) {
153        if (hdr->front_guard[i] != FRONT_GUARD) {
154            return 0;
155        }
156    }
157    return 1;
158}
159
160static inline void init_rear_guard(hdr_t *hdr) {
161    ftr_t* ftr = to_ftr(hdr);
162    memset(ftr->rear_guard, REAR_GUARD, REAR_GUARD_LEN);
163}
164
165static inline bool is_rear_guard_valid(hdr_t *hdr) {
166    unsigned i;
167    int valid = 1;
168    int first_mismatch = -1;
169    ftr_t* ftr = to_ftr(hdr);
170    for (i = 0; i < REAR_GUARD_LEN; i++) {
171        if (ftr->rear_guard[i] != REAR_GUARD) {
172            if (first_mismatch < 0)
173                first_mismatch = i;
174            valid = 0;
175        } else if (first_mismatch >= 0) {
176            log_message("+++ REAR GUARD MISMATCH [%d, %d)\n", first_mismatch, i);
177            first_mismatch = -1;
178        }
179    }
180
181    if (first_mismatch >= 0)
182        log_message("+++ REAR GUARD MISMATCH [%d, %d)\n", first_mismatch, i);
183    return valid;
184}
185
186static inline void add_locked(hdr_t *hdr, hdr_t **tail, hdr_t **head) {
187    hdr->prev = NULL;
188    hdr->next = *head;
189    if (*head)
190        (*head)->prev = hdr;
191    else
192        *tail = hdr;
193    *head = hdr;
194}
195
196static inline int del_locked(hdr_t *hdr, hdr_t **tail, hdr_t **head) {
197    if (hdr->prev) {
198        hdr->prev->next = hdr->next;
199    } else {
200        *head = hdr->next;
201    }
202    if (hdr->next) {
203        hdr->next->prev = hdr->prev;
204    } else {
205        *tail = hdr->prev;
206    }
207    return 0;
208}
209
210static inline void add(hdr_t *hdr, size_t size) {
211    ScopedPthreadMutexLocker locker(&lock);
212    hdr->tag = ALLOCATION_TAG;
213    hdr->size = size;
214    init_front_guard(hdr);
215    init_rear_guard(hdr);
216    num++;
217    add_locked(hdr, &tail, &head);
218}
219
220static inline int del(hdr_t *hdr) {
221    if (hdr->tag != ALLOCATION_TAG) {
222        return -1;
223    }
224
225    ScopedPthreadMutexLocker locker(&lock);
226    del_locked(hdr, &tail, &head);
227    num--;
228    return 0;
229}
230
231static inline void poison(hdr_t *hdr) {
232    memset(user(hdr), FREE_POISON, hdr->size);
233}
234
235static int was_used_after_free(hdr_t *hdr) {
236    unsigned i;
237    const char *data = (const char *)user(hdr);
238    for (i = 0; i < hdr->size; i++)
239        if (data[i] != FREE_POISON)
240            return 1;
241    return 0;
242}
243
244/* returns 1 if valid, *safe == 1 if safe to dump stack */
245static inline int check_guards(hdr_t *hdr, int *safe) {
246    *safe = 1;
247    if (!is_front_guard_valid(hdr)) {
248        if (hdr->front_guard[0] == FRONT_GUARD) {
249            log_message("+++ ALLOCATION %p SIZE %d HAS A CORRUPTED FRONT GUARD\n",
250                       user(hdr), hdr->size);
251        } else {
252            log_message("+++ ALLOCATION %p HAS A CORRUPTED FRONT GUARD "\
253                      "(NOT DUMPING STACKTRACE)\n", user(hdr));
254            /* Allocation header is probably corrupt, do not print stack trace */
255            *safe = 0;
256        }
257        return 0;
258    }
259
260    if (!is_rear_guard_valid(hdr)) {
261        log_message("+++ ALLOCATION %p SIZE %d HAS A CORRUPTED REAR GUARD\n",
262                   user(hdr), hdr->size);
263        return 0;
264    }
265
266    return 1;
267}
268
269/* returns 1 if valid, *safe == 1 if safe to dump stack */
270static inline int check_allocation_locked(hdr_t *hdr, int *safe) {
271    int valid = 1;
272    *safe = 1;
273
274    if (hdr->tag != ALLOCATION_TAG && hdr->tag != BACKLOG_TAG) {
275        log_message("+++ ALLOCATION %p HAS INVALID TAG %08x (NOT DUMPING STACKTRACE)\n",
276                   user(hdr), hdr->tag);
277        // Allocation header is probably corrupt, do not dequeue or dump stack
278        // trace.
279        *safe = 0;
280        return 0;
281    }
282
283    if (hdr->tag == BACKLOG_TAG && was_used_after_free(hdr)) {
284        log_message("+++ ALLOCATION %p SIZE %d WAS USED AFTER BEING FREED\n",
285                   user(hdr), hdr->size);
286        valid = 0;
287        /* check the guards to see if it's safe to dump a stack trace */
288        check_guards(hdr, safe);
289    } else {
290        valid = check_guards(hdr, safe);
291    }
292
293    if (!valid && *safe) {
294        log_message("+++ ALLOCATION %p SIZE %d ALLOCATED HERE:\n",
295                        user(hdr), hdr->size);
296        print_backtrace(hdr->bt, hdr->bt_depth);
297        if (hdr->tag == BACKLOG_TAG) {
298            log_message("+++ ALLOCATION %p SIZE %d FREED HERE:\n",
299                       user(hdr), hdr->size);
300            print_backtrace(hdr->freed_bt, hdr->freed_bt_depth);
301        }
302    }
303
304    return valid;
305}
306
307static inline int del_and_check_locked(hdr_t *hdr,
308                                       hdr_t **tail, hdr_t **head, unsigned *cnt,
309                                       int *safe) {
310    int valid = check_allocation_locked(hdr, safe);
311    if (safe) {
312        (*cnt)--;
313        del_locked(hdr, tail, head);
314    }
315    return valid;
316}
317
318static inline void del_from_backlog_locked(hdr_t *hdr) {
319    int safe;
320    del_and_check_locked(hdr,
321                         &backlog_tail, &backlog_head, &backlog_num,
322                         &safe);
323    hdr->tag = 0; /* clear the tag */
324}
325
326static inline void del_from_backlog(hdr_t *hdr) {
327    ScopedPthreadMutexLocker locker(&backlog_lock);
328    del_from_backlog_locked(hdr);
329}
330
331static inline int del_leak(hdr_t *hdr, int *safe) {
332    ScopedPthreadMutexLocker locker(&lock);
333    return del_and_check_locked(hdr, &tail, &head, &num, safe);
334}
335
336static inline void add_to_backlog(hdr_t *hdr) {
337    ScopedPthreadMutexLocker locker(&backlog_lock);
338    hdr->tag = BACKLOG_TAG;
339    backlog_num++;
340    add_locked(hdr, &backlog_tail, &backlog_head);
341    poison(hdr);
342    /* If we've exceeded the maximum backlog, clear it up */
343    while (backlog_num > malloc_double_free_backlog) {
344        hdr_t *gone = backlog_tail;
345        del_from_backlog_locked(gone);
346        dlfree(gone);
347    }
348}
349
350extern "C" void* chk_malloc(size_t size) {
351//  log_message("%s: %s\n", __FILE__, __FUNCTION__);
352
353    hdr_t* hdr = static_cast<hdr_t*>(dlmalloc(sizeof(hdr_t) + size + sizeof(ftr_t)));
354    if (hdr) {
355        hdr->bt_depth = get_backtrace(hdr->bt, MAX_BACKTRACE_DEPTH);
356        add(hdr, size);
357        return user(hdr);
358    }
359    return NULL;
360}
361
362extern "C" void* chk_memalign(size_t, size_t bytes) {
363//  log_message("%s: %s\n", __FILE__, __FUNCTION__);
364    // XXX: it's better to use malloc, than being wrong
365    return chk_malloc(bytes);
366}
367
368extern "C" void chk_free(void *ptr) {
369//  log_message("%s: %s\n", __FILE__, __FUNCTION__);
370
371    if (!ptr) /* ignore free(NULL) */
372        return;
373
374    hdr_t* hdr = meta(ptr);
375
376    if (del(hdr) < 0) {
377        intptr_t bt[MAX_BACKTRACE_DEPTH];
378        int depth;
379        depth = get_backtrace(bt, MAX_BACKTRACE_DEPTH);
380        if (hdr->tag == BACKLOG_TAG) {
381            log_message("+++ ALLOCATION %p SIZE %d BYTES MULTIPLY FREED!\n",
382                       user(hdr), hdr->size);
383            log_message("+++ ALLOCATION %p SIZE %d ALLOCATED HERE:\n",
384                       user(hdr), hdr->size);
385            print_backtrace(hdr->bt, hdr->bt_depth);
386            /* hdr->freed_bt_depth should be nonzero here */
387            log_message("+++ ALLOCATION %p SIZE %d FIRST FREED HERE:\n",
388                       user(hdr), hdr->size);
389            print_backtrace(hdr->freed_bt, hdr->freed_bt_depth);
390            log_message("+++ ALLOCATION %p SIZE %d NOW BEING FREED HERE:\n",
391                       user(hdr), hdr->size);
392            print_backtrace(bt, depth);
393        } else {
394            log_message("+++ ALLOCATION %p IS CORRUPTED OR NOT ALLOCATED VIA TRACKER!\n",
395                       user(hdr));
396            print_backtrace(bt, depth);
397            /* Leak here so that we do not crash */
398            //dlfree(user(hdr));
399        }
400    } else {
401        hdr->freed_bt_depth = get_backtrace(hdr->freed_bt,
402                                      MAX_BACKTRACE_DEPTH);
403        add_to_backlog(hdr);
404    }
405}
406
407extern "C" void *chk_realloc(void *ptr, size_t size) {
408//  log_message("%s: %s\n", __FILE__, __FUNCTION__);
409
410    if (!size) {
411        chk_free(ptr);
412        return NULL;
413    }
414
415    if (!ptr) {
416        return chk_malloc(size);
417    }
418
419    hdr_t* hdr = meta(ptr);
420
421    if (del(hdr) < 0) {
422        intptr_t bt[MAX_BACKTRACE_DEPTH];
423        int depth;
424        depth = get_backtrace(bt, MAX_BACKTRACE_DEPTH);
425        if (hdr->tag == BACKLOG_TAG) {
426            log_message("+++ REALLOCATION %p SIZE %d OF FREED MEMORY!\n",
427                       user(hdr), size, hdr->size);
428            log_message("+++ ALLOCATION %p SIZE %d ALLOCATED HERE:\n",
429                       user(hdr), hdr->size);
430            print_backtrace(hdr->bt, hdr->bt_depth);
431            /* hdr->freed_bt_depth should be nonzero here */
432            log_message("+++ ALLOCATION %p SIZE %d FIRST FREED HERE:\n",
433                       user(hdr), hdr->size);
434            print_backtrace(hdr->freed_bt, hdr->freed_bt_depth);
435            log_message("+++ ALLOCATION %p SIZE %d NOW BEING REALLOCATED HERE:\n",
436                       user(hdr), hdr->size);
437            print_backtrace(bt, depth);
438
439             /* We take the memory out of the backlog and fall through so the
440             * reallocation below succeeds.  Since we didn't really free it, we
441             * can default to this behavior.
442             */
443            del_from_backlog(hdr);
444        } else {
445            log_message("+++ REALLOCATION %p SIZE %d IS CORRUPTED OR NOT ALLOCATED VIA TRACKER!\n",
446                       user(hdr), size);
447            print_backtrace(bt, depth);
448            // just get a whole new allocation and leak the old one
449            return dlrealloc(0, size);
450            // return dlrealloc(user(hdr), size); // assuming it was allocated externally
451        }
452    }
453
454    hdr = static_cast<hdr_t*>(dlrealloc(hdr, sizeof(hdr_t) + size + sizeof(ftr_t)));
455    if (hdr) {
456        hdr->bt_depth = get_backtrace(hdr->bt, MAX_BACKTRACE_DEPTH);
457        add(hdr, size);
458        return user(hdr);
459    }
460
461    return NULL;
462}
463
464extern "C" void *chk_calloc(int nmemb, size_t size) {
465//  log_message("%s: %s\n", __FILE__, __FUNCTION__);
466    size_t total_size = nmemb * size;
467    hdr_t* hdr = static_cast<hdr_t*>(dlcalloc(1, sizeof(hdr_t) + total_size + sizeof(ftr_t)));
468    if (hdr) {
469        hdr->bt_depth = get_backtrace(
470                            hdr->bt, MAX_BACKTRACE_DEPTH);
471        add(hdr, total_size);
472        return user(hdr);
473    }
474    return NULL;
475}
476
477static void heaptracker_free_leaked_memory() {
478    if (num) {
479        log_message("+++ THERE ARE %d LEAKED ALLOCATIONS\n", num);
480    }
481
482    hdr_t *del = NULL;
483    while (head) {
484        int safe;
485        del = head;
486        log_message("+++ DELETING %d BYTES OF LEAKED MEMORY AT %p (%d REMAINING)\n",
487                del->size, user(del), num);
488        if (del_leak(del, &safe)) {
489            /* safe == 1, because the allocation is valid */
490            log_message("+++ ALLOCATION %p SIZE %d ALLOCATED HERE:\n",
491                        user(del), del->size);
492            print_backtrace(del->bt, del->bt_depth);
493        }
494        dlfree(del);
495    }
496
497//  log_message("+++ DELETING %d BACKLOGGED ALLOCATIONS\n", backlog_num);
498    while (backlog_head) {
499        del = backlog_tail;
500        del_from_backlog(del);
501        dlfree(del);
502    }
503}
504
505/* Initializes malloc debugging framework.
506 * See comments on MallocDebugInit in malloc_debug_common.h
507 */
508extern "C" int malloc_debug_initialize() {
509    if (!malloc_double_free_backlog)
510        malloc_double_free_backlog = BACKLOG_DEFAULT_LEN;
511    milist = init_mapinfo(getpid());
512    return 0;
513}
514
515extern "C" void malloc_debug_finalize() {
516    heaptracker_free_leaked_memory();
517    deinit_mapinfo(milist);
518}
519