Go to:
Gentoo Home
Documentation
Forums
Lists
Bugs
Planet
Store
Wiki
Get Gentoo!
Gentoo's Bugzilla – Attachment 245389 Details for
Bug 335290
sys-devel/gcc-4.{0,1,2,3,4}: -mudflap accepts environment variables if setuid
Home
|
New
–
[Ex]
|
Browse
|
Search
|
Privacy Policy
|
[?]
|
Reports
|
Requests
|
Help
|
New Account
|
Log In
[x]
|
Forgot Password
Login:
[x]
gcc-4.4.x: fix $MUDFLAP_OPTIONS environment handling, based on gcc bug #41433
gcc-4.4.x-fix-mudflap_options-env.patch (text/plain), 88.08 KB, created by
m4rvin
on 2010-08-30 17:18:27 UTC
(
hide
)
Description:
gcc-4.4.x: fix $MUDFLAP_OPTIONS environment handling, based on gcc bug #41433
Filename:
MIME Type:
Creator:
m4rvin
Created:
2010-08-30 17:18:27 UTC
Size:
88.08 KB
patch
obsolete
>mudflap accepts options via $MUDFLAP_OPTIONS even when running setuid. > >-viol-gdb option invokes programs upon error detection which is bad. >Note that NULL ptr derefs which are unexploitable in userspace programs, then >become exploitable. >Fix by either ignoring this variable for setuid's (other options >are bad too; what worth a mudflap if it can be disabled for >setuids which it should protect) or some other magic. > >http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41433 >http://gcc.gnu.org/viewcvs?view=revision&revision=152026 > >diff -Nur a/libmudflap/mf-runtime.c b/libmudflap/mf-runtime.c >--- a/libmudflap/mf-runtime.c 2010-01-09 01:05:06.000000000 +0100 >+++ b/libmudflap/mf-runtime.c 2010-06-26 00:41:24.558021334 +0200 >@@ -303,6 +303,14 @@ > #ifdef LIBMUDFLAPTH > __mf_opts.thread_stack = 0; > #endif >+ >+ /* PR41443: Beware that the above flags will be applied to >+ setuid/setgid binaries, and cannot be overriden with >+ $MUDFLAP_OPTIONS. So the defaults must be non-exploitable. >+ >+ Should we consider making the default violation_mode something >+ harsher than viol_nop? OTOH, glibc's MALLOC_CHECK_ is disabled >+ by default for these same programs. */ > } > > static struct mudoption >@@ -442,7 +450,7 @@ > "This is a %s%sGCC \"mudflap\" memory-checked binary.\n" > "Mudflap is Copyright (C) 2002-2010 Free Software Foundation, Inc.\n" > "\n" >- "The mudflap code can be controlled by an environment variable:\n" >+ "Unless setuid, a program's mudflap options be set by an environment variable:\n" > "\n" > "$ export MUDFLAP_OPTIONS='<options>'\n" > "$ <mudflapped_program>\n" >@@ -705,7 +713,8 @@ > > __mf_set_default_options (); > >- ov = getenv ("MUDFLAP_OPTIONS"); >+ if (getuid () == geteuid () && getgid () == getegid ()) /* PR41433, not setuid */ >+ ov = getenv ("MUDFLAP_OPTIONS"); > if (ov) > { > int rc = __mfu_set_options (ov); >diff -Nur a/libmudflap/mf-runtime.c.orig b/libmudflap/mf-runtime.c.orig >--- a/libmudflap/mf-runtime.c.orig 1970-01-01 01:00:00.000000000 +0100 >+++ b/libmudflap/mf-runtime.c.orig 2010-01-09 01:05:06.000000000 +0100 >@@ -0,0 +1,2859 @@ >+/* Mudflap: narrow-pointer bounds-checking by tree rewriting. >+ Copyright (C) 2002, 2003, 2004, 2005, 2006, 2008, 2009, 2010 >+ Free Software Foundation, Inc. >+ Contributed by Frank Ch. Eigler <fche@redhat.com> >+ and Graydon Hoare <graydon@redhat.com> >+ Splay Tree code originally by Mark Mitchell <mark@markmitchell.com>, >+ adapted from libiberty. >+ >+This file is part of GCC. >+ >+GCC is free software; you can redistribute it and/or modify it under >+the terms of the GNU General Public License as published by the Free >+Software Foundation; either version 3, or (at your option) any later >+version. >+ >+GCC is distributed in the hope that it will be useful, but WITHOUT ANY >+WARRANTY; without even the implied warranty of MERCHANTABILITY or >+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License >+for more details. >+ >+Under Section 7 of GPL version 3, you are granted additional >+permissions described in the GCC Runtime Library Exception, version >+3.1, as published by the Free Software Foundation. >+ >+You should have received a copy of the GNU General Public License and >+a copy of the GCC Runtime Library Exception along with this program; >+see the files COPYING3 and COPYING.RUNTIME respectively. If not, see >+<http://www.gnu.org/licenses/>. */ >+ >+#include "config.h" >+ >+/* These attempt to coax various unix flavours to declare all our >+ needed tidbits in the system headers. */ >+#if !defined(__FreeBSD__) && !defined(__APPLE__) >+#define _POSIX_SOURCE >+#endif /* Some BSDs break <sys/socket.h> if this is defined. */ >+#define _GNU_SOURCE >+#define _XOPEN_SOURCE >+#define _BSD_TYPES >+#define __EXTENSIONS__ >+#define _ALL_SOURCE >+#define _LARGE_FILE_API >+#define _XOPEN_SOURCE_EXTENDED 1 >+ >+#include <stdio.h> >+#include <stdlib.h> >+#include <sys/types.h> >+#include <sys/time.h> >+#include <time.h> >+#include <unistd.h> >+#ifdef HAVE_EXECINFO_H >+#include <execinfo.h> >+#endif >+#ifdef HAVE_SIGNAL_H >+#include <signal.h> >+#endif >+#include <assert.h> >+ >+#include <string.h> >+#include <limits.h> >+#include <sys/types.h> >+#include <signal.h> >+#include <errno.h> >+#include <ctype.h> >+ >+#include "mf-runtime.h" >+#include "mf-impl.h" >+ >+ >+/* ------------------------------------------------------------------------ */ >+/* Splay-tree implementation. */ >+ >+typedef uintptr_t mfsplay_tree_key; >+typedef void *mfsplay_tree_value; >+ >+/* Forward declaration for a node in the tree. */ >+typedef struct mfsplay_tree_node_s *mfsplay_tree_node; >+ >+/* The type of a function used to iterate over the tree. */ >+typedef int (*mfsplay_tree_foreach_fn) (mfsplay_tree_node, void *); >+ >+/* The nodes in the splay tree. */ >+struct mfsplay_tree_node_s >+{ >+ /* Data. */ >+ mfsplay_tree_key key; >+ mfsplay_tree_value value; >+ /* Children. */ >+ mfsplay_tree_node left; >+ mfsplay_tree_node right; >+ /* XXX: The addition of a parent pointer may eliminate some recursion. */ >+}; >+ >+/* The splay tree itself. */ >+struct mfsplay_tree_s >+{ >+ /* The root of the tree. */ >+ mfsplay_tree_node root; >+ >+ /* The last key value for which the tree has been splayed, but not >+ since modified. */ >+ mfsplay_tree_key last_splayed_key; >+ int last_splayed_key_p; >+ >+ /* Statistics. */ >+ unsigned num_keys; >+ >+ /* Traversal recursion control flags. */ >+ unsigned max_depth; >+ unsigned depth; >+ unsigned rebalance_p; >+}; >+typedef struct mfsplay_tree_s *mfsplay_tree; >+ >+static mfsplay_tree mfsplay_tree_new (void); >+static mfsplay_tree_node mfsplay_tree_insert (mfsplay_tree, mfsplay_tree_key, mfsplay_tree_value); >+static void mfsplay_tree_remove (mfsplay_tree, mfsplay_tree_key); >+static mfsplay_tree_node mfsplay_tree_lookup (mfsplay_tree, mfsplay_tree_key); >+static mfsplay_tree_node mfsplay_tree_predecessor (mfsplay_tree, mfsplay_tree_key); >+static mfsplay_tree_node mfsplay_tree_successor (mfsplay_tree, mfsplay_tree_key); >+static int mfsplay_tree_foreach (mfsplay_tree, mfsplay_tree_foreach_fn, void *); >+static void mfsplay_tree_rebalance (mfsplay_tree sp); >+ >+/* ------------------------------------------------------------------------ */ >+/* Utility macros */ >+ >+#define CTOR __attribute__ ((constructor)) >+#define DTOR __attribute__ ((destructor)) >+ >+ >+/* Codes to describe the context in which a violation occurs. */ >+#define __MF_VIOL_UNKNOWN 0 >+#define __MF_VIOL_READ 1 >+#define __MF_VIOL_WRITE 2 >+#define __MF_VIOL_REGISTER 3 >+#define __MF_VIOL_UNREGISTER 4 >+#define __MF_VIOL_WATCH 5 >+ >+/* Protect against recursive calls. */ >+ >+static void >+begin_recursion_protect1 (const char *pf) >+{ >+ if (__mf_get_state () == reentrant) >+ { >+ write (2, "mf: erroneous reentrancy detected in `", 38); >+ write (2, pf, strlen(pf)); >+ write (2, "'\n", 2); \ >+ abort (); >+ } >+ __mf_set_state (reentrant); >+} >+ >+#define BEGIN_RECURSION_PROTECT() \ >+ begin_recursion_protect1 (__PRETTY_FUNCTION__) >+ >+#define END_RECURSION_PROTECT() \ >+ __mf_set_state (active) >+ >+/* ------------------------------------------------------------------------ */ >+/* Required globals. */ >+ >+#define LOOKUP_CACHE_MASK_DFL 1023 >+#define LOOKUP_CACHE_SIZE_MAX 65536 /* Allows max CACHE_MASK 0xFFFF */ >+#define LOOKUP_CACHE_SHIFT_DFL 2 >+ >+struct __mf_cache __mf_lookup_cache [LOOKUP_CACHE_SIZE_MAX]; >+uintptr_t __mf_lc_mask = LOOKUP_CACHE_MASK_DFL; >+unsigned char __mf_lc_shift = LOOKUP_CACHE_SHIFT_DFL; >+#define LOOKUP_CACHE_SIZE (__mf_lc_mask + 1) >+ >+struct __mf_options __mf_opts; >+int __mf_starting_p = 1; >+ >+#ifdef LIBMUDFLAPTH >+#if defined(HAVE_TLS) && !defined(USE_EMUTLS) >+__thread enum __mf_state_enum __mf_state_1 = reentrant; >+#endif >+#else >+enum __mf_state_enum __mf_state_1 = reentrant; >+#endif >+ >+#ifdef LIBMUDFLAPTH >+pthread_mutex_t __mf_biglock = >+#ifdef PTHREAD_ERRORCHECK_MUTEX_INITIALIZER_NP >+ PTHREAD_ERRORCHECK_MUTEX_INITIALIZER_NP; >+#else >+ PTHREAD_MUTEX_INITIALIZER; >+#endif >+#endif >+ >+/* Use HAVE_PTHREAD_H here instead of LIBMUDFLAPTH, so that even >+ the libmudflap.la (no threading support) can diagnose whether >+ the application is linked with -lpthread. See __mf_usage() below. */ >+#if HAVE_PTHREAD_H >+#ifdef _POSIX_THREADS >+#pragma weak pthread_join >+#else >+#define pthread_join NULL >+#endif >+#endif >+ >+ >+/* ------------------------------------------------------------------------ */ >+/* stats-related globals. */ >+ >+static unsigned long __mf_count_check; >+static unsigned long __mf_lookup_cache_reusecount [LOOKUP_CACHE_SIZE_MAX]; >+static unsigned long __mf_count_register; >+static unsigned long __mf_total_register_size [__MF_TYPE_MAX+1]; >+static unsigned long __mf_count_unregister; >+static unsigned long __mf_total_unregister_size; >+static unsigned long __mf_count_violation [__MF_VIOL_WATCH+1]; >+static unsigned long __mf_sigusr1_received; >+static unsigned long __mf_sigusr1_handled; >+/* not static */ unsigned long __mf_reentrancy; >+#ifdef LIBMUDFLAPTH >+/* not static */ unsigned long __mf_lock_contention; >+#endif >+ >+ >+/* ------------------------------------------------------------------------ */ >+/* mode-check-related globals. */ >+ >+typedef struct __mf_object >+{ >+ uintptr_t low, high; /* __mf_register parameters */ >+ const char *name; >+ char type; /* __MF_TYPE_something */ >+ char watching_p; /* Trigger a VIOL_WATCH on access? */ >+ unsigned read_count; /* Number of times __mf_check/read was called on this object. */ >+ unsigned write_count; /* Likewise for __mf_check/write. */ >+ unsigned liveness; /* A measure of recent checking activity. */ >+ unsigned description_epoch; /* Last epoch __mf_describe_object printed this. */ >+ >+ uintptr_t alloc_pc; >+ struct timeval alloc_time; >+ char **alloc_backtrace; >+ size_t alloc_backtrace_size; >+#ifdef LIBMUDFLAPTH >+ pthread_t alloc_thread; >+#endif >+ >+ int deallocated_p; >+ uintptr_t dealloc_pc; >+ struct timeval dealloc_time; >+ char **dealloc_backtrace; >+ size_t dealloc_backtrace_size; >+#ifdef LIBMUDFLAPTH >+ pthread_t dealloc_thread; >+#endif >+} __mf_object_t; >+ >+/* Live objects: splay trees, separated by type, ordered on .low (base address). */ >+/* Actually stored as static vars within lookup function below. */ >+ >+/* Dead objects: circular arrays; _MIN_CEM .. _MAX_CEM only */ >+static unsigned __mf_object_dead_head[__MF_TYPE_MAX_CEM+1]; /* next empty spot */ >+static __mf_object_t *__mf_object_cemetary[__MF_TYPE_MAX_CEM+1][__MF_PERSIST_MAX]; >+ >+ >+/* ------------------------------------------------------------------------ */ >+/* Forward function declarations */ >+ >+void __mf_init () CTOR; >+static void __mf_sigusr1_respond (); >+static unsigned __mf_find_objects (uintptr_t ptr_low, uintptr_t ptr_high, >+ __mf_object_t **objs, unsigned max_objs); >+static unsigned __mf_find_objects2 (uintptr_t ptr_low, uintptr_t ptr_high, >+ __mf_object_t **objs, unsigned max_objs, int type); >+static unsigned __mf_find_dead_objects (uintptr_t ptr_low, uintptr_t ptr_high, >+ __mf_object_t **objs, unsigned max_objs); >+static void __mf_adapt_cache (); >+static void __mf_describe_object (__mf_object_t *obj); >+static unsigned __mf_watch_or_not (void *ptr, size_t sz, char flag); >+static mfsplay_tree __mf_object_tree (int type); >+static void __mf_link_object (__mf_object_t *node); >+static void __mf_unlink_object (__mf_object_t *node); >+ >+ >+/* ------------------------------------------------------------------------ */ >+/* Configuration engine */ >+ >+static void >+__mf_set_default_options () >+{ >+ memset (& __mf_opts, 0, sizeof (__mf_opts)); >+ >+ __mf_opts.adapt_cache = 1000003; >+ __mf_opts.abbreviate = 1; >+ __mf_opts.verbose_violations = 1; >+ __mf_opts.free_queue_length = 4; >+ __mf_opts.persistent_count = 100; >+ __mf_opts.crumple_zone = 32; >+ __mf_opts.backtrace = 4; >+ __mf_opts.timestamps = 1; >+ __mf_opts.mudflap_mode = mode_check; >+ __mf_opts.violation_mode = viol_nop; >+#ifdef HAVE___LIBC_FREERES >+ __mf_opts.call_libc_freeres = 1; >+#endif >+ __mf_opts.heur_std_data = 1; >+#ifdef LIBMUDFLAPTH >+ __mf_opts.thread_stack = 0; >+#endif >+} >+ >+static struct mudoption >+{ >+ char *name; >+ char *description; >+ enum >+ { >+ set_option, >+ read_integer_option, >+ } type; >+ unsigned value; >+ unsigned *target; >+} >+options [] = >+ { >+ {"mode-nop", >+ "mudflaps do nothing", >+ set_option, (unsigned)mode_nop, (unsigned *)&__mf_opts.mudflap_mode}, >+ {"mode-populate", >+ "mudflaps populate object tree", >+ set_option, (unsigned)mode_populate, (unsigned *)&__mf_opts.mudflap_mode}, >+ {"mode-check", >+ "mudflaps check for memory violations", >+ set_option, (unsigned)mode_check, (unsigned *)&__mf_opts.mudflap_mode}, >+ {"mode-violate", >+ "mudflaps always cause violations (diagnostic)", >+ set_option, (unsigned)mode_violate, (unsigned *)&__mf_opts.mudflap_mode}, >+ >+ {"viol-nop", >+ "violations do not change program execution", >+ set_option, (unsigned)viol_nop, (unsigned *)&__mf_opts.violation_mode}, >+ {"viol-abort", >+ "violations cause a call to abort()", >+ set_option, (unsigned)viol_abort, (unsigned *)&__mf_opts.violation_mode}, >+ {"viol-segv", >+ "violations are promoted to SIGSEGV signals", >+ set_option, (unsigned)viol_segv, (unsigned *)&__mf_opts.violation_mode}, >+ {"viol-gdb", >+ "violations fork a gdb process attached to current program", >+ set_option, (unsigned)viol_gdb, (unsigned *)&__mf_opts.violation_mode}, >+ {"trace-calls", >+ "trace calls to mudflap runtime library", >+ set_option, 1, &__mf_opts.trace_mf_calls}, >+ {"verbose-trace", >+ "trace internal events within mudflap runtime library", >+ set_option, 1, &__mf_opts.verbose_trace}, >+ {"collect-stats", >+ "collect statistics on mudflap's operation", >+ set_option, 1, &__mf_opts.collect_stats}, >+#ifdef SIGUSR1 >+ {"sigusr1-report", >+ "print report upon SIGUSR1", >+ set_option, 1, &__mf_opts.sigusr1_report}, >+#endif >+ {"internal-checking", >+ "perform more expensive internal checking", >+ set_option, 1, &__mf_opts.internal_checking}, >+ {"print-leaks", >+ "print any memory leaks at program shutdown", >+ set_option, 1, &__mf_opts.print_leaks}, >+#ifdef HAVE___LIBC_FREERES >+ {"libc-freeres", >+ "call glibc __libc_freeres at shutdown for better leak data", >+ set_option, 1, &__mf_opts.call_libc_freeres}, >+#endif >+ {"check-initialization", >+ "detect uninitialized object reads", >+ set_option, 1, &__mf_opts.check_initialization}, >+ {"verbose-violations", >+ "print verbose messages when memory violations occur", >+ set_option, 1, &__mf_opts.verbose_violations}, >+ {"abbreviate", >+ "abbreviate repetitive listings", >+ set_option, 1, &__mf_opts.abbreviate}, >+ {"timestamps", >+ "track object lifetime timestamps", >+ set_option, 1, &__mf_opts.timestamps}, >+ {"ignore-reads", >+ "ignore read accesses - assume okay", >+ set_option, 1, &__mf_opts.ignore_reads}, >+ {"wipe-stack", >+ "wipe stack objects at unwind", >+ set_option, 1, &__mf_opts.wipe_stack}, >+ {"wipe-heap", >+ "wipe heap objects at free", >+ set_option, 1, &__mf_opts.wipe_heap}, >+ {"heur-proc-map", >+ "support /proc/self/map heuristics", >+ set_option, 1, &__mf_opts.heur_proc_map}, >+ {"heur-stack-bound", >+ "enable a simple upper stack bound heuristic", >+ set_option, 1, &__mf_opts.heur_stack_bound}, >+ {"heur-start-end", >+ "support _start.._end heuristics", >+ set_option, 1, &__mf_opts.heur_start_end}, >+ {"heur-stdlib", >+ "register standard library data (argv, errno, stdin, ...)", >+ set_option, 1, &__mf_opts.heur_std_data}, >+ {"free-queue-length", >+ "queue N deferred free() calls before performing them", >+ read_integer_option, 0, &__mf_opts.free_queue_length}, >+ {"persistent-count", >+ "keep a history of N unregistered regions", >+ read_integer_option, 0, &__mf_opts.persistent_count}, >+ {"crumple-zone", >+ "surround allocations with crumple zones of N bytes", >+ read_integer_option, 0, &__mf_opts.crumple_zone}, >+ /* XXX: not type-safe. >+ {"lc-mask", >+ "set lookup cache size mask to N (2**M - 1)", >+ read_integer_option, 0, (int *)(&__mf_lc_mask)}, >+ {"lc-shift", >+ "set lookup cache pointer shift", >+ read_integer_option, 0, (int *)(&__mf_lc_shift)}, >+ */ >+ {"lc-adapt", >+ "adapt mask/shift parameters after N cache misses", >+ read_integer_option, 1, &__mf_opts.adapt_cache}, >+ {"backtrace", >+ "keep an N-level stack trace of each call context", >+ read_integer_option, 0, &__mf_opts.backtrace}, >+#ifdef LIBMUDFLAPTH >+ {"thread-stack", >+ "override thread stacks allocation: N kB", >+ read_integer_option, 0, &__mf_opts.thread_stack}, >+#endif >+ {0, 0, set_option, 0, NULL} >+ }; >+ >+static void >+__mf_usage () >+{ >+ struct mudoption *opt; >+ >+ fprintf (stderr, >+ "This is a %s%sGCC \"mudflap\" memory-checked binary.\n" >+ "Mudflap is Copyright (C) 2002-2010 Free Software Foundation, Inc.\n" >+ "\n" >+ "The mudflap code can be controlled by an environment variable:\n" >+ "\n" >+ "$ export MUDFLAP_OPTIONS='<options>'\n" >+ "$ <mudflapped_program>\n" >+ "\n" >+ "where <options> is a space-separated list of \n" >+ "any of the following options. Use `-no-OPTION' to disable options.\n" >+ "\n", >+#if HAVE_PTHREAD_H >+ (pthread_join ? "multi-threaded " : "single-threaded "), >+#else >+ "", >+#endif >+#if LIBMUDFLAPTH >+ "thread-aware " >+#else >+ "thread-unaware " >+#endif >+ ); >+ /* XXX: The multi-threaded thread-unaware combination is bad. */ >+ >+ for (opt = options; opt->name; opt++) >+ { >+ int default_p = (opt->value == * opt->target); >+ >+ switch (opt->type) >+ { >+ char buf[128]; >+ case set_option: >+ fprintf (stderr, "-%-23.23s %s", opt->name, opt->description); >+ if (default_p) >+ fprintf (stderr, " [active]\n"); >+ else >+ fprintf (stderr, "\n"); >+ break; >+ case read_integer_option: >+ strncpy (buf, opt->name, 128); >+ strncpy (buf + strlen (opt->name), "=N", 2); >+ fprintf (stderr, "-%-23.23s %s", buf, opt->description); >+ fprintf (stderr, " [%d]\n", * opt->target); >+ break; >+ default: abort(); >+ } >+ } >+ >+ fprintf (stderr, "\n"); >+} >+ >+ >+int >+__mf_set_options (const char *optstr) >+{ >+ int rc; >+ LOCKTH (); >+ BEGIN_RECURSION_PROTECT (); >+ rc = __mfu_set_options (optstr); >+ /* XXX: It's not really that easy. A change to a bunch of parameters >+ can require updating auxiliary state or risk crashing: >+ free_queue_length, crumple_zone ... */ >+ END_RECURSION_PROTECT (); >+ UNLOCKTH (); >+ return rc; >+} >+ >+ >+int >+__mfu_set_options (const char *optstr) >+{ >+ struct mudoption *opts = 0; >+ char *nxt = 0; >+ long tmp = 0; >+ int rc = 0; >+ const char *saved_optstr = optstr; >+ >+ /* XXX: bounds-check for optstr! */ >+ >+ while (*optstr) >+ { >+ switch (*optstr) { >+ case ' ': >+ case '\t': >+ case '\n': >+ optstr++; >+ break; >+ >+ case '-': >+ if (*optstr+1) >+ { >+ int negate = 0; >+ optstr++; >+ >+ if (*optstr == '?' || >+ strncmp (optstr, "help", 4) == 0) >+ { >+ /* Caller will print help and exit. */ >+ return -1; >+ } >+ >+ if (strncmp (optstr, "no-", 3) == 0) >+ { >+ negate = 1; >+ optstr = & optstr[3]; >+ } >+ >+ for (opts = options; opts->name; opts++) >+ { >+ if (strncmp (optstr, opts->name, strlen (opts->name)) == 0) >+ { >+ optstr += strlen (opts->name); >+ assert (opts->target); >+ switch (opts->type) >+ { >+ case set_option: >+ if (negate) >+ *(opts->target) = 0; >+ else >+ *(opts->target) = opts->value; >+ break; >+ case read_integer_option: >+ if (! negate && (*optstr == '=' && *(optstr+1))) >+ { >+ optstr++; >+ tmp = strtol (optstr, &nxt, 10); >+ if ((optstr != nxt) && (tmp != LONG_MAX)) >+ { >+ optstr = nxt; >+ *(opts->target) = (int)tmp; >+ } >+ } >+ else if (negate) >+ * opts->target = 0; >+ break; >+ } >+ } >+ } >+ } >+ break; >+ >+ default: >+ fprintf (stderr, >+ "warning: unrecognized string '%s' in mudflap options\n", >+ optstr); >+ optstr += strlen (optstr); >+ rc = -1; >+ break; >+ } >+ } >+ >+ /* Special post-processing: bound __mf_lc_mask and free_queue_length for security. */ >+ __mf_lc_mask &= (LOOKUP_CACHE_SIZE_MAX - 1); >+ __mf_opts.free_queue_length &= (__MF_FREEQ_MAX - 1); >+ >+ /* Clear the lookup cache, in case the parameters got changed. */ >+ /* XXX: race */ >+ memset (__mf_lookup_cache, 0, sizeof(__mf_lookup_cache)); >+ /* void slot 0 */ >+ __mf_lookup_cache[0].low = MAXPTR; >+ >+ TRACE ("set options from `%s'\n", saved_optstr); >+ >+ /* Call this unconditionally, in case -sigusr1-report was toggled. */ >+ __mf_sigusr1_respond (); >+ >+ return rc; >+} >+ >+ >+#ifdef PIC >+ >+void >+__mf_resolve_single_dynamic (struct __mf_dynamic_entry *e) >+{ >+ char *err; >+ >+ assert (e); >+ if (e->pointer) return; >+ >+#if HAVE_DLVSYM >+ if (e->version != NULL && e->version[0] != '\0') /* non-null/empty */ >+ e->pointer = dlvsym (RTLD_NEXT, e->name, e->version); >+ else >+#endif >+ e->pointer = dlsym (RTLD_NEXT, e->name); >+ >+ err = dlerror (); >+ >+ if (err) >+ { >+ fprintf (stderr, "mf: error in dlsym(\"%s\"): %s\n", >+ e->name, err); >+ abort (); >+ } >+ if (! e->pointer) >+ { >+ fprintf (stderr, "mf: dlsym(\"%s\") = NULL\n", e->name); >+ abort (); >+ } >+} >+ >+ >+static void >+__mf_resolve_dynamics () >+{ >+ int i; >+ for (i = 0; i < dyn_INITRESOLVE; i++) >+ __mf_resolve_single_dynamic (& __mf_dynamic[i]); >+} >+ >+ >+/* NB: order must match enums in mf-impl.h */ >+struct __mf_dynamic_entry __mf_dynamic [] = >+{ >+ {NULL, "calloc", NULL}, >+ {NULL, "free", NULL}, >+ {NULL, "malloc", NULL}, >+ {NULL, "mmap", NULL}, >+ {NULL, "munmap", NULL}, >+ {NULL, "realloc", NULL}, >+ {NULL, "DUMMY", NULL}, /* dyn_INITRESOLVE */ >+#ifdef LIBMUDFLAPTH >+ {NULL, "pthread_create", PTHREAD_CREATE_VERSION}, >+ {NULL, "pthread_join", NULL}, >+ {NULL, "pthread_exit", NULL} >+#endif >+}; >+ >+#endif /* PIC */ >+ >+ >+ >+/* ------------------------------------------------------------------------ */ >+ >+/* Lookup & manage automatic initialization of the five or so splay trees. */ >+static mfsplay_tree >+__mf_object_tree (int type) >+{ >+ static mfsplay_tree trees [__MF_TYPE_MAX+1]; >+ assert (type >= 0 && type <= __MF_TYPE_MAX); >+ if (UNLIKELY (trees[type] == NULL)) >+ trees[type] = mfsplay_tree_new (); >+ return trees[type]; >+} >+ >+ >+/* not static */void >+__mf_init () >+{ >+ char *ov = 0; >+ >+ /* Return if initialization has already been done. */ >+ if (LIKELY (__mf_starting_p == 0)) >+ return; >+ >+ /* This initial bootstrap phase requires that __mf_starting_p = 1. */ >+#ifdef PIC >+ __mf_resolve_dynamics (); >+#endif >+ __mf_starting_p = 0; >+ >+ __mf_set_state (active); >+ >+ __mf_set_default_options (); >+ >+ ov = getenv ("MUDFLAP_OPTIONS"); >+ if (ov) >+ { >+ int rc = __mfu_set_options (ov); >+ if (rc < 0) >+ { >+ __mf_usage (); >+ exit (1); >+ } >+ } >+ >+ /* Initialize to a non-zero description epoch. */ >+ __mf_describe_object (NULL); >+ >+#define REG_RESERVED(obj) \ >+ __mf_register (& obj, sizeof(obj), __MF_TYPE_NOACCESS, # obj) >+ >+ REG_RESERVED (__mf_lookup_cache); >+ REG_RESERVED (__mf_lc_mask); >+ REG_RESERVED (__mf_lc_shift); >+ /* XXX: others of our statics? */ >+ >+ /* Prevent access to *NULL. */ >+ __mf_register (MINPTR, 1, __MF_TYPE_NOACCESS, "NULL"); >+ __mf_lookup_cache[0].low = (uintptr_t) -1; >+} >+ >+ >+ >+int >+__wrap_main (int argc, char* argv[]) >+{ >+ extern char **environ; >+ extern int main (); >+ extern int __real_main (); >+ static int been_here = 0; >+ >+ if (__mf_opts.heur_std_data && ! been_here) >+ { >+ unsigned i; >+ >+ been_here = 1; >+ __mf_register (argv, sizeof(char *)*(argc+1), __MF_TYPE_STATIC, "argv[]"); >+ for (i=0; i<argc; i++) >+ { >+ unsigned j = strlen (argv[i]); >+ __mf_register (argv[i], j+1, __MF_TYPE_STATIC, "argv element"); >+ } >+ >+ for (i=0; ; i++) >+ { >+ char *e = environ[i]; >+ unsigned j; >+ if (e == NULL) break; >+ j = strlen (environ[i]); >+ __mf_register (environ[i], j+1, __MF_TYPE_STATIC, "environ element"); >+ } >+ __mf_register (environ, sizeof(char *)*(i+1), __MF_TYPE_STATIC, "environ[]"); >+ >+ __mf_register (& errno, sizeof (errno), __MF_TYPE_STATIC, "errno area"); >+ >+ __mf_register (stdin, sizeof (*stdin), __MF_TYPE_STATIC, "stdin"); >+ __mf_register (stdout, sizeof (*stdout), __MF_TYPE_STATIC, "stdout"); >+ __mf_register (stderr, sizeof (*stderr), __MF_TYPE_STATIC, "stderr"); >+ >+ /* Make some effort to register ctype.h static arrays. */ >+ /* XXX: e.g., on Solaris, may need to register __ctype, _ctype, __ctype_mask, __toupper, etc. */ >+ /* On modern Linux GLIBC, these are thread-specific and changeable, and are dealt >+ with in mf-hooks2.c. */ >+ } >+ >+#ifdef PIC >+ return main (argc, argv, environ); >+#else >+ return __real_main (argc, argv, environ); >+#endif >+} >+ >+ >+ >+extern void __mf_fini () DTOR; >+void __mf_fini () >+{ >+ TRACE ("__mf_fini\n"); >+ __mfu_report (); >+ >+#ifndef PIC >+/* Since we didn't populate the tree for allocations in constructors >+ before __mf_init, we cannot check destructors after __mf_fini. */ >+ __mf_opts.mudflap_mode = mode_nop; >+#endif >+} >+ >+ >+ >+/* ------------------------------------------------------------------------ */ >+/* __mf_check */ >+ >+void __mf_check (void *ptr, size_t sz, int type, const char *location) >+{ >+ LOCKTH (); >+ BEGIN_RECURSION_PROTECT (); >+ __mfu_check (ptr, sz, type, location); >+ END_RECURSION_PROTECT (); >+ UNLOCKTH (); >+} >+ >+ >+void __mfu_check (void *ptr, size_t sz, int type, const char *location) >+{ >+ unsigned entry_idx = __MF_CACHE_INDEX (ptr); >+ struct __mf_cache *entry = & __mf_lookup_cache [entry_idx]; >+ int judgement = 0; /* 0=undecided; <0=violation; >0=okay */ >+ uintptr_t ptr_low = (uintptr_t) ptr; >+ uintptr_t ptr_high = CLAMPSZ (ptr, sz); >+ struct __mf_cache old_entry = *entry; >+ >+ if (UNLIKELY (__mf_opts.sigusr1_report)) >+ __mf_sigusr1_respond (); >+ if (UNLIKELY (__mf_opts.ignore_reads && type == 0)) >+ return; >+ >+ TRACE ("check ptr=%p b=%u size=%lu %s location=`%s'\n", >+ ptr, entry_idx, (unsigned long)sz, >+ (type == 0 ? "read" : "write"), location); >+ >+ switch (__mf_opts.mudflap_mode) >+ { >+ case mode_nop: >+ /* It is tempting to poison the cache here similarly to >+ mode_populate. However that eliminates a valuable >+ distinction between these two modes. mode_nop is useful to >+ let a user count & trace every single check / registration >+ call. mode_populate is useful to let a program run fast >+ while unchecked. >+ */ >+ judgement = 1; >+ break; >+ >+ case mode_populate: >+ entry->low = ptr_low; >+ entry->high = ptr_high; >+ judgement = 1; >+ break; >+ >+ case mode_check: >+ { >+ unsigned heuristics = 0; >+ >+ /* Advance aging/adaptation counters. */ >+ static unsigned adapt_count; >+ adapt_count ++; >+ if (UNLIKELY (__mf_opts.adapt_cache > 0 && >+ adapt_count > __mf_opts.adapt_cache)) >+ { >+ adapt_count = 0; >+ __mf_adapt_cache (); >+ } >+ >+ /* Looping only occurs if heuristics were triggered. */ >+ while (judgement == 0) >+ { >+ DECLARE (void, free, void *p); >+ __mf_object_t* ovr_obj[1]; >+ unsigned obj_count; >+ __mf_object_t** all_ovr_obj = NULL; >+ __mf_object_t** dealloc_me = NULL; >+ unsigned i; >+ >+ /* Find all overlapping objects. Be optimistic that there is just one. */ >+ obj_count = __mf_find_objects (ptr_low, ptr_high, ovr_obj, 1); >+ if (UNLIKELY (obj_count > 1)) >+ { >+ /* Allocate a real buffer and do the search again. */ >+ DECLARE (void *, malloc, size_t c); >+ unsigned n; >+ all_ovr_obj = CALL_REAL (malloc, (sizeof (__mf_object_t *) * >+ obj_count)); >+ if (all_ovr_obj == NULL) abort (); >+ n = __mf_find_objects (ptr_low, ptr_high, all_ovr_obj, obj_count); >+ assert (n == obj_count); >+ dealloc_me = all_ovr_obj; >+ } >+ else >+ { >+ all_ovr_obj = ovr_obj; >+ dealloc_me = NULL; >+ } >+ >+ /* Update object statistics. */ >+ for (i = 0; i < obj_count; i++) >+ { >+ __mf_object_t *obj = all_ovr_obj[i]; >+ assert (obj != NULL); >+ if (type == __MF_CHECK_READ) >+ obj->read_count ++; >+ else >+ obj->write_count ++; >+ obj->liveness ++; >+ } >+ >+ /* Iterate over the various objects. There are a number of special cases. */ >+ for (i = 0; i < obj_count; i++) >+ { >+ __mf_object_t *obj = all_ovr_obj[i]; >+ >+ /* Any __MF_TYPE_NOACCESS hit is bad. */ >+ if (UNLIKELY (obj->type == __MF_TYPE_NOACCESS)) >+ judgement = -1; >+ >+ /* Any object with a watch flag is bad. */ >+ if (UNLIKELY (obj->watching_p)) >+ judgement = -2; /* trigger VIOL_WATCH */ >+ >+ /* A read from an uninitialized object is bad. */ >+ if (UNLIKELY (__mf_opts.check_initialization >+ /* reading */ >+ && type == __MF_CHECK_READ >+ /* not written */ >+ && obj->write_count == 0 >+ /* uninitialized (heap) */ >+ && obj->type == __MF_TYPE_HEAP)) >+ judgement = -1; >+ } >+ >+ /* We now know that the access spans no invalid objects. */ >+ if (LIKELY (judgement >= 0)) >+ for (i = 0; i < obj_count; i++) >+ { >+ __mf_object_t *obj = all_ovr_obj[i]; >+ >+ /* Is this access entirely contained within this object? */ >+ if (LIKELY (ptr_low >= obj->low && ptr_high <= obj->high)) >+ { >+ /* Valid access. */ >+ entry->low = obj->low; >+ entry->high = obj->high; >+ judgement = 1; >+ } >+ } >+ >+ /* This access runs off the end of one valid object. That >+ could be okay, if other valid objects fill in all the >+ holes. We allow this only for HEAP and GUESS type >+ objects. Accesses to STATIC and STACK variables >+ should not be allowed to span. */ >+ if (UNLIKELY ((judgement == 0) && (obj_count > 1))) >+ { >+ unsigned uncovered = 0; >+ for (i = 0; i < obj_count; i++) >+ { >+ __mf_object_t *obj = all_ovr_obj[i]; >+ int j, uncovered_low_p, uncovered_high_p; >+ uintptr_t ptr_lower, ptr_higher; >+ >+ uncovered_low_p = ptr_low < obj->low; >+ ptr_lower = CLAMPSUB (obj->low, 1); >+ uncovered_high_p = ptr_high > obj->high; >+ ptr_higher = CLAMPADD (obj->high, 1); >+ >+ for (j = 0; j < obj_count; j++) >+ { >+ __mf_object_t *obj2 = all_ovr_obj[j]; >+ >+ if (i == j) continue; >+ >+ /* Filter out objects that cannot be spanned across. */ >+ if (obj2->type == __MF_TYPE_STACK >+ || obj2->type == __MF_TYPE_STATIC) >+ continue; >+ >+ /* Consider a side "covered" if obj2 includes >+ the next byte on that side. */ >+ if (uncovered_low_p >+ && (ptr_lower >= obj2->low && ptr_lower <= obj2->high)) >+ uncovered_low_p = 0; >+ if (uncovered_high_p >+ && (ptr_high >= obj2->low && ptr_higher <= obj2->high)) >+ uncovered_high_p = 0; >+ } >+ >+ if (uncovered_low_p || uncovered_high_p) >+ uncovered ++; >+ } >+ >+ /* Success if no overlapping objects are uncovered. */ >+ if (uncovered == 0) >+ judgement = 1; >+ } >+ >+ >+ if (dealloc_me != NULL) >+ CALL_REAL (free, dealloc_me); >+ >+ /* If the judgment is still unknown at this stage, loop >+ around at most one more time. */ >+ if (judgement == 0) >+ { >+ if (heuristics++ < 2) /* XXX parametrize this number? */ >+ judgement = __mf_heuristic_check (ptr_low, ptr_high); >+ else >+ judgement = -1; >+ } >+ } >+ >+ } >+ break; >+ >+ case mode_violate: >+ judgement = -1; >+ break; >+ } >+ >+ if (__mf_opts.collect_stats) >+ { >+ __mf_count_check ++; >+ >+ if (LIKELY (old_entry.low != entry->low || old_entry.high != entry->high)) >+ /* && (old_entry.low != 0) && (old_entry.high != 0)) */ >+ __mf_lookup_cache_reusecount [entry_idx] ++; >+ } >+ >+ if (UNLIKELY (judgement < 0)) >+ __mf_violation (ptr, sz, >+ (uintptr_t) __builtin_return_address (0), location, >+ ((judgement == -1) ? >+ (type == __MF_CHECK_READ ? __MF_VIOL_READ : __MF_VIOL_WRITE) : >+ __MF_VIOL_WATCH)); >+} >+ >+ >+static __mf_object_t * >+__mf_insert_new_object (uintptr_t low, uintptr_t high, int type, >+ const char *name, uintptr_t pc) >+{ >+ DECLARE (void *, calloc, size_t c, size_t n); >+ >+ __mf_object_t *new_obj; >+ new_obj = CALL_REAL (calloc, 1, sizeof(__mf_object_t)); >+ new_obj->low = low; >+ new_obj->high = high; >+ new_obj->type = type; >+ new_obj->name = name; >+ new_obj->alloc_pc = pc; >+#if HAVE_GETTIMEOFDAY >+ if (__mf_opts.timestamps) >+ gettimeofday (& new_obj->alloc_time, NULL); >+#endif >+#if LIBMUDFLAPTH >+ new_obj->alloc_thread = pthread_self (); >+#endif >+ >+ if (__mf_opts.backtrace > 0 && (type == __MF_TYPE_HEAP || type == __MF_TYPE_HEAP_I)) >+ new_obj->alloc_backtrace_size = >+ __mf_backtrace (& new_obj->alloc_backtrace, >+ (void *) pc, 2); >+ >+ __mf_link_object (new_obj); >+ return new_obj; >+} >+ >+ >+static void >+__mf_uncache_object (__mf_object_t *old_obj) >+{ >+ /* Remove any low/high pointers for this object from the lookup cache. */ >+ >+ /* Can it possibly exist in the cache? */ >+ if (LIKELY (old_obj->read_count + old_obj->write_count)) >+ { >+ uintptr_t low = old_obj->low; >+ uintptr_t high = old_obj->high; >+ struct __mf_cache *entry; >+ unsigned i; >+ if ((high - low) >= (__mf_lc_mask << __mf_lc_shift)) >+ { >+ /* For large objects (>= cache size - 1) check the whole cache. */ >+ entry = & __mf_lookup_cache [0]; >+ for (i = 0; i <= __mf_lc_mask; i++, entry++) >+ { >+ /* NB: the "||" in the following test permits this code to >+ tolerate the situation introduced by __mf_check over >+ contiguous objects, where a cache entry spans several >+ objects. */ >+ if (entry->low == low || entry->high == high) >+ { >+ entry->low = MAXPTR; >+ entry->high = MINPTR; >+ } >+ } >+ } >+ else >+ { >+ /* Object is now smaller then cache size. */ >+ unsigned entry_low_idx = __MF_CACHE_INDEX (low); >+ unsigned entry_high_idx = __MF_CACHE_INDEX (high); >+ if (entry_low_idx <= entry_high_idx) >+ { >+ entry = & __mf_lookup_cache [entry_low_idx]; >+ for (i = entry_low_idx; i <= entry_high_idx; i++, entry++) >+ { >+ /* NB: the "||" in the following test permits this code to >+ tolerate the situation introduced by __mf_check over >+ contiguous objects, where a cache entry spans several >+ objects. */ >+ if (entry->low == low || entry->high == high) >+ { >+ entry->low = MAXPTR; >+ entry->high = MINPTR; >+ } >+ } >+ } >+ else >+ { >+ /* Object wrapped around the end of the cache. First search >+ from low to end of cache and then from 0 to high. */ >+ entry = & __mf_lookup_cache [entry_low_idx]; >+ for (i = entry_low_idx; i <= __mf_lc_mask; i++, entry++) >+ { >+ /* NB: the "||" in the following test permits this code to >+ tolerate the situation introduced by __mf_check over >+ contiguous objects, where a cache entry spans several >+ objects. */ >+ if (entry->low == low || entry->high == high) >+ { >+ entry->low = MAXPTR; >+ entry->high = MINPTR; >+ } >+ } >+ entry = & __mf_lookup_cache [0]; >+ for (i = 0; i <= entry_high_idx; i++, entry++) >+ { >+ /* NB: the "||" in the following test permits this code to >+ tolerate the situation introduced by __mf_check over >+ contiguous objects, where a cache entry spans several >+ objects. */ >+ if (entry->low == low || entry->high == high) >+ { >+ entry->low = MAXPTR; >+ entry->high = MINPTR; >+ } >+ } >+ } >+ } >+ } >+} >+ >+ >+void >+__mf_register (void *ptr, size_t sz, int type, const char *name) >+{ >+ LOCKTH (); >+ BEGIN_RECURSION_PROTECT (); >+ __mfu_register (ptr, sz, type, name); >+ END_RECURSION_PROTECT (); >+ UNLOCKTH (); >+} >+ >+ >+void >+__mfu_register (void *ptr, size_t sz, int type, const char *name) >+{ >+ TRACE ("register ptr=%p size=%lu type=%x name='%s'\n", >+ ptr, (unsigned long) sz, type, name ? name : ""); >+ >+ if (__mf_opts.collect_stats) >+ { >+ __mf_count_register ++; >+ __mf_total_register_size [(type < 0) ? 0 : >+ (type > __MF_TYPE_MAX) ? 0 : >+ type] += sz; >+ } >+ >+ if (UNLIKELY (__mf_opts.sigusr1_report)) >+ __mf_sigusr1_respond (); >+ >+ switch (__mf_opts.mudflap_mode) >+ { >+ case mode_nop: >+ break; >+ >+ case mode_violate: >+ __mf_violation (ptr, sz, (uintptr_t) __builtin_return_address (0), NULL, >+ __MF_VIOL_REGISTER); >+ break; >+ >+ case mode_populate: >+ /* Clear the cache. */ >+ /* XXX: why the entire cache? */ >+ /* XXX: race */ >+ memset (__mf_lookup_cache, 0, sizeof(__mf_lookup_cache)); >+ /* void slot 0 */ >+ __mf_lookup_cache[0].low = MAXPTR; >+ break; >+ >+ case mode_check: >+ { >+ __mf_object_t *ovr_objs [1]; >+ unsigned num_overlapping_objs; >+ uintptr_t low = (uintptr_t) ptr; >+ uintptr_t high = CLAMPSZ (ptr, sz); >+ uintptr_t pc = (uintptr_t) __builtin_return_address (0); >+ >+ /* Treat unknown size indication as 1. */ >+ if (UNLIKELY (sz == 0)) sz = 1; >+ >+ /* Look for objects only of the same type. This will e.g. permit a registration >+ of a STATIC overlapping with a GUESS, and a HEAP with a NOACCESS. At >+ __mf_check time however harmful overlaps will be detected. */ >+ num_overlapping_objs = __mf_find_objects2 (low, high, ovr_objs, 1, type); >+ >+ /* Handle overlaps. */ >+ if (UNLIKELY (num_overlapping_objs > 0)) >+ { >+ __mf_object_t *ovr_obj = ovr_objs[0]; >+ >+ /* Accept certain specific duplication pairs. */ >+ if (((type == __MF_TYPE_STATIC) || (type == __MF_TYPE_GUESS)) >+ && ovr_obj->low == low >+ && ovr_obj->high == high >+ && ovr_obj->type == type) >+ { >+ /* Duplicate registration for static objects may come >+ from distinct compilation units. */ >+ VERBOSE_TRACE ("harmless duplicate reg %p-%p `%s'\n", >+ (void *) low, (void *) high, >+ (ovr_obj->name ? ovr_obj->name : "")); >+ break; >+ } >+ >+ /* Alas, a genuine violation. */ >+ else >+ { >+ /* Two or more *real* mappings here. */ >+ __mf_violation ((void *) ptr, sz, >+ (uintptr_t) __builtin_return_address (0), NULL, >+ __MF_VIOL_REGISTER); >+ } >+ } >+ else /* No overlapping objects: AOK. */ >+ __mf_insert_new_object (low, high, type, name, pc); >+ >+ /* We could conceivably call __mf_check() here to prime the cache, >+ but then the read_count/write_count field is not reliable. */ >+ break; >+ } >+ } /* end switch (__mf_opts.mudflap_mode) */ >+} >+ >+ >+void >+__mf_unregister (void *ptr, size_t sz, int type) >+{ >+ LOCKTH (); >+ BEGIN_RECURSION_PROTECT (); >+ __mfu_unregister (ptr, sz, type); >+ END_RECURSION_PROTECT (); >+ UNLOCKTH (); >+} >+ >+ >+void >+__mfu_unregister (void *ptr, size_t sz, int type) >+{ >+ DECLARE (void, free, void *ptr); >+ >+ if (UNLIKELY (__mf_opts.sigusr1_report)) >+ __mf_sigusr1_respond (); >+ >+ TRACE ("unregister ptr=%p size=%lu type=%x\n", ptr, (unsigned long) sz, type); >+ >+ switch (__mf_opts.mudflap_mode) >+ { >+ case mode_nop: >+ break; >+ >+ case mode_violate: >+ __mf_violation (ptr, sz, >+ (uintptr_t) __builtin_return_address (0), NULL, >+ __MF_VIOL_UNREGISTER); >+ break; >+ >+ case mode_populate: >+ /* Clear the cache. */ >+ /* XXX: race */ >+ memset (__mf_lookup_cache, 0, sizeof(__mf_lookup_cache)); >+ /* void slot 0 */ >+ __mf_lookup_cache[0].low = MAXPTR; >+ break; >+ >+ case mode_check: >+ { >+ __mf_object_t *old_obj = NULL; >+ __mf_object_t *del_obj = NULL; /* Object to actually delete. */ >+ __mf_object_t *objs[1] = {NULL}; >+ unsigned num_overlapping_objs; >+ >+ num_overlapping_objs = __mf_find_objects2 ((uintptr_t) ptr, >+ CLAMPSZ (ptr, sz), objs, 1, type); >+ >+ /* Special case for HEAP_I - see free & realloc hook. They don't >+ know whether the input region was HEAP or HEAP_I before >+ unmapping it. Here we give HEAP a try in case HEAP_I >+ failed. */ >+ if ((type == __MF_TYPE_HEAP_I) && (num_overlapping_objs == 0)) >+ { >+ num_overlapping_objs = __mf_find_objects2 ((uintptr_t) ptr, >+ CLAMPSZ (ptr, sz), objs, 1, __MF_TYPE_HEAP); >+ } >+ >+ old_obj = objs[0]; >+ if (UNLIKELY ((num_overlapping_objs != 1) /* more than one overlap */ >+ || ((sz == 0) ? 0 : (sz != (old_obj->high - old_obj->low + 1))) /* size mismatch */ >+ || ((uintptr_t) ptr != old_obj->low))) /* base mismatch */ >+ { >+ __mf_violation (ptr, sz, >+ (uintptr_t) __builtin_return_address (0), NULL, >+ __MF_VIOL_UNREGISTER); >+ break; >+ } >+ >+ __mf_unlink_object (old_obj); >+ __mf_uncache_object (old_obj); >+ >+ /* Wipe buffer contents if desired. */ >+ if ((__mf_opts.wipe_stack && old_obj->type == __MF_TYPE_STACK) >+ || (__mf_opts.wipe_heap && (old_obj->type == __MF_TYPE_HEAP >+ || old_obj->type == __MF_TYPE_HEAP_I))) >+ { >+ memset ((void *) old_obj->low, >+ 0, >+ (size_t) (old_obj->high - old_obj->low + 1)); >+ } >+ >+ /* Manage the object cemetary. */ >+ if (__mf_opts.persistent_count > 0 >+ && (unsigned) old_obj->type <= __MF_TYPE_MAX_CEM) >+ { >+ old_obj->deallocated_p = 1; >+ old_obj->dealloc_pc = (uintptr_t) __builtin_return_address (0); >+#if HAVE_GETTIMEOFDAY >+ if (__mf_opts.timestamps) >+ gettimeofday (& old_obj->dealloc_time, NULL); >+#endif >+#ifdef LIBMUDFLAPTH >+ old_obj->dealloc_thread = pthread_self (); >+#endif >+ >+ if (__mf_opts.backtrace > 0 && old_obj->type == __MF_TYPE_HEAP) >+ old_obj->dealloc_backtrace_size = >+ __mf_backtrace (& old_obj->dealloc_backtrace, >+ NULL, 2); >+ >+ /* Encourage this object to be displayed again in current epoch. */ >+ old_obj->description_epoch --; >+ >+ /* Put this object into the cemetary. This may require this plot to >+ be recycled, and the previous resident to be designated del_obj. */ >+ { >+ unsigned row = old_obj->type; >+ unsigned plot = __mf_object_dead_head [row]; >+ >+ del_obj = __mf_object_cemetary [row][plot]; >+ __mf_object_cemetary [row][plot] = old_obj; >+ plot ++; >+ if (plot == __mf_opts.persistent_count) plot = 0; >+ __mf_object_dead_head [row] = plot; >+ } >+ } >+ else >+ del_obj = old_obj; >+ >+ if (__mf_opts.print_leaks) >+ { >+ if ((old_obj->read_count + old_obj->write_count) == 0 && >+ (old_obj->type == __MF_TYPE_HEAP >+ || old_obj->type == __MF_TYPE_HEAP_I)) >+ { >+ /* The problem with a warning message here is that we may not >+ be privy to accesses to such objects that occur within >+ uninstrumented libraries. */ >+#if 0 >+ fprintf (stderr, >+ "*******\n" >+ "mudflap warning: unaccessed registered object:\n"); >+ __mf_describe_object (old_obj); >+#endif >+ } >+ } >+ >+ if (del_obj != NULL) /* May or may not equal old_obj. */ >+ { >+ if (__mf_opts.backtrace > 0) >+ { >+ CALL_REAL(free, del_obj->alloc_backtrace); >+ if (__mf_opts.persistent_count > 0) >+ { >+ CALL_REAL(free, del_obj->dealloc_backtrace); >+ } >+ } >+ CALL_REAL(free, del_obj); >+ } >+ >+ break; >+ } >+ } /* end switch (__mf_opts.mudflap_mode) */ >+ >+ >+ if (__mf_opts.collect_stats) >+ { >+ __mf_count_unregister ++; >+ __mf_total_unregister_size += sz; >+ } >+} >+ >+ >+ >+struct tree_stats >+{ >+ unsigned obj_count; >+ unsigned long total_size; >+ unsigned live_obj_count; >+ double total_weight; >+ double weighted_size; >+ unsigned long weighted_address_bits [sizeof (uintptr_t) * 8][2]; >+}; >+ >+ >+ >+static int >+__mf_adapt_cache_fn (mfsplay_tree_node n, void *param) >+{ >+ __mf_object_t *obj = (__mf_object_t *) n->value; >+ struct tree_stats *s = (struct tree_stats *) param; >+ >+ assert (obj != NULL && s != NULL); >+ >+ /* Exclude never-accessed objects. */ >+ if (obj->read_count + obj->write_count) >+ { >+ s->obj_count ++; >+ s->total_size += (obj->high - obj->low + 1); >+ >+ if (obj->liveness) >+ { >+ unsigned i; >+ uintptr_t addr; >+ >+ /* VERBOSE_TRACE ("analyze low=%p live=%u name=`%s'\n", >+ (void *) obj->low, obj->liveness, obj->name); */ >+ >+ s->live_obj_count ++; >+ s->total_weight += (double) obj->liveness; >+ s->weighted_size += >+ (double) (obj->high - obj->low + 1) * >+ (double) obj->liveness; >+ >+ addr = obj->low; >+ for (i=0; i<sizeof(uintptr_t) * 8; i++) >+ { >+ unsigned bit = addr & 1; >+ s->weighted_address_bits[i][bit] += obj->liveness; >+ addr = addr >> 1; >+ } >+ >+ /* Age the liveness value. */ >+ obj->liveness >>= 1; >+ } >+ } >+ >+ return 0; >+} >+ >+ >+static void >+__mf_adapt_cache () >+{ >+ struct tree_stats s; >+ uintptr_t new_mask = 0; >+ unsigned char new_shift; >+ float cache_utilization; >+ float max_value; >+ static float smoothed_new_shift = -1.0; >+ unsigned i; >+ >+ memset (&s, 0, sizeof (s)); >+ >+ mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_HEAP), __mf_adapt_cache_fn, (void *) & s); >+ mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_HEAP_I), __mf_adapt_cache_fn, (void *) & s); >+ mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_STACK), __mf_adapt_cache_fn, (void *) & s); >+ mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_STATIC), __mf_adapt_cache_fn, (void *) & s); >+ mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_GUESS), __mf_adapt_cache_fn, (void *) & s); >+ >+ /* Maybe we're dealing with funny aging/adaptation parameters, or an >+ empty tree. Just leave the cache alone in such cases, rather >+ than risk dying by division-by-zero. */ >+ if (! (s.obj_count > 0) && (s.live_obj_count > 0) && (s.total_weight > 0.0)) >+ return; >+ >+ /* Guess a good value for the shift parameter by finding an address bit that is a >+ good discriminant of lively objects. */ >+ max_value = 0.0; >+ for (i=0; i<sizeof (uintptr_t)*8; i++) >+ { >+ float value = (float) s.weighted_address_bits[i][0] * (float) s.weighted_address_bits[i][1]; >+ if (max_value < value) max_value = value; >+ } >+ for (i=0; i<sizeof (uintptr_t)*8; i++) >+ { >+ float shoulder_factor = 0.7; /* Include slightly less popular bits too. */ >+ float value = (float) s.weighted_address_bits[i][0] * (float) s.weighted_address_bits[i][1]; >+ if (value >= max_value * shoulder_factor) >+ break; >+ } >+ if (smoothed_new_shift < 0) smoothed_new_shift = __mf_lc_shift; >+ /* Converge toward this slowly to reduce flapping. */ >+ smoothed_new_shift = 0.9*smoothed_new_shift + 0.1*i; >+ new_shift = (unsigned) (smoothed_new_shift + 0.5); >+ assert (new_shift < sizeof (uintptr_t)*8); >+ >+ /* Count number of used buckets. */ >+ cache_utilization = 0.0; >+ for (i = 0; i < (1 + __mf_lc_mask); i++) >+ if (__mf_lookup_cache[i].low != 0 || __mf_lookup_cache[i].high != 0) >+ cache_utilization += 1.0; >+ cache_utilization /= (1 + __mf_lc_mask); >+ >+ new_mask |= 0xffff; /* XXX: force a large cache. */ >+ new_mask &= (LOOKUP_CACHE_SIZE_MAX - 1); >+ >+ VERBOSE_TRACE ("adapt cache obj=%u/%u sizes=%lu/%.0f/%.0f => " >+ "util=%u%% m=%p s=%u\n", >+ s.obj_count, s.live_obj_count, s.total_size, s.total_weight, s.weighted_size, >+ (unsigned)(cache_utilization*100.0), (void *) new_mask, new_shift); >+ >+ /* We should reinitialize cache if its parameters have changed. */ >+ if (new_mask != __mf_lc_mask || >+ new_shift != __mf_lc_shift) >+ { >+ __mf_lc_mask = new_mask; >+ __mf_lc_shift = new_shift; >+ /* XXX: race */ >+ memset (__mf_lookup_cache, 0, sizeof(__mf_lookup_cache)); >+ /* void slot 0 */ >+ __mf_lookup_cache[0].low = MAXPTR; >+ } >+} >+ >+ >+ >+/* __mf_find_object[s] */ >+ >+/* Find overlapping live objecs between [low,high]. Return up to >+ max_objs of their pointers in objs[]. Return total count of >+ overlaps (may exceed max_objs). */ >+ >+unsigned >+__mf_find_objects2 (uintptr_t ptr_low, uintptr_t ptr_high, >+ __mf_object_t **objs, unsigned max_objs, int type) >+{ >+ unsigned count = 0; >+ mfsplay_tree t = __mf_object_tree (type); >+ mfsplay_tree_key k = (mfsplay_tree_key) ptr_low; >+ int direction; >+ >+ mfsplay_tree_node n = mfsplay_tree_lookup (t, k); >+ /* An exact match for base address implies a hit. */ >+ if (n != NULL) >+ { >+ if (count < max_objs) >+ objs[count] = (__mf_object_t *) n->value; >+ count ++; >+ } >+ >+ /* Iterate left then right near this key value to find all overlapping objects. */ >+ for (direction = 0; direction < 2; direction ++) >+ { >+ /* Reset search origin. */ >+ k = (mfsplay_tree_key) ptr_low; >+ >+ while (1) >+ { >+ __mf_object_t *obj; >+ >+ n = (direction == 0 ? mfsplay_tree_successor (t, k) : mfsplay_tree_predecessor (t, k)); >+ if (n == NULL) break; >+ obj = (__mf_object_t *) n->value; >+ >+ if (! (obj->low <= ptr_high && obj->high >= ptr_low)) /* No overlap? */ >+ break; >+ >+ if (count < max_objs) >+ objs[count] = (__mf_object_t *) n->value; >+ count ++; >+ >+ k = (mfsplay_tree_key) obj->low; >+ } >+ } >+ >+ return count; >+} >+ >+ >+unsigned >+__mf_find_objects (uintptr_t ptr_low, uintptr_t ptr_high, >+ __mf_object_t **objs, unsigned max_objs) >+{ >+ int type; >+ unsigned count = 0; >+ >+ /* Search each splay tree for overlaps. */ >+ for (type = __MF_TYPE_NOACCESS; type <= __MF_TYPE_GUESS; type++) >+ { >+ unsigned c = __mf_find_objects2 (ptr_low, ptr_high, objs, max_objs, type); >+ if (c > max_objs) >+ { >+ max_objs = 0; >+ objs = NULL; >+ } >+ else /* NB: C may equal 0 */ >+ { >+ max_objs -= c; >+ objs += c; >+ } >+ count += c; >+ } >+ >+ return count; >+} >+ >+ >+ >+/* __mf_link_object */ >+ >+static void >+__mf_link_object (__mf_object_t *node) >+{ >+ mfsplay_tree t = __mf_object_tree (node->type); >+ mfsplay_tree_insert (t, (mfsplay_tree_key) node->low, (mfsplay_tree_value) node); >+} >+ >+/* __mf_unlink_object */ >+ >+static void >+__mf_unlink_object (__mf_object_t *node) >+{ >+ mfsplay_tree t = __mf_object_tree (node->type); >+ mfsplay_tree_remove (t, (mfsplay_tree_key) node->low); >+} >+ >+/* __mf_find_dead_objects */ >+ >+/* Find overlapping dead objecs between [low,high]. Return up to >+ max_objs of their pointers in objs[]. Return total count of >+ overlaps (may exceed max_objs). */ >+ >+static unsigned >+__mf_find_dead_objects (uintptr_t low, uintptr_t high, >+ __mf_object_t **objs, unsigned max_objs) >+{ >+ if (__mf_opts.persistent_count > 0) >+ { >+ unsigned count = 0; >+ unsigned recollection = 0; >+ unsigned row = 0; >+ >+ assert (low <= high); >+ assert (max_objs == 0 || objs != NULL); >+ >+ /* Widen the search from the most recent plots in each row, looking >+ backward in time. */ >+ recollection = 0; >+ while (recollection < __mf_opts.persistent_count) >+ { >+ count = 0; >+ >+ for (row = 0; row <= __MF_TYPE_MAX_CEM; row ++) >+ { >+ unsigned plot; >+ unsigned i; >+ >+ plot = __mf_object_dead_head [row]; >+ for (i = 0; i <= recollection; i ++) >+ { >+ __mf_object_t *obj; >+ >+ /* Look backward through row: it's a circular buffer. */ >+ if (plot > 0) plot --; >+ else plot = __mf_opts.persistent_count - 1; >+ >+ obj = __mf_object_cemetary [row][plot]; >+ if (obj && obj->low <= high && obj->high >= low) >+ { >+ /* Found an overlapping dead object! */ >+ if (count < max_objs) >+ objs [count] = obj; >+ count ++; >+ } >+ } >+ } >+ >+ if (count) >+ break; >+ >+ /* Look farther back in time. */ >+ recollection = (recollection * 2) + 1; >+ } >+ >+ return count; >+ } else { >+ return 0; >+ } >+} >+ >+/* __mf_describe_object */ >+ >+static void >+__mf_describe_object (__mf_object_t *obj) >+{ >+ static unsigned epoch = 0; >+ if (obj == NULL) >+ { >+ epoch ++; >+ return; >+ } >+ >+ if (__mf_opts.abbreviate && obj->description_epoch == epoch) >+ { >+ fprintf (stderr, >+ "mudflap %sobject %p: name=`%s'\n", >+ (obj->deallocated_p ? "dead " : ""), >+ (void *) obj, (obj->name ? obj->name : "")); >+ return; >+ } >+ else >+ obj->description_epoch = epoch; >+ >+ fprintf (stderr, >+ "mudflap %sobject %p: name=`%s'\n" >+ "bounds=[%p,%p] size=%lu area=%s check=%ur/%uw liveness=%u%s\n" >+ "alloc time=%lu.%06lu pc=%p" >+#ifdef LIBMUDFLAPTH >+ " thread=%u" >+#endif >+ "\n", >+ (obj->deallocated_p ? "dead " : ""), >+ (void *) obj, (obj->name ? obj->name : ""), >+ (void *) obj->low, (void *) obj->high, >+ (unsigned long) (obj->high - obj->low + 1), >+ (obj->type == __MF_TYPE_NOACCESS ? "no-access" : >+ obj->type == __MF_TYPE_HEAP ? "heap" : >+ obj->type == __MF_TYPE_HEAP_I ? "heap-init" : >+ obj->type == __MF_TYPE_STACK ? "stack" : >+ obj->type == __MF_TYPE_STATIC ? "static" : >+ obj->type == __MF_TYPE_GUESS ? "guess" : >+ "unknown"), >+ obj->read_count, obj->write_count, obj->liveness, >+ obj->watching_p ? " watching" : "", >+ obj->alloc_time.tv_sec, obj->alloc_time.tv_usec, >+ (void *) obj->alloc_pc >+#ifdef LIBMUDFLAPTH >+ , (unsigned) obj->alloc_thread >+#endif >+ ); >+ >+ if (__mf_opts.backtrace > 0) >+ { >+ unsigned i; >+ for (i=0; i<obj->alloc_backtrace_size; i++) >+ fprintf (stderr, " %s\n", obj->alloc_backtrace[i]); >+ } >+ >+ if (__mf_opts.persistent_count > 0) >+ { >+ if (obj->deallocated_p) >+ { >+ fprintf (stderr, "dealloc time=%lu.%06lu pc=%p" >+#ifdef LIBMUDFLAPTH >+ " thread=%u" >+#endif >+ "\n", >+ obj->dealloc_time.tv_sec, obj->dealloc_time.tv_usec, >+ (void *) obj->dealloc_pc >+#ifdef LIBMUDFLAPTH >+ , (unsigned) obj->dealloc_thread >+#endif >+ ); >+ >+ >+ if (__mf_opts.backtrace > 0) >+ { >+ unsigned i; >+ for (i=0; i<obj->dealloc_backtrace_size; i++) >+ fprintf (stderr, " %s\n", obj->dealloc_backtrace[i]); >+ } >+ } >+ } >+} >+ >+ >+static int >+__mf_report_leaks_fn (mfsplay_tree_node n, void *param) >+{ >+ __mf_object_t *node = (__mf_object_t *) n->value; >+ unsigned *count = (unsigned *) param; >+ >+ if (count != NULL) >+ (*count) ++; >+ >+ fprintf (stderr, "Leaked object %u:\n", (*count)); >+ __mf_describe_object (node); >+ >+ return 0; >+} >+ >+ >+static unsigned >+__mf_report_leaks () >+{ >+ unsigned count = 0; >+ >+ (void) mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_HEAP), >+ __mf_report_leaks_fn, & count); >+ (void) mfsplay_tree_foreach (__mf_object_tree (__MF_TYPE_HEAP_I), >+ __mf_report_leaks_fn, & count); >+ >+ return count; >+} >+ >+/* ------------------------------------------------------------------------ */ >+/* __mf_report */ >+ >+void >+__mf_report () >+{ >+ LOCKTH (); >+ BEGIN_RECURSION_PROTECT (); >+ __mfu_report (); >+ END_RECURSION_PROTECT (); >+ UNLOCKTH (); >+} >+ >+void >+__mfu_report () >+{ >+ if (__mf_opts.collect_stats) >+ { >+ fprintf (stderr, >+ "*******\n" >+ "mudflap stats:\n" >+ "calls to __mf_check: %lu\n" >+ " __mf_register: %lu [%luB, %luB, %luB, %luB, %luB]\n" >+ " __mf_unregister: %lu [%luB]\n" >+ " __mf_violation: [%lu, %lu, %lu, %lu, %lu]\n", >+ __mf_count_check, >+ __mf_count_register, >+ __mf_total_register_size[0], __mf_total_register_size[1], >+ __mf_total_register_size[2], __mf_total_register_size[3], >+ __mf_total_register_size[4], /* XXX */ >+ __mf_count_unregister, __mf_total_unregister_size, >+ __mf_count_violation[0], __mf_count_violation[1], >+ __mf_count_violation[2], __mf_count_violation[3], >+ __mf_count_violation[4]); >+ >+ fprintf (stderr, >+ "calls with reentrancy: %lu\n", __mf_reentrancy); >+#ifdef LIBMUDFLAPTH >+ fprintf (stderr, >+ " lock contention: %lu\n", __mf_lock_contention); >+#endif >+ >+ /* Lookup cache stats. */ >+ { >+ unsigned i; >+ unsigned max_reuse = 0; >+ unsigned num_used = 0; >+ unsigned num_unused = 0; >+ >+ for (i = 0; i < LOOKUP_CACHE_SIZE; i++) >+ { >+ if (__mf_lookup_cache_reusecount[i]) >+ num_used ++; >+ else >+ num_unused ++; >+ if (max_reuse < __mf_lookup_cache_reusecount[i]) >+ max_reuse = __mf_lookup_cache_reusecount[i]; >+ } >+ fprintf (stderr, "lookup cache slots used: %u unused: %u peak-reuse: %u\n", >+ num_used, num_unused, max_reuse); >+ } >+ >+ { >+ unsigned live_count; >+ live_count = __mf_find_objects (MINPTR, MAXPTR, NULL, 0); >+ fprintf (stderr, "number of live objects: %u\n", live_count); >+ } >+ >+ if (__mf_opts.persistent_count > 0) >+ { >+ unsigned dead_count = 0; >+ unsigned row, plot; >+ for (row = 0; row <= __MF_TYPE_MAX_CEM; row ++) >+ for (plot = 0 ; plot < __mf_opts.persistent_count; plot ++) >+ if (__mf_object_cemetary [row][plot] != 0) >+ dead_count ++; >+ fprintf (stderr, " zombie objects: %u\n", dead_count); >+ } >+ } >+ if (__mf_opts.print_leaks && (__mf_opts.mudflap_mode == mode_check)) >+ { >+ unsigned l; >+ extern void * __mf_wrap_alloca_indirect (size_t c); >+ >+ /* Free up any remaining alloca()'d blocks. */ >+ __mf_wrap_alloca_indirect (0); >+#ifdef HAVE___LIBC_FREERES >+ if (__mf_opts.call_libc_freeres) >+ { >+ extern void __libc_freeres (void); >+ __libc_freeres (); >+ } >+#endif >+ >+ __mf_describe_object (NULL); /* Reset description epoch. */ >+ l = __mf_report_leaks (); >+ fprintf (stderr, "number of leaked objects: %u\n", l); >+ } >+} >+ >+/* __mf_backtrace */ >+ >+size_t >+__mf_backtrace (char ***symbols, void *guess_pc, unsigned guess_omit_levels) >+{ >+ void ** pc_array; >+ unsigned pc_array_size = __mf_opts.backtrace + guess_omit_levels; >+ unsigned remaining_size; >+ unsigned omitted_size = 0; >+ unsigned i; >+ DECLARE (void, free, void *ptr); >+ DECLARE (void *, calloc, size_t c, size_t n); >+ DECLARE (void *, malloc, size_t n); >+ >+ pc_array = CALL_REAL (calloc, pc_array_size, sizeof (void *) ); >+#ifdef HAVE_BACKTRACE >+ pc_array_size = backtrace (pc_array, pc_array_size); >+#else >+#define FETCH(n) do { if (pc_array_size >= n) { \ >+ pc_array[n] = __builtin_return_address(n); \ >+ if (pc_array[n] == 0) pc_array_size = n; } } while (0) >+ >+ /* Unroll some calls __builtin_return_address because this function >+ only takes a literal integer parameter. */ >+ FETCH (0); >+#if 0 >+ /* XXX: __builtin_return_address sometimes crashes (!) on >0 arguments, >+ rather than simply returning 0. :-( */ >+ FETCH (1); >+ FETCH (2); >+ FETCH (3); >+ FETCH (4); >+ FETCH (5); >+ FETCH (6); >+ FETCH (7); >+ FETCH (8); >+ if (pc_array_size > 8) pc_array_size = 9; >+#else >+ if (pc_array_size > 0) pc_array_size = 1; >+#endif >+ >+#undef FETCH >+#endif >+ >+ /* We want to trim the first few levels of the stack traceback, >+ since they contain libmudflap wrappers and junk. If pc_array[] >+ ends up containing a non-NULL guess_pc, then trim everything >+ before that. Otherwise, omit the first guess_omit_levels >+ entries. */ >+ >+ if (guess_pc != NULL) >+ for (i=0; i<pc_array_size; i++) >+ if (pc_array [i] == guess_pc) >+ omitted_size = i; >+ >+ if (omitted_size == 0) /* No match? */ >+ if (pc_array_size > guess_omit_levels) >+ omitted_size = guess_omit_levels; >+ >+ remaining_size = pc_array_size - omitted_size; >+ >+#ifdef HAVE_BACKTRACE_SYMBOLS >+ *symbols = backtrace_symbols (pc_array + omitted_size, remaining_size); >+#else >+ { >+ /* Let's construct a buffer by hand. It will have <remaining_size> >+ char*'s at the front, pointing at individual strings immediately >+ afterwards. */ >+ void *buffer; >+ char *chars; >+ char **pointers; >+ enum { perline = 30 }; >+ buffer = CALL_REAL (malloc, remaining_size * (perline + sizeof(char *))); >+ pointers = (char **) buffer; >+ chars = (char *)buffer + (remaining_size * sizeof (char *)); >+ for (i = 0; i < remaining_size; i++) >+ { >+ pointers[i] = chars; >+ sprintf (chars, "[0x%p]", pc_array [omitted_size + i]); >+ chars = chars + perline; >+ } >+ *symbols = pointers; >+ } >+#endif >+ CALL_REAL (free, pc_array); >+ >+ return remaining_size; >+} >+ >+/* ------------------------------------------------------------------------ */ >+/* __mf_violation */ >+ >+void >+__mf_violation (void *ptr, size_t sz, uintptr_t pc, >+ const char *location, int type) >+{ >+ char buf [128]; >+ static unsigned violation_number; >+ DECLARE(void, free, void *ptr); >+ >+ TRACE ("violation pc=%p location=%s type=%d ptr=%p size=%lu\n", >+ (void *) pc, >+ (location != NULL ? location : ""), type, ptr, (unsigned long) sz); >+ >+ if (__mf_opts.collect_stats) >+ __mf_count_violation [(type < 0) ? 0 : >+ (type > __MF_VIOL_WATCH) ? 0 : >+ type] ++; >+ >+ /* Print out a basic warning message. */ >+ if (__mf_opts.verbose_violations) >+ { >+ unsigned dead_p; >+ unsigned num_helpful = 0; >+ struct timeval now = { 0, 0 }; >+#if HAVE_GETTIMEOFDAY >+ gettimeofday (& now, NULL); >+#endif >+ >+ violation_number ++; >+ fprintf (stderr, >+ "*******\n" >+ "mudflap violation %u (%s): time=%lu.%06lu " >+ "ptr=%p size=%lu\npc=%p%s%s%s\n", >+ violation_number, >+ ((type == __MF_VIOL_READ) ? "check/read" : >+ (type == __MF_VIOL_WRITE) ? "check/write" : >+ (type == __MF_VIOL_REGISTER) ? "register" : >+ (type == __MF_VIOL_UNREGISTER) ? "unregister" : >+ (type == __MF_VIOL_WATCH) ? "watch" : "unknown"), >+ now.tv_sec, now.tv_usec, >+ (void *) ptr, (unsigned long)sz, (void *) pc, >+ (location != NULL ? " location=`" : ""), >+ (location != NULL ? location : ""), >+ (location != NULL ? "'" : "")); >+ >+ if (__mf_opts.backtrace > 0) >+ { >+ char ** symbols; >+ unsigned i, num; >+ >+ num = __mf_backtrace (& symbols, (void *) pc, 2); >+ /* Note: backtrace_symbols calls malloc(). But since we're in >+ __mf_violation and presumably __mf_check, it'll detect >+ recursion, and not put the new string into the database. */ >+ >+ for (i=0; i<num; i++) >+ fprintf (stderr, " %s\n", symbols[i]); >+ >+ /* Calling free() here would trigger a violation. */ >+ CALL_REAL(free, symbols); >+ } >+ >+ >+ /* Look for nearby objects. For this, we start with s_low/s_high >+ pointing to the given area, looking for overlapping objects. >+ If none show up, widen the search area and keep looking. */ >+ >+ if (sz == 0) sz = 1; >+ >+ for (dead_p = 0; dead_p <= 1; dead_p ++) /* for dead_p in 0 1 */ >+ { >+ enum {max_objs = 3}; /* magic */ >+ __mf_object_t *objs[max_objs]; >+ unsigned num_objs = 0; >+ uintptr_t s_low, s_high; >+ unsigned tries = 0; >+ unsigned i; >+ >+ s_low = (uintptr_t) ptr; >+ s_high = CLAMPSZ (ptr, sz); >+ >+ while (tries < 16) /* magic */ >+ { >+ if (dead_p) >+ num_objs = __mf_find_dead_objects (s_low, s_high, objs, max_objs); >+ else >+ num_objs = __mf_find_objects (s_low, s_high, objs, max_objs); >+ >+ if (num_objs) /* good enough */ >+ break; >+ >+ tries ++; >+ >+ /* XXX: tune this search strategy. It's too dependent on >+ sz, which can vary from 1 to very big (when array index >+ checking) numbers. */ >+ s_low = CLAMPSUB (s_low, (sz * tries * tries)); >+ s_high = CLAMPADD (s_high, (sz * tries * tries)); >+ } >+ >+ for (i = 0; i < min (num_objs, max_objs); i++) >+ { >+ __mf_object_t *obj = objs[i]; >+ uintptr_t low = (uintptr_t) ptr; >+ uintptr_t high = CLAMPSZ (ptr, sz); >+ unsigned before1 = (low < obj->low) ? obj->low - low : 0; >+ unsigned after1 = (low > obj->high) ? low - obj->high : 0; >+ unsigned into1 = (high >= obj->low && low <= obj->high) ? low - obj->low : 0; >+ unsigned before2 = (high < obj->low) ? obj->low - high : 0; >+ unsigned after2 = (high > obj->high) ? high - obj->high : 0; >+ unsigned into2 = (high >= obj->low && low <= obj->high) ? high - obj->low : 0; >+ >+ fprintf (stderr, "Nearby object %u: checked region begins %uB %s and ends %uB %s\n", >+ num_helpful + i + 1, >+ (before1 ? before1 : after1 ? after1 : into1), >+ (before1 ? "before" : after1 ? "after" : "into"), >+ (before2 ? before2 : after2 ? after2 : into2), >+ (before2 ? "before" : after2 ? "after" : "into")); >+ __mf_describe_object (obj); >+ } >+ num_helpful += num_objs; >+ } >+ >+ fprintf (stderr, "number of nearby objects: %u\n", num_helpful); >+ } >+ >+ /* How to finally handle this violation? */ >+ switch (__mf_opts.violation_mode) >+ { >+ case viol_nop: >+ break; >+ case viol_segv: >+ kill (getpid(), SIGSEGV); >+ break; >+ case viol_abort: >+ abort (); >+ break; >+ case viol_gdb: >+ >+ snprintf (buf, 128, "gdb --pid=%u", (unsigned) getpid ()); >+ system (buf); >+ /* XXX: should probably fork() && sleep(GDB_WAIT_PARAMETER) >+ instead, and let the forked child execlp() gdb. That way, this >+ subject process can be resumed under the supervision of gdb. >+ This can't happen now, since system() only returns when gdb >+ dies. In that case, we need to beware of starting a second >+ concurrent gdb child upon the next violation. (But if the first >+ gdb dies, then starting a new one is appropriate.) */ >+ break; >+ } >+} >+ >+/* ------------------------------------------------------------------------ */ >+ >+ >+unsigned __mf_watch (void *ptr, size_t sz) >+{ >+ unsigned rc; >+ LOCKTH (); >+ BEGIN_RECURSION_PROTECT (); >+ rc = __mf_watch_or_not (ptr, sz, 1); >+ END_RECURSION_PROTECT (); >+ UNLOCKTH (); >+ return rc; >+} >+ >+unsigned __mf_unwatch (void *ptr, size_t sz) >+{ >+ unsigned rc; >+ LOCKTH (); >+ rc = __mf_watch_or_not (ptr, sz, 0); >+ UNLOCKTH (); >+ return rc; >+} >+ >+ >+static unsigned >+__mf_watch_or_not (void *ptr, size_t sz, char flag) >+{ >+ uintptr_t ptr_high = CLAMPSZ (ptr, sz); >+ uintptr_t ptr_low = (uintptr_t) ptr; >+ unsigned count = 0; >+ >+ TRACE ("%s ptr=%p size=%lu\n", >+ (flag ? "watch" : "unwatch"), ptr, (unsigned long) sz); >+ >+ switch (__mf_opts.mudflap_mode) >+ { >+ case mode_nop: >+ case mode_populate: >+ case mode_violate: >+ count = 0; >+ break; >+ >+ case mode_check: >+ { >+ __mf_object_t **all_ovr_objs; >+ unsigned obj_count; >+ unsigned n; >+ DECLARE (void *, malloc, size_t c); >+ DECLARE (void, free, void *p); >+ >+ obj_count = __mf_find_objects (ptr_low, ptr_high, NULL, 0); >+ VERBOSE_TRACE (" %u:", obj_count); >+ >+ all_ovr_objs = CALL_REAL (malloc, (sizeof (__mf_object_t *) * obj_count)); >+ if (all_ovr_objs == NULL) abort (); >+ n = __mf_find_objects (ptr_low, ptr_high, all_ovr_objs, obj_count); >+ assert (n == obj_count); >+ >+ for (n = 0; n < obj_count; n ++) >+ { >+ __mf_object_t *obj = all_ovr_objs[n]; >+ >+ VERBOSE_TRACE (" [%p]", (void *) obj); >+ if (obj->watching_p != flag) >+ { >+ obj->watching_p = flag; >+ count ++; >+ >+ /* Remove object from cache, to ensure next access >+ goes through __mf_check(). */ >+ if (flag) >+ __mf_uncache_object (obj); >+ } >+ } >+ CALL_REAL (free, all_ovr_objs); >+ } >+ break; >+ } >+ >+ return count; >+} >+ >+ >+void >+__mf_sigusr1_handler (int num) >+{ >+ __mf_sigusr1_received ++; >+} >+ >+/* Install or remove SIGUSR1 handler as necessary. >+ Also, respond to a received pending SIGUSR1. */ >+void >+__mf_sigusr1_respond () >+{ >+ static int handler_installed; >+ >+#ifdef SIGUSR1 >+ /* Manage handler */ >+ if (__mf_opts.sigusr1_report && ! handler_installed) >+ { >+ signal (SIGUSR1, __mf_sigusr1_handler); >+ handler_installed = 1; >+ } >+ else if(! __mf_opts.sigusr1_report && handler_installed) >+ { >+ signal (SIGUSR1, SIG_DFL); >+ handler_installed = 0; >+ } >+#endif >+ >+ /* Manage enqueued signals */ >+ if (__mf_sigusr1_received > __mf_sigusr1_handled) >+ { >+ __mf_sigusr1_handled ++; >+ assert (__mf_get_state () == reentrant); >+ __mfu_report (); >+ handler_installed = 0; /* We may need to re-enable signal; this might be a SysV library. */ >+ } >+} >+ >+ >+/* XXX: provide an alternative __assert_fail function that cannot >+ fail due to libmudflap infinite recursion. */ >+#ifndef NDEBUG >+ >+static void >+write_itoa (int fd, unsigned n) >+{ >+ enum x { bufsize = sizeof(n)*4 }; >+ char buf [bufsize]; >+ unsigned i; >+ >+ for (i=0; i<bufsize-1; i++) >+ { >+ unsigned digit = n % 10; >+ buf[bufsize-2-i] = digit + '0'; >+ n /= 10; >+ if (n == 0) >+ { >+ char *m = & buf [bufsize-2-i]; >+ buf[bufsize-1] = '\0'; >+ write (fd, m, strlen(m)); >+ break; >+ } >+ } >+} >+ >+ >+void >+__assert_fail (const char *msg, const char *file, unsigned line, const char *func) >+{ >+#define write2(string) write (2, (string), strlen ((string))); >+ write2("mf"); >+#ifdef LIBMUDFLAPTH >+ write2("("); >+ write_itoa (2, (unsigned) pthread_self ()); >+ write2(")"); >+#endif >+ write2(": assertion failure: `"); >+ write (2, msg, strlen (msg)); >+ write2("' in "); >+ write (2, func, strlen (func)); >+ write2(" at "); >+ write (2, file, strlen (file)); >+ write2(":"); >+ write_itoa (2, line); >+ write2("\n"); >+#undef write2 >+ abort (); >+} >+ >+ >+#endif >+ >+ >+ >+/* Adapted splay tree code, originally from libiberty. It has been >+ specialized for libmudflap as requested by RMS. */ >+ >+static void >+mfsplay_tree_free (void *p) >+{ >+ DECLARE (void, free, void *p); >+ CALL_REAL (free, p); >+} >+ >+static void * >+mfsplay_tree_xmalloc (size_t s) >+{ >+ DECLARE (void *, malloc, size_t s); >+ return CALL_REAL (malloc, s); >+} >+ >+ >+static void mfsplay_tree_splay (mfsplay_tree, mfsplay_tree_key); >+static mfsplay_tree_node mfsplay_tree_splay_helper (mfsplay_tree, >+ mfsplay_tree_key, >+ mfsplay_tree_node *, >+ mfsplay_tree_node *, >+ mfsplay_tree_node *); >+ >+ >+/* Help splay SP around KEY. PARENT and GRANDPARENT are the parent >+ and grandparent, respectively, of NODE. */ >+ >+static mfsplay_tree_node >+mfsplay_tree_splay_helper (mfsplay_tree sp, >+ mfsplay_tree_key key, >+ mfsplay_tree_node * node, >+ mfsplay_tree_node * parent, >+ mfsplay_tree_node * grandparent) >+{ >+ mfsplay_tree_node *next; >+ mfsplay_tree_node n; >+ int comparison; >+ >+ n = *node; >+ >+ if (!n) >+ return *parent; >+ >+ comparison = ((key > n->key) ? 1 : ((key < n->key) ? -1 : 0)); >+ >+ if (comparison == 0) >+ /* We've found the target. */ >+ next = 0; >+ else if (comparison < 0) >+ /* The target is to the left. */ >+ next = &n->left; >+ else >+ /* The target is to the right. */ >+ next = &n->right; >+ >+ if (next) >+ { >+ /* Check whether our recursion depth is too high. Abort this search, >+ and signal that a rebalance is required to continue. */ >+ if (sp->depth > sp->max_depth) >+ { >+ sp->rebalance_p = 1; >+ return n; >+ } >+ >+ /* Continue down the tree. */ >+ sp->depth ++; >+ n = mfsplay_tree_splay_helper (sp, key, next, node, parent); >+ sp->depth --; >+ >+ /* The recursive call will change the place to which NODE >+ points. */ >+ if (*node != n || sp->rebalance_p) >+ return n; >+ } >+ >+ if (!parent) >+ /* NODE is the root. We are done. */ >+ return n; >+ >+ /* First, handle the case where there is no grandparent (i.e., >+ *PARENT is the root of the tree.) */ >+ if (!grandparent) >+ { >+ if (n == (*parent)->left) >+ { >+ *node = n->right; >+ n->right = *parent; >+ } >+ else >+ { >+ *node = n->left; >+ n->left = *parent; >+ } >+ *parent = n; >+ return n; >+ } >+ >+ /* Next handle the cases where both N and *PARENT are left children, >+ or where both are right children. */ >+ if (n == (*parent)->left && *parent == (*grandparent)->left) >+ { >+ mfsplay_tree_node p = *parent; >+ >+ (*grandparent)->left = p->right; >+ p->right = *grandparent; >+ p->left = n->right; >+ n->right = p; >+ *grandparent = n; >+ return n; >+ } >+ else if (n == (*parent)->right && *parent == (*grandparent)->right) >+ { >+ mfsplay_tree_node p = *parent; >+ >+ (*grandparent)->right = p->left; >+ p->left = *grandparent; >+ p->right = n->left; >+ n->left = p; >+ *grandparent = n; >+ return n; >+ } >+ >+ /* Finally, deal with the case where N is a left child, but *PARENT >+ is a right child, or vice versa. */ >+ if (n == (*parent)->left) >+ { >+ (*parent)->left = n->right; >+ n->right = *parent; >+ (*grandparent)->right = n->left; >+ n->left = *grandparent; >+ *grandparent = n; >+ return n; >+ } >+ else >+ { >+ (*parent)->right = n->left; >+ n->left = *parent; >+ (*grandparent)->left = n->right; >+ n->right = *grandparent; >+ *grandparent = n; >+ return n; >+ } >+} >+ >+ >+ >+static int >+mfsplay_tree_rebalance_helper1 (mfsplay_tree_node n, void *array_ptr) >+{ >+ mfsplay_tree_node **p = array_ptr; >+ *(*p) = n; >+ (*p)++; >+ return 0; >+} >+ >+ >+static mfsplay_tree_node >+mfsplay_tree_rebalance_helper2 (mfsplay_tree_node * array, unsigned low, >+ unsigned high) >+{ >+ unsigned middle = low + (high - low) / 2; >+ mfsplay_tree_node n = array[middle]; >+ >+ /* Note that since we're producing a balanced binary tree, it is not a problem >+ that this function is recursive. */ >+ if (low + 1 <= middle) >+ n->left = mfsplay_tree_rebalance_helper2 (array, low, middle - 1); >+ else >+ n->left = NULL; >+ >+ if (middle + 1 <= high) >+ n->right = mfsplay_tree_rebalance_helper2 (array, middle + 1, high); >+ else >+ n->right = NULL; >+ >+ return n; >+} >+ >+ >+/* Rebalance the entire tree. Do this by copying all the node >+ pointers into an array, then cleverly re-linking them. */ >+static void >+mfsplay_tree_rebalance (mfsplay_tree sp) >+{ >+ mfsplay_tree_node *all_nodes, *all_nodes_1; >+ >+ if (sp->num_keys <= 2) >+ return; >+ >+ all_nodes = mfsplay_tree_xmalloc (sizeof (mfsplay_tree_node) * sp->num_keys); >+ >+ /* Traverse all nodes to copy their addresses into this array. */ >+ all_nodes_1 = all_nodes; >+ mfsplay_tree_foreach (sp, mfsplay_tree_rebalance_helper1, >+ (void *) &all_nodes_1); >+ >+ /* Relink all the nodes. */ >+ sp->root = mfsplay_tree_rebalance_helper2 (all_nodes, 0, sp->num_keys - 1); >+ >+ mfsplay_tree_free (all_nodes); >+} >+ >+ >+/* Splay SP around KEY. */ >+static void >+mfsplay_tree_splay (mfsplay_tree sp, mfsplay_tree_key key) >+{ >+ if (sp->root == 0) >+ return; >+ >+ /* If we just splayed the tree with the same key, do nothing. */ >+ if (sp->last_splayed_key_p && >+ (sp->last_splayed_key == key)) >+ return; >+ >+ /* Compute a maximum recursion depth for a splay tree with NUM nodes. >+ The idea is to limit excessive stack usage if we're facing >+ degenerate access patterns. Unfortunately such patterns can occur >+ e.g. during static initialization, where many static objects might >+ be registered in increasing address sequence, or during a case where >+ large tree-like heap data structures are allocated quickly. >+ >+ On x86, this corresponds to roughly 200K of stack usage. >+ XXX: For libmudflapth, this could be a function of __mf_opts.thread_stack. */ >+ sp->max_depth = 2500; >+ sp->rebalance_p = sp->depth = 0; >+ >+ mfsplay_tree_splay_helper (sp, key, &sp->root, NULL, NULL); >+ if (sp->rebalance_p) >+ { >+ mfsplay_tree_rebalance (sp); >+ >+ sp->rebalance_p = sp->depth = 0; >+ mfsplay_tree_splay_helper (sp, key, &sp->root, NULL, NULL); >+ >+ if (sp->rebalance_p) >+ abort (); >+ } >+ >+ >+ /* Cache this splay key. */ >+ sp->last_splayed_key = key; >+ sp->last_splayed_key_p = 1; >+} >+ >+ >+ >+/* Allocate a new splay tree. */ >+static mfsplay_tree >+mfsplay_tree_new () >+{ >+ mfsplay_tree sp = mfsplay_tree_xmalloc (sizeof (struct mfsplay_tree_s)); >+ sp->root = NULL; >+ sp->last_splayed_key_p = 0; >+ sp->num_keys = 0; >+ >+ return sp; >+} >+ >+ >+ >+/* Insert a new node (associating KEY with DATA) into SP. If a >+ previous node with the indicated KEY exists, its data is replaced >+ with the new value. Returns the new node. */ >+static mfsplay_tree_node >+mfsplay_tree_insert (mfsplay_tree sp, mfsplay_tree_key key, mfsplay_tree_value value) >+{ >+ int comparison = 0; >+ >+ mfsplay_tree_splay (sp, key); >+ >+ if (sp->root) >+ comparison = ((sp->root->key > key) ? 1 : >+ ((sp->root->key < key) ? -1 : 0)); >+ >+ if (sp->root && comparison == 0) >+ { >+ /* If the root of the tree already has the indicated KEY, just >+ replace the value with VALUE. */ >+ sp->root->value = value; >+ } >+ else >+ { >+ /* Create a new node, and insert it at the root. */ >+ mfsplay_tree_node node; >+ >+ node = mfsplay_tree_xmalloc (sizeof (struct mfsplay_tree_node_s)); >+ node->key = key; >+ node->value = value; >+ sp->num_keys++; >+ if (!sp->root) >+ node->left = node->right = 0; >+ else if (comparison < 0) >+ { >+ node->left = sp->root; >+ node->right = node->left->right; >+ node->left->right = 0; >+ } >+ else >+ { >+ node->right = sp->root; >+ node->left = node->right->left; >+ node->right->left = 0; >+ } >+ >+ sp->root = node; >+ sp->last_splayed_key_p = 0; >+ } >+ >+ return sp->root; >+} >+ >+/* Remove KEY from SP. It is not an error if it did not exist. */ >+ >+static void >+mfsplay_tree_remove (mfsplay_tree sp, mfsplay_tree_key key) >+{ >+ mfsplay_tree_splay (sp, key); >+ sp->last_splayed_key_p = 0; >+ if (sp->root && (sp->root->key == key)) >+ { >+ mfsplay_tree_node left, right; >+ left = sp->root->left; >+ right = sp->root->right; >+ /* Delete the root node itself. */ >+ mfsplay_tree_free (sp->root); >+ sp->num_keys--; >+ /* One of the children is now the root. Doesn't matter much >+ which, so long as we preserve the properties of the tree. */ >+ if (left) >+ { >+ sp->root = left; >+ /* If there was a right child as well, hang it off the >+ right-most leaf of the left child. */ >+ if (right) >+ { >+ while (left->right) >+ left = left->right; >+ left->right = right; >+ } >+ } >+ else >+ sp->root = right; >+ } >+} >+ >+/* Lookup KEY in SP, returning VALUE if present, and NULL >+ otherwise. */ >+ >+static mfsplay_tree_node >+mfsplay_tree_lookup (mfsplay_tree sp, mfsplay_tree_key key) >+{ >+ mfsplay_tree_splay (sp, key); >+ if (sp->root && (sp->root->key == key)) >+ return sp->root; >+ else >+ return 0; >+} >+ >+ >+/* Return the immediate predecessor KEY, or NULL if there is no >+ predecessor. KEY need not be present in the tree. */ >+ >+static mfsplay_tree_node >+mfsplay_tree_predecessor (mfsplay_tree sp, mfsplay_tree_key key) >+{ >+ int comparison; >+ mfsplay_tree_node node; >+ /* If the tree is empty, there is certainly no predecessor. */ >+ if (!sp->root) >+ return NULL; >+ /* Splay the tree around KEY. That will leave either the KEY >+ itself, its predecessor, or its successor at the root. */ >+ mfsplay_tree_splay (sp, key); >+ comparison = ((sp->root->key > key) ? 1 : >+ ((sp->root->key < key) ? -1 : 0)); >+ >+ /* If the predecessor is at the root, just return it. */ >+ if (comparison < 0) >+ return sp->root; >+ /* Otherwise, find the rightmost element of the left subtree. */ >+ node = sp->root->left; >+ if (node) >+ while (node->right) >+ node = node->right; >+ return node; >+} >+ >+/* Return the immediate successor KEY, or NULL if there is no >+ successor. KEY need not be present in the tree. */ >+ >+static mfsplay_tree_node >+mfsplay_tree_successor (mfsplay_tree sp, mfsplay_tree_key key) >+{ >+ int comparison; >+ mfsplay_tree_node node; >+ /* If the tree is empty, there is certainly no successor. */ >+ if (!sp->root) >+ return NULL; >+ /* Splay the tree around KEY. That will leave either the KEY >+ itself, its predecessor, or its successor at the root. */ >+ mfsplay_tree_splay (sp, key); >+ comparison = ((sp->root->key > key) ? 1 : >+ ((sp->root->key < key) ? -1 : 0)); >+ /* If the successor is at the root, just return it. */ >+ if (comparison > 0) >+ return sp->root; >+ /* Otherwise, find the leftmost element of the right subtree. */ >+ node = sp->root->right; >+ if (node) >+ while (node->left) >+ node = node->left; >+ return node; >+} >+ >+/* Call FN, passing it the DATA, for every node in SP, following an >+ in-order traversal. If FN every returns a non-zero value, the >+ iteration ceases immediately, and the value is returned. >+ Otherwise, this function returns 0. >+ >+ This function simulates recursion using dynamically allocated >+ arrays, since it may be called from mfsplay_tree_rebalance(), which >+ in turn means that the tree is already uncomfortably deep for stack >+ space limits. */ >+static int >+mfsplay_tree_foreach (mfsplay_tree st, mfsplay_tree_foreach_fn fn, void *data) >+{ >+ mfsplay_tree_node *stack1; >+ char *stack2; >+ unsigned sp; >+ int val = 0; >+ enum s { s_left, s_here, s_right, s_up }; >+ >+ if (st->root == NULL) /* => num_keys == 0 */ >+ return 0; >+ >+ stack1 = mfsplay_tree_xmalloc (sizeof (mfsplay_tree_node) * st->num_keys); >+ stack2 = mfsplay_tree_xmalloc (sizeof (char) * st->num_keys); >+ >+ sp = 0; >+ stack1 [sp] = st->root; >+ stack2 [sp] = s_left; >+ >+ while (1) >+ { >+ mfsplay_tree_node n; >+ enum s s; >+ >+ n = stack1 [sp]; >+ s = stack2 [sp]; >+ >+ /* Handle each of the four possible states separately. */ >+ >+ /* 1: We're here to traverse the left subtree (if any). */ >+ if (s == s_left) >+ { >+ stack2 [sp] = s_here; >+ if (n->left != NULL) >+ { >+ sp ++; >+ stack1 [sp] = n->left; >+ stack2 [sp] = s_left; >+ } >+ } >+ >+ /* 2: We're here to traverse this node. */ >+ else if (s == s_here) >+ { >+ stack2 [sp] = s_right; >+ val = (*fn) (n, data); >+ if (val) break; >+ } >+ >+ /* 3: We're here to traverse the right subtree (if any). */ >+ else if (s == s_right) >+ { >+ stack2 [sp] = s_up; >+ if (n->right != NULL) >+ { >+ sp ++; >+ stack1 [sp] = n->right; >+ stack2 [sp] = s_left; >+ } >+ } >+ >+ /* 4: We're here after both subtrees (if any) have been traversed. */ >+ else if (s == s_up) >+ { >+ /* Pop the stack. */ >+ if (sp == 0) break; /* Popping off the root note: we're finished! */ >+ sp --; >+ } >+ >+ else >+ abort (); >+ } >+ >+ mfsplay_tree_free (stack1); >+ mfsplay_tree_free (stack2); >+ return val; >+}
You cannot view the attachment while viewing its details because your browser does not support IFRAMEs.
View the attachment on a separate page
.
View Attachment As Raw
Actions:
View
Attachments on
bug 335290
: 245389