💻 computer science

Enhanced Passive Reader-Writer (EPRW) Locks for Userspace Poll-Mode Datapaths

This paper presents the Enhanced Passive Reader-Writer (EPRW) lock, a userspace adaptation of the original PRW lock that eliminates the incompatible heartbeat requirement for poll-mode datapaths while preserving scalability and adding critical features like lock upgrade, downgrade, and non-blocking acquisition.

Original authors: Mukul Katiyar

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mukul Katiyar

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a busy library where a group of people (the readers) want to browse books simultaneously, while a single person (the writer) needs to rearrange the shelves. The library has a strict rule: no one can move the shelves while anyone is looking at the books, and no one can look at the books while the shelves are being moved.

For a long time, the library used a clever system called the Passive Reader-Writer (PRW) lock. It was amazing because the readers didn't have to shout or tap their feet to say, "I'm here!" They could just walk in quietly. However, this system had a hidden catch: if a writer needed to move the shelves, they had to send a "wake-up call" (like a librarian running down the aisle) to every single person in the building, even those just sitting in the lobby doing nothing. If a person in the lobby forgot to answer the call, the writer would be stuck waiting forever.

In the world of computer chips (specifically in high-speed networks called DPDK), this "wake-up call" system breaks down. Computers in these networks are like super-fast runners who never stop to answer a phone call; they are too busy running a tight loop of tasks. If the library system forced these runners to stop and answer a "heartbeat" call just to say they were still alive, it would slow everything down and break their rhythm.

The Big Discovery
The researchers at Versa Networks, led by Mukul Katiyar, figured out a way to fix this. They created a new system called the Enhanced Passive Reader-Writer (EPRW) lock.

Here is the magic trick: Instead of waiting for a wake-up call, the readers now carry a small, glowing badge that updates itself automatically while they are waiting in line.

The Old Way: If a reader was waiting for the writer, they would hide their badge. The writer, seeing no badge, would panic and wait forever, thinking the reader was lost.
The New Way: The reader keeps their badge glowing and updates it while they are waiting. The writer looks at the badge and sees, "Ah, this person is still here, but they are just waiting at the door, not actually inside the room." Because the writer knows the reader is just waiting, the writer can safely move the shelves without needing a wake-up call.

What This Solves
The paper proves that this new method works perfectly. It removes the annoying rule that forced every single computer thread to stop and "check in" (the heartbeat) just to be polite.

No more heartbeats: Threads that are idle or just waiting don't need to do anything extra. They just keep spinning their wheels, and the system knows they are safe.
Speed: The readers still get their "atomic-free" fast path, meaning they can grab the lock without slowing down the whole system.
New Tricks: The authors also added features the old system didn't have, like letting a reader instantly turn into a writer (upgrade) or a writer turn back into a reader (downgrade) without causing a traffic jam.

The "Compact" Version
The paper also suggests a way to make this system use less memory. The original system used huge 64-bit counters (like a odometer that goes up to 18 quintillion). The new system can use tiny 16-bit counters (like a car odometer that rolls over after 65,536 miles).

The Risk: If the counter rolls over, the writer might get confused and think an old reader is still there.
The Fix: The authors proved that by broadcasting the current counter number to everyone every time a writer finishes, the system stays safe even if the counter rolls over. This allows the system to shrink from needing 64 bytes of memory per thread down to just 3 bytes—a massive saving for systems with hundreds of threads.

How Sure Are They?
The authors didn't just guess; they proved the math works using strict logic. They also ran a massive test with 65 threads running billions of operations, and the system passed with zero errors. Most importantly, they tell us this isn't just a theory: the system has been running in production at Versa Networks for several years, handling real network traffic without any failures.

What They Rule Out
The paper is very clear about what doesn't work in this specific environment. It argues that the old "heartbeat" requirement is a dead end for these types of high-speed computer networks. You cannot just patch the old system; you have to change the rules of how the readers and writers talk to each other. The paper rejects the idea that idle threads need to be forced to update their status manually.

In short, the EPRW lock is a smarter, lighter, and faster way to manage traffic in high-speed computer networks, removing the need for constant "check-ins" and letting the system run smoothly without the writers getting stuck in traffic jams.

Technical Summary: Enhanced Passive Reader-Writer (EPRW) Locks for Userspace Poll-Mode Datapaths

Problem Statement

The paper addresses a critical scalability bottleneck in userspace packet processing environments, specifically those utilizing the Data Plane Development Kit (DPDK). The authors identify that adapting the Passive Reader-Writer (PRW) lock—originally designed for OS kernels—to userspace introduces a structural flaw known as the heartbeat requirement.

In the original kernel-based PRW algorithm (Liu, Zhang, and Chen, USENIX ATC'14), writers rely on Inter-Processor Interrupts (IPIs) to force idle cores to update their version counters, ensuring writers do not stall indefinitely. In userspace, IPIs are unavailable. Consequently, the adaptation requires every registered thread, including those that are entirely idle or performing unrelated work, to periodically call a Read_Heartbeat function to update its version counter. If a single thread neglects this call, it stalls all writers indefinitely.

This requirement is fundamentally incompatible with the "poll-mode" programming discipline of DPDK, where logical cores (lcores) execute tight, deterministic forwarding loops. Forcing every lcore to call a heartbeat function on every loop iteration—even when the lock is not involved—couples all code paths to the locking library, disrupts packet timing, and introduces significant error-prone complexity at scale.

Methodology: The EPRW Algorithm

The authors propose the Enhanced Passive Reader-Writer (EPRW) lock, an adaptation that eliminates the heartbeat requirement entirely by reinterpreting the semantics of the "version match" condition.

Key Algorithmic Changes

Boundary Semantics: In the original PRW lock, a reader clears its presence flag (RP) before spinning externally when a writer is detected, updating its version counter as a "farewell." In EPRW, the reader retains its presence flag while spinning in the Read_Lock loop and continuously updates its version counter (TV) within that loop.
New Invariant: Under EPRW, a version match (TV[i] == GV) combined with a present flag (RP[i] == Present) implies that the thread is at the lock boundary (waiting for the writer to release) and not inside a critical section. This allows writers to safely proceed past such threads without waiting for an external heartbeat.
Writer Scan Logic: The writer's scan condition is modified to RP[i] == Present ∧ TV[i] != GV. This ensures that threads which are idle (Absent) are skipped, while threads waiting at the boundary (Present) are recognized as having acknowledged the current epoch.
Version Broadcast: To support compact 16-bit version counters and prevent rollover issues, the Write_Unlock operation includes a broadcast step where the writer updates the version counter of all registered threads to the current global version before releasing the lock. This ensures no thread retains a stale version from a previous epoch.
Non-Atomic Operations: The algorithm utilizes non-atomic increments for the global version counter (GV) during the write lock acquisition, relying on the mutual exclusion provided by the Compare-And-Swap (CAS) on the writer flag to ensure safety. This reduces cache-line contention.

Extended Operations

The paper extends the base algorithm to include operations necessary for production userspace use, which were absent in the original design:

Atomic Upgrade: A reader can atomically transition to a writer.
Atomic Downgrade: A writer can atomically transition to a reader.
Non-Blocking Try-Locks: Variants for both readers and writers that return immediately if the lock cannot be acquired, rather than spinning.

Key Contributions

Elimination of the Heartbeat Requirement: The primary contribution is the identification that the heartbeat requirement is an artifact of the userspace adaptation's handling of stale version counters. By redefining the spin-loop behavior, the authors remove the need for periodic refresh calls by idle threads.
Correctness Proof: The authors provide a formal proof of the algorithm's safety (writer exclusion and reader-writer exclusion) and progress guarantees under a sequentially consistent memory model, with analysis for relaxed memory models (x86-TSO and ARMv8).
Memory Compactness: The introduction of a 16-bit version counter variant, coupled with the write-unlock broadcast mechanism, allows for significant memory savings (up to 10.7× reduction in storage for specific configurations) without sacrificing correctness against counter rollover.
Production Validation: The algorithm has been deployed in a production DPDK-based network function at Versa Networks.

Results and Validation

Correctness: The EPRW lock preserves the safety and progress guarantees of the original PRW algorithm. The reader fast path remains structurally identical to the original (one store, one fence, one load), ensuring equivalent read-path throughput.
Production Deployment: The lock has operated continuously for several years in a production environment at Versa Networks. No correctness failures attributable to the locking algorithm have been observed.
Testing: Prior to deployment, the implementation underwent rigorous validation with a multi-threaded test program spawning 65 threads executing billions of iterations of all lock operations (including upgrades, downgrades, and try-locks). The test passed with zero assertion failures, verifying mutual exclusion invariants.
Overhead: The write-unlock path introduces an $O(N)$ version broadcast. However, for read-dominated workloads typical of PRW-family locks, this cost is amortized over the write interval and bounded by a small constant number of cache lines.

Significance

The paper claims that the EPRW lock fundamentally simplifies the locking discipline for packet processing threads in userspace. By removing the pervasive heartbeat obligation, it eliminates a class of latent correctness risks where a single idle thread could stall the entire system. The algorithm successfully adapts the high scalability of passive locking to the strict, non-preemptive constraints of DPDK lcores, enabling the use of reader-writer locks in environments where they were previously considered impractical due to the heartbeat requirement. The work demonstrates that the IPI-based mechanism of the kernel can be effectively replaced by a semantic reinterpretation of the spin loop, achieving similar scalability without the associated userspace overhead.