af_unix: Iterate all vertices by DFS.
authorKuniyuki Iwashima <kuniyu@amazon.com>
Mon, 25 Mar 2024 20:24:15 +0000 (13:24 -0700)
committerJakub Kicinski <kuba@kernel.org>
Fri, 29 Mar 2024 15:27:59 +0000 (08:27 -0700)
commit6ba76fd2848e107594ea4f03b737230f74bc23ea
treeeea4636063f3c09114f1df07b22f74171b41c369
parent22c3c0c52d32f41cc38cd936ea0c93f22ced3315
af_unix: Iterate all vertices by DFS.

The new GC will use a depth first search graph algorithm to find
cyclic references.  The algorithm visits every vertex exactly once.

Here, we implement the DFS part without recursion so that no one
can abuse it.

unix_walk_scc() marks every vertex unvisited by initialising index
as UNIX_VERTEX_INDEX_UNVISITED and iterates inflight vertices in
unix_unvisited_vertices and call __unix_walk_scc() to start DFS from
an arbitrary vertex.

__unix_walk_scc() iterates all edges starting from the vertex and
explores the neighbour vertices with DFS using edge_stack.

After visiting all neighbours, __unix_walk_scc() moves the visited
vertex to unix_visited_vertices so that unix_walk_scc() will not
restart DFS from the visited vertex.

Signed-off-by: Kuniyuki Iwashima <kuniyu@amazon.com>
Acked-by: Paolo Abeni <pabeni@redhat.com>
Link: https://lore.kernel.org/r/20240325202425.60930-6-kuniyu@amazon.com
Signed-off-by: Jakub Kicinski <kuba@kernel.org>
include/net/af_unix.h
net/unix/garbage.c