[libcamera-devel] [PATCH v2 1/1] pipeline: simple: Use breadth-first search to setup media pipeline

[Laurent Pinchart]

Hi Marian,

Thank you for the patch.

On Mon, Mar 15, 2021 at 11:17:25AM +0100, Marian Cichy wrote:
> 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. The shortest path has a good chance to be

I'll clarify that the last sentence is about i.MX6Q by phrasing it "On
i.MX6Q, the shortest path ...".

> 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 at pengutronix.de>

Tested-by: Laurent Pinchart <laurent.pinchart at ideasonboard.com>
Reviewed-by: Laurent Pinchart <laurent.pinchart at ideasonboard.com>

And pushed.

> ---
> changelog:
> 
> - Renamed uniform-cost search to breadth-first search in commit message
> - Renamed uniform-cost search to breadth-first search in code comment
> - Rephrased comment for more generic cases
> - Fixed code-style issues
> - Include <unordered_map>
> - Replace std::pair<> with struct Entity
> - Rename parentList to parents
> - Applied various suggestions to simplify code and reduce indentation
> - Make debug-message for found capture device more explicit
> - Avoid double-lookup when backtracing the parents
> - Drop MEDIA_LNK_FL_ENABLED/IMMUTABLE chreck
> ---
> 
>  src/libcamera/pipeline/simple/simple.cpp | 91 +++++++++++++-----------
>  1 file changed, 50 insertions(+), 41 deletions(-)
> 
> diff --git a/src/libcamera/pipeline/simple/simple.cpp b/src/libcamera/pipeline/simple/simple.cpp
> index 1fcf3671..d24d7199 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>
>  
> @@ -274,63 +275,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()

-- 
Regards,

Laurent Pinchart