From 4671911df040aeb3fdda07ae7cd2ce41eb6421cd Mon Sep 17 00:00:00 2001
From: Marian Cichy <m.cichy@pengutronix.de>
Date: Mon, 15 Mar 2021 11:17:25 +0100
Subject: pipeline: simple: Use breadth-first search to setup media pipeline

When the SimplePipeline is setting up its data and media pipeline in the
SimpleCameraData constructor, it merely tries to find the first valid
pad and link to the next entity, starting from the camera sensor.
Following this path may not always lead to a valid capture device and
therefore the setup will fail on some machines. This is for example an
issue when using the SimplePipeline on an i.MX-6Q with its i.MX IPU.

This commit implements a different approach to setup the media-pipeline
by finding the shortest path to a valid capture device, using the
breadth-first search algorithm. On i.MX6Q, the shortest path has a good
chance to be the path from the sensor to the CSI capture device, as
other paths may involve image converters, encoders or other IPU blocks
and will have therefore more nodes.

Signed-off-by: Marian Cichy <m.cichy@pengutronix.de>
Reviewed-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com>
Signed-off-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com>
---
 src/libcamera/pipeline/simple/simple.cpp | 91 ++++++++++++++++++--------------
 1 file changed, 50 insertions(+), 41 deletions(-)

(limited to 'src/libcamera/pipeline/simple')

diff --git a/src/libcamera/pipeline/simple/simple.cpp b/src/libcamera/pipeline/simple/simple.cpp
index d7128156..cdf7e3ee 100644
--- a/src/libcamera/pipeline/simple/simple.cpp
+++ b/src/libcamera/pipeline/simple/simple.cpp
@@ -15,6 +15,7 @@
 #include <set>
 #include <string>
 #include <string.h>
+#include <unordered_map>
 #include <utility>
 #include <vector>
 
@@ -271,63 +272,71 @@ SimpleCameraData::SimpleCameraData(SimplePipelineHandler *pipe,
 	int ret;
 
 	/*
-	 * Walk the pipeline towards the video node and store all entities
-	 * along the way.
+	 * Find the shortest path from the camera sensor to a video capture
+	 * device using the breadth-first search algorithm. This heuristic will
+	 * be most likely to skip paths that aren't suitable for the simple
+	 * pipeline handler on more complex devices, and is guaranteed to
+	 * produce a valid path on all devices that have a single option.
+	 *
+	 * For instance, on the IPU-based i.MX6Q, the shortest path will skip
+	 * encoders and image converters, and will end in a CSI capture device.
 	 */
-	MediaEntity *source = sensor;
+	std::unordered_set<MediaEntity *> visited;
+	std::queue<MediaEntity *> queue;
 
-	while (source) {
-		/* If we have reached a video node, we're done. */
-		if (source->function() == MEDIA_ENT_F_IO_V4L)
-			break;
+	/* Remember at each entity where we came from. */
+	std::unordered_map<MediaEntity *, Entity> parents;
+	queue.push(sensor);
 
-		/*
-		 * Use the first output pad that has links and follow its first
-		 * link.
-		 */
-		MediaPad *sourcePad = nullptr;
-		MediaLink *sourceLink = nullptr;
-		for (MediaPad *pad : source->pads()) {
-			if ((pad->flags() & MEDIA_PAD_FL_SOURCE) &&
-			    !pad->links().empty()) {
-				sourcePad = pad;
-				sourceLink = pad->links().front();
-				break;
-			}
-		}
+	MediaEntity *entity = nullptr;
 
-		if (!sourcePad)
-			return;
+	while (!queue.empty()) {
+		entity = queue.back();
+		queue.pop();
 
-		entities_.push_back({ source, sourceLink });
+		/* Found the capture device. */
+		if (entity->function() == MEDIA_ENT_F_IO_V4L) {
+			LOG(SimplePipeline, Debug)
+				<< "Found capture device " << entity->name();
+			video_ = pipe->video(entity);
+			break;
+		}
 
-		source = sourceLink->sink()->entity();
+		/* The actual breadth-first search algorithm. */
+		visited.insert(entity);
+		for (MediaPad *pad : entity->pads()) {
+			if (!(pad->flags() & MEDIA_PAD_FL_SOURCE))
+				continue;
 
-		/* Avoid infinite loops. */
-		auto iter = std::find_if(entities_.begin(), entities_.end(),
-					 [&](const Entity &entity) {
-						 return entity.entity == source;
-					 });
-		if (iter != entities_.end()) {
-			LOG(SimplePipeline, Info) << "Loop detected in pipeline";
-			return;
+			for (MediaLink *link : pad->links()) {
+				MediaEntity *next = link->sink()->entity();
+				if (visited.find(next) == visited.end()) {
+					queue.push(next);
+					parents.insert({ next, { entity, link } });
+				}
+			}
 		}
 	}
 
-	/*
-	 * We have a valid pipeline, get the video device and create the camera
-	 * sensor.
-	 */
-	video_ = pipe->video(source);
 	if (!video_)
 		return;
 
+	/*
+	 * With the parents, we can follow back our way from the capture device
+	 * to the sensor.
+	 */
+	for (auto it = parents.find(entity); it != parents.end();
+	     it = parents.find(entity)) {
+		const Entity &e = it->second;
+		entities_.push_front(e);
+		entity = e.entity;
+	}
+
+	/* Finally also remember the sensor. */
 	sensor_ = std::make_unique<CameraSensor>(sensor);
 	ret = sensor_->init();
-	if (ret) {
+	if (ret)
 		sensor_.reset();
-		return;
-	}
 }
 
 int SimpleCameraData::init()
-- 
cgit v1.2.1