• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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