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