bcheck.c

小而快的c编译器

/*
 *  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      0

typedef 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)));
#endif

void *__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_HOOKS
static 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_STATIC
static BoundEntry *__bound_t1[BOUND_T1_SIZE]; /* page table */
#else
static BoundEntry **__bound_t1; /* page table */
#endif
static 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);
    }
}

#else

void __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;                                       \
}
#endif

BOUND_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;