dummynet: fix wf2q use-after-free

When we clean up a wf2q+ queue we need to ensure that we remove it from
the correct heap. If we leave a queue pointer behind in an unexpected
heap we'll later write to it, causing a use-after-free and unpredictable
panics.

Teach the dummynet heap code to verify that we're removing the correct
object so we can safely attempt to remove objects not contained in the
heap.

Remove a to-be-removed queue from all heaps.

Also don't continue the enqueue function if we're not finding the queue
on the idle heap as we'd expect.

While here also remove the empty heap warning, because this is now
expected to happen.

See also:	https://redmine.pfsense.org/issues/14433
Sponsored by:	Rubicon Communications, LLC ("Netgate")

3 files changed, 18 insertions, 16 deletions

diff --git a/sys/netpfil/ipfw/dn_heap.c b/sys/netpfil/ipfw/dn_heap.c
index d1c386e48697..bc6b9c142dc2 100644
--- a/sys/netpfil/ipfw/dn_heap.c
+++ b/sys/netpfil/ipfw/dn_heap.c
@@ -178,14 +178,13 @@ heap_insert(struct dn_heap *h, uint64_t key1, void *p)
 /*
  * remove top element from heap, or obj if obj != NULL
  */
-void
+bool
 heap_extract(struct dn_heap *h, void *obj)
 {
 	int child, father, max = h->elements - 1;
 
 	if (max < 0) {
-		printf("--- %s: empty heap 0x%p\n", __FUNCTION__, h);
-		return;
+		return false;
 	}
 	if (obj == NULL)
 		father = 0; /* default: move up smallest child */
@@ -194,11 +193,14 @@ heap_extract(struct dn_heap *h, void *obj)
 			panic("%s: extract from middle not set on %p\n",
 				__FUNCTION__, h);
 		father = *((int *)((char *)obj + h->ofs));
-		if (father < 0 || father >= h->elements) {
-			panic("%s: father %d out of bound 0..%d\n",
-				__FUNCTION__, father, h->elements);
-		}
+		if (father < 0 || father >= h->elements)
+			return false;
 	}
+	/* We should make sure that the object we're trying to remove is
+	 * actually in this heap. */
+	if (obj != NULL && h->p[father].object != obj)
+		return false;
+
 	/*
 	 * below, father is the index of the empty element, which
 	 * we replace at each step with the smallest child until we
@@ -223,6 +225,8 @@ heap_extract(struct dn_heap *h, void *obj)
 		h->p[father] = h->p[max];
 		heap_insert(h, father, NULL);
 	}
+
+	return true;
 }
 
 #if 0
diff --git a/sys/netpfil/ipfw/dn_heap.h b/sys/netpfil/ipfw/dn_heap.h
index f50ffdef33eb..4ae1c1cb8750 100644
--- a/sys/netpfil/ipfw/dn_heap.h
+++ b/sys/netpfil/ipfw/dn_heap.h
@@ -102,7 +102,7 @@ enum {
 #define SET_HEAP_OFS(h, n)	do { (h)->ofs = n; } while (0)
 int     heap_init(struct dn_heap *h, int size, int ofs);
 int     heap_insert(struct dn_heap *h, uint64_t key1, void *p);
-void    heap_extract(struct dn_heap *h, void *obj);
+bool    heap_extract(struct dn_heap *h, void *obj);
 void heap_free(struct dn_heap *h);
 int heap_scan(struct dn_heap *, int (*)(void *, uintptr_t), uintptr_t);
 
diff --git a/sys/netpfil/ipfw/dn_sched_wf2q.c b/sys/netpfil/ipfw/dn_sched_wf2q.c
index 7f81c0a098f1..5b69eb083d7f 100644
--- a/sys/netpfil/ipfw/dn_sched_wf2q.c
+++ b/sys/netpfil/ipfw/dn_sched_wf2q.c
@@ -157,7 +157,8 @@ wf2qp_enqueue(struct dn_sch_inst *_si, struct dn_queue *q, struct mbuf *m)
         si->wsum += fs->fs.par[0];	/* add weight of new queue. */
 	si->inv_wsum = ONE_FP/si->wsum;
     } else { /* if it was idle then it was in the idle heap */
-        heap_extract(&si->idle_heap, q);
+        if (! heap_extract(&si->idle_heap, q))
+		return 1;
         alg_fq->S = MAX64(alg_fq->F, si->V);	/* compute new S */
     }
     alg_fq->F = alg_fq->S + len * alg_fq->inv_w;
@@ -338,13 +339,10 @@ wf2qp_free_queue(struct dn_queue *q)
 	/* extract from the heap. XXX TODO we may need to adjust V
 	 * to make sure the invariants hold.
 	 */
-	if (q->mq.head == NULL) {
-		heap_extract(&si->idle_heap, q);
-	} else if (DN_KEY_LT(si->V, alg_fq->S)) {
-		heap_extract(&si->ne_heap, q);
-	} else {
-		heap_extract(&si->sch_heap, q);
-	}
+	heap_extract(&si->idle_heap, q);
+	heap_extract(&si->ne_heap, q);
+	heap_extract(&si->sch_heap, q);
+
 	return 0;
 }