[{"id":15639,"web_url":"https://patchwork.libcamera.org/comment/15639/","msgid":"","date":"2021-03-13T02:04:58","subject":"Re: [libcamera-devel] [PATCH 2/2] pipeline: simple: Use\n\tuniform-cost search algorithm 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 Tue, Mar 09, 2021 at 12:29:49PM +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 IMX 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> uniform-cost search algorithm. The shortest path has a good chance to be\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> ---\n> src/libcamera/pipeline/simple/simple.cpp | 104 +++++++++++------------\n> 1 file changed, 52 insertions(+), 52 deletions(-)\n> \n> diff --git a/src/libcamera/pipeline/simple/simple.cpp b/src/libcamera/pipeline/simple/simple.cpp\n> index 1fcf3671..82a3b402 100644\n> --- a/src/libcamera/pipeline/simple/simple.cpp\n> +++ b/src/libcamera/pipeline/simple/simple.cpp\n> @@ -274,62 +274,62 @@ 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 * Use the uniform-cost search algorithm to find the shortest path to a\n> +\t * capture device. The shortest path has a good chance to end in a\n> +\t * CSI capture device, as this is the most direct path for a camera.\n> +\t * There are other capture devices which ends in encoders or image\n> +\t * converters which will write the capture image to RAM. These paths\n> +\t * would be invalid for the purpose of SimplePipeline. These paths are\n> +\t * also usually longer as they would naturally contain IC- or encoder\n> +\t * IPU-blocks. Therefore, this algorithm will avoid these paths.\n\nThis comment is specific to the i.MX6, while the simple pipeline handler\nisn't. Could it be rephrased in a generic way ? The i.MX6-specific parts\ncould be kept as an example.\n\n> \t */\n> -\tMediaEntity *source = sensor;\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> -\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> +\tstd::unordered_set visited;\n\nThis should be\n\n\tstd::unordered_set visited;\n\nand similarly below. We have a script to catch coding style issues, in\nutils/checkstyle.py. I'd recommend enabling it as a git hook by copying\neither utils/hooks/post-commit or utils/hooks/pre-commit to the\n.git/hooks/ directory.\n\nPlease note that coding style decisions are not always clear-cut, the\nrecommendations of the script can be ignored when appropriate.\n\n> +\tstd::queue queue;\n> +\n> +\t/* Remember at each entity where we came from */\n> +\tstd::unordered_map> parentList;\n\nYou should include .\n\nHow about replacing the pair with Entity ? And as it's not a list, maybe\nwe should just it parentMap, or just parents ?\n\n> +\tqueue.push(sensor);\n> +\n> +\twhile (!queue.empty()) {\n> +\t\tMediaEntity *entity = queue.back();\n> +\t\tqueue.pop();\n\nLet's give the code a bit of room to breath with blank lines to separate\nfunctional blocks :-)\n\n> +\t\t/* Found the capture device */\n> +\t\tif (entity->function() == MEDIA_ENT_F_IO_V4L) {\n> +\t\t\tvideo_ = pipe->video(entity);\n\nHow about a\n\t\t\tbreak;\n\nhere, and moving the next block after the while() ? It will keep the\nsearch simpler to read and reduce indentation.\n\n> +\t\t\tLOG(SimplePipeline, Debug) << \"Capture Device: \"\n> +\t\t\t\t\t\t << entity->name();\n\nSomething that checkstyle.py doesn't know about yet, we write multi-line\nlog statements with a line break just after LOG():\n\n\t\t\tLOG(SimplePipeline, Debug)\n\t\t\t\t<< \"Capture Device: \" << entity->name();\n\nAnd maybe \"Found capture device\" to make it a bit more explicit ?\n\n> +\t\t\t/* With the parentList, we can follow back our way from\n> +\t\t\t * the capture device to the sensor. */\n> +\t\t\twhile (parentList.find(entity) != parentList.end()) {\n> +\t\t\t\tstd::pair p = parentList[entity];\n> +\t\t\t\tEntity e { p.first, p.second };\n> +\t\t\t\tentities_.push_front(e);\n> +\t\t\t\tentity = p.first;\n> +\t\t\t}\n\nWe could avoid a double-lookup (in the condition of the while look, and\nthrough the map's [] operator) with\n\n\t\t\tfor (auto it = parents.find(entity); it != parents.end();\n\t\t\t it = parents.find(entity)) {\n\t\t\t\tconst Entity &e = it->second;\n\t\t\t\tentities_.push_front(e);\n\t\t\t\tentity = e.entity;\n\t\t\t}\n\n> +\t\t\t/* Finally also remember the sensor */\n> +\t\t\tsensor_ = std::make_unique(sensor);\n> +\t\t\tret = sensor_->init();\n> +\t\t\tif (ret) {\n> +\t\t\t\tsensor_.reset();\n> \t\t\t}\n> -\t\t}\n> -\n> -\t\tif (!sourcePad)\n> -\t\t\treturn;\n> -\n> -\t\tentities_.push_back({ source, sourceLink });\n> -\n> -\t\tsource = sourceLink->sink()->entity();\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}\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> -\tsensor_ = std::make_unique(sensor);\n> -\tret = sensor_->init();\n> -\tif (ret) {\n> -\t\tsensor_.reset();\n> -\t\treturn;\n> +\t\t/* The actual uniform-cost 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\n\t\t\tif (!(pad->flags() & MEDIA_PAD_FL_SOURCE))\n\t\t\t\tcontinue;\n\nwill reduce indentation of the next block.\n\n> +\t\t\t\tfor (MediaLink *link : pad->links()) {\n> +\t\t\t\t\tif ((link->flags() & MEDIA_LNK_FL_ENABLED) ||\n> +\t\t\t\t\t !(link->flags() & MEDIA_LNK_FL_IMMUTABLE)) {\n\nYou can drop this check, as immutable links are always enabled.\n\n> +\t\t\t\t\t\tMediaEntity *next = link->sink()->entity();\n> +\t\t\t\t\t\tif (visited.find(next) == visited.end()) {\n> +\t\t\t\t\t\t\tqueue.push(next);\n> +\t\t\t\t\t\t\tparentList.insert( { next, { entity, link } });\n> +\t\t\t\t\t\t}\n> +\t\t\t\t\t}\n> +\t\t\t\t}\n> +\t\t\t}\n> +\t\t}\n> \t}\n> }\n\nAs I've implemented the changes described above in order to test the\ncode on i.MX7D, here's the result to save you from having to duplicate\nthe work. Feel free to include any of this in v2 after testing it on the\ni.MX6Q.\n\ndiff --git a/src/libcamera/pipeline/simple/simple.cpp b/src/libcamera/pipeline/simple/simple.cpp\nindex c0f870de9b2e..449c30651876 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@@ -272,63 +273,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 uniform-cost 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/* Remember at each entity where we came from. */\n+\tstd::unordered_map parents;\n+\tqueue.push(sensor);\n+\n+\tMediaEntity *entity = nullptr;\n+\n+\twhile (!queue.empty()) {\n+\t\tentity = queue.back();\n+\t\tqueue.pop();\n+\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\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/* The actual uniform-cost 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\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-\n-\t\tif (!sourcePad)\n-\t\t\treturn;\n-\n-\t\tentities_.push_back({ source, sourceLink });\n-\n-\t\tsource = sourceLink->sink()->entity();\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}\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 E3F89BD1F1\n\tfor ;\n\tSat, 13 Mar 2021 02:05:35 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 4F02E605B1;\n\tSat, 13 Mar 2021 03:05:35 +0100 (CET)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id D277C602E8\n\tfor ;\n\tSat, 13 Mar 2021 03:05:33 +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 4C624527;\n\tSat, 13 Mar 2021 03:05:33 +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=\"lPoAt2UH\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1615601133;\n\tbh=+omwcAxjvZalof0TgnHPB9BMYE1hr1t2iLejinFxR+8=;\n\th=Date:From:To:Cc:Subject:References:In-Reply-To:From;\n\tb=lPoAt2UHrQ8fhKUnvXmuMSsaWv1u/MM6TqCADWmypshWHA54g6U9ZaXlzODjSZmu+\n\tJRHumrz7vpzgPK0EpVPwQgFyp6QE2U+4IMcVsBZdSG6z5fH3mHmpH8aRFAEsiWDZuj\n\tZeLKHKnLW/Q4VQOVPa5Dpl5f4HsWP/2STsiTSHdw=","Date":"Sat, 13 Mar 2021 04:04:58 +0200","From":"Laurent Pinchart ","To":"Marian Cichy ","Message-ID":"","References":"<20210309112949.26251-1-m.cichy@pengutronix.de>\n\t<20210309112949.26251-3-m.cichy@pengutronix.de>","MIME-Version":"1.0","Content-Disposition":"inline","In-Reply-To":"<20210309112949.26251-3-m.cichy@pengutronix.de>","Subject":"Re: [libcamera-devel] [PATCH 2/2] pipeline: simple: Use\n\tuniform-cost search algorithm 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\" "}}]