restore/restore.c

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