/* *  Tiny C Memory and bounds checker *  *  Copyright (c) 2002 Fabrice Bellard * *  This program is free software; you can redistribute it and/or modify *  it under the terms of the GNU General Public License as published by *  the Free Software Foundation; either version 2 of the License, or *  (at your option) any later version. * *  This program is distributed in the hope that it will be useful, *  but WITHOUT ANY WARRANTY; without even the implied warranty of *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the *  GNU General Public License for more details. * *  You should have received a copy of the GNU General Public License *  along with this program; if not, write to the Free Software *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */#include <stdlib.h>#include <stdio.h>#include <stdarg.h>#include <string.h>#ifndef __FreeBSD__#include <malloc.h>#endif//#define BOUND_DEBUG/* define so that bound array is static (faster, but use memory if   bound checking not used) *///#define BOUND_STATIC/* use malloc hooks. Currently the code cannot be reliable if no hooks */#define CONFIG_TCC_MALLOC_HOOKS#define HAVE_MEMALIGN#ifdef __FreeBSD__#warning Bound checking not fully supported on FreeBSD#undef CONFIG_TCC_MALLOC_HOOKS#undef HAVE_MEMALIGN#endif#define BOUND_T1_BITS 13#define BOUND_T2_BITS 11#define BOUND_T3_BITS (32 - BOUND_T1_BITS - BOUND_T2_BITS)#define BOUND_T1_SIZE (1 << BOUND_T1_BITS)#define BOUND_T2_SIZE (1 << BOUND_T2_BITS)#define BOUND_T3_SIZE (1 << BOUND_T3_BITS)#define BOUND_E_BITS  4#define BOUND_T23_BITS (BOUND_T2_BITS + BOUND_T3_BITS)#define BOUND_T23_SIZE (1 << BOUND_T23_BITS)/* this pointer is generated when bound check is incorrect */#define INVALID_POINTER ((void *)(-2))/* size of an empty region */#define EMPTY_SIZE        0xffffffff/* size of an invalid region */#define INVALID_SIZE      0typedef struct BoundEntry {    unsigned long start;    unsigned long size;    struct BoundEntry *next;    unsigned long is_invalid; /* true if pointers outside region are invalid */} BoundEntry;/* external interface */void __bound_init(void);void __bound_new_region(void *p, unsigned long size);int __bound_delete_region(void *p);/* currently, tcc cannot compile that because we use unsupported GNU C   extensions */#if !defined(__TINYC__)void *__bound_ptr_add(void *p, int offset) __attribute__((regparm(2)));void *__bound_ptr_indir1(void *p, int offset) __attribute__((regparm(2)));void *__bound_ptr_indir2(void *p, int offset) __attribute__((regparm(2)));void *__bound_ptr_indir4(void *p, int offset) __attribute__((regparm(2)));void *__bound_ptr_indir8(void *p, int offset) __attribute__((regparm(2)));void *__bound_ptr_indir12(void *p, int offset) __attribute__((regparm(2)));void *__bound_ptr_indir16(void *p, int offset) __attribute__((regparm(2)));void __bound_local_new(void *p) __attribute__((regparm(1)));void __bound_local_delete(void *p) __attribute__((regparm(1)));#endifvoid *__bound_malloc(size_t size, const void *caller);void *__bound_memalign(size_t size, size_t align, const void *caller);void __bound_free(void *ptr, const void *caller);void *__bound_realloc(void *ptr, size_t size, const void *caller);static void *libc_malloc(size_t size);static void libc_free(void *ptr);static void install_malloc_hooks(void);static void restore_malloc_hooks(void);#ifdef CONFIG_TCC_MALLOC_HOOKSstatic void *saved_malloc_hook;static void *saved_free_hook;static void *saved_realloc_hook;static void *saved_memalign_hook;#endif/* linker definitions */extern char _end;/* TCC definitions */extern char __bounds_start; /* start of static bounds table *//* error message, just for TCC */const char *__bound_error_msg;/* runtime error output */extern void rt_error(unsigned long pc, const char *fmt, ...);#ifdef BOUND_STATICstatic BoundEntry *__bound_t1[BOUND_T1_SIZE]; /* page table */#elsestatic BoundEntry **__bound_t1; /* page table */#endifstatic BoundEntry *__bound_empty_t2;   /* empty page, for unused pages */static BoundEntry *__bound_invalid_t2; /* invalid page, for invalid pointers */static BoundEntry *__bound_find_region(BoundEntry *e1, void *p){    unsigned long addr, tmp;    BoundEntry *e;    e = e1;    while (e != NULL) {        addr = (unsigned long)p;        addr -= e->start;        if (addr <= e->size) {            /* put region at the head */            tmp = e1->start;            e1->start = e->start;            e->start = tmp;            tmp = e1->size;            e1->size = e->size;            e->size = tmp;            return e1;        }        e = e->next;    }    /* no entry found: return empty entry or invalid entry */    if (e1->is_invalid)        return __bound_invalid_t2;    else        return __bound_empty_t2;}/* print a bound error message */static void bound_error(const char *fmt, ...){    __bound_error_msg = fmt;    *(int *)0 = 0; /* force a runtime error */}static void bound_alloc_error(void){    bound_error("not enough memory for bound checking code");}/* currently, tcc cannot compile that because we use GNUC extensions */#if !defined(__TINYC__)/* return '(p + offset)' for pointer arithmetic (a pointer can reach   the end of a region in this case */void *__bound_ptr_add(void *p, int offset){    unsigned long addr = (unsigned long)p;    BoundEntry *e;#if defined(BOUND_DEBUG)    printf("add: 0x%x %d\n", (int)p, offset);#endif    e = __bound_t1[addr >> (BOUND_T2_BITS + BOUND_T3_BITS)];    e = (BoundEntry *)((char *)e +                        ((addr >> (BOUND_T3_BITS - BOUND_E_BITS)) &                         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS)));    addr -= e->start;    if (addr > e->size) {        e = __bound_find_region(e, p);        addr = (unsigned long)p - e->start;    }    addr += offset;    if (addr > e->size)        return INVALID_POINTER; /* return an invalid pointer */    return p + offset;}/* return '(p + offset)' for pointer indirection (the resulting must   be strictly inside the region */#define BOUND_PTR_INDIR(dsize)                                          \void *__bound_ptr_indir ## dsize (void *p, int offset)                  \{                                                                       \    unsigned long addr = (unsigned long)p;                              \    BoundEntry *e;                                                      \                                                                        \    e = __bound_t1[addr >> (BOUND_T2_BITS + BOUND_T3_BITS)];            \    e = (BoundEntry *)((char *)e +                                      \                       ((addr >> (BOUND_T3_BITS - BOUND_E_BITS)) &      \                        ((BOUND_T2_SIZE - 1) << BOUND_E_BITS)));        \    addr -= e->start;                                                   \    if (addr > e->size) {                                               \        e = __bound_find_region(e, p);                                  \        addr = (unsigned long)p - e->start;                             \    }                                                                   \    addr += offset + dsize;                                             \    if (addr > e->size)                                                 \        return INVALID_POINTER; /* return an invalid pointer */         \    return p + offset;                                                  \}#ifdef __i386__/* return the frame pointer of the caller */#define GET_CALLER_FP(fp)\{\    unsigned long *fp1;\    __asm__ __volatile__ ("movl %%ebp,%0" :"=g" (fp1));\    fp = fp1[0];\}#else#error put code to extract the calling frame pointer#endif/* called when entering a function to add all the local regions */void __bound_local_new(void *p1) {    unsigned long addr, size, fp, *p = p1;    GET_CALLER_FP(fp);    for(;;) {        addr = p[0];        if (addr == 0)            break;        addr += fp;        size = p[1];        p += 2;        __bound_new_region((void *)addr, size);    }}/* called when leaving a function to delete all the local regions */void __bound_local_delete(void *p1) {    unsigned long addr, fp, *p = p1;    GET_CALLER_FP(fp);    for(;;) {        addr = p[0];        if (addr == 0)            break;        addr += fp;        p += 2;        __bound_delete_region((void *)addr);    }}#elsevoid __bound_local_new(void *p) {}void __bound_local_delete(void *p) {}void *__bound_ptr_add(void *p, int offset){    return p + offset;}#define BOUND_PTR_INDIR(dsize)                               \void *__bound_ptr_indir ## dsize (void *p, int offset)       \{                                                            \    return p + offset;                                       \}#endifBOUND_PTR_INDIR(1)BOUND_PTR_INDIR(2)BOUND_PTR_INDIR(4)BOUND_PTR_INDIR(8)BOUND_PTR_INDIR(12)BOUND_PTR_INDIR(16)static BoundEntry *__bound_new_page(void){    BoundEntry *page;    int i;    page = libc_malloc(sizeof(BoundEntry) * BOUND_T2_SIZE);    if (!page)        bound_alloc_error();    for(i=0;i<BOUND_T2_SIZE;i++) {        /* put empty entries */        page[i].start = 0;        page[i].size = EMPTY_SIZE;        page[i].next = NULL;        page[i].is_invalid = 0;    }    return page;}/* currently we use malloc(). Should use bound_new_page() */static BoundEntry *bound_new_entry(void){    BoundEntry *e;    e = libc_malloc(sizeof(BoundEntry));    return e;}static void bound_free_entry(BoundEntry *e){    libc_free(e);}static inline BoundEntry *get_page(int index){    BoundEntry *page;    page = __bound_t1[index];    if (page == __bound_empty_t2 || page == __bound_invalid_t2) {        /* create a new page if necessary */        page = __bound_new_page();        __bound_t1[index] = page;    }    return page;}/* mark a region as being invalid (can only be used during init) */static void mark_invalid(unsigned long addr, unsigned long size){    unsigned long start, end;    BoundEntry *page;    int t1_start, t1_end, i, j, t2_start, t2_end;    start = addr;    end = addr + size;    t2_start = (start + BOUND_T3_SIZE - 1) >> BOUND_T3_BITS;    if (end != 0)        t2_end = end >> BOUND_T3_BITS;    else        t2_end = 1 << (BOUND_T1_BITS + BOUND_T2_BITS);#if 0    printf("mark_invalid: start = %x %x\n", t2_start, t2_end);#endif        /* first we handle full pages */    t1_start = (t2_start + BOUND_T2_SIZE - 1) >> BOUND_T2_BITS;    t1_end = t2_end >> BOUND_T2_BITS;    i = t2_start & (BOUND_T2_SIZE - 1);    j = t2_end & (BOUND_T2_SIZE - 1);        if (t1_start == t1_end) {        page = get_page(t2_start >> BOUND_T2_BITS);        for(; i < j; i++) {            page[i].size = INVALID_SIZE;            page[i].is_invalid = 1;        }    } else {        if (i > 0) {            page = get_page(t2_start >> BOUND_T2_BITS);            for(; i < BOUND_T2_SIZE; i++) {                page[i].size = INVALID_SIZE;                page[i].is_invalid = 1;            }        }        for(i = t1_start; i < t1_end; i++) {            __bound_t1[i] = __bound_invalid_t2;        }        if (j != 0) {            page = get_page(t1_end);            for(i = 0; i < j; i++) {                page[i].size = INVALID_SIZE;                page[i].is_invalid = 1;            }        }    }}void __bound_init(void){    int i;    BoundEntry *page;    unsigned long start, size;    int *p;    /* save malloc hooks and install bound check hooks */    install_malloc_hooks();#ifndef BOUND_STATIC    __bound_t1 = libc_malloc(BOUND_T1_SIZE * sizeof(BoundEntry *));    if (!__bound_t1)        bound_alloc_error();#endif    __bound_empty_t2 = __bound_new_page();    for(i=0;i<BOUND_T1_SIZE;i++) {        __bound_t1[i] = __bound_empty_t2;    }    page = __bound_new_page();    for(i=0;i<BOUND_T2_SIZE;i++) {        /* put invalid entries */        page[i].start = 0;        page[i].size = INVALID_SIZE;        page[i].next = NULL;        page[i].is_invalid = 1;    }    __bound_invalid_t2 = page;    /* invalid pointer zone */    start = (unsigned long)INVALID_POINTER & ~(BOUND_T23_SIZE - 1);    size = BOUND_T23_SIZE;    mark_invalid(start, size);#if !defined(__TINYC__) && defined(CONFIG_TCC_MALLOC_HOOKS)    /* malloc zone is also marked invalid. can only use that with       hooks because all libs should use the same malloc. The solution       would be to build a new malloc for tcc. */    start = (unsigned long)&_end;    size = 128 * 0x100000;    mark_invalid(start, size);#endif    /* add all static bound check values */    p = (int *)&__bounds_start;    while (p[0] != 0) {        __bound_new_region((void *)p[0], p[1]);        p += 2;    }}static inline void add_region(BoundEntry *e,                               unsigned long start, unsigned long size){    BoundEntry *e1;