From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753203AbbERAtN (ORCPT ); Sun, 17 May 2015 20:49:13 -0400 Received: from LGEMRELSE6Q.lge.com ([156.147.1.121]:54882 "EHLO lgemrelse6q.lge.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752106AbbERAlX (ORCPT ); Sun, 17 May 2015 20:41:23 -0400 X-Original-SENDERIP: 10.177.220.203 X-Original-MAILFROM: namhyung@kernel.org From: Namhyung Kim To: Arnaldo Carvalho de Melo Cc: Ingo Molnar , Peter Zijlstra , Jiri Olsa , LKML , David Ahern , Adrian Hunter , Andi Kleen , Frederic Weisbecker , Stephane Eranian Subject: [PATCH 13/40] perf tools: Convert dead thread list into rbtree Date: Mon, 18 May 2015 09:30:28 +0900 Message-Id: <1431909055-21442-14-git-send-email-namhyung@kernel.org> X-Mailer: git-send-email 2.4.0 In-Reply-To: <1431909055-21442-1-git-send-email-namhyung@kernel.org> References: <1431909055-21442-1-git-send-email-namhyung@kernel.org> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.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-file 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 Signed-off-by: Namhyung Kim --- tools/perf/util/machine.c | 80 ++++++++++++++++++++++++++++++++++++++++++----- tools/perf/util/machine.h | 2 +- tools/perf/util/thread.c | 21 +++++++++++-- tools/perf/util/thread.h | 11 +++---- 4 files changed, 96 insertions(+), 18 deletions(-) diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c index 34bf89f7f4f3..ae07b84a40f5 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->kernel_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; @@ -93,6 +93,29 @@ static void dsos__delete(struct dsos *dsos) } } +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(&t->rb_node, &machine->dead_threads); + RB_CLEAR_NODE(&t->rb_node); + + while (!list_empty(&t->tid_node)) { + pos = list_first_entry(&t->tid_node, + struct thread, tid_node); + list_del_init(&pos->tid_node); + thread__delete(pos); + } + + thread__delete(t); + } +} + void machine__delete_threads(struct machine *machine) { struct rb_node *nd; @@ -106,6 +129,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) @@ -1308,6 +1333,10 @@ 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 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; @@ -1316,15 +1345,43 @@ static void __machine__remove_thread(struct machine *machine, struct thread *th, pthread_rwlock_wrlock(&machine->threads_lock); rb_erase(&th->rb_node, &machine->threads); RB_CLEAR_NODE(&th->rb_node); + + th->dead = true; + + /* + * No need to have an additional reference for non-index file. + */ + if (!perf_has_index) { + thread__put(th); + goto out; + } + /* - * 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. + * 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. */ - list_add_tail(&th->node, &machine->dead_threads); + while (*p != NULL) { + parent = *p; + pos = rb_entry(parent, struct thread, rb_node); + + if (pos->tid == th->tid) { + list_add_tail(&th->tid_node, &pos->tid_node); + 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) @@ -1826,7 +1883,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)) { @@ -1836,10 +1893,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_node, tid_node) { + 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 c7963c63c474..53cdd1aad3ff 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 dsos user_dsos; diff --git a/tools/perf/util/thread.c b/tools/perf/util/thread.c index 962558024415..ccf1808348fe 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) { @@ -38,6 +39,7 @@ struct thread *thread__new(pid_t pid, pid_t tid) thread->ppid = -1; thread->cpu = -1; INIT_LIST_HEAD(&thread->comm_list); + INIT_LIST_HEAD(&thread->tid_node); if (unwind__prepare_access(thread) < 0) goto err_thread; @@ -54,7 +56,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->node); + INIT_LIST_HEAD(&thread->tid_node); RB_CLEAR_NODE(&thread->rb_node); } @@ -70,7 +72,7 @@ void thread__delete(struct thread *thread) struct comm *comm, *tmp; BUG_ON(!RB_EMPTY_NODE(&thread->rb_node)); - BUG_ON(!list_empty(&thread->node)); + BUG_ON(!list_empty(&thread->tid_node)); thread_stack__free(thread); @@ -97,7 +99,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_node); thread__delete(thread); } } diff --git a/tools/perf/util/thread.h b/tools/perf/util/thread.h index 903cfaf2628d..d6f6f150f3ff 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_node; struct map_groups *mg; pid_t pid_; /* Not all tools update this */ pid_t tid; @@ -25,7 +23,8 @@ struct thread { atomic_t refcnt; char shortname[3]; bool comm_set; - 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; int comm_len; 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.4.0