{"id":1177,"date":"2010-11-23T15:44:19","date_gmt":"2010-11-23T14:44:19","guid":{"rendered":"http:\/\/glandium.org\/blog\/?p=1177"},"modified":"2010-12-04T12:36:28","modified_gmt":"2010-12-04T11:36:28","slug":"improving-libxul-startup-io-by-hacking-the-elf-format","status":"publish","type":"post","link":"https:\/\/glandium.org\/blog\/?p=1177","title":{"rendered":"Improving libxul startup I\/O by hacking the ELF format"},"content":{"rendered":"

If you have been following this blog during the past months, you might have gathered that I've been focusing on I\/O patterns on library initialization, more specifically libxul.so<\/code>. The very patterns there's not much to do about, except enduring them, or hacking ld.so<\/code> and\/or the toolchain. The latter is not necessarily easy, and won't benefit everyone until all linux distros use an improved glibc and\/or toolchain. This could take years before any actual result would reach end users.<\/p>\n

But with a little creativity, one can overcome these limitations and improve the situation today. Here is a summary of my recent hacks.<\/p>\n

<\/a><\/p>\n

Backwards static initializers<\/h2>\n

As Taras showed in the past<\/a>, static initializers are executed in reverse order. It turns out it is an unfortunate design choice in gcc<\/code>, and it also turns out not to impact all ELF binary files.<\/p>\n

As far as I know there are currently two different implementations of the static initializers call loop, one provided by gcc<\/code>, and one provided by ld.so<\/code>.<\/p>\n

In the gcc<\/code> case, the compiler creates a .ctors<\/code> section, starting with 0xffffffff<\/code>, ending with 0x00000000<\/code>, and filled with pointers to the various static initializer functions, in ascending order. The compiler also injects an initializer function, called from .init<\/code>, going through this .ctors<\/code> section, starting from the end (__do_global_ctors_aux<\/code> in crtend.o<\/code>). A similar .dtors<\/code> section is created for functions to run when the library is unloaded, and the pointers in it are called in ascending order. There is actually no importance in the order in which .ctors<\/code> and .dtors<\/code> are executed. All that matters is that they are executed in reverse order from each other, because that limits the risks of bad ordering. It is only unfortunate that .ctors<\/code> was chosen to be the one backwards.<\/p>\n

In the ld.so<\/code> case, the compiler creates a .init_array<\/code> section, filled with pointers to the various static initializer functions, in ascending order. It also stores the location and the size of this section in the PT_DYNAMIC<\/code> ELF header. At runtime, ld.so<\/code> itself reads this information and executes the static initializers in ascending orders. A similar .fini_array<\/code> section is created for functions to run when the library in unloaded, and ld.so<\/code> goes through it in descending order.<\/p>\n

The .init_array<\/code> section is newer, and for backwards compatibility reasons, is not used on systems that have been using the .ctors<\/code> approach forever. On the other hand, some newer ABIs, such as arm EABI, uses the new facility, which means they are not victim of backwards static initialization. I however wonder if backwards compatibility is still needed, considering how long .init_array<\/code> support has been around (more than 11 years, according to glibc git repository<\/a>).<\/p>\n

While we could obviously bug the gcc<\/code> maintainers to revert their .ctors<\/code> execution order, or ditch .ctors<\/code> support on glibc systems, which means we wouldn't get any immediate global benefit, we can also just revert the .ctors<\/code> section content<\/a>. Please note the source code out there doesn't take care of reverting the .dtors<\/code> section accordingly, because it is currently empty in libxul.so<\/code>.<\/p>\n

<\/a><\/p>\n

Relocations<\/h2>\n

As I mentioned in an earlier post<\/a>, relocations are what make it possible to load libraries at arbitrary locations. Unfortunately, a great number of relocations means awful I\/O patterns: ld.so<\/code> reads and applies them one by one, and while the kernel reads ahead by 128 KB chunks, when your relocation section exceeds that amount by more than an order of magnitude, it means I\/O goes back and forth a lot between the relocation section and where the relocations take place.<\/p>\n

There are two classes of relocations: REL and RELA. In both cases, there are several types of relocations, some of which require an addend. The difference between both classes is in REL relocations, the addend is stored at the offset the relocation takes place, and in RELA relocations, the addend is stored in the relocation entry. It means that RELA relocations effectively waste space, as the addend ends up actually being stored twice: it is also stored at the offset the relocation takes place, like with REL relocations, though it could technically be nulled out, there ; in any case, the space is wasted.<\/p>\n

REL relocations thus take 2 words of storage, and RELA relocations, 3. On x86, the ELF ABI only uses REL relocations, and words are 32 bits, making each relocation take 8 bytes ; on x86-64, the ELF ABI only uses RELA relocations, and words are 64 bits, thus making each relocation take 24 bytes, 3 times that of x86 relocations. On ARM, both may be used, but apparently the compiler and the linker only use REL relocations.<\/p>\n

These words of storage are used to store 3 or 4 bits of informations:<\/p>\n