sbin/restore/restore.c

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