Received-SPF: pass (google.com: domain of linux-kernel+bounces-100546-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.48.161 as permitted sender) client-ip=147.75.48.161;
Precedence: bulk
MIME-Version: 1.0
References: <CALGdzur-rsLbd4BcgtR9QV2=ZH8xHAVySjm2z2TT=Aog74mdPw@mail.gmail.com>
 <6dd0d822-046c-4dd2-9532-79d7ab96ec05@gmail.com>
In-Reply-To: <6dd0d822-046c-4dd2-9532-79d7ab96ec05@gmail.com>
From: Chenyuan Yang <chenyuan0y@gmail.com>
Date: Tue, 12 Mar 2024 11:53:27 -0500
Message-ID: <CALGdzuoA4ANBurXyP+00hFPmPznixcMTgrYNp1P4VwvpFb_GtA@mail.gmail.com>
Subject: Re: [drivers/iio] Question about `iio_gts_build_avail_time_table`
To: Matti Vaittinen <mazziesaccount@gmail.com>
Cc: jic23@kernel.org, lars@metafoo.de, linux-iio@vger.kernel.org, 
	linux-kernel@vger.kernel.org, Zijie Zhao <zzjas98@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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++] =3D new;
-                       continue;
-               }
+               times[idx] =3D 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=E2=80=AFAM 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/industriali=
o-gts-helper.c#L363)
> >
> > ```
> > static int iio_gts_build_avail_time_table(struct iio_gts *gts)
> > {
> >    int *times, i, j, idx =3D 0, *int_micro_times;
> >
> >    if (!gts->num_itime)
> >      return 0;
> >
> >    times =3D kcalloc(gts->num_itime, sizeof(int), GFP_KERNEL);
> >    if (!times)
> >      return -ENOMEM;
> >
> >    /* Sort times from all tables to one and remove duplicates */
> >    for (i =3D gts->num_itime - 1; i >=3D 0; i--) {
> >      int new =3D gts->itime_table[i].time_us;
> >
> >      if (times[idx] < new) {
> >        times[idx++] =3D new;
> >        continue;
> >      }
> >
> >      for (j =3D 0; j <=3D idx; j++) {
> >        if (times[j] > new) {
> >          memmove(&times[j + 1], &times[j],
> >                                  (idx - j) * sizeof(int));
> >          times[j] =3D 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 =3D gts->num_itime - 1; i >=3D 0; i--) {
>                 int new =3D gts->itime_table[i].time_us;
>
> -               if (times[idx] < new) {
> -                       times[idx++] =3D new;
> -                       continue;
> -               }
> +               times[idx] =3D 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 =3D 0; j <=3D idx; j++) {
>                         if (times[j] > new) {
>                                 memmove(&times[j + 1], &times[j],
>                                         (idx - j) * sizeof(int));
>                                 times[j] =3D new;
> -                               idx++;
> +                               break;
>                         }
>                 }
> +               idx++;
>         }
>         /* create a list of times formatted as list of IIO_VAL_INT_PLUS_M=
ICRO */
>
>
> 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 mysel=
f.
>
> 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! ~~
>