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

[Eric Biggers <ebiggers@kernel.org>]

On Sun, Oct 25, 2026 at 03:10:13AM +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.

Maybe reword to be more specific, like: "It is the sole user of this
data structure, which has 1700 lines of code with no test suite and has
had many bugs reported over the years, with LLMs now finding more."

>  struct key_tag {
>  	struct rcu_head		rcu;
> @@ -118,18 +118,7 @@ struct key_tag {
>  struct keyring_index_key {
>  	/* [!] If this structure is altered, the union in struct key must change too! */
>  	unsigned long		hash;			/* Hash value */

As I suggested before, I think the hash field (here and in struct key)
should be changed to u32, since that is all that is used now.  Also, the
SipHash value can just be truncated from 64 bits to 32 instead of
"folded".  Also, the pointers can be used directly in the computation
once again, now that they're no longer needed for the assoc_array key.
(And that means the domain_id and type_id can be removed.)

Are those simplifications planned for follow-up commits, maybe?

> +static int keyring_obj_cmpfn(struct rhashtable_compare_arg *arg,
> +			     const void *obj)
> +{
> +	const struct keyring_link *link = obj;
> +	const struct key *key = rcu_dereference_check(link->key, true);

This probably should use keyring_link_key(), which should be moved up to
earlier in the file.  Or rcu_dereference(), since it looks like this is
always called under the RCU lock.

> +static void keyring_index_free(struct key *keyring)
> +{
> +	struct keyring_index *index = keyring_index_locked(keyring);
> +
> +	if (!index)
> +		return;
> +
> +	rcu_assign_pointer(keyring->index, NULL);
> +	queue_rcu_work(system_dfl_wq, &index->rcu_work);

It's queue_rcu_work() rather than call_rcu() because
rhashtable_destroy() can sleep, right?  Commenting that might help.

> +static struct keyring_index *keyring_get_index(struct key *keyring)
> +{
> +	struct keyring_index *links __free(kfree) =
> +		keyring_index_locked(keyring);
> +	int ret;
> +
> +	if (links)
> +		return_ptr(links);
> +
> +	links = kzalloc_obj(struct keyring_index);
> +	if (!links)
> +		return ERR_PTR(-ENOMEM);
> +	ret = rhashtable_init(&links->ht, &keyring_link_params);
> +	if (ret < 0)
> +		return ERR_PTR(ret);
> +
> +	INIT_LIST_HEAD(&links->list);
> +	INIT_RCU_WORK(&links->rcu_work, keyring_index_free_work);
> +	rcu_assign_pointer(keyring->index, links);
> +	return_ptr(links);
> +}

Assigning the live index to a __free variable is kind of weird (even
though return_ptr handles it).  I think it would be simpler without
scoped cleanup here:

static struct keyring_index *keyring_get_index(struct key *keyring)
{
	struct keyring_index *links = keyring_index_locked(keyring);
	int ret;

	if (links)
		return links;

	links = kzalloc_obj(struct keyring_index);
	if (!links)
		return ERR_PTR(-ENOMEM);
	ret = rhashtable_init(&links->ht, &keyring_link_params);
	if (ret < 0) {
		kfree(links);
		return ERR_PTR(ret);
	}

	INIT_LIST_HEAD(&links->list);
	INIT_RCU_WORK(&links->rcu_work, keyring_index_free_work);
	rcu_assign_pointer(keyring->index, links);
	return links;
}

> +void __key_link(struct key *keyring, struct key *key, struct keyring_link *edit[2])
>  {
> +	struct keyring_index *index = keyring_index_locked(keyring);
> +	int ret = 0;
> +
>  	__key_get(key);
> -	assoc_array_insert_set_object(*_edit, keyring_key_to_ptr(key));
> -	assoc_array_apply_edit(*_edit);
> -	*_edit = NULL;
> +	rcu_assign_pointer(edit[0]->key, key);
> +
> +	if (edit[1]) {
> +		ret = rhashtable_replace_fast(&index->ht, &edit[1]->node,
> +					      &edit[0]->node, keyring_link_params);
> +		if (ret)
> +			goto out;

rhashtable_replace_fast() shouldn't fail here, but if it does, we should
put the reference to the key that was taken earlier in the function:

		if (WARN_ON(ret)) {
			key_put(key);
			return;
		}

(That would replace the 'out' label and its WARN_ON.)

>  void __key_link_end(struct key *keyring,
>  		    const struct keyring_index_key *index_key,
> -		    struct assoc_array_edit *edit)
> +		    struct keyring_link *edit[2])
>  	__releases(&keyring->sem)
>  	__releases(&keyring_serialise_link_lock)
>  {
> +	struct keyring_link *link = edit[0];
> +
>  	BUG_ON(index_key->type == NULL);
>  	kenter("%d,%s,", keyring->serial, index_key->type->name);
>  
> -	if (edit) {
> -		if (!edit->dead_leaf) {
> +	if (link) {
> +		if (!edit[1]) {
>  			key_payload_reserve(keyring,
>  				keyring->datalen - KEYQUOTA_LINK_BYTES);
> +			WARN_ON(rhashtable_remove_fast(&keyring_index_locked(keyring)->ht,
> +						       &link->node,
> +						       keyring_link_params));
> +			call_rcu(&link->rcu, keyring_link_free_rcu);
> +		} else {
> +			kfree(link);
>  		}
> -		assoc_array_cancel_edit(edit);
> +
> +		edit[0] = NULL;
> +		edit[1] = NULL;
>  	}

How about replacing 'struct keyring_link *edit[2]' with a named struct?
It's kind of hard to remember what [0] and [1] are.

- Eric