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

[Eric Biggers <ebiggers@kernel.org>]

On Fri, Oct 30, 2026 at 01:24:10AM +0200, Jarkko Sakkinen wrote:
> It is the sole user of this data structure,
> which has during the age of LLMs transformed into a maintenance nightmare.

As I said on v3, this probably should be reworded to be more specific.
Otherwise it sounds subjective, and it may become a weird Phoronix
headline like "Linux awakens from associative array nightmare".
See the sentence I suggested at
https://lore.kernel.org/keyrings/20261027012952.GC2395@quark/

> assoc_array is replaced with three new data types:

Well, 'struct keyring_edit' is the odd one out, since it replaces
'struct assoc_array_edit', not 'struct assoc_array'.  It is also
temporary transactional state.

It would be clearer to say that the replacement for 'struct assoc_array'
is 'struct keyring_index'.  Then describe what that contains (which
would include mentioning 'struct keyring_link').

It would also be worth mentioning explicitly that this is a significant
negative diff in the keyrings subsystem, since correctly integrating
with assoc_array was quite complex.

Overall I suggest de-emphasizing the rhashtable in the commit message
slightly, given that it's just one piece of the new implementation.
After all, it could have been a basic custom hashtable instead, and
other high-level details of this commit would still be the same.

> Jhashes used by rhashtable are rehashed from the SipHash digests of the
> search keys and links.

The commit message should mention explicitly whether there are any
userspace-visible behavior changes or not.

KEYCTL_READ now outputs in insertion order, not hash order, right?  And
likewise for the search order of sibling keyrings.  Those differences
should be fine, but they should be mentioned.  Any other changes?

> -/*
> - * Hash a key type, domain and description.  KEYCTL_READ exposes the tree's
> - * traversal order, so no part of the index may contain kernel addresses.
> + * Hash a key type, domain and description.
>   */
>  static void hash_key_type_and_desc(struct keyring_index_key *index_key)
>  {
> -	const unsigned level_shift = ASSOC_ARRAY_LEVEL_STEP;
> -	const unsigned long fan_mask = ASSOC_ARRAY_FAN_MASK;
>  	static siphash_key_t hash_key __read_mostly;
> -	unsigned long hash;
>  	u64 acc;
>  
>  	get_random_once(&hash_key, sizeof(hash_key));
>  	acc = siphash(index_key->description, index_key->desc_len, &hash_key);
> -	acc = siphash_3u64(index_key->type_id, index_key->domain_id, acc,
> -			   &hash_key);
> -
> -	/* Fold the hash down to 32 bits if need be. */
> -	hash = acc;
> -	if (ASSOC_ARRAY_KEY_CHUNK_SIZE == 32)
> -		hash ^= acc >> 32;
> -
> -	/* Squidge all the keyrings into a separate part of the tree to
> -	 * ordinary keys by making sure the lowest level segment in the hash is
> -	 * zero for keyrings and non-zero otherwise.
> -	 */
> -	if (index_key->type != &key_type_keyring && (hash & fan_mask) == 0)
> -		hash |= (hash >> (ASSOC_ARRAY_KEY_CHUNK_SIZE - level_shift)) | 1;
> -	else if (index_key->type == &key_type_keyring && (hash & fan_mask) != 0)
> -		hash = (hash + (hash << level_shift)) & ~fan_mask;
> -	index_key->hash = hash;
> +	index_key->hash = siphash_3u64((uintptr_t)index_key->type,
> +				       (uintptr_t)index_key->domain_tag,
> +				       acc, &hash_key);

There should be a comment here that explains why it's safe to hash the
pointers and truncate the hash value.  It is clear to me but will not be
to others.  Here is what I suggested on v1:

        /*
         * Compute a SipHash value of the description, type pointer, and domain
         * tag pointer using a per-boot random key.
         *
         * Note that using the pointers as input to the hash is safe, since
         * SipHash is a cryptographically secure pseudorandom function.  Thus
         * the hash values don't leak any information about the pointers.
         *
         * Similarly, truncating the SipHash values to the required 32 bits is
         * also safe.  No "folding" step is needed.
         */

Side note: keyring.c now uses jhash as well, so it should include
<linux/jhash.h> explicitly rather than rely on transitive inclusion.

- Eric