OSDN Git Service

* config/m68k/m68k.c (TARGET_TRAMPOLINE_INIT): New.
[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 #if defined(__FreeBSD__) && defined(LIBMUDFLAPTH)
699   pthread_self();
700   LOCKTH ();
701   UNLOCKTH ();
702 #endif /* Prime mutex which calls calloc upon first lock to avoid deadlock. */
703
704   /* This initial bootstrap phase requires that __mf_starting_p = 1. */
705 #ifdef PIC
706   __mf_resolve_dynamics ();
707 #endif
708   __mf_starting_p = 0;
709
710   __mf_set_state (active);
711
712   __mf_set_default_options ();
713
714   ov = getenv ("MUDFLAP_OPTIONS");
715   if (ov)
716     {
717       int rc = __mfu_set_options (ov);
718       if (rc < 0)
719         {
720           __mf_usage ();
721           exit (1);
722         }
723     }
724
725   /* Initialize to a non-zero description epoch. */
726   __mf_describe_object (NULL);
727
728 #define REG_RESERVED(obj) \
729   __mf_register (& obj, sizeof(obj), __MF_TYPE_NOACCESS, # obj)
730
731   REG_RESERVED (__mf_lookup_cache);
732   REG_RESERVED (__mf_lc_mask);
733   REG_RESERVED (__mf_lc_shift);
734   /* XXX: others of our statics?  */
735
736   /* Prevent access to *NULL. */
737   __mf_register (MINPTR, 1, __MF_TYPE_NOACCESS, "NULL");
738   __mf_lookup_cache[0].low = (uintptr_t) -1;
739 }
740
741
742
743 int
744 __wrap_main (int argc, char* argv[])
745 {
746   extern char **environ;
747   extern int main ();
748   extern int __real_main ();
749   static int been_here = 0;
750
751   if (__mf_opts.heur_std_data && ! been_here)
752     {
753       unsigned i;
754
755       been_here = 1;
756       __mf_register (argv, sizeof(char *)*(argc+1), __MF_TYPE_STATIC, "argv[]");
757       for (i=0; i<argc; i++)
758         {
759           unsigned j = strlen (argv[i]);
760           __mf_register (argv[i], j+1, __MF_TYPE_STATIC, "argv element");
761         }
762
763       for (i=0; ; i++)
764         {
765           char *e = environ[i];
766           unsigned j;
767           if (e == NULL) break;
768           j = strlen (environ[i]);
769           __mf_register (environ[i], j+1, __MF_TYPE_STATIC, "environ element");
770         }
771       __mf_register (environ, sizeof(char *)*(i+1), __MF_TYPE_STATIC, "environ[]");
772
773       __mf_register (& errno, sizeof (errno), __MF_TYPE_STATIC, "errno area");
774
775       __mf_register (stdin,  sizeof (*stdin),  __MF_TYPE_STATIC, "stdin");
776       __mf_register (stdout, sizeof (*stdout), __MF_TYPE_STATIC, "stdout");
777       __mf_register (stderr, sizeof (*stderr), __MF_TYPE_STATIC, "stderr");
778
779       /* Make some effort to register ctype.h static arrays.  */
780       /* XXX: e.g., on Solaris, may need to register __ctype, _ctype, __ctype_mask, __toupper, etc. */
781       /* On modern Linux GLIBC, these are thread-specific and changeable, and are dealt
782          with in mf-hooks2.c.  */
783     }
784
785 #ifdef PIC
786   return main (argc, argv, environ);
787 #else
788   return __real_main (argc, argv, environ);
789 #endif
790 }
791
792
793
794 extern void __mf_fini () DTOR;
795 void __mf_fini ()
796 {
797   TRACE ("__mf_fini\n");
798   __mfu_report ();
799
800 #ifndef PIC
801 /* Since we didn't populate the tree for allocations in constructors
802    before __mf_init, we cannot check destructors after __mf_fini.  */
803   __mf_opts.mudflap_mode = mode_nop;
804 #endif
805 }
806
807
808
809 /* ------------------------------------------------------------------------ */
810 /* __mf_check */
811
812 void __mf_check (void *ptr, size_t sz, int type, const char *location)
813 {
814   LOCKTH ();
815   BEGIN_RECURSION_PROTECT ();
816   __mfu_check (ptr, sz, type, location);
817   END_RECURSION_PROTECT ();
818   UNLOCKTH ();
819 }
820
821
822 void __mfu_check (void *ptr, size_t sz, int type, const char *location)
823 {
824   unsigned entry_idx = __MF_CACHE_INDEX (ptr);
825   struct __mf_cache *entry = & __mf_lookup_cache [entry_idx];
826   int judgement = 0; /* 0=undecided; <0=violation; >0=okay */
827   uintptr_t ptr_low = (uintptr_t) ptr;
828   uintptr_t ptr_high = CLAMPSZ (ptr, sz);
829   struct __mf_cache old_entry = *entry;
830
831   if (UNLIKELY (__mf_opts.sigusr1_report))
832     __mf_sigusr1_respond ();
833   if (UNLIKELY (__mf_opts.ignore_reads && type == 0))
834     return;
835
836   TRACE ("check ptr=%p b=%u size=%lu %s location=`%s'\n",
837          ptr, entry_idx, (unsigned long)sz,
838          (type == 0 ? "read" : "write"), location);
839
840   switch (__mf_opts.mudflap_mode)
841     {
842     case mode_nop:
843       /* It is tempting to poison the cache here similarly to
844          mode_populate.  However that eliminates a valuable
845          distinction between these two modes.  mode_nop is useful to
846          let a user count & trace every single check / registration
847          call.  mode_populate is useful to let a program run fast
848          while unchecked.
849       */
850       judgement = 1;
851       break;
852
853     case mode_populate:
854       entry->low = ptr_low;
855       entry->high = ptr_high;
856       judgement = 1;
857       break;
858
859     case mode_check:
860       {
861         unsigned heuristics = 0;
862
863         /* Advance aging/adaptation counters.  */
864         static unsigned adapt_count;
865         adapt_count ++;
866         if (UNLIKELY (__mf_opts.adapt_cache > 0 &&
867                       adapt_count > __mf_opts.adapt_cache))
868           {
869             adapt_count = 0;
870             __mf_adapt_cache ();
871           }
872
873         /* Looping only occurs if heuristics were triggered.  */
874         while (judgement == 0)
875           {
876             DECLARE (void, free, void *p);
877             __mf_object_t* ovr_obj[1];
878             unsigned obj_count;
879             __mf_object_t** all_ovr_obj = NULL;
880             __mf_object_t** dealloc_me = NULL;
881             unsigned i;
882
883             /* Find all overlapping objects.  Be optimistic that there is just one.  */
884             obj_count = __mf_find_objects (ptr_low, ptr_high, ovr_obj, 1);
885             if (UNLIKELY (obj_count > 1))
886               {
887                 /* Allocate a real buffer and do the search again.  */
888                 DECLARE (void *, malloc, size_t c);
889                 unsigned n;
890                 all_ovr_obj = CALL_REAL (malloc, (sizeof (__mf_object_t *) *
891                                                    obj_count));
892                 if (all_ovr_obj == NULL) abort ();
893                 n = __mf_find_objects (ptr_low, ptr_high, all_ovr_obj, obj_count);
894                 assert (n == obj_count);
895                 dealloc_me = all_ovr_obj;
896               }
897             else
898               {
899                 all_ovr_obj = ovr_obj;
900                 dealloc_me = NULL;
901               }
902
903             /* Update object statistics.  */
904             for (i = 0; i < obj_count; i++)
905               {
906                 __mf_object_t *obj = all_ovr_obj[i];
907                 assert (obj != NULL);
908                 if (type == __MF_CHECK_READ)
909                   obj->read_count ++;
910                 else
911                   obj->write_count ++;
912                 obj->liveness ++;
913               }
914
915             /* Iterate over the various objects.  There are a number of special cases.  */
916             for (i = 0; i < obj_count; i++)
917               {
918                   __mf_object_t *obj = all_ovr_obj[i];
919
920                 /* Any __MF_TYPE_NOACCESS hit is bad.  */
921                 if (UNLIKELY (obj->type == __MF_TYPE_NOACCESS))
922                   judgement = -1;
923
924                 /* Any object with a watch flag is bad.  */
925                 if (UNLIKELY (obj->watching_p))
926                   judgement = -2; /* trigger VIOL_WATCH */
927
928                 /* A read from an uninitialized object is bad. */
929                 if (UNLIKELY (__mf_opts.check_initialization
930                               /* reading */
931                               && type == __MF_CHECK_READ
932                               /* not written */
933                               && obj->write_count == 0
934                               /* uninitialized (heap) */
935                               && obj->type == __MF_TYPE_HEAP))
936                   judgement = -1;
937               }
938
939             /* We now know that the access spans no invalid objects.  */
940             if (LIKELY (judgement >= 0))
941               for (i = 0; i < obj_count; i++)
942                 {
943                   __mf_object_t *obj = all_ovr_obj[i];
944
945                   /* Is this access entirely contained within this object?  */
946                   if (LIKELY (ptr_low >= obj->low && ptr_high <= obj->high))
947                     {
948                       /* Valid access.  */
949                       entry->low = obj->low;
950                       entry->high = obj->high;
951                       judgement = 1;
952                     }
953                 }
954
955             /* This access runs off the end of one valid object.  That
956                 could be okay, if other valid objects fill in all the
957                 holes.  We allow this only for HEAP and GUESS type
958                 objects.  Accesses to STATIC and STACK variables
959                 should not be allowed to span.  */
960             if (UNLIKELY ((judgement == 0) && (obj_count > 1)))
961               {
962                 unsigned uncovered = 0;
963                 for (i = 0; i < obj_count; i++)
964                   {
965                     __mf_object_t *obj = all_ovr_obj[i];
966                     int j, uncovered_low_p, uncovered_high_p;
967                     uintptr_t ptr_lower, ptr_higher;
968
969                     uncovered_low_p = ptr_low < obj->low;
970                     ptr_lower = CLAMPSUB (obj->low, 1);
971                     uncovered_high_p = ptr_high > obj->high;
972                     ptr_higher = CLAMPADD (obj->high, 1);
973
974                     for (j = 0; j < obj_count; j++)
975                       {
976                         __mf_object_t *obj2 = all_ovr_obj[j];
977
978                         if (i == j) continue;
979
980                         /* Filter out objects that cannot be spanned across.  */
981                         if (obj2->type == __MF_TYPE_STACK
982                             || obj2->type == __MF_TYPE_STATIC)
983                           continue;
984
985                           /* Consider a side "covered" if obj2 includes
986                              the next byte on that side.  */
987                           if (uncovered_low_p
988                               && (ptr_lower >= obj2->low && ptr_lower <= obj2->high))
989                             uncovered_low_p = 0;
990                           if (uncovered_high_p
991                               && (ptr_high >= obj2->low && ptr_higher <= obj2->high))
992                             uncovered_high_p = 0;
993                       }
994
995                     if (uncovered_low_p || uncovered_high_p)
996                       uncovered ++;
997                   }
998
999                 /* Success if no overlapping objects are uncovered.  */
1000                 if (uncovered == 0)
1001                   judgement = 1;
1002                 }
1003
1004
1005             if (dealloc_me != NULL)
1006               CALL_REAL (free, dealloc_me);
1007
1008             /* If the judgment is still unknown at this stage, loop
1009                around at most one more time.  */
1010             if (judgement == 0)
1011               {
1012                 if (heuristics++ < 2) /* XXX parametrize this number? */
1013                   judgement = __mf_heuristic_check (ptr_low, ptr_high);
1014                 else
1015                   judgement = -1;
1016               }
1017           }
1018
1019       }
1020       break;
1021
1022     case mode_violate:
1023       judgement = -1;
1024       break;
1025     }
1026
1027   if (__mf_opts.collect_stats)
1028     {
1029       __mf_count_check ++;
1030
1031       if (LIKELY (old_entry.low != entry->low || old_entry.high != entry->high))
1032         /* && (old_entry.low != 0) && (old_entry.high != 0)) */
1033         __mf_lookup_cache_reusecount [entry_idx] ++;
1034     }
1035
1036   if (UNLIKELY (judgement < 0))
1037     __mf_violation (ptr, sz,
1038                     (uintptr_t) __builtin_return_address (0), location,
1039                     ((judgement == -1) ?
1040                      (type == __MF_CHECK_READ ? __MF_VIOL_READ : __MF_VIOL_WRITE) :
1041                      __MF_VIOL_WATCH));
1042 }
1043
1044
1045 static __mf_object_t *
1046 __mf_insert_new_object (uintptr_t low, uintptr_t high, int type,
1047                         const char *name, uintptr_t pc)
1048 {
1049   DECLARE (void *, calloc, size_t c, size_t n);
1050
1051   __mf_object_t *new_obj;
1052   new_obj = CALL_REAL (calloc, 1, sizeof(__mf_object_t));
1053   new_obj->low = low;
1054   new_obj->high = high;
1055   new_obj->type = type;
1056   new_obj->name = name;
1057   new_obj->alloc_pc = pc;
1058 #if HAVE_GETTIMEOFDAY
1059   if (__mf_opts.timestamps)
1060     gettimeofday (& new_obj->alloc_time, NULL);
1061 #endif
1062 #if LIBMUDFLAPTH
1063   new_obj->alloc_thread = pthread_self ();
1064 #endif
1065
1066   if (__mf_opts.backtrace > 0 && (type == __MF_TYPE_HEAP || type == __MF_TYPE_HEAP_I))
1067     new_obj->alloc_backtrace_size =
1068       __mf_backtrace (& new_obj->alloc_backtrace,
1069                       (void *) pc, 2);
1070
1071   __mf_link_object (new_obj);
1072   return new_obj;
1073 }
1074
1075
1076 static void
1077 __mf_uncache_object (__mf_object_t *old_obj)
1078 {
1079   /* Remove any low/high pointers for this object from the lookup cache.  */
1080
1081   /* Can it possibly exist in the cache?  */
1082   if (LIKELY (old_obj->read_count + old_obj->write_count))
1083     {
1084       uintptr_t low = old_obj->low;
1085       uintptr_t high = old_obj->high;
1086       struct __mf_cache *entry;
1087       unsigned i;
1088       if ((high - low) >= (__mf_lc_mask << __mf_lc_shift))
1089         {
1090           /* For large objects (>= cache size - 1) check the whole cache.  */
1091           entry = & __mf_lookup_cache [0];
1092           for (i = 0; i <= __mf_lc_mask; i++, entry++)
1093             {
1094               /* NB: the "||" in the following test permits this code to
1095                  tolerate the situation introduced by __mf_check over
1096                  contiguous objects, where a cache entry spans several
1097                  objects.  */
1098               if (entry->low == low || entry->high == high)
1099                 {
1100                   entry->low = MAXPTR;
1101                   entry->high = MINPTR;
1102                 }
1103             }
1104         }
1105       else
1106         {
1107           /* Object is now smaller then cache size.  */
1108           unsigned entry_low_idx = __MF_CACHE_INDEX (low);
1109           unsigned entry_high_idx = __MF_CACHE_INDEX (high);
1110           if (entry_low_idx <= entry_high_idx)
1111             {
1112               entry = & __mf_lookup_cache [entry_low_idx];
1113               for (i = entry_low_idx; i <= entry_high_idx; i++, entry++)
1114                 {
1115                   /* NB: the "||" in the following test permits this code to
1116                      tolerate the situation introduced by __mf_check over
1117                      contiguous objects, where a cache entry spans several
1118                      objects.  */
1119                   if (entry->low == low || entry->high == high)
1120                     {
1121                       entry->low = MAXPTR;
1122                       entry->high = MINPTR;
1123                     }
1124                 }
1125             }
1126           else
1127             {
1128               /* Object wrapped around the end of the cache. First search
1129                  from low to end of cache and then from 0 to high.  */
1130               entry = & __mf_lookup_cache [entry_low_idx];
1131               for (i = entry_low_idx; i <= __mf_lc_mask; i++, entry++)
1132                 {
1133                   /* NB: the "||" in the following test permits this code to
1134                      tolerate the situation introduced by __mf_check over
1135                      contiguous objects, where a cache entry spans several
1136                      objects.  */
1137                   if (entry->low == low || entry->high == high)
1138                     {
1139                       entry->low = MAXPTR;
1140                       entry->high = MINPTR;
1141                     }
1142                 }
1143               entry = & __mf_lookup_cache [0];
1144               for (i = 0; i <= entry_high_idx; i++, entry++)
1145                 {
1146                   /* NB: the "||" in the following test permits this code to
1147                      tolerate the situation introduced by __mf_check over
1148                      contiguous objects, where a cache entry spans several
1149                      objects.  */
1150                   if (entry->low == low || entry->high == high)
1151                     {
1152                       entry->low = MAXPTR;
1153                       entry->high = MINPTR;
1154                     }
1155                 }
1156             }
1157         }
1158     }
1159 }
1160
1161
1162 void
1163 __mf_register (void *ptr, size_t sz, int type, const char *name)
1164 {
1165   LOCKTH ();
1166   BEGIN_RECURSION_PROTECT ();
1167   __mfu_register (ptr, sz, type, name);
1168   END_RECURSION_PROTECT ();
1169   UNLOCKTH ();
1170 }
1171
1172
1173 void
1174 __mfu_register (void *ptr, size_t sz, int type, const char *name)
1175 {
1176   TRACE ("register ptr=%p size=%lu type=%x name='%s'\n",
1177          ptr, (unsigned long) sz, type, name ? name : "");
1178
1179   if (__mf_opts.collect_stats)
1180     {
1181       __mf_count_register ++;
1182       __mf_total_register_size [(type < 0) ? 0 :
1183                                 (type > __MF_TYPE_MAX) ? 0 :
1184                                 type] += sz;
1185     }
1186
1187   if (UNLIKELY (__mf_opts.sigusr1_report))
1188     __mf_sigusr1_respond ();
1189
1190   switch (__mf_opts.mudflap_mode)
1191     {
1192     case mode_nop:
1193       break;
1194
1195     case mode_violate:
1196       __mf_violation (ptr, sz, (uintptr_t) __builtin_return_address (0), NULL,
1197                       __MF_VIOL_REGISTER);
1198       break;
1199
1200     case mode_populate:
1201       /* Clear the cache.  */
1202       /* XXX: why the entire cache? */
1203       /* XXX: race */
1204       memset (__mf_lookup_cache, 0, sizeof(__mf_lookup_cache));
1205       /* void slot 0 */
1206       __mf_lookup_cache[0].low = MAXPTR;
1207       break;
1208
1209     case mode_check:
1210       {
1211         __mf_object_t *ovr_objs [1];
1212         unsigned num_overlapping_objs;
1213         uintptr_t low = (uintptr_t) ptr;
1214         uintptr_t high = CLAMPSZ (ptr, sz);
1215         uintptr_t pc = (uintptr_t) __builtin_return_address (0);
1216
1217         /* Treat unknown size indication as 1.  */
1218         if (UNLIKELY (sz == 0)) sz = 1;
1219
1220         /* Look for objects only of the same type.  This will e.g. permit a registration
1221            of a STATIC overlapping with a GUESS, and a HEAP with a NOACCESS.  At
1222            __mf_check time however harmful overlaps will be detected. */
1223         num_overlapping_objs = __mf_find_objects2 (low, high, ovr_objs, 1, type);
1224
1225         /* Handle overlaps.  */
1226         if (UNLIKELY (num_overlapping_objs > 0))
1227           {
1228             __mf_object_t *ovr_obj = ovr_objs[0];
1229
1230             /* Accept certain specific duplication pairs.  */
1231             if (((type == __MF_TYPE_STATIC) || (type == __MF_TYPE_GUESS))
1232                 && ovr_obj->low == low
1233                 && ovr_obj->high == high
1234                 && ovr_obj->type == type)
1235               {
1236                 /* Duplicate registration for static objects may come
1237                    from distinct compilation units.  */
1238                 VERBOSE_TRACE ("harmless duplicate reg %p-%p `%s'\n",
1239                                (void *) low, (void *) high,
1240                                (ovr_obj->name ? ovr_obj->name : ""));
1241                 break;
1242               }
1243
1244             /* Alas, a genuine violation.  */
1245             else
1246               {
1247                 /* Two or more *real* mappings here. */
1248                 __mf_violation ((void *) ptr, sz,
1249                                 (uintptr_t) __builtin_return_address (0), NULL,
1250                                 __MF_VIOL_REGISTER);
1251               }
1252           }
1253         else /* No overlapping objects: AOK.  */
1254           __mf_insert_new_object (low, high, type, name, pc);
1255
1256         /* We could conceivably call __mf_check() here to prime the cache,
1257            but then the read_count/write_count field is not reliable.  */
1258         break;
1259       }
1260     } /* end switch (__mf_opts.mudflap_mode) */
1261 }
1262
1263
1264 void
1265 __mf_unregister (void *ptr, size_t sz, int type)
1266 {
1267   LOCKTH ();
1268   BEGIN_RECURSION_PROTECT ();
1269   __mfu_unregister (ptr, sz, type);
1270   END_RECURSION_PROTECT ();
1271   UNLOCKTH ();
1272 }
1273
1274
1275 void
1276 __mfu_unregister (void *ptr, size_t sz, int type)
1277 {
1278   DECLARE (void, free, void *ptr);
1279
1280   if (UNLIKELY (__mf_opts.sigusr1_report))
1281     __mf_sigusr1_respond ();
1282
1283   TRACE ("unregister ptr=%p size=%lu type=%x\n", ptr, (unsigned long) sz, type);
1284
1285   switch (__mf_opts.mudflap_mode)
1286     {
1287     case mode_nop:
1288       break;
1289
1290     case mode_violate:
1291       __mf_violation (ptr, sz,
1292                       (uintptr_t) __builtin_return_address (0), NULL,
1293                       __MF_VIOL_UNREGISTER);
1294       break;
1295
1296     case mode_populate:
1297       /* Clear the cache.  */
1298       /* XXX: race */
1299       memset (__mf_lookup_cache, 0, sizeof(__mf_lookup_cache));
1300       /* void slot 0 */
1301       __mf_lookup_cache[0].low = MAXPTR;
1302       break;
1303
1304     case mode_check:
1305       {
1306         __mf_object_t *old_obj = NULL;
1307         __mf_object_t *del_obj = NULL;  /* Object to actually delete. */
1308         __mf_object_t *objs[1] = {NULL};
1309         unsigned num_overlapping_objs;
1310
1311         num_overlapping_objs = __mf_find_objects2 ((uintptr_t) ptr,
1312                                                    CLAMPSZ (ptr, sz), objs, 1, type);
1313
1314         /* Special case for HEAP_I - see free & realloc hook.  They don't
1315            know whether the input region was HEAP or HEAP_I before
1316            unmapping it.  Here we give HEAP a try in case HEAP_I
1317            failed.  */
1318         if ((type == __MF_TYPE_HEAP_I) && (num_overlapping_objs == 0))
1319           {
1320             num_overlapping_objs = __mf_find_objects2 ((uintptr_t) ptr,
1321                                                        CLAMPSZ (ptr, sz), objs, 1, __MF_TYPE_HEAP);
1322           }
1323
1324         old_obj = objs[0];
1325         if (UNLIKELY ((num_overlapping_objs != 1) /* more than one overlap */
1326                       || ((sz == 0) ? 0 : (sz != (old_obj->high - old_obj->low + 1))) /* size mismatch */
1327                       || ((uintptr_t) ptr != old_obj->low))) /* base mismatch */
1328           {
1329             __mf_violation (ptr, sz,
1330                             (uintptr_t) __builtin_return_address (0), NULL,
1331                             __MF_VIOL_UNREGISTER);
1332             break;
1333           }
1334
1335         __mf_unlink_object (old_obj);
1336         __mf_uncache_object (old_obj);
1337
1338         /* Wipe buffer contents if desired.  */
1339         if ((__mf_opts.wipe_stack && old_obj->type == __MF_TYPE_STACK)
1340             || (__mf_opts.wipe_heap && (old_obj->type == __MF_TYPE_HEAP
1341                                         || old_obj->type == __MF_TYPE_HEAP_I)))
1342           {
1343             memset ((void *) old_obj->low,
1344                     0,
1345                     (size_t) (old_obj->high - old_obj->low + 1));
1346           }
1347
1348         /* Manage the object cemetary.  */
1349         if (__mf_opts.persistent_count > 0
1350             && (unsigned) old_obj->type <= __MF_TYPE_MAX_CEM)
1351           {
1352             old_obj->deallocated_p = 1;
1353             old_obj->dealloc_pc = (uintptr_t) __builtin_return_address (0);
1354 #if HAVE_GETTIMEOFDAY
1355             if (__mf_opts.timestamps)
1356               gettimeofday (& old_obj->dealloc_time, NULL);
1357 #endif
1358 #ifdef LIBMUDFLAPTH
1359             old_obj->dealloc_thread = pthread_self ();
1360 #endif
1361
1362             if (__mf_opts.backtrace > 0 && old_obj->type == __MF_TYPE_HEAP)
1363               old_obj->dealloc_backtrace_size =
1364                 __mf_backtrace (& old_obj->dealloc_backtrace,
1365                                 NULL, 2);
1366
1367             /* Encourage this object to be displayed again in current epoch.  */
1368             old_obj->description_epoch --;
1369
1370             /* Put this object into the cemetary.  This may require this plot to
1371                be recycled, and the previous resident to be designated del_obj.  */
1372             {
1373               unsigned row = old_obj->type;
1374               unsigned plot = __mf_object_dead_head [row];
1375
1376               del_obj = __mf_object_cemetary [row][plot];
1377               __mf_object_cemetary [row][plot] = old_obj;
1378               plot ++;
1379               if (plot == __mf_opts.persistent_count) plot = 0;
1380               __mf_object_dead_head [row] = plot;
1381             }
1382           }
1383         else
1384           del_obj = old_obj;
1385
1386         if (__mf_opts.print_leaks)
1387           {
1388             if ((old_obj->read_count + old_obj->write_count) == 0 &&
1389                 (old_obj->type == __MF_TYPE_HEAP
1390                  || old_obj->type == __MF_TYPE_HEAP_I))
1391               {
1392                 /* The problem with a warning message here is that we may not
1393                    be privy to accesses to such objects that occur within
1394                    uninstrumented libraries.  */
1395 #if 0
1396                 fprintf (stderr,
1397                          "*******\n"
1398                          "mudflap warning: unaccessed registered object:\n");
1399                 __mf_describe_object (old_obj);
1400 #endif
1401               }
1402           }
1403
1404         if (del_obj != NULL) /* May or may not equal old_obj.  */
1405           {
1406             if (__mf_opts.backtrace > 0)
1407               {
1408                 CALL_REAL(free, del_obj->alloc_backtrace);
1409                 if (__mf_opts.persistent_count > 0)
1410                   {
1411                     CALL_REAL(free, del_obj->dealloc_backtrace);
1412                   }
1413               }
1414             CALL_REAL(free, del_obj);
1415           }
1416
1417         break;
1418       }
1419     } /* end switch (__mf_opts.mudflap_mode) */
1420
1421
1422   if (__mf_opts.collect_stats)
1423     {
1424       __mf_count_unregister ++;
1425       __mf_total_unregister_size += sz;
1426     }
1427 }
1428
1429
1430
1431 struct tree_stats
1432 {
1433   unsigned obj_count;
1434   unsigned long total_size;
1435   unsigned live_obj_count;
1436   double total_weight;
1437   double weighted_size;
1438   unsigned long weighted_address_bits [sizeof (uintptr_t) * 8][2];
1439 };
1440
1441
1442
1443 static int
1444 __mf_adapt_cache_fn (mfsplay_tree_node n, void *param)
1445 {
1446   __mf_object_t *obj = (__mf_object_t *) n->value;
1447   struct tree_stats *s = (struct tree_stats *) param;
1448
1449   assert (obj != NULL && s != NULL);
1450
1451   /* Exclude never-accessed objects.  */
1452   if (obj->read_count + obj->write_count)
1453     {
1454       s->obj_count ++;
1455       s->total_size += (obj->high - obj->low + 1);
1456
1457       if (obj->liveness)
1458         {
1459           unsigned i;
1460           uintptr_t addr;
1461
1462           /* VERBOSE_TRACE ("analyze low=%p live=%u name=`%s'\n",
1463              (void *) obj->low, obj->liveness, obj->name); */
1464
1465           s->live_obj_count ++;
1466           s->total_weight += (double) obj->liveness;
1467           s->weighted_size +=
1468             (double) (obj->high - obj->low + 1) *
1469             (double) obj->liveness;
1470
1471           addr = obj->low;
1472           for (i=0; i<sizeof(uintptr_t) * 8; i++)
1473             {
1474               unsigned bit = addr & 1;
1475               s->weighted_address_bits[i][bit] += obj->liveness;
1476               addr = addr >> 1;
1477             }
1478
1479           /* Age the liveness value.  */
1480           obj->liveness >>= 1;
1481         }
1482     }
1483
1484   return 0;
1485 }
1486
1487
1488 static void
1489 __mf_adapt_cache ()
1490 {
1491   struct tree_stats s;
1492   uintptr_t new_mask = 0;
1493   unsigned char new_shift;
1494   float cache_utilization;
1495   float max_value;
1496   static float smoothed_new_shift = -1.0;
1497   unsigned i;
1498
1499   memset (&s, 0, sizeof (s));
1500
1501   mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_HEAP), __mf_adapt_cache_fn, (void *) & s);
1502   mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_HEAP_I), __mf_adapt_cache_fn, (void *) & s);
1503   mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_STACK), __mf_adapt_cache_fn, (void *) & s);
1504   mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_STATIC), __mf_adapt_cache_fn, (void *) & s);
1505   mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_GUESS), __mf_adapt_cache_fn, (void *) & s);
1506
1507   /* Maybe we're dealing with funny aging/adaptation parameters, or an
1508      empty tree.  Just leave the cache alone in such cases, rather
1509      than risk dying by division-by-zero.  */
1510   if (! (s.obj_count > 0) && (s.live_obj_count > 0) && (s.total_weight > 0.0))
1511     return;
1512
1513   /* Guess a good value for the shift parameter by finding an address bit that is a
1514      good discriminant of lively objects.  */
1515   max_value = 0.0;
1516   for (i=0; i<sizeof (uintptr_t)*8; i++)
1517     {
1518       float value = (float) s.weighted_address_bits[i][0] * (float) s.weighted_address_bits[i][1];
1519       if (max_value < value) max_value = value;
1520     }
1521   for (i=0; i<sizeof (uintptr_t)*8; i++)
1522     {
1523       float shoulder_factor = 0.7;  /* Include slightly less popular bits too.  */
1524       float value = (float) s.weighted_address_bits[i][0] * (float) s.weighted_address_bits[i][1];
1525       if (value >= max_value * shoulder_factor)
1526         break;
1527     }
1528   if (smoothed_new_shift < 0) smoothed_new_shift = __mf_lc_shift;
1529   /* Converge toward this slowly to reduce flapping. */
1530   smoothed_new_shift = 0.9*smoothed_new_shift + 0.1*i;
1531   new_shift = (unsigned) (smoothed_new_shift + 0.5);
1532   assert (new_shift < sizeof (uintptr_t)*8);
1533
1534   /* Count number of used buckets.  */
1535   cache_utilization = 0.0;
1536   for (i = 0; i < (1 + __mf_lc_mask); i++)
1537     if (__mf_lookup_cache[i].low != 0 || __mf_lookup_cache[i].high != 0)
1538       cache_utilization += 1.0;
1539   cache_utilization /= (1 + __mf_lc_mask);
1540
1541   new_mask |= 0xffff; /* XXX: force a large cache.  */
1542   new_mask &= (LOOKUP_CACHE_SIZE_MAX - 1);
1543
1544   VERBOSE_TRACE ("adapt cache obj=%u/%u sizes=%lu/%.0f/%.0f => "
1545                  "util=%u%% m=%p s=%u\n",
1546                  s.obj_count, s.live_obj_count, s.total_size, s.total_weight, s.weighted_size,
1547                  (unsigned)(cache_utilization*100.0), (void *) new_mask, new_shift);
1548
1549   /* We should reinitialize cache if its parameters have changed.  */
1550   if (new_mask != __mf_lc_mask ||
1551       new_shift != __mf_lc_shift)
1552     {
1553       __mf_lc_mask = new_mask;
1554       __mf_lc_shift = new_shift;
1555       /* XXX: race */
1556       memset (__mf_lookup_cache, 0, sizeof(__mf_lookup_cache));
1557       /* void slot 0 */
1558       __mf_lookup_cache[0].low = MAXPTR;
1559     }
1560 }
1561
1562
1563
1564 /* __mf_find_object[s] */
1565
1566 /* Find overlapping live objecs between [low,high].  Return up to
1567    max_objs of their pointers in objs[].  Return total count of
1568    overlaps (may exceed max_objs). */
1569
1570 unsigned
1571 __mf_find_objects2 (uintptr_t ptr_low, uintptr_t ptr_high,
1572                     __mf_object_t **objs, unsigned max_objs, int type)
1573 {
1574   unsigned count = 0;
1575   mfsplay_tree t = __mf_object_tree (type);
1576   mfsplay_tree_key k = (mfsplay_tree_key) ptr_low;
1577   int direction;
1578
1579   mfsplay_tree_node n = mfsplay_tree_lookup (t, k);
1580   /* An exact match for base address implies a hit.  */
1581   if (n != NULL)
1582     {
1583       if (count < max_objs)
1584         objs[count] = (__mf_object_t *) n->value;
1585       count ++;
1586     }
1587
1588   /* Iterate left then right near this key value to find all overlapping objects. */
1589   for (direction = 0; direction < 2; direction ++)
1590     {
1591       /* Reset search origin.  */
1592       k = (mfsplay_tree_key) ptr_low;
1593
1594       while (1)
1595         {
1596           __mf_object_t *obj;
1597
1598           n = (direction == 0 ? mfsplay_tree_successor (t, k) : mfsplay_tree_predecessor (t, k));
1599           if (n == NULL) break;
1600           obj = (__mf_object_t *) n->value;
1601
1602           if (! (obj->low <= ptr_high && obj->high >= ptr_low)) /* No overlap? */
1603             break;
1604
1605           if (count < max_objs)
1606             objs[count] = (__mf_object_t *) n->value;
1607           count ++;
1608
1609           k = (mfsplay_tree_key) obj->low;
1610         }
1611     }
1612
1613   return count;
1614 }
1615
1616
1617 unsigned
1618 __mf_find_objects (uintptr_t ptr_low, uintptr_t ptr_high,
1619                    __mf_object_t **objs, unsigned max_objs)
1620 {
1621   int type;
1622   unsigned count = 0;
1623
1624   /* Search each splay tree for overlaps.  */
1625   for (type = __MF_TYPE_NOACCESS; type <= __MF_TYPE_GUESS; type++)
1626     {
1627       unsigned c = __mf_find_objects2 (ptr_low, ptr_high, objs, max_objs, type);
1628       if (c > max_objs)
1629         {
1630           max_objs = 0;
1631           objs = NULL;
1632         }
1633       else /* NB: C may equal 0 */
1634         {
1635           max_objs -= c;
1636           objs += c;
1637         }
1638       count += c;
1639     }
1640
1641   return count;
1642 }
1643
1644
1645
1646 /* __mf_link_object */
1647
1648 static void
1649 __mf_link_object (__mf_object_t *node)
1650 {
1651   mfsplay_tree t = __mf_object_tree (node->type);
1652   mfsplay_tree_insert (t, (mfsplay_tree_key) node->low, (mfsplay_tree_value) node);
1653 }
1654
1655 /* __mf_unlink_object */
1656
1657 static void
1658 __mf_unlink_object (__mf_object_t *node)
1659 {
1660   mfsplay_tree t = __mf_object_tree (node->type);
1661   mfsplay_tree_remove (t, (mfsplay_tree_key) node->low);
1662 }
1663
1664 /* __mf_find_dead_objects */
1665
1666 /* Find overlapping dead objecs between [low,high].  Return up to
1667    max_objs of their pointers in objs[].  Return total count of
1668    overlaps (may exceed max_objs).  */
1669
1670 static unsigned
1671 __mf_find_dead_objects (uintptr_t low, uintptr_t high,
1672                         __mf_object_t **objs, unsigned max_objs)
1673 {
1674   if (__mf_opts.persistent_count > 0)
1675     {
1676       unsigned count = 0;
1677       unsigned recollection = 0;
1678       unsigned row = 0;
1679
1680       assert (low <= high);
1681       assert (max_objs == 0 || objs != NULL);
1682
1683       /* Widen the search from the most recent plots in each row, looking
1684          backward in time.  */
1685       recollection = 0;
1686       while (recollection < __mf_opts.persistent_count)
1687         {
1688           count = 0;
1689
1690           for (row = 0; row <= __MF_TYPE_MAX_CEM; row ++)
1691             {
1692               unsigned plot;
1693               unsigned i;
1694
1695               plot = __mf_object_dead_head [row];
1696               for (i = 0; i <= recollection; i ++)
1697                 {
1698                   __mf_object_t *obj;
1699
1700                   /* Look backward through row: it's a circular buffer.  */
1701                   if (plot > 0) plot --;
1702                   else plot = __mf_opts.persistent_count - 1;
1703
1704                   obj = __mf_object_cemetary [row][plot];
1705                   if (obj && obj->low <= high && obj->high >= low)
1706                     {
1707                       /* Found an overlapping dead object!  */
1708                       if (count < max_objs)
1709                         objs [count] = obj;
1710                       count ++;
1711                     }
1712                 }
1713             }
1714
1715           if (count)
1716             break;
1717
1718           /* Look farther back in time.  */
1719           recollection = (recollection * 2) + 1;
1720         }
1721
1722       return count;
1723     } else {
1724       return 0;
1725     }
1726 }
1727
1728 /* __mf_describe_object */
1729
1730 static void
1731 __mf_describe_object (__mf_object_t *obj)
1732 {
1733   static unsigned epoch = 0;
1734   if (obj == NULL)
1735     {
1736       epoch ++;
1737       return;
1738     }
1739
1740   if (__mf_opts.abbreviate && obj->description_epoch == epoch)
1741     {
1742       fprintf (stderr,
1743                "mudflap %sobject %p: name=`%s'\n",
1744                (obj->deallocated_p ? "dead " : ""),
1745                (void *) obj, (obj->name ? obj->name : ""));
1746       return;
1747     }
1748   else
1749     obj->description_epoch = epoch;
1750
1751   fprintf (stderr,
1752            "mudflap %sobject %p: name=`%s'\n"
1753            "bounds=[%p,%p] size=%lu area=%s check=%ur/%uw liveness=%u%s\n"
1754            "alloc time=%lu.%06lu pc=%p"
1755 #ifdef LIBMUDFLAPTH
1756            " thread=%u"
1757 #endif
1758            "\n",
1759            (obj->deallocated_p ? "dead " : ""),
1760            (void *) obj, (obj->name ? obj->name : ""),
1761            (void *) obj->low, (void *) obj->high,
1762            (unsigned long) (obj->high - obj->low + 1),
1763            (obj->type == __MF_TYPE_NOACCESS ? "no-access" :
1764             obj->type == __MF_TYPE_HEAP ? "heap" :
1765             obj->type == __MF_TYPE_HEAP_I ? "heap-init" :
1766             obj->type == __MF_TYPE_STACK ? "stack" :
1767             obj->type == __MF_TYPE_STATIC ? "static" :
1768             obj->type == __MF_TYPE_GUESS ? "guess" :
1769             "unknown"),
1770            obj->read_count, obj->write_count, obj->liveness,
1771            obj->watching_p ? " watching" : "",
1772            obj->alloc_time.tv_sec, obj->alloc_time.tv_usec,
1773            (void *) obj->alloc_pc
1774 #ifdef LIBMUDFLAPTH
1775            , (unsigned) obj->alloc_thread
1776 #endif
1777            );
1778
1779   if (__mf_opts.backtrace > 0)
1780   {
1781     unsigned i;
1782     for (i=0; i<obj->alloc_backtrace_size; i++)
1783       fprintf (stderr, "      %s\n", obj->alloc_backtrace[i]);
1784   }
1785
1786   if (__mf_opts.persistent_count > 0)
1787     {
1788       if (obj->deallocated_p)
1789         {
1790           fprintf (stderr, "dealloc time=%lu.%06lu pc=%p"
1791 #ifdef LIBMUDFLAPTH
1792                    " thread=%u"
1793 #endif
1794                    "\n",
1795                    obj->dealloc_time.tv_sec, obj->dealloc_time.tv_usec,
1796                    (void *) obj->dealloc_pc
1797 #ifdef LIBMUDFLAPTH
1798                    , (unsigned) obj->dealloc_thread
1799 #endif
1800                    );
1801
1802
1803           if (__mf_opts.backtrace > 0)
1804           {
1805             unsigned i;
1806             for (i=0; i<obj->dealloc_backtrace_size; i++)
1807               fprintf (stderr, "      %s\n", obj->dealloc_backtrace[i]);
1808           }
1809         }
1810     }
1811 }
1812
1813
1814 static int
1815 __mf_report_leaks_fn (mfsplay_tree_node n, void *param)
1816 {
1817   __mf_object_t *node = (__mf_object_t *) n->value;
1818   unsigned *count = (unsigned *) param;
1819
1820   if (count != NULL)
1821     (*count) ++;
1822
1823   fprintf (stderr, "Leaked object %u:\n", (*count));
1824   __mf_describe_object (node);
1825
1826   return 0;
1827 }
1828
1829
1830 static unsigned
1831 __mf_report_leaks ()
1832 {
1833   unsigned count = 0;
1834
1835   (void) mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_HEAP),
1836                              __mf_report_leaks_fn, & count);
1837   (void) mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_HEAP_I),
1838                              __mf_report_leaks_fn, & count);
1839
1840   return count;
1841 }
1842
1843 /* ------------------------------------------------------------------------ */
1844 /* __mf_report */
1845
1846 void
1847 __mf_report ()
1848 {
1849   LOCKTH ();
1850   BEGIN_RECURSION_PROTECT ();
1851   __mfu_report ();
1852   END_RECURSION_PROTECT ();
1853   UNLOCKTH ();
1854 }
1855
1856 void
1857 __mfu_report ()
1858 {
1859   if (__mf_opts.collect_stats)
1860     {
1861       fprintf (stderr,
1862                "*******\n"
1863                "mudflap stats:\n"
1864                "calls to __mf_check: %lu\n"
1865                "         __mf_register: %lu [%luB, %luB, %luB, %luB, %luB]\n"
1866                "         __mf_unregister: %lu [%luB]\n"
1867                "         __mf_violation: [%lu, %lu, %lu, %lu, %lu]\n",
1868                __mf_count_check,
1869                __mf_count_register,
1870                __mf_total_register_size[0], __mf_total_register_size[1],
1871                __mf_total_register_size[2], __mf_total_register_size[3],
1872                __mf_total_register_size[4], /* XXX */
1873                __mf_count_unregister, __mf_total_unregister_size,
1874                __mf_count_violation[0], __mf_count_violation[1],
1875                __mf_count_violation[2], __mf_count_violation[3],
1876                __mf_count_violation[4]);
1877
1878       fprintf (stderr,
1879                "calls with reentrancy: %lu\n", __mf_reentrancy);
1880 #ifdef LIBMUDFLAPTH
1881       fprintf (stderr,
1882                "           lock contention: %lu\n", __mf_lock_contention);
1883 #endif
1884
1885       /* Lookup cache stats.  */
1886       {
1887         unsigned i;
1888         unsigned max_reuse = 0;
1889         unsigned num_used = 0;
1890         unsigned num_unused = 0;
1891
1892         for (i = 0; i < LOOKUP_CACHE_SIZE; i++)
1893           {
1894             if (__mf_lookup_cache_reusecount[i])
1895               num_used ++;
1896             else
1897               num_unused ++;
1898             if (max_reuse < __mf_lookup_cache_reusecount[i])
1899               max_reuse = __mf_lookup_cache_reusecount[i];
1900           }
1901         fprintf (stderr, "lookup cache slots used: %u  unused: %u  peak-reuse: %u\n",
1902                  num_used, num_unused, max_reuse);
1903       }
1904
1905       {
1906         unsigned live_count;
1907         live_count = __mf_find_objects (MINPTR, MAXPTR, NULL, 0);
1908         fprintf (stderr, "number of live objects: %u\n", live_count);
1909       }
1910
1911       if (__mf_opts.persistent_count > 0)
1912         {
1913           unsigned dead_count = 0;
1914           unsigned row, plot;
1915           for (row = 0; row <= __MF_TYPE_MAX_CEM; row ++)
1916             for (plot = 0 ; plot < __mf_opts.persistent_count; plot ++)
1917               if (__mf_object_cemetary [row][plot] != 0)
1918                 dead_count ++;
1919           fprintf (stderr, "          zombie objects: %u\n", dead_count);
1920         }
1921     }
1922   if (__mf_opts.print_leaks && (__mf_opts.mudflap_mode == mode_check))
1923     {
1924       unsigned l;
1925       extern void * __mf_wrap_alloca_indirect (size_t c);
1926
1927       /* Free up any remaining alloca()'d blocks.  */
1928       __mf_wrap_alloca_indirect (0);
1929 #ifdef HAVE___LIBC_FREERES
1930       if (__mf_opts.call_libc_freeres)
1931         {
1932           extern void __libc_freeres (void);
1933           __libc_freeres ();
1934         }
1935 #endif
1936
1937       __mf_describe_object (NULL); /* Reset description epoch.  */
1938       l = __mf_report_leaks ();
1939       fprintf (stderr, "number of leaked objects: %u\n", l);
1940     }
1941 }
1942
1943 /* __mf_backtrace */
1944
1945 size_t
1946 __mf_backtrace (char ***symbols, void *guess_pc, unsigned guess_omit_levels)
1947 {
1948   void ** pc_array;
1949   unsigned pc_array_size = __mf_opts.backtrace + guess_omit_levels;
1950   unsigned remaining_size;
1951   unsigned omitted_size = 0;
1952   unsigned i;
1953   DECLARE (void, free, void *ptr);
1954   DECLARE (void *, calloc, size_t c, size_t n);
1955   DECLARE (void *, malloc, size_t n);
1956
1957   pc_array = CALL_REAL (calloc, pc_array_size, sizeof (void *) );
1958 #ifdef HAVE_BACKTRACE
1959   pc_array_size = backtrace (pc_array, pc_array_size);
1960 #else
1961 #define FETCH(n) do { if (pc_array_size >= n) { \
1962                  pc_array[n] = __builtin_return_address(n); \
1963                  if (pc_array[n] == 0) pc_array_size = n; } } while (0)
1964
1965   /* Unroll some calls __builtin_return_address because this function
1966      only takes a literal integer parameter.  */
1967   FETCH (0);
1968 #if 0
1969   /* XXX: __builtin_return_address sometimes crashes (!) on >0 arguments,
1970      rather than simply returning 0.  :-(  */
1971   FETCH (1);
1972   FETCH (2);
1973   FETCH (3);
1974   FETCH (4);
1975   FETCH (5);
1976   FETCH (6);
1977   FETCH (7);
1978   FETCH (8);
1979   if (pc_array_size > 8) pc_array_size = 9;
1980 #else
1981   if (pc_array_size > 0) pc_array_size = 1;
1982 #endif
1983
1984 #undef FETCH
1985 #endif
1986
1987   /* We want to trim the first few levels of the stack traceback,
1988      since they contain libmudflap wrappers and junk.  If pc_array[]
1989      ends up containing a non-NULL guess_pc, then trim everything
1990      before that.  Otherwise, omit the first guess_omit_levels
1991      entries. */
1992
1993   if (guess_pc != NULL)
1994     for (i=0; i<pc_array_size; i++)
1995       if (pc_array [i] == guess_pc)
1996         omitted_size = i;
1997
1998   if (omitted_size == 0) /* No match? */
1999     if (pc_array_size > guess_omit_levels)
2000       omitted_size = guess_omit_levels;
2001
2002   remaining_size = pc_array_size - omitted_size;
2003
2004 #ifdef HAVE_BACKTRACE_SYMBOLS
2005   *symbols = backtrace_symbols (pc_array + omitted_size, remaining_size);
2006 #else
2007   {
2008     /* Let's construct a buffer by hand.  It will have <remaining_size>
2009        char*'s at the front, pointing at individual strings immediately
2010        afterwards.  */
2011     void *buffer;
2012     char *chars;
2013     char **pointers;
2014     enum { perline = 30 };
2015     buffer = CALL_REAL (malloc, remaining_size * (perline + sizeof(char *)));
2016     pointers = (char **) buffer;
2017     chars = (char *)buffer + (remaining_size * sizeof (char *));
2018     for (i = 0; i < remaining_size; i++)
2019       {
2020         pointers[i] = chars;
2021         sprintf (chars, "[0x%p]", pc_array [omitted_size + i]);
2022         chars = chars + perline;
2023       }
2024     *symbols = pointers;
2025   }
2026 #endif
2027   CALL_REAL (free, pc_array);
2028
2029   return remaining_size;
2030 }
2031
2032 /* ------------------------------------------------------------------------ */
2033 /* __mf_violation */
2034
2035 void
2036 __mf_violation (void *ptr, size_t sz, uintptr_t pc,
2037                 const char *location, int type)
2038 {
2039   char buf [128];
2040   static unsigned violation_number;
2041   DECLARE(void, free, void *ptr);
2042
2043   TRACE ("violation pc=%p location=%s type=%d ptr=%p size=%lu\n",
2044          (void *) pc,
2045          (location != NULL ? location : ""), type, ptr, (unsigned long) sz);
2046
2047   if (__mf_opts.collect_stats)
2048     __mf_count_violation [(type < 0) ? 0 :
2049                           (type > __MF_VIOL_WATCH) ? 0 :
2050                           type] ++;
2051
2052   /* Print out a basic warning message.  */
2053   if (__mf_opts.verbose_violations)
2054   {
2055     unsigned dead_p;
2056     unsigned num_helpful = 0;
2057     struct timeval now = { 0, 0 };
2058 #if HAVE_GETTIMEOFDAY
2059     gettimeofday (& now, NULL);
2060 #endif
2061
2062     violation_number ++;
2063     fprintf (stderr,
2064              "*******\n"
2065              "mudflap violation %u (%s): time=%lu.%06lu "
2066              "ptr=%p size=%lu\npc=%p%s%s%s\n",
2067              violation_number,
2068              ((type == __MF_VIOL_READ) ? "check/read" :
2069               (type == __MF_VIOL_WRITE) ? "check/write" :
2070               (type == __MF_VIOL_REGISTER) ? "register" :
2071               (type == __MF_VIOL_UNREGISTER) ? "unregister" :
2072               (type == __MF_VIOL_WATCH) ? "watch" : "unknown"),
2073              now.tv_sec, now.tv_usec,
2074              (void *) ptr, (unsigned long)sz, (void *) pc,
2075              (location != NULL ? " location=`" : ""),
2076              (location != NULL ? location : ""),
2077              (location != NULL ? "'" : ""));
2078
2079     if (__mf_opts.backtrace > 0)
2080       {
2081         char ** symbols;
2082         unsigned i, num;
2083
2084         num = __mf_backtrace (& symbols, (void *) pc, 2);
2085         /* Note: backtrace_symbols calls malloc().  But since we're in
2086            __mf_violation and presumably __mf_check, it'll detect
2087            recursion, and not put the new string into the database.  */
2088
2089         for (i=0; i<num; i++)
2090           fprintf (stderr, "      %s\n", symbols[i]);
2091
2092         /* Calling free() here would trigger a violation.  */
2093         CALL_REAL(free, symbols);
2094       }
2095
2096
2097     /* Look for nearby objects.  For this, we start with s_low/s_high
2098        pointing to the given area, looking for overlapping objects.
2099        If none show up, widen the search area and keep looking. */
2100
2101     if (sz == 0) sz = 1;
2102
2103     for (dead_p = 0; dead_p <= 1; dead_p ++) /* for dead_p in 0 1 */
2104       {
2105         enum {max_objs = 3}; /* magic */
2106         __mf_object_t *objs[max_objs];
2107         unsigned num_objs = 0;
2108         uintptr_t s_low, s_high;
2109         unsigned tries = 0;
2110         unsigned i;
2111
2112         s_low = (uintptr_t) ptr;
2113         s_high = CLAMPSZ (ptr, sz);
2114
2115         while (tries < 16) /* magic */
2116           {
2117             if (dead_p)
2118               num_objs = __mf_find_dead_objects (s_low, s_high, objs, max_objs);
2119             else
2120               num_objs = __mf_find_objects (s_low, s_high, objs, max_objs);
2121
2122             if (num_objs) /* good enough */
2123               break;
2124
2125             tries ++;
2126
2127             /* XXX: tune this search strategy.  It's too dependent on
2128              sz, which can vary from 1 to very big (when array index
2129              checking) numbers. */
2130             s_low = CLAMPSUB (s_low, (sz * tries * tries));
2131             s_high = CLAMPADD (s_high, (sz * tries * tries));
2132           }
2133
2134         for (i = 0; i < min (num_objs, max_objs); i++)
2135           {
2136             __mf_object_t *obj = objs[i];
2137             uintptr_t low = (uintptr_t) ptr;
2138             uintptr_t high = CLAMPSZ (ptr, sz);
2139             unsigned before1 = (low < obj->low) ? obj->low - low : 0;
2140             unsigned after1 = (low > obj->high) ? low - obj->high : 0;
2141             unsigned into1 = (high >= obj->low && low <= obj->high) ? low - obj->low : 0;
2142             unsigned before2 = (high < obj->low) ? obj->low - high : 0;
2143             unsigned after2 = (high > obj->high) ? high - obj->high : 0;
2144             unsigned into2 = (high >= obj->low && low <= obj->high) ? high - obj->low : 0;
2145
2146             fprintf (stderr, "Nearby object %u: checked region begins %uB %s and ends %uB %s\n",
2147                      num_helpful + i + 1,
2148                      (before1 ? before1 : after1 ? after1 : into1),
2149                      (before1 ? "before" : after1 ? "after" : "into"),
2150                      (before2 ? before2 : after2 ? after2 : into2),
2151                      (before2 ? "before" : after2 ? "after" : "into"));
2152             __mf_describe_object (obj);
2153           }
2154         num_helpful += num_objs;
2155       }
2156
2157     fprintf (stderr, "number of nearby objects: %u\n", num_helpful);
2158   }
2159
2160   /* How to finally handle this violation?  */
2161   switch (__mf_opts.violation_mode)
2162     {
2163     case viol_nop:
2164       break;
2165     case viol_segv:
2166       kill (getpid(), SIGSEGV);
2167       break;
2168     case viol_abort:
2169       abort ();
2170       break;
2171     case viol_gdb:
2172
2173       snprintf (buf, 128, "gdb --pid=%u", (unsigned) getpid ());
2174       system (buf);
2175       /* XXX: should probably fork() && sleep(GDB_WAIT_PARAMETER)
2176       instead, and let the forked child execlp() gdb.  That way, this
2177       subject process can be resumed under the supervision of gdb.
2178       This can't happen now, since system() only returns when gdb
2179       dies.  In that case, we need to beware of starting a second
2180       concurrent gdb child upon the next violation.  (But if the first
2181       gdb dies, then starting a new one is appropriate.)  */
2182       break;
2183     }
2184 }
2185
2186 /* ------------------------------------------------------------------------ */
2187
2188
2189 unsigned __mf_watch (void *ptr, size_t sz)
2190 {
2191   unsigned rc;
2192   LOCKTH ();
2193   BEGIN_RECURSION_PROTECT ();
2194   rc = __mf_watch_or_not (ptr, sz, 1);
2195   END_RECURSION_PROTECT ();
2196   UNLOCKTH ();
2197   return rc;
2198 }
2199
2200 unsigned __mf_unwatch (void *ptr, size_t sz)
2201 {
2202   unsigned rc;
2203   LOCKTH ();
2204   rc = __mf_watch_or_not (ptr, sz, 0);
2205   UNLOCKTH ();
2206   return rc;
2207 }
2208
2209
2210 static unsigned
2211 __mf_watch_or_not (void *ptr, size_t sz, char flag)
2212 {
2213   uintptr_t ptr_high = CLAMPSZ (ptr, sz);
2214   uintptr_t ptr_low = (uintptr_t) ptr;
2215   unsigned count = 0;
2216
2217   TRACE ("%s ptr=%p size=%lu\n",
2218          (flag ? "watch" : "unwatch"), ptr, (unsigned long) sz);
2219
2220   switch (__mf_opts.mudflap_mode)
2221     {
2222     case mode_nop:
2223     case mode_populate:
2224     case mode_violate:
2225       count = 0;
2226       break;
2227
2228     case mode_check:
2229       {
2230         __mf_object_t **all_ovr_objs;
2231         unsigned obj_count;
2232         unsigned n;
2233         DECLARE (void *, malloc, size_t c);
2234         DECLARE (void, free, void *p);
2235
2236         obj_count = __mf_find_objects (ptr_low, ptr_high, NULL, 0);
2237         VERBOSE_TRACE (" %u:", obj_count);
2238
2239         all_ovr_objs = CALL_REAL (malloc, (sizeof (__mf_object_t *) * obj_count));
2240         if (all_ovr_objs == NULL) abort ();
2241         n = __mf_find_objects (ptr_low, ptr_high, all_ovr_objs, obj_count);
2242         assert (n == obj_count);
2243
2244         for (n = 0; n < obj_count; n ++)
2245           {
2246             __mf_object_t *obj = all_ovr_objs[n];
2247
2248             VERBOSE_TRACE (" [%p]", (void *) obj);
2249             if (obj->watching_p != flag)
2250               {
2251                 obj->watching_p = flag;
2252                 count ++;
2253
2254                 /* Remove object from cache, to ensure next access
2255                    goes through __mf_check().  */
2256                 if (flag)
2257                   __mf_uncache_object (obj);
2258               }
2259           }
2260         CALL_REAL (free, all_ovr_objs);
2261       }
2262       break;
2263     }
2264
2265   return count;
2266 }
2267
2268
2269 void
2270 __mf_sigusr1_handler (int num)
2271 {
2272   __mf_sigusr1_received ++;
2273 }
2274
2275 /* Install or remove SIGUSR1 handler as necessary.
2276    Also, respond to a received pending SIGUSR1.  */
2277 void
2278 __mf_sigusr1_respond ()
2279 {
2280   static int handler_installed;
2281
2282 #ifdef SIGUSR1
2283   /* Manage handler */
2284   if (__mf_opts.sigusr1_report && ! handler_installed)
2285     {
2286       signal (SIGUSR1, __mf_sigusr1_handler);
2287       handler_installed = 1;
2288     }
2289   else if(! __mf_opts.sigusr1_report && handler_installed)
2290     {
2291       signal (SIGUSR1, SIG_DFL);
2292       handler_installed = 0;
2293     }
2294 #endif
2295
2296   /* Manage enqueued signals */
2297   if (__mf_sigusr1_received > __mf_sigusr1_handled)
2298     {
2299       __mf_sigusr1_handled ++;
2300       assert (__mf_get_state () == reentrant);
2301       __mfu_report ();
2302       handler_installed = 0; /* We may need to re-enable signal; this might be a SysV library. */
2303     }
2304 }
2305
2306
2307 /* XXX: provide an alternative __assert_fail function that cannot
2308    fail due to libmudflap infinite recursion.  */
2309 #ifndef NDEBUG
2310
2311 static void
2312 write_itoa (int fd, unsigned n)
2313 {
2314   enum x { bufsize = sizeof(n)*4 };
2315   char buf [bufsize];
2316   unsigned i;
2317
2318   for (i=0; i<bufsize-1; i++)
2319     {
2320       unsigned digit = n % 10;
2321       buf[bufsize-2-i] = digit + '0';
2322       n /= 10;
2323       if (n == 0)
2324         {
2325           char *m = & buf [bufsize-2-i];
2326           buf[bufsize-1] = '\0';
2327           write (fd, m, strlen(m));
2328           break;
2329         }
2330     }
2331 }
2332
2333
2334 void
2335 __assert_fail (const char *msg, const char *file, unsigned line, const char *func)
2336 {
2337 #define write2(string) write (2, (string), strlen ((string)));
2338   write2("mf");
2339 #ifdef LIBMUDFLAPTH
2340   write2("(");
2341   write_itoa (2, (unsigned) pthread_self ());
2342   write2(")");
2343 #endif
2344   write2(": assertion failure: `");
2345   write (2, msg, strlen (msg));
2346   write2("' in ");
2347   write (2, func, strlen (func));
2348   write2(" at ");
2349   write (2, file, strlen (file));
2350   write2(":");
2351   write_itoa (2, line);
2352   write2("\n");
2353 #undef write2
2354   abort ();
2355 }
2356
2357
2358 #endif
2359
2360
2361
2362 /* Adapted splay tree code, originally from libiberty.  It has been
2363    specialized for libmudflap as requested by RMS.  */
2364
2365 static void
2366 mfsplay_tree_free (void *p)
2367 {
2368   DECLARE (void, free, void *p);
2369   CALL_REAL (free, p);
2370 }
2371
2372 static void *
2373 mfsplay_tree_xmalloc (size_t s)
2374 {
2375   DECLARE (void *, malloc, size_t s);
2376   return CALL_REAL (malloc, s);
2377 }
2378
2379
2380 static void mfsplay_tree_splay (mfsplay_tree, mfsplay_tree_key);
2381 static mfsplay_tree_node mfsplay_tree_splay_helper (mfsplay_tree,
2382                                                 mfsplay_tree_key,
2383                                                 mfsplay_tree_node *,
2384                                                 mfsplay_tree_node *,
2385                                                 mfsplay_tree_node *);
2386
2387
2388 /* Help splay SP around KEY.  PARENT and GRANDPARENT are the parent
2389    and grandparent, respectively, of NODE.  */
2390
2391 static mfsplay_tree_node
2392 mfsplay_tree_splay_helper (mfsplay_tree sp,
2393                          mfsplay_tree_key key,
2394                          mfsplay_tree_node * node,
2395                          mfsplay_tree_node * parent,
2396                          mfsplay_tree_node * grandparent)
2397 {
2398   mfsplay_tree_node *next;
2399   mfsplay_tree_node n;
2400   int comparison;
2401
2402   n = *node;
2403
2404   if (!n)
2405     return *parent;
2406
2407   comparison = ((key > n->key) ? 1 : ((key < n->key) ? -1 : 0));
2408
2409   if (comparison == 0)
2410     /* We've found the target.  */
2411     next = 0;
2412   else if (comparison < 0)
2413     /* The target is to the left.  */
2414     next = &n->left;
2415   else
2416     /* The target is to the right.  */
2417     next = &n->right;
2418
2419   if (next)
2420     {
2421       /* Check whether our recursion depth is too high.  Abort this search,
2422          and signal that a rebalance is required to continue.  */
2423       if (sp->depth > sp->max_depth)
2424         {
2425           sp->rebalance_p = 1;
2426           return n;
2427          }
2428
2429       /* Continue down the tree.  */
2430       sp->depth ++;
2431       n = mfsplay_tree_splay_helper (sp, key, next, node, parent);
2432       sp->depth --;
2433
2434       /* The recursive call will change the place to which NODE
2435          points.  */
2436       if (*node != n || sp->rebalance_p)
2437         return n;
2438     }
2439
2440   if (!parent)
2441     /* NODE is the root.  We are done.  */
2442     return n;
2443
2444   /* First, handle the case where there is no grandparent (i.e.,
2445    *PARENT is the root of the tree.)  */
2446   if (!grandparent)
2447     {
2448       if (n == (*parent)->left)
2449         {
2450           *node = n->right;
2451           n->right = *parent;
2452         }
2453       else
2454         {
2455           *node = n->left;
2456           n->left = *parent;
2457         }
2458       *parent = n;
2459       return n;
2460     }
2461
2462   /* Next handle the cases where both N and *PARENT are left children,
2463      or where both are right children.  */
2464   if (n == (*parent)->left && *parent == (*grandparent)->left)
2465     {
2466       mfsplay_tree_node p = *parent;
2467
2468       (*grandparent)->left = p->right;
2469       p->right = *grandparent;
2470       p->left = n->right;
2471       n->right = p;
2472       *grandparent = n;
2473       return n;
2474     }
2475   else if (n == (*parent)->right && *parent == (*grandparent)->right)
2476     {
2477       mfsplay_tree_node p = *parent;
2478
2479       (*grandparent)->right = p->left;
2480       p->left = *grandparent;
2481       p->right = n->left;
2482       n->left = p;
2483       *grandparent = n;
2484       return n;
2485     }
2486
2487   /* Finally, deal with the case where N is a left child, but *PARENT
2488      is a right child, or vice versa.  */
2489   if (n == (*parent)->left)
2490     {
2491       (*parent)->left = n->right;
2492       n->right = *parent;
2493       (*grandparent)->right = n->left;
2494       n->left = *grandparent;
2495       *grandparent = n;
2496       return n;
2497     }
2498   else
2499     {
2500       (*parent)->right = n->left;
2501       n->left = *parent;
2502       (*grandparent)->left = n->right;
2503       n->right = *grandparent;
2504       *grandparent = n;
2505       return n;
2506     }
2507 }
2508
2509
2510
2511 static int
2512 mfsplay_tree_rebalance_helper1 (mfsplay_tree_node n, void *array_ptr)
2513 {
2514   mfsplay_tree_node **p = array_ptr;
2515   *(*p) = n;
2516   (*p)++;
2517   return 0;
2518 }
2519
2520
2521 static mfsplay_tree_node
2522 mfsplay_tree_rebalance_helper2 (mfsplay_tree_node * array, unsigned low,
2523                               unsigned high)
2524 {
2525   unsigned middle = low + (high - low) / 2;
2526   mfsplay_tree_node n = array[middle];
2527
2528   /* Note that since we're producing a balanced binary tree, it is not a problem
2529      that this function is recursive.  */
2530   if (low + 1 <= middle)
2531     n->left = mfsplay_tree_rebalance_helper2 (array, low, middle - 1);
2532   else
2533     n->left = NULL;
2534
2535   if (middle + 1 <= high)
2536     n->right = mfsplay_tree_rebalance_helper2 (array, middle + 1, high);
2537   else
2538     n->right = NULL;
2539
2540   return n;
2541 }
2542
2543
2544 /* Rebalance the entire tree.  Do this by copying all the node
2545    pointers into an array, then cleverly re-linking them.  */
2546 static void
2547 mfsplay_tree_rebalance (mfsplay_tree sp)
2548 {
2549   mfsplay_tree_node *all_nodes, *all_nodes_1;
2550
2551   if (sp->num_keys <= 2)
2552     return;
2553
2554   all_nodes = mfsplay_tree_xmalloc (sizeof (mfsplay_tree_node) * sp->num_keys);
2555
2556   /* Traverse all nodes to copy their addresses into this array.  */
2557   all_nodes_1 = all_nodes;
2558   mfsplay_tree_foreach (sp, mfsplay_tree_rebalance_helper1,
2559                       (void *) &all_nodes_1);
2560
2561   /* Relink all the nodes.  */
2562   sp->root = mfsplay_tree_rebalance_helper2 (all_nodes, 0, sp->num_keys - 1);
2563
2564   mfsplay_tree_free (all_nodes);
2565 }
2566
2567
2568 /* Splay SP around KEY.  */
2569 static void
2570 mfsplay_tree_splay (mfsplay_tree sp, mfsplay_tree_key key)
2571 {
2572   if (sp->root == 0)
2573     return;
2574
2575   /* If we just splayed the tree with the same key, do nothing.  */
2576   if (sp->last_splayed_key_p &&
2577       (sp->last_splayed_key == key))
2578     return;
2579
2580   /* Compute a maximum recursion depth for a splay tree with NUM nodes.
2581      The idea is to limit excessive stack usage if we're facing
2582      degenerate access patterns.  Unfortunately such patterns can occur
2583      e.g. during static initialization, where many static objects might
2584      be registered in increasing address sequence, or during a case where
2585      large tree-like heap data structures are allocated quickly.
2586
2587      On x86, this corresponds to roughly 200K of stack usage.
2588      XXX: For libmudflapth, this could be a function of __mf_opts.thread_stack.  */
2589   sp->max_depth = 2500;
2590   sp->rebalance_p = sp->depth = 0;
2591
2592   mfsplay_tree_splay_helper (sp, key, &sp->root, NULL, NULL);
2593   if (sp->rebalance_p)
2594     {
2595       mfsplay_tree_rebalance (sp);
2596
2597       sp->rebalance_p = sp->depth = 0;
2598       mfsplay_tree_splay_helper (sp, key, &sp->root, NULL, NULL);
2599
2600       if (sp->rebalance_p)
2601         abort ();
2602     }
2603
2604
2605   /* Cache this splay key. */
2606   sp->last_splayed_key = key;
2607   sp->last_splayed_key_p = 1;
2608 }
2609
2610
2611
2612 /* Allocate a new splay tree.  */
2613 static mfsplay_tree
2614 mfsplay_tree_new ()
2615 {
2616   mfsplay_tree sp = mfsplay_tree_xmalloc (sizeof (struct mfsplay_tree_s));
2617   sp->root = NULL;
2618   sp->last_splayed_key_p = 0;
2619   sp->num_keys = 0;
2620
2621   return sp;
2622 }
2623
2624
2625
2626 /* Insert a new node (associating KEY with DATA) into SP.  If a
2627    previous node with the indicated KEY exists, its data is replaced
2628    with the new value.  Returns the new node.  */
2629 static mfsplay_tree_node
2630 mfsplay_tree_insert (mfsplay_tree sp, mfsplay_tree_key key, mfsplay_tree_value value)
2631 {
2632   int comparison = 0;
2633
2634   mfsplay_tree_splay (sp, key);
2635
2636   if (sp->root)
2637     comparison = ((sp->root->key > key) ? 1 :
2638                   ((sp->root->key < key) ? -1 : 0));
2639
2640   if (sp->root && comparison == 0)
2641     {
2642       /* If the root of the tree already has the indicated KEY, just
2643          replace the value with VALUE.  */
2644       sp->root->value = value;
2645     }
2646   else
2647     {
2648       /* Create a new node, and insert it at the root.  */
2649       mfsplay_tree_node node;
2650
2651       node = mfsplay_tree_xmalloc (sizeof (struct mfsplay_tree_node_s));
2652       node->key = key;
2653       node->value = value;
2654       sp->num_keys++;
2655       if (!sp->root)
2656         node->left = node->right = 0;
2657       else if (comparison < 0)
2658         {
2659           node->left = sp->root;
2660           node->right = node->left->right;
2661           node->left->right = 0;
2662         }
2663       else
2664         {
2665           node->right = sp->root;
2666           node->left = node->right->left;
2667           node->right->left = 0;
2668         }
2669
2670       sp->root = node;
2671       sp->last_splayed_key_p = 0;
2672     }
2673
2674   return sp->root;
2675 }
2676
2677 /* Remove KEY from SP.  It is not an error if it did not exist.  */
2678
2679 static void
2680 mfsplay_tree_remove (mfsplay_tree sp, mfsplay_tree_key key)
2681 {
2682   mfsplay_tree_splay (sp, key);
2683   sp->last_splayed_key_p = 0;
2684   if (sp->root && (sp->root->key == key))
2685     {
2686       mfsplay_tree_node left, right;
2687       left = sp->root->left;
2688       right = sp->root->right;
2689       /* Delete the root node itself.  */
2690       mfsplay_tree_free (sp->root);
2691       sp->num_keys--;
2692       /* One of the children is now the root.  Doesn't matter much
2693          which, so long as we preserve the properties of the tree.  */
2694       if (left)
2695         {
2696           sp->root = left;
2697           /* If there was a right child as well, hang it off the
2698              right-most leaf of the left child.  */
2699           if (right)
2700             {
2701               while (left->right)
2702                 left = left->right;
2703               left->right = right;
2704             }
2705         }
2706       else
2707         sp->root = right;
2708     }
2709 }
2710
2711 /* Lookup KEY in SP, returning VALUE if present, and NULL
2712    otherwise.  */
2713
2714 static mfsplay_tree_node
2715 mfsplay_tree_lookup (mfsplay_tree sp, mfsplay_tree_key key)
2716 {
2717   mfsplay_tree_splay (sp, key);
2718   if (sp->root && (sp->root->key == key))
2719     return sp->root;
2720   else
2721     return 0;
2722 }
2723
2724
2725 /* Return the immediate predecessor KEY, or NULL if there is no
2726    predecessor.  KEY need not be present in the tree.  */
2727
2728 static mfsplay_tree_node
2729 mfsplay_tree_predecessor (mfsplay_tree sp, mfsplay_tree_key key)
2730 {
2731   int comparison;
2732   mfsplay_tree_node node;
2733   /* If the tree is empty, there is certainly no predecessor.  */
2734   if (!sp->root)
2735     return NULL;
2736   /* Splay the tree around KEY.  That will leave either the KEY
2737      itself, its predecessor, or its successor at the root.  */
2738   mfsplay_tree_splay (sp, key);
2739   comparison = ((sp->root->key > key) ? 1 :
2740                 ((sp->root->key < key) ? -1 : 0));
2741
2742   /* If the predecessor is at the root, just return it.  */
2743   if (comparison < 0)
2744     return sp->root;
2745   /* Otherwise, find the rightmost element of the left subtree.  */
2746   node = sp->root->left;
2747   if (node)
2748     while (node->right)
2749       node = node->right;
2750   return node;
2751 }
2752
2753 /* Return the immediate successor KEY, or NULL if there is no
2754    successor.  KEY need not be present in the tree.  */
2755
2756 static mfsplay_tree_node
2757 mfsplay_tree_successor (mfsplay_tree sp, mfsplay_tree_key key)
2758 {
2759   int comparison;
2760   mfsplay_tree_node node;
2761   /* If the tree is empty, there is certainly no successor.  */
2762   if (!sp->root)
2763     return NULL;
2764   /* Splay the tree around KEY.  That will leave either the KEY
2765      itself, its predecessor, or its successor at the root.  */
2766   mfsplay_tree_splay (sp, key);
2767   comparison = ((sp->root->key > key) ? 1 :
2768                 ((sp->root->key < key) ? -1 : 0));
2769   /* If the successor is at the root, just return it.  */
2770   if (comparison > 0)
2771     return sp->root;
2772   /* Otherwise, find the leftmost element of the right subtree.  */
2773   node = sp->root->right;
2774   if (node)
2775     while (node->left)
2776       node = node->left;
2777   return node;
2778 }
2779
2780 /* Call FN, passing it the DATA, for every node in SP, following an
2781    in-order traversal.  If FN every returns a non-zero value, the
2782    iteration ceases immediately, and the value is returned.
2783    Otherwise, this function returns 0.
2784
2785    This function simulates recursion using dynamically allocated
2786    arrays, since it may be called from mfsplay_tree_rebalance(), which
2787    in turn means that the tree is already uncomfortably deep for stack
2788    space limits.  */
2789 static int
2790 mfsplay_tree_foreach (mfsplay_tree st, mfsplay_tree_foreach_fn fn, void *data)
2791 {
2792   mfsplay_tree_node *stack1;
2793   char *stack2;
2794   unsigned sp;
2795   int val = 0;
2796   enum s { s_left, s_here, s_right, s_up };
2797
2798   if (st->root == NULL) /* => num_keys == 0 */
2799     return 0;
2800
2801   stack1 = mfsplay_tree_xmalloc (sizeof (mfsplay_tree_node) * st->num_keys);
2802   stack2 = mfsplay_tree_xmalloc (sizeof (char) * st->num_keys);
2803
2804   sp = 0;
2805   stack1 [sp] = st->root;
2806   stack2 [sp] = s_left;
2807
2808   while (1)
2809     {
2810       mfsplay_tree_node n;
2811       enum s s;
2812
2813       n = stack1 [sp];
2814       s = stack2 [sp];
2815
2816       /* Handle each of the four possible states separately.  */
2817
2818       /* 1: We're here to traverse the left subtree (if any).  */
2819       if (s == s_left)
2820         {
2821           stack2 [sp] = s_here;
2822           if (n->left != NULL)
2823             {
2824               sp ++;
2825               stack1 [sp] = n->left;
2826               stack2 [sp] = s_left;
2827             }
2828         }
2829
2830       /* 2: We're here to traverse this node.  */
2831       else if (s == s_here)
2832         {
2833           stack2 [sp] = s_right;
2834           val = (*fn) (n, data);
2835           if (val) break;
2836         }
2837
2838       /* 3: We're here to traverse the right subtree (if any).  */
2839       else if (s == s_right)
2840         {
2841           stack2 [sp] = s_up;
2842           if (n->right != NULL)
2843             {
2844               sp ++;
2845               stack1 [sp] = n->right;
2846               stack2 [sp] = s_left;
2847             }
2848         }
2849
2850       /* 4: We're here after both subtrees (if any) have been traversed.  */
2851       else if (s == s_up)
2852         {
2853           /* Pop the stack.  */
2854           if (sp == 0) break; /* Popping off the root note: we're finished!  */
2855           sp --;
2856         }
2857
2858       else
2859         abort ();
2860     }
2861
2862   mfsplay_tree_free (stack1);
2863   mfsplay_tree_free (stack2);
2864   return val;
2865 }