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