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