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