Prune recursion frames.

2 files changed, 70 insertions, 30 deletions

diff --git a/src/callgraph-store.c b/src/callgraph-store.c
index 25491f1..3a300d5 100644
--- a/src/callgraph-store.c
+++ b/src/callgraph-store.c
@@ -966,7 +966,6 @@ call_graph_store_update (CallGraphStore *store,
 		    _call_graph_frame_accumulate (child, At, Ap);
 		    child->allocator = NULL;
 		    n++;
-		    g_assert (n < A->n_frames && n < AA->n_frames);
 		}
 
 		if (n < AA->n_frames)
diff --git a/src/lwp.c b/src/lwp.c
index e39588e..5a28595 100644
--- a/src/lwp.c
+++ b/src/lwp.c
@@ -95,8 +95,12 @@ struct _lwp_allocator {
     gpointer ips[0];
 };
 
+static guint
+_lwp_add_allocator (gpointer *ips, guint n_ips);
+
 static pthread_mutex_t event_mutex = PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP;
 static gboolean _lwp_disable_stacktraces;
+static gboolean _lwp_enable_recursion_pruning;
 static guint _lwp_num_callers = (guint) -1;
 
 static GSList *pending_allocators;
@@ -620,35 +624,6 @@ _lwp_add_ip (gconstpointer eip)
     _lwp_queue_lookup_symbol (eip);
 }
 
-
-static guint
-_lwp_allocator_alloc (gpointer *ips, guint n_ips, gulong hash)
-{
-    static guint allocator_key;
-
-    LWP_Allocator *A;
-    guint n, index;
-
-    A = _lwp_perm_alloc (sizeof (LWP_Allocator) + sizeof(gpointer) * n_ips);
-
-    A->key = ++allocator_key;
-    A->hash = hash;
-    A->n_ips = n_ips;
-    memcpy (A->ips, ips, sizeof (gpointer) * n_ips);
-
-    index = hash % G_N_ELEMENTS (allocator_ht);
-    A->ht_next = allocator_ht[index];
-    allocator_ht[index] = A;
-
-    pending_allocators = _lwp_gslist_prepend (pending_allocators, A);
-
-    /* add to symbol translation ht */
-    for (n = 0; n < n_ips; n++)
-	_lwp_add_ip (ips[n]);
-
-    return A->key;
-}
-
 static gulong
 _lwp_allocator_hash (gpointer *ips, guint n_ips)
 {
@@ -684,6 +659,66 @@ _lwp_allocator_equal (const LWP_Allocator *A,
 }
 
 static guint
+_lwp_prune_recursion (gpointer *ips, guint n_ips)
+{
+    guint n, len;
+
+    for (len = 1; len < n_ips/2; len++) {
+	for (n = 0; n < n_ips - 2*len; n++) {
+	    guint m = n + len;
+	    while (memcmp (ips + n, ips + m, len * sizeof (gpointer)) == 0) {
+		m += len;
+		if (m + len > n_ips)
+		    break;
+	    }
+	    if (m != n + len) {
+		memmove (ips + n + len, ips + m, sizeof (gpointer) * (n_ips - m));
+		n_ips -= m - n - len;
+	    }
+	}
+    }
+    return n_ips;
+}
+
+static guint
+_lwp_allocator_alloc (gpointer *ips, guint n_ips, gulong hash)
+{
+    static guint allocator_key;
+
+    LWP_Allocator *A;
+    guint n, index;
+
+    A = _lwp_perm_alloc (sizeof (LWP_Allocator) + sizeof(gpointer) * n_ips);
+
+    A->key = 0;
+    A->hash = hash;
+    A->n_ips = n_ips;
+    memcpy (A->ips, ips, sizeof (gpointer) * n_ips);
+
+    index = hash % G_N_ELEMENTS (allocator_ht);
+    A->ht_next = allocator_ht[index];
+    allocator_ht[index] = A;
+
+    if (_lwp_enable_recursion_pruning) {
+	guint pruned_n_ips = _lwp_prune_recursion (ips, n_ips);
+	if (pruned_n_ips != n_ips)
+	    A->key = _lwp_add_allocator (ips, pruned_n_ips);
+    }
+
+    if (A->key == 0) {
+	pending_allocators = _lwp_gslist_prepend (pending_allocators, A);
+
+	/* add to symbol translation ht */
+	for (n = 0; n < n_ips; n++)
+	    _lwp_add_ip (ips[n]);
+
+	A->key = ++allocator_key;
+    }
+
+    return A->key;
+}
+
+static guint
 _lwp_add_allocator (gpointer *ips, guint n_ips)
 {
     LWP_Allocator *A;
@@ -1026,6 +1061,12 @@ __lwp_init (void)
 	    _lwp_disable_stacktraces = TRUE;
     }
 
+    if (! _lwp_disable_stacktraces) {
+	env = getenv ("LWP_PRUNE_RECURSION");
+	_lwp_enable_recursion_pruning = env != NULL;
+    }
+	_lwp_enable_recursion_pruning = TRUE;
+
     DLSYM_DEFINE (malloc);
     DLSYM_DEFINE (calloc);
     DLSYM_DEFINE (realloc);