Deleting Items from Filesystems on Unix like systems traditionally requires that one has to recurse into each sub-directory and unlink each entry. This has some drawbacks.

1. On large trees and slow storage mediums (HDD’s, Network filesystems) this can take considerable time (hours to days for really big trees).
2. Deletion is not atomic, until the deletion process completes partial data remains in place.
3. It may not free space as fast and as much as expected while running. This is especially true when data is hard linked. Space is only feed after the last link to the data becomes deleted.

• We want to free disk space in an optimal way, freeing as much as possible already at begin of the deletion process.
• Deletion should appear to be atomic for all use cases. Once a directory is deleted, one can instantly reuse its name.
• Even on power failures, crashes or other disruptions, eventually no stale data is left behind. Deletion resumes after a reboot.
• The actual deletion can run in background with low priorities to allow other workload to use the IO-Bandwidth.
• As long it frees space in a optimal way it is not so important when the complete deletion process takes longer.

• We crate a system service (‘rmrfd’) which operates in the background and deletes directories and files.
• Renaming/moving directories on the same Filesystem is an atomic operation. Usually this is very fast. Lets use this.
• Every filesystem where we want to delete files ‘rmrfd’ gets some directories which are watched.
• These directories are writable by anyone who is allowed to use the rmrfd service.
• When one wants to delete directory trees or files they are simply move into the corresponding ‘rmrfd’ directory.
• The daemon detects the added entry and runs an ‘inventory’ scan on these. This scan records st_size, st_dev, st_ino, st_nlink and its path in a database. Note that this is expensive, but much less expensive than doing a recursive delete.
• The Database is ideally in memory, but may be backed on disk on a lazy/volatile/non-logging way. Care must be taken that Database access generates the least possible access to the Disks. On unclean shutdown this Database will be discarded and rebuild.
• Once the inventory is finished we can run queries. Finding files where all its hardlinks are exist only in the ‘rmrfd’ directories, sorted by size, biggest first. Deleting these first will free the most space with the least operations.
• As new files or directories are moved to the ‘rmrfd’ directory they are added to the inventory as above.
• Eventually all files falling into the above category are deleted (this should also freed the most space). Then only files which have hardlinks out of the ‘rmrfd’ scope remain. We can just start a recursive delete on these remains. This will be slow and not free much space, as the bulk space was already freed before but eventually complete.

• The Database could grow excessively large, only add files with a size over some configured threshold to it.

While moving data into the ‘rmrfd’ directories for asynchronous deletion is simple, it may be not sufficient for some use cases. For this a simple API exits.

• int64_t rmrf(const char* path, int8_t sync)

The ‘sync’ argument can be one of the following:

-1

Asynchronous deletion. The function will return immediately.

0

Synchronous deletion. Return as soon the size to be freed (inventory created) is known. This is useful when the caller only needs to know how much space eventually will be freed.

1..100

Synchronous deletion. Return when as much percent of the space is freed. With this the caller can block until space becomes really available. Due to the nature how filesystems store data this will be inaccurate and the caller has to put more safeguards into place. Being able to limit this by some percentage allows for reasonably fast return while the bulk of slow deletions may still progress in the background.

0

when asynchronous removal was requested and accepted.

Number of (1k) blocks it will free

on synchronous removal.

an error code (negative number)

when anything got wrong.

This API is a library that operates in the caller context. It connects to the ‘rmrfd’ over a local socket. Messages between the library and the ‘rmrfd’ are only informal. The movement of the data into the ‘rmrfd’ directory will be done by the API itself, thus there is no worry about security implications.

The API opens a session to the daemon for each call, after that a Request/Response textual protocol (with nul terminators) is used. In case of any Error the session ends. Protocol examples are given below for the successful cases, while any request can as well fail with an error number ERR nnn\0.

1. Query for a given path which ‘rmrf’ directory to use. There must be an existing ‘rmrf’ directory on the same filesysystem as the to be deleted object. Further as safeguard this directory must be either on the same directory level or above. Thus with proper placement of ‘rmrf’ directories one has some limited control over what could be deleted.

   Send:    PATH /foo/bar/baz\0
   Receive: OK /foo/bar/.rmrf/$TMPDIR/\0
       

   Note that the rmrfd reserves and returns a temporary directory for the operations to prevent name collisions.

2. Move the to be deleted data into the returned temporary directory

   In case this fails for some reason the session can just be terminated by closing the fd.

3. Set the sync policy, start deleting

   Send:    SYNC 85\0
   Receive: OK 12345678\0 // return freed size after a while
       

A simple commandline utility ‘rmrf’ that calls above API can be implemented.

Deletion may still cross devices when a mountpoint exists below the deleted directory. This needs to be addressed:

• since the mountpoint is within the domain of rmrfd it needs to unmount it (otherwise it wont be able to delete the tree)
• needs a option to cross devices, but defaults to not do so (only unmounting happens)