THEORY OF OPERATION for finddupe.c
copyright(c)2009 Scott Mitchell Jennings
under the terms of the GNU General Public License GPL3+
Wed Feb 25 08:55:46 PST 2009

* Requirements

Finddupe requires the readline, glib, and blkid libraries, and if
compiled with the FLTK interface, those libraries as well.

Readline is used for editing volume and file comments, glib is
used for MD5, and blkid is used to get the device name, volume
name and UUID of filesystems. Since it tends to cache things in
/etc/blkid.tab, it often works even for devices we do not have
read perms on.

I used to use gcrypt, but when it proved to be abit buggy, I
switched to glib and found it performed equally well.



* The volume and file and inode list structures

Finddupe stats all files in all paths specified on the command
line, staying within a single filesystem for each path (by
default).

For each filesystem encountered, a "volume list" structure is
added to a linked list of volumes.

For each file encountered on a volume, a "file list" structure is
added to a hash table of files on that volume, hashed by
pathname. This allows quick detection of pathname collisions
between the catalogs and the filesystem while scanning files.

Each file has an inode, and for each inode encountered, an "inode
list" structure is added to a hash table of inodes on that
volume. This allows quick detection of inode collisions (hard
links).

There is also a global hash table of inodes by size, so that
inodes of identical size can quickly be located when searching
for duplicates.

When a new filesystem is encountered, an attempt is made to load
a catalog file for that volume into the newly formed volume
structure and it's tables of file and inode structures. The
catalog is trusted to be free of filename collisions, and
self-consistent in it's files' link counts.


* Removable Media

Finddupe is meant to be used on removable media as well.  For
each path specified on the command line, if the path exists, an
attempt is made to mount media there by execing /bin/mount. If
the mount succeeds, an attempt will be made to unmount and eject
the media upon completion. If the path does not exist, it is
shortened, slash by slash, until it does exist, and then the
mount attempt is made.

If the device is readable, an attempt will be made to get the
volume names of DVDs and CDs, as well as to generate something of
a UUID from ISO filesystem data. (I add myself to the cdrom
group) If "implantisomd5" was used when the disk was created,
finddupe will use it's data as part of the effective UUID. (would
be so much nicer if there were a standard for this supported by
BLKID or VOLID, but no such luck)

* File Discovery

Before actually loading all the catalog files it needs, it first
loads only their headers, so it knows how many files total it
must load from catalog files, and can attempt to generate some
kind of ETA while actually loaded them.  Then it loads them.
Next it scans all the specified paths, find all regular files in
those paths, and adds them to list.

* Removal of missing files from the catalogs

Once all the file data has been read in from catalogs and by
stating all the files in the specified paths, any files loaded
from catalogs which should have been in those paths, but were not
found, are removed from subsequent searches or catalog writes.

* MD5 hash data  generation

If forced MD5 generation was selected (-m) a special pass is run
to generate the MD5 hash data for all files found in the
specified paths, which were missing, or missing MD5 data, in the
catalogs. The total ammount of data that must be read in to do
this was previously calculated, so that an ETA can be shown for
this process.

If forced MD5 generation was not selected, this pass is omitted,
and MD5 generation is only done in the Duplication Discovery pass
(below) on files found to be of equal size.

When finddupe is run for thet first time on a filesystem, MD5
data generation is the most time consuming part of it's
execution.

* Duplication Discovery

This process compares the MD5 data of all files of equal size,
generating the MD5 data if missing.  This is also the process
that hardlinks all duplicates if that feature has been invoked.

Various approaches attempt to optimize this process, and an
attempt is made to estimate the total number of compares that
will be done, so that an ETA may be displayed during the process.

Upon completion, each file list structure contains a circular
linked list of all files sharing it's inode (hard links), and
another circular linked list of all files sharing identical
content.

* Duplication Reports

The last process searches for all groups of duplicate files,
reporting groups of duplicates in order of descending size.

A switch (-r) limits the number of groups of duplicates which are
reported. By default all groups of duplicates are reported.



* Progress Reporting (when run via the command-line interface)

Throughout it's operation, finddupe reports it's progress as a
single line of text, updated once per second. When this line of
text exceeds the terminal width, text is removed from the middle
of the line, and replaced with "...".

Terminal width is discovered by ioctl(1,TIOCGWINSZ,&ts). Should
that fail, the "COLUMNS" environment variable is used. Should
that fail, a default of 80 columns is assumed.

SIGWINCH is caught to keep the terminal width accurate.


While reading in files from a catalog, or from media, the total
number of files read in so far, and the total size of those files
are reported as well as the pathname of the last file added.

While generating MD5sum data, the percent of the file's data
remaining to be read, and the speed at which it is presently
being read is reported

While searching for duplicates, the two files currently being
compared are printed, separated by a '|'. To fit the terminal
width, text is removed from the middle of each pathname, and
replace with '...'


 -smj <smudgeinator@users.sourceforge.net>
