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