netdev - Re: [PATCH bpf-next 2/7] lib: reciprocal_div: implement the improved algorithm on the paper mentioned

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAMsOgNDapubGdbP=nB8r8Mps5pMtjK9CSr3sn-LvDCOvyCg4Wg@mail.gmail.com>
Date:   Thu, 28 Jun 2018 20:02:43 +0100
From:   Jiong Wang <jiong.wang@...ronome.com>
To:     Song Liu <liu.song.a23@...il.com>
Cc:     Jakub Kicinski <jakub.kicinski@...ronome.com>,
        Alexei Starovoitov <alexei.starovoitov@...il.com>,
        Daniel Borkmann <daniel@...earbox.net>,
        oss-drivers@...ronome.com, Networking <netdev@...r.kernel.org>
Subject: Re: [PATCH bpf-next 2/7] lib: reciprocal_div: implement the improved
 algorithm on the paper mentioned

On Tue, Jun 26, 2018 at 7:21 AM, Song Liu <liu.song.a23@...il.com> wrote:
> On Sun, Jun 24, 2018 at 8:54 PM, Jakub Kicinski
> <jakub.kicinski@...ronome.com> wrote:
>> From: Jiong Wang <jiong.wang@...ronome.com>

<snip>

>> +
>> +struct reciprocal_value_adv reciprocal_value_adv(u32 d, u8 prec)
>> +{
>> +       struct reciprocal_value_adv R;
>> +       u32 l, post_shift;
>> +       u64 mhigh, mlow;
>> +
>> +       l = fls(d - 1);
>> +       post_shift = l;
>> +       /* NOTE: mlow/mhigh could overflow u64 when l == 32 which means d has
>> +        * MSB set. This case needs to be handled before calling
>> +        * "reciprocal_value_adv", please see the comment at
>> +        * include/linux/reciprocal_div.h.
>> +        */
>
> Shall we handle l == 32 case better? I guess the concern here is extra
> handling may
> slow down the fast path?

The implementation of "reciprocal_value_adv" hasn't considered l  ==
32 which will make the code more complex.

As described at the pseudo code about how to call
"reciprocal_value_adv" in include/linux/reciprocal_div.h, l == 32
means the MSB of dividend is set, so the result of unsigned
divisor/dividend could only be 0 or 1, so the divide result could be
easily get by a comparison then conditional move 0 or 1 to the result.

> If that's the case, we should at least add a WARNING on the slow path.

OK, I will add a pr_warn inside "reciprocal_value_adv" when l == 32 is
triggered.

Thanks,
Jiong