{"id":11536,"url":"https://patchwork.libcamera.org/api/1.1/patches/11536/?format=json","web_url":"https://patchwork.libcamera.org/patch/11536/","project":{"id":1,"url":"https://patchwork.libcamera.org/api/1.1/projects/1/?format=json","name":"libcamera","link_name":"libcamera","list_id":"libcamera_core","list_email":"libcamera-devel@lists.libcamera.org","web_url":"","scm_url":"","webscm_url":""},"msgid":"<20210309112949.26251-3-m.cichy@pengutronix.de>","date":"2021-03-09T11:29:49","name":"[libcamera-devel,2/2] pipeline: simple: Use uniform-cost search algorithm to setup media pipeline","commit_ref":null,"pull_url":null,"state":"superseded","archived":false,"hash":"1071d68ad314dc5e46033de9c3b71302ce35de11","submitter":{"id":80,"url":"https://patchwork.libcamera.org/api/1.1/people/80/?format=json","name":"Marian Cichy","email":"m.cichy@pengutronix.de"},"delegate":null,"mbox":"https://patchwork.libcamera.org/patch/11536/mbox/","series":[{"id":1777,"url":"https://patchwork.libcamera.org/api/1.1/series/1777/?format=json","web_url":"https://patchwork.libcamera.org/project/libcamera/list/?series=1777","date":"2021-03-09T11:29:49","name":"[libcamera-devel,1/2] media_entity: Overload == operator to use media-entities in maps","version":1,"mbox":"https://patchwork.libcamera.org/series/1777/mbox/"}],"comments":"https://patchwork.libcamera.org/api/patches/11536/comments/","check":"pending","checks":"https://patchwork.libcamera.org/api/patches/11536/checks/","tags":{},"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 09F8FBD80C\n\tfor ;\n\tTue, 9 Mar 2021 11:30:34 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 5C1C468AA3;\n\tTue, 9 Mar 2021 12:30:33 +0100 (CET)","from metis.ext.pengutronix.de (metis.ext.pengutronix.de\n\t[IPv6:2001:67c:670:201:290:27ff:fe1d:cc33])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 92AF1602E6\n\tfor ;\n\tTue, 9 Mar 2021 12:30:31 +0100 (CET)","from dude02.hi.pengutronix.de ([2001:67c:670:100:1d::28])\n\tby metis.ext.pengutronix.de with esmtps\n\t(TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92)\n\t(envelope-from )\n\tid 1lJaZK-000842-TG; Tue, 09 Mar 2021 12:30:30 +0100","from mci by dude02.hi.pengutronix.de with local (Exim 4.92)\n\t(envelope-from )\n\tid 1lJaZK-0007Sr-Ks; Tue, 09 Mar 2021 12:30:30 +0100"],"From":"Marian Cichy ","To":"libcamera-devel@lists.libcamera.org","Date":"Tue, 9 Mar 2021 12:29:49 +0100","Message-Id":"<20210309112949.26251-3-m.cichy@pengutronix.de>","X-Mailer":"git-send-email 2.29.2","In-Reply-To":"<20210309112949.26251-1-m.cichy@pengutronix.de>","References":"<20210309112949.26251-1-m.cichy@pengutronix.de>","MIME-Version":"1.0","X-SA-Exim-Connect-IP":"2001:67c:670:100:1d::28","X-SA-Exim-Mail-From":"mci@pengutronix.de","X-SA-Exim-Scanned":"No (on metis.ext.pengutronix.de);\n\tSAEximRunCond expanded to false","X-PTX-Original-Recipient":"libcamera-devel@lists.libcamera.org","Subject":"[libcamera-devel] [PATCH 2/2] pipeline: simple: Use uniform-cost\n\tsearch 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":"graphics@pengutronix.de, Marian Cichy ","Content-Type":"text/plain; charset=\"us-ascii\"","Content-Transfer-Encoding":"7bit","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "},"content":"When the SimplePipeline is setting up its data and media pipeline in the\nSimpleCameraData constructor, it merely tries to find the first valid\npad and link to the next entity, starting from the camera sensor.\nFollowing this path may not always lead to a valid capture device and\ntherefore the setup will fail on some machines. This is for example an\nissue when using the SimplePipeline on an i.MX-6Q with its IMX IPU.\n\nThis commit implements a different approach to setup the media-pipeline\nby finding the shortest path to a valid capture device, using the\nuniform-cost search algorithm. The shortest path has a good chance to be\nthe path from the sensor to the CSI capture device, as other paths may\ninvolve image converters, encoders or other IPU blocks and will have\ntherefore more nodes.\n\nSigned-off-by: Marian Cichy \n---\n src/libcamera/pipeline/simple/simple.cpp | 104 +++++++++++------------\n 1 file changed, 52 insertions(+), 52 deletions(-)","diff":"diff --git a/src/libcamera/pipeline/simple/simple.cpp b/src/libcamera/pipeline/simple/simple.cpp\nindex 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 \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+\tstd::queue queue;\n+\n+\t/* Remember at each entity where we came from */\n+\tstd::unordered_map> parentList;\n+\tqueue.push(sensor);\n+\n+\twhile (!queue.empty()) {\n+\t\tMediaEntity *entity = queue.back();\n+\t\tqueue.pop();\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+\t\t\tLOG(SimplePipeline, Debug) << \"Capture Device: \"\n+\t\t\t\t\t\t << entity->name();\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+\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+\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+\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 \n","prefixes":["libcamera-devel","2/2"]}