1
/******************************************************
2
The database buffer replacement algorithm
6
Created 11/5/1995 Heikki Tuuri
7
*******************************************************/
18
#include "sync0sync.h"
20
#include "hash0hash.h"
30
/* The number of blocks from the LRU_old pointer onward, including the block
31
pointed to, must be 3/8 of the whole LRU list length, except that the
32
tolerance defined below is allowed. Note that the tolerance must be small
33
enough such that for even the BUF_LRU_OLD_MIN_LEN long LRU list, the
34
LRU_old pointer is not allowed to point to either end of the LRU list. */
36
#define BUF_LRU_OLD_TOLERANCE 20
38
/* The whole LRU list length is divided by this number to determine an
39
initial segment in buf_LRU_get_recent_limit */
41
#define BUF_LRU_INITIAL_RATIO 8
43
/**********************************************************************
44
Takes a block out of the LRU list and page hash table and sets the block
45
state to BUF_BLOCK_REMOVE_HASH. */
48
buf_LRU_block_remove_hashed_page(
49
/*=============================*/
50
buf_block_t* block); /* in: block, must contain a file page and
51
be in a state where it can be freed; there
52
may or may not be a hash index to the page */
53
/**********************************************************************
54
Puts a file page whose has no hash index to the free list. */
57
buf_LRU_block_free_hashed_page(
58
/*===========================*/
59
buf_block_t* block); /* in: block, must contain a file page and
60
be in a state where it can be freed */
62
/**********************************************************************
63
Gets the minimum LRU_position field for the blocks in an initial segment
64
(determined by BUF_LRU_INITIAL_RATIO) of the LRU list. The limit is not
65
guaranteed to be precise, because the ulint_clock may wrap around. */
68
buf_LRU_get_recent_limit(void)
69
/*==========================*/
70
/* out: the limit; zero if could not determine it */
76
mutex_enter(&(buf_pool->mutex));
78
len = UT_LIST_GET_LEN(buf_pool->LRU);
80
if (len < BUF_LRU_OLD_MIN_LEN) {
81
/* The LRU list is too short to do read-ahead */
83
mutex_exit(&(buf_pool->mutex));
88
block = UT_LIST_GET_FIRST(buf_pool->LRU);
90
limit = block->LRU_position - len / BUF_LRU_INITIAL_RATIO;
92
mutex_exit(&(buf_pool->mutex));
97
/**********************************************************************
98
Look for a replaceable block from the end of the LRU list and put it to
99
the free list if found. */
102
buf_LRU_search_and_free_block(
103
/*==========================*/
104
/* out: TRUE if freed */
105
ulint n_iterations) /* in: how many times this has been called
106
repeatedly without result: a high value
107
means that we should search farther */
114
mutex_enter(&(buf_pool->mutex));
118
distance = BUF_LRU_FREE_SEARCH_LEN * (1 + n_iterations / 5);
121
block = UT_LIST_GET_LAST(buf_pool->LRU);
123
while (i < distance && block != NULL) {
125
if (buf_flush_ready_for_replace(block)) {
127
if (buf_debug_prints) {
129
"Putting space %lu page %lu to free list\n",
130
block->space, block->offset);
133
buf_LRU_block_remove_hashed_page(block);
135
mutex_exit(&(buf_pool->mutex));
137
btr_search_drop_page_hash_index(block->frame);
139
mutex_enter(&(buf_pool->mutex));
141
buf_LRU_block_free_hashed_page(block);
148
block = UT_LIST_GET_PREV(LRU, block);
151
if (buf_pool->LRU_flush_ended > 0) {
152
buf_pool->LRU_flush_ended--;
156
buf_pool->LRU_flush_ended = 0;
159
mutex_exit(&(buf_pool->mutex));
164
/**********************************************************************
165
Tries to remove LRU flushed blocks from the end of the LRU list and put them
166
to the free list. This is beneficial for the efficiency of the insert buffer
167
operation, as flushed pages from non-unique non-clustered indexes are here
168
taken out of the buffer pool, and their inserts redirected to the insert
169
buffer. Otherwise, the flushed blocks could get modified again before read
170
operations need new buffer blocks, and the i/o work done in flushing would be
174
buf_LRU_try_free_flushed_blocks(void)
175
/*=================================*/
177
mutex_enter(&(buf_pool->mutex));
179
while (buf_pool->LRU_flush_ended > 0) {
181
mutex_exit(&(buf_pool->mutex));
183
buf_LRU_search_and_free_block(0);
185
mutex_enter(&(buf_pool->mutex));
188
mutex_exit(&(buf_pool->mutex));
191
/**********************************************************************
192
Returns a free block from buf_pool. The block is taken off the free list.
193
If it is empty, blocks are moved from the end of the LRU list to the free
197
buf_LRU_get_free_block(void)
198
/*========================*/
199
/* out: the free control block */
201
buf_block_t* block = NULL;
203
ulint n_iterations = 0;
205
mutex_enter(&(buf_pool->mutex));
207
if (buf_pool->LRU_flush_ended > 0) {
208
mutex_exit(&(buf_pool->mutex));
210
buf_LRU_try_free_flushed_blocks();
212
mutex_enter(&(buf_pool->mutex));
215
/* If there is a block in the free list, take it */
216
if (UT_LIST_GET_LEN(buf_pool->free) > 0) {
218
block = UT_LIST_GET_FIRST(buf_pool->free);
219
UT_LIST_REMOVE(free, buf_pool->free, block);
220
block->state = BUF_BLOCK_READY_FOR_USE;
222
mutex_exit(&(buf_pool->mutex));
227
/* If no block was in the free list, search from the end of the LRU
228
list and try to free a block there */
230
mutex_exit(&(buf_pool->mutex));
232
freed = buf_LRU_search_and_free_block(n_iterations);
238
/* No free block was found near the end of the list: try to flush
241
buf_flush_free_margin();
243
os_event_wait(buf_pool->no_flush[BUF_FLUSH_LRU]);
247
os_aio_simulated_wake_handler_threads();
249
if (n_iterations > 10) {
251
os_thread_sleep(500000);
254
if (n_iterations > 20) {
257
rw_lock_list_print_info();
259
if (n_iterations > 30) {
261
"Innobase: Warning: difficult to find free blocks from\n"
262
"Innobase: the buffer pool! Consider increasing the\n"
263
"Innobase: buffer pool size.\n");
270
/***********************************************************************
271
Moves the LRU_old pointer so that the length of the old blocks list
272
is inside the allowed limits. */
275
buf_LRU_old_adjust_len(void)
276
/*========================*/
281
ut_ad(buf_pool->LRU_old);
282
ut_ad(mutex_own(&(buf_pool->mutex)));
283
ut_ad(3 * (BUF_LRU_OLD_MIN_LEN / 8) > BUF_LRU_OLD_TOLERANCE + 5);
286
old_len = buf_pool->LRU_old_len;
287
new_len = 3 * (UT_LIST_GET_LEN(buf_pool->LRU) / 8);
289
/* Update the LRU_old pointer if necessary */
291
if (old_len < new_len - BUF_LRU_OLD_TOLERANCE) {
293
buf_pool->LRU_old = UT_LIST_GET_PREV(LRU,
295
(buf_pool->LRU_old)->old = TRUE;
296
buf_pool->LRU_old_len++;
298
} else if (old_len > new_len + BUF_LRU_OLD_TOLERANCE) {
300
(buf_pool->LRU_old)->old = FALSE;
301
buf_pool->LRU_old = UT_LIST_GET_NEXT(LRU,
303
buf_pool->LRU_old_len--;
305
ut_ad(buf_pool->LRU_old); /* Check that we did not
306
fall out of the LRU list */
312
/***********************************************************************
313
Initializes the old blocks pointer in the LRU list.
314
This function should be called when the LRU list grows to
315
BUF_LRU_OLD_MIN_LEN length. */
318
buf_LRU_old_init(void)
319
/*==================*/
323
ut_ad(UT_LIST_GET_LEN(buf_pool->LRU) == BUF_LRU_OLD_MIN_LEN);
325
/* We first initialize all blocks in the LRU list as old and then use
326
the adjust function to move the LRU_old pointer to the right
329
block = UT_LIST_GET_FIRST(buf_pool->LRU);
331
while (block != NULL) {
333
block = UT_LIST_GET_NEXT(LRU, block);
336
buf_pool->LRU_old = UT_LIST_GET_FIRST(buf_pool->LRU);
337
buf_pool->LRU_old_len = UT_LIST_GET_LEN(buf_pool->LRU);
339
buf_LRU_old_adjust_len();
342
/**********************************************************************
343
Removes a block from the LRU list. */
346
buf_LRU_remove_block(
347
/*=================*/
348
buf_block_t* block) /* in: control block */
352
ut_ad(mutex_own(&(buf_pool->mutex)));
354
/* If the LRU_old pointer is defined and points to just this block,
355
move it backward one step */
357
if (block == buf_pool->LRU_old) {
359
/* Below: the previous block is guaranteed to exist, because
360
the LRU_old pointer is only allowed to differ by the
361
tolerance value from strict 3/8 of the LRU list length. */
363
buf_pool->LRU_old = UT_LIST_GET_PREV(LRU, block);
364
(buf_pool->LRU_old)->old = TRUE;
366
buf_pool->LRU_old_len++;
367
ut_ad(buf_pool->LRU_old);
370
/* Remove the block from the LRU list */
371
UT_LIST_REMOVE(LRU, buf_pool->LRU, block);
373
/* If the LRU list is so short that LRU_old not defined, return */
374
if (UT_LIST_GET_LEN(buf_pool->LRU) < BUF_LRU_OLD_MIN_LEN) {
376
buf_pool->LRU_old = NULL;
381
ut_ad(buf_pool->LRU_old);
383
/* Update the LRU_old_len field if necessary */
386
buf_pool->LRU_old_len--;
389
/* Adjust the length of the old block list if necessary */
390
buf_LRU_old_adjust_len();
393
/**********************************************************************
394
Adds a block to the LRU list end. */
397
buf_LRU_add_block_to_end_low(
398
/*=========================*/
399
buf_block_t* block) /* in: control block */
401
buf_block_t* last_block;
405
ut_ad(mutex_own(&(buf_pool->mutex)));
409
last_block = UT_LIST_GET_LAST(buf_pool->LRU);
412
block->LRU_position = last_block->LRU_position;
414
block->LRU_position = buf_pool_clock_tic();
417
UT_LIST_ADD_LAST(LRU, buf_pool->LRU, block);
419
if (UT_LIST_GET_LEN(buf_pool->LRU) >= BUF_LRU_OLD_MIN_LEN) {
421
buf_pool->LRU_old_len++;
424
if (UT_LIST_GET_LEN(buf_pool->LRU) > BUF_LRU_OLD_MIN_LEN) {
426
ut_ad(buf_pool->LRU_old);
428
/* Adjust the length of the old block list if necessary */
430
buf_LRU_old_adjust_len();
432
} else if (UT_LIST_GET_LEN(buf_pool->LRU) == BUF_LRU_OLD_MIN_LEN) {
434
/* The LRU list is now long enough for LRU_old to become
441
/**********************************************************************
442
Adds a block to the LRU list. */
445
buf_LRU_add_block_low(
446
/*==================*/
447
buf_block_t* block, /* in: control block */
448
ibool old) /* in: TRUE if should be put to the old blocks
449
in the LRU list, else put to the start; if the
450
LRU list is very short, the block is added to
451
the start, regardless of this parameter */
457
ut_ad(mutex_own(&(buf_pool->mutex)));
460
cl = buf_pool_clock_tic();
462
if (!old || (UT_LIST_GET_LEN(buf_pool->LRU) < BUF_LRU_OLD_MIN_LEN)) {
464
UT_LIST_ADD_FIRST(LRU, buf_pool->LRU, block);
466
block->LRU_position = cl;
467
block->freed_page_clock = buf_pool->freed_page_clock;
469
UT_LIST_INSERT_AFTER(LRU, buf_pool->LRU, buf_pool->LRU_old,
471
buf_pool->LRU_old_len++;
473
/* We copy the LRU position field of the previous block
476
block->LRU_position = (buf_pool->LRU_old)->LRU_position;
479
if (UT_LIST_GET_LEN(buf_pool->LRU) > BUF_LRU_OLD_MIN_LEN) {
481
ut_ad(buf_pool->LRU_old);
483
/* Adjust the length of the old block list if necessary */
485
buf_LRU_old_adjust_len();
487
} else if (UT_LIST_GET_LEN(buf_pool->LRU) == BUF_LRU_OLD_MIN_LEN) {
489
/* The LRU list is now long enough for LRU_old to become
496
/**********************************************************************
497
Adds a block to the LRU list. */
502
buf_block_t* block, /* in: control block */
503
ibool old) /* in: TRUE if should be put to the old
504
blocks in the LRU list, else put to the start;
505
if the LRU list is very short, the block is
506
added to the start, regardless of this
509
buf_LRU_add_block_low(block, old);
512
/**********************************************************************
513
Moves a block to the start of the LRU list. */
516
buf_LRU_make_block_young(
517
/*=====================*/
518
buf_block_t* block) /* in: control block */
520
buf_LRU_remove_block(block);
521
buf_LRU_add_block_low(block, FALSE);
524
/**********************************************************************
525
Moves a block to the end of the LRU list. */
528
buf_LRU_make_block_old(
529
/*===================*/
530
buf_block_t* block) /* in: control block */
532
buf_LRU_remove_block(block);
533
buf_LRU_add_block_to_end_low(block);
536
/**********************************************************************
537
Puts a block back to the free list. */
540
buf_LRU_block_free_non_file_page(
541
/*=============================*/
542
buf_block_t* block) /* in: block, must not contain a file page */
544
ut_ad(mutex_own(&(buf_pool->mutex)));
547
ut_ad((block->state == BUF_BLOCK_MEMORY)
548
|| (block->state == BUF_BLOCK_READY_FOR_USE));
550
block->state = BUF_BLOCK_NOT_USED;
552
UT_LIST_ADD_FIRST(free, buf_pool->free, block);
555
/**********************************************************************
556
Takes a block out of the LRU list and page hash table and sets the block
557
state to BUF_BLOCK_REMOVE_HASH. */
560
buf_LRU_block_remove_hashed_page(
561
/*=============================*/
562
buf_block_t* block) /* in: block, must contain a file page and
563
be in a state where it can be freed; there
564
may or may not be a hash index to the page */
566
ut_ad(mutex_own(&(buf_pool->mutex)));
569
ut_ad(block->state == BUF_BLOCK_FILE_PAGE);
571
ut_a(block->io_fix == 0);
572
ut_a(block->buf_fix_count == 0);
573
ut_a(ut_dulint_cmp(block->oldest_modification, ut_dulint_zero) == 0);
575
buf_LRU_remove_block(block);
577
buf_pool->freed_page_clock += 1;
579
buf_frame_modify_clock_inc(block->frame);
581
HASH_DELETE(buf_block_t, hash, buf_pool->page_hash,
582
buf_page_address_fold(block->space, block->offset),
585
block->state = BUF_BLOCK_REMOVE_HASH;
588
/**********************************************************************
589
Puts a file page whose has no hash index to the free list. */
592
buf_LRU_block_free_hashed_page(
593
/*===========================*/
594
buf_block_t* block) /* in: block, must contain a file page and
595
be in a state where it can be freed */
597
ut_ad(mutex_own(&(buf_pool->mutex)));
598
ut_ad(block->state == BUF_BLOCK_REMOVE_HASH);
600
block->state = BUF_BLOCK_MEMORY;
602
buf_LRU_block_free_non_file_page(block);
605
/**************************************************************************
606
Validates the LRU list. */
609
buf_LRU_validate(void)
610
/*==================*/
618
mutex_enter(&(buf_pool->mutex));
620
if (UT_LIST_GET_LEN(buf_pool->LRU) >= BUF_LRU_OLD_MIN_LEN) {
622
ut_a(buf_pool->LRU_old);
623
old_len = buf_pool->LRU_old_len;
624
new_len = 3 * (UT_LIST_GET_LEN(buf_pool->LRU) / 8);
625
ut_a(old_len >= new_len - BUF_LRU_OLD_TOLERANCE);
626
ut_a(old_len <= new_len + BUF_LRU_OLD_TOLERANCE);
629
UT_LIST_VALIDATE(LRU, buf_block_t, buf_pool->LRU);
631
block = UT_LIST_GET_FIRST(buf_pool->LRU);
635
while (block != NULL) {
637
ut_a(block->state == BUF_BLOCK_FILE_PAGE);
643
if (buf_pool->LRU_old && (old_len == 1)) {
644
ut_a(buf_pool->LRU_old == block);
647
LRU_pos = block->LRU_position;
649
block = UT_LIST_GET_NEXT(LRU, block);
652
/* If the following assert fails, it may
653
not be an error: just the buf_pool clock
654
has wrapped around */
655
ut_a(LRU_pos >= block->LRU_position);
659
if (buf_pool->LRU_old) {
660
ut_a(buf_pool->LRU_old_len == old_len);
663
UT_LIST_VALIDATE(free, buf_block_t, buf_pool->free);
665
block = UT_LIST_GET_FIRST(buf_pool->free);
667
while (block != NULL) {
668
ut_a(block->state == BUF_BLOCK_NOT_USED);
670
block = UT_LIST_GET_NEXT(free, block);
673
mutex_exit(&(buf_pool->mutex));
677
/**************************************************************************
678
Prints the LRU list. */
689
mutex_enter(&(buf_pool->mutex));
691
printf("Pool ulint clock %lu\n", buf_pool->ulint_clock);
693
block = UT_LIST_GET_FIRST(buf_pool->LRU);
697
while (block != NULL) {
699
printf("BLOCK %lu ", block->offset);
705
if (block->buf_fix_count) {
706
printf("buffix count %lu ", block->buf_fix_count);
710
printf("io_fix %lu ", block->io_fix);
713
if (ut_dulint_cmp(block->oldest_modification,
714
ut_dulint_zero) > 0) {
718
printf("LRU pos %lu ", block->LRU_position);
720
frame = buf_block_get_frame(block);
722
printf("type %lu ", fil_page_get_type(frame));
723
printf("index id %lu ", ut_dulint_get_low(
724
btr_page_get_index_id(frame)));
726
block = UT_LIST_GET_NEXT(LRU, block);
733
mutex_exit(&(buf_pool->mutex));
added
removed
innobase/buf/buf0lru.c
