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