1
/******************************************************
4
(c) 1994-1996 Innobase Oy
6
Created 2/2/1994 Heikki Tuuri
7
*******************************************************/
14
#include "page0types.h"
17
#include "data0data.h"
18
#include "dict0dict.h"
23
#ifdef UNIV_MATERIALIZE
31
Index page header starts at the first offset left free by the FIL-module */
33
typedef byte page_header_t;
35
#define PAGE_HEADER FSEG_PAGE_DATA /* index page header starts at this
37
/*-----------------------------*/
38
#define PAGE_N_DIR_SLOTS 0 /* number of slots in page directory */
39
#define PAGE_HEAP_TOP 2 /* pointer to record heap top */
40
#define PAGE_N_HEAP 4 /* number of records in the heap,
41
bit 15=flag: new-style compact page format */
42
#define PAGE_FREE 6 /* pointer to start of page free record list */
43
#define PAGE_GARBAGE 8 /* number of bytes in deleted records */
44
#define PAGE_LAST_INSERT 10 /* pointer to the last inserted record, or
45
NULL if this info has been reset by a delete,
47
#define PAGE_DIRECTION 12 /* last insert direction: PAGE_LEFT, ... */
48
#define PAGE_N_DIRECTION 14 /* number of consecutive inserts to the same
50
#define PAGE_N_RECS 16 /* number of user records on the page */
51
#define PAGE_MAX_TRX_ID 18 /* highest id of a trx which may have modified
52
a record on the page; a dulint; defined only
53
in secondary indexes; specifically, not in an
54
ibuf tree; NOTE: this may be modified only
55
when the thread has an x-latch to the page,
56
and ALSO an x-latch to btr_search_latch
57
if there is a hash index to the page! */
58
#define PAGE_HEADER_PRIV_END 26 /* end of private data structure of the page
59
header which are set in a page create */
61
#define PAGE_LEVEL 26 /* level of the node in an index tree; the
62
leaf level is the level 0 */
63
#define PAGE_INDEX_ID 28 /* index id where the page belongs */
64
#define PAGE_BTR_SEG_LEAF 36 /* file segment header for the leaf pages in
65
a B-tree: defined only on the root page of a
66
B-tree, but not in the root of an ibuf tree */
67
#define PAGE_BTR_IBUF_FREE_LIST PAGE_BTR_SEG_LEAF
68
#define PAGE_BTR_IBUF_FREE_LIST_NODE PAGE_BTR_SEG_LEAF
69
/* in the place of PAGE_BTR_SEG_LEAF and _TOP
70
there is a free list base node if the page is
71
the root page of an ibuf tree, and at the same
72
place is the free list node if the page is in
74
#define PAGE_BTR_SEG_TOP (36 + FSEG_HEADER_SIZE)
75
/* file segment header for the non-leaf pages
76
in a B-tree: defined only on the root page of
77
a B-tree, but not in the root of an ibuf
80
#define PAGE_DATA (PAGE_HEADER + 36 + 2 * FSEG_HEADER_SIZE)
81
/* start of data on the page */
83
#define PAGE_OLD_INFIMUM (PAGE_DATA + 1 + REC_N_OLD_EXTRA_BYTES)
84
/* offset of the page infimum record on an
86
#define PAGE_OLD_SUPREMUM (PAGE_DATA + 2 + 2 * REC_N_OLD_EXTRA_BYTES + 8)
87
/* offset of the page supremum record on an
89
#define PAGE_OLD_SUPREMUM_END (PAGE_OLD_SUPREMUM + 9)
90
/* offset of the page supremum record end on
92
#define PAGE_NEW_INFIMUM (PAGE_DATA + REC_N_NEW_EXTRA_BYTES)
93
/* offset of the page infimum record on a
94
new-style compact page */
95
#define PAGE_NEW_SUPREMUM (PAGE_DATA + 2 * REC_N_NEW_EXTRA_BYTES + 8)
96
/* offset of the page supremum record on a
97
new-style compact page */
98
#define PAGE_NEW_SUPREMUM_END (PAGE_NEW_SUPREMUM + 8)
99
/* offset of the page supremum record end on
100
a new-style compact page */
101
/*-----------------------------*/
103
/* Directions of cursor movement */
106
#define PAGE_SAME_REC 3
107
#define PAGE_SAME_PAGE 4
108
#define PAGE_NO_DIRECTION 5
114
typedef byte page_dir_slot_t;
115
typedef page_dir_slot_t page_dir_t;
117
/* Offset of the directory start down from the page end. We call the
118
slot with the highest file address directory start, as it points to
119
the first record in the list of records. */
120
#define PAGE_DIR FIL_PAGE_DATA_END
122
/* We define a slot in the page directory as two bytes */
123
#define PAGE_DIR_SLOT_SIZE 2
125
/* The offset of the physically lower end of the directory, counted from
126
page end, when the page is empty */
127
#define PAGE_EMPTY_DIR_START (PAGE_DIR + 2 * PAGE_DIR_SLOT_SIZE)
129
/* The maximum and minimum number of records owned by a directory slot. The
130
number may drop below the minimum in the first and the last slot in the
132
#define PAGE_DIR_SLOT_MAX_N_OWNED 8
133
#define PAGE_DIR_SLOT_MIN_N_OWNED 4
135
/*****************************************************************
136
Returns the max trx id field value. */
141
page_t* page); /* in: page */
142
/*****************************************************************
143
Sets the max trx id field value. */
148
page_t* page, /* in: page */
149
dulint trx_id);/* in: transaction id */
150
/*****************************************************************
151
Sets the max trx id field value if trx_id is bigger than the previous
155
page_update_max_trx_id(
156
/*===================*/
157
page_t* page, /* in: page */
158
dulint trx_id); /* in: transaction id */
159
/*****************************************************************
160
Reads the given header field. */
163
page_header_get_field(
164
/*==================*/
165
page_t* page, /* in: page */
166
ulint field); /* in: PAGE_N_DIR_SLOTS, ... */
167
/*****************************************************************
168
Sets the given header field. */
171
page_header_set_field(
172
/*==================*/
173
page_t* page, /* in: page */
174
ulint field, /* in: PAGE_N_DIR_SLOTS, ... */
175
ulint val); /* in: value */
176
/*****************************************************************
177
Returns the pointer stored in the given header field. */
182
/* out: pointer or NULL */
183
page_t* page, /* in: page */
184
ulint field); /* in: PAGE_FREE, ... */
185
/*****************************************************************
186
Sets the pointer stored in the given header field. */
191
page_t* page, /* in: page */
192
ulint field, /* in: PAGE_FREE, ... */
193
byte* ptr); /* in: pointer or NULL*/
194
/*****************************************************************
195
Resets the last insert info field in the page header. Writes to mlog
196
about this operation. */
199
page_header_reset_last_insert(
200
/*==========================*/
201
page_t* page, /* in: page */
202
mtr_t* mtr); /* in: mtr */
203
/****************************************************************
204
Gets the first record on the page. */
207
page_get_infimum_rec(
208
/*=================*/
209
/* out: the first record in record list */
210
page_t* page); /* in: page which must have record(s) */
211
/****************************************************************
212
Gets the last record on the page. */
215
page_get_supremum_rec(
216
/*==================*/
217
/* out: the last record in record list */
218
page_t* page); /* in: page which must have record(s) */
219
/****************************************************************
220
Returns the middle record of record list. If there are an even number
221
of records in the list, returns the first record of upper half-list. */
226
/* out: middle record */
227
page_t* page); /* in: page */
228
/*****************************************************************
229
Compares a data tuple to a physical record. Differs from the function
230
cmp_dtuple_rec_with_match in the way that the record must reside on an
231
index page, and also page infimum and supremum records can be given in
232
the parameter rec. These are considered as the negative infinity and
233
the positive infinity in the alphabetical order. */
236
page_cmp_dtuple_rec_with_match(
237
/*===========================*/
238
/* out: 1, 0, -1, if dtuple is greater, equal,
239
less than rec, respectively, when only the
240
common first fields are compared */
241
dtuple_t* dtuple, /* in: data tuple */
242
rec_t* rec, /* in: physical record on a page; may also
243
be page infimum or supremum, in which case
244
matched-parameter values below are not
246
const ulint* offsets,/* in: array returned by rec_get_offsets() */
247
ulint* matched_fields, /* in/out: number of already completely
248
matched fields; when function returns
249
contains the value for current comparison */
250
ulint* matched_bytes); /* in/out: number of already matched
251
bytes within the first field not completely
252
matched; when function returns contains the
253
value for current comparison */
254
/*****************************************************************
255
Gets the number of user records on page (the infimum and supremum records
256
are not user records). */
261
/* out: number of user records */
262
page_t* page); /* in: index page */
263
/*******************************************************************
264
Returns the number of records before the given record in chain.
265
The number includes infimum and supremum records. */
268
page_rec_get_n_recs_before(
269
/*=======================*/
270
/* out: number of records */
271
rec_t* rec); /* in: the physical record */
272
/*****************************************************************
273
Gets the number of records in the heap. */
278
/* out: number of user records */
279
page_t* page); /* in: index page */
280
/*****************************************************************
281
Sets the number of records in the heap. */
286
page_t* page, /* in: index page */
287
ulint n_heap);/* in: number of records */
288
/*****************************************************************
289
Gets the number of dir slots in directory. */
292
page_dir_get_n_slots(
293
/*=================*/
294
/* out: number of slots */
295
page_t* page); /* in: index page */
296
/*****************************************************************
297
Sets the number of dir slots in directory. */
300
page_dir_set_n_slots(
301
/*=================*/
302
/* out: number of slots */
303
page_t* page, /* in: index page */
304
ulint n_slots);/* in: number of slots */
305
/*****************************************************************
306
Gets pointer to nth directory slot. */
309
page_dir_get_nth_slot(
310
/*==================*/
311
/* out: pointer to dir slot */
312
page_t* page, /* in: index page */
313
ulint n); /* in: position */
314
/******************************************************************
315
Used to check the consistency of a record on a page. */
320
/* out: TRUE if succeed */
321
rec_t* rec); /* in: record */
322
/*******************************************************************
323
Gets the record pointed to by a directory slot. */
326
page_dir_slot_get_rec(
327
/*==================*/
328
/* out: pointer to record */
329
page_dir_slot_t* slot); /* in: directory slot */
330
/*******************************************************************
331
This is used to set the record offset in a directory slot. */
334
page_dir_slot_set_rec(
335
/*==================*/
336
page_dir_slot_t* slot, /* in: directory slot */
337
rec_t* rec); /* in: record on the page */
338
/*******************************************************************
339
Gets the number of records owned by a directory slot. */
342
page_dir_slot_get_n_owned(
343
/*======================*/
344
/* out: number of records */
345
page_dir_slot_t* slot); /* in: page directory slot */
346
/*******************************************************************
347
This is used to set the owned records field of a directory slot. */
350
page_dir_slot_set_n_owned(
351
/*======================*/
352
page_dir_slot_t* slot, /* in: directory slot */
353
ulint n); /* in: number of records owned
355
/****************************************************************
356
Calculates the space reserved for directory slots of a given
357
number of records. The exact value is a fraction number
358
n * PAGE_DIR_SLOT_SIZE / PAGE_DIR_SLOT_MIN_N_OWNED, and it is
359
rounded upwards to an integer. */
362
page_dir_calc_reserved_space(
363
/*=========================*/
364
ulint n_recs); /* in: number of records */
365
/*******************************************************************
366
Looks for the directory slot which owns the given record. */
369
page_dir_find_owner_slot(
370
/*=====================*/
371
/* out: the directory slot number */
372
rec_t* rec); /* in: the physical record */
373
/****************************************************************
374
Determine whether the page is in new-style compact format. */
379
/* out: nonzero if the page is in compact
380
format, zero if it is in old-style format */
381
page_t* page); /* in: index page */
382
/****************************************************************
383
TRUE if the record is on a page in compact format. */
388
/* out: nonzero if in compact format */
389
const rec_t* rec); /* in: record */
390
/****************************************************************
391
Gets the pointer to the next record on the page. */
396
/* out: pointer to next record */
397
rec_t* rec); /* in: pointer to record, must not be page
399
/****************************************************************
400
Sets the pointer to the next record on the page. */
405
rec_t* rec, /* in: pointer to record, must not be
407
rec_t* next); /* in: pointer to next record, must not
409
/****************************************************************
410
Gets the pointer to the previous record. */
415
/* out: pointer to previous record */
416
rec_t* rec); /* in: pointer to record,
417
must not be page infimum */
418
/****************************************************************
419
TRUE if the record is a user record on the page. */
422
page_rec_is_user_rec_low(
423
/*=====================*/
424
/* out: TRUE if a user record */
425
ulint offset);/* in: record offset on page */
426
/****************************************************************
427
TRUE if the record is the supremum record on a page. */
430
page_rec_is_supremum_low(
431
/*=====================*/
432
/* out: TRUE if the supremum record */
433
ulint offset);/* in: record offset on page */
434
/****************************************************************
435
TRUE if the record is the infimum record on a page. */
438
page_rec_is_infimum_low(
439
/*=====================*/
440
/* out: TRUE if the infimum record */
441
ulint offset);/* in: record offset on page */
443
/****************************************************************
444
TRUE if the record is a user record on the page. */
447
page_rec_is_user_rec(
448
/*=================*/
449
/* out: TRUE if a user record */
450
const rec_t* rec); /* in: record */
451
/****************************************************************
452
TRUE if the record is the supremum record on a page. */
455
page_rec_is_supremum(
456
/*=================*/
457
/* out: TRUE if the supremum record */
458
const rec_t* rec); /* in: record */
459
/****************************************************************
460
TRUE if the record is the infimum record on a page. */
465
/* out: TRUE if the infimum record */
466
const rec_t* rec); /* in: record */
467
/*******************************************************************
468
Looks for the record which owns the given record. */
471
page_rec_find_owner_rec(
472
/*====================*/
473
/* out: the owner record */
474
rec_t* rec); /* in: the physical record */
475
/***************************************************************************
476
This is a low-level operation which is used in a database index creation
477
to update the page number of a created B-tree to a data dictionary
481
page_rec_write_index_page_no(
482
/*=========================*/
483
rec_t* rec, /* in: record to update */
484
ulint i, /* in: index of the field to update */
485
ulint page_no,/* in: value to write */
486
mtr_t* mtr); /* in: mtr */
487
/****************************************************************
488
Returns the maximum combined size of records which can be inserted on top
492
page_get_max_insert_size(
493
/*=====================*/
494
/* out: maximum combined size for inserted records */
495
page_t* page, /* in: index page */
496
ulint n_recs); /* in: number of records */
497
/****************************************************************
498
Returns the maximum combined size of records which can be inserted on top
499
of record heap if page is first reorganized. */
502
page_get_max_insert_size_after_reorganize(
503
/*======================================*/
504
/* out: maximum combined size for inserted records */
505
page_t* page, /* in: index page */
506
ulint n_recs);/* in: number of records */
507
/*****************************************************************
508
Calculates free space if a page is emptied. */
511
page_get_free_space_of_empty(
512
/*=========================*/
513
/* out: free space */
514
ulint comp) /* in: nonzero=compact page format */
515
__attribute__((const));
516
/****************************************************************
517
Returns the sum of the sizes of the records in the record list
518
excluding the infimum and supremum records. */
523
/* out: data in bytes */
524
page_t* page); /* in: index page */
525
/****************************************************************
526
Allocates a block of memory from an index page. */
531
/* out: pointer to start of allocated
532
buffer, or NULL if allocation fails */
533
page_t* page, /* in: index page */
534
ulint need, /* in: number of bytes needed */
535
dict_index_t* index, /* in: record descriptor */
536
ulint* heap_no);/* out: this contains the heap number
537
of the allocated record
538
if allocation succeeds */
539
/****************************************************************
540
Puts a record to free list. */
545
page_t* page, /* in: index page */
546
rec_t* rec, /* in: pointer to the (origin of) record */
547
const ulint* offsets);/* in: array returned by rec_get_offsets() */
548
/**************************************************************
549
The index page creation function. */
554
/* out: pointer to the page */
555
buf_frame_t* frame, /* in: a buffer frame where the page is
557
mtr_t* mtr, /* in: mini-transaction handle */
558
ulint comp); /* in: nonzero=compact page format */
559
/*****************************************************************
560
Differs from page_copy_rec_list_end, because this function does not
561
touch the lock table and max trx id on page. */
564
page_copy_rec_list_end_no_locks(
565
/*============================*/
566
page_t* new_page, /* in: index page to copy to */
567
page_t* page, /* in: index page */
568
rec_t* rec, /* in: record on page */
569
dict_index_t* index, /* in: record descriptor */
570
mtr_t* mtr); /* in: mtr */
571
/*****************************************************************
572
Copies records from page to new_page, from the given record onward,
573
including that record. Infimum and supremum records are not copied.
574
The records are copied to the start of the record list on new_page. */
577
page_copy_rec_list_end(
578
/*===================*/
579
page_t* new_page, /* in: index page to copy to */
580
page_t* page, /* in: index page */
581
rec_t* rec, /* in: record on page */
582
dict_index_t* index, /* in: record descriptor */
583
mtr_t* mtr); /* in: mtr */
584
/*****************************************************************
585
Copies records from page to new_page, up to the given record, NOT
586
including that record. Infimum and supremum records are not copied.
587
The records are copied to the end of the record list on new_page. */
590
page_copy_rec_list_start(
591
/*=====================*/
592
page_t* new_page, /* in: index page to copy to */
593
page_t* page, /* in: index page */
594
rec_t* rec, /* in: record on page */
595
dict_index_t* index, /* in: record descriptor */
596
mtr_t* mtr); /* in: mtr */
597
/*****************************************************************
598
Deletes records from a page from a given record onward, including that record.
599
The infimum and supremum records are not deleted. */
602
page_delete_rec_list_end(
603
/*=====================*/
604
page_t* page, /* in: index page */
605
rec_t* rec, /* in: record on page */
606
dict_index_t* index, /* in: record descriptor */
607
ulint n_recs, /* in: number of records to delete,
608
or ULINT_UNDEFINED if not known */
609
ulint size, /* in: the sum of the sizes of the
610
records in the end of the chain to
611
delete, or ULINT_UNDEFINED if not known */
612
mtr_t* mtr); /* in: mtr */
613
/*****************************************************************
614
Deletes records from page, up to the given record, NOT including
615
that record. Infimum and supremum records are not deleted. */
618
page_delete_rec_list_start(
619
/*=======================*/
620
page_t* page, /* in: index page */
621
rec_t* rec, /* in: record on page */
622
dict_index_t* index, /* in: record descriptor */
623
mtr_t* mtr); /* in: mtr */
624
/*****************************************************************
625
Moves record list end to another page. Moved records include
629
page_move_rec_list_end(
630
/*===================*/
631
page_t* new_page, /* in: index page where to move */
632
page_t* page, /* in: index page */
633
rec_t* split_rec, /* in: first record to move */
634
dict_index_t* index, /* in: record descriptor */
635
mtr_t* mtr); /* in: mtr */
636
/*****************************************************************
637
Moves record list start to another page. Moved records do not include
641
page_move_rec_list_start(
642
/*=====================*/
643
page_t* new_page, /* in: index page where to move */
644
page_t* page, /* in: index page */
645
rec_t* split_rec, /* in: first record not to move */
646
dict_index_t* index, /* in: record descriptor */
647
mtr_t* mtr); /* in: mtr */
648
/********************************************************************
649
Splits a directory slot which owns too many records. */
654
page_t* page, /* in: the index page in question */
655
ulint slot_no); /* in: the directory slot */
656
/*****************************************************************
657
Tries to balance the given directory slot with too few records
658
with the upper neighbor, so that there are at least the minimum number
659
of records owned by the slot; this may result in the merging of
663
page_dir_balance_slot(
664
/*==================*/
665
page_t* page, /* in: index page */
666
ulint slot_no); /* in: the directory slot */
667
/**************************************************************
668
Parses a log record of a record list end or start deletion. */
671
page_parse_delete_rec_list(
672
/*=======================*/
673
/* out: end of log record or NULL */
674
byte type, /* in: MLOG_LIST_END_DELETE,
675
MLOG_LIST_START_DELETE,
676
MLOG_COMP_LIST_END_DELETE or
677
MLOG_COMP_LIST_START_DELETE */
678
byte* ptr, /* in: buffer */
679
byte* end_ptr,/* in: buffer end */
680
dict_index_t* index, /* in: record descriptor */
681
page_t* page, /* in: page or NULL */
682
mtr_t* mtr); /* in: mtr or NULL */
683
/***************************************************************
684
Parses a redo log record of creating a page. */
689
/* out: end of log record or NULL */
690
byte* ptr, /* in: buffer */
691
byte* end_ptr,/* in: buffer end */
692
ulint comp, /* in: nonzero=compact page format */
693
page_t* page, /* in: page or NULL */
694
mtr_t* mtr); /* in: mtr or NULL */
695
/****************************************************************
696
Prints record contents including the data relevant only in
697
the index page context. */
702
rec_t* rec, /* in: physical record */
703
const ulint* offsets);/* in: record descriptor */
704
/*******************************************************************
705
This is used to print the contents of the directory for
706
debugging purposes. */
711
page_t* page, /* in: index page */
712
ulint pr_n); /* in: print n first and n last entries */
713
/*******************************************************************
714
This is used to print the contents of the page record list for
715
debugging purposes. */
720
page_t* page, /* in: index page */
721
dict_index_t* index, /* in: dictionary index of the page */
722
ulint pr_n); /* in: print n first and n last entries */
723
/*******************************************************************
724
Prints the info in a page header. */
730
/*******************************************************************
731
This is used to print the contents of the page for
732
debugging purposes. */
737
page_t* page, /* in: index page */
738
dict_index_t* index, /* in: dictionary index of the page */
739
ulint dn, /* in: print dn first and last entries
741
ulint rn); /* in: print rn first and last records
743
/*******************************************************************
744
The following is used to validate a record on a page. This function
745
differs from rec_validate as it can also check the n_owned field and
746
the heap_no field. */
751
/* out: TRUE if ok */
752
rec_t* rec, /* in: physical record */
753
const ulint* offsets);/* in: array returned by rec_get_offsets() */
754
/*******************************************************************
755
Checks that the first directory slot points to the infimum record and
756
the last to the supremum. This function is intended to track if the
757
bug fixed in 4.0.14 has caused corruption to users' databases. */
762
page_t* page); /* in: index page */
763
/*******************************************************************
764
This function checks the consistency of an index page when we do not
765
know the index. This is also resilient so that this should never crash
766
even if the page is total garbage. */
769
page_simple_validate(
770
/*=================*/
771
/* out: TRUE if ok */
772
page_t* page); /* in: index page */
773
/*******************************************************************
774
This function checks the consistency of an index page. */
779
/* out: TRUE if ok */
780
page_t* page, /* in: index page */
781
dict_index_t* index); /* in: data dictionary index containing
782
the page record type definition */
783
/*******************************************************************
784
Looks in the page record list for a record with the given heap number. */
787
page_find_rec_with_heap_no(
788
/*=======================*/
789
/* out: record, NULL if not found */
790
page_t* page, /* in: index page */
791
ulint heap_no);/* in: heap number */
793
#ifdef UNIV_MATERIALIZE
795
#define UNIV_INLINE UNIV_INLINE_ORIGINAL
799
#include "page0page.ic"