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 subsystem needs is just a generic key-value store, which performs well with sparse key sets. Replace assoc_array with an rhashtable-backed keyring index and remove assoc_array from the kernel. CHANGES ======= v7: - Rebased. v6: - Eric Biggers: Set .insecure_elasticity = true in keyring_link_params and drop the -EBUSY retry loop in __key_link_begin(). - Addeded Reviewed-by's from Eric Bigger and Ignat Korchagin. v5: - Eric Biggers: Include <linux/jhash.h> explicitly in keyring.c. - Eric Biggers: Document why hashing type/domain_tag pointers with SipHash and truncating the digest to 32 bits are safe. - Eric Biggers: Rework the commit message for "KEYS: Replace assoc_array with rhashtable", including behavioral and operational changes. - Retry rhashtable_insert_fast() on transient -EBUSY in __key_link_begin(). v4: - Eric Biggers: Correct the kerneldoc summary for keyring_is_empty(). - Eric Biggers: Truncate keyring_index_key hash to u32 and drop index_id. - Eric Biggers, David Howells: Use a proper struct instead of a two-element array to pass the edits. - Eric Biggers: __keyring_link(): Call key_put() in the rollback of rhashtable_replace_fast(). - Eric Biggers: Retract from using __free(kfree) in keyring_get_index(). - Eric Biggers: Reuse keyring_link_key() in keyring_obj_cmpfn(). - Eric Biggers: Document why keyring_index_free() uses queue_rcu_work(). - Eric Biggers: Fix the commit message for "KEYS: Replace assoc_array with rhashtable". v3: - Since David is away for the next week I decided to address the low hanging fruit that I reported myself. - Unified and sanitized function and variable naming and removed unnecessary asymmetry e.g., by renaming keyring_remove_all_links as keyring_index_free, 'links' as 'index' and '_edit' as 'edit'. - Flattened the implementation by refactoring out some useless wrappers and other constructs. - Addressed continuation after triggered WARN_ON() on at the three sites that I've described in my email response to the previous patch set version. - Reworked keyring_read() so that it triggers the scheduler between the iterations. - Dropped "Assisted-by: LLM" tag because checkpatch.pl told me so. v2: - Tried to address all the issues pointed out by David and Eric. Tell me if something was ignored, as that would be an unintentional mishap. - Updated and trimmed the source code comments. - For assoc_array_edit I decided to go with two-element pointer array, which shifts a bit what David suggested. - Dropped is_keyring flag. It was so obvious call so I mention it here just in case because too obvious maxes out my self-doubt ;-) - Used cleanup.h primitives where I possibly could especially in order to make fallible initializations more bug-resistant. - The already-ack'd bug fixes are included but will be dropped as soon as I've sent them over to Linus. VERSIONS ======== - v6: https://lore.kernel.org/keyrings/[email protected]/ - v5: https://lore.kernel.org/keyrings/[email protected]/ - v4: https://lore.kernel.org/keyrings/[email protected]/ - v3: https://lore.kernel.org/keyrings/[email protected]/ - v2: https://lore.kernel.org/keyrings/[email protected]/ - v1: https://lore.kernel.org/keyrings/[email protected]/ Cc: [email protected] Cc: [email protected] Cc: [email protected] Cc: [email protected] Cc: [email protected] Cc: [email protected] Cc: [email protected] Cc: [email protected] Cc: Alasdair Kergon <[email protected]> Cc: Alexei Starovoitov <[email protected]> Cc: Alex Shi <[email protected]> Cc: Andrew Morton <[email protected]> Cc: Andrii Nakryiko <[email protected]> Cc: Benjamin Marzinski <[email protected]> Cc: Daniel Borkmann <[email protected]> Cc: David Howells <[email protected]> Cc: Dongliang Mu <[email protected]> Cc: Eduard Zingerman <[email protected]> Cc: Emil Tsalapatis <[email protected]> Cc: Eric Biggers <[email protected]> Cc: Ignat Korchagin <[email protected]> Cc: Ihor Solodrai <[email protected]> Cc: James Morris <[email protected]> Cc: Jarkko Sakkinen <[email protected]> Cc: Jiri Olsa <[email protected]> Cc: Jonathan Corbet <[email protected]> Cc: Kumar Kartikeya Dwivedi <[email protected]> Cc: Martin KaFai Lau <[email protected]> Cc: Mike Snitzer <[email protected]> Cc: Mikulas Patocka <[email protected]> Cc: Paul Moore <[email protected]> Cc: Randy Dunlap <[email protected]> Cc: "Serge E. Hallyn" <[email protected]> Cc: Shuah Khan <[email protected]> Cc: Song Liu <[email protected]> Cc: "Theodore Y. Ts'o" <[email protected]> Cc: Yanteng Si <[email protected]> Cc: Yonghong Song <[email protected]> Jarkko Sakkinen (3): KEYS: Introduce keyring_is_empty() KEYS: Replace assoc_array with rhashtable lib: Remove assoc_array Documentation/core-api/assoc_array.rst | 564 ------ Documentation/core-api/index.rst | 1 - .../zh_CN/core-api/assoc_array.rst | 473 ----- .../translations/zh_CN/core-api/index.rst | 1 - drivers/md/dm-verity-verify-sig.c | 2 +- fs/verity/signature.c | 2 +- include/keys/keyring-type.h | 1 - include/linux/assoc_array.h | 88 - include/linux/assoc_array_priv.h | 178 -- include/linux/key-type.h | 1 - include/linux/key.h | 29 +- kernel/bpf/keys.c | 2 +- lib/Kconfig | 14 - lib/Makefile | 1 - lib/assoc_array.c | 1724 ----------------- security/keys/Kconfig | 1 - security/keys/internal.h | 14 +- security/keys/key.c | 22 +- security/keys/keyring.c | 994 +++++----- security/keys/request_key.c | 8 +- .../dm-verity/test-dm-verity-keyring.sh | 2 +- 21 files changed, 479 insertions(+), 3643 deletions(-) delete mode 100644 Documentation/core-api/assoc_array.rst delete mode 100644 Documentation/translations/zh_CN/core-api/assoc_array.rst delete mode 100644 include/linux/assoc_array.h delete mode 100644 include/linux/assoc_array_priv.h delete mode 100644 lib/assoc_array.c -- 2.47.3
