What could have been. A time travel story of x32 and FatELF

I was toying around with the idea to write about this for a week or two by now, and I discussed it with Luca as well, but my main issue has been coming up with a title this time.. the original title I had in mind was a Marvel-style What if… “… x32 and FatELF arrived nine years ago”. But then Randall beat me to it with his hypothetical question answering site.

So let’s put some background in context; I criticised in the past Ryan’s FatELF idea and recently Intel’s x32 — but would I have criticised them the same way if the two of them came up almost together nine years ago? I don’t think so; and this is the main issue with this kind of ideas: you need the perfect timing or they are not worth much. Both of them came out at the wrong time in my opinion.

So here’s my scenario that didn’t happen and can’t happen now.

It’s 2003, AMD just launched their Opteron CPU which is the first sporting the new x86-64 ISA. Intel, after admitting to the failure of their ~~Itanic~~ Itanium project, releases IA-32e following suit. At the same time, though, they decide that AMD’s route of pure 64-bit architecture for desktop and servers is going to take too long to be production-ready, especially on Linux, as even just discussing multlib support is making LSB show its frailty.

They decide to thus introduce a new ABI, called x32 (in contrast with x64 used by Sun and Microsoft to refer to AMD’s original ABI). At the same time they decide to hire Ryan Gordon, to push forward a sketchy idea he proposed, about supporting Apple-style fat binaries in Linux — the idea was originally ignored because nobody expected any use out of a technique used in 1994 to move from M68k to PowerPC and then left to die with no further use.

The combined energy of Intel and Ryan came up with a plan on how to introduce the new ABI, and thus the new architecture, in an almost painless way. A new C library version is to be introduced in Linux, partially breaking compatibility with the current libc.so.6, but this is for the greatest good.

The new version of the C library, glibc 3.0, will bring a libc.so.7 for the two architectures, introducing a few incompatibility in the declarations. First of all, the largefile optional support is being dropped: both ABIs will use only 64-bit off_t, and to avoid the same kind of apocalyptic feeling of Y2K, they also decided to use 64-bit clock_t types.

These changes make a very slight dent into the usual x86 performance, but this is not really visible in the new x32 ABI. Most importantly, Intel wanted to avoid the huge work required to port to either IA-64 or AMD64, by creating an ILP32 ABI — where int, long and void * are all 32-bit. And here’s where Ryan’s idea comes to fruition.

Source code written in C will compile identically between x86 and x32, and thanks to the changes, aligning the size of some primitive standard types, even more complex data types will be identical between the two. The new FatELF extended format introduced by glibc 3.0 leverages this — original x86 code will be emitted in the .text section of the ELF, while the new code will live in .text32 — all the data, string and symbol tables are kept in single copy only. The dynamic loader can then map one or the other section depending on whether the CPU supports 64-bit instructions and all the dependencies are available on the new ABI.

Intel seems to have turned the tables under AMD’s nose with their idea, thanks to the vastly negative experience with the Itanium: the required changes to the compiler and loader are really minimal, and most of the softare will just build on the new ABI without any extra change, thanks to maintaining most of the data sizes of the currently most widespread architectures (the only changes are off_t behaving like largefile is enabled by default, and then clock_t that got extended). Of course this still requires vast porting of assembly-ridden software such as libav and most interpreter-based software, but all of this can easily happen over time thanks to Ryan’s FatELF design.

Dissolve effect running

Yes, too bad that Intel took their dear time to enter the x86-64 market, and even longer to come up with x32, to the point where now most of the software is already ported, and supporting x32 means doing most of the work again. Plus since they don’t plan on making a new version of the C library available on x86 with the same data sizes as x32, the idea of actually sharing the ELF data and overhead is out of question (the symbol table as well, since x86 still have the open/open64 split which in my fantasy is actually gone!) — and Ryan’s own implementation of FatELF was a bit of an over-achiever, as it doesn’t actually share anything between one architecture and the other.

So unfortunately this is not something viable to implement now (it’s way too late), and it’s not something that was implemented then — and the result is a very messed up situation.

A few more reason why FatELF is not

Seems like people keep on expecting Ryan Gordon’s FatELF to solve all the problems. Today I was told I was being illogical by writing that it has no benefits. Well, I’d like to reiterate that I’m quite sure of what I’m saying here! And even if this is likely going to be a pointless expedient, I’ll try to convey once again why I think even just by discussing that we’re wasting time and resources.

I have to say, most of the people pretending that FatELF is useful seem to be expert mirror-climber, so they changed so many ideas on how it should be used, where it should be used, and which benefits it has, that this post will jump from point to point quite confusingly. I’m sorry about that.

First of all, let me try to make this clear: FatELF is going to do nothing to make cross-arch development easier. If you want easier cross-arch or cross-OS development, you go with interpreted or byte-compiled languages such as Ruby, Python, Java, C#/.NET, or whatever else. FatELF focuses on ELF files, which are produced by the C, C+, Fortran compilers and the like. I can’t speak for Fortran as it’s a language that I do not know, but C and C+ datatypes are very much specific to architecture, operating system, compiler, heck even version of the libraries, system and 3rdparty! You cannot solve those problems with FatELF, as whatever benefits it has, they can only appear after the build. But at any rate, let’s proceed.

FatELF supposedly make build easier, but it doesn’t. If you really think so you have never ever tried building something for Apple’s Universal Binary. Support for autoconf and most likely any other build system along those lines, simply suck. The problem is that whatever results you get from a test in one architecture might not have the same result in the other. And Apple’s Universal Binary only encompass an operating system that has been developed without thinking too much of compatibility with others, and was under the same tight controls, where the tests for APIs are going to be almost identical for all the arches. (You might not know, but Linux’s syscall numbers are not the same across architectures; the reason is that they are actually designed to partly maintain compatibility with proprietary (and non) operating systems that originated on that architecture and were mainstream at the time. So for instance on IA-64 the syscall numbers are compatible with HP-UX, while on SPARC are compatible with Solaris, for the most part.)

This does not even come close to consider the mess of the toolchain. Of course you could have a single toolchain patched to emit code for a number of architectures, but is that going to work at all? Given that I have actually worked as a consultant building cross-toolchains for embedded architectures, I can tell you that it’s difficult enough to get one working. Count the need for patches for specific architectures, and you might start to get part of a pictures. While binutils already theoretically supports a “multitarget” build that adds in one build the support for all the architectures that they have written code for, doing the same for gcc is going to be a huge mess. Now you could (as I suggested) write a cc frontend that takes care of compiling the code for multiple architectures at the time, but as I said above it’s not easy to ensure the tests are actually meaningful between architectures, let alone operating systems.

FatELF cannot share data sections. One common mistake to make thinking about FatELF is that it only requires duplication of executable sections (.text), but that’s not the case. Data sections (.data, .bss, .rodata) are dependent on the data types, which as I said above are architecture dependent, and operating system dependent, and even library dependent. They are part of the ABI; each ELF you build for a number of target arches right now is going to have its own ABI, so the data sections are not shared. The best I can think of, to reduce this problem, is to make use of -fdata-sections and then merge sections with identical content; it’s feasible, but I’m sure that at the best of cases is going to create a problem with caching of near objects, and the best it’s going to cause misalignment of data to be read in the same pass. D’uh!

Just so you know how variable are the data sections: even though you could just use #ifdef, both the Linux kernel and the GNU C Library (and most likely uClibc as well even though I don’t have it around to double-check it) install different sets of headers; this should be an indication of how different the interfaces are between them.

Another important note here: as far as I could tell from the specifics that Ryan provided (I really can’t be arsed to look back at them right now), FatELF files are not interpolated, mixing the sections of them, but merged in a sort-of archive, with the loader/kernel deciding which parts of it will be loaded as a normal ELF. The reason for this decision likely lies in one tiny winy detail: ELF files were designed to be mapped straight from disk to data structures in memory; for this reason, ELF have classes and data orders. For instance x86-64 uses ELF of class 64 and order LSB (Least-significant bit first, or little-endian) while PPC uses ELF of class 32 and order MSB (Most-significant bit first, or big-endian). It’s not just a matter of the content of .text but it’s also pervasive in the index structures within the ELF file, and it is so for performance reasons. Having to swap all the data or deal with different sizes is not something you want to do in the kernel loader.

When do you distribute a FatELF? This is one tricky question because both Ryan and various supporters change opinion here more often they change socks. Ryan said that he was working on getting an Ubuntu built entirely of FatELFs, leaving to intend that distributions would be using FatELF for their packaging. Then he said that it wasn’t something for packagers but for Indipendent Software Vendors (ISVs). Today I was told that FatELF simplifies the distribution by distributing a single executable that can be “executed in place” rather than having to provide two of them.

Let’s be clear: distributors are very unlikely to provide FatELF binaries in their packages. Even though it might sound tenting to implement multilib with them, it’s going to be a mess just the same; it might reduce the size of the whole archive of binary packages, because you share the non-ELF files between architectures, but it’ll increase the used traffic to download them, and while disk space is mostly getting cheaper and cheaper, network traffic is still a rare commodity. Even more so, users won’t like to have installed stuff for architectures that they don’t use, and will likely ask for a way to clean them up, at which point they’ll wonder why they are downloading it at all. Please note that while Apple did their best to convince people to use Universal Binary, a number of software was produced to strip the alternative architecture files from their executable files at all.

Today I was offered, as I said, that it is easier to distribute one executable file rather than two. But when are you found doing that at all? Quite rarely; ISVs provide pre-defined packaging, usually in form of binary packages for the particular distribution (this already makes it a multiple-file download). Most complex software will be in an archive anyway because you don’t just build everything in but rather put it in different files: icons, images, … even Java software that actually use archives as main object format (JAR files are ZIP files), ships in archives installing separate data files, multiple JARs, wrapper scripts and so on so forth. I was also told that you could strip the extra architectures at install time, but if you do so, you might as well decide which of multiple files to install, making it moot to use a fat binary at all.

All in all, I still have to see one use case that actually can be solved by FatELF better than a few wrapper scripts and an archive. Sure you can create some straw-man arguments where FatELF works and scripts don’t, such as the “execute in-place” idea above, but really tell me when was the last time you needed that? Please also remember that while “changes happen everytime”, we’re talking about changing in a particularly invasive way a number of layers:

the kernel;
the loader;
the C library (separated from the loader!);
the compiler, has almost to be rewritten;
the linker, obviously;
the tools to handle the files;
all the libraries that change API among architectures.

Even if all of this became stock, there’s a huge marginal cost here, and it’s not going to happen anytime soon. And even if it did, how much time is going to take before it gets mainstream enough to be used by ISVs? There are some that sill support RHEL3.

There are “smaller benefits”, as, again, I was told before, and those are not nothing. Maybe that’s the case but the question is “is it worth it?”. Once in the kernel is not going to take much work at runtime, but is it work the marginal cost of implementing all that stuff and maintaining it? I most definitely don’t think so. I guess the only reason why Apple coped with that is that they had most of the logic code already developed and laying around from when they transitioned from M68K to PowerPC.

I’m sorry to burst your bubbles, but FatELF was an ill-conceived idea, that is not going to gain traction for a very good reason: it makes no sense! Any of the use-cases I have read up to now are straw-men, that either resemble what OSX does or what Windows does. But Linux is neither. Now, let’s move on, please?

What distributions want

Or A 101 lesson on how to ensure that your software package is available to the distribution users (which, incidentally, are the Linux users; while already the conglomerate Linux marketshare is pretty low when compared with Windows and OS X, the marketshare of not-really-distributions like Slackware or Linux from scratch is probably so trivial that you don’t have to care about them most of the time. That, and their users are usually not so much scared about installing stuff by themselves.

I’m posting this quickie because I’d like to tell one other thing to Ryan… yes, you are a drama queen. And you proven it right with your latest rant and it really upsets me that instead of trying to understand the problem your solution seems to be closing yourslef even more inside your little world. It upsets me because I can see you as a capable programmer and I’d prefer your capacity being used for something that people can benefit from, rather than wasted on stuff pointless, like FatELF.

The fact that instead of trying to understand the technical points that me and others made, and tell us why you think they are not good enough, you’re just closing yourself further. By saying that “lots of people talked about it” you’re just proving what you’re looking for: fame and glory. Without actual substantial results to back it up. Just an hint: the people who matters aren’t those who continue saying “FatELF will make distributions useless, will make it possible to develop cross-platform software, will solve the world’s hunger”; the people who matters are those that review FatELF for its technical side, and most of us already deemed it pointless; I already explained what I think about it.

Any ISV that thinks FatELF will solve their cross-distribution or cross-architecture problems have no idea what an ELF file is; they don’t really understand the whole situation at all. I’m pretty sure there are such ISV out there… but I wouldn’t really look forward for them to decide what to put inside the kernel and the other projects.

Do you want your software (your games) to be available to as many people as possible? Start working with the freaking distributions! You don’t need to have mastered all the possible package managers, you don’t even need to know about any of them directly, but you got to listen if packagers ask for some changes. If a packager asks you to unbundle a library or allow selecting between bundled or system library; do it, they have their reasons and they know how to deal with eventual incompatibilities. If a packager asks you to either change your installation structure or at least make it flexible, that’s because with a very few exceptions, distributions are fine with following the FHS.

Take a look to “Distributions-friendly packages”: part 1 part 2 and part 3 .

But no, Ryan’s solution here is again taking cheap shots to distributions and packagers, without actually noticing that, after more than ten years distributions are not going away.

Oh and the first commenter who will try to say again that FatELF is the solution, can please tell me how’s that going to ensure that the people writing the code will understand the difference between little endian and big endian? Or that the size of a pointer is not always 32-bit? Count that in as a captcha; if you cannot give me an answer to those two questions, your comment supporting FatELF as The Solution will be deleted.

ELF should rather be on a diet

I’ve been first linked the FatELF project in late October by our very own solar; I wanted to write some commentary about it but I couldn’t find the time; today the news is that the author gave up on it after both Linux kernel and GLIBC developer dissed his idea. The post where he noted his intention to discontinue the project looks one drama-queen of a post regarding the idea of contributing to other projects… I say that because, well, it’s always going to be this way if you think about an idea, don’t discuss it before implementing, and then feel angry for the rejection when it comes. I’m pretty sure that no rejection was personal in this rejection, and I can tell you that what I would have written after reading about it the first time would have been “Nice Proof of Concept, but it’s not going to fly”.

Let’s first introduce the idea behind the project: to copy Apple’s “Universal Binaries”, that technique that allowed programs to run both on PPC-based Mac as well as the new Intel-based Mac when they decided to make the transaction, this time applying the same principle to the ELF files that are used on basically all modern UNIX and Unix-like systems (Linux, *BSD, Solaris). There is a strange list of benefits in the project’s homepage; I say strange because they really seem straw arguments for creating FatELF, since I rarely have seen this applied in real world.

Let’s be clear, when Ulrich Drepper (who’s definitely not the most charming developer in our community) says this:

Yes. It is a “solution” which adds costs in many, many places for a problem that doesn’t exist. I don’t see why people even spend a second thinking about this.

I’m not agreeing to the fact that nobody should have spent a second thinking about the idea; toying with ideas, even silly ideas like this one (because as you’ll soon see, this is a silly idea), is always worth it: it gives you an idea of how stuff works, they might actually lead somewhere, or they might simply give yo the sense of proportion of why they don’t work. But there are things to consider when doing stuff like this, and the first is that if there is a status quo, it might be worth discussing the reason of that status quo before going in full sprint and spend a huge amount of time to implement something, as the chance that’s just not going to work is quite high.

To make an example of another status quo-fiddling idea, you might remember Michael Meeks’s direct bindings for ELF files; the idea was definitely interesting, it proven quite fast as well, but it didn’t lead anywhere; Michael, and others including me, “wasted” time in testing it out, even though it was later blocked by Drepper with enough reasons and it’s no longer worked on. Let me qualify that “wasted” though: it was wasted only from the point of view of that particular feature, which led nowhere, but that particular work was what actually made me learn how the two linkers worked together, and got me interested in problems of visibility and cow as well as finding out one xine bug that would have been absolutely voodoo to me if I didn’t spend time learning about symbol resolution before.

Back to FatELF now: why do I think the idea is silly? Why am I agreeing with Drepper about the fact that it’s a solution with too high costs for the unrequested results? Well the first point to make is when Apple made the first step toward universal binaries; if you think the idea sprouted during the PPC to Intel transition, you’re wrong. As Wikipedia notes Apple’s first fat binary implementation dates back to 1994. During the M68K to PPC transition. Replicating the same procedure for an architecture change wasn’t extremely difficult to them to begin with, even though it wasn’t OSX that was used during that particular transition. The other fact is that the first Intel transition was – for their good or bad – a temporary one. As you can probably have noted, they are now transitioning from i386 software to x86-64 software (after my post on PIE you can probably guess why that’s definitely important to them).

But it goes much further than that: Apple has a long history of allowing users to port the content their computer from one to the next with each update, and at the same time they have a lot of third party providing software; since third parties started upgrading to universal binaries before Intel Macs were released for the users, if users kept up to date with the release, one they got their new Intel Mac they would just had to copy the content from the old to the new system and be done with it. This is definitely due to the target audience of Apple.

There is another thing to know about Apple and OS X, that you might not know about if you’ve never used a Mac: applications are distributed in bundles, which are nothing more than a directory structure, inside which the actual binary is hidden; inside the bundle you find all the resources that are needed for the program to run (translations, pictures, help files, generic data files, and so on). To copy an application you only have to copy the bundle, to remove almost all applications you just shove the bundle in the trash can. This forces distributions to happen in bundles as well, which is why Universal Binaries were so important to Apple: the same bundle had to work for all people so that it could still be copied identical between one computer to the other and work, no matter the architecture. This is also why, comparing the size of bundles built Universal, PPC-only and Intel-only, the first is not as big as the size of the other two: all the external resources are shared.

So back to Linux, and see how this applies: with a single notable exception all the Linux distributions out there use a more or less standard Filesystem Hierarchy Standard compatible layout (some use LSB-compatible layout, the two are not one and the same, but the whole idea is definitely similar). In such a setup, there are no bundles, and the executable code is already separated from the code that is not architecture-dependent (/usr/share) and thus shareable. So the only parts that cannot be shared, that FatELF would allow to be shared are the executable code parts, like /bin and /lib.

Now let’s start with understanding where the whole idea is going to be applied: first of all, Linux distributions, by their own design, have a central repository for software, which OS X does not have; and that central repository can be set up at installation time for getting the correct version of the software, without asking the user to know about the architecture by itself. The idea of using fat binaries to reduce the size of that repository is moot: the shareable data is already, for most distributions I know, shared in -noarch packages (arch-independent); the only thing you’d be able to spare would be the metadata of packages, which I’m quite sure for most “big” applications is not going to be that important. And on the other hand, the space you’d be saving on the repository side is going to be wasted by the users on their harddrive (which is definitely going to be disproportionally smaller) and by the bandwidth used to push the data around (hey, if even Google is trying to reduce the downloaded size fatelf is not only going against the status quo but also the technical trend!).

And while I’m quite sure people are going to say that once again, disk space is cheap nowadays, and thus throwing more disks at the problem is going to fix it, there is one place where it’s quite difficult to throw more space at it: CDs and DVDs, which is actually one of the things that FatELF is proposing to make easier, probably in light of users not knowing whether their architecture is x86, amd64 or whatever else. Well, this is already been tackled by projects such as SysRescueCD that provide two kernels and a single userland for the two architectures, given that x86-64 can run x86 code.

The benefits listed in FatELF’s page seem also to focus somewhat to the transition between one arch and the other, like it’s now happening between x86 and x86-64; sure it looks like a big transition and quite a few players in the market are striving to do their best to make the thing as smooth as possible, but either we start thinking of the new x86-64 as the arch, and keep x86 as legacy, or we’re going to get stuck in a transition state forever; Universal Binaries for Apple played a fundamental role in what has been a temporary transition, and one they actually completed quite fast: Snow Leopard does no longer support PPC systems, and everybody is expected the next iteration (10.7) to drop support for 32-bit Intel processors entirely to make the best use of the new 64-bit capabilities. Sure there could be some better handling of transitioning between architectures in Linux as well, especially for people migrating from one system to the other, but given the way distributions work, it’s much easier for a new install to pick up the home directories set up in the older system, import the configuration, and then install the same packages that are installed in the previous one.

After all, FatELF is a trade-off: you trade bigger binaries for almost-universal compatibility. But is the space the only problem at stake here? Not at all; to support something like FatELF you need changes at a high number of layers; the same project page shows that changes were needed in the Linux kernel, the C library (glibc only, but Linux supports uclibc as well), binutils, gdb, elfutils and so on. For interpreted language bindings you also have to count in changing the way Ruby, Python, Java, and the others load their libraries since they now hardcode the architecture information in the path.

Now, let’s get to the real only speakable benefit in that page:

A download that is largely data and not executable code, such as a large video game, doesn’t need to use disproportionate amounts of disk space and bandwidth to supply builds for multiple architectures. Just supply one, with a slightly larger binary with the otherwise unchanged hundreds of megabytes of data.

You might or might know that icculus.org where the FatELF project is hosted is the home of the Linux port of Quake and other similar games, so this is likely the only real problem that was, up to now, really come up before: having big packages for multiple arches that consists mostly of shareable data. As said before, distributions already have architecture-independent packages most of the time; it’s also not uncommon for games to separate the data from the engine source itself, since the engine is much more likely to change than the data (and at the same time, if you use the source version you still need the same data as the binary version). The easiest solution is thus to detach the engine from the data and get the two downloaded separately; I wonder what the issue is with that.

On the other hand, there is a much easier way to handle all this: ship multiple separate ELF binaries in the same binary package, then add a simple sh script that calls the right one for the current host. This is quite easy to do, and requires no change at any of the previously-noted layers. Of course, there is another point made on the FatELF project page that this does not work with libraries… but it’s really not that of an issue, since the script can also set LD_LIBRARY_PATH to point to the correct path for the current architecture as well. Again, this would solve the same exact problem for vendors without requiring any change at all in the layers of the operating system. It’s transparent, it’s easy, it’s perfectly feasible.

I hear already people complaining “but a single FatELF file would be smaller than multiple ELF files!”. Not really. What you can share between the different ELF objects, in theory, is still metadata only (and I’m not convinced by the project page alone that that’s what it’s going to do, it seems to me like it’s a sheer bundling of files together): SONAME, NEEDED entries and similar. Unless you also start bundling different operating systems together – which is what the project also seem to hint at – because in that case you also have no warranty that the metadata is going to be the same: the same code will require different libraries depending on the operating system it’s built for.

Generally, an ELF file is composed of executable code, data, metadata related to the ELF file itself, and then metadata related to the executable code (symbol tables, debugging information) and metadata related to the data (relocations). You can barely share the file’s metadata between architectures, you definitely cannot share it between operating systems as stated above (different SONAME rules, different NEEDED).

You could share string data, since that’s actually the same between different architectures and operating systems most of the time but that’s not really a good reason; you cannot share constant data because there are different ordering, different sizes and different paddings across architectures, even two very alike like x86 and x86-64 (which is why it’s basically impossible to have inter-ABI calls!).

You cannot share debugging information either (which might be the big part of an ELF file) because it’s tied to the offset of the executable code, and the same applies to the symbol tables.

So, bottomline, since there are quite a few strawy benefits on the FatELF project page, here is a list of problems caused by that approach:

introduces a non-trivial amount of new code at various layers of the system (kernel, loader, linker, compiler, debugger, language interpreters, …), it doesn’t matter that a lot of that code is already published by now, it has to be maintained long-time as well, and this introduces a huge amount of complexity;
would increase dramatically the size of downloading packages for the optimistic case (a single architecture throughout a household or organisation) since each package would comprise of multiple architectures at once;
would use up more space on disk since each executable and library would then be duplicated entirely multiple times; note that at the time Universal Binaries started popping up on systems, more than one software was released to strip the other architecture out of them to reduce space to be wasted on already-ported or won’t-be-ported systems; while FatELF obviously comes with the utilities by itself, I’m pretty sure most tech-savvy users would then decide simply to strip off the architectures that are useless to them;
would require non-trivial cross-compilation from build servers which right now all the distributions, as far as I know, tend to avoid.

In general, distributions will definitely never going to want to use this; free software projects would probably employ better their time by making sure the software is easily available in distributions (which often means they should talk to distributors to make sure their software has an usable build system and runtime configuration); proprietary software vendors might be interested in something like that – if they are insane or know nothing about ELF, that is – but even then the whole stack of changes needed is going to be way disproportionate to the advantages/

So I’m sorry if Ryan feels bad about contributing to other projects now because people turned down his idea, but maybe he should try for once to get out of his little world and see how things work with other projects involved, like discussing stuff first, asking around and proposing: people would have turned him down with probably most of the same arguments I used here today, without him having to spend time writing unused (and unusable) code.