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