xt_hashlimig build error (was Re: [RFC 01/17] x86/asm/64: Remove the restore_c_regs_and_iret label)

xt_hashlimig build error (was Re: [RFC 01/17] x86/asm/64: Remove the restore_c_regs_and_iret label)

[Linus Torvalds]

On Thu, Sep 7, 2017 at 3:29 AM, Ingo Molnar <mingo@kernel.org> wrote:
>
> not the best of kernels, 32-bit allyesconfig doesn't even appear to build:
>
>   net/netfilter/xt_hashlimit.o: In function `hashlimit_mt_common.isra.6':
>   xt_hashlimit.c:(.text+0x1146): undefined reference to `__udivdi3'

I think this is due to commit bea74641e378 ("netfilter: xt_hashlimit:
add rate match mode").

It adds a 64-bit divide in user2rate_bytes() afaik, and to make things
worse it seems to be a really stupid one too.

Although I guess "worse" is not bad when the stupidity of it should
mean that it's easy to avoid the 64-bit issue.

Oddly, user2rate() that actually *does* need a 64-bit divide, seems to
do it right and use "div64_u64()" to do so.

But user2rate_bytes() could easily avoid any 64-bit issues, since it
divides the max 32-bit (unsigned) number with a 64-bit unsigned
number.

It would be easy to just say

 - "if high 32 bits are set, result is 0"

 - else do a 32-bit divide

or just use "div64_u64()" in that code too.

But honestly, that math is odd in other ways too (is that "r-1"
_supposed_ to underflow to -1 for large 'user' counts?), so somebody
needs to look at that logic.

And there might be some other 64-bit divide I missed, so please,
netfilter people, check the 32-bit build.

                  Linus

Re: xt_hashlimig build error (was Re: [RFC 01/17] x86/asm/64: Remove the restore_c_regs_and_iret label)

[Vishwanath Pai]

On 09/07/2017 01:51 PM, Linus Torvalds wrote:
> On Thu, Sep 7, 2017 at 3:29 AM, Ingo Molnar <mingo@kernel.org> wrote:
>>
>> not the best of kernels, 32-bit allyesconfig doesn't even appear to build:
>>
>>   net/netfilter/xt_hashlimit.o: In function `hashlimit_mt_common.isra.6':
>>   xt_hashlimit.c:(.text+0x1146): undefined reference to `__udivdi3'
> 
> I think this is due to commit bea74641e378 ("netfilter: xt_hashlimit:
> add rate match mode").
> 
> It adds a 64-bit divide in user2rate_bytes() afaik, and to make things
> worse it seems to be a really stupid one too.
> 
> Although I guess "worse" is not bad when the stupidity of it should
> mean that it's easy to avoid the 64-bit issue.
> 
> Oddly, user2rate() that actually *does* need a 64-bit divide, seems to
> do it right and use "div64_u64()" to do so.
> 
> But user2rate_bytes() could easily avoid any 64-bit issues, since it
> divides the max 32-bit (unsigned) number with a 64-bit unsigned
> number.
> 
> It would be easy to just say
> 
>  - "if high 32 bits are set, result is 0"
> 
>  - else do a 32-bit divide
> 
> or just use "div64_u64()" in that code too.
> 
> But honestly, that math is odd in other ways too (is that "r-1"
> _supposed_ to underflow to -1 for large 'user' counts?), so somebody
> needs to look at that logic.
> 
> And there might be some other 64-bit divide I missed, so please,
> netfilter people, check the 32-bit build.
> 
>                   Linus
> 

Sorry about the build failure, we have already queued up a fix for this:
https://patchwork.ozlabs.org/patch/810772/

I agree, this could've been easily avoided, I happened to overlook this
particular line. There are other places in xt_hashlimit where we use
64bit division and I believe we have already covered those cases using
div64_u64.

- Vishwanath

Re: xt_hashlimig build error (was Re: [RFC 01/17] x86/asm/64: Remove the restore_c_regs_and_iret label)

[Linus Torvalds]

On Thu, Sep 7, 2017 at 11:25 AM, Vishwanath Pai <vpai@akamai.com> wrote:
> On 09/07/2017 01:51 PM, Linus Torvalds wrote:
>>
>> But honestly, that math is odd in other ways too (is that "r-1"
>> _supposed_ to underflow to -1 for large 'user' counts?), so somebody
>> needs to look at that logic.
>
> Sorry about the build failure, we have already queued up a fix for this:
> https://patchwork.ozlabs.org/patch/810772/

Note: that patch has *exactly* the issue I was talking about above.

Doing that

    if (user > 0xFFFFFFFFULL)
        return 0;

is different from the old code, which used to result in a zero in the
divide, and then

    r = (r - 1) << 4;

would cause it to return a large value.

So the patch in question doesn't just fix the build error, it
completely changes the semantics of the function too.

I *think* the new behavior is likely what you want, but these kinds of
things should be _described_.

Also, even with the patch, we have garbage:

    0xFFFFFFFFULL / (u32)user

why is that sub-expression pointlessly doing a 64-bit divide with a
32-bit number? The compiler is hopefully smart enough to point things
out, but that "ULL" really is _wrong_ there, and could cause a stupid
compiler to still do a 64-bit divide (although hopefully the simpler
version that is 64/32).

So please clarify both the correct behavior _and_ the actual typing of
the divide, ok?

                 Linus

Re: xt_hashlimig build error (was Re: [RFC 01/17] x86/asm/64: Remove the restore_c_regs_and_iret label)

[Vishwanath Pai]

On 09/07/2017 02:43 PM, Linus Torvalds wrote:
> Note: that patch has *exactly* the issue I was talking about above.
> 
> Doing that
> 
>     if (user > 0xFFFFFFFFULL)
>         return 0;
> 
> is different from the old code, which used to result in a zero in the
> divide, and then
> 
>     r = (r - 1) << 4;
> 
> would cause it to return a large value.
> 
> So the patch in question doesn't just fix the build error, it
> completely changes the semantics of the function too.
> 
> I *think* the new behavior is likely what you want, but these kinds of
> things should be _described_.
> 
> Also, even with the patch, we have garbage:
> 
>     0xFFFFFFFFULL / (u32)user
> 
> why is that sub-expression pointlessly doing a 64-bit divide with a
> 32-bit number? The compiler is hopefully smart enough to point things
> out, but that "ULL" really is _wrong_ there, and could cause a stupid
> compiler to still do a 64-bit divide (although hopefully the simpler
> version that is 64/32).
> 
> So please clarify both the correct behavior _and_ the actual typing of
> the divide, ok?
> 
>                  Linus

The value of 'user' is sent from userspace, which is the return value of
this function:

static uint64_t bytes_to_cost(uint32_t bytes)
{
        uint32_t r = bytes >> XT_HASHLIMIT_BYTE_SHIFT;
        return UINT32_MAX / (r+1);
}

What user2rate_bytes() is trying to do is the opposite of above. The
size of 'user' is 64bit for a different reason altogether, but in this
case it is guaranteed to be always < U32_MAX. And hence using 64bit
divide is completely pointless (which I now realize).

Writing U32INT_MAX as 0xFFFFFFFFULL was a mistake on my part. I could
have avoided all of this by using built-in constants instead of trying
to define them myself. I will rewrite the function as below and send out
another patch:

static u64 user2rate_bytes(u64 user)
{
        u64 r;

        r = user ? U32_MAX / (u32) user : U32_MAX;
        r = (r - 1) << XT_HASHLIMIT_BYTE_SHIFT;
        return r;
}

-Vishwanath

RE: xt_hashlimig build error (was Re: [RFC 01/17] x86/asm/64: Remove the restore_c_regs_and_iret label)

[Lubashev, Igor]

Since user is u64, it is best to have a predictable return value for all possible values of user.  So maybe:

static u64 user2rate_bytes(u64 user)
{
        u64 r;

        r = user ? U32_MAX / (u32) min(user, U32_MAX) : U32_MAX;
        r = (r - 1) << XT_HASHLIMIT_BYTE_SHIFT;
        return r;
}


-----Original Message-----
From: Vishwanath Pai [mailto:vpai@akamai.com] 
Sent: Thursday, September 07, 2017 4:17 PM
To: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Ingo Molnar <mingo@kernel.org>; Lubashev, Igor <ilubashe@akamai.com>; Hunt, Joshua <johunt@akamai.com>; Pablo Neira Ayuso <pablo@netfilter.org>; Borislav Petkov <bp@alien8.de>; Andy Lutomirski <luto@kernel.org>; the arch/x86 maintainers <x86@kernel.org>; Linux Kernel Mailing List <linux-kernel@vger.kernel.org>; Brian Gerst <brgerst@gmail.com>; Andrew Cooper <andrew.cooper3@citrix.com>; Juergen Gross <jgross@suse.com>; Boris Ostrovsky <boris.ostrovsky@oracle.com>; Kees Cook <keescook@chromium.org>; Andrew Morton <akpm@linux-foundation.org>; David S. Miller <davem@davemloft.net>; Arnd Bergmann <arnd@arndb.de>
Subject: Re: xt_hashlimig build error (was Re: [RFC 01/17] x86/asm/64: Remove the restore_c_regs_and_iret label)

On 09/07/2017 02:43 PM, Linus Torvalds wrote:
> Note: that patch has *exactly* the issue I was talking about above.
> 
> Doing that
> 
>     if (user > 0xFFFFFFFFULL)
>         return 0;
> 
> is different from the old code, which used to result in a zero in the 
> divide, and then
> 
>     r = (r - 1) << 4;
> 
> would cause it to return a large value.
> 
> So the patch in question doesn't just fix the build error, it 
> completely changes the semantics of the function too.
> 
> I *think* the new behavior is likely what you want, but these kinds of 
> things should be _described_.
> 
> Also, even with the patch, we have garbage:
> 
>     0xFFFFFFFFULL / (u32)user
> 
> why is that sub-expression pointlessly doing a 64-bit divide with a 
> 32-bit number? The compiler is hopefully smart enough to point things 
> out, but that "ULL" really is _wrong_ there, and could cause a stupid 
> compiler to still do a 64-bit divide (although hopefully the simpler 
> version that is 64/32).
> 
> So please clarify both the correct behavior _and_ the actual typing of 
> the divide, ok?
> 
>                  Linus

The value of 'user' is sent from userspace, which is the return value of this function:

static uint64_t bytes_to_cost(uint32_t bytes) {
        uint32_t r = bytes >> XT_HASHLIMIT_BYTE_SHIFT;
        return UINT32_MAX / (r+1);
}

What user2rate_bytes() is trying to do is the opposite of above. The size of 'user' is 64bit for a different reason altogether, but in this case it is guaranteed to be always < U32_MAX. And hence using 64bit divide is completely pointless (which I now realize).

Writing U32INT_MAX as 0xFFFFFFFFULL was a mistake on my part. I could have avoided all of this by using built-in constants instead of trying to define them myself. I will rewrite the function as below and send out another patch:

static u64 user2rate_bytes(u64 user)
{
        u64 r;

        r = user ? U32_MAX / (u32) user : U32_MAX;
        r = (r - 1) << XT_HASHLIMIT_BYTE_SHIFT;
        return r;
}

-Vishwanath

Re: xt_hashlimig build error (was Re: [RFC 01/17] x86/asm/64: Remove the restore_c_regs_and_iret label)

[Linus Torvalds]

On Thu, Sep 7, 2017 at 1:16 PM, Vishwanath Pai <vpai@akamai.com> wrote:
>
> Writing U32INT_MAX as 0xFFFFFFFFULL was a mistake on my part. I could
> have avoided all of this by using built-in constants instead of trying
> to define them myself. I will rewrite the function as below and send out
> another patch:
>
> static u64 user2rate_bytes(u64 user)
> {
>         u64 r;
>
>         r = user ? U32_MAX / (u32) user : U32_MAX;
>         r = (r - 1) << XT_HASHLIMIT_BYTE_SHIFT;
>         return r;
> }

No, that is *still* wrong.

In particular, the test for "user" being zero is done in 64 bits, but
then when you do the divide, the cast to (u32) will take the low 32
bits - which may be zero, because only upper bits were set.

So now you get a divide-by-zero.

What seems to be going on is that a value larger than UINT32_MAX is
basically "invalid", since the reverse function cannot possibly
generate that.

So one possible fix is to just make that an error case in the caller,
and then make user2rate_bytes() not take (or return) "u64" at all, but
simply use u32.

Please be more careful here.

              Linus

Re: xt_hashlimig build error (was Re: [RFC 01/17] x86/asm/64: Remove the restore_c_regs_and_iret label)

[Vishwanath Pai]

On 09/07/2017 04:45 PM, Linus Torvalds wrote:
> On Thu, Sep 7, 2017 at 1:16 PM, Vishwanath Pai <vpai@akamai.com> wrote:
>>
>> Writing U32INT_MAX as 0xFFFFFFFFULL was a mistake on my part. I could
>> have avoided all of this by using built-in constants instead of trying
>> to define them myself. I will rewrite the function as below and send out
>> another patch:
>>
>> static u64 user2rate_bytes(u64 user)
>> {
>>         u64 r;
>>
>>         r = user ? U32_MAX / (u32) user : U32_MAX;
>>         r = (r - 1) << XT_HASHLIMIT_BYTE_SHIFT;
>>         return r;
>> }
> 
> No, that is *still* wrong.
> 
> In particular, the test for "user" being zero is done in 64 bits, but
> then when you do the divide, the cast to (u32) will take the low 32
> bits - which may be zero, because only upper bits were set.
> 
> So now you get a divide-by-zero.
> 
> What seems to be going on is that a value larger than UINT32_MAX is
> basically "invalid", since the reverse function cannot possibly
> generate that.
> 
> So one possible fix is to just make that an error case in the caller,
> and then make user2rate_bytes() not take (or return) "u64" at all, but
> simply use u32.
> 
> Please be more careful here.
> 
>               Linus
> 

Yes, that is true. Thanks for pointing it out. I will change the user
param to 'u32', and also change the return type to u32 as well. I will
add a check in hashlimit_mt_check() to make sure the userspace never
sends anything > U32_MAX and error out if they do.

Thanks,
Vishwanath