NAME
Acme::Parataxis::Sync::RwLock - Reader-writer lock: many readers, or one writer
SYNOPSIS
use v5.40;
use Acme::Parataxis qw[async fiber];
use Acme::Parataxis::Sync::RwLock;
my $table = Acme::Parataxis::Sync::RwLock->new;
my %cache;
async {
my @handles;
for my $id ( 1 .. 3 ) {
push @handles, fiber {
my $guard = $table->read_guard; # several readers may be inside at once
$cache{"row $id"} = $id * 10;
};
}
$_->await for @handles;
say 'read ', join ', ', map { $cache{$_} } sort keys %cache;
say 'and the lock is free again, ', $table->readers, ' holds left';
{
my $guard = $table->write_guard; # now nobody else gets in
$cache{'row 4'} = 40;
}
say 'after the writer, the cache holds ', scalar keys %cache, ' rows';
};
# read 10, 20, 30
# and the lock is free again, 0 holds left
# after the writer, the cache holds 4 rowsDESCRIPTION
A lock with two modes. Any number of fibers may hold a read hold at the same time; a write hold is exclusive, and no read or write can be taken while it is held. A fiber that already holds a read hold may take another, and the lock keeps count rather than parking - which is what lets the same fiber read the same structure from inside a function it is already reading.
The interesting part is how the two queues interact. A waiting writer is served first, and a reader arriving while a writer is queued joins the queue behind it instead of going straight in. That is the difference from a naive readers-writer lock, and it is what stops a steady stream of readers from starving a writer indefinitely.
use v5.40;
use Acme::Parataxis qw[async fiber await_sleep];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
my @log;
async {
my $first = fiber {
$lock->read_lock;
await_sleep( 100 );
$lock->read_unlock;
push @log, 'first reader out';
};
await_sleep( 10 );
my $writer = fiber {
$lock->write_lock;
push @log, 'writer in';
await_sleep( 20 );
$lock->write_unlock;
push @log, 'writer out';
};
await_sleep( 10 );
my @others;
for my $id ( 1 .. 2 ) {
push @others, fiber {
$lock->read_lock;
push @log, "reader $id in";
await_sleep( 5 );
$lock->read_unlock;
};
}
$first->await;
$writer->await;
$_->await for @others;
push @log, 'both readers out';
say join ', ', @log;
};
# first reader out, writer in, writer out, reader 1 in, reader 2 in, both readers outThe two readers queued behind the writer are let in together, by a single pass over the read queue, so they overlap rather than running one after the other - and neither of them got in early, even though the lock was readable for most of the writer's wait.
METHODS
new( )
use v5.40;
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
say 'a fresh lock: writer ', ( defined $lock->writer ? 'set' : 'none' )
. ', readers ' . $lock->readers
. ', waiters ' . $lock->waiters;
# a fresh lock: writer none, readers 0, waiters 0Creates an unlocked lock. Takes no arguments: an unknown key croaks with Unrecognized parameters for "Acme::Parataxis::Sync::RwLock" constructor.
read_lock( )
use v5.40;
use Acme::Parataxis qw[async];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
$lock->read_lock;
say 'outstanding holds: ', $lock->readers;
$lock->read_lock; # a second hold on the same fiber
say 'and after deepening: ', $lock->readers;
say 'but only one fiber is holding: ', $lock->read_holders;
$lock->read_unlock;
$lock->read_unlock;
say 'both released: ', $lock->readers;
};
# outstanding holds: 1
# and after deepening: 2
# but only one fiber is holding: 1
# both released: 0Takes a read hold, parking only while a writer holds the lock or is queued ahead of you, and returns true. Every call takes one hold, so two calls need two read_unlock calls.
If the calling fiber already holds a read hold the lock deepens in place rather than parking, and returns true. That is not a convenience - parking there would deadlock, because a queued writer is waiting for this fiber's first hold to drain while the second hold waits for the writer. The same applies when the calling fiber is the writer: it may take a read hold, because it already has exclusive access.
read_unlock( )
use v5.40;
use Acme::Parataxis qw[async];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
say 'with no hold: ', ( eval { $lock->read_unlock; 'allowed' } || 'croaks' );
$lock->read_lock;
$lock->read_lock;
$lock->read_unlock;
say 'one hold left: ', $lock->readers;
$lock->read_unlock;
say 'none left: ', $lock->readers;
};
# with no hold: croaks
# one hold left: 1
# none left: 0Releases exactly one read hold belonging to the calling fiber, and returns true. Croaks if this fiber holds none.
Releasing one hold at a time is what lets nested read_guards unwind independently: an inner guard's destruction frees its own hold and cannot strand the outer one on a hold the fiber no longer has.
try_read_lock( )
use v5.40;
use Acme::Parataxis qw[async];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
say 'on a free lock: ', ( $lock->try_read_lock ? 'taken' : 'refused' );
$lock->read_lock;
say 'while this fiber holds one: ', ( $lock->try_read_lock ? 'deepened' : 'refused' );
$lock->read_unlock;
$lock->read_unlock;
};
# on a free lock: taken
# while this fiber holds one: deepenedTakes a read hold only if it can be taken at once, returning true, and false without parking otherwise. False means a writer holds the lock or a writer is queued - a queued writer is enough, so a reader never jumps the queue. The deepening rule from read_lock applies here too, so this returns true rather than false when the calling fiber already holds a read hold.
write_lock( )
use v5.40;
use Acme::Parataxis qw[async];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
$lock->read_lock;
say 'upgrading a read hold: ', ( eval { $lock->write_lock; 'allowed' } || 'croaks' );
$lock->read_unlock;
$lock->write_lock;
say 'now the writer is fiber: ', $lock->writer;
say 'and re-entering: ', ( eval { $lock->write_lock; 'allowed' } || 'croaks' );
$lock->write_unlock;
};
# upgrading a read hold: croaks
# now the writer is fiber: 0
# and re-entering: croaksTakes the exclusive write lock, parking until every reader has drained and no writer is queued ahead of you, and returns true. Croaks if the calling fiber already holds the write lock, and croaks if it holds a read hold.
That second croak is the one to design around: upgrading a read hold to a write hold is not supported. There is no deadlock-prone retry in there, and no silent promotion either. A fiber that holds a read and needs to write has to drop the read and take the write, which means going back through the queue.
write_unlock( )
use v5.40;
use Acme::Parataxis qw[async fiber await_sleep];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
say 'with no writer: ', ( eval { $lock->write_unlock; 'allowed' } || 'croaks' );
$lock->write_lock;
my $rival = fiber {
await_sleep( 20 );
say 'from another fiber: ', ( eval { $lock->write_unlock; 'allowed' } || 'croaks' );
};
$rival->await;
$lock->write_unlock;
};
# with no writer: croaks
# from another fiber: croaksReleases the write lock, handing it to the next queued writer if there is one, or letting the queued readers in otherwise, and returns true. Croaks if the lock is not write-held, and croaks if the calling fiber is not the writer.
try_write_lock( )
use v5.40;
use Acme::Parataxis qw[async fiber await_sleep];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
say 'on a free lock: ', ( $lock->try_write_lock ? 'taken' : 'refused' );
$lock->write_unlock;
my $reader = fiber { $lock->read_lock; await_sleep( 100 ); $lock->read_unlock };
await_sleep( 10 );
say 'while a reader holds it: ', ( $lock->try_write_lock ? 'taken' : 'refused' );
$reader->await;
};
# on a free lock: taken
# while a reader holds it: refusedTakes the write lock only if it is completely free, returning true, and false without parking otherwise. False means a writer holds it, any reader holds it, or a writer is queued. It croaks on the same two mistakes as write_lock - re-entry, and trying to upgrade a read hold.
read_guard( ) and write_guard( )
use v5.40;
use Acme::Parataxis qw[async];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
{
my $guard = $lock->read_guard; # takes a read hold, parking if it must
say 'inside, outstanding holds: ', $lock->readers;
}
say 'released at the end of the block: ', $lock->readers;
{
my $guard = $lock->write_guard;
say 'and in write mode, the writer is: ', $lock->writer;
}
say 'released, so the writer is: ', ( defined $lock->writer ? 'still set' : 'none' );
};
# inside, outstanding holds: 1
# released at the end of the block: 0
# and in write mode, the writer is: 0
# released, so the writer is: noneTake the lock in the given mode and return an opaque guard that releases it when the guard is destroyed. Because the release is at destruction, an exception part-way through the block still gives the lock back.
Both return the same class, Acme::Parataxis::Sync::RwLock::Guard, which has no methods of its own. It is not a lock and it does not expose the lock it wraps; its only job is to call read_unlock or write_unlock at destruction, depending on the mode it was made with.
writer and owner
use v5.40;
use Acme::Parataxis qw[async];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
say 'before anything: ', ( defined $lock->writer ? 'set' : 'none' );
async {
$lock->write_lock;
say 'while held, by fiber: ', $lock->writer;
$lock->write_unlock;
};
# before anything: none
# while held, by fiber: 0The id of the fiber holding the write lock, or undef when there is none. owner returns the same value - it is here for symmetry with Acme::Parataxis::Sync::Mutex, whose owner means the same thing. Neither says anything about read holds; for those see readers. Both are readers, so they work off a fiber as well as on one.
readers and read_holders
use v5.40;
use Acme::Parataxis qw[async fiber];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
say 'on a free lock: holds ', $lock->readers, ', holders ', $lock->read_holders;
my $deep = fiber {
$lock->read_lock;
$lock->read_lock;
await_sleep( 50 );
$lock->read_unlock;
$lock->read_unlock;
};
await_sleep( 10 );
say 'one fiber with two holds: holds ', $lock->readers, ', holders ', $lock->read_holders;
my $other = fiber { $lock->read_lock; await_sleep( 20 ); $lock->read_unlock };
await_sleep( 10 );
say 'and a second fiber: holds ', $lock->readers, ', holders ', $lock->read_holders;
$_->await for $deep, $other;
say 'once they are done: holds ', $lock->readers, ', holders ', $lock->read_holders;
};
# on a free lock: holds 0, holders 0
# one fiber with two holds: holds 2, holders 1
# and a second fiber: holds 3, holders 2
# once they are done: holds 0, holders 0readers is the number of outstanding read holds, counted one per read_lock call, so deepening a hold shows up here. read_holders is the number of fibers that hold at least one, so it does not. Both are readers, so they work off a fiber as well as on one.
waiters, read_waiters and write_waiters
use v5.40;
use Acme::Parataxis qw[async fiber await_sleep];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
my $reader = fiber { $lock->read_lock; await_sleep( 100 ); $lock->read_unlock };
await_sleep( 10 );
my $writer = fiber { $lock->write_lock; await_sleep( 20 ); $lock->write_unlock };
await_sleep( 10 );
my @late;
for my $id ( 1 .. 2 ) { push @late, fiber { $lock->read_lock; $lock->read_unlock } }
await_sleep( 10 );
say 'reading: ', scalar( $lock->read_waiters ), ', writing: ', scalar( $lock->write_waiters )
. ', total: ' . $lock->waiters;
$reader->await;
$writer->await;
$_->await for @late;
say 'once it is all over: ', $lock->waiters;
};
# reading: 2, writing: 1, total: 3
# once it is all over: 0How many fibers are queued: read_waiters for a read hold, write_waiters for the write lock, and waiters for both together. They count the two queues, so a single reader queued behind a single writer is waiters 2. A fiber running the action is not in any of them, and each count drops as its queue is served rather than when the waiter runs. All three are readers, so they work off a fiber as well as on one.
Be careful how you call the two queue readers. They are readers on an array field, so they follow the usual array rule: in scalar context you get the count, and in list context you get the queued fiber ids. say takes a list, so asking it to print one of them directly splices the ids into your sentence instead of a number, and with nothing queued it splices in nothing at all.
use v5.40;
use Acme::Parataxis qw[async fiber await_sleep];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
my $holder = fiber { $lock->write_lock; await_sleep( 100 ); $lock->write_unlock };
await_sleep( 10 );
my @queued = map { fiber { $lock->read_lock; $lock->read_unlock } } 1 .. 2;
await_sleep( 10 );
my @ids = $lock->read_waiters;
say 'asked for a list: ', scalar @ids, ' items come back';
say 'asked for a count: ', scalar( $lock->read_waiters );
say 'joined into a string: ', length( join '', $lock->read_waiters ), ' characters';
$holder->await;
$_->await for @queued;
say 'with nothing queued, the same join: ', length( join '', $lock->read_waiters ), ' characters';
};
# asked for a list: 2 items come back
# asked for a count: 2
# joined into a string: 2 characters
# with nothing queued, the same join: 0 charactersThe two items and the two characters are the two fiber ids, not the number two - the count happens to agree here only because two fibers are queued. Wrap the call in scalar whenever it goes straight into a string. waiters is an ordinary method and always returns a count, so it needs no such care.
How It Works
Five pieces of state carry it: $writer, the fiber holding the write lock or undef; $readers, the count of outstanding read holds; %read_holders, fiber id to how many holds that fiber owns; and the two queues @read_waiters and @write_waiters.
Everything funnels through one private method, _pump, which runs on every release. It has exactly two rules: if a writer is queued, hand the lock to the first of them and return; otherwise grant a read hold to every queued reader in a single pass. That is the whole of the fairness policy, and it is why writers cannot be starved and why waiting readers end up sharing rather than queuing.
A release calls _pump only when it could matter. read_unlock calls it when the last hold drains, because a writer may be waiting for that; write_unlock calls it unconditionally, because either queue may be waiting for the writer to leave. Grants are recorded before the woken fiber runs, so there is no instant at which the lock looks free and another fiber can take it - the same atomic hand-off the rest of the family uses.
Recipes
Protecting a structure that is read far more than it is written
The shape to reach for. Reads take the read guard, so they overlap freely; the occasional write takes the write guard and everyone else waits.
use v5.40;
use Acme::Parataxis qw[async fiber await_sleep];
use Acme::Parataxis::Sync::RwLock;
my $index = Acme::Parataxis::Sync::RwLock->new;
my %table = ( alpha => 1, beta => 2 );
async {
my @readers = map {
fiber {
my $guard = $index->read_guard; # the rest just read
say 'outstanding read holds, as this reader sees them: ', $index->readers;
await_sleep( 20 );
return;
}
} 1 .. 3;
await_sleep( 10 );
my $writer = fiber {
my $guard = $index->write_guard; # one fiber rewrites
%table = ( alpha => 1, beta => 2, gamma => 3 );
return;
};
$_->await for @readers;
$writer->await;
say 'and the keys are now ', join ', ', ( sort keys %table );
};
# outstanding read holds, as this reader sees them: 1
# outstanding read holds, as this reader sees them: 2
# outstanding read holds, as this reader sees them: 3
# and the keys are now alpha, beta, gammaEach reader's guard is a separate hold, so the count climbs as they arrive: the last one to get in saw three readers holding at once. The writer queued behind all of them and was served once they had drained.
Letting a fiber re-read what it is already reading
read_lock counts holds per fiber rather than parking, so a helper called from inside a critical section can take the read hold it needs and give it straight back.
use v5.40;
use Acme::Parataxis qw[async];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
my %seen;
sub lookup {
my $key = shift;
my $guard = $lock->read_guard; # a second hold on the same fiber
return $seen{$key};
}
async {
my $guard = $lock->read_guard; # the outer hold
$seen{answer} = 42;
say 'from inside a read hold: ', lookup('answer');
say 'holds taken: ', $lock->readers, ' (the inner one is back already)';
$seen{answer} = 43;
say 'and the outer hold still protects the write: ', $lock->readers;
};
# from inside a read hold: 42
# holds taken: 1 (the inner one is back already)
# and the outer hold still protects the write: 1Bounding a wait
A fiber parked for a read or a write hold is parked on an ordinary interruptible wait, so with_timeout( $ms, ... ) bounds it and a cancelled token aborts it. Either way the fiber leaves the queue, and a queued writer is not left waiting on a hold that will never arrive.
use v5.40;
use Acme::Parataxis qw[async fiber await_sleep];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
my $reader = fiber { $lock->read_lock; await_sleep( 200 ); $lock->read_unlock };
await_sleep( 10 );
my $impatient = fiber {
eval { Acme::Parataxis::with_timeout( 30, sub { $lock->write_lock } ) };
my $why = $@ ? ( $@->message =~ s/ at .*//sr ) : 'got it';
say 'the impatient writer: ', $why;
say ' and the write queue it left: ', scalar( $lock->write_waiters );
};
$impatient->await;
say 'the read hold is untouched: ', $lock->readers;
$reader->await;
};
# the impatient writer: The operation timed out
# and the write queue it left: 0
# the read hold is untouched: 1Behavior Notes
There is no upgrade from read to write
write_lock and try_write_lock both croak if the calling fiber holds a read hold, rather than taking the write lock and hoping the other holds drain. That is the safe choice - a silent upgrade that waited for its own holds would deadlock, because it is the fiber that has to release them - but it means the pattern is not available.
The way out is to release the read holds first and then take the write lock, accepting the gap. If the work between the two must be atomic, the structure has to be reachable another way: keep a separate mutex for the fields that actually need read-to-write promotion, and use this lock for the read-mostly ones.
use v5.40;
use Acme::Parataxis qw[async];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
my %seen;
async {
$lock->read_lock;
$lock->read_lock;
say 'holds before: ', $lock->readers;
$lock->read_unlock;
$lock->read_unlock;
say 'after dropping both: ', $lock->readers;
say 'now the write lock is: ', ( $lock->try_write_lock ? 'available' : 'refused' );
$lock->write_unlock;
};
# holds before: 2
# after dropping both: 0
# now the write lock is: availableA queued writer turns every read lock into a wait
Writer preference is not a hint - a queued writer is enough to make read_lock park, and enough to make try_read_lock return false. A fiber that reads in a loop while writers are waiting can therefore find itself parking on reads it would previously have taken instantly, even though the lock was readable the whole time.
That is the intended trade: without it a steady stream of readers can keep a writer waiting indefinitely, because each new reader is granted as soon as the current holds drain. If your workload really is read-mostly and you cannot accept occasional writer delays, this is the wrong lock for it.
use v5.40;
use Acme::Parataxis qw[async fiber await_sleep];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
my $reader = fiber { $lock->read_lock; await_sleep( 100 ); $lock->read_unlock };
await_sleep( 10 );
my $first = $lock->try_read_lock;
say 'before any writer queues, a try_read: ', ( $first ? 'taken' : 'refused' );
$lock->read_unlock if $first;
my $writer = fiber { $lock->write_lock; await_sleep( 20 ); $lock->write_unlock };
await_sleep( 10 );
my $second = $lock->try_read_lock;
say 'once one has queued, the same call: ', ( $second ? 'taken' : 'refused' );
$lock->read_unlock if $second;
$reader->await;
$writer->await;
};
# before any writer queues, a try_read: taken
# once one has queued, the same call: refusedThe two calls are the same, made either side of one write_lock and nothing else. Only the queue in between changed the answer, so it is the queue and not the hold that did it. Each read_unlock is guarded because a refused try_read_lock leaves nothing to release, and read_unlock croaks on a fiber that holds no read.
A stranded hold bricks the lock
Nothing releases a read or a write hold on behalf of a fiber that ends holding one, and there is no API to take a hold back. A fiber that returns from inside a critical section leaves the holds outstanding, and for the write lock that is permanent: the lock is held by a fiber that no longer exists, so nothing can ever take it again.
use v5.40;
use Acme::Parataxis qw[async fiber await_sleep];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
my $holder = fiber { $lock->write_lock; 1 }; # returns without unlocking
$holder->await;
await_sleep( 10 );
say 'the holder is gone and the lock is still held';
say ' a new fiber can take a read: ', ( $lock->try_read_lock ? 'yes' : 'no' );
say ' a new fiber can take a write: ', ( $lock->try_write_lock ? 'yes' : 'no' );
};
# the holder is gone and the lock is still held
# a new fiber can take a read: no
# a new fiber can take a write: noA stranded read hold is less absolute but just as confusing, because of how fiber ids work. A fiber's id is recycled as soon as it finishes, so the next fiber to be created is handed the dead one's id - and the lock now believes it holds the read. Asking for the write lock then fails with the upgrade croak from "write_lock( )", naming a problem the caller does not have:
use v5.40;
use Acme::Parataxis qw[async fiber await_sleep];
use Acme::Parataxis::Sync::RwLock;
my $lock = Acme::Parataxis::Sync::RwLock->new;
async {
my $holder = fiber { $lock->read_lock; 1 }; # returns without unlocking
$holder->await;
await_sleep( 10 );
say 'the holder is gone, readers stranded at ', $lock->readers;
my $next = fiber {
my $why = eval { $lock->write_lock; 'it took the write lock' } || $@;
$why =~ s/\s+at .*//s;
$why =~ s/;.*//s; # just the reason, not the advice
say ' and a new fiber asking for the write: ', $why;
};
$next->await;
};
# the holder is gone, readers stranded at 1
# and a new fiber asking for the write: RwLock write_lock: this fiber holds a read lockThe same recycling explains the write-lock case from the other direction. The stranded writer is fid 1, the next fiber created is also fid 1, and write_lock reports RwLock is not reentrant: this fiber already holds the write lock - a reentrancy error for a lock the caller has never touched.
What prevents all of this is the guard: take it into a lexical at the top of the body and let scope exit release it. That covers an exception and a fiber that returns early, which between them are nearly all of it. It does not cover a fiber torn down without unwinding its scopes.
SEE ALSO
Acme::Parataxis::Sync, Acme::Parataxis::Sync::Mutex, Acme::Parataxis::Sync::WaitGroup, Acme::Parataxis::Sync::Barrier, Acme::Parataxis::Sync::Once, Acme::Parataxis::Error::Timeout, Acme::Parataxis::Error::Cancelled
AUTHOR
Sanko Robinson https://github.com/sanko
LICENSE
Copyright (C) Sanko Robinson.
This library is free software; you can redistribute it and/or modify it under the terms found in the Artistic License 2.