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