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