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