MySQL  8.0.21
Source Code Documentation
ut0counter.h
Go to the documentation of this file.
1 /*****************************************************************************
2 
3 Copyright (c) 2012, 2020, Oracle and/or its affiliates. All Rights Reserved.
4 
5 This program is free software; you can redistribute it and/or modify it under
6 the terms of the GNU General Public License, version 2.0, as published by the
7 Free Software Foundation.
8 
9 This program is also distributed with certain software (including but not
10 limited to OpenSSL) that is licensed under separate terms, as designated in a
11 particular file or component or in included license documentation. The authors
12 of MySQL hereby grant you an additional permission to link the program and
13 your derivative works with the separately licensed software that they have
14 included with MySQL.
15 
16 This program is distributed in the hope that it will be useful, but WITHOUT
17 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18 FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
19 for more details.
20 
21 You should have received a copy of the GNU General Public License along with
22 this program; if not, write to the Free Software Foundation, Inc.,
23 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
24 
25 *****************************************************************************/
26 
27 /** @file include/ut0counter.h
28 
29  Counter utility class
30 
31  Created 2012/04/12 by Sunny Bains
32  *******************************************************/
33 
34 #ifndef ut0counter_h
35 #define ut0counter_h
36 
37 #include <my_rdtsc.h>
38 
39 #include "univ.i"
40 
41 #include "os0thread.h"
42 #include "ut0cpu_cache.h"
43 #include "ut0dbg.h"
44 
45 #include <array>
46 #include <atomic>
47 #include <functional>
48 
49 /** Default number of slots to use in ib_counter_t */
50 #define IB_N_SLOTS 64
51 
52 /** Get the offset into the counter array. */
53 template <typename Type, int N>
55  /** Default constructor/destructor should be OK. */
56 
57  /** @return offset within m_counter */
58  static size_t offset(size_t index) UNIV_NOTHROW {
59  return (((index % N) + 1) * (ut::INNODB_CACHE_LINE_SIZE / sizeof(Type)));
60  }
61 };
62 
63 /** Use the result of my_timer_cycles(), which mainly uses RDTSC for cycles,
64 to index into the counter array. See the comments for my_timer_cycles() */
65 template <typename Type = ulint, int N = 1>
66 struct counter_indexer_t : public generic_indexer_t<Type, N> {
67  /** Default constructor/destructor should be OK. */
68 
69  enum { fast = 1 };
70 
71  /** @return result from RDTSC or similar functions. */
72  static size_t get_rnd_index() UNIV_NOTHROW {
73  size_t c = static_cast<size_t>(my_timer_cycles());
74 
75  if (c != 0) {
76  return (c);
77  } else {
78  /* We may go here if my_timer_cycles() returns 0,
79  so we have to have the plan B for the counter. */
80 #if !defined(_WIN32)
81  return (size_t(os_thread_get_curr_id()));
82 #else
83  LARGE_INTEGER cnt;
84  QueryPerformanceCounter(&cnt);
85 
86  return (static_cast<size_t>(cnt.QuadPart));
87 #endif /* !_WIN32 */
88  }
89  }
90 };
91 
92 /** For counters where N=1 */
93 template <typename Type = ulint, int N = 1>
95  /** Default constructor/destructor should are OK. */
96 
97  enum { fast = 0 };
98 
99  /** @return offset within m_counter */
100  static size_t offset(size_t index) UNIV_NOTHROW {
101  ut_ad(N == 1);
102  return ((ut::INNODB_CACHE_LINE_SIZE / sizeof(Type)));
103  }
104 
105  /** @return 1 */
106  static size_t get_rnd_index() UNIV_NOTHROW {
107  ut_ad(N == 1);
108  return (1);
109  }
110 };
111 
112 #define default_indexer_t counter_indexer_t
113 
114 /** Class for using fuzzy counters. The counter is not protected by any
115 mutex and the results are not guaranteed to be 100% accurate but close
116 enough. Creates an array of counters and separates each element by the
117 ut::INNODB_CACHE_LINE_SIZE bytes */
118 template <typename Type, int N = IB_N_SLOTS,
119  template <typename, int> class Indexer = default_indexer_t>
121  public:
122  ib_counter_t() { memset(m_counter, 0x0, sizeof(m_counter)); }
123 
124  ~ib_counter_t() { ut_ad(validate()); }
125 
126  static bool is_fast() { return (Indexer<Type, N>::fast); }
127 
128  bool validate() UNIV_NOTHROW {
129 #ifdef UNIV_DEBUG
130  size_t n = (ut::INNODB_CACHE_LINE_SIZE / sizeof(Type));
131 
132  /* Check that we aren't writing outside our defined bounds. */
133  for (size_t i = 0; i < UT_ARR_SIZE(m_counter); i += n) {
134  for (size_t j = 1; j < n - 1; ++j) {
135  ut_ad(m_counter[i + j] == 0);
136  }
137  }
138 #endif /* UNIV_DEBUG */
139  return (true);
140  }
141 
142  /** If you can't use a good index id. Increment by 1. */
143  void inc() UNIV_NOTHROW { add(1); }
144 
145  /** If you can't use a good index id.
146  @param n is the amount to increment */
147  void add(Type n) UNIV_NOTHROW {
148  size_t i = m_policy.offset(m_policy.get_rnd_index());
149 
150  ut_ad(i < UT_ARR_SIZE(m_counter));
151 
152  m_counter[i] += n;
153  }
154 
155  /** Use this if you can use a unique identifier, saves a
156  call to get_rnd_index().
157  @param index index into a slot
158  @param n amount to increment */
159  void add(size_t index, Type n) UNIV_NOTHROW {
160  size_t i = m_policy.offset(index);
161 
162  ut_ad(i < UT_ARR_SIZE(m_counter));
163 
164  m_counter[i] += n;
165  }
166 
167  /** If you can't use a good index id. Decrement by 1. */
168  void dec() UNIV_NOTHROW { sub(1); }
169 
170  /** If you can't use a good index id.
171  @param n the amount to decrement */
172  void sub(Type n) UNIV_NOTHROW {
173  size_t i = m_policy.offset(m_policy.get_rnd_index());
174 
175  ut_ad(i < UT_ARR_SIZE(m_counter));
176 
177  m_counter[i] -= n;
178  }
179 
180  /** Use this if you can use a unique identifier, saves a
181  call to get_rnd_index().
182  @param index index into a slot
183  @param n amount to decrement */
184  void sub(size_t index, Type n) UNIV_NOTHROW {
185  size_t i = m_policy.offset(index);
186 
187  ut_ad(i < UT_ARR_SIZE(m_counter));
188 
189  m_counter[i] -= n;
190  }
191 
192  /* @return total value - not 100% accurate, since it is not atomic. */
193  operator Type() const UNIV_NOTHROW {
194  Type total = 0;
195 
196  for (size_t i = 0; i < N; ++i) {
197  total += m_counter[m_policy.offset(i)];
198  }
199 
200  return (total);
201  }
202 
203  Type operator[](size_t index) const UNIV_NOTHROW {
204  size_t i = m_policy.offset(index);
205 
206  ut_ad(i < UT_ARR_SIZE(m_counter));
207 
208  return (m_counter[i]);
209  }
210 
211  private:
212  /** Indexer into the array */
213  Indexer<Type, N> m_policy;
214 
215  /** Slot 0 is unused. */
216  Type m_counter[(N + 1) * (ut::INNODB_CACHE_LINE_SIZE / sizeof(Type))];
217 };
218 
219 /** Sharded atomic counter. */
220 namespace Counter {
221 
222 using Type = uint64_t;
223 
224 using N = std::atomic<Type>;
225 
226 static_assert(ut::INNODB_CACHE_LINE_SIZE >= sizeof(N),
227  "Atomic counter size > ut::INNODB_CACHE_LINE_SIZE");
228 
230 
231 /** Counter shard. */
232 struct Shard {
233  /** Separate on cache line. */
235 
236  /** Sharded counter. */
237  N m_n{};
238 };
239 
240 using Function = std::function<void(const Type)>;
241 
242 /** Relaxed order by default. */
243 constexpr auto Memory_order = std::memory_order_relaxed;
244 
245 template <size_t COUNT = 128>
246 struct Shards {
247  /* Shard array. */
248  std::array<Shard, COUNT> m_arr{};
249 
250  /* Memory order for the shards. */
251  std::memory_order m_memory_order{Memory_order};
252 
253  /** Override default memory order.
254  @param[in] memory_order memory order */
255  void set_order(std::memory_order memory_order) {
256  m_memory_order = memory_order;
257  }
258 };
259 
260 /** Increment the counter for a shard by n.
261 @param[in,out] shards Sharded counter to increment.
262 @param[in] id Shard key.
263 @param[in] n Number to add.
264 @return previous value. */
265 template <size_t COUNT>
266 inline Type add(Shards<COUNT> &shards, size_t id, size_t n) {
267  auto &shard_arr = shards.m_arr;
268  auto order = shards.m_memory_order;
269 
270  return (shard_arr[id % shard_arr.size()].m_n.fetch_add(n, order));
271 }
272 
273 /** Decrement the counter for a shard by n.
274 @param[in,out] shards Sharded counter to increment.
275 @param[in] id Shard key.
276 @param[in] n Number to add.
277 @return previous value. */
278 template <size_t COUNT>
279 inline Type sub(Shards<COUNT> &shards, size_t id, size_t n) {
280  ut_ad(get(shards, id) >= n);
281 
282  auto &shard_arr = shards.m_arr;
283  auto order = shards.m_memory_order;
284  return (shard_arr[id % shard_arr.size()].m_n.fetch_sub(n, order));
285 }
286 
287 /** Increment the counter of a shard by 1.
288 @param[in,out] shards Sharded counter to increment.
289 @param[in] id Shard key.
290 @return previous value. */
291 template <size_t COUNT>
292 inline Type inc(Shards<COUNT> &shards, size_t id) {
293  return (add(shards, id, 1));
294 }
295 
296 /** Decrement the counter of a shard by 1.
297 @param[in,out] shards Sharded counter to decrement.
298 @param[in] id Shard key.
299 @return previous value. */
300 template <size_t COUNT>
301 inline Type dec(Shards<COUNT> &shards, size_t id) {
302  return (sub(shards, id, 1));
303 }
304 
305 /** Get the counter value for a shard.
306 @param[in,out] shards Sharded counter to increment.
307 @param[in] id Shard key.
308 @return current value. */
309 template <size_t COUNT>
310 inline Type get(const Shards<COUNT> &shards, size_t id) noexcept {
311  auto &shard_arr = shards.m_arr;
312  auto order = shards.m_memory_order;
313 
314  return (shard_arr[id % shard_arr.size()].m_n.load(order));
315 }
316 
317 /** Iterate over the shards.
318 @param[in] shards Shards to iterate over
319 @param[in] f Callback function
320 */
321 template <size_t COUNT>
322 inline void for_each(const Shards<COUNT> &shards, Function &&f) noexcept {
323  for (const auto &shard : shards.m_arr) {
324  f(shard.m_n);
325  }
326 }
327 
328 /** Get the total value of all shards.
329 @param[in] shards Shards to sum.
330 @return total value. */
331 template <size_t COUNT>
332 inline Type total(const Shards<COUNT> &shards) noexcept {
333  Type n = 0;
334 
335  for_each(shards, [&](const Type count) { n += count; });
336 
337  return (n);
338 }
339 
340 /** Clear the counter - reset to 0.
341 @param[in,out] shards Shards to clear. */
342 template <size_t COUNT>
343 inline void clear(Shards<COUNT> &shards) noexcept {
344  for (auto &shard : shards.m_arr) {
345  shard.m_n.store(0, shards.m_memory_order);
346  }
347 }
348 
349 /** Copy the counters, overwrite destination.
350 @param[in,out] dst Destination shard
351 @param[in] src Source shard. */
352 template <size_t COUNT>
353 inline void copy(Shards<COUNT> &dst, const Shards<COUNT> &src) noexcept {
354  size_t i{0};
355  for_each(src, [&](const Type count) {
356  dst.m_arr[i++].m_n.store(count, dst.m_memory_order);
357  });
358 }
359 
360 /** Accumulate the counters, add source to destination.
361 @param[in,out] dst Destination shard
362 @param[in] src Source shard. */
363 template <size_t COUNT>
364 inline void add(Shards<COUNT> &dst, const Shards<COUNT> &src) noexcept {
365  size_t i{0};
366  for_each(src, [&](const Type count) {
367  dst.m_arr[i++].m_n.fetch_add(count, dst.m_memory_order);
368  });
369 }
370 } // namespace Counter
371 
372 #endif /* ut0counter_h */
void clear(Shards< COUNT > &shards) noexcept
Clear the counter - reset to 0.
Definition: ut0counter.h:343
byte[ut::INNODB_CACHE_LINE_SIZE - sizeof(N)] Pad
Definition: ut0counter.h:229
#define default_indexer_t
Definition: ut0counter.h:112
static size_t offset(size_t index) 1
Definition: ut0counter.h:100
ib_counter_t()
Definition: ut0counter.h:122
static size_t get_rnd_index() 1
Definition: ut0counter.h:72
#define IB_N_SLOTS
Default number of slots to use in ib_counter_t.
Definition: ut0counter.h:50
ssize_t count
Definition: memcached.c:386
Counter shard.
Definition: ut0counter.h:232
void add(Type n) 1
If you can&#39;t use a good index id.
Definition: ut0counter.h:147
void add(size_t index, Type n) 1
Use this if you can use a unique identifier, saves a call to get_rnd_index().
Definition: ut0counter.h:159
void sub(Type n) 1
If you can&#39;t use a good index id.
Definition: ut0counter.h:172
Multi-platform timer code.
Type dec(Shards< COUNT > &shards, size_t id)
Decrement the counter of a shard by 1.
Definition: ut0counter.h:301
The interface to the operating system process and thread control primitives.
void dec() 1
If you can&#39;t use a good index id.
Definition: ut0counter.h:168
Pad m_pad
Separate on cache line.
Definition: ut0counter.h:234
unsigned long id[MAX_DEAD]
Definition: xcom_base.cc:443
Definition: ut0counter.h:246
~ib_counter_t()
Definition: ut0counter.h:124
uint64_t Type
Definition: ut0counter.h:222
void add(Shards< COUNT > &dst, const Shards< COUNT > &src) noexcept
Accumulate the counters, add source to destination.
Definition: ut0counter.h:364
std::atomic< Type > N
Definition: ut0counter.h:224
Type total(const Shards< COUNT > &shards) noexcept
Get the total value of all shards.
Definition: ut0counter.h:332
constexpr auto Memory_order
Relaxed order by default.
Definition: ut0counter.h:243
void for_each(const Shards< COUNT > &shards, Function &&f) noexcept
Iterate over the shards.
Definition: ut0counter.h:322
Indexer< Type, N > m_policy
Indexer into the array.
Definition: ut0counter.h:213
void sub(size_t index, Type n) 1
Use this if you can use a unique identifier, saves a call to get_rnd_index().
Definition: ut0counter.h:184
std::array< Shard, COUNT > m_arr
Definition: ut0counter.h:248
Class for using fuzzy counters.
Definition: ut0counter.h:120
Use the result of my_timer_cycles(), which mainly uses RDTSC for cycles, to index into the counter ar...
Definition: ut0counter.h:66
static size_t offset(size_t index) 1
Default constructor/destructor should be OK.
Definition: ut0counter.h:58
Type operator[](size_t index) const 1
Definition: ut0counter.h:203
Debug utilities for Innobase.
std::function< void(const Type)> Function
Definition: ut0counter.h:240
bool validate() 1
Definition: ut0counter.h:128
#define ut_ad(EXPR)
Debug assertion.
Definition: ut0dbg.h:65
static bool is_fast()
Definition: ut0counter.h:126
void set_order(std::memory_order memory_order)
Override default memory order.
Definition: ut0counter.h:255
Get the offset into the counter array.
Definition: ut0counter.h:54
std::memory_order m_memory_order
Definition: ut0counter.h:251
os_thread_id_t os_thread_get_curr_id()
Returns the thread identifier of current thread.
Definition: os0thread.cc:93
void inc() 1
If you can&#39;t use a good index id.
Definition: ut0counter.h:143
int n
Definition: xcom_base.cc:442
Sharded atomic counter.
Definition: ut0counter.h:220
constexpr size_t INNODB_CACHE_LINE_SIZE
CPU cache line size.
Definition: ut0cpu_cache.h:40
ulonglong my_timer_cycles(void)
A cycle timer.
Definition: my_rdtsc.cc:116
For counters where N=1.
Definition: ut0counter.h:94
Type inc(Shards< COUNT > &shards, size_t id)
Increment the counter of a shard by 1.
Definition: ut0counter.h:292
unsigned char byte
Blob class.
Definition: common.h:159
Utilities related to CPU cache.
static size_t get_rnd_index() 1
Definition: ut0counter.h:106
Type sub(Shards< COUNT > &shards, size_t id, size_t n)
Decrement the counter for a shard by n.
Definition: ut0counter.h:279
void copy(Shards< COUNT > &dst, const Shards< COUNT > &src) noexcept
Copy the counters, overwrite destination.
Definition: ut0counter.h:353