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