diff --git a/sys/kern/uipc_usrreq.c b/sys/kern/uipc_usrreq.c
index 302dcb0ed1c2..c0efca124ccd 100644
--- a/sys/kern/uipc_usrreq.c
+++ b/sys/kern/uipc_usrreq.c
@@ -2215,6 +2215,37 @@ unp_externalize_fp(struct file *fp)
 	return (ret);
 }
 
+static void
+unp_gc_scan(struct unpcb *unp, void (*op)(struct filedescent **, int))
+{
+	struct socket *so, *soa;
+
+	so = unp->unp_socket;
+	SOCK_LOCK(so);
+	if (SOLISTENING(so)) {
+		/*
+		 * Mark all sockets in our accept queue.
+		 */
+		TAILQ_FOREACH(soa, &so->sol_comp, so_list) {
+			if (sotounpcb(soa)->unp_gcflag & UNPGC_IGNORE_RIGHTS)
+				continue;
+			SOCKBUF_LOCK(&soa->so_rcv);
+			unp_scan(soa->so_rcv.sb_mb, op);
+			SOCKBUF_UNLOCK(&soa->so_rcv);
+		}
+	} else {
+		/*
+		 * Mark all sockets we reference with RIGHTS.
+		 */
+		if ((unp->unp_gcflag & UNPGC_IGNORE_RIGHTS) == 0) {
+			SOCKBUF_LOCK(&so->so_rcv);
+			unp_scan(so->so_rcv.sb_mb, op);
+			SOCKBUF_UNLOCK(&so->so_rcv);
+		}
+	}
+	SOCK_UNLOCK(so);
+}
+
 /*
  * unp_defer indicates whether additional work has been defered for a future
  * pass through unp_gc().  It is thread local and does not require explicit
@@ -2223,8 +2254,21 @@ unp_externalize_fp(struct file *fp)
 static int	unp_marked;
 static int	unp_unreachable;
 
+/*
+ * The cycle detection algorithm may only operate on sockets that have been
+ * marked as UNPGC_DEAD at the start of unp_gc(). However, the UNPGC_DEAD flag
+ * is cleared if it turns out the socket is not in a cycle after all. In
+ * this case there is the UNPGC_SCANNED flag set, though. This is the reason
+ * unp_decrease_msgcount/unp_increase_msgcount check for (UNPGC_DEAD |
+ * UNPGC_SCANNED).
+ */
+
+#ifdef INVARIANTS
+static int msgcount_changed;
+#endif
+
 static void
-unp_accessable(struct filedescent **fdep, int fdcount)
+unp_decrease_msgcount(struct filedescent **fdep, int fdcount)
 {
 	struct unpcb *unp;
 	struct file *fp;
@@ -2234,10 +2278,32 @@ unp_accessable(struct filedescent **fdep, int fdcount)
 		fp = fdep[i]->fde_file;
 		if ((unp = fptounp(fp)) == NULL)
 			continue;
-		if (unp->unp_gcflag & UNPGC_REF)
+		if (!(unp->unp_gcflag & (UNPGC_DEAD | UNPGC_SCANNED)))
 			continue;
-		unp->unp_gcflag &= ~UNPGC_DEAD;
-		unp->unp_gcflag |= UNPGC_REF;
+		unp->unp_msgcount--;
+#ifdef INVARIANTS
+		msgcount_changed--;
+#endif
+	}
+}
+
+static void
+unp_increase_msgcount(struct filedescent **fdep, int fdcount)
+{
+	struct unpcb *unp;
+	struct file *fp;
+	int i;
+
+	for (i = 0; i < fdcount; i++) {
+		fp = fdep[i]->fde_file;
+		if ((unp = fptounp(fp)) == NULL)
+			continue;
+		if (!(unp->unp_gcflag & (UNPGC_DEAD | UNPGC_SCANNED)))
+			continue;
+		unp->unp_msgcount++;
+#ifdef INVARIANTS
+		msgcount_changed++;
+#endif
 		unp_marked++;
 	}
 }
@@ -2245,51 +2311,22 @@ unp_accessable(struct filedescent **fdep, int fdcount)
 static void
 unp_gc_process(struct unpcb *unp)
 {
-	struct socket *so, *soa;
-	struct file *fp;
+
+	/* Not potentially in a cycle. Nothing to do. */
+	if (!(unp->unp_gcflag & UNPGC_DEAD))
+		return;
 
 	/* Already processed. */
 	if (unp->unp_gcflag & UNPGC_SCANNED)
 		return;
-	fp = unp->unp_file;
 
-	/*
-	 * Check for a socket potentially in a cycle.  It must be in a
-	 * queue as indicated by msgcount, and this must equal the file
-	 * reference count.  Note that when msgcount is 0 the file is NULL.
-	 */
-	if ((unp->unp_gcflag & UNPGC_REF) == 0 && fp &&
-	    unp->unp_msgcount != 0 && fp->f_count == unp->unp_msgcount) {
-		unp->unp_gcflag |= UNPGC_DEAD;
-		unp_unreachable++;
-		return;
-	}
+	unp->unp_gcflag |= UNPGC_SCANNED;
 
-	so = unp->unp_socket;
-	SOCK_LOCK(so);
-	if (SOLISTENING(so)) {
-		/*
-		 * Mark all sockets in our accept queue.
-		 */
-		TAILQ_FOREACH(soa, &so->sol_comp, so_list) {
-			if (sotounpcb(soa)->unp_gcflag & UNPGC_IGNORE_RIGHTS)
-				continue;
-			SOCKBUF_LOCK(&soa->so_rcv);
-			unp_scan(soa->so_rcv.sb_mb, unp_accessable);
-			SOCKBUF_UNLOCK(&soa->so_rcv);
-		}
-	} else {
-		/*
-		 * Mark all sockets we reference with RIGHTS.
-		 */
-		if ((unp->unp_gcflag & UNPGC_IGNORE_RIGHTS) == 0) {
-			SOCKBUF_LOCK(&so->so_rcv);
-			unp_scan(so->so_rcv.sb_mb, unp_accessable);
-			SOCKBUF_UNLOCK(&so->so_rcv);
-		}
+	if (unp->unp_msgcount > 0) {
+		unp->unp_gcflag &= ~UNPGC_DEAD;
+		unp_unreachable--;
+		unp_gc_scan(unp, unp_increase_msgcount);
 	}
-	SOCK_UNLOCK(so);
-	unp->unp_gcflag |= UNPGC_SCANNED;
 }
 
 static int unp_recycled;
@@ -2321,34 +2358,80 @@ unp_gc(__unused void *arg, int pending)
 			unp->unp_gcflag =
 			    (unp->unp_gcflag & UNPGC_IGNORE_RIGHTS);
 
+	unp_unreachable = 0;
+
+	for (head = heads; *head != NULL; head++)
+		LIST_FOREACH(unp, *head, unp_link) {
+			struct file *fp;
+
+			fp = unp->unp_file;
+
+			/*
+			 * Check for a socket potentially in a cycle.  It must
+			 * be in a queue as indicated by msgcount, and this
+			 * must equal the file reference count.  Note that when
+			 * msgcount is 0 the file is NULL.
+			 */
+			if (fp && unp->unp_msgcount != 0 &&
+			    fp->f_count == unp->unp_msgcount) {
+				unp->unp_gcflag |= UNPGC_DEAD;
+				++unp_unreachable;
+			}
+		}
+
+	/* Only one potentially unreachable socket cannot form a cycle. */
+	if (unp_unreachable <= 1) {
+		UNP_LINK_RUNLOCK();
+		return;
+	}
+
+	for (head = heads; *head != NULL; head++)
+		LIST_FOREACH(unp, *head, unp_link) {
+			if (unp->unp_gcflag & UNPGC_DEAD) {
+				unp_gc_scan(unp, unp_decrease_msgcount);
+			}
+		}
+
 	/*
-	 * Scan marking all reachable sockets with UNPGC_REF.  Once a socket
-	 * is reachable all of the sockets it references are reachable.
+	 * If a socket still has a non-negative msgcount it cannot be in a
+	 * cycle. In this case increment msgcount of all children iteratively.
 	 * Stop the scan once we do a complete loop without discovering
 	 * a new reachable socket.
 	 */
 	do {
-		unp_unreachable = 0;
 		unp_marked = 0;
 		for (head = heads; *head != NULL; head++)
 			LIST_FOREACH(unp, *head, unp_link)
 				unp_gc_process(unp);
 	} while (unp_marked);
-	UNP_LINK_RUNLOCK();
-	if (unp_unreachable == 0)
-		return;
+
+	/*
+	 * Sockets that still have the UNPGC_DEAD flag set are unreachable.
+	 * Restore msgcount of their children, too, so that no msgcount field
+	 * is changed by the algorithm.
+	 */
+	for (head = heads; *head != NULL; head++)
+		LIST_FOREACH(unp, *head, unp_link) {
+			if (unp->unp_gcflag & UNPGC_DEAD) {
+				unp_gc_scan(unp, unp_increase_msgcount);
+			}
+		}
+
+	KASSERT(msgcount_changed == 0,
+	    ("unp_gc: msgcount fields must not be changed"));
 
 	/*
 	 * Allocate space for a local list of dead unpcbs.
+	 * unp_unreachable is the number of sockets that have
+	 * the UNPGC_DEAD flag set.
 	 */
 	unref = malloc(unp_unreachable * sizeof(struct file *),
 	    M_TEMP, M_WAITOK);
 
 	/*
 	 * Iterate looking for sockets which have been specifically marked
-	 * as as unreachable and store them locally.
+	 * as unreachable and store them locally.
 	 */
-	UNP_LINK_RLOCK();
 	for (total = 0, head = heads; *head != NULL; head++)
 		LIST_FOREACH(unp, *head, unp_link)
 			if ((unp->unp_gcflag & UNPGC_DEAD) != 0) {
diff --git a/sys/sys/unpcb.h b/sys/sys/unpcb.h
index b348a889b2c2..48587b3accf0 100644
--- a/sys/sys/unpcb.h
+++ b/sys/sys/unpcb.h
@@ -111,10 +111,9 @@ struct unpcb {
 /*
  * Flags in unp_gcflag.
  */
-#define	UNPGC_REF			0x1	/* unpcb has external ref. */
-#define	UNPGC_DEAD			0x2	/* unpcb might be dead. */
-#define	UNPGC_SCANNED			0x4	/* Has been scanned. */
-#define	UNPGC_IGNORE_RIGHTS		0x8	/* Attached rights are freed */
+#define	UNPGC_DEAD			0x1	/* unpcb might be dead. */
+#define	UNPGC_SCANNED			0x2	/* Has been scanned. */
+#define	UNPGC_IGNORE_RIGHTS		0x4	/* Attached rights are freed */
 
 #define	sotounpcb(so)	((struct unpcb *)((so)->so_pcb))