1/*****************************************************************************
2
3Copyright (c) 1996, 2016, Oracle and/or its affiliates. All Rights Reserved.
4Copyright (c) 2016, 2017, MariaDB Corporation.
5
6This program is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free Software
8Foundation; version 2 of the License.
9
10This program is distributed in the hope that it will be useful, but WITHOUT
11ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
14You should have received a copy of the GNU General Public License along with
15this program; if not, write to the Free Software Foundation, Inc.,
1651 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
17
18*****************************************************************************/
19
20/**************************************************//**
21@file btr/btr0pcur.cc
22The index tree persistent cursor
23
24Created 2/23/1996 Heikki Tuuri
25*******************************************************/
26
27#include "btr0pcur.h"
28#include "ut0byte.h"
29#include "rem0cmp.h"
30#include "trx0trx.h"
31
32/**************************************************************//**
33Allocates memory for a persistent cursor object and initializes the cursor.
34@return own: persistent cursor */
35btr_pcur_t*
36btr_pcur_create_for_mysql(void)
37/*============================*/
38{
39 btr_pcur_t* pcur;
40 DBUG_ENTER("btr_pcur_create_for_mysql");
41
42 pcur = (btr_pcur_t*) ut_malloc_nokey(sizeof(btr_pcur_t));
43
44 pcur->btr_cur.index = NULL;
45 btr_pcur_init(pcur);
46
47 DBUG_PRINT("btr_pcur_create_for_mysql", ("pcur: %p", pcur));
48 DBUG_RETURN(pcur);
49}
50
51/**************************************************************//**
52Resets a persistent cursor object, freeing ::old_rec_buf if it is
53allocated and resetting the other members to their initial values. */
54void
55btr_pcur_reset(
56/*===========*/
57 btr_pcur_t* cursor) /*!< in, out: persistent cursor */
58{
59 btr_pcur_free(cursor);
60 cursor->old_rec_buf = NULL;
61 cursor->btr_cur.index = NULL;
62 cursor->btr_cur.page_cur.rec = NULL;
63 cursor->old_rec = NULL;
64 cursor->old_n_fields = 0;
65 cursor->old_stored = false;
66
67 cursor->latch_mode = BTR_NO_LATCHES;
68 cursor->pos_state = BTR_PCUR_NOT_POSITIONED;
69}
70
71/**************************************************************//**
72Frees the memory for a persistent cursor object. */
73void
74btr_pcur_free_for_mysql(
75/*====================*/
76 btr_pcur_t* cursor) /*!< in, own: persistent cursor */
77{
78 DBUG_ENTER("btr_pcur_free_for_mysql");
79 DBUG_PRINT("btr_pcur_free_for_mysql", ("pcur: %p", cursor));
80
81 btr_pcur_free(cursor);
82 ut_free(cursor);
83 DBUG_VOID_RETURN;
84}
85
86/**************************************************************//**
87The position of the cursor is stored by taking an initial segment of the
88record the cursor is positioned on, before, or after, and copying it to the
89cursor data structure, or just setting a flag if the cursor id before the
90first in an EMPTY tree, or after the last in an EMPTY tree. NOTE that the
91page where the cursor is positioned must not be empty if the index tree is
92not totally empty! */
93void
94btr_pcur_store_position(
95/*====================*/
96 btr_pcur_t* cursor, /*!< in: persistent cursor */
97 mtr_t* mtr) /*!< in: mtr */
98{
99 page_cur_t* page_cursor;
100 buf_block_t* block;
101 rec_t* rec;
102 dict_index_t* index;
103 page_t* page;
104 ulint offs;
105
106 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
107 ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
108
109 block = btr_pcur_get_block(cursor);
110 index = btr_cur_get_index(btr_pcur_get_btr_cur(cursor));
111
112 page_cursor = btr_pcur_get_page_cur(cursor);
113
114 rec = page_cur_get_rec(page_cursor);
115 page = page_align(rec);
116 offs = page_offset(rec);
117
118 ut_ad(block->page.buf_fix_count);
119 /* For spatial index, when we do positioning on parent
120 buffer if necessary, it might not hold latches, but the
121 tree must be locked to prevent change on the page */
122 ut_ad(mtr_memo_contains_flagged(mtr, block,
123 MTR_MEMO_PAGE_S_FIX
124 | MTR_MEMO_PAGE_X_FIX)
125 || (dict_index_is_spatial(index)
126 && mtr_memo_contains_flagged(
127 mtr, dict_index_get_lock(index),
128 MTR_MEMO_X_LOCK | MTR_MEMO_SX_LOCK)));
129
130 cursor->old_stored = true;
131
132 if (page_is_empty(page)) {
133 /* It must be an empty index tree; NOTE that in this case
134 we do not store the modify_clock, but always do a search
135 if we restore the cursor position */
136
137 ut_a(!page_has_siblings(page));
138 ut_ad(page_is_leaf(page));
139 ut_ad(page_get_page_no(page) == index->page);
140
141 if (page_rec_is_supremum_low(offs)) {
142 cursor->rel_pos = BTR_PCUR_AFTER_LAST_IN_TREE;
143 } else {
144 cursor->rel_pos = BTR_PCUR_BEFORE_FIRST_IN_TREE;
145 }
146
147 return;
148 }
149
150 if (page_rec_is_supremum_low(offs)) {
151 rec = page_rec_get_prev(rec);
152
153 ut_ad(!page_rec_is_infimum(rec));
154 ut_ad(!rec_is_default_row(rec, index));
155
156 cursor->rel_pos = BTR_PCUR_AFTER;
157 } else if (page_rec_is_infimum_low(offs)) {
158 rec = page_rec_get_next(rec);
159
160 if (rec_is_default_row(rec, index)) {
161 rec = page_rec_get_next(rec);
162 ut_ad(!page_rec_is_supremum(rec));
163 }
164
165 cursor->rel_pos = BTR_PCUR_BEFORE;
166 } else {
167 cursor->rel_pos = BTR_PCUR_ON;
168 }
169
170 cursor->old_rec = dict_index_copy_rec_order_prefix(
171 index, rec, &cursor->old_n_fields,
172 &cursor->old_rec_buf, &cursor->buf_size);
173
174 cursor->block_when_stored = block;
175
176 /* Function try to check if block is S/X latch. */
177 cursor->modify_clock = buf_block_get_modify_clock(block);
178 cursor->withdraw_clock = buf_withdraw_clock;
179}
180
181/**************************************************************//**
182Copies the stored position of a pcur to another pcur. */
183void
184btr_pcur_copy_stored_position(
185/*==========================*/
186 btr_pcur_t* pcur_receive, /*!< in: pcur which will receive the
187 position info */
188 btr_pcur_t* pcur_donate) /*!< in: pcur from which the info is
189 copied */
190{
191 ut_free(pcur_receive->old_rec_buf);
192 ut_memcpy(pcur_receive, pcur_donate, sizeof(btr_pcur_t));
193
194 if (pcur_donate->old_rec_buf) {
195
196 pcur_receive->old_rec_buf = (byte*)
197 ut_malloc_nokey(pcur_donate->buf_size);
198
199 ut_memcpy(pcur_receive->old_rec_buf, pcur_donate->old_rec_buf,
200 pcur_donate->buf_size);
201 pcur_receive->old_rec = pcur_receive->old_rec_buf
202 + (pcur_donate->old_rec - pcur_donate->old_rec_buf);
203 }
204
205 pcur_receive->old_n_fields = pcur_donate->old_n_fields;
206}
207
208/**************************************************************//**
209Restores the stored position of a persistent cursor bufferfixing the page and
210obtaining the specified latches. If the cursor position was saved when the
211(1) cursor was positioned on a user record: this function restores the position
212to the last record LESS OR EQUAL to the stored record;
213(2) cursor was positioned on a page infimum record: restores the position to
214the last record LESS than the user record which was the successor of the page
215infimum;
216(3) cursor was positioned on the page supremum: restores to the first record
217GREATER than the user record which was the predecessor of the supremum.
218(4) cursor was positioned before the first or after the last in an empty tree:
219restores to before first or after the last in the tree.
220@return TRUE if the cursor position was stored when it was on a user
221record and it can be restored on a user record whose ordering fields
222are identical to the ones of the original user record */
223ibool
224btr_pcur_restore_position_func(
225/*===========================*/
226 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF, ... */
227 btr_pcur_t* cursor, /*!< in: detached persistent cursor */
228 const char* file, /*!< in: file name */
229 unsigned line, /*!< in: line where called */
230 mtr_t* mtr) /*!< in: mtr */
231{
232 dict_index_t* index;
233 dtuple_t* tuple;
234 page_cur_mode_t mode;
235 page_cur_mode_t old_mode;
236 mem_heap_t* heap;
237
238 ut_ad(mtr->is_active());
239 //ut_ad(cursor->old_stored);
240 ut_ad(cursor->pos_state == BTR_PCUR_WAS_POSITIONED
241 || cursor->pos_state == BTR_PCUR_IS_POSITIONED);
242
243 index = btr_cur_get_index(btr_pcur_get_btr_cur(cursor));
244
245 if (UNIV_UNLIKELY
246 (cursor->rel_pos == BTR_PCUR_AFTER_LAST_IN_TREE
247 || cursor->rel_pos == BTR_PCUR_BEFORE_FIRST_IN_TREE)) {
248 dberr_t err = DB_SUCCESS;
249
250 /* In these cases we do not try an optimistic restoration,
251 but always do a search */
252
253 err = btr_cur_open_at_index_side(
254 cursor->rel_pos == BTR_PCUR_BEFORE_FIRST_IN_TREE,
255 index, latch_mode,
256 btr_pcur_get_btr_cur(cursor), 0, mtr);
257
258 if (err != DB_SUCCESS) {
259 ib::warn() << " Error code: " << err
260 << " btr_pcur_restore_position_func "
261 << " called from file: "
262 << file << " line: " << line
263 << " table: " << index->table->name
264 << " index: " << index->name;
265 }
266
267 cursor->latch_mode =
268 BTR_LATCH_MODE_WITHOUT_INTENTION(latch_mode);
269 cursor->pos_state = BTR_PCUR_IS_POSITIONED;
270 cursor->block_when_stored = btr_pcur_get_block(cursor);
271
272 return(FALSE);
273 }
274
275 ut_a(cursor->old_rec);
276 ut_a(cursor->old_n_fields);
277
278 switch (latch_mode) {
279 case BTR_SEARCH_LEAF:
280 case BTR_MODIFY_LEAF:
281 case BTR_SEARCH_PREV:
282 case BTR_MODIFY_PREV:
283 /* Try optimistic restoration. */
284
285 if (!buf_pool_is_obsolete(cursor->withdraw_clock)
286 && btr_cur_optimistic_latch_leaves(
287 cursor->block_when_stored, cursor->modify_clock,
288 &latch_mode, btr_pcur_get_btr_cur(cursor),
289 file, line, mtr)) {
290
291 cursor->pos_state = BTR_PCUR_IS_POSITIONED;
292 cursor->latch_mode = latch_mode;
293
294 buf_block_dbg_add_level(
295 btr_pcur_get_block(cursor),
296 dict_index_is_ibuf(index)
297 ? SYNC_IBUF_TREE_NODE : SYNC_TREE_NODE);
298
299 if (cursor->rel_pos == BTR_PCUR_ON) {
300#ifdef UNIV_DEBUG
301 const rec_t* rec;
302 const ulint* offsets1;
303 const ulint* offsets2;
304 rec = btr_pcur_get_rec(cursor);
305
306 heap = mem_heap_create(256);
307 offsets1 = rec_get_offsets(
308 cursor->old_rec, index, NULL, true,
309 cursor->old_n_fields, &heap);
310 offsets2 = rec_get_offsets(
311 rec, index, NULL, true,
312 cursor->old_n_fields, &heap);
313
314 ut_ad(!cmp_rec_rec(cursor->old_rec,
315 rec, offsets1, offsets2,
316 index));
317 mem_heap_free(heap);
318#endif /* UNIV_DEBUG */
319 return(TRUE);
320 }
321 /* This is the same record as stored,
322 may need to be adjusted for BTR_PCUR_BEFORE/AFTER,
323 depending on search mode and direction. */
324 if (btr_pcur_is_on_user_rec(cursor)) {
325 cursor->pos_state
326 = BTR_PCUR_IS_POSITIONED_OPTIMISTIC;
327 }
328 return(FALSE);
329 }
330 }
331
332 /* If optimistic restoration did not succeed, open the cursor anew */
333
334 heap = mem_heap_create(256);
335
336 tuple = dict_index_build_data_tuple(cursor->old_rec, index, true,
337 cursor->old_n_fields, heap);
338
339 /* Save the old search mode of the cursor */
340 old_mode = cursor->search_mode;
341
342 switch (cursor->rel_pos) {
343 case BTR_PCUR_ON:
344 mode = PAGE_CUR_LE;
345 break;
346 case BTR_PCUR_AFTER:
347 mode = PAGE_CUR_G;
348 break;
349 case BTR_PCUR_BEFORE:
350 mode = PAGE_CUR_L;
351 break;
352 default:
353 ut_error;
354 mode = PAGE_CUR_UNSUPP;
355 }
356
357 btr_pcur_open_with_no_init_func(index, tuple, mode, latch_mode,
358 cursor,
359#ifdef BTR_CUR_HASH_ADAPT
360 NULL,
361#endif /* BTR_CUR_HASH_ADAPT */
362 file, line, mtr);
363
364 /* Restore the old search mode */
365 cursor->search_mode = old_mode;
366
367 ut_ad(cursor->rel_pos == BTR_PCUR_ON
368 || cursor->rel_pos == BTR_PCUR_BEFORE
369 || cursor->rel_pos == BTR_PCUR_AFTER);
370 if (cursor->rel_pos == BTR_PCUR_ON
371 && btr_pcur_is_on_user_rec(cursor)
372 && !cmp_dtuple_rec(tuple, btr_pcur_get_rec(cursor),
373 rec_get_offsets(btr_pcur_get_rec(cursor),
374 index, NULL, true,
375 ULINT_UNDEFINED, &heap))) {
376
377 /* We have to store the NEW value for the modify clock,
378 since the cursor can now be on a different page!
379 But we can retain the value of old_rec */
380
381 cursor->block_when_stored = btr_pcur_get_block(cursor);
382 cursor->modify_clock = buf_block_get_modify_clock(
383 cursor->block_when_stored);
384 cursor->old_stored = true;
385 cursor->withdraw_clock = buf_withdraw_clock;
386
387 mem_heap_free(heap);
388
389 return(TRUE);
390 }
391
392 mem_heap_free(heap);
393
394 /* We have to store new position information, modify_clock etc.,
395 to the cursor because it can now be on a different page, the record
396 under it may have been removed, etc. */
397
398 btr_pcur_store_position(cursor, mtr);
399
400 return(FALSE);
401}
402
403/*********************************************************//**
404Moves the persistent cursor to the first record on the next page. Releases the
405latch on the current page, and bufferunfixes it. Note that there must not be
406modifications on the current page, as then the x-latch can be released only in
407mtr_commit. */
408void
409btr_pcur_move_to_next_page(
410/*=======================*/
411 btr_pcur_t* cursor, /*!< in: persistent cursor; must be on the
412 last record of the current page */
413 mtr_t* mtr) /*!< in: mtr */
414{
415 ulint next_page_no;
416 page_t* page;
417 buf_block_t* next_block;
418 page_t* next_page;
419 ulint mode;
420
421 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
422 ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
423 ut_ad(btr_pcur_is_after_last_on_page(cursor));
424
425 cursor->old_stored = false;
426
427 page = btr_pcur_get_page(cursor);
428
429 if (UNIV_UNLIKELY(!page)) {
430 return;
431 }
432
433 next_page_no = btr_page_get_next(page, mtr);
434
435 ut_ad(next_page_no != FIL_NULL);
436
437 mode = cursor->latch_mode;
438 switch (mode) {
439 case BTR_SEARCH_TREE:
440 mode = BTR_SEARCH_LEAF;
441 break;
442 case BTR_MODIFY_TREE:
443 mode = BTR_MODIFY_LEAF;
444 }
445
446 buf_block_t* block = btr_pcur_get_block(cursor);
447
448 next_block = btr_block_get(
449 page_id_t(block->page.id.space(), next_page_no),
450 block->page.size, mode,
451 btr_pcur_get_btr_cur(cursor)->index, mtr);
452
453 if (UNIV_UNLIKELY(!next_block)) {
454 return;
455 }
456
457 next_page = buf_block_get_frame(next_block);
458#ifdef UNIV_BTR_DEBUG
459 ut_a(page_is_comp(next_page) == page_is_comp(page));
460 ut_a(btr_page_get_prev(next_page, mtr)
461 == btr_pcur_get_block(cursor)->page.id.page_no());
462#endif /* UNIV_BTR_DEBUG */
463
464 btr_leaf_page_release(btr_pcur_get_block(cursor), mode, mtr);
465
466 page_cur_set_before_first(next_block, btr_pcur_get_page_cur(cursor));
467
468 ut_d(page_check_dir(next_page));
469}
470
471/*********************************************************//**
472Moves the persistent cursor backward if it is on the first record of the page.
473Commits mtr. Note that to prevent a possible deadlock, the operation
474first stores the position of the cursor, commits mtr, acquires the necessary
475latches and restores the cursor position again before returning. The
476alphabetical position of the cursor is guaranteed to be sensible on
477return, but it may happen that the cursor is not positioned on the last
478record of any page, because the structure of the tree may have changed
479during the time when the cursor had no latches. */
480static
481void
482btr_pcur_move_backward_from_page(
483/*=============================*/
484 btr_pcur_t* cursor, /*!< in: persistent cursor, must be on the first
485 record of the current page */
486 mtr_t* mtr) /*!< in: mtr */
487{
488 ulint prev_page_no;
489 page_t* page;
490 buf_block_t* prev_block;
491 ulint latch_mode;
492 ulint latch_mode2;
493
494 ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
495 ut_ad(btr_pcur_is_before_first_on_page(cursor));
496 ut_ad(!btr_pcur_is_before_first_in_tree(cursor));
497
498 latch_mode = cursor->latch_mode;
499
500 if (latch_mode == BTR_SEARCH_LEAF) {
501
502 latch_mode2 = BTR_SEARCH_PREV;
503
504 } else if (latch_mode == BTR_MODIFY_LEAF) {
505
506 latch_mode2 = BTR_MODIFY_PREV;
507 } else {
508 latch_mode2 = 0; /* To eliminate compiler warning */
509 ut_error;
510 }
511
512 btr_pcur_store_position(cursor, mtr);
513
514 mtr_commit(mtr);
515
516 mtr_start(mtr);
517
518 btr_pcur_restore_position(latch_mode2, cursor, mtr);
519
520 page = btr_pcur_get_page(cursor);
521
522 prev_page_no = btr_page_get_prev(page, mtr);
523
524 if (prev_page_no == FIL_NULL) {
525 } else if (btr_pcur_is_before_first_on_page(cursor)) {
526
527 prev_block = btr_pcur_get_btr_cur(cursor)->left_block;
528
529 btr_leaf_page_release(btr_pcur_get_block(cursor),
530 latch_mode, mtr);
531
532 page_cur_set_after_last(prev_block,
533 btr_pcur_get_page_cur(cursor));
534 } else {
535
536 /* The repositioned cursor did not end on an infimum
537 record on a page. Cursor repositioning acquired a latch
538 also on the previous page, but we do not need the latch:
539 release it. */
540
541 prev_block = btr_pcur_get_btr_cur(cursor)->left_block;
542
543 btr_leaf_page_release(prev_block, latch_mode, mtr);
544 }
545
546 cursor->latch_mode = latch_mode;
547 cursor->old_stored = false;
548}
549
550/*********************************************************//**
551Moves the persistent cursor to the previous record in the tree. If no records
552are left, the cursor stays 'before first in tree'.
553@return TRUE if the cursor was not before first in tree */
554ibool
555btr_pcur_move_to_prev(
556/*==================*/
557 btr_pcur_t* cursor, /*!< in: persistent cursor; NOTE that the
558 function may release the page latch */
559 mtr_t* mtr) /*!< in: mtr */
560{
561 ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
562 ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
563
564 cursor->old_stored = false;
565
566 if (btr_pcur_is_before_first_on_page(cursor)) {
567
568 if (btr_pcur_is_before_first_in_tree(cursor)) {
569
570 return(FALSE);
571 }
572
573 btr_pcur_move_backward_from_page(cursor, mtr);
574
575 return(TRUE);
576 }
577
578 btr_pcur_move_to_prev_on_page(cursor);
579
580 return(TRUE);
581}
582
583/**************************************************************//**
584If mode is PAGE_CUR_G or PAGE_CUR_GE, opens a persistent cursor on the first
585user record satisfying the search condition, in the case PAGE_CUR_L or
586PAGE_CUR_LE, on the last user record. If no such user record exists, then
587in the first case sets the cursor after last in tree, and in the latter case
588before first in tree. The latching mode must be BTR_SEARCH_LEAF or
589BTR_MODIFY_LEAF. */
590void
591btr_pcur_open_on_user_rec_func(
592/*===========================*/
593 dict_index_t* index, /*!< in: index */
594 const dtuple_t* tuple, /*!< in: tuple on which search done */
595 page_cur_mode_t mode, /*!< in: PAGE_CUR_L, ... */
596 ulint latch_mode, /*!< in: BTR_SEARCH_LEAF or
597 BTR_MODIFY_LEAF */
598 btr_pcur_t* cursor, /*!< in: memory buffer for persistent
599 cursor */
600 const char* file, /*!< in: file name */
601 unsigned line, /*!< in: line where called */
602 mtr_t* mtr) /*!< in: mtr */
603{
604 btr_pcur_open_low(index, 0, tuple, mode, latch_mode, cursor,
605 file, line, 0, mtr);
606
607 if ((mode == PAGE_CUR_GE) || (mode == PAGE_CUR_G)) {
608
609 if (btr_pcur_is_after_last_on_page(cursor)) {
610
611 btr_pcur_move_to_next_user_rec(cursor, mtr);
612 }
613 } else {
614 ut_ad((mode == PAGE_CUR_LE) || (mode == PAGE_CUR_L));
615
616 /* Not implemented yet */
617
618 ut_error;
619 }
620}
621