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