From: Laurent Pinchart <laurent.pinchart@ideasonboard.com>
To: Sakari Ailus <sakari.ailus@iki.fi>
Cc: Laurent Pinchart <laurent.pinchart+renesas@ideasonboard.com>,
linux-media@vger.kernel.org, linux-sh@vger.kernel.org,
Hans Verkuil <hverkuil@xs4all.nl>
Subject: Re: [PATCH v2 1/5] media: Fix circular graph traversal
Date: Wed, 24 Jul 2013 14:09:09 +0000 [thread overview]
Message-ID: <2101153.GOPGx1zmjS@avalon> (raw)
In-Reply-To: <20130718102209.GA11823@valkosipuli.retiisi.org.uk>
Hi Sakari,
On Thursday 18 July 2013 13:22:09 Sakari Ailus wrote:
> On Thu, Jul 18, 2013 at 01:06:40AM +0200, Laurent Pinchart wrote:
> > On Wednesday 17 July 2013 22:47:03 Sakari Ailus wrote:
> > > On Wed, Jul 17, 2013 at 04:54:38PM +0200, Laurent Pinchart wrote:
> > > > The graph traversal API (media_entity_graph_walk_*) will fail to
> > > > correctly walk the graph when circular links exist. Fix it by checking
> > > > whether an entity is already present in the stack before pushing it.
> > >
> > > We never had any multiply connected graphs (ignoring direction, nor
> > > supported them) before. So this is rather a patch that adds support for
> > > those instead of fixing it. :-)
> >
> > Good point, I'll add support for your comment to the commit message :-D
> >
> > > > Signed-off-by: Laurent Pinchart
> > > > <laurent.pinchart+renesas@ideasonboard.com>
> > > > ---
> > > >
> > > > drivers/media/media-entity.c | 17 ++++++++++++-----
> > > > 1 file changed, 12 insertions(+), 5 deletions(-)
> > > >
> > > > diff --git a/drivers/media/media-entity.c
> > > > b/drivers/media/media-entity.c
> > > > index cb30ffb..c8aba5e 100644
> > > > --- a/drivers/media/media-entity.c
> > > > +++ b/drivers/media/media-entity.c
> > > > @@ -121,9 +121,9 @@ static struct media_entity *stack_pop(struct
> > > > media_entity_graph *graph)
> > > >
> > > > return entity;
> > > >
> > > > }
> > > >
> > > > -#define stack_peek(en) ((en)->stack[(en)->top - 1].entity)
> > > > -#define link_top(en) ((en)->stack[(en)->top].link)
> > > > -#define stack_top(en) ((en)->stack[(en)->top].entity)
> > > > +#define stack_peek(en, i) ((en)->stack[i].entity)
> > > > +#define link_top(en) ((en)->stack[(en)->top].link)
> > > > +#define stack_top(en) ((en)->stack[(en)->top].entity)
> > > >
> > > > /**
> > > >
> > > > * media_entity_graph_walk_start - Start walking the media graph at a
> > > > given entity>
> > > >
> > > > @@ -159,6 +159,8 @@ EXPORT_SYMBOL_GPL(media_entity_graph_walk_start);
> > > >
> > > > struct media_entity *
> > > > media_entity_graph_walk_next(struct media_entity_graph *graph)
> > > > {
> > > >
> > > > + unsigned int i;
> > > > +
> > > >
> > > > if (stack_top(graph) = NULL)
> > > >
> > > > return NULL;
> > > >
> > > > @@ -181,8 +183,13 @@ media_entity_graph_walk_next(struct
> > > > media_entity_graph *graph)>
> > > >
> > > > /* Get the entity in the other end of the link . */
> > > > next = media_entity_other(entity, link);
> > > >
> > > > - /* Was it the entity we came here from? */
> > > > - if (next = stack_peek(graph)) {
> > > > + /* Is the entity already in the path? */
> > > > + for (i = 1; i < graph->top; ++i) {
> > > > + if (next = stack_peek(graph, i))
> > > > + break;
> > > > + }
> > > > +
> > > > + if (i < graph->top) {
> > > >
> > > > link_top(graph)++;
> > > > continue;
> > > >
> > > > }
> > >
> > > I think you should also ensure a node in the graph hasn't been
> > > enumerated in the past; otherwise it's possible to do that multiple
> > > times in a multiply connected graph.
> >
> > I'm not sure to follow you here, could you please elaborate ?
>
> Depth-first search in a multiply connected graph must avoid finding again
> the same nodes. As we didn't have multiply connected graphs, the only thing
> that was necessary was to avoid going back exactly the same route that the
> search came from.
>
> In a multiply connected graph a node can be reached through multiple paths.
> This means that instead of avoiding to go back where we came from (either
> the previous node or the full stack), we must avoid finding again the same
> nodes we've found previously.
Indeed, I somehow managed to overlook the issue. That's not really a problem
in my case, as circular graphs are not supported by my hardware, but a generic
solution is indeed needed.
> > > How about using a bit field that contained as many bits as there were
> > > entities? It's also faster to check for a single bit than loop over the
> > > whole path for each entity, which certainly will start showing in
> > > execution time with these link numbres.
> >
> > That's possible, yes. We would then need to dynamically allocate the bit
> > field in the start function, and add a new media_entity_graph_walk_end()
> > function (I would then rename media_entity_graph_walk_start() to
> > media_entity_graph_walk_begin()) to free the bit field. If you think
> > that's worth it I can give it a try.
>
> Do you think we could define a maximum number of entities? It can be
> increased if any driver happens to need more. I'd be more comfortable in
> doing the allocation in the stack that way: the number will be relatively
> small in any case, say, 32 or 64 bits for which kzalloc() would be overkill.
This should work for now, but I'm a bit concerned that it would break in the
future if we introduce dynamic entity (un)registration. In that case the
maximum number of entities could be capped, but the IDs will increase.
--
Regards,
Laurent Pinchart
next prev parent reply other threads:[~2013-07-24 14:09 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-07-17 14:54 [PATCH v2 0/5] Renesas VSP1 driver Laurent Pinchart
2013-07-17 14:54 ` [PATCH v2 1/5] media: Fix circular graph traversal Laurent Pinchart
2013-07-17 19:47 ` Sakari Ailus
2013-07-17 23:06 ` Laurent Pinchart
2013-07-18 10:22 ` Sakari Ailus
2013-07-24 14:09 ` Laurent Pinchart [this message]
2013-07-17 14:54 ` [PATCH v2 2/5] v4l: Fix V4L2_MBUS_FMT_YUV10_1X30 media bus pixel code value Laurent Pinchart
2013-07-17 14:54 ` [PATCH v2 3/5] v4l: Add media format codes for ARGB8888 and AYUV8888 on 32-bit busses Laurent Pinchart
2013-07-24 21:26 ` Sylwester Nawrocki
2013-07-25 11:44 ` Laurent Pinchart
2013-07-17 14:54 ` [PATCH v2 4/5] v4l: Add V4L2_PIX_FMT_NV16M and V4L2_PIX_FMT_NV61M formats Laurent Pinchart
2013-07-24 21:23 ` Sylwester Nawrocki
[not found] ` <1374072882-14598-6-git-send-email-laurent.pinchart+renesas@ideasonboard.com>
2013-07-24 10:38 ` [PATCH v2 5/5] v4l: Renesas R-Car VSP1 driver Katsuya MATSUBARA
2013-07-24 15:05 ` Laurent Pinchart
2013-07-24 22:48 ` Sakari Ailus
2013-07-25 11:46 ` Laurent Pinchart
2013-07-25 13:43 ` Sakari Ailus
2013-07-31 15:13 ` Laurent Pinchart
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=2101153.GOPGx1zmjS@avalon \
--to=laurent.pinchart@ideasonboard.com \
--cc=hverkuil@xs4all.nl \
--cc=laurent.pinchart+renesas@ideasonboard.com \
--cc=linux-media@vger.kernel.org \
--cc=linux-sh@vger.kernel.org \
--cc=sakari.ailus@iki.fi \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).