Open bakkot opened 1 month ago
Neither are the design we've been working on, though it is close. The approach we've been considering is somewhat similar to the C++ unique_lock
, given the flexibility that a UniqueLock
provides. This is the version I used in TypeScript's experimentation with shared structs: https://github.com/microsoft/TypeScript/blob/shared-struct-test/src/compiler/threading/uniqueLock.ts
The API I've been discussing with the V8 teams at Google and Microsoft looks something like this:
type Lockable = Mutex; // `| SharedMutex` or others in the future
class UniqueLock<T extends Lockable> {
constructor(mutex?: Lockable, t: "lock" | "defer-lock" | "try-to-lock" | "adopt-lock" = "lock");
get mutex(): Lockable | undefined;
get ownsLock(): boolean;
tryLock(): boolean; // try to lock the mutex. non-blocking
lock(): void; // lock the mutex (possibly with a timeout?). blocking
lockAsync(): Promise<void>; // locks the mutex asynchronously. non-blocking
unlock(): void; // unlocks the mutex
release(): void; // detach the mutex without unlocking
swap(other: UniqueLock<T>): void; // swap state with another mutex
move(): UniqueLock<T>; // create a new lock with this lock's state, releasing this lock
[Symbol.dispose](): void; // unlock mutex and release the lock if it is taken.
}
Examples:
// take lock synchronously (off UI thread)
{
using lck = new UniqueLock(mut);
} // lock released
// take lock asynchronously (on UI thread)
{
using lck = new UniqueLock(mut, "defer-lock");
await lck.lockAsync();
}
// try to take lock (on or off UI thread) 1/2
{
using lck = new UniqueLock(mut, "try-to-lock");
if (lck.ownsLock) {
...
}
}
// try to take lock (on or off UI thread) 2/2
{
using lck = new UniqueLock(mut, "defer-lock");
if (lck.tryLock()) {
...
}
}
// take, release, and retake lock (off UI thread)
{
using lck = new UniqueLock(mut);
// has lock
lck.unlock();
// does not have lock
lck.lock();
// has lock again
}
// adopt an existing lock, such as when bootstrapping an application started from another
// short-lived thread that is no longer participating in coordination.
{
const lck1 = new UniqueLock(mut, "adopt-lock"); // adopts lock that was already taken
lck1.ownsLock; // true
}
// swapping locks
{
using lck1 = new UniqueLock();
{
using lck2 = new UniqueLock(mut);
...
lck1.ownsLock; // false
lck1.mutex; // undefined
lck2.ownsLock; // true
lck2.mutex; // [object Mutex]
lck1.swap(lck2);
lck1.ownsLock; // true
lck1.mutex; // [object Mutex]
lck2.ownsLock; // false
lck2.mutex; // undefined
}
}
And if/when we later add a SharedMutex
for read/write locks, you use UniqueLock
for readers and a SharedLock
for writers.
By having UniqueLock
be a non-shared, local JS object it cannot leak into other threads, while Mutex
remains a shared object and is possibly otherwise opaque to consumers. In addition, we can introduce other locking mechanisms later, such as a ScopedLock
that implements a deadlock prevention algorithm when you need to acquire locks for multiple resources and want to avoid deadlocks.
Unfortunately, a simple mutex.lock()
with a dispose
is not sufficient for many of the use cases that we actually need locking for. The above design keeps concerns properly separated and provides the flexibility needed to build more complex coordination mechanisms and deadlock prevention algorithms.
Can you give examples of cases for which the mutex.lock()
design is not sufficient?
Can you give examples of cases for which the
mutex.lock()
design is not sufficient?
I gave a number of examples, above. While fairly simplistic, they do illustrate a number of real-world uses of std::unique_lock
from C++ that I found compelling while working with the dev trial.
Also, something like ScopedLock
can implement deadlock prevention fairly efficiently in terms of UniqueLock
. The only reason I'm not using it in the version of ScopedLock
I linked to above is because it's using some internal wrappers around Atomics.Mutex
as the dev trial did not contain a UniqueLock
or other mechanism that was compatible with using
.
Sorry, I meant example use cases. Things you're trying to do with the more complicated API, not just how you call it.
Of the above API examples, swap
and move
are probably the least useful. The most useful being lock
/lockAsync
, tryLock
, unlock
, release
, and [Symbol.dispose]
(which combines unlock()
and release()
) which all have very relevant use cases.
The use cases for lock
/lockAsync
and [Symbol.dispose]
should be fairly obvious and are equally as relevant to UniqueLock
and mutex.lock()
designs. tryLock()
is highly useful for fast and efficient spin-locking, and when coupled with unlock()
can be used to implement low-overhead scoped locking across multiple mutexes with deadlock prevention.
Let's imagine, for the moment, that Mutex
had an API like this:
interface Mutex {
lock(): Disposable;
lockAsync(): Promise<Disposable>;
tryLock(): Disposable | undefined;
}
To implement a multi-mutex lock with deadlock prevention, like ScopedLock
, you might do something like this:
/**
* @param {Iterable<Mutex>} mutexes
* @returns {Disposable}
*/
export function lockAll(mutexes) {
mutexes = Array.from(mutexes);
let locks = new Array(mutexes.length);
let remaining = mutexes.length;
let index = 0;
let error;
let hasError = false;
while (!hasError) {
try {
if (remaining === 0) {
// all locks taken, return a disposable to release them later
const scope = new DisposableScope();
for (const lock of locks.slice(index)) {
scope.use(lock);
}
for (const lock of locks.slice(0, index)) {
scope.use(lock);
}
return scope;
}
if (remaining === mutexes.length) {
// always wait for the first lock
locks[index] = mutexes[index].lock(); // NOTE: lock token allocation
}
else {
locks[index] = mutexes[index].tryLock(); // NOTE: lock token allocation
if (!locks[index]) {
// failed to take lock. release each token and start over at the current index
let i = (index + mutexes.length - 1) % mutexes.length;
while (remaining < mutexes.length) {
// always unlock all locks taken, even if one unlock fails for some reason
try {
locks[i]?.[Symbol.dispose](); // NOTE: lock token release
locks[i] = undefined;
}
catch (e) {
error = error ? new SuppressedError(e, error) : e;
hasError = true;
}
i = (index + mutexes.length - 1) % mutexes.length;
remaining++;
}
continue;
}
// lock was taken, move to next mutex
index = (index + 1) % mutexes.length;
remaining--;
}
}
catch (e) {
error = error ? new SuppressedError(e, error) : e;
hasError = true;
}
}
// if we reach this point, an error occurred. unlock all locks taken in reverse order and throw the error
let i = (index + mutexes.length - 1) % mutexes.length;
while (remaining < mutexes.length) {
// always unlock all locks taken, even if one unlock fails for some reason
try {
locks[i]?.[Symbol.dispose]();
}
catch (e) {
error = new SuppressedError(e, error);
}
i = (index + mutexes.length - 1) % mutexes.length;
remaining++;
}
throw error;
}
This algorithm steps through all of the provided mutexes, locking each one in order. We only use lock
for the first mutex, and use tryLock
for subsequent mutexes to avoid a deadlock. If we fail to take a subsequent lock, we must rewind all of the taken locks and start over. When we restart, we restart the process starting at the current index since that is the lock that was in contention.
The downside of this approach is that there is overhead for producing and releasing new disposable lock tokens when there is significant contention. Even though these are nursery objects, that means they are cheap, not free. This is unfortunate because in the ideal scenario, all of the locks we take are expected to at least outlive the function call.
Here is the same algorithm utilizing UniqueLock
, tryLock
, and unlock
:
/**
* @param {Iterable<Mutex>} mutexes
* @returns {Disposable}
*/
export function lockAll(mutexes) {
const locks = Array.from(mutexes, mutex => new UniqueLock(mutex, "defer-lock")); // all allocations occur once
let remaining = locks.length;
let index = 0;
let error;
let hasError = false;
while (!hasError) {
try {
if (remaining === 0) {
// all locks taken, return a disposable to release them later
const scope = new DisposableScope();
for (const lock of locks.slice(index)) {
scope.use(lock);
}
for (const lock of locks.slice(0, index)) {
scope.use(lock);
}
return scope;
}
if (remaining === locks.length) {
// always wait for the first lock
locks[index].lock(); // NOTE: no allocation
}
else {
if (!locks[index].tryLock()) { // NOTE: no allocation
// failed to take lock. release each token and start over at the current index
let i = (index + locks.length - 1) % locks.length;
while (remaining < locks.length) {
// always unlock all locks taken, even if one unlock fails for some reason
try {
locks[i].unlock(); // NOTE: no release
}
catch (e) {
error = error ? new SuppressedError(e, error) : e;
hasError = true;
}
i = (index + locks.length - 1) % locks.length;
remaining++;
}
continue;
}
// lock was taken, move to next mutex
index = (index + 1) % locks.length;
remaining--;
}
}
catch (e) {
error = error ? new SuppressedError(e, error) : e;
hasError = true;
}
}
// if we reach this point, an error occurred. unlock all locks taken in reverse order and throw the error
let i = (index + locks.length - 1) % locks.length;
while (remaining < locks.length) {
// always unlock all locks taken, even if one unlock fails for some reason
try {
locks.unlock();
}
catch (e) {
error = new SuppressedError(e, error);
}
i = (index + locks.length - 1) % locks.length;
remaining++;
}
throw error;
}
Here, there is no overhead from object allocation and release during high contention. All of the locks that will eventually outlive the function are allocated all at once.
I see. I agree that the object allocations in that specific algorithm are unfortunate, though I would want to hear from an engine that this matters in practice before committing to a more complex design just to avoid these allocations.
In any case, if the goal was just "avoid allocations in the above algorithm", that would be more simply accomplished by making mutex.lock
/mutex.tryLock
accept an optional release
d token which it would then re-lock and return, as in
using token = mutex.lock();
//...
token.release();
// ...
mutex.lock(token);
You would then implement the above algorithm by changing your first implementation as follows:
- locks[index] = mutexes[index].lock();
+ locks[index] = mutexes[index].lock(locks[index]);
- locks[index] = mutexes[index].tryLock();
- if (!locks[index]) {
+ let lock = mutexes[index].tryLock(mutexes[index]);
+ if (lock) { mutexes[index] = lock; /* only does anything the first time through */ }
+ else {
- locks[i] = undefined;
That seems much simpler than the UniqueLock
API.
I'm not sure I would agree that is simpler. The mechanics of what you're describing add a lot more moving parts and complex interactions to reason over and a fair amount of back and forth. It's certainly not straightforward.
What I am suggesting isn't complex. You have the mutex, which is purely shared state, and the lock, which is the thread-local mechanism to interact with that state. Everything you want to do to interact with the Mutex is on the lock object:
The UniqueLock
is the resource you hold, and initializing the resource as part of using
is the closest application of RAII there is.
In addition, we'd likely change Condition.wait
to take the lock (the thing that actually has both lock
/unlock
) rather than the mutex itself, as that is a far clearer separation of concerns.
IMO, UniqueLock
is a very clean and consistent API and is extremely flexible.
In your design, locking a mutex is done by creating a separate object (the creation of which may or may not lock the mutex, depending on a four-state enum argument to the constructor) and/or by calling a method on the separate object. Async locking is necessarily two steps because new
cannot be async. The separate object may or may not remain associated with that mutex and there are several methods for juggling this.
In my design, locking a mutex is always done by calling a method on the mutex, which creates or updates a token. Async locking looks exactly like sync locking, just calling the async API instead of the sync API and adding an await
. The token has no capabilities at all except the ability to unlock while it is the result of the most recent locking.
If there's some reason to want the extra complexity of UniqueLock
, I'm happy to have that conversation. But the UniqueLock
design is definitely more complex and has more moving parts. I don't think that's arguable.
The design I've proposed incidentally is quite close to the design in Rust. Indeed if you consider using
equivalent to dropping an object in Rust, it's nearly identical. I think we should generally prefer taking our cues from Rust rather than C++.
The readme mentions a possible integration with explicit resource management. It suggests adding
mutex.lock
andmutex.unlock
and making mutexes disposable. I think the latter two points are wrong, and the correct API would look like this:i.e.,
mutex.lock
returns an object with aSymbol.dispose
method and a string-namedunlock
method (as an alias ofdispose
), rather than the mutex being disposable. This makes it impossible to accidentally unlock the mutex without first locking it.The tokens need not be shared objects (
though I guess they could be, if that's easy to do). Edit: Actually, on talking this over, probably the ideal is for the tokens to be cloneable, in the sense of having explicit support instructuredClone
, but not be shared objects.cc @michaelficarra @lucacasonato