Skip to content

Instantly share code, notes, and snippets.

@jnthn
Created September 18, 2017 10:24
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jnthn/6f4a2258092a7fac7f80056a982e8003 to your computer and use it in GitHub Desktop.
Save jnthn/6f4a2258092a7fac7f80056a982e8003 to your computer and use it in GitHub Desktop.
use nqp;
# An asynchronous lock provides a non-blocking non-reentrant mechanism for
# mutual exclusion. The lock method returns a Promise, hich will already be
# Kept if nothing was holding the lock already, so execution can proceed
# immediately. For performance reasons, in this case it returns a singleton
# Promise instance. Otherwise, a Promise in planned state will be returned,
# and Kept once the lock has been unlocked by its current holder. The lock
# and unlock do not need to take place on the same thread; that's why it's not
# reentrant.
my class X::Lock::Async::NotLocked is Exception {
method message() {
"Cannot unlock a Lock::Async that is not currently locked"
}
}
my class Lock::Async {
# The Holder class is an immutable object. A type object represents an
# unheld lock, an instance represents a held lock, and it has a queue of
# vows to be kept on unlock.
my class Holder {
has $!queue;
method queue-vow(\v) {
my $new-queue := $!queue.DEFINITE
?? nqp::clone($!queue)
!! nqp::list();
nqp::push($new-queue, v);
nqp::p6bindattrinvres(nqp::create(Holder), Holder, '$!queue', $new-queue)
}
method waiter-queue-length() {
nqp::elems($!queue)
}
# Assumes it won't be called if there is no queue (SINGLE_HOLDER case
# in unlock())
method head-vow() {
nqp::atpos($!queue, 0)
}
# Assumes it won't be called if the queue only had one item in it (to
# mantain SINGLE_HOLDER fast path usage)
method without-head-vow() {
my $new-queue := nqp::clone($!queue);
nqp::shift($new-queue);
nqp::p6bindattrinvres(nqp::create(Holder), Holder, '$!queue', $new-queue)
}
}
# Base states for Holder
my constant NO_HOLDER = Holder;
my constant SINGLE_HOLDER = Holder.new;
# The current holder record, with waiters queue, of the lock.
has Holder $!holder = Holder;
# Singleton Promise to be used when there's no need to wait.
my \KEPT-PROMISE := do {
my \p = Promise.new;
p.keep(True);
p
}
method lock(Lock::Async:D: --> Promise) {
loop {
my $holder :=$!holder;
if $holder.DEFINITE {
my $p := Promise.new;
my $v := $p.vow;
my $holder-update = $holder.queue-vow($v);
if cas($!holder, $holder, $holder-update) =:= $holder {
return $p;
}
}
else {
if cas($!holder, NO_HOLDER, SINGLE_HOLDER) =:= NO_HOLDER {
# Successfully acquired and we're the only holder
return KEPT-PROMISE;
}
}
}
}
method unlock(Lock::Async:D: --> Nil) {
loop {
my $holder :=$!holder;
if $holder =:= SINGLE_HOLDER {
# We're the single holder and there's no wait queue.
if cas($!holder, SINGLE_HOLDER, NO_HOLDER) =:= SINGLE_HOLDER {
# Successfully released to NO_HOLDER state.
return;
}
}
elsif $holder.DEFINITE {
my int $queue-length = $holder.waiter-queue-length();
my $v := $holder.head-vow;
if $queue-length == 1 {
if cas($!holder, $holder, SINGLE_HOLDER) =:= $holder {
# Successfully released; keep the head vow, thus
# giving the lock to the next waiter.
$v.keep(True);
return;
}
}
else {
my $new-holder := $holder.without-head-vow();
if cas($!holder, $holder, $new-holder) =:= $holder {
# Successfully released and installed remaining queue;
# keep the head vow which we successfully removed.
$v.keep(True);
return;
}
}
}
else {
die X::Lock::Async::NotLocked.new;
}
}
}
method protect(Lock::Async:D: &code) {
my int $acquired = 0;
await self.lock();
$acquired = 1;
LEAVE self.unlock() if $acquired;
code()
}
}
use Test;
throws-like { Lock::Async.new.unlock },
X::Lock::Async::NotLocked,
'Cannot unlock an async lock that was never locked';
{
my $lock = Lock::Async.new;
lives-ok { await $lock.lock() }, 'Can successfully acquire the lock';
lives-ok { $lock.unlock() }, 'Can successfully release the lock';
lives-ok { await $lock.lock() }, 'Can successfully acquire the lock again';
lives-ok { $lock.unlock() }, 'Can successfully release the lock again';
throws-like { Lock::Async.new.unlock },
X::Lock::Async::NotLocked,
'Trying an extra unlock dies';
}
{
my $lock = Lock::Async.new;
my $acquire1 = $lock.lock();
isa-ok $acquire1, Promise, 'lock() method returns a Promise';
is $acquire1.status, Kept, 'The Promise on first call to lock is Kept';
my $acquire2 = $lock.lock();
isa-ok $acquire2, Promise, 'Second call to lock() method returns a Promise';
is $acquire2.status, Planned, 'The Promise on the second call to lock is Planned';
lives-ok { $lock.unlock() }, 'Can unlock';
await Promise.anyof($acquire2, Promise.in(5));
is $acquire2.status, Kept, 'The Promise on the second lock() call was kept';
lives-ok { $lock.unlock() }, 'Can unlock the second time';
my $acquire3 = $lock.lock();
is $acquire3.status, Kept, 'Locking the now-free lock again works';
lives-ok { $lock.unlock() }, 'And can unlock it again';
}
{
my $lock = Lock::Async.new;
my @promises;
lives-ok { @promises = $lock.lock() xx 5 }, '5 acquires in a row work';
for ^5 -> $i {
isa-ok @promises[$i], Promise, "Acquire {$i + 1} returns a Promise";
}
is @promises[0].status, Kept, 'First Promise is kept';
for 1..4 -> $i {
is @promises[$i].status, Planned, "Promise {$i + 1} is planned";
}
for 1..4 -> $i {
lives-ok { $lock.unlock() }, "Unlock $i lived";
await Promise.anyof(@promises[$i], Promise.in(5));
is @promises[$i].status, Kept, "Promise {$i + 1} is now also kept";
}
lives-ok { $lock.unlock() }, 'Unlock 5 lived';
my $acquire-after = $lock.lock();
is $acquire-after.status, Kept, 'Locking the now-free lock again works';
lives-ok { $lock.unlock() }, 'And can unlock it again';
}
done-testing;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment