Possible Web Locks deadlock

[rhashimoto]

There is a potential deadlock in src/examples/WebLocks.js as described here. xLock() is supposed to timeout to prevent this but the current implementation does not.

[rhashimoto]

This is a trickier issue than I initially thought. When SQLite returns SQLITE_BUSY to the application, which it does when the VFS returns SQLITE_BUSY from xLock(), the application has to decide how to handle that. It can retry the same statement again, but this will end up in the same blocked state if that statement is part of a multi-statement transaction and the contention is with another multi-statement transaction that is also being stubbornly retried. In this case, all but one of the participants must ROLLBACK and retry the transaction in its entirety, which allows the remaining participant to complete its transaction.

Ideally we want to return SQLITE_BUSY to all the participants in the deadlock except one. That is doable because we can identify the connection that has made the most progress toward getting the exclusive lock and return SQLITE_BUSY to all the others. Now who is responsible for doing the ROLLBACK and retry part, the library or the application?

SQLite's policy is to have the application keep track of its transactions instead of caching them and doing retry automatically so it makes sense for wa-sqlite to do the same thing. We don't know what other code the application might be running alongside the transaction statements that also would need to be replayed so making the application responsible for rewinding everything seems best for now (maybe in the future there could be an API "transaction" call that takes an idempotent function argument). That does make application development when there is potential concurrency a little bit harder, which is unfortunate.

So what I'm going to do is change the default WebLocks.js to use only exclusive locking, which removes that deadlock possibility. This will remove the need for applications to handle SQLITE_BUSY at the cost of not allowing concurrent read transactions (they will be executed sequentially). I will add an alternative WebLocksShared.js that is a drop-in replacement that does allow concurrent read transactions for applications that are willing to handle SQLITE_BUSY.

An implementation note: We can do better than a timeout for WebLocksShared. We just need to distinguish when we can't get a RESERVED lock because someone else already has it versus because someone is just getting a SHARED lock. We can do that by adding another lock and polling it with LockManager.query() - it will really be used as a signal instead of as a lock (it won't block anything).

[rhashimoto]

Completed as described.