| 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: <20240306201413.13082-1-kuniyu@amazon.com>
Date: Wed, 6 Mar 2024 12:14:13 -0800
From: Kuniyuki Iwashima <kuniyu@...zon.com>
To: <pabeni@...hat.com>
CC: <davem@...emloft.net>, <edumazet@...gle.com>, <kuba@...nel.org>,
<kuni1840@...il.com>, <kuniyu@...zon.com>, <netdev@...r.kernel.org>
Subject: Re: [PATCH v4 net-next 05/15] af_unix: Iterate all vertices by DFS.
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.
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 ?
Thanks!
Powered by blists - more mailing lists