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