Hi Sakari,
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+rene...@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 ?
> 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.
--
Regards,
Laurent Pinchart
--
To unsubscribe from this list: send the line "unsubscribe linux-media" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
