Punchline: > My tarball happened to contain over 800 000 links with ".." as a path component. It also happened to contain over 5.4 million hard links. The beh

Punchline: > My tarball happened to contain over 800 000 links with ".." as a path component. It also happened to contain over 5.4 million hard links. The behavior is more precisely described not as quadratic, but O(n*m), where n is the number of symlinks pointing outside of the extraction directory, and m is the number of hardlinks. It happens because of the security precautions gnu tar performs to make sure a malicious archive can't set up a symlink pointing to an arbitrary place in your filesystem, and then extract files to it. The strategy they use has an unoptimized corner case when the archive also has a lot of hardlinks. The mechanism could probably be improved by remembering the list of deferred symlinks in a hash map rather than a linked list, but also, both symlinks pointing outside the extraction directory, and hardlinks, are uncommon. (Edited to correct: The problem exists even if the hardlinks do not actually point at the symlinks.)