URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libmudflap/] [mf-runtime.c] - Rev 779
Go to most recent revision | Compare with Previous | Blame | View Log
/* Mudflap: narrow-pointer bounds-checking by tree rewriting. Copyright (C) 2002, 2003, 2004, 2005, 2006, 2008, 2009, 2010, 2011, 2012 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 /* 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 { 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-2012 Free Software Foundation, Inc.\n" "\n" "Unless setuid, a program's mudflap options be set 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}, #ifdef HAVE_MMAP64 {NULL, "mmap64", NULL}, #endif {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; #if defined(__FreeBSD__) && defined(LIBMUDFLAPTH) pthread_self(); LOCKTH (); UNLOCKTH (); #endif /* Prime mutex which calls calloc upon first lock to avoid deadlock. */ /* 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 (); if (getuid () == geteuid () && getgid () == getegid ()) /* PR41433, not setuid */ 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"); #if !(defined(__sun__) && defined(__svr4__)) /* Conflicts with the automatic registration of __iob[]. */ __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"); #endif /* Make some effort to register ctype.h static arrays. */ #if defined(__sun__) && defined(__svr4__) /* __ctype[] is declared without size, but MB_CUR_MAX is the last member. There seems to be no proper way to determine the size. */ __mf_register (__ctype, &MB_CUR_MAX - &__ctype[0] + 1, __MF_TYPE_STATIC, "__ctype"); /* __ctype_mask points at _C_masks[1]. The size can only determined using nm on libc.so.1. */ __mf_register (__ctype_mask - 1, 1028, __MF_TYPE_STATIC, "_C_masks"); #endif /* 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; }
Go to most recent revision | Compare with Previous | Blame | View Log