| 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: <ae074ab772566932d491a43fa34e0625ef855f2d.camel@redhat.com>
Date: Thu, 07 Mar 2024 10:08:16 +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 v4 net-next 05/15] af_unix: Iterate all vertices by DFS.
On Wed, 2024-03-06 at 12:14 -0800, Kuniyuki Iwashima wrote:
> From: Paolo Abeni <pabeni@...hat.com>
> Date: Tue, 05 Mar 2024 09:53:17 +0100
> > On Thu, 2024-02-29 at 18:22 -0800, Kuniyuki Iwashima wrote:
> > > The new GC will use a depth first search graph algorithm to find
> > > cyclic references. The algorithm visits every vertex exactly once.
> > >
> > > Here, we implement its DFS part without recursion so that no one
> > > can abuse it.
> > >
> > > unix_walk_scc() marks every vertex unvisited by initialising index
> > > as UNIX_VERTEX_INDEX_UNVISITED, iterates inflight vertices in
> > > unix_unvisited_vertices, and call __unix_walk_scc() to start DFS
> > > from an arbitrary vertex.
> > >
> > > __unix_walk_scc() iterates all edges starting from the vertex and
> > > explores the neighbour vertices with DFS using edge_stack.
> > >
> > > After visiting all neighbours, __unix_walk_scc() moves the visited
> > > vertex to unix_visited_vertices so that unix_walk_scc() will not
> > > restart DFS from the visited vertex.
> > >
> > > Signed-off-by: Kuniyuki Iwashima <kuniyu@...zon.com>
> > > ---
> > > include/net/af_unix.h | 2 ++
> > > net/unix/garbage.c | 74 +++++++++++++++++++++++++++++++++++++++++++
> > > 2 files changed, 76 insertions(+)
> > >
> > > diff --git a/include/net/af_unix.h b/include/net/af_unix.h
> > > index f31ad1166346..970a91da2239 100644
> > > --- a/include/net/af_unix.h
> > > +++ b/include/net/af_unix.h
> > > @@ -33,12 +33,14 @@ struct unix_vertex {
> > > struct list_head edges;
> > > struct list_head entry;
> > > unsigned long out_degree;
> > > + unsigned long index;
> > > };
> > >
> > > struct unix_edge {
> > > struct unix_sock *predecessor;
> > > struct unix_sock *successor;
> > > struct list_head vertex_entry;
> > > + struct list_head stack_entry;
> > > };
> > >
> > > struct sock *unix_peer_get(struct sock *sk);
> > > diff --git a/net/unix/garbage.c b/net/unix/garbage.c
> > > index 84c8ea524a98..8b16ab9e240e 100644
> > > --- a/net/unix/garbage.c
> > > +++ b/net/unix/garbage.c
> > > @@ -103,6 +103,11 @@ struct unix_sock *unix_get_socket(struct file *filp)
> > >
> > > static LIST_HEAD(unix_unvisited_vertices);
> > >
> > > +enum unix_vertex_index {
> > > + UNIX_VERTEX_INDEX_UNVISITED,
> > > + UNIX_VERTEX_INDEX_START,
> > > +};
> > > +
> > > static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge)
> > > {
> > > struct unix_vertex *vertex = edge->predecessor->vertex;
> > > @@ -241,6 +246,73 @@ void unix_destroy_fpl(struct scm_fp_list *fpl)
> > > unix_free_vertices(fpl);
> > > }
> > >
> > > +static LIST_HEAD(unix_visited_vertices);
> > > +
> > > +static void __unix_walk_scc(struct unix_vertex *vertex)
> > > +{
> > > + unsigned long index = UNIX_VERTEX_INDEX_START;
> > > + struct unix_edge *edge;
> > > + LIST_HEAD(edge_stack);
> > > +
> > > +next_vertex:
> > > + vertex->index = index;
> > > + index++;
> > > +
> > > + /* Explore neighbour vertices (receivers of the current vertex's fd). */
> > > + list_for_each_entry(edge, &vertex->edges, vertex_entry) {
> > > + struct unix_vertex *next_vertex = edge->successor->vertex;
> > > +
> > > + if (!next_vertex)
> > > + continue;
> > > +
> > > + if (next_vertex->index == UNIX_VERTEX_INDEX_UNVISITED) {
> > > + /* Iterative deepening depth first search
> > > + *
> > > + * 1. Push a forward edge to edge_stack and set
> > > + * the successor to vertex for the next iteration.
> > > + */
> > > + list_add(&edge->stack_entry, &edge_stack);
> > > +
> > > + vertex = next_vertex;
> > > + goto next_vertex;
> > > +
> > > + /* 2. Pop the edge directed to the current vertex
> > > + * and restore the ancestor for backtracking.
> > > + */
> > > +prev_vertex:
> > > + edge = list_first_entry(&edge_stack, typeof(*edge), stack_entry);
> > > + list_del_init(&edge->stack_entry);
> > > +
> > > + vertex = edge->predecessor->vertex;
> > > + }
> > > + }
> > > +
> > > + /* Don't restart DFS from this vertex in unix_walk_scc(). */
> > > + list_move_tail(&vertex->entry, &unix_visited_vertices);
> > > +
> > > + /* Need backtracking ? */
> > > + if (!list_empty(&edge_stack))
> > > + goto prev_vertex;
> > > +}
> > > +
> > > +static void unix_walk_scc(void)
> > > +{
> > > + struct unix_vertex *vertex;
> > > +
> > > + list_for_each_entry(vertex, &unix_unvisited_vertices, entry)
> > > + vertex->index = UNIX_VERTEX_INDEX_UNVISITED;
> > > +
> > > + /* Visit every vertex exactly once.
> > > + * __unix_walk_scc() moves visited vertices to unix_visited_vertices.
> > > + */
> > > + while (!list_empty(&unix_unvisited_vertices)) {
> > > + vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry);
> > > + __unix_walk_scc(vertex);
> >
> > If I read correctly this is the single loop that could use the CPU for
> > a possibly long time. I'm wondering if adding a cond_resched_lock()
> > here (and possibly move the gc to a specific thread instead of a
> > workqueue) would make sense.
> >
> > It could avoid possibly very long starvation of the system wq and the
> > used CPU.
>
> TIL cond_resched_lock() :)
>
> The loop is executed only when we add/del/update edges whose successor
> is alredy inflight, and the loop takes O(|Vertex| + |Edges|).
>
> If the loop takes so long, there would be too many inflight skbs, but
> the current GC does not care such a situation.
Yes, the whole idea was about a possible additional improvement WRT the
current status.
> The suggestion still makes sense, and then we could use mutex instead of
> spinlock after kthread conversion.
>
> Given the series has already 15 patches, I can add cond_resched_lock()
> only in the next version and include the conversion in the follow-up
> patches or include both changes as followup or do the conversion as prep.
>
> What's the preferred option ?
Keep all the 'new stuff' in follow-up series would be the best option
IMHO.
Thanks!
Paolo
Powered by blists - more mailing lists