[RFC] Highly efficient reader-writer lock (EPRW) for mostly-read applications

[Stephen Hemminger]

On Tue, 8 Sep 2026 03:55:12 +0000
Mukul Katiyar <mukul at versa-networks.com> wrote:

> Hi all,
> 
> Sharing a userspace reader-writer lock that has been running in production in a DPDK-based network function for several years and wanted to check if there would be interest in contributing it to DPDK as rte_eprwlock.
> 
> The Enhanced Passive Reader-Writer (EPRW) lock eliminates atomic operations on the reader fast path, giving near-flat per-reader performance as core count grows. It is compatible with poll-mode lcore discipline — no heartbeat or periodic refresh required from registered threads.
> 
> Details, correctness proof, memory ordering analysis (x86-TSO and ARM), and performance evaluation against rte_rwlock and pthread_rwlock_t are in a preprint at:
> https://zenodo.org/records/22636501
> 
> Would this be a useful addition to DPDK?
> 
> Regards,
> Mukul Katiyar
> Versa Networks
> 

As an exercise, also point Fable AI to do analysis of the paper versus current DPDK code.
Surprisingly AI is relatively good at understanding locking; probably because it has been
trained on a huge data set of academic papers.

Short version: this is a write-up of Versa fixing a bug in their own
userspace port of Liu's PRW lock. It is not a critique of rte_rwlock
and does not cite any DPDK primitive (DPDK is cited as "Intel
Corporation 2024", which tells you how closely they looked). "Outdated
DPDK" is too generous; there is no DPDK survey at all. The DPDK
relevance is only the deployment context.

Analysis:

1. What the algorithm actually is. Once the writer scan checks `RP[i]
== Present && TV[i] != GV`, the version counter only distinguishes
"spinning at boundary" from "inside CS". A three-state per-thread flag
(ABSENT/WAITING/ACTIVE) does the same job with no GV, no unlock
broadcast, no rollover. The only thing TV buys is a WAITING to ACTIVE
transition without a store+fence, because the writer's GV++ invalidates
the match for it. That is the contended path, so it does not affect
throughput. Strip that and you have a per-thread-flag rwlock: Hsieh and
Weihl 1992, Linux 2.4 brlock, Dice/Shavit read indicators,
percpu_rw_semaphore slow path. The "heartbeat" was self-inflicted: they
dropped the kernel IPI and did not add an offline state. `RP = Absent`
is `rte_rcu_qsbr_thread_offline()`.

2. The premise contradicts DPDK practice. Section 3 says per-lcore
periodic reporting is incompatible with poll-mode discipline.
`rte_rcu_qsbr_quiescent()` per loop iteration is exactly how lib/rcu is
used, with online/offline for idle threads. Section 10 admits the QSBR
analogy but not that DPDK ships it. liburcu (Desnoyers et al., TPDS
2012) is the canonical treatment of replacing kernel IPI/quiescence in
userspace and is not cited either. RCU also gives readers zero wait and
real reclamation; EPRW writers still spin on every in-CS reader.

3. No comparison, no numbers. Missing: rte_rwlock (4 bytes, WAIT bit so
writers cannot starve), rte_pflock (bounded wait both sides),
rte_seqlock/seqcount, rte_rcu_qsbr, rte_mcslock, rte_ticketlock.
Microbenchmarks "left for future work". EPRW has no fairness: a reader
spinning on W must catch a window between one writer's `W = Absent` and
the next writer's CAS, and back-to-back writers skip it forever since
its TV matches. That is the case pflock was added for.

4. Concrete defects:
   - Lemma 8.1 is wrong. `Try_Write_Lock` increments GV and on failure releases W without the broadcast. A caller retrying try_wlock against a reader stuck in its CS (preempted control thread, slow path) gets 65536 failures, GV wraps, `TV[i] == GV`, false boundary match, exclusion violated. The 16-bit variant is unsafe as published. Trivial fix, but the proof did not cover its own try path.
   - ARMv8 `Read_Lock`: the exit load of W has no acquire. The DMB after the RP store does not order that load against later CS loads, so a reader can see pre-write data. Same in `Try_Read_Lock`. Section 6 walks every barrier site and misses this one. Fine on TSO.
   - Plain-C data races: readers load GV while the writer does a non-atomic increment; TV[i] is stored by thread i and by the broadcasting writer. Works on hardware with aligned words, UB in C11. Any DPDK version would need rte_stdatomic relaxed ops anyway.
   - Compact mode packs 3-byte slots: 32 threads in 3 cache lines, so every read lock/unlock is a store to a shared line. That reintroduces the coherence traffic PRW exists to avoid. The 64-byte alignment in the original is the whole point. No measurement.
   - Write_Unlock broadcast invalidates N reader-owned lines per write on top of the scan. Fine for read-mostly, but it is why per-lcore-slot locks do not fit "hundreds of locks", which is their own compact-mode motivation.
   - `TV[tid] = GV` in the Write_Lock contention loop is dead: a plain contender has RP Absent, so the winner's scan skips it regardless. Only Upgrade needs it.
   - "Non-atomic upgrade" (return 1) is a read unlock followed by a write lock; data can change in between. The name invites misuse.
   - Reader fast path uses MFENCE. rte_smp_mb() uses `lock addl` on x86 for a reason; xchg for the RP store folds store and barrier.