create: a root inside an earlier directory root is archived twice, extract then deletes a hard link #10393

Problem

If a directory is given as a recursion root and a later root is located inside that directory, borg create archives that fs object twice. If the duplicate is a hard link, borg extract then deletes a file.

Found while working on #10388 / #10389, related to #5603. Seen on current master (a690440), macOS; the code in question is platform independent. 1.4-maint has the same skip_inodes logic (only read, not tested there).

Reproduction

mkdir input; echo -n 123456 > input/file1; ln input/file1 input/file2; ln input/file1 input/file3
borg repo-create -e aes256-ocb
borg create --list arch input input/file3
# A input/file3
# h input/file2
# h input/file1
# d input
# h input/file3      <- input/file3 is in the archive twice
mkdir out; cd out; borg extract arch
# input/file3: link: [Errno 2] No such file or directory: '.../out/input/file3' -> '.../out/input/file3'

Afterwards input/file3 is missing in the extracted tree (file1 and file2 are there, with a link count of 2).

Which name needs to be given as the second root depends on the platform: it has to be the member of the hard link group that gets archived first (first in inode order, here file3). borg extract remembers the first extracted member of a hard link group as the link target of the group. When the duplicate item comes, it removes the existing file at that path (the link target!) and then tries os.link(path, path).

With a file that is not hard-linked, or with a sub-directory root (borg create arch input input/sub), the items are "just" duplicated in the archive.

Cause

archiver/create_cmd.py: the duplicate root protection from #5603 only puts finished recursion roots into skip_inodes. Fs objects found while recursing are never recorded (that would need memory proportional to the file count). So "child root first, then its parent directory" is protected, but "parent directory root first, then a root inside it" is not.

Note: just checking "is this root below an earlier directory root" is not sufficient, as the earlier walk might not have archived that root (e.g. it did not recurse into a directory tagged via --exclude-if-present or into another filesystem with --one-file-system), so an explicitly given root in there must still get archived.

Suggested fix

• create: while recursing, when done with a path that also is a recursion root, record it in skip_inodes (costs memory proportional to the count of roots only).
• extract: be robust against a duplicate hard link item (there are other ways to get one, e.g. giving the same path twice via --paths-from-stdin): do not remove a path that is the remembered link target of its own hlid.