| Message ID | 20241105145406.554365-1-aardelean@baylibre.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | [v2,1/2] util_macros.h: fix/rework find_closest() macros | expand |
On Tue, 5 Nov 2024 16:54:05 +0200 Alexandru Ardelean <aardelean@baylibre.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! 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. 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?
On Wed, Nov 6, 2024 at 1:08 AM Andrew Morton <akpm@linux-foundation.org> wrote: > > On Tue, 5 Nov 2024 16:54:05 +0200 Alexandru Ardelean <aardelean@baylibre.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.
On Wed, 6 Nov 2024 16:03:36 +0200 Alexandru Ardelean <aardelean@baylibre.com> wrote: > On Wed, Nov 6, 2024 at 1:08 AM Andrew Morton <akpm@linux-foundation.org> wrote: > > 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. Non-inline, I think. It's big. > 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. Sure, just the minimum for a bugfix. > > 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? A new and separate patchset. A low-priority cleanup from whoever has the time and motivation ;) > 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. Yes, I guess int32 would be best. I agree that unsigned values greater than INT_MAX are unlikely. I suggest a series of patches which convert individual callers to int32 and the final patch introduces lib/find_closest.c.
diff --git a/include/linux/util_macros.h b/include/linux/util_macros.h index 6bb460c3e818..825487fb66fa 100644 --- a/include/linux/util_macros.h +++ b/include/linux/util_macros.h @@ -4,19 +4,6 @@ #include <linux/math.h> -#define __find_closest(x, a, as, op) \ -({ \ - typeof(as) __fc_i, __fc_as = (as) - 1; \ - typeof(x) __fc_x = (x); \ - typeof(*a) const *__fc_a = (a); \ - for (__fc_i = 0; __fc_i < __fc_as; __fc_i++) { \ - if (__fc_x op DIV_ROUND_CLOSEST(__fc_a[__fc_i] + \ - __fc_a[__fc_i + 1], 2)) \ - break; \ - } \ - (__fc_i); \ -}) - /** * find_closest - locate the closest element in a sorted array * @x: The reference value. @@ -25,8 +12,27 @@ * @as: Size of 'a'. * * Returns the index of the element closest to 'x'. + * Note: If using an array of negative numbers (or mixed positive numbers), + * then be sure that 'x' is of a signed-type to get good results. */ -#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); \ +}) /** * find_closest_descending - locate the closest element in a sorted array @@ -36,9 +42,27 @@ * @as: Size of 'a'. * * Similar to find_closest() but 'a' is expected to be sorted in descending - * order. + * order. The iteration is done in reverse order, so that the comparison + * of '__fc_right' & '__fc_left' also works for unsigned numbers. */ -#define find_closest_descending(x, a, as) __find_closest(x, a, as, >=) +#define find_closest_descending(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 = __fc_as; __fc_i >= 1; __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); \ +}) /** * is_insidevar - check if the @ptr points inside the @var memory range.
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. The rounding issues occur for progressions of 1, 2 and 3. It goes away when the progression/interval between two values is 4 or larger. It's particularly bad for progressions of 1. For example if there's an array of 'a = { 1, 2, 3 }', using 'find_closest(2, a ...)' would return 0 (the index of '1'), rather than returning 1 (the index of '2'). This means that for exact values (with a progression of 1), find_closest() will misbehave and return the index of the value smaller than the one we're searching for. For progressions of 2 and 3, the exact values are obtained correctly; but values aren't approximated correctly (as one would expect). Starting with progressions of 4, all seems to be good (one gets what one would expect). While one could argue that 'find_closest()' should not be used for arrays with progressions of 1 (i.e. '{1, 2, 3, ...}', the macro should still behave correctly. The bug was found while testing the 'drivers/iio/adc/ad7606.c', specifically the oversampling feature. For reference, the oversampling values are listed as: static const unsigned int ad7606_oversampling_avail[7] = { 1, 2, 4, 8, 16, 32, 64, }; When doing: 1. $ echo 1 > /sys/bus/iio/devices/iio\:device0/oversampling_ratio $ cat /sys/bus/iio/devices/iio\:device0/oversampling_ratio 1 # this is fine 2. $ echo 2 > /sys/bus/iio/devices/iio\:device0/oversampling_ratio $ cat /sys/bus/iio/devices/iio\:device0/oversampling_ratio 1 # this is wrong; 2 should be returned here 3. $ echo 3 > /sys/bus/iio/devices/iio\:device0/oversampling_ratio $ cat /sys/bus/iio/devices/iio\:device0/oversampling_ratio 2 # this is fine 4. $ echo 4 > /sys/bus/iio/devices/iio\:device0/oversampling_ratio $ cat /sys/bus/iio/devices/iio\:device0/oversampling_ratio 4 # this is fine And from here-on, the values are as correct (one gets what one would expect.) While writing a kunit test for this bug, a peculiar issue was found for the array in the 'drivers/hwmon/ina2xx.c' & 'drivers/iio/adc/ina2xx-adc.c' drivers. While running the kunit test (for 'ina226_avg_tab' from these drivers): * idx = find_closest([-1 to 2], ina226_avg_tab, ARRAY_SIZE(ina226_avg_tab)); This returns idx == 0, so value. * idx = find_closest(3, ina226_avg_tab, ARRAY_SIZE(ina226_avg_tab)); This returns idx == 0, value 1; and now one could argue whether 3 is closer to 4 or to 1. This quirk only appears for value '3' in this array, but it seems to be a another rounding issue. * And from 4 onwards the 'find_closest'() works fine (one gets what one would expect). This change reworks the find_closest() macros to also check the difference between the left and right elements when 'x'. If the distance to the right is smaller (than the distance to the left), the index is incremented by 1. This also makes redundant the need for using the DIV_ROUND_CLOSEST() macro. In order to accommodate for any mix of negative + positive values, the internal variables '__fc_x', '__fc_mid_x', '__fc_left' & '__fc_right' are forced to 'long' type. This also addresses any potential bugs/issues with 'x' being of an unsigned type. In those situations any comparison between signed & unsigned would be promoted to a comparison between 2 unsigned numbers; this is especially annoying when '__fc_left' & '__fc_right' underflow. The find_closest_descending() macro was also reworked and duplicated from the find_closest(), and it is being iterated in reverse. The main reason for this is to get the same indices as 'find_closest()' (but in reverse). The comparison for '__fc_right < __fc_left' favors going the array in ascending order. For example for array '{ 1024, 512, 256, 128, 64, 16, 4, 1 }' and x = 3, we get: __fc_mid_x = 2 __fc_left = -1 __fc_right = -2 Then '__fc_right < __fc_left' evaluates to true and '__fc_i++' becomes 7 which is not quite incorrect, but 3 is closer to 4 than to 1. This change has been validated with the kunit from the next patch. Fixes: 95d119528b0b ("util_macros.h: add find_closest() macro") Signed-off-by: Alexandru Ardelean <aardelean@baylibre.com> --- Changelog v1 -> v2: * https://lore.kernel.org/linux-iio/20241031063707.795842-1-aardelean@baylibre.com/ * split the __find_closest() macro into find_closest() & find_closest_descending() * find_closest_descending() is iterating in reverse order * this favors some corner cases with small values * forcing types for '__fc_x', '__fc_mid_x', '__fc_left' && '__fc_right' to be long * this resolves several potential issues with combining arrays of signed/unsigned values with 'x' of type signed/unsigned * fixed error with previous implementation where __fc_mid_x was used instead of __fc_x when calculating '__fc_left' && '__fc_right' * updated commit description with more information (also found on previous thread) + the description for the changed implementation include/linux/util_macros.h | 56 ++++++++++++++++++++++++++----------- 1 file changed, 40 insertions(+), 16 deletions(-)