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