From nobody Wed Dec 17 03:27:47 2025 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 312A31E1E1C; Wed, 21 May 2025 14:51:20 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1747839080; cv=none; b=uBaBoRnI8c1ssZzAPx9i6OIkstIPYCEbsEt8meS/T5u4IlpqTw0+CGw1pa2/oG3oCai1MWgpSuxOH2Ruo0UiCpnb71ja+CJDA4r5R51lu1EenuR5EdSJmoqrn8oG1fzjW0ssEySilcaY6qj/PM20OvocECp9sIof7UU4sPKmaVQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1747839080; c=relaxed/simple; bh=wRQQFqc9Q+OLVI5oXIa/+8+D65v+vcb0Zh7HW85KKHA=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=kjrof9FgPxRFIu3q7DF+0BxNa4m6si7uUl+ATfXto5nmedjqlNSh58av4YTgdRmss2gVkkm6tvZg9KSwGjHHpCyTNN4Ar/GNWj6N2ZmIOujRVdy22RJFqApPUOpUHmGBUY2pok7pCZIpzOojValNbJLEMb8a1ehkBwR1tlvCyHw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=DA8eXBMz; arc=none smtp.client-ip=10.30.226.201 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="DA8eXBMz" Received: by smtp.kernel.org (Postfix) with ESMTPSA id CD885C4CEE4; Wed, 21 May 2025 14:51:17 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1747839080; bh=wRQQFqc9Q+OLVI5oXIa/+8+D65v+vcb0Zh7HW85KKHA=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=DA8eXBMzI1PSW+QcxTgxDwb8qWW5aTeW/mXfohn6JRevEPD8V7Wz1g6o72F2UFbjV Rd1iXuvp8d7+eiKJqL3ipAeBXnjzCMvNJo6bQBGbWqEfTCKfXx51WgBtJYQzeqeywf JlBD6KHGI9bTiAsUmaCgPphUZkszuBDcUqfuKIyc0uUFzqVl7NSOycv1IiuEe1Z8op H8DkVB3Vt1vVbtwkxg/DDX478zKE14Ldolm/TGeztcOvomAqglFaj62FnEJWgodEIX oO3+J5qJxcH/RWdLNl1p+YmxyVT46GwCa+rcVFYE5+1Y5YYCEFxqCOttshYq29VhCk 3H0qnWABVwXvQ== From: Lee Jones To: lee@kernel.org, "David S. Miller" , Eric Dumazet , Jakub Kicinski , Paolo Abeni , Kuniyuki Iwashima , Jens Axboe , Sasha Levin , Michal Luczaj , Rao Shoaib , Simon Horman , linux-kernel@vger.kernel.org, netdev@vger.kernel.org Cc: stable@vger.kernel.org Subject: [PATCH v6.6 15/26] af_unix: Save O(n) setup of Tarjan's algo. Date: Wed, 21 May 2025 14:45:23 +0000 Message-ID: <20250521144803.2050504-16-lee@kernel.org> X-Mailer: git-send-email 2.49.0.1112.g889b7c5bd8-goog In-Reply-To: <20250521144803.2050504-1-lee@kernel.org> References: <20250521144803.2050504-1-lee@kernel.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" From: Kuniyuki Iwashima [ Upstream commit ba31b4a4e1018f5844c6eb31734976e2184f2f9a ] Before starting Tarjan's algorithm, we need to mark all vertices as unvisited. We can save this O(n) setup by reserving two special indices (0, 1) and using two variables. The first time we link a vertex to unix_unvisited_vertices, we set unix_vertex_unvisited_index to index. During DFS, we can see that the index of unvisited vertices is the same as unix_vertex_unvisited_index. When we finalise SCC later, we set unix_vertex_grouped_index to each vertex's index. Then, we can know (i) that the vertex is on the stack if the index of a visited vertex is >=3D 2 and (ii) that it is not on the stack and belongs to a different SCC if the index is unix_vertex_grouped_index. After the whole algorithm, all indices of vertices are set as unix_vertex_grouped_index. Next time we start DFS, we know that all unvisited vertices have unix_vertex_grouped_index, and we can use unix_vertex_unvisited_index as the not-on-stack marker. To use the same variable in __unix_walk_scc(), we can swap unix_vertex_(grouped|unvisited)_index at the end of Tarjan's algorithm. Signed-off-by: Kuniyuki Iwashima Acked-by: Paolo Abeni Link: https://lore.kernel.org/r/20240325202425.60930-10-kuniyu@amazon.com Signed-off-by: Jakub Kicinski (cherry picked from commit ba31b4a4e1018f5844c6eb31734976e2184f2f9a) Signed-off-by: Lee Jones --- include/net/af_unix.h | 1 - net/unix/garbage.c | 26 +++++++++++++++----------- 2 files changed, 15 insertions(+), 12 deletions(-) diff --git a/include/net/af_unix.h b/include/net/af_unix.h index 9d92dd608fc42..053f67adb9f1b 100644 --- a/include/net/af_unix.h +++ b/include/net/af_unix.h @@ -37,7 +37,6 @@ struct unix_vertex { unsigned long out_degree; unsigned long index; unsigned long lowlink; - bool on_stack; }; =20 struct unix_edge { diff --git a/net/unix/garbage.c b/net/unix/garbage.c index 6ff7e0b5c5444..feae6c17b2911 100644 --- a/net/unix/garbage.c +++ b/net/unix/garbage.c @@ -115,16 +115,20 @@ static struct unix_vertex *unix_edge_successor(struct= unix_edge *edge) static LIST_HEAD(unix_unvisited_vertices); =20 enum unix_vertex_index { - UNIX_VERTEX_INDEX_UNVISITED, + UNIX_VERTEX_INDEX_MARK1, + UNIX_VERTEX_INDEX_MARK2, UNIX_VERTEX_INDEX_START, }; =20 +static unsigned long unix_vertex_unvisited_index =3D UNIX_VERTEX_INDEX_MAR= K1; + static void unix_add_edge(struct scm_fp_list *fpl, struct unix_edge *edge) { struct unix_vertex *vertex =3D edge->predecessor->vertex; =20 if (!vertex) { vertex =3D list_first_entry(&fpl->vertices, typeof(*vertex), entry); + vertex->index =3D unix_vertex_unvisited_index; vertex->out_degree =3D 0; INIT_LIST_HEAD(&vertex->edges); =20 @@ -265,6 +269,7 @@ void unix_destroy_fpl(struct scm_fp_list *fpl) } =20 static LIST_HEAD(unix_visited_vertices); +static unsigned long unix_vertex_grouped_index =3D UNIX_VERTEX_INDEX_MARK2; =20 static void __unix_walk_scc(struct unix_vertex *vertex) { @@ -274,10 +279,10 @@ static void __unix_walk_scc(struct unix_vertex *verte= x) LIST_HEAD(edge_stack); =20 next_vertex: - /* Push vertex to vertex_stack. + /* Push vertex to vertex_stack and mark it as on-stack + * (index >=3D UNIX_VERTEX_INDEX_START). * The vertex will be popped when finalising SCC later. */ - vertex->on_stack =3D true; list_add(&vertex->scc_entry, &vertex_stack); =20 vertex->index =3D index; @@ -291,7 +296,7 @@ static void __unix_walk_scc(struct unix_vertex *vertex) if (!next_vertex) continue; =20 - if (next_vertex->index =3D=3D UNIX_VERTEX_INDEX_UNVISITED) { + if (next_vertex->index =3D=3D unix_vertex_unvisited_index) { /* Iterative deepening depth first search * * 1. Push a forward edge to edge_stack and set @@ -317,7 +322,7 @@ static void __unix_walk_scc(struct unix_vertex *vertex) * to skip SCC finalisation. */ vertex->lowlink =3D min(vertex->lowlink, next_vertex->lowlink); - } else if (next_vertex->on_stack) { + } else if (next_vertex->index !=3D unix_vertex_grouped_index) { /* Loop detected by a back/cross edge. * * The successor is on vertex_stack, so two vertices are @@ -344,7 +349,8 @@ static void __unix_walk_scc(struct unix_vertex *vertex) /* Don't restart DFS from this vertex in unix_walk_scc(). */ list_move_tail(&vertex->entry, &unix_visited_vertices); =20 - vertex->on_stack =3D false; + /* Mark vertex as off-stack. */ + vertex->index =3D unix_vertex_grouped_index; } =20 list_del(&scc); @@ -357,20 +363,18 @@ static void __unix_walk_scc(struct unix_vertex *verte= x) =20 static void unix_walk_scc(void) { - struct unix_vertex *vertex; - - list_for_each_entry(vertex, &unix_unvisited_vertices, entry) - vertex->index =3D 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)) { + struct unix_vertex *vertex; + vertex =3D list_first_entry(&unix_unvisited_vertices, typeof(*vertex), e= ntry); __unix_walk_scc(vertex); } =20 list_replace_init(&unix_visited_vertices, &unix_unvisited_vertices); + swap(unix_vertex_unvisited_index, unix_vertex_grouped_index); } =20 static LIST_HEAD(gc_candidates); --=20 2.49.0.1112.g889b7c5bd8-goog