1
/*****************************************************************************
3
Copyright (c) 1994, 2009, Innobase Oy. All Rights Reserved.
5
This program is free software; you can redistribute it and/or modify it under
6
the terms of the GNU General Public License as published by the Free Software
7
Foundation; version 2 of the License.
9
This program is distributed in the hope that it will be useful, but WITHOUT
10
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
You should have received a copy of the GNU General Public License along with
14
this program; if not, write to the Free Software Foundation, Inc., 59 Temple
15
Place, Suite 330, Boston, MA 02111-1307 USA
17
*****************************************************************************/
19
/********************************************************************//**
23
Created 6/9/1994 Heikki Tuuri
24
*************************************************************************/
40
The basic element of the memory management is called a memory
41
heap. A memory heap is conceptually a
42
stack from which memory can be allocated. The stack may grow infinitely.
43
The top element of the stack may be freed, or
44
the whole stack can be freed at one time. The advantage of the
45
memory heap concept is that we can avoid using the malloc and free
46
functions of C which are quite expensive, for example, on the Solaris + GCC
47
system (50 MHz Sparc, 1993) the pair takes 3 microseconds,
48
on Win NT + 100MHz Pentium, 2.5 microseconds.
49
When we use a memory heap,
50
we can allocate larger blocks of memory at a time and thus
51
reduce overhead. Slightly more efficient the method is when we
52
allocate the memory from the index page buffer pool, as we can
53
claim a new page fast. This is called buffer allocation.
54
When we allocate the memory from the dynamic memory of the
55
C environment, that is called dynamic allocation.
57
The default way of operation of the memory heap is the following.
58
First, when the heap is created, an initial block of memory is
59
allocated. In dynamic allocation this may be about 50 bytes.
60
If more space is needed, additional blocks are allocated
61
and they are put into a linked list.
62
After the initial block, each allocated block is twice the size of the
63
previous, until a threshold is attained, after which the sizes
64
of the blocks stay the same. An exception is, of course, the case
65
where the caller requests a memory buffer whose size is
66
bigger than the threshold. In that case a block big enough must
69
The heap is physically arranged so that if the current block
70
becomes full, a new block is allocated and always inserted in the
71
chain of blocks as the last block.
73
In the debug version of the memory management, all the allocated
74
heaps are kept in a list (which is implemented as a hash table).
75
Thus we can notice if the caller tries to free an already freed
76
heap. In addition, each buffer given to the caller contains
77
start field at the start and a trailer field at the end of the buffer.
79
The start field has the following content:
80
A. sizeof(ulint) bytes of field length (in the standard byte order)
81
B. sizeof(ulint) bytes of check field (a random number)
83
The trailer field contains:
84
A. sizeof(ulint) bytes of check field (the same random number as at the start)
86
Thus we can notice if something has been copied over the
87
borders of the buffer, which is illegal.
88
The memory in the buffers is initialized to a random byte sequence.
89
After freeing, all the blocks in the heap are set to random bytes
90
to help us discover errors which result from the use of
91
buffers in an already freed heap. */
93
#ifdef MEM_PERIODIC_CHECK
95
ibool mem_block_list_inited;
96
/* List of all mem blocks allocated; protected by the mem_comm_pool mutex */
97
UT_LIST_BASE_NODE_T(mem_block_t) mem_block_list;
101
/**********************************************************************//**
102
Duplicates a NUL-terminated string, allocated from a memory heap.
103
@return own: a copy of the string */
108
mem_heap_t* heap, /*!< in: memory heap where string is allocated */
109
const char* str) /*!< in: string to be copied */
111
return(mem_heap_dup(heap, str, strlen(str) + 1));
114
/**********************************************************************//**
115
Duplicate a block of data, allocated from a memory heap.
116
@return own: a copy of the data */
121
mem_heap_t* heap, /*!< in: memory heap where copy is allocated */
122
const void* data, /*!< in: data to be copied */
123
ulint len) /*!< in: length of data, in bytes */
125
return(memcpy(mem_heap_alloc(heap, len), data, len));
128
/**********************************************************************//**
129
Concatenate two strings and return the result, using a memory heap.
130
@return own: the result */
135
mem_heap_t* heap, /*!< in: memory heap where string is allocated */
136
const char* s1, /*!< in: string 1 */
137
const char* s2) /*!< in: string 2 */
140
ulint s1_len = strlen(s1);
141
ulint s2_len = strlen(s2);
143
s = mem_heap_alloc(heap, s1_len + s2_len + 1);
145
memcpy(s, s1, s1_len);
146
memcpy(s + s1_len, s2, s2_len);
148
s[s1_len + s2_len] = '\0';
154
/****************************************************************//**
155
Helper function for mem_heap_printf.
156
@return length of formatted string, including terminating NUL */
161
char* buf, /*!< in/out: buffer to store formatted string
162
in, or NULL to just calculate length */
163
const char* format, /*!< in: format string */
164
va_list ap) /*!< in: arguments */
170
/* Does this format specifier have the 'l' length modifier. */
171
ibool is_long = FALSE;
173
/* Length of one parameter. */
176
if (*format++ != '%') {
177
/* Non-format character. */
182
*buf++ = *(format - 1);
188
if (*format == 'l') {
197
char* s = va_arg(ap, char*);
199
/* "%ls" is a non-sensical format specifier. */
206
memcpy(buf, s, plen);
219
/* We only support 'long' values for now. */
222
val = va_arg(ap, unsigned long);
224
plen = sprintf(tmp, "%lu", val);
228
memcpy(buf, tmp, plen);
237
/* "%l%" is a non-sensical format specifier. */
253
/* For the NUL character. */
263
/****************************************************************//**
264
A simple (s)printf replacement that dynamically allocates the space for the
265
formatted string from the given heap. This supports a very limited set of
266
the printf syntax: types 's' and 'u' and length modifier 'l' (which is
267
required for the 'u' type).
268
@return heap-allocated formatted string */
273
mem_heap_t* heap, /*!< in: memory heap */
274
const char* format, /*!< in: format string */
281
/* Calculate length of string */
283
va_start(ap, format);
284
len = mem_heap_printf_low(NULL, format, ap);
287
/* Now create it for real. */
288
str = mem_heap_alloc(heap, len);
289
va_start(ap, format);
290
mem_heap_printf_low(str, format, ap);
296
/***************************************************************//**
297
Creates a memory heap block where data can be allocated.
298
@return own: memory heap block, NULL if did not succeed (only possible
299
for MEM_HEAP_BTR_SEARCH type heaps) */
302
mem_heap_create_block(
303
/*==================*/
304
mem_heap_t* heap, /*!< in: memory heap or NULL if first block
306
ulint n, /*!< in: number of bytes needed for user data */
307
ulint type, /*!< in: type of heap: MEM_HEAP_DYNAMIC or
309
const char* file_name,/*!< in: file name where created */
310
ulint line) /*!< in: line where created */
312
#ifndef UNIV_HOTBACKUP
313
buf_block_t* buf_block = NULL;
314
#endif /* !UNIV_HOTBACKUP */
318
ut_ad((type == MEM_HEAP_DYNAMIC) || (type == MEM_HEAP_BUFFER)
319
|| (type == MEM_HEAP_BUFFER + MEM_HEAP_BTR_SEARCH));
321
if (heap && heap->magic_n != MEM_BLOCK_MAGIC_N) {
322
mem_analyze_corruption(heap);
325
/* In dynamic allocation, calculate the size: block header + data. */
326
len = MEM_BLOCK_HEADER_SIZE + MEM_SPACE_NEEDED(n);
328
#ifndef UNIV_HOTBACKUP
329
if (type == MEM_HEAP_DYNAMIC || len < UNIV_PAGE_SIZE / 2) {
331
ut_ad(type == MEM_HEAP_DYNAMIC || n <= MEM_MAX_ALLOC_IN_BUF);
333
block = mem_area_alloc(&len, mem_comm_pool);
335
len = UNIV_PAGE_SIZE;
337
if ((type & MEM_HEAP_BTR_SEARCH) && heap) {
338
/* We cannot allocate the block from the
339
buffer pool, but must get the free block from
340
the heap header free block field */
342
buf_block = heap->free_block;
343
heap->free_block = NULL;
345
if (UNIV_UNLIKELY(!buf_block)) {
350
buf_block = buf_block_alloc(0);
353
block = (mem_block_t*) buf_block->frame;
357
block->buf_block = buf_block;
358
block->free_block = NULL;
359
#else /* !UNIV_HOTBACKUP */
360
len = MEM_BLOCK_HEADER_SIZE + MEM_SPACE_NEEDED(n);
361
block = ut_malloc(len);
363
#endif /* !UNIV_HOTBACKUP */
365
block->magic_n = MEM_BLOCK_MAGIC_N;
366
ut_strlcpy_rev(block->file_name, file_name, sizeof(block->file_name));
369
#ifdef MEM_PERIODIC_CHECK
370
mem_pool_mutex_enter();
372
if (!mem_block_list_inited) {
373
mem_block_list_inited = TRUE;
374
UT_LIST_INIT(mem_block_list);
377
UT_LIST_ADD_LAST(mem_block_list, mem_block_list, block);
379
mem_pool_mutex_exit();
381
mem_block_set_len(block, len);
382
mem_block_set_type(block, type);
383
mem_block_set_free(block, MEM_BLOCK_HEADER_SIZE);
384
mem_block_set_start(block, MEM_BLOCK_HEADER_SIZE);
386
ut_ad((ulint)MEM_BLOCK_HEADER_SIZE < len);
391
/***************************************************************//**
392
Adds a new block to a memory heap.
393
@return created block, NULL if did not succeed (only possible for
394
MEM_HEAP_BTR_SEARCH type heaps) */
399
mem_heap_t* heap, /*!< in: memory heap */
400
ulint n) /*!< in: number of bytes user needs */
403
mem_block_t* new_block;
406
ut_ad(mem_heap_check(heap));
408
block = UT_LIST_GET_LAST(heap->base);
410
/* We have to allocate a new block. The size is always at least
411
doubled until the standard size is reached. After that the size
412
stays the same, except in cases where the caller needs more space. */
414
new_size = 2 * mem_block_get_len(block);
416
if (heap->type != MEM_HEAP_DYNAMIC) {
417
/* From the buffer pool we allocate buffer frames */
418
ut_a(n <= MEM_MAX_ALLOC_IN_BUF);
420
if (new_size > MEM_MAX_ALLOC_IN_BUF) {
421
new_size = MEM_MAX_ALLOC_IN_BUF;
423
} else if (new_size > MEM_BLOCK_STANDARD_SIZE) {
425
new_size = MEM_BLOCK_STANDARD_SIZE;
432
new_block = mem_heap_create_block(heap, new_size, heap->type,
433
heap->file_name, heap->line);
434
if (new_block == NULL) {
439
/* Add the new block as the last block */
441
UT_LIST_INSERT_AFTER(list, heap->base, block, new_block);
446
/******************************************************************//**
447
Frees a block from a memory heap. */
452
mem_heap_t* heap, /*!< in: heap */
453
mem_block_t* block) /*!< in: block to free */
457
#ifndef UNIV_HOTBACKUP
458
buf_block_t* buf_block = block->buf_block;
459
#endif /* !UNIV_HOTBACKUP */
461
if (block->magic_n != MEM_BLOCK_MAGIC_N) {
462
mem_analyze_corruption(block);
465
UT_LIST_REMOVE(list, heap->base, block);
467
#ifdef MEM_PERIODIC_CHECK
468
mem_pool_mutex_enter();
470
UT_LIST_REMOVE(mem_block_list, mem_block_list, block);
472
mem_pool_mutex_exit();
476
block->magic_n = MEM_FREED_BLOCK_MAGIC_N;
478
#ifdef UNIV_MEM_DEBUG
479
/* In the debug version we set the memory to a random combination
480
of hex 0xDE and 0xAD. */
482
mem_erase_buf((byte*)block, len);
483
#else /* UNIV_MEM_DEBUG */
484
UNIV_MEM_ASSERT_AND_FREE(block, len);
485
#endif /* UNIV_MEM_DEBUG */
487
#ifndef UNIV_HOTBACKUP
488
if (type == MEM_HEAP_DYNAMIC || len < UNIV_PAGE_SIZE / 2) {
491
mem_area_free(block, mem_comm_pool);
493
ut_ad(type & MEM_HEAP_BUFFER);
495
buf_block_free(buf_block);
497
#else /* !UNIV_HOTBACKUP */
499
#endif /* !UNIV_HOTBACKUP */
502
#ifndef UNIV_HOTBACKUP
503
/******************************************************************//**
504
Frees the free_block field from a memory heap. */
507
mem_heap_free_block_free(
508
/*=====================*/
509
mem_heap_t* heap) /*!< in: heap */
511
if (UNIV_LIKELY_NULL(heap->free_block)) {
513
buf_block_free(heap->free_block);
515
heap->free_block = NULL;
518
#endif /* !UNIV_HOTBACKUP */
520
#ifdef MEM_PERIODIC_CHECK
521
/******************************************************************//**
522
Goes through the list of all allocated mem blocks, checks their magic
523
numbers, and reports possible corruption. */
526
mem_validate_all_blocks(void)
527
/*=========================*/
531
mem_pool_mutex_enter();
533
block = UT_LIST_GET_FIRST(mem_block_list);
536
if (block->magic_n != MEM_BLOCK_MAGIC_N) {
537
mem_analyze_corruption(block);
540
block = UT_LIST_GET_NEXT(mem_block_list, block);
543
mem_pool_mutex_exit();