Fix performance degradation of contended LWLock on NUMA

Good day, everyone.

This patch improves performance of contended LWLock.
It was tested on 4 socket 72 core x86 server (144 HT) Centos 7.1
gcc 4.8.5

Results:

pgbench -i -s 300 + pgbench --skip-some-updates
Clients | master | patched
========+=========+=======
30 | 32k | 32k
50 | 53k | 53k
100 | 102k | 107k
150 | 120k | 131k
200 | 129k | 148k
252 | 121k | 159k
304 | 101k | 163k
356 | 79k | 166k
395 | 70k | 166k
434 | 62k | 166k

pgbench -i -s 900 + pgbench
Clients | master | patched
========+=========+=======
30 | 31k | 31k
50 | 50k | 49k
100 | 75k | 78k
150 | 92k | 96k
200 | 87k | 106k
252 | 69k | 108k
304 | 55k | 110k
356 | 48k | 110k
395 | 44k | 108k
434 | 40k | 109k

I could not claim read-only benchmarks are affected in any way: results
are unstable between postgresql restarts and varies in a same interval
for both versions. Although some micro-optimization were made to ensure
this parity.
Since investigations exist on changing shared buffers structure (by
removing LWLock from a buffer hash partition lock [1]), I stopped
attempts to gather more reliable statistic for readonly benchmarks.

[1] Takashi Horikawa "Don't stop the world"
https://www.pgcon.org/2017/schedule/events/1078.en.html

Also, looks like patch doesn't affect single NUMA node performance
significantly.

postgresql.conf is tuned with following parameters:
shared_buffers = 32GB
max_connections = 500
fsync = on
synchronous_commit = on
full_page_writes = off
wal_buffers = 16MB
wal_writer_flush_after = 16MB
commit_delay = 2
max_wal_size = 16GB

Patch changes the way LWLock is acquired.

Before patch, lock is acquired using following procedure:
1. first LWLock->state is checked for ability to take a lock, and CAS
performed (either lock could be acquired or not). And it is retried if
status were changed.
2. if lock is not acquired at first 1, Proc is put into wait list, using
LW_FLAG_LOCKED bit of LWLock->state as a spin-lock for wait list.
In fact, profile shows that LWLockWaitListLock spends a lot of CPU on
contendend LWLock (upto 20%).
Additional CAS loop is inside pg_atomic_fetch_or_u32 for setting
LW_FLAG_HAS_WAITERS. And releasing wait list lock is another CAS loop
on the same LWLock->state.
3. after that state is checked again, because lock could be released
before Proc were queued into wait list.
4. if lock were acquired at step 3, Proc should be dequeued from wait
list (another spin lock and CAS loop). And this operation could be
quite heavy, because whole list should be traversed.

Patch makes lock acquiring in single CAS loop:
1. LWLock->state is read, and ability for lock acquiring is detected.
If there is possibility to take a lock, CAS tried.
If CAS were successful, lock is aquired (same to original version).
2. but if lock is currently held by other backend, we check ability for
taking WaitList lock. If wait list lock is not help by anyone, CAS
perfomed for taking WaitList lock and set LW_FLAG_HAS_WAITERS at once.
If CAS were successful, then LWLock were still held at the moment wait
list lock were held - this proves correctness of new algorithm. And
Proc is queued to wait list then.
3. Otherwise spin_delay is performed, and loop returns to step 1.

So invariant is preserved:
- either we grab the lock,
- or we set HAS_WAITERS while lock were held by someone, and queue self
into wait list.

Algorithm for LWLockWaitForVar is also refactored. New version is:
1. If lock is not held by anyone, it immediately exit.
2. Otherwise it is checked for ability to take WaitList lock, because
variable is protected with it. If so, CAS is performed, and if it is
successful, loop breaked to step 4.
3. Otherwise spin_delay perfomed, and loop returns to step 1.
4. var is checked for change.
If it were changed, we unlock wait list lock and exit.
Note: it could not change in following steps because we are holding
wait list lock.
5. Otherwise CAS on setting necessary flags is performed. If it succeed,
then queue Proc to wait list and exit.
6. If Case failed, then there is possibility for LWLock to be already
released - if so then we should unlock wait list and exit.
7. Otherwise loop returns to step 5.

So invariant is preserved:
- either we found LWLock free,
- or we found changed variable,
- or we set flags and queue self while LWLock were held.

Spin_delay is not performed at step 7, because we should release wait
list lock as soon as possible.

Additionally, taking wait list lock is skipped in both algorithms if
SpinDelayStatus.spins is less than part of spins_per_delay loop
iterations (so, it is initial iterations, and some iterations after
pg_usleep, because SpinDelayStatus.spins is reset after sleep). It
effectively turns LWLock into spinlock on low contended case. It was
made because unpatched behaviour (test-queue-retest-unqueue) is already
looks like cutted spin, and shows on "contended but not much" load
sometimes better performance against patch without "spin". Also, before
adding "spin" top performance of patched were equal to top performance
of unpatched, it just didn't degrade.
(Thanks to Teodor Sigaev for suggestion).

Patch consists of 6 commits:
1. Change LWLockWaitListLock to have function-wide delayStatus instead
of local to atomic_read loop. It is already gives some improvement,
but not too much.
2. Refactor acquiring LWLock.
3. Refactor LWLockWaitForVar. Also, LWLockQueueSelf and
LWLockDeququeSelf are removed because they are not referenced since
this commit.
4. Make LWLock to look more like spin lock.
5. Fix comment about algorithm.
6. Make initialization of SpinDelayStatus lighter, because it is on a
fast path of LWLock.

As I couild understand, main benefit cames from XLogInsertLock,
XLogFlushLock and CLogControlLock. XLogInsertLock became spin-lock on
most cases, and it was remarkable boost to add "spin" behaviour to
LWLockWaitForVar because it is used in checking that xlog already
flushed till desired position. Other locks just stop to degrade on high
load.

Patch conflicts with LWLock optimization for Power processors
https://commitfest.postgresql.org/14/984/
Alexandr Korotkov (my chief) doesn't mind if this patch will be
accepted first, and Power will be readdressed after.

PS.
For SHARED lock `skip_wait_list = spins_per_delay / 2;` . Probably it is
better to set it to more conservative `spins_per_delay / 4`, but I have
no enough evidence in favor of either decision.
Though it is certainly better to have it larger, than
`spins_per_delay / 8` that is set for EXCLUSIVE lock.

With regards,
--
Sokolov Yura aka funny_falcon
Postgres Professional: https://postgrespro.ru
The Russian Postgres Company