Re: [RFC PATCH 00/12] RCU pseudo-transactions

[Mathieu Desnoyers]

On 2026-10-18 20:55, Joel Fernandes wrote:
> On Fri, Oct 16, 2026 at 09:33:07AM -0400, Mathieu Desnoyers wrote:
> > Hi,
> >
> > Earlier this year, I came up with a neat trick which reduces the mental
> > challenge of adapting data structures to RCU.  It turns out that it also
> > widens the applicability of RCU to additional classes of data
> > structures.
> >
> > This is done by a low-overhead abstraction which I'm naming
> > "RCU Pseudo-Transactions" [1, 2]. I name this "pseudo" because unlike
> > classic transactions, the writers exclude each other, readers get no
> > snapshot, and there is no abort.
>
> Cool idea! Instead of tagging the pointer, perhaps alternatively the proxy
> object can be allocated in specific dedicated parts of kernel address space?
> Might be slower to test against though. But perhaps will make it usable by any
> users who use lower bits for other purposes.

A range check is possible, but it costs more on the read-side fast
path than a single-bit test, and with variable bounds it adds memory
loads. On x86-64, roughly:

1) Low-bit tag:              ptr & 0x1

     test  $0x1, %al
     jnz   slow

2) Range, constant bounds:   ptr >= BEGIN && ptr < END

     sub   $BEGIN, %rax
     cmp   $(END - BEGIN), %rax
     jb    slow

3) Range, variable bounds:   ptr >= begin && ptr < end

     cmp   begin(%rip), %rax
     jb    fast
     cmp   end(%rip), %rax
     jb    slow

Users that already need a low bit for other purposes can align their
objects on 16 bytes and use any of the other low bits as the tag,
still with a single test. A multi-bit pattern within the low 4 bits
can also be used as the tag, at the cost of and + cmp + jne on the
fast path, if more flexibility is needed.

One alternative I've considered (suggested by Paul McKenney) was to
use a trap (page fault) to handle the proxy case. The idea would be to
make sure the proxy address range triggers a read fault, and handle
the proxy resolution within a page fault handler.

This is a tradeoff: we'd skip the test-and-branch on the fast path,
but we would then have to make readers take page faults (orders of
magnitude slower) whenever they run concurrently with an ongoing
transaction. This would favor a workload with very infrequent updates
at a large cost for workloads where updates are not *so* infrequent.

Therefore I went for an approach which would keep read-side overhead in
the same order of magnitude whether or not a transaction is in progress,
hence the low-bit tag check.

> Btw, Pseudo-Transactions sounds long and weird, maybe "RCU proxy"? :-)

I initially called it "RCU flip-latch proxy", but ended up going for
a name that better describes what this really is: a transaction
in the filesystem (journaling) sense.

Note that I use "proxy" in my definitions and code to describe pointers
that are re-routed to the transaction descriptor records.

Thank you for the feedback!

Mathieu

--
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com