Date: Tue, 27 Feb 2024 12:02:27 +0100
From: Paolo Abeni <pabeni@...hat.com>
To: Kuniyuki Iwashima <kuniyu@...zon.com>, "David S. Miller"
	 <davem@...emloft.net>, Eric Dumazet <edumazet@...gle.com>, Jakub Kicinski
	 <kuba@...nel.org>
Cc: Kuniyuki Iwashima <kuni1840@...il.com>, netdev@...r.kernel.org
Subject: Re: [PATCH v3 net-next 05/14] af_unix: Detect Strongly Connected
 Components.

On Fri, 2024-02-23 at 13:39 -0800, Kuniyuki Iwashima wrote:
> In the new GC, we use a simple graph algorithm, Tarjan's Strongly
> Connected Components (SCC) algorithm, to find cyclic references.
> 
> The algorithm visits every vertex exactly once using depth-first
> search (DFS).  We implement it without recursion so that no one
> can abuse it.
> 
> There could be multiple graphs, so we iterate unix_unvisited_vertices
> in unix_walk_scc() and do DFS in __unix_walk_scc(), where we move
> visited vertices to another list, unix_visited_vertices, not to
> restart DFS twice on a visited vertex later in unix_walk_scc().
> 
> DFS starts by pushing an input vertex to a stack and assigning it
> a unique number.  Two fields, index and lowlink, are initialised
> with the number, but lowlink could be updated later during DFS.
> 
> If a vertex has an edge to an unvisited inflight vertex, we visit
> it and do the same processing.  So, we will have vertices in the
> stack in the order they appear and number them consecutively in
> the same order.
> 
> If a vertex has a back-edge to a visited vertex in the stack,
> we update the predecessor's lowlink with the successor's index.
> 
> After iterating edges from the vertex, we check if its index
> equals its lowlink.
> 
> If the lowlink is different from the index, it shows there was a
> back-edge.  Then, we propagate the lowlink to its predecessor and
> go back to the predecessor to resume checking from the next edge
> of the back-edge.
> 
> If the lowlink is the same as the index, we pop vertices before
> and including the vertex from the stack.  Then, the set of vertices
> is SCC, possibly forming a cycle.  At the same time, we move the
> vertices to unix_visited_vertices.
> 
> When we finish the algorithm, all vertices in each SCC will be
> linked via unix_vertex.scc_entry.
> 
> Let's take an example.  We have a graph including five inflight
> vertices (F is not inflight):
> 
>   A -> B -> C -> D -> E (-> F)
>        ^         |
>        `---------'
> 
> Suppose that we start DFS from C.  We will visit C, D, and B first
> and initialise their index and lowlink.  Then, the stack looks like
> this:
> 
>   > B = (3, 3)  (index, lowlink)
>     D = (2, 2)
>     C = (1, 1)
> 
> When checking B's edge to C, we update B's lowlink with C's index
> and propagate it to D.
> 
>     B = (3, 1)  (index, lowlink)
>   > D = (2, 1)
>     C = (1, 1)
> 
> Next, we visit E, which has no edge to an inflight vertex.
> 
>   > E = (4, 4)  (index, lowlink)
>     B = (3, 1)
>     D = (2, 1)
>     C = (1, 1)
> 
> When we leave from E, its index and lowlink are the same, so we
> pop E from the stack as single-vertex SCC.  Next, we leave from
> D but do nothing because its lowlink is different from its index.
> 
>     B = (3, 1)  (index, lowlink)
>     D = (2, 1)
>   > C = (1, 1)
> 
> Then, we leave from C, whose index and lowlink are the same, so
> we pop B, D and C as SCC.
> 
> Last, we do DFS for the rest of vertices, A, which is also a
> single-vertex SCC.
> 
> Finally, each unix_vertex.scc_entry is linked as follows:
> 
>   A -.  B -> C -> D  E -.
>   ^  |  ^         |  ^  |
>   `--'  `---------'  `--'
> 
> We use SCC later to decide whether we can garbage-collect the
> sockets.
> 
> Note that we still cannot detect SCC properly if an edge points
> to an embryo socket.  The following two patches will sort it out.
> 
> Signed-off-by: Kuniyuki Iwashima <kuniyu@...zon.com>
> ---
>  include/net/af_unix.h |  5 +++
>  net/unix/garbage.c    | 82 +++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 87 insertions(+)
> 
> diff --git a/include/net/af_unix.h b/include/net/af_unix.h
> index f31ad1166346..67736767b616 100644
> --- a/include/net/af_unix.h
> +++ b/include/net/af_unix.h
> @@ -32,13 +32,18 @@ void wait_for_unix_gc(struct scm_fp_list *fpl);
>  struct unix_vertex {
>  	struct list_head edges;
>  	struct list_head entry;
> +	struct list_head scc_entry;
>  	unsigned long out_degree;
> +	unsigned long index;
> +	unsigned long lowlink;
> +	bool on_stack;
>  };
>  
>  struct unix_edge {
>  	struct unix_sock *predecessor;
>  	struct unix_sock *successor;
>  	struct list_head vertex_entry;
> +	struct list_head stack_entry;
>  };
>  
>  struct sock *unix_peer_get(struct sock *sk);
> diff --git a/net/unix/garbage.c b/net/unix/garbage.c
> index e8fe08796d02..7e90663513f9 100644
> --- a/net/unix/garbage.c
> +++ b/net/unix/garbage.c
> @@ -103,6 +103,11 @@ struct unix_sock *unix_get_socket(struct file *filp)
>  
>  static LIST_HEAD(unix_unvisited_vertices);
>  
> +enum unix_vertex_index {
> +	UNIX_VERTEX_INDEX_UNVISITED,
> +	UNIX_VERTEX_INDEX_START,
> +};
> +
>  static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge)
>  {
>  	struct unix_vertex *vertex = edge->predecessor->vertex;
> @@ -245,6 +250,81 @@ void unix_destroy_fpl(struct scm_fp_list *fpl)
>  	unix_free_vertices(fpl);
>  }
>  
> +static LIST_HEAD(unix_visited_vertices);
> +
> +static void __unix_walk_scc(struct unix_vertex *vertex)
> +{
> +	unsigned long index = UNIX_VERTEX_INDEX_START;
> +	LIST_HEAD(vertex_stack);
> +	struct unix_edge *edge;
> +	LIST_HEAD(edge_stack);
> +
> +next_vertex:
> +	vertex->index = index;
> +	vertex->lowlink = index;
> +	index++;
> +
> +	vertex->on_stack = true;
> +	list_add(&vertex->scc_entry, &vertex_stack);
> +
> +	list_for_each_entry(edge, &vertex->edges, vertex_entry) {
> +		struct unix_vertex *next_vertex = edge->successor->vertex;
> +
> +		if (!next_vertex)
> +			continue;
> +
> +		if (next_vertex->index == UNIX_VERTEX_INDEX_UNVISITED) {
> +			list_add(&edge->stack_entry, &edge_stack);
> +
> +			vertex = next_vertex;
> +			goto next_vertex;
> +prev_vertex:
> +			next_vertex = vertex;
> +
> +			edge = list_first_entry(&edge_stack, typeof(*edge), stack_entry);
> +			list_del_init(&edge->stack_entry);
> +
> +			vertex = edge->predecessor->vertex;
> +
> +			vertex->lowlink = min(vertex->lowlink, next_vertex->lowlink);
> +		} else if (edge->successor->vertex->on_stack) {

It looks like you can replace ^^^^^^^^^^^^^^^^^^^^ with 'next_vertex'
and that would be more readable.

IMHO more importantly: this code is fairly untrivial, I think that a
significant amount of comments would help the review and the long term
maintenance - even if everything is crystal clear and obvious to you,
restating the obvious in a comment would help me ;)

Thanks,

Paolo

Powered by blists - more mailing lists