[RFC PATCH 5/6] KEYS: Replace assoc_array with struct keyring_index

[Jarkko Sakkinen]

On Thu, Oct 22, 2026 at 02:22:43AM +0300, Jarkko Sakkinen wrote:
> On Sat, Oct 17, 2026 at 12:53:03AM +0300, Jarkko Sakkinen wrote:
> > Linux keyring would be better off without struct assoc_array given the
> > overhead caused by sole ownership of it. Linux has multiple popular choices
> > for key-value store and there is nothing special in lib/assoc_array.c that
> > would make it stand out enough to be ratiaonalize the time spent on
> > maintaining it.
> > 
> > A keyring has a sparse data population, making rhashtable a plausible
> > choice. Multiple subsystems rely on it, and best of all, rhashtable has
> > dedicated maintainers.
> > 
> > Replace assoc_array with struct keyring_index, allocated for a keyring on
> > its first link attempt. Initialize its ht member with rhashtable_init()
> > to store links indexed by key type, domain tag and description.
> > 
> > Maintain two linked lists in the index:
> > 
> > - all: enumerate committed links without retrying hash table walks when
> >   the table resizes.
> > - keyrings: visit nested keyrings during recursive search without scanning
> >   links to other key types.
> > 
> > A key can belong to several keyrings. Represent each link with struct
> > keyring_link so it has separate hash table and list nodes and holds its
> > own key reference. Traverse the lists under RCU and defer freeing removed
> > links and dropping their key references until after a grace period.
> > 
> > Assisted-by: LLM
> > Co-developed-by: Linus Torvalds <torvalds at linux-foundation.org>
> > Signed-off-by: Linus Torvalds <torvalds at linux-foundation.org>
> > Signed-off-by: Jarkko Sakkinen <jarkko at kernel.org>
> 
> In addition to addressing Eric's and David's comments, I'll align the
> change with Kyle's fix (and rewrite the commit message).

This turned out not to be difficult. I just purposely had retained the
original behavior of the this patch when I rebased it yesterday until I
had my keyring PR out so could not know :-)

Kyle's fix came at really great spot because if it had came after this
feature had landed stable kernels would need a different fix than the
mainline (given that they build on top of different data structures).

Br, Jarkko