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