| Message ID | 20240325202425.60930-1-kuniyu@amazon.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | af_unix: Rework GC. | expand |
On Mon, 2024-03-25 at 13:24 -0700, Kuniyuki Iwashima wrote: > When we pass a file descriptor to an AF_UNIX socket via SCM_RIGTHS, > the underlying struct file of the inflight fd gets its refcount bumped. > If the fd is of an AF_UNIX socket, we need to track it in case it forms > cyclic references. > > Let's say we send a fd of AF_UNIX socket A to B and vice versa and > close() both sockets. > > When created, each socket's struct file initially has one reference. > After the fd exchange, both refcounts are bumped up to 2. Then, close() > decreases both to 1. From this point on, no one can touch the file/socket. > > However, the struct file has one refcount and thus never calls the > release() function of the AF_UNIX socket. > > That's why we need to track all inflight AF_UNIX sockets and run garbage > collection. > > This series replaces the current GC implementation that locks each inflight > socket's receive queue and requires trickiness in other places. > > The new GC does not lock each socket's queue to minimise its effect and > tries to be lightweight if there is no cyclic reference or no update in > the shape of the inflight fd graph. > > The new implementation is based on Tarjan's Strongly Connected Components > algorithm, and we will consider each inflight AF_UNIX socket as a vertex > and its file descriptor as an edge in a directed graph. > > For the details, please see each patch. > > patch 1 - 3 : Add struct to express inflight socket graphs > patch 4 : Optimse inflight fd counting > patch 5 - 6 : Group SCC possibly forming a cycle > patch 7 - 8 : Support embryo socket > patch 9 - 11 : Make GC lightweight > patch 12 - 13 : Detect dead cycle references > patch 14 : Replace GC algorithm > patch 15 : selftest > > After this series is applied, we can remove the two ugly tricks for race, > scm_fp_dup() in unix_attach_fds() and spin_lock dance in unix_peek_fds() > as done in patch 14/15 of v1. > > Also, we will add cond_resched_lock() in __unix_gc() and convert it to > use a dedicated kthread instead of global system workqueue as suggested > by Paolo in a v4 thread. > > > Changes: > v5: > * Rebase on the latest net-next.git I went through this and LGTM. Additionally, I think it would be better merge this at the beginning of the cycle rather then later. Acked-by: Paolo Abeni <pabeni@redhat.com>
Hello: This series was applied to netdev/net-next.git (main) by Jakub Kicinski <kuba@kernel.org>: On Mon, 25 Mar 2024 13:24:10 -0700 you wrote: > When we pass a file descriptor to an AF_UNIX socket via SCM_RIGTHS, > the underlying struct file of the inflight fd gets its refcount bumped. > If the fd is of an AF_UNIX socket, we need to track it in case it forms > cyclic references. > > Let's say we send a fd of AF_UNIX socket A to B and vice versa and > close() both sockets. > > [...] Here is the summary with links: - [v5,net-next,01/15] af_unix: Allocate struct unix_vertex for each inflight AF_UNIX fd. https://git.kernel.org/netdev/net-next/c/1fbfdfaa5902 - [v5,net-next,02/15] af_unix: Allocate struct unix_edge for each inflight AF_UNIX fd. https://git.kernel.org/netdev/net-next/c/29b64e354029 - [v5,net-next,03/15] af_unix: Link struct unix_edge when queuing skb. https://git.kernel.org/netdev/net-next/c/42f298c06b30 - [v5,net-next,04/15] af_unix: Bulk update unix_tot_inflight/unix_inflight when queuing skb. https://git.kernel.org/netdev/net-next/c/22c3c0c52d32 - [v5,net-next,05/15] af_unix: Iterate all vertices by DFS. https://git.kernel.org/netdev/net-next/c/6ba76fd2848e - [v5,net-next,06/15] af_unix: Detect Strongly Connected Components. https://git.kernel.org/netdev/net-next/c/3484f063172d - [v5,net-next,07/15] af_unix: Save listener for embryo socket. https://git.kernel.org/netdev/net-next/c/aed6ecef55d7 - [v5,net-next,08/15] af_unix: Fix up unix_edge.successor for embryo socket. https://git.kernel.org/netdev/net-next/c/dcf70df2048d - [v5,net-next,09/15] af_unix: Save O(n) setup of Tarjan's algo. https://git.kernel.org/netdev/net-next/c/ba31b4a4e101 - [v5,net-next,10/15] af_unix: Skip GC if no cycle exists. https://git.kernel.org/netdev/net-next/c/77e5593aebba - [v5,net-next,11/15] af_unix: Avoid Tarjan's algorithm if unnecessary. https://git.kernel.org/netdev/net-next/c/ad081928a8b0 - [v5,net-next,12/15] af_unix: Assign a unique index to SCC. https://git.kernel.org/netdev/net-next/c/bfdb01283ee8 - [v5,net-next,13/15] af_unix: Detect dead SCC. https://git.kernel.org/netdev/net-next/c/a15702d8b3aa - [v5,net-next,14/15] af_unix: Replace garbage collection algorithm. https://git.kernel.org/netdev/net-next/c/4090fa373f0e - [v5,net-next,15/15] selftest: af_unix: Test GC for SCM_RIGHTS. https://git.kernel.org/netdev/net-next/c/2aa0cff26ed5 You are awesome, thank you!
When we pass a file descriptor to an AF_UNIX socket via SCM_RIGTHS, the underlying struct file of the inflight fd gets its refcount bumped. If the fd is of an AF_UNIX socket, we need to track it in case it forms cyclic references. Let's say we send a fd of AF_UNIX socket A to B and vice versa and close() both sockets. When created, each socket's struct file initially has one reference. After the fd exchange, both refcounts are bumped up to 2. Then, close() decreases both to 1. From this point on, no one can touch the file/socket. However, the struct file has one refcount and thus never calls the release() function of the AF_UNIX socket. That's why we need to track all inflight AF_UNIX sockets and run garbage collection. This series replaces the current GC implementation that locks each inflight socket's receive queue and requires trickiness in other places. The new GC does not lock each socket's queue to minimise its effect and tries to be lightweight if there is no cyclic reference or no update in the shape of the inflight fd graph. The new implementation is based on Tarjan's Strongly Connected Components algorithm, and we will consider each inflight AF_UNIX socket as a vertex and its file descriptor as an edge in a directed graph. For the details, please see each patch. patch 1 - 3 : Add struct to express inflight socket graphs patch 4 : Optimse inflight fd counting patch 5 - 6 : Group SCC possibly forming a cycle patch 7 - 8 : Support embryo socket patch 9 - 11 : Make GC lightweight patch 12 - 13 : Detect dead cycle references patch 14 : Replace GC algorithm patch 15 : selftest After this series is applied, we can remove the two ugly tricks for race, scm_fp_dup() in unix_attach_fds() and spin_lock dance in unix_peek_fds() as done in patch 14/15 of v1. Also, we will add cond_resched_lock() in __unix_gc() and convert it to use a dedicated kthread instead of global system workqueue as suggested by Paolo in a v4 thread. Changes: v5: * Rebase on the latest net-next.git v4: https://lore.kernel.org/netdev/20240301022243.73908-1-kuniyu@amazon.com/ * Split SCC detection patch to 3 & 4 * Add comments * Patch 10 * Remove early return in unix_update_graph(), (cyclic=1, grouped=1) triggers access to uninit scc_index in unix_walk_scc_fast() * Patch 12 * Make unix_vertex_last_index local var * Patch 13 * s/dead/scc_dead/ * Patch 14 * Fix lockdep false-positive splat * Make hitlist local var v3: https://lore.kernel.org/netdev/20240223214003.17369-1-kuniyu@amazon.com/ * Patch 1 * Allocate struct unix_vertex dynamically only for inflight socket * Patch 2 * Rename unix_edge.entry to unix_edge.vertex_entry * Change edge->successor/predecessor to struct unix_sock * Patch 7 * Fix up embryo successor during GC instead of overwriting edge in unix_add_edge() * To not allcoate unix_vertex to listener for embryo socket * Kept the name unix_update_edges() unchanged as it affect successor tracking during GC * Patch 12 * Drop self_degree and check all edges * To not allcoate unix_vertex to listener for embryo socket v2: https://lore.kernel.org/netdev/20240216210556.65913-1-kuniyu@amazon.com/ * Drop 2 patches as follow-up that removes trickiness in unix_attach_fds() and unix_peek_fds(). * Patch 2 * Fix build error when CONFIG_UNIX=n * Patch 3 * Remove unnecessary INIT_LIST_HEAD() * Patch 7 * Fix build warning for using goto label at the end of the loop * Patch 13 * Call kfree_skb() for oob skb * Patch 14 * Add test case for MSG_OOB v1: https://lore.kernel.org/netdev/20240203030058.60750-1-kuniyu@amazon.com/ Kuniyuki Iwashima (15): af_unix: Allocate struct unix_vertex for each inflight AF_UNIX fd. af_unix: Allocate struct unix_edge for each inflight AF_UNIX fd. af_unix: Link struct unix_edge when queuing skb. af_unix: Bulk update unix_tot_inflight/unix_inflight when queuing skb. af_unix: Iterate all vertices by DFS. af_unix: Detect Strongly Connected Components. af_unix: Save listener for embryo socket. af_unix: Fix up unix_edge.successor for embryo socket. af_unix: Save O(n) setup of Tarjan's algo. af_unix: Skip GC if no cycle exists. af_unix: Avoid Tarjan's algorithm if unnecessary. af_unix: Assign a unique index to SCC. af_unix: Detect dead SCC. af_unix: Replace garbage collection algorithm. selftest: af_unix: Test GC for SCM_RIGHTS. include/net/af_unix.h | 31 +- include/net/scm.h | 9 + net/core/scm.c | 11 + net/unix/af_unix.c | 27 +- net/unix/garbage.c | 573 ++++++++++++------ tools/testing/selftests/net/.gitignore | 1 + tools/testing/selftests/net/af_unix/Makefile | 2 +- .../selftests/net/af_unix/scm_rights.c | 286 +++++++++ 8 files changed, 735 insertions(+), 205 deletions(-) create mode 100644 tools/testing/selftests/net/af_unix/scm_rights.c