From nobody Thu Nov 5 05:11:18 2026 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=100.103.45.18 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1793848454; b=Hd7ceMW04HfPhRGl7NGL0SLveu/oMOMJUe7YVJEpzR7SMZDyVe1YBMo65+8AzQ6M1coY 5GQReNSICIJBn4hqET7KC+fOUGxAxnaMruSxTb41iaFd/vd4iJZ8v9xjaT0w36Up7zGmG 37zNNhOUKOZTFcqO8zBGYSKIODE2oYMXrD+m7r9ICct4PF65T6VwKoIsL5zssWf+eIOUO LZVpCS/CKrzExoj2eOUz1rjPMQ+ZP4kH+RpY1vq9hUU1OGDxuRYuvm8K3ttNhh8lveIkr xuQ3Gv70OmQm499QKNZGDhCHWd4eWw6fa9ScswPgGqeenNpaRi8Zba0oi9j+LhJ+ntA== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1793848454; h=Received:DKIM-Signature:From:To:Cc:Subject:Date:Message-ID:X-Mailer: In-Reply-To:References:MIME-Version:Content-Transfer-Encoding; bh=d57Xwxdq7ggCiZHh4PGNXJufaWf8Hx04l8Vo55VakVk=; b=PNALdDJkv6X1Lwsq1NqV01RMVivLHn9yxkPOaudkeLdRJPVnUQp4CIcQW1/k6LVhi5cy 6Ub0wQLVArxK5zUxBm4jDIjdFr801SO0uzs9QQ6aWoxrKk7qCMPLoOE4y1+SWT8zZXaIP 1zNrDPEyoJnP/OAMEcvVHUgIb5t5FMGOBRS/MPdH3HB855+KBFaI6FM8TrIciOPPGaP0N GA1U8Ac5X6YEcwP6IG1oNz5fJ2AwfCv2rOXUs68UJa3EhkBnIGrFHyaZ1MZKleVaYWtjD j28G+/f89EfJvkcvpaV0Kdfec01K4TwWVJKfnTorQJn0+i5H8Ch/18Wn/CWuA4UD0Uw== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass header.d=kernel.org header.i=@kernel.org header.a=rsa-sha256 header.s=k20260515 header.b=VgdQBmAF; arc=none smtp.remote-ip=100.103.45.18 Received: from smtp.kernel.org (quasi.space.kernel.org [100.103.45.18]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (prime256v1)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with UTF8SMTPS id 6EA03606A334; Thu, 5 Nov 2026 03:14:14 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key, unprotected) header.d=kernel.org header.i=@kernel.org header.a=rsa-sha256 header.s=k20260515 header.b=VgdQBmAF Received: by smtp.kernel.org (Postfix) with UTF8SMTPSA id 6A2C11F00A15; Thu, 5 Nov 2026 03:14:13 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kernel.org; s=k20260515; t=1793848454; bh=d57Xwxdq7ggCiZHh4PGNXJufaWf8Hx04l8Vo55VakVk=; h=From:To:Cc:Subject:Date:In-Reply-To:References; b=VgdQBmAFZs7l45kySOt1KaURQxQBpI2W7uJgqVFaQwbaaNBsyaOCNcAh/9wOhyKAe OIlClBLYE4vwVfPsOkEfp628ND79LS1HjHHuIqEIy4EDzNE+6pZsLzXidmBbPSKqUg ila5gkcd4EXi4u7OJghEIiyPf1HfmcrFxfd01TdSO/Weo3IP4x//Ezi6njHCNtEMmK wIESO/hyhzH4UbRVvc1Dvj84es71LNee33JVW2YUoMOUnNkyVDBc1jS+h4c15wT6u8 1LzvYeIwlR0nOTVl7TR2KaRxZx/oYCw/Qlojbs2FERLNLzmqr84oZREBGlzOYy7k1+ YsGnaBS8WblHA== From: Jarkko Sakkinen To: David Howells Cc: Jarkko Sakkinen , bpf@vger.kernel.org, dm-devel@lists.linux.dev, fsverity@lists.linux.dev, keyrings@vger.kernel.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org, linux-security-module@vger.kernel.org, Alasdair Kergon , Alexei Starovoitov , Alex Shi , Andrew Morton , Andrii Nakryiko , Benjamin Marzinski , Daniel Borkmann , Dongliang Mu , Eduard Zingerman , Emil Tsalapatis , Eric Biggers , Ihor Solodrai , James Morris , Jiri Olsa , Jonathan Corbet , Kumar Kartikeya Dwivedi , Martin KaFai Lau , Mike Snitzer , Mikulas Patocka , Paul Moore , Randy Dunlap , "Serge E. Hallyn" , Shuah Khan , Song Liu , "Theodore Y. Ts'o" , Yanteng Si , Yonghong Song Subject: [PATCH v5 1/3] KEYS: Introduce keyring_is_empty() Date: Thu, 5 Nov 2026 05:13:59 +0200 Message-ID: <20261105031401.956609-2-jarkko@kernel.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20261105031401.956609-1-jarkko@kernel.org> References: <20261105031401.956609-1-jarkko@kernel.org> X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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 Signed-off-by: Jarkko Sakkinen --- 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(-) diff --git a/drivers/md/dm-verity-verify-sig.c b/drivers/md/dm-verity-verif= y-sig.c index 0c65c7a31da8..bd5143aae4fa 100644 --- a/drivers/md/dm-verity-verify-sig.c +++ b/drivers/md/dm-verity-verify-sig.c @@ -153,7 +153,7 @@ int verity_verify_root_hash(const void *root_hash, size= _t root_hash_len, if (ret !=3D -ENOKEY && ret !=3D -EKEYREJECTED) return ret; =20 - if (dm_verity_keyring->keys.nr_leaves_on_tree && + if (!keyring_is_empty(dm_verity_keyring) && dm_verity_keyring->restrict_link) ret =3D verify_pkcs7_signature(root_hash, root_hash_len, sig_data, sig_len, diff --git a/fs/verity/signature.c b/fs/verity/signature.c index 2f49c5d9d987..b45b39b829b2 100644 --- a/fs/verity/signature.c +++ b/fs/verity/signature.c @@ -70,7 +70,7 @@ int fsverity_verify_signature(const struct fsverity_info = *vi, return 0; } =20 - if (fsverity_keyring->keys.nr_leaves_on_tree =3D=3D 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. diff --git a/include/linux/key.h b/include/linux/key.h index 420412aab926..9ff10b780865 100644 --- a/include/linux/key.h +++ b/include/linux/key.h @@ -439,6 +439,7 @@ extern int restrict_link_reject(struct key *keyring, struct key *restriction_key); =20 extern int keyring_clear(struct key *keyring); +bool keyring_is_empty(const struct key *keyring); =20 extern key_ref_t keyring_search(key_ref_t keyring, struct key_type *type, diff --git a/kernel/bpf/keys.c b/kernel/bpf/keys.c index bffc356839ac..24e0416abc99 100644 --- a/kernel/bpf/keys.c +++ b/kernel/bpf/keys.c @@ -29,7 +29,7 @@ struct bpf_key *bpf_lookup_keyring(void) =20 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; =20 diff --git a/security/keys/keyring.c b/security/keys/keyring.c index 5281da9d5bf7..ac48d6204915 100644 --- a/security/keys/keyring.c +++ b/security/keys/keyring.c @@ -443,6 +443,16 @@ static void keyring_destroy(struct key *keyring) assoc_array_destroy(&keyring->keys, &keyring_assoc_array_ops); } =20 +/** + * 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) =3D=3D 0; +} +EXPORT_SYMBOL(keyring_is_empty); + /* * Describe a keyring for /proc. */ diff --git a/tools/testing/selftests/dm-verity/test-dm-verity-keyring.sh b/= tools/testing/selftests/dm-verity/test-dm-verity-keyring.sh index 1f9601ef22f8..792449d356cf 100755 --- a/tools/testing/selftests/dm-verity/test-dm-verity-keyring.sh +++ b/tools/testing/selftests/dm-verity/test-dm-verity-keyring.sh @@ -746,7 +746,7 @@ test_keyring_inactive_when_empty() { log_info "TEST: Verify dm-verity keyring is inactive when sealed empty" =20 # When keyring_unsealed=3D0, the keyring is sealed immediately while e= mpty - # This means it should NOT be used for verification (nr_leaves_on_tree= =3D0) + # An empty keyring should NOT be used for verification. =20 log_info "Keyring state (should be empty and sealed):" list_keyring_keys --=20 2.47.3 From nobody Thu Nov 5 05:11:18 2026 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=100.103.45.18 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1793848459; b=3FSmrfmCiLUhvwOjs3EioHu7ainqUR4EHCuvWREqjTlCTBHHtqIVEfUfNSMTqpN5HgLR Gak4cXFYYkYeZZqBEfgxDlyZuUg/yIp3n4cl1SC4C+S5Pxanbp1nFdBeTAJrrFYjtkRyg NLyTdJLt7lgYvrQ1IEDmTSKW9+tEuZMPkQI/TJ/KCHvngB1Z/j5frRLdm0wOXkIPtsd7E 79YEbaMnCxk35SaZqmFSVsBXKiubgLQBitLST7WK9/HxZlswG+JloZ6Aj6YA9o9Dgv7z/ 7sSK0uYDl9iOmaf1Gw+mZGsLdcmEW5mR8OGE7RlG5+BzpCF4p2p+RjLqrMtyEDS+Rkg== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1793848459; h=Received:DKIM-Signature:From:To:Cc:Subject:Date:Message-ID:X-Mailer: In-Reply-To:References:MIME-Version:Content-Transfer-Encoding; bh=UyolsUZ+lGPTUTuBm2oBpUwJ2w79S0GGLfNHUfCm78g=; b=txATN72nGh+YtBtkq9N/KDDjKqPwPumEid2toa9TV8yYMY+ahztcB4PK1NOHDtvZhIvj iA55IC8iPSPJos/DS33V53zSAJlGpLOvNH5Xfr+kUa5MF1KCdCHFWbJV3qQybQ8wHgnM1 m8XySOZ9uyuSEqX1xt9aHrSgBlrzZQHXP+uQN02MkqfmpC1TNtTYqLB2w0nWUQNXfmxxb ohV7sh8+y2ouuZZ0yBq0kKBV8J0mWklTlCF/z1NjFU7HMre+IfLfmGSgcAzqmZXNPIYdH pJ2IsToLuyStJVrWlAjxWAKZdCFENY9f5pTjPEDbZx7UdG+BBHw0If5EFUHMldwwYug== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass header.d=kernel.org header.i=@kernel.org header.a=rsa-sha256 header.s=k20260515 header.b=DMvKwtay; arc=none smtp.remote-ip=100.103.45.18 Received: from smtp.kernel.org (quasi.space.kernel.org [100.103.45.18]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (prime256v1)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with UTF8SMTPS id 93589606A31B; Thu, 5 Nov 2026 03:14:18 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key, unprotected) header.d=kernel.org header.i=@kernel.org header.a=rsa-sha256 header.s=k20260515 header.b=DMvKwtay Received: by smtp.kernel.org (Postfix) with UTF8SMTPSA id 605341F000C1; Thu, 5 Nov 2026 03:14:17 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kernel.org; s=k20260515; t=1793848458; bh=UyolsUZ+lGPTUTuBm2oBpUwJ2w79S0GGLfNHUfCm78g=; h=From:To:Cc:Subject:Date:In-Reply-To:References; b=DMvKwtay6Oj0EmiIc/6esgjZf8tnuj0ECfXhIn65trsrfJR+q5O4otOzFdUmaqXTA m5ArqfV04DbPV+lMmygHhvUnate1CPE60Cz2EU4uQRKm6bnglwJz842DqkQfKdrXig kWGvLT95omR45DfHij1twcBC1LiipQYezzTO5EKCf/EaoCksZfr38Ei7ImZfYHkejt X3ZIGAlsQIj+IdjIUP0kJk63PQ5IDDnCbRrt5riDs70HKqnL9e9s01fvIg0EqZ+Hrt 6iik//OhqXVjfI1LkD3SD48xnGsA+NzeNc04YpK3G5mCElXSJLi4JiCumh3RUT9Yka 6TFOKyHGhy1aA== From: Jarkko Sakkinen To: David Howells Cc: Jarkko Sakkinen , bpf@vger.kernel.org, dm-devel@lists.linux.dev, fsverity@lists.linux.dev, keyrings@vger.kernel.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org, linux-security-module@vger.kernel.org, Alasdair Kergon , Alexei Starovoitov , Alex Shi , Andrew Morton , Andrii Nakryiko , Benjamin Marzinski , Daniel Borkmann , Dongliang Mu , Eduard Zingerman , Emil Tsalapatis , Eric Biggers , Ihor Solodrai , James Morris , Jiri Olsa , Jonathan Corbet , Kumar Kartikeya Dwivedi , Martin KaFai Lau , Mike Snitzer , Mikulas Patocka , Paul Moore , Randy Dunlap , "Serge E. Hallyn" , Shuah Khan , Song Liu , "Theodore Y. Ts'o" , Yanteng Si , Yonghong Song , Linus Torvalds Subject: [PATCH v5 2/3] KEYS: Replace assoc_array with rhashtable Date: Thu, 5 Nov 2026 05:14:00 +0200 Message-ID: <20261105031401.956609-3-jarkko@kernel.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20261105031401.956609-1-jarkko@kernel.org> References: <20261105031401.956609-1-jarkko@kernel.org> X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The keyrings subsystem is the sole user of assoc_array. It has over 1700 lines of code, no test suite, and a long history of bugs, with LLMs now finding more. This unfortunate outcome has evolved over time by large from the shortage of in-kernel callers, time bandwidth and 3rd party contributors. What the keyrings needs is just a generic key-value store, which performs well with sparse key sets. Replace struct assoc_array in struct key with struct keyring_index: - keyring_index: holds an rhashtable for direct lookups, an RCU-protected list of keyring_link entries for stable walks, the active link count, and an rcu_work item for deferred teardown. - keyring_link: links a key into a keyring's hash table and list, caching its 32-bit SipHash digest rehashed with jhash by rhashtable. Correspondingly, struct assoc_array_edit is replaced by struct keyring_edit for delivering transient state across link operations. Other behavioral changes: - KEYCTL_READ and sibling-keyring searches follow list order instead of hash order: keyrings are prepended, other keys are appended, and replacing a matching key retains its position. - key_unlink(), keyring_clear(), keyring_revoke(), and keyring_gc() no longer allocate memory. - keyring_index_free() uses queue_rcu_work() instead of call_rcu() because rhashtable_destroy() may sleep. Suggested-by: Eric Biggers Co-developed-by: Linus Torvalds Signed-off-by: Linus Torvalds Signed-off-by: Jarkko Sakkinen --- 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 | 986 ++++++++++++++++-------------------- security/keys/request_key.c | 8 +- 8 files changed, 465 insertions(+), 596 deletions(-) diff --git a/include/keys/keyring-type.h b/include/keys/keyring-type.h index 1dc83862f519..314832f5dc4a 100644 --- a/include/keys/keyring-type.h +++ b/include/keys/keyring-type.h @@ -9,6 +9,5 @@ #define _KEYS_KEYRING_TYPE_H =20 #include -#include =20 #endif /* _KEYS_KEYRING_TYPE_H */ diff --git a/include/linux/key-type.h b/include/linux/key-type.h index c4f329b6ae3f..bb97bd3e5af4 100644 --- a/include/linux/key-type.h +++ b/include/linux/key-type.h @@ -161,7 +161,6 @@ struct key_type { const void *in, const void *in2); =20 /* 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; diff --git a/include/linux/key.h b/include/linux/key.h index 9ff10b780865..0d2d64e10f7b 100644 --- a/include/linux/key.h +++ b/include/linux/key.h @@ -17,7 +17,6 @@ #include #include #include -#include #include #include =20 @@ -107,34 +106,21 @@ struct key_owner; struct key_tag; struct keyring_list; struct keyring_name; +struct keyring_index; =20 struct key_tag { struct rcu_head rcu; - atomic64_t index_id; /* Opaque keyring index ID */ refcount_t usage; bool removed; /* T when subject removed */ }; =20 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; }; =20 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; }; }; =20 @@ -271,7 +255,7 @@ struct key { struct { /* Keyring bits */ struct list_head name_link; - struct assoc_array keys; + struct keyring_index __rcu *index; }; }; =20 diff --git a/security/keys/Kconfig b/security/keys/Kconfig index f4510d8cb485..3f64d60d0f8a 100644 --- a/security/keys/Kconfig +++ b/security/keys/Kconfig @@ -5,7 +5,6 @@ =20 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. diff --git a/security/keys/internal.h b/security/keys/internal.h index b7b622bc36a1..c452d71cce03 100644 --- a/security/keys/internal.h +++ b/security/keys/internal.h @@ -21,6 +21,12 @@ #include =20 struct iovec; +struct keyring_link; + +struct keyring_edit { + struct keyring_link *new; + struct keyring_link *old; +}; =20 #ifdef __KDEBUG #define kenter(FMT, ...) \ @@ -98,13 +104,13 @@ extern int __key_move_lock(struct key *l_keyring, stru= ct 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); =20 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 (intenti= on to replace) */ #define KEYRING_SEARCH_RECURSE 0x0040 /* Search child keyrings also */ =20 - int (*iterator)(const void *object, void *iterator_data); + int (*iterator)(const struct key *key, void *iterator_data); =20 /* Internal stuff */ int skipped_ret; diff --git a/security/keys/key.c b/security/keys/key.c index 3f1f0fc13710..20cf273cf4a3 100644 --- a/security/keys/key.c +++ b/security/keys/key.c @@ -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; =20 @@ -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); =20 - __key_link(keyring, key, _edit); + __key_link(keyring, key, edit); } =20 /* 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 =3D NULL; + struct keyring_edit edit =3D {}; int ret; =20 memset(&prep, 0, sizeof(prep)); @@ -543,7 +543,7 @@ int key_instantiate_and_link(struct key *key, =20 error_link_end: if (keyring) - __key_link_end(keyring, &key->index_key, edit); + __key_link_end(keyring, &key->index_key, &edit); =20 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 =3D NULL; + struct keyring_edit edit =3D {}; int ret, awaken, link_ret =3D 0; =20 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 =3D __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); } } =20 @@ -635,7 +635,7 @@ int key_reject_and_link(struct key *key, mutex_unlock(&key_construction_mutex); =20 if (keyring && link_ret =3D=3D 0) - __key_link_end(keyring, &key->index_key, edit); + __key_link_end(keyring, &key->index_key, &edit); =20 /* 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 keyri= ng_ref, .description =3D description, }; struct key_preparsed_payload prep; - struct assoc_array_edit *edit =3D NULL; + struct keyring_edit edit =3D {}; const struct cred *cred =3D current_cred(); struct key *keyring, *key =3D NULL; key_ref_t key_ref; @@ -966,7 +966,7 @@ static key_ref_t __key_create_or_update(key_ref_t keyri= ng_ref, key_ref =3D make_key_ref(key, is_key_possessed(keyring_ref)); =20 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 keyri= ng_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); =20 key =3D key_ref_to_ptr(key_ref); if (test_bit(KEY_FLAG_USER_CONSTRUCT, &key->flags)) { diff --git a/security/keys/keyring.c b/security/keys/keyring.c index ac48d6204915..772fa0e35f9d 100644 --- a/security/keys/keyring.c +++ b/security/keys/keyring.c @@ -12,14 +12,16 @@ #include #include #include +#include +#include #include #include #include #include +#include #include +#include #include -#include -#include #include #include #include "internal.h" @@ -31,25 +33,152 @@ #define KEYRING_SEARCH_MAX_DEPTH 6 =20 /* - * We mark pointers we pass to the associative array with bit 1 set if - * they're keyrings and clear otherwise. + * Keyrings are inserted at the head of @list, other keys at the tail, so + * recursive search can stop at the first non-keyring. */ -#define KEYRING_PTR_SUBTYPE 0x2UL +struct keyring_index { + struct rhashtable ht; + struct list_head list; /* Active keys */ + unsigned long nr; /* Number of active keys */ + struct rcu_work rcu_work; +}; + +/* + * __key_link_begin() inserts new links with @key NULL so allocation happe= ns + * before __key_link(). @hash is cached so resizing can hash links while = @key + * is NULL. + */ +struct keyring_link { + struct rcu_head rcu; + struct rhash_head node; + struct key __rcu *key; /* NULL while inactive */ + struct list_head list; + u32 hash; +}; + +static u32 keyring_hashfn(const void *data, u32 len, u32 seed) +{ + const struct keyring_index_key *index_key =3D data; + + return jhash_1word(index_key->hash, seed); +} =20 -static inline bool keyring_ptr_is_keyring(const struct assoc_array_ptr *x) +static u32 keyring_obj_hashfn(const void *data, u32 len, u32 seed) { - return (unsigned long)x & KEYRING_PTR_SUBTYPE; + const struct keyring_link *link =3D data; + + return jhash_1word(link->hash, seed); } -static inline struct key *keyring_ptr_to_key(const struct assoc_array_ptr = *x) + +static bool keyring_index_key_equal(const struct keyring_index_key *a, + const struct keyring_index_key *b) { - void *object =3D assoc_array_ptr_to_leaf(x); - return (struct key *)((unsigned long)object & ~KEYRING_PTR_SUBTYPE); + return a->type =3D=3D b->type && + a->domain_tag =3D=3D b->domain_tag && + a->desc_len =3D=3D b->desc_len && + memcmp(a->description, b->description, a->desc_len) =3D=3D 0; } -static inline void *keyring_key_to_ptr(struct key *key) + +static struct key *keyring_link_key(const struct keyring_link *link) { - if (key->type =3D=3D &key_type_keyring) - return (void *)((unsigned long)key | KEYRING_PTR_SUBTYPE); - return key; + return rcu_dereference_check(link->key, true); +} + +static int keyring_obj_cmpfn(struct rhashtable_compare_arg *arg, + const void *obj) +{ + const struct keyring_link *link =3D obj; + const struct key *key =3D keyring_link_key(link); + + return !key || !keyring_index_key_equal(&key->index_key, arg->key); +} + +static const struct rhashtable_params keyring_link_params =3D { + .head_offset =3D offsetof(struct keyring_link, node), + .hashfn =3D keyring_hashfn, + .obj_hashfn =3D keyring_obj_hashfn, + .obj_cmpfn =3D keyring_obj_cmpfn, + .min_size =3D 4, + .nelem_hint =3D 3, + .automatic_shrinking =3D true, +}; + +static struct keyring_index *keyring_index_locked(const struct key *keyrin= g) +{ + return rcu_dereference_protected(keyring->index, + lockdep_is_held(&keyring->sem)); +} + +static struct keyring_link *keyring_find_link(struct keyring_index *index, + const struct keyring_index_key *index_key) +{ + if (!index) + return NULL; + + return rhashtable_lookup_fast(&index->ht, index_key, keyring_link_params); +} + +static int keyring_iterate(const struct key *keyring, + int (*iterator)(const struct key *key, void *data), + void *data) +{ + struct keyring_index *index; + struct keyring_link *link; + int ret; + + guard(rcu)(); + index =3D rcu_dereference(keyring->index); + if (index) { + list_for_each_entry_rcu(link, &index->list, list) { + ret =3D iterator(keyring_link_key(link), data); + if (ret) + return ret; + } + } + + return 0; +} + +static void keyring_link_free_rcu(struct rcu_head *rcu) +{ + struct keyring_link *link =3D container_of(rcu, struct keyring_link, rcu); + + key_put(rcu_dereference_raw(link->key)); + kfree(link); +} + +static void __keyring_index_free(struct keyring_index *index) +{ + struct keyring_link *link, *tmp; + + rhashtable_destroy(&index->ht); + + list_for_each_entry_safe(link, tmp, &index->list, list) { + key_put(rcu_dereference_protected(link->key, true)); + kfree(link); + } + + kfree(index); +} + +static void keyring_index_free_work(struct work_struct *work) +{ + struct keyring_index *index =3D container_of(to_rcu_work(work), + struct keyring_index, rcu_work); + + __keyring_index_free(index); +} + +static void keyring_index_free(struct key *keyring) +{ + struct keyring_index *index =3D keyring_index_locked(keyring); + + if (!index) + return; + + rcu_assign_pointer(keyring->index, NULL); + /* rhashtable_destroy() may sleep, so defer via rcu_work. */ + queue_rcu_work(system_dfl_wq, &index->rcu_work); } =20 static DEFINE_RWLOCK(keyring_name_lock); @@ -143,80 +272,44 @@ static void keyring_free_preparse(struct key_preparse= d_payload *prep) static int keyring_instantiate(struct key *keyring, struct key_preparsed_payload *prep) { - assoc_array_init(&keyring->keys); + RCU_INIT_POINTER(keyring->index, NULL); /* make the keyring available by name if it has one */ keyring_publish_name(keyring); return 0; } =20 /* - * Give key types and domains address-independent identities. Zero means = that - * an ID has not yet been allocated. As with inode sequence numbers used = by - * futexes, this relies on the 64-bit counter not wrapping in a machine's - * lifetime. - */ -static u64 key_index_id(atomic64_t *id) -{ - static atomic64_t next_id; - u64 old, new; - - old =3D atomic64_read(id); - if (likely(old)) - return old; - - do { - new =3D atomic64_inc_return(&next_id); - } while (WARN_ON_ONCE(!new)); - - old =3D 0; - if (!atomic64_try_cmpxchg_relaxed(id, &old, new)) - return old; - return new; -} - -/* - * Hash a key type, domain and description. KEYCTL_READ exposes the tree's - * traversal order, so no part of the index may contain kernel addresses. + * Hash a key type, domain and description. */ static void hash_key_type_and_desc(struct keyring_index_key *index_key) { - const unsigned level_shift =3D ASSOC_ARRAY_LEVEL_STEP; - const unsigned long fan_mask =3D ASSOC_ARRAY_FAN_MASK; static siphash_key_t hash_key __read_mostly; - unsigned long hash; u64 acc; =20 + /* + * Compute a SipHash value of the description, type pointer, and domain + * tag pointer using a per-boot random key. + * + * Note that using the pointers as input to the hash is safe, since + * SipHash is a cryptographically secure pseudorandom function. Thus + * the hash values don't leak any information about the pointers. + * + * Similarly, truncating the SipHash values to the required 32 bits is + * also safe. No "folding" step is needed. + */ get_random_once(&hash_key, sizeof(hash_key)); acc =3D siphash(index_key->description, index_key->desc_len, &hash_key); - acc =3D siphash_3u64(index_key->type_id, index_key->domain_id, acc, - &hash_key); - - /* Fold the hash down to 32 bits if need be. */ - hash =3D acc; - if (ASSOC_ARRAY_KEY_CHUNK_SIZE =3D=3D 32) - hash ^=3D acc >> 32; - - /* Squidge all the keyrings into a separate part of the tree to - * ordinary keys by making sure the lowest level segment in the hash is - * zero for keyrings and non-zero otherwise. - */ - if (index_key->type !=3D &key_type_keyring && (hash & fan_mask) =3D=3D 0) - hash |=3D (hash >> (ASSOC_ARRAY_KEY_CHUNK_SIZE - level_shift)) | 1; - else if (index_key->type =3D=3D &key_type_keyring && (hash & fan_mask) != =3D 0) - hash =3D (hash + (hash << level_shift)) & ~fan_mask; - index_key->hash =3D hash; + index_key->hash =3D siphash_3u64((uintptr_t)index_key->type, + (uintptr_t)index_key->domain_tag, + acc, &hash_key); } =20 /* - * Finalise an index key to include a part of the description actually in = the - * index key, to set the domain tag and index IDs, and to calculate the ha= sh. + * Finalise an index key to set the domain tag and calculate the hash. */ void key_set_index_key(struct keyring_index_key *index_key) { static struct key_tag default_domain_tag =3D { .usage =3D REFCOUNT_INIT(1= ), }; - size_t n =3D min_t(size_t, index_key->desc_len, sizeof(index_key->desc)); - - memcpy(index_key->desc, index_key->description, n); =20 if (!index_key->domain_tag) { if (index_key->type->flags & KEY_TYPE_NET_DOMAIN) @@ -225,14 +318,6 @@ void key_set_index_key(struct keyring_index_key *index= _key) index_key->domain_tag =3D &default_domain_tag; } =20 - /* Preserve the IDs when copying an existing key's index. In - * particular, its type may already have been unregistered. - */ - if (!index_key->type_id) - index_key->type_id =3D key_index_id(&index_key->type->index_id); - if (!index_key->domain_id) - index_key->domain_id =3D key_index_id(&index_key->domain_tag->index_id); - hash_key_type_and_desc(index_key); } =20 @@ -268,150 +353,6 @@ void key_remove_domain(struct key_tag *domain_tag) key_schedule_gc_links(); } =20 -/* - * Build the next index key chunk. - * - * The hash and inline description are followed by the 64-bit type and dom= ain - * IDs, low word first, and then by the rest of the description. - * We return it one word-sized chunk at a time. - */ -static unsigned long keyring_get_key_chunk(const void *data, int level) -{ - const unsigned int id_chunks =3D sizeof(u64) / sizeof(unsigned long); - const struct keyring_index_key *index_key =3D data; - int desc_len =3D index_key->desc_len; - unsigned long chunk =3D 0; - int n =3D sizeof(chunk); - unsigned int offset; - const u8 *d; - - level /=3D ASSOC_ARRAY_KEY_CHUNK_SIZE; - switch (level) { - case 0: - return index_key->hash; - case 1: - return index_key->x; - } - - level -=3D 2; - if (level < id_chunks) - return index_key->type_id >> (level * ASSOC_ARRAY_KEY_CHUNK_SIZE); - level -=3D id_chunks; - if (level < id_chunks) - return index_key->domain_id >> (level * ASSOC_ARRAY_KEY_CHUNK_SIZE); - level -=3D id_chunks; - - offset =3D sizeof(index_key->desc) + level * sizeof(long); - if (desc_len <=3D offset) - return 0; - - d =3D index_key->description + offset; - desc_len -=3D offset; - if (desc_len > n) - desc_len =3D n; - d +=3D desc_len; - do { - chunk <<=3D 8; - chunk |=3D *--d; - } while (--desc_len > 0); - return chunk; -} - -static unsigned long keyring_get_object_key_chunk(const void *object, int = level) -{ - const struct key *key =3D keyring_ptr_to_key(object); - return keyring_get_key_chunk(&key->index_key, level); -} - -static bool keyring_compare_object(const void *object, const void *data) -{ - const struct keyring_index_key *index_key =3D data; - const struct key *key =3D keyring_ptr_to_key(object); - - return key->index_key.type =3D=3D index_key->type && - key->index_key.domain_tag =3D=3D index_key->domain_tag && - key->index_key.desc_len =3D=3D index_key->desc_len && - memcmp(key->index_key.description, index_key->description, - index_key->desc_len) =3D=3D 0; -} - -/* - * Compare the index keys of a pair of objects and determine the bit posit= ion - * at which they differ - if they differ. - */ -static int keyring_diff_objects(const void *object, const void *data) -{ - const struct key *key_a =3D keyring_ptr_to_key(object); - const struct keyring_index_key *a =3D &key_a->index_key; - const struct keyring_index_key *b =3D data; - unsigned long seg_a, seg_b; - int level, i; - u64 diff; - - level =3D 0; - seg_a =3D a->hash; - seg_b =3D b->hash; - if ((seg_a ^ seg_b) !=3D 0) - goto differ; - level +=3D ASSOC_ARRAY_KEY_CHUNK_SIZE / 8; - - /* The inline description contributes one machine-word-sized chunk. */ - seg_a =3D a->x; - seg_b =3D b->x; - if ((seg_a ^ seg_b) !=3D 0) - goto differ; - level +=3D sizeof(unsigned long); - - diff =3D a->type_id ^ b->type_id; - if (diff) - return level * 8 + __ffs64(diff); - level +=3D sizeof(u64); - - diff =3D a->domain_id ^ b->domain_id; - if (diff) - return level * 8 + __ffs64(diff); - level +=3D sizeof(u64); - - i =3D sizeof(a->desc); - if (a->desc_len <=3D i) - goto same; - - for (; i < a->desc_len; i++) { - seg_a =3D *(unsigned char *)(a->description + i); - seg_b =3D *(unsigned char *)(b->description + i); - if ((seg_a ^ seg_b) !=3D 0) - goto differ_plus_i; - } - -same: - return -1; - -differ_plus_i: - level +=3D i - (int)sizeof(a->desc); -differ: - i =3D level * 8 + __ffs(seg_a ^ seg_b); - return i; -} - -/* - * Free an object after stripping the keyring flag off of the pointer. - */ -static void keyring_free_object(void *object) -{ - key_put(keyring_ptr_to_key(object)); -} - -/* - * Operations for keyring management by the index-tree routines. - */ -static const struct assoc_array_ops keyring_assoc_array_ops =3D { - .get_key_chunk =3D keyring_get_key_chunk, - .get_object_key_chunk =3D keyring_get_object_key_chunk, - .compare_object =3D keyring_compare_object, - .diff_objects =3D keyring_diff_objects, - .free_object =3D keyring_free_object, -}; - /* * Clean up a keyring when it is destroyed. Unpublish its name if it had = one * and dispose of its data. @@ -423,6 +364,8 @@ static const struct assoc_array_ops keyring_assoc_array= _ops =3D { */ static void keyring_destroy(struct key *keyring) { + struct keyring_index *index; + if (keyring->description) { write_lock(&keyring_name_lock); =20 @@ -440,7 +383,18 @@ static void keyring_destroy(struct key *keyring) kfree(keyres); } =20 - assoc_array_destroy(&keyring->keys, &keyring_assoc_array_ops); + index =3D rcu_dereference_protected(keyring->index, true); + if (index) + __keyring_index_free(index); +} + +static unsigned long keyring_nr_links(const struct key *keyring) +{ + const struct keyring_index *index; + + guard(rcu)(); + index =3D rcu_dereference(keyring->index); + return index ? READ_ONCE(index->nr) : 0; } =20 /** @@ -449,7 +403,7 @@ static void keyring_destroy(struct key *keyring) */ bool keyring_is_empty(const struct key *keyring) { - return READ_ONCE(keyring->keys.nr_leaves_on_tree) =3D=3D 0; + return keyring_nr_links(keyring) =3D=3D 0; } EXPORT_SYMBOL(keyring_is_empty); =20 @@ -458,41 +412,22 @@ EXPORT_SYMBOL(keyring_is_empty); */ static void keyring_describe(const struct key *keyring, struct seq_file *m) { + unsigned long nr; + if (keyring->description) seq_puts(m, keyring->description); else seq_puts(m, "[anon]"); =20 if (key_is_positive(keyring)) { - if (keyring->keys.nr_leaves_on_tree !=3D 0) - seq_printf(m, ": %lu", keyring->keys.nr_leaves_on_tree); + nr =3D keyring_nr_links(keyring); + if (nr !=3D 0) + seq_printf(m, ": %lu", nr); else seq_puts(m, ": empty"); } } =20 -struct keyring_read_iterator_context { - size_t buflen; - size_t count; - key_serial_t *buffer; -}; - -static int keyring_read_iterator(const void *object, void *data) -{ - struct keyring_read_iterator_context *ctx =3D data; - const struct key *key =3D keyring_ptr_to_key(object); - - kenter("{%s,%d},,{%zu/%zu}", - key->type->name, key->serial, ctx->count, ctx->buflen); - - if (ctx->count >=3D ctx->buflen) - return 1; - - *ctx->buffer++ =3D key->serial; - ctx->count +=3D sizeof(key->serial); - return 0; -} - /* * Read a list of key IDs from the keyring's contents in binary form * @@ -503,7 +438,10 @@ static int keyring_read_iterator(const void *object, v= oid *data) static long keyring_read(const struct key *keyring, char *buffer, size_t buflen) { - struct keyring_read_iterator_context ctx; + struct keyring_index *links =3D keyring_index_locked(keyring); + key_serial_t *serials =3D (key_serial_t *)buffer; + struct keyring_link *link; + size_t count =3D 0; long ret; =20 kenter("{%d},,%zu", key_serial(keyring), buflen); @@ -511,25 +449,22 @@ static long keyring_read(const struct key *keyring, if (buflen & (sizeof(key_serial_t) - 1)) return -EINVAL; =20 - /* Copy as many key IDs as fit into the buffer */ - if (buffer && buflen) { - ctx.buffer =3D (key_serial_t *)buffer; - ctx.buflen =3D buflen; - ctx.count =3D 0; - ret =3D assoc_array_iterate(&keyring->keys, - keyring_read_iterator, &ctx); - if (ret < 0) { - kleave(" =3D %ld [iterate]", ret); - return ret; + if (buffer && buflen && links) { + list_for_each_entry(link, &links->list, list) { + if (count =3D=3D buflen / sizeof(*serials)) + break; + + serials[count++] =3D keyring_link_key(link)->serial; + cond_resched(); } } =20 - /* Return the size of the buffer needed */ - ret =3D keyring->keys.nr_leaves_on_tree * sizeof(key_serial_t); + ret =3D links ? links->nr * sizeof(key_serial_t) : 0; if (ret <=3D buflen) kleave("=3D %ld [ok]", ret); else kleave("=3D %ld [buffer too small]", ret); + return ret; } =20 @@ -593,10 +528,9 @@ bool key_default_cmp(const struct key *key, /* * Iteration function to consider each key found. */ -static int keyring_search_iterator(const void *object, void *iterator_data) +static int keyring_search_iterator(const struct key *key, void *iterator_d= ata) { struct keyring_search_context *ctx =3D iterator_data; - const struct key *key =3D keyring_ptr_to_key(object); unsigned long kflags =3D READ_ONCE(key->flags); short state =3D key_read_state(key); =20 @@ -663,19 +597,78 @@ static int keyring_search_iterator(const void *object= , void *iterator_data) /* * Search inside a keyring for a key. We can search by walking to it * directly based on its index-key or we can iterate over the entire - * tree looking for it, based on the match function. + * list looking for it, based on the match function. */ static int search_keyring(struct key *keyring, struct keyring_search_conte= xt *ctx) { if (ctx->match_data.lookup_type =3D=3D KEYRING_SEARCH_LOOKUP_DIRECT) { - const void *object; + struct keyring_link *link; + struct key *key; + + link =3D keyring_find_link(rcu_dereference(keyring->index), + &ctx->index_key); + if (!link) + return 0; + key =3D keyring_link_key(link); + return ctx->iterator(key, ctx); + } + + return keyring_iterate(keyring, ctx->iterator, ctx); +} =20 - object =3D assoc_array_find(&keyring->keys, - &keyring_assoc_array_ops, - &ctx->index_key); - return object ? ctx->iterator(object, ctx) : 0; +/* + * Depth-first search of @keyring and its nested keyrings. + */ +static int search_keyring_tree(struct key *keyring, + struct keyring_search_context *ctx, int depth) +{ + struct keyring_index *links; + struct keyring_link *link; + int ret; + + if (keyring->flags & ((1 << KEY_FLAG_INVALIDATED) | + (1 << KEY_FLAG_REVOKED))) + return 0; + + if (search_keyring(keyring, ctx)) + goto found; + + if (!(ctx->flags & KEYRING_SEARCH_RECURSE)) + return 0; + links =3D rcu_dereference(keyring->index); + if (!links) + return 0; + + list_for_each_entry_rcu(link, &links->list, list) { + struct key *key =3D keyring_link_key(link); + + if (key->type !=3D &key_type_keyring) + break; + if (depth >=3D KEYRING_SEARCH_MAX_DEPTH) { + if (!(ctx->flags & KEYRING_SEARCH_DETECT_TOO_DEEP)) + return 0; + ctx->result =3D ERR_PTR(-ELOOP); + return -ELOOP; + } + + if (!(ctx->flags & KEYRING_SEARCH_NO_CHECK_PERM) && + key_task_permission(make_key_ref(key, ctx->possessed), + ctx->cred, KEY_NEED_SEARCH) < 0) + continue; + + ret =3D search_keyring_tree(key, ctx, depth + 1); + if (ret < 0) + return ret; + if (ret) + goto found; } - return assoc_array_iterate(&keyring->keys, ctx->iterator, ctx); + + return 0; + +found: + if (!(ctx->flags & KEYRING_SEARCH_NO_UPDATE_TIME)) + keyring->last_used_at =3D ctx->now; + return 1; } =20 /* @@ -685,17 +678,7 @@ static int search_keyring(struct key *keyring, struct = keyring_search_context *ct static bool search_nested_keyrings(struct key *keyring, struct keyring_search_context *ctx) { - struct { - struct key *keyring; - struct assoc_array_node *node; - int slot; - } stack[KEYRING_SEARCH_MAX_DEPTH]; - - struct assoc_array_shortcut *shortcut; - struct assoc_array_node *node; - struct assoc_array_ptr *ptr; struct key *key; - int sp =3D 0, slot; =20 kenter("{%d},{%s,%s}", keyring->serial, @@ -713,9 +696,9 @@ static bool search_nested_keyrings(struct key *keyring, * and whether it is valid or not. */ if (ctx->match_data.lookup_type =3D=3D KEYRING_SEARCH_LOOKUP_ITERATE || - keyring_compare_object(keyring, &ctx->index_key)) { + keyring_index_key_equal(&keyring->index_key, &ctx->index_key)) { ctx->skipped_ret =3D 2; - switch (ctx->iterator(keyring_key_to_ptr(keyring), ctx)) { + switch (ctx->iterator(keyring, ctx)) { case 1: goto found; case 2: @@ -727,152 +710,11 @@ static bool search_nested_keyrings(struct key *keyri= ng, =20 ctx->skipped_ret =3D 0; =20 - /* Start processing a new keyring */ -descend_to_keyring: - kdebug("descend to %d", keyring->serial); - if (keyring->flags & ((1 << KEY_FLAG_INVALIDATED) | - (1 << KEY_FLAG_REVOKED))) - goto not_this_keyring; - - /* Search through the keys in this keyring before its searching its - * subtrees. - */ - if (search_keyring(keyring, ctx)) - goto found; - - /* Then manually iterate through the keyrings nested in this one. - * - * Start from the root node of the index tree. Because of the way the - * hash function has been set up, keyrings cluster on the leftmost - * branch of the root node (root slot 0) or in the root node itself. - * Non-keyrings avoid the leftmost branch of the root entirely (root - * slots 1-15). - */ - if (!(ctx->flags & KEYRING_SEARCH_RECURSE)) - goto not_this_keyring; - - ptr =3D READ_ONCE(keyring->keys.root); - if (!ptr) - goto not_this_keyring; - - if (assoc_array_ptr_is_shortcut(ptr)) { - /* If the root is a shortcut, either the keyring only contains - * keyring pointers (everything clusters behind root slot 0) or - * doesn't contain any keyring pointers. - */ - shortcut =3D assoc_array_ptr_to_shortcut(ptr); - if ((shortcut->index_key[0] & ASSOC_ARRAY_FAN_MASK) !=3D 0) - goto not_this_keyring; - - ptr =3D READ_ONCE(shortcut->next_node); - node =3D assoc_array_ptr_to_node(ptr); - goto begin_node; - } - - node =3D assoc_array_ptr_to_node(ptr); - ptr =3D node->slots[0]; - if (!assoc_array_ptr_is_meta(ptr)) - goto begin_node; - -descend_to_node: - /* Descend to a more distal node in this keyring's content tree and go - * through that. - */ - kdebug("descend"); - if (assoc_array_ptr_is_shortcut(ptr)) { - shortcut =3D assoc_array_ptr_to_shortcut(ptr); - ptr =3D READ_ONCE(shortcut->next_node); - BUG_ON(!assoc_array_ptr_is_node(ptr)); - } - node =3D assoc_array_ptr_to_node(ptr); - -begin_node: - kdebug("begin_node"); - slot =3D 0; -ascend_to_node: - /* Go through the slots in a node */ - for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) { - ptr =3D READ_ONCE(node->slots[slot]); - - if (assoc_array_ptr_is_meta(ptr)) { - if (node->back_pointer || - assoc_array_ptr_is_shortcut(ptr)) - goto descend_to_node; - } - - if (!keyring_ptr_is_keyring(ptr)) - continue; - - key =3D keyring_ptr_to_key(ptr); - - if (sp >=3D KEYRING_SEARCH_MAX_DEPTH) { - if (ctx->flags & KEYRING_SEARCH_DETECT_TOO_DEEP) { - ctx->result =3D ERR_PTR(-ELOOP); - return false; - } - goto not_this_keyring; - } - - /* Search a nested keyring */ - if (!(ctx->flags & KEYRING_SEARCH_NO_CHECK_PERM) && - key_task_permission(make_key_ref(key, ctx->possessed), - ctx->cred, KEY_NEED_SEARCH) < 0) - continue; - - /* stack the current position */ - stack[sp].keyring =3D keyring; - stack[sp].node =3D node; - stack[sp].slot =3D slot; - sp++; - - /* begin again with the new keyring */ - keyring =3D key; - goto descend_to_keyring; - } - - /* We've dealt with all the slots in the current node, so now we need - * to ascend to the parent and continue processing there. - */ - ptr =3D READ_ONCE(node->back_pointer); - slot =3D node->parent_slot; - - if (ptr && assoc_array_ptr_is_shortcut(ptr)) { - shortcut =3D assoc_array_ptr_to_shortcut(ptr); - ptr =3D READ_ONCE(shortcut->back_pointer); - slot =3D shortcut->parent_slot; - } - if (!ptr) - goto not_this_keyring; - node =3D assoc_array_ptr_to_node(ptr); - slot++; - - /* If we've ascended to the root (zero backpointer), we must have just - * finished processing the leftmost branch rather than the root slots - - * so there can't be any more keyrings for us to find. - */ - if (node->back_pointer) { - kdebug("ascend %d", slot); - goto ascend_to_node; - } - - /* The keyring we're looking at was disqualified or didn't contain a - * matching key. - */ -not_this_keyring: - kdebug("not_this_keyring %d", sp); - if (sp <=3D 0) { + if (search_keyring_tree(keyring, ctx, 0) <=3D 0) { kleave(" =3D false"); return false; } =20 - /* Resume the processing of a keyring higher up in the tree */ - sp--; - keyring =3D stack[sp].keyring; - node =3D stack[sp].node; - slot =3D stack[sp].slot + 1; - kdebug("ascend to %d [%d]", keyring->serial, slot); - goto ascend_to_node; - /* We found a viable match */ found: key =3D key_ref_to_ptr(ctx->result); @@ -880,8 +722,6 @@ static bool search_nested_keyrings(struct key *keyring, if (!(ctx->flags & KEYRING_SEARCH_NO_UPDATE_TIME)) { key->last_used_at =3D ctx->now; keyring->last_used_at =3D ctx->now; - while (sp > 0) - stack[--sp].keyring->last_used_at =3D ctx->now; } kleave(" =3D true"); return true; @@ -1128,8 +968,8 @@ EXPORT_SYMBOL(keyring_restrict); key_ref_t find_key_to_update(key_ref_t keyring_ref, const struct keyring_index_key *index_key) { + struct keyring_link *link; struct key *keyring, *key; - const void *object; =20 keyring =3D key_ref_to_ptr(keyring_ref); =20 @@ -1137,17 +977,16 @@ key_ref_t find_key_to_update(key_ref_t keyring_ref, keyring->serial, index_key->type->name, index_key->description); =20 guard(rcu)(); - object =3D assoc_array_find(&keyring->keys, &keyring_assoc_array_ops, - index_key); + link =3D keyring_find_link(rcu_dereference(keyring->index), index_key); =20 - if (object) + if (link) goto found; =20 kleave(" =3D NULL"); return NULL; =20 found: - key =3D keyring_ptr_to_key(object); + key =3D keyring_link_key(link); if (key->flags & ((1 << KEY_FLAG_INVALIDATED) | (1 << KEY_FLAG_REVOKED))) { kleave(" =3D NULL [x]"); @@ -1217,11 +1056,10 @@ struct key *find_keyring_by_name(const char *name, = bool uid_keyring) return keyring; } =20 -static int keyring_detect_cycle_iterator(const void *object, +static int keyring_detect_cycle_iterator(const struct key *key, void *iterator_data) { struct keyring_search_context *ctx =3D iterator_data; - const struct key *key =3D keyring_ptr_to_key(object); =20 kenter("{%d}", key->serial); =20 @@ -1317,56 +1155,94 @@ int __key_move_lock(struct key *l_keyring, struct k= ey *u_keyring, return 0; } =20 +static struct keyring_index *keyring_get_index(struct key *keyring) +{ + struct keyring_index *links =3D keyring_index_locked(keyring); + int ret; + + if (links) + return links; + + links =3D kzalloc_obj(struct keyring_index); + if (!links) + return ERR_PTR(-ENOMEM); + ret =3D rhashtable_init(&links->ht, &keyring_link_params); + if (ret < 0) { + kfree(links); + return ERR_PTR(ret); + } + + INIT_LIST_HEAD(&links->list); + INIT_RCU_WORK(&links->rcu_work, keyring_index_free_work); + rcu_assign_pointer(keyring->index, links); + return links; +} + /* * Preallocate memory so that a key can be linked into to a keyring. */ int __key_link_begin(struct key *keyring, const struct keyring_index_key *index_key, - struct assoc_array_edit **_edit) + struct keyring_edit *edit) { - struct assoc_array_edit *edit; + struct keyring_link *link __free(kfree) =3D NULL; + struct keyring_link *replace; + struct keyring_index *links; int ret; =20 kenter("%d,%s,%s,", keyring->serial, index_key->type->name, index_key->description); =20 - BUG_ON(index_key->desc_len =3D=3D 0); - BUG_ON(*_edit !=3D NULL); + if (WARN_ON(index_key->desc_len =3D=3D 0) || WARN_ON(edit->new)) + return -EINVAL; =20 - *_edit =3D NULL; + edit->new =3D NULL; + edit->old =3D NULL; =20 ret =3D -EKEYREVOKED; if (test_bit(KEY_FLAG_REVOKED, &keyring->flags)) goto error; =20 - /* Create an edit script that will insert/replace the key in the - * keyring tree. - */ - edit =3D assoc_array_insert(&keyring->keys, - &keyring_assoc_array_ops, - index_key, - NULL); - if (IS_ERR(edit)) { - ret =3D PTR_ERR(edit); + links =3D keyring_get_index(keyring); + if (IS_ERR(links)) { + ret =3D PTR_ERR(links); goto error; } =20 + ret =3D -ENOMEM; + link =3D kzalloc_obj(struct keyring_link); + if (!link) + goto error; + link->hash =3D index_key->hash; + + replace =3D keyring_find_link(links, index_key); /* If we're not replacing a link in-place then we're going to need some * extra quota. */ - if (!edit->dead_leaf) { + if (!replace) { ret =3D key_payload_reserve(keyring, keyring->datalen + KEYQUOTA_LINK_BYTES); if (ret < 0) - goto error_cancel; + goto error; + + do { + ret =3D rhashtable_insert_fast(&links->ht, &link->node, + keyring_link_params); + if (ret =3D=3D -EBUSY) + fsleep(100); + } while (ret =3D=3D -EBUSY); + if (ret < 0) { + key_payload_reserve(keyring, + keyring->datalen - KEYQUOTA_LINK_BYTES); + goto error; + } } =20 - *_edit =3D edit; + edit->new =3D no_free_ptr(link); + edit->old =3D replace; kleave(" =3D 0"); return 0; =20 -error_cancel: - assoc_array_cancel_edit(edit); error: kleave(" =3D %d", ret); return ret; @@ -1395,13 +1271,35 @@ int __key_link_check_live_key(struct key *keyring, = struct key *key) * holds at most one link to any given key of a particular type+description * combination. */ -void __key_link(struct key *keyring, struct key *key, - struct assoc_array_edit **_edit) +void __key_link(struct key *keyring, struct key *key, struct keyring_edit = *edit) { + struct keyring_index *index =3D keyring_index_locked(keyring); + int ret; + __key_get(key); - assoc_array_insert_set_object(*_edit, keyring_key_to_ptr(key)); - assoc_array_apply_edit(*_edit); - *_edit =3D NULL; + rcu_assign_pointer(edit->new->key, key); + + if (edit->old) { + ret =3D rhashtable_replace_fast(&index->ht, &edit->old->node, + &edit->new->node, keyring_link_params); + if (WARN_ON(ret)) { + key_put(key); + return; + } + + list_replace_rcu(&edit->old->list, &edit->new->list); + call_rcu(&edit->old->rcu, keyring_link_free_rcu); + } else { + if (key->type =3D=3D &key_type_keyring) + list_add_rcu(&edit->new->list, &index->list); + else + list_add_tail_rcu(&edit->new->list, &index->list); + + WRITE_ONCE(index->nr, index->nr + 1); + } + + edit->new =3D NULL; + edit->old =3D NULL; notify_key(keyring, NOTIFY_KEY_LINKED, key_serial(key)); } =20 @@ -1412,20 +1310,31 @@ void __key_link(struct key *keyring, struct key *ke= y, */ void __key_link_end(struct key *keyring, const struct keyring_index_key *index_key, - struct assoc_array_edit *edit) + struct keyring_edit *edit) __releases(&keyring->sem) __releases(&keyring_serialise_link_lock) { + struct keyring_link *link =3D edit->new; + BUG_ON(index_key->type =3D=3D NULL); kenter("%d,%s,", keyring->serial, index_key->type->name); =20 - if (edit) { - if (!edit->dead_leaf) { + if (link) { + if (!edit->old) { key_payload_reserve(keyring, keyring->datalen - KEYQUOTA_LINK_BYTES); + WARN_ON(rhashtable_remove_fast(&keyring_index_locked(keyring)->ht, + &link->node, + keyring_link_params)); + call_rcu(&link->rcu, keyring_link_free_rcu); + } else { + kfree(link); } - assoc_array_cancel_edit(edit); + + edit->new =3D NULL; + edit->old =3D NULL; } + up_write(&keyring->sem); =20 if (index_key->type =3D=3D &key_type_keyring) @@ -1455,9 +1364,9 @@ static int __key_link_check_restriction(struct key *k= eyring, struct key *key) * of the user's key data quota to hold the link. * * Returns 0 if successful, -ENOTDIR if the keyring isn't a keyring, - * -EKEYREVOKED if the keyring has been revoked, -ENFILE if the keyring is - * full, -EDQUOT if there is insufficient key data quota remaining to add - * another link or -ENOMEM if there's insufficient memory. + * -EKEYREVOKED if the keyring has been revoked, -EDQUOT if there is insuf= ficient + * key data quota remaining to add another link or -ENOMEM if there's + * insufficient memory. * * It is assumed that the caller has checked that it is permitted for a li= nk to * be made (the keyring should have Write permission and the key Link @@ -1465,7 +1374,7 @@ static int __key_link_check_restriction(struct key *k= eyring, struct key *key) */ int key_link(struct key *keyring, struct key *key) { - struct assoc_array_edit *edit =3D NULL; + struct keyring_edit edit =3D {}; int ret; =20 kenter("{%d,%d}", keyring->serial, refcount_read(&keyring->usage)); @@ -1489,7 +1398,7 @@ int key_link(struct key *keyring, struct key *key) __key_link(keyring, key, &edit); =20 error_end: - __key_link_end(keyring, &key->index_key, edit); + __key_link_end(keyring, &key->index_key, &edit); error: kleave(" =3D %d {%d,%d}", ret, keyring->serial, refcount_read(&keyring->u= sage)); return ret; @@ -1513,27 +1422,21 @@ static int __key_unlink_lock(struct key *keyring) * Begin the process of unlinking a key from a keyring. */ static int __key_unlink_begin(struct key *keyring, struct key *key, - struct assoc_array_edit **_edit) + struct keyring_link **edit) { - struct assoc_array_edit *edit; - const void *object; + struct keyring_link *link; =20 - BUG_ON(*_edit !=3D NULL); + if (WARN_ON(*edit)) + return -EINVAL; =20 - object =3D assoc_array_find(&keyring->keys, &keyring_assoc_array_ops, - &key->index_key); - if (!object || keyring_ptr_to_key(object) !=3D key) + link =3D keyring_find_link(keyring_index_locked(keyring), &key->index_key= ); + if (!link) return -ENOENT; =20 - edit =3D assoc_array_delete(&keyring->keys, &keyring_assoc_array_ops, - &key->index_key); - if (IS_ERR(edit)) - return PTR_ERR(edit); - - if (!edit) + if (keyring_link_key(link) !=3D key) return -ENOENT; =20 - *_edit =3D edit; + *edit =3D link; return 0; } =20 @@ -1541,27 +1444,22 @@ static int __key_unlink_begin(struct key *keyring, = struct key *key, * Apply an unlink change. */ static void __key_unlink(struct key *keyring, struct key *key, - struct assoc_array_edit **_edit) + struct keyring_link *link) { - assoc_array_apply_edit(*_edit); + struct keyring_index *index =3D keyring_index_locked(keyring); + int ret; + + ret =3D rhashtable_remove_fast(&index->ht, &link->node, keyring_link_para= ms); + if (WARN_ON(ret)) + return; + + list_del_rcu(&link->list); + WRITE_ONCE(index->nr, index->nr - 1); + call_rcu(&link->rcu, keyring_link_free_rcu); notify_key(keyring, NOTIFY_KEY_UNLINKED, key_serial(key)); - *_edit =3D NULL; key_payload_reserve(keyring, keyring->datalen - KEYQUOTA_LINK_BYTES); } =20 -/* - * Finish unlinking a key from to a keyring. - */ -static void __key_unlink_end(struct key *keyring, - struct key *key, - struct assoc_array_edit *edit) - __releases(&keyring->sem) -{ - if (edit) - assoc_array_cancel_edit(edit); - up_write(&keyring->sem); -} - /** * key_unlink - Unlink the first link to a key from a keyring. * @keyring: The keyring to remove the link from. @@ -1571,9 +1469,8 @@ static void __key_unlink_end(struct key *keyring, * * This function will write-lock the keyring's semaphore. * - * Returns 0 if successful, -ENOTDIR if the keyring isn't a keyring, -ENOE= NT if - * the key isn't linked to by the keyring or -ENOMEM if there's insufficie= nt - * memory. + * Returns 0 if successful, -ENOTDIR if the keyring isn't a keyring or -EN= OENT if + * the key isn't linked to by the keyring. * * It is assumed that the caller has checked that it is permitted for a li= nk to * be removed (the keyring should have Write permission; no permissions are @@ -1581,7 +1478,7 @@ static void __key_unlink_end(struct key *keyring, */ int key_unlink(struct key *keyring, struct key *key) { - struct assoc_array_edit *edit =3D NULL; + struct keyring_link *edit =3D NULL; int ret; =20 key_check(keyring); @@ -1593,8 +1490,8 @@ int key_unlink(struct key *keyring, struct key *key) =20 ret =3D __key_unlink_begin(keyring, key, &edit); if (ret =3D=3D 0) - __key_unlink(keyring, key, &edit); - __key_unlink_end(keyring, key, edit); + __key_unlink(keyring, key, edit); + up_write(&keyring->sem); return ret; } EXPORT_SYMBOL(key_unlink); @@ -1614,11 +1511,10 @@ EXPORT_SYMBOL(key_unlink); * some of the user's key data quota to hold the link on @to_keyring. * * Returns 0 if successful, -ENOTDIR if either keyring isn't a keyring, - * -EKEYREVOKED if either keyring has been revoked, -ENFILE if the second - * keyring is full, -EDQUOT if there is insufficient key data quota remain= ing - * to add another link or -ENOMEM if there's insufficient memory. If - * KEYCTL_MOVE_EXCL is set, then -EEXIST will be returned if there's alrea= dy a - * matching key in @to_keyring. + * -EKEYREVOKED if either keyring has been revoked, -EDQUOT if there is + * insufficient key data quota remaining to add another link or -ENOMEM if + * there's insufficient memory. If KEYCTL_MOVE_EXCL is set, then -EEXIST = will + * be returned if there's already a matching key in @to_keyring. * * It is assumed that the caller has checked that it is permitted for a li= nk to * be made (the keyring should have Write permission and the key Link @@ -1629,7 +1525,8 @@ int key_move(struct key *key, struct key *to_keyring, unsigned int flags) { - struct assoc_array_edit *from_edit =3D NULL, *to_edit =3D NULL; + struct keyring_link *from_edit =3D NULL; + struct keyring_edit to_edit =3D {}; int ret; =20 kenter("%d,%d,%d", key->serial, from_keyring->serial, to_keyring->serial); @@ -1652,7 +1549,7 @@ int key_move(struct key *key, goto error; =20 ret =3D -EEXIST; - if (to_edit->dead_leaf && (flags & KEYCTL_MOVE_EXCL)) + if (to_edit.old && (flags & KEYCTL_MOVE_EXCL)) goto error; =20 ret =3D __key_link_check_restriction(to_keyring, key); @@ -1662,11 +1559,11 @@ int key_move(struct key *key, if (ret < 0) goto error; =20 - __key_unlink(from_keyring, key, &from_edit); + __key_unlink(from_keyring, key, from_edit); __key_link(to_keyring, key, &to_edit); error: - __key_link_end(to_keyring, &key->index_key, to_edit); - __key_unlink_end(from_keyring, key, from_edit); + __key_link_end(to_keyring, &key->index_key, &to_edit); + up_write(&from_keyring->sem); out: kleave(" =3D %d", ret); return ret; @@ -1683,27 +1580,17 @@ EXPORT_SYMBOL(key_move); */ int keyring_clear(struct key *keyring) { - struct assoc_array_edit *edit; - int ret; - if (keyring->type !=3D &key_type_keyring) return -ENOTDIR; =20 down_write(&keyring->sem); =20 - edit =3D assoc_array_clear(&keyring->keys, &keyring_assoc_array_ops); - if (IS_ERR(edit)) { - ret =3D PTR_ERR(edit); - } else { - if (edit) - assoc_array_apply_edit(edit); - notify_key(keyring, NOTIFY_KEY_CLEARED, 0); - key_payload_reserve(keyring, 0); - ret =3D 0; - } + keyring_index_free(keyring); + notify_key(keyring, NOTIFY_KEY_CLEARED, 0); + key_payload_reserve(keyring, 0); =20 up_write(&keyring->sem); - return ret; + return 0; } EXPORT_SYMBOL(keyring_clear); =20 @@ -1714,30 +1601,12 @@ EXPORT_SYMBOL(keyring_clear); */ static void keyring_revoke(struct key *keyring) { - struct assoc_array_edit *edit; - - edit =3D assoc_array_clear(&keyring->keys, &keyring_assoc_array_ops); - if (!IS_ERR(edit)) { - if (edit) - assoc_array_apply_edit(edit); - key_payload_reserve(keyring, 0); - } + keyring_index_free(keyring); + key_payload_reserve(keyring, 0); } =20 -static bool keyring_gc_select_iterator(void *object, void *iterator_data) +static int keyring_gc_check_iterator(const struct key *key, void *iterator= _data) { - struct key *key =3D keyring_ptr_to_key(object); - time64_t *limit =3D iterator_data; - - if (key_is_dead(key, *limit)) - return false; - key_get(key); - return true; -} - -static int keyring_gc_check_iterator(const void *object, void *iterator_da= ta) -{ - const struct key *key =3D keyring_ptr_to_key(object); time64_t *limit =3D iterator_data; =20 key_check(key); @@ -1752,7 +1621,9 @@ static int keyring_gc_check_iterator(const void *obje= ct, void *iterator_data) */ void keyring_gc(struct key *keyring, time64_t limit) { - int result; + struct keyring_link *link, *tmp; + struct keyring_index *index; + int ret; =20 kenter("%x{%s}", keyring->serial, keyring->description ?: ""); =20 @@ -1761,11 +1632,7 @@ void keyring_gc(struct key *keyring, time64_t limit) goto dont_gc; =20 /* scan the keyring looking for dead keys */ - rcu_read_lock(); - result =3D assoc_array_iterate(&keyring->keys, - keyring_gc_check_iterator, &limit); - rcu_read_unlock(); - if (result =3D=3D true) + if (keyring_iterate(keyring, keyring_gc_check_iterator, &limit)) goto do_gc; =20 dont_gc: @@ -1774,8 +1641,23 @@ void keyring_gc(struct key *keyring, time64_t limit) =20 do_gc: down_write(&keyring->sem); - assoc_array_gc(&keyring->keys, &keyring_assoc_array_ops, - keyring_gc_select_iterator, &limit); + index =3D keyring_index_locked(keyring); + if (index) { + list_for_each_entry_safe(link, tmp, &index->list, list) { + if (!key_is_dead(keyring_link_key(link), limit)) + continue; + + ret =3D rhashtable_remove_fast(&index->ht, &link->node, + keyring_link_params); + if (WARN_ON(ret)) + break; + + list_del_rcu(&link->list); + WRITE_ONCE(index->nr, index->nr - 1); + call_rcu(&link->rcu, keyring_link_free_rcu); + } + } + up_write(&keyring->sem); kleave(" [gc]"); } diff --git a/security/keys/request_key.c b/security/keys/request_key.c index 22cd66a44da5..40fbcd15be43 100644 --- a/security/keys/request_key.c +++ b/security/keys/request_key.c @@ -372,7 +372,7 @@ static int construct_alloc_key(struct keyring_search_co= ntext *ctx, struct key_user *user, struct key **_key) { - struct assoc_array_edit *edit =3D NULL; + struct keyring_edit edit =3D {}; struct key *key; key_perm_t perm; key_ref_t key_ref; @@ -433,7 +433,7 @@ static int construct_alloc_key(struct keyring_search_co= ntext *ctx, =20 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 =3D key; kleave(" =3D 0 [%d]", key_serial(key)); @@ -452,7 +452,7 @@ static int construct_alloc_key(struct keyring_search_co= ntext *ctx, ret =3D __key_link_check_live_key(dest_keyring, key); if (ret =3D=3D 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_co= ntext *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); --=20 2.47.3 From nobody Thu Nov 5 05:11:18 2026 Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.remote-ip=100.103.45.18 ARC-Seal: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; cv=none; t=1793848464; b=aE0x0o+sRgL+l9eNFG3LXCv3mYuaXZ6m9n7XDUx6BHnnns992wWetiiiUolCs7VR2br+ JjY8vlSCUU8BLPeB6PmzNBixiThqe/2/PXRc4qjwovHN81oCoCjJoqWD7AnEMP3aBoAsB pmFOXhEBDBRW5nsVytWITb3P0MdUpux3f5Uv+QM8Dp1pbSGM4eYo+KDO0DwdUaTD0DO3f wyap9ur8MZBxwLn4i1Fg5stcyTYUYwFYHZFaB73HYximRtm8lM1r5Otwep4HW64DvkpbH 5F4CuZRVZp4+rhE16VQZy22366w2IKFCgl8wZz9Nvcck3XR9bL1iTaACXaaAp63eoLA== ARC-Message-Signature: i=1; d=subspace.kernel.org; s=arc20261015; a=rsa-sha256; c=relaxed/relaxed; t=1793848464; h=Received:DKIM-Signature:From:To:Cc:Subject:Date:Message-ID:X-Mailer: In-Reply-To:References:MIME-Version:Content-Type: Content-Transfer-Encoding; bh=SmMr07ewPGCdwkiiIKgDx5nYeyqw/2DFjGDHoPbfUgo=; b=5NzYZa2Zsgh1vuygKV20eFg4qo+9eMoM/e6FXg7CJd7p+9mtxyOHi5Ok6Gew6GAIcTOn VOt4fKwWGZsdgd3o3Ffo66ngGpiJ9LtC+8aHazE94I3JWJtjqs7sr3d1OD/lxxGPSfr7y 34ymKLZ8EQfDuiKdMxQj4SClrXfhxyWNRKG2xJjPBdsQgsL5AINWHqzQjI7jPjwt7yQUb U0IstcR6mA/BMFk6/30gTrCNAPTJodTbKAC/EaqsV3EO3+8IRu5sge4To7sG4agAB8n2V fQ7A9SoVDkSYvHUFBXLdc3N8EJgVYc67mayP1OQcYQqDJLvqNSfzdigVfjNeIaqm7YQ== ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass header.d=kernel.org header.i=@kernel.org header.a=rsa-sha256 header.s=k20260515 header.b=X2fsPlJG; arc=none smtp.remote-ip=100.103.45.18 Received: from smtp.kernel.org (quasi.space.kernel.org [100.103.45.18]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (prime256v1)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with UTF8SMTPS id 4FFEE606A337; Thu, 5 Nov 2026 03:14:23 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key, unprotected) header.d=kernel.org header.i=@kernel.org header.a=rsa-sha256 header.s=k20260515 header.b=X2fsPlJG Received: by smtp.kernel.org (Postfix) with UTF8SMTPSA id 9A7D21F00A16; Thu, 5 Nov 2026 03:14:21 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kernel.org; s=k20260515; t=1793848462; bh=SmMr07ewPGCdwkiiIKgDx5nYeyqw/2DFjGDHoPbfUgo=; h=From:To:Cc:Subject:Date:In-Reply-To:References; b=X2fsPlJGQ6wANGiQl/BBJ3Wm739/wKvnmwqrIv3wnLqbRn1MWIIYz2qFPShk3TrSt eMFdt8GGGwOQVT9qgv3pEAXEylg0A+EHX7aDCN7OBJgeMXU4e4+HgdwamwVMfmWWFO uVotM1Rvat5B9AHDxg90QuEyB3DIh+PX3aEp+8l5KYGT1bEPoVhVRs7TBXUS+/Gci9 lhM4FTsVehFYS+ZhI5g6TY/wNgUtlEeCu++QFTfdykcyBeVbvDFJDbVpSCq+vqN8BJ t4Z6O+QZRfTwCMsGImLSJXAsmYWFANugXcht+fcmQsRehRBgUdHW5EAM46tFLU9hWM Yv3vwiSelWM/A== From: Jarkko Sakkinen To: David Howells Cc: Jarkko Sakkinen , bpf@vger.kernel.org, dm-devel@lists.linux.dev, fsverity@lists.linux.dev, keyrings@vger.kernel.org, linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org, linux-kselftest@vger.kernel.org, linux-security-module@vger.kernel.org, Alasdair Kergon , Alexei Starovoitov , Alex Shi , Andrew Morton , Andrii Nakryiko , Benjamin Marzinski , Daniel Borkmann , Dongliang Mu , Eduard Zingerman , Emil Tsalapatis , Eric Biggers , Ihor Solodrai , James Morris , Jiri Olsa , Jonathan Corbet , Kumar Kartikeya Dwivedi , Martin KaFai Lau , Mike Snitzer , Mikulas Patocka , Paul Moore , Randy Dunlap , "Serge E. Hallyn" , Shuah Khan , Song Liu , "Theodore Y. Ts'o" , Yanteng Si , Yonghong Song Subject: [PATCH v5 3/3] lib: Remove assoc_array Date: Thu, 5 Nov 2026 05:14:01 +0200 Message-ID: <20261105031401.956609-4-jarkko@kernel.org> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20261105031401.956609-1-jarkko@kernel.org> References: <20261105031401.956609-1-jarkko@kernel.org> X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Post: List-Help: List-Subscribe: List-Unsubscribe: List-Owner: Precedence: list MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable As assoc_array has no longer in-kernel users, remove assoc_array implementation, includes and documentation. Reviewed-by: Eric Biggers Signed-off-by: Jarkko Sakkinen --- 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.r= st delete mode 100644 include/linux/assoc_array.h delete mode 100644 include/linux/assoc_array_priv.h delete mode 100644 lib/assoc_array.c diff --git a/Documentation/core-api/assoc_array.rst b/Documentation/core-ap= i/assoc_array.rst deleted file mode 100644 index 19d89f92bf8d..000000000000 --- a/Documentation/core-api/assoc_array.rst +++ /dev/null @@ -1,564 +0,0 @@ -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D -Generic Associative Array Implementation -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - -Overview -=3D=3D=3D=3D=3D=3D=3D=3D - -This associative array implementation is an object container with the foll= owing -properties: - -1. Objects are opaque pointers. The implementation does not care where th= ey - 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. Th= is - 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 n= ot - 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 t= he - RCU readlock is being held by the thread doing the look up. - -The implementation uses a tree of 16-pointer nodes internally that are ind= exed -on each level by nibbles from the index key in the same manner as in a rad= ix -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 -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - -The public API can be found in ````. 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 lat= er be -applied to effect the changes without risking ``ENOMEM``. This retains the -preallocated metadata blocks that will be installed in the internal tree a= nd -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 d= one -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 barri= ers - 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 functi= on, - 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 retu= rn - ``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 match= es - 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 p= eriod - 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 retur= ns - an edit script that must be applied. ``-ENOMEM`` is returned in the ca= se 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 retur= ns - an edit script that must be applied. ``-ENOMEM`` is returned in the ca= se of - an out-of-memory error. ``NULL`` will be returned if the specified obj= ect - 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 retur= ns - an edit script that must be applied. ``-ENOMEM`` is returned in the ca= se 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 travers= ing - 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 k= ept. - 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 iterat= ion - to reduce the number of nodes in it. - - The ``iterator_data`` is passed directly to ``iterator()`` and is other= wise - ignored by the function. - - The function will return ``0`` if successful and ``-ENOMEM`` if there w= asn't - enough memory. - - It is possible for other threads to iterate over or search the array un= der - 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 len= gth -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 nod= es -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 level= s 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 -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - -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 - =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D = =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - 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: - - =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D - KEY PREFIX NODE - =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D - 137* D - 138* E - 13[0-69-f]* C - 1[0-24-f]* B - e6* G - e[0-57-f]* F - [02-df]* A - =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D - -So, for instance, keys with the following example index keys will be found= in -the appropriate nodes: - - =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D = =3D=3D=3D=3D - INDEX KEY PREFIX NODE - =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D = =3D=3D=3D=3D - 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 - =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D = =3D=3D=3D=3D - -To save memory, if a node can hold all the leaves in its portion of keyspa= ce, -then the node will have all those leaves in it and will not have any metad= ata -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 ma= tches -the metadata key prefix must be in the subtree that the metadata pointer p= oints -to. - -In the above example list of index keys, node A will contain: - - =3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - SLOT CONTENT INDEX KEY (PREFIX) - =3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - 1 PTR TO NODE B 1* - any LEAF 9431809de993ba - any LEAF b4542910809cd - e PTR TO NODE F e* - any LEAF f3842239082 - =3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - -and node B: - - =3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - SLOT CONTENT INDEX KEY (PREFIX) - =3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - 3 PTR TO NODE C 13* - any LEAF 1458952489 - =3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - - -Shortcuts ---------- - -Shortcuts are metadata records that jump over a piece of keyspace. A shor= tcut -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 exampl= e, -the tree contains at least 17 nodes all with key prefix ``1111``. The -insertion algorithm will insert a shortcut to skip over the ``1111`` keysp= ace -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 t= he -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 co= mmon -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 numbe= r of -slot in that parent that points to it. None-recursive iteration uses thes= e 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 tric= ky. - - -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 un= til - 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 t= he - 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 n= ew - 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 t= oo. - - 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 pass= ed, -so as long as anyone doing walking or iteration holds the RCU read lock, t= he -old superstructure should not go away on them. diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/inde= x.rst index 92f91c6a0d79..d56c60663b0c 100644 --- a/Documentation/core-api/index.rst +++ b/Documentation/core-api/index.rst @@ -38,7 +38,6 @@ Library functionality that is used throughout the kernel. kobject kref cleanup - assoc_array folio_queue xarray maple_tree diff --git a/Documentation/translations/zh_CN/core-api/assoc_array.rst b/Do= cumentation/translations/zh_CN/core-api/assoc_array.rst deleted file mode 100644 index 3649bf0d1488..000000000000 --- a/Documentation/translations/zh_CN/core-api/assoc_array.rst +++ /dev/null @@ -1,473 +0,0 @@ -.. include:: ../disclaimer-zh_CN.rst - -:Original: Documentation/core-api/assoc_array.rst - -:=E7=BF=BB=E8=AF=91: - - =E5=8F=B8=E5=BB=B6=E8=85=BE Yanteng Si - -:=E6=A0=A1=E8=AF=91: - - - -.. _cn_core-api_assoc_array: - -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D -=E9=80=9A=E7=94=A8=E5=85=B3=E8=81=94=E6=95=B0=E7=BB=84=E7=9A=84=E5=AE=9E= =E7=8E=B0 -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - -=E7=AE=80=E4=BB=8B -=3D=3D=3D=3D - -=E8=BF=99=E4=B8=AA=E5=85=B3=E8=81=94=E6=95=B0=E7=BB=84=E7=9A=84=E5=AE=9E= =E7=8E=B0=E6=98=AF=E4=B8=80=E4=B8=AA=E5=85=B7=E6=9C=89=E4=BB=A5=E4=B8=8B=E5= =B1=9E=E6=80=A7=E7=9A=84=E5=AF=B9=E8=B1=A1=E5=AE=B9=E5=99=A8: - -1. =E5=AF=B9=E8=B1=A1=E6=98=AF=E4=B8=8D=E9=80=8F=E6=98=8E=E7=9A=84=E6=8C= =87=E9=92=88=E3=80=82=E8=AF=A5=E5=AE=9E=E7=8E=B0=E4=B8=8D=E5=85=B3=E5=BF=83= =E5=AE=83=E4=BB=AC=E6=8C=87=E5=90=91=E5=93=AA=E9=87=8C=EF=BC=88=E5=A6=82=E6= =9E=9C=E6=9C=89=E7=9A=84=E8=AF=9D=EF=BC=89=E6=88=96=E5=AE=83=E4=BB=AC=E6=8C= =87=E5=90=91=E4=BB=80=E4=B9=88=EF=BC=88=E5=A6=82=E6=9E=9C=E6=9C=89=E7=9A=84 - =E8=AF=9D=EF=BC=89=E3=80=82 - - .. note:: - - =E6=8C=87=E5=90=91=E5=AF=B9=E8=B1=A1=E7=9A=84=E6=8C=87=E9=92=88 *=E5= =BF=85=E9=A1=BB* =E5=9C=A8=E6=9C=80=E5=B0=8F=E6=9C=89=E6=95=88=E4=BD=8D=E4= =B8=BA=E9=9B=B6=E3=80=82 - -2. =E5=AF=B9=E8=B1=A1=E4=B8=8D=E9=9C=80=E8=A6=81=E5=8C=85=E5=90=AB=E4=BE= =9B=E6=95=B0=E7=BB=84=E4=BD=BF=E7=94=A8=E7=9A=84=E9=93=BE=E6=8E=A5=E5=9D=97= =E3=80=82=E8=BF=99=E5=85=81=E8=AE=B8=E4=B8=80=E4=B8=AA=E5=AF=B9=E8=B1=A1=E5= =90=8C=E6=97=B6=E4=BD=8D=E4=BA=8E=E5=A4=9A=E4=B8=AA=E6=95=B0=E7=BB=84=E4=B8= =AD=E3=80=82=E7=9B=B8=E5=8F=8D=EF=BC=8C=E6=95=B0=E7=BB=84=E6=98=AF - =E7=94=B1=E6=8C=87=E5=90=91=E5=AF=B9=E8=B1=A1=E7=9A=84=E5=85=83=E6=95= =B0=E6=8D=AE=E5=9D=97=E7=BB=84=E6=88=90=E7=9A=84=E3=80=82 - -3. =E5=AF=B9=E8=B1=A1=E9=9C=80=E8=A6=81=E7=B4=A2=E5=BC=95=E9=94=AE=E6=9D= =A5=E5=AE=9A=E4=BD=8D=E5=AE=83=E4=BB=AC=E5=9C=A8=E9=98=B5=E5=88=97=E4=B8=AD= =E7=9A=84=E4=BD=8D=E7=BD=AE=E3=80=82 - -4. =E7=B4=A2=E5=BC=95=E9=94=AE=E5=BF=85=E9=A1=BB=E6=98=AF=E5=94=AF=E4=B8= =80=E7=9A=84=E3=80=82=E6=8F=92=E5=85=A5=E4=B8=80=E4=B8=AA=E4=B8=8E=E5=B7=B2= =E7=BB=8F=E5=9C=A8=E6=95=B0=E7=BB=84=E4=B8=AD=E7=9A=84=E4=B8=94=E5=85=B7=E6= =9C=89=E7=9B=B8=E5=90=8C=E9=94=AE=E5=80=BC=E7=9A=84=E5=AF=B9=E8=B1=A1=E5=B0= =86=E5=8F=96=E4=BB=A3=E6=97=A7=E7=9A=84=E5=AF=B9=E8=B1=A1=E3=80=82 - -5. =E7=B4=A2=E5=BC=95=E9=94=AE=E5=8F=AF=E4=BB=A5=E6=98=AF=E4=BB=BB=E4=BD= =95=E9=95=BF=E5=BA=A6=EF=BC=8C=E4=B9=9F=E5=8F=AF=E4=BB=A5=E6=98=AF=E4=B8=8D= =E5=90=8C=E7=9A=84=E9=95=BF=E5=BA=A6=E3=80=82 - -6. =E7=B4=A2=E5=BC=95=E9=94=AE=E5=BA=94=E8=AF=A5=E5=9C=A8=E6=97=A9=E6=9C= =9F=E5=B0=B1=E5=AF=B9=E9=95=BF=E5=BA=A6=E8=BF=9B=E8=A1=8C=E7=BC=96=E7=A0=81= =EF=BC=8C=E5=8D=B3=E5=9C=A8=E4=BB=BB=E4=BD=95=E7=94=B1=E4=BA=8E=E9=95=BF=E5= =BA=A6=E5=BC=95=E8=B5=B7=E7=9A=84=E5=8F=98=E5=8C=96=E5=87=BA=E7=8E=B0=E4=B9= =8B=E5=89=8D=E3=80=82 - -7. =E7=B4=A2=E5=BC=95=E9=94=AE=E5=8F=AF=E4=BB=A5=E5=8C=85=E6=8B=AC=E4=B8= =80=E4=B8=AA=E5=93=88=E5=B8=8C=E5=80=BC=EF=BC=8C=E4=BB=A5=E4=BE=BF=E5=B0=86= =E5=AF=B9=E8=B1=A1=E5=88=86=E6=95=A3=E5=88=B0=E6=95=B4=E4=B8=AA=E6=95=B0=E7= =BB=84=E4=B8=AD=E3=80=82 - -8. =E8=AF=A5=E6=95=B0=E7=BB=84=E5=8F=AF=E4=BB=A5=E8=BF=AD=E4=BB=A3=E3=80= =82=E5=AF=B9=E8=B1=A1=E4=B8=8D=E4=B8=80=E5=AE=9A=E4=BC=9A=E6=8C=89=E7=B4=A2= =E5=BC=95=E9=94=AE=E7=9A=84=E9=A1=BA=E5=BA=8F=E5=87=BA=E7=8E=B0=E3=80=82 - -9. =E6=95=B0=E7=BB=84=E5=8F=AF=E4=BB=A5=E5=9C=A8=E8=A2=AB=E4=BF=AE=E6=94= =B9=E7=9A=84=E6=97=B6=E5=80=99=E8=BF=9B=E8=A1=8C=E8=BF=AD=E4=BB=A3=EF=BC=8C= =E5=8F=AA=E8=A6=81RCU=E7=9A=84=E8=AF=BB=E9=94=81=E8=A2=AB=E8=BF=AD=E4=BB=A3= =E5=99=A8=E6=8C=81=E6=9C=89=E3=80=82=E7=84=B6=E8=80=8C=EF=BC=8C=E8=AF=B7=E6= =B3=A8=E6=84=8F=EF=BC=8C=E5=9C=A8=E8=BF=99=E7=A7=8D=E6=83=85 - =E5=86=B5=E4=B8=8B=EF=BC=8C=E4=B8=80=E4=BA=9B=E5=AF=B9=E8=B1=A1=E5=8F= =AF=E8=83=BD=E4=BC=9A=E8=A2=AB=E7=9C=8B=E5=88=B0=E4=B8=8D=E6=AD=A2=E4=B8=80= =E6=AC=A1=E3=80=82=E5=A6=82=E6=9E=9C=E8=BF=99=E6=98=AF=E4=B8=AA=E9=97=AE=E9= =A2=98=EF=BC=8C=E8=BF=AD=E4=BB=A3=E5=99=A8=E5=BA=94=E8=AF=A5=E9=94=81=E5=AE= =9A=E4=BB=A5=E9=98=B2=E6=AD=A2=E4=BF=AE=E6=94=B9=E3=80=82=E7=84=B6 - =E8=80=8C=EF=BC=8C=E9=99=A4=E9=9D=9E=E5=88=A0=E9=99=A4=EF=BC=8C=E5=90= =A6=E5=88=99=E5=AF=B9=E8=B1=A1=E4=B8=8D=E4=BC=9A=E8=A2=AB=E9=94=99=E8=BF=87= =E3=80=82 - -10. =E6=95=B0=E7=BB=84=E4=B8=AD=E7=9A=84=E5=AF=B9=E8=B1=A1=E5=8F=AF=E4=BB= =A5=E9=80=9A=E8=BF=87=E5=85=B6=E7=B4=A2=E5=BC=95=E9=94=AE=E8=BF=9B=E8=A1=8C= =E6=9F=A5=E8=AF=A2=E3=80=82 - -11. =E5=BD=93=E6=95=B0=E7=BB=84=E8=A2=AB=E4=BF=AE=E6=94=B9=E6=97=B6=EF=BC= =8C=E5=AF=B9=E8=B1=A1=E5=8F=AF=E4=BB=A5=E8=A2=AB=E6=9F=A5=E8=AF=A2=EF=BC=8C= =E5=89=8D=E6=8F=90=E6=98=AF=E8=BF=9B=E8=A1=8C=E6=9F=A5=E8=AF=A2=E7=9A=84=E7= =BA=BF=E7=A8=8B=E6=8C=81=E6=9C=89RCU=E7=9A=84=E8=AF=BB=E9=94=81=E3=80=82 - -=E8=AF=A5=E5=AE=9E=E7=8E=B0=E5=9C=A8=E5=86=85=E9=83=A8=E4=BD=BF=E7=94=A8= =E4=BA=86=E4=B8=80=E6=A3=B5=E7=94=B116=E4=B8=AA=E6=8C=87=E9=92=88=E8=8A=82= =E7=82=B9=E7=BB=84=E6=88=90=E7=9A=84=E6=A0=91=EF=BC=8C=E8=BF=99=E4=BA=9B=E8= =8A=82=E7=82=B9=E5=9C=A8=E6=AF=8F=E4=B8=80=E5=B1=82=E9=83=BD=E7=94=B1=E7=B4= =A2=E5=BC=95=E9=94=AE=E7=9A=84=E5=B0=8F=E6=95=B0=E7=82=B9=E8=BF=9B=E8=A1=8C= =E7=B4=A2 -=E5=BC=95=EF=BC=8C=E5=85=B6=E6=96=B9=E5=BC=8F=E4=B8=8E=E5=9F=BA=E6=95=B0= =E6=A0=91=E7=9B=B8=E5=90=8C=E3=80=82=E4=B8=BA=E4=BA=86=E6=8F=90=E9=AB=98=E5= =86=85=E5=AD=98=E6=95=88=E7=8E=87=EF=BC=8C=E5=8F=AF=E4=BB=A5=E6=94=BE=E7=BD= =AE=E5=BF=AB=E6=8D=B7=E9=94=AE=EF=BC=8C=E4=BB=A5=E8=B7=B3=E8=BF=87=E6=9C=AC= =E6=9D=A5=E6=98=AF=E4=B8=80=E7=B3=BB=E5=88=97=E5=8D=95=E5=8D=A0=E8=8A=82=E7= =82=B9=E7=9A=84=E5=9C=B0 -=E6=96=B9=E3=80=82=E6=AD=A4=E5=A4=96=EF=BC=8C=E8=8A=82=E7=82=B9=E5=B0=86= =E5=8F=B6=E5=AD=90=E5=AF=B9=E8=B1=A1=E6=8C=87=E9=92=88=E6=89=93=E5=8C=85=E5= =88=B0=E8=8A=82=E7=82=B9=E7=9A=84=E7=A9=BA=E9=97=B2=E7=A9=BA=E9=97=B4=E4=B8= =AD=EF=BC=8C=E8=80=8C=E4=B8=8D=E6=98=AF=E5=81=9A=E4=B8=80=E4=B8=AA=E9=A2=9D= =E5=A4=96=E7=9A=84=E5=88=86=E6=94=AF=EF=BC=8C=E7=9B=B4=E5=88=B0=E6=9C=89=E5= =AF=B9=E8=B1=A1 -=E9=9C=80=E8=A6=81=E8=A2=AB=E6=B7=BB=E5=8A=A0=E5=88=B0=E4=B8=80=E4=B8=AA= =E5=AE=8C=E6=95=B4=E7=9A=84=E8=8A=82=E7=82=B9=E4=B8=AD=E3=80=82 - -=E5=85=AC=E7=94=A8API -=3D=3D=3D=3D=3D=3D=3D - -=E5=85=AC=E7=94=A8API=E5=8F=AF=E4=BB=A5=E5=9C=A8 ````= =E4=B8=AD=E6=89=BE=E5=88=B0=E3=80=82=E5=85=B3=E8=81=94=E6=95=B0=E7=BB=84= =E7=9A=84=E6=A0=B9=E6=98=AF=E4=BB=A5=E4=B8=8B=E7=BB=93=E6=9E=84:: - - struct assoc_array { - ... - }; - -=E8=AF=A5=E4=BB=A3=E7=A0=81=E6=98=AF=E9=80=9A=E8=BF=87=E5=90=AF=E7=94=A8 `= `CONFIG_ASSOCIATIVE_ARRAY`` =E6=9D=A5=E9=80=89=E6=8B=A9=E7=9A=84=EF=BC=8C= =E4=BB=A5:: - - ./script/config -e ASSOCIATIVE_ARRAY - - -=E7=BC=96=E8=BE=91=E8=84=9A=E6=9C=AC --------- - -=E6=8F=92=E5=85=A5=E5=92=8C=E5=88=A0=E9=99=A4=E5=8A=9F=E8=83=BD=E4=BC=9A= =E4=BA=A7=E7=94=9F=E4=B8=80=E4=B8=AA=E2=80=9C=E7=BC=96=E8=BE=91=E8=84=9A=E6= =9C=AC=E2=80=9D=EF=BC=8C=E4=BB=A5=E5=90=8E=E5=8F=AF=E4=BB=A5=E5=BA=94=E7=94= =A8=E8=BF=99=E4=B8=AA=E8=84=9A=E6=9C=AC=E6=9D=A5=E5=AE=9E=E7=8E=B0=E6=9B=B4= =E6=94=B9=EF=BC=8C=E8=80=8C=E4=B8=8D=E4=BC=9A=E9=80=A0=E6=88=90 ``ENOMEM`` -=E9=A3=8E=E9=99=A9=E3=80=82=E8=BF=99=E4=BF=9D=E7=95=99=E4=BA=86=E5=B0=86= =E8=A2=AB=E5=AE=89=E8=A3=85=E5=9C=A8=E5=86=85=E9=83=A8=E6=A0=91=E4=B8=AD=E7= =9A=84=E9=A2=84=E5=88=86=E9=85=8D=E7=9A=84=E5=85=83=E6=95=B0=E6=8D=AE=E5=9D= =97=EF=BC=8C=E5=B9=B6=E8=B7=9F=E8=B8=AA=E5=BA=94=E7=94=A8=E8=84=9A=E6=9C=AC= =E6=97=B6=E5=B0=86=E4=BB=8E=E6=A0=91=E4=B8=AD=E5=88=A0=E9=99=A4=E7=9A=84=E5= =85=83=E6=95=B0 -=E6=8D=AE=E5=9D=97=E3=80=82 - -=E5=9C=A8=E8=84=9A=E6=9C=AC=E5=BA=94=E7=94=A8=E5=90=8E=EF=BC=8C=E8=BF=99= =E4=B9=9F=E8=A2=AB=E7=94=A8=E6=9D=A5=E8=B7=9F=E8=B8=AA=E6=AD=BB=E5=9D=97=E5= =92=8C=E6=AD=BB=E5=AF=B9=E8=B1=A1=EF=BC=8C=E4=BB=A5=E4=BE=BF=E4=BB=A5=E5=90= =8E=E5=8F=AF=E4=BB=A5=E9=87=8A=E6=94=BE=E5=AE=83=E4=BB=AC=E3=80=82=E9=87=8A= =E6=94=BE=E6=98=AF=E5=9C=A8RCU=E5=AE=BD=E9=99=90=E6=9C=9F=E8=BF=87=E5=90=8E -=E8=BF=9B=E8=A1=8C=E7=9A=84--=E5=9B=A0=E6=AD=A4=E5=85=81=E8=AE=B8=E8=AE=BF= =E9=97=AE=E5=8A=9F=E8=83=BD=E5=9C=A8RCU=E8=AF=BB=E9=94=81=E4=B8=8B=E8=BF=9B= =E8=A1=8C=E3=80=82 - -=E8=84=9A=E6=9C=AC=E5=9C=A8API=E4=B9=8B=E5=A4=96=E6=98=BE=E7=A4=BA=E4=B8= =BA=E4=B8=80=E4=B8=AA=E7=B1=BB=E5=9E=8B=E4=B8=BA:: - - struct assoc_array_edit; - -=E6=9C=89=E4=B8=A4=E4=B8=AA=E5=A4=84=E7=90=86=E8=84=9A=E6=9C=AC=E7=9A=84= =E5=8A=9F=E8=83=BD: - -1. =E5=BA=94=E7=94=A8=E4=B8=80=E4=B8=AA=E7=BC=96=E8=BE=91=E8=84=9A=E6=9C= =AC:: - - void assoc_array_apply_edit(struct assoc_array_edit *edit); - -=E8=BF=99=E5=B0=86=E6=89=A7=E8=A1=8C=E7=BC=96=E8=BE=91=E5=8A=9F=E8=83=BD= =EF=BC=8C=E6=8F=92=E5=80=BC=E5=90=84=E7=A7=8D=E5=86=99=E5=B1=8F=E9=9A=9C=EF= =BC=8C=E4=BB=A5=E5=85=81=E8=AE=B8=E5=9C=A8RCU=E8=AF=BB=E9=94=81=E4=B8=8B=E7= =9A=84=E8=AE=BF=E9=97=AE=E7=BB=A7=E7=BB=AD=E8=BF=9B=E8=A1=8C=E3=80=82=E7=84= =B6=E5=90=8E=EF=BC=8C=E7=BC=96=E8=BE=91=E8=84=9A=E6=9C=AC=E5=B0=86=E8=A2=AB -=E4=BC=A0=E9=80=92=E7=BB=99 ``call_rcu()`` =EF=BC=8C=E4=BB=A5=E9=87=8A=E6= =94=BE=E5=AE=83=E5=92=8C=E5=AE=83=E6=89=80=E6=8C=87=E5=90=91=E7=9A=84=E4=BB= =BB=E4=BD=95=E6=AD=BB=E7=9A=84=E4=B8=9C=E8=A5=BF=E3=80=82 - -2. Cancel an edit script:: - - void assoc_array_cancel_edit(struct assoc_array_edit *edit); - -=E8=BF=99=E5=B0=86=E7=AB=8B=E5=8D=B3=E9=87=8A=E6=94=BE=E7=BC=96=E8=BE=91= =E8=84=9A=E6=9C=AC=E5=92=8C=E6=89=80=E6=9C=89=E9=A2=84=E5=88=86=E9=85=8D=E7= =9A=84=E5=86=85=E5=AD=98=E3=80=82=E5=A6=82=E6=9E=9C=E8=BF=99=E6=98=AF=E4=B8= =BA=E4=BA=86=E6=8F=92=E5=85=A5=EF=BC=8C=E6=96=B0=E7=9A=84=E5=AF=B9=E8=B1=A1= =E4=B8=8D=E4=BC=9A=E8=A2=AB=E8=BF=99=E4=B8=AA=E5=87=BD=E6=95=B0=E9=87=8A=E6= =94=BE=EF=BC=8C -=E8=80=8C=E6=98=AF=E5=BF=85=E9=A1=BB=E7=94=B1=E8=B0=83=E7=94=A8=E8=80=85= =E9=87=8A=E6=94=BE=E3=80=82 - -=E8=BF=99=E4=BA=9B=E5=87=BD=E6=95=B0=E4=BF=9D=E8=AF=81=E4=B8=8D=E4=BC=9A= =E5=A4=B1=E8=B4=A5=E3=80=82 - - -=E6=93=8D=E4=BD=9C=E8=A1=A8 ------- - -=E5=90=84=E7=A7=8D=E5=8A=9F=E8=83=BD=E9=87=87=E7=94=A8=E4=BA=86=E4=B8=80= =E4=B8=AA=E6=93=8D=E4=BD=9C=E8=A1=A8:: - - struct assoc_array_ops { - ... - }; - -=E8=BF=99=E6=8C=87=E5=87=BA=E4=BA=86=E4=B8=80=E4=BA=9B=E6=96=B9=E6=B3=95= =EF=BC=8C=E6=89=80=E6=9C=89=E8=BF=99=E4=BA=9B=E6=96=B9=E6=B3=95=E9=83=BD=E9= =9C=80=E8=A6=81=E6=8F=90=E4=BE=9B: - -1. =E4=BB=8E=E8=B0=83=E7=94=A8=E8=80=85=E6=95=B0=E6=8D=AE=E4=B8=AD=E8=8E= =B7=E5=8F=96=E7=B4=A2=E5=BC=95=E9=94=AE=E7=9A=84=E4=B8=80=E4=B8=AA=E5=9D=97= :: - - unsigned long (*get_key_chunk)(const void *index_key, int level); - -=E8=BF=99=E5=BA=94=E8=AF=A5=E8=BF=94=E5=9B=9E=E4=B8=80=E4=B8=AA=E7=94=B1= =E8=B0=83=E7=94=A8=E8=80=85=E6=8F=90=E4=BE=9B=E7=9A=84=E7=B4=A2=E5=BC=95=E9= =94=AE=E7=9A=84=E5=9D=97=EF=BC=8C=E4=BB=8Elevel=E5=8F=82=E6=95=B0=E7=BB=99= =E5=87=BA=E7=9A=84 *=E6=AF=94=E7=89=B9* =E4=BD=8D=E7=BD=AE=E5=BC=80=E5=A7= =8B=E3=80=82level=E5=8F=82=E6=95=B0=E5=B0=86 -=E6=98=AF ``ASSOC_ARRAY_KEY_CHUNK_SIZE`` =E7=9A=84=E5=80=8D=E6=95=B0=EF=BC= =8C=E8=AF=A5=E5=87=BD=E6=95=B0=E5=BA=94=E8=BF=94=E5=9B=9E ``ASSOC_ARRAY_KEY= _CHUNK_SIZE`` -=E4=BD=8D=E3=80=82=E4=B8=8D=E5=8F=AF=E8=83=BD=E5=87=BA=E7=8E=B0=E9=94=99= =E8=AF=AF=E3=80=82 - - -2. =E8=8E=B7=E5=8F=96=E4=B8=80=E4=B8=AA=E5=AF=B9=E8=B1=A1=E7=9A=84=E7=B4= =A2=E5=BC=95=E9=94=AE=E7=9A=84=E4=B8=80=E4=B8=AA=E5=9D=97:: - - unsigned long (*get_object_key_chunk)(const void *object, int level); - -=E5=92=8C=E5=89=8D=E9=9D=A2=E7=9A=84=E5=87=BD=E6=95=B0=E4=B8=80=E6=A0=B7= =EF=BC=8C=E4=BD=86=E6=98=AF=E4=BB=8E=E6=95=B0=E7=BB=84=E4=B8=AD=E7=9A=84=E4= =B8=80=E4=B8=AA=E5=AF=B9=E8=B1=A1=E8=80=8C=E4=B8=8D=E6=98=AF=E4=BB=8E=E8=B0= =83=E7=94=A8=E8=80=85=E6=8F=90=E4=BE=9B=E7=9A=84=E7=B4=A2=E5=BC=95=E9=94=AE= =E4=B8=AD=E8=8E=B7=E5=8F=96=E6=95=B0=E6=8D=AE=E3=80=82 - - -3. =E7=9C=8B=E7=9C=8B=E8=BF=99=E6=98=AF=E5=90=A6=E6=98=AF=E6=88=91=E4=BB= =AC=E8=A6=81=E6=89=BE=E7=9A=84=E5=AF=B9=E8=B1=A1:: - - bool (*compare_object)(const void *object, const void *index_key); - -=E5=B0=86=E5=AF=B9=E8=B1=A1=E4=B8=8E=E4=B8=80=E4=B8=AA=E7=B4=A2=E5=BC=95= =E9=94=AE=E8=BF=9B=E8=A1=8C=E6=AF=94=E8=BE=83=EF=BC=8C=E5=A6=82=E6=9E=9C=E5= =8C=B9=E9=85=8D=E5=88=99=E8=BF=94=E5=9B=9E ``true`` =EF=BC=8C=E4=B8=8D=E5= =8C=B9=E9=85=8D=E5=88=99=E8=BF=94=E5=9B=9E ``false`` =E3=80=82 - - -4. =E5=AF=B9=E4=B8=A4=E4=B8=AA=E5=AF=B9=E8=B1=A1=E7=9A=84=E7=B4=A2=E5=BC= =95=E9=94=AE=E8=BF=9B=E8=A1=8C=E6=AF=94=E8=BE=83:: - - int (*diff_objects)(const void *object, const void *index_key); - -=E8=BF=94=E5=9B=9E=E6=8C=87=E5=AE=9A=E5=AF=B9=E8=B1=A1=E7=9A=84=E7=B4=A2= =E5=BC=95=E9=94=AE=E4=B8=8E=E7=BB=99=E5=AE=9A=E7=B4=A2=E5=BC=95=E9=94=AE=E4= =B8=8D=E5=90=8C=E7=9A=84=E6=AF=94=E7=89=B9=E4=BD=8D=E7=BD=AE=EF=BC=8C=E5=A6= =82=E6=9E=9C=E5=AE=83=E4=BB=AC=E7=9B=B8=E5=90=8C=EF=BC=8C=E5=88=99=E8=BF=94= =E5=9B=9E-1=E3=80=82 - - -5. =E9=87=8A=E6=94=BE=E4=B8=80=E4=B8=AA=E5=AF=B9=E8=B1=A1:: - - void (*free_object)(void *object); - -=E9=87=8A=E6=94=BE=E6=8C=87=E5=AE=9A=E7=9A=84=E5=AF=B9=E8=B1=A1=E3=80=82= =E6=B3=A8=E6=84=8F=EF=BC=8C=E8=BF=99=E5=8F=AF=E8=83=BD=E6=98=AF=E5=9C=A8=E8= =B0=83=E7=94=A8 ``assoc_array_apply_edit()`` =E5=90=8E=E7=9A=84=E4=B8=80=E4= =B8=AARCU=E5=AE=BD=E9=99=90=E6=9C=9F=E5=86=85 -=E8=B0=83=E7=94=A8=E7=9A=84=EF=BC=8C=E6=89=80=E4=BB=A5=E5=9C=A8=E6=A8=A1= =E5=9D=97=E5=8D=B8=E8=BD=BD=E6=97=B6=E5=8F=AF=E8=83=BD=E9=9C=80=E8=A6=81 ``= synchronize_rcu()`` =E3=80=82 - - -=E6=93=8D=E6=8E=A7=E5=87=BD=E6=95=B0 --------- - -=E6=9C=89=E4=B8=80=E4=BA=9B=E5=87=BD=E6=95=B0=E7=94=A8=E4=BA=8E=E6=93=8D= =E6=8E=A7=E5=85=B3=E8=81=94=E6=95=B0=E7=BB=84: - -1. =E5=88=9D=E5=A7=8B=E5=8C=96=E4=B8=80=E4=B8=AA=E5=85=B3=E8=81=94=E6=95= =B0=E7=BB=84:: - - void assoc_array_init(struct assoc_array *array); - -=E8=BF=99=E5=B0=86=E5=88=9D=E5=A7=8B=E5=8C=96=E4=B8=80=E4=B8=AA=E5=85=B3= =E8=81=94=E6=95=B0=E7=BB=84=E7=9A=84=E5=9F=BA=E7=A1=80=E7=BB=93=E6=9E=84=E3= =80=82=E5=AE=83=E4=B8=8D=E4=BC=9A=E5=A4=B1=E8=B4=A5=E3=80=82 - - -2. =E5=9C=A8=E4=B8=80=E4=B8=AA=E5=85=B3=E8=81=94=E6=95=B0=E7=BB=84=E4=B8= =AD=E6=8F=92=E5=85=A5/=E6=9B=BF=E6=8D=A2=E4=B8=80=E4=B8=AA=E5=AF=B9=E8=B1= =A1:: - - struct assoc_array_edit * - assoc_array_insert(struct assoc_array *array, - const struct assoc_array_ops *ops, - const void *index_key, - void *object); - -=E8=BF=99=E5=B0=86=E6=8A=8A=E7=BB=99=E5=AE=9A=E7=9A=84=E5=AF=B9=E8=B1=A1= =E6=8F=92=E5=85=A5=E6=95=B0=E7=BB=84=E4=B8=AD=E3=80=82=E6=B3=A8=E6=84=8F=EF= =BC=8C=E6=8C=87=E9=92=88=E7=9A=84=E6=9C=80=E5=B0=8F=E6=9C=89=E6=95=88=E4=BD= =8D=E5=BF=85=E9=A1=BB=E6=98=AF0=EF=BC=8C=E5=9B=A0=E4=B8=BA=E5=AE=83=E8=A2= =AB=E7=94=A8=E6=9D=A5=E5=9C=A8=E5=86=85=E9=83=A8=E6=A0=87=E8=AE=B0=E6=8C=87= =E9=92=88=E7=9A=84=E7=B1=BB -=E5=9E=8B=E3=80=82 - -=E5=A6=82=E6=9E=9C=E8=AF=A5=E9=94=AE=E5=B7=B2=E7=BB=8F=E5=AD=98=E5=9C=A8= =E4=B8=80=E4=B8=AA=E5=AF=B9=E8=B1=A1=EF=BC=8C=E9=82=A3=E4=B9=88=E5=AE=83=E5= =B0=86=E8=A2=AB=E6=96=B0=E7=9A=84=E5=AF=B9=E8=B1=A1=E6=89=80=E5=8F=96=E4=BB= =A3=EF=BC=8C=E6=97=A7=E7=9A=84=E5=AF=B9=E8=B1=A1=E5=B0=86=E8=A2=AB=E8=87=AA= =E5=8A=A8=E9=87=8A=E6=94=BE=E3=80=82 - -``index_key`` =E5=8F=82=E6=95=B0=E5=BA=94=E6=8C=81=E6=9C=89=E7=B4=A2=E5=BC= =95=E9=94=AE=E4=BF=A1=E6=81=AF=EF=BC=8C=E5=B9=B6=E5=9C=A8=E8=B0=83=E7=94=A8= OPP=E8=A1=A8=E4=B8=AD=E7=9A=84=E6=96=B9=E6=B3=95=E6=97=B6=E4=BC=A0=E9=80=92= =E7=BB=99=E5=AE=83=E4=BB=AC=E3=80=82 - -=E8=BF=99=E4=B8=AA=E5=87=BD=E6=95=B0=E4=B8=8D=E5=AF=B9=E6=95=B0=E7=BB=84= =E6=9C=AC=E8=BA=AB=E5=81=9A=E4=BB=BB=E4=BD=95=E6=94=B9=E5=8A=A8=EF=BC=8C=E8= =80=8C=E6=98=AF=E8=BF=94=E5=9B=9E=E4=B8=80=E4=B8=AA=E5=BF=85=E9=A1=BB=E5=BA= =94=E7=94=A8=E7=9A=84=E7=BC=96=E8=BE=91=E8=84=9A=E6=9C=AC=E3=80=82=E5=A6=82= =E6=9E=9C=E5=87=BA=E7=8E=B0=E5=86=85=E5=AD=98=E4=B8=8D=E8=B6=B3=E7=9A=84=E9= =94=99=E8=AF=AF=EF=BC=8C=E4=BC=9A -=E8=BF=94=E5=9B=9E ``-ENOMEM`` =E3=80=82 - -=E8=B0=83=E7=94=A8=E8=80=85=E5=BA=94=E4=B8=93=E9=97=A8=E9=94=81=E5=AE=9A= =E6=95=B0=E7=BB=84=E7=9A=84=E5=85=B6=E4=BB=96=E4=BF=AE=E6=94=B9=E5=99=A8=E3= =80=82 - - -3. =E4=BB=8E=E4=B8=80=E4=B8=AA=E5=85=B3=E8=81=94=E6=95=B0=E7=BB=84=E4=B8= =AD=E5=88=A0=E9=99=A4=E4=B8=80=E4=B8=AA=E5=AF=B9=E8=B1=A1:: - - struct assoc_array_edit * - assoc_array_delete(struct assoc_array *array, - const struct assoc_array_ops *ops, - const void *index_key); - -=E8=BF=99=E5=B0=86=E4=BB=8E=E6=95=B0=E7=BB=84=E4=B8=AD=E5=88=A0=E9=99=A4= =E4=B8=80=E4=B8=AA=E7=AC=A6=E5=90=88=E6=8C=87=E5=AE=9A=E6=95=B0=E6=8D=AE=E7= =9A=84=E5=AF=B9=E8=B1=A1=E3=80=82 - -``index_key`` =E5=8F=82=E6=95=B0=E5=BA=94=E6=8C=81=E6=9C=89=E7=B4=A2=E5=BC= =95=E9=94=AE=E4=BF=A1=E6=81=AF=EF=BC=8C=E5=B9=B6=E5=9C=A8=E8=B0=83=E7=94=A8= OPP=E8=A1=A8=E4=B8=AD=E7=9A=84=E6=96=B9=E6=B3=95=E6=97=B6=E4=BC=A0=E9=80=92= =E7=BB=99=E5=AE=83=E4=BB=AC=E3=80=82 - -=E8=BF=99=E4=B8=AA=E5=87=BD=E6=95=B0=E4=B8=8D=E5=AF=B9=E6=95=B0=E7=BB=84= =E6=9C=AC=E8=BA=AB=E5=81=9A=E4=BB=BB=E4=BD=95=E6=94=B9=E5=8A=A8=EF=BC=8C=E8= =80=8C=E6=98=AF=E8=BF=94=E5=9B=9E=E4=B8=80=E4=B8=AA=E5=BF=85=E9=A1=BB=E5=BA= =94=E7=94=A8=E7=9A=84=E7=BC=96=E8=BE=91=E8=84=9A=E6=9C=AC=E3=80=82 ``-ENOME= M`` =E5=9C=A8=E5=87=BA=E7=8E=B0=E5=86=85=E5=AD=98=E4=B8=8D=E8=B6=B3 -=E7=9A=84=E9=94=99=E8=AF=AF=E6=97=B6=E8=BF=94=E5=9B=9E=E3=80=82=E5=A6=82= =E6=9E=9C=E5=9C=A8=E6=95=B0=E7=BB=84=E4=B8=AD=E6=B2=A1=E6=9C=89=E6=89=BE=E5= =88=B0=E6=8C=87=E5=AE=9A=E7=9A=84=E5=AF=B9=E8=B1=A1=EF=BC=8C=E5=B0=86=E8=BF= =94=E5=9B=9E ``NULL`` =E3=80=82 - -=E8=B0=83=E7=94=A8=E8=80=85=E5=BA=94=E8=AF=A5=E5=AF=B9=E6=95=B0=E7=BB=84= =E7=9A=84=E5=85=B6=E4=BB=96=E4=BF=AE=E6=94=B9=E8=80=85=E8=BF=9B=E8=A1=8C=E4= =B8=93=E9=97=A8=E9=94=81=E5=AE=9A=E3=80=82 - - -4. =E4=BB=8E=E4=B8=80=E4=B8=AA=E5=85=B3=E8=81=94=E6=95=B0=E7=BB=84=E4=B8= =AD=E5=88=A0=E9=99=A4=E6=89=80=E6=9C=89=E5=AF=B9=E8=B1=A1:: - - struct assoc_array_edit * - assoc_array_clear(struct assoc_array *array, - const struct assoc_array_ops *ops); - -=E8=BF=99=E4=B8=AA=E5=87=BD=E6=95=B0=E5=88=A0=E9=99=A4=E4=BA=86=E4=B8=80= =E4=B8=AA=E5=85=B3=E8=81=94=E6=95=B0=E7=BB=84=E4=B8=AD=E7=9A=84=E6=89=80=E6= =9C=89=E5=AF=B9=E8=B1=A1=EF=BC=8C=E4=BD=BF=E5=85=B6=E5=AE=8C=E5=85=A8=E4=B8= =BA=E7=A9=BA=E3=80=82 - -=E8=BF=99=E4=B8=AA=E5=87=BD=E6=95=B0=E6=B2=A1=E6=9C=89=E5=AF=B9=E6=95=B0= =E7=BB=84=E6=9C=AC=E8=BA=AB=E5=81=9A=E4=BB=BB=E4=BD=95=E6=94=B9=E5=8A=A8=EF= =BC=8C=E8=80=8C=E6=98=AF=E8=BF=94=E5=9B=9E=E4=B8=80=E4=B8=AA=E5=BF=85=E9=A1= =BB=E5=BA=94=E7=94=A8=E7=9A=84=E7=BC=96=E8=BE=91=E8=84=9A=E6=9C=AC=E3=80=82= =E5=A6=82=E6=9E=9C=E5=87=BA=E7=8E=B0=E5=86=85=E5=AD=98=E4=B8=8D=E8=B6=B3 -=E7=9A=84=E9=94=99=E8=AF=AF=EF=BC=8C=E5=88=99=E8=BF=94=E5=9B=9E ``-ENOMEM`= ` =E3=80=82 - -=E8=B0=83=E7=94=A8=E8=80=85=E5=BA=94=E4=B8=93=E9=97=A8=E9=94=81=E5=AE=9A= =E6=95=B0=E7=BB=84=E7=9A=84=E5=85=B6=E4=BB=96=E4=BF=AE=E6=94=B9=E8=80=85=E3= =80=82 - - -5. =E9=94=80=E6=AF=81=E4=B8=80=E4=B8=AA=E5=85=B3=E8=81=94=E6=95=B0=E7=BB= =84=EF=BC=8C=E5=88=A0=E9=99=A4=E6=89=80=E6=9C=89=E5=AF=B9=E8=B1=A1:: - - void assoc_array_destroy(struct assoc_array *array, - const struct assoc_array_ops *ops); - -=E8=BF=99=E5=B0=86=E7=A0=B4=E5=9D=8F=E5=85=B3=E8=81=94=E6=95=B0=E7=BB=84= =E7=9A=84=E5=86=85=E5=AE=B9=EF=BC=8C=E4=BD=BF=E5=85=B6=E5=AE=8C=E5=85=A8=E4= =B8=BA=E7=A9=BA=E3=80=82=E5=9C=A8=E8=BF=99=E4=B8=AA=E5=87=BD=E6=95=B0=E9=94= =80=E6=AF=81=E6=95=B0=E7=BB=84=E7=9A=84=E5=90=8C=E6=97=B6=EF=BC=8C=E4=B8=8D= =E5=85=81=E8=AE=B8=E5=8F=A6=E4=B8=80=E4=B8=AA=E7=BA=BF=E7=A8=8B=E5=9C=A8RCU= =E8=AF=BB=E9=94=81 -=E4=B8=8B=E9=81=8D=E5=8E=86=E6=95=B0=E7=BB=84=EF=BC=8C=E5=9B=A0=E4=B8=BA= =E5=9C=A8=E5=86=85=E5=AD=98=E9=87=8A=E6=94=BE=E6=97=B6=E4=B8=8D=E6=89=A7=E8= =A1=8CRCU=E5=BB=B6=E8=BF=9F=EF=BC=8C=E8=BF=99=E9=9C=80=E8=A6=81=E5=88=86=E9= =85=8D=E5=86=85=E5=AD=98=E3=80=82 - -=E8=B0=83=E7=94=A8=E8=80=85=E5=BA=94=E8=AF=A5=E4=B8=93=E9=97=A8=E9=92=88= =E5=AF=B9=E6=95=B0=E7=BB=84=E7=9A=84=E5=85=B6=E4=BB=96=E4=BF=AE=E6=94=B9=E8= =80=85=E5=92=8C=E8=AE=BF=E9=97=AE=E8=80=85=E8=BF=9B=E8=A1=8C=E9=94=81=E5=AE= =9A=E3=80=82 - - -6. =E5=9E=83=E5=9C=BE=E5=9B=9E=E6=94=B6=E4=B8=80=E4=B8=AA=E5=85=B3=E8=81= =94=E6=95=B0=E7=BB=84:: - - int assoc_array_gc(struct assoc_array *array, - const struct assoc_array_ops *ops, - bool (*iterator)(void *object, void *iterator_data), - void *iterator_data); - -=E8=BF=99=E6=98=AF=E5=AF=B9=E4=B8=80=E4=B8=AA=E5=85=B3=E8=81=94=E6=95=B0= =E7=BB=84=E4=B8=AD=E7=9A=84=E5=AF=B9=E8=B1=A1=E8=BF=9B=E8=A1=8C=E8=BF=AD=E4= =BB=A3=EF=BC=8C=E5=B9=B6=E5=B0=86=E6=AF=8F=E4=B8=AA=E5=AF=B9=E8=B1=A1=E4=BC= =A0=E9=80=92=E7=BB=99 ``iterator()`` =E3=80=82=E5=A6=82=E6=9E=9C ``iterator= ()`` =E8=BF=94=E5=9B=9E -true=EF=BC=8C=E8=AF=A5=E5=AF=B9=E8=B1=A1=E8=A2=AB=E4=BF=9D=E7=95=99=E3=80= =82=E5=A6=82=E6=9E=9C=E5=AE=83=E8=BF=94=E5=9B=9E ``false`` =EF=BC=8C=E8=AF= =A5=E5=AF=B9=E8=B1=A1=E5=B0=86=E8=A2=AB=E9=87=8A=E6=94=BE=E3=80=82=E5=A6=82= =E6=9E=9C ``iterator()`` =E5=87=BD=E6=95=B0=E8=BF=94=E5=9B=9E ``true`` =EF= =BC=8C=E5=AE=83=E5=BF=85=E9=A1=BB -=E5=9C=A8=E8=BF=94=E5=9B=9E=E4=B9=8B=E5=89=8D=E5=AF=B9=E8=AF=A5=E5=AF=B9= =E8=B1=A1=E8=BF=9B=E8=A1=8C=E9=80=82=E5=BD=93=E7=9A=84 ``refcount`` =E9=80= =92=E5=A2=9E=E3=80=82 - -=E5=A6=82=E6=9E=9C=E5=8F=AF=E8=83=BD=E7=9A=84=E8=AF=9D=EF=BC=8C=E5=86=85= =E9=83=A8=E6=A0=91=E5=B0=86=E8=A2=AB=E6=89=93=E5=8C=85=E4=B8=8B=E6=9D=A5=EF= =BC=8C=E4=BD=9C=E4=B8=BA=E8=BF=AD=E4=BB=A3=E7=9A=84=E4=B8=80=E9=83=A8=E5=88= =86=EF=BC=8C=E4=BB=A5=E5=87=8F=E5=B0=91=E5=85=B6=E4=B8=AD=E7=9A=84=E8=8A=82= =E7=82=B9=E6=95=B0=E9=87=8F=E3=80=82 - -``iterator_data`` =E8=A2=AB=E7=9B=B4=E6=8E=A5=E4=BC=A0=E9=80=92=E7=BB=99 `= `iterator()`` =EF=BC=8C=E5=90=A6=E5=88=99=E4=BC=9A=E8=A2=AB=E5=87=BD=E6=95= =B0=E5=BF=BD=E7=95=A5=E3=80=82 - -=E5=A6=82=E6=9E=9C=E6=88=90=E5=8A=9F=EF=BC=8C=E8=AF=A5=E5=87=BD=E6=95=B0= =E5=B0=86=E8=BF=94=E5=9B=9E ``0`` =EF=BC=8C=E5=A6=82=E6=9E=9C=E6=B2=A1=E6= =9C=89=E8=B6=B3=E5=A4=9F=E7=9A=84=E5=86=85=E5=AD=98=EF=BC=8C=E5=88=99=E8=BF= =94=E5=9B=9E ``-ENOMEM`` =E3=80=82 - -=E5=9C=A8=E8=BF=99=E4=B8=AA=E5=87=BD=E6=95=B0=E6=89=A7=E8=A1=8C=E8=BF=87= =E7=A8=8B=E4=B8=AD=EF=BC=8C=E5=85=B6=E4=BB=96=E7=BA=BF=E7=A8=8B=E6=9C=89=E5= =8F=AF=E8=83=BD=E5=9C=A8RCU=E8=AF=BB=E9=94=81=E4=B8=8B=E8=BF=AD=E4=BB=A3=E6= =88=96=E6=90=9C=E7=B4=A2=E9=98=B5=E5=88=97=E3=80=82=E8=B0=83=E7=94=A8=E8=80= =85=E5=BA=94=E8=AF=A5=E4=B8=93=E9=97=A8=E9=92=88=E5=AF=B9=E6=95=B0=E7=BB=84= =E7=9A=84=E5=85=B6=E4=BB=96 -=E4=BF=AE=E6=94=B9=E8=80=85=E8=BF=9B=E8=A1=8C=E9=94=81=E5=AE=9A=E3=80=82 - - -=E8=AE=BF=E9=97=AE=E5=87=BD=E6=95=B0 --------- - -=E6=9C=89=E4=B8=A4=E4=B8=AA=E5=87=BD=E6=95=B0=E7=94=A8=E4=BA=8E=E8=AE=BF= =E9=97=AE=E4=B8=80=E4=B8=AA=E5=85=B3=E8=81=94=E6=95=B0=E7=BB=84: - -1. =E9=81=8D=E5=8E=86=E4=B8=80=E4=B8=AA=E5=85=B3=E8=81=94=E6=95=B0=E7=BB= =84=E4=B8=AD=E7=9A=84=E6=89=80=E6=9C=89=E5=AF=B9=E8=B1=A1:: - - int assoc_array_iterate(const struct assoc_array *array, - int (*iterator)(const void *object, - void *iterator_data), - void *iterator_data); - -=E8=BF=99=E5=B0=86=E6=95=B0=E7=BB=84=E4=B8=AD=E7=9A=84=E6=AF=8F=E4=B8=AA= =E5=AF=B9=E8=B1=A1=E4=BC=A0=E9=80=92=E7=BB=99=E8=BF=AD=E4=BB=A3=E5=99=A8=E5= =9B=9E=E8=B0=83=E5=87=BD=E6=95=B0=E3=80=82 ``iterator_data`` =E6=98=AF=E8= =AF=A5=E5=87=BD=E6=95=B0=E7=9A=84=E7=A7=81=E6=9C=89=E6=95=B0=E6=8D=AE=E3=80= =82 - -=E5=9C=A8=E6=95=B0=E7=BB=84=E8=A2=AB=E4=BF=AE=E6=94=B9=E7=9A=84=E5=90=8C= =E6=97=B6=EF=BC=8C=E5=8F=AF=E4=BB=A5=E5=9C=A8=E6=95=B0=E7=BB=84=E4=B8=8A=E4= =BD=BF=E7=94=A8=E8=BF=99=E4=B8=AA=E6=96=B9=E6=B3=95=EF=BC=8C=E5=89=8D=E6=8F= =90=E6=98=AFRCU=E8=AF=BB=E9=94=81=E8=A2=AB=E6=8C=81=E6=9C=89=E3=80=82=E5=9C= =A8=E8=BF=99=E7=A7=8D=E6=83=85=E5=86=B5=E4=B8=8B=EF=BC=8C=E8=BF=AD=E4=BB=A3= =E5=87=BD=E6=95=B0=E6=9C=89 -=E5=8F=AF=E8=83=BD=E4=B8=A4=E6=AC=A1=E7=9C=8B=E5=88=B0=E6=9F=90=E4=BA=9B= =E5=AF=B9=E8=B1=A1=E3=80=82=E5=A6=82=E6=9E=9C=E8=BF=99=E6=98=AF=E4=B8=AA=E9= =97=AE=E9=A2=98=EF=BC=8C=E9=82=A3=E4=B9=88=E4=BF=AE=E6=94=B9=E5=BA=94=E8=AF= =A5=E8=A2=AB=E9=94=81=E5=AE=9A=E3=80=82=E7=84=B6=E8=80=8C=EF=BC=8C=E8=BF=AD= =E4=BB=A3=E7=AE=97=E6=B3=95=E4=B8=8D=E5=BA=94=E8=AF=A5=E9=94=99=E8=BF=87=E4= =BB=BB=E4=BD=95=E5=AF=B9=E8=B1=A1=E3=80=82 - -=E5=A6=82=E6=9E=9C=E6=95=B0=E7=BB=84=E4=B8=AD=E6=B2=A1=E6=9C=89=E5=AF=B9= =E8=B1=A1=EF=BC=8C=E8=AF=A5=E5=87=BD=E6=95=B0=E5=B0=86=E8=BF=94=E5=9B=9E ``= 0`` =EF=BC=8C=E5=90=A6=E5=88=99=E5=B0=86=E8=BF=94=E5=9B=9E=E6=9C=80=E5=90= =8E=E4=B8=80=E6=AC=A1=E8=B0=83=E7=94=A8=E7=9A=84=E8=BF=AD=E4=BB=A3=E5=99=A8= =E5=87=BD=E6=95=B0=E7=9A=84=E7=BB=93=E6=9E=9C=E3=80=82=E5=A6=82=E6=9E=9C=E5= =AF=B9=E8=BF=AD=E4=BB=A3=E5=87=BD=E6=95=B0 -=E7=9A=84=E4=BB=BB=E4=BD=95=E8=B0=83=E7=94=A8=E5=AF=BC=E8=87=B4=E9=9D=9E= =E9=9B=B6=E8=BF=94=E5=9B=9E=EF=BC=8C=E8=BF=AD=E4=BB=A3=E7=AB=8B=E5=8D=B3=E5= =81=9C=E6=AD=A2=E3=80=82 - - -2. =E5=9C=A8=E4=B8=80=E4=B8=AA=E5=85=B3=E8=81=94=E6=95=B0=E7=BB=84=E4=B8= =AD=E5=AF=BB=E6=89=BE=E4=B8=80=E4=B8=AA=E5=AF=B9=E8=B1=A1:: - - void *assoc_array_find(const struct assoc_array *array, - const struct assoc_array_ops *ops, - const void *index_key); - -=E8=BF=99=E5=B0=86=E7=9B=B4=E6=8E=A5=E7=A9=BF=E8=BF=87=E6=95=B0=E7=BB=84= =E7=9A=84=E5=86=85=E9=83=A8=E6=A0=91=EF=BC=8C=E5=88=B0=E8=BE=BE=E7=B4=A2=E5= =BC=95=E9=94=AE=E6=89=80=E6=8C=87=E5=AE=9A=E7=9A=84=E5=AF=B9=E8=B1=A1=E3=80= =82 - -=E8=BF=99=E4=B8=AA=E5=87=BD=E6=95=B0=E5=8F=AF=E4=BB=A5=E5=9C=A8=E4=BF=AE= =E6=94=B9=E6=95=B0=E7=BB=84=E7=9A=84=E5=90=8C=E6=97=B6=E7=94=A8=E5=9C=A8=E6= =95=B0=E7=BB=84=E4=B8=8A=EF=BC=8C=E5=89=8D=E6=8F=90=E6=98=AFRCU=E8=AF=BB=E9= =94=81=E8=A2=AB=E6=8C=81=E6=9C=89=E3=80=82 - -=E5=A6=82=E6=9E=9C=E6=89=BE=E5=88=B0=E5=AF=B9=E8=B1=A1=EF=BC=8C=E8=AF=A5= =E5=87=BD=E6=95=B0=E5=B0=86=E8=BF=94=E5=9B=9E=E5=AF=B9=E8=B1=A1=EF=BC=88=E5= =B9=B6=E5=B0=86 ``*_type`` =E8=AE=BE=E7=BD=AE=E4=B8=BA=E5=AF=B9=E8=B1=A1=E7= =9A=84=E7=B1=BB=E5=9E=8B=EF=BC=89=EF=BC=8C=E5=A6=82=E6=9E=9C=E6=B2=A1=E6=9C= =89=E6=89=BE=E5=88=B0=E5=AF=B9=E8=B1=A1=EF=BC=8C=E5=B0=86=E8=BF=94=E5=9B=9E= ``NULL`` =E3=80=82 - - -=E7=B4=A2=E5=BC=95=E9=94=AE=E5=BD=A2=E5=BC=8F ----------- - -=E7=B4=A2=E5=BC=95=E9=94=AE=E5=8F=AF=E4=BB=A5=E6=98=AF=E4=BB=BB=E4=BD=95= =E5=BD=A2=E5=BC=8F=E7=9A=84=EF=BC=8C=E4=BD=86=E6=98=AF=E7=94=B1=E4=BA=8E=E7= =AE=97=E6=B3=95=E6=B2=A1=E6=9C=89=E8=A2=AB=E5=91=8A=E7=9F=A5=E9=94=AE=E6=9C= =89=E5=A4=9A=E9=95=BF=EF=BC=8C=E6=89=80=E4=BB=A5=E5=BC=BA=E7=83=88=E5=BB=BA= =E8=AE=AE=E5=9C=A8=E4=BB=BB=E4=BD=95=E7=94=B1=E4=BA=8E=E9=95=BF=E5=BA=A6=E8= =80=8C=E4=BA=A7=E7=94=9F=E7=9A=84=E5=8F=98=E5=8C=96 -=E5=AF=B9=E6=AF=94=E8=BE=83=E4=BA=A7=E7=94=9F=E5=BD=B1=E5=93=8D=E4=B9=8B= =E5=89=8D=EF=BC=8C=E7=B4=A2=E5=BC=95=E9=94=AE=E5=BA=94=E8=AF=A5=E5=BE=88=E6= =97=A9=E5=B0=B1=E5=8C=85=E6=8B=AC=E5=85=B6=E9=95=BF=E5=BA=A6=E3=80=82 - -=E8=BF=99=E5=B0=86=E5=AF=BC=E8=87=B4=E5=85=B7=E6=9C=89=E4=B8=8D=E5=90=8C= =E9=95=BF=E5=BA=A6=E9=94=AE=E7=9A=84=E5=8F=B6=E5=AD=90=E7=9B=B8=E4=BA=92=E5= =88=86=E6=95=A3=EF=BC=8C=E8=80=8C=E5=85=B7=E6=9C=89=E7=9B=B8=E5=90=8C=E9=95= =BF=E5=BA=A6=E9=94=AE=E7=9A=84=E5=8F=B6=E5=AD=90=E5=88=99=E8=81=9A=E9=9B=86= =E5=9C=A8=E4=B8=80=E8=B5=B7=E3=80=82 - -=E6=88=91=E4=BB=AC=E8=BF=98=E5=BB=BA=E8=AE=AE=E7=B4=A2=E5=BC=95=E9=94=AE= =E4=BB=A5=E9=94=AE=E7=9A=84=E5=85=B6=E4=BD=99=E9=83=A8=E5=88=86=E7=9A=84=E5= =93=88=E5=B8=8C=E5=80=BC=E5=BC=80=E5=A7=8B=EF=BC=8C=E4=BB=A5=E6=9C=80=E5=A4= =A7=E9=99=90=E5=BA=A6=E5=9C=B0=E6=8F=90=E9=AB=98=E6=95=B4=E4=B8=AA=E9=94=AE= =E7=A9=BA=E9=97=B4=E7=9A=84=E6=95=A3=E5=B8=83=E6=83=85=E5=86=B5=E3=80=82 - -=E5=88=86=E6=95=A3=E6=80=A7=E8=B6=8A=E5=A5=BD=EF=BC=8C=E5=86=85=E9=83=A8= =E6=A0=91=E5=B0=B1=E8=B6=8A=E5=AE=BD=EF=BC=8C=E8=B6=8A=E4=BD=8E=E3=80=82 - -=E5=88=86=E6=95=A3=E6=80=A7=E5=B7=AE=E5=B9=B6=E4=B8=8D=E6=98=AF=E4=B8=80= =E4=B8=AA=E5=A4=AA=E5=A4=A7=E7=9A=84=E9=97=AE=E9=A2=98=EF=BC=8C=E5=9B=A0=E4= =B8=BA=E6=9C=89=E5=BF=AB=E6=8D=B7=E9=94=AE=EF=BC=8C=E8=8A=82=E7=82=B9=E5=8F= =AF=E4=BB=A5=E5=8C=85=E5=90=AB=E5=8F=B6=E5=AD=90=E5=92=8C=E5=85=83=E6=95=B0= =E6=8D=AE=E6=8C=87=E9=92=88=E7=9A=84=E6=B7=B7=E5=90=88=E7=89=A9=E3=80=82 - -=E7=B4=A2=E5=BC=95=E9=94=AE=E6=98=AF=E4=BB=A5=E6=9C=BA=E5=99=A8=E5=AD=97= =E7=9A=84=E5=9D=97=E7=8A=B6=E6=9D=A5=E8=AF=BB=E5=8F=96=E7=9A=84=E3=80=82=E6= =AF=8F=E4=B8=AA=E5=9D=97=E8=A2=AB=E7=BB=86=E5=88=86=E4=B8=BA=E6=AF=8F=E5=B1= =82=E4=B8=80=E4=B8=AAnibble=EF=BC=884=E6=AF=94=E7=89=B9=EF=BC=89=EF=BC=8C= =E6=89=80=E4=BB=A5=E5=9C=A832=E4=BD=8DCPU=E4=B8=8A=E8=BF=99=E9=80=82=E5=90= =888=E5=B1=82=EF=BC=8C -=E5=9C=A864=E4=BD=8DCPU=E4=B8=8A=E9=80=82=E5=90=8816=E5=B1=82=E3=80=82=E9= =99=A4=E9=9D=9E=E6=95=A3=E5=B8=83=E6=83=85=E5=86=B5=E7=9C=9F=E7=9A=84=E5=BE= =88=E5=B7=AE=EF=BC=8C=E5=90=A6=E5=88=99=E4=B8=8D=E5=A4=AA=E5=8F=AF=E8=83=BD= =E6=9C=89=E8=B6=85=E8=BF=87=E4=B8=80=E4=B8=AA=E5=AD=97=E7=9A=84=E4=BB=BB=E4= =BD=95=E7=89=B9=E5=AE=9A=E7=B4=A2=E5=BC=95=E9=94=AE=E9=9C=80=E8=A6=81=E8=A2= =AB=E4=BD=BF=E7=94=A8=E3=80=82 - - -=E5=86=85=E9=83=A8=E5=B7=A5=E4=BD=9C=E6=9C=BA=E5=88=B6 -=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - -=E5=85=B3=E8=81=94=E6=95=B0=E7=BB=84=E6=95=B0=E6=8D=AE=E7=BB=93=E6=9E=84= =E6=9C=89=E4=B8=80=E4=B8=AA=E5=86=85=E9=83=A8=E6=A0=91=E3=80=82=E8=BF=99=E4= =B8=AA=E6=A0=91=E7=94=B1=E4=B8=A4=E7=A7=8D=E7=B1=BB=E5=9E=8B=E7=9A=84=E5=85= =83=E6=95=B0=E6=8D=AE=E5=9D=97=E6=9E=84=E6=88=90=EF=BC=9A=E8=8A=82=E7=82=B9= =E5=92=8C=E5=BF=AB=E6=8D=B7=E9=94=AE=E3=80=82 - -=E4=B8=80=E4=B8=AA=E8=8A=82=E7=82=B9=E6=98=AF=E4=B8=80=E4=B8=AA=E6=A7=BD= =E7=9A=84=E6=95=B0=E7=BB=84=E3=80=82=E6=AF=8F=E4=B8=AA=E6=A7=BD=E5=8F=AF=E4= =BB=A5=E5=8C=85=E5=90=AB=E4=BB=A5=E4=B8=8B=E5=9B=9B=E7=A7=8D=E4=B8=9C=E8=A5= =BF=E4=B9=8B=E4=B8=80: - -* =E4=B8=80=E4=B8=AANULL=E7=9A=84=E6=8C=87=E9=92=88=EF=BC=8C=E8=A1=A8=E7= =A4=BA=E6=A7=BD=E6=98=AF=E7=A9=BA=E7=9A=84=E3=80=82 -* =E4=B8=80=E4=B8=AA=E6=8C=87=E5=90=91=E5=AF=B9=E8=B1=A1=EF=BC=88=E5=8F=B6= =E5=AD=90=EF=BC=89=E7=9A=84=E6=8C=87=E9=92=88=E3=80=82 -* =E4=B8=80=E4=B8=AA=E6=8C=87=E5=90=91=E4=B8=8B=E4=B8=80=E7=BA=A7=E8=8A=82= =E7=82=B9=E7=9A=84=E6=8C=87=E9=92=88=E3=80=82 -* =E4=B8=80=E4=B8=AA=E6=8C=87=E5=90=91=E5=BF=AB=E6=8D=B7=E9=94=AE=E7=9A=84= =E6=8C=87=E9=92=88=E3=80=82 - - -=E5=9F=BA=E6=9C=AC=E7=9A=84=E5=86=85=E9=83=A8=E6=A0=91=E5=BD=A2=E5=B8=83= =E5=B1=80 ------------------- - -=E6=9A=82=E6=97=B6=E4=B8=8D=E8=80=83=E8=99=91=E5=BF=AB=E6=8D=B7=E9=94=AE= =EF=BC=8C=E8=8A=82=E7=82=B9=E5=BD=A2=E6=88=90=E4=B8=80=E4=B8=AA=E5=A4=9A=E7= =BA=A7=E6=A0=91=E3=80=82=E7=B4=A2=E5=BC=95=E9=94=AE=E7=A9=BA=E9=97=B4=E8=A2= =AB=E6=A0=91=E4=B8=8A=E7=9A=84=E8=8A=82=E7=82=B9=E4=B8=A5=E6=A0=BC=E7=BB=86= =E5=88=86=EF=BC=8C=E8=8A=82=E7=82=B9=E5=87=BA=E7=8E=B0=E5=9C=A8=E5=9B=BA=E5= =AE=9A=E7=9A=84=E5=B1=82=E6=AC=A1=E4=B8=8A=E3=80=82=E4=BE=8B=E5=A6=82:: - - Level: 0 1 2 3 - =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D = =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - 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 | - +---+ - -=E5=9C=A8=E4=B8=8A=E8=BF=B0=E4=BE=8B=E5=AD=90=E4=B8=AD=EF=BC=8C=E6=9C=897= =E4=B8=AA=E8=8A=82=E7=82=B9=EF=BC=88A-G=EF=BC=89=EF=BC=8C=E6=AF=8F=E4=B8=AA= =E8=8A=82=E7=82=B9=E6=9C=8916=E4=B8=AA=E6=A7=BD=EF=BC=880-f=EF=BC=89=E3=80= =82=E5=81=87=E8=AE=BE=E6=A0=91=E4=B8=8A=E6=B2=A1=E6=9C=89=E5=85=B6=E4=BB=96= =E5=85=83=E6=95=B0=E6=8D=AE=E8=8A=82=E7=82=B9=EF=BC=8C=E9=82=A3=E4=B9=88=E5= =AF=86=E9=92=A5=E7=A9=BA=E9=97=B4 -=E6=98=AF=E8=BF=99=E6=A0=B7=E5=88=92=E5=88=86=E7=9A=84:: - - KEY PREFIX NODE - =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D - 137* D - 138* E - 13[0-69-f]* C - 1[0-24-f]* B - e6* G - e[0-57-f]* F - [02-df]* A - -=E5=9B=A0=E6=AD=A4=EF=BC=8C=E4=BE=8B=E5=A6=82=EF=BC=8C=E5=85=B7=E6=9C=89= =E4=BB=A5=E4=B8=8B=E7=A4=BA=E4=BE=8B=E7=B4=A2=E5=BC=95=E9=94=AE=E7=9A=84=E9= =94=AE=E5=B0=86=E5=9C=A8=E9=80=82=E5=BD=93=E7=9A=84=E8=8A=82=E7=82=B9=E4=B8= =AD=E8=A2=AB=E6=89=BE=E5=88=B0:: - - INDEX KEY PREFIX NODE - =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D = =3D=3D=3D=3D - 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 - -=E4=B8=BA=E4=BA=86=E8=8A=82=E7=9C=81=E5=86=85=E5=AD=98=EF=BC=8C=E5=A6=82= =E6=9E=9C=E4=B8=80=E4=B8=AA=E8=8A=82=E7=82=B9=E5=8F=AF=E4=BB=A5=E5=AE=B9=E7= =BA=B3=E5=AE=83=E7=9A=84=E9=82=A3=E9=83=A8=E5=88=86=E9=94=AE=E7=A9=BA=E9=97= =B4=E4=B8=AD=E7=9A=84=E6=89=80=E6=9C=89=E5=8F=B6=E5=AD=90=EF=BC=8C=E9=82=A3= =E4=B9=88=E8=BF=99=E4=B8=AA=E8=8A=82=E7=82=B9=E5=B0=86=E6=9C=89=E6=89=80=E6= =9C=89=E8=BF=99=E4=BA=9B=E5=8F=B6=E5=AD=90=EF=BC=8C=E8=80=8C=E4=B8=8D -=E4=BC=9A=E6=9C=89=E4=BB=BB=E4=BD=95=E5=85=83=E6=95=B0=E6=8D=AE=E6=8C=87= =E9=92=88=E2=80=94=E2=80=94=E5=8D=B3=E4=BD=BF=E5=85=B6=E4=B8=AD=E4=B8=80=E4= =BA=9B=E5=8F=B6=E5=AD=90=E6=83=B3=E5=9C=A8=E5=90=8C=E4=B8=80=E4=B8=AA=E6=A7= =BD=E4=B8=AD=E3=80=82 - -=E4=B8=80=E4=B8=AA=E8=8A=82=E7=82=B9=E5=8F=AF=E4=BB=A5=E5=8C=85=E5=90=AB= =E5=8F=B6=E5=AD=90=E5=92=8C=E5=85=83=E6=95=B0=E6=8D=AE=E6=8C=87=E9=92=88=E7= =9A=84=E5=BC=82=E8=B4=A8=E6=80=A7=E6=B7=B7=E5=90=88=E3=80=82=E5=85=83=E6=95= =B0=E6=8D=AE=E6=8C=87=E9=92=88=E5=BF=85=E9=A1=BB=E5=9C=A8=E4=B8=8E=E5=AE=83= =E4=BB=AC=E7=9A=84=E5=85=B3=E9=94=AE=E7=A9=BA=E9=97=B4=E7=9A=84=E7=BB=86=E5= =88=86=E7=9B=B8=E5=8C=B9=E9=85=8D=E7=9A=84=E6=A7=BD=E4=B8=AD=E3=80=82 -=E5=8F=B6=E5=AD=90=E5=8F=AF=E4=BB=A5=E5=9C=A8=E4=BB=BB=E4=BD=95=E6=B2=A1= =E6=9C=89=E8=A2=AB=E5=85=83=E6=95=B0=E6=8D=AE=E6=8C=87=E9=92=88=E5=8D=A0=E6= =8D=AE=E7=9A=84=E6=A7=BD=E4=B8=AD=E3=80=82=E4=BF=9D=E8=AF=81=E4=B8=80=E4=B8= =AA=E8=8A=82=E7=82=B9=E4=B8=AD=E6=B2=A1=E6=9C=89=E4=B8=80=E4=B8=AA=E5=8F=B6= =E5=AD=90=E4=BC=9A=E4=B8=8E=E5=85=83=E6=95=B0=E6=8D=AE=E6=8C=87=E9=92=88=E5= =8D=A0=E6=8D=AE=E7=9A=84=E6=A7=BD=E7=9B=B8=E5=8C=B9=E9=85=8D=E3=80=82 -=E5=A6=82=E6=9E=9C=E5=85=83=E6=95=B0=E6=8D=AE=E6=8C=87=E9=92=88=E5=9C=A8= =E9=82=A3=E9=87=8C=EF=BC=8C=E4=BB=BB=E4=BD=95=E9=94=AE=E4=B8=8E=E5=85=83=E6= =95=B0=E6=8D=AE=E9=94=AE=E5=89=8D=E7=BC=80=E7=9B=B8=E5=8C=B9=E9=85=8D=E7=9A= =84=E5=8F=B6=E5=BF=85=E9=A1=BB=E5=9C=A8=E5=85=83=E6=95=B0=E6=8D=AE=E6=8C=87= =E9=92=88=E6=8C=87=E5=90=91=E7=9A=84=E5=AD=90=E6=A0=91=E4=B8=AD=E3=80=82 - -=E5=9C=A8=E4=B8=8A=E9=9D=A2=E7=9A=84=E7=B4=A2=E5=BC=95=E9=94=AE=E7=9A=84= =E4=BE=8B=E5=AD=90=E5=88=97=E8=A1=A8=E4=B8=AD=EF=BC=8C=E8=8A=82=E7=82=B9A= =E5=B0=86=E5=8C=85=E5=90=AB:: - - SLOT CONTENT INDEX KEY (PREFIX) - =3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D - 1 PTR TO NODE B 1* - any LEAF 9431809de993ba - any LEAF b4542910809cd - e PTR TO NODE F e* - any LEAF f3842239082 - -=E5=92=8C=E8=8A=82=E7=82=B9B:: - - 3 PTR TO NODE C 13* - any LEAF 1458952489 - - -=E5=BF=AB=E6=8D=B7=E9=94=AE ---------- - -=E5=BF=AB=E6=8D=B7=E9=94=AE=E6=98=AF=E8=B7=B3=E8=BF=87=E4=B8=80=E5=9D=97= =E9=94=AE=E7=A9=BA=E9=97=B4=E7=9A=84=E5=85=83=E6=95=B0=E6=8D=AE=E8=AE=B0=E5= =BD=95=E3=80=82=E5=BF=AB=E6=8D=B7=E9=94=AE=E6=98=AF=E4=B8=80=E7=B3=BB=E5=88= =97=E9=80=9A=E8=BF=87=E5=B1=82=E6=AC=A1=E4=B8=8A=E5=8D=87=E7=9A=84=E5=8D=95= =E5=8D=A0=E8=8A=82=E7=82=B9=E7=9A=84=E6=9B=BF=E4=BB=A3=E7=89=A9=E3=80=82=E5= =BF=AB=E6=8D=B7=E9=94=AE=E7=9A=84=E5=AD=98=E5=9C=A8=E6=98=AF -=E4=B8=BA=E4=BA=86=E8=8A=82=E7=9C=81=E5=86=85=E5=AD=98=E5=92=8C=E5=8A=A0= =E5=BF=AB=E9=81=8D=E5=8E=86=E9=80=9F=E5=BA=A6=E3=80=82 - -=E6=A0=91=E7=9A=84=E6=A0=B9=E9=83=A8=E6=9C=89=E5=8F=AF=E8=83=BD=E6=98=AF= =E4=B8=80=E4=B8=AA=E5=BF=AB=E6=8D=B7=E9=94=AE=E2=80=94=E2=80=94=E6=AF=94=E5= =A6=82=E8=AF=B4=EF=BC=8C=E6=A0=91=E8=87=B3=E5=B0=91=E5=8C=85=E5=90=AB17=E4= =B8=AA=E8=8A=82=E7=82=B9=EF=BC=8C=E9=83=BD=E6=9C=89=E9=94=AE=E5=89=8D=E7=BC= =80 ``1111`` =E3=80=82=E6=8F=92=E5=85=A5=E7=AE=97=E6=B3=95=E5=B0=86=E6=8F= =92=E5=85=A5=E4=B8=80=E4=B8=AA=E5=BF=AB=E6=8D=B7=E9=94=AE=EF=BC=8C -=E4=BB=A5=E5=8D=95=E6=AC=A1=E8=B7=B3=E8=BF=87 ``1111`` =E7=9A=84=E9=94=AE= =E4=BD=8D=EF=BC=8C=E5=B9=B6=E5=88=B0=E8=BE=BE=E7=AC=AC=E5=9B=9B=E5=B1=82=EF= =BC=8C=E5=9C=A8=E8=BF=99=E9=87=8C=EF=BC=8C=E8=BF=99=E4=BA=9B=E9=94=AE=E4=BD= =8D=E5=AE=9E=E9=99=85=E4=B8=8A=E5=8F=98=E5=BE=97=E4=B8=8D=E5=90=8C=E3=80=82 - - -=E6=8B=86=E5=88=86=E5=92=8C=E5=90=88=E5=B9=B6=E8=8A=82=E7=82=B9 ------------------------------- - -=E6=AF=8F=E4=B8=AA=E8=8A=82=E7=82=B9=E7=9A=84=E6=9C=80=E5=A4=A7=E5=AE=B9= =E9=87=8F=E4=B8=BA16=E4=B8=AA=E5=8F=B6=E5=AD=90=E5=92=8C=E5=85=83=E6=95=B0= =E6=8D=AE=E6=8C=87=E9=92=88=E3=80=82=E5=A6=82=E6=9E=9C=E6=8F=92=E5=85=A5=E7= =AE=97=E6=B3=95=E5=8F=91=E7=8E=B0=E5=AE=83=E6=AD=A3=E8=AF=95=E5=9B=BE=E5=B0= =86=E4=B8=80=E4=B8=AA=E7=AC=AC17=E4=B8=AA=E5=AF=B9=E8=B1=A1=E6=8F=92=E5=85= =A5=E5=88=B0=E4=B8=80=E4=B8=AA=E8=8A=82=E7=82=B9=E4=B8=AD=EF=BC=8C -=E8=AF=A5=E8=8A=82=E7=82=B9=E5=B0=86=E8=A2=AB=E6=8B=86=E5=88=86=EF=BC=8C= =E4=BD=BF=E5=BE=97=E8=87=B3=E5=B0=91=E4=B8=A4=E4=B8=AA=E5=9C=A8=E8=AF=A5=E5= =B1=82=E6=9C=89=E4=B8=80=E4=B8=AA=E5=85=B1=E5=90=8C=E7=9A=84=E5=85=B3=E9=94= =AE=E6=AE=B5=E7=9A=84=E5=8F=B6=E5=AD=90=E6=9C=80=E7=BB=88=E5=9C=A8=E4=B8=80= =E4=B8=AA=E5=8D=95=E7=8B=AC=E7=9A=84=E8=8A=82=E7=82=B9=E4=B8=AD=EF=BC=8C=E8= =AF=A5=E5=85=B1=E5=90=8C=E7=9A=84=E5=85=B3=E9=94=AE=E6=AE=B5=E7=9A=84=E6=A0= =B9 -=E5=9C=A8=E8=AF=A5=E6=A7=BD=E4=B8=8A=E3=80=82 - -=E5=A6=82=E6=9E=9C=E4=B8=80=E4=B8=AA=E5=AE=8C=E6=95=B4=E7=9A=84=E8=8A=82= =E7=82=B9=E4=B8=AD=E7=9A=84=E5=8F=B6=E5=AD=90=E5=92=8C=E8=A2=AB=E6=8F=92=E5= =85=A5=E7=9A=84=E5=8F=B6=E5=AD=90=E8=B6=B3=E5=A4=9F=E7=9B=B8=E4=BC=BC=EF=BC= =8C=E9=82=A3=E4=B9=88=E5=B0=B1=E4=BC=9A=E5=9C=A8=E6=A0=91=E4=B8=AD=E6=8F=92= =E5=85=A5=E4=B8=80=E4=B8=AA=E5=BF=AB=E6=8D=B7=E9=94=AE=E3=80=82 - -=E5=BD=93=E6=A0=B9=E6=A4=8D=E4=BA=8E=E6=9F=90=E4=B8=AA=E8=8A=82=E7=82=B9= =E7=9A=84=E5=AD=90=E6=A0=91=E4=B8=AD=E7=9A=84=E5=AF=B9=E8=B1=A1=E6=95=B0=E9= =87=8F=E4=B8=8B=E9=99=8D=E5=88=B016=E4=B8=AA=E6=88=96=E6=9B=B4=E5=B0=91=E6= =97=B6=EF=BC=8C=E9=82=A3=E4=B9=88=E8=AF=A5=E5=AD=90=E6=A0=91=E5=B0=86=E8=A2= =AB=E5=90=88=E5=B9=B6=E6=88=90=E4=B8=80=E4=B8=AA=E5=8D=95=E7=8B=AC=E7=9A=84= =E8=8A=82=E7=82=B9=E2=80=94=E2=80=94=E5=A6=82=E6=9E=9C=E5=8F=AF=E8=83=BD=E7= =9A=84 -=E8=AF=9D=EF=BC=8C=E8=BF=99=E5=B0=86=E5=90=91=E6=A0=B9=E9=83=A8=E6=89=A9= =E6=95=A3=E3=80=82 - - -=E9=9D=9E=E9=80=92=E5=BD=92=E5=BC=8F=E8=BF=AD=E4=BB=A3 ------------- - -=E6=AF=8F=E4=B8=AA=E8=8A=82=E7=82=B9=E5=92=8C=E5=BF=AB=E6=8D=B7=E9=94=AE= =E9=83=BD=E5=8C=85=E5=90=AB=E4=B8=80=E4=B8=AA=E6=8C=87=E5=90=91=E5=85=B6=E7= =88=B6=E8=8A=82=E7=82=B9=E7=9A=84=E5=90=8E=E7=BD=AE=E6=8C=87=E9=92=88=EF=BC= =8C=E4=BB=A5=E5=8F=8A=E8=AF=A5=E7=88=B6=E8=8A=82=E7=82=B9=E4=B8=AD=E6=8C=87= =E5=90=91=E5=AE=83=E7=9A=84=E6=A7=BD=E6=95=B0=E3=80=82=E9=9D=9E=E9=80=92=E5= =BD=92=E8=BF=AD=E4=BB=A3=E4=BD=BF=E7=94=A8=E8=BF=99=E4=BA=9B=E6=9D=A5 -=E9=80=9A=E8=BF=87=E6=A0=91=E7=9A=84=E6=A0=B9=E9=83=A8=E8=BF=9B=E8=A1=8C= =EF=BC=8C=E5=89=8D=E5=BE=80=E7=88=B6=E8=8A=82=E7=82=B9=EF=BC=8C=E6=A7=BDN+1= =EF=BC=8C=E4=BB=A5=E7=A1=AE=E4=BF=9D=E5=9C=A8=E6=B2=A1=E6=9C=89=E5=A0=86=E6= =A0=88=E7=9A=84=E6=83=85=E5=86=B5=E4=B8=8B=E5=8F=96=E5=BE=97=E8=BF=9B=E5=B1= =95=E3=80=82 - -=E7=84=B6=E8=80=8C=EF=BC=8C=E5=8F=8D=E5=90=91=E6=8C=87=E9=92=88=E4=BD=BF= =E5=BE=97=E5=90=8C=E6=97=B6=E6=94=B9=E5=8F=98=E5=92=8C=E8=BF=AD=E4=BB=A3=E5= =8F=98=E5=BE=97=E5=BE=88=E6=A3=98=E6=89=8B=E3=80=82 - - -=E5=90=8C=E6=97=B6=E6=94=B9=E5=8F=98=E5=92=8C=E8=BF=AD=E4=BB=A3 --------------- - -=E6=9C=89=E4=B8=80=E4=BA=9B=E6=83=85=E5=86=B5=E9=9C=80=E8=A6=81=E8=80=83= =E8=99=91: - -1. =E7=AE=80=E5=8D=95=E7=9A=84=E6=8F=92=E5=85=A5/=E6=9B=BF=E6=8D=A2=E3=80= =82=E8=BF=99=E6=B6=89=E5=8F=8A=E5=88=B0=E7=AE=80=E5=8D=95=E5=9C=B0=E5=B0=86= =E4=B8=80=E4=B8=AANULL=E6=88=96=E6=97=A7=E7=9A=84=E5=8C=B9=E9=85=8D=E5=8F= =B6=E5=AD=90=E7=9A=84=E6=8C=87=E9=92=88=E6=9B=BF=E6=8D=A2=E4=B8=BA=E5=B1=8F= =E9=9A=9C=E5=90=8E=E7=9A=84=E6=96=B0=E5=8F=B6=E5=AD=90=E7=9A=84=E6=8C=87=E9= =92=88=E3=80=82=E5=90=A6=E5=88=99=E5=85=83=E6=95=B0 - =E6=8D=AE=E5=9D=97=E4=B8=8D=E4=BC=9A=E6=94=B9=E5=8F=98=E3=80=82=E4=B8= =80=E4=B8=AA=E6=97=A7=E7=9A=84=E5=8F=B6=E5=AD=90=E7=9B=B4=E5=88=B0RCU=E5=AE= =BD=E9=99=90=E6=9C=9F=E8=BF=87=E5=90=8E=E6=89=8D=E4=BC=9A=E8=A2=AB=E9=87=8A= =E6=94=BE=E3=80=82 - -2. =E7=AE=80=E5=8D=95=E5=88=A0=E9=99=A4=E3=80=82=E8=BF=99=E5=8F=AA=E6=98= =AF=E6=B6=89=E5=8F=8A=E5=88=B0=E6=B8=85=E9=99=A4=E4=B8=80=E4=B8=AA=E6=97=A7= =E7=9A=84=E5=8C=B9=E9=85=8D=E5=8F=B6=E5=AD=90=E3=80=82=E5=85=83=E6=95=B0=E6= =8D=AE=E5=9D=97=E4=B8=8D=E4=BC=9A=E6=9C=89=E5=85=B6=E4=BB=96=E5=8F=98=E5=8C= =96=E3=80=82=E6=97=A7=E7=9A=84=E5=8F=B6=E5=AD=90=E7=9B=B4=E5=88=B0RCU=E5=AE= =BD=E9=99=90=E6=9C=9F=E4=B9=8B=E5=90=8E=E6=89=8D=E4=BC=9A - =E8=A2=AB=E9=87=8A=E6=94=BE=E3=80=82 - -3. =E6=8F=92=E5=85=A5=EF=BC=8C=E6=9B=BF=E6=8D=A2=E6=88=91=E4=BB=AC=E8=BF= =98=E6=B2=A1=E6=9C=89=E8=BF=9B=E5=85=A5=E7=9A=84=E5=AD=90=E6=A0=91=E7=9A=84= =E4=B8=80=E9=83=A8=E5=88=86=E3=80=82=E8=BF=99=E5=8F=AF=E8=83=BD=E6=B6=89=E5= =8F=8A=E5=88=B0=E6=9B=BF=E6=8D=A2=E8=AF=A5=E5=AD=90=E6=A0=91=E7=9A=84=E4=B8= =80=E9=83=A8=E5=88=86=E2=80=94=E2=80=94=E4=BD=86=E8=BF=99=E4=B8=8D=E4=BC=9A= =E5=BD=B1=E5=93=8D=E8=BF=AD=E4=BB=A3=EF=BC=8C=E5=9B=A0=E4=B8=BA=E6=88=91=E4= =BB=AC - =E8=BF=98=E6=B2=A1=E6=9C=89=E5=88=B0=E8=BE=BE=E5=AE=83=E7=9A=84=E6=8C= =87=E9=92=88=EF=BC=8C=E8=80=8C=E4=B8=94=E7=A5=96=E5=85=88=E5=9D=97=E4=B9=9F= =E4=B8=8D=E4=BC=9A=E8=A2=AB=E6=9B=BF=E6=8D=A2=EF=BC=88=E8=BF=99=E4=BA=9B=E5= =9D=97=E7=9A=84=E5=B8=83=E5=B1=80=E4=B8=8D=E4=BC=9A=E6=94=B9=E5=8F=98=EF=BC= =89=E3=80=82 - -4. =E6=8F=92=E5=85=A5=E6=9B=BF=E6=8D=A2=E4=BA=86=E6=88=91=E4=BB=AC=E6=AD= =A3=E5=9C=A8=E5=A4=84=E7=90=86=E7=9A=84=E8=8A=82=E7=82=B9=E3=80=82=E8=BF=99= =E4=B8=8D=E6=98=AF=E4=B8=80=E4=B8=AA=E9=97=AE=E9=A2=98=EF=BC=8C=E5=9B=A0=E4= =B8=BA=E6=88=91=E4=BB=AC=E5=B7=B2=E7=BB=8F=E9=80=9A=E8=BF=87=E4=BA=86=E9=94= =9A=E5=AE=9A=E6=8C=87=E9=92=88=EF=BC=8C=E7=9B=B4=E5=88=B0=E6=88=91=E4=BB=AC= =E8=B7=9F=E9=9A=8F=E5=90=8E=E9=9D=A2=E7=9A=84=E6=8C=87=E9=92=88=E6=89=8D - =E4=BC=9A=E5=88=87=E6=8D=A2=E5=88=B0=E6=96=B0=E7=9A=84=E5=B8=83=E5=B1= =80=E4=B8=8A=E2=80=94=E2=80=94=E8=BF=99=E6=97=B6=E6=88=91=E4=BB=AC=E5=B7=B2= =E7=BB=8F=E6=A3=80=E6=9F=A5=E4=BA=86=E8=A2=AB=E6=9B=BF=E6=8D=A2=E8=8A=82=E7= =82=B9=E7=9A=84=E5=8F=B6=E5=AD=90=EF=BC=88=E5=9C=A8=E8=B7=9F=E9=9A=8F=E4=BB= =BB=E4=BD=95=E5=85=83=E6=95=B0=E6=8D=AE=E6=8C=87=E9=92=88=E4=B9=8B=E5=89=8D= =EF=BC=8C=E6=88=91=E4=BB=AC=E4=BC=9A=E8=BF=AD=E4=BB=A3=E4=B8=80=E4=B8=AA=E8= =8A=82 - =E7=82=B9=E7=9A=84=E6=89=80=E6=9C=89=E5=8F=B6=E5=AD=90=EF=BC=89=E3=80= =82 - - =E7=84=B6=E8=80=8C=EF=BC=8C=E6=88=91=E4=BB=AC=E5=8F=AF=E8=83=BD=E4=BC= =9A=E9=87=8D=E6=96=B0=E7=9C=8B=E5=88=B0=E4=B8=80=E4=BA=9B=E5=8F=B6=E5=AD=90= =EF=BC=8C=E8=BF=99=E4=BA=9B=E5=8F=B6=E5=AD=90=E5=B7=B2=E7=BB=8F=E8=A2=AB=E5= =88=86=E5=89=B2=E6=88=90=E4=B8=80=E4=B8=AA=E6=96=B0=E7=9A=84=E5=88=86=E6=94= =AF=EF=BC=8C=E8=80=8C=E8=BF=99=E4=B8=AA=E5=88=86=E6=94=AF=E7=9A=84=E4=BD=8D= =E7=BD=AE=E6=AF=94=E6=88=91=E4=BB=AC=E4=B9=8B=E5=89=8D=E7=9A=84=E4=BD=8D - =E7=BD=AE=E6=9B=B4=E8=BF=9C=E3=80=82 - -5. =E6=8F=92=E5=85=A5=E6=9B=BF=E6=8D=A2=E4=BA=86=E6=88=91=E4=BB=AC=E6=AD= =A3=E5=9C=A8=E5=A4=84=E7=90=86=E7=9A=84=E4=BE=9D=E8=B5=96=E5=88=86=E6=94=AF= =E7=9A=84=E8=8A=82=E7=82=B9=E3=80=82=E8=BF=99=E4=B8=8D=E4=BC=9A=E5=BD=B1=E5= =93=8D=E5=88=B0=E6=88=91=E4=BB=AC=EF=BC=8C=E7=9B=B4=E5=88=B0=E6=88=91=E4=BB= =AC=E8=B7=9F=E9=9A=8F=E5=90=8E=E9=9D=A2=E7=9A=84=E6=8C=87=E9=92=88=E3=80=82= =E4=B8=8E=EF=BC=884=EF=BC=89=E7=B1=BB=E4=BC=BC=E3=80=82 - -6. =E5=88=A0=E6=8E=89=E6=88=91=E4=BB=AC=E4=B8=8B=E9=9D=A2=E7=9A=84=E4=B8= =80=E4=B8=AA=E5=88=86=E6=94=AF=E3=80=82=E8=BF=99=E4=B8=8D=E4=BC=9A=E5=BD=B1= =E5=93=8D=E6=88=91=E4=BB=AC=EF=BC=8C=E5=9B=A0=E4=B8=BA=E5=9C=A8=E6=88=91=E4= =BB=AC=E7=9C=8B=E5=88=B0=E6=96=B0=E8=8A=82=E7=82=B9=E4=B9=8B=E5=89=8D=EF=BC= =8C=E5=9B=9E=E6=BA=AF=E6=8C=87=E9=92=88=E4=BC=9A=E8=AE=A9=E6=88=91=E4=BB=AC= =E5=9B=9E=E5=88=B0=E6=96=B0=E8=8A=82=E7=82=B9=E7=9A=84=E7=88=B6=E8=8A=82 - =E7=82=B9=E3=80=82=E6=95=B4=E4=B8=AA=E5=B4=A9=E6=BA=83=E7=9A=84=E5=AD= =90=E6=A0=91=E8=A2=AB=E6=89=94=E6=8E=89=E4=BA=86=EF=BC=8C=E6=B2=A1=E6=9C=89= =E4=BB=BB=E4=BD=95=E5=8F=98=E5=8C=96=E2=80=94=E2=80=94=E8=80=8C=E4=B8=94=E4= =BB=8D=E7=84=B6=E4=BC=9A=E5=9C=A8=E5=90=8C=E4=B8=80=E4=B8=AA=E6=A7=BD=E4=B8= =8A=E7=94=9F=E6=A0=B9=EF=BC=8C=E6=89=80=E4=BB=A5=E6=88=91=E4=BB=AC=E4=B8=8D= =E5=BA=94=E8=AF=A5=E7=AC=AC=E4=BA=8C=E6=AC=A1=E5=A4=84=E7=90=86=E5=AE=83=EF= =BC=8C - =E5=9B=A0=E4=B8=BA=E6=88=91=E4=BB=AC=E4=BC=9A=E5=9B=9E=E5=88=B0=E6=A7= =BD+1=E3=80=82 - -.. note:: - - =E5=9C=A8=E6=9F=90=E4=BA=9B=E6=83=85=E5=86=B5=E4=B8=8B=EF=BC=8C=E6=88= =91=E4=BB=AC=E9=9C=80=E8=A6=81=E5=90=8C=E6=97=B6=E6=94=B9=E5=8F=98=E4=B8=80= =E4=B8=AA=E8=8A=82=E7=82=B9=E7=9A=84=E7=88=B6=E6=8C=87=E9=92=88=E5=92=8C=E7= =88=B6=E6=A7=BD=E6=8C=87=E9=92=88=EF=BC=88=E6=AF=94=E5=A6=82=E8=AF=B4=EF=BC= =8C=E6=88=91=E4=BB=AC=E5=9C=A8=E5=AE=83=E4=B9=8B=E5=89=8D=E6=8F=92=E5=85=A5= =E4=BA=86=E5=8F=A6=E4=B8=80=E4=B8=AA=E8=8A=82=E7=82=B9=EF=BC=8C - =E5=B9=B6=E6=8A=8A=E5=AE=83=E5=BE=80=E4=B8=8A=E7=A7=BB=E4=BA=86=E4=B8= =80=E5=B1=82=EF=BC=89=E3=80=82=E6=88=91=E4=BB=AC=E4=B8=8D=E8=83=BD=E5=9C=A8= =E4=B8=8D=E9=94=81=E5=AE=9A=E8=AF=BB=E5=8F=96=E7=9A=84=E6=83=85=E5=86=B5=E4= =B8=8B=E8=BF=99=E6=A0=B7=E5=81=9A=E2=80=94=E2=80=94=E6=89=80=E4=BB=A5=E6=88= =91=E4=BB=AC=E5=BF=85=E9=A1=BB=E5=90=8C=E6=97=B6=E6=9B=BF=E6=8D=A2=E8=AF=A5= =E8=8A=82=E7=82=B9=E3=80=82 - - =E7=84=B6=E8=80=8C=EF=BC=8C=E5=BD=93=E6=88=91=E4=BB=AC=E6=8A=8A=E4=B8= =80=E4=B8=AA=E5=BF=AB=E6=8D=B7=E9=94=AE=E6=94=B9=E6=88=90=E4=B8=80=E4=B8=AA= =E8=8A=82=E7=82=B9=E6=97=B6=EF=BC=8C=E8=BF=99=E4=B8=8D=E6=98=AF=E4=B8=80=E4= =B8=AA=E9=97=AE=E9=A2=98=EF=BC=8C=E5=9B=A0=E4=B8=BA=E5=BF=AB=E6=8D=B7=E9=94= =AE=E5=8F=AA=E6=9C=89=E4=B8=80=E4=B8=AA=E6=A7=BD=EF=BC=8C=E6=89=80=E4=BB=A5= =E5=BD=93=E5=90=91=E5=90=8E=E9=81=8D - =E5=8E=86=E4=B8=80=E4=B8=AA=E6=A7=BD=E6=97=B6=EF=BC=8C=E4=B8=8D=E4=BC= =9A=E4=BD=BF=E7=94=A8=E7=88=B6=E6=A7=BD=E5=8F=B7=E3=80=82=E8=BF=99=E6=84=8F= =E5=91=B3=E7=9D=80=E5=85=88=E6=94=B9=E5=8F=98=E6=A7=BD=E4=BD=8D=E5=8F=B7=E6= =98=AF=E5=8F=AF=E4=BB=A5=E7=9A=84=E2=80=94=E2=80=94=E5=8F=AA=E8=A6=81=E4=BD= =BF=E7=94=A8=E9=80=82=E5=BD=93=E7=9A=84=E5=B1=8F=E9=9A=9C=E6=9D=A5=E7=A1=AE= =E4=BF=9D=E7=88=B6=E6=A7=BD=E4=BD=8D=E5=8F=B7=E5=9C=A8=E5=90=8E - =E9=80=80=E6=8C=87=E9=92=88=E4=B9=8B=E5=90=8E=E8=A2=AB=E8=AF=BB=E5=8F= =96=E3=80=82 - -=E8=BF=87=E6=97=B6=E7=9A=84=E5=9D=97=E5=92=8C=E5=8F=B6=E5=AD=90=E5=9C=A8RC= U=E5=AE=BD=E9=99=90=E6=9C=9F=E8=BF=87=E5=90=8E=E4=BC=9A=E8=A2=AB=E9=87=8A= =E6=94=BE=EF=BC=8C=E6=89=80=E4=BB=A5=E5=8F=AA=E8=A6=81=E4=BB=BB=E4=BD=95=E8= =BF=9B=E8=A1=8C=E9=81=8D=E5=8E=86=E6=88=96=E8=BF=AD=E4=BB=A3=E7=9A=84=E4=BA= =BA=E6=8C=81=E6=9C=89RCU=E8=AF=BB=E9=94=81=EF=BC=8C=E6=97=A7=E7=9A=84=E4=B8= =8A=E5=B1=82=E5=BB=BA=E7=AD=91=E5=B0=B1=E4=B8=8D -=E5=BA=94=E8=AF=A5=E5=9C=A8=E4=BB=96=E4=BB=AC=E8=BA=AB=E4=B8=8A=E6=B6=88= =E5=A4=B1=E3=80=82 diff --git a/Documentation/translations/zh_CN/core-api/index.rst b/Document= ation/translations/zh_CN/core-api/index.rst index 453a02cd1f44..ec4b03b2a0a6 100644 --- a/Documentation/translations/zh_CN/core-api/index.rst +++ b/Documentation/translations/zh_CN/core-api/index.rst @@ -41,7 +41,6 @@ =20 kobject kref - assoc_array xarray rbtree idr diff --git a/include/linux/assoc_array.h b/include/linux/assoc_array.h deleted file mode 100644 index 8b3f230ce894..000000000000 --- a/include/linux/assoc_array.h +++ /dev/null @@ -1,88 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0-or-later */ -/* Generic associative array implementation. - * - * See Documentation/core-api/assoc_array.rst for information. - * - * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved. - * Written by David Howells (dhowells@redhat.com) - */ - -#ifndef _LINUX_ASSOC_ARRAY_H -#define _LINUX_ASSOC_ARRAY_H - -#ifdef CONFIG_ASSOCIATIVE_ARRAY - -#include - -#define ASSOC_ARRAY_KEY_CHUNK_SIZE BITS_PER_LONG /* Key data retrieved in = chunks of this size */ - -/* - * Generic associative array. - */ -struct assoc_array { - struct assoc_array_ptr *root; /* The node at the root of the tree */ - unsigned long nr_leaves_on_tree; -}; - -/* - * Operations on objects and index keys for use by array manipulation rout= ines. - */ -struct assoc_array_ops { - /* Method to get a chunk of an index key from caller-supplied data */ - unsigned long (*get_key_chunk)(const void *index_key, int level); - - /* Method to get a piece of an object's index key */ - unsigned long (*get_object_key_chunk)(const void *object, int level); - - /* Is this the object we're looking for? */ - bool (*compare_object)(const void *object, const void *index_key); - - /* How different is an object from an index key, to a bit position in - * their keys? (or -1 if they're the same) - */ - int (*diff_objects)(const void *object, const void *index_key); - - /* Method to free an object. */ - void (*free_object)(void *object); -}; - -/* - * Access and manipulation functions. - */ -struct assoc_array_edit; - -static inline void assoc_array_init(struct assoc_array *array) -{ - array->root =3D NULL; - array->nr_leaves_on_tree =3D 0; -} - -extern int assoc_array_iterate(const struct assoc_array *array, - int (*iterator)(const void *object, - void *iterator_data), - void *iterator_data); -extern void *assoc_array_find(const struct assoc_array *array, - const struct assoc_array_ops *ops, - const void *index_key); -extern void assoc_array_destroy(struct assoc_array *array, - const struct assoc_array_ops *ops); -extern struct assoc_array_edit *assoc_array_insert(struct assoc_array *arr= ay, - const struct assoc_array_ops *ops, - const void *index_key, - void *object); -extern void assoc_array_insert_set_object(struct assoc_array_edit *edit, - void *object); -extern struct assoc_array_edit *assoc_array_delete(struct assoc_array *arr= ay, - const struct assoc_array_ops *ops, - const void *index_key); -extern struct assoc_array_edit *assoc_array_clear(struct assoc_array *arra= y, - const struct assoc_array_ops *ops); -extern void assoc_array_apply_edit(struct assoc_array_edit *edit); -extern void assoc_array_cancel_edit(struct assoc_array_edit *edit); -extern int assoc_array_gc(struct assoc_array *array, - const struct assoc_array_ops *ops, - bool (*iterator)(void *object, void *iterator_data), - void *iterator_data); - -#endif /* CONFIG_ASSOCIATIVE_ARRAY */ -#endif /* _LINUX_ASSOC_ARRAY_H */ diff --git a/include/linux/assoc_array_priv.h b/include/linux/assoc_array_p= riv.h deleted file mode 100644 index dca733ef6750..000000000000 --- a/include/linux/assoc_array_priv.h +++ /dev/null @@ -1,178 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0-or-later */ -/* Private definitions for the generic associative array implementation. - * - * See Documentation/core-api/assoc_array.rst for information. - * - * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved. - * Written by David Howells (dhowells@redhat.com) - */ - -#ifndef _LINUX_ASSOC_ARRAY_PRIV_H -#define _LINUX_ASSOC_ARRAY_PRIV_H - -#ifdef CONFIG_ASSOCIATIVE_ARRAY - -#include - -#define ASSOC_ARRAY_FAN_OUT 16 /* Number of slots per node */ -#define ASSOC_ARRAY_FAN_MASK (ASSOC_ARRAY_FAN_OUT - 1) -#define ASSOC_ARRAY_LEVEL_STEP (ilog2(ASSOC_ARRAY_FAN_OUT)) -#define ASSOC_ARRAY_LEVEL_STEP_MASK (ASSOC_ARRAY_LEVEL_STEP - 1) -#define ASSOC_ARRAY_KEY_CHUNK_MASK (ASSOC_ARRAY_KEY_CHUNK_SIZE - 1) -#define ASSOC_ARRAY_KEY_CHUNK_SHIFT (ilog2(BITS_PER_LONG)) - -/* - * Undefined type representing a pointer with type information in the bott= om - * two bits. - */ -struct assoc_array_ptr; - -/* - * An N-way node in the tree. - * - * Each slot contains one of four things: - * - * (1) Nothing (NULL). - * - * (2) A leaf object (pointer types 0). - * - * (3) A next-level node (pointer type 1, subtype 0). - * - * (4) A shortcut (pointer type 1, subtype 1). - * - * The tree is optimised for search-by-ID, but permits reasonable iteration - * also. - * - * The tree is navigated by constructing an index key consisting of an arr= ay of - * segments, where each segment is ilog2(ASSOC_ARRAY_FAN_OUT) bits in size. - * - * The segments correspond to levels of the tree (the first segment is use= d at - * level 0, the second at level 1, etc.). - */ -struct assoc_array_node { - struct assoc_array_ptr *back_pointer; - u8 parent_slot; - struct assoc_array_ptr *slots[ASSOC_ARRAY_FAN_OUT]; - unsigned long nr_leaves_on_branch; -}; - -/* - * A shortcut through the index space out to where a collection of nodes/l= eaves - * with the same IDs live. - */ -struct assoc_array_shortcut { - struct assoc_array_ptr *back_pointer; - int parent_slot; - int skip_to_level; - struct assoc_array_ptr *next_node; - unsigned long index_key[]; -}; - -/* - * Preallocation cache. - */ -struct assoc_array_edit { - struct rcu_head rcu; - struct assoc_array *array; - const struct assoc_array_ops *ops; - const struct assoc_array_ops *ops_for_excised_subtree; - struct assoc_array_ptr *leaf; - struct assoc_array_ptr **leaf_p; - struct assoc_array_ptr *dead_leaf; - struct assoc_array_ptr *new_meta[3]; - struct assoc_array_ptr *excised_meta[1]; - struct assoc_array_ptr *excised_subtree; - struct assoc_array_ptr **set_backpointers[ASSOC_ARRAY_FAN_OUT]; - struct assoc_array_ptr *set_backpointers_to; - struct assoc_array_node *adjust_count_on; - long adjust_count_by; - struct { - struct assoc_array_ptr **ptr; - struct assoc_array_ptr *to; - } set[2]; - struct { - u8 *p; - u8 to; - } set_parent_slot[1]; - u8 segment_cache[ASSOC_ARRAY_FAN_OUT + 1]; -}; - -/* - * Internal tree member pointers are marked in the bottom one or two bits = to - * indicate what type they are so that we don't have to look behind every - * pointer to see what it points to. - * - * We provide functions to test type annotations and to create and transla= te - * the annotated pointers. - */ -#define ASSOC_ARRAY_PTR_TYPE_MASK 0x1UL -#define ASSOC_ARRAY_PTR_LEAF_TYPE 0x0UL /* Points to leaf (or nowhere) */ -#define ASSOC_ARRAY_PTR_META_TYPE 0x1UL /* Points to node or shortcut */ -#define ASSOC_ARRAY_PTR_SUBTYPE_MASK 0x2UL -#define ASSOC_ARRAY_PTR_NODE_SUBTYPE 0x0UL -#define ASSOC_ARRAY_PTR_SHORTCUT_SUBTYPE 0x2UL - -static inline bool assoc_array_ptr_is_meta(const struct assoc_array_ptr *x) -{ - return (unsigned long)x & ASSOC_ARRAY_PTR_TYPE_MASK; -} -static inline bool assoc_array_ptr_is_leaf(const struct assoc_array_ptr *x) -{ - return !assoc_array_ptr_is_meta(x); -} -static inline bool assoc_array_ptr_is_shortcut(const struct assoc_array_pt= r *x) -{ - return (unsigned long)x & ASSOC_ARRAY_PTR_SUBTYPE_MASK; -} -static inline bool assoc_array_ptr_is_node(const struct assoc_array_ptr *x) -{ - return !assoc_array_ptr_is_shortcut(x); -} - -static inline void *assoc_array_ptr_to_leaf(const struct assoc_array_ptr *= x) -{ - return (void *)((unsigned long)x & ~ASSOC_ARRAY_PTR_TYPE_MASK); -} - -static inline -unsigned long __assoc_array_ptr_to_meta(const struct assoc_array_ptr *x) -{ - return (unsigned long)x & - ~(ASSOC_ARRAY_PTR_SUBTYPE_MASK | ASSOC_ARRAY_PTR_TYPE_MASK); -} -static inline -struct assoc_array_node *assoc_array_ptr_to_node(const struct assoc_array_= ptr *x) -{ - return (struct assoc_array_node *)__assoc_array_ptr_to_meta(x); -} -static inline -struct assoc_array_shortcut *assoc_array_ptr_to_shortcut(const struct asso= c_array_ptr *x) -{ - return (struct assoc_array_shortcut *)__assoc_array_ptr_to_meta(x); -} - -static inline -struct assoc_array_ptr *__assoc_array_x_to_ptr(const void *p, unsigned lon= g t) -{ - return (struct assoc_array_ptr *)((unsigned long)p | t); -} -static inline -struct assoc_array_ptr *assoc_array_leaf_to_ptr(const void *p) -{ - return __assoc_array_x_to_ptr(p, ASSOC_ARRAY_PTR_LEAF_TYPE); -} -static inline -struct assoc_array_ptr *assoc_array_node_to_ptr(const struct assoc_array_n= ode *p) -{ - return __assoc_array_x_to_ptr( - p, ASSOC_ARRAY_PTR_META_TYPE | ASSOC_ARRAY_PTR_NODE_SUBTYPE); -} -static inline -struct assoc_array_ptr *assoc_array_shortcut_to_ptr(const struct assoc_arr= ay_shortcut *p) -{ - return __assoc_array_x_to_ptr( - p, ASSOC_ARRAY_PTR_META_TYPE | ASSOC_ARRAY_PTR_SHORTCUT_SUBTYPE); -} - -#endif /* CONFIG_ASSOCIATIVE_ARRAY */ -#endif /* _LINUX_ASSOC_ARRAY_PRIV_H */ diff --git a/lib/Kconfig b/lib/Kconfig index 1e42f5167c68..f70382dbb159 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -349,20 +349,6 @@ config XARRAY_MULTI Support entries which occupy multiple consecutive indices in the XArray. =20 -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 =20 diff --git a/lib/Makefile b/lib/Makefile index a2afe954805c..4777dfcc8244 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -141,7 +141,6 @@ obj-$(CONFIG_GENERIC_HWEIGHT) +=3D hweight.o =20 obj-$(CONFIG_BTREE) +=3D btree.o obj-$(CONFIG_INTERVAL_TREE) +=3D interval_tree.o -obj-$(CONFIG_ASSOCIATIVE_ARRAY) +=3D assoc_array.o obj-$(CONFIG_DEBUG_PREEMPT) +=3D smp_processor_id.o obj-$(CONFIG_LIST_HARDENED) +=3D list_debug.o obj-$(CONFIG_DEBUG_OBJECTS) +=3D debugobjects.o diff --git a/lib/assoc_array.c b/lib/assoc_array.c deleted file mode 100644 index b6c9723e12ce..000000000000 --- a/lib/assoc_array.c +++ /dev/null @@ -1,1724 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0-or-later -/* Generic associative array implementation. - * - * See Documentation/core-api/assoc_array.rst for information. - * - * Copyright (C) 2013 Red Hat, Inc. All Rights Reserved. - * Written by David Howells (dhowells@redhat.com) - */ -//#define DEBUG -#include -#include -#include -#include - -/* - * Iterate over an associative array. The caller must hold the RCU read l= ock - * or better. - */ -static int assoc_array_subtree_iterate(const struct assoc_array_ptr *root, - const struct assoc_array_ptr *stop, - int (*iterator)(const void *leaf, - void *iterator_data), - void *iterator_data) -{ - const struct assoc_array_shortcut *shortcut; - const struct assoc_array_node *node; - const struct assoc_array_ptr *cursor, *ptr, *parent; - unsigned long has_meta; - int slot, ret; - - cursor =3D root; - -begin_node: - if (assoc_array_ptr_is_shortcut(cursor)) { - /* Descend through a shortcut */ - shortcut =3D assoc_array_ptr_to_shortcut(cursor); - cursor =3D READ_ONCE(shortcut->next_node); /* Address dependency. */ - } - - node =3D assoc_array_ptr_to_node(cursor); - slot =3D 0; - - /* We perform two passes of each node. - * - * The first pass does all the leaves in this node. This means we - * don't miss any leaves if the node is split up by insertion whilst - * we're iterating over the branches rooted here (we may, however, see - * some leaves twice). - */ - has_meta =3D 0; - for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) { - ptr =3D READ_ONCE(node->slots[slot]); /* Address dependency. */ - has_meta |=3D (unsigned long)ptr; - if (ptr && assoc_array_ptr_is_leaf(ptr)) { - /* We need a barrier between the read of the pointer, - * which is supplied by the above READ_ONCE(). - */ - /* Invoke the callback */ - ret =3D iterator(assoc_array_ptr_to_leaf(ptr), - iterator_data); - if (ret) - return ret; - } - } - - /* The second pass attends to all the metadata pointers. If we follow - * one of these we may find that we don't come back here, but rather go - * back to a replacement node with the leaves in a different layout. - * - * We are guaranteed to make progress, however, as the slot number for - * a particular portion of the key space cannot change - and we - * continue at the back pointer + 1. - */ - if (!(has_meta & ASSOC_ARRAY_PTR_META_TYPE)) - goto finished_node; - slot =3D 0; - -continue_node: - node =3D assoc_array_ptr_to_node(cursor); - for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) { - ptr =3D READ_ONCE(node->slots[slot]); /* Address dependency. */ - if (assoc_array_ptr_is_meta(ptr)) { - cursor =3D ptr; - goto begin_node; - } - } - -finished_node: - /* Move up to the parent (may need to skip back over a shortcut) */ - parent =3D READ_ONCE(node->back_pointer); /* Address dependency. */ - slot =3D node->parent_slot; - if (parent =3D=3D stop) - return 0; - - if (assoc_array_ptr_is_shortcut(parent)) { - shortcut =3D assoc_array_ptr_to_shortcut(parent); - cursor =3D parent; - parent =3D READ_ONCE(shortcut->back_pointer); /* Address dependency. */ - slot =3D shortcut->parent_slot; - if (parent =3D=3D stop) - return 0; - } - - /* Ascend to next slot in parent node */ - cursor =3D parent; - slot++; - goto continue_node; -} - -/** - * assoc_array_iterate - Pass all objects in the array to a callback - * @array: The array to iterate over. - * @iterator: The callback function. - * @iterator_data: Private data for the callback function. - * - * Iterate over all the objects in an associative array. Each one will be - * presented to the iterator function. - * - * If the array is being modified concurrently with the iteration then it = is - * possible that some objects in the array will be passed to the iterator - * callback more than once - though every object should be passed at least - * once. If this is undesirable then the caller must lock against modific= ation - * for the duration of this function. - * - * The function will return 0 if no objects were in the array or else it w= ill - * 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. - * - * The caller should hold the RCU read lock or better if concurrent - * modification is possible. - */ -int assoc_array_iterate(const struct assoc_array *array, - int (*iterator)(const void *object, - void *iterator_data), - void *iterator_data) -{ - struct assoc_array_ptr *root =3D READ_ONCE(array->root); /* Address depen= dency. */ - - if (!root) - return 0; - return assoc_array_subtree_iterate(root, NULL, iterator, iterator_data); -} - -enum assoc_array_walk_status { - assoc_array_walk_tree_empty, - assoc_array_walk_found_terminal_node, - assoc_array_walk_found_wrong_shortcut, -}; - -struct assoc_array_walk_result { - struct { - struct assoc_array_node *node; /* Node in which leaf might be found */ - int level; - int slot; - } terminal_node; - struct { - struct assoc_array_shortcut *shortcut; - int level; - int sc_level; - unsigned long sc_segments; - unsigned long dissimilarity; - } wrong_shortcut; -}; - -/* - * Navigate through the internal tree looking for the closest node to the = key. - */ -static enum assoc_array_walk_status -assoc_array_walk(const struct assoc_array *array, - const struct assoc_array_ops *ops, - const void *index_key, - struct assoc_array_walk_result *result) -{ - struct assoc_array_shortcut *shortcut; - struct assoc_array_node *node; - struct assoc_array_ptr *cursor, *ptr; - unsigned long sc_segments, dissimilarity; - unsigned long segments; - int level, sc_level, next_sc_level; - int slot; - - pr_devel("-->%s()\n", __func__); - - cursor =3D READ_ONCE(array->root); /* Address dependency. */ - if (!cursor) - return assoc_array_walk_tree_empty; - - level =3D 0; - - /* Use segments from the key for the new leaf to navigate through the - * internal tree, skipping through nodes and shortcuts that are on - * route to the destination. Eventually we'll come to a slot that is - * either empty or contains a leaf at which point we've found a node in - * which the leaf we're looking for might be found or into which it - * should be inserted. - */ -jumped: - segments =3D ops->get_key_chunk(index_key, level); - pr_devel("segments[%d]: %lx\n", level, segments); - - if (assoc_array_ptr_is_shortcut(cursor)) - goto follow_shortcut; - -consider_node: - node =3D assoc_array_ptr_to_node(cursor); - slot =3D segments >> (level & ASSOC_ARRAY_KEY_CHUNK_MASK); - slot &=3D ASSOC_ARRAY_FAN_MASK; - ptr =3D READ_ONCE(node->slots[slot]); /* Address dependency. */ - - pr_devel("consider slot %x [ix=3D%d type=3D%lu]\n", - slot, level, (unsigned long)ptr & 3); - - if (!assoc_array_ptr_is_meta(ptr)) { - /* The node doesn't have a node/shortcut pointer in the slot - * corresponding to the index key that we have to follow. - */ - result->terminal_node.node =3D node; - result->terminal_node.level =3D level; - result->terminal_node.slot =3D slot; - pr_devel("<--%s() =3D terminal_node\n", __func__); - return assoc_array_walk_found_terminal_node; - } - - if (assoc_array_ptr_is_node(ptr)) { - /* There is a pointer to a node in the slot corresponding to - * this index key segment, so we need to follow it. - */ - cursor =3D ptr; - level +=3D ASSOC_ARRAY_LEVEL_STEP; - if ((level & ASSOC_ARRAY_KEY_CHUNK_MASK) !=3D 0) - goto consider_node; - goto jumped; - } - - /* There is a shortcut in the slot corresponding to the index key - * segment. We follow the shortcut if its partial index key matches - * this leaf's. Otherwise we need to split the shortcut. - */ - cursor =3D ptr; -follow_shortcut: - shortcut =3D assoc_array_ptr_to_shortcut(cursor); - pr_devel("shortcut to %d\n", shortcut->skip_to_level); - sc_level =3D level + ASSOC_ARRAY_LEVEL_STEP; - BUG_ON(sc_level > shortcut->skip_to_level); - - do { - /* Check the leaf against the shortcut's index key a word at a - * time, trimming the final word (the shortcut stores the index - * key completely from the root to the shortcut's target). - */ - if ((sc_level & ASSOC_ARRAY_KEY_CHUNK_MASK) =3D=3D 0) - segments =3D ops->get_key_chunk(index_key, sc_level); - - sc_segments =3D shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SH= IFT]; - dissimilarity =3D segments ^ sc_segments; - - if (shortcut->skip_to_level < round_down(sc_level, - ASSOC_ARRAY_KEY_CHUNK_SIZE) + ASSOC_ARRAY_KEY_CHUNK_SIZE) { - /* Trim segments that are beyond the shortcut */ - int shift =3D shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK; - dissimilarity &=3D ~(ULONG_MAX << shift); - next_sc_level =3D shortcut->skip_to_level; - } else { - next_sc_level =3D sc_level + ASSOC_ARRAY_KEY_CHUNK_SIZE; - next_sc_level =3D round_down(next_sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE); - } - - if (dissimilarity !=3D 0) { - /* This shortcut points elsewhere */ - result->wrong_shortcut.shortcut =3D shortcut; - result->wrong_shortcut.level =3D level; - result->wrong_shortcut.sc_level =3D sc_level; - result->wrong_shortcut.sc_segments =3D sc_segments; - result->wrong_shortcut.dissimilarity =3D dissimilarity; - return assoc_array_walk_found_wrong_shortcut; - } - - sc_level =3D next_sc_level; - } while (sc_level < shortcut->skip_to_level); - - /* The shortcut matches the leaf's index to this point. */ - cursor =3D READ_ONCE(shortcut->next_node); /* Address dependency. */ - if (((level ^ sc_level) & ~ASSOC_ARRAY_KEY_CHUNK_MASK) !=3D 0) { - level =3D sc_level; - goto jumped; - } else { - level =3D sc_level; - goto consider_node; - } -} - -/** - * assoc_array_find - Find an object by index key - * @array: The associative array to search. - * @ops: The operations to use. - * @index_key: The key to the object. - * - * Find an object in an associative array by walking through the internal = tree - * to the node that should contain the object and then searching the leaves - * there. NULL is returned if the requested object was not found in the a= rray. - * - * The caller must hold the RCU read lock or better. - */ -void *assoc_array_find(const struct assoc_array *array, - const struct assoc_array_ops *ops, - const void *index_key) -{ - struct assoc_array_walk_result result; - const struct assoc_array_node *node; - const struct assoc_array_ptr *ptr; - const void *leaf; - int slot; - - if (assoc_array_walk(array, ops, index_key, &result) !=3D - assoc_array_walk_found_terminal_node) - return NULL; - - node =3D result.terminal_node.node; - - /* If the target key is available to us, it's has to be pointed to by - * the terminal node. - */ - for (slot =3D 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) { - ptr =3D READ_ONCE(node->slots[slot]); /* Address dependency. */ - if (ptr && assoc_array_ptr_is_leaf(ptr)) { - /* We need a barrier between the read of the pointer - * and dereferencing the pointer - but only if we are - * actually going to dereference it. - */ - leaf =3D assoc_array_ptr_to_leaf(ptr); - if (ops->compare_object(leaf, index_key)) - return (void *)leaf; - } - } - - return NULL; -} - -/* - * Destructively iterate over an associative array. The caller must preve= nt - * other simultaneous accesses. - */ -static void assoc_array_destroy_subtree(struct assoc_array_ptr *root, - const struct assoc_array_ops *ops) -{ - struct assoc_array_shortcut *shortcut; - struct assoc_array_node *node; - struct assoc_array_ptr *cursor, *parent =3D NULL; - int slot =3D -1; - - pr_devel("-->%s()\n", __func__); - - cursor =3D root; - if (!cursor) { - pr_devel("empty\n"); - return; - } - -move_to_meta: - if (assoc_array_ptr_is_shortcut(cursor)) { - /* Descend through a shortcut */ - pr_devel("[%d] shortcut\n", slot); - BUG_ON(!assoc_array_ptr_is_shortcut(cursor)); - shortcut =3D assoc_array_ptr_to_shortcut(cursor); - BUG_ON(shortcut->back_pointer !=3D parent); - BUG_ON(slot !=3D -1 && shortcut->parent_slot !=3D slot); - parent =3D cursor; - cursor =3D shortcut->next_node; - slot =3D -1; - BUG_ON(!assoc_array_ptr_is_node(cursor)); - } - - pr_devel("[%d] node\n", slot); - node =3D assoc_array_ptr_to_node(cursor); - BUG_ON(node->back_pointer !=3D parent); - BUG_ON(slot !=3D -1 && node->parent_slot !=3D slot); - slot =3D 0; - -continue_node: - pr_devel("Node %p [back=3D%p]\n", node, node->back_pointer); - for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) { - struct assoc_array_ptr *ptr =3D node->slots[slot]; - if (!ptr) - continue; - if (assoc_array_ptr_is_meta(ptr)) { - parent =3D cursor; - cursor =3D ptr; - goto move_to_meta; - } - - if (ops) { - pr_devel("[%d] free leaf\n", slot); - ops->free_object(assoc_array_ptr_to_leaf(ptr)); - } - } - - parent =3D node->back_pointer; - slot =3D node->parent_slot; - pr_devel("free node\n"); - kfree(node); - if (!parent) - return; /* Done */ - - /* Move back up to the parent (may need to free a shortcut on - * the way up) */ - if (assoc_array_ptr_is_shortcut(parent)) { - shortcut =3D assoc_array_ptr_to_shortcut(parent); - BUG_ON(shortcut->next_node !=3D cursor); - cursor =3D parent; - parent =3D shortcut->back_pointer; - slot =3D shortcut->parent_slot; - pr_devel("free shortcut\n"); - kfree(shortcut); - if (!parent) - return; - - BUG_ON(!assoc_array_ptr_is_node(parent)); - } - - /* Ascend to next slot in parent node */ - pr_devel("ascend to %p[%d]\n", parent, slot); - cursor =3D parent; - node =3D assoc_array_ptr_to_node(cursor); - slot++; - goto continue_node; -} - -/** - * assoc_array_destroy - Destroy an associative array - * @array: The array to destroy. - * @ops: The operations to use. - * - * Discard all metadata and free all objects in an associative array. The - * array will be empty and ready to use again upon completion. This funct= ion - * cannot fail. - * - * The caller must prevent all other accesses whilst this takes place as no - * attempt is made to adjust pointers gracefully to permit RCU readlock-ho= lding - * accesses to continue. On the other hand, no memory allocation is requi= red. - */ -void assoc_array_destroy(struct assoc_array *array, - const struct assoc_array_ops *ops) -{ - assoc_array_destroy_subtree(array->root, ops); - array->root =3D NULL; -} - -/* - * Handle insertion into an empty tree. - */ -static bool assoc_array_insert_in_empty_tree(struct assoc_array_edit *edit) -{ - struct assoc_array_node *new_n0; - - pr_devel("-->%s()\n", __func__); - - new_n0 =3D kzalloc_obj(struct assoc_array_node); - if (!new_n0) - return false; - - edit->new_meta[0] =3D assoc_array_node_to_ptr(new_n0); - edit->leaf_p =3D &new_n0->slots[0]; - edit->adjust_count_on =3D new_n0; - edit->set[0].ptr =3D &edit->array->root; - edit->set[0].to =3D assoc_array_node_to_ptr(new_n0); - - pr_devel("<--%s() =3D ok [no root]\n", __func__); - return true; -} - -/* - * Handle insertion into a terminal node. - */ -static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit = *edit, - const struct assoc_array_ops *ops, - const void *index_key, - struct assoc_array_walk_result *result) -{ - struct assoc_array_shortcut *shortcut, *new_s0; - struct assoc_array_node *node, *new_n0, *new_n1, *side; - struct assoc_array_ptr *ptr; - unsigned long dissimilarity, base_seg, blank; - size_t keylen; - bool have_meta; - int level, diff; - int slot, next_slot, free_slot, i, j; - - node =3D result->terminal_node.node; - level =3D result->terminal_node.level; - edit->segment_cache[ASSOC_ARRAY_FAN_OUT] =3D result->terminal_node.slot; - - pr_devel("-->%s()\n", __func__); - - /* We arrived at a node which doesn't have an onward node or shortcut - * pointer that we have to follow. This means that (a) the leaf we - * want must go here (either by insertion or replacement) or (b) we - * need to split this node and insert in one of the fragments. - */ - free_slot =3D -1; - - /* Firstly, we have to check the leaves in this node to see if there's - * a matching one we should replace in place. - */ - for (i =3D 0; i < ASSOC_ARRAY_FAN_OUT; i++) { - ptr =3D node->slots[i]; - if (!ptr) { - free_slot =3D i; - continue; - } - if (assoc_array_ptr_is_leaf(ptr) && - ops->compare_object(assoc_array_ptr_to_leaf(ptr), - index_key)) { - pr_devel("replace in slot %d\n", i); - edit->leaf_p =3D &node->slots[i]; - edit->dead_leaf =3D node->slots[i]; - pr_devel("<--%s() =3D ok [replace]\n", __func__); - return true; - } - } - - /* If there is a free slot in this node then we can just insert the - * leaf here. - */ - if (free_slot >=3D 0) { - pr_devel("insert in free slot %d\n", free_slot); - edit->leaf_p =3D &node->slots[free_slot]; - edit->adjust_count_on =3D node; - pr_devel("<--%s() =3D ok [insert]\n", __func__); - return true; - } - - /* The node has no spare slots - so we're either going to have to split - * it or insert another node before it. - * - * Whatever, we're going to need at least two new nodes - so allocate - * those now. We may also need a new shortcut, but we deal with that - * when we need it. - */ - new_n0 =3D kzalloc_obj(struct assoc_array_node); - if (!new_n0) - return false; - edit->new_meta[0] =3D assoc_array_node_to_ptr(new_n0); - new_n1 =3D kzalloc_obj(struct assoc_array_node); - if (!new_n1) - return false; - edit->new_meta[1] =3D assoc_array_node_to_ptr(new_n1); - - /* We need to find out how similar the leaves are. */ - pr_devel("no spare slots\n"); - have_meta =3D false; - for (i =3D 0; i < ASSOC_ARRAY_FAN_OUT; i++) { - ptr =3D node->slots[i]; - if (assoc_array_ptr_is_meta(ptr)) { - edit->segment_cache[i] =3D 0xff; - have_meta =3D true; - continue; - } - base_seg =3D ops->get_object_key_chunk( - assoc_array_ptr_to_leaf(ptr), level); - base_seg >>=3D level & ASSOC_ARRAY_KEY_CHUNK_MASK; - edit->segment_cache[i] =3D base_seg & ASSOC_ARRAY_FAN_MASK; - } - - if (have_meta) { - pr_devel("have meta\n"); - goto split_node; - } - - /* The node contains only leaves */ - dissimilarity =3D 0; - base_seg =3D edit->segment_cache[0]; - for (i =3D 1; i < ASSOC_ARRAY_FAN_OUT; i++) - dissimilarity |=3D edit->segment_cache[i] ^ base_seg; - - pr_devel("only leaves; dissimilarity=3D%lx\n", dissimilarity); - - if ((dissimilarity & ASSOC_ARRAY_FAN_MASK) =3D=3D 0) { - /* The old leaves all cluster in the same slot. We will need - * to insert a shortcut if the new node wants to cluster with them. - */ - if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) =3D=3D 0) - goto all_leaves_cluster_together; - - /* Otherwise all the old leaves cluster in the same slot, but - * the new leaf wants to go into a different slot - so we - * create a new node (n0) to hold the new leaf and a pointer to - * a new node (n1) holding all the old leaves. - * - * This can be done by falling through to the node splitting - * path. - */ - pr_devel("present leaves cluster but not new leaf\n"); - } - -split_node: - pr_devel("split node\n"); - - /* We need to split the current node. The node must contain anything - * from a single leaf (in the one leaf case, this leaf will cluster - * with the new leaf) and the rest meta-pointers, to all leaves, some - * of which may cluster. - * - * It won't contain the case in which all the current leaves plus the - * new leaves want to cluster in the same slot. - * - * We need to expel at least two leaves out of a set consisting of the - * leaves in the node and the new leaf. The current meta pointers can - * just be copied as they shouldn't cluster with any of the leaves. - * - * We need a new node (n0) to replace the current one and a new node to - * take the expelled nodes (n1). - */ - edit->set[0].to =3D assoc_array_node_to_ptr(new_n0); - new_n0->back_pointer =3D node->back_pointer; - new_n0->parent_slot =3D node->parent_slot; - new_n1->back_pointer =3D assoc_array_node_to_ptr(new_n0); - new_n1->parent_slot =3D -1; /* Need to calculate this */ - -do_split_node: - pr_devel("do_split_node\n"); - - new_n0->nr_leaves_on_branch =3D node->nr_leaves_on_branch; - new_n1->nr_leaves_on_branch =3D 0; - - /* Begin by finding two matching leaves. There have to be at least two - * that match - even if there are meta pointers - because any leaf that - * would match a slot with a meta pointer in it must be somewhere - * behind that meta pointer and cannot be here. Further, given N - * remaining leaf slots, we now have N+1 leaves to go in them. - */ - for (i =3D 0; i < ASSOC_ARRAY_FAN_OUT; i++) { - slot =3D edit->segment_cache[i]; - if (slot !=3D 0xff) - for (j =3D i + 1; j < ASSOC_ARRAY_FAN_OUT + 1; j++) - if (edit->segment_cache[j] =3D=3D slot) - goto found_slot_for_multiple_occupancy; - } -found_slot_for_multiple_occupancy: - pr_devel("same slot: %x %x [%02x]\n", i, j, slot); - BUG_ON(i >=3D ASSOC_ARRAY_FAN_OUT); - BUG_ON(j >=3D ASSOC_ARRAY_FAN_OUT + 1); - BUG_ON(slot >=3D ASSOC_ARRAY_FAN_OUT); - - new_n1->parent_slot =3D slot; - - /* Metadata pointers cannot change slot */ - for (i =3D 0; i < ASSOC_ARRAY_FAN_OUT; i++) - if (assoc_array_ptr_is_meta(node->slots[i])) - new_n0->slots[i] =3D node->slots[i]; - else - new_n0->slots[i] =3D NULL; - BUG_ON(new_n0->slots[slot] !=3D NULL); - new_n0->slots[slot] =3D assoc_array_node_to_ptr(new_n1); - - /* Filter the leaf pointers between the new nodes */ - free_slot =3D -1; - next_slot =3D 0; - for (i =3D 0; i < ASSOC_ARRAY_FAN_OUT; i++) { - if (assoc_array_ptr_is_meta(node->slots[i])) - continue; - if (edit->segment_cache[i] =3D=3D slot) { - new_n1->slots[next_slot++] =3D node->slots[i]; - new_n1->nr_leaves_on_branch++; - } else { - do { - free_slot++; - } while (new_n0->slots[free_slot] !=3D NULL); - new_n0->slots[free_slot] =3D node->slots[i]; - } - } - - pr_devel("filtered: f=3D%x n=3D%x\n", free_slot, next_slot); - - if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] !=3D slot) { - do { - free_slot++; - } while (new_n0->slots[free_slot] !=3D NULL); - edit->leaf_p =3D &new_n0->slots[free_slot]; - edit->adjust_count_on =3D new_n0; - } else { - edit->leaf_p =3D &new_n1->slots[next_slot++]; - edit->adjust_count_on =3D new_n1; - } - - BUG_ON(next_slot <=3D 1); - - edit->set_backpointers_to =3D assoc_array_node_to_ptr(new_n0); - for (i =3D 0; i < ASSOC_ARRAY_FAN_OUT; i++) { - if (edit->segment_cache[i] =3D=3D 0xff) { - ptr =3D node->slots[i]; - BUG_ON(assoc_array_ptr_is_leaf(ptr)); - if (assoc_array_ptr_is_node(ptr)) { - side =3D assoc_array_ptr_to_node(ptr); - edit->set_backpointers[i] =3D &side->back_pointer; - } else { - shortcut =3D assoc_array_ptr_to_shortcut(ptr); - edit->set_backpointers[i] =3D &shortcut->back_pointer; - } - } - } - - ptr =3D node->back_pointer; - if (!ptr) - edit->set[0].ptr =3D &edit->array->root; - else if (assoc_array_ptr_is_node(ptr)) - edit->set[0].ptr =3D &assoc_array_ptr_to_node(ptr)->slots[node->parent_s= lot]; - else - edit->set[0].ptr =3D &assoc_array_ptr_to_shortcut(ptr)->next_node; - edit->excised_meta[0] =3D assoc_array_node_to_ptr(node); - pr_devel("<--%s() =3D ok [split node]\n", __func__); - return true; - -all_leaves_cluster_together: - /* All the leaves, new and old, want to cluster together in this node - * in the same slot, so we have to replace this node with a shortcut to - * skip over the identical parts of the key and then place a pair of - * nodes, one inside the other, at the end of the shortcut and - * distribute the keys between them. - * - * Firstly we need to work out where the leaves start diverging as a - * bit position into their keys so that we know how big the shortcut - * needs to be. - * - * We only need to make a single pass of N of the N+1 leaves because if - * any keys differ between themselves at bit X then at least one of - * them must also differ with the base key at bit X or before. - */ - pr_devel("all leaves cluster together\n"); - diff =3D INT_MAX; - for (i =3D 0; i < ASSOC_ARRAY_FAN_OUT; i++) { - int x =3D ops->diff_objects(assoc_array_ptr_to_leaf(node->slots[i]), - index_key); - if (x < diff) { - BUG_ON(x < 0); - diff =3D x; - } - } - BUG_ON(diff =3D=3D INT_MAX); - BUG_ON(diff < level + ASSOC_ARRAY_LEVEL_STEP); - - keylen =3D round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE); - keylen >>=3D ASSOC_ARRAY_KEY_CHUNK_SHIFT; - - new_s0 =3D kzalloc_flex(*new_s0, index_key, keylen); - if (!new_s0) - return false; - edit->new_meta[2] =3D assoc_array_shortcut_to_ptr(new_s0); - - edit->set[0].to =3D assoc_array_shortcut_to_ptr(new_s0); - new_s0->back_pointer =3D node->back_pointer; - new_s0->parent_slot =3D node->parent_slot; - new_s0->next_node =3D assoc_array_node_to_ptr(new_n0); - new_n0->back_pointer =3D assoc_array_shortcut_to_ptr(new_s0); - new_n0->parent_slot =3D 0; - new_n1->back_pointer =3D assoc_array_node_to_ptr(new_n0); - new_n1->parent_slot =3D -1; /* Need to calculate this */ - - new_s0->skip_to_level =3D level =3D diff & ~ASSOC_ARRAY_LEVEL_STEP_MASK; - pr_devel("skip_to_level =3D %d [diff %d]\n", level, diff); - BUG_ON(level <=3D 0); - - for (i =3D 0; i < keylen; i++) - new_s0->index_key[i] =3D - ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE); - - if (level & ASSOC_ARRAY_KEY_CHUNK_MASK) { - blank =3D ULONG_MAX << (level & ASSOC_ARRAY_KEY_CHUNK_MASK); - pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank); - new_s0->index_key[keylen - 1] &=3D ~blank; - } - - /* This now reduces to a node splitting exercise for which we'll need - * to regenerate the disparity table. - */ - for (i =3D 0; i < ASSOC_ARRAY_FAN_OUT; i++) { - ptr =3D node->slots[i]; - base_seg =3D ops->get_object_key_chunk(assoc_array_ptr_to_leaf(ptr), - level); - base_seg >>=3D level & ASSOC_ARRAY_KEY_CHUNK_MASK; - edit->segment_cache[i] =3D base_seg & ASSOC_ARRAY_FAN_MASK; - } - - base_seg =3D ops->get_key_chunk(index_key, level); - base_seg >>=3D level & ASSOC_ARRAY_KEY_CHUNK_MASK; - edit->segment_cache[ASSOC_ARRAY_FAN_OUT] =3D base_seg & ASSOC_ARRAY_FAN_M= ASK; - goto do_split_node; -} - -/* - * Handle insertion into the middle of a shortcut. - */ -static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit, - const struct assoc_array_ops *ops, - struct assoc_array_walk_result *result) -{ - struct assoc_array_shortcut *shortcut, *new_s0, *new_s1; - struct assoc_array_node *node, *new_n0, *side; - unsigned long sc_segments, dissimilarity, blank; - size_t keylen; - int level, sc_level, diff; - int sc_slot; - - shortcut =3D result->wrong_shortcut.shortcut; - level =3D result->wrong_shortcut.level; - sc_level =3D result->wrong_shortcut.sc_level; - sc_segments =3D result->wrong_shortcut.sc_segments; - dissimilarity =3D result->wrong_shortcut.dissimilarity; - - pr_devel("-->%s(ix=3D%d dis=3D%lx scix=3D%d)\n", - __func__, level, dissimilarity, sc_level); - - /* We need to split a shortcut and insert a node between the two - * pieces. Zero-length pieces will be dispensed with entirely. - * - * First of all, we need to find out in which level the first - * difference was. - */ - diff =3D __ffs(dissimilarity); - diff &=3D ~ASSOC_ARRAY_LEVEL_STEP_MASK; - diff +=3D sc_level & ~ASSOC_ARRAY_KEY_CHUNK_MASK; - pr_devel("diff=3D%d\n", diff); - - if (!shortcut->back_pointer) { - edit->set[0].ptr =3D &edit->array->root; - } else if (assoc_array_ptr_is_node(shortcut->back_pointer)) { - node =3D assoc_array_ptr_to_node(shortcut->back_pointer); - edit->set[0].ptr =3D &node->slots[shortcut->parent_slot]; - } else { - BUG(); - } - - edit->excised_meta[0] =3D assoc_array_shortcut_to_ptr(shortcut); - - /* Create a new node now since we're going to need it anyway */ - new_n0 =3D kzalloc_obj(struct assoc_array_node); - if (!new_n0) - return false; - edit->new_meta[0] =3D assoc_array_node_to_ptr(new_n0); - edit->adjust_count_on =3D new_n0; - - /* Insert a new shortcut before the new node if this segment isn't of - * zero length - otherwise we just connect the new node directly to the - * parent. - */ - level +=3D ASSOC_ARRAY_LEVEL_STEP; - if (diff > level) { - pr_devel("pre-shortcut %d...%d\n", level, diff); - keylen =3D round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE); - keylen >>=3D ASSOC_ARRAY_KEY_CHUNK_SHIFT; - - new_s0 =3D kzalloc_flex(*new_s0, index_key, keylen); - if (!new_s0) - return false; - edit->new_meta[1] =3D assoc_array_shortcut_to_ptr(new_s0); - edit->set[0].to =3D assoc_array_shortcut_to_ptr(new_s0); - new_s0->back_pointer =3D shortcut->back_pointer; - new_s0->parent_slot =3D shortcut->parent_slot; - new_s0->next_node =3D assoc_array_node_to_ptr(new_n0); - new_s0->skip_to_level =3D diff; - - new_n0->back_pointer =3D assoc_array_shortcut_to_ptr(new_s0); - new_n0->parent_slot =3D 0; - - memcpy(new_s0->index_key, shortcut->index_key, - flex_array_size(new_s0, index_key, keylen)); - - blank =3D ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK); - pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank); - new_s0->index_key[keylen - 1] &=3D ~blank; - } else { - pr_devel("no pre-shortcut\n"); - edit->set[0].to =3D assoc_array_node_to_ptr(new_n0); - new_n0->back_pointer =3D shortcut->back_pointer; - new_n0->parent_slot =3D shortcut->parent_slot; - } - - side =3D assoc_array_ptr_to_node(shortcut->next_node); - new_n0->nr_leaves_on_branch =3D side->nr_leaves_on_branch; - - /* We need to know which slot in the new node is going to take a - * metadata pointer. - */ - sc_slot =3D sc_segments >> (diff & ASSOC_ARRAY_KEY_CHUNK_MASK); - sc_slot &=3D ASSOC_ARRAY_FAN_MASK; - - pr_devel("new slot %lx >> %d -> %d\n", - sc_segments, diff & ASSOC_ARRAY_KEY_CHUNK_MASK, sc_slot); - - /* Determine whether we need to follow the new node with a replacement - * for the current shortcut. We could in theory reuse the current - * shortcut if its parent slot number doesn't change - but that's a - * 1-in-16 chance so not worth expending the code upon. - */ - level =3D diff + ASSOC_ARRAY_LEVEL_STEP; - if (level < shortcut->skip_to_level) { - pr_devel("post-shortcut %d...%d\n", level, shortcut->skip_to_level); - keylen =3D round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE); - keylen >>=3D ASSOC_ARRAY_KEY_CHUNK_SHIFT; - - new_s1 =3D kzalloc_flex(*new_s1, index_key, keylen); - if (!new_s1) - return false; - edit->new_meta[2] =3D assoc_array_shortcut_to_ptr(new_s1); - - new_s1->back_pointer =3D assoc_array_node_to_ptr(new_n0); - new_s1->parent_slot =3D sc_slot; - new_s1->next_node =3D shortcut->next_node; - new_s1->skip_to_level =3D shortcut->skip_to_level; - - new_n0->slots[sc_slot] =3D assoc_array_shortcut_to_ptr(new_s1); - - memcpy(new_s1->index_key, shortcut->index_key, - flex_array_size(new_s1, index_key, keylen)); - - edit->set[1].ptr =3D &side->back_pointer; - edit->set[1].to =3D assoc_array_shortcut_to_ptr(new_s1); - } else { - pr_devel("no post-shortcut\n"); - - /* We don't have to replace the pointed-to node as long as we - * use memory barriers to make sure the parent slot number is - * changed before the back pointer (the parent slot number is - * irrelevant to the old parent shortcut). - */ - new_n0->slots[sc_slot] =3D shortcut->next_node; - edit->set_parent_slot[0].p =3D &side->parent_slot; - edit->set_parent_slot[0].to =3D sc_slot; - edit->set[1].ptr =3D &side->back_pointer; - edit->set[1].to =3D assoc_array_node_to_ptr(new_n0); - } - - /* Install the new leaf in a spare slot in the new node. */ - if (sc_slot =3D=3D 0) - edit->leaf_p =3D &new_n0->slots[1]; - else - edit->leaf_p =3D &new_n0->slots[0]; - - pr_devel("<--%s() =3D ok [split shortcut]\n", __func__); - return true; -} - -/** - * assoc_array_insert - Script insertion of an object into an associative = array - * @array: The array to insert into. - * @ops: The operations to use. - * @index_key: The key to insert at. - * @object: The object to insert. - * - * Precalculate and preallocate a script for the insertion or replacement = of an - * object in an associative array. This results in an edit script that can - * either be applied or cancelled. - * - * The function returns a pointer to an edit script or -ENOMEM. - * - * The caller should lock against other modifications and must continue to= hold - * the lock until assoc_array_apply_edit() has been called. - * - * Accesses to the tree may take place concurrently with this function, - * provided they hold the RCU read lock. - */ -struct assoc_array_edit *assoc_array_insert(struct assoc_array *array, - const struct assoc_array_ops *ops, - const void *index_key, - void *object) -{ - struct assoc_array_walk_result result; - struct assoc_array_edit *edit; - - pr_devel("-->%s()\n", __func__); - - /* The leaf pointer we're given must not have the bottom bit set as we - * use those for type-marking the pointer. NULL pointers are also not - * allowed as they indicate an empty slot but we have to allow them - * here as they can be updated later. - */ - BUG_ON(assoc_array_ptr_is_meta(object)); - - edit =3D kzalloc_obj(struct assoc_array_edit); - if (!edit) - return ERR_PTR(-ENOMEM); - edit->array =3D array; - edit->ops =3D ops; - edit->leaf =3D assoc_array_leaf_to_ptr(object); - edit->adjust_count_by =3D 1; - - switch (assoc_array_walk(array, ops, index_key, &result)) { - case assoc_array_walk_tree_empty: - /* Allocate a root node if there isn't one yet */ - if (!assoc_array_insert_in_empty_tree(edit)) - goto enomem; - return edit; - - case assoc_array_walk_found_terminal_node: - /* We found a node that doesn't have a node/shortcut pointer in - * the slot corresponding to the index key that we have to - * follow. - */ - if (!assoc_array_insert_into_terminal_node(edit, ops, index_key, - &result)) - goto enomem; - return edit; - - case assoc_array_walk_found_wrong_shortcut: - /* We found a shortcut that didn't match our key in a slot we - * needed to follow. - */ - if (!assoc_array_insert_mid_shortcut(edit, ops, &result)) - goto enomem; - return edit; - } - -enomem: - /* Clean up after an out of memory error */ - pr_devel("enomem\n"); - assoc_array_cancel_edit(edit); - return ERR_PTR(-ENOMEM); -} - -/** - * assoc_array_insert_set_object - Set the new object pointer in an edit s= cript - * @edit: The edit script to modify. - * @object: The object pointer to set. - * - * Change the object to be inserted in an edit script. The object pointed= to - * by the old object is not freed. This must be done prior to applying the - * script. - */ -void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *ob= ject) -{ - BUG_ON(!object); - edit->leaf =3D assoc_array_leaf_to_ptr(object); -} - -struct assoc_array_delete_collapse_context { - struct assoc_array_node *node; - const void *skip_leaf; - int slot; -}; - -/* - * Subtree collapse to node iterator. - */ -static int assoc_array_delete_collapse_iterator(const void *leaf, - void *iterator_data) -{ - struct assoc_array_delete_collapse_context *collapse =3D iterator_data; - - if (leaf =3D=3D collapse->skip_leaf) - return 0; - - BUG_ON(collapse->slot >=3D ASSOC_ARRAY_FAN_OUT); - - collapse->node->slots[collapse->slot++] =3D assoc_array_leaf_to_ptr(leaf); - return 0; -} - -/** - * assoc_array_delete - Script deletion of an object from an associative a= rray - * @array: The array to search. - * @ops: The operations to use. - * @index_key: The key to the object. - * - * Precalculate and preallocate a script for the deletion of an object fro= m an - * associative array. This results in an edit script that can either be - * applied or cancelled. - * - * The function returns a pointer to an edit script if the object was foun= d, - * NULL if the object was not found or -ENOMEM. - * - * The caller should lock against other modifications and must continue to= hold - * the lock until assoc_array_apply_edit() has been called. - * - * Accesses to the tree may take place concurrently with this function, - * provided they hold the RCU read lock. - */ -struct assoc_array_edit *assoc_array_delete(struct assoc_array *array, - const struct assoc_array_ops *ops, - const void *index_key) -{ - struct assoc_array_delete_collapse_context collapse; - struct assoc_array_walk_result result; - struct assoc_array_node *node, *new_n0; - struct assoc_array_edit *edit; - struct assoc_array_ptr *ptr; - bool has_meta; - int slot, i; - - pr_devel("-->%s()\n", __func__); - - edit =3D kzalloc_obj(struct assoc_array_edit); - if (!edit) - return ERR_PTR(-ENOMEM); - edit->array =3D array; - edit->ops =3D ops; - edit->adjust_count_by =3D -1; - - switch (assoc_array_walk(array, ops, index_key, &result)) { - case assoc_array_walk_found_terminal_node: - /* We found a node that should contain the leaf we've been - * asked to remove - *if* it's in the tree. - */ - pr_devel("terminal_node\n"); - node =3D result.terminal_node.node; - - for (slot =3D 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) { - ptr =3D node->slots[slot]; - if (ptr && - assoc_array_ptr_is_leaf(ptr) && - ops->compare_object(assoc_array_ptr_to_leaf(ptr), - index_key)) - goto found_leaf; - } - fallthrough; - case assoc_array_walk_tree_empty: - case assoc_array_walk_found_wrong_shortcut: - default: - assoc_array_cancel_edit(edit); - pr_devel("not found\n"); - return NULL; - } - -found_leaf: - BUG_ON(array->nr_leaves_on_tree <=3D 0); - - /* In the simplest form of deletion we just clear the slot and release - * the leaf after a suitable interval. - */ - edit->dead_leaf =3D node->slots[slot]; - edit->set[0].ptr =3D &node->slots[slot]; - edit->set[0].to =3D NULL; - edit->adjust_count_on =3D node; - - /* If that concludes erasure of the last leaf, then delete the entire - * internal array. - */ - if (array->nr_leaves_on_tree =3D=3D 1) { - edit->set[1].ptr =3D &array->root; - edit->set[1].to =3D NULL; - edit->adjust_count_on =3D NULL; - edit->excised_subtree =3D array->root; - pr_devel("all gone\n"); - return edit; - } - - /* However, we'd also like to clear up some metadata blocks if we - * possibly can. - * - * We go for a simple algorithm of: if this node has FAN_OUT or fewer - * leaves in it, then attempt to collapse it - and attempt to - * recursively collapse up the tree. - * - * We could also try and collapse in partially filled subtrees to take - * up space in this node. - */ - if (node->nr_leaves_on_branch <=3D ASSOC_ARRAY_FAN_OUT + 1) { - struct assoc_array_node *parent, *grandparent; - struct assoc_array_ptr *ptr; - - /* First of all, we need to know if this node has metadata so - * that we don't try collapsing if all the leaves are already - * here. - */ - has_meta =3D false; - for (i =3D 0; i < ASSOC_ARRAY_FAN_OUT; i++) { - ptr =3D node->slots[i]; - if (assoc_array_ptr_is_meta(ptr)) { - has_meta =3D true; - break; - } - } - - pr_devel("leaves: %ld [m=3D%d]\n", - node->nr_leaves_on_branch - 1, has_meta); - - /* Look further up the tree to see if we can collapse this node - * into a more proximal node too. - */ - parent =3D node; - collapse_up: - pr_devel("collapse subtree: %ld\n", parent->nr_leaves_on_branch); - - ptr =3D parent->back_pointer; - if (!ptr) - goto do_collapse; - if (assoc_array_ptr_is_shortcut(ptr)) { - struct assoc_array_shortcut *s =3D assoc_array_ptr_to_shortcut(ptr); - ptr =3D s->back_pointer; - if (!ptr) - goto do_collapse; - } - - grandparent =3D assoc_array_ptr_to_node(ptr); - if (grandparent->nr_leaves_on_branch <=3D ASSOC_ARRAY_FAN_OUT + 1) { - parent =3D grandparent; - goto collapse_up; - } - - do_collapse: - /* There's no point collapsing if the original node has no meta - * pointers to discard and if we didn't merge into one of that - * node's ancestry. - */ - if (has_meta || parent !=3D node) { - node =3D parent; - - /* Create a new node to collapse into */ - new_n0 =3D kzalloc_obj(struct assoc_array_node); - if (!new_n0) - goto enomem; - edit->new_meta[0] =3D assoc_array_node_to_ptr(new_n0); - - new_n0->back_pointer =3D node->back_pointer; - new_n0->parent_slot =3D node->parent_slot; - new_n0->nr_leaves_on_branch =3D node->nr_leaves_on_branch; - edit->adjust_count_on =3D new_n0; - - collapse.node =3D new_n0; - collapse.skip_leaf =3D assoc_array_ptr_to_leaf(edit->dead_leaf); - collapse.slot =3D 0; - assoc_array_subtree_iterate(assoc_array_node_to_ptr(node), - node->back_pointer, - assoc_array_delete_collapse_iterator, - &collapse); - pr_devel("collapsed %d,%lu\n", collapse.slot, new_n0->nr_leaves_on_bran= ch); - BUG_ON(collapse.slot !=3D new_n0->nr_leaves_on_branch - 1); - - if (!node->back_pointer) { - edit->set[1].ptr =3D &array->root; - } else if (assoc_array_ptr_is_leaf(node->back_pointer)) { - BUG(); - } else if (assoc_array_ptr_is_node(node->back_pointer)) { - struct assoc_array_node *p =3D - assoc_array_ptr_to_node(node->back_pointer); - edit->set[1].ptr =3D &p->slots[node->parent_slot]; - } else if (assoc_array_ptr_is_shortcut(node->back_pointer)) { - struct assoc_array_shortcut *s =3D - assoc_array_ptr_to_shortcut(node->back_pointer); - edit->set[1].ptr =3D &s->next_node; - } - edit->set[1].to =3D assoc_array_node_to_ptr(new_n0); - edit->excised_subtree =3D assoc_array_node_to_ptr(node); - } - } - - return edit; - -enomem: - /* Clean up after an out of memory error */ - pr_devel("enomem\n"); - assoc_array_cancel_edit(edit); - return ERR_PTR(-ENOMEM); -} - -/** - * assoc_array_clear - Script deletion of all objects from an associative = array - * @array: The array to clear. - * @ops: The operations to use. - * - * Precalculate and preallocate a script for the deletion of all the objec= ts - * from an associative array. This results in an edit script that can eit= her - * be applied or cancelled. - * - * The function returns a pointer to an edit script if there are objects t= o be - * deleted, NULL if there are no objects in the array or -ENOMEM. - * - * The caller should lock against other modifications and must continue to= hold - * the lock until assoc_array_apply_edit() has been called. - * - * Accesses to the tree may take place concurrently with this function, - * provided they hold the RCU read lock. - */ -struct assoc_array_edit *assoc_array_clear(struct assoc_array *array, - const struct assoc_array_ops *ops) -{ - struct assoc_array_edit *edit; - - pr_devel("-->%s()\n", __func__); - - if (!array->root) - return NULL; - - edit =3D kzalloc_obj(struct assoc_array_edit); - if (!edit) - return ERR_PTR(-ENOMEM); - edit->array =3D array; - edit->ops =3D ops; - edit->set[1].ptr =3D &array->root; - edit->set[1].to =3D NULL; - edit->excised_subtree =3D array->root; - edit->ops_for_excised_subtree =3D ops; - pr_devel("all gone\n"); - return edit; -} - -/* - * Handle the deferred destruction after an applied edit. - */ -static void assoc_array_rcu_cleanup(struct rcu_head *head) -{ - struct assoc_array_edit *edit =3D - container_of(head, struct assoc_array_edit, rcu); - int i; - - pr_devel("-->%s()\n", __func__); - - if (edit->dead_leaf) - edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf)); - for (i =3D 0; i < ARRAY_SIZE(edit->excised_meta); i++) - if (edit->excised_meta[i]) - kfree(assoc_array_ptr_to_node(edit->excised_meta[i])); - - if (edit->excised_subtree) { - BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree)); - if (assoc_array_ptr_is_node(edit->excised_subtree)) { - struct assoc_array_node *n =3D - assoc_array_ptr_to_node(edit->excised_subtree); - n->back_pointer =3D NULL; - } else { - struct assoc_array_shortcut *s =3D - assoc_array_ptr_to_shortcut(edit->excised_subtree); - s->back_pointer =3D NULL; - } - assoc_array_destroy_subtree(edit->excised_subtree, - edit->ops_for_excised_subtree); - } - - kfree(edit); -} - -/** - * assoc_array_apply_edit - Apply an edit script to an associative array - * @edit: The script to apply. - * - * Apply an edit script to an associative array to effect an insertion, - * deletion or clearance. As the edit script includes preallocated memory, - * this is guaranteed not to fail. - * - * The edit script, dead objects and dead metadata will be scheduled for - * destruction after an RCU grace period to permit those doing read-only - * accesses on the array to continue to do so under the RCU read lock whil= st - * the edit is taking place. - */ -void assoc_array_apply_edit(struct assoc_array_edit *edit) -{ - struct assoc_array_shortcut *shortcut; - struct assoc_array_node *node; - struct assoc_array_ptr *ptr; - int i; - - pr_devel("-->%s()\n", __func__); - - smp_wmb(); - if (edit->leaf_p) - *edit->leaf_p =3D edit->leaf; - - smp_wmb(); - for (i =3D 0; i < ARRAY_SIZE(edit->set_parent_slot); i++) - if (edit->set_parent_slot[i].p) - *edit->set_parent_slot[i].p =3D edit->set_parent_slot[i].to; - - smp_wmb(); - for (i =3D 0; i < ARRAY_SIZE(edit->set_backpointers); i++) - if (edit->set_backpointers[i]) - *edit->set_backpointers[i] =3D edit->set_backpointers_to; - - smp_wmb(); - for (i =3D 0; i < ARRAY_SIZE(edit->set); i++) - if (edit->set[i].ptr) - *edit->set[i].ptr =3D edit->set[i].to; - - if (edit->array->root =3D=3D NULL) { - edit->array->nr_leaves_on_tree =3D 0; - } else if (edit->adjust_count_on) { - node =3D edit->adjust_count_on; - for (;;) { - node->nr_leaves_on_branch +=3D edit->adjust_count_by; - - ptr =3D node->back_pointer; - if (!ptr) - break; - if (assoc_array_ptr_is_shortcut(ptr)) { - shortcut =3D assoc_array_ptr_to_shortcut(ptr); - ptr =3D shortcut->back_pointer; - if (!ptr) - break; - } - BUG_ON(!assoc_array_ptr_is_node(ptr)); - node =3D assoc_array_ptr_to_node(ptr); - } - - edit->array->nr_leaves_on_tree +=3D edit->adjust_count_by; - } - - call_rcu(&edit->rcu, assoc_array_rcu_cleanup); -} - -/** - * assoc_array_cancel_edit - Discard an edit script. - * @edit: The script to discard. - * - * Free an edit script and all the preallocated data it holds without maki= ng - * any changes to the associative array it was intended for. - * - * NOTE! In the case of an insertion script, this does _not_ release the = leaf - * that was to be inserted. That is left to the caller. - */ -void assoc_array_cancel_edit(struct assoc_array_edit *edit) -{ - struct assoc_array_ptr *ptr; - int i; - - pr_devel("-->%s()\n", __func__); - - /* Clean up after an out of memory error */ - for (i =3D 0; i < ARRAY_SIZE(edit->new_meta); i++) { - ptr =3D edit->new_meta[i]; - if (ptr) { - if (assoc_array_ptr_is_node(ptr)) - kfree(assoc_array_ptr_to_node(ptr)); - else - kfree(assoc_array_ptr_to_shortcut(ptr)); - } - } - kfree(edit); -} - -/** - * assoc_array_gc - Garbage collect an associative array. - * @array: The array to clean. - * @ops: The operations to use. - * @iterator: A callback function to pass judgement on each object. - * @iterator_data: Private data for the callback function. - * - * Collect garbage from an associative array and pack down the internal tr= ee to - * save memory. - * - * The iterator function is asked to pass judgement upon each object in the - * array. If it returns false, the object is discard and if it returns tr= ue, - * the object is kept. If it returns true, it must increment the object's - * usage count (or whatever it needs to do to retain it) before returning. - * - * This function returns 0 if successful or -ENOMEM if out of memory. In = the - * latter case, the array is not changed. - * - * The caller should lock against other modifications and must continue to= hold - * the lock until assoc_array_apply_edit() has been called. - * - * Accesses to the tree may take place concurrently with this function, - * provided they hold the RCU read lock. - */ -int assoc_array_gc(struct assoc_array *array, - const struct assoc_array_ops *ops, - bool (*iterator)(void *object, void *iterator_data), - void *iterator_data) -{ - struct assoc_array_shortcut *shortcut, *new_s; - struct assoc_array_node *node, *new_n; - struct assoc_array_edit *edit; - struct assoc_array_ptr *cursor, *ptr; - struct assoc_array_ptr *new_root, *new_parent, **new_ptr_pp; - unsigned long nr_leaves_on_tree; - bool retained; - int keylen, slot, nr_free, next_slot, i; - - pr_devel("-->%s()\n", __func__); - - if (!array->root) - return 0; - - edit =3D kzalloc_obj(struct assoc_array_edit); - if (!edit) - return -ENOMEM; - edit->array =3D array; - edit->ops =3D ops; - edit->ops_for_excised_subtree =3D ops; - edit->set[0].ptr =3D &array->root; - edit->excised_subtree =3D array->root; - - new_root =3D new_parent =3D NULL; - new_ptr_pp =3D &new_root; - cursor =3D array->root; - -descend: - /* If this point is a shortcut, then we need to duplicate it and - * advance the target cursor. - */ - if (assoc_array_ptr_is_shortcut(cursor)) { - shortcut =3D assoc_array_ptr_to_shortcut(cursor); - keylen =3D round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE); - keylen >>=3D ASSOC_ARRAY_KEY_CHUNK_SHIFT; - new_s =3D kmalloc_flex(*new_s, index_key, keylen); - if (!new_s) - goto enomem; - pr_devel("dup shortcut %p -> %p\n", shortcut, new_s); - memcpy(new_s, shortcut, struct_size(new_s, index_key, keylen)); - new_s->back_pointer =3D new_parent; - new_s->parent_slot =3D shortcut->parent_slot; - *new_ptr_pp =3D new_parent =3D assoc_array_shortcut_to_ptr(new_s); - new_ptr_pp =3D &new_s->next_node; - cursor =3D shortcut->next_node; - } - - /* Duplicate the node at this position */ - node =3D assoc_array_ptr_to_node(cursor); - new_n =3D kzalloc_obj(struct assoc_array_node); - if (!new_n) - goto enomem; - pr_devel("dup node %p -> %p\n", node, new_n); - new_n->back_pointer =3D new_parent; - new_n->parent_slot =3D node->parent_slot; - *new_ptr_pp =3D new_parent =3D assoc_array_node_to_ptr(new_n); - new_ptr_pp =3D NULL; - slot =3D 0; - -continue_node: - /* Filter across any leaves and gc any subtrees */ - for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) { - ptr =3D node->slots[slot]; - if (!ptr) - continue; - - if (assoc_array_ptr_is_leaf(ptr)) { - if (iterator(assoc_array_ptr_to_leaf(ptr), - iterator_data)) - /* The iterator will have done any reference - * counting on the object for us. - */ - new_n->slots[slot] =3D ptr; - continue; - } - - new_ptr_pp =3D &new_n->slots[slot]; - cursor =3D ptr; - goto descend; - } - -retry_compress: - pr_devel("-- compress node %p --\n", new_n); - - /* Count up the number of empty slots in this node and work out the - * subtree leaf count. - */ - new_n->nr_leaves_on_branch =3D 0; - nr_free =3D 0; - for (slot =3D 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) { - ptr =3D new_n->slots[slot]; - if (!ptr) - nr_free++; - else if (assoc_array_ptr_is_leaf(ptr)) - new_n->nr_leaves_on_branch++; - } - pr_devel("free=3D%d, leaves=3D%lu\n", nr_free, new_n->nr_leaves_on_branch= ); - - /* See what we can fold in */ - retained =3D false; - next_slot =3D 0; - for (slot =3D 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) { - struct assoc_array_shortcut *s; - struct assoc_array_node *child; - - ptr =3D new_n->slots[slot]; - if (!ptr || assoc_array_ptr_is_leaf(ptr)) - continue; - - s =3D NULL; - if (assoc_array_ptr_is_shortcut(ptr)) { - s =3D assoc_array_ptr_to_shortcut(ptr); - ptr =3D s->next_node; - } - - child =3D assoc_array_ptr_to_node(ptr); - new_n->nr_leaves_on_branch +=3D child->nr_leaves_on_branch; - - if (child->nr_leaves_on_branch <=3D nr_free + 1) { - /* Fold the child node into this one */ - pr_devel("[%d] fold node %lu/%d [nx %d]\n", - slot, child->nr_leaves_on_branch, nr_free + 1, - next_slot); - - /* We would already have reaped an intervening shortcut - * on the way back up the tree. - */ - BUG_ON(s); - - new_n->slots[slot] =3D NULL; - nr_free++; - if (slot < next_slot) - next_slot =3D slot; - for (i =3D 0; i < ASSOC_ARRAY_FAN_OUT; i++) { - struct assoc_array_ptr *p =3D child->slots[i]; - if (!p) - continue; - BUG_ON(assoc_array_ptr_is_meta(p)); - while (new_n->slots[next_slot]) - next_slot++; - BUG_ON(next_slot >=3D ASSOC_ARRAY_FAN_OUT); - new_n->slots[next_slot++] =3D p; - nr_free--; - } - kfree(child); - } else { - pr_devel("[%d] retain node %lu/%d [nx %d]\n", - slot, child->nr_leaves_on_branch, nr_free + 1, - next_slot); - retained =3D true; - } - } - - if (retained && new_n->nr_leaves_on_branch <=3D ASSOC_ARRAY_FAN_OUT) { - pr_devel("internal nodes remain despite enough space, retrying\n"); - goto retry_compress; - } - pr_devel("after: %lu\n", new_n->nr_leaves_on_branch); - - nr_leaves_on_tree =3D new_n->nr_leaves_on_branch; - - /* Excise this node if it is singly occupied by a shortcut */ - if (nr_free =3D=3D ASSOC_ARRAY_FAN_OUT - 1) { - for (slot =3D 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) - if ((ptr =3D new_n->slots[slot])) - break; - - if (assoc_array_ptr_is_meta(ptr) && - assoc_array_ptr_is_shortcut(ptr)) { - pr_devel("excise node %p with 1 shortcut\n", new_n); - new_s =3D assoc_array_ptr_to_shortcut(ptr); - new_parent =3D new_n->back_pointer; - slot =3D new_n->parent_slot; - kfree(new_n); - if (!new_parent) { - new_s->back_pointer =3D NULL; - new_s->parent_slot =3D 0; - new_root =3D ptr; - goto gc_complete; - } - - if (assoc_array_ptr_is_shortcut(new_parent)) { - /* We can discard any preceding shortcut also */ - struct assoc_array_shortcut *s =3D - assoc_array_ptr_to_shortcut(new_parent); - - pr_devel("excise preceding shortcut\n"); - - new_parent =3D new_s->back_pointer =3D s->back_pointer; - slot =3D new_s->parent_slot =3D s->parent_slot; - kfree(s); - if (!new_parent) { - new_s->back_pointer =3D NULL; - new_s->parent_slot =3D 0; - new_root =3D ptr; - goto gc_complete; - } - } - - new_s->back_pointer =3D new_parent; - new_s->parent_slot =3D slot; - new_n =3D assoc_array_ptr_to_node(new_parent); - new_n->slots[slot] =3D ptr; - goto ascend_old_tree; - } - } - - /* Excise any shortcuts we might encounter that point to nodes that - * only contain leaves. - */ - ptr =3D new_n->back_pointer; - if (!ptr) - goto gc_complete; - - if (assoc_array_ptr_is_shortcut(ptr)) { - new_s =3D assoc_array_ptr_to_shortcut(ptr); - new_parent =3D new_s->back_pointer; - slot =3D new_s->parent_slot; - - if (new_n->nr_leaves_on_branch <=3D ASSOC_ARRAY_FAN_OUT) { - struct assoc_array_node *n; - - pr_devel("excise shortcut\n"); - new_n->back_pointer =3D new_parent; - new_n->parent_slot =3D slot; - kfree(new_s); - if (!new_parent) { - new_root =3D assoc_array_node_to_ptr(new_n); - goto gc_complete; - } - - n =3D assoc_array_ptr_to_node(new_parent); - n->slots[slot] =3D assoc_array_node_to_ptr(new_n); - } - } else { - new_parent =3D ptr; - } - new_n =3D assoc_array_ptr_to_node(new_parent); - -ascend_old_tree: - ptr =3D node->back_pointer; - if (assoc_array_ptr_is_shortcut(ptr)) { - shortcut =3D assoc_array_ptr_to_shortcut(ptr); - slot =3D shortcut->parent_slot; - cursor =3D shortcut->back_pointer; - if (!cursor) - goto gc_complete; - } else { - slot =3D node->parent_slot; - cursor =3D ptr; - } - BUG_ON(!cursor); - node =3D assoc_array_ptr_to_node(cursor); - slot++; - goto continue_node; - -gc_complete: - edit->set[0].to =3D new_root; - assoc_array_apply_edit(edit); - array->nr_leaves_on_tree =3D nr_leaves_on_tree; - return 0; - -enomem: - pr_devel("enomem\n"); - assoc_array_destroy_subtree(new_root, edit->ops); - kfree(edit); - return -ENOMEM; -} --=20 2.47.3