Re: [PATCH v1 net-next 2/6] af_unix: Save the number of loops in inflight graph.

[Kuniyuki Iwashima <kuniyu@amazon.com>]

From: Paolo Abeni <pabeni@redhat.com>
Date: Tue, 07 May 2024 15:54:33 +0200
> On Fri, 2024-05-03 at 15:31 -0700, Kuniyuki Iwashima wrote:
> > unix_walk_scc_fast() calls unix_scc_cyclic() for every SCC so that we
> > can make unix_graph_maybe_cyclic false when all SCC are cleaned up.
> > 
> > If we count the number of loops in the graph during Tarjan's algorithm,
> > we need not call unix_scc_cyclic() in unix_walk_scc_fast().
> > 
> > Instead, we can just decrement the number when calling unix_collect_skb()
> > and update unix_graph_maybe_cyclic based on the count.
> > 
> > Signed-off-by: Kuniyuki Iwashima <kuniyu@amazon.com>
> > ---
> >  net/unix/garbage.c | 19 +++++++++++--------
> >  1 file changed, 11 insertions(+), 8 deletions(-)
> > 
> > diff --git a/net/unix/garbage.c b/net/unix/garbage.c
> > index 1f8b8cdfcdc8..7ffb80dd422c 100644
> > --- a/net/unix/garbage.c
> > +++ b/net/unix/garbage.c
> > @@ -405,6 +405,7 @@ static bool unix_scc_cyclic(struct list_head *scc)
> >  
> >  static LIST_HEAD(unix_visited_vertices);
> >  static unsigned long unix_vertex_grouped_index = UNIX_VERTEX_INDEX_MARK2;
> > +static unsigned long unix_graph_circles;
> >  
> >  static void __unix_walk_scc(struct unix_vertex *vertex, unsigned long *last_index,
> >  			    struct sk_buff_head *hitlist)
> > @@ -494,8 +495,8 @@ static void __unix_walk_scc(struct unix_vertex *vertex, unsigned long *last_inde
> >  
> >  		if (scc_dead)
> >  			unix_collect_skb(&scc, hitlist);
> > -		else if (!unix_graph_maybe_cyclic)
> > -			unix_graph_maybe_cyclic = unix_scc_cyclic(&scc);
> > +		else if (unix_scc_cyclic(&scc))
> > +			unix_graph_circles++;
> >  
> >  		list_del(&scc);
> >  	}
> > @@ -509,7 +510,7 @@ static void unix_walk_scc(struct sk_buff_head *hitlist)
> >  {
> >  	unsigned long last_index = UNIX_VERTEX_INDEX_START;
> >  
> > -	unix_graph_maybe_cyclic = false;
> > +	unix_graph_circles = 0;
> >  
> >  	/* Visit every vertex exactly once.
> >  	 * __unix_walk_scc() moves visited vertices to unix_visited_vertices.
> > @@ -524,13 +525,12 @@ static void unix_walk_scc(struct sk_buff_head *hitlist)
> >  	list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices);
> >  	swap(unix_vertex_unvisited_index, unix_vertex_grouped_index);
> >  
> > +	unix_graph_maybe_cyclic = !!unix_graph_circles;
> >  	unix_graph_grouped = true;
> >  }
> >  
> >  static void unix_walk_scc_fast(struct sk_buff_head *hitlist)
> >  {
> > -	unix_graph_maybe_cyclic = false;
> > -
> >  	while (!list_empty(&unix_unvisited_vertices)) {
> >  		struct unix_vertex *vertex;
> >  		struct list_head scc;
> > @@ -546,15 +546,18 @@ static void unix_walk_scc_fast(struct sk_buff_head *hitlist)
> >  				scc_dead = unix_vertex_dead(vertex);
> >  		}
> >  
> > -		if (scc_dead)
> > +		if (scc_dead) {
> >  			unix_collect_skb(&scc, hitlist);
> > -		else if (!unix_graph_maybe_cyclic)
> > -			unix_graph_maybe_cyclic = unix_scc_cyclic(&scc);
> > +			unix_graph_circles--;
> 
> Possibly WARN_ON_ONCE(unix_graph_circles < 0) ?

Will add in v2.

> 
> I find this patch a little scaring - meaning I can't understand it
> fully,
> I'm wondering if it would make any sense to postpone this patch
> to the next cycle?

It's fine by me to postpone patch 2 - 5, but it would be appreciated
if patch 1 makes it to this cycle.

Thanks!