[PATCH 11/20] function_graph: Use a simple LRU for fgraph_array index number

From: Steven Rostedt
Date: Fri May 24 2024 - 22:40:21 EST


From: "Masami Hiramatsu (Google)" <mhiramat@xxxxxxxxxx>

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.

Link: https://lore.kernel.org/linux-trace-kernel/171509103267.162236.6885097397289135378.stgit@devnote2

Signed-off-by: Masami Hiramatsu (Google) <mhiramat@xxxxxxxxxx>
Signed-off-by: Steven Rostedt (Google) <rostedt@xxxxxxxxxxx>
---
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 67fa7fbf6aac..8e029d5e94f6 100644
--- a/kernel/trace/fgraph.c
+++ b/kernel/trace/fgraph.c
@@ -125,10 +125,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;
+}
+
/* Get the FRAME_OFFSET from the word from the @offset on ret_stack */
static inline int get_frame_offset(struct task_struct *t, int offset)
{
@@ -375,7 +413,7 @@ int function_graph_enter(unsigned long ret, unsigned long func,
if (offset < 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)
@@ -927,7 +965,7 @@ int register_ftrace_graph(struct fgraph_ops *gops)
{
int command = 0;
int ret = 0;
- int i;
+ int i = -1;

mutex_lock(&ftrace_lock);

@@ -943,21 +981,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++;
@@ -981,6 +1014,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);
@@ -990,25 +1024,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--;

--
2.43.0