[PATCH v2 5/6] KEYS: Replace assoc_array with rhashtable

[Jarkko Sakkinen]

On Fri, Oct 23, 2026 at 03:09:25PM +0300, Jarkko Sakkinen wrote:
> The keyring subsystem depends on assoc_array for searching keys by their
> description, type and domain. It is the sole user of this data structure,
> which has during the age of LLMs transformed into a maintenance nightmare.
> 
> assoc_array needs to be replaced with a data structure meeting the
> following criteria:
> 
> 1. Must be suitable for a sparse key-value store.
> 2. Must have multiple in-kernel users.
> 3. Would be nice if it had dedicated maintainers.
> 
> rhashtable is likely the best pick from the available options as it is
> designed for a sparse key space, has dedicated maintainers, and multiple
> in-kernel users.
> 
> assoc_array is replaced with two new data types:
> 
> - keyring_index: contains a searchable index of links to keys and an RCU
>   protected list for active links, which is used to provide stable walks.
> - keyring_link: a keyring node and its contents. Multiple of these can be
>   associated with a key as it can belong to multiple keyrings.
> 
> assoc_array_edit is substituted with two-element array of keyring_link
> pointers with no specific data type defined.
> 
> Jenkins hash digest's used by rhashtable are rehashed from the SipHash
> digests of search keys and links.
> 
> Assisted-by: LLM
> Suggested-by: Eric Biggers <ebiggers at kernel.org>
> 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>

I did quite extensive testing on this revision and have deployed these
patches to my at-work project builds, which is a vLMM appliance type of
an operating system.

Br, Jarkko