KEYS: Replace assoc_array with rhashtable
Subsystems (11)
Jarkko Sakkinen
maintainerv13 cover KEYS: Replace assoc_array with rhashtable
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
=======
v13:
- s390/cert_store: Hold key reference across key_unlink(), and ignore -ENOENT.
- s390/cert_store: Add "s390/cert_store: Read-lock keyring semaphore in invalidate_keyring_keys()".
v12:
- Fixed Sashiko reported issues in s390/cert_store patches.
v11:
- RCU-safe iterator for keyring_read().
- Addresses s390 issues. I won't carry them for long in the series.
v10:
- No changes since the previous round. This is a sanity check round given the lack of feedback to v9. I'll apply these patch very soon, unless nothing (relevant) comes up fast.
v9:
- Replace __free(kfree) with explicit cleanup so early goto out paths cannot bypass initialization of the link pointer. Preserve kleave() tracing on all exit paths.
v8:
- Fixed broken rebase.
- Restructured __key_link_begin() a bit as a response to a minor complaint from Sashiko.
- Fixed a minor glitch in __key_link_begin(): now also first invariant invokes kleave() on failure.
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
========
- v12:
https://lore.kernel.org/keyrings/[email protected]/
- v11:
https://lore.kernel.org/keyrings/[email protected]/
- v10:
https://lore.kernel.org/keyrings/[email protected]/
- v9:
https://lore.kernel.org/keyrings/[email protected]/k
- v8:
https://lore.kernel.org/keyrings/[email protected]/
- v7:
https://lore.kernel.org/keyrings/[email protected]/
- 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]/
Jarkko Sakkinen (7):
s390/cert_store: Pin the user session keyring s390/cert_store: Return an owned reference from find_cs_keyring() s390/cert_store: Skip keys that disappeared during invalidation s390/cert_store: Read-lock keyring semaphore in
invalidate_keyring_keys()
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 - arch/s390/kernel/cert_store.c | 60 +- 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 | 1016 +++++----- security/keys/request_key.c | 8 +- .../dm-verity/test-dm-verity-keyring.sh | 2 +- 22 files changed, 541 insertions(+), 3663 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
Jarkko Sakkinen
maintainerPATCH v13 1/7 s390/cert_store: Pin the user session keyring
The user session keyring stays alive only because the session keyring is pinned by current_cred().
Pin the reference at:
1. find_cs_keyring()
2. cleanup_cs_keys()
3. create_cs_keyring()
--- arch/s390/kernel/cert_store.c | 27 +++++++++++++++++++++++---- 1 file changed, 23 insertions(+), 4 deletions(-)
arch/s390/kernel/cert_store.c +23 -4
@@ -307,7 +307,6 @@ static struct key *get_user_session_keyring(void) PTR_ERR(us_keyring_ref));return ERR_PTR (-ENOKEY ); } -key_ref_put (us_keyring_ref);return key_ref_to_ptr (us_keyring_ref); }
@@ -352,11 +351,17 @@ static int invalidate_keyring_keys(struct key *keyring)static struct key *find_cs_keyring (void ) {key_ref_t cs_keyring_ref; +struct key *us_keyring;struct key *cs_keyring; - cs_keyring_ref =keyring_search (make_key_ref (get_user_session_keyring (), true), + us_keyring =get_user_session_keyring (); +if (IS_ERR (us_keyring)) +return NULL ; + + cs_keyring_ref =keyring_search (make_key_ref (us_keyring, true), &key_type_keyring,CERT_STORE_KEYRING_NAME , false); +key_put (us_keyring);if (!IS_ERR (cs_keyring_ref)) { cs_keyring =key_ref_to_ptr (cs_keyring_ref);key_ref_put (cs_keyring_ref);
@@ -373,6 +378,7 @@ static struct key *find_cs_keyring(void)static void cleanup_cs_keys (void ) { +struct key *us_keyring;struct key *cs_keyring; cs_keyring =find_cs_keyring ();
@@ -390,20 +396,33 @@ static void cleanup_cs_keys(void)keyring_clear (cs_keyring);key_invalidate (cs_keyring);key_put (cs_keyring); -key_unlink (get_user_session_keyring (), cs_keyring); + + us_keyring =get_user_session_keyring (); +if (IS_ERR (us_keyring)) +return ; + +key_unlink (us_keyring, cs_keyring); +key_put (us_keyring); }static struct key *create_cs_keyring (void ) {static struct key *cs_keyring; +struct key *us_keyring;/* Cleanup previous cs_keyring and all associated keys if any. */ cleanup_cs_keys (); + + us_keyring =get_user_session_keyring (); +if (IS_ERR (us_keyring)) +return NULL ; + cs_keyring =keyring_alloc (CERT_STORE_KEYRING_NAME ,GLOBAL_ROOT_UID ,GLOBAL_ROOT_GID ,current_cred (), (KEY_POS_ALL & ~KEY_POS_SETATTR ) |KEY_USR_VIEW |KEY_USR_READ ,KEY_ALLOC_NOT_IN_QUOTA |KEY_ALLOC_SET_KEEP , -NULL ,get_user_session_keyring ()); +NULL , us_keyring); +key_put (us_keyring);if (IS_ERR (cs_keyring)) {pr_dbf_msg ("Can't allocate cert_store keyring" );return NULL ;
Signature · 1 line
2.47.3
[email protected]
AI reviewRe: [PATCH v13 1/7] s390/cert_store: Pin the user session keyring
Sashiko has reviewed this patch and found no issues.
Quoted 5 lines
The user session keyring stays alive only because the session keyring is pinned by
current_cred().Pin the reference at:
Quoted 8 lines
1.
find_cs_keyring()
2.cleanup_cs_keys()
3.create_cs_keyring()Cc David Howells <[email protected]>Cc [email protected] # v6.1+Fixes 8cf57d7217c3 ("s390: add support for user-defined certificates")Signed-off-by Jarkko Sakkinen <[email protected]>
Sashiko has reviewed this patch and found no issues.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
Jarkko Sakkinen
maintainerPATCH v13 2/7 s390/cert_store: Return an owned reference from find_cs_keyring()
In reply to Jarkko SakkinenReturn an owned reference from find_cs_keyring() so that it will not get dropped.
--- arch/s390/kernel/cert_store.c | 21 +++++++++------------ 1 file changed, 9 insertions(+), 12 deletions(-)
arch/s390/kernel/cert_store.c +9 -12
@@ -362,17 +362,13 @@ static struct key *find_cs_keyring(void) &key_type_keyring,CERT_STORE_KEYRING_NAME , false);key_put (us_keyring); -if (!IS_ERR (cs_keyring_ref)) { - cs_keyring =key_ref_to_ptr (cs_keyring_ref); -key_ref_put (cs_keyring_ref); - goto found; - } +if (!IS_ERR (cs_keyring_ref)) +return key_ref_to_ptr (cs_keyring_ref); +/* Search default locations: thread, process, session keyrings */ cs_keyring =request_key (&key_type_keyring,CERT_STORE_KEYRING_NAME ,NULL );if (IS_ERR (cs_keyring))return NULL ; -key_put (cs_keyring); -found:return cs_keyring; }
@@ -395,14 +391,16 @@ static void cleanup_cs_keys(void)keyring_clear (cs_keyring);key_invalidate (cs_keyring); -key_put (cs_keyring); us_keyring =get_user_session_keyring (); -if (IS_ERR (us_keyring)) +if (IS_ERR (us_keyring)) { +key_put (cs_keyring);return ; + }key_unlink (us_keyring, cs_keyring);key_put (us_keyring); +key_put (cs_keyring); }static struct key *create_cs_keyring (void )
@@ -729,13 +727,12 @@ static int fill_cs_keyring(void) goto cleanup_keys; rc =add_certificates_to_keyring (vcssb, cs_keyring); +key_put (cs_keyring);if (rc) - goto cleanup_cs_keyring; + goto cleanup_keys; goto out; -cleanup_cs_keyring: -key_put (cs_keyring); cleanup_keys:cleanup_cs_keys (); out:
Signature · 1 line
2.47.3
[email protected]
AI reviewRe: [PATCH v13 2/7] s390/cert_store: Return an owned reference from find_cs_keyring()
Sashiko has reviewed this patch and found no issues.
Quoted 7 lines
Return an owned reference from
find_cs_keyring()so that it will not get dropped.Cc David Howells <[email protected]>Cc [email protected] # v6.6+Fixes 8cf57d7217c3 ("s390: add support for user-defined certificates")Signed-off-by Jarkko Sakkinen <[email protected]>
Sashiko has reviewed this patch and found no issues.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
Jarkko Sakkinen
maintainerPATCH v13 3/7 s390/cert_store: Skip keys that disappeared during invalidation
In reply to Jarkko Sakkinenkey_lookup() can return ERR_PTR(-ENOKEY) for an unlinked key. Skip such keys instead.
--- arch/s390/kernel/cert_store.c | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-)
arch/s390/kernel/cert_store.c +9 -1
@@ -331,17 +331,25 @@ static int invalidate_keyring_keys(struct key *keyring) goto out; } + rc =0 ; +for (key_index =0 ; key_index < num_keys; key_index++) { current_key =key_lookup (key_array[key_index]); +if (IS_ERR (current_key)) +continue ; +pr_dbf_msg ("Invalidating key %08x" , current_key->serial);key_invalidate (current_key); -key_put (current_key); rc =key_unlink (keyring, current_key); +if (rc == -ENOENT ) + rc =0 ;if (rc) {pr_dbf_msg ("Couldn't unlink key %08x: %d" , current_key->serial, rc); +key_put (current_key);break ; } +key_put (current_key); } out:kfree (key_array);
Signature · 1 line
2.47.3
[email protected]
AI reviewRe: [PATCH v13 3/7] s390/cert_store: Skip keys that disappeared during invalidation
Sashiko has reviewed this patch and found no issues.
Quoted 7 lines
key_lookup()can returnERR_PTR(-ENOKEY)for an unlinked key. Skip such keys instead.Cc David Howells <[email protected]>Cc [email protected] # v6.6+Fixes 8cf57d7217c3 ("s390: add support for user-defined certificates")Signed-off-by Jarkko Sakkinen <[email protected]>
Sashiko has reviewed this patch and found no issues.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=3
Jarkko Sakkinen
maintainerPATCH v13 4/7 s390/cert_store: Read-lock keyring semaphore in invalidate_keyring_keys()
In reply to Jarkko Sakkinenkey_type->read() requires the caller to hold key->sem for reading. Acquire keyring->sem across the two key_type_keyring.read() calls in invalidate_keyring_keys() so the keyring cannot be modified between the size query and the payload read.
--- arch/s390/kernel/cert_store.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
arch/s390/kernel/cert_store.c +5 -1
@@ -319,13 +319,17 @@ static int invalidate_keyring_keys(struct key *keyring)struct key *current_key;int rc; +down_read (&keyring->sem); keyring_payload_len = key_type_keyring.read (keyring,NULL ,0 ); num_keys = keyring_payload_len /sizeof (key_serial_t); key_array =kzalloc_objs (key_serial_t, num_keys); -if (!key_array) +if (!key_array) { +up_read (&keyring->sem);return -ENOMEM ; + } rc = key_type_keyring.read (keyring, (char *)key_array, keyring_payload_len); +up_read (&keyring->sem);if (rc != keyring_payload_len) {pr_dbf_msg ("Couldn't read keyring payload" ); goto out;
Signature · 1 line
2.47.3
[email protected]
AI reviewRe: [PATCH v13 4/7] s390/cert_store: Read-lock keyring semaphore in invalidate_keyring_keys()
Sashiko has reviewed this patch and found no issues.
Quoted 9 lines
key_type->read()requires the caller to holdkey->semfor reading. Acquirekeyring->semacross the twokey_type_keyring.read()calls ininvalidate_keyring_keys()so the keyring cannot be modified between the size query and the payload read.Cc David Howells <[email protected]>Cc [email protected] # v6.6+Fixes 8cf57d7217c3 ("s390: add support for user-defined certificates")Signed-off-by Jarkko Sakkinen <[email protected]>
Sashiko has reviewed this patch and found no issues.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=4
Jarkko Sakkinen
maintainerPATCH v13 5/7 KEYS: Introduce keyring_is_empty()
In reply to Jarkko SakkinenIntroduce keyring_is_empty() in order to decouple for BPF, dm-verity and fs-verity how keyring internally manages the keys.
--- drivers/md/dm-verity-verify-sig.c | 2 +- fs/verity/signature.c | 2 +- include/linux/key.h | 1 + kernel/bpf/keys.c | 2 +- security/keys/keyring.c | 10 ++++++++++ .../selftests/dm-verity/test-dm-verity-keyring.sh | 2 +- 6 files changed, 15 insertions(+), 4 deletions(-)
drivers/md/dm-verity-verify-sig.c +1 -1
@@ -153,7 +153,7 @@ int verity_verify_root_hash(const void *root_hash, size_t root_hash_len,if (ret != -ENOKEY && ret != -EKEYREJECTED )return ret; -if (dm_verity_keyring->keys.nr_leaves_on_tree && +if (!keyring_is_empty (dm_verity_keyring) && dm_verity_keyring->restrict_link) ret = verify_pkcs7_signature(root_hash, root_hash_len, sig_data, sig_len,
fs/verity/signature.c +1 -1
@@ -70,7 +70,7 @@ int fsverity_verify_signature(const struct fsverity_info *vi,return 0 ; } -if (fsverity_keyring->keys.nr_leaves_on_tree ==0 ) { +if (keyring_is_empty (fsverity_keyring)) {/* * The ".fs-verity" keyring is empty, due to builtin signatures * being supported by the kernel but not actually being used.
include/linux/key.h +1 -0
@@ -439,6 +439,7 @@ extern int restrict_link_reject(struct key *keyring, struct key *restriction_key);extern int keyring_clear (struct key *keyring); +bool keyring_is_empty (const struct key *keyring); extern key_ref_t keyring_search(key_ref_t keyring, struct key_type *type,
kernel/bpf/keys.c +1 -1
@@ -29,7 +29,7 @@ struct bpf_key *bpf_lookup_keyring(void)if (!bpf_keyring)return NULL ; -if (!READ_ONCE (bpf_keyring->keys.nr_leaves_on_tree) || +if (keyring_is_empty (bpf_keyring) || !READ_ONCE (bpf_keyring->restrict_link))return NULL ;
security/keys/keyring.c +10 -0
@@ -443,6 +443,16 @@ static void keyring_destroy(struct key *keyring)assoc_array_destroy (&keyring->keys, &keyring_assoc_array_ops); } +/** +* keyring_is_empty - Check whether a keyring is empty +* @keyring: The keyring to check. +*/ +bool keyring_is_empty (const struct key *keyring) +{ +return READ_ONCE (keyring->keys.nr_leaves_on_tree) ==0 ; +} +EXPORT_SYMBOL (keyring_is_empty); +/* * Describe a keyring for /proc. */
tools/testing/selftests/dm-verity/test-dm-verity-keyring.sh +1 -1
@@ -746,7 +746,7 @@ test_keyring_inactive_when_empty() { log_info "TEST: Verify dm-verity keyring is inactive when sealed empty" # When keyring_unsealed=0, the keyring is sealed immediately while empty - # This means it should NOT be used for verification (nr_leaves_on_tree=0) + # An empty keyring should NOT be used for verification. log_info "Keyring state (should be empty and sealed):" list_keyring_keys
Signature · 1 line
2.47.3
[email protected]
AI reviewRe: [PATCH v13 5/7] KEYS: Introduce keyring_is_empty()
Sashiko has reviewed this patch and found no issues.
Quoted 6 lines
Introduce
keyring_is_empty()in order to decouple for BPF, dm-verity and fs-verity how keyring internally manages the keys.Reviewed-by Eric Biggers <[email protected]>Reviewed-by Ignat Korchagin <[email protected]>Signed-off-by Jarkko Sakkinen <[email protected]>
Sashiko has reviewed this patch and found no issues.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=5
Jarkko Sakkinen
maintainerPATCH v13 6/7 KEYS: Replace assoc_array with rhashtable
In reply to Jarkko SakkinenThe 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.
--- include/keys/keyring-type.h | 1 - include/linux/key-type.h | 1 - include/linux/key.h | 28 +- security/keys/Kconfig | 1 - security/keys/internal.h | 14 +- security/keys/key.c | 22 +- security/keys/keyring.c | 1008 ++++++++++++++++------------------- security/keys/request_key.c | 8 +- 8 files changed, 483 insertions(+), 600 deletions(-)
include/keys/keyring-type.h +0 -1
@@ -9,6 +9,5 @@#define _KEYS_KEYRING_TYPE_H#include <linux/key.h> -#include <linux/assoc_array.h> #endif /* _KEYS_KEYRING_TYPE_H */
include/linux/key-type.h +0 -1
@@ -161,7 +161,6 @@ struct key_type { const void *in, const void *in2);/* internal fields */ -atomic64_t index_id;/* Opaque keyring index ID */ struct list_head link;/* link in types list */ struct lock_class_key lock_class;/* key->sem lock class */ } __randomize_layout;
include/linux/key.h +6 -22
@@ -17,7 +17,6 @@#include <linux/sysctl.h> #include <linux/rwsem.h> #include <linux/atomic.h> -#include <linux/assoc_array.h> #include <linux/refcount.h> #include <linux/time64.h>
@@ -107,34 +106,21 @@ struct key_owner;struct key_tag ;struct keyring_list ;struct keyring_name ; +struct keyring_index ;struct key_tag {struct rcu_head rcu; -atomic64_t index_id;/* Opaque keyring index ID */ refcount_t usage;bool removed;/* T when subject removed */ };struct keyring_index_key {/* [!] If this structure is altered, the union in struct key must change too! */ -unsigned long hash;/* Hash value */ -union { -struct { -#ifdef __LITTLE_ENDIAN/* Put desc_len at the LSB of x */ -u16 desc_len; -char desc[sizeof (long ) -2 ];/* First few chars of description */ -#else -char desc[sizeof (long ) -2 ];/* First few chars of description */ -u16 desc_len; -#endif - }; -unsigned long x; - }; +u32 hash;/* Hash value */ +unsigned int desc_len;struct key_type *type;struct key_tag *domain_tag;/* Domain of operation */ const char *description; -u64 type_id;/* Cached index IDs */ -u64 domain_id; };union key_payload {
@@ -252,13 +238,11 @@ struct key {union {struct keyring_index_key index_key;struct { -unsigned long hash; -unsigned long len_desc; +u32 hash; +unsigned int desc_len;struct key_type *type;/* type of key */ struct key_tag *domain_tag;/* Domain of operation */ char *description; -u64 type_id; -u64 domain_id; }; };
@@ -271,7 +255,7 @@ struct key {struct {/* Keyring bits */ struct list_head name_link; -struct assoc_array keys; +struct keyring_index __rcu *index; }; };
security/keys/Kconfig +0 -1
@@ -5,7 +5,6 @@ menuconfig KEYS bool "Enable access key retention support" - select ASSOCIATIVE_ARRAY help This option provides support for retaining authentication tokens and access keys in the kernel.
security/keys/internal.h +10 -4
@@ -21,6 +21,12 @@#include <linux/vmalloc.h> struct iovec ; +struct keyring_link ; + +struct keyring_edit { +struct keyring_link *new; +struct keyring_link *old; +};#ifdef __KDEBUG#define kenter (FMT , ...) \
@@ -98,13 +104,13 @@ extern int __key_move_lock(struct key *l_keyring, struct key *u_keyring, const struct keyring_index_key *index_key);extern int __key_link_begin (struct key *keyring,const struct keyring_index_key *index_key, -struct assoc_array_edit **_edit); +struct keyring_edit *edit);extern int __key_link_check_live_key (struct key *keyring,struct key *key);extern void __key_link (struct key *keyring,struct key *key, -struct assoc_array_edit **_edit); +struct keyring_edit *edit);extern void __key_link_end (struct key *keyring,const struct keyring_index_key *index_key, -struct assoc_array_edit *edit); +struct keyring_edit *edit);extern key_ref_t find_key_to_update (key_ref_t keyring_ref,const struct keyring_index_key *index_key);
@@ -122,7 +128,7 @@ struct keyring_search_context {#define KEYRING_SEARCH_SKIP_EXPIRED 0x0020/* Ignore expired keys (intention to replace) */ #define KEYRING_SEARCH_RECURSE 0x0040/* Search child keyrings also */ -int (*iterator)(const void *object,void *iterator_data); +int (*iterator)(const struct key *key,void *iterator_data);/* Internal stuff */ int skipped_ret;
security/keys/key.c +11 -11
@@ -430,7 +430,7 @@ static int __key_instantiate_and_link(struct key *key,struct key_preparsed_payload *prep, struct key *keyring, struct key *authkey, - struct assoc_array_edit **_edit) + struct keyring_edit *edit) { int ret, awaken;
@@ -461,7 +461,7 @@ static int __key_instantiate_and_link(struct key *key,if (test_bit (KEY_FLAG_KEEP , &keyring->flags))set_bit (KEY_FLAG_KEEP , &key->flags); -__key_link (keyring, key, _edit); +__key_link (keyring, key, edit); }/* disable the authorisation key */
@@ -505,7 +505,7 @@ int key_instantiate_and_link(struct key *key, struct key *authkey) {struct key_preparsed_payload prep; -struct assoc_array_edit *edit =NULL ; +struct keyring_edit edit = {};int ret;memset (&prep,0 ,sizeof (prep));
@@ -543,7 +543,7 @@ int key_instantiate_and_link(struct key *key, error_link_end:if (keyring) -__key_link_end (keyring, &key->index_key, edit); +__key_link_end (keyring, &key->index_key, &edit); error:if (key->type->preparse)
@@ -580,7 +580,7 @@ int key_reject_and_link(struct key *key,struct key *keyring, struct key *authkey) { - struct assoc_array_edit *edit = NULL; + struct keyring_edit edit = {};int ret, awaken, link_ret =0 ;key_check (key);
@@ -599,12 +599,12 @@ int key_reject_and_link(struct key *key,* concurrent restriction install. */ if (keyring->restrict_link) { -__key_link_end (keyring, &key->index_key, edit); +__key_link_end (keyring, &key->index_key, &edit);return -EPERM ; } link_ret =__key_link_begin (keyring, &key->index_key, &edit);if (link_ret <0 ) -__key_link_end (keyring, &key->index_key, edit); +__key_link_end (keyring, &key->index_key, &edit); } }
@@ -635,7 +635,7 @@ int key_reject_and_link(struct key *key,mutex_unlock (&key_construction_mutex);if (keyring && link_ret ==0 ) -__key_link_end (keyring, &key->index_key, edit); +__key_link_end (keyring, &key->index_key, &edit);/* wake up anyone waiting for a key to be constructed */ if (awaken)
@@ -825,7 +825,7 @@ static key_ref_t __key_create_or_update(key_ref_t keyring_ref, .description = description, };struct key_preparsed_payload prep; -struct assoc_array_edit *edit =NULL ; +struct keyring_edit edit = {};const struct cred *cred =current_cred ();struct key *keyring, *key =NULL ;key_ref_t key_ref;
@@ -966,7 +966,7 @@ static key_ref_t __key_create_or_update(key_ref_t keyring_ref, key_ref =make_key_ref (key,is_key_possessed (keyring_ref)); error_link_end: -__key_link_end (keyring, &index_key, edit); +__key_link_end (keyring, &index_key, &edit); error_free_prep:if (index_key.type->preparse) index_key.type->free_preparse (&prep);
@@ -979,7 +979,7 @@ static key_ref_t __key_create_or_update(key_ref_t keyring_ref,/* we found a matching key, so we're going to try to update it * - we can drop the locks first as we have the key pinned */ -__key_link_end (keyring, &index_key, edit); +__key_link_end (keyring, &index_key, &edit); key =key_ref_to_ptr (key_ref);if (test_bit (KEY_FLAG_USER_CONSTRUCT , &key->flags)) {
security/keys/keyring.c +452 -556
1,393 lines not on this page · raw message
security/keys/request_key.c +4 -4
@@ -372,7 +372,7 @@ static int construct_alloc_key(struct keyring_search_context *ctx,struct key_user *user, struct key **_key) { - struct assoc_array_edit *edit = NULL; + struct keyring_edit edit = {};struct key *key;key_perm_t perm;key_ref_t key_ref;
@@ -433,7 +433,7 @@ static int construct_alloc_key(struct keyring_search_context *ctx,mutex_unlock (&key_construction_mutex);if (dest_keyring) -__key_link_end (dest_keyring, &key->index_key, edit); +__key_link_end (dest_keyring, &key->index_key, &edit);mutex_unlock (&user->cons_lock); *_key = key;kleave (" = 0 [%d]" ,key_serial (key));
@@ -452,7 +452,7 @@ static int construct_alloc_key(struct keyring_search_context *ctx, ret =__key_link_check_live_key (dest_keyring, key);if (ret ==0 )__key_link (dest_keyring, key, &edit); -__key_link_end (dest_keyring, &key->index_key, edit); +__key_link_end (dest_keyring, &key->index_key, &edit);if (ret <0 ) goto link_check_failed; }
@@ -470,7 +470,7 @@ static int construct_alloc_key(struct keyring_search_context *ctx, link_alloc_failed:mutex_unlock (&key_construction_mutex); link_alloc_failed_unlocked: -__key_link_end (dest_keyring, &key->index_key, edit); +__key_link_end (dest_keyring, &key->index_key, &edit); link_lock_failed:mutex_unlock (&user->cons_lock);key_put (key);
Signature · 1 line
2.47.3
[email protected]
AI reviewSashiko has reviewed this patch and found no issues.
Quoted 15 lines
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_arrayin struct key with structkeyring_index:-
keyring_index: holds an rhashtable for direct lookups, an RCU-protected list ofkeyring_linkentries for stable walks, the active link count, and anrcu_workitem for deferred teardown.
Quoted 6 lines
[ ... ]Suggested-by Eric Biggers <[email protected]>Co-developed-by Linus Torvalds <[email protected]>Signed-off-by Linus Torvalds <[email protected]>Reviewed-by Eric Biggers <[email protected]>Signed-off-by Jarkko Sakkinen <[email protected]>
Sashiko has reviewed this patch and found no issues.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=6
[email protected]
AI reviewTL;DR: Comment only, not a bug today: the new keyring_read() comment says no semaphore is needed and concurrent changes are possible, but the caller's semaphore prevents that. Suggests rewording it.
Quoted 1 line
KEYS: Replace
assoc_arraywith rhashtable
TL;DR: Comment only, not a bug today: the new keyring_read() comment says no semaphore is needed and concurrent changes are possible, but the caller's semaphore prevents that. Suggests rewording it.
Quoted 3 lines
security/keys/keyring.c +0
-0
[ ... ]
Quoted 12 lines
/*
* Read a list of key IDs from the keyring's contents in binary form *
- * The keyring's semaphore is read-locked by the caller. This prevents someone
- * from modifying it under us - which could cause us to read key IDs multiple
- * times.
+ * The walk is RCU-protected, so the keyring's semaphore is not required. A
+ * keyring modified concurrently may list a key twice or miss one, but it can
+ * never have a link freed under the walk.
*/
static long keyring_read(const struct key *keyring,
char *buffer,size_tbuflen)
[ ... ]
security/keys/keyring.c static long keyring_read(const struct key *keyring, · line 470
Quoted 3 lines
security/keys/keyring.c +2
-0+ ret =keyring_iterate (keyring, keyring_read_iterator, &ctx); +if (ret <0 )return ret;
[ ... ]
This isn't a bug today, but the new comment looks inaccurate. It says the keyring's semaphore is not required and that a concurrent modification may list a key twice or miss one.
keyring_read() walks the list under RCU, but the length it returns is computed separately afterwards:
ret = keyring_iterate(keyring, keyring_read_iterator, &ctx);
...
ret = keyring_nr_links(keyring) * sizeof(key_serial_t);keyctl_read_key() allocates key_data with kvmalloc(), which is not zeroed, and when the returned length is <= buflen it does:
ret = __keyctl_read_key(key, key_data, key_data_len);
if (ret <= 0 || ret > buflen)
break;
...
if (copy_to_user(buffer, key_data, ret))If a link were added between the walk and keyring_nr_links(), ret would cover more entries than were written, and the extra uninitialised bytes would be copied to userspace.
Today this can't happen, because __keyctl_read_key() does down_read(&key->sem) (as does the s390 invalidate_keyring_keys()), and every writer of index->list and index->nr (__key_link_lock(), __key_move_lock(), __key_unlink_lock(), keyring_clear(), keyring_gc(), and key_revoke() via keyring_revoke()) holds the semaphore for write. So the concurrent modification described by the comment does not occur.
Could the comment instead say that the caller holds the keyring's semaphore, which keeps the list and the link count stable across the walk and the length calculation, with RCU only keeping the walk itself memory-safe?
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/43634583011
Jarkko Sakkinen
maintainerQuoted 7 lines · On Sat, Nov 14, 2026 at 08:24:27PM +0000, [email protected] wrote:
Quoted 3 lines
+ * The walk is RCU-protected, so the keyring's semaphore is not required. A
+ * keyring modified concurrently may list a key twice or miss one, but it can
+ * never have a link freed under the walk.Could the comment instead say that the caller holds the keyring's semaphore, which keeps the list and the link count stable across the walk and the length calculation, with RCU only keeping the walk itself memory-safe?
If I did not miss anything, this is the only remark.
Hmm...
I think this is enough prose to capture the preconditions:
/* * The list and link count are stable across the walk as the caller * holds keyring->sem. */
Br, Jarkko
Jarkko Sakkinen
maintainerPATCH v13 7/7 lib: Remove assoc_array
In reply to Jarkko SakkinenAs assoc_array has no longer in-kernel users, remove assoc_array implementation, includes and documentation.
--- 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 - include/linux/assoc_array.h | 88 - include/linux/assoc_array_priv.h | 178 -- lib/Kconfig | 14 - lib/Makefile | 1 - lib/assoc_array.c | 1724 ----------------- 9 files changed, 3044 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
Documentation/core-api/assoc_array.rst deleted +0 -564
@@ -1,564 +0,0 @@ -======================================== -Generic Associative Array Implementation -======================================== - -Overview -======== - -This associative array implementation is an object container with the following -properties: - -1. Objects are opaque pointers. The implementation does not care where they - point (if anywhere) or what they point to (if anything). - - .. note:: - - Pointers to objects _must_ be zero in the least significant bit. - -2. Objects do not need to contain linkage blocks for use by the array. This - permits an object to be located in multiple arrays simultaneously. - Rather, the array is made up of metadata blocks that point to objects. - -3. Objects require index keys to locate them within the array. - -4. Index keys must be unique. Inserting an object with the same key as one - already in the array will replace the old object. - -5. Index keys can be of any length and can be of different lengths. - -6. Index keys should encode the length early on, before any variation due to - length is seen. - -7. Index keys can include a hash to scatter objects throughout the array. - -8. The array can iterated over. The objects will not necessarily come out in - key order. - -9. The array can be iterated over while it is being modified, provided the - RCU readlock is being held by the iterator. Note, however, under these - circumstances, some objects may be seen more than once. If this is a - problem, the iterator should lock against modification. Objects will not - be missed, however, unless deleted. - -10. Objects in the array can be looked up by means of their index key. - -11. Objects can be looked up while the array is being modified, provided the - RCU readlock is being held by the thread doing the look up. - -The implementation uses a tree of 16-pointer nodes internally that are indexed -on each level by nibbles from the index key in the same manner as in a radix -tree. To improve memory efficiency, shortcuts can be emplaced to skip over -what would otherwise be a series of single-occupancy nodes. Further, nodes -pack leaf object pointers into spare space in the node rather than making an -extra branch until as such time an object needs to be added to a full node. - - -The Public API -============== - -The public API can be found in ``<linux/assoc_array.h>``. The associative -array is rooted on the following structure:: - - struct assoc_array { - ... - }; - -The code is selected by enabling ``CONFIG_ASSOCIATIVE_ARRAY`` with:: - - ./script/config -e ASSOCIATIVE_ARRAY - - -Edit Script ------------ - -The insertion and deletion functions produce an 'edit script' that can later be -applied to effect the changes without risking ``ENOMEM``. This retains the -preallocated metadata blocks that will be installed in the internal tree and -keeps track of the metadata blocks that will be removed from the tree when the -script is applied. - -This is also used to keep track of dead blocks and dead objects after the -script has been applied so that they can be freed later. The freeing is done -after an RCU grace period has passed - thus allowing access functions to -proceed under the RCU read lock. - -The script appears as outside of the API as a pointer of the type:: - - struct assoc_array_edit; - -There are two functions for dealing with the script: - -1. Apply an edit script:: - - void assoc_array_apply_edit(struct assoc_array_edit *edit); - - This will perform the edit functions, interpolating various write barriers - to permit accesses under the RCU read lock to continue. The edit script - will then be passed to ``call_rcu()`` to free it and any dead stuff it - points to. - -2. Cancel an edit script:: - - void assoc_array_cancel_edit(struct assoc_array_edit *edit); - - This frees the edit script and all preallocated memory immediately. If - this was for insertion, the new object is *not* released by this function, - but must rather be released by the caller. - -These functions are guaranteed not to fail. - - -Operations Table ----------------- - -Various functions take a table of operations:: - - struct assoc_array_ops { - ... - }; - -This points to a number of methods, all of which need to be provided: - -1. Get a chunk of index key from caller data:: - - unsigned long (*get_key_chunk)(const void *index_key, int level); - - This should return a chunk of caller-supplied index key starting at the - *bit* position given by the level argument. The level argument will be a - multiple of ``ASSOC_ARRAY_KEY_CHUNK_SIZE`` and the function should return - ``ASSOC_ARRAY_KEY_CHUNK_SIZE bits``. No error is possible. - - -2. Get a chunk of an object's index key:: - - unsigned long (*get_object_key_chunk)(const void *object, int level); - - As the previous function, but gets its data from an object in the array - rather than from a caller-supplied index key. - - -3. See if this is the object we're looking for:: - - bool (*compare_object)(const void *object, const void *index_key); - - Compare the object against an index key and return ``true`` if it matches - and ``false`` if it doesn't. - - -4. Diff the index keys of two objects:: - - int (*diff_objects)(const void *object, const void *index_key); - - Return the bit position at which the index key of the specified object - differs from the given index key or -1 if they are the same. - - -5. Free an object:: - - void (*free_object)(void *object); - - Free the specified object. Note that this may be called an RCU grace period - after ``assoc_array_apply_edit()`` was called, so ``synchronize_rcu()`` may - be necessary on module unloading. - - -Manipulation Functions ----------------------- - -There are a number of functions for manipulating an associative array: - -1. Initialise an associative array:: - - void assoc_array_init(struct assoc_array *array); - - This initialises the base structure for an associative array. It can't fail. - - -2. Insert/replace an object in an associative array:: - - struct assoc_array_edit * - assoc_array_insert(struct assoc_array *array, - const struct assoc_array_ops *ops, - const void *index_key, - void *object); - - This inserts the given object into the array. Note that the least - significant bit of the pointer must be zero as it's used to type-mark - pointers internally. - - If an object already exists for that key then it will be replaced with the - new object and the old one will be freed automatically. - - The ``index_key`` argument should hold index key information and is - passed to the methods in the ops table when they are called. - - This function makes no alteration to the array itself, but rather returns - an edit script that must be applied. ``-ENOMEM`` is returned in the case of - an out-of-memory error. - - The caller should lock exclusively against other modifiers of the array. - - -3. Delete an object from an associative array:: - - struct assoc_array_edit * - assoc_array_delete(struct assoc_array *array, - const struct assoc_array_ops *ops, - const void *index_key); - - This deletes an object that matches the specified data from the array. - - The ``index_key`` argument should hold index key information and is - passed to the methods in the ops table when they are called. - - This function makes no alteration to the array itself, but rather returns - an edit script that must be applied. ``-ENOMEM`` is returned in the case of - an out-of-memory error. ``NULL`` will be returned if the specified object - is not found within the array. - -The caller should lock exclusively against other modifiers of the array. - - -4. Delete all objects from an associative array:: - - struct assoc_array_edit * - assoc_array_clear(struct assoc_array *array, - const struct assoc_array_ops *ops); - - This deletes all the objects from an associative array and leaves it - completely empty. - - This function makes no alteration to the array itself, but rather returns - an edit script that must be applied. ``-ENOMEM`` is returned in the case of - an out-of-memory error. - - The caller should lock exclusively against other modifiers of the array. - - -5. Destroy an associative array, deleting all objects:: - - void assoc_array_destroy(struct assoc_array *array, - const struct assoc_array_ops *ops); - - This destroys the contents of the associative array and leaves it - completely empty. It is not permitted for another thread to be traversing - the array under the RCU read lock at the same time as this function is - destroying it as no RCU deferral is performed on memory release - - something that would require memory to be allocated. - - The caller should lock exclusively against other modifiers and accessors - of the array. - - -6. Garbage collect an associative array:: - - int assoc_array_gc(struct assoc_array *array, - const struct assoc_array_ops *ops, - bool (*iterator)(void *object, void *iterator_data), - void *iterator_data); - - This iterates over the objects in an associative array and passes each one - to ``iterator()``. If ``iterator()`` returns ``true``, the object is kept. - If it returns ``false``, the object will be freed. If the ``iterator()`` - function returns ``true``, it must perform any appropriate refcount - incrementing on the object before returning. - - The internal tree will be packed down if possible as part of the iteration - to reduce the number of nodes in it. - - The ``iterator_data`` is passed directly to ``iterator()`` and is otherwise - ignored by the function. - - The function will return ``0`` if successful and ``-ENOMEM`` if there wasn't - enough memory. - - It is possible for other threads to iterate over or search the array under - the RCU read lock while this function is in progress. The caller should - lock exclusively against other modifiers of the array. - - -Access Functions ----------------- - -There are two functions for accessing an associative array: - -1. Iterate over all the objects in an associative array:: - - int assoc_array_iterate(const struct assoc_array *array, - int (*iterator)(const void *object, - void *iterator_data), - void *iterator_data); - - This passes each object in the array to the iterator callback function. - ``iterator_data`` is private data for that function. - - This may be used on an array at the same time as the array is being - modified, provided the RCU read lock is held. Under such circumstances, - it is possible for the iteration function to see some objects twice. If - this is a problem, then modification should be locked against. The - iteration algorithm should not, however, miss any objects. - - The function will return ``0`` if no objects were in the array or else it - will return the result of the last iterator function called. Iteration - stops immediately if any call to the iteration function results in a - non-zero return. - - -2. Find an object in an associative array:: - - void *assoc_array_find(const struct assoc_array *array, - const struct assoc_array_ops *ops, - const void *index_key); - - This walks through the array's internal tree directly to the object - specified by the index key. - - This may be used on an array at the same time as the array is being - modified, provided the RCU read lock is held. - - The function will return the object if found (and set ``*_type`` to the - object type) or will return ``NULL`` if the object was not found. - - -Index Key Form --------------- - -The index key can be of any form, but since the algorithms aren't told how long -the key is, it is strongly recommended that the index key includes its length -very early on before any variation due to the length would have an effect on -comparisons. - -This will cause leaves with different length keys to scatter away from each -other - and those with the same length keys to cluster together. - -It is also recommended that the index key begin with a hash of the rest of the -key to maximise scattering throughout keyspace. - -The better the scattering, the wider and lower the internal tree will be. - -Poor scattering isn't too much of a problem as there are shortcuts and nodes -can contain mixtures of leaves and metadata pointers. - -The index key is read in chunks of machine word. Each chunk is subdivided into -one nibble (4 bits) per level, so on a 32-bit CPU this is good for 8 levels and -on a 64-bit CPU, 16 levels. Unless the scattering is really poor, it is -unlikely that more than one word of any particular index key will have to be -used. - - -Internal Workings -================= - -The associative array data structure has an internal tree. This tree is -constructed of two types of metadata blocks: nodes and shortcuts. - -A node is an array of slots. Each slot can contain one of four things: - -* A NULL pointer, indicating that the slot is empty. -* A pointer to an object (a leaf). -* A pointer to a node at the next level. -* A pointer to a shortcut. - - -Basic Internal Tree Layout --------------------------- - -Ignoring shortcuts for the moment, the nodes form a multilevel tree. The index -key space is strictly subdivided by the nodes in the tree and nodes occur on -fixed levels. For example:: - - Level: 0 1 2 3 - =============== =============== =============== =============== - NODE D - NODE B NODE C +------>+---+ - +------>+---+ +------>+---+ | | 0 | - NODE A | | 0 | | | 0 | | +---+ - +---+ | +---+ | +---+ | : : - | 0 | | : : | : : | +---+ - +---+ | +---+ | +---+ | | f | - | 1 |---+ | 3 |---+ | 7 |---+ +---+ - +---+ +---+ +---+ - : : : : | 8 |---+ - +---+ +---+ +---+ | NODE E - | e |---+ | f | : : +------>+---+ - +---+ | +---+ +---+ | 0 | - | f | | | f | +---+ - +---+ | +---+ : : - | NODE F +---+ - +------>+---+ | f | - | 0 | NODE G +---+ - +---+ +------>+---+ - : : | | 0 | - +---+ | +---+ - | 6 |---+ : : - +---+ +---+ - : : | f | - +---+ +---+ - | f | - +---+ - -In the above example, there are 7 nodes (A-G), each with 16 slots (0-f). -Assuming no other meta data nodes in the tree, the key space is divided -thusly: - - =========== ==== - KEY PREFIX NODE - =========== ==== - 137* D - 138* E - 13[0-69-f]* C - 1[0-24-f]* B - e6* G - e[0-57-f]* F - [02-df]* A - =========== ==== - -So, for instance, keys with the following example index keys will be found in -the appropriate nodes: - - =============== ======= ==== - INDEX KEY PREFIX NODE - =============== ======= ==== - 13694892892489 13 C - 13795289025897 137 D - 13889dde88793 138 E - 138bbb89003093 138 E - 1394879524789 12 C - 1458952489 1 B - 9431809de993ba \- A - b4542910809cd \- A - e5284310def98 e F - e68428974237 e6 G - e7fffcbd443 e F - f3842239082 \- A - =============== ======= ==== - -To save memory, if a node can hold all the leaves in its portion of keyspace, -then the node will have all those leaves in it and will not have any metadata -pointers - even if some of those leaves would like to be in the same slot. - -A node can contain a heterogeneous mix of leaves and metadata pointers. -Metadata pointers must be in the slots that match their subdivisions of key -space. The leaves can be in any slot not occupied by a metadata pointer. It -is guaranteed that none of the leaves in a node will match a slot occupied by a -metadata pointer. If the metadata pointer is there, any leaf whose key matches -the metadata key prefix must be in the subtree that the metadata pointer points -to. - -In the above example list of index keys, node A will contain: - - ==== =============== ================== - SLOT CONTENT INDEX KEY (PREFIX) - ==== =============== ================== - 1 PTR TO NODE B 1* - any LEAF 9431809de993ba - any LEAF b4542910809cd - e PTR TO NODE F e* - any LEAF f3842239082 - ==== =============== ================== - -and node B: - - ==== =============== ================== - SLOT CONTENT INDEX KEY (PREFIX) - ==== =============== ================== - 3 PTR TO NODE C 13* - any LEAF 1458952489 - ==== =============== ================== - - -Shortcuts ---------- - -Shortcuts are metadata records that jump over a piece of keyspace. A shortcut -is a replacement for a series of single-occupancy nodes ascending through the -levels. Shortcuts exist to save memory and to speed up traversal. - -It is possible for the root of the tree to be a shortcut - say, for example, -the tree contains at least 17 nodes all with key prefix ``1111``. The -insertion algorithm will insert a shortcut to skip over the ``1111`` keyspace -in a single bound and get to the fourth level where these actually become -different. - - -Splitting And Collapsing Nodes ------------------------------- - -Each node has a maximum capacity of 16 leaves and metadata pointers. If the -insertion algorithm finds that it is trying to insert a 17th object into a -node, that node will be split such that at least two leaves that have a common -key segment at that level end up in a separate node rooted on that slot for -that common key segment. - -If the leaves in a full node and the leaf that is being inserted are -sufficiently similar, then a shortcut will be inserted into the tree. - -When the number of objects in the subtree rooted at a node falls to 16 or -fewer, then the subtree will be collapsed down to a single node - and this will -ripple towards the root if possible. - - -Non-Recursive Iteration ------------------------ - -Each node and shortcut contains a back pointer to its parent and the number of -slot in that parent that points to it. None-recursive iteration uses these to -proceed rootwards through the tree, going to the parent node, slot N + 1 to -make sure progress is made without the need for a stack. - -The backpointers, however, make simultaneous alteration and iteration tricky. - - -Simultaneous Alteration And Iteration -------------------------------------- - -There are a number of cases to consider: - -1. Simple insert/replace. This involves simply replacing a NULL or old - matching leaf pointer with the pointer to the new leaf after a barrier. - The metadata blocks don't change otherwise. An old leaf won't be freed - until after the RCU grace period. - -2. Simple delete. This involves just clearing an old matching leaf. The - metadata blocks don't change otherwise. The old leaf won't be freed until - after the RCU grace period. - -3. Insertion replacing part of a subtree that we haven't yet entered. This - may involve replacement of part of that subtree - but that won't affect - the iteration as we won't have reached the pointer to it yet and the - ancestry blocks are not replaced (the layout of those does not change). - -4. Insertion replacing nodes that we're actively processing. This isn't a - problem as we've passed the anchoring pointer and won't switch onto the - new layout until we follow the back pointers - at which point we've - already examined the leaves in the replaced node (we iterate over all the - leaves in a node before following any of its metadata pointers). - - We might, however, re-see some leaves that have been split out into a new - branch that's in a slot further along than we were at. - -5. Insertion replacing nodes that we're processing a dependent branch of. - This won't affect us until we follow the back pointers. Similar to (4). - -6. Deletion collapsing a branch under us. This doesn't affect us because the - back pointers will get us back to the parent of the new node before we - could see the new node. The entire collapsed subtree is thrown away - unchanged - and will still be rooted on the same slot, so we shouldn't - process it a second time as we'll go back to slot + 1. - -.. note:: - - Under some circumstances, we need to simultaneously change the parent - pointer and the parent slot pointer on a node (say, for example, we - inserted another node before it and moved it up a level). We cannot do - this without locking against a read - so we have to replace that node too. - - However, when we're changing a shortcut into a node this isn't a problem - as shortcuts only have one slot and so the parent slot number isn't used - when traversing backwards over one. This means that it's okay to change - the slot number first - provided suitable barriers are used to make sure - the parent slot number is read after the back pointer. - -Obsolete blocks and leaves are freed up after an RCU grace period has passed, -so as long as anyone doing walking or iteration holds the RCU read lock, the -old superstructure should not go away on them.
Documentation/core-api/index.rst +0 -1
@@ -38,7 +38,6 @@ Library functionality that is used throughout the kernel. kobject kref cleanup - assoc_array folio_queue xarray maple_tree
Documentation/translations/zh_CN/core-api/assoc_array.rst deleted +0 -473
473 lines not on this page · raw message
Documentation/translations/zh_CN/core-api/index.rst +0 -1
@@ -41,7 +41,6 @@ kobject kref - assoc_array xarray rbtree idr
include/linux/assoc_array.h deleted +0 -88
88 lines not on this page · raw message
include/linux/assoc_array_priv.h deleted +0 -178
178 lines not on this page · raw message
lib/Kconfig +0 -14
@@ -349,20 +349,6 @@ config XARRAY_MULTI Support entries which occupy multiple consecutive indices in the XArray. -config ASSOCIATIVE_ARRAY - bool - help - Generic associative array. Can be searched and iterated over whilst - it is being modified. It is also reasonably quick to search and - modify. The algorithms are non-recursive, and the trees are highly - capacious. - - See: - - Documentation/core-api/assoc_array.rst - - for more information. - config CLOSURES bool
lib/Makefile +0 -1
@@ -141,7 +141,6 @@ obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o obj-$(CONFIG_BTREE) += btree.o obj-$(CONFIG_INTERVAL_TREE) += interval_tree.o -obj-$(CONFIG_ASSOCIATIVE_ARRAY) += assoc_array.o obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o obj-$(CONFIG_LIST_HARDENED) += list_debug.o obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o
lib/assoc_array.c deleted +0 -1724
1,656 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 1 line
2.47.3
Part of the diff is not shown here. View the raw message.
[email protected]
AI reviewRe: [PATCH v13 7/7] lib: Remove assoc_array
Sashiko has reviewed this patch and found no issues.
Quoted 5 lines
As
assoc_arrayhas no longer in-kernel users, removeassoc_arrayimplementation, includes and documentation.Reviewed-by Eric Biggers <[email protected]>Signed-off-by Jarkko Sakkinen <[email protected]>
Sashiko has reviewed this patch and found no issues.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=7
Heiko Carstens
maintainerHi Jarkko,
Quoted 9 lines · Jarkko Sakkinen
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_arraywith an rhashtable-backed keyring index and removeassoc_arrayfrom the kernel.
...
Quoted 4 lines
v13:
- s390/cert_store: Hold key reference acrosskey_unlink(), and ignore-ENOENT.
- s390/cert_store: Add "s390/cert_store: Read-lock keyring semaphore ininvalidate_keyring_keys()".
Actually I had / have a patch series of 15 small patches ready to address various bugs in certstore, including yours. I'll send them later - a few (or many) collide with your patches. Not sure how we coordinate this.
Jarkko Sakkinen
maintainerQuoted 15 lines · Heiko Carstens
Hi Jarkko,
Quoted 9 lines · Jarkko Sakkinen
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_arraywith an rhashtable-backed keyring index and removeassoc_arrayfrom the kernel....
Quoted 8 lines
Quoted 4 lines
v13:
- s390/cert_store: Hold key reference acrosskey_unlink(), and ignore-ENOENT.
- s390/cert_store: Add "s390/cert_store: Read-lock keyring semaphore ininvalidate_keyring_keys()".Actually I had / have a patch series of 15 small patches ready to address various bugs in certstore, including yours. I'll send them later - a few (or many) collide with your patches. Not sure how we coordinate this.
That is perfect. I don't honestly care about patch authorship in this case too much. Do whatever you want :-) I'm just happy to get them out of the way.
Br, Jarkko