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