libmudflap/mf-runtime.c

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