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

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.


> Also see my comment in the previous patch. I really would make
> 'tags' a nested attribute, and then parsing the 'tags' attribute
> would be simple iteration over the tags.

I leave it to Jakub to decide the best approach for passing tags
via the netlink protocol.


> (And don't name it tagset. That will be confusing the hell of out
> of any storage folks, where a tagset is something completely
> different.)

Since the primary operation on this container is "intersection",
set makes the most sense. Stringset?


-- 
Chuck Lever