From: "Masami Hiramatsu (Google)" <mhiramat@kernel.org>
To: Alexei Starovoitov <alexei.starovoitov@gmail.com>,
Steven Rostedt <rostedt@goodmis.org>,
Florent Revest <revest@chromium.org>
Cc: linux-trace-kernel@vger.kernel.org,
LKML <linux-kernel@vger.kernel.org>,
Martin KaFai Lau <martin.lau@linux.dev>,
bpf <bpf@vger.kernel.org>, Sven Schnelle <svens@linux.ibm.com>,
Alexei Starovoitov <ast@kernel.org>, Jiri Olsa <jolsa@kernel.org>,
Arnaldo Carvalho de Melo <acme@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>,
Alan Maguire <alan.maguire@oracle.com>,
Mark Rutland <mark.rutland@arm.com>,
Peter Zijlstra <peterz@infradead.org>,
Thomas Gleixner <tglx@linutronix.de>, Guo Ren <guoren@kernel.org>
Subject: [PATCH v9 13/36] function_graph: Use a simple LRU for fgraph_array index number
Date: Mon, 15 Apr 2024 21:51:31 +0900 [thread overview]
Message-ID: <171318549135.254850.10548833007838101346.stgit@devnote2> (raw)
In-Reply-To: <171318533841.254850.15841395205784342850.stgit@devnote2>
From: Masami Hiramatsu (Google) <mhiramat@kernel.org>
Since the fgraph_array index is used for the bitmap on the shadow
stack, it may leave some entries after a function_graph instance is
removed. Thus if another instance reuses the fgraph_array index soon
after releasing it, the fgraph may confuse to call the newer callback
for the entries which are pushed by the older instance.
To avoid reusing the fgraph_array index soon after releasing, introduce
a simple LRU table for managing the index number. This will reduce the
possibility of this confusion.
Signed-off-by: Masami Hiramatsu (Google) <mhiramat@kernel.org>
---
Changes in v8:
- Add a WARN_ON_ONCE() if fgraph_lru_table[] is broken when releasing
index, and remove WARN_ON_ONCE() from unregister_ftrace_graph()
- Fix to release allocated index if register_ftrace_graph() fails.
- Add comments and code cleanup.
Changes in v5:
- Fix the underflow bug in fgraph_lru_release_index() and return 0
if the release is succeded.
Changes in v4:
- Newly added.
---
kernel/trace/fgraph.c | 71 +++++++++++++++++++++++++++++++++++--------------
1 file changed, 50 insertions(+), 21 deletions(-)
diff --git a/kernel/trace/fgraph.c b/kernel/trace/fgraph.c
index aa9a4fac3373..7e73bc3eab8b 100644
--- a/kernel/trace/fgraph.c
+++ b/kernel/trace/fgraph.c
@@ -99,10 +99,48 @@ enum {
DEFINE_STATIC_KEY_FALSE(kill_ftrace_graph);
int ftrace_graph_active;
-static int fgraph_array_cnt;
-
static struct fgraph_ops *fgraph_array[FGRAPH_ARRAY_SIZE];
+/* LRU index table for fgraph_array */
+static int fgraph_lru_table[FGRAPH_ARRAY_SIZE];
+static int fgraph_lru_next;
+static int fgraph_lru_last;
+
+/* Initialize fgraph_lru_table with unused index */
+static void fgraph_lru_init(void)
+{
+ int i;
+
+ for (i = 0; i < FGRAPH_ARRAY_SIZE; i++)
+ fgraph_lru_table[i] = i;
+}
+
+/* Release the used index to the LRU table */
+static int fgraph_lru_release_index(int idx)
+{
+ if (idx < 0 || idx >= FGRAPH_ARRAY_SIZE ||
+ WARN_ON_ONCE(fgraph_lru_table[fgraph_lru_last] != -1))
+ return -1;
+
+ fgraph_lru_table[fgraph_lru_last] = idx;
+ fgraph_lru_last = (fgraph_lru_last + 1) % FGRAPH_ARRAY_SIZE;
+ return 0;
+}
+
+/* Allocate a new index from LRU table */
+static int fgraph_lru_alloc_index(void)
+{
+ int idx = fgraph_lru_table[fgraph_lru_next];
+
+ /* No id is available */
+ if (idx == -1)
+ return -1;
+
+ fgraph_lru_table[fgraph_lru_next] = -1;
+ fgraph_lru_next = (fgraph_lru_next + 1) % FGRAPH_ARRAY_SIZE;
+ return idx;
+}
+
static inline int get_ret_stack_index(struct task_struct *t, int offset)
{
return t->ret_stack[offset] & FGRAPH_RET_INDEX_MASK;
@@ -367,7 +405,7 @@ int function_graph_enter(unsigned long ret, unsigned long func,
if (index < 0)
goto out;
- for (i = 0; i < fgraph_array_cnt; i++) {
+ for (i = 0; i < FGRAPH_ARRAY_SIZE; i++) {
struct fgraph_ops *gops = fgraph_array[i];
if (gops == &fgraph_stub)
@@ -919,7 +957,7 @@ int register_ftrace_graph(struct fgraph_ops *gops)
{
int command = 0;
int ret = 0;
- int i;
+ int i = -1;
mutex_lock(&ftrace_lock);
@@ -935,21 +973,16 @@ int register_ftrace_graph(struct fgraph_ops *gops)
/* The array must always have real data on it */
for (i = 0; i < FGRAPH_ARRAY_SIZE; i++)
fgraph_array[i] = &fgraph_stub;
+ fgraph_lru_init();
}
- /* Look for an available spot */
- for (i = 0; i < FGRAPH_ARRAY_SIZE; i++) {
- if (fgraph_array[i] == &fgraph_stub)
- break;
- }
- if (i >= FGRAPH_ARRAY_SIZE) {
+ i = fgraph_lru_alloc_index();
+ if (i < 0 || WARN_ON_ONCE(fgraph_array[i] != &fgraph_stub)) {
ret = -ENOSPC;
goto out;
}
fgraph_array[i] = gops;
- if (i + 1 > fgraph_array_cnt)
- fgraph_array_cnt = i + 1;
gops->idx = i;
ftrace_graph_active++;
@@ -973,6 +1006,7 @@ int register_ftrace_graph(struct fgraph_ops *gops)
if (ret) {
fgraph_array[i] = &fgraph_stub;
ftrace_graph_active--;
+ fgraph_lru_release_index(i);
}
out:
mutex_unlock(&ftrace_lock);
@@ -982,25 +1016,20 @@ int register_ftrace_graph(struct fgraph_ops *gops)
void unregister_ftrace_graph(struct fgraph_ops *gops)
{
int command = 0;
- int i;
mutex_lock(&ftrace_lock);
if (unlikely(!ftrace_graph_active))
goto out;
- if (unlikely(gops->idx < 0 || gops->idx >= fgraph_array_cnt))
+ if (unlikely(gops->idx < 0 || gops->idx >= FGRAPH_ARRAY_SIZE ||
+ fgraph_array[gops->idx] != gops))
goto out;
- WARN_ON_ONCE(fgraph_array[gops->idx] != gops);
+ if (fgraph_lru_release_index(gops->idx) < 0)
+ goto out;
fgraph_array[gops->idx] = &fgraph_stub;
- if (gops->idx + 1 == fgraph_array_cnt) {
- i = gops->idx;
- while (i >= 0 && fgraph_array[i] == &fgraph_stub)
- i--;
- fgraph_array_cnt = i + 1;
- }
ftrace_graph_active--;
next prev parent reply other threads:[~2024-04-15 12:51 UTC|newest]
Thread overview: 59+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-04-15 12:48 [PATCH v9 00/36] tracing: fprobe: function_graph: Multi-function graph and fprobe on fgraph Masami Hiramatsu (Google)
2024-04-15 12:49 ` [PATCH v9 01/36] tracing: Add a comment about ftrace_regs definition Masami Hiramatsu (Google)
2024-04-24 12:23 ` Florent Revest
2024-04-24 13:19 ` Florent Revest
2024-04-24 14:31 ` Masami Hiramatsu
2024-04-15 12:49 ` [PATCH v9 02/36] tracing: Rename ftrace_regs_return_value to ftrace_regs_get_return_value Masami Hiramatsu (Google)
2024-04-15 12:49 ` [PATCH v9 03/36] x86: tracing: Add ftrace_regs definition in the header Masami Hiramatsu (Google)
2024-04-15 12:49 ` [PATCH v9 04/36] function_graph: Convert ret_stack to a series of longs Masami Hiramatsu (Google)
2024-04-15 12:49 ` [PATCH v9 05/36] fgraph: Use BUILD_BUG_ON() to make sure we have structures divisible by long Masami Hiramatsu (Google)
2024-04-15 12:50 ` [PATCH v9 06/36] function_graph: Add an array structure that will allow multiple callbacks Masami Hiramatsu (Google)
2024-04-15 12:50 ` [PATCH v9 07/36] function_graph: Allow multiple users to attach to function graph Masami Hiramatsu (Google)
2024-04-20 3:52 ` Steven Rostedt
2024-04-20 8:56 ` Masami Hiramatsu
2024-04-15 12:50 ` [PATCH v9 08/36] function_graph: Remove logic around ftrace_graph_entry and return Masami Hiramatsu (Google)
2024-04-15 12:50 ` [PATCH v9 09/36] ftrace/function_graph: Pass fgraph_ops to function graph callbacks Masami Hiramatsu (Google)
2024-04-15 12:50 ` [PATCH v9 10/36] ftrace: Allow function_graph tracer to be enabled in instances Masami Hiramatsu (Google)
2024-04-15 12:51 ` [PATCH v9 11/36] ftrace: Allow ftrace startup flags exist without dynamic ftrace Masami Hiramatsu (Google)
2024-04-15 12:51 ` [PATCH v9 12/36] function_graph: Have the instances use their own ftrace_ops for filtering Masami Hiramatsu (Google)
2024-04-15 12:51 ` Masami Hiramatsu (Google) [this message]
2024-04-15 12:51 ` [PATCH v9 14/36] function_graph: Add "task variables" per task for fgraph_ops Masami Hiramatsu (Google)
2024-04-15 12:51 ` [PATCH v9 15/36] function_graph: Move set_graph_function tests to shadow stack global var Masami Hiramatsu (Google)
2024-04-15 12:52 ` [PATCH v9 16/36] function_graph: Move graph depth stored data " Masami Hiramatsu (Google)
2024-04-15 12:52 ` [PATCH v9 17/36] function_graph: Move graph notrace bit " Masami Hiramatsu (Google)
2024-04-15 12:52 ` [PATCH v9 18/36] function_graph: Implement fgraph_reserve_data() and fgraph_retrieve_data() Masami Hiramatsu (Google)
2024-04-15 12:52 ` [PATCH v9 19/36] function_graph: Add selftest for passing local variables Masami Hiramatsu (Google)
2024-04-15 12:52 ` [PATCH v9 20/36] ftrace: Add multiple fgraph storage selftest Masami Hiramatsu (Google)
2024-04-15 12:53 ` [PATCH v9 21/36] function_graph: Pass ftrace_regs to entryfunc Masami Hiramatsu (Google)
2024-04-15 12:53 ` [PATCH v9 22/36] function_graph: Replace fgraph_ret_regs with ftrace_regs Masami Hiramatsu (Google)
2024-04-15 12:53 ` [PATCH v9 23/36] function_graph: Pass ftrace_regs to retfunc Masami Hiramatsu (Google)
2024-04-15 12:53 ` [PATCH v9 24/36] fprobe: Use ftrace_regs in fprobe entry handler Masami Hiramatsu (Google)
2024-04-15 12:53 ` [PATCH v9 25/36] fprobe: Use ftrace_regs in fprobe exit handler Masami Hiramatsu (Google)
2024-04-15 12:54 ` [PATCH v9 26/36] tracing: Add ftrace_partial_regs() for converting ftrace_regs to pt_regs Masami Hiramatsu (Google)
2024-04-15 12:54 ` [PATCH v9 27/36] tracing: Add ftrace_fill_perf_regs() for perf event Masami Hiramatsu (Google)
2024-04-15 12:54 ` [PATCH v9 28/36] tracing/fprobe: Enable fprobe events with CONFIG_DYNAMIC_FTRACE_WITH_ARGS Masami Hiramatsu (Google)
2024-04-15 12:54 ` [PATCH v9 29/36] bpf: Enable kprobe_multi feature if CONFIG_FPROBE is enabled Masami Hiramatsu (Google)
2024-04-25 20:09 ` Andrii Nakryiko
2024-04-29 14:57 ` Masami Hiramatsu
2024-04-15 12:54 ` [PATCH v9 30/36] ftrace: Add CONFIG_HAVE_FTRACE_GRAPH_FUNC Masami Hiramatsu (Google)
2024-04-15 12:55 ` [PATCH v9 31/36] fprobe: Rewrite fprobe on function-graph tracer Masami Hiramatsu (Google)
2024-04-15 12:55 ` [PATCH v9 32/36] tracing/fprobe: Remove nr_maxactive from fprobe Masami Hiramatsu (Google)
2024-04-15 12:55 ` [PATCH v9 33/36] selftests: ftrace: Remove obsolate maxactive syntax check Masami Hiramatsu (Google)
2024-04-15 12:55 ` [PATCH v9 34/36] selftests/ftrace: Add a test case for repeating register/unregister fprobe Masami Hiramatsu (Google)
2024-04-15 12:55 ` [PATCH v9 35/36] Documentation: probes: Update fprobe on function-graph tracer Masami Hiramatsu (Google)
2024-04-15 12:55 ` [PATCH v9 36/36] fgraph: Skip recording calltime/rettime if it is not nneeded Masami Hiramatsu (Google)
2024-04-25 20:15 ` Andrii Nakryiko
2024-04-29 14:56 ` Masami Hiramatsu
2024-04-19 5:36 ` [PATCH v9 00/36] tracing: fprobe: function_graph: Multi-function graph and fprobe on fgraph Masami Hiramatsu
2024-04-19 8:01 ` Steven Rostedt
2024-04-24 13:35 ` Florent Revest
2024-04-25 15:10 ` Masami Hiramatsu
2024-04-25 20:31 ` Andrii Nakryiko
2024-04-28 23:25 ` Steven Rostedt
2024-04-29 20:28 ` Andrii Nakryiko
2024-04-29 13:51 ` Masami Hiramatsu
2024-04-29 20:25 ` Andrii Nakryiko
2024-04-30 13:32 ` Masami Hiramatsu
2024-04-30 16:29 ` Andrii Nakryiko
2024-05-02 2:06 ` Masami Hiramatsu
2024-05-07 21:04 ` Andrii Nakryiko
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=171318549135.254850.10548833007838101346.stgit@devnote2 \
--to=mhiramat@kernel.org \
--cc=acme@kernel.org \
--cc=alan.maguire@oracle.com \
--cc=alexei.starovoitov@gmail.com \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=guoren@kernel.org \
--cc=jolsa@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-trace-kernel@vger.kernel.org \
--cc=mark.rutland@arm.com \
--cc=martin.lau@linux.dev \
--cc=peterz@infradead.org \
--cc=revest@chromium.org \
--cc=rostedt@goodmis.org \
--cc=svens@linux.ibm.com \
--cc=tglx@linutronix.de \
/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 read-only IMAP folder(s) and NNTP newsgroup(s).