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