1 /*****************************************************************************
2 
3 Copyright (c) 1995, 2016, Oracle and/or its affiliates. All Rights Reserved.
4 
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License, version 2.0,
7 as published by the Free Software Foundation.
8 
9 This program is also distributed with certain software (including
10 but not limited to OpenSSL) that is licensed under separate terms,
11 as designated in a particular file or component or in included license
12 documentation.  The authors of MySQL hereby grant you an additional
13 permission to link the program and your derivative works with the
14 separately licensed software that they have included with MySQL.
15 
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19 GNU General Public License, version 2.0, for more details.
20 
21 You should have received a copy of the GNU General Public License along with
22 this program; if not, write to the Free Software Foundation, Inc.,
23 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
24 
25 *****************************************************************************/
26 
27 /**************************************************//**
28 @file include/buf0lru.h
29 The database buffer pool LRU replacement algorithm
30 
31 Created 11/5/1995 Heikki Tuuri
32 *******************************************************/
33 
34 #ifndef buf0lru_h
35 #define buf0lru_h
36 
37 #include "univ.i"
38 #ifndef UNIV_HOTBACKUP
39 #include "ut0byte.h"
40 #include "buf0types.h"
41 
42 // Forward declaration
43 struct trx_t;
44 
45 /******************************************************************//**
46 Returns TRUE if less than 25 % of the buffer pool is available. This can be
47 used in heuristics to prevent huge transactions eating up the whole buffer
48 pool for their locks.
49 @return	TRUE if less than 25 % of buffer pool left */
50 UNIV_INTERN
51 ibool
52 buf_LRU_buf_pool_running_out(void);
53 /*==============================*/
54 
55 /*#######################################################################
56 These are low-level functions
57 #########################################################################*/
58 
59 /** Minimum LRU list length for which the LRU_old pointer is defined */
60 #define BUF_LRU_OLD_MIN_LEN	512	/* 8 megabytes of 16k pages */
61 
62 /******************************************************************//**
63 Flushes all dirty pages or removes all pages belonging
64 to a given tablespace. A PROBLEM: if readahead is being started, what
65 guarantees that it will not try to read in pages after this operation
66 has completed? */
67 UNIV_INTERN
68 void
69 buf_LRU_flush_or_remove_pages(
70 /*==========================*/
71 	ulint		id,		/*!< in: space id */
72 	buf_remove_t	buf_remove,	/*!< in: remove or flush strategy */
73 	const trx_t*	trx);		/*!< to check if the operation must
74 					be interrupted */
75 
76 #if defined UNIV_DEBUG || defined UNIV_BUF_DEBUG
77 /********************************************************************//**
78 Insert a compressed block into buf_pool->zip_clean in the LRU order. */
79 UNIV_INTERN
80 void
81 buf_LRU_insert_zip_clean(
82 /*=====================*/
83 	buf_page_t*	bpage);	/*!< in: pointer to the block in question */
84 #endif /* UNIV_DEBUG || UNIV_BUF_DEBUG */
85 
86 /******************************************************************//**
87 Try to free a block.  If bpage is a descriptor of a compressed-only
88 page, the descriptor object will be freed as well.
89 
90 NOTE: If this function returns true, it will temporarily
91 release buf_pool->mutex.  Furthermore, the page frame will no longer be
92 accessible via bpage.
93 
94 The caller must hold buf_pool->mutex and must not hold any
95 buf_page_get_mutex() when calling this function.
96 @return true if freed, false otherwise. */
97 UNIV_INTERN
98 bool
99 buf_LRU_free_page(
100 /*==============*/
101 	buf_page_t*	bpage,	/*!< in: block to be freed */
102 	bool		zip)	/*!< in: true if should remove also the
103 				compressed page of an uncompressed page */
104 	MY_ATTRIBUTE((nonnull));
105 /******************************************************************//**
106 Try to free a replaceable block.
107 @return	TRUE if found and freed */
108 UNIV_INTERN
109 ibool
110 buf_LRU_scan_and_free_block(
111 /*========================*/
112 	buf_pool_t*	buf_pool,	/*!< in: buffer pool instance */
113 	ibool		scan_all)	/*!< in: scan whole LRU list
114 					if TRUE, otherwise scan only
115 					'old' blocks. */
116 	MY_ATTRIBUTE((nonnull,warn_unused_result));
117 /******************************************************************//**
118 Returns a free block from the buf_pool.  The block is taken off the
119 free list.  If it is empty, returns NULL.
120 @return	a free control block, or NULL if the buf_block->free list is empty */
121 UNIV_INTERN
122 buf_block_t*
123 buf_LRU_get_free_only(
124 /*==================*/
125 	buf_pool_t*	buf_pool);	/*!< buffer pool instance */
126 /******************************************************************//**
127 Returns a free block from the buf_pool. The block is taken off the
128 free list. If it is empty, blocks are moved from the end of the
129 LRU list to the free list.
130 This function is called from a user thread when it needs a clean
131 block to read in a page. Note that we only ever get a block from
132 the free list. Even when we flush a page or find a page in LRU scan
133 we put it to free list to be used.
134 * iteration 0:
135   * get a block from free list, success:done
136   * if there is an LRU flush batch in progress:
137     * wait for batch to end: retry free list
138   * if buf_pool->try_LRU_scan is set
139     * scan LRU up to srv_LRU_scan_depth to find a clean block
140     * the above will put the block on free list
141     * success:retry the free list
142   * flush one dirty page from tail of LRU to disk
143     * the above will put the block on free list
144     * success: retry the free list
145 * iteration 1:
146   * same as iteration 0 except:
147     * scan whole LRU list
148     * scan LRU list even if buf_pool->try_LRU_scan is not set
149 * iteration > 1:
150   * same as iteration 1 but sleep 100ms
151 @return	the free control block, in state BUF_BLOCK_READY_FOR_USE */
152 UNIV_INTERN
153 buf_block_t*
154 buf_LRU_get_free_block(
155 /*===================*/
156 	buf_pool_t*	buf_pool)	/*!< in/out: buffer pool instance */
157 	MY_ATTRIBUTE((nonnull,warn_unused_result));
158 /******************************************************************//**
159 Determines if the unzip_LRU list should be used for evicting a victim
160 instead of the general LRU list.
161 @return	TRUE if should use unzip_LRU */
162 UNIV_INTERN
163 ibool
164 buf_LRU_evict_from_unzip_LRU(
165 /*=========================*/
166 	buf_pool_t*	buf_pool);
167 /******************************************************************//**
168 Puts a block back to the free list. */
169 UNIV_INTERN
170 void
171 buf_LRU_block_free_non_file_page(
172 /*=============================*/
173 	buf_block_t*	block);	/*!< in: block, must not contain a file page */
174 /******************************************************************//**
175 Adds a block to the LRU list. Please make sure that the zip_size is
176 already set into the page zip when invoking the function, so that we
177 can get correct zip_size from the buffer page when adding a block
178 into LRU */
179 UNIV_INTERN
180 void
181 buf_LRU_add_block(
182 /*==============*/
183 	buf_page_t*	bpage,	/*!< in: control block */
184 	ibool		old);	/*!< in: TRUE if should be put to the old
185 				blocks in the LRU list, else put to the
186 				start; if the LRU list is very short, added to
187 				the start regardless of this parameter */
188 /******************************************************************//**
189 Adds a block to the LRU list of decompressed zip pages. */
190 UNIV_INTERN
191 void
192 buf_unzip_LRU_add_block(
193 /*====================*/
194 	buf_block_t*	block,	/*!< in: control block */
195 	ibool		old);	/*!< in: TRUE if should be put to the end
196 				of the list, else put to the start */
197 /******************************************************************//**
198 Moves a block to the start of the LRU list. */
199 UNIV_INTERN
200 void
201 buf_LRU_make_block_young(
202 /*=====================*/
203 	buf_page_t*	bpage);	/*!< in: control block */
204 /******************************************************************//**
205 Moves a block to the end of the LRU list. */
206 UNIV_INTERN
207 void
208 buf_LRU_make_block_old(
209 /*===================*/
210 	buf_page_t*	bpage);	/*!< in: control block */
211 /**********************************************************************//**
212 Updates buf_pool->LRU_old_ratio.
213 @return	updated old_pct */
214 UNIV_INTERN
215 ulint
216 buf_LRU_old_ratio_update(
217 /*=====================*/
218 	uint	old_pct,/*!< in: Reserve this percentage of
219 			the buffer pool for "old" blocks. */
220 	ibool	adjust);/*!< in: TRUE=adjust the LRU list;
221 			FALSE=just assign buf_pool->LRU_old_ratio
222 			during the initialization of InnoDB */
223 /********************************************************************//**
224 Update the historical stats that we are collecting for LRU eviction
225 policy at the end of each interval. */
226 UNIV_INTERN
227 void
228 buf_LRU_stat_update(void);
229 /*=====================*/
230 
231 /******************************************************************//**
232 Remove one page from LRU list and put it to free list */
233 UNIV_INTERN
234 void
235 buf_LRU_free_one_page(
236 /*==================*/
237 	buf_page_t*	bpage)	/*!< in/out: block, must contain a file page and
238 				be in a state where it can be freed; there
239 				may or may not be a hash index to the page */
240 	MY_ATTRIBUTE((nonnull));
241 
242 #if defined UNIV_DEBUG || defined UNIV_BUF_DEBUG
243 /**********************************************************************//**
244 Validates the LRU list.
245 @return	TRUE */
246 UNIV_INTERN
247 ibool
248 buf_LRU_validate(void);
249 /*==================*/
250 #endif /* UNIV_DEBUG || UNIV_BUF_DEBUG */
251 #if defined UNIV_DEBUG_PRINT || defined UNIV_DEBUG || defined UNIV_BUF_DEBUG
252 /**********************************************************************//**
253 Prints the LRU list. */
254 UNIV_INTERN
255 void
256 buf_LRU_print(void);
257 /*===============*/
258 #endif /* UNIV_DEBUG_PRINT || UNIV_DEBUG || UNIV_BUF_DEBUG */
259 
260 /** @name Heuristics for detecting index scan @{ */
261 /** The denominator of buf_pool->LRU_old_ratio. */
262 #define BUF_LRU_OLD_RATIO_DIV	1024
263 /** Maximum value of buf_pool->LRU_old_ratio.
264 @see buf_LRU_old_adjust_len
265 @see buf_pool->LRU_old_ratio_update */
266 #define BUF_LRU_OLD_RATIO_MAX	BUF_LRU_OLD_RATIO_DIV
267 /** Minimum value of buf_pool->LRU_old_ratio.
268 @see buf_LRU_old_adjust_len
269 @see buf_pool->LRU_old_ratio_update
270 The minimum must exceed
271 (BUF_LRU_OLD_TOLERANCE + 5) * BUF_LRU_OLD_RATIO_DIV / BUF_LRU_OLD_MIN_LEN. */
272 #define BUF_LRU_OLD_RATIO_MIN	51
273 
274 #if BUF_LRU_OLD_RATIO_MIN >= BUF_LRU_OLD_RATIO_MAX
275 # error "BUF_LRU_OLD_RATIO_MIN >= BUF_LRU_OLD_RATIO_MAX"
276 #endif
277 #if BUF_LRU_OLD_RATIO_MAX > BUF_LRU_OLD_RATIO_DIV
278 # error "BUF_LRU_OLD_RATIO_MAX > BUF_LRU_OLD_RATIO_DIV"
279 #endif
280 
281 /** Move blocks to "new" LRU list only if the first access was at
282 least this many milliseconds ago.  Not protected by any mutex or latch. */
283 extern uint	buf_LRU_old_threshold_ms;
284 /* @} */
285 
286 /** @brief Statistics for selecting the LRU list for eviction.
287 
288 These statistics are not 'of' LRU but 'for' LRU.  We keep count of I/O
289 and page_zip_decompress() operations.  Based on the statistics we decide
290 if we want to evict from buf_pool->unzip_LRU or buf_pool->LRU. */
291 struct buf_LRU_stat_t
292 {
293 	ulint	io;	/**< Counter of buffer pool I/O operations. */
294 	ulint	unzip;	/**< Counter of page_zip_decompress operations. */
295 };
296 
297 /** Current operation counters.  Not protected by any mutex.
298 Cleared by buf_LRU_stat_update(). */
299 extern buf_LRU_stat_t	buf_LRU_stat_cur;
300 
301 /** Running sum of past values of buf_LRU_stat_cur.
302 Updated by buf_LRU_stat_update().  Protected by buf_pool->mutex. */
303 extern buf_LRU_stat_t	buf_LRU_stat_sum;
304 
305 /********************************************************************//**
306 Increments the I/O counter in buf_LRU_stat_cur. */
307 #define buf_LRU_stat_inc_io() buf_LRU_stat_cur.io++
308 /********************************************************************//**
309 Increments the page_zip_decompress() counter in buf_LRU_stat_cur. */
310 #define buf_LRU_stat_inc_unzip() buf_LRU_stat_cur.unzip++
311 
312 #ifndef UNIV_NONINL
313 #include "buf0lru.ic"
314 #endif
315 
316 #endif /* !UNIV_HOTBACKUP */
317 
318 #endif
319