All of lore.kernel.org
 help / color / mirror / Atom feed
From: William Chuang <founder@logarcheon.com>
To: akpm@linux-foundation.org
Cc: dhowells@redhat.com, keyrings@vger.kernel.org,
	linux-kernel@vger.kernel.org,
	William Chuang <founder@logarcheon.com>
Subject: [PATCH 0/2] lib/assoc_array: fix root-shortcut split lookup regression, add KUnit tests
Date: Mon, 16 Nov 2026 05:41:17 +0000	[thread overview]
Message-ID: <20261116054112.39078-1-founder@logarcheon.com> (raw)

This series adds a KUnit test suite for lib/assoc_array.c and fixes a
lookup bug that suite exposes.

When a root shortcut is split at the first level-segment boundary, the
replacement node is installed one segment too shallow. Lookups then walk
the tree at the wrong depth, so a fraction of previously inserted keys can
no longer be found, even though they remain in the array.

Patch 1 adds the test suite; it passes on mainline. Patch 2 fixes the
split path in assoc_array_insert() and adds a regression test that fails
without the fix, keeping the series bisection-clean.

The fix was checked by exhaustive fan-out enumeration, randomized stress
runs, and KASAN; the patch 2 commit message describes the mechanism in
detail.

William Chuang (2):
  lib/assoc_array: add KUnit test suite
  lib/assoc_array: fix lookups after splitting a root shortcut

 lib/Kconfig.debug             |  17 +
 lib/assoc_array.c             |   3 +-
 lib/tests/Makefile            |   1 +
 lib/tests/assoc_array_kunit.c | 991 ++++++++++++++++++++++++++++++++++
 4 files changed, 1011 insertions(+), 1 deletion(-)
 create mode 100644 lib/tests/assoc_array_kunit.c

-- 
2.39.1



             reply	other threads:[~2026-11-16  5:41 UTC|newest]

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-16  5:41 William Chuang [this message]
2026-11-16  5:41 ` [PATCH 1/2] lib/assoc_array: add KUnit test suite William Chuang
2026-11-16  5:51   ` sashiko-bot
2026-11-16 20:28   ` kernel test robot
2026-11-16  5:41 ` [PATCH 2/2] lib/assoc_array: fix lookups after splitting a root shortcut William Chuang

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20261116054112.39078-1-founder@logarcheon.com \
    --to=founder@logarcheon.com \
    --cc=akpm@linux-foundation.org \
    --cc=dhowells@redhat.com \
    --cc=keyrings@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.