MySQL 8.2.0
Source Code Documentation
ut0counter.h
Go to the documentation of this file.
1/*****************************************************************************
2
3Copyright (c) 2012, 2023, Oracle and/or its affiliates.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License, version 2.0, as published by the
7Free Software Foundation.
8
9This program is also distributed with certain software (including but not
10limited to OpenSSL) that is licensed under separate terms, as designated in a
11particular file or component or in included license documentation. The authors
12of MySQL hereby grant you an additional permission to link the program and
13your derivative works with the separately licensed software that they have
14included with MySQL.
15
16This program is distributed in the hope that it will be useful, but WITHOUT
17ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
19for more details.
20
21You should have received a copy of the GNU General Public License along with
22this program; if not, write to the Free Software Foundation, Inc.,
2351 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 */
50constexpr uint32_t IB_N_SLOTS = 64;
51
52/** Get the offset into the counter array. */
53template <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,
64to index into the counter array. See the comments for my_timer_cycles() */
65template <typename Type = ulint, int N = 1>
66struct 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)
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 */
93template <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 [[maybe_unused]]) UNIV_NOTHROW {
101 static_assert(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 static_assert(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
115mutex and the results are not guaranteed to be 100% accurate but close
116enough. Creates an array of counters and separates each element by the
117ut::INNODB_CACHE_LINE_SIZE bytes */
118template <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
125
126 static bool is_fast() { return (Indexer<Type, N>::fast); }
127
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 */
148 size_t i = m_policy.offset(m_policy.get_rnd_index());
149
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
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 */
173 size_t i = m_policy.offset(m_policy.get_rnd_index());
174
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
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
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. */
217};
218
219/** Sharded atomic counter. */
220namespace Counter {
221
222using Type = uint64_t;
223
224using N = std::atomic<Type>;
225
226static_assert(ut::INNODB_CACHE_LINE_SIZE >= sizeof(N),
227 "Atomic counter size > ut::INNODB_CACHE_LINE_SIZE");
228
229using Pad = byte[ut::INNODB_CACHE_LINE_SIZE - sizeof(N)];
230
231/** Counter shard. */
232struct Shard {
233 /** Separate on cache line. */
235
236 /** Sharded counter. */
238};
239
240using Function = std::function<void(const Type)>;
241
242/** Relaxed order by default. */
243constexpr auto Memory_order = std::memory_order_relaxed;
244
245template <size_t COUNT = 128>
246struct 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. */
265template <size_t COUNT>
266inline 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. */
278template <size_t COUNT>
279inline 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. */
291template <size_t COUNT>
292inline 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. */
300template <size_t COUNT>
301inline 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. */
309template <size_t COUNT>
310inline 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*/
321template <size_t COUNT>
322inline 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. */
331template <size_t COUNT>
332inline 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. */
342template <size_t COUNT>
343inline 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. */
352template <size_t COUNT>
353inline 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. */
363template <size_t COUNT>
364inline 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 */
Class for using fuzzy counters.
Definition: ut0counter.h:120
static bool is_fast()
Definition: ut0counter.h:126
void sub(Type n) 1
If you can't use a good index id.
Definition: ut0counter.h:172
void add(Type n) 1
If you can'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
ib_counter_t()
Definition: ut0counter.h:122
bool validate() 1
Definition: ut0counter.h:128
void dec() 1
If you can't use a good index id.
Definition: ut0counter.h:168
Type operator[](size_t index) const 1
Definition: ut0counter.h:203
Type m_counter[(N+1) *(ut::INNODB_CACHE_LINE_SIZE/sizeof(Type))]
Slot 0 is unused.
Definition: ut0counter.h:216
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
~ib_counter_t()
Definition: ut0counter.h:124
void inc() 1
If you can't use a good index id.
Definition: ut0counter.h:143
Multi-platform timer code.
ulonglong my_timer_cycles(void)
A cycle timer.
Definition: my_rdtsc.cc:97
static int count
Definition: myisam_ftdump.cc:44
Sharded atomic counter.
Definition: ut0counter.h:220
Type inc(Shards< COUNT > &shards, size_t id)
Increment the counter of a shard by 1.
Definition: ut0counter.h:292
std::function< void(const Type)> Function
Definition: ut0counter.h:240
uint64_t Type
Definition: ut0counter.h:222
Type add(Shards< COUNT > &shards, size_t id, size_t n)
Increment the counter for a shard by n.
Definition: ut0counter.h:266
byte[ut::INNODB_CACHE_LINE_SIZE - sizeof(N)] Pad
Definition: ut0counter.h:229
void copy(Shards< COUNT > &dst, const Shards< COUNT > &src) noexcept
Copy the counters, overwrite destination.
Definition: ut0counter.h:353
constexpr auto Memory_order
Relaxed order by default.
Definition: ut0counter.h:243
Type dec(Shards< COUNT > &shards, size_t id)
Decrement the counter of a shard by 1.
Definition: ut0counter.h:301
Type total(const Shards< COUNT > &shards) noexcept
Get the total value of all shards.
Definition: ut0counter.h:332
Type sub(Shards< COUNT > &shards, size_t id, size_t n)
Decrement the counter for a shard by n.
Definition: ut0counter.h:279
void for_each(const Shards< COUNT > &shards, Function &&f) noexcept
Iterate over the shards.
Definition: ut0counter.h:322
std::atomic< Type > N
Definition: ut0counter.h:224
void clear(Shards< COUNT > &shards) noexcept
Clear the counter - reset to 0.
Definition: ut0counter.h:343
Type get(const Shards< COUNT > &shards, size_t id) noexcept
Get the counter value for a shard.
Definition: ut0counter.h:310
constexpr size_t INNODB_CACHE_LINE_SIZE
CPU cache line size.
Definition: ut0cpu_cache.h:40
const thread_local size_t this_thread_hash
The hash value of the current thread's id.
Definition: os0thread.h:72
The interface to the operating system process and thread control primitives.
Counter shard.
Definition: ut0counter.h:232
N m_n
Sharded counter.
Definition: ut0counter.h:237
Pad m_pad
Separate on cache line.
Definition: ut0counter.h:234
Definition: ut0counter.h:246
void set_order(std::memory_order memory_order)
Override default memory order.
Definition: ut0counter.h:255
std::array< Shard, COUNT > m_arr
Definition: ut0counter.h:248
std::memory_order m_memory_order
Definition: ut0counter.h:251
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 get_rnd_index() 1
Definition: ut0counter.h:72
@ fast
Definition: ut0counter.h:69
Get the offset into the counter array.
Definition: ut0counter.h:54
static size_t offset(size_t index) 1
Default constructor/destructor should be OK.
Definition: ut0counter.h:58
For counters where N=1.
Definition: ut0counter.h:94
static size_t get_rnd_index() 1
Definition: ut0counter.h:106
@ fast
Definition: ut0counter.h:97
static size_t offset(size_t index) 1
Definition: ut0counter.h:100
Version control for database, common definitions, and include files.
#define UNIV_NOTHROW
Definition: univ.i:455
#define UT_ARR_SIZE(a)
Definition: univ.i:523
constexpr uint32_t IB_N_SLOTS
Default number of slots to use in ib_counter_t.
Definition: ut0counter.h:50
#define default_indexer_t
Definition: ut0counter.h:112
Utilities related to CPU cache.
Debug utilities for Innobase.
#define ut_ad(EXPR)
Debug assertion.
Definition: ut0dbg.h:68
int n
Definition: xcom_base.cc:508