Developer’s Guide¶

This guide is targeted to people that want to write new features or fix bugs in rmlint.

Bugs¶

Please use the issue tracker to post and discuss bugs and features:

https://github.com/sahib/rmlint/issues

Philosophy¶

We try to adhere to some principles when adding features:

Try to stay compatible to standard unix’ tools and ideas.
Try to stay out of the users way and never be interactive.
Try to make scripting as easy as possible.
Never make rmlint modify the filesystem itself, only produce output to let the user easily do it.

Also keep this in mind, if you want to make a feature request.

Making contributions¶

The code is hosted on GitHub, therefore our preferred way of receiving patches is using GitHub’s pull requests (normal git pull requests are okay too of course).

Note

origin/master should always contain working software. Base your patches and pull requests always on origin/develop.

Here’s a short step-by-step:

Fork it.
Create a branch from develop. (git checkout develop && git checkout -b my_feature)
Commit your changes. (git commit -am "Fixed it all.")
Check if your commit message is good. (If not: git commit --amend)
Push to the branch (git push origin my_feature)
Open a Pull Request against the develop branch.
Enjoy a refreshing Tea and wait until we get back to you.

Here are some other things to check before submitting your contribution:

Does your code look alien to the other code? Is the style the same? You can run this command to make sure it is the same:
```
$ clang-format -style=file -i $(find lib src -iname '*.[ch]')
```
Do all tests run? Go to the test documentation for more info. Also after opening the pull request, your code will be checked via GitHub workflows.
Is your commit message descriptive? whatthecommit.com has some good examples how they should not look like.
Is rmlint running okay inside of valgrind (i.e. no leaks and no memory violations)?

For language-translations/updates it is also okay to send the .po files via mail at sahib@online.de, since not every translator is necessarily a software developer.

Testsuite¶

rmlint has a not yet complete but quite powerful testsuite. It is not complete yet (and probably never will), but it’s already a valuable boost of confidence in rmlint's correctness.

The tests are based on pytest and are written in python>=3.11. Every testcase just runs the (previously built) rmlint binary a and parses its json output. So they are technically blackbox-tests.

To ensure required test dependencies are present:

$ pip3 install -r tests/requirements.txt

On every commit, those tests are additionally run on GitHub Actions.

Control Variables¶

The behaviour of the testsuite can be controlled by certain environment variables which are:

RM_TS_DIR: Testdir to create files in. Can be very large with some tests, sometimes tmpfs might therefore slow down your computer. The directory must already exist. By default, a temporary directory will be used.
RM_TS_USE_VALGRIND: Run each test inside of valgrind’s memcheck. (slow)
RM_TS_CHECK_LEAKS: Fail test if valgrind indicates (definite) memory leak.
RM_TS_USE_GDB: Run tests inside of gdb. Fatal signals will trigger a backtrace.
RM_TS_PEDANTIC: Run each test several times with different optimization options and check for errors between the runs. (slow).
RM_TS_SLEEP: Waits a long time before executing a command. Useful for starting the testcase and manually running rmlint on the priorly generated testdir.
RM_TS_PRINT_CMD: Print the command that is currently run.
RM_TS_ALWAYS_CLEAN: Remove the per-test directory right away, failed or not.

The files of a failing test are kept for inspection, those of a passing one are removed as the run goes along. Pass -o tmp_path_retention_policy=all to keep everything, or =none to keep nothing.

Additionally, slow tests can be run by appending -m slow to the commandline. More information on this syntax can be found on the pytest documentation. Also, -q can be used to invalidate the default -v, so individual test names aren’t displayed.

The suite can be run in parallel with pytest-xdist:

$ pytest -n auto

Before each release we call the testsuite (at least) like this:

$ sudo RM_TS_USE_VALGRIND=1 RM_TS_PRINT_CMD=1 RM_TS_PEDANTIC=1 pytest -m ''

The sudo here is used to execute some tests that require root access (such as creating invalid user and group IDs). However, most tests will work fine without it. -m '' option is used to execute all tests, including those marked as slow.

Coverage¶

To see which functions need more testcases we use gcov to detect which lines were executed (and how often) by the testsuite. Here’s a short quickstart using lcov:

$ CFLAGS="-fprofile-arcs -ftest-coverage" LDFLAGS="-fprofile-arcs -ftest-coverage" scons -j4 DEBUG=1
$ sudo RM_TS_USE_VALGRIND=1 RM_TS_PRINT_CMD=1 RM_TS_PEDANTIC=1 pytest -s -m 'slow and not known_issue'
$ lcov --capture --directory . --output-file coverage.info
$ genhtml coverage.info --output-directory out

The coverage results are updated from time to time here:

http://sahib.github.io/rmlint/gcov/index.html

Structure¶

tests
├── test_formatters   # Tests for output formatters (like sh or json)
├── test_options      # Tests for normal options like --merge-directories etc.
├── test_types        # Tests for all lint types rmlint can find
└── utils.py          # Common utilities shared among tests.

Templates¶

A template for a testcase looks like this:

from tests.utils import create_file

def test_basic():
    create_file('xxx', 'a')
    create_file('xxx', 'b')

    head, *data, footer = run_rmlint('-a blake3 -S a')

    assert footer['duplicate_sets'] == 1
    assert footer['total_lint_size'] == 3
    assert footer['total_files'] == 2
    assert footer['duplicates'] == 1

Rules¶

Test should be able to run as normal user.

If that’s not possible, check at the beginning of the testcase with this:

import pytest

def test_root_only_case():
  if not runs_as_root():
      pytest.skip("reason")

Regressions in rmlint should get their own testcase so they do not appear again.

Slow tests can be marked with a slow attribute:

import pytest

@pytest.mark.slow
def test_debian_support():
    assert random.choice([True, False]):

Unresolved issues can be marked with the known_issue attribute to avoid failing automated CI testing.

Container¶

Tests can be run in an Alpine container.

$ buildah bud --target test -t rmlint-test .
$ podman run --rm --privileged rmlint-test

Note for Mac Developers¶

The touch command included with macOS does not include a -d option, which is necessary for certain tests to function. The simplest way to work around this is to install the coreutils package via Homebrew, which provides a GNU version of touch:

$ brew install coreutils

Then prepend the coreutils GNU command directory to your PATH when running the test suite:

$ PATH="$(brew --prefix coreutils)/libexec/gnubin:$PATH" pytest ...

Buildsystem Helpers¶

Environment Variables¶

CFLAGS:: Extra flags passed to the compiler.
LDFLAGS:: Extra flags passed to the linker.
CC:: Which compiler to use?

# Use clang and enable profiling, verbose build and enable debugging
CC=clang CFLAGS='-pg' LDFLAGS='-pg' scons VERBOSE=1 DEBUG=1

Variables¶

PREFIX=<prefix>:

Change the installation prefix. By default this is /usr/local, but some users might prefer /usr or /opt.

DESTDIR=<destdir>:

Staging directory like /tmp/rootfs. It is prepended to PREFIX and is mainly useful for packagers.

LIBDIR=<libdir>:

This applies only to the static library librmlint.a installation, which is not installed by default (use scons install-lib). Some distributions use separate lib directories for 64/32 bit. If this happens, you should set the correct one for 64 bit with LIBDIR=lib64.

O=<level>:

Set the optimization level.

Valid levels are currently those that may be passed with the GCC/Clang option -O; these include 0, 1, 2, 3, s, fast, g, etc., depending on the compiler version.

In addition, the level may be debug or release, which indicates that the optimization level should be whatever the build system currently defines to be the default for the associated build mode.

Leaving it unset follows the build mode: -Og under DEBUG=1, -O2 otherwise.

DEBUG=1:

Enable a debugging build.

This turns on extra tests; in particular, it turns on run-time assertions. By default, a debug build excludes optimizations that may hinder debugging, but this may be overridden with the O variable, as usual.

Note that setting DEBUG=1 does not enable the production of debugger symbols; to enable those, use SYMBOLS=1.

This should always be enabled during development.

SYMBOLS=1:

Enable debugger symbols.

This option instructs the compiler to collect information that will help tools such as gdb present human-readable identifiers for a program’s functions and variables, etc. Note, though, that this information becomes obscured by optimizations, so make sure to set the optimization level appropriately.

VERBOSE=1:

Print the exact compiler and linker commands. Useful for troubleshooting build errors.

FORCE=1:

Keep building even if the compiler emit warnings, i.e. bypass -Werror.

CCFLAGS=<command line options>:

Set the last compiler options.

Internally, the build system maintains in CCFLAGS the list of options that are supplied to the compiler; this list is composed by combining the relevant environment variables (such as CFLAGS) along with the choices made by other build-time configurations.

This command-line variable makes it possible to override an option in this list by supplying customized command-line options to be appended. For example: DEBUG=1 CCFLAGS=-g1.

The string that is supplied as the value for this variable is parsed as per a POSIX shell command line, and so it may include shell quoting if necessary.

STRIP=1:

Strip symbols while linking (or after linking on macOS).

SANITISE=<comma-separated list>:

Compile with sanitisers enabled. Good to associate with SYMBOLS=1. SANITISE=1 means =address,undefined,leak.

Arguments¶

–show-config:: Print a summary of all features that will be compiled and what the environment looks like, then carry on with the target. Add -n to stop at the summary instead.
–without-libelf:: Do not link with libelf, which is needed for nonstripped binary detection.
–without-blkid:: Do not link with libblkid, which is needed to differentiate between normal rotational harddisks and non-rotational disks.
–without-fiemap:: Do not attempt to use the FIEMAP ioctl(2).
–without-gettext:: Do not link with libintl and do not compile any message catalogs.
–without-gui:: Do not build or install shredder (GUI).
–without-compile-glib-schemas:: Do not (re)compile system Glib schemas on installation/uninstallation.

By default, all --without-* options are enabled, i.e. as if they were compiled by an hypothetical --with-* option.

Notable targets¶

install:

Install all program parts system-wide.

install-core:

Install only the binary, its manpage and the translations.

install-gui:

Install only the Shredder GUI: the Python package, the desktop file, the icon and eventually the GSettings schema.

man:

Build the manpage.

docs:

Build the online html docs (which you are reading now).

test:

Build the tests (requires python and pytest installed). Optionally valgrind can be installed to run the tests through valgrind:

$ RM_TS_USE_VALGRIND=1 pytest

PYTEST_ARGS= passes extra arguments.

$ scons test PYTEST_ARGS='-m reflink'
$ scons test PYTEST_ARGS="-m 'not slow and not manpage'"

xgettext:

Extract a gettext .pot template from the source.

msgmerge:

Update every .po catalog against rmlint.pot.

gettext:

xgettext followed by msgmerge.

dist:

Build a tarball suitable for release. Save it under rmlint-$major-$minor-$patch(-$prerelease).tar.gz.

cdb:

Generate a JSON compilation database compile_commands.json.

compile-flags:

For older tools, generate a compile_flags.txt file, as well as a .clang_complete link.

Sourcecode layout¶

All C-source lives in lib, the file names should be self explanatory.
As an exception, the main lives in src/rmlint.c.
All documentation is inside docs.
All translation stuff should go to po.
Tests are written in Python and live in tests.

Hashfunctions¶

Here is a short comparison of the existing hashfunctions in rmlint (linear scale). For reference: Those plots were rendered with these sources - which are very ugly, sorry.

If you want to add new hashfunctions, you should have some arguments why it is valuable and possibly even benchmark it with the above scripts to see if it’s really that much faster.

Also keep in mind that most of the time the hashfunction is not the bottleneck.

Optimizations¶

For sake of overview, here is a short list of optimizations implemented in rmlint:

Obvious ones¶

Do not compare each file with each other by content, use a hashfunction to reduce comparison overhead drastically (introduces possibility of collisions though).
Only compare files of same size with each other.
Use incremental hashing, i.e. hash block-wise each size group and stop as soon a difference occurs or the file is read fully.
Create one reading thread for each physical disk. This gives a big speedup if files are roughly evenly spread over multiple physical disks [note: currently using 2 reading threads per disk as a workaround for a speed regression but hoping to fix this for rmlint 2.5].
Disk traversal is similarly multi-threaded, one thread per disk.
Create separate hashing threads (one for each file) so that the reader threads don’t have to wait for hashing to catch up.

Subtle ones¶

Check only executable files to be non-stripped binaries.
Use preadv(2) based reading for small speeedups.
Every thread in rmlint is shared, so only few calls to pthread_create are made.

Insane ones¶

Use fiemap ioctl(2) to analyze the harddisk layout of each file, so each block can read it in perfect order on a rotational device.
Check the device ID of each file to see if it on a rotational (normal hard disks) or on a non-rotational device (like an SSD). On the latter the fiemap optimisation is bypassed.
Use a common buffer pool for IO buffers and recycle used buffers to reduce memory allocation overheads.
Use only one hashsum per group of same-sized files.
Implement paranoia check using the same algorithm as the incremental hash. The difference is that large chunks of the file are read and kept in memory instead of just keeping the hash in memory. This avoids the need for a two-pass algorithm (find matches using hashes then confirm via bytewise comparison). Each file is read once only. This achieves bytewise comparison in O(N) time, even if there are large clusters of same-size files. The downside is that it is somewhat memory-intensive (can be configured by --limit-mem option).