lib/bcheck.c

   1 /*
   2  *  Tiny C Memory and bounds checker
   3  *
   4  *  Copyright (c) 2002 Fabrice Bellard
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  */
  20 #include <stdlib.h>
  21 #include <stdio.h>
  22 #include <stdarg.h>
  23 #include <string.h>
  24 #if !defined(__FreeBSD__) && !defined(__FreeBSD_kernel__) \
  25     && !defined(__DragonFly__) && !defined(__OpenBSD__) && !defined(__NetBSD__)
  26 #include <malloc.h>
  27 #endif
  28 #if !defined(_WIN32)
  29 #include <unistd.h>
  30 #endif
  31
  32 /* #define BOUND_DEBUG */
  33
  34 /* define so that bound array is static (faster, but use memory if
  35    bound checking not used) */
  36 /* #define BOUND_STATIC */
  37
  38 /* use malloc hooks. Currently the code cannot be reliable if no hooks */
  39 #define CONFIG_TCC_MALLOC_HOOKS
  40 #define HAVE_MEMALIGN
  41
  42 #if defined(__FreeBSD__) || defined(__FreeBSD_kernel__) \
  43     || defined(__DragonFly__) || defined(__dietlibc__) \
  44     || defined(__UCLIBC__) || defined(__OpenBSD__) || defined(__NetBSD__) \
  45     || defined(_WIN32) || defined(TCC_UCLIBC)
  46 #warning Bound checking does not support malloc (etc.) in this environment.
  47 #undef CONFIG_TCC_MALLOC_HOOKS
  48 #undef HAVE_MEMALIGN
  49 #endif
  50
  51 #define BOUND_T1_BITS 13
  52 #define BOUND_T2_BITS 11
  53 #define BOUND_T3_BITS (32 - BOUND_T1_BITS - BOUND_T2_BITS)
  54
  55 #define BOUND_T1_SIZE (1 << BOUND_T1_BITS)
  56 #define BOUND_T2_SIZE (1 << BOUND_T2_BITS)
  57 #define BOUND_T3_SIZE (1 << BOUND_T3_BITS)
  58 #define BOUND_E_BITS  4
  59
  60 #define BOUND_T23_BITS (BOUND_T2_BITS + BOUND_T3_BITS)
  61 #define BOUND_T23_SIZE (1 << BOUND_T23_BITS)
  62
  63
  64 /* this pointer is generated when bound check is incorrect */
  65 #define INVALID_POINTER ((void *)(-2))
  66 /* size of an empty region */
  67 #define EMPTY_SIZE        0xffffffff
  68 /* size of an invalid region */
  69 #define INVALID_SIZE      0
  70
  71 typedef struct BoundEntry {
  72     size_t start;
  73     size_t size;
  74     struct BoundEntry *next;
  75     size_t is_invalid; /* true if pointers outside region are invalid */
  76 } BoundEntry;
  77
  78 /* external interface */
  79 void __bound_init(void);
  80 void __bound_new_region(void *p, size_t size);
  81 int __bound_delete_region(void *p);
  82
  83 #ifdef __attribute__
  84   /* an __attribute__ macro is defined in the system headers */
  85   #undef __attribute__
  86 #endif
  87 #define FASTCALL __attribute__((regparm(3)))
  88
  89 void *__bound_malloc(size_t size, const void *caller);
  90 void *__bound_memalign(size_t size, size_t align, const void *caller);
  91 void __bound_free(void *ptr, const void *caller);
  92 void *__bound_realloc(void *ptr, size_t size, const void *caller);
  93 static void *libc_malloc(size_t size);
  94 static void libc_free(void *ptr);
  95 static void install_malloc_hooks(void);
  96 static void restore_malloc_hooks(void);
  97
  98 #ifdef CONFIG_TCC_MALLOC_HOOKS
  99 static void *saved_malloc_hook;
 100 static void *saved_free_hook;
 101 static void *saved_realloc_hook;
 102 static void *saved_memalign_hook;
 103 #endif
 104
 105 /* TCC definitions */
 106 extern char __bounds_start; /* start of static bounds table */
 107 /* error message, just for TCC */
 108 const char *__bound_error_msg;
 109
 110 /* runtime error output */
 111 extern void rt_error(size_t pc, const char *fmt, ...);
 112
 113 #ifdef BOUND_STATIC
 114 static BoundEntry *__bound_t1[BOUND_T1_SIZE]; /* page table */
 115 #else
 116 static BoundEntry **__bound_t1; /* page table */
 117 #endif
 118 static BoundEntry *__bound_empty_t2;   /* empty page, for unused pages */
 119 static BoundEntry *__bound_invalid_t2; /* invalid page, for invalid pointers */
 120
 121 static BoundEntry *__bound_find_region(BoundEntry *e1, void *p)
 122 {
 123     size_t addr, tmp;
 124     BoundEntry *e;
 125
 126     e = e1;
 127     while (e != NULL) {
 128         addr = (size_t)p;
 129         addr -= e->start;
 130         if (addr <= e->size) {
 131             /* put region at the head */
 132             tmp = e1->start;
 133             e1->start = e->start;
 134             e->start = tmp;
 135             tmp = e1->size;
 136             e1->size = e->size;
 137             e->size = tmp;
 138             return e1;
 139         }
 140         e = e->next;
 141     }
 142     /* no entry found: return empty entry or invalid entry */
 143     if (e1->is_invalid)
 144         return __bound_invalid_t2;
 145     else
 146         return __bound_empty_t2;
 147 }
 148
 149 /* print a bound error message */
 150 static void bound_error(const char *fmt, ...)
 151 {
 152     __bound_error_msg = fmt;
 153     fprintf(stderr,"%s %s: %s\n", __FILE__, __FUNCTION__, fmt);
 154     *(int *)0 = 0; /* force a runtime error */
 155 }
 156
 157 static void bound_alloc_error(void)
 158 {
 159     bound_error("not enough memory for bound checking code");
 160 }
 161
 162 /* return '(p + offset)' for pointer arithmetic (a pointer can reach
 163    the end of a region in this case */
 164 void * FASTCALL __bound_ptr_add(void *p, size_t offset)
 165 {
 166     size_t addr = (size_t)p;
 167     BoundEntry *e;
 168
 169     __bound_init();
 170
 171 #if defined(BOUND_DEBUG)
 172     printf("%s %s: 0x%x %d\n", __FILE__, __FUNCTION__, (int)p, offset);
 173 #endif
 174
 175     e = __bound_t1[addr >> (BOUND_T2_BITS + BOUND_T3_BITS)];
 176     e = (BoundEntry *)((char *)e +
 177                        ((addr >> (BOUND_T3_BITS - BOUND_E_BITS)) &
 178                         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS)));
 179     addr -= e->start;
 180     if (addr > e->size) {
 181         e = __bound_find_region(e, p);
 182         addr = (size_t)p - e->start;
 183     }
 184     addr += offset;
 185     if (addr >= e->size) {
 186         fprintf(stderr,"%s %s: %p is outside of the region\n", __FILE__, __FUNCTION__, p + offset);
 187         return INVALID_POINTER; /* return an invalid pointer */
 188     }
 189     return p + offset;
 190 }
 191
 192 /* return '(p + offset)' for pointer indirection (the resulting must
 193    be strictly inside the region */
 194 #define BOUND_PTR_INDIR(dsize)                                          \
 195 void * FASTCALL __bound_ptr_indir ## dsize (void *p, size_t offset)     \
 196 {                                                                       \
 197     size_t addr = (size_t)p;                                            \
 198     BoundEntry *e;                                                      \
 199                                                                         \
 200     __bound_init();                                                     \
 201     e = __bound_t1[addr >> (BOUND_T2_BITS + BOUND_T3_BITS)];            \
 202     e = (BoundEntry *)((char *)e +                                      \
 203                        ((addr >> (BOUND_T3_BITS - BOUND_E_BITS)) &      \
 204                         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS)));        \
 205     addr -= e->start;                                                   \
 206     if (addr > e->size) {                                               \
 207         e = __bound_find_region(e, p);                                  \
 208         addr = (size_t)p - e->start;                                    \
 209     }                                                                   \
 210     addr += offset + dsize;                                             \
 211     if (addr > e->size) {                                               \
 212         fprintf(stderr,"%s %s: %p is outside of the region\n", __FILE__, __FUNCTION__, p + offset); \
 213         return INVALID_POINTER; /* return an invalid pointer */         \
 214     }                                                                   \
 215     return p + offset;                                                  \
 216 }
 217
 218 BOUND_PTR_INDIR(1)
 219 BOUND_PTR_INDIR(2)
 220 BOUND_PTR_INDIR(4)
 221 BOUND_PTR_INDIR(8)
 222 BOUND_PTR_INDIR(12)
 223 BOUND_PTR_INDIR(16)
 224
 225 /* return the frame pointer of the caller */
 226 #define GET_CALLER_FP(fp)\
 227 {\
 228     fp = (size_t)__builtin_frame_address(1);\
 229 }
 230
 231 /* called when entering a function to add all the local regions */
 232 void FASTCALL __bound_local_new(void *p1)
 233 {
 234     size_t addr, size, fp, *p = p1;
 235 #ifdef BOUND_DEBUG
 236     fprintf(stderr, "%s, %s start p1=%p *p1=%p\n", __FILE__, __FUNCTION__, p, *p);
 237 #endif
 238     GET_CALLER_FP(fp);
 239     for(;;) {
 240         addr = p[0];
 241         if (addr == 0)
 242             break;
 243         addr += fp;
 244         size = p[1];
 245         p += 2;
 246         __bound_new_region((void *)addr, size);
 247     }
 248 #ifdef BOUND_DEBUG
 249     fprintf(stderr, "%s, %s end\n", __FILE__, __FUNCTION__);
 250 #endif
 251 }
 252
 253 /* called when leaving a function to delete all the local regions */
 254 void FASTCALL __bound_local_delete(void *p1)
 255 {
 256     size_t addr, fp, *p = p1;
 257     GET_CALLER_FP(fp);
 258     for(;;) {
 259         addr = p[0];
 260         if (addr == 0)
 261             break;
 262         addr += fp;
 263         p += 2;
 264         __bound_delete_region((void *)addr);
 265     }
 266 }
 267
 268 static BoundEntry *__bound_new_page(void)
 269 {
 270     BoundEntry *page;
 271     int i;
 272
 273     page = libc_malloc(sizeof(BoundEntry) * BOUND_T2_SIZE);
 274     if (!page)
 275         bound_alloc_error();
 276     for(i=0;i<BOUND_T2_SIZE;i++) {
 277         /* put empty entries */
 278         page[i].start = 0;
 279         page[i].size = EMPTY_SIZE;
 280         page[i].next = NULL;
 281         page[i].is_invalid = 0;
 282     }
 283     return page;
 284 }
 285
 286 /* currently we use malloc(). Should use bound_new_page() */
 287 static BoundEntry *bound_new_entry(void)
 288 {
 289     BoundEntry *e;
 290     e = libc_malloc(sizeof(BoundEntry));
 291     return e;
 292 }
 293
 294 static void bound_free_entry(BoundEntry *e)
 295 {
 296     libc_free(e);
 297 }
 298
 299 static inline BoundEntry *get_page(int index)
 300 {
 301     BoundEntry *page;
 302     page = __bound_t1[index];
 303     if (page == __bound_empty_t2 || page == __bound_invalid_t2) {
 304         /* create a new page if necessary */
 305         page = __bound_new_page();
 306         __bound_t1[index] = page;
 307     }
 308     return page;
 309 }
 310
 311 /* mark a region as being invalid (can only be used during init) */
 312 static void mark_invalid(size_t addr, size_t size)
 313 {
 314     size_t start, end;
 315     BoundEntry *page;
 316     size_t t1_start, t1_end, i, j, t2_start, t2_end;
 317
 318     start = addr;
 319     end = addr + size;
 320
 321     t2_start = (start + BOUND_T3_SIZE - 1) >> BOUND_T3_BITS;
 322     if (end != 0)
 323         t2_end = end >> BOUND_T3_BITS;
 324     else
 325         t2_end = 1 << (BOUND_T1_BITS + BOUND_T2_BITS);
 326
 327 #if 0
 328     printf("mark_invalid: start = %x %x\n", t2_start, t2_end);
 329 #endif
 330
 331     /* first we handle full pages */
 332     t1_start = (t2_start + BOUND_T2_SIZE - 1) >> BOUND_T2_BITS;
 333     t1_end = t2_end >> BOUND_T2_BITS;
 334
 335     i = t2_start & (BOUND_T2_SIZE - 1);
 336     j = t2_end & (BOUND_T2_SIZE - 1);
 337
 338     if (t1_start == t1_end) {
 339         page = get_page(t2_start >> BOUND_T2_BITS);
 340         for(; i < j; i++) {
 341             page[i].size = INVALID_SIZE;
 342             page[i].is_invalid = 1;
 343         }
 344     } else {
 345         if (i > 0) {
 346             page = get_page(t2_start >> BOUND_T2_BITS);
 347             for(; i < BOUND_T2_SIZE; i++) {
 348                 page[i].size = INVALID_SIZE;
 349                 page[i].is_invalid = 1;
 350             }
 351         }
 352         for(i = t1_start; i < t1_end; i++) {
 353             __bound_t1[i] = __bound_invalid_t2;
 354         }
 355         if (j != 0) {
 356             page = get_page(t1_end);
 357             for(i = 0; i < j; i++) {
 358                 page[i].size = INVALID_SIZE;
 359                 page[i].is_invalid = 1;
 360             }
 361         }
 362     }
 363 }
 364
 365 void __bound_init(void)
 366 {
 367     int i;
 368     BoundEntry *page;
 369     size_t start, size;
 370     size_t *p;
 371
 372     static int inited;
 373     if (inited)
 374         return;
 375
 376     inited = 1;
 377
 378 #ifdef BOUND_DEBUG
 379     fprintf(stderr, "%s, %s() start\n", __FILE__, __FUNCTION__);
 380 #endif
 381
 382     /* save malloc hooks and install bound check hooks */
 383     install_malloc_hooks();
 384
 385 #ifndef BOUND_STATIC
 386     __bound_t1 = libc_malloc(BOUND_T1_SIZE * sizeof(BoundEntry *));
 387     if (!__bound_t1)
 388         bound_alloc_error();
 389 #endif
 390     __bound_empty_t2 = __bound_new_page();
 391     for(i=0;i<BOUND_T1_SIZE;i++) {
 392         __bound_t1[i] = __bound_empty_t2;
 393     }
 394
 395     page = __bound_new_page();
 396     for(i=0;i<BOUND_T2_SIZE;i++) {
 397         /* put invalid entries */
 398         page[i].start = 0;
 399         page[i].size = INVALID_SIZE;
 400         page[i].next = NULL;
 401         page[i].is_invalid = 1;
 402     }
 403     __bound_invalid_t2 = page;
 404
 405     /* invalid pointer zone */
 406     start = (size_t)INVALID_POINTER & ~(BOUND_T23_SIZE - 1);
 407     size = BOUND_T23_SIZE;
 408     mark_invalid(start, size);
 409
 410 #if defined(CONFIG_TCC_MALLOC_HOOKS)
 411     /* malloc zone is also marked invalid. can only use that with
 412      * hooks because all libs should use the same malloc. The solution
 413      * would be to build a new malloc for tcc.
 414      *
 415      * usually heap (= malloc zone) comes right after bss, i.e. after _end, but
 416      * not always - either if we are running from under `tcc -b -run`, or if
 417      * address space randomization is turned on(a), heap start will be separated
 418      * from bss end.
 419      *
 420      * So sbrk(0) will be a good approximation for start_brk:
 421      *
 422      *   - if we are a separately compiled program, __bound_init() runs early,
 423      *     and sbrk(0) should be equal or very near to start_brk(b) (in case other
 424      *     constructors malloc something), or
 425      *
 426      *   - if we are running from under `tcc -b -run`, sbrk(0) will return
 427      *     start of heap portion which is under this program control, and not
 428      *     mark as invalid earlier allocated memory.
 429      *
 430      *
 431      * (a) /proc/sys/kernel/randomize_va_space = 2, on Linux;
 432      *     usually turned on by default.
 433      *
 434      * (b) on Linux >= v3.3, the alternative is to read
 435      *     start_brk from /proc/self/stat
 436      */
 437     start = (size_t)sbrk(0);
 438     size = 128 * 0x100000;
 439     mark_invalid(start, size);
 440 #endif
 441
 442     /* add all static bound check values */
 443     p = (size_t *)&__bounds_start;
 444     while (p[0] != 0) {
 445         __bound_new_region((void *)p[0], p[1]);
 446         p += 2;
 447     }
 448 #ifdef BOUND_DEBUG
 449     fprintf(stderr, "%s, %s() end\n\n", __FILE__, __FUNCTION__);
 450 #endif
 451 }
 452
 453 void __bound_main_arg(void **p)
 454 {
 455     void *start = p;
 456     while (*p++);
 457 #ifdef BOUND_DEBUG
 458         fprintf(stderr, "%s, %s calling __bound_new_region(%p, %p)\n",
 459            __FILE__, __FUNCTION__, (void *) p - start);
 460 #endif
 461     __bound_new_region(start, (void *) p - start);
 462 }
 463
 464 void __bound_exit(void)
 465 {
 466     restore_malloc_hooks();
 467 }
 468
 469 static inline void add_region(BoundEntry *e,
 470                               size_t start, size_t size)
 471 {
 472     BoundEntry *e1;
 473     if (e->start == 0) {
 474         /* no region : add it */
 475         e->start = start;
 476         e->size = size;
 477     } else {
 478         /* already regions in the list: add it at the head */
 479         e1 = bound_new_entry();
 480         e1->start = e->start;
 481         e1->size = e->size;
 482         e1->next = e->next;
 483         e->start = start;
 484         e->size = size;
 485         e->next = e1;
 486     }
 487 }
 488
 489 /* create a new region. It should not already exist in the region list */
 490 void __bound_new_region(void *p, size_t size)
 491 {
 492     size_t start, end;
 493     BoundEntry *page, *e, *e2;
 494     size_t t1_start, t1_end, i, t2_start, t2_end;
 495
 496     __bound_init();
 497
 498 #ifdef BOUND_DEBUG
 499     fprintf(stderr, "%s, %s(%p, %p) start\n",
 500            __FILE__, __FUNCTION__, p, size);
 501 #endif
 502
 503     start = (size_t)p;
 504     end = start + size;
 505     t1_start = start >> (BOUND_T2_BITS + BOUND_T3_BITS);
 506     t1_end = end >> (BOUND_T2_BITS + BOUND_T3_BITS);
 507
 508     /* start */
 509     page = get_page(t1_start);
 510     t2_start = (start >> (BOUND_T3_BITS - BOUND_E_BITS)) &
 511         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS);
 512     t2_end = (end >> (BOUND_T3_BITS - BOUND_E_BITS)) &
 513         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS);
 514
 515
 516     e = (BoundEntry *)((char *)page + t2_start);
 517     add_region(e, start, size);
 518
 519     if (t1_end == t1_start) {
 520         /* same ending page */
 521         e2 = (BoundEntry *)((char *)page + t2_end);
 522         if (e2 > e) {
 523             e++;
 524             for(;e<e2;e++) {
 525                 e->start = start;
 526                 e->size = size;
 527             }
 528             add_region(e, start, size);
 529         }
 530     } else {
 531         /* mark until end of page */
 532         e2 = page + BOUND_T2_SIZE;
 533         e++;
 534         for(;e<e2;e++) {
 535             e->start = start;
 536             e->size = size;
 537         }
 538         /* mark intermediate pages, if any */
 539         for(i=t1_start+1;i<t1_end;i++) {
 540             page = get_page(i);
 541             e2 = page + BOUND_T2_SIZE;
 542             for(e=page;e<e2;e++) {
 543                 e->start = start;
 544                 e->size = size;
 545             }
 546         }
 547         /* last page */
 548         page = get_page(t1_end);
 549         e2 = (BoundEntry *)((char *)page + t2_end);
 550         for(e=page;e<e2;e++) {
 551             e->start = start;
 552             e->size = size;
 553         }
 554         add_region(e, start, size);
 555     }
 556 #ifdef BOUND_DEBUG
 557     fprintf(stderr, "%s, %s end\n", __FILE__, __FUNCTION__);
 558 #endif
 559 }
 560
 561 /* delete a region */
 562 static inline void delete_region(BoundEntry *e,
 563                                  void *p, size_t empty_size)
 564 {
 565     size_t addr;
 566     BoundEntry *e1;
 567
 568     addr = (size_t)p;
 569     addr -= e->start;
 570     if (addr <= e->size) {
 571         /* region found is first one */
 572         e1 = e->next;
 573         if (e1 == NULL) {
 574             /* no more region: mark it empty */
 575             e->start = 0;
 576             e->size = empty_size;
 577         } else {
 578             /* copy next region in head */
 579             e->start = e1->start;
 580             e->size = e1->size;
 581             e->next = e1->next;
 582             bound_free_entry(e1);
 583         }
 584     } else {
 585         /* find the matching region */
 586         for(;;) {
 587             e1 = e;
 588             e = e->next;
 589             /* region not found: do nothing */
 590             if (e == NULL)
 591                 break;
 592             addr = (size_t)p - e->start;
 593             if (addr <= e->size) {
 594                 /* found: remove entry */
 595                 e1->next = e->next;
 596                 bound_free_entry(e);
 597                 break;
 598             }
 599         }
 600     }
 601 }
 602
 603 /* WARNING: 'p' must be the starting point of the region. */
 604 /* return non zero if error */
 605 int __bound_delete_region(void *p)
 606 {
 607     size_t start, end, addr, size, empty_size;
 608     BoundEntry *page, *e, *e2;
 609     size_t t1_start, t1_end, t2_start, t2_end, i;
 610
 611     __bound_init();
 612
 613 #ifdef BOUND_DEBUG
 614     fprintf(stderr, "%s %s() start\n", __FILE__, __FUNCTION__);
 615 #endif
 616
 617     start = (size_t)p;
 618     t1_start = start >> (BOUND_T2_BITS + BOUND_T3_BITS);
 619     t2_start = (start >> (BOUND_T3_BITS - BOUND_E_BITS)) &
 620         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS);
 621
 622     /* find region size */
 623     page = __bound_t1[t1_start];
 624     e = (BoundEntry *)((char *)page + t2_start);
 625     addr = start - e->start;
 626     if (addr > e->size)
 627         e = __bound_find_region(e, p);
 628     /* test if invalid region */
 629     if (e->size == EMPTY_SIZE || (size_t)p != e->start)
 630         return -1;
 631     /* compute the size we put in invalid regions */
 632     if (e->is_invalid)
 633         empty_size = INVALID_SIZE;
 634     else
 635         empty_size = EMPTY_SIZE;
 636     size = e->size;
 637     end = start + size;
 638
 639     /* now we can free each entry */
 640     t1_end = end >> (BOUND_T2_BITS + BOUND_T3_BITS);
 641     t2_end = (end >> (BOUND_T3_BITS - BOUND_E_BITS)) &
 642         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS);
 643
 644     delete_region(e, p, empty_size);
 645     if (t1_end == t1_start) {
 646         /* same ending page */
 647         e2 = (BoundEntry *)((char *)page + t2_end);
 648         if (e2 > e) {
 649             e++;
 650             for(;e<e2;e++) {
 651                 e->start = 0;
 652                 e->size = empty_size;
 653             }
 654             delete_region(e, p, empty_size);
 655         }
 656     } else {
 657         /* mark until end of page */
 658         e2 = page + BOUND_T2_SIZE;
 659         e++;
 660         for(;e<e2;e++) {
 661             e->start = 0;
 662             e->size = empty_size;
 663         }
 664         /* mark intermediate pages, if any */
 665         /* XXX: should free them */
 666         for(i=t1_start+1;i<t1_end;i++) {
 667             page = get_page(i);
 668             e2 = page + BOUND_T2_SIZE;
 669             for(e=page;e<e2;e++) {
 670                 e->start = 0;
 671                 e->size = empty_size;
 672             }
 673         }
 674         /* last page */
 675         page = get_page(t1_end);
 676         e2 = (BoundEntry *)((char *)page + t2_end);
 677         for(e=page;e<e2;e++) {
 678             e->start = 0;
 679             e->size = empty_size;
 680         }
 681         delete_region(e, p, empty_size);
 682     }
 683
 684 #ifdef BOUND_DEBUG
 685     fprintf(stderr, "%s %s() end\n", __FILE__, __FUNCTION__);
 686 #endif
 687
 688     return 0;
 689 }
 690
 691 /* return the size of the region starting at p, or EMPTY_SIZE if non
 692    existent region. */
 693 static size_t get_region_size(void *p)
 694 {
 695     size_t addr = (size_t)p;
 696     BoundEntry *e;
 697
 698     e = __bound_t1[addr >> (BOUND_T2_BITS + BOUND_T3_BITS)];
 699     e = (BoundEntry *)((char *)e +
 700                        ((addr >> (BOUND_T3_BITS - BOUND_E_BITS)) &
 701                         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS)));
 702     addr -= e->start;
 703     if (addr > e->size)
 704         e = __bound_find_region(e, p);
 705     if (e->start != (size_t)p)
 706         return EMPTY_SIZE;
 707     return e->size;
 708 }
 709
 710 /* patched memory functions */
 711
 712 /* force compiler to perform stores coded up to this point */
 713 #define barrier()   __asm__ __volatile__ ("": : : "memory")
 714
 715 static void install_malloc_hooks(void)
 716 {
 717 #ifdef CONFIG_TCC_MALLOC_HOOKS
 718     saved_malloc_hook = __malloc_hook;
 719     saved_free_hook = __free_hook;
 720     saved_realloc_hook = __realloc_hook;
 721     saved_memalign_hook = __memalign_hook;
 722     __malloc_hook = __bound_malloc;
 723     __free_hook = __bound_free;
 724     __realloc_hook = __bound_realloc;
 725     __memalign_hook = __bound_memalign;
 726
 727     barrier();
 728 #endif
 729 }
 730
 731 static void restore_malloc_hooks(void)
 732 {
 733 #ifdef CONFIG_TCC_MALLOC_HOOKS
 734     __malloc_hook = saved_malloc_hook;
 735     __free_hook = saved_free_hook;
 736     __realloc_hook = saved_realloc_hook;
 737     __memalign_hook = saved_memalign_hook;
 738
 739     barrier();
 740 #endif
 741 }
 742
 743 static void *libc_malloc(size_t size)
 744 {
 745     void *ptr;
 746     restore_malloc_hooks();
 747     ptr = malloc(size);
 748     install_malloc_hooks();
 749     return ptr;
 750 }
 751
 752 static void libc_free(void *ptr)
 753 {
 754     restore_malloc_hooks();
 755     free(ptr);
 756     install_malloc_hooks();
 757 }
 758
 759 /* XXX: we should use a malloc which ensure that it is unlikely that
 760    two malloc'ed data have the same address if 'free' are made in
 761    between. */
 762 void *__bound_malloc(size_t size, const void *caller)
 763 {
 764     void *ptr;
 765
 766     /* we allocate one more byte to ensure the regions will be
 767        separated by at least one byte. With the glibc malloc, it may
 768        be in fact not necessary */
 769     ptr = libc_malloc(size + 1);
 770
 771     if (!ptr)
 772         return NULL;
 773
 774 #ifdef BOUND_DEBUG
 775     fprintf(stderr, "%s, %s calling __bound_new_region(%p, %p)\n",
 776            __FILE__, __FUNCTION__, ptr, size);
 777 #endif
 778     __bound_new_region(ptr, size);
 779     return ptr;
 780 }
 781
 782 void *__bound_memalign(size_t size, size_t align, const void *caller)
 783 {
 784     void *ptr;
 785
 786     restore_malloc_hooks();
 787
 788 #ifndef HAVE_MEMALIGN
 789     if (align > 4) {
 790         /* XXX: handle it ? */
 791         ptr = NULL;
 792     } else {
 793         /* we suppose that malloc aligns to at least four bytes */
 794         ptr = malloc(size + 1);
 795     }
 796 #else
 797     /* we allocate one more byte to ensure the regions will be
 798        separated by at least one byte. With the glibc malloc, it may
 799        be in fact not necessary */
 800     ptr = memalign(size + 1, align);
 801 #endif
 802
 803     install_malloc_hooks();
 804
 805     if (!ptr)
 806         return NULL;
 807
 808 #ifdef BOUND_DEBUG
 809     fprintf(stderr, "%s, %s calling __bound_new_region(%p, %p)\n",
 810            __FILE__, __FUNCTION__, ptr, size);
 811 #endif
 812     __bound_new_region(ptr, size);
 813     return ptr;
 814 }
 815
 816 void __bound_free(void *ptr, const void *caller)
 817 {
 818     if (ptr == NULL)
 819         return;
 820     if (__bound_delete_region(ptr) != 0)
 821         bound_error("freeing invalid region");
 822
 823     libc_free(ptr);
 824 }
 825
 826 void *__bound_realloc(void *ptr, size_t size, const void *caller)
 827 {
 828     void *ptr1;
 829     size_t old_size;
 830
 831     if (size == 0) {
 832         __bound_free(ptr, caller);
 833         return NULL;
 834     } else {
 835         ptr1 = __bound_malloc(size, caller);
 836         if (ptr == NULL || ptr1 == NULL)
 837             return ptr1;
 838         old_size = get_region_size(ptr);
 839         if (old_size == EMPTY_SIZE)
 840             bound_error("realloc'ing invalid pointer");
 841         memcpy(ptr1, ptr, old_size);
 842         __bound_free(ptr, caller);
 843         return ptr1;
 844     }
 845 }
 846
 847 #ifndef CONFIG_TCC_MALLOC_HOOKS
 848 void *__bound_calloc(size_t nmemb, size_t size)
 849 {
 850     void *ptr;
 851     size = size * nmemb;
 852     ptr = __bound_malloc(size, NULL);
 853     if (!ptr)
 854         return NULL;
 855     memset(ptr, 0, size);
 856     return ptr;
 857 }
 858 #endif
 859
 860 #if 0
 861 static void bound_dump(void)
 862 {
 863     BoundEntry *page, *e;
 864     int i, j;
 865
 866     printf("region dump:\n");
 867     for(i=0;i<BOUND_T1_SIZE;i++) {
 868         page = __bound_t1[i];
 869         for(j=0;j<BOUND_T2_SIZE;j++) {
 870             e = page + j;
 871             /* do not print invalid or empty entries */
 872             if (e->size != EMPTY_SIZE && e->start != 0) {
 873                 printf("%08x:",
 874                        (i << (BOUND_T2_BITS + BOUND_T3_BITS)) +
 875                        (j << BOUND_T3_BITS));
 876                 do {
 877                     printf(" %08lx:%08lx", e->start, e->start + e->size);
 878                     e = e->next;
 879                 } while (e != NULL);
 880                 printf("\n");
 881             }
 882         }
 883     }
 884 }
 885 #endif
 886
 887 /* some useful checked functions */
 888
 889 /* check that (p ... p + size - 1) lies inside 'p' region, if any */
 890 static void __bound_check(const void *p, size_t size)
 891 {
 892     if (size == 0)
 893         return;
 894     p = __bound_ptr_add((void *)p, size);
 895     if (p == INVALID_POINTER)
 896         bound_error("invalid pointer");
 897 }
 898
 899 void *__bound_memcpy(void *dst, const void *src, size_t size)
 900 {
 901     __bound_check(dst, size);
 902     __bound_check(src, size);
 903     /* check also region overlap */
 904     if (src >= dst && src < dst + size)
 905         bound_error("overlapping regions in memcpy()");
 906     return memcpy(dst, src, size);
 907 }
 908
 909 void *__bound_memmove(void *dst, const void *src, size_t size)
 910 {
 911     __bound_check(dst, size);
 912     __bound_check(src, size);
 913     return memmove(dst, src, size);
 914 }
 915
 916 void *__bound_memset(void *dst, int c, size_t size)
 917 {
 918     __bound_check(dst, size);
 919     return memset(dst, c, size);
 920 }
 921
 922 /* XXX: could be optimized */
 923 int __bound_strlen(const char *s)
 924 {
 925     const char *p;
 926     size_t len;
 927
 928     len = 0;
 929     for(;;) {
 930         p = __bound_ptr_indir1((char *)s, len);
 931         if (p == INVALID_POINTER)
 932             bound_error("bad pointer in strlen()");
 933         if (*p == '\0')
 934             break;
 935         len++;
 936     }
 937     return len;
 938 }
 939
 940 char *__bound_strcpy(char *dst, const char *src)
 941 {
 942     int len;
 943     len = __bound_strlen(src);
 944     return __bound_memcpy(dst, src, len + 1);
 945 }