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