af_unix: Unlink scc_entry in unix_del_edge().
Subsystems (3)
Kuniyuki Iwashima
maintainerPATCH 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().
--- net/unix/garbage.c | 1 + 1 file changed, 1 insertion(+)
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); } }
Signature · 1 line
2.55.0.571.g244d577d93-goog
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 BAt 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 byskb_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 notThis 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'sscc_entry.Let's unlink
scc_entrybefore freeing the vertex inunix_del_edge().Fixes 4090fa373f0e ("af_unix: Replace garbage collection algorithm.")Reported-by Kyle Zeng <[email protected]>Signed-off-by Kuniyuki Iwashima <[email protected]>--- net/unix/garbage.c | 1 + 1 file changed, 1 insertion(+)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); } }Signature · 1 line
2.55.0.571.g244d577d93-goog
Kuniyuki Iwashima
maintainerQuoted 1 line
[PATCH v1 net-next]
af_unix: Unlinkscc_entryinunix_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 BAt 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 byskb_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 notThis 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'sscc_entry.Let's unlink
scc_entrybefore freeing the vertex inunix_del_edge().Fixes 4090fa373f0e ("af_unix: Replace garbage collection algorithm.")Reported-by Kyle Zeng <[email protected]>Signed-off-by Kuniyuki Iwashima <[email protected]>--- net/unix/garbage.c | 1 + 1 file changed, 1 insertion(+)net/unix/garbage.c +1
-1@@ -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
Jakub Kicinski
maintainerQuoted 3 lines · On Mon, 3 Aug 2026 17:46:37 -0700 Kuniyuki Iwashima wrote:
Quoted 1 line
[PATCH v1 net-next]
af_unix: Unlinkscc_entryinunix_del_edge().Sorry, this is for net.git.
ack
Jakub Kicinski
maintainerThis 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]>,
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: Unlinkscc_entryinunix_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'sscc_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
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?
Kuniyuki Iwashima
maintainerQuoted 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: Unlinkscc_entryinunix_del_edge().A vertex whose
out_degreedrops to zero is moved tofpl->verticesand later freed byunix_free_vertices(), but it stayed linked in the circularscc_entrylist built by__unix_walk_scc(). This adds alist_del(&vertex->scc_entry)so a followingunix_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: Unlinkscc_entryinunix_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'sscc_entry.[Severity: Low]
Could the changelog name what "iterates over A" means in practice? A's vertex has already been kfree()d byunix_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)plusclose()onAF_UNIXsockets, would it help stable triage to say explicitly that the pre-patch behaviour is a use-after-free on the freedunix_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
-0net/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 unbalancesunix_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 withfpl->dead== true,unix_del_edge()deliberately skipsunix_update_graph(), so B survives as a self-linked singleton ring back onunix_unvisited_verticesand the state staysUNIX_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_statetoUNIX_GRAPH_NOT_CYCLICwhile 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_UNIXfd 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 stayUNIX_GRAPH_CYCLIC, sounix_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 (
58b47c713711ande29c7a4cec86), 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 !
Jakub Kicinski
maintainerQuoted 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?"
👆️
Kuniyuki Iwashima
maintainerQuoted 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.
Jakub Kicinski
maintainerQuoted 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 :)
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