1/*****************************************************************************
2
3Copyright (c) 1996, 2021, Oracle and/or its affiliates.
4
5This program is free software; you can redistribute it and/or modify
6it under the terms of the GNU General Public License, version 2.0,
7as published by the Free Software Foundation.
8
9This program is also distributed with certain software (including
10but not limited to OpenSSL) that is licensed under separate terms,
11as designated in a particular file or component or in included license
12documentation.  The authors of MySQL hereby grant you an additional
13permission to link the program and your derivative works with the
14separately licensed software that they have included with MySQL.
15
16This program is distributed in the hope that it will be useful,
17but WITHOUT ANY WARRANTY; without even the implied warranty of
18MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19GNU General Public License, version 2.0, for more details.
20
21You should have received a copy of the GNU General Public License along with
22this program; if not, write to the Free Software Foundation, Inc.,
2351 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
24
25*****************************************************************************/
26
27/**************************************************//**
28@file include/btr0pcur.ic
29The index tree persistent cursor
30
31Created 2/23/1996 Heikki Tuuri
32*******************************************************/
33
34
35/*********************************************************//**
36Gets the rel_pos field for a cursor whose position has been stored.
37@return BTR_PCUR_ON, ... */
38UNIV_INLINE
39ulint
40btr_pcur_get_rel_pos(
41/*=================*/
42	const btr_pcur_t*	cursor)	/*!< in: persistent cursor */
43{
44	ut_ad(cursor);
45	ut_ad(cursor->old_rec);
46	ut_ad(cursor->old_stored);
47	ut_ad(cursor->pos_state == BTR_PCUR_WAS_POSITIONED
48	      || cursor->pos_state == BTR_PCUR_IS_POSITIONED);
49
50	return(cursor->rel_pos);
51}
52
53#ifdef UNIV_DEBUG
54/*********************************************************//**
55Returns the btr cursor component of a persistent cursor.
56@return pointer to btr cursor component */
57UNIV_INLINE
58btr_cur_t*
59btr_pcur_get_btr_cur(
60/*=================*/
61	const btr_pcur_t*	cursor)	/*!< in: persistent cursor */
62{
63	const btr_cur_t*	btr_cur = &cursor->btr_cur;
64	return((btr_cur_t*) btr_cur);
65}
66
67/*********************************************************//**
68Returns the page cursor component of a persistent cursor.
69@return pointer to page cursor component */
70UNIV_INLINE
71page_cur_t*
72btr_pcur_get_page_cur(
73/*==================*/
74	const btr_pcur_t*	cursor)	/*!< in: persistent cursor */
75{
76	return(btr_cur_get_page_cur(btr_pcur_get_btr_cur(cursor)));
77}
78
79/*********************************************************//**
80Returns the page of a persistent cursor.
81@return pointer to the page */
82UNIV_INLINE
83page_t*
84btr_pcur_get_page(
85/*==============*/
86	const btr_pcur_t*	cursor)	/*!< in: persistent cursor */
87{
88	ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
89
90	return(btr_cur_get_page(btr_pcur_get_btr_cur(cursor)));
91}
92
93/*********************************************************//**
94Returns the buffer block of a persistent cursor.
95@return pointer to the block */
96UNIV_INLINE
97buf_block_t*
98btr_pcur_get_block(
99/*===============*/
100	const btr_pcur_t*	cursor)	/*!< in: persistent cursor */
101{
102	ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
103
104	return(btr_cur_get_block(btr_pcur_get_btr_cur(cursor)));
105}
106
107/*********************************************************//**
108Returns the record of a persistent cursor.
109@return pointer to the record */
110UNIV_INLINE
111rec_t*
112btr_pcur_get_rec(
113/*=============*/
114	const btr_pcur_t*	cursor)	/*!< in: persistent cursor */
115{
116	ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
117	ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
118
119	return(btr_cur_get_rec(btr_pcur_get_btr_cur(cursor)));
120}
121#endif /* UNIV_DEBUG */
122
123/**************************************************************//**
124Gets the up_match value for a pcur after a search.
125@return number of matched fields at the cursor or to the right if
126search mode was PAGE_CUR_GE, otherwise undefined */
127UNIV_INLINE
128ulint
129btr_pcur_get_up_match(
130/*==================*/
131	const btr_pcur_t*	cursor) /*!< in: persistent cursor */
132{
133	const btr_cur_t*	btr_cursor;
134
135	ut_ad((cursor->pos_state == BTR_PCUR_WAS_POSITIONED)
136	      || (cursor->pos_state == BTR_PCUR_IS_POSITIONED));
137
138	btr_cursor = btr_pcur_get_btr_cur(cursor);
139
140	ut_ad(btr_cursor->up_match != ULINT_UNDEFINED);
141
142	return(btr_cursor->up_match);
143}
144
145/**************************************************************//**
146Gets the low_match value for a pcur after a search.
147@return number of matched fields at the cursor or to the right if
148search mode was PAGE_CUR_LE, otherwise undefined */
149UNIV_INLINE
150ulint
151btr_pcur_get_low_match(
152/*===================*/
153	const btr_pcur_t*	cursor) /*!< in: persistent cursor */
154{
155	const btr_cur_t*	btr_cursor;
156
157	ut_ad((cursor->pos_state == BTR_PCUR_WAS_POSITIONED)
158	      || (cursor->pos_state == BTR_PCUR_IS_POSITIONED));
159
160	btr_cursor = btr_pcur_get_btr_cur(cursor);
161	ut_ad(btr_cursor->low_match != ULINT_UNDEFINED);
162
163	return(btr_cursor->low_match);
164}
165
166/*********************************************************//**
167Checks if the persistent cursor is after the last user record on
168a page. */
169UNIV_INLINE
170ibool
171btr_pcur_is_after_last_on_page(
172/*===========================*/
173	const btr_pcur_t*	cursor)	/*!< in: persistent cursor */
174{
175	ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
176	ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
177
178	return(page_cur_is_after_last(btr_pcur_get_page_cur(cursor)));
179}
180
181/*********************************************************//**
182Checks if the persistent cursor is before the first user record on
183a page. */
184UNIV_INLINE
185ibool
186btr_pcur_is_before_first_on_page(
187/*=============================*/
188	const btr_pcur_t*	cursor)	/*!< in: persistent cursor */
189{
190	ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
191	ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
192
193	return(page_cur_is_before_first(btr_pcur_get_page_cur(cursor)));
194}
195
196/*********************************************************//**
197Checks if the persistent cursor is on a user record. */
198UNIV_INLINE
199ibool
200btr_pcur_is_on_user_rec(
201/*====================*/
202	const btr_pcur_t*	cursor)	/*!< in: persistent cursor */
203{
204	ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
205	ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
206
207	if (btr_pcur_is_before_first_on_page(cursor)
208	    || btr_pcur_is_after_last_on_page(cursor)) {
209
210		return(FALSE);
211	}
212
213	return(TRUE);
214}
215
216/*********************************************************//**
217Checks if the persistent cursor is before the first user record in
218the index tree. */
219UNIV_INLINE
220ibool
221btr_pcur_is_before_first_in_tree(
222/*=============================*/
223	btr_pcur_t*	cursor,	/*!< in: persistent cursor */
224	mtr_t*		mtr)	/*!< in: mtr */
225{
226	ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
227	ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
228
229	if (btr_page_get_prev(btr_pcur_get_page(cursor), mtr) != FIL_NULL) {
230
231		return(FALSE);
232	}
233
234	return(page_cur_is_before_first(btr_pcur_get_page_cur(cursor)));
235}
236
237/*********************************************************//**
238Checks if the persistent cursor is after the last user record in
239the index tree. */
240UNIV_INLINE
241ibool
242btr_pcur_is_after_last_in_tree(
243/*===========================*/
244	btr_pcur_t*	cursor,	/*!< in: persistent cursor */
245	mtr_t*		mtr)	/*!< in: mtr */
246{
247	ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
248	ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
249
250	if (btr_page_get_next(btr_pcur_get_page(cursor), mtr) != FIL_NULL) {
251
252		return(FALSE);
253	}
254
255	return(page_cur_is_after_last(btr_pcur_get_page_cur(cursor)));
256}
257
258/*********************************************************//**
259Moves the persistent cursor to the next record on the same page. */
260UNIV_INLINE
261void
262btr_pcur_move_to_next_on_page(
263/*==========================*/
264	btr_pcur_t*	cursor)	/*!< in/out: persistent cursor */
265{
266	ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
267	ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
268
269	page_cur_move_to_next(btr_pcur_get_page_cur(cursor));
270
271	cursor->old_stored = false;
272}
273
274/*********************************************************//**
275Moves the persistent cursor to the previous record on the same page. */
276UNIV_INLINE
277void
278btr_pcur_move_to_prev_on_page(
279/*==========================*/
280	btr_pcur_t*	cursor)	/*!< in/out: persistent cursor */
281{
282	ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
283	ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
284
285	page_cur_move_to_prev(btr_pcur_get_page_cur(cursor));
286
287	cursor->old_stored = false;
288}
289
290/*********************************************************//**
291Moves the persistent cursor to the last record on the same page. */
292UNIV_INLINE
293void
294btr_pcur_move_to_last_on_page(
295/*==========================*/
296	btr_pcur_t*	cursor,	/*!< in: persistent cursor */
297	mtr_t*		mtr)	/*!< in: mtr */
298{
299	UT_NOT_USED(mtr);
300	ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
301
302	page_cur_set_after_last(btr_pcur_get_block(cursor),
303				btr_pcur_get_page_cur(cursor));
304
305	cursor->old_stored = false;
306}
307
308/*********************************************************//**
309Moves the persistent cursor to the next user record in the tree. If no user
310records are left, the cursor ends up 'after last in tree'.
311@return TRUE if the cursor moved forward, ending on a user record */
312UNIV_INLINE
313ibool
314btr_pcur_move_to_next_user_rec(
315/*===========================*/
316	btr_pcur_t*	cursor,	/*!< in: persistent cursor; NOTE that the
317				function may release the page latch */
318	mtr_t*		mtr)	/*!< in: mtr */
319{
320	ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
321	ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
322	cursor->old_stored = false;
323loop:
324	if (btr_pcur_is_after_last_on_page(cursor)) {
325
326		if (btr_pcur_is_after_last_in_tree(cursor, mtr)) {
327
328			return(FALSE);
329		}
330
331		btr_pcur_move_to_next_page(cursor, mtr);
332	} else {
333		btr_pcur_move_to_next_on_page(cursor);
334	}
335
336	if (btr_pcur_is_on_user_rec(cursor)) {
337
338		return(TRUE);
339	}
340
341	goto loop;
342}
343
344/*********************************************************//**
345Moves the persistent cursor to the next record in the tree. If no records are
346left, the cursor stays 'after last in tree'.
347@return TRUE if the cursor was not after last in tree */
348UNIV_INLINE
349ibool
350btr_pcur_move_to_next(
351/*==================*/
352	btr_pcur_t*	cursor,	/*!< in: persistent cursor; NOTE that the
353				function may release the page latch */
354	mtr_t*		mtr)	/*!< in: mtr */
355{
356	ut_ad(cursor->pos_state == BTR_PCUR_IS_POSITIONED);
357	ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
358
359	cursor->old_stored = false;
360
361	if (btr_pcur_is_after_last_on_page(cursor)) {
362
363		if (btr_pcur_is_after_last_in_tree(cursor, mtr)) {
364
365			return(FALSE);
366		}
367
368		btr_pcur_move_to_next_page(cursor, mtr);
369
370		return(TRUE);
371	}
372
373	btr_pcur_move_to_next_on_page(cursor);
374
375	return(TRUE);
376}
377
378/**************************************************************//**
379Commits the mtr and sets the pcur latch mode to BTR_NO_LATCHES,
380that is, the cursor becomes detached.
381Function btr_pcur_store_position should be used before calling this,
382if restoration of cursor is wanted later. */
383UNIV_INLINE
384void
385btr_pcur_commit_specify_mtr(
386/*========================*/
387	btr_pcur_t*	pcur,	/*!< in: persistent cursor */
388	mtr_t*		mtr)	/*!< in: mtr to commit */
389{
390	ut_ad(pcur->pos_state == BTR_PCUR_IS_POSITIONED);
391
392	pcur->latch_mode = BTR_NO_LATCHES;
393
394	mtr_commit(mtr);
395
396	pcur->pos_state = BTR_PCUR_WAS_POSITIONED;
397}
398
399/**************************************************************//**
400Sets the old_rec_buf field to NULL. */
401UNIV_INLINE
402void
403btr_pcur_init(
404/*==========*/
405	btr_pcur_t*	pcur)	/*!< in: persistent cursor */
406{
407	pcur->old_stored = false;
408	pcur->old_rec_buf = NULL;
409	pcur->old_rec = NULL;
410
411	pcur->btr_cur.rtr_info = NULL;
412	pcur->import_ctx = NULL;
413}
414
415/** Free old_rec_buf.
416@param[in]	pcur	Persistent cursor holding old_rec to be freed. */
417UNIV_INLINE
418void
419btr_pcur_free(
420	btr_pcur_t*	pcur)
421{
422	ut_free(pcur->old_rec_buf);
423}
424
425/**************************************************************//**
426Initializes and opens a persistent cursor to an index tree. It should be
427closed with btr_pcur_close. */
428UNIV_INLINE
429dberr_t
430btr_pcur_open_low(
431/*==============*/
432	dict_index_t*	index,	/*!< in: index */
433	ulint		level,	/*!< in: level in the btree */
434	const dtuple_t*	tuple,	/*!< in: tuple on which search done */
435	page_cur_mode_t	mode,	/*!< in: PAGE_CUR_L, ...;
436				NOTE that if the search is made using a unique
437				prefix of a record, mode should be
438				PAGE_CUR_LE, not PAGE_CUR_GE, as the latter
439				may end up on the previous page from the
440				record! */
441	ulint		latch_mode,/*!< in: BTR_SEARCH_LEAF, ... */
442	btr_pcur_t*	cursor, /*!< in: memory buffer for persistent cursor */
443	const char*	file,	/*!< in: file name */
444	ulint		line,	/*!< in: line where called */
445	mtr_t*		mtr)	/*!< in: mtr */
446{
447	btr_cur_t*	btr_cursor;
448	dberr_t err = DB_SUCCESS;
449
450	/* Initialize the cursor */
451
452	btr_pcur_init(cursor);
453
454	cursor->latch_mode = BTR_LATCH_MODE_WITHOUT_FLAGS(latch_mode);
455	cursor->search_mode = mode;
456
457	/* Search with the tree cursor */
458
459	btr_cursor = btr_pcur_get_btr_cur(cursor);
460
461	ut_ad(!dict_index_is_spatial(index));
462
463	if (dict_table_is_intrinsic(index->table)) {
464		ut_ad((latch_mode & BTR_MODIFY_LEAF)
465		      || (latch_mode & BTR_SEARCH_LEAF)
466		      || (latch_mode & BTR_MODIFY_TREE));
467		btr_cur_search_to_nth_level_with_no_latch(
468			index, level, tuple, mode, btr_cursor,
469			file, line, mtr,
470			(((latch_mode & BTR_MODIFY_LEAF)
471			 || (latch_mode & BTR_MODIFY_TREE)) ? true : false));
472	} else {
473		err = btr_cur_search_to_nth_level(
474			index, level, tuple, mode, latch_mode,
475			btr_cursor, 0, file, line, mtr);
476	}
477
478	if (err != DB_SUCCESS) {
479		ib::warn() << " Error code: " << err
480			   << " btr_pcur_open_low "
481			   << " level: " << level
482			   << " called from file: "
483			   << file << " line: " << line
484			   << " table: " << index->table->name
485			   << " index: " << index->name;
486	}
487
488	cursor->pos_state = BTR_PCUR_IS_POSITIONED;
489
490	cursor->trx_if_known = NULL;
491
492	return(err);
493}
494
495/**************************************************************//**
496Opens an persistent cursor to an index tree without initializing the
497cursor. */
498UNIV_INLINE
499dberr_t
500btr_pcur_open_with_no_init_func(
501/*============================*/
502	dict_index_t*	index,	/*!< in: index */
503	const dtuple_t*	tuple,	/*!< in: tuple on which search done */
504	page_cur_mode_t	mode,	/*!< in: PAGE_CUR_L, ...;
505				NOTE that if the search is made using a unique
506				prefix of a record, mode should be
507				PAGE_CUR_LE, not PAGE_CUR_GE, as the latter
508				may end up on the previous page of the
509				record! */
510	ulint		latch_mode,/*!< in: BTR_SEARCH_LEAF, ...;
511				NOTE that if has_search_latch != 0 then
512				we maybe do not acquire a latch on the cursor
513				page, but assume that the caller uses his
514				btr search latch to protect the record! */
515	btr_pcur_t*	cursor, /*!< in: memory buffer for persistent cursor */
516	ulint		has_search_latch,
517				/*!< in: latch mode the caller
518				currently has on search system:
519				RW_S_LATCH, or 0 */
520	const char*	file,	/*!< in: file name */
521	ulint		line,	/*!< in: line where called */
522	mtr_t*		mtr)	/*!< in: mtr */
523{
524	btr_cur_t*	btr_cursor;
525	dberr_t		err = DB_SUCCESS;
526
527	cursor->latch_mode = BTR_LATCH_MODE_WITHOUT_INTENTION(latch_mode);
528	cursor->search_mode = mode;
529
530	/* Search with the tree cursor */
531
532	btr_cursor = btr_pcur_get_btr_cur(cursor);
533
534	if (dict_table_is_intrinsic(index->table)) {
535		ut_ad((latch_mode & BTR_MODIFY_LEAF)
536		      || (latch_mode & BTR_SEARCH_LEAF));
537		btr_cur_search_to_nth_level_with_no_latch(
538			index, 0, tuple, mode, btr_cursor,
539			file, line, mtr,
540			((latch_mode & BTR_MODIFY_LEAF) ? true : false));
541	} else {
542		err = btr_cur_search_to_nth_level(
543			index, 0, tuple, mode, latch_mode, btr_cursor,
544			has_search_latch, file, line, mtr);
545	}
546
547	cursor->pos_state = BTR_PCUR_IS_POSITIONED;
548
549	cursor->old_stored = false;
550
551	cursor->trx_if_known = NULL;
552
553        return err;
554}
555
556/*****************************************************************//**
557Opens a persistent cursor at either end of an index. */
558UNIV_INLINE
559dberr_t
560btr_pcur_open_at_index_side(
561/*========================*/
562	bool		from_left,	/*!< in: true if open to the low end,
563					false if to the high end */
564	dict_index_t*	index,		/*!< in: index */
565	ulint		latch_mode,	/*!< in: latch mode */
566	btr_pcur_t*	pcur,		/*!< in/out: cursor */
567	bool		init_pcur,	/*!< in: whether to initialize pcur */
568	ulint		level,		/*!< in: level to search for
569					(0=leaf) */
570	mtr_t*		mtr)		/*!< in/out: mini-transaction */
571{
572	dberr_t		err = DB_SUCCESS;
573
574	pcur->latch_mode = BTR_LATCH_MODE_WITHOUT_FLAGS(latch_mode);
575
576	pcur->search_mode = from_left ? PAGE_CUR_G : PAGE_CUR_L;
577
578	if (init_pcur) {
579		btr_pcur_init(pcur);
580	}
581
582	if (dict_table_is_intrinsic(index->table)) {
583		btr_cur_open_at_index_side_with_no_latch(
584			from_left, index,
585			btr_pcur_get_btr_cur(pcur), level, mtr);
586	} else {
587		err = btr_cur_open_at_index_side(
588			from_left, index, latch_mode,
589			btr_pcur_get_btr_cur(pcur), level, mtr);
590	}
591	pcur->pos_state = BTR_PCUR_IS_POSITIONED;
592
593	pcur->old_stored = false;
594
595	pcur->trx_if_known = NULL;
596
597	return err;
598}
599
600/**********************************************************************//**
601Positions a cursor at a randomly chosen position within a B-tree.
602@return true if the index is available and we have put the cursor, false
603if the index is unavailable */
604UNIV_INLINE
605bool
606btr_pcur_open_at_rnd_pos_func(
607/*==========================*/
608	dict_index_t*	index,		/*!< in: index */
609	ulint		latch_mode,	/*!< in: BTR_SEARCH_LEAF, ... */
610	btr_pcur_t*	cursor,		/*!< in/out: B-tree pcur */
611	const char*	file,		/*!< in: file name */
612	ulint		line,		/*!< in: line where called */
613	mtr_t*		mtr)		/*!< in: mtr */
614{
615	/* Initialize the cursor */
616
617	cursor->latch_mode = latch_mode;
618	cursor->search_mode = PAGE_CUR_G;
619
620	btr_pcur_init(cursor);
621
622	bool	available;
623
624	available = btr_cur_open_at_rnd_pos_func(index, latch_mode,
625						 btr_pcur_get_btr_cur(cursor),
626						 file, line, mtr);
627	cursor->pos_state = BTR_PCUR_IS_POSITIONED;
628	cursor->old_stored = false;
629
630	cursor->trx_if_known = NULL;
631
632	return(available);
633}
634
635/**************************************************************//**
636Frees the possible memory heap of a persistent cursor and sets the latch
637mode of the persistent cursor to BTR_NO_LATCHES.
638WARNING: this function does not release the latch on the page where the
639cursor is currently positioned. The latch is acquired by the
640"move to next/previous" family of functions. Since recursive shared locks
641are not allowed, you must take care (if using the cursor in S-mode) to
642manually release the latch by either calling
643btr_leaf_page_release(btr_pcur_get_block(&pcur), pcur.latch_mode, mtr)
644or by committing the mini-transaction right after btr_pcur_close().
645A subsequent attempt to crawl the same page in the same mtr would cause
646an assertion failure. */
647UNIV_INLINE
648void
649btr_pcur_close(
650/*===========*/
651	btr_pcur_t*	cursor)	/*!< in: persistent cursor */
652{
653	ut_free(cursor->old_rec_buf);
654
655	if (cursor->btr_cur.rtr_info) {
656		rtr_clean_rtr_info(cursor->btr_cur.rtr_info, true);
657		cursor->btr_cur.rtr_info = NULL;
658	}
659
660	cursor->old_rec = NULL;
661	cursor->old_rec_buf = NULL;
662	cursor->btr_cur.page_cur.rec = NULL;
663	cursor->btr_cur.page_cur.block = NULL;
664
665	cursor->old_rec = NULL;
666	cursor->old_stored = false;
667
668	cursor->latch_mode = BTR_NO_LATCHES;
669	cursor->pos_state = BTR_PCUR_NOT_POSITIONED;
670
671	cursor->trx_if_known = NULL;
672}
673
674/*********************************************************//**
675Moves the persistent cursor to the infimum record on the same page. */
676UNIV_INLINE
677void
678btr_pcur_move_before_first_on_page(
679/*===============================*/
680	btr_pcur_t*	cursor) /*!< in/out: persistent cursor */
681{
682	ut_ad(cursor->latch_mode != BTR_NO_LATCHES);
683
684	page_cur_set_before_first(btr_pcur_get_block(cursor),
685		btr_pcur_get_page_cur(cursor));
686
687	cursor->old_stored = false;
688}
689