| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <961535955d1988b7f8ad06f0cb93a200f4b97fb6.camel@redhat.com>
Date: Wed, 28 Feb 2024 18:51:41 +0100
From: Paolo Abeni <pabeni@...hat.com>
To: Kuniyuki Iwashima <kuniyu@...zon.com>
Cc: davem@...emloft.net, edumazet@...gle.com, kuba@...nel.org,
kuni1840@...il.com, netdev@...r.kernel.org
Subject: Re: [PATCH v3 net-next 11/14] af_unix: Assign a unique index to SCC.
On Wed, 2024-02-28 at 08:25 -0800, Kuniyuki Iwashima wrote:
> From: Paolo Abeni <pabeni@...hat.com>
> Date: Wed, 28 Feb 2024 08:49:46 +0100
> > On Tue, 2024-02-27 at 19:05 -0800, Kuniyuki Iwashima wrote:
> > > From: Paolo Abeni <pabeni@...hat.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@...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?
> > >
> > > Then, the number of inflight AF_UNIX sockets is at least 2^64 - 1.
> >
> > Isn't "unix_vertex_last_index" value preserved across consecutive cg
> > run? I though we could reach wrap around after a lot of gc runs...
>
> It's preserved across consecutive DFS in a single gc run, but
> unix_walk_scc() always reset it. So, if it's wrapped, there
> would be too many sockets.
Ah, I missed that point. No wrap-around problem then!
> I used unix_vertex_last_index elsewhere in the initial draft,
> but now local variable could be better here.
You could bundle the index, hitlist, etc. in a single struct (gs_state
or whatever) and pass around a single argument, if that helps.
Cheers,
Paolo
Powered by blists - more mailing lists