Messages in this thread Patch in this message | | | From | Namhyung Kim <> | Subject | [RFC/PATCH 14/38] perf tools: Convert dead thread list into rbtree | Date | Fri, 2 Oct 2015 14:18:55 +0900 |
| |
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
| |