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.1 (Berkeley) 05/28/85"; 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 vprintf(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 any of these arise, something is grievously wrong with 389 * the current state of the symbol table. 390 */ 391 case INOFND|NAMEFND|MODECHG: 392 case NAMEFND|MODECHG: 393 case INOFND|MODECHG: 394 case NIL: 395 panic("[%s] %s: inconsistent state\n", keyval(key), name); 396 break; 397 398 /* 399 * These states "cannot" arise for any state of the symbol table. 400 */ 401 case ONTAPE|MODECHG: 402 case MODECHG: 403 default: 404 panic("[%s] %s: impossible state\n", keyval(key), name); 405 break; 406 } 407 return (descend); 408 } 409 410 /* 411 * Calculate the active flags in a key. 412 */ 413 char * 414 keyval(key) 415 int key; 416 { 417 static char keybuf[32]; 418 419 (void) strcpy(keybuf, "|NIL"); 420 keybuf[0] = '\0'; 421 if (key & ONTAPE) 422 (void) strcat(keybuf, "|ONTAPE"); 423 if (key & INOFND) 424 (void) strcat(keybuf, "|INOFND"); 425 if (key & NAMEFND) 426 (void) strcat(keybuf, "|NAMEFND"); 427 if (key & MODECHG) 428 (void) strcat(keybuf, "|MODECHG"); 429 return (&keybuf[1]); 430 } 431 432 /* 433 * Find unreferenced link names. 434 */ 435 findunreflinks() 436 { 437 register struct entry *ep, *np; 438 register ino_t i; 439 440 vprintf(stdout, "Find unreferenced names.\n"); 441 for (i = ROOTINO; i < maxino; i++) { 442 ep = lookupino(i); 443 if (ep == NIL || ep->e_type == LEAF || BIT(i, dumpmap) == 0) 444 continue; 445 for (np = ep->e_entries; np != NIL; np = np->e_sibling) { 446 if (np->e_flags == 0) { 447 dprintf(stdout, 448 "%s: remove unreferenced name\n", 449 myname(np)); 450 removeleaf(np); 451 freeentry(np); 452 } 453 } 454 } 455 /* 456 * Any leaves remaining in removed directories is unreferenced. 457 */ 458 for (ep = removelist; ep != NIL; ep = ep->e_next) { 459 for (np = ep->e_entries; np != NIL; np = np->e_sibling) { 460 if (np->e_type == LEAF) { 461 if (np->e_flags != 0) 462 badentry(np, "unreferenced with flags"); 463 dprintf(stdout, 464 "%s: remove unreferenced name\n", 465 myname(np)); 466 removeleaf(np); 467 freeentry(np); 468 } 469 } 470 } 471 } 472 473 /* 474 * Remove old nodes (directories). 475 * Note that this routine runs in O(N*D) where: 476 * N is the number of directory entries to be removed. 477 * D is the maximum depth of the tree. 478 * If N == D this can be quite slow. If the list were 479 * topologically sorted, the deletion could be done in 480 * time O(N). 481 */ 482 removeoldnodes() 483 { 484 register struct entry *ep, **prev; 485 long change; 486 487 vprintf(stdout, "Remove old nodes (directories).\n"); 488 do { 489 change = 0; 490 prev = &removelist; 491 for (ep = removelist; ep != NIL; ep = *prev) { 492 if (ep->e_entries != NIL) { 493 prev = &ep->e_next; 494 continue; 495 } 496 *prev = ep->e_next; 497 removenode(ep); 498 freeentry(ep); 499 change++; 500 } 501 } while (change); 502 for (ep = removelist; ep != NIL; ep = ep->e_next) 503 badentry(ep, "cannot remove, non-empty"); 504 } 505 506 /* 507 * This is the routine used to extract files for the 'r' command. 508 * Extract new leaves. 509 */ 510 createleaves(symtabfile) 511 char *symtabfile; 512 { 513 register struct entry *ep; 514 ino_t first; 515 long curvol; 516 517 if (command == 'R') { 518 vprintf(stdout, "Continue extraction of new leaves\n"); 519 } else { 520 vprintf(stdout, "Extract new leaves.\n"); 521 dumpsymtable(symtabfile, volno); 522 } 523 first = lowerbnd(ROOTINO); 524 curvol = volno; 525 while (curfile.ino < maxino) { 526 first = lowerbnd(first); 527 /* 528 * If the next available file is not the one which we 529 * expect then we have missed one or more files. Since 530 * we do not request files that were not on the tape, 531 * the lost files must have been due to a tape read error, 532 * or a file that was removed while the dump was in progress. 533 */ 534 while (first < curfile.ino) { 535 ep = lookupino(first); 536 if (ep == NIL) 537 panic("%d: bad first\n", first); 538 fprintf(stderr, "%s: not found on tape\n", myname(ep)); 539 ep->e_flags &= ~(NEW|EXTRACT); 540 first = lowerbnd(first); 541 } 542 /* 543 * If we find files on the tape that have no corresponding 544 * directory entries, then we must have found a file that 545 * was created while the dump was in progress. Since we have 546 * no name for it, we discard it knowing that it will be 547 * on the next incremental tape. 548 */ 549 if (first != curfile.ino) { 550 fprintf(stderr, "expected next file %d, got %d\n", 551 first, curfile.ino); 552 skipfile(); 553 goto next; 554 } 555 ep = lookupino(curfile.ino); 556 if (ep == NIL) 557 panic("unknown file on tape\n"); 558 if ((ep->e_flags & (NEW|EXTRACT)) == 0) 559 badentry(ep, "unexpected file on tape"); 560 /* 561 * If the file is to be extracted, then the old file must 562 * be removed since its type may change from one leaf type 563 * to another (eg "file" to "character special"). 564 */ 565 if ((ep->e_flags & EXTRACT) != 0) { 566 removeleaf(ep); 567 ep->e_flags &= ~REMOVED; 568 } 569 (void) extractfile(myname(ep)); 570 ep->e_flags &= ~(NEW|EXTRACT); 571 /* 572 * We checkpoint the restore after every tape reel, so 573 * as to simplify the amount of work re quired by the 574 * 'R' command. 575 */ 576 next: 577 if (curvol != volno) { 578 dumpsymtable(symtabfile, volno); 579 skipmaps(); 580 curvol = volno; 581 } 582 } 583 } 584 585 /* 586 * This is the routine used to extract files for the 'x' and 'i' commands. 587 * Efficiently extract a subset of the files on a tape. 588 */ 589 createfiles() 590 { 591 register ino_t first, next, last; 592 register struct entry *ep; 593 long curvol; 594 595 vprintf(stdout, "Extract requested files\n"); 596 curfile.action = SKIP; 597 getvol((long)1); 598 skipmaps(); 599 skipdirs(); 600 first = lowerbnd(ROOTINO); 601 last = upperbnd(maxino - 1); 602 for (;;) { 603 first = lowerbnd(first); 604 last = upperbnd(last); 605 /* 606 * Check to see if any files remain to be extracted 607 */ 608 if (first > last) 609 return; 610 /* 611 * Reject any volumes with inodes greater 612 * than the last one needed 613 */ 614 while (curfile.ino > last) { 615 curfile.action = SKIP; 616 getvol((long)0); 617 skipmaps(); 618 skipdirs(); 619 } 620 /* 621 * Decide on the next inode needed. 622 * Skip across the inodes until it is found 623 * or an out of order volume change is encountered 624 */ 625 next = lowerbnd(curfile.ino); 626 do { 627 curvol = volno; 628 while (next > curfile.ino && volno == curvol) 629 skipfile(); 630 skipmaps(); 631 skipdirs(); 632 } while (volno == curvol + 1); 633 /* 634 * If volume change out of order occurred the 635 * current state must be recalculated 636 */ 637 if (volno != curvol) 638 continue; 639 /* 640 * If the current inode is greater than the one we were 641 * looking for then we missed the one we were looking for. 642 * Since we only attempt to extract files listed in the 643 * dump map, the lost files must have been due to a tape 644 * read error, or a file that was removed while the dump 645 * was in progress. Thus we report all requested files 646 * between the one we were looking for, and the one we 647 * found as missing, and delete their request flags. 648 */ 649 while (next < curfile.ino) { 650 ep = lookupino(next); 651 if (ep == NIL) 652 panic("corrupted symbol table\n"); 653 fprintf(stderr, "%s: not found on tape\n", myname(ep)); 654 ep->e_flags &= ~NEW; 655 next = lowerbnd(next); 656 } 657 /* 658 * The current inode is the one that we are looking for, 659 * so extract it per its requested name. 660 */ 661 if (next == curfile.ino && next <= last) { 662 ep = lookupino(next); 663 if (ep == NIL) 664 panic("corrupted symbol table\n"); 665 (void) extractfile(myname(ep)); 666 ep->e_flags &= ~NEW; 667 if (volno != curvol) 668 skipmaps(); 669 } 670 } 671 } 672 673 /* 674 * Add links. 675 */ 676 createlinks() 677 { 678 register struct entry *np, *ep; 679 register ino_t i; 680 char name[BUFSIZ]; 681 682 vprintf(stdout, "Add links\n"); 683 for (i = ROOTINO; i < maxino; i++) { 684 ep = lookupino(i); 685 if (ep == NIL) 686 continue; 687 for (np = ep->e_links; np != NIL; np = np->e_links) { 688 if ((np->e_flags & NEW) == 0) 689 continue; 690 (void) strcpy(name, myname(ep)); 691 if (ep->e_type == NODE) { 692 (void) linkit(name, myname(np), SYMLINK); 693 } else { 694 (void) linkit(name, myname(np), HARDLINK); 695 } 696 np->e_flags &= ~NEW; 697 } 698 } 699 } 700 701 /* 702 * Check the symbol table. 703 * We do this to insure that all the requested work was done, and 704 * that no temporary names remain. 705 */ 706 checkrestore() 707 { 708 register struct entry *ep; 709 register ino_t i; 710 711 vprintf(stdout, "Check the symbol table.\n"); 712 for (i = ROOTINO; i < maxino; i++) { 713 for (ep = lookupino(i); ep != NIL; ep = ep->e_links) { 714 ep->e_flags &= ~KEEP; 715 if (ep->e_type == NODE) 716 ep->e_flags &= ~(NEW|EXISTED); 717 if (ep->e_flags != NULL) 718 badentry(ep, "incomplete operations"); 719 } 720 } 721 } 722 723 /* 724 * Compare with the directory structure on the tape 725 * A paranoid check that things are as they should be. 726 */ 727 long 728 verifyfile(name, ino, type) 729 char *name; 730 ino_t ino; 731 int type; 732 { 733 struct entry *np, *ep; 734 long descend = GOOD; 735 736 ep = lookupname(name); 737 if (ep == NIL) { 738 fprintf(stderr, "Warning: missing name %s\n", name); 739 return (FAIL); 740 } 741 np = lookupino(ino); 742 if (np != ep) 743 descend = FAIL; 744 for ( ; np != NIL; np = np->e_links) 745 if (np == ep) 746 break; 747 if (np == NIL) 748 panic("missing inumber %d\n", ino); 749 if (ep->e_type == LEAF && type != LEAF) 750 badentry(ep, "type should be LEAF"); 751 return (descend); 752 } 753