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 for Android: free password hash cracker in your pocket

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

Message-ID: <20241204235209.v4xjweehhp5knbew@skbuf>
Date: Thu, 5 Dec 2024 01:52:09 +0200
From: Vladimir Oltean <vladimir.oltean@....com>
To: Jacob Keller <jacob.e.keller@...el.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 Wed, Dec 04, 2024 at 03:24:59PM -0800, Jacob Keller wrote:
> On 12/4/2024 9:12 AM, Vladimir Oltean wrote:
> > And there's one more thing I tried, which mostly worked. That was to
> > express CHECK_PACKED_FIELDS_N in terms of CHECK_PACKED_FIELDS_N-1.
> > This further reduced the auto-generated code size from 1478 lines to 302
> > lines, which I think is appealing.
> > 
> 
> I figured it out! There are two key issues involved:
> 
> > diff --git a/scripts/gen_packed_field_checks.c b/scripts/gen_packed_field_checks.c
> > index fabbb741c9a8..bac85c04ef20 100644
> > --- a/scripts/gen_packed_field_checks.c
> > +++ b/scripts/gen_packed_field_checks.c
> > @@ -10,9 +10,10 @@ int main(int argc, char **argv)
> >  	for (int i = 1; i <= MAX_PACKED_FIELD_SIZE; i++) {
> >  		printf("#define CHECK_PACKED_FIELDS_%d(fields) ({ \\\n", i);
> >  
> > -		for (int j = 0; j < i; j++)
> > -			printf("\tCHECK_PACKED_FIELD(fields, %d); \\\n", j);
> > +		if (i != 1)
> > +			printf("\tCHECK_PACKED_FIELDS_%d(fields); \\\n", i - 1);
> >  
> > +		printf("\tCHECK_PACKED_FIELD(fields, %d); \\\n", i);
> 
> This needs to be i - 1, since arrays are 0-indexed, so this code expands
> to checking the wrong value.
> 
> CHECK_PACKED_FIELDS_1 needs to become
> 
> CHECK_PACKED_FIELD(fields, 0)
> 
> but this code makes it:
> 
> CHECK_PACKED_FIELD(fields, 1)
> 
> 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.

> >  		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.

> 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).

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.

> 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.