From nobody Sun Feb 8 02:24:56 2026 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 C7718217704; Wed, 21 May 2025 15:34:17 +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=1747841657; cv=none; b=sSG7VVGc0DSEpDytSKyzh3QerEPMMY+fhRa8sfVVcrI4pcbK73cO7z8wpuXKRjr/hoc1pyoMOkawd4vFwdahNMp5Y8x3a69gynGE2qRva2RRTnteHDpSZJ8k8/ARVTO4qFfq3YIkA5vwt8UbuXDyDmmflPvSYe8W1UfRTG4wBhQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1747841657; c=relaxed/simple; bh=uNlOJaA3Kj9exb8Mp76c1OZdZEWpdVv9D2KSAybA18Q=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=WwjAeoTUcDr9DXYcgQyU7ODr9EZCot28O5EEoudm6C/gyQPsDn6zd9oFv5Jet1MFCxpfraU0RbLpn/bG4bROq03D5wmMQpN5N+UggQB+fbw+mP0YUD5fPmy+tBOFUfWIXNPwVpsDmb6mRJcAngsb2uMj+DUQjnkwa3NXhRp9ufA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=r/SiIbi8; 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="r/SiIbi8" Received: by smtp.kernel.org (Postfix) with ESMTPSA id AC4F9C4CEE4; Wed, 21 May 2025 15:34:14 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1747841657; bh=uNlOJaA3Kj9exb8Mp76c1OZdZEWpdVv9D2KSAybA18Q=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=r/SiIbi87JL+YWRLguYSshkkgWbRjRQx6ooMpbxhPM02zq9suGVedlxL8OpsIIZoH 5T66yaq2/LAGg54Mlcp+AyHG+6nTk+aTZMu/Z15f+C50vuyA3B0dnAhma2TIhmCeGm wRewuomehLUdmTz4fsqA7arDDwep04K4rmqNNmNwdxbOVHUjJH8lf0quTSHQB9iVrf oDkUYdkAojPMNsU3ZrWJEnSyw+LwVmN7GqvofcPLAHcHB1AxQrgrGRUy+jqZnKhkFC FXLNiv3MJwpIDwkzi+jbVPlZtGNOgZPhBCG9y6B6WgOzYNgkEm4+aajDTPM9tvmopv w2iq2u1XbN3Zg== From: Lee Jones To: lee@kernel.org, "David S. Miller" , Eric Dumazet , Jakub Kicinski , Paolo Abeni , Christian Brauner , Kuniyuki Iwashima , Alexander Mikhalitsyn , 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.1 17/27] af_unix: Skip GC if no cycle exists. Date: Wed, 21 May 2025 16:27:16 +0100 Message-ID: <20250521152920.1116756-18-lee@kernel.org> X-Mailer: git-send-email 2.49.0.1143.g0be31eac6b-goog In-Reply-To: <20250521152920.1116756-1-lee@kernel.org> References: <20250521152920.1116756-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 77e5593aebba823bcbcf2c4b58b07efcd63933b8 ] We do not need to run GC if there is no possible cyclic reference. We use unix_graph_maybe_cyclic to decide if we should run GC. If a fd of an AF_UNIX socket is passed to an already inflight AF_UNIX socket, they could form a cyclic reference. Then, we set true to unix_graph_maybe_cyclic and later run Tarjan's algorithm to group them into SCC. Once we run Tarjan's algorithm, we are 100% sure whether cyclic references exist or not. If there is no cycle, we set false to unix_graph_maybe_cyclic and can skip the entire garbage collection next time. When finalising SCC, we set true to unix_graph_maybe_cyclic if SCC consists of multiple vertices. Even if SCC is a single vertex, a cycle might exist as self-fd passing. Given the corner case is rare, we detect it by checking all edges of the vertex and set true to unix_graph_maybe_cyclic. With this change, __unix_gc() is just a spin_lock() dance in the normal usage. Signed-off-by: Kuniyuki Iwashima Acked-by: Paolo Abeni Link: https://lore.kernel.org/r/20240325202425.60930-11-kuniyu@amazon.com Signed-off-by: Jakub Kicinski (cherry picked from commit 77e5593aebba823bcbcf2c4b58b07efcd63933b8) Signed-off-by: Lee Jones --- net/unix/garbage.c | 48 +++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 47 insertions(+), 1 deletion(-) diff --git a/net/unix/garbage.c b/net/unix/garbage.c index feae6c17b291..8f0dc39bb72f 100644 --- a/net/unix/garbage.c +++ b/net/unix/garbage.c @@ -112,6 +112,19 @@ static struct unix_vertex *unix_edge_successor(struct = unix_edge *edge) return edge->successor->vertex; } =20 +static bool unix_graph_maybe_cyclic; + +static void unix_update_graph(struct unix_vertex *vertex) +{ + /* If the receiver socket is not inflight, no cyclic + * reference could be formed. + */ + if (!vertex) + return; + + unix_graph_maybe_cyclic =3D true; +} + static LIST_HEAD(unix_unvisited_vertices); =20 enum unix_vertex_index { @@ -138,12 +151,16 @@ static void unix_add_edge(struct scm_fp_list *fpl, st= ruct unix_edge *edge) =20 vertex->out_degree++; list_add_tail(&edge->vertex_entry, &vertex->edges); + + unix_update_graph(unix_edge_successor(edge)); } =20 static void unix_del_edge(struct scm_fp_list *fpl, struct unix_edge *edge) { struct unix_vertex *vertex =3D edge->predecessor->vertex; =20 + unix_update_graph(unix_edge_successor(edge)); + list_del(&edge->vertex_entry); vertex->out_degree--; =20 @@ -227,6 +244,7 @@ void unix_del_edges(struct scm_fp_list *fpl) void unix_update_edges(struct unix_sock *receiver) { spin_lock(&unix_gc_lock); + unix_update_graph(unix_sk(receiver->listener)->vertex); receiver->listener =3D NULL; spin_unlock(&unix_gc_lock); } @@ -268,6 +286,26 @@ void unix_destroy_fpl(struct scm_fp_list *fpl) unix_free_vertices(fpl); } =20 +static bool unix_scc_cyclic(struct list_head *scc) +{ + struct unix_vertex *vertex; + struct unix_edge *edge; + + /* SCC containing multiple vertices ? */ + if (!list_is_singular(scc)) + return true; + + vertex =3D list_first_entry(scc, typeof(*vertex), scc_entry); + + /* Self-reference or a embryo-listener circle ? */ + list_for_each_entry(edge, &vertex->edges, vertex_entry) { + if (unix_edge_successor(edge) =3D=3D vertex) + return true; + } + + return false; +} + static LIST_HEAD(unix_visited_vertices); static unsigned long unix_vertex_grouped_index =3D UNIX_VERTEX_INDEX_MARK2; =20 @@ -353,6 +391,9 @@ static void __unix_walk_scc(struct unix_vertex *vertex) vertex->index =3D unix_vertex_grouped_index; } =20 + if (!unix_graph_maybe_cyclic) + unix_graph_maybe_cyclic =3D unix_scc_cyclic(&scc); + list_del(&scc); } =20 @@ -363,6 +404,8 @@ static void __unix_walk_scc(struct unix_vertex *vertex) =20 static void unix_walk_scc(void) { + unix_graph_maybe_cyclic =3D false; + /* Visit every vertex exactly once. * __unix_walk_scc() moves visited vertices to unix_visited_vertices. */ @@ -524,6 +567,9 @@ static void __unix_gc(struct work_struct *work) =20 spin_lock(&unix_gc_lock); =20 + if (!unix_graph_maybe_cyclic) + goto skip_gc; + unix_walk_scc(); =20 /* First, select candidates for garbage collection. Only @@ -633,7 +679,7 @@ static void __unix_gc(struct work_struct *work) =20 /* All candidates should have been detached by now. */ WARN_ON_ONCE(!list_empty(&gc_candidates)); - +skip_gc: /* Paired with READ_ONCE() in wait_for_unix_gc(). */ WRITE_ONCE(gc_in_progress, false); =20 --=20 2.49.0.1143.g0be31eac6b-goog