Tar archive quadratic time. 2022
Why tar archive sucks
Amazing article. After 30 years, now i know the unix tar format, and how bad it is.
• No indexing of files. You need to read the entire archive to know what files are in it.
• Via 3 extensions over decades, UStar, pax file format, gnu tar, the format became very convoluted. quote: .
needs to support 5 different ways of reading the file path, 5 different ways of reading the link path, and 3 different ways of reading the file size
• Gnu tar, in order to prevent security problem of extracting file outside the current dir, it uses a very inefficient algorithm and data structure, making it quadratic time slow.
For every hard link, we walk the list of all delayed links. But it actually gets worse; ... So for all "normal" hard links, it has to go through the entire linked list of delayed links twice.
• But if you use option “tar -P” (or --absolute-paths), it bypass this but mean malicious tar file can put files anywhere on your system.
- The tar archive format, its extensions, and why GNU tar extracts in quadratic time
- By Martin Dørum aka Mortie
- https://mort.coffee/home/tar/
Gnu tar fixed the quadratic problem
note: bsd tar doesn't have this problem. gnu tar fixed the quadratic time problem.
