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

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.

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

> 
>> 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.
> 
> 
Sure.

>> (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?
> 
> 
Better.

Cheers,

Hannes
-- 
Dr. Hannes Reinecke                  Kernel Storage Architect
[email protected]                                +49 911 74053 688
SUSE Software Solutions GmbH, Frankenstr. 146, 90461 Nürnberg
HRB 36809 (AG Nürnberg), GF: I. Totev, A. McDonald, W. Knoblich