sbin/restore/restore.c

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