sbin/restore/restore.c

   1 /*
   2  * Copyright (c) 1983, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. Neither the name of the University nor the names of its contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  *
  29  * @(#)restore.c        8.3 (Berkeley) 9/13/94
  30  * $FreeBSD: src/sbin/restore/restore.c,v 1.7.2.1 2002/03/01 21:32:28 iedowse Exp $
  31  */
  32
  33 #include <sys/types.h>
  34
  35 #include <vfs/ufs/dinode.h>
  36
  37 #include <stdio.h>
  38 #include <string.h>
  39
  40 #include "restore.h"
  41 #include "extern.h"
  42
  43 static char *keyval(int);
  44
  45 /*
  46  * This implements the 't' option.
  47  * List entries on the tape.
  48  */
  49 long
  50 listfile(char *name, ufs1_ino_t ino, int type)
  51 {
  52         long descend = hflag ? GOOD : FAIL;
  53
  54         if (TSTINO(ino, dumpmap) == 0)
  55                 return (descend);
  56         vprintf(stdout, "%s", type == LEAF ? "leaf" : "dir ");
  57         fprintf(stdout, "%10d\t%s\n", ino, name);
  58         return (descend);
  59 }
  60
  61 /*
  62  * This implements the 'x' option.
  63  * Request that new entries be extracted.
  64  */
  65 long
  66 addfile(char *name, ufs1_ino_t ino, int type)
  67 {
  68         struct entry *ep;
  69         long descend = hflag ? GOOD : FAIL;
  70         char buf[100];
  71
  72         if (TSTINO(ino, dumpmap) == 0) {
  73                 dprintf(stdout, "%s: not on the tape\n", name);
  74                 return (descend);
  75         }
  76         if (ino == UFS_WINO && command == 'i' && !vflag)
  77                 return (descend);
  78         if (!mflag) {
  79                 sprintf(buf, "./%u", ino);
  80                 name = buf;
  81                 if (type == NODE) {
  82                         genliteraldir(name, ino);
  83                         return (descend);
  84                 }
  85         }
  86         ep = lookupino(ino);
  87         if (ep != NULL) {
  88                 if (strcmp(name, myname(ep)) == 0) {
  89                         ep->e_flags |= NEW;
  90                         return (descend);
  91                 }
  92                 type |= LINK;
  93         }
  94         ep = addentry(name, ino, type);
  95         if (type == NODE)
  96                 newnode(ep);
  97         ep->e_flags |= NEW;
  98         return (descend);
  99 }
 100
 101 /*
 102  * This is used by the 'i' option to undo previous requests made by addfile.
 103  * Delete entries from the request queue.
 104  */
 105 /* ARGSUSED */
 106 long
 107 deletefile(char *name, ufs1_ino_t ino, int type __unused)
 108 {
 109         long descend = hflag ? GOOD : FAIL;
 110         struct entry *ep;
 111
 112         if (TSTINO(ino, dumpmap) == 0)
 113                 return (descend);
 114         ep = lookupname(name);
 115         if (ep != NULL) {
 116                 ep->e_flags &= ~NEW;
 117                 ep->e_flags |= REMOVED;
 118                 if (ep->e_type != NODE)
 119                         freeentry(ep);
 120         }
 121         return (descend);
 122 }
 123
 124 /*
 125  * The following four routines implement the incremental
 126  * restore algorithm. The first removes old entries, the second
 127  * does renames and calculates the extraction list, the third
 128  * cleans up link names missed by the first two, and the final
 129  * one deletes old directories.
 130  *
 131  * Directories cannot be immediately deleted, as they may have
 132  * other files in them which need to be moved out first. As
 133  * directories to be deleted are found, they are put on the
 134  * following deletion list. After all deletions and renames
 135  * are done, this list is actually deleted.
 136  */
 137 static struct entry *removelist;
 138
 139 /*
 140  *      Remove invalid whiteouts from the old tree.
 141  *      Remove unneeded leaves from the old tree.
 142  *      Remove directories from the lookup chains.
 143  */
 144 void
 145 removeoldleaves(void)
 146 {
 147         struct entry *ep, *nextep;
 148         ufs1_ino_t i, mydirino;
 149
 150         vprintf(stdout, "Mark entries to be removed.\n");
 151         if ((ep = lookupino(UFS_WINO))) {
 152                 vprintf(stdout, "Delete whiteouts\n");
 153                 for ( ; ep != NULL; ep = nextep) {
 154                         nextep = ep->e_links;
 155                         mydirino = ep->e_parent->e_ino;
 156                         /*
 157                          * We remove all whiteouts that are in directories
 158                          * that have been removed or that have been dumped.
 159                          */
 160                         if (TSTINO(mydirino, usedinomap) &&
 161                             !TSTINO(mydirino, dumpmap))
 162                                 continue;
 163                         delwhiteout(ep);
 164                         freeentry(ep);
 165                 }
 166         }
 167         for (i = UFS_ROOTINO + 1; i < maxino; i++) {
 168                 ep = lookupino(i);
 169                 if (ep == NULL)
 170                         continue;
 171                 if (TSTINO(i, usedinomap))
 172                         continue;
 173                 for ( ; ep != NULL; ep = ep->e_links) {
 174                         dprintf(stdout, "%s: REMOVE\n", myname(ep));
 175                         if (ep->e_type == LEAF) {
 176                                 removeleaf(ep);
 177                                 freeentry(ep);
 178                         } else {
 179                                 mktempname(ep);
 180                                 deleteino(ep->e_ino);
 181                                 ep->e_next = removelist;
 182                                 removelist = ep;
 183                         }
 184                 }
 185         }
 186 }
 187
 188 /*
 189  *      For each directory entry on the incremental tape, determine which
 190  *      category it falls into as follows:
 191  *      KEEP - entries that are to be left alone.
 192  *      NEW - new entries to be added.
 193  *      EXTRACT - files that must be updated with new contents.
 194  *      LINK - new links to be added.
 195  *      Renames are done at the same time.
 196  */
 197 long
 198 nodeupdates(char *name, ufs1_ino_t ino, int type)
 199 {
 200         struct entry *ep, *np, *ip;
 201         long descend = GOOD;
 202         int lookuptype = 0;
 203         int key = 0;
 204                 /* key values */
 205 #               define ONTAPE   0x1     /* inode is on the tape */
 206 #               define INOFND   0x2     /* inode already exists */
 207 #               define NAMEFND  0x4     /* name already exists */
 208 #               define MODECHG  0x8     /* mode of inode changed */
 209
 210         /*
 211          * This routine is called once for each element in the
 212          * directory hierarchy, with a full path name.
 213          * The "type" value is incorrectly specified as LEAF for
 214          * directories that are not on the dump tape.
 215          *
 216          * Check to see if the file is on the tape.
 217          */
 218         if (TSTINO(ino, dumpmap))
 219                 key |= ONTAPE;
 220         /*
 221          * Check to see if the name exists, and if the name is a link.
 222          */
 223         np = lookupname(name);
 224         if (np != NULL) {
 225                 key |= NAMEFND;
 226                 ip = lookupino(np->e_ino);
 227                 if (ip == NULL)
 228                         panic("corrupted symbol table\n");
 229                 if (ip != np)
 230                         lookuptype = LINK;
 231         }
 232         /*
 233          * Check to see if the inode exists, and if one of its links
 234          * corresponds to the name (if one was found).
 235          */
 236         ip = lookupino(ino);
 237         if (ip != NULL) {
 238                 key |= INOFND;
 239                 for (ep = ip->e_links; ep != NULL; ep = ep->e_links) {
 240                         if (ep == np) {
 241                                 ip = ep;
 242                                 break;
 243                         }
 244                 }
 245         }
 246         /*
 247          * If both a name and an inode are found, but they do not
 248          * correspond to the same file, then both the inode that has
 249          * been found and the inode corresponding to the name that
 250          * has been found need to be renamed. The current pathname
 251          * is the new name for the inode that has been found. Since
 252          * all files to be deleted have already been removed, the
 253          * named file is either a now unneeded link, or it must live
 254          * under a new name in this dump level. If it is a link, it
 255          * can be removed. If it is not a link, it is given a
 256          * temporary name in anticipation that it will be renamed
 257          * when it is later found by inode number.
 258          */
 259         if (((key & (INOFND|NAMEFND)) == (INOFND|NAMEFND)) && ip != np) {
 260                 if (lookuptype == LINK) {
 261                         removeleaf(np);
 262                         freeentry(np);
 263                 } else {
 264                         dprintf(stdout, "name/inode conflict, mktempname %s\n",
 265                                 myname(np));
 266                         mktempname(np);
 267                 }
 268                 np = NULL;
 269                 key &= ~NAMEFND;
 270         }
 271         if ((key & ONTAPE) &&
 272           (((key & INOFND) && ip->e_type != type) ||
 273            ((key & NAMEFND) && np->e_type != type)))
 274                 key |= MODECHG;
 275
 276         /*
 277          * Decide on the disposition of the file based on its flags.
 278          * Note that we have already handled the case in which
 279          * a name and inode are found that correspond to different files.
 280          * Thus if both NAMEFND and INOFND are set then ip == np.
 281          */
 282         switch (key) {
 283
 284         /*
 285          * A previously existing file has been found.
 286          * Mark it as KEEP so that other links to the inode can be
 287          * detected, and so that it will not be reclaimed by the search
 288          * for unreferenced names.
 289          */
 290         case INOFND|NAMEFND:
 291                 ip->e_flags |= KEEP;
 292                 dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
 293                         flagvalues(ip));
 294                 break;
 295
 296         /*
 297          * A file on the tape has a name which is the same as a name
 298          * corresponding to a different file in the previous dump.
 299          * Since all files to be deleted have already been removed,
 300          * this file is either a now unneeded link, or it must live
 301          * under a new name in this dump level. If it is a link, it
 302          * can simply be removed. If it is not a link, it is given a
 303          * temporary name in anticipation that it will be renamed
 304          * when it is later found by inode number (see INOFND case
 305          * below). The entry is then treated as a new file.
 306          */
 307         case ONTAPE|NAMEFND:
 308         case ONTAPE|NAMEFND|MODECHG:
 309                 if (lookuptype == LINK) {
 310                         removeleaf(np);
 311                         freeentry(np);
 312                 } else {
 313                         mktempname(np);
 314                 }
 315                 /* fall through */
 316
 317         /*
 318          * A previously non-existent file.
 319          * Add it to the file system, and request its extraction.
 320          * If it is a directory, create it immediately.
 321          * (Since the name is unused there can be no conflict)
 322          */
 323         case ONTAPE:
 324                 ep = addentry(name, ino, type);
 325                 if (type == NODE)
 326                         newnode(ep);
 327                 ep->e_flags |= NEW|KEEP;
 328                 dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
 329                         flagvalues(ep));
 330                 break;
 331
 332         /*
 333          * A file with the same inode number, but a different
 334          * name has been found. If the other name has not already
 335          * been found (indicated by the KEEP flag, see above) then
 336          * this must be a new name for the file, and it is renamed.
 337          * If the other name has been found then this must be a
 338          * link to the file. Hard links to directories are not
 339          * permitted, and are either deleted or converted to
 340          * symbolic links. Finally, if the file is on the tape,
 341          * a request is made to extract it.
 342          */
 343         case ONTAPE|INOFND:
 344                 if (type == LEAF && (ip->e_flags & KEEP) == 0)
 345                         ip->e_flags |= EXTRACT;
 346                 /* fall through */
 347         case INOFND:
 348                 if ((ip->e_flags & KEEP) == 0) {
 349                         renameit(myname(ip), name);
 350                         moveentry(ip, name);
 351                         ip->e_flags |= KEEP;
 352                         dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
 353                                 flagvalues(ip));
 354                         break;
 355                 }
 356                 if (ip->e_type == NODE) {
 357                         descend = FAIL;
 358                         fprintf(stderr,
 359                                 "deleted hard link %s to directory %s\n",
 360                                 name, myname(ip));
 361                         break;
 362                 }
 363                 ep = addentry(name, ino, type|LINK);
 364                 ep->e_flags |= NEW;
 365                 dprintf(stdout, "[%s] %s: %s|LINK\n", keyval(key), name,
 366                         flagvalues(ep));
 367                 break;
 368
 369         /*
 370          * A previously known file which is to be updated. If it is a link,
 371          * then all names referring to the previous file must be removed
 372          * so that the subset of them that remain can be recreated.
 373          */
 374         case ONTAPE|INOFND|NAMEFND:
 375                 if (lookuptype == LINK) {
 376                         removeleaf(np);
 377                         freeentry(np);
 378                         ep = addentry(name, ino, type|LINK);
 379                         if (type == NODE)
 380                                 newnode(ep);
 381                         ep->e_flags |= NEW|KEEP;
 382                         dprintf(stdout, "[%s] %s: %s|LINK\n", keyval(key), name,
 383                                 flagvalues(ep));
 384                         break;
 385                 }
 386                 if (type == LEAF && lookuptype != LINK)
 387                         np->e_flags |= EXTRACT;
 388                 np->e_flags |= KEEP;
 389                 dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
 390                         flagvalues(np));
 391                 break;
 392
 393         /*
 394          * An inode is being reused in a completely different way.
 395          * Normally an extract can simply do an "unlink" followed
 396          * by a "creat". Here we must do effectively the same
 397          * thing. The complications arise because we cannot really
 398          * delete a directory since it may still contain files
 399          * that we need to rename, so we delete it from the symbol
 400          * table, and put it on the list to be deleted eventually.
 401          * Conversely if a directory is to be created, it must be
 402          * done immediately, rather than waiting until the
 403          * extraction phase.
 404          */
 405         case ONTAPE|INOFND|MODECHG:
 406         case ONTAPE|INOFND|NAMEFND|MODECHG:
 407                 if (ip->e_flags & KEEP) {
 408                         badentry(ip, "cannot KEEP and change modes");
 409                         break;
 410                 }
 411                 if (ip->e_type == LEAF) {
 412                         /* changing from leaf to node */
 413                         for (ip = lookupino(ino); ip != NULL; ip = ip->e_links) {
 414                                 if (ip->e_type != LEAF)
 415                                         badentry(ip, "NODE and LEAF links to same inode");
 416                                 removeleaf(ip);
 417                                 freeentry(ip);
 418                         }
 419                         ip = addentry(name, ino, type);
 420                         newnode(ip);
 421                 } else {
 422                         /* changing from node to leaf */
 423                         if ((ip->e_flags & TMPNAME) == 0)
 424                                 mktempname(ip);
 425                         deleteino(ip->e_ino);
 426                         ip->e_next = removelist;
 427                         removelist = ip;
 428                         ip = addentry(name, ino, type);
 429                 }
 430                 ip->e_flags |= NEW|KEEP;
 431                 dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
 432                         flagvalues(ip));
 433                 break;
 434
 435         /*
 436          * A hard link to a directory that has been removed.
 437          * Ignore it.
 438          */
 439         case NAMEFND:
 440                 dprintf(stdout, "[%s] %s: Extraneous name\n", keyval(key),
 441                         name);
 442                 descend = FAIL;
 443                 break;
 444
 445         /*
 446          * If we find a directory entry for a file that is not on
 447          * the tape, then we must have found a file that was created
 448          * while the dump was in progress. Since we have no contents
 449          * for it, we discard the name knowing that it will be on the
 450          * next incremental tape.
 451          */
 452         case 0:
 453                 fprintf(stderr, "%s: (inode %d) not found on tape\n",
 454                         name, ino);
 455                 break;
 456
 457         /*
 458          * If any of these arise, something is grievously wrong with
 459          * the current state of the symbol table.
 460          */
 461         case INOFND|NAMEFND|MODECHG:
 462         case NAMEFND|MODECHG:
 463         case INOFND|MODECHG:
 464                 fprintf(stderr, "[%s] %s: inconsistent state\n", keyval(key),
 465                         name);
 466                 break;
 467
 468         /*
 469          * These states "cannot" arise for any state of the symbol table.
 470          */
 471         case ONTAPE|MODECHG:
 472         case MODECHG:
 473         default:
 474                 panic("[%s] %s: impossible state\n", keyval(key), name);
 475                 break;
 476         }
 477         return (descend);
 478 }
 479
 480 /*
 481  * Calculate the active flags in a key.
 482  */
 483 static char *
 484 keyval(int key)
 485 {
 486         static char keybuf[32];
 487
 488         strcpy(keybuf, "|NIL");
 489         keybuf[0] = '\0';
 490         if (key & ONTAPE)
 491                 strcat(keybuf, "|ONTAPE");
 492         if (key & INOFND)
 493                 strcat(keybuf, "|INOFND");
 494         if (key & NAMEFND)
 495                 strcat(keybuf, "|NAMEFND");
 496         if (key & MODECHG)
 497                 strcat(keybuf, "|MODECHG");
 498         return (&keybuf[1]);
 499 }
 500
 501 /*
 502  * Find unreferenced link names.
 503  */
 504 void
 505 findunreflinks(void)
 506 {
 507         struct entry *ep, *np;
 508         ufs1_ino_t i;
 509
 510         vprintf(stdout, "Find unreferenced names.\n");
 511         for (i = UFS_ROOTINO; i < maxino; i++) {
 512                 ep = lookupino(i);
 513                 if (ep == NULL || ep->e_type == LEAF || TSTINO(i, dumpmap) == 0)
 514                         continue;
 515                 for (np = ep->e_entries; np != NULL; np = np->e_sibling) {
 516                         if (np->e_flags == 0) {
 517                                 dprintf(stdout,
 518                                     "%s: remove unreferenced name\n",
 519                                     myname(np));
 520                                 removeleaf(np);
 521                                 freeentry(np);
 522                         }
 523                 }
 524         }
 525         /*
 526          * Any leaves remaining in removed directories is unreferenced.
 527          */
 528         for (ep = removelist; ep != NULL; ep = ep->e_next) {
 529                 for (np = ep->e_entries; np != NULL; np = np->e_sibling) {
 530                         if (np->e_type == LEAF) {
 531                                 if (np->e_flags != 0)
 532                                         badentry(np, "unreferenced with flags");
 533                                 dprintf(stdout,
 534                                     "%s: remove unreferenced name\n",
 535                                     myname(np));
 536                                 removeleaf(np);
 537                                 freeentry(np);
 538                         }
 539                 }
 540         }
 541 }
 542
 543 /*
 544  * Remove old nodes (directories).
 545  * Note that this routine runs in O(N*D) where:
 546  *      N is the number of directory entries to be removed.
 547  *      D is the maximum depth of the tree.
 548  * If N == D this can be quite slow. If the list were
 549  * topologically sorted, the deletion could be done in
 550  * time O(N).
 551  */
 552 void
 553 removeoldnodes(void)
 554 {
 555         struct entry *ep, **prev;
 556         long change;
 557
 558         vprintf(stdout, "Remove old nodes (directories).\n");
 559         do      {
 560                 change = 0;
 561                 prev = &removelist;
 562                 for (ep = removelist; ep != NULL; ep = *prev) {
 563                         if (ep->e_entries != NULL) {
 564                                 prev = &ep->e_next;
 565                                 continue;
 566                         }
 567                         *prev = ep->e_next;
 568                         removenode(ep);
 569                         freeentry(ep);
 570                         change++;
 571                 }
 572         } while (change);
 573         for (ep = removelist; ep != NULL; ep = ep->e_next)
 574                 badentry(ep, "cannot remove, non-empty");
 575 }
 576
 577 /*
 578  * This is the routine used to extract files for the 'r' command.
 579  * Extract new leaves.
 580  */
 581 void
 582 createleaves(const char *symtabfile)
 583 {
 584         struct entry *ep;
 585         ufs1_ino_t first;
 586         long curvol;
 587
 588         if (command == 'R') {
 589                 vprintf(stdout, "Continue extraction of new leaves\n");
 590         } else {
 591                 vprintf(stdout, "Extract new leaves.\n");
 592                 dumpsymtable(symtabfile, volno);
 593         }
 594         first = lowerbnd(UFS_ROOTINO);
 595         curvol = volno;
 596         while (curfile.ino < maxino) {
 597                 first = lowerbnd(first);
 598                 /*
 599                  * If the next available file is not the one which we
 600                  * expect then we have missed one or more files. Since
 601                  * we do not request files that were not on the tape,
 602                  * the lost files must have been due to a tape read error,
 603                  * or a file that was removed while the dump was in progress.
 604                  */
 605                 while (first < curfile.ino) {
 606                         ep = lookupino(first);
 607                         if (ep == NULL)
 608                                 panic("%d: bad first\n", first);
 609                         fprintf(stderr, "%s: not found on tape\n", myname(ep));
 610                         ep->e_flags &= ~(NEW|EXTRACT);
 611                         first = lowerbnd(first);
 612                 }
 613                 /*
 614                  * If we find files on the tape that have no corresponding
 615                  * directory entries, then we must have found a file that
 616                  * was created while the dump was in progress. Since we have
 617                  * no name for it, we discard it knowing that it will be
 618                  * on the next incremental tape.
 619                  */
 620                 if (first != curfile.ino) {
 621                         fprintf(stderr, "expected next file %d, got %d\n",
 622                                 first, curfile.ino);
 623                         skipfile();
 624                         goto next;
 625                 }
 626                 ep = lookupino(curfile.ino);
 627                 if (ep == NULL)
 628                         panic("unknown file on tape\n");
 629                 if ((ep->e_flags & (NEW|EXTRACT)) == 0)
 630                         badentry(ep, "unexpected file on tape");
 631                 /*
 632                  * If the file is to be extracted, then the old file must
 633                  * be removed since its type may change from one leaf type
 634                  * to another (e.g. "file" to "character special").
 635                  */
 636                 if ((ep->e_flags & EXTRACT) != 0) {
 637                         removeleaf(ep);
 638                         ep->e_flags &= ~REMOVED;
 639                 }
 640                 extractfile(myname(ep));
 641                 ep->e_flags &= ~(NEW|EXTRACT);
 642                 /*
 643                  * We checkpoint the restore after every tape reel, so
 644                  * as to simplify the amount of work required by the
 645                  * 'R' command.
 646                  */
 647         next:
 648                 if (curvol != volno) {
 649                         dumpsymtable(symtabfile, volno);
 650                         skipmaps();
 651                         curvol = volno;
 652                 }
 653         }
 654 }
 655
 656 /*
 657  * This is the routine used to extract files for the 'x' and 'i' commands.
 658  * Efficiently extract a subset of the files on a tape.
 659  */
 660 void
 661 createfiles(void)
 662 {
 663         ufs1_ino_t first, next, last;
 664         struct entry *ep;
 665         long curvol;
 666
 667         vprintf(stdout, "Extract requested files\n");
 668         curfile.action = SKIP;
 669         getvol((long)1);
 670         skipmaps();
 671         skipdirs();
 672         first = lowerbnd(UFS_ROOTINO);
 673         last = upperbnd(maxino - 1);
 674         for (;;) {
 675                 curvol = volno;
 676                 first = lowerbnd(first);
 677                 last = upperbnd(last);
 678                 /*
 679                  * Check to see if any files remain to be extracted
 680                  */
 681                 if (first > last)
 682                         return;
 683                 /*
 684                  * Reject any volumes with inodes greater than the last
 685                  * one needed, so that we can quickly skip backwards to
 686                  * a volume containing useful inodes. We can't do this
 687                  * if there are no further volumes available (curfile.ino
 688                  * >= maxino) or if we are already at the first tape.
 689                  */
 690                 if (curfile.ino > last && curfile.ino < maxino && volno > 1) {
 691                         curfile.action = SKIP;
 692                         getvol((long)0);
 693                         skipmaps();
 694                         skipdirs();
 695                         continue;
 696                 }
 697                 /*
 698                  * Decide on the next inode needed.
 699                  * Skip across the inodes until it is found
 700                  * or a volume change is encountered
 701                  */
 702                 if (curfile.ino < maxino) {
 703                         next = lowerbnd(curfile.ino);
 704                         while (next > curfile.ino && volno == curvol)
 705                                 skipfile();
 706                         if (volno != curvol) {
 707                                 skipmaps();
 708                                 skipdirs();
 709                                 continue;
 710                         }
 711                 } else {
 712                         /*
 713                          * No further volumes or inodes available. Set
 714                          * `next' to the first inode, so that a warning
 715                          * is emitted below for each missing file.
 716                          */
 717                         next = first;
 718                 }
 719                 /*
 720                  * If the current inode is greater than the one we were
 721                  * looking for then we missed the one we were looking for.
 722                  * Since we only attempt to extract files listed in the
 723                  * dump map, the lost files must have been due to a tape
 724                  * read error, or a file that was removed while the dump
 725                  * was in progress. Thus we report all requested files
 726                  * between the one we were looking for, and the one we
 727                  * found as missing, and delete their request flags.
 728                  */
 729                 while (next < curfile.ino) {
 730                         ep = lookupino(next);
 731                         if (ep == NULL)
 732                                 panic("corrupted symbol table\n");
 733                         fprintf(stderr, "%s: not found on tape\n", myname(ep));
 734                         ep->e_flags &= ~NEW;
 735                         next = lowerbnd(next);
 736                 }
 737                 /*
 738                  * The current inode is the one that we are looking for,
 739                  * so extract it per its requested name.
 740                  */
 741                 if (next == curfile.ino && next <= last) {
 742                         ep = lookupino(next);
 743                         if (ep == NULL)
 744                                 panic("corrupted symbol table\n");
 745                         extractfile(myname(ep));
 746                         ep->e_flags &= ~NEW;
 747                         if (volno != curvol)
 748                                 skipmaps();
 749                 }
 750         }
 751 }
 752
 753 /*
 754  * Add links.
 755  */
 756 void
 757 createlinks(void)
 758 {
 759         struct entry *np, *ep;
 760         ufs1_ino_t i;
 761         char name[BUFSIZ];
 762
 763         if ((ep = lookupino(UFS_WINO))) {
 764                 vprintf(stdout, "Add whiteouts\n");
 765                 for ( ; ep != NULL; ep = ep->e_links) {
 766                         if ((ep->e_flags & NEW) == 0)
 767                                 continue;
 768                         addwhiteout(myname(ep));
 769                         ep->e_flags &= ~NEW;
 770                 }
 771         }
 772         vprintf(stdout, "Add links\n");
 773         for (i = UFS_ROOTINO; i < maxino; i++) {
 774                 ep = lookupino(i);
 775                 if (ep == NULL)
 776                         continue;
 777                 for (np = ep->e_links; np != NULL; np = np->e_links) {
 778                         if ((np->e_flags & NEW) == 0)
 779                                 continue;
 780                         strcpy(name, myname(ep));
 781                         if (ep->e_type == NODE) {
 782                                 linkit(name, myname(np), SYMLINK);
 783                         } else {
 784                                 linkit(name, myname(np), HARDLINK);
 785                         }
 786                         np->e_flags &= ~NEW;
 787                 }
 788         }
 789 }
 790
 791 /*
 792  * Check the symbol table.
 793  * We do this to insure that all the requested work was done, and
 794  * that no temporary names remain.
 795  */
 796 void
 797 checkrestore(void)
 798 {
 799         struct entry *ep;
 800         ufs1_ino_t i;
 801
 802         vprintf(stdout, "Check the symbol table.\n");
 803         for (i = UFS_WINO; i < maxino; i++) {
 804                 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
 805                         ep->e_flags &= ~KEEP;
 806                         if (ep->e_type == NODE)
 807                                 ep->e_flags &= ~(NEW|EXISTED);
 808                         if (ep->e_flags != 0)
 809                                 badentry(ep, "incomplete operations");
 810                 }
 811         }
 812 }
 813
 814 /*
 815  * Compare with the directory structure on the tape
 816  * A paranoid check that things are as they should be.
 817  */
 818 long
 819 verifyfile(char *name, ufs1_ino_t ino, int type)
 820 {
 821         struct entry *np, *ep;
 822         long descend = GOOD;
 823
 824         ep = lookupname(name);
 825         if (ep == NULL) {
 826                 fprintf(stderr, "Warning: missing name %s\n", name);
 827                 return (FAIL);
 828         }
 829         np = lookupino(ino);
 830         if (np != ep)
 831                 descend = FAIL;
 832         for ( ; np != NULL; np = np->e_links)
 833                 if (np == ep)
 834                         break;
 835         if (np == NULL)
 836                 panic("missing inumber %ju\n", (uintmax_t)ino);
 837         if (ep->e_type == LEAF && type != LEAF)
 838                 badentry(ep, "type should be LEAF");
 839         return (descend);
 840 }