Just before queuing skb with inflight fds, we call scm_stat_add(),
which is a good place to set up the preallocated struct unix_edge
in UNIXCB(skb).fp->edges.

Then, we call unix_add_edges() and construct the directed graph
as follows:

  1. Set the inflight socket's unix_vertex to unix_edge.predecessor
  2. Set the receiver's unix_vertex to unix_edge.successor
  3. Link unix_edge.entry to the inflight socket's unix_vertex.edges
  4. Link inflight socket's unix_vertex.entry to unix_unvisited_vertices.

Let's say we pass the fd of AF_UNIX socket A to B and the fd of B
to C.  The graph looks like this:

  +-------------------------+
  | unix_unvisited_vertices | <------------------------.
  +-------------------------+                          |
  +                                                    |
  |   +-------------+                +-------------+   |            +-------------+
  |   | unix_sock A |                | unix_sock B |   |            | unix_sock C |
  |   +-------------+                +-------------+   |            +-------------+
  |   | unix_vertex | <----.  .----> | unix_vertex | <-|--.  .----> | unix_vertex |
  |   | +-----------+      |  |      | +-----------+   |  |  |      | +-----------+
  `-> | |   entry   | +------------> | |   entry   | +-'  |  |      | |   entry   |
      | |-----------|      |  |      | |-----------|      |  |      | |-----------|
      | |   edges   | <-.  |  |      | |   edges   | <-.  |  |      | |   edges   |
      +-+-----------+   |  |  |      +-+-----------+   |  |  |      +-+-----------+
                        |  |  |                        |  |  |
  .---------------------'  |  |  .---------------------'  |  |
  |                        |  |  |                        |  |
  |   +-------------+      |  |  |   +-------------+      |  |
  |   |  unix_edge  |      |  |  |   |  unix_edge  |      |  |
  |   +-------------+      |  |  |   +-------------+      |  |
  `-> |    entry    |      |  |  `-> |    entry    |      |  |
      |-------------|      |  |      |-------------|      |  |
      | predecessor | +----'  |      | predecessor | +----'  |
      |-------------|         |      |-------------|         |
      |  successor  | +-------'      |  successor  | +-------'
      +-------------+                +-------------+

Henceforth, we denote such a graph as A -> B (-> C).

Now, we can express all inflight fd graphs that do not contain
embryo sockets.  The following two patches will support the
particular case.

Signed-off-by: Kuniyuki Iwashima <redacted>
---
 include/net/af_unix.h |  2 ++
 include/net/scm.h     |  1 +
 net/core/scm.c        |  2 ++
 net/unix/af_unix.c    |  8 +++++--
 net/unix/garbage.c    | 56 ++++++++++++++++++++++++++++++++++++++++++-
 5 files changed, 66 insertions(+), 3 deletions(-)

diff --git a/include/net/af_unix.h b/include/net/af_unix.h
index cab9dfb666f3..54d62467a70b 100644
--- a/include/net/af_unix.h
+++ b/include/net/af_unix.h

@@ -23,6 +23,8 @@ extern unsigned int unix_tot_inflight;
 void unix_inflight(struct user_struct *user, struct file *fp);
 void unix_notinflight(struct user_struct *user, struct file *fp);
 void unix_init_vertex(struct unix_sock *u);
+void unix_add_edges(struct scm_fp_list *fpl, struct unix_sock *receiver);
+void unix_del_edges(struct scm_fp_list *fpl);
 int unix_alloc_edges(struct scm_fp_list *fpl);
 void unix_free_edges(struct scm_fp_list *fpl);
 void unix_gc(void);

diff --git a/include/net/scm.h b/include/net/scm.h
index a1142dee086c..7d807fe466a3 100644
--- a/include/net/scm.h
+++ b/include/net/scm.h

@@ -32,6 +32,7 @@ struct scm_fp_list {
 	short			count_unix;
 	short			max;
 #ifdef CONFIG_UNIX
+	bool			inflight;
 	struct unix_edge	*edges;
 #endif
 	struct user_struct	*user;

diff --git a/net/core/scm.c b/net/core/scm.c
index 8661524ed6e5..d141c00eb116 100644
--- a/net/core/scm.c
+++ b/net/core/scm.c

@@ -87,6 +87,7 @@ static int scm_fp_copy(struct cmsghdr *cmsg, struct scm_fp_list **fplp)
 		*fplp = fpl;
 		fpl->count = 0;
 		fpl->count_unix = 0;
+		fpl->inflight = false;
 		fpl->edges = NULL;
 		fpl->max = SCM_MAX_FD;
 		fpl->user = NULL;

@@ -378,6 +379,7 @@ struct scm_fp_list *scm_fp_dup(struct scm_fp_list *fpl)
 		for (i = 0; i < fpl->count; i++)
 			get_file(fpl->fp[i]);
 
+		new_fpl->inflight = false;
 		new_fpl->edges = NULL;
 		new_fpl->max = new_fpl->count;
 		new_fpl->user = get_uid(fpl->user);

diff --git a/net/unix/af_unix.c b/net/unix/af_unix.c
index 0391f66546a6..ea7bac18a781 100644
--- a/net/unix/af_unix.c
+++ b/net/unix/af_unix.c

@@ -1956,8 +1956,10 @@ static void scm_stat_add(struct sock *sk, struct sk_buff *skb)
 	struct scm_fp_list *fp = UNIXCB(skb).fp;
 	struct unix_sock *u = unix_sk(sk);
 
-	if (unlikely(fp && fp->count))
+	if (unlikely(fp && fp->count)) {
 		atomic_add(fp->count, &u->scm_stat.nr_fds);
+		unix_add_edges(fp, u);
+	}
 }
 
 static void scm_stat_del(struct sock *sk, struct sk_buff *skb)

@@ -1965,8 +1967,10 @@ static void scm_stat_del(struct sock *sk, struct sk_buff *skb)
 	struct scm_fp_list *fp = UNIXCB(skb).fp;
 	struct unix_sock *u = unix_sk(sk);
 
-	if (unlikely(fp && fp->count))
+	if (unlikely(fp && fp->count)) {
 		atomic_sub(fp->count, &u->scm_stat.nr_fds);
+		unix_del_edges(fp);
+	}
 }
 
 /*

diff --git a/net/unix/garbage.c b/net/unix/garbage.c
index 6a3572e43b9f..572ac0994c69 100644
--- a/net/unix/garbage.c
+++ b/net/unix/garbage.c

@@ -110,6 +110,58 @@ void unix_init_vertex(struct unix_sock *u)
 	INIT_LIST_HEAD(&vertex->entry);
 }
 
+DEFINE_SPINLOCK(unix_gc_lock);
+static LIST_HEAD(unix_unvisited_vertices);
+
+void unix_add_edges(struct scm_fp_list *fpl, struct unix_sock *receiver)
+{
+	int i = 0, j = 0;
+
+	spin_lock(&unix_gc_lock);
+
+	while (i < fpl->count_unix) {
+		struct unix_sock *inflight = unix_get_socket(fpl->fp[j++]);
+		struct unix_edge *edge;
+
+		if (!inflight)
+			continue;
+
+		edge = fpl->edges + i++;
+		edge->predecessor = &inflight->vertex;
+		edge->successor = &receiver->vertex;
+
+		if (!edge->predecessor->out_degree++)
+			list_add_tail(&edge->predecessor->entry, &unix_unvisited_vertices);
+
+		INIT_LIST_HEAD(&edge->entry);