I've been working on some data-deduplication which forced me to use the file system as a hash-table. This resulted in some directories which it took literal hours to delete using almost any reasonable method (i.e.
ls -f1 | xargs rm,
find -delete, etc.)
Under Ext2/3/4 file systems, a directory is a file containing a hash table from filenames to inode numbers (in my case, reaching around 60 MB!) As I understand, running
rm -rf and friends is slow, because it follows this methodology:
Iterate over the hash table in the directory file. For every filename-inode pair encountered, atomically:
- Decrement the name count on the inode.
- Remove the entry from the hash table.
(Deletion of the files/inodes occurs when their name count reaches 0 and there are no programs having file descriptors open which are pointing to those inodes.)
Decrementing the name-count of an inode is fast.
Deleting a file (especially a small one) is also fast: one simply designates the drive blocks the file owns as free in the availability table.
The slowdown, as I can tell, arises in the removal of entries from the hash table. Each deletion probably has a chance to trigger a re-hashing, seeing as I observed the directory file's size diminishing as files were removed.
What I am asking is twofold:
- Is my reasoning correct, in it being the hash-table manipulation that slows down the process?
If it is, is there is a tool that does the following (and which is thereby, probably a lot faster?)
- Decrement the name count of every inode listed in the directory file.
- Delete all content of the entire directory at once.