Re: MAYBE BUG in dar 2.7.2 with hardlinks handling

On 03/12/2021 00:29, Alexey Loukianov via Dar-support wrote:
> Hi Denis,

Hi Alexey,

First, no worries for your message if you find it long. It has the
advantage to clearly show the problem you met. If all reported problems
 where that well detailed and explained, it would save a lot of
exchanges and time to understand the context, reproduce the problem and
understand it!

So according to you description and very helpful script to reproduce the
problem, my understanding is the following:

during a differential backup, dar read the directory to backup in the
order the operating system provides it:

1/ If the subdirectory to be provided is the one that was present in the
archive of reference, the hard linked file is seen as unchanged and when
it is seen in the second directory it is detected as being an already
seen hard link and dar stores a "cat_mirage" object in the resulting
catalogue (several "cat_mirage" objects point to a "cat_etoile" object
that hold the hard linked inode). In that case you get the behavior you
expect.

2/ Now, you have guessed, when the first subdirectory returned by the
operating system is the new one, the hard linked file is recorded as a
new file, because in the backup of reference nothing existed at that
place. When it is seen a second time in the "old" directory dar put a
"cat_mirage" structure pointing to the already saved inode, to keep
record of hard link nature of both occurences, but this hard linked file
stays saved in the resulting backup, because its data has already been
stored in the backup and the data, EA or FSA of other files may have
been added after it already.

The order of entries in a directory is no linked to the lexicographical
order of their name. It is completely filesystem dependent... adding a
new file in a directory may take place at the first slot available, at
the end of the list, or other behaviors depending on the underlying data
structure and its current status, that holds the directory content on a
given filesystem. This explains the randomness of the behavior.

These are the facts and observations.

Now, is it a problem under normal backup context (I mean when dar is
used without rsync on a directory tree to backup)?

Not really: if a hard linked file exits and has not changed or got added
hard links, its first occurence met in the directory tree during a
differential backup will match an existing entry in the backup of
reference and the catalogue whill hold an "unsaved" entry, other
occurence of that hard linked file will be stored as a "hardlink"
(things are a bit more complex but a save your from the implementation
details).

However if one is adding a new hard link to an existing hardlinked
inode, there is statistically at most one chance on three (and as less
chances as the number of hard links to the inode increases) for this new
occurence to be seen before one that was recorded in the backup of
reference. In that rare case only, the hard linked inode is saved again,
even if it had not changed since the backup of reference.

Improving this behavior is quite tricky, as between the new occurence
met and the first old occurence met, a lot of files may have been added
to the backup. Modifying the hard linked inode status would not reduce
the backup size unless the data put after it was shifted back in the
backup by the amount of saved data the file had. For small hard linked
files that have just been seen, this could be simple, but when you take
into account the fact that a backup may be written to pipe or may use
slices, or worse may use encryption, or even worse can make use of slice
hashing, and yet a mix of all these at the same time... the penalty to
skip back even for a small amount is important when it is not
impossible. Also, considering that the first old occurence of a hard
link may be met near the end of the backup, detecting the problem could
only be possible a long time after the first "new" hard link occurence
to that file...

Let me take some time to see how this could be improved, but so far I
have not simple solution: Modifing this behavior in the way that would
suite your need, could lead dar to almost complete a backup and skip
back near the beginning (it may be impossible depending on the context)
and restart the whole backup again... Thus for a condition that should
be very unfrequent in normal condition of dar usage, this could lead to
a heavy impact in term of backup processing time in your situation,
without frequent advantage in 'normal' use context.

But note that this behavior is not new, I've tested 2.7.2 and 2.6.15:
they behave the same.

This is my turn to be sorry for this long explanation! :)

Cheers,
Denis



> 
> Thanks a lot for such a wonderful piece of software you created, dar is
> simply brilliant.
> I've been using it for a long time to handle my incremental backups
> needs and it was working flawlessly.
> 
> Backup strategy I use is:
> 1. rsync with --dest-link option from a remote box to a backup handling
> box once per day, dir names are in YYYY-MM-DD format, link-dest for
> today's backup is always last available previous backup, typically - one
> that was done yesterday.
> 2. Middle-term storage for last 4 years: create full dar backups with
> "-R YYYY-MM-DD -c YYYY-MM-DD" for any "first backup of the month",
> create incremental dar backups with "-R YYYY-MM-DD -A YYYY-MM-(DD-1) -c
> YYYY-MM-DD" for all other dirs of the same month.
> 3. Long-term storage: retention policy is to keep one full backup per
> month done at the beginning of the month for anything that is older than
> 4 years, write these to a cold storage and store somewhere in the attic
> for future generations :-).
> 
> As mentioned previously it was working flawlessly for years and I was
> more than happy with it.
> One thing that kind-a annoyed me was that in case I wanted to restore
> backups from dars back to the way directories were laid out and files
> hardlinked after initial rsync I had to use shell-scripting similar to
> this one:
> 
> mkdir work
> DARs_DIR="/opt/storage/DARs/2016/"
> P=2016-12
> ls -1 "$DAR_DIR/$P*.1.dar" | sort -n | while read f; do
>     d=${f%.1.dar}
>     dar -wa -x "${d}" -R $PWD/work/ || break;
>     mkdir -p $d
>     rsync -a --link-dest=$PWD/$P ./work/ ./$d/ || break
>     P="$d"
> done
> 
> Code above does what I want but it is too complex for such a simple
> task, rsync usage slows things down and the need to use "work" dir to
> store WIP "checkpoints" inflates disk space requirement.
> 
> Thus I thought about an optimization of the backup methodology that was
> possible in theory knowing that dar is expected to be able to properly
> handle hardlinks. Idea was to run dar with "-R" set to the parent
> directory where all YYYY-MM-DD directories are stored and limit what is
> getting backed up by using "-g" options like this:
> 
> dar -c 2016-12-01 -R /opt/storage/backups/2016 -g 2016-12-01/   # Create
> full backup of the month start
> dar -c 2016-12-02 -A 2016-12-01 -R /opt/storage/backups/2016 -g
> 2016-12-01/ -g 2016-12-02/   # Create first incremental backup of the
> month for day 02
> dar -c 2016-12-03 -A 2016-12-02 -R /opt/storage/backups/2016 -g
> 2016-12-02/ -g 2016-12-03/   # Create first incremental backup of the
> month for day 03
> 
> ... and so on. Expectations are that archive for day 02 of the month
> would not include any files for day 01 - as they all were backed up and
> available in reference full archive for day 01 - and for day 02 it would
> only save new or changed files compared to day 01 as all other files in
> dir for day 02 are hardlinks to files in dir for day 01 - which again
> are already saved in previous backup. Same stands for day 03 incremental
> backup and so on.
> 
> Observed behaviour does not match expectations - for day 02 hardlinks
> get always saved into dar ignoring the fact that same files are already
> saved in reference archive for day 01. For days 03 and greater things
> seem to go wildly random - sometimes hardlinks are saved into backup,
> sometimes not.
> 
> Here is a small test script reproducing the problem:
> ================8<===================
> #!/bin/bash -x
> 
> WDIR=$(mktemp -q -d -p "$PWD" dar-test-XXX)
> [ -d "$WDIR" ] || { echo "Failed to create working dir!" >&2; exit 1; }
> 
> LAST_DIR=z
> 
> pushd "$WDIR"
> 
> mkdir a
> truncate -s 16192 a/abc.txt
> for i in `eval echo \{b..$LAST_DIR\}` ; do
>     mkdir $i
>     ln a/abc.txt $i/abc.txt
> done
> ls -li `eval echo \{a..$LAST_DIR\}`
> dar -ah --sparse-file-min-size 1E -c dif-when-hardlink-a -R . -g a
> --fsa-scope none
> dar -l dif-when-hardlink-a -alist-ea
> 
> PREV=a
> for i in `eval echo \{b..$LAST_DIR\}` ; do
>     dar -ah --sparse-file-min-size 1E -c dif-when-hardlink-$i -R . -g
> $PREV/ -g $i/ -A dif-when-hardlink-$PREV --fsa-scope none
>     dar -l dif-when-hardlink-$i -alist-ea
>     PREV=$i
> done
> 
> popd
> ================8<===================
> 
> Here is listing of produced dars on the test VM I use as a playground:
> 
> # ll *.dar
> -rw-r--r-- 1 root root 17025 Dec  3 02:03 dif-when-hardlink-a.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-b.1.dar
> -rw-r--r-- 1 root root   894 Dec  3 02:03 dif-when-hardlink-c.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-d.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-e.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-f.1.dar
> -rw-r--r-- 1 root root   894 Dec  3 02:03 dif-when-hardlink-g.1.dar
> -rw-r--r-- 1 root root   894 Dec  3 02:03 dif-when-hardlink-h.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-i.1.dar
> -rw-r--r-- 1 root root   894 Dec  3 02:03 dif-when-hardlink-j.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-k.1.dar
> -rw-r--r-- 1 root root   894 Dec  3 02:03 dif-when-hardlink-l.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-m.1.dar
> -rw-r--r-- 1 root root   894 Dec  3 02:03 dif-when-hardlink-n.1.dar
> -rw-r--r-- 1 root root   894 Dec  3 02:03 dif-when-hardlink-o.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-p.1.dar
> -rw-r--r-- 1 root root   894 Dec  3 02:03 dif-when-hardlink-q.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-r.1.dar
> -rw-r--r-- 1 root root   894 Dec  3 02:03 dif-when-hardlink-s.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-t.1.dar
> -rw-r--r-- 1 root root   894 Dec  3 02:03 dif-when-hardlink-u.1.dar
> -rw-r--r-- 1 root root   894 Dec  3 02:03 dif-when-hardlink-v.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-w.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-x.1.dar
> -rw-r--r-- 1 root root   894 Dec  3 02:03 dif-when-hardlink-y.1.dar
> -rw-r--r-- 1 root root 17220 Dec  3 02:03 dif-when-hardlink-z.1.dar
> 
> Notice the file size column, it shows all the story.
> 
> I'm not sure if this one is really the bug or it's me doing something
> weird and having wrong assumptions/expectations.
> Please advice on what's going on here and why do I get this behaviour
> for this incremental backup approach?
> 
> Thanks in advance and sorry for a fuzz (and a wall of text this message
> is).
>