Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

[Ingo Oeser]

Hi Mark,

On Thursday 18 December 2008, Mark McLoughlin wrote:
> diff --git a/drivers/virtio/virtio_ring.c b/drivers/virtio/virtio_ring.c
> index 5777196..2330c4b 100644
> --- a/drivers/virtio/virtio_ring.c
> +++ b/drivers/virtio/virtio_ring.c
> @@ -70,6 +73,55 @@ struct vring_virtqueue
>  
>  #define to_vvq(_vq) container_of(_vq, struct vring_virtqueue, vq)
>  
> +/* Set up an indirect table of descriptors and add it to the queue. */
> +static int vring_add_indirect(struct vring_virtqueue *vq,
> +			      struct scatterlist sg[],
> +			      unsigned int out,
> +			      unsigned int in)
> +{
> +	struct vring_desc *desc;
> +	unsigned head;
> +	int i;
> +
> +	desc = kmalloc((out + in) * sizeof(struct vring_desc), GFP_ATOMIC);

kmalloc() returns ZERO_SIZE_PTR, if (out + in) == 0

> +	if (!desc)
> +		return vq->vring.num;
> +
> +	/* Transfer entries from the sg list into the indirect page */
> +	for (i = 0; i < out; i++) {
> +		desc[i].flags = VRING_DESC_F_NEXT;
> +		desc[i].addr = sg_phys(sg);
> +		desc[i].len = sg->length;
> +		desc[i].next = i+1;
> +		sg++;
> +	}
> +	for (; i < (out + in); i++) {
> +		desc[i].flags = VRING_DESC_F_NEXT|VRING_DESC_F_WRITE;
> +		desc[i].addr = sg_phys(sg);
> +		desc[i].len = sg->length;
> +		desc[i].next = i+1;
> +		sg++;
> +	}
> +
> +	/* Last one doesn't continue. */
> +	desc[i-1].flags &= ~VRING_DESC_F_NEXT;
> +	desc[i-1].next = 0;

So this array index can fail (be -1).
Please check and avoid within this function.


Best Regards

Ingo Oeser

Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

[Mark McLoughlin]

Hi Ingo,

On Sat, 2008-12-20 at 12:38 +0100, Ingo Oeser wrote:
> Hi Mark,
> 
> On Thursday 18 December 2008, Mark McLoughlin wrote:
> > diff --git a/drivers/virtio/virtio_ring.c b/drivers/virtio/virtio_ring.c
> > index 5777196..2330c4b 100644
> > --- a/drivers/virtio/virtio_ring.c
> > +++ b/drivers/virtio/virtio_ring.c
> > @@ -70,6 +73,55 @@ struct vring_virtqueue
> >  
> >  #define to_vvq(_vq) container_of(_vq, struct vring_virtqueue, vq)
> >  
> > +/* Set up an indirect table of descriptors and add it to the queue. */
> > +static int vring_add_indirect(struct vring_virtqueue *vq,
> > +			      struct scatterlist sg[],
> > +			      unsigned int out,
> > +			      unsigned int in)
> > +{
> > +	struct vring_desc *desc;
> > +	unsigned head;
> > +	int i;
> > +
> > +	desc = kmalloc((out + in) * sizeof(struct vring_desc), GFP_ATOMIC);
> 
> kmalloc() returns ZERO_SIZE_PTR, if (out + in) == 0

vring_add_buf() has:

  BUG_ON(out + in == 0)

I should just add that here too before the kmalloc() call.

Thanks,
Mark.

Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

[Mark McLoughlin]

Hi Rusty,

On Thu, 2008-12-18 at 17:10 +0000, Mark McLoughlin wrote:
> Add a new feature flag for indirect ring entries. These are ring
> entries which point to a table of buffer descriptors.
> 
> The idea here is to increase the ring capacity by allowing a larger
> effective ring size whereby the ring size dictates the number of
> requests that may be outstanding, rather than the size of those
> requests.
> 
> This should be most effective in the case of block I/O where we can
> potentially benefit by concurrently dispatching a large number of
> large requests. Even in the simple case of single segment block
> requests, this results in a threefold increase in ring capacity.

Apparently, this would also be useful for the windows virtio-net
drivers.

Dor can explain further, but apparently Windows has been observed
passing the driver a packet with >256 fragments when using TSO.

With a ring size of 256, the guest can either drop the packet or copy it
into a single buffer. We'd much rather if we could use an indirect ring
entry to pass this number of fragments without copying.

For reference the original patch was here:

  http://lkml.org/lkml/2008/12/18/212

Cheers,
Mark.

Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

[Dor Laor]

Mark McLoughlin wrote:
> Hi Rusty,
>
> On Thu, 2008-12-18 at 17:10 +0000, Mark McLoughlin wrote:
>   
>> Add a new feature flag for indirect ring entries. These are ring
>> entries which point to a table of buffer descriptors.
>>
>> The idea here is to increase the ring capacity by allowing a larger
>> effective ring size whereby the ring size dictates the number of
>> requests that may be outstanding, rather than the size of those
>> requests.
>>
>> This should be most effective in the case of block I/O where we can
>> potentially benefit by concurrently dispatching a large number of
>> large requests. Even in the simple case of single segment block
>> requests, this results in a threefold increase in ring capacity.
>>     
>
> Apparently, this would also be useful for the windows virtio-net
> drivers.
>
> Dor can explain further, but apparently Windows has been observed
> passing the driver a packet with >256 fragments when using TSO.
>
> With a ring size of 256, the guest can either drop the packet or copy it
> into a single buffer. We'd much rather if we could use an indirect ring
> entry to pass this number of fragments without copying.
>   
Correct. This is what we do in Windows today.
The problem arises when using sending lots of small packets
from the win guest and TSO. Windows prepare very big scatter gather
list, bigger than the ring size (270 fragments).
Having indirect ring entries is good both for this and also for block 
io, as described
above.

Cheers,
Dor
> For reference the original patch was here:
>
>   http://lkml.org/lkml/2008/12/18/212
>
> Cheers,
> Mark.
>
> _______________________________________________
> Virtualization mailing list
> Virtualization@lists.linux-foundation.org
> https://lists.linux-foundation.org/mailman/listinfo/virtualization
>   

Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

[Rusty Russell]

On Mon, 27 Apr 2009 05:13:53 pm Dor Laor wrote:
> Mark McLoughlin wrote:
> > Hi Rusty,
> >
> > On Thu, 2008-12-18 at 17:10 +0000, Mark McLoughlin wrote:
> >   
> >> Add a new feature flag for indirect ring entries. These are ring
> >> entries which point to a table of buffer descriptors.
> >>
> >> The idea here is to increase the ring capacity by allowing a larger
> >> effective ring size whereby the ring size dictates the number of
> >> requests that may be outstanding, rather than the size of those
> >> requests.

OK, just so we track our mistakes.

1) virtio_rings must be physically contiguous, even though they actually
   have two independent parts.
2) The number of elements in a ring must be a power of 2.
3) virtio_pci tells the guest what number of elements to use.
4) The guest has to allocate that much physically contiguous memory, or fail.

In practice, 128 elements = 2 pages, 256 elements = 3 pages, 512 elements
= 5 pages.  Order 1, order 2, order 3 under Linux.  1 is OK, 2 is iffy, 3 is
hard.

Blocked from doing the simpler thing, we've decided to go with a layer
of indirection.  But the patch is simple and clean, so there's nothing
fundamental to object to.

I can't find 3/3, did it go missing?

Thanks,
Rusty.



> >>
> >> This should be most effective in the case of block I/O where we can
> >> potentially benefit by concurrently dispatching a large number of
> >> large requests. Even in the simple case of single segment block
> >> requests, this results in a threefold increase in ring capacity.
> >>     
> >
> > Apparently, this would also be useful for the windows virtio-net
> > drivers.
> >
> > Dor can explain further, but apparently Windows has been observed
> > passing the driver a packet with >256 fragments when using TSO.
> >
> > With a ring size of 256, the guest can either drop the packet or copy it
> > into a single buffer. We'd much rather if we could use an indirect ring
> > entry to pass this number of fragments without copying.
> >   
> Correct. This is what we do in Windows today.
> The problem arises when using sending lots of small packets
> from the win guest and TSO. Windows prepare very big scatter gather
> list, bigger than the ring size (270 fragments).
> Having indirect ring entries is good both for this and also for block 
> io, as described
> above.
> 
> Cheers,
> Dor
> > For reference the original patch was here:
> >
> >   http://lkml.org/lkml/2008/12/18/212
> >
> > Cheers,
> > Mark.
> >
> > _______________________________________________
> > Virtualization mailing list
> > Virtualization@lists.linux-foundation.org
> > https://lists.linux-foundation.org/mailman/listinfo/virtualization
> >   
> 

Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

[Mark McLoughlin]

On Mon, 2009-05-04 at 11:49 +0930, Rusty Russell wrote:
> On Mon, 27 Apr 2009 05:13:53 pm Dor Laor wrote:
> > Mark McLoughlin wrote:
> > > Hi Rusty,
> > >
> > > On Thu, 2008-12-18 at 17:10 +0000, Mark McLoughlin wrote:
> > >   
> > >> Add a new feature flag for indirect ring entries. These are ring
> > >> entries which point to a table of buffer descriptors.
> > >>
> > >> The idea here is to increase the ring capacity by allowing a larger
> > >> effective ring size whereby the ring size dictates the number of
> > >> requests that may be outstanding, rather than the size of those
> > >> requests.
> 
> OK, just so we track our mistakes.
> 
> 1) virtio_rings must be physically contiguous, even though they actually
>    have two independent parts.
> 2) The number of elements in a ring must be a power of 2.
> 3) virtio_pci tells the guest what number of elements to use.
> 4) The guest has to allocate that much physically contiguous memory, or fail.
> 
> In practice, 128 elements = 2 pages, 256 elements = 3 pages, 512 elements
> = 5 pages.  Order 1, order 2, order 3 under Linux.  1 is OK, 2 is iffy, 3 is
> hard.
> 
> Blocked from doing the simpler thing, we've decided to go with a layer
> of indirection.  But the patch is simple and clean, so there's nothing
> fundamental to object to.

Still have one FIXME in the patch worth looking at - at what point
should we use an indirect entry rather than consuming N entries? 

> I can't find 3/3, did it go missing?

Following up with all three patches again.

Cheers,
Mark.

Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

[Rusty Russell]

On Tue, 12 May 2009 02:40:38 am Mark McLoughlin wrote:
> > Blocked from doing the simpler thing, we've decided to go with a layer
> > of indirection.  But the patch is simple and clean, so there's nothing
> > fundamental to object to.
>
> Still have one FIXME in the patch worth looking at - at what point
> should we use an indirect entry rather than consuming N entries?

OK, I've applied these as is.  I'm doing some virtio net benchmarking (under 
lguest); I'll see if I can get a reasonable figure.  I don't think there's an 
obvious right answer; it depends how many more packets are coming as well as 
how many descriptors each will use.

Thanks,
Rusty.

Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

[Rusty Russell]

On Tue, 12 May 2009 02:40:38 am Mark McLoughlin wrote:
> Still have one FIXME in the patch worth looking at - at what point
> should we use an indirect entry rather than consuming N entries?

Is this overkill?

Rusty.

virtio: use indirect buffers based on demand (heuristic)

virtio_ring uses a ring buffer of descriptors: indirect support allows
a single descriptor to refer to a table of descriptors.  This saves
space in the ring, but requires a kmalloc/kfree.

Rather than try to figure out what the right threshold at which to use
indirect buffers, we drop the threshold dynamically when the ring is
under stress.

Note: to stress this, I reduced the ring size to 32 in lguest, and a
1G send reduced the threshold to 9.

Note2: I moved the BUG_ON()s above the indirect test, where they belong
(indirect falls thru on OOM, so the constraints still apply).

Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

diff --git a/drivers/virtio/virtio_ring.c b/drivers/virtio/virtio_ring.c
--- a/drivers/virtio/virtio_ring.c
+++ b/drivers/virtio/virtio_ring.c
@@ -63,6 +63,8 @@ struct vring_virtqueue
 
 	/* Host supports indirect buffers */
 	bool indirect;
+	/* Threshold before we go indirect. */
+	unsigned int indirect_threshold;
 
 	/* Number of free buffers */
 	unsigned int num_free;
@@ -137,6 +141,32 @@ static int vring_add_indirect(struct vri
 	return head;
 }
 
+static void adjust_threshold(struct vring_virtqueue *vq,
+			     unsigned int out, unsigned int in)
+{
+	/* There are really two species of virtqueue, and it matters here.
+	 * If there are no output parts, it's a "normally full" receive queue,
+	 * otherwise it's a "normally empty" send queue. */
+	if (out) {
+		/* Leave threshold unless we're full. */
+		if (out + in < vq->num_free)
+			return;
+	} else {
+		/* Leave threshold unless we're empty. */
+		if (vq->num_free != vq->vring.num)
+			return;
+	}
+
+	/* Never drop threshold below 1 */
+	vq->indirect_threshold /= 2;
+	vq->indirect_threshold |= 1;
+
+	printk("%s %s: indirect threshold %u (%u+%u vs %u)\n", 
+	       dev_name(&vq->vq.vdev->dev),
+	       vq->vq.name, vq->indirect_threshold,
+	       out, in, vq->num_free);
+}
+
 static int vring_add_buf(struct virtqueue *_vq,
 			 struct scatterlist sg[],
 			 unsigned int out,
@@ -149,18 +179,31 @@ static int vring_add_buf(struct virtqueu
 	START_USE(vq);
 
 	BUG_ON(data == NULL);
-
-	/* If the host supports indirect descriptor tables, and we have multiple
-	 * buffers, then go indirect. FIXME: tune this threshold */
-	if (vq->indirect && (out + in) > 1 && vq->num_free) {
-		head = vring_add_indirect(vq, sg, out, in);
-		if (head != vq->vring.num)
-			goto add_head;
-	}
-
 	BUG_ON(out + in > vq->vring.num);
 	BUG_ON(out + in == 0);
 
+	/* If the host supports indirect descriptor tables, consider it. */
+	if (vq->indirect) {
+		bool try_indirect;
+
+		/* We tweak the threshold automatically. */
+		adjust_threshold(vq, out, in);
+
+		/* If we can't fit any at all, fall through. */
+		if (vq->num_free == 0)
+			try_indirect = false;
+		else if (out + in > vq->num_free)
+			try_indirect = true;
+		else
+			try_indirect = (out + in > vq->indirect_threshold);
+
+		if (try_indirect) {
+			head = vring_add_indirect(vq, sg, out, in);
+			if (head != vq->vring.num)
+				goto add_head;
+		}
+	}
+
 	if (vq->num_free < out + in) {
 		pr_debug("Can't add buf len %i - avail = %i\n",
 			 out + in, vq->num_free);
@@ -391,6 +434,7 @@ struct virtqueue *vring_new_virtqueue(un
 #endif
 
 	vq->indirect = virtio_has_feature(vdev, VIRTIO_RING_F_INDIRECT_DESC);
+	vq->indirect_threshold = num;
 
 	/* No callback?  Tell other side not to bother us. */
 	if (!callback)

Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

[Avi Kivity]

Rusty Russell wrote:
>  
> +static void adjust_threshold(struct vring_virtqueue *vq,
> +			     unsigned int out, unsigned int in)
> +{
> +	/* There are really two species of virtqueue, and it matters here.
> +	 * If there are no output parts, it's a "normally full" receive queue,
> +	 * otherwise it's a "normally empty" send queue. */
>   

This comment is true for networking, but not for block. ++overkill with 
a ->adjust_threshold op.

-- 
Do not meddle in the internals of kernels, for they are subtle and quick to panic.

Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

[Rusty Russell]

On Sun, 17 May 2009 03:57:01 pm Avi Kivity wrote:
> Rusty Russell wrote:
> > +static void adjust_threshold(struct vring_virtqueue *vq,
> > +			     unsigned int out, unsigned int in)
> > +{
> > +	/* There are really two species of virtqueue, and it matters here.
> > +	 * If there are no output parts, it's a "normally full" receive queue,
> > +	 * otherwise it's a "normally empty" send queue. */
>
> This comment is true for networking, but not for block. ++overkill with
> a ->adjust_threshold op.

No, it's true for block.  It has output parts, so we should reduce threshold 
when it's full.  Network recvq is an example which should reduce threshold 
when it's empty.

->adjust_threshold is better as an arg to vring_new_virtqueue, but it's still 
not clear what the answer would be.

Rusty.

Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

[Avi Kivity]

Rusty Russell wrote:
> On Sun, 17 May 2009 03:57:01 pm Avi Kivity wrote:
>   
>> Rusty Russell wrote:
>>     
>>> +static void adjust_threshold(struct vring_virtqueue *vq,
>>> +			     unsigned int out, unsigned int in)
>>> +{
>>> +	/* There are really two species of virtqueue, and it matters here.
>>> +	 * If there are no output parts, it's a "normally full" receive queue,
>>> +	 * otherwise it's a "normally empty" send queue. */
>>>       
>> This comment is true for networking, but not for block. ++overkill with
>> a ->adjust_threshold op.
>>     
>
> No, it's true for block.  It has output parts, so we should reduce threshold 
> when it's full.  Network recvq is an example which should reduce threshold 
> when it's empty.
>   

You mean the header that contains the sector number?  It's a little 
incidental, but I guess it works.

-- 
error compiling committee.c: too many arguments to function

Re: [PATCH 2/3] virtio: indirect ring entries (VIRTIO_RING_F_INDIRECT_DESC)

[Rusty Russell]

On Mon, 18 May 2009 12:35:39 am Avi Kivity wrote:
> Rusty Russell wrote:
> > No, it's true for block.  It has output parts, so we should reduce
> > threshold when it's full.  Network recvq is an example which should
> > reduce threshold when it's empty.
>
> You mean the header that contains the sector number?  It's a little
> incidental, but I guess it works.

Yes, the one which breaks is randomness.  You really do just throw buffers with 
no metadata in them and the request is implied. If/when we care, we can add a 
hint flag.

Cheers,
Rusty.