Deadlock detection and resolution?

[alvestrand]

If two processes execute

await navigator.locks.acquire('A', async lock => {
await navigator.locks.acquire('B')
})

and

await navigator.locks.aquire('B', async lock => {
await navigator.locks.acquire('A')
})

standard processing theory says that they will sooner or later end up in a sad state (deadlock).

1. can we detect this?
2. can we resolve this?

On the detection side, it worries me slightly that the lock snapshot state doesn't identify holders in any way; there's no way to differentiate between "X holds A and Y holds B" and "X holds A and B, Y waits for A and B".

[inexorabletash]

The naive answer is of course: that's a bug in the web app, which should be coded to avoid deadlocks, e.g. by always requesting multiple locks in a strict order. (See #20). But yeah, what further assistance can we provide...

As noted, even a web app that is defending against its own bugs can't tell by state inspection what is holding the locks/making the requests; logging the query() snapshot to the server may not provide enough to debug. Ideas that come to mind: (1) allowing apps to specify an arbitrary identifier with each request which is reflected in the snapshot, (2) including a the user-agent assigned id in the snapshot. I don't think we expose the latter outside of SWs at the moment, so it wouldn't correlate with much, although it would at least show that A and B are held by/requested by different contexts, thus clearly showing the deadlock.

[alvestrand]

I think it's inevitable that locks will be used inside libraries.

A side effect of "a lock is a name" is that the system has no idea what locks can exist - so some library can always use an internal lock that would fit in lexical order in a surprising way - so there's no way for the browser to predict what locks are going to exist, which defeats most schemes for avoiding deadlock.

What I'd like to see is:
a) a part of the spec that talks about the danger of deadlocks, and that acquisition in some hierarchical order and not holding them longer than required are both Good Practices - won't prevent them, but will at least warn the users that they should google the word "deadlock" when their app stops suddenly and mysteriously :-)
b) a part of the spec that allows diagnostics. Including a context ID in the lock listing (I'd go for an internally generated one - don't burden the simple use cases with managing an ID space, and don't let the user shoot themselves in the foot by having two contexts with the same name) seems like a good start.

[inexorabletash]

re: spec/deadlocks - absolutely, everything you listed is awesome. I'm signing you up to review it when written. :)

re: diagnostics - In theory, including the context's environment id would be straightforward (one more thing plumbed through from request). @domenic - is this a reasonable use of that data?

(In Blink's implementation, it looks like we currently mint the client ID as a UUID in the "service worker host" i.e. a SW-specific bit of code associated with each client (a.k.a. agent), rather than actually having something that multiple services could easily share. I.e. some refactoring would be needed, but that's not a spec problem.)

[domenic]

I don't know much about environment ID; I think it was added for service workers. @jungkees or maybe @annevk would be able to help understand that better. Although I guess you figured most of it out by digging through the Blink code :)

[inexorabletash]

Took a stab at adding clientId to the snapshot in the proto-spec.

I have an implementation/tests in blink (up for review shortly) that adds the property, although it mints the ids on its own (like serviceworker).

[inexorabletash]

Closing this for now - I added a section to the explainer (README) about deadlocks; everything in the explainer should end up in the eventual spec so that'll be the seed.

Thanks @alvestrand !