1/******************************************************
2XtraBackup: hot backup tool for InnoDB
3(c) 2009-2012 Percona Inc.
4Originally Created 3/3/2009 Yasufumi Kinoshita
5Written by Alexey Kopytov, Aleksandr Kuzminsky, Stewart Smith, Vadim Tkachenko,
6Yasufumi Kinoshita, Ignacio Nin and Baron Schwartz.
7
8This program is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; version 2 of the License.
11
12This program is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with this program; if not, write to the Free Software
19Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
20
21*******************************************************/
22
23/* Changed page bitmap implementation */
24
25#include "changed_page_bitmap.h"
26
27#include "common.h"
28#include "xtrabackup.h"
29#include "srv0srv.h"
30
31/* TODO: copy-pasted shared definitions from the XtraDB bitmap write code.
32Remove these on the first opportunity, i.e. single-binary XtraBackup. */
33
34/* log0online.h */
35
36/** Single bitmap file information */
37struct log_online_bitmap_file_t {
38 char name[FN_REFLEN]; /*!< Name with full path */
39 pfs_os_file_t file; /*!< Handle to opened file */
40 ib_uint64_t size; /*!< Size of the file */
41 ib_uint64_t offset; /*!< Offset of the next read,
42 or count of already-read bytes
43 */
44};
45
46/** A set of bitmap files containing some LSN range */
47struct log_online_bitmap_file_range_t {
48 size_t count; /*!< Number of files */
49 /*!< Dynamically-allocated array of info about individual files */
50 struct files_t {
51 char name[FN_REFLEN];/*!< Name of a file */
52 lsn_t start_lsn; /*!< Starting LSN of data in this
53 file */
54 ulong seq_num; /*!< Sequence number of this file */
55 } *files;
56};
57
58/* log0online.c */
59
60/** File name stem for bitmap files. */
61static const char* bmp_file_name_stem = "ib_modified_log_";
62
63/** The bitmap file block size in bytes. All writes will be multiples of this.
64 */
65enum {
66 MODIFIED_PAGE_BLOCK_SIZE = 4096
67};
68
69/** Offsets in a file bitmap block */
70enum {
71 MODIFIED_PAGE_IS_LAST_BLOCK = 0,/* 1 if last block in the current
72 write, 0 otherwise. */
73 MODIFIED_PAGE_START_LSN = 4, /* The starting tracked LSN of this and
74 other blocks in the same write */
75 MODIFIED_PAGE_END_LSN = 12, /* The ending tracked LSN of this and
76 other blocks in the same write */
77 MODIFIED_PAGE_SPACE_ID = 20, /* The space ID of tracked pages in
78 this block */
79 MODIFIED_PAGE_1ST_PAGE_ID = 24, /* The page ID of the first tracked
80 page in this block */
81 MODIFIED_PAGE_BLOCK_UNUSED_1 = 28,/* Unused in order to align the start
82 of bitmap at 8 byte boundary */
83 MODIFIED_PAGE_BLOCK_BITMAP = 32,/* Start of the bitmap itself */
84 MODIFIED_PAGE_BLOCK_UNUSED_2 = MODIFIED_PAGE_BLOCK_SIZE - 8,
85 /* Unused in order to align the end of
86 bitmap at 8 byte boundary */
87 MODIFIED_PAGE_BLOCK_CHECKSUM = MODIFIED_PAGE_BLOCK_SIZE - 4
88 /* The checksum of the current block */
89};
90
91/** Length of the bitmap data in a block */
92enum { MODIFIED_PAGE_BLOCK_BITMAP_LEN
93 = MODIFIED_PAGE_BLOCK_UNUSED_2 - MODIFIED_PAGE_BLOCK_BITMAP };
94
95/** Length of the bitmap data in a block in page ids */
96enum { MODIFIED_PAGE_BLOCK_ID_COUNT = MODIFIED_PAGE_BLOCK_BITMAP_LEN * 8 };
97
98typedef ib_uint64_t bitmap_word_t;
99
100/****************************************************************//**
101Calculate a bitmap block checksum. Algorithm borrowed from
102log_block_calc_checksum.
103@return checksum */
104UNIV_INLINE
105ulint
106log_online_calc_checksum(
107/*=====================*/
108 const byte* block); /*!<in: bitmap block */
109
110/****************************************************************//**
111Provide a comparisson function for the RB-tree tree (space,
112block_start_page) pairs. Actual implementation does not matter as
113long as the ordering is full.
114@return -1 if p1 < p2, 0 if p1 == p2, 1 if p1 > p2
115*/
116static
117int
118log_online_compare_bmp_keys(
119/*========================*/
120 const void* p1, /*!<in: 1st key to compare */
121 const void* p2) /*!<in: 2nd key to compare */
122{
123 const byte *k1 = (const byte *)p1;
124 const byte *k2 = (const byte *)p2;
125
126 ulint k1_space = mach_read_from_4(k1 + MODIFIED_PAGE_SPACE_ID);
127 ulint k2_space = mach_read_from_4(k2 + MODIFIED_PAGE_SPACE_ID);
128 if (k1_space == k2_space) {
129
130 ulint k1_start_page
131 = mach_read_from_4(k1 + MODIFIED_PAGE_1ST_PAGE_ID);
132 ulint k2_start_page
133 = mach_read_from_4(k2 + MODIFIED_PAGE_1ST_PAGE_ID);
134 return k1_start_page < k2_start_page
135 ? -1 : k1_start_page > k2_start_page ? 1 : 0;
136 }
137 return k1_space < k2_space ? -1 : 1;
138}
139
140/****************************************************************//**
141Calculate a bitmap block checksum. Algorithm borrowed from
142log_block_calc_checksum.
143@return checksum */
144UNIV_INLINE
145ulint
146log_online_calc_checksum(
147/*=====================*/
148 const byte* block) /*!<in: bitmap block */
149{
150 ulint sum;
151 ulint sh;
152 ulint i;
153
154 sum = 1;
155 sh = 0;
156
157 for (i = 0; i < MODIFIED_PAGE_BLOCK_CHECKSUM; i++) {
158
159 ulint b = block[i];
160 sum &= 0x7FFFFFFFUL;
161 sum += b;
162 sum += b << sh;
163 sh++;
164 if (sh > 24) {
165
166 sh = 0;
167 }
168 }
169
170 return sum;
171}
172
173/****************************************************************//**
174Read one bitmap data page and check it for corruption.
175
176@return TRUE if page read OK, FALSE if I/O error */
177static
178ibool
179log_online_read_bitmap_page(
180/*========================*/
181 log_online_bitmap_file_t *bitmap_file, /*!<in/out: bitmap
182 file */
183 byte *page, /*!<out: read page. Must be at
184 least MODIFIED_PAGE_BLOCK_SIZE
185 bytes long */
186 ibool *checksum_ok) /*!<out: TRUE if page
187 checksum OK */
188{
189 ulint checksum;
190 ulint actual_checksum;
191 ibool success;
192
193 ut_a(bitmap_file->size >= MODIFIED_PAGE_BLOCK_SIZE);
194 ut_a(bitmap_file->offset
195 <= bitmap_file->size - MODIFIED_PAGE_BLOCK_SIZE);
196 ut_a(bitmap_file->offset % MODIFIED_PAGE_BLOCK_SIZE == 0);
197 success = os_file_read(IORequestRead,
198 bitmap_file->file, page, bitmap_file->offset,
199 MODIFIED_PAGE_BLOCK_SIZE);
200
201 if (UNIV_UNLIKELY(!success)) {
202
203 /* The following call prints an error message */
204 os_file_get_last_error(TRUE);
205 msg("InnoDB: Warning: failed reading changed page bitmap "
206 "file \'%s\'\n", bitmap_file->name);
207 return FALSE;
208 }
209
210 bitmap_file->offset += MODIFIED_PAGE_BLOCK_SIZE;
211 ut_ad(bitmap_file->offset <= bitmap_file->size);
212
213 checksum = mach_read_from_4(page + MODIFIED_PAGE_BLOCK_CHECKSUM);
214 actual_checksum = log_online_calc_checksum(page);
215 *checksum_ok = (checksum == actual_checksum);
216
217 return TRUE;
218}
219
220/*********************************************************************//**
221Check the name of a given file if it's a changed page bitmap file and
222return file sequence and start LSN name components if it is. If is not,
223the values of output parameters are undefined.
224
225@return TRUE if a given file is a changed page bitmap file. */
226static
227ibool
228log_online_is_bitmap_file(
229/*======================*/
230 const os_file_stat_t* file_info, /*!<in: file to
231 check */
232 ulong* bitmap_file_seq_num, /*!<out: bitmap file
233 sequence number */
234 lsn_t* bitmap_file_start_lsn) /*!<out: bitmap file
235 start LSN */
236{
237 char stem[FN_REFLEN];
238
239 ut_ad (strlen(file_info->name) < OS_FILE_MAX_PATH);
240
241 return ((file_info->type == OS_FILE_TYPE_FILE
242 || file_info->type == OS_FILE_TYPE_LINK)
243 && (sscanf(file_info->name, "%[a-z_]%lu_" LSN_PF ".xdb", stem,
244 bitmap_file_seq_num, bitmap_file_start_lsn) == 3)
245 && (!strcmp(stem, bmp_file_name_stem)));
246}
247
248/*********************************************************************//**
249List the bitmap files in srv_data_home and setup their range that contains the
250specified LSN interval. This range, if non-empty, will start with a file that
251has the greatest LSN equal to or less than the start LSN and will include all
252the files up to the one with the greatest LSN less than the end LSN. Caller
253must free bitmap_files->files when done if bitmap_files set to non-NULL and
254this function returned TRUE. Field bitmap_files->count might be set to a
255larger value than the actual count of the files, and space for the unused array
256slots will be allocated but cleared to zeroes.
257
258@return TRUE if succeeded
259*/
260static
261ibool
262log_online_setup_bitmap_file_range(
263/*===============================*/
264 log_online_bitmap_file_range_t *bitmap_files, /*!<in/out: bitmap file
265 range */
266 lsn_t range_start, /*!<in: start LSN */
267 lsn_t range_end) /*!<in: end LSN */
268{
269 os_file_dir_t bitmap_dir;
270 os_file_stat_t bitmap_dir_file_info;
271 ulong first_file_seq_num = ULONG_MAX;
272 ulong last_file_seq_num = 0;
273 lsn_t first_file_start_lsn = LSN_MAX;
274
275 xb_ad(range_end >= range_start);
276
277 bitmap_files->count = 0;
278 bitmap_files->files = NULL;
279
280 /* 1st pass: size the info array */
281
282 bitmap_dir = os_file_opendir(srv_data_home, FALSE);
283 if (UNIV_UNLIKELY(!bitmap_dir)) {
284
285 msg("InnoDB: Error: failed to open bitmap directory \'%s\'\n",
286 srv_data_home);
287 return FALSE;
288 }
289
290 while (!os_file_readdir_next_file(srv_data_home, bitmap_dir,
291 &bitmap_dir_file_info)) {
292
293 ulong file_seq_num;
294 lsn_t file_start_lsn;
295
296 if (!log_online_is_bitmap_file(&bitmap_dir_file_info,
297 &file_seq_num,
298 &file_start_lsn)
299 || file_start_lsn >= range_end) {
300
301 continue;
302 }
303
304 if (file_seq_num > last_file_seq_num) {
305
306 last_file_seq_num = file_seq_num;
307 }
308
309 if (file_start_lsn >= range_start
310 || file_start_lsn == first_file_start_lsn
311 || first_file_start_lsn > range_start) {
312
313 /* A file that falls into the range */
314
315 if (file_start_lsn < first_file_start_lsn) {
316
317 first_file_start_lsn = file_start_lsn;
318 }
319 if (file_seq_num < first_file_seq_num) {
320
321 first_file_seq_num = file_seq_num;
322 }
323 } else if (file_start_lsn > first_file_start_lsn) {
324
325 /* A file that has LSN closer to the range start
326 but smaller than it, replacing another such file */
327 first_file_start_lsn = file_start_lsn;
328 first_file_seq_num = file_seq_num;
329 }
330 }
331
332 if (UNIV_UNLIKELY(os_file_closedir(bitmap_dir))) {
333
334 os_file_get_last_error(TRUE);
335 msg("InnoDB: Error: cannot close \'%s\'\n",srv_data_home);
336 return FALSE;
337 }
338
339 if (first_file_seq_num == ULONG_MAX && last_file_seq_num == 0) {
340
341 bitmap_files->count = 0;
342 return TRUE;
343 }
344
345 bitmap_files->count = last_file_seq_num - first_file_seq_num + 1;
346
347 /* 2nd pass: get the file names in the file_seq_num order */
348
349 bitmap_dir = os_file_opendir(srv_data_home, FALSE);
350 if (UNIV_UNLIKELY(!bitmap_dir)) {
351
352 msg("InnoDB: Error: failed to open bitmap directory \'%s\'\n",
353 srv_data_home);
354 return FALSE;
355 }
356
357 bitmap_files->files =
358 static_cast<log_online_bitmap_file_range_t::files_t *>
359 (malloc(bitmap_files->count * sizeof(bitmap_files->files[0])));
360 memset(bitmap_files->files, 0,
361 bitmap_files->count * sizeof(bitmap_files->files[0]));
362
363 while (!os_file_readdir_next_file(srv_data_home, bitmap_dir,
364 &bitmap_dir_file_info)) {
365
366 ulong file_seq_num;
367 lsn_t file_start_lsn;
368 size_t array_pos;
369
370 if (!log_online_is_bitmap_file(&bitmap_dir_file_info,
371 &file_seq_num,
372 &file_start_lsn)
373 || file_start_lsn >= range_end
374 || file_start_lsn < first_file_start_lsn) {
375
376 continue;
377 }
378
379 array_pos = file_seq_num - first_file_seq_num;
380 if (UNIV_UNLIKELY(array_pos >= bitmap_files->count)) {
381
382 msg("InnoDB: Error: inconsistent bitmap file "
383 "directory\n");
384 free(bitmap_files->files);
385 return FALSE;
386 }
387
388 if (file_seq_num > bitmap_files->files[array_pos].seq_num) {
389
390 bitmap_files->files[array_pos].seq_num = file_seq_num;
391 strncpy(bitmap_files->files[array_pos].name,
392 bitmap_dir_file_info.name, FN_REFLEN);
393 bitmap_files->files[array_pos].name[FN_REFLEN - 1]
394 = '\0';
395 bitmap_files->files[array_pos].start_lsn
396 = file_start_lsn;
397 }
398 }
399
400 if (UNIV_UNLIKELY(os_file_closedir(bitmap_dir))) {
401
402 os_file_get_last_error(TRUE);
403 msg("InnoDB: Error: cannot close \'%s\'\n", srv_data_home);
404 free(bitmap_files->files);
405 return FALSE;
406 }
407
408#ifdef UNIV_DEBUG
409 ut_ad(bitmap_files->files[0].seq_num == first_file_seq_num);
410
411 for (size_t i = 1; i < bitmap_files->count; i++) {
412 if (!bitmap_files->files[i].seq_num) {
413
414 break;
415 }
416 ut_ad(bitmap_files->files[i].seq_num
417 > bitmap_files->files[i - 1].seq_num);
418 ut_ad(bitmap_files->files[i].start_lsn
419 >= bitmap_files->files[i - 1].start_lsn);
420 }
421#endif
422
423 return TRUE;
424}
425
426/****************************************************************//**
427Open a bitmap file for reading.
428
429@return whether opened successfully */
430static
431bool
432log_online_open_bitmap_file_read_only(
433/*==================================*/
434 const char* name, /*!<in: bitmap file
435 name without directory,
436 which is assumed to be
437 srv_data_home */
438 log_online_bitmap_file_t* bitmap_file) /*!<out: opened bitmap
439 file */
440{
441 bool success = false;
442
443 xb_ad(name[0] != '\0');
444
445 snprintf(bitmap_file->name, FN_REFLEN, "%s%s", srv_data_home, name);
446 bitmap_file->file = os_file_create_simple_no_error_handling(
447 0, bitmap_file->name,
448 OS_FILE_OPEN, OS_FILE_READ_ONLY, true, &success);
449 if (UNIV_UNLIKELY(!success)) {
450
451 /* Here and below assume that bitmap file names do not
452 contain apostrophes, thus no need for ut_print_filename(). */
453 msg("InnoDB: Warning: error opening the changed page "
454 "bitmap \'%s\'\n", bitmap_file->name);
455 return success;
456 }
457
458 bitmap_file->size = os_file_get_size(bitmap_file->file);
459 bitmap_file->offset = 0;
460
461#ifdef UNIV_LINUX
462 posix_fadvise(bitmap_file->file, 0, 0, POSIX_FADV_SEQUENTIAL);
463 posix_fadvise(bitmap_file->file, 0, 0, POSIX_FADV_NOREUSE);
464#endif
465
466 return success;
467}
468
469/****************************************************************//**
470Diagnose one or both of the following situations if we read close to
471the end of bitmap file:
4721) Warn if the remainder of the file is less than one page.
4732) Error if we cannot read any more full pages but the last read page
474did not have the last-in-run flag set.
475
476@return FALSE for the error */
477static
478ibool
479log_online_diagnose_bitmap_eof(
480/*===========================*/
481 const log_online_bitmap_file_t* bitmap_file, /*!< in: bitmap file */
482 ibool last_page_in_run)/*!< in: "last page in
483 run" flag value in the
484 last read page */
485{
486 /* Check if we are too close to EOF to read a full page */
487 if ((bitmap_file->size < MODIFIED_PAGE_BLOCK_SIZE)
488 || (bitmap_file->offset
489 > bitmap_file->size - MODIFIED_PAGE_BLOCK_SIZE)) {
490
491 if (UNIV_UNLIKELY(bitmap_file->offset != bitmap_file->size)) {
492
493 /* If we are not at EOF and we have less than one page
494 to read, it's junk. This error is not fatal in
495 itself. */
496
497 msg("InnoDB: Warning: junk at the end of changed "
498 "page bitmap file \'%s\'.\n", bitmap_file->name);
499 }
500
501 if (UNIV_UNLIKELY(!last_page_in_run)) {
502
503 /* We are at EOF but the last read page did not finish
504 a run */
505 /* It's a "Warning" here because it's not a fatal error
506 for the whole server */
507 msg("InnoDB: Warning: changed page bitmap "
508 "file \'%s\' does not contain a complete run "
509 "at the end.\n", bitmap_file->name);
510 return FALSE;
511 }
512 }
513 return TRUE;
514}
515
516/* End of copy-pasted definitions */
517
518/** Iterator structure over changed page bitmap */
519struct xb_page_bitmap_range_struct {
520 const xb_page_bitmap *bitmap; /* Bitmap with data */
521 ulint space_id; /* Space id for this
522 iterator */
523 ulint bit_i; /* Bit index of the iterator
524 position in the current page */
525 const ib_rbt_node_t *bitmap_node; /* Current bitmap tree node */
526 const byte *bitmap_page; /* Current bitmap page */
527 ulint current_page_id;/* Current page id */
528};
529
530/****************************************************************//**
531Print a diagnostic message on missing bitmap data for an LSN range. */
532static
533void
534xb_msg_missing_lsn_data(
535/*====================*/
536 lsn_t missing_interval_start, /*!<in: interval start */
537 lsn_t missing_interval_end) /*!<in: interval end */
538{
539 msg("mariabackup: warning: changed page data missing for LSNs between "
540 LSN_PF " and " LSN_PF "\n", missing_interval_start,
541 missing_interval_end);
542}
543
544/****************************************************************//**
545Scan a bitmap file until data for a desired LSN or EOF is found and check that
546the page before the starting one is not corrupted to ensure that the found page
547indeed contains the very start of the desired LSN data. The caller must check
548the page LSN values to determine if the bitmap file was scanned until the data
549was found or until EOF. Page must be at least MODIFIED_PAGE_BLOCK_SIZE big.
550
551@return TRUE if the scan successful without corruption detected
552*/
553static
554ibool
555xb_find_lsn_in_bitmap_file(
556/*=======================*/
557 log_online_bitmap_file_t *bitmap_file, /*!<in/out: bitmap
558 file */
559 byte *page, /*!<in/out: last read
560 bitmap page */
561 lsn_t *page_end_lsn, /*!<out: end LSN of the
562 last read page */
563 lsn_t lsn) /*!<in: LSN to find */
564{
565 ibool last_page_ok = TRUE;
566 ibool next_to_last_page_ok = TRUE;
567
568 xb_ad (bitmap_file->size >= MODIFIED_PAGE_BLOCK_SIZE);
569
570 *page_end_lsn = 0;
571
572 while ((*page_end_lsn <= lsn)
573 && (bitmap_file->offset
574 <= bitmap_file->size - MODIFIED_PAGE_BLOCK_SIZE)) {
575
576 next_to_last_page_ok = last_page_ok;
577 if (!log_online_read_bitmap_page(bitmap_file, page,
578 &last_page_ok)) {
579
580 return FALSE;
581 }
582
583 *page_end_lsn = mach_read_from_8(page + MODIFIED_PAGE_END_LSN);
584 }
585
586 /* We check two pages here because the last read page already contains
587 the required LSN data. If the next to the last one page is corrupted,
588 then we have no way of telling if that page contained the required LSN
589 range data too */
590 return last_page_ok && next_to_last_page_ok;
591}
592
593/****************************************************************//**
594Read the disk bitmap and build the changed page bitmap tree for the
595LSN interval incremental_lsn to checkpoint_lsn_start.
596
597@return the built bitmap tree or NULL if unable to read the full interval for
598any reason. */
599xb_page_bitmap*
600xb_page_bitmap_init(void)
601/*=====================*/
602{
603 log_online_bitmap_file_t bitmap_file;
604 lsn_t bmp_start_lsn = incremental_lsn;
605 lsn_t bmp_end_lsn = checkpoint_lsn_start;
606 byte page[MODIFIED_PAGE_BLOCK_SIZE];
607 lsn_t current_page_end_lsn;
608 xb_page_bitmap *result;
609 ibool last_page_in_run= FALSE;
610 log_online_bitmap_file_range_t bitmap_files;
611 size_t bmp_i;
612 ibool last_page_ok = TRUE;
613
614 if (UNIV_UNLIKELY(bmp_start_lsn > bmp_end_lsn)) {
615
616 msg("mariabackup: incremental backup LSN " LSN_PF
617 " is larger than than the last checkpoint LSN " LSN_PF
618 "\n", bmp_start_lsn, bmp_end_lsn);
619 return NULL;
620 }
621
622 if (!log_online_setup_bitmap_file_range(&bitmap_files, bmp_start_lsn,
623 bmp_end_lsn)) {
624
625 return NULL;
626 }
627
628 /* Only accept no bitmap files returned if start LSN == end LSN */
629 if (bitmap_files.count == 0 && bmp_end_lsn != bmp_start_lsn) {
630
631 return NULL;
632 }
633
634 result = rbt_create(MODIFIED_PAGE_BLOCK_SIZE,
635 log_online_compare_bmp_keys);
636
637 if (bmp_start_lsn == bmp_end_lsn) {
638
639 /* Empty range - empty bitmap */
640 return result;
641 }
642
643 bmp_i = 0;
644
645 if (UNIV_UNLIKELY(bitmap_files.files[bmp_i].start_lsn
646 > bmp_start_lsn)) {
647
648 /* The 1st file does not have the starting LSN data */
649 xb_msg_missing_lsn_data(bmp_start_lsn,
650 bitmap_files.files[bmp_i].start_lsn);
651 rbt_free(result);
652 free(bitmap_files.files);
653 return NULL;
654 }
655
656 /* Skip any zero-sized files at the start */
657 while ((bmp_i < bitmap_files.count - 1)
658 && (bitmap_files.files[bmp_i].start_lsn
659 == bitmap_files.files[bmp_i + 1].start_lsn)) {
660
661 bmp_i++;
662 }
663
664 /* Is the 1st bitmap file missing? */
665 if (UNIV_UNLIKELY(bitmap_files.files[bmp_i].name[0] == '\0')) {
666
667 /* TODO: this is not the exact missing range */
668 xb_msg_missing_lsn_data(bmp_start_lsn, bmp_end_lsn);
669 rbt_free(result);
670 free(bitmap_files.files);
671 return NULL;
672 }
673
674 /* Open the 1st bitmap file */
675 if (UNIV_UNLIKELY(!log_online_open_bitmap_file_read_only(
676 bitmap_files.files[bmp_i].name,
677 &bitmap_file))) {
678
679 rbt_free(result);
680 free(bitmap_files.files);
681 return NULL;
682 }
683
684 /* If the 1st file is truncated, no data. Not merged with the case
685 below because zero-length file indicates not a corruption but missing
686 subsequent files instead. */
687 if (UNIV_UNLIKELY(bitmap_file.size < MODIFIED_PAGE_BLOCK_SIZE)) {
688
689 xb_msg_missing_lsn_data(bmp_start_lsn, bmp_end_lsn);
690 rbt_free(result);
691 free(bitmap_files.files);
692 os_file_close(bitmap_file.file);
693 return NULL;
694 }
695
696 /* Find the start of the required LSN range in the file */
697 if (UNIV_UNLIKELY(!xb_find_lsn_in_bitmap_file(&bitmap_file, page,
698 &current_page_end_lsn,
699 bmp_start_lsn))) {
700
701 msg("mariabackup: Warning: changed page bitmap file "
702 "\'%s\' corrupted\n", bitmap_file.name);
703 rbt_free(result);
704 free(bitmap_files.files);
705 os_file_close(bitmap_file.file);
706 return NULL;
707 }
708
709 last_page_in_run
710 = mach_read_from_4(page + MODIFIED_PAGE_IS_LAST_BLOCK);
711
712 if (UNIV_UNLIKELY(!log_online_diagnose_bitmap_eof(&bitmap_file,
713 last_page_in_run))) {
714
715 rbt_free(result);
716 free(bitmap_files.files);
717 os_file_close(bitmap_file.file);
718 return NULL;
719 }
720
721 if (UNIV_UNLIKELY(current_page_end_lsn < bmp_start_lsn)) {
722
723 xb_msg_missing_lsn_data(current_page_end_lsn, bmp_start_lsn);
724 rbt_free(result);
725 free(bitmap_files.files);
726 os_file_close(bitmap_file.file);
727 return NULL;
728 }
729
730 /* 1st bitmap page found, add it to the tree. */
731 rbt_insert(result, page, page);
732
733 /* Read next pages/files until all required data is read */
734 while (last_page_ok
735 && (current_page_end_lsn < bmp_end_lsn
736 || (current_page_end_lsn == bmp_end_lsn
737 && !last_page_in_run))) {
738
739 ib_rbt_bound_t tree_search_pos;
740
741 /* If EOF, advance the file skipping over any empty files */
742 while (bitmap_file.size < MODIFIED_PAGE_BLOCK_SIZE
743 || (bitmap_file.offset
744 > bitmap_file.size - MODIFIED_PAGE_BLOCK_SIZE)) {
745
746 os_file_close(bitmap_file.file);
747
748 if (UNIV_UNLIKELY(
749 !log_online_diagnose_bitmap_eof(
750 &bitmap_file, last_page_in_run))) {
751
752 rbt_free(result);
753 free(bitmap_files.files);
754 return NULL;
755 }
756
757 bmp_i++;
758
759 if (UNIV_UNLIKELY(bmp_i == bitmap_files.count
760 || (bitmap_files.files[bmp_i].seq_num
761 == 0))) {
762
763 xb_msg_missing_lsn_data(current_page_end_lsn,
764 bmp_end_lsn);
765 rbt_free(result);
766 free(bitmap_files.files);
767 return NULL;
768 }
769
770 /* Is the next file missing? */
771 if (UNIV_UNLIKELY(bitmap_files.files[bmp_i].name[0]
772 == '\0')) {
773
774 /* TODO: this is not the exact missing range */
775 xb_msg_missing_lsn_data(bitmap_files.files
776 [bmp_i - 1].start_lsn,
777 bmp_end_lsn);
778 rbt_free(result);
779 free(bitmap_files.files);
780 return NULL;
781 }
782
783 if (UNIV_UNLIKELY(
784 !log_online_open_bitmap_file_read_only(
785 bitmap_files.files[bmp_i].name,
786 &bitmap_file))) {
787
788 rbt_free(result);
789 free(bitmap_files.files);
790 return NULL;
791 }
792 }
793
794 if (UNIV_UNLIKELY(
795 !log_online_read_bitmap_page(&bitmap_file, page,
796 &last_page_ok))) {
797
798 rbt_free(result);
799 free(bitmap_files.files);
800 os_file_close(bitmap_file.file);
801 return NULL;
802 }
803
804 if (UNIV_UNLIKELY(!last_page_ok)) {
805
806 msg("mariabackup: warning: changed page bitmap file "
807 "\'%s\' corrupted.\n", bitmap_file.name);
808 rbt_free(result);
809 free(bitmap_files.files);
810 os_file_close(bitmap_file.file);
811 return NULL;
812 }
813
814 /* Merge the current page with an existing page or insert a new
815 page into the tree */
816
817 if (!rbt_search(result, &tree_search_pos, page)) {
818
819 /* Merge the bitmap pages */
820 byte *existing_page
821 = rbt_value(byte, tree_search_pos.last);
822 bitmap_word_t *bmp_word_1 = (bitmap_word_t *)
823 (existing_page + MODIFIED_PAGE_BLOCK_BITMAP);
824 bitmap_word_t *bmp_end = (bitmap_word_t *)
825 (existing_page + MODIFIED_PAGE_BLOCK_UNUSED_2);
826 bitmap_word_t *bmp_word_2 = (bitmap_word_t *)
827 (page + MODIFIED_PAGE_BLOCK_BITMAP);
828 while (bmp_word_1 < bmp_end) {
829
830 *bmp_word_1++ |= *bmp_word_2++;
831 }
832 xb_a (bmp_word_1 == bmp_end);
833 } else {
834
835 /* Add a new page */
836 rbt_add_node(result, &tree_search_pos, page);
837 }
838
839 current_page_end_lsn
840 = mach_read_from_8(page + MODIFIED_PAGE_END_LSN);
841 last_page_in_run
842 = mach_read_from_4(page + MODIFIED_PAGE_IS_LAST_BLOCK);
843 }
844
845 xb_a (current_page_end_lsn >= bmp_end_lsn);
846
847 free(bitmap_files.files);
848 os_file_close(bitmap_file.file);
849
850 return result;
851}
852
853/****************************************************************//**
854Free the bitmap tree. */
855void
856xb_page_bitmap_deinit(
857/*==================*/
858 xb_page_bitmap* bitmap) /*!<in/out: bitmap tree */
859{
860 if (bitmap) {
861
862 rbt_free(bitmap);
863 }
864}
865
866/****************************************************************//**
867Advance to the next bitmap page or setup the first bitmap page for the
868given bitmap range. Assumes that bitmap_range->bitmap_page has been
869already found/bumped by rbt_search()/rbt_next().
870
871@return FALSE if no more bitmap data for the range space ID */
872static
873ibool
874xb_page_bitmap_setup_next_page(
875/*===========================*/
876 xb_page_bitmap_range* bitmap_range) /*!<in/out: the bitmap range */
877{
878 ulint new_space_id;
879 ulint new_1st_page_id;
880
881 if (bitmap_range->bitmap_node == NULL) {
882
883 bitmap_range->current_page_id = ULINT_UNDEFINED;
884 return FALSE;
885 }
886
887 bitmap_range->bitmap_page = rbt_value(byte, bitmap_range->bitmap_node);
888
889 new_space_id = mach_read_from_4(bitmap_range->bitmap_page
890 + MODIFIED_PAGE_SPACE_ID);
891 if (new_space_id != bitmap_range->space_id) {
892
893 /* No more data for the current page id. */
894 xb_a(new_space_id > bitmap_range->space_id);
895 bitmap_range->current_page_id = ULINT_UNDEFINED;
896 return FALSE;
897 }
898
899 new_1st_page_id = mach_read_from_4(bitmap_range->bitmap_page +
900 MODIFIED_PAGE_1ST_PAGE_ID);
901 xb_a (new_1st_page_id >= bitmap_range->current_page_id
902 || bitmap_range->current_page_id == ULINT_UNDEFINED);
903
904 bitmap_range->current_page_id = new_1st_page_id;
905 bitmap_range->bit_i = 0;
906
907 return TRUE;
908}
909
910/** Find the node with the smallest key that greater than equal to search key.
911@param[in] tree red-black tree
912@param[in] key search key
913@return node with the smallest greater-than-or-equal key
914@retval NULL if none was found */
915static
916const ib_rbt_node_t*
917rbt_lower_bound(const ib_rbt_t* tree, const void* key)
918{
919 ut_ad(!tree->cmp_arg);
920 const ib_rbt_node_t* ge = NULL;
921
922 for (const ib_rbt_node_t *node = tree->root->left;
923 node != tree->nil; ) {
924 int result = tree->compare(node->value, key);
925
926 if (result < 0) {
927 node = node->right;
928 } else {
929 ge = node;
930 if (result == 0) {
931 break;
932 }
933
934 node = node->left;
935 }
936 }
937
938 return(ge);
939}
940
941/****************************************************************//**
942Set up a new bitmap range iterator over a given space id changed
943pages in a given bitmap.
944
945@return bitmap range iterator */
946xb_page_bitmap_range*
947xb_page_bitmap_range_init(
948/*======================*/
949 xb_page_bitmap* bitmap, /*!< in: bitmap to iterate over */
950 ulint space_id) /*!< in: space id */
951{
952 byte search_page[MODIFIED_PAGE_BLOCK_SIZE];
953 xb_page_bitmap_range *result
954 = static_cast<xb_page_bitmap_range *>(malloc(sizeof(*result)));
955
956 memset(result, 0, sizeof(*result));
957 result->bitmap = bitmap;
958 result->space_id = space_id;
959 result->current_page_id = ULINT_UNDEFINED;
960
961 /* Search for the 1st page for the given space id */
962 /* This also sets MODIFIED_PAGE_1ST_PAGE_ID to 0, which is what we
963 want. */
964 memset(search_page, 0, MODIFIED_PAGE_BLOCK_SIZE);
965 mach_write_to_4(search_page + MODIFIED_PAGE_SPACE_ID, space_id);
966
967 result->bitmap_node = rbt_lower_bound(result->bitmap, search_page);
968
969 xb_page_bitmap_setup_next_page(result);
970
971 return result;
972}
973
974/****************************************************************//**
975Get the value of the bitmap->range->bit_i bitmap bit
976
977@return the current bit value */
978static inline
979ibool
980is_bit_set(
981/*=======*/
982 const xb_page_bitmap_range* bitmap_range) /*!< in: bitmap
983 range */
984{
985 return ((*(((bitmap_word_t *)(bitmap_range->bitmap_page
986 + MODIFIED_PAGE_BLOCK_BITMAP))
987 + (bitmap_range->bit_i >> 6)))
988 & (1ULL << (bitmap_range->bit_i & 0x3F))) ? TRUE : FALSE;
989}
990
991/****************************************************************//**
992Get the next page id that has its bit set or cleared, i.e. equal to
993bit_value.
994
995@return page id */
996ulint
997xb_page_bitmap_range_get_next_bit(
998/*==============================*/
999 xb_page_bitmap_range* bitmap_range, /*!< in/out: bitmap range */
1000 ibool bit_value) /*!< in: bit value */
1001{
1002 if (UNIV_UNLIKELY(bitmap_range->current_page_id
1003 == ULINT_UNDEFINED)) {
1004
1005 return ULINT_UNDEFINED;
1006 }
1007
1008 do {
1009 while (bitmap_range->bit_i < MODIFIED_PAGE_BLOCK_ID_COUNT) {
1010
1011 while (is_bit_set(bitmap_range) != bit_value
1012 && (bitmap_range->bit_i
1013 < MODIFIED_PAGE_BLOCK_ID_COUNT)) {
1014
1015 bitmap_range->current_page_id++;
1016 bitmap_range->bit_i++;
1017 }
1018
1019 if (bitmap_range->bit_i
1020 < MODIFIED_PAGE_BLOCK_ID_COUNT) {
1021
1022 ulint result = bitmap_range->current_page_id;
1023 bitmap_range->current_page_id++;
1024 bitmap_range->bit_i++;
1025 return result;
1026 }
1027 }
1028
1029 bitmap_range->bitmap_node
1030 = rbt_next(bitmap_range->bitmap,
1031 bitmap_range->bitmap_node);
1032
1033 } while (xb_page_bitmap_setup_next_page(bitmap_range));
1034
1035 return ULINT_UNDEFINED;
1036}
1037
1038/****************************************************************//**
1039Free the bitmap range iterator. */
1040void
1041xb_page_bitmap_range_deinit(
1042/*========================*/
1043 xb_page_bitmap_range* bitmap_range) /*! in/out: bitmap range */
1044{
1045 free(bitmap_range);
1046}
1047