Message-ID: <20240301022243.73908-1-kuniyu@amazon.com>
Date: Thu, 29 Feb 2024 18:22:28 -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 v4 net-next 00/15] af_unix: Rework GC.

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.


Changes:
  v4:
    * 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

-- 
2.30.2

Powered by blists - more mailing lists