Mercurial > hg > CbC > CbC_gcc

comparison libmudflap/mf-runtime.c @ 0:a06113de4d67

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