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.30 2002/07/19 14:57:40 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, UNUSED(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         int doremove;
 750
 751         if (command == 'R') {
 752                 Vprintf(stdout, "Continue extraction of new leaves\n");
 753         } else {
 754                 Vprintf(stdout, "Extract new leaves.\n");
 755                 dumpsymtable(symtabfile, volno);
 756         }
 757         first = lowerbnd(ROOTINO);
 758         curvol = volno;
 759         while (curfile.ino < maxino) {
 760                 first = lowerbnd(first);
 761                 /*
 762                  * If the next available file is not the one which we
 763                  * expect then we have missed one or more files. Since
 764                  * we do not request files that were not on the tape,
 765                  * the lost files must have been due to a tape read error,
 766                  * or a file that was removed while the dump was in progress.
 767                  */
 768                 while (first < curfile.ino) {
 769                         ep = lookupino(first);
 770                         if (ep == NULL)
 771                                 panic("%d: bad first\n", first);
 772                         fprintf(stderr, "%s: (inode %lu) not found on tape\n",
 773                                 myname(ep), (unsigned long)first);
 774                         ep->e_flags &= ~(NEW|EXTRACT);
 775                         first = lowerbnd(first);
 776                 }
 777                 /*
 778                  * If we find files on the tape that have no corresponding
 779                  * directory entries, then we must have found a file that
 780                  * was created while the dump was in progress. Since we have
 781                  * no name for it, we discard it knowing that it will be
 782                  * on the next incremental tape.
 783                  */
 784                 if (first != curfile.ino) {
 785                         fprintf(stderr, "expected next file %ld, got %lu\n",
 786                                 (long)first, (unsigned long)curfile.ino);
 787                         skipfile();
 788                         goto next;
 789                 }
 790                 ep = lookupino(curfile.ino);
 791                 if (ep == NULL)
 792                         panic("unknown file on tape\n");
 793                 if ((ep->e_flags & (NEW|EXTRACT)) == 0)
 794                         badentry(ep, "unexpected file on tape");
 795                 /*
 796                  * If the file is to be extracted, then the old file must
 797                  * be removed since its type may change from one leaf type
 798                  * to another (e.g. "file" to "character special").
 799                  */
 800                 if ((ep->e_flags & EXTRACT) != 0)
 801                         doremove = 1;
 802                 else
 803                         doremove = 0;
 804                 (void) extractfile(ep, doremove);
 805                 ep->e_flags &= ~(NEW|EXTRACT);
 806                 /*
 807                  * We checkpoint the restore after every tape reel, so
 808                  * as to simplify the amount of work required by the
 809                  * 'R' command.
 810                  */
 811         next:
 812                 if (curvol != volno) {
 813                         dumpsymtable(symtabfile, volno);
 814                         skipmaps();
 815                         curvol = volno;
 816                 }
 817         }
 818         /*
 819          * If we encounter the end of the tape and the next available
 820          * file is not the one which we expect then we have missed one
 821          * or more files. Since we do not request files that were not
 822          * on the tape, the lost files must have been due to a tape
 823          * read error, or a file that was removed while the dump was
 824          * in progress.
 825          */
 826         first = lowerbnd(first);
 827         while (first < curfile.ino) {
 828                 ep = lookupino(first);
 829                 if (ep == NULL)
 830                         panic("%d: bad first\n", first);
 831                 fprintf(stderr, "%s: (inode %lu) not found on tape\n",
 832                         myname(ep), (unsigned long)first);
 833                 do_compare_error;
 834                 ep->e_flags &= ~(NEW|EXTRACT);
 835                 first = lowerbnd(first);
 836         }
 837 }
 838
 839 /*
 840  * This is the routine used to extract files for the 'x' and 'i' commands.
 841  * Efficiently extract a subset of the files on a tape.
 842  */
 843 void
 844 createfiles(void)
 845 {
 846         dump_ino_t first, next, last;
 847         struct entry *ep;
 848         long curvol;
 849 #ifdef USE_QFA
 850         long tnum, tmpcnt;
 851         long long tpos, curtpos;
 852         time_t tistart, tiend, titaken;
 853 #endif
 854
 855         Vprintf(stdout, "Extract requested files\n");
 856         curfile.action = SKIP;
 857 #ifdef USE_QFA
 858         if (tapeposflag)
 859                 curfile.ino = 0;
 860         else
 861 #endif
 862                 if (volinfo[1] == ROOTINO)
 863                         curfile.ino = 0;
 864                 else
 865                         getvol((long)1);
 866         skipmaps();
 867         skipdirs();
 868         first = lowerbnd(ROOTINO);
 869         last = upperbnd(maxino - 1);
 870         for (;;) {
 871 #ifdef USE_QFA
 872                 tmpcnt = 1;
 873 #endif
 874                 first = lowerbnd(first);
 875                 last = upperbnd(last);
 876                 /*
 877                  * Check to see if any files remain to be extracted
 878                  */
 879                 if (first > last)
 880                         return;
 881                 /*
 882                  * Reject any volumes with inodes greater
 883                  * than the last one needed
 884                  */
 885                 while (curfile.ino > last) {
 886                         curfile.action = SKIP;
 887                         if (!pipein)
 888                                 getvol((long)0);
 889                         if (curfile.ino == maxino) {
 890                                 next = lowerbnd(first);
 891                                 while (next < curfile.ino) {
 892                                         ep = lookupino(next);
 893                                         if (ep == NULL)
 894                                                 panic("corrupted symbol table\n");
 895                                         fprintf(stderr, "%s: (inode %lu) not found on tape\n",
 896                                                 myname(ep), (unsigned long)next);
 897                                         ep->e_flags &= ~NEW;
 898                                         next = lowerbnd(next);
 899                                 }
 900                                 return;
 901                         }
 902                         skipmaps();
 903                         skipdirs();
 904                 }
 905                 /*
 906                  * Decide on the next inode needed.
 907                  * Skip across the inodes until it is found
 908                  * or an out of order volume change is encountered
 909                  */
 910                 next = lowerbnd(curfile.ino);
 911 #ifdef USE_QFA
 912                 tistart = time(NULL);
 913                 if (tapeposflag) {
 914                         /* get tape position for inode (position directly) */
 915                         (void)Inode2Tapepos(next, &tnum, &tpos, 1);
 916                         if (tpos == 0)
 917                                 /* get tape position for last available inode
 918                                  * (position before) */
 919                                 (void)Inode2Tapepos(next, &tnum, &tpos, 0);
 920                         if (tpos != 0) {
 921                                 if (tnum != volno)
 922                                         (void)RequestVol(tnum);
 923                                 if (GetTapePos(&curtpos) == 0) {
 924                                         /*  curtpos +1000 ???, some drives
 925                                          *  might be too slow */
 926                                         if (tpos != curtpos) {
 927 #ifdef DEBUG_QFA
 928                                                 msg("positioning tape %ld from %lld to %lld for inode %10lu ...\n", volno, curtpos, tpos, (unsigned long)next);
 929 #endif
 930                                                 if (GotoTapePos(tpos) == 0) {
 931 #ifdef DEBUG_QFA
 932                                                         if (GetTapePos(&curtpos) == 0)
 933                                                                 msg("before resync at tape position %lld (%ld, %ld, %s)\n", curtpos, next, curfile.ino, curfile.name);
 934 #endif
 935                                                         ReReadInodeFromTape(next);
 936 #ifdef DEBUG_QFA
 937                                                         if (GetTapePos(&curtpos) == 0)
 938                                                                 msg("after resync at tape position %lld (%ld, %ld, %s)\n", curtpos, next, curfile.ino, curfile.name);
 939 #endif
 940                                                 }
 941                                         }
 942 #ifdef DEBUG_QFA
 943                                         else
 944                                                 msg("already at tape %ld position %ld for inode %10lu ...\n", volno, tpos, (unsigned long)next);
 945 #endif
 946                                 }
 947                         }
 948                 }
 949                 else
 950 #endif /* USA_QFA */
 951                         if (volinfo[1] == ROOTINO) {
 952                                 int i, goodvol = 1;
 953
 954                                 for (i = 1; i < (int)TP_NINOS && volinfo[i] != 0; ++i)
 955                                         if (volinfo[i] < next)
 956                                                 goodvol = i;
 957
 958                                 if (goodvol != volno)
 959                                         RequestVol(goodvol);
 960                         }
 961
 962                 do      {
 963                         curvol = volno;
 964                         while (next > curfile.ino && volno == curvol) {
 965 #ifdef USE_QFA
 966                                 ++tmpcnt;
 967 #endif
 968                                 skipfile();
 969                         }
 970                         skipmaps();
 971                         skipdirs();
 972                 } while (volno == curvol + 1);
 973 #ifdef USE_QFA
 974                 tiend = time(NULL);
 975                 titaken = tiend - tistart;
 976 #ifdef DEBUG_QFA
 977                 if (titaken / 60 > 0)
 978                         msg("%ld reads took %d:%02d:%02d\n",
 979                                 tmpcnt, titaken / 3600,
 980                                 (titaken % 3600) / 60, titaken % 60);
 981 #endif
 982 #endif /* USE_QFA */
 983
 984                 /*
 985                  * If volume change out of order occurred the
 986                  * current state must be recalculated
 987                  */
 988                 if (volno != curvol)
 989                         continue;
 990                 /*
 991                  * If the current inode is greater than the one we were
 992                  * looking for then we missed the one we were looking for.
 993                  * Since we only attempt to extract files listed in the
 994                  * dump map, the lost files must have been due to a tape
 995                  * read error, or a file that was removed while the dump
 996                  * was in progress. Thus we report all requested files
 997                  * between the one we were looking for, and the one we
 998                  * found as missing, and delete their request flags.
 999                  */
1000                 while (next < curfile.ino) {
1001                         ep = lookupino(next);
1002                         if (ep == NULL)
1003                                 panic("corrupted symbol table\n");
1004 #ifdef USE_QFA
1005                         if (!createtapeposflag)
1006                                 fprintf(stderr, "%s: (inode %lu) not found on tape\n",
1007                                         myname(ep), (unsigned long)next);
1008 #endif
1009                         ep->e_flags &= ~NEW;
1010                         next = lowerbnd(next);
1011                 }
1012                 /*
1013                  * The current inode is the one that we are looking for,
1014                  * so extract it per its requested name.
1015                  */
1016                 if (next == curfile.ino && next <= last) {
1017                         ep = lookupino(next);
1018                         if (ep == NULL)
1019                                 panic("corrupted symbol table\n");
1020 #ifdef USE_QFA
1021                         if (createtapeposflag) {
1022 #ifdef DEBUG_QFA
1023                                 msg("inode %ld at tapepos %ld\n", curfile.ino, curtapepos);
1024 #endif
1025                                 sprintf(gTps, "%ld\t%ld\t%lld\n", (unsigned long)curfile.ino, volno, curtapepos);
1026                                 if (write(gTapeposfd, gTps, strlen(gTps)) != (ssize_t)strlen(gTps))
1027                                         warn("error writing tapepos file.\n");
1028                                 skipfile();
1029                         }
1030                         else {
1031                                 msg("restoring %s\n", myname(ep));
1032 #endif /* USE_QFA */
1033                                 (void) extractfile(ep, 0);
1034 #ifdef USE_QFA
1035                         }
1036 #endif /* USE_QFA */
1037                         ep->e_flags &= ~NEW;
1038                         if (volno != curvol)
1039                                 skipmaps();
1040                 }
1041         }
1042 }
1043
1044 /*
1045  * Add links.
1046  */
1047 void
1048 createlinks(void)
1049 {
1050         struct entry *np, *ep;
1051         dump_ino_t i;
1052         char name[BUFSIZ];
1053
1054         if ((ep = lookupino(WINO))) {
1055                 Vprintf(stdout, "Add whiteouts\n");
1056                 for ( ; ep != NULL; ep = ep->e_links) {
1057                         if ((ep->e_flags & NEW) == 0)
1058                                 continue;
1059 #ifdef  __linux__
1060                         (void)fprintf(stderr, "BUG! Should call addwhiteout\n");
1061 #else
1062                         (void) addwhiteout(myname(ep));
1063 #endif
1064                         ep->e_flags &= ~NEW;
1065                 }
1066         }
1067         Vprintf(stdout, "Add links\n");
1068         for (i = ROOTINO; i < maxino; i++) {
1069                 ep = lookupino(i);
1070                 if (ep == NULL)
1071                         continue;
1072                 for (np = ep->e_links; np != NULL; np = np->e_links) {
1073                         if ((np->e_flags & NEW) == 0)
1074                                 continue;
1075                         (void) strcpy(name, myname(ep));
1076                         if (ep->e_type == NODE) {
1077                                 (void) linkit(name, myname(np), SYMLINK);
1078                         } else {
1079                                 (void) linkit(name, myname(np), HARDLINK);
1080                         }
1081                         np->e_flags &= ~NEW;
1082                 }
1083         }
1084 }
1085
1086 /*
1087  * Check the symbol table.
1088  * We do this to insure that all the requested work was done, and
1089  * that no temporary names remain.
1090  */
1091 void
1092 checkrestore(void)
1093 {
1094         struct entry *ep;
1095         dump_ino_t i;
1096
1097         Vprintf(stdout, "Check the symbol table.\n");
1098         for (i = WINO; i < maxino; i++) {
1099                 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
1100                         ep->e_flags &= ~KEEP;
1101                         if (ep->e_type == NODE)
1102                                 ep->e_flags &= ~(NEW|EXISTED);
1103                         if (ep->e_flags /* != NULL */)
1104                                 badentry(ep, "incomplete operations");
1105                 }
1106         }
1107 }
1108
1109 /*
1110  * Compare with the directory structure on the tape
1111  * A paranoid check that things are as they should be.
1112  */
1113 long
1114 verifyfile(char *name, dump_ino_t ino, int type)
1115 {
1116         struct entry *np, *ep;
1117         long descend = GOOD;
1118
1119         ep = lookupname(name);
1120         if (ep == NULL) {
1121                 fprintf(stderr, "Warning: missing name %s\n", name);
1122                 return (FAIL);
1123         }
1124         np = lookupino(ino);
1125         if (np != ep)
1126                 descend = FAIL;
1127         for ( ; np != NULL; np = np->e_links)
1128                 if (np == ep)
1129                         break;
1130         if (np == NULL)
1131                 panic("missing inumber %d\n", ino);
1132         if (ep->e_type == LEAF && type != LEAF)
1133                 badentry(ep, "type should be LEAF");
1134         return (descend);
1135 }