[PATCH v13 0/7] KEYS: Replace assoc_array with rhashtable

[Jarkko Sakkinen <jarkko@kernel.org>]

The keyrings subsystem is the sole user of assoc_array. It has over 1700
lines of code, no test suite, and a long history of bugs, with LLMs now
finding more.

This unfortunate outcome has evolved over time by large from the shortage
of in-kernel callers, time bandwidth and 3rd party contributors.  What the
keyrings subsystem needs is just a generic key-value store, which performs
well with sparse key sets. Replace assoc_array with an rhashtable-backed
keyring index and remove assoc_array from the kernel.

CHANGES
=======

v13:
- s390/cert_store: Hold key reference across key_unlink(), and ignore -ENOENT.
- s390/cert_store: Add "s390/cert_store: Read-lock keyring semaphore in
  invalidate_keyring_keys()".

v12:
- Fixed Sashiko reported issues in s390/cert_store patches.

v11:
- RCU-safe iterator for keyring_read().
- Addresses s390 issues. I won't carry them for long in the series.

v10:
- No changes since the previous round. This is a sanity check round
  given the lack of feedback to v9. I'll apply these patch very soon,
  unless nothing (relevant) comes up fast.

v9:
- Replace __free(kfree) with explicit cleanup so early goto out paths
  cannot bypass initialization of the link pointer. Preserve kleave()
  tracing on all exit paths.

v8:
- Fixed broken rebase.
- Restructured __key_link_begin() a bit as a response to a minor
  complaint from Sashiko.
- Fixed a minor glitch in __key_link_begin(): now also first invariant
  invokes kleave() on failure.

v7:
- Rebased.

v6:
- Eric Biggers: Set .insecure_elasticity = true in keyring_link_params and
  drop the -EBUSY retry loop in __key_link_begin().
- Addeded Reviewed-by's from Eric Bigger and Ignat Korchagin.

v5:
- Eric Biggers: Include <linux/jhash.h> explicitly in keyring.c.
- Eric Biggers: Document why hashing type/domain_tag pointers with SipHash
  and truncating the digest to 32 bits are safe.
- Eric Biggers: Rework the commit message for "KEYS: Replace assoc_array
  with rhashtable", including behavioral and operational changes.
- Retry rhashtable_insert_fast() on transient -EBUSY in __key_link_begin().

v4:
- Eric Biggers: Correct the kerneldoc summary for keyring_is_empty().
- Eric Biggers: Truncate keyring_index_key hash to u32 and drop index_id.
- Eric Biggers, David Howells: Use a proper struct instead of a two-element
  array to pass the edits.
- Eric Biggers: __keyring_link(): Call key_put() in the rollback of
  rhashtable_replace_fast().
- Eric Biggers: Retract from using __free(kfree) in keyring_get_index().
- Eric Biggers: Reuse keyring_link_key() in keyring_obj_cmpfn().
- Eric Biggers: Document why keyring_index_free() uses queue_rcu_work().
- Eric Biggers: Fix the commit message for "KEYS: Replace assoc_array with
  rhashtable".

v3:
- Since David is away for the next week I decided to address the
  low hanging fruit that I reported myself.
- Unified and sanitized function and variable naming and removed
  unnecessary asymmetry e.g., by renaming keyring_remove_all_links
  as keyring_index_free, 'links' as 'index' and '_edit' as 'edit'.
- Flattened the implementation by refactoring out some useless
  wrappers and other constructs.
- Addressed continuation after triggered WARN_ON() on at the three
  sites that I've described in my email response to the previous
  patch set version.
- Reworked keyring_read() so that it triggers the scheduler between
  the iterations.
- Dropped "Assisted-by: LLM" tag because checkpatch.pl told me so.

v2:
- Tried to address all the issues pointed out by David and Eric. Tell me
  if something was ignored, as that would be an unintentional mishap.
- Updated and trimmed the source code comments.
- For assoc_array_edit I decided to go with two-element pointer array,
  which shifts a bit what David suggested.
- Dropped is_keyring flag. It was so obvious call so I mention it here
  just in case because too obvious maxes out my self-doubt ;-)
- Used cleanup.h primitives where I possibly could especially in order
  to make fallible initializations more bug-resistant.
- The already-ack'd bug fixes are included but will be dropped as soon
  as I've sent them over to Linus.

VERSIONS
========

- v12:
  https://lore.kernel.org/keyrings/20261114164139.429814-1-jarkko@kernel.org/
- v11:
  https://lore.kernel.org/keyrings/20261114161211.376859-1-jarkko@kernel.org/
- v10:
  https://lore.kernel.org/keyrings/20261113161836.3587552-1-jarkko@kernel.org/
- v9:
  https://lore.kernel.org/keyrings/20261110053323.2936729-1-jarkko@kernel.org/k
- v8:
  https://lore.kernel.org/keyrings/20261110044043.2608600-1-jarkko@kernel.org/
- v7:
  https://lore.kernel.org/keyrings/20261110033738.2495880-1-jarkko@kernel.org/
- v6:
  https://lore.kernel.org/keyrings/20261107195605.3929659-1-jarkko@kernel.org/
- v5:
  https://lore.kernel.org/keyrings/20261105031401.956609-1-jarkko@kernel.org/
- v4:
  https://lore.kernel.org/keyrings/20261029232437.2581640-1-jarkko@kernel.org/
- v3:
  https://lore.kernel.org/keyrings/20261025001105.1824178-1-jarkko@kernel.org/
- v2:
  https://lore.kernel.org/keyrings/20261023120953.1206778-1-jarkko@kernel.org/
- v1:
  https://lore.kernel.org/keyrings/20261016215326.4110064-1-jarkko@kernel.org/

Cc: bpf@vger.kernel.org
Cc: dm-devel@lists.linux.dev
Cc: fsverity@lists.linux.dev
Cc: keyrings@vger.kernel.org
Cc: linux-doc@vger.kernel.org
Cc: linux-kernel@vger.kernel.org
Cc: linux-kselftest@vger.kernel.org
Cc: linux-security-module@vger.kernel.org
Cc: Alasdair Kergon <agk@redhat.com>
Cc: Alexander Gordeev <agordeev@linux.ibm.com>
Cc: Alexei Starovoitov <ast@kernel.org>
Cc: Alex Shi <alexs@kernel.org>
Cc: Anastasia Eskova <anastasia.eskova@ibm.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Andrii Nakryiko <andrii@kernel.org>
Cc: Benjamin Marzinski <bmarzins@redhat.com>
Cc: Christian Borntraeger <borntraeger@linux.ibm.com>
Cc: Daniel Borkmann <daniel@iogearbox.net>
Cc: David Howells <dhowells@redhat.com>
Cc: Dongliang Mu <dzm91@hust.edu.cn>
Cc: Eduard Zingerman <eddyz87@gmail.com>
Cc: Emil Tsalapatis <emil@etsalapatis.com>
Cc: Eric Biggers <ebiggers@kernel.org>
Cc: Ignat Korchagin <ignat@linux.win>
Cc: Heiko Carstens <hca@linux.ibm.com>
Cc: Ihor Solodrai <ihor.solodrai@linux.dev>
Cc: James Bottomley <James.Bottomley@HansenPartnership.com>
Cc: James Morris <jmorris@namei.org>
Cc: Jarkko Sakkinen <jarkko@kernel.org>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: Jonathan Corbet <corbet@lwn.net>
Cc: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Martin KaFai Lau <martin.lau@linux.dev>
Cc: Mike Snitzer <snitzer@kernel.org>
Cc: Mikulas Patocka <mpatocka@redhat.com>
Cc: Mimi Zohar <zohar@linux.ibm.com>
Cc: Paul Moore <paul@paul-moore.com>
Cc: Peter Oberparleiter <oberpar@linux.ibm.com>
Cc: Randy Dunlap <rdunlap@infradead.org>
Cc: Roberto Sassu <roberto.sassu@huawei.com>
Cc: "Serge E. Hallyn" <serge@hallyn.com>
Cc: Shuah Khan <skhan@linuxfoundation.org>
Cc: Song Liu <song@kernel.org>
Cc: Sven Schnelle <svens@linux.ibm.com>
Cc: "Theodore Y. Ts'o" <tytso@mit.edu>
Cc: Vasily Gorbik <gor@linux.ibm.com>
Cc: Yanteng Si <si.yanteng@linux.dev>
Cc: Yonghong Song <yonghong.song@linux.dev>

Jarkko Sakkinen (7):
  s390/cert_store: Pin the user session keyring
  s390/cert_store: Return an owned reference from find_cs_keyring()
  s390/cert_store: Skip keys that disappeared during invalidation
  s390/cert_store: Read-lock keyring semaphore in
    invalidate_keyring_keys()
  KEYS: Introduce keyring_is_empty()
  KEYS: Replace assoc_array with rhashtable
  lib: Remove assoc_array

 Documentation/core-api/assoc_array.rst        |  564 ------
 Documentation/core-api/index.rst              |    1 -
 .../zh_CN/core-api/assoc_array.rst            |  473 -----
 .../translations/zh_CN/core-api/index.rst     |    1 -
 arch/s390/kernel/cert_store.c                 |   60 +-
 drivers/md/dm-verity-verify-sig.c             |    2 +-
 fs/verity/signature.c                         |    2 +-
 include/keys/keyring-type.h                   |    1 -
 include/linux/assoc_array.h                   |   88 -
 include/linux/assoc_array_priv.h              |  178 --
 include/linux/key-type.h                      |    1 -
 include/linux/key.h                           |   29 +-
 kernel/bpf/keys.c                             |    2 +-
 lib/Kconfig                                   |   14 -
 lib/Makefile                                  |    1 -
 lib/assoc_array.c                             | 1724 -----------------
 security/keys/Kconfig                         |    1 -
 security/keys/internal.h                      |   14 +-
 security/keys/key.c                           |   22 +-
 security/keys/keyring.c                       | 1016 +++++-----
 security/keys/request_key.c                   |    8 +-
 .../dm-verity/test-dm-verity-keyring.sh       |    2 +-
 22 files changed, 541 insertions(+), 3663 deletions(-)
 delete mode 100644 Documentation/core-api/assoc_array.rst
 delete mode 100644 Documentation/translations/zh_CN/core-api/assoc_array.rst
 delete mode 100644 include/linux/assoc_array.h
 delete mode 100644 include/linux/assoc_array_priv.h
 delete mode 100644 lib/assoc_array.c

--
2.47.3