From e6e1e8b2f876dc122f28fb565643108ed90bebfb Mon Sep 17 00:00:00 2001 From: Alexandre Felipe Date: Tue, 6 Oct 2026 07:56:55 +0100 Subject: [PATCH-v1 2/2] introduce LWLockAligned Currently the main LWLocks has some individual LWLocks, and some partitioned LWLocks that consists on an array of LWLocks that protect partitions of a hash table. Given that a hash table having B buckets and P partitions, and access pattern roughly uniform per bucket, each partition will have B/P, buckets and will control a fraction 1/P of the accesses, instead of having on lock for the hash entire hash table. Currently all the LWLocks are padded to prevent cache-line contention between different locks. LWLockPadded[N] [ 00 -- -- -- -- ] [ 01 -- -- -- -- ] [ 02 -- -- -- -- ] ... This prevents false-sharing, however with the same amount of memory, more locks could be allocated with reduced padding, by choosing a divisor of the cache line size, it is guaranteed that only one cache line will be touched by any lock. Let S = sizeof(LWLockPadded) / sizeof(LWLockAligned), we can arrange S locks per cache-line. LWLockAligned [ 01 02 03 04 ] [ 05 06 07 08 ] [ 09 0a 9b 0c ] ... Although this allocation would increase cache line contention if applied to unrelated LWLock, for partition LWLock, having P cache-lines, each holding S LWLocks and L LWLockAcquire/LWLockRelease uniformly distributed over the partitions, each LWLock will be acquired L / (P * S) times, and each cache line will serve S * (L / (P * S)) = L / P operations. In plain English, the number of times a lock in a given cache-line is used is independent of S. So, packing more locks in one cache line makes no difference, right? Wrong! Notice that the number of operations per LWLock, is L / (P * S) LW_EXCLUSIVE Concurrency ======================== For simplicity consider a single cache line, having S locks, and L tasks requiring exclusive locks uniformly distributed over the partitions. The concurrency will be roughly S, i.e. with S=1, only one backend will be working at a time, having S=4, up to 4 backends can be working at a time. LW_EXCLUSIVE Waits ================== Consider a LW_EXCLUSIVE lock waiting for LW_SHARED to drain, to model that let's say that shared locks have a poisson distribution and on average $\lambda$ shared locks are in place. The probability of a successful LW_EXCLUSIVE acquisition is $e^{-\lambda}`, after going to sleep it will take on average $\lambda e^{\lambda}$ to be awakened, and once awakened it will again succed with probability $e^{-\lambda}$, because by the time it wakes up and attempt the lock it might have been acquired again. Having S partitions will reduce the average LW_SHARED locks taken, so the impact will be on the exponent. LW_SHARED Waits =============== A LW_SHARED will have wait if a single LW_EXCLUSIVE lock is taken, having S partitions instead of 1 means makes reduces the number of backends put to sleep is reduced by a factor S. LWLockWaitListLock ================== This is a spin lock, having one waiting process also makes every othe accesses on the cache line slow. QueueSelf will touch the LWLock multiple times while holding the spin-lock a waiting process invalidating the cache-line exclusive access of the holder, could make the operation one or two orders of magnitude slower. CAS Loop ======== The main concern about this design would be having multiple backends acquiring different locks held by the same cache-line. The argument for increasing S is that if another backend is touching the same cache line on a different lock, with S=1 it would also be touching the it. So the analysis left to do is, whether it is preferrable to have a concurrent access on the same lock or on a different lock. Having concurrent access on a different lock doesn't cause a CAS retry. Concurrent access on the same lock will cause a retry even if the relevant bits didn't change, e.g. LWLockRelease while trying to acquire a shared lock, would decrease the lock counter causing the CAS to retry. The same goes for LWLockWaitListLock, or concurrent LWLockAttempt. So it is definitely better to have multiple partition locks in the same cache line than a single lock in the cache line. --- .../storage/lmgr/generate-lwlocknames.pl | 2 +- src/include/pg_config_manual.h | 1 + src/include/storage/lwlock.h | 45 ++++++++++++++----- 3 files changed, 37 insertions(+), 11 deletions(-) diff --git a/src/backend/storage/lmgr/generate-lwlocknames.pl b/src/backend/storage/lmgr/generate-lwlocknames.pl index 48fa2807b2b..0538a2cb010 100644 --- a/src/backend/storage/lmgr/generate-lwlocknames.pl +++ b/src/backend/storage/lmgr/generate-lwlocknames.pl @@ -130,7 +130,7 @@ while (<$lwlocklist>) $lastlockidx = $lockidx; # Add a "Lock" suffix to each lock name, as the C code depends on that. - printf $h "#define %-32s (&MainLWLockArray[$lockidx].lock)\n", + printf $h "#define %-32s (&MainLWLocks->individual[$lockidx].lock)\n", $lockname . "Lock"; next; diff --git a/src/include/pg_config_manual.h b/src/include/pg_config_manual.h index 521b49b8888..eb4d253860e 100644 --- a/src/include/pg_config_manual.h +++ b/src/include/pg_config_manual.h @@ -214,6 +214,7 @@ * The default is 128, which should be large enough for all supported * platforms. */ +#define PG_LOG2_CACHE_LINE_SIZE 7 #define PG_CACHE_LINE_SIZE 128 /* diff --git a/src/include/storage/lwlock.h b/src/include/storage/lwlock.h index f1afaf894fe..2e7f669bf50 100644 --- a/src/include/storage/lwlock.h +++ b/src/include/storage/lwlock.h @@ -61,9 +61,19 @@ typedef struct LWLock */ #define LWLOCK_PADDED_SIZE PG_CACHE_LINE_SIZE +#ifdef LOCK_DEBUG +#define LOG2_LWLOCK_ALIGNED_SIZE 5 +#else +#define LOG2_LWLOCK_ALIGNED_SIZE 4 +#endif +#define LWLOCK_ALIGNED_SIZE (1 << LOG2_LWLOCK_ALIGNED_SIZE) + StaticAssertDecl(sizeof(LWLock) <= LWLOCK_PADDED_SIZE, "Miscalculated LWLock padding"); - +StaticAssertDecl(sizeof(LWLock) <= LWLOCK_ALIGNED_SIZE, + "Miscalculated LWLock alignment"); +StaticAssertDecl(LWLOCK_ALIGNED_SIZE < 2 * sizeof(LWLock), + "Wasteful LWLock alignment"); /* LWLock, padded to a full cache line size */ typedef union LWLockPadded { @@ -71,23 +81,38 @@ typedef union LWLockPadded char pad[LWLOCK_PADDED_SIZE]; } LWLockPadded; +typedef union LWLockAligned +{ + LWLock lock; + char pad[LWLOCK_ALIGNED_SIZE]; +} LWLockAligned; + /* * It's a bit odd to declare NUM_BUFFER_PARTITIONS and NUM_LOCK_PARTITIONS * here, but we need them for the definition of MainLWLockStruct, and * having this file include lock.h or bufmgr.h would be backwards. */ + +#define LWLOCK_NUM_PARTITIONS(group) \ + (1 << LOG2_NUM_##group##_PARTITIONS) +#define LWLOCK_NUM_PARTITION_BITS(group) \ + (LOG_NUM_##group##_CACHE_LINES + PG_LOG2_CACHE_LINE_SIZE - LOG2_LWLOCK_ALIGNED_SIZE) + /* Number of partitions of the shared buffer mapping hashtable */ -#define LOG2_NUM_BUFFER_PARTITIONS 7 -#define NUM_BUFFER_PARTITIONS (1 << LOG2_NUM_BUFFER_PARTITIONS) +#define LOG2_NUM_BUFFER_CACHE_LINES 7 +#define LOG2_NUM_BUFFER_PARTITIONS LWLOCK_NUM_PARTITION_BITS(BUFFER) +#define NUM_BUFFER_PARTITIONS LWLOCK_NUM_PARTITIONS(BUFFER) /* Number of partitions the shared lock tables are divided into */ -#define LOG2_NUM_LOCK_PARTITIONS 4 -#define NUM_LOCK_PARTITIONS (1 << LOG2_NUM_LOCK_PARTITIONS) +#define LOG2_NUM_LOCK_CACHE_LINES 4 +#define LOG2_NUM_LOCK_PARTITIONS LWLOCK_NUM_PARTITION_BITS(LOCK) +#define NUM_LOCK_PARTITIONS LWLOCK_NUM_PARTITIONS(LOCK) /* Number of partitions the shared predicate lock tables are divided into */ -#define LOG2_NUM_PREDICATELOCK_PARTITIONS 4 -#define NUM_PREDICATELOCK_PARTITIONS (1 << LOG2_NUM_PREDICATELOCK_PARTITIONS) +#define LOG2_NUM_PREDICATELOCK_CACHE_LINES 4 +#define LOG2_NUM_LOCK_PARTITIONS LWLOCK_NUM_PARTITION_BITS(PREDICATELOCK) +#define NUM_PREDICATELOCK_PARTITIONS LWLOCK_NUM_PARTITIONS(PREDICATELOCK) /* * Built-in LWLocks in shared memory. Extension locks requested with @@ -96,9 +121,9 @@ typedef union LWLockPadded typedef struct MainLWLockStruct { LWLockPadded individual[NUM_INDIVIDUAL_LWLOCKS]; - LWLockPadded buffer_mapping[NUM_BUFFER_PARTITIONS]; - LWLockPadded lock_manager[NUM_LOCK_PARTITIONS]; - LWLockPadded predicate_lock_manager[NUM_PREDICATELOCK_PARTITIONS]; + LWLockAligned buffer_mapping[NUM_BUFFER_PARTITIONS]; + LWLockAligned lock_manager[NUM_LOCK_PARTITIONS]; + LWLockAligned predicate_lock_manager[NUM_PREDICATELOCK_PARTITIONS]; LWLockPadded extra[FLEXIBLE_ARRAY_MEMBER]; } MainLWLockStruct; -- 2.53.0