diff mbox series

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

Message ID 170723220474.502590.7646977373091779892.stgit@devnote2 (mailing list archive)
State Superseded
Headers show
Series tracing: fprobe: function_graph: Multi-function graph and fprobe on fgraph | expand

Commit Message

Masami Hiramatsu (Google) Feb. 6, 2024, 3:10 p.m. UTC 
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 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(-)

Comments

Steven Rostedt Feb. 14, 2024, 6:04 p.m. UTC | #1 
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.

> +		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)) {


>  		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.

-- 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) Feb. 14, 2024, 11:48 p.m. UTC | #2 
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--;
> >  
>
diff mbox series

Patch

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)
+		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)) {
 		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;
 
 	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--;