From: Jiri Olsa <jolsa@kernel.org>
To: Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: Frederic Weisbecker <fweisbec@gmail.com>,
lkml <linux-kernel@vger.kernel.org>,
Ingo Molnar <mingo@kernel.org>,
Namhyung Kim <namhyung@kernel.org>,
Alexander Shishkin <alexander.shishkin@linux.intel.com>,
Peter Zijlstra <a.p.zijlstra@chello.nl>,
Andi Kleen <andi@firstfloor.org>,
Alexey Budankov <alexey.budankov@linux.intel.com>
Subject: [PATCH 17/48] perf tools: Convert dead thread list into rbtree
Date: Thu, 13 Sep 2018 14:54:19 +0200 [thread overview]
Message-ID: <20180913125450.21342-18-jolsa@kernel.org> (raw)
In-Reply-To: <20180913125450.21342-1-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 aec68908d604..8c3537f980ed 100644
--- a/tools/perf/util/intel-pt.c
+++ b/tools/perf/util/intel-pt.c
@@ -2517,7 +2517,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 c4acd2001db0..c36c27429866 100644
--- a/tools/perf/util/machine.c
+++ b/tools/perf/util/machine.c
@@ -41,10 +41,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;
}
}
@@ -171,6 +172,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;
@@ -178,6 +201,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) {
@@ -186,6 +210,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);
}
}
@@ -1673,6 +1700,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__set_last_match(threads, NULL);
@@ -1684,14 +1713,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)
@@ -2395,7 +2454,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;
@@ -2408,10 +2467,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 d856b85862e2..d91a3567d2cd 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 a61683157760..47c03001d578 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 64eaa68bb112..d573f3715fec 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.17.1
next prev parent reply other threads:[~2018-09-13 12:55 UTC|newest]
Thread overview: 101+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-09-13 12:54 [RFCv2 00/48] perf tools: Add threads to record command Jiri Olsa
2018-09-13 12:54 ` [PATCH 01/48] perf tools: Remove perf_tool from event_op2 Jiri Olsa
2018-09-25 9:31 ` [tip:perf/core] " tip-bot for Jiri Olsa
2018-09-13 12:54 ` [PATCH 02/48] perf tools: Remove perf_tool from event_op3 Jiri Olsa
2018-09-18 20:56 ` Arnaldo Carvalho de Melo
2018-09-23 19:45 ` Jiri Olsa
2018-09-25 9:31 ` [tip:perf/core] " tip-bot for Jiri Olsa
2018-09-13 12:54 ` [PATCH 03/48] perf tools: Pass struct perf_mmap into auxtrace_mmap__read* functions Jiri Olsa
2018-09-25 9:32 ` [tip:perf/core] perf auxtrace: Pass struct perf_mmap into mmap__read* functions tip-bot for Jiri Olsa
2018-09-13 12:54 ` [PATCH 04/48] perf tools: Add struct perf_mmap arg into record__write Jiri Olsa
2018-09-25 9:32 ` [tip:perf/core] perf tools: Add 'struct perf_mmap' arg to record__write() tip-bot for Jiri Olsa
2018-09-13 12:54 ` [PATCH 05/48] perf tools: Use a software dummy event to track task/mmap events Jiri Olsa
2018-09-13 12:54 ` [PATCH 06/48] perf tools: Create separate mmap for dummy tracking event Jiri Olsa
2018-09-13 12:54 ` [PATCH 07/48] perf tools: Extend perf_evlist__mmap_ex() to use track mmap Jiri Olsa
2018-09-13 12:54 ` [PATCH 08/48] perf report: Skip dummy tracking event Jiri Olsa
2018-09-13 12:54 ` [PATCH 09/48] perf tools: Make copyfile_offset global Jiri Olsa
2018-09-18 20:54 ` Arnaldo Carvalho de Melo
2018-09-23 19:44 ` Jiri Olsa
2018-09-25 9:33 ` [tip:perf/core] perf util: Make copyfile_offset() global tip-bot for Jiri Olsa
2018-09-13 12:54 ` [PATCH 10/48] perf tools: Add HEADER_DATA_INDEX feature Jiri Olsa
2018-09-13 12:54 ` [PATCH 11/48] perf tools: Handle indexed data file properly Jiri Olsa
2018-09-13 12:54 ` [PATCH 12/48] perf tools: Add perf_data__create_index function Jiri Olsa
2018-09-13 12:54 ` [PATCH 13/48] perf record: Add --index option for building index table Jiri Olsa
2018-09-13 12:54 ` [PATCH 14/48] perf tools: Introduce thread__comm(_str)_by_time() helpers Jiri Olsa
2018-09-13 12:54 ` [PATCH 15/48] perf tools: Add a test case for thread comm handling Jiri Olsa
2018-09-13 12:54 ` [PATCH 16/48] perf tools: Use thread__comm_by_time() when adding hist entries Jiri Olsa
2018-09-13 12:54 ` Jiri Olsa [this message]
2018-09-13 12:54 ` [PATCH 18/48] perf tools: Introduce machine__find*_thread_by_time() Jiri Olsa
2018-09-13 12:54 ` [PATCH 19/48] perf tools: Add thread::exited flag Jiri Olsa
2018-09-13 12:54 ` [PATCH 20/48] perf tools: Add a test case for timed thread handling Jiri Olsa
2018-09-13 12:54 ` [PATCH 21/48] perf tools: Maintain map groups list in a leader thread Jiri Olsa
2018-09-13 12:54 ` [PATCH 22/48] perf tools: Introduce thread__find_symbol_by_time() and friends Jiri Olsa
2018-09-13 12:54 ` [PATCH 23/48] perf callchain: Use thread__find_addr_location_by_time() " Jiri Olsa
2018-09-13 12:54 ` [PATCH 24/48] perf tools: Add a test case for timed map groups handling Jiri Olsa
2018-09-13 12:54 ` [PATCH 25/48] perf tools: Save timestamp of a map creation Jiri Olsa
2018-09-13 12:54 ` [PATCH 26/48] perf tools: Introduce map_groups__{insert,find}_by_time() Jiri Olsa
2018-09-13 12:54 ` [PATCH 27/48] perf tools: Use map_groups__find_addr_by_time() Jiri Olsa
2018-09-13 12:54 ` [PATCH 28/48] perf tools: Add testcase for managing maps with time Jiri Olsa
2018-09-13 12:54 ` [PATCH 29/48] perf callchain: Maintain libunwind's address space in map_groups Jiri Olsa
2018-09-14 18:15 ` Arnaldo Carvalho de Melo
2018-09-14 19:00 ` Jiri Olsa
2018-09-13 12:54 ` [PATCH 30/48] perf tools: Rename perf_evlist__munmap_filtered to perf_mmap__put_filtered Jiri Olsa
2018-09-13 12:54 ` [PATCH 31/48] tools lib fd array: Introduce fdarray__add_clone function Jiri Olsa
2018-09-13 12:54 ` [PATCH 32/48] tools lib subcmd: Add OPT_INTEGER_OPTARG|_SET options Jiri Olsa
2018-09-13 12:54 ` [PATCH 33/48] perf tools: Move __perf_session__process_events args into struct Jiri Olsa
2018-09-13 12:54 ` [PATCH 34/48] perf ui progress: Fix index progress display Jiri Olsa
2018-09-13 12:54 ` [PATCH 35/48] perf tools: Add threads debug variable Jiri Olsa
2018-09-13 12:54 ` [PATCH 36/48] perf tools: Add perf_mmap__read_tail function Jiri Olsa
2018-09-13 12:54 ` [PATCH 37/48] perf record: Introduce struct record_thread Jiri Olsa
2018-09-17 11:26 ` Namhyung Kim
2018-09-23 19:31 ` Jiri Olsa
2018-09-13 12:54 ` [PATCH 38/48] perf record: Read record thread's mmaps Jiri Olsa
2018-09-17 11:28 ` Namhyung Kim
2018-09-23 19:35 ` Jiri Olsa
2018-09-13 12:54 ` [PATCH 39/48] perf record: Move waking into struct record Jiri Olsa
2018-09-17 11:31 ` Namhyung Kim
2018-09-23 19:36 ` Jiri Olsa
2018-09-13 12:54 ` [PATCH 40/48] perf record: Move samples into struct record_thread Jiri Olsa
2018-09-13 12:54 ` [PATCH 41/48] perf record: Move bytes_written " Jiri Olsa
2018-09-13 12:54 ` [PATCH 42/48] perf record: Add record_thread start/stop/process functions Jiri Olsa
2018-09-13 12:54 ` [PATCH 43/48] perf record: Wait for all threads being started Jiri Olsa
2018-09-13 12:54 ` [PATCH 44/48] perf record: Add --threads option Jiri Olsa
2018-09-17 11:37 ` Namhyung Kim
2018-09-13 12:54 ` [PATCH 45/48] perf record: Add --thread-stats option support Jiri Olsa
2018-09-13 12:54 ` [PATCH 46/48] perf record: Add maps to --thread-stats output Jiri Olsa
2018-09-13 12:54 ` [PATCH 47/48] perf record: Spread maps for --threads option Jiri Olsa
2018-09-17 11:40 ` Namhyung Kim
2018-09-23 19:44 ` Jiri Olsa
2018-09-24 14:22 ` Arnaldo Carvalho de Melo
2018-09-26 6:23 ` Jiri Olsa
2018-09-27 16:01 ` Jiri Olsa
2018-09-28 6:25 ` Namhyung Kim
2018-09-13 12:54 ` [PATCH 48/48] perf record: Spread maps for --threads=X option Jiri Olsa
2018-09-13 16:10 ` [RFCv2 00/48] perf tools: Add threads to record command Alexey Budankov
2018-09-14 2:29 ` Namhyung Kim
2018-09-14 7:15 ` Alexey Budankov
2018-09-14 8:23 ` Jiri Olsa
2018-09-14 9:40 ` Ingo Molnar
2018-09-14 11:15 ` Peter Zijlstra
2018-09-14 11:47 ` Jiri Olsa
2018-09-14 12:01 ` Peter Zijlstra
2018-09-14 12:13 ` Ingo Molnar
2018-09-14 12:19 ` Jiri Olsa
2018-09-14 12:45 ` Ingo Molnar
2018-09-14 9:33 ` Ingo Molnar
2018-09-14 8:26 ` Jiri Olsa
2018-09-14 8:28 ` Jiri Olsa
2018-09-14 9:37 ` Alexey Budankov
2018-09-21 6:13 ` Alexey Budankov
2018-09-21 12:15 ` Alexey Budankov
2018-09-24 19:23 ` Alexey Budankov
2018-10-02 21:41 ` Jiri Olsa
2018-10-03 7:01 ` Alexey Budankov
2018-09-23 19:30 ` Jiri Olsa
2018-09-24 7:02 ` Alexey Budankov
2018-09-24 13:09 ` Alexey Budankov
2018-09-24 14:29 ` Jiri Olsa
2018-09-24 18:32 ` Alexey Budankov
2018-09-24 19:12 ` Alexey Budankov
2018-10-05 6:14 ` Namhyung Kim
2018-09-14 17:02 ` Andi Kleen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20180913125450.21342-18-jolsa@kernel.org \
--to=jolsa@kernel.org \
--cc=a.p.zijlstra@chello.nl \
--cc=acme@kernel.org \
--cc=alexander.shishkin@linux.intel.com \
--cc=alexey.budankov@linux.intel.com \
--cc=andi@firstfloor.org \
--cc=fweisbec@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=namhyung@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).