Add Tearable, for concurrently-modified non-atomic objects.

Summary:
This adds the Tearable class template, which holds storage for an
arbitrarily-sized object that can be concurrently read or written without any
external synchronization.

Reviewed By: yfeldblum, djwatson

Differential Revision: D6422334

fbshipit-source-id: ee3853bbd393ac8e30dca6439c61606cc5495f92

diff --git a/folly/Makefile.am b/folly/Makefile.am
index e5e0f9b..3ba08f4 100644 (file)
--- a/folly/Makefile.am
+++ b/folly/Makefile.am
@@ -439,6 +439,7 @@ nobase_follyinclude_HEADERS = \
        synchronization/ParkingLot.h \
        synchronization/RWSpinLock.h \
        synchronization/SaturatingSemaphore.h \
        synchronization/ParkingLot.h \
        synchronization/RWSpinLock.h \
        synchronization/SaturatingSemaphore.h \

+       synchronization/Tearable.h \

        synchronization/WaitOptions.h \
        synchronization/detail/AtomicUtils.h \
        synchronization/detail/Sleeper.h \
        synchronization/WaitOptions.h \
        synchronization/detail/AtomicUtils.h \
        synchronization/detail/Sleeper.h \

diff --git a/folly/synchronization/Tearable.h b/folly/synchronization/Tearable.h
new file mode 100644 (file)
index 0000000..95f6890
--- /dev/null
+++ b/folly/synchronization/Tearable.h
@@ -0,0 +1,98 @@
+/*
+ * Copyright 2018-present Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#pragma once
+
+#include <atomic>
+#include <cstring>
+#include <type_traits>
+
+namespace folly {
+
+/**
+ * This class allows you to perform torn loads and stores on the bits of a
+ * trivially-copyable type T without triggering undefined behavior. You may
+ * encounter corrupt data, but should not encounter nasal demons.
+ *
+ * This class provides no atomicity or memory ordering. Loads and stores are
+ * expected often to be data races. Synchronization is expected to be provided
+ * externally, and this class is helpful in building higher-level optimistic
+ * concurrency tools in combination with externally-provided synchronization.
+ *
+ * To see why this is useful, consider the guarantees provided by
+ * std::atomic<T>. It ensures that every load returns a T that was stored in the
+ * atomic. If T is too large to be read/written with a single load/store
+ * instruction, std::atomic<T> falls back to locking to provide this guarantee.
+ * Users pay this cost even if they have some higher-level mechanism (an
+ * external lock, version numbers, other application-level reasoning) that makes
+ * them resilient to torn reads. Tearable<T> allows concurrent access without
+ * these costs.
+ *
+ * For types smaller than the processor word size, prefer std::atomic<T>.
+ */
+template <typename T>
+class Tearable {
+ public:
+  // We memcpy the object representation, and the destructor would not know how
+  // to deal with an object state it doesn't understand.
+  static_assert(
+      std::is_trivially_copyable<T>::value,
+      "Tearable types must be trivially copyable.");
+
+  Tearable() {
+    for (std::size_t i = 0; i < kNumDataWords; ++i) {
+      std::atomic_init(&data_[i], RawWord{});
+    }
+  }
+
+  Tearable(const T& val) : Tearable() {
+    store(val);
+  }
+
+  // Note that while filling dst with invalid data should be fine, *doing
+  // anything* with the result may trigger undefined behavior unless you've
+  // verified that the data you read was consistent.
+  void load(T& dst) const {
+    RawWord newDst[kNumDataWords];
+
+    for (std::size_t i = 0; i < kNumDataWords; ++i) {
+      newDst[i] = data_[i].load(std::memory_order_relaxed);
+    }
+    std::memcpy(&dst, newDst, sizeof(T));
+  }
+
+  void store(const T& val) {
+    RawWord newData[kNumDataWords];
+    std::memcpy(newData, &val, sizeof(T));
+
+    for (std::size_t i = 0; i < kNumDataWords; ++i) {
+      data_[i].store(newData[i], std::memory_order_relaxed);
+    }
+  }
+
+ private:
+  // A union gets us memcpy-like copy semantics always.
+  union RawWord {
+    // "unsigned" here matters; we may read uninitialized values (in the
+    // trailing data word in write(), for instance).
+    unsigned char data alignas(void*)[sizeof(void*)];
+  };
+  const static std::size_t kNumDataWords =
+      (sizeof(T) + sizeof(RawWord) - 1) / sizeof(RawWord);
+
+  std::atomic<RawWord> data_[kNumDataWords];
+};
+
+} // namespace folly

diff --git a/folly/synchronization/test/TearableTest.cpp b/folly/synchronization/test/TearableTest.cpp
new file mode 100644 (file)
index 0000000..96101f5
--- /dev/null
+++ b/folly/synchronization/test/TearableTest.cpp
@@ -0,0 +1,93 @@
+/*
+ * Copyright 2018-present Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <folly/synchronization/Tearable.h>
+
+#include <atomic>
+#include <thread>
+
+#include <folly/portability/GTest.h>
+
+using namespace folly;
+
+namespace {
+
+struct Data {
+  Data(unsigned char value) {
+    setValue(value);
+  }
+
+  void setValue(unsigned char value) {
+    for (auto& item : contents) {
+      item = value;
+    }
+  }
+
+  void checkValue(unsigned char value) {
+    for (auto& item : contents) {
+      ASSERT_EQ(value, item);
+    }
+  }
+
+  void checkValue2(unsigned char value1, unsigned char value2) {
+    for (auto& item : contents) {
+      ASSERT_TRUE(item == value1 || item == value2);
+    }
+  }
+
+  // Note the odd size -- this will hopefully expose layout bugs under
+  // sanitizers.
+  unsigned char contents[99];
+};
+
+TEST(TearableTest, BasicOperations) {
+  Tearable<Data> tearable;
+  Data src(0);
+  Data dst(1);
+  for (char c = 0; c < 10; ++c) {
+    src.setValue(c);
+    tearable.store(src);
+    tearable.load(dst);
+    dst.checkValue(c);
+  }
+}
+
+TEST(TearableTest, Races) {
+  std::atomic<bool> stop(false);
+  Tearable<Data> tearable(Data(1));
+  std::thread write1([&]() {
+    Data data0(1);
+    while (!stop.load(std::memory_order_relaxed)) {
+      tearable.store(data0);
+    }
+  });
+  std::thread write2([&]() {
+    Data data1(2);
+    while (!stop.load(std::memory_order_relaxed)) {
+      tearable.store(data1);
+    }
+  });
+  Data val(0);
+  for (int i = 0; i < 100 * 1000; ++i) {
+    tearable.load(val);
+    val.checkValue2(1, 2);
+  }
+  stop.store(true, std::memory_order_relaxed);
+  write1.join();
+  write2.join();
+}
+
+} // namespace