Re: [PATCH v5 2/3] KEYS: Replace assoc_array with rhashtable

[Eric Biggers <ebiggers@kernel.org>]

On Thu, Nov 05, 2026 at 05:14:00AM +0200, Jarkko Sakkinen wrote:
> The keyrings subsystem is the sole user of assoc_array. It has over 1700
> lines of code, no test suite, and a long history of bugs, with LLMs now
> finding more.
> 
> This unfortunate outcome has evolved over time by large from the shortage
> of in-kernel callers, time bandwidth and 3rd party contributors.
> 
> What the keyrings needs is just a generic key-value store, which performs
> well with sparse key sets.
> 
> Replace struct assoc_array in struct key with struct keyring_index:
> 
> - keyring_index: holds an rhashtable for direct lookups, an RCU-protected
>   list of keyring_link entries for stable walks, the active link count, and
>   an rcu_work item for deferred teardown.
> - keyring_link: links a key into a keyring's hash table and list, caching
>   its 32-bit SipHash digest rehashed with jhash by rhashtable.
> 
> Correspondingly, struct assoc_array_edit is replaced by struct keyring_edit
> for delivering transient state across link operations.
> 
> Other behavioral changes:
> 
> - KEYCTL_READ and sibling-keyring searches follow list order instead of
>   hash order: keyrings are prepended, other keys are appended, and
>   replacing a matching key retains its position.
> - key_unlink(), keyring_clear(), keyring_revoke(), and keyring_gc() no
>   longer allocate memory.
> - keyring_index_free() uses queue_rcu_work() instead of call_rcu() because
>   rhashtable_destroy() may sleep.
> 
> Suggested-by: Eric Biggers <ebiggers@kernel.org>
> Co-developed-by: Linus Torvalds <torvalds@linux-foundation.org>
> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
> Signed-off-by: Jarkko Sakkinen <jarkko@kernel.org>

Reviewed-by: Eric Biggers <ebiggers@kernel.org>

But one comment below.

> +		do {
> +			ret = rhashtable_insert_fast(&links->ht, &link->node,
> +						     keyring_link_params);
> +			if (ret == -EBUSY)
> +				fsleep(100);
> +		} while (ret == -EBUSY);
> +		if (ret < 0) {
> +			key_payload_reserve(keyring,
> +					    keyring->datalen - KEYQUOTA_LINK_BYTES);
> +			goto error;
> +		}

I don't think the retry loop is actually sufficient or desirable here
(though it would be very rare for it to be reached).  It gets reached
when there are too many elements in one rhashtable chain.  However,
we're already pre-hashing with SipHash, and the rhashtable level hash is
passed only the 32-bit SipHash.  Suppose we reach this case because the
SipHash values collided: then rhashtable's rehashing would never reduce
the chain length, and the -EBUSY would last forever.

I think the right solution is to just set '.insecure_elasticity = true'
in the rhashtable_params, to disable the chain length checks.  Those
checks make no sense when we're using SipHash anyway.

Then the retry loop would not be needed.

(And even for rhashtable users who aren't using SipHash, like
fs/verity/, hard-failing insertions if the hash chains gets too long
seems wrong.  I mean, imagine if the kernel started refusing to do file
operations if one of the hash chains in the VFS hash tables happened to
get too long...  But I guess rhashtable was designed for towards
networking users who are able to just drop the data without much issue.
Plus it predates SipHash existing.)

- Eric