sbin/restore/restore.c

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