From c07e60250f500a143a8d4184edebc6b777f731ee Mon Sep 17 00:00:00 2001
From: sf <sf@openbsd.org>
Date: Tue, 30 May 2017 08:35:32 +0000
Subject: [PATCH] virtio: Do LIFO in the freelist

Use a SLIST instead of a SIMPLEQ and use LIFO instead of FIFO. This should
improve cache usage.
---
 sys/dev/pv/virtio.c    | 18 +++++++++---------
 sys/dev/pv/virtiovar.h |  6 +++---
 2 files changed, 12 insertions(+), 12 deletions(-)

diff --git a/sys/dev/pv/virtio.c b/sys/dev/pv/virtio.c
index cddeb9d146a..8d1fb468933 100644
--- a/sys/dev/pv/virtio.c
+++ b/sys/dev/pv/virtio.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: virtio.c,v 1.5 2017/05/27 10:24:31 sf Exp $	*/
+/*	$OpenBSD: virtio.c,v 1.6 2017/05/30 08:35:32 sf Exp $	*/
 /*	$NetBSD: virtio.c,v 1.3 2011/11/02 23:05:52 njoly Exp $	*/
 
 /*
@@ -256,10 +256,10 @@ virtio_init_vq(struct virtio_softc *sc, struct virtqueue *vq, int reinit)
 	}
 
 	/* free slot management */
-	SIMPLEQ_INIT(&vq->vq_freelist);
+	SLIST_INIT(&vq->vq_freelist);
 	for (i = 0; i < vq_size; i++) {
-		SIMPLEQ_INSERT_TAIL(&vq->vq_freelist,
-				    &vq->vq_entries[i], qe_list);
+		SLIST_INSERT_HEAD(&vq->vq_freelist, &vq->vq_entries[i],
+		    qe_list);
 		vq->vq_entries[i].qe_index = i;
 	}
 
@@ -405,7 +405,7 @@ virtio_free_vq(struct virtio_softc *sc, struct virtqueue *vq)
 
 	/* device must be already deactivated */
 	/* confirm the vq is empty */
-	SIMPLEQ_FOREACH(qe, &vq->vq_freelist, qe_list) {
+	SLIST_FOREACH(qe, &vq->vq_freelist, qe_list) {
 		i++;
 	}
 	if (i != vq->vq_num) {
@@ -435,10 +435,10 @@ vq_alloc_entry(struct virtqueue *vq)
 {
 	struct vq_entry *qe;
 
-	if (SIMPLEQ_EMPTY(&vq->vq_freelist))
+	if (SLIST_EMPTY(&vq->vq_freelist))
 		return NULL;
-	qe = SIMPLEQ_FIRST(&vq->vq_freelist);
-	SIMPLEQ_REMOVE_HEAD(&vq->vq_freelist, qe_list);
+	qe = SLIST_FIRST(&vq->vq_freelist);
+	SLIST_REMOVE_HEAD(&vq->vq_freelist, qe_list);
 
 	return qe;
 }
@@ -446,7 +446,7 @@ vq_alloc_entry(struct virtqueue *vq)
 void
 vq_free_entry(struct virtqueue *vq, struct vq_entry *qe)
 {
-	SIMPLEQ_INSERT_TAIL(&vq->vq_freelist, qe, qe_list);
+	SLIST_INSERT_HEAD(&vq->vq_freelist, qe, qe_list);
 }
 
 /*
diff --git a/sys/dev/pv/virtiovar.h b/sys/dev/pv/virtiovar.h
index 521167060b2..9e453a145e4 100644
--- a/sys/dev/pv/virtiovar.h
+++ b/sys/dev/pv/virtiovar.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: virtiovar.h,v 1.3 2017/05/27 10:24:31 sf Exp $	*/
+/*	$OpenBSD: virtiovar.h,v 1.4 2017/05/30 08:35:32 sf Exp $	*/
 /*	$NetBSD: virtiovar.h,v 1.1 2011/10/30 12:12:21 hannken Exp $	*/
 
 /*
@@ -81,7 +81,7 @@
 #endif
 
 struct vq_entry {
-	SIMPLEQ_ENTRY(vq_entry)	qe_list; /* free list */
+	SLIST_ENTRY(vq_entry)	qe_list; /* free list */
 	uint16_t		qe_index; /* index in vq_desc array */
 	/* followings are used only when it is the `head' entry */
 	int16_t			qe_next;     /* next enq slot */
@@ -114,7 +114,7 @@ struct virtqueue {
 
 	/* free entry management */
 	struct vq_entry		*vq_entries;
-	SIMPLEQ_HEAD(, vq_entry) vq_freelist;
+	SLIST_HEAD(, vq_entry) vq_freelist;
 	struct mutex		*vq_freelist_lock;
 
 	/* enqueue/dequeue status */
-- 
2.20.1