How to `du` only the space used up by files that are not hardlinked elsewhere?

Question

Using rsync --link-dest for space-saving snapshots, how can I figure out how much space I actually saved? Or more general:

How to figure out how much space a directory uses considering only files that are not hardlinked elsewhere outside the directory structure? Asked differently: How much space would actually be freed after a deletion of that directory? (du -hs would lie. The space required for the hardlinks themselves may be included)

Answer 1

Assuming there aren't internal hardlinks (that is, every file with more than 1 hardlink is linked from outside the tree), you can do:

find . -links -2 -print0 | du -c --files0-from=-

---

EDIT And here is what I sketched in the comment, applied. Only without du; kudos to @StephaneChazelas for noticing du is not necessary. Explanation at the end.

( find . -type d -printf '%k + ' ; \
  find . \! -type d -printf '%n\t%i\t%k\n' | \
    sort | uniq -c                         | \
    awk '$1 >= $2 { print $4 " +\\" }' ; \
  echo 0 ) | bc

What we do is to create a string with the disk usage (in KB) of every relevant file, separated by plus signs. Then we feed that big addition to bc.

The first find invocation does that for directories.

The second find prints link count, inode, and disk usage. We pass that list through sort | uniq -c to get a list of (number of appearances in the tree, link count, inode, disk usage).

We pass that list through awk, and, if the first field (# of appearances) is greater than or equal the second (# of hardlinks), meaning there aren't links to this file from outside the tree, then print the fourth field (disk usage) with a plus sign and a backslash attached.

Finally we output a 0, so the formula is syntactically correct (it would en in + otherwise) and pass it to bc. Phew.

(But I would use the simpler first method, if it gives a good enough answer.)

Answer 2

du actualy won't lie ;) It parses the dir(s) one gives it, counting only the first of all hardlinks pointing to the same inode it encounters.

If you ask du what it sees in one directory only, it does not care that there are other hard links pointing to the same contents:

$ du -h daily.0 && du -hc daily.1
29G /daily.0
29G /daily.1

Now give it dirs on the same row (starting with the most recent one for rsync incremental backups with --link-dest):

$ du -hc daily.0 daily.1
29G /daily.0
364M /daily.1
29G total

Or the whole backup dir:

$ du -hc --max-depth=1 /snapshots
29G /daily.0
364M /daily.1
537M /daily.2
333M /daily.3
30G total

Any file in 'daily.1' referencing an inode (aka "real" file) already referenced in 'daily.0' will not be counted.

Therefore deleting daily.1 will save 364MB on your device.

REMOVE

Answer 3

Basically, you need to get the inode numbers and number of links for all the files (non-directories), compare that number of link with the number of occurrence of each inode, and if they differ, exclude the file.

Assuming, they're all on the same filesystem, something like this should work (with GNU find):

find . -type d -printf '%k\n' -o -printf '%i %n %k\n' |
   awk '
     NF==1{t+=$0; next}
     {n1[$1]=$2; n2[$1]++; s[$1]=$3}
     END {
       for (i in n1)
         if (n1[i] == n2[i])
           t+=s[i]
       print t
     }'