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