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