2 * SPDX-License-Identifier: BSD-3-Clause
4 * Copyright (c) 1983, 1993
5 * The Regents of the University of California. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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.
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
34 static char sccsid[] = "@(#)restore.c 8.3 (Berkeley) 9/13/94";
38 #include <sys/cdefs.h>
39 __FBSDID("$FreeBSD$");
41 #include <sys/types.h>
48 #include <ufs/ufs/dinode.h>
53 static char *keyval(int);
56 * This implements the 't' option.
57 * List entries on the tape.
60 listfile(char *name, ino_t ino, int type)
62 long descend = hflag ? GOOD : FAIL;
64 if (TSTINO(ino, dumpmap) == 0)
66 vprintf(stdout, "%s", type == LEAF ? "leaf" : "dir ");
67 fprintf(stdout, "%10ju\t%s\n", (uintmax_t)ino, name);
72 * This implements the 'x' option.
73 * Request that new entries be extracted.
76 addfile(char *name, ino_t ino, int type)
79 long descend = hflag ? GOOD : FAIL;
82 if (TSTINO(ino, dumpmap) == 0) {
83 dprintf(stdout, "%s: not on the tape\n", name);
86 if (ino == UFS_WINO && command == 'i' && !vflag)
89 (void) sprintf(buf, "./%ju", (uintmax_t)ino);
92 (void) genliteraldir(name, ino);
98 if (strcmp(name, myname(ep)) == 0) {
104 ep = addentry(name, ino, type);
112 * This is used by the 'i' option to undo previous requests made by addfile.
113 * Delete entries from the request queue.
117 deletefile(char *name, ino_t ino, int type)
119 long descend = hflag ? GOOD : FAIL;
122 if (TSTINO(ino, dumpmap) == 0)
124 ep = lookupname(name);
127 ep->e_flags |= REMOVED;
128 if (ep->e_type != NODE)
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.
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.
147 static struct entry *removelist;
150 * Remove invalid whiteouts from the old tree.
151 * Remove unneeded leaves from the old tree.
152 * Remove directories from the lookup chains.
155 removeoldleaves(void)
157 struct entry *ep, *nextep;
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;
167 * We remove all whiteouts that are in directories
168 * that have been removed or that have been dumped.
170 if (TSTINO(mydirino, usedinomap) &&
171 !TSTINO(mydirino, dumpmap))
177 for (i = UFS_ROOTINO + 1; i < maxino; i++) {
181 if (TSTINO(i, usedinomap))
183 for ( ; ep != NULL; ep = ep->e_links) {
184 dprintf(stdout, "%s: REMOVE\n", myname(ep));
185 if (ep->e_type == LEAF) {
190 deleteino(ep->e_ino);
191 ep->e_next = removelist;
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.
208 nodeupdates(char *name, ino_t ino, int type)
210 struct entry *ep, *np, *ip;
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 */
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.
226 * Check to see if the file is on the tape.
228 if (TSTINO(ino, dumpmap))
231 * Check to see if the name exists, and if the name is a link.
233 np = lookupname(name);
236 ip = lookupino(np->e_ino);
238 panic("corrupted symbol table\n");
243 * Check to see if the inode exists, and if one of its links
244 * corresponds to the name (if one was found).
249 for (ep = ip->e_links; ep != NULL; ep = ep->e_links) {
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.
269 if (((key & (INOFND|NAMEFND)) == (INOFND|NAMEFND)) && ip != np) {
270 if (lookuptype == LINK) {
274 dprintf(stdout, "name/inode conflict, mktempname %s\n",
281 if ((key & ONTAPE) &&
282 (((key & INOFND) && ip->e_type != type) ||
283 ((key & NAMEFND) && np->e_type != type)))
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.
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.
302 dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
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.
318 case ONTAPE|NAMEFND|MODECHG:
319 if (lookuptype == LINK) {
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)
334 ep = addentry(name, ino, type);
337 ep->e_flags |= NEW|KEEP;
338 dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
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.
354 if (type == LEAF && (ip->e_flags & KEEP) == 0)
355 ip->e_flags |= EXTRACT;
358 if ((ip->e_flags & KEEP) == 0) {
359 renameit(myname(ip), name);
362 dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
366 if (ip->e_type == NODE) {
369 "deleted hard link %s to directory %s\n",
373 ep = addentry(name, ino, type|LINK);
375 dprintf(stdout, "[%s] %s: %s|LINK\n", keyval(key), name,
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.
384 case ONTAPE|INOFND|NAMEFND:
385 if (lookuptype == LINK) {
388 ep = addentry(name, ino, type|LINK);
391 ep->e_flags |= NEW|KEEP;
392 dprintf(stdout, "[%s] %s: %s|LINK\n", keyval(key), name,
396 if (type == LEAF && lookuptype != LINK)
397 np->e_flags |= EXTRACT;
399 dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
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
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");
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");
429 ip = addentry(name, ino, type);
432 /* changing from node to leaf */
433 if ((ip->e_flags & TMPNAME) == 0)
435 deleteino(ip->e_ino);
436 ip->e_next = removelist;
438 ip = addentry(name, ino, type);
440 ip->e_flags |= NEW|KEEP;
441 dprintf(stdout, "[%s] %s: %s\n", keyval(key), name,
446 * A hard link to a directory that has been removed.
450 dprintf(stdout, "[%s] %s: Extraneous name\n", keyval(key),
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.
463 fprintf(stderr, "%s: (inode %ju) not found on tape\n",
464 name, (uintmax_t)ino);
468 * If any of these arise, something is grievously wrong with
469 * the current state of the symbol table.
471 case INOFND|NAMEFND|MODECHG:
472 case NAMEFND|MODECHG:
474 fprintf(stderr, "[%s] %s: inconsistent state\n", keyval(key),
479 * These states "cannot" arise for any state of the symbol table.
484 panic("[%s] %s: impossible state\n", keyval(key), name);
491 * Calculate the active flags in a key.
496 static char keybuf[32];
498 (void) strcpy(keybuf, "|NIL");
501 (void) strcat(keybuf, "|ONTAPE");
503 (void) strcat(keybuf, "|INOFND");
505 (void) strcat(keybuf, "|NAMEFND");
507 (void) strcat(keybuf, "|MODECHG");
512 * Find unreferenced link names.
517 struct entry *ep, *np;
520 vprintf(stdout, "Find unreferenced names.\n");
521 for (i = UFS_ROOTINO; i < maxino; i++) {
523 if (ep == NULL || ep->e_type == LEAF || TSTINO(i, dumpmap) == 0)
525 for (np = ep->e_entries; np != NULL; np = np->e_sibling) {
526 if (np->e_flags == 0) {
528 "%s: remove unreferenced name\n",
536 * Any leaves remaining in removed directories is unreferenced.
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");
544 "%s: remove unreferenced name\n",
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
565 struct entry *ep, **prev;
568 vprintf(stdout, "Remove old nodes (directories).\n");
572 for (ep = removelist; ep != NULL; ep = *prev) {
573 if (ep->e_entries != NULL) {
583 for (ep = removelist; ep != NULL; ep = ep->e_next)
584 badentry(ep, "cannot remove, non-empty");
588 * This is the routine used to extract files for the 'r' command.
589 * Extract new leaves.
592 createleaves(char *symtabfile)
598 if (command == 'R') {
599 vprintf(stdout, "Continue extraction of new leaves\n");
601 vprintf(stdout, "Extract new leaves.\n");
602 dumpsymtable(symtabfile, volno);
604 first = lowerbnd(UFS_ROOTINO);
606 while (curfile.ino < maxino) {
607 first = lowerbnd(first);
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.
615 while (first < curfile.ino) {
616 ep = lookupino(first);
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);
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.
630 if (first != curfile.ino) {
631 fprintf(stderr, "expected next file %ju, got %ju\n",
632 (uintmax_t)first, (uintmax_t)curfile.ino);
636 ep = lookupino(curfile.ino);
638 panic("unknown file on tape\n");
639 if ((ep->e_flags & (NEW|EXTRACT)) == 0)
640 badentry(ep, "unexpected file on tape");
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").
646 if ((ep->e_flags & EXTRACT) != 0) {
648 ep->e_flags &= ~REMOVED;
650 (void) extractfile(myname(ep));
651 ep->e_flags &= ~(NEW|EXTRACT);
653 * We checkpoint the restore after every tape reel, so
654 * as to simplify the amount of work required by the
658 if (curvol != volno) {
659 dumpsymtable(symtabfile, volno);
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.
673 ino_t first, next, last;
677 vprintf(stdout, "Extract requested files\n");
678 curfile.action = SKIP;
682 first = lowerbnd(UFS_ROOTINO);
683 last = upperbnd(maxino - 1);
686 first = lowerbnd(first);
687 last = upperbnd(last);
689 * Check to see if any files remain to be extracted
694 if (curfile.ino == maxino)
696 if((ep = lookupino(curfile.ino)) != NULL &&
697 (ep->e_flags & (NEW|EXTRACT))) {
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.
711 if (curfile.ino > last && curfile.ino < maxino && volno > 1) {
712 curfile.action = SKIP;
719 * Decide on the next inode needed.
720 * Skip across the inodes until it is found
721 * or a volume change is encountered
723 if (curfile.ino < maxino) {
724 next = lowerbnd(curfile.ino);
725 while (next > curfile.ino && volno == curvol)
727 if (volno != curvol) {
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.
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.
750 while (next < curfile.ino) {
751 ep = lookupino(next);
753 panic("corrupted symbol table\n");
754 fprintf(stderr, "%s: not found on tape\n", myname(ep));
756 next = lowerbnd(next);
759 * The current inode is the one that we are looking for,
760 * so extract it per its requested name.
762 if (next == curfile.ino && next <= last) {
763 ep = lookupino(next);
765 panic("corrupted symbol table\n");
767 (void) extractfile(myname(ep));
781 struct entry *np, *ep;
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)
790 (void) addwhiteout(myname(ep));
794 vprintf(stdout, "Add links\n");
795 for (i = UFS_ROOTINO; i < maxino; i++) {
799 for (np = ep->e_links; np != NULL; np = np->e_links) {
800 if ((np->e_flags & NEW) == 0)
802 (void) strcpy(name, myname(ep));
803 if (ep->e_type == NODE) {
804 (void) linkit(name, myname(np), SYMLINK);
806 (void) linkit(name, myname(np), HARDLINK);
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.
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");
837 * Compare with the directory structure on the tape
838 * A paranoid check that things are as they should be.
841 verifyfile(char *name, ino_t ino, int type)
843 struct entry *np, *ep;
846 ep = lookupname(name);
848 fprintf(stderr, "Warning: missing name %s\n", name);
854 for ( ; np != NULL; np = np->e_links)
858 panic("missing inumber %ju\n", (uintmax_t)ino);
859 if (ep->e_type == LEAF && type != LEAF)
860 badentry(ep, "type should be LEAF");