Skip to contentSkip to conversation

virtio: put last seen used index into ring itself

PATCH In review Michael S. Tsirkin 4 participants 23 messages May 26, 2010 – Jun 2, 2010

Subsystems (4)
Network drivers KVM virtio core virtio net driver
lore
Share & tools
lore

Michael S. Tsirkin

author maintainer
#0 lore raw

cover virtio: put last seen used index into ring itself

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Generally, the Host end of the virtio ring doesn't need to see where Guest is up to in consuming the ring. However, to completely understand what's going on from the outside, this information must be exposed. For example, host can reduce the number of interrupts by detecting that the guest is currently handling previous buffers.

We add a feature bit so the guest can tell the host that it's writing out the current value there, if it wants to use that.

This differs from original approach in that the used index is put after avail index (they are typically written out together). To avoid cache bounces on descriptor access,
and make future extensions easier, we put the ring itself at start of page, and move the control after it.

Signed-off-by Michael S. Tsirkin <[email protected]>

Michael S. Tsirkin (2):
virtio: support layout with avail ring before idx
virtio: publish used idx

 drivers/net/virtio_net.c     |    2 ++
 drivers/virtio/virtio_ring.c |   19 ++++++++++++++++---
 include/linux/virtio_ring.h  |   34 ++++++++++++++++++++++++++++------
 3 files changed, 46 insertions(+), 9 deletions(-)
author maintainer
#1 lore raw

PATCH 1/2 virtio: support layout with avail ring before idx

This adds an (unused) option to put available ring before control (avail index, flags). This avoids cache line sharing between control and ring, and also
makes it possible to extend avail control without incurring extra cache misses.

Signed-off-by Michael S. Tsirkin <[email protected]>
---
 drivers/virtio/virtio_ring.c |    4 ++--
 include/linux/virtio_ring.h  |   30 ++++++++++++++++++++++++------
 2 files changed, 26 insertions(+), 8 deletions(-)
drivers/virtio/virtio_ring.c +2 -2
index 1ca8890..2241342 100644
@@ -224,7 +224,7 @@ add_head:
 	/* Put entry in available array (but don't update avail->idx until they
 	 * do sync).  FIXME: avoid modulus here? */
 	avail = (vq->vring.avail->idx + vq->num_added++) % vq->vring.num;
-	vq->vring.avail->ring[avail] = head;
+	vq->vring.avail_ring[avail] = head;
 
 	pr_debug("Added buffer head %i to %p\n", head, vq);
 	END_USE(vq);

@@ -425,7 +425,7 @@ struct virtqueue *vring_new_virtqueue(unsigned int num,
 	if (!vq)
 		return NULL;
 
-	vring_init(&vq->vring, num, pages, vring_align);
+	vring_init(&vq->vring, num, pages, vring_align, false);
 	vq->vq.callback = callback;
 	vq->vq.vdev = vdev;
 	vq->vq.name = name;
include/linux/virtio_ring.h +24 -6
index e4d144b..c5f3ee7 100644
@@ -47,6 +47,11 @@ struct vring_avail {
 	__u16 ring[];
 };
 
+struct vring_avail_ctrl {
+	__u16 flags;
+	__u16 idx;
+};
+
 /* u32 is used here for ids for padding reasons. */
 struct vring_used_elem {
 	/* Index of start of used descriptor chain. */

@@ -66,7 +71,9 @@ struct vring {
 
 	struct vring_desc *desc;
 
-	struct vring_avail *avail;
+	struct vring_avail_ctrl *avail;
+
+	__u16 *avail_ring;
 
 	struct vring_used *used;
 };

@@ -79,11 +86,18 @@ struct vring {
  *	// The actual descriptors (16 bytes each)
  *	struct vring_desc desc[num];
  *
- *	// A ring of available descriptor heads with free-running index.
+ *	// A ring of available descriptor heads with a control structure
+ *      // including a free-running index.
+ *      // The ring can come either after  (legacy) or before the control.
  *	__u16 avail_flags;
  *	__u16 avail_idx;
  *	__u16 available[num];
  *
+ * or
+ *
+ *	__u16 available[num];
+ *	__u16 avail_flags;
+ *	__u16 avail_idx;
  *	// Padding to the next align boundary.
  *	char pad[];
  *

@@ -94,13 +108,17 @@ struct vring {
  * };
  */
 static inline void vring_init(struct vring *vr, unsigned int num, void *p,
-			      unsigned long align)
+			      unsigned long align, bool avail_ring_first)
 {
+	struct vring_avail *avail = p + num * sizeof(struct vring_desc);
 	vr->num = num;
 	vr->desc = p;
-	vr->avail = p + num*sizeof(struct vring_desc);
-	vr->used = (void *)(((unsigned long)&vr->avail->ring[num] + align-1)
-			    & ~(align - 1));
+	vr->avail_ring = avail_ring_first ? (void*)avail : &avail->ring;
+	vr->avail = avail_ring_first ? (void *)&vr->avail_ring[num] : p;
+	vr->used = (void *)ALIGN((unsigned long)&avail->ring[num], align);
+	/* Verify that avail fits before used. */
+	BUG_ON((unsigned long)(vr->avail + 1) > (unsigned long)vr->used);
+	BUG_ON((unsigned long)(&vr->avail_ring[num]) > (unsigned long)vr->used);
 }
 
 static inline unsigned vring_size(unsigned int num, unsigned long align)
Signature · 1 line
1.7.1.12.g42b7f
author maintainer
#2 lore raw

PATCH 1/2 virtio: support layout with avail ring before idx

In reply to Michael S. Tsirkin

This adds an (unused) option to put available ring before control (avail index, flags). This avoids cache line sharing between control and ring, and also
makes it possible to extend avail control without incurring extra cache misses.

Signed-off-by Michael S. Tsirkin <[email protected]>
---
 drivers/virtio/virtio_ring.c |    4 ++--
 include/linux/virtio_ring.h  |   30 ++++++++++++++++++++++++------
 2 files changed, 26 insertions(+), 8 deletions(-)
drivers/virtio/virtio_ring.c +2 -2
index 1ca8890..2241342 100644
@@ -224,7 +224,7 @@ add_head:
 	/* Put entry in available array (but don't update avail->idx until they
 	 * do sync).  FIXME: avoid modulus here? */
 	avail = (vq->vring.avail->idx + vq->num_added++) % vq->vring.num;
-	vq->vring.avail->ring[avail] = head;
+	vq->vring.avail_ring[avail] = head;
 
 	pr_debug("Added buffer head %i to %p\n", head, vq);
 	END_USE(vq);

@@ -425,7 +425,7 @@ struct virtqueue *vring_new_virtqueue(unsigned int num,
 	if (!vq)
 		return NULL;
 
-	vring_init(&vq->vring, num, pages, vring_align);
+	vring_init(&vq->vring, num, pages, vring_align, false);
 	vq->vq.callback = callback;
 	vq->vq.vdev = vdev;
 	vq->vq.name = name;
include/linux/virtio_ring.h +24 -6
index e4d144b..c5f3ee7 100644
@@ -47,6 +47,11 @@ struct vring_avail {
 	__u16 ring[];
 };
 
+struct vring_avail_ctrl {
+	__u16 flags;
+	__u16 idx;
+};
+
 /* u32 is used here for ids for padding reasons. */
 struct vring_used_elem {
 	/* Index of start of used descriptor chain. */

@@ -66,7 +71,9 @@ struct vring {
 
 	struct vring_desc *desc;
 
-	struct vring_avail *avail;
+	struct vring_avail_ctrl *avail;
+
+	__u16 *avail_ring;
 
 	struct vring_used *used;
 };

@@ -79,11 +86,18 @@ struct vring {
  *	// The actual descriptors (16 bytes each)
  *	struct vring_desc desc[num];
  *
- *	// A ring of available descriptor heads with free-running index.
+ *	// A ring of available descriptor heads with a control structure
+ *      // including a free-running index.
+ *      // The ring can come either after  (legacy) or before the control.
  *	__u16 avail_flags;
  *	__u16 avail_idx;
  *	__u16 available[num];
  *
+ * or
+ *
+ *	__u16 available[num];
+ *	__u16 avail_flags;
+ *	__u16 avail_idx;
  *	// Padding to the next align boundary.
  *	char pad[];
  *

@@ -94,13 +108,17 @@ struct vring {
  * };
  */
 static inline void vring_init(struct vring *vr, unsigned int num, void *p,
-			      unsigned long align)
+			      unsigned long align, bool avail_ring_first)
 {
+	struct vring_avail *avail = p + num * sizeof(struct vring_desc);
 	vr->num = num;
 	vr->desc = p;
-	vr->avail = p + num*sizeof(struct vring_desc);
-	vr->used = (void *)(((unsigned long)&vr->avail->ring[num] + align-1)
-			    & ~(align - 1));
+	vr->avail_ring = avail_ring_first ? (void*)avail : &avail->ring;
+	vr->avail = avail_ring_first ? (void *)&vr->avail_ring[num] : p;
+	vr->used = (void *)ALIGN((unsigned long)&avail->ring[num], align);
+	/* Verify that avail fits before used. */
+	BUG_ON((unsigned long)(vr->avail + 1) > (unsigned long)vr->used);
+	BUG_ON((unsigned long)(&vr->avail_ring[num]) > (unsigned long)vr->used);
 }
 
 static inline unsigned vring_size(unsigned int num, unsigned long align)
Signature · 1 line
1.7.1.12.g42b7f
author maintainer
#3 lore raw

PATCH 2/2 virtio: publish used idx

In reply to Michael S. Tsirkin
Signed-off-by Michael S. Tsirkin <[email protected]>
---
 drivers/net/virtio_net.c     |    2 ++
 drivers/virtio/virtio_ring.c |   17 +++++++++++++++--
 include/linux/virtio_ring.h  |    4 ++++
 3 files changed, 21 insertions(+), 2 deletions(-)
drivers/net/virtio_net.c +2 -0
index 78eb319..30e7483 100644
@@ -23,6 +23,7 @@
 #include <linux/module.h>
 #include <linux/virtio.h>
 #include <linux/virtio_net.h>
+#include <linux/virtio_ring.h>
 #include <linux/scatterlist.h>
 #include <linux/if_vlan.h>
 #include <linux/slab.h>

@@ -1056,6 +1057,7 @@ static unsigned int features[] = {
 	VIRTIO_NET_F_GUEST_ECN, VIRTIO_NET_F_GUEST_UFO,
 	VIRTIO_NET_F_MRG_RXBUF, VIRTIO_NET_F_STATUS, VIRTIO_NET_F_CTRL_VQ,
 	VIRTIO_NET_F_CTRL_RX, VIRTIO_NET_F_CTRL_VLAN,
+	VIRTIO_RING_F_PUBLISH_USED,
 };
 
 static struct virtio_driver virtio_net_driver = {
drivers/virtio/virtio_ring.c +15 -2
index 2241342..4a5458e 100644
@@ -92,6 +92,9 @@ struct vring_virtqueue
 	/* Last used index we've seen. */
 	u16 last_used_idx;
 
+	/* Publish last used index we've seen at this location. */
+	u16 *publish_last_used_idx;
+
 	/* How to notify other side. FIXME: commonalize hcalls! */
 	void (*notify)(struct virtqueue *vq);
 

@@ -325,7 +328,7 @@ void *virtqueue_get_buf(struct virtqueue *_vq, unsigned int *len)
 	/* detach_buf clears data, so grab it now. */
 	ret = vq->data[i];
 	detach_buf(vq, i);
-	vq->last_used_idx++;
+	*vq->publish_last_used_idx = ++vq->last_used_idx;
 	END_USE(vq);
 	return ret;
 }

@@ -348,6 +351,8 @@ bool virtqueue_enable_cb(struct virtqueue *_vq)
 	/* We optimistically turn back on interrupts, then check if there was
 	 * more to do. */
 	vq->vring.avail->flags &= ~VRING_AVAIL_F_NO_INTERRUPT;
+	/* Besides flags write, this barrier also flushes out
+	 * last available index write. */
 	virtio_mb();
 	if (unlikely(more_used(vq))) {
 		END_USE(vq);

@@ -425,13 +430,19 @@ struct virtqueue *vring_new_virtqueue(unsigned int num,
 	if (!vq)
 		return NULL;
 
-	vring_init(&vq->vring, num, pages, vring_align, false);
+	vring_init(&vq->vring, num, pages, vring_align,
+		   virtio_has_feature(vdev, VIRTIO_RING_F_PUBLISH_USED));
+	if (virtio_has_feature(vdev, VIRTIO_RING_F_PUBLISH_USED))
+	    vq->publish_last_used_idx = &vq->vring.avail->last_used_idx;
+	else
+	    vq->publish_last_used_idx = &vq->last_used_idx;
 	vq->vq.callback = callback;
 	vq->vq.vdev = vdev;
 	vq->vq.name = name;
 	vq->notify = notify;
 	vq->broken = false;
 	vq->last_used_idx = 0;
+	*vq->publish_last_used_idx = 0;
 	vq->num_added = 0;
 	list_add_tail(&vq->vq.list, &vdev->vqs);
 #ifdef DEBUG

@@ -473,6 +484,8 @@ void vring_transport_features(struct virtio_device *vdev)
 		switch (i) {
 		case VIRTIO_RING_F_INDIRECT_DESC:
 			break;
+		case VIRTIO_RING_F_PUBLISH_USED:
+			break;
 		default:
 			/* We don't understand this bit. */
 			clear_bit(i, vdev->features);
include/linux/virtio_ring.h +4 -0
index c5f3ee7..0de35c5 100644
@@ -29,6 +29,9 @@
 /* We support indirect buffer descriptors */
 #define VIRTIO_RING_F_INDIRECT_DESC	28
 
+/* The Guest publishes last-seen used index at the end of the avail ring. */
+#define VIRTIO_RING_F_PUBLISH_USED	29
+
 /* Virtio ring descriptors: 16 bytes.  These can chain together via "next". */
 struct vring_desc {
 	/* Address (guest-physical). */

@@ -50,6 +53,7 @@ struct vring_avail {
 struct vring_avail_ctrl {
 	__u16 flags;
 	__u16 idx;
+	__u16 last_used_idx;
 };
 
 /* u32 is used here for ids for padding reasons. */
Signature · 1 line
1.7.1.12.g42b7f
author maintainer
#4 lore raw

PATCH 2/2 virtio: publish used idx

In reply to Michael S. Tsirkin
Signed-off-by Michael S. Tsirkin <[email protected]>
---
 drivers/net/virtio_net.c     |    2 ++
 drivers/virtio/virtio_ring.c |   17 +++++++++++++++--
 include/linux/virtio_ring.h  |    4 ++++
 3 files changed, 21 insertions(+), 2 deletions(-)
drivers/net/virtio_net.c +2 -0
index 78eb319..30e7483 100644
@@ -23,6 +23,7 @@
 #include <linux/module.h>
 #include <linux/virtio.h>
 #include <linux/virtio_net.h>
+#include <linux/virtio_ring.h>
 #include <linux/scatterlist.h>
 #include <linux/if_vlan.h>
 #include <linux/slab.h>

@@ -1056,6 +1057,7 @@ static unsigned int features[] = {
 	VIRTIO_NET_F_GUEST_ECN, VIRTIO_NET_F_GUEST_UFO,
 	VIRTIO_NET_F_MRG_RXBUF, VIRTIO_NET_F_STATUS, VIRTIO_NET_F_CTRL_VQ,
 	VIRTIO_NET_F_CTRL_RX, VIRTIO_NET_F_CTRL_VLAN,
+	VIRTIO_RING_F_PUBLISH_USED,
 };
 
 static struct virtio_driver virtio_net_driver = {
drivers/virtio/virtio_ring.c +15 -2
index 2241342..4a5458e 100644
@@ -92,6 +92,9 @@ struct vring_virtqueue
 	/* Last used index we've seen. */
 	u16 last_used_idx;
 
+	/* Publish last used index we've seen at this location. */
+	u16 *publish_last_used_idx;
+
 	/* How to notify other side. FIXME: commonalize hcalls! */
 	void (*notify)(struct virtqueue *vq);
 

@@ -325,7 +328,7 @@ void *virtqueue_get_buf(struct virtqueue *_vq, unsigned int *len)
 	/* detach_buf clears data, so grab it now. */
 	ret = vq->data[i];
 	detach_buf(vq, i);
-	vq->last_used_idx++;
+	*vq->publish_last_used_idx = ++vq->last_used_idx;
 	END_USE(vq);
 	return ret;
 }

@@ -348,6 +351,8 @@ bool virtqueue_enable_cb(struct virtqueue *_vq)
 	/* We optimistically turn back on interrupts, then check if there was
 	 * more to do. */
 	vq->vring.avail->flags &= ~VRING_AVAIL_F_NO_INTERRUPT;
+	/* Besides flags write, this barrier also flushes out
+	 * last available index write. */
 	virtio_mb();
 	if (unlikely(more_used(vq))) {
 		END_USE(vq);

@@ -425,13 +430,19 @@ struct virtqueue *vring_new_virtqueue(unsigned int num,
 	if (!vq)
 		return NULL;
 
-	vring_init(&vq->vring, num, pages, vring_align, false);
+	vring_init(&vq->vring, num, pages, vring_align,
+		   virtio_has_feature(vdev, VIRTIO_RING_F_PUBLISH_USED));
+	if (virtio_has_feature(vdev, VIRTIO_RING_F_PUBLISH_USED))
+	    vq->publish_last_used_idx = &vq->vring.avail->last_used_idx;
+	else
+	    vq->publish_last_used_idx = &vq->last_used_idx;
 	vq->vq.callback = callback;
 	vq->vq.vdev = vdev;
 	vq->vq.name = name;
 	vq->notify = notify;
 	vq->broken = false;
 	vq->last_used_idx = 0;
+	*vq->publish_last_used_idx = 0;
 	vq->num_added = 0;
 	list_add_tail(&vq->vq.list, &vdev->vqs);
 #ifdef DEBUG

@@ -473,6 +484,8 @@ void vring_transport_features(struct virtio_device *vdev)
 		switch (i) {
 		case VIRTIO_RING_F_INDIRECT_DESC:
 			break;
+		case VIRTIO_RING_F_PUBLISH_USED:
+			break;
 		default:
 			/* We don't understand this bit. */
 			clear_bit(i, vdev->features);
include/linux/virtio_ring.h +4 -0
index c5f3ee7..0de35c5 100644
@@ -29,6 +29,9 @@
 /* We support indirect buffer descriptors */
 #define VIRTIO_RING_F_INDIRECT_DESC	28
 
+/* The Guest publishes last-seen used index at the end of the avail ring. */
+#define VIRTIO_RING_F_PUBLISH_USED	29
+
 /* Virtio ring descriptors: 16 bytes.  These can chain together via "next". */
 struct vring_desc {
 	/* Address (guest-physical). */

@@ -50,6 +53,7 @@ struct vring_avail {
 struct vring_avail_ctrl {
 	__u16 flags;
 	__u16 idx;
+	__u16 last_used_idx;
 };
 
 /* u32 is used here for ids for padding reasons. */
Signature · 1 line
1.7.1.12.g42b7f
#5 lore raw
In reply to Michael S. Tsirkin
Quoted 11 lines · Michael S. Tsirkin

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Generally, the Host end of the virtio ring doesn't need to see where Guest is up to in consuming the ring. However, to completely understand what's going on from the outside, this information must be exposed. For example, host can reduce the number of interrupts by detecting that the guest is currently handling previous buffers.

Quoted 9 lines

We add a feature bit so the guest can tell the host that it's writing out the current value there, if it wants to use that.

This differs from original approach in that the used index is put after avail index (they are typically written out together). To avoid cache bounces on descriptor access,
and make future extensions easier, we put the ring itself at start of page, and move the control after it.

I missed the spec patch, can you repost it?

Signature · 1 line
error compiling committee.c: too many arguments to function
author maintainer
#6 lore raw
Quoted 1 line · Avi Kivity

I missed the spec patch, can you repost it?

Still work in progress, but here it is.
Note I am still debating with myself whether we should split avail idx and flags into separate cache lines.

virtio-spec.lyx +242 -3
index ed35893..150e5a8 100644
@@ -1803,6 +1803,36 @@ next
 \emph default
  descriptor entry (modulo the ring size).
  This starts at 0, and increases.
+\change_inserted 0 1274966643
+
+\end_layout
+
+\begin_layout Standard
+
+\change_inserted 0 1274968378
+When PUBLISH_USED feature flag has 
+\emph on
+not
+\emph default
+ been negotiated, the ring follows the 
+\begin_inset Quotes eld
+\end_inset
+
+flags
+\begin_inset Quotes erd
+\end_inset
+
+ and the 
+\begin_inset Quotes eld
+\end_inset
+
+idx
+\begin_inset Quotes erd
+\end_inset
+
+ fields:
+\change_unchanged
+
 \end_layout
 
 \begin_layout Standard

@@ -1845,7 +1875,134 @@ struct vring_avail {
 
 \end_layout
 
+\begin_layout Standard
+
+\change_inserted 0 1274968432
+\begin_inset CommandInset label
+LatexCommand label
+name "PUBLISH_USED-feature"
+
+\end_inset
+
+When PUBLISH_USED feature flag has been negotiated, the control structure
+ including the 
+\begin_inset Quotes eld
+\end_inset
+
+flags and the 
+\begin_inset Quotes eld
+\end_inset
+
+idx
+\begin_inset Quotes erd
+\end_inset
+
+ fields follows the ring.
+ This leaves the room for the 
+\begin_inset Quotes eld
+\end_inset
+
+last_seen_used_idx
+\begin_inset Quotes erd
+\end_inset
+
+ field, which indicates the most recent 
+\begin_inset Quotes eld
+\end_inset
+
+idx
+\begin_inset Quotes erd
+\end_inset
+
+ value observed by guest in the used ring (see 
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "sub:Used-Ring"
+
+\end_inset
+
+ below):
+\end_layout
+
+\begin_layout Standard
+
+\change_inserted 0 1274967396
+\begin_inset listings
+inline false
+status open
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274967404
+
+struct vring_avail {
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274967405
+
+   u16 ring[qsz]; /* qsz is the Queue Size field read from device */
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274967533
+
+#define VRING_AVAIL_F_NO_INTERRUPT      1
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274967533
+
+   u16 flags;
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274967533
+
+   u16 idx;
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274968345
+
+   u16 last_seen_used_idx;
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274967396
+
+}; 
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+
+\change_inserted 0 1274967715
+If the ring is large enough, the second layout maintains the control and
+ ring structures on separate cache lines.
+\end_layout
+
 \begin_layout Subsection
+
+\change_inserted 0 1274968415
+\begin_inset CommandInset label
+LatexCommand label
+name "sub:Used-Ring"
+
+\end_inset
+
+
+\change_unchanged
 Used Ring
 \end_layout
 

@@ -2391,12 +2548,20 @@ status open
 
 \begin_layout Plain Layout
 
-while (vq->last_seen_used != vring->used.idx) {
+while (vq->last_seen_used
+\change_inserted 0 1274968316
+_idx
+\change_unchanged
+ != vring->used.idx) {
 \end_layout
 
 \begin_layout Plain Layout
 
-    struct vring_used_elem *e = vring.used->ring[vq->last_seen_used%vsz];
+    struct vring_used_elem *e = vring.used->ring[vq->last_seen_used
+\change_inserted 0 1274968326
+_idx
+\change_unchanged
+%vsz];
 \end_layout
 
 \begin_layout Plain Layout

@@ -2406,7 +2571,11 @@ while (vq->last_seen_used != vring->used.idx) {
 
 \begin_layout Plain Layout
 
-    vq->last_seen_used++;
+    vq->last_seen_used
+\change_inserted 0 1274968321
+_idx
+\change_unchanged
+++;
 \end_layout
 
 \begin_layout Plain Layout

@@ -2419,6 +2588,13 @@ while (vq->last_seen_used != vring->used.idx) {
 
 \end_layout
 
+\begin_layout Standard
+
+\change_inserted 0 1274968252
+If PUBLISH_USED feature is negotiated, last_seen_used value should be published
+ to the device in the avail ring.
+\end_layout
+
 \begin_layout Subsection
 Dealing With Configuration Changes
 \end_layout

@@ -2986,6 +3162,47 @@ struct vring_avail {
 \begin_layout Plain Layout
 
 };
+\change_inserted 0 1274966477
+
+\end_layout
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274966484
+
+struct vring_avail_ctrl {
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274966489
+
+        __u16 flags;
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274966494
+
+        __u16 idx;
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274966499
+
+        __u16 last_used_idx;
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274966474
+
+};
 \end_layout
 
 \begin_layout Plain Layout

@@ -3349,6 +3566,28 @@ reference "sub:Indirect-Descriptors"
 \end_inset
 
 .
+\change_inserted 0 1274967762
+
+\end_layout
+
+\begin_layout Description
+
+\change_inserted 0 1274967926
+VIRTIO_F_RING_PUBLISH_USED
+\begin_inset space ~
+\end_inset
+
+(29) Negotiating this feature indicates that the avail ring layout includes
+ the used index observed by driver, see
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "PUBLISH_USED-feature"
+
+\end_inset
+
+.
+\change_unchanged
+
 \end_layout
 
 \begin_layout Description
author maintainer
#7 lore raw
In reply to Avi Kivity
Quoted 1 line · Avi Kivity

I missed the spec patch, can you repost it?

Still work in progress, but here it is.
Note I am still debating with myself whether we should split avail idx and flags into separate cache lines.

virtio-spec.lyx +242 -3
index ed35893..150e5a8 100644
@@ -1803,6 +1803,36 @@ next
 \emph default
  descriptor entry (modulo the ring size).
  This starts at 0, and increases.
+\change_inserted 0 1274966643
+
+\end_layout
+
+\begin_layout Standard
+
+\change_inserted 0 1274968378
+When PUBLISH_USED feature flag has 
+\emph on
+not
+\emph default
+ been negotiated, the ring follows the 
+\begin_inset Quotes eld
+\end_inset
+
+flags
+\begin_inset Quotes erd
+\end_inset
+
+ and the 
+\begin_inset Quotes eld
+\end_inset
+
+idx
+\begin_inset Quotes erd
+\end_inset
+
+ fields:
+\change_unchanged
+
 \end_layout
 
 \begin_layout Standard

@@ -1845,7 +1875,134 @@ struct vring_avail {
 
 \end_layout
 
+\begin_layout Standard
+
+\change_inserted 0 1274968432
+\begin_inset CommandInset label
+LatexCommand label
+name "PUBLISH_USED-feature"
+
+\end_inset
+
+When PUBLISH_USED feature flag has been negotiated, the control structure
+ including the 
+\begin_inset Quotes eld
+\end_inset
+
+flags and the 
+\begin_inset Quotes eld
+\end_inset
+
+idx
+\begin_inset Quotes erd
+\end_inset
+
+ fields follows the ring.
+ This leaves the room for the 
+\begin_inset Quotes eld
+\end_inset
+
+last_seen_used_idx
+\begin_inset Quotes erd
+\end_inset
+
+ field, which indicates the most recent 
+\begin_inset Quotes eld
+\end_inset
+
+idx
+\begin_inset Quotes erd
+\end_inset
+
+ value observed by guest in the used ring (see 
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "sub:Used-Ring"
+
+\end_inset
+
+ below):
+\end_layout
+
+\begin_layout Standard
+
+\change_inserted 0 1274967396
+\begin_inset listings
+inline false
+status open
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274967404
+
+struct vring_avail {
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274967405
+
+   u16 ring[qsz]; /* qsz is the Queue Size field read from device */
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274967533
+
+#define VRING_AVAIL_F_NO_INTERRUPT      1
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274967533
+
+   u16 flags;
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274967533
+
+   u16 idx;
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274968345
+
+   u16 last_seen_used_idx;
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274967396
+
+}; 
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+
+\change_inserted 0 1274967715
+If the ring is large enough, the second layout maintains the control and
+ ring structures on separate cache lines.
+\end_layout
+
 \begin_layout Subsection
+
+\change_inserted 0 1274968415
+\begin_inset CommandInset label
+LatexCommand label
+name "sub:Used-Ring"
+
+\end_inset
+
+
+\change_unchanged
 Used Ring
 \end_layout
 

@@ -2391,12 +2548,20 @@ status open
 
 \begin_layout Plain Layout
 
-while (vq->last_seen_used != vring->used.idx) {
+while (vq->last_seen_used
+\change_inserted 0 1274968316
+_idx
+\change_unchanged
+ != vring->used.idx) {
 \end_layout
 
 \begin_layout Plain Layout
 
-    struct vring_used_elem *e = vring.used->ring[vq->last_seen_used%vsz];
+    struct vring_used_elem *e = vring.used->ring[vq->last_seen_used
+\change_inserted 0 1274968326
+_idx
+\change_unchanged
+%vsz];
 \end_layout
 
 \begin_layout Plain Layout

@@ -2406,7 +2571,11 @@ while (vq->last_seen_used != vring->used.idx) {
 
 \begin_layout Plain Layout
 
-    vq->last_seen_used++;
+    vq->last_seen_used
+\change_inserted 0 1274968321
+_idx
+\change_unchanged
+++;
 \end_layout
 
 \begin_layout Plain Layout

@@ -2419,6 +2588,13 @@ while (vq->last_seen_used != vring->used.idx) {
 
 \end_layout
 
+\begin_layout Standard
+
+\change_inserted 0 1274968252
+If PUBLISH_USED feature is negotiated, last_seen_used value should be published
+ to the device in the avail ring.
+\end_layout
+
 \begin_layout Subsection
 Dealing With Configuration Changes
 \end_layout

@@ -2986,6 +3162,47 @@ struct vring_avail {
 \begin_layout Plain Layout
 
 };
+\change_inserted 0 1274966477
+
+\end_layout
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274966484
+
+struct vring_avail_ctrl {
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274966489
+
+        __u16 flags;
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274966494
+
+        __u16 idx;
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274966499
+
+        __u16 last_used_idx;
+\end_layout
+
+\begin_layout Plain Layout
+
+\change_inserted 0 1274966474
+
+};
 \end_layout
 
 \begin_layout Plain Layout

@@ -3349,6 +3566,28 @@ reference "sub:Indirect-Descriptors"
 \end_inset
 
 .
+\change_inserted 0 1274967762
+
+\end_layout
+
+\begin_layout Description
+
+\change_inserted 0 1274967926
+VIRTIO_F_RING_PUBLISH_USED
+\begin_inset space ~
+\end_inset
+
+(29) Negotiating this feature indicates that the avail ring layout includes
+ the used index observed by driver, see
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "PUBLISH_USED-feature"
+
+\end_inset
+
+.
+\change_unchanged
+
 \end_layout
 
 \begin_layout Description
#8 lore raw
In reply to Michael S. Tsirkin
Quoted 11 lines · Michael S. Tsirkin

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Generally, the Host end of the virtio ring doesn't need to see where Guest is up to in consuming the ring. However, to completely understand what's going on from the outside, this information must be exposed. For example, host can reduce the number of interrupts by detecting that the guest is currently handling previous buffers.

Quoted 9 lines

We add a feature bit so the guest can tell the host that it's writing out the current value there, if it wants to use that.

This differs from original approach in that the used index is put after avail index (they are typically written out together). To avoid cache bounces on descriptor access,
and make future extensions easier, we put the ring itself at start of page, and move the control after it.

I missed the spec patch, can you repost it?

Signature · 1 line
error compiling committee.c: too many arguments to function
#9 lore raw
In reply to Michael S. Tsirkin
Quoted 11 lines · Michael S. Tsirkin

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Generally, the Host end of the virtio ring doesn't need to see where Guest is up to in consuming the ring. However, to completely understand what's going on from the outside, this information must be exposed. For example, host can reduce the number of interrupts by detecting that the guest is currently handling previous buffers.

Quoted 8 lines

We add a feature bit so the guest can tell the host that it's writing out the current value there, if it wants to use that.

This differs from original approach in that the used index is put after avail index (they are typically written out together). To avoid cache bounces on descriptor access,
and make future extensions easier, we put the ring itself at start of page, and move the control after it.

Hi Michael,

It looks pretty good to me, however one thing I have been thinking of while reading through it:

Rather than storing a pointer within the ring struct, pointing into a position within the same struct. How about storing a byte offset instead and using a cast to get to the pointer position? That would avoid the pointer dereference, which is less effective cache wise and harder for the CPU to predict.

Not sure whether it really matters performance wise, just a thought.

Cheers,
Jes

#10 lore raw
In reply to Michael S. Tsirkin
Quoted 11 lines · Michael S. Tsirkin

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Generally, the Host end of the virtio ring doesn't need to see where Guest is up to in consuming the ring. However, to completely understand what's going on from the outside, this information must be exposed. For example, host can reduce the number of interrupts by detecting that the guest is currently handling previous buffers.

Quoted 8 lines

We add a feature bit so the guest can tell the host that it's writing out the current value there, if it wants to use that.

This differs from original approach in that the used index is put after avail index (they are typically written out together). To avoid cache bounces on descriptor access,
and make future extensions easier, we put the ring itself at start of page, and move the control after it.

Hi Michael,

It looks pretty good to me, however one thing I have been thinking of while reading through it:

Rather than storing a pointer within the ring struct, pointing into a position within the same struct. How about storing a byte offset instead and using a cast to get to the pointer position? That would avoid the pointer dereference, which is less effective cache wise and harder for the CPU to predict.

Not sure whether it really matters performance wise, just a thought.

Cheers,
Jes

author maintainer
#11 lore raw
Quoted 32 lines · Jes Sorensen
Quoted 11 lines · Michael S. Tsirkin

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Generally, the Host end of the virtio ring doesn't need to see where Guest is up to in consuming the ring. However, to completely understand what's going on from the outside, this information must be exposed. For example, host can reduce the number of interrupts by detecting that the guest is currently handling previous buffers.

Quoted 8 lines

We add a feature bit so the guest can tell the host that it's writing out the current value there, if it wants to use that.

This differs from original approach in that the used index is put after avail index (they are typically written out together). To avoid cache bounces on descriptor access,
and make future extensions easier, we put the ring itself at start of page, and move the control after it.

Hi Michael,

It looks pretty good to me, however one thing I have been thinking of while reading through it:

Rather than storing a pointer within the ring struct, pointing into a position within the same struct. How about storing a byte offset instead and using a cast to get to the pointer position? That would avoid the pointer dereference, which is less effective cache wise and harder for the CPU to predict.

Quoted 4 lines

Not sure whether it really matters performance wise, just a thought.

Cheers,
Jes

I think this won't work: when PUBLUSH_USED_IDX is negotiated, the pointer is to within the ring.

Signature · 1 line
MST
author maintainer
#12 lore raw
In reply to Jes Sorensen
Quoted 32 lines · Jes Sorensen
Quoted 11 lines · Michael S. Tsirkin

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Generally, the Host end of the virtio ring doesn't need to see where Guest is up to in consuming the ring. However, to completely understand what's going on from the outside, this information must be exposed. For example, host can reduce the number of interrupts by detecting that the guest is currently handling previous buffers.

Quoted 8 lines

We add a feature bit so the guest can tell the host that it's writing out the current value there, if it wants to use that.

This differs from original approach in that the used index is put after avail index (they are typically written out together). To avoid cache bounces on descriptor access,
and make future extensions easier, we put the ring itself at start of page, and move the control after it.

Hi Michael,

It looks pretty good to me, however one thing I have been thinking of while reading through it:

Rather than storing a pointer within the ring struct, pointing into a position within the same struct. How about storing a byte offset instead and using a cast to get to the pointer position? That would avoid the pointer dereference, which is less effective cache wise and harder for the CPU to predict.

Quoted 4 lines

Not sure whether it really matters performance wise, just a thought.

Cheers,
Jes

I think this won't work: when PUBLUSH_USED_IDX is negotiated, the pointer is to within the ring.

Signature · 1 line
MST
#13 lore raw
Quoted 10 lines · Michael S. Tsirkin
Quoted 9 lines · Jes Sorensen

It looks pretty good to me, however one thing I have been thinking of while reading through it:

Rather than storing a pointer within the ring struct, pointing into a position within the same struct. How about storing a byte offset instead and using a cast to get to the pointer position? That would avoid the pointer dereference, which is less effective cache wise and harder for the CPU to predict.

Quoted 4 lines
Quoted 1 line

Not sure whether it really matters performance wise, just a thought.

I think this won't work: when PUBLUSH_USED_IDX is negotiated, the pointer is to within the ring.

Hmmm shame, it would be a nice optimization.

Maybe it's time to introduce the v2 ring format, rather than having adding more kludges to the existing one?

Cheers,
Jes

author maintainer
#14 lore raw
Quoted 16 lines · Jes Sorensen
Quoted 10 lines · Michael S. Tsirkin
Quoted 9 lines · Jes Sorensen

It looks pretty good to me, however one thing I have been thinking of while reading through it:

Rather than storing a pointer within the ring struct, pointing into a position within the same struct. How about storing a byte offset instead and using a cast to get to the pointer position? That would avoid the pointer dereference, which is less effective cache wise and harder for the CPU to predict.

Quoted 4 lines
Quoted 1 line

Not sure whether it really matters performance wise, just a thought.

I think this won't work: when PUBLUSH_USED_IDX is negotiated, the pointer is to within the ring.

Quoted 7 lines

Hmmm shame, it would be a nice optimization.

Maybe it's time to introduce the v2 ring format, rather than having adding more kludges to the existing one?

Cheers,
Jes

There has been discussion about a ring format that does not use indexes at all. My guess is that would be a good point for v2 ring format. But making that a product
and tuning might take a while. So definitely something to keep in mind but I would not want that to block this optimization.

Signature · 1 line
MST
author maintainer
#15 lore raw
In reply to Jes Sorensen
Quoted 16 lines · Jes Sorensen
Quoted 10 lines · Michael S. Tsirkin
Quoted 9 lines · Jes Sorensen

It looks pretty good to me, however one thing I have been thinking of while reading through it:

Rather than storing a pointer within the ring struct, pointing into a position within the same struct. How about storing a byte offset instead and using a cast to get to the pointer position? That would avoid the pointer dereference, which is less effective cache wise and harder for the CPU to predict.

Quoted 4 lines
Quoted 1 line

Not sure whether it really matters performance wise, just a thought.

I think this won't work: when PUBLUSH_USED_IDX is negotiated, the pointer is to within the ring.

Quoted 7 lines

Hmmm shame, it would be a nice optimization.

Maybe it's time to introduce the v2 ring format, rather than having adding more kludges to the existing one?

Cheers,
Jes

There has been discussion about a ring format that does not use indexes at all. My guess is that would be a good point for v2 ring format. But making that a product
and tuning might take a while. So definitely something to keep in mind but I would not want that to block this optimization.

Signature · 1 line
MST
#16 lore raw
In reply to Michael S. Tsirkin
Quoted 10 lines · Michael S. Tsirkin
Quoted 9 lines · Jes Sorensen

It looks pretty good to me, however one thing I have been thinking of while reading through it:

Rather than storing a pointer within the ring struct, pointing into a position within the same struct. How about storing a byte offset instead and using a cast to get to the pointer position? That would avoid the pointer dereference, which is less effective cache wise and harder for the CPU to predict.

Quoted 4 lines
Quoted 1 line

Not sure whether it really matters performance wise, just a thought.

I think this won't work: when PUBLUSH_USED_IDX is negotiated, the pointer is to within the ring.

Hmmm shame, it would be a nice optimization.

Maybe it's time to introduce the v2 ring format, rather than having adding more kludges to the existing one?

Cheers,
Jes

#17 lore raw
In reply to Michael S. Tsirkin
Quoted 4 lines · Michael S. Tsirkin

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Sorry, not without some evidence that it'll actually reduce cacheline bouncing. I *think* it will, but it's not obvious: the host may keep looking at avail_idx as we're updating last_seen. Or does qemu always look at both together anyway?

Can someone convince me this is a win?
Rusty.

#18 lore raw
In reply to Michael S. Tsirkin
Quoted 4 lines · Michael S. Tsirkin

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Sorry, not without some evidence that it'll actually reduce cacheline bouncing. I *think* it will, but it's not obvious: the host may keep looking at avail_idx as we're updating last_seen. Or does qemu always look at both together anyway?

Can someone convince me this is a win?
Rusty.

author maintainer
#19 lore raw
Quoted 6 lines · Rusty Russell
Quoted 4 lines · Michael S. Tsirkin

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Quoted 6 lines

Sorry, not without some evidence that it'll actually reduce cacheline bouncing. I *think* it will, but it's not obvious: the host may keep looking at avail_idx as we're updating last_seen. Or does qemu always look at both together anyway?
Can someone convince me this is a win?
Rusty.

What really happens is host looks at flags and last_seen together. And flags happens to be in the same cache line with avail idx. So to get an obvious win, we should put flags and last_seen
in a separate cache line from avail, which us easy - just add some padding.

And I'll relax the requirement from guest to only require it to update last_seen when interrupts are enabled. This way flags and last_seen are written together and read together.

Makes sense?

Signature · 1 line
MST
author maintainer
#20 lore raw
In reply to Rusty Russell
Quoted 6 lines · Rusty Russell
Quoted 4 lines · Michael S. Tsirkin

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Quoted 6 lines

Sorry, not without some evidence that it'll actually reduce cacheline bouncing. I *think* it will, but it's not obvious: the host may keep looking at avail_idx as we're updating last_seen. Or does qemu always look at both together anyway?
Can someone convince me this is a win?
Rusty.

What really happens is host looks at flags and last_seen together. And flags happens to be in the same cache line with avail idx. So to get an obvious win, we should put flags and last_seen
in a separate cache line from avail, which us easy - just add some padding.

And I'll relax the requirement from guest to only require it to update last_seen when interrupts are enabled. This way flags and last_seen are written together and read together.

Makes sense?

Signature · 1 line
MST
#21 lore raw
In reply to Rusty Russell
Quoted 6 lines · Rusty Russell
Quoted 4 lines · Michael S. Tsirkin

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Quoted 7 lines

Sorry, not without some evidence that it'll actually reduce cacheline bouncing. I *think* it will, but it's not obvious: the host may keep looking at avail_idx as we're updating last_seen. Or does qemu always look at both together anyway?

Can someone convince me this is a win?
Rusty.

Hi Rusty,

I ran some tests using the vring index publish patch with virtio_blk. The numbers are based on running IOZone on a ramdisk passed to the guest via virtio. While I didn't see any throughput improvements, I saw a 20-30% reduction in the VMExit count for the full run. This was measured grabbing the VMExit count prior and after the run and calculating the difference.

I have the numbers in a PDF, so I will email it to you in private as I don't like sending PDFs to the mailing list. However if anybody else wants the numbers feel free to ping me off list and I'll forward them.

Cheers,
Jes

#22 lore raw
In reply to Rusty Russell
Quoted 6 lines · Rusty Russell
Quoted 4 lines · Michael S. Tsirkin

Here's a rewrite of the original patch with a new layout. I haven't tested it yet so no idea how this performs, but I think this addresses the cache bounce issue raised by Avi. Posting for early flames/comments.

Quoted 7 lines

Sorry, not without some evidence that it'll actually reduce cacheline bouncing. I *think* it will, but it's not obvious: the host may keep looking at avail_idx as we're updating last_seen. Or does qemu always look at both together anyway?

Can someone convince me this is a win?
Rusty.

Hi Rusty,

I ran some tests using the vring index publish patch with virtio_blk. The numbers are based on running IOZone on a ramdisk passed to the guest via virtio. While I didn't see any throughput improvements, I saw a 20-30% reduction in the VMExit count for the full run. This was measured grabbing the VMExit count prior and after the run and calculating the difference.

I have the numbers in a PDF, so I will email it to you in private as I don't like sending PDFs to the mailing list. However if anybody else wants the numbers feel free to ping me off list and I'll forward them.

Cheers,
Jes