[PATCH v1 net 0/2] af_unix: Fix inconsistent scc_index.

[PATCH v1 net 0/2] af_unix: Fix inconsistent scc_index.

[Kuniyuki Iwashima]

James Burton reported that a single SCC could have multiple
scc_index and unix_vertex_dead() fails to detect a dead SCC.

Patch 1 fixes it and Patch 2 adds a test case.


Kuniyuki Iwashima (2):
  af_unix: Unify scc_index when finalising SCC in __unix_walk_scc().
  selftest: af_unix: Add test case with mixed lowpoint in scm_rights.c.

 net/unix/garbage.c                              | 17 ++++++++++-------
 .../testing/selftests/net/af_unix/scm_rights.c  | 17 +++++++++++++++++
 2 files changed, 27 insertions(+), 7 deletions(-)

-- 
2.55.0.1007.g17ff1f9808-goog

[PATCH v1 net 1/2] af_unix: Unify scc_index when finalising SCC in __unix_walk_scc().

[Kuniyuki Iwashima]

Commit bfdb01283ee8 ("af_unix: Assign a unique index to SCC.")
changed Tarjan's algorithm to update lowlink with lowlink,
which is called lowpoint (unix_vertex.scc_index).

unix_vertex_dead() assumes all vertices in an SCC share the same
lowpoint, but this is not always true if an SCC has two or more
back edges, depending on the order of DFS.

For example, the graph below has two back edges from B to A
and from C to B.

  A --> B --> C
  ^    | ^    |
  `----' `----'

If DFS walks through A -> B -> C -> B (-> C -> B) -> A (-> B -> A),
each index and scc_index will be updated as follows.

  A --> B --> C    C = (3, 3)  (index, scc_index)
                   B = (2, 2)
                   A = (1, 1)

  A ... B ... C    C = (3, 2)<-.
         ^    |    B = (2, 2) -'
         `----'    A = (1, 1)

  A ... B ... C    C = (3, 2)
  ^    | .    .    B = (2, 1)<-.
  `----'  ....     A = (1, 1) -'

Then, unix_vertex_dead() thinks that B is passed to another
SCC with scc_index 2, and the SCC is not garbage-collected.

This does not happen if DFS walks in a different order below
or starts from B.

    1      3
  A --> B --> C
  ^    | ^    |
  `----' `----'
     2      4

Let's unify scc_index across the SCC when finalising it.

Note that updating v->index was previously done in unix_scc_dead(),
when called from __unix_walk_scc(), just to save one loop.  Since
__unix_walk_scc() now iterates over the SCC anyway, the update is
moved back to __unix_walk_scc() and 'fast' argument is dropped.

Fixes: 4090fa373f0e ("af_unix: Replace garbage collection algorithm.")
Reported-by: James Burton <jamesburton@meta.com>
Signed-off-by: Kuniyuki Iwashima <kuniyu@google.com>
---
 net/unix/garbage.c | 17 ++++++++++-------
 1 file changed, 10 insertions(+), 7 deletions(-)

diff --git a/net/unix/garbage.c b/net/unix/garbage.c
index 9fcaaf55cba5..da774f56ca64 100644
--- a/net/unix/garbage.c
+++ b/net/unix/garbage.c
@@ -374,7 +374,7 @@ static bool unix_vertex_dead(struct unix_vertex *vertex)
 static LIST_HEAD(unix_visited_vertices);
 static unsigned long unix_vertex_grouped_index = UNIX_VERTEX_INDEX_MARK2;
 
-static bool unix_scc_dead(struct list_head *scc, bool fast)
+static bool unix_scc_dead(struct list_head *scc)
 {
 	struct unix_vertex *vertex;
 	bool scc_dead = true;
@@ -386,10 +386,6 @@ static bool unix_scc_dead(struct list_head *scc, bool fast)
 		/* Don't restart DFS from this vertex. */
 		list_move_tail(&vertex->entry, &unix_visited_vertices);
 
-		/* Mark vertex as off-stack for __unix_walk_scc(). */
-		if (!fast)
-			vertex->index = unix_vertex_grouped_index;
-
 		if (scc_dead)
 			scc_dead = unix_vertex_dead(vertex);
 	}
@@ -521,6 +517,7 @@ static unsigned long __unix_walk_scc(struct unix_vertex *vertex,
 	}
 
 	if (vertex->index == vertex->scc_index) {
+		struct unix_vertex *v;
 		struct list_head scc;
 
 		/* SCC finalised.
@@ -530,7 +527,13 @@ static unsigned long __unix_walk_scc(struct unix_vertex *vertex,
 		 */
 		__list_cut_position(&scc, &vertex_stack, &vertex->scc_entry);
 
-		if (unix_scc_dead(&scc, false)) {
+		list_for_each_entry_reverse(v, &scc, scc_entry) {
+			/* Mark vertex as off-stack and assign a unique ID. */
+			v->index = unix_vertex_grouped_index;
+			v->scc_index = vertex->scc_index;
+		}
+
+		if (unix_scc_dead(&scc)) {
 			unix_collect_skb(&scc, hitlist);
 		} else {
 			if (unix_vertex_max_scc_index < vertex->scc_index)
@@ -588,7 +591,7 @@ static void unix_walk_scc_fast(struct sk_buff_head *hitlist)
 		vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry);
 		list_add(&scc, &vertex->scc_entry);
 
-		if (unix_scc_dead(&scc, true)) {
+		if (unix_scc_dead(&scc)) {
 			cyclic_sccs--;
 			unix_collect_skb(&scc, hitlist);
 		}
-- 
2.55.0.1007.g17ff1f9808-goog

[PATCH v1 net 2/2] selftest: af_unix: Add test case with mixed lowpoint in scm_rights.c.

[Kuniyuki Iwashima]

The new test case creates two SCCs so that each of them
has multiple scc_index.

Without patch, GC cannot free the sockets and the test fails.

  #  RUN           scm_rights.dgram.mixed_lowpoints ...
  # scm_rights.c:176:mixed_lowpoints:Expected 0 (0) == ret (12)
  # mixed_lowpoints: Test terminated by assertion
  #          FAIL  scm_rights.dgram.mixed_lowpoints
  not ok 5 scm_rights.dgram.mixed_lowpoints
  ...
  # FAILED: 45 / 50 tests passed.
  # Totals: pass:45 fail:5 xfail:0 xpass:0 skip:0 error:0

With the patch, all tests pass.

  # PASSED: 50 / 50 tests passed.
  # Totals: pass:50 fail:0 xfail:0 xpass:0 skip:0 error:0

Signed-off-by: Kuniyuki Iwashima <kuniyu@google.com>
---
 .../testing/selftests/net/af_unix/scm_rights.c  | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/tools/testing/selftests/net/af_unix/scm_rights.c b/tools/testing/selftests/net/af_unix/scm_rights.c
index d82a79c21c17..c165f250220a 100644
--- a/tools/testing/selftests/net/af_unix/scm_rights.c
+++ b/tools/testing/selftests/net/af_unix/scm_rights.c
@@ -378,4 +378,21 @@ TEST_F(scm_rights, backtrack_from_scc)
 	close_sockets(10);
 }
 
+TEST_F(scm_rights, mixed_lowpoint)
+{
+	create_sockets(6);
+
+	send_fd(0, 1);
+	send_fd(1, 2);
+	send_fd(2, 1);
+	send_fd(1, 0);
+
+	send_fd(3, 4);
+	send_fd(4, 5);
+	send_fd(5, 4);
+	send_fd(4, 3);
+
+	close_sockets(6);
+}
+
 TEST_HARNESS_MAIN
-- 
2.55.0.1007.g17ff1f9808-goog