bcheck.c

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