The graph traversal API (media_entity_graph_walk_*) doesn't support
cyclic graphs and will fail to correctly walk a graph when circular
links exist. Support circular graph traversal by checking whether an
entity has already been visited before pushing it to the stack.
Signed-off-by: Laurent Pinchart laurent.pinchart+rene...@ideasonboard.com
Acked-by: Sakari Ailus sakari.ai...@iki.fi
---
drivers/media/media-entity.c | 14 +++---
include/media/media-entity.h | 4
2 files changed, 15 insertions(+), 3 deletions(-)
diff --git a/drivers/media/media-entity.c b/drivers/media/media-entity.c
index cb30ffb..2c286c3 100644
--- a/drivers/media/media-entity.c
+++ b/drivers/media/media-entity.c
@@ -20,6 +20,7 @@
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
+#include linux/bitmap.h
#include linux/module.h
#include linux/slab.h
#include media/media-entity.h
@@ -121,7 +122,6 @@ 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)
@@ -140,6 +140,12 @@ void media_entity_graph_walk_start(struct
media_entity_graph *graph,
{
graph-top = 0;
graph-stack[graph-top].entity = NULL;
+ bitmap_zero(graph-entities, MEDIA_ENTITY_ENUM_MAX_ID);
+
+ if (WARN_ON(entity-id = MEDIA_ENTITY_ENUM_MAX_ID))
+ return;
+
+ __set_bit(entity-id, graph-entities);
stack_push(graph, entity);
}
EXPORT_SYMBOL_GPL(media_entity_graph_walk_start);
@@ -180,9 +186,11 @@ 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);
+ if (WARN_ON(next-id = MEDIA_ENTITY_ENUM_MAX_ID))
+ return NULL;
- /* Was it the entity we came here from? */
- if (next == stack_peek(graph)) {
+ /* Has the entity already been visited? */
+ if (__test_and_set_bit(next-id, graph-entities)) {
link_top(graph)++;
continue;
}
diff --git a/include/media/media-entity.h b/include/media/media-entity.h
index 06bacf9..10df551 100644
--- a/include/media/media-entity.h
+++ b/include/media/media-entity.h
@@ -23,6 +23,7 @@
#ifndef _MEDIA_ENTITY_H
#define _MEDIA_ENTITY_H
+#include linux/bitops.h
#include linux/list.h
#include linux/media.h
@@ -113,12 +114,15 @@ static inline u32 media_entity_subtype(struct
media_entity *entity)
}
#define MEDIA_ENTITY_ENUM_MAX_DEPTH16
+#define MEDIA_ENTITY_ENUM_MAX_ID 64
struct media_entity_graph {
struct {
struct media_entity *entity;
int link;
} stack[MEDIA_ENTITY_ENUM_MAX_DEPTH];
+
+ DECLARE_BITMAP(entities, MEDIA_ENTITY_ENUM_MAX_ID);
int top;
};
--
1.8.1.5
--
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
