| //===--- MetadataCache.h - Implements the metadata cache --------*- C++ -*-===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See http://swift.org/LICENSE.txt for license information |
| // See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| #ifndef SWIFT_RUNTIME_METADATACACHE_H |
| #define SWIFT_RUNTIME_METADATACACHE_H |
| |
| #include "llvm/ADT/Hashing.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "swift/Runtime/Concurrent.h" |
| #include "swift/Runtime/Metadata.h" |
| #include "swift/Runtime/Mutex.h" |
| #include <condition_variable> |
| #include <thread> |
| |
| #ifndef SWIFT_DEBUG_RUNTIME |
| #define SWIFT_DEBUG_RUNTIME 0 |
| #endif |
| |
| namespace swift { |
| |
| /// A bump pointer for metadata allocations. Since metadata is (currently) |
| /// never released, it does not support deallocation. This allocator by itself |
| /// is not thread-safe; in concurrent uses, allocations must be guarded by |
| /// a lock, such as the per-metadata-cache lock used to guard metadata |
| /// instantiations. All allocations are pointer-aligned. |
| class MetadataAllocator { |
| /// Address of the next available space. The allocator grabs a page at a time, |
| /// so the need for a new page can be determined by page alignment. |
| /// |
| /// Initializing to -1 instead of nullptr ensures that the first allocation |
| /// triggers a page allocation since it will always span a "page" boundary. |
| std::atomic<uintptr_t> NextValue; |
| |
| public: |
| constexpr MetadataAllocator() : NextValue(~(uintptr_t)0) {} |
| |
| // Don't copy or move, please. |
| MetadataAllocator(const MetadataAllocator &) = delete; |
| MetadataAllocator(MetadataAllocator &&) = delete; |
| MetadataAllocator &operator=(const MetadataAllocator &) = delete; |
| MetadataAllocator &operator=(MetadataAllocator &&) = delete; |
| |
| void *alloc(size_t size); |
| }; |
| |
| // A wrapper around a pointer to a metadata cache entry that provides |
| // DenseMap semantics that compare values in the key vector for the metadata |
| // instance. |
| // |
| // This is stored as a pointer to the arguments buffer, so that we can save |
| // an offset while looking for the matching argument given a key. |
| class KeyDataRef { |
| const void * const *Args; |
| unsigned Length; |
| |
| KeyDataRef(const void * const *args, unsigned length) |
| : Args(args), Length(length) {} |
| |
| public: |
| template <class Entry> |
| static KeyDataRef forEntry(const Entry *e, unsigned numArguments) { |
| return KeyDataRef(e->getArgumentsBuffer(), numArguments); |
| } |
| |
| static KeyDataRef forArguments(const void * const *args, |
| unsigned numArguments) { |
| return KeyDataRef(args, numArguments); |
| } |
| |
| template <class Entry> |
| const Entry *getEntry() const { |
| return Entry::fromArgumentsBuffer(Args, Length); |
| } |
| |
| bool operator==(KeyDataRef rhs) const { |
| // Compare the sizes. |
| unsigned asize = size(), bsize = rhs.size(); |
| if (asize != bsize) return false; |
| |
| // Compare the content. |
| auto abegin = begin(), bbegin = rhs.begin(); |
| for (unsigned i = 0; i < asize; ++i) |
| if (abegin[i] != bbegin[i]) return false; |
| return true; |
| } |
| |
| int compare(KeyDataRef rhs) const { |
| // Compare the sizes. |
| unsigned asize = size(), bsize = rhs.size(); |
| if (asize != bsize) { |
| return (asize < bsize ? -1 : 1); |
| } |
| |
| // Compare the content. |
| auto abegin = begin(), bbegin = rhs.begin(); |
| for (unsigned i = 0; i < asize; ++i) { |
| if (abegin[i] != bbegin[i]) |
| return (uintptr_t(abegin[i]) < uintptr_t(bbegin[i]) ? -1 : 1); |
| } |
| |
| return 0; |
| } |
| |
| size_t hash() { |
| size_t H = 0x56ba80d1 * Length ; |
| for (unsigned i = 0; i < Length; i++) { |
| H = (H >> 10) | (H << ((sizeof(size_t) * 8) - 10)); |
| H ^= ((size_t)Args[i]) ^ ((size_t)Args[i] >> 19); |
| } |
| H *= 0x27d4eb2d; |
| return (H >> 10) | (H << ((sizeof(size_t) * 8) - 10)); |
| } |
| |
| const void * const *begin() const { return Args; } |
| const void * const *end() const { return Args + Length; } |
| unsigned size() const { return Length; } |
| }; |
| |
| template <class Impl> |
| struct CacheEntryHeader { |
| /// LLDB walks this list. |
| /// FIXME: when LLDB stops walking this list, there will stop being |
| /// any reason to store argument data in cache entries, and a *ton* |
| /// of weird stuff here will go away. |
| const Impl *Next; |
| }; |
| |
| /// A CRTP class for defining entries in a metadata cache. |
| template <class Impl, class Header = CacheEntryHeader<Impl> > |
| class alignas(void*) CacheEntry : public Header { |
| |
| CacheEntry(const CacheEntry &other) = delete; |
| void operator=(const CacheEntry &other) = delete; |
| |
| Impl *asImpl() { return static_cast<Impl*>(this); } |
| const Impl *asImpl() const { return static_cast<const Impl*>(this); } |
| |
| protected: |
| CacheEntry() = default; |
| |
| public: |
| static Impl *allocate(MetadataAllocator &allocator, |
| const void * const *arguments, |
| size_t numArguments, size_t payloadSize) { |
| void *buffer = allocator.alloc(sizeof(Impl) + |
| numArguments * sizeof(void*) + |
| payloadSize); |
| void *resultPtr = (char*)buffer + numArguments * sizeof(void*); |
| auto result = new (resultPtr) Impl(numArguments); |
| |
| // Copy the arguments into the right place for the key. |
| memcpy(buffer, arguments, |
| numArguments * sizeof(void*)); |
| |
| return result; |
| } |
| |
| void **getArgumentsBuffer() { |
| return reinterpret_cast<void**>(this) - asImpl()->getNumArguments(); |
| } |
| |
| void * const *getArgumentsBuffer() const { |
| return reinterpret_cast<void * const *>(this) |
| - asImpl()->getNumArguments(); |
| } |
| |
| template <class T> T *getData() { |
| return reinterpret_cast<T *>(asImpl() + 1); |
| } |
| |
| template <class T> const T *getData() const { |
| return const_cast<CacheEntry*>(this)->getData<T>(); |
| } |
| |
| static const Impl *fromArgumentsBuffer(const void * const *argsBuffer, |
| unsigned numArguments) { |
| return reinterpret_cast<const Impl *>(argsBuffer + numArguments); |
| } |
| }; |
| |
| /// The implementation of a metadata cache. Note that all-zero must |
| /// be a valid state for the cache. |
| template <class ValueTy> class MetadataCache { |
| /// A key value as provided to the concurrent map. |
| struct Key { |
| size_t Hash; |
| KeyDataRef KeyData; |
| |
| Key(KeyDataRef data) : Hash(data.hash()), KeyData(data) {} |
| }; |
| |
| /// The layout of an entry in the concurrent map. |
| class Entry { |
| size_t Hash; |
| unsigned KeyLength; |
| |
| /// Does this entry have a value, or is it currently undergoing |
| /// initialization? |
| /// |
| /// This (and the following field) is ever modified under the lock, |
| /// but it can be read from any thread, including while the lock |
| /// is held. |
| std::atomic<bool> HasValue; |
| union { |
| ValueTy *Value; |
| std::thread::id InitializingThread; |
| }; |
| |
| const void **getKeyDataBuffer() { |
| return reinterpret_cast<const void **>(this + 1); |
| } |
| const void * const *getKeyDataBuffer() const { |
| return reinterpret_cast<const void * const *>(this + 1); |
| } |
| public: |
| Entry(const Key &key) |
| : Hash(key.Hash), KeyLength(key.KeyData.size()), HasValue(false) { |
| InitializingThread = std::this_thread::get_id(); |
| memcpy(getKeyDataBuffer(), key.KeyData.begin(), |
| KeyLength * sizeof(void*)); |
| } |
| |
| bool isBeingInitializedByCurrentThread() const { |
| return InitializingThread == std::this_thread::get_id(); |
| } |
| |
| KeyDataRef getKeyData() const { |
| return KeyDataRef::forArguments(getKeyDataBuffer(), KeyLength); |
| } |
| |
| long getKeyIntValueForDump() const { |
| return Hash; |
| } |
| |
| static size_t getExtraAllocationSize(const Key &key) { |
| return key.KeyData.size() * sizeof(void*); |
| } |
| |
| int compareWithKey(const Key &key) const { |
| // Order by hash first, then by the actual key data. |
| if (key.Hash != Hash) { |
| return (key.Hash < Hash ? -1 : 1); |
| } else { |
| return key.KeyData.compare(getKeyData()); |
| } |
| } |
| |
| ValueTy *getValue() const { |
| if (HasValue.load(std::memory_order_acquire)) { |
| return Value; |
| } |
| return nullptr; |
| } |
| |
| void setValue(ValueTy *value) { |
| Value = value; |
| HasValue.store(true, std::memory_order_release); |
| } |
| }; |
| |
| /// The concurrent map. |
| ConcurrentMap<Entry> Map; |
| |
| static_assert(sizeof(Map) == 2 * sizeof(void*), |
| "offset of Head is not at proper offset"); |
| |
| /// The head of a linked list connecting all the metadata cache entries. |
| /// TODO: Remove this when LLDB is able to understand the final data |
| /// structure for the metadata cache. |
| const ValueTy *Head; |
| |
| struct ConcurrencyControl { |
| Mutex Lock; |
| ConditionVariable Queue; |
| }; |
| std::unique_ptr<ConcurrencyControl> Concurrency; |
| |
| /// Allocator for entries of this cache. |
| MetadataAllocator Allocator; |
| |
| public: |
| MetadataCache() : Concurrency(new ConcurrencyControl()) {} |
| ~MetadataCache() {} |
| |
| /// Caches are not copyable. |
| MetadataCache(const MetadataCache &other) = delete; |
| MetadataCache &operator=(const MetadataCache &other) = delete; |
| |
| /// Get the allocator for metadata in this cache. |
| /// The allocator can only be safely used while the cache is locked during |
| /// an addMetadataEntry call. |
| MetadataAllocator &getAllocator() { return Allocator; } |
| |
| /// Look up a cached metadata entry. If a cache match exists, return it. |
| /// Otherwise, call entryBuilder() and add that to the cache. |
| const ValueTy *findOrAdd(const void * const *arguments, size_t numArguments, |
| llvm::function_ref<ValueTy *()> builder) { |
| |
| #if SWIFT_DEBUG_RUNTIME |
| printf("%s(%p): looking for entry with %zu arguments:\n", |
| Entry::getName(), this, numArguments); |
| for (size_t i = 0; i < numArguments; i++) { |
| printf("%s(%p): %p\n", ValueTy::getName(), this, arguments[i]); |
| } |
| #endif |
| |
| Key key(KeyDataRef::forArguments(arguments, numArguments)); |
| |
| #if SWIFT_DEBUG_RUNTIME |
| printf("%s(%p): generated hash %llx\n", |
| ValueTy::getName(), this, key.Hash); |
| #endif |
| |
| // Ensure the existence of a map entry. |
| auto insertResult = Map.getOrInsert(key); |
| Entry *entry = insertResult.first; |
| |
| // If we didn't insert the entry, then we just need to get the |
| // initialized value from the entry. |
| if (!insertResult.second) { |
| |
| // If the entry is already initialized, great. |
| auto value = entry->getValue(); |
| if (value) { |
| return value; |
| } |
| |
| // Otherwise, we have to grab the lock and wait for the value to |
| // appear there. Note that we have to check again immediately |
| // after acquiring the lock to prevent a race. |
| auto concurrency = Concurrency.get(); |
| concurrency->Lock.withLockOrWait(concurrency->Queue, [&, this] { |
| if ((value = entry->getValue())) { |
| return true; // found a value, done waiting |
| } |
| |
| // As a QoI safe-guard against the simplest form of cyclic |
| // dependency, check whether this thread is the one responsible |
| // for initializing the metadata. |
| if (entry->isBeingInitializedByCurrentThread()) { |
| fprintf(stderr, |
| "%s(%p): cyclic metadata dependency detected, aborting\n", |
| ValueTy::getName(), (void*) this); |
| abort(); |
| } |
| |
| return false; // don't have a value, continue waiting |
| }); |
| |
| return value; |
| } |
| |
| // Otherwise, we created the entry and are responsible for |
| // creating the metadata. |
| auto value = builder(); |
| |
| // Update the linked list. |
| value->Next = Head; |
| Head = value; |
| |
| #if SWIFT_DEBUG_RUNTIME |
| printf("%s(%p): created %p\n", |
| ValueTy::getName(), (void*) this, value); |
| #endif |
| |
| // Acquire the lock, set the value, and notify any waiters. |
| auto concurrency = Concurrency.get(); |
| concurrency->Lock.withLockThenNotifyAll( |
| concurrency->Queue, [&entry, &value] { entry->setValue(value); }); |
| |
| return value; |
| } |
| }; |
| |
| } // namespace swift |
| |
| #endif // SWIFT_RUNTIME_METADATACACHE_H |