How freedup in principle works

Freedup always searches for files of identical size and compares them byte-by-byte. The only exception are "extra styles", where the tags (details see next chapter) are intentionally skipped.

In principle freedup only knows about linking. Therefore maximum risk is to link different files. During development many precautions were taken, but I have to emphasize that this risk exists. Only when using interactive mode you may delete files in a two step process, too.

Hash functions should speed up freedup since they avoid comparing files that have been scanned before (and might differ in the last characters). Freedup is slowed down, if files of the same size differ early. Then you should switch the hash function off, which is now the default. If most files of the same size are likely to be identical (more then just two), it probably pays to switch hash functions on. There is an internal hash function that allows some interesting speed enhancements (see below). External hash functions might be interesting to check the internal one for correctness.

Before files are compared byte-by-byte you might apply restrictions, like being owned by the same group or user, having the same permission or whatever the options allow you. These options always apply.

Why freedup does not use hash functions by default

The new algorithm records hash sums on the fly (starting in version 1.3-1) and is in worst case - depending on cpu - half as fast as without using hash functions. When reading files the hash function is calculated until the comparison fails. The hash context is stored until the next comparison takes place and if it fails at a later block, the hash calculation will be continued where it stopped earlier. Since reading and comparing files works with data blocks (predefined 4k) the hash values can sometimes be calculated although the comparison fails.

time ./freedup -x mp3 --hash ? -ni /testdir
7856 files; 1 match; average file size 46MB; 50% smaller 4k; 2900 BogoMIPS
2852 classic hash sums to avoid 3411 byte-by-byte comparisons.
hash supportParameterReal TimeUser TimeSys Time
without hash support--hash 02m04.646s0m00.599s0m03.455s
with classic hashsum--hash 15m31.221s2m21.914s0m16.303s
with advanced hash--hash 21m59.720s0m06.006s0m03.515s

time ./freedup --hash ? -n /mp3dir
7919 files; 0 matches; all around average file size 4.5MB; 1400 BogoMIPS
4502 classic hash sums to avoid 3819 byte-by-byte comparisons.
hash supportParameterReal TimeUser TimeSys Time
without hash support--hash 05m21.690s0m15.130s0m25.560s
with classic hashsum--hash 145m14.048s36m33.470s2m29.380s
with advanced hash--hash 210m01.311s6m28.610s0m28.150s

time ./freedup --hash ? -x mp3 -n /mp3dir
7919 files; 456 duplicates; all around average file size 4.5MB; 1400 BogoMIPS
4524 classic hash sums to avoid 3425 byte-by-byte comparisons.
hash supportParameterReal TimeUser TimeSys Time
without hash support--hash 06m48.276s0m18.590s0m28.600s
with classic hashsum--hash 149m35.108s37m06.450s2m47.400s
with advanced hash--hash 212m33.688s6m51.530s0m31.090s

As a consequence of these results, the advantage of hash functions is not obvious for most environments. I assume that there are situations, where many files have the same size and quite similar contents. Then one should switch hash function usage to the advanced mode. But since I do not intend to rely on hash results without having byte-by-byte comparison, I changed the default value since freedup 1.3-2 to off.

How freedup "extra styles" work

This concept was introduced in version 1.1 due to the fact that I wanted files to be linked although they differed. I am talking of mp3 files where the tags showed minor variations. First I considered retagging all files, but I would have to remove either all or complete all tags (n.b. MP3v1 tags are at the end, MP3v2 tags are at the beginning of an mp3 file, both are optional).

The extra style now should compare the essential file content, i.e. the mpeg encoded sound part in case of the mp3 files. Currently the following rules are established:

since for each file type exactly one method exists (might change in future), an automated mode will call the respective method according to the file magic. The name of each file is not considered for type checking.

Please note, that these styles change the behaviour according to the file contents. The change the size of the compared contents, but this does not affect the options that belong to the files, like ownerships or file names.

If you like to contribute, this is quite simple. There are source files for each style. Start with a copy of my.c and my.h. Rename the functions, fill in your way to evaluate the irrelevant bytes at start and the trailing ones, as well as a way to find size and magic. Add a matching line to the extra[] table in auto.c, compile, test and submit to me.

How freedup works

  1. scan all directory trees recursively for all regular files
  2. build a list of those files and keep their name, lstat() and arg position
  3. sort the files by comparing their sizes using qsort()
  4. in case the comparison has to report equal file size additional properties are compared
  5. most property checks have to be added using command line options
  6. if all demands are fullfilled, the files are compared block by block (4k)
  7. if both files are identical and on the same file system they will be renamed, hard linked, renamed file removed.
  8. if hardlinking is not possible soft links are tried, except one of the paths is not starting at root (but can be forced)
  9. sorting is repeated, the reason why it is needed was not checked yet
  10. finally a short report is delivered