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

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

[Kuniyuki Iwashima]

Kyle Zeng reported that GC could free a dead SCC partially.

The scenario is as follows:

   1) Create two SCCs:

       X -.   A <-> B
       ^--'

   2) Run the following concurrently:

      2-1) send() sk-B to sk-B from sk-X
      2-2) close() both A and B

At 2-1), there is a small window where unix_add_edges()
publishes a new edge (B <-> B) to GC but its skb is not queued
by skb_queue_tail().

If 2-2) completes before skb_queue_tail() and GC is triggered,
it judges A <-> B as dead, but B is not freed because GC cannot
collect the not-yet-queued skb holding the B <-> B edge.

       X -.   A <-> B -. This edge is visible
       ^--'         ^..'  but skb is not

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 -.
       ^--'         ^--'

However, X's SCC forces the next GC to call unix_walk_scc_fast(),
and it iterates over A through B's scc_entry.

Let's unlink scc_entry before freeing the vertex in unix_del_edge().

Fixes: 4090fa373f0e ("af_unix: Replace garbage collection algorithm.")
Reported-by: Kyle Zeng <kylebot@openai.com>
Signed-off-by: Kuniyuki Iwashima <kuniyu@google.com>
---
 net/unix/garbage.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/net/unix/garbage.c b/net/unix/garbage.c
index 0783555e2526..9fcaaf55cba5 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);
 	}
 }
 
-- 
2.55.0.571.g244d577d93-goog

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

[Kyle Zeng]

On Tue, Aug 04, 2026 at 12:21:54AM +0000, Kuniyuki Iwashima wrote:
> Kyle Zeng reported that GC could free a dead SCC partially.
> 
> The scenario is as follows:
> 
>    1) Create two SCCs:
> 
>        X -.   A <-> B
>        ^--'
> 
>    2) Run the following concurrently:
> 
>       2-1) send() sk-B to sk-B from sk-X
>       2-2) close() both A and B
> 
> At 2-1), there is a small window where unix_add_edges()
> publishes a new edge (B <-> B) to GC but its skb is not queued
> by skb_queue_tail().
> 
> If 2-2) completes before skb_queue_tail() and GC is triggered,
> it judges A <-> B as dead, but B is not freed because GC cannot
> collect the not-yet-queued skb holding the B <-> B edge.
> 
>        X -.   A <-> B -. This edge is visible
>        ^--'         ^..'  but skb is not
> 
> 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 -.
>        ^--'         ^--'
> 
> However, X's SCC forces the next GC to call unix_walk_scc_fast(),
> and it iterates over A through B's scc_entry.
> 
> Let's unlink scc_entry before freeing the vertex in unix_del_edge().
> 
> Fixes: 4090fa373f0e ("af_unix: Replace garbage collection algorithm.")
> Reported-by: Kyle Zeng <kylebot@openai.com>
> Signed-off-by: Kuniyuki Iwashima <kuniyu@google.com>
> ---
>  net/unix/garbage.c | 1 +
>  1 file changed, 1 insertion(+)
> 
> diff --git a/net/unix/garbage.c b/net/unix/garbage.c
> index 0783555e2526..9fcaaf55cba5 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);
>  	}
>  }
>  
> -- 
> 2.55.0.571.g244d577d93-goog
> 

Reviewed-by: Kyle Zeng <kylebot@openai.com>

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

[Kuniyuki Iwashima]

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

Sorry, this is for net.git.


On Mon, Aug 3, 2026 at 5:21 PM Kuniyuki Iwashima <kuniyu@google.com> wrote:
>
> Kyle Zeng reported that GC could free a dead SCC partially.
>
> The scenario is as follows:
>
>    1) Create two SCCs:
>
>        X -.   A <-> B
>        ^--'
>
>    2) Run the following concurrently:
>
>       2-1) send() sk-B to sk-B from sk-X
>       2-2) close() both A and B
>
> At 2-1), there is a small window where unix_add_edges()
> publishes a new edge (B <-> B) to GC but its skb is not queued
> by skb_queue_tail().
>
> If 2-2) completes before skb_queue_tail() and GC is triggered,
> it judges A <-> B as dead, but B is not freed because GC cannot
> collect the not-yet-queued skb holding the B <-> B edge.
>
>        X -.   A <-> B -. This edge is visible
>        ^--'         ^..'  but skb is not
>
> 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 -.
>        ^--'         ^--'
>
> However, X's SCC forces the next GC to call unix_walk_scc_fast(),
> and it iterates over A through B's scc_entry.
>
> Let's unlink scc_entry before freeing the vertex in unix_del_edge().
>
> Fixes: 4090fa373f0e ("af_unix: Replace garbage collection algorithm.")
> Reported-by: Kyle Zeng <kylebot@openai.com>
> Signed-off-by: Kuniyuki Iwashima <kuniyu@google.com>
> ---
>  net/unix/garbage.c | 1 +
>  1 file changed, 1 insertion(+)
>
> diff --git a/net/unix/garbage.c b/net/unix/garbage.c
> index 0783555e2526..9fcaaf55cba5 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);
>         }
>  }
>
> --
> 2.55.0.571.g244d577d93-goog
>

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

[Jakub Kicinski]

On Mon, 3 Aug 2026 17:46:37 -0700 Kuniyuki Iwashima wrote:
> > [PATCH v1 net-next] af_unix: Unlink scc_entry in unix_del_edge().  
> 
> Sorry, this is for net.git.

ack

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

[Jakub Kicinski]

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?

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

[Kuniyuki Iwashima]

On Thu, Aug 6, 2026 at 10:29 AM Jakub Kicinski <kuba@kernel.org> wrote:
>
> 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?

Good point, looks like Claude is now better than Gemini :)

I'll change unix_walk_scc_fast() like below.

if (unix_scc_dead(&scc, true)) {
        unix_collect_skb(&scc, hitlist);
        if (list_empty(&scc))
                cyclic_sccs--;
}

Thanks !

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

[Jakub Kicinski]

On Thu, 6 Aug 2026 10:58:56 -0700 Kuniyuki Iwashima wrote:
> > 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?"

👆️

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

[Kuniyuki Iwashima]

On Thu, Aug 6, 2026 at 11:36 AM Jakub Kicinski <kuba@kernel.org> wrote:
>
> On Thu, 6 Aug 2026 10:58:56 -0700 Kuniyuki Iwashima wrote:
> > > 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?"
>
> 👆️

Ah missed this, yes, it's a separate one.

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

[Jakub Kicinski]

On Thu, 6 Aug 2026 11:45:19 -0700 Kuniyuki Iwashima wrote:
> On Thu, Aug 6, 2026 at 11:36 AM Jakub Kicinski <kuba@kernel.org> wrote:
> >
> > On Thu, 6 Aug 2026 10:58:56 -0700 Kuniyuki Iwashima wrote:  
> > > > 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?"  
> >
> > 👆️  
> 
> Ah missed this, yes, it's a separate one.

Thanks :)

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

[patchwork-bot+netdevbpf]

Hello:

This patch was applied to netdev/net.git (main)
by Jakub Kicinski <kuba@kernel.org>:

On Tue,  4 Aug 2026 00:21:54 +0000 you wrote:
> Kyle Zeng reported that GC could free a dead SCC partially.
> 
> The scenario is as follows:
> 
>    1) Create two SCCs:
> 
>        X -.   A <-> B
>        ^--'
> 
> [...]

Here is the summary with links:
  - [v1,net-next] af_unix: Unlink scc_entry in unix_del_edge().
    https://git.kernel.org/netdev/net/c/594d90519502

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html