MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
fut0lst.cc
Go to the documentation of this file.
1 /*****************************************************************************
2 
3 Copyright (c) 1995, 2011, Oracle and/or its affiliates. All Rights Reserved.
4 
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.
8 
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.
12 
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.,
15 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
16 
17 *****************************************************************************/
18 
19 /******************************************************************/
26 #include "fut0lst.h"
27 
28 #ifdef UNIV_NONINL
29 #include "fut0lst.ic"
30 #endif
31 
32 #include "buf0buf.h"
33 #include "page0page.h"
34 
35 /********************************************************************/
37 static
38 void
39 flst_add_to_empty(
40 /*==============*/
41  flst_base_node_t* base,
43  flst_node_t* node,
44  mtr_t* mtr)
45 {
46  ulint space;
47  fil_addr_t node_addr;
48  ulint len;
49 
50  ut_ad(mtr && base && node);
51  ut_ad(base != node);
52  ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
53  ut_ad(mtr_memo_contains_page(mtr, node, MTR_MEMO_PAGE_X_FIX));
54  len = flst_get_len(base, mtr);
55  ut_a(len == 0);
56 
57  buf_ptr_get_fsp_addr(node, &space, &node_addr);
58 
59  /* Update first and last fields of base node */
60  flst_write_addr(base + FLST_FIRST, node_addr, mtr);
61  flst_write_addr(base + FLST_LAST, node_addr, mtr);
62 
63  /* Set prev and next fields of node to add */
64  flst_write_addr(node + FLST_PREV, fil_addr_null, mtr);
65  flst_write_addr(node + FLST_NEXT, fil_addr_null, mtr);
66 
67  /* Update len of base node */
68  mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
69 }
70 
71 /********************************************************************/
73 UNIV_INTERN
74 void
75 flst_add_last(
76 /*==========*/
77  flst_base_node_t* base,
78  flst_node_t* node,
79  mtr_t* mtr)
80 {
81  ulint space;
82  fil_addr_t node_addr;
83  ulint len;
84  fil_addr_t last_addr;
85  flst_node_t* last_node;
86 
87  ut_ad(mtr && base && node);
88  ut_ad(base != node);
89  ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
90  ut_ad(mtr_memo_contains_page(mtr, node, MTR_MEMO_PAGE_X_FIX));
91  len = flst_get_len(base, mtr);
92  last_addr = flst_get_last(base, mtr);
93 
94  buf_ptr_get_fsp_addr(node, &space, &node_addr);
95 
96  /* If the list is not empty, call flst_insert_after */
97  if (len != 0) {
98  if (last_addr.page == node_addr.page) {
99  last_node = page_align(node) + last_addr.boffset;
100  } else {
101  ulint zip_size = fil_space_get_zip_size(space);
102 
103  last_node = fut_get_ptr(space, zip_size, last_addr,
104  RW_X_LATCH, mtr);
105  }
106 
107  flst_insert_after(base, last_node, node, mtr);
108  } else {
109  /* else call flst_add_to_empty */
110  flst_add_to_empty(base, node, mtr);
111  }
112 }
113 
114 /********************************************************************/
116 UNIV_INTERN
117 void
118 flst_add_first(
119 /*===========*/
120  flst_base_node_t* base,
121  flst_node_t* node,
122  mtr_t* mtr)
123 {
124  ulint space;
125  fil_addr_t node_addr;
126  ulint len;
127  fil_addr_t first_addr;
128  flst_node_t* first_node;
129 
130  ut_ad(mtr && base && node);
131  ut_ad(base != node);
132  ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
133  ut_ad(mtr_memo_contains_page(mtr, node, MTR_MEMO_PAGE_X_FIX));
134  len = flst_get_len(base, mtr);
135  first_addr = flst_get_first(base, mtr);
136 
137  buf_ptr_get_fsp_addr(node, &space, &node_addr);
138 
139  /* If the list is not empty, call flst_insert_before */
140  if (len != 0) {
141  if (first_addr.page == node_addr.page) {
142  first_node = page_align(node) + first_addr.boffset;
143  } else {
144  ulint zip_size = fil_space_get_zip_size(space);
145 
146  first_node = fut_get_ptr(space, zip_size, first_addr,
147  RW_X_LATCH, mtr);
148  }
149 
150  flst_insert_before(base, node, first_node, mtr);
151  } else {
152  /* else call flst_add_to_empty */
153  flst_add_to_empty(base, node, mtr);
154  }
155 }
156 
157 /********************************************************************/
159 UNIV_INTERN
160 void
161 flst_insert_after(
162 /*==============*/
163  flst_base_node_t* base,
164  flst_node_t* node1,
165  flst_node_t* node2,
166  mtr_t* mtr)
167 {
168  ulint space;
169  fil_addr_t node1_addr;
170  fil_addr_t node2_addr;
171  flst_node_t* node3;
172  fil_addr_t node3_addr;
173  ulint len;
174 
175  ut_ad(mtr && node1 && node2 && base);
176  ut_ad(base != node1);
177  ut_ad(base != node2);
178  ut_ad(node2 != node1);
179  ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
180  ut_ad(mtr_memo_contains_page(mtr, node1, MTR_MEMO_PAGE_X_FIX));
181  ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
182 
183  buf_ptr_get_fsp_addr(node1, &space, &node1_addr);
184  buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
185 
186  node3_addr = flst_get_next_addr(node1, mtr);
187 
188  /* Set prev and next fields of node2 */
189  flst_write_addr(node2 + FLST_PREV, node1_addr, mtr);
190  flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr);
191 
192  if (!fil_addr_is_null(node3_addr)) {
193  /* Update prev field of node3 */
194  ulint zip_size = fil_space_get_zip_size(space);
195 
196  node3 = fut_get_ptr(space, zip_size,
197  node3_addr, RW_X_LATCH, mtr);
198  flst_write_addr(node3 + FLST_PREV, node2_addr, mtr);
199  } else {
200  /* node1 was last in list: update last field in base */
201  flst_write_addr(base + FLST_LAST, node2_addr, mtr);
202  }
203 
204  /* Set next field of node1 */
205  flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr);
206 
207  /* Update len of base node */
208  len = flst_get_len(base, mtr);
209  mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
210 }
211 
212 /********************************************************************/
214 UNIV_INTERN
215 void
216 flst_insert_before(
217 /*===============*/
218  flst_base_node_t* base,
219  flst_node_t* node2,
220  flst_node_t* node3,
221  mtr_t* mtr)
222 {
223  ulint space;
224  flst_node_t* node1;
225  fil_addr_t node1_addr;
226  fil_addr_t node2_addr;
227  fil_addr_t node3_addr;
228  ulint len;
229 
230  ut_ad(mtr && node2 && node3 && base);
231  ut_ad(base != node2);
232  ut_ad(base != node3);
233  ut_ad(node2 != node3);
234  ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
235  ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
236  ut_ad(mtr_memo_contains_page(mtr, node3, MTR_MEMO_PAGE_X_FIX));
237 
238  buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
239  buf_ptr_get_fsp_addr(node3, &space, &node3_addr);
240 
241  node1_addr = flst_get_prev_addr(node3, mtr);
242 
243  /* Set prev and next fields of node2 */
244  flst_write_addr(node2 + FLST_PREV, node1_addr, mtr);
245  flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr);
246 
247  if (!fil_addr_is_null(node1_addr)) {
248  ulint zip_size = fil_space_get_zip_size(space);
249  /* Update next field of node1 */
250  node1 = fut_get_ptr(space, zip_size, node1_addr,
251  RW_X_LATCH, mtr);
252  flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr);
253  } else {
254  /* node3 was first in list: update first field in base */
255  flst_write_addr(base + FLST_FIRST, node2_addr, mtr);
256  }
257 
258  /* Set prev field of node3 */
259  flst_write_addr(node3 + FLST_PREV, node2_addr, mtr);
260 
261  /* Update len of base node */
262  len = flst_get_len(base, mtr);
263  mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
264 }
265 
266 /********************************************************************/
268 UNIV_INTERN
269 void
270 flst_remove(
271 /*========*/
272  flst_base_node_t* base,
273  flst_node_t* node2,
274  mtr_t* mtr)
275 {
276  ulint space;
277  ulint zip_size;
278  flst_node_t* node1;
279  fil_addr_t node1_addr;
280  fil_addr_t node2_addr;
281  flst_node_t* node3;
282  fil_addr_t node3_addr;
283  ulint len;
284 
285  ut_ad(mtr && node2 && base);
286  ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
287  ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
288 
289  buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
290  zip_size = fil_space_get_zip_size(space);
291 
292  node1_addr = flst_get_prev_addr(node2, mtr);
293  node3_addr = flst_get_next_addr(node2, mtr);
294 
295  if (!fil_addr_is_null(node1_addr)) {
296 
297  /* Update next field of node1 */
298 
299  if (node1_addr.page == node2_addr.page) {
300 
301  node1 = page_align(node2) + node1_addr.boffset;
302  } else {
303  node1 = fut_get_ptr(space, zip_size,
304  node1_addr, RW_X_LATCH, mtr);
305  }
306 
307  ut_ad(node1 != node2);
308 
309  flst_write_addr(node1 + FLST_NEXT, node3_addr, mtr);
310  } else {
311  /* node2 was first in list: update first field in base */
312  flst_write_addr(base + FLST_FIRST, node3_addr, mtr);
313  }
314 
315  if (!fil_addr_is_null(node3_addr)) {
316  /* Update prev field of node3 */
317 
318  if (node3_addr.page == node2_addr.page) {
319 
320  node3 = page_align(node2) + node3_addr.boffset;
321  } else {
322  node3 = fut_get_ptr(space, zip_size,
323  node3_addr, RW_X_LATCH, mtr);
324  }
325 
326  ut_ad(node2 != node3);
327 
328  flst_write_addr(node3 + FLST_PREV, node1_addr, mtr);
329  } else {
330  /* node2 was last in list: update last field in base */
331  flst_write_addr(base + FLST_LAST, node1_addr, mtr);
332  }
333 
334  /* Update len of base node */
335  len = flst_get_len(base, mtr);
336  ut_ad(len > 0);
337 
338  mlog_write_ulint(base + FLST_LEN, len - 1, MLOG_4BYTES, mtr);
339 }
340 
341 /********************************************************************/
345 UNIV_INTERN
346 void
347 flst_cut_end(
348 /*=========*/
349  flst_base_node_t* base,
350  flst_node_t* node2,
351  ulint n_nodes,
353  mtr_t* mtr)
354 {
355  ulint space;
356  flst_node_t* node1;
357  fil_addr_t node1_addr;
358  fil_addr_t node2_addr;
359  ulint len;
360 
361  ut_ad(mtr && node2 && base);
362  ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
363  ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
364  ut_ad(n_nodes > 0);
365 
366  buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
367 
368  node1_addr = flst_get_prev_addr(node2, mtr);
369 
370  if (!fil_addr_is_null(node1_addr)) {
371 
372  /* Update next field of node1 */
373 
374  if (node1_addr.page == node2_addr.page) {
375 
376  node1 = page_align(node2) + node1_addr.boffset;
377  } else {
378  node1 = fut_get_ptr(space,
379  fil_space_get_zip_size(space),
380  node1_addr, RW_X_LATCH, mtr);
381  }
382 
383  flst_write_addr(node1 + FLST_NEXT, fil_addr_null, mtr);
384  } else {
385  /* node2 was first in list: update the field in base */
386  flst_write_addr(base + FLST_FIRST, fil_addr_null, mtr);
387  }
388 
389  flst_write_addr(base + FLST_LAST, node1_addr, mtr);
390 
391  /* Update len of base node */
392  len = flst_get_len(base, mtr);
393  ut_ad(len >= n_nodes);
394 
395  mlog_write_ulint(base + FLST_LEN, len - n_nodes, MLOG_4BYTES, mtr);
396 }
397 
398 /********************************************************************/
402 UNIV_INTERN
403 void
404 flst_truncate_end(
405 /*==============*/
406  flst_base_node_t* base,
407  flst_node_t* node2,
408  ulint n_nodes,
409  mtr_t* mtr)
410 {
411  fil_addr_t node2_addr;
412  ulint len;
413  ulint space;
414 
415  ut_ad(mtr && node2 && base);
416  ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
417  ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
418  if (n_nodes == 0) {
419 
420  ut_ad(fil_addr_is_null(flst_get_next_addr(node2, mtr)));
421 
422  return;
423  }
424 
425  buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
426 
427  /* Update next field of node2 */
428  flst_write_addr(node2 + FLST_NEXT, fil_addr_null, mtr);
429 
430  flst_write_addr(base + FLST_LAST, node2_addr, mtr);
431 
432  /* Update len of base node */
433  len = flst_get_len(base, mtr);
434  ut_ad(len >= n_nodes);
435 
436  mlog_write_ulint(base + FLST_LEN, len - n_nodes, MLOG_4BYTES, mtr);
437 }
438 
439 /********************************************************************/
442 UNIV_INTERN
443 ibool
444 flst_validate(
445 /*==========*/
446  const flst_base_node_t* base,
447  mtr_t* mtr1)
448 {
449  ulint space;
450  ulint zip_size;
451  const flst_node_t* node;
452  fil_addr_t node_addr;
453  fil_addr_t base_addr;
454  ulint len;
455  ulint i;
456  mtr_t mtr2;
457 
458  ut_ad(base);
459  ut_ad(mtr_memo_contains_page(mtr1, base, MTR_MEMO_PAGE_X_FIX));
460 
461  /* We use two mini-transaction handles: the first is used to
462  lock the base node, and prevent other threads from modifying the
463  list. The second is used to traverse the list. We cannot run the
464  second mtr without committing it at times, because if the list
465  is long, then the x-locked pages could fill the buffer resulting
466  in a deadlock. */
467 
468  /* Find out the space id */
469  buf_ptr_get_fsp_addr(base, &space, &base_addr);
470  zip_size = fil_space_get_zip_size(space);
471 
472  len = flst_get_len(base, mtr1);
473  node_addr = flst_get_first(base, mtr1);
474 
475  for (i = 0; i < len; i++) {
476  mtr_start(&mtr2);
477 
478  node = fut_get_ptr(space, zip_size,
479  node_addr, RW_X_LATCH, &mtr2);
480  node_addr = flst_get_next_addr(node, &mtr2);
481 
482  mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer
483  becoming full */
484  }
485 
486  ut_a(fil_addr_is_null(node_addr));
487 
488  node_addr = flst_get_last(base, mtr1);
489 
490  for (i = 0; i < len; i++) {
491  mtr_start(&mtr2);
492 
493  node = fut_get_ptr(space, zip_size,
494  node_addr, RW_X_LATCH, &mtr2);
495  node_addr = flst_get_prev_addr(node, &mtr2);
496 
497  mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer
498  becoming full */
499  }
500 
501  ut_a(fil_addr_is_null(node_addr));
502 
503  return(TRUE);
504 }
505 
506 /********************************************************************/
508 UNIV_INTERN
509 void
510 flst_print(
511 /*=======*/
512  const flst_base_node_t* base,
513  mtr_t* mtr)
514 {
515  const buf_frame_t* frame;
516  ulint len;
517 
518  ut_ad(base && mtr);
519  ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
520  frame = page_align((byte*) base);
521 
522  len = flst_get_len(base, mtr);
523 
524  fprintf(stderr,
525  "FILE-BASED LIST:\n"
526  "Base node in space %lu page %lu byte offset %lu; len %lu\n",
527  (ulong) page_get_space_id(frame),
528  (ulong) page_get_page_no(frame),
529  (ulong) page_offset(base), (ulong) len);
530 }