MySQL  8.0.20
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 "ut0dbg.h"
43 
44 #include <array>
45 #include <atomic>
46 #include <functional>
47 
48 /** CPU cache line size */
49 #ifdef __powerpc__
50 #define INNOBASE_CACHE_LINE_SIZE 128
51 #else
52 #define INNOBASE_CACHE_LINE_SIZE 64
53 #endif /* __powerpc__ */
54 
55 /** Default number of slots to use in ib_counter_t */
56 #define IB_N_SLOTS 64
57 
58 /** Get the offset into the counter array. */
59 template <typename Type, int N>
61  /** Default constructor/destructor should be OK. */
62 
63  /** @return offset within m_counter */
64  static size_t offset(size_t index) UNIV_NOTHROW {
65  return (((index % N) + 1) * (INNOBASE_CACHE_LINE_SIZE / sizeof(Type)));
66  }
67 };
68 
69 /** Use the result of my_timer_cycles(), which mainly uses RDTSC for cycles,
70 to index into the counter array. See the comments for my_timer_cycles() */
71 template <typename Type = ulint, int N = 1>
72 struct counter_indexer_t : public generic_indexer_t<Type, N> {
73  /** Default constructor/destructor should be OK. */
74 
75  enum { fast = 1 };
76 
77  /** @return result from RDTSC or similar functions. */
78  static size_t get_rnd_index() UNIV_NOTHROW {
79  size_t c = static_cast<size_t>(my_timer_cycles());
80 
81  if (c != 0) {
82  return (c);
83  } else {
84  /* We may go here if my_timer_cycles() returns 0,
85  so we have to have the plan B for the counter. */
86 #if !defined(_WIN32)
87  return (size_t(os_thread_get_curr_id()));
88 #else
89  LARGE_INTEGER cnt;
90  QueryPerformanceCounter(&cnt);
91 
92  return (static_cast<size_t>(cnt.QuadPart));
93 #endif /* !_WIN32 */
94  }
95  }
96 };
97 
98 /** For counters where N=1 */
99 template <typename Type = ulint, int N = 1>
101  /** Default constructor/destructor should are OK. */
102 
103  enum { fast = 0 };
104 
105  /** @return offset within m_counter */
106  static size_t offset(size_t index) UNIV_NOTHROW {
107  ut_ad(N == 1);
108  return ((INNOBASE_CACHE_LINE_SIZE / sizeof(Type)));
109  }
110 
111  /** @return 1 */
112  static size_t get_rnd_index() UNIV_NOTHROW {
113  ut_ad(N == 1);
114  return (1);
115  }
116 };
117 
118 #define default_indexer_t counter_indexer_t
119 
120 /** Class for using fuzzy counters. The counter is not protected by any
121 mutex and the results are not guaranteed to be 100% accurate but close
122 enough. Creates an array of counters and separates each element by the
123 INNOBASE_CACHE_LINE_SIZE bytes */
124 template <typename Type, int N = IB_N_SLOTS,
125  template <typename, int> class Indexer = default_indexer_t>
127  public:
128  ib_counter_t() { memset(m_counter, 0x0, sizeof(m_counter)); }
129 
130  ~ib_counter_t() { ut_ad(validate()); }
131 
132  static bool is_fast() { return (Indexer<Type, N>::fast); }
133 
134  bool validate() UNIV_NOTHROW {
135 #ifdef UNIV_DEBUG
136  size_t n = (INNOBASE_CACHE_LINE_SIZE / sizeof(Type));
137 
138  /* Check that we aren't writing outside our defined bounds. */
139  for (size_t i = 0; i < UT_ARR_SIZE(m_counter); i += n) {
140  for (size_t j = 1; j < n - 1; ++j) {
141  ut_ad(m_counter[i + j] == 0);
142  }
143  }
144 #endif /* UNIV_DEBUG */
145  return (true);
146  }
147 
148  /** If you can't use a good index id. Increment by 1. */
149  void inc() UNIV_NOTHROW { add(1); }
150 
151  /** If you can't use a good index id.
152  @param n is the amount to increment */
153  void add(Type n) UNIV_NOTHROW {
154  size_t i = m_policy.offset(m_policy.get_rnd_index());
155 
156  ut_ad(i < UT_ARR_SIZE(m_counter));
157 
158  m_counter[i] += n;
159  }
160 
161  /** Use this if you can use a unique identifier, saves a
162  call to get_rnd_index().
163  @param index index into a slot
164  @param n amount to increment */
165  void add(size_t index, Type n) UNIV_NOTHROW {
166  size_t i = m_policy.offset(index);
167 
168  ut_ad(i < UT_ARR_SIZE(m_counter));
169 
170  m_counter[i] += n;
171  }
172 
173  /** If you can't use a good index id. Decrement by 1. */
174  void dec() UNIV_NOTHROW { sub(1); }
175 
176  /** If you can't use a good index id.
177  @param n the amount to decrement */
178  void sub(Type n) UNIV_NOTHROW {
179  size_t i = m_policy.offset(m_policy.get_rnd_index());
180 
181  ut_ad(i < UT_ARR_SIZE(m_counter));
182 
183  m_counter[i] -= n;
184  }
185 
186  /** Use this if you can use a unique identifier, saves a
187  call to get_rnd_index().
188  @param index index into a slot
189  @param n amount to decrement */
190  void sub(size_t index, Type n) UNIV_NOTHROW {
191  size_t i = m_policy.offset(index);
192 
193  ut_ad(i < UT_ARR_SIZE(m_counter));
194 
195  m_counter[i] -= n;
196  }
197 
198  /* @return total value - not 100% accurate, since it is not atomic. */
199  operator Type() const UNIV_NOTHROW {
200  Type total = 0;
201 
202  for (size_t i = 0; i < N; ++i) {
203  total += m_counter[m_policy.offset(i)];
204  }
205 
206  return (total);
207  }
208 
209  Type operator[](size_t index) const UNIV_NOTHROW {
210  size_t i = m_policy.offset(index);
211 
212  ut_ad(i < UT_ARR_SIZE(m_counter));
213 
214  return (m_counter[i]);
215  }
216 
217  private:
218  /** Indexer into the array */
219  Indexer<Type, N> m_policy;
220 
221  /** Slot 0 is unused. */
222  Type m_counter[(N + 1) * (INNOBASE_CACHE_LINE_SIZE / sizeof(Type))];
223 };
224 
225 /** Sharded atomic counter. */
226 namespace Counter {
227 
228 using Type = uint64_t;
229 
230 using N = std::atomic<Type>;
231 
232 static_assert(INNOBASE_CACHE_LINE_SIZE >= sizeof(N),
233  "Atomic counter size > INNOBASE_CACHE_LINE_SIZE");
234 
235 using Pad = byte[INNOBASE_CACHE_LINE_SIZE - sizeof(N)];
236 
237 /** Counter shard. */
238 struct Shard {
239  /** Separate on cache line. */
241 
242  /** Sharded counter. */
243  N m_n{};
244 };
245 
246 template <size_t COUNT = 128>
247 using Shards = std::array<Shard, COUNT>;
248 
249 using Function = std::function<void(const Type)>;
250 
251 constexpr auto Memory_order = std::memory_order_relaxed;
252 
253 /** Increment the counter for a shard by n.
254 @param[in,out] shards Sharded counter to increment.
255 @param[in] id Shard key.
256 @param[in] n Number to add.
257 @return previous value. */
258 template <size_t COUNT>
259 inline Type add(Shards<COUNT> &shards, size_t id, size_t n) {
260  return (shards[id % shards.size()].m_n.fetch_add(n, Memory_order));
261 }
262 
263 /** Decrement the counter for a shard by n.
264 @param[in,out] shards Sharded counter to increment.
265 @param[in] id Shard key.
266 @param[in] n Number to add.
267 @return previous value. */
268 template <size_t COUNT>
269 inline Type sub(Shards<COUNT> &shards, size_t id, size_t n) {
270  return (shards[id % shards.size()].m_n.fetch_sub(n, Memory_order));
271 }
272 
273 /** Increment the counter of a shard by 1.
274 @param[in,out] shards Sharded counter to increment.
275 @param[in] id Shard key.
276 @return previous value. */
277 template <size_t COUNT>
278 inline Type inc(Shards<COUNT> &shards, size_t id) {
279  return (add(shards, id, 1));
280 }
281 
282 /** Decrement the counter of a shard by 1.
283 @param[in,out] shards Sharded counter to decrement.
284 @param[in] id Shard key.
285 @return previous value. */
286 template <size_t COUNT>
287 inline Type dec(Shards<COUNT> &shards, size_t id) {
288  return (sub(shards, id, 1));
289 }
290 
291 /** Get the counter value for a shard.
292 @param[in,out] shards Sharded counter to increment.
293 @param[in] id Shard key.
294 @return current value. */
295 template <size_t COUNT>
296 inline Type get(const Shards<COUNT> &shards, size_t id) noexcept {
297  return (shards[id % shards.size()].m_n.load(Memory_order));
298 }
299 
300 /** Iterate over the shards.
301 @param[in] shards Shards to iterate over
302 @param[in] f Callback function
303 */
304 template <size_t COUNT>
305 inline void for_each(const Shards<COUNT> &shards, Function &&f) noexcept {
306  for (const auto &shard : shards) {
307  f(shard.m_n);
308  }
309 }
310 
311 /** Get the total value of all shards.
312 @param[in] shards Shards to sum.
313 @return total value. */
314 template <size_t COUNT>
315 inline Type total(const Shards<COUNT> &shards) noexcept {
316  Type n = 0;
317 
318  for_each(shards, [&](const Type count) { n += count; });
319 
320  return (n);
321 }
322 
323 /** Clear the counter - reset to 0.
324 @param[in,out] shards Shards to clear. */
325 template <size_t COUNT>
326 inline void clear(Shards<COUNT> &shards) noexcept {
327  for (auto &shard : shards) {
328  shard.m_n.store(0, Memory_order);
329  }
330 }
331 
332 /** Copy the counters, overwrite destination.
333 @param[in,out] dst Destination shard
334 @param[in] src Source shard. */
335 template <size_t COUNT>
336 inline void copy(Shards<COUNT> &dst, const Shards<COUNT> &src) noexcept {
337  size_t i{0};
338  for_each(src, [&](const Type count) {
339  dst[i++].m_n.store(count, std::memory_order_relaxed);
340  });
341 }
342 
343 /** Accumulate the counters, add source to destination.
344 @param[in,out] dst Destination shard
345 @param[in] src Source shard. */
346 template <size_t COUNT>
347 inline void add(Shards<COUNT> &dst, const Shards<COUNT> &src) noexcept {
348  size_t i{0};
349  for_each(src, [&](const Type count) {
350  dst[i++].m_n.fetch_add(count, std::memory_order_relaxed);
351  });
352 }
353 } // namespace Counter
354 
355 #endif /* ut0counter_h */
void clear(Shards< COUNT > &shards) noexcept
Clear the counter - reset to 0.
Definition: ut0counter.h:326
#define default_indexer_t
Definition: ut0counter.h:118
static size_t offset(size_t index) 1
Definition: ut0counter.h:106
ib_counter_t()
Definition: ut0counter.h:128
static size_t get_rnd_index() 1
Definition: ut0counter.h:78
#define IB_N_SLOTS
Default number of slots to use in ib_counter_t.
Definition: ut0counter.h:56
ssize_t count
Definition: memcached.c:386
Counter shard.
Definition: ut0counter.h:238
void add(Type n) 1
If you can&#39;t use a good index id.
Definition: ut0counter.h:153
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:165
void sub(Type n) 1
If you can&#39;t use a good index id.
Definition: ut0counter.h:178
Multi-platform timer code.
Type dec(Shards< COUNT > &shards, size_t id)
Decrement the counter of a shard by 1.
Definition: ut0counter.h:287
The interface to the operating system process and thread control primitives.
unsigned long id[MAX_DEAD]
Definition: xcom_base.c:426
void dec() 1
If you can&#39;t use a good index id.
Definition: ut0counter.h:174
Pad m_pad
Separate on cache line.
Definition: ut0counter.h:240
byte[INNOBASE_CACHE_LINE_SIZE - sizeof(N)] Pad
Definition: ut0counter.h:235
~ib_counter_t()
Definition: ut0counter.h:130
uint64_t Type
Definition: ut0counter.h:228
void add(Shards< COUNT > &dst, const Shards< COUNT > &src) noexcept
Accumulate the counters, add source to destination.
Definition: ut0counter.h:347
std::atomic< Type > N
Definition: ut0counter.h:230
Type total(const Shards< COUNT > &shards) noexcept
Get the total value of all shards.
Definition: ut0counter.h:315
constexpr auto Memory_order
Definition: ut0counter.h:251
void for_each(const Shards< COUNT > &shards, Function &&f) noexcept
Iterate over the shards.
Definition: ut0counter.h:305
#define INNOBASE_CACHE_LINE_SIZE
CPU cache line size.
Definition: ut0counter.h:52
Indexer< Type, N > m_policy
Indexer into the array.
Definition: ut0counter.h:219
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:190
std::array< Shard, COUNT > Shards
Definition: ut0counter.h:247
Class for using fuzzy counters.
Definition: ut0counter.h:126
Use the result of my_timer_cycles(), which mainly uses RDTSC for cycles, to index into the counter ar...
Definition: ut0counter.h:72
static size_t offset(size_t index) 1
Default constructor/destructor should be OK.
Definition: ut0counter.h:64
Type operator[](size_t index) const 1
Definition: ut0counter.h:209
Debug utilities for Innobase.
int n
Definition: xcom_base.c:425
std::function< void(const Type)> Function
Definition: ut0counter.h:249
bool validate() 1
Definition: ut0counter.h:134
#define ut_ad(EXPR)
Debug assertion.
Definition: ut0dbg.h:65
static bool is_fast()
Definition: ut0counter.h:132
Get the offset into the counter array.
Definition: ut0counter.h:60
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:149
Sharded atomic counter.
Definition: ut0counter.h:226
ulonglong my_timer_cycles(void)
A cycle timer.
Definition: my_rdtsc.cc:116
For counters where N=1.
Definition: ut0counter.h:100
Type inc(Shards< COUNT > &shards, size_t id)
Increment the counter of a shard by 1.
Definition: ut0counter.h:278
unsigned char byte
Blob class.
Definition: common.h:159
static size_t get_rnd_index() 1
Definition: ut0counter.h:112
Type sub(Shards< COUNT > &shards, size_t id, size_t n)
Decrement the counter for a shard by n.
Definition: ut0counter.h:269
void copy(Shards< COUNT > &dst, const Shards< COUNT > &src) noexcept
Copy the counters, overwrite destination.
Definition: ut0counter.h:336