git.gag.com Git - debian/dump/blob - restore/restore.c

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