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