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