Line data Source code
1 : /*
2 : ___________________________________________
3 : | _ ___ _ |
4 : | | | |__ \ | | |
5 : | | |__ ) |__ _ __ _ ___ _ __ | |_ |
6 : | | '_ \ / // _` |/ _` |/ _ \ '_ \| __| | HTTP/2 AGENT FOR MOCK TESTING
7 : | | | | |/ /| (_| | (_| | __/ | | | |_ | Version 0.0.z
8 : | |_| |_|____\__,_|\__, |\___|_| |_|\__| | https://github.com/testillano/h2agent
9 : | __/ | |
10 : | |___/ |
11 : |___________________________________________|
12 :
13 : Licensed under the MIT License <http://opensource.org/licenses/MIT>.
14 : SPDX-License-Identifier: MIT
15 : Copyright (c) 2021 Eduardo Ramos
16 :
17 : Permission is hereby granted, free of charge, to any person obtaining a copy
18 : of this software and associated documentation files (the "Software"), to deal
19 : in the Software without restriction, including without limitation the rights
20 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
21 : copies of the Software, and to permit persons to whom the Software is
22 : furnished to do so, subject to the following conditions:
23 :
24 : The above copyright notice and this permission notice shall be included in all
25 : copies or substantial portions of the Software.
26 :
27 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
28 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
29 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
30 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
31 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
32 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
33 : SOFTWARE.
34 : */
35 :
36 : #pragma once
37 :
38 : // Better unordered_map than map:
39 : // Slighly more memory consumption (not significative in load tests) due to the hash map.
40 : // But order is not important for us, and the size is not very big (prune is normally
41 : // applied in load test provisions), so the cache is not used.
42 : // As insertion and deletion are equally fast for both containers, we focus on search
43 : // (O(log2(n)) for map as binary tree, O(1) constant as average (O(n) in worst case)
44 : // for unordered map as hash table), so for our case, unordered_map seems to be the best choice.
45 : #include <array>
46 : #include <functional>
47 : #include <unordered_map>
48 :
49 : #include <common.hpp>
50 :
51 : #include <nlohmann/json.hpp>
52 :
53 :
54 : namespace h2agent
55 : {
56 : namespace model
57 : {
58 :
59 : /**
60 : * Thread-safe associative map with OPT-IN mutex sharding.
61 : *
62 : * @tparam Key key type
63 : * @tparam Value value type
64 : * @tparam Shards number of independent lock shards (default 1).
65 : *
66 : * With \c Shards == 1 (the default) this is byte-for-byte the historical
67 : * single-\c shared_mutex map: every existing user (event stores, etc.) keeps
68 : * exactly the old behaviour with zero extra overhead.
69 : *
70 : * With \c Shards > 1 the keyspace is partitioned across N independent
71 : * (\c mutex, \c unordered_map) shards, routed by \c std::hash(key) % Shards:
72 : * - PER-KEY operations (get/tryGet/exists/add/remove/modifyOrInsert) lock ONLY
73 : * the shard owning the key, so writes to independent keys from different
74 : * threads do not serialize against each other. This is the hot-traffic win
75 : * (e.g. a provision touching many vault keys under high concurrency).
76 : * - WHOLE-MAP operations (size/empty/forEach/getJson/clear/copy) must observe
77 : * every shard, so they lock ALL shards in a FIXED ascending order (which is
78 : * deadlock-free). These are administrative/report paths (e.g.
79 : * GET /admin/v1/vault), NOT the traffic hot path, so global locking there is
80 : * acceptable by design.
81 : *
82 : * Per-key atomicity of \c modifyOrInsert (read-modify-write under one lock) is
83 : * preserved in both modes.
84 : */
85 : template<typename Key, typename Value, std::size_t Shards = 1>
86 : class Map {
87 :
88 : static_assert(Shards >= 1, "Map requires at least one shard");
89 :
90 : typedef typename std::unordered_map<Key, Value> map_t;
91 : using IterationCallback = std::function<void(const Key&, const Value&)>;
92 :
93 : struct Shard {
94 : mutable mutex_t mutex_{};
95 : map_t map_{};
96 : };
97 :
98 : std::array<Shard, Shards> shards_{};
99 :
100 : // Route a key to its shard. For Shards==1 this is a no-op (index 0), so the
101 : // hash is not even computed on the single-shard hot path.
102 117351 : Shard& shardFor(const Key& key) {
103 753 : if constexpr (Shards == 1) return shards_[0];
104 116598 : else return shards_[std::hash<Key>{}(key) % Shards];
105 : }
106 990 : const Shard& shardFor(const Key& key) const {
107 440 : if constexpr (Shards == 1) return shards_[0];
108 550 : else return shards_[std::hash<Key>{}(key) % Shards];
109 : }
110 :
111 : public:
112 :
113 19746 : Map() {};
114 :
115 : /** copy constructor: snapshot every shard of 'other' under read locks
116 : * (fixed ascending order), then copy into our matching shards. */
117 9 : Map(const Map& other) {
118 9 : for (std::size_t i = 0; i < Shards; ++i) {
119 8 : read_guard_t guard(other.shards_[i].mutex_);
120 8 : shards_[i].map_ = other.shards_[i].map_;
121 : }
122 1 : }
123 :
124 2713 : ~Map() = default;
125 :
126 : // getters
127 :
128 169 : bool exists(const Key& key) const
129 : {
130 169 : const Shard& s = shardFor(key);
131 169 : read_guard_t guard(s.mutex_);
132 338 : return (s.map_.find(key) != s.map_.end());
133 169 : }
134 :
135 : /**
136 : * Searchs map key
137 : *
138 : * @param key key to find
139 : * @param exits written by reference
140 : * @return Value for provided key, or initizalized Value when key is missing
141 : */
142 640 : Value get(const Key& key, bool &exists) const
143 : {
144 640 : const Shard& s = shardFor(key);
145 640 : read_guard_t guard(s.mutex_);
146 640 : auto it = s.map_.find(key);
147 640 : exists = (it != s.map_.end());
148 1280 : return (exists ? it->second : Value{}); // return copy
149 640 : }
150 :
151 : /**
152 : * Getter which avoid copy of empty value and is more readable than get()
153 : */
154 181 : bool tryGet(const Key& key, Value& out_value) const {
155 181 : const Shard& s = shardFor(key);
156 181 : read_guard_t guard(s.mutex_);
157 181 : auto it = s.map_.find(key);
158 181 : if (it != s.map_.end()) {
159 108 : out_value = it->second;
160 108 : return true;
161 : }
162 73 : return false;
163 181 : }
164 :
165 : /** map size (sum across shards; each shard read-locked in turn) */
166 373 : size_t size() const
167 : {
168 373 : size_t total = 0;
169 1554 : for (const auto& s : shards_) {
170 1181 : read_guard_t guard(s.mutex_);
171 1181 : total += s.map_.size();
172 : }
173 373 : return total;
174 : }
175 :
176 16 : bool empty() const
177 : {
178 328 : for (const auto& s : shards_) {
179 163 : read_guard_t guard(s.mutex_);
180 163 : if (!s.map_.empty()) return false;
181 : }
182 2 : return true;
183 : }
184 :
185 : /**
186 : * @brief Iterates safely over all elements in the map.
187 : * * This method provides **read access** to the map's elements in a **thread-safe** manner
188 : * by applying a user-defined callback function to each key-value pair. With sharding, ALL
189 : * shards are read-locked in fixed ascending order for the full iteration (a consistent
190 : * snapshot). Admin/report path -- keep callbacks short.
191 : *
192 : * @param callback A function applied to every key-value pair, signature void(const Key&, const Value&).
193 : *
194 : * @note This function uses the callback pattern to prevent the exposure of unsafe iterators
195 : * (\c dangling iterators) to external threads.
196 : */
197 68 : void forEach(const IterationCallback& callback) const {
198 : // Lock all shards (ascending order) for a consistent whole-map view.
199 68 : std::array<read_guard_t, Shards> guards = lockAllShared();
200 623 : for (const auto& s : shards_) {
201 670 : for (const auto& pair : s.map_) {
202 115 : callback(pair.first, pair.second);
203 : }
204 : }
205 68 : }
206 :
207 : /**
208 : * @brief Safely converts the internal map content into a JSON object.
209 : *
210 : * Locks ALL shards (read, fixed ascending order) for the duration so the
211 : * serialized object is a consistent snapshot across the whole keyspace.
212 : * Administrative path (e.g. GET /admin/v1/vault), not the traffic hot path.
213 : *
214 : * @return nlohmann::json A new copy of the map's content as a JSON object.
215 : */
216 71 : nlohmann::json getJson() const {
217 71 : std::array<read_guard_t, Shards> guards = lockAllShared();
218 : if constexpr (Shards == 1) {
219 2 : return nlohmann::json(shards_[0].map_); // return copy
220 : } else {
221 70 : nlohmann::json j = nlohmann::json::object();
222 1182 : for (const auto& s : shards_) {
223 163658 : for (const auto& pair : s.map_) {
224 162546 : j[pair.first] = pair.second;
225 : }
226 : }
227 140 : return j;
228 70 : }
229 71 : }
230 :
231 : // setters
232 :
233 : /**
234 : * Adds a new value to the map (Lvalue variant). Locks only the key's shard.
235 : */
236 888 : void add(const Key& key, const Value &value) {
237 888 : Shard& s = shardFor(key);
238 888 : write_guard_t guard(s.mutex_);
239 888 : s.map_.insert_or_assign(key, value);
240 888 : }
241 :
242 : // Rvalue variant (std::move)
243 496 : void add(const Key& key, Value&& value) {
244 496 : Shard& s = shardFor(key);
245 496 : write_guard_t guard(s.mutex_);
246 496 : s.map_.insert_or_assign(key, std::move(value));
247 496 : }
248 :
249 : /**
250 : * Atomically reads, modifies and writes back a value under a single shard
251 : * write lock. If the key doesn't exist, a default-constructed Value is
252 : * passed to the modifier.
253 : *
254 : * @param key key to modify
255 : * @param modifier function that receives a reference to the value and modifies it in place
256 : */
257 : template<typename Modifier>
258 115975 : void modifyOrInsert(const Key& key, Modifier&& modifier) {
259 115975 : Shard& s = shardFor(key);
260 115861 : write_guard_t guard(s.mutex_);
261 117880 : modifier(s.map_[key]); // operator[] inserts default if missing
262 116740 : }
263 :
264 : /**
265 : * Adds another map of same kind to the map. Each entry is routed to its own
266 : * shard and locked individually.
267 : *
268 : * @param m map to add
269 : */
270 : void add(const map_t& m)
271 : {
272 : for (const auto& kv : m) {
273 : Shard& s = shardFor(kv.first);
274 : write_guard_t guard(s.mutex_);
275 : s.map_.insert_or_assign(kv.first, kv.second);
276 : }
277 : }
278 :
279 : /**
280 : * Removes key (locks only the key's shard)
281 : *
282 : * @param key key to remove
283 : */
284 11 : void remove(const Key& key, bool &exists)
285 : {
286 11 : Shard& s = shardFor(key);
287 11 : write_guard_t guard(s.mutex_);
288 11 : exists = (s.map_.erase(key) > 0);
289 11 : }
290 :
291 : /** Clear map (locks ALL shards for write, fixed ascending order).
292 : * @return true if something was deleted */
293 31 : bool clear()
294 : {
295 31 : std::array<write_guard_t, Shards> guards = lockAllExclusive();
296 31 : bool result = false;
297 136 : for (auto& s : shards_) {
298 105 : if (!s.map_.empty()) result = true;
299 105 : s.map_.clear();
300 : }
301 31 : return result;
302 31 : }
303 :
304 : private:
305 : // Acquire a read lock on every shard in fixed ascending order (deadlock-free).
306 139 : std::array<read_guard_t, Shards> lockAllShared() const {
307 139 : return lockAllSharedImpl(std::make_index_sequence<Shards>{});
308 : }
309 : template<std::size_t... I>
310 139 : std::array<read_guard_t, Shards> lockAllSharedImpl(std::index_sequence<I...>) const {
311 139 : return { read_guard_t(shards_[I].mutex_)... };
312 139 : }
313 :
314 : // Acquire a write lock on every shard in fixed ascending order (deadlock-free).
315 31 : std::array<write_guard_t, Shards> lockAllExclusive() {
316 31 : return lockAllExclusiveImpl(std::make_index_sequence<Shards>{});
317 : }
318 : template<std::size_t... I>
319 31 : std::array<write_guard_t, Shards> lockAllExclusiveImpl(std::index_sequence<I...>) {
320 31 : return { write_guard_t(shards_[I].mutex_)... };
321 31 : }
322 : };
323 :
324 : }
325 : }
326 :
|
