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 consider each inflight file descriptor of AF_UNIX sockets
as an edge in a directed graph.

If socket B has the fd of socket A, socket B holds refcount of A, and then
we consider it as A -> B.

For the details, please see each patch.

  patch 1  -  5 : Add struct to express graphs
  patch       6 : Optimse inflight fd counters
  patch       7 : Group SCC
  patch 8  - 10 : Make GC lightweight
  patch 11 - 12 : Detect dead cycle reference
  patch      13 : Replace GC algorithm
  patch 14 - 15 : Remove confusing tricks
  patch      16 : selftest


Kuniyuki Iwashima (16):
  af_unix: Add struct unix_vertex in struct unix_sock.
  af_unix: Allocate struct unix_edge for each inflight AF_UNIX fd.
  af_unix: Link struct unix_edge when queuing skb.
  af_unix: Save listener for embryo socket.
  af_unix: Fix up unix_edge.successor for embryo socket.
  af_unix: Bulk update unix_tot_inflight/unix_inflight when queuing skb.
  af_unix: Detect Strongly Connected Components.
  af_unix: Save O(n) setup of Tarjan's algo.
  af_unix: Avoid Tarjan's algorithm if unnecessary.
  af_unix: Skip GC if no cycle exists.
  af_unix: Assign a unique index to SCC.
  af_unix: Detect dead SCC.
  af_unix: Replace garbage collection algorithm.
  af_unix: Remove scm_fp_dup() in unix_attach_fds().
  af_unix: Remove lock dance in unix_peek_fds().
  selftest: af_unix: Test GC for SCM_RIGHTS.

 include/net/af_unix.h                         |  34 +-
 include/net/scm.h                             |   8 +
 net/core/scm.c                                |   5 +
 net/unix/af_unix.c                            |  78 +--
 net/unix/garbage.c                            | 459 +++++++++++-------
 tools/testing/selftests/net/.gitignore        |   1 +
 tools/testing/selftests/net/af_unix/Makefile  |   2 +-
 .../selftests/net/af_unix/scm_rights.c        | 242 +++++++++
 8 files changed, 580 insertions(+), 249 deletions(-)
 create mode 100644 tools/testing/selftests/net/af_unix/scm_rights.c

-- 
2.30.2