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