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