1 /* 2 * Copyright (c) 2010 The DragonFly Project. All rights reserved. 3 * 4 * This code is derived from software contributed to The DragonFly Project 5 * by Matthew Dillon <dillon@backplane.com> 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * 3. Neither the name of The DragonFly Project nor the names of its 18 * contributors may be used to endorse or promote products derived 19 * from this software without specific, prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32 * SUCH DAMAGE. 33 */ 34 35 #include "hammer.h" 36 37 struct recover_dict { 38 struct recover_dict *next; 39 struct recover_dict *parent; 40 int64_t obj_id; 41 uint8_t obj_type; 42 uint8_t flags; 43 uint16_t pfs_id; 44 int64_t size; 45 char *name; 46 }; 47 48 #define DICTF_MADEDIR 0x01 49 #define DICTF_MADEFILE 0x02 50 #define DICTF_PARENT 0x04 /* parent attached for real */ 51 #define DICTF_TRAVERSED 0x80 52 53 static void recover_top(char *ptr, hammer_off_t offset); 54 static void recover_elm(hammer_btree_leaf_elm_t leaf); 55 static struct recover_dict *get_dict(int64_t obj_id, uint16_t pfs_id); 56 static char *recover_path(struct recover_dict *dict); 57 static void sanitize_string(char *str); 58 static hammer_off_t scan_raw_limit(void); 59 static void scan_bigblocks(int target_zone); 60 static void free_bigblocks(void); 61 static void add_bigblock_entry(hammer_off_t offset); 62 static int test_bigblock_entry(hammer_off_t offset); 63 64 static const char *TargetDir; 65 static int CachedFd = -1; 66 static char *CachedPath; 67 68 typedef struct bigblock { 69 RB_ENTRY(bigblock) entry; 70 hammer_off_t phys_offset; /* zone-2 */ 71 } *bigblock_t; 72 73 static int 74 bigblock_cmp(bigblock_t b1, bigblock_t b2) 75 { 76 if (b1->phys_offset < b2->phys_offset) 77 return(-1); 78 if (b1->phys_offset > b2->phys_offset) 79 return(1); 80 return(0); 81 } 82 83 RB_HEAD(bigblock_rb_tree, bigblock) ZoneTree = RB_INITIALIZER(&ZoneTree); 84 RB_PROTOTYPE2(bigblock_rb_tree, bigblock, entry, bigblock_cmp, hammer_off_t); 85 RB_GENERATE2(bigblock_rb_tree, bigblock, entry, bigblock_cmp, hammer_off_t, 86 phys_offset); 87 88 /* 89 * XXX There is a hidden bug here while iterating zone-2 offset as 90 * shown in an example below. 91 * 92 * If a volume was once used as HAMMER filesystem which consists of 93 * multiple volumes whose usage has reached beyond the first volume, 94 * and then later re-formatted only using 1 volume, hammer recover is 95 * likely to hit assertion in get_buffer() due to having access to 96 * invalid volume (vol1,2,...) from old filesystem data. 97 * 98 * To avoid this, now the command only scans upto the last big-block 99 * that's actually used for filesystem data or meta-data at the moment, 100 * if all layer1/2 entries have correct CRC values. This also avoids 101 * recovery of irrelevant files from old filesystem. 102 * 103 * |-----vol0-----|-----vol1-----|-----vol2-----| old filesystem 104 * <-----------------------> used by old filesystem 105 * 106 * |-----vol0-----| new filesystem 107 * <-----> used by new filesystem 108 * <-------> unused, invalid data from old filesystem 109 * <-> B-Tree nodes likely to point to vol1 110 */ 111 112 void 113 hammer_cmd_recover(char **av, int ac) 114 { 115 struct buffer_info *data_buffer; 116 struct volume_info *volume; 117 bigblock_t b; 118 hammer_off_t off; 119 hammer_off_t off_end; 120 hammer_off_t raw_limit = 0; 121 hammer_off_t zone_limit = 0; 122 char *ptr; 123 int i; 124 int target_zone = HAMMER_ZONE_BTREE_INDEX; 125 int full = 0; 126 int quick = 0; 127 128 if (ac < 1) { 129 fprintf(stderr, "hammer recover <target_dir> [full|quick]\n"); 130 exit(1); 131 } 132 133 TargetDir = av[0]; 134 if (ac > 1) { 135 if (!strcmp(av[1], "full")) 136 full = 1; 137 if (!strcmp(av[1], "quick")) 138 quick = 1; 139 } 140 assert(!full || !quick); 141 142 if (mkdir(TargetDir, 0777) == -1) { 143 if (errno != EEXIST) { 144 perror("mkdir"); 145 exit(1); 146 } 147 } 148 149 printf("Running %sraw scan of HAMMER image, recovering to %s\n", 150 full ? "full " : quick ? "quick " : "", 151 TargetDir); 152 153 if (!full) { 154 raw_limit = scan_raw_limit(); 155 if (raw_limit) { 156 raw_limit += HAMMER_BIGBLOCK_SIZE; 157 assert(hammer_is_zone_raw_buffer(raw_limit)); 158 } 159 } 160 161 if (quick) { 162 scan_bigblocks(target_zone); 163 if (!RB_EMPTY(&ZoneTree)) { 164 printf("Found zone-%d big-blocks at\n", target_zone); 165 RB_FOREACH(b, bigblock_rb_tree, &ZoneTree) 166 printf("%016jx\n", b->phys_offset); 167 168 b = RB_MAX(bigblock_rb_tree, &ZoneTree); 169 zone_limit = b->phys_offset + HAMMER_BIGBLOCK_SIZE; 170 assert(hammer_is_zone_raw_buffer(zone_limit)); 171 } 172 } 173 174 if (raw_limit || zone_limit) { 175 #define _fmt "Scanning zone-%d big-blocks till %016jx" 176 if (!raw_limit) /* unlikely */ 177 printf(_fmt" ???", target_zone, zone_limit); 178 else if (!zone_limit) 179 printf(_fmt, HAMMER_ZONE_RAW_BUFFER_INDEX, raw_limit); 180 else if (raw_limit >= zone_limit) 181 printf(_fmt, target_zone, zone_limit); 182 else /* unlikely */ 183 printf(_fmt" ???", HAMMER_ZONE_RAW_BUFFER_INDEX, raw_limit); 184 printf("\n"); 185 } 186 187 data_buffer = NULL; 188 for (i = 0; i < HAMMER_MAX_VOLUMES; i++) { 189 volume = get_volume(i); 190 if (volume == NULL) 191 continue; 192 193 printf("Scanning volume %d size %s\n", 194 volume->vol_no, sizetostr(volume->size)); 195 off = HAMMER_ENCODE_RAW_BUFFER(volume->vol_no, 0); 196 off_end = off + HAMMER_VOL_BUF_SIZE(volume->ondisk); 197 198 while (off < off_end) { 199 if (raw_limit) { 200 if (off >= raw_limit) { 201 printf("Done %016jx\n", (uintmax_t)off); 202 goto end; 203 } 204 } 205 if (zone_limit) { 206 if (off >= zone_limit) { 207 printf("Done %016jx\n", (uintmax_t)off); 208 goto end; 209 } 210 if (!test_bigblock_entry(off)) { 211 off = HAMMER_ZONE_LAYER2_NEXT_OFFSET(off); 212 continue; 213 } 214 } 215 216 ptr = get_buffer_data(off, &data_buffer, 0); 217 if (ptr) 218 recover_top(ptr, off); 219 off += HAMMER_BUFSIZE; 220 } 221 } 222 end: 223 rel_buffer(data_buffer); 224 free_bigblocks(); 225 226 if (CachedPath) { 227 free(CachedPath); 228 close(CachedFd); 229 CachedPath = NULL; 230 CachedFd = -1; 231 } 232 } 233 234 static __inline 235 void 236 print_node(hammer_node_ondisk_t node, hammer_off_t offset) 237 { 238 char buf[HAMMER_BTREE_LEAF_ELMS + 1]; 239 int maxcount = hammer_node_max_elements(node->type); 240 int i; 241 242 for (i = 0; i < node->count && i < maxcount; ++i) 243 buf[i] = hammer_elm_btype(&node->elms[i]); 244 buf[i] = '\0'; 245 246 printf("%016jx %c %d %s\n", offset, node->type, node->count, buf); 247 } 248 249 /* 250 * Top level recovery processor. Assume the data is a B-Tree node. 251 * If the CRC is good we attempt to process the node, building the 252 * object space and creating the dictionary as we go. 253 */ 254 static void 255 recover_top(char *ptr, hammer_off_t offset) 256 { 257 hammer_node_ondisk_t node; 258 hammer_btree_elm_t elm; 259 int maxcount; 260 int i; 261 int isnode; 262 263 for (node = (void *)ptr; (char *)node < ptr + HAMMER_BUFSIZE; ++node) { 264 isnode = hammer_crc_test_btree(node); 265 maxcount = hammer_node_max_elements(node->type); 266 267 if (DebugOpt) { 268 if (isnode) 269 print_node(node, offset); 270 else if (DebugOpt > 1) 271 printf("%016jx -\n", offset); 272 } 273 offset += sizeof(*node); 274 275 if (isnode && node->type == HAMMER_BTREE_TYPE_LEAF) { 276 for (i = 0; i < node->count && i < maxcount; ++i) { 277 elm = &node->elms[i]; 278 if (elm->base.btype == HAMMER_BTREE_TYPE_RECORD) 279 recover_elm(&elm->leaf); 280 } 281 } 282 } 283 } 284 285 static void 286 recover_elm(hammer_btree_leaf_elm_t leaf) 287 { 288 struct buffer_info *data_buffer = NULL; 289 struct recover_dict *dict; 290 struct recover_dict *dict2; 291 hammer_data_ondisk_t ondisk; 292 hammer_off_t data_offset; 293 struct stat st; 294 int chunk; 295 int len; 296 int zfill; 297 int64_t file_offset; 298 uint16_t pfs_id; 299 size_t nlen; 300 int fd; 301 char *name; 302 char *path1; 303 char *path2; 304 305 /* 306 * Ignore deleted records 307 */ 308 if (leaf->delete_ts) 309 return; 310 if ((data_offset = leaf->data_offset) != 0) 311 ondisk = get_buffer_data(data_offset, &data_buffer, 0); 312 else 313 ondisk = NULL; 314 if (ondisk == NULL) 315 goto done; 316 317 len = leaf->data_len; 318 chunk = HAMMER_BUFSIZE - ((int)data_offset & HAMMER_BUFMASK); 319 if (chunk > len) 320 chunk = len; 321 322 if (len < 0 || len > HAMMER_XBUFSIZE || len > chunk) 323 goto done; 324 325 pfs_id = lo_to_pfs(leaf->base.localization); 326 327 /* 328 * Note that meaning of leaf->base.obj_id differs depending 329 * on record type. For a direntry, leaf->base.obj_id points 330 * to its parent inode that this entry is a part of, but not 331 * its corresponding inode. 332 */ 333 dict = get_dict(leaf->base.obj_id, pfs_id); 334 335 switch(leaf->base.rec_type) { 336 case HAMMER_RECTYPE_INODE: 337 /* 338 * We found an inode which also tells us where the file 339 * or directory is in the directory hierarchy. 340 */ 341 if (VerboseOpt) { 342 printf("inode %016jx:%05d found\n", 343 (uintmax_t)leaf->base.obj_id, pfs_id); 344 } 345 path1 = recover_path(dict); 346 347 /* 348 * Attach the inode to its parent. This isn't strictly 349 * necessary because the information is also in the 350 * directory entries, but if we do not find the directory 351 * entry this ensures that the files will still be 352 * reasonably well organized in their proper directories. 353 */ 354 if ((dict->flags & DICTF_PARENT) == 0 && 355 dict->obj_id != HAMMER_OBJID_ROOT && 356 ondisk->inode.parent_obj_id != 0) { 357 dict->flags |= DICTF_PARENT; 358 dict->parent = get_dict(ondisk->inode.parent_obj_id, 359 pfs_id); 360 if (dict->parent && 361 (dict->parent->flags & DICTF_MADEDIR) == 0) { 362 dict->parent->flags |= DICTF_MADEDIR; 363 path2 = recover_path(dict->parent); 364 printf("mkdir %s\n", path2); 365 mkdir(path2, 0777); 366 free(path2); 367 path2 = NULL; 368 } 369 } 370 if (dict->obj_type == 0) 371 dict->obj_type = ondisk->inode.obj_type; 372 dict->size = ondisk->inode.size; 373 path2 = recover_path(dict); 374 375 if (lstat(path1, &st) == 0) { 376 if (ondisk->inode.obj_type == HAMMER_OBJTYPE_REGFILE) { 377 truncate(path1, dict->size); 378 /* chmod(path1, 0666); */ 379 } 380 if (strcmp(path1, path2)) { 381 printf("Rename %s -> %s\n", path1, path2); 382 rename(path1, path2); 383 } 384 } else if (ondisk->inode.obj_type == HAMMER_OBJTYPE_REGFILE) { 385 printf("mkinode (file) %s\n", path2); 386 fd = open(path2, O_RDWR|O_CREAT, 0666); 387 if (fd > 0) 388 close(fd); 389 } else if (ondisk->inode.obj_type == HAMMER_OBJTYPE_DIRECTORY) { 390 printf("mkinode (dir) %s\n", path2); 391 mkdir(path2, 0777); 392 dict->flags |= DICTF_MADEDIR; 393 } 394 free(path1); 395 free(path2); 396 break; 397 case HAMMER_RECTYPE_DATA: 398 /* 399 * File record data 400 */ 401 if (leaf->base.obj_id == 0) 402 break; 403 if (VerboseOpt) { 404 printf("inode %016jx:%05d data %016jx,%d\n", 405 (uintmax_t)leaf->base.obj_id, 406 pfs_id, 407 (uintmax_t)leaf->base.key - len, 408 len); 409 } 410 411 /* 412 * Update the dictionary entry 413 */ 414 if (dict->obj_type == 0) 415 dict->obj_type = HAMMER_OBJTYPE_REGFILE; 416 417 /* 418 * If the parent directory has not been created we 419 * have to create it (typically a PFS%05d) 420 */ 421 if (dict->parent && 422 (dict->parent->flags & DICTF_MADEDIR) == 0) { 423 dict->parent->flags |= DICTF_MADEDIR; 424 path2 = recover_path(dict->parent); 425 printf("mkdir %s\n", path2); 426 mkdir(path2, 0777); 427 free(path2); 428 path2 = NULL; 429 } 430 431 /* 432 * Create the file if necessary, report file creations 433 */ 434 path1 = recover_path(dict); 435 if (CachedPath && strcmp(CachedPath, path1) == 0) { 436 fd = CachedFd; 437 } else { 438 fd = open(path1, O_CREAT|O_RDWR, 0666); 439 } 440 if (fd < 0) { 441 printf("Unable to create %s: %s\n", 442 path1, strerror(errno)); 443 free(path1); 444 break; 445 } 446 if ((dict->flags & DICTF_MADEFILE) == 0) { 447 dict->flags |= DICTF_MADEFILE; 448 printf("mkfile %s\n", path1); 449 } 450 451 /* 452 * And write the record. A HAMMER data block is aligned 453 * and may contain trailing zeros after the file EOF. The 454 * inode record is required to get the actual file size. 455 * 456 * However, when the inode record is not available 457 * we can do a sparse write and that will get it right 458 * most of the time even if the inode record is never 459 * found. 460 */ 461 file_offset = (int64_t)leaf->base.key - len; 462 lseek(fd, (off_t)file_offset, SEEK_SET); 463 while (len) { 464 if (dict->size == -1) { 465 for (zfill = chunk - 1; zfill >= 0; --zfill) { 466 if (((char *)ondisk)[zfill]) 467 break; 468 } 469 ++zfill; 470 } else { 471 zfill = chunk; 472 } 473 474 if (zfill) 475 write(fd, ondisk, zfill); 476 if (zfill < chunk) 477 lseek(fd, chunk - zfill, SEEK_CUR); 478 479 len -= chunk; 480 data_offset += chunk; 481 file_offset += chunk; 482 ondisk = get_buffer_data(data_offset, &data_buffer, 0); 483 if (ondisk == NULL) 484 break; 485 chunk = HAMMER_BUFSIZE - 486 ((int)data_offset & HAMMER_BUFMASK); 487 if (chunk > len) 488 chunk = len; 489 } 490 if (dict->size >= 0 && file_offset > dict->size) { 491 ftruncate(fd, dict->size); 492 /* fchmod(fd, 0666); */ 493 } 494 495 if (fd == CachedFd) { 496 free(path1); 497 } else if (CachedPath) { 498 free(CachedPath); 499 close(CachedFd); 500 CachedPath = path1; 501 CachedFd = fd; 502 } else { 503 CachedPath = path1; 504 CachedFd = fd; 505 } 506 break; 507 case HAMMER_RECTYPE_DIRENTRY: 508 nlen = len - HAMMER_ENTRY_NAME_OFF; 509 if ((int)nlen < 0) /* illegal length */ 510 break; 511 if (ondisk->entry.obj_id == 0 || 512 ondisk->entry.obj_id == HAMMER_OBJID_ROOT) 513 break; 514 name = malloc(nlen + 1); 515 bcopy(ondisk->entry.name, name, nlen); 516 name[nlen] = 0; 517 sanitize_string(name); 518 519 if (VerboseOpt) { 520 printf("dir %016jx:%05d entry %016jx \"%s\"\n", 521 (uintmax_t)leaf->base.obj_id, 522 pfs_id, 523 (uintmax_t)ondisk->entry.obj_id, 524 name); 525 } 526 527 /* 528 * We can't deal with hardlinks so if the object already 529 * has a name assigned to it we just keep using that name. 530 */ 531 dict2 = get_dict(ondisk->entry.obj_id, pfs_id); 532 path1 = recover_path(dict2); 533 534 if (dict2->name == NULL) 535 dict2->name = name; 536 else 537 free(name); 538 539 /* 540 * Attach dict2 to its directory (dict), create the 541 * directory (dict) if necessary. We must ensure 542 * that the directory entry exists in order to be 543 * able to properly rename() the file without creating 544 * a namespace conflict. 545 */ 546 if ((dict2->flags & DICTF_PARENT) == 0) { 547 dict2->flags |= DICTF_PARENT; 548 dict2->parent = dict; 549 if ((dict->flags & DICTF_MADEDIR) == 0) { 550 dict->flags |= DICTF_MADEDIR; 551 path2 = recover_path(dict); 552 printf("mkdir %s\n", path2); 553 mkdir(path2, 0777); 554 free(path2); 555 path2 = NULL; 556 } 557 } 558 path2 = recover_path(dict2); 559 if (strcmp(path1, path2) != 0 && lstat(path1, &st) == 0) { 560 printf("Rename %s -> %s\n", path1, path2); 561 rename(path1, path2); 562 } 563 free(path1); 564 free(path2); 565 break; 566 default: 567 /* 568 * Ignore any other record types 569 */ 570 break; 571 } 572 done: 573 rel_buffer(data_buffer); 574 } 575 576 #define RD_HSIZE 32768 577 #define RD_HMASK (RD_HSIZE - 1) 578 579 struct recover_dict *RDHash[RD_HSIZE]; 580 581 static 582 struct recover_dict * 583 get_dict(int64_t obj_id, uint16_t pfs_id) 584 { 585 struct recover_dict *dict; 586 int i; 587 588 if (obj_id == 0) 589 return(NULL); 590 591 i = crc32(&obj_id, sizeof(obj_id)) & RD_HMASK; 592 for (dict = RDHash[i]; dict; dict = dict->next) { 593 if (dict->obj_id == obj_id && 594 dict->pfs_id == pfs_id) { 595 break; 596 } 597 } 598 if (dict == NULL) { 599 dict = malloc(sizeof(*dict)); 600 bzero(dict, sizeof(*dict)); 601 dict->obj_id = obj_id; 602 dict->pfs_id = pfs_id; 603 dict->next = RDHash[i]; 604 dict->size = -1; 605 RDHash[i] = dict; 606 607 /* 608 * Always connect dangling dictionary entries to object 1 609 * (the root of the PFS). 610 * 611 * DICTF_PARENT will not be set until we know what the 612 * real parent directory object is. 613 */ 614 if (dict->obj_id != HAMMER_OBJID_ROOT) 615 dict->parent = get_dict(HAMMER_OBJID_ROOT, pfs_id); 616 } 617 return(dict); 618 } 619 620 struct path_info { 621 enum { PI_FIGURE, PI_LOAD } state; 622 uint16_t pfs_id; 623 char *base; 624 char *next; 625 int len; 626 }; 627 628 static void recover_path_helper(struct recover_dict *, struct path_info *); 629 630 static 631 char * 632 recover_path(struct recover_dict *dict) 633 { 634 struct path_info info; 635 636 /* Find info.len first */ 637 bzero(&info, sizeof(info)); 638 info.state = PI_FIGURE; 639 recover_path_helper(dict, &info); 640 641 /* Fill in the path */ 642 info.pfs_id = dict->pfs_id; 643 info.base = malloc(info.len); 644 info.next = info.base; 645 info.state = PI_LOAD; 646 recover_path_helper(dict, &info); 647 648 /* Return the path */ 649 return(info.base); 650 } 651 652 #define STRLEN_OBJID 22 /* "obj_0x%016jx" */ 653 #define STRLEN_PFSID 8 /* "PFS%05d" */ 654 655 static 656 void 657 recover_path_helper(struct recover_dict *dict, struct path_info *info) 658 { 659 /* 660 * Calculate path element length 661 */ 662 dict->flags |= DICTF_TRAVERSED; 663 664 switch(info->state) { 665 case PI_FIGURE: 666 if (dict->obj_id == HAMMER_OBJID_ROOT) 667 info->len += STRLEN_PFSID; 668 else if (dict->name) 669 info->len += strlen(dict->name); 670 else 671 info->len += STRLEN_OBJID; 672 ++info->len; 673 674 if (dict->parent && 675 (dict->parent->flags & DICTF_TRAVERSED) == 0) { 676 recover_path_helper(dict->parent, info); 677 } else { 678 info->len += strlen(TargetDir) + 1; 679 } 680 break; 681 case PI_LOAD: 682 if (dict->parent && 683 (dict->parent->flags & DICTF_TRAVERSED) == 0) { 684 recover_path_helper(dict->parent, info); 685 } else { 686 strcpy(info->next, TargetDir); 687 info->next += strlen(info->next); 688 } 689 690 *info->next++ = '/'; 691 if (dict->obj_id == HAMMER_OBJID_ROOT) { 692 snprintf(info->next, STRLEN_PFSID + 1, 693 "PFS%05d", info->pfs_id); 694 } else if (dict->name) { 695 strcpy(info->next, dict->name); 696 } else { 697 snprintf(info->next, STRLEN_OBJID + 1, 698 "obj_0x%016jx", (uintmax_t)dict->obj_id); 699 } 700 info->next += strlen(info->next); 701 break; 702 } 703 dict->flags &= ~DICTF_TRAVERSED; 704 } 705 706 static 707 void 708 sanitize_string(char *str) 709 { 710 while (*str) { 711 if (!isprint(*str)) 712 *str = 'x'; 713 ++str; 714 } 715 } 716 717 static 718 hammer_off_t 719 scan_raw_limit(void) 720 { 721 struct volume_info *vol; 722 hammer_blockmap_t rootmap; 723 hammer_blockmap_layer1_t layer1; 724 hammer_blockmap_layer2_t layer2; 725 struct buffer_info *buffer1 = NULL; 726 struct buffer_info *buffer2 = NULL; 727 hammer_off_t layer1_offset; 728 hammer_off_t layer2_offset; 729 hammer_off_t phys_offset; 730 hammer_off_t block_offset; 731 hammer_off_t offset = 0; 732 int zone = HAMMER_ZONE_FREEMAP_INDEX; 733 734 vol = get_root_volume(); 735 rootmap = &vol->ondisk->vol0_blockmap[zone]; 736 assert(rootmap->phys_offset != 0); 737 738 for (phys_offset = HAMMER_ZONE_ENCODE(zone, 0); 739 phys_offset < HAMMER_ZONE_ENCODE(zone, HAMMER_OFF_LONG_MASK); 740 phys_offset += HAMMER_BLOCKMAP_LAYER2) { 741 /* 742 * Dive layer 1. 743 */ 744 layer1_offset = rootmap->phys_offset + 745 HAMMER_BLOCKMAP_LAYER1_OFFSET(phys_offset); 746 layer1 = get_buffer_data(layer1_offset, &buffer1, 0); 747 748 if (!hammer_crc_test_layer1(layer1)) { 749 offset = 0; /* failed */ 750 goto end; 751 } 752 if (layer1->phys_offset == HAMMER_BLOCKMAP_UNAVAIL) 753 continue; 754 755 for (block_offset = 0; 756 block_offset < HAMMER_BLOCKMAP_LAYER2; 757 block_offset += HAMMER_BIGBLOCK_SIZE) { 758 /* 759 * Dive layer 2, each entry represents a big-block. 760 */ 761 layer2_offset = layer1->phys_offset + 762 HAMMER_BLOCKMAP_LAYER2_OFFSET(block_offset); 763 layer2 = get_buffer_data(layer2_offset, &buffer2, 0); 764 765 if (!hammer_crc_test_layer2(layer2)) { 766 offset = 0; /* failed */ 767 goto end; 768 } 769 if (layer2->zone == HAMMER_ZONE_UNAVAIL_INDEX) { 770 break; 771 } else if (layer2->zone && layer2->zone != zone) { 772 offset = phys_offset + block_offset; 773 } 774 } 775 } 776 end: 777 rel_buffer(buffer1); 778 rel_buffer(buffer2); 779 780 return(hammer_xlate_to_zone2(offset)); 781 } 782 783 static 784 void 785 scan_bigblocks(int target_zone) 786 { 787 struct volume_info *vol; 788 hammer_blockmap_t rootmap; 789 hammer_blockmap_layer1_t layer1; 790 hammer_blockmap_layer2_t layer2; 791 struct buffer_info *buffer1 = NULL; 792 struct buffer_info *buffer2 = NULL; 793 hammer_off_t layer1_offset; 794 hammer_off_t layer2_offset; 795 hammer_off_t phys_offset; 796 hammer_off_t block_offset; 797 hammer_off_t offset = 0; 798 int zone = HAMMER_ZONE_FREEMAP_INDEX; 799 800 vol = get_root_volume(); 801 rootmap = &vol->ondisk->vol0_blockmap[zone]; 802 assert(rootmap->phys_offset != 0); 803 804 for (phys_offset = HAMMER_ZONE_ENCODE(zone, 0); 805 phys_offset < HAMMER_ZONE_ENCODE(zone, HAMMER_OFF_LONG_MASK); 806 phys_offset += HAMMER_BLOCKMAP_LAYER2) { 807 /* 808 * Dive layer 1. 809 */ 810 layer1_offset = rootmap->phys_offset + 811 HAMMER_BLOCKMAP_LAYER1_OFFSET(phys_offset); 812 layer1 = get_buffer_data(layer1_offset, &buffer1, 0); 813 814 /* 815 if (!hammer_crc_test_layer1(layer1)) { 816 } 817 */ 818 if (layer1->phys_offset == HAMMER_BLOCKMAP_UNAVAIL) 819 continue; 820 821 for (block_offset = 0; 822 block_offset < HAMMER_BLOCKMAP_LAYER2; 823 block_offset += HAMMER_BIGBLOCK_SIZE) { 824 offset = phys_offset + block_offset; 825 /* 826 * Dive layer 2, each entry represents a big-block. 827 */ 828 layer2_offset = layer1->phys_offset + 829 HAMMER_BLOCKMAP_LAYER2_OFFSET(block_offset); 830 layer2 = get_buffer_data(layer2_offset, &buffer2, 0); 831 832 /* 833 if (!hammer_crc_test_layer2(layer2)) { 834 } 835 */ 836 if (layer2->zone == target_zone) { 837 add_bigblock_entry(offset); 838 } else if (layer2->zone == HAMMER_ZONE_UNAVAIL_INDEX) { 839 break; 840 } 841 } 842 } 843 rel_buffer(buffer1); 844 rel_buffer(buffer2); 845 } 846 847 static 848 void 849 free_bigblocks(void) 850 { 851 bigblock_t b; 852 853 while ((b = RB_ROOT(&ZoneTree)) != NULL) { 854 RB_REMOVE(bigblock_rb_tree, &ZoneTree, b); 855 free(b); 856 } 857 assert(RB_EMPTY(&ZoneTree)); 858 } 859 860 static 861 void 862 add_bigblock_entry(hammer_off_t offset) 863 { 864 bigblock_t b; 865 866 b = calloc(sizeof(*b), 1); 867 b->phys_offset = hammer_xlate_to_zone2(offset); 868 assert((b->phys_offset & HAMMER_BIGBLOCK_MASK64) == 0); 869 870 RB_INSERT(bigblock_rb_tree, &ZoneTree, b); 871 } 872 873 static 874 int 875 test_bigblock_entry(hammer_off_t offset) 876 { 877 bigblock_t b; 878 879 offset = hammer_xlate_to_zone2(offset); 880 offset &= ~HAMMER_BIGBLOCK_MASK64; 881 882 b = RB_LOOKUP(bigblock_rb_tree, &ZoneTree, offset); 883 if (b) 884 return(1); 885 return(0); 886 } 887