iio: Fix the sorting functionality in iio_gts_build_avail_time_table
Subsystems (2)
PATCH 1/1 iio: Fix the sorting functionality in iio_gts_build_avail_time_table
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/[email protected].
---
drivers/iio/industrialio-gts-helper.c +3 -2
@@ -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) { times[idx++] = new;continue ; }
@@ -385,9 +385,10 @@ static int iio_gts_build_avail_time_table(struct iio_gts *gts)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 */
Jonathan Cameron
maintainerQuoted 1 line · On Wed, 13 Mar 2024 10:57:35 -0500 Chenyuan Yang <[email protected]> wrote:
The sorting in
iio_gts_build_avail_time_tableis not working as intended.
For function names, add () so
The sorting in iio_gts_build_avail_time_table() is not working as intended.
I can fix this up whilst applying but will be waiting for a RB or related from Matti before queuing this up.
I'm assuming there are no existing drivers in tree that hit this problem? If there are reply saying which ones so I can assess whether to rush this fix in or not.
Thanks,
Jonathan
Quoted 48 lines
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 oncetimes[j] > new, the valuenewwill be added in the current position and thetimes[j]will be moved toj+1position, 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/[email protected].
Reported-by Chenyuan Yang <[email protected]>Suggested-by Matti Vaittinen <[email protected]>Fixes 38416c28e16890b52fdd5eb73479299ec3f062f3 ("iio: light: Add gain-time-scale helpers")Signed-off-by Chenyuan Yang <[email protected]>---
drivers/iio/industrialio-gts-helper.c +3
-2@@ -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) { times[idx++] = new;continue ; }@@ -385,9 +385,10 @@ static int iio_gts_build_avail_time_table(struct iio_gts *gts)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 */
Matti Vaittinen
maintainerQuoted 9 lines · Jonathan Cameron
Quoted 1 line · On Wed, 13 Mar 2024 10:57:35 -0500 Chenyuan Yang <[email protected]> wrote:
The sorting in
iio_gts_build_avail_time_tableis not working as intended.For function names, add () so
The sorting iniio_gts_build_avail_time_table()is not working as intended.I can fix this up whilst applying but will be waiting for a RB or related from Matti before queuing this up.
Thanks for waiting Jonathan. I wanted to run a set of tests before acking this - but I didn't manage to find the required half an hour for it Today... I'll handle this early tomorrow.
Quoted 1 line
I'm assuming there are no existing drivers in tree that hit this problem?
I don't think so. The ROHM drivers which use the avail_times have (by luck) the time tables already sorted in a suitable way.
Quoted 7 lines
If there are reply saying which ones so I can assess whether to rush this fix in or not.
Thanks,
Jonathan
Yours,
-- Matti
Signature · 5 lines
Matti Vaittinen Linux kernel developer at ROHM Semiconductors Oulu Finland ~~ When things go utterly wrong vim users can always type :help! ~~
Matti Vaittinen
maintainerHi Chenyuan,
Thank you very much for taking the time and effort to fix my bugs! :)
Quoted 16 lines · Chenyuan Yang
The sorting in
iio_gts_build_avail_time_tableis 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 oncetimes[j] > new, the valuenewwill be added in the current position and thetimes[j]will be moved toj+1position, 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".
Quoted 4 lines
For more details, please refer to https://lore.kernel.org/all/[email protected].
Reported-by Chenyuan Yang <[email protected]>Suggested-by Matti Vaittinen <[email protected]>
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!
drivers/iio/industrialio-gts-helper.c static int iio_gts_build_avail_time_table(struct iio_gts *gts) · line 378
Quoted 13 lines
Fixes 38416c28e16890b52fdd5eb73479299ec3f062f3 ("iio: light: Add gain-time-scale helpers")Signed-off-by Chenyuan Yang <[email protected]>---
drivers/iio/industrialio-gts-helper.c +1
-1@@ -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.
drivers/iio/industrialio-gts-helper.c static int iio_gts_build_avail_time_table(struct iio_gts *gts) · line 392
Quoted 13 lines
drivers/iio/industrialio-gts-helper.c +2
-1times[idx++] = new;continue ; }@@ -385,9 +385,10 @@ static int iio_gts_build_avail_time_table(struct iio_gts *gts)memmove (×[j +1 ], ×[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(×[j + 1], ×[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 :)
drivers/iio/industrialio-gts-helper.c static int iio_gts_build_avail_time_table(struct iio_gts *gts) · line 394
Quoted 3 lines
drivers/iio/industrialio-gts-helper.c +0
-0/* create a list of times formatted as list of IIO_VAL_INT_PLUS_MICRO */
Yours,
-- Matti
Signature · 5 lines
Matti Vaittinen Linux kernel developer at ROHM Semiconductors Oulu Finland ~~ When things go utterly wrong vim users can always type :help! ~~
Hi Matti,
Thanks for your reply!
Quoted 2 lines
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!
You did help me figure out the real issue here and how to fix it :)
Quoted 1 line
Do you think you could fix the removal of the duplicates too?
Sure, I can help to implement the deduplication logic. Here is a potential patch for it based on your help. Besides, I changed the stop condition in the inner loop to j < idx since the current last index should be idx - 1.
---
drivers/iio/industrialio-gts-helper.c +5 -2
@@ -375,17 +375,20 @@ 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) { times[idx++] = new;continue ; } -for (j =0 ; j <= idx; j++) { +for (j =0 ; j < idx; j++) { +if (times[j] == new) +break ;if (times[j] > new) {memmove (×[j +1 ], ×[j], (idx - j) *sizeof (int )); times[j] = new; idx++; +break ; } } }
Jonathan Cameron
maintainerQuoted 7 lines · On Fri, 15 Mar 2024 15:49:10 -0500 Chenyuan Yang <[email protected]> wrote:
Hi Matti,
Thanks for your reply!
Quoted 2 lines
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!
Quoted 8 lines
You did help me figure out the real issue here and how to fix it :)
Quoted 1 line
Do you think you could fix the removal of the duplicates too?
Sure, I can help to implement the deduplication logic. Here is a potential patch for it based on your help. Besides, I changed the stop condition in the inner loop to
j < idxsince the current last index should beidx - 1.
Matti, I didn't follow why duplicates are a problem?
Sure the code is less efficient, but do we end up with a wrong answer as a result (I've not checked logic, but I'd expect either first or last of repeating values to be used depending on the alg).
I'm not convinced adding to complexity of the code is worthwhile if its not a functional problem. I would expect a unit test to verify that duplicates aren't a problem though (given you have unit tests!)
Jonathan
Quoted 29 lines
---
drivers/iio/industrialio-gts-helper.c +5
-2@@ -375,17 +375,20 @@ 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) { times[idx++] = new;continue ; } -for (j =0 ; j <= idx; j++) { +for (j =0 ; j < idx; j++) { +if (times[j] == new) +break ;if (times[j] > new) {memmove (×[j +1 ], ×[j], (idx - j) *sizeof (int )); times[j] = new; idx++; +break ; } } }
Matti Vaittinen
maintainerHi Jonathan, all.
I am resending this as I don't think I found the mail from lore. I wrote this using my phone so maybe it was sent as HTML and stuck to some filters. If you receive this twice - I am sorry...
la 16. maalisk. 2024 klo 15.40 Jonathan Cameron <[email protected] <mailto:[email protected]>> kirjoitti:
Quoted 13 lines
Quoted 9 lines · On Fri, 15 Mar 2024 15:49:10 -0500 Chenyuan Yang <[email protected]…
Hi Matti,
Thanks for your reply!
Quoted 2 lines
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!
You did help me figure out the real issue here and how to fix it :)
Quoted 8 lines
Quoted 6 lines
Quoted 1 line
Do you think you could fix the removal of the duplicates too?
Sure, I can help to implement the deduplication logic. Here is a potential patch for it based on your help. Besides, I changed the stop condition in the inner loop to
j < idxsince the current last index should beidx - 1.Matti, I didn't follow why duplicates are a problem?
The function here builds the tables for available integration times. These are shown to users via sysfs (if I'm not mistaken) - and while the user-space algorithms may tolerate dublicates, they are ugly (in my opinon) when available times are manually listed.
Quoted 3 lines
Sure the code is less efficient, but do we end up with a wrong answer as a result (I've not checked logic, but I'd expect either first or last of repeating values to be used depending on the alg).
If we discuss completely omitting duplicated times from the driver (which was one thing I referred in my previous mail) - then we are likely to face problems as there can be register values, which then can't be translated to times, read from a HW.
Eg, we need to have everything described in driver tables used for driver's computations - but (in my opinion) we should drop duplicates from these tables which we hand over via sysfs.
Yours,
-- Matti
Jonathan Cameron
maintainerQuoted 41 lines · On Wed, 20 Mar 2024 09:02:46 +0200 Matti Vaittinen <[email protected]>…
Hi Jonathan, all.
I am resending this as I don't think I found the mail from lore. I wrote this using my phone so maybe it was sent as HTML and stuck to some filters. If you receive this twice - I am sorry...
la 16. maalisk. 2024 klo 15.40 Jonathan Cameron <[email protected] <mailto:[email protected]>> kirjoitti:
Quoted 13 lines
Quoted 9 lines · On Fri, 15 Mar 2024 15:49:10 -0500 Chenyuan Yang <[email protected]…
Hi Matti,
Thanks for your reply!
Quoted 2 lines
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!
You did help me figure out the real issue here and how to fix it :)
Quoted 8 lines
Quoted 6 lines
Quoted 1 line
Do you think you could fix the removal of the duplicates too?
Sure, I can help to implement the deduplication logic. Here is a potential patch for it based on your help. Besides, I changed the stop condition in the inner loop to
j < idxsince the current last index should beidx - 1.Matti, I didn't follow why duplicates are a problem?
The function here builds the tables for available integration times. These are shown to users via sysfs (if I'm not mistaken) - and while the user-space algorithms may tolerate dublicates, they are ugly (in my opinon) when available times are manually listed.
Quoted 3 lines
Sure the code is less efficient, but do we end up with a wrong answer as a result (I've not checked logic, but I'd expect either first or last of repeating values to be used depending on the alg).
Quoted 9 lines
If we discuss completely omitting duplicated times from the driver (which was one thing I referred in my previous mail) - then we are likely to face problems as there can be register values, which then can't be translated to times, read from a HW.
Eg, we need to have everything described in driver tables used for driver's computations - but (in my opinion) we should drop duplicates from these tables which we hand over via sysfs.
All makes sense. Thanks for the explanation.
J
Quoted 2 lines
Yours,
-- Matti
Matti Vaittinen
maintainerQuoted 49 lines · Jonathan Cameron
Quoted 46 lines · On Wed, 20 Mar 2024 09:02:46 +0200 Matti Vaittinen <[email protected]>…
Hi Jonathan, all.
I am resending this as I don't think I found the mail from lore. I wrote this using my phone so maybe it was sent as HTML and stuck to some filters. If you receive this twice - I am sorry...
la 16. maalisk. 2024 klo 15.40 Jonathan Cameron <[email protected] <mailto:[email protected]>> kirjoitti:
Quoted 13 lines
Quoted 9 lines · On Fri, 15 Mar 2024 15:49:10 -0500 Chenyuan Yang <[email protected]…
Hi Matti,
Thanks for your reply!
Quoted 2 lines
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!
You did help me figure out the real issue here and how to fix it :)
Quoted 8 lines
Quoted 6 lines
Quoted 1 line
Do you think you could fix the removal of the duplicates too?
Sure, I can help to implement the deduplication logic. Here is a potential patch for it based on your help. Besides, I changed the stop condition in the inner loop to
j < idxsince the current last index should beidx - 1.Matti, I didn't follow why duplicates are a problem?
The function here builds the tables for available integration times. These are shown to users via sysfs (if I'm not mistaken) - and while the user-space algorithms may tolerate dublicates, they are ugly (in my opinon) when available times are manually listed.
Quoted 3 lines
Sure the code is less efficient, but do we end up with a wrong answer as a result (I've not checked logic, but I'd expect either first or last of repeating values to be used depending on the alg).
If we discuss completely omitting duplicated times from the driver (which was one thing I referred in my previous mail) - then we are likely to face problems as there can be register values, which then can't be translated to times, read from a HW.
Quoted 5 lines
Quoted 4 lines
Eg, we need to have everything described in driver tables used for driver's computations - but (in my opinion) we should drop duplicates from these tables which we hand over via sysfs.
All makes sense. Thanks for the explanation.
Hi Chenyuan
I don't think I have seen a patch fixing this merged? Do you know if I have just missed it? If not, do you still plan to send a fix to this or should I do it?
Yours,
-- Matti
Signature · 5 lines
Matti Vaittinen Linux kernel developer at ROHM Semiconductors Oulu Finland ~~ When things go utterly wrong vim users can always type :help! ~~
Matti Vaittinen
maintainerHi Jonathan, Chenyuan,
to 11. huhtik. 2024 klo 15.20 Matti Vaittinen
([email protected]) kirjoitti:
Quoted 55 lines · Jonathan Cameron
Quoted 53 lines
Quoted 50 lines · On Wed, 20 Mar 2024 09:02:46 +0200 Matti Vaittinen <[email protected]>…
Hi Jonathan, all.
I am resending this as I don't think I found the mail from lore. I wrote this using my phone so maybe it was sent as HTML and stuck to some filters. If you receive this twice - I am sorry...
la 16. maalisk. 2024 klo 15.40 Jonathan Cameron <[email protected] <mailto:[email protected]>> kirjoitti:
Quoted 13 lines
Quoted 9 lines · On Fri, 15 Mar 2024 15:49:10 -0500 Chenyuan Yang <[email protected]…
Hi Matti,
Thanks for your reply!
Quoted 2 lines
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!
You did help me figure out the real issue here and how to fix it :)
Quoted 8 lines
Quoted 6 lines
Quoted 1 line
Do you think you could fix the removal of the duplicates too?
Sure, I can help to implement the deduplication logic. Here is a potential patch for it based on your help. Besides, I changed the stop condition in the inner loop to
j < idxsince the current last index should beidx - 1.Matti, I didn't follow why duplicates are a problem?
The function here builds the tables for available integration times. These are shown to users via sysfs (if I'm not mistaken) - and while the user-space algorithms may tolerate dublicates, they are ugly (in my opinon) when available times are manually listed.
Quoted 3 lines
Sure the code is less efficient, but do we end up with a wrong answer as a result (I've not checked logic, but I'd expect either first or last of repeating values to be used depending on the alg).
If we discuss completely omitting duplicated times from the driver (which was one thing I referred in my previous mail) - then we are likely to face problems as there can be register values, which then can't be translated to times, read from a HW.
Eg, we need to have everything described in driver tables used for driver's computations - but (in my opinion) we should drop duplicates from these tables which we hand over via sysfs.
Quoted 7 lines
Quoted 1 line
All makes sense. Thanks for the explanation.
Hi Chenyuan
I don't think I have seen a patch fixing this merged? Do you know if I have just missed it? If not, do you still plan to send a fix to this or should I do it?
Jonathan, seems like Chenyuan has gone offline. I'd like to get this fixed as it'll bite us sooner or later if left like this. What's the right way to proceed? Should I craft a patch and add signed-off or suggested-by from Chenyuan as he has done most of this already?
Yours,
-- Matti
Quoted 7 lines
--
Matti Vaittinen
Linux kernel developer at ROHM Semiconductors
Oulu Finland~~ When things go utterly wrong vim users can always type :help! ~~
Signature · 8 lines
Matti Vaittinen Linux kernel developer at ROHM Semiconductors Oulu Finland ~~ When things go utterly wrong vim users can always type :help! ~~ Discuss - Estimate - Plan - Report and finally accomplish this: void do_work(int time) __attribute__ ((const));
Jonathan Cameron
maintainerQuoted 63 lines · On Fri, 26 Apr 2024 08:52:54 +0300 Matti Vaittinen <[email protected]>…
Hi Jonathan, Chenyuan,
to 11. huhtik. 2024 klo 15.20 Matti Vaittinen
([email protected]) kirjoitti:Quoted 59 lines · Jonathan Cameron
Quoted 49 lines
Quoted 46 lines · On Wed, 20 Mar 2024 09:02:46 +0200 Matti Vaittinen <[email protected]>…
Hi Jonathan, all.
I am resending this as I don't think I found the mail from lore. I wrote this using my phone so maybe it was sent as HTML and stuck to some filters. If you receive this twice - I am sorry...
la 16. maalisk. 2024 klo 15.40 Jonathan Cameron <[email protected] <mailto:[email protected]>> kirjoitti:
Quoted 13 lines
Quoted 9 lines · On Fri, 15 Mar 2024 15:49:10 -0500 Chenyuan Yang <[email protected]…
Hi Matti,
Thanks for your reply!
Quoted 2 lines
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!
You did help me figure out the real issue here and how to fix it :)
Quoted 8 lines
Quoted 6 lines
Quoted 1 line
Do you think you could fix the removal of the duplicates too?
Sure, I can help to implement the deduplication logic. Here is a potential patch for it based on your help. Besides, I changed the stop condition in the inner loop to
j < idxsince the current last index should beidx - 1.Matti, I didn't follow why duplicates are a problem?
The function here builds the tables for available integration times. These are shown to users via sysfs (if I'm not mistaken) - and while the user-space algorithms may tolerate dublicates, they are ugly (in my opinon) when available times are manually listed.
Quoted 3 lines
Sure the code is less efficient, but do we end up with a wrong answer as a result (I've not checked logic, but I'd expect either first or last of repeating values to be used depending on the alg).
If we discuss completely omitting duplicated times from the driver (which was one thing I referred in my previous mail) - then we are likely to face problems as there can be register values, which then can't be translated to times, read from a HW.
Quoted 5 lines
Quoted 4 lines
Eg, we need to have everything described in driver tables used for driver's computations - but (in my opinion) we should drop duplicates from these tables which we hand over via sysfs.
All makes sense. Thanks for the explanation.
Hi Chenyuan
Quoted 8 lines
Quoted 3 lines
I don't think I have seen a patch fixing this merged? Do you know if I have just missed it? If not, do you still plan to send a fix to this or should I do it?
Jonathan, seems like Chenyuan has gone offline. I'd like to get this fixed as it'll bite us sooner or later if left like this. What's the right way to proceed? Should I craft a patch and add signed-off or suggested-by from Chenyuan as he has done most of this already?
If it's closely related to Chenyuan's original patch, keep the authorship the same and add a Co-developed-by + sign off for yourself.
If you end more or less writing a fresh patch, then a Suggested-by is fine.
Jonathan
Quoted 13 lines
Yours,
-- MattiQuoted 7 lines
--
Matti Vaittinen
Linux kernel developer at ROHM Semiconductors
Oulu Finland~~ When things go utterly wrong vim users can always type :help! ~~