[PATCH v5 12/34] function_graph: Use a simple LRU for fgraph_array index number

[Masami Hiramatsu (Google)]

From: Masami Hiramatsu (Google) <mhira...@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) <mhira...@kernel.org>
---
 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 |   67 ++++++++++++++++++++++++++++++++++---------------
 1 file changed, 47 insertions(+), 20 deletions(-)

diff --git a/kernel/trace/fgraph.c b/kernel/trace/fgraph.c
index 6f537ebd3ed7..aa5e4ec9fbb2 100644
--- a/kernel/trace/fgraph.c
+++ b/kernel/trace/fgraph.c
@@ -99,10 +99,44 @@ 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;
+
+static void fgraph_lru_init(void)
+{
+       int i;
+
+       for (i = 0; i < FGRAPH_ARRAY_SIZE; i++)
+               fgraph_lru_table[i] = i;
+}
+
+static int fgraph_lru_release_index(int idx)
+{
+       if (idx < 0 || idx >= FGRAPH_ARRAY_SIZE ||
+           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;
+}
+
+static int fgraph_lru_alloc_index(void)
+{
+       int idx = fgraph_lru_table[fgraph_lru_next];
+
+       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 +401,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)
@@ -932,21 +966,17 @@ 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 = -EBUSY;
                goto out;
        }
 
        fgraph_array[i] = gops;
-       if (i + 1 > fgraph_array_cnt)
-               fgraph_array_cnt = i + 1;
        gops->idx = i;
 
        ftrace_graph_active++;
@@ -976,25 +1006,22 @@ 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))
+               goto out;
+
+       if (WARN_ON_ONCE(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--;