Skip to contentSkip to conversation

af_unix: Unlink scc_entry in unix_del_edge().

PATCH Applied Kuniyuki Iwashima 4 participants 10 messages Aug 4 – Aug 6

Subsystems (3)
lore
Share & tools
lore

Kuniyuki Iwashima

author maintainer
#0 lore raw

PATCH 1/1 af_unix: Unlink scc_entry in unix_del_edge().

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.")
---
 net/unix/garbage.c | 1 +
 1 file changed, 1 insertion(+)
net/unix/garbage.c +1 -0
index 0783555e2526..9fcaaf55cba5 100644
@@ -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);
 	}
 }
 
Signature · 1 line
2.55.0.571.g244d577d93-goog
Reviewed-by on v1 1/1
#1 lore raw
Quoted 58 lines · 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.")
---
 net/unix/garbage.c | 1 +
 1 file changed, 1 insertion(+)
net/unix/garbage.c +1 -0
index 0783555e2526..9fcaaf55cba5 100644
@@ -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);
 	}
 }
 
Signature · 1 line
2.55.0.571.g244d577d93-goog
author maintainer
#2 lore raw
In reply to Kuniyuki Iwashima
Quoted 1 line

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

Sorry, this is for net.git.

Quoted 59 lines · 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.")
---
 net/unix/garbage.c | 1 +
 1 file changed, 1 insertion(+)
net/unix/garbage.c +1 -1
index 0783555e2526..9fcaaf55cba5 100644
@@ -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

maintainer
#3 lore raw
Quoted 3 lines · On Mon, 3 Aug 2026 17:46:37 -0700 Kuniyuki Iwashima wrote:
Quoted 1 line

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

Sorry, this is for net.git.

ack

maintainer
#4 lore raw
In reply to Kuniyuki Iwashima

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 <[email protected]>,

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.

Quoted 3 lines

af_unix: Unlink scc_entry in unix_del_edge().

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

[ ... ]

Quoted 2 lines

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?

Quoted 11 lines

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 -.
       ^--'         ^--'
net/unix/garbage.c +0 -0
index 0783555e25266..9fcaaf55cba5d 100644

net/unix/garbage.c static void unix_del_edge(struct scm_fp_list *fpl, struct unix_edge *edge) · line 191

Quoted 6 lines
net/unix/garbage.c +1 -0
@@ -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?

author maintainer
#5 lore raw
Quoted 137 lines · 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 <[email protected]>,

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.

Quoted 3 lines

af_unix: Unlink scc_entry in unix_del_edge().

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

[ ... ]

Quoted 2 lines

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?

Quoted 11 lines

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 -.
       ^--'         ^--'
net/unix/garbage.c +0 -0
index 0783555e25266..9fcaaf55cba5d 100644

net/unix/garbage.c static void unix_del_edge(struct scm_fp_list *fpl, struct unix_edge *edge) · line 191

Quoted 6 lines
net/unix/garbage.c +1 -0
@@ -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:

Quoted 8 lines
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 !

maintainer
#6 lore raw
Quoted 3 lines · On Thu, 6 Aug 2026 10:58:56 -0700 Kuniyuki Iwashima wrote:
Quoted 3 lines

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?"

👆️

author maintainer
#7 lore raw
Quoted 7 lines · Jakub Kicinski
Quoted 3 lines · On Thu, 6 Aug 2026 10:58:56 -0700 Kuniyuki Iwashima wrote:
Quoted 3 lines

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.

maintainer
#8 lore raw
Quoted 10 lines · On Thu, 6 Aug 2026 11:45:19 -0700 Kuniyuki Iwashima wrote:
Quoted 7 lines · Jakub Kicinski
Quoted 3 lines · On Thu, 6 Aug 2026 10:58:56 -0700 Kuniyuki Iwashima wrote:
Quoted 3 lines

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 :)

#9 lore raw
In reply to Kuniyuki Iwashima
This patch was applied to netdev/net.git (main) by Jakub Kicinski <[email protected]>:

Hello:

This patch was applied to netdev/net.git (main)
by Jakub Kicinski <[email protected]>:

Quoted 10 lines · 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!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html