[PATCH 3/9] lib: Add a "tagset" data structure
Chuck Lever
cel at kernel.org
Fri Jun 5 10:34:37 PDT 2026
From: Chuck Lever <chuck.lever at oracle.com>
Access control mechanisms sometimes need to match metadata tags
between a session and a resource. A tagset provides efficient
membership testing and set intersection operations for this purpose.
The implementation uses a sorted array of string pointers. Unlike
hash tables, sorted arrays support efficient intersection without
needing to iterate one set and probe the other. Unlike rbtrees,
they require no per-element node allocation, minimizing memory
overhead for small sets typical of resource tagging.
Operation complexities:
- tagset_add(): O(1)
- tagset_finalize(): O(N log N) for sorting and deduplication
- tagset_is_member(): O(log N) via binary search
- tagset_intersection(): O(N + M) via merge comparison
The API follows a build-then-query pattern: callers initialize,
allocate capacity, add tags, then finalize before querying. Once
finalized, the tagset is suitable for concurrent read access.
Consumers of the new APIs will be introduced in subsequent patches.
Signed-off-by: Chuck Lever <chuck.lever at oracle.com>
---
Documentation/core-api/index.rst | 1 +
Documentation/core-api/tagset.rst | 225 ++++++++++++++++++++++++++++++++++++++
include/linux/tagset.h | 187 +++++++++++++++++++++++++++++++
lib/Makefile | 1 +
lib/tagset.c | 174 +++++++++++++++++++++++++++++
5 files changed, 588 insertions(+)
diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.rst
index 13769d5c40bf..d48c074e6b12 100644
--- a/Documentation/core-api/index.rst
+++ b/Documentation/core-api/index.rst
@@ -45,6 +45,7 @@ Library functionality that is used throughout the kernel.
idr
circular-buffers
rbtree
+ tagset
generic-radix-tree
packing
this_cpu_ops
diff --git a/Documentation/core-api/tagset.rst b/Documentation/core-api/tagset.rst
new file mode 100644
index 000000000000..2945cfa95ab4
--- /dev/null
+++ b/Documentation/core-api/tagset.rst
@@ -0,0 +1,225 @@
+.. SPDX-License-Identifier: GPL-2.0+
+
+======
+Tagset
+======
+
+Overview
+========
+
+A tagset is a set of strings, intended for resource tagging where
+metadata about a resource is represented simply by a name. The public
+API can be found in ``<linux/tagset.h>``.
+
+
+Initialization and Destruction
+==============================
+
+A tagset must be initialized before use::
+
+ struct tagset tags;
+ tagset_init(&tags);
+
+Before adding tags, allocate capacity::
+
+ if (!tagset_alloc(&tags, num_tags, GFP_KERNEL))
+ return -ENOMEM;
+
+When finished, release all resources::
+
+ tagset_destroy(&tags);
+
+This frees all tag strings and the array. The tagset is reinitialized
+and may be reused by calling ``tagset_alloc()`` again.
+
+
+Adding Tags
+===========
+
+Two functions are provided for adding tags. Both require that
+sufficient capacity has been allocated via ``tagset_alloc()``.
+All functions that allocate memory return false on failure; callers
+should check return values.
+
+``tagset_add()``
+ Adds a tag string that is already in kmalloc'd memory. On success,
+ the tagset takes ownership of the string and will free it when
+ the tagset is destroyed::
+
+ char *tag = kstrdup("mytag", GFP_KERNEL);
+ if (!tag || !tagset_add(&tags, tag))
+ kfree(tag); /* failed, caller must free */
+
+``tagset_add_dup()``
+ Duplicates the tag string internally. The caller retains ownership
+ of the original string::
+
+ if (!tagset_add_dup(&tags, "mytag", GFP_KERNEL))
+ return -ENOMEM;
+
+Both functions return true on success, false on failure. Tags must
+not be added after ``tagset_finalize()`` has been called. Use
+``GFP_ATOMIC`` when adding tags in atomic context.
+
+
+Finalizing
+==========
+
+After adding all tags, the tagset must be finalized before querying::
+
+ tagset_finalize(&tags);
+
+This sorts the array to enable efficient binary search and removes
+any duplicate tags. Calling ``tagset_is_member()`` or
+``tagset_intersection()`` on a non-finalized tagset produces
+undefined results.
+
+
+Querying Tags
+=============
+
+``tagset_is_empty()``
+ Returns true if the tagset contains no tags.
+
+``tagset_count()``
+ Returns the number of tags in the tagset. Before finalization,
+ this is the number of tags added; after finalization, this is
+ the number of unique tags.
+
+``tagset_is_member()``
+ Returns true if a tag is present in the tagset. Uses binary
+ search for O(log N) complexity::
+
+ if (tagset_is_member(&tags, "mytag"))
+ pr_info("tag found\n");
+
+``tagset_intersection()``
+ Returns true if two tagsets share at least one common tag.
+ Uses merge-style comparison for O(N+M) complexity::
+
+ if (tagset_intersection(&tags1, &tags2))
+ pr_info("sets overlap\n");
+
+
+Iteration
+=========
+
+Use ``tagset_for_each()`` to iterate over all tags::
+
+ unsigned int index;
+ char *tag;
+
+ tagset_for_each(&tags, index, tag)
+ pr_info("tag: %s\n", tag);
+
+Callers should not depend on the order in which tags are returned.
+Modifying the tagset during iteration produces undefined behavior.
+
+
+Copying
+=======
+
+``tagset_copy()`` duplicates all tags from one tagset to another::
+
+ struct tagset copy;
+ if (!tagset_copy(©, &original, GFP_KERNEL))
+ pr_err("copy failed\n");
+
+The source tagset should be finalized before copying. The destination
+tagset is initialized and ready for queries after this function
+returns (no separate ``tagset_finalize()`` call is needed). Each tag
+string is duplicated, so the two tagsets are fully independent after
+copying.
+
+
+Typical Usage Pattern
+=====================
+
+A typical usage pattern for building a tagset::
+
+ struct tagset tags;
+
+ tagset_init(&tags);
+ if (!tagset_alloc(&tags, count, GFP_KERNEL))
+ return -ENOMEM;
+
+ for (i = 0; i < count; i++) {
+ if (!tagset_add_dup(&tags, strings[i], GFP_KERNEL)) {
+ tagset_destroy(&tags);
+ return -ENOMEM;
+ }
+ }
+ tagset_finalize(&tags);
+
+ /* Now safe to query */
+ if (tagset_is_member(&tags, "target"))
+ do_something();
+
+ tagset_destroy(&tags);
+
+
+Thread Safety
+=============
+
+Tagsets have no internal locking. Callers provide synchronization
+between writers and readers.
+
+The build-and-finalize phase mutates the tagset; the post-finalize
+query phase reads from it. The two phases must be separated by a
+publication boundary, because ``tagset_finalize()`` itself carries
+no memory barrier. A reader that observes the finalized tagset
+before the writer's stores have propagated may see a stale
+``ts_count`` or a partially populated ``ts_tags[]`` array.
+
+Three publication patterns are sufficient:
+
+* Lock release after ``tagset_finalize()``, lock acquire before
+ each query. The matching unlock/lock pair supplies release and
+ acquire ordering.
+
+* ``rcu_assign_pointer()`` of the tagset pointer after
+ ``tagset_finalize()``, paired with ``rcu_dereference()`` inside
+ an RCU read-side critical section on the reader.
+
+* ``smp_store_release()`` of the tagset pointer after
+ ``tagset_finalize()``, paired with ``smp_load_acquire()`` on the
+ reader.
+
+Once published, the tagset must remain immutable until no further
+readers can observe it. ``tagset_destroy()`` is not safe against
+concurrent readers, and ``tagset_finalize()`` must not be called
+more than once. With RCU publication, callers typically defer
+destruction to a grace period (``synchronize_rcu()`` before
+``tagset_destroy()``, or ``tagset_destroy()`` from a
+``call_rcu()`` callback) so that in-flight readers drain before
+the storage is freed.
+
+
+Implementation
+==============
+
+Each tagset is rooted on the following structure::
+
+ struct tagset {
+ char **ts_tags;
+ unsigned int ts_count;
+ unsigned int ts_capacity;
+ bool ts_finalized;
+ };
+
+The implementation uses a sorted array of string pointers, providing
+O(log N) membership testing and O(N+M) intersection operations.
+
++------------------------+-------------+
+| Operation | Complexity |
++========================+=============+
+| tagset_add | O(1) |
++------------------------+-------------+
+| tagset_finalize | O(N log N) |
++------------------------+-------------+
+| tagset_is_member | O(log N) |
++------------------------+-------------+
+| tagset_intersection | O(N + M) |
++------------------------+-------------+
+| tagset_copy | O(N) |
++------------------------+-------------+
diff --git a/include/linux/tagset.h b/include/linux/tagset.h
new file mode 100644
index 000000000000..8b0a58add8fc
--- /dev/null
+++ b/include/linux/tagset.h
@@ -0,0 +1,187 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Tagsets
+ *
+ * Copyright (c) 2025, Oracle and/or its affiliates.
+ * Author: Chuck Lever <chuck.lever at oracle.com>
+ *
+ * A tagset is a set of strings. See
+ * Documentation/core-api/tagset.rst for how to use tagsets.
+ *
+ * Tagsets have no internal locking. Callers provide synchronization
+ * between writers and readers, including a release/acquire (RCU, or
+ * matching unlock/lock) publication boundary between tagset_finalize()
+ * and the first concurrent query, and a grace period (or equivalent
+ * reader drain) before tagset_destroy(). See the Thread Safety section
+ * of Documentation/core-api/tagset.rst.
+ */
+
+#ifndef _LINUX_TAGSET_H
+#define _LINUX_TAGSET_H
+
+#include <linux/bug.h>
+#include <linux/slab.h>
+
+struct tagset {
+ char **ts_tags;
+ unsigned int ts_count;
+ unsigned int ts_capacity;
+ bool ts_finalized;
+};
+
+#define TAGSET_INIT \
+ { .ts_tags = NULL, .ts_count = 0, .ts_capacity = 0, .ts_finalized = false }
+#define DEFINE_TAGSET(name) \
+ struct tagset name = TAGSET_INIT
+
+/**
+ * tagset_for_each - Iterate over items in a tagset
+ * @set: An initialized tagset containing zero or more items
+ * @index: Index counter for the iteration
+ * @tag: Tag retrieved from the tagset
+ */
+#define tagset_for_each(set, index, tag) \
+ for ((index) = 0; (index) < (set)->ts_count && \
+ ((tag) = (set)->ts_tags[index], true); (index)++)
+
+/**
+ * tagset_init - Initialize an empty tagset
+ * @set: tagset to be initialized
+ */
+static inline void tagset_init(struct tagset *set)
+{
+ set->ts_tags = NULL;
+ set->ts_count = 0;
+ set->ts_capacity = 0;
+ set->ts_finalized = false;
+}
+
+/**
+ * tagset_alloc - Pre-allocate space for tags
+ * @set: An initialized tagset
+ * @capacity: Number of tags to allocate space for
+ * @gfp: Memory allocation flags
+ *
+ * This function may only be called once per tagset. Calling it on a
+ * tagset that has already been allocated returns failure.
+ *
+ * @capacity may be zero. The tagset then represents an empty set:
+ * tagset_add() rejects further additions, and tagset_finalize(),
+ * tagset_is_member(), tagset_intersection(), and tagset_destroy()
+ * all handle it correctly. The same state is produced by
+ * DEFINE_TAGSET() and tagset_init() alone, so callers that know the
+ * set is empty may skip tagset_alloc() entirely.
+ *
+ * Return:
+ * %true: allocation succeeded (or @capacity was zero)
+ * %false: allocation failed or tagset already allocated
+ */
+static inline __must_check bool
+tagset_alloc(struct tagset *set, unsigned int capacity, gfp_t gfp)
+{
+ if (set->ts_tags)
+ return false;
+ if (capacity == 0)
+ return true;
+
+ set->ts_tags = kcalloc(capacity, sizeof(char *), gfp);
+ if (!set->ts_tags)
+ return false;
+ set->ts_capacity = capacity;
+ return true;
+}
+
+/**
+ * tagset_is_empty - Determine if a tagset contains any tags
+ * @set: An initialized tagset to be checked
+ *
+ * Return:
+ * %true: if @set is empty
+ * %false: if @set contains one or more tags
+ */
+static inline bool tagset_is_empty(const struct tagset *set)
+{
+ return set->ts_count == 0;
+}
+
+/**
+ * tagset_count - Return the number of tags in a tagset
+ * @set: An initialized tagset to be checked
+ *
+ * If called before tagset_finalize(), returns the number of tags
+ * added. If called after, returns the number of unique tags.
+ *
+ * Return:
+ * The number of tags in @set
+ */
+static inline unsigned int tagset_count(const struct tagset *set)
+{
+ return set->ts_count;
+}
+
+/**
+ * tagset_add - Add a tag to a tagset
+ * @set: An initialized tagset with available capacity
+ * @tag: non-NULL tag string to be added to @set, in kmalloc'd memory
+ *
+ * On success, @tag is now owned by @set and will be freed either
+ * by tagset_finalize() (if a content duplicate) or tagset_destroy().
+ * The tagset must have been allocated with sufficient capacity via
+ * tagset_alloc(). Tags must not be added after tagset_finalize() has
+ * been called. Callers must not hand the same pointer to tagset_add()
+ * more than once: ownership has already transferred, and a second add
+ * produces a double-free at tagset_destroy().
+ *
+ * Return:
+ * %true: @tag is now a member of @set
+ * %false: @tag could not be added (NULL or no capacity)
+ */
+static inline __must_check bool
+tagset_add(struct tagset *set, char *tag)
+{
+ if (WARN_ON_ONCE(set->ts_finalized))
+ return false;
+ if (!tag || set->ts_count >= set->ts_capacity)
+ return false;
+ set->ts_tags[set->ts_count++] = tag;
+ return true;
+}
+
+/**
+ * tagset_add_dup - Add a copy of a tag to a tagset
+ * @set: An initialized tagset with available capacity
+ * @tag: non-NULL tag string to be copied and added to @set
+ * @gfp: Memory allocation flags
+ *
+ * On success, @tag will have been copied into a kmalloc'd
+ * buffer. The caller can release @tag immediately. Tags must not
+ * be added after tagset_finalize() has been called.
+ *
+ * Return:
+ * %true: @tag is now a member of @set
+ * %false: @tag could not be added (NULL, no capacity, or ENOMEM)
+ */
+static inline __must_check bool
+tagset_add_dup(struct tagset *set, const char *tag, gfp_t gfp)
+{
+ char *entry;
+
+ if (WARN_ON_ONCE(set->ts_finalized))
+ return false;
+ if (!tag || set->ts_count >= set->ts_capacity)
+ return false;
+ entry = kstrdup(tag, gfp);
+ if (!entry)
+ return false;
+ set->ts_tags[set->ts_count++] = entry;
+ return true;
+}
+
+/* Implemented in lib/tagset.c */
+void tagset_finalize(struct tagset *set);
+void tagset_destroy(struct tagset *set);
+bool tagset_is_member(const struct tagset *set, const char *tag);
+bool tagset_copy(struct tagset *dest, const struct tagset *src, gfp_t gfp);
+bool tagset_intersection(const struct tagset *set1, const struct tagset *set2);
+
+#endif /* _LINUX_TAGSET_H */
diff --git a/lib/Makefile b/lib/Makefile
index f33a24bf1c19..4f3be192be5b 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -61,6 +61,7 @@ obj-y += bcd.o sort.o parser.o debug_locks.o random32.o \
generic-radix-tree.o bitmap-str.o
obj-y += string_helpers.o
obj-y += hexdump.o
+obj-y += tagset.o
obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
obj-y += kstrtox.o
obj-$(CONFIG_FIND_BIT_BENCHMARK) += find_bit_benchmark.o
diff --git a/lib/tagset.c b/lib/tagset.c
new file mode 100644
index 000000000000..a7e09895e370
--- /dev/null
+++ b/lib/tagset.c
@@ -0,0 +1,174 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Tagsets - a sorted set of strings
+ *
+ * Copyright (c) 2025, Oracle and/or its affiliates.
+ * Author: Chuck Lever <chuck.lever at oracle.com>
+ */
+
+#include <linux/bug.h>
+#include <linux/export.h>
+#include <linux/sort.h>
+#include <linux/tagset.h>
+
+static int tagset_cmp(const void *a, const void *b)
+{
+ const char * const *sa = a;
+ const char * const *sb = b;
+
+ return strcmp(*sa, *sb);
+}
+
+/**
+ * tagset_finalize - Sort the tagset and remove duplicates
+ * @set: An initialized tagset that has been populated
+ *
+ * This must be called after all tags have been added and before
+ * calling tagset_is_member() or tagset_intersection(). Duplicate
+ * tags are removed and their memory is freed.
+ */
+void tagset_finalize(struct tagset *set)
+{
+ unsigned int i, j;
+
+ if (WARN_ON_ONCE(set->ts_finalized))
+ return;
+ if (set->ts_count > 1) {
+ sort(set->ts_tags, set->ts_count, sizeof(char *),
+ tagset_cmp, NULL);
+
+ /* Remove duplicates in place */
+ for (i = 0, j = 1; j < set->ts_count; j++) {
+ if (strcmp(set->ts_tags[i], set->ts_tags[j]) == 0)
+ kfree(set->ts_tags[j]);
+ else
+ set->ts_tags[++i] = set->ts_tags[j];
+ }
+ set->ts_count = i + 1;
+ }
+ set->ts_finalized = true;
+}
+EXPORT_SYMBOL_GPL(tagset_finalize);
+
+/**
+ * tagset_destroy - Release tagset resources
+ * @set: tagset to be destroyed
+ */
+void tagset_destroy(struct tagset *set)
+{
+ unsigned int i;
+
+ for (i = 0; i < set->ts_count; i++)
+ kfree(set->ts_tags[i]);
+ kfree(set->ts_tags);
+ tagset_init(set);
+}
+EXPORT_SYMBOL_GPL(tagset_destroy);
+
+/**
+ * tagset_is_member - Check if a tag is already a member of a tagset
+ * @set: An initialized and finalized tagset to be checked
+ * @tag: tag string to search for
+ *
+ * Uses binary search. The tagset must have been finalized first.
+ *
+ * Return:
+ * %true: if @tag is a member of @set
+ * %false: if @tag is not a member of @set
+ */
+bool tagset_is_member(const struct tagset *set, const char *tag)
+{
+ unsigned int low = 0, high = set->ts_count;
+
+ WARN_ON_ONCE(!set->ts_finalized);
+ while (low < high) {
+ unsigned int mid = low + (high - low) / 2;
+ int cmp = strcmp(tag, set->ts_tags[mid]);
+
+ if (cmp == 0)
+ return true;
+ if (cmp < 0)
+ high = mid;
+ else
+ low = mid + 1;
+ }
+ return false;
+}
+EXPORT_SYMBOL_GPL(tagset_is_member);
+
+/**
+ * tagset_copy - Duplicate tags to another tagset
+ * @dest: An empty, initialized tagset to be filled
+ * @src: An initialized tagset to be copied from
+ * @gfp: Memory allocation flags
+ *
+ * @dest must be initialized -- via TAGSET_INIT, DEFINE_TAGSET,
+ * tagset_init(), or a prior tagset_destroy() -- and must hold no
+ * tags. Passing a populated tagset leaks its contents.
+ *
+ * On success @dest is populated and ready for use; no call to
+ * tagset_finalize() is required. On failure @dest is left as an
+ * empty, finalized tagset, so callers can safely run queries
+ * against it without first checking the return value.
+ *
+ * Return:
+ * %true: All tags in @src were copied to @dest
+ * %false: A failure occurred; @dest is empty and finalized
+ */
+bool tagset_copy(struct tagset *dest, const struct tagset *src, gfp_t gfp)
+{
+ unsigned int i;
+
+ /* src is already sorted, so dest is too */
+ dest->ts_finalized = src->ts_finalized;
+ if (src->ts_count == 0)
+ return true;
+ if (!tagset_alloc(dest, src->ts_count, gfp))
+ goto out_fail;
+ for (i = 0; i < src->ts_count; i++) {
+ char *entry = kstrdup(src->ts_tags[i], gfp);
+
+ if (!entry)
+ goto out_fail;
+ dest->ts_tags[dest->ts_count++] = entry;
+ }
+ return true;
+
+out_fail:
+ tagset_destroy(dest);
+ dest->ts_finalized = true;
+ return false;
+}
+EXPORT_SYMBOL_GPL(tagset_copy);
+
+/**
+ * tagset_intersection - Report if there are common tags
+ * @set1: An initialized and finalized tagset
+ * @set2: Another initialized and finalized tagset
+ *
+ * Uses merge-style comparison of two sorted arrays for O(N+M)
+ * complexity.
+ *
+ * Return:
+ * %true: @set1 and @set2 have at least one common tag
+ * %false: @set1 and @set2 have no tags in common
+ */
+bool tagset_intersection(const struct tagset *set1, const struct tagset *set2)
+{
+ unsigned int i = 0, j = 0;
+
+ WARN_ON_ONCE(!set1->ts_finalized);
+ WARN_ON_ONCE(!set2->ts_finalized);
+ while (i < set1->ts_count && j < set2->ts_count) {
+ int cmp = strcmp(set1->ts_tags[i], set2->ts_tags[j]);
+
+ if (cmp == 0)
+ return true;
+ if (cmp < 0)
+ i++;
+ else
+ j++;
+ }
+ return false;
+}
+EXPORT_SYMBOL_GPL(tagset_intersection);
--
2.54.0
More information about the Linux-nvme
mailing list