[libcamera-devel] [PATCH] libcamera: V4L2Device: Remove the controls order assumption in updateControls()
Hirokazu Honda
hiroh at chromium.org
Thu Apr 22 04:14:59 CEST 2021
On Wed, Apr 21, 2021 at 9:36 PM Jacopo Mondi <jacopo at jmondi.org> wrote:
>
> 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.
> */
>
Thanks. I missed this comment.
> 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...
>
I actually have never faced any issue due to this.
As a reader, this assumption is unnecessary and thus feels strange for me.
Removing the assumption is simple enough I believe, so I hope this
change makes sense to everyone.
-Hiro
>
> > -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
More information about the libcamera-devel
mailing list