1 files changed, 441 insertions, 76 deletions

diff --git a/drivers/media/mc/mc-entity.c b/drivers/media/mc/mc-entity.c
index ad153a426a36..0a5c92b8bbce 100644
--- a/drivers/media/mc/mc-entity.c
+++ b/drivers/media/mc/mc-entity.c
@@ -226,6 +226,27 @@ EXPORT_SYMBOL_GPL(media_entity_pads_init);
  * Graph traversal
  */
 
+/*
+ * This function checks the interdependency inside the entity between @pad0
+ * and @pad1. If two pads are interdependent they are part of the same pipeline
+ * and enabling one of the pads means that the other pad will become "locked"
+ * and doesn't allow configuration changes.
+ *
+ * For the time being all pads are considered interdependent.
+ */
+static bool media_entity_has_pad_interdep(struct media_entity *entity,
+					  unsigned int pad0, unsigned int pad1)
+{
+	if (pad0 >= entity->num_pads || pad1 >= entity->num_pads)
+		return false;
+
+	if (entity->pads[pad0].flags & entity->pads[pad1].flags &
+	    (MEDIA_PAD_FL_SINK | MEDIA_PAD_FL_SOURCE))
+		return false;
+
+	return true;
+}
+
 static struct media_entity *
 media_entity_other(struct media_entity *entity, struct media_link *link)
 {
@@ -374,97 +395,436 @@ EXPORT_SYMBOL_GPL(media_graph_walk_next);
  * Pipeline management
  */
 
+/*
+ * The pipeline traversal stack stores pads that are reached during graph
+ * traversal, with a list of links to be visited to continue the traversal.
+ * When a new pad is reached, an entry is pushed on the top of the stack and
+ * points to the incoming pad and the first link of the entity.
+ *
+ * To find further pads in the pipeline, the traversal algorithm follows
+ * internal pad dependencies in the entity, and then links in the graph. It
+ * does so by iterating over all links of the entity, and following enabled
+ * links that originate from a pad that is internally connected to the incoming
+ * pad, as reported by the media_entity_has_pad_interdep() function.
+ */
+
+/**
+ * struct media_pipeline_walk_entry - Entry in the pipeline traversal stack
+ *
+ * @pad: The media pad being visited
+ * @links: Links left to be visited
+ */
+struct media_pipeline_walk_entry {
+	struct media_pad *pad;
+	struct list_head *links;
+};
+
+/**
+ * struct media_pipeline_walk - State used by the media pipeline traversal
+ *				algorithm
+ *
+ * @mdev: The media device
+ * @stack: Depth-first search stack
+ * @stack.size: Number of allocated entries in @stack.entries
+ * @stack.top: Index of the top stack entry (-1 if the stack is empty)
+ * @stack.entries: Stack entries
+ */
+struct media_pipeline_walk {
+	struct media_device *mdev;
+
+	struct {
+		unsigned int size;
+		int top;
+		struct media_pipeline_walk_entry *entries;
+	} stack;
+};
+
+#define MEDIA_PIPELINE_STACK_GROW_STEP		16
+
+static struct media_pipeline_walk_entry *
+media_pipeline_walk_top(struct media_pipeline_walk *walk)
+{
+	return &walk->stack.entries[walk->stack.top];
+}
+
+static bool media_pipeline_walk_empty(struct media_pipeline_walk *walk)
+{
+	return walk->stack.top == -1;
+}
+
+/* Increase the stack size by MEDIA_PIPELINE_STACK_GROW_STEP elements. */
+static int media_pipeline_walk_resize(struct media_pipeline_walk *walk)
+{
+	struct media_pipeline_walk_entry *entries;
+	unsigned int new_size;
+
+	/* Safety check, to avoid stack overflows in case of bugs. */
+	if (walk->stack.size >= 256)
+		return -E2BIG;
+
+	new_size = walk->stack.size + MEDIA_PIPELINE_STACK_GROW_STEP;
+
+	entries = krealloc(walk->stack.entries,
+			   new_size * sizeof(*walk->stack.entries),
+			   GFP_KERNEL);
+	if (!entries)
+		return -ENOMEM;
+
+	walk->stack.entries = entries;
+	walk->stack.size = new_size;
+
+	return 0;
+}
+
+/* Push a new entry on the stack. */
+static int media_pipeline_walk_push(struct media_pipeline_walk *walk,
+				    struct media_pad *pad)
+{
+	struct media_pipeline_walk_entry *entry;
+	int ret;
+
+	if (walk->stack.top + 1 >= walk->stack.size) {
+		ret = media_pipeline_walk_resize(walk);
+		if (ret)
+			return ret;
+	}
+
+	walk->stack.top++;
+	entry = media_pipeline_walk_top(walk);
+	entry->pad = pad;
+	entry->links = pad->entity->links.next;
+
+	dev_dbg(walk->mdev->dev,
+		"media pipeline: pushed entry %u: '%s':%u\n",
+		walk->stack.top, pad->entity->name, pad->index);
+
+	return 0;
+}
+
+/*
+ * Move the top entry link cursor to the next link. If all links of the entry
+ * have been visited, pop the entry itself.
+ */
+static void media_pipeline_walk_pop(struct media_pipeline_walk *walk)
+{
+	struct media_pipeline_walk_entry *entry;
+
+	if (WARN_ON(walk->stack.top < 0))
+		return;
+
+	entry = media_pipeline_walk_top(walk);
+
+	if (entry->links->next == &entry->pad->entity->links) {
+		dev_dbg(walk->mdev->dev,
+			"media pipeline: entry %u has no more links, popping\n",
+			walk->stack.top);
+
+		walk->stack.top--;
+		return;
+	}
+
+	entry->links = entry->links->next;
+
+	dev_dbg(walk->mdev->dev,
+		"media pipeline: moved entry %u to next link\n",
+		walk->stack.top);
+}
+
+/* Free all memory allocated while walking the pipeline. */
+static void media_pipeline_walk_destroy(struct media_pipeline_walk *walk)
+{
+	kfree(walk->stack.entries);
+}
+
+/* Add a pad to the pipeline and push it to the stack. */
+static int media_pipeline_add_pad(struct media_pipeline *pipe,
+				  struct media_pipeline_walk *walk,
+				  struct media_pad *pad)
+{
+	struct media_pipeline_pad *ppad;
+
+	list_for_each_entry(ppad, &pipe->pads, list) {
+		if (ppad->pad == pad) {
+			dev_dbg(pad->graph_obj.mdev->dev,
+				"media pipeline: already contains pad '%s':%u\n",
+				pad->entity->name, pad->index);
+			return 0;
+		}
+	}
+
+	ppad = kzalloc(sizeof(*ppad), GFP_KERNEL);
+	if (!ppad)
+		return -ENOMEM;
+
+	ppad->pipe = pipe;
+	ppad->pad = pad;
+
+	list_add_tail(&ppad->list, &pipe->pads);
+
+	dev_dbg(pad->graph_obj.mdev->dev,
+		"media pipeline: added pad '%s':%u\n",
+		pad->entity->name, pad->index);
+
+	return media_pipeline_walk_push(walk, pad);
+}
+
+/* Explore the next link of the entity at the top of the stack. */
+static int media_pipeline_explore_next_link(struct media_pipeline *pipe,
+					    struct media_pipeline_walk *walk)
+{
+	struct media_pipeline_walk_entry *entry = media_pipeline_walk_top(walk);
+	struct media_pad *pad;
+	struct media_link *link;
+	struct media_pad *local;
+	struct media_pad *remote;
+	int ret;
+
+	pad = entry->pad;
+	link = list_entry(entry->links, typeof(*link), list);
+	media_pipeline_walk_pop(walk);
+
+	dev_dbg(walk->mdev->dev,
+		"media pipeline: exploring link '%s':%u -> '%s':%u\n",
+		link->source->entity->name, link->source->index,
+		link->sink->entity->name, link->sink->index);
+
+	/* Skip links that are not enabled. */
+	if (!(link->flags & MEDIA_LNK_FL_ENABLED)) {
+		dev_dbg(walk->mdev->dev,
+			"media pipeline: skipping link (disabled)\n");
+		return 0;
+	}
+
+	/* Get the local pad and remote pad. */
+	if (link->source->entity == pad->entity) {
+		local = link->source;
+		remote = link->sink;
+	} else {
+		local = link->sink;
+		remote = link->source;
+	}
+
+	/*
+	 * Skip links that originate from a different pad than the incoming pad
+	 * that is not connected internally in the entity to the incoming pad.
+	 */
+	if (pad != local &&
+	    !media_entity_has_pad_interdep(pad->entity, pad->index, local->index)) {
+		dev_dbg(walk->mdev->dev,
+			"media pipeline: skipping link (no route)\n");
+		return 0;
+	}
+
+	/*
+	 * Add the local and remote pads of the link to the pipeline and push
+	 * them to the stack, if they're not already present.
+	 */
+	ret = media_pipeline_add_pad(pipe, walk, local);
+	if (ret)
+		return ret;
+
+	ret = media_pipeline_add_pad(pipe, walk, remote);
+	if (ret)
+		return ret;
+
+	return 0;
+}
+
+static void media_pipeline_cleanup(struct media_pipeline *pipe)
+{
+	while (!list_empty(&pipe->pads)) {
+		struct media_pipeline_pad *ppad;
+
+		ppad = list_first_entry(&pipe->pads, typeof(*ppad), list);
+		list_del(&ppad->list);
+		kfree(ppad);
+	}
+}
+
+static int media_pipeline_populate(struct media_pipeline *pipe,
+				   struct media_pad *pad)
+{
+	struct media_pipeline_walk walk = { };
+	struct media_pipeline_pad *ppad;
+	int ret;
+
+	/*
+	 * Populate the media pipeline by walking the media graph, starting
+	 * from @pad.
+	 */
+	INIT_LIST_HEAD(&pipe->pads);
+	pipe->mdev = pad->graph_obj.mdev;
+
+	walk.mdev = pipe->mdev;
+	walk.stack.top = -1;
+	ret = media_pipeline_add_pad(pipe, &walk, pad);
+	if (ret)
+		goto done;
+
+	/*
+	 * Use a depth-first search algorithm: as long as the stack is not
+	 * empty, explore the next link of the top entry. The
+	 * media_pipeline_explore_next_link() function will either move to the
+	 * next link, pop the entry if fully visited, or add new entries on
+	 * top.
+	 */
+	while (!media_pipeline_walk_empty(&walk)) {
+		ret = media_pipeline_explore_next_link(pipe, &walk);
+		if (ret)
+			goto done;
+	}
+
+	dev_dbg(pad->graph_obj.mdev->dev,
+		"media pipeline populated, found pads:\n");
+
+	list_for_each_entry(ppad, &pipe->pads, list)
+		dev_dbg(pad->graph_obj.mdev->dev, "- '%s':%u\n",
+			ppad->pad->entity->name, ppad->pad->index);
+
+	WARN_ON(walk.stack.top != -1);
+
+	ret = 0;
+
+done:
+	media_pipeline_walk_destroy(&walk);
+
+	if (ret)
+		media_pipeline_cleanup(pipe);
+
+	return ret;
+}
+
 __must_check int __media_pipeline_start(struct media_entity *entity,
 					struct media_pipeline *pipe)
 {
 	struct media_device *mdev = entity->graph_obj.mdev;
-	struct media_graph *graph = &pipe->graph;
-	struct media_entity *entity_err = entity;
-	struct media_link *link;
+	struct media_pipeline_pad *err_ppad;
+	struct media_pipeline_pad *ppad;
 	int ret;
 
+	lockdep_assert_held(&mdev->graph_mutex);
+
+	/*
+	 * media_pipeline_start(entity) only makes sense with entities that have
+	 * a single pad.
+	 */
+
+	if (WARN_ON(entity->num_pads != 1))
+		return -EINVAL;
+
+	/*
+	 * If the entity is already part of a pipeline, that pipeline must
+	 * be the same as the pipe given to media_pipeline_start().
+	 */
+	if (WARN_ON(entity->pads->pipe && entity->pads->pipe != pipe))
+		return -EINVAL;
+
+	/*
+	 * If the pipeline has already been started, it is guaranteed to be
+	 * valid, so just increase the start count.
+	 */
 	if (pipe->start_count) {
 		pipe->start_count++;
 		return 0;
 	}
 
-	ret = media_graph_walk_init(&pipe->graph, mdev);
+	/*
+	 * Populate the pipeline. This populates the media_pipeline pads list
+	 * with media_pipeline_pad instances for each pad found during graph
+	 * walk.
+	 */
+	ret = media_pipeline_populate(pipe, entity->pads);
 	if (ret)
 		return ret;
 
-	media_graph_walk_start(&pipe->graph, entity);
+	/*
+	 * Now that all the pads in the pipeline have been gathered, perform
+	 * the validation steps.
+	 */
+
+	list_for_each_entry(ppad, &pipe->pads, list) {
+		struct media_pad *pad = ppad->pad;
+		struct media_entity *entity = pad->entity;
+		bool has_enabled_link = false;
+		bool has_link = false;
+		struct media_link *link;
 
-	while ((entity = media_graph_walk_next(graph))) {
-		DECLARE_BITMAP(active, MEDIA_ENTITY_MAX_PADS);
-		DECLARE_BITMAP(has_no_links, MEDIA_ENTITY_MAX_PADS);
+		dev_dbg(mdev->dev, "Validating pad '%s':%u\n", pad->entity->name,
+			pad->index);
 
-		if (entity->pipe && entity->pipe != pipe) {
-			pr_err("Pipe active for %s. Can't start for %s\n",
-				entity->name,
-				entity_err->name);
+		/*
+		 * 1. Ensure that the pad doesn't already belong to a different
+		 * pipeline.
+		 */
+		if (pad->pipe) {
+			dev_dbg(mdev->dev, "Failed to start pipeline: pad '%s':%u busy\n",
+				pad->entity->name, pad->index);
 			ret = -EBUSY;
 			goto error;
 		}
 
-		/* Already streaming --- no need to check. */
-		if (entity->pipe)
-			continue;
-
-		entity->pipe = pipe;
-
-		if (!entity->ops || !entity->ops->link_validate)
-			continue;
-
-		bitmap_zero(active, entity->num_pads);
-		bitmap_fill(has_no_links, entity->num_pads);
-
+		/*
+		 * 2. Validate all active links whose sink is the current pad.
+		 * Validation of the source pads is performed in the context of
+		 * the connected sink pad to avoid duplicating checks.
+		 */
 		for_each_media_entity_data_link(entity, link) {
-			struct media_pad *pad = link->sink->entity == entity
-						? link->sink : link->source;
+			/* Skip links unrelated to the current pad. */
+			if (link->sink != pad && link->source != pad)
+				continue;
 
-			/* Mark that a pad is connected by a link. */
-			bitmap_clear(has_no_links, pad->index, 1);
+			/* Record if the pad has links and enabled links. */
+			if (link->flags & MEDIA_LNK_FL_ENABLED)
+				has_enabled_link = true;
+			has_link = true;
 
 			/*
-			 * Pads that either do not need to connect or
-			 * are connected through an enabled link are
-			 * fine.
+			 * Validate the link if it's enabled and has the
+			 * current pad as its sink.
 			 */
-			if (!(pad->flags & MEDIA_PAD_FL_MUST_CONNECT) ||
-			    link->flags & MEDIA_LNK_FL_ENABLED)
-				bitmap_set(active, pad->index, 1);
+			if (!(link->flags & MEDIA_LNK_FL_ENABLED))
+				continue;
 
-			/*
-			 * Link validation will only take place for
-			 * sink ends of the link that are enabled.
-			 */
-			if (link->sink != pad ||
-			    !(link->flags & MEDIA_LNK_FL_ENABLED))
+			if (link->sink != pad)
+				continue;
+
+			if (!entity->ops || !entity->ops->link_validate)
 				continue;
 
 			ret = entity->ops->link_validate(link);
-			if (ret < 0 && ret != -ENOIOCTLCMD) {
-				dev_dbg(entity->graph_obj.mdev->dev,
-					"link validation failed for '%s':%u -> '%s':%u, error %d\n",
+			if (ret) {
+				dev_dbg(mdev->dev,
+					"Link '%s':%u -> '%s':%u failed validation: %d\n",
 					link->source->entity->name,
 					link->source->index,
-					entity->name, link->sink->index, ret);
+					link->sink->entity->name,
+					link->sink->index, ret);
 				goto error;
 			}
-		}
 
-		/* Either no links or validated links are fine. */
-		bitmap_or(active, active, has_no_links, entity->num_pads);
+			dev_dbg(mdev->dev,
+				"Link '%s':%u -> '%s':%u is valid\n",
+				link->source->entity->name,
+				link->source->index,
+				link->sink->entity->name,
+				link->sink->index);
+		}
 
-		if (!bitmap_full(active, entity->num_pads)) {
+		/*
+		 * 3. If the pad has the MEDIA_PAD_FL_MUST_CONNECT flag set,
+		 * ensure that it has either no link or an enabled link.
+		 */
+		if ((pad->flags & MEDIA_PAD_FL_MUST_CONNECT) && has_link &&
+		    !has_enabled_link) {
+			dev_dbg(mdev->dev,
+				"Pad '%s':%u must be connected by an enabled link\n",
+				pad->entity->name, pad->index);
 			ret = -ENOLINK;
-			dev_dbg(entity->graph_obj.mdev->dev,
-				"'%s':%u must be connected by an enabled link\n",
-				entity->name,
-				(unsigned)find_first_zero_bit(
-					active, entity->num_pads));
 			goto error;
 		}
+
+		/* Validation passed, store the pipe pointer in the pad. */
+		pad->pipe = pipe;
 	}
 
 	pipe->start_count++;
@@ -476,20 +836,15 @@ error:
 	 * Link validation on graph failed. We revert what we did and
 	 * return the error.
 	 */
-	media_graph_walk_start(graph, entity_err);
-
-	while ((entity_err = media_graph_walk_next(graph))) {
-		entity_err->pipe = NULL;
 
-		/*
-		 * We haven't started entities further than this so we quit
-		 * here.
-		 */
-		if (entity_err == entity)
+	list_for_each_entry(err_ppad, &pipe->pads, list) {
+		if (err_ppad == ppad)
 			break;
+
+		err_ppad->pad->pipe = NULL;
 	}
 
-	media_graph_walk_cleanup(graph);
+	media_pipeline_cleanup(pipe);
 
 	return ret;
 }
@@ -510,8 +865,8 @@ EXPORT_SYMBOL_GPL(media_pipeline_start);
 
 void __media_pipeline_stop(struct media_entity *entity)
 {
-	struct media_graph *graph = &entity->pipe->graph;
-	struct media_pipeline *pipe = entity->pipe;
+	struct media_pipeline *pipe = entity->pads->pipe;
+	struct media_pipeline_pad *ppad;
 
 	/*
 	 * If the following check fails, the driver has performed an
@@ -523,12 +878,10 @@ void __media_pipeline_stop(struct media_entity *entity)
 	if (--pipe->start_count)
 		return;
 
-	media_graph_walk_start(graph, entity);
+	list_for_each_entry(ppad, &pipe->pads, list)
+		ppad->pad->pipe = NULL;
 
-	while ((entity = media_graph_walk_next(graph)))
-		entity->pipe = NULL;
-
-	media_graph_walk_cleanup(graph);
+	media_pipeline_cleanup(pipe);
 
 	if (pipe->allocated)
 		kfree(pipe);
@@ -835,7 +1188,7 @@ int __media_entity_setup_link(struct media_link *link, u32 flags)
 {
 	const u32 mask = MEDIA_LNK_FL_ENABLED;
 	struct media_device *mdev;
-	struct media_entity *source, *sink;
+	struct media_pad *source, *sink;
 	int ret = -EBUSY;
 
 	if (link == NULL)
@@ -851,12 +1204,11 @@ int __media_entity_setup_link(struct media_link *link, u32 flags)
 	if (link->flags == flags)
 		return 0;
 
-	source = link->source->entity;
-	sink = link->sink->entity;
+	source = link->source;
+	sink = link->sink;
 
 	if (!(link->flags & MEDIA_LNK_FL_DYNAMIC) &&
-	    (media_entity_is_streaming(source) ||
-	     media_entity_is_streaming(sink)))
+	    (media_pad_is_streaming(source) || media_pad_is_streaming(sink)))
 		return -EBUSY;
 
 	mdev = source->graph_obj.mdev;
@@ -1034,10 +1386,23 @@ EXPORT_SYMBOL_GPL(media_entity_get_fwnode_pad);
 
 struct media_pipeline *media_entity_pipeline(struct media_entity *entity)
 {
-	return entity->pipe;
+	struct media_pad *pad;
+
+	media_entity_for_each_pad(entity, pad) {
+		if (pad->pipe)
+			return pad->pipe;
+	}
+
+	return NULL;
 }
 EXPORT_SYMBOL_GPL(media_entity_pipeline);
 
+struct media_pipeline *media_pad_pipeline(struct media_pad *pad)
+{
+	return pad->pipe;
+}
+EXPORT_SYMBOL_GPL(media_pad_pipeline);
+
 static void media_interface_init(struct media_device *mdev,
 				 struct media_interface *intf,
 				 u32 gobj_type,