* Copyright (c) 1983 The Regents of the University of California.
* %sccs.include.redist.c%
static char sccsid
[] = "@(#)restore.c 5.7 (Berkeley) %G%";
* This implements the 't' option.
* List entries on the tape.
listfile(name
, ino
, type
)
long descend
= hflag
? GOOD
: FAIL
;
if (BIT(ino
, dumpmap
) == 0) {
vprintf(stdout
, "%s", type
== LEAF
? "leaf" : "dir ");
fprintf(stdout
, "%10d\t%s\n", ino
, name
);
* This implements the 'x' option.
* Request that new entries be extracted.
register struct entry
*ep
;
long descend
= hflag
? GOOD
: FAIL
;
if (BIT(ino
, dumpmap
) == 0) {
dprintf(stdout
, "%s: not on the tape\n", name
);
(void) sprintf(buf
, "./%u", ino
);
(void) genliteraldir(name
, ino
);
if (strcmp(name
, myname(ep
)) == 0) {
ep
= addentry(name
, ino
, type
);
* This is used by the 'i' option to undo previous requests made by addfile.
* Delete entries from the request queue.
deletefile(name
, ino
, type
)
long descend
= hflag
? GOOD
: FAIL
;
if (BIT(ino
, dumpmap
) == 0) {
* The following four routines implement the incremental
* restore algorithm. The first removes old entries, the second
* does renames and calculates the extraction list, the third
* cleans up link names missed by the first two, and the final
* one deletes old directories.
* Directories cannot be immediately deleted, as they may have
* other files in them which need to be moved out first. As
* directories to be deleted are found, they are put on the
* following deletion list. After all deletions and renames
* are done, this list is actually deleted.
static struct entry
*removelist
;
* Remove unneeded leaves from the old tree.
* Remove directories from the lookup chains.
register struct entry
*ep
;
vprintf(stdout
, "Mark entries to be removed.\n");
for (i
= ROOTINO
+ 1; i
< maxino
; i
++) {
for ( ; ep
!= NIL
; ep
= ep
->e_links
) {
dprintf(stdout
, "%s: REMOVE\n", myname(ep
));
if (ep
->e_type
== LEAF
) {
* For each directory entry on the incremental tape, determine which
* category it falls into as follows:
* KEEP - entries that are to be left alone.
* NEW - new entries to be added.
* EXTRACT - files that must be updated with new contents.
* LINK - new links to be added.
* Renames are done at the same time.
nodeupdates(name
, ino
, type
)
register struct entry
*ep
, *np
, *ip
;
# define ONTAPE 0x1 /* inode is on the tape */
# define INOFND 0x2 /* inode already exists */
# define NAMEFND 0x4 /* name already exists */
# define MODECHG 0x8 /* mode of inode changed */
* This routine is called once for each element in the
* directory hierarchy, with a full path name.
* The "type" value is incorrectly specified as LEAF for
* directories that are not on the dump tape.
* Check to see if the file is on the tape.
* Check to see if the name exists, and if the name is a link.
ip
= lookupino(np
->e_ino
);
panic("corrupted symbol table\n");
* Check to see if the inode exists, and if one of its links
* corresponds to the name (if one was found).
for (ep
= ip
->e_links
; ep
!= NIL
; ep
= ep
->e_links
) {
* If both a name and an inode are found, but they do not
* correspond to the same file, then both the inode that has
* been found and the inode corresponding to the name that
* has been found need to be renamed. The current pathname
* is the new name for the inode that has been found. Since
* all files to be deleted have already been removed, the
* named file is either a now unneeded link, or it must live
* under a new name in this dump level. If it is a link, it
* can be removed. If it is not a link, it is given a
* temporary name in anticipation that it will be renamed
* when it is later found by inode number.
if (((key
& (INOFND
|NAMEFND
)) == (INOFND
|NAMEFND
)) && ip
!= np
) {
if (lookuptype
== LINK
) {
dprintf(stdout
, "name/inode conflict, mktempname %s\n",
(((key
& INOFND
) && ip
->e_type
!= type
) ||
((key
& NAMEFND
) && np
->e_type
!= type
)))
* Decide on the disposition of the file based on its flags.
* Note that we have already handled the case in which
* a name and inode are found that correspond to different files.
* Thus if both NAMEFND and INOFND are set then ip == np.
* A previously existing file has been found.
* Mark it as KEEP so that other links to the inode can be
* detected, and so that it will not be reclaimed by the search
* for unreferenced names.
dprintf(stdout
, "[%s] %s: %s\n", keyval(key
), name
,
* A file on the tape has a name which is the same as a name
* corresponding to a different file in the previous dump.
* Since all files to be deleted have already been removed,
* this file is either a now unneeded link, or it must live
* under a new name in this dump level. If it is a link, it
* can simply be removed. If it is not a link, it is given a
* temporary name in anticipation that it will be renamed
* when it is later found by inode number (see INOFND case
* below). The entry is then treated as a new file.
case ONTAPE
|NAMEFND
|MODECHG
:
if (lookuptype
== LINK
) {
* A previously non-existent file.
* Add it to the file system, and request its extraction.
* If it is a directory, create it immediately.
* (Since the name is unused there can be no conflict)
ep
= addentry(name
, ino
, type
);
dprintf(stdout
, "[%s] %s: %s\n", keyval(key
), name
,
* A file with the same inode number, but a different
* name has been found. If the other name has not already
* been found (indicated by the KEEP flag, see above) then
* this must be a new name for the file, and it is renamed.
* If the other name has been found then this must be a
* link to the file. Hard links to directories are not
* permitted, and are either deleted or converted to
* symbolic links. Finally, if the file is on the tape,
* a request is made to extract it.
if (type
== LEAF
&& (ip
->e_flags
& KEEP
) == 0)
if ((ip
->e_flags
& KEEP
) == 0) {
renameit(myname(ip
), name
);
dprintf(stdout
, "[%s] %s: %s\n", keyval(key
), name
,
if (ip
->e_type
== NODE
) {
"deleted hard link %s to directory %s\n",
ep
= addentry(name
, ino
, type
|LINK
);
dprintf(stdout
, "[%s] %s: %s|LINK\n", keyval(key
), name
,
* A previously known file which is to be updated.
case ONTAPE
|INOFND
|NAMEFND
:
if (type
== LEAF
&& lookuptype
!= LINK
)
dprintf(stdout
, "[%s] %s: %s\n", keyval(key
), name
,
* An inode is being reused in a completely different way.
* Normally an extract can simply do an "unlink" followed
* by a "creat". Here we must do effectively the same
* thing. The complications arise because we cannot really
* delete a directory since it may still contain files
* that we need to rename, so we delete it from the symbol
* table, and put it on the list to be deleted eventually.
* Conversely if a directory is to be created, it must be
* done immediately, rather than waiting until the
case ONTAPE
|INOFND
|MODECHG
:
case ONTAPE
|INOFND
|NAMEFND
|MODECHG
:
if (ip
->e_flags
& KEEP
) {
badentry(ip
, "cannot KEEP and change modes");
if (ip
->e_type
== LEAF
) {
/* changing from leaf to node */
ip
= addentry(name
, ino
, type
);
/* changing from node to leaf */
if ((ip
->e_flags
& TMPNAME
) == 0)
ip
= addentry(name
, ino
, type
);
dprintf(stdout
, "[%s] %s: %s\n", keyval(key
), name
,
* A hard link to a diirectory that has been removed.
dprintf(stdout
, "[%s] %s: Extraneous name\n", keyval(key
),
* If we find a directory entry for a file that is not on
* the tape, then we must have found a file that was created
* while the dump was in progress. Since we have no contents
* for it, we discard the name knowing that it will be on the
fprintf(stderr
, "%s: (inode %d) not found on tape\n",
* If any of these arise, something is grievously wrong with
* the current state of the symbol table.
case INOFND
|NAMEFND
|MODECHG
:
fprintf(stderr
, "[%s] %s: inconsistent state\n", keyval(key
),
* These states "cannot" arise for any state of the symbol table.
panic("[%s] %s: impossible state\n", keyval(key
), name
);
* Calculate the active flags in a key.
(void) strcpy(keybuf
, "|NIL");
(void) strcat(keybuf
, "|ONTAPE");
(void) strcat(keybuf
, "|INOFND");
(void) strcat(keybuf
, "|NAMEFND");
(void) strcat(keybuf
, "|MODECHG");
* Find unreferenced link names.
register struct entry
*ep
, *np
;
vprintf(stdout
, "Find unreferenced names.\n");
for (i
= ROOTINO
; i
< maxino
; i
++) {
if (ep
== NIL
|| ep
->e_type
== LEAF
|| BIT(i
, dumpmap
) == 0)
for (np
= ep
->e_entries
; np
!= NIL
; np
= np
->e_sibling
) {
"%s: remove unreferenced name\n",
* Any leaves remaining in removed directories is unreferenced.
for (ep
= removelist
; ep
!= NIL
; ep
= ep
->e_next
) {
for (np
= ep
->e_entries
; np
!= NIL
; np
= np
->e_sibling
) {
if (np
->e_type
== LEAF
) {
badentry(np
, "unreferenced with flags");
"%s: remove unreferenced name\n",
* Remove old nodes (directories).
* Note that this routine runs in O(N*D) where:
* N is the number of directory entries to be removed.
* D is the maximum depth of the tree.
* If N == D this can be quite slow. If the list were
* topologically sorted, the deletion could be done in
register struct entry
*ep
, **prev
;
vprintf(stdout
, "Remove old nodes (directories).\n");
for (ep
= removelist
; ep
!= NIL
; ep
= *prev
) {
if (ep
->e_entries
!= NIL
) {
for (ep
= removelist
; ep
!= NIL
; ep
= ep
->e_next
)
badentry(ep
, "cannot remove, non-empty");
* This is the routine used to extract files for the 'r' command.
register struct entry
*ep
;
vprintf(stdout
, "Continue extraction of new leaves\n");
vprintf(stdout
, "Extract new leaves.\n");
dumpsymtable(symtabfile
, volno
);
first
= lowerbnd(ROOTINO
);
while (curfile
.ino
< maxino
) {
* If the next available file is not the one which we
* expect then we have missed one or more files. Since
* we do not request files that were not on the tape,
* the lost files must have been due to a tape read error,
* or a file that was removed while the dump was in progress.
while (first
< curfile
.ino
) {
panic("%d: bad first\n", first
);
fprintf(stderr
, "%s: not found on tape\n", myname(ep
));
ep
->e_flags
&= ~(NEW
|EXTRACT
);
* If we find files on the tape that have no corresponding
* directory entries, then we must have found a file that
* was created while the dump was in progress. Since we have
* no name for it, we discard it knowing that it will be
* on the next incremental tape.
if (first
!= curfile
.ino
) {
fprintf(stderr
, "expected next file %d, got %d\n",
ep
= lookupino(curfile
.ino
);
panic("unknown file on tape\n");
if ((ep
->e_flags
& (NEW
|EXTRACT
)) == 0)
badentry(ep
, "unexpected file on tape");
* If the file is to be extracted, then the old file must
* be removed since its type may change from one leaf type
* to another (eg "file" to "character special").
if ((ep
->e_flags
& EXTRACT
) != 0) {
(void) extractfile(myname(ep
));
ep
->e_flags
&= ~(NEW
|EXTRACT
);
* We checkpoint the restore after every tape reel, so
* as to simplify the amount of work re quired by the
dumpsymtable(symtabfile
, volno
);
* This is the routine used to extract files for the 'x' and 'i' commands.
* Efficiently extract a subset of the files on a tape.
register ino_t first
, next
, last
;
register struct entry
*ep
;
vprintf(stdout
, "Extract requested files\n");
first
= lowerbnd(ROOTINO
);
last
= upperbnd(maxino
- 1);
* Check to see if any files remain to be extracted
* Reject any volumes with inodes greater
* than the last one needed
while (curfile
.ino
> last
) {
* Decide on the next inode needed.
* Skip across the inodes until it is found
* or an out of order volume change is encountered
next
= lowerbnd(curfile
.ino
);
while (next
> curfile
.ino
&& volno
== curvol
)
} while (volno
== curvol
+ 1);
* If volume change out of order occurred the
* current state must be recalculated
* If the current inode is greater than the one we were
* looking for then we missed the one we were looking for.
* Since we only attempt to extract files listed in the
* dump map, the lost files must have been due to a tape
* read error, or a file that was removed while the dump
* was in progress. Thus we report all requested files
* between the one we were looking for, and the one we
* found as missing, and delete their request flags.
while (next
< curfile
.ino
) {
panic("corrupted symbol table\n");
fprintf(stderr
, "%s: not found on tape\n", myname(ep
));
* The current inode is the one that we are looking for,
* so extract it per its requested name.
if (next
== curfile
.ino
&& next
<= last
) {
panic("corrupted symbol table\n");
(void) extractfile(myname(ep
));
register struct entry
*np
, *ep
;
vprintf(stdout
, "Add links\n");
for (i
= ROOTINO
; i
< maxino
; i
++) {
for (np
= ep
->e_links
; np
!= NIL
; np
= np
->e_links
) {
if ((np
->e_flags
& NEW
) == 0)
(void) strcpy(name
, myname(ep
));
if (ep
->e_type
== NODE
) {
(void) linkit(name
, myname(np
), SYMLINK
);
(void) linkit(name
, myname(np
), HARDLINK
);
* Check the symbol table.
* We do this to insure that all the requested work was done, and
* that no temporary names remain.
register struct entry
*ep
;
vprintf(stdout
, "Check the symbol table.\n");
for (i
= ROOTINO
; i
< maxino
; i
++) {
for (ep
= lookupino(i
); ep
!= NIL
; ep
= ep
->e_links
) {
ep
->e_flags
&= ~(NEW
|EXISTED
);
badentry(ep
, "incomplete operations");
* Compare with the directory structure on the tape
* A paranoid check that things are as they should be.
verifyfile(name
, ino
, type
)
fprintf(stderr
, "Warning: missing name %s\n", name
);
for ( ; np
!= NIL
; np
= np
->e_links
)
panic("missing inumber %d\n", ino
);
if (ep
->e_type
== LEAF
&& type
!= LEAF
)
badentry(ep
, "type should be LEAF");