[PATCH RFC] tools/ocaml/xb: Correct calculations of data/space the ring

[PATCH RFC] tools/ocaml/xb: Correct calculations of data/space the ring

[Andrew Cooper]

ml_interface_{read,write}() would miscalculate the quantity of
data/space in the ring if it crossed the ring boundary, and incorrectly
return a short read/write.

This causes a protocol stall, as either side of the ring ends up waiting
for what they believe to be the other side needing to take the next
action.

Correct the calculations to cope with crossing the ring boundary.

In addition, correct the error detection.  It is a hard error if the
producer index gets more than a ring size ahead of the consumer, or if
the consumer ever overtakes the producer.

Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
---
RFC as untested yet, although testing is lined up.  Presented for early
review/nitpicking.

CC: Ian Campbell <Ian.Campbell@citrix.com>
CC: Ian Jackson <Ian.Jackson@eu.citrix.com>
CC: Wei Liu <wei.liu2@citrix.com>
CC: David Scott <dave@recoil.org>
CC: Samuel Thibault <samuel.thibault@ens-lyon.org>
---
 tools/ocaml/libs/xb/xs_ring_stubs.c | 68 +++++++++++++++++++++++++------------
 1 file changed, 47 insertions(+), 21 deletions(-)

diff --git a/tools/ocaml/libs/xb/xs_ring_stubs.c b/tools/ocaml/libs/xb/xs_ring_stubs.c
index fd561a2..67e6269 100644
--- a/tools/ocaml/libs/xb/xs_ring_stubs.c
+++ b/tools/ocaml/libs/xb/xs_ring_stubs.c
@@ -50,7 +50,7 @@ CAMLprim value ml_interface_read(value ml_interface,
 
 	struct xenstore_domain_interface *intf = interface->addr;
 	XENSTORE_RING_IDX cons, prod; /* offsets only */
-	int to_read;
+	int total_data, data;
 	uint32_t connection;
 
 	cons = *(volatile uint32_t*)&intf->req_cons;
@@ -62,22 +62,32 @@ CAMLprim value ml_interface_read(value ml_interface,
 
 	xen_mb();
 
-	if ((prod - cons) > XENSTORE_RING_SIZE)
+	if (((prod - cons) > XENSTORE_RING_SIZE) ||
+            ((cons - prod) < -XENSTORE_RING_SIZE))
 		caml_failwith("bad connection");
 
-	if (prod == cons) {
+	/* Check for any pending data at all. */
+	total_data = prod - cons;
+	if (total_data == 0) {
+		/* No pending data at all. */
 		result = 0;
 		goto exit;
 	}
-	cons = MASK_XENSTORE_IDX(cons);
-	prod = MASK_XENSTORE_IDX(prod);
-	if (prod > cons)
-		to_read = prod - cons;
-	else
-		to_read = XENSTORE_RING_SIZE - cons;
-	if (to_read < len)
-		len = to_read;
-	memcpy(buffer, intf->req + cons, len);
+	else if (total_data > len)
+		/* Some data - make a partial read. */
+		len = total_data;
+
+	/* Check whether data crosses the end of the ring. */
+	data = XENSTORE_RING_SIZE - MASK_XENSTORE_IDX(cons);
+	if (len <= data)
+		/* Data within the remaining part of the ring. */
+		memcpy(buffer, intf->req + MASK_XENSTORE_IDX(cons), len);
+	else {
+		/* Data crosses the ring boundary. Read both halves. */
+		memcpy(buffer, intf->req + MASK_XENSTORE_IDX(cons), data);
+		memcpy(buffer + data, intf->req, len - data);
+	}
+
 	xen_mb();
 	intf->req_cons += len;
 	result = len;
@@ -100,7 +110,7 @@ CAMLprim value ml_interface_write(value ml_interface,
 
 	struct xenstore_domain_interface *intf = interface->addr;
 	XENSTORE_RING_IDX cons, prod;
-	int can_write;
+	int total_space, space;
 	uint32_t connection;
 
 	cons = *(volatile uint32_t*)&intf->rsp_cons;
@@ -111,17 +121,33 @@ CAMLprim value ml_interface_write(value ml_interface,
 		caml_raise_constant(*caml_named_value("Xb.Reconnect"));
 
 	xen_mb();
-	if ( (prod - cons) >= XENSTORE_RING_SIZE ) {
+
+	if (((prod - cons) > XENSTORE_RING_SIZE) ||
+            ((cons - prod) < -XENSTORE_RING_SIZE))
+		caml_failwith("bad connection");
+
+	/* Check for space to write the full message. */
+	total_space = prod - cons;
+	if (total_space == 0) {
+		/* No space at all - exit having done nothing. */
 		result = 0;
 		goto exit;
 	}
-	if (MASK_XENSTORE_IDX(prod) >= MASK_XENSTORE_IDX(cons))
-		can_write = XENSTORE_RING_SIZE - MASK_XENSTORE_IDX(prod);
-	else 
-		can_write = MASK_XENSTORE_IDX(cons) - MASK_XENSTORE_IDX(prod);
-	if (can_write < len)
-		len = can_write;
-	memcpy(intf->rsp + MASK_XENSTORE_IDX(prod), buffer, len);
+	else if (total_space < len)
+		/* Some space - make a partial write. */
+		len = total_space;
+
+	/* Check for space until the ring wraps. */
+	space = XENSTORE_RING_SIZE - MASK_XENSTORE_IDX(prod);
+	if (len <= space )
+		/* Message fits inside the remaining part of the ring. */
+		memcpy(intf->rsp + MASK_XENSTORE_IDX(prod), buffer, len);
+	else {
+		/* Message wraps around the end of the ring. Write both halves. */
+		memcpy(intf->rsp + MASK_XENSTORE_IDX(prod), buffer, space);
+		memcpy(intf->rsp, buffer + space, len - space);
+	}
+
 	xen_mb();
 	intf->rsp_prod += len;
 	result = len;
-- 
2.1.4

Re: [PATCH RFC] tools/ocaml/xb: Correct calculations of data/space the ring

[Samuel Thibault]

Andrew Cooper, le Wed 28 Oct 2015 16:05:36 +0000, a écrit :
> @@ -62,22 +62,32 @@ CAMLprim value ml_interface_read(value ml_interface,
>  
>  	xen_mb();
>  
> -	if ((prod - cons) > XENSTORE_RING_SIZE)
> +	if (((prod - cons) > XENSTORE_RING_SIZE) ||
> +            ((cons - prod) < -XENSTORE_RING_SIZE))

prod and cons are uint32_t, so the difference will still be unsigned.
IIRC the test is not bogus even when prod wraps around, (prod - cons)
will still correctly be the difference between both, modulo 2^32.

Indeed, the read side also needs the same two-memcpy fix.

> +	/* Check for any pending data at all. */
> +	total_data = prod - cons;
> +	if (total_data == 0) {
...
> +	else if (total_data > len)
> +		/* Some data - make a partial read. */
> +		len = total_data;
> +
> +	/* Check whether data crosses the end of the ring. */
> +	data = XENSTORE_RING_SIZE - MASK_XENSTORE_IDX(cons);
> +	if (len <= data)
> +		/* Data within the remaining part of the ring. */
> +		memcpy(buffer, intf->req + MASK_XENSTORE_IDX(cons), len);
> +	else {
> +		/* Data crosses the ring boundary. Read both halves. */
> +		memcpy(buffer, intf->req + MASK_XENSTORE_IDX(cons), data);
> +		memcpy(buffer + data, intf->req, len - data);
> +	}
> +

That looks right and nice-looking to me.

>  	xen_mb();
>  	intf->req_cons += len;
>  	result = len;
> @@ -100,7 +110,7 @@ CAMLprim value ml_interface_write(value ml_interface,
>  
>  	struct xenstore_domain_interface *intf = interface->addr;
>  	XENSTORE_RING_IDX cons, prod;
> -	int can_write;
> +	int total_space, space;
>  	uint32_t connection;
>  
>  	cons = *(volatile uint32_t*)&intf->rsp_cons;
> @@ -111,17 +121,33 @@ CAMLprim value ml_interface_write(value ml_interface,
>  		caml_raise_constant(*caml_named_value("Xb.Reconnect"));
>  
>  	xen_mb();
> -	if ( (prod - cons) >= XENSTORE_RING_SIZE ) {
> +
> +	if (((prod - cons) > XENSTORE_RING_SIZE) ||
> +            ((cons - prod) < -XENSTORE_RING_SIZE))

Ditto.

> +	/* Check for space to write the full message. */
> +	total_space = prod - cons;
> +	if (total_space == 0) {

Shouldn't that be total_space == XENSTORE_RING_SIZE?

> +		/* No space at all - exit having done nothing. */
>  		result = 0;
>  		goto exit;
>  	}
> +	else if (total_space < len)
> +		/* Some space - make a partial write. */
> +		len = total_space;
> +
> +	/* Check for space until the ring wraps. */
> +	space = XENSTORE_RING_SIZE - MASK_XENSTORE_IDX(prod);
> +	if (len <= space )
> +		/* Message fits inside the remaining part of the ring. */
> +		memcpy(intf->rsp + MASK_XENSTORE_IDX(prod), buffer, len);
> +	else {
> +		/* Message wraps around the end of the ring. Write both halves. */
> +		memcpy(intf->rsp + MASK_XENSTORE_IDX(prod), buffer, space);
> +		memcpy(intf->rsp, buffer + space, len - space);
> +	}

That looks right and nicer-looking than my attempt :)

Samuel

Re: [PATCH RFC] tools/ocaml/xb: Correct calculations of data/space the ring

[Andrew Cooper]

On 28/10/15 16:18, Samuel Thibault wrote:
> Andrew Cooper, le Wed 28 Oct 2015 16:05:36 +0000, a écrit :
>> @@ -62,22 +62,32 @@ CAMLprim value ml_interface_read(value ml_interface,
>>  
>>  	xen_mb();
>>  
>> -	if ((prod - cons) > XENSTORE_RING_SIZE)
>> +	if (((prod - cons) > XENSTORE_RING_SIZE) ||
>> +            ((cons - prod) < -XENSTORE_RING_SIZE))
> prod and cons are uint32_t, so the difference will still be unsigned.

The RHS will also be promoted to unsigned, as int has insufficient range
for the LHS.

> IIRC the test is not bogus even when prod wraps around, (prod - cons)
> will still correctly be the difference between both, modulo 2^32.

(prod - cons) >= XENSTORE_RING_SIZE checks for the prod getting more
than a ring's worth ahead of cons.

(cons - prod) < -XENSTORE_RING_SIZE is supposed to check for cons
getting ahead of prod (the naive (cons > prod) fails when the ring
wraps), although I notice it still buggy in the case where cons == prod.

>
> Indeed, the read side also needs the same two-memcpy fix.
>
>> +	/* Check for any pending data at all. */
>> +	total_data = prod - cons;
>> +	if (total_data == 0) {
> ...
>> +	else if (total_data > len)
>> +		/* Some data - make a partial read. */
>> +		len = total_data;
>> +
>> +	/* Check whether data crosses the end of the ring. */
>> +	data = XENSTORE_RING_SIZE - MASK_XENSTORE_IDX(cons);
>> +	if (len <= data)
>> +		/* Data within the remaining part of the ring. */
>> +		memcpy(buffer, intf->req + MASK_XENSTORE_IDX(cons), len);
>> +	else {
>> +		/* Data crosses the ring boundary. Read both halves. */
>> +		memcpy(buffer, intf->req + MASK_XENSTORE_IDX(cons), data);
>> +		memcpy(buffer + data, intf->req, len - data);
>> +	}
>> +
> That looks right and nice-looking to me.
>
>>  	xen_mb();
>>  	intf->req_cons += len;
>>  	result = len;
>> @@ -100,7 +110,7 @@ CAMLprim value ml_interface_write(value ml_interface,
>>  
>>  	struct xenstore_domain_interface *intf = interface->addr;
>>  	XENSTORE_RING_IDX cons, prod;
>> -	int can_write;
>> +	int total_space, space;
>>  	uint32_t connection;
>>  
>>  	cons = *(volatile uint32_t*)&intf->rsp_cons;
>> @@ -111,17 +121,33 @@ CAMLprim value ml_interface_write(value ml_interface,
>>  		caml_raise_constant(*caml_named_value("Xb.Reconnect"));
>>  
>>  	xen_mb();
>> -	if ( (prod - cons) >= XENSTORE_RING_SIZE ) {
>> +
>> +	if (((prod - cons) > XENSTORE_RING_SIZE) ||
>> +            ((cons - prod) < -XENSTORE_RING_SIZE))
> Ditto.
>
>> +	/* Check for space to write the full message. */
>> +	total_space = prod - cons;
>> +	if (total_space == 0) {
> Shouldn't that be total_space == XENSTORE_RING_SIZE?

Yes - I think it should.  (I should probably kill my pending tests -
they are not going to get very far...)

~Andrew

>
>> +		/* No space at all - exit having done nothing. */
>>  		result = 0;
>>  		goto exit;
>>  	}
>> +	else if (total_space < len)
>> +		/* Some space - make a partial write. */
>> +		len = total_space;
>> +
>> +	/* Check for space until the ring wraps. */
>> +	space = XENSTORE_RING_SIZE - MASK_XENSTORE_IDX(prod);
>> +	if (len <= space )
>> +		/* Message fits inside the remaining part of the ring. */
>> +		memcpy(intf->rsp + MASK_XENSTORE_IDX(prod), buffer, len);
>> +	else {
>> +		/* Message wraps around the end of the ring. Write both halves. */
>> +		memcpy(intf->rsp + MASK_XENSTORE_IDX(prod), buffer, space);
>> +		memcpy(intf->rsp, buffer + space, len - space);
>> +	}
> That looks right and nicer-looking than my attempt :)
>
> Samuel

Re: [PATCH RFC] tools/ocaml/xb: Correct calculations of data/space the ring

[Samuel Thibault]

Andrew Cooper, le Wed 28 Oct 2015 16:43:54 +0000, a écrit :
> > IIRC the test is not bogus even when prod wraps around, (prod - cons)
> > will still correctly be the difference between both, modulo 2^32.
> 
> (prod - cons) >= XENSTORE_RING_SIZE checks for the prod getting more
> than a ring's worth ahead of cons.
> 
> (cons - prod) < -XENSTORE_RING_SIZE is supposed to check for cons
> getting ahead of prod

If cons is a ahead of prod, prod-cons is way bigger than
XENSTORE_RING_SIZE, and thus the first test already catches that. In the
2^32 wrap case, the difference will still be correct.

Samuel

Re: [PATCH RFC] tools/ocaml/xb: Correct calculations of data/space the ring

[Andrew Cooper]

On 28/10/15 16:56, Samuel Thibault wrote:
> Andrew Cooper, le Wed 28 Oct 2015 16:43:54 +0000, a écrit :
>>> IIRC the test is not bogus even when prod wraps around, (prod - cons)
>>> will still correctly be the difference between both, modulo 2^32.
>> (prod - cons) >= XENSTORE_RING_SIZE checks for the prod getting more
>> than a ring's worth ahead of cons.
>>
>> (cons - prod) < -XENSTORE_RING_SIZE is supposed to check for cons
>> getting ahead of prod
> If cons is a ahead of prod, prod-cons is way bigger than
> XENSTORE_RING_SIZE, and thus the first test already catches that. In the
> 2^32 wrap case, the difference will still be correct.

Hmm - of course.  I will scale back the adjustments to the error handling.

~Andrew