MySQL 9.0.0
Source Code Documentation
shared_block_pool.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2024, Oracle and/or its affiliates.
2
3This program is free software; you can redistribute it and/or modify it under
4the terms of the GNU General Public License, version 2.0, as published by the
5Free Software Foundation.
6
7This program is designed to work with certain software (including
8but not limited to OpenSSL) that is licensed under separate terms,
9as designated in a particular file or component or in included license
10documentation. The authors of MySQL hereby grant you an additional
11permission to link the program and your derivative works with the
12separately licensed software that they have either included with
13the program or referenced in the documentation.
14
15This program is distributed in the hope that it will be useful, but WITHOUT
16ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
18for more details.
19
20You should have received a copy of the GNU General Public License along with
21this program; if not, write to the Free Software Foundation, Inc.,
2251 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24/** @file storage/temptable/include/temptable/shared_block_pool.h
25TempTable shared-block pool implementation. */
26
27#ifndef TEMPTABLE_SHARED_BLOCK_POOL_H
28#define TEMPTABLE_SHARED_BLOCK_POOL_H
29
30#include <array>
31#include <cstddef>
32#include <limits>
33
38
39namespace temptable {
40
41/** Lock-free pool of POOL_SIZE Block elements.
42 *
43 * Each Block element in a pool is represented by a slot. Each slot can be
44 * either free (default) or occupied. Acquiring the Block is possible only from
45 * an empty slot. Releasing the Block makes the slot free again.
46 *
47 * Acquiring and releasing the Block is done via THD identifier on which,
48 * implicitly, modulo-arithmethic is applied in order to pick the right slot.
49 * To avoid questionable performance of modulo-arithmetic in its more general
50 * form, POOL_SIZE is constrained only to numbers which are power of two. This
51 * enables us to implement a modulo operation in single bitwise instruction.
52 * Check whether POOL_SIZE is a number which is power of two is run during the
53 * compile-time.
54 *
55 * Given that this pool is envisioned to be used concurrently by multiple
56 * threads, both the slot and Block are aligned to the size of CPU L1
57 * data-cache. This makes sure that we negate the effect of false-sharing
58 * (threads bouncing each ones data from cache).
59 */
60template <size_t POOL_SIZE>
62 /** Check whether all compile-time pre-conditions are set. */
63 static_assert(POOL_SIZE && !(POOL_SIZE & (POOL_SIZE - 1)),
64 "POOL_SIZE template parameter must be a power of two.");
65
66 /** Build a slot type:
67 * a lock-free pool of L1-DCACHE aligned unsigned long long's
68 */
71
72 /** Be pedantic about the element type we used when building the slot type. */
74
75 /** Constexpr variable denoting a non-occupied (free) slot. */
77 std::numeric_limits<Shared_block_slot_element_type>::max();
78
79 /** Bitmask which enables us to implement modulo-arithmetic operation in
80 * single bitwise instruction. */
81 static constexpr size_t MODULO_MASK = POOL_SIZE - 1;
82
83 /** In the event of inability to express ourselves with something like
84 * std::array<alignas<N> Block> we have to fallback to this method.
85 * */
88 };
89
90 /** An array of L1-dcache aligned Blocks
91 * Note: This is _not_ the same as:
92 * alignas(L1_DCACHE_SIZE) std::array<Block, POOL_SIZE>
93 * */
94 std::array<L1_dcache_aligned_block, POOL_SIZE> m_shared_block;
95
96 /** Lock-free slots. */
98
99 public:
100 /** Given the THD identifier, try to acquire an instance of Block. In the
101 * event of success, non-nullptr instance of Block will be returned and
102 * underlying slot will be marked as occupied. Otherwise, slot must have been
103 * already occupied in which case a nullptr will be returned.
104 *
105 * Using the same THD identifier to re-acquire the Block (from the same slot)
106 * is supported but not possible if some other THD identifier is used.
107 *
108 * [in] thd_id THD identifier.
109 * @return Returns a pointer to the Block (success) or nullptr (failure).
110 * */
111 Block *try_acquire(size_t thd_id) {
112 auto slot_idx = thd_id & MODULO_MASK;
113 auto slot_thd_id = FREE_SLOT;
114 if (m_slot.compare_exchange_strong(slot_idx, slot_thd_id, thd_id)) {
115 return &m_shared_block[slot_idx].block;
116 } else if (slot_thd_id == thd_id) {
117 return &m_shared_block[slot_idx].block;
118 } else {
119 return nullptr;
120 }
121 }
122
123 /** Given the THD identifier, try to release an acquired instance of a
124 * Block. In the event of success, slot will be marked as non-occupied.
125 * Assuming that Block is not empty, it will also be destroyed.
126 *
127 * Trying to release the Block/slot by using some other THD identifier is not
128 * possible and will therefore render this operation as failed.
129 *
130 * [in] thd_id THD identifier.
131 * @return Returns true (success) or false (failure).
132 * */
133 bool try_release(size_t thd_id) {
134 auto slot_idx = thd_id & MODULO_MASK;
135 if (m_slot.load(slot_idx) == thd_id) {
136 auto &block = m_shared_block[slot_idx].block;
137 if (!block.is_empty()) {
138 if (block.type() == Source::RAM) {
139 MemoryMonitor::RAM::decrease(block.size());
140 } else if (block.type() == Source::MMAP_FILE) {
141 MemoryMonitor::MMAP::decrease(block.size());
142 }
143 block.destroy();
144 }
145 m_slot.store(slot_idx, FREE_SLOT);
146 return true;
147 }
148 return false;
149 }
150};
151
152} // namespace temptable
153
154#endif /* TEMPTABLE_SHARED_BLOCK_POOL_H */
Block abstraction for temptable-allocator.
Memory-block abstraction whose purpose is to serve as a building block for custom memory-allocator im...
Definition: block.h:163
bool compare_exchange_strong(size_t idx, Lock_free_pool::Type &expected, Lock_free_pool::Type desired, std::memory_order order=std::memory_order_seq_cst)
Atomically compares the object representation of an array element at given index with the expected,...
Definition: lock_free_pool.h:105
typename Lock_free_type< unsigned long long, ALIGNMENT, Lock_free_type_selector >::Type Type
Definition: lock_free_pool.h:51
Lock_free_pool::Type load(size_t idx, std::memory_order order=std::memory_order_seq_cst) const
Atomically loads and returns the current value from an array at given index.
Definition: lock_free_pool.h:88
void store(size_t idx, Lock_free_pool::Type value, std::memory_order order=std::memory_order_seq_cst)
Atomically replaces current value in an array at given index.
Definition: lock_free_pool.h:76
Lock-free pool of POOL_SIZE Block elements.
Definition: shared_block_pool.h:61
std::array< L1_dcache_aligned_block, POOL_SIZE > m_shared_block
An array of L1-dcache aligned Blocks Note: This is not the same as: alignas(L1_DCACHE_SIZE) std::arra...
Definition: shared_block_pool.h:94
bool try_release(size_t thd_id)
Given the THD identifier, try to release an acquired instance of a Block.
Definition: shared_block_pool.h:133
Block * try_acquire(size_t thd_id)
Given the THD identifier, try to acquire an instance of Block.
Definition: shared_block_pool.h:111
Shared_block_slot m_slot
Lock-free slots.
Definition: shared_block_pool.h:97
static constexpr Shared_block_slot_element_type FREE_SLOT
Constexpr variable denoting a non-occupied (free) slot.
Definition: shared_block_pool.h:76
typename Shared_block_slot::Type Shared_block_slot_element_type
Be pedantic about the element type we used when building the slot type.
Definition: shared_block_pool.h:73
static constexpr size_t MODULO_MASK
Bitmask which enables us to implement modulo-arithmetic operation in single bitwise instruction.
Definition: shared_block_pool.h:81
Lock-free pool implementation.
Lock-free type (selection) implementation.
Definition: allocator.h:45
@ MMAP_FILE
Memory is allocated on disk, using mmap()'ed file.
@ RAM
Memory is allocated from RAM, using malloc() for example.
constexpr size_t L1_DCACHE_SIZE
Store L1-dcache size information into the constexpr expression.
Definition: constants.h:82
TempTable constants.
In the event of inability to express ourselves with something like std::array<alignas<N> Block> we ha...
Definition: shared_block_pool.h:86
static size_t decrease(size_t bytes)
Log decrements of MMAP-backed memory consumption.
Definition: allocator.h:95
static size_t decrease(size_t bytes)
Log decrements of heap-memory consumption.
Definition: allocator.h:68