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

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 2 potential
issues to consider:
- [Medium] keys: missing insecure_elasticity and unbounded -EBUSY loop
  in __key_link_begin()
- [Low] keys: mixed goto and delayed __free() initialization in
  __key_link_begin()
--

commit 2ac2cea452f12974dec0263462b3e701c718671c
Author: Jarkko Sakkinen <jarkko@kernel.org>

KEYS: Replace assoc_array with rhashtable

This commit replaces the associative array in struct key with a
keyring_index backed by an rhashtable for direct lookups and an
RCU-protected list of keyring_link entries for ordered traversal.

> diff --git a/security/keys/keyring.c b/security/keys/keyring.c
> index ac48d6204915a..772fa0e35f9db 100644
> --- a/security/keys/keyring.c
> +++ b/security/keys/keyring.c
> @@ -31,25 +33,152 @@

[ ... ]

> +static const struct rhashtable_params keyring_link_params = {
> +	.head_offset		= offsetof(struct keyring_link, node),
> +	.hashfn			= keyring_hashfn,
> +	.obj_hashfn		= keyring_obj_hashfn,
> +	.obj_cmpfn		= keyring_obj_cmpfn,
> +	.min_size		= 4,
> +	.nelem_hint		= 3,
> +	.automatic_shrinking	= true,
> +};

[ ... ]

> @@ -1317,56 +1155,94 @@ int __key_move_lock(struct key *l_keyring, struct key *u_keyring,

[ ... ]

>  int __key_link_begin(struct key *keyring,
>  		     const struct keyring_index_key *index_key,
> -		     struct assoc_array_edit **_edit)
> +		     struct keyring_edit *edit)
>  {
> -	struct assoc_array_edit *edit;
> +	struct keyring_link *link __free(kfree) = NULL;
> +	struct keyring_link *replace;
> +	struct keyring_index *links;
>  	int ret;
>  
>  	kenter("%d,%s,%s,",
>  	       keyring->serial, index_key->type->name, index_key->description);
>  
> -	BUG_ON(index_key->desc_len == 0);
> -	BUG_ON(*_edit != NULL);
> +	if (WARN_ON(index_key->desc_len == 0) || WARN_ON(edit->new))
> +		return -EINVAL;
>  
> -	*_edit = NULL;
> +	edit->new = NULL;
> +	edit->old = NULL;
>  
>  	ret = -EKEYREVOKED;
>  	if (test_bit(KEY_FLAG_REVOKED, &keyring->flags))
>  		goto error;
>  
> -	/* Create an edit script that will insert/replace the key in the
> -	 * keyring tree.
> -	 */
> -	edit = assoc_array_insert(&keyring->keys,
> -				  &keyring_assoc_array_ops,
> -				  index_key,
> -				  NULL);
> -	if (IS_ERR(edit)) {
> -		ret = PTR_ERR(edit);
> +	links = keyring_get_index(keyring);
> +	if (IS_ERR(links)) {
> +		ret = PTR_ERR(links);
>  		goto error;
>  	}
>  
> +	ret = -ENOMEM;
> +	link = kzalloc_obj(struct keyring_link);
> +	if (!link)
> +		goto error;

[Severity: Low]
This isn't a bug, but per the cleanup.h conventions, link should be
defined and initialized at its kzalloc_obj() allocation site rather than
declared as NULL at the top of __key_link_begin() and mixed with goto
error paths.

> +	link->hash = index_key->hash;
> +
> +	replace = keyring_find_link(links, index_key);
>  	/* If we're not replacing a link in-place then we're going to need some
>  	 * extra quota.
>  	 */
> -	if (!edit->dead_leaf) {
> +	if (!replace) {
>  		ret = key_payload_reserve(keyring,
>  					  keyring->datalen + KEYQUOTA_LINK_BYTES);
>  		if (ret < 0)
> -			goto error_cancel;
> +			goto error;
> +
> +		do {
> +			ret = rhashtable_insert_fast(&links->ht, &link->node,
> +						     keyring_link_params);
> +			if (ret == -EBUSY)
> +				fsleep(100);
> +		} while (ret == -EBUSY);

[Severity: Medium]
As reported by Eric Biggers on v5 [1], should keyring_link_params set
.insecure_elasticity = true instead of looping on -EBUSY here?

Without .insecure_elasticity, rhashtable_insert_fast() enforces the
16-entry bucket chain limit (RHT_ELASTICITY) and returns -EBUSY to trigger
a rehash.  Because keyring_obj_hashfn() only hashes the 32-bit link->hash
via jhash_1word(), entries with colliding 32-bit SipHash digests cannot be
split by rehashing with a new seed, so __key_link_begin() can spin
indefinitely in this loop while holding keyring->sem.  This was fixed in
v6 by setting .insecure_elasticity = true and dropping the retry loop, but
appears to have been lost in v7.

[1] https://lore.kernel.org/r/20261107032551.GA1990@sol

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261110033738.2495880-1-jarkko@kernel.org?part=2