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.3 (Berkeley) 6/18/87";
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
listfile(name,ino,type)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
addfile(name,ino,type)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
deletefile(name,ino,type)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 */
removeoldleaves()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
nodeupdates(name,ino,type)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 *
keyval(key)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 */
findunreflinks()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 */
removeoldnodes()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 */
createleaves(symtabfile)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 */
createfiles()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 */
createlinks()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 */
checkrestore()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
verifyfile(name,ino,type)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