1
/*****************************************************************************
3
Copyright (C) 1994, 2009, Innobase Oy. All Rights Reserved.
5
This program is free software; you can redistribute it and/or modify it under
6
the terms of the GNU General Public License as published by the Free Software
7
Foundation; version 2 of the License.
9
This program is distributed in the hope that it will be useful, but WITHOUT
10
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
You should have received a copy of the GNU General Public License along with
14
this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
15
St, Fifth Floor, Boston, MA 02110-1301 USA
17
*****************************************************************************/
19
/********************************************************************//**
1
/************************************************************************
4
(c) 1994-1996 Innobase Oy
23
6
Created 10/4/1994 Heikki Tuuri
24
7
*************************************************************************/
31
14
#include "page0zip.h"
32
16
#include "mtr0log.h"
33
17
#include "log0recv.h"
35
#ifndef UNIV_HOTBACKUP
36
18
#include "rem0cmp.h"
20
static ulint page_rnd = 976722341;
38
22
#ifdef PAGE_CUR_ADAPT
39
23
# ifdef UNIV_SEARCH_PERF_STAT
40
24
static ulint page_cur_short_succ = 0;
41
25
# endif /* UNIV_SEARCH_PERF_STAT */
43
/*******************************************************************//**
44
This is a linear congruential generator PRNG. Returns a pseudo random
45
number between 0 and 2^64-1 inclusive. The formula and the constants
47
X[n+1] = (a * X[n] + c) mod m
49
X[0] = ut_time_us(NULL)
50
a = 1103515245 (3^5 * 5 * 7 * 129749)
51
c = 12345 (3 * 5 * 823)
52
m = 18446744073709551616 (2^64)
54
@return number between 0 and 2^64-1 */
57
page_cur_lcg_prng(void)
58
/*===================*/
60
#define LCG_a 1103515245
62
static ib_uint64_t lcg_current = 0;
63
static ibool initialized = FALSE;
66
lcg_current = (ib_uint64_t) ut_time_us(NULL);
70
/* no need to "% 2^64" explicitly because lcg_current is
71
64 bit and this will be done anyway */
72
lcg_current = LCG_a * lcg_current + LCG_c;
77
/****************************************************************//**
78
Tries a search shortcut based on the last insert.
79
@return TRUE on success */
27
/********************************************************************
28
Tries a search shortcut based on the last insert. */
82
31
page_cur_try_search_shortcut(
83
32
/*=========================*/
84
const buf_block_t* block, /*!< in: index page */
85
const dict_index_t* index, /*!< in: record descriptor */
86
const dtuple_t* tuple, /*!< in: data tuple */
33
/* out: TRUE on success */
34
const buf_block_t* block, /* in: index page */
35
const dict_index_t* index, /* in: record descriptor */
36
const dtuple_t* tuple, /* in: data tuple */
87
37
ulint* iup_matched_fields,
88
/*!< in/out: already matched
38
/* in/out: already matched
89
39
fields in upper limit record */
90
40
ulint* iup_matched_bytes,
91
/*!< in/out: already matched
41
/* in/out: already matched
92
42
bytes in a field not yet
93
43
completely matched */
94
44
ulint* ilow_matched_fields,
95
/*!< in/out: already matched
45
/* in/out: already matched
96
46
fields in lower limit record */
97
47
ulint* ilow_matched_bytes,
98
/*!< in/out: already matched
48
/* in/out: already matched
99
49
bytes in a field not yet
100
50
completely matched */
101
page_cur_t* cursor) /*!< out: page cursor */
51
page_cur_t* cursor) /* out: page cursor */
104
54
const rec_t* next_rec;
191
141
#ifdef PAGE_CUR_LE_OR_EXTENDS
192
/****************************************************************//**
142
/********************************************************************
193
143
Checks if the nth field in a record is a character type field which extends
194
144
the nth field in tuple, i.e., the field is longer or equal in length and has
195
common first characters.
196
@return TRUE if rec field extends tuple field */
145
common first characters. */
199
148
page_cur_rec_field_extends(
200
149
/*=======================*/
201
const dtuple_t* tuple, /*!< in: data tuple */
202
const rec_t* rec, /*!< in: record */
203
const ulint* offsets,/*!< in: array returned by rec_get_offsets() */
204
ulint n) /*!< in: compare nth field */
150
/* out: TRUE if rec field
151
extends tuple field */
152
const dtuple_t* tuple, /* in: data tuple */
153
const rec_t* rec, /* in: record */
154
const ulint* offsets,/* in: array returned by rec_get_offsets() */
155
ulint n) /* in: compare nth field */
206
157
const dtype_t* type;
207
158
const dfield_t* dfield;
240
191
#endif /* PAGE_CUR_LE_OR_EXTENDS */
242
/****************************************************************//**
193
/********************************************************************
243
194
Searches the right position for a page cursor. */
246
197
page_cur_search_with_match(
247
198
/*=======================*/
248
const buf_block_t* block, /*!< in: buffer block */
249
const dict_index_t* index, /*!< in: record descriptor */
250
const dtuple_t* tuple, /*!< in: data tuple */
251
ulint mode, /*!< in: PAGE_CUR_L,
199
const buf_block_t* block, /* in: buffer block */
200
const dict_index_t* index, /* in: record descriptor */
201
const dtuple_t* tuple, /* in: data tuple */
202
ulint mode, /* in: PAGE_CUR_L,
252
203
PAGE_CUR_LE, PAGE_CUR_G, or
254
205
ulint* iup_matched_fields,
255
/*!< in/out: already matched
206
/* in/out: already matched
256
207
fields in upper limit record */
257
208
ulint* iup_matched_bytes,
258
/*!< in/out: already matched
209
/* in/out: already matched
259
210
bytes in a field not yet
260
211
completely matched */
261
212
ulint* ilow_matched_fields,
262
/*!< in/out: already matched
213
/* in/out: already matched
263
214
fields in lower limit record */
264
215
ulint* ilow_matched_bytes,
265
/*!< in/out: already matched
216
/* in/out: already matched
266
217
bytes in a field not yet
267
218
completely matched */
268
page_cur_t* cursor) /*!< out: page cursor */
219
page_cur_t* cursor) /* out: page cursor */
540
/***********************************************************//**
491
/***************************************************************
541
492
Positions a page cursor on a randomly chosen user record on a page. If there
542
493
are no user records, sets the cursor on the infimum record. */
545
496
page_cur_open_on_rnd_user_rec(
546
497
/*==========================*/
547
buf_block_t* block, /*!< in: page */
548
page_cur_t* cursor) /*!< out: page cursor */
498
buf_block_t* block, /* in: page */
499
page_cur_t* cursor) /* out: page cursor */
551
502
ulint n_recs = page_get_n_recs(buf_block_get_frame(block));
560
rnd = (ulint) (page_cur_lcg_prng() % n_recs);
511
page_rnd += 87584577;
513
rnd = page_rnd % n_recs;
563
516
page_cur_move_to_next(cursor);
567
/***********************************************************//**
520
/***************************************************************
568
521
Writes the log record of a record insert on a page. */
571
524
page_cur_insert_rec_write_log(
572
525
/*==========================*/
573
rec_t* insert_rec, /*!< in: inserted physical record */
574
ulint rec_size, /*!< in: insert_rec size */
575
rec_t* cursor_rec, /*!< in: record the
526
rec_t* insert_rec, /* in: inserted physical record */
527
ulint rec_size, /* in: insert_rec size */
528
rec_t* cursor_rec, /* in: record the
576
529
cursor is pointing to */
577
dict_index_t* index, /*!< in: record descriptor */
578
mtr_t* mtr) /*!< in: mini-transaction handle */
530
dict_index_t* index, /* in: record descriptor */
531
mtr_t* mtr) /* in: mini-transaction handle */
580
533
ulint cur_rec_size;
581
534
ulint extra_size;
745
698
mlog_catenate_string(mtr, ins_ptr, rec_size);
748
#else /* !UNIV_HOTBACKUP */
749
# define page_cur_insert_rec_write_log(ins_rec,size,cur,index,mtr) ((void) 0)
750
#endif /* !UNIV_HOTBACKUP */
752
/***********************************************************//**
753
Parses a log record of a record insert on a page.
754
@return end of log record or NULL */
702
/***************************************************************
703
Parses a log record of a record insert on a page. */
757
706
page_cur_parse_insert_rec(
758
707
/*======================*/
759
ibool is_short,/*!< in: TRUE if short inserts */
760
byte* ptr, /*!< in: buffer */
761
byte* end_ptr,/*!< in: buffer end */
762
buf_block_t* block, /*!< in: page or NULL */
763
dict_index_t* index, /*!< in: record descriptor */
764
mtr_t* mtr) /*!< in: mtr or NULL */
708
/* out: end of log record or NULL */
709
ibool is_short,/* in: TRUE if short inserts */
710
byte* ptr, /* in: buffer */
711
byte* end_ptr,/* in: buffer end */
712
buf_block_t* block, /* in: page or NULL */
713
dict_index_t* index, /* in: record descriptor */
714
mtr_t* mtr) /* in: mtr or NULL */
766
716
ulint origin_offset;
767
717
ulint end_seg_len;
940
890
return(ptr + end_seg_len);
943
/***********************************************************//**
893
/***************************************************************
944
894
Inserts a record next to page cursor on an uncompressed page.
945
895
Returns pointer to inserted record if succeed, i.e., enough
946
space available, NULL otherwise. The cursor stays at the same position.
947
@return pointer to record if succeed, NULL otherwise */
896
space available, NULL otherwise. The cursor stays at the same position. */
950
899
page_cur_insert_rec_low(
951
900
/*====================*/
952
rec_t* current_rec,/*!< in: pointer to current record after
901
/* out: pointer to record if succeed, NULL
903
rec_t* current_rec,/* in: pointer to current record after
953
904
which the new record is inserted */
954
dict_index_t* index, /*!< in: record descriptor */
955
const rec_t* rec, /*!< in: pointer to a physical record */
956
ulint* offsets,/*!< in/out: rec_get_offsets(rec, index) */
957
mtr_t* mtr) /*!< in: mini-transaction handle, or NULL */
905
dict_index_t* index, /* in: record descriptor */
906
const rec_t* rec, /* in: pointer to a physical record */
907
ulint* offsets,/* in/out: rec_get_offsets(rec, index) */
908
mtr_t* mtr) /* in: mini-transaction handle, or NULL */
910
byte* insert_buf = NULL;
961
page_t* page; /*!< the relevant page */
962
rec_t* last_insert; /*!< cursor position at previous
912
page_t* page; /* the relevant page */
913
rec_t* last_insert; /* cursor position at previous
964
rec_t* free_rec; /*!< a free record that was reused,
915
rec_t* free_rec; /* a free record that was reused,
966
rec_t* insert_rec; /*!< inserted record */
967
ulint heap_no; /*!< heap number of the inserted
917
rec_t* insert_rec; /* inserted record */
918
ulint heap_no; /* heap number of the inserted
970
921
ut_ad(rec_offs_validate(rec, index, offsets));
1152
1103
return(insert_rec);
1155
/***********************************************************//**
1156
Compresses or reorganizes a page after an optimistic insert.
1157
@return rec if succeed, NULL otherwise */
1106
/***************************************************************
1107
Compresses or reorganizes a page after an optimistic insert. */
1160
1110
page_cur_insert_rec_zip_reorg(
1161
1111
/*==========================*/
1162
rec_t** current_rec,/*!< in/out: pointer to current record after
1112
/* out: rec if succeed, NULL otherwise */
1113
rec_t** current_rec,/* in/out: pointer to current record after
1163
1114
which the new record is inserted */
1164
buf_block_t* block, /*!< in: buffer block */
1165
dict_index_t* index, /*!< in: record descriptor */
1166
rec_t* rec, /*!< in: inserted record */
1167
page_t* page, /*!< in: uncompressed page */
1168
page_zip_des_t* page_zip,/*!< in: compressed page */
1169
mtr_t* mtr) /*!< in: mini-transaction, or NULL */
1115
buf_block_t* block, /* in: buffer block */
1116
dict_index_t* index, /* in: record descriptor */
1117
rec_t* rec, /* in: inserted record */
1118
page_t* page, /* in: uncompressed page */
1119
page_zip_des_t* page_zip,/* in: compressed page */
1120
mtr_t* mtr) /* in: mini-transaction, or NULL */
1197
1148
/* Out of space: restore the page */
1198
if (!page_zip_decompress(page_zip, page, FALSE)) {
1149
if (!page_zip_decompress(page_zip, page)) {
1199
1150
ut_error; /* Memory corrupted? */
1201
1152
ut_ad(page_validate(page, index));
1205
/***********************************************************//**
1156
/***************************************************************
1206
1157
Inserts a record next to page cursor on a compressed and uncompressed
1207
1158
page. Returns pointer to inserted record if succeed, i.e.,
1208
1159
enough space available, NULL otherwise.
1209
The cursor stays at the same position.
1210
@return pointer to record if succeed, NULL otherwise */
1160
The cursor stays at the same position. */
1213
1163
page_cur_insert_rec_zip(
1214
1164
/*====================*/
1215
rec_t** current_rec,/*!< in/out: pointer to current record after
1165
/* out: pointer to record if succeed, NULL
1167
rec_t** current_rec,/* in/out: pointer to current record after
1216
1168
which the new record is inserted */
1217
buf_block_t* block, /*!< in: buffer block of *current_rec */
1218
dict_index_t* index, /*!< in: record descriptor */
1219
const rec_t* rec, /*!< in: pointer to a physical record */
1220
ulint* offsets,/*!< in/out: rec_get_offsets(rec, index) */
1221
mtr_t* mtr) /*!< in: mini-transaction handle, or NULL */
1169
buf_block_t* block, /* in: buffer block of *current_rec */
1170
dict_index_t* index, /* in: record descriptor */
1171
const rec_t* rec, /* in: pointer to a physical record */
1172
ulint* offsets,/* in/out: rec_get_offsets(rec, index) */
1173
mtr_t* mtr) /* in: mini-transaction handle, or NULL */
1175
byte* insert_buf = NULL;
1224
1176
ulint rec_size;
1225
page_t* page; /*!< the relevant page */
1226
rec_t* last_insert; /*!< cursor position at previous
1177
page_t* page; /* the relevant page */
1178
rec_t* last_insert; /* cursor position at previous
1228
rec_t* free_rec; /*!< a free record that was reused,
1180
rec_t* free_rec; /* a free record that was reused,
1230
rec_t* insert_rec; /*!< inserted record */
1231
ulint heap_no; /*!< heap number of the inserted
1182
rec_t* insert_rec; /* inserted record */
1183
ulint heap_no; /* heap number of the inserted
1233
1185
page_zip_des_t* page_zip;
1333
1285
rec_get_next_ptr(free_rec, TRUE),
1336
if (!page_is_leaf(page)) {
1337
/* Zero out the node pointer of free_rec,
1338
in case it will not be overwritten by
1341
ut_ad(rec_size > REC_NODE_PTR_SIZE);
1343
if (rec_offs_extra_size(foffsets)
1344
+ rec_offs_data_size(foffsets) > rec_size) {
1346
memset(rec_get_end(free_rec, foffsets)
1347
- REC_NODE_PTR_SIZE, 0,
1350
} else if (dict_index_is_clust(index)) {
1351
/* Zero out the DB_TRX_ID and DB_ROLL_PTR
1352
columns of free_rec, in case it will not be
1353
overwritten by insert_rec. */
1359
trx_id_col = dict_index_get_sys_col_pos(index,
1361
ut_ad(trx_id_col > 0);
1362
ut_ad(trx_id_col != ULINT_UNDEFINED);
1364
trx_id_offs = rec_get_nth_field_offs(foffsets,
1366
ut_ad(len == DATA_TRX_ID_LEN);
1368
if (DATA_TRX_ID_LEN + DATA_ROLL_PTR_LEN + trx_id_offs
1369
+ rec_offs_extra_size(foffsets) > rec_size) {
1370
/* We will have to zero out the
1371
DB_TRX_ID and DB_ROLL_PTR, because
1372
they will not be fully overwritten by
1375
memset(free_rec + trx_id_offs, 0,
1376
DATA_TRX_ID_LEN + DATA_ROLL_PTR_LEN);
1379
ut_ad(free_rec + trx_id_offs + DATA_TRX_ID_LEN
1380
== rec_get_nth_field(free_rec, foffsets,
1381
trx_id_col + 1, &len));
1382
ut_ad(len == DATA_ROLL_PTR_LEN);
1385
1288
if (UNIV_LIKELY_NULL(heap)) {
1386
1289
mem_heap_free(heap);
1499
1402
return(insert_rec);
1502
#ifndef UNIV_HOTBACKUP
1503
/**********************************************************//**
1504
Writes a log record of copying a record list end to a new created page.
1505
@return 4-byte field where to write the log data length, or NULL if
1506
logging is disabled */
1405
/**************************************************************
1406
Writes a log record of copying a record list end to a new created page. */
1509
1409
page_copy_rec_list_to_created_page_write_log(
1510
1410
/*=========================================*/
1511
page_t* page, /*!< in: index page */
1512
dict_index_t* index, /*!< in: record descriptor */
1513
mtr_t* mtr) /*!< in: mtr */
1411
/* out: 4-byte field where to
1412
write the log data length,
1413
or NULL if logging is disabled */
1414
page_t* page, /* in: index page */
1415
dict_index_t* index, /* in: record descriptor */
1416
mtr_t* mtr) /* in: mtr */
1527
1430
return(log_ptr);
1529
#endif /* !UNIV_HOTBACKUP */
1531
/**********************************************************//**
1532
Parses a log record of copying a record list end to a new created page.
1533
@return end of log record or NULL */
1433
/**************************************************************
1434
Parses a log record of copying a record list end to a new created page. */
1536
1437
page_parse_copy_rec_list_to_created_page(
1537
1438
/*=====================================*/
1538
byte* ptr, /*!< in: buffer */
1539
byte* end_ptr,/*!< in: buffer end */
1540
buf_block_t* block, /*!< in: page or NULL */
1541
dict_index_t* index, /*!< in: record descriptor */
1542
mtr_t* mtr) /*!< in: mtr or NULL */
1439
/* out: end of log record or NULL */
1440
byte* ptr, /* in: buffer */
1441
byte* end_ptr,/* in: buffer end */
1442
buf_block_t* block, /* in: page or NULL */
1443
dict_index_t* index, /* in: record descriptor */
1444
mtr_t* mtr) /* in: mtr or NULL */
1545
1447
ulint log_data_len;
1584
1486
return(rec_end);
1587
#ifndef UNIV_HOTBACKUP
1588
/*************************************************************//**
1489
/*****************************************************************
1589
1490
Copies records from page to a newly created page, from a given record onward,
1590
1491
including that record. Infimum and supremum records are not copied. */
1593
1494
page_copy_rec_list_end_to_created_page(
1594
1495
/*===================================*/
1595
page_t* new_page, /*!< in/out: index page to copy to */
1596
rec_t* rec, /*!< in: first record to copy */
1597
dict_index_t* index, /*!< in: record descriptor */
1598
mtr_t* mtr) /*!< in: mtr */
1496
page_t* new_page, /* in/out: index page to copy to */
1497
rec_t* rec, /* in: first record to copy */
1498
dict_index_t* index, /* in: record descriptor */
1499
mtr_t* mtr) /* in: mtr */
1600
1501
page_dir_slot_t* slot = 0; /* remove warning */
1601
1502
byte* heap_top;
1758
1659
mtr_set_log_mode(mtr, log_mode);
1761
/***********************************************************//**
1662
/***************************************************************
1762
1663
Writes log record of a record delete on a page. */
1765
1666
page_cur_delete_rec_write_log(
1766
1667
/*==========================*/
1767
rec_t* rec, /*!< in: record to be deleted */
1768
dict_index_t* index, /*!< in: record descriptor */
1769
mtr_t* mtr) /*!< in: mini-transaction handle */
1668
rec_t* rec, /* in: record to be deleted */
1669
dict_index_t* index, /* in: record descriptor */
1670
mtr_t* mtr) /* in: mini-transaction handle */
1789
1690
mlog_close(mtr, log_ptr + 2);
1791
#else /* !UNIV_HOTBACKUP */
1792
# define page_cur_delete_rec_write_log(rec,index,mtr) ((void) 0)
1793
#endif /* !UNIV_HOTBACKUP */
1795
/***********************************************************//**
1796
Parses log record of a record delete on a page.
1797
@return pointer to record end or NULL */
1693
/***************************************************************
1694
Parses log record of a record delete on a page. */
1800
1697
page_cur_parse_delete_rec(
1801
1698
/*======================*/
1802
byte* ptr, /*!< in: buffer */
1803
byte* end_ptr,/*!< in: buffer end */
1804
buf_block_t* block, /*!< in: page or NULL */
1805
dict_index_t* index, /*!< in: record descriptor */
1806
mtr_t* mtr) /*!< in: mtr or NULL */
1699
/* out: pointer to record end or NULL */
1700
byte* ptr, /* in: buffer */
1701
byte* end_ptr,/* in: buffer end */
1702
buf_block_t* block, /* in: page or NULL */
1703
dict_index_t* index, /* in: record descriptor */
1704
mtr_t* mtr) /* in: mtr or NULL */
1809
1707
page_cur_t cursor;
1844
/***********************************************************//**
1742
/***************************************************************
1845
1743
Deletes a record at the page cursor. The cursor is moved to the next
1846
1744
record after the deleted one. */
1849
1747
page_cur_delete_rec(
1850
1748
/*================*/
1851
page_cur_t* cursor, /*!< in/out: a page cursor */
1852
dict_index_t* index, /*!< in: record descriptor */
1853
const ulint* offsets,/*!< in: rec_get_offsets(cursor->rec, index) */
1854
mtr_t* mtr) /*!< in: mini-transaction handle */
1749
page_cur_t* cursor, /* in/out: a page cursor */
1750
dict_index_t* index, /* in: record descriptor */
1751
const ulint* offsets,/* in: rec_get_offsets(cursor->rec, index) */
1752
mtr_t* mtr) /* in: mini-transaction handle */
1856
1754
page_dir_slot_t* cur_dir_slot;
1857
1755
page_dir_slot_t* prev_slot;
1958
1856
ut_a(!page_zip || page_zip_validate(page_zip, page));
1959
1857
#endif /* UNIV_ZIP_DEBUG */
1962
#ifdef UNIV_COMPILE_TEST_FUNCS
1964
/*******************************************************************//**
1965
Print the first n numbers, generated by page_cur_lcg_prng() to make sure
1966
(visually) that it works properly. */
1968
test_page_cur_lcg_prng(
1969
/*===================*/
1970
int n) /*!< in: print first n numbers */
1973
unsigned long long rnd;
1975
for (i = 0; i < n; i++) {
1976
rnd = page_cur_lcg_prng();
1977
printf("%llu\t%%2=%llu %%3=%llu %%5=%llu %%7=%llu %%11=%llu\n",
1987
#endif /* UNIV_COMPILE_TEST_FUNCS */