← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/innobase/mem/mem0mem.c

  • Committer: Moriyoshi Koizumi
  • Date: 2008-11-15 18:36:31 UTC
  • mto: (584.1.5 devel)
  • mto: This revision was merged to the branch mainline in revision 588.
  • Revision ID: mozo@mozo.jp-20081115183631-81d0clowyot42mk7
Incorporating changes proposed by mtaylor.

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/innobase/mem/mem0mem.c
 
1
/************************************************************************
 
2
The memory management
 
3
 
 
4
(c) 1994, 1995 Innobase Oy
 
5
 
 
6
Created 6/9/1994 Heikki Tuuri
 
7
*************************************************************************/
 
8
 
 
9
 
 
10
#include "mem0mem.h"
 
11
#ifdef UNIV_NONINL
 
12
#include "mem0mem.ic"
 
13
#endif
 
14
 
 
15
#include "mach0data.h"
 
16
#include "buf0buf.h"
 
17
#include "btr0sea.h"
 
18
#include "srv0srv.h"
 
19
#include "mem0dbg.c"
 
20
#include <stdarg.h>
 
21
 
 
22
/*
 
23
                        THE MEMORY MANAGEMENT
 
24
                        =====================
 
25
 
 
26
The basic element of the memory management is called a memory
 
27
heap. A memory heap is conceptually a
 
28
stack from which memory can be allocated. The stack may grow infinitely.
 
29
The top element of the stack may be freed, or
 
30
the whole stack can be freed at one time. The advantage of the
 
31
memory heap concept is that we can avoid using the malloc and free
 
32
functions of C which are quite expensive, for example, on the Solaris + GCC
 
33
system (50 MHz Sparc, 1993) the pair takes 3 microseconds,
 
34
on Win NT + 100MHz Pentium, 2.5 microseconds.
 
35
When we use a memory heap,
 
36
we can allocate larger blocks of memory at a time and thus
 
37
reduce overhead. Slightly more efficient the method is when we
 
38
allocate the memory from the index page buffer pool, as we can
 
39
claim a new page fast. This is called buffer allocation.
 
40
When we allocate the memory from the dynamic memory of the
 
41
C environment, that is called dynamic allocation.
 
42
 
 
43
The default way of operation of the memory heap is the following.
 
44
First, when the heap is created, an initial block of memory is
 
45
allocated. In dynamic allocation this may be about 50 bytes.
 
46
If more space is needed, additional blocks are allocated
 
47
and they are put into a linked list.
 
48
After the initial block, each allocated block is twice the size of the
 
49
previous, until a threshold is attained, after which the sizes
 
50
of the blocks stay the same. An exception is, of course, the case
 
51
where the caller requests a memory buffer whose size is
 
52
bigger than the threshold. In that case a block big enough must
 
53
be allocated.
 
54
 
 
55
The heap is physically arranged so that if the current block
 
56
becomes full, a new block is allocated and always inserted in the
 
57
chain of blocks as the last block.
 
58
 
 
59
In the debug version of the memory management, all the allocated
 
60
heaps are kept in a list (which is implemented as a hash table).
 
61
Thus we can notice if the caller tries to free an already freed
 
62
heap. In addition, each buffer given to the caller contains
 
63
start field at the start and a trailer field at the end of the buffer.
 
64
 
 
65
The start field has the following content:
 
66
A. sizeof(ulint) bytes of field length (in the standard byte order)
 
67
B. sizeof(ulint) bytes of check field (a random number)
 
68
 
 
69
The trailer field contains:
 
70
A. sizeof(ulint) bytes of check field (the same random number as at the start)
 
71
 
 
72
Thus we can notice if something has been copied over the
 
73
borders of the buffer, which is illegal.
 
74
The memory in the buffers is initialized to a random byte sequence.
 
75
After freeing, all the blocks in the heap are set to random bytes
 
76
to help us discover errors which result from the use of
 
77
buffers in an already freed heap. */
 
78
 
 
79
#ifdef MEM_PERIODIC_CHECK
 
80
 
 
81
ibool                                   mem_block_list_inited;
 
82
/* List of all mem blocks allocated; protected by the mem_comm_pool mutex */
 
83
UT_LIST_BASE_NODE_T(mem_block_t)        mem_block_list;
 
84
 
 
85
#endif
 
86
 
 
87
/**************************************************************************
 
88
Duplicates a NUL-terminated string, allocated from a memory heap. */
 
89
UNIV_INTERN
 
90
char*
 
91
mem_heap_strdup(
 
92
/*============*/
 
93
                                /* out, own: a copy of the string */
 
94
        mem_heap_t*     heap,   /* in: memory heap where string is allocated */
 
95
        const char*     str)    /* in: string to be copied */
 
96
{
 
97
        return(mem_heap_dup(heap, str, strlen(str) + 1));
 
98
}
 
99
 
 
100
/**************************************************************************
 
101
Duplicate a block of data, allocated from a memory heap. */
 
102
UNIV_INTERN
 
103
void*
 
104
mem_heap_dup(
 
105
/*=========*/
 
106
                                /* out, own: a copy of the data */
 
107
        mem_heap_t*     heap,   /* in: memory heap where copy is allocated */
 
108
        const void*     data,   /* in: data to be copied */
 
109
        ulint           len)    /* in: length of data, in bytes */
 
110
{
 
111
        return(memcpy(mem_heap_alloc(heap, len), data, len));
 
112
}
 
113
 
 
114
/**************************************************************************
 
115
Concatenate two memory blocks and return the result, using a memory heap. */
 
116
UNIV_INTERN
 
117
void*
 
118
mem_heap_cat(
 
119
/*=========*/
 
120
                                /* out, own: the result */
 
121
        mem_heap_t*     heap,   /* in: memory heap where result is allocated */
 
122
        const void*     b1,     /* in: block 1 */
 
123
        ulint           len1,   /* in: length of b1, in bytes */
 
124
        const void*     b2,     /* in: block 2 */
 
125
        ulint           len2)   /* in: length of b2, in bytes */
 
126
{
 
127
        void*   res = mem_heap_alloc(heap, len1 + len2);
 
128
 
 
129
        memcpy(res, b1, len1);
 
130
        memcpy((char*)res + len1, b2, len2);
 
131
 
 
132
        return(res);
 
133
}
 
134
 
 
135
/**************************************************************************
 
136
Concatenate two strings and return the result, using a memory heap. */
 
137
UNIV_INTERN
 
138
char*
 
139
mem_heap_strcat(
 
140
/*============*/
 
141
                                /* out, own: the result */
 
142
        mem_heap_t*     heap,   /* in: memory heap where string is allocated */
 
143
        const char*     s1,     /* in: string 1 */
 
144
        const char*     s2)     /* in: string 2 */
 
145
{
 
146
        char*   s;
 
147
        ulint   s1_len = strlen(s1);
 
148
        ulint   s2_len = strlen(s2);
 
149
 
 
150
        s = mem_heap_alloc(heap, s1_len + s2_len + 1);
 
151
 
 
152
        memcpy(s, s1, s1_len);
 
153
        memcpy(s + s1_len, s2, s2_len);
 
154
 
 
155
        s[s1_len + s2_len] = '\0';
 
156
 
 
157
        return(s);
 
158
}
 
159
 
 
160
 
 
161
/********************************************************************
 
162
Helper function for mem_heap_printf. */
 
163
static
 
164
ulint
 
165
mem_heap_printf_low(
 
166
/*================*/
 
167
                                /* out: length of formatted string,
 
168
                                including terminating NUL */
 
169
        char*           buf,    /* in/out: buffer to store formatted string
 
170
                                in, or NULL to just calculate length */
 
171
        const char*     format, /* in: format string */
 
172
        va_list         ap)     /* in: arguments */
 
173
{
 
174
        ulint           len = 0;
 
175
 
 
176
        while (*format) {
 
177
 
 
178
                /* Does this format specifier have the 'l' length modifier. */
 
179
                ibool   is_long = FALSE;
 
180
 
 
181
                /* Length of one parameter. */
 
182
                size_t  plen;
 
183
 
 
184
                if (*format++ != '%') {
 
185
                        /* Non-format character. */
 
186
 
 
187
                        len++;
 
188
 
 
189
                        if (buf) {
 
190
                                *buf++ = *(format - 1);
 
191
                        }
 
192
 
 
193
                        continue;
 
194
                }
 
195
 
 
196
                if (*format == 'l') {
 
197
                        is_long = TRUE;
 
198
                        format++;
 
199
                }
 
200
 
 
201
                switch (*format++) {
 
202
                case 's':
 
203
                        /* string */
 
204
                        {
 
205
                                char*   s = va_arg(ap, char*);
 
206
 
 
207
                                /* "%ls" is a non-sensical format specifier. */
 
208
                                ut_a(!is_long);
 
209
 
 
210
                                plen = strlen(s);
 
211
                                len += plen;
 
212
 
 
213
                                if (buf) {
 
214
                                        memcpy(buf, s, plen);
 
215
                                        buf += plen;
 
216
                                }
 
217
                        }
 
218
 
 
219
                        break;
 
220
 
 
221
                case 'u':
 
222
                        /* unsigned int */
 
223
                        {
 
224
                                char            tmp[32];
 
225
                                unsigned long   val;
 
226
 
 
227
                                /* We only support 'long' values for now. */
 
228
                                ut_a(is_long);
 
229
 
 
230
                                val = va_arg(ap, unsigned long);
 
231
 
 
232
                                plen = sprintf(tmp, "%lu", val);
 
233
                                len += plen;
 
234
 
 
235
                                if (buf) {
 
236
                                        memcpy(buf, tmp, plen);
 
237
                                        buf += plen;
 
238
                                }
 
239
                        }
 
240
 
 
241
                        break;
 
242
 
 
243
                case '%':
 
244
 
 
245
                        /* "%l%" is a non-sensical format specifier. */
 
246
                        ut_a(!is_long);
 
247
 
 
248
                        len++;
 
249
 
 
250
                        if (buf) {
 
251
                                *buf++ = '%';
 
252
                        }
 
253
 
 
254
                        break;
 
255
 
 
256
                default:
 
257
                        ut_error;
 
258
                }
 
259
        }
 
260
 
 
261
        /* For the NUL character. */
 
262
        len++;
 
263
 
 
264
        if (buf) {
 
265
                *buf = '\0';
 
266
        }
 
267
 
 
268
        return(len);
 
269
}
 
270
 
 
271
/********************************************************************
 
272
A simple (s)printf replacement that dynamically allocates the space for the
 
273
formatted string from the given heap. This supports a very limited set of
 
274
the printf syntax: types 's' and 'u' and length modifier 'l' (which is
 
275
required for the 'u' type). */
 
276
UNIV_INTERN
 
277
char*
 
278
mem_heap_printf(
 
279
/*============*/
 
280
                                /* out: heap-allocated formatted string */
 
281
        mem_heap_t*     heap,   /* in: memory heap */
 
282
        const char*     format, /* in: format string */
 
283
        ...)
 
284
{
 
285
        va_list         ap;
 
286
        char*           str;
 
287
        ulint           len;
 
288
 
 
289
        /* Calculate length of string */
 
290
        len = 0;
 
291
        va_start(ap, format);
 
292
        len = mem_heap_printf_low(NULL, format, ap);
 
293
        va_end(ap);
 
294
 
 
295
        /* Now create it for real. */
 
296
        str = mem_heap_alloc(heap, len);
 
297
        va_start(ap, format);
 
298
        mem_heap_printf_low(str, format, ap);
 
299
        va_end(ap);
 
300
 
 
301
        return(str);
 
302
}
 
303
 
 
304
/*******************************************************************
 
305
Creates a memory heap block where data can be allocated. */
 
306
UNIV_INTERN
 
307
mem_block_t*
 
308
mem_heap_create_block(
 
309
/*==================*/
 
310
                                /* out, own: memory heap block, NULL if
 
311
                                did not succeed (only possible for
 
312
                                MEM_HEAP_BTR_SEARCH type heaps) */
 
313
        mem_heap_t*     heap,   /* in: memory heap or NULL if first block
 
314
                                should be created */
 
315
        ulint           n,      /* in: number of bytes needed for user data */
 
316
        ulint           type,   /* in: type of heap: MEM_HEAP_DYNAMIC or
 
317
                                MEM_HEAP_BUFFER */
 
318
        const char*     file_name,/* in: file name where created */
 
319
        ulint           line)   /* in: line where created */
 
320
{
 
321
        buf_block_t*    buf_block = NULL;
 
322
        mem_block_t*    block;
 
323
        ulint           len;
 
324
 
 
325
        ut_ad((type == MEM_HEAP_DYNAMIC) || (type == MEM_HEAP_BUFFER)
 
326
              || (type == MEM_HEAP_BUFFER + MEM_HEAP_BTR_SEARCH));
 
327
 
 
328
        if (heap && heap->magic_n != MEM_BLOCK_MAGIC_N) {
 
329
                mem_analyze_corruption(heap);
 
330
        }
 
331
 
 
332
        /* In dynamic allocation, calculate the size: block header + data. */
 
333
 
 
334
        if (type == MEM_HEAP_DYNAMIC) {
 
335
 
 
336
                len = MEM_BLOCK_HEADER_SIZE + MEM_SPACE_NEEDED(n);
 
337
                block = mem_area_alloc(&len, mem_comm_pool);
 
338
        } else {
 
339
                ut_ad(n <= MEM_MAX_ALLOC_IN_BUF);
 
340
 
 
341
                len = MEM_BLOCK_HEADER_SIZE + MEM_SPACE_NEEDED(n);
 
342
 
 
343
                if (len < UNIV_PAGE_SIZE / 2) {
 
344
 
 
345
                        block = mem_area_alloc(&len, mem_comm_pool);
 
346
                } else {
 
347
                        len = UNIV_PAGE_SIZE;
 
348
 
 
349
                        if ((type & MEM_HEAP_BTR_SEARCH) && heap) {
 
350
                                /* We cannot allocate the block from the
 
351
                                buffer pool, but must get the free block from
 
352
                                the heap header free block field */
 
353
 
 
354
                                buf_block = heap->free_block;
 
355
                                heap->free_block = NULL;
 
356
 
 
357
                                if (UNIV_UNLIKELY(!buf_block)) {
 
358
 
 
359
                                        return(NULL);
 
360
                                }
 
361
                        } else {
 
362
                                buf_block = buf_block_alloc(0);
 
363
                        }
 
364
 
 
365
                        block = (mem_block_t*) buf_block->frame;
 
366
                }
 
367
        }
 
368
 
 
369
        ut_ad(block);
 
370
        block->buf_block = buf_block;
 
371
        block->magic_n = MEM_BLOCK_MAGIC_N;
 
372
        ut_strlcpy_rev(block->file_name, file_name, sizeof(block->file_name));
 
373
        block->line = line;
 
374
 
 
375
#ifdef MEM_PERIODIC_CHECK
 
376
        mem_pool_mutex_enter();
 
377
 
 
378
        if (!mem_block_list_inited) {
 
379
                mem_block_list_inited = TRUE;
 
380
                UT_LIST_INIT(mem_block_list);
 
381
        }
 
382
 
 
383
        UT_LIST_ADD_LAST(mem_block_list, mem_block_list, block);
 
384
 
 
385
        mem_pool_mutex_exit();
 
386
#endif
 
387
        mem_block_set_len(block, len);
 
388
        mem_block_set_type(block, type);
 
389
        mem_block_set_free(block, MEM_BLOCK_HEADER_SIZE);
 
390
        mem_block_set_start(block, MEM_BLOCK_HEADER_SIZE);
 
391
 
 
392
        block->free_block = NULL;
 
393
 
 
394
        ut_ad((ulint)MEM_BLOCK_HEADER_SIZE < len);
 
395
 
 
396
        return(block);
 
397
}
 
398
 
 
399
/*******************************************************************
 
400
Adds a new block to a memory heap. */
 
401
UNIV_INTERN
 
402
mem_block_t*
 
403
mem_heap_add_block(
 
404
/*===============*/
 
405
                                /* out: created block, NULL if did not
 
406
                                succeed (only possible for
 
407
                                MEM_HEAP_BTR_SEARCH type heaps)*/
 
408
        mem_heap_t*     heap,   /* in: memory heap */
 
409
        ulint           n)      /* in: number of bytes user needs */
 
410
{
 
411
        mem_block_t*    block;
 
412
        mem_block_t*    new_block;
 
413
        ulint           new_size;
 
414
 
 
415
        ut_ad(mem_heap_check(heap));
 
416
 
 
417
        block = UT_LIST_GET_LAST(heap->base);
 
418
 
 
419
        /* We have to allocate a new block. The size is always at least
 
420
        doubled until the standard size is reached. After that the size
 
421
        stays the same, except in cases where the caller needs more space. */
 
422
 
 
423
        new_size = 2 * mem_block_get_len(block);
 
424
 
 
425
        if (heap->type != MEM_HEAP_DYNAMIC) {
 
426
                /* From the buffer pool we allocate buffer frames */
 
427
                ut_a(n <= MEM_MAX_ALLOC_IN_BUF);
 
428
 
 
429
                if (new_size > MEM_MAX_ALLOC_IN_BUF) {
 
430
                        new_size = MEM_MAX_ALLOC_IN_BUF;
 
431
                }
 
432
        } else if (new_size > MEM_BLOCK_STANDARD_SIZE) {
 
433
 
 
434
                new_size = MEM_BLOCK_STANDARD_SIZE;
 
435
        }
 
436
 
 
437
        if (new_size < n) {
 
438
                new_size = n;
 
439
        }
 
440
 
 
441
        new_block = mem_heap_create_block(heap, new_size, heap->type,
 
442
                                          heap->file_name, heap->line);
 
443
        if (new_block == NULL) {
 
444
 
 
445
                return(NULL);
 
446
        }
 
447
 
 
448
        /* Add the new block as the last block */
 
449
 
 
450
        UT_LIST_INSERT_AFTER(list, heap->base, block, new_block);
 
451
 
 
452
        return(new_block);
 
453
}
 
454
 
 
455
/**********************************************************************
 
456
Frees a block from a memory heap. */
 
457
UNIV_INTERN
 
458
void
 
459
mem_heap_block_free(
 
460
/*================*/
 
461
        mem_heap_t*     heap,   /* in: heap */
 
462
        mem_block_t*    block)  /* in: block to free */
 
463
{
 
464
        ulint           type;
 
465
        ulint           len;
 
466
        buf_block_t*    buf_block;
 
467
 
 
468
        if (block->magic_n != MEM_BLOCK_MAGIC_N) {
 
469
                mem_analyze_corruption(block);
 
470
        }
 
471
 
 
472
        UT_LIST_REMOVE(list, heap->base, block);
 
473
 
 
474
#ifdef MEM_PERIODIC_CHECK
 
475
        mem_pool_mutex_enter();
 
476
 
 
477
        UT_LIST_REMOVE(mem_block_list, mem_block_list, block);
 
478
 
 
479
        mem_pool_mutex_exit();
 
480
#endif
 
481
        type = heap->type;
 
482
        len = block->len;
 
483
        buf_block = block->buf_block;
 
484
        block->magic_n = MEM_FREED_BLOCK_MAGIC_N;
 
485
 
 
486
#ifdef UNIV_MEM_DEBUG
 
487
        /* In the debug version we set the memory to a random combination
 
488
        of hex 0xDE and 0xAD. */
 
489
 
 
490
        mem_erase_buf((byte*)block, len);
 
491
#else /* UNIV_MEM_DEBUG */
 
492
        UNIV_MEM_ASSERT_AND_FREE(block, len);
 
493
#endif /* UNIV_MEM_DEBUG */
 
494
 
 
495
        if (type == MEM_HEAP_DYNAMIC) {
 
496
 
 
497
                ut_ad(!buf_block);
 
498
                mem_area_free(block, mem_comm_pool);
 
499
        } else {
 
500
                ut_ad(type & MEM_HEAP_BUFFER);
 
501
 
 
502
                if (len >= UNIV_PAGE_SIZE / 2) {
 
503
                        buf_block_free(buf_block);
 
504
                } else {
 
505
                        ut_ad(!buf_block);
 
506
                        mem_area_free(block, mem_comm_pool);
 
507
                }
 
508
        }
 
509
}
 
510
 
 
511
/**********************************************************************
 
512
Frees the free_block field from a memory heap. */
 
513
UNIV_INTERN
 
514
void
 
515
mem_heap_free_block_free(
 
516
/*=====================*/
 
517
        mem_heap_t*     heap)   /* in: heap */
 
518
{
 
519
        if (UNIV_LIKELY_NULL(heap->free_block)) {
 
520
 
 
521
                buf_block_free(heap->free_block);
 
522
 
 
523
                heap->free_block = NULL;
 
524
        }
 
525
}
 
526
 
 
527
#ifdef MEM_PERIODIC_CHECK
 
528
/**********************************************************************
 
529
Goes through the list of all allocated mem blocks, checks their magic
 
530
numbers, and reports possible corruption. */
 
531
UNIV_INTERN
 
532
void
 
533
mem_validate_all_blocks(void)
 
534
/*=========================*/
 
535
{
 
536
        mem_block_t*    block;
 
537
 
 
538
        mem_pool_mutex_enter();
 
539
 
 
540
        block = UT_LIST_GET_FIRST(mem_block_list);
 
541
 
 
542
        while (block) {
 
543
                if (block->magic_n != MEM_BLOCK_MAGIC_N) {
 
544
                        mem_analyze_corruption(block);
 
545
                }
 
546
 
 
547
                block = UT_LIST_GET_NEXT(mem_block_list, block);
 
548
        }
 
549
 
 
550
        mem_pool_mutex_exit();
 
551
}
 
552
#endif