[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <0bddd6e22f91e0d629b41a84c9e2eb56e3260176.camel@redhat.com>
Date: Tue, 05 Mar 2024 09:44:00 +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 v4 net-next 12/15] af_unix: Assign a unique index to SCC.
On Thu, 2024-02-29 at 18:22 -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.)
I'm wondering if there is any reference to this variation of Tarjan's
algorithm you can point, to help understanding, future memory,
reviewing.
Thanks!
Paolo
Powered by blists - more mailing lists