btr0btr.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:74k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /******************************************************
  2. The B-tree
  3. (c) 1994-1996 Innobase Oy
  4. Created 6/2/1994 Heikki Tuuri
  5. *******************************************************/
  6.  
  7. #include "btr0btr.h"
  8. #ifdef UNIV_NONINL
  9. #include "btr0btr.ic"
  10. #endif
  11. #include "fsp0fsp.h"
  12. #include "page0page.h"
  13. #include "btr0cur.h"
  14. #include "btr0sea.h"
  15. #include "btr0pcur.h"
  16. #include "rem0cmp.h"
  17. #include "lock0lock.h"
  18. #include "ibuf0ibuf.h"
  19. /*
  20. Latching strategy of the InnoDB B-tree
  21. --------------------------------------
  22. A tree latch protects all non-leaf nodes of the tree. Each node of a tree
  23. also has a latch of its own.
  24. A B-tree operation normally first acquires an S-latch on the tree. It
  25. searches down the tree and releases the tree latch when it has the
  26. leaf node latch. To save CPU time we do not acquire any latch on
  27. non-leaf nodes of the tree during a search, those pages are only bufferfixed.
  28. If an operation needs to restructure the tree, it acquires an X-latch on
  29. the tree before searching to a leaf node. If it needs, for example, to
  30. split a leaf,
  31. (1) InnoDB decides the split point in the leaf,
  32. (2) allocates a new page,
  33. (3) inserts the appropriate node pointer to the first non-leaf level,
  34. (4) releases the tree X-latch,
  35. (5) and then moves records from the leaf to the new allocated page.
  36. Node pointers
  37. -------------
  38. Leaf pages of a B-tree contain the index records stored in the
  39. tree. On levels n > 0 we store 'node pointers' to pages on level
  40. n - 1. For each page there is exactly one node pointer stored:
  41. thus the our tree is an ordinary B-tree, not a B-link tree.
  42. A node pointer contains a prefix P of an index record. The prefix
  43. is long enough so that it determines an index record uniquely.
  44. The file page number of the child page is added as the last
  45. field. To the child page we can store node pointers or index records
  46. which are >= P in the alphabetical order, but < P1 if there is
  47. a next node pointer on the level, and P1 is its prefix.
  48. If a node pointer with a prefix P points to a non-leaf child, 
  49. then the leftmost record in the child must have the same
  50. prefix P. If it points to a leaf node, the child is not required
  51. to contain any record with a prefix equal to P. The leaf case
  52. is decided this way to allow arbitrary deletions in a leaf node
  53. without touching upper levels of the tree.
  54. We have predefined a special minimum record which we
  55. define as the smallest record in any alphabetical order.
  56. A minimum record is denoted by setting a bit in the record
  57. header. A minimum record acts as the prefix of a node pointer
  58. which points to a leftmost node on any level of the tree.
  59. File page allocation
  60. --------------------
  61. In the root node of a B-tree there are two file segment headers.
  62. The leaf pages of a tree are allocated from one file segment, to
  63. make them consecutive on disk if possible. From the other file segment
  64. we allocate pages for the non-leaf levels of the tree.
  65. */
  66. /******************************************************************
  67. Creates a new index page to the tree (not the root, and also not
  68. used in page reorganization). */
  69. static
  70. void
  71. btr_page_create(
  72. /*============*/
  73. page_t* page, /* in: page to be created */
  74. dict_tree_t* tree, /* in: index tree */
  75. mtr_t* mtr); /* in: mtr */
  76. /******************************************************************
  77. Sets the child node file address in a node pointer. */
  78. UNIV_INLINE
  79. void
  80. btr_node_ptr_set_child_page_no(
  81. /*===========================*/
  82. rec_t* rec, /* in: node pointer record */
  83. ulint page_no, /* in: child node address */
  84. mtr_t* mtr); /* in: mtr */
  85. /****************************************************************
  86. Returns the upper level node pointer to a page. It is assumed that
  87. mtr holds an x-latch on the tree. */
  88. static
  89. rec_t*
  90. btr_page_get_father_node_ptr(
  91. /*=========================*/
  92. /* out: pointer to node pointer record */
  93. dict_tree_t* tree, /* in: index tree */
  94. page_t* page, /* in: page: must contain at least one
  95. user record */
  96. mtr_t* mtr); /* in: mtr */
  97. /*****************************************************************
  98. Empties an index page. */
  99. static
  100. void
  101. btr_page_empty(
  102. /*===========*/
  103. page_t* page, /* in: page to be emptied */
  104. mtr_t* mtr); /* in: mtr */
  105. /*****************************************************************
  106. Returns TRUE if the insert fits on the appropriate half-page
  107. with the chosen split_rec. */
  108. static
  109. ibool
  110. btr_page_insert_fits(
  111. /*=================*/
  112. /* out: TRUE if fits */
  113. btr_cur_t* cursor, /* in: cursor at which insert
  114. should be made */
  115. rec_t* split_rec, /* in: suggestion for first record
  116. on upper half-page, or NULL if
  117. tuple should be first */
  118. dtuple_t* tuple); /* in: tuple to insert */
  119. /******************************************************************
  120. Gets the root node of a tree and x-latches it. */
  121. page_t*
  122. btr_root_get(
  123. /*=========*/
  124. /* out: root page, x-latched */
  125. dict_tree_t* tree, /* in: index tree */
  126. mtr_t* mtr) /* in: mtr */
  127. {
  128. ulint space;
  129. ulint root_page_no;
  130. page_t* root;
  131. space = dict_tree_get_space(tree);
  132. root_page_no = dict_tree_get_page(tree);
  133. root = btr_page_get(space, root_page_no, RW_X_LATCH, mtr);
  134. return(root);
  135. }
  136. /*****************************************************************
  137. Gets pointer to the previous user record in the tree. It is assumed that
  138. the caller has appropriate latches on the page and its neighbor. */
  139. rec_t*
  140. btr_get_prev_user_rec(
  141. /*==================*/
  142. /* out: previous user record, NULL if there is none */
  143. rec_t* rec, /* in: record on leaf level */
  144. mtr_t* mtr) /* in: mtr holding a latch on the page, and if
  145. needed, also to the previous page */
  146. {
  147. page_t* page;
  148. page_t* prev_page;
  149. ulint prev_page_no;
  150. rec_t* prev_rec;
  151. ulint space;
  152. page = buf_frame_align(rec);
  153. if (page_get_infimum_rec(page) != rec) {
  154. prev_rec = page_rec_get_prev(rec);
  155. if (page_get_infimum_rec(page) != prev_rec) {
  156. return(prev_rec);
  157. }
  158. }
  159. prev_page_no = btr_page_get_prev(page, mtr);
  160. space = buf_frame_get_space_id(page);
  161. if (prev_page_no != FIL_NULL) {
  162. prev_page = buf_page_get_with_no_latch(space, prev_page_no,
  163. mtr);
  164. /* The caller must already have a latch to the brother */
  165. ut_ad((mtr_memo_contains(mtr, buf_block_align(prev_page),
  166.        MTR_MEMO_PAGE_S_FIX))
  167.       || (mtr_memo_contains(mtr, buf_block_align(prev_page),
  168.        MTR_MEMO_PAGE_X_FIX)));
  169. prev_rec = page_rec_get_prev(page_get_supremum_rec(prev_page));
  170. return(prev_rec);
  171. }
  172. return(NULL);
  173. }
  174. /*****************************************************************
  175. Gets pointer to the next user record in the tree. It is assumed that the
  176. caller has appropriate latches on the page and its neighbor. */
  177. rec_t*
  178. btr_get_next_user_rec(
  179. /*==================*/
  180. /* out: next user record, NULL if there is none */
  181. rec_t* rec, /* in: record on leaf level */
  182. mtr_t* mtr) /* in: mtr holding a latch on the page, and if
  183. needed, also to the next page */
  184. {
  185. page_t* page;
  186. page_t* next_page;
  187. ulint next_page_no;
  188. rec_t* next_rec;
  189. ulint space;
  190. page = buf_frame_align(rec);
  191. if (page_get_supremum_rec(page) != rec) {
  192. next_rec = page_rec_get_next(rec);
  193. if (page_get_supremum_rec(page) != next_rec) {
  194. return(next_rec);
  195. }
  196. }
  197. next_page_no = btr_page_get_next(page, mtr);
  198. space = buf_frame_get_space_id(page);
  199. if (next_page_no != FIL_NULL) {
  200. next_page = buf_page_get_with_no_latch(space, next_page_no,
  201. mtr);
  202. /* The caller must already have a latch to the brother */
  203. ut_ad((mtr_memo_contains(mtr, buf_block_align(next_page),
  204.        MTR_MEMO_PAGE_S_FIX))
  205.       || (mtr_memo_contains(mtr, buf_block_align(next_page),
  206.        MTR_MEMO_PAGE_X_FIX)));
  207. next_rec = page_rec_get_next(page_get_infimum_rec(next_page));
  208. return(next_rec);
  209. }
  210. return(NULL);
  211. }
  212. /******************************************************************
  213. Creates a new index page to the tree (not the root, and also not used in
  214. page reorganization). */
  215. static
  216. void
  217. btr_page_create(
  218. /*============*/
  219. page_t* page, /* in: page to be created */
  220. dict_tree_t* tree, /* in: index tree */
  221. mtr_t* mtr) /* in: mtr */
  222. {
  223. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  224.        MTR_MEMO_PAGE_X_FIX));
  225. page_create(page, mtr);
  226. buf_block_align(page)->check_index_page_at_flush = TRUE;
  227. btr_page_set_index_id(page, tree->id, mtr);
  228. }
  229. /******************************************************************
  230. Allocates a new file page to be used in an ibuf tree. Takes the page from
  231. the free list of the tree, which must contain pages! */
  232. static
  233. page_t*
  234. btr_page_alloc_for_ibuf(
  235. /*====================*/
  236. /* out: new allocated page, x-latched */
  237. dict_tree_t* tree, /* in: index tree */
  238. mtr_t* mtr) /* in: mtr */
  239. {
  240. fil_addr_t node_addr;
  241. page_t* root;
  242. page_t* new_page;
  243. root = btr_root_get(tree, mtr);
  244. node_addr = flst_get_first(root + PAGE_HEADER
  245. + PAGE_BTR_IBUF_FREE_LIST, mtr);
  246. ut_a(node_addr.page != FIL_NULL);
  247. new_page = buf_page_get(dict_tree_get_space(tree), node_addr.page,
  248. RW_X_LATCH, mtr);
  249. #ifdef UNIV_SYNC_DEBUG
  250. buf_page_dbg_add_level(new_page, SYNC_TREE_NODE_NEW);
  251. #endif /* UNIV_SYNC_DEBUG */
  252. flst_remove(root + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST,
  253.     new_page + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST_NODE,
  254. mtr);
  255. ut_ad(flst_validate(root + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST, mtr));
  256. return(new_page);
  257. }
  258. /******************************************************************
  259. Allocates a new file page to be used in an index tree. NOTE: we assume
  260. that the caller has made the reservation for free extents! */
  261. page_t*
  262. btr_page_alloc(
  263. /*===========*/
  264. /* out: new allocated page, x-latched;
  265. NULL if out of space */
  266. dict_tree_t* tree, /* in: index tree */
  267. ulint hint_page_no, /* in: hint of a good page */
  268. byte file_direction, /* in: direction where a possible
  269. page split is made */
  270. ulint level, /* in: level where the page is placed
  271. in the tree */
  272. mtr_t* mtr) /* in: mtr */
  273. {
  274. fseg_header_t* seg_header;
  275. page_t* root;
  276. page_t* new_page;
  277. ulint new_page_no;
  278. if (tree->type & DICT_IBUF) {
  279. return(btr_page_alloc_for_ibuf(tree, mtr));
  280. }
  281. root = btr_root_get(tree, mtr);
  282. if (level == 0) {
  283. seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_LEAF;
  284. } else {
  285. seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_TOP;
  286. }
  287. /* Parameter TRUE below states that the caller has made the
  288. reservation for free extents, and thus we know that a page can
  289. be allocated: */
  290. new_page_no = fseg_alloc_free_page_general(seg_header, hint_page_no,
  291. file_direction, TRUE, mtr);
  292. if (new_page_no == FIL_NULL) {
  293. return(NULL);
  294. }
  295. new_page = buf_page_get(dict_tree_get_space(tree), new_page_no,
  296. RW_X_LATCH, mtr);
  297. #ifdef UNIV_SYNC_DEBUG
  298. buf_page_dbg_add_level(new_page, SYNC_TREE_NODE_NEW);
  299. #endif /* UNIV_SYNC_DEBUG */
  300. return(new_page);
  301. }
  302. /******************************************************************
  303. Gets the number of pages in a B-tree. */
  304. ulint
  305. btr_get_size(
  306. /*=========*/
  307. /* out: number of pages */
  308. dict_index_t* index, /* in: index */
  309. ulint flag) /* in: BTR_N_LEAF_PAGES or BTR_TOTAL_SIZE */
  310. {
  311. fseg_header_t* seg_header;
  312. page_t* root;
  313. ulint n;
  314. ulint dummy;
  315. mtr_t mtr;
  316. mtr_start(&mtr);
  317. mtr_s_lock(dict_tree_get_lock(index->tree), &mtr);
  318. root = btr_root_get(index->tree, &mtr);
  319. if (flag == BTR_N_LEAF_PAGES) {
  320. seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_LEAF;
  321. fseg_n_reserved_pages(seg_header, &n, &mtr);
  322. } else if (flag == BTR_TOTAL_SIZE) {
  323. seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_TOP;
  324. n = fseg_n_reserved_pages(seg_header, &dummy, &mtr);
  325. seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_LEAF;
  326. n += fseg_n_reserved_pages(seg_header, &dummy, &mtr);
  327. } else {
  328. ut_error;
  329. }
  330. mtr_commit(&mtr);
  331. return(n);
  332. }
  333. /******************************************************************
  334. Frees a page used in an ibuf tree. Puts the page to the free list of the
  335. ibuf tree. */
  336. static
  337. void
  338. btr_page_free_for_ibuf(
  339. /*===================*/
  340. dict_tree_t* tree, /* in: index tree */
  341. page_t* page, /* in: page to be freed, x-latched */
  342. mtr_t* mtr) /* in: mtr */
  343. {
  344. page_t* root;
  345. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  346.        MTR_MEMO_PAGE_X_FIX));
  347. root = btr_root_get(tree, mtr);
  348. flst_add_first(root + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST,
  349.        page + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST_NODE, mtr);
  350. ut_ad(flst_validate(root + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST,
  351. mtr));
  352. }
  353. /******************************************************************
  354. Frees a file page used in an index tree. Can be used also to (BLOB)
  355. external storage pages, because the page level 0 can be given as an
  356. argument. */
  357. void
  358. btr_page_free_low(
  359. /*==============*/
  360. dict_tree_t* tree, /* in: index tree */
  361. page_t* page, /* in: page to be freed, x-latched */
  362. ulint level, /* in: page level */
  363. mtr_t* mtr) /* in: mtr */
  364. {
  365. fseg_header_t* seg_header;
  366. page_t* root;
  367. ulint space;
  368. ulint page_no;
  369. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  370.        MTR_MEMO_PAGE_X_FIX));
  371. /* The page gets invalid for optimistic searches: increment the frame
  372. modify clock */
  373. buf_frame_modify_clock_inc(page);
  374. if (tree->type & DICT_IBUF) {
  375. btr_page_free_for_ibuf(tree, page, mtr);
  376. return;
  377. }
  378. root = btr_root_get(tree, mtr);
  379. if (level == 0) {
  380. seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_LEAF;
  381. } else {
  382. seg_header = root + PAGE_HEADER + PAGE_BTR_SEG_TOP;
  383. }
  384. space = buf_frame_get_space_id(page);
  385. page_no = buf_frame_get_page_no(page);
  386. fseg_free_page(seg_header, space, page_no, mtr);
  387. }
  388. /******************************************************************
  389. Frees a file page used in an index tree. NOTE: cannot free field external
  390. storage pages because the page must contain info on its level. */
  391. void
  392. btr_page_free(
  393. /*==========*/
  394. dict_tree_t* tree, /* in: index tree */
  395. page_t* page, /* in: page to be freed, x-latched */
  396. mtr_t* mtr) /* in: mtr */
  397. {
  398. ulint level;
  399. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  400.        MTR_MEMO_PAGE_X_FIX));
  401. level = btr_page_get_level(page, mtr);
  402. btr_page_free_low(tree, page, level, mtr);
  403. }
  404. /******************************************************************
  405. Sets the child node file address in a node pointer. */
  406. UNIV_INLINE
  407. void
  408. btr_node_ptr_set_child_page_no(
  409. /*===========================*/
  410. rec_t* rec, /* in: node pointer record */
  411. ulint page_no, /* in: child node address */
  412. mtr_t* mtr) /* in: mtr */
  413. {
  414. ulint n_fields;
  415. byte* field;
  416. ulint len;
  417. ut_ad(0 < btr_page_get_level(buf_frame_align(rec), mtr));
  418. n_fields = rec_get_n_fields(rec);
  419. /* The child address is in the last field */
  420. field = rec_get_nth_field(rec, n_fields - 1, &len);
  421. ut_ad(len == 4);
  422. mlog_write_ulint(field, page_no, MLOG_4BYTES, mtr);
  423. }
  424. /****************************************************************
  425. Returns the child page of a node pointer and x-latches it. */
  426. static
  427. page_t*
  428. btr_node_ptr_get_child(
  429. /*===================*/
  430.   /* out: child page, x-latched */
  431. rec_t* node_ptr, /* in: node pointer */
  432. mtr_t* mtr) /* in: mtr */
  433. {
  434. ulint page_no;
  435. ulint space;
  436. page_t* page;
  437. space = buf_frame_get_space_id(node_ptr);
  438. page_no = btr_node_ptr_get_child_page_no(node_ptr);
  439. page = btr_page_get(space, page_no, RW_X_LATCH, mtr);
  440. return(page);
  441. }
  442. /****************************************************************
  443. Returns the upper level node pointer to a page. It is assumed that mtr holds
  444. an x-latch on the tree. */
  445. static
  446. rec_t*
  447. btr_page_get_father_for_rec(
  448. /*========================*/
  449. /* out: pointer to node pointer record,
  450. its page x-latched */
  451. dict_tree_t* tree, /* in: index tree */
  452. page_t* page, /* in: page: must contain at least one
  453. user record */
  454. rec_t* user_rec,/* in: user_record on page */
  455. mtr_t* mtr) /* in: mtr */
  456. {
  457. mem_heap_t* heap;
  458. dtuple_t* tuple;
  459. btr_cur_t cursor;
  460. rec_t* node_ptr;
  461. ut_ad(mtr_memo_contains(mtr, dict_tree_get_lock(tree),
  462. MTR_MEMO_X_LOCK));
  463. ut_a(user_rec != page_get_supremum_rec(page));
  464. ut_a(user_rec != page_get_infimum_rec(page));
  465. ut_ad(dict_tree_get_page(tree) != buf_frame_get_page_no(page));
  466. heap = mem_heap_create(100);
  467. tuple = dict_tree_build_node_ptr(tree, user_rec, 0, heap,
  468.  btr_page_get_level(page, mtr));
  469. /* In the following, we choose just any index from the tree as the
  470. first parameter for btr_cur_search_to_nth_level. */
  471. btr_cur_search_to_nth_level(UT_LIST_GET_FIRST(tree->tree_indexes),
  472. btr_page_get_level(page, mtr) + 1,
  473. tuple, PAGE_CUR_LE,
  474. BTR_CONT_MODIFY_TREE, &cursor, 0, mtr);
  475. node_ptr = btr_cur_get_rec(&cursor);
  476. if (btr_node_ptr_get_child_page_no(node_ptr) !=
  477.                                                 buf_frame_get_page_no(page)) {
  478. fputs("InnoDB: Dump of the child page:n", stderr);
  479. buf_page_print(buf_frame_align(page));
  480. fputs("InnoDB: Dump of the parent page:n", stderr);
  481. buf_page_print(buf_frame_align(node_ptr));
  482. fputs("InnoDB: Corruption of an index tree: table ", stderr);
  483. ut_print_name(stderr, NULL,
  484. UT_LIST_GET_FIRST(tree->tree_indexes)->table_name);
  485. fputs(", index ", stderr);
  486. ut_print_name(stderr, NULL,
  487. UT_LIST_GET_FIRST(tree->tree_indexes)->name);
  488. fprintf(stderr, ",n"
  489. "InnoDB: father ptr page no %lu, child page no %lun",
  490. (ulong) btr_node_ptr_get_child_page_no(node_ptr),
  491. (ulong) buf_frame_get_page_no(page));
  492.       page_rec_print(page_rec_get_next(page_get_infimum_rec(page)));
  493.       page_rec_print(node_ptr);
  494. fputs(
  495. "InnoDB: You should dump + drop + reimport the table to fix then"
  496. "InnoDB: corruption. If the crash happens at the database startup, seen"
  497. "InnoDB: http://dev.mysql.com/doc/mysql/en/Forcing_recovery.html aboutn"
  498. "InnoDB: forcing recovery. Then dump + drop + reimport.n", stderr);
  499. }
  500. ut_a(btr_node_ptr_get_child_page_no(node_ptr) ==
  501. buf_frame_get_page_no(page));
  502. mem_heap_free(heap);
  503. return(node_ptr);
  504. }
  505. /****************************************************************
  506. Returns the upper level node pointer to a page. It is assumed that
  507. mtr holds an x-latch on the tree. */
  508. static
  509. rec_t*
  510. btr_page_get_father_node_ptr(
  511. /*=========================*/
  512. /* out: pointer to node pointer record */
  513. dict_tree_t* tree, /* in: index tree */
  514. page_t* page, /* in: page: must contain at least one
  515. user record */
  516. mtr_t* mtr) /* in: mtr */
  517. {
  518. return(btr_page_get_father_for_rec(tree, page,
  519. page_rec_get_next(page_get_infimum_rec(page)), mtr));
  520. }
  521. /****************************************************************
  522. Creates the root node for a new index tree. */
  523. ulint
  524. btr_create(
  525. /*=======*/
  526. /* out: page number of the created root, FIL_NULL if
  527. did not succeed */
  528. ulint type, /* in: type of the index */
  529. ulint space, /* in: space where created */
  530. dulint index_id,/* in: index id */
  531. mtr_t* mtr) /* in: mini-transaction handle */
  532. {
  533. ulint page_no;
  534. buf_frame_t* ibuf_hdr_frame;
  535. buf_frame_t* frame;
  536. page_t* page;
  537. /* Create the two new segments (one, in the case of an ibuf tree) for
  538. the index tree; the segment headers are put on the allocated root page
  539. (for an ibuf tree, not in the root, but on a separate ibuf header
  540. page) */
  541. if (type & DICT_IBUF) {
  542. /* Allocate first the ibuf header page */
  543. ibuf_hdr_frame = fseg_create(space, 0,
  544. IBUF_HEADER + IBUF_TREE_SEG_HEADER, mtr);
  545. #ifdef UNIV_SYNC_DEBUG
  546. buf_page_dbg_add_level(ibuf_hdr_frame, SYNC_TREE_NODE_NEW);
  547. #endif /* UNIV_SYNC_DEBUG */
  548. ut_ad(buf_frame_get_page_no(ibuf_hdr_frame)
  549.   == IBUF_HEADER_PAGE_NO);
  550. /* Allocate then the next page to the segment: it will be the
  551.   tree root page */
  552.   page_no = fseg_alloc_free_page(
  553. ibuf_hdr_frame + IBUF_HEADER
  554.   + IBUF_TREE_SEG_HEADER, IBUF_TREE_ROOT_PAGE_NO,
  555. FSP_UP, mtr);
  556. ut_ad(page_no == IBUF_TREE_ROOT_PAGE_NO);
  557. frame = buf_page_get(space, page_no, RW_X_LATCH, mtr);
  558. } else {
  559. frame = fseg_create(space, 0, PAGE_HEADER + PAGE_BTR_SEG_TOP,
  560. mtr);
  561. }
  562. if (frame == NULL) {
  563. return(FIL_NULL);
  564. }
  565. page_no = buf_frame_get_page_no(frame);
  566. #ifdef UNIV_SYNC_DEBUG
  567. buf_page_dbg_add_level(frame, SYNC_TREE_NODE_NEW);
  568. #endif /* UNIV_SYNC_DEBUG */
  569. if (type & DICT_IBUF) {
  570. /* It is an insert buffer tree: initialize the free list */
  571. ut_ad(page_no == IBUF_TREE_ROOT_PAGE_NO);
  572. flst_init(frame + PAGE_HEADER + PAGE_BTR_IBUF_FREE_LIST, mtr);
  573. } else {
  574. /* It is a non-ibuf tree: create a file segment for leaf
  575. pages */
  576. fseg_create(space, page_no, PAGE_HEADER + PAGE_BTR_SEG_LEAF,
  577. mtr);
  578. /* The fseg create acquires a second latch on the page,
  579. therefore we must declare it: */
  580. #ifdef UNIV_SYNC_DEBUG
  581. buf_page_dbg_add_level(frame, SYNC_TREE_NODE_NEW);
  582. #endif /* UNIV_SYNC_DEBUG */
  583. }
  584. /* Create a new index page on the the allocated segment page */
  585. page = page_create(frame, mtr);
  586. buf_block_align(page)->check_index_page_at_flush = TRUE;
  587. /* Set the index id of the page */
  588. btr_page_set_index_id(page, index_id, mtr);
  589. /* Set the level of the new index page */
  590. btr_page_set_level(page, 0, mtr);
  591. /* Set the next node and previous node fields */
  592. btr_page_set_next(page, FIL_NULL, mtr);
  593. btr_page_set_prev(page, FIL_NULL, mtr);
  594. /* We reset the free bits for the page to allow creation of several
  595. trees in the same mtr, otherwise the latch on a bitmap page would
  596. prevent it because of the latching order */
  597. ibuf_reset_free_bits_with_type(type, page);
  598. /* In the following assertion we test that two records of maximum
  599. allowed size fit on the root page: this fact is needed to ensure
  600. correctness of split algorithms */
  601. ut_ad(page_get_max_insert_size(page, 2) > 2 * BTR_PAGE_MAX_REC_SIZE);
  602. return(page_no);
  603. }
  604. /****************************************************************
  605. Frees a B-tree except the root page, which MUST be freed after this
  606. by calling btr_free_root. */
  607. void
  608. btr_free_but_not_root(
  609. /*==================*/
  610. ulint space, /* in: space where created */
  611. ulint root_page_no) /* in: root page number */
  612. {
  613. ibool finished;
  614. page_t* root;
  615. mtr_t mtr;
  616. leaf_loop:
  617. mtr_start(&mtr);
  618. root = btr_page_get(space, root_page_no, RW_X_LATCH, &mtr);
  619. /* NOTE: page hash indexes are dropped when a page is freed inside
  620. fsp0fsp. */
  621. finished = fseg_free_step(
  622. root + PAGE_HEADER + PAGE_BTR_SEG_LEAF, &mtr);
  623. mtr_commit(&mtr);
  624. if (!finished) {
  625. goto leaf_loop;
  626. }
  627. top_loop:
  628. mtr_start(&mtr);
  629. root = btr_page_get(space, root_page_no, RW_X_LATCH, &mtr);
  630. finished = fseg_free_step_not_header(
  631. root + PAGE_HEADER + PAGE_BTR_SEG_TOP, &mtr);
  632. mtr_commit(&mtr);
  633. if (!finished) {
  634. goto top_loop;
  635. }
  636. }
  637. /****************************************************************
  638. Frees the B-tree root page. Other tree MUST already have been freed. */
  639. void
  640. btr_free_root(
  641. /*==========*/
  642. ulint space, /* in: space where created */
  643. ulint root_page_no, /* in: root page number */
  644. mtr_t* mtr) /* in: a mini-transaction which has already
  645. been started */
  646. {
  647. ibool finished;
  648. page_t* root;
  649. root = btr_page_get(space, root_page_no, RW_X_LATCH, mtr);
  650. btr_search_drop_page_hash_index(root);
  651. top_loop:
  652. finished = fseg_free_step(
  653. root + PAGE_HEADER + PAGE_BTR_SEG_TOP, mtr);
  654. if (!finished) {
  655. goto top_loop;
  656. }
  657. }
  658. /*****************************************************************
  659. Reorganizes an index page. */
  660. static
  661. void
  662. btr_page_reorganize_low(
  663. /*====================*/
  664. ibool recovery,/* in: TRUE if called in recovery: locks should not
  665. be updated, i.e., there cannot exist locks on the
  666. page, and a hash index should not be dropped: it
  667. cannot exist */
  668. page_t* page, /* in: page to be reorganized */
  669. mtr_t* mtr) /* in: mtr */
  670. {
  671. page_t* new_page;
  672. ulint log_mode;
  673. ulint data_size1;
  674. ulint data_size2;
  675. ulint max_ins_size1;
  676. ulint max_ins_size2;
  677. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  678.        MTR_MEMO_PAGE_X_FIX));
  679. data_size1 = page_get_data_size(page);
  680. max_ins_size1 = page_get_max_insert_size_after_reorganize(page, 1);
  681. /* Write the log record */
  682. mlog_write_initial_log_record(page, MLOG_PAGE_REORGANIZE, mtr);
  683. /* Turn logging off */
  684. log_mode = mtr_set_log_mode(mtr, MTR_LOG_NONE);
  685. new_page = buf_frame_alloc();
  686. /* Copy the old page to temporary space */
  687. buf_frame_copy(new_page, page);
  688. if (!recovery) {
  689. btr_search_drop_page_hash_index(page);
  690. }
  691. /* Recreate the page: note that global data on page (possible
  692. segment headers, next page-field, etc.) is preserved intact */
  693. page_create(page, mtr);
  694. buf_block_align(page)->check_index_page_at_flush = TRUE;
  695. /* Copy the records from the temporary space to the recreated page;
  696. do not copy the lock bits yet */
  697. page_copy_rec_list_end_no_locks(page, new_page,
  698. page_get_infimum_rec(new_page), mtr);
  699. /* Copy max trx id to recreated page */
  700. page_set_max_trx_id(page, page_get_max_trx_id(new_page));
  701. if (!recovery) {
  702. /* Update the record lock bitmaps */
  703. lock_move_reorganize_page(page, new_page);
  704. }
  705. data_size2 = page_get_data_size(page);
  706. max_ins_size2 = page_get_max_insert_size_after_reorganize(page, 1);
  707. if (data_size1 != data_size2 || max_ins_size1 != max_ins_size2) {
  708. buf_page_print(page);
  709. buf_page_print(new_page);
  710.         fprintf(stderr,
  711. "InnoDB: Error: page old data size %lu new data size %lun"
  712. "InnoDB: Error: page old max ins size %lu new max ins size %lun"
  713. "InnoDB: Submit a detailed bug report to http://bugs.mysql.comn",
  714. (unsigned long) data_size1, (unsigned long) data_size2,
  715. (unsigned long) max_ins_size1,
  716. (unsigned long) max_ins_size2);
  717. }
  718. buf_frame_free(new_page);
  719. /* Restore logging mode */
  720. mtr_set_log_mode(mtr, log_mode);
  721. }
  722. /*****************************************************************
  723. Reorganizes an index page. */
  724. void
  725. btr_page_reorganize(
  726. /*================*/
  727. page_t* page, /* in: page to be reorganized */
  728. mtr_t* mtr) /* in: mtr */
  729. {
  730. btr_page_reorganize_low(FALSE, page, mtr);
  731. }
  732. /***************************************************************
  733. Parses a redo log record of reorganizing a page. */
  734. byte*
  735. btr_parse_page_reorganize(
  736. /*======================*/
  737. /* out: end of log record or NULL */
  738. byte* ptr, /* in: buffer */
  739. byte* end_ptr __attribute__((unused)), /* in: buffer end */
  740. page_t* page, /* in: page or NULL */
  741. mtr_t* mtr) /* in: mtr or NULL */
  742. {
  743. ut_ad(ptr && end_ptr);
  744. /* The record is empty, except for the record initial part */
  745. if (page) {
  746. btr_page_reorganize_low(TRUE, page, mtr);
  747. }
  748. return(ptr);
  749. }
  750. /*****************************************************************
  751. Empties an index page. */
  752. static
  753. void
  754. btr_page_empty(
  755. /*===========*/
  756. page_t* page, /* in: page to be emptied */
  757. mtr_t* mtr) /* in: mtr */
  758. {
  759. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  760.        MTR_MEMO_PAGE_X_FIX));
  761. btr_search_drop_page_hash_index(page);
  762. /* Recreate the page: note that global data on page (possible
  763. segment headers, next page-field, etc.) is preserved intact */
  764. page_create(page, mtr);
  765. buf_block_align(page)->check_index_page_at_flush = TRUE;
  766. }
  767. /*****************************************************************
  768. Makes tree one level higher by splitting the root, and inserts
  769. the tuple. It is assumed that mtr contains an x-latch on the tree.
  770. NOTE that the operation of this function must always succeed,
  771. we cannot reverse it: therefore enough free disk space must be
  772. guaranteed to be available before this function is called. */
  773. rec_t*
  774. btr_root_raise_and_insert(
  775. /*======================*/
  776. /* out: inserted record */
  777. btr_cur_t* cursor, /* in: cursor at which to insert: must be
  778. on the root page; when the function returns,
  779. the cursor is positioned on the predecessor
  780. of the inserted record */
  781. dtuple_t* tuple, /* in: tuple to insert */
  782. mtr_t* mtr) /* in: mtr */
  783. {
  784. dict_tree_t* tree;
  785. page_t* root;
  786. page_t* new_page;
  787. ulint new_page_no;
  788. rec_t* rec;
  789. mem_heap_t* heap;
  790. dtuple_t* node_ptr;
  791. ulint level;
  792. rec_t* node_ptr_rec;
  793. page_cur_t* page_cursor;
  794. root = btr_cur_get_page(cursor);
  795. tree = btr_cur_get_tree(cursor);
  796. ut_ad(dict_tree_get_page(tree) == buf_frame_get_page_no(root));
  797. ut_ad(mtr_memo_contains(mtr, dict_tree_get_lock(tree),
  798. MTR_MEMO_X_LOCK));
  799. ut_ad(mtr_memo_contains(mtr, buf_block_align(root),
  800.        MTR_MEMO_PAGE_X_FIX));
  801. btr_search_drop_page_hash_index(root);
  802. /* Allocate a new page to the tree. Root splitting is done by first
  803. moving the root records to the new page, emptying the root, putting
  804. a node pointer to the new page, and then splitting the new page. */
  805. new_page = btr_page_alloc(tree, 0, FSP_NO_DIR,
  806.   btr_page_get_level(root, mtr), mtr);
  807. btr_page_create(new_page, tree, mtr);
  808. level = btr_page_get_level(root, mtr);
  809. /* Set the levels of the new index page and root page */
  810. btr_page_set_level(new_page, level, mtr);
  811. btr_page_set_level(root, level + 1, mtr);
  812. /* Set the next node and previous node fields of new page */
  813. btr_page_set_next(new_page, FIL_NULL, mtr);
  814. btr_page_set_prev(new_page, FIL_NULL, mtr);
  815. /* Move the records from root to the new page */
  816. page_move_rec_list_end(new_page, root, page_get_infimum_rec(root),
  817. mtr);
  818. /* If this is a pessimistic insert which is actually done to
  819. perform a pessimistic update then we have stored the lock
  820. information of the record to be inserted on the infimum of the
  821. root page: we cannot discard the lock structs on the root page */
  822. lock_update_root_raise(new_page, root);
  823. /* Create a memory heap where the node pointer is stored */
  824. heap = mem_heap_create(100);
  825. rec = page_rec_get_next(page_get_infimum_rec(new_page));
  826. new_page_no = buf_frame_get_page_no(new_page);
  827. /* Build the node pointer (= node key and page address) for the
  828. child */
  829. node_ptr = dict_tree_build_node_ptr(tree, rec, new_page_no, heap,
  830.                           level);
  831. /* Reorganize the root to get free space */
  832. btr_page_reorganize(root, mtr);
  833. page_cursor = btr_cur_get_page_cur(cursor);
  834. /* Insert node pointer to the root */
  835. page_cur_set_before_first(root, page_cursor);
  836. node_ptr_rec = page_cur_tuple_insert(page_cursor, node_ptr, mtr);
  837. ut_ad(node_ptr_rec);
  838. /* The node pointer must be marked as the predefined minimum record,
  839. as there is no lower alphabetical limit to records in the leftmost
  840. node of a level: */
  841. btr_set_min_rec_mark(node_ptr_rec, mtr);
  842. /* Free the memory heap */
  843. mem_heap_free(heap);
  844. /* We play safe and reset the free bits for the new page */
  845. /* fprintf(stderr, "Root raise new page no %lun",
  846. buf_frame_get_page_no(new_page)); */
  847. ibuf_reset_free_bits(UT_LIST_GET_FIRST(tree->tree_indexes),
  848. new_page);
  849. /* Reposition the cursor to the child node */
  850. page_cur_search(new_page, tuple, PAGE_CUR_LE, page_cursor);
  851. /* Split the child and insert tuple */
  852. return(btr_page_split_and_insert(cursor, tuple, mtr));
  853. }
  854. /*****************************************************************
  855. Decides if the page should be split at the convergence point of inserts
  856. converging to the left. */
  857. ibool
  858. btr_page_get_split_rec_to_left(
  859. /*===========================*/
  860. /* out: TRUE if split recommended */
  861. btr_cur_t* cursor, /* in: cursor at which to insert */
  862. rec_t** split_rec) /* out: if split recommended,
  863. the first record on upper half page,
  864. or NULL if tuple to be inserted should
  865. be first */
  866. {
  867. page_t* page;
  868. rec_t* insert_point;
  869. rec_t* infimum;
  870. page = btr_cur_get_page(cursor);
  871. insert_point = btr_cur_get_rec(cursor);
  872. if (page_header_get_ptr(page, PAGE_LAST_INSERT)
  873.     == page_rec_get_next(insert_point)) {
  874.       infimum = page_get_infimum_rec(page);
  875. /* If the convergence is in the middle of a page, include also
  876. the record immediately before the new insert to the upper
  877. page. Otherwise, we could repeatedly move from page to page
  878. lots of records smaller than the convergence point. */
  879. if (infimum != insert_point
  880.     && page_rec_get_next(infimum) != insert_point) {
  881. *split_rec = insert_point;
  882. } else {
  883.       *split_rec = page_rec_get_next(insert_point);
  884.       }
  885. return(TRUE);
  886. }
  887. return(FALSE);
  888. }
  889. /*****************************************************************
  890. Decides if the page should be split at the convergence point of inserts
  891. converging to the right. */
  892. ibool
  893. btr_page_get_split_rec_to_right(
  894. /*============================*/
  895. /* out: TRUE if split recommended */
  896. btr_cur_t* cursor, /* in: cursor at which to insert */
  897. rec_t** split_rec) /* out: if split recommended,
  898. the first record on upper half page,
  899. or NULL if tuple to be inserted should
  900. be first */
  901. {
  902. page_t* page;
  903. rec_t* insert_point;
  904. rec_t* supremum;
  905. page = btr_cur_get_page(cursor);
  906. insert_point = btr_cur_get_rec(cursor);
  907. /* We use eager heuristics: if the new insert would be right after
  908. the previous insert on the same page, we assume that there is a
  909. pattern of sequential inserts here. */
  910. if (page_header_get_ptr(page, PAGE_LAST_INSERT) == insert_point) {
  911.       supremum = page_get_supremum_rec(page);
  912.        
  913. if (page_rec_get_next(insert_point) != supremum
  914.     && page_rec_get_next(page_rec_get_next(insert_point))
  915. != supremum) {
  916. /* If there are >= 2 user records up from the insert
  917. point, split all but 1 off. We want to keep one because
  918. then sequential inserts can use the adaptive hash
  919. index, as they can do the necessary checks of the right
  920. search position just by looking at the records on this
  921. page. */
  922. *split_rec = page_rec_get_next(
  923. page_rec_get_next(insert_point));
  924. } else {
  925. /* Else split at the new record to insert */
  926.       *split_rec = NULL;
  927.       }
  928. return(TRUE);
  929. }
  930. return(FALSE);
  931. }
  932. /*****************************************************************
  933. Calculates a split record such that the tuple will certainly fit on
  934. its half-page when the split is performed. We assume in this function
  935. only that the cursor page has at least one user record. */
  936. static
  937. rec_t*
  938. btr_page_get_sure_split_rec(
  939. /*========================*/
  940. /* out: split record, or NULL if
  941. tuple will be the first record on
  942. upper half-page */
  943. btr_cur_t* cursor, /* in: cursor at which insert
  944. should be made */
  945. dtuple_t* tuple) /* in: tuple to insert */
  946. {
  947. page_t* page;
  948. ulint insert_size;
  949. ulint free_space;
  950. ulint total_data;
  951. ulint total_n_recs;
  952. ulint total_space;
  953. ulint incl_data;
  954. rec_t* ins_rec;
  955. rec_t* rec;
  956. rec_t* next_rec;
  957. ulint n;
  958. page = btr_cur_get_page(cursor);
  959. insert_size = rec_get_converted_size(tuple);
  960. free_space  = page_get_free_space_of_empty();
  961. /* free_space is now the free space of a created new page */
  962. total_data   = page_get_data_size(page) + insert_size;
  963. total_n_recs = page_get_n_recs(page) + 1;
  964. ut_ad(total_n_recs >= 2);
  965. total_space  = total_data + page_dir_calc_reserved_space(total_n_recs);
  966. n = 0;
  967. incl_data = 0;
  968. ins_rec = btr_cur_get_rec(cursor);
  969. rec = page_get_infimum_rec(page);
  970. /* We start to include records to the left half, and when the
  971. space reserved by them exceeds half of total_space, then if
  972. the included records fit on the left page, they will be put there
  973. if something was left over also for the right page,
  974. otherwise the last included record will be the first on the right
  975. half page */
  976. for (;;) {
  977. /* Decide the next record to include */
  978. if (rec == ins_rec) {
  979. rec = NULL; /* NULL denotes that tuple is
  980. now included */
  981. } else if (rec == NULL) {
  982. rec = page_rec_get_next(ins_rec);
  983. } else {
  984. rec = page_rec_get_next(rec);
  985. }
  986. if (rec == NULL) {
  987. /* Include tuple */
  988. incl_data += insert_size;
  989. } else {
  990. incl_data += rec_get_size(rec);
  991. }
  992. n++;
  993. if (incl_data + page_dir_calc_reserved_space(n)
  994.                     >= total_space / 2) {
  995.                      if (incl_data + page_dir_calc_reserved_space(n)
  996.                          <= free_space) {
  997.                           /* The next record will be the first on
  998.                           the right half page if it is not the
  999.                           supremum record of page */
  1000. if (rec == ins_rec) {
  1001. next_rec = NULL;
  1002. } else if (rec == NULL) {
  1003. next_rec = page_rec_get_next(ins_rec);
  1004. } else {
  1005. next_rec = page_rec_get_next(rec);
  1006. }
  1007. if (next_rec != page_get_supremum_rec(page)) {
  1008. return(next_rec);
  1009. }
  1010.                      }
  1011. return(rec);
  1012. }
  1013. }
  1014. }
  1015. /*****************************************************************
  1016. Returns TRUE if the insert fits on the appropriate half-page with the
  1017. chosen split_rec. */
  1018. static
  1019. ibool
  1020. btr_page_insert_fits(
  1021. /*=================*/
  1022. /* out: TRUE if fits */
  1023. btr_cur_t* cursor, /* in: cursor at which insert
  1024. should be made */
  1025. rec_t* split_rec, /* in: suggestion for first record
  1026. on upper half-page, or NULL if
  1027. tuple to be inserted should be first */
  1028. dtuple_t* tuple) /* in: tuple to insert */
  1029. {
  1030. page_t* page;
  1031. ulint insert_size;
  1032. ulint free_space;
  1033. ulint total_data;
  1034. ulint total_n_recs;
  1035. rec_t* rec;
  1036. rec_t* end_rec;
  1037. page = btr_cur_get_page(cursor);
  1038. insert_size = rec_get_converted_size(tuple);
  1039. free_space  = page_get_free_space_of_empty();
  1040. /* free_space is now the free space of a created new page */
  1041. total_data   = page_get_data_size(page) + insert_size;
  1042. total_n_recs = page_get_n_recs(page) + 1;
  1043. /* We determine which records (from rec to end_rec, not including
  1044. end_rec) will end up on the other half page from tuple when it is
  1045. inserted. */
  1046. if (split_rec == NULL) {
  1047. rec = page_rec_get_next(page_get_infimum_rec(page));
  1048. end_rec = page_rec_get_next(btr_cur_get_rec(cursor));
  1049. } else if (cmp_dtuple_rec(tuple, split_rec) >= 0) {
  1050. rec = page_rec_get_next(page_get_infimum_rec(page));
  1051.   end_rec = split_rec;
  1052. } else {
  1053. rec = split_rec;
  1054. end_rec = page_get_supremum_rec(page);
  1055. }
  1056. if (total_data + page_dir_calc_reserved_space(total_n_recs)
  1057.     <= free_space) {
  1058. /* Ok, there will be enough available space on the
  1059. half page where the tuple is inserted */
  1060. return(TRUE);
  1061. }
  1062. while (rec != end_rec) {
  1063. /* In this loop we calculate the amount of reserved
  1064. space after rec is removed from page. */
  1065. total_data -= rec_get_size(rec);
  1066. total_n_recs--;
  1067. if (total_data + page_dir_calc_reserved_space(total_n_recs)
  1068.                     <= free_space) {
  1069. /* Ok, there will be enough available space on the
  1070. half page where the tuple is inserted */
  1071. return(TRUE);
  1072. }
  1073. rec = page_rec_get_next(rec);
  1074. }
  1075. return(FALSE);
  1076. }
  1077. /***********************************************************
  1078. Inserts a data tuple to a tree on a non-leaf level. It is assumed
  1079. that mtr holds an x-latch on the tree. */
  1080. void
  1081. btr_insert_on_non_leaf_level(
  1082. /*=========================*/
  1083. dict_tree_t* tree, /* in: tree */
  1084. ulint level, /* in: level, must be > 0 */
  1085. dtuple_t* tuple, /* in: the record to be inserted */
  1086. mtr_t* mtr) /* in: mtr */
  1087. {
  1088. big_rec_t* dummy_big_rec;
  1089. btr_cur_t cursor;
  1090. ulint err;
  1091. rec_t* rec;
  1092. ut_ad(level > 0);
  1093. /* In the following, choose just any index from the tree as the
  1094. first parameter for btr_cur_search_to_nth_level. */
  1095. btr_cur_search_to_nth_level(UT_LIST_GET_FIRST(tree->tree_indexes),
  1096.     level, tuple, PAGE_CUR_LE,
  1097.     BTR_CONT_MODIFY_TREE,
  1098.     &cursor, 0, mtr);
  1099. err = btr_cur_pessimistic_insert(BTR_NO_LOCKING_FLAG
  1100. | BTR_KEEP_SYS_FLAG
  1101. | BTR_NO_UNDO_LOG_FLAG,
  1102. &cursor, tuple,
  1103. &rec, &dummy_big_rec, NULL, mtr);
  1104. ut_a(err == DB_SUCCESS);
  1105. }
  1106. /******************************************************************
  1107. Attaches the halves of an index page on the appropriate level in an
  1108. index tree. */
  1109. static
  1110. void
  1111. btr_attach_half_pages(
  1112. /*==================*/
  1113. dict_tree_t* tree, /* in: the index tree */
  1114. page_t* page, /* in: page to be split */
  1115. rec_t* split_rec, /* in: first record on upper
  1116. half page */
  1117. page_t* new_page, /* in: the new half page */
  1118. ulint direction, /* in: FSP_UP or FSP_DOWN */
  1119. mtr_t* mtr) /* in: mtr */
  1120. {
  1121. ulint space;
  1122. rec_t* node_ptr;
  1123. page_t* prev_page;
  1124. page_t* next_page;
  1125. ulint prev_page_no;
  1126. ulint next_page_no;
  1127. ulint level;
  1128. page_t* lower_page;
  1129. page_t* upper_page;
  1130. ulint lower_page_no;
  1131. ulint upper_page_no;
  1132. dtuple_t* node_ptr_upper;
  1133. mem_heap_t*  heap;
  1134. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  1135.        MTR_MEMO_PAGE_X_FIX));
  1136. ut_ad(mtr_memo_contains(mtr, buf_block_align(new_page),
  1137.        MTR_MEMO_PAGE_X_FIX));
  1138. /* Based on split direction, decide upper and lower pages */
  1139. if (direction == FSP_DOWN) {
  1140. lower_page_no = buf_frame_get_page_no(new_page);
  1141. upper_page_no = buf_frame_get_page_no(page);
  1142. lower_page = new_page;
  1143. upper_page = page;
  1144. /* Look from the tree for the node pointer to page */
  1145. node_ptr = btr_page_get_father_node_ptr(tree, page, mtr);
  1146. /* Replace the address of the old child node (= page) with the 
  1147. address of the new lower half */
  1148. btr_node_ptr_set_child_page_no(node_ptr, lower_page_no, mtr);
  1149. } else {
  1150. lower_page_no = buf_frame_get_page_no(page);
  1151. upper_page_no = buf_frame_get_page_no(new_page);
  1152. lower_page = page;
  1153. upper_page = new_page;
  1154. }
  1155.    
  1156. /* Create a memory heap where the data tuple is stored */
  1157. heap = mem_heap_create(100);
  1158. /* Get the level of the split pages */
  1159. level = btr_page_get_level(page, mtr);
  1160. /* Build the node pointer (= node key and page address) for the upper
  1161. half */
  1162. node_ptr_upper = dict_tree_build_node_ptr(tree, split_rec,
  1163.      upper_page_no, heap, level);
  1164. /* Insert it next to the pointer to the lower half. Note that this
  1165. may generate recursion leading to a split on the higher level. */
  1166. btr_insert_on_non_leaf_level(tree, level + 1, node_ptr_upper, mtr);
  1167. /* Free the memory heap */
  1168. mem_heap_free(heap);
  1169. /* Get the previous and next pages of page */
  1170. prev_page_no = btr_page_get_prev(page, mtr);
  1171. next_page_no = btr_page_get_next(page, mtr);
  1172. space = buf_frame_get_space_id(page);
  1173. /* Update page links of the level */
  1174. if (prev_page_no != FIL_NULL) {
  1175. prev_page = btr_page_get(space, prev_page_no, RW_X_LATCH, mtr);
  1176. btr_page_set_next(prev_page, lower_page_no, mtr);
  1177. }
  1178. if (next_page_no != FIL_NULL) {
  1179. next_page = btr_page_get(space, next_page_no, RW_X_LATCH, mtr);
  1180. btr_page_set_prev(next_page, upper_page_no, mtr);
  1181. }
  1182. btr_page_set_prev(lower_page, prev_page_no, mtr);
  1183. btr_page_set_next(lower_page, upper_page_no, mtr);
  1184. btr_page_set_level(lower_page, level, mtr);
  1185. btr_page_set_prev(upper_page, lower_page_no, mtr);
  1186. btr_page_set_next(upper_page, next_page_no, mtr);
  1187. btr_page_set_level(upper_page, level, mtr);
  1188. }
  1189. /*****************************************************************
  1190. Splits an index page to halves and inserts the tuple. It is assumed
  1191. that mtr holds an x-latch to the index tree. NOTE: the tree x-latch
  1192. is released within this function! NOTE that the operation of this
  1193. function must always succeed, we cannot reverse it: therefore
  1194. enough free disk space must be guaranteed to be available before
  1195. this function is called. */
  1196. rec_t*
  1197. btr_page_split_and_insert(
  1198. /*======================*/
  1199. /* out: inserted record; NOTE: the tree
  1200. x-latch is released! NOTE: 2 free disk
  1201. pages must be available! */
  1202. btr_cur_t* cursor, /* in: cursor at which to insert; when the
  1203. function returns, the cursor is positioned
  1204. on the predecessor of the inserted record */
  1205. dtuple_t* tuple, /* in: tuple to insert */
  1206. mtr_t* mtr) /* in: mtr */
  1207. {
  1208. dict_tree_t* tree;
  1209. page_t* page;
  1210. ulint page_no;
  1211. byte direction;
  1212. ulint hint_page_no;
  1213. page_t* new_page;
  1214. rec_t* split_rec;
  1215. page_t* left_page;
  1216. page_t* right_page;
  1217. page_t* insert_page;
  1218. page_cur_t* page_cursor;
  1219. rec_t* first_rec;
  1220. byte* buf = 0; /* remove warning */
  1221. rec_t* move_limit;
  1222. ibool insert_will_fit;
  1223. ulint n_iterations = 0;
  1224. rec_t* rec;
  1225. func_start:
  1226. tree = btr_cur_get_tree(cursor);
  1227. ut_ad(mtr_memo_contains(mtr, dict_tree_get_lock(tree),
  1228. MTR_MEMO_X_LOCK));
  1229. #ifdef UNIV_SYNC_DEBUG
  1230. ut_ad(rw_lock_own(dict_tree_get_lock(tree), RW_LOCK_EX));
  1231. #endif /* UNIV_SYNC_DEBUG */
  1232. page = btr_cur_get_page(cursor);
  1233. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  1234.        MTR_MEMO_PAGE_X_FIX));
  1235. ut_ad(page_get_n_recs(page) >= 2);
  1236. page_no = buf_frame_get_page_no(page);
  1237. /* 1. Decide the split record; split_rec == NULL means that the
  1238. tuple to be inserted should be the first record on the upper
  1239. half-page */
  1240. if (n_iterations > 0) {
  1241. direction = FSP_UP;
  1242. hint_page_no = page_no + 1;
  1243. split_rec = btr_page_get_sure_split_rec(cursor, tuple);
  1244. } else if (btr_page_get_split_rec_to_right(cursor, &split_rec)) {
  1245. direction = FSP_UP;
  1246. hint_page_no = page_no + 1;
  1247. } else if (btr_page_get_split_rec_to_left(cursor, &split_rec)) {
  1248. direction = FSP_DOWN;
  1249. hint_page_no = page_no - 1;
  1250. } else {
  1251. direction = FSP_UP;
  1252. hint_page_no = page_no + 1;
  1253. split_rec = page_get_middle_rec(page);
  1254. }
  1255. /* 2. Allocate a new page to the tree */
  1256. new_page = btr_page_alloc(tree, hint_page_no, direction,
  1257. btr_page_get_level(page, mtr), mtr);
  1258. btr_page_create(new_page, tree, mtr);
  1259. /* 3. Calculate the first record on the upper half-page, and the
  1260. first record (move_limit) on original page which ends up on the
  1261. upper half */
  1262. if (split_rec != NULL) {
  1263. first_rec = split_rec;
  1264. move_limit = split_rec;
  1265. } else {
  1266. buf = mem_alloc(rec_get_converted_size(tuple));
  1267. first_rec = rec_convert_dtuple_to_rec(buf, tuple);
  1268. move_limit = page_rec_get_next(btr_cur_get_rec(cursor));
  1269. }
  1270. /* 4. Do first the modifications in the tree structure */
  1271. btr_attach_half_pages(tree, page, first_rec, new_page, direction, mtr);
  1272. if (split_rec == NULL) {
  1273. mem_free(buf);
  1274. }
  1275. /* If the split is made on the leaf level and the insert will fit
  1276. on the appropriate half-page, we may release the tree x-latch.
  1277. We can then move the records after releasing the tree latch,
  1278. thus reducing the tree latch contention. */
  1279. insert_will_fit = btr_page_insert_fits(cursor, split_rec, tuple);
  1280. if (insert_will_fit && (btr_page_get_level(page, mtr) == 0)) {
  1281. mtr_memo_release(mtr, dict_tree_get_lock(tree),
  1282. MTR_MEMO_X_LOCK);
  1283. }
  1284. /* 5. Move then the records to the new page */
  1285. if (direction == FSP_DOWN) {
  1286. /* fputs("Split leftn", stderr); */
  1287. page_move_rec_list_start(new_page, page, move_limit, mtr);
  1288. left_page = new_page;
  1289. right_page = page;
  1290. lock_update_split_left(right_page, left_page);
  1291. } else {
  1292. /* fputs("Split rightn", stderr); */
  1293. page_move_rec_list_end(new_page, page, move_limit, mtr);
  1294. left_page = page;
  1295. right_page = new_page;
  1296. lock_update_split_right(right_page, left_page);
  1297. }
  1298. /* 6. The split and the tree modification is now completed. Decide the
  1299. page where the tuple should be inserted */
  1300. if (split_rec == NULL) {
  1301. insert_page = right_page;
  1302. } else if (cmp_dtuple_rec(tuple, first_rec) >= 0) {
  1303. insert_page = right_page;
  1304. } else {
  1305. insert_page = left_page;
  1306. }
  1307. /* 7. Reposition the cursor for insert and try insertion */
  1308. page_cursor = btr_cur_get_page_cur(cursor);
  1309. page_cur_search(insert_page, tuple, PAGE_CUR_LE, page_cursor);
  1310. rec = page_cur_tuple_insert(page_cursor, tuple, mtr);
  1311. if (rec != NULL) {
  1312. /* Insert fit on the page: update the free bits for the
  1313. left and right pages in the same mtr */
  1314. ibuf_update_free_bits_for_two_pages_low(cursor->index,
  1315. left_page,
  1316. right_page, mtr);
  1317. /* fprintf(stderr, "Split and insert done %lu %lun",
  1318. buf_frame_get_page_no(left_page),
  1319. buf_frame_get_page_no(right_page)); */
  1320. return(rec);
  1321. }
  1322. /* 8. If insert did not fit, try page reorganization */
  1323. btr_page_reorganize(insert_page, mtr);
  1324. page_cur_search(insert_page, tuple, PAGE_CUR_LE, page_cursor);
  1325. rec = page_cur_tuple_insert(page_cursor, tuple, mtr);
  1326. if (rec == NULL) {
  1327. /* The insert did not fit on the page: loop back to the
  1328. start of the function for a new split */
  1329. /* We play safe and reset the free bits for new_page */
  1330. ibuf_reset_free_bits(cursor->index, new_page);
  1331. /* fprintf(stderr, "Split second round %lun",
  1332. buf_frame_get_page_no(page)); */
  1333. n_iterations++;
  1334. ut_ad(n_iterations < 2);
  1335. ut_ad(!insert_will_fit);
  1336. goto func_start;
  1337. }
  1338. /* Insert fit on the page: update the free bits for the
  1339. left and right pages in the same mtr */
  1340. ibuf_update_free_bits_for_two_pages_low(cursor->index, left_page,
  1341. right_page, mtr);
  1342. /* fprintf(stderr, "Split and insert done %lu %lun",
  1343. buf_frame_get_page_no(left_page),
  1344. buf_frame_get_page_no(right_page)); */
  1345. ut_ad(page_validate(left_page, UT_LIST_GET_FIRST(tree->tree_indexes)));
  1346. ut_ad(page_validate(right_page, UT_LIST_GET_FIRST(tree->tree_indexes)));
  1347. return(rec);
  1348. }
  1349. /*****************************************************************
  1350. Removes a page from the level list of pages. */
  1351. static
  1352. void
  1353. btr_level_list_remove(
  1354. /*==================*/
  1355. dict_tree_t* tree __attribute__((unused)), /* in: index tree */
  1356. page_t* page, /* in: page to remove */
  1357. mtr_t* mtr) /* in: mtr */
  1358. {
  1359. ulint space;
  1360. ulint prev_page_no;
  1361. page_t* prev_page;
  1362. ulint next_page_no;
  1363. page_t* next_page;
  1364. ut_ad(tree && page && mtr);
  1365. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  1366.        MTR_MEMO_PAGE_X_FIX));
  1367. /* Get the previous and next page numbers of page */
  1368. prev_page_no = btr_page_get_prev(page, mtr);
  1369. next_page_no = btr_page_get_next(page, mtr);
  1370. space = buf_frame_get_space_id(page);
  1371. /* Update page links of the level */
  1372. if (prev_page_no != FIL_NULL) {
  1373. prev_page = btr_page_get(space, prev_page_no, RW_X_LATCH, mtr);
  1374. btr_page_set_next(prev_page, next_page_no, mtr);
  1375. }
  1376. if (next_page_no != FIL_NULL) {
  1377. next_page = btr_page_get(space, next_page_no, RW_X_LATCH, mtr);
  1378. btr_page_set_prev(next_page, prev_page_no, mtr);
  1379. }
  1380. }
  1381. /********************************************************************
  1382. Writes the redo log record for setting an index record as the predefined
  1383. minimum record. */
  1384. UNIV_INLINE
  1385. void
  1386. btr_set_min_rec_mark_log(
  1387. /*=====================*/
  1388. rec_t* rec, /* in: record */
  1389. mtr_t* mtr) /* in: mtr */
  1390. {
  1391. mlog_write_initial_log_record(rec, MLOG_REC_MIN_MARK, mtr);
  1392. /* Write rec offset as a 2-byte ulint */
  1393. mlog_catenate_ulint(mtr, rec - buf_frame_align(rec), MLOG_2BYTES);
  1394. }
  1395. /********************************************************************
  1396. Parses the redo log record for setting an index record as the predefined
  1397. minimum record. */
  1398. byte*
  1399. btr_parse_set_min_rec_mark(
  1400. /*=======================*/
  1401. /* out: end of log record or NULL */
  1402. byte* ptr, /* in: buffer */
  1403. byte* end_ptr,/* in: buffer end */
  1404. page_t* page, /* in: page or NULL */
  1405. mtr_t* mtr) /* in: mtr or NULL */
  1406. {
  1407. rec_t* rec;
  1408. if (end_ptr < ptr + 2) {
  1409. return(NULL);
  1410. }
  1411. if (page) {
  1412. rec = page + mach_read_from_2(ptr);
  1413. btr_set_min_rec_mark(rec, mtr);
  1414. }
  1415. return(ptr + 2);
  1416. }
  1417. /********************************************************************
  1418. Sets a record as the predefined minimum record. */
  1419. void
  1420. btr_set_min_rec_mark(
  1421. /*=================*/
  1422. rec_t* rec, /* in: record */
  1423. mtr_t* mtr) /* in: mtr */
  1424. {
  1425. ulint info_bits;
  1426. info_bits = rec_get_info_bits(rec);
  1427. rec_set_info_bits(rec, info_bits | REC_INFO_MIN_REC_FLAG);
  1428. btr_set_min_rec_mark_log(rec, mtr);
  1429. }
  1430. /*****************************************************************
  1431. Deletes on the upper level the node pointer to a page. */
  1432. void
  1433. btr_node_ptr_delete(
  1434. /*================*/
  1435. dict_tree_t* tree, /* in: index tree */
  1436. page_t* page, /* in: page whose node pointer is deleted */
  1437. mtr_t* mtr) /* in: mtr */
  1438. {
  1439. rec_t* node_ptr;
  1440. btr_cur_t cursor;
  1441. ibool compressed;
  1442. ulint err;
  1443. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  1444. MTR_MEMO_PAGE_X_FIX));
  1445. /* Delete node pointer on father page */
  1446. node_ptr = btr_page_get_father_node_ptr(tree, page, mtr);
  1447. btr_cur_position(UT_LIST_GET_FIRST(tree->tree_indexes), node_ptr,
  1448. &cursor);
  1449. compressed = btr_cur_pessimistic_delete(&err, TRUE, &cursor, FALSE,
  1450. mtr);
  1451. ut_a(err == DB_SUCCESS);
  1452. if (!compressed) {
  1453. btr_cur_compress_if_useful(&cursor, mtr);
  1454. }
  1455. }
  1456. /*****************************************************************
  1457. If page is the only on its level, this function moves its records to the
  1458. father page, thus reducing the tree height. */
  1459. static
  1460. void
  1461. btr_lift_page_up(
  1462. /*=============*/
  1463. dict_tree_t* tree, /* in: index tree */
  1464. page_t* page, /* in: page which is the only on its level;
  1465. must not be empty: use
  1466. btr_discard_only_page_on_level if the last
  1467. record from the page should be removed */
  1468. mtr_t* mtr) /* in: mtr */
  1469. {
  1470. rec_t* node_ptr;
  1471. page_t* father_page;
  1472. ulint page_level;
  1473. ut_ad(btr_page_get_prev(page, mtr) == FIL_NULL);
  1474. ut_ad(btr_page_get_next(page, mtr) == FIL_NULL);
  1475. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  1476.        MTR_MEMO_PAGE_X_FIX));
  1477. node_ptr = btr_page_get_father_node_ptr(tree, page, mtr);
  1478. father_page = buf_frame_align(node_ptr);
  1479. page_level = btr_page_get_level(page, mtr);
  1480. btr_search_drop_page_hash_index(page);
  1481. /* Make the father empty */
  1482. btr_page_empty(father_page, mtr);
  1483. /* Move records to the father */
  1484.   page_copy_rec_list_end(father_page, page, page_get_infimum_rec(page),
  1485. mtr);
  1486. lock_update_copy_and_discard(father_page, page);
  1487. btr_page_set_level(father_page, page_level, mtr);
  1488. /* Free the file page */
  1489. btr_page_free(tree, page, mtr);
  1490. /* We play safe and reset the free bits for the father */
  1491. ibuf_reset_free_bits(UT_LIST_GET_FIRST(tree->tree_indexes),
  1492. father_page);
  1493. ut_ad(page_validate(father_page,
  1494. UT_LIST_GET_FIRST(tree->tree_indexes)));
  1495. ut_ad(btr_check_node_ptr(tree, father_page, mtr));
  1496. }
  1497. /*****************************************************************
  1498. Tries to merge the page first to the left immediate brother if such a
  1499. brother exists, and the node pointers to the current page and to the brother
  1500. reside on the same page. If the left brother does not satisfy these
  1501. conditions, looks at the right brother. If the page is the only one on that
  1502. level lifts the records of the page to the father page, thus reducing the
  1503. tree height. It is assumed that mtr holds an x-latch on the tree and on the
  1504. page. If cursor is on the leaf level, mtr must also hold x-latches to the
  1505. brothers, if they exist. NOTE: it is assumed that the caller has reserved
  1506. enough free extents so that the compression will always succeed if done! */
  1507. void
  1508. btr_compress(
  1509. /*=========*/
  1510. btr_cur_t* cursor, /* in: cursor on the page to merge or lift;
  1511. the page must not be empty: in record delete
  1512. use btr_discard_page if the page would become
  1513. empty */
  1514. mtr_t* mtr) /* in: mtr */
  1515. {
  1516. dict_tree_t* tree;
  1517. ulint space;
  1518. ulint left_page_no;
  1519. ulint right_page_no;
  1520. page_t* merge_page;
  1521. page_t* father_page;
  1522. ibool is_left;
  1523. page_t* page;
  1524. rec_t* orig_pred;
  1525. rec_t* orig_succ;
  1526. rec_t* node_ptr;
  1527. ulint data_size;
  1528. ulint n_recs;
  1529. ulint max_ins_size;
  1530. ulint max_ins_size_reorg;
  1531. ulint level;
  1532. page = btr_cur_get_page(cursor);
  1533. tree = btr_cur_get_tree(cursor);
  1534. ut_ad(mtr_memo_contains(mtr, dict_tree_get_lock(tree),
  1535. MTR_MEMO_X_LOCK));
  1536. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  1537. MTR_MEMO_PAGE_X_FIX));
  1538. level = btr_page_get_level(page, mtr);
  1539. space = dict_tree_get_space(tree);
  1540. left_page_no = btr_page_get_prev(page, mtr);
  1541. right_page_no = btr_page_get_next(page, mtr);
  1542. /* fprintf(stderr, "Merge left page %lu right %lu n", left_page_no,
  1543. right_page_no); */
  1544. node_ptr = btr_page_get_father_node_ptr(tree, page, mtr);
  1545. father_page = buf_frame_align(node_ptr);
  1546. /* Decide the page to which we try to merge and which will inherit
  1547. the locks */
  1548. if (left_page_no != FIL_NULL) {
  1549. is_left = TRUE;
  1550. merge_page = btr_page_get(space, left_page_no, RW_X_LATCH,
  1551. mtr);
  1552. } else if (right_page_no != FIL_NULL) {
  1553. is_left = FALSE;
  1554. merge_page = btr_page_get(space, right_page_no, RW_X_LATCH,
  1555. mtr);
  1556. } else {
  1557. /* The page is the only one on the level, lift the records
  1558. to the father */
  1559. btr_lift_page_up(tree, page, mtr);
  1560. return;
  1561. }
  1562. n_recs = page_get_n_recs(page);
  1563. data_size = page_get_data_size(page);
  1564. max_ins_size_reorg = page_get_max_insert_size_after_reorganize(
  1565. merge_page, n_recs);
  1566. if (data_size > max_ins_size_reorg) {
  1567. /* No space for merge */
  1568. return;
  1569. }
  1570. ut_ad(page_validate(merge_page, cursor->index));
  1571. max_ins_size = page_get_max_insert_size(merge_page, n_recs);
  1572. if (data_size > max_ins_size) {
  1573. /* We have to reorganize merge_page */
  1574. btr_page_reorganize(merge_page, mtr);
  1575. max_ins_size = page_get_max_insert_size(merge_page, n_recs);
  1576. ut_ad(page_validate(merge_page, cursor->index));
  1577. ut_ad(page_get_max_insert_size(merge_page, n_recs)
  1578. == max_ins_size_reorg);
  1579. }
  1580. if (data_size > max_ins_size) {
  1581. /* Add fault tolerance, though this should never happen */
  1582. return;
  1583. }
  1584. btr_search_drop_page_hash_index(page);
  1585. /* Remove the page from the level list */
  1586. btr_level_list_remove(tree, page, mtr);
  1587. if (is_left) {
  1588. btr_node_ptr_delete(tree, page, mtr);
  1589. } else {
  1590. /* Replace the address of the old child node (= page) with the 
  1591. address of the merge page to the right */
  1592. btr_node_ptr_set_child_page_no(node_ptr, right_page_no, mtr);
  1593. btr_node_ptr_delete(tree, merge_page, mtr);
  1594. }
  1595. /* Move records to the merge page */
  1596. if (is_left) {
  1597. orig_pred = page_rec_get_prev(
  1598. page_get_supremum_rec(merge_page));
  1599. page_copy_rec_list_start(merge_page, page,
  1600. page_get_supremum_rec(page), mtr);
  1601. lock_update_merge_left(merge_page, orig_pred, page);
  1602. } else {
  1603. orig_succ = page_rec_get_next(
  1604. page_get_infimum_rec(merge_page));
  1605. page_copy_rec_list_end(merge_page, page,
  1606. page_get_infimum_rec(page), mtr);
  1607. lock_update_merge_right(orig_succ, page);
  1608. }
  1609. /* We have added new records to merge_page: update its free bits */
  1610. ibuf_update_free_bits_if_full(cursor->index, merge_page,
  1611. UNIV_PAGE_SIZE, ULINT_UNDEFINED);
  1612. ut_ad(page_validate(merge_page, cursor->index));
  1613. /* Free the file page */
  1614. btr_page_free(tree, page, mtr);
  1615. ut_ad(btr_check_node_ptr(tree, merge_page, mtr));
  1616. }
  1617. /*****************************************************************
  1618. Discards a page that is the only page on its level. */
  1619. static
  1620. void
  1621. btr_discard_only_page_on_level(
  1622. /*===========================*/
  1623. dict_tree_t* tree, /* in: index tree */
  1624. page_t* page, /* in: page which is the only on its level */
  1625. mtr_t* mtr) /* in: mtr */
  1626. {
  1627. rec_t* node_ptr;
  1628. page_t* father_page;
  1629. ulint page_level;
  1630. ut_ad(btr_page_get_prev(page, mtr) == FIL_NULL);
  1631. ut_ad(btr_page_get_next(page, mtr) == FIL_NULL);
  1632. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  1633. MTR_MEMO_PAGE_X_FIX));
  1634. btr_search_drop_page_hash_index(page);
  1635. node_ptr = btr_page_get_father_node_ptr(tree, page, mtr);
  1636. father_page = buf_frame_align(node_ptr);
  1637. page_level = btr_page_get_level(page, mtr);
  1638. lock_update_discard(page_get_supremum_rec(father_page), page);
  1639. btr_page_set_level(father_page, page_level, mtr);
  1640. /* Free the file page */
  1641. btr_page_free(tree, page, mtr);
  1642. if (buf_frame_get_page_no(father_page) == dict_tree_get_page(tree)) {
  1643. /* The father is the root page */
  1644. btr_page_empty(father_page, mtr);
  1645. /* We play safe and reset the free bits for the father */
  1646. ibuf_reset_free_bits(UT_LIST_GET_FIRST(tree->tree_indexes),
  1647. father_page);
  1648. } else {
  1649. ut_ad(page_get_n_recs(father_page) == 1);
  1650. btr_discard_only_page_on_level(tree, father_page, mtr);
  1651. }
  1652. }
  1653. /*****************************************************************
  1654. Discards a page from a B-tree. This is used to remove the last record from
  1655. a B-tree page: the whole page must be removed at the same time. This cannot
  1656. be used for the root page, which is allowed to be empty. */
  1657. void
  1658. btr_discard_page(
  1659. /*=============*/
  1660. btr_cur_t* cursor, /* in: cursor on the page to discard: not on
  1661. the root page */
  1662. mtr_t* mtr) /* in: mtr */
  1663. {
  1664. dict_tree_t* tree;
  1665. ulint space;
  1666. ulint left_page_no;
  1667. ulint right_page_no;
  1668. page_t* merge_page;
  1669. ibool is_left;
  1670. page_t* page;
  1671. rec_t* node_ptr;
  1672. page = btr_cur_get_page(cursor);
  1673. tree = btr_cur_get_tree(cursor);
  1674. ut_ad(dict_tree_get_page(tree) != buf_frame_get_page_no(page));
  1675. ut_ad(mtr_memo_contains(mtr, dict_tree_get_lock(tree),
  1676. MTR_MEMO_X_LOCK));
  1677. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  1678. MTR_MEMO_PAGE_X_FIX));
  1679. space = dict_tree_get_space(tree);
  1680. /* Decide the page which will inherit the locks */
  1681. left_page_no = btr_page_get_prev(page, mtr);
  1682. right_page_no = btr_page_get_next(page, mtr);
  1683. if (left_page_no != FIL_NULL) {
  1684. is_left = TRUE;
  1685. merge_page = btr_page_get(space, left_page_no, RW_X_LATCH,
  1686. mtr);
  1687. } else if (right_page_no != FIL_NULL) {
  1688. is_left = FALSE;
  1689. merge_page = btr_page_get(space, right_page_no, RW_X_LATCH,
  1690. mtr);
  1691. } else {
  1692. btr_discard_only_page_on_level(tree, page, mtr);
  1693. return;
  1694. }
  1695. btr_search_drop_page_hash_index(page);
  1696. if (left_page_no == FIL_NULL && btr_page_get_level(page, mtr) > 0) {
  1697. /* We have to mark the leftmost node pointer on the right
  1698. side page as the predefined minimum record */
  1699. node_ptr = page_rec_get_next(page_get_infimum_rec(merge_page));
  1700. ut_ad(node_ptr != page_get_supremum_rec(merge_page));
  1701. btr_set_min_rec_mark(node_ptr, mtr);
  1702. }
  1703. btr_node_ptr_delete(tree, page, mtr);
  1704. /* Remove the page from the level list */
  1705. btr_level_list_remove(tree, page, mtr);
  1706. if (is_left) {
  1707. lock_update_discard(page_get_supremum_rec(merge_page), page);
  1708. } else {
  1709. lock_update_discard(page_rec_get_next(
  1710.     page_get_infimum_rec(merge_page)), page);
  1711. }
  1712. /* Free the file page */
  1713. btr_page_free(tree, page, mtr);
  1714. ut_ad(btr_check_node_ptr(tree, merge_page, mtr));
  1715. }
  1716. /*****************************************************************
  1717. Prints size info of a B-tree. */
  1718. void
  1719. btr_print_size(
  1720. /*===========*/
  1721. dict_tree_t* tree) /* in: index tree */
  1722. {
  1723. page_t* root;
  1724. fseg_header_t* seg;
  1725. mtr_t mtr;
  1726. if (tree->type & DICT_IBUF) {
  1727. fputs(
  1728. "Sorry, cannot print info of an ibuf tree: use ibuf functionsn",
  1729. stderr);
  1730. return;
  1731. }
  1732. mtr_start(&mtr);
  1733. root = btr_root_get(tree, &mtr);
  1734. seg = root + PAGE_HEADER + PAGE_BTR_SEG_TOP;
  1735. fputs("INFO OF THE NON-LEAF PAGE SEGMENTn", stderr);
  1736. fseg_print(seg, &mtr);
  1737. if (!(tree->type & DICT_UNIVERSAL)) {
  1738. seg = root + PAGE_HEADER + PAGE_BTR_SEG_LEAF;
  1739. fputs("INFO OF THE LEAF PAGE SEGMENTn", stderr);
  1740. fseg_print(seg, &mtr);
  1741. }
  1742. mtr_commit(&mtr); 
  1743. }
  1744. /****************************************************************
  1745. Prints recursively index tree pages. */
  1746. static
  1747. void
  1748. btr_print_recursive(
  1749. /*================*/
  1750. dict_tree_t* tree, /* in: index tree */
  1751. page_t* page, /* in: index page */
  1752. ulint width, /* in: print this many entries from start
  1753. and end */
  1754. mtr_t* mtr) /* in: mtr */
  1755. {
  1756. page_cur_t cursor;
  1757. ulint n_recs;
  1758. ulint i = 0;
  1759. mtr_t mtr2;
  1760. rec_t* node_ptr;
  1761. page_t* child;
  1762. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  1763. MTR_MEMO_PAGE_X_FIX));
  1764. fprintf(stderr, "NODE ON LEVEL %lu page number %lun",
  1765.        (ulong) btr_page_get_level(page, mtr),
  1766.        (ulong) buf_frame_get_page_no(page));
  1767. page_print(page, width, width);
  1768. n_recs = page_get_n_recs(page);
  1769. page_cur_set_before_first(page, &cursor);
  1770. page_cur_move_to_next(&cursor);
  1771. while (!page_cur_is_after_last(&cursor)) {
  1772. if (0 == btr_page_get_level(page, mtr)) {
  1773. /* If this is the leaf level, do nothing */
  1774. } else if ((i <= width) || (i >= n_recs - width)) {
  1775. mtr_start(&mtr2);
  1776. node_ptr = page_cur_get_rec(&cursor);
  1777. child = btr_node_ptr_get_child(node_ptr, &mtr2);
  1778. btr_print_recursive(tree, child, width, &mtr2);
  1779. mtr_commit(&mtr2);
  1780. }
  1781. page_cur_move_to_next(&cursor);
  1782. i++;
  1783. }
  1784. }
  1785. /******************************************************************
  1786. Prints directories and other info of all nodes in the tree. */
  1787. void
  1788. btr_print_tree(
  1789. /*===========*/
  1790. dict_tree_t* tree, /* in: tree */
  1791. ulint width) /* in: print this many entries from start
  1792. and end */
  1793. {
  1794. mtr_t mtr;
  1795. page_t* root;
  1796. fputs("--------------------------n"
  1797. "INDEX TREE PRINTn", stderr);
  1798. mtr_start(&mtr);
  1799. root = btr_root_get(tree, &mtr);
  1800. btr_print_recursive(tree, root, width, &mtr);
  1801. mtr_commit(&mtr);
  1802. btr_validate_tree(tree);
  1803. }
  1804. /****************************************************************
  1805. Checks that the node pointer to a page is appropriate. */
  1806. ibool
  1807. btr_check_node_ptr(
  1808. /*===============*/
  1809. /* out: TRUE */
  1810. dict_tree_t* tree, /* in: index tree */
  1811. page_t* page, /* in: index page */
  1812. mtr_t* mtr) /* in: mtr */
  1813. {
  1814. mem_heap_t* heap;
  1815. rec_t* node_ptr;
  1816. dtuple_t* node_ptr_tuple;
  1817. ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
  1818. MTR_MEMO_PAGE_X_FIX));
  1819. if (dict_tree_get_page(tree) == buf_frame_get_page_no(page)) {
  1820. return(TRUE);
  1821. }
  1822. node_ptr = btr_page_get_father_node_ptr(tree, page, mtr);
  1823.  
  1824. if (btr_page_get_level(page, mtr) == 0) {
  1825. return(TRUE);
  1826. }
  1827. heap = mem_heap_create(256);
  1828. node_ptr_tuple = dict_tree_build_node_ptr(
  1829. tree,
  1830. page_rec_get_next(page_get_infimum_rec(page)),
  1831. 0, heap, btr_page_get_level(page, mtr));
  1832. ut_a(cmp_dtuple_rec(node_ptr_tuple, node_ptr) == 0);
  1833. mem_heap_free(heap);
  1834. return(TRUE);
  1835. }
  1836. /****************************************************************
  1837. Display identification information for a record. */
  1838. static
  1839. void
  1840. btr_index_rec_validate_report(
  1841. /*==========================*/
  1842. page_t* page, /* in: index page */
  1843. rec_t* rec, /* in: index record */
  1844. dict_index_t* index) /* in: index */
  1845. {
  1846. fputs("InnoDB: Record in ", stderr);
  1847. dict_index_name_print(stderr, NULL, index);
  1848. fprintf(stderr, ", page %lu, at offset %lun",
  1849. buf_frame_get_page_no(page), (ulint)(rec - page));
  1850. }
  1851. /****************************************************************
  1852. Checks the size and number of fields in a record based on the definition of
  1853. the index. */
  1854. ibool
  1855. btr_index_rec_validate(
  1856. /*====================*/
  1857. /* out: TRUE if ok */
  1858. rec_t* rec, /* in: index record */
  1859. dict_index_t* index, /* in: index */
  1860. ibool dump_on_error) /* in: TRUE if the function
  1861. should print hex dump of record
  1862. and page on error */
  1863. {
  1864. ulint len;
  1865. ulint n;
  1866. ulint i;
  1867. page_t* page;
  1868. page = buf_frame_align(rec);
  1869. if (index->type & DICT_UNIVERSAL) {
  1870.         /* The insert buffer index tree can contain records from any
  1871.         other index: we cannot check the number of fields or
  1872.         their length */
  1873.         return(TRUE);
  1874. }
  1875. n = dict_index_get_n_fields(index);
  1876. if (rec_get_n_fields(rec) != n) {
  1877. btr_index_rec_validate_report(page, rec, index);
  1878. fprintf(stderr, "InnoDB: has %lu fields, should have %lun",
  1879. (ulong) rec_get_n_fields(rec), (ulong) n);
  1880. if (!dump_on_error) {
  1881. return(FALSE);
  1882. }
  1883. buf_page_print(page);
  1884. fputs("InnoDB: corrupt record ", stderr);
  1885. rec_print(stderr, rec);
  1886. putc('n', stderr);
  1887. return(FALSE);
  1888. }
  1889. for (i = 0; i < n; i++) {
  1890. dtype_t* type = dict_index_get_nth_type(index, i);
  1891. rec_get_nth_field(rec, i, &len);
  1892. /* Note that prefix indexes are not fixed size even when
  1893. their type is CHAR. */
  1894. if ((dict_index_get_nth_field(index, i)->prefix_len == 0
  1895.     && len != UNIV_SQL_NULL && dtype_is_fixed_size(type)
  1896.     && len != dtype_get_fixed_size(type))
  1897.    ||
  1898.    (dict_index_get_nth_field(index, i)->prefix_len > 0
  1899.     && len != UNIV_SQL_NULL
  1900.     && len >
  1901.    dict_index_get_nth_field(index, i)->prefix_len)) {
  1902. btr_index_rec_validate_report(page, rec, index);
  1903. fprintf(stderr,
  1904. "InnoDB: field %lu len is %lu, should be %lun",
  1905. (ulong) i, (ulong) len, (ulong) dtype_get_fixed_size(type));
  1906. if (!dump_on_error) {
  1907. return(FALSE);
  1908. }
  1909. buf_page_print(page);
  1910. fputs("InnoDB: corrupt record ", stderr);
  1911. rec_print(stderr, rec);
  1912. putc('n', stderr);
  1913. return(FALSE);
  1914. }
  1915. }
  1916. return(TRUE);
  1917. }
  1918. /****************************************************************
  1919. Checks the size and number of fields in records based on the definition of
  1920. the index. */
  1921. static
  1922. ibool
  1923. btr_index_page_validate(
  1924. /*====================*/
  1925. /* out: TRUE if ok */
  1926. page_t* page, /* in: index page */
  1927. dict_index_t* index) /* in: index */
  1928. {
  1929. page_cur_t  cur;
  1930. ibool ret = TRUE;
  1931. page_cur_set_before_first(page, &cur);
  1932. page_cur_move_to_next(&cur);
  1933. for (;;) {
  1934. if (page_cur_is_after_last(&cur)) {
  1935. break;
  1936. }
  1937. if (!btr_index_rec_validate(cur.rec, index, TRUE)) {
  1938. return(FALSE);
  1939. }
  1940. page_cur_move_to_next(&cur);
  1941. }
  1942. return(ret);
  1943. }
  1944. /****************************************************************
  1945. Report an error on one page of an index tree. */
  1946. static
  1947. void
  1948. btr_validate_report1(
  1949. /* out: TRUE if ok */
  1950. dict_index_t* index, /* in: index */
  1951. ulint level, /* in: B-tree level */
  1952. page_t* page) /* in: index page */
  1953. {
  1954. fprintf(stderr, "InnoDB: Error in page %lu of ",
  1955. buf_frame_get_page_no(page));
  1956. dict_index_name_print(stderr, NULL, index);
  1957. if (level) {
  1958. fprintf(stderr, ", index tree level %lu", level);
  1959. }
  1960. putc('n', stderr);
  1961. }
  1962. /****************************************************************
  1963. Report an error on two pages of an index tree. */
  1964. static
  1965. void
  1966. btr_validate_report2(
  1967. /* out: TRUE if ok */
  1968. dict_index_t* index, /* in: index */
  1969. ulint level, /* in: B-tree level */
  1970. page_t* page1, /* in: first index page */
  1971. page_t* page2) /* in: second index page */
  1972. {
  1973. fprintf(stderr, "InnoDB: Error in pages %lu and %lu of ",
  1974. buf_frame_get_page_no(page1),
  1975. buf_frame_get_page_no(page2));
  1976. dict_index_name_print(stderr, NULL, index);
  1977. if (level) {
  1978. fprintf(stderr, ", index tree level %lu", level);
  1979. }
  1980. putc('n', stderr);
  1981. }
  1982. /****************************************************************
  1983. Validates index tree level. */
  1984. static
  1985. ibool
  1986. btr_validate_level(
  1987. /*===============*/
  1988. /* out: TRUE if ok */
  1989. dict_tree_t* tree, /* in: index tree */
  1990. ulint level) /* in: level number */
  1991. {
  1992. ulint space;
  1993. page_t* page;
  1994. page_t* right_page = 0; /* remove warning */
  1995. page_t* father_page;
  1996. page_t* right_father_page;
  1997. rec_t* node_ptr;
  1998. rec_t* right_node_ptr;
  1999. ulint right_page_no;
  2000. ulint left_page_no;
  2001. page_cur_t cursor;
  2002. mem_heap_t* heap;
  2003. dtuple_t* node_ptr_tuple;
  2004. ibool ret = TRUE;
  2005. dict_index_t* index;
  2006. mtr_t mtr;
  2007. mtr_start(&mtr);
  2008. mtr_x_lock(dict_tree_get_lock(tree), &mtr);
  2009. page = btr_root_get(tree, &mtr);
  2010. space = buf_frame_get_space_id(page);
  2011. while (level != btr_page_get_level(page, &mtr)) {
  2012. ut_a(btr_page_get_level(page, &mtr) > 0);
  2013. page_cur_set_before_first(page, &cursor);
  2014. page_cur_move_to_next(&cursor);
  2015. node_ptr = page_cur_get_rec(&cursor);
  2016. page = btr_node_ptr_get_child(node_ptr, &mtr);
  2017. }
  2018. index = UT_LIST_GET_FIRST(tree->tree_indexes);
  2019. /* Now we are on the desired level. Loop through the pages on that
  2020. level. */
  2021. loop:
  2022. mtr_x_lock(dict_tree_get_lock(tree), &mtr);
  2023. /* Check ordering etc. of records */
  2024. if (!page_validate(page, index)) {
  2025. btr_validate_report1(index, level, page);
  2026. ret = FALSE;
  2027. } else if (level == 0) {
  2028. /* We are on level 0. Check that the records have the right
  2029. number of fields, and field lengths are right. */
  2030. if (!btr_index_page_validate(page, index)) {
  2031. ret = FALSE;
  2032. }
  2033. }
  2034. ut_a(btr_page_get_level(page, &mtr) == level);
  2035. right_page_no = btr_page_get_next(page, &mtr);
  2036. left_page_no = btr_page_get_prev(page, &mtr);
  2037. ut_a((page_get_n_recs(page) > 0)
  2038.      || ((level == 0) &&
  2039.   (buf_frame_get_page_no(page) == dict_tree_get_page(tree))));
  2040. if (right_page_no != FIL_NULL) {
  2041. right_page = btr_page_get(space, right_page_no, RW_X_LATCH,
  2042. &mtr);
  2043. if (cmp_rec_rec(page_rec_get_prev(page_get_supremum_rec(page)),
  2044. page_rec_get_next(page_get_infimum_rec(right_page)),
  2045. UT_LIST_GET_FIRST(tree->tree_indexes)) >= 0) {
  2046. btr_validate_report2(index, level, page, right_page);
  2047. fputs("InnoDB: records in wrong order"
  2048. " on adjacent pagesn", stderr);
  2049. buf_page_print(page);
  2050. buf_page_print(right_page);
  2051. fputs("InnoDB: record ", stderr);
  2052. rec_print(stderr, page_rec_get_prev(
  2053. page_get_supremum_rec(page)));
  2054. putc('n', stderr);
  2055. fputs("InnoDB: record ", stderr);
  2056. rec_print(stderr, page_rec_get_next(
  2057. page_get_infimum_rec(right_page)));
  2058. putc('n', stderr);
  2059.    ret = FALSE;
  2060.    }
  2061. }
  2062. if (level > 0 && left_page_no == FIL_NULL) {
  2063. ut_a(REC_INFO_MIN_REC_FLAG & rec_get_info_bits(
  2064. page_rec_get_next(page_get_infimum_rec(page))));
  2065. }
  2066. if (buf_frame_get_page_no(page) != dict_tree_get_page(tree)) {
  2067. /* Check father node pointers */
  2068. node_ptr = btr_page_get_father_node_ptr(tree, page, &mtr);
  2069. father_page = buf_frame_align(node_ptr);
  2070. if (btr_node_ptr_get_child_page_no(node_ptr) !=
  2071. buf_frame_get_page_no(page)
  2072.    || node_ptr != btr_page_get_father_for_rec(tree, page,
  2073.     page_rec_get_prev(page_get_supremum_rec(page)),
  2074. &mtr)) {
  2075. btr_validate_report1(index, level, page);
  2076. fputs("InnoDB: node pointer to the page is wrongn",
  2077. stderr);
  2078. buf_page_print(father_page);
  2079. buf_page_print(page);
  2080. fputs("InnoDB: node ptr ", stderr);
  2081. rec_print(stderr, node_ptr);
  2082. fprintf(stderr, "n"
  2083. "InnoDB: node ptr child page n:o %lun",
  2084. (unsigned long) btr_node_ptr_get_child_page_no(node_ptr));
  2085. fputs("InnoDB: record on page ", stderr);
  2086. rec_print(stderr,
  2087.   btr_page_get_father_for_rec(tree, page,
  2088.       page_rec_get_prev(page_get_supremum_rec(page)),
  2089. &mtr));
  2090. putc('n', stderr);
  2091.     ret = FALSE;
  2092.     goto node_ptr_fails;
  2093. }
  2094. if (btr_page_get_level(page, &mtr) > 0) {
  2095. heap = mem_heap_create(256);
  2096. node_ptr_tuple = dict_tree_build_node_ptr(
  2097. tree,
  2098. page_rec_get_next(
  2099. page_get_infimum_rec(page)),
  2100. 0, heap,
  2101.         btr_page_get_level(page, &mtr));
  2102. if (cmp_dtuple_rec(node_ptr_tuple, node_ptr) != 0) {
  2103. btr_validate_report1(index, level, page);
  2104. buf_page_print(father_page);
  2105. buf_page_print(page);
  2106. fputs("InnoDB: Error: node ptrs differ"
  2107. " on levels > 0n"
  2108. "InnoDB: node ptr ", stderr);
  2109. rec_print(stderr, node_ptr);
  2110. fputs("InnoDB: first rec ", stderr);
  2111. rec_print(stderr, page_rec_get_next(
  2112. page_get_infimum_rec(page)));
  2113. putc('n', stderr);
  2114.     ret = FALSE;
  2115. mem_heap_free(heap);
  2116.     goto node_ptr_fails;
  2117. }
  2118. mem_heap_free(heap);
  2119. }
  2120. if (left_page_no == FIL_NULL) {
  2121. ut_a(node_ptr == page_rec_get_next(
  2122. page_get_infimum_rec(father_page)));
  2123. ut_a(btr_page_get_prev(father_page, &mtr) == FIL_NULL);
  2124. }
  2125. if (right_page_no == FIL_NULL) {
  2126. ut_a(node_ptr == page_rec_get_prev(
  2127. page_get_supremum_rec(father_page)));
  2128. ut_a(btr_page_get_next(father_page, &mtr) == FIL_NULL);
  2129. }
  2130. if (right_page_no != FIL_NULL) {
  2131. right_node_ptr = btr_page_get_father_node_ptr(tree,
  2132. right_page, &mtr);
  2133. if (page_rec_get_next(node_ptr) !=
  2134. page_get_supremum_rec(father_page)) {
  2135. if (right_node_ptr !=
  2136. page_rec_get_next(node_ptr)) {
  2137. ret = FALSE;
  2138. fputs(
  2139. "InnoDB: node pointer to the right page is wrongn",
  2140. stderr);
  2141. btr_validate_report1(index, level,
  2142. page);
  2143. buf_page_print(father_page);
  2144. buf_page_print(page);
  2145. buf_page_print(right_page);
  2146. }
  2147. } else {
  2148. right_father_page = buf_frame_align(
  2149. right_node_ptr);
  2150. if (right_node_ptr != page_rec_get_next(
  2151.     page_get_infimum_rec(
  2152. right_father_page))) {
  2153. ret = FALSE;
  2154. fputs(
  2155. "InnoDB: node pointer 2 to the right page is wrongn",
  2156. stderr);
  2157. btr_validate_report1(index, level,
  2158. page);
  2159. buf_page_print(father_page);
  2160. buf_page_print(right_father_page);
  2161. buf_page_print(page);
  2162. buf_page_print(right_page);
  2163. }
  2164. if (buf_frame_get_page_no(right_father_page)
  2165.    != btr_page_get_next(father_page, &mtr)) {
  2166. ret = FALSE;
  2167. fputs(
  2168. "InnoDB: node pointer 3 to the right page is wrongn",
  2169. stderr);
  2170. btr_validate_report1(index, level,
  2171. page);
  2172. buf_page_print(father_page);
  2173. buf_page_print(right_father_page);
  2174. buf_page_print(page);
  2175. buf_page_print(right_page);
  2176. }
  2177. }
  2178. }
  2179. }
  2180. node_ptr_fails:
  2181. mtr_commit(&mtr);
  2182. if (right_page_no != FIL_NULL) {
  2183. mtr_start(&mtr);
  2184. page = btr_page_get(space, right_page_no, RW_X_LATCH, &mtr);
  2185. goto loop;
  2186. }
  2187. return(ret);
  2188. }
  2189. /******************************************************************
  2190. Checks the consistency of an index tree. */
  2191. ibool
  2192. btr_validate_tree(
  2193. /*==============*/
  2194. /* out: TRUE if ok */
  2195. dict_tree_t* tree) /* in: tree */
  2196. {
  2197. mtr_t mtr;
  2198. page_t* root;
  2199. ulint i;
  2200. ulint n;
  2201. mtr_start(&mtr);
  2202. mtr_x_lock(dict_tree_get_lock(tree), &mtr);
  2203. root = btr_root_get(tree, &mtr);
  2204. n = btr_page_get_level(root, &mtr);
  2205. for (i = 0; i <= n; i++) {
  2206. if (!btr_validate_level(tree, n - i)) {
  2207. mtr_commit(&mtr);
  2208. return(FALSE);
  2209. }
  2210. }
  2211. mtr_commit(&mtr);
  2212. return(TRUE);
  2213. }