{"id":23489,"url":"https://patchwork.libcamera.org/api/1.1/patches/23489/?format=json","web_url":"https://patchwork.libcamera.org/patch/23489/","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":"<20250606164156.1442682-9-barnabas.pocze@ideasonboard.com>","date":"2025-06-06T16:41:41","name":"[RFC,v1,08/23] Documentation: design: Document `MetadataList`","commit_ref":null,"pull_url":null,"state":"superseded","archived":false,"hash":"63d7fdfc046943e2633cd7d0fa1d6acc999eaed2","submitter":{"id":216,"url":"https://patchwork.libcamera.org/api/1.1/people/216/?format=json","name":"Barnabás Pőcze","email":"barnabas.pocze@ideasonboard.com"},"delegate":null,"mbox":"https://patchwork.libcamera.org/patch/23489/mbox/","series":[{"id":5210,"url":"https://patchwork.libcamera.org/api/1.1/series/5210/?format=json","web_url":"https://patchwork.libcamera.org/project/libcamera/list/?series=5210","date":"2025-06-06T16:41:33","name":"libcamera: Add `MetadataList`","version":1,"mbox":"https://patchwork.libcamera.org/series/5210/mbox/"}],"comments":"https://patchwork.libcamera.org/api/patches/23489/comments/","check":"pending","checks":"https://patchwork.libcamera.org/api/patches/23489/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 E53F2C3327\n\tfor ;\n\tFri, 6 Jun 2025 16:42:39 +0000 (UTC)","from lancelot.ideasonboard.com (localhost [IPv6:::1])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTP id 5A27D68DC3;\n\tFri, 6 Jun 2025 18:42:39 +0200 (CEST)","from perceval.ideasonboard.com (perceval.ideasonboard.com\n\t[213.167.242.64])\n\tby lancelot.ideasonboard.com (Postfix) with ESMTPS id 4B81768DBF\n\tfor ;\n\tFri, 6 Jun 2025 18:42:17 +0200 (CEST)","from pb-laptop.local (185.182.215.79.nat.pool.zt.hu\n\t[185.182.215.79])\n\tby perceval.ideasonboard.com (Postfix) with ESMTPSA id AD8B98DB\n\tfor ;\n\tFri, 6 Jun 2025 18:42:12 +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=\"gWhzA+lJ\"; dkim-atps=neutral","DKIM-Signature":"v=1; a=rsa-sha256; c=relaxed/simple; d=ideasonboard.com;\n\ts=mail; t=1749228132;\n\tbh=1kY2O66QbkDnWvTOQisEpM4nUeC4GAZmxwqjPJ7dfHk=;\n\th=From:To:Subject:Date:In-Reply-To:References:From;\n\tb=gWhzA+lJgExJjMc86OEg5mLvWthCuoTlEENMPwkfG7mYtZuUkZWbhHbYppAlGklgr\n\tbyjqbma35QyNwdeaiiV4y2GQoat/9sM3HMXUvIcbFndOnbXQuiVIDuA4xOjuedk3NT\n\t/ggiUbxe2zl9WvghUwAQSaCr4Yc+h1jqq8PQAqEA=","From":"=?utf-8?q?Barnab=C3=A1s_P=C5=91cze?= ","To":"libcamera-devel@lists.libcamera.org","Subject":"[RFC PATCH v1 08/23] Documentation: design: Document `MetadataList`","Date":"Fri, 6 Jun 2025 18:41:41 +0200","Message-ID":"<20250606164156.1442682-9-barnabas.pocze@ideasonboard.com>","X-Mailer":"git-send-email 2.49.0","In-Reply-To":"<20250606164156.1442682-1-barnabas.pocze@ideasonboard.com>","References":"<20250606164156.1442682-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":"","List-Unsubscribe":",\n\t","List-Archive":"","List-Post":"","List-Help":"","List-Subscribe":",\n\t","Errors-To":"libcamera-devel-bounces@lists.libcamera.org","Sender":"\"libcamera-devel\" "},"content":"Add a document describing the problem, the choices, and the design of\nthe separate metadata list data structure.\n\nSigned-off-by: Barnabás Pőcze \n---\n Documentation/design/metadata-list.rst | 234 +++++++++++++++++++++++++\n Documentation/index.rst | 1 +\n Documentation/meson.build | 1 +\n 3 files changed, 236 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..a42f94bdf\n--- /dev/null\n+++ b/Documentation/design/metadata-list.rst\n@@ -0,0 +1,234 @@\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+\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 one the image, etc. using certain metadata items. For such an\n+application it is likely best if the final value of each metadata item is reported\n+as 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` object.\n+This signal is dispatched whenever new metadata items become available for a queued request.\n+This mechanism is completely optional, only interested applications need to subscribe,\n+others are free to ignore it completely. `Request::metadata()` will contain the sum of\n+all early metadata items at request completion.\n+\n+Thread safety\n+^^^^^^^^^^^^^\n+\n+At the moment, event handlers of the application are always dispatched in a private\n+thread of libcamera. This requires that applications process the various events in a\n+thread-safe manner wrt. themselves. The burden of correct synchronization falls\n+upon the applications.\n+\n+Previously, a `ControlList` was used to store the metadata pertaining to a particular\n+request. A `ControlList` is implemented using an `std::unordered_map`, meaning that\n+its thread-safety is limited. This hints at a need for a separate data structure\n+or at least some kind of thread-safe wrapper.\n+\n+\n+Requirements\n+------------\n+\n+We wish to provide a simple, easy-to-use, and hard-to-misuse interface for applications.\n+Notably, applications should be able to delegate early metadata processing to their\n+own separate threads safely wrt. the metadata list. Consider the following scenario:\n+the pipeline handler send early metadata items to the application, the application\n+delegates it to a separate thread. After that, the private libcamera thread is no\n+longer blocked, thus the pipeline handler can continue working on the request: e.g.\n+add more metadata items. Simultaneously, the application might be reading the metadata\n+items on a separate thread. This situation should be safe and work correctly, ideally\n+with any number of threads reading the completed metadata items. Until the request\n+is destroyed or reused, whichever happens first.\n+\n+Secondarily, efficiency should be considered: copies, locks, reference counting, etc.\n+should be avoided if possible.\n+\n+Preferably, it should be possible to refer to a contiguous (in insertion order) subset\n+of values reasonably efficiently (i.e. avoiding having to store a separate list of\n+numeric identifiers, etc.).\n+\n+\n+Options\n+-------\n+\n+Keep using `ControlList`\n+^^^^^^^^^^^^^^^^^^^^^^^^\n+\n+Using a `ControlList` (and hence `std::unordered_map`) with early metadata completion would\n+be possible, but it would place a number of potentially non-intuitive and easy to violate\n+restrictions on applications, making it harder to use safely. Specifically, the application\n+would have to retrieve a pointer to the `ControlValue` object in the metadata `ControlList`,\n+and then access it only through that pointer. It wouldn't be able to do lookups on the metadata\n+list outside the event handler. As a consequence, the usual way of retrieving metadata using\n+the pre-defined `Control` objects would no longer be possible, losing type-safety.\n+\n+Send a copy\n+^^^^^^^^^^^\n+\n+Passing a separate `ControlList` containing the just completed metadata, and disallowing access\n+to the request's metadata list until completion works fine, and avoids the synchronization issues\n+on the libcamera side. Nonetheless, it has two significant drawbacks:\n+\n+1. It moves the issue of synchronization from libcamera to the application: the application still has\n+ to access its own data in a thread-safe manner and/or transfer the partial metadata list to its\n+ *main* thread of execution.\n+2. Early metadata can be reported multiple times for each request, thus making copies can have negative\n+ performance implications.\n+\n+\n+Design\n+------\n+\n+A separate data structure is introduced to contain the metadata items pertaining to a given request.\n+It is referred to as \"metadata list\" from now on.\n+\n+The current design of the metadata list places a number of restrictions on request metadata.\n+A metadata list is backed by a pre-allocated (at construction time) contiguous block of\n+memory sized appropriately to contain all possible metadata items. This means that the\n+number and size of metadata items that a camera can report must be known in advance. The\n+newly introduced `MetadataListPlan` type is used for that purpose. At the time of writing\n+this does not appear to be a significant limitation since most metadata has a fixed size,\n+and each pipeline handler (and IPA) has a fixed set of metadata that it can report. There\n+are, however, metadata items that have a variably-sized array type. In those cases an upper\n+bound on the number of elements must be provided.\n+\n+`MetadataListPlan`\n+^^^^^^^^^^^^^^^^^^\n+\n+A `MetadataListPlan` collects the set of possible metadata items. It maps the numeric id\n+of the control to a collection of static information (size, etc.). This is most importantly\n+used to calculate the size required to store all possible metadata item.\n+\n+Each camera has its own `MetadataListPlan` object similarly to its `ControlInfoMap`. It is\n+used to create requests for the the camera with an appropriately sized `MetadataList`.\n+Pipeline handlers should fill it during camera initialization or configuration, and they\n+are allowed to modify it as long as they camera is not configured and during configuration.\n+\n+`MetadataList`\n+^^^^^^^^^^^^^^\n+\n+The current metadata list implementation is a single-writer multiple-readers thread-safe\n+data structure that provides lock-free lookup and access for any number of threads, while\n+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 contains\n+a copy of the `MetadataListPlan` used to construct the `MetadataList`. In addition to\n+the static information about the metadata item, it contains dynamic information such\n+as whether the metadata item has been added to the list or not.\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 in\n+this second part will be referred to as the \"fill level\" from now on. The self-contained\n+nature of the second part leads to a certain level of data duplication between the two\n+parts, however, the end goal is to have a serialized version of `ControlList` with the\n+same serialized format. This would allow a `MetadataList` to be \"trivially\" reinterpreted\n+as a control list at any point of its lifetime, 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 store\n+all possible metadata items according to the supplied `MetadataListPlan`. Storage, for\n+all possible metadata items and the necessary auxiliary structures is then allocated.\n+This allocation remains fixed for the entire lifetime of a `MetadataList`, which is\n+crucial to satisfy the earlier requirements.\n+\n+Each metadata item can only be added to a metadata list once. This constraint does not pose\n+a significant limitation, instead, it simplifies the interface and implementation; it is\n+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. Each\n+value has a header, which contains information such as the size, alignment, type, etc.\n+of the value. The data bytes are aligned to the alignment specified in the header,\n+and padding may be inserted after the last data byte to guarantee proper alignment\n+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, which can reasonably be limited to 4 GiB, meaning\n+that a 32-bit unsigned integer is sufficient to store the fill level. This makes it\n+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 used to\n+find the appropriate entry. Then, it is checked whether the given control id has already\n+been added, and if it has, then its data can be returned in a `ControlValueView` object.\n+\n+Insertion\n+'''''''''\n+\n+Similarly to lookup, insertion also starts with binary searching the entry belonging\n+to the given numeric identifier. If an entry is present for the given id and no value\n+has already been stored with that id, then insertion can proceed. The value is appended\n+to the serialized list of control values according to the format described earlier.\n+Then the fill level is atomically incremented, and the entry is marked as set. After\n+that the new value is available for readers to consume.\n+\n+Having a single writer is an essential requirement to be able to carry out insertion in\n+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 controls\n+in the \"second part\" of the data structure. An iterator can be implemented as a single\n+pointer, pointing to the header of the current entry. The begin iterator simply points\n+to location of the header of the first value. The end iterator is simply the end of the\n+serialized list of values, which can be calculated from the begin iterator and the fill\n+level of the serialized list.\n+\n+The above iterator can model a `C++ forward iterator`_, that is, only increments of 1 are\n+possible in constant time, and going backwards is not possible. Advancing to the next value\n+can be simply implemented by reading the size and alignment from the header, and adjusting\n+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 is.\n+This should only be done when there are no readers, otherwise readers might run into\n+data races if they keep reading the metadata when new entries are being added after\n+clearing it.\n+\n+Clearing is implemented by resetting each metadata entry in the \"first part\", as well\n+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 encoded such that a simple byte range\n+is capable of representing any number of items that have been added in succession.\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, and\n+trivially copyable, making it easy to provide to the application. It has much of\n+the same features as a `MetadataList`, e.g. it can be iterated and one can do lookups.\n+Naturally, both iteration and lookups only consider the values added after the checkpoint\n+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 \n \n Design document: AE \n+ Design document: Metadata list \n \n .. toctree::\n :hidden:\ndiff --git a/Documentation/meson.build b/Documentation/meson.build\nindex 0fc5909d0..79e687953 100644\n--- a/Documentation/meson.build\n+++ b/Documentation/meson.build\n@@ -127,6 +127,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","v1","08/23"]}