netdev - Re: [PATCH v4 net-next 05/15] af_unix: Iterate all vertices by DFS.

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <25a99a706459304e9661881d413a342558a23372.camel@redhat.com>
Date: Tue, 05 Mar 2024 09:53:17 +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 v4 net-next 05/15] af_unix: Iterate all vertices by DFS.

On Thu, 2024-02-29 at 18:22 -0800, Kuniyuki Iwashima wrote:
> 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 its 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, 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@...zon.com>
> ---
>  include/net/af_unix.h |  2 ++
>  net/unix/garbage.c    | 74 +++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 76 insertions(+)
> 
> diff --git a/include/net/af_unix.h b/include/net/af_unix.h
> index f31ad1166346..970a91da2239 100644
> --- a/include/net/af_unix.h
> +++ b/include/net/af_unix.h
> @@ -33,12 +33,14 @@ struct unix_vertex {
>  	struct list_head edges;
>  	struct list_head entry;
>  	unsigned long out_degree;
> +	unsigned long index;
>  };
>  
>  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 84c8ea524a98..8b16ab9e240e 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;
> @@ -241,6 +246,73 @@ 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;
> +	struct unix_edge *edge;
> +	LIST_HEAD(edge_stack);
> +
> +next_vertex:
> +	vertex->index = index;
> +	index++;
> +
> +	/* Explore neighbour vertices (receivers of the current vertex's fd). */
> +	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) {
> +			/* Iterative deepening depth first search
> +			 *
> +			 *   1. Push a forward edge to edge_stack and set
> +			 *      the successor to vertex for the next iteration.
> +			 */
> +			list_add(&edge->stack_entry, &edge_stack);
> +
> +			vertex = next_vertex;
> +			goto next_vertex;
> +
> +			/*   2. Pop the edge directed to the current vertex
> +			 *      and restore the ancestor for backtracking.
> +			 */
> +prev_vertex:
> +			edge = list_first_entry(&edge_stack, typeof(*edge), stack_entry);
> +			list_del_init(&edge->stack_entry);
> +
> +			vertex = edge->predecessor->vertex;
> +		}
> +	}
> +
> +	/* Don't restart DFS from this vertex in unix_walk_scc(). */
> +	list_move_tail(&vertex->entry, &unix_visited_vertices);
> +
> +	/* Need backtracking ? */
> +	if (!list_empty(&edge_stack))
> +		goto prev_vertex;
> +}
> +
> +static void unix_walk_scc(void)
> +{
> +	struct unix_vertex *vertex;
> +
> +	list_for_each_entry(vertex, &unix_unvisited_vertices, entry)
> +		vertex->index = UNIX_VERTEX_INDEX_UNVISITED;
> +
> +	/* Visit every vertex exactly once.
> +	 * __unix_walk_scc() moves visited vertices to unix_visited_vertices.
> +	 */
> +	while (!list_empty(&unix_unvisited_vertices)) {
> +		vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry);
> +		__unix_walk_scc(vertex);

If I read correctly this is the single loop that could use the CPU for
a possibly long time. I'm wondering if adding a cond_resched_lock()
here (and possibly move the gc to a specific thread instead of a
workqueue) would make sense.

It could avoid possibly very long starvation of the system wq and the
used CPU.

Cheers,

Paolo