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(×[j + 1], ×[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(×[j + 1], ×[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! ~~
