← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

  • Committer: Brian Aker
  • Date: 2009-05-11 17:50:22 UTC
  • Revision ID: brian@gaz-20090511175022-y35q9ky6uh9ldcjt
Replacing Sun employee copyright headers (aka... anything done by a Sun
employee is copyright by Sun).

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
 
NOTE: Use the corresponding macro instead of this function.
89
 
Allocates a single buffer of memory from the dynamic memory of
90
 
the C compiler. Is like malloc of C. The buffer must be freed
91
 
with mem_free. */
92
 
 
93
 
void*
94
 
mem_alloc_func_noninline(
95
 
/*=====================*/
96
 
                                        /* out, own: free storage */
97
 
        ulint           n,              /* in: desired number of bytes */
98
 
        const char*     file_name,      /* in: file name where created */
99
 
        ulint           line)           /* in: line where created */
100
 
{
101
 
        return(mem_alloc_func(n, file_name, line));
102
 
}
103
 
 
104
 
/**************************************************************************
105
 
Duplicates a NUL-terminated string, allocated from a memory heap. */
106
 
 
107
 
char*
108
 
mem_heap_strdup(
109
 
/*============*/
110
 
                                /* out, own: a copy of the string */
111
 
        mem_heap_t*     heap,   /* in: memory heap where string is allocated */
112
 
        const char*     str)    /* in: string to be copied */
113
 
{
114
 
        return(mem_heap_dup(heap, str, strlen(str) + 1));
115
 
}
116
 
 
117
 
/**************************************************************************
118
 
Duplicate a block of data, allocated from a memory heap. */
119
 
 
120
 
void*
121
 
mem_heap_dup(
122
 
/*=========*/
123
 
                                /* out, own: a copy of the data */
124
 
        mem_heap_t*     heap,   /* in: memory heap where copy is allocated */
125
 
        const void*     data,   /* in: data to be copied */
126
 
        ulint           len)    /* in: length of data, in bytes */
127
 
{
128
 
        return(memcpy(mem_heap_alloc(heap, len), data, len));
129
 
}
130
 
 
131
 
/**************************************************************************
132
 
Concatenate two memory blocks and return the result, using a memory heap. */
133
 
 
134
 
void*
135
 
mem_heap_cat(
136
 
/*=========*/
137
 
                                /* out, own: the result */
138
 
        mem_heap_t*     heap,   /* in: memory heap where result is allocated */
139
 
        const void*     b1,     /* in: block 1 */
140
 
        ulint           len1,   /* in: length of b1, in bytes */
141
 
        const void*     b2,     /* in: block 2 */
142
 
        ulint           len2)   /* in: length of b2, in bytes */
143
 
{
144
 
        void*   res = mem_heap_alloc(heap, len1 + len2);
145
 
 
146
 
        memcpy(res, b1, len1);
147
 
        memcpy((char*)res + len1, b2, len2);
148
 
 
149
 
        return(res);
150
 
}
151
 
 
152
 
/**************************************************************************
153
 
Concatenate two strings and return the result, using a memory heap. */
154
 
 
155
 
char*
156
 
mem_heap_strcat(
157
 
/*============*/
158
 
                                /* out, own: the result */
159
 
        mem_heap_t*     heap,   /* in: memory heap where string is allocated */
160
 
        const char*     s1,     /* in: string 1 */
161
 
        const char*     s2)     /* in: string 2 */
162
 
{
163
 
        char*   s;
164
 
        ulint   s1_len = strlen(s1);
165
 
        ulint   s2_len = strlen(s2);
166
 
 
167
 
        s = mem_heap_alloc(heap, s1_len + s2_len + 1);
168
 
 
169
 
        memcpy(s, s1, s1_len);
170
 
        memcpy(s + s1_len, s2, s2_len);
171
 
 
172
 
        s[s1_len + s2_len] = '\0';
173
 
 
174
 
        return(s);
175
 
}
176
 
 
177
 
 
178
 
/********************************************************************
179
 
Helper function for mem_heap_printf. */
180
 
static
181
 
ulint
182
 
mem_heap_printf_low(
183
 
/*================*/
184
 
                                /* out: length of formatted string,
185
 
                                including terminating NUL */
186
 
        char*           buf,    /* in/out: buffer to store formatted string
187
 
                                in, or NULL to just calculate length */
188
 
        const char*     format, /* in: format string */
189
 
        va_list         ap)     /* in: arguments */
190
 
{
191
 
        ulint           len = 0;
192
 
 
193
 
        while (*format) {
194
 
 
195
 
                /* Does this format specifier have the 'l' length modifier. */
196
 
                ibool   is_long = FALSE;
197
 
 
198
 
                /* Length of one parameter. */
199
 
                size_t  plen;
200
 
 
201
 
                if (*format++ != '%') {
202
 
                        /* Non-format character. */
203
 
 
204
 
                        len++;
205
 
 
206
 
                        if (buf) {
207
 
                                *buf++ = *(format - 1);
208
 
                        }
209
 
 
210
 
                        continue;
211
 
                }
212
 
 
213
 
                if (*format == 'l') {
214
 
                        is_long = TRUE;
215
 
                        format++;
216
 
                }
217
 
 
218
 
                switch (*format++) {
219
 
                case 's':
220
 
                        /* string */
221
 
                        {
222
 
                                char*   s = va_arg(ap, char*);
223
 
 
224
 
                                /* "%ls" is a non-sensical format specifier. */
225
 
                                ut_a(!is_long);
226
 
 
227
 
                                plen = strlen(s);
228
 
                                len += plen;
229
 
 
230
 
                                if (buf) {
231
 
                                        memcpy(buf, s, plen);
232
 
                                        buf += plen;
233
 
                                }
234
 
                        }
235
 
 
236
 
                        break;
237
 
 
238
 
                case 'u':
239
 
                        /* unsigned int */
240
 
                        {
241
 
                                char            tmp[32];
242
 
                                unsigned long   val;
243
 
 
244
 
                                /* We only support 'long' values for now. */
245
 
                                ut_a(is_long);
246
 
 
247
 
                                val = va_arg(ap, unsigned long);
248
 
 
249
 
                                plen = sprintf(tmp, "%lu", val);
250
 
                                len += plen;
251
 
 
252
 
                                if (buf) {
253
 
                                        memcpy(buf, tmp, plen);
254
 
                                        buf += plen;
255
 
                                }
256
 
                        }
257
 
 
258
 
                        break;
259
 
 
260
 
                case '%':
261
 
 
262
 
                        /* "%l%" is a non-sensical format specifier. */
263
 
                        ut_a(!is_long);
264
 
 
265
 
                        len++;
266
 
 
267
 
                        if (buf) {
268
 
                                *buf++ = '%';
269
 
                        }
270
 
 
271
 
                        break;
272
 
 
273
 
                default:
274
 
                        ut_error;
275
 
                }
276
 
        }
277
 
 
278
 
        /* For the NUL character. */
279
 
        len++;
280
 
 
281
 
        if (buf) {
282
 
                *buf = '\0';
283
 
        }
284
 
 
285
 
        return(len);
286
 
}
287
 
 
288
 
/********************************************************************
289
 
A simple (s)printf replacement that dynamically allocates the space for the
290
 
formatted string from the given heap. This supports a very limited set of
291
 
the printf syntax: types 's' and 'u' and length modifier 'l' (which is
292
 
required for the 'u' type). */
293
 
 
294
 
char*
295
 
mem_heap_printf(
296
 
/*============*/
297
 
                                /* out: heap-allocated formatted string */
298
 
        mem_heap_t*     heap,   /* in: memory heap */
299
 
        const char*     format, /* in: format string */
300
 
        ...)
301
 
{
302
 
        va_list         ap;
303
 
        char*           str;
304
 
        ulint           len;
305
 
 
306
 
        /* Calculate length of string */
307
 
        len = 0;
308
 
        va_start(ap, format);
309
 
        len = mem_heap_printf_low(NULL, format, ap);
310
 
        va_end(ap);
311
 
 
312
 
        /* Now create it for real. */
313
 
        str = mem_heap_alloc(heap, len);
314
 
        va_start(ap, format);
315
 
        mem_heap_printf_low(str, format, ap);
316
 
        va_end(ap);
317
 
 
318
 
        return(str);
319
 
}
320
 
 
321
 
/*******************************************************************
322
 
Creates a memory heap block where data can be allocated. */
323
 
 
324
 
mem_block_t*
325
 
mem_heap_create_block(
326
 
/*==================*/
327
 
                                /* out, own: memory heap block, NULL if
328
 
                                did not succeed (only possible for
329
 
                                MEM_HEAP_BTR_SEARCH type heaps) */
330
 
        mem_heap_t*     heap,   /* in: memory heap or NULL if first block
331
 
                                should be created */
332
 
        ulint           n,      /* in: number of bytes needed for user data, or
333
 
                                if init_block is not NULL, its size in bytes */
334
 
        void*           init_block, /* in: init block in fast create,
335
 
                                type must be MEM_HEAP_DYNAMIC */
336
 
        ulint           type,   /* in: type of heap: MEM_HEAP_DYNAMIC or
337
 
                                MEM_HEAP_BUFFER */
338
 
        const char*     file_name,/* in: file name where created */
339
 
        ulint           line)   /* in: line where created */
340
 
{
341
 
        mem_block_t*    block;
342
 
        ulint           len;
343
 
 
344
 
        ut_ad((type == MEM_HEAP_DYNAMIC) || (type == MEM_HEAP_BUFFER)
345
 
              || (type == MEM_HEAP_BUFFER + MEM_HEAP_BTR_SEARCH));
346
 
 
347
 
        if (heap && heap->magic_n != MEM_BLOCK_MAGIC_N) {
348
 
                mem_analyze_corruption(heap);
349
 
        }
350
 
 
351
 
        /* In dynamic allocation, calculate the size: block header + data. */
352
 
 
353
 
        if (init_block != NULL) {
354
 
                ut_ad(type == MEM_HEAP_DYNAMIC);
355
 
                ut_ad(n > MEM_BLOCK_START_SIZE + MEM_BLOCK_HEADER_SIZE);
356
 
                len = n;
357
 
                block = init_block;
358
 
 
359
 
        } else if (type == MEM_HEAP_DYNAMIC) {
360
 
 
361
 
                len = MEM_BLOCK_HEADER_SIZE + MEM_SPACE_NEEDED(n);
362
 
                block = mem_area_alloc(len, mem_comm_pool);
363
 
        } else {
364
 
                ut_ad(n <= MEM_MAX_ALLOC_IN_BUF);
365
 
 
366
 
                len = MEM_BLOCK_HEADER_SIZE + MEM_SPACE_NEEDED(n);
367
 
 
368
 
                if (len < UNIV_PAGE_SIZE / 2) {
369
 
 
370
 
                        block = mem_area_alloc(len, mem_comm_pool);
371
 
                } else {
372
 
                        len = UNIV_PAGE_SIZE;
373
 
 
374
 
                        if ((type & MEM_HEAP_BTR_SEARCH) && heap) {
375
 
                                /* We cannot allocate the block from the
376
 
                                buffer pool, but must get the free block from
377
 
                                the heap header free block field */
378
 
 
379
 
                                block = (mem_block_t*)heap->free_block;
380
 
                                heap->free_block = NULL;
381
 
                        } else {
382
 
                                block = (mem_block_t*)buf_frame_alloc();
383
 
                        }
384
 
                }
385
 
        }
386
 
 
387
 
        if (block == NULL) {
388
 
                /* Only MEM_HEAP_BTR_SEARCH allocation should ever fail. */
389
 
                ut_a(type & MEM_HEAP_BTR_SEARCH);
390
 
 
391
 
                return(NULL);
392
 
        }
393
 
 
394
 
        block->magic_n = MEM_BLOCK_MAGIC_N;
395
 
        ut_strlcpy_rev(block->file_name, file_name, sizeof(block->file_name));
396
 
        block->line = line;
397
 
 
398
 
#ifdef MEM_PERIODIC_CHECK
399
 
        mem_pool_mutex_enter();
400
 
 
401
 
        if (!mem_block_list_inited) {
402
 
                mem_block_list_inited = TRUE;
403
 
                UT_LIST_INIT(mem_block_list);
404
 
        }
405
 
 
406
 
        UT_LIST_ADD_LAST(mem_block_list, mem_block_list, block);
407
 
 
408
 
        mem_pool_mutex_exit();
409
 
#endif
410
 
        mem_block_set_len(block, len);
411
 
        mem_block_set_type(block, type);
412
 
        mem_block_set_free(block, MEM_BLOCK_HEADER_SIZE);
413
 
        mem_block_set_start(block, MEM_BLOCK_HEADER_SIZE);
414
 
 
415
 
        block->free_block = NULL;
416
 
        block->init_block = (init_block != NULL);
417
 
 
418
 
        ut_ad((ulint)MEM_BLOCK_HEADER_SIZE < len);
419
 
 
420
 
        return(block);
421
 
}
422
 
 
423
 
/*******************************************************************
424
 
Adds a new block to a memory heap. */
425
 
 
426
 
mem_block_t*
427
 
mem_heap_add_block(
428
 
/*===============*/
429
 
                                /* out: created block, NULL if did not
430
 
                                succeed (only possible for
431
 
                                MEM_HEAP_BTR_SEARCH type heaps)*/
432
 
        mem_heap_t*     heap,   /* in: memory heap */
433
 
        ulint           n)      /* in: number of bytes user needs */
434
 
{
435
 
        mem_block_t*    block;
436
 
        mem_block_t*    new_block;
437
 
        ulint           new_size;
438
 
 
439
 
        ut_ad(mem_heap_check(heap));
440
 
 
441
 
        block = UT_LIST_GET_LAST(heap->base);
442
 
 
443
 
        /* We have to allocate a new block. The size is always at least
444
 
        doubled until the standard size is reached. After that the size
445
 
        stays the same, except in cases where the caller needs more space. */
446
 
 
447
 
        new_size = 2 * mem_block_get_len(block);
448
 
 
449
 
        if (heap->type != MEM_HEAP_DYNAMIC) {
450
 
                /* From the buffer pool we allocate buffer frames */
451
 
                ut_a(n <= MEM_MAX_ALLOC_IN_BUF);
452
 
 
453
 
                if (new_size > MEM_MAX_ALLOC_IN_BUF) {
454
 
                        new_size = MEM_MAX_ALLOC_IN_BUF;
455
 
                }
456
 
        } else if (new_size > MEM_BLOCK_STANDARD_SIZE) {
457
 
 
458
 
                new_size = MEM_BLOCK_STANDARD_SIZE;
459
 
        }
460
 
 
461
 
        if (new_size < n) {
462
 
                new_size = n;
463
 
        }
464
 
 
465
 
        new_block = mem_heap_create_block(heap, new_size, NULL, heap->type,
466
 
                                          heap->file_name, heap->line);
467
 
        if (new_block == NULL) {
468
 
 
469
 
                return(NULL);
470
 
        }
471
 
 
472
 
        /* Add the new block as the last block */
473
 
 
474
 
        UT_LIST_INSERT_AFTER(list, heap->base, block, new_block);
475
 
 
476
 
        return(new_block);
477
 
}
478
 
 
479
 
/**********************************************************************
480
 
Frees a block from a memory heap. */
481
 
 
482
 
void
483
 
mem_heap_block_free(
484
 
/*================*/
485
 
        mem_heap_t*     heap,   /* in: heap */
486
 
        mem_block_t*    block)  /* in: block to free */
487
 
{
488
 
        ulint   type;
489
 
        ulint   len;
490
 
        ibool   init_block;
491
 
 
492
 
        if (block->magic_n != MEM_BLOCK_MAGIC_N) {
493
 
                mem_analyze_corruption(block);
494
 
        }
495
 
 
496
 
        UT_LIST_REMOVE(list, heap->base, block);
497
 
 
498
 
#ifdef MEM_PERIODIC_CHECK
499
 
        mem_pool_mutex_enter();
500
 
 
501
 
        UT_LIST_REMOVE(mem_block_list, mem_block_list, block);
502
 
 
503
 
        mem_pool_mutex_exit();
504
 
#endif
505
 
        type = heap->type;
506
 
        len = block->len;
507
 
        init_block = block->init_block;
508
 
        block->magic_n = MEM_FREED_BLOCK_MAGIC_N;
509
 
 
510
 
#ifdef UNIV_MEM_DEBUG
511
 
        /* In the debug version we set the memory to a random combination
512
 
        of hex 0xDE and 0xAD. */
513
 
 
514
 
        mem_erase_buf((byte*)block, len);
515
 
#else /* UNIV_MEM_DEBUG */
516
 
        UNIV_MEM_ASSERT_AND_FREE(block, len);
517
 
#endif /* UNIV_MEM_DEBUG */
518
 
 
519
 
        if (init_block) {
520
 
                /* Do not have to free: do nothing */
521
 
 
522
 
        } else if (type == MEM_HEAP_DYNAMIC) {
523
 
 
524
 
                mem_area_free(block, mem_comm_pool);
525
 
        } else {
526
 
                ut_ad(type & MEM_HEAP_BUFFER);
527
 
 
528
 
                if (len >= UNIV_PAGE_SIZE / 2) {
529
 
                        buf_frame_free((byte*)block);
530
 
                } else {
531
 
                        mem_area_free(block, mem_comm_pool);
532
 
                }
533
 
        }
534
 
}
535
 
 
536
 
/**********************************************************************
537
 
Frees the free_block field from a memory heap. */
538
 
 
539
 
void
540
 
mem_heap_free_block_free(
541
 
/*=====================*/
542
 
        mem_heap_t*     heap)   /* in: heap */
543
 
{
544
 
        if (heap->free_block) {
545
 
 
546
 
                buf_frame_free(heap->free_block);
547
 
 
548
 
                heap->free_block = NULL;
549
 
        }
550
 
}
551
 
 
552
 
#ifdef MEM_PERIODIC_CHECK
553
 
/**********************************************************************
554
 
Goes through the list of all allocated mem blocks, checks their magic
555
 
numbers, and reports possible corruption. */
556
 
 
557
 
void
558
 
mem_validate_all_blocks(void)
559
 
/*=========================*/
560
 
{
561
 
        mem_block_t*    block;
562
 
 
563
 
        mem_pool_mutex_enter();
564
 
 
565
 
        block = UT_LIST_GET_FIRST(mem_block_list);
566
 
 
567
 
        while (block) {
568
 
                if (block->magic_n != MEM_BLOCK_MAGIC_N) {
569
 
                        mem_analyze_corruption(block);
570
 
                }
571
 
 
572
 
                block = UT_LIST_GET_NEXT(mem_block_list, block);
573
 
        }
574
 
 
575
 
        mem_pool_mutex_exit();
576
 
}
577
 
#endif