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 <[email protected]> > Co-developed-by: Linus Torvalds <[email protected]> > Signed-off-by: Linus Torvalds <[email protected]> > Signed-off-by: Jarkko Sakkinen <[email protected]>
Reviewed-by: Eric Biggers <[email protected]> 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
