untrusted comment: signature from openbsd 5.6 base private key
RWR0EANmo9nqhm+ggK98I1rvCSdAAAuoh2w1cAW9PShdW52IqAaM+ogTfSbujjQHeJknhwld7EWu105QrmO3qtPlpSZCEpik9g4=

OpenBSD 5.6 errata 13, Dec 10, 2014:

Missing memory barriers in virtio(4) can lead to hangs with virtio devices,
like vio(4) and vioblk(4).

Apply patch using:
    
    signify -Vep /etc/signify/openbsd-56-base.pub -x 013_virtio.patch.sig -m - | \
        (cd /usr/src && patch -p0)

Then build and install a new kernel:

    cd /usr/src/sys/arch/`machine`/conf
    KK=`sysctl -n kern.osversion | cut -d# -f1`
    config $KK
    cd ../compile/$KK
    make
    make install

Index: sys/dev/pci/virtio.c
===================================================================
RCS file: /cvs/src/sys/dev/pci/virtio.c,v
retrieving revision 1.9
retrieving revision 1.9.4.1
diff -u -p -r1.9 -r1.9.4.1
--- sys/dev/pci/virtio.c	13 Jul 2014 23:10:23 -0000	1.9
+++ sys/dev/pci/virtio.c	9 Dec 2014 12:54:26 -0000	1.9.4.1
@@ -657,6 +657,8 @@ publish_avail_idx(struct virtio_softc *s
 {
 	vq_sync_aring(sc, vq, BUS_DMASYNC_PREWRITE);
 	vq_sync_uring(sc, vq, BUS_DMASYNC_PREREAD);
+
+	virtio_membar_producer();
 	vq->vq_avail->idx = vq->vq_avail_idx;
 	vq_sync_aring(sc, vq, BUS_DMASYNC_POSTWRITE);
 	vq->vq_queued = 1;
@@ -687,11 +689,15 @@ notify:
 			uint16_t n = vq->vq_avail_idx;
 			uint16_t t;
 			publish_avail_idx(sc, vq);
+
+			virtio_membar_sync();
 			t = VQ_AVAIL_EVENT(vq) + 1;
 			if ((uint16_t)(n - t) < (uint16_t)(n - o))
 				sc->sc_ops->kick(sc, vq->vq_index);
 		} else {
 			publish_avail_idx(sc, vq);
+
+			virtio_membar_sync();
 			if (!(vq->vq_used->flags & VRING_USED_F_NO_NOTIFY))
 				sc->sc_ops->kick(sc, vq->vq_index);
 		}
@@ -744,6 +750,8 @@ virtio_dequeue(struct virtio_softc *sc, 
 		return ENOENT;
 	usedidx = vq->vq_used_idx++;
 	usedidx &= vq->vq_mask;
+
+	virtio_membar_consumer();
 	slot = vq->vq_used->ring[usedidx].id;
 	qe = &vq->vq_entries[slot];
 
@@ -794,6 +802,7 @@ virtio_postpone_intr(struct virtqueue *v
 
 	/* set the new event index: avail_ring->used_event = idx */
 	VQ_USED_EVENT(vq) = idx;
+	virtio_membar_sync();
 
 	vq_sync_aring(vq->vq_owner, vq, BUS_DMASYNC_PREWRITE);
 	vq->vq_queued++;
@@ -867,6 +876,8 @@ virtio_start_vq_intr(struct virtio_softc
 		VQ_USED_EVENT(vq) = vq->vq_used_idx;
 	else
 		vq->vq_avail->flags &= ~VRING_AVAIL_F_NO_INTERRUPT;
+
+	virtio_membar_sync();
 
 	vq_sync_aring(sc, vq, BUS_DMASYNC_PREWRITE);
 	vq->vq_queued++;
Index: sys/arch/i386/include/atomic.h
===================================================================
RCS file: /cvs/src/sys/arch/i386/include/atomic.h,v
retrieving revision 1.12
retrieving revision 1.12.4.1
diff -u -p -r1.12 -r1.12.4.1
--- sys/arch/i386/include/atomic.h	29 Mar 2014 18:09:29 -0000	1.12
+++ sys/arch/i386/include/atomic.h	9 Dec 2014 12:53:03 -0000	1.12.4.1
@@ -49,6 +49,13 @@
 #else
 #define LOCK
 #endif
+
+#define __membar(_f) do { __asm __volatile(_f ::: "memory"); } while (0)
+
+/* virtio needs MP membars even on SP kernels */
+#define virtio_membar_producer()	__membar("")
+#define virtio_membar_consumer()	__membar("")
+#define virtio_membar_sync()		__membar("lock; addl $0,0(%%esp)")
 
 static __inline u_int64_t
 i386_atomic_testset_uq(volatile u_int64_t *ptr, u_int64_t val)
Index: sys/arch/amd64/include/atomic.h
===================================================================
RCS file: /cvs/src/sys/arch/amd64/include/atomic.h,v
retrieving revision 1.13
retrieving revision 1.13.4.1
diff -u -p -r1.13 -r1.13.4.1
--- sys/arch/amd64/include/atomic.h	18 Jul 2014 10:40:14 -0000	1.13
+++ sys/arch/amd64/include/atomic.h	9 Dec 2014 12:53:03 -0000	1.13.4.1
@@ -54,6 +54,13 @@
 #else
 #define LOCK
 #endif
+
+#define __membar(_f) do { __asm __volatile(_f ::: "memory"); } while (0)
+
+/* virtio needs MP membars even on SP kernels */
+#define virtio_membar_producer()	__membar("")
+#define virtio_membar_consumer()	__membar("")
+#define virtio_membar_sync()		__membar("mfence")
 
 static inline unsigned int
 _atomic_cas_uint(volatile unsigned int *p, unsigned int e, unsigned int n)