Fix another race in Notification Queue

[folly.git] / folly / SmallLocks.h

diff --git a/folly/SmallLocks.h b/folly/SmallLocks.h
index 51abb97c738608bf346165117e51eb5989ccd874..1e2915d5de127c5ffab8627c34e08cf9273277f3 100644 (file)
--- a/folly/SmallLocks.h
+++ b/folly/SmallLocks.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2014 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -34,6 +34,7 @@
  * @author Jordan DeLong <delong.j@fb.com>
  */
 
+#include <array>
 #include <cinttypes>
 #include <type_traits>
 #include <ctime>
@@ -43,8 +44,9 @@
 #include <mutex>
 
 #include <glog/logging.h>
+#include <folly/Portability.h>
 
-#ifndef __x86_64__
+#if !FOLLY_X64
 # error "SmallLocks.h is currently x64-only."
 #endif
 
@@ -77,7 +79,7 @@ namespace detail {
          * linux this varies by kernel version from 1ms to 10ms).
          */
         struct timespec ts = { 0, 500000 };
-        nanosleep(&ts, NULL);
+        nanosleep(&ts, nullptr);
       }
     }
   };
@@ -108,12 +110,13 @@ struct MicroSpinLock {
    */
   bool cas(uint8_t compare, uint8_t newVal) {
     bool out;
-    asm volatile("lock; cmpxchgb %2, (%3);"
-                 "setz %0;"
-                 : "=r" (out)
+    bool memVal; // only set if the cmpxchg fails
+    asm volatile("lock; cmpxchgb %[newVal], (%[lockPtr]);"
+                 "setz %[output];"
+                 : [output] "=r" (out), "=a" (memVal)
                  : "a" (compare), // cmpxchgb constrains this to be in %al
-                   "q" (newVal),  // Needs to be byte-accessible
-                   "r" (&lock_)
+                   [newVal] "q" (newVal),  // Needs to be byte-accessible
+                   [lockPtr] "r" (&lock_)
                  : "memory", "flags");
     return out;
   }
@@ -172,7 +175,7 @@ struct PicoSpinLock {
                   sizeof(IntType) == 8,
                 "PicoSpinLock can't work on integers smaller than 2 bytes");
 
-public:
+ public:
   static const UIntType kLockBitMask_ = UIntType(1) << Bit;
   UIntType lock_;
 
@@ -275,6 +278,50 @@ public:
 
 //////////////////////////////////////////////////////////////////////
 
+/**
+ * Array of spinlocks where each one is padded to prevent false sharing.
+ * Useful for shard-based locking implementations in environments where
+ * contention is unlikely.
+ */
+
+// TODO: generate it from configure (`getconf LEVEL1_DCACHE_LINESIZE`)
+#define FOLLY_CACHE_LINE_SIZE 64
+
+template <class T, size_t N>
+struct SpinLockArray {
+  T& operator[](size_t i) {
+    return data_[i].lock;
+  }
+
+  const T& operator[](size_t i) const {
+    return data_[i].lock;
+  }
+
+  constexpr size_t size() const { return N; }
+
+ private:
+  struct PaddedSpinLock {
+    PaddedSpinLock() : lock() { }
+    T lock;
+    char padding[FOLLY_CACHE_LINE_SIZE - sizeof(T)];
+  };
+  static_assert(sizeof(PaddedSpinLock) == FOLLY_CACHE_LINE_SIZE,
+                "Invalid size of PaddedSpinLock");
+
+  // Check if T can theoretically cross a cache line.
+  // NOTE: It should be alignof(std::max_align_t), but max_align_t
+  // isn't supported by gcc 4.6.2.
+  static_assert(alignof(MaxAlign) > 0 &&
+                FOLLY_CACHE_LINE_SIZE % alignof(MaxAlign) == 0 &&
+                sizeof(T) <= alignof(MaxAlign),
+                "T can cross cache line boundaries");
+
+  char padding_[FOLLY_CACHE_LINE_SIZE];
+  std::array<PaddedSpinLock, N> data_;
+} __attribute__((aligned));
+
+//////////////////////////////////////////////////////////////////////
+
 typedef std::lock_guard<MicroSpinLock> MSLGuard;
 
 //////////////////////////////////////////////////////////////////////