Drizzled Public API Documentation

page0page.cc

00001 /*****************************************************************************
00002 
00003 Copyright (C) 1994, 2010, Innobase Oy. All Rights Reserved.
00004 
00005 This program is free software; you can redistribute it and/or modify it under
00006 the terms of the GNU General Public License as published by the Free Software
00007 Foundation; version 2 of the License.
00008 
00009 This program is distributed in the hope that it will be useful, but WITHOUT
00010 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00011 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
00012 
00013 You should have received a copy of the GNU General Public License along with
00014 this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
00015 St, Fifth Floor, Boston, MA 02110-1301 USA
00016 
00017 *****************************************************************************/
00018 
00019 /**************************************************/
00026 #include "page0page.h"
00027 #ifdef UNIV_NONINL
00028 #include "page0page.ic"
00029 #endif
00030 
00031 #include "page0cur.h"
00032 #include "page0zip.h"
00033 #include "buf0buf.h"
00034 #include "btr0btr.h"
00035 #ifndef UNIV_HOTBACKUP
00036 # include "srv0srv.h"
00037 # include "lock0lock.h"
00038 # include "fut0lst.h"
00039 # include "btr0sea.h"
00040 #endif /* !UNIV_HOTBACKUP */
00041 
00042 /*      THE INDEX PAGE
00043       ==============
00044 
00045 The index page consists of a page header which contains the page's
00046 id and other information. On top of it are the the index records
00047 in a heap linked into a one way linear list according to alphabetic order.
00048 
00049 Just below page end is an array of pointers which we call page directory,
00050 to about every sixth record in the list. The pointers are placed in
00051 the directory in the alphabetical order of the records pointed to,
00052 enabling us to make binary search using the array. Each slot n:o I
00053 in the directory points to a record, where a 4-bit field contains a count
00054 of those records which are in the linear list between pointer I and
00055 the pointer I - 1 in the directory, including the record
00056 pointed to by pointer I and not including the record pointed to by I - 1.
00057 We say that the record pointed to by slot I, or that slot I, owns
00058 these records. The count is always kept in the range 4 to 8, with
00059 the exception that it is 1 for the first slot, and 1--8 for the second slot.
00060 
00061 An essentially binary search can be performed in the list of index
00062 records, like we could do if we had pointer to every record in the
00063 page directory. The data structure is, however, more efficient when
00064 we are doing inserts, because most inserts are just pushed on a heap.
00065 Only every 8th insert requires block move in the directory pointer
00066 table, which itself is quite small. A record is deleted from the page
00067 by just taking it off the linear list and updating the number of owned
00068 records-field of the record which owns it, and updating the page directory,
00069 if necessary. A special case is the one when the record owns itself.
00070 Because the overhead of inserts is so small, we may also increase the
00071 page size from the projected default of 8 kB to 64 kB without too
00072 much loss of efficiency in inserts. Bigger page becomes actual
00073 when the disk transfer rate compared to seek and latency time rises.
00074 On the present system, the page size is set so that the page transfer
00075 time (3 ms) is 20 % of the disk random access time (15 ms).
00076 
00077 When the page is split, merged, or becomes full but contains deleted
00078 records, we have to reorganize the page.
00079 
00080 Assuming a page size of 8 kB, a typical index page of a secondary
00081 index contains 300 index entries, and the size of the page directory
00082 is 50 x 4 bytes = 200 bytes. */
00083 
00084 /***************************************************************/
00087 UNIV_INTERN
00088 ulint
00089 page_dir_find_owner_slot(
00090 /*=====================*/
00091   const rec_t*  rec)  
00092 {
00093   const page_t*     page;
00094   register uint16     rec_offs_bytes;
00095   register const page_dir_slot_t* slot;
00096   register const page_dir_slot_t* first_slot;
00097   register const rec_t*   r = rec;
00098 
00099   ut_ad(page_rec_check(rec));
00100 
00101   page = page_align(rec);
00102   first_slot = page_dir_get_nth_slot(page, 0);
00103   slot = page_dir_get_nth_slot(page, page_dir_get_n_slots(page) - 1);
00104 
00105   if (page_is_comp(page)) {
00106     while (rec_get_n_owned_new(r) == 0) {
00107       r = rec_get_next_ptr_const(r, TRUE);
00108       ut_ad(r >= page + PAGE_NEW_SUPREMUM);
00109       ut_ad(r < page + (UNIV_PAGE_SIZE - PAGE_DIR));
00110     }
00111   } else {
00112     while (rec_get_n_owned_old(r) == 0) {
00113       r = rec_get_next_ptr_const(r, FALSE);
00114       ut_ad(r >= page + PAGE_OLD_SUPREMUM);
00115       ut_ad(r < page + (UNIV_PAGE_SIZE - PAGE_DIR));
00116     }
00117   }
00118 
00119   rec_offs_bytes = mach_encode_2(r - page);
00120 
00121   while (UNIV_LIKELY(*(uint16*) slot != rec_offs_bytes)) {
00122 
00123     if (UNIV_UNLIKELY(slot == first_slot)) {
00124       fprintf(stderr,
00125         "InnoDB: Probable data corruption on"
00126         " page %lu\n"
00127         "InnoDB: Original record ",
00128         (ulong) page_get_page_no(page));
00129 
00130       if (page_is_comp(page)) {
00131         fputs("(compact record)", stderr);
00132       } else {
00133         rec_print_old(stderr, rec);
00134       }
00135 
00136       fputs("\n"
00137             "InnoDB: on that page.\n"
00138             "InnoDB: Cannot find the dir slot for record ",
00139             stderr);
00140       if (page_is_comp(page)) {
00141         fputs("(compact record)", stderr);
00142       } else {
00143         rec_print_old(stderr, page
00144                 + mach_decode_2(rec_offs_bytes));
00145       }
00146       fputs("\n"
00147             "InnoDB: on that page!\n", stderr);
00148 
00149       buf_page_print(page, 0);
00150 
00151       ut_error;
00152     }
00153 
00154     slot += PAGE_DIR_SLOT_SIZE;
00155   }
00156 
00157   return(((ulint) (first_slot - slot)) / PAGE_DIR_SLOT_SIZE);
00158 }
00159 
00160 /**************************************************************/
00163 static
00164 ibool
00165 page_dir_slot_check(
00166 /*================*/
00167   page_dir_slot_t*  slot) 
00168 {
00169   page_t* page;
00170   ulint n_slots;
00171   ulint n_owned;
00172 
00173   ut_a(slot);
00174 
00175   page = page_align(slot);
00176 
00177   n_slots = page_dir_get_n_slots(page);
00178 
00179   ut_a(slot <= page_dir_get_nth_slot(page, 0));
00180   ut_a(slot >= page_dir_get_nth_slot(page, n_slots - 1));
00181 
00182   ut_a(page_rec_check(page_dir_slot_get_rec(slot)));
00183 
00184   if (page_is_comp(page)) {
00185     n_owned = rec_get_n_owned_new(page_dir_slot_get_rec(slot));
00186   } else {
00187     n_owned = rec_get_n_owned_old(page_dir_slot_get_rec(slot));
00188   }
00189 
00190   if (slot == page_dir_get_nth_slot(page, 0)) {
00191     ut_a(n_owned == 1);
00192   } else if (slot == page_dir_get_nth_slot(page, n_slots - 1)) {
00193     ut_a(n_owned >= 1);
00194     ut_a(n_owned <= PAGE_DIR_SLOT_MAX_N_OWNED);
00195   } else {
00196     ut_a(n_owned >= PAGE_DIR_SLOT_MIN_N_OWNED);
00197     ut_a(n_owned <= PAGE_DIR_SLOT_MAX_N_OWNED);
00198   }
00199 
00200   return(TRUE);
00201 }
00202 
00203 /*************************************************************/
00205 UNIV_INTERN
00206 void
00207 page_set_max_trx_id(
00208 /*================*/
00209   buf_block_t*  block,  
00210   page_zip_des_t* page_zip,
00211   trx_id_t  trx_id, 
00212   mtr_t*    mtr)  
00213 {
00214   page_t*   page    = buf_block_get_frame(block);
00215 #ifndef UNIV_HOTBACKUP
00216   const ibool is_hashed = block->is_hashed;
00217 
00218   if (is_hashed) {
00219     rw_lock_x_lock(&btr_search_latch);
00220   }
00221 
00222   ut_ad(!mtr || mtr_memo_contains(mtr, block, MTR_MEMO_PAGE_X_FIX));
00223 #endif /* !UNIV_HOTBACKUP */
00224 
00225   /* It is not necessary to write this change to the redo log, as
00226   during a database recovery we assume that the max trx id of every
00227   page is the maximum trx id assigned before the crash. */
00228 
00229   if (UNIV_LIKELY_NULL(page_zip)) {
00230     mach_write_to_8(page + (PAGE_HEADER + PAGE_MAX_TRX_ID), trx_id);
00231     page_zip_write_header(page_zip,
00232               page + (PAGE_HEADER + PAGE_MAX_TRX_ID),
00233               8, mtr);
00234 #ifndef UNIV_HOTBACKUP
00235   } else if (mtr) {
00236     mlog_write_ull(page + (PAGE_HEADER + PAGE_MAX_TRX_ID),
00237              trx_id, mtr);
00238 #endif /* !UNIV_HOTBACKUP */
00239   } else {
00240     mach_write_to_8(page + (PAGE_HEADER + PAGE_MAX_TRX_ID), trx_id);
00241   }
00242 
00243 #ifndef UNIV_HOTBACKUP
00244   if (is_hashed) {
00245     rw_lock_x_unlock(&btr_search_latch);
00246   }
00247 #endif /* !UNIV_HOTBACKUP */
00248 }
00249 
00250 /************************************************************/
00253 UNIV_INTERN
00254 byte*
00255 page_mem_alloc_heap(
00256 /*================*/
00257   page_t*   page, 
00258   page_zip_des_t* page_zip,
00261   ulint   need, 
00262   ulint*    heap_no)
00265 {
00266   byte* block;
00267   ulint avl_space;
00268 
00269   ut_ad(page && heap_no);
00270 
00271   avl_space = page_get_max_insert_size(page, 1);
00272 
00273   if (avl_space >= need) {
00274     block = page_header_get_ptr(page, PAGE_HEAP_TOP);
00275 
00276     page_header_set_ptr(page, page_zip, PAGE_HEAP_TOP,
00277             block + need);
00278     *heap_no = page_dir_get_n_heap(page);
00279 
00280     page_dir_set_n_heap(page, page_zip, 1 + *heap_no);
00281 
00282     return(block);
00283   }
00284 
00285   return(NULL);
00286 }
00287 
00288 #ifndef UNIV_HOTBACKUP
00289 /**********************************************************/
00291 UNIV_INLINE
00292 void
00293 page_create_write_log(
00294 /*==================*/
00295   buf_frame_t*  frame,  
00297   mtr_t*    mtr,  
00298   ibool   comp) 
00299 {
00300   mlog_write_initial_log_record(frame, comp
00301               ? MLOG_COMP_PAGE_CREATE
00302               : MLOG_PAGE_CREATE, mtr);
00303 }
00304 #else /* !UNIV_HOTBACKUP */
00305 # define page_create_write_log(frame,mtr,comp) ((void) 0)
00306 #endif /* !UNIV_HOTBACKUP */
00307 
00308 /***********************************************************/
00311 UNIV_INTERN
00312 byte*
00313 page_parse_create(
00314 /*==============*/
00315   byte*   ptr,  
00316   byte*   /*end_ptr __attribute__((unused))*/, 
00317   ulint   comp, 
00318   buf_block_t*  block,  
00319   mtr_t*    mtr)  
00320 {
00321   ut_ad(ptr && end_ptr);
00322 
00323   /* The record is empty, except for the record initial part */
00324 
00325   if (block) {
00326     page_create(block, mtr, comp);
00327   }
00328 
00329   return(ptr);
00330 }
00331 
00332 /**********************************************************/
00335 static
00336 page_t*
00337 page_create_low(
00338 /*============*/
00339   buf_block_t*  block,    
00341   ulint   comp)   
00342 {
00343   page_dir_slot_t* slot;
00344   mem_heap_t* heap;
00345   dtuple_t* tuple;
00346   dfield_t* field;
00347   byte*   heap_top;
00348   rec_t*    infimum_rec;
00349   rec_t*    supremum_rec;
00350   page_t*   page;
00351   dict_index_t* index;
00352   ulint*    offsets;
00353 
00354   ut_ad(block);
00355 #if PAGE_BTR_IBUF_FREE_LIST + FLST_BASE_NODE_SIZE > PAGE_DATA
00356 # error "PAGE_BTR_IBUF_FREE_LIST + FLST_BASE_NODE_SIZE > PAGE_DATA"
00357 #endif
00358 #if PAGE_BTR_IBUF_FREE_LIST_NODE + FLST_NODE_SIZE > PAGE_DATA
00359 # error "PAGE_BTR_IBUF_FREE_LIST_NODE + FLST_NODE_SIZE > PAGE_DATA"
00360 #endif
00361 
00362   /* The infimum and supremum records use a dummy index. */
00363   if (UNIV_LIKELY(comp)) {
00364     index = dict_ind_compact;
00365   } else {
00366     index = dict_ind_redundant;
00367   }
00368 
00369   /* 1. INCREMENT MODIFY CLOCK */
00370   buf_block_modify_clock_inc(block);
00371 
00372   page = buf_block_get_frame(block);
00373 
00374   fil_page_set_type(page, FIL_PAGE_INDEX);
00375 
00376   heap = mem_heap_create(200);
00377 
00378   /* 3. CREATE THE INFIMUM AND SUPREMUM RECORDS */
00379 
00380   /* Create first a data tuple for infimum record */
00381   tuple = dtuple_create(heap, 1);
00382   dtuple_set_info_bits(tuple, REC_STATUS_INFIMUM);
00383   field = dtuple_get_nth_field(tuple, 0);
00384 
00385   dfield_set_data(field, "infimum", 8);
00386   dtype_set(dfield_get_type(field),
00387       DATA_VARCHAR, DATA_ENGLISH | DATA_NOT_NULL, 8);
00388   /* Set the corresponding physical record to its place in the page
00389   record heap */
00390 
00391   heap_top = page + PAGE_DATA;
00392 
00393   infimum_rec = rec_convert_dtuple_to_rec(heap_top, index, tuple, 0);
00394 
00395   if (UNIV_LIKELY(comp)) {
00396     ut_a(infimum_rec == page + PAGE_NEW_INFIMUM);
00397 
00398     rec_set_n_owned_new(infimum_rec, NULL, 1);
00399     rec_set_heap_no_new(infimum_rec, 0);
00400   } else {
00401     ut_a(infimum_rec == page + PAGE_OLD_INFIMUM);
00402 
00403     rec_set_n_owned_old(infimum_rec, 1);
00404     rec_set_heap_no_old(infimum_rec, 0);
00405   }
00406 
00407   offsets = rec_get_offsets(infimum_rec, index, NULL,
00408           ULINT_UNDEFINED, &heap);
00409 
00410   heap_top = rec_get_end(infimum_rec, offsets);
00411 
00412   /* Create then a tuple for supremum */
00413 
00414   tuple = dtuple_create(heap, 1);
00415   dtuple_set_info_bits(tuple, REC_STATUS_SUPREMUM);
00416   field = dtuple_get_nth_field(tuple, 0);
00417 
00418   dfield_set_data(field, "supremum", comp ? 8 : 9);
00419   dtype_set(dfield_get_type(field),
00420       DATA_VARCHAR, DATA_ENGLISH | DATA_NOT_NULL, comp ? 8 : 9);
00421 
00422   supremum_rec = rec_convert_dtuple_to_rec(heap_top, index, tuple, 0);
00423 
00424   if (UNIV_LIKELY(comp)) {
00425     ut_a(supremum_rec == page + PAGE_NEW_SUPREMUM);
00426 
00427     rec_set_n_owned_new(supremum_rec, NULL, 1);
00428     rec_set_heap_no_new(supremum_rec, 1);
00429   } else {
00430     ut_a(supremum_rec == page + PAGE_OLD_SUPREMUM);
00431 
00432     rec_set_n_owned_old(supremum_rec, 1);
00433     rec_set_heap_no_old(supremum_rec, 1);
00434   }
00435 
00436   offsets = rec_get_offsets(supremum_rec, index, offsets,
00437           ULINT_UNDEFINED, &heap);
00438   heap_top = rec_get_end(supremum_rec, offsets);
00439 
00440   ut_ad(heap_top == page
00441         + (comp ? PAGE_NEW_SUPREMUM_END : PAGE_OLD_SUPREMUM_END));
00442 
00443   mem_heap_free(heap);
00444 
00445   /* 4. INITIALIZE THE PAGE */
00446 
00447   page_header_set_field(page, NULL, PAGE_N_DIR_SLOTS, 2);
00448   page_header_set_ptr(page, NULL, PAGE_HEAP_TOP, heap_top);
00449   page_header_set_field(page, NULL, PAGE_N_HEAP, comp
00450             ? 0x8000 | PAGE_HEAP_NO_USER_LOW
00451             : PAGE_HEAP_NO_USER_LOW);
00452   page_header_set_ptr(page, NULL, PAGE_FREE, NULL);
00453   page_header_set_field(page, NULL, PAGE_GARBAGE, 0);
00454   page_header_set_ptr(page, NULL, PAGE_LAST_INSERT, NULL);
00455   page_header_set_field(page, NULL, PAGE_DIRECTION, PAGE_NO_DIRECTION);
00456   page_header_set_field(page, NULL, PAGE_N_DIRECTION, 0);
00457   page_header_set_field(page, NULL, PAGE_N_RECS, 0);
00458   page_set_max_trx_id(block, NULL, 0, NULL);
00459   memset(heap_top, 0, UNIV_PAGE_SIZE - PAGE_EMPTY_DIR_START
00460          - page_offset(heap_top));
00461 
00462   /* 5. SET POINTERS IN RECORDS AND DIR SLOTS */
00463 
00464   /* Set the slots to point to infimum and supremum. */
00465 
00466   slot = page_dir_get_nth_slot(page, 0);
00467   page_dir_slot_set_rec(slot, infimum_rec);
00468 
00469   slot = page_dir_get_nth_slot(page, 1);
00470   page_dir_slot_set_rec(slot, supremum_rec);
00471 
00472   /* Set the next pointers in infimum and supremum */
00473 
00474   if (UNIV_LIKELY(comp)) {
00475     rec_set_next_offs_new(infimum_rec, PAGE_NEW_SUPREMUM);
00476     rec_set_next_offs_new(supremum_rec, 0);
00477   } else {
00478     rec_set_next_offs_old(infimum_rec, PAGE_OLD_SUPREMUM);
00479     rec_set_next_offs_old(supremum_rec, 0);
00480   }
00481 
00482   return(page);
00483 }
00484 
00485 /**********************************************************/
00488 UNIV_INTERN
00489 page_t*
00490 page_create(
00491 /*========*/
00492   buf_block_t*  block,    
00494   mtr_t*    mtr,    
00495   ulint   comp)   
00496 {
00497   page_create_write_log(buf_block_get_frame(block), mtr, comp);
00498   return(page_create_low(block, comp));
00499 }
00500 
00501 /**********************************************************/
00504 UNIV_INTERN
00505 page_t*
00506 page_create_zip(
00507 /*============*/
00508   buf_block_t*  block,    
00510   dict_index_t* index,    
00511   ulint   level,    
00512   mtr_t*    mtr)    
00513 {
00514   page_t*   page;
00515   page_zip_des_t* page_zip  = buf_block_get_page_zip(block);
00516 
00517   ut_ad(block);
00518   ut_ad(page_zip);
00519   ut_ad(index);
00520   ut_ad(dict_table_is_comp(index->table));
00521 
00522   page = page_create_low(block, TRUE);
00523   mach_write_to_2(page + PAGE_HEADER + PAGE_LEVEL, level);
00524 
00525   if (UNIV_UNLIKELY(!page_zip_compress(page_zip, page, index, mtr))) {
00526     /* The compression of a newly created page
00527     should always succeed. */
00528     ut_error;
00529   }
00530 
00531   return(page);
00532 }
00533 
00534 /*************************************************************/
00537 UNIV_INTERN
00538 void
00539 page_copy_rec_list_end_no_locks(
00540 /*============================*/
00541   buf_block_t*  new_block,  
00542   buf_block_t*  block,    
00543   rec_t*    rec,    
00544   dict_index_t* index,    
00545   mtr_t*    mtr)    
00546 {
00547   page_t*   new_page  = buf_block_get_frame(new_block);
00548   page_cur_t  cur1;
00549   rec_t*    cur2;
00550   mem_heap_t* heap    = NULL;
00551   ulint   offsets_[REC_OFFS_NORMAL_SIZE];
00552   ulint*    offsets   = offsets_;
00553   rec_offs_init(offsets_);
00554 
00555   page_cur_position(rec, block, &cur1);
00556 
00557   if (page_cur_is_before_first(&cur1)) {
00558 
00559     page_cur_move_to_next(&cur1);
00560   }
00561 
00562   ut_a((ibool)!!page_is_comp(new_page)
00563        == dict_table_is_comp(index->table));
00564   ut_a(page_is_comp(new_page) == page_rec_is_comp(rec));
00565   ut_a(mach_read_from_2(new_page + UNIV_PAGE_SIZE - 10) == (ulint)
00566        (page_is_comp(new_page) ? PAGE_NEW_INFIMUM : PAGE_OLD_INFIMUM));
00567 
00568   cur2 = page_get_infimum_rec(buf_block_get_frame(new_block));
00569 
00570   /* Copy records from the original page to the new page */
00571 
00572   while (!page_cur_is_after_last(&cur1)) {
00573     rec_t*  cur1_rec = page_cur_get_rec(&cur1);
00574     rec_t*  ins_rec;
00575     offsets = rec_get_offsets(cur1_rec, index, offsets,
00576             ULINT_UNDEFINED, &heap);
00577     ins_rec = page_cur_insert_rec_low(cur2, index,
00578               cur1_rec, offsets, mtr);
00579     if (UNIV_UNLIKELY(!ins_rec)) {
00580       /* Track an assertion failure reported on the mailing
00581       list on June 18th, 2003 */
00582 
00583       buf_page_print(new_page, 0);
00584       buf_page_print(page_align(rec), 0);
00585       ut_print_timestamp(stderr);
00586 
00587       fprintf(stderr,
00588         "InnoDB: rec offset %lu, cur1 offset %lu,"
00589         " cur2 offset %lu\n",
00590         (ulong) page_offset(rec),
00591         (ulong) page_offset(page_cur_get_rec(&cur1)),
00592         (ulong) page_offset(cur2));
00593       ut_error;
00594     }
00595 
00596     page_cur_move_to_next(&cur1);
00597     cur2 = ins_rec;
00598   }
00599 
00600   if (UNIV_LIKELY_NULL(heap)) {
00601     mem_heap_free(heap);
00602   }
00603 }
00604 
00605 #ifndef UNIV_HOTBACKUP
00606 /*************************************************************/
00612 UNIV_INTERN
00613 rec_t*
00614 page_copy_rec_list_end(
00615 /*===================*/
00616   buf_block_t*  new_block,  
00617   buf_block_t*  block,    
00618   rec_t*    rec,    
00619   dict_index_t* index,    
00620   mtr_t*    mtr)    
00621 {
00622   page_t*   new_page  = buf_block_get_frame(new_block);
00623   page_zip_des_t* new_page_zip  = buf_block_get_page_zip(new_block);
00624   page_t*   page    = page_align(rec);
00625   rec_t*    ret   = page_rec_get_next(
00626     page_get_infimum_rec(new_page));
00627   ulint   log_mode  = 0; /* remove warning */
00628 
00629 #ifdef UNIV_ZIP_DEBUG
00630   if (new_page_zip) {
00631     page_zip_des_t* page_zip = buf_block_get_page_zip(block);
00632     ut_a(page_zip);
00633 
00634     /* Strict page_zip_validate() may fail here.
00635     Furthermore, btr_compress() may set FIL_PAGE_PREV to
00636     FIL_NULL on new_page while leaving it intact on
00637     new_page_zip.  So, we cannot validate new_page_zip. */
00638     ut_a(page_zip_validate_low(page_zip, page, TRUE));
00639   }
00640 #endif /* UNIV_ZIP_DEBUG */
00641   ut_ad(buf_block_get_frame(block) == page);
00642   ut_ad(page_is_leaf(page) == page_is_leaf(new_page));
00643   ut_ad(page_is_comp(page) == page_is_comp(new_page));
00644   /* Here, "ret" may be pointing to a user record or the
00645   predefined supremum record. */
00646 
00647   if (UNIV_LIKELY_NULL(new_page_zip)) {
00648     log_mode = mtr_set_log_mode(mtr, MTR_LOG_NONE);
00649   }
00650 
00651   if (page_dir_get_n_heap(new_page) == PAGE_HEAP_NO_USER_LOW) {
00652     page_copy_rec_list_end_to_created_page(new_page, rec,
00653                    index, mtr);
00654   } else {
00655     page_copy_rec_list_end_no_locks(new_block, block, rec,
00656             index, mtr);
00657   }
00658 
00659   /* Update PAGE_MAX_TRX_ID on the uncompressed page.
00660   Modifications will be redo logged and copied to the compressed
00661   page in page_zip_compress() or page_zip_reorganize() below. */
00662   if (dict_index_is_sec_or_ibuf(index) && page_is_leaf(page)) {
00663     page_update_max_trx_id(new_block, NULL,
00664                page_get_max_trx_id(page), mtr);
00665   }
00666 
00667   if (UNIV_LIKELY_NULL(new_page_zip)) {
00668     mtr_set_log_mode(mtr, log_mode);
00669 
00670     if (UNIV_UNLIKELY
00671         (!page_zip_compress(new_page_zip, new_page, index, mtr))) {
00672       /* Before trying to reorganize the page,
00673       store the number of preceding records on the page. */
00674       ulint ret_pos
00675         = page_rec_get_n_recs_before(ret);
00676       /* Before copying, "ret" was the successor of
00677       the predefined infimum record.  It must still
00678       have at least one predecessor (the predefined
00679       infimum record, or a freshly copied record
00680       that is smaller than "ret"). */
00681       ut_a(ret_pos > 0);
00682 
00683       if (UNIV_UNLIKELY
00684           (!page_zip_reorganize(new_block, index, mtr))) {
00685 
00686         if (UNIV_UNLIKELY
00687             (!page_zip_decompress(new_page_zip,
00688                 new_page, FALSE))) {
00689           ut_error;
00690         }
00691         ut_ad(page_validate(new_page, index));
00692         return(NULL);
00693       } else {
00694         /* The page was reorganized:
00695         Seek to ret_pos. */
00696         ret = new_page + PAGE_NEW_INFIMUM;
00697 
00698         do {
00699           ret = rec_get_next_ptr(ret, TRUE);
00700         } while (--ret_pos);
00701       }
00702     }
00703   }
00704 
00705   /* Update the lock table and possible hash index */
00706 
00707   lock_move_rec_list_end(new_block, block, rec);
00708 
00709   btr_search_move_or_delete_hash_entries(new_block, block, index);
00710 
00711   return(ret);
00712 }
00713 
00714 /*************************************************************/
00720 UNIV_INTERN
00721 rec_t*
00722 page_copy_rec_list_start(
00723 /*=====================*/
00724   buf_block_t*  new_block,  
00725   buf_block_t*  block,    
00726   rec_t*    rec,    
00727   dict_index_t* index,    
00728   mtr_t*    mtr)    
00729 {
00730   page_t*   new_page  = buf_block_get_frame(new_block);
00731   page_zip_des_t* new_page_zip  = buf_block_get_page_zip(new_block);
00732   page_cur_t  cur1;
00733   rec_t*    cur2;
00734   ulint   log_mode  = 0 /* remove warning */;
00735   mem_heap_t* heap    = NULL;
00736   rec_t*    ret
00737     = page_rec_get_prev(page_get_supremum_rec(new_page));
00738   ulint   offsets_[REC_OFFS_NORMAL_SIZE];
00739   ulint*    offsets   = offsets_;
00740   rec_offs_init(offsets_);
00741 
00742   /* Here, "ret" may be pointing to a user record or the
00743   predefined infimum record. */
00744 
00745   if (page_rec_is_infimum(rec)) {
00746 
00747     return(ret);
00748   }
00749 
00750   if (UNIV_LIKELY_NULL(new_page_zip)) {
00751     log_mode = mtr_set_log_mode(mtr, MTR_LOG_NONE);
00752   }
00753 
00754   page_cur_set_before_first(block, &cur1);
00755   page_cur_move_to_next(&cur1);
00756 
00757   cur2 = ret;
00758 
00759   /* Copy records from the original page to the new page */
00760 
00761   while (page_cur_get_rec(&cur1) != rec) {
00762     rec_t*  cur1_rec = page_cur_get_rec(&cur1);
00763     offsets = rec_get_offsets(cur1_rec, index, offsets,
00764             ULINT_UNDEFINED, &heap);
00765     cur2 = page_cur_insert_rec_low(cur2, index,
00766                  cur1_rec, offsets, mtr);
00767     ut_a(cur2);
00768 
00769     page_cur_move_to_next(&cur1);
00770   }
00771 
00772   if (UNIV_LIKELY_NULL(heap)) {
00773     mem_heap_free(heap);
00774   }
00775 
00776   /* Update PAGE_MAX_TRX_ID on the uncompressed page.
00777   Modifications will be redo logged and copied to the compressed
00778   page in page_zip_compress() or page_zip_reorganize() below. */
00779   if (dict_index_is_sec_or_ibuf(index)
00780       && page_is_leaf(page_align(rec))) {
00781     page_update_max_trx_id(new_block, NULL,
00782                page_get_max_trx_id(page_align(rec)),
00783                mtr);
00784   }
00785 
00786   if (UNIV_LIKELY_NULL(new_page_zip)) {
00787     mtr_set_log_mode(mtr, log_mode);
00788 
00789     if (UNIV_UNLIKELY
00790         (!page_zip_compress(new_page_zip, new_page, index, mtr))) {
00791       /* Before trying to reorganize the page,
00792       store the number of preceding records on the page. */
00793       ulint ret_pos
00794         = page_rec_get_n_recs_before(ret);
00795       /* Before copying, "ret" was the predecessor
00796       of the predefined supremum record.  If it was
00797       the predefined infimum record, then it would
00798       still be the infimum.  Thus, the assertion
00799       ut_a(ret_pos > 0) would fail here. */
00800 
00801       if (UNIV_UNLIKELY
00802           (!page_zip_reorganize(new_block, index, mtr))) {
00803 
00804         if (UNIV_UNLIKELY
00805             (!page_zip_decompress(new_page_zip,
00806                 new_page, FALSE))) {
00807           ut_error;
00808         }
00809         ut_ad(page_validate(new_page, index));
00810         return(NULL);
00811       } else {
00812         /* The page was reorganized:
00813         Seek to ret_pos. */
00814         ret = new_page + PAGE_NEW_INFIMUM;
00815 
00816         do {
00817           ret = rec_get_next_ptr(ret, TRUE);
00818         } while (--ret_pos);
00819       }
00820     }
00821   }
00822 
00823   /* Update the lock table and possible hash index */
00824 
00825   lock_move_rec_list_start(new_block, block, rec, ret);
00826 
00827   btr_search_move_or_delete_hash_entries(new_block, block, index);
00828 
00829   return(ret);
00830 }
00831 
00832 /**********************************************************/
00834 UNIV_INLINE
00835 void
00836 page_delete_rec_list_write_log(
00837 /*===========================*/
00838   rec_t*    rec,  
00839   dict_index_t* index,  
00840   byte    type, 
00842   mtr_t*    mtr)  
00843 {
00844   byte* log_ptr;
00845   ut_ad(type == MLOG_LIST_END_DELETE
00846         || type == MLOG_LIST_START_DELETE
00847         || type == MLOG_COMP_LIST_END_DELETE
00848         || type == MLOG_COMP_LIST_START_DELETE);
00849 
00850   log_ptr = mlog_open_and_write_index(mtr, rec, index, type, 2);
00851   if (log_ptr) {
00852     /* Write the parameter as a 2-byte ulint */
00853     mach_write_to_2(log_ptr, page_offset(rec));
00854     mlog_close(mtr, log_ptr + 2);
00855   }
00856 }
00857 #else /* !UNIV_HOTBACKUP */
00858 # define page_delete_rec_list_write_log(rec,index,type,mtr) ((void) 0)
00859 #endif /* !UNIV_HOTBACKUP */
00860 
00861 /**********************************************************/
00864 UNIV_INTERN
00865 byte*
00866 page_parse_delete_rec_list(
00867 /*=======================*/
00868   byte    type, 
00872   byte*   ptr,  
00873   byte*   end_ptr,
00874   buf_block_t*  block,  
00875   dict_index_t* index,  
00876   mtr_t*    mtr)  
00877 {
00878   page_t* page;
00879   ulint offset;
00880 
00881   ut_ad(type == MLOG_LIST_END_DELETE
00882         || type == MLOG_LIST_START_DELETE
00883         || type == MLOG_COMP_LIST_END_DELETE
00884         || type == MLOG_COMP_LIST_START_DELETE);
00885 
00886   /* Read the record offset as a 2-byte ulint */
00887 
00888   if (end_ptr < ptr + 2) {
00889 
00890     return(NULL);
00891   }
00892 
00893   offset = mach_read_from_2(ptr);
00894   ptr += 2;
00895 
00896   if (!block) {
00897 
00898     return(ptr);
00899   }
00900 
00901   page = buf_block_get_frame(block);
00902 
00903   ut_ad(!!page_is_comp(page) == dict_table_is_comp(index->table));
00904 
00905   if (type == MLOG_LIST_END_DELETE
00906       || type == MLOG_COMP_LIST_END_DELETE) {
00907     page_delete_rec_list_end(page + offset, block, index,
00908            ULINT_UNDEFINED, ULINT_UNDEFINED,
00909            mtr);
00910   } else {
00911     page_delete_rec_list_start(page + offset, block, index, mtr);
00912   }
00913 
00914   return(ptr);
00915 }
00916 
00917 /*************************************************************/
00920 UNIV_INTERN
00921 void
00922 page_delete_rec_list_end(
00923 /*=====================*/
00924   rec_t*    rec,  
00925   buf_block_t*  block,  
00926   dict_index_t* index,  
00927   ulint   n_recs, 
00929   ulint   size, 
00932   mtr_t*    mtr)  
00933 {
00934   page_dir_slot_t*slot;
00935   ulint   slot_index;
00936   rec_t*    last_rec;
00937   rec_t*    prev_rec;
00938   ulint   n_owned;
00939   page_zip_des_t* page_zip  = buf_block_get_page_zip(block);
00940   page_t*   page    = page_align(rec);
00941   mem_heap_t* heap    = NULL;
00942   ulint   offsets_[REC_OFFS_NORMAL_SIZE];
00943   ulint*    offsets   = offsets_;
00944   rec_offs_init(offsets_);
00945 
00946   ut_ad(size == ULINT_UNDEFINED || size < UNIV_PAGE_SIZE);
00947   ut_ad(!page_zip || page_rec_is_comp(rec));
00948 #ifdef UNIV_ZIP_DEBUG
00949   ut_a(!page_zip || page_zip_validate(page_zip, page));
00950 #endif /* UNIV_ZIP_DEBUG */
00951 
00952   if (page_rec_is_infimum(rec)) {
00953     rec = page_rec_get_next(rec);
00954   }
00955 
00956   if (page_rec_is_supremum(rec)) {
00957 
00958     return;
00959   }
00960 
00961   /* Reset the last insert info in the page header and increment
00962   the modify clock for the frame */
00963 
00964   page_header_set_ptr(page, page_zip, PAGE_LAST_INSERT, NULL);
00965 
00966   /* The page gets invalid for optimistic searches: increment the
00967   frame modify clock */
00968 
00969   buf_block_modify_clock_inc(block);
00970 
00971   page_delete_rec_list_write_log(rec, index, page_is_comp(page)
00972                ? MLOG_COMP_LIST_END_DELETE
00973                : MLOG_LIST_END_DELETE, mtr);
00974 
00975   if (UNIV_LIKELY_NULL(page_zip)) {
00976     ulint   log_mode;
00977 
00978     ut_a(page_is_comp(page));
00979     /* Individual deletes are not logged */
00980 
00981     log_mode = mtr_set_log_mode(mtr, MTR_LOG_NONE);
00982 
00983     do {
00984       page_cur_t  cur;
00985       page_cur_position(rec, block, &cur);
00986 
00987       offsets = rec_get_offsets(rec, index, offsets,
00988               ULINT_UNDEFINED, &heap);
00989       rec = rec_get_next_ptr(rec, TRUE);
00990 #ifdef UNIV_ZIP_DEBUG
00991       ut_a(page_zip_validate(page_zip, page));
00992 #endif /* UNIV_ZIP_DEBUG */
00993       page_cur_delete_rec(&cur, index, offsets, mtr);
00994     } while (page_offset(rec) != PAGE_NEW_SUPREMUM);
00995 
00996     if (UNIV_LIKELY_NULL(heap)) {
00997       mem_heap_free(heap);
00998     }
00999 
01000     /* Restore log mode */
01001 
01002     mtr_set_log_mode(mtr, log_mode);
01003     return;
01004   }
01005 
01006   prev_rec = page_rec_get_prev(rec);
01007 
01008   last_rec = page_rec_get_prev(page_get_supremum_rec(page));
01009 
01010   if ((size == ULINT_UNDEFINED) || (n_recs == ULINT_UNDEFINED)) {
01011     rec_t*    rec2    = rec;
01012     /* Calculate the sum of sizes and the number of records */
01013     size = 0;
01014     n_recs = 0;
01015 
01016     do {
01017       ulint s;
01018       offsets = rec_get_offsets(rec2, index, offsets,
01019               ULINT_UNDEFINED, &heap);
01020       s = rec_offs_size(offsets);
01021       ut_ad(rec2 - page + s - rec_offs_extra_size(offsets)
01022             < UNIV_PAGE_SIZE);
01023       ut_ad(size + s < UNIV_PAGE_SIZE);
01024       size += s;
01025       n_recs++;
01026 
01027       rec2 = page_rec_get_next(rec2);
01028     } while (!page_rec_is_supremum(rec2));
01029 
01030     if (UNIV_LIKELY_NULL(heap)) {
01031       mem_heap_free(heap);
01032     }
01033   }
01034 
01035   ut_ad(size < UNIV_PAGE_SIZE);
01036 
01037   /* Update the page directory; there is no need to balance the number
01038   of the records owned by the supremum record, as it is allowed to be
01039   less than PAGE_DIR_SLOT_MIN_N_OWNED */
01040 
01041   if (page_is_comp(page)) {
01042     rec_t*  rec2  = rec;
01043     ulint count = 0;
01044 
01045     while (rec_get_n_owned_new(rec2) == 0) {
01046       count++;
01047 
01048       rec2 = rec_get_next_ptr(rec2, TRUE);
01049     }
01050 
01051     ut_ad(rec_get_n_owned_new(rec2) > count);
01052 
01053     n_owned = rec_get_n_owned_new(rec2) - count;
01054     slot_index = page_dir_find_owner_slot(rec2);
01055     slot = page_dir_get_nth_slot(page, slot_index);
01056   } else {
01057     rec_t*  rec2  = rec;
01058     ulint count = 0;
01059 
01060     while (rec_get_n_owned_old(rec2) == 0) {
01061       count++;
01062 
01063       rec2 = rec_get_next_ptr(rec2, FALSE);
01064     }
01065 
01066     ut_ad(rec_get_n_owned_old(rec2) > count);
01067 
01068     n_owned = rec_get_n_owned_old(rec2) - count;
01069     slot_index = page_dir_find_owner_slot(rec2);
01070     slot = page_dir_get_nth_slot(page, slot_index);
01071   }
01072 
01073   page_dir_slot_set_rec(slot, page_get_supremum_rec(page));
01074   page_dir_slot_set_n_owned(slot, NULL, n_owned);
01075 
01076   page_dir_set_n_slots(page, NULL, slot_index + 1);
01077 
01078   /* Remove the record chain segment from the record chain */
01079   page_rec_set_next(prev_rec, page_get_supremum_rec(page));
01080 
01081   /* Catenate the deleted chain segment to the page free list */
01082 
01083   page_rec_set_next(last_rec, page_header_get_ptr(page, PAGE_FREE));
01084   page_header_set_ptr(page, NULL, PAGE_FREE, rec);
01085 
01086   page_header_set_field(page, NULL, PAGE_GARBAGE, size
01087             + page_header_get_field(page, PAGE_GARBAGE));
01088 
01089   page_header_set_field(page, NULL, PAGE_N_RECS,
01090             (ulint)(page_get_n_recs(page) - n_recs));
01091 }
01092 
01093 /*************************************************************/
01096 UNIV_INTERN
01097 void
01098 page_delete_rec_list_start(
01099 /*=======================*/
01100   rec_t*    rec,  
01101   buf_block_t*  block,  
01102   dict_index_t* index,  
01103   mtr_t*    mtr)  
01104 {
01105   page_cur_t  cur1;
01106   ulint   log_mode;
01107   ulint   offsets_[REC_OFFS_NORMAL_SIZE];
01108   ulint*    offsets   = offsets_;
01109   mem_heap_t* heap    = NULL;
01110   byte    type;
01111 
01112   rec_offs_init(offsets_);
01113 
01114   ut_ad((ibool) !!page_rec_is_comp(rec)
01115         == dict_table_is_comp(index->table));
01116 #ifdef UNIV_ZIP_DEBUG
01117   {
01118     page_zip_des_t* page_zip= buf_block_get_page_zip(block);
01119     page_t*   page  = buf_block_get_frame(block);
01120 
01121     /* page_zip_validate() would detect a min_rec_mark mismatch
01122     in btr_page_split_and_insert()
01123     between btr_attach_half_pages() and insert_page = ...
01124     when btr_page_get_split_rec_to_left() holds
01125     (direction == FSP_DOWN). */
01126     ut_a(!page_zip || page_zip_validate_low(page_zip, page, TRUE));
01127   }
01128 #endif /* UNIV_ZIP_DEBUG */
01129 
01130   if (page_rec_is_infimum(rec)) {
01131 
01132     return;
01133   }
01134 
01135   if (page_rec_is_comp(rec)) {
01136     type = MLOG_COMP_LIST_START_DELETE;
01137   } else {
01138     type = MLOG_LIST_START_DELETE;
01139   }
01140 
01141   page_delete_rec_list_write_log(rec, index, type, mtr);
01142 
01143   page_cur_set_before_first(block, &cur1);
01144   page_cur_move_to_next(&cur1);
01145 
01146   /* Individual deletes are not logged */
01147 
01148   log_mode = mtr_set_log_mode(mtr, MTR_LOG_NONE);
01149 
01150   while (page_cur_get_rec(&cur1) != rec) {
01151     offsets = rec_get_offsets(page_cur_get_rec(&cur1), index,
01152             offsets, ULINT_UNDEFINED, &heap);
01153     page_cur_delete_rec(&cur1, index, offsets, mtr);
01154   }
01155 
01156   if (UNIV_LIKELY_NULL(heap)) {
01157     mem_heap_free(heap);
01158   }
01159 
01160   /* Restore log mode */
01161 
01162   mtr_set_log_mode(mtr, log_mode);
01163 }
01164 
01165 #ifndef UNIV_HOTBACKUP
01166 /*************************************************************/
01171 UNIV_INTERN
01172 ibool
01173 page_move_rec_list_end(
01174 /*===================*/
01175   buf_block_t*  new_block,  
01176   buf_block_t*  block,    
01177   rec_t*    split_rec,  
01178   dict_index_t* index,    
01179   mtr_t*    mtr)    
01180 {
01181   page_t*   new_page  = buf_block_get_frame(new_block);
01182   ulint   old_data_size;
01183   ulint   new_data_size;
01184   ulint   old_n_recs;
01185   ulint   new_n_recs;
01186 
01187   old_data_size = page_get_data_size(new_page);
01188   old_n_recs = page_get_n_recs(new_page);
01189 #ifdef UNIV_ZIP_DEBUG
01190   {
01191     page_zip_des_t* new_page_zip
01192       = buf_block_get_page_zip(new_block);
01193     page_zip_des_t* page_zip
01194       = buf_block_get_page_zip(block);
01195     ut_a(!new_page_zip == !page_zip);
01196     ut_a(!new_page_zip
01197          || page_zip_validate(new_page_zip, new_page));
01198     ut_a(!page_zip
01199          || page_zip_validate(page_zip, page_align(split_rec)));
01200   }
01201 #endif /* UNIV_ZIP_DEBUG */
01202 
01203   if (UNIV_UNLIKELY(!page_copy_rec_list_end(new_block, block,
01204               split_rec, index, mtr))) {
01205     return(FALSE);
01206   }
01207 
01208   new_data_size = page_get_data_size(new_page);
01209   new_n_recs = page_get_n_recs(new_page);
01210 
01211   ut_ad(new_data_size >= old_data_size);
01212 
01213   page_delete_rec_list_end(split_rec, block, index,
01214          new_n_recs - old_n_recs,
01215          new_data_size - old_data_size, mtr);
01216 
01217   return(TRUE);
01218 }
01219 
01220 /*************************************************************/
01224 UNIV_INTERN
01225 ibool
01226 page_move_rec_list_start(
01227 /*=====================*/
01228   buf_block_t*  new_block,  
01229   buf_block_t*  block,    
01230   rec_t*    split_rec,  
01231   dict_index_t* index,    
01232   mtr_t*    mtr)    
01233 {
01234   if (UNIV_UNLIKELY(!page_copy_rec_list_start(new_block, block,
01235                 split_rec, index, mtr))) {
01236     return(FALSE);
01237   }
01238 
01239   page_delete_rec_list_start(split_rec, block, index, mtr);
01240 
01241   return(TRUE);
01242 }
01243 
01244 /***********************************************************************/
01247 UNIV_INTERN
01248 void
01249 page_rec_write_index_page_no(
01250 /*=========================*/
01251   rec_t*  rec,  
01252   ulint i,  
01253   ulint page_no,
01254   mtr_t*  mtr)  
01255 {
01256   byte* data;
01257   ulint len;
01258 
01259   data = rec_get_nth_field_old(rec, i, &len);
01260 
01261   ut_ad(len == 4);
01262 
01263   mlog_write_ulint(data, page_no, MLOG_4BYTES, mtr);
01264 }
01265 #endif /* !UNIV_HOTBACKUP */
01266 
01267 /**************************************************************/
01271 UNIV_INLINE
01272 void
01273 page_dir_delete_slot(
01274 /*=================*/
01275   page_t*   page, 
01276   page_zip_des_t* page_zip,
01277   ulint   slot_no)
01278 {
01279   page_dir_slot_t*  slot;
01280   ulint     n_owned;
01281   ulint     i;
01282   ulint     n_slots;
01283 
01284   ut_ad(!page_zip || page_is_comp(page));
01285   ut_ad(slot_no > 0);
01286   ut_ad(slot_no + 1 < page_dir_get_n_slots(page));
01287 
01288   n_slots = page_dir_get_n_slots(page);
01289 
01290   /* 1. Reset the n_owned fields of the slots to be
01291   deleted */
01292   slot = page_dir_get_nth_slot(page, slot_no);
01293   n_owned = page_dir_slot_get_n_owned(slot);
01294   page_dir_slot_set_n_owned(slot, page_zip, 0);
01295 
01296   /* 2. Update the n_owned value of the first non-deleted slot */
01297 
01298   slot = page_dir_get_nth_slot(page, slot_no + 1);
01299   page_dir_slot_set_n_owned(slot, page_zip,
01300           n_owned + page_dir_slot_get_n_owned(slot));
01301 
01302   /* 3. Destroy the slot by copying slots */
01303   for (i = slot_no + 1; i < n_slots; i++) {
01304     rec_t*  rec = (rec_t*)
01305       page_dir_slot_get_rec(page_dir_get_nth_slot(page, i));
01306     page_dir_slot_set_rec(page_dir_get_nth_slot(page, i - 1), rec);
01307   }
01308 
01309   /* 4. Zero out the last slot, which will be removed */
01310   mach_write_to_2(page_dir_get_nth_slot(page, n_slots - 1), 0);
01311 
01312   /* 5. Update the page header */
01313   page_header_set_field(page, page_zip, PAGE_N_DIR_SLOTS, n_slots - 1);
01314 }
01315 
01316 /**************************************************************/
01320 UNIV_INLINE
01321 void
01322 page_dir_add_slot(
01323 /*==============*/
01324   page_t*   page, 
01325   page_zip_des_t* page_zip,
01326   ulint   start)  
01328 {
01329   page_dir_slot_t*  slot;
01330   ulint     n_slots;
01331 
01332   n_slots = page_dir_get_n_slots(page);
01333 
01334   ut_ad(start < n_slots - 1);
01335 
01336   /* Update the page header */
01337   page_dir_set_n_slots(page, page_zip, n_slots + 1);
01338 
01339   /* Move slots up */
01340   slot = page_dir_get_nth_slot(page, n_slots);
01341   memmove(slot, slot + PAGE_DIR_SLOT_SIZE,
01342     (n_slots - 1 - start) * PAGE_DIR_SLOT_SIZE);
01343 }
01344 
01345 /****************************************************************/
01347 UNIV_INTERN
01348 void
01349 page_dir_split_slot(
01350 /*================*/
01351   page_t*   page, 
01352   page_zip_des_t* page_zip,
01354   ulint   slot_no)
01355 {
01356   rec_t*      rec;
01357   page_dir_slot_t*  new_slot;
01358   page_dir_slot_t*  prev_slot;
01359   page_dir_slot_t*  slot;
01360   ulint     i;
01361   ulint     n_owned;
01362 
01363   ut_ad(page);
01364   ut_ad(!page_zip || page_is_comp(page));
01365   ut_ad(slot_no > 0);
01366 
01367   slot = page_dir_get_nth_slot(page, slot_no);
01368 
01369   n_owned = page_dir_slot_get_n_owned(slot);
01370   ut_ad(n_owned == PAGE_DIR_SLOT_MAX_N_OWNED + 1);
01371 
01372   /* 1. We loop to find a record approximately in the middle of the
01373   records owned by the slot. */
01374 
01375   prev_slot = page_dir_get_nth_slot(page, slot_no - 1);
01376   rec = (rec_t*) page_dir_slot_get_rec(prev_slot);
01377 
01378   for (i = 0; i < n_owned / 2; i++) {
01379     rec = page_rec_get_next(rec);
01380   }
01381 
01382   ut_ad(n_owned / 2 >= PAGE_DIR_SLOT_MIN_N_OWNED);
01383 
01384   /* 2. We add one directory slot immediately below the slot to be
01385   split. */
01386 
01387   page_dir_add_slot(page, page_zip, slot_no - 1);
01388 
01389   /* The added slot is now number slot_no, and the old slot is
01390   now number slot_no + 1 */
01391 
01392   new_slot = page_dir_get_nth_slot(page, slot_no);
01393   slot = page_dir_get_nth_slot(page, slot_no + 1);
01394 
01395   /* 3. We store the appropriate values to the new slot. */
01396 
01397   page_dir_slot_set_rec(new_slot, rec);
01398   page_dir_slot_set_n_owned(new_slot, page_zip, n_owned / 2);
01399 
01400   /* 4. Finally, we update the number of records field of the
01401   original slot */
01402 
01403   page_dir_slot_set_n_owned(slot, page_zip, n_owned - (n_owned / 2));
01404 }
01405 
01406 /*************************************************************/
01410 UNIV_INTERN
01411 void
01412 page_dir_balance_slot(
01413 /*==================*/
01414   page_t*   page, 
01415   page_zip_des_t* page_zip,
01416   ulint   slot_no)
01417 {
01418   page_dir_slot_t*  slot;
01419   page_dir_slot_t*  up_slot;
01420   ulint     n_owned;
01421   ulint     up_n_owned;
01422   rec_t*      old_rec;
01423   rec_t*      new_rec;
01424 
01425   ut_ad(page);
01426   ut_ad(!page_zip || page_is_comp(page));
01427   ut_ad(slot_no > 0);
01428 
01429   slot = page_dir_get_nth_slot(page, slot_no);
01430 
01431   /* The last directory slot cannot be balanced with the upper
01432   neighbor, as there is none. */
01433 
01434   if (UNIV_UNLIKELY(slot_no == page_dir_get_n_slots(page) - 1)) {
01435 
01436     return;
01437   }
01438 
01439   up_slot = page_dir_get_nth_slot(page, slot_no + 1);
01440 
01441   n_owned = page_dir_slot_get_n_owned(slot);
01442   up_n_owned = page_dir_slot_get_n_owned(up_slot);
01443 
01444   ut_ad(n_owned == PAGE_DIR_SLOT_MIN_N_OWNED - 1);
01445 
01446   /* If the upper slot has the minimum value of n_owned, we will merge
01447   the two slots, therefore we assert: */
01448   ut_ad(2 * PAGE_DIR_SLOT_MIN_N_OWNED - 1 <= PAGE_DIR_SLOT_MAX_N_OWNED);
01449 
01450   if (up_n_owned > PAGE_DIR_SLOT_MIN_N_OWNED) {
01451 
01452     /* In this case we can just transfer one record owned
01453     by the upper slot to the property of the lower slot */
01454     old_rec = (rec_t*) page_dir_slot_get_rec(slot);
01455 
01456     if (page_is_comp(page)) {
01457       new_rec = rec_get_next_ptr(old_rec, TRUE);
01458 
01459       rec_set_n_owned_new(old_rec, page_zip, 0);
01460       rec_set_n_owned_new(new_rec, page_zip, n_owned + 1);
01461     } else {
01462       new_rec = rec_get_next_ptr(old_rec, FALSE);
01463 
01464       rec_set_n_owned_old(old_rec, 0);
01465       rec_set_n_owned_old(new_rec, n_owned + 1);
01466     }
01467 
01468     page_dir_slot_set_rec(slot, new_rec);
01469 
01470     page_dir_slot_set_n_owned(up_slot, page_zip, up_n_owned -1);
01471   } else {
01472     /* In this case we may merge the two slots */
01473     page_dir_delete_slot(page, page_zip, slot_no);
01474   }
01475 }
01476 
01477 #ifndef UNIV_HOTBACKUP
01478 /************************************************************/
01482 UNIV_INTERN
01483 rec_t*
01484 page_get_middle_rec(
01485 /*================*/
01486   page_t* page) 
01487 {
01488   page_dir_slot_t*  slot;
01489   ulint     middle;
01490   ulint     i;
01491   ulint     n_owned;
01492   ulint     count;
01493   rec_t*      rec;
01494 
01495   /* This many records we must leave behind */
01496   middle = (page_get_n_recs(page) + PAGE_HEAP_NO_USER_LOW) / 2;
01497 
01498   count = 0;
01499 
01500   for (i = 0;; i++) {
01501 
01502     slot = page_dir_get_nth_slot(page, i);
01503     n_owned = page_dir_slot_get_n_owned(slot);
01504 
01505     if (count + n_owned > middle) {
01506       break;
01507     } else {
01508       count += n_owned;
01509     }
01510   }
01511 
01512   ut_ad(i > 0);
01513   slot = page_dir_get_nth_slot(page, i - 1);
01514   rec = (rec_t*) page_dir_slot_get_rec(slot);
01515   rec = page_rec_get_next(rec);
01516 
01517   /* There are now count records behind rec */
01518 
01519   for (i = 0; i < middle - count; i++) {
01520     rec = page_rec_get_next(rec);
01521   }
01522 
01523   return(rec);
01524 }
01525 #endif /* !UNIV_HOTBACKUP */
01526 
01527 /***************************************************************/
01531 UNIV_INTERN
01532 ulint
01533 page_rec_get_n_recs_before(
01534 /*=======================*/
01535   const rec_t*  rec)  
01536 {
01537   const page_dir_slot_t*  slot;
01538   const rec_t*    slot_rec;
01539   const page_t*   page;
01540   ulint     i;
01541   lint      n = 0;
01542 
01543   ut_ad(page_rec_check(rec));
01544 
01545   page = page_align(rec);
01546   if (page_is_comp(page)) {
01547     while (rec_get_n_owned_new(rec) == 0) {
01548 
01549       rec = rec_get_next_ptr_const(rec, TRUE);
01550       n--;
01551     }
01552 
01553     for (i = 0; ; i++) {
01554       slot = page_dir_get_nth_slot(page, i);
01555       slot_rec = page_dir_slot_get_rec(slot);
01556 
01557       n += rec_get_n_owned_new(slot_rec);
01558 
01559       if (rec == slot_rec) {
01560 
01561         break;
01562       }
01563     }
01564   } else {
01565     while (rec_get_n_owned_old(rec) == 0) {
01566 
01567       rec = rec_get_next_ptr_const(rec, FALSE);
01568       n--;
01569     }
01570 
01571     for (i = 0; ; i++) {
01572       slot = page_dir_get_nth_slot(page, i);
01573       slot_rec = page_dir_slot_get_rec(slot);
01574 
01575       n += rec_get_n_owned_old(slot_rec);
01576 
01577       if (rec == slot_rec) {
01578 
01579         break;
01580       }
01581     }
01582   }
01583 
01584   n--;
01585 
01586   ut_ad(n >= 0);
01587 
01588   return((ulint) n);
01589 }
01590 
01591 #ifndef UNIV_HOTBACKUP
01592 /************************************************************/
01595 UNIV_INTERN
01596 void
01597 page_rec_print(
01598 /*===========*/
01599   const rec_t*  rec,  
01600   const ulint*  offsets)
01601 {
01602   ut_a(!page_rec_is_comp(rec) == !rec_offs_comp(offsets));
01603   rec_print_new(stderr, rec, offsets);
01604   if (page_rec_is_comp(rec)) {
01605     fprintf(stderr,
01606       " n_owned: %lu; heap_no: %lu; next rec: %lu\n",
01607       (ulong) rec_get_n_owned_new(rec),
01608       (ulong) rec_get_heap_no_new(rec),
01609       (ulong) rec_get_next_offs(rec, TRUE));
01610   } else {
01611     fprintf(stderr,
01612       " n_owned: %lu; heap_no: %lu; next rec: %lu\n",
01613       (ulong) rec_get_n_owned_old(rec),
01614       (ulong) rec_get_heap_no_old(rec),
01615       (ulong) rec_get_next_offs(rec, TRUE));
01616   }
01617 
01618   page_rec_check(rec);
01619   rec_validate(rec, offsets);
01620 }
01621 
01622 /***************************************************************/
01625 UNIV_INTERN
01626 void
01627 page_dir_print(
01628 /*===========*/
01629   page_t* page, 
01630   ulint pr_n) 
01631 {
01632   ulint     n;
01633   ulint     i;
01634   page_dir_slot_t*  slot;
01635 
01636   n = page_dir_get_n_slots(page);
01637 
01638   fprintf(stderr, "--------------------------------\n"
01639     "PAGE DIRECTORY\n"
01640     "Page address %p\n"
01641     "Directory stack top at offs: %lu; number of slots: %lu\n",
01642     page, (ulong) page_offset(page_dir_get_nth_slot(page, n - 1)),
01643     (ulong) n);
01644   for (i = 0; i < n; i++) {
01645     slot = page_dir_get_nth_slot(page, i);
01646     if ((i == pr_n) && (i < n - pr_n)) {
01647       fputs("    ...   \n", stderr);
01648     }
01649     if ((i < pr_n) || (i >= n - pr_n)) {
01650       fprintf(stderr,
01651         "Contents of slot: %lu: n_owned: %lu,"
01652         " rec offs: %lu\n",
01653         (ulong) i,
01654         (ulong) page_dir_slot_get_n_owned(slot),
01655         (ulong)
01656         page_offset(page_dir_slot_get_rec(slot)));
01657     }
01658   }
01659   fprintf(stderr, "Total of %lu records\n"
01660     "--------------------------------\n",
01661     (ulong) (PAGE_HEAP_NO_USER_LOW + page_get_n_recs(page)));
01662 }
01663 
01664 /***************************************************************/
01667 UNIV_INTERN
01668 void
01669 page_print_list(
01670 /*============*/
01671   buf_block_t*  block,  
01672   dict_index_t* index,  
01673   ulint   pr_n) 
01674 {
01675   page_t*   page    = block->frame;
01676   page_cur_t  cur;
01677   ulint   count;
01678   ulint   n_recs;
01679   mem_heap_t* heap    = NULL;
01680   ulint   offsets_[REC_OFFS_NORMAL_SIZE];
01681   ulint*    offsets   = offsets_;
01682   rec_offs_init(offsets_);
01683 
01684   ut_a((ibool)!!page_is_comp(page) == dict_table_is_comp(index->table));
01685 
01686   fprintf(stderr,
01687     "--------------------------------\n"
01688     "PAGE RECORD LIST\n"
01689     "Page address %p\n", page);
01690 
01691   n_recs = page_get_n_recs(page);
01692 
01693   page_cur_set_before_first(block, &cur);
01694   count = 0;
01695   for (;;) {
01696     offsets = rec_get_offsets(cur.rec, index, offsets,
01697             ULINT_UNDEFINED, &heap);
01698     page_rec_print(cur.rec, offsets);
01699 
01700     if (count == pr_n) {
01701       break;
01702     }
01703     if (page_cur_is_after_last(&cur)) {
01704       break;
01705     }
01706     page_cur_move_to_next(&cur);
01707     count++;
01708   }
01709 
01710   if (n_recs > 2 * pr_n) {
01711     fputs(" ... \n", stderr);
01712   }
01713 
01714   while (!page_cur_is_after_last(&cur)) {
01715     page_cur_move_to_next(&cur);
01716 
01717     if (count + pr_n >= n_recs) {
01718       offsets = rec_get_offsets(cur.rec, index, offsets,
01719               ULINT_UNDEFINED, &heap);
01720       page_rec_print(cur.rec, offsets);
01721     }
01722     count++;
01723   }
01724 
01725   fprintf(stderr,
01726     "Total of %lu records \n"
01727     "--------------------------------\n",
01728     (ulong) (count + 1));
01729 
01730   if (UNIV_LIKELY_NULL(heap)) {
01731     mem_heap_free(heap);
01732   }
01733 }
01734 
01735 /***************************************************************/
01737 UNIV_INTERN
01738 void
01739 page_header_print(
01740 /*==============*/
01741   const page_t* page)
01742 {
01743   fprintf(stderr,
01744     "--------------------------------\n"
01745     "PAGE HEADER INFO\n"
01746     "Page address %p, n records %lu (%s)\n"
01747     "n dir slots %lu, heap top %lu\n"
01748     "Page n heap %lu, free %lu, garbage %lu\n"
01749     "Page last insert %lu, direction %lu, n direction %lu\n",
01750     page, (ulong) page_header_get_field(page, PAGE_N_RECS),
01751     page_is_comp(page) ? "compact format" : "original format",
01752     (ulong) page_header_get_field(page, PAGE_N_DIR_SLOTS),
01753     (ulong) page_header_get_field(page, PAGE_HEAP_TOP),
01754     (ulong) page_dir_get_n_heap(page),
01755     (ulong) page_header_get_field(page, PAGE_FREE),
01756     (ulong) page_header_get_field(page, PAGE_GARBAGE),
01757     (ulong) page_header_get_field(page, PAGE_LAST_INSERT),
01758     (ulong) page_header_get_field(page, PAGE_DIRECTION),
01759     (ulong) page_header_get_field(page, PAGE_N_DIRECTION));
01760 }
01761 
01762 /***************************************************************/
01765 UNIV_INTERN
01766 void
01767 page_print(
01768 /*=======*/
01769   buf_block_t*  block,  
01770   dict_index_t* index,  
01771   ulint   dn, 
01773   ulint   rn) 
01775 {
01776   page_t* page = block->frame;
01777 
01778   page_header_print(page);
01779   page_dir_print(page, dn);
01780   page_print_list(block, index, rn);
01781 }
01782 #endif /* !UNIV_HOTBACKUP */
01783 
01784 /***************************************************************/
01789 UNIV_INTERN
01790 ibool
01791 page_rec_validate(
01792 /*==============*/
01793   rec_t*    rec,  
01794   const ulint*  offsets)
01795 {
01796   ulint n_owned;
01797   ulint heap_no;
01798   page_t* page;
01799 
01800   page = page_align(rec);
01801   ut_a(!page_is_comp(page) == !rec_offs_comp(offsets));
01802 
01803   page_rec_check(rec);
01804   rec_validate(rec, offsets);
01805 
01806   if (page_rec_is_comp(rec)) {
01807     n_owned = rec_get_n_owned_new(rec);
01808     heap_no = rec_get_heap_no_new(rec);
01809   } else {
01810     n_owned = rec_get_n_owned_old(rec);
01811     heap_no = rec_get_heap_no_old(rec);
01812   }
01813 
01814   if (UNIV_UNLIKELY(!(n_owned <= PAGE_DIR_SLOT_MAX_N_OWNED))) {
01815     fprintf(stderr,
01816       "InnoDB: Dir slot of rec %lu, n owned too big %lu\n",
01817       (ulong) page_offset(rec), (ulong) n_owned);
01818     return(FALSE);
01819   }
01820 
01821   if (UNIV_UNLIKELY(!(heap_no < page_dir_get_n_heap(page)))) {
01822     fprintf(stderr,
01823       "InnoDB: Heap no of rec %lu too big %lu %lu\n",
01824       (ulong) page_offset(rec), (ulong) heap_no,
01825       (ulong) page_dir_get_n_heap(page));
01826     return(FALSE);
01827   }
01828 
01829   return(TRUE);
01830 }
01831 
01832 #ifndef UNIV_HOTBACKUP
01833 /***************************************************************/
01837 UNIV_INTERN
01838 void
01839 page_check_dir(
01840 /*===========*/
01841   const page_t* page) 
01842 {
01843   ulint n_slots;
01844   ulint infimum_offs;
01845   ulint supremum_offs;
01846 
01847   n_slots = page_dir_get_n_slots(page);
01848   infimum_offs = mach_read_from_2(page_dir_get_nth_slot(page, 0));
01849   supremum_offs = mach_read_from_2(page_dir_get_nth_slot(page,
01850                      n_slots - 1));
01851 
01852   if (UNIV_UNLIKELY(!page_rec_is_infimum_low(infimum_offs))) {
01853 
01854     fprintf(stderr,
01855       "InnoDB: Page directory corruption:"
01856       " infimum not pointed to\n");
01857     buf_page_print(page, 0);
01858   }
01859 
01860   if (UNIV_UNLIKELY(!page_rec_is_supremum_low(supremum_offs))) {
01861 
01862     fprintf(stderr,
01863       "InnoDB: Page directory corruption:"
01864       " supremum not pointed to\n");
01865     buf_page_print(page, 0);
01866   }
01867 }
01868 #endif /* !UNIV_HOTBACKUP */
01869 
01870 /***************************************************************/
01875 UNIV_INTERN
01876 ibool
01877 page_simple_validate_old(
01878 /*=====================*/
01879   page_t* page) 
01880 {
01881   page_dir_slot_t* slot;
01882   ulint   slot_no;
01883   ulint   n_slots;
01884   rec_t*    rec;
01885   byte*   rec_heap_top;
01886   ulint   count;
01887   ulint   own_count;
01888   ibool   ret = FALSE;
01889 
01890   ut_a(!page_is_comp(page));
01891 
01892   /* Check first that the record heap and the directory do not
01893   overlap. */
01894 
01895   n_slots = page_dir_get_n_slots(page);
01896 
01897   if (UNIV_UNLIKELY(n_slots > UNIV_PAGE_SIZE / 4)) {
01898     fprintf(stderr,
01899       "InnoDB: Nonsensical number %lu of page dir slots\n",
01900       (ulong) n_slots);
01901 
01902     goto func_exit;
01903   }
01904 
01905   rec_heap_top = page_header_get_ptr(page, PAGE_HEAP_TOP);
01906 
01907   if (UNIV_UNLIKELY(rec_heap_top
01908         > page_dir_get_nth_slot(page, n_slots - 1))) {
01909 
01910     fprintf(stderr,
01911       "InnoDB: Record heap and dir overlap on a page,"
01912       " heap top %lu, dir %lu\n",
01913       (ulong) page_header_get_field(page, PAGE_HEAP_TOP),
01914       (ulong)
01915       page_offset(page_dir_get_nth_slot(page, n_slots - 1)));
01916 
01917     goto func_exit;
01918   }
01919 
01920   /* Validate the record list in a loop checking also that it is
01921   consistent with the page record directory. */
01922 
01923   count = 0;
01924   own_count = 1;
01925   slot_no = 0;
01926   slot = page_dir_get_nth_slot(page, slot_no);
01927 
01928   rec = page_get_infimum_rec(page);
01929 
01930   for (;;) {
01931     if (UNIV_UNLIKELY(rec > rec_heap_top)) {
01932       fprintf(stderr,
01933         "InnoDB: Record %lu is above"
01934         " rec heap top %lu\n",
01935         (ulong)(rec - page),
01936         (ulong)(rec_heap_top - page));
01937 
01938       goto func_exit;
01939     }
01940 
01941     if (UNIV_UNLIKELY(rec_get_n_owned_old(rec))) {
01942       /* This is a record pointed to by a dir slot */
01943       if (UNIV_UNLIKELY(rec_get_n_owned_old(rec)
01944             != own_count)) {
01945 
01946         fprintf(stderr,
01947           "InnoDB: Wrong owned count %lu, %lu,"
01948           " rec %lu\n",
01949           (ulong) rec_get_n_owned_old(rec),
01950           (ulong) own_count,
01951           (ulong)(rec - page));
01952 
01953         goto func_exit;
01954       }
01955 
01956       if (UNIV_UNLIKELY
01957           (page_dir_slot_get_rec(slot) != rec)) {
01958         fprintf(stderr,
01959           "InnoDB: Dir slot does not point"
01960           " to right rec %lu\n",
01961           (ulong)(rec - page));
01962 
01963         goto func_exit;
01964       }
01965 
01966       own_count = 0;
01967 
01968       if (!page_rec_is_supremum(rec)) {
01969         slot_no++;
01970         slot = page_dir_get_nth_slot(page, slot_no);
01971       }
01972     }
01973 
01974     if (page_rec_is_supremum(rec)) {
01975 
01976       break;
01977     }
01978 
01979     if (UNIV_UNLIKELY
01980         (rec_get_next_offs(rec, FALSE) < FIL_PAGE_DATA
01981          || rec_get_next_offs(rec, FALSE) >= UNIV_PAGE_SIZE)) {
01982       fprintf(stderr,
01983         "InnoDB: Next record offset"
01984         " nonsensical %lu for rec %lu\n",
01985         (ulong) rec_get_next_offs(rec, FALSE),
01986         (ulong) (rec - page));
01987 
01988       goto func_exit;
01989     }
01990 
01991     count++;
01992 
01993     if (UNIV_UNLIKELY(count > UNIV_PAGE_SIZE)) {
01994       fprintf(stderr,
01995         "InnoDB: Page record list appears"
01996         " to be circular %lu\n",
01997         (ulong) count);
01998       goto func_exit;
01999     }
02000 
02001     rec = page_rec_get_next(rec);
02002     own_count++;
02003   }
02004 
02005   if (UNIV_UNLIKELY(rec_get_n_owned_old(rec) == 0)) {
02006     fprintf(stderr, "InnoDB: n owned is zero in a supremum rec\n");
02007 
02008     goto func_exit;
02009   }
02010 
02011   if (UNIV_UNLIKELY(slot_no != n_slots - 1)) {
02012     fprintf(stderr, "InnoDB: n slots wrong %lu, %lu\n",
02013       (ulong) slot_no, (ulong) (n_slots - 1));
02014     goto func_exit;
02015   }
02016 
02017   if (UNIV_UNLIKELY(page_header_get_field(page, PAGE_N_RECS)
02018         + PAGE_HEAP_NO_USER_LOW
02019         != count + 1)) {
02020     fprintf(stderr, "InnoDB: n recs wrong %lu %lu\n",
02021       (ulong) page_header_get_field(page, PAGE_N_RECS)
02022       + PAGE_HEAP_NO_USER_LOW,
02023       (ulong) (count + 1));
02024 
02025     goto func_exit;
02026   }
02027 
02028   /* Check then the free list */
02029   rec = page_header_get_ptr(page, PAGE_FREE);
02030 
02031   while (rec != NULL) {
02032     if (UNIV_UNLIKELY(rec < page + FIL_PAGE_DATA
02033           || rec >= page + UNIV_PAGE_SIZE)) {
02034       fprintf(stderr,
02035         "InnoDB: Free list record has"
02036         " a nonsensical offset %lu\n",
02037         (ulong) (rec - page));
02038 
02039       goto func_exit;
02040     }
02041 
02042     if (UNIV_UNLIKELY(rec > rec_heap_top)) {
02043       fprintf(stderr,
02044         "InnoDB: Free list record %lu"
02045         " is above rec heap top %lu\n",
02046         (ulong) (rec - page),
02047         (ulong) (rec_heap_top - page));
02048 
02049       goto func_exit;
02050     }
02051 
02052     count++;
02053 
02054     if (UNIV_UNLIKELY(count > UNIV_PAGE_SIZE)) {
02055       fprintf(stderr,
02056         "InnoDB: Page free list appears"
02057         " to be circular %lu\n",
02058         (ulong) count);
02059       goto func_exit;
02060     }
02061 
02062     rec = page_rec_get_next(rec);
02063   }
02064 
02065   if (UNIV_UNLIKELY(page_dir_get_n_heap(page) != count + 1)) {
02066 
02067     fprintf(stderr, "InnoDB: N heap is wrong %lu, %lu\n",
02068       (ulong) page_dir_get_n_heap(page),
02069       (ulong) (count + 1));
02070 
02071     goto func_exit;
02072   }
02073 
02074   ret = TRUE;
02075 
02076 func_exit:
02077   return(ret);
02078 }
02079 
02080 /***************************************************************/
02085 UNIV_INTERN
02086 ibool
02087 page_simple_validate_new(
02088 /*=====================*/
02089   page_t* page) 
02090 {
02091   page_dir_slot_t* slot;
02092   ulint   slot_no;
02093   ulint   n_slots;
02094   rec_t*    rec;
02095   byte*   rec_heap_top;
02096   ulint   count;
02097   ulint   own_count;
02098   ibool   ret = FALSE;
02099 
02100   ut_a(page_is_comp(page));
02101 
02102   /* Check first that the record heap and the directory do not
02103   overlap. */
02104 
02105   n_slots = page_dir_get_n_slots(page);
02106 
02107   if (UNIV_UNLIKELY(n_slots > UNIV_PAGE_SIZE / 4)) {
02108     fprintf(stderr,
02109       "InnoDB: Nonsensical number %lu"
02110       " of page dir slots\n", (ulong) n_slots);
02111 
02112     goto func_exit;
02113   }
02114 
02115   rec_heap_top = page_header_get_ptr(page, PAGE_HEAP_TOP);
02116 
02117   if (UNIV_UNLIKELY(rec_heap_top
02118         > page_dir_get_nth_slot(page, n_slots - 1))) {
02119 
02120     fprintf(stderr,
02121       "InnoDB: Record heap and dir overlap on a page,"
02122       " heap top %lu, dir %lu\n",
02123       (ulong) page_header_get_field(page, PAGE_HEAP_TOP),
02124       (ulong)
02125       page_offset(page_dir_get_nth_slot(page, n_slots - 1)));
02126 
02127     goto func_exit;
02128   }
02129 
02130   /* Validate the record list in a loop checking also that it is
02131   consistent with the page record directory. */
02132 
02133   count = 0;
02134   own_count = 1;
02135   slot_no = 0;
02136   slot = page_dir_get_nth_slot(page, slot_no);
02137 
02138   rec = page_get_infimum_rec(page);
02139 
02140   for (;;) {
02141     if (UNIV_UNLIKELY(rec > rec_heap_top)) {
02142       fprintf(stderr,
02143         "InnoDB: Record %lu is above rec"
02144         " heap top %lu\n",
02145         (ulong) page_offset(rec),
02146         (ulong) page_offset(rec_heap_top));
02147 
02148       goto func_exit;
02149     }
02150 
02151     if (UNIV_UNLIKELY(rec_get_n_owned_new(rec))) {
02152       /* This is a record pointed to by a dir slot */
02153       if (UNIV_UNLIKELY(rec_get_n_owned_new(rec)
02154             != own_count)) {
02155 
02156         fprintf(stderr,
02157           "InnoDB: Wrong owned count %lu, %lu,"
02158           " rec %lu\n",
02159           (ulong) rec_get_n_owned_new(rec),
02160           (ulong) own_count,
02161           (ulong) page_offset(rec));
02162 
02163         goto func_exit;
02164       }
02165 
02166       if (UNIV_UNLIKELY
02167           (page_dir_slot_get_rec(slot) != rec)) {
02168         fprintf(stderr,
02169           "InnoDB: Dir slot does not point"
02170           " to right rec %lu\n",
02171           (ulong) page_offset(rec));
02172 
02173         goto func_exit;
02174       }
02175 
02176       own_count = 0;
02177 
02178       if (!page_rec_is_supremum(rec)) {
02179         slot_no++;
02180         slot = page_dir_get_nth_slot(page, slot_no);
02181       }
02182     }
02183 
02184     if (page_rec_is_supremum(rec)) {
02185 
02186       break;
02187     }
02188 
02189     if (UNIV_UNLIKELY
02190         (rec_get_next_offs(rec, TRUE) < FIL_PAGE_DATA
02191          || rec_get_next_offs(rec, TRUE) >= UNIV_PAGE_SIZE)) {
02192       fprintf(stderr,
02193         "InnoDB: Next record offset nonsensical %lu"
02194         " for rec %lu\n",
02195         (ulong) rec_get_next_offs(rec, TRUE),
02196         (ulong) page_offset(rec));
02197 
02198       goto func_exit;
02199     }
02200 
02201     count++;
02202 
02203     if (UNIV_UNLIKELY(count > UNIV_PAGE_SIZE)) {
02204       fprintf(stderr,
02205         "InnoDB: Page record list appears"
02206         " to be circular %lu\n",
02207         (ulong) count);
02208       goto func_exit;
02209     }
02210 
02211     rec = page_rec_get_next(rec);
02212     own_count++;
02213   }
02214 
02215   if (UNIV_UNLIKELY(rec_get_n_owned_new(rec) == 0)) {
02216     fprintf(stderr, "InnoDB: n owned is zero"
02217       " in a supremum rec\n");
02218 
02219     goto func_exit;
02220   }
02221 
02222   if (UNIV_UNLIKELY(slot_no != n_slots - 1)) {
02223     fprintf(stderr, "InnoDB: n slots wrong %lu, %lu\n",
02224       (ulong) slot_no, (ulong) (n_slots - 1));
02225     goto func_exit;
02226   }
02227 
02228   if (UNIV_UNLIKELY(page_header_get_field(page, PAGE_N_RECS)
02229         + PAGE_HEAP_NO_USER_LOW
02230         != count + 1)) {
02231     fprintf(stderr, "InnoDB: n recs wrong %lu %lu\n",
02232       (ulong) page_header_get_field(page, PAGE_N_RECS)
02233       + PAGE_HEAP_NO_USER_LOW,
02234       (ulong) (count + 1));
02235 
02236     goto func_exit;
02237   }
02238 
02239   /* Check then the free list */
02240   rec = page_header_get_ptr(page, PAGE_FREE);
02241 
02242   while (rec != NULL) {
02243     if (UNIV_UNLIKELY(rec < page + FIL_PAGE_DATA
02244           || rec >= page + UNIV_PAGE_SIZE)) {
02245       fprintf(stderr,
02246         "InnoDB: Free list record has"
02247         " a nonsensical offset %lu\n",
02248         (ulong) page_offset(rec));
02249 
02250       goto func_exit;
02251     }
02252 
02253     if (UNIV_UNLIKELY(rec > rec_heap_top)) {
02254       fprintf(stderr,
02255         "InnoDB: Free list record %lu"
02256         " is above rec heap top %lu\n",
02257         (ulong) page_offset(rec),
02258         (ulong) page_offset(rec_heap_top));
02259 
02260       goto func_exit;
02261     }
02262 
02263     count++;
02264 
02265     if (UNIV_UNLIKELY(count > UNIV_PAGE_SIZE)) {
02266       fprintf(stderr,
02267         "InnoDB: Page free list appears"
02268         " to be circular %lu\n",
02269         (ulong) count);
02270       goto func_exit;
02271     }
02272 
02273     rec = page_rec_get_next(rec);
02274   }
02275 
02276   if (UNIV_UNLIKELY(page_dir_get_n_heap(page) != count + 1)) {
02277 
02278     fprintf(stderr, "InnoDB: N heap is wrong %lu, %lu\n",
02279       (ulong) page_dir_get_n_heap(page),
02280       (ulong) (count + 1));
02281 
02282     goto func_exit;
02283   }
02284 
02285   ret = TRUE;
02286 
02287 func_exit:
02288   return(ret);
02289 }
02290 
02291 /***************************************************************/
02294 UNIV_INTERN
02295 ibool
02296 page_validate(
02297 /*==========*/
02298   page_t*   page, 
02299   dict_index_t* index)  
02301 {
02302   page_dir_slot_t*slot= NULL;
02303   mem_heap_t* heap= NULL;
02304   byte*   buf= NULL;
02305   ulint   count= 0;
02306   ulint   own_count= 0;
02307   ulint   rec_own_count= 0;
02308   ulint   slot_no= 0;
02309   ulint   data_size= 0;
02310   rec_t*    rec= NULL;
02311   rec_t*    old_rec   = NULL;
02312   ulint   offs= 0;
02313   ulint   n_slots= 0;
02314   ibool   ret   = FALSE;
02315   ulint   i= 0;
02316   ulint*    offsets   = NULL;
02317   ulint*    old_offsets = NULL;
02318         void* buf_ptr= NULL;
02319 
02320   if (UNIV_UNLIKELY((ibool) !!page_is_comp(page)
02321         != dict_table_is_comp(index->table))) {
02322     fputs("InnoDB: 'compact format' flag mismatch\n", stderr);
02323     goto func_exit2;
02324   }
02325   if (page_is_comp(page)) {
02326     if (UNIV_UNLIKELY(!page_simple_validate_new(page))) {
02327       goto func_exit2;
02328     }
02329   } else {
02330     if (UNIV_UNLIKELY(!page_simple_validate_old(page))) {
02331       goto func_exit2;
02332     }
02333   }
02334 
02335   heap = mem_heap_create(UNIV_PAGE_SIZE + 200);
02336 
02337   /* The following buffer is used to check that the
02338   records in the page record heap do not overlap */
02339 
02340         buf_ptr= mem_heap_zalloc(heap, UNIV_PAGE_SIZE);
02341   buf = static_cast<byte *>(buf_ptr);
02342 
02343   /* Check first that the record heap and the directory do not
02344   overlap. */
02345 
02346   n_slots = page_dir_get_n_slots(page);
02347 
02348   if (UNIV_UNLIKELY(!(page_header_get_ptr(page, PAGE_HEAP_TOP)
02349           <= page_dir_get_nth_slot(page, n_slots - 1)))) {
02350 
02351     fprintf(stderr, 
02352       "InnoDB: Record heap and dir overlap"
02353       " on space %lu page %lu index %s, %p, %p\n",
02354       (ulong) page_get_space_id(page),
02355       (ulong) page_get_page_no(page), index->name,
02356       page_header_get_ptr(page, PAGE_HEAP_TOP),
02357       page_dir_get_nth_slot(page, n_slots - 1));
02358 
02359     goto func_exit;
02360   }
02361 
02362   /* Validate the record list in a loop checking also that
02363   it is consistent with the directory. */
02364   count = 0;
02365   data_size = 0;
02366   own_count = 1;
02367   slot_no = 0;
02368   slot = page_dir_get_nth_slot(page, slot_no);
02369 
02370   rec = page_get_infimum_rec(page);
02371 
02372   for (;;) {
02373     offsets = rec_get_offsets(rec, index, offsets,
02374             ULINT_UNDEFINED, &heap);
02375 
02376     if (page_is_comp(page) && page_rec_is_user_rec(rec)
02377         && UNIV_UNLIKELY(rec_get_node_ptr_flag(rec)
02378              == page_is_leaf(page))) {
02379       fputs("InnoDB: node_ptr flag mismatch\n", stderr);
02380       goto func_exit;
02381     }
02382 
02383     if (UNIV_UNLIKELY(!page_rec_validate(rec, offsets))) {
02384       goto func_exit;
02385     }
02386 
02387 #ifndef UNIV_HOTBACKUP
02388     /* Check that the records are in the ascending order */
02389     if (UNIV_LIKELY(count >= PAGE_HEAP_NO_USER_LOW)
02390         && !page_rec_is_supremum(rec)) {
02391       if (UNIV_UNLIKELY
02392           (1 != cmp_rec_rec(rec, old_rec,
02393                 offsets, old_offsets, index))) {
02394         fprintf(stderr, 
02395           "InnoDB: Records in wrong order"
02396           " on space %lu page %lu index %s\n",
02397           (ulong) page_get_space_id(page),
02398           (ulong) page_get_page_no(page),
02399           index->name);
02400         fputs("\nInnoDB: previous record ", stderr);
02401         rec_print_new(stderr, old_rec, old_offsets);
02402         fputs("\nInnoDB: record ", stderr);
02403         rec_print_new(stderr, rec, offsets);
02404         putc('\n', stderr);
02405 
02406         goto func_exit;
02407       }
02408     }
02409 #endif /* !UNIV_HOTBACKUP */
02410 
02411     if (page_rec_is_user_rec(rec)) {
02412 
02413       data_size += rec_offs_size(offsets);
02414     }
02415 
02416     offs = page_offset(rec_get_start(rec, offsets));
02417     i = rec_offs_size(offsets);
02418     if (UNIV_UNLIKELY(offs + i >= UNIV_PAGE_SIZE)) {
02419       fputs("InnoDB: record offset out of bounds\n", stderr);
02420       goto func_exit;
02421     }
02422 
02423     while (i--) {
02424       if (UNIV_UNLIKELY(buf[offs + i])) {
02425         /* No other record may overlap this */
02426 
02427         fputs("InnoDB: Record overlaps another\n",
02428               stderr);
02429         goto func_exit;
02430       }
02431 
02432       buf[offs + i] = 1;
02433     }
02434 
02435     if (page_is_comp(page)) {
02436       rec_own_count = rec_get_n_owned_new(rec);
02437     } else {
02438       rec_own_count = rec_get_n_owned_old(rec);
02439     }
02440 
02441     if (UNIV_UNLIKELY(rec_own_count)) {
02442       /* This is a record pointed to by a dir slot */
02443       if (UNIV_UNLIKELY(rec_own_count != own_count)) {
02444         fprintf(stderr,
02445           "InnoDB: Wrong owned count %lu, %lu\n",
02446           (ulong) rec_own_count,
02447           (ulong) own_count);
02448         goto func_exit;
02449       }
02450 
02451       if (page_dir_slot_get_rec(slot) != rec) {
02452         fputs("InnoDB: Dir slot does not"
02453               " point to right rec\n",
02454               stderr);
02455         goto func_exit;
02456       }
02457 
02458       page_dir_slot_check(slot);
02459 
02460       own_count = 0;
02461       if (!page_rec_is_supremum(rec)) {
02462         slot_no++;
02463         slot = page_dir_get_nth_slot(page, slot_no);
02464       }
02465     }
02466 
02467     if (page_rec_is_supremum(rec)) {
02468       break;
02469     }
02470 
02471     count++;
02472     own_count++;
02473     old_rec = rec;
02474     rec = page_rec_get_next(rec);
02475 
02476     /* set old_offsets to offsets; recycle offsets */
02477     {
02478       ulint* tmp_offs = old_offsets;
02479       old_offsets = offsets;
02480       offsets = tmp_offs;
02481     }
02482   }
02483 
02484   if (page_is_comp(page)) {
02485     if (UNIV_UNLIKELY(rec_get_n_owned_new(rec) == 0)) {
02486 
02487       goto n_owned_zero;
02488     }
02489   } else if (UNIV_UNLIKELY(rec_get_n_owned_old(rec) == 0)) {
02490 n_owned_zero:
02491     fputs("InnoDB: n owned is zero\n", stderr);
02492     goto func_exit;
02493   }
02494 
02495   if (UNIV_UNLIKELY(slot_no != n_slots - 1)) {
02496     fprintf(stderr, "InnoDB: n slots wrong %lu %lu\n",
02497       (ulong) slot_no, (ulong) (n_slots - 1));
02498     goto func_exit;
02499   }
02500 
02501   if (UNIV_UNLIKELY(page_header_get_field(page, PAGE_N_RECS)
02502         + PAGE_HEAP_NO_USER_LOW
02503         != count + 1)) {
02504     fprintf(stderr, "InnoDB: n recs wrong %lu %lu\n",
02505       (ulong) page_header_get_field(page, PAGE_N_RECS)
02506       + PAGE_HEAP_NO_USER_LOW,
02507       (ulong) (count + 1));
02508     goto func_exit;
02509   }
02510 
02511   if (UNIV_UNLIKELY(data_size != page_get_data_size(page))) {
02512     fprintf(stderr,
02513       "InnoDB: Summed data size %lu, returned by func %lu\n",
02514       (ulong) data_size, (ulong) page_get_data_size(page));
02515     goto func_exit;
02516   }
02517 
02518   /* Check then the free list */
02519   rec = page_header_get_ptr(page, PAGE_FREE);
02520 
02521   while (rec != NULL) {
02522     offsets = rec_get_offsets(rec, index, offsets,
02523             ULINT_UNDEFINED, &heap);
02524     if (UNIV_UNLIKELY(!page_rec_validate(rec, offsets))) {
02525 
02526       goto func_exit;
02527     }
02528 
02529     count++;
02530     offs = page_offset(rec_get_start(rec, offsets));
02531     i = rec_offs_size(offsets);
02532     if (UNIV_UNLIKELY(offs + i >= UNIV_PAGE_SIZE)) {
02533       fputs("InnoDB: record offset out of bounds\n", stderr);
02534       goto func_exit;
02535     }
02536 
02537     while (i--) {
02538 
02539       if (UNIV_UNLIKELY(buf[offs + i])) {
02540         fputs("InnoDB: Record overlaps another"
02541               " in free list\n", stderr);
02542         goto func_exit;
02543       }
02544 
02545       buf[offs + i] = 1;
02546     }
02547 
02548     rec = page_rec_get_next(rec);
02549   }
02550 
02551   if (UNIV_UNLIKELY(page_dir_get_n_heap(page) != count + 1)) {
02552     fprintf(stderr, "InnoDB: N heap is wrong %lu %lu\n",
02553       (ulong) page_dir_get_n_heap(page),
02554       (ulong) count + 1);
02555     goto func_exit;
02556   }
02557 
02558   ret = TRUE;
02559 
02560 func_exit:
02561   mem_heap_free(heap);
02562 
02563   if (UNIV_UNLIKELY(ret == FALSE)) {
02564 func_exit2:
02565     fprintf(stderr, 
02566       "InnoDB: Apparent corruption"
02567       " in space %lu page %lu index %s\n",
02568       (ulong) page_get_space_id(page),
02569       (ulong) page_get_page_no(page),
02570       index->name);
02571     buf_page_print(page, 0);
02572   }
02573 
02574   return(ret);
02575 }
02576 
02577 #ifndef UNIV_HOTBACKUP
02578 /***************************************************************/
02581 UNIV_INTERN
02582 const rec_t*
02583 page_find_rec_with_heap_no(
02584 /*=======================*/
02585   const page_t* page, 
02586   ulint   heap_no)
02587 {
02588   const rec_t*  rec;
02589 
02590   if (page_is_comp(page)) {
02591     rec = page + PAGE_NEW_INFIMUM;
02592 
02593     for(;;) {
02594       ulint rec_heap_no = rec_get_heap_no_new(rec);
02595 
02596       if (rec_heap_no == heap_no) {
02597 
02598         return(rec);
02599       } else if (rec_heap_no == PAGE_HEAP_NO_SUPREMUM) {
02600 
02601         return(NULL);
02602       }
02603 
02604       rec = page + rec_get_next_offs(rec, TRUE);
02605     }
02606   } else {
02607     rec = page + PAGE_OLD_INFIMUM;
02608 
02609     for (;;) {
02610       ulint rec_heap_no = rec_get_heap_no_old(rec);
02611 
02612       if (rec_heap_no == heap_no) {
02613 
02614         return(rec);
02615       } else if (rec_heap_no == PAGE_HEAP_NO_SUPREMUM) {
02616 
02617         return(NULL);
02618       }
02619 
02620       rec = page + rec_get_next_offs(rec, FALSE);
02621     }
02622   }
02623 }
02624 #endif /* !UNIV_HOTBACKUP */