**Next message:**Rasmus Villemoes: "Re: [RFC] vfs: don't bother clearing close_on_exec bit for unused fds"**Previous message:**Michael Welling: "Re: [PATCH 4/4] Input: tsc2004 - Document ts2004 dt bindings"**In reply to:**Rasmus Villemoes: "Re: [PATCH v2] string_helpers: fix precision loss for some inputs"**Next in thread:**James Bottomley: "[PATCH v4] string_helpers: fix precision loss for some inputs"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

From: James Bottomley <JBottomley@xxxxxxxx>

It was noticed that we lose precision in the final calculation for some

inputs. The most egregious example is size=3000 blk_size=1900 in units of 10

should yield 5.70 MB but in fact yields 3.00 MB (oops). This is because the

current algorithm doesn't correctly account for all the remainders in the

logarithms. Fix this by doing a correct calculation in the remainders based

on napier's algorithm. Additionally, now we have the correct result, we have

to account for arithmetic rounding because we're printing 3 digits of

precision. This means that if the fourth digit is five or greater, we have to

round up, so add a section to ensure correct rounding. Finally account for

all possible inputs correctly, including zero for block size.

Reported-by: Vitaly Kuznetsov <vkuznets@xxxxxxxxxx>

Cc: stable@xxxxxxxxxxxxxxx # delay backport by two months for testing

Fixes: b9f28d863594c429e1df35a0474d2663ca28b307

Signed-off-by: James Bottomley <JBottomley@xxxxxxxx>

---

v2: updated with a recommendation from Rasmus Villemoes to truncate the

initial precision at just under 32 bits

v3: put back the missing do_divs

diff --git a/lib/string_helpers.c b/lib/string_helpers.c

index 5939f63..c2ffb73 100644

--- a/lib/string_helpers.c

+++ b/lib/string_helpers.c

@@ -43,38 +43,45 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,

[STRING_UNITS_10] = 1000,

[STRING_UNITS_2] = 1024,

};

- int i, j;

- u32 remainder = 0, sf_cap, exp;

+ static const unsigned int rounding[] = { 500, 50, 5, 0};

+ int i = 0, j;

+ u32 remainder = 0, sf_cap;

char tmp[8];

const char *unit;

tmp[0] = '\0';

- i = 0;

- if (!size)

+

+ if (blk_size == 0)

+ size = 0;

+ if (size == 0)

goto out;

- while (blk_size >= divisor[units]) {

- remainder = do_div(blk_size, divisor[units]);

+ /* This is napier's algorithm. Reduce the original block size to

+ *

+ * coefficient * divisor[units]^i

+ *

+ * we do the reduction so both coefficients are just under 32 bits so

+ * that multiplying them together won't overflow 64 bits and we keep

+ * as much precision as possible in the numbers.

+ *

+ * Note: it's safe to throw away the remainders here because all the

+ * precision is in the coefficients.

+ */

+ while (blk_size >= UINT_MAX) {

+ do_div(blk_size, divisor[units]);

i++;

}

- exp = divisor[units] / (u32)blk_size;

- /*

- * size must be strictly greater than exp here to ensure that remainder

- * is greater than divisor[units] coming out of the if below.

- */

- if (size > exp) {

- remainder = do_div(size, divisor[units]);

- remainder *= blk_size;

+ while (size >= UINT_MAX) {

+ do_div(size, divisor[units]);

i++;

- } else {

- remainder *= size;

}

+ /* now perform the actual multiplication keeping i as the sum of the

+ * two logarithms */

size *= blk_size;

- size += remainder / divisor[units];

- remainder %= divisor[units];

+ /* and logarithmically reduce it until it's just under the divisor */

while (size >= divisor[units]) {

remainder = do_div(size, divisor[units]);

i++;

@@ -84,9 +91,20 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,

for (j = 0; sf_cap*10 < 1000; j++)

sf_cap *= 10;

+ /* express the remainder as a decimal (it's currently the numerator of

+ * a fraction whose denominator is divisor[units]) */

+ remainder *= 1000;

+ remainder /= divisor[units];

+

+ /* add a 5 to the digit below what will be printed to ensure

+ * an arithmetical round up and carry it through to size */

+ remainder += rounding[j];

+ if (remainder >= 1000) {

+ remainder -= 1000;

+ size += 1;

+ }

+

if (j) {

- remainder *= 1000;

- remainder /= divisor[units];

snprintf(tmp, sizeof(tmp), ".%03u", remainder);

tmp[j+1] = '\0';

}

--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

the body of a message to majordomo@xxxxxxxxxxxxxxx

More majordomo info at http://vger.kernel.org/majordomo-info.html

Please read the FAQ at http://www.tux.org/lkml/

**Next message:**Rasmus Villemoes: "Re: [RFC] vfs: don't bother clearing close_on_exec bit for unused fds"**Previous message:**Michael Welling: "Re: [PATCH 4/4] Input: tsc2004 - Document ts2004 dt bindings"**In reply to:**Rasmus Villemoes: "Re: [PATCH v2] string_helpers: fix precision loss for some inputs"**Next in thread:**James Bottomley: "[PATCH v4] string_helpers: fix precision loss for some inputs"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]