Message-ID: <6dd0d822-046c-4dd2-9532-79d7ab96ec05@gmail.com>
Date: Tue, 12 Mar 2024 13:16:31 +0200
From: Matti Vaittinen <mazziesaccount@...il.com>
To: Chenyuan Yang <chenyuan0y@...il.com>, jic23@...nel.org, lars@...afoo.de,
 linux-iio@...r.kernel.org
Cc: linux-kernel@...r.kernel.org, Zijie Zhao <zzjas98@...il.com>
Subject: Re: [drivers/iio] Question about `iio_gts_build_avail_time_table`

Hi Chenyuan!

Thank you for pointing out the problems :)

On 3/11/24 21:48, Chenyuan Yang wrote:
> Dear Linux Developers for IIO Driver,
> 
> We are curious about the functionality of
> `iio_gts_build_avail_time_table`
> (https://elixir.bootlin.com/linux/latest/source/drivers/iio/industrialio-gts-helper.c#L363)
> 
> ```
> static int iio_gts_build_avail_time_table(struct iio_gts *gts)
> {
>    int *times, i, j, idx = 0, *int_micro_times;
> 
>    if (!gts->num_itime)
>      return 0;
> 
>    times = kcalloc(gts->num_itime, sizeof(int), GFP_KERNEL);
>    if (!times)
>      return -ENOMEM;
> 
>    /* 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 (times[idx] < new) {
>        times[idx++] = new;
>        continue;
>      }
> 
>      for (j = 0; j <= idx; j++) {
>        if (times[j] > new) {
>          memmove(&times[j + 1], &times[j],
>                                  (idx - j) * sizeof(int));
>          times[j] = new;
>          idx++;
>        }
>      }
>    ...
> }
> ```
> 
> For this function, we are trying to understand how it works but not
> sure how this sorting is done.
> 
> 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".
> 
> Please correct us if we miss some key prerequisites for this function
> or the data structure.
> Thanks in advance!

You are correct. The sorting is not working as intended! It has only 
worked and passed the tests because the arrays in the test and driver 
code have been ordered in "descending time" - order. The code above has 
done a copying of items in reverse order, resulting a working set of 
available times.

> A possible patch based on our understanding is attached.

I copied your suggested fix here for my initial thoughts:

diff --git a/drivers/iio/industrialio-gts-helper.c 
b/drivers/iio/industrialio-gts-helper.c
index 7653261d2dc2..0667da988295 100644
--- a/drivers/iio/industrialio-gts-helper.c
+++ b/drivers/iio/industrialio-gts-helper.c
@@ -375,19 +375,17 @@ 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) {
-			times[idx++] = new;
-			continue;
-		}
+		times[idx] = new;

The idea of the check which has been removed was to assign the value in 
the array in first free spot if it is bigger than the last value. As you 
pointed out, the implementation is wrong, but I think the idea is Ok. 
Here you do unconditional assignment which is slightly sub-optimal.

  		for (j = 0; j <= idx; j++) {
  			if (times[j] > new) {
  				memmove(&times[j + 1], &times[j],
  					(idx - j) * sizeof(int));
  				times[j] = new;
-				idx++;
+				break;
  			}
  		}
+		idx++;
  	}
  	/* create a list of times formatted as list of IIO_VAL_INT_PLUS_MICRO */


I will fire-up a setup with the IIO-GTS Kunit tests, and alter the order 
of times in array for the available times test.

I would appreciate if you could post formal fixup-patch in inline 
message as per usual Linux review and merge process. That would simplify 
the process for Jonathan and other reviewers. Please, let me know if you 
don't want to send a formal fix. In that case I will write a fix by myself.

Finally, your finding and report is _very much_ appreciated! Thanks!

Yours,
	-- Matti

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

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

Powered by blists - more mailing lists