1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef ABSL_CONTAINER_INTERNAL_CONTAINER_MEMORY_H_
16 #define ABSL_CONTAINER_INTERNAL_CONTAINER_MEMORY_H_
17
18 #include <cassert>
19 #include <cstddef>
20 #include <memory>
21 #include <new>
22 #include <tuple>
23 #include <type_traits>
24 #include <utility>
25
26 #include "absl/base/config.h"
27 #include "absl/memory/memory.h"
28 #include "absl/meta/type_traits.h"
29 #include "absl/utility/utility.h"
30
31 #ifdef ABSL_HAVE_ADDRESS_SANITIZER
32 #include <sanitizer/asan_interface.h>
33 #endif
34
35 #ifdef ABSL_HAVE_MEMORY_SANITIZER
36 #include <sanitizer/msan_interface.h>
37 #endif
38
39 namespace absl {
40 ABSL_NAMESPACE_BEGIN
41 namespace container_internal {
42
43 template <size_t Alignment>
alignas(Alignment)44 struct alignas(Alignment) AlignedType {};
45
46 // Allocates at least n bytes aligned to the specified alignment.
47 // Alignment must be a power of 2. It must be positive.
48 //
49 // Note that many allocators don't honor alignment requirements above certain
50 // threshold (usually either alignof(std::max_align_t) or alignof(void*)).
51 // Allocate() doesn't apply alignment corrections. If the underlying allocator
52 // returns insufficiently alignment pointer, that's what you are going to get.
53 template <size_t Alignment, class Alloc>
Allocate(Alloc * alloc,size_t n)54 void* Allocate(Alloc* alloc, size_t n) {
55 static_assert(Alignment > 0, "");
56 assert(n && "n must be positive");
57 using M = AlignedType<Alignment>;
58 using A = typename absl::allocator_traits<Alloc>::template rebind_alloc<M>;
59 using AT = typename absl::allocator_traits<Alloc>::template rebind_traits<M>;
60 // On macOS, "mem_alloc" is a #define with one argument defined in
61 // rpc/types.h, so we can't name the variable "mem_alloc" and initialize it
62 // with the "foo(bar)" syntax.
63 A my_mem_alloc(*alloc);
64 void* p = AT::allocate(my_mem_alloc, (n + sizeof(M) - 1) / sizeof(M));
65 assert(reinterpret_cast<uintptr_t>(p) % Alignment == 0 &&
66 "allocator does not respect alignment");
67 return p;
68 }
69
70 // The pointer must have been previously obtained by calling
71 // Allocate<Alignment>(alloc, n).
72 template <size_t Alignment, class Alloc>
Deallocate(Alloc * alloc,void * p,size_t n)73 void Deallocate(Alloc* alloc, void* p, size_t n) {
74 static_assert(Alignment > 0, "");
75 assert(n && "n must be positive");
76 using M = AlignedType<Alignment>;
77 using A = typename absl::allocator_traits<Alloc>::template rebind_alloc<M>;
78 using AT = typename absl::allocator_traits<Alloc>::template rebind_traits<M>;
79 // On macOS, "mem_alloc" is a #define with one argument defined in
80 // rpc/types.h, so we can't name the variable "mem_alloc" and initialize it
81 // with the "foo(bar)" syntax.
82 A my_mem_alloc(*alloc);
83 AT::deallocate(my_mem_alloc, static_cast<M*>(p),
84 (n + sizeof(M) - 1) / sizeof(M));
85 }
86
87 namespace memory_internal {
88
89 // Constructs T into uninitialized storage pointed by `ptr` using the args
90 // specified in the tuple.
91 template <class Alloc, class T, class Tuple, size_t... I>
ConstructFromTupleImpl(Alloc * alloc,T * ptr,Tuple && t,absl::index_sequence<I...>)92 void ConstructFromTupleImpl(Alloc* alloc, T* ptr, Tuple&& t,
93 absl::index_sequence<I...>) {
94 absl::allocator_traits<Alloc>::construct(
95 *alloc, ptr, std::get<I>(std::forward<Tuple>(t))...);
96 }
97
98 template <class T, class F>
99 struct WithConstructedImplF {
100 template <class... Args>
decltypeWithConstructedImplF101 decltype(std::declval<F>()(std::declval<T>())) operator()(
102 Args&&... args) const {
103 return std::forward<F>(f)(T(std::forward<Args>(args)...));
104 }
105 F&& f;
106 };
107
108 template <class T, class Tuple, size_t... Is, class F>
decltype(std::declval<F> ()(std::declval<T> ()))109 decltype(std::declval<F>()(std::declval<T>())) WithConstructedImpl(
110 Tuple&& t, absl::index_sequence<Is...>, F&& f) {
111 return WithConstructedImplF<T, F>{std::forward<F>(f)}(
112 std::get<Is>(std::forward<Tuple>(t))...);
113 }
114
115 template <class T, size_t... Is>
116 auto TupleRefImpl(T&& t, absl::index_sequence<Is...>)
117 -> decltype(std::forward_as_tuple(std::get<Is>(std::forward<T>(t))...)) {
118 return std::forward_as_tuple(std::get<Is>(std::forward<T>(t))...);
119 }
120
121 // Returns a tuple of references to the elements of the input tuple. T must be a
122 // tuple.
123 template <class T>
124 auto TupleRef(T&& t) -> decltype(
125 TupleRefImpl(std::forward<T>(t),
126 absl::make_index_sequence<
127 std::tuple_size<typename std::decay<T>::type>::value>())) {
128 return TupleRefImpl(
129 std::forward<T>(t),
130 absl::make_index_sequence<
131 std::tuple_size<typename std::decay<T>::type>::value>());
132 }
133
134 template <class F, class K, class V>
decltype(std::declval<F> ()(std::declval<const K &> (),std::piecewise_construct,std::declval<std::tuple<K>> (),std::declval<V> ()))135 decltype(std::declval<F>()(std::declval<const K&>(), std::piecewise_construct,
136 std::declval<std::tuple<K>>(), std::declval<V>()))
137 DecomposePairImpl(F&& f, std::pair<std::tuple<K>, V> p) {
138 const auto& key = std::get<0>(p.first);
139 return std::forward<F>(f)(key, std::piecewise_construct, std::move(p.first),
140 std::move(p.second));
141 }
142
143 } // namespace memory_internal
144
145 // Constructs T into uninitialized storage pointed by `ptr` using the args
146 // specified in the tuple.
147 template <class Alloc, class T, class Tuple>
ConstructFromTuple(Alloc * alloc,T * ptr,Tuple && t)148 void ConstructFromTuple(Alloc* alloc, T* ptr, Tuple&& t) {
149 memory_internal::ConstructFromTupleImpl(
150 alloc, ptr, std::forward<Tuple>(t),
151 absl::make_index_sequence<
152 std::tuple_size<typename std::decay<Tuple>::type>::value>());
153 }
154
155 // Constructs T using the args specified in the tuple and calls F with the
156 // constructed value.
157 template <class T, class Tuple, class F>
decltype(std::declval<F> ()(std::declval<T> ()))158 decltype(std::declval<F>()(std::declval<T>())) WithConstructed(
159 Tuple&& t, F&& f) {
160 return memory_internal::WithConstructedImpl<T>(
161 std::forward<Tuple>(t),
162 absl::make_index_sequence<
163 std::tuple_size<typename std::decay<Tuple>::type>::value>(),
164 std::forward<F>(f));
165 }
166
167 // Given arguments of an std::pair's consructor, PairArgs() returns a pair of
168 // tuples with references to the passed arguments. The tuples contain
169 // constructor arguments for the first and the second elements of the pair.
170 //
171 // The following two snippets are equivalent.
172 //
173 // 1. std::pair<F, S> p(args...);
174 //
175 // 2. auto a = PairArgs(args...);
176 // std::pair<F, S> p(std::piecewise_construct,
177 // std::move(p.first), std::move(p.second));
PairArgs()178 inline std::pair<std::tuple<>, std::tuple<>> PairArgs() { return {}; }
179 template <class F, class S>
PairArgs(F && f,S && s)180 std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(F&& f, S&& s) {
181 return {std::piecewise_construct, std::forward_as_tuple(std::forward<F>(f)),
182 std::forward_as_tuple(std::forward<S>(s))};
183 }
184 template <class F, class S>
PairArgs(const std::pair<F,S> & p)185 std::pair<std::tuple<const F&>, std::tuple<const S&>> PairArgs(
186 const std::pair<F, S>& p) {
187 return PairArgs(p.first, p.second);
188 }
189 template <class F, class S>
PairArgs(std::pair<F,S> && p)190 std::pair<std::tuple<F&&>, std::tuple<S&&>> PairArgs(std::pair<F, S>&& p) {
191 return PairArgs(std::forward<F>(p.first), std::forward<S>(p.second));
192 }
193 template <class F, class S>
194 auto PairArgs(std::piecewise_construct_t, F&& f, S&& s)
195 -> decltype(std::make_pair(memory_internal::TupleRef(std::forward<F>(f)),
196 memory_internal::TupleRef(std::forward<S>(s)))) {
197 return std::make_pair(memory_internal::TupleRef(std::forward<F>(f)),
198 memory_internal::TupleRef(std::forward<S>(s)));
199 }
200
201 // A helper function for implementing apply() in map policies.
202 template <class F, class... Args>
203 auto DecomposePair(F&& f, Args&&... args)
204 -> decltype(memory_internal::DecomposePairImpl(
205 std::forward<F>(f), PairArgs(std::forward<Args>(args)...))) {
206 return memory_internal::DecomposePairImpl(
207 std::forward<F>(f), PairArgs(std::forward<Args>(args)...));
208 }
209
210 // A helper function for implementing apply() in set policies.
211 template <class F, class Arg>
decltype(std::declval<F> ()(std::declval<const Arg &> (),std::declval<Arg> ()))212 decltype(std::declval<F>()(std::declval<const Arg&>(), std::declval<Arg>()))
213 DecomposeValue(F&& f, Arg&& arg) {
214 const auto& key = arg;
215 return std::forward<F>(f)(key, std::forward<Arg>(arg));
216 }
217
218 // Helper functions for asan and msan.
SanitizerPoisonMemoryRegion(const void * m,size_t s)219 inline void SanitizerPoisonMemoryRegion(const void* m, size_t s) {
220 #ifdef ABSL_HAVE_ADDRESS_SANITIZER
221 ASAN_POISON_MEMORY_REGION(m, s);
222 #endif
223 #ifdef ABSL_HAVE_MEMORY_SANITIZER
224 __msan_poison(m, s);
225 #endif
226 (void)m;
227 (void)s;
228 }
229
SanitizerUnpoisonMemoryRegion(const void * m,size_t s)230 inline void SanitizerUnpoisonMemoryRegion(const void* m, size_t s) {
231 #ifdef ABSL_HAVE_ADDRESS_SANITIZER
232 ASAN_UNPOISON_MEMORY_REGION(m, s);
233 #endif
234 #ifdef ABSL_HAVE_MEMORY_SANITIZER
235 __msan_unpoison(m, s);
236 #endif
237 (void)m;
238 (void)s;
239 }
240
241 template <typename T>
SanitizerPoisonObject(const T * object)242 inline void SanitizerPoisonObject(const T* object) {
243 SanitizerPoisonMemoryRegion(object, sizeof(T));
244 }
245
246 template <typename T>
SanitizerUnpoisonObject(const T * object)247 inline void SanitizerUnpoisonObject(const T* object) {
248 SanitizerUnpoisonMemoryRegion(object, sizeof(T));
249 }
250
251 namespace memory_internal {
252
253 // If Pair is a standard-layout type, OffsetOf<Pair>::kFirst and
254 // OffsetOf<Pair>::kSecond are equivalent to offsetof(Pair, first) and
255 // offsetof(Pair, second) respectively. Otherwise they are -1.
256 //
257 // The purpose of OffsetOf is to avoid calling offsetof() on non-standard-layout
258 // type, which is non-portable.
259 template <class Pair, class = std::true_type>
260 struct OffsetOf {
261 static constexpr size_t kFirst = static_cast<size_t>(-1);
262 static constexpr size_t kSecond = static_cast<size_t>(-1);
263 };
264
265 template <class Pair>
266 struct OffsetOf<Pair, typename std::is_standard_layout<Pair>::type> {
267 static constexpr size_t kFirst = offsetof(Pair, first);
268 static constexpr size_t kSecond = offsetof(Pair, second);
269 };
270
271 template <class K, class V>
272 struct IsLayoutCompatible {
273 private:
274 struct Pair {
275 K first;
276 V second;
277 };
278
279 // Is P layout-compatible with Pair?
280 template <class P>
281 static constexpr bool LayoutCompatible() {
282 return std::is_standard_layout<P>() && sizeof(P) == sizeof(Pair) &&
283 alignof(P) == alignof(Pair) &&
284 memory_internal::OffsetOf<P>::kFirst ==
285 memory_internal::OffsetOf<Pair>::kFirst &&
286 memory_internal::OffsetOf<P>::kSecond ==
287 memory_internal::OffsetOf<Pair>::kSecond;
288 }
289
290 public:
291 // Whether pair<const K, V> and pair<K, V> are layout-compatible. If they are,
292 // then it is safe to store them in a union and read from either.
293 static constexpr bool value = std::is_standard_layout<K>() &&
294 std::is_standard_layout<Pair>() &&
295 memory_internal::OffsetOf<Pair>::kFirst == 0 &&
296 LayoutCompatible<std::pair<K, V>>() &&
297 LayoutCompatible<std::pair<const K, V>>();
298 };
299
300 } // namespace memory_internal
301
302 // The internal storage type for key-value containers like flat_hash_map.
303 //
304 // It is convenient for the value_type of a flat_hash_map<K, V> to be
305 // pair<const K, V>; the "const K" prevents accidental modification of the key
306 // when dealing with the reference returned from find() and similar methods.
307 // However, this creates other problems; we want to be able to emplace(K, V)
308 // efficiently with move operations, and similarly be able to move a
309 // pair<K, V> in insert().
310 //
311 // The solution is this union, which aliases the const and non-const versions
312 // of the pair. This also allows flat_hash_map<const K, V> to work, even though
313 // that has the same efficiency issues with move in emplace() and insert() -
314 // but people do it anyway.
315 //
316 // If kMutableKeys is false, only the value member can be accessed.
317 //
318 // If kMutableKeys is true, key can be accessed through all slots while value
319 // and mutable_value must be accessed only via INITIALIZED slots. Slots are
320 // created and destroyed via mutable_value so that the key can be moved later.
321 //
322 // Accessing one of the union fields while the other is active is safe as
323 // long as they are layout-compatible, which is guaranteed by the definition of
324 // kMutableKeys. For C++11, the relevant section of the standard is
325 // https://timsong-cpp.github.io/cppwp/n3337/class.mem#19 (9.2.19)
326 template <class K, class V>
327 union map_slot_type {
328 map_slot_type() {}
329 ~map_slot_type() = delete;
330 using value_type = std::pair<const K, V>;
331 using mutable_value_type =
332 std::pair<absl::remove_const_t<K>, absl::remove_const_t<V>>;
333
334 value_type value;
335 mutable_value_type mutable_value;
336 absl::remove_const_t<K> key;
337 };
338
339 template <class K, class V>
340 struct map_slot_policy {
341 using slot_type = map_slot_type<K, V>;
342 using value_type = std::pair<const K, V>;
343 using mutable_value_type = std::pair<K, V>;
344
345 private:
346 static void emplace(slot_type* slot) {
347 // The construction of union doesn't do anything at runtime but it allows us
348 // to access its members without violating aliasing rules.
349 new (slot) slot_type;
350 }
351 // If pair<const K, V> and pair<K, V> are layout-compatible, we can accept one
352 // or the other via slot_type. We are also free to access the key via
353 // slot_type::key in this case.
354 using kMutableKeys = memory_internal::IsLayoutCompatible<K, V>;
355
356 public:
357 static value_type& element(slot_type* slot) { return slot->value; }
358 static const value_type& element(const slot_type* slot) {
359 return slot->value;
360 }
361
362 // When C++17 is available, we can use std::launder to provide mutable
363 // access to the key for use in node handle.
364 #if defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606
365 static K& mutable_key(slot_type* slot) {
366 // Still check for kMutableKeys so that we can avoid calling std::launder
367 // unless necessary because it can interfere with optimizations.
368 return kMutableKeys::value ? slot->key
369 : *std::launder(const_cast<K*>(
370 std::addressof(slot->value.first)));
371 }
372 #else // !(defined(__cpp_lib_launder) && __cpp_lib_launder >= 201606)
373 static const K& mutable_key(slot_type* slot) { return key(slot); }
374 #endif
375
376 static const K& key(const slot_type* slot) {
377 return kMutableKeys::value ? slot->key : slot->value.first;
378 }
379
380 template <class Allocator, class... Args>
381 static void construct(Allocator* alloc, slot_type* slot, Args&&... args) {
382 emplace(slot);
383 if (kMutableKeys::value) {
384 absl::allocator_traits<Allocator>::construct(*alloc, &slot->mutable_value,
385 std::forward<Args>(args)...);
386 } else {
387 absl::allocator_traits<Allocator>::construct(*alloc, &slot->value,
388 std::forward<Args>(args)...);
389 }
390 }
391
392 // Construct this slot by moving from another slot.
393 template <class Allocator>
394 static void construct(Allocator* alloc, slot_type* slot, slot_type* other) {
395 emplace(slot);
396 if (kMutableKeys::value) {
397 absl::allocator_traits<Allocator>::construct(
398 *alloc, &slot->mutable_value, std::move(other->mutable_value));
399 } else {
400 absl::allocator_traits<Allocator>::construct(*alloc, &slot->value,
401 std::move(other->value));
402 }
403 }
404
405 template <class Allocator>
406 static void destroy(Allocator* alloc, slot_type* slot) {
407 if (kMutableKeys::value) {
408 absl::allocator_traits<Allocator>::destroy(*alloc, &slot->mutable_value);
409 } else {
410 absl::allocator_traits<Allocator>::destroy(*alloc, &slot->value);
411 }
412 }
413
414 template <class Allocator>
415 static void transfer(Allocator* alloc, slot_type* new_slot,
416 slot_type* old_slot) {
417 emplace(new_slot);
418 if (kMutableKeys::value) {
419 absl::allocator_traits<Allocator>::construct(
420 *alloc, &new_slot->mutable_value, std::move(old_slot->mutable_value));
421 } else {
422 absl::allocator_traits<Allocator>::construct(*alloc, &new_slot->value,
423 std::move(old_slot->value));
424 }
425 destroy(alloc, old_slot);
426 }
427
428 template <class Allocator>
429 static void swap(Allocator* alloc, slot_type* a, slot_type* b) {
430 if (kMutableKeys::value) {
431 using std::swap;
432 swap(a->mutable_value, b->mutable_value);
433 } else {
434 value_type tmp = std::move(a->value);
435 absl::allocator_traits<Allocator>::destroy(*alloc, &a->value);
436 absl::allocator_traits<Allocator>::construct(*alloc, &a->value,
437 std::move(b->value));
438 absl::allocator_traits<Allocator>::destroy(*alloc, &b->value);
439 absl::allocator_traits<Allocator>::construct(*alloc, &b->value,
440 std::move(tmp));
441 }
442 }
443
444 template <class Allocator>
445 static void move(Allocator* alloc, slot_type* src, slot_type* dest) {
446 if (kMutableKeys::value) {
447 dest->mutable_value = std::move(src->mutable_value);
448 } else {
449 absl::allocator_traits<Allocator>::destroy(*alloc, &dest->value);
450 absl::allocator_traits<Allocator>::construct(*alloc, &dest->value,
451 std::move(src->value));
452 }
453 }
454 };
455
456 } // namespace container_internal
457 ABSL_NAMESPACE_END
458 } // namespace absl
459
460 #endif // ABSL_CONTAINER_INTERNAL_CONTAINER_MEMORY_H_
461