OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libmudflap/] [mf-runtime.c] - Blame information for rev 791

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.