1 /***************************************************************************** 2 3 Copyright (c) 1994, 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/mem0mem.h 28 The memory management 29 30 Created 6/9/1994 Heikki Tuuri 31 *******************************************************/ 32 33 #ifndef mem0mem_h 34 #define mem0mem_h 35 36 #include "mach0data.h" 37 #include "univ.i" 38 #include "ut0byte.h" 39 #include "ut0mem.h" 40 #include "ut0rnd.h" 41 42 #include <limits.h> 43 44 #include <memory> 45 46 /* -------------------- MEMORY HEAPS ----------------------------- */ 47 48 /** A block of a memory heap consists of the info structure 49 followed by an area of memory */ 50 typedef struct mem_block_info_t mem_block_t; 51 52 /** A memory heap is a nonempty linear list of memory blocks */ 53 typedef mem_block_t mem_heap_t; 54 55 /** Types of allocation for memory heaps: DYNAMIC means allocation from the 56 dynamic memory pool of the C compiler, BUFFER means allocation from the 57 buffer pool; the latter method is used for very big heaps */ 58 59 #define MEM_HEAP_DYNAMIC 0 /* the most common type */ 60 #define MEM_HEAP_BUFFER 1 61 #define MEM_HEAP_BTR_SEARCH \ 62 2 /* this flag can optionally be \ 63 ORed to MEM_HEAP_BUFFER, in which \ 64 case heap->free_block is used in \ 65 some cases for memory allocations, \ 66 and if it's NULL, the memory \ 67 allocation functions can return \ 68 NULL. */ 69 70 /** Different type of heaps in terms of which data structure is using them */ 71 #define MEM_HEAP_FOR_BTR_SEARCH (MEM_HEAP_BTR_SEARCH | MEM_HEAP_BUFFER) 72 #define MEM_HEAP_FOR_PAGE_HASH (MEM_HEAP_DYNAMIC) 73 #define MEM_HEAP_FOR_RECV_SYS (MEM_HEAP_BUFFER) 74 #define MEM_HEAP_FOR_LOCK_HEAP (MEM_HEAP_BUFFER) 75 76 /** The following start size is used for the first block in the memory heap if 77 the size is not specified, i.e., 0 is given as the parameter in the call of 78 create. The standard size is the maximum (payload) size of the blocks used for 79 allocations of small buffers. */ 80 81 #define MEM_BLOCK_START_SIZE 64 82 #define MEM_BLOCK_STANDARD_SIZE \ 83 (UNIV_PAGE_SIZE >= 16384 ? 8000 : MEM_MAX_ALLOC_IN_BUF) 84 85 /** If a memory heap is allowed to grow into the buffer pool, the following 86 is the maximum size for a single allocated buffer 87 (from UNIV_PAGE_SIZE we subtract MEM_BLOCK_HEADER_SIZE and 2*MEM_NO_MANS_LAND 88 since it's something we always need to put. Since in MEM_SPACE_NEEDED we round 89 n to the next multiple of UNIV_MEM_ALINGMENT, we need to cut from the rest the 90 part that cannot be divided by UNIV_MEM_ALINGMENT): */ 91 #define MEM_MAX_ALLOC_IN_BUF \ 92 ((UNIV_PAGE_SIZE - MEM_BLOCK_HEADER_SIZE - 2 * MEM_NO_MANS_LAND) & \ 93 ~(UNIV_MEM_ALIGNMENT - 1)) 94 95 /* Before and after any allocated object we will put MEM_NO_MANS_LAND bytes of 96 some data (different before and after) which is supposed not to be modified by 97 anyone. This way it would be much easier to determine whether anyone was 98 writing on not his memory, especially that Valgrind can assure there was no 99 reads or writes to this memory. */ 100 #ifdef UNIV_DEBUG 101 const int MEM_NO_MANS_LAND = 16; 102 #else 103 const int MEM_NO_MANS_LAND = 0; 104 #endif 105 106 /* Byte that we would put before allocated object MEM_NO_MANS_LAND times.*/ 107 const byte MEM_NO_MANS_LAND_BEFORE_BYTE = 0xCE; 108 /* Byte that we would put after allocated object MEM_NO_MANS_LAND times.*/ 109 const byte MEM_NO_MANS_LAND_AFTER_BYTE = 0xDF; 110 111 /** Space needed when allocating for a user a field of length N. 112 The space is allocated only in multiples of UNIV_MEM_ALIGNMENT. In debug mode 113 contains two areas of no mans lands before and after the buffer requested. */ 114 #define MEM_SPACE_NEEDED(N) \ 115 ut_calc_align(N + 2 * MEM_NO_MANS_LAND, UNIV_MEM_ALIGNMENT) 116 117 #ifdef UNIV_DEBUG 118 /** Macro for memory heap creation. 119 @param[in] size Desired start block size. */ 120 #define mem_heap_create(size) \ 121 mem_heap_create_func((size), __FILE__, __LINE__, MEM_HEAP_DYNAMIC) 122 123 /** Macro for memory heap creation. 124 @param[in] size Desired start block size. 125 @param[in] type Heap type */ 126 #define mem_heap_create_typed(size, type) \ 127 mem_heap_create_func((size), __FILE__, __LINE__, (type)) 128 129 #else /* UNIV_DEBUG */ 130 /** Macro for memory heap creation. 131 @param[in] size Desired start block size. */ 132 #define mem_heap_create(size) mem_heap_create_func((size), MEM_HEAP_DYNAMIC) 133 134 /** Macro for memory heap creation. 135 @param[in] size Desired start block size. 136 @param[in] type Heap type */ 137 #define mem_heap_create_typed(size, type) mem_heap_create_func((size), (type)) 138 139 #endif /* UNIV_DEBUG */ 140 141 /** Creates a memory heap. 142 NOTE: Use the corresponding macros instead of this function. 143 A single user buffer of 'size' will fit in the block. 144 0 creates a default size block. 145 @param[in] size Desired start block size. */ 146 #ifdef UNIV_DEBUG 147 /** 148 @param[in] file_name File name where created 149 @param[in] line Line where created */ 150 #endif /* UNIV_DEBUG */ 151 /** 152 @param[in] type Heap type 153 @return own: memory heap, NULL if did not succeed (only possible for 154 MEM_HEAP_BTR_SEARCH type heaps) */ 155 UNIV_INLINE 156 mem_heap_t *mem_heap_create_func(ulint size, 157 #ifdef UNIV_DEBUG 158 const char *file_name, ulint line, 159 #endif /* UNIV_DEBUG */ 160 ulint type); 161 162 /** Frees the space occupied by a memory heap. 163 NOTE: Use the corresponding macro instead of this function. 164 @param[in] heap Heap to be freed */ 165 UNIV_INLINE 166 void mem_heap_free(mem_heap_t *heap); 167 168 /** Allocates and zero-fills n bytes of memory from a memory heap. 169 @param[in] heap memory heap 170 @param[in] n number of bytes; if the heap is allowed to grow into 171 the buffer pool, this must be <= MEM_MAX_ALLOC_IN_BUF 172 @return allocated, zero-filled storage */ 173 UNIV_INLINE 174 void *mem_heap_zalloc(mem_heap_t *heap, ulint n); 175 176 /** Allocates n bytes of memory from a memory heap. 177 @param[in] heap memory heap 178 @param[in] n number of bytes; if the heap is allowed to grow into 179 the buffer pool, this must be <= MEM_MAX_ALLOC_IN_BUF 180 @return allocated storage, NULL if did not succeed (only possible for 181 MEM_HEAP_BTR_SEARCH type heaps) */ 182 UNIV_INLINE 183 void *mem_heap_alloc(mem_heap_t *heap, ulint n); 184 185 /** Returns a pointer to the heap top. 186 @param[in] heap memory heap 187 @return pointer to the heap top */ 188 UNIV_INLINE 189 byte *mem_heap_get_heap_top(mem_heap_t *heap); 190 191 /** Frees the space in a memory heap exceeding the pointer given. 192 The pointer must have been acquired from mem_heap_get_heap_top. 193 The first memory block of the heap is not freed. 194 @param[in] heap heap from which to free 195 @param[in] old_top pointer to old top of heap */ 196 UNIV_INLINE 197 void mem_heap_free_heap_top(mem_heap_t *heap, byte *old_top); 198 199 /** Empties a memory heap. 200 The first memory block of the heap is not freed. 201 @param[in] heap heap to empty */ 202 UNIV_INLINE 203 void mem_heap_empty(mem_heap_t *heap); 204 205 /** Returns a pointer to the topmost element in a memory heap. 206 The size of the element must be given. 207 @param[in] heap memory heap 208 @param[in] n size of the topmost element 209 @return pointer to the topmost element */ 210 UNIV_INLINE 211 void *mem_heap_get_top(mem_heap_t *heap, ulint n); 212 213 /** Checks if a given chunk of memory is the topmost element stored in the 214 heap. If this is the case, then calling mem_heap_free_top() would free 215 that element from the heap. 216 @param[in] heap memory heap 217 @param[in] buf presumed topmost element 218 @param[in] buf_sz size of buf in bytes 219 @return true if topmost */ 220 UNIV_INLINE 221 bool mem_heap_is_top(mem_heap_t *heap, const void *buf, ulint buf_sz) 222 MY_ATTRIBUTE((warn_unused_result)); 223 224 /** Allocate a new chunk of memory from a memory heap, possibly discarding the 225 topmost element. If the memory chunk specified with (top, top_sz) is the 226 topmost element, then it will be discarded, otherwise it will be left untouched 227 and this function will be equivallent to mem_heap_alloc(). 228 @param[in,out] heap memory heap 229 @param[in] top chunk to discard if possible 230 @param[in] top_sz size of top in bytes 231 @param[in] new_sz desired size of the new chunk 232 @return allocated storage, NULL if did not succeed (only possible for 233 MEM_HEAP_BTR_SEARCH type heaps) */ 234 UNIV_INLINE 235 void *mem_heap_replace(mem_heap_t *heap, const void *top, ulint top_sz, 236 ulint new_sz); 237 238 /** Allocate a new chunk of memory from a memory heap, possibly discarding the 239 topmost element and then copy the specified data to it. If the memory chunk 240 specified with (top, top_sz) is the topmost element, then it will be discarded, 241 otherwise it will be left untouched and this function will be equivalent to 242 mem_heap_dup(). 243 @param[in,out] heap memory heap 244 @param[in] top chunk to discard if possible 245 @param[in] top_sz size of top in bytes 246 @param[in] data new data to duplicate 247 @param[in] data_sz size of data in bytes 248 @return allocated storage, NULL if did not succeed (only possible for 249 MEM_HEAP_BTR_SEARCH type heaps) */ 250 UNIV_INLINE 251 void *mem_heap_dup_replace(mem_heap_t *heap, const void *top, ulint top_sz, 252 const void *data, ulint data_sz); 253 254 /** Allocate a new chunk of memory from a memory heap, possibly discarding the 255 topmost element and then copy the specified string to it. If the memory chunk 256 specified with (top, top_sz) is the topmost element, then it will be discarded, 257 otherwise it will be left untouched and this function will be equivalent to 258 mem_heap_strdup(). 259 @param[in,out] heap memory heap 260 @param[in] top chunk to discard if possible 261 @param[in] top_sz size of top in bytes 262 @param[in] str new data to duplicate 263 @return allocated string, NULL if did not succeed (only possible for 264 MEM_HEAP_BTR_SEARCH type heaps) */ 265 UNIV_INLINE 266 char *mem_heap_strdup_replace(mem_heap_t *heap, const void *top, ulint top_sz, 267 const char *str); 268 269 /** Frees the topmost element in a memory heap. 270 @param[in] heap memory heap 271 @param[in] n size of the topmost element 272 The size of the element must be given. */ 273 UNIV_INLINE 274 void mem_heap_free_top(mem_heap_t *heap, ulint n); 275 276 /** Returns the space in bytes occupied by a memory heap. */ 277 UNIV_INLINE 278 ulint mem_heap_get_size(mem_heap_t *heap); /*!< in: heap */ 279 280 /** Duplicates a NUL-terminated string. 281 @param[in] str string to be copied 282 @return own: a copy of the string, must be deallocated with ut_free */ 283 UNIV_INLINE 284 char *mem_strdup(const char *str); 285 286 /** Makes a NUL-terminated copy of a nonterminated string. 287 @param[in] str string to be copied 288 @param[in] len length of str, in bytes 289 @return own: a copy of the string, must be deallocated with ut_free */ 290 UNIV_INLINE 291 char *mem_strdupl(const char *str, ulint len); 292 293 /** Duplicates a NUL-terminated string, allocated from a memory heap. 294 @param[in] heap memory heap where string is allocated 295 @param[in] str string to be copied 296 @return own: a copy of the string */ 297 char *mem_heap_strdup(mem_heap_t *heap, const char *str); 298 299 /** Makes a NUL-terminated copy of a nonterminated string, allocated from a 300 memory heap. 301 @param[in] heap memory heap where string is allocated 302 @param[in] str string to be copied 303 @param[in] len length of str, in bytes 304 @return own: a copy of the string */ 305 UNIV_INLINE 306 char *mem_heap_strdupl(mem_heap_t *heap, const char *str, ulint len); 307 308 /** Concatenate two strings and return the result, using a memory heap. 309 @return own: the result */ 310 char *mem_heap_strcat( 311 mem_heap_t *heap, /*!< in: memory heap where string is allocated */ 312 const char *s1, /*!< in: string 1 */ 313 const char *s2); /*!< in: string 2 */ 314 315 /** Duplicate a block of data, allocated from a memory heap. 316 @return own: a copy of the data */ 317 void *mem_heap_dup( 318 mem_heap_t *heap, /*!< in: memory heap where copy is allocated */ 319 const void *data, /*!< in: data to be copied */ 320 ulint len); /*!< in: length of data, in bytes */ 321 322 /** A simple sprintf replacement that dynamically allocates the space for the 323 formatted string from the given heap. This supports a very limited set of 324 the printf syntax: types 's' and 'u' and length modifier 'l' (which is 325 required for the 'u' type). 326 @return heap-allocated formatted string */ 327 char *mem_heap_printf(mem_heap_t *heap, /*!< in: memory heap */ 328 const char *format, /*!< in: format string */ 329 ...) MY_ATTRIBUTE((format(printf, 2, 3))); 330 331 /** Checks that an object is a memory heap (or a block of it) 332 @param[in] heap Memory heap to check */ 333 UNIV_INLINE 334 void mem_block_validate(const mem_heap_t *heap); 335 336 #ifdef UNIV_DEBUG 337 /** Validates the contents of a memory heap. 338 Asserts that the memory heap is consistent 339 @param[in] heap Memory heap to validate */ 340 void mem_heap_validate(const mem_heap_t *heap); 341 342 #endif /* UNIV_DEBUG */ 343 344 /*#######################################################################*/ 345 346 /** The info structure stored at the beginning of a heap block */ 347 struct mem_block_info_t { 348 uint64_t magic_n; /* magic number for debugging */ 349 #ifdef UNIV_DEBUG 350 char file_name[16]; /* file name where the mem heap was created */ 351 ulint line; /*!< line number where the mem heap was created */ 352 #endif /* UNIV_DEBUG */ 353 UT_LIST_BASE_NODE_T(mem_block_t) 354 base; /* In the first block in the 355 the list this is the base node of the list of blocks; 356 in subsequent blocks this is undefined */ 357 UT_LIST_NODE_T(mem_block_t) 358 list; /* This contains pointers to next 359 and prev in the list. The first block allocated 360 to the heap is also the first block in this list, 361 though it also contains the base node of the list. */ 362 ulint len; /*!< physical length of this block in bytes */ 363 ulint total_size; /*!< physical length in bytes of all blocks 364 in the heap. This is defined only in the base 365 node and is set to ULINT_UNDEFINED in others. */ 366 ulint type; /*!< type of heap: MEM_HEAP_DYNAMIC, or 367 MEM_HEAP_BUF possibly ORed to MEM_HEAP_BTR_SEARCH */ 368 ulint free; /*!< offset in bytes of the first free position for 369 user data in the block */ 370 ulint start; /*!< the value of the struct field 'free' at the 371 creation of the block */ 372 void *free_block; 373 /* if the MEM_HEAP_BTR_SEARCH bit is set in type, 374 and this is the heap root, this can contain an 375 allocated buffer frame, which can be appended as a 376 free block to the heap, if we need more space; 377 otherwise, this is NULL */ 378 void *buf_block; 379 /* if this block has been allocated from the buffer 380 pool, this contains the buf_block_t handle; 381 otherwise, this is NULL */ 382 }; 383 384 #define MEM_BLOCK_MAGIC_N 0x445566778899AABB 385 #define MEM_FREED_BLOCK_MAGIC_N 0xBBAA998877665544 386 387 /* Header size for a memory heap block */ 388 #define MEM_BLOCK_HEADER_SIZE \ 389 ut_calc_align(sizeof(mem_block_info_t), UNIV_MEM_ALIGNMENT) 390 391 #include "mem0mem.ic" 392 393 /** A C++ wrapper class to the mem_heap_t routines, so that it can be used 394 as an STL allocator */ 395 template <typename T> 396 class mem_heap_allocator { 397 public: 398 typedef T value_type; 399 typedef size_t size_type; 400 typedef ptrdiff_t difference_type; 401 typedef T *pointer; 402 typedef const T *const_pointer; 403 typedef T &reference; 404 typedef const T &const_reference; 405 mem_heap_allocator(mem_heap_t * heap)406 mem_heap_allocator(mem_heap_t *heap) : m_heap(heap) {} 407 mem_heap_allocator(const mem_heap_allocator & other)408 mem_heap_allocator(const mem_heap_allocator &other) : m_heap(other.m_heap) { 409 // Do nothing 410 } 411 412 template <typename U> mem_heap_allocator(const mem_heap_allocator<U> & other)413 mem_heap_allocator(const mem_heap_allocator<U> &other) 414 : m_heap(other.m_heap) { 415 // Do nothing 416 } 417 ~mem_heap_allocator()418 ~mem_heap_allocator() { m_heap = nullptr; } 419 max_size()420 size_type max_size() const { return (ULONG_MAX / sizeof(T)); } 421 422 /** This function returns a pointer to the first element of a newly 423 allocated array large enough to contain n objects of type T; only the 424 memory is allocated, and the objects are not constructed. Moreover, 425 an optional pointer argument (that points to an object already 426 allocated by mem_heap_allocator) can be used as a hint to the 427 implementation about where the new memory should be allocated in 428 order to improve locality. */ 429 pointer allocate(size_type n, const_pointer hint = nullptr) { 430 return (reinterpret_cast<pointer>(mem_heap_alloc(m_heap, n * sizeof(T)))); 431 } 432 deallocate(pointer p,size_type n)433 void deallocate(pointer p, size_type n) {} 434 address(reference r)435 pointer address(reference r) const { return (&r); } 436 address(const_reference r)437 const_pointer address(const_reference r) const { return (&r); } 438 construct(pointer p,const_reference t)439 void construct(pointer p, const_reference t) { 440 new (reinterpret_cast<void *>(p)) T(t); 441 } 442 destroy(pointer p)443 void destroy(pointer p) { (reinterpret_cast<T *>(p))->~T(); } 444 445 /** Allocators are required to supply the below template class member 446 which enables the possibility of obtaining a related allocator, 447 parametrized in terms of a different type. For example, given an 448 allocator type IntAllocator for objects of type int, a related 449 allocator type for objects of type long could be obtained using 450 IntAllocator::rebind<long>::other */ 451 template <typename U> 452 struct rebind { 453 typedef mem_heap_allocator<U> other; 454 }; 455 456 /** Get the underlying memory heap object. 457 @return the underlying memory heap object. */ get_mem_heap()458 mem_heap_t *get_mem_heap() const { return (m_heap); } 459 460 private: 461 mem_heap_t *m_heap; 462 template <typename U> 463 friend class mem_heap_allocator; 464 }; 465 466 template <class T> 467 bool operator==(const mem_heap_allocator<T> &left, 468 const mem_heap_allocator<T> &right) { 469 return (left.get_mem_heap() == right.get_mem_heap()); 470 } 471 472 template <class T> 473 bool operator!=(const mem_heap_allocator<T> &left, 474 const mem_heap_allocator<T> &right) { 475 return (left.get_mem_heap() != right.get_mem_heap()); 476 } 477 478 #endif 479