[RFC,v3,07/22] libcamera: Add `MetadataList`

24910 diff mbox series

diff --git a/include/libcamera/meson.build b/include/libcamera/meson.build
index 30ea76f947..410b548dde 100644
--- a/include/libcamera/meson.build
+++ b/include/libcamera/meson.build
@@ -12,6 +12,8 @@  libcamera_public_headers = files([
     'framebuffer_allocator.h',
     'geometry.h',
     'logging.h',
+    'metadata_list.h',
+    'metadata_list_plan.h',
     'orientation.h',
     'pixel_format.h',
     'request.h',
diff --git a/include/libcamera/metadata_list.h b/include/libcamera/metadata_list.h
new file mode 100644
index 0000000000..9366dcbc3a
--- /dev/null
+++ b/include/libcamera/metadata_list.h
@@ -0,0 +1,529 @@ 
+/* SPDX-License-Identifier: LGPL-2.1-or-later */
+/*
+ * Copyright (C) 2025, Ideas On Board Oy
+ *
+ * Metadata list
+ */
+
+#pragma once
+
+#include <algorithm>
+#include <atomic>
+#include <cassert>
+#include <cstdint>
+#include <optional>
+#include <type_traits>
+#include <utility>
+
+#include <libcamera/base/internal/align.h>
+#include <libcamera/base/internal/cxx20.h>
+#include <libcamera/base/span.h>
+
+#include <libcamera/controls.h>
+
+namespace libcamera {
+
+class MetadataListPlan;
+
+class MetadataList
+{
+private:
+	/**
+	 * \brief The entry corresponding to a potential value in the list
+	 */
+	struct Entry {
+		static constexpr uint32_t kInvalidOffset = -1;
+
+		/**
+		 * \brief Numeric identifier in the list
+		 */
+		const uint32_t tag;
+
+		/**
+		 * \brief Number of bytes available for the value
+		 */
+		const uint32_t capacity;
+
+		/**
+		 * \brief Alignment of the value
+		 */
+		const uint32_t alignment;
+
+		const ControlType type;
+		const bool isArray;
+
+		/**
+		 * \brief Offset of the ValueHeader of the value pertaining to this entry
+		 *
+		 * Offset from the beginning of the allocation, and
+		 * and _not_ relative to `contentOffset_`.
+		 */
+		std::atomic_uint32_t headerOffset = kInvalidOffset;
+
+		[[nodiscard]]
+		std::optional<uint32_t> hasValue() const
+		{
+			auto offset = headerOffset.load(std::memory_order_relaxed);
+			if (offset == kInvalidOffset)
+				return {};
+
+			return offset;
+		}
+
+		[[nodiscard]]
+		std::optional<uint32_t> acquireData() const
+		{
+			auto offset = hasValue();
+			if (offset) {
+				/* sync with release-store on `headerOffset` in `MetadataList::set()` */
+				std::atomic_thread_fence(std::memory_order_acquire);
+			}
+
+			return offset;
+		}
+	};
+
+	/**
+	 * \brief The header describing a value in the list
+	 */
+	struct ValueHeader {
+		/**
+		 * \brief Numeric identifier of the value in the list
+		 */
+		uint32_t tag;
+
+		/**
+		 * \brief Number of bytes used by the value
+		 *
+		 * This can be calculated using type and numElements, it is stored
+		 * here to facilitate easier iteration in the buffer.
+		 */
+		uint32_t size;
+
+		/**
+		 * \brief Alignment of the value
+		 */
+		uint32_t alignment;
+
+		/**
+		 * \brief Type of the value
+		 */
+		ControlType type;
+
+		/**
+		 * \brief Whether the value is an array
+		 */
+		bool isArray;
+
+		/**
+		 * \brief Number of elements in the value
+		 */
+		uint32_t numElements;
+	};
+
+	struct State {
+		/**
+		 * \brief Number of items present in the list
+		 */
+		uint32_t count;
+
+		/**
+		 * \brief Number of bytes used in the buffer
+		 */
+		uint32_t fill;
+	};
+
+public:
+	explicit MetadataList(const MetadataListPlan &plan);
+
+	MetadataList(const MetadataList &) = delete;
+	MetadataList(MetadataList &&) = delete;
+
+	MetadataList &operator=(const MetadataList &) = delete;
+	MetadataList &operator=(MetadataList &&) = delete;
+
+	~MetadataList();
+
+	// \todo want these?
+	[[nodiscard]] std::size_t size() const { return state_.load(std::memory_order_relaxed).count; }
+	[[nodiscard]] bool empty() const { return state_.load(std::memory_order_relaxed).fill == 0; }
+
+	enum class SetError {
+		UnknownTag = 1,
+		AlreadySet,
+		SizeMismatch,
+		TypeMismatch,
+	};
+
+	[[nodiscard]]
+	SetError set(uint32_t tag, ControlValueView v)
+	{
+		auto *e = find(tag);
+		if (!e)
+			return SetError::UnknownTag;
+
+		return set(*e, v);
+	}
+
+	template<typename T>
+	[[nodiscard]]
+	SetError set(const Control<T> &ctrl, const internal::cxx20::type_identity_t<T> &value)
+	{
+		using TypeInfo = libcamera::details::control_type<T>;
+
+		if constexpr (TypeInfo::size > 0) {
+			static_assert(std::is_trivially_copyable_v<typename T::value_type>);
+
+			return set(ctrl.id(), {
+				TypeInfo::value,
+				true,
+				value.size(),
+				reinterpret_cast<const std::byte *>(value.data()),
+			});
+		} else {
+			static_assert(std::is_trivially_copyable_v<T>);
+
+			return set(ctrl.id(), {
+				TypeInfo::value,
+				false,
+				1,
+				reinterpret_cast<const std::byte *>(&value),
+			});
+		}
+	}
+
+	template<typename T>
+	[[nodiscard]]
+	std::optional<T> get(const Control<T> &ctrl) const
+	{
+		ControlValueView v = get(ctrl.id());
+		if (!v)
+			return {};
+
+		return v.get<T>();
+	}
+
+	// \todo operator ControlListView() const ?
+	// \todo explicit operator ControlList() const ?
+
+	[[nodiscard]]
+	ControlValueView get(uint32_t tag) const
+	{
+		const auto *e = find(tag);
+		if (!e)
+			return {};
+
+		return dataOf(*e);
+	}
+
+	void clear();
+
+	class iterator
+	{
+	public:
+		using difference_type = std::ptrdiff_t;
+		using value_type = std::pair<uint32_t, ControlValueView>;
+		using pointer = void;
+		using reference = value_type;
+		using iterator_category = std::forward_iterator_tag;
+
+		iterator() = default;
+
+		iterator& operator++()
+		{
+			const auto &h = header();
+
+			p_ += sizeof(h);
+			p_ = internal::align::up(p_, h.alignment);
+			p_ += h.size;
+			p_ = internal::align::up(p_, alignof(decltype(h)));
+
+			return *this;
+		}
+
+		iterator operator++(int)
+		{
+			auto copy = *this;
+			++*this;
+			return copy;
+		}
+
+		[[nodiscard]]
+		reference operator*() const
+		{
+			const auto &h = header();
+			const auto *data = internal::align::up(p_ + sizeof(h), h.alignment);
+
+			return { h.tag, { h.type, h.isArray, h.numElements, data } };
+		}
+
+		[[nodiscard]]
+		bool operator==(const iterator &other) const
+		{
+			return p_ == other.p_;
+		}
+
+		[[nodiscard]]
+		bool operator!=(const iterator &other) const
+		{
+			return !(*this == other);
+		}
+
+	private:
+		iterator(const std::byte *p)
+			: p_(p)
+		{
+		}
+
+		[[nodiscard]]
+		const ValueHeader &header() const
+		{
+			return *reinterpret_cast<const ValueHeader *>(p_);
+		}
+
+		friend MetadataList;
+
+		const std::byte *p_ = nullptr;
+	};
+
+	[[nodiscard]]
+	iterator begin() const
+	{
+		return { p_ + contentOffset_ };
+	}
+
+	[[nodiscard]]
+	iterator end() const
+	{
+		return { p_ + contentOffset_ + state_.load(std::memory_order_acquire).fill };
+	}
+
+	class Diff
+	{
+	public:
+		// \todo want these?
+		[[nodiscard]] explicit operator bool() const { return !empty(); }
+		[[nodiscard]] bool empty() const { return start_ == stop_; }
+		[[nodiscard]] std::size_t size() const { return changed_; }
+		[[nodiscard]] const MetadataList &list() const { return *list_; }
+
+		[[nodiscard]]
+		ControlValueView get(uint32_t tag) const
+		{
+			const auto *e = list_->find(tag);
+			if (!e)
+				return {};
+
+			auto o = e->acquireData();
+			if (!o)
+				return {};
+
+			if (!(start_ <= *o && *o < stop_))
+				return {};
+
+			return list_->dataOf(*o);
+		}
+
+		template<typename T>
+		[[nodiscard]]
+		std::optional<T> get(const Control<T> &ctrl) const
+		{
+			ControlValueView v = get(ctrl.id());
+			if (!v)
+				return {};
+
+			return v.get<T>();
+		}
+
+		[[nodiscard]]
+		iterator begin() const
+		{
+			return { list_->p_ + start_ };
+		}
+
+		[[nodiscard]]
+		iterator end() const
+		{
+			return { list_->p_ + stop_ };
+		}
+
+	private:
+		Diff(const MetadataList &list, std::size_t changed, std::size_t oldFill, std::size_t newFill)
+			: list_(&list),
+			  changed_(changed),
+			  start_(list.contentOffset_ + oldFill),
+			  stop_(list.contentOffset_ + newFill)
+		{
+		}
+
+		friend MetadataList;
+		friend struct Checkpoint;
+
+		/**
+		 * \brief Source lits of the checkpoint
+		 */
+		const MetadataList *list_ = nullptr;
+
+		/**
+		 * \brief Number of items contained in the diff
+		 */
+		std::size_t changed_;
+
+		/**
+		 * \brief Offset of the ValueHeader of the first value in the diff
+		 */
+		std::size_t start_;
+
+		/**
+		 * \brief Offset of the "past-the-end" ValueHeader of the diff
+		 */
+		std::size_t stop_;
+	};
+
+	[[nodiscard]] std::optional<Diff> merge(const ControlList &other);
+
+	class Checkpoint
+	{
+	public:
+		[[nodiscard]]
+		Diff diffSince() const
+		{
+			/* sync with release-store on `state_` in `set()` */
+			const auto curr = list_->state_.load(std::memory_order_acquire);
+
+			assert(state_.count <= curr.count);
+			assert(state_.fill <= curr.fill);
+
+			return {
+				*list_,
+				curr.count - state_.count,
+				state_.fill,
+				curr.fill,
+			};
+		}
+
+	private:
+		Checkpoint(const MetadataList &list)
+			: list_(&list),
+			  state_(list.state_.load(std::memory_order_relaxed))
+		{
+		}
+
+		friend MetadataList;
+
+		/**
+		 * \brief Source list of the checkpoint
+		 */
+		const MetadataList *list_ = nullptr;
+
+		/**
+		 * \brief State of the list when the checkpoint was created
+		 */
+		State state_ = {};
+	};
+
+	[[nodiscard]]
+	Checkpoint checkpoint() const
+	{
+		return { *this };
+	}
+
+private:
+	[[nodiscard]]
+	static constexpr std::size_t entriesOffset()
+	{
+		return 0;
+	}
+
+	[[nodiscard]]
+	static constexpr std::size_t contentOffset(std::size_t entries)
+	{
+		return internal::align::up(entriesOffset() + entries * sizeof(Entry), alignof(ValueHeader));
+	}
+
+	[[nodiscard]]
+	Span<Entry> entries() const
+	{
+		return { reinterpret_cast<Entry *>(p_ + entriesOffset()), capacity_ };
+	}
+
+	[[nodiscard]]
+	Entry *find(uint32_t tag) const
+	{
+		const auto entries = this->entries();
+		auto it = std::partition_point(entries.begin(), entries.end(), [&](const auto &e) {
+			return e.tag < tag;
+		});
+
+		if (it == entries.end() || it->tag != tag)
+			return nullptr;
+
+		return &*it;
+	}
+
+	[[nodiscard]]
+	ControlValueView dataOf(const Entry &e) const
+	{
+		const auto o = e.acquireData();
+		return o ? dataOf(*o) : ControlValueView{ };
+	}
+
+	[[nodiscard]]
+	ControlValueView dataOf(std::size_t headerOffset) const
+	{
+		assert(headerOffset <= alloc_ - sizeof(ValueHeader));
+		assert(internal::align::is(p_ + headerOffset, alignof(ValueHeader)));
+
+		const auto *vh = reinterpret_cast<const ValueHeader *>(p_ + headerOffset);
+		const auto *p = reinterpret_cast<const std::byte *>(vh) + sizeof(*vh);
+		std::size_t avail = p_ + alloc_ - p;
+
+		const auto *data = internal::align::up(vh->size, vh->alignment, p, &avail);
+		assert(data);
+
+		return { vh->type, vh->isArray, vh->numElements, data };
+	}
+
+	[[nodiscard]] SetError set(Entry &e, ControlValueView v);
+
+	[[nodiscard]]
+	std::pair<MetadataList::SetError, MetadataList::ValueHeader *>
+	set(const Entry &e, ControlValueView v, State &s);
+
+	/**
+	 * \brief Number of \ref Entry "entries"
+	 */
+	std::size_t capacity_ = 0;
+
+	/**
+	 * \brief Offset of the first ValueHeader
+	 */
+	std::size_t contentOffset_ = -1;
+
+	/**
+	 * \brief Pointer to the allocation
+	 */
+	std::byte *p_ = nullptr;
+
+	/**
+	 * \brief Size of the allocation in bytes
+	 */
+	std::size_t alloc_ = 0;
+
+	/**
+	 * \brief Current state of the list
+	 */
+	std::atomic<State> state_ = State{};
+
+	// \todo ControlIdMap in any way shape or form?
+
+	/*
+	 * If this is problematic on a 32-bit architecture, then
+	 * `count` can be stored in a separate atomic variable
+	 * but then `Diff::changed_` must be removed since the fill
+	 * level and item count cannot be retrieved atomically.
+	 */
+	static_assert(decltype(state_)::is_always_lock_free);
+};
+
+} /* namespace libcamera */
diff --git a/include/libcamera/metadata_list_plan.h b/include/libcamera/metadata_list_plan.h
new file mode 100644
index 0000000000..8f058e5c0d
--- /dev/null
+++ b/include/libcamera/metadata_list_plan.h
@@ -0,0 +1,110 @@ 
+/* SPDX-License-Identifier: LGPL-2.1-or-later */
+/*
+ * Copyright (C) 2025, Ideas On Board Oy
+ */
+
+#pragma once
+
+#include <cassert>
+#include <cstddef>
+#include <map>
+#include <stdint.h>
+#include <type_traits>
+
+#include <libcamera/base/internal/cxx20.h>
+
+#include <libcamera/controls.h>
+
+namespace libcamera {
+
+class MetadataListPlan
+{
+public:
+	struct Entry {
+		uint32_t size;
+		uint32_t alignment; // \todo is this necessary?
+		uint32_t numElements;
+		ControlType type;
+		bool isArray;
+	};
+
+	[[nodiscard]] bool empty() const { return items_.empty(); }
+	[[nodiscard]] std::size_t size() const { return items_.size(); }
+	[[nodiscard]] decltype(auto) begin() const { return items_.begin(); }
+	[[nodiscard]] decltype(auto) end() const { return items_.end(); }
+	void clear() { items_.clear(); }
+
+	template<
+		typename T,
+		std::enable_if_t<libcamera::details::control_type<T>::size != libcamera::dynamic_extent> * = nullptr
+	>
+	MetadataListPlan &set(const Control<T> &ctrl)
+	{
+		if constexpr (libcamera::details::control_type<T>::size > 0) {
+			static_assert(libcamera::details::control_type<T>::size != libcamera::dynamic_extent);
+
+			return set<typename T::value_type>(
+				ctrl.id(),
+				libcamera::details::control_type<T>::size,
+				true
+			);
+		} else {
+			return set<T>(ctrl.id(), 1, false);
+		}
+	}
+
+	template<
+		typename T,
+		std::enable_if_t<libcamera::details::control_type<T>::size == libcamera::dynamic_extent> * = nullptr
+	>
+	MetadataListPlan &set(const Control<T> &ctrl, std::size_t numElements)
+	{
+		return set<typename T::value_type>(ctrl.id(), numElements, true);
+	}
+
+	[[nodiscard]]
+	bool set(uint32_t tag,
+		 std::size_t size, std::size_t alignment,
+		 std::size_t numElements, ControlType type, bool isArray);
+
+	[[nodiscard]]
+	const Entry *get(uint32_t tag) const
+	{
+		auto it = items_.find(tag);
+		if (it == items_.end())
+			return nullptr;
+
+		return &it->second;
+	}
+
+	[[nodiscard]]
+	const Entry *get(const ControlId &cid) const
+	{
+		const auto *e = get(cid.id());
+		if (!e)
+			return nullptr;
+
+		if (e->type != cid.type() || e->isArray != cid.isArray())
+			return nullptr;
+
+		return e;
+	}
+
+private:
+	std::map<uint32_t, Entry> items_;
+
+	template<typename T>
+	MetadataListPlan &set(uint32_t tag, std::size_t numElements, bool isArray)
+	{
+		static_assert(std::is_trivially_copyable_v<T>);
+
+		[[maybe_unused]] bool ok = set(tag,
+					       sizeof(T), alignof(T),
+					       numElements, details::control_type<T>::value, isArray);
+		assert(ok);
+
+		return *this;
+	}
+};
+
+} /* namespace libcamera */
diff --git a/src/libcamera/meson.build b/src/libcamera/meson.build
index 5b9b86f211..7fd806ae78 100644
--- a/src/libcamera/meson.build
+++ b/src/libcamera/meson.build
@@ -9,6 +9,7 @@  libcamera_public_sources = files([
     'framebuffer.cpp',
     'framebuffer_allocator.cpp',
     'geometry.cpp',
+    'metadata_list.cpp',
     'orientation.cpp',
     'pixel_format.cpp',
     'request.cpp',
diff --git a/src/libcamera/metadata_list.cpp b/src/libcamera/metadata_list.cpp
new file mode 100644
index 0000000000..5a5114fc73
--- /dev/null
+++ b/src/libcamera/metadata_list.cpp
@@ -0,0 +1,594 @@ 
+/* SPDX-License-Identifier: LGPL-2.1-or-later */
+/*
+ * Copyright (C) 2025, Ideas On Board Oy
+ */
+
+#include <libcamera/metadata_list.h>
+
+#include <cstring>
+#include <limits>
+#include <new>
+
+#include <libcamera/base/internal/align.h>
+#include <libcamera/base/internal/cxx20.h>
+
+#include <libcamera/metadata_list_plan.h>
+
+#if __has_include(<sanitizer/asan_interface.h>)
+#if __SANITIZE_ADDRESS__ /* gcc */
+#include <sanitizer/asan_interface.h>
+#define HAS_ASAN 1
+#elif defined(__has_feature)
+#if __has_feature(address_sanitizer) /* clang */
+#include <sanitizer/asan_interface.h>
+#define HAS_ASAN 1
+#endif
+#endif
+#endif
+
+namespace libcamera {
+
+/**
+ * \class MetadataListPlan
+ * \brief Class to hold the possible set of metadata items for a MetadataList
+ */
+
+/**
+ * \class MetadataListPlan::Entry
+ * \brief Details of a metadata item
+ */
+
+/**
+ * \internal
+ * \var MetadataListPlan::Entry::size
+ * \brief Number of bytes in a single element
+ *
+ * \var MetadataListPlan::Entry::alignment
+ * \brief Required alignment of the elements
+ * \endinternal
+ *
+ * \var MetadataListPlan::Entry::numElements
+ * \brief Number of elements in the value
+ * \sa ControlValueView::numElements()
+ *
+ * \var MetadataListPlan::Entry::type
+ * \brief The type of the value
+ * \sa ControlValueView::type()
+ *
+ * \var MetadataListPlan::Entry::isArray
+ * \brief Whether or not the value is array-like
+ * \sa ControlValueView::isArray()
+ */
+
+/**
+ * \fn MetadataListPlan::begin() const
+ * \brief Retrieve the begin iterator
+ */
+
+/**
+ * \fn MetadataListPlan::end() const
+ * \brief Retrieve the end iterator
+ */
+
+/**
+ * \fn MetadataListPlan::size() const
+ * \brief Retrieve the number of entries
+ */
+
+/**
+ * \fn MetadataListPlan::empty() const
+ * \brief Check if empty
+ */
+
+/**
+ * \internal
+ * \fn MetadataListPlan::clear()
+ * \brief Remove all controls
+ */
+
+/**
+ * \internal
+ * \fn MetadataListPlan::set(const Control<T> &ctrl)
+ * \brief Add an entry for the given control to the metadata list plan
+ * \param[in] ctrl The control
+ */
+
+/**
+ * \internal
+ * \fn MetadataListPlan::set(const Control<T> &ctrl, std::size_t count)
+ * \brief Add an entry for the given dynamically-sized control to the metadata list plan
+ * \param[in] ctrl The control
+ * \param[in] count The maximum number of elements
+ *
+ * Add the dynamically-sized control \a ctrl to the metadata list plan with a maximum
+ * capacity of \a count elements.
+ */
+
+/**
+ * \internal
+ * \brief Add an entry to the metadata list plan
+ * \return \a true if the entry has been added, or \a false if the given parameters
+ *         would result in an invalid entry
+ *
+ * This functions adds an entry with essentially arbitrary parameters, without deriving
+ * them from a given ControlId instance. This is mainly used when deserializing.
+ */
+bool MetadataListPlan::set(uint32_t tag,
+			   std::size_t size, std::size_t alignment,
+			   std::size_t numElements, ControlType type, bool isArray)
+{
+	if (size == 0 || size > std::numeric_limits<uint32_t>::max())
+		return false;
+	if (alignment > std::numeric_limits<uint32_t>::max())
+		return false;
+	if (!internal::cxx20::has_single_bit(alignment))
+		return false;
+	if (numElements > std::numeric_limits<uint32_t>::max() / size)
+		return false;
+	if (!isArray && numElements != 1)
+		return false;
+
+	items_[tag] = {
+		.size = uint32_t(size),
+		.alignment = uint32_t(alignment),
+		.numElements = uint32_t(numElements),
+		.type = type,
+		.isArray = isArray,
+	};
+
+	return true;
+}
+
+/**
+ * \fn MetadataListPlan::get(uint32_t tag) const
+ * \brief Find the \ref Entry "entry" with the given identifier
+ */
+
+/**
+ * \fn MetadataListPlan::get(const ControlId &cid) const
+ * \brief Find the \ref Entry "entry" for the given ControlId
+ *
+ * The \ref Entry "entry" is only returned if ControlId::type() and ControlId::isArray()
+ * of \a cid matches Entry::type and Entry::isArray, respectively.
+ */
+
+/**
+ * \class MetadataList
+ * \brief Class to hold metadata items
+ *
+ * Similarly to a ControlList, a MetadataList provides a way for applications to
+ * query and enumerate the values of controls. However, a MetadataList allows
+ * thread-safe access to the data for applications, which is needed so that
+ * applications can process the metadata of in-flight \ref Request "requests"
+ * (for which purposes ControlList is not suitable).
+ *
+ * \internal
+ * A MetadataList is essentially an append-only list of values. Internally, it
+ * contains a single allocation that is divided into two parts:
+ *
+ *   * a list of entries sorted by their numeric identifiers
+ *     (each corresponding to an entry in the MetadataListPlan);
+ *   * a series of ValueHeader + data bytes that contain the actual data.
+ *
+ * When a value is added to the list, the corresponding Entry is updated, and the
+ * ValueHeader and the data bytes are appended to the end of the second part.
+ *
+ * The reason for the redundancy is the following: the first part enables quick
+ * lookups (binary search); the second part provides a self-contained flat buffer
+ * of all the data.
+ */
+
+/**
+ * \internal
+ * \brief Construct a metadata list according to \a plan
+ *
+ * Construct a metadata list according to the provided \a plan.
+ */
+MetadataList::MetadataList(const MetadataListPlan &plan)
+	: capacity_(plan.size()),
+	  contentOffset_(MetadataList::contentOffset(capacity_)),
+	  alloc_(contentOffset_)
+{
+	for (const auto &[tag, e] : plan) {
+		alloc_ += sizeof(ValueHeader);
+		alloc_ += e.alignment - 1; // XXX: this is the maximum
+		alloc_ += e.size * e.numElements;
+		alloc_ += alignof(ValueHeader) - 1; // XXX: this is the maximum
+	}
+
+	p_ = static_cast<std::byte *>(::operator new(alloc_));
+
+	auto *entries = reinterpret_cast<Entry *>(p_ + entriesOffset());
+	auto it = plan.begin();
+
+	for (std::size_t i = 0; i < capacity_; i++, ++it) {
+		const auto &[tag, e] = *it;
+
+		new (static_cast<void *>(&entries[i])) Entry{
+			.tag = tag,
+			.capacity = e.size * e.numElements,
+			.alignment = e.alignment,
+			.type = e.type,
+			.isArray = e.isArray,
+		};
+	}
+
+#if HAS_ASAN
+	::__sanitizer_annotate_contiguous_container(
+		p_ + contentOffset_, p_ + alloc_,
+		p_ + alloc_, p_ + contentOffset_
+	);
+#endif
+}
+
+MetadataList::~MetadataList()
+{
+	for (auto &e : entries())
+		std::destroy_at(&e);
+
+#if HAS_ASAN
+	/*
+	 * The documentation says the range apparently has to be
+	 * restored to its initial state before it is deallocated.
+	 */
+	::__sanitizer_annotate_contiguous_container(
+		p_ + contentOffset_, p_ + alloc_,
+		p_ + contentOffset_ + state_.load(std::memory_order_relaxed).fill, p_ + alloc_
+	);
+#endif
+
+	::operator delete(p_, alloc_);
+}
+
+/**
+ * \fn MetadataList::size() const
+ * \brief Retrieve the number of controls
+ * \context This function is \threadsafe.
+ * \note If the list is being modified, the return value may be out of
+ *       date by the time the function returns
+ */
+
+/**
+ * \fn MetadataList::empty() const
+ * \brief Check if empty
+ * \context This function is \threadsafe.
+ * \note If the list is being modified, the return value may be out of
+ *       date by the time the function returns
+ */
+
+/**
+ * \internal
+ * \brief Remove all items from the list
+ * \note This function in effect resets the list to its original state. As a consequence it invalidates - among others -
+ *       all iterators, Checkpoint, and Diff objects that are associated with the list. No readers must exist
+ *       when this function is called.
+ */
+void MetadataList::clear()
+{
+	for (auto &e : entries())
+		e.headerOffset.store(Entry::kInvalidOffset, std::memory_order_relaxed);
+
+	[[maybe_unused]] State s = state_.exchange({}, std::memory_order_relaxed);
+
+#if HAS_ASAN
+	::__sanitizer_annotate_contiguous_container(
+		p_ + contentOffset_, p_ + alloc_,
+		p_ + contentOffset_ + s.fill, p_ + contentOffset_
+	);
+#endif
+}
+
+
+/**
+ * \fn MetadataList::begin() const
+ * \brief Retrieve begin iterator
+ * \context This function is \threadsafe.
+ */
+
+/**
+ * \fn MetadataList::end() const
+ * \brief Retrieve end iterator
+ * \context This function is \threadsafe.
+ */
+
+/**
+ * \fn MetadataList::get(const Control<T> &ctrl) const
+ * \brief Get the value of control \a ctrl
+ * \return A std::optional<T> containing the control value, or std::nullopt if
+ *         the control \a ctrl is not present in the list
+ * \context This function is \threadsafe.
+ */
+
+/**
+ * \fn MetadataList::get(uint32_t tag) const
+ * \brief Get the value of pertaining to the numeric identifier \a tag
+ * \return A std::optional<T> containing the control value, or std::nullopt if
+ *         the control is not present in the list
+ * \context This function is \threadsafe.
+ */
+
+/**
+ * \internal
+ * \fn MetadataList::set(const Control<T> &ctrl, const internal::cxx20::type_identity_t<T> &value)
+ * \brief Set the value of control \a ctrl to \a value
+ */
+
+/**
+ * \internal
+ * \fn MetadataList::set(uint32_t tag, ControlValueView v)
+ * \brief Set the value of pertaining to the numeric identifier \a tag to \a v
+ */
+
+/**
+ * \internal
+ * \brief Add items from \a other
+ *
+ * If any of them items cannot be added, then an empty optional is returned,
+ * and this function has no effects.
+ */
+std::optional<MetadataList::Diff> MetadataList::merge(const ControlList &other)
+{
+	// \todo check id map of `other`?
+
+	/* Copy the data and update a temporary state (`newState`) */
+
+	const auto oldState = state_.load(std::memory_order_relaxed);
+	auto newState = oldState;
+	const auto entries = this->entries();
+
+	for (const auto &[tag, value] : other) {
+		auto *e = find(tag);
+		if (!e)
+			return {};
+
+		auto [ err, header ] = set(*e, value, newState);
+		if (err != SetError())
+			return {};
+
+		/* HACK: temporarily use the `tag` member to store the entry index */
+		header->tag = e - entries.data();
+	}
+
+	/*
+	 * At this point the data is already in place and every item has been validated
+	 * to have a known id, appropriate size and type, etc., but they are not visible
+	 * in any way. The next step is to make them visible by updating `headerOffset`
+	 * in each affected `Entry` and `state_` in `*this`.
+	 */
+
+	iterator it(p_ + contentOffset_ + oldState.fill);
+	const iterator end(p_ + contentOffset_ + newState.fill);
+
+	for (; it != end; ++it) {
+		auto &header = const_cast<ValueHeader &>(it.header());
+		auto &e = entries[header.tag]; /* HACK: header.tag is temporarily the Entry index */
+
+		header.tag = e.tag; /* HACK: restore */
+
+		e.headerOffset.store(
+			reinterpret_cast<const std::byte *>(&header) - p_,
+			std::memory_order_release
+		);
+	}
+
+	state_.store(newState, std::memory_order_release);
+
+	return {{ *this, newState.count - oldState.count, oldState.fill, newState.fill }};
+}
+
+/**
+ * \internal
+ * \enum MetadataList::SetError
+ * \brief Error code returned by a set operation
+ *
+ * \var MetadataList::SetError::UnknownTag
+ * \brief The tag is not supported by the metadata list
+ * \var MetadataList::SetError::AlreadySet
+ * \brief A value has already been added with the given tag
+ * \var MetadataList::SetError::SizeMismatch
+ * \brief The size of the data is not appropriate for the given tag
+ * \var MetadataList::SetError::TypeMismatch
+ * \brief The type of the value does not match the expected type
+ */
+
+/**
+ * \internal
+ * \fn MetadataList::checkpoint() const
+ * \brief Create a checkpoint
+ * \context This function is \threadsafe.
+ */
+
+MetadataList::SetError MetadataList::set(Entry &e, ControlValueView v)
+{
+	auto s = state_.load(std::memory_order_relaxed);
+
+	auto [ err, header ] = set(e, v, s);
+	if (err != SetError())
+		return err;
+
+	e.headerOffset.store(
+		reinterpret_cast<const std::byte *>(header) - p_,
+		std::memory_order_release
+	);
+	state_.store(s, std::memory_order_release);
+
+	return {};
+}
+
+std::pair<MetadataList::SetError, MetadataList::ValueHeader *>
+MetadataList::set(const Entry &e, ControlValueView v, State &s)
+{
+	if (e.hasValue())
+		return { SetError::AlreadySet, {} };
+	if (e.type != v.type() || e.isArray != v.isArray())
+		return { SetError::TypeMismatch, {} };
+
+	const auto src = v.data();
+	if (e.isArray) {
+		if (src.size_bytes() > e.capacity)
+			return { SetError::SizeMismatch, {} };
+	} else {
+		if (src.size_bytes() != e.capacity)
+			return { SetError::SizeMismatch, {} };
+	}
+
+	std::byte *oldEnd = p_ + contentOffset_ + s.fill;
+	std::byte *p = oldEnd;
+
+	auto *headerPtr = internal::align::up<ValueHeader>(p);
+	auto *dataPtr = internal::align::up(src.size_bytes(), e.alignment, p);
+	internal::align::up(0, alignof(ValueHeader), p);
+
+#if HAS_ASAN
+	::__sanitizer_annotate_contiguous_container(
+		p_ + contentOffset_, p_ + alloc_,
+		oldEnd, p
+	);
+#endif
+
+	auto *header = new (headerPtr) ValueHeader{
+		.tag = e.tag,
+		.size = uint32_t(src.size_bytes()),
+		.alignment = e.alignment,
+		.type = v.type(),
+		.isArray = v.isArray(),
+		.numElements = uint32_t(v.numElements()),
+	};
+	std::memcpy(dataPtr, src.data(), src.size_bytes());
+
+	s.fill += p - oldEnd;
+	s.count += 1;
+
+	return { {}, header };
+}
+
+/**
+ * \class MetadataList::iterator
+ * \brief Iterator
+ */
+
+/**
+ * \typedef MetadataList::iterator::difference_type
+ * \brief iterator's difference type
+ */
+
+/**
+ * \typedef MetadataList::iterator::value_type
+ * \brief iterator's value type
+ */
+
+/**
+ * \typedef MetadataList::iterator::pointer
+ * \brief iterator's pointer type
+ */
+
+/**
+ * \typedef MetadataList::iterator::reference
+ * \brief iterator's reference type
+ */
+
+/**
+ * \typedef MetadataList::iterator::iterator_category
+ * \brief iterator's category
+ */
+
+/**
+ * \fn MetadataList::iterator::operator*()
+ * \brief Retrieve value at iterator
+ * \return A \a ControlListView representing the value
+ */
+
+/**
+ * \fn MetadataList::iterator::operator==(const iterator &other) const
+ * \brief Check if two iterators are equal
+ */
+
+/**
+ * \fn MetadataList::iterator::operator!=(const iterator &other) const
+ * \brief Check if two iterators are not equal
+ */
+
+/**
+ * \fn MetadataList::iterator::operator++(int)
+ * \brief Advance the iterator
+ */
+
+/**
+ * \fn MetadataList::iterator::operator++()
+ * \brief Advance the iterator
+ */
+
+/**
+ * \class MetadataList::Diff
+ * \brief Designates a series of consecutively added metadata items
+ *
+ * A Diff object provides a partial view into a MetadataList, it designates
+ * a series of consecutively added metadata items. Its main purposes is to
+ * enable applications to receive a list of changes made to a MetadataList.
+ *
+ * \sa Camera::metadataAvailable
+ * \internal
+ * \sa MetadataList::Checkpoint::diffSince()
+ */
+
+/**
+ * \fn MetadataList::Diff::list() const
+ * \brief Retrieve the associated MetadataList
+ */
+
+/**
+ * \fn MetadataList::Diff::size() const
+ * \brief Retrieve the number of metadata items designated
+ */
+
+/**
+ * \fn MetadataList::Diff::empty() const
+ * \brief Check if any metadata items are designated
+ */
+
+/**
+ * \fn MetadataList::Diff::operator bool() const
+ * \copydoc MetadataList::Diff::empty() const
+ */
+
+/**
+ * \fn MetadataList::Diff::get(const Control<T> &ctrl) const
+ * \copydoc MetadataList::get(const Control<T> &ctrl) const
+ * \note The lookup will fail if the metadata item is not designated by this Diff object,
+ *       even if it is otherwise present in the backing MetadataList.
+ */
+
+/**
+ * \fn MetadataList::Diff::get(uint32_t tag) const
+ * \copydoc MetadataList::get(uint32_t tag) const
+ * \note The lookup will fail if the metadata item is not designated by this Diff object,
+ *       even if it is otherwise present in the backing MetadataList.
+ */
+
+/**
+ * \fn MetadataList::Diff::begin() const
+ * \brief Retrieve the begin iterator
+ */
+
+/**
+ * \fn MetadataList::Diff::end() const
+ * \brief Retrieve the end iterator
+ */
+
+/**
+ * \internal
+ * \class MetadataList::Checkpoint
+ * \brief Designates a particular state of a MetadataList
+ *
+ * A Checkpoint object designates a point in the stream of metadata items in the associated
+ * MetadataList. Its main use to be able to retrieve the set of metadata items that were
+ * added to the list after the designated point using diffSince().
+ */
+
+/**
+ * \internal
+ * \fn MetadataList::Checkpoint::diffSince() const
+ * \brief Retrieve the set of metadata items added since the checkpoint was created
+ */
+
+} /* namespace libcamera */
diff --git a/test/controls/meson.build b/test/controls/meson.build
index 763f8905e7..ff635454b3 100644
--- a/test/controls/meson.build
+++ b/test/controls/meson.build
@@ -5,12 +5,22 @@  control_tests = [
     {'name': 'control_info_map', 'sources': ['control_info_map.cpp']},
     {'name': 'control_list', 'sources': ['control_list.cpp']},
     {'name': 'control_value', 'sources': ['control_value.cpp']},
+    {'name': 'metadata_list', 'sources': ['metadata_list.cpp']},
 ]
 
+if asan_enabled
+    control_tests += {
+        'name': 'metadata_list_iter_uaf',
+        'sources': ['metadata_list_iter_uaf.cpp'],
+        'should_fail': true,
+    }
+endif
+
 foreach test : control_tests
     exe = executable(test['name'], test['sources'],
                      dependencies : libcamera_public,
                      link_with : test_libraries,
                      include_directories : test_includes_internal)
-    test(test['name'], exe, suite : 'controls', is_parallel : false)
+    test(test['name'], exe, suite : 'controls', is_parallel : false,
+         should_fail : test.get('should_fail', false))
 endforeach
diff --git a/test/controls/metadata_list.cpp b/test/controls/metadata_list.cpp
new file mode 100644
index 0000000000..b0eddde436
--- /dev/null
+++ b/test/controls/metadata_list.cpp
@@ -0,0 +1,205 @@ 
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/*
+ * Copyright (C) 2025, Ideas On Board Oy
+ *
+ * MetadataList tests
+ */
+
+#include <future>
+#include <iostream>
+#include <thread>
+
+#include <libcamera/control_ids.h>
+#include <libcamera/metadata_list.h>
+#include <libcamera/metadata_list_plan.h>
+#include <libcamera/property_ids.h>
+
+#include "test.h"
+
+using namespace std;
+using namespace libcamera;
+
+#define ASSERT(x) do { \
+	if (!static_cast<bool>(x)) { \
+		std::cerr << '`' << #x << "` failed" << std::endl; \
+		return TestFail; \
+	} \
+} while (false)
+
+class MetadataListTest : public Test
+{
+public:
+	MetadataListTest() = default;
+
+protected:
+	int run() override
+	{
+		MetadataListPlan mlp;
+		mlp.set(controls::ExposureTime);
+		mlp.set(controls::ExposureValue);
+		mlp.set(controls::ColourGains);
+		mlp.set(controls::AfWindows, 10);
+		mlp.set(controls::AeEnable);
+		mlp.set(controls::SensorTimestamp);
+
+		MetadataList ml(mlp);
+
+		/*
+		*`properties::Location` has the same numeric id as `controls::AeEnable` (checked by the `static_assert`
+		* below), but they have different types; check that this is detected.
+		*/
+		static_assert(static_cast<unsigned int>(properties::LOCATION) == controls::AE_ENABLE);
+		ASSERT(ml.set(properties::Location, 0xCDCD) == MetadataList::SetError::TypeMismatch);
+
+		ASSERT(ml.set(controls::AfWindows, std::array<Rectangle, 11>{}) == MetadataList::SetError::SizeMismatch);
+		ASSERT(ml.set(controls::ColourTemperature, 123) == MetadataList::SetError::UnknownTag);
+
+		auto f1 = std::async(std::launch::async, [&] {
+			using namespace std::chrono_literals;
+
+			std::this_thread::sleep_for(500ms);
+			ASSERT(ml.set(controls::ExposureTime, 0x1111) == MetadataList::SetError());
+
+			std::this_thread::sleep_for(500ms);
+			ASSERT(ml.set(controls::ExposureValue, 1) == MetadataList::SetError());
+
+			std::this_thread::sleep_for(500ms);
+			ASSERT(ml.set(controls::ColourGains, std::array{
+				123.f,
+				456.f
+			}) == MetadataList::SetError());
+
+			std::this_thread::sleep_for(500ms);
+			ASSERT(ml.set(controls::AfWindows, std::array{
+				Rectangle(),
+				Rectangle(1, 2, 3, 4),
+				Rectangle(0x1111, 0x2222, 0x3333, 0x4444),
+			}) == MetadataList::SetError());
+
+			return TestPass;
+		});
+
+		auto f2 = std::async(std::launch::async, [&] {
+			for (;;) {
+				const auto x = ml.get(controls::ExposureTime);
+				const auto y = ml.get(controls::ExposureValue);
+				const auto z = ml.get(controls::ColourGains);
+				const auto w = ml.get(controls::AfWindows);
+
+				if (x)
+					ASSERT(*x == 0x1111);
+
+				if (y)
+					ASSERT(*y == 1.0f);
+
+				if (z) {
+					ASSERT(z->size() == 2);
+					ASSERT((*z)[0] == 123.f);
+					ASSERT((*z)[1] == 456.f);
+				}
+
+				if (w) {
+					ASSERT(w->size() == 3);
+					ASSERT((*w)[0].isNull());
+					ASSERT((*w)[1] == Rectangle(1, 2, 3, 4));
+					ASSERT((*w)[2] == Rectangle(0x1111, 0x2222, 0x3333, 0x4444));
+				}
+
+				if (x && y && z && w)
+					break;
+			}
+
+			return TestPass;
+		});
+
+		ASSERT(f1.get() == TestPass);
+		ASSERT(f2.get() == TestPass);
+
+		ASSERT(ml.set(controls::ExposureTime, 0x2222) == MetadataList::SetError::AlreadySet);
+		ASSERT(ml.set(controls::ExposureValue, 2) == MetadataList::SetError::AlreadySet);
+
+		ASSERT(ml.get(controls::ExposureTime) == 0x1111);
+		ASSERT(ml.get(controls::ExposureValue) == 1);
+
+		for (auto &&[tag, v] : ml)
+			std::cout << "[" << tag << "] -> " << v << '\n';
+
+		std::cout << std::endl;
+
+		/* Test MetadataList::Diff */
+		{
+			ml.clear();
+			ASSERT(ml.empty());
+			ASSERT(ml.size() == 0);
+
+			ASSERT(ml.set(controls::ExposureTime, 0x2222) == MetadataList::SetError());
+			ASSERT(ml.get(controls::ExposureTime) == 0x2222);
+
+			auto c = ml.checkpoint();
+
+			ASSERT(ml.set(controls::ExposureValue, 2) == MetadataList::SetError());
+			ASSERT(ml.set(controls::SensorTimestamp, 0x99999999) == MetadataList::SetError());
+
+			auto d = c.diffSince();
+			ASSERT(&d.list() == &ml);
+
+			ASSERT(ml.set(controls::ColourGains, std::array{ 1.f, 2.f }) == MetadataList::SetError());
+
+			ASSERT(d);
+			ASSERT(!d.empty());
+			ASSERT(d.size() == 2);
+			ASSERT(!d.get(controls::ExposureTime));
+			ASSERT(!d.get(controls::ColourGains));
+			ASSERT(!d.get(controls::AfWindows));
+			ASSERT(d.get(controls::ExposureValue) == 2);
+			ASSERT(d.get(controls::SensorTimestamp) == 0x99999999);
+
+			for (auto &&[tag, v] : d)
+				std::cout << "[" << tag << "] -> " << v << '\n';
+
+			/* Test if iterators work with algorithms. */
+			std::ignore = std::find_if(d.begin(), d.end(), [](const auto &) {
+				return false;
+			});
+		}
+
+		/* Test transactional behaviour of MetadataList::merge() */
+		{
+			ml.clear();
+			ASSERT(ml.empty());
+			ASSERT(ml.size() == 0);
+
+			{
+				ControlList cl;
+				cl.set(controls::ExposureTime, 0xFEFE);
+				cl.set(controls::ColourGains, std::array{ 1.1f, 2.2f });
+
+				auto d = ml.merge(cl);
+				ASSERT(d);
+				ASSERT(d->size() == cl.size());
+				ASSERT(d->get(controls::ExposureTime) == 0xFEFE);
+				ASSERT(ml.size() == d->size());
+			}
+
+			ASSERT(ml.get(controls::ExposureTime) == 0xFEFE);
+
+			{
+				ControlList cl;
+				cl.set(999, 999); /* not part of plan */
+				cl.set(controls::ExposureTime, 0xEFEF); /* already set */
+				cl.set(properties::Location, 0xCDCD); /* type mismatch */
+				cl.set(controls::SensorTimestamp, 0xABAB); /* ok */
+
+				auto c = ml.checkpoint();
+				auto oldSize = ml.size();
+				ASSERT(!ml.merge(cl));
+				ASSERT(c.diffSince().empty());
+				ASSERT(ml.size() == oldSize);
+			}
+		}
+
+		return TestPass;
+	}
+};
+
+TEST_REGISTER(MetadataListTest)
diff --git a/test/controls/metadata_list_iter_uaf.cpp b/test/controls/metadata_list_iter_uaf.cpp
new file mode 100644
index 0000000000..66b31136e4
--- /dev/null
+++ b/test/controls/metadata_list_iter_uaf.cpp
@@ -0,0 +1,36 @@ 
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/*
+ * Copyright (C) 2025, Ideas On Board Oy
+ *
+ * MetadataList tests
+ */
+
+#include <libcamera/control_ids.h>
+#include <libcamera/metadata_list.h>
+#include <libcamera/metadata_list_plan.h>
+#include <libcamera/property_ids.h>
+
+#include "test.h"
+
+using namespace std;
+using namespace libcamera;
+
+class MetadataListIterUAFTest : public Test
+{
+public:
+	MetadataListIterUAFTest() = default;
+
+protected:
+	int run() override
+	{
+		MetadataListPlan mlp;
+		mlp.set(controls::AeEnable);
+
+		MetadataList ml(mlp);
+		std::ignore = *ml.begin(); /* Trigger ASAN. */
+
+		return TestPass;
+	}
+};
+
+TEST_REGISTER(MetadataListIterUAFTest)