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