[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <5f13e49d7aa3fb7ce51a5bea51268882a90a32c1.camel@redhat.com>
Date: Tue, 27 Feb 2024 12:19:40 +0100
From: Paolo Abeni <pabeni@...hat.com>
To: Kuniyuki Iwashima <kuniyu@...zon.com>, "David S. Miller"
<davem@...emloft.net>, Eric Dumazet <edumazet@...gle.com>, Jakub Kicinski
<kuba@...nel.org>
Cc: Kuniyuki Iwashima <kuni1840@...il.com>, netdev@...r.kernel.org
Subject: Re: [PATCH v3 net-next 11/14] af_unix: Assign a unique index to SCC.
On Fri, 2024-02-23 at 13:40 -0800, Kuniyuki Iwashima wrote:
> The definition of the lowlink in Tarjan's algorithm is the
> smallest index of a vertex that is reachable with at most one
> back-edge in SCC. This is not useful for a cross-edge.
>
> If we start traversing from A in the following graph, the final
> lowlink of D is 3. The cross-edge here is one between D and C.
>
> A -> B -> D D = (4, 3) (index, lowlink)
> ^ | | C = (3, 1)
> | V | B = (2, 1)
> `--- C <--' A = (1, 1)
>
> This is because the lowlink of D is updated with the index of C.
>
> In the following patch, we detect a dead SCC by checking two
> conditions for each vertex.
>
> 1) vertex has no edge directed to another SCC (no bridge)
> 2) vertex's out_degree is the same as the refcount of its file
>
> If 1) is false, there is a receiver of all fds of the SCC and
> its ancestor SCC.
>
> To evaluate 1), we need to assign a unique index to each SCC and
> assign it to all vertices in the SCC.
>
> This patch changes the lowlink update logic for cross-edge so
> that in the example above, the lowlink of D is updated with the
> lowlink of C.
>
> A -> B -> D D = (4, 1) (index, lowlink)
> ^ | | C = (3, 1)
> | V | B = (2, 1)
> `--- C <--' A = (1, 1)
>
> Then, all vertices in the same SCC have the same lowlink, and we
> can quickly find the bridge connecting to different SCC if exists.
>
> However, it is no longer called lowlink, so we rename it to
> scc_index. (It's sometimes called lowpoint.)
>
> Also, we add a global variable to hold the last index used in DFS
> so that we do not reset the initial index in each DFS.
>
> This patch can be squashed to the SCC detection patch but is
> split deliberately for anyone wondering why lowlink is not used
> as used in the original Tarjan's algorithm and many reference
> implementations.
>
> Signed-off-by: Kuniyuki Iwashima <kuniyu@...zon.com>
> ---
> include/net/af_unix.h | 2 +-
> net/unix/garbage.c | 15 ++++++++-------
> 2 files changed, 9 insertions(+), 8 deletions(-)
>
> diff --git a/include/net/af_unix.h b/include/net/af_unix.h
> index ec040caaa4b5..696d997a5ac9 100644
> --- a/include/net/af_unix.h
> +++ b/include/net/af_unix.h
> @@ -36,7 +36,7 @@ struct unix_vertex {
> struct list_head scc_entry;
> unsigned long out_degree;
> unsigned long index;
> - unsigned long lowlink;
> + unsigned long scc_index;
> };
>
> struct unix_edge {
> diff --git a/net/unix/garbage.c b/net/unix/garbage.c
> index 1d9a0498dec5..0eb1610c96d7 100644
> --- a/net/unix/garbage.c
> +++ b/net/unix/garbage.c
> @@ -308,18 +308,18 @@ static bool unix_scc_cyclic(struct list_head *scc)
>
> static LIST_HEAD(unix_visited_vertices);
> static unsigned long unix_vertex_grouped_index = UNIX_VERTEX_INDEX_MARK2;
> +static unsigned long unix_vertex_last_index = UNIX_VERTEX_INDEX_START;
>
> static void __unix_walk_scc(struct unix_vertex *vertex)
> {
> - unsigned long index = UNIX_VERTEX_INDEX_START;
> LIST_HEAD(vertex_stack);
> struct unix_edge *edge;
> LIST_HEAD(edge_stack);
>
> next_vertex:
> - vertex->index = index;
> - vertex->lowlink = index;
> - index++;
> + vertex->index = unix_vertex_last_index;
> + vertex->scc_index = unix_vertex_last_index;
> + unix_vertex_last_index++;
>
> list_add(&vertex->scc_entry, &vertex_stack);
>
> @@ -342,13 +342,13 @@ static void __unix_walk_scc(struct unix_vertex *vertex)
>
> vertex = edge->predecessor->vertex;
>
> - vertex->lowlink = min(vertex->lowlink, next_vertex->lowlink);
> + vertex->scc_index = min(vertex->scc_index, next_vertex->scc_index);
> } else if (next_vertex->index != unix_vertex_grouped_index) {
> - vertex->lowlink = min(vertex->lowlink, next_vertex->index);
> + vertex->scc_index = min(vertex->scc_index, next_vertex->scc_index);
I guess the above will break when unix_vertex_last_index wraps around,
or am I low on coffee? (I guess there is not such a thing as enough
coffee to allow me reviewing this whole series at once ;)
Can we expect a wrap around in host with (surprisingly very) long
uptimes?
Thanks,
Paolo
Powered by blists - more mailing lists