Import libcompiler_rt 3.9.0, LLVM's replacement for libgcc.

This is the lib/builtin directory of the compiler-rt source tarball.

comments/ok patrick@, ok kettenis@

1 files changed, 331 insertions, 0 deletions

diff --git a/lib/libcompiler_rt/atomic.c b/lib/libcompiler_rt/atomic.c
new file mode 100644
index 00000000000..f1ddc3e0c52
--- /dev/null
+++ b/lib/libcompiler_rt/atomic.c
@@ -0,0 +1,331 @@
+/*===-- atomic.c - Implement support functions for atomic operations.------===
+ *
+ *                     The LLVM Compiler Infrastructure
+ *
+ * This file is dual licensed under the MIT and the University of Illinois Open
+ * Source Licenses. See LICENSE.TXT for details.
+ *
+ *===----------------------------------------------------------------------===
+ *
+ *  atomic.c defines a set of functions for performing atomic accesses on
+ *  arbitrary-sized memory locations.  This design uses locks that should
+ *  be fast in the uncontended case, for two reasons:
+ * 
+ *  1) This code must work with C programs that do not link to anything
+ *     (including pthreads) and so it should not depend on any pthread
+ *     functions.
+ *  2) Atomic operations, rather than explicit mutexes, are most commonly used
+ *     on code where contended operations are rate.
+ * 
+ *  To avoid needing a per-object lock, this code allocates an array of
+ *  locks and hashes the object pointers to find the one that it should use.
+ *  For operations that must be atomic on two locations, the lower lock is
+ *  always acquired first, to avoid deadlock.
+ *
+ *===----------------------------------------------------------------------===
+ */
+
+#include <stdint.h>
+#include <string.h>
+
+#include "assembly.h"
+
+// Clang objects if you redefine a builtin.  This little hack allows us to
+// define a function with the same name as an intrinsic.
+#pragma redefine_extname __atomic_load_c SYMBOL_NAME(__atomic_load)
+#pragma redefine_extname __atomic_store_c SYMBOL_NAME(__atomic_store)
+#pragma redefine_extname __atomic_exchange_c SYMBOL_NAME(__atomic_exchange)
+#pragma redefine_extname __atomic_compare_exchange_c SYMBOL_NAME(__atomic_compare_exchange)
+
+/// Number of locks.  This allocates one page on 32-bit platforms, two on
+/// 64-bit.  This can be specified externally if a different trade between
+/// memory usage and contention probability is required for a given platform.
+#ifndef SPINLOCK_COUNT
+#define SPINLOCK_COUNT (1<<10)
+#endif
+static const long SPINLOCK_MASK = SPINLOCK_COUNT - 1;
+
+////////////////////////////////////////////////////////////////////////////////
+// Platform-specific lock implementation.  Falls back to spinlocks if none is
+// defined.  Each platform should define the Lock type, and corresponding
+// lock() and unlock() functions.
+////////////////////////////////////////////////////////////////////////////////
+#ifdef __FreeBSD__
+#include <errno.h>
+#include <sys/types.h>
+#include <machine/atomic.h>
+#include <sys/umtx.h>
+typedef struct _usem Lock;
+__inline static void unlock(Lock *l) {
+  __c11_atomic_store((_Atomic(uint32_t)*)&l->_count, 1, __ATOMIC_RELEASE);
+  __c11_atomic_thread_fence(__ATOMIC_SEQ_CST);
+  if (l->_has_waiters)
+      _umtx_op(l, UMTX_OP_SEM_WAKE, 1, 0, 0);
+}
+__inline static void lock(Lock *l) {
+  uint32_t old = 1;
+  while (!__c11_atomic_compare_exchange_weak((_Atomic(uint32_t)*)&l->_count, &old,
+        0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
+    _umtx_op(l, UMTX_OP_SEM_WAIT, 0, 0, 0);
+    old = 1;
+  }
+}
+/// locks for atomic operations
+static Lock locks[SPINLOCK_COUNT] = { [0 ...  SPINLOCK_COUNT-1] = {0,1,0} };
+
+#elif defined(__APPLE__)
+#include <libkern/OSAtomic.h>
+typedef OSSpinLock Lock;
+__inline static void unlock(Lock *l) {
+  OSSpinLockUnlock(l);
+}
+/// Locks a lock.  In the current implementation, this is potentially
+/// unbounded in the contended case.
+__inline static void lock(Lock *l) {
+  OSSpinLockLock(l);
+}
+static Lock locks[SPINLOCK_COUNT]; // initialized to OS_SPINLOCK_INIT which is 0
+
+#else
+typedef _Atomic(uintptr_t) Lock;
+/// Unlock a lock.  This is a release operation.
+__inline static void unlock(Lock *l) {
+  __c11_atomic_store(l, 0, __ATOMIC_RELEASE);
+}
+/// Locks a lock.  In the current implementation, this is potentially
+/// unbounded in the contended case.
+__inline static void lock(Lock *l) {
+  uintptr_t old = 0;
+  while (!__c11_atomic_compare_exchange_weak(l, &old, 1, __ATOMIC_ACQUIRE,
+        __ATOMIC_RELAXED))
+    old = 0;
+}
+/// locks for atomic operations
+static Lock locks[SPINLOCK_COUNT];
+#endif
+
+
+/// Returns a lock to use for a given pointer.  
+static __inline Lock *lock_for_pointer(void *ptr) {
+  intptr_t hash = (intptr_t)ptr;
+  // Disregard the lowest 4 bits.  We want all values that may be part of the
+  // same memory operation to hash to the same value and therefore use the same
+  // lock.  
+  hash >>= 4;
+  // Use the next bits as the basis for the hash
+  intptr_t low = hash & SPINLOCK_MASK;
+  // Now use the high(er) set of bits to perturb the hash, so that we don't
+  // get collisions from atomic fields in a single object
+  hash >>= 16;
+  hash ^= low;
+  // Return a pointer to the word to use
+  return locks + (hash & SPINLOCK_MASK);
+}
+
+/// Macros for determining whether a size is lock free.  Clang can not yet
+/// codegen __atomic_is_lock_free(16), so for now we assume 16-byte values are
+/// not lock free.
+#define IS_LOCK_FREE_1 __c11_atomic_is_lock_free(1)
+#define IS_LOCK_FREE_2 __c11_atomic_is_lock_free(2)
+#define IS_LOCK_FREE_4 __c11_atomic_is_lock_free(4)
+#define IS_LOCK_FREE_8 __c11_atomic_is_lock_free(8)
+#define IS_LOCK_FREE_16 0
+
+/// Macro that calls the compiler-generated lock-free versions of functions
+/// when they exist.
+#define LOCK_FREE_CASES() \
+  do {\
+  switch (size) {\
+    case 2:\
+      if (IS_LOCK_FREE_2) {\
+        LOCK_FREE_ACTION(uint16_t);\
+      }\
+    case 4:\
+      if (IS_LOCK_FREE_4) {\
+        LOCK_FREE_ACTION(uint32_t);\
+      }\
+    case 8:\
+      if (IS_LOCK_FREE_8) {\
+        LOCK_FREE_ACTION(uint64_t);\
+      }\
+    case 16:\
+      if (IS_LOCK_FREE_16) {\
+        /* FIXME: __uint128_t isn't available on 32 bit platforms.
+        LOCK_FREE_ACTION(__uint128_t);*/\
+      }\
+  }\
+  } while (0)
+
+
+/// An atomic load operation.  This is atomic with respect to the source
+/// pointer only.
+void __atomic_load_c(int size, void *src, void *dest, int model) {
+#define LOCK_FREE_ACTION(type) \
+    *((type*)dest) = __c11_atomic_load((_Atomic(type)*)src, model);\
+    return;
+  LOCK_FREE_CASES();
+#undef LOCK_FREE_ACTION
+  Lock *l = lock_for_pointer(src);
+  lock(l);
+  memcpy(dest, src, size);
+  unlock(l);
+}
+
+/// An atomic store operation.  This is atomic with respect to the destination
+/// pointer only.
+void __atomic_store_c(int size, void *dest, void *src, int model) {
+#define LOCK_FREE_ACTION(type) \
+    __c11_atomic_store((_Atomic(type)*)dest, *(type*)dest, model);\
+    return;
+  LOCK_FREE_CASES();
+#undef LOCK_FREE_ACTION
+  Lock *l = lock_for_pointer(dest);
+  lock(l);
+  memcpy(dest, src, size);
+  unlock(l);
+}
+
+/// Atomic compare and exchange operation.  If the value at *ptr is identical
+/// to the value at *expected, then this copies value at *desired to *ptr.  If
+/// they  are not, then this stores the current value from *ptr in *expected.
+///
+/// This function returns 1 if the exchange takes place or 0 if it fails. 
+int __atomic_compare_exchange_c(int size, void *ptr, void *expected,
+    void *desired, int success, int failure) {
+#define LOCK_FREE_ACTION(type) \
+  return __c11_atomic_compare_exchange_strong((_Atomic(type)*)ptr, (type*)expected,\
+      *(type*)desired, success, failure)
+  LOCK_FREE_CASES();
+#undef LOCK_FREE_ACTION
+  Lock *l = lock_for_pointer(ptr);
+  lock(l);
+  if (memcmp(ptr, expected, size) == 0) {
+    memcpy(ptr, desired, size);
+    unlock(l);
+    return 1;
+  }
+  memcpy(expected, ptr, size);
+  unlock(l);
+  return 0;
+}
+
+/// Performs an atomic exchange operation between two pointers.  This is atomic
+/// with respect to the target address.
+void __atomic_exchange_c(int size, void *ptr, void *val, void *old, int model) {
+#define LOCK_FREE_ACTION(type) \
+    *(type*)old = __c11_atomic_exchange((_Atomic(type)*)ptr, *(type*)val,\
+        model);\
+    return;
+  LOCK_FREE_CASES();
+#undef LOCK_FREE_ACTION
+  Lock *l = lock_for_pointer(ptr);
+  lock(l);
+  memcpy(old, ptr, size);
+  memcpy(ptr, val, size);
+  unlock(l);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// Where the size is known at compile time, the compiler may emit calls to
+// specialised versions of the above functions.
+////////////////////////////////////////////////////////////////////////////////
+#define OPTIMISED_CASES\
+  OPTIMISED_CASE(1, IS_LOCK_FREE_1, uint8_t)\
+  OPTIMISED_CASE(2, IS_LOCK_FREE_2, uint16_t)\
+  OPTIMISED_CASE(4, IS_LOCK_FREE_4, uint32_t)\
+  OPTIMISED_CASE(8, IS_LOCK_FREE_8, uint64_t)\
+  /* FIXME: __uint128_t isn't available on 32 bit platforms.
+  OPTIMISED_CASE(16, IS_LOCK_FREE_16, __uint128_t)*/\
+
+#define OPTIMISED_CASE(n, lockfree, type)\
+type __atomic_load_##n(type *src, int model) {\
+  if (lockfree)\
+    return __c11_atomic_load((_Atomic(type)*)src, model);\
+  Lock *l = lock_for_pointer(src);\
+  lock(l);\
+  type val = *src;\
+  unlock(l);\
+  return val;\
+}
+OPTIMISED_CASES
+#undef OPTIMISED_CASE
+
+#define OPTIMISED_CASE(n, lockfree, type)\
+void  __atomic_store_##n(type *dest, type val, int model) {\
+  if (lockfree) {\
+    __c11_atomic_store((_Atomic(type)*)dest, val, model);\
+    return;\
+  }\
+  Lock *l = lock_for_pointer(dest);\
+  lock(l);\
+  *dest = val;\
+  unlock(l);\
+  return;\
+}
+OPTIMISED_CASES
+#undef OPTIMISED_CASE
+
+#define OPTIMISED_CASE(n, lockfree, type)\
+type __atomic_exchange_##n(type *dest, type val, int model) {\
+  if (lockfree)\
+    return __c11_atomic_exchange((_Atomic(type)*)dest, val, model);\
+  Lock *l = lock_for_pointer(dest);\
+  lock(l);\
+  type tmp = *dest;\
+  *dest = val;\
+  unlock(l);\
+  return tmp;\
+}
+OPTIMISED_CASES
+#undef OPTIMISED_CASE
+
+#define OPTIMISED_CASE(n, lockfree, type)\
+int __atomic_compare_exchange_##n(type *ptr, type *expected, type desired,\
+    int success, int failure) {\
+  if (lockfree)\
+    return __c11_atomic_compare_exchange_strong((_Atomic(type)*)ptr, expected, desired,\
+        success, failure);\
+  Lock *l = lock_for_pointer(ptr);\
+  lock(l);\
+  if (*ptr == *expected) {\
+    *ptr = desired;\
+    unlock(l);\
+    return 1;\
+  }\
+  *expected = *ptr;\
+  unlock(l);\
+  return 0;\
+}
+OPTIMISED_CASES
+#undef OPTIMISED_CASE
+
+////////////////////////////////////////////////////////////////////////////////
+// Atomic read-modify-write operations for integers of various sizes.
+////////////////////////////////////////////////////////////////////////////////
+#define ATOMIC_RMW(n, lockfree, type, opname, op) \
+type __atomic_fetch_##opname##_##n(type *ptr, type val, int model) {\
+  if (lockfree) \
+    return __c11_atomic_fetch_##opname((_Atomic(type)*)ptr, val, model);\
+  Lock *l = lock_for_pointer(ptr);\
+  lock(l);\
+  type tmp = *ptr;\
+  *ptr = tmp op val;\
+  unlock(l);\
+  return tmp;\
+}
+
+#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, add, +)
+OPTIMISED_CASES
+#undef OPTIMISED_CASE
+#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, sub, -)
+OPTIMISED_CASES
+#undef OPTIMISED_CASE
+#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, and, &)
+OPTIMISED_CASES
+#undef OPTIMISED_CASE
+#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, or, |)
+OPTIMISED_CASES
+#undef OPTIMISED_CASE
+#define OPTIMISED_CASE(n, lockfree, type) ATOMIC_RMW(n, lockfree, type, xor, ^)
+OPTIMISED_CASES
+#undef OPTIMISED_CASE