[libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the controls order assumption in updateControls()

[Jacopo Mondi]

Hi Hiro,

On Wed, Apr 21, 2021 at 06:37:45PM +0900, Hirokazu Honda wrote:
> On Wed, Apr 21, 2021 at 6:30 PM Laurent Pinchart
> <laurent.pinchart at ideasonboard.com> wrote:
> >
> > Hi Hiro,
> >
> > On Wed, Apr 21, 2021 at 11:34:58AM +0900, Hirokazu Honda wrote:
> > > On Tue, Apr 20, 2021 at 9:25 AM Laurent Pinchart wrote:
> > > > On Thu, Apr 15, 2021 at 01:36:25PM +0900, Hirokazu Honda wrote:
> > > > > The original updateControls() has the assumption that ctrls and
> > > > > v4l2Ctrls lists in the same order. It is dependent on the caller
> > > > > implementation though. This changes updateControls()
> > > > > implementation so that it works without the assumption.
> > > > >
> > > > > Signed-off-by: Hirokazu Honda <hiroh at chromium.org>
> > > > > ---
> > > > >  src/libcamera/v4l2_device.cpp | 26 +++++++++++++-------------
> > > > >  1 file changed, 13 insertions(+), 13 deletions(-)
> > > > >
> > > > > diff --git a/src/libcamera/v4l2_device.cpp b/src/libcamera/v4l2_device.cpp
> > > > > index d4a9bb75..8fd79934 100644
> > > > > --- a/src/libcamera/v4l2_device.cpp
> > > > > +++ b/src/libcamera/v4l2_device.cpp
> > > > > @@ -525,19 +525,19 @@ void V4L2Device::updateControls(ControlList *ctrls,
> > > > >                               const struct v4l2_ext_control *v4l2Ctrls,
> > > > >                               unsigned int count)
> > > > >  {
> > > > > -     unsigned int i = 0;
> > > > > -     for (auto &ctrl : *ctrls) {
> > > > > -             if (i == count)
> > > > > -                     break;
> > > > > -
> > > > > -             const struct v4l2_ext_control *v4l2Ctrl = &v4l2Ctrls[i];
> > > > > -             unsigned int id = ctrl.first;
> > > > > -             ControlValue &value = ctrl.second;
> > > > > +     for (unsigned int i = 0; i < count; i++) {
> > > > > +             const struct v4l2_ext_control &v4l2Ctrl = v4l2Ctrls[i];
> > > > > +             const unsigned int id = v4l2Ctrl.id;
> > > > > +             if (!ctrls->contains(id)) {
> > > > > +                     LOG(V4L2, Error) << "ControlList doesn't contain id: "
> > > > > +                                      << id;
> > > > > +                     return;
> > > > > +             }
> > > > >
> > > > > -             const auto iter = controls_.find(id);
> > > > > -             switch (iter->first->type()) {
> > > > > +             ControlValue value = ctrls->get(id);
> > > >
> > > > This is less efficient, as the function now runs with O(n^2) complexity.
> > >
> > > Can you explain me why the time complexity is O(n^2)?
> > > Since controls_ is based on std::unordered_map, find(), contains(),
> > > get() and set() should be O(1).
> > > So I think this is still O(n).

I read that all these functions are "in worst case" linear to the
length of the input in complexity

> >
> > You're right that it's not O(n^2) as we use an unordered map.
> > std::unordered_map::find() is "constant on average, worst case linear in
> > the size of the container".
> >
> > > > Given that updateControls() is private, why is requiring ctrls and
> > > > v4l2Ctrls to have the same order a problem ? The requirement should be
> > > > documented, but does it cause any issue ?
> > >
> > > I think the restriction is strange and unnecessary, and a caller might
> > > have to pre-process to keep that.
> > > Well, so far, the caller is only V4L2Device and we don't need anything
> > > to keep the rule.
> >
> > That was my point, it's a private function of the class :-) As all
> > callers currently guarantee the order, I'd defer this change until we
> > have a use case.
> >
>
> I forgot mentioning there is no guaranteed upon traversing std::unordered_map.
> https://stackoverflow.com/questions/50870951/iterating-over-unordered-map-c
>
> So I think as long as std::unordered_map is used, the original
> implementation is problematic?

If you look at the callers, the v4l2Ctrls are filled in by iterating
on the ControlList (which is an unordered map).

Regardless of how the ControlList is sorted, v4l2Ctrls will have the
same sorting order. There's a comment that explains that in
getControls():

	/*
	 * Start by filling the ControlList. This can't be combined with filling
	 * v4l2Ctrls, as updateControls() relies on both containers having the
	 * same order, and the control list is based on a map, which is not
	 * sorted by insertion order.
	 */

I might have missed what issue you have encountered.

I'm anyway not opposed to this change, as the ordering assumption is a
bit weird, even if it should be safe.

Changing such a core feature would require some careful testing, and
if there's no actual reason to change it I would be cautious to do so
but I'm not opposed...


> -Hiro
>
> > > > > +             switch (value.type()) {
> > > > >               case ControlTypeInteger64:
> > > > > -                     value.set<int64_t>(v4l2Ctrl->value64);
> > > > > +                     value.set<int64_t>(v4l2Ctrl.value64);
> > > > >                       break;
> > > > >
> > > > >               case ControlTypeByte:
> > > > > @@ -552,11 +552,11 @@ void V4L2Device::updateControls(ControlList *ctrls,
> > > > >                        * \todo To be changed when support for string controls
> > > > >                        * will be added.
> > > > >                        */
> > > > > -                     value.set<int32_t>(v4l2Ctrl->value);
> > > > > +                     value.set<int32_t>(v4l2Ctrl.value);
> > > > >                       break;
> > > > >               }
> > > > >
> > > > > -             i++;
> > > > > +             ctrls->set(id, value);
> > > > >       }
> > > > >  }
> > > > >
> >
> > --
> > Regards,
> >
> > Laurent Pinchart
> _______________________________________________
> libcamera-devel mailing list
> libcamera-devel at lists.libcamera.org
> https://lists.libcamera.org/listinfo/libcamera-devel