1/*****************************************************************************
2
3Copyright (c) 1994, 2020, Oracle and/or its affiliates. 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, version 2.0, as published by the
7Free Software Foundation.
8
9This program is also distributed with certain software (including but not
10limited to OpenSSL) that is licensed under separate terms, as designated in a
11particular file or component or in included license documentation. The authors
12of MySQL hereby grant you an additional permission to link the program and
13your derivative works with the separately licensed software that they have
14included with MySQL.
15
16This program is distributed in the hope that it will be useful, but WITHOUT
17ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
18FOR A PARTICULAR PURPOSE. See the GNU General Public License, version 2.0,
19for 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 St, Fifth Floor, Boston, MA 02110-1301  USA
24
25*****************************************************************************/
26
27/** @file include/btr0btr.ic
28 The B-tree
29
30 Created 6/2/1994 Heikki Tuuri
31 *******************************************************/
32
33#include "mach0data.h"
34#ifndef UNIV_HOTBACKUP
35#include "mtr0log.h"
36#include "mtr0mtr.h"
37#include "page0zip.h"
38#endif /* !UNIV_HOTBACKUP */
39
40/** NOTE - Changing this from the original number of 50 to 45 as
41insert_debug.test was failing in ASAN build because of a stack overflow issue.
42It was found that rtr_info_t was taking up a lot of stack space in the function
43btr_insert_on_non_leaf_level_func which is part of the recursive stack
44trace. */
45#define BTR_MAX_NODE_LEVEL          \
46  45 /*!< Maximum B-tree page level \
47     (not really a hard limit).     \
48     Used in debug assertions       \
49     in btr_page_set_level and      \
50     btr_page_get_level_low */
51
52#ifndef UNIV_HOTBACKUP
53/** Gets a buffer page and declares its latching order level.
54@param[in]	page_id	page id
55@param[in]	mode	latch mode
56@param[in]	file	file name
57@param[in]	line	line where called */
58#ifdef UNIV_DEBUG
59/**
60@param[in]	index	index tree, may be NULL if it is not an insert buffer
61tree */
62#endif /* UNIV_DEBUG */
63/**
64@param[in,out]	mtr	mini-transaction
65@return block */
66UNIV_INLINE
67buf_block_t *btr_block_get_func(const page_id_t &page_id,
68                                const page_size_t &page_size, ulint mode,
69                                const char *file, ulint line,
70#ifdef UNIV_DEBUG
71                                const dict_index_t *index,
72#endif /* UNIV_DEBUG */
73                                mtr_t *mtr) {
74  buf_block_t *block;
75
76  block = buf_page_get_gen(page_id, page_size, mode, nullptr,
77                           Page_fetch::NORMAL, file, line, mtr);
78
79  if (mode != RW_NO_LATCH) {
80    buf_block_dbg_add_level(block, index != nullptr && dict_index_is_ibuf(index)
81                                       ? SYNC_IBUF_TREE_NODE
82                                       : SYNC_TREE_NODE);
83  }
84
85  return (block);
86}
87
88/** Sets the index id field of a page. */
89UNIV_INLINE
90void btr_page_set_index_id(
91    page_t *page,             /*!< in: page to be created */
92    page_zip_des_t *page_zip, /*!< in: compressed page whose uncompressed
93                             part will be updated, or NULL */
94    space_index_t id,         /*!< in: index id */
95    mtr_t *mtr)               /*!< in: mtr */
96{
97  if (page_zip) {
98    mach_write_to_8(page + (PAGE_HEADER + PAGE_INDEX_ID), id);
99    page_zip_write_header(page_zip, page + (PAGE_HEADER + PAGE_INDEX_ID), 8,
100                          mtr);
101  } else {
102    mlog_write_ull(page + (PAGE_HEADER + PAGE_INDEX_ID), id, mtr);
103  }
104}
105#endif /* !UNIV_HOTBACKUP */
106
107/** Gets the index id field of a page.
108 @return index id */
109UNIV_INLINE
110space_index_t btr_page_get_index_id(const page_t *page) /*!< in: index page */
111{
112  return (mach_read_from_8(page + PAGE_HEADER + PAGE_INDEX_ID));
113}
114
115/** Gets the node level field in an index page.
116 @return level, leaf level == 0 */
117UNIV_INLINE
118ulint btr_page_get_level_low(const page_t *page) /*!< in: index page */
119{
120  ulint level;
121
122  ut_ad(page);
123
124  level = mach_read_from_2(page + PAGE_HEADER + PAGE_LEVEL);
125
126  ut_ad(level <= BTR_MAX_NODE_LEVEL);
127
128  return (level);
129}
130
131/** Sets the node level field in an index page. */
132UNIV_INLINE
133void btr_page_set_level(
134    page_t *page,             /*!< in: index page */
135    page_zip_des_t *page_zip, /*!< in: compressed page whose uncompressed
136                             part will be updated, or NULL */
137    ulint level,              /*!< in: level, leaf level == 0 */
138    mtr_t *mtr)               /*!< in: mini-transaction handle */
139{
140  ut_ad(page != nullptr);
141  ut_ad(mtr != nullptr);
142  ut_ad(level <= BTR_MAX_NODE_LEVEL);
143
144  if (page_zip) {
145    mach_write_to_2(page + (PAGE_HEADER + PAGE_LEVEL), level);
146    page_zip_write_header(page_zip, page + (PAGE_HEADER + PAGE_LEVEL), 2, mtr);
147  } else {
148    mlog_write_ulint(page + (PAGE_HEADER + PAGE_LEVEL), level, MLOG_2BYTES,
149                     mtr);
150  }
151}
152
153/** Gets the next index page number.
154 @return next page number */
155UNIV_INLINE
156page_no_t btr_page_get_next(const page_t *page, /*!< in: index page */
157                            mtr_t *mtr MY_ATTRIBUTE((unused)))
158/*!< in: mini-transaction handle */
159{
160  ut_ad(page != nullptr);
161  ut_ad(mtr != nullptr);
162
163  return (mach_read_from_4(page + FIL_PAGE_NEXT));
164}
165
166/** Sets the next index page field. */
167UNIV_INLINE
168void btr_page_set_next(
169    page_t *page,             /*!< in: index page */
170    page_zip_des_t *page_zip, /*!< in: compressed page whose uncompressed
171                             part will be updated, or NULL */
172    page_no_t next,           /*!< in: next page number */
173    mtr_t *mtr)               /*!< in: mini-transaction handle */
174{
175  ut_ad(page != nullptr);
176  ut_ad(mtr != nullptr);
177
178  if (page_zip) {
179    mach_write_to_4(page + FIL_PAGE_NEXT, next);
180    page_zip_write_header(page_zip, page + FIL_PAGE_NEXT, 4, mtr);
181  } else {
182    mlog_write_ulint(page + FIL_PAGE_NEXT, next, MLOG_4BYTES, mtr);
183  }
184}
185
186/** Gets the previous index page number.
187 @return prev page number */
188UNIV_INLINE
189page_no_t btr_page_get_prev(
190    const page_t *page,                /*!< in: index page */
191    mtr_t *mtr MY_ATTRIBUTE((unused))) /*!< in: mini-transaction handle */
192{
193  ut_ad(page != nullptr);
194  ut_ad(mtr != nullptr);
195
196  return (mach_read_from_4(page + FIL_PAGE_PREV));
197}
198
199/** Sets the previous index page field. */
200UNIV_INLINE
201void btr_page_set_prev(
202    page_t *page,             /*!< in: index page */
203    page_zip_des_t *page_zip, /*!< in: compressed page whose uncompressed
204                             part will be updated, or NULL */
205    page_no_t prev,           /*!< in: previous page number */
206    mtr_t *mtr)               /*!< in: mini-transaction handle */
207{
208  ut_ad(page != nullptr);
209  ut_ad(mtr != nullptr);
210
211  if (page_zip) {
212    mach_write_to_4(page + FIL_PAGE_PREV, prev);
213    page_zip_write_header(page_zip, page + FIL_PAGE_PREV, 4, mtr);
214  } else {
215    mlog_write_ulint(page + FIL_PAGE_PREV, prev, MLOG_4BYTES, mtr);
216  }
217}
218
219/** Gets the child node file address in a node pointer.
220 NOTE: the offsets array must contain all offsets for the record since
221 we read the last field according to offsets and assume that it contains
222 the child page number. In other words offsets must have been retrieved
223 with rec_get_offsets(n_fields=ULINT_UNDEFINED).
224 @return child node address */
225UNIV_INLINE
226page_no_t btr_node_ptr_get_child_page_no(
227    const rec_t *rec,     /*!< in: node pointer record */
228    const ulint *offsets) /*!< in: array returned by rec_get_offsets() */
229{
230  const byte *field;
231  ulint len;
232  page_no_t page_no;
233
234  ut_ad(!rec_offs_comp(offsets) || rec_get_node_ptr_flag(rec));
235
236  /* The child address is in the last field */
237  field = rec_get_nth_field(rec, offsets, rec_offs_n_fields(offsets) - 1, &len);
238
239  ut_ad(len == 4);
240
241  page_no = mach_read_from_4(field);
242  ut_ad(page_no > 1);
243
244  return (page_no);
245}
246
247#ifndef UNIV_HOTBACKUP
248/** Releases the latches on a leaf page and bufferunfixes it. */
249UNIV_INLINE
250void btr_leaf_page_release(buf_block_t *block, /*!< in: buffer block */
251                           ulint latch_mode,   /*!< in: BTR_SEARCH_LEAF or
252                                               BTR_MODIFY_LEAF */
253                           mtr_t *mtr)         /*!< in: mtr */
254{
255  ut_ad(latch_mode == BTR_SEARCH_LEAF || latch_mode == BTR_MODIFY_LEAF ||
256        latch_mode == BTR_NO_LATCHES);
257
258  ut_ad(!mtr_memo_contains(mtr, block, MTR_MEMO_MODIFY));
259
260  ulint mode;
261  switch (latch_mode) {
262    case BTR_SEARCH_LEAF:
263      mode = MTR_MEMO_PAGE_S_FIX;
264      break;
265    case BTR_MODIFY_LEAF:
266      mode = MTR_MEMO_PAGE_X_FIX;
267      break;
268    case BTR_NO_LATCHES:
269      mode = MTR_MEMO_BUF_FIX;
270      break;
271    default:
272      ut_a(0);
273  }
274
275  mtr->memo_release(block, mode);
276}
277#endif /* !UNIV_HOTBACKUP */
278