MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
page0page.cc
Go to the documentation of this file.
1 /*****************************************************************************
2 
3 Copyright (c) 1994, 2013, Oracle and/or its affiliates. All Rights Reserved.
4 Copyright (c) 2012, Facebook Inc.
5 
6 This program is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free Software
8 Foundation; version 2 of the License.
9 
10 This program is distributed in the hope that it will be useful, but WITHOUT
11 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13 
14 You should have received a copy of the GNU General Public License along with
15 this program; if not, write to the Free Software Foundation, Inc.,
16 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
17 
18 *****************************************************************************/
19 
20 /**************************************************/
27 #define THIS_MODULE
28 #include "page0page.h"
29 #ifdef UNIV_NONINL
30 #include "page0page.ic"
31 #endif
32 #undef THIS_MODULE
33 
34 #include "page0cur.h"
35 #include "page0zip.h"
36 #include "buf0buf.h"
37 #include "btr0btr.h"
38 #ifndef UNIV_HOTBACKUP
39 # include "srv0srv.h"
40 # include "lock0lock.h"
41 # include "fut0lst.h"
42 # include "btr0sea.h"
43 #endif /* !UNIV_HOTBACKUP */
44 
45 /* THE INDEX PAGE
46  ==============
47 
48 The index page consists of a page header which contains the page's
49 id and other information. On top of it are the index records
50 in a heap linked into a one way linear list according to alphabetic order.
51 
52 Just below page end is an array of pointers which we call page directory,
53 to about every sixth record in the list. The pointers are placed in
54 the directory in the alphabetical order of the records pointed to,
55 enabling us to make binary search using the array. Each slot n:o I
56 in the directory points to a record, where a 4-bit field contains a count
57 of those records which are in the linear list between pointer I and
58 the pointer I - 1 in the directory, including the record
59 pointed to by pointer I and not including the record pointed to by I - 1.
60 We say that the record pointed to by slot I, or that slot I, owns
61 these records. The count is always kept in the range 4 to 8, with
62 the exception that it is 1 for the first slot, and 1--8 for the second slot.
63 
64 An essentially binary search can be performed in the list of index
65 records, like we could do if we had pointer to every record in the
66 page directory. The data structure is, however, more efficient when
67 we are doing inserts, because most inserts are just pushed on a heap.
68 Only every 8th insert requires block move in the directory pointer
69 table, which itself is quite small. A record is deleted from the page
70 by just taking it off the linear list and updating the number of owned
71 records-field of the record which owns it, and updating the page directory,
72 if necessary. A special case is the one when the record owns itself.
73 Because the overhead of inserts is so small, we may also increase the
74 page size from the projected default of 8 kB to 64 kB without too
75 much loss of efficiency in inserts. Bigger page becomes actual
76 when the disk transfer rate compared to seek and latency time rises.
77 On the present system, the page size is set so that the page transfer
78 time (3 ms) is 20 % of the disk random access time (15 ms).
79 
80 When the page is split, merged, or becomes full but contains deleted
81 records, we have to reorganize the page.
82 
83 Assuming a page size of 8 kB, a typical index page of a secondary
84 index contains 300 index entries, and the size of the page directory
85 is 50 x 4 bytes = 200 bytes. */
86 
87 /***************************************************************/
90 UNIV_INTERN
91 ulint
92 page_dir_find_owner_slot(
93 /*=====================*/
94  const rec_t* rec)
95 {
96  const page_t* page;
97  register uint16 rec_offs_bytes;
98  register const page_dir_slot_t* slot;
99  register const page_dir_slot_t* first_slot;
100  register const rec_t* r = rec;
101 
102  ut_ad(page_rec_check(rec));
103 
104  page = page_align(rec);
105  first_slot = page_dir_get_nth_slot(page, 0);
106  slot = page_dir_get_nth_slot(page, page_dir_get_n_slots(page) - 1);
107 
108  if (page_is_comp(page)) {
109  while (rec_get_n_owned_new(r) == 0) {
110  r = rec_get_next_ptr_const(r, TRUE);
111  ut_ad(r >= page + PAGE_NEW_SUPREMUM);
112  ut_ad(r < page + (UNIV_PAGE_SIZE - PAGE_DIR));
113  }
114  } else {
115  while (rec_get_n_owned_old(r) == 0) {
116  r = rec_get_next_ptr_const(r, FALSE);
117  ut_ad(r >= page + PAGE_OLD_SUPREMUM);
118  ut_ad(r < page + (UNIV_PAGE_SIZE - PAGE_DIR));
119  }
120  }
121 
122  rec_offs_bytes = mach_encode_2(r - page);
123 
124  while (UNIV_LIKELY(*(uint16*) slot != rec_offs_bytes)) {
125 
126  if (UNIV_UNLIKELY(slot == first_slot)) {
127  fprintf(stderr,
128  "InnoDB: Probable data corruption on"
129  " page %lu\n"
130  "InnoDB: Original record ",
131  (ulong) page_get_page_no(page));
132 
133  if (page_is_comp(page)) {
134  fputs("(compact record)", stderr);
135  } else {
136  rec_print_old(stderr, rec);
137  }
138 
139  fputs("\n"
140  "InnoDB: on that page.\n"
141  "InnoDB: Cannot find the dir slot for record ",
142  stderr);
143  if (page_is_comp(page)) {
144  fputs("(compact record)", stderr);
145  } else {
146  rec_print_old(stderr, page
147  + mach_decode_2(rec_offs_bytes));
148  }
149  fputs("\n"
150  "InnoDB: on that page!\n", stderr);
151 
152  buf_page_print(page, 0, 0);
153 
154  ut_error;
155  }
156 
157  slot += PAGE_DIR_SLOT_SIZE;
158  }
159 
160  return(((ulint) (first_slot - slot)) / PAGE_DIR_SLOT_SIZE);
161 }
162 
163 /**************************************************************/
166 static
167 ibool
168 page_dir_slot_check(
169 /*================*/
170  const page_dir_slot_t* slot)
171 {
172  const page_t* page;
173  ulint n_slots;
174  ulint n_owned;
175 
176  ut_a(slot);
177 
178  page = page_align(slot);
179 
180  n_slots = page_dir_get_n_slots(page);
181 
182  ut_a(slot <= page_dir_get_nth_slot(page, 0));
183  ut_a(slot >= page_dir_get_nth_slot(page, n_slots - 1));
184 
185  ut_a(page_rec_check(page_dir_slot_get_rec(slot)));
186 
187  if (page_is_comp(page)) {
188  n_owned = rec_get_n_owned_new(page_dir_slot_get_rec(slot));
189  } else {
190  n_owned = rec_get_n_owned_old(page_dir_slot_get_rec(slot));
191  }
192 
193  if (slot == page_dir_get_nth_slot(page, 0)) {
194  ut_a(n_owned == 1);
195  } else if (slot == page_dir_get_nth_slot(page, n_slots - 1)) {
196  ut_a(n_owned >= 1);
197  ut_a(n_owned <= PAGE_DIR_SLOT_MAX_N_OWNED);
198  } else {
199  ut_a(n_owned >= PAGE_DIR_SLOT_MIN_N_OWNED);
200  ut_a(n_owned <= PAGE_DIR_SLOT_MAX_N_OWNED);
201  }
202 
203  return(TRUE);
204 }
205 
206 /*************************************************************/
208 UNIV_INTERN
209 void
210 page_set_max_trx_id(
211 /*================*/
212  buf_block_t* block,
213  page_zip_des_t* page_zip,
214  trx_id_t trx_id,
215  mtr_t* mtr)
216 {
217  page_t* page = buf_block_get_frame(block);
218 #ifndef UNIV_HOTBACKUP
219  ut_ad(!mtr || mtr_memo_contains(mtr, block, MTR_MEMO_PAGE_X_FIX));
220 #endif /* !UNIV_HOTBACKUP */
221 
222  /* It is not necessary to write this change to the redo log, as
223  during a database recovery we assume that the max trx id of every
224  page is the maximum trx id assigned before the crash. */
225 
226  if (page_zip) {
227  mach_write_to_8(page + (PAGE_HEADER + PAGE_MAX_TRX_ID), trx_id);
228  page_zip_write_header(page_zip,
229  page + (PAGE_HEADER + PAGE_MAX_TRX_ID),
230  8, mtr);
231 #ifndef UNIV_HOTBACKUP
232  } else if (mtr) {
233  mlog_write_ull(page + (PAGE_HEADER + PAGE_MAX_TRX_ID),
234  trx_id, mtr);
235 #endif /* !UNIV_HOTBACKUP */
236  } else {
237  mach_write_to_8(page + (PAGE_HEADER + PAGE_MAX_TRX_ID), trx_id);
238  }
239 }
240 
241 /************************************************************/
244 UNIV_INTERN
245 byte*
246 page_mem_alloc_heap(
247 /*================*/
248  page_t* page,
249  page_zip_des_t* page_zip,
252  ulint need,
253  ulint* heap_no)
256 {
257  byte* block;
258  ulint avl_space;
259 
260  ut_ad(page && heap_no);
261 
262  avl_space = page_get_max_insert_size(page, 1);
263 
264  if (avl_space >= need) {
265  block = page_header_get_ptr(page, PAGE_HEAP_TOP);
266 
267  page_header_set_ptr(page, page_zip, PAGE_HEAP_TOP,
268  block + need);
269  *heap_no = page_dir_get_n_heap(page);
270 
271  page_dir_set_n_heap(page, page_zip, 1 + *heap_no);
272 
273  return(block);
274  }
275 
276  return(NULL);
277 }
278 
279 #ifndef UNIV_HOTBACKUP
280 /**********************************************************/
282 UNIV_INLINE
283 void
284 page_create_write_log(
285 /*==================*/
286  buf_frame_t* frame,
288  mtr_t* mtr,
289  ibool comp)
290 {
291  mlog_write_initial_log_record(frame, comp
292  ? MLOG_COMP_PAGE_CREATE
293  : MLOG_PAGE_CREATE, mtr);
294 }
295 #else /* !UNIV_HOTBACKUP */
296 # define page_create_write_log(frame,mtr,comp) ((void) 0)
297 #endif /* !UNIV_HOTBACKUP */
298 
299 /***********************************************************/
302 UNIV_INTERN
303 byte*
304 page_parse_create(
305 /*==============*/
306  byte* ptr,
307  byte* end_ptr __attribute__((unused)),
308  ulint comp,
309  buf_block_t* block,
310  mtr_t* mtr)
311 {
312  ut_ad(ptr && end_ptr);
313 
314  /* The record is empty, except for the record initial part */
315 
316  if (block) {
317  page_create(block, mtr, comp);
318  }
319 
320  return(ptr);
321 }
322 
323 /**********************************************************/
326 static
327 page_t*
328 page_create_low(
329 /*============*/
330  buf_block_t* block,
332  ulint comp)
333 {
334  page_dir_slot_t* slot;
335  mem_heap_t* heap;
336  dtuple_t* tuple;
337  dfield_t* field;
338  byte* heap_top;
339  rec_t* infimum_rec;
340  rec_t* supremum_rec;
341  page_t* page;
342  dict_index_t* index;
343  ulint* offsets;
344 
345  ut_ad(block);
346 #if PAGE_BTR_IBUF_FREE_LIST + FLST_BASE_NODE_SIZE > PAGE_DATA
347 # error "PAGE_BTR_IBUF_FREE_LIST + FLST_BASE_NODE_SIZE > PAGE_DATA"
348 #endif
349 #if PAGE_BTR_IBUF_FREE_LIST_NODE + FLST_NODE_SIZE > PAGE_DATA
350 # error "PAGE_BTR_IBUF_FREE_LIST_NODE + FLST_NODE_SIZE > PAGE_DATA"
351 #endif
352 
353  /* The infimum and supremum records use a dummy index. */
354  if (UNIV_LIKELY(comp)) {
355  index = dict_ind_compact;
356  } else {
357  index = dict_ind_redundant;
358  }
359 
360  /* 1. INCREMENT MODIFY CLOCK */
361  buf_block_modify_clock_inc(block);
362 
363  page = buf_block_get_frame(block);
364 
365  fil_page_set_type(page, FIL_PAGE_INDEX);
366 
367  heap = mem_heap_create(200);
368 
369  /* 3. CREATE THE INFIMUM AND SUPREMUM RECORDS */
370 
371  /* Create first a data tuple for infimum record */
372  tuple = dtuple_create(heap, 1);
373  dtuple_set_info_bits(tuple, REC_STATUS_INFIMUM);
374  field = dtuple_get_nth_field(tuple, 0);
375 
376  dfield_set_data(field, "infimum", 8);
377  dtype_set(dfield_get_type(field),
378  DATA_VARCHAR, DATA_ENGLISH | DATA_NOT_NULL, 8);
379  /* Set the corresponding physical record to its place in the page
380  record heap */
381 
382  heap_top = page + PAGE_DATA;
383 
384  infimum_rec = rec_convert_dtuple_to_rec(heap_top, index, tuple, 0);
385 
386  if (UNIV_LIKELY(comp)) {
387  ut_a(infimum_rec == page + PAGE_NEW_INFIMUM);
388 
389  rec_set_n_owned_new(infimum_rec, NULL, 1);
390  rec_set_heap_no_new(infimum_rec, 0);
391  } else {
392  ut_a(infimum_rec == page + PAGE_OLD_INFIMUM);
393 
394  rec_set_n_owned_old(infimum_rec, 1);
395  rec_set_heap_no_old(infimum_rec, 0);
396  }
397 
398  offsets = rec_get_offsets(infimum_rec, index, NULL,
399  ULINT_UNDEFINED, &heap);
400 
401  heap_top = rec_get_end(infimum_rec, offsets);
402 
403  /* Create then a tuple for supremum */
404 
405  tuple = dtuple_create(heap, 1);
406  dtuple_set_info_bits(tuple, REC_STATUS_SUPREMUM);
407  field = dtuple_get_nth_field(tuple, 0);
408 
409  dfield_set_data(field, "supremum", comp ? 8 : 9);
410  dtype_set(dfield_get_type(field),
411  DATA_VARCHAR, DATA_ENGLISH | DATA_NOT_NULL, comp ? 8 : 9);
412 
413  supremum_rec = rec_convert_dtuple_to_rec(heap_top, index, tuple, 0);
414 
415  if (UNIV_LIKELY(comp)) {
416  ut_a(supremum_rec == page + PAGE_NEW_SUPREMUM);
417 
418  rec_set_n_owned_new(supremum_rec, NULL, 1);
419  rec_set_heap_no_new(supremum_rec, 1);
420  } else {
421  ut_a(supremum_rec == page + PAGE_OLD_SUPREMUM);
422 
423  rec_set_n_owned_old(supremum_rec, 1);
424  rec_set_heap_no_old(supremum_rec, 1);
425  }
426 
427  offsets = rec_get_offsets(supremum_rec, index, offsets,
428  ULINT_UNDEFINED, &heap);
429  heap_top = rec_get_end(supremum_rec, offsets);
430 
431  ut_ad(heap_top == page
432  + (comp ? PAGE_NEW_SUPREMUM_END : PAGE_OLD_SUPREMUM_END));
433 
434  mem_heap_free(heap);
435 
436  /* 4. INITIALIZE THE PAGE */
437 
438  page_header_set_field(page, NULL, PAGE_N_DIR_SLOTS, 2);
439  page_header_set_ptr(page, NULL, PAGE_HEAP_TOP, heap_top);
440  page_header_set_field(page, NULL, PAGE_N_HEAP, comp
441  ? 0x8000 | PAGE_HEAP_NO_USER_LOW
442  : PAGE_HEAP_NO_USER_LOW);
443  page_header_set_ptr(page, NULL, PAGE_FREE, NULL);
444  page_header_set_field(page, NULL, PAGE_GARBAGE, 0);
445  page_header_set_ptr(page, NULL, PAGE_LAST_INSERT, NULL);
446  page_header_set_field(page, NULL, PAGE_DIRECTION, PAGE_NO_DIRECTION);
447  page_header_set_field(page, NULL, PAGE_N_DIRECTION, 0);
448  page_header_set_field(page, NULL, PAGE_N_RECS, 0);
449  page_set_max_trx_id(block, NULL, 0, NULL);
450  memset(heap_top, 0, UNIV_PAGE_SIZE - PAGE_EMPTY_DIR_START
451  - page_offset(heap_top));
452 
453  /* 5. SET POINTERS IN RECORDS AND DIR SLOTS */
454 
455  /* Set the slots to point to infimum and supremum. */
456 
457  slot = page_dir_get_nth_slot(page, 0);
458  page_dir_slot_set_rec(slot, infimum_rec);
459 
460  slot = page_dir_get_nth_slot(page, 1);
461  page_dir_slot_set_rec(slot, supremum_rec);
462 
463  /* Set the next pointers in infimum and supremum */
464 
465  if (UNIV_LIKELY(comp)) {
466  rec_set_next_offs_new(infimum_rec, PAGE_NEW_SUPREMUM);
467  rec_set_next_offs_new(supremum_rec, 0);
468  } else {
469  rec_set_next_offs_old(infimum_rec, PAGE_OLD_SUPREMUM);
470  rec_set_next_offs_old(supremum_rec, 0);
471  }
472 
473  return(page);
474 }
475 
476 /**********************************************************/
479 UNIV_INTERN
480 page_t*
481 page_create(
482 /*========*/
483  buf_block_t* block,
485  mtr_t* mtr,
486  ulint comp)
487 {
488  page_create_write_log(buf_block_get_frame(block), mtr, comp);
489  return(page_create_low(block, comp));
490 }
491 
492 /**********************************************************/
495 UNIV_INTERN
496 page_t*
497 page_create_zip(
498 /*============*/
499  buf_block_t* block,
501  dict_index_t* index,
502  ulint level,
503  trx_id_t max_trx_id,
504  mtr_t* mtr)
505 {
506  page_t* page;
507  page_zip_des_t* page_zip = buf_block_get_page_zip(block);
508 
509  ut_ad(block);
510  ut_ad(page_zip);
511  ut_ad(index);
512  ut_ad(dict_table_is_comp(index->table));
513 
514  page = page_create_low(block, TRUE);
515  mach_write_to_2(PAGE_HEADER + PAGE_LEVEL + page, level);
516  mach_write_to_8(PAGE_HEADER + PAGE_MAX_TRX_ID + page, max_trx_id);
517 
518  if (!page_zip_compress(page_zip, page, index,
519  page_zip_level, mtr)) {
520  /* The compression of a newly created page
521  should always succeed. */
522  ut_error;
523  }
524 
525  return(page);
526 }
527 
528 /**********************************************************/
530 UNIV_INTERN
531 void
532 page_create_empty(
533 /*==============*/
534  buf_block_t* block,
535  dict_index_t* index,
536  mtr_t* mtr)
537 {
538  trx_id_t max_trx_id = 0;
539  const page_t* page = buf_block_get_frame(block);
540  page_zip_des_t* page_zip= buf_block_get_page_zip(block);
541 
542  ut_ad(fil_page_get_type(page) == FIL_PAGE_INDEX);
543 
544  if (dict_index_is_sec_or_ibuf(index) && page_is_leaf(page)) {
545  max_trx_id = page_get_max_trx_id(page);
546  ut_ad(max_trx_id);
547  }
548 
549  if (page_zip) {
550  page_create_zip(block, index,
551  page_header_get_field(page, PAGE_LEVEL),
552  max_trx_id, mtr);
553  } else {
554  page_create(block, mtr, page_is_comp(page));
555 
556  if (max_trx_id) {
557  page_update_max_trx_id(
558  block, page_zip, max_trx_id, mtr);
559  }
560  }
561 }
562 
563 /*************************************************************/
571 UNIV_INTERN
572 void
573 page_copy_rec_list_end_no_locks(
574 /*============================*/
575  buf_block_t* new_block,
576  buf_block_t* block,
577  rec_t* rec,
578  dict_index_t* index,
579  mtr_t* mtr)
580 {
581  page_t* new_page = buf_block_get_frame(new_block);
582  page_cur_t cur1;
583  rec_t* cur2;
584  mem_heap_t* heap = NULL;
585  ulint offsets_[REC_OFFS_NORMAL_SIZE];
586  ulint* offsets = offsets_;
587  rec_offs_init(offsets_);
588 
589  page_cur_position(rec, block, &cur1);
590 
591  if (page_cur_is_before_first(&cur1)) {
592 
593  page_cur_move_to_next(&cur1);
594  }
595 
596  btr_assert_not_corrupted(new_block, index);
597  ut_a(page_is_comp(new_page) == page_rec_is_comp(rec));
598  ut_a(mach_read_from_2(new_page + UNIV_PAGE_SIZE - 10) == (ulint)
599  (page_is_comp(new_page) ? PAGE_NEW_INFIMUM : PAGE_OLD_INFIMUM));
600 
601  cur2 = page_get_infimum_rec(buf_block_get_frame(new_block));
602 
603  /* Copy records from the original page to the new page */
604 
605  while (!page_cur_is_after_last(&cur1)) {
606  rec_t* cur1_rec = page_cur_get_rec(&cur1);
607  rec_t* ins_rec;
608  offsets = rec_get_offsets(cur1_rec, index, offsets,
609  ULINT_UNDEFINED, &heap);
610  ins_rec = page_cur_insert_rec_low(cur2, index,
611  cur1_rec, offsets, mtr);
612  if (UNIV_UNLIKELY(!ins_rec)) {
613  /* Track an assertion failure reported on the mailing
614  list on June 18th, 2003 */
615 
616  buf_page_print(new_page, 0,
617  BUF_PAGE_PRINT_NO_CRASH);
618  buf_page_print(page_align(rec), 0,
619  BUF_PAGE_PRINT_NO_CRASH);
620  ut_print_timestamp(stderr);
621 
622  fprintf(stderr,
623  "InnoDB: rec offset %lu, cur1 offset %lu,"
624  " cur2 offset %lu\n",
625  (ulong) page_offset(rec),
626  (ulong) page_offset(page_cur_get_rec(&cur1)),
627  (ulong) page_offset(cur2));
628  ut_error;
629  }
630 
631  page_cur_move_to_next(&cur1);
632  cur2 = ins_rec;
633  }
634 
635  if (UNIV_LIKELY_NULL(heap)) {
636  mem_heap_free(heap);
637  }
638 }
639 
640 #ifndef UNIV_HOTBACKUP
641 /*************************************************************/
653 UNIV_INTERN
654 rec_t*
655 page_copy_rec_list_end(
656 /*===================*/
657  buf_block_t* new_block,
658  buf_block_t* block,
659  rec_t* rec,
660  dict_index_t* index,
661  mtr_t* mtr)
662 {
663  page_t* new_page = buf_block_get_frame(new_block);
664  page_zip_des_t* new_page_zip = buf_block_get_page_zip(new_block);
665  page_t* page = page_align(rec);
666  rec_t* ret = page_rec_get_next(
667  page_get_infimum_rec(new_page));
668  ulint log_mode = 0; /* remove warning */
669 
670 #ifdef UNIV_ZIP_DEBUG
671  if (new_page_zip) {
672  page_zip_des_t* page_zip = buf_block_get_page_zip(block);
673  ut_a(page_zip);
674 
675  /* Strict page_zip_validate() may fail here.
676  Furthermore, btr_compress() may set FIL_PAGE_PREV to
677  FIL_NULL on new_page while leaving it intact on
678  new_page_zip. So, we cannot validate new_page_zip. */
679  ut_a(page_zip_validate_low(page_zip, page, index, TRUE));
680  }
681 #endif /* UNIV_ZIP_DEBUG */
682  ut_ad(buf_block_get_frame(block) == page);
683  ut_ad(page_is_leaf(page) == page_is_leaf(new_page));
684  ut_ad(page_is_comp(page) == page_is_comp(new_page));
685  /* Here, "ret" may be pointing to a user record or the
686  predefined supremum record. */
687 
688  if (new_page_zip) {
689  log_mode = mtr_set_log_mode(mtr, MTR_LOG_NONE);
690  }
691 
692  if (page_dir_get_n_heap(new_page) == PAGE_HEAP_NO_USER_LOW) {
693  page_copy_rec_list_end_to_created_page(new_page, rec,
694  index, mtr);
695  } else {
696  page_copy_rec_list_end_no_locks(new_block, block, rec,
697  index, mtr);
698  }
699 
700  /* Update PAGE_MAX_TRX_ID on the uncompressed page.
701  Modifications will be redo logged and copied to the compressed
702  page in page_zip_compress() or page_zip_reorganize() below. */
703  if (dict_index_is_sec_or_ibuf(index) && page_is_leaf(page)) {
704  page_update_max_trx_id(new_block, NULL,
705  page_get_max_trx_id(page), mtr);
706  }
707 
708  if (new_page_zip) {
709  mtr_set_log_mode(mtr, log_mode);
710 
711  if (!page_zip_compress(new_page_zip, new_page,
712  index, page_zip_level, mtr)) {
713  /* Before trying to reorganize the page,
714  store the number of preceding records on the page. */
715  ulint ret_pos
716  = page_rec_get_n_recs_before(ret);
717  /* Before copying, "ret" was the successor of
718  the predefined infimum record. It must still
719  have at least one predecessor (the predefined
720  infimum record, or a freshly copied record
721  that is smaller than "ret"). */
722  ut_a(ret_pos > 0);
723 
724  if (!page_zip_reorganize(new_block, index, mtr)) {
725 
726  btr_blob_dbg_remove(new_page, index,
727  "copy_end_reorg_fail");
728  if (!page_zip_decompress(new_page_zip,
729  new_page, FALSE)) {
730  ut_error;
731  }
732  ut_ad(page_validate(new_page, index));
733  btr_blob_dbg_add(new_page, index,
734  "copy_end_reorg_fail");
735  return(NULL);
736  } else {
737  /* The page was reorganized:
738  Seek to ret_pos. */
739  ret = new_page + PAGE_NEW_INFIMUM;
740 
741  do {
742  ret = rec_get_next_ptr(ret, TRUE);
743  } while (--ret_pos);
744  }
745  }
746  }
747 
748  /* Update the lock table and possible hash index */
749 
750  lock_move_rec_list_end(new_block, block, rec);
751 
752  btr_search_move_or_delete_hash_entries(new_block, block, index);
753 
754  return(ret);
755 }
756 
757 /*************************************************************/
769 UNIV_INTERN
770 rec_t*
771 page_copy_rec_list_start(
772 /*=====================*/
773  buf_block_t* new_block,
774  buf_block_t* block,
775  rec_t* rec,
776  dict_index_t* index,
777  mtr_t* mtr)
778 {
779  page_t* new_page = buf_block_get_frame(new_block);
780  page_zip_des_t* new_page_zip = buf_block_get_page_zip(new_block);
781  page_cur_t cur1;
782  rec_t* cur2;
783  ulint log_mode = 0 /* remove warning */;
784  mem_heap_t* heap = NULL;
785  rec_t* ret
786  = page_rec_get_prev(page_get_supremum_rec(new_page));
787  ulint offsets_[REC_OFFS_NORMAL_SIZE];
788  ulint* offsets = offsets_;
789  rec_offs_init(offsets_);
790 
791  /* Here, "ret" may be pointing to a user record or the
792  predefined infimum record. */
793 
794  if (page_rec_is_infimum(rec)) {
795 
796  return(ret);
797  }
798 
799  if (new_page_zip) {
800  log_mode = mtr_set_log_mode(mtr, MTR_LOG_NONE);
801  }
802 
803  page_cur_set_before_first(block, &cur1);
804  page_cur_move_to_next(&cur1);
805 
806  cur2 = ret;
807 
808  /* Copy records from the original page to the new page */
809 
810  while (page_cur_get_rec(&cur1) != rec) {
811  rec_t* cur1_rec = page_cur_get_rec(&cur1);
812  offsets = rec_get_offsets(cur1_rec, index, offsets,
813  ULINT_UNDEFINED, &heap);
814  cur2 = page_cur_insert_rec_low(cur2, index,
815  cur1_rec, offsets, mtr);
816  ut_a(cur2);
817 
818  page_cur_move_to_next(&cur1);
819  }
820 
821  if (UNIV_LIKELY_NULL(heap)) {
822  mem_heap_free(heap);
823  }
824 
825  /* Update PAGE_MAX_TRX_ID on the uncompressed page.
826  Modifications will be redo logged and copied to the compressed
827  page in page_zip_compress() or page_zip_reorganize() below. */
828  if (dict_index_is_sec_or_ibuf(index)
829  && page_is_leaf(page_align(rec))) {
830  page_update_max_trx_id(new_block, NULL,
831  page_get_max_trx_id(page_align(rec)),
832  mtr);
833  }
834 
835  if (new_page_zip) {
836  mtr_set_log_mode(mtr, log_mode);
837 
838  DBUG_EXECUTE_IF("page_copy_rec_list_start_compress_fail",
839  goto zip_reorganize;);
840 
841  if (!page_zip_compress(new_page_zip, new_page, index,
842  page_zip_level, mtr)) {
843 
844  ulint ret_pos;
845 #ifndef DBUG_OFF
846 zip_reorganize:
847 #endif /* DBUG_OFF */
848  /* Before trying to reorganize the page,
849  store the number of preceding records on the page. */
850  ret_pos = page_rec_get_n_recs_before(ret);
851  /* Before copying, "ret" was the predecessor
852  of the predefined supremum record. If it was
853  the predefined infimum record, then it would
854  still be the infimum, and we would have
855  ret_pos == 0. */
856 
857  if (UNIV_UNLIKELY
858  (!page_zip_reorganize(new_block, index, mtr))) {
859 
860  btr_blob_dbg_remove(new_page, index,
861  "copy_start_reorg_fail");
862  if (UNIV_UNLIKELY
863  (!page_zip_decompress(new_page_zip,
864  new_page, FALSE))) {
865  ut_error;
866  }
867  ut_ad(page_validate(new_page, index));
868  btr_blob_dbg_add(new_page, index,
869  "copy_start_reorg_fail");
870  return(NULL);
871  }
872 
873  /* The page was reorganized: Seek to ret_pos. */
874  ret = page_rec_get_nth(new_page, ret_pos);
875  }
876  }
877 
878  /* Update the lock table and possible hash index */
879 
880  lock_move_rec_list_start(new_block, block, rec, ret);
881 
882  btr_search_move_or_delete_hash_entries(new_block, block, index);
883 
884  return(ret);
885 }
886 
887 /**********************************************************/
889 UNIV_INLINE
890 void
891 page_delete_rec_list_write_log(
892 /*===========================*/
893  rec_t* rec,
894  dict_index_t* index,
895  byte type,
897  mtr_t* mtr)
898 {
899  byte* log_ptr;
900  ut_ad(type == MLOG_LIST_END_DELETE
901  || type == MLOG_LIST_START_DELETE
902  || type == MLOG_COMP_LIST_END_DELETE
903  || type == MLOG_COMP_LIST_START_DELETE);
904 
905  log_ptr = mlog_open_and_write_index(mtr, rec, index, type, 2);
906  if (log_ptr) {
907  /* Write the parameter as a 2-byte ulint */
908  mach_write_to_2(log_ptr, page_offset(rec));
909  mlog_close(mtr, log_ptr + 2);
910  }
911 }
912 #else /* !UNIV_HOTBACKUP */
913 # define page_delete_rec_list_write_log(rec,index,type,mtr) ((void) 0)
914 #endif /* !UNIV_HOTBACKUP */
915 
916 /**********************************************************/
919 UNIV_INTERN
920 byte*
921 page_parse_delete_rec_list(
922 /*=======================*/
923  byte type,
927  byte* ptr,
928  byte* end_ptr,
929  buf_block_t* block,
930  dict_index_t* index,
931  mtr_t* mtr)
932 {
933  page_t* page;
934  ulint offset;
935 
936  ut_ad(type == MLOG_LIST_END_DELETE
937  || type == MLOG_LIST_START_DELETE
938  || type == MLOG_COMP_LIST_END_DELETE
939  || type == MLOG_COMP_LIST_START_DELETE);
940 
941  /* Read the record offset as a 2-byte ulint */
942 
943  if (end_ptr < ptr + 2) {
944 
945  return(NULL);
946  }
947 
948  offset = mach_read_from_2(ptr);
949  ptr += 2;
950 
951  if (!block) {
952 
953  return(ptr);
954  }
955 
956  page = buf_block_get_frame(block);
957 
958  ut_ad(!!page_is_comp(page) == dict_table_is_comp(index->table));
959 
960  if (type == MLOG_LIST_END_DELETE
961  || type == MLOG_COMP_LIST_END_DELETE) {
962  page_delete_rec_list_end(page + offset, block, index,
963  ULINT_UNDEFINED, ULINT_UNDEFINED,
964  mtr);
965  } else {
966  page_delete_rec_list_start(page + offset, block, index, mtr);
967  }
968 
969  return(ptr);
970 }
971 
972 /*************************************************************/
975 UNIV_INTERN
976 void
977 page_delete_rec_list_end(
978 /*=====================*/
979  rec_t* rec,
980  buf_block_t* block,
981  dict_index_t* index,
982  ulint n_recs,
984  ulint size,
987  mtr_t* mtr)
988 {
989  page_dir_slot_t*slot;
990  ulint slot_index;
991  rec_t* last_rec;
992  rec_t* prev_rec;
993  ulint n_owned;
994  page_zip_des_t* page_zip = buf_block_get_page_zip(block);
995  page_t* page = page_align(rec);
996  mem_heap_t* heap = NULL;
997  ulint offsets_[REC_OFFS_NORMAL_SIZE];
998  ulint* offsets = offsets_;
999  rec_offs_init(offsets_);
1000 
1001  ut_ad(size == ULINT_UNDEFINED || size < UNIV_PAGE_SIZE);
1002  ut_ad(!page_zip || page_rec_is_comp(rec));
1003 #ifdef UNIV_ZIP_DEBUG
1004  ut_a(!page_zip || page_zip_validate(page_zip, page, index));
1005 #endif /* UNIV_ZIP_DEBUG */
1006 
1007  if (page_rec_is_supremum(rec)) {
1008  ut_ad(n_recs == 0 || n_recs == ULINT_UNDEFINED);
1009  /* Nothing to do, there are no records bigger than the
1010  page supremum. */
1011  return;
1012  }
1013 
1014  if (recv_recovery_is_on()) {
1015  /* If we are replaying a redo log record, we must
1016  replay it exactly. Since MySQL 5.6.11, we should be
1017  generating a redo log record for page creation if
1018  the page would become empty. Thus, this branch should
1019  only be executed when applying redo log that was
1020  generated by an older version of MySQL. */
1021  } else if (page_rec_is_infimum(rec)
1022  || n_recs == page_get_n_recs(page)) {
1023 delete_all:
1024  /* We are deleting all records. */
1025  page_create_empty(block, index, mtr);
1026  return;
1027  } else if (page_is_comp(page)) {
1028  if (page_rec_get_next_low(page + PAGE_NEW_INFIMUM, 1) == rec) {
1029  /* We are deleting everything from the first
1030  user record onwards. */
1031  goto delete_all;
1032  }
1033  } else {
1034  if (page_rec_get_next_low(page + PAGE_OLD_INFIMUM, 0) == rec) {
1035  /* We are deleting everything from the first
1036  user record onwards. */
1037  goto delete_all;
1038  }
1039  }
1040 
1041  /* Reset the last insert info in the page header and increment
1042  the modify clock for the frame */
1043 
1044  page_header_set_ptr(page, page_zip, PAGE_LAST_INSERT, NULL);
1045 
1046  /* The page gets invalid for optimistic searches: increment the
1047  frame modify clock */
1048 
1049  buf_block_modify_clock_inc(block);
1050 
1051  page_delete_rec_list_write_log(rec, index, page_is_comp(page)
1052  ? MLOG_COMP_LIST_END_DELETE
1053  : MLOG_LIST_END_DELETE, mtr);
1054 
1055  if (page_zip) {
1056  ulint log_mode;
1057 
1058  ut_a(page_is_comp(page));
1059  /* Individual deletes are not logged */
1060 
1061  log_mode = mtr_set_log_mode(mtr, MTR_LOG_NONE);
1062 
1063  do {
1064  page_cur_t cur;
1065  page_cur_position(rec, block, &cur);
1066 
1067  offsets = rec_get_offsets(rec, index, offsets,
1068  ULINT_UNDEFINED, &heap);
1069  rec = rec_get_next_ptr(rec, TRUE);
1070 #ifdef UNIV_ZIP_DEBUG
1071  ut_a(page_zip_validate(page_zip, page, index));
1072 #endif /* UNIV_ZIP_DEBUG */
1073  page_cur_delete_rec(&cur, index, offsets, mtr);
1074  } while (page_offset(rec) != PAGE_NEW_SUPREMUM);
1075 
1076  if (UNIV_LIKELY_NULL(heap)) {
1077  mem_heap_free(heap);
1078  }
1079 
1080  /* Restore log mode */
1081 
1082  mtr_set_log_mode(mtr, log_mode);
1083  return;
1084  }
1085 
1086  prev_rec = page_rec_get_prev(rec);
1087 
1088  last_rec = page_rec_get_prev(page_get_supremum_rec(page));
1089 
1090  if ((size == ULINT_UNDEFINED) || (n_recs == ULINT_UNDEFINED)) {
1091  rec_t* rec2 = rec;
1092  /* Calculate the sum of sizes and the number of records */
1093  size = 0;
1094  n_recs = 0;
1095 
1096  do {
1097  ulint s;
1098  offsets = rec_get_offsets(rec2, index, offsets,
1099  ULINT_UNDEFINED, &heap);
1100  s = rec_offs_size(offsets);
1101  ut_ad(rec2 - page + s - rec_offs_extra_size(offsets)
1102  < UNIV_PAGE_SIZE);
1103  ut_ad(size + s < UNIV_PAGE_SIZE);
1104  size += s;
1105  n_recs++;
1106 
1107  rec2 = page_rec_get_next(rec2);
1108  } while (!page_rec_is_supremum(rec2));
1109 
1110  if (UNIV_LIKELY_NULL(heap)) {
1111  mem_heap_free(heap);
1112  }
1113  }
1114 
1115  ut_ad(size < UNIV_PAGE_SIZE);
1116 
1117  /* Update the page directory; there is no need to balance the number
1118  of the records owned by the supremum record, as it is allowed to be
1119  less than PAGE_DIR_SLOT_MIN_N_OWNED */
1120 
1121  if (page_is_comp(page)) {
1122  rec_t* rec2 = rec;
1123  ulint count = 0;
1124 
1125  while (rec_get_n_owned_new(rec2) == 0) {
1126  count++;
1127 
1128  rec2 = rec_get_next_ptr(rec2, TRUE);
1129  }
1130 
1131  ut_ad(rec_get_n_owned_new(rec2) > count);
1132 
1133  n_owned = rec_get_n_owned_new(rec2) - count;
1134  slot_index = page_dir_find_owner_slot(rec2);
1135  ut_ad(slot_index > 0);
1136  slot = page_dir_get_nth_slot(page, slot_index);
1137  } else {
1138  rec_t* rec2 = rec;
1139  ulint count = 0;
1140 
1141  while (rec_get_n_owned_old(rec2) == 0) {
1142  count++;
1143 
1144  rec2 = rec_get_next_ptr(rec2, FALSE);
1145  }
1146 
1147  ut_ad(rec_get_n_owned_old(rec2) > count);
1148 
1149  n_owned = rec_get_n_owned_old(rec2) - count;
1150  slot_index = page_dir_find_owner_slot(rec2);
1151  ut_ad(slot_index > 0);
1152  slot = page_dir_get_nth_slot(page, slot_index);
1153  }
1154 
1155  page_dir_slot_set_rec(slot, page_get_supremum_rec(page));
1156  page_dir_slot_set_n_owned(slot, NULL, n_owned);
1157 
1158  page_dir_set_n_slots(page, NULL, slot_index + 1);
1159 
1160  /* Remove the record chain segment from the record chain */
1161  page_rec_set_next(prev_rec, page_get_supremum_rec(page));
1162 
1163  btr_blob_dbg_op(page, rec, index, "delete_end",
1164  btr_blob_dbg_remove_rec);
1165 
1166  /* Catenate the deleted chain segment to the page free list */
1167 
1168  page_rec_set_next(last_rec, page_header_get_ptr(page, PAGE_FREE));
1169  page_header_set_ptr(page, NULL, PAGE_FREE, rec);
1170 
1171  page_header_set_field(page, NULL, PAGE_GARBAGE, size
1172  + page_header_get_field(page, PAGE_GARBAGE));
1173 
1174  page_header_set_field(page, NULL, PAGE_N_RECS,
1175  (ulint)(page_get_n_recs(page) - n_recs));
1176 }
1177 
1178 /*************************************************************/
1181 UNIV_INTERN
1182 void
1183 page_delete_rec_list_start(
1184 /*=======================*/
1185  rec_t* rec,
1186  buf_block_t* block,
1187  dict_index_t* index,
1188  mtr_t* mtr)
1189 {
1190  page_cur_t cur1;
1191  ulint log_mode;
1192  ulint offsets_[REC_OFFS_NORMAL_SIZE];
1193  ulint* offsets = offsets_;
1194  mem_heap_t* heap = NULL;
1195  byte type;
1196 
1197  rec_offs_init(offsets_);
1198 
1199  ut_ad((ibool) !!page_rec_is_comp(rec)
1200  == dict_table_is_comp(index->table));
1201 #ifdef UNIV_ZIP_DEBUG
1202  {
1203  page_zip_des_t* page_zip= buf_block_get_page_zip(block);
1204  page_t* page = buf_block_get_frame(block);
1205 
1206  /* page_zip_validate() would detect a min_rec_mark mismatch
1207  in btr_page_split_and_insert()
1208  between btr_attach_half_pages() and insert_page = ...
1209  when btr_page_get_split_rec_to_left() holds
1210  (direction == FSP_DOWN). */
1211  ut_a(!page_zip
1212  || page_zip_validate_low(page_zip, page, index, TRUE));
1213  }
1214 #endif /* UNIV_ZIP_DEBUG */
1215 
1216  if (page_rec_is_infimum(rec)) {
1217  return;
1218  }
1219 
1220  if (page_rec_is_supremum(rec)) {
1221  /* We are deleting all records. */
1222  page_create_empty(block, index, mtr);
1223  return;
1224  }
1225 
1226  if (page_rec_is_comp(rec)) {
1227  type = MLOG_COMP_LIST_START_DELETE;
1228  } else {
1229  type = MLOG_LIST_START_DELETE;
1230  }
1231 
1232  page_delete_rec_list_write_log(rec, index, type, mtr);
1233 
1234  page_cur_set_before_first(block, &cur1);
1235  page_cur_move_to_next(&cur1);
1236 
1237  /* Individual deletes are not logged */
1238 
1239  log_mode = mtr_set_log_mode(mtr, MTR_LOG_NONE);
1240 
1241  while (page_cur_get_rec(&cur1) != rec) {
1242  offsets = rec_get_offsets(page_cur_get_rec(&cur1), index,
1243  offsets, ULINT_UNDEFINED, &heap);
1244  page_cur_delete_rec(&cur1, index, offsets, mtr);
1245  }
1246 
1247  if (UNIV_LIKELY_NULL(heap)) {
1248  mem_heap_free(heap);
1249  }
1250 
1251  /* Restore log mode */
1252 
1253  mtr_set_log_mode(mtr, log_mode);
1254 }
1255 
1256 #ifndef UNIV_HOTBACKUP
1257 /*************************************************************/
1268 UNIV_INTERN
1269 ibool
1270 page_move_rec_list_end(
1271 /*===================*/
1272  buf_block_t* new_block,
1273  buf_block_t* block,
1274  rec_t* split_rec,
1275  dict_index_t* index,
1276  mtr_t* mtr)
1277 {
1278  page_t* new_page = buf_block_get_frame(new_block);
1279  ulint old_data_size;
1280  ulint new_data_size;
1281  ulint old_n_recs;
1282  ulint new_n_recs;
1283 
1284  old_data_size = page_get_data_size(new_page);
1285  old_n_recs = page_get_n_recs(new_page);
1286 #ifdef UNIV_ZIP_DEBUG
1287  {
1288  page_zip_des_t* new_page_zip
1289  = buf_block_get_page_zip(new_block);
1290  page_zip_des_t* page_zip
1291  = buf_block_get_page_zip(block);
1292  ut_a(!new_page_zip == !page_zip);
1293  ut_a(!new_page_zip
1294  || page_zip_validate(new_page_zip, new_page, index));
1295  ut_a(!page_zip
1296  || page_zip_validate(page_zip, page_align(split_rec),
1297  index));
1298  }
1299 #endif /* UNIV_ZIP_DEBUG */
1300 
1301  if (UNIV_UNLIKELY(!page_copy_rec_list_end(new_block, block,
1302  split_rec, index, mtr))) {
1303  return(FALSE);
1304  }
1305 
1306  new_data_size = page_get_data_size(new_page);
1307  new_n_recs = page_get_n_recs(new_page);
1308 
1309  ut_ad(new_data_size >= old_data_size);
1310 
1311  page_delete_rec_list_end(split_rec, block, index,
1312  new_n_recs - old_n_recs,
1313  new_data_size - old_data_size, mtr);
1314 
1315  return(TRUE);
1316 }
1317 
1318 /*************************************************************/
1328 UNIV_INTERN
1329 ibool
1330 page_move_rec_list_start(
1331 /*=====================*/
1332  buf_block_t* new_block,
1333  buf_block_t* block,
1334  rec_t* split_rec,
1335  dict_index_t* index,
1336  mtr_t* mtr)
1337 {
1338  if (UNIV_UNLIKELY(!page_copy_rec_list_start(new_block, block,
1339  split_rec, index, mtr))) {
1340  return(FALSE);
1341  }
1342 
1343  page_delete_rec_list_start(split_rec, block, index, mtr);
1344 
1345  return(TRUE);
1346 }
1347 #endif /* !UNIV_HOTBACKUP */
1348 
1349 /**************************************************************/
1353 UNIV_INLINE
1354 void
1355 page_dir_delete_slot(
1356 /*=================*/
1357  page_t* page,
1358  page_zip_des_t* page_zip,
1359  ulint slot_no)
1360 {
1361  page_dir_slot_t* slot;
1362  ulint n_owned;
1363  ulint i;
1364  ulint n_slots;
1365 
1366  ut_ad(!page_zip || page_is_comp(page));
1367  ut_ad(slot_no > 0);
1368  ut_ad(slot_no + 1 < page_dir_get_n_slots(page));
1369 
1370  n_slots = page_dir_get_n_slots(page);
1371 
1372  /* 1. Reset the n_owned fields of the slots to be
1373  deleted */
1374  slot = page_dir_get_nth_slot(page, slot_no);
1375  n_owned = page_dir_slot_get_n_owned(slot);
1376  page_dir_slot_set_n_owned(slot, page_zip, 0);
1377 
1378  /* 2. Update the n_owned value of the first non-deleted slot */
1379 
1380  slot = page_dir_get_nth_slot(page, slot_no + 1);
1381  page_dir_slot_set_n_owned(slot, page_zip,
1382  n_owned + page_dir_slot_get_n_owned(slot));
1383 
1384  /* 3. Destroy the slot by copying slots */
1385  for (i = slot_no + 1; i < n_slots; i++) {
1386  rec_t* rec = (rec_t*)
1387  page_dir_slot_get_rec(page_dir_get_nth_slot(page, i));
1388  page_dir_slot_set_rec(page_dir_get_nth_slot(page, i - 1), rec);
1389  }
1390 
1391  /* 4. Zero out the last slot, which will be removed */
1392  mach_write_to_2(page_dir_get_nth_slot(page, n_slots - 1), 0);
1393 
1394  /* 5. Update the page header */
1395  page_header_set_field(page, page_zip, PAGE_N_DIR_SLOTS, n_slots - 1);
1396 }
1397 
1398 /**************************************************************/
1402 UNIV_INLINE
1403 void
1404 page_dir_add_slot(
1405 /*==============*/
1406  page_t* page,
1407  page_zip_des_t* page_zip,
1408  ulint start)
1410 {
1411  page_dir_slot_t* slot;
1412  ulint n_slots;
1413 
1414  n_slots = page_dir_get_n_slots(page);
1415 
1416  ut_ad(start < n_slots - 1);
1417 
1418  /* Update the page header */
1419  page_dir_set_n_slots(page, page_zip, n_slots + 1);
1420 
1421  /* Move slots up */
1422  slot = page_dir_get_nth_slot(page, n_slots);
1423  memmove(slot, slot + PAGE_DIR_SLOT_SIZE,
1424  (n_slots - 1 - start) * PAGE_DIR_SLOT_SIZE);
1425 }
1426 
1427 /****************************************************************/
1429 UNIV_INTERN
1430 void
1431 page_dir_split_slot(
1432 /*================*/
1433  page_t* page,
1434  page_zip_des_t* page_zip,
1436  ulint slot_no)
1437 {
1438  rec_t* rec;
1439  page_dir_slot_t* new_slot;
1440  page_dir_slot_t* prev_slot;
1441  page_dir_slot_t* slot;
1442  ulint i;
1443  ulint n_owned;
1444 
1445  ut_ad(page);
1446  ut_ad(!page_zip || page_is_comp(page));
1447  ut_ad(slot_no > 0);
1448 
1449  slot = page_dir_get_nth_slot(page, slot_no);
1450 
1451  n_owned = page_dir_slot_get_n_owned(slot);
1452  ut_ad(n_owned == PAGE_DIR_SLOT_MAX_N_OWNED + 1);
1453 
1454  /* 1. We loop to find a record approximately in the middle of the
1455  records owned by the slot. */
1456 
1457  prev_slot = page_dir_get_nth_slot(page, slot_no - 1);
1458  rec = (rec_t*) page_dir_slot_get_rec(prev_slot);
1459 
1460  for (i = 0; i < n_owned / 2; i++) {
1461  rec = page_rec_get_next(rec);
1462  }
1463 
1464  ut_ad(n_owned / 2 >= PAGE_DIR_SLOT_MIN_N_OWNED);
1465 
1466  /* 2. We add one directory slot immediately below the slot to be
1467  split. */
1468 
1469  page_dir_add_slot(page, page_zip, slot_no - 1);
1470 
1471  /* The added slot is now number slot_no, and the old slot is
1472  now number slot_no + 1 */
1473 
1474  new_slot = page_dir_get_nth_slot(page, slot_no);
1475  slot = page_dir_get_nth_slot(page, slot_no + 1);
1476 
1477  /* 3. We store the appropriate values to the new slot. */
1478 
1479  page_dir_slot_set_rec(new_slot, rec);
1480  page_dir_slot_set_n_owned(new_slot, page_zip, n_owned / 2);
1481 
1482  /* 4. Finally, we update the number of records field of the
1483  original slot */
1484 
1485  page_dir_slot_set_n_owned(slot, page_zip, n_owned - (n_owned / 2));
1486 }
1487 
1488 /*************************************************************/
1492 UNIV_INTERN
1493 void
1494 page_dir_balance_slot(
1495 /*==================*/
1496  page_t* page,
1497  page_zip_des_t* page_zip,
1498  ulint slot_no)
1499 {
1500  page_dir_slot_t* slot;
1501  page_dir_slot_t* up_slot;
1502  ulint n_owned;
1503  ulint up_n_owned;
1504  rec_t* old_rec;
1505  rec_t* new_rec;
1506 
1507  ut_ad(page);
1508  ut_ad(!page_zip || page_is_comp(page));
1509  ut_ad(slot_no > 0);
1510 
1511  slot = page_dir_get_nth_slot(page, slot_no);
1512 
1513  /* The last directory slot cannot be balanced with the upper
1514  neighbor, as there is none. */
1515 
1516  if (UNIV_UNLIKELY(slot_no == page_dir_get_n_slots(page) - 1)) {
1517 
1518  return;
1519  }
1520 
1521  up_slot = page_dir_get_nth_slot(page, slot_no + 1);
1522 
1523  n_owned = page_dir_slot_get_n_owned(slot);
1524  up_n_owned = page_dir_slot_get_n_owned(up_slot);
1525 
1526  ut_ad(n_owned == PAGE_DIR_SLOT_MIN_N_OWNED - 1);
1527 
1528  /* If the upper slot has the minimum value of n_owned, we will merge
1529  the two slots, therefore we assert: */
1530  ut_ad(2 * PAGE_DIR_SLOT_MIN_N_OWNED - 1 <= PAGE_DIR_SLOT_MAX_N_OWNED);
1531 
1532  if (up_n_owned > PAGE_DIR_SLOT_MIN_N_OWNED) {
1533 
1534  /* In this case we can just transfer one record owned
1535  by the upper slot to the property of the lower slot */
1536  old_rec = (rec_t*) page_dir_slot_get_rec(slot);
1537 
1538  if (page_is_comp(page)) {
1539  new_rec = rec_get_next_ptr(old_rec, TRUE);
1540 
1541  rec_set_n_owned_new(old_rec, page_zip, 0);
1542  rec_set_n_owned_new(new_rec, page_zip, n_owned + 1);
1543  } else {
1544  new_rec = rec_get_next_ptr(old_rec, FALSE);
1545 
1546  rec_set_n_owned_old(old_rec, 0);
1547  rec_set_n_owned_old(new_rec, n_owned + 1);
1548  }
1549 
1550  page_dir_slot_set_rec(slot, new_rec);
1551 
1552  page_dir_slot_set_n_owned(up_slot, page_zip, up_n_owned -1);
1553  } else {
1554  /* In this case we may merge the two slots */
1555  page_dir_delete_slot(page, page_zip, slot_no);
1556  }
1557 }
1558 
1559 /************************************************************/
1563 UNIV_INTERN
1564 const rec_t*
1565 page_rec_get_nth_const(
1566 /*===================*/
1567  const page_t* page,
1568  ulint nth)
1569 {
1570  const page_dir_slot_t* slot;
1571  ulint i;
1572  ulint n_owned;
1573  const rec_t* rec;
1574 
1575  if (nth == 0) {
1576  return(page_get_infimum_rec(page));
1577  }
1578 
1579  ut_ad(nth < UNIV_PAGE_SIZE / (REC_N_NEW_EXTRA_BYTES + 1));
1580 
1581  for (i = 0;; i++) {
1582 
1583  slot = page_dir_get_nth_slot(page, i);
1584  n_owned = page_dir_slot_get_n_owned(slot);
1585 
1586  if (n_owned > nth) {
1587  break;
1588  } else {
1589  nth -= n_owned;
1590  }
1591  }
1592 
1593  ut_ad(i > 0);
1594  slot = page_dir_get_nth_slot(page, i - 1);
1595  rec = page_dir_slot_get_rec(slot);
1596 
1597  if (page_is_comp(page)) {
1598  do {
1599  rec = page_rec_get_next_low(rec, TRUE);
1600  ut_ad(rec);
1601  } while (nth--);
1602  } else {
1603  do {
1604  rec = page_rec_get_next_low(rec, FALSE);
1605  ut_ad(rec);
1606  } while (nth--);
1607  }
1608 
1609  return(rec);
1610 }
1611 
1612 /***************************************************************/
1616 UNIV_INTERN
1617 ulint
1618 page_rec_get_n_recs_before(
1619 /*=======================*/
1620  const rec_t* rec)
1621 {
1622  const page_dir_slot_t* slot;
1623  const rec_t* slot_rec;
1624  const page_t* page;
1625  ulint i;
1626  lint n = 0;
1627 
1628  ut_ad(page_rec_check(rec));
1629 
1630  page = page_align(rec);
1631  if (page_is_comp(page)) {
1632  while (rec_get_n_owned_new(rec) == 0) {
1633 
1634  rec = rec_get_next_ptr_const(rec, TRUE);
1635  n--;
1636  }
1637 
1638  for (i = 0; ; i++) {
1639  slot = page_dir_get_nth_slot(page, i);
1640  slot_rec = page_dir_slot_get_rec(slot);
1641 
1642  n += rec_get_n_owned_new(slot_rec);
1643 
1644  if (rec == slot_rec) {
1645 
1646  break;
1647  }
1648  }
1649  } else {
1650  while (rec_get_n_owned_old(rec) == 0) {
1651 
1652  rec = rec_get_next_ptr_const(rec, FALSE);
1653  n--;
1654  }
1655 
1656  for (i = 0; ; i++) {
1657  slot = page_dir_get_nth_slot(page, i);
1658  slot_rec = page_dir_slot_get_rec(slot);
1659 
1660  n += rec_get_n_owned_old(slot_rec);
1661 
1662  if (rec == slot_rec) {
1663 
1664  break;
1665  }
1666  }
1667  }
1668 
1669  n--;
1670 
1671  ut_ad(n >= 0);
1672  ut_ad((ulong) n < UNIV_PAGE_SIZE / (REC_N_NEW_EXTRA_BYTES + 1));
1673 
1674  return((ulint) n);
1675 }
1676 
1677 #ifndef UNIV_HOTBACKUP
1678 /************************************************************/
1681 UNIV_INTERN
1682 void
1683 page_rec_print(
1684 /*===========*/
1685  const rec_t* rec,
1686  const ulint* offsets)
1687 {
1688  ut_a(!page_rec_is_comp(rec) == !rec_offs_comp(offsets));
1689  rec_print_new(stderr, rec, offsets);
1690  if (page_rec_is_comp(rec)) {
1691  fprintf(stderr,
1692  " n_owned: %lu; heap_no: %lu; next rec: %lu\n",
1693  (ulong) rec_get_n_owned_new(rec),
1694  (ulong) rec_get_heap_no_new(rec),
1695  (ulong) rec_get_next_offs(rec, TRUE));
1696  } else {
1697  fprintf(stderr,
1698  " n_owned: %lu; heap_no: %lu; next rec: %lu\n",
1699  (ulong) rec_get_n_owned_old(rec),
1700  (ulong) rec_get_heap_no_old(rec),
1701  (ulong) rec_get_next_offs(rec, FALSE));
1702  }
1703 
1704  page_rec_check(rec);
1705  rec_validate(rec, offsets);
1706 }
1707 
1708 # ifdef UNIV_BTR_PRINT
1709 /***************************************************************/
1712 UNIV_INTERN
1713 void
1714 page_dir_print(
1715 /*===========*/
1716  page_t* page,
1717  ulint pr_n)
1718 {
1719  ulint n;
1720  ulint i;
1721  page_dir_slot_t* slot;
1722 
1723  n = page_dir_get_n_slots(page);
1724 
1725  fprintf(stderr, "--------------------------------\n"
1726  "PAGE DIRECTORY\n"
1727  "Page address %p\n"
1728  "Directory stack top at offs: %lu; number of slots: %lu\n",
1729  page, (ulong) page_offset(page_dir_get_nth_slot(page, n - 1)),
1730  (ulong) n);
1731  for (i = 0; i < n; i++) {
1732  slot = page_dir_get_nth_slot(page, i);
1733  if ((i == pr_n) && (i < n - pr_n)) {
1734  fputs(" ... \n", stderr);
1735  }
1736  if ((i < pr_n) || (i >= n - pr_n)) {
1737  fprintf(stderr,
1738  "Contents of slot: %lu: n_owned: %lu,"
1739  " rec offs: %lu\n",
1740  (ulong) i,
1741  (ulong) page_dir_slot_get_n_owned(slot),
1742  (ulong)
1743  page_offset(page_dir_slot_get_rec(slot)));
1744  }
1745  }
1746  fprintf(stderr, "Total of %lu records\n"
1747  "--------------------------------\n",
1748  (ulong) (PAGE_HEAP_NO_USER_LOW + page_get_n_recs(page)));
1749 }
1750 
1751 /***************************************************************/
1754 UNIV_INTERN
1755 void
1756 page_print_list(
1757 /*============*/
1758  buf_block_t* block,
1759  dict_index_t* index,
1760  ulint pr_n)
1761 {
1762  page_t* page = block->frame;
1763  page_cur_t cur;
1764  ulint count;
1765  ulint n_recs;
1766  mem_heap_t* heap = NULL;
1767  ulint offsets_[REC_OFFS_NORMAL_SIZE];
1768  ulint* offsets = offsets_;
1769  rec_offs_init(offsets_);
1770 
1771  ut_a((ibool)!!page_is_comp(page) == dict_table_is_comp(index->table));
1772 
1773  fprintf(stderr,
1774  "--------------------------------\n"
1775  "PAGE RECORD LIST\n"
1776  "Page address %p\n", page);
1777 
1778  n_recs = page_get_n_recs(page);
1779 
1780  page_cur_set_before_first(block, &cur);
1781  count = 0;
1782  for (;;) {
1783  offsets = rec_get_offsets(cur.rec, index, offsets,
1784  ULINT_UNDEFINED, &heap);
1785  page_rec_print(cur.rec, offsets);
1786 
1787  if (count == pr_n) {
1788  break;
1789  }
1790  if (page_cur_is_after_last(&cur)) {
1791  break;
1792  }
1793  page_cur_move_to_next(&cur);
1794  count++;
1795  }
1796 
1797  if (n_recs > 2 * pr_n) {
1798  fputs(" ... \n", stderr);
1799  }
1800 
1801  while (!page_cur_is_after_last(&cur)) {
1802  page_cur_move_to_next(&cur);
1803 
1804  if (count + pr_n >= n_recs) {
1805  offsets = rec_get_offsets(cur.rec, index, offsets,
1806  ULINT_UNDEFINED, &heap);
1807  page_rec_print(cur.rec, offsets);
1808  }
1809  count++;
1810  }
1811 
1812  fprintf(stderr,
1813  "Total of %lu records \n"
1814  "--------------------------------\n",
1815  (ulong) (count + 1));
1816 
1817  if (UNIV_LIKELY_NULL(heap)) {
1818  mem_heap_free(heap);
1819  }
1820 }
1821 
1822 /***************************************************************/
1824 UNIV_INTERN
1825 void
1826 page_header_print(
1827 /*==============*/
1828  const page_t* page)
1829 {
1830  fprintf(stderr,
1831  "--------------------------------\n"
1832  "PAGE HEADER INFO\n"
1833  "Page address %p, n records %lu (%s)\n"
1834  "n dir slots %lu, heap top %lu\n"
1835  "Page n heap %lu, free %lu, garbage %lu\n"
1836  "Page last insert %lu, direction %lu, n direction %lu\n",
1837  page, (ulong) page_header_get_field(page, PAGE_N_RECS),
1838  page_is_comp(page) ? "compact format" : "original format",
1839  (ulong) page_header_get_field(page, PAGE_N_DIR_SLOTS),
1840  (ulong) page_header_get_field(page, PAGE_HEAP_TOP),
1841  (ulong) page_dir_get_n_heap(page),
1842  (ulong) page_header_get_field(page, PAGE_FREE),
1843  (ulong) page_header_get_field(page, PAGE_GARBAGE),
1844  (ulong) page_header_get_field(page, PAGE_LAST_INSERT),
1845  (ulong) page_header_get_field(page, PAGE_DIRECTION),
1846  (ulong) page_header_get_field(page, PAGE_N_DIRECTION));
1847 }
1848 
1849 /***************************************************************/
1852 UNIV_INTERN
1853 void
1854 page_print(
1855 /*=======*/
1856  buf_block_t* block,
1857  dict_index_t* index,
1858  ulint dn,
1860  ulint rn)
1862 {
1863  page_t* page = block->frame;
1864 
1865  page_header_print(page);
1866  page_dir_print(page, dn);
1867  page_print_list(block, index, rn);
1868 }
1869 # endif /* UNIV_BTR_PRINT */
1870 #endif /* !UNIV_HOTBACKUP */
1871 
1872 /***************************************************************/
1877 UNIV_INTERN
1878 ibool
1879 page_rec_validate(
1880 /*==============*/
1881  const rec_t* rec,
1882  const ulint* offsets)
1883 {
1884  ulint n_owned;
1885  ulint heap_no;
1886  const page_t* page;
1887 
1888  page = page_align(rec);
1889  ut_a(!page_is_comp(page) == !rec_offs_comp(offsets));
1890 
1891  page_rec_check(rec);
1892  rec_validate(rec, offsets);
1893 
1894  if (page_rec_is_comp(rec)) {
1895  n_owned = rec_get_n_owned_new(rec);
1896  heap_no = rec_get_heap_no_new(rec);
1897  } else {
1898  n_owned = rec_get_n_owned_old(rec);
1899  heap_no = rec_get_heap_no_old(rec);
1900  }
1901 
1902  if (UNIV_UNLIKELY(!(n_owned <= PAGE_DIR_SLOT_MAX_N_OWNED))) {
1903  fprintf(stderr,
1904  "InnoDB: Dir slot of rec %lu, n owned too big %lu\n",
1905  (ulong) page_offset(rec), (ulong) n_owned);
1906  return(FALSE);
1907  }
1908 
1909  if (UNIV_UNLIKELY(!(heap_no < page_dir_get_n_heap(page)))) {
1910  fprintf(stderr,
1911  "InnoDB: Heap no of rec %lu too big %lu %lu\n",
1912  (ulong) page_offset(rec), (ulong) heap_no,
1913  (ulong) page_dir_get_n_heap(page));
1914  return(FALSE);
1915  }
1916 
1917  return(TRUE);
1918 }
1919 
1920 #ifndef UNIV_HOTBACKUP
1921 /***************************************************************/
1925 UNIV_INTERN
1926 void
1927 page_check_dir(
1928 /*===========*/
1929  const page_t* page)
1930 {
1931  ulint n_slots;
1932  ulint infimum_offs;
1933  ulint supremum_offs;
1934 
1935  n_slots = page_dir_get_n_slots(page);
1936  infimum_offs = mach_read_from_2(page_dir_get_nth_slot(page, 0));
1937  supremum_offs = mach_read_from_2(page_dir_get_nth_slot(page,
1938  n_slots - 1));
1939 
1940  if (UNIV_UNLIKELY(!page_rec_is_infimum_low(infimum_offs))) {
1941 
1942  fprintf(stderr,
1943  "InnoDB: Page directory corruption:"
1944  " infimum not pointed to\n");
1945  buf_page_print(page, 0, 0);
1946  }
1947 
1948  if (UNIV_UNLIKELY(!page_rec_is_supremum_low(supremum_offs))) {
1949 
1950  fprintf(stderr,
1951  "InnoDB: Page directory corruption:"
1952  " supremum not pointed to\n");
1953  buf_page_print(page, 0, 0);
1954  }
1955 }
1956 #endif /* !UNIV_HOTBACKUP */
1957 
1958 /***************************************************************/
1963 UNIV_INTERN
1964 ibool
1965 page_simple_validate_old(
1966 /*=====================*/
1967  const page_t* page)
1968 {
1969  const page_dir_slot_t* slot;
1970  ulint slot_no;
1971  ulint n_slots;
1972  const rec_t* rec;
1973  const byte* rec_heap_top;
1974  ulint count;
1975  ulint own_count;
1976  ibool ret = FALSE;
1977 
1978  ut_a(!page_is_comp(page));
1979 
1980  /* Check first that the record heap and the directory do not
1981  overlap. */
1982 
1983  n_slots = page_dir_get_n_slots(page);
1984 
1985  if (UNIV_UNLIKELY(n_slots > UNIV_PAGE_SIZE / 4)) {
1986  fprintf(stderr,
1987  "InnoDB: Nonsensical number %lu of page dir slots\n",
1988  (ulong) n_slots);
1989 
1990  goto func_exit;
1991  }
1992 
1993  rec_heap_top = page_header_get_ptr(page, PAGE_HEAP_TOP);
1994 
1995  if (UNIV_UNLIKELY(rec_heap_top
1996  > page_dir_get_nth_slot(page, n_slots - 1))) {
1997 
1998  fprintf(stderr,
1999  "InnoDB: Record heap and dir overlap on a page,"
2000  " heap top %lu, dir %lu\n",
2001  (ulong) page_header_get_field(page, PAGE_HEAP_TOP),
2002  (ulong)
2003  page_offset(page_dir_get_nth_slot(page, n_slots - 1)));
2004 
2005  goto func_exit;
2006  }
2007 
2008  /* Validate the record list in a loop checking also that it is
2009  consistent with the page record directory. */
2010 
2011  count = 0;
2012  own_count = 1;
2013  slot_no = 0;
2014  slot = page_dir_get_nth_slot(page, slot_no);
2015 
2016  rec = page_get_infimum_rec(page);
2017 
2018  for (;;) {
2019  if (UNIV_UNLIKELY(rec > rec_heap_top)) {
2020  fprintf(stderr,
2021  "InnoDB: Record %lu is above"
2022  " rec heap top %lu\n",
2023  (ulong)(rec - page),
2024  (ulong)(rec_heap_top - page));
2025 
2026  goto func_exit;
2027  }
2028 
2029  if (UNIV_UNLIKELY(rec_get_n_owned_old(rec))) {
2030  /* This is a record pointed to by a dir slot */
2031  if (UNIV_UNLIKELY(rec_get_n_owned_old(rec)
2032  != own_count)) {
2033 
2034  fprintf(stderr,
2035  "InnoDB: Wrong owned count %lu, %lu,"
2036  " rec %lu\n",
2037  (ulong) rec_get_n_owned_old(rec),
2038  (ulong) own_count,
2039  (ulong)(rec - page));
2040 
2041  goto func_exit;
2042  }
2043 
2044  if (UNIV_UNLIKELY
2045  (page_dir_slot_get_rec(slot) != rec)) {
2046  fprintf(stderr,
2047  "InnoDB: Dir slot does not point"
2048  " to right rec %lu\n",
2049  (ulong)(rec - page));
2050 
2051  goto func_exit;
2052  }
2053 
2054  own_count = 0;
2055 
2056  if (!page_rec_is_supremum(rec)) {
2057  slot_no++;
2058  slot = page_dir_get_nth_slot(page, slot_no);
2059  }
2060  }
2061 
2062  if (page_rec_is_supremum(rec)) {
2063 
2064  break;
2065  }
2066 
2067  if (UNIV_UNLIKELY
2068  (rec_get_next_offs(rec, FALSE) < FIL_PAGE_DATA
2069  || rec_get_next_offs(rec, FALSE) >= UNIV_PAGE_SIZE)) {
2070  fprintf(stderr,
2071  "InnoDB: Next record offset"
2072  " nonsensical %lu for rec %lu\n",
2073  (ulong) rec_get_next_offs(rec, FALSE),
2074  (ulong) (rec - page));
2075 
2076  goto func_exit;
2077  }
2078 
2079  count++;
2080 
2081  if (UNIV_UNLIKELY(count > UNIV_PAGE_SIZE)) {
2082  fprintf(stderr,
2083  "InnoDB: Page record list appears"
2084  " to be circular %lu\n",
2085  (ulong) count);
2086  goto func_exit;
2087  }
2088 
2089  rec = page_rec_get_next_const(rec);
2090  own_count++;
2091  }
2092 
2093  if (UNIV_UNLIKELY(rec_get_n_owned_old(rec) == 0)) {
2094  fprintf(stderr, "InnoDB: n owned is zero in a supremum rec\n");
2095 
2096  goto func_exit;
2097  }
2098 
2099  if (UNIV_UNLIKELY(slot_no != n_slots - 1)) {
2100  fprintf(stderr, "InnoDB: n slots wrong %lu, %lu\n",
2101  (ulong) slot_no, (ulong) (n_slots - 1));
2102  goto func_exit;
2103  }
2104 
2105  if (UNIV_UNLIKELY(page_header_get_field(page, PAGE_N_RECS)
2106  + PAGE_HEAP_NO_USER_LOW
2107  != count + 1)) {
2108  fprintf(stderr, "InnoDB: n recs wrong %lu %lu\n",
2109  (ulong) page_header_get_field(page, PAGE_N_RECS)
2110  + PAGE_HEAP_NO_USER_LOW,
2111  (ulong) (count + 1));
2112 
2113  goto func_exit;
2114  }
2115 
2116  /* Check then the free list */
2117  rec = page_header_get_ptr(page, PAGE_FREE);
2118 
2119  while (rec != NULL) {
2120  if (UNIV_UNLIKELY(rec < page + FIL_PAGE_DATA
2121  || rec >= page + UNIV_PAGE_SIZE)) {
2122  fprintf(stderr,
2123  "InnoDB: Free list record has"
2124  " a nonsensical offset %lu\n",
2125  (ulong) (rec - page));
2126 
2127  goto func_exit;
2128  }
2129 
2130  if (UNIV_UNLIKELY(rec > rec_heap_top)) {
2131  fprintf(stderr,
2132  "InnoDB: Free list record %lu"
2133  " is above rec heap top %lu\n",
2134  (ulong) (rec - page),
2135  (ulong) (rec_heap_top - page));
2136 
2137  goto func_exit;
2138  }
2139 
2140  count++;
2141 
2142  if (UNIV_UNLIKELY(count > UNIV_PAGE_SIZE)) {
2143  fprintf(stderr,
2144  "InnoDB: Page free list appears"
2145  " to be circular %lu\n",
2146  (ulong) count);
2147  goto func_exit;
2148  }
2149 
2150  rec = page_rec_get_next_const(rec);
2151  }
2152 
2153  if (UNIV_UNLIKELY(page_dir_get_n_heap(page) != count + 1)) {
2154 
2155  fprintf(stderr, "InnoDB: N heap is wrong %lu, %lu\n",
2156  (ulong) page_dir_get_n_heap(page),
2157  (ulong) (count + 1));
2158 
2159  goto func_exit;
2160  }
2161 
2162  ret = TRUE;
2163 
2164 func_exit:
2165  return(ret);
2166 }
2167 
2168 /***************************************************************/
2173 UNIV_INTERN
2174 ibool
2175 page_simple_validate_new(
2176 /*=====================*/
2177  const page_t* page)
2178 {
2179  const page_dir_slot_t* slot;
2180  ulint slot_no;
2181  ulint n_slots;
2182  const rec_t* rec;
2183  const byte* rec_heap_top;
2184  ulint count;
2185  ulint own_count;
2186  ibool ret = FALSE;
2187 
2188  ut_a(page_is_comp(page));
2189 
2190  /* Check first that the record heap and the directory do not
2191  overlap. */
2192 
2193  n_slots = page_dir_get_n_slots(page);
2194 
2195  if (UNIV_UNLIKELY(n_slots > UNIV_PAGE_SIZE / 4)) {
2196  fprintf(stderr,
2197  "InnoDB: Nonsensical number %lu"
2198  " of page dir slots\n", (ulong) n_slots);
2199 
2200  goto func_exit;
2201  }
2202 
2203  rec_heap_top = page_header_get_ptr(page, PAGE_HEAP_TOP);
2204 
2205  if (UNIV_UNLIKELY(rec_heap_top
2206  > page_dir_get_nth_slot(page, n_slots - 1))) {
2207 
2208  fprintf(stderr,
2209  "InnoDB: Record heap and dir overlap on a page,"
2210  " heap top %lu, dir %lu\n",
2211  (ulong) page_header_get_field(page, PAGE_HEAP_TOP),
2212  (ulong)
2213  page_offset(page_dir_get_nth_slot(page, n_slots - 1)));
2214 
2215  goto func_exit;
2216  }
2217 
2218  /* Validate the record list in a loop checking also that it is
2219  consistent with the page record directory. */
2220 
2221  count = 0;
2222  own_count = 1;
2223  slot_no = 0;
2224  slot = page_dir_get_nth_slot(page, slot_no);
2225 
2226  rec = page_get_infimum_rec(page);
2227 
2228  for (;;) {
2229  if (UNIV_UNLIKELY(rec > rec_heap_top)) {
2230  fprintf(stderr,
2231  "InnoDB: Record %lu is above rec"
2232  " heap top %lu\n",
2233  (ulong) page_offset(rec),
2234  (ulong) page_offset(rec_heap_top));
2235 
2236  goto func_exit;
2237  }
2238 
2239  if (UNIV_UNLIKELY(rec_get_n_owned_new(rec))) {
2240  /* This is a record pointed to by a dir slot */
2241  if (UNIV_UNLIKELY(rec_get_n_owned_new(rec)
2242  != own_count)) {
2243 
2244  fprintf(stderr,
2245  "InnoDB: Wrong owned count %lu, %lu,"
2246  " rec %lu\n",
2247  (ulong) rec_get_n_owned_new(rec),
2248  (ulong) own_count,
2249  (ulong) page_offset(rec));
2250 
2251  goto func_exit;
2252  }
2253 
2254  if (UNIV_UNLIKELY
2255  (page_dir_slot_get_rec(slot) != rec)) {
2256  fprintf(stderr,
2257  "InnoDB: Dir slot does not point"
2258  " to right rec %lu\n",
2259  (ulong) page_offset(rec));
2260 
2261  goto func_exit;
2262  }
2263 
2264  own_count = 0;
2265 
2266  if (!page_rec_is_supremum(rec)) {
2267  slot_no++;
2268  slot = page_dir_get_nth_slot(page, slot_no);
2269  }
2270  }
2271 
2272  if (page_rec_is_supremum(rec)) {
2273 
2274  break;
2275  }
2276 
2277  if (UNIV_UNLIKELY
2278  (rec_get_next_offs(rec, TRUE) < FIL_PAGE_DATA
2279  || rec_get_next_offs(rec, TRUE) >= UNIV_PAGE_SIZE)) {
2280  fprintf(stderr,
2281  "InnoDB: Next record offset nonsensical %lu"
2282  " for rec %lu\n",
2283  (ulong) rec_get_next_offs(rec, TRUE),
2284  (ulong) page_offset(rec));
2285 
2286  goto func_exit;
2287  }
2288 
2289  count++;
2290 
2291  if (UNIV_UNLIKELY(count > UNIV_PAGE_SIZE)) {
2292  fprintf(stderr,
2293  "InnoDB: Page record list appears"
2294  " to be circular %lu\n",
2295  (ulong) count);
2296  goto func_exit;
2297  }
2298 
2299  rec = page_rec_get_next_const(rec);
2300  own_count++;
2301  }
2302 
2303  if (UNIV_UNLIKELY(rec_get_n_owned_new(rec) == 0)) {
2304  fprintf(stderr, "InnoDB: n owned is zero"
2305  " in a supremum rec\n");
2306 
2307  goto func_exit;
2308  }
2309 
2310  if (UNIV_UNLIKELY(slot_no != n_slots - 1)) {
2311  fprintf(stderr, "InnoDB: n slots wrong %lu, %lu\n",
2312  (ulong) slot_no, (ulong) (n_slots - 1));
2313  goto func_exit;
2314  }
2315 
2316  if (UNIV_UNLIKELY(page_header_get_field(page, PAGE_N_RECS)
2317  + PAGE_HEAP_NO_USER_LOW
2318  != count + 1)) {
2319  fprintf(stderr, "InnoDB: n recs wrong %lu %lu\n",
2320  (ulong) page_header_get_field(page, PAGE_N_RECS)
2321  + PAGE_HEAP_NO_USER_LOW,
2322  (ulong) (count + 1));
2323 
2324  goto func_exit;
2325  }
2326 
2327  /* Check then the free list */
2328  rec = page_header_get_ptr(page, PAGE_FREE);
2329 
2330  while (rec != NULL) {
2331  if (UNIV_UNLIKELY(rec < page + FIL_PAGE_DATA
2332  || rec >= page + UNIV_PAGE_SIZE)) {
2333  fprintf(stderr,
2334  "InnoDB: Free list record has"
2335  " a nonsensical offset %lu\n",
2336  (ulong) page_offset(rec));
2337 
2338  goto func_exit;
2339  }
2340 
2341  if (UNIV_UNLIKELY(rec > rec_heap_top)) {
2342  fprintf(stderr,
2343  "InnoDB: Free list record %lu"
2344  " is above rec heap top %lu\n",
2345  (ulong) page_offset(rec),
2346  (ulong) page_offset(rec_heap_top));
2347 
2348  goto func_exit;
2349  }
2350 
2351  count++;
2352 
2353  if (UNIV_UNLIKELY(count > UNIV_PAGE_SIZE)) {
2354  fprintf(stderr,
2355  "InnoDB: Page free list appears"
2356  " to be circular %lu\n",
2357  (ulong) count);
2358  goto func_exit;
2359  }
2360 
2361  rec = page_rec_get_next_const(rec);
2362  }
2363 
2364  if (UNIV_UNLIKELY(page_dir_get_n_heap(page) != count + 1)) {
2365 
2366  fprintf(stderr, "InnoDB: N heap is wrong %lu, %lu\n",
2367  (ulong) page_dir_get_n_heap(page),
2368  (ulong) (count + 1));
2369 
2370  goto func_exit;
2371  }
2372 
2373  ret = TRUE;
2374 
2375 func_exit:
2376  return(ret);
2377 }
2378 
2379 /***************************************************************/
2382 UNIV_INTERN
2383 ibool
2384 page_validate(
2385 /*==========*/
2386  const page_t* page,
2387  dict_index_t* index)
2389 {
2390  const page_dir_slot_t* slot;
2391  mem_heap_t* heap;
2392  byte* buf;
2393  ulint count;
2394  ulint own_count;
2395  ulint rec_own_count;
2396  ulint slot_no;
2397  ulint data_size;
2398  const rec_t* rec;
2399  const rec_t* old_rec = NULL;
2400  ulint offs;
2401  ulint n_slots;
2402  ibool ret = FALSE;
2403  ulint i;
2404  ulint* offsets = NULL;
2405  ulint* old_offsets = NULL;
2406 
2407  if (UNIV_UNLIKELY((ibool) !!page_is_comp(page)
2408  != dict_table_is_comp(index->table))) {
2409  fputs("InnoDB: 'compact format' flag mismatch\n", stderr);
2410  goto func_exit2;
2411  }
2412  if (page_is_comp(page)) {
2413  if (UNIV_UNLIKELY(!page_simple_validate_new(page))) {
2414  goto func_exit2;
2415  }
2416  } else {
2417  if (UNIV_UNLIKELY(!page_simple_validate_old(page))) {
2418  goto func_exit2;
2419  }
2420  }
2421 
2422  if (dict_index_is_sec_or_ibuf(index) && page_is_leaf(page)
2423  && !page_is_empty(page)) {
2424  trx_id_t max_trx_id = page_get_max_trx_id(page);
2425  trx_id_t sys_max_trx_id = trx_sys_get_max_trx_id();
2426 
2427  if (max_trx_id == 0 || max_trx_id > sys_max_trx_id) {
2428  ib_logf(IB_LOG_LEVEL_ERROR,
2429  "PAGE_MAX_TRX_ID out of bounds: "
2430  TRX_ID_FMT ", " TRX_ID_FMT,
2431  max_trx_id, sys_max_trx_id);
2432  goto func_exit2;
2433  }
2434  }
2435 
2436  heap = mem_heap_create(UNIV_PAGE_SIZE + 200);
2437 
2438  /* The following buffer is used to check that the
2439  records in the page record heap do not overlap */
2440 
2441  buf = static_cast<byte*>(mem_heap_zalloc(heap, UNIV_PAGE_SIZE));
2442 
2443  /* Check first that the record heap and the directory do not
2444  overlap. */
2445 
2446  n_slots = page_dir_get_n_slots(page);
2447 
2448  if (UNIV_UNLIKELY(!(page_header_get_ptr(page, PAGE_HEAP_TOP)
2449  <= page_dir_get_nth_slot(page, n_slots - 1)))) {
2450 
2451  fprintf(stderr,
2452  "InnoDB: Record heap and dir overlap"
2453  " on space %lu page %lu index %s, %p, %p\n",
2454  (ulong) page_get_space_id(page),
2455  (ulong) page_get_page_no(page), index->name,
2456  page_header_get_ptr(page, PAGE_HEAP_TOP),
2457  page_dir_get_nth_slot(page, n_slots - 1));
2458 
2459  goto func_exit;
2460  }
2461 
2462  /* Validate the record list in a loop checking also that
2463  it is consistent with the directory. */
2464  count = 0;
2465  data_size = 0;
2466  own_count = 1;
2467  slot_no = 0;
2468  slot = page_dir_get_nth_slot(page, slot_no);
2469 
2470  rec = page_get_infimum_rec(page);
2471 
2472  for (;;) {
2473  offsets = rec_get_offsets(rec, index, offsets,
2474  ULINT_UNDEFINED, &heap);
2475 
2476  if (page_is_comp(page) && page_rec_is_user_rec(rec)
2477  && UNIV_UNLIKELY(rec_get_node_ptr_flag(rec)
2478  == page_is_leaf(page))) {
2479  fputs("InnoDB: node_ptr flag mismatch\n", stderr);
2480  goto func_exit;
2481  }
2482 
2483  if (UNIV_UNLIKELY(!page_rec_validate(rec, offsets))) {
2484  goto func_exit;
2485  }
2486 
2487 #ifndef UNIV_HOTBACKUP
2488  /* Check that the records are in the ascending order */
2489  if (UNIV_LIKELY(count >= PAGE_HEAP_NO_USER_LOW)
2490  && !page_rec_is_supremum(rec)) {
2491  if (UNIV_UNLIKELY
2492  (1 != cmp_rec_rec(rec, old_rec,
2493  offsets, old_offsets, index))) {
2494  fprintf(stderr,
2495  "InnoDB: Records in wrong order"
2496  " on space %lu page %lu index %s\n",
2497  (ulong) page_get_space_id(page),
2498  (ulong) page_get_page_no(page),
2499  index->name);
2500  fputs("\nInnoDB: previous record ", stderr);
2501  rec_print_new(stderr, old_rec, old_offsets);
2502  fputs("\nInnoDB: record ", stderr);
2503  rec_print_new(stderr, rec, offsets);
2504  putc('\n', stderr);
2505 
2506  goto func_exit;
2507  }
2508  }
2509 #endif /* !UNIV_HOTBACKUP */
2510 
2511  if (page_rec_is_user_rec(rec)) {
2512 
2513  data_size += rec_offs_size(offsets);
2514  }
2515 
2516  offs = page_offset(rec_get_start(rec, offsets));
2517  i = rec_offs_size(offsets);
2518  if (UNIV_UNLIKELY(offs + i >= UNIV_PAGE_SIZE)) {
2519  fputs("InnoDB: record offset out of bounds\n", stderr);
2520  goto func_exit;
2521  }
2522 
2523  while (i--) {
2524  if (UNIV_UNLIKELY(buf[offs + i])) {
2525  /* No other record may overlap this */
2526 
2527  fputs("InnoDB: Record overlaps another\n",
2528  stderr);
2529  goto func_exit;
2530  }
2531 
2532  buf[offs + i] = 1;
2533  }
2534 
2535  if (page_is_comp(page)) {
2536  rec_own_count = rec_get_n_owned_new(rec);
2537  } else {
2538  rec_own_count = rec_get_n_owned_old(rec);
2539  }
2540 
2541  if (UNIV_UNLIKELY(rec_own_count)) {
2542  /* This is a record pointed to by a dir slot */
2543  if (UNIV_UNLIKELY(rec_own_count != own_count)) {
2544  fprintf(stderr,
2545  "InnoDB: Wrong owned count %lu, %lu\n",
2546  (ulong) rec_own_count,
2547  (ulong) own_count);
2548  goto func_exit;
2549  }
2550 
2551  if (page_dir_slot_get_rec(slot) != rec) {
2552  fputs("InnoDB: Dir slot does not"
2553  " point to right rec\n",
2554  stderr);
2555  goto func_exit;
2556  }
2557 
2558  page_dir_slot_check(slot);
2559 
2560  own_count = 0;
2561  if (!page_rec_is_supremum(rec)) {
2562  slot_no++;
2563  slot = page_dir_get_nth_slot(page, slot_no);
2564  }
2565  }
2566 
2567  if (page_rec_is_supremum(rec)) {
2568  break;
2569  }
2570 
2571  count++;
2572  own_count++;
2573  old_rec = rec;
2574  rec = page_rec_get_next_const(rec);
2575 
2576  /* set old_offsets to offsets; recycle offsets */
2577  {
2578  ulint* offs = old_offsets;
2579  old_offsets = offsets;
2580  offsets = offs;
2581  }
2582  }
2583 
2584  if (page_is_comp(page)) {
2585  if (UNIV_UNLIKELY(rec_get_n_owned_new(rec) == 0)) {
2586 
2587  goto n_owned_zero;
2588  }
2589  } else if (UNIV_UNLIKELY(rec_get_n_owned_old(rec) == 0)) {
2590 n_owned_zero:
2591  fputs("InnoDB: n owned is zero\n", stderr);
2592  goto func_exit;
2593  }
2594 
2595  if (UNIV_UNLIKELY(slot_no != n_slots - 1)) {
2596  fprintf(stderr, "InnoDB: n slots wrong %lu %lu\n",
2597  (ulong) slot_no, (ulong) (n_slots - 1));
2598  goto func_exit;
2599  }
2600 
2601  if (UNIV_UNLIKELY(page_header_get_field(page, PAGE_N_RECS)
2602  + PAGE_HEAP_NO_USER_LOW
2603  != count + 1)) {
2604  fprintf(stderr, "InnoDB: n recs wrong %lu %lu\n",
2605  (ulong) page_header_get_field(page, PAGE_N_RECS)
2606  + PAGE_HEAP_NO_USER_LOW,
2607  (ulong) (count + 1));
2608  goto func_exit;
2609  }
2610 
2611  if (UNIV_UNLIKELY(data_size != page_get_data_size(page))) {
2612  fprintf(stderr,
2613  "InnoDB: Summed data size %lu, returned by func %lu\n",
2614  (ulong) data_size, (ulong) page_get_data_size(page));
2615  goto func_exit;
2616  }
2617 
2618  /* Check then the free list */
2619  rec = page_header_get_ptr(page, PAGE_FREE);
2620 
2621  while (rec != NULL) {
2622  offsets = rec_get_offsets(rec, index, offsets,
2623  ULINT_UNDEFINED, &heap);
2624  if (UNIV_UNLIKELY(!page_rec_validate(rec, offsets))) {
2625 
2626  goto func_exit;
2627  }
2628 
2629  count++;
2630  offs = page_offset(rec_get_start(rec, offsets));
2631  i = rec_offs_size(offsets);
2632  if (UNIV_UNLIKELY(offs + i >= UNIV_PAGE_SIZE)) {
2633  fputs("InnoDB: record offset out of bounds\n", stderr);
2634  goto func_exit;
2635  }
2636 
2637  while (i--) {
2638 
2639  if (UNIV_UNLIKELY(buf[offs + i])) {
2640  fputs("InnoDB: Record overlaps another"
2641  " in free list\n", stderr);
2642  goto func_exit;
2643  }
2644 
2645  buf[offs + i] = 1;
2646  }
2647 
2648  rec = page_rec_get_next_const(rec);
2649  }
2650 
2651  if (UNIV_UNLIKELY(page_dir_get_n_heap(page) != count + 1)) {
2652  fprintf(stderr, "InnoDB: N heap is wrong %lu %lu\n",
2653  (ulong) page_dir_get_n_heap(page),
2654  (ulong) count + 1);
2655  goto func_exit;
2656  }
2657 
2658  ret = TRUE;
2659 
2660 func_exit:
2661  mem_heap_free(heap);
2662 
2663  if (UNIV_UNLIKELY(ret == FALSE)) {
2664 func_exit2:
2665  fprintf(stderr,
2666  "InnoDB: Apparent corruption"
2667  " in space %lu page %lu index %s\n",
2668  (ulong) page_get_space_id(page),
2669  (ulong) page_get_page_no(page),
2670  index->name);
2671  buf_page_print(page, 0, 0);
2672  }
2673 
2674  return(ret);
2675 }
2676 
2677 #ifndef UNIV_HOTBACKUP
2678 /***************************************************************/
2681 UNIV_INTERN
2682 const rec_t*
2683 page_find_rec_with_heap_no(
2684 /*=======================*/
2685  const page_t* page,
2686  ulint heap_no)
2687 {
2688  const rec_t* rec;
2689 
2690  if (page_is_comp(page)) {
2691  rec = page + PAGE_NEW_INFIMUM;
2692 
2693  for(;;) {
2694  ulint rec_heap_no = rec_get_heap_no_new(rec);
2695 
2696  if (rec_heap_no == heap_no) {
2697 
2698  return(rec);
2699  } else if (rec_heap_no == PAGE_HEAP_NO_SUPREMUM) {
2700 
2701  return(NULL);
2702  }
2703 
2704  rec = page + rec_get_next_offs(rec, TRUE);
2705  }
2706  } else {
2707  rec = page + PAGE_OLD_INFIMUM;
2708 
2709  for (;;) {
2710  ulint rec_heap_no = rec_get_heap_no_old(rec);
2711 
2712  if (rec_heap_no == heap_no) {
2713 
2714  return(rec);
2715  } else if (rec_heap_no == PAGE_HEAP_NO_SUPREMUM) {
2716 
2717  return(NULL);
2718  }
2719 
2720  rec = page + rec_get_next_offs(rec, FALSE);
2721  }
2722  }
2723 }
2724 #endif /* !UNIV_HOTBACKUP */
2725 
2726 /*******************************************************/
2731 UNIV_INTERN
2732 bool
2733 page_delete_rec(
2734 /*============*/
2735  const dict_index_t* index,
2737  page_cur_t* pcur,
2739  page_zip_des_t* page_zip,
2740  const ulint* offsets)
2741 {
2742  bool no_compress_needed;
2743  buf_block_t* block = pcur->block;
2744  page_t* page = buf_block_get_frame(block);
2745 
2746  ut_ad(page_is_leaf(page));
2747 
2748  if (!rec_offs_any_extern(offsets)
2749  && ((page_get_data_size(page) - rec_offs_size(offsets)
2750  < BTR_CUR_PAGE_COMPRESS_LIMIT)
2751  || (mach_read_from_4(page + FIL_PAGE_NEXT) == FIL_NULL
2752  && mach_read_from_4(page + FIL_PAGE_PREV) == FIL_NULL)
2753  || (page_get_n_recs(page) < 2))) {
2754 
2755  ulint root_page_no = dict_index_get_page(index);
2756 
2757  /* The page fillfactor will drop below a predefined
2758  minimum value, OR the level in the B-tree contains just
2759  one page, OR the page will become empty: we recommend
2760  compression if this is not the root page. */
2761 
2762  no_compress_needed = page_get_page_no(page) == root_page_no;
2763  } else {
2764  no_compress_needed = true;
2765  }
2766 
2767  if (no_compress_needed) {
2768 #ifdef UNIV_ZIP_DEBUG
2769  ut_a(!page_zip || page_zip_validate(page_zip, page, index));
2770 #endif /* UNIV_ZIP_DEBUG */
2771 
2772  page_cur_delete_rec(pcur, index, offsets, 0);
2773 
2774 #ifdef UNIV_ZIP_DEBUG
2775  ut_a(!page_zip || page_zip_validate(page_zip, page, index));
2776 #endif /* UNIV_ZIP_DEBUG */
2777  }
2778 
2779  return(no_compress_needed);
2780 }
2781