[{"id":15713,"web_url":"https://patchwork.libcamera.org/comment/15713/","msgid":"","date":"2021-03-16T00:12:14","subject":"Re: [libcamera-devel] [PATCH v2 1/1] pipeline: simple: Use\n\tbreadth-first search to setup media pipeline","submitter":{"id":2,"url":"https://patchwork.libcamera.org/api/people/2/","name":"Laurent Pinchart","email":"laurent.pinchart@ideasonboard.com"},"content":"Hi Marian,\n\nThank you for the patch.\n\nOn Mon, Mar 15, 2021 at 11:17:25AM +0100, Marian Cichy wrote:\n> When the SimplePipeline is setting up its data and media pipeline in the\n> SimpleCameraData constructor, it merely tries to find the first valid\n> pad and link to the next entity, starting from the camera sensor.\n> Following this path may not always lead to a valid capture device and\n> therefore the setup will fail on some machines. This is for example an\n> issue when using the SimplePipeline on an i.MX-6Q with its i.MX IPU.\n> \n> This commit implements a different approach to setup the media-pipeline\n> by finding the shortest path to a valid capture device, using the\n> breadth-first search algorithm. The shortest path has a good chance to be\n\nI'll clarify that the last sentence is about i.MX6Q by phrasing it \"On\ni.MX6Q, the shortest path ...\".\n\n> the path from the sensor to the CSI capture device, as other paths may\n> involve image converters, encoders or other IPU blocks and will have\n> therefore more nodes.\n> \n> Signed-off-by: Marian Cichy \n\nTested-by: Laurent Pinchart \nReviewed-by: Laurent Pinchart \n\nAnd pushed.\n\n> ---\n> changelog:\n> \n> - Renamed uniform-cost search to breadth-first search in commit message\n> - Renamed uniform-cost search to breadth-first search in code comment\n> - Rephrased comment for more generic cases\n> - Fixed code-style issues\n> - Include \n> - Replace std::pair<> with struct Entity\n> - Rename parentList to parents\n> - Applied various suggestions to simplify code and reduce indentation\n> - Make debug-message for found capture device more explicit\n> - Avoid double-lookup when backtracing the parents\n> - Drop MEDIA_LNK_FL_ENABLED/IMMUTABLE chreck\n> ---\n> \n> src/libcamera/pipeline/simple/simple.cpp | 91 +++++++++++++-----------\n> 1 file changed, 50 insertions(+), 41 deletions(-)\n> \n> diff --git a/src/libcamera/pipeline/simple/simple.cpp b/src/libcamera/pipeline/simple/simple.cpp\n> index 1fcf3671..d24d7199 100644\n> --- a/src/libcamera/pipeline/simple/simple.cpp\n> +++ b/src/libcamera/pipeline/simple/simple.cpp\n> @@ -15,6 +15,7 @@\n> #include \n> #include \n> #include \n> +#include \n> #include \n> #include \n> \n> @@ -274,63 +275,71 @@ SimpleCameraData::SimpleCameraData(SimplePipelineHandler *pipe,\n> \tint ret;\n> \n> \t/*\n> -\t * Walk the pipeline towards the video node and store all entities\n> -\t * along the way.\n> +\t * Find the shortest path from the camera sensor to a video capture\n> +\t * device using the breadth-first search algorithm. This heuristic will\n> +\t * be most likely to skip paths that aren't suitable for the simple\n> +\t * pipeline handler on more complex devices, and is guaranteed to\n> +\t * produce a valid path on all devices that have a single option.\n> +\t *\n> +\t * For instance, on the IPU-based i.MX6Q, the shortest path will skip\n> +\t * encoders and image converters, and will end in a CSI capture device.\n> \t */\n> -\tMediaEntity *source = sensor;\n> +\tstd::unordered_set visited;\n> +\tstd::queue queue;\n> \n> -\twhile (source) {\n> -\t\t/* If we have reached a video node, we're done. */\n> -\t\tif (source->function() == MEDIA_ENT_F_IO_V4L)\n> -\t\t\tbreak;\n> +\t/* Remember at each entity where we came from. */\n> +\tstd::unordered_map parents;\n> +\tqueue.push(sensor);\n> \n> -\t\t/*\n> -\t\t * Use the first output pad that has links and follow its first\n> -\t\t * link.\n> -\t\t */\n> -\t\tMediaPad *sourcePad = nullptr;\n> -\t\tMediaLink *sourceLink = nullptr;\n> -\t\tfor (MediaPad *pad : source->pads()) {\n> -\t\t\tif ((pad->flags() & MEDIA_PAD_FL_SOURCE) &&\n> -\t\t\t !pad->links().empty()) {\n> -\t\t\t\tsourcePad = pad;\n> -\t\t\t\tsourceLink = pad->links().front();\n> -\t\t\t\tbreak;\n> -\t\t\t}\n> -\t\t}\n> +\tMediaEntity *entity = nullptr;\n> \n> -\t\tif (!sourcePad)\n> -\t\t\treturn;\n> +\twhile (!queue.empty()) {\n> +\t\tentity = queue.back();\n> +\t\tqueue.pop();\n> \n> -\t\tentities_.push_back({ source, sourceLink });\n> +\t\t/* Found the capture device. */\n> +\t\tif (entity->function() == MEDIA_ENT_F_IO_V4L) {\n> +\t\t\tLOG(SimplePipeline, Debug)\n> +\t\t\t\t<< \"Found capture device \" << entity->name();\n> +\t\t\tvideo_ = pipe->video(entity);\n> +\t\t\tbreak;\n> +\t\t}\n> \n> -\t\tsource = sourceLink->sink()->entity();\n> +\t\t/* The actual breadth-first search algorithm. */\n> +\t\tvisited.insert(entity);\n> +\t\tfor (MediaPad *pad : entity->pads()) {\n> +\t\t\tif (!(pad->flags() & MEDIA_PAD_FL_SOURCE))\n> +\t\t\t\tcontinue;\n> \n> -\t\t/* Avoid infinite loops. */\n> -\t\tauto iter = std::find_if(entities_.begin(), entities_.end(),\n> -\t\t\t\t\t [&](const Entity &entity) {\n> -\t\t\t\t\t\t return entity.entity == source;\n> -\t\t\t\t\t });\n> -\t\tif (iter != entities_.end()) {\n> -\t\t\tLOG(SimplePipeline, Info) << \"Loop detected in pipeline\";\n> -\t\t\treturn;\n> +\t\t\tfor (MediaLink *link : pad->links()) {\n> +\t\t\t\tMediaEntity *next = link->sink()->entity();\n> +\t\t\t\tif (visited.find(next) == visited.end()) {\n> +\t\t\t\t\tqueue.push(next);\n> +\t\t\t\t\tparents.insert({ next, { entity, link } });\n> +\t\t\t\t}\n> +\t\t\t}\n> \t\t}\n> \t}\n> \n> -\t/*\n> -\t * We have a valid pipeline, get the video device and create the camera\n> -\t * sensor.\n> -\t */\n> -\tvideo_ = pipe->video(source);\n> \tif (!video_)\n> \t\treturn;\n> \n> +\t/*\n> +\t * With the parents, we can follow back our way from the capture device\n> +\t * to the sensor.\n> +\t */\n> +\tfor (auto it = parents.find(entity); it != parents.end();\n> +\t it = parents.find(entity)) {\n> +\t\tconst Entity &e = it->second;\n> +\t\tentities_.push_front(e);\n> +\t\tentity = e.entity;\n> +\t}\n> +\n> +\t/* Finally also remember the sensor. */\n> \tsensor_ = std::make_unique(sensor);\n> \tret = sensor_->init();\n> -\tif (ret) {\n> +\tif (ret)\n> \t\tsensor_.reset();\n> -\t\treturn;\n> -\t}\n> }\n> \n> int SimpleCameraData::init()","headers":{"Return-Path":"","X-Original-To":"parsemail@patchwork.libcamera.org","Delivered-To":"parsemail@patchwork.libcamera.org","Received":["from lancelot.ideasonboard.com (lancelot.ideasonboard.com\n\t[92.243.16.209])\n\tby patchwork.libcamera.org (Postfix) with ESMTPS id 01ED3BD80E\n\tfor ;\n\tTue, 16 Mar 2021 00:12:52 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 71859602E3;\n\tTue, 16 Mar 2021 01:12:51 +0100 (CET)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 5C2F9602DB\n\tfor ;\n\tTue, 16 Mar 2021 01:12:50 +0100 (CET)","from pendragon.ideasonboard.com (62-78-145-57.bb.dnainternet.fi\n\t[62.78.145.57])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id CF0793E7;\n\tTue, 16 Mar 2021 01:12:49 +0100 (CET)"],"Authentication-Results":"lancelot.ideasonboard.com;\n\tdkim=fail reason=\"signature verification failed\" (1024-bit key;\n\tunprotected) header.d=ideasonboard.com header.i=@ideasonboard.com\n\theader.b=\"C6QTF3SK\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1615853570;\n\tbh=M5A7//mgLfKTjmoNKa5QAiYVaau1/ZGY+a1fRl4pGAU=;\n\th=Date:From:To:Cc:Subject:References:In-Reply-To:From;\n\tb=C6QTF3SK4CJRIfkuiSAjzQ1GsIm3iVhXkAV+Ehb8TO38J7SELeeraoT9T9/LCD5Ga\n\tot8JGMnABcligwvynHMVvQGxHdrtHQQbKkoqmhC6XugbI3n5LHf3vxa0NzYI+IwP+0\n\tCS4Tql9XU2aGuNgHMf0J5dVCNUvFAHmAi4Ux+a8M=","Date":"Tue, 16 Mar 2021 02:12:14 +0200","From":"Laurent Pinchart ","To":"Marian Cichy ","Message-ID":"","References":"<20210315101725.31371-1-m.cichy@pengutronix.de>\n\t<20210315101725.31371-2-m.cichy@pengutronix.de>","MIME-Version":"1.0","Content-Disposition":"inline","In-Reply-To":"<20210315101725.31371-2-m.cichy@pengutronix.de>","Subject":"Re: [libcamera-devel] [PATCH v2 1/1] pipeline: simple: Use\n\tbreadth-first search to setup media pipeline","X-BeenThere":"libcamera-devel@lists.libcamera.org","X-Mailman-Version":"2.1.29","Precedence":"list","List-Id":"","List-Unsubscribe":",\n\t","List-Archive":"","List-Post":"","List-Help":"","List-Subscribe":",\n\t","Cc":"libcamera-devel@lists.libcamera.org, graphics@pengutronix.de","Content-Type":"text/plain; charset=\"us-ascii\"","Content-Transfer-Encoding":"7bit","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "}}]