20 ms·
The tar archive format, and why GNU tar extracts in quadratic time
- thanatos519 4y agoI've never had a big enough n to notice this.
- brian_herman 4y ago“I'm absolutely certain that it's possible to make GNU tar extract in O(n) without --absolute-paths by replacing the linked list with a hash map. But that's an adventure for another time.“ from the article maybe someone could put in a pr
- stabbles 4y agoPretty sure there's tons of C libraries that do not use hash maps because it requires implementing a hash map.
- mort96 4y agoThe fun thing is, GNU tar already has a hash map implementation, and it uses that hash map to make sense of hard links in the archive creation code. It's just not used in the extractor for whatever reason.
- IshKebab 4y agoProbably because whoever wrote the extractor didn't want to learn how to use some custom hashmap written by the guy who wrote the compressor. Or maybe didn't even know it existed.
- mort96 4y agoIt uses the hash table from gnulib: https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=blob;f=lib/hash.h https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=blob;f=l... -- so that's not the reason, gnulib's hash table should be pretty general and robust.
- vjeux 4y agoIf you want to see more examples of accidentally quadratic behaviors: https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/
- game-of-throws 4y ago> I decided that learning the tar file format and making my own tar extractor would probably be faster than waiting for tar. If you want something done right, you gotta do it yourself!
- barkingcat 4y agoI've been going through the first edition of Art of Intel x86 Assembly and there was a mention that DEC used octal numbers (PDP-11 uses octal) and a cross reference of the tar wiki page indicates that the first tar was written for Version 7 Unix, which was made for the PDP-11. Gnu tar most likely inherited the octal system in order to retain compatibility with the original tar utility.
- eesmith 4y agoWhile GNU tar inherits this from the original tar, it doesn't seem to be something intrinsic to the PDP-11 or DEC given that the earlier Unix 'tap' archival system uses 'plain binary numbers ("base 256")', not octals. Here's the V7 tar.c: https://github.com/dspinellis/unix-history-repo/blob/Research-V7-Snapshot-Development/usr/src/cmd/tar/tar.c https://github.com/dspinellis/unix-history-repo/blob/Researc... and it's documentation: https://github.com/dspinellis/unix-history-repo/blob/Research-V7-Snapshot-Development/usr/man/man1/tar.1 https://github.com/dspinellis/unix-history-repo/blob/Researc... The C code clearly shows the octal (I've never used "%o" myself!): sscanf(dblock.dbuf.mode, "%o", &i); sp->st_mode = i; sscanf(dblock.dbuf.uid, "%o", &i); sp->st_uid = i; sscanf(dblock.dbuf.gid, "%o", &i); sp->st_gid = i; sscanf(dblock.dbuf.size, "%lo", &sp->st_size); sscanf(dblock.dbuf.mtime, "%lo", &sp->st_mtime); sscanf(dblock.dbuf.chksum, "%o", &chksum); Now, older versions of Unix supported DECTape, going back to the first manual from 1971 (see the "tap" command at http://www.bitsavers.org/pdf/bellLabs/unix/UNIX_ProgrammersManual_Nov71.pdf http://www.bitsavers.org/pdf/bellLabs/unix/UNIX_ProgrammersM... , page "5_06", which is 94 of 211 - the command-line interface is clearly related to tar). Here's the tp.5 format description from V6 at https://github.com/dspinellis/unix-history-repo/blob/Research-V6-Snapshot-Development/usr/doc/man/man5/tp.5 https://github.com/dspinellis/unix-history-repo/blob/Researc... DEC/mag tape formats ... Each entry has the following format: path name 32 bytes mode 2 bytes uid 1 byte gid 1 byte unused 1 byte size 3 bytes time modified 4 bytes tape address 2 bytes unused 16 bytes check sum 2 bytes These are in essentially the same order as the "struct file_header" for tar shown in the linked-to essay. But you can see at https://github.com/dspinellis/unix-history-repo/blob/Research-V6-Snapshot-Development/usr/sys/ino.h https://github.com/dspinellis/unix-history-repo/blob/Researc... that mtime is an int[2], so 4 bytes (yes, 16-bit integers; confirm with https://github.com/dspinellis/unix-history-repo/blob/Research-V6-Snapshot-Development/usr/sys/inode.h https://github.com/dspinellis/unix-history-repo/blob/Researc... showing i_mode is an integer). Which means this older "tap" DECTape support uses 'plain binary numbers ("base 256")', not octal.
- komadori 4y agoI wonder if Jörg Schilling's (RIP) star* handles this better. I recall he was pretty scathing about GNU tar back when I used Solaris. * http://cdrtools.sourceforge.net/private/star.html http://cdrtools.sourceforge.net/private/star.html
- asveikau 4y ago> Jörg Schilling's (RIP) As someone who burned a lot of CDs on Linux on the 90s, you bet i recognize that name, and didn't hear this news. https://lwn.net/Articles/872489/ https://lwn.net/Articles/872489/
- macintux 4y agoThere were some interesting personal anecdotes shared here: https://news.ycombinator.com/item?id=28827388 https://news.ycombinator.com/item?id=28827388
- mauvehaus 4y agoI didn't mention it there, but I was actually responsible for some pax format related work many years back and reached out to him with a question pertaining to his star implementation. He had strong feelings about his star being the star and an unrelated star archiving tool needing to be renamed. Something I was in no position to do or advocate for. I no longer remember if we actually discussed the technical matter or not at any point. I was wondering if mention of him would pop up in the comments since he wrote a tar (and possibly pax, I no longer remember) implementation.
- Kenji 4y ago
- mjevans 4y agobsdtar (libarchive) - I wonder if it avoids these issues?
- Twirrim 4y ago> Tar is pretty unusual for an archive file format. There's no archive header, no index of files to fascilitate seeking, no magic bytes to help file and its ilk detect whether a file is a tar archive, no footer, no archive-wide metadata. The only kind of thing in a tar file is a file object. tar = tape archive. It was designed around streaming files to a tape drive in a serial fashion. Tape bandwidth has almost always been slow compared to source data devices. You need to start writing to the target device as fast as possible. Taking time to construct a full index just delays starting the slowest stage of things, while providing only relatively minimal benefit. Generating an index is fairly straightforward, the file headers give you the information you need, including what you need to know to get to the next file header. Your only bottleneck is just how fast random reads are. If the file is on disk, it should be relatively trivial. It's even possible to do this relatively cheaply with Range headers if you're looking at a tar file stored on an HTTP endpoint, though you'll likely want to think about some smart pre-fetching behaviour.
- vetinari 4y agoThe issue with tapes is not the bandwidth, it is the seek latency, could be around ~2 minutes end to end (with the correct tape already loaded). So tapes are not used as random-access, thus no central index on tape archive. The backup software systems keep their catalogs elsewhere.
- Waterluvian 4y agoWhen I was a beginner I once accidentally created an Amazon RDS Postgres database backed by tape. I was so flustered by how slow it was until I saw the setting.
- ufo 4y agoLol! I'm curious how slow it got... How slow are we talking about here?
- Waterluvian 4y ago
- im3w1l 4y agoI have to say that using an archive format with this feature set for source distribution or really anything but backups makes me uneasy. When I unzip some file from the internet I dont want it putting files owned by some random uid in ../../. Like what if dogpictures.tar.gz contains a ../.bashrc. Untar from $USER/Downloads and whoops..
- tpoacher 4y agowait, is that a thing with tar??? EDIT: nevermind, I read the actual article. This only happens if you explicitly tell it to with the -P flag.
- Ekaros 4y agoI wonder if there could be better design. Maybe on packing side. Why wouldn't you order files and links in such way that single pass is enough.
- killingtime74 4y agoBetter design is not to use Tar
- userbinator 4y agoThe effect of restricting writes to only a directory and its descendants seems like the perfect use-case for chroot(), except that comes with some other limitations too. I started out computing in the PC world with the DOS family (then moving on to Windows) before working with any of the Unixes, so my perspective may be different from those who started with Unix/Linux, but in my experience it seems links (both soft and especially hard ones when applied to directories) cause a rather large number of problems in comparison to their usefulness; they make the filesystem a graph instead of a tree, adding complexity to all applications that need to traverse it.
- mort96 4y agoYou're not wrong about symlinks being problematic; there's an LWN post about it from yesterday: https://lwn.net/Articles/902247/ https://lwn.net/Articles/902247/ Luckily, most systems don't support directory hard links. (IIRC, maxOS does though, through some extremely hacky mechanism.)
- userbinator 4y agoI think you meant to link https://lwn.net/Articles/899543/ https://lwn.net/Articles/899543/ (and HN discussion at https://news.ycombinator.com/item?id=32190032 https://news.ycombinator.com/item?id=32190032 ) instead of that single comment. It takes the security angle (which is frankly oversold these days, but that's another rant...), but also makes some very good points about the complexity they introduce --- which does, among other things, create security issues. FWIW, I don't hardlinks are a good idea either. (In FAT filesystems, it is possible to have "hardlinks" where the same data is referred to by multiple names, but those are actually errors and referred to as "crosslinked files".) Without links, there's a 1-to-1 mapping between (absolute) paths and file contents. When operating on a path, there's no need to consider whether the API will act on the link or what it points to.
- saagarjha 4y agoAPFS does not support directory hardlinks, although HFS+ did.
- mdavidn 4y agoOne advantage of tar is that, because the format has no built-in support for compression or random access, the entire archive is compressed together. Similarities in adjacent files will improve the compression ratio. To support random access, the ZIP format must compress each file separately.
- orlp 4y agoThat's just not true, at least theoretically speaking (I have no idea about ZIP's actual internals). One could do a two-pass algorithm to find common substrings to build a dictionary, store this shared dictionary once, and then compress the files individually referring to this shared dictionary for the common substrings.
- bick_nyers 4y agoAs long as you have a pointer index in the header for the start/end of every individual file I don't see why that wouldn't work.
- lazide 4y agoWell, except no zip decompression library I know supports anything like that.
- deleted 4y ago[deleted]
- adrianmonk 4y agoYou definitely could. I did it for a proprietary format once. Each item was quite small (typically 100-ish bytes IIRC), and I needed random access. One approach would have been to split it into pages of a few kilobytes and separately compress those. But on this platform, I/O was primitive and very slow, and the CPU was also extremely slow. So it was advantageous to decompress only the necessary data. So I came up with a rudimentary custom compression algorithm. I scanned all entries for common strings and made a shared dictionary. Each entry was then stored as a sequence of indexes into the shared dictionary. Decompressing an entry was dead simple: read the sequence of dictionary indices and copy from the dictionary to the output. On a side note, the unexpected challenge of this method was how to choose which strings to put in the shared dictionary. I tried a few things and ended up with a heuristic that tries to balance favoring longer strings with favoring frequently occurring strings. I'm sure there are much better ways than that. If I had it to do over, I probably would have gone with the compressed pages approach simply because the implementation would've been done so much quicker. But I think I did achieve faster decompression and a better compression ratio.
- saagarjha 4y ago> You may think that the numeric values (file_mode, file_size, file_mtime, ...) would be encoded in base 10, or maybe in hex, or using plain binary numbers ("base 256"). But no, they're actually encoded as octal strings (with a NUL terminator, or sometimes a space terminator). Tar is the only file format I know of which uses base 8 to encode numbers. Tar’s “competitor”, cpio, does this as well (at least in one of the popular implementations). The Xcode XIP file, if you’re familiar with that particular format, is a couple layers of wrapping on top of a cpio archive, so deep inside my tool to expand these there’s a spot where I read these all out in a similar fashion: https://github.com/saagarjha/unxip/blob/5dcfe2c0f9578bc43070981ab89baec8610d8091/unxip.swift#L369 https://github.com/saagarjha/unxip/blob/5dcfe2c0f9578bc43070... More generally, though, both tar and cpio doesn’t have an index because they don’t need them, they’re meant to be decompressed in a streaming fashion where this information isn’t necessary. It’s kind of inconvenient if you want to extract a single file, but for large archives you really want to compress files together and maintaining an index for this is both expensive and nontrivial, so I guess these formats are just “good enough”.
- masklinn 4y agoGit also uses octal to encode entry modes in tree objects. That’s despite tree objects not being ascii-readable (object-ids are stored in binary form rather than the hex used in most other locations). TBF the only common numeric format I’ve yet to see is base64, git uses octal, decimal, hex, binary (BE), at least two completely different VLEs, plus a bitmap scheme.
- 1vuio0pswjnm7 4y ago"In any case, the result is that a tar extractor which wants to support both pax tar files and GNU tar files 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." https://github.com/libarchive/libarchive https://github.com/libarchive/libarchive
- jonpalmisc 4y agoHN crowd might have some interesting takes on this: what is your preferred archive (and/or compression) format, and why? I’ve been using .tar.xz for archiving, but haven’t looked into what the “best” option really is.
- na85 4y agoI have always been partial to .uha, the files produced by Uwe Herklotz' UHARC archive utility. I mostly ran into them on pirated game rips downloaded from DALnet IRC in the 90s and early aughts. It's extremely slow, however. If I was going to be packing lots of data I'd probably use mopaq (.mpq) which has support for LZMA and Huffman coding.
- forrestthewoods 4y agoI use windows, so .zip. Maybe on rare occasion .7z if I really want better compression. .tar.xz files are a gross pain on windows and I’m always annoyed when people use them.
- Affric 4y agoWhy are they a pain?
- auscompgeek 4y agoHow are tarballs any more of a pain than .7z?
- kasabali 4y agoI'll have a guess: because 7-zip gui doesn't decompress tar.gz files in a single step (ie. first you extract the tar, then you extract it again)
- forrestthewoods 4y agoIIRC 7zip actually does it in one step. But many tools such as WinZip do not. I forget the exact behavior of built-in, WinZip, and WinRar.
- mgerdts 4y agoThis is not a problem with the file format, it is a problem with the program that is interpreting it.
- sedatk 4y agoTL;DR, IIUIC: Hardlink creation code in tar checks if a hardlink created or not by going over a list of previously created hardlink placeholders, and does that every time it needs to create a hardlink.
- kentonv 4y agoPunchline: > 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.)
- romwell 4y agoYup, and that's worst-case quadratic in number of links (symlinks and hardlinks). It's still weird they didn't do a hashmap.
- account42 4y agoIt's C and they probably never thought of anyone having a file with that many links.
- mort96 4y agoTo clarify, the problem doesn't only exist with symlinks pointing outside of the extraction directory. The problem exists if the symlink's target path is a relative directory which contains "..". That means a symlink at "somedir/subdir1/foo" which points to "../bar" will also use the delayed link mechanism, even though the symlink doesn't point to outside of the extraction directory. Relative symlinks which contain ".." are incredibly common in some contexts.
- jepler 4y agoI wonder if the non-portable linux openat2 with RESOLVE_BENEATH could help with this problem. The documentation suggests that it should prevent escaping the intended location via ".." components literally or in symlinks.
- cyphar 4y agoAuthor of openat2(2) here, yes it would (as well as protecting against races where the target directory is having path components changed to symlinks during extraction). RESOLVE_IN_ROOT would be more akin to extracting in a chroot(2). But you would need to be careful how you deal with path operations in the rest of the program in a way that is fairly easy to mess up. I've been working on a userspace library[1] which would make writing userspace programs that interact with these kinds of dangerous paths more safe (though it's been on the backburner recently). [1]: https://github.com/openSUSE/libpathrs https://github.com/openSUSE/libpathrs
- ArrayBoundCheck 4y ago> I decided that learning the tar file format and making my own tar extractor would probably be faster than waiting for tar. And I was right; before the day was over, I had a working tar extractor, and I had successfully extracted my 1.1TiB tarball. That's awesome! I once did the same thing (something else, not a tar). I was on discord at the time and typed in messages about the stupid stuff I noticed while writing my own code. A guy told me I'm an asshole and a shit programmer/personality because I wasn't willing to use stick with/figure out standard tools + blocked me. Which is weird because why wouldn't you want more tools available. I gave away my source at the end Don't be afraid of writing your own stuff!
- Aeolun 4y agoI always used to think there was something magic about these formats (like, only really smart people would design a new format, and my custom csv was somehow ‘less’ than other formats), but now I’m older and I find that it’s just a bunch of files concatenated together to make a new one. The magic is lost, but I feel a lot better about myself :)
- jjice 4y agoThat's the beauty! It's just a bunch of files concated and when you throw compression algorithm X over it, it works pretty well. Super neat IMO.
- IshKebab 4y agoWell it's neat for a 10 minute hack on an internal project. Not so great that it's become the standard way of distributing files in Linux. Although in this case I'd say it's the fault of symlinks daring to exist and spew their flaws over everyone. Plus maybe slightly C's fault for not coming with a data structure library so everyone uses linked lists for everything. Presumably this wouldn't have happened in any other language (e.g. C++) because they would have used a set or hashmap or whatever. A stone age language dealing with a misguided filesystem feature for a brain-dead archive format. Surprising that it works at all really!
- jjice 4y agoConsidering there are other file formats that are used and occupy the same space as tar balls, the fact that tar balls are common for quite a bit of archiving should represent a win. Other formats (like zip, 7z, rar, etc) have come along and while they're in use and zips specifically are very common, tar balls are still used. Must speak something to them?
- IshKebab 4y agoI believe they're popular in Linux because they come preinstalled. Zip also can't store symlinks but I doubt that is very important in most situations.
- ctur 4y agoIn general, it is preferable now to use squashfs for most tar use cases three days. Random access, high compression levels, and completely operable with userland tools and a FUSE file system. tar does have some niche uses (streaming) but if you don’t need streaming, you can get massively faster compression into a format much more ergonomically pleasant.
- brongondwana 4y agoI have also written a tar format extractor, which is still in use for the backup system at Fastmail: https://metacpan.org/pod/Archive::Tar::Stream https://metacpan.org/pod/Archive::Tar::Stream It's capable of reading and writing tar files, and the big benefit over extracting is that you can repack a tar by (as the name says) streaming it, with a decision callback which allows you to discard, keep, or "edit" a file - where edit does unpack to a temporary file at which point you can arbitrarily change the file or the header info and then keep or discard once you're done.
- cdelsolar 4y agotar totally burned me very very recently. I wrote a Python script to create a tar file from a bunch of different ML model artifacts. The tar file untarred fine to my computer, but I could not open it with an existing Go program. The Go program would try to create files and folders if they weren’t available, but it seemed the way I had made the tar file, it didn’t “create an empty directory” first before adding the files in that directory. When I untarred it in the terminal with xvf I would see the files in the directories inside the tarball being created. But when I untarred a previous working version of this tarball, it would create the directory before untarring it. Googling all of this is impossible by the way. I couldn’t figure out how to get Python to create a “blank directory” first inside the tarball so eventually I gave up and made my script take in a path to an already existing folder instead of individual files.
- thomashabets2 4y agoIf you like the tar format then you may be interested in reading https://blog.habets.se/2019/11/CVE-2019-14866-gnu-cpio.html https://blog.habets.se/2019/11/CVE-2019-14866-gnu-cpio.html