Rdfind – redundant data find

Introduction

Rdfind is a program that finds duplicate files. It is useful for compressing backup directories or just finding duplicate files. It compares files based on content, NOT on name.

When I want to change some file, I am often nervous to break something and therefore copy all the old files to some directory named app_2006xxxx or whatever. The same when I switch computer system and am afraid to lose my old stuff. This makes all my files exist in numerous places, and I never feel like cleaning up. This is where rdfind comes in handy. It will find those files and report them to you. Optionally, erase them or replace them with links (hard or symbolic). Rdfind is a command line tool – that means no GUI.

Install

Rdfind is written in c++ and should compile under any *nix. It is currently running under Mandriva, Fedora Core, Macintosh and Windows (under cygwin).

Note that rdfind is licensed under GPL, and there is no warranty etc. See the license for details.

Installing with RPM

Here are precompiled packages. Drop me a line if you test it on some other system!

rdfind-1.2.2-1.i386.rpm (compiled on Debian, with rpmbuild. Tested on Fedora Core 3)
rdfind-1.2.2-1.i586.rpm (compiled on Debian, with rpmbuild. Tested on Fedora Core 3)
rdfind-1.2.1-0.1.20060mdk.i586.rpm (compiled on Mandriva 2006. Tested on a Fedora Core 3 and Mandriva 2006)
rdfind-1.2.2-1.src.rpm

Packages are signed with this key

Import the key (as root) with rpm --import rdfind-distribution-key.gpg

Verify the package with rpm -K rdfind-1.2.1-0.1.20060mdk.i586.rpm

Installing from source

Installing from source requires nettle library.Here is how to get and install nettle:

wget ftp://ftp.lysator.liu.se/pub/security/lsh/nettle-1.14.tar.gz -nc
wget ftp://ftp.lysator.liu.se/pub/security/lsh/nettle-1.14.tar.gz.asc -nc
wget ftp://ftp.lysator.liu.se/pub/security/lsh/distribution-key.gpg -nc

gpg --fast-import distribution-key.gpg                    # omit if you do not want to verify
gpg --verify nettle-1.14.tar.gz.asc --nettle-1.14.tar.gz  # omit if you do not want to verify
tar -xzvf nettle-1.14.tar.gz
./configure
make
su # Only if you have root privileges. See note below.
make install
exit

If you install nettle as non-root, you must create a link so that rdfind later can do #include "nettle/nettle_header_files.h" correctly. Use for instance the commands

cd nettle-1.14
cd ..
ln -s nettle-1.14 nettle

Next step is to build rdfind.

Download rdfind 1.2.2 (gzipped tar archive, 101 kB)
Download rdfind 1.2.1 (bzipped tar archive, 74 kB)

Build rdfind

[pauls@localhost tmp]$ bunzip2 rdfind-1.2.1.tar.bz2
[pauls@localhost tmp]$ tar xf rdfind-1.2.1.tar
[pauls@localhost tmp]$ cd rdfind-1.2.1/
[pauls@localhost rdfind-1.2]$./configure    # see note below
[pauls@localhost rdfind-1.2]$make
[pauls@localhost rdfind-1.2]$su             # if you have root privileges
[pauls@localhost rdfind-1.2]$make install

Note that if nettle is not installed by root, you might need to pass LDFLAGS=-L../path/to/nettle/library CPPFLAGS=-I../path/to/nettle_headerfiles to configure.

Usage

The syntax is

rdfind [options] directory_or_file_1 [directory_or_file_2] [directory_or_file_3]

Without options, a results file will be created in the current directory. For full options, see the man page.

Examples

Basic example, taken from a *nix environment:
Look for duplicate files in directory /home/pauls/bilder:

[pauls@localhost ~]$ rdfind /home/pauls/bilder/
Now scanning "/home/pauls/bilder", found 3301 files.
Now have 3301 files in total.
Removed 0 files due to nonunique device and inode.
Now removing files with zero size...removed 3 files
Total size is 2861229059 bytes or 3 Gib
Now sorting on size:removed 3176 files due to unique sizes.122 files left.
Now eliminating candidates based on first bytes:removed 8 files.114 files left.
Now eliminating candidates based on last bytes:removed 12 files.102 files left.
Now eliminating candidates based on md5 checksum:removed 2 files.100 files left.
It seems like you have 100 files that are not unique
Totally, 24 Mib can be reduced.
Now making results file results.txt
[pauls@localhost ~]$                  

From the last row, it is seen that there are 100 files that are not unique. Let us examine them by looking at the newly created results.txt:

[pauls@localhost ~]$ cat results.txt
# Automatically generated
# duptype id depth size device inode priority name
DUPTYPE_FIRST_OCCURENCE 960 3 4872 2056 5948858 1 /home/pauls/bilder/digitalkamera/horisontbild/.xvpics/test 001.jpg.gtmp.jpg
DUPTYPE_WITHIN_SAME_TREE -960 3 4872 2056 5932098 1 /home/pauls/bilder/digitalkamera/horisontbild/.xvpics/test 001.jpg
.
(intermediate rows removed)
.
DUPTYPE_FIRST_OCCURENCE 1042 2 7904558 2056 6209685 1 /home/pauls/bilder/digitalkamera/skridskotur040103/skridskotur040103 014.avi
DUPTYPE_WITHIN_SAME_TREE -1042 3 7904558 2056 327923 1 /home/pauls/bilder/digitalkamera/saknat/skridskotur040103/skridskotur040103 014.avi
# end of file

Consider the last two rows. It says that the file skridskotur040103 014.avi exists both in /home/pauls/bilder/digitalkamera/skridskotur040103/ and /home/pauls/bilder/digitalkamera/saknat/skridskotur040103/. I can now the one I consider a duplicate by hand.

Algorithm

Rdfind uses the following algorithm. If N is the number of files to search through, the effort required is in worst case O(Nlog(N)). Because it sorts files on inodes prior do disk reading, it is quite fast. It also only reads from disk when it is needed.

1. Loop over each argument on the command line. Assign each argument a priority number, in increasing order.

2. For each argument, list the directory contents recursively and assign it to the file list. Assign a directory depth number, starting at 0 for every argument.

3. If the input argument is a file, add it to the file list.

4. Loop over the list, and find out the sizes of all files.

5. If flag -removeident true: Remove items from the list which already are added, based on the combination of inode and device number.

6. Sort files on size. Remove files from the list, which have unique sizes.

7. Sort on device and inode(speeds up file reading). Read a few bytes from the beginning of each file (first bytes).

8. Remove files from list that have the same size but different first bytes.

9. Sort on device and inode(speeds up file reading). Read a few bytes from the end of each file (last bytes).

10. Remove files from list that have the same size but different last bytes.

11. Sort on device and inode(speeds up file reading). Perform a checksum calculation for each file.

12. Only keep files on the list with the same size and checksum. These are duplicates.

13. Sort list on size, priority number, and depth. The first file for every set of duplicates is considered to be the original.

14. If flag ”-makeresultsfile true”, then print results file (default). Exit.(?)

15. If flag ”-deleteduplicates true”, then delete (unlink) duplicate files. Exit.

16. If flag ”-makesymlinks true”, then replace duplicates with a symbolic link to the original. Exit.

17. If flag ”-makehardlinks true”, then replace duplicates with a hard link to the original. Exit.

Alternatives and benchmark

There are some interesting alternatives.

Duff: http://duff.sourceforge.net/ by Camilla Berglund.

Fslint: http://www.pixelbeat.org/fslint/ by Pádraig Brady

A search on ”finding duplicate files” will give you lots of matches.

Here is a small benchmark. Times are obtained from ”elapsed time” in the time command. The command has been repeated several times in a row, where the result from each run is shown in the table below. The test computer is a 3 GHz PIV with 1 GB RAM, Maxtor SATA 8 Mb cache, running Mandriva 2006.

time ./duff -rP dir >slask.txt 

time ./findup dir >slask.txt

time rdfind dir

Note: units are minutes:seconds

Author

Rdfind is written by Paul Sundvall. If you find this software useful, please drop me an email! The adress is x@y.z where x=rdfind, y=paulsundvall, z=net.

Help with creating files for rpm/deb building is especially needed. Suggestions and comments are very welcome.