Re: [PATCH v1 net-next] af_unix: Unlink scc_entry in unix_del_edge().

[Jakub Kicinski <kuba@kernel.org>]

This is an AI-generated review of your patch. The human sending this
email says "I meant to send this yesterday, damn. This is completely
separate right?"
---
af_unix: Unlink scc_entry in unix_del_edge().

A vertex whose out_degree drops to zero is moved to fpl->vertices and later
freed by unix_free_vertices(), but it stayed linked in the circular
scc_entry list built by __unix_walk_scc().  This adds a
list_del(&vertex->scc_entry) so a following unix_walk_scc_fast() no longer
walks into the freed vertex.  Reported-by: Kyle Zeng <kylebot@openai.com>,
Fixes: 4090fa373f0e ("af_unix: Replace garbage collection algorithm.").

Two questions below, one about the changelog wording and one about the
cyclic SCC accounting that the described remnant vertex feeds into.

> af_unix: Unlink scc_entry in unix_del_edge().
>
> Kyle Zeng reported that GC could free a dead SCC partially.
[ ... ]
> However, X's SCC forces the next GC to call unix_walk_scc_fast(),
> and it iterates over A through B's scc_entry.

[Severity: Low]
Could the changelog name what "iterates over A" means in practice?  A's
vertex has already been kfree()d by unix_free_vertices() at that point, so
the fast walk reads and writes freed memory:

net/unix/garbage.c:unix_scc_dead() {
	list_for_each_entry_reverse(vertex, scc, scc_entry) {
		/* Don't restart DFS from this vertex. */
		list_move_tail(&vertex->entry, &unix_visited_vertices);
	...
}

net/unix/garbage.c:unix_collect_skb() {
	list_for_each_entry_reverse(vertex, scc, scc_entry) {
		...
		edge = list_first_entry(&vertex->edges, typeof(*edge), vertex_entry);
	...
}

The summary says "GC could free a dead SCC partially", and the words
use-after-free or list corruption do not appear anywhere in the message.
Since the trigger is ordinary unprivileged sendmsg(SCM_RIGHTS) plus close()
on AF_UNIX sockets, would it help stable triage to say explicitly that the
pre-patch behaviour is a use-after-free on the freed unix_vertex?

> This itself is not a problem since the next GC run will judge
> B as dead as well and free it finally.
>
>        X -.   A <.> B -.
>        ^--'         ^--'

> diff --git a/net/unix/garbage.c b/net/unix/garbage.c
> index 0783555e25266..9fcaaf55cba5d 100644
> --- a/net/unix/garbage.c
> +++ b/net/unix/garbage.c
> @@ -186,6 +186,7 @@ static void unix_del_edge(struct scm_fp_list *fpl, struct unix_edge *edge)
>  	if (!vertex->out_degree) {
>  		edge->predecessor->vertex = NULL;
>  		list_move_tail(&vertex->entry, &fpl->vertices);
> +		list_del(&vertex->scc_entry);
>  	}
>  }

[Severity: High]
This isn't a bug introduced by this patch, but the surviving remnant vertex
that the changelog accepts as harmless looks like it unbalances
unix_graph_cyclic_sccs.

__unix_walk_scc() only counts SCCs that are still alive:

net/unix/garbage.c:__unix_walk_scc() {
	if (unix_scc_dead(&scc, false)) {
		unix_collect_skb(&scc, hitlist);
	} else {
		...
		if (unix_scc_cyclic(&scc))
			cyclic_sccs++;
	}
}

so the {A, B} SCC that the full walk judges dead contributes 0.  But the
fast walk decrements once for every ring it finds dead:

net/unix/garbage.c:unix_walk_scc_fast() {
	vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry);
	list_add(&scc, &vertex->scc_entry);

	if (unix_scc_dead(&scc, true)) {
		cyclic_sccs--;
		unix_collect_skb(&scc, hitlist);
	}
	...
	WRITE_ONCE(unix_graph_cyclic_sccs, cyclic_sccs);
	WRITE_ONCE(unix_graph_state,
		   cyclic_sccs ? UNIX_GRAPH_CYCLIC : UNIX_GRAPH_NOT_CYCLIC);
}

Using the exact scenario from the changelog, with X's live cyclic SCC plus
{A, B}: the full walk collects {A, B} and stores unix_graph_cyclic_sccs = 1
for X.  Because the purge runs with fpl->dead == true, unix_del_edge()
deliberately skips unix_update_graph(), so B survives as a self-linked
singleton ring back on unix_unvisited_vertices and the state stays
UNIX_GRAPH_CYCLIC.

The next GC then takes the fast walk, finds B's singleton ring dead and does
cyclic_sccs-- on a group that was never counted, taking the counter 1 -> 0.

Can that flip unix_graph_state to UNIX_GRAPH_NOT_CYCLIC while X's cyclic SCC
is still present?  After that, both entry points bail out:

net/unix/garbage.c:unix_gc() {
	if (unix_graph_state == UNIX_GRAPH_NOT_CYCLIC) {
		spin_unlock(&unix_gc_lock);
		goto skip_gc;
	}
}

net/unix/garbage.c:unix_schedule_gc() {
	if (READ_ONCE(unix_graph_state) == UNIX_GRAPH_NOT_CYCLIC)
		return;
}

Closing X's fd does not release the socket while it is inflight, so nothing
calls unix_del_edges()/unix_update_graph() to re-arm the state.  Does that
leak X's struct sock, its skb and the pinned struct file until some
unrelated sender happens to pass an AF_UNIX fd to an inflight receiver?

And if two such remnant rings are found in one fast walk while the counter
is 1, does the second cyclic_sccs-- wrap the unsigned long to ULONG_MAX?
The state would then stay UNIX_GRAPH_CYCLIC, so unix_walk_scc() is never
selected again to recompute the counter, and this makes every fd-passing
send take the synchronous path:

net/unix/garbage.c:unix_schedule_gc() {
	if (user && READ_ONCE(unix_graph_cyclic_sccs))
		flush_work(&unix_gc_work);
}

The counter and the unconditional decrement predate this patch (58b47c713711
and e29c7a4cec86), so this is not a regression from the one-line addition,
but should the accounting also be corrected for the remnant case?