stdlib/public/runtime/MetadataCache.h - third_party/swift - Git at Google

 //===--- MetadataCache.h - Implements the metadata cache --------*- 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_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 {

 class MetadataAllocator : public llvm::AllocatorBase<MetadataAllocator> {
 public:
   void Reset() {}

   LLVM_ATTRIBUTE_RETURNS_NONNULL void *Allocate(size_t size, size_t alignment);
   using AllocatorBase<MetadataAllocator>::Allocate;

   void Deallocate(const void *Ptr, size_t size);
   using AllocatorBase<MetadataAllocator>::Deallocate;

   void PrintStats() const {}
 };

 /// A typedef for simple global caches.
 template <class EntryTy>
 using SimpleGlobalCache =
   ConcurrentMap<EntryTy, /*destructor*/ false, MetadataAllocator>;

 // 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 {};

 /// 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.Allocate(sizeof(Impl)  +
                                       numArguments * sizeof(void*) +
                                       payloadSize,
                                       alignof(Impl));
     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);
     }

     intptr_t getKeyIntValueForDump() const {
       return Hash;
     }

     static size_t getExtraAllocationSize(const Key &key) {
       return key.KeyData.size() * sizeof(void*);
     }
     size_t getExtraAllocationSize() const {
       return getKeyData().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, /*Destructor*/ false, MetadataAllocator> Map;

   struct ConcurrencyControl {
     Mutex Lock;
     ConditionVariable Queue;
   };
   std::unique_ptr<ConcurrencyControl> Concurrency;

 public:
   MetadataCache() : Concurrency(new ConcurrencyControl()) {}
   ~MetadataCache() = default;

   /// 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 Map.getAllocator(); }

   /// 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",
            ValueTy::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 %zu\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();

 #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
	//===--- MetadataCache.h - Implements the metadata cache --------- 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_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 {

	class MetadataAllocator : public llvm::AllocatorBase<MetadataAllocator> {
	public:
	void Reset() {}

	LLVM_ATTRIBUTE_RETURNS_NONNULL void *Allocate(size_t size, size_t alignment);
	using AllocatorBase<MetadataAllocator>::Allocate;

	void Deallocate(const void *Ptr, size_t size);
	using AllocatorBase<MetadataAllocator>::Deallocate;

	void PrintStats() const {}
	};

	/// A typedef for simple global caches.
	template <class EntryTy>
	using SimpleGlobalCache =
	ConcurrentMap<EntryTy, /destructor/ false, MetadataAllocator>;

	// 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 {};

	/// 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.Allocate(sizeof(Impl) +
	numArguments * sizeof(void*) +
	payloadSize,
	alignof(Impl));
	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);
	}

	intptr_t getKeyIntValueForDump() const {
	return Hash;
	}

	static size_t getExtraAllocationSize(const Key &key) {
	return key.KeyData.size() * sizeof(void*);
	}
	size_t getExtraAllocationSize() const {
	return getKeyData().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, /Destructor/ false, MetadataAllocator> Map;

	struct ConcurrencyControl {
	Mutex Lock;
	ConditionVariable Queue;
	};
	std::unique_ptr<ConcurrencyControl> Concurrency;

	public:
	MetadataCache() : Concurrency(new ConcurrencyControl()) {}
	~MetadataCache() = default;

	/// 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 Map.getAllocator(); }

	/// 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",
	ValueTy::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 %zu\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();

	#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