| //===--- Concurrent.h - Concurrent Data Structures -------------*- C++ -*-===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| #ifndef SWIFT_RUNTIME_CONCURRENTUTILS_H |
| #define SWIFT_RUNTIME_CONCURRENTUTILS_H |
| #include <iterator> |
| #include <algorithm> |
| #include <atomic> |
| #include <functional> |
| #include <stdint.h> |
| #include <vector> |
| #include "llvm/Support/Allocator.h" |
| #include "Atomic.h" |
| #include "Debug.h" |
| #include "Mutex.h" |
| |
| #if defined(__FreeBSD__) || defined(__CYGWIN__) || defined(__HAIKU__) |
| #include <stdio.h> |
| #endif |
| |
| namespace swift { |
| |
| /// This is a node in a concurrent linked list. |
| template <class ElemTy> struct ConcurrentListNode { |
| ConcurrentListNode(ElemTy Elem) : Payload(Elem), Next(nullptr) {} |
| ConcurrentListNode(const ConcurrentListNode &) = delete; |
| ConcurrentListNode &operator=(const ConcurrentListNode &) = delete; |
| |
| /// The element. |
| ElemTy Payload; |
| /// Points to the next link in the chain. |
| ConcurrentListNode<ElemTy> *Next; |
| }; |
| |
| /// This is a concurrent linked list. It supports insertion at the beginning |
| /// of the list and traversal using iterators. |
| /// This is a very simple implementation of a concurrent linked list |
| /// using atomic operations. The 'push_front' method allocates a new link |
| /// and attempts to compare and swap the old head pointer with pointer to |
| /// the new link. This operation may fail many times if there are other |
| /// contending threads, but eventually the head pointer is set to the new |
| /// link that already points to the old head value. Notice that the more |
| /// difficult feature of removing links is not supported. |
| /// See 'push_front' for more details. |
| template <class ElemTy> struct ConcurrentList { |
| ConcurrentList() : First(nullptr) {} |
| ~ConcurrentList() { |
| clear(); |
| } |
| |
| /// Remove all of the links in the chain. This method leaves |
| /// the list at a usable state and new links can be added. |
| /// Notice that this operation is non-concurrent because |
| /// we have no way of ensuring that no one is currently |
| /// traversing the list. |
| void clear() { |
| // Iterate over the list and delete all the nodes. |
| auto Ptr = First.load(std::memory_order_acquire); |
| First.store(nullptr, std:: memory_order_release); |
| |
| while (Ptr) { |
| auto N = Ptr->Next; |
| delete Ptr; |
| Ptr = N; |
| } |
| } |
| |
| ConcurrentList(const ConcurrentList &) = delete; |
| ConcurrentList &operator=(const ConcurrentList &) = delete; |
| |
| /// A list iterator. |
| struct ConcurrentListIterator : |
| public std::iterator<std::forward_iterator_tag, ElemTy> { |
| |
| /// Points to the current link. |
| ConcurrentListNode<ElemTy> *Ptr; |
| /// C'tor. |
| ConcurrentListIterator(ConcurrentListNode<ElemTy> *P) : Ptr(P) {} |
| /// Move to the next element. |
| ConcurrentListIterator &operator++() { |
| Ptr = Ptr->Next; |
| return *this; |
| } |
| /// Access the element. |
| ElemTy &operator*() { return Ptr->Payload; } |
| /// Same? |
| bool operator==(const ConcurrentListIterator &o) const { |
| return o.Ptr == Ptr; |
| } |
| /// Not the same? |
| bool operator!=(const ConcurrentListIterator &o) const { |
| return o.Ptr != Ptr; |
| } |
| }; |
| |
| /// Iterator entry point. |
| typedef ConcurrentListIterator iterator; |
| /// Marks the beginning of the list. |
| iterator begin() const { |
| return ConcurrentListIterator(First.load(std::memory_order_acquire)); |
| } |
| /// Marks the end of the list. |
| iterator end() const { return ConcurrentListIterator(nullptr); } |
| |
| /// Add a new item to the list. |
| void push_front(ElemTy Elem) { |
| /// Allocate a new node. |
| ConcurrentListNode<ElemTy> *N = new ConcurrentListNode<ElemTy>(Elem); |
| // Point to the first element in the list. |
| N->Next = First.load(std::memory_order_acquire); |
| auto OldFirst = N->Next; |
| // Try to replace the current First with the new node. |
| while (!std::atomic_compare_exchange_weak_explicit(&First, &OldFirst, N, |
| std::memory_order_release, |
| std::memory_order_relaxed)) { |
| // If we fail, update the new node to point to the new head and try to |
| // insert before the new |
| // first element. |
| N->Next = OldFirst; |
| } |
| } |
| |
| /// Points to the first link in the list. |
| std::atomic<ConcurrentListNode<ElemTy> *> First; |
| }; |
| |
| /// A utility function for ordering two integers, which is useful |
| /// for implementing compareWithKey. |
| template <class T> |
| static inline int compareIntegers(T left, T right) { |
| return (left == right ? 0 : left < right ? -1 : 1); |
| } |
| |
| /// A utility function for ordering two pointers, which is useful |
| /// for implementing compareWithKey. |
| template <class T> |
| static inline int comparePointers(const T *left, const T *right) { |
| return (left == right ? 0 : std::less<const T *>()(left, right) ? -1 : 1); |
| } |
| |
| template <class EntryTy, bool ProvideDestructor, class Allocator> |
| class ConcurrentMapBase; |
| |
| /// The partial specialization of ConcurrentMapBase whose destructor is |
| /// trivial. The other implementation inherits from this, so this is a |
| /// base for all ConcurrentMaps. |
| template <class EntryTy, class Allocator> |
| class ConcurrentMapBase<EntryTy, false, Allocator> : protected Allocator { |
| protected: |
| struct Node { |
| std::atomic<Node*> Left; |
| std::atomic<Node*> Right; |
| EntryTy Payload; |
| |
| template <class... Args> |
| Node(Args &&... args) |
| : Left(nullptr), Right(nullptr), Payload(std::forward<Args>(args)...) {} |
| |
| Node(const Node &) = delete; |
| Node &operator=(const Node &) = delete; |
| |
| #ifndef NDEBUG |
| void dump() const { |
| auto L = Left.load(std::memory_order_acquire); |
| auto R = Right.load(std::memory_order_acquire); |
| printf("\"%p\" [ label = \" {<f0> %08lx | {<f1> | <f2>}}\" " |
| "style=\"rounded\" shape=\"record\"];\n", |
| this, (long) Payload.getKeyValueForDump()); |
| |
| if (L) { |
| L->dump(); |
| printf("\"%p\":f1 -> \"%p\":f0;\n", this, L); |
| } |
| if (R) { |
| R->dump(); |
| printf("\"%p\":f2 -> \"%p\":f0;\n", this, R); |
| } |
| } |
| #endif |
| }; |
| |
| std::atomic<Node*> Root; |
| |
| constexpr ConcurrentMapBase() : Root(nullptr) {} |
| |
| // Implicitly trivial destructor. |
| ~ConcurrentMapBase() = default; |
| |
| void destroyNode(Node *node) { |
| assert(node && "destroying null node"); |
| auto allocSize = sizeof(Node) + node->Payload.getExtraAllocationSize(); |
| |
| // Destroy the node's payload. |
| node->~Node(); |
| |
| // Deallocate the node. The static_cast here is required |
| // because LLVM's allocator API is insane. |
| this->Deallocate(static_cast<void*>(node), allocSize); |
| } |
| }; |
| |
| /// The partial specialization of ConcurrentMapBase which provides a |
| /// non-trivial destructor. |
| template <class EntryTy, class Allocator> |
| class ConcurrentMapBase<EntryTy, true, Allocator> |
| : protected ConcurrentMapBase<EntryTy, false, Allocator> { |
| protected: |
| using super = ConcurrentMapBase<EntryTy, false, Allocator>; |
| using Node = typename super::Node; |
| |
| constexpr ConcurrentMapBase() {} |
| |
| ~ConcurrentMapBase() { |
| destroyTree(this->Root); |
| } |
| |
| private: |
| void destroyTree(const std::atomic<Node*> &edge) { |
| // This can be a relaxed load because destruction is not allowed to race |
| // with other operations. |
| auto node = edge.load(std::memory_order_relaxed); |
| if (!node) return; |
| |
| // Destroy the node's children. |
| destroyTree(node->Left); |
| destroyTree(node->Right); |
| |
| // Destroy the node itself. |
| this->destroyNode(node); |
| } |
| }; |
| |
| /// A concurrent map that is implemented using a binary tree. It supports |
| /// concurrent insertions but does not support removals or rebalancing of |
| /// the tree. |
| /// |
| /// The entry type must provide the following operations: |
| /// |
| /// /// For debugging purposes only. Summarize this key as an integer value. |
| /// intptr_t getKeyIntValueForDump() const; |
| /// |
| /// /// A ternary comparison. KeyTy is the type of the key provided |
| /// /// to find or getOrInsert. |
| /// int compareWithKey(KeyTy key) const; |
| /// |
| /// /// Return the amount of extra trailing space required by an entry, |
| /// /// where KeyTy is the type of the first argument to getOrInsert and |
| /// /// ArgTys is the type of the remaining arguments. |
| /// static size_t getExtraAllocationSize(KeyTy key, ArgTys...) |
| /// |
| /// /// Return the amount of extra trailing space that was requested for |
| /// /// this entry. This method is only used to compute the size of the |
| /// /// object during node deallocation; it does not need to return a |
| /// /// correct value so long as the allocator's Deallocate implementation |
| /// /// ignores this argument. |
| /// size_t getExtraAllocationSize() const; |
| /// |
| /// If ProvideDestructor is false, the destructor will be trivial. This |
| /// can be appropriate when the object is declared at global scope. |
| template <class EntryTy, bool ProvideDestructor = true, |
| class Allocator = llvm::MallocAllocator> |
| class ConcurrentMap |
| : private ConcurrentMapBase<EntryTy, ProvideDestructor, Allocator> { |
| using super = ConcurrentMapBase<EntryTy, ProvideDestructor, Allocator>; |
| |
| using Node = typename super::Node; |
| |
| /// Inherited from base class: |
| /// std::atomic<Node*> Root; |
| using super::Root; |
| |
| /// This member stores the address of the last node that was found by the |
| /// search procedure. We cache the last search to accelerate code that |
| /// searches the same value in a loop. |
| std::atomic<Node*> LastSearch; |
| |
| public: |
| constexpr ConcurrentMap() : LastSearch(nullptr) {} |
| |
| ConcurrentMap(const ConcurrentMap &) = delete; |
| ConcurrentMap &operator=(const ConcurrentMap &) = delete; |
| |
| // ConcurrentMap<T, false> must have a trivial destructor. |
| ~ConcurrentMap() = default; |
| |
| public: |
| |
| Allocator &getAllocator() { |
| return *this; |
| } |
| |
| #ifndef NDEBUG |
| void dump() const { |
| auto R = Root.load(std::memory_order_acquire); |
| printf("digraph g {\n" |
| "graph [ rankdir = \"TB\"];\n" |
| "node [ fontsize = \"16\" ];\n" |
| "edge [ ];\n"); |
| if (R) { |
| R->dump(); |
| } |
| printf("\n}\n"); |
| } |
| #endif |
| |
| /// Search for a value by key \p Key. |
| /// \returns a pointer to the value or null if the value is not in the map. |
| template <class KeyTy> |
| EntryTy *find(const KeyTy &key) { |
| // Check if we are looking for the same key that we looked for in the last |
| // time we called this function. |
| if (Node *last = LastSearch.load(std::memory_order_acquire)) { |
| if (last->Payload.compareWithKey(key) == 0) |
| return &last->Payload; |
| } |
| |
| // Search the tree, starting from the root. |
| Node *node = Root.load(std::memory_order_acquire); |
| while (node) { |
| int comparisonResult = node->Payload.compareWithKey(key); |
| if (comparisonResult == 0) { |
| LastSearch.store(node, std::memory_order_release); |
| return &node->Payload; |
| } else if (comparisonResult < 0) { |
| node = node->Left.load(std::memory_order_acquire); |
| } else { |
| node = node->Right.load(std::memory_order_acquire); |
| } |
| } |
| |
| return nullptr; |
| } |
| |
| /// Get or create an entry in the map. |
| /// |
| /// \returns the entry in the map and whether a new node was added (true) |
| /// or already existed (false) |
| template <class KeyTy, class... ArgTys> |
| std::pair<EntryTy*, bool> getOrInsert(KeyTy key, ArgTys &&... args) { |
| // Check if we are looking for the same key that we looked for the |
| // last time we called this function. |
| if (Node *last = LastSearch.load(std::memory_order_acquire)) { |
| if (last && last->Payload.compareWithKey(key) == 0) |
| return { &last->Payload, false }; |
| } |
| |
| // The node we allocated. |
| Node *newNode = nullptr; |
| |
| // Start from the root. |
| auto edge = &Root; |
| |
| while (true) { |
| // Load the edge. |
| Node *node = edge->load(std::memory_order_acquire); |
| |
| // If there's a node there, it's either a match or we're going to |
| // one of its children. |
| if (node) { |
| searchFromNode: |
| |
| // Compare our key against the node's key. |
| int comparisonResult = node->Payload.compareWithKey(key); |
| |
| // If it's equal, we can use this node. |
| if (comparisonResult == 0) { |
| // Destroy the node we allocated before if we're carrying one around. |
| if (newNode) this->destroyNode(newNode); |
| |
| // Cache and report that we found an existing node. |
| LastSearch.store(node, std::memory_order_release); |
| return { &node->Payload, false }; |
| } |
| |
| // Otherwise, select the appropriate child edge and descend. |
| edge = (comparisonResult < 0 ? &node->Left : &node->Right); |
| continue; |
| } |
| |
| // Create a new node. |
| if (!newNode) { |
| size_t allocSize = |
| sizeof(Node) + EntryTy::getExtraAllocationSize(key, args...); |
| void *memory = this->Allocate(allocSize, alignof(Node)); |
| newNode = ::new (memory) Node(key, std::forward<ArgTys>(args)...); |
| } |
| |
| // Try to set the edge to the new node. |
| if (std::atomic_compare_exchange_strong_explicit(edge, &node, newNode, |
| std::memory_order_acq_rel, |
| std::memory_order_acquire)) { |
| // If that succeeded, cache and report that we created a new node. |
| LastSearch.store(newNode, std::memory_order_release); |
| return { &newNode->Payload, true }; |
| } |
| |
| // Otherwise, we lost the race because some other thread initialized |
| // the edge before us. node will be set to the current value; |
| // repeat the search from there. |
| assert(node && "spurious failure from compare_exchange_strong?"); |
| goto searchFromNode; |
| } |
| } |
| }; |
| |
| |
| /// An append-only array that can be read without taking locks. Writes |
| /// are still locked and serialized, but only with respect to other |
| /// writes. |
| template <class ElemTy> struct ConcurrentReadableArray { |
| private: |
| /// The struct used for the array's storage. The `Elem` member is |
| /// considered to be the first element of a variable-length array, |
| /// whose size is determined by the allocation. The `Capacity` member |
| /// from `ConcurrentReadableArray` indicates how large it can be. |
| struct Storage { |
| std::atomic<size_t> Count; |
| typename std::aligned_storage<sizeof(ElemTy), alignof(ElemTy)>::type Elem; |
| |
| static Storage *allocate(size_t capacity) { |
| auto size = sizeof(Storage) + (capacity - 1) * sizeof(Storage().Elem); |
| auto *ptr = reinterpret_cast<Storage *>(malloc(size)); |
| if (!ptr) swift::crash("Could not allocate memory."); |
| ptr->Count.store(0, std::memory_order_relaxed); |
| return ptr; |
| } |
| |
| void deallocate() { |
| for (size_t i = 0; i < Count; i++) { |
| data()[i].~ElemTy(); |
| } |
| free(this); |
| } |
| |
| ElemTy *data() { |
| return reinterpret_cast<ElemTy *>(&Elem); |
| } |
| }; |
| |
| size_t Capacity; |
| std::atomic<size_t> ReaderCount; |
| std::atomic<Storage *> Elements; |
| Mutex WriterLock; |
| std::vector<Storage *> FreeList; |
| |
| void incrementReaders() { |
| ReaderCount.fetch_add(1, std::memory_order_acquire); |
| } |
| |
| void decrementReaders() { |
| ReaderCount.fetch_sub(1, std::memory_order_release); |
| } |
| |
| void deallocateFreeList() { |
| for (Storage *storage : FreeList) |
| storage->deallocate(); |
| FreeList.clear(); |
| FreeList.shrink_to_fit(); |
| } |
| |
| public: |
| struct Snapshot { |
| ConcurrentReadableArray *Array; |
| const ElemTy *Start; |
| size_t Count; |
| |
| Snapshot(ConcurrentReadableArray *array, const ElemTy *start, size_t count) |
| : Array(array), Start(start), Count(count) {} |
| |
| Snapshot(const Snapshot &other) |
| : Array(other.Array), Start(other.Start), Count(other.Count) { |
| Array->incrementReaders(); |
| } |
| |
| ~Snapshot() { |
| Array->decrementReaders(); |
| } |
| |
| const ElemTy *begin() { return Start; } |
| const ElemTy *end() { return Start + Count; } |
| size_t count() { return Count; } |
| }; |
| |
| // This type cannot be safely copied, moved, or deleted. |
| ConcurrentReadableArray(const ConcurrentReadableArray &) = delete; |
| ConcurrentReadableArray(ConcurrentReadableArray &&) = delete; |
| ConcurrentReadableArray &operator=(const ConcurrentReadableArray &) = delete; |
| |
| ConcurrentReadableArray() : Capacity(0), ReaderCount(0), Elements(nullptr) {} |
| |
| ~ConcurrentReadableArray() { |
| assert(ReaderCount.load(std::memory_order_acquire) == 0 && |
| "deallocating ConcurrentReadableArray with outstanding snapshots"); |
| deallocateFreeList(); |
| } |
| |
| void push_back(const ElemTy &elem) { |
| ScopedLock guard(WriterLock); |
| |
| auto *storage = Elements.load(std::memory_order_relaxed); |
| auto count = storage ? storage->Count.load(std::memory_order_relaxed) : 0; |
| if (count >= Capacity) { |
| auto newCapacity = std::max((size_t)16, count * 2); |
| auto *newStorage = Storage::allocate(newCapacity); |
| if (storage) { |
| std::copy(storage->data(), storage->data() + count, newStorage->data()); |
| newStorage->Count.store(count, std::memory_order_relaxed); |
| FreeList.push_back(storage); |
| } |
| |
| storage = newStorage; |
| Capacity = newCapacity; |
| Elements.store(storage, std::memory_order_release); |
| } |
| |
| new(&storage->data()[count]) ElemTy(elem); |
| storage->Count.store(count + 1, std::memory_order_release); |
| |
| if (ReaderCount.load(std::memory_order_acquire) == 0) |
| deallocateFreeList(); |
| } |
| |
| Snapshot snapshot() { |
| incrementReaders(); |
| auto *storage = Elements.load(SWIFT_MEMORY_ORDER_CONSUME); |
| if (storage == nullptr) { |
| return Snapshot(this, nullptr, 0); |
| } |
| |
| auto count = storage->Count.load(std::memory_order_acquire); |
| const auto *ptr = storage->data(); |
| return Snapshot(this, ptr, count); |
| } |
| }; |
| |
| } // end namespace swift |
| |
| #endif // SWIFT_RUNTIME_CONCURRENTUTILS_H |