Re: Spinlocks, yet again: analysis and proposed patches

Is there a TODO here?

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

Tom Lane wrote:
> The test case I just posted shows that our spinlock code, which we had
> thought largely done, is once again becoming a performance bottleneck.
> It's time to resurrect some of the ideas we kicked around in early
> 2002, and didn't pursue because we decided spinlocks weren't our major
> performance problem.
>
> I started investigating this by trying to understand why the "futex
> spinlock" patch had helped the Red Hat customer I mentioned, when it
> hadn't done anything much in last year's experiments. It turns out
> that this customer was using an 8-way Opteron, and the futex patch
> helps a lot more on that architecture than others. Some random
> experimentation eventually turned up part of the reason: the x86 TAS
> assembly code we are using is pessimal for x86_64. Specifically,
> s_lock.h uses this for both architectures:
>
> /* Use a non-locking test before asserting the bus lock */
> __asm__ __volatile__(
> " cmpb $0,%1 \n"
> " jne 1f \n"
> " lock \n"
> " xchgb %0,%1 \n"
> "1: \n"
>
> and it turns out that deleting the cmpb and jne makes things go
> significantly faster on Opterons. So the "non-locking test" is
> not a win at all on x86_64. As best I can tell from testing,
> removing it wins because it causes the rate of spinlock delays
> to drop significantly. Why this should be is not completely
> obvious. I speculate that the Opterons are capable of pulling
> in a copy of the cache line that contains the spinlock and then
> running 100 iterations of the cmpb test without ever noticing
> that the processor holding the lock has now released it. Without
> the cmpb, they are forced by the locking xchgb test to actually
> look at the real state of the spinlock each time.
>
> I kinda suspect that the cmpb test is a no-op or loss on all
> Intelish processors: it can only be a win if you expect a lot
> of contention for the spin lock, but in percentage terms we still
> have a very low conflict rate, so in most executions of the TAS
> macro, the cmpb is just wasted cycles. Bottom line: we definitely
> don't want it for x86_64, and maybe not at all, but we need more
> research to decide the latter.
>
> The second reason that the futex patch is helping is that when
> a spinlock delay does occur, it allows the delaying process to be
> awoken almost immediately, rather than delaying 10 msec or more
> as the existing code does. However, given that we are only expecting
> the spinlock to be held for a couple dozen instructions, using the
> kernel futex mechanism is huge overkill --- the in-kernel overhead
> to manage the futex state is almost certainly several orders of
> magnitude more than the delay we actually want.
>
> I looked into several other methods of doing the spinlock delay
> instead. I think all of these were suggested at one point or
> another in our earlier discussions of spinlocks:
>
> 1. Use sched_yield() if available: it does just what we want,
> ie, yield the processor without forcing any useless time delay
> before we can be rescheduled. This doesn't exist everywhere
> but it exists in recent Linuxen, so I tried it. It made for a
> beautiful improvement in my test case numbers: CPU utilization
> went to 100% and the context swap rate to almost nil. Unfortunately,
> I also saw fairly frequent "stuck spinlock" panics when running
> more queries than there were processors --- this despite increasing
> NUM_DELAYS to 10000 in s_lock.c. So I don't trust sched_yield
> anymore. Whatever it's doing in Linux 2.6 isn't what you'd expect.
> (I speculate that it's set up to only yield the processor to other
> processes already affiliated to that processor. In any case, it
> is definitely capable of getting through 10000 yields without
> running the guy who's holding the spinlock.)
>
> 2. Reduce the length of the select() delays in s_lock. The current code
> delays in quanta of 10msec, but on recent Linuxen (and I think other
> platforms too) the scheduling quantum is 1msec, so we can get the
> processor back faster if we ask for a 1msec delay. I tried this and it
> is definitely a win on Linux; it doesn't seem to hurt anything on older
> systems either, they just round the delay up to 10msec like before.
> So I think we should do this, even though it's only a partial answer.
>
> 3. Modify the spin loop to do a little more work between TAS() tests.
> In the existing code there are only about half a dozen instructions
> total in the normal spin loop, most of them very fast, with the result
> that the spinning processor does its best to monopolize the system bus
> with locked probe instructions. This is obviously not good, as it'll
> interfere with the ability of the spinlock holder to complete its work
> and release the lock. (The bulk of the spinlock uses are for LWLocks,
> and with the current data structures the LWLock's own state is usually
> going to be in the same cache line as the spinlock proper, so that
> cache grabs for the spinlock hurt the LWLock state updating as well
> as the eventual spinlock release.) I modified the code to use an
> integer modulo operation as part of the test for SPINS_PER_DELAY;
> on most processors this should keep the processor's attention and
> keep it away from the system bus for several times longer than an
> average instruction. (It's relevant here that the "rep;nop" used
> to slow the spin loop on recent Intel processors appears to be
> completely ignored by Opterons. Basically we need a non-hardware-
> specific trick to slow the loop.)
>
> 4. Modify SPINS_PER_DELAY. Looping more times instead of entering the
> kernel is a win for SMP boxes: whenever you give up and call the kernel
> to delay, it's likely that the spinlock holder will have released the
> lock before you even get all the way into the kernel, let alone get
> rescheduled again. I found that pushing SPINS_PER_DELAY above 200
> caused the select delay rate to fall to almost nil in this test case.
> However, that would be counterproductive for uniprocessors where the
> optimal strategy is normally to give up the processor immediately.
> We've talked about making the spin count user configurable, but I never
> cared for that answer. Instead, I've worked up some code to
> automatically adjust the spin count depending on whether we seem to be
> in a uniprocessor or multiprocessor. The idea is to decrease the spin
> count (down to a lower limit) whenever s_lock has to delay in order to
> get a lock, and to increase the count (up to a limit) whenever we see
> the lock come free before we've had to delay. The former condition
> suggests that we are in a uniprocessor and the latter suggests we are in
> a multiprocessor. I recall having complained that this idea would
> probably be unstable, but in testing it seems to do pretty nicely at
> converging to the minimum spin count on a 1-CPU machine and the maximum
> limit on an SMP box. It could do with more testing though to see if it
> works the same for other people.
>
> My proposal therefore is to do #2, #3, and #4, and to modify the TAS
> assembly code at least on x86_64. Together, these changes bring
> my test case on a 4-way Opteron from
>
> N, runtime: 1 36s 2 61s 4 105s 8 198s
>
> to
>
> N, runtime: 1 35s 2 48s 4 58s 8 105s
>
> At 4 queries, CPU utilization is 100% and the context swap rate nearly
> nil, which seems to mean we've gained another (temporary no doubt)
> victory over the spinlock problem.
>
> I attach two proposed patches: the first removes the cmpb/jne from
> the x86 TAS assembly code, and the second one does the s_lock changes
> enumerated as points #2, #3, #4. The first one in particular needs
> more testing to see if it hurts performance on any non-Opteron x86
> chips. (If so, we'd just make it conditional to x86_64.)
>
> Comments and testing invited.
>
> regards, tom lane
>

Content-Description: slock-no-cmpb.patch

> *** REL8_0/src/include/storage/s_lock.h Sun Aug 28 20:41:44 2005
> --- new/s_lock.h Fri Sep 9 14:58:44 2005
> ***************
> *** 120,132 ****
> {
> register slock_t _res = 1;
>
> ! /* Use a non-locking test before asserting the bus lock */
> __asm__ __volatile__(
> - " cmpb $0,%1 \n"
> - " jne 1f \n"
> - " lock \n"
> " xchgb %0,%1 \n"
> - "1: \n"
> : "+q"(_res), "+m"(*lock)
> :
> : "memory", "cc");
> --- 120,128 ----
> {
> register slock_t _res = 1;
>
> ! /* xchg implies a LOCK prefix, so no need to say LOCK explicitly */
> __asm__ __volatile__(
> " xchgb %0,%1 \n"
> : "+q"(_res), "+m"(*lock)
> :
> : "memory", "cc");

Content-Description: spin-delay.patch

> *** /home/postgres/pgsql/src/backend/storage/lmgr/proc.c.orig Sat Aug 20 19:26:24 2005
> --- /home/postgres/pgsql/src/backend/storage/lmgr/proc.c Sun Sep 11 15:07:20 2005
> ***************
> *** 170,175 ****
> --- 170,177 ----
>
> ProcGlobal->freeProcs = INVALID_OFFSET;
>
> + ProcGlobal->spins_per_delay = DEFAULT_SPINS_PER_DELAY;
> +
> /*
> * Pre-create the PGPROC structures and create a semaphore for
> * each.
> ***************
> *** 224,232 ****
> --- 226,239 ----
> /*
> * Try to get a proc struct from the free list. If this fails, we
> * must be out of PGPROC structures (not to mention semaphores).
> + *
> + * While we are holding the ProcStructLock, also copy the current
> + * shared estimate of spins_per_delay to local storage.
> */
> SpinLockAcquire(ProcStructLock);
>
> + set_spins_per_delay(procglobal->spins_per_delay);
> +
> myOffset = procglobal->freeProcs;
>
> if (myOffset != INVALID_OFFSET)
> ***************
> *** 318,338 ****
>
> Assert(proctype >= 0 && proctype < NUM_DUMMY_PROCS);
>
> dummyproc = &DummyProcs[proctype];
>
> /*
> * dummyproc should not presently be in use by anyone else
> */
> if (dummyproc->pid != 0)
> elog(FATAL, "DummyProc[%d] is in use by PID %d",
> proctype, dummyproc->pid);
> MyProc = dummyproc;
>
> /*
> * Initialize all fields of MyProc, except MyProc->sem which was set
> * up by InitProcGlobal.
> */
> - MyProc->pid = MyProcPid; /* marks dummy proc as in use by me */
> SHMQueueElemInit(&(MyProc->links));
> MyProc->waitStatus = STATUS_OK;
> MyProc->xid = InvalidTransactionId;
> --- 325,362 ----
>
> Assert(proctype >= 0 && proctype < NUM_DUMMY_PROCS);
>
> + /*
> + * Just for paranoia's sake, we use the ProcStructLock to protect
> + * assignment and releasing of DummyProcs entries.
> + *
> + * While we are holding the ProcStructLock, also copy the current
> + * shared estimate of spins_per_delay to local storage.
> + */
> + SpinLockAcquire(ProcStructLock);
> +
> + set_spins_per_delay(ProcGlobal->spins_per_delay);
> +
> dummyproc = &DummyProcs[proctype];
>
> /*
> * dummyproc should not presently be in use by anyone else
> */
> if (dummyproc->pid != 0)
> + {
> + SpinLockRelease(ProcStructLock);
> elog(FATAL, "DummyProc[%d] is in use by PID %d",
> proctype, dummyproc->pid);
> + }
> MyProc = dummyproc;
>
> + MyProc->pid = MyProcPid; /* marks dummy proc as in use by me */
> +
> + SpinLockRelease(ProcStructLock);
> +
> /*
> * Initialize all fields of MyProc, except MyProc->sem which was set
> * up by InitProcGlobal.
> */
> SHMQueueElemInit(&(MyProc->links));
> MyProc->waitStatus = STATUS_OK;
> MyProc->xid = InvalidTransactionId;
> ***************
> *** 509,514 ****
> --- 533,541 ----
> /* PGPROC struct isn't mine anymore */
> MyProc = NULL;
>
> + /* Update shared estimate of spins_per_delay */
> + procglobal->spins_per_delay = update_spins_per_delay(procglobal->spins_per_delay);
> +
> SpinLockRelease(ProcStructLock);
> }
>
> ***************
> *** 532,542 ****
> --- 559,576 ----
> /* Release any LW locks I am holding (see notes above) */
> LWLockReleaseAll();
>
> + SpinLockAcquire(ProcStructLock);
> +
> /* Mark dummy proc no longer in use */
> MyProc->pid = 0;
>
> /* PGPROC struct isn't mine anymore */
> MyProc = NULL;
> +
> + /* Update shared estimate of spins_per_delay */
> + ProcGlobal->spins_per_delay = update_spins_per_delay(ProcGlobal->spins_per_delay);
> +
> + SpinLockRelease(ProcStructLock);
> }
>
>
> *** /home/postgres/pgsql/src/backend/storage/lmgr/s_lock.c.orig Fri Aug 26 10:47:35 2005
> --- /home/postgres/pgsql/src/backend/storage/lmgr/s_lock.c Sun Sep 11 17:43:20 2005
> ***************
> *** 21,26 ****
> --- 21,30 ----
> #include "storage/s_lock.h"
> #include "miscadmin.h"
>
> +
> + static int spins_per_delay = DEFAULT_SPINS_PER_DELAY;
> +
> +
> /*
> * s_lock_stuck() - complain about a stuck spinlock
> */
> ***************
> *** 49,102 ****
> * We loop tightly for awhile, then delay using pg_usleep() and try
> * again. Preferably, "awhile" should be a small multiple of the
> * maximum time we expect a spinlock to be held. 100 iterations seems
> ! * about right. In most multi-CPU scenarios, the spinlock is probably
> ! * held by a process on another CPU and will be released before we
> ! * finish 100 iterations. However, on a uniprocessor, the tight loop
> ! * is just a waste of cycles, so don't iterate thousands of times.
> *
> * Once we do decide to block, we use randomly increasing pg_usleep()
> ! * delays. The first delay is 10 msec, then the delay randomly
> ! * increases to about one second, after which we reset to 10 msec and
> * start again. The idea here is that in the presence of heavy
> * contention we need to increase the delay, else the spinlock holder
> * may never get to run and release the lock. (Consider situation
> * where spinlock holder has been nice'd down in priority by the
> * scheduler --- it will not get scheduled until all would-be
> ! * acquirers are sleeping, so if we always use a 10-msec sleep, there
> * is a real possibility of starvation.) But we can't just clamp the
> * delay to an upper bound, else it would take a long time to make a
> * reasonable number of tries.
> *
> * We time out and declare error after NUM_DELAYS delays (thus, exactly
> * that many tries). With the given settings, this will usually take
> ! * 3 or so minutes. It seems better to fix the total number of tries
> * (and thus the probability of unintended failure) than to fix the
> * total time spent.
> *
> ! * The pg_usleep() delays are measured in centiseconds (0.01 sec) because
> ! * 10 msec is a common resolution limit at the OS level.
> */
> ! #define SPINS_PER_DELAY 100
> #define NUM_DELAYS 1000
> ! #define MIN_DELAY_CSEC 1
> ! #define MAX_DELAY_CSEC 100
>
> ! int spins = 0;
> int delays = 0;
> ! int cur_delay = MIN_DELAY_CSEC;
>
> while (TAS(lock))
> {
> /* CPU-specific delay each time through the loop */
> SPIN_DELAY();
>
> ! /* Block the process every SPINS_PER_DELAY tries */
> ! if (++spins > SPINS_PER_DELAY)
> {
> if (++delays > NUM_DELAYS)
> s_lock_stuck(lock, file, line);
>
> ! pg_usleep(cur_delay * 10000L);
>
> #if defined(S_LOCK_TEST)
> fprintf(stdout, "*");
> --- 53,121 ----
> * We loop tightly for awhile, then delay using pg_usleep() and try
> * again. Preferably, "awhile" should be a small multiple of the
> * maximum time we expect a spinlock to be held. 100 iterations seems
> ! * about right as an initial guess. However, on a uniprocessor the
> ! * loop is a waste of cycles, while in a multi-CPU scenario it's usually
> ! * better to spin a bit longer than to call the kernel, so we try to
> ! * adapt the spin loop count depending on whether we seem to be in
> ! * a uniprocessor or multiprocessor.
> *
> * Once we do decide to block, we use randomly increasing pg_usleep()
> ! * delays. The first delay is 1 msec, then the delay randomly
> ! * increases to about one second, after which we reset to 1 msec and
> * start again. The idea here is that in the presence of heavy
> * contention we need to increase the delay, else the spinlock holder
> * may never get to run and release the lock. (Consider situation
> * where spinlock holder has been nice'd down in priority by the
> * scheduler --- it will not get scheduled until all would-be
> ! * acquirers are sleeping, so if we always use a 1-msec sleep, there
> * is a real possibility of starvation.) But we can't just clamp the
> * delay to an upper bound, else it would take a long time to make a
> * reasonable number of tries.
> *
> * We time out and declare error after NUM_DELAYS delays (thus, exactly
> * that many tries). With the given settings, this will usually take
> ! * 2 or so minutes. It seems better to fix the total number of tries
> * (and thus the probability of unintended failure) than to fix the
> * total time spent.
> *
> ! * The pg_usleep() delays are measured in milliseconds because 1 msec
> ! * is a common resolution limit at the OS level for newer platforms.
> ! * On older platforms the resolution limit is usually 10 msec, in
> ! * which case the total delay before timeout will be a bit more.
> */
> ! #define MIN_SPINS_PER_DELAY 10
> ! #define MAX_SPINS_PER_DELAY 1000
> #define NUM_DELAYS 1000
> ! #define MIN_DELAY_MSEC 1
> ! #define MAX_DELAY_MSEC 1000
>
> ! int spins = spins_per_delay;
> int delays = 0;
> ! int cur_delay = 0;
>
> while (TAS(lock))
> {
> /* CPU-specific delay each time through the loop */
> SPIN_DELAY();
>
> ! /*
> ! * Block the process every spins_per_delay tries.
> ! *
> ! * What we are really testing for here is spins being decremented
> ! * to zero. We insert an unnecessary integer modulo operation
> ! * into the test because we'd like this loop to run longer than
> ! * just two or three instructions: ideally, the processor should
> ! * not be contending for the system bus for a little while here.
> ! */
> ! if ((--spins % MAX_SPINS_PER_DELAY) == 0)
> {
> if (++delays > NUM_DELAYS)
> s_lock_stuck(lock, file, line);
>
> ! if (cur_delay == 0) /* first time to delay? */
> ! cur_delay = MIN_DELAY_MSEC;
> !
> ! pg_usleep(cur_delay * 1000L);
>
> #if defined(S_LOCK_TEST)
> fprintf(stdout, "*");
> ***************
> *** 107,119 ****
> cur_delay += (int) (cur_delay *
> (((double) random()) / ((double) MAX_RANDOM_VALUE)) + 0.5);
> /* wrap back to minimum delay when max is exceeded */
> ! if (cur_delay > MAX_DELAY_CSEC)
> ! cur_delay = MIN_DELAY_CSEC;
>
> ! spins = 0;
> }
> }
> }
>
> /*
> * Various TAS implementations that cannot live in s_lock.h as no inline
> --- 126,200 ----
> cur_delay += (int) (cur_delay *
> (((double) random()) / ((double) MAX_RANDOM_VALUE)) + 0.5);
> /* wrap back to minimum delay when max is exceeded */
> ! if (cur_delay > MAX_DELAY_MSEC)
> ! cur_delay = MIN_DELAY_MSEC;
>
> ! spins = spins_per_delay;
> }
> }
> +
> + /*
> + * If we were able to acquire the lock without delaying, it's a good
> + * indication we are in a multiprocessor. If we had to delay, it's
> + * a sign (but not a sure thing) that we are in a uniprocessor.
> + * Hence, we decrement spins_per_delay slowly when we had to delay,
> + * and increase it rapidly when we didn't. It's expected that
> + * spins_per_delay will converge to the minimum value on a uniprocessor
> + * and to the maximum value on a multiprocessor.
> + *
> + * Note: spins_per_delay is local within our current process.
> + * We want to average these observations across multiple backends,
> + * since it's relatively rare for this function to even get entered,
> + * and so a single backend might not live long enough to converge on
> + * a good value. That is handled by the two routines below.
> + */
> + if (cur_delay == 0)
> + {
> + /* we never had to delay */
> + spins_per_delay += 100;
> + spins_per_delay = Min(spins_per_delay, MAX_SPINS_PER_DELAY);
> + }
> + else
> + {
> + spins_per_delay -= 1;
> + spins_per_delay = Max(spins_per_delay, MIN_SPINS_PER_DELAY);
> + }
> + }
> +
> +
> + /*
> + * Set local copy of spins_per_delay during backend startup.
> + *
> + * NB: this has to be pretty fast as it is called while holding a spinlock
> + */
> + void
> + set_spins_per_delay(int shared_spins_per_delay)
> + {
> + spins_per_delay = shared_spins_per_delay;
> + }
> +
> + /*
> + * Update shared estimate of spins_per_delay during backend exit.
> + *
> + * NB: this has to be pretty fast as it is called while holding a spinlock
> + */
> + int
> + update_spins_per_delay(int shared_spins_per_delay)
> + {
> + /*
> + * We use an exponential moving average with a relatively slow
> + * adaption rate, so that noise in any one backend's result won't
> + * affect the shared value too much. As long as both inputs are
> + * within the allowed range, the result must be too, so we need not
> + * worry about clamping the result.
> + *
> + * We deliberately truncate rather than rounding; this is so that
> + * single adjustments inside a backend can affect the shared estimate
> + * (see the asymmetric adjustment rules above).
> + */
> + return (shared_spins_per_delay * 15 + spins_per_delay) / 16;
> }
> +
>
> /*
> * Various TAS implementations that cannot live in s_lock.h as no inline
> *** /home/postgres/pgsql/src/include/storage/proc.h.orig Sat Aug 20 19:26:34 2005
> --- /home/postgres/pgsql/src/include/storage/proc.h Sun Sep 11 15:07:09 2005
> ***************
> *** 105,110 ****
> --- 105,112 ----
> {
> /* Head of list of free PGPROC structures */
> SHMEM_OFFSET freeProcs;
> + /* Current shared estimate of appropriate spins_per_delay value */
> + int spins_per_delay;
> } PROC_HDR;
>
>
> *** /home/postgres/pgsql/src/include/storage/s_lock.h.orig Sun Aug 28 20:41:34 2005
> --- /home/postgres/pgsql/src/include/storage/s_lock.h Sun Sep 11 15:07:09 2005
> ***************
> *** 826,829 ****
> --- 826,835 ----
> */
> extern void s_lock(volatile slock_t *lock, const char *file, int line);
>
> + /* Support for dynamic adjustment of spins_per_delay */
> + #define DEFAULT_SPINS_PER_DELAY 100
> +
> + extern void set_spins_per_delay(int shared_spins_per_delay);
> + extern int update_spins_per_delay(int shared_spins_per_delay);
> +
> #endif /* S_LOCK_H */

>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: don't forget to increase your free space map settings

--
Bruce Momjian | http://candle.pha.pa.us
pgman(at)candle(dot)pha(dot)pa(dot)us | (610) 359-1001
+ If your life is a hard drive, | 13 Roberts Road
+ Christ can be your backup. | Newtown Square, Pennsylvania 19073