libmudflap/mf-runtime.c

   1 /* Mudflap: narrow-pointer bounds-checking by tree rewriting.
   2    Copyright (C) 2002, 2003 Free Software Foundation, Inc.
   3    Contributed by Frank Ch. Eigler <fche@redhat.com>
   4    and Graydon Hoare <graydon@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 In addition to the permissions in the GNU General Public License, the
  14 Free Software Foundation gives you unlimited permission to link the
  15 compiled version of this file into combinations with other programs,
  16 and to distribute those combinations without any restriction coming
  17 from the use of this file.  (The General Public License restrictions
  18 do apply in other respects; for example, they cover modification of
  19 the file, and distribution when not linked into a combine
  20 executable.)
  21
  22 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  23 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  24 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  25 for more details.
  26
  27 You should have received a copy of the GNU General Public License
  28 along with GCC; see the file COPYING.  If not, write to the Free
  29 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  30 02111-1307, USA.  */
  31
  32 #include "config.h"
  33
  34 /* These attempt to coax various unix flavours to declare all our
  35    needed tidbits in the system headers.  */
  36 #if !defined(__FreeBSD__)
  37 #define _POSIX_SOURCE
  38 #endif /* Some BSDs break <sys/socket.h> if this is defined. */
  39 #define _GNU_SOURCE
  40 #define _XOPEN_SOURCE
  41 #define _BSD_TYPES
  42 #define __EXTENSIONS__
  43 #define _ALL_SOURCE
  44 #define _LARGE_FILE_API
  45 #define _XOPEN_SOURCE_EXTENDED 1
  46
  47 #include <stdio.h>
  48 #include <stdlib.h>
  49 #include <sys/types.h>
  50 #include <sys/time.h>
  51 #include <time.h>
  52 #include <unistd.h>
  53 #ifdef HAVE_EXECINFO_H
  54 #include <execinfo.h>
  55 #endif
  56 #ifdef HAVE_SIGNAL_H
  57 #include <signal.h>
  58 #endif
  59 #include <assert.h>
  60
  61 #include <string.h>
  62 #include <limits.h>
  63 #include <sys/types.h>
  64 #include <signal.h>
  65 #include <errno.h>
  66
  67 #include "mf-runtime.h"
  68 #include "mf-impl.h"
  69
  70
  71 /* ------------------------------------------------------------------------ */
  72 /* Utility macros */
  73
  74 #define CTOR  __attribute__ ((constructor))
  75 #define DTOR  __attribute__ ((destructor))
  76
  77
  78 /* Codes to describe the context in which a violation occurs. */
  79 #define __MF_VIOL_UNKNOWN 0
  80 #define __MF_VIOL_READ 1
  81 #define __MF_VIOL_WRITE 2
  82 #define __MF_VIOL_REGISTER 3
  83 #define __MF_VIOL_UNREGISTER 4
  84 #define __MF_VIOL_WATCH 5
  85
  86 /* Protect against recursive calls. */
  87 #define BEGIN_RECURSION_PROTECT() do { \
  88   if (UNLIKELY (__mf_state == reentrant)) { \
  89     write (2, "mf: erroneous reentrancy detected in `", 38); \
  90     write (2, __PRETTY_FUNCTION__, strlen(__PRETTY_FUNCTION__)); \
  91     write (2, "'\n", 2); \
  92     abort (); } \
  93   __mf_state = reentrant;  \
  94   } while (0)
  95
  96 #define END_RECURSION_PROTECT() do { \
  97   __mf_state = active; \
  98   } while (0)
  99
 100
 101
 102 /* ------------------------------------------------------------------------ */
 103 /* Required globals.  */
 104
 105 #define LOOKUP_CACHE_MASK_DFL 1023
 106 #define LOOKUP_CACHE_SIZE_MAX 4096 /* Allows max CACHE_MASK 0x0FFF */
 107 #define LOOKUP_CACHE_SHIFT_DFL 2
 108
 109 struct __mf_cache __mf_lookup_cache [LOOKUP_CACHE_SIZE_MAX];
 110 uintptr_t __mf_lc_mask = LOOKUP_CACHE_MASK_DFL;
 111 unsigned char __mf_lc_shift = LOOKUP_CACHE_SHIFT_DFL;
 112 #define LOOKUP_CACHE_SIZE (__mf_lc_mask + 1)
 113
 114 struct __mf_options __mf_opts;
 115
 116 int __mf_starting_p = 1;
 117 #ifndef LIBMUDFLAPTH
 118 enum __mf_state_enum __mf_state = active;
 119 #else
 120 /* See __mf_state_perthread() in mf-hooks.c. */
 121 #endif
 122
 123
 124 #ifdef LIBMUDFLAPTH
 125 pthread_mutex_t __mf_biglock =
 126 #ifdef PTHREAD_ERRORCHECK_MUTEX_INITIALIZER_NP
 127        PTHREAD_ERRORCHECK_MUTEX_INITIALIZER_NP;
 128 #else
 129        PTHREAD_MUTEX_INITIALIZER;
 130 #endif
 131 #endif
 132
 133 /* Use HAVE_PTHREAD_H here instead of LIBMUDFLAPTH, so that even
 134    the libmudflap.la (no threading support) can diagnose whether
 135    the application is linked with -lpthread.  See __mf_usage() below.  */
 136 #if HAVE_PTHREAD_H
 137 #pragma weak pthread_join
 138 const void *threads_active_p = (void *) pthread_join;
 139 #endif
 140
 141
 142 /* ------------------------------------------------------------------------ */
 143 /* stats-related globals.  */
 144
 145 static unsigned long __mf_count_check;
 146 static unsigned long __mf_lookup_cache_reusecount [LOOKUP_CACHE_SIZE_MAX];
 147 static unsigned long __mf_treerot_left, __mf_treerot_right;
 148 static unsigned long __mf_count_register;
 149 static unsigned long __mf_total_register_size [__MF_TYPE_MAX+1];
 150 static unsigned long __mf_count_unregister;
 151 static unsigned long __mf_total_unregister_size;
 152 static unsigned long __mf_count_violation [__MF_VIOL_WATCH+1];
 153 static unsigned long __mf_sigusr1_received;
 154 static unsigned long __mf_sigusr1_handled;
 155 /* not static */ unsigned long __mf_reentrancy;
 156 #ifdef LIBMUDFLAPTH
 157 /* not static */ unsigned long __mf_lock_contention;
 158 #endif
 159
 160
 161 /* ------------------------------------------------------------------------ */
 162 /* mode-check-related globals.  */
 163
 164 typedef struct __mf_object
 165 {
 166   uintptr_t low, high; /* __mf_register parameters */
 167   const char *name;
 168   char type; /* __MF_TYPE_something */
 169   char watching_p; /* Trigger a VIOL_WATCH on access? */
 170   unsigned read_count; /* Number of times __mf_check/read was called on this object.  */
 171   unsigned write_count; /* Likewise for __mf_check/write.  */
 172   unsigned liveness; /* A measure of recent checking activity.  */
 173   unsigned description_epoch; /* Last epoch __mf_describe_object printed this.  */
 174
 175   uintptr_t alloc_pc;
 176   struct timeval alloc_time;
 177   char **alloc_backtrace;
 178   size_t alloc_backtrace_size;
 179 #ifdef LIBMUDFLAPTH
 180   pthread_t alloc_thread;
 181 #endif
 182
 183   int deallocated_p;
 184   uintptr_t dealloc_pc;
 185   struct timeval dealloc_time;
 186   char **dealloc_backtrace;
 187   size_t dealloc_backtrace_size;
 188 #ifdef LIBMUDFLAPTH
 189   pthread_t dealloc_thread;
 190 #endif
 191 } __mf_object_t;
 192
 193
 194 typedef struct __mf_object_tree
 195 {
 196   __mf_object_t data;
 197   struct __mf_object_tree *left;
 198   struct __mf_object_tree *right;
 199 } __mf_object_tree_t;
 200
 201 /* Live objects: binary tree on __mf_object_t.low */
 202 static __mf_object_tree_t *__mf_object_root;
 203
 204 /* Dead objects: circular arrays; _MIN_CEM .. _MAX_CEM only */
 205 static unsigned __mf_object_dead_head[__MF_TYPE_MAX_CEM+1]; /* next empty spot */
 206 static __mf_object_tree_t *__mf_object_cemetary[__MF_TYPE_MAX_CEM+1][__MF_PERSIST_MAX];
 207
 208
 209 /* ------------------------------------------------------------------------ */
 210 /* Forward function declarations */
 211
 212 static void __mf_init () CTOR;
 213 static void __mf_sigusr1_respond ();
 214 static unsigned __mf_find_objects (uintptr_t ptr_low, uintptr_t ptr_high,
 215                                    __mf_object_tree_t **objs, unsigned max_objs);
 216 static unsigned __mf_find_dead_objects (uintptr_t ptr_low, uintptr_t ptr_high,
 217                                         __mf_object_tree_t **objs, unsigned max_objs);
 218 static void __mf_link_object (__mf_object_tree_t *obj);
 219 static void __mf_age_tree (__mf_object_tree_t *obj);
 220 static void __mf_adapt_cache ();
 221 static void __mf_unlink_object (__mf_object_tree_t *obj);
 222 static void __mf_describe_object (__mf_object_t *obj);
 223 static unsigned __mf_watch_or_not (void *ptr, size_t sz, char flag);
 224
 225
 226
 227 /* ------------------------------------------------------------------------ */
 228 /* Configuration engine */
 229
 230 static void
 231 __mf_set_default_options ()
 232 {
 233   memset (& __mf_opts, 0, sizeof (__mf_opts));
 234
 235   __mf_opts.tree_aging =    13037;
 236   __mf_opts.adapt_cache = 1000003;
 237   __mf_opts.abbreviate = 1;
 238   __mf_opts.verbose_violations = 1;
 239   __mf_opts.free_queue_length = 4;
 240   __mf_opts.persistent_count = 100;
 241   __mf_opts.crumple_zone = 32;
 242   __mf_opts.backtrace = 4;
 243   __mf_opts.mudflap_mode = mode_check;
 244   __mf_opts.violation_mode = viol_nop;
 245   __mf_opts.heur_std_data = 1;
 246 #ifdef LIBMUDFLAPTH
 247   __mf_opts.thread_stack = 0;
 248 #endif
 249 }
 250
 251 static struct option
 252 {
 253   char *name;
 254   char *description;
 255   enum
 256     {
 257       set_option,
 258       read_integer_option,
 259     } type;
 260   int value;
 261   int *target;
 262 }
 263 options [] =
 264   {
 265     {"mode-nop",
 266      "mudflaps do nothing",
 267      set_option, (int)mode_nop, (int *)&__mf_opts.mudflap_mode},
 268     {"mode-populate",
 269      "mudflaps populate object tree",
 270      set_option, (int)mode_populate, (int *)&__mf_opts.mudflap_mode},
 271     {"mode-check",
 272      "mudflaps check for memory violations",
 273      set_option, (int)mode_check, (int *)&__mf_opts.mudflap_mode},
 274     {"mode-violate",
 275      "mudflaps always cause violations (diagnostic)",
 276      set_option, (int)mode_violate, (int *)&__mf_opts.mudflap_mode},
 277
 278     {"viol-nop",
 279      "violations do not change program execution",
 280      set_option, (int)viol_nop, (int *)&__mf_opts.violation_mode},
 281     {"viol-abort",
 282      "violations cause a call to abort()",
 283      set_option, (int)viol_abort, (int *)&__mf_opts.violation_mode},
 284     {"viol-segv",
 285      "violations are promoted to SIGSEGV signals",
 286      set_option, (int)viol_segv, (int *)&__mf_opts.violation_mode},
 287     {"viol-gdb",
 288      "violations fork a gdb process attached to current program",
 289      set_option, (int)viol_gdb, (int *)&__mf_opts.violation_mode},
 290     {"trace-calls",
 291      "trace calls to mudflap runtime library",
 292      set_option, 1, &__mf_opts.trace_mf_calls},
 293     {"verbose-trace",
 294      "trace internal events within mudflap runtime library",
 295      set_option, 1, &__mf_opts.verbose_trace},
 296     {"collect-stats",
 297      "collect statistics on mudflap's operation",
 298      set_option, 1, &__mf_opts.collect_stats},
 299 #ifdef SIGUSR1
 300     {"sigusr1-report",
 301      "print report upon SIGUSR1",
 302      set_option, 1, &__mf_opts.sigusr1_report},
 303 #endif
 304     {"internal-checking",
 305      "perform more expensive internal checking",
 306      set_option, 1, &__mf_opts.internal_checking},
 307     {"age-tree",
 308      "age the object tree after N accesses for working set",
 309      read_integer_option, 1000000, &__mf_opts.tree_aging},
 310     {"print-leaks",
 311      "print any memory leaks at program shutdown",
 312      set_option, 1, &__mf_opts.print_leaks},
 313     {"check-initialization",
 314      "detect uninitialized object reads",
 315      set_option, 1, &__mf_opts.check_initialization},
 316     {"verbose-violations",
 317      "print verbose messages when memory violations occur",
 318      set_option, 1, &__mf_opts.verbose_violations},
 319     {"abbreviate",
 320      "abbreviate repetitive listings",
 321      set_option, 1, &__mf_opts.abbreviate},
 322     {"wipe-stack",
 323      "wipe stack objects at unwind",
 324      set_option, 1, &__mf_opts.wipe_stack},
 325     {"wipe-heap",
 326      "wipe heap objects at free",
 327      set_option, 1, &__mf_opts.wipe_heap},
 328     {"heur-proc-map",
 329      "support /proc/self/map heuristics",
 330      set_option, 1, &__mf_opts.heur_proc_map},
 331     {"heur-stack-bound",
 332      "enable a simple upper stack bound heuristic",
 333      set_option, 1, &__mf_opts.heur_stack_bound},
 334     {"heur-start-end",
 335      "support _start.._end heuristics",
 336      set_option, 1, &__mf_opts.heur_start_end},
 337     {"heur-stdlib",
 338      "register standard library data (argv, errno, stdin, ...)",
 339      set_option, 1, &__mf_opts.heur_std_data},
 340     {"free-queue-length",
 341      "queue N deferred free() calls before performing them",
 342      read_integer_option, 0, &__mf_opts.free_queue_length},
 343     {"persistent-count",
 344      "keep a history of N unregistered regions",
 345      read_integer_option, 0, &__mf_opts.persistent_count},
 346     {"crumple-zone",
 347      "surround allocations with crumple zones of N bytes",
 348      read_integer_option, 0, &__mf_opts.crumple_zone},
 349     /* XXX: not type-safe.
 350     {"lc-mask",
 351      "set lookup cache size mask to N (2**M - 1)",
 352      read_integer_option, 0, (int *)(&__mf_lc_mask)},
 353     {"lc-shift",
 354      "set lookup cache pointer shift",
 355      read_integer_option, 0, (int *)(&__mf_lc_shift)},
 356     */
 357     {"lc-adapt",
 358      "adapt mask/shift parameters after N cache misses",
 359      read_integer_option, 1, &__mf_opts.adapt_cache},
 360     {"backtrace",
 361      "keep an N-level stack trace of each call context",
 362      read_integer_option, 0, &__mf_opts.backtrace},
 363 #ifdef LIBMUDFLAPTH
 364     {"thread-stack",
 365      "override thread stacks allocation: N kB",
 366      read_integer_option, 0, &__mf_opts.thread_stack},
 367 #endif
 368     {0, 0, set_option, 0, NULL}
 369   };
 370
 371 static void
 372 __mf_usage ()
 373 {
 374   struct option *opt;
 375
 376   fprintf (stderr,
 377            "This is a %s%sGCC \"mudflap\" memory-checked binary.\n"
 378            "Mudflap is Copyright (C) 2002-2003 Free Software Foundation, Inc.\n"
 379            "\n"
 380            "The mudflap code can be controlled by an environment variable:\n"
 381            "\n"
 382            "$ export MUDFLAP_OPTIONS='<options>'\n"
 383            "$ <mudflapped_program>\n"
 384            "\n"
 385            "where <options> is a space-separated list of \n"
 386            "any of the following options.  Use `-no-OPTION' to disable options.\n"
 387            "\n",
 388 #if HAVE_PTHREAD_H
 389            (threads_active_p ? "multi-threaded " : "single-threaded "),
 390 #else
 391            "",
 392 #endif
 393 #if LIBMUDFLAPTH
 394            "thread-aware "
 395 #else
 396            "thread-unaware "
 397 #endif
 398             );
 399   /* XXX: The multi-threaded thread-unaware combination is bad.  */
 400
 401   for (opt = options; opt->name; opt++)
 402     {
 403       int default_p = (opt->value == * opt->target);
 404
 405       switch (opt->type)
 406         {
 407           char buf[128];
 408         case set_option:
 409           fprintf (stderr, "-%-23.23s %s", opt->name, opt->description);
 410           if (default_p)
 411             fprintf (stderr, " [active]\n");
 412           else
 413             fprintf (stderr, "\n");
 414           break;
 415         case read_integer_option:
 416           strncpy (buf, opt->name, 128);
 417           strncpy (buf + strlen (opt->name), "=N", 2);
 418           fprintf (stderr, "-%-23.23s %s", buf, opt->description);
 419           fprintf (stderr, " [%d]\n", * opt->target);
 420           break;
 421         default: abort();
 422         }
 423     }
 424
 425   fprintf (stderr, "\n");
 426 }
 427
 428
 429 int
 430 __mf_set_options (const char *optstr)
 431 {
 432   int rc;
 433   LOCKTH ();
 434   BEGIN_RECURSION_PROTECT ();
 435   rc = __mfu_set_options (optstr);
 436   /* XXX: It's not really that easy.  A change to a bunch of parameters
 437      can require updating auxiliary state or risk crashing:
 438      free_queue_length, crumple_zone ... */
 439   END_RECURSION_PROTECT ();
 440   UNLOCKTH ();
 441   return rc;
 442 }
 443
 444
 445 int
 446 __mfu_set_options (const char *optstr)
 447 {
 448   struct option *opts = 0;
 449   char *nxt = 0;
 450   long tmp = 0;
 451   int rc = 0;
 452   const char *saved_optstr = optstr;
 453
 454   /* XXX: bounds-check for optstr! */
 455
 456   while (*optstr)
 457     {
 458       switch (*optstr) {
 459       case ' ':
 460       case '\t':
 461       case '\n':
 462         optstr++;
 463         break;
 464
 465       case '-':
 466         if (*optstr+1)
 467           {
 468             int negate = 0;
 469             optstr++;
 470
 471             if (*optstr == '?' ||
 472                 strncmp (optstr, "help", 4) == 0)
 473               {
 474                 /* Caller will print help and exit.  */
 475                 return -1;
 476               }
 477
 478             if (strncmp (optstr, "no-", 3) == 0)
 479               {
 480                 negate = 1;
 481                 optstr = & optstr[3];
 482               }
 483
 484             for (opts = options; opts->name; opts++)
 485               {
 486                 if (strncmp (optstr, opts->name, strlen (opts->name)) == 0)
 487                   {
 488                     optstr += strlen (opts->name);
 489                     assert (opts->target);
 490                     switch (opts->type)
 491                       {
 492                       case set_option:
 493                         if (negate)
 494                           *(opts->target) = 0;
 495                         else
 496                           *(opts->target) = opts->value;
 497                         break;
 498                       case read_integer_option:
 499                         if (! negate && (*optstr == '=' && *(optstr+1)))
 500                           {
 501                             optstr++;
 502                             tmp = strtol (optstr, &nxt, 10);
 503                             if ((optstr != nxt) && (tmp != LONG_MAX))
 504                               {
 505                                 optstr = nxt;
 506                                 *(opts->target) = (int)tmp;
 507                               }
 508                           }
 509                         else if (negate)
 510                           * opts->target = 0;
 511                         break;
 512                       }
 513                   }
 514               }
 515           }
 516         break;
 517
 518       default:
 519         fprintf (stderr,
 520                  "warning: unrecognized string '%s' in mudflap options\n",
 521                  optstr);
 522         optstr += strlen (optstr);
 523         rc = -1;
 524         break;
 525       }
 526     }
 527
 528   /* Special post-processing: bound __mf_lc_mask and free_queue_length for security. */
 529   __mf_lc_mask &= (LOOKUP_CACHE_SIZE_MAX - 1);
 530   __mf_opts.free_queue_length &= (__MF_FREEQ_MAX - 1);
 531
 532   /* Clear the lookup cache, in case the parameters got changed.  */
 533   /* XXX: race */
 534   memset (__mf_lookup_cache, 0, sizeof(__mf_lookup_cache));
 535   /* void slot 0 */
 536   __mf_lookup_cache[0].low = MAXPTR;
 537
 538   TRACE ("set options from `%s'\n", saved_optstr);
 539
 540   /* Call this unconditionally, in case -sigusr1-report was toggled. */
 541   __mf_sigusr1_respond ();
 542
 543   return rc;
 544 }
 545
 546
 547 #ifdef PIC
 548
 549 void
 550 __mf_resolve_single_dynamic (struct __mf_dynamic_entry *e)
 551 {
 552   char *err;
 553
 554   assert (e);
 555   if (e->pointer) return;
 556
 557 #if HAVE_DLVSYM
 558   if (e->version != NULL && e->version[0] != '\0') /* non-null/empty */
 559     e->pointer = dlvsym (RTLD_NEXT, e->name, e->version);
 560   else
 561 #endif
 562     e->pointer = dlsym (RTLD_NEXT, e->name);
 563
 564   err = dlerror ();
 565
 566   if (err)
 567     {
 568       fprintf (stderr, "mf: error in dlsym(\"%s\"): %s\n",
 569                e->name, err);
 570       abort ();
 571     }
 572   if (! e->pointer)
 573     {
 574       fprintf (stderr, "mf: dlsym(\"%s\") = NULL\n", e->name);
 575       abort ();
 576     }
 577 }
 578
 579
 580 static void
 581 __mf_resolve_dynamics ()
 582 {
 583   int i;
 584   for (i = 0; i < dyn_INITRESOLVE; i++)
 585     __mf_resolve_single_dynamic (& __mf_dynamic[i]);
 586 }
 587
 588
 589 /* NB: order must match enums in mf-impl.h */
 590 struct __mf_dynamic_entry __mf_dynamic [] =
 591 {
 592   {NULL, "calloc", NULL},
 593   {NULL, "free", NULL},
 594   {NULL, "malloc", NULL},
 595   {NULL, "mmap", NULL},
 596   {NULL, "munmap", NULL},
 597   {NULL, "realloc", NULL},
 598   {NULL, "DUMMY", NULL}, /* dyn_INITRESOLVE */
 599 #ifdef LIBMUDFLAPTH
 600   {NULL, "pthread_create", PTHREAD_CREATE_VERSION},
 601   {NULL, "pthread_join", NULL},
 602   {NULL, "pthread_exit", NULL}
 603 #endif
 604 };
 605
 606 #endif /* PIC */
 607
 608
 609
 610 /* ------------------------------------------------------------------------ */
 611
 612
 613 void __mf_init ()
 614 {
 615   char *ov = 0;
 616
 617   /* This initial bootstrap phase requires that __mf_starting_p = 1. */
 618 #ifdef PIC
 619   __mf_resolve_dynamics ();
 620 #endif
 621   __mf_starting_p = 0;
 622
 623   __mf_set_default_options ();
 624
 625   ov = getenv ("MUDFLAP_OPTIONS");
 626   if (ov)
 627     {
 628       int rc = __mfu_set_options (ov);
 629       if (rc < 0)
 630         {
 631           __mf_usage ();
 632           exit (1);
 633         }
 634     }
 635
 636   /* Initialize to a non-zero description epoch. */
 637   __mf_describe_object (NULL);
 638
 639 #define REG_RESERVED(obj) \
 640   __mf_register (& obj, sizeof(obj), __MF_TYPE_NOACCESS, # obj)
 641
 642   REG_RESERVED (__mf_lookup_cache);
 643   REG_RESERVED (__mf_lc_mask);
 644   REG_RESERVED (__mf_lc_shift);
 645   /* XXX: others of our statics?  */
 646
 647   /* Prevent access to *NULL. */
 648   __mf_register (MINPTR, 1, __MF_TYPE_NOACCESS, "NULL");
 649   __mf_lookup_cache[0].low = (uintptr_t) -1;
 650 }
 651
 652
 653
 654 int
 655 __wrap_main (int argc, char* argv[])
 656 {
 657   extern char **environ;
 658   extern int main ();
 659   static int been_here = 0;
 660
 661   if (__mf_opts.heur_std_data && ! been_here)
 662     {
 663       unsigned i;
 664
 665       been_here = 1;
 666       __mf_register (argv, sizeof(char *)*(argc+1), __MF_TYPE_STATIC, "argv[]");
 667       for (i=0; i<argc; i++)
 668         {
 669           unsigned j = strlen (argv[i]);
 670           __mf_register (argv[i], j+1, __MF_TYPE_STATIC, "argv element");
 671         }
 672
 673       for (i=0; ; i++)
 674         {
 675           char *e = environ[i];
 676           unsigned j;
 677           if (e == NULL) break;
 678           j = strlen (environ[i]);
 679           __mf_register (environ[i], j+1, __MF_TYPE_STATIC, "environ element");
 680         }
 681       __mf_register (environ, sizeof(char *)*(i+1), __MF_TYPE_STATIC, "environ[]");
 682
 683       __mf_register (& errno, sizeof (errno), __MF_TYPE_STATIC, "errno area");
 684
 685       __mf_register (stdin,  sizeof (*stdin),  __MF_TYPE_STATIC, "stdin");
 686       __mf_register (stdout, sizeof (*stdout), __MF_TYPE_STATIC, "stdout");
 687       __mf_register (stderr, sizeof (*stderr), __MF_TYPE_STATIC, "stderr");
 688     }
 689
 690 #ifdef PIC
 691   return main (argc, argv, environ);
 692 #else
 693   return __real_main (argc, argv, environ);
 694 #endif
 695 }
 696
 697
 698
 699 extern void __mf_fini () DTOR;
 700 void __mf_fini ()
 701 {
 702   TRACE ("__mf_fini\n");
 703   __mfu_report ();
 704 }
 705
 706
 707
 708 /* ------------------------------------------------------------------------ */
 709 /* __mf_check */
 710
 711 void __mf_check (void *ptr, size_t sz, int type, const char *location)
 712 {
 713   LOCKTH ();
 714   BEGIN_RECURSION_PROTECT ();
 715   __mfu_check (ptr, sz, type, location);
 716   END_RECURSION_PROTECT ();
 717   UNLOCKTH ();
 718 }
 719
 720
 721 void __mfu_check (void *ptr, size_t sz, int type, const char *location)
 722 {
 723   unsigned entry_idx = __MF_CACHE_INDEX (ptr);
 724   struct __mf_cache *entry = & __mf_lookup_cache [entry_idx];
 725   int judgement = 0; /* 0=undecided; <0=violation; >0=okay */
 726   uintptr_t ptr_low = (uintptr_t) ptr;
 727   uintptr_t ptr_high = CLAMPSZ (ptr, sz);
 728   struct __mf_cache old_entry = *entry;
 729
 730   if (UNLIKELY (__mf_opts.sigusr1_report))
 731     __mf_sigusr1_respond ();
 732
 733   TRACE ("check ptr=%p b=%u size=%lu %s location=`%s'\n",
 734          ptr, entry_idx, (unsigned long)sz,
 735          (type == 0 ? "read" : "write"), location);
 736
 737   switch (__mf_opts.mudflap_mode)
 738     {
 739     case mode_nop:
 740       entry->low = MINPTR;
 741       entry->high = MAXPTR;
 742       judgement = 1;
 743       break;
 744
 745     case mode_populate:
 746       entry->low = ptr_low;
 747       entry->high = ptr_high;
 748       judgement = 1;
 749       break;
 750
 751     case mode_check:
 752       {
 753         unsigned heuristics = 0;
 754
 755         /* Advance aging/adaptation counters.  */
 756         if (__mf_object_root)
 757           {
 758             static unsigned aging_count;
 759             static unsigned adapt_count;
 760             aging_count ++;
 761             adapt_count ++;
 762             if (UNLIKELY (__mf_opts.tree_aging > 0 &&
 763                           aging_count > __mf_opts.tree_aging))
 764               {
 765                 aging_count = 0;
 766                 __mf_age_tree (__mf_object_root);
 767               }
 768             if (UNLIKELY (__mf_opts.adapt_cache > 0 &&
 769                           adapt_count > __mf_opts.adapt_cache))
 770               {
 771                 adapt_count = 0;
 772                 __mf_adapt_cache ();
 773               }
 774           }
 775
 776         /* Looping only occurs if heuristics were triggered.  */
 777         while (judgement == 0)
 778           {
 779             __mf_object_tree_t* ovr_obj[1];
 780             unsigned obj_count;
 781
 782             obj_count = __mf_find_objects (ptr_low, ptr_high, ovr_obj, 1);
 783
 784             if (LIKELY (obj_count == 1)) /* A single hit! */
 785               {
 786                 __mf_object_t *obj = & ovr_obj[0]->data;
 787                 assert (obj != NULL);
 788                 if (LIKELY (ptr_low >= obj->low && ptr_high <= obj->high))
 789                   {
 790                     /* XXX: hope for no overflow!  */
 791                     if (type == __MF_CHECK_READ)
 792                       obj->read_count ++;
 793                     else
 794                       obj->write_count ++;
 795
 796                     obj->liveness ++;
 797
 798                     if (UNLIKELY (obj->type == __MF_TYPE_NOACCESS))
 799                       judgement = -1;
 800                     else if (UNLIKELY (obj->watching_p))
 801                       judgement = -2; /* trigger VIOL_WATCH */
 802                     else if (UNLIKELY (__mf_opts.check_initialization
 803                                        /* reading */
 804                                        && type == __MF_CHECK_READ
 805                                        /* not written */
 806                                        && obj->write_count == 0
 807                                        /* uninitialized (heap) */
 808                                        && obj->type == __MF_TYPE_HEAP))
 809                       judgement = -1;
 810                     else
 811                       {
 812                         /* Valid access.  */
 813                         entry->low = obj->low;
 814                         entry->high = obj->high;
 815                         judgement = 1;
 816                       }
 817                   }
 818                 /* The object did not cover the entire accessed region.  */
 819               }
 820             else if (LIKELY (obj_count > 1))
 821               {
 822                 __mf_object_tree_t **all_ovr_objs;
 823                 unsigned n;
 824                 DECLARE (void *, malloc, size_t c);
 825                 DECLARE (void, free, void *p);
 826
 827                 all_ovr_objs = CALL_REAL (malloc, (sizeof (__mf_object_tree_t *) *
 828                                                    obj_count));
 829                 if (all_ovr_objs == NULL) abort ();
 830                 n = __mf_find_objects (ptr_low, ptr_high, all_ovr_objs, obj_count);
 831                 assert (n == obj_count);
 832
 833                 /* Confirm that accessed range is covered by first/last object. */
 834                 if (LIKELY ((ptr_low >= all_ovr_objs[0]->data.low) &&
 835                             (ptr_high <= all_ovr_objs[obj_count-1]->data.high)))
 836                   {
 837                     /* Presume valid access.  */
 838                     judgement = 1;
 839
 840                     /* Confirm that intermediate objects are
 841                        contiguous and share a single name.  Thus they
 842                        are likely split up GUESS regions, or mmap
 843                        pages.  The idea of the name check is to
 844                        prevent an oversize access to a
 845                        stack-registered object (followed by some GUESS
 846                        type) from being accepted as a hit.  */
 847                     for (n=0; n<obj_count-1; n++)
 848                       {
 849                         __mf_object_t *obj = & (all_ovr_objs[n]->data);
 850                         __mf_object_t *nextobj = & (all_ovr_objs[n+1]->data);
 851
 852                         if (UNLIKELY (obj->type == __MF_TYPE_NOACCESS))
 853                           judgement = -1; /* Force error. */
 854
 855                         if (UNLIKELY (judgement == 1 &&
 856                                       (obj->high + 1 != nextobj->low)))
 857                           judgement = 0; /* Cancel presumption. */
 858
 859                         if (UNLIKELY (judgement == 1 &&
 860                                       (obj->name != nextobj->name)))
 861                           judgement = 0; /* Cancel presumption. */
 862                         /* NB: strcmp above is not necessary since the
 863                            same literal string pointer is normally
 864                            used when creating regions.  */
 865
 866                         /* XXX: hope for no overflow!  */
 867                         if (type == __MF_CHECK_READ)
 868                           obj->read_count ++;
 869                         else
 870                           obj->write_count ++;
 871                         obj->liveness ++;
 872                       }
 873
 874                     /* If the access is otherwise successful, check whether
 875                        any of the covered objects are being watched.  */
 876                     if (judgement > 0)
 877                       {
 878                         unsigned i;
 879                         for (i=0; i<obj_count; i++)
 880                           if (all_ovr_objs[i]->data.watching_p)
 881                             judgement = -2;  /* trigger VIOL_WATCH */
 882                       }
 883
 884                     /* Check for uninitialized reads.  */
 885                     if (judgement > 0 &&
 886                         __mf_opts.check_initialization &&
 887                         type == __MF_CHECK_READ)
 888                       {
 889                         unsigned i;
 890                         unsigned written_count = 0;
 891
 892                         for (i=0; i<obj_count; i++)
 893                           {
 894                             __mf_object_t *obj = & all_ovr_objs[i]->data;
 895
 896                             if (obj->write_count
 897                                 || obj->type == __MF_TYPE_HEAP_I
 898                                 || obj->type == __MF_TYPE_GUESS)
 899                               written_count ++;
 900                           }
 901
 902                         /* Check for ALL pieces having been written-to.
 903                            XXX: should this be ANY instead?  */
 904                         if (written_count != obj_count)
 905                           judgement = -1;
 906                       }
 907
 908                     /* Fill out the cache with the bounds of the first
 909                        object and the last object that covers this
 910                        cache line (== includes the same __MF_CACHE_INDEX).
 911                        This could let this cache line span *two* distinct
 912                        registered objects: a peculiar but reasonable
 913                        situation.  The cache line may not include the
 914                        entire object though.  */
 915                     if (judgement > 0)
 916                       {
 917                         unsigned i;
 918                         entry->low = all_ovr_objs[0]->data.low;
 919                         for (i=0; i<obj_count; i++)
 920                           {
 921                             uintptr_t high = all_ovr_objs[i]->data.high;
 922                             if (__MF_CACHE_INDEX (high) == entry_idx)
 923                               entry->high = high;
 924                           }
 925                       }
 926                   }
 927
 928                 CALL_REAL (free, all_ovr_objs);
 929               }
 930
 931             if (judgement == 0)
 932               {
 933                 if (heuristics++ < 2) /* XXX parametrize this number? */
 934                   judgement = __mf_heuristic_check (ptr_low, ptr_high);
 935                 else
 936                   judgement = -1;
 937               }
 938           }
 939
 940       }
 941       break;
 942
 943     case mode_violate:
 944       judgement = -1;
 945       break;
 946     }
 947
 948   if (__mf_opts.collect_stats)
 949     {
 950       __mf_count_check ++;
 951
 952       if (LIKELY (old_entry.low != entry->low || old_entry.high != entry->high))
 953         /* && (old_entry.low != 0) && (old_entry.high != 0)) */
 954         __mf_lookup_cache_reusecount [entry_idx] ++;
 955     }
 956
 957   if (UNLIKELY (judgement < 0))
 958     __mf_violation (ptr, sz,
 959                     (uintptr_t) __builtin_return_address (0), location,
 960                     ((judgement == -1) ?
 961                      (type == __MF_CHECK_READ ? __MF_VIOL_READ : __MF_VIOL_WRITE) :
 962                      __MF_VIOL_WATCH));
 963 }
 964
 965
 966 static __mf_object_tree_t *
 967 __mf_insert_new_object (uintptr_t low, uintptr_t high, int type,
 968                         const char *name, uintptr_t pc)
 969 {
 970   DECLARE (void *, calloc, size_t c, size_t n);
 971
 972   __mf_object_tree_t *new_obj;
 973   new_obj = CALL_REAL (calloc, 1, sizeof(__mf_object_tree_t));
 974   new_obj->data.low = low;
 975   new_obj->data.high = high;
 976   new_obj->data.type = type;
 977   new_obj->data.name = name;
 978   new_obj->data.alloc_pc = pc;
 979 #if HAVE_GETTIMEOFDAY
 980   gettimeofday (& new_obj->data.alloc_time, NULL);
 981 #endif
 982 #if LIBMUDFLAPTH
 983   new_obj->data.alloc_thread = pthread_self ();
 984 #endif
 985
 986   if (__mf_opts.backtrace > 0 && (type == __MF_TYPE_HEAP || type == __MF_TYPE_HEAP_I))
 987     new_obj->data.alloc_backtrace_size =
 988       __mf_backtrace (& new_obj->data.alloc_backtrace,
 989                       (void *) pc, 2);
 990
 991   __mf_link_object (new_obj);
 992   return new_obj;
 993 }
 994
 995
 996 static void
 997 __mf_uncache_object (__mf_object_t *old_obj)
 998 {
 999   /* Remove any low/high pointers for this object from the lookup cache.  */
1000
1001   /* Can it possibly exist in the cache?  */
1002   if (LIKELY (old_obj->read_count + old_obj->write_count))
1003     {
1004       uintptr_t low = old_obj->low;
1005       uintptr_t high = old_obj->high;
1006       unsigned idx_low = __MF_CACHE_INDEX (low);
1007       unsigned idx_high = __MF_CACHE_INDEX (high);
1008       unsigned i;
1009       for (i = idx_low; i <= idx_high; i++)
1010         {
1011           struct __mf_cache *entry = & __mf_lookup_cache [i];
1012           /* NB: the "||" in the following test permits this code to
1013              tolerate the situation introduced by __mf_check over
1014              contiguous objects, where a cache entry spans several
1015              objects.  */
1016           if (entry->low == low || entry->high == high)
1017             {
1018               entry->low = MAXPTR;
1019               entry->high = MINPTR;
1020             }
1021         }
1022     }
1023 }
1024
1025
1026 void
1027 __mf_register (void *ptr, size_t sz, int type, const char *name)
1028 {
1029   LOCKTH ();
1030   BEGIN_RECURSION_PROTECT ();
1031   __mfu_register (ptr, sz, type, name);
1032   END_RECURSION_PROTECT ();
1033   UNLOCKTH ();
1034 }
1035
1036
1037 void
1038 __mfu_register (void *ptr, size_t sz, int type, const char *name)
1039 {
1040   TRACE ("register ptr=%p size=%lu type=%x name='%s'\n",
1041          ptr, (unsigned long) sz, type, name ? name : "");
1042
1043   if (__mf_opts.collect_stats)
1044     {
1045       __mf_count_register ++;
1046       __mf_total_register_size [(type < 0) ? 0 :
1047                                 (type > __MF_TYPE_MAX) ? 0 :
1048                                 type] += sz;
1049     }
1050
1051   if (UNLIKELY (__mf_opts.sigusr1_report))
1052     __mf_sigusr1_respond ();
1053
1054   switch (__mf_opts.mudflap_mode)
1055     {
1056     case mode_nop:
1057       break;
1058
1059     case mode_violate:
1060       __mf_violation (ptr, sz, (uintptr_t) __builtin_return_address (0), NULL,
1061                       __MF_VIOL_REGISTER);
1062       break;
1063
1064     case mode_populate:
1065       /* Clear the cache.  */
1066       /* XXX: why the entire cache? */
1067       /* XXX: race */
1068       memset (__mf_lookup_cache, 0, sizeof(__mf_lookup_cache));
1069       /* void slot 0 */
1070       __mf_lookup_cache[0].low = MAXPTR;
1071       break;
1072
1073     case mode_check:
1074       {
1075         __mf_object_tree_t *ovr_objs [1];
1076         unsigned num_overlapping_objs;
1077         uintptr_t low = (uintptr_t) ptr;
1078         uintptr_t high = CLAMPSZ (ptr, sz);
1079         uintptr_t pc = (uintptr_t) __builtin_return_address (0);
1080
1081         /* Treat unknown size indication as 1.  */
1082         if (UNLIKELY (sz == 0)) sz = 1;
1083
1084         num_overlapping_objs = __mf_find_objects (low, high, ovr_objs, 1);
1085
1086         /* Handle overlaps.  */
1087         if (UNLIKELY (num_overlapping_objs > 0))
1088           {
1089             __mf_object_tree_t *ovr_obj = ovr_objs[0];
1090
1091             /* Quietly accept a single duplicate registration for
1092                static objects, since these may come from distinct
1093                compilation units.  */
1094             if (type == __MF_TYPE_STATIC
1095                 && ovr_obj->data.type == __MF_TYPE_STATIC
1096                 && ovr_obj->data.low == low
1097                 && ovr_obj->data.high == high)
1098               {
1099                 /* do nothing */
1100                 VERBOSE_TRACE ("duplicate static reg %p-%p `%s'\n",
1101                                (void *) low, (void *) high,
1102                                (ovr_obj->data.name ? ovr_obj->data.name : ""));
1103                 break;
1104               }
1105
1106             /* Quietly accept a single duplicate registration for
1107                guess objects too.  */
1108             if (type == __MF_TYPE_GUESS &&
1109                 ovr_obj->data.type == __MF_TYPE_GUESS &&
1110                 ovr_obj->data.low == low &&
1111                 ovr_obj->data.high == high)
1112               {
1113                 /* do nothing */
1114                 VERBOSE_TRACE ("duplicate guess reg %p-%p\n",
1115                                (void *) low, (void *) high);
1116                 break;
1117               }
1118
1119             /* Quietly accept new a guess registration that overlaps
1120                at least one existing object.  Trim it down to size.  */
1121             else if (type == __MF_TYPE_GUESS)
1122               {
1123                 /* We need to split this new GUESS region into some
1124                    smaller ones.  Or we may not need to insert it at
1125                    all if it is covered by the overlapping region.  */
1126
1127                 /* First, identify all the overlapping objects.  */
1128                 __mf_object_tree_t **all_ovr_objs;
1129                 unsigned num_ovr_objs, n;
1130                 uintptr_t next_low;
1131                 DECLARE (void *, malloc, size_t c);
1132                 DECLARE (void, free, void *p);
1133
1134                 all_ovr_objs = CALL_REAL (malloc, (sizeof (__mf_object_tree_t *) *
1135                                                    num_overlapping_objs));
1136                 if (all_ovr_objs == NULL) abort ();
1137                 num_ovr_objs = __mf_find_objects (low, high, all_ovr_objs,
1138                                                   num_overlapping_objs);
1139                 assert (num_ovr_objs == num_overlapping_objs);
1140
1141                 VERBOSE_TRACE ("splitting guess %p-%p, # overlaps: %u\n",
1142                                (void *) low, (void *) high, num_ovr_objs);
1143
1144                 /* Add GUESS regions between the holes: before each
1145                    overlapping region.  */
1146
1147                 next_low = low;
1148                 /* This makes use of the assumption that __mf_find_objects() returns
1149                    overlapping objects in an increasing sequence.  */
1150                 for (n=0; n < min (num_ovr_objs, num_overlapping_objs); n++)
1151                   {
1152                     if (all_ovr_objs[n]->data.low > next_low) /* Gap? */
1153                       {
1154                         uintptr_t next_high = CLAMPSUB (all_ovr_objs[n]->data.low, 1);
1155                         __mfu_register ((void *) next_low, next_high-next_low+1,
1156                                         __MF_TYPE_GUESS, name);
1157                       }
1158                     next_low = CLAMPADD (all_ovr_objs[n]->data.high, 1);
1159                   }
1160                 /* Add in any leftover room at the top.  */
1161                 if (next_low <= high)
1162                   __mfu_register ((void *) next_low, high-next_low+1,
1163                                   __MF_TYPE_GUESS, name);
1164
1165                 /* XXX: future optimization: allow consecutive GUESS regions to
1166                    be glued together.  */
1167                 CALL_REAL (free, all_ovr_objs);
1168                 return;
1169               }
1170
1171             /* Quietly accept a non-GUESS region overlaying a GUESS
1172                region.  Handle it by removing the GUESS region
1173                temporarily, then recursively adding this new object,
1174                and then the GUESS back.  The latter will be split up
1175                by the recursive process above.  */
1176             else if (ovr_obj->data.type == __MF_TYPE_GUESS)
1177               {
1178                 uintptr_t old_low = ovr_obj->data.low;
1179                 uintptr_t old_high = ovr_obj->data.high;
1180                 const char* old_name = ovr_obj->data.name;
1181
1182                 /* Now to recursively remove the guess piece, and
1183                    reinsert them in the opposite order.  Recursion
1184                    should bottom out if another non-GUESS overlapping
1185                    region is found for this new object (resulting in a
1186                    violation), or if no further overlap occurs.  The
1187                    located GUESS region should end up being split up
1188                    in any case.  */
1189                 __mfu_unregister ((void *) old_low, old_high-old_low+1);
1190                 __mfu_register ((void *) low, sz, type, name);
1191                 __mfu_register ((void *) old_low, old_high-old_low+1,
1192                                 __MF_TYPE_GUESS, old_name);
1193                 return;
1194               }
1195
1196             /* Alas, a genuine violation.  */
1197             else
1198               {
1199                 /* Two or more *real* mappings here. */
1200                 __mf_violation ((void *) ptr, sz,
1201                                 (uintptr_t) __builtin_return_address (0), NULL,
1202                                 __MF_VIOL_REGISTER);
1203               }
1204           }
1205
1206         /* No overlapping objects: AOK.  */
1207         else
1208           {
1209             __mf_insert_new_object (low, high, type, name, pc);
1210           }
1211
1212         /* We could conceivably call __mf_check() here to prime the cache,
1213            but then the read_count/write_count field is not reliable.  */
1214
1215         break;
1216       }
1217     } /* end switch (__mf_opts.mudflap_mode) */
1218 }
1219
1220
1221 void
1222 __mf_unregister (void *ptr, size_t sz)
1223 {
1224   LOCKTH ();
1225   BEGIN_RECURSION_PROTECT ();
1226   __mfu_unregister (ptr, sz);
1227   END_RECURSION_PROTECT ();
1228   UNLOCKTH ();
1229 }
1230
1231
1232 void
1233 __mfu_unregister (void *ptr, size_t sz)
1234 {
1235   DECLARE (void, free, void *ptr);
1236
1237   if (UNLIKELY (__mf_opts.sigusr1_report))
1238   __mf_sigusr1_respond ();
1239
1240   TRACE ("unregister ptr=%p size=%lu\n", ptr, (unsigned long) sz);
1241
1242   switch (__mf_opts.mudflap_mode)
1243     {
1244     case mode_nop:
1245       break;
1246
1247     case mode_violate:
1248       __mf_violation (ptr, sz,
1249                       (uintptr_t) __builtin_return_address (0), NULL,
1250                       __MF_VIOL_UNREGISTER);
1251       break;
1252
1253     case mode_populate:
1254       /* Clear the cache.  */
1255       /* XXX: race */
1256       memset (__mf_lookup_cache, 0, sizeof(__mf_lookup_cache));
1257       /* void slot 0 */
1258       __mf_lookup_cache[0].low = MAXPTR;
1259       break;
1260
1261     case mode_check:
1262       {
1263         __mf_object_tree_t *old_obj = NULL;
1264         __mf_object_tree_t *del_obj = NULL;  /* Object to actually delete. */
1265         __mf_object_tree_t *objs[1] = {NULL};
1266         unsigned num_overlapping_objs;
1267
1268         /* Treat unknown size indication as 1.  */
1269         if (sz == 0) sz = 1;
1270
1271         num_overlapping_objs = __mf_find_objects ((uintptr_t) ptr,
1272                                                   CLAMPSZ (ptr, sz), objs, 1);
1273
1274         /* XXX: handle unregistration of big old GUESS region, that has since
1275            been splintered.  */
1276         old_obj = objs[0];
1277
1278         if (UNLIKELY (num_overlapping_objs != 1 ||
1279                       (uintptr_t)ptr != old_obj->data.low)) /* XXX: what about sz? */
1280           {
1281             __mf_violation (ptr, sz,
1282                             (uintptr_t) __builtin_return_address (0), NULL,
1283                             __MF_VIOL_UNREGISTER);
1284             break;
1285           }
1286
1287         __mf_unlink_object (old_obj);
1288         __mf_uncache_object (& old_obj->data);
1289
1290         /* Wipe buffer contents if desired.  */
1291         if ((__mf_opts.wipe_stack && old_obj->data.type == __MF_TYPE_STACK)
1292             || (__mf_opts.wipe_heap && (old_obj->data.type == __MF_TYPE_HEAP
1293                                         || old_obj->data.type == __MF_TYPE_HEAP_I)))
1294           {
1295             memset ((void *) old_obj->data.low,
1296                     0,
1297                     (size_t) (old_obj->data.high - old_obj->data.low + 1));
1298           }
1299
1300         /* Manage the object cemetary.  */
1301         if (__mf_opts.persistent_count > 0 &&
1302             old_obj->data.type >= 0 &&
1303             old_obj->data.type <= __MF_TYPE_MAX_CEM)
1304           {
1305             old_obj->data.deallocated_p = 1;
1306             old_obj->left = old_obj->right = NULL;
1307             old_obj->data.dealloc_pc = (uintptr_t) __builtin_return_address (0);
1308 #if HAVE_GETTIMEOFDAY
1309             gettimeofday (& old_obj->data.dealloc_time, NULL);
1310 #endif
1311 #ifdef LIBMUDFLAPTH
1312             old_obj->data.dealloc_thread = pthread_self ();
1313 #endif
1314
1315             if (__mf_opts.backtrace > 0 && old_obj->data.type == __MF_TYPE_HEAP)
1316               old_obj->data.dealloc_backtrace_size =
1317                 __mf_backtrace (& old_obj->data.dealloc_backtrace,
1318                                 NULL, 2);
1319
1320             /* Encourage this object to be displayed again in current epoch.  */
1321             old_obj->data.description_epoch --;
1322
1323             /* Put this object into the cemetary.  This may require this plot to
1324                be recycled, and the previous resident to be designated del_obj.  */
1325             {
1326               unsigned row = old_obj->data.type;
1327               unsigned plot = __mf_object_dead_head [row];
1328
1329               del_obj = __mf_object_cemetary [row][plot];
1330               __mf_object_cemetary [row][plot] = old_obj;
1331               plot ++;
1332               if (plot == __mf_opts.persistent_count) plot = 0;
1333               __mf_object_dead_head [row] = plot;
1334             }
1335           }
1336         else
1337           del_obj = old_obj;
1338
1339         if (__mf_opts.print_leaks)
1340           {
1341             if ((old_obj->data.read_count + old_obj->data.write_count) == 0 &&
1342                 (old_obj->data.type == __MF_TYPE_HEAP
1343                  || old_obj->data.type == __MF_TYPE_HEAP_I))
1344               {
1345                 fprintf (stderr,
1346                          "*******\n"
1347                          "mudflap warning: unaccessed registered object:\n");
1348                 __mf_describe_object (& old_obj->data);
1349               }
1350           }
1351
1352         if (del_obj != NULL) /* May or may not equal old_obj.  */
1353           {
1354             if (__mf_opts.backtrace > 0)
1355               {
1356                 CALL_REAL(free, del_obj->data.alloc_backtrace);
1357                 if (__mf_opts.persistent_count > 0)
1358                   {
1359                     CALL_REAL(free, del_obj->data.dealloc_backtrace);
1360                   }
1361               }
1362             CALL_REAL(free, del_obj);
1363           }
1364
1365         break;
1366       }
1367     } /* end switch (__mf_opts.mudflap_mode) */
1368
1369
1370   if (__mf_opts.collect_stats)
1371     {
1372       __mf_count_unregister ++;
1373       __mf_total_unregister_size += sz;
1374     }
1375 }
1376
1377 /* ------------------------------------------------------------------------ */
1378 /* __mf_validate_live_object_tree, _object_cemetary */
1379
1380 static void
1381 __mf_validate_live_object_tree (__mf_object_tree_t *obj)
1382 {
1383   assert (obj != NULL);
1384
1385   if (__mf_opts.persistent_count > 0)
1386     assert (! obj->data.deallocated_p);
1387
1388   if (obj->left)
1389     {
1390       assert (obj->left->data.high < obj->data.low);
1391       __mf_validate_live_object_tree (obj->left);
1392     }
1393   if (obj->right)
1394     {
1395       assert (obj->right->data.low > obj->data.high);
1396       __mf_validate_live_object_tree (obj->right);
1397     }
1398 }
1399
1400 static void
1401 __mf_validate_object_cemetary ()
1402 {
1403   unsigned cls;
1404   unsigned i;
1405
1406   for (cls = 0; cls <= __MF_TYPE_MAX_CEM; cls++)
1407     {
1408       assert (__mf_object_dead_head [cls] >= 0 &&
1409               __mf_object_dead_head [cls] < __mf_opts.persistent_count);
1410       for (i = 0; i < __mf_opts.persistent_count; i++)
1411         {
1412           __mf_object_tree_t *obj = __mf_object_cemetary [cls][i];
1413           if (obj != NULL)
1414             {
1415               assert (obj->data.deallocated_p);
1416               assert (obj->left == NULL);
1417               assert (obj->right == NULL);
1418             }
1419         }
1420     }
1421 }
1422
1423 static void
1424 __mf_validate_objects ()
1425 {
1426   if (__mf_object_root)
1427     __mf_validate_live_object_tree (__mf_object_root);
1428
1429   if (__mf_opts.persistent_count > 0)
1430     __mf_validate_object_cemetary ();
1431 }
1432
1433
1434 static void
1435 __mf_age_tree (__mf_object_tree_t *obj)
1436 {
1437   assert (obj != NULL);
1438   obj->data.liveness = obj->data.liveness >> 1;
1439
1440   if (obj->left)
1441     __mf_age_tree (obj->left);
1442   if (obj->right)
1443     __mf_age_tree (obj->right);
1444 }
1445
1446
1447
1448 struct tree_stats
1449 {
1450   unsigned obj_count;
1451   unsigned long total_size;
1452   unsigned live_obj_count;
1453   double total_weight;
1454   double weighted_size;
1455   unsigned long weighted_address_bits [sizeof (uintptr_t) * 8][2];
1456 };
1457
1458
1459 static void
1460 __mf_tree_analyze (__mf_object_tree_t *obj, struct tree_stats* s)
1461 {
1462   assert (obj != NULL);
1463
1464   if (obj->left)
1465     __mf_tree_analyze (obj->left, s);
1466
1467   /* Exclude never-accessed objects.  */
1468   if (obj->data.read_count + obj->data.write_count)
1469     {
1470       s->obj_count ++;
1471       s->total_size += (obj->data.high - obj->data.low + 1);
1472
1473       if (obj->data.liveness)
1474         {
1475           unsigned i;
1476           uintptr_t addr;
1477
1478           VERBOSE_TRACE ("analyze low=%p live=%u name=`%s'\n",
1479                          (void *) obj->data.low, obj->data.liveness, obj->data.name);
1480
1481           s->live_obj_count ++;
1482           s->total_weight += (double) obj->data.liveness;
1483           s->weighted_size +=
1484             (double) (obj->data.high - obj->data.low + 1) *
1485             (double) obj->data.liveness;
1486
1487           addr = obj->data.low;
1488           for (i=0; i<sizeof(uintptr_t) * 8; i++)
1489             {
1490               unsigned bit = addr & 1;
1491               s->weighted_address_bits[i][bit] += obj->data.liveness;
1492               addr = addr >> 1;
1493             }
1494         }
1495     }
1496
1497   if (obj->right)
1498     __mf_tree_analyze (obj->right, s);
1499 }
1500
1501
1502 static void
1503 __mf_adapt_cache ()
1504 {
1505   struct tree_stats s;
1506   uintptr_t new_mask = 0;
1507   unsigned char new_shift;
1508   float cache_utilization;
1509   float max_value;
1510   static float smoothed_new_shift = -1.0;
1511   unsigned i;
1512
1513   memset (&s, 0, sizeof (s));
1514   if (__mf_object_root)
1515     __mf_tree_analyze (__mf_object_root, & s);
1516
1517   /* Maybe we're dealing with funny aging/adaptation parameters, or an
1518      empty tree.  Just leave the cache alone in such cases, rather
1519      than risk dying by division-by-zero.  */
1520   if (! (s.obj_count > 0) && (s.live_obj_count > 0) && (s.total_weight > 0.0))
1521     return;
1522
1523   /* Guess a good value for the shift parameter by finding an address bit that is a
1524      good discriminant of lively objects.  */
1525   max_value = 0.0;
1526   for (i=0; i<sizeof (uintptr_t)*8; i++)
1527     {
1528       float value = (float) s.weighted_address_bits[i][0] * (float) s.weighted_address_bits[i][1];
1529       if (max_value < value) max_value = value;
1530     }
1531   for (i=0; i<sizeof (uintptr_t)*8; i++)
1532     {
1533       float shoulder_factor = 0.7;  /* Include slightly less popular bits too.  */
1534       float value = (float) s.weighted_address_bits[i][0] * (float) s.weighted_address_bits[i][1];
1535       if (value >= max_value * shoulder_factor)
1536         break;
1537     }
1538   if (smoothed_new_shift < 0) smoothed_new_shift = __mf_lc_shift;
1539   /* Converge toward this slowly to reduce flapping. */
1540   smoothed_new_shift = 0.9*smoothed_new_shift + 0.1*i;
1541   new_shift = (unsigned) (smoothed_new_shift + 0.5);
1542   assert (new_shift < sizeof (uintptr_t)*8);
1543
1544   /* Count number of used buckets.  */
1545   cache_utilization = 0.0;
1546   for (i = 0; i < (1 + __mf_lc_mask); i++)
1547     if (__mf_lookup_cache[i].low != 0 || __mf_lookup_cache[i].high != 0)
1548       cache_utilization += 1.0;
1549   cache_utilization /= (1 + __mf_lc_mask);
1550
1551   new_mask |= 0x3ff; /* XXX: force a large cache.  */
1552   new_mask &= (LOOKUP_CACHE_SIZE_MAX - 1);
1553
1554   VERBOSE_TRACE ("adapt cache obj=%u/%u sizes=%lu/%.0f/%.0f => "
1555                  "util=%u%% m=%p s=%u\n",
1556                  s.obj_count, s.live_obj_count, s.total_size, s.total_weight, s.weighted_size,
1557                  (unsigned)(cache_utilization*100.0), (void *) new_mask, new_shift);
1558
1559   /* We should reinitialize cache if its parameters have changed.  */
1560   if (new_mask != __mf_lc_mask ||
1561       new_shift != __mf_lc_shift)
1562     {
1563       __mf_lc_mask = new_mask;
1564       __mf_lc_shift = new_shift;
1565       /* XXX: race */
1566       memset (__mf_lookup_cache, 0, sizeof(__mf_lookup_cache));
1567       /* void slot 0 */
1568       __mf_lookup_cache[0].low = MAXPTR;
1569     }
1570 }
1571
1572
1573
1574
1575 /* __mf_find_object[s] */
1576
1577 /* Find overlapping live objecs between [low,high].  Return up to
1578    max_objs of their pointers in objs[].  Return total count of
1579    overlaps (may exceed max_objs). */
1580
1581 /* XXX: track traversal statistics, like average depth, balance.  */
1582
1583 static unsigned
1584 __mf_find_objects_rec (uintptr_t low, uintptr_t high, __mf_object_tree_t **nodep,
1585                        __mf_object_tree_t **objs, unsigned max_objs)
1586 {
1587   unsigned count;
1588   __mf_object_tree_t *node = *nodep;
1589
1590   assert (low <= high);
1591   assert (max_objs == 0 || objs != NULL);
1592
1593   if (UNLIKELY (node == NULL)) return 0;
1594
1595   /* Traverse down left subtree. */
1596   count = 0;
1597   if (low < node->data.low)
1598     count += __mf_find_objects_rec (low, min(high, node->data.low),
1599                                     & node->left, objs, max_objs);
1600
1601   /* Track the used slots of objs[].  */
1602   if (count < max_objs)
1603     {
1604       objs += count;
1605       max_objs -= count;
1606     }
1607   else
1608     {
1609       max_objs = 0;
1610     }
1611
1612   /* Check for overlap with this node.  */
1613   if (high >= node->data.low && low <= node->data.high)
1614     {
1615       count ++;
1616       if (max_objs > 0)  /* Any room left?  */
1617         {
1618           objs[0] = node;
1619           objs ++;
1620           max_objs --;
1621         }
1622     }
1623
1624   /* Traverse down right subtree.  */
1625   if (high > node->data.high)
1626     count += __mf_find_objects_rec (max (low, node->data.high), high,
1627                                     & node->right, objs, max_objs);
1628   /* There is no need to manipulate objs/max_objs any further.  */
1629
1630
1631   /* Rotate a child node up if its access count is higher. */
1632   if (UNLIKELY ((node->left && node->left->data.liveness > node->data.liveness) &&
1633                 ((!node->right || (node->right &&
1634                                    node->left->data.liveness >
1635                                    node->right->data.liveness)))))
1636     {
1637       __mf_object_tree_t *l = node->left;
1638       __mf_object_tree_t *l_r = l->right;
1639
1640       *nodep = l;
1641       l->right = node;
1642       node->left = l_r;
1643       __mf_treerot_left ++;
1644     }
1645   else if (UNLIKELY ((node->right && node->right->data.liveness > node->data.liveness) &&
1646                      ((!node->left || (node->left &&
1647                                        node->right->data.liveness >
1648                                        node->left->data.liveness)))))
1649     {
1650       __mf_object_tree_t *r = node->right;
1651       __mf_object_tree_t *r_l = r->left;
1652
1653       *nodep = r;
1654       r->left = node;
1655       node->right = r_l;
1656       __mf_treerot_right ++;
1657     }
1658
1659   return count;
1660 }
1661
1662
1663 unsigned
1664 __mf_find_objects (uintptr_t ptr_low, uintptr_t ptr_high,
1665                    __mf_object_tree_t **objs, unsigned max_objs)
1666 {
1667   if (UNLIKELY(__mf_opts.internal_checking))
1668     __mf_validate_objects ();
1669
1670   return __mf_find_objects_rec (ptr_low, ptr_high, & __mf_object_root, objs, max_objs);
1671 }
1672
1673 /* __mf_link_object */
1674
1675 static void
1676 __mf_link_object2 (__mf_object_tree_t *ptr, __mf_object_tree_t **link)
1677 {
1678   __mf_object_tree_t *node = *link;
1679
1680   assert (ptr != NULL);
1681   if (UNLIKELY(node == NULL))
1682     {
1683       *link = ptr;
1684       return;
1685     }
1686
1687   if (ptr->data.high < node->data.low)
1688     return __mf_link_object2 (ptr, & node->left);
1689   else if (ptr->data.low > node->data.high)
1690     return __mf_link_object2 (ptr, & node->right);
1691   else
1692     abort (); /* XXX: duplicate object */
1693 }
1694
1695
1696 void
1697 __mf_link_object (__mf_object_tree_t *ptr)
1698 {
1699   if (UNLIKELY(__mf_opts.internal_checking))
1700     __mf_validate_objects ();
1701
1702   return __mf_link_object2 (ptr, & __mf_object_root);
1703 }
1704
1705 /* __mf_unlink_object */
1706
1707 static void
1708 __mf_unlink_object2 (__mf_object_tree_t *ptr, __mf_object_tree_t **link)
1709 {
1710   __mf_object_tree_t *node = *link;
1711
1712   assert (ptr != NULL);
1713   if (UNLIKELY(node == ptr))
1714     {
1715       static unsigned promote_left_p = 0;
1716       promote_left_p = 1 - promote_left_p;
1717
1718       /* Alternate promoting the left & right subtrees. */
1719       if (promote_left_p)
1720         {
1721           *link = ptr->left;
1722           if (ptr->right != NULL)
1723             __mf_link_object2 (ptr->right, link);
1724         }
1725       else
1726         {
1727           *link = ptr->right;
1728           if (ptr->left != NULL)
1729             __mf_link_object2 (ptr->left, link);
1730         }
1731
1732       return;
1733     }
1734
1735   if (ptr->data.high < node->data.low)
1736     return __mf_unlink_object2 (ptr, & node->left);
1737   else if (ptr->data.low > node->data.high)
1738     return __mf_unlink_object2 (ptr, & node->right);
1739   else
1740     abort (); /* XXX: missing object; should fail more gracefully. */
1741 }
1742
1743 static void
1744 __mf_unlink_object (__mf_object_tree_t *node)
1745 {
1746   __mf_unlink_object2 (node, & __mf_object_root);
1747 }
1748
1749 /* __mf_find_dead_objects */
1750
1751 /* Find overlapping dead objecs between [low,high].  Return up to
1752    max_objs of their pointers in objs[].  Return total count of
1753    overlaps (may exceed max_objs).  */
1754
1755 static unsigned
1756 __mf_find_dead_objects (uintptr_t low, uintptr_t high,
1757                         __mf_object_tree_t **objs, unsigned max_objs)
1758 {
1759   if (__mf_opts.persistent_count > 0)
1760     {
1761       unsigned count = 0;
1762       unsigned recollection = 0;
1763       unsigned row = 0;
1764
1765       assert (low <= high);
1766       assert (max_objs == 0 || objs != NULL);
1767
1768       /* Widen the search from the most recent plots in each row, looking
1769          backward in time.  */
1770       recollection = 0;
1771       while (recollection < __mf_opts.persistent_count)
1772         {
1773           count = 0;
1774
1775           for (row = 0; row <= __MF_TYPE_MAX_CEM; row ++)
1776             {
1777               unsigned plot;
1778               unsigned i;
1779
1780               plot = __mf_object_dead_head [row];
1781               for (i = 0; i <= recollection; i ++)
1782                 {
1783                   __mf_object_tree_t *obj;
1784
1785                   /* Look backward through row: it's a circular buffer.  */
1786                   if (plot > 0) plot --;
1787                   else plot = __mf_opts.persistent_count - 1;
1788
1789                   obj = __mf_object_cemetary [row][plot];
1790                   if (obj && obj->data.low <= high && obj->data.high >= low)
1791                     {
1792                       /* Found an overlapping dead object!  */
1793                       if (count < max_objs)
1794                         objs [count] = obj;
1795                       count ++;
1796                     }
1797                 }
1798             }
1799
1800           if (count)
1801             break;
1802
1803           /* Look farther back in time.  */
1804           recollection = (recollection * 2) + 1;
1805         }
1806
1807       return count;
1808     } else {
1809       return 0;
1810     }
1811 }
1812
1813 /* __mf_describe_object */
1814
1815 static void
1816 __mf_describe_object (__mf_object_t *obj)
1817 {
1818   static unsigned epoch = 0;
1819   if (obj == NULL)
1820     {
1821       epoch ++;
1822       return;
1823     }
1824
1825   if (__mf_opts.abbreviate && obj->description_epoch == epoch)
1826     {
1827       fprintf (stderr,
1828                "mudflap object %p: name=`%s'\n",
1829                (void *) obj, (obj->name ? obj->name : ""));
1830       return;
1831     }
1832   else
1833     obj->description_epoch = epoch;
1834
1835   fprintf (stderr,
1836            "mudflap object %p: name=`%s'\n"
1837            "bounds=[%p,%p] size=%lu area=%s check=%ur/%uw liveness=%u%s\n"
1838            "alloc time=%lu.%06lu pc=%p"
1839 #ifdef LIBMUDFLAPTH
1840            " thread=%u"
1841 #endif
1842            "\n",
1843            (void *) obj, (obj->name ? obj->name : ""),
1844            (void *) obj->low, (void *) obj->high,
1845            (unsigned long) (obj->high - obj->low + 1),
1846            (obj->type == __MF_TYPE_NOACCESS ? "no-access" :
1847             obj->type == __MF_TYPE_HEAP ? "heap" :
1848             obj->type == __MF_TYPE_HEAP_I ? "heap-init" :
1849             obj->type == __MF_TYPE_STACK ? "stack" :
1850             obj->type == __MF_TYPE_STATIC ? "static" :
1851             obj->type == __MF_TYPE_GUESS ? "guess" :
1852             "unknown"),
1853            obj->read_count, obj->write_count, obj->liveness,
1854            obj->watching_p ? " watching" : "",
1855            obj->alloc_time.tv_sec, obj->alloc_time.tv_usec,
1856            (void *) obj->alloc_pc
1857 #ifdef LIBMUDFLAPTH
1858            , (unsigned) obj->alloc_thread
1859 #endif
1860            );
1861
1862   if (__mf_opts.backtrace > 0)
1863   {
1864     unsigned i;
1865     for (i=0; i<obj->alloc_backtrace_size; i++)
1866       fprintf (stderr, "      %s\n", obj->alloc_backtrace[i]);
1867   }
1868
1869   if (__mf_opts.persistent_count > 0)
1870     {
1871       if (obj->deallocated_p)
1872         {
1873           fprintf (stderr, "dealloc time=%lu.%06lu pc=%p"
1874 #ifdef LIBMUDFLAPTH
1875                    " thread=%u"
1876 #endif
1877                    "\n",
1878                    obj->dealloc_time.tv_sec, obj->dealloc_time.tv_usec,
1879                    (void *) obj->dealloc_pc
1880 #ifdef LIBMUDFLAPTH
1881                    , (unsigned) obj->dealloc_thread
1882 #endif
1883                    );
1884
1885
1886           if (__mf_opts.backtrace > 0)
1887           {
1888             unsigned i;
1889             for (i=0; i<obj->dealloc_backtrace_size; i++)
1890               fprintf (stderr, "      %s\n", obj->dealloc_backtrace[i]);
1891           }
1892         }
1893     }
1894 }
1895
1896 static unsigned
1897 __mf_report_leaks (__mf_object_tree_t *node)
1898 {
1899  /* The counter is amongst recursive calls, so
1900     that cumulative numbers are printed below.  */
1901   static unsigned count = 0;
1902
1903   if (node == NULL)  /* Reset */
1904     {
1905       count = 0;
1906       return 0;
1907     }
1908
1909   /* Inorder traversal. */
1910   if (node->left)
1911     __mf_report_leaks (node->left);
1912   if (node->data.type == __MF_TYPE_HEAP
1913       || node->data.type == __MF_TYPE_HEAP_I)
1914     {
1915       count ++;
1916       fprintf (stderr, "Leaked object %u:\n", count);
1917       __mf_describe_object (& node->data);
1918     }
1919   if (node->right)
1920     __mf_report_leaks (node->right);
1921
1922   return count;
1923 }
1924
1925 /* ------------------------------------------------------------------------ */
1926 /* __mf_report */
1927
1928 void
1929 __mf_report ()
1930 {
1931   LOCKTH ();
1932   BEGIN_RECURSION_PROTECT ();
1933   __mfu_report ();
1934   END_RECURSION_PROTECT ();
1935   UNLOCKTH ();
1936 }
1937
1938 void
1939 __mfu_report ()
1940 {
1941   if (__mf_opts.collect_stats)
1942     {
1943       fprintf (stderr,
1944                "*******\n"
1945                "mudflap stats:\n"
1946                "calls to __mf_check: %lu rot: %lu/%lu\n"
1947                "         __mf_register: %lu [%luB, %luB, %luB, %luB, %luB]\n"
1948                "         __mf_unregister: %lu [%luB]\n"
1949                "         __mf_violation: [%lu, %lu, %lu, %lu, %lu]\n",
1950                __mf_count_check, __mf_treerot_left, __mf_treerot_right,
1951                __mf_count_register,
1952                __mf_total_register_size[0], __mf_total_register_size[1],
1953                __mf_total_register_size[2], __mf_total_register_size[3],
1954                __mf_total_register_size[4], /* XXX */
1955                __mf_count_unregister, __mf_total_unregister_size,
1956                __mf_count_violation[0], __mf_count_violation[1],
1957                __mf_count_violation[2], __mf_count_violation[3],
1958                __mf_count_violation[4]);
1959
1960       fprintf (stderr,
1961                "calls with reentrancy: %lu\n", __mf_reentrancy);
1962 #ifdef LIBMUDFLAPTH
1963       fprintf (stderr,
1964                "           lock contention: %lu\n", __mf_lock_contention);
1965 #endif
1966
1967       /* Lookup cache stats.  */
1968       {
1969         unsigned i;
1970         unsigned max_reuse = 0;
1971         unsigned num_used = 0;
1972         unsigned num_unused = 0;
1973
1974         for (i = 0; i < LOOKUP_CACHE_SIZE; i++)
1975           {
1976             if (__mf_lookup_cache_reusecount[i])
1977               num_used ++;
1978             else
1979               num_unused ++;
1980             if (max_reuse < __mf_lookup_cache_reusecount[i])
1981               max_reuse = __mf_lookup_cache_reusecount[i];
1982           }
1983         fprintf (stderr, "lookup cache slots used: %u  unused: %u  peak-reuse: %u\n",
1984                  num_used, num_unused, max_reuse);
1985       }
1986
1987       {
1988         unsigned live_count;
1989         live_count = __mf_find_objects (MINPTR, MAXPTR, NULL, 0);
1990         fprintf (stderr, "number of live objects: %u\n", live_count);
1991       }
1992
1993       if (__mf_opts.persistent_count > 0)
1994         {
1995           unsigned dead_count = 0;
1996           unsigned row, plot;
1997           for (row = 0; row <= __MF_TYPE_MAX_CEM; row ++)
1998             for (plot = 0 ; plot < __mf_opts.persistent_count; plot ++)
1999               if (__mf_object_cemetary [row][plot] != 0)
2000                 dead_count ++;
2001           fprintf (stderr, "          zombie objects: %u\n", dead_count);
2002         }
2003     }
2004   if (__mf_opts.print_leaks && (__mf_opts.mudflap_mode == mode_check))
2005     {
2006       unsigned l;
2007       extern void * __mf_wrap_alloca_indirect (size_t c);
2008
2009       /* Free up any remaining alloca()'d blocks.  */
2010       __mf_wrap_alloca_indirect (0);
2011       __mf_describe_object (NULL); /* Reset description epoch.  */
2012       __mf_report_leaks (NULL); /* Reset cumulative count.  */
2013       l = __mf_report_leaks (__mf_object_root);
2014       fprintf (stderr, "number of leaked objects: %u\n", l);
2015     }
2016 }
2017
2018 /* __mf_backtrace */
2019
2020 size_t
2021 __mf_backtrace (char ***symbols, void *guess_pc, unsigned guess_omit_levels)
2022 {
2023   void ** pc_array;
2024   unsigned pc_array_size = __mf_opts.backtrace + guess_omit_levels;
2025   unsigned remaining_size;
2026   unsigned omitted_size = 0;
2027   unsigned i;
2028   DECLARE (void, free, void *ptr);
2029   DECLARE (void *, calloc, size_t c, size_t n);
2030   DECLARE (void *, malloc, size_t n);
2031
2032   pc_array = CALL_REAL (calloc, pc_array_size, sizeof (void *) );
2033 #ifdef HAVE_BACKTRACE
2034   pc_array_size = backtrace (pc_array, pc_array_size);
2035 #else
2036 #define FETCH(n) do { if (pc_array_size >= n) { \
2037                  pc_array[n] = __builtin_return_address(n); \
2038                  if (pc_array[n] == 0) pc_array_size = n; } } while (0)
2039
2040   /* Unroll some calls __builtin_return_address because this function
2041      only takes a literal integer parameter.  */
2042   FETCH (0);
2043 #if 0
2044   /* XXX: __builtin_return_address sometimes crashes (!) on >0 arguments,
2045      rather than simply returning 0.  :-(  */
2046   FETCH (1);
2047   FETCH (2);
2048   FETCH (3);
2049   FETCH (4);
2050   FETCH (5);
2051   FETCH (6);
2052   FETCH (7);
2053   FETCH (8);
2054   if (pc_array_size > 8) pc_array_size = 9;
2055 #else
2056   if (pc_array_size > 0) pc_array_size = 1;
2057 #endif
2058
2059 #undef FETCH
2060 #endif
2061
2062   /* We want to trim the first few levels of the stack traceback,
2063      since they contain libmudflap wrappers and junk.  If pc_array[]
2064      ends up containing a non-NULL guess_pc, then trim everything
2065      before that.  Otherwise, omit the first guess_omit_levels
2066      entries. */
2067
2068   if (guess_pc != NULL)
2069     for (i=0; i<pc_array_size; i++)
2070       if (pc_array [i] == guess_pc)
2071         omitted_size = i;
2072
2073   if (omitted_size == 0) /* No match? */
2074     if (pc_array_size > guess_omit_levels)
2075       omitted_size = guess_omit_levels;
2076
2077   remaining_size = pc_array_size - omitted_size;
2078
2079 #ifdef HAVE_BACKTRACE_SYMBOLS
2080   *symbols = backtrace_symbols (pc_array + omitted_size, remaining_size);
2081 #else
2082   {
2083     /* Let's construct a buffer by hand.  It will have <remaining_size>
2084        char*'s at the front, pointing at individual strings immediately
2085        afterwards.  */
2086     void *buffer;
2087     char *chars;
2088     char **pointers;
2089     enum { perline = 30 };
2090     buffer = CALL_REAL (malloc, remaining_size * (perline + sizeof(char *)));
2091     pointers = (char **) buffer;
2092     chars = (char *)buffer + (remaining_size * sizeof (char *));
2093     for (i = 0; i < remaining_size; i++)
2094       {
2095         pointers[i] = chars;
2096         sprintf (chars, "[0x%p]", pc_array [omitted_size + i]);
2097         chars = chars + perline;
2098       }
2099     *symbols = pointers;
2100   }
2101 #endif
2102   CALL_REAL (free, pc_array);
2103
2104   return remaining_size;
2105 }
2106
2107 /* ------------------------------------------------------------------------ */
2108 /* __mf_violation */
2109
2110 void
2111 __mf_violation (void *ptr, size_t sz, uintptr_t pc,
2112                 const char *location, int type)
2113 {
2114   char buf [128];
2115   static unsigned violation_number;
2116   DECLARE(void, free, void *ptr);
2117
2118   TRACE ("violation pc=%p location=%s type=%d ptr=%p size=%lu\n",
2119          (void *) pc,
2120          (location != NULL ? location : ""), type, ptr, (unsigned long) sz);
2121
2122   if (__mf_opts.collect_stats)
2123     __mf_count_violation [(type < 0) ? 0 :
2124                           (type > __MF_VIOL_WATCH) ? 0 :
2125                           type] ++;
2126
2127   /* Print out a basic warning message.  */
2128   if (__mf_opts.verbose_violations)
2129   {
2130     unsigned dead_p;
2131     unsigned num_helpful = 0;
2132     struct timeval now;
2133 #if HAVE_GETTIMEOFDAY
2134     gettimeofday (& now, NULL);
2135 #endif
2136
2137     violation_number ++;
2138     fprintf (stderr,
2139              "*******\n"
2140              "mudflap violation %u (%s): time=%lu.%06lu "
2141              "ptr=%p size=%lu\npc=%p%s%s%s\n",
2142              violation_number,
2143              ((type == __MF_VIOL_READ) ? "check/read" :
2144               (type == __MF_VIOL_WRITE) ? "check/write" :
2145               (type == __MF_VIOL_REGISTER) ? "register" :
2146               (type == __MF_VIOL_UNREGISTER) ? "unregister" :
2147               (type == __MF_VIOL_WATCH) ? "watch" : "unknown"),
2148              now.tv_sec, now.tv_usec,
2149              (void *) ptr, (unsigned long)sz, (void *) pc,
2150              (location != NULL ? " location=`" : ""),
2151              (location != NULL ? location : ""),
2152              (location != NULL ? "'" : ""));
2153
2154     if (__mf_opts.backtrace > 0)
2155       {
2156         char ** symbols;
2157         unsigned i, num;
2158
2159         num = __mf_backtrace (& symbols, (void *) pc, 2);
2160         /* Note: backtrace_symbols calls malloc().  But since we're in
2161            __mf_violation and presumably __mf_check, it'll detect
2162            recursion, and not put the new string into the database.  */
2163
2164         for (i=0; i<num; i++)
2165           fprintf (stderr, "      %s\n", symbols[i]);
2166
2167         /* Calling free() here would trigger a violation.  */
2168         CALL_REAL(free, symbols);
2169       }
2170
2171
2172     /* Look for nearby objects.  For this, we start with s_low/s_high
2173        pointing to the given area, looking for overlapping objects.
2174        If none show up, widen the search area and keep looking. */
2175
2176     if (sz == 0) sz = 1;
2177
2178     for (dead_p = 0; dead_p <= 1; dead_p ++) /* for dead_p in 0 1 */
2179       {
2180         enum {max_objs = 3}; /* magic */
2181         __mf_object_tree_t *objs[max_objs];
2182         unsigned num_objs = 0;
2183         uintptr_t s_low, s_high;
2184         unsigned tries = 0;
2185         unsigned i;
2186
2187         s_low = (uintptr_t) ptr;
2188         s_high = CLAMPSZ (ptr, sz);
2189
2190         while (tries < 16) /* magic */
2191           {
2192             if (dead_p)
2193               num_objs = __mf_find_dead_objects (s_low, s_high, objs, max_objs);
2194             else
2195               num_objs = __mf_find_objects (s_low, s_high, objs, max_objs);
2196
2197             if (num_objs) /* good enough */
2198               break;
2199
2200             tries ++;
2201
2202             /* XXX: tune this search strategy.  It's too dependent on
2203              sz, which can vary from 1 to very big (when array index
2204              checking) numbers. */
2205             s_low = CLAMPSUB (s_low, (sz * tries * tries));
2206             s_high = CLAMPADD (s_high, (sz * tries * tries));
2207           }
2208
2209         for (i = 0; i < min (num_objs, max_objs); i++)
2210           {
2211             __mf_object_t *obj = & objs[i]->data;
2212             uintptr_t low = (uintptr_t) ptr;
2213             uintptr_t high = CLAMPSZ (ptr, sz);
2214             unsigned before1 = (low < obj->low) ? obj->low - low : 0;
2215             unsigned after1 = (low > obj->high) ? low - obj->high : 0;
2216             unsigned into1 = (high >= obj->low && low <= obj->high) ? low - obj->low : 0;
2217             unsigned before2 = (high < obj->low) ? obj->low - high : 0;
2218             unsigned after2 = (high > obj->high) ? high - obj->high : 0;
2219             unsigned into2 = (high >= obj->low && low <= obj->high) ? high - obj->low : 0;
2220
2221             fprintf (stderr, "Nearby object %u: checked region begins %uB %s and ends %uB %s\n",
2222                      num_helpful + i + 1,
2223                      (before1 ? before1 : after1 ? after1 : into1),
2224                      (before1 ? "before" : after1 ? "after" : "into"),
2225                      (before2 ? before2 : after2 ? after2 : into2),
2226                      (before2 ? "before" : after2 ? "after" : "into"));
2227             __mf_describe_object (obj);
2228           }
2229         num_helpful += num_objs;
2230       }
2231
2232     fprintf (stderr, "number of nearby objects: %u\n", num_helpful);
2233   }
2234
2235   /* How to finally handle this violation?  */
2236   switch (__mf_opts.violation_mode)
2237     {
2238     case viol_nop:
2239       break;
2240     case viol_segv:
2241       kill (getpid(), SIGSEGV);
2242       break;
2243     case viol_abort:
2244       abort ();
2245       break;
2246     case viol_gdb:
2247       snprintf (buf, 128, "gdb --pid=%d", getpid ());
2248       system (buf);
2249       /* XXX: should probably fork() && sleep(GDB_WAIT_PARAMETER)
2250       instead, and let the forked child execlp() gdb.  That way, this
2251       subject process can be resumed under the supervision of gdb.
2252       This can't happen now, since system() only returns when gdb
2253       dies.  In that case, we need to beware of starting a second
2254       concurrent gdb child upon the next violation.  (But if the first
2255       gdb dies, then starting a new one is appropriate.)  */
2256       break;
2257     }
2258 }
2259
2260 /* ------------------------------------------------------------------------ */
2261
2262
2263 unsigned __mf_watch (void *ptr, size_t sz)
2264 {
2265   unsigned rc;
2266   LOCKTH ();
2267   BEGIN_RECURSION_PROTECT ();
2268   rc = __mf_watch_or_not (ptr, sz, 1);
2269   END_RECURSION_PROTECT ();
2270   UNLOCKTH ();
2271   return rc;
2272 }
2273
2274 unsigned __mf_unwatch (void *ptr, size_t sz)
2275 {
2276   unsigned rc;
2277   LOCKTH ();
2278   rc = __mf_watch_or_not (ptr, sz, 0);
2279   UNLOCKTH ();
2280   return rc;
2281 }
2282
2283
2284 static unsigned
2285 __mf_watch_or_not (void *ptr, size_t sz, char flag)
2286 {
2287   uintptr_t ptr_high = CLAMPSZ (ptr, sz);
2288   uintptr_t ptr_low = (uintptr_t) ptr;
2289   unsigned count = 0;
2290
2291   TRACE ("%s ptr=%p size=%lu\n",
2292          (flag ? "watch" : "unwatch"), ptr, (unsigned long) sz);
2293
2294   switch (__mf_opts.mudflap_mode)
2295     {
2296     case mode_nop:
2297     case mode_populate:
2298     case mode_violate:
2299       count = 0;
2300       break;
2301
2302     case mode_check:
2303       {
2304         __mf_object_tree_t **all_ovr_objs;
2305         unsigned obj_count;
2306         unsigned n;
2307         DECLARE (void *, malloc, size_t c);
2308         DECLARE (void, free, void *p);
2309
2310         obj_count = __mf_find_objects (ptr_low, ptr_high, NULL, 0);
2311         VERBOSE_TRACE (" %u:", obj_count);
2312
2313         all_ovr_objs = CALL_REAL (malloc, (sizeof (__mf_object_tree_t *) *
2314                                            obj_count));
2315         if (all_ovr_objs == NULL) abort ();
2316         n = __mf_find_objects (ptr_low, ptr_high, all_ovr_objs, obj_count);
2317         assert (n == obj_count);
2318
2319         for (n = 0; n < obj_count; n ++)
2320           {
2321             __mf_object_t *obj = & (all_ovr_objs[n]->data);
2322
2323             VERBOSE_TRACE (" [%p]", (void *) obj);
2324             if (obj->watching_p != flag)
2325               {
2326                 obj->watching_p = flag;
2327                 count ++;
2328
2329                 /* Remove object from cache, to ensure next access
2330                    goes through __mf_check().  */
2331                 if (flag)
2332                   __mf_uncache_object (obj);
2333               }
2334           }
2335         CALL_REAL (free, all_ovr_objs);
2336       }
2337       break;
2338     }
2339
2340   return count;
2341 }
2342
2343
2344 void
2345 __mf_sigusr1_handler (int num)
2346 {
2347   __mf_sigusr1_received ++;
2348 }
2349
2350 /* Install or remove SIGUSR1 handler as necessary.
2351    Also, respond to a received pending SIGUSR1.  */
2352 void
2353 __mf_sigusr1_respond ()
2354 {
2355   static int handler_installed;
2356
2357 #ifdef SIGUSR1
2358   /* Manage handler */
2359   if (__mf_opts.sigusr1_report && ! handler_installed)
2360     {
2361       signal (SIGUSR1, __mf_sigusr1_handler);
2362       handler_installed = 1;
2363     }
2364   else if(! __mf_opts.sigusr1_report && handler_installed)
2365     {
2366       signal (SIGUSR1, SIG_DFL);
2367       handler_installed = 0;
2368     }
2369 #endif
2370
2371   /* Manage enqueued signals */
2372   if (__mf_sigusr1_received > __mf_sigusr1_handled)
2373     {
2374       __mf_sigusr1_handled ++;
2375       assert (__mf_state == reentrant);
2376       __mfu_report ();
2377       handler_installed = 0; /* We may need to re-enable signal; this might be a SysV library. */
2378     }
2379 }
2380
2381
2382 /* XXX: provide an alternative __assert_fail function that cannot
2383    fail due to libmudflap infinite recursion.  */
2384 #ifndef NDEBUG
2385
2386 static void
2387 write_itoa (int fd, unsigned n)
2388 {
2389   enum x { bufsize = sizeof(n)*4 };
2390   char buf [bufsize];
2391   unsigned i;
2392
2393   for (i=0; i<bufsize-1; i++)
2394     {
2395       unsigned digit = n % 10;
2396       buf[bufsize-2-i] = digit + '0';
2397       n /= 10;
2398       if (n == 0)
2399         {
2400           char *m = & buf [bufsize-2-i];
2401           buf[bufsize-1] = '\0';
2402           write (fd, m, strlen(m));
2403           break;
2404         }
2405     }
2406 }
2407
2408
2409 void
2410 __assert_fail (const char *msg, const char *file, unsigned line, const char *func)
2411 {
2412 #define write2(string) write (2, (string), strlen ((string)));
2413   write2("mf");
2414 #ifdef LIBMUDFLAPTH
2415   write2("(");
2416   write_itoa (2, (unsigned) pthread_self ());
2417   write2(")");
2418 #endif
2419   write2(": assertion failure: `");
2420   write (2, msg, strlen (msg));
2421   write2("' in ");
2422   write (2, func, strlen (func));
2423   write2(" at ");
2424   write (2, file, strlen (file));
2425   write2(":");
2426   write_itoa (2, line);
2427   write2("\n");
2428 #undef write2
2429   abort ();
2430 }
2431
2432
2433 #endif