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

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

[Mukul Katiyar]

[-- Attachment #1: Type: text/plain, Size: 802 bytes --]

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


[-- Attachment #2: Type: text/html, Size: 2883 bytes --]

Re: [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@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

Dead link.
I looked at the original article as found by web search.

> 
> Would this be a useful addition to DPDK?
> 
> Regards,
> Mukul Katiyar
> Versa Networks
> 

Send it as a patch. I have looked at lots of different reader-write lock implementations such
as phase-fair and mcs reader writer locks. The trade off is always cost of lock acquisition
when uncontended, versus behaviour under heavy contention. The current trivial version is fast
when uncontended; other algorithms add a queue (like mcs) which makes them behave better
when getting hammered by lots of contention.

DPDK was also fixed to not starve writers several releases ago. It seems the research
paper is referring to original old code.

Also using reader-write locks should always be discouraged. RCU is a much better solution.

Re: [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@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.

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

[Mukul Katiyar]

[-- Attachment #1: Type: text/plain, Size: 2816 bytes --]

Hi all,

Apologies for the issue with the link to the latest version. Zenodo—a widely used European preprint repository—has been experiencing frequent downtime over the last few days.

Stephen, it looks like the web search turned up an older version. Here is the latest version, which addresses the gaps in the previous draft regarding weakly ordered memory architectures, adds performance comparisons, covers rollover/    broadcast mechanics, and details cache-line-aligned per-thread objects.:

https://drive.google.com/drive/folders/10vzzQYHB2Z6KKIWyqI2fDxiss1jTA8QM?usp=sharing

I will reply separately regarding the design choices and their practical utility.

Thanks,
Mukul

From: Stephen Hemminger <stephen@networkplumber.org>
Date: Tuesday, September 8, 2026 at 10:40 AM
To: Mukul Katiyar <mukul@versa-networks.com>
Cc: dev@dpdk.org <dev@dpdk.org>
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 <mukul@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<https://zenodo.org/records/22636501>

Dead link.
I looked at the original article as found by web search.

>
> Would this be a useful addition to DPDK?
>
> Regards,
> Mukul Katiyar
> Versa Networks
>

Send it as a patch. I have looked at lots of different reader-write lock implementations such
as phase-fair and mcs reader writer locks. The trade off is always cost of lock acquisition
when uncontended, versus behaviour under heavy contention. The current trivial version is fast
when uncontended; other algorithms add a queue (like mcs) which makes them behave better
when getting hammered by lots of contention.

DPDK was also fixed to not starve writers several releases ago. It seems the research
paper is referring to original old code.

Also using reader-write locks should always be discouraged. RCU is a much better solution.

[-- Attachment #2: Type: text/html, Size: 6001 bytes --]

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

[Mukul Katiyar]

[-- Attachment #1: Type: text/plain, Size: 12222 bytes --]

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 <stephen@networkplumber.org>
Date: Tuesday, September 8, 2026 at 10:55 AM
To: Mukul Katiyar <mukul@versa-networks.com>
Cc: dev@dpdk.org <dev@dpdk.org>
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 <mukul@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://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.


[-- Attachment #2: Type: text/html, Size: 21922 bytes --]