Hi Stephen, Thanks, I sincerely appreciate for your time and patience in reviewing this. The latest version already addresses many of the issues you/AI had pointed out. Here are some details of the design choices for this rwlock.
This lock targets problems that RCU cannot solve: datapath threads that must block readers while a writer performs in-place mutation. RCU's zero-reader-wait property requires copy-update semantics — that option is unavailable for many complex datastruct mutations, the object's identity is embedded in other structures, etc. For those cases a rwlock is the correct primitive, and the question is which rwlock minimizes reader cost. We agree RCU should be preferred wherever it applies. This is precisely for where it does not. Two concrete patterns, frequently seen in software data paths, drive the design: 1. Control-side config objects read per packet or per flow by multiple datapath threads, written rarely by a single control thread. 2. Objects that can be mutated from any datapath thread but are read far more often than written. Write events are on the order of 10^-7 of packet events — roughly once per 100 ms at 1 Mpps. Reader critical sections are 10–100 ns. Writers are at most a few 100 ns when used correctly. This submission is not a bug fix!. The contribution is elimination of the atomic RMW on the reader fast path. Every DPDK rwlock primitive — rte_rwlock, rte_pflock, rte_ticketlock — requires an atomic increment or CAS on every reader lock and unlock. prwlock readers use only a plain store, a memory fence, and a plain load on entry, and a release store on exit. No atomic RMW anywhere on the reader path, contended or not. That property is not available in any current DPDK primitive, which is why no DPDK primitive is cited as equivalent. A three-state flag (ABSENT/WAITING/ACTIVE) does encode similar state, but the version counter does more than distinguish states. When the writer increments GV to V, any reader that has updated TV[i] == V satisfies the scan even while still inside the critical section (CS) boundary spin — the writer skips it. To get the same behavior would result in a very similar version based implementation. The cited prior work (brlock, percpu_rw_semaphore, Dice/Shavit) either requires exclusive CPU pinning for all threads, kernel primitives unavailable in userspace, or does not eliminate the atomic RMW on the reader path. On RP = Absent` == `rte_rcu_qsbr_thread_offline()` / IPI replacement: These are not equivalent, and understanding why requires going back to what the "heartbeat" in the original paper actually was. The kernel PRW lock used IPIs (Inter-Processor Interrupts) to notify readers when a writer was spinning: hardware interrupts, delivered preemptively to the remote CPU, handled in tens of nanoseconds. That is the mechanism that kept writer wait bounded at CS granularity. When porting to userspace, IPIs are unavailable. The version counter is the only substitute that stays in the same latency class, in nanoseconds. QSBR's `thread_offline()` is not a replacement for this. It is a process-wide cooperative signal — "not accessing any RCU-protected object" — that requires the thread to reach a designated quiescent point on its own execution schedule. A DPDK datapath lcore is never offline in that sense; it processes packets continuously. Using `thread_offline()` / `thread_online()` to signal is semantically wrong (it signals across all locks, not one) and likely infeasible (millions of calls per second per lock instance, each more expensive than the release store it replaces). More fundamentally, QSBR is lock-unaware at fine granularity: a writer on lock-A must wait for all lcores to reach a quiescent state, including lcores that have never touched lock-A and are actively holding lock-B. QSBR epoch introduces cross-lock serialization where none logically exists. We had a QSBR-based implementation a decade ago. Here a 50 ns write produces a ~50 µs reader stall because every reader arriving after the writer must spin on writer_status for the entire grace period. rte_rcu_qsbr_quiescent() per loop iteration is correct usage of lib/rcu. A packet processing loop takes 10 - 100 µs; in practice, with security and stateful service processing, it can exceed that. That is the minimum writer wait, and it becomes the reader blocking time for every reader arriving while the writer waits. For a lock whose readers execute in 10–100 ns, a 10–100 µs wait is fundamentally wrong. Per-CPU rwlocks carry an assumption each reader thread must be the sole thread on its CPU or atomic incr/decr are required for accounting. Here we do allow for non-pinned thread also to be able to take the lock in some very rare and infrequent cases. The latest version includes profiling results for two representative workloads, both showing substantial throughput gains over atomic-RMW rwlocks on the reader-heavy paths this lock targets. Fairness of readers between successive writers: This has not been an observed issue in the target workloads; if it becomes one, a writer-count backoff is a straightforward addition. AI flagged Correctness violations: * Lemma 8.1 / TryWriteLock GV rollover (16-bit). Valid and I shall fix it. * Write unlock memory barrier: This has been fixed in this last version. * Plain-C data races on GV: I will look into it for C11 conformance. * The compact (16-bit) variant was introduced for memory-constrained deployments where hundreds of lock instances must fit in a small footprint. This was changed in latest version and performance profiled is with cache lined aligned per-thread objects. * Write-Unlock broadcast invalidates N reader-owned lines per write: Correct, but this is rare as write lock itself is rare so doesn’t effect datapath performance. Also, this was done for defensive reasons, and can be safely removed, except for in upgrade. * Non-atomic upgrade: This has been addressed in the latest version. Thanks Mukul From: Stephen Hemminger <[email protected]> Date: Tuesday, September 8, 2026 at 10:55 AM To: Mukul Katiyar <[email protected]> Cc: [email protected] <[email protected]> Subject: Re: [RFC] Highly efficient reader-writer lock (EPRW) for mostly-read applications CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you recognize the sender and know the content is safe. On Tue, 8 Sep 2026 03:55:12 +0000 Mukul Katiyar <[email protected]> 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://nam10.safelinks.protection.outlook.com/?url=https%3A%2F%2Fzenodo.org%2Frecords%2F22636501&data=05%7C02%7Cmukul%40versa-networks.com%7Cc15a028a60544172794f08df0dd2654a%7Cd39a23bd897c45f1a3f5c5213b673627%7C0%7C0%7C639244869461676917%7CUnknown%7CTWFpbGZsb3d8eyJFbXB0eU1hcGkiOnRydWUsIlYiOiIwLjAuMDAwMCIsIlAiOiJXaW4zMiIsIkFOIjoiTWFpbCIsIldUIjoyfQ%3D%3D%7C0%7C%7C%7C&sdata=a5uPwrJifNq2SQ5yh38Iko6luqsAWWwvRiLDho3gtd8%3D&reserved=0<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.
