MySQL 8.3.0
Source Code Documentation
block.h
Go to the documentation of this file.
1/* Copyright (c) 2019, 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/block.h
24Block abstraction for temptable-allocator. */
25
26#ifndef TEMPTABLE_BLOCK_H
27#define TEMPTABLE_BLOCK_H
28
29#include <cstddef> // size_t
30#include <cstdint> // uint8_t, uintptr_t
31#include <limits> // std::numeric_limits
32#include <sstream> // std::stringstream
33#include <string> // std::string
34
35#include "memory_debugging.h"
36#include "my_dbug.h"
41
42namespace temptable {
43
44/** Initialize the PSI memory engine. */
45void Block_PSI_init();
46/** Log logical (Chunk) memory allocation.
47 *
48 * [in] Number of bytes allocated
49 * */
51/** Log logical (Chunk) memory deallocation.
52 *
53 * [in] Number of bytes deallocated
54 * */
56/** Log physical memory allocation of a Block located in RAM.
57 *
58 * [in] Pointer to user memory block
59 * [in] Number of bytes allocated
60 * */
61void Block_PSI_track_physical_ram_allocation(void *ptr, size_t size);
62/** Log physical memory deallocation of a Block located in RAM.
63 *
64 * [in] Pointer to PSI header
65 * */
67/** Log physical memory allocation of a Block located in MMAP-ed file.
68 *
69 * [in] Pointer to user memory block
70 * [in] Number of bytes allocated
71 * */
72void Block_PSI_track_physical_disk_allocation(void *ptr, size_t size);
73/** Log physical memory deallocation of a Block located in MMAP-ed file.
74 *
75 * [in] Pointer to PSI header
76 * */
78
79/** Memory-block abstraction whose purpose is to serve as a building block
80 * for custom memory-allocator implementations.
81 *
82 * TL;DR How it works:
83 * Instantiation:
84 * - With given size and given memory source, Block will allocate memory
85 * and adjust its Header metadata with the relevant information.
86 * Allocation:
87 * - From allocated memory space, Block finds out what is the next
88 * available slot to fit the new Chunk into.
89 * - Creates a new Chunk with the address pointing to that slot.
90 * - Increments the number of allocated chunks.
91 * - Returns a Chunk.
92 * Deallocation:
93 * - Decrements the number of allocated chunks.
94 * - Returns current number of allocated chunks.
95 * Destruction:
96 * - Simply deallocates the memory.
97 *
98 * Now, more detailed description ...
99 *
100 * Normally, custom memory-allocators will feed clients' memory allocation
101 * and deallocation requests solely through the provided Block interface which
102 * enables allocators not to worry about the whole lot of low-level memory
103 * byte-juggling but to focus on application-level details.
104 *
105 * Block, once created, will occupy at-least (see below why) the specified
106 * amount of memory after which it will be able to serve client-requested
107 * allocations and deallocations in logical units called Chunks. Chunk is
108 * an arbitrarily-sized view over a region of memory allocated during the
109 * Block creation. Block can fit as many Chunks as there is free memory space
110 * left in it. Once there is no free space left, another Block of memory has
111 * to be created. Block is not resizeable. E.g. 4KB-sized Block can feed 1x4KB,
112 * 2x2KB, 1KB+3KB or any other combination of Chunks whose total size does not
113 * exceed the Block size (4KB).
114 *
115 * Organizing Block memory into Chunks is implementation house-keeping detail
116 * stored in its Header metadata region. Block does not maintain the list of
117 * Chunks, it only ever keeps the number of currently allocated Chunks and
118 * the offset to the first memory location available to feed the next
119 * allocation request.
120 *
121 * While still using the same interface, custom memory-allocators are able to
122 * choose where should the Block allocate actual memory from. It could be
123 * anything defined by Source but currently only RAM and MMAP-ed files are
124 * available and implemented as options.
125 *
126 * For the benefit of (amortized) constant-time allocations, Block does not
127 * re-use or do any other special operations over deallocated Chunks so
128 * memory-allocators which will be using it may suffer from block-level
129 * memory-fragmentation and consequently higher memory-consumption. Exceptions
130 * are deallocations of first and last Chunks in a Block when it is possible
131 * to easily re-adjust the offset and therefore be able to re-use that part
132 * of memory.
133 *
134 * Another big advantage, which is very closely related to constant-time
135 * allocations, is that it minimizes the number of system-calls required to
136 * allocate and deallocate the memory which consequently may lower the
137 * process-level memory-fragmentation.
138 *
139 * Block size does not necessarily end-up being the size originally requested by
140 * the client but it will be actually implicitly rounded to the next multiple
141 * of CPU word-size which may result in better memory utilization. Actual block
142 * size can be queried through the Block interface.
143 *
144 * To optimize for the CPU memory-access, but also to enable code not to
145 * segfault on architectures which do not support unaligned-memory-access
146 * (e.g. SPARC), Block will always adjust requested Chunk allocation size to
147 * match the size which is rounded to the next multiple of CPU word-size
148 * (Block::ALIGN_TO constant). End result is that Block might end up allocating
149 * just a few more bytes bigger Chunk than actually requested but that
150 * information, however, does not need to be maintained or cared about by the
151 * client code.
152 *
153 * Along with the small space overhead due to the automatic word-size-adjustment
154 * of Chunk size, each Block allocation will also have a few bytes overhead for
155 * maintaining the Header metadata (Header::SIZE) as well as for maintaining the
156 * Chunk metadata (Chunk::METADATA_SIZE). Implementation and data layout details
157 * can be found at respective header file declarations.
158 *
159 * All dirty-implementation details are hidden in Header implementation
160 * which makes sure that proper care is taken to handle chunk offsets,
161 * available slots, number of present chunks etc. */
162class Block : private Header {
163 public:
164 /** Block will self-adjust all requested allocation-sizes to the multiple of
165 * this value. */
166 static constexpr size_t ALIGN_TO = alignof(void *);
167
168 public:
169 /** Default constructor which creates an empty Block. */
170 Block() noexcept = default;
171
172 /** Constructor which creates a Block of given size from the given
173 * memory source.
174 *
175 * [in] Block size in bytes.
176 * [in] Source where Block will allocate actual memory from. */
177 Block(size_t size, Source memory_source);
178
179 /** Constructor which creates a Block from given Chunk. Chunk holds
180 * just enough information so we can deduce which Block does it belong to.
181 *
182 * [in] Existing Chunk in memory. */
183 explicit Block(Chunk chunk) noexcept;
184
185 /** Equality operator.
186 *
187 * [in] Block to compare it against.
188 * @return true if two Blocks are equal (pointing to the same memory
189 * location). */
190 bool operator==(const Block &other) const;
191
192 /** Inequality operator.
193 *
194 * [in] Block to compare it against.
195 * @return true if two Blocks are not equal (not pointing to the same
196 * memory location). */
197 bool operator!=(const Block &other) const;
198
199 /** Allocate a Chunk from a Block.
200 *
201 * [in] Size of the Chunk to be allocated.
202 * @return Chunk of memory. */
203 Chunk allocate(size_t chunk_size) noexcept;
204
205 /** Deallocate a Chunk from a Block.
206 *
207 * [in] Chunk to be deallocated.
208 * [in] Size of the Chunk to be deallocated.
209 * @return Remaining number of Chunks in a Block. */
210 size_t deallocate(Chunk chunk, size_t chunk_size) noexcept;
211
212 /** Destroy the whole Block. This operation will release all occupied memory
213 * by the Block so client code must make sure that it doesn't keep dangling
214 * Chunks in the memory. */
215 void destroy() noexcept;
216
217 /** Check if Block is empty (not holding any data).
218 *
219 * @return true if it is */
220 bool is_empty() const;
221
222 /** Check if Block can fit (allocate) a Chunk of given size.
223 *
224 * [in] Desired chunk size in bytes.
225 * @return true if can */
226 bool can_accommodate(size_t chunk_size) const;
227
228 /** Get the Block Source type (memory where it resides).
229 *
230 * @return one of Source values */
231 Source type() const;
232
233 /** Get the Block size.
234 *
235 * @return Block size */
236 size_t size() const;
237
238 /** Get current number of Chunks allocated by the Block.
239 *
240 * @return Number of Chunks allocated by this Block */
241 size_t number_of_used_chunks() const;
242
243 /** A human-readable string that describes a Block.
244 *
245 * @return human-readable string */
246 std::string to_string() const;
247
248 /** For given size, how much memory will Block with single Chunk actually
249 * occupy. This calculation takes into account both the Header/Chunk metadata
250 * and the data payload.
251 *
252 * [in] Data payload size in bytes.
253 * @return Size Block would allocate for given n_bytes.
254 * */
255 static size_t size_hint(size_t n_bytes);
256
257 private:
258 /** Delegating constructor which populates Header with provided information.
259 *
260 * [in] Address of a memory region allocated by the Block
261 * [in] Source of memory region
262 * [in] Block size in bytes. */
263 Block(uint8_t *block_memory, Source block_type, size_t block_size) noexcept;
264
265 /** Are we looking at the last (rightmost) chunk in a Block.
266 *
267 * [in] Reference to a Chunk
268 * [in] Chunk size
269 * @return true if we are */
270 bool is_rightmost_chunk(const Chunk &chunk, size_t chunk_size) const;
271
272 /** What is the word-size (ALIGN_TO) aligned size of an input size?
273 *
274 * [in] Input size
275 * @return Block-size rounded up to the next ALIGN_TO size */
276 static size_t aligned_size(size_t size);
277};
278
279static inline uint8_t *allocate_from(Source src, size_t size) {
280 void *ptr = nullptr;
281 size_t raw_size = size;
282#ifdef HAVE_PSI_MEMORY_INTERFACE
283 raw_size += PSI_HEADER_SIZE;
284#endif
285 if (src == Source::RAM) {
286 ptr = Memory<Source::RAM>::allocate(raw_size);
288 } else if (src == Source::MMAP_FILE) {
291 }
292#ifdef HAVE_PSI_MEMORY_INTERFACE
293 return reinterpret_cast<uint8_t *>(HEADER_TO_USER(ptr));
294#else
295 return reinterpret_cast<uint8_t *>(ptr);
296#endif
297}
298
299static inline void deallocate_from(Source src, size_t size,
300 uint8_t *block_address) {
301 size_t raw_size = size;
302 uint8_t *raw_block_address = block_address;
303#ifdef HAVE_PSI_MEMORY_INTERFACE
304 raw_size += PSI_HEADER_SIZE;
305 raw_block_address = USER_TO_HEADER_UINT8_T(block_address);
306#endif
307 if (src == Source::RAM) {
309 Memory<Source::RAM>::deallocate(raw_block_address, raw_size);
310 } else if (src == Source::MMAP_FILE) {
312 Memory<Source::MMAP_FILE>::deallocate(raw_block_address, raw_size);
313 }
314}
315
316inline Block::Block(Chunk chunk) noexcept : Header(chunk.block()) {
317 assert(!is_empty());
318}
319
320inline Block::Block(size_t size, Source memory_source)
321 : Block(allocate_from(memory_source, Block::aligned_size(size)),
322 memory_source, Block::aligned_size(size)) {
323 assert(!is_empty());
324}
325
326inline Block::Block(uint8_t *block_memory, Source block_memory_type,
327 size_t block_size) noexcept
328 : Header(block_memory, block_memory_type, block_size) {
329 assert(!is_empty());
330
331 /* Prevent writes to the memory which we took from the OS but still have
332 * not shipped outside of the Allocator. This will also prevent reads, but
333 * reads would have been reported even without this because the memory we
334 * took from the OS is "undefined" by default. */
336 block_size - Header::SIZE);
337
338 DBUG_PRINT("temptable_allocator", ("block create: size=%zu, new_block=(%s)",
339 block_size, to_string().c_str()));
340}
341
342inline bool Block::operator==(const Block &other) const {
343 return Header::block_address() == other.block_address();
344}
345
346inline bool Block::operator!=(const Block &other) const {
347 return !(Header::block_address() == other.block_address());
348}
349
350inline Chunk Block::allocate(size_t chunk_size) noexcept {
351 assert(!is_empty());
352 assert(can_accommodate(chunk_size));
353
354 const size_t chunk_size_aligned = Block::aligned_size(chunk_size);
355
356 /* Remove the "no access" flag we set on this memory during block
357 * creation. Relax it to report read+depend_on_contents. */
359 Chunk::size_hint(chunk_size_aligned));
360
363
364 Block_PSI_track_logical_allocation(chunk_size_aligned);
365 DBUG_PRINT("temptable_allocator",
366 ("allocate from block: chunk_size=%zu, from_block=(%s); "
367 "return=%p",
368 chunk_size, to_string().c_str(), chunk.data()));
369
370 return chunk;
371}
372
373inline size_t Block::deallocate(Chunk chunk, size_t chunk_size) noexcept {
374 assert(!is_empty());
375 DBUG_PRINT("temptable_allocator",
376 ("deallocate from block: size=%zu, from_block=(%s), chunk_data=%p",
377 chunk_size, to_string().c_str(), chunk.data()));
378
379 const size_t chunk_size_aligned = Block::aligned_size(chunk_size);
380 Block_PSI_track_logical_deallocation(chunk_size_aligned);
381
383 Chunk::size_hint(chunk_size_aligned),
384 is_rightmost_chunk(chunk, Chunk::size_hint(chunk_size_aligned)));
385}
386
387inline void Block::destroy() noexcept {
388 assert(!is_empty());
389 assert(Header::number_of_used_chunks() == 0);
390 DBUG_PRINT("temptable_allocator",
391 ("destroying the block: (%s)", to_string().c_str()));
392
396}
397
398inline bool Block::is_empty() const {
399 return Header::block_address() == nullptr;
400}
401
402inline bool Block::can_accommodate(size_t n_bytes) const {
403 assert(!is_empty());
404
405 const size_t n_bytes_aligned = Block::aligned_size(n_bytes);
406 const size_t block_size = Header::block_size();
408 assert(first_pristine_offset <=
409 std::numeric_limits<decltype(block_size)>::max() -
410 Chunk::size_hint(n_bytes_aligned));
411
412 return first_pristine_offset + Chunk::size_hint(n_bytes_aligned) <=
414}
415
416inline Source Block::type() const {
417 assert(!is_empty());
419}
420
421inline size_t Block::size() const {
422 assert(!is_empty());
423 return Header::block_size();
424}
425
426inline size_t Block::number_of_used_chunks() const {
427 assert(!is_empty());
429}
430
431inline std::string Block::to_string() const {
432 assert(!is_empty());
433 std::stringstream s;
434 s << "address=" << static_cast<void *>(Header::block_address())
435 << ", size=" << Header::block_size()
436 << ", num_chunks=" << Header::number_of_used_chunks()
437 << ", first_pristine=" << Header::first_pristine_offset();
438 return s.str();
439}
440
441inline bool Block::is_rightmost_chunk(const Chunk &chunk,
442 size_t size_bytes) const {
443 assert(!is_empty());
444 return chunk.offset() + size_bytes == Header::first_pristine_offset();
445}
446
447inline size_t Block::size_hint(size_t n_bytes) {
449}
450
451inline size_t Block::aligned_size(size_t size) {
452 return (size + Block::ALIGN_TO - 1) & ~(Block::ALIGN_TO - 1);
453}
454
455} /* namespace temptable */
456
457#endif /* TEMPTABLE_BLOCK_H */
Chunk abstraction for temptable Block allocator.
Memory-block abstraction whose purpose is to serve as a building block for custom memory-allocator im...
Definition: block.h:162
Source type() const
Get the Block Source type (memory where it resides).
Definition: block.h:416
bool is_empty() const
Check if Block is empty (not holding any data).
Definition: block.h:398
std::string to_string() const
A human-readable string that describes a Block.
Definition: block.h:431
void destroy() noexcept
Destroy the whole Block.
Definition: block.h:387
size_t deallocate(Chunk chunk, size_t chunk_size) noexcept
Deallocate a Chunk from a Block.
Definition: block.h:373
bool can_accommodate(size_t chunk_size) const
Check if Block can fit (allocate) a Chunk of given size.
Definition: block.h:402
size_t number_of_used_chunks() const
Get current number of Chunks allocated by the Block.
Definition: block.h:426
static constexpr size_t ALIGN_TO
Block will self-adjust all requested allocation-sizes to the multiple of this value.
Definition: block.h:166
size_t size() const
Get the Block size.
Definition: block.h:421
Block() noexcept=default
Default constructor which creates an empty Block.
bool operator==(const Block &other) const
Equality operator.
Definition: block.h:342
bool operator!=(const Block &other) const
Inequality operator.
Definition: block.h:346
Chunk allocate(size_t chunk_size) noexcept
Allocate a Chunk from a Block.
Definition: block.h:350
bool is_rightmost_chunk(const Chunk &chunk, size_t chunk_size) const
Are we looking at the last (rightmost) chunk in a Block.
Definition: block.h:441
static size_t aligned_size(size_t size)
What is the word-size (ALIGN_TO) aligned size of an input size?
Definition: block.h:451
static size_t size_hint(size_t n_bytes)
For given size, how much memory will Block with single Chunk actually occupy.
Definition: block.h:447
Chunk is an abstraction with the purpose of representing a smallest logical memory-unit within the Bl...
Definition: chunk.h:67
size_t offset() const
Get the Chunk offset relative to the start of belonging Block.
Definition: chunk.h:153
static size_t size_hint(size_t n_bytes)
For given size, how much memory will be occupied by the Chunk.
Definition: chunk.h:159
Header is an abstraction with the purpose of holding and maintaining the Block metadata.
Definition: header.h:73
uint8_t * next_available_slot() const
Enable Block to get the next available slot that it can use for next Chunk allocation.
Definition: header.h:190
size_t block_size() const
Get the Block size.
Definition: header.h:200
void reset()
Enable Block to reset the Header metadata upon Block destruction.
Definition: header.h:235
Source memory_source_type() const
Get the Block Source type (memory where it resides).
Definition: header.h:196
Header() noexcept
Default constructor which creates an empty Header.
Definition: header.h:172
uint8_t * block_address() const
Enable Block to get its memory address.
Definition: header.h:194
size_t increment_number_of_used_chunks(size_t chunk_size)
Enable Block to increment the reference-count when (logically) allocating new Chunks.
Definition: header.h:212
static constexpr size_t SIZE
Block header (metadata) size.
Definition: header.h:79
size_t decrement_number_of_used_chunks(size_t chunk_size, bool rightmost_chunk)
Enable Block to decrement the reference-count when (logically) deallocating existing Chunks.
Definition: header.h:217
size_t first_pristine_offset() const
Get current first-pristine-offset.
Definition: header.h:208
size_t number_of_used_chunks() const
Get current number of Chunks allocated by the Block.
Definition: header.h:204
#define USER_TO_HEADER_UINT8_T(P)
Definition: mysql_memory.h:95
#define PSI_HEADER_SIZE
Definition: mysql_memory.h:85
Header abstraction for temptable Block allocator.
static std::string to_string(const LEX_STRING &str)
Definition: lex_string.h:49
Various macros useful for communicating with memory debuggers, such as Valgrind.
#define MEM_NOACCESS(a, len)
Definition: memory_debugging.h:59
#define MEM_UNDEFINED(a, len)
Definition: memory_debugging.h:57
Memory utilities for temptable-allocator.
#define DBUG_PRINT(keyword, arglist)
Definition: my_dbug.h:180
#define HEADER_TO_USER(P)
Definition: my_memory.cc:46
Instrumentation helpers for memory allocation.
Definition: varlen_sort.h:174
Definition: allocator.h:44
static void deallocate_from(Source src, size_t size, uint8_t *block_address)
Definition: block.h:299
void Block_PSI_init()
Initialize the PSI memory engine.
Definition: block.cc:73
void Block_PSI_track_physical_ram_allocation(void *ptr, size_t size)
Log physical memory allocation of a Block located in RAM.
Definition: block.cc:102
void Block_PSI_track_physical_disk_allocation(void *ptr, size_t size)
Log physical memory allocation of a Block located in MMAP-ed file.
Definition: block.cc:125
void Block_PSI_track_physical_ram_deallocation(uint8_t *ptr)
Log physical memory deallocation of a Block located in RAM.
Definition: block.cc:115
static uint8_t * allocate_from(Source src, size_t size)
Definition: block.h:279
Source
Type of memory allocated.
Definition: memutils.h:67
@ MMAP_FILE
Memory is allocated on disk, using mmap()'ed file.
@ RAM
Memory is allocated from RAM, using malloc() for example.
void Block_PSI_track_physical_disk_deallocation(uint8_t *ptr)
Log physical memory deallocation of a Block located in MMAP-ed file.
Definition: block.cc:138
void Block_PSI_track_logical_deallocation(size_t size)
Log logical (Chunk) memory deallocation.
Definition: block.cc:94
void Block_PSI_track_logical_allocation(size_t size)
Log logical (Chunk) memory allocation.
Definition: block.cc:80
static void deallocate(void *ptr, size_t bytes)
static void * allocate(size_t bytes)