This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tree-ssa libmudflap] performance/functionality improvements
- From: "Frank Ch. Eigler" <fche at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 20 Sep 2002 13:50:51 -0400
- Subject: [tree-ssa libmudflap] performance/functionality improvements
Hi -
I'm about to commit the following patch against libmudflap.
It tweaks some informal heuristics to the object binary-tree logic
to guess at a working set of objects, so they are gradually moved closer
to the root of the tree. I'm sure this data structure is evolving toward
some theoretically well-known variant... One future possibility is to
dynamically adapt the lookup-cache parameters based upon the current
working set's characteristics.
It also adds a NOACCESS type region to the repertoire. The idea is that
instead of adding only positive (access-allowed) regions to the database,
one can add negative ones too. This way, regions that must not be accessed
by an instrumented program, despite heuristics, can be identified. Maybe
it can be used for marking future inter-object safety padding.
It's also starting to be a little more sophisticated about how much
work it does to track very transient objects.
Index: ChangeLog
+2002-09-20 Frank Ch. Eigler <fche@redhat.com>
+
+ * test/fail18-frag.c: New test file for NOACCESS regions.
+ * Makefile.am (TESTS): Add new test.
+ * Makefile.in: Regenerated.
+
+ * mf-heuristics.c (__mf_heuristics_check): Correct deja_vu logic.
+ * mf-impl.h (tree_aging): Add new mudflap_option, default 1000000.
+ (optimize_object_tree): Remove unused mudflap_option.
+ * mf-runtime.h (__MF_TYPE_NOACCESS): New region type. Add printing
+ support throughout. Use .._MAX_CEM for cemetary upper bound.
+ * mf-runtime.c (__mf_init): Register __mf_* globals as NOACCESS
+ regions.
+ (__mf_object): Add new liveness field for use by tree aging.
+ (__mf_check): Trigger tree aging when needed.
+ (__mf_age_tree): New function to decay liveness field.
+ (__mf_find_objects_rec): Use liveness field to rotate tree.
+ (__mf_insert_new_object): Only provide backtrace for HEAP objects.
+ (__mf_unregister): Ditto.
+ (__mf_register): Tweak duplicate-static message.
+ (__mf_violation: Tweak nearby-object counter printing.
+
Index: Makefile.am
===================================================================
RCS file: /cvs/gcc/gcc/libmudflap/Attic/Makefile.am,v
retrieving revision 1.1.2.11
diff -u -p -w -r1.1.2.11 Makefile.am
--- Makefile.am 16 Sep 2002 14:49:57 -0000 1.1.2.11
+++ Makefile.am 20 Sep 2002 17:41:54 -0000
@@ -12,7 +12,7 @@ TESTS_ENVIRONMENT = LD_LIBRARY_PATH='.li
TESTS = test/fail1.x test/fail2.x test/fail3.x test/fail4.x test/fail5.x \
test/fail6.x test/fail7.x test/fail8.x test/fail9.x test/fail10.x \
test/fail11.x test/fail12.x test/fail13.x test/fail14.x test/fail15.x \
- test/fail16.x test/fail17.x \
+ test/fail16.x test/fail17.x test/fail18.x \
test/pass1.x test/pass2.x test/pass3.x test/pass4.x test/pass5.x \
test/pass6.x test/pass7.x test/pass8.x test/pass9.x test/pass10.x \
test/pass11.x test/pass12.x test/pass13.x test/pass14.x test/pass15.x \
Index: mf-heuristics.c
===================================================================
RCS file: /cvs/gcc/gcc/libmudflap/Attic/mf-heuristics.c,v
retrieving revision 1.1.2.9
diff -u -p -w -r1.1.2.9 mf-heuristics.c
--- mf-heuristics.c 16 Sep 2002 14:49:57 -0000 1.1.2.9
+++ mf-heuristics.c 20 Sep 2002 17:41:54 -0000
@@ -85,15 +85,16 @@ __mf_heuristic_check (uintptr_t ptr, uin
for (i=0; i<max_entries; i++)
{
if (entry_used[i] &&
- (entry[i].low >= ptr) &&
- (entry[i].high <= ptr_high))
+ (entry[i].low <= ptr) &&
+ (entry[i].high >= ptr_high))
deja_vu = 1;
}
if (! deja_vu)
{
/* Time to run the heuristic. Rescan /proc/self/maps; update the
- entry[] array; remove expired entries, add new ones. */
+ entry[] array; XXX: remove expired entries, add new ones.
+ XXX: Consider entries that have grown (e.g., stack). */
char buf[512];
char flags[4];
void *low, *high;
@@ -115,6 +116,7 @@ __mf_heuristic_check (uintptr_t ptr, uin
{
entry[i].low = (uintptr_t) low;
entry[i].high = (uintptr_t) high;
+ entry_used[i] = 1;
break;
}
}
Index: mf-impl.h
===================================================================
RCS file: /cvs/gcc/gcc/libmudflap/Attic/mf-impl.h,v
retrieving revision 1.1.2.5
diff -u -p -w -r1.1.2.5 mf-impl.h
--- mf-impl.h 16 Sep 2002 14:49:57 -0000 1.1.2.5
+++ mf-impl.h 20 Sep 2002 17:41:54 -0000
@@ -55,9 +55,12 @@ struct __mf_options
/* Collect and emit statistics. */
unsigned collect_stats;
- /* Execute internal checking code */
+ /* Execute internal checking code. */
unsigned internal_checking;
+ /* Age object liveness periodically. */
+ unsigned tree_aging;
+
/* Print list of leaked heap objects on shutdown. */
unsigned print_leaks;
@@ -66,9 +69,6 @@ struct __mf_options
/* Emit internal tracing message. */
unsigned verbose_trace;
-
- /* Perform occasional tree-rotations to optimize lookups. */
- unsigned optimize_object_tree;
/* Support multiple threads. */
unsigned multi_threaded;
Index: mf-runtime.c
===================================================================
RCS file: /cvs/gcc/gcc/libmudflap/Attic/mf-runtime.c,v
retrieving revision 1.1.2.14
diff -u -p -w -r1.1.2.14 mf-runtime.c
--- mf-runtime.c 16 Sep 2002 14:49:57 -0000 1.1.2.14
+++ mf-runtime.c 20 Sep 2002 17:41:54 -0000
@@ -84,12 +84,12 @@ __mf_set_default_options ()
__mf_opts.verbose_trace = 0;
__mf_opts.collect_stats = 0;
__mf_opts.internal_checking = 0;
+ __mf_opts.tree_aging = 1000000;
__mf_opts.print_leaks = 0;
__mf_opts.verbose_violations = 0;
- __mf_opts.optimize_object_tree = 0;
__mf_opts.multi_threaded = 0;
- __mf_opts.free_queue_length = 0;
- __mf_opts.persistent_count = 0;
+ __mf_opts.free_queue_length = 4;
+ __mf_opts.persistent_count = 100;
__mf_opts.crumple_zone = 32;
__mf_opts.backtrace = 4;
__mf_opts.mudflap_mode = mode_check;
@@ -138,29 +138,27 @@ options [] =
{"viol-gdb",
"violations fork a gdb process attached to current program",
set_option, (int)viol_gdb, (int *)&__mf_opts.violation_mode},
-
{"trace-calls",
"trace calls to mudflap runtime library",
set_option, 1, &__mf_opts.trace_mf_calls},
{"verbose-trace",
"trace internal events within mudflap runtime library",
set_option, 1, &__mf_opts.verbose_trace},
-
{"collect-stats",
"collect statistics on mudflap's operation",
set_option, 1, &__mf_opts.collect_stats},
{"internal-checking",
"perform more expensive internal checking",
set_option, 1, &__mf_opts.internal_checking},
+ {"age-tree",
+ "age the object tree after N accesses for working set",
+ read_integer_option, 1000000, &__mf_opts.tree_aging},
{"print-leaks",
"print any memory leaks at program shutdown",
set_option, 1, &__mf_opts.print_leaks},
{"verbose-violations",
"print verbose messages when memory violations occur",
set_option, 1, &__mf_opts.verbose_violations},
- {"optimize-object-tree",
- "periodically optimize memory object tracking tree",
- set_option, 1, &__mf_opts.optimize_object_tree},
/* XXX: this should be sensitive to gcc --enable-threading= setting */
{"multi-threaded",
"support multiple threads",
@@ -425,6 +423,13 @@ void __mf_init ()
}
__mf_state = active;
+#define REG_RESERVED(obj) \
+ __mf_register ((uintptr_t) & obj, (uintptr_t) sizeof(obj), __MF_TYPE_NOACCESS, # obj)
+
+ REG_RESERVED (__mf_lookup_cache);
+ REG_RESERVED (__mf_lc_mask);
+ REG_RESERVED (__mf_lc_shift);
+ /* XXX: others of our statics? */
}
@@ -452,10 +457,11 @@ static unsigned long __mf_count_violatio
typedef struct __mf_object
{
- uintptr_t low, high;
+ uintptr_t low, high; /* __mf_register parameters */
int type;
const char *name;
- unsigned check_count; /* Number of times __mf_check was called. */
+ unsigned check_count; /* Number of times __mf_check was called on this object. */
+ unsigned liveness; /* A measure of recent checking activity. */
uintptr_t alloc_pc;
struct timeval alloc_time;
@@ -479,9 +485,9 @@ typedef struct __mf_object_tree
/* Live objects: binary tree on __mf_object_t.low */
__mf_object_tree_t *__mf_object_root;
-/* Dead objects: circular arrays; exclude __MF_TYPE_GUESS. */
-unsigned __mf_object_dead_head[__MF_TYPE_GUESS+1]; /* next empty spot */
-__mf_object_tree_t *__mf_object_cemetary[__MF_TYPE_GUESS][__MF_PERSIST_MAX];
+/* Dead objects: circular arrays; _MIN_CEM .. _MAX_CEM only */
+unsigned __mf_object_dead_head[__MF_TYPE_MAX_CEM]; /* next empty spot */
+__mf_object_tree_t *__mf_object_cemetary[__MF_TYPE_MAX_CEM][__MF_PERSIST_MAX];
static __mf_object_tree_t *__mf_find_object (uintptr_t low, uintptr_t high);
static unsigned __mf_find_objects (uintptr_t ptr_low, uintptr_t ptr_high,
@@ -489,6 +495,7 @@ static unsigned __mf_find_objects (uintp
static unsigned __mf_find_dead_objects (uintptr_t ptr_low, uintptr_t ptr_high,
__mf_object_tree_t **objs, unsigned max_objs);
static void __mf_link_object (__mf_object_tree_t *obj);
+static void __mf_age_tree (__mf_object_tree_t *obj);
static void __mf_unlink_object (__mf_object_tree_t *obj);
static void __mf_describe_object (__mf_object_t *obj);
@@ -523,14 +530,38 @@ void __mf_check (uintptr_t ptr, uintptr_
/* Looping only occurs if heuristics were triggered. */
while (1)
{
+ /* XXX: This search embodied by __mf_find_object prevents
+ an access that spans contiguous objects. Spanning two
+ GUESS regions should be accepted, but can that happen?
+ Maybe a heuristic that glues them together is
+ needed. */
__mf_object_tree_t *node = __mf_find_object (ptr, ptr_high);
__mf_object_t *obj = (node != NULL ? (& node->data) : NULL);
if (LIKELY (obj && ptr >= obj->low && ptr_high <= obj->high))
{
+ /* Handle tree liveness aging. */
+ static unsigned cache_miss_count;
+ cache_miss_count ++;
+ if (UNLIKELY (__mf_opts.tree_aging > 0 &&
+ cache_miss_count > __mf_opts.tree_aging))
+ {
+ cache_miss_count = 0;
+ __mf_age_tree (__mf_object_root);
+ }
+ obj->liveness ++;
+
+ obj->check_count ++; /* XXX: what about overflow? */
+
+ if (UNLIKELY (obj->type == __MF_TYPE_NOACCESS))
+ {
+ violation_p = 1;
+ }
+ else
+ {
entry->low = obj->low;
entry->high = obj->high;
- obj->check_count ++; /* XXX: what about overflow? */
+ }
break;
}
else if (heuristics++ < 2) /* XXX parametrize this number? */
@@ -601,7 +632,7 @@ __mf_insert_new_object (uintptr_t low, u
new_obj->data.alloc_pc = pc;
gettimeofday (& new_obj->data.alloc_time, NULL);
- if (__mf_opts.backtrace > 0)
+ if (__mf_opts.backtrace > 0 && type == __MF_TYPE_HEAP)
new_obj->data.alloc_backtrace_size =
__mf_backtrace (& new_obj->data.alloc_backtrace,
(void *) pc, 2);
@@ -698,7 +729,9 @@ __mf_register (uintptr_t ptr, uintptr_t
ovr_obj->data.high == high)
{
/* do nothing */
- VERBOSE_TRACE ("mf: duplicate static reg %08lx-%08lx\n", low, high);
+ VERBOSE_TRACE ("mf: duplicate static reg %08lx-%08lx `%s'\n",
+ low, high,
+ (ovr_obj->data.name ? ovr_obj->data.name : ""));
END_RECURSION_PROTECT;
return;
}
@@ -881,7 +914,7 @@ __mf_unregister (uintptr_t ptr, uintptr_
old_obj->data.dealloc_pc = (uintptr_t) __builtin_return_address (0);
gettimeofday (& old_obj->data.dealloc_time, NULL);
- if (__mf_opts.backtrace > 0)
+ if (__mf_opts.backtrace > 0 && old_obj->data.type == __MF_TYPE_HEAP)
old_obj->data.dealloc_backtrace_size =
__mf_backtrace (& old_obj->data.dealloc_backtrace,
NULL, 2);
@@ -889,8 +922,8 @@ __mf_unregister (uintptr_t ptr, uintptr_
/* Put this object into the cemetary. This may require this plot to
be recycled, and the previous resident to be designated del_obj. */
- assert (old_obj->data.type >= __MF_TYPE_UNKNOWN &&
- old_obj->data.type < __MF_TYPE_GUESS);
+ assert (old_obj->data.type >= 0 &&
+ old_obj->data.type <= __MF_TYPE_MAX_CEM);
{
unsigned row = old_obj->data.type;
unsigned plot = __mf_object_dead_head [row];
@@ -975,7 +1008,7 @@ __mf_validate_object_cemetary ()
unsigned cls;
unsigned i;
- for (cls = __MF_TYPE_UNKNOWN; cls < __MF_TYPE_GUESS; cls++)
+ for (cls = 0; cls <= __MF_TYPE_MAX_CEM; cls++)
{
assert (__mf_object_dead_head [cls] >= 0 &&
__mf_object_dead_head [cls] < __mf_opts.persistent_count);
@@ -1002,6 +1035,22 @@ __mf_validate_objects ()
__mf_validate_object_cemetary ();
}
+
+static void
+__mf_age_tree (__mf_object_tree_t *obj)
+{
+ assert (obj != NULL);
+ obj->data.liveness = obj->data.liveness >> 1;
+
+ if (obj->left)
+ __mf_age_tree (obj->left);
+ if (obj->right)
+ __mf_age_tree (obj->right);
+}
+
+
+
+
/* __mf_find_object[s] */
/* Find overlapping live objecs between [low,high]. Return up to
@@ -1057,12 +1106,10 @@ __mf_find_objects_rec (uintptr_t low, ui
/* Rotate a child node up if its access count is higher. */
- /* XXX: Should there be a minimum check_count delta that triggers this? */
- /* XXX: Should age (scale down) system-wide check_counts periodically. */
- if (UNLIKELY ((node->left && node->left->data.check_count > node->data.check_count) &&
+ if (UNLIKELY ((node->left && node->left->data.liveness > node->data.liveness) &&
((!node->right || (node->right &&
- node->left->data.check_count >
- node->right->data.check_count)))))
+ node->left->data.liveness >
+ node->right->data.liveness)))))
{
__mf_object_tree_t *l = node->left;
__mf_object_tree_t *l_r = l->right;
@@ -1072,10 +1119,10 @@ __mf_find_objects_rec (uintptr_t low, ui
node->left = l_r;
__mf_treerot_left ++;
}
- else if (UNLIKELY ((node->right && node->right->data.check_count > node->data.check_count) &&
+ else if (UNLIKELY ((node->right && node->right->data.liveness > node->data.liveness) &&
((!node->left || (node->left &&
- node->right->data.check_count >
- node->left->data.check_count)))))
+ node->right->data.liveness >
+ node->left->data.liveness)))))
{
__mf_object_tree_t *r = node->right;
__mf_object_tree_t *r_l = r->left;
@@ -1086,7 +1133,6 @@ __mf_find_objects_rec (uintptr_t low, ui
__mf_treerot_right ++;
}
-
return count;
}
@@ -1220,7 +1266,7 @@ __mf_find_dead_objects (uintptr_t low, u
{
count = 0;
- for (row = __MF_TYPE_UNKNOWN; row < __MF_TYPE_GUESS; row ++)
+ for (row = 0; row <= __MF_TYPE_MAX_CEM; row ++)
{
unsigned plot;
unsigned i;
@@ -1267,7 +1313,7 @@ __mf_describe_object (__mf_object_t *obj
fprintf (stderr,
"mudflap object %08lx: name=`%s'\n"
- "bounds=[%08lx,%08lx] size=%lu area=%s access-count=%u\n"
+ "bounds=[%08lx,%08lx] size=%lu area=%s checked=%u liveness=%u\n"
"alloc time=%lu.%06lu pc=%08lx\n",
obj, (obj->name ? obj->name : ""),
obj->low, obj->high, (obj->high - obj->low + 1),
@@ -1275,8 +1321,8 @@ __mf_describe_object (__mf_object_t *obj
obj->type == __MF_TYPE_STACK ? "stack" :
obj->type == __MF_TYPE_STATIC ? "static" :
obj->type == __MF_TYPE_GUESS ? "guess" :
- "unknown"),
- obj->check_count,
+ "no-access"),
+ obj->check_count, obj->liveness,
obj->alloc_time.tv_sec, obj->alloc_time.tv_usec, obj->alloc_pc);
if (__mf_opts.backtrace > 0)
@@ -1380,11 +1426,11 @@ __mf_report ()
{
unsigned dead_count = 0;
unsigned row, plot;
- for (row = __MF_TYPE_UNKNOWN; row < __MF_TYPE_GUESS; row ++)
+ for (row = 0; row <= __MF_TYPE_MAX_CEM; row ++)
for (plot = 0 ; plot < __mf_opts.persistent_count; plot ++)
if (__mf_object_cemetary [row][plot] != 0)
dead_count ++;
- fprintf (stderr, " persistent dead objects: %u\n", dead_count);
+ fprintf (stderr, " zombie objects: %u\n", dead_count);
}
}
if (__mf_opts.print_leaks && (__mf_opts.mudflap_mode == mode_check))
@@ -1548,7 +1594,7 @@ __mf_violation (uintptr_t ptr, uintptr_t
unsigned into2 = (high >= obj->low && low <= obj->high) ? high - obj->low : 0;
fprintf (stderr, "Nearby object %u: checked region begins %uB %s and ends %uB %s\n",
- i + 1,
+ num_helpful + i + 1,
(before1 ? before1 : after1 ? after1 : into1),
(before1 ? "before" : after1 ? "after" : "into"),
(before2 ? before2 : after2 ? after2 : into2),
Index: mf-runtime.h
===================================================================
RCS file: /cvs/gcc/gcc/libmudflap/Attic/mf-runtime.h,v
retrieving revision 1.1.2.8
diff -u -p -w -r1.1.2.8 mf-runtime.h
--- mf-runtime.h 27 Aug 2002 22:33:29 -0000 1.1.2.8
+++ mf-runtime.h 20 Sep 2002 17:41:54 -0000
@@ -39,10 +39,12 @@ extern void __mf_check (uintptr_t ptr, u
/* Codes to describe a region of memory being registered. */
-#define __MF_TYPE_UNKNOWN 0
+#define __MF_TYPE_NOACCESS 0
#define __MF_TYPE_HEAP 1
#define __MF_TYPE_STACK 2
#define __MF_TYPE_STATIC 3
+#define __MF_TYPE_MAX_CEM 3
+
#define __MF_TYPE_GUESS 4
#define __MF_TYPE_MAX __MF_TYPE_GUESS
Index: test/fail18-frag.c
===================================================================
RCS file: test/fail18-frag.c
diff -N test/fail18-frag.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ test/fail18-frag.c 20 Sep 2002 17:41:54 -0000
@@ -0,0 +1,5 @@
+/* One cannot redeclare __mf_lc_mask in proper C from instrumented
+ code, because of the way the instrumentation code emits its decls. */
+extern unsigned foo __asm__ ("__mf_lc_mask");
+unsigned *bar = &foo;
+*bar = 4;