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