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