Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1260744 > unrolled thread

Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface Vitaly Kuznetsov <vkuznets@redhat.com> - 2015-11-02 17:00 +0100
    Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for  string_get_size() interface James Bottomley <jbottomley@odin.com> - 2015-11-03 04:50 +0100
      Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface Vitaly Kuznetsov <vkuznets@redhat.com> - 2015-11-03 14:20 +0100
        Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for  string_get_size() interface James Bottomley <jbottomley@odin.com> - 2015-11-03 18:10 +0100
          Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface Rasmus Villemoes <linux@rasmusvillemoes.dk> - 2015-11-03 22:00 +0100
            Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for  string_get_size() interface James Bottomley <jbottomley@odin.com> - 2015-11-03 22:20 +0100

#1260744 — Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

James Bottomley <jbottomley@odin.com> writes:

> On Fri, 2015-10-30 at 11:46 +0100, Vitaly Kuznetsov wrote:
>> James Bottomley <jbottomley@odin.com> writes:
>> 
>> > On Thu, 2015-10-29 at 17:30 +0100, Vitaly Kuznetsov wrote:
>> >> string_get_size() can't really handle huge block sizes, especially
>> >> blk_size > U32_MAX but string_get_size() interface states the opposite.
>> >> Change blk_size from u64 to u32 to reflect the reality.
>> >
>> > What is the actual evidence for this?  The calculation is designed to be
>> > a symmetric 128 bit multiply.  When I wrote and tested it, it worked
>> > fine for huge block sizes.
>> 
>> We have 'u32 remainder' and then we do:
>> 
>> exp = divisor[units] / (u32)blk_size;
>> ...
>> remainder = do_div(size, divisor[units]);
>> remainder *= blk_size;
>> 
>> I'm pretty sure it will overflow for some inputs.
>
> It shouldn't; the full code snippet does this:
>
>         	while (blk_size >= divisor[units]) {
>         		remainder = do_div(blk_size, divisor[units]);
>         		i++;
>         	}
>
>         	exp = divisor[units] / (u32)blk_size;
>
> So by the time it reaches the statement you complain about, blk_size is
> already less than or equal to the divisor (which is 1000 or 1024) so
> truncating to 32 bits is always correct.
>

I overlooked, sorry!

> I'm sort of getting the impression you don't quite understand the
> mathematics:  i is the logarithm to the base divisor[units].  We reduce
> both operands to exponents of the logarithm base (adding the two bases
> together in i), which means they are by definition in a range between
> zero and the base and then multiply the remaining exponents correcting
> the result for a base overflow (so the result is always a correct
> exponent and i is the logarithm to the base).  It's actually simply
> Napier's algorithm.
>
> The reason we're getting the up to 2.5% rounding errors you complain
> about is because at each logarithm until the last one, we throw away the
> remainder (it's legitimate because it's always 1000x smaller than the
> exponent), but in the case of a large remainder it provides a small
> correction to the final operation which we don't account for.  If you
> want to make a true correction, you save the penultimate residue in each
> case, multiply each by the *other* exponent add them together, divide by
> the base and increment the final result by the remainder.

My assumption was that we don't really need to support blk_sizes >
U32_MAX and we can simplify string_get_size() instead of adding
additional complexity. Apparently, the assumption was wrong.

>
> However, for 2.5% the physicist in me says the above is way overkill.
>

It is getting was over 2.5% if blk_size is not a power of 2. While it is
probably never the case for block subsystem the function is in lib and
pretends to be general-enough. I'll try to make proper correction and
let's see if it's worth the effort. 

Thanks,

> James
>
>> >
>> > James
>> >
>> >> Signed-off-by: Vitaly Kuznetsov <vkuznets@redhat.com>
>> >> ---
>> >>  include/linux/string_helpers.h | 2 +-
>> >>  lib/string_helpers.c           | 4 ++--
>> >>  2 files changed, 3 insertions(+), 3 deletions(-)
>> >> 
>> >> diff --git a/include/linux/string_helpers.h b/include/linux/string_helpers.h
>> >> index dabe643..1223e80 100644
>> >> --- a/include/linux/string_helpers.h
>> >> +++ b/include/linux/string_helpers.h
>> >> @@ -10,7 +10,7 @@ enum string_size_units {
>> >>  	STRING_UNITS_2,		/* use binary powers of 2^10 */
>> >>  };
>> >>  
>> >> -void string_get_size(u64 size, u64 blk_size, enum string_size_units units,
>> >> +void string_get_size(u64 size, u32 blk_size, enum string_size_units units,
>> >>  		     char *buf, int len);
>> >>  
>> >>  #define UNESCAPE_SPACE		0x01
>> >> diff --git a/lib/string_helpers.c b/lib/string_helpers.c
>> >> index 5939f63..f6c27dc 100644
>> >> --- a/lib/string_helpers.c
>> >> +++ b/lib/string_helpers.c
>> >> @@ -26,7 +26,7 @@
>> >>   * at least 9 bytes and will always be zero terminated.
>> >>   *
>> >>   */
>> >> -void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
>> >> +void string_get_size(u64 size, u32 blk_size, const enum string_size_units units,
>> >>  		     char *buf, int len)
>> >>  {
>> >>  	static const char *const units_10[] = {
>> >> @@ -58,7 +58,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
>> >>  		i++;
>> >>  	}
>> >>  
>> >> -	exp = divisor[units] / (u32)blk_size;
>> >> +	exp = divisor[units] / 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.
>> 

-- 
  Vitaly
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1261179 — Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

T24gTW9uLCAyMDE1LTExLTAyIGF0IDE2OjU4ICswMTAwLCBWaXRhbHkgS3V6bmV0c292IHdyb3Rl
Og0KPiBKYW1lcyBCb3R0b21sZXkgPGpib3R0b21sZXlAb2Rpbi5jb20+IHdyaXRlczoNCj4gDQo+
ID4gT24gRnJpLCAyMDE1LTEwLTMwIGF0IDExOjQ2ICswMTAwLCBWaXRhbHkgS3V6bmV0c292IHdy
b3RlOg0KPiA+PiBKYW1lcyBCb3R0b21sZXkgPGpib3R0b21sZXlAb2Rpbi5jb20+IHdyaXRlczoN
Cj4gPj4gDQo+ID4+ID4gT24gVGh1LCAyMDE1LTEwLTI5IGF0IDE3OjMwICswMTAwLCBWaXRhbHkg
S3V6bmV0c292IHdyb3RlOg0KPiA+PiA+PiBzdHJpbmdfZ2V0X3NpemUoKSBjYW4ndCByZWFsbHkg
aGFuZGxlIGh1Z2UgYmxvY2sgc2l6ZXMsIGVzcGVjaWFsbHkNCj4gPj4gPj4gYmxrX3NpemUgPiBV
MzJfTUFYIGJ1dCBzdHJpbmdfZ2V0X3NpemUoKSBpbnRlcmZhY2Ugc3RhdGVzIHRoZSBvcHBvc2l0
ZS4NCj4gPj4gPj4gQ2hhbmdlIGJsa19zaXplIGZyb20gdTY0IHRvIHUzMiB0byByZWZsZWN0IHRo
ZSByZWFsaXR5Lg0KPiA+PiA+DQo+ID4+ID4gV2hhdCBpcyB0aGUgYWN0dWFsIGV2aWRlbmNlIGZv
ciB0aGlzPyAgVGhlIGNhbGN1bGF0aW9uIGlzIGRlc2lnbmVkIHRvIGJlDQo+ID4+ID4gYSBzeW1t
ZXRyaWMgMTI4IGJpdCBtdWx0aXBseS4gIFdoZW4gSSB3cm90ZSBhbmQgdGVzdGVkIGl0LCBpdCB3
b3JrZWQNCj4gPj4gPiBmaW5lIGZvciBodWdlIGJsb2NrIHNpemVzLg0KPiA+PiANCj4gPj4gV2Ug
aGF2ZSAndTMyIHJlbWFpbmRlcicgYW5kIHRoZW4gd2UgZG86DQo+ID4+IA0KPiA+PiBleHAgPSBk
aXZpc29yW3VuaXRzXSAvICh1MzIpYmxrX3NpemU7DQo+ID4+IC4uLg0KPiA+PiByZW1haW5kZXIg
PSBkb19kaXYoc2l6ZSwgZGl2aXNvclt1bml0c10pOw0KPiA+PiByZW1haW5kZXIgKj0gYmxrX3Np
emU7DQo+ID4+IA0KPiA+PiBJJ20gcHJldHR5IHN1cmUgaXQgd2lsbCBvdmVyZmxvdyBmb3Igc29t
ZSBpbnB1dHMuDQo+ID4NCj4gPiBJdCBzaG91bGRuJ3Q7IHRoZSBmdWxsIGNvZGUgc25pcHBldCBk
b2VzIHRoaXM6DQo+ID4NCj4gPiAgICAgICAgIAl3aGlsZSAoYmxrX3NpemUgPj0gZGl2aXNvclt1
bml0c10pIHsNCj4gPiAgICAgICAgIAkJcmVtYWluZGVyID0gZG9fZGl2KGJsa19zaXplLCBkaXZp
c29yW3VuaXRzXSk7DQo+ID4gICAgICAgICAJCWkrKzsNCj4gPiAgICAgICAgIAl9DQo+ID4NCj4g
PiAgICAgICAgIAlleHAgPSBkaXZpc29yW3VuaXRzXSAvICh1MzIpYmxrX3NpemU7DQo+ID4NCj4g
PiBTbyBieSB0aGUgdGltZSBpdCByZWFjaGVzIHRoZSBzdGF0ZW1lbnQgeW91IGNvbXBsYWluIGFi
b3V0LCBibGtfc2l6ZSBpcw0KPiA+IGFscmVhZHkgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIHRoZSBk
aXZpc29yICh3aGljaCBpcyAxMDAwIG9yIDEwMjQpIHNvDQo+ID4gdHJ1bmNhdGluZyB0byAzMiBi
aXRzIGlzIGFsd2F5cyBjb3JyZWN0Lg0KPiA+DQo+IA0KPiBJIG92ZXJsb29rZWQsIHNvcnJ5IQ0K
PiANCj4gPiBJJ20gc29ydCBvZiBnZXR0aW5nIHRoZSBpbXByZXNzaW9uIHlvdSBkb24ndCBxdWl0
ZSB1bmRlcnN0YW5kIHRoZQ0KPiA+IG1hdGhlbWF0aWNzOiAgaSBpcyB0aGUgbG9nYXJpdGhtIHRv
IHRoZSBiYXNlIGRpdmlzb3JbdW5pdHNdLiAgV2UgcmVkdWNlDQo+ID4gYm90aCBvcGVyYW5kcyB0
byBleHBvbmVudHMgb2YgdGhlIGxvZ2FyaXRobSBiYXNlIChhZGRpbmcgdGhlIHR3byBiYXNlcw0K
PiA+IHRvZ2V0aGVyIGluIGkpLCB3aGljaCBtZWFucyB0aGV5IGFyZSBieSBkZWZpbml0aW9uIGlu
IGEgcmFuZ2UgYmV0d2Vlbg0KPiA+IHplcm8gYW5kIHRoZSBiYXNlIGFuZCB0aGVuIG11bHRpcGx5
IHRoZSByZW1haW5pbmcgZXhwb25lbnRzIGNvcnJlY3RpbmcNCj4gPiB0aGUgcmVzdWx0IGZvciBh
IGJhc2Ugb3ZlcmZsb3cgKHNvIHRoZSByZXN1bHQgaXMgYWx3YXlzIGEgY29ycmVjdA0KPiA+IGV4
cG9uZW50IGFuZCBpIGlzIHRoZSBsb2dhcml0aG0gdG8gdGhlIGJhc2UpLiAgSXQncyBhY3R1YWxs
eSBzaW1wbHkNCj4gPiBOYXBpZXIncyBhbGdvcml0aG0uDQo+ID4NCj4gPiBUaGUgcmVhc29uIHdl
J3JlIGdldHRpbmcgdGhlIHVwIHRvIDIuNSUgcm91bmRpbmcgZXJyb3JzIHlvdSBjb21wbGFpbg0K
PiA+IGFib3V0IGlzIGJlY2F1c2UgYXQgZWFjaCBsb2dhcml0aG0gdW50aWwgdGhlIGxhc3Qgb25l
LCB3ZSB0aHJvdyBhd2F5IHRoZQ0KPiA+IHJlbWFpbmRlciAoaXQncyBsZWdpdGltYXRlIGJlY2F1
c2UgaXQncyBhbHdheXMgMTAwMHggc21hbGxlciB0aGFuIHRoZQ0KPiA+IGV4cG9uZW50KSwgYnV0
IGluIHRoZSBjYXNlIG9mIGEgbGFyZ2UgcmVtYWluZGVyIGl0IHByb3ZpZGVzIGEgc21hbGwNCj4g
PiBjb3JyZWN0aW9uIHRvIHRoZSBmaW5hbCBvcGVyYXRpb24gd2hpY2ggd2UgZG9uJ3QgYWNjb3Vu
dCBmb3IuICBJZiB5b3UNCj4gPiB3YW50IHRvIG1ha2UgYSB0cnVlIGNvcnJlY3Rpb24sIHlvdSBz
YXZlIHRoZSBwZW51bHRpbWF0ZSByZXNpZHVlIGluIGVhY2gNCj4gPiBjYXNlLCBtdWx0aXBseSBl
YWNoIGJ5IHRoZSAqb3RoZXIqIGV4cG9uZW50IGFkZCB0aGVtIHRvZ2V0aGVyLCBkaXZpZGUgYnkN
Cj4gPiB0aGUgYmFzZSBhbmQgaW5jcmVtZW50IHRoZSBmaW5hbCByZXN1bHQgYnkgdGhlIHJlbWFp
bmRlci4NCj4gDQo+IE15IGFzc3VtcHRpb24gd2FzIHRoYXQgd2UgZG9uJ3QgcmVhbGx5IG5lZWQg
dG8gc3VwcG9ydCBibGtfc2l6ZXMgPg0KPiBVMzJfTUFYIGFuZCB3ZSBjYW4gc2ltcGxpZnkgc3Ry
aW5nX2dldF9zaXplKCkgaW5zdGVhZCBvZiBhZGRpbmcNCj4gYWRkaXRpb25hbCBjb21wbGV4aXR5
LiBBcHBhcmVudGx5LCB0aGUgYXNzdW1wdGlvbiB3YXMgd3JvbmcuDQo+IA0KPiA+DQo+ID4gSG93
ZXZlciwgZm9yIDIuNSUgdGhlIHBoeXNpY2lzdCBpbiBtZSBzYXlzIHRoZSBhYm92ZSBpcyB3YXkg
b3ZlcmtpbGwuDQo+ID4NCj4gDQo+IEl0IGlzIGdldHRpbmcgd2FzIG92ZXIgMi41JSBpZiBibGtf
c2l6ZSBpcyBub3QgYSBwb3dlciBvZiAyLiBXaGlsZSBpdCBpcw0KPiBwcm9iYWJseSBuZXZlciB0
aGUgY2FzZSBmb3IgYmxvY2sgc3Vic3lzdGVtIHRoZSBmdW5jdGlvbiBpcyBpbiBsaWIgYW5kDQo+
IHByZXRlbmRzIHRvIGJlIGdlbmVyYWwtZW5vdWdoLiBJJ2xsIHRyeSB0byBtYWtlIHByb3BlciBj
b3JyZWN0aW9uIGFuZA0KPiBsZXQncyBzZWUgaWYgaXQncyB3b3J0aCB0aGUgZWZmb3J0LiANCg0K
T0ssIHRoaXMgaXMgdGhlIGZ1bGwgY2FsY3VsYXRpb24uICBJdCBhbHNvIGluY2x1ZGVzIGFuIGFy
aXRobWV0aWMNCnJvdW5kaW5nIHRvIHRoZSBmaW5hbCBmaWd1cmUgcHJpbnQuICBJIHN1cHBvc2Ug
aXQncyBub3QgdGhhdCBtdWNoIG1vcmUNCmNvbXBsZXhpdHkgdGhhbiB0aGUgb3JpZ2luYWwsIGFu
ZCBpdCBkb2VzIG1ha2UgdGhlIGFsZ29yaXRobSBlYXNpZXIgdG8NCnVuZGVyc3RhbmQuDQoNCldl
IGNvdWxkIGRvIHdpdGggcnVubmluZyB0aGUgY29tbWVudHMgYnkgc29tZSBvdGhlciBub24tbWF0
aGVtYXRpY2lhbiwNCm5vdyBJJ3ZlIGV4cGxhaW5lZCBpdCBpbiBkZXRhaWwgdG8geW91IHR3bywg
dG8gc2VlIGlmIHRoZXkgYWN0dWFsbHkgZ2l2ZQ0KYW4gdW5kZXJzdGFuZGluZyBvZiB0aGUgYWxn
b3JpdGhtLg0KDQpKYW1lcw0KDQotLS0NCg0KZGlmZiAtLWdpdCBhL2xpYi9zdHJpbmdfaGVscGVy
cy5jIGIvbGliL3N0cmluZ19oZWxwZXJzLmMNCmluZGV4IDU5MzlmNjMuLjFlYzdlNzdhIDEwMDY0
NA0KLS0tIGEvbGliL3N0cmluZ19oZWxwZXJzLmMNCisrKyBiL2xpYi9zdHJpbmdfaGVscGVycy5j
DQpAQCAtNDQsNyArNDQsNyBAQCB2b2lkIHN0cmluZ19nZXRfc2l6ZSh1NjQgc2l6ZSwgdTY0IGJs
a19zaXplLCBjb25zdCBlbnVtIHN0cmluZ19zaXplX3VuaXRzIHVuaXRzLA0KIAkJW1NUUklOR19V
TklUU18yXSA9IDEwMjQsDQogCX07DQogCWludCBpLCBqOw0KLQl1MzIgcmVtYWluZGVyID0gMCwg
c2ZfY2FwLCBleHA7DQorCXUzMiByZW1haW5kZXIgPSAwLCBzZl9jYXAsIHIxID0gMCwgcjIgPSAw
LCByb3VuZDsNCiAJY2hhciB0bXBbOF07DQogCWNvbnN0IGNoYXIgKnVuaXQ7DQogDQpAQCAtNTMs
MjcgKzUzLDQ2IEBAIHZvaWQgc3RyaW5nX2dldF9zaXplKHU2NCBzaXplLCB1NjQgYmxrX3NpemUs
IGNvbnN0IGVudW0gc3RyaW5nX3NpemVfdW5pdHMgdW5pdHMsDQogCWlmICghc2l6ZSkNCiAJCWdv
dG8gb3V0Ow0KIA0KKwkvKiBUaGlzIGlzIG5hcGllcidzIGFsZ29yaXRobS4gIFJlZHVjZSB0aGUg
b3JpZ2luYWwgYmxvY2sgc2l6ZSB0bw0KKwkgKg0KKwkgKiBjbyAqIGRpdmlzb3JbdW5pdHNdXmkN
CisJICoNCisJICogd2hlcmUgY28gPSBibGtfc2l6ZSArIHIxL2Rpdmlzb3JbdW5pdHNdOw0KKwkg
Kg0KKwkgKiBhbmQgdGhlIHNhbWUgZm9yIHNpemUuICBXZSBzaW1wbHkgYWRkIHRvIHRoZSBleHBv
bmVudCBpLCBiZWNhdXNlDQorCSAqIHRoZSBmaW5hbCBjYWxjdWxhdGlvbiB3ZSdyZSBsb29raW5n
IGZvciBpcw0KKwkgKg0KKwkgKiAoY28xICogY28yKSAqIGRpdmlzb3JbdW5pdHNdXmkNCisJICov
DQorDQorDQogCXdoaWxlIChibGtfc2l6ZSA+PSBkaXZpc29yW3VuaXRzXSkgew0KLQkJcmVtYWlu
ZGVyID0gZG9fZGl2KGJsa19zaXplLCBkaXZpc29yW3VuaXRzXSk7DQorCQlyMSA9IGRvX2Rpdihi
bGtfc2l6ZSwgZGl2aXNvclt1bml0c10pOw0KIAkJaSsrOw0KIAl9DQogDQotCWV4cCA9IGRpdmlz
b3JbdW5pdHNdIC8gKHUzMilibGtfc2l6ZTsNCi0JLyoNCi0JICogc2l6ZSBtdXN0IGJlIHN0cmlj
dGx5IGdyZWF0ZXIgdGhhbiBleHAgaGVyZSB0byBlbnN1cmUgdGhhdCByZW1haW5kZXINCi0JICog
aXMgZ3JlYXRlciB0aGFuIGRpdmlzb3JbdW5pdHNdIGNvbWluZyBvdXQgb2YgdGhlIGlmIGJlbG93
Lg0KLQkgKi8NCi0JaWYgKHNpemUgPiBleHApIHsNCi0JCXJlbWFpbmRlciA9IGRvX2RpdihzaXpl
LCBkaXZpc29yW3VuaXRzXSk7DQotCQlyZW1haW5kZXIgKj0gYmxrX3NpemU7DQorCXdoaWxlIChz
aXplID49IGRpdmlzb3JbdW5pdHNdKSB7DQorCQlyMiA9IGRvX2RpdihzaXplLCBkaXZpc29yW3Vu
aXRzXSk7DQogCQlpKys7DQotCX0gZWxzZSB7DQotCQlyZW1haW5kZXIgKj0gc2l6ZTsNCiAJfQ0K
IA0KLQlzaXplICo9IGJsa19zaXplOw0KLQlzaXplICs9IHJlbWFpbmRlciAvIGRpdmlzb3JbdW5p
dHNdOw0KLQlyZW1haW5kZXIgJT0gZGl2aXNvclt1bml0c107DQorCS8qIGhlcmUncyB0aGUgbWFn
aWMuICBjbzEgKiBjbzIgbWF5IGJlID4gZGl2aXNvcltpXSwgc28gY29ycmVjdCBmb3INCisJICog
dGhhdCBpbiB0aGUgZXhwb25lbnQgYW5kIG1ha2Ugc3VyZSB0aGF0IHRoZSBhZGRpdGlvbmFsIGNv
cnJlY3Rpb25zDQorCSAqIGZyb20gdGhlIHJlbWFpbmRlcnMgaXMgYWRkZWQgaW4uDQorCSAqDQor
CSAqIGNvMSAqY28yID0gKGJsa19zaXplICsgcjEvZGl2aXNvclt1bml0c10pKihzaXplICsgcjIv
ZGl2aXNvclt1bml0c10pDQorCSAqDQorCSAqIHRoZXJlZm9yZQ0KKwkgKg0KKwkgKiBjbzEqY28y
KmRpdmlzb3JbdW5pdHNdID0gYmxrX3NpemUqc2l6ZSpkaXZpc29yW3VuaXRzXSArDQorCSAqICAg
ICAgICAgIHIxKnNpemUgKyByMipzaXplICsgcjEqcjIvZGl2aXNvclt1bml0c10NCisJICoNCisJ
ICogZHJvcCB0aGUgbGFzdCB0ZXJtIGJlY2F1c2UgaXQncyB0b28gc21hbGwgYW5kIHBlcmZvcm0g
dGhlDQorCSAqIGNhbGN1bGF0aW9uIGNsZXZlcmx5IGJ5IGRlY3JlbWV0aW5nIGkgdG8gYmUgYXV0
b21hdGljYWxseSBkZWFsaW5nDQorCSAqIHdpdGggZXZlcnl0aGluZyBtdWx0aXBsaWVkIGJ5IGRp
dmlzb3JbdW5pdHNdICovDQorDQorCS0taTsNCisJc2l6ZSA9IHNpemUgKiBibGtfc2l6ZSAqIGRp
dmlzb3JbdW5pdHNdICsgcjEgKiBzaXplICsgcjIgKiBibGtfc2l6ZTsNCiANCiAJd2hpbGUgKHNp
emUgPj0gZGl2aXNvclt1bml0c10pIHsNCiAJCXJlbWFpbmRlciA9IGRvX2RpdihzaXplLCBkaXZp
c29yW3VuaXRzXSk7DQpAQCAtODEsOCArMTAwLDE1IEBAIHZvaWQgc3RyaW5nX2dldF9zaXplKHU2
NCBzaXplLCB1NjQgYmxrX3NpemUsIGNvbnN0IGVudW0gc3RyaW5nX3NpemVfdW5pdHMgdW5pdHMs
DQogCX0NCiANCiAJc2ZfY2FwID0gc2l6ZTsNCi0JZm9yIChqID0gMDsgc2ZfY2FwKjEwIDwgMTAw
MDsgaisrKQ0KKwlyb3VuZCA9IDUwMDsNCisJZm9yIChqID0gMDsgc2ZfY2FwKjEwIDwgMTAwMDsg
aisrKSB7DQogCQlzZl9jYXAgKj0gMTA7DQorCQlyb3VuZCAvPSAxMDsNCisJfQ0KKw0KKwkvKiBh
ZGQgYSA1IHRvIHRoZSBkaWdpdCBiZWxvdyB3aGF0IHdpbGwgYmUgcHJpbnRlZCB0byBlbnN1cmUN
CisJICogYW4gYXJpdGhtZXRpY2FsIHJvdW5kIHVwICovDQorCXJlbWFpbmRlciArPSByb3VuZDsN
CiANCiAJaWYgKGopIHsNCiAJCXJlbWFpbmRlciAqPSAxMDAwOw0KDQo=
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1261490

James Bottomley <jbottomley@odin.com> writes:

> On Mon, 2015-11-02 at 16:58 +0100, Vitaly Kuznetsov wrote:
>> James Bottomley <jbottomley@odin.com> writes:
>> 
>> > On Fri, 2015-10-30 at 11:46 +0100, Vitaly Kuznetsov wrote:
>> >> James Bottomley <jbottomley@odin.com> writes:
>> >> 
>> >> > On Thu, 2015-10-29 at 17:30 +0100, Vitaly Kuznetsov wrote:
>> >> >> string_get_size() can't really handle huge block sizes, especially
>> >> >> blk_size > U32_MAX but string_get_size() interface states the opposite.
>> >> >> Change blk_size from u64 to u32 to reflect the reality.
>> >> >
>> >> > What is the actual evidence for this?  The calculation is designed to be
>> >> > a symmetric 128 bit multiply.  When I wrote and tested it, it worked
>> >> > fine for huge block sizes.
>> >> 
>> >> We have 'u32 remainder' and then we do:
>> >> 
>> >> exp = divisor[units] / (u32)blk_size;
>> >> ...
>> >> remainder = do_div(size, divisor[units]);
>> >> remainder *= blk_size;
>> >> 
>> >> I'm pretty sure it will overflow for some inputs.
>> >
>> > It shouldn't; the full code snippet does this:
>> >
>> >         	while (blk_size >= divisor[units]) {
>> >         		remainder = do_div(blk_size, divisor[units]);
>> >         		i++;
>> >         	}
>> >
>> >         	exp = divisor[units] / (u32)blk_size;
>> >
>> > So by the time it reaches the statement you complain about, blk_size is
>> > already less than or equal to the divisor (which is 1000 or 1024) so
>> > truncating to 32 bits is always correct.
>> >
>> 
>> I overlooked, sorry!
>> 
>> > I'm sort of getting the impression you don't quite understand the
>> > mathematics:  i is the logarithm to the base divisor[units].  We reduce
>> > both operands to exponents of the logarithm base (adding the two bases
>> > together in i), which means they are by definition in a range between
>> > zero and the base and then multiply the remaining exponents correcting
>> > the result for a base overflow (so the result is always a correct
>> > exponent and i is the logarithm to the base).  It's actually simply
>> > Napier's algorithm.
>> >
>> > The reason we're getting the up to 2.5% rounding errors you complain
>> > about is because at each logarithm until the last one, we throw away the
>> > remainder (it's legitimate because it's always 1000x smaller than the
>> > exponent), but in the case of a large remainder it provides a small
>> > correction to the final operation which we don't account for.  If you
>> > want to make a true correction, you save the penultimate residue in each
>> > case, multiply each by the *other* exponent add them together, divide by
>> > the base and increment the final result by the remainder.
>> 
>> My assumption was that we don't really need to support blk_sizes >
>> U32_MAX and we can simplify string_get_size() instead of adding
>> additional complexity. Apparently, the assumption was wrong.
>> 
>> >
>> > However, for 2.5% the physicist in me says the above is way overkill.
>> >
>> 
>> It is getting was over 2.5% if blk_size is not a power of 2. While it is
>> probably never the case for block subsystem the function is in lib and
>> pretends to be general-enough. I'll try to make proper correction and
>> let's see if it's worth the effort. 
>
> OK, this is the full calculation.  It also includes an arithmetic
> rounding to the final figure print.  I suppose it's not that much more
> complexity than the original, and it does make the algorithm easier to
> understand.
>
> We could do with running the comments by some other non-mathematician,
> now I've explained it in detail to you two, to see if they actually give
> an understanding of the algorithm.

Thanks, to me they look great! One nitpick below ...

>
> James
>
> ---
>
> diff --git a/lib/string_helpers.c b/lib/string_helpers.c
> index 5939f63..1ec7e77a 100644
> --- a/lib/string_helpers.c
> +++ b/lib/string_helpers.c
> @@ -44,7 +44,7 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
>  		[STRING_UNITS_2] = 1024,
>  	};
>  	int i, j;
> -	u32 remainder = 0, sf_cap, exp;
> +	u32 remainder = 0, sf_cap, r1 = 0, r2 = 0, round;
>  	char tmp[8];
>  	const char *unit;
>
> @@ -53,27 +53,46 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
>  	if (!size)
>  		goto out;
>
> +	/* This is napier's algorithm.  Reduce the original block size to
> +	 *
> +	 * co * divisor[units]^i
> +	 *
> +	 * where co = blk_size + r1/divisor[units];
> +	 *
> +	 * and the same for size.  We simply add to the exponent i, because
> +	 * the final calculation we're looking for is
> +	 *
> +	 * (co1 * co2) * divisor[units]^i
> +	 */
> +
> +
>  	while (blk_size >= divisor[units]) {
> -		remainder = do_div(blk_size, divisor[units]);
> +		r1 = 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 >= divisor[units]) {
> +		r2 = do_div(size, divisor[units]);
>  		i++;
> -	} else {
> -		remainder *= size;
>  	}
>
> -	size *= blk_size;
> -	size += remainder / divisor[units];
> -	remainder %= divisor[units];
> +	/* here's the magic.  co1 * co2 may be > divisor[i], so correct for
> +	 * that in the exponent and make sure that the additional corrections
> +	 * from the remainders is added in.
> +	 *
> +	 * co1 *co2 = (blk_size + r1/divisor[units])*(size + r2/divisor[units])
> +	 *
> +	 * therefore
> +	 *
> +	 * co1*co2*divisor[units] = blk_size*size*divisor[units] +
> +	 *          r1*size + r2*size + r1*r2/divisor[units]
> +	 *
> +	 * drop the last term because it's too small and perform the
> +	 * calculation cleverly by decremeting i to be automatically dealing
> +	 * with everything multiplied by divisor[units] */
> +
> +	--i;
> +	size = size * blk_size * divisor[units] + r1 * size + r2 *
> blk_size;

The last term is actually not that small. Here is an example:

size = 8192  blk_size = 1024

'As is' the algorithm gives us '8.38 MB', and if we add "+ r1 * r1 /
divisor[units]" we get '8.39 MB' (the correct answer is 8192 * 1024 =
8388608 which is 8.39).

Both r1 and r2 are < divisor[units] here so r1 * r2 won't overflow u32,
I suggest we add this term.

>
>  	while (size >= divisor[units]) {
>  		remainder = do_div(size, divisor[units]);
> @@ -81,8 +100,15 @@ void string_get_size(u64 size, u64 blk_size, const enum string_size_units units,
>  	}
>
>  	sf_cap = size;
> -	for (j = 0; sf_cap*10 < 1000; j++)
> +	round = 500;
> +	for (j = 0; sf_cap*10 < 1000; j++) {
>  		sf_cap *= 10;
> +		round /= 10;
> +	}
> +
> +	/* add a 5 to the digit below what will be printed to ensure
> +	 * an arithmetical round up */
> +	remainder += round;
>
>  	if (j) {
>  		remainder *= 1000;

Can I post this solution with your Suggested-by or do you plan to do it
yourself?

Thanks,

-- 
  Vitaly
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1261726 — Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

T24gVHVlLCAyMDE1LTExLTAzIGF0IDE0OjEzICswMTAwLCBWaXRhbHkgS3V6bmV0c292IHdyb3Rl
Og0KPiBKYW1lcyBCb3R0b21sZXkgPGpib3R0b21sZXlAb2Rpbi5jb20+IHdyaXRlczoNCj4gDQo+
ID4gT24gTW9uLCAyMDE1LTExLTAyIGF0IDE2OjU4ICswMTAwLCBWaXRhbHkgS3V6bmV0c292IHdy
b3RlOg0KPiA+PiBKYW1lcyBCb3R0b21sZXkgPGpib3R0b21sZXlAb2Rpbi5jb20+IHdyaXRlczoN
Cj4gPj4gDQo+ID4+ID4gT24gRnJpLCAyMDE1LTEwLTMwIGF0IDExOjQ2ICswMTAwLCBWaXRhbHkg
S3V6bmV0c292IHdyb3RlOg0KPiA+PiA+PiBKYW1lcyBCb3R0b21sZXkgPGpib3R0b21sZXlAb2Rp
bi5jb20+IHdyaXRlczoNCj4gPj4gPj4gDQo+ID4+ID4+ID4gT24gVGh1LCAyMDE1LTEwLTI5IGF0
IDE3OjMwICswMTAwLCBWaXRhbHkgS3V6bmV0c292IHdyb3RlOg0KPiA+PiA+PiA+PiBzdHJpbmdf
Z2V0X3NpemUoKSBjYW4ndCByZWFsbHkgaGFuZGxlIGh1Z2UgYmxvY2sgc2l6ZXMsIGVzcGVjaWFs
bHkNCj4gPj4gPj4gPj4gYmxrX3NpemUgPiBVMzJfTUFYIGJ1dCBzdHJpbmdfZ2V0X3NpemUoKSBp
bnRlcmZhY2Ugc3RhdGVzIHRoZSBvcHBvc2l0ZS4NCj4gPj4gPj4gPj4gQ2hhbmdlIGJsa19zaXpl
IGZyb20gdTY0IHRvIHUzMiB0byByZWZsZWN0IHRoZSByZWFsaXR5Lg0KPiA+PiA+PiA+DQo+ID4+
ID4+ID4gV2hhdCBpcyB0aGUgYWN0dWFsIGV2aWRlbmNlIGZvciB0aGlzPyAgVGhlIGNhbGN1bGF0
aW9uIGlzIGRlc2lnbmVkIHRvIGJlDQo+ID4+ID4+ID4gYSBzeW1tZXRyaWMgMTI4IGJpdCBtdWx0
aXBseS4gIFdoZW4gSSB3cm90ZSBhbmQgdGVzdGVkIGl0LCBpdCB3b3JrZWQNCj4gPj4gPj4gPiBm
aW5lIGZvciBodWdlIGJsb2NrIHNpemVzLg0KPiA+PiA+PiANCj4gPj4gPj4gV2UgaGF2ZSAndTMy
IHJlbWFpbmRlcicgYW5kIHRoZW4gd2UgZG86DQo+ID4+ID4+IA0KPiA+PiA+PiBleHAgPSBkaXZp
c29yW3VuaXRzXSAvICh1MzIpYmxrX3NpemU7DQo+ID4+ID4+IC4uLg0KPiA+PiA+PiByZW1haW5k
ZXIgPSBkb19kaXYoc2l6ZSwgZGl2aXNvclt1bml0c10pOw0KPiA+PiA+PiByZW1haW5kZXIgKj0g
YmxrX3NpemU7DQo+ID4+ID4+IA0KPiA+PiA+PiBJJ20gcHJldHR5IHN1cmUgaXQgd2lsbCBvdmVy
ZmxvdyBmb3Igc29tZSBpbnB1dHMuDQo+ID4+ID4NCj4gPj4gPiBJdCBzaG91bGRuJ3Q7IHRoZSBm
dWxsIGNvZGUgc25pcHBldCBkb2VzIHRoaXM6DQo+ID4+ID4NCj4gPj4gPiAgICAgICAgIAl3aGls
ZSAoYmxrX3NpemUgPj0gZGl2aXNvclt1bml0c10pIHsNCj4gPj4gPiAgICAgICAgIAkJcmVtYWlu
ZGVyID0gZG9fZGl2KGJsa19zaXplLCBkaXZpc29yW3VuaXRzXSk7DQo+ID4+ID4gICAgICAgICAJ
CWkrKzsNCj4gPj4gPiAgICAgICAgIAl9DQo+ID4+ID4NCj4gPj4gPiAgICAgICAgIAlleHAgPSBk
aXZpc29yW3VuaXRzXSAvICh1MzIpYmxrX3NpemU7DQo+ID4+ID4NCj4gPj4gPiBTbyBieSB0aGUg
dGltZSBpdCByZWFjaGVzIHRoZSBzdGF0ZW1lbnQgeW91IGNvbXBsYWluIGFib3V0LCBibGtfc2l6
ZSBpcw0KPiA+PiA+IGFscmVhZHkgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIHRoZSBkaXZpc29yICh3
aGljaCBpcyAxMDAwIG9yIDEwMjQpIHNvDQo+ID4+ID4gdHJ1bmNhdGluZyB0byAzMiBiaXRzIGlz
IGFsd2F5cyBjb3JyZWN0Lg0KPiA+PiA+DQo+ID4+IA0KPiA+PiBJIG92ZXJsb29rZWQsIHNvcnJ5
IQ0KPiA+PiANCj4gPj4gPiBJJ20gc29ydCBvZiBnZXR0aW5nIHRoZSBpbXByZXNzaW9uIHlvdSBk
b24ndCBxdWl0ZSB1bmRlcnN0YW5kIHRoZQ0KPiA+PiA+IG1hdGhlbWF0aWNzOiAgaSBpcyB0aGUg
bG9nYXJpdGhtIHRvIHRoZSBiYXNlIGRpdmlzb3JbdW5pdHNdLiAgV2UgcmVkdWNlDQo+ID4+ID4g
Ym90aCBvcGVyYW5kcyB0byBleHBvbmVudHMgb2YgdGhlIGxvZ2FyaXRobSBiYXNlIChhZGRpbmcg
dGhlIHR3byBiYXNlcw0KPiA+PiA+IHRvZ2V0aGVyIGluIGkpLCB3aGljaCBtZWFucyB0aGV5IGFy
ZSBieSBkZWZpbml0aW9uIGluIGEgcmFuZ2UgYmV0d2Vlbg0KPiA+PiA+IHplcm8gYW5kIHRoZSBi
YXNlIGFuZCB0aGVuIG11bHRpcGx5IHRoZSByZW1haW5pbmcgZXhwb25lbnRzIGNvcnJlY3RpbmcN
Cj4gPj4gPiB0aGUgcmVzdWx0IGZvciBhIGJhc2Ugb3ZlcmZsb3cgKHNvIHRoZSByZXN1bHQgaXMg
YWx3YXlzIGEgY29ycmVjdA0KPiA+PiA+IGV4cG9uZW50IGFuZCBpIGlzIHRoZSBsb2dhcml0aG0g
dG8gdGhlIGJhc2UpLiAgSXQncyBhY3R1YWxseSBzaW1wbHkNCj4gPj4gPiBOYXBpZXIncyBhbGdv
cml0aG0uDQo+ID4+ID4NCj4gPj4gPiBUaGUgcmVhc29uIHdlJ3JlIGdldHRpbmcgdGhlIHVwIHRv
IDIuNSUgcm91bmRpbmcgZXJyb3JzIHlvdSBjb21wbGFpbg0KPiA+PiA+IGFib3V0IGlzIGJlY2F1
c2UgYXQgZWFjaCBsb2dhcml0aG0gdW50aWwgdGhlIGxhc3Qgb25lLCB3ZSB0aHJvdyBhd2F5IHRo
ZQ0KPiA+PiA+IHJlbWFpbmRlciAoaXQncyBsZWdpdGltYXRlIGJlY2F1c2UgaXQncyBhbHdheXMg
MTAwMHggc21hbGxlciB0aGFuIHRoZQ0KPiA+PiA+IGV4cG9uZW50KSwgYnV0IGluIHRoZSBjYXNl
IG9mIGEgbGFyZ2UgcmVtYWluZGVyIGl0IHByb3ZpZGVzIGEgc21hbGwNCj4gPj4gPiBjb3JyZWN0
aW9uIHRvIHRoZSBmaW5hbCBvcGVyYXRpb24gd2hpY2ggd2UgZG9uJ3QgYWNjb3VudCBmb3IuICBJ
ZiB5b3UNCj4gPj4gPiB3YW50IHRvIG1ha2UgYSB0cnVlIGNvcnJlY3Rpb24sIHlvdSBzYXZlIHRo
ZSBwZW51bHRpbWF0ZSByZXNpZHVlIGluIGVhY2gNCj4gPj4gPiBjYXNlLCBtdWx0aXBseSBlYWNo
IGJ5IHRoZSAqb3RoZXIqIGV4cG9uZW50IGFkZCB0aGVtIHRvZ2V0aGVyLCBkaXZpZGUgYnkNCj4g
Pj4gPiB0aGUgYmFzZSBhbmQgaW5jcmVtZW50IHRoZSBmaW5hbCByZXN1bHQgYnkgdGhlIHJlbWFp
bmRlci4NCj4gPj4gDQo+ID4+IE15IGFzc3VtcHRpb24gd2FzIHRoYXQgd2UgZG9uJ3QgcmVhbGx5
IG5lZWQgdG8gc3VwcG9ydCBibGtfc2l6ZXMgPg0KPiA+PiBVMzJfTUFYIGFuZCB3ZSBjYW4gc2lt
cGxpZnkgc3RyaW5nX2dldF9zaXplKCkgaW5zdGVhZCBvZiBhZGRpbmcNCj4gPj4gYWRkaXRpb25h
bCBjb21wbGV4aXR5LiBBcHBhcmVudGx5LCB0aGUgYXNzdW1wdGlvbiB3YXMgd3JvbmcuDQo+ID4+
IA0KPiA+PiA+DQo+ID4+ID4gSG93ZXZlciwgZm9yIDIuNSUgdGhlIHBoeXNpY2lzdCBpbiBtZSBz
YXlzIHRoZSBhYm92ZSBpcyB3YXkgb3ZlcmtpbGwuDQo+ID4+ID4NCj4gPj4gDQo+ID4+IEl0IGlz
IGdldHRpbmcgd2FzIG92ZXIgMi41JSBpZiBibGtfc2l6ZSBpcyBub3QgYSBwb3dlciBvZiAyLiBX
aGlsZSBpdCBpcw0KPiA+PiBwcm9iYWJseSBuZXZlciB0aGUgY2FzZSBmb3IgYmxvY2sgc3Vic3lz
dGVtIHRoZSBmdW5jdGlvbiBpcyBpbiBsaWIgYW5kDQo+ID4+IHByZXRlbmRzIHRvIGJlIGdlbmVy
YWwtZW5vdWdoLiBJJ2xsIHRyeSB0byBtYWtlIHByb3BlciBjb3JyZWN0aW9uIGFuZA0KPiA+PiBs
ZXQncyBzZWUgaWYgaXQncyB3b3J0aCB0aGUgZWZmb3J0LiANCj4gPg0KPiA+IE9LLCB0aGlzIGlz
IHRoZSBmdWxsIGNhbGN1bGF0aW9uLiAgSXQgYWxzbyBpbmNsdWRlcyBhbiBhcml0aG1ldGljDQo+
ID4gcm91bmRpbmcgdG8gdGhlIGZpbmFsIGZpZ3VyZSBwcmludC4gIEkgc3VwcG9zZSBpdCdzIG5v
dCB0aGF0IG11Y2ggbW9yZQ0KPiA+IGNvbXBsZXhpdHkgdGhhbiB0aGUgb3JpZ2luYWwsIGFuZCBp
dCBkb2VzIG1ha2UgdGhlIGFsZ29yaXRobSBlYXNpZXIgdG8NCj4gPiB1bmRlcnN0YW5kLg0KPiA+
DQo+ID4gV2UgY291bGQgZG8gd2l0aCBydW5uaW5nIHRoZSBjb21tZW50cyBieSBzb21lIG90aGVy
IG5vbi1tYXRoZW1hdGljaWFuLA0KPiA+IG5vdyBJJ3ZlIGV4cGxhaW5lZCBpdCBpbiBkZXRhaWwg
dG8geW91IHR3bywgdG8gc2VlIGlmIHRoZXkgYWN0dWFsbHkgZ2l2ZQ0KPiA+IGFuIHVuZGVyc3Rh
bmRpbmcgb2YgdGhlIGFsZ29yaXRobS4NCj4gDQo+IFRoYW5rcywgdG8gbWUgdGhleSBsb29rIGdy
ZWF0ISBPbmUgbml0cGljayBiZWxvdyAuLi4NCj4gDQo+ID4NCj4gPiBKYW1lcw0KPiA+DQo+ID4g
LS0tDQo+ID4NCj4gPiBkaWZmIC0tZ2l0IGEvbGliL3N0cmluZ19oZWxwZXJzLmMgYi9saWIvc3Ry
aW5nX2hlbHBlcnMuYw0KPiA+IGluZGV4IDU5MzlmNjMuLjFlYzdlNzdhIDEwMDY0NA0KPiA+IC0t
LSBhL2xpYi9zdHJpbmdfaGVscGVycy5jDQo+ID4gKysrIGIvbGliL3N0cmluZ19oZWxwZXJzLmMN
Cj4gPiBAQCAtNDQsNyArNDQsNyBAQCB2b2lkIHN0cmluZ19nZXRfc2l6ZSh1NjQgc2l6ZSwgdTY0
IGJsa19zaXplLCBjb25zdCBlbnVtIHN0cmluZ19zaXplX3VuaXRzIHVuaXRzLA0KPiA+ICAJCVtT
VFJJTkdfVU5JVFNfMl0gPSAxMDI0LA0KPiA+ICAJfTsNCj4gPiAgCWludCBpLCBqOw0KPiA+IC0J
dTMyIHJlbWFpbmRlciA9IDAsIHNmX2NhcCwgZXhwOw0KPiA+ICsJdTMyIHJlbWFpbmRlciA9IDAs
IHNmX2NhcCwgcjEgPSAwLCByMiA9IDAsIHJvdW5kOw0KPiA+ICAJY2hhciB0bXBbOF07DQo+ID4g
IAljb25zdCBjaGFyICp1bml0Ow0KPiA+DQo+ID4gQEAgLTUzLDI3ICs1Myw0NiBAQCB2b2lkIHN0
cmluZ19nZXRfc2l6ZSh1NjQgc2l6ZSwgdTY0IGJsa19zaXplLCBjb25zdCBlbnVtIHN0cmluZ19z
aXplX3VuaXRzIHVuaXRzLA0KPiA+ICAJaWYgKCFzaXplKQ0KPiA+ICAJCWdvdG8gb3V0Ow0KPiA+
DQo+ID4gKwkvKiBUaGlzIGlzIG5hcGllcidzIGFsZ29yaXRobS4gIFJlZHVjZSB0aGUgb3JpZ2lu
YWwgYmxvY2sgc2l6ZSB0bw0KPiA+ICsJICoNCj4gPiArCSAqIGNvICogZGl2aXNvclt1bml0c11e
aQ0KPiA+ICsJICoNCj4gPiArCSAqIHdoZXJlIGNvID0gYmxrX3NpemUgKyByMS9kaXZpc29yW3Vu
aXRzXTsNCj4gPiArCSAqDQo+ID4gKwkgKiBhbmQgdGhlIHNhbWUgZm9yIHNpemUuICBXZSBzaW1w
bHkgYWRkIHRvIHRoZSBleHBvbmVudCBpLCBiZWNhdXNlDQo+ID4gKwkgKiB0aGUgZmluYWwgY2Fs
Y3VsYXRpb24gd2UncmUgbG9va2luZyBmb3IgaXMNCj4gPiArCSAqDQo+ID4gKwkgKiAoY28xICog
Y28yKSAqIGRpdmlzb3JbdW5pdHNdXmkNCj4gPiArCSAqLw0KPiA+ICsNCj4gPiArDQo+ID4gIAl3
aGlsZSAoYmxrX3NpemUgPj0gZGl2aXNvclt1bml0c10pIHsNCj4gPiAtCQlyZW1haW5kZXIgPSBk
b19kaXYoYmxrX3NpemUsIGRpdmlzb3JbdW5pdHNdKTsNCj4gPiArCQlyMSA9IGRvX2RpdihibGtf
c2l6ZSwgZGl2aXNvclt1bml0c10pOw0KPiA+ICAJCWkrKzsNCj4gPiAgCX0NCj4gPg0KPiA+IC0J
ZXhwID0gZGl2aXNvclt1bml0c10gLyAodTMyKWJsa19zaXplOw0KPiA+IC0JLyoNCj4gPiAtCSAq
IHNpemUgbXVzdCBiZSBzdHJpY3RseSBncmVhdGVyIHRoYW4gZXhwIGhlcmUgdG8gZW5zdXJlIHRo
YXQgcmVtYWluZGVyDQo+ID4gLQkgKiBpcyBncmVhdGVyIHRoYW4gZGl2aXNvclt1bml0c10gY29t
aW5nIG91dCBvZiB0aGUgaWYgYmVsb3cuDQo+ID4gLQkgKi8NCj4gPiAtCWlmIChzaXplID4gZXhw
KSB7DQo+ID4gLQkJcmVtYWluZGVyID0gZG9fZGl2KHNpemUsIGRpdmlzb3JbdW5pdHNdKTsNCj4g
PiAtCQlyZW1haW5kZXIgKj0gYmxrX3NpemU7DQo+ID4gKwl3aGlsZSAoc2l6ZSA+PSBkaXZpc29y
W3VuaXRzXSkgew0KPiA+ICsJCXIyID0gZG9fZGl2KHNpemUsIGRpdmlzb3JbdW5pdHNdKTsNCj4g
PiAgCQlpKys7DQo+ID4gLQl9IGVsc2Ugew0KPiA+IC0JCXJlbWFpbmRlciAqPSBzaXplOw0KPiA+
ICAJfQ0KPiA+DQo+ID4gLQlzaXplICo9IGJsa19zaXplOw0KPiA+IC0Jc2l6ZSArPSByZW1haW5k
ZXIgLyBkaXZpc29yW3VuaXRzXTsNCj4gPiAtCXJlbWFpbmRlciAlPSBkaXZpc29yW3VuaXRzXTsN
Cj4gPiArCS8qIGhlcmUncyB0aGUgbWFnaWMuICBjbzEgKiBjbzIgbWF5IGJlID4gZGl2aXNvcltp
XSwgc28gY29ycmVjdCBmb3INCj4gPiArCSAqIHRoYXQgaW4gdGhlIGV4cG9uZW50IGFuZCBtYWtl
IHN1cmUgdGhhdCB0aGUgYWRkaXRpb25hbCBjb3JyZWN0aW9ucw0KPiA+ICsJICogZnJvbSB0aGUg
cmVtYWluZGVycyBpcyBhZGRlZCBpbi4NCj4gPiArCSAqDQo+ID4gKwkgKiBjbzEgKmNvMiA9IChi
bGtfc2l6ZSArIHIxL2Rpdmlzb3JbdW5pdHNdKSooc2l6ZSArIHIyL2Rpdmlzb3JbdW5pdHNdKQ0K
PiA+ICsJICoNCj4gPiArCSAqIHRoZXJlZm9yZQ0KPiA+ICsJICoNCj4gPiArCSAqIGNvMSpjbzIq
ZGl2aXNvclt1bml0c10gPSBibGtfc2l6ZSpzaXplKmRpdmlzb3JbdW5pdHNdICsNCj4gPiArCSAq
ICAgICAgICAgIHIxKnNpemUgKyByMipzaXplICsgcjEqcjIvZGl2aXNvclt1bml0c10NCj4gPiAr
CSAqDQo+ID4gKwkgKiBkcm9wIHRoZSBsYXN0IHRlcm0gYmVjYXVzZSBpdCdzIHRvbyBzbWFsbCBh
bmQgcGVyZm9ybSB0aGUNCj4gPiArCSAqIGNhbGN1bGF0aW9uIGNsZXZlcmx5IGJ5IGRlY3JlbWV0
aW5nIGkgdG8gYmUgYXV0b21hdGljYWxseSBkZWFsaW5nDQo+ID4gKwkgKiB3aXRoIGV2ZXJ5dGhp
bmcgbXVsdGlwbGllZCBieSBkaXZpc29yW3VuaXRzXSAqLw0KPiA+ICsNCj4gPiArCS0taTsNCj4g
PiArCXNpemUgPSBzaXplICogYmxrX3NpemUgKiBkaXZpc29yW3VuaXRzXSArIHIxICogc2l6ZSAr
IHIyICoNCj4gPiBibGtfc2l6ZTsNCj4gDQo+IFRoZSBsYXN0IHRlcm0gaXMgYWN0dWFsbHkgbm90
IHRoYXQgc21hbGwuIEhlcmUgaXMgYW4gZXhhbXBsZToNCg0KSXQncyBhbHdheXMgPCAxIGluIHRo
ZSBmaW5hbCBlcXVhdGlvbiBiZWNhdXNlIGl0J3MgZGl2aWRlZCBieSB0aGUgc3F1YXJlDQpvZiBk
aXZpc29yW3VuaXRzXS4gIEhvd2V2ZXIsIHRoYXQgY2FuIG1ha2UgYSBjb250cmlidXRpb24gdG8g
dGhlIHJvdW5kDQp1cCwgSSBzdXBwb3NlIGxlYWRpbmcgdG8gdGhlIHRydW5jYXRpb24geW91IHNl
ZQ0KDQo+IHNpemUgPSA4MTkyICBibGtfc2l6ZSA9IDEwMjQNCj4gDQo+ICdBcyBpcycgdGhlIGFs
Z29yaXRobSBnaXZlcyB1cyAnOC4zOCBNQicsIGFuZCBpZiB3ZSBhZGQgIisgcjEgKiByMSAvDQo+
IGRpdmlzb3JbdW5pdHNdIiB3ZSBnZXQgJzguMzkgTUInICh0aGUgY29ycmVjdCBhbnN3ZXIgaXMg
ODE5MiAqIDEwMjQgPQ0KPiA4Mzg4NjA4IHdoaWNoIGlzIDguMzkpLg0KPiANCj4gQm90aCByMSBh
bmQgcjIgYXJlIDwgZGl2aXNvclt1bml0c10gaGVyZSBzbyByMSAqIHIyIHdvbid0IG92ZXJmbG93
IHUzMiwNCj4gSSBzdWdnZXN0IHdlIGFkZCB0aGlzIHRlcm0uDQo+IA0KPiA+DQo+ID4gIAl3aGls
ZSAoc2l6ZSA+PSBkaXZpc29yW3VuaXRzXSkgew0KPiA+ICAJCXJlbWFpbmRlciA9IGRvX2Rpdihz
aXplLCBkaXZpc29yW3VuaXRzXSk7DQo+ID4gQEAgLTgxLDggKzEwMCwxNSBAQCB2b2lkIHN0cmlu
Z19nZXRfc2l6ZSh1NjQgc2l6ZSwgdTY0IGJsa19zaXplLCBjb25zdCBlbnVtIHN0cmluZ19zaXpl
X3VuaXRzIHVuaXRzLA0KPiA+ICAJfQ0KPiA+DQo+ID4gIAlzZl9jYXAgPSBzaXplOw0KPiA+IC0J
Zm9yIChqID0gMDsgc2ZfY2FwKjEwIDwgMTAwMDsgaisrKQ0KPiA+ICsJcm91bmQgPSA1MDA7DQo+
ID4gKwlmb3IgKGogPSAwOyBzZl9jYXAqMTAgPCAxMDAwOyBqKyspIHsNCj4gPiAgCQlzZl9jYXAg
Kj0gMTA7DQo+ID4gKwkJcm91bmQgLz0gMTA7DQo+ID4gKwl9DQo+ID4gKw0KPiA+ICsJLyogYWRk
IGEgNSB0byB0aGUgZGlnaXQgYmVsb3cgd2hhdCB3aWxsIGJlIHByaW50ZWQgdG8gZW5zdXJlDQo+
ID4gKwkgKiBhbiBhcml0aG1ldGljYWwgcm91bmQgdXAgKi8NCj4gPiArCXJlbWFpbmRlciArPSBy
b3VuZDsNCj4gPg0KPiA+ICAJaWYgKGopIHsNCj4gPiAgCQlyZW1haW5kZXIgKj0gMTAwMDsNCj4g
DQo+IENhbiBJIHBvc3QgdGhpcyBzb2x1dGlvbiB3aXRoIHlvdXIgU3VnZ2VzdGVkLWJ5IG9yIGRv
IHlvdSBwbGFuIHRvIGRvIGl0DQo+IHlvdXJzZWxmPw0KDQpJdCB3YXMgYSBzdWdnZXN0aW9uIHdo
ZW4gSSBleHBsYWluZWQgd2hhdCB0aGUgbWlzc2luZyBzb3VyY2VzIG9mDQpwcmVjaXNpb24gd2Vy
ZSwgSSBkb24ndCB0aGluayBpdCdzIHJlYWxseSBhIHN1Z2dlc3Rpb24gd2hlbiBpdCBjb21lcw0K
d2l0aCBhbiBleGVtcGxhcnkgcGF0Y2guICBIb3dldmVyLCB0aGUgd2hvbGUgdGhpbmcgbmVlZHMg
cG9saXNoaW5nDQpiZWNhdXNlIGFsbCB0aGUgZGl2aXNpb25zIG5lZWQgdG8gYmUgZWxpbWluYXRl
ZCwgc2luY2UgdGhleSdyZSBhIGh1Z2UNCnNvdXJjZSBvZiBwcm9ibGVtcyBmb3IgbW9zdCAzMiBi
aXQgQ1BVcywgc28gSSBjYW4gZml4IGl0IGFsbCB0aGUgd2F5IGFuZA0KcmVwb3N0Lg0KDQpKYW1l
cw0KDQo=
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1261892

On Tue, Nov 03 2015, James Bottomley <jbottomley@odin.com> wrote:

>
> It was a suggestion when I explained what the missing sources of
> precision were, I don't think it's really a suggestion when it comes
> with an exemplary patch.

ex·em·pla·ry
adjective

    1.
    serving as a desirable model; representing the best of its kind.

Said exemplary patch produces "1.10 KiB" for size=2047,
blk_size=1. (This is caused by the introduction of rounding, and is
probably fixable.)

James, I do understand the algorithm you're trying to use. What I don't
understand is why you insist on using the approach of reducing size and
blk_size all the way before multiplying them. It seems much simpler to
just reduce them till they're below U32_MAX (not keeping track of any
remainders at that point), multiply them, and then proceed as usual,
This avoids having to deal with weird cross-multiplication terms, gives
more accurate results (yes, I tested that) and avoids the extra 64/32
division you introduce by decrementing i.

Rasmus

To be precise, the body I suggest is

	while (blk_size > U32_MAX) {
		do_div(blk_size, divisor[units]);
		i++;
	}
	while (size > U32_MAX) {
		do_div(size, divisor[units]);
		i++;
	}
	size *= blk_size;
	while (size > divisor[units]) {
		remainder = do_div(size, divisor[units]);
		i++;
	}

whether the last one should be > or >= is debatable; I think 1024 KiB is
better than 1.00 MiB.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1261903 — Re: [PATCH v3 1/4] lib/string_helpers: change blk_size to u32 for string_get_size() interface

T24gVHVlLCAyMDE1LTExLTAzIGF0IDIxOjU3ICswMTAwLCBSYXNtdXMgVmlsbGVtb2VzIHdyb3Rl
Og0KPiBPbiBUdWUsIE5vdiAwMyAyMDE1LCBKYW1lcyBCb3R0b21sZXkgPGpib3R0b21sZXlAb2Rp
bi5jb20+IHdyb3RlOg0KPiANCj4gPg0KPiA+IEl0IHdhcyBhIHN1Z2dlc3Rpb24gd2hlbiBJIGV4
cGxhaW5lZCB3aGF0IHRoZSBtaXNzaW5nIHNvdXJjZXMgb2YNCj4gPiBwcmVjaXNpb24gd2VyZSwg
SSBkb24ndCB0aGluayBpdCdzIHJlYWxseSBhIHN1Z2dlc3Rpb24gd2hlbiBpdCBjb21lcw0KPiA+
IHdpdGggYW4gZXhlbXBsYXJ5IHBhdGNoLg0KPiANCj4gZXjCt2VtwrdwbGHCt3J5DQo+IGFkamVj
dGl2ZQ0KPiANCj4gICAgIDEuDQo+ICAgICBzZXJ2aW5nIGFzIGEgZGVzaXJhYmxlIG1vZGVsOyBy
ZXByZXNlbnRpbmcgdGhlIGJlc3Qgb2YgaXRzIGtpbmQuDQo+IA0KPiBTYWlkIGV4ZW1wbGFyeSBw
YXRjaCBwcm9kdWNlcyAiMS4xMCBLaUIiIGZvciBzaXplPTIwNDcsDQo+IGJsa19zaXplPTEuIChU
aGlzIGlzIGNhdXNlZCBieSB0aGUgaW50cm9kdWN0aW9uIG9mIHJvdW5kaW5nLCBhbmQgaXMNCj4g
cHJvYmFibHkgZml4YWJsZS4pDQo+IA0KPiBKYW1lcywgSSBkbyB1bmRlcnN0YW5kIHRoZSBhbGdv
cml0aG0geW91J3JlIHRyeWluZyB0byB1c2UuIFdoYXQgSSBkb24ndA0KPiB1bmRlcnN0YW5kIGlz
IHdoeSB5b3UgaW5zaXN0IG9uIHVzaW5nIHRoZSBhcHByb2FjaCBvZiByZWR1Y2luZyBzaXplIGFu
ZA0KPiBibGtfc2l6ZSBhbGwgdGhlIHdheSBiZWZvcmUgbXVsdGlwbHlpbmcgdGhlbS4gSXQgc2Vl
bXMgbXVjaCBzaW1wbGVyIHRvDQo+IGp1c3QgcmVkdWNlIHRoZW0gdGlsbCB0aGV5J3JlIGJlbG93
IFUzMl9NQVggKG5vdCBrZWVwaW5nIHRyYWNrIG9mIGFueQ0KPiByZW1haW5kZXJzIGF0IHRoYXQg
cG9pbnQpLCBtdWx0aXBseSB0aGVtLCBhbmQgdGhlbiBwcm9jZWVkIGFzIHVzdWFsLA0KPiBUaGlz
IGF2b2lkcyBoYXZpbmcgdG8gZGVhbCB3aXRoIHdlaXJkIGNyb3NzLW11bHRpcGxpY2F0aW9uIHRl
cm1zLCBnaXZlcw0KPiBtb3JlIGFjY3VyYXRlIHJlc3VsdHMgKHllcywgSSB0ZXN0ZWQgdGhhdCkg
YW5kIGF2b2lkcyB0aGUgZXh0cmEgNjQvMzINCj4gZGl2aXNpb24geW91IGludHJvZHVjZSBieSBk
ZWNyZW1lbnRpbmcgaS4NCg0KV2VsbCwgd29vZCBhbmQgdHJlZXMsIEkgdGhpbmsuICBJIGRvbid0
IGJlbGlldmUgdGhlcmUncyBhbnkgbW9yZQ0KYWNjdXJhY3kgd2l0aCB0aGUgc2Vjb25kIG9yZGVy
IHRlcm0sIGJ1dCBpdCBpcyBhIGxvdCBzaW1wbGVyIGZvciBhbnlvbmUNCnRvIHVuZGVyc3RhbmQu
ICBJJ2xsIHBvc3QgYSB2Mi4NCg0KSmFtZXMNCg0K
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web