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