initial commit

Change-Id: I8f7a7eeece0e516efa486b77e9d97805c0e65d3e
Signed-off-by: Iliyan Malchev <malchev@google.com>

1 files changed, 576 insertions, 0 deletions

diff --git a/heaptracker.c b/heaptracker.c
new file mode 100644
index 0000000..6f2dcfe
--- /dev/null
+++ b/heaptracker.c
@@ -0,0 +1,576 @@
+/*
+**
+** Copyright (C) 2008-2011, The Android Open Source Project
+**
+** Licensed under the Apache License, Version 2.0 (the "License");
+** you may not use this file except in compliance with the License.
+** You may obtain a copy of the License at
+**
+**     http://www.apache.org/licenses/LICENSE-2.0
+**
+** Unless required by applicable law or agreed to in writing, software
+** distributed under the License is distributed on an "AS IS" BASIS,
+** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+** See the License for the specific language governing permissions and
+** limitations under the License.
+*/
+
+#include <android/log.h>
+#include <pthread.h>
+#include <time.h>
+#include <stdarg.h>
+
+#include "mapinfo.h"
+
+extern int heaptracker_stacktrace(intptr_t*, size_t);
+extern void *__real_malloc(size_t size);
+extern void *__real_realloc(void *ptr, size_t size);
+extern void *__real_calloc(int nmemb, int size);
+extern void __real_free(void *ptr);
+
+static mapinfo *milist;
+
+#define MAX_BACKTRACE_DEPTH 15
+#define ALLOCATION_TAG      0x1ee7d00d
+#define BACKLOG_TAG         0xbabecafe
+#define FREE_POISON         0xa5
+#define BACKLOG_MAX         50
+#define FRONT_GUARD         0xaa
+#define FRONT_GUARD_LEN     (1<<4)
+#define REAR_GUARD          0xbb
+#define REAR_GUARD_LEN      (1<<4)
+#define SCANNER_SLEEP_S     3
+
+struct hdr {
+    uint32_t tag;
+    struct hdr *prev;
+    struct hdr *next;
+    intptr_t bt[MAX_BACKTRACE_DEPTH];
+    int bt_depth;
+    intptr_t freed_bt[MAX_BACKTRACE_DEPTH];
+    int freed_bt_depth;
+    size_t size;
+    char front_guard[FRONT_GUARD_LEN];
+} __attribute__((packed));
+
+struct ftr {
+    char rear_guard[REAR_GUARD_LEN];
+} __attribute__((packed));
+
+static inline struct ftr * to_ftr(struct hdr *hdr)
+{
+    return (struct ftr *)(((char *)(hdr + 1)) + hdr->size);
+}
+
+static inline void *user(struct hdr *hdr)
+{
+    return hdr + 1;
+}
+
+static inline struct hdr *meta(void *user)
+{
+    return ((struct hdr *)user) - 1;
+}
+
+extern int __android_log_vprint(int prio, const char *tag, const char *fmt, va_list ap);
+static void default_log(const char *fmt, ...)
+{
+    va_list lst;
+    va_start(lst, fmt);
+    __android_log_vprint(ANDROID_LOG_ERROR, "DEBUG", fmt, lst);
+    va_end(lst);
+}
+
+/* Override this for non-printf reporting */
+void (*malloc_log)(const char *fmt, ...) = default_log;
+/* Call this ad dlclose() to get leaked memory */
+void free_leaked_memory(void);
+
+static unsigned num;
+static struct hdr *first;
+static struct hdr *last;
+static pthread_rwlock_t lock = PTHREAD_RWLOCK_INITIALIZER;
+
+static unsigned backlog_num;
+static struct hdr *backlog_first;
+static struct hdr *backlog_last;
+static pthread_rwlock_t backlog_lock = PTHREAD_RWLOCK_INITIALIZER;
+
+static void print_backtrace(const intptr_t *bt, int depth)
+{
+    mapinfo *mi;
+    int cnt, rel_pc;
+    malloc_log("*** *** *** *** *** *** *** *** *** *** *** *** *** *** *** ***\n");
+    for (cnt = 0; cnt < depth && cnt < MAX_BACKTRACE_DEPTH; cnt++) {
+        mi = pc_to_mapinfo(milist, bt[cnt], &rel_pc);
+        malloc_log("\t#%02d  pc %08x  %s\n", cnt,
+                   mi ? rel_pc : bt[cnt],
+                   mi ? mi->name : "(unknown)");
+    }
+}
+
+static inline void init_front_guard(struct hdr *hdr)
+{
+    memset(hdr->front_guard, FRONT_GUARD, FRONT_GUARD_LEN);
+}
+
+static inline int is_front_guard_valid(struct hdr *hdr)
+{
+    unsigned i;
+    for (i = 0; i < FRONT_GUARD_LEN; i++)
+        if (hdr->front_guard[i] != FRONT_GUARD)
+            return 0;
+    return 1;
+}
+
+static inline void init_rear_guard(struct hdr *hdr)
+{
+    struct ftr *ftr = to_ftr(hdr);
+    memset(ftr->rear_guard, REAR_GUARD, REAR_GUARD_LEN);
+}
+
+static inline int is_rear_guard_valid(struct hdr *hdr)
+{
+    unsigned i;
+    int valid = 1;
+    int first_mismatch = -1;
+    struct ftr *ftr = to_ftr(hdr);
+    for (i = 0; i < REAR_GUARD_LEN; i++) {
+        if (ftr->rear_guard[i] != REAR_GUARD) {
+            if (first_mismatch < 0)
+                first_mismatch = i;
+            valid = 0;
+        }
+        else if (first_mismatch >= 0) {
+            malloc_log("+++ REAR GUARD MISMATCH [%d, %d)\n", first_mismatch, i);
+            first_mismatch = -1;
+        }
+    }
+
+    if (first_mismatch >= 0)
+        malloc_log("+++ REAR GUARD MISMATCH [%d, %d)\n", first_mismatch, i);
+    return valid;
+}
+
+static inline void __add(struct hdr *hdr, struct hdr **first, struct hdr **last)
+{
+    hdr->prev = 0;
+    hdr->next = *last;
+    if (*last)
+        (*last)->prev = hdr;
+    else
+        *first = hdr;
+    *last = hdr;
+}
+
+static inline int __del(struct hdr *hdr, struct hdr **first, struct hdr **last)
+{
+    if (hdr->prev)
+        hdr->prev->next = hdr->next;
+    else
+        *last = hdr->next;
+    if (hdr->next)
+        hdr->next->prev = hdr->prev;
+    else
+        *first = hdr->prev;
+    return 0;
+}
+
+static inline void add(struct hdr *hdr, size_t size)
+{
+    pthread_rwlock_wrlock(&lock);
+    hdr->tag = ALLOCATION_TAG;
+    hdr->size = size;
+    init_front_guard(hdr);
+    init_rear_guard(hdr);
+    num++;
+    __add(hdr, &first, &last);
+    pthread_rwlock_unlock(&lock);
+}
+
+static inline int del(struct hdr *hdr)
+{
+    if (hdr->tag != ALLOCATION_TAG)
+        return -1;
+
+    pthread_rwlock_wrlock(&lock);
+    __del(hdr, &first, &last);
+    num--;
+    pthread_rwlock_unlock(&lock);
+    return 0;
+}
+
+static inline void poison(struct hdr *hdr)
+{
+    memset(user(hdr), FREE_POISON, hdr->size);
+}
+
+static int was_used_after_free(struct hdr *hdr)
+{
+    unsigned i;
+    const char *data = (const char *)user(hdr);
+    for (i = 0; i < hdr->size; i++)
+        if (data[i] != FREE_POISON)
+            return 1;
+    return 0;
+}
+
+/* returns 1 if valid, *safe == 1 if safe to dump stack */
+static inline int check_guards(struct hdr *hdr, int *safe)
+{
+    *safe = 1;
+    if (!is_front_guard_valid(hdr)) {
+        if (hdr->front_guard[0] == FRONT_GUARD) {
+            malloc_log("+++ ALLOCATION %p SIZE %d HAS A CORRUPTED FRONT GUARD\n",
+                       user(hdr), hdr->size);
+        } else {
+            malloc_log("+++ ALLOCATION %p HAS A CORRUPTED FRONT GUARD "\
+                      "(NOT DUMPING STACKTRACE)\n", user(hdr));
+            /* Allocation header is probably corrupt, do not print stack trace */
+            *safe = 0;
+        }
+        return 0;
+    }
+
+    if (!is_rear_guard_valid(hdr)) {
+        malloc_log("+++ ALLOCATION %p SIZE %d HAS A CORRUPTED REAR GUARD\n",
+                   user(hdr), hdr->size);
+        return 0;
+    }
+
+    return 1;
+}
+
+/* returns 1 if valid, *safe == 1 if safe to dump stack */
+static inline int __check_allocation(struct hdr *hdr, int *safe)
+{
+    int valid = 1;
+    *safe = 1;
+
+    if (hdr->tag != ALLOCATION_TAG && hdr->tag != BACKLOG_TAG) {
+        malloc_log("+++ ALLOCATION %p HAS INVALID TAG %08x (NOT DUMPING STACKTRACE)\n",
+                   user(hdr), hdr->tag);
+	/* Allocation header is probably corrupt, do not dequeue or dump stack
+         * trace.
+         */
+        *safe = 0;
+        return 0;
+    }
+
+    if (hdr->tag == BACKLOG_TAG && was_used_after_free(hdr)) {
+        malloc_log("+++ ALLOCATION %p SIZE %d WAS USED AFTER BEING FREED\n",
+                   user(hdr), hdr->size);
+        valid = 0;
+	/* check the guards to see if it's safe to dump a stack trace */
+        (void)check_guards(hdr, safe);
+    }
+    else
+        valid = check_guards(hdr, safe);
+
+    if (!valid && *safe) {
+        malloc_log("+++ ALLOCATION %p SIZE %d ALLOCATED HERE:\n",
+                        user(hdr), hdr->size);
+        print_backtrace(hdr->bt, hdr->bt_depth);
+        if (hdr->tag == BACKLOG_TAG) {
+            malloc_log("+++ ALLOCATION %p SIZE %d FREED HERE:\n",
+                       user(hdr), hdr->size);
+            print_backtrace(hdr->freed_bt, hdr->freed_bt_depth);
+        }
+    }
+
+    return valid;
+}
+
+static inline int __del_and_check(struct hdr *hdr,
+                                   struct hdr **first, struct hdr **last, unsigned *cnt,
+                                   int *safe)
+{
+    int valid;
+    valid = __check_allocation(hdr, safe);
+    if (safe) {
+        (*cnt)--;
+        __del(hdr, first, last);
+    }
+    return valid;
+}
+
+static inline void __del_from_backlog(struct hdr *hdr)
+{
+        int safe;
+        (void)__del_and_check(hdr,
+                              &backlog_first, &backlog_last, &backlog_num,
+                              &safe);
+        hdr->tag = 0; /* clear the tag */
+}
+
+static inline void del_from_backlog(struct hdr *hdr)
+{
+    pthread_rwlock_wrlock(&backlog_lock);
+    __del_from_backlog(hdr);
+    pthread_rwlock_unlock(&backlog_lock);
+}
+
+static inline int del_leak(struct hdr *hdr, int *safe)
+{
+    int valid;
+    pthread_rwlock_wrlock(&lock);
+    valid = __del_and_check(hdr,
+                            &first, &last, &num,
+                            safe);
+    pthread_rwlock_unlock(&lock);
+    return valid;
+}
+
+static inline void add_to_backlog(struct hdr *hdr)
+{
+    pthread_rwlock_wrlock(&backlog_lock);
+    hdr->tag = BACKLOG_TAG;
+    backlog_num++;
+    __add(hdr, &backlog_first, &backlog_last);
+    poison(hdr);
+    /* If we've exceeded the maximum backlog, clear it up */
+    while (backlog_num > BACKLOG_MAX) {
+        struct hdr *gone = backlog_first;
+        __del_from_backlog(gone);
+        __real_free(gone);
+    }
+    pthread_rwlock_unlock(&backlog_lock);
+}
+
+void* __wrap_malloc(size_t size)
+{
+//  malloc_tracker_log("%s: %s\n", __FILE__, __FUNCTION__);
+    struct hdr *hdr = __real_malloc(sizeof(struct hdr) + size +
+                                    sizeof(struct ftr));
+    if (hdr) {
+        hdr->bt_depth = heaptracker_stacktrace(
+                            hdr->bt, MAX_BACKTRACE_DEPTH);
+        add(hdr, size);
+        return hdr+1;
+    }
+    return NULL;
+}
+
+void __wrap_free(void *ptr)
+{
+    struct hdr *hdr;
+    if (!ptr) /* ignore free(NULL) */
+        return;
+
+    hdr = meta(ptr);
+
+    if (del(hdr) < 0) {
+        intptr_t bt[MAX_BACKTRACE_DEPTH];
+        int depth;
+        depth = heaptracker_stacktrace(bt, MAX_BACKTRACE_DEPTH);
+        if (hdr->tag == BACKLOG_TAG) {
+            malloc_log("+++ ALLOCATION %p SIZE %d BYTES MULTIPLY FREED!\n",
+                       user(hdr), hdr->size);
+            malloc_log("+++ ALLOCATION %p SIZE %d ALLOCATED HERE:\n",
+                       user(hdr), hdr->size);
+            print_backtrace(hdr->bt, hdr->bt_depth);
+            /* hdr->freed_bt_depth should be nonzero here */
+            malloc_log("+++ ALLOCATION %p SIZE %d FIRST FREED HERE:\n",
+                       user(hdr), hdr->size);
+            print_backtrace(hdr->freed_bt, hdr->freed_bt_depth);
+            malloc_log("+++ ALLOCATION %p SIZE %d NOW BEING FREED HERE:\n",
+                       user(hdr), hdr->size);
+            print_backtrace(bt, depth);
+        }
+        else {
+            malloc_log("+++ ALLOCATION %p IS CORRUPTED OR NOT ALLOCATED VIA TRACKER!\n",
+                       user(hdr));
+            print_backtrace(bt, depth);
+            /* Leak here so that we do not crash */
+            //__real_free(user(hdr));
+        }
+    }
+    else {
+        hdr->freed_bt_depth = heaptracker_stacktrace(hdr->freed_bt,
+                                      MAX_BACKTRACE_DEPTH);
+        add_to_backlog(hdr);
+    }
+}
+
+void *__wrap_realloc(void *ptr, size_t size)
+{
+    struct hdr *hdr;
+
+    if (!size) {
+        __wrap_free(ptr);
+        return NULL;
+    }
+
+    if (!ptr)
+        return __wrap_malloc(size);
+
+    hdr = meta(ptr);
+
+//  malloc_log("%s: %s\n", __FILE__, __FUNCTION__);
+    if (del(hdr) < 0) {
+        intptr_t bt[MAX_BACKTRACE_DEPTH];
+        int depth;
+        depth = heaptracker_stacktrace(bt, MAX_BACKTRACE_DEPTH);
+        if (hdr->tag == BACKLOG_TAG) {
+            malloc_log("+++ REALLOCATION %p SIZE %d OF FREED MEMORY!\n",
+                       user(hdr), size, hdr->size);
+            malloc_log("+++ ALLOCATION %p SIZE %d ALLOCATED HERE:\n",
+                       user(hdr), hdr->size);
+            print_backtrace(hdr->bt, hdr->bt_depth);
+            /* hdr->freed_bt_depth should be nonzero here */
+            malloc_log("+++ ALLOCATION %p SIZE %d FIRST FREED HERE:\n",
+                       user(hdr), hdr->size);
+            print_backtrace(hdr->freed_bt, hdr->freed_bt_depth);
+            malloc_log("+++ ALLOCATION %p SIZE %d NOW BEING REALLOCATED HERE:\n",
+                       user(hdr), hdr->size);
+            print_backtrace(bt, depth);
+
+	    /* We take the memory out of the backlog and fall through so the
+	     * reallocation below succeeds.  Since we didn't really free it, we
+	     * can default to this behavior.
+             */
+            del_from_backlog(hdr);
+        }
+        else {
+            malloc_log("+++ REALLOCATION %p SIZE %d IS CORRUPTED OR NOT ALLOCATED VIA TRACKER!\n",
+                       user(hdr), size);
+            print_backtrace(bt, depth);
+            // just get a whole new allocation and leak the old one
+            return __real_realloc(0, size);
+            // return __real_realloc(user(hdr), size); // assuming it was allocated externally
+        }
+    }
+ 
+    hdr = __real_realloc(hdr, sizeof(struct hdr) + size);
+    if (hdr) {
+        hdr->bt_depth = heaptracker_stacktrace(hdr->bt, MAX_BACKTRACE_DEPTH);
+        add(hdr, size);
+        return user(hdr);
+    }
+
+    return NULL;
+}
+
+void *__wrap_calloc(int nmemb, size_t size)
+{
+//  malloc_tracker_log("%s: %s\n", __FILE__, __FUNCTION__);
+    struct hdr *hdr;
+    size_t __size = nmemb * size;
+    hdr = __real_calloc(1, sizeof(struct hdr) + __size);
+    if (hdr) {
+        hdr->bt_depth = heaptracker_stacktrace(
+                            hdr->bt, MAX_BACKTRACE_DEPTH);
+        add(hdr, __size);
+        return user(hdr);
+    }
+    return NULL;
+}
+
+void heaptracker_free_leaked_memory(void)
+{
+    struct hdr *del; int cnt;
+
+    if (num)
+        malloc_log("+++ THERE ARE %d LEAKED ALLOCATIONS\n", num);
+
+    while (last) {
+        int safe;
+        del = last;
+        malloc_log("+++ DELETING %d BYTES OF LEAKED MEMORY AT %p (%d REMAINING)\n",
+                del->size, user(del), num);
+        if (del_leak(del, &safe)) {
+            /* safe == 1, because the allocation is valid */
+            malloc_log("+++ ALLOCATION %p SIZE %d ALLOCATED HERE:\n",
+                        user(del), del->size);
+            print_backtrace(del->bt, del->bt_depth);
+        }
+        __real_free(del);
+    }
+
+//  malloc_log("+++ DELETING %d BACKLOGGED ALLOCATIONS\n", backlog_num);
+    while (backlog_last) {
+	del = backlog_first;
+        del_from_backlog(del);
+        __real_free(del);
+    }
+}
+
+static int check_list(struct hdr *list, pthread_rwlock_t *rwlock)
+{
+    struct hdr *hdr;
+    int safe, num_checked;
+
+    pthread_rwlock_rdlock(rwlock);
+    num_checked = 0;
+    hdr = list;
+    while (hdr) {
+        (void)__check_allocation(hdr, &safe);
+        hdr = hdr->next;
+        num_checked++;
+    }
+    pthread_rwlock_unlock(rwlock);
+
+    return num_checked;
+}
+
+static pthread_t scanner_thread;
+static pthread_cond_t scanner_cond = PTHREAD_COND_INITIALIZER;
+static int scanner_stop;
+static pthread_mutex_t scanner_lock = PTHREAD_MUTEX_INITIALIZER;
+
+static void* scanner(void *data __attribute__((unused)))
+{
+    struct timespec ts;
+    int num_checked, num_checked_backlog;
+
+    while (1) {
+        num_checked = check_list(last, &lock);
+        num_checked_backlog = check_list(backlog_last, &backlog_lock);
+
+//      malloc_log("@@@ scanned %d/%d allocs and %d/%d freed\n",
+//                 num_checked, num,
+//                 num_checked_backlog, backlog_num);
+
+        pthread_mutex_lock(&scanner_lock);
+        if (!scanner_stop) {
+            clock_gettime(CLOCK_REALTIME, &ts);
+            ts.tv_sec += SCANNER_SLEEP_S;
+            pthread_cond_timedwait(&scanner_cond, &scanner_lock, &ts);
+        }
+        if (scanner_stop) {
+            pthread_mutex_unlock(&scanner_lock);
+            break;
+        }
+        pthread_mutex_unlock(&scanner_lock);
+    }
+
+//  malloc_log("@@@ scanner thread exiting");
+    return NULL;
+}
+
+static void init(void) __attribute__((constructor));
+static void init(void)
+{
+//  malloc_log("@@@ start scanner thread");
+    milist = init_mapinfo(getpid());
+    pthread_create(&scanner_thread,
+                   NULL,
+                   scanner,
+                   NULL);
+}
+
+static void deinit(void) __attribute__((destructor));
+static void deinit(void)
+{
+//  malloc_log("@@@ signal stop to scanner thread");
+    pthread_mutex_lock(&scanner_lock);
+    scanner_stop = 1;
+    pthread_cond_signal(&scanner_cond);
+    pthread_mutex_unlock(&scanner_lock);
+//  malloc_log("@@@ wait for scanner thread to exit");
+    pthread_join(scanner_thread, NULL);
+//  malloc_log("@@@ scanner thread stopped");
+
+    heaptracker_free_leaked_memory();
+    deinit_mapinfo(milist);
+}