release/src/router/mysql/storage/innobase/btr/btr0pcur.c

   1 /******************************************************
   2 The index tree persistent cursor
   3
   4 (c) 1996 Innobase Oy
   5
   6 Created 2/23/1996 Heikki Tuuri
   7 *******************************************************/
   8
   9 #include "btr0pcur.h"
  10
  11 #ifdef UNIV_NONINL
  12 #include "btr0pcur.ic"
  13 #endif
  14
  15 #include "ut0byte.h"
  16 #include "rem0cmp.h"
  17 #include "trx0trx.h"
  18
  19 /******************************************************************
  20 Allocates memory for a persistent cursor object and initializes the cursor. */
  21
  22 btr_pcur_t*
  23 btr_pcur_create_for_mysql(void)
  24 /*============================*/
  25                                 /* out, own: persistent cursor */
  26 {
  27         btr_pcur_t*     pcur;
  28
  29         pcur = mem_alloc(sizeof(btr_pcur_t));
  30
  31         pcur->btr_cur.index = NULL;
  32         btr_pcur_init(pcur);
  33
  34         return(pcur);
  35 }
  36
  37 /******************************************************************
  38 Frees the memory for a persistent cursor object. */
  39
  40 void
  41 btr_pcur_free_for_mysql(
  42 /*====================*/
  43         btr_pcur_t*     cursor) /* in, own: persistent cursor */
  44 {
  45         if (cursor->old_rec_buf != NULL) {
  46
  47                 mem_free(cursor->old_rec_buf);
  48
  49                 cursor->old_rec_buf = NULL;
  50         }
  51
  52         cursor->btr_cur.page_cur.rec = NULL;
  53         cursor->old_rec = NULL;
  54         cursor->old_n_fields = 0;
  55         cursor->old_stored = BTR_PCUR_OLD_NOT_STORED;
  56
  57         cursor->latch_mode = BTR_NO_LATCHES;
  58         cursor->pos_state = BTR_PCUR_NOT_POSITIONED;
  59
  60         mem_free(cursor);
  61 }
  62
  63 /******************************************************************
  64 The position of the cursor is stored by taking an initial segment of the
  65 record the cursor is positioned on, before, or after, and copying it to the
  66 cursor data structure, or just setting a flag if the cursor id before the
  67 first in an EMPTY tree, or after the last in an EMPTY tree. NOTE that the
  68 page where the cursor is positioned must not be empty if the index tree is
  69 not totally empty! */
  70
  71 void
  72 btr_pcur_store_position(
  73 /*====================*/
  74         btr_pcur_t*     cursor, /* in: persistent cursor */
  75         mtr_t*          mtr)    /* in: mtr */
  76 {
  77         page_cur_t*     page_cursor;
  78         rec_t*          rec;
  79         dict_index_t*   index;
  80         page_t*         page;
  81         ulint           offs;
  82
  83         ut_a(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
  84         ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
  85
  86         index = btr_cur_get_index(btr_pcur_get_btr_cur(cursor));
  87
  88         page_cursor = btr_pcur_get_page_cur(cursor);
  89
  90         rec = page_cur_get_rec(page_cursor);
  91         page = page_align(rec);
  92         offs = page_offset(rec);
  93
  94         ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  95                                 MTR_MEMO_PAGE_S_FIX)
  96               || mtr_memo_contains(mtr, buf_block_align(page),
  97                                    MTR_MEMO_PAGE_X_FIX));
  98         ut_a(cursor->latch_mode != BTR_NO_LATCHES);
  99
 100         if (UNIV_UNLIKELY(page_get_n_recs(page) == 0)) {
 101                 /* It must be an empty index tree; NOTE that in this case
 102                 we do not store the modify_clock, but always do a search
 103                 if we restore the cursor position */
 104
 105                 ut_a(btr_page_get_next(page, mtr) == FIL_NULL);
 106                 ut_a(btr_page_get_prev(page, mtr) == FIL_NULL);
 107
 108                 cursor->old_stored = BTR_PCUR_OLD_STORED;
 109
 110                 if (page_rec_is_supremum_low(offs)) {
 111
 112                         cursor->rel_pos = BTR_PCUR_AFTER_LAST_IN_TREE;
 113                 } else {
 114                         cursor->rel_pos = BTR_PCUR_BEFORE_FIRST_IN_TREE;
 115                 }
 116
 117                 return;
 118         }
 119
 120         if (page_rec_is_supremum_low(offs)) {
 121
 122                 rec = page_rec_get_prev(rec);
 123
 124                 cursor->rel_pos = BTR_PCUR_AFTER;
 125
 126         } else if (page_rec_is_infimum_low(offs)) {
 127
 128                 rec = page_rec_get_next(rec);
 129
 130                 cursor->rel_pos = BTR_PCUR_BEFORE;
 131         } else {
 132                 cursor->rel_pos = BTR_PCUR_ON;
 133         }
 134
 135         cursor->old_stored = BTR_PCUR_OLD_STORED;
 136         cursor->old_rec = dict_index_copy_rec_order_prefix(
 137                 index, rec, &cursor->old_n_fields,
 138                 &cursor->old_rec_buf, &cursor->buf_size);
 139
 140         cursor->block_when_stored = buf_block_align(page);
 141         cursor->modify_clock = buf_block_get_modify_clock(
 142                 cursor->block_when_stored);
 143 }
 144
 145 /******************************************************************
 146 Copies the stored position of a pcur to another pcur. */
 147
 148 void
 149 btr_pcur_copy_stored_position(
 150 /*==========================*/
 151         btr_pcur_t*     pcur_receive,   /* in: pcur which will receive the
 152                                         position info */
 153         btr_pcur_t*     pcur_donate)    /* in: pcur from which the info is
 154                                         copied */
 155 {
 156         if (pcur_receive->old_rec_buf) {
 157                 mem_free(pcur_receive->old_rec_buf);
 158         }
 159
 160         ut_memcpy(pcur_receive, pcur_donate, sizeof(btr_pcur_t));
 161
 162         if (pcur_donate->old_rec_buf) {
 163
 164                 pcur_receive->old_rec_buf = mem_alloc(pcur_donate->buf_size);
 165
 166                 ut_memcpy(pcur_receive->old_rec_buf, pcur_donate->old_rec_buf,
 167                           pcur_donate->buf_size);
 168                 pcur_receive->old_rec = pcur_receive->old_rec_buf
 169                         + (pcur_donate->old_rec - pcur_donate->old_rec_buf);
 170         }
 171
 172         pcur_receive->old_n_fields = pcur_donate->old_n_fields;
 173 }
 174
 175 /******************************************************************
 176 Restores the stored position of a persistent cursor bufferfixing the page and
 177 obtaining the specified latches. If the cursor position was saved when the
 178 (1) cursor was positioned on a user record: this function restores the position
 179 to the last record LESS OR EQUAL to the stored record;
 180 (2) cursor was positioned on a page infimum record: restores the position to
 181 the last record LESS than the user record which was the successor of the page
 182 infimum;
 183 (3) cursor was positioned on the page supremum: restores to the first record
 184 GREATER than the user record which was the predecessor of the supremum.
 185 (4) cursor was positioned before the first or after the last in an empty tree:
 186 restores to before first or after the last in the tree. */
 187
 188 ibool
 189 btr_pcur_restore_position(
 190 /*======================*/
 191                                         /* out: TRUE if the cursor position
 192                                         was stored when it was on a user record
 193                                         and it can be restored on a user record
 194                                         whose ordering fields are identical to
 195                                         the ones of the original user record */
 196         ulint           latch_mode,     /* in: BTR_SEARCH_LEAF, ... */
 197         btr_pcur_t*     cursor,         /* in: detached persistent cursor */
 198         mtr_t*          mtr)            /* in: mtr */
 199 {
 200         dict_index_t*   index;
 201         page_t*         page;
 202         dtuple_t*       tuple;
 203         ulint           mode;
 204         ulint           old_mode;
 205         mem_heap_t*     heap;
 206
 207         index = btr_cur_get_index(btr_pcur_get_btr_cur(cursor));
 208
 209         if (UNIV_UNLIKELY(cursor->old_stored != BTR_PCUR_OLD_STORED)
 210             || UNIV_UNLIKELY(cursor->pos_state != BTR_PCUR_WAS_POSITIONED
 211                              && cursor->pos_state != BTR_PCUR_IS_POSITIONED)) {
 212                 ut_print_buf(stderr, cursor, sizeof(btr_pcur_t));
 213                 if (cursor->trx_if_known) {
 214                         trx_print(stderr, cursor->trx_if_known, 0);
 215                 }
 216
 217                 ut_error;
 218         }
 219
 220         if (UNIV_UNLIKELY(
 221                     cursor->rel_pos == BTR_PCUR_AFTER_LAST_IN_TREE
 222                     || cursor->rel_pos == BTR_PCUR_BEFORE_FIRST_IN_TREE)) {
 223
 224                 /* In these cases we do not try an optimistic restoration,
 225                 but always do a search */
 226
 227                 btr_cur_open_at_index_side(
 228                         cursor->rel_pos == BTR_PCUR_BEFORE_FIRST_IN_TREE,
 229                         index, latch_mode, btr_pcur_get_btr_cur(cursor), mtr);
 230
 231                 cursor->block_when_stored
 232                         = buf_block_align(btr_pcur_get_page(cursor));
 233
 234                 return(FALSE);
 235         }
 236
 237         ut_a(cursor->old_rec);
 238         ut_a(cursor->old_n_fields);
 239
 240         page = btr_cur_get_page(btr_pcur_get_btr_cur(cursor));
 241
 242         if (UNIV_LIKELY(latch_mode == BTR_SEARCH_LEAF)
 243             || UNIV_LIKELY(latch_mode == BTR_MODIFY_LEAF)) {
 244                 /* Try optimistic restoration */
 245
 246                 if (UNIV_LIKELY(buf_page_optimistic_get(
 247                                         latch_mode,
 248                                         cursor->block_when_stored, page,
 249                                         cursor->modify_clock, mtr))) {
 250                         cursor->pos_state = BTR_PCUR_IS_POSITIONED;
 251 #ifdef UNIV_SYNC_DEBUG
 252                         buf_page_dbg_add_level(page, SYNC_TREE_NODE);
 253 #endif /* UNIV_SYNC_DEBUG */
 254                         if (cursor->rel_pos == BTR_PCUR_ON) {
 255 #ifdef UNIV_DEBUG
 256                                 rec_t*          rec;
 257                                 ulint*          offsets1;
 258                                 ulint*          offsets2;
 259 #endif /* UNIV_DEBUG */
 260                                 cursor->latch_mode = latch_mode;
 261 #ifdef UNIV_DEBUG
 262                                 rec = btr_pcur_get_rec(cursor);
 263
 264                                 heap = mem_heap_create(256);
 265                                 offsets1 = rec_get_offsets(
 266                                         cursor->old_rec, index, NULL,
 267                                         cursor->old_n_fields, &heap);
 268                                 offsets2 = rec_get_offsets(
 269                                         rec, index, NULL,
 270                                         cursor->old_n_fields, &heap);
 271
 272                                 ut_ad(!cmp_rec_rec(cursor->old_rec,
 273                                                    rec, offsets1, offsets2,
 274                                                    index));
 275                                 mem_heap_free(heap);
 276 #endif /* UNIV_DEBUG */
 277                                 return(TRUE);
 278                         }
 279
 280                         return(FALSE);
 281                 }
 282         }
 283
 284         /* If optimistic restoration did not succeed, open the cursor anew */
 285
 286         heap = mem_heap_create(256);
 287
 288         tuple = dict_index_build_data_tuple(index, cursor->old_rec,
 289                                             cursor->old_n_fields, heap);
 290
 291         /* Save the old search mode of the cursor */
 292         old_mode = cursor->search_mode;
 293
 294         switch (cursor->rel_pos) {
 295         case BTR_PCUR_ON:
 296                 mode = PAGE_CUR_LE;
 297                 break;
 298         case BTR_PCUR_AFTER:
 299                 mode = PAGE_CUR_G;
 300                 break;
 301         case BTR_PCUR_BEFORE:
 302                 mode = PAGE_CUR_L;
 303                 break;
 304         default:
 305                 ut_error;
 306                 mode = 0; /* silence a warning */
 307         }
 308
 309         btr_pcur_open_with_no_init(index, tuple, mode, latch_mode,
 310                                    cursor, 0, mtr);
 311
 312         /* Restore the old search mode */
 313         cursor->search_mode = old_mode;
 314
 315         switch (cursor->rel_pos) {
 316         case BTR_PCUR_ON:
 317                 if (btr_pcur_is_on_user_rec(cursor, mtr)
 318                     && !cmp_dtuple_rec(
 319                             tuple, btr_pcur_get_rec(cursor),
 320                             rec_get_offsets(btr_pcur_get_rec(cursor),
 321                                             index, NULL,
 322                                             ULINT_UNDEFINED, &heap))) {
 323
 324                         /* We have to store the NEW value for
 325                         the modify clock, since the cursor can
 326                         now be on a different page! But we can
 327                         retain the value of old_rec */
 328
 329                         cursor->block_when_stored =
 330                                 buf_block_align(
 331                                         btr_pcur_get_page(cursor));
 332                         cursor->modify_clock =
 333                                 buf_block_get_modify_clock(
 334                                         cursor->block_when_stored);
 335                         cursor->old_stored = BTR_PCUR_OLD_STORED;
 336
 337                         mem_heap_free(heap);
 338
 339                         return(TRUE);
 340                 }
 341 #ifdef UNIV_DEBUG
 342                 /* fall through */
 343         case BTR_PCUR_BEFORE:
 344         case BTR_PCUR_AFTER:
 345                 break;
 346         default:
 347                 ut_error;
 348 #endif /* UNIV_DEBUG */
 349         }
 350
 351         mem_heap_free(heap);
 352
 353         /* We have to store new position information, modify_clock etc.,
 354         to the cursor because it can now be on a different page, the record
 355         under it may have been removed, etc. */
 356
 357         btr_pcur_store_position(cursor, mtr);
 358
 359         return(FALSE);
 360 }
 361
 362 /*************************************************************
 363 Moves the persistent cursor to the first record on the next page. Releases the
 364 latch on the current page, and bufferunfixes it. Note that there must not be
 365 modifications on the current page, as then the x-latch can be released only in
 366 mtr_commit. */
 367
 368 void
 369 btr_pcur_move_to_next_page(
 370 /*=======================*/
 371         btr_pcur_t*     cursor, /* in: persistent cursor; must be on the
 372                                 last record of the current page */
 373         mtr_t*          mtr)    /* in: mtr */
 374 {
 375         ulint   next_page_no;
 376         ulint   space;
 377         page_t* page;
 378         page_t* next_page;
 379
 380         ut_a(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
 381         ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
 382         ut_ad(btr_pcur_is_after_last_on_page(cursor, mtr));
 383
 384         cursor->old_stored = BTR_PCUR_OLD_NOT_STORED;
 385
 386         page = btr_pcur_get_page(cursor);
 387
 388         next_page_no = btr_page_get_next(page, mtr);
 389         space = buf_frame_get_space_id(page);
 390
 391         ut_ad(next_page_no != FIL_NULL);
 392
 393         next_page = btr_page_get(space, next_page_no, cursor->latch_mode, mtr);
 394 #ifdef UNIV_BTR_DEBUG
 395         ut_a(btr_page_get_prev(next_page, mtr) == buf_frame_get_page_no(page));
 396 #endif /* UNIV_BTR_DEBUG */
 397         ut_a(page_is_comp(next_page) == page_is_comp(page));
 398         buf_block_align(next_page)->check_index_page_at_flush = TRUE;
 399
 400         btr_leaf_page_release(page, cursor->latch_mode, mtr);
 401
 402         page_cur_set_before_first(next_page, btr_pcur_get_page_cur(cursor));
 403
 404         page_check_dir(next_page);
 405 }
 406
 407 /*************************************************************
 408 Moves the persistent cursor backward if it is on the first record of the page.
 409 Commits mtr. Note that to prevent a possible deadlock, the operation
 410 first stores the position of the cursor, commits mtr, acquires the necessary
 411 latches and restores the cursor position again before returning. The
 412 alphabetical position of the cursor is guaranteed to be sensible on
 413 return, but it may happen that the cursor is not positioned on the last
 414 record of any page, because the structure of the tree may have changed
 415 during the time when the cursor had no latches. */
 416
 417 void
 418 btr_pcur_move_backward_from_page(
 419 /*=============================*/
 420         btr_pcur_t*     cursor, /* in: persistent cursor, must be on the first
 421                                 record of the current page */
 422         mtr_t*          mtr)    /* in: mtr */
 423 {
 424         ulint   prev_page_no;
 425         page_t* page;
 426         page_t* prev_page;
 427         ulint   latch_mode;
 428         ulint   latch_mode2;
 429
 430         ut_a(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
 431         ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
 432         ut_ad(btr_pcur_is_before_first_on_page(cursor, mtr));
 433         ut_ad(!btr_pcur_is_before_first_in_tree(cursor, mtr));
 434
 435         latch_mode = cursor->latch_mode;
 436
 437         if (latch_mode == BTR_SEARCH_LEAF) {
 438
 439                 latch_mode2 = BTR_SEARCH_PREV;
 440
 441         } else if (latch_mode == BTR_MODIFY_LEAF) {
 442
 443                 latch_mode2 = BTR_MODIFY_PREV;
 444         } else {
 445                 latch_mode2 = 0; /* To eliminate compiler warning */
 446                 ut_error;
 447         }
 448
 449         btr_pcur_store_position(cursor, mtr);
 450
 451         mtr_commit(mtr);
 452
 453         mtr_start(mtr);
 454
 455         btr_pcur_restore_position(latch_mode2, cursor, mtr);
 456
 457         page = btr_pcur_get_page(cursor);
 458
 459         prev_page_no = btr_page_get_prev(page, mtr);
 460
 461         if (btr_pcur_is_before_first_on_page(cursor, mtr)
 462             && (prev_page_no != FIL_NULL)) {
 463
 464                 prev_page = btr_pcur_get_btr_cur(cursor)->left_page;
 465
 466                 btr_leaf_page_release(page, latch_mode, mtr);
 467
 468                 page_cur_set_after_last(prev_page,
 469                                         btr_pcur_get_page_cur(cursor));
 470         } else if (prev_page_no != FIL_NULL) {
 471
 472                 /* The repositioned cursor did not end on an infimum record on
 473                 a page. Cursor repositioning acquired a latch also on the
 474                 previous page, but we do not need the latch: release it. */
 475
 476                 prev_page = btr_pcur_get_btr_cur(cursor)->left_page;
 477
 478                 btr_leaf_page_release(prev_page, latch_mode, mtr);
 479         }
 480
 481         cursor->latch_mode = latch_mode;
 482
 483         cursor->old_stored = BTR_PCUR_OLD_NOT_STORED;
 484 }
 485
 486 /*************************************************************
 487 Moves the persistent cursor to the previous record in the tree. If no records
 488 are left, the cursor stays 'before first in tree'. */
 489
 490 ibool
 491 btr_pcur_move_to_prev(
 492 /*==================*/
 493                                 /* out: TRUE if the cursor was not before first
 494                                 in tree */
 495         btr_pcur_t*     cursor, /* in: persistent cursor; NOTE that the
 496                                 function may release the page latch */
 497         mtr_t*          mtr)    /* in: mtr */
 498 {
 499         ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
 500         ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
 501
 502         cursor->old_stored = BTR_PCUR_OLD_NOT_STORED;
 503
 504         if (btr_pcur_is_before_first_on_page(cursor, mtr)) {
 505
 506                 if (btr_pcur_is_before_first_in_tree(cursor, mtr)) {
 507
 508                         return(FALSE);
 509                 }
 510
 511                 btr_pcur_move_backward_from_page(cursor, mtr);
 512
 513                 return(TRUE);
 514         }
 515
 516         btr_pcur_move_to_prev_on_page(cursor, mtr);
 517
 518         return(TRUE);
 519 }
 520
 521 /******************************************************************
 522 If mode is PAGE_CUR_G or PAGE_CUR_GE, opens a persistent cursor on the first
 523 user record satisfying the search condition, in the case PAGE_CUR_L or
 524 PAGE_CUR_LE, on the last user record. If no such user record exists, then
 525 in the first case sets the cursor after last in tree, and in the latter case
 526 before first in tree. The latching mode must be BTR_SEARCH_LEAF or
 527 BTR_MODIFY_LEAF. */
 528
 529 void
 530 btr_pcur_open_on_user_rec(
 531 /*======================*/
 532         dict_index_t*   index,          /* in: index */
 533         dtuple_t*       tuple,          /* in: tuple on which search done */
 534         ulint           mode,           /* in: PAGE_CUR_L, ... */
 535         ulint           latch_mode,     /* in: BTR_SEARCH_LEAF or
 536                                         BTR_MODIFY_LEAF */
 537         btr_pcur_t*     cursor,         /* in: memory buffer for persistent
 538                                         cursor */
 539         mtr_t*          mtr)            /* in: mtr */
 540 {
 541         btr_pcur_open(index, tuple, mode, latch_mode, cursor, mtr);
 542
 543         if ((mode == PAGE_CUR_GE) || (mode == PAGE_CUR_G)) {
 544
 545                 if (btr_pcur_is_after_last_on_page(cursor, mtr)) {
 546
 547                         btr_pcur_move_to_next_user_rec(cursor, mtr);
 548                 }
 549         } else {
 550                 ut_ad((mode == PAGE_CUR_LE) || (mode == PAGE_CUR_L));
 551
 552                 /* Not implemented yet */
 553
 554                 ut_error;
 555         }
 556 }