Date: Fri, 8 Mar 2013 02:00:17 +1100 (EST) From: Bruce Evans <brde@optusnet.com.au> To: Colin Percival <cperciva@FreeBSD.org> Cc: David Malone <dwmalone@maths.tcd.ie>, svn-src-head@FreeBSD.org, svn-src-all@FreeBSD.org, src-committers@FreeBSD.org, Peter Grehan <grehan@FreeBSD.org> Subject: Re: svn commit: r247871 - head/usr.sbin/bhyve Message-ID: <20130308004634.W1510@besplex.bde.org> In-Reply-To: <5137CF1D.3020506@freebsd.org> References: <201303060728.r267SKP3018477@svn.freebsd.org> <20130306231613.GA5146@walton.maths.tcd.ie> <5137CF1D.3020506@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Wed, 6 Mar 2013, Colin Percival wrote: > On 03/06/13 15:16, David Malone wrote: >>> + /* >>> + * We're just computing (a-b) in GF(216). >> >>> + ndesc = (unsigned)*hq->hq_avail_idx - (unsigned)hq->hq_cur_aidx; >> >> I think the comment here is wrong? Subtraction (and addition) in >> GF(2^16) is just xor of 16 bit numbers. You seem to actually be >> working in Z(2^16), where subtraction is normal subtraction mod >> 65536. > > Given that there's no such thing as GF(216) due to 216 = 2^3 * 3^3 not > being a prime power, the comment is definitely wrong. ;-) 216 looks like a typo for 2**16, but 2**16 is even more obviously not a prime :-). 2^16 looks like way of writing 2**16 in non-C contexts where '^' isn't the xor operator. The `unsigned' casts seem to be wrong too: - 'unsigned' is spelled u_int in KNF, and bhyve used the latter everywhere else in the directory. (However, it only spelled 'unsigned char' as u_char in 12 out of 15 instances.) - they don't actually work to give subtraction mod 2**16. Assume a result that carries (this was the complicated case in the old code). Say first term = 1 and second term = 3. These promote to int, thanks to C90's broken "value-preserving" promotion rules. The result with uncast ints would be -2. Assigning this to "int ndesc;" doesn't change the value. With the ints cast to unsigned, the result is 1U - 3U = -2U. Assigning this to "int ndesc;" gives an implementation-defined result that is usually -2. Not what we want. We want (uint16_t)-2 = 0xFFFE. The casts of the terms make no difference except to give implementation- defined behaviour. The cast of the result of the expression has the same defined behaviour of adding 1 more than UINT16_MAX that was coded explicitly for the case that carries in the old version. The broken promotion rules actually help here, by avoiding the implementation-defined behaviour provided int is larger than uint16_t. However, ndesc shouild be u_int to avoid the immplementation-defined behaviour from assigning large u_ints to it, or better uint16_t to discard the top bits without a cast. The general method that works here is: u_int result, t1, t2; result = t1 - t2; or uintN_t result, t1, t2; result = t1 - t2; where uintN_t has promotion rank higher than u_int. Using a uintN_t that has promotion rank smaller than u_int gives promotions to int, or using int directly, give a morass of sign extension problems. However, when promotion occurs, it prevents overflow of the signed int expression, and the result of that is usable of you convert it back to uintN_t before really using it. That is not done here -- the next use is an assert() that will fail when ndesc = -2, or, if ndesc is changed to u_int, then it will fail when ndesc = -2U ~= infinity. The code seems to be quite broken apart from this. Maybe just the assert() in it. Wrap probably doesn't give numbers like 1-3 (mod 2**16) = 65534, but more like 1-63 (mod 2**16) = 65536-62 = 65474. Here the magic 63 is the queue size - 1. We want a difference of 2, and would get that by evaluating mod the queue size, but we evaluate modulo 2**16 modulo bugs. 65474 exceeds the queue size so the assertion fails. The modulo by 2**16 can be done a bit faster, at least if ints are 16 bits, but the critical uses of the indexes seem to mostly do a slow runtime modulo (uidx % hq->hq_size), so they will be slow but will work if the indexes are taken mod 2**16 or even mod 2**(number of bits in u_int). Calculating the difference with a sloppy modulo might work too. But not when we assert that it gives a small value. Also, if the indexes are allowed to exceed the queue size, then even the non-carry case may give a large value. Bruce
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20130308004634.W1510>