[RFC/PATCH 14/38] perf tools: Convert dead thread list into rbtree

[Namhyung Kim <namhyung@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>
Signed-off-by: Namhyung Kim <namhyung@kernel.org>
---
 tools/perf/util/machine.c | 82 +++++++++++++++++++++++++++++++++++++++++------
 tools/perf/util/machine.h |  2 +-
 tools/perf/util/thread.c  | 18 ++++++++++-
 tools/perf/util/thread.h  | 11 +++----
 4 files changed, 96 insertions(+), 17 deletions(-)

diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c
index 5ef90be2a249..2b9fbe55c896 100644
--- a/tools/perf/util/machine.c
+++ b/tools/perf/util/machine.c
@@ -30,8 +30,8 @@ int machine__init(struct machine *machine, const char *root_dir, pid_t pid)
 	dsos__init(&machine->dsos);
 
 	machine->threads = RB_ROOT;
+	machine->dead_threads = RB_ROOT;
 	pthread_rwlock_init(&machine->threads_lock, NULL);
-	INIT_LIST_HEAD(&machine->dead_threads);
 	machine->last_match = NULL;
 
 	machine->vdso_info = NULL;
@@ -104,6 +104,28 @@ static void dsos__exit(struct dsos *dsos)
 	pthread_rwlock_destroy(&dsos->lock);
 }
 
+static void machine__delete_dead_threads(struct machine *machine)
+{
+	struct rb_node *nd = rb_first(&machine->dead_threads);
+
+	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, &machine->dead_threads);
+
+		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;
@@ -117,6 +139,8 @@ void machine__delete_threads(struct machine *machine)
 		__machine__remove_thread(machine, t, false);
 	}
 	pthread_rwlock_unlock(&machine->threads_lock);
+
+	machine__delete_dead_threads(machine);
 }
 
 void machine__exit(struct machine *machine)
@@ -1361,6 +1385,10 @@ out_problem:
 
 static void __machine__remove_thread(struct machine *machine, struct thread *th, bool lock)
 {
+	struct rb_node **p = &machine->dead_threads.rb_node;
+	struct rb_node *parent = NULL;
+	struct thread *pos;
+
 	if (machine->last_match == th)
 		machine->last_match = NULL;
 
@@ -1368,16 +1396,45 @@ static void __machine__remove_thread(struct machine *machine, struct thread *th,
 	if (lock)
 		pthread_rwlock_wrlock(&machine->threads_lock);
 	rb_erase_init(&th->rb_node, &machine->threads);
-	RB_CLEAR_NODE(&th->rb_node);
+
+	th->dead = true;
+
 	/*
-	 * 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.
 	 */
-	list_add_tail(&th->node, &machine->dead_threads);
+	if (!perf_has_index) {
+		thread__put(th);
+		goto out;
+	}
+
+	/*
+	 * 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.
+	 */
+	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, &machine->dead_threads);
+
+out:
 	if (lock)
 		pthread_rwlock_unlock(&machine->threads_lock);
-	thread__put(th);
 }
 
 void machine__remove_thread(struct machine *machine, struct thread *th)
@@ -1899,7 +1956,7 @@ int machine__for_each_thread(struct machine *machine,
 			     void *priv)
 {
 	struct rb_node *nd;
-	struct thread *thread;
+	struct thread *thread, *pos;
 	int rc = 0;
 
 	for (nd = rb_first(&machine->threads); nd; nd = rb_next(nd)) {
@@ -1909,10 +1966,17 @@ int machine__for_each_thread(struct machine *machine,
 			return rc;
 	}
 
-	list_for_each_entry(thread, &machine->dead_threads, node) {
+	for (nd = rb_first(&machine->dead_threads); 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 2c2b443df5ba..23242de926df 100644
--- a/tools/perf/util/machine.h
+++ b/tools/perf/util/machine.h
@@ -30,8 +30,8 @@ struct machine {
 	bool		  comm_exec;
 	char		  *root_dir;
 	struct rb_root	  threads;
+	struct rb_root	  dead_threads;
 	pthread_rwlock_t  threads_lock;
-	struct list_head  dead_threads;
 	struct thread	  *last_match;
 	struct vdso_info  *vdso_info;
 	struct perf_env   *env;
diff --git a/tools/perf/util/thread.c b/tools/perf/util/thread.c
index 8244397753fd..674792e8fa2f 100644
--- a/tools/perf/util/thread.c
+++ b/tools/perf/util/thread.c
@@ -9,6 +9,7 @@
 #include "debug.h"
 #include "comm.h"
 #include "unwind.h"
+#include "machine.h"
 
 int thread__init_map_groups(struct thread *thread, struct machine *machine)
 {
@@ -54,6 +55,7 @@ struct thread *thread__new(pid_t pid, pid_t tid)
 
 		list_add(&comm->list, &thread->comm_list);
 		atomic_set(&thread->refcnt, 0);
+		INIT_LIST_HEAD(&thread->tid_list);
 		RB_CLEAR_NODE(&thread->rb_node);
 	}
 
@@ -69,6 +71,7 @@ void thread__delete(struct thread *thread)
 	struct comm *comm, *tmp;
 
 	BUG_ON(!RB_EMPTY_NODE(&thread->rb_node));
+	BUG_ON(!list_empty(&thread->tid_list));
 
 	thread_stack__free(thread);
 
@@ -95,7 +98,20 @@ struct thread *thread__get(struct thread *thread)
 void thread__put(struct thread *thread)
 {
 	if (thread && atomic_dec_and_test(&thread->refcnt)) {
-		list_del_init(&thread->node);
+		if (!RB_EMPTY_NODE(&thread->rb_node)) {
+			struct machine *machine = thread->mg->machine;
+
+			if (thread->dead) {
+				rb_erase(&thread->rb_node,
+					 &machine->dead_threads);
+			} else {
+				rb_erase(&thread->rb_node,
+					 &machine->threads);
+			}
+			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 33418e6dc64a..b8f794d97b75 100644
--- a/tools/perf/util/thread.h
+++ b/tools/perf/util/thread.h
@@ -13,10 +13,8 @@
 struct thread_stack;
 
 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;
@@ -26,7 +24,8 @@ struct thread {
 	char			shortname[3];
 	bool			comm_set;
 	int			comm_len;
-	bool			dead; /* if set thread has exited */
+	bool			exited; /* if set thread has exited */
+	bool			dead; /* thread is in dead_threads list */
 	struct list_head	comm_list;
 	u64			db_id;
 
@@ -54,7 +53,7 @@ static inline void __thread__zput(struct thread **thread)
 
 static inline void thread__exited(struct thread *thread)
 {
-	thread->dead = true;
+	thread->exited = true;
 }
 
 int __thread__set_comm(struct thread *thread, const char *comm, u64 timestamp,
-- 
2.6.0