1/*****************************************************************************
2
3Copyright (c) 1995, 2016, Oracle and/or its affiliates. All Rights Reserved.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License as published by the Free Software
7Foundation; version 2 of the License.
8
9This program is distributed in the hope that it will be useful, but WITHOUT
10ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
13You should have received a copy of the GNU General Public License along with
14this program; if not, write to the Free Software Foundation, Inc.,
1551 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
16
17*****************************************************************************/
18
19/******************************************************************//**
20@file fut/fut0lst.cc
21File-based list utilities
22
23Created 11/28/1995 Heikki Tuuri
24***********************************************************************/
25
26#include "fut0lst.h"
27#include "buf0buf.h"
28#include "page0page.h"
29
30/********************************************************************//**
31Adds a node to an empty list. */
32static
33void
34flst_add_to_empty(
35/*==============*/
36 flst_base_node_t* base, /*!< in: pointer to base node of
37 empty list */
38 flst_node_t* node, /*!< in: node to add */
39 mtr_t* mtr) /*!< in: mini-transaction handle */
40{
41 ulint space;
42 fil_addr_t node_addr;
43
44 ut_ad(mtr && base && node);
45 ut_ad(base != node);
46 ut_ad(mtr_memo_contains_page_flagged(mtr, base,
47 MTR_MEMO_PAGE_X_FIX
48 | MTR_MEMO_PAGE_SX_FIX));
49 ut_ad(mtr_memo_contains_page_flagged(mtr, node,
50 MTR_MEMO_PAGE_X_FIX
51 | MTR_MEMO_PAGE_SX_FIX));
52 ut_a(!flst_get_len(base));
53
54 buf_ptr_get_fsp_addr(node, &space, &node_addr);
55
56 /* Update first and last fields of base node */
57 flst_write_addr(base + FLST_FIRST, node_addr, mtr);
58 flst_write_addr(base + FLST_LAST, node_addr, mtr);
59
60 /* Set prev and next fields of node to add */
61 flst_write_addr(node + FLST_PREV, fil_addr_null, mtr);
62 flst_write_addr(node + FLST_NEXT, fil_addr_null, mtr);
63
64 /* Update len of base node */
65 mlog_write_ulint(base + FLST_LEN, 1, MLOG_4BYTES, mtr);
66}
67
68/********************************************************************//**
69Inserts a node after another in a list. */
70static
71void
72flst_insert_after(
73/*==============*/
74 flst_base_node_t* base, /*!< in: pointer to base node of list */
75 flst_node_t* node1, /*!< in: node to insert after */
76 flst_node_t* node2, /*!< in: node to add */
77 mtr_t* mtr); /*!< in: mini-transaction handle */
78/********************************************************************//**
79Inserts a node before another in a list. */
80static
81void
82flst_insert_before(
83/*===============*/
84 flst_base_node_t* base, /*!< in: pointer to base node of list */
85 flst_node_t* node2, /*!< in: node to insert */
86 flst_node_t* node3, /*!< in: node to insert before */
87 mtr_t* mtr); /*!< in: mini-transaction handle */
88
89/********************************************************************//**
90Adds a node as the last node in a list. */
91void
92flst_add_last(
93/*==========*/
94 flst_base_node_t* base, /*!< in: pointer to base node of list */
95 flst_node_t* node, /*!< in: node to add */
96 mtr_t* mtr) /*!< in: mini-transaction handle */
97{
98 ulint space;
99 fil_addr_t node_addr;
100 ulint len;
101 fil_addr_t last_addr;
102
103 ut_ad(mtr && base && node);
104 ut_ad(base != node);
105 ut_ad(mtr_memo_contains_page_flagged(mtr, base,
106 MTR_MEMO_PAGE_X_FIX
107 | MTR_MEMO_PAGE_SX_FIX));
108 ut_ad(mtr_memo_contains_page_flagged(mtr, node,
109 MTR_MEMO_PAGE_X_FIX
110 | MTR_MEMO_PAGE_SX_FIX));
111 len = flst_get_len(base);
112 last_addr = flst_get_last(base, mtr);
113
114 buf_ptr_get_fsp_addr(node, &space, &node_addr);
115
116 /* If the list is not empty, call flst_insert_after */
117 if (len != 0) {
118 flst_node_t* last_node;
119
120 if (last_addr.page == node_addr.page) {
121 last_node = page_align(node) + last_addr.boffset;
122 } else {
123 bool found;
124 const page_size_t& page_size
125 = fil_space_get_page_size(space, &found);
126
127 ut_ad(found);
128
129 last_node = fut_get_ptr(space, page_size, last_addr,
130 RW_SX_LATCH, mtr);
131 }
132
133 flst_insert_after(base, last_node, node, mtr);
134 } else {
135 /* else call flst_add_to_empty */
136 flst_add_to_empty(base, node, mtr);
137 }
138}
139
140/********************************************************************//**
141Adds a node as the first node in a list. */
142void
143flst_add_first(
144/*===========*/
145 flst_base_node_t* base, /*!< in: pointer to base node of list */
146 flst_node_t* node, /*!< in: node to add */
147 mtr_t* mtr) /*!< in: mini-transaction handle */
148{
149 ulint space;
150 fil_addr_t node_addr;
151 ulint len;
152 fil_addr_t first_addr;
153 flst_node_t* first_node;
154
155 ut_ad(mtr && base && node);
156 ut_ad(base != node);
157 ut_ad(mtr_memo_contains_page_flagged(mtr, base,
158 MTR_MEMO_PAGE_X_FIX
159 | MTR_MEMO_PAGE_SX_FIX));
160 ut_ad(mtr_memo_contains_page_flagged(mtr, node,
161 MTR_MEMO_PAGE_X_FIX
162 | MTR_MEMO_PAGE_SX_FIX));
163 len = flst_get_len(base);
164 first_addr = flst_get_first(base, mtr);
165
166 buf_ptr_get_fsp_addr(node, &space, &node_addr);
167
168 /* If the list is not empty, call flst_insert_before */
169 if (len != 0) {
170 if (first_addr.page == node_addr.page) {
171 first_node = page_align(node) + first_addr.boffset;
172 } else {
173 bool found;
174 const page_size_t& page_size
175 = fil_space_get_page_size(space, &found);
176
177 ut_ad(found);
178
179 first_node = fut_get_ptr(space, page_size, first_addr,
180 RW_SX_LATCH, mtr);
181 }
182
183 flst_insert_before(base, node, first_node, mtr);
184 } else {
185 /* else call flst_add_to_empty */
186 flst_add_to_empty(base, node, mtr);
187 }
188}
189
190/********************************************************************//**
191Inserts a node after another in a list. */
192static
193void
194flst_insert_after(
195/*==============*/
196 flst_base_node_t* base, /*!< in: pointer to base node of list */
197 flst_node_t* node1, /*!< in: node to insert after */
198 flst_node_t* node2, /*!< in: node to add */
199 mtr_t* mtr) /*!< in: mini-transaction handle */
200{
201 ulint space;
202 fil_addr_t node1_addr;
203 fil_addr_t node2_addr;
204 flst_node_t* node3;
205 fil_addr_t node3_addr;
206 ulint len;
207
208 ut_ad(mtr && node1 && node2 && base);
209 ut_ad(base != node1);
210 ut_ad(base != node2);
211 ut_ad(node2 != node1);
212 ut_ad(mtr_memo_contains_page_flagged(mtr, base,
213 MTR_MEMO_PAGE_X_FIX
214 | MTR_MEMO_PAGE_SX_FIX));
215 ut_ad(mtr_memo_contains_page_flagged(mtr, node1,
216 MTR_MEMO_PAGE_X_FIX
217 | MTR_MEMO_PAGE_SX_FIX));
218 ut_ad(mtr_memo_contains_page_flagged(mtr, node2,
219 MTR_MEMO_PAGE_X_FIX
220 | MTR_MEMO_PAGE_SX_FIX));
221
222 buf_ptr_get_fsp_addr(node1, &space, &node1_addr);
223 buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
224
225 node3_addr = flst_get_next_addr(node1, mtr);
226
227 /* Set prev and next fields of node2 */
228 flst_write_addr(node2 + FLST_PREV, node1_addr, mtr);
229 flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr);
230
231 if (!fil_addr_is_null(node3_addr)) {
232 /* Update prev field of node3 */
233 bool found;
234 const page_size_t& page_size
235 = fil_space_get_page_size(space, &found);
236
237 ut_ad(found);
238
239 node3 = fut_get_ptr(space, page_size,
240 node3_addr, RW_SX_LATCH, mtr);
241 flst_write_addr(node3 + FLST_PREV, node2_addr, mtr);
242 } else {
243 /* node1 was last in list: update last field in base */
244 flst_write_addr(base + FLST_LAST, node2_addr, mtr);
245 }
246
247 /* Set next field of node1 */
248 flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr);
249
250 /* Update len of base node */
251 len = flst_get_len(base);
252 mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
253}
254
255/********************************************************************//**
256Inserts a node before another in a list. */
257static
258void
259flst_insert_before(
260/*===============*/
261 flst_base_node_t* base, /*!< in: pointer to base node of list */
262 flst_node_t* node2, /*!< in: node to insert */
263 flst_node_t* node3, /*!< in: node to insert before */
264 mtr_t* mtr) /*!< in: mini-transaction handle */
265{
266 ulint space;
267 flst_node_t* node1;
268 fil_addr_t node1_addr;
269 fil_addr_t node2_addr;
270 fil_addr_t node3_addr;
271 ulint len;
272
273 ut_ad(mtr && node2 && node3 && base);
274 ut_ad(base != node2);
275 ut_ad(base != node3);
276 ut_ad(node2 != node3);
277 ut_ad(mtr_memo_contains_page_flagged(mtr, base,
278 MTR_MEMO_PAGE_X_FIX
279 | MTR_MEMO_PAGE_SX_FIX));
280 ut_ad(mtr_memo_contains_page_flagged(mtr, node2,
281 MTR_MEMO_PAGE_X_FIX
282 | MTR_MEMO_PAGE_SX_FIX));
283 ut_ad(mtr_memo_contains_page_flagged(mtr, node3,
284 MTR_MEMO_PAGE_X_FIX
285 | MTR_MEMO_PAGE_SX_FIX));
286
287 buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
288 buf_ptr_get_fsp_addr(node3, &space, &node3_addr);
289
290 node1_addr = flst_get_prev_addr(node3, mtr);
291
292 /* Set prev and next fields of node2 */
293 flst_write_addr(node2 + FLST_PREV, node1_addr, mtr);
294 flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr);
295
296 if (!fil_addr_is_null(node1_addr)) {
297 bool found;
298 const page_size_t& page_size
299 = fil_space_get_page_size(space, &found);
300
301 ut_ad(found);
302
303 /* Update next field of node1 */
304 node1 = fut_get_ptr(space, page_size, node1_addr,
305 RW_SX_LATCH, mtr);
306 flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr);
307 } else {
308 /* node3 was first in list: update first field in base */
309 flst_write_addr(base + FLST_FIRST, node2_addr, mtr);
310 }
311
312 /* Set prev field of node3 */
313 flst_write_addr(node3 + FLST_PREV, node2_addr, mtr);
314
315 /* Update len of base node */
316 len = flst_get_len(base);
317 mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
318}
319
320/********************************************************************//**
321Removes a node. */
322void
323flst_remove(
324/*========*/
325 flst_base_node_t* base, /*!< in: pointer to base node of list */
326 flst_node_t* node2, /*!< in: node to remove */
327 mtr_t* mtr) /*!< in: mini-transaction handle */
328{
329 ulint space;
330 flst_node_t* node1;
331 fil_addr_t node1_addr;
332 fil_addr_t node2_addr;
333 flst_node_t* node3;
334 fil_addr_t node3_addr;
335 ulint len;
336
337 ut_ad(mtr && node2 && base);
338 ut_ad(mtr_memo_contains_page_flagged(mtr, base,
339 MTR_MEMO_PAGE_X_FIX
340 | MTR_MEMO_PAGE_SX_FIX));
341 ut_ad(mtr_memo_contains_page_flagged(mtr, node2,
342 MTR_MEMO_PAGE_X_FIX
343 | MTR_MEMO_PAGE_SX_FIX));
344
345 buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
346
347 bool found;
348 const page_size_t& page_size = fil_space_get_page_size(space,
349 &found);
350
351 ut_ad(found);
352
353 node1_addr = flst_get_prev_addr(node2, mtr);
354 node3_addr = flst_get_next_addr(node2, mtr);
355
356 if (!fil_addr_is_null(node1_addr)) {
357
358 /* Update next field of node1 */
359
360 if (node1_addr.page == node2_addr.page) {
361
362 node1 = page_align(node2) + node1_addr.boffset;
363 } else {
364 node1 = fut_get_ptr(space, page_size,
365 node1_addr, RW_SX_LATCH, mtr);
366 }
367
368 ut_ad(node1 != node2);
369
370 flst_write_addr(node1 + FLST_NEXT, node3_addr, mtr);
371 } else {
372 /* node2 was first in list: update first field in base */
373 flst_write_addr(base + FLST_FIRST, node3_addr, mtr);
374 }
375
376 if (!fil_addr_is_null(node3_addr)) {
377 /* Update prev field of node3 */
378
379 if (node3_addr.page == node2_addr.page) {
380
381 node3 = page_align(node2) + node3_addr.boffset;
382 } else {
383 node3 = fut_get_ptr(space, page_size,
384 node3_addr, RW_SX_LATCH, mtr);
385 }
386
387 ut_ad(node2 != node3);
388
389 flst_write_addr(node3 + FLST_PREV, node1_addr, mtr);
390 } else {
391 /* node2 was last in list: update last field in base */
392 flst_write_addr(base + FLST_LAST, node1_addr, mtr);
393 }
394
395 /* Update len of base node */
396 len = flst_get_len(base);
397 ut_ad(len > 0);
398
399 mlog_write_ulint(base + FLST_LEN, len - 1, MLOG_4BYTES, mtr);
400}
401
402/********************************************************************//**
403Validates a file-based list.
404@return TRUE if ok */
405ibool
406flst_validate(
407/*==========*/
408 const flst_base_node_t* base, /*!< in: pointer to base node of list */
409 mtr_t* mtr1) /*!< in: mtr */
410{
411 ulint space;
412 const flst_node_t* node;
413 fil_addr_t node_addr;
414 fil_addr_t base_addr;
415 ulint len;
416 ulint i;
417 mtr_t mtr2;
418
419 ut_ad(base);
420 ut_ad(mtr_memo_contains_page_flagged(mtr1, base,
421 MTR_MEMO_PAGE_X_FIX
422 | MTR_MEMO_PAGE_SX_FIX));
423
424 /* We use two mini-transaction handles: the first is used to
425 lock the base node, and prevent other threads from modifying the
426 list. The second is used to traverse the list. We cannot run the
427 second mtr without committing it at times, because if the list
428 is long, then the x-locked pages could fill the buffer resulting
429 in a deadlock. */
430
431 /* Find out the space id */
432 buf_ptr_get_fsp_addr(base, &space, &base_addr);
433
434 bool found;
435 const page_size_t& page_size = fil_space_get_page_size(space,
436 &found);
437
438 ut_ad(found);
439
440 len = flst_get_len(base);
441 node_addr = flst_get_first(base, mtr1);
442
443 for (i = 0; i < len; i++) {
444 mtr_start(&mtr2);
445
446 node = fut_get_ptr(space, page_size,
447 node_addr, RW_SX_LATCH, &mtr2);
448 node_addr = flst_get_next_addr(node, &mtr2);
449
450 mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer
451 becoming full */
452 }
453
454 ut_a(fil_addr_is_null(node_addr));
455
456 node_addr = flst_get_last(base, mtr1);
457
458 for (i = 0; i < len; i++) {
459 mtr_start(&mtr2);
460
461 node = fut_get_ptr(space, page_size,
462 node_addr, RW_SX_LATCH, &mtr2);
463 node_addr = flst_get_prev_addr(node, &mtr2);
464
465 mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer
466 becoming full */
467 }
468
469 ut_a(fil_addr_is_null(node_addr));
470
471 return(TRUE);
472}
473