[PATCH 17/49] perf tools: Convert dead thread list into rbtree

[Jiri Olsa <jolsa@kernel.org>]

Currently perf maintains dead threads in a linked list but this can be
a problem if someone needs to search from it especially in a large
session which might have many dead threads.  Convert it to a rbtree
like normal threads and it'll be used later with multi-thread changes.

The list node is now used for chaining dead threads of same tid since
it's easier to handle such threads in time order.

Cc: Frederic Weisbecker <fweisbec@gmail.com>
Link: http://lkml.kernel.org/n/tip-86w2k0bjyi98p0kvyb6frcu5@git.kernel.org
Original-patch-by: Namhyung Kim <namhyung@kernel.org>
Signed-off-by: Jiri Olsa <jolsa@kernel.org>
---
 tools/perf/util/intel-pt.c |  2 +-
 tools/perf/util/machine.c  | 82 +++++++++++++++++++++++++++++++++++++++++-----
 tools/perf/util/machine.h  | 10 +++---
 tools/perf/util/thread.c   | 12 ++++++-
 tools/perf/util/thread.h   |  6 ++--
 5 files changed, 93 insertions(+), 19 deletions(-)

diff --git a/tools/perf/util/intel-pt.c b/tools/perf/util/intel-pt.c
index 23f9ba676df0..e727e6f32202 100644
--- a/tools/perf/util/intel-pt.c
+++ b/tools/perf/util/intel-pt.c
@@ -2535,7 +2535,7 @@ int intel_pt_process_auxtrace_info(union perf_event *event,
 	 * current thread lifetime assuption is kept and we don't segfault
 	 * at list_del_init().
 	 */
-	INIT_LIST_HEAD(&pt->unknown_thread->node);
+	INIT_LIST_HEAD(&pt->unknown_thread->tid_list);
 
 	err = thread__set_comm(pt->unknown_thread, "unknown", 0);
 	if (err)
diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c
index b05a67464c03..a4d0dd57ad18 100644
--- a/tools/perf/util/machine.c
+++ b/tools/perf/util/machine.c
@@ -40,10 +40,11 @@ static void machine__threads_init(struct machine *machine)
 
 	for (i = 0; i < THREADS__TABLE_SIZE; i++) {
 		struct threads *threads = &machine->threads[i];
+
 		threads->entries = RB_ROOT;
+		threads->dead    = RB_ROOT;
 		init_rwsem(&threads->lock);
 		threads->nr = 0;
-		INIT_LIST_HEAD(&threads->dead);
 		threads->last_match = NULL;
 	}
 }
@@ -149,6 +150,28 @@ static void dsos__exit(struct dsos *dsos)
 	exit_rwsem(&dsos->lock);
 }
 
+static void threads__delete_dead(struct threads *threads)
+{
+	struct rb_node *nd = rb_first(&threads->dead);
+
+	while (nd) {
+		struct thread *t = rb_entry(nd, struct thread, rb_node);
+		struct thread *pos;
+
+		nd = rb_next(nd);
+		rb_erase_init(&t->rb_node, &threads->dead);
+
+		while (!list_empty(&t->tid_list)) {
+			pos = list_first_entry(&t->tid_list,
+					       struct thread, tid_list);
+			list_del_init(&pos->tid_list);
+			thread__delete(pos);
+		}
+
+		thread__delete(t);
+	}
+}
+
 void machine__delete_threads(struct machine *machine)
 {
 	struct rb_node *nd;
@@ -156,6 +179,7 @@ void machine__delete_threads(struct machine *machine)
 
 	for (i = 0; i < THREADS__TABLE_SIZE; i++) {
 		struct threads *threads = &machine->threads[i];
+
 		down_write(&threads->lock);
 		nd = rb_first(&threads->entries);
 		while (nd) {
@@ -164,6 +188,9 @@ void machine__delete_threads(struct machine *machine)
 			nd = rb_next(nd);
 			__machine__remove_thread(machine, t, false);
 		}
+
+		threads__delete_dead(threads);
+
 		up_write(&threads->lock);
 	}
 }
@@ -1512,6 +1539,8 @@ int machine__process_mmap_event(struct machine *machine, union perf_event *event
 static void __machine__remove_thread(struct machine *machine, struct thread *th, bool lock)
 {
 	struct threads *threads = machine__threads(machine, th->tid);
+	struct rb_node **p, *parent;
+	struct thread *pos;
 
 	if (threads->last_match == th)
 		threads->last_match = NULL;
@@ -1523,14 +1552,44 @@ static void __machine__remove_thread(struct machine *machine, struct thread *th,
 	RB_CLEAR_NODE(&th->rb_node);
 	--threads->nr;
 	/*
-	 * Move it first to the dead_threads list, then drop the reference,
-	 * if this is the last reference, then the thread__delete destructor
-	 * will be called and we will remove it from the dead_threads list.
+	 * No need to have an additional reference for non-index file
+	 * as they can be released when reference holders died and
+	 * there will be no more new references.
+	 */
+	if (!perf_has_index) {
+		thread__put(th);
+		goto out;
+	}
+
+	p = &threads->dead.rb_node;
+	parent = NULL;
+
+	/*
+	 * For indexed file, We may have references to this (dead)
+	 * thread, as samples are processed after fork/exit events.
+	 * Just move them to a separate rbtree and keep a reference.
 	 */
-	list_add_tail(&th->node, &threads->dead);
+	while (*p != NULL) {
+		parent = *p;
+		pos = rb_entry(parent, struct thread, rb_node);
+
+		if (pos->tid == th->tid) {
+			list_add_tail(&th->tid_list, &pos->tid_list);
+			goto out;
+		}
+
+		if (th->tid < pos->tid)
+			p = &(*p)->rb_left;
+		else
+			p = &(*p)->rb_right;
+	}
+
+	rb_link_node(&th->rb_node, parent, p);
+	rb_insert_color(&th->rb_node, &threads->dead);
+
+out:
 	if (lock)
 		up_write(&threads->lock);
-	thread__put(th);
 }
 
 void machine__remove_thread(struct machine *machine, struct thread *th)
@@ -2237,7 +2296,7 @@ int machine__for_each_thread(struct machine *machine,
 {
 	struct threads *threads;
 	struct rb_node *nd;
-	struct thread *thread;
+	struct thread *thread, *pos;
 	int rc = 0;
 	int i;
 
@@ -2250,10 +2309,17 @@ int machine__for_each_thread(struct machine *machine,
 				return rc;
 		}
 
-		list_for_each_entry(thread, &threads->dead, node) {
+		for (nd = rb_first(&threads->dead); nd; nd = rb_next(nd)) {
+			thread = rb_entry(nd, struct thread, rb_node);
 			rc = fn(thread, priv);
 			if (rc != 0)
 				return rc;
+
+			list_for_each_entry(pos, &thread->tid_list, tid_list) {
+				rc = fn(pos, priv);
+				if (rc != 0)
+					return rc;
+			}
 		}
 	}
 	return rc;
diff --git a/tools/perf/util/machine.h b/tools/perf/util/machine.h
index 5ce860b64c74..1d1a2f199f90 100644
--- a/tools/perf/util/machine.h
+++ b/tools/perf/util/machine.h
@@ -29,11 +29,11 @@ struct vdso_info;
 #define THREADS__TABLE_SIZE	(1 << THREADS__TABLE_BITS)
 
 struct threads {
-	struct rb_root	  entries;
-	struct rw_semaphore lock;
-	unsigned int	  nr;
-	struct list_head  dead;
-	struct thread	  *last_match;
+	struct rb_root		 entries;
+	struct rb_root		 dead;
+	struct rw_semaphore	 lock;
+	unsigned int		 nr;
+	struct thread		*last_match;
 };
 
 struct machine {
diff --git a/tools/perf/util/thread.c b/tools/perf/util/thread.c
index bf79a3ef06bc..b5ac28731c01 100644
--- a/tools/perf/util/thread.c
+++ b/tools/perf/util/thread.c
@@ -61,6 +61,7 @@ struct thread *thread__new(pid_t pid, pid_t tid)
 
 		list_add(&comm->list, &thread->comm_list);
 		refcount_set(&thread->refcnt, 1);
+		INIT_LIST_HEAD(&thread->tid_list);
 		RB_CLEAR_NODE(&thread->rb_node);
 		/* Thread holds first ref to nsdata. */
 		thread->nsinfo = nsinfo__new(pid);
@@ -79,6 +80,7 @@ void thread__delete(struct thread *thread)
 	struct comm *comm, *tmp_comm;
 
 	BUG_ON(!RB_EMPTY_NODE(&thread->rb_node));
+	BUG_ON(!list_empty(&thread->tid_list));
 
 	thread_stack__free(thread);
 
@@ -123,7 +125,15 @@ void thread__put(struct thread *thread)
 		 * Remove it from the dead_threads list, as last reference
 		 * is gone.
 		 */
-		list_del_init(&thread->node);
+		if (!RB_EMPTY_NODE(&thread->rb_node)) {
+			struct machine *machine = thread->mg->machine;
+			struct threads *threads = machine__threads(machine, thread->tid);
+
+			rb_erase(&thread->rb_node, &threads->dead);
+			RB_CLEAR_NODE(&thread->rb_node);
+		}
+
+		list_del_init(&thread->tid_list);
 		thread__delete(thread);
 	}
 }
diff --git a/tools/perf/util/thread.h b/tools/perf/util/thread.h
index cc670f02f9f2..0db517e9a1a0 100644
--- a/tools/perf/util/thread.h
+++ b/tools/perf/util/thread.h
@@ -16,10 +16,8 @@ struct thread_stack;
 struct unwind_libunwind_ops;
 
 struct thread {
-	union {
-		struct rb_node	 rb_node;
-		struct list_head node;
-	};
+	struct rb_node		rb_node;
+	struct list_head	tid_list;
 	struct map_groups	*mg;
 	pid_t			pid_; /* Not all tools update this */
 	pid_t			tid;
-- 
2.13.6