OSDN Git Service

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