sbin/restore/restore.c

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