From 98d1077ce0603b0713353d638cb1436a28827af6 Mon Sep 17 00:00:00 2001 From: David Goldblatt Date: Fri, 12 Jan 2018 23:57:16 -0800 Subject: [PATCH] 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 --- folly/Makefile.am | 1 + folly/synchronization/Tearable.h | 98 +++++++++++++++++++++ folly/synchronization/test/TearableTest.cpp | 93 +++++++++++++++++++ 3 files changed, 192 insertions(+) create mode 100644 folly/synchronization/Tearable.h create mode 100644 folly/synchronization/test/TearableTest.cpp diff --git a/folly/Makefile.am b/folly/Makefile.am index e5e0f9b9..3ba08f4c 100644 --- 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/Tearable.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 index 00000000..95f68904 --- /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 +#include +#include + +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. 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 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 allows concurrent access without + * these costs. + * + * For types smaller than the processor word size, prefer std::atomic. + */ +template +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::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 data_[kNumDataWords]; +}; + +} // namespace folly diff --git a/folly/synchronization/test/TearableTest.cpp b/folly/synchronization/test/TearableTest.cpp new file mode 100644 index 00000000..96101f59 --- /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 + +#include +#include + +#include + +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 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 stop(false); + Tearable 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 -- 2.34.1