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