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