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