drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
fut0lst.cc
1/*****************************************************************************
2
3Copyright (C) 1995, 2009, Innobase Oy. 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., 51 Franklin
15St, Fifth Floor, Boston, MA 02110-1301 USA
16
17*****************************************************************************/
18
19/******************************************************************/
25
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/********************************************************************/
37static
38void
39flst_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/********************************************************************/
73UNIV_INTERN
74void
75flst_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/********************************************************************/
116UNIV_INTERN
117void
118flst_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/********************************************************************/
159UNIV_INTERN
160void
161flst_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/********************************************************************/
214UNIV_INTERN
215void
216flst_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/********************************************************************/
268UNIV_INTERN
269void
270flst_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/********************************************************************/
345UNIV_INTERN
346void
347flst_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/********************************************************************/
402UNIV_INTERN
403void
404flst_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/********************************************************************/
442UNIV_INTERN
443ibool
444flst_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/********************************************************************/
508UNIV_INTERN
509void
510flst_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}
UNIV_INLINE void buf_ptr_get_fsp_addr(const void *ptr, ulint *space, fil_addr_t *addr)
byte buf_frame_t
Definition buf0types.h:44
struct fil_addr_struct fil_addr_t
Definition fil0fil.h:64
UNIV_INLINE byte * fut_get_ptr(ulint space, ulint zip_size, fil_addr_t addr, ulint rw_latch, mtr_t *mtr)
UNIV_INLINE fil_addr_t flst_get_first(const flst_base_node_t *base, mtr_t *mtr)
UNIV_INLINE fil_addr_t flst_get_prev_addr(const flst_node_t *node, mtr_t *mtr)
UNIV_INLINE void flst_write_addr(fil_faddr_t *faddr, fil_addr_t addr, mtr_t *mtr)
UNIV_INLINE fil_addr_t flst_get_next_addr(const flst_node_t *node, mtr_t *mtr)
UNIV_INLINE fil_addr_t flst_get_last(const flst_base_node_t *base, mtr_t *mtr)
UNIV_INLINE ulint flst_get_len(const flst_base_node_t *base, mtr_t *mtr)
UNIV_INTERN void mlog_write_ulint(byte *ptr, ulint val, byte type, mtr_t *mtr)
Definition mtr0log.cc:247
UNIV_INTERN void mtr_commit(mtr_t *mtr) __attribute__((nonnull))
Definition mtr0mtr.cc:247
UNIV_INLINE void mtr_start(mtr_t *mtr) __attribute__((nonnull))
#define MLOG_4BYTES
Definition mtr0mtr.h:68
UNIV_INLINE ulint page_get_space_id(const page_t *page)
UNIV_INLINE ulint page_offset(const void *ptr) __attribute__((const))
UNIV_INLINE ulint page_get_page_no(const page_t *page)
UNIV_INLINE page_t * page_align(const void *ptr) __attribute__((const))
ulint boffset
Definition fil0fil.h:68
#define ut_ad(EXPR)
Definition ut0dbg.h:127
#define ut_a(EXPR)
Definition ut0dbg.h:105