Re: [PATCH v7 14/36] function_graph: Use a simple LRU for fgraph_array index number

Masami Hiramatsu
2024-02-14T23:48:10Z

On Wed, 14 Feb 2024 13:04:09 -0500
Steven Rostedt <rostedt@goodmis.org> wrote:

> On Wed, 7 Feb 2024 00:10:04 +0900
> "Masami Hiramatsu (Google)" <mhiramat@kernel.org> wrote:
>
> > diff --git a/kernel/trace/fgraph.c b/kernel/trace/fgraph.c
> > index ae42de909845..323a74623543 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)
>
> Can fgraph_lru_table[fgraph_lru_last] != -1 ever happen? If not, we should
> probably add a:
>
> WARN_ON_ONCE(fgraph_lru_table[fgraph_lru_last] != -1))
>
> As the size of fgraph_lru_table is the same size as the available indexes,
> if we hit this I would think we had a fgraph_lru_relaese_index() without a
> fgraph_lru_alloc_index() associated with it.

OK, let me make it warning.

>
> > + 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)
> > @@ -935,21 +969,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)) {
>
> The above can nicely fit on one column. No need to break it up:
>
> if (i < 0 || WARN_ON_ONCE(fgraph_array[i] != &fgraph_stub)) {

OK.

>
>
> > 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++;
> > @@ -979,25 +1009,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;
>
> Removing the above WARN_ON_ONCE() is more reason to add it to the release
> function.

OK.

Thank you for review!

>
> -- Steve
>
>
> >
> > 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--;
> >
>

--
Masami Hiramatsu (Google) <mhiramat@kernel.org>