64-bit Archives Needed
- by user9154181
A little over a year ago, we received a question from someone who
was trying to build software on Solaris. He was getting errors
from the ar command when creating an archive. At that time, the ar
command on Solaris was a 32-bit command. There was more than
2GB of data, and the ar command was hitting the file size limit
for a 32-bit process that doesn't use the largefile APIs.
Even in 2011, 2GB is a very large amount of code, so we had not heard
this one before. Most of our toolchain was extended
to handle 64-bit sized data back in the 1990's, but archives were not changed,
presumably because there was no perceived need for it. Since then of course,
programs have continued to get larger, and in 2010, the time had finally come
to investigate the issue and find a way to provide for larger archives.
As part of that process, I had to do a deep dive into the archive
format, and also do some Unix archeology. I'm going to record what I
learned here, to document what Solaris does,
and in the hope that it might help someone else trying to solve the same
problem for their platform.
Archive Format Details
Archives are hardly cutting edge technology. They are still used of
course, but their basic form hasn't changed in decades. Other than to
fix a bug, which is rare, we don't tend to touch that code
much. The archive file format is described in /usr/include/ar.h,
and I won't repeat the
details here. Instead, here is a rough overview of the archive file format,
implemented by System V Release 4 (SVR4) Unix systems such as Solaris:
Every archive starts with a "magic number". This is a sequence
of 8 characters: "!<arch>\n".
The magic number is followed by 1 or more members. A
member starts with a fixed header, defined by the
ar_hdr structure in/usr/include/ar.h.
Immediately following the header comes the
data for the member. Members must be padded at the end with newline
characters so that they have even length.
The requirement to pad members to an even length is a dead giveaway
as to the age of the archive format. It tells you that this format
dates from the 1970's, and more specifically from the era of 16-bit
systems such as the PDP-11 that Unix was originally developed on.
A 32-bit system would have required 4 bytes, and 64-bit systems
such as we use today would probably have required 8 bytes.
2 byte alignment is a poor choice for ELF object archive members.
32-bit objects require 4 byte alignment, and 64-bit objects require
64-bit alignment. The link-editor uses mmap() to process
archives, and if the members have the wrong alignment, we have to
slide (copy) them to the correct alignment
before we can access the ELF data structures inside. The archive
format requires 2 byte padding, but it doesn't prohibit more.
The Solaris ar command takes advantage of this, and pads ELF
object members to 8 byte boundaries. Anything else is padded to 2
as required by the format.
The archive header (ar_hdr) represents all numeric
values using an ASCII text representation rather than as binary
integers. This
means that an archive that contains only text members can be viewed
using tools such as cat, more, or a text
editor. The original designers of this format clearly thought
that archives would be used for many file types, and not just for
objects. Things didn't turn out that way of course
— nearly all
archives contain relocatable objects for a single operating system
and machine, and are used primarily as input to the link-editor (ld).
Archives can have special members that are created by
the ar command rather than being
supplied by the user. These special members
are all distinguished by having a name that starts with the slash (/)
character. This is an unambiguous marker that says that the user could
not have supplied it. The reason for this is that regular archive members
are given the plain name of the file that was inserted to create them,
and any path components are stripped off. Slash is the delimiter
character used by Unix to separate path components, and as such
cannot occur within a plain file name.
The ar command hides
the special members from you when you list the contents of an archive,
so most users don't know that they exist.
There are only two possible special members: A symbol table that maps
ELF symbols to the object
archive member that provides it, and a string table used to hold
member names that exceed 15 characters. The '/' convention for tagging
special members provides room for adding more such members should the
need arise. As I will discuss below, we took advantage of this fact
to add an alternate 64-bit symbol table special member which is used in
archives that are larger than 4GB.
When an archive contains ELF object members, the ar command builds
a special archive member known as the symbol table that
maps all ELF symbols in the object to the archive member that provides
it. The link-editor uses this symbol table to determine which symbols
are provided by the objects in that archive.
If an archive has a symbol table, it will always be the first
member in the archive, immediately following the magic number. Unlike
member headers, symbol tables do use binary integers to represent
offsets. These integers are always stored in big-endian format,
even on a little endian host such as x86.
The archive header (ar_hdr) provides 15 characters for representing
the member name. If any member has a name that is longer than this,
then the real name is written into a special archive member called
the string table, and the member's name field instead
contains a slash (/) character followed by a decimal representation of
the offset of the real name within the string table.
The string table is required to precede all normal archive members,
so it will be the second member if the archive contains a symbol
table, and the first member otherwise.
The archive format is not designed to make finding a given
member easy. Such operations move through the archive from front
to back examining each member in turn, and run in O(n) time. This would be
bad if archives were commonly used in that manner, but in general,
they are not.
Typically, the ar command is used to build an new archive from
scratch, inserting all the objects in one operation, and then the
link-editor accesses the members in the archive in constant time
by using the offsets provided by the symbol table. Both
of these operations are reasonably efficient. However, listing the contents
of a large archive with the ar
command can be rather slow.
Factors That Limit Solaris Archive Size
As is often the case, there was more than one limiting factor
preventing Solaris archives from growing beyond the 32-bit limits
of 2GB (32-bit signed) and 4GB (32-bit unsigned). These limits are listed
in the order they are hit as archive size grows, so the earlier ones
mask those that follow.
The original Solaris archive file format can handle sizes up to 4GB
without issue. However, the ar command was delivered as a
32-bit executable that did
not use the largefile APIs. As such, the ar command itself could
not create a file larger than 2GB. One can solve this by
building ar with the largefile APIs which would allow it to
reach 4GB, but a simpler and better answer is to deliver a 64-bit
ar, which has the ability to scale well past 4GB.
Symbol table offsets are stored as 32-bit big-endian
binary integers, which limits the maximum archive size
to 4GB. To get around
this limit requires a different symbol table format, or
an extension mechanism to the current one, similar in nature to
the way member names longer than 15 characters are handled in
member headers.
The size field in the archive member header (ar_hdr)
is an ASCII string capable of representing a 32-bit unsigned
value. This places a 4GB size limit on the size of any individual
member in an archive.
In considering format extensions to get past these limits, it is
important to remember that very few archives will require
the ability to scale past 4GB for many years. The old format, while
no beauty, continues to be sufficient for its purpose. This argues for
a backward compatible fix that allows newer versions of Solaris to
produce archives that are compatible with older versions of the system
unless the size of the archive exceeds 4GB.
Archive Format Differences Among Unix Variants
While considering how to extend Solaris archives to scale to 64-bits,
I wanted to know how similar archives from other Unix systems
are to those produced by Solaris, and whether they had already
solved the 64-bit issue. I've successfully moved archives between
different Unix systems before with
good luck, so I knew that there was some commonality. If it
turned out that there was already a viable defacto standard for 64-bit archives,
it would obviously be better to adopt that rather than invent something new.
The archive file format is not formally standardized. However, the
ar command and archive format were part of the original Unix
from Bell Labs. Other systems started with that format, extending it in various
often incompatible ways, but usually with the same common shared core. Most of
these systems use the same magic number to identify their archives, despite
the fact that their archives are not always fully compatible with each other.
It is often true that archives can be copied between different
Unix variants, and if the member names are short enough, the ar command from
one system can often read archives produced on another.
In practice,
it is rare to find an archive containing anything other than objects for
a single operating system and machine type. Such an archive is only of
use on the type of system that created it, and is only used on that system.
This is probably why cross platform compatibility of archives between Unix
variants has never been an issue. Otherwise, the use of the same
magic number in archives with incompatible formats would be a problem.
I was able to find information for a number of
Unix variants, described below. These can be divided roughly into three
tribes, SVR4 Unix, BSD Unix, and IBM AIX. Solaris is a SVR4 Unix, and its
archives are completely compatible with those from the other members
of that group (GNU/Linux, HP-UX, and SGI IRIX).
AIX
AIX is an exception to rule that Unix archive formats are all
based on the original Bell labs Unix format. It appears that AIX
supports 2 formats (small and big), both of which differ in
fundamental ways from other Unix systems:
These formats use a different magic number than the standard
one used by Solaris and other Unix variants.
They include support for removing archive members from
a file without reallocating the file, marking dead areas as
unused, and reusing them when new archive items are inserted.
They have a special table of contents member (File Member Header)
which lets you find out everything that's in the archive
without having to actually traverse the entire file. Their symbol
table members are quite similar to those from other systems though.
Their member headers are doubly linked, containing offsets to
both the previous and next members.
Of the Unix systems described here, AIX has the only format I saw
that will have reasonable insert/delete performance for really large
archives. Everyone else has O(n) performance, and are going to be
slow to use with large archives.
BSD
BSD has gone through 4 versions of archive format, which are
described in their
manpage. They use the same member header as SVR4, but their symbol table
format is different, and their scheme for long member
names puts the name directly after the member header rather than into
a string table.
GNU/Linux
The GNU toolchain uses the SVR4 format, and is compatible with
Solaris.
HP-UX
HP-UX seems to follow the SVR4 model, and is compatible with
Solaris.
IRIX
IRIX has 32 and 64-bit archives. The 32-bit format is the
standard SVR4 format, and is compatible with Solaris. The 64-bit format
is the same, except that the symbol table uses
64-bit integers.
IRIX assumes that an archive
contains objects of a single ELFCLASS/MACHINE, and any archive containing
ELFCLASS64 objects receives a 64-bit symbol table. Although they only use
it for 64-bit objects, nothing in the archive format limits it
to ELFCLASS64. It would be perfectly valid to produce a 64-bit
symbol table in an archive containing 32-bit objects, text files, or
anything else.
Tru64 Unix (Digital/Compaq/HP)
Tru64 Unix uses a format much like ours, but their symbol table is
a hash table, making specific symbol lookup much faster. The Solaris
link-editor uses archives by examining the entire
symbol table looking for unsatisfied symbols for the link, and not
by looking up individual symbols, so there would be no benefit to
Solaris from such a hash table. The
Tru64 ld must use a different approach in which the hash table pays
off for them.
Widening the existing SVR4 archive symbol tables rather than inventing something
new is the simplest path forward. There is ample precedent for this
approach in the ELF world. When ELF was extended to support 64-bit objects,
the approach was largely to take the existing data structures, and define
64-bit versions of them. We called the old set ELF32, and the new set ELF64.
My guess is that there was no need to widen the archive format at that time,
but had there been, it seems obvious that this is
how it would have been done.
The Implementation of 64-bit Solaris Archives
As mentioned earlier, there was no desire to improve the fundamental
nature of archives. They have always had O(n) insert/delete behavior, and
for the most part it hasn't mattered. AIX made efforts to improve this,
but those efforts did not find widespread
adoption. For the purposes of link-editing, which is essentially the
only thing that archives
are used for, the existing format is adequate, and issues of backward
compatibility trump the desire to do something technically better.
Widening the existing symbol table format to 64-bits is therefore the
obvious way to proceed. For Solaris 11, I implemented that,
and I also updated the ar command so that a 64-bit
version is run by default. This eliminates the 2 most significant limits
to archive size, leaving only the limit on an individual archive member.
We only generate
a 64-bit symbol table if the archive exceeds 4GB, or when the new -S
option
to the ar command is used. This maximizes backward compatibility, as an
archive produced by Solaris 11 is highly likely to be less than 4GB in
size, and will therefore employ the same format understood by
older versions of the
system. The main reason for the existence of the -S option is to allow
us to test the 64-bit format without having to construct huge archives to
do so. I don't believe it will find much use outside of that.
Other than the new ability to create and use extremely large archives,
this change is largely invisible to the end user. When reading an
archive, the ar command will transparently accept either form of symbol table.
Similarly, the ELF library (libelf) has been updated to understand
either format. Users of libelf (such as the link-editor ld) do not need
to be modified to use the new format, because these changes are encapsulated
behind the existing functions provided by libelf.
As mentioned above, this work did not lift the limit on the
maximum size of an individual archive member. That limit remains fixed
at 4GB for now. This is not because we think objects will never get that
large, for the history of computing says otherwise. Rather, this is based
on an estimation that single relocatable objects of that size will not
appear for a decade or two. A lot can change in that time, and it is better not
to overengineer things by writing code that will sit and rot for years
without being used.
It is not too soon however to have a plan for that eventuality. When
the time comes when this limit needs to be lifted, I believe that there
is a simple solution that is consistent with the existing format.
The archive member header size field is an ASCII string, like the name,
and as such, the overflow scheme used for long names can also be used to
handle the size. The size string would be placed into the archive string
table, and its offset in the string table would then be written into the
archive header size field using the same format "/ddd" used for overflowed
names.
