| // | |
| // Copyright 2020 The Abseil Authors. | |
| // | |
| // 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 | |
| // | |
| // https://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. | |
| namespace absl { | |
| ABSL_NAMESPACE_BEGIN | |
| namespace flags_internal { | |
| // Align 'x' up to the nearest 'align' bytes. | |
| inline constexpr size_t AlignUp(size_t x, size_t align) { | |
| return align * ((x + align - 1) / align); | |
| } | |
| // A SequenceLock implements lock-free reads. A sequence counter is incremented | |
| // before and after each write, and readers access the counter before and after | |
| // accessing the protected data. If the counter is verified to not change during | |
| // the access, and the sequence counter value was even, then the reader knows | |
| // that the read was race-free and valid. Otherwise, the reader must fall back | |
| // to a Mutex-based code path. | |
| // | |
| // This particular SequenceLock starts in an "uninitialized" state in which | |
| // TryRead() returns false. It must be enabled by calling MarkInitialized(). | |
| // This serves as a marker that the associated flag value has not yet been | |
| // initialized and a slow path needs to be taken. | |
| // | |
| // The memory reads and writes protected by this lock must use the provided | |
| // `TryRead()` and `Write()` functions. These functions behave similarly to | |
| // `memcpy()`, with one oddity: the protected data must be an array of | |
| // `std::atomic<uint64>`. This is to comply with the C++ standard, which | |
| // considers data races on non-atomic objects to be undefined behavior. See "Can | |
| // Seqlocks Get Along With Programming Language Memory Models?"[1] by Hans J. | |
| // Boehm for more details. | |
| // | |
| // [1] https://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf | |
| class SequenceLock { | |
| public: | |
| constexpr SequenceLock() : lock_(kUninitialized) {} | |
| // Mark that this lock is ready for use. | |
| void MarkInitialized() { | |
| assert(lock_.load(std::memory_order_relaxed) == kUninitialized); | |
| lock_.store(0, std::memory_order_release); | |
| } | |
| // Copy "size" bytes of data from "src" to "dst", protected as a read-side | |
| // critical section of the sequence lock. | |
| // | |
| // Unlike traditional sequence lock implementations which loop until getting a | |
| // clean read, this implementation returns false in the case of concurrent | |
| // calls to `Write`. In such a case, the caller should fall back to a | |
| // locking-based slow path. | |
| // | |
| // Returns false if the sequence lock was not yet marked as initialized. | |
| // | |
| // NOTE: If this returns false, "dst" may be overwritten with undefined | |
| // (potentially uninitialized) data. | |
| bool TryRead(void* dst, const std::atomic<uint64_t>* src, size_t size) const { | |
| // Acquire barrier ensures that no loads done by f() are reordered | |
| // above the first load of the sequence counter. | |
| int64_t seq_before = lock_.load(std::memory_order_acquire); | |
| if (ABSL_PREDICT_FALSE(seq_before & 1) == 1) return false; | |
| RelaxedCopyFromAtomic(dst, src, size); | |
| // Another acquire fence ensures that the load of 'lock_' below is | |
| // strictly ordered after the RelaxedCopyToAtomic call above. | |
| std::atomic_thread_fence(std::memory_order_acquire); | |
| int64_t seq_after = lock_.load(std::memory_order_relaxed); | |
| return ABSL_PREDICT_TRUE(seq_before == seq_after); | |
| } | |
| // Copy "size" bytes from "src" to "dst" as a write-side critical section | |
| // of the sequence lock. Any concurrent readers will be forced to retry | |
| // until they get a read that does not conflict with this write. | |
| // | |
| // This call must be externally synchronized against other calls to Write, | |
| // but may proceed concurrently with reads. | |
| void Write(std::atomic<uint64_t>* dst, const void* src, size_t size) { | |
| // We can use relaxed instructions to increment the counter since we | |
| // are extenally synchronized. The std::atomic_thread_fence below | |
| // ensures that the counter updates don't get interleaved with the | |
| // copy to the data. | |
| int64_t orig_seq = lock_.load(std::memory_order_relaxed); | |
| assert((orig_seq & 1) == 0); // Must be initially unlocked. | |
| lock_.store(orig_seq + 1, std::memory_order_relaxed); | |
| // We put a release fence between update to lock_ and writes to shared data. | |
| // Thus all stores to shared data are effectively release operations and | |
| // update to lock_ above cannot be re-ordered past any of them. Note that | |
| // this barrier is not for the fetch_add above. A release barrier for the | |
| // fetch_add would be before it, not after. | |
| std::atomic_thread_fence(std::memory_order_release); | |
| RelaxedCopyToAtomic(dst, src, size); | |
| // "Release" semantics ensure that none of the writes done by | |
| // RelaxedCopyToAtomic() can be reordered after the following modification. | |
| lock_.store(orig_seq + 2, std::memory_order_release); | |
| } | |
| // Return the number of times that Write() has been called. | |
| // | |
| // REQUIRES: This must be externally synchronized against concurrent calls to | |
| // `Write()` or `IncrementModificationCount()`. | |
| // REQUIRES: `MarkInitialized()` must have been previously called. | |
| int64_t ModificationCount() const { | |
| int64_t val = lock_.load(std::memory_order_relaxed); | |
| assert(val != kUninitialized && (val & 1) == 0); | |
| return val / 2; | |
| } | |
| // REQUIRES: This must be externally synchronized against concurrent calls to | |
| // `Write()` or `ModificationCount()`. | |
| // REQUIRES: `MarkInitialized()` must have been previously called. | |
| void IncrementModificationCount() { | |
| int64_t val = lock_.load(std::memory_order_relaxed); | |
| assert(val != kUninitialized); | |
| lock_.store(val + 2, std::memory_order_relaxed); | |
| } | |
| private: | |
| // Perform the equivalent of "memcpy(dst, src, size)", but using relaxed | |
| // atomics. | |
| static void RelaxedCopyFromAtomic(void* dst, const std::atomic<uint64_t>* src, | |
| size_t size) { | |
| char* dst_byte = static_cast<char*>(dst); | |
| while (size >= sizeof(uint64_t)) { | |
| uint64_t word = src->load(std::memory_order_relaxed); | |
| std::memcpy(dst_byte, &word, sizeof(word)); | |
| dst_byte += sizeof(word); | |
| src++; | |
| size -= sizeof(word); | |
| } | |
| if (size > 0) { | |
| uint64_t word = src->load(std::memory_order_relaxed); | |
| std::memcpy(dst_byte, &word, size); | |
| } | |
| } | |
| // Perform the equivalent of "memcpy(dst, src, size)", but using relaxed | |
| // atomics. | |
| static void RelaxedCopyToAtomic(std::atomic<uint64_t>* dst, const void* src, | |
| size_t size) { | |
| const char* src_byte = static_cast<const char*>(src); | |
| while (size >= sizeof(uint64_t)) { | |
| uint64_t word; | |
| std::memcpy(&word, src_byte, sizeof(word)); | |
| dst->store(word, std::memory_order_relaxed); | |
| src_byte += sizeof(word); | |
| dst++; | |
| size -= sizeof(word); | |
| } | |
| if (size > 0) { | |
| uint64_t word = 0; | |
| std::memcpy(&word, src_byte, size); | |
| dst->store(word, std::memory_order_relaxed); | |
| } | |
| } | |
| static constexpr int64_t kUninitialized = -1; | |
| std::atomic<int64_t> lock_; | |
| }; | |
| } // namespace flags_internal | |
| ABSL_NAMESPACE_END | |
| } // namespace absl | |