Patch Detail
Show a patch.
GET /api/1.1/patches/23876/?format=api
{ "id": 23876, "url": "https://patchwork.libcamera.org/api/1.1/patches/23876/?format=api", "web_url": "https://patchwork.libcamera.org/patch/23876/", "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": "<20250721104622.1550908-9-barnabas.pocze@ideasonboard.com>", "date": "2025-07-21T10:46:08", "name": "[RFC,v2,08/22] Documentation: design: Document `MetadataList`", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": false, "hash": "29d27a20e4fb31f02d6d76908853c13308c3e786", "submitter": { "id": 216, "url": "https://patchwork.libcamera.org/api/1.1/people/216/?format=api", "name": "Barnabás Pőcze", "email": "barnabas.pocze@ideasonboard.com" }, "delegate": null, "mbox": "https://patchwork.libcamera.org/patch/23876/mbox/", "series": [ { "id": 5305, "url": "https://patchwork.libcamera.org/api/1.1/series/5305/?format=api", "web_url": "https://patchwork.libcamera.org/project/libcamera/list/?series=5305", "date": "2025-07-21T10:46:00", "name": "libcamera: Add `MetadataList`", "version": 2, "mbox": "https://patchwork.libcamera.org/series/5305/mbox/" } ], "comments": "https://patchwork.libcamera.org/api/patches/23876/comments/", "check": "pending", "checks": "https://patchwork.libcamera.org/api/patches/23876/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 8F0B9C3237\n\tfor <parsemail@patchwork.libcamera.org>;\n\tMon, 21 Jul 2025 10:46:45 +0000 (UTC)", "from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 0932E68FF8;\n\tMon, 21 Jul 2025 12:46:45 +0200 (CEST)", "from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id E4BBA68FE7\n\tfor <libcamera-devel@lists.libcamera.org>;\n\tMon, 21 Jul 2025 12:46:31 +0200 (CEST)", "from pb-laptop.local (185.221.140.39.nat.pool.zt.hu\n\t[185.221.140.39])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id 80FBD795A\n\tfor <libcamera-devel@lists.libcamera.org>;\n\tMon, 21 Jul 2025 12:45:54 +0200 (CEST)" ], "Authentication-Results": "lancelot.ideasonboard.com; dkim=pass (1024-bit key;\n\tunprotected) header.d=ideasonboard.com header.i=@ideasonboard.com\n\theader.b=\"t1OVmWAy\"; dkim-atps=neutral", "DKIM-Signature": "v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1753094755;\n\tbh=1Z4Ze4aBe0U7UvhRbDcjXrwxY+JnFDfPFd36A6o0Y5U=;\n\th=From:To:Subject:Date:In-Reply-To:References:From;\n\tb=t1OVmWAyn7lESevj9o/sl1lKorB31Nj4MPbmY30ViF4V8SBezaBbFQkMEsiGWxHeu\n\t/46StTOvPvCODcmv82ogPElMigo5simYFAw0oqBVHh9uSo4PU8pT6x+MkZ7ysHuQfr\n\tkk92u30sl7RPOyYESXMvAYFq4j1iM7pnOhA3edlU=", "From": "=?utf-8?q?Barnab=C3=A1s_P=C5=91cze?= <barnabas.pocze@ideasonboard.com>", "To": "libcamera-devel@lists.libcamera.org", "Subject": "[RFC PATCH v2 08/22] Documentation: design: Document `MetadataList`", "Date": "Mon, 21 Jul 2025 12:46:08 +0200", "Message-ID": "<20250721104622.1550908-9-barnabas.pocze@ideasonboard.com>", "X-Mailer": "git-send-email 2.50.1", "In-Reply-To": "<20250721104622.1550908-1-barnabas.pocze@ideasonboard.com>", "References": "<20250721104622.1550908-1-barnabas.pocze@ideasonboard.com>", "MIME-Version": "1.0", "Content-Type": "text/plain; charset=UTF-8", "Content-Transfer-Encoding": "8bit", "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>", "Errors-To": "libcamera-devel-bounces@lists.libcamera.org", "Sender": "\"libcamera-devel\" <libcamera-devel-bounces@lists.libcamera.org>" }, "content": "Add a document describing the problem, the choices,\nand the design of the separate metadata list type.\n\nSigned-off-by: Barnabás Pőcze <barnabas.pocze@ideasonboard.com>\n---\nchanges in v2:\n * rewrite \"Thread safety\" section\n---\n Documentation/design/metadata-list.rst | 263 +++++++++++++++++++++++++\n Documentation/index.rst | 1 +\n Documentation/meson.build | 1 +\n 3 files changed, 265 insertions(+)\n create mode 100644 Documentation/design/metadata-list.rst", "diff": "diff --git a/Documentation/design/metadata-list.rst b/Documentation/design/metadata-list.rst\nnew file mode 100644\nindex 000000000..01af091c5\n--- /dev/null\n+++ b/Documentation/design/metadata-list.rst\n@@ -0,0 +1,263 @@\n+.. SPDX-License-Identifier: CC-BY-SA-4.0\n+\n+Design of the metadata list\n+===========================\n+\n+This document explains the design and rationale of the metadata list.\n+\n+Description of the problem\n+--------------------------\n+\n+Early metadata\n+^^^^^^^^^^^^^^\n+\n+A pipeline handler might report numerous metadata items to the application about\n+a single request. It is likely that different metadata items become available at\n+different points in time while a request is being processed.\n+\n+Simultaneously, an application might desire to carry out potentially non-trivial\n+extra processing on the image, etc. using certain metadata items. For such an\n+application it is likely best if the value of each metadata item is reported as\n+soon as possible, thus allowing it to start processing as soon as possible.\n+\n+For this reason, libcamera provides the `metadataAvailable` signal on each `Camera`\n+object. This signal is dispatched whenever new metadata items become available for a\n+queued request. This mechanism is completely optional, only interested applications\n+need to subscribe, others are free to ignore it completely. `Request::metadata()`\n+will contain the sum of all early metadata items at request completion.\n+\n+Thread safety\n+^^^^^^^^^^^^^\n+\n+The application and libcamera are operating in separate threads. This means that while\n+a request is being processed, accessing the request's metadata list brings up the\n+question of concurrent access. Previously, the metadata list was implemented using a\n+`ControlList`, which uses `std::unordered_map` as its backing storage. That type\n+does not provide strong thread-safety guarantees. As a consequence, accessing the\n+metadata list was only allowed in certain contexts:\n+\n+ (1) before request submission\n+ (2) after request completion\n+ (3) in libcamera signal handler\n+\n+Contexts (1) and (2) are most likely assumed (and expected) by users of libcamera, and\n+they are not too interesting because they do not overlap with request processing, where a\n+pipeline handler could be modifying the list in parallel.\n+\n+Context (3) is merely an implementation detail of the libcamera signal-slot event handling\n+mechanism (libcamera users cannot use the asynchronous event delivery mechanism).\n+\n+Naturally, in a context where accessing the metadata list is safe, querying the metadata\n+items of interest and storing them in an application specific manner is a good and safe\n+approach. However, in (3) keeping the libcamera internal thread blocked for too long\n+will have detrimental effects, so processing must be kept to a minimum.\n+\n+As a consequence, if an application is unable to query the metadata items of interest\n+in a safe context (potentially because it does not know) but wants delegate work (that\n+needs access to metadata) to separate worker threads, it is forced to create a copy of\n+the entire metadata list, which is hardly optimal. The introduction of early metadata\n+completion only makes it worse (due to potentially multiple completion events).\n+\n+Requirements\n+------------\n+\n+We wish to provide a simple, easy-to-use, and hard-to-misuse interface for\n+applications. Notably, applications should be able to perform early metadata\n+processing safely wrt. any concurrent modifications libcamera might perform.\n+\n+Secondly, efficiency should be considered: copies, locks, reference counting,\n+etc. should be avoided if possible.\n+\n+Preferably, it should be possible to refer to a contiguous (in insertion order)\n+subset of values reasonably efficiently so that applications can be notified\n+about the just inserted metadata items without creating separate data structures\n+(i.e. a set of numeric ids).\n+\n+Options\n+-------\n+\n+Several options have been considered for making use of already existing mechanisms,\n+to avoid the introduction of a new type. These all fell short of some or all of the\n+requirements proposed above. Some ideas that use the existing `ControlList` type are\n+discussed below.\n+\n+Send a copy\n+^^^^^^^^^^^\n+\n+Passing a separate `ControlList` containing the just completed metadata, and\n+disallowing access to the request's metadata list until completion works fine, and\n+avoids the synchronization issues on the libcamera side. Nonetheless, it has two\n+significant drawbacks:\n+\n+1. It moves the issue of synchronization from libcamera to the application: the\n+ application still has to access its own data in a thread-safe manner and/or\n+ transfer the partial metadata list to its intended thread of execution.\n+2. The metadata list may contain potentially large data, copying which may be\n+ a non-negligible performance cost (especially if it does not even end up needed).\n+\n+Keep using `ControlList`\n+^^^^^^^^^^^^^^^^^^^^^^^^\n+\n+Using a `ControlList` (and hence `std::unordered_map`) with early metadata completion\n+would be possible, but it would place a number of potentially non-intuitive and\n+easy to violate restrictions on applications, making it harder to use safely.\n+Specifically, the application would have to retrieve a pointer to the `ControlValue`\n+object in the metadata `ControlList`, and then access it only through that pointer.\n+(This is guaranteed to work since `std::unordered_map` provides pointer stability\n+wrt. insertions.)\n+\n+However, it wouldn't be able to do lookups on the metadata list outside the event\n+handler, thus a pointer or iterator to every potentially accessed metadata item\n+has to be retrieved and saved in the event handler. Additionally, the usual way\n+of retrieving metadata using the pre-defined `Control<T>` objects would no longer\n+be possible, losing type-safety. (Although the `ControlValue` type could be extended\n+to support that.)\n+\n+Design\n+------\n+\n+A separate data structure is introduced to contain the metadata items pertaining\n+to a given request. It is referred to as \"metadata list\" from now on.\n+\n+A metadata list is backed by a pre-allocated (at construction time) contiguous\n+block of memory sized appropriately to contain all possible metadata items. This\n+means that the number and size of metadata items that a camera can report must\n+be known in advance. The newly introduced `MetadataListPlan` type is used for\n+that purpose. At the time of writing this does not appear to be a significant\n+limitation since most metadata has a fixed size, and each pipeline handler (and\n+IPA) has a fixed set of metadata that it can report. There are, however, metadata\n+items that have a variably-sized array type. In those cases an upper bound on the\n+number of elements must be provided.\n+\n+`MetadataListPlan`\n+^^^^^^^^^^^^^^^^^^\n+\n+A `MetadataListPlan` collects the set of possible metadata items. It maps the\n+numeric id of the control to a collection of static information (size, etc.). This\n+is most importantly used to calculate the size required to store all possible\n+metadata item.\n+\n+Each camera has its own `MetadataListPlan` object similarly to its `ControlInfoMap`.\n+It is used to create requests for the camera with an appropriately sized `MetadataList`.\n+Pipeline handlers should fill it during camera initialization or configuration,\n+and they are allowed to modify it before and during camera configuration.\n+\n+`MetadataList`\n+^^^^^^^^^^^^^^\n+\n+The current metadata list implementation is a single-writer multiple-readers\n+thread-safe data structure that provides lock-free lookup and access for any number\n+of threads, while allowing a single thread at a time to add metadata items.\n+\n+The implemented metadata list has two main parts. The first part essentially\n+contains a copy of the `MetadataListPlan` used to construct the `MetadataList`. In\n+addition to the static information about the metadata item, it contains dynamic\n+information such as whether the metadata item has been added to the list or not.\n+These entries are sorted by the numeric identifier to facilitate faster lookup.\n+\n+The second part of a metadata list is a completely self-contained serialized list\n+of metadata items. The number of bytes used for actually storing metadata items\n+in this second part will be referred to as the \"fill level\" from now on. The\n+self-contained nature of the second part leads to a certain level of data duplication\n+between the two parts, however, the end goal is to have a serialized version of\n+`ControlList` with the same serialized format. This would allow a `MetadataList`\n+to be \"trivially\" reinterpreted as a control list at any point of its lifetime,\n+simplifying the interoperability between the two.\n+TODO: do we really want that?\n+\n+A metadata list, at construction time, calculates the number of bytes necessary to\n+store all possible metadata items according to the supplied `MetadataListPlan`.\n+Storage, for all possible metadata items and the necessary auxiliary structures,\n+is then allocated. This allocation remains fixed for the entire lifetime of a\n+`MetadataList`, which is crucial to satisfy the earlier requirements.\n+\n+Each metadata item can only be added to a metadata list once. This constraint\n+does not pose a significant limitation, instead, it simplifies the interface and\n+implementation; it is essentially an append-only list.\n+\n+Serialization\n+'''''''''''''\n+\n+The actual values are encoded in the \"second part\" of the metadata list in a fairly\n+simple fashion. Each control value is encoded as header + data bytes + padding.\n+Each value has a header, which contains information such as the size, alignment,\n+type, etc. of the value. The data bytes are aligned to the alignment specified\n+in the header, and padding may be inserted after the last data byte to guarantee\n+proper alignment for the next header. Padding is present even after the last entry.\n+\n+The minimum amount of state needed to describe such a serialized list of values is\n+merely the number of bytes used. This can reasonably be limited to 4 GiB, meaning\n+that a 32-bit unsigned integer is sufficient to store the fill level. This makes\n+it possible to easily update the state in a wait-free fashion.\n+\n+Lookup\n+''''''\n+\n+Lookup in a metadata list is done using the metadata entries in the \"first part\".\n+These entries are sorted by their numeric identifiers, hence binary search is\n+used to find the appropriate entry. Then, it is checked whether the given control\n+id has already been added, and if it has, then its data can be returned in a\n+`ControlValueView` object.\n+\n+Insertion\n+'''''''''\n+\n+Similarly to lookup, insertion also starts with binary searching the entry\n+corresponding to the given numeric identifier. If an entry is present for the\n+given id and no value has already been stored with that id, then insertion can\n+proceed. The value is appended to the serialized list of control values according\n+to the format described earlier. Then the fill level is atomically incremented,\n+and the entry is marked as set. After that the new value is available for readers\n+to consume.\n+\n+Having a single writer is an essential requirement to be able to carry out insertion\n+in a reasonably efficient, and thread-safe manner.\n+\n+Iteration\n+'''''''''\n+\n+Iteration of a `MetadataList` is carried out only using the serialized list of\n+controls in the \"second part\" of the data structure. An iterator can be implemented\n+as a single pointer, pointing to the header of the current entry. The begin iterator\n+simply points to location of the header of the first value. The end iterator is\n+simply the end of the serialized list of values, which can be calculated from the\n+begin iterator and the fill level of the serialized list.\n+\n+The above iterator can model a `C++ forward iterator`_, that is, only increments\n+of 1 are possible in constant time, and going backwards is not possible. Advancing\n+to the next value can be simply implemented by reading the size and alignment from\n+the header, and adjusting the iterator's pointer by the necessary amount.\n+\n+TODO: is a forward iterator enough? is a bidirectional iterator needed?\n+\n+.. _C++ forward iterator: https://en.cppreference.com/w/cpp/iterator/forward_iterator.html\n+\n+Clearing\n+''''''''\n+\n+Removing a single value is not supported, but clearing the entire metadata list\n+is. This should only be done when there are no readers, otherwise readers might\n+run into data races if they keep reading the metadata when new entries are being\n+added after clearing it.\n+\n+Clearing is implemented by resetting each metadata entry in the \"first part\", as\n+well as resetting the stored fill level of the serialized buffer to 0.\n+\n+Partial view\n+''''''''''''\n+\n+When multiple metadata items are completed early, it is important to provide a way\n+for the application to know exactly which metadata items have just been added. The\n+serialized values in the data structure are laid out sequentially. This makes it\n+possible for a simple byte range to denote a range of metadata items. Hence the\n+completed metadata items can be transferred to the application as a simple byte\n+range, without needing extra data structures (such as a set of numeric ids).\n+\n+The `MetadataList::Checkpoint` type is used to store that state of the serialized\n+list (number of bytes and number of items) at a given point in time. From such a\n+checkpoint object a `MetadataList::Diff` object can be constructed, which represents\n+all values added since the checkpoint. This *diff* object is reasonably small,\n+and trivially copyable, making it easy to provide to the application. It has much\n+of the same features as a `MetadataList`, e.g. it can be iterated and one can do\n+lookups. Naturally, both iteration and lookups only consider the values added after\n+the checkpoint and before the creation of the `MetadataList::Diff` object.\ndiff --git a/Documentation/index.rst b/Documentation/index.rst\nindex 251112fbd..60cb77702 100644\n--- a/Documentation/index.rst\n+++ b/Documentation/index.rst\n@@ -24,6 +24,7 @@\n Tracing guide <guides/tracing>\n \n Design document: AE <design/ae>\n+ Design document: Metadata list <design/metadata-list>\n \n .. toctree::\n :hidden:\ndiff --git a/Documentation/meson.build b/Documentation/meson.build\nindex 3afdcc1a8..1721f9af1 100644\n--- a/Documentation/meson.build\n+++ b/Documentation/meson.build\n@@ -128,6 +128,7 @@ if sphinx.found()\n 'conf.py',\n 'contributing.rst',\n 'design/ae.rst',\n+ 'design/metadata-list.rst',\n 'documentation-contents.rst',\n 'environment_variables.rst',\n 'feature_requirements.rst',\n", "prefixes": [ "RFC", "v2", "08/22" ] }