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.39 2010/03/22 16:08:10 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  * This also takes care of directories which were missed by removeoldleaves(),
 571  * because their inode has been reused, but excluded from the dump.
 572  */
 573 void
 574 findunreflinks(void)
 575 {
 576         struct entry *ep, *np;
 577         dump_ino_t i;
 578         int j;
 579
 580         Vprintf(stdout, "Find unreferenced names.\n");
 581         for (i = ROOTINO; i < maxino; i++) {
 582                 ep = lookupino(i);
 583                 if (ep == NULL || ep->e_type == LEAF || TSTINO(i, dumpmap) == 0)
 584                         continue;
 585                 if (ep->e_entries == NULL)
 586                         continue;
 587                 for (j = 0; j < dirhash_size; j++) {
 588                         for (np = ep->e_entries[j]; np != NULL; np = np->e_sibling) {
 589                                 if ((np->e_flags & ~TMPNAME) == 0) {
 590                                         Dprintf(stdout,
 591                                             "%s: remove unreferenced name\n",
 592                                             myname(np));
 593                                         if (np->e_type == LEAF) {
 594                                                 removeleaf(np);
 595                                                 freeentry(np);
 596                                         } else {
 597                                                 np->e_flags |= TMPNAME;
 598                                                 deleteino(np->e_ino);
 599                                                 np->e_next = removelist;
 600                                                 removelist = np;
 601                                         }
 602                                 }
 603                         }
 604                 }
 605         }
 606         /*
 607          * Any leaves remaining in removed directories is unreferenced.
 608          */
 609         for (ep = removelist; ep != NULL; ep = ep->e_next) {
 610                 if (ep->e_entries == NULL)
 611                         continue;
 612                 for (j = 0; j < dirhash_size; j++) {
 613                         for (np = ep->e_entries[j]; np != NULL; np = np->e_sibling) {
 614                                 if (np->e_type == LEAF) {
 615                                         if (np->e_flags != 0)
 616                                                 badentry(np, "unreferenced with flags");
 617                                         Dprintf(stdout,
 618                                             "%s: remove unreferenced name\n",
 619                                             myname(np));
 620                                         removeleaf(np);
 621                                         freeentry(np);
 622                                 } else {
 623                                         if ((np->e_flags & ~TMPNAME) != 0)
 624                                                 badentry(np, "unreferenced with flags");
 625
 626                                         if (np->e_flags == 0) {
 627                                                 Dprintf(stdout,
 628                                                     "%s: remove unreferenced name\n",
 629                                                     myname(np));
 630                                                 np->e_next = ep->e_next;
 631                                                 ep->e_next = np;
 632                                         }
 633                                 }
 634                         }
 635                 }
 636         }
 637 }
 638
 639 /*
 640  * Remove old nodes (directories).
 641  * Note that this routine runs in O(N*D) where:
 642  *      N is the number of directory entries to be removed.
 643  *      D is the maximum depth of the tree.
 644  * If N == D this can be quite slow. If the list were
 645  * topologically sorted, the deletion could be done in
 646  * time O(N).
 647  */
 648 void
 649 removeoldnodes(void)
 650 {
 651         struct entry *ep, **prev;
 652         long change;
 653
 654         Vprintf(stdout, "Remove old nodes (directories).\n");
 655         do      {
 656                 change = 0;
 657                 prev = &removelist;
 658                 for (ep = removelist; ep != NULL; ep = *prev) {
 659                         int docont = 0;
 660                         if (ep->e_entries != NULL) {
 661                                 int i;
 662                                 for (i = 0; i < dirhash_size; i++) {
 663                                         if (ep->e_entries[i] != NULL) {
 664                                                 prev = &ep->e_next;
 665                                                 docont = 1;
 666                                                 break;
 667                                         }
 668                                 }
 669                         }
 670                         if (docont)
 671                                 continue;
 672                         *prev = ep->e_next;
 673                         removenode(ep);
 674                         freeentry(ep);
 675                         change++;
 676                 }
 677         } while (change);
 678         for (ep = removelist; ep != NULL; ep = ep->e_next)
 679                 badentry(ep, "cannot remove, non-empty");
 680 }
 681
 682 /* Compare the file specified in `ep' (which is on tape) to the */
 683 /* current copy of this file on disk.  If do_compare is 0, then just */
 684 /* make our caller think we did it--this is used to handle hard links */
 685 /* to files and devices. */
 686 static void
 687 compare_entry(struct entry *ep, int do_compare)
 688 {
 689         if ((ep->e_flags & (NEW|EXTRACT)) == 0) {
 690                 badentry(ep, "unexpected file on tape");
 691                 do_compare_error;
 692         }
 693         if (do_compare) {
 694                 (void) comparefile(myname(ep));
 695                 skipxattr();
 696         }
 697         ep->e_flags &= ~(NEW|EXTRACT);
 698 }
 699
 700 /*
 701  * This is the routine used to compare files for the 'C' command.
 702  */
 703 void
 704 compareleaves(void)
 705 {
 706         struct entry *ep;
 707         dump_ino_t first;
 708         long curvol;
 709
 710         first = lowerbnd(ROOTINO);
 711         curvol = volno;
 712         while (curfile.ino < maxino) {
 713                 first = lowerbnd(first);
 714                 /*
 715                  * If the next available file is not the one which we
 716                  * expect then we have missed one or more files. Since
 717                  * we do not request files that were not on the tape,
 718                  * the lost files must have been due to a tape read error,
 719                  * or a file that was removed while the dump was in progress.
 720                  */
 721                 while (first < curfile.ino) {
 722                         ep = lookupino(first);
 723                         if (ep == NULL)
 724                                 panic("%d: bad first\n", first);
 725                         fprintf(stderr, "%s: not found on tape\n", myname(ep));
 726                         do_compare_error;
 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                         do_compare_error;
 747                 }
 748                 compare_entry(ep, 1);
 749                 for (ep = ep->e_links; ep != NULL; ep = ep->e_links) {
 750                         compare_entry(ep, 0);
 751                 }
 752
 753                 /*
 754                  * We checkpoint the restore after every tape reel, so
 755                  * as to simplify the amount of work re quired by the
 756                  * 'R' command.
 757                  */
 758         next:
 759                 if (curvol != volno) {
 760                         skipmaps();
 761                         curvol = volno;
 762                 }
 763         }
 764         /*
 765          * If we encounter the end of the tape and the next available
 766          * file is not the one which we expect then we have missed one
 767          * or more files. Since we do not request files that were not
 768          * on the tape, the lost files must have been due to a tape
 769          * read error, or a file that was removed while the dump was
 770          * in progress.
 771          */
 772         first = lowerbnd(first);
 773         while (first < curfile.ino) {
 774                 ep = lookupino(first);
 775                 if (ep == NULL)
 776                         panic("%d: bad first\n", first);
 777                 fprintf(stderr, "%s: (inode %lu) not found on tape\n",
 778                         myname(ep), (unsigned long)first);
 779                 do_compare_error;
 780                 ep->e_flags &= ~(NEW|EXTRACT);
 781                 first = lowerbnd(first);
 782         }
 783 }
 784
 785 /*
 786  * This is the routine used to extract files for the 'r' command.
 787  * Extract new leaves.
 788  */
 789 void
 790 createleaves(char *symtabfile)
 791 {
 792         struct entry *ep;
 793         dump_ino_t first;
 794         long curvol;
 795         int doremove;
 796
 797         if (command == 'R') {
 798                 Vprintf(stdout, "Continue extraction of new leaves\n");
 799         } else {
 800                 Vprintf(stdout, "Extract new leaves.\n");
 801                 dumpsymtable(symtabfile, volno);
 802         }
 803         first = lowerbnd(ROOTINO);
 804         curvol = volno;
 805         while (curfile.ino < maxino) {
 806                 first = lowerbnd(first);
 807                 /*
 808                  * If the next available file is not the one which we
 809                  * expect then we have missed one or more files. Since
 810                  * we do not request files that were not on the tape,
 811                  * the lost files must have been due to a tape read error,
 812                  * or a file that was removed while the dump was in progress.
 813                  */
 814                 while (first < curfile.ino) {
 815                         ep = lookupino(first);
 816                         if (ep == NULL)
 817                                 panic("%d: bad first\n", first);
 818                         fprintf(stderr, "%s: (inode %lu) not found on tape\n",
 819                                 myname(ep), (unsigned long)first);
 820                         ep->e_flags &= ~(NEW|EXTRACT);
 821                         first = lowerbnd(first);
 822                 }
 823                 /*
 824                  * If we find files on the tape that have no corresponding
 825                  * directory entries, then we must have found a file that
 826                  * was created while the dump was in progress. Since we have
 827                  * no name for it, we discard it knowing that it will be
 828                  * on the next incremental tape.
 829                  */
 830                 if (first != curfile.ino) {
 831                         fprintf(stderr, "expected next file %ld, got %lu\n",
 832                                 (long)first, (unsigned long)curfile.ino);
 833                         skipfile();
 834                         goto next;
 835                 }
 836                 ep = lookupino(curfile.ino);
 837                 if (ep == NULL)
 838                         panic("unknown file on tape\n");
 839                 if ((ep->e_flags & (NEW|EXTRACT)) == 0)
 840                         badentry(ep, "unexpected file on tape");
 841                 /*
 842                  * If the file is to be extracted, then the old file must
 843                  * be removed since its type may change from one leaf type
 844                  * to another (e.g. "file" to "character special").
 845                  */
 846                 if ((ep->e_flags & EXTRACT) != 0)
 847                         doremove = 1;
 848                 else
 849                         doremove = 0;
 850                 (void) extractfile(ep, doremove);
 851                 skipxattr();
 852                 ep->e_flags &= ~(NEW|EXTRACT);
 853
 854                 /*
 855                  * We checkpoint the restore after every tape reel, so
 856                  * as to simplify the amount of work required by the
 857                  * 'R' command.
 858                  */
 859 next:
 860                 if (curvol != volno) {
 861                         dumpsymtable(symtabfile, volno);
 862                         skipmaps();
 863                         curvol = volno;
 864                 }
 865         }
 866         /*
 867          * If we encounter the end of the tape and the next available
 868          * file is not the one which we expect then we have missed one
 869          * or more files. Since we do not request files that were not
 870          * on the tape, the lost files must have been due to a tape
 871          * read error, or a file that was removed while the dump was
 872          * in progress.
 873          */
 874         first = lowerbnd(first);
 875         while (first < curfile.ino) {
 876                 ep = lookupino(first);
 877                 if (ep == NULL)
 878                         panic("%d: bad first\n", first);
 879                 fprintf(stderr, "%s: (inode %lu) not found on tape\n",
 880                         myname(ep), (unsigned long)first);
 881                 do_compare_error;
 882                 ep->e_flags &= ~(NEW|EXTRACT);
 883                 first = lowerbnd(first);
 884         }
 885 }
 886
 887 /*
 888  * This is the routine used to extract files for the 'x' and 'i' commands.
 889  * Efficiently extract a subset of the files on a tape.
 890  */
 891 void
 892 createfiles(void)
 893 {
 894         dump_ino_t first, next, last;
 895         struct entry *ep;
 896         long curvol;
 897 #ifdef USE_QFA
 898         long tnum, tmpcnt;
 899         long long tpos, curtpos = 0;
 900         time_t tistart, tiend, titaken;
 901         int             volChg;
 902 #endif
 903
 904         Vprintf(stdout, "Extract requested files\n");
 905         curfile.action = SKIP;
 906 #ifdef USE_QFA
 907         if (tapeposflag)
 908                 curfile.ino = 0;
 909         else
 910 #endif
 911                 if (volinfo[1] == ROOTINO)
 912                         curfile.ino = 0;
 913                 else
 914                         getvol((long)1);
 915         skipmaps();
 916         skipdirs();
 917         first = lowerbnd(ROOTINO);
 918         last = upperbnd(maxino - 1);
 919         for (;;) {
 920 #ifdef USE_QFA
 921                 tmpcnt = 1;
 922 #endif
 923                 first = lowerbnd(first);
 924                 last = upperbnd(last);
 925                 /*
 926                  * Check to see if any files remain to be extracted
 927                  */
 928                 if (first > last)
 929                         return;
 930                 /*
 931                  * Reject any volumes with inodes greater
 932                  * than the last one needed
 933                  */
 934                 while (curfile.ino > last) {
 935                         curfile.action = SKIP;
 936                         if (!pipein)
 937                                 getvol((long)0);
 938                         if (curfile.ino == maxino) {
 939                                 next = lowerbnd(first);
 940                                 while (next < curfile.ino) {
 941                                         ep = lookupino(next);
 942                                         if (ep == NULL)
 943                                                 panic("corrupted symbol table\n");
 944                                         fprintf(stderr, "%s: (inode %lu) not found on tape\n",
 945                                                 myname(ep), (unsigned long)next);
 946                                         ep->e_flags &= ~NEW;
 947                                         next = lowerbnd(next);
 948                                 }
 949                                 return;
 950                         }
 951                         skipmaps();
 952                         skipdirs();
 953                 }
 954                 /*
 955                  * Decide on the next inode needed.
 956                  * Skip across the inodes until it is found
 957                  * or an out of order volume change is encountered
 958                  */
 959                 next = lowerbnd(curfile.ino);
 960 #ifdef USE_QFA
 961                 tistart = time(NULL);
 962                 if (tapeposflag) {
 963                         /* get tape position for inode */
 964                         (void)Inode2Tapepos(next, &tnum, &tpos, 0);
 965                         if (tpos != 0) {
 966                                 if (tnum != volno) {
 967                                         (void)RequestVol(tnum);
 968                                         volChg = 1;
 969                                 } else {
 970                                         volChg = 0;
 971                                 }
 972                                 if (GetTapePos(&curtpos) == 0) {
 973                                         /*  curtpos +1000 ???, some drives
 974                                          *  might be too slow */
 975                                         if (((tpos > (curtpos + 1000)) && (volChg == 0)) || ((tpos != curtpos) && (volChg == 1))) {
 976                                                 volChg = 0;
 977 #ifdef DEBUG_QFA
 978                                                 msg("positioning tape %ld from %lld to %lld for inode %lu ...\n", volno, curtpos, tpos, (unsigned long)next);
 979 #endif
 980                                                 if (GotoTapePos(tpos) == 0) {
 981 #ifdef DEBUG_QFA
 982                                                         if (GetTapePos(&curtpos) == 0) {
 983                                                                 msg("before resnyc at tape position %lld (%ld, %ld, %s)\n", curtpos, next, curfile.ino, curfile.name);
 984                                                         }
 985 #endif
 986                                                         ReReadInodeFromTape(next);
 987 #ifdef DEBUG_QFA
 988                                                         if (GetTapePos(&curtpos) == 0) {
 989                                                                 msg("after resnyc at tape position %lld (%ld, %ld, %s)\n", curtpos, next, curfile.ino, curfile.name);
 990                                                         }
 991 #endif
 992                                                 }
 993                                         } else {
 994 #ifdef DEBUG_QFA
 995                                                 msg("already at tape %ld position %ld for inode %lu ...\n", volno, tpos, (unsigned long)next);
 996 #endif
 997                                         }
 998                                 }
 999                         }
1000                 }
1001                 else
1002 #endif /* USA_QFA */
1003                         if (volinfo[1] == ROOTINO) {
1004                                 int i, goodvol = 1;
1005
1006                                 for (i = 1; i < (int)TP_NINOS && volinfo[i] != 0; ++i)
1007                                         if (volinfo[i] < next)
1008                                                 goodvol = i;
1009
1010                                 if (goodvol != volno)
1011                                         RequestVol(goodvol);
1012                         }
1013
1014                 do      {
1015                         curvol = volno;
1016                         while (next > curfile.ino && volno == curvol) {
1017 #ifdef USE_QFA
1018                                 ++tmpcnt;
1019 #endif
1020                                 skipfile();
1021                         }
1022                         skipmaps();
1023                         skipdirs();
1024                 } while (volno == curvol + 1);
1025 #ifdef USE_QFA
1026                 tiend = time(NULL);
1027                 titaken = tiend - tistart;
1028 #ifdef DEBUG_QFA
1029                 if (titaken / 60 > 0)
1030                         msg("%ld reads took %d:%02d:%02d\n",
1031                                 tmpcnt, titaken / 3600,
1032                                 (titaken % 3600) / 60, titaken % 60);
1033 #endif
1034 #endif /* USE_QFA */
1035
1036                 /*
1037                  * If volume change out of order occurred the
1038                  * current state must be recalculated
1039                  */
1040                 if (volno != curvol)
1041                         continue;
1042                 /*
1043                  * If the current inode is greater than the one we were
1044                  * looking for then we missed the one we were looking for.
1045                  * Since we only attempt to extract files listed in the
1046                  * dump map, the lost files must have been due to a tape
1047                  * read error, or a file that was removed while the dump
1048                  * was in progress. Thus we report all requested files
1049                  * between the one we were looking for, and the one we
1050                  * found as missing, and delete their request flags.
1051                  */
1052                 while (next < curfile.ino) {
1053                         ep = lookupino(next);
1054                         if (ep == NULL)
1055                                 panic("corrupted symbol table\n");
1056 #ifdef USE_QFA
1057                         if (!createtapeposflag)
1058 #endif
1059                                 fprintf(stderr, "%s: (inode %lu) not found on tape\n",
1060                                         myname(ep), (unsigned long)next);
1061                         ep->e_flags &= ~NEW;
1062                         next = lowerbnd(next);
1063                 }
1064                 /*
1065                  * The current inode is the one that we are looking for,
1066                  * so extract it per its requested name.
1067                  */
1068                 if (next == curfile.ino && next <= last) {
1069                         ep = lookupino(next);
1070                         if (ep == NULL)
1071                                 panic("corrupted symbol table\n");
1072 #ifdef USE_QFA
1073                         if (createtapeposflag) {
1074 #ifdef DEBUG_QFA
1075                                 msg("inode %ld at tapepos %ld\n", curfile.ino, curtapepos);
1076 #endif
1077                                 sprintf(gTps, "%ld\t%ld\t%lld\n", (unsigned long)curfile.ino, volno, curtapepos);
1078                                 if (write(gTapeposfd, gTps, strlen(gTps)) != (ssize_t)strlen(gTps))
1079                                         warn("error writing tapepos file.\n");
1080                                 skipfile();
1081                         } else {
1082 #endif /* USE_QFA */
1083                                 (void) extractfile(ep, 0);
1084                                 skipxattr();
1085
1086 #ifdef USE_QFA
1087                         }
1088 #endif /* USE_QFA */
1089                         ep->e_flags &= ~NEW;
1090                         if (volno != curvol)
1091                                 skipmaps();
1092                 }
1093         }
1094 }
1095
1096 /*
1097  * Add links.
1098  */
1099 void
1100 createlinks(void)
1101 {
1102         struct entry *np, *ep;
1103         dump_ino_t i;
1104         char name[BUFSIZ];
1105
1106         if ((ep = lookupino(WINO))) {
1107                 Vprintf(stdout, "Add whiteouts\n");
1108                 for ( ; ep != NULL; ep = ep->e_links) {
1109                         if ((ep->e_flags & NEW) == 0)
1110                                 continue;
1111 #ifdef  __linux__
1112                         (void)fprintf(stderr, "BUG! Should call addwhiteout\n");
1113 #else
1114 #ifdef sunos
1115 #else
1116                         (void) addwhiteout(myname(ep));
1117 #endif
1118 #endif
1119                         ep->e_flags &= ~NEW;
1120                 }
1121         }
1122         Vprintf(stdout, "Add links\n");
1123         for (i = ROOTINO; i < maxino; i++) {
1124                 ep = lookupino(i);
1125                 if (ep == NULL)
1126                         continue;
1127                 for (np = ep->e_links; np != NULL; np = np->e_links) {
1128                         if ((np->e_flags & NEW) == 0)
1129                                 continue;
1130                         (void) strcpy(name, myname(ep));
1131                         if (ep->e_type == NODE) {
1132                                 (void) linkit(name, myname(np), SYMLINK);
1133                         } else {
1134                                 (void) linkit(name, myname(np), HARDLINK);
1135                         }
1136                         np->e_flags &= ~NEW;
1137                 }
1138         }
1139 }
1140
1141 /*
1142  * Check the symbol table.
1143  * We do this to insure that all the requested work was done, and
1144  * that no temporary names remain.
1145  */
1146 void
1147 checkrestore(void)
1148 {
1149         struct entry *ep;
1150         dump_ino_t i;
1151
1152         Vprintf(stdout, "Check the symbol table.\n");
1153         for (i = WINO; i < maxino; i++) {
1154                 for (ep = lookupino(i); ep != NULL; ep = ep->e_links) {
1155                         ep->e_flags &= ~KEEP;
1156                         if (ep->e_type == NODE)
1157                                 ep->e_flags &= ~(NEW|EXISTED);
1158                         if (ep->e_flags /* != NULL */)
1159                                 badentry(ep, "incomplete operations");
1160                 }
1161         }
1162 }
1163
1164 /*
1165  * Compare with the directory structure on the tape
1166  * A paranoid check that things are as they should be.
1167  */
1168 long
1169 verifyfile(char *name, dump_ino_t ino, int type)
1170 {
1171         struct entry *np, *ep;
1172         long descend = GOOD;
1173
1174         ep = lookupname(name);
1175         if (ep == NULL) {
1176                 fprintf(stderr, "Warning: missing name %s\n", name);
1177                 return (FAIL);
1178         }
1179         np = lookupino(ino);
1180         if (np != ep)
1181                 descend = FAIL;
1182         for ( ; np != NULL; np = np->e_links)
1183                 if (np == ep)
1184                         break;
1185         if (np == NULL)
1186                 panic("missing inumber %d\n", ino);
1187         if (ep->e_type == LEAF && type != LEAF)
1188                 badentry(ep, "type should be LEAF");
1189         return (descend);
1190 }