[drivers/iio] Question about `iio_gts_build_avail_time_table`

[drivers/iio] Question about `iio_gts_build_avail_time_table`

[Chenyuan Yang]

[-- Attachment #1: Type: text/plain, Size: 1845 bytes --]

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!

A possible patch based on our understanding is attached.

Best,
Chenyuan

[-- Attachment #2: iio.patch --]
[-- Type: application/octet-stream, Size: 763 bytes --]

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;
 
 		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 */

Re: [drivers/iio] Question about `iio_gts_build_avail_time_table`

[Matti Vaittinen]

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! ~~

Re: [drivers/iio] Question about `iio_gts_build_avail_time_table`

[Chenyuan Yang]

Hi Matti,

I have a question about the "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".

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

It appears that the comparison should perhaps be made with `idx-1`
rather than `idx`, given that `idx` represents the current number of
copied values in times, whereas `idx-1` points to the last value.
Could I have your thoughts on this?

Best,
Chenyuan

On Tue, Mar 12, 2024 at 6:16 AM Matti Vaittinen
<mazziesaccount@gmail.com> wrote:
>
> 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! ~~
>

Re: [drivers/iio] Question about `iio_gts_build_avail_time_table`

[Matti Vaittinen]

Hi Chenyuan,

On 3/12/24 18:53, Chenyuan Yang wrote:
> Hi Matti,
> 
> I have a question about the "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".

Can you please avoid top-posting when discussing on the Linux lists. You 
can find more information from:
https://www.kernel.org/doc/html/latest/process/submitting-patches.html

part of which may be crucial in order to get your changes applied if you 
haven't already familiarized yourself with the kernel development processes.


> 
> -               if (times[idx] < new) {
> -                       times[idx++] = new;
> -                       continue;
> -               }
> +               times[idx] = new;
> 
> It appears that the comparison should perhaps be made with `idx-1`
> rather than `idx`, given that `idx` represents the current number of
> copied values in times, whereas `idx-1` points to the last value.
> Could I have your thoughts on this?

Yes. I implemented the old code wrong as you pointed out.

You may want to take the GTS Kunit test cases:
https://lore.kernel.org/all/6b839dd533fd93b75c2e6f6a8f2286233d4901fb.1704881096.git.mazziesaccount@gmail.com/
which, I think, are already merged in IIO testing branch.

You can test the sorting when you change the order of the times in the 
test case:

+static const struct iio_itime_sel_mul gts_test_itimes[] = {
+	GAIN_SCALE_ITIME_US(400 * 1000, TEST_TSEL_400, 8),
+	GAIN_SCALE_ITIME_US(200 * 1000, TEST_TSEL_200, 4),
+	GAIN_SCALE_ITIME_US(100 * 1000, TEST_TSEL_100, 2),
+	GAIN_SCALE_ITIME_US(50 * 1000, TEST_TSEL_50, 1),
+#define TIMEGAIN_MAX 8
+};

for example to

+static const struct iio_itime_sel_mul gts_test_itimes[] = {
+	GAIN_SCALE_ITIME_US(400 * 1000, TEST_TSEL_400, 8),
+	GAIN_SCALE_ITIME_US(50 * 1000, TEST_TSEL_50, 1),
+	GAIN_SCALE_ITIME_US(200 * 1000, TEST_TSEL_200, 4),
+	GAIN_SCALE_ITIME_US(100 * 1000, TEST_TSEL_100, 2),
+#define TIMEGAIN_MAX 8
+};

Yours,
	-- Matti

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

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