netdev - Re: [PATCH net-next v8 03/10] lib: packing: add pack_fields() and unpack

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-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <843bdcd0-2284-43c0-81a1-feb4d1f910ea@intel.com>
Date: Wed, 4 Dec 2024 16:23:48 -0800
From: Jacob Keller <jacob.e.keller@...el.com>
To: Vladimir Oltean <vladimir.oltean@....com>
CC: Andrew Morton <akpm@...ux-foundation.org>, Eric Dumazet
	<edumazet@...gle.com>, Jakub Kicinski <kuba@...nel.org>, Paolo Abeni
	<pabeni@...hat.com>, Tony Nguyen <anthony.l.nguyen@...el.com>, "Przemek
 Kitszel" <przemyslaw.kitszel@...el.com>, Masahiro Yamada
	<masahiroy@...nel.org>, netdev <netdev@...r.kernel.org>
Subject: Re: [PATCH net-next v8 03/10] lib: packing: add pack_fields() and
 unpack_fields()



On 12/4/2024 3:52 PM, Vladimir Oltean wrote:
> On Wed, Dec 04, 2024 at 03:24:59PM -0800, Jacob Keller wrote:
>> On 12/4/2024 9:12 AM, Vladimir Oltean wrote:
>> Thus, all the array definitions are off-by-one, leading to the last one
>> being out-of-bounds.
> 
> ah :-/
> 
> I should have paid more attention, sorry.
> 

It happens to the best of us. As they say, in programming there are 3
hard problems: naming things, and off-by-one errors.

>>>  		printf("})\n\n");
>>>  	}
>>>  
>>>
>>> The problem is that, for some reason, it introduces this sparse warning:
>>>
>>> ../lib/packing_test.c:436:9: warning: invalid access past the end of 'test_fields' (24 24)
>>> ../lib/packing_test.c:448:9: warning: invalid access past the end of 'test_fields' (24 24)
>>>
>>> Nobody accesses past element 6 (ARRAY_SIZE) of test_fields[]. I ran the
>>
>> The array size is 6, but we try to access element 6 which is one past
>> the array... good old off-by-one error :)
>>
>> There is one further complication which is that the nested statement
>> expressions ({ ... }) for each CHECK_PACKED_FIELD_N eventually make GCC
>> confused, as it doesn't seem to keep track of the types very well.
> 
> I only tested with clang which didn't complain, sorry.
> 

Yea, I have had mixed luck between compilers. Masahiro had suggested a
for-loop which clang handles just fine, but GCC doesn't bother parsing.
I don't like only having the checks on some compilers.

>> I fixed that by changing the individual CHECK_PACKED_FIELD_N to be
>> non-statement expressions, and then wrapping their calls in the
>> builtin_choose_expr() with ({ ... }), which prevents us from creating
>> too many expression layers for GCC. It actually results in identical
>> code being evaluated as with the old version but now with a constant
>> scaling of the text size: 2 lines per additional check.
> 
> Yeah, I think that was the logical next development step. By doing this now,
> I think you just saved an extra patch iteration, thanks.
> 
>> Of course the complexity scales linearly, but that means our text size
>> no longer scales with O(n*log(n)) but just as O(N).
> 
> Well, technically, the number of lines of code required, in "naive" form,
> for overlap checking of arrays up to length N should be N*(N+1)/2, which
> "grows quicker" than N*log(N).
> 

Right. I was thinking of with this ordered check, you have O(N) scaling
for the number of checks, but that means that we have O(N^2) number of
lines as we scale the number of checks up. Each macro required ~N lines,
but we have N macros, so we get N^2 number of lines.

> But I don't think we can talk about algorithmic complexity here (big O
> notation), which stays the same (linear) in both ways of expressing the
> same thing.
>

Right. The computation stays the same. But now, we only need 4 lines per
check, because each check is built on top of the previous ones recursively.

>> Its fantastic improvement, thanks for the suggestion. I'll have v9 out
>> with these improvements soon.
> 
> And thanks for staying online with this effort for more than an entire
> kernel development cycle! Looking forward to v9.

Yea. This has certainly taken longer than I would have liked, but I'm
happy with the end result. We got something much better, even if it took
fiddling around in the wrong areas for longer than I would have liked. I
think these changes are great for ice, and also make packing much easier
to use for others on the long run. Hopefully we can see more adoption now.