Skip to contentSkip to conversation

KEYS: Replace assoc_array with rhashtable

PATCH In review Jarkko Sakkinen 4 participants 19 messages Nov 14 – Nov 16

Subsystems (11)
lore
Share & tools
lore

Jarkko Sakkinen

author maintainer
#0 lore raw

v13 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]/

Cc Alasdair Kergon <[email protected]>
Cc Alexander Gordeev <[email protected]>
Cc Alexei Starovoitov <[email protected]>
Cc Alex Shi <[email protected]>
Cc Anastasia Eskova <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Benjamin Marzinski <[email protected]>
Cc Christian Borntraeger <[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 Heiko Carstens <[email protected]>
Cc Ihor Solodrai <[email protected]>
Cc James Bottomley <[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 Linus Torvalds <[email protected]>
Cc Martin KaFai Lau <[email protected]>
Cc Mike Snitzer <[email protected]>
Cc Mikulas Patocka <[email protected]>
Cc Mimi Zohar <[email protected]>
Cc Paul Moore <[email protected]>
Cc Peter Oberparleiter <[email protected]>
Cc Randy Dunlap <[email protected]>
Cc Roberto Sassu <[email protected]>
Cc "Serge E. Hallyn" <[email protected]>
Cc Shuah Khan <[email protected]>
Cc Song Liu <[email protected]>
Cc Sven Schnelle <[email protected]>
Cc "Theodore Y. Ts'o" <[email protected]>
Cc Vasily Gorbik <[email protected]>
Cc Yanteng Si <[email protected]>
Cc Yonghong Song <[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

author maintainer
#1 lore raw

PATCH 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()

Cc David Howells <[email protected]>
Fixes 8cf57d7217c3 ("s390: add support for user-defined certificates")
---
 arch/s390/kernel/cert_store.c | 27 +++++++++++++++++++++++----
 1 file changed, 23 insertions(+), 4 deletions(-)
arch/s390/kernel/cert_store.c +23 -4
index 998f2da56175..bb218b42a2c9 100644
@@ -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
#2 lore raw

Re: [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]>
Fixes 8cf57d7217c3 ("s390: add support for user-defined certificates")

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
author maintainer
#3 lore raw

PATCH v13 2/7 s390/cert_store: Return an owned reference from find_cs_keyring()

In reply to Jarkko Sakkinen

Return an owned reference from find_cs_keyring() so that it will not get dropped.

Cc David Howells <[email protected]>
Fixes 8cf57d7217c3 ("s390: add support for user-defined certificates")
---
 arch/s390/kernel/cert_store.c | 21 +++++++++------------
 1 file changed, 9 insertions(+), 12 deletions(-)
arch/s390/kernel/cert_store.c +9 -12
index bb218b42a2c9..0a10b31d68af 100644
@@ -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
#4 lore raw

Re: [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]>
Fixes 8cf57d7217c3 ("s390: add support for user-defined certificates")

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
author maintainer
#5 lore raw

PATCH v13 3/7 s390/cert_store: Skip keys that disappeared during invalidation

In reply to Jarkko Sakkinen

key_lookup() can return ERR_PTR(-ENOKEY) for an unlinked key. Skip such keys instead.

Cc David Howells <[email protected]>
Fixes 8cf57d7217c3 ("s390: add support for user-defined certificates")
---
 arch/s390/kernel/cert_store.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)
arch/s390/kernel/cert_store.c +9 -1
index 0a10b31d68af..bec95991edae 100644
@@ -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
#6 lore raw

Re: [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 return ERR_PTR(-ENOKEY) for an unlinked key. Skip such keys instead.

Cc David Howells <[email protected]>
Fixes 8cf57d7217c3 ("s390: add support for user-defined certificates")

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=3
author maintainer
#7 lore raw

PATCH v13 4/7 s390/cert_store: Read-lock keyring semaphore in invalidate_keyring_keys()

In reply to Jarkko Sakkinen

key_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.

Cc David Howells <[email protected]>
Fixes 8cf57d7217c3 ("s390: add support for user-defined certificates")
---
 arch/s390/kernel/cert_store.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)
arch/s390/kernel/cert_store.c +5 -1
index bec95991edae..7d339fe2f6fc 100644
@@ -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
#8 lore raw

Re: [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 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.

Cc David Howells <[email protected]>
Fixes 8cf57d7217c3 ("s390: add support for user-defined certificates")

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=4
author maintainer
#9 lore raw

PATCH v13 5/7 KEYS: Introduce keyring_is_empty()

In reply to Jarkko Sakkinen

Introduce 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
index 0c65c7a31da8..bd5143aae4fa 100644
@@ -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
index 2f49c5d9d987..b45b39b829b2 100644
@@ -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
index 420412aab926..9ff10b780865 100644
@@ -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
index bffc356839ac..24e0416abc99 100644
@@ -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
index 357f56360810..3d12dc4b5974 100644
@@ -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
index 1f9601ef22f8..792449d356cf 100755
@@ -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
#10 lore raw

Re: [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.

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=5
author maintainer
#11 lore raw

PATCH v13 6/7 KEYS: Replace assoc_array with rhashtable

In reply to 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 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
index 1dc83862f519..314832f5dc4a 100644
@@ -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
index c4f329b6ae3f..bb97bd3e5af4 100644
@@ -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
index 9ff10b780865..0d2d64e10f7b 100644
@@ -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
index f4510d8cb485..3f64d60d0f8a 100644
@@ -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
index b7b622bc36a1..c452d71cce03 100644
@@ -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
index 3f1f0fc13710..20cf273cf4a3 100644
@@ -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
index 22cd66a44da5..40fbcd15be43 100644
@@ -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
#12 lore raw
Sashiko 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_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.

Quoted 6 lines

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=6
#13 lore raw
In reply to Jarkko Sakkinen
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 1 line

KEYS: Replace assoc_array with 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_t buflen)

[ ... ]

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

author maintainer
#14 lore raw
Quoted 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

author maintainer
#15 lore raw

PATCH v13 7/7 lib: Remove assoc_array

In reply to Jarkko Sakkinen

As 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
deleted file mode 100644
index 19d89f92bf8d..000000000000
@@ -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
index 92f91c6a0d79..d56c60663b0c 100644
@@ -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
index 453a02cd1f44..ec4b03b2a0a6 100644
@@ -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
index 1e42f5167c68..f70382dbb159 100644
@@ -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
index a2afe954805c..4777dfcc8244 100644
@@ -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.

#16 lore raw

Re: [PATCH v13 7/7] lib: Remove assoc_array

Sashiko has reviewed this patch and found no issues.
Quoted 5 lines

As assoc_array has no longer in-kernel users, remove assoc_array implementation, includes and documentation.

Sashiko has reviewed this patch and found no issues.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=7
maintainer
#17 lore raw
In reply to Jarkko Sakkinen

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_array with an rhashtable-backed keyring index and remove assoc_array from the kernel.

...

Quoted 4 lines

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()".

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.

author maintainer
#18 lore raw
Quoted 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_array with an rhashtable-backed keyring index and remove assoc_array from the kernel.

...

Quoted 8 lines
Quoted 4 lines

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()".

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