netdev - [PATCH v1 net-next 09/16] af_unix: Avoid Tarjan's algorithm if unnecessary.

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20240203030058.60750-10-kuniyu@amazon.com>
Date: Fri, 2 Feb 2024 19:00:51 -0800
From: Kuniyuki Iwashima <kuniyu@...zon.com>
To: "David S. Miller" <davem@...emloft.net>, Eric Dumazet
	<edumazet@...gle.com>, Jakub Kicinski <kuba@...nel.org>, Paolo Abeni
	<pabeni@...hat.com>
CC: Kuniyuki Iwashima <kuniyu@...zon.com>, Kuniyuki Iwashima
	<kuni1840@...il.com>, <netdev@...r.kernel.org>
Subject: [PATCH v1 net-next 09/16] af_unix: Avoid Tarjan's algorithm if unnecessary.

In a typical use case, there should be no cyclic references, so we
should skip full cycle detection as much as possible.

Every time we add/delete/update an edge, we check if the successor
is already inflight.

The vertex does not form a cycle if the successor is not inflight.
Thus, we do not need to run Tarjan's algorithm.  Instead, we can
just iterate the already grouped SCC in unix_walk_scc_fast().

But if the successor is already in flight, we set unix_graph_updated
to true and do the grouping again later in unix_walk_scc().

Signed-off-by: Kuniyuki Iwashima <kuniyu@...zon.com>
---
 net/unix/garbage.c | 46 ++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 44 insertions(+), 2 deletions(-)

diff --git a/net/unix/garbage.c b/net/unix/garbage.c
index 24137bf95e02..0f46df05a019 100644
--- a/net/unix/garbage.c
+++ b/net/unix/garbage.c
@@ -111,6 +111,19 @@ void unix_init_vertex(struct unix_sock *u)
 	INIT_LIST_HEAD(&vertex->scc_entry);
 }
 
+static bool unix_graph_updated;
+
+static void unix_graph_update(struct unix_edge *edge)
+{
+	if (unix_graph_updated)
+		return;
+
+	if (!edge->successor->out_degree)
+		return;
+
+	unix_graph_updated = true;
+}
+
 DEFINE_SPINLOCK(unix_gc_lock);
 static LIST_HEAD(unix_unvisited_vertices);
 unsigned int unix_tot_inflight;
@@ -159,6 +172,8 @@ void unix_add_edges(struct scm_fp_list *fpl, struct unix_sock *receiver)
 			INIT_LIST_HEAD(&edge->embryo_entry);
 			list_add_tail(&edge->embryo_entry, &receiver->vertex.edges);
 		}
+
+		unix_graph_update(edge);
 	}
 
 	WRITE_ONCE(unix_tot_inflight, unix_tot_inflight + fpl->count_unix);
@@ -178,6 +193,8 @@ void unix_del_edges(struct scm_fp_list *fpl)
 	while (i < fpl->count_unix) {
 		struct unix_edge *edge = fpl->edges + i++;
 
+		unix_graph_update(edge);
+
 		list_del(&edge->entry);
 
 		if (!--edge->predecessor->out_degree)
@@ -198,8 +215,11 @@ void unix_update_edges(struct unix_sock *receiver)
 
 	spin_lock(&unix_gc_lock);
 
-	list_for_each_entry(edge, &receiver->vertex.edges, embryo_entry)
+	list_for_each_entry(edge, &receiver->vertex.edges, embryo_entry) {
+		unix_graph_update(edge);
+
 		edge->successor = &receiver->vertex;
+	}
 
 	list_del_init(&receiver->vertex.edges);
 
@@ -297,6 +317,25 @@ static void unix_walk_scc(void)
 
 	list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices);
 	swap(unix_vertex_unvisited_index, unix_vertex_grouped_index);
+	unix_graph_updated = false;
+}
+
+static void unix_walk_scc_fast(void)
+{
+	while (!list_empty(&unix_unvisited_vertices)) {
+		struct unix_vertex *vertex;
+		LIST_HEAD(scc);
+
+		vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry);
+		list_add(&scc, &vertex->scc_entry);
+
+		list_for_each_entry_reverse(vertex, &scc, scc_entry)
+			list_move_tail(&vertex->entry, &unix_visited_vertices);
+
+		list_del(&scc);
+	}
+
+	list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices);
 }
 
 static LIST_HEAD(gc_candidates);
@@ -446,7 +485,10 @@ static void __unix_gc(struct work_struct *work)
 
 	spin_lock(&unix_gc_lock);
 
-	unix_walk_scc();
+	if (unix_graph_updated)
+		unix_walk_scc();
+	else
+		unix_walk_scc_fast();
 
 	/* First, select candidates for garbage collection.  Only
 	 * in-flight sockets are considered, and from those only ones
-- 
2.30.2