libexec/rtld-elf/i386/lockdflt.c

   1 /*-
   2  * Copyright 1999, 2000 John D. Polstra.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  15  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  16  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  17  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  18  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  19  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  20  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  21  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  *
  25  * $FreeBSD: src/libexec/rtld-elf/i386/lockdflt.c,v 1.5.2.4 2002/07/11 23:52:32 jdp Exp $
  26  */
  27
  28 /*
  29  * Thread locking implementation for the dynamic linker.
  30  *
  31  * On 80486 and later CPUs we use the "simple, non-scalable
  32  * reader-preference lock" from:
  33  *
  34  *   J. M. Mellor-Crummey and M. L. Scott. "Scalable Reader-Writer
  35  *   Synchronization for Shared-Memory Multiprocessors." 3rd ACM Symp. on
  36  *   Principles and Practice of Parallel Programming, April 1991.
  37  *
  38  * In this algorithm the lock is a single word.  Its low-order bit is
  39  * set when a writer holds the lock.  The remaining high-order bits
  40  * contain a count of readers desiring the lock.  The algorithm requires
  41  * atomic "compare_and_store" and "add" operations.
  42  *
  43  * The "compare_and_store" operation requires the "cmpxchg" instruction
  44  * on the x86.  Unfortunately, the 80386 CPU does not support that
  45  * instruction -- only the 80486 and later models support it.  So on the
  46  * 80386 we must use simple test-and-set exclusive locks instead.  We
  47  * determine which kind of lock to use by trying to execute a "cmpxchg"
  48  * instruction and catching the SIGILL which results on the 80386.
  49  */
  50
  51 #include <setjmp.h>
  52 #include <signal.h>
  53 #include <stdlib.h>
  54 #include <time.h>
  55
  56 #include "debug.h"
  57 #include "rtld.h"
  58
  59 #define CACHE_LINE_SIZE         32
  60
  61 #define WAFLAG          0x1     /* A writer holds the lock */
  62 #define RC_INCR         0x2     /* Adjusts count of readers desiring lock */
  63
  64 typedef struct Struct_Lock {
  65         volatile int lock;
  66         void *base;
  67 } Lock;
  68
  69 static sigset_t fullsigmask, oldsigmask;
  70
  71 static inline int
  72 cmpxchgl(int old, int new, volatile int *m)
  73 {
  74         int result;
  75
  76         __asm __volatile ("lock; cmpxchgl %2, %0"
  77             : "+m"(*m), "=a"(result)
  78             : "r"(new), "1"(old)
  79             : "cc");
  80
  81         return result;
  82 }
  83
  84 static inline int
  85 xchgl(int v, volatile int *m)
  86 {
  87         int result;
  88
  89         __asm __volatile ("xchgl %0, %1"
  90             : "=r"(result), "+m"(*m)
  91             : "0"(v));
  92
  93         return result;
  94 }
  95
  96 static void *
  97 lock_create(void *context)
  98 {
  99     void *base;
 100     char *p;
 101     uintptr_t r;
 102     Lock *l;
 103
 104     /*
 105      * Arrange for the lock to occupy its own cache line.  First, we
 106      * optimistically allocate just a cache line, hoping that malloc
 107      * will give us a well-aligned block of memory.  If that doesn't
 108      * work, we allocate a larger block and take a well-aligned cache
 109      * line from it.
 110      */
 111     base = xmalloc(CACHE_LINE_SIZE);
 112     p = (char *)base;
 113     if ((uintptr_t)p % CACHE_LINE_SIZE != 0) {
 114         free(base);
 115         base = xmalloc(2 * CACHE_LINE_SIZE);
 116         p = (char *)base;
 117         if ((r = (uintptr_t)p % CACHE_LINE_SIZE) != 0)
 118             p += CACHE_LINE_SIZE - r;
 119     }
 120     l = (Lock *)p;
 121     l->base = base;
 122     l->lock = 0;
 123     return l;
 124 }
 125
 126 static void
 127 lock_destroy(void *lock)
 128 {
 129     Lock *l = (Lock *)lock;
 130
 131     free(l->base);
 132 }
 133
 134 /*
 135  * Crude exclusive locks for the 80386, which does not support the
 136  * cmpxchg instruction.
 137  */
 138 static void
 139 lock80386_acquire(void *lock)
 140 {
 141     Lock *l = (Lock *)lock;
 142     sigset_t tmp_oldsigmask;
 143
 144     for ( ; ; ) {
 145         sigprocmask(SIG_BLOCK, &fullsigmask, &tmp_oldsigmask);
 146         if (xchgl(1, &l->lock) == 0)
 147             break;
 148         sigprocmask(SIG_SETMASK, &tmp_oldsigmask, NULL);
 149         while (l->lock != 0)
 150             ;   /* Spin */
 151     }
 152     oldsigmask = tmp_oldsigmask;
 153 }
 154
 155 static void
 156 lock80386_release(void *lock)
 157 {
 158     Lock *l = (Lock *)lock;
 159
 160     l->lock = 0;
 161     sigprocmask(SIG_SETMASK, &oldsigmask, NULL);
 162 }
 163
 164 /*
 165  * Better reader/writer locks for the 80486 and later CPUs.
 166  */
 167 static void
 168 rlock_acquire(void *lock)
 169 {
 170     Lock *l = (Lock *)lock;
 171
 172     atomic_add_int(&l->lock, RC_INCR);
 173     while (l->lock & WAFLAG)
 174             ;   /* Spin */
 175 }
 176
 177 static void
 178 wlock_acquire(void *lock)
 179 {
 180     Lock *l = (Lock *)lock;
 181     sigset_t tmp_oldsigmask;
 182
 183     for ( ; ; ) {
 184         sigprocmask(SIG_BLOCK, &fullsigmask, &tmp_oldsigmask);
 185         if (cmpxchgl(0, WAFLAG, &l->lock) == 0)
 186             break;
 187         sigprocmask(SIG_SETMASK, &tmp_oldsigmask, NULL);
 188     }
 189     oldsigmask = tmp_oldsigmask;
 190 }
 191
 192 static void
 193 rlock_release(void *lock)
 194 {
 195     Lock *l = (Lock *)lock;
 196
 197     atomic_add_int(&l->lock, -RC_INCR);
 198 }
 199
 200 static void
 201 wlock_release(void *lock)
 202 {
 203     Lock *l = (Lock *)lock;
 204
 205     atomic_add_int(&l->lock, -WAFLAG);
 206     sigprocmask(SIG_SETMASK, &oldsigmask, NULL);
 207 }
 208
 209 /*
 210  * Code to determine at runtime whether the CPU supports the cmpxchg
 211  * instruction.  This instruction allows us to use locks that are more
 212  * efficient, but it didn't exist on the 80386.
 213  */
 214 static jmp_buf sigill_env;
 215
 216 static void
 217 sigill(int sig)
 218 {
 219     longjmp(sigill_env, 1);
 220 }
 221
 222 static int
 223 cpu_supports_cmpxchg(void)
 224 {
 225     struct sigaction act, oact;
 226     int result;
 227     volatile int lock;
 228
 229     memset(&act, 0, sizeof act);
 230     act.sa_handler = sigill;
 231     sigemptyset(&act.sa_mask);
 232     act.sa_flags = 0;
 233
 234     sigaction(SIGILL, &act, &oact);
 235     if (setjmp(sigill_env) == 0) {
 236         lock = 0;
 237         cmpxchgl(0, 1, &lock);
 238         result = 1;
 239     } else
 240         result = 0;
 241     sigaction(SIGILL, &oact, NULL);
 242     return result;
 243 }
 244
 245 void
 246 lockdflt_init(LockInfo *li)
 247 {
 248     li->context = NULL;
 249     li->context_destroy = NULL;
 250     li->lock_create = lock_create;
 251     li->lock_destroy = lock_destroy;
 252     if (cpu_supports_cmpxchg()) {
 253         /* Use fast locks that require an 80486 or later. */
 254         li->rlock_acquire = rlock_acquire;
 255         li->wlock_acquire = wlock_acquire;
 256         li->rlock_release = rlock_release;
 257         li->wlock_release = wlock_release;
 258     } else {
 259         /* It's a cruddy old 80386. */
 260         li->rlock_acquire = li->wlock_acquire = lock80386_acquire;
 261         li->rlock_release = li->wlock_release = lock80386_release;
 262     }
 263     /*
 264      * Construct a mask to block all signals except traps which might
 265      * conceivably be generated within the dynamic linker itself.
 266      */
 267     sigfillset(&fullsigmask);
 268     sigdelset(&fullsigmask, SIGILL);
 269     sigdelset(&fullsigmask, SIGTRAP);
 270     sigdelset(&fullsigmask, SIGABRT);
 271     sigdelset(&fullsigmask, SIGEMT);
 272     sigdelset(&fullsigmask, SIGFPE);
 273     sigdelset(&fullsigmask, SIGBUS);
 274     sigdelset(&fullsigmask, SIGSEGV);
 275     sigdelset(&fullsigmask, SIGSYS);
 276 }