diff options
| author | Jeff Law <law@redhat.com> | 2013-10-26 04:14:34 -0600 |
|---|---|---|
| committer | Jeff Law <law@gcc.gnu.org> | 2013-10-26 04:14:34 -0600 |
| commit | 98906124e3aa4cb17695d900fe19498e5bde63e4 (patch) | |
| tree | db4fb2e3b3425e4080112ab6c0fa8e4922a5a2d7 /libmudflap/mf-runtime.c | |
| parent | 19b632c6dd5e1e901ae1bac3fc92164a724ccab5 (diff) | |
| download | gcc-98906124e3aa4cb17695d900fe19498e5bde63e4.zip gcc-98906124e3aa4cb17695d900fe19498e5bde63e4.tar.gz gcc-98906124e3aa4cb17695d900fe19498e5bde63e4.tar.bz2 | |
Makefile.def (target_modules): Remove libmudflap
* Makefile.def (target_modules): Remove libmudflap
(languages): Remove check-target-libmudflap).
* Makefile.in: Rebuilt.
* Makefile.tpl (check-target-libmudflap-c++): Remove.
* configure.ac (target_libraries): Remove target-libmudflap.
Remove checks which disabled libmudflap on some systems.
* configure: Rebuilt.
* libmudflap: Directory removed.
* Makefile.in (C_COMMON_OBJS): Remove tree-mudflap.
(OBJS): Remove tree-nomudflap.o
(GTFILES): Remove tree-mudflap.c
* builtins.c (expand_builtin_alloc): Remove mudflap support.
* gcc.c (MFWRAP_SPEC, MFLIB_SPEC): Likewise.
(mfwrap_spec, mflib_spec): Likewise.
(cpp_unique_options, cc1_options, static_specs): Likewise.
* gimplify (gimplify_vla_decl, build_va_arg_indirect_ref): Likewise.
* passes.def: Likewise.
* toplev.c (compile_file, process_options): Likewise.
* tree-inline.c (copy_tree_r): Likewise.
* tree-pass.,h (make_pass_mudflap_1, make_pass_mudflap_2): Likewise.
* varasm.c (make_decl_rtl, make_decl_rtl_for_debug): Likewise.
(build_constant_desc, output_constant_def_contents): Likewise.
(categorize_decl_for_section): Likewise.
* tree-mudflap.c: Removed.
* tree-mudflap.h: Removed.
* tree-nomudflap.c: Removed.
* bfin/uclinux.h (MFWRAP_SPEC): Remove.
* moxie/uclinux.h (MFWRAP_SPEC): Likewise.
* rs6000/aix.h (MFWRAP_SPEC, MFLIB_SPEC): Likewise.
* config/sol2.h (MFLIB_SPEC): Likewise.
* doc/install.texi: Remove mudflap references.
* doc/passes.texi: Similarly.
* doc/sourcebuild.texi: Similarly.
* doc/invoke.texi: Remove mudlfap related options.
* c-family/c-common.c (c_define_builtins): Remove mudflap support.
* c-family/c.opt: Ignore and warn for mudflap options.
* g++.dg/torture/pr49309.C: Removed.
* gcc.dg/dfp/pr35739.c: Removed.
From-SVN: r204090
Diffstat (limited to 'libmudflap/mf-runtime.c')
| -rw-r--r-- | libmudflap/mf-runtime.c | 2886 |
1 files changed, 0 insertions, 2886 deletions
diff --git a/libmudflap/mf-runtime.c b/libmudflap/mf-runtime.c deleted file mode 100644 index 96a396e..0000000 --- a/libmudflap/mf-runtime.c +++ /dev/null @@ -1,2886 +0,0 @@ -/* Mudflap: narrow-pointer bounds-checking by tree rewriting. - Copyright (C) 2002-2013 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-2013 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; -} |