Re: RFC: PERCPU_LIST to fix PR kern/52515

[Taylor R Campbell <campbell+netbsd-tech-kern%mumble.net@localhost>]

> Date: Thu, 7 Dec 2017 05:21:58 +0000
> From: Taylor R Campbell <campbell+netbsd-tech-kern%mumble.net@localhost>
> 
> I dropped this thread on the floor a while ago and I forget what the
> status was.  I've had a patch sitting in my tree for a while which I
> brushed off to put the list update logic in separate functions, as I
> think chuq requested a while ago, but still keep it all isolated to
> subr_psref.c and avoid defining any new macros.

...One of these days, I will teach the computer to remind me when I
didn't attach the patch I mentioned.

Index: sys/kern/subr_psref.c
===================================================================
RCS file: /cvsroot/src/sys/kern/subr_psref.c,v
retrieving revision 1.7
diff -p -u -r1.7 subr_psref.c
--- sys/kern/subr_psref.c	1 Jun 2017 02:45:13 -0000	1.7
+++ sys/kern/subr_psref.c	7 Dec 2017 05:12:44 -0000
@@ -78,12 +78,129 @@ __KERNEL_RCSID(0, "$NetBSD: subr_psref.c
 #include <sys/queue.h>
 #include <sys/xcall.h>
 
-LIST_HEAD(psref_head, psref);
-
 static bool	_psref_held(const struct psref_target *, struct psref_class *,
 		    bool);
 
 /*
+ * struct psref_head
+ *
+ *	Head of a list of psrefs.
+ *
+ *	We use a custom list data structure here in which the first
+ *	element of the list has a null prevp, instead of a prevp
+ *	pointing at the list head.  We must do this because the list
+ *	head can migrate in memory due to percpu_alloc.
+ *
+ *	Avoiding the back-pointer into the head further requires
+ *	passing the head to psref_list_remove.  We can't use _any_ of
+ *	the existing LIST_* because we can't distinguish which prevp
+ *	points at the head with them.  So we can't even partly use the
+ *	LIST_* macros with a kludge.
+ *
+ *	This structure is of limited utility, so it is restricted to
+ *	this file for now.
+ */
+struct psref_head {
+	struct psref	*prh_first;
+};
+
+/*
+ * PSREF_LIST_FOREACH(psref, head)
+ *
+ *	Loop header for iterating over the list of psrefs starting at
+ *	head.
+ */
+#define	PSREF_LIST_FOREACH(PSREF, HEAD)					      \
+	for ((PSREF) = (HEAD)->prh_first;				      \
+	     (PSREF) != NULL;						      \
+	     (PSREF) = (PSREF)->psref_next)
+
+/*
+ * psref_list_empty(head)
+ *
+ *	True iff the list of psrefs starting at head is empty.
+ */
+static inline bool
+psref_list_empty(const struct psref_head *head)
+{
+
+	return head->prh_first == NULL;
+}
+
+/*
+ * psref_list_insert_head(head, psref)
+ *
+ *	Insert psref at the front of the list starting at head.
+ */
+static inline void
+psref_list_insert_head(struct psref_head *head, struct psref *psref)
+{
+
+	KASSERTMSG((head->prh_first == NULL ||
+		head->prh_first->psref_prevp == NULL),
+	    "psref_head %p [cpu%d] psref %p prevp is %p, not null",
+	    head, cpu_index(curcpu()), head->prh_first,
+	    head->prh_first->psref_prevp);
+
+	/*
+	 * Set the next element of our new element to whatever the
+	 * first element is, if there is one, and if there is one, set
+	 * its previous pointer to point at our new element.
+	 */
+	if ((psref->psref_next = head->prh_first) != NULL)
+		psref->psref_next->psref_prevp = &psref->psref_next;
+
+	/* Mark the new element as the first in the list.  */
+	psref->psref_prevp = NULL;
+
+	/* Publish.  */
+	head->prh_first = psref;
+}
+
+/*
+ * psref_list_remove(head, psref)
+ *
+ *	Remove psref from the list it is on, which must start at head.
+ */
+static inline void
+psref_list_remove(struct psref_head *head, struct psref *psref)
+{
+
+	/*
+	 * Either the previous pointer, if there is one, or the list
+	 * head, if there isn't because we're at the head of the list,
+	 * had better point at this psref.  If this is not at the head
+	 * of the list, the head of the list had better *not* point at
+	 * this psref.
+	 */
+	KASSERTMSG(psref->psref_prevp == NULL || *psref->psref_prevp == psref,
+	    "psref %p prevp %p points at %p",
+	    psref, psref->psref_prevp, *psref->psref_prevp);
+	KASSERTMSG((psref->psref_prevp == NULL) == (head->prh_first == psref),
+	    "psref %p prevp %p psref_head %p [cpu%d] first is %p",
+	    psref, psref->psref_prevp, head, cpu_index(curcpu()),
+	    head->prh_first);
+
+	/* If there is a next element, set its previous pointer to ours.  */
+	if (psref->psref_next != NULL)
+		psref->psref_next->psref_prevp = psref->psref_prevp;
+
+	/*
+	 * If it's at the head of the list, we must modify the head
+	 * explicitly.  We can't have psref->psref_prevp be a
+	 * back-pointer into the head because percpu_alloc may move the
+	 * per-CPU objects around in memory, which would invalidate
+	 * that back-pointer.
+	 */
+	if (psref->psref_prevp == NULL)
+		head->prh_first = psref->psref_next;
+
+	/* Paranoia: poison this element so it can no longer be used.  */
+	psref->psref_prevp = (void *)1; /* poison */
+	psref->psref_next = (void *)2;	/* poison */
+}
+
+/*
  * struct psref_class
  *
  *	Private global state for a class of passive reference targets.
@@ -135,7 +252,7 @@ psref_cpu_drained_p(void *p, void *cooki
 	const struct psref_cpu *pcpu = p;
 	bool *retp = cookie;
 
-	if (!LIST_EMPTY(&pcpu->pcpu_head))
+	if (!psref_list_empty(&pcpu->pcpu_head))
 		*retp = false;
 }
 
@@ -194,7 +311,7 @@ psref_check_duplication(struct psref_cpu
 	bool found = false;
 	struct psref *_psref;
 
-	LIST_FOREACH(_psref, &pcpu->pcpu_head, psref_entry) {
+	PSREF_LIST_FOREACH(_psref, &pcpu->pcpu_head) {
 		if (_psref == psref &&
 		    _psref->psref_target == target) {
 			found = true;
@@ -250,7 +367,7 @@ psref_acquire(struct psref *psref, const
 #endif
 
 	/* Record our reference.  */
-	LIST_INSERT_HEAD(&pcpu->pcpu_head, psref, psref_entry);
+	psref_list_insert_head(&pcpu->pcpu_head, psref);
 	psref->psref_target = target;
 	psref->psref_lwp = curlwp;
 	psref->psref_cpu = curcpu();
@@ -273,6 +390,7 @@ void
 psref_release(struct psref *psref, const struct psref_target *target,
     struct psref_class *class)
 {
+	struct psref_cpu *pcpu;
 	int s;
 
 	KASSERTMSG((kpreempt_disabled() || cpu_softintr_p() ||
@@ -297,12 +415,12 @@ psref_release(struct psref *psref, const
 
 	/*
 	 * Block interrupts and remove the psref from the current CPU's
-	 * list.  No need to percpu_getref or get the head of the list,
-	 * and the caller guarantees that we are bound to a CPU anyway
-	 * (as does blocking interrupts).
+	 * list.
 	 */
 	s = splraiseipl(class->prc_iplcookie);
-	LIST_REMOVE(psref, psref_entry);
+	pcpu = percpu_getref(class->prc_percpu);
+	psref_list_remove(&pcpu->pcpu_head, psref);
+	percpu_putref(class->prc_percpu);
 	splx(s);
 
 	/* If someone is waiting for users to drain, notify 'em.  */
@@ -353,7 +471,7 @@ psref_copy(struct psref *pto, const stru
 	pcpu = percpu_getref(class->prc_percpu);
 
 	/* Record the new reference.  */
-	LIST_INSERT_HEAD(&pcpu->pcpu_head, pto, psref_entry);
+	psref_list_insert_head(&pcpu->pcpu_head, pto);
 	pto->psref_target = pfrom->psref_target;
 	pto->psref_lwp = curlwp;
 	pto->psref_cpu = curcpu();
@@ -474,7 +592,7 @@ _psref_held(const struct psref_target *t
 	pcpu = percpu_getref(class->prc_percpu);
 
 	/* Search through all the references on this CPU.  */
-	LIST_FOREACH(psref, &pcpu->pcpu_head, psref_entry) {
+	PSREF_LIST_FOREACH(psref, &pcpu->pcpu_head) {
 		/* Sanity-check the reference's CPU.  */
 		KASSERTMSG((psref->psref_cpu == curcpu()),
 		    "passive reference transferred from CPU %u to CPU %u",
Index: sys/sys/psref.h
===================================================================
RCS file: /cvsroot/src/sys/sys/psref.h,v
retrieving revision 1.2
diff -p -u -r1.2 psref.h
--- sys/sys/psref.h	16 Dec 2016 20:12:11 -0000	1.2
+++ sys/sys/psref.h	7 Dec 2017 05:12:44 -0000
@@ -69,7 +69,8 @@ struct psref_target {
  *	written only on the local CPU.
  */
 struct psref {
-	LIST_ENTRY(psref)		psref_entry;
+	struct psref			*psref_next;
+	struct psref			**psref_prevp;
 	const struct psref_target	*psref_target;
 	struct lwp			*psref_lwp;
 	struct cpu_info			*psref_cpu;