linux-kernel - RE: [PATCH v2] overflow: optimize struct

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <43ac488d0a83486ca6d969643c7b531d@AcuMS.aculab.com>
Date: Wed, 11 Sep 2024 16:46:51 +0000
From: David Laight <David.Laight@...LAB.COM>
To: 'Vincent MAILHOL' <mailhol.vincent@...adoo.fr>
CC: Kees Cook <kees@...nel.org>, "Gustavo A . R . Silva"
	<gustavoars@...nel.org>, "linux-hardening@...r.kernel.org"
	<linux-hardening@...r.kernel.org>, "linux-kernel@...r.kernel.org"
	<linux-kernel@...r.kernel.org>
Subject: RE: [PATCH v2] overflow: optimize struct_size() calculation

...
> > [1] Both the '+' and '*' have extra code to detect overflow and return
> >   a 'big' value that will cause kmalloc() to return NULL.
> > I've not looked at the generated code but it is likely to be horrid
> >   (especially the check for multiply overflowing).
> > In this case there are enough constants that the alternative check:
> >         if (count > (MAX_SIZE - sizeof (*s)) / sizeof (s->member))
> >                 size = MAX_SIZE;
> >         else
> >                 size = sizeof (*s) + count * sizeof (s->member);
> > is fine and only has one conditional in it.
> > In some cases the compiler may already know that the count is small enough.
> 
> Indeed. If count is small enough, the code isn't that horrid. If I
> take this example:
> 
>   size_t foo(u32 count)
>   {
>           return struct_size_t(struct s, fam, count);
>   }
> 
> I got this code:

What happens if the flex-array is larger than 1 byte - so a multiply is needed.
Probably worth testing something that isn't a power of 2.
Also check 32bit archs -godbolt can help.

	David

> 
>   0000000000000010 <foo>:
>     10:   f3 0f 1e fa             endbr64
>     14:   89 f8                   mov    %edi,%eax
>     16:   48 83 c0 10             add    $0x10,%rax
>     1a:   e9 00 00 00 00          jmp    1f <foo+0xf>

Add -d to objdump to get the relocation printed.
(I think this is a build where 'ret' isn't allowed :-)

	David

> 
> Here, no SIZE_MAX because the multiplication can not wraparound
> regardless of the value of count. It is only after changing the type
> of count to u64 that the compiler will emit a comparison:
> 
> 0000000000000010 <foo>:
>   10:   f3 0f 1e fa             endbr64
>   14:   48 8d 47 10             lea    0x10(%rdi),%rax
>   18:   48 83 ff f0             cmp    $0xfffffffffffffff0,%rdi
>   1c:   48 c7 c2 ff ff ff ff    mov    $0xffffffffffffffff,%rdx
>   23:   48 0f 43 c2             cmovae %rdx,%rax
>   27:   e9 00 00 00 00          jmp    2c <foo+0x1c>
> 
> For reference, this is the code after applying my patch, with count as a u32:
> 
>   0000000000000010 <foo>:
>     10:   f3 0f 1e fa             endbr64
>     14:   89 f8                   mov    %edi,%eax
>     16:   ba 10 00 00 00          mov    $0x10,%edx
>     1b:   48 83 c0 0c             add    $0xc,%rax
>     1f:   48 39 d0                cmp    %rdx,%rax
>     22:   48 0f 42 c2             cmovb  %rdx,%rax
>     26:   e9 00 00 00 00          jmp    2b <foo+0x1b>
> 
> and with count as a u64:
> 
>   0000000000000010 <foo>:
>     10:   f3 0f 1e fa             endbr64
>     14:   48 83 c7 0c             add    $0xc,%rdi
>     18:   72 11                   jb     2b <foo+0x1b>
>     1a:   b8 10 00 00 00          mov    $0x10,%eax
>     1f:   48 39 c7                cmp    %rax,%rdi
>     22:   48 0f 43 c7             cmovae %rdi,%rax
>     26:   e9 00 00 00 00          jmp    2b <foo+0x1b>
>     2b:   48 83 c8 ff             or     $0xffffffffffffffff,%rax
>     2f:   e9 00 00 00 00          jmp    34 <foo+0x24>
> 
> Thank you for your comments!
> 
> 
> Yours sincerely,
> Vincent Mailhol

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)