Re: [PATCH 3/9] lib: Add a "tagset" data structure

On Wed, Jun 10, 2026, at 3:06 AM, Hannes Reinecke wrote:
> On 6/9/26 15:35, Chuck Lever wrote:
>> 
>> On Tue, Jun 9, 2026, at 2:45 AM, Hannes Reinecke wrote:
>>> On 6/5/26 19:34, Chuck Lever wrote:
>>>> From: Chuck Lever <[email protected]>
>>>>
>>>> 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.
>>>>
>>> [ .. ]
>>>
>>>
>>> Isn't this overcomplicating matters?
>>> In the end, this a list of strings.
>>> Wouldn't a simple rbtree holding the strings be sufficient?
>>> (And quicker to lookup :-)
>> 
>> This isn't overcomplicating matters.
>> 
>> Consider that a TLS session might have several, even dozens of
>> tags. An NFSD export might also have a dozen or more tags.
>> 
>> We need a mechanism that will compute the intersection of those
>> two sets efficiently -- that is not a simple lookup. Keeping a
>> set of tags in a list or in an r-b tree would require MxN look
>> up operations to compute that intersection.
>> 
> It sure would. But we're dealing with a comparative small number
> of entries (later patches cap it to 64), so runtime really is of
> no concern.

I'm going to push back on that. Let's compare the proposed
tagset implementation with a putative r-b tree-based one.

On a big NFS server, mount operations happen frequently. With 5
tags on a session (say) and 5 allow-tags on an export, that is
25 lookups, each O(log(5)) (for r-b tree).

With the current tagset implementation, it is O(5 + 5).

If both the session and export tags are using the maximum number
of tags, an "intersection" turns into 4000+ lookups, each
O(log(64)). With the current tagset implementation, it's only
O(64 + 64).

The performance of one "intersection" operation goes south
quickly with the number of tags when conventional data types are
used.

And these are all memory fetches, so not all that fast. r-b trees
are notoriously non-optimal in terms of memory access efficiency,
though not as bad as a linked list.


> But let me see if I can come up with an alternative implementation
> using rb trees.

I'm skeptical that an r-b tree implementation will be much simpler.
It will definitely be more costly in terms of CPU and memory
accesses.

For the time being, note that TLS session tags have no support
for PSK -- there are no data items inside the shared keys on
which to match a tag. We might find something else to match on,
though, who knows?


-- 
Chuck Lever