From: Kuniyuki Iwashima <kuniyu@amazon.com>
To: <pabeni@redhat.com>
Cc: <davem@davemloft.net>, <edumazet@google.com>, <kuba@kernel.org>,
<kuni1840@gmail.com>, <kuniyu@amazon.com>,
<netdev@vger.kernel.org>
Subject: Re: [PATCH v3 net-next 11/14] af_unix: Assign a unique index to SCC.
Date: Tue, 27 Feb 2024 19:05:07 -0800 [thread overview]
Message-ID: <20240228030508.31297-1-kuniyu@amazon.com> (raw)
In-Reply-To: <5f13e49d7aa3fb7ce51a5bea51268882a90a32c1.camel@redhat.com>
From: Paolo Abeni <pabeni@redhat.com>
Date: Tue, 27 Feb 2024 12:19:40 +0100
> 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@amazon.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?
Then, the number of inflight AF_UNIX sockets is at least 2^64 - 1.
After this series, struct unix_sock is 1024 bytes, so... the host
would have roughly
2^10 * 2^64 == 2^74 bytes == 2^34 TBi == 17179869184 TBi
memory!
So, we need not expect a wrap around :)
next prev parent reply other threads:[~2024-02-28 3:05 UTC|newest]
Thread overview: 33+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-02-23 21:39 [PATCH v3 net-next 00/14] af_unix: Rework GC Kuniyuki Iwashima
2024-02-23 21:39 ` [PATCH v3 net-next 01/14] af_unix: Allocate struct unix_vertex for each inflight AF_UNIX fd Kuniyuki Iwashima
2024-02-23 21:39 ` [PATCH v3 net-next 02/14] af_unix: Allocate struct unix_edge " Kuniyuki Iwashima
2024-02-23 21:39 ` [PATCH v3 net-next 03/14] af_unix: Link struct unix_edge when queuing skb Kuniyuki Iwashima
2024-02-23 21:39 ` [PATCH v3 net-next 04/14] af_unix: Bulk update unix_tot_inflight/unix_inflight " Kuniyuki Iwashima
2024-02-27 10:47 ` Paolo Abeni
2024-02-28 2:34 ` Kuniyuki Iwashima
2024-02-28 7:46 ` Paolo Abeni
2024-02-23 21:39 ` [PATCH v3 net-next 05/14] af_unix: Detect Strongly Connected Components Kuniyuki Iwashima
2024-02-25 0:34 ` Jakub Kicinski
2024-02-26 19:07 ` Kuniyuki Iwashima
2024-02-27 11:02 ` Paolo Abeni
2024-02-28 2:49 ` Kuniyuki Iwashima
2024-02-23 21:39 ` [PATCH v3 net-next 06/14] af_unix: Save listener for embryo socket Kuniyuki Iwashima
2024-02-23 21:39 ` [PATCH v3 net-next 07/14] af_unix: Fix up unix_edge.successor " Kuniyuki Iwashima
2024-02-23 21:39 ` [PATCH v3 net-next 08/14] af_unix: Save O(n) setup of Tarjan's algo Kuniyuki Iwashima
2024-02-23 21:39 ` [PATCH v3 net-next 09/14] af_unix: Skip GC if no cycle exists Kuniyuki Iwashima
2024-02-23 21:39 ` [PATCH v3 net-next 10/14] af_unix: Avoid Tarjan's algorithm if unnecessary Kuniyuki Iwashima
2024-02-23 21:40 ` [PATCH v3 net-next 11/14] af_unix: Assign a unique index to SCC Kuniyuki Iwashima
2024-02-27 11:19 ` Paolo Abeni
2024-02-28 3:05 ` Kuniyuki Iwashima [this message]
2024-02-28 7:49 ` Paolo Abeni
2024-02-28 16:25 ` Kuniyuki Iwashima
2024-02-28 17:51 ` Paolo Abeni
2024-02-23 21:40 ` [PATCH v3 net-next 12/14] af_unix: Detect dead SCC Kuniyuki Iwashima
2024-02-27 11:25 ` Paolo Abeni
2024-02-28 3:14 ` Kuniyuki Iwashima
2024-02-23 21:40 ` [PATCH v3 net-next 13/14] af_unix: Replace garbage collection algorithm Kuniyuki Iwashima
2024-02-27 11:36 ` Paolo Abeni
2024-02-28 3:32 ` Kuniyuki Iwashima
2024-02-28 8:08 ` Paolo Abeni
2024-02-28 16:29 ` Kuniyuki Iwashima
2024-02-23 21:40 ` [PATCH v3 net-next 14/14] selftest: af_unix: Test GC for SCM_RIGHTS Kuniyuki Iwashima
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20240228030508.31297-1-kuniyu@amazon.com \
--to=kuniyu@amazon.com \
--cc=davem@davemloft.net \
--cc=edumazet@google.com \
--cc=kuba@kernel.org \
--cc=kuni1840@gmail.com \
--cc=netdev@vger.kernel.org \
--cc=pabeni@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).