Attachment 192515 Details for Bug 227285 – patch for a GC that detects cycles

[patch] patch for a GC that detects cycles

unp-gc-cycle-detection.patch (text/plain), 7.51 KB, created by Jan Kokemüller on 2018-04-14 19:59:37 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Jan Kokemüller

Created: 2018-04-14 19:59:37 UTC

Size: 7.51 KB

patch

obsolete

>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))
>

Actions: View | Diff

Attachments on bug 227285: 192211 | 192213 | 192214 | 192216 | 192350 | 192514 | 192515