sbin/hammer/cmd_recover.c

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