The problem of keeping track of hardlinks as you traverse a directory tree

March 1, 2022

One of the reactions to my discovery about rsync not handling hardlinks by default was surprise that memory was an issue of concern when doing this. After all, you might ask, how hard is the problem and how much memory are we talking about? That depends on what sort of program you are and how thorough a job you want to do.

A program like du has the simplest case. GNU du's normal behavior is to ignore hardlinks after the first time it sees them, so all it needs to do is keep track of enough information to identify a file with more than one link if it sees it again. Normally this is the file's inode number and device. Modern Unixes use 64-bit inode numbers and generally 64-bit device numbers, so you're looking at 16 bytes per hardlinked file. Since you don't want to do a linear search of a potentially very large array every time you encounter a hardlinked file, you're also going to need additional space for some sort of random access data structure. It's probably not worth keeping track of the link count, especially since it's also a 64-bit integer on at least one popular platform (Linux); you're probably losing more space than you gain back by being able to drop entries when you've seen all their links. However, all of this space usage is relatively trivial by modern standards.

(You can reduce the memory needs in most situations by having a two-level data structure, where you give each separate device number its own inode lookup structure. This reduces the per-file information down to one 64-bit number from two, since you're storing the device number only once instead of once per hardlinked file. Usually you'll only be dealing with a few device numbers so this is a real win. It does complicate the code a bit. I don't know if GNU du uses this approach.)

A program like rsync or tar has a harder problem, because it also needs to keep track of the full file name for some instance of the hardlinked file (normally it will keep track of the first one). Full file names can be long, especially if you have something annoying like a deeply nested directory structure, and given the additional memory usage you now probably do want to also store the link count so you can delete entries once you no longer need them.

(The good news is that you don't need to look things up by file name, so you can continue to only have a fast random access data structure for the inode number plus the device. And you can still optimize the handling of device numbers, although this is no longer so much of a memory saving on a percentage basis.)

The worst case for both du style and rsync style programs is when you are working with a directory tree where all files have hardlinks that go outside the tree. In this case, both programs wind up permanently keeping track of all files in the tree in RAM; even if you track link count, you'll never see all of the links for any file so you can never drop any entries. Such directory trees can happen in a variety of situations, including space-saving backups that hardlink unchanged files between backup trees.

For scale, a large root filesystem on one of our compute servers has around 2.5 million files with the text of their full file names amounting to just over 200 Mbytes. On our NFS fileservers, the filesystem with the most files has around 7 million of them and a total full filename text size on the order of 665 Mbytes. On modern machines with multiple gigabytes of RAM that are often mostly unused, programs like du and rsync should be able to handle even the very unlikely worst case situation without blowing up. In more constrained environments, they might start to have issues.

(This was sparked by reddit comments on my rsync entry.)

Written on 01 March 2022.
« Firefox (Nightly) and the case of the fading scrollbars on Unix
A Python program can be outside of a virtual environment it uses »

Page tools: View Source, Add Comment.
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Tue Mar 1 22:30:16 2022
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.