granicus.if.org Git - postgresql/blob - src/backend/storage/lmgr/s_lock.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * s_lock.c
   4  *         Hardware-dependent implementation of spinlocks.
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2006, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  *
  11  * IDENTIFICATION
  12  *        $PostgreSQL: pgsql/src/backend/storage/lmgr/s_lock.c,v 1.44 2006/05/11 21:58:22 tgl Exp $
  13  *
  14  *-------------------------------------------------------------------------
  15  */
  16 #include "postgres.h"
  17
  18 #include <time.h>
  19 #include <unistd.h>
  20
  21 #include "storage/s_lock.h"
  22 #include "miscadmin.h"
  23
  24
  25 static int      spins_per_delay = DEFAULT_SPINS_PER_DELAY;
  26
  27
  28 /*
  29  * s_lock_stuck() - complain about a stuck spinlock
  30  */
  31 static void
  32 s_lock_stuck(volatile slock_t *lock, const char *file, int line)
  33 {
  34 #if defined(S_LOCK_TEST)
  35         fprintf(stderr,
  36                         "\nStuck spinlock (%p) detected at %s:%d.\n",
  37                         lock, file, line);
  38         exit(1);
  39 #else
  40         elog(PANIC, "stuck spinlock (%p) detected at %s:%d",
  41                  lock, file, line);
  42 #endif
  43 }
  44
  45
  46 /*
  47  * s_lock(lock) - platform-independent portion of waiting for a spinlock.
  48  */
  49 void
  50 s_lock(volatile slock_t *lock, const char *file, int line)
  51 {
  52         /*
  53          * We loop tightly for awhile, then delay using pg_usleep() and try again.
  54          * Preferably, "awhile" should be a small multiple of the maximum time we
  55          * expect a spinlock to be held.  100 iterations seems about right as an
  56          * initial guess.  However, on a uniprocessor the loop is a waste of
  57          * cycles, while in a multi-CPU scenario it's usually better to spin a bit
  58          * longer than to call the kernel, so we try to adapt the spin loop count
  59          * depending on whether we seem to be in a uniprocessor or multiprocessor.
  60          *
  61          * Note: you might think MIN_SPINS_PER_DELAY should be just 1, but you'd
  62          * be wrong; there are platforms where that can result in a "stuck
  63          * spinlock" failure.  This has been seen particularly on Alphas; it seems
  64          * that the first TAS after returning from kernel space will always fail
  65          * on that hardware.
  66          *
  67          * Once we do decide to block, we use randomly increasing pg_usleep()
  68          * delays. The first delay is 1 msec, then the delay randomly increases to
  69          * about one second, after which we reset to 1 msec and start again.  The
  70          * idea here is that in the presence of heavy contention we need to
  71          * increase the delay, else the spinlock holder may never get to run and
  72          * release the lock.  (Consider situation where spinlock holder has been
  73          * nice'd down in priority by the scheduler --- it will not get scheduled
  74          * until all would-be acquirers are sleeping, so if we always use a 1-msec
  75          * sleep, there is a real possibility of starvation.)  But we can't just
  76          * clamp the delay to an upper bound, else it would take a long time to
  77          * make a reasonable number of tries.
  78          *
  79          * We time out and declare error after NUM_DELAYS delays (thus, exactly
  80          * that many tries).  With the given settings, this will usually take 2 or
  81          * so minutes.  It seems better to fix the total number of tries (and thus
  82          * the probability of unintended failure) than to fix the total time
  83          * spent.
  84          *
  85          * The pg_usleep() delays are measured in milliseconds because 1 msec is a
  86          * common resolution limit at the OS level for newer platforms. On older
  87          * platforms the resolution limit is usually 10 msec, in which case the
  88          * total delay before timeout will be a bit more.
  89          */
  90 #define MIN_SPINS_PER_DELAY 10
  91 #define MAX_SPINS_PER_DELAY 1000
  92 #define NUM_DELAYS                      1000
  93 #define MIN_DELAY_MSEC          1
  94 #define MAX_DELAY_MSEC          1000
  95
  96         int                     spins = 0;
  97         int                     delays = 0;
  98         int                     cur_delay = 0;
  99
 100         while (TAS(lock))
 101         {
 102                 /* CPU-specific delay each time through the loop */
 103                 SPIN_DELAY();
 104
 105                 /* Block the process every spins_per_delay tries */
 106                 if (++spins >= spins_per_delay)
 107                 {
 108                         if (++delays > NUM_DELAYS)
 109                                 s_lock_stuck(lock, file, line);
 110
 111                         if (cur_delay == 0) /* first time to delay? */
 112                                 cur_delay = MIN_DELAY_MSEC;
 113
 114                         pg_usleep(cur_delay * 1000L);
 115
 116 #if defined(S_LOCK_TEST)
 117                         fprintf(stdout, "*");
 118                         fflush(stdout);
 119 #endif
 120
 121                         /* increase delay by a random fraction between 1X and 2X */
 122                         cur_delay += (int) (cur_delay *
 123                                   ((double) random() / (double) MAX_RANDOM_VALUE) + 0.5);
 124                         /* wrap back to minimum delay when max is exceeded */
 125                         if (cur_delay > MAX_DELAY_MSEC)
 126                                 cur_delay = MIN_DELAY_MSEC;
 127
 128                         spins = 0;
 129                 }
 130         }
 131
 132         /*
 133          * If we were able to acquire the lock without delaying, it's a good
 134          * indication we are in a multiprocessor.  If we had to delay, it's a sign
 135          * (but not a sure thing) that we are in a uniprocessor. Hence, we
 136          * decrement spins_per_delay slowly when we had to delay, and increase it
 137          * rapidly when we didn't.  It's expected that spins_per_delay will
 138          * converge to the minimum value on a uniprocessor and to the maximum
 139          * value on a multiprocessor.
 140          *
 141          * Note: spins_per_delay is local within our current process. We want to
 142          * average these observations across multiple backends, since it's
 143          * relatively rare for this function to even get entered, and so a single
 144          * backend might not live long enough to converge on a good value.      That
 145          * is handled by the two routines below.
 146          */
 147         if (cur_delay == 0)
 148         {
 149                 /* we never had to delay */
 150                 if (spins_per_delay < MAX_SPINS_PER_DELAY)
 151                         spins_per_delay = Min(spins_per_delay + 100, MAX_SPINS_PER_DELAY);
 152         }
 153         else
 154         {
 155                 if (spins_per_delay > MIN_SPINS_PER_DELAY)
 156                         spins_per_delay = Max(spins_per_delay - 1, MIN_SPINS_PER_DELAY);
 157         }
 158 }
 159
 160
 161 /*
 162  * Set local copy of spins_per_delay during backend startup.
 163  *
 164  * NB: this has to be pretty fast as it is called while holding a spinlock
 165  */
 166 void
 167 set_spins_per_delay(int shared_spins_per_delay)
 168 {
 169         spins_per_delay = shared_spins_per_delay;
 170 }
 171
 172 /*
 173  * Update shared estimate of spins_per_delay during backend exit.
 174  *
 175  * NB: this has to be pretty fast as it is called while holding a spinlock
 176  */
 177 int
 178 update_spins_per_delay(int shared_spins_per_delay)
 179 {
 180         /*
 181          * We use an exponential moving average with a relatively slow adaption
 182          * rate, so that noise in any one backend's result won't affect the shared
 183          * value too much.      As long as both inputs are within the allowed range,
 184          * the result must be too, so we need not worry about clamping the result.
 185          *
 186          * We deliberately truncate rather than rounding; this is so that single
 187          * adjustments inside a backend can affect the shared estimate (see the
 188          * asymmetric adjustment rules above).
 189          */
 190         return (shared_spins_per_delay * 15 + spins_per_delay) / 16;
 191 }
 192
 193
 194 /*
 195  * Various TAS implementations that cannot live in s_lock.h as no inline
 196  * definition exists (yet).
 197  * In the future, get rid of tas.[cso] and fold it into this file.
 198  *
 199  * If you change something here, you will likely need to modify s_lock.h too,
 200  * because the definitions for these are split between this file and s_lock.h.
 201  */
 202
 203
 204 #ifdef HAVE_SPINLOCKS                   /* skip spinlocks if requested */
 205
 206
 207 #if defined(__GNUC__)
 208
 209 /*
 210  * All the gcc flavors that are not inlined
 211  */
 212
 213
 214 /*
 215  * Note: all the if-tests here probably ought to be testing gcc version
 216  * rather than platform, but I don't have adequate info to know what to
 217  * write.  Ideally we'd flush all this in favor of the inline version.
 218  */
 219 #if defined(__m68k__) && !defined(__linux__)
 220 /* really means: extern int tas(slock_t* **lock); */
 221 static void
 222 tas_dummy()
 223 {
 224         __asm__         __volatile__(
 225 #if defined(__NetBSD__) && defined(__ELF__)
 226 /* no underscore for label and % for registers */
 227                                                                                  "\
 228 .global         tas                             \n\
 229 tas:                                                    \n\
 230                         movel   %sp@(0x4),%a0   \n\
 231                         tas     %a0@            \n\
 232                         beq     _success        \n\
 233                         moveq   #-128,%d0       \n\
 234                         rts                             \n\
 235 _success:                                               \n\
 236                         moveq   #0,%d0          \n\
 237                         rts                             \n"
 238 #else
 239                                                                                  "\
 240 .global         _tas                            \n\
 241 _tas:                                                   \n\
 242                         movel   sp@(0x4),a0     \n\
 243                         tas     a0@                     \n\
 244                         beq     _success        \n\
 245                         moveq   #-128,d0        \n\
 246                         rts                                     \n\
 247 _success:                                               \n\
 248                         moveq   #0,d0           \n\
 249                         rts                                     \n"
 250 #endif   /* __NetBSD__ && __ELF__ */
 251         );
 252 }
 253 #endif   /* __m68k__ && !__linux__ */
 254 #else                                                   /* not __GNUC__ */
 255
 256 /*
 257  * All non gcc
 258  */
 259
 260
 261 #if defined(sun3)
 262 static void
 263 tas_dummy()                                             /* really means: extern int tas(slock_t
 264                                                                  * *lock); */
 265 {
 266         asm("LLA0:");
 267         asm("   .data");
 268         asm("   .text");
 269         asm("|#PROC# 04");
 270         asm("   .globl  _tas");
 271         asm("_tas:");
 272         asm("|#PROLOGUE# 1");
 273         asm("   movel   sp@(0x4),a0");
 274         asm("   tas a0@");
 275         asm("   beq LLA1");
 276         asm("   moveq   #-128,d0");
 277         asm("   rts");
 278         asm("LLA1:");
 279         asm("   moveq   #0,d0");
 280         asm("   rts");
 281         asm("   .data");
 282 }
 283 #endif   /* sun3 */
 284
 285
 286 #if defined(__sparc__) || defined(__sparc)
 287 /*
 288  * sparc machines not using gcc
 289  */
 290 static void
 291 tas_dummy()                                             /* really means: extern int tas(slock_t
 292                                                                  * *lock); */
 293 {
 294         asm("_tas:");
 295
 296         /*
 297          * Sparc atomic test and set (sparc calls it "atomic load-store")
 298          */
 299         asm("ldstub [%r8], %r8");
 300         asm("retl");
 301         asm("nop");
 302 }
 303 #endif   /* __sparc || __sparc__ */
 304 #endif   /* not __GNUC__ */
 305 #endif   /* HAVE_SPINLOCKS */
 306
 307
 308
 309 /*****************************************************************************/
 310 #if defined(S_LOCK_TEST)
 311
 312 /*
 313  * test program for verifying a port's spinlock support.
 314  */
 315
 316 struct test_lock_struct
 317 {
 318         char            pad1;
 319         slock_t         lock;
 320         char            pad2;
 321 };
 322
 323 volatile struct test_lock_struct test_lock;
 324
 325 int
 326 main()
 327 {
 328         srandom((unsigned int) time(NULL));
 329
 330         test_lock.pad1 = test_lock.pad2 = 0x44;
 331
 332         S_INIT_LOCK(&test_lock.lock);
 333
 334         if (test_lock.pad1 != 0x44 || test_lock.pad2 != 0x44)
 335         {
 336                 printf("S_LOCK_TEST: failed, declared datatype is wrong size\n");
 337                 return 1;
 338         }
 339
 340         if (!S_LOCK_FREE(&test_lock.lock))
 341         {
 342                 printf("S_LOCK_TEST: failed, lock not initialized\n");
 343                 return 1;
 344         }
 345
 346         S_LOCK(&test_lock.lock);
 347
 348         if (test_lock.pad1 != 0x44 || test_lock.pad2 != 0x44)
 349         {
 350                 printf("S_LOCK_TEST: failed, declared datatype is wrong size\n");
 351                 return 1;
 352         }
 353
 354         if (S_LOCK_FREE(&test_lock.lock))
 355         {
 356                 printf("S_LOCK_TEST: failed, lock not locked\n");
 357                 return 1;
 358         }
 359
 360         S_UNLOCK(&test_lock.lock);
 361
 362         if (test_lock.pad1 != 0x44 || test_lock.pad2 != 0x44)
 363         {
 364                 printf("S_LOCK_TEST: failed, declared datatype is wrong size\n");
 365                 return 1;
 366         }
 367
 368         if (!S_LOCK_FREE(&test_lock.lock))
 369         {
 370                 printf("S_LOCK_TEST: failed, lock not unlocked\n");
 371                 return 1;
 372         }
 373
 374         S_LOCK(&test_lock.lock);
 375
 376         if (test_lock.pad1 != 0x44 || test_lock.pad2 != 0x44)
 377         {
 378                 printf("S_LOCK_TEST: failed, declared datatype is wrong size\n");
 379                 return 1;
 380         }
 381
 382         if (S_LOCK_FREE(&test_lock.lock))
 383         {
 384                 printf("S_LOCK_TEST: failed, lock not re-locked\n");
 385                 return 1;
 386         }
 387
 388         printf("S_LOCK_TEST: this will print %d stars and then\n", NUM_DELAYS);
 389         printf("             exit with a 'stuck spinlock' message\n");
 390         printf("             if S_LOCK() and TAS() are working.\n");
 391         fflush(stdout);
 392
 393         s_lock(&test_lock.lock, __FILE__, __LINE__);
 394
 395         printf("S_LOCK_TEST: failed, lock not locked\n");
 396         return 1;
 397 }
 398
 399 #endif   /* S_LOCK_TEST */