af_unix: Avoid Tarjan's algorithm if unnecessary.
authorKuniyuki Iwashima <kuniyu@amazon.com>
Mon, 25 Mar 2024 20:24:21 +0000 (13:24 -0700)
committerJakub Kicinski <kuba@kernel.org>
Fri, 29 Mar 2024 15:28:29 +0000 (08:28 -0700)
commitad081928a8b0f57f269df999a28087fce6f2b6ce
treea4e69083a76da9a10a6a2a0de1a13c19f773911c
parent77e5593aebba823bcbcf2c4b58b07efcd63933b8
af_unix: Avoid Tarjan's algorithm if unnecessary.

Once a cyclic reference is formed, we need to run GC to check if
there is dead SCC.

However, we do not need to run Tarjan's algorithm if we know that
the shape of the inflight graph has not been changed.

If an edge is added/updated/deleted and the edge's successor is
inflight, we set false to unix_graph_grouped, which means we need
to re-classify SCC.

Once we finalise SCC, we set true to unix_graph_grouped.

While unix_graph_grouped is true, we can iterate the grouped
SCC using vertex->scc_entry in unix_walk_scc_fast().

list_add() and list_for_each_entry_reverse() uses seem weird, but
they are to keep the vertex order consistent and make writing test
easier.

Signed-off-by: Kuniyuki Iwashima <kuniyu@amazon.com>
Acked-by: Paolo Abeni <pabeni@redhat.com>
Link: https://lore.kernel.org/r/20240325202425.60930-12-kuniyu@amazon.com
Signed-off-by: Jakub Kicinski <kuba@kernel.org>
net/unix/garbage.c