Re: [PATCH] iio: Fix the sorting functionality in iio_gts_build_avail_time_table

[Matti Vaittinen <mazziesaccount@gmail.com>]

Hi Chenyuan,

Thank you very much for taking the time and effort to fix my bugs! :)

On 3/13/24 17:57, Chenyuan Yang wrote:
> The sorting in iio_gts_build_avail_time_table is not working as intended.
> It could result in an out-of-bounds access when the time is zero.
> 
> Here are more details:
> 
> 1. When the gts->itime_table[i].time_us is zero, e.g., the time
> sequence is `3, 0, 1`, the inner for-loop will not terminate and do
> out-of-bound writes. This is because once `times[j] > new`, the value
> `new` will be added in the current position and the `times[j]` will be
> moved to `j+1` position, which makes the if-condition always hold.
> Meanwhile, idx will be added one, making the loop keep running without
> termination and out-of-bound write.
> 2. If none of the gts->itime_table[i].time_us is zero, the elements
> will just be copied without being sorted as described in the comment
> "Sort times from all tables to one and remove duplicates".
> 
> For more details, please refer to https://lore.kernel.org/all/6dd0d822-046c-4dd2-9532-79d7ab96ec05@gmail.com.
> 
> Reported-by: Chenyuan Yang <chenyuan0y@gmail.com>
> Suggested-by: Matti Vaittinen <mazziesaccount@gmail.com>

I think the suggested-by tag is a bit of an overkill :) I don't feel 
like taking the credit - you spotted the problem and fixed it!

> Fixes: 38416c28e16890b52fdd5eb73479299ec3f062f3 ("iio: light: Add gain-time-scale helpers")
> Signed-off-by: Chenyuan Yang <chenyuan0y@gmail.com>
> ---
> diff --git a/drivers/iio/industrialio-gts-helper.c b/drivers/iio/industrialio-gts-helper.c
> index 7653261d2dc2..61714a8d5717 100644
> --- a/drivers/iio/industrialio-gts-helper.c
> +++ b/drivers/iio/industrialio-gts-helper.c
> @@ -375,7 +375,7 @@ static int iio_gts_build_avail_time_table(struct iio_gts *gts)
>   	for (i = gts->num_itime - 1; i >= 0; i--) {
>   		int new = gts->itime_table[i].time_us;
>   
> -		if (times[idx] < new) {
> +		if (idx == 0 || times[idx - 1] < new) {

This part should work just fine - thanks.

>   			times[idx++] = new;
>   			continue;
>   		}
> @@ -385,9 +385,10 @@ static int iio_gts_build_avail_time_table(struct iio_gts *gts)
>   				memmove(&times[j + 1], &times[j],
>   					(idx - j) * sizeof(int));
>   				times[j] = new;
> -				idx++;
> +				break;
>   			}
>   		}
> +		idx++;
>   	}

Here you successfully fix the sorting but the duplicates aren't removed. 
I'd like to have the removal of duplicates as occasionally we see 
hardware where multiple register values mean same setting. In such a 
case we probably want to have multiple entries with same integration 
time in the time array - so the driver can convert all register values 
to correct times. We, however, don't want to list same values for 
available times via sysfs. Hence I think removing the duplicates makes 
sense.

I think the logic we try to achieve is something like:

         /* Sort times from all tables to one and remove duplicates */ 

         for (i = gts->num_itime - 1; i >= 0; i--) {
                 int new = gts->itime_table[i].time_us;

                 if (idx == 0 || times[idx - 1] < new) {
                         times[idx++] = new;
                         continue;
                 }

                 for (j = 0; j <= idx; j++) {
                         if (times[j] == new) {
                                 idx--;
                                 break;
                         }
                         if (times[j] > new) {
                                 memmove(&times[j + 1], &times[j],
                                         (idx - j) * sizeof(int));
                                 times[j] = new;
                                 break;
                         }
                 }
                 idx++;
         }

but the flow can probably be further improved to avoid doing idx--; 
followed by idx++; for a duplicate.

Do you think you could fix the removal of the duplicates too?

In any case, this patch is far better than the existing code, and I did 
run some tests on it too, but I would be happy if the duplicates were 
handled as well :)

>   
>   	/* create a list of times formatted as list of IIO_VAL_INT_PLUS_MICRO */
> 

Yours,
	-- Matti

-- 
Matti Vaittinen
Linux kernel developer at ROHM Semiconductors
Oulu Finland

~~ When things go utterly wrong vim users can always type :help! ~~