1 /* Copyright (c) 2015-2017, 2019 The Khronos Group Inc. 2 * Copyright (c) 2015-2017, 2019 Valve Corporation 3 * Copyright (c) 2015-2017, 2019 LunarG, Inc. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 * Author: Mark Lobodzinski <mark@lunarg.com> 18 * Author: Courtney Goeltzenleuchter <courtney@LunarG.com> 19 * Author: Dave Houlton <daveh@lunarg.com> 20 */ 21 22 #pragma once 23 24 #include <cassert> 25 #include <cstddef> 26 #include <functional> 27 #include <stdbool.h> 28 #include <string> 29 #include <vector> 30 #include <set> 31 #include "cast_utils.h" 32 #include "vk_format_utils.h" 33 #include "vk_layer_logging.h" 34 35 #ifndef WIN32 36 #include <strings.h> // For ffs() 37 #else 38 #include <intrin.h> // For __lzcnt() 39 #endif 40 41 #ifdef __cplusplus 42 // Traits objects to allow string_join to operate on collections of const char * 43 template <typename String> 44 struct StringJoinSizeTrait { sizeStringJoinSizeTrait45 static size_t size(const String &str) { return str.size(); } 46 }; 47 48 template <> 49 struct StringJoinSizeTrait<const char *> { 50 static size_t size(const char *str) { 51 if (!str) return 0; 52 return strlen(str); 53 } 54 }; 55 // Similar to perl/python join 56 // * String must support size, reserve, append, and be default constructable 57 // * StringCollection must support size, const forward iteration, and store 58 // strings compatible with String::append 59 // * Accessor trait can be set if default accessors (compatible with string 60 // and const char *) don't support size(StringCollection::value_type &) 61 // 62 // Return type based on sep type 63 template <typename String = std::string, typename StringCollection = std::vector<String>, 64 typename Accessor = StringJoinSizeTrait<typename StringCollection::value_type>> 65 static inline String string_join(const String &sep, const StringCollection &strings) { 66 String joined; 67 const size_t count = strings.size(); 68 if (!count) return joined; 69 70 // Prereserved storage, s.t. we will execute in linear time (avoids reallocation copies) 71 size_t reserve = (count - 1) * sep.size(); 72 for (const auto &str : strings) { 73 reserve += Accessor::size(str); // abstracted to allow const char * type in StringCollection 74 } 75 joined.reserve(reserve + 1); 76 77 // Seps only occur *between* strings entries, so first is special 78 auto current = strings.cbegin(); 79 joined.append(*current); 80 ++current; 81 for (; current != strings.cend(); ++current) { 82 joined.append(sep); 83 joined.append(*current); 84 } 85 return joined; 86 } 87 88 // Requires StringCollection::value_type has a const char * constructor and is compatible the string_join::String above 89 template <typename StringCollection = std::vector<std::string>, typename SepString = std::string> 90 static inline SepString string_join(const char *sep, const StringCollection &strings) { 91 return string_join<SepString, StringCollection>(SepString(sep), strings); 92 } 93 94 // Perl/Python style join operation for general types using stream semantics 95 // Note: won't be as fast as string_join above, but simpler to use (and code) 96 // Note: Modifiable reference doesn't match the google style but does match std style for stream handling and algorithms 97 template <typename Stream, typename String, typename ForwardIt> 98 Stream &stream_join(Stream &stream, const String &sep, ForwardIt first, ForwardIt last) { 99 if (first != last) { 100 stream << *first; 101 ++first; 102 while (first != last) { 103 stream << sep << *first; 104 ++first; 105 } 106 } 107 return stream; 108 } 109 110 // stream_join For whole collections with forward iterators 111 template <typename Stream, typename String, typename Collection> 112 Stream &stream_join(Stream &stream, const String &sep, const Collection &values) { 113 return stream_join(stream, sep, values.cbegin(), values.cend()); 114 } 115 116 typedef void *dispatch_key; 117 static inline dispatch_key get_dispatch_key(const void *object) { return (dispatch_key) * (VkLayerDispatchTable **)object; } 118 119 VK_LAYER_EXPORT VkLayerInstanceCreateInfo *get_chain_info(const VkInstanceCreateInfo *pCreateInfo, VkLayerFunction func); 120 VK_LAYER_EXPORT VkLayerDeviceCreateInfo *get_chain_info(const VkDeviceCreateInfo *pCreateInfo, VkLayerFunction func); 121 122 static inline bool IsPowerOfTwo(unsigned x) { return x && !(x & (x - 1)); } 123 124 extern "C" { 125 #endif 126 127 #define VK_LAYER_API_VERSION VK_MAKE_VERSION(1, 0, VK_HEADER_VERSION) 128 129 typedef enum VkStringErrorFlagBits { 130 VK_STRING_ERROR_NONE = 0x00000000, 131 VK_STRING_ERROR_LENGTH = 0x00000001, 132 VK_STRING_ERROR_BAD_DATA = 0x00000002, 133 } VkStringErrorFlagBits; 134 typedef VkFlags VkStringErrorFlags; 135 136 VK_LAYER_EXPORT void layer_debug_report_actions(debug_report_data *report_data, 137 std::vector<VkDebugReportCallbackEXT> &logging_callback, 138 const VkAllocationCallbacks *pAllocator, const char *layer_identifier); 139 140 VK_LAYER_EXPORT void layer_debug_messenger_actions(debug_report_data *report_data, 141 std::vector<VkDebugUtilsMessengerEXT> &logging_messenger, 142 const VkAllocationCallbacks *pAllocator, const char *layer_identifier); 143 144 VK_LAYER_EXPORT VkStringErrorFlags vk_string_validate(const int max_length, const char *char_array); 145 VK_LAYER_EXPORT bool white_list(const char *item, const std::set<std::string> &whitelist); 146 147 static inline int u_ffs(int val) { 148 #ifdef WIN32 149 unsigned long bit_pos = 0; 150 if (_BitScanForward(&bit_pos, val) != 0) { 151 bit_pos += 1; 152 } 153 return bit_pos; 154 #else 155 return ffs(val); 156 #endif 157 } 158 159 #ifdef __cplusplus 160 } 161 #endif 162 163 // shared_mutex support added in MSVC 2015 update 2 164 #if defined(_MSC_FULL_VER) && _MSC_FULL_VER >= 190023918 && NTDDI_VERSION > NTDDI_WIN10_RS2 165 #include <shared_mutex> 166 #endif 167 168 // Limited concurrent_unordered_map that supports internally-synchronized 169 // insert/erase/access. Splits locking across N buckets and uses shared_mutex 170 // for read/write locking. Iterators are not supported. The following 171 // operations are supported: 172 // 173 // insert_or_assign: Insert a new element or update an existing element. 174 // insert: Insert a new element and return whether it was inserted. 175 // erase: Remove an element. 176 // contains: Returns true if the key is in the map. 177 // find: Returns != end() if found, value is in ret->second. 178 // pop: Erases and returns the erased value if found. 179 // 180 // find/end: find returns a vaguely iterator-like type that can be compared to 181 // end and can use iter->second to retrieve the reference. This is to ease porting 182 // for existing code that combines the existence check and lookup in a single 183 // operation (and thus a single lock). i.e.: 184 // 185 // auto iter = map.find(key); 186 // if (iter != map.end()) { 187 // T t = iter->second; 188 // ... 189 // 190 // snapshot: Return an array of elements (key, value pairs) that satisfy an optional 191 // predicate. This can be used as a substitute for iterators in exceptional cases. 192 template <typename Key, typename T, int BUCKETSLOG2 = 2> 193 class vl_concurrent_unordered_map { 194 public: 195 void insert_or_assign(const Key &key, const T &value) { 196 uint32_t h = ConcurrentMapHashObject(key); 197 write_lock_guard_t lock(locks[h].lock); 198 maps[h][key] = value; 199 } 200 201 bool insert(const Key &key, const T &value) { 202 uint32_t h = ConcurrentMapHashObject(key); 203 write_lock_guard_t lock(locks[h].lock); 204 auto ret = maps[h].insert(typename std::unordered_map<Key, T>::value_type(key, value)); 205 return ret.second; 206 } 207 208 // returns size_type 209 size_t erase(const Key &key) { 210 uint32_t h = ConcurrentMapHashObject(key); 211 write_lock_guard_t lock(locks[h].lock); 212 return maps[h].erase(key); 213 } 214 215 bool contains(const Key &key) { 216 uint32_t h = ConcurrentMapHashObject(key); 217 read_lock_guard_t lock(locks[h].lock); 218 return maps[h].count(key) != 0; 219 } 220 221 // type returned by find() and end(). 222 class FindResult { 223 public: 224 FindResult(bool a, T b) : result(a, std::move(b)) {} 225 226 // == and != only support comparing against end() 227 bool operator==(const FindResult &other) const { 228 if (result.first == false && other.result.first == false) { 229 return true; 230 } 231 return false; 232 } 233 bool operator!=(const FindResult &other) const { return !(*this == other); } 234 235 // Make -> act kind of like an iterator. 236 std::pair<bool, T> *operator->() { return &result; } 237 const std::pair<bool, T> *operator->() const { return &result; } 238 239 private: 240 // (found, reference to element) 241 std::pair<bool, T> result; 242 }; 243 244 // find()/end() return a FindResult containing a copy of the value. For end(), 245 // return a default value. 246 FindResult end() { return FindResult(false, T()); } 247 248 FindResult find(const Key &key) { 249 uint32_t h = ConcurrentMapHashObject(key); 250 read_lock_guard_t lock(locks[h].lock); 251 252 auto itr = maps[h].find(key); 253 bool found = itr != maps[h].end(); 254 255 if (found) { 256 return FindResult(true, itr->second); 257 } else { 258 return end(); 259 } 260 } 261 262 FindResult pop(const Key &key) { 263 uint32_t h = ConcurrentMapHashObject(key); 264 write_lock_guard_t lock(locks[h].lock); 265 266 auto itr = maps[h].find(key); 267 bool found = itr != maps[h].end(); 268 269 if (found) { 270 auto ret = std::move(FindResult(true, itr->second)); 271 maps[h].erase(itr); 272 return ret; 273 } else { 274 return end(); 275 } 276 } 277 278 std::vector<std::pair<const Key, T>> snapshot(std::function<bool(T)> f = nullptr) { 279 std::vector<std::pair<const Key, T>> ret; 280 for (int h = 0; h < BUCKETS; ++h) { 281 read_lock_guard_t lock(locks[h].lock); 282 for (auto j : maps[h]) { 283 if (!f || f(j.second)) { 284 ret.push_back(j); 285 } 286 } 287 } 288 return ret; 289 } 290 291 private: 292 static const int BUCKETS = (1 << BUCKETSLOG2); 293 // shared_mutex support added in MSVC 2015 update 2 294 #if defined(_MSC_FULL_VER) && _MSC_FULL_VER >= 190023918 && NTDDI_VERSION > NTDDI_WIN10_RS2 295 #include <shared_mutex> 296 typedef std::shared_mutex lock_t; 297 typedef std::shared_lock<lock_t> read_lock_guard_t; 298 typedef std::unique_lock<lock_t> write_lock_guard_t; 299 #else 300 typedef std::mutex lock_t; 301 typedef std::unique_lock<lock_t> read_lock_guard_t; 302 typedef std::unique_lock<lock_t> write_lock_guard_t; 303 #endif 304 305 std::unordered_map<Key, T> maps[BUCKETS]; 306 struct { 307 lock_t lock; 308 // Put each lock on its own cache line to avoid false cache line sharing. 309 char padding[(-int(sizeof(lock_t))) & 63]; 310 } locks[BUCKETS]; 311 312 uint32_t ConcurrentMapHashObject(const Key &object) const { 313 uint64_t u64 = (uint64_t)(uintptr_t)object; 314 uint32_t hash = (uint32_t)(u64 >> 32) + (uint32_t)u64; 315 hash ^= (hash >> BUCKETSLOG2) ^ (hash >> (2 * BUCKETSLOG2)); 316 hash &= (BUCKETS - 1); 317 return hash; 318 } 319 }; 320