MySQL 9.0.0
Source Code Documentation
atomics_array.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2024, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is designed to work with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have either included with
13 the program or referenced in the documentation.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24#ifndef CONTAINER_ATOMIC_INTEGRALS_ARRAY
25#define CONTAINER_ATOMIC_INTEGRALS_ARRAY
26
27#include <algorithm>
28#include <atomic>
29#include <cmath>
30#include <map>
31#include <memory>
32#include <sstream>
33#include <thread>
34#include <tuple>
35
36#include "sql/containers/atomics_array_index_padding.h" // container::Padded_Indexing
37#include "sql/memory/unique_ptr.h" // memory::Unique_ptr
38
39namespace container {
40/**
41 Array of `std::atomic` elements of type `T`.
42
43 An array of `std::atomic` elements implies, almost for sure, a
44 multi-threaded environment and concurrent access to the array may lead to
45 false sharing when consecutive elements are pulled into the same CPU
46 cache line. This class accepts, as a template parameter, a helper class
47 that is both an element storage index translator and element storage size
48 provider. Different strategies to prevent false sharing and the
49 subsequent cache invalidation and misses, may be applied. Amongst others,
50 padding each element of the array to the size of the cache line or use
51 index translation to interleave sequential indexes to leave enough space
52 for them not to be pulled into the same cache line. The two described
53 strategies are provided already with the `container::Padded_indexing` and
54 `container::Interleaved_indexing` classes.
55
56 Template parameters are as follows:
57 - `T`: the integral type for the array elements.
58 - `I`: type of indexing to be used by this array in the form of a
59 class. Available classes are `container::Padded_indexing` and
60 `container::Interleaved_indexing`. The parameter defaults to
61 `container::Padded_indexing`.
62 - `A`: type of memory allocator to be used, in the form of a class
63 (defaults to no allocator).
64
65 When and if deciding between interleaved or padded indexing, one could
66 take into consideration, amongst possibly others, the following
67 arguments:
68
69 - For arrays with random concurrent access patterns, interleaved indexing
70 doesn't ensure false-sharing prevention.
71 - For arrays with sequential concurrent access patterns, if it's needed
72 that interleaved indexing prevents false-sharing, consecutive array
73 indexes will need to be apart, physically, the size of a
74 cache-line. So, in a system with expectation of T threads accessing
75 concurrently an array of elements of size `E` and with a cache-line of
76 size `CL`, the array capacity should be at least `T * (CL / E)` for
77 interleaved indexing to prevent false-sharing.
78 - Padded indexing will always prevent false-sharing but it will consume
79 more memory in order to have the same array capacity as the interleaved
80 indexing.
81 */
82template <typename T, typename I = container::Padded_indexing<T>,
83 typename A = std::nullptr_t>
85 public:
86 using pointer_type = T *;
87 using const_pointer_type = T const *;
88 using reference_type = T &;
89 using const_reference_type = T const &;
90 using value_type = T;
91 using const_value_type = T const;
92 using element_type = std::atomic<T>;
93
94 /**
95 Iterator helper class to iterate over the array, from 0 to the array
96 size.
97
98 Check C++ documentation on `Iterator named requirements` for more
99 information on the implementation.
100 */
101 class Iterator {
102 public:
103 using difference_type = std::ptrdiff_t;
104 using value_type = T;
105 using pointer = T *;
106 using reference = T;
107 using iterator_category = std::forward_iterator_tag;
108
109 /**
110 */
111 explicit Iterator(Atomics_array<T, I, A> const &parent, size_t position);
112 Iterator(const Iterator &rhs);
114 virtual ~Iterator() = default;
115
116 // BASIC ITERATOR METHODS //
121 // END / BASIC ITERATOR METHODS //
122
123 // INPUT ITERATOR METHODS //
126 bool operator==(Iterator const &rhs) const;
127 bool operator!=(Iterator const &rhs) const;
128 // END / INPUT ITERATOR METHODS //
129
130 // OUTPUT ITERATOR METHODS //
131 // reference operator*(); <- already defined
132 // iterator operator++(int); <- already defined
133 // END / OUTPUT ITERATOR METHODS //
134
135 // FORWARD ITERATOR METHODS //
136 // Enable support for both input and output iterator <- already enabled
137 // END / FORWARD ITERATOR METHODS //
138
139 private:
140 /** The position of the element this iterator is pointing to. */
141 size_t m_current{0};
142 /** The reference to the queue holding the elements. */
144 };
145
146 /**
147 Constructor allowing a specific memory allocator, a specific queue size
148 and the instance of `T` to initialize the array with.
149
150 @param alloc The memory allocator instance
151 @param size The desired size for the queue
152 @param init_value The instance of `T` to initialize the array with
153 */
154 template <
155 typename D = T, typename J = I, typename B = A,
156 std::enable_if_t<!std::is_same<B, std::nullptr_t>::value> * = nullptr>
157 Atomics_array(A &alloc, size_t size, T init_value);
158 /**
159 Constructor allowing a specific queue size and the instance of `T` to
160 initialize the array with.
161
162 @param size The desired size for the queue
163 @param init_value The instance of `T` to initialize the array with
164 */
165 template <
166 typename D = T, typename J = I, typename B = A,
167 std::enable_if_t<std::is_same<B, std::nullptr_t>::value> * = nullptr>
168 Atomics_array(size_t size, T init_value);
169 // Deleted copy and move constructors.
172 //
173 /**
174 Destructor for the class.
175 */
176 virtual ~Atomics_array() = default;
177 // Deleted copy and move operators.
180 //
181 /**
182 Retrieves the value stored in a specific index of the array.
183
184 @param index The index of the element to retrieve the value for
185
186 @return the value of the element at index `index`
187 */
188 element_type &operator[](size_t index) const;
189 /**
190 Retrieves an iterator instance that points to the beginning of the
191 array.
192
193 @return An instance of an iterator pointing to the beginning of the
194 array.
195 */
196 Iterator begin() const;
197 /**
198 Retrieves an iterator instance that points to the end of the underlying
199 array.
200
201 @return An instance of an iterator pointing to the end of the underlying
202 array.
203 */
204 Iterator end() const;
205 /**
206 Finds a value in the queue according to the evaluation of `predicate`
207 by traversing the array from `start_from` to the array size.
208
209 The find condition is given according to the predicate `predicate` which
210 should be any predicate which translatable to `[](value_type value,
211 size_t index) -> bool`. If the predicate evaluates to `true`, the value
212 and respective index are returned as an `std::tuple`.
213
214 Check C++ documentation for the definition of `Predicate` named requirement
215 for more information.
216
217 @param predicate The predicate to be evaluated
218 @param start_from The index to start the search at
219
220 @return A tuple holding the value and the index of the first element
221 for which the predicate evaluated to true. If the predicate
222 doesn't evaluate to true for any of the elements, it returns a
223 pair holding the default value for `T` and the size of the
224 array.
225
226 */
227 template <typename Pred>
228 std::tuple<T, size_t> find_if(Pred predicate, size_t start_from = 0) const;
229 /**
230 First the first occurrence of `to_find`, starting at `start_from` index.
231
232 @param to_find the value to find
233 @param start_from the index to start the search from
234
235 @return the index of the the first element that matches the `to_find`
236 value or the array size if no element matches.
237 */
238 size_t find(T to_find, size_t start_from = 0) const;
239 /**
240 Returns the size of the array.
241
242 @return The size of the array
243 */
244 size_t size() const;
245 /**
246 Returns the number of bytes used to allocate the array.
247
248 @return The number of bytes used to allocate the array
249 */
250 size_t allocated_size() const;
251 /**
252 Return `this` queue textual representation.
253
254 @return The textual representation for `this` queue.
255 */
256 std::string to_string() const;
257
258 friend std::ostream &operator<<(std::ostream &out,
260 out << in.to_string(true) << std::flush;
261 return out;
262 }
263
264 private:
265 /** The index translation object to be used */
267 /** The byte array in which the elements will be stored */
269
270 /**
271 Initializes the array.
272
273 @return The reference to `this` object, for chaining purposes.
274 */
276};
277} // namespace container
278
279template <typename T, typename I, typename A>
281 Atomics_array<T, I, A> const &parent, size_t position)
282 : m_current{position}, m_parent{&parent} {}
283
284template <typename T, typename I, typename A>
286 : m_current{rhs.m_current}, m_parent{rhs.m_parent} {}
287
288template <typename T, typename I, typename A>
290 : m_current{rhs.m_current}, m_parent{rhs.m_parent} {
291 rhs.m_current = 0;
292 rhs.m_parent = nullptr;
293}
294
295template <typename T, typename I, typename A>
298 this->m_current = rhs.m_current;
299 this->m_parent = rhs.m_parent;
300 return (*this);
301}
302
303template <typename T, typename I, typename A>
306 this->m_current = rhs.m_current;
307 this->m_parent = rhs.m_parent;
308 rhs.m_current = 0;
309 rhs.m_parent = nullptr;
310 return (*this);
311}
312
313template <typename T, typename I, typename A>
316 if (this->m_current < this->m_parent->m_index.size()) {
317 ++this->m_current;
318 }
319 return (*this);
320}
321
322template <typename T, typename I, typename A>
325 return (*this->m_parent)[this->m_current];
326}
327
328template <typename T, typename I, typename A>
331 auto to_return = (*this);
332 ++(*this);
333 return to_return;
334}
335
336template <typename T, typename I, typename A>
339 return &((*this->m_parent)[this->m_current]);
340}
341
342template <typename T, typename I, typename A>
344 Iterator const &rhs) const {
345 return this->m_current == rhs.m_current && this->m_parent == rhs.m_parent;
346}
347
348template <typename T, typename I, typename A>
350 Iterator const &rhs) const {
351 return !((*this) == rhs);
352}
353
354template <typename T, typename I, typename A>
355template <typename D, typename J, typename B,
356 std::enable_if_t<!std::is_same<B, std::nullptr_t>::value> *>
358 T init_value)
359 : m_index{size},
360 m_array{alloc, static_cast<size_t>(m_index.size()) * I::element_size()} {
361 this->init(init_value);
362}
363
364template <typename T, typename I, typename A>
365template <typename D, typename J, typename B,
366 std::enable_if_t<std::is_same<B, std::nullptr_t>::value> *>
368 : m_index{size},
369 m_array{memory::make_unique<unsigned char[]>(
370 static_cast<size_t>(m_index.size()) * I::element_size())} {
371 this->init(init_value);
372}
373
374template <typename T, typename I, typename A>
377 return reinterpret_cast<Atomics_array::element_type &>(
378 this->m_array[this->m_index.translate(index)]);
379}
380
381template <typename T, typename I, typename A>
384 return Iterator{*this, 0};
385}
386
387template <typename T, typename I, typename A>
390 return Iterator{*this, this->m_index.size()};
391}
392
393template <typename T, typename I, typename A>
394template <typename Pred>
396 Pred predicate, size_t start_from) const {
397 for (size_t idx = start_from; idx != this->m_index.size(); ++idx) {
398 auto &current = (*this)[idx];
399 T value = current.load(std::memory_order_relaxed);
400 if (predicate(value, idx)) {
401 return std::make_tuple(value, idx);
402 }
403 }
404 return std::make_tuple(std::numeric_limits<T>::max(), this->m_index.size());
405}
406
407template <typename T, typename I, typename A>
409 size_t start_from) const {
410 for (size_t idx = start_from; idx != this->m_index.size(); ++idx) {
411 auto &current = (*this)[idx];
412 T value = current.load(std::memory_order_relaxed);
413 if (value == to_find) {
414 return idx;
415 }
416 }
417 return this->m_index.size();
418}
419
420template <typename T, typename I, typename A>
422 return this->m_index.size();
423}
424
425template <typename T, typename I, typename A>
427 return this->m_index.size() * I::element_size();
428}
429
430template <typename T, typename I, typename A>
433 for (auto value : (*this)) {
434 out << std::to_string(value) << ", ";
435 }
436 out << "EOF" << std::flush;
437 return out.str();
438}
439
440template <typename T, typename I, typename A>
442 T init_value) {
443 for (size_t idx = 0; idx != this->m_index.size(); ++idx) {
444 ::new (&this->m_array[this->m_index.translate(idx)])
445 element_type(init_value);
446 }
447 return (*this);
448}
449
450#endif // CONTAINER_ATOMIC_INTEGRALS_ARRAY
Iterator helper class to iterate over the array, from 0 to the array size.
Definition: atomics_array.h:101
bool operator!=(Iterator const &rhs) const
Definition: atomics_array.h:349
std::forward_iterator_tag iterator_category
Definition: atomics_array.h:107
size_t m_current
The position of the element this iterator is pointing to.
Definition: atomics_array.h:141
Iterator & operator=(const Iterator &rhs)
Definition: atomics_array.h:297
T reference
Definition: atomics_array.h:106
reference operator*() const
Definition: atomics_array.h:324
Iterator(Atomics_array< T, I, A > const &parent, size_t position)
Definition: atomics_array.h:280
T * pointer
Definition: atomics_array.h:105
T value_type
Definition: atomics_array.h:104
pointer operator->() const
Definition: atomics_array.h:338
Iterator & operator++()
Definition: atomics_array.h:315
std::ptrdiff_t difference_type
Definition: atomics_array.h:103
Atomics_array< T, I, A > const * m_parent
The reference to the queue holding the elements.
Definition: atomics_array.h:143
bool operator==(Iterator const &rhs) const
Definition: atomics_array.h:343
Array of std::atomic elements of type T.
Definition: atomics_array.h:84
T const const_value_type
Definition: atomics_array.h:91
T const & const_reference_type
Definition: atomics_array.h:89
size_t find(T to_find, size_t start_from=0) const
First the first occurrence of to_find, starting at start_from index.
Definition: atomics_array.h:408
T value_type
Definition: atomics_array.h:90
T * pointer_type
Definition: atomics_array.h:86
size_t size() const
Returns the size of the array.
Definition: atomics_array.h:421
container::Atomics_array< T, I, A > & init(T init_value)
Initializes the array.
Definition: atomics_array.h:441
Atomics_array< T, I, A > & operator=(Atomics_array< T, I, A > &&rhs)=delete
std::string to_string() const
Return this queue textual representation.
Definition: atomics_array.h:431
Atomics_array(Atomics_array< T, I, A > const &rhs)=delete
I m_index
The index translation object to be used.
Definition: atomics_array.h:266
std::tuple< T, size_t > find_if(Pred predicate, size_t start_from=0) const
Finds a value in the queue according to the evaluation of predicate by traversing the array from star...
Definition: atomics_array.h:395
T const * const_pointer_type
Definition: atomics_array.h:87
Atomics_array< T, I, A > & operator=(Atomics_array< T, I, A > const &rhs)=delete
Iterator end() const
Retrieves an iterator instance that points to the end of the underlying array.
Definition: atomics_array.h:389
Atomics_array(A &alloc, size_t size, T init_value)
Constructor allowing a specific memory allocator, a specific queue size and the instance of T to init...
Definition: atomics_array.h:357
std::atomic< T > element_type
Definition: atomics_array.h:92
memory::Unique_ptr< unsigned char[], A > m_array
The byte array in which the elements will be stored.
Definition: atomics_array.h:268
size_t allocated_size() const
Returns the number of bytes used to allocate the array.
Definition: atomics_array.h:426
Atomics_array(size_t size, T init_value)
Constructor allowing a specific queue size and the instance of T to initialize the array with.
Definition: atomics_array.h:367
T & reference_type
Definition: atomics_array.h:88
Iterator begin() const
Retrieves an iterator instance that points to the beginning of the array.
Definition: atomics_array.h:383
virtual ~Atomics_array()=default
Destructor for the class.
Atomics_array(Atomics_array< T, I, A > &&rhs)=delete
friend std::ostream & operator<<(std::ostream &out, Atomics_array< T, I, A > &in)
Definition: atomics_array.h:258
element_type & operator[](size_t index) const
Retrieves the value stored in a specific index of the array.
Definition: atomics_array.h:376
Smart pointer to hold a unique pointer to a heap allocated memory of type T, constructed using a spec...
Definition: unique_ptr.h:152
static std::string to_string(const LEX_STRING &str)
Definition: lex_string.h:50
Definition: atomics_array.h:39
Definition: aligned_atomic.h:44
Unique_ptr< T, std::nullptr_t > make_unique(size_t size)
In-place constructs a new unique pointer with no specific allocator and with array type T.
size_t size(const char *const c)
Definition: base64.h:46
static mysql_service_status_t flush(reference_caching_cache cache) noexcept
Definition: component.cc:114
std::basic_ostringstream< char, std::char_traits< char >, ut::allocator< char > > ostringstream
Specialization of basic_ostringstream which uses ut::allocator.
Definition: ut0new.h:2871