linux-kernel - Re: [PATCH v2 1/2] util_macros.h: fix/rework find

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: <CA+GgBR-a050NUMB4Z=Q1UhqjAcKRVVw4k+S9uBZp6iRGqHkB6A@mail.gmail.com>
Date: Wed, 6 Nov 2024 16:03:36 +0200
From: Alexandru Ardelean <aardelean@...libre.com>
To: Andrew Morton <akpm@...ux-foundation.org>
Cc: linux-iio@...r.kernel.org, linux-kernel@...r.kernel.org, jic23@...nel.org, 
	bartosz.golaszewski@...aro.org, gregkh@...uxfoundation.org
Subject: Re: [PATCH v2 1/2] util_macros.h: fix/rework find_closest() macros

On Wed, Nov 6, 2024 at 1:08 AM Andrew Morton <akpm@...ux-foundation.org> wrote:
>
> On Tue,  5 Nov 2024 16:54:05 +0200 Alexandru Ardelean <aardelean@...libre.com> wrote:
>
> > A bug was found in the find_closest() (find_closest_descending() is also
> > affected after some testing), where for certain values with small
> > progressions, the rounding (done by averaging 2 values) causes an incorrect
> > index to be returned.
>
> Convincing changelog, thanks.
>
> > -#define find_closest(x, a, as) __find_closest(x, a, as, <=)
> > +#define find_closest(x, a, as)                                               \
> > +({                                                                   \
> > +     typeof(as) __fc_i, __fc_as = (as) - 1;                          \
> > +     long __fc_mid_x, __fc_x = (x);                                  \
> > +     long __fc_left, __fc_right;                                     \
> > +     typeof(*a) const *__fc_a = (a);                                 \
> > +     for (__fc_i = 0; __fc_i < __fc_as; __fc_i++) {                  \
> > +             __fc_mid_x = (__fc_a[__fc_i] + __fc_a[__fc_i + 1]) / 2; \
> > +             if (__fc_x <= __fc_mid_x) {                             \
> > +                     __fc_left = __fc_x - __fc_a[__fc_i];            \
> > +                     __fc_right = __fc_a[__fc_i + 1] - __fc_x;       \
> > +                     if (__fc_right < __fc_left)                     \
> > +                             __fc_i++;                               \
> > +                     break;                                          \
> > +             }                                                       \
> > +     }                                                               \
> > +     (__fc_i);                                                       \
> > +})
> >
> > ...
> >
> > +#define find_closest_descending(x, a, as)                            \
>
> Boy these things are hard to read.  They're also bloaty and I'm
> counting 36ish callsites!
>

Yeah, they're not easy on the eyes at first.
But you do get used to them, after spending some time trying to
understand why they're not working for some values.

> Can we fix both issues by just giving up on the macro approach and
> reimplement them in out-of-line C code?  All the sites I looked at are
> using 32-bit quantities - a mix of signed and unsigned.
>

Converting this to a static-inline was my other thought, rather than
keeping the macros.
But I'm not sure where to draw the line between too much rework vs a bug-fix.
Just fixing the bug was done in V1 of this patch, but then the kunit
exposed a bunch more.

> It's separate from this bugfix of course, but would it be feasible for
> someone to go switch all callers to use u32's then reimplement these in
> lib/find_closest.c?
>

That would work.
How would a rework be preferred?
As a continuation to this patchset? Or a V3 to this patchset?

It's not a big effort to do, now that the kunit is in place.
I actually have a bunch of kunit variants (locally) that try various
combinations of signed/unsigned X & arrays.
But they drove me slightly nuts, until I decided to do the enforcement
to 'long' type for x, mid, left, right variables.

A catch-all implementation (for all current use-cases) would be best
with an int32 vs uint32 for X, mid, left & right (variables).
The thing with X being an int32 is more related to what userspace
would expect to see when inputting a negative number against an array
(of signed or unsigned).
The type of the elements in the array (signed or unsigned) doesn't
matter much (if focusing on the type for the X, mid, left & right
variables).

For the oversampling feature in ad7606, with unsigned X:
   echo -1 > /sys/bus/iio/devices/iio\:device0/oversampling_ratio
would return 128 rather than 0 (for "cat
/sys/bus/iio/devices/iio\:device0/oversampling_ratio")
Right now, the IIO framework treats -1 as an 'int'

But, moving forward: what would some preferences be?
- have variants of find_closest() for unsigned/signed arrays? (
find_closest_u32() or find_closest_i32() ?)
   - AFAICT so far, there aren't any values in the arrays that get
close to INT32_MAX, so int32 may work for now
   - maybe later some 64-bit variants could be added if needed
- should the variables X, mid, left & right be the same signedness as the array

The only preference (towards which I'm leaning) is just making sure
that X (and friends) are signed.