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