Re: Adding REPACK [concurrently]

Hello, Antonin!

I've briefly looked at your patch. As I understand it, it cancels the
other process only when REPACK actually tries to upgrade the lock. In
that sense, its approach is close to my variant at [0].

AFAIU, Andres's concern is that the "victim" should be cancelled
sooner, rather than waiting until REPACK actually attempts the
upgrade. I was trying to solve it by
[1].

-------------------------------

There are some comments on [1]:

Some details related to POC from previous letter (once I re-read that
in the morning I relized it is not so easy to understand, sorry).

So, goal of patch to:
* make sure REPACK will survive deadlock which may caused by lock upgrade
* reject some other backend with error early than deadlock really
occur - to avoid pointless waiting for other commands
* implement it at deadlock detector level to correctly handle
different 2+ backend-involved scenarious

To achive it the first idea is to add some kind of "future lock"
(FutureWaitLock). It may declare an intention to acquire a lock of a
certain level as high-priority in the future.
Once deadlock detector starts to walking graph it treat that intention
like an actual "waiting".
That way deadlock detector looks for one more step in the future -
moment of actual acquiring the "future" lock - and if it ends with
cycle - reject waiting backend ("future deadlock detected").

Looks like best place to put that FutureWaitLock is PGPROC itself.

Few moments to consider:
* it is not allowed to declare a future lock if backend already holds
some kind of lock for the same tag (this may cause a race condition).
* so, REPACK first declares future Access Excluvie and only after it
Share Update Exclusive
* declared future lock should be >= SUE

So far everything looks good.

In case of that scenario:

S1: BEGIN; SELECT * FROM t;
S2: REPACK (CONCURRENTLY) t;
S1: LOCK TABLE t in ACCESS EXCLUSIVE MODE <--- "future deadlock detected"

Deadlock detector sees:

S1 ----> S2 (waiting for AE conflicting with SUE)
S2 ----> S1 (future wait for AE conflict with current Access Share)

But there is a tricky case related to SUE:

S1: BEGIN; SELECT * FROM t;
S2: REPACK (CONCURRENTLY) t;
S1: LOCK TABLE t in SHARE UPDATE EXCLUSIVE MODE;

In that case we have almost the same deadlock scenario - but that is
not visible to deadlock detector.
It happens because SUE does not force all locks taken on 't' to be
transfered using FastPathTransferRelationLocks into the main table
(SUE is does not ConflictsWithRelationFastPath).
Because of it S2 -> S1 edge is not visible by deadlock detector
(Access Share is held using fast-path).

To deal with it we may force any relation with FutureWaitLock to
through slow-path locking - but I don't think it is acceptable.

Instead next approach is proposed:

* deadlock detector checks if any "future" locks are present in the
system (counter in shared memory)
* if so - it iterates over all PROCs to collect relations which are
"future locked"
* for each such relations - FastPathTransferRelationLocks called and
slow-path is forced (FastPathStrongRelationLocks->count)
* deadlock detector start looking for cycles
* once ready - FastPathStrongRelationLocks->count is decremented to
allow fast-path

That way performance degradation happens only during deadlock detector
processing and only if some future locks present.

Due tue LW ordering we need to use some tricks to avoid LW-level
deadlocks (using some kind of retry logic, but that is more explained
in the patch).

[0]: https://www.postgresql.org/message-id/flat/CADzfLwURKVNQ%2B%2BDpi7bjoGfj-8pchDQEVex3eWBx0NCYn6TbDQ%40mail.gmail.com#bceb18354aa20c130a94b1deedd76fb7.

[1}] postgresql.org/message-id/flat/CADzfLwU8Qw6LXFHO7Tbjc-O7o%2BtM26jdnOJBWqYLu61rf7bO%2Bg%40mail.gmail.com#1e96f8882363afb2fc53c2f08346f527