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:

quoted

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:

quoted

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.

quoted

 		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.