rcu_txn_load() and rcu_txn_record_chain() look the slot up among the records of the transaction with a linear scan, so a transaction of n records costs O(n) per access and O(n^2) to build. Most lookups miss.
Answer the miss from a Bloom filter: a clear bit means the slot is not recorded, and the scan is skipped. A hit still goes to the scan, so the filter never changes an answer. The filter is armed by the first lookup that faces RCU_TXN_BLOOM_MIN records, and is not even zeroed before that. Most transactions hold a record or two, for which the scan is cheaper than hashing. The filter takes 128 bytes, which the handle does not carry, as it lives on the stack: the filter lives in the descriptor, past the records. A descriptor of RCU_TXN_BLOOM_MIN records or more has room for it among the slots of its records array, which the array's __counted_by() covers, and a resize carries an armed filter over to the new descriptor. Assisted-by: LLM Signed-off-by: Mathieu Desnoyers <[email protected]> --- include/linux/rcu_txn.h | 89 ++++++++++++++++++-- include/linux/rcu_txn_bloom.h | 110 +++++++++++++++++++++++++ lib/rcu_txn.c | 36 ++++++++- lib/tests/rcu_txn_kunit.c | 147 ++++++++++++++++++++++++++++++++++ 4 files changed, 373 insertions(+), 9 deletions(-) create mode 100644 include/linux/rcu_txn_bloom.h diff --git a/include/linux/rcu_txn.h b/include/linux/rcu_txn.h index 48e87ea2d90b..ee152100ab95 100644 --- a/include/linux/rcu_txn.h +++ b/include/linux/rcu_txn.h @@ -102,6 +102,7 @@ #include <linux/errno.h> #include <linux/gfp_types.h> #include <linux/rcupdate.h> +#include <linux/rcu_txn_bloom.h> /* read-your-own-writes filter */ #include <linux/stddef.h> #include <linux/string.h> #include <linux/types.h> @@ -197,7 +198,13 @@ struct rcu_txn_desc { struct rcu_txn_group group; /* read by installed proxies */ struct rcu_head rcu_head; /* deferred-free handle */ unsigned int cap; /* records it can hold */ - struct rcu_txn_record records[] __counted_by(cap); + /* + * Record-sized slots of the allocation: the @cap records and, in a + * descriptor of RCU_TXN_BLOOM_MIN records or more, past them, the + * read-your-own-writes filter (__rcu_txn_bloom()). + */ + unsigned int slots; + struct rcu_txn_record records[] __counted_by(slots); }; /* @@ -218,6 +225,7 @@ struct rcu_txn { gfp_t gfp; /* for the descriptor */ enum rcu_txn_state state; bool disjoint; /* declared slot-disjoint */ + bool bloom_live; /* the descriptor's filter is armed */ }; /* @@ -463,9 +471,10 @@ static inline void __rcu_txn_done(struct rcu_txn *t) /* * Scan this transaction's records for @slot, or NULL. Linear, so O(nr) per - * call and O(nr^2) to build a write set. The returned pointer is invalidated - * by the next record() (a grow may move the records), so use it before - * recording again. + * call and O(nr^2) to build a write set -- __rcu_txn_find_ryw() below is what + * keeps that off the hot path. The returned pointer is invalidated by the + * next record() (a grow may move the records), so use it before recording + * again. */ static inline struct rcu_txn_record *__rcu_txn_scan(const struct rcu_txn *t, void __rcu **slot) @@ -478,6 +487,69 @@ static inline struct rcu_txn_record *__rcu_txn_scan(const struct rcu_txn *t, return NULL; } +/* + * RCU_TXN_BLOOM_MIN: the record count from which the read-your-own-writes + * filter (<linux/rcu_txn_bloom.h>) is used. Below it the filter is never + * armed, nor even zeroed. + * + * rcu_txn_load() is only called on a slot about to be recorded, so loads + * track records one for one, and most transactions are tiny: one edge for an + * hlist operation, two for a list operation. Scanning that many records is + * cheaper than hashing. + * + * The filter is built and armed by the first __rcu_txn_find_ryw() that faces + * at least this many records, then kept current by every record(). Arming on + * the record that crosses the threshold instead would make a transaction of + * exactly RCU_TXN_BLOOM_MIN records build a filter it never tests. + * + * The filter lives in the descriptor, past the records, so that the handle on + * the stack does not carry it. A descriptor of this many records or more has + * room for it (rcu_txn_desc_alloc()). + */ +#define RCU_TXN_BLOOM_MIN 8 + +static_assert(RCU_TXN_BLOOM_MIN > 1); + +/* The filter of the handle's descriptor: see RCU_TXN_BLOOM_MIN. */ +static inline u64 *__rcu_txn_bloom(const struct rcu_txn *t) +{ + return (u64 *)&t->desc->records[t->desc->cap]; +} + +/* + * Build the filter from the records so far and arm it. See + * RCU_TXN_BLOOM_MIN. + */ +static inline void __rcu_txn_bloom_arm(struct rcu_txn *t) +{ + u64 *bloom = __rcu_txn_bloom(t); + unsigned int i; + + memset(bloom, 0, RCU_TXN_BLOOM_SIZE); + for (i = 0; i < t->nr; i++) + rcu_txn_bloom_set(bloom, t->records[i].slot); + t->bloom_live = true; +} + +/* + * __rcu_txn_scan() behind the filter: a clear bit means the slot is not + * recorded, and the scan is skipped. All k bits set leaves the answer to the + * scan, which rules out a false positive. The filter never changes the answer. + */ +static inline struct rcu_txn_record *__rcu_txn_find_ryw(struct rcu_txn *t, + void __rcu **slot) +{ + if (unlikely(!t->bloom_live)) { + /* Armed on first use: see RCU_TXN_BLOOM_MIN. */ + if (t->nr < RCU_TXN_BLOOM_MIN) + return __rcu_txn_scan(t, slot); + __rcu_txn_bloom_arm(t); + } + if (!rcu_txn_bloom_test(__rcu_txn_bloom(t), slot)) + return NULL; /* definitely absent */ + return __rcu_txn_scan(t, slot); +} + /* * Grow a full handle: double its capacity, or give an unreserved handle its * first RCU_TXN_CAP records. Returns false if it cannot allocate. @@ -531,6 +603,8 @@ static inline bool rcu_txn_record(struct rcu_txn *t, void __rcu **slot, return false; /* OOM, now sticky */ r = &t->records[t->nr++]; __rcu_txn_record_set(r, slot, old_ptr, new_ptr, tag); + if (unlikely(t->bloom_live)) /* armed: keep it current */ + rcu_txn_bloom_set(__rcu_txn_bloom(t), slot); return true; } @@ -579,7 +653,8 @@ static inline bool rcu_txn_record(struct rcu_txn *t, void __rcu **slot, * a list, may write the same slot. * * This skips the lookup among the records so far on every load and record, a - * scan: a small saving from the second record on. + * scan or, past RCU_TXN_BLOOM_MIN records, a Bloom filter test: a small saving + * from the second record on. * * Recording a slot twice on such a handle breaks the rule of rcu_txn_record(), * with the consequence stated there. @@ -619,7 +694,7 @@ static inline void *rcu_txn_load(struct rcu_txn *t, void __rcu **slot, /* A consumed handle has no record left: it reads committed values. */ WARN_ON_ONCE(t->state == RCU_TXN_DONE); if (!t->disjoint) { - r = __rcu_txn_scan(t, slot); + r = __rcu_txn_find_ryw(t, slot); if (r) return r->ptr[1]; /* our own pending write */ } @@ -637,7 +712,7 @@ static inline bool __rcu_txn_chain(struct rcu_txn *t, void __rcu **slot, { struct rcu_txn_record *r; - r = __rcu_txn_scan(t, slot); + r = __rcu_txn_find_ryw(t, slot); if (!r) return rcu_txn_record(t, slot, old_ptr, new_ptr, tag); r->ptr[1] = new_ptr; /* committed old preserved */ diff --git a/include/linux/rcu_txn_bloom.h b/include/linux/rcu_txn_bloom.h new file mode 100644 index 000000000000..c2b3b0e6ff01 --- /dev/null +++ b/include/linux/rcu_txn_bloom.h @@ -0,0 +1,110 @@ +/* SPDX-License-Identifier: LGPL-2.1-or-later */ +/* + * Read-your-own-writes Bloom filter of the RCU pseudo-transactions + * + * Copyright (C) 2026 Mathieu Desnoyers <[email protected]> + */ +#ifndef _LINUX_RCU_TXN_BLOOM_H +#define _LINUX_RCU_TXN_BLOOM_H + +/* + * An RCU pseudo-transaction with read-your-own-writes must decide, per + * access, whether a slot is already in this transaction's write set. + * The authoritative test is a linear scan of the records, so a write + * set of n slots costs O(n) per access and O(n^2) to build -- and the + * scan is pure overhead on the dominant case, the lookup miss. + * + * This Bloom filter is an optimisation to answer the miss in O(1) + * without false negatives: a clear bit means the slot is definitely + * absent, so the scan is skipped outright. All k bits set means + * present or a false positive, so the scan runs. + * + * Correctness never depends on the filter's presence, width or k. A false + * positive only costs time: the scan of the records that the filter fails to + * skip, which then finds the slot absent. Correctness does depend on the + * absence of false negatives, which is an obligation on the engine: the filter + * must be set for every slot recorded while it is live (arming rebuilds it + * from all records, so this holds from the moment it goes live). + * + * This is the mechanism only. The state belongs to the caller, which + * provides RCU_TXN_BLOOM_SIZE bytes and owns zeroing them; where they live and + * when the filter is armed is the engine's policy: see RCU_TXN_BLOOM_MIN in + * <linux/rcu_txn.h>. These helpers are pure functions over the array. + */ + +#include <linux/compiler_types.h> +#include <linux/types.h> + +/* + * RCU_TXN_BLOOM_WORDS sets the filter width (64 bits each; 16 = 1024 bits). + * With k bits over m = 64 * WORDS bits and n recorded slots the false-positive + * rate is ~(1 - e^{-kn/m})^k, which for a sparse filter is (kn/m)^k: doubling + * the width divides it by ~2^k. + * + * Both width and k only ever trade filter cost against the false-positive + * rate: correctness never depends on either. + */ +#define RCU_TXN_BLOOM_WORDS 16 + +/* + * RCU_TXN_BLOOM_K sets the number of hash bits a slot maps to. Raising k by + * one multiplies the false-positive rate by the fill factor kn/m: a win only + * while the filter is sparse. + */ +#define RCU_TXN_BLOOM_K 3 + +#define RCU_TXN_BLOOM_BITS (64ULL * RCU_TXN_BLOOM_WORDS) +#define RCU_TXN_BLOOM_SIZE (sizeof(u64) * RCU_TXN_BLOOM_WORDS) + +/* + * Two independent hashes of the slot, for Kirsch-Mitzenmacher double hashing: + * one SplitMix64 avalanche (two multiplies), its 64 bits split into two 32-bit + * lanes. A single multiply would leave the k positions correlated, slot + * addresses being aligned and clustered. h2 is forced odd so that h1 + i*h2 + * visits k distinct bits. + */ +static inline void rcu_txn_bloom_h1h2(void __rcu **slot, u64 *h1, u64 *h2) +{ + /* + * Shift by the alignment every slot has, 4 bytes on 32-bit: >> 3 would + * map adjacent slots there to the same k positions. On 64-bit the one + * zero bit left is mixed away by the avalanche. + */ + u64 x = (u64)(unsigned long)slot >> 2; + + x ^= x >> 30; x *= 0xbf58476d1ce4e5b9ULL; + x ^= x >> 27; x *= 0x94d049bb133111ebULL; + x ^= x >> 31; + *h1 = x & 0xffffffffULL; /* low lane */ + *h2 = (x >> 32) | 1; /* high lane, odd stride */ +} + +static inline bool rcu_txn_bloom_test(const u64 *bloom, void __rcu **slot) +{ + u64 h1, h2; + unsigned int i; + + rcu_txn_bloom_h1h2(slot, &h1, &h2); + for (i = 0; i < RCU_TXN_BLOOM_K; i++) { + u64 idx = (h1 + (u64)i * h2) % RCU_TXN_BLOOM_BITS; + + if (!(bloom[idx >> 6] & ((u64)1 << (idx & 63)))) + return false; /* a clear bit: definitely absent */ + } + return true; /* all k bits set: present (or a false positive) */ +} + +static inline void rcu_txn_bloom_set(u64 *bloom, void __rcu **slot) +{ + u64 h1, h2; + unsigned int i; + + rcu_txn_bloom_h1h2(slot, &h1, &h2); + for (i = 0; i < RCU_TXN_BLOOM_K; i++) { + u64 idx = (h1 + (u64)i * h2) % RCU_TXN_BLOOM_BITS; + + bloom[idx >> 6] |= (u64)1 << (idx & 63); + } +} + +#endif /* _LINUX_RCU_TXN_BLOOM_H */ diff --git a/lib/rcu_txn.c b/lib/rcu_txn.c index 232ad715468a..b040af0a8cdb 100644 --- a/lib/rcu_txn.c +++ b/lib/rcu_txn.c @@ -9,6 +9,8 @@ */ #include <linux/export.h> +#include <linux/math.h> +#include <linux/minmax.h> #include <linux/overflow.h> #include <linux/rcu_txn.h> #include <linux/rcupdate.h> @@ -17,6 +19,24 @@ #include "rcu_txn_internal.h" +/* Record-sized slots that the filter takes, past the records. */ +#define RCU_TXN_BLOOM_SLOTS \ + DIV_ROUND_UP(RCU_TXN_BLOOM_SIZE, sizeof(struct rcu_txn_record)) + +/* + * The records that a descriptor of @slots record-sized slots holds. Once they + * are RCU_TXN_BLOOM_MIN or more, the filter takes the slots past them: a + * descriptor with slots for that many records but not for the filter as well + * holds RCU_TXN_BLOOM_MIN - 1 records. + */ +static unsigned int rcu_txn_desc_cap(unsigned int slots) +{ + if (slots < RCU_TXN_BLOOM_MIN) + return slots; + return max_t(unsigned int, slots - RCU_TXN_BLOOM_SLOTS, + RCU_TXN_BLOOM_MIN - 1); +} + /* * Allocate a transaction descriptor for at least @cap records, with its flip * group initialized. Its capacity is what the allocation holds, which may be @@ -32,12 +52,17 @@ static struct rcu_txn_desc *rcu_txn_desc_alloc(unsigned int cap, gfp_t gfp) struct rcu_txn_desc *desc; size_t size; - size = kmalloc_size_roundup(struct_size(desc, records, cap)); + size = struct_size(desc, records, cap); + if (cap >= RCU_TXN_BLOOM_MIN) + size = size_add(size, RCU_TXN_BLOOM_SLOTS * + sizeof(struct rcu_txn_record)); + size = kmalloc_size_roundup(size); desc = kmalloc(size, gfp); if (!desc) return NULL; __rcu_txn_group_init(&desc->group); - desc->cap = (size - sizeof(*desc)) / sizeof(desc->records[0]); + desc->slots = (size - sizeof(*desc)) / sizeof(desc->records[0]); + desc->cap = rcu_txn_desc_cap(desc->slots); return desc; } @@ -66,6 +91,13 @@ bool __rcu_txn_resize(struct rcu_txn *t, unsigned int cap) if (t->nr) /* @records is NULL until first allocated */ memcpy(desc->records, t->records, (size_t)t->nr * sizeof(*desc->records)); + /* + * An armed filter moves too: both descriptors hold RCU_TXN_BLOOM_MIN + * records or more, so both have room for it. + */ + if (t->bloom_live) + memcpy(&desc->records[desc->cap], __rcu_txn_bloom(t), + RCU_TXN_BLOOM_SIZE); kfree(t->desc); /* NULL if it had none */ t->desc = desc; t->records = desc->records; diff --git a/lib/tests/rcu_txn_kunit.c b/lib/tests/rcu_txn_kunit.c index e5323e21157b..3111fc537ff3 100644 --- a/lib/tests/rcu_txn_kunit.c +++ b/lib/tests/rcu_txn_kunit.c @@ -436,6 +436,147 @@ static void rcu_txn_test_consumed_handle(struct kunit *test) KUNIT_EXPECT_PTR_EQ(test, rcu_access_pointer(slot), T(1)); } +static void __rcu *bloom_slots[4096]; + +/* An empty filter answers absent for every slot. */ +static void rcu_txn_test_bloom_empty(struct kunit *test) +{ + u64 bloom[RCU_TXN_BLOOM_WORDS] = {}; + unsigned int i, present = 0; + + for (i = 0; i < ARRAY_SIZE(bloom_slots); i++) + present += rcu_txn_bloom_test(bloom, &bloom_slots[i]); + KUNIT_EXPECT_EQ(test, present, 0); +} + +/* + * No false negatives: every slot ever set still reads present, whatever is set + * after it. This is the property the engine's correctness rests on. + */ +static void rcu_txn_test_bloom_no_false_negative(struct kunit *test) +{ + u64 bloom[RCU_TXN_BLOOM_WORDS] = {}; + unsigned int i, j, missing = 0; + + for (i = 0; i < ARRAY_SIZE(bloom_slots); i++) { + rcu_txn_bloom_set(bloom, &bloom_slots[i]); + /* Testing all i + 1 each round is O(n^2): sample. */ + for (j = 0; j <= i; j += i / 16 + 1) + missing += !rcu_txn_bloom_test(bloom, &bloom_slots[j]); + } + for (i = 0; i < ARRAY_SIZE(bloom_slots); i++) + missing += !rcu_txn_bloom_test(bloom, &bloom_slots[i]); + KUNIT_EXPECT_EQ(test, missing, 0); +} + +/* + * The filter still discriminates past its design fill: with an eighth of the + * slots set, not every absent slot reads present. The bound only has to catch + * a degenerate hash. + */ +static void rcu_txn_test_bloom_discriminates(struct kunit *test) +{ + const unsigned int nr = ARRAY_SIZE(bloom_slots); + u64 bloom[RCU_TXN_BLOOM_WORDS] = {}; + unsigned int i, false_positives = 0; + + for (i = 0; i < nr / 8; i++) + rcu_txn_bloom_set(bloom, &bloom_slots[i]); + for (i = nr / 8; i < nr; i++) + false_positives += rcu_txn_bloom_test(bloom, &bloom_slots[i]); + KUNIT_EXPECT_LT(test, false_positives, nr - nr / 8); +} + +/* + * The filter does not depend on insertion order. Arming rebuilds it from the + * records so far, so a rebuilt filter must match one grown incrementally. + */ +static void rcu_txn_test_bloom_rebuild(struct kunit *test) +{ + u64 bloom[RCU_TXN_BLOOM_WORDS] = {}, rebuilt[RCU_TXN_BLOOM_WORDS] = {}; + unsigned int i; + + for (i = 0; i < 64; i++) + rcu_txn_bloom_set(bloom, &bloom_slots[i]); + for (i = 64; i-- > 0; ) + rcu_txn_bloom_set(rebuilt, &bloom_slots[i]); + KUNIT_EXPECT_MEMEQ(test, bloom, rebuilt, sizeof(bloom)); +} + +/* + * The engine arms the filter at the first lookup that faces RCU_TXN_BLOOM_MIN + * records, and keeps it current from then on: slots recorded before and after + * the arming are both found. + */ +static void rcu_txn_test_bloom_arming(struct kunit *test) +{ + enum { NR = 2 * RCU_TXN_BLOOM_MIN }; + void __rcu *slots[NR]; + struct rcu_txn txn; + unsigned int i; + + for (i = 0; i < NR; i++) + RCU_INIT_POINTER(slots[i], T(i)); + rcu_txn_init(&txn, GFP_KERNEL); + for (i = 0; i < NR; i++) { + void *v = rcu_txn_load(&txn, &slots[i], TAG); + + /* The lookup that faces RCU_TXN_BLOOM_MIN records arms it. */ + KUNIT_EXPECT_EQ(test, txn.bloom_live, i >= RCU_TXN_BLOOM_MIN); + rcu_txn_record_chain(&txn, &slots[i], v, T(20 + i), TAG); + } + for (i = 0; i < NR; i++) { + void *v = rcu_txn_load(&txn, &slots[i], TAG); + + KUNIT_EXPECT_PTR_EQ(test, v, T(20 + i)); + rcu_txn_record_chain(&txn, &slots[i], v, T(100 + i), TAG); + } + KUNIT_EXPECT_EQ(test, txn.nr, NR); /* fused */ + KUNIT_EXPECT_EQ(test, rcu_txn_commit(&txn), 0); + KUNIT_EXPECT_TRUE(test, all_settled(slots, NR)); + + /* A handle declared disjoint never looks up, and never arms. */ + rcu_txn_init(&txn, GFP_KERNEL); + rcu_txn_declare_disjoint(&txn); + for (i = 0; i < NR; i++) { + void *v = rcu_txn_load(&txn, &slots[i], TAG); + + rcu_txn_record_chain(&txn, &slots[i], v, T(i), TAG); + } + KUNIT_EXPECT_FALSE(test, txn.bloom_live); + rcu_txn_cancel(&txn); +} + +/* + * An armed filter moves with the records when the transaction outgrows its + * descriptor: every slot recorded before and after the move is still found. + */ +static void rcu_txn_test_bloom_grow(struct kunit *test) +{ + enum { NR = 8 * RCU_TXN_BLOOM_MIN }; + void __rcu *slots[NR]; + unsigned int i, cap = 0; + struct rcu_txn txn; + + for (i = 0; i < NR; i++) + RCU_INIT_POINTER(slots[i], T(i)); + rcu_txn_init(&txn, GFP_KERNEL); + for (i = 0; i < NR; i++) { + void *v = rcu_txn_load(&txn, &slots[i], TAG); + + if (txn.bloom_live && !cap) + cap = txn.cap; /* armed in this descriptor */ + rcu_txn_record_chain(&txn, &slots[i], v, T(100 + i), TAG); + } + KUNIT_ASSERT_NE(test, cap, 0); + KUNIT_EXPECT_GT(test, txn.cap, cap); /* grown since */ + for (i = 0; i < NR; i++) + KUNIT_EXPECT_PTR_EQ(test, rcu_txn_load(&txn, &slots[i], TAG), + T(100 + i)); + KUNIT_EXPECT_EQ(test, rcu_txn_commit(&txn), 0); + KUNIT_EXPECT_TRUE(test, all_settled(slots, NR)); +} + static struct kunit_case rcu_txn_test_cases[] = { KUNIT_CASE(rcu_txn_test_single_record), KUNIT_CASE(rcu_txn_test_multi_record), @@ -449,6 +590,12 @@ static struct kunit_case rcu_txn_test_cases[] = { KUNIT_CASE(rcu_txn_test_ryw_chain), KUNIT_CASE(rcu_txn_test_disjoint), KUNIT_CASE(rcu_txn_test_consumed_handle), + KUNIT_CASE(rcu_txn_test_bloom_empty), + KUNIT_CASE(rcu_txn_test_bloom_no_false_negative), + KUNIT_CASE(rcu_txn_test_bloom_discriminates), + KUNIT_CASE(rcu_txn_test_bloom_rebuild), + KUNIT_CASE(rcu_txn_test_bloom_arming), + KUNIT_CASE(rcu_txn_test_bloom_grow), {} }; -- 2.47.3
