netdev - [PATCH v1 net-next 11/16] af_unix: Assign a unique index to SCC.

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-12-kuniyu@amazon.com>
Date: Fri, 2 Feb 2024 19:00:53 -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 11/16] af_unix: Assign a unique index to SCC.

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.

If we start traversing from A in the following graph, the final
lowlink of D is 3.

  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.

To evaluate 1), we need to assign a unique index to a SCC and
assign it to all vertices in the SCC.

This patch changes the lowlink update logic so that in the above
example, 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 if exists.

However, it is no longer called lowlink, so we rename it to
scc_index.

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.

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 59ec8d7880ce..66c8cf835625 100644
--- a/include/net/af_unix.h
+++ b/include/net/af_unix.h
@@ -38,7 +38,7 @@ struct unix_vertex {
 	unsigned long out_degree;
 	unsigned long self_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 cbddca5d8dd1..3d60a5379b7b 100644
--- a/net/unix/garbage.c
+++ b/net/unix/garbage.c
@@ -263,18 +263,18 @@ void unix_free_edges(struct scm_fp_list *fpl)
 
 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_move(&vertex->scc_entry, &vertex_stack);
 
@@ -290,11 +290,11 @@ static void __unix_walk_scc(struct unix_vertex *vertex)
 		}
 
 		if (edge->successor->index != unix_vertex_grouped_index)
-			vertex->lowlink = min(vertex->lowlink, edge->successor->index);
+			vertex->scc_index = min(vertex->scc_index, edge->successor->scc_index);
 next_edge:
 	}
 
-	if (vertex->index == vertex->lowlink) {
+	if (vertex->index == vertex->scc_index) {
 		LIST_HEAD(scc);
 
 		list_cut_position(&scc, &vertex_stack, &vertex->scc_entry);
@@ -321,13 +321,14 @@ static void __unix_walk_scc(struct unix_vertex *vertex)
 		list_del_init(&edge->stack_entry);
 
 		vertex = edge->predecessor;
-		vertex->lowlink = min(vertex->lowlink, edge->successor->lowlink);
+		vertex->scc_index = min(vertex->scc_index, edge->successor->scc_index);
 		goto next_edge;
 	}
 }
 
 static void unix_walk_scc(void)
 {
+	unix_vertex_last_index = UNIX_VERTEX_INDEX_START;
 	unix_graph_maybe_cyclic = false;
 
 	while (!list_empty(&unix_unvisited_vertices)) {
-- 
2.30.2