1 /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3  *     Copyright 2016 Couchbase, 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 
18 /**
19  * AtomicUnorderedMap - A thread-safe map class.
20  *
21  * AtomicUnorderedMap is a thread-safe unordered map (associative array).
22  * Elements can be added, removed and found concurrently from different
23  * threads safely.
24  *
25  *
26  * THREAD SAFETY
27  * Items are returned by value (instead of via an iterator) - this ensures that
28  * once an item is passed back to the caller, it can safely be accessed even if
29  * another thread has concurrently deleted it from the map.
30  *
31  * While this may seen limiting, the value type can be a (smart) pointer if
32  * desired, removing the need to copy the actual underlying object. However,
33  * if a pointer type is used then operations on the pointed-to objects are
34  * *not* automatically thread-safe. In other words, while you can safely call
35  * insert(<ptr>) from multiple threads, you *cannot* safely mutate the object
36  * pointed to (by the pointer which insert() returns) from multiple threads
37  * without additional synchronization. For example, having an per-object
38  * mutex, or making the object atomic.
39  *
40  *
41  * FUNCTIONALITY
42  * Implements a relatively simple set of operations modeled on
43  * std::unordered_map:
44  *
45  *   - empty() returns true if the map is empty.
46  *   - size() to return the number of elements in the map.
47  *   - insert() to add an element
48  *   - find() to search for an element
49  *   - erase() to delete an element
50  *   - clear() to delete all elements
51  *
52  * Iteration, a la `auto it = begin(); it++; ...` isn't directly supported;
53  * the main reason is that another thread may have removed an item between
54  * calling begin() and moving to the next item, so it's not possible to ensure
55  * all elements are acted on. Instead, a number of functions similar to
56  * std::algorithm are provided:
57  *
58  *   - find_if() to search for the first element matching a given predicate.
59  *   - for_each() to apply a function to every element in the map.
60  *
61  *
62  * LOCKING STRATEGIES
63  * There are two locking strategies available:
64  * - Internal locking, where the methods themselves lock on entry (and unlock
65  *   on exit).
66  * - External locking, where a lock is acquired before calling the methods.
67  *
68  * For simple use-cases internal locking is sufficient (and safer) - the caller
69  * doesn't have to concern themselves with locking, and can rely on the object
70  * doing the right thing.
71  * However if the caller needs to ensure that multiple operations on the map
72  * are atomic (e.g. find()ing an item and then conditionally erase()ing it) then
73  * external locking can be used.
74  *
75  * For example, to atomically remove an key only if it's value is false:
76  *
77  *     typedef AtomicUnorderedMap<int, bool> M; // Key:int, Value:bool
78  *     M map;
79  *     ...
80  *     { // Create new scope for external lock guard.
81  *         std::lock_guard<M> guard(map);
82  *         bool it = map.find(key_of_interest, guard);
83  *         if (it && *it == false) {
84  *             map.erase(it, guard);
85  *         }
86  *     } // end of scope, map unlocked.
87  *
88  * Note that the guard is passed into the find() and erase() functions to
89  * indicate that an external lock is already acquired (and hence an internal
90  * lock should not be acquired).
91  *
92  * See Boost Synchronization
93  * (http://www.boost.org/doc/libs/1_60_0/doc/html/thread/synchronization.html)
94  * for more details & background on the internal / external locking strategies
95  * used here.
96  */
97 
98 #pragma once
99 
100 #include "atomic.h"
101 
102 #include <folly/CachelinePadded.h>
103 #include <platform/rwlock.h>
104 
105 #include <algorithm>
106 #include <shared_mutex>
107 #include <unordered_map>
108 
109 template <class Key,
110           class T,
111           class Hash = std::hash<Key>,
112           class KeyEqual = std::equal_to<Key>,
113           class Allocator = std::allocator<std::pair<const Key, T> > >
114 class AtomicUnorderedMap;
115 
116 template <class Key, class T, class Hash, class KeyEqual, class Allocator>
117 class AtomicUnorderedMap {
118 public:
119     using map_type = AtomicUnorderedMap<Key, T, Hash, KeyEqual, Allocator>;
120 
121     // Alias to simplify all the other defs
122     using base_map_type =
123             typename std::unordered_map<Key, T, Hash, KeyEqual, Allocator>;
124 
125     // Map to the type aliases in the underlying map.
126     using key_type = typename base_map_type::key_type;
127     using mapped_type = typename base_map_type::mapped_type;
128     using value_type = typename base_map_type::value_type;
129     using size_type = typename base_map_type::size_type;
130 
empty() const131     bool empty() const {
132         std::shared_lock<cb::RWLock> guard(*this->rwlock); // internally locked
133         return map.empty();
134     }
135 
size() const136     size_type size() const {
137         std::shared_lock<cb::RWLock> guard(*this->rwlock); // internally locked
138         return map.size();
139     }
140 
141     /* Lookup */
142 
143     /**
144      * Searches for the given key in the map using external shared locking
145      * @param key Reference to the key to find
146      * @param shared_lock reference to the shared_lock
147      * @returns a pair consisting of:
148      *  - the found element (or a default-constructed element if not found)
149      *  - and bool denoting if the given key was found.
150      */
find(const Key& key, std::shared_lock<map_type>&)151     std::pair<T, bool> find(const Key& key, std::shared_lock<map_type>&) {
152         return find_UNLOCKED(key);
153     }
154 
155     /**
156      * Searches for the given key in the map using external exclusive locking
157      * @param key Reference to the key to find
158      * @param lock_guard reference to the lock_guard
159      * @returns a pair consisting of:
160      *  - the found element (or a default-constructed element if not found)
161      *  - and bool denoting if the given key was found.
162      */
find(const Key& key, std::lock_guard<map_type>&)163     std::pair<T, bool> find(const Key& key, std::lock_guard<map_type>&) {
164         return find_UNLOCKED(key);
165     }
166 
167     /**
168      * Searches for the given key in the map, internally locked
169      * @param key Reference to the key to find
170      * @returns a pair consisting of:
171      *  - the found element (or a default-constructed element if not found)
172      *  - and bool denoting if the given key was found.
173      */
find(const Key& key)174     std::pair<T, bool> find(const Key& key) {
175         std::shared_lock<map_type> guard(*this); // internally locked
176         return find(key, guard);
177     }
178 
179     /** Searches for first element which matches the given predicate.
180      *  Returns a pair consisting of:
181      *  - the first found element (or a default-constructed element if not
182      * found)
183      *  - and bool denoting if a matching element was found.
184      */
185     template <class UnaryPredicate>
find_if(UnaryPredicate p)186     std::pair<T, bool> find_if(UnaryPredicate p) {
187         std::shared_lock<map_type> guard(*this); // internally locked
188         auto iter = std::find_if(map.begin(), map.end(), p);
189         if (iter != map.end()) {
190             return {iter->second, true};
191         } else {
192             return std::make_pair(T(), false);
193         }
194     }
195 
196     /**
197      * Applies the given function object to every mapped value and returns from
198      * f some other value only if f returns a value that evaluates to true
199      * (bool operator)
200      *
201      * The function should take a value_type reference as a parameter and return
202      * some-type by value. some-type must be a type which supports operator bool
203      * e.g. std::shared_ptr. As each map element is evaluated, the iteration
204      * will stop when f returns a value which 'if (value)' evaluates to true,
205      * the value is then returned.
206      * If every element is visited and nothing evaluated to true, then a default
207      * initialised some-type is returned.
208      *
209      * @param key Key value to lookup
210      * @param f Function object to be applied
211      * @returns The value found by f or a default initialised value
212      */
213     template <class UnaryFunction>
find_if2(UnaryFunction f)214     auto find_if2(UnaryFunction f) {
215         std::shared_lock<map_type> guard(*this);
216         return find_if2_UNLOCKED(f);
217     }
218 
219     /* Modifiers */
220 
clear(std::lock_guard<map_type>&)221     void clear(std::lock_guard<map_type>&) {
222         // Externally locked
223         map.clear();
224     }
clear()225     void clear() {
226         std::lock_guard<map_type> guard(*this); // internally locked
227         clear(guard);
228     }
229 
230     /**
231      * Applies the given function object to every element in the map using
232      * exclusive locking
233      *
234      * @param f Function object to be applied to every element in the map
235      * @param lock_guard externally held lock
236      */
237     template <class UnaryFunction>
for_each(UnaryFunction f, std::lock_guard<map_type>&)238     void for_each(UnaryFunction f, std::lock_guard<map_type>&) {
239         std::for_each(map.begin(), map.end(), f);
240     }
241 
242     /**
243      * Applies the given function object to every element in the map
244      *
245      * @param f Function object to be applied to every element in the map
246      */
247     template <class UnaryFunction>
for_each(UnaryFunction f)248     void for_each(UnaryFunction f) {
249         std::shared_lock<map_type> guard(*this); // internally locked
250         for_each(f, guard);
251     }
252 
253     /**
254      * Applies the given function object to the key (if mapped)
255      *
256      * The function should take a value_type reference as a parameter
257      *
258      * @param key Key value to lookup
259      * @param f Function object to be applied
260      * @returns true if the key was found and f applied
261      */
262     template <class UnaryFunction>
apply(const key_type& key, UnaryFunction f)263     bool apply(const key_type& key, UnaryFunction f) {
264         std::shared_lock<map_type> guard(*this);
265         auto iter = map.find(key);
266         if (iter != map.end()) {
267             f(*iter);
268         }
269         return iter != map.end();
270     }
271 
272     /**
273      * Applies the given function object to every element in the map using
274      * shared_lock locking
275      *
276      * @param f Function object to be applied to every element in the map
277      * @param lock_guard externally held lock
278      */
279     template <class UnaryFunction>
for_each(UnaryFunction f, std::shared_lock<map_type>&)280     void for_each(UnaryFunction f, std::shared_lock<map_type>&) {
281         std::for_each(map.begin(), map.end(), f);
282     }
283 
284     /**
285      * Attempts to erase the given key from the map.
286      *  Returns a pair consisting of:
287      *  - the erased element (or a default-constructed element if not found)
288      *  - and bool denoting if the given key was erased.
289      */
erase(const key_type& key, std::lock_guard<map_type>&)290     std::pair<T, bool> erase(const key_type& key, std::lock_guard<map_type>&) {
291         // Externally locked
292         auto iter = map.find(key);
293         if (iter != map.end()) {
294             T result = iter->second;
295             map.erase(iter);
296             return {result, true};
297         } else {
298             return std::make_pair(T(), false);
299         }
300     }
erase(const key_type& key)301     std::pair<T, bool> erase(const key_type& key) {
302         std::lock_guard<map_type> guard(*this); // internally locked
303         return erase(key, guard);
304     }
305 
306     /**
307      * Attempts to insert the given key into the map, if it does not already
308      * exist.
309      *  Returns true if the element was inserted, or false if an element
310      *  with the given key already exists.
311      */
insert(const value_type& value)312     bool insert(const value_type& value) {
313         std::lock_guard<map_type> guard(*this); // internally locked
314         auto result = map.insert(value);
315         return result.second;
316     }
317 
318     /**
319      * Attempts to insert the given key into the map, if it does not already
320      * exist.
321      *  Returns true if the element was inserted, or false if an element
322      *  with the given key already exists.
323      */
insert(const value_type& value, std::lock_guard<map_type>&)324     bool insert(const value_type& value, std::lock_guard<map_type>&) {
325         auto result = map.insert(value);
326         return result.second;
327     }
328 
329     /*
330      * Locking
331      *
332      * Note: Prefer to use RAII-style lock holders (e.g. std::lock_guard<>())
333      *       instead of the raw methods here.
334      */
335 
336     /* Explicitly locks the container. */
lock()337     void lock() {
338         rwlock->lock();
339     }
340 
unlock()341     void unlock() {
342         rwlock->unlock();
343     }
344 
lock_shared()345     void lock_shared() {
346         rwlock->lock_shared();
347     }
348 
unlock_shared()349     void unlock_shared() {
350         rwlock->unlock_shared();
351     }
352 
353 private:
find_UNLOCKED(const Key& key)354     std::pair<T, bool> find_UNLOCKED(const Key& key) {
355         auto iter = map.find(key);
356         if (iter != map.end()) {
357             return {iter->second, true};
358         } else {
359             return std::make_pair(T(), false);
360         }
361     }
362 
363     template <class UnaryFunction>
find_if2_UNLOCKED(UnaryFunction f)364     auto find_if2_UNLOCKED(UnaryFunction f) {
365         using UnaryFunctionRval = decltype(f(*map.find({})));
366         for (auto& kv : map) {
367             auto rv = f(kv);
368             if (rv) {
369                 return rv;
370             }
371         }
372         return UnaryFunctionRval{};
373     }
374 
375     std::unordered_map<Key, T, Hash, KeyEqual, Allocator> map;
376 
377     // MB-32107
378     // Cacheline padded as it was identified that this lock shared with the
379     // preceeding map and in the case of the DcpProducer some following atomic
380     // variables. As this mutex occupies 56 bytes on Linux (almost an entire
381     // cache line) we should pad it to prevent the shuffling of members in the
382     // DcpProducer class moving this mutex and causing false sharing that
383     // affects performance.
384     mutable folly::CachelinePadded<cb::RWLock> rwlock;
385 };
386