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

Jiri Olsa
2018-01-09T15:36:14Z

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