restore/restore.c

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