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 void __bound_delete_region(void *p);
  58
  59 void *__bound_ptr_add(void *p, int offset) __attribute__((regparm(2)));
  60 char __bound_ptr_indir_b(void *p, int offset) __attribute__((regparm(2)));
  61 unsigned char __bound_ptr_indir_ub(void *p, int offset) __attribute__((regparm(2)));
  62 short __bound_ptr_indir_w(void *p, int offset) __attribute__((regparm(2)));
  63 unsigned short __bound_ptr_indir_uw(void *p, int offset) __attribute__((regparm(2)));
  64 int __bound_ptr_indir_i(void *p, int offset) __attribute((regparm(2)));
  65
  66 void *__bound_calloc(size_t nmemb, size_t size);
  67 void *__bound_malloc(size_t size);
  68 void __bound_free(void *ptr);
  69 void *__bound_realloc(void *ptr, size_t size);
  70
  71 extern char _end;
  72
  73 #ifdef BOUND_STATIC
  74 static BoundEntry *__bound_t1[BOUND_T1_SIZE]; /* page table */
  75 #else
  76 static BoundEntry **__bound_t1; /* page table */
  77 #endif
  78 static BoundEntry *__bound_empty_t2;   /* empty page, for unused pages */
  79 static BoundEntry *__bound_invalid_t2; /* invalid page, for invalid pointers */
  80
  81 static BoundEntry *__bound_find_region(BoundEntry *e1, void *p)
  82 {
  83     unsigned long addr, tmp;
  84     BoundEntry *e;
  85
  86     e = e1;
  87     while (e != NULL) {
  88         addr = (unsigned long)p;
  89         addr -= e->start;
  90         if (addr <= e->size) {
  91             /* put region at the head */
  92             tmp = e1->start;
  93             e1->start = e->start;
  94             e->start = tmp;
  95             tmp = e1->size;
  96             e1->size = e->size;
  97             e->size = tmp;
  98             return e1;
  99         }
 100         e = e->next;
 101     }
 102     /* no entry found: return empty entry or invalid entry */
 103     if (e1->is_invalid)
 104         return __bound_invalid_t2;
 105     else
 106         return __bound_empty_t2;
 107 }
 108
 109 static void bound_error(const char *fmt, ...)
 110 {
 111     va_list ap;
 112     va_start(ap, fmt);
 113     fprintf(stderr, "bounds check: ");
 114     vfprintf(stderr, fmt, ap);
 115     fprintf(stderr, "\n");
 116     exit(1);
 117     va_end(ap);
 118 }
 119
 120 static void bound_alloc_error(void)
 121 {
 122     bound_error("not enough memory for bound checking code\n");
 123 }
 124
 125 /* do: return (p + offset); */
 126 void *__bound_ptr_add(void *p, int offset)
 127 {
 128     unsigned long addr = (unsigned long)p;
 129     BoundEntry *e;
 130 #ifdef BOUND_DEBUG
 131     printf("add: 0x%x %d\n", (int)p, offset);
 132 #endif
 133
 134     e = __bound_t1[addr >> (BOUND_T2_BITS + BOUND_T3_BITS)];
 135     e = (BoundEntry *)((char *)e +
 136                        ((addr >> (BOUND_T3_BITS - BOUND_E_BITS)) &
 137                         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS)));
 138     addr -= e->start;
 139     if (addr > e->size) {
 140         e = __bound_find_region(e, p);
 141         addr = (unsigned long)p - e->start;
 142     }
 143     addr += offset;
 144     if (addr > e->size)
 145         return INVALID_POINTER; /* return an invalid pointer */
 146     return p + offset;
 147 }
 148
 149 /* do: return *(type *)(p + offset); */
 150 #define BOUND_PTR_INDIR(suffix, type)                                   \
 151 type __bound_ptr_indir_ ## suffix (void *p, int offset)                 \
 152 {                                                                       \
 153     unsigned long addr = (unsigned long)p;                              \
 154     BoundEntry *e;                                                      \
 155                                                                         \
 156     e = __bound_t1[addr >> (BOUND_T2_BITS + BOUND_T3_BITS)];            \
 157     e = (BoundEntry *)((char *)e +                                      \
 158                        ((addr >> (BOUND_T3_BITS - BOUND_E_BITS)) &      \
 159                         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS)));        \
 160     addr -= e->start;                                                   \
 161     if (addr > e->size) {                                               \
 162         e = __bound_find_region(e, p);                                  \
 163         addr = (unsigned long)p - e->start;                             \
 164     }                                                                   \
 165     addr += offset + sizeof(type);                                      \
 166     if (addr > e->size)                                                 \
 167         bound_error("dereferencing invalid pointer");                   \
 168     return *(type *)(p + offset);                                       \
 169 }
 170
 171 BOUND_PTR_INDIR(b, char)
 172 BOUND_PTR_INDIR(ub, unsigned char)
 173 BOUND_PTR_INDIR(w, short)
 174 BOUND_PTR_INDIR(uw, unsigned short)
 175 BOUND_PTR_INDIR(i, int)
 176
 177 static BoundEntry *__bound_new_page(void)
 178 {
 179     BoundEntry *page;
 180     int i;
 181
 182     page = malloc(sizeof(BoundEntry) * BOUND_T2_SIZE);
 183     if (!page)
 184         bound_alloc_error();
 185     for(i=0;i<BOUND_T2_SIZE;i++) {
 186         /* put empty entries */
 187         page[i].start = 0;
 188         page[i].size = EMPTY_SIZE;
 189         page[i].next = NULL;
 190         page[i].is_invalid = 0;
 191     }
 192     return page;
 193 }
 194
 195 /* currently we use malloc(). Should use bound_new_page() */
 196 static BoundEntry *bound_new_entry(void)
 197 {
 198     BoundEntry *e;
 199     e = malloc(sizeof(BoundEntry));
 200     return e;
 201 }
 202
 203 static void bound_free_entry(BoundEntry *e)
 204 {
 205     free(e);
 206 }
 207
 208 static inline BoundEntry *get_page(int index)
 209 {
 210     BoundEntry *page;
 211     page = __bound_t1[index];
 212     if (page == __bound_empty_t2 || page == __bound_invalid_t2) {
 213         /* create a new page if necessary */
 214         page = __bound_new_page();
 215         __bound_t1[index] = page;
 216     }
 217     return page;
 218 }
 219
 220 /* mark a region as being invalid (can only be used during init) */
 221 static void mark_invalid(unsigned long addr, unsigned long size)
 222 {
 223     unsigned long start, end;
 224     BoundEntry *page;
 225     int t1_start, t1_end, i, j, t2_start, t2_end;
 226
 227     start = addr;
 228     end = addr + size;
 229
 230     t2_start = (start + BOUND_T3_SIZE - 1) >> BOUND_T3_BITS;
 231     if (end != 0)
 232         t2_end = end >> BOUND_T3_BITS;
 233     else
 234         t2_end = 1 << (BOUND_T1_BITS + BOUND_T2_BITS);
 235
 236     printf("mark_invalid: start = %x %x\n", t2_start, t2_end);
 237
 238     /* first we handle full pages */
 239     t1_start = (t2_start + BOUND_T2_SIZE - 1) >> BOUND_T2_BITS;
 240     t1_end = t2_end >> BOUND_T2_BITS;
 241
 242     i = t2_start & (BOUND_T2_SIZE - 1);
 243     j = t2_end & (BOUND_T2_SIZE - 1);
 244
 245     if (t1_start == t1_end) {
 246         page = get_page(t2_start >> BOUND_T2_BITS);
 247         for(; i < j; i++) {
 248             page[i].size = INVALID_SIZE;
 249             page[i].is_invalid = 1;
 250         }
 251     } else {
 252         if (i > 0) {
 253             page = get_page(t2_start >> BOUND_T2_BITS);
 254             for(; i < BOUND_T2_SIZE; i++) {
 255                 page[i].size = INVALID_SIZE;
 256                 page[i].is_invalid = 1;
 257             }
 258         }
 259         for(i = t1_start; i < t1_end; i++) {
 260             __bound_t1[i] = __bound_invalid_t2;
 261         }
 262         if (j != 0) {
 263             page = get_page(t1_end);
 264             for(i = 0; i < j; i++) {
 265                 page[i].size = INVALID_SIZE;
 266                 page[i].is_invalid = 1;
 267             }
 268         }
 269     }
 270 }
 271
 272 void __bound_init(void)
 273 {
 274     int i;
 275     BoundEntry *page;
 276     unsigned long start, size;
 277
 278 #ifndef BOUND_STATIC
 279     __bound_t1 = malloc(BOUND_T1_SIZE * sizeof(BoundEntry *));
 280     if (!__bound_t1)
 281         bound_alloc_error();
 282 #endif
 283     __bound_empty_t2 = __bound_new_page();
 284     for(i=0;i<BOUND_T1_SIZE;i++) {
 285         __bound_t1[i] = __bound_empty_t2;
 286     }
 287
 288     page = __bound_new_page();
 289     for(i=0;i<BOUND_T2_SIZE;i++) {
 290         /* put invalid entries */
 291         page[i].start = 0;
 292         page[i].size = INVALID_SIZE;
 293         page[i].next = NULL;
 294         page[i].is_invalid = 1;
 295     }
 296     __bound_invalid_t2 = page;
 297
 298     /* invalid pointer zone */
 299     start = (unsigned long)INVALID_POINTER & ~(BOUND_T23_SIZE - 1);
 300     size = BOUND_T23_SIZE;
 301     mark_invalid(start, size);
 302
 303     /* malloc zone is also marked invalid */
 304     start = (unsigned long)&_end;
 305     size = 128 * 0x100000;
 306     mark_invalid(start, size);
 307 }
 308
 309 static inline void add_region(BoundEntry *e,
 310                               unsigned long start, unsigned long size)
 311 {
 312     BoundEntry *e1;
 313     if (e->start == 0) {
 314         /* no region : add it */
 315         e->start = start;
 316         e->size = size;
 317     } else {
 318         /* already regions in the list: add it at the head */
 319         e1 = bound_new_entry();
 320         e1->start = e->start;
 321         e1->size = e->size;
 322         e1->next = e->next;
 323         e->start = start;
 324         e->size = size;
 325         e->next = e1;
 326     }
 327 }
 328
 329 /* create a new region. It should not already exist in the region list */
 330 void __bound_new_region(void *p, unsigned long size)
 331 {
 332     unsigned long start, end;
 333     BoundEntry *page, *e, *e2;
 334     int t1_start, t1_end, i, t2_start, t2_end;
 335
 336     start = (unsigned long)p;
 337     end = start + size;
 338     t1_start = start >> (BOUND_T2_BITS + BOUND_T3_BITS);
 339     t1_end = end >> (BOUND_T2_BITS + BOUND_T3_BITS);
 340
 341     /* start */
 342     page = get_page(t1_start);
 343     t2_start = (start >> (BOUND_T3_BITS - BOUND_E_BITS)) &
 344         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS);
 345     t2_end = (end >> (BOUND_T3_BITS - BOUND_E_BITS)) &
 346         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS);
 347 #ifdef BOUND_DEBUG
 348     printf("new %lx %lx %x %x %x %x\n",
 349            start, end, t1_start, t1_end, t2_start, t2_end);
 350 #endif
 351
 352     e = (BoundEntry *)((char *)page + t2_start);
 353     add_region(e, start, size);
 354
 355     if (t1_end == t1_start) {
 356         /* same ending page */
 357         e2 = (BoundEntry *)((char *)page + t2_end);
 358         if (e2 > e) {
 359             e++;
 360             for(;e<e2;e++) {
 361                 e->start = start;
 362                 e->size = size;
 363             }
 364             add_region(e, start, size);
 365         }
 366     } else {
 367         /* mark until end of page */
 368         e2 = page + BOUND_T2_SIZE;
 369         e++;
 370         for(;e<e2;e++) {
 371             e->start = start;
 372             e->size = size;
 373         }
 374         /* mark intermediate pages, if any */
 375         for(i=t1_start+1;i<t1_end;i++) {
 376             page = get_page(i);
 377             e2 = page + BOUND_T2_SIZE;
 378             for(e=page;e<e2;e++) {
 379                 e->start = start;
 380                 e->size = size;
 381             }
 382         }
 383         /* last page */
 384         page = get_page(t2_end);
 385         e2 = (BoundEntry *)((char *)page + t2_end);
 386         for(e=page;e<e2;e++) {
 387             e->start = start;
 388             e->size = size;
 389         }
 390         add_region(e, start, size);
 391     }
 392 }
 393
 394 /* delete a region */
 395 static inline void delete_region(BoundEntry *e,
 396                                  void *p, unsigned long empty_size)
 397 {
 398     unsigned long addr;
 399     BoundEntry *e1;
 400
 401     addr = (unsigned long)p;
 402     addr -= e->start;
 403     if (addr <= e->size) {
 404         /* region found is first one */
 405         e1 = e->next;
 406         if (e1 == NULL) {
 407             /* no more region: mark it empty */
 408             e->start = 0;
 409             e->size = empty_size;
 410         } else {
 411             /* copy next region in head */
 412             e->start = e1->start;
 413             e->size = e1->size;
 414             e->next = e1->next;
 415             bound_free_entry(e1);
 416         }
 417     } else {
 418         /* find the matching region */
 419         for(;;) {
 420             e1 = e;
 421             e = e->next;
 422             /* region not found: do nothing */
 423             if (e == NULL)
 424                 break;
 425             addr = (unsigned long)p - e->start;
 426             if (addr <= e->size) {
 427                 /* found: remove entry */
 428                 e1->next = e->next;
 429                 bound_free_entry(e);
 430                 break;
 431             }
 432         }
 433     }
 434 }
 435
 436 /* WARNING: 'p' must be the starting point of the region. */
 437 void __bound_delete_region(void *p)
 438 {
 439     unsigned long start, end, addr, size, empty_size;
 440     BoundEntry *page, *e, *e2;
 441     int t1_start, t1_end, t2_start, t2_end, i;
 442
 443     start = (unsigned long)p;
 444     t1_start = start >> (BOUND_T2_BITS + BOUND_T3_BITS);
 445     t2_start = (start >> (BOUND_T3_BITS - BOUND_E_BITS)) &
 446         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS);
 447
 448     /* find region size */
 449     page = __bound_t1[t1_start];
 450     e = (BoundEntry *)((char *)page + t2_start);
 451     addr = start - e->start;
 452     if (addr > e->size)
 453         e = __bound_find_region(e, p);
 454     /* test if invalid region */
 455     if (e->size == EMPTY_SIZE || (unsigned long)p != e->start)
 456         bound_error("deleting invalid region");
 457     /* compute the size we put in invalid regions */
 458     if (e->is_invalid)
 459         empty_size = INVALID_SIZE;
 460     else
 461         empty_size = EMPTY_SIZE;
 462     size = e->size;
 463     end = start + size;
 464
 465     /* now we can free each entry */
 466     t1_end = end >> (BOUND_T2_BITS + BOUND_T3_BITS);
 467     t2_end = (end >> (BOUND_T3_BITS - BOUND_E_BITS)) &
 468         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS);
 469
 470     delete_region(e, p, empty_size);
 471     if (t1_end == t1_start) {
 472         /* same ending page */
 473         e2 = (BoundEntry *)((char *)page + t2_end);
 474         if (e2 > e) {
 475             e++;
 476             for(;e<e2;e++) {
 477                 e->start = 0;
 478                 e->size = empty_size;
 479             }
 480             delete_region(e, p, empty_size);
 481         }
 482     } else {
 483         /* mark until end of page */
 484         e2 = page + BOUND_T2_SIZE;
 485         e++;
 486         for(;e<e2;e++) {
 487             e->start = 0;
 488             e->size = empty_size;
 489         }
 490         /* mark intermediate pages, if any */
 491         /* XXX: should free them */
 492         for(i=t1_start+1;i<t1_end;i++) {
 493             page = get_page(i);
 494             e2 = page + BOUND_T2_SIZE;
 495             for(e=page;e<e2;e++) {
 496                 e->start = 0;
 497                 e->size = empty_size;
 498             }
 499         }
 500         /* last page */
 501         page = get_page(t2_end);
 502         e2 = (BoundEntry *)((char *)page + t2_end);
 503         for(e=page;e<e2;e++) {
 504             e->start = 0;
 505             e->size = empty_size;
 506         }
 507         delete_region(e, p, empty_size);
 508     }
 509 }
 510
 511 /* return the size of the region starting at p, or EMPTY_SIZE if non
 512    existant region. */
 513 static unsigned long get_region_size(void *p)
 514 {
 515     unsigned long addr = (unsigned long)p;
 516     BoundEntry *e;
 517
 518     e = __bound_t1[addr >> (BOUND_T2_BITS + BOUND_T3_BITS)];
 519     e = (BoundEntry *)((char *)e +
 520                        ((addr >> (BOUND_T3_BITS - BOUND_E_BITS)) &
 521                         ((BOUND_T2_SIZE - 1) << BOUND_E_BITS)));
 522     addr -= e->start;
 523     if (addr > e->size)
 524         e = __bound_find_region(e, p);
 525     if (e->start != (unsigned long)p)
 526         return EMPTY_SIZE;
 527     return e->size;
 528 }
 529
 530 /* patched memory functions */
 531
 532 /* XXX: we should use a malloc which ensure that it is unlikely that
 533    two malloc'ed data have the same address if 'free' are made in
 534    between. */
 535 void *__bound_malloc(size_t size)
 536 {
 537     void *ptr;
 538     /* we allocate one more byte to ensure the regions will be
 539        separated by at least one byte. With the glibc malloc, it may
 540        be in fact not necessary */
 541     ptr = malloc(size + 1);
 542     if (!ptr)
 543         return NULL;
 544     __bound_new_region(ptr, size);
 545     return ptr;
 546 }
 547
 548 void __bound_free(void *ptr)
 549 {
 550     if (ptr == NULL)
 551         return;
 552     __bound_delete_region(ptr);
 553     free(ptr);
 554 }
 555
 556 void *__bound_realloc(void *ptr, size_t size)
 557 {
 558     void *ptr1;
 559     int old_size;
 560
 561     if (size == 0) {
 562         __bound_free(ptr);
 563         return NULL;
 564     } else {
 565         ptr1 = __bound_malloc(size);
 566         if (ptr == NULL || ptr1 == NULL)
 567             return ptr1;
 568         old_size = get_region_size(ptr);
 569         if (old_size == EMPTY_SIZE)
 570             bound_error("realloc'ing invalid pointer");
 571         memcpy(ptr1, ptr, old_size);
 572         __bound_free(ptr);
 573         return ptr1;
 574     }
 575 }
 576
 577 void *__bound_calloc(size_t nmemb, size_t size)
 578 {
 579     void *ptr;
 580     size = size * nmemb;
 581     ptr = __bound_malloc(size);
 582     if (!ptr)
 583         return NULL;
 584     memset(ptr, 0, size);
 585     return ptr;
 586 }
 587
 588 #if 0
 589 static void bound_dump(void)
 590 {
 591     BoundEntry *page, *e;
 592     int i, j;
 593
 594     printf("region dump:\n");
 595     for(i=0;i<BOUND_T1_SIZE;i++) {
 596         page = __bound_t1[i];
 597         for(j=0;j<BOUND_T2_SIZE;j++) {
 598             e = page + j;
 599             /* do not print invalid or empty entries */
 600             if (e->size != EMPTY_SIZE && e->start != 0) {
 601                 printf("%08x:",
 602                        (i << (BOUND_T2_BITS + BOUND_T3_BITS)) +
 603                        (j << BOUND_T3_BITS));
 604                 do {
 605                     printf(" %08lx:%08lx", e->start, e->start + e->size);
 606                     e = e->next;
 607                 } while (e != NULL);
 608                 printf("\n");
 609             }
 610         }
 611     }
 612 }
 613 #endif