Patch Detail
Show a patch.
GET /api/1.1/patches/11578/?format=api
{ "id": 11578, "url": "https://patchwork.libcamera.org/api/1.1/patches/11578/?format=api", "web_url": "https://patchwork.libcamera.org/patch/11578/", "project": { "id": 1, "url": "https://patchwork.libcamera.org/api/1.1/projects/1/?format=api", "name": "libcamera", "link_name": "libcamera", "list_id": "libcamera_core", "list_email": "libcamera-devel@lists.libcamera.org", "web_url": "", "scm_url": "", "webscm_url": "" }, "msgid": "<20210315101725.31371-2-m.cichy@pengutronix.de>", "date": "2021-03-15T10:17:25", "name": "[libcamera-devel,v2,1/1] pipeline: simple: Use breadth-first search to setup media pipeline", "commit_ref": null, "pull_url": null, "state": "accepted", "archived": false, "hash": "c7b851d9361cfd3cc528b65ea0b043bd54c18b04", "submitter": { "id": 80, "url": "https://patchwork.libcamera.org/api/1.1/people/80/?format=api", "name": "Marian Cichy", "email": "m.cichy@pengutronix.de" }, "delegate": null, "mbox": "https://patchwork.libcamera.org/patch/11578/mbox/", "series": [ { "id": 1791, "url": "https://patchwork.libcamera.org/api/1.1/series/1791/?format=api", "web_url": "https://patchwork.libcamera.org/project/libcamera/list/?series=1791", "date": "2021-03-15T10:17:24", "name": "Use breadth-first search in media-pipeline setup", "version": 2, "mbox": "https://patchwork.libcamera.org/series/1791/mbox/" } ], "comments": "https://patchwork.libcamera.org/api/patches/11578/comments/", "check": "pending", "checks": "https://patchwork.libcamera.org/api/patches/11578/checks/", "tags": {}, "headers": { "Return-Path": "<libcamera-devel-bounces@lists.libcamera.org>", "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 6502DBD80E\n\tfor <parsemail@patchwork.libcamera.org>;\n\tMon, 15 Mar 2021 10:17:33 +0000 (UTC)", "from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 5ACC468D43;\n\tMon, 15 Mar 2021 11:17:32 +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 9655668D3E\n\tfor <libcamera-devel@lists.libcamera.org>;\n\tMon, 15 Mar 2021 11:17:30 +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 <mci@pengutronix.de>)\n\tid 1lLkHx-0008RT-TN; Mon, 15 Mar 2021 11:17:29 +0100", "from mci by dude02.hi.pengutronix.de with local (Exim 4.92)\n\t(envelope-from <mci@pengutronix.de>)\n\tid 1lLkHx-0008VE-Kv; Mon, 15 Mar 2021 11:17:29 +0100" ], "From": "Marian Cichy <m.cichy@pengutronix.de>", "To": "libcamera-devel@lists.libcamera.org", "Date": "Mon, 15 Mar 2021 11:17:25 +0100", "Message-Id": "<20210315101725.31371-2-m.cichy@pengutronix.de>", "X-Mailer": "git-send-email 2.29.2", "In-Reply-To": "<20210315101725.31371-1-m.cichy@pengutronix.de>", "References": "<20210315101725.31371-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 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": "<libcamera-devel.lists.libcamera.org>", "List-Unsubscribe": "<https://lists.libcamera.org/options/libcamera-devel>,\n\t<mailto:libcamera-devel-request@lists.libcamera.org?subject=unsubscribe>", "List-Archive": "<https://lists.libcamera.org/pipermail/libcamera-devel/>", "List-Post": "<mailto:libcamera-devel@lists.libcamera.org>", "List-Help": "<mailto:libcamera-devel-request@lists.libcamera.org?subject=help>", "List-Subscribe": "<https://lists.libcamera.org/listinfo/libcamera-devel>,\n\t<mailto:libcamera-devel-request@lists.libcamera.org?subject=subscribe>", "Cc": "graphics@pengutronix.de, Marian Cichy <m.cichy@pengutronix.de>", "Content-Type": "text/plain; charset=\"us-ascii\"", "Content-Transfer-Encoding": "7bit", "Errors-To": "libcamera-devel-bounces@lists.libcamera.org", "Sender": "\"libcamera-devel\" <libcamera-devel-bounces@lists.libcamera.org>" }, "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 i.MX 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\nbreadth-first 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 <m.cichy@pengutronix.de>\n---\nchangelog:\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 <unordered_map>\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(-)", "diff": "diff --git a/src/libcamera/pipeline/simple/simple.cpp b/src/libcamera/pipeline/simple/simple.cpp\nindex 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 <set>\n #include <string>\n #include <string.h>\n+#include <unordered_map>\n #include <utility>\n #include <vector>\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<MediaEntity *> visited;\n+\tstd::queue<MediaEntity *> 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<MediaEntity *, Entity> 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<CameraSensor>(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()\n", "prefixes": [ "libcamera-devel", "v2", "1/1" ] }