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. The very patterns there s not much to do about, except enduring them, or hacking
ld.so 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.
But with a little creativity, one can overcome these limitations and improve the situation today. Here is a summary of my recent hacks.
Backwards static initializers
As
Taras showed in the past, static initializers are executed in reverse order. It turns out it is an unfortunate design choice in
gcc, and it also turns out not to impact all ELF binary files.
As far as I know there are currently two different implementations of the static initializers call loop, one provided by
gcc, and one provided by
ld.so.
In the
gcc case, the compiler creates a
.ctors section, starting with
0xffffffff, ending with
0x00000000, and filled with pointers to the various static initializer functions, in ascending order. The compiler also injects an initializer function, called from
.init, going through this
.ctors section, starting from the end (
__do_global_ctors_aux in
crtend.o). A similar
.dtors 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 and
.dtors 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 was chosen to be the one backwards.
In the
ld.so case, the compiler creates a
.init_array 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 ELF header. At runtime,
ld.so itself reads this information and executes the static initializers in ascending orders. A similar
.fini_array section is created for functions to run when the library in unloaded, and
ld.so goes through it in descending order.
The
.init_array section is newer, and for backwards compatibility reasons, is not used on systems that have been using the
.ctors 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 support has been around (more than 11 years, according to
glibc git repository).
While we could obviously bug the
gcc maintainers to revert their
.ctors execution order, or ditch
.ctors support on glibc systems, which means we wouldn t get any immediate global benefit, we can also just
revert the .ctors section content. Please note the source code out there doesn t take care of reverting the
.dtors section accordingly, because it is currently empty in
libxul.so.
Relocations
As I mentioned in an
earlier post, 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 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.
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.
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.
These words of storage are used to store 3 or 4 bits of informations:
r_offset: the offset at which the relocation takes placer_info: containing both the relocation type and a symbol reference for the relocation. On 32 bits systems, the symbol reference is stored on 24 bits, and the relocation type on 8 bits. On 64 bits systems, the symbol reference is stored on 32 bits, and the relocation type on 32 bits (which means at least 24 bits are never going to be used: there are currently no ABI using more than 256 relocation types).r_addend: The addend, only in RELA relocations
The linker splits relocations in two main categories: those for dynamic linking at startup and those for procedure linkage table (PLT) resolution at runtime. Here is what the repartition look like on
libxul.so (taken from the mozilla-central nightly from Nov, the 22nd):
|
dynamic relocations |
PLT relocations |
| Architecture |
number |
size (bytes) |
number |
size (bytes) |
| x86 |
231,836 |
1,854,688 |
3,772 |
30,176 |
| x86-64 |
235,893 |
5,661,432 |
3,773 |
90,528 |
So, PLT relocations are quite negligible, and dynamic relocations are just huge, especially on x86-64. Compared to the binary size, it s pretty scary:
| Architecture |
libxul.so size |
relocations size |
% |
| x86 |
21,869,684 |
1,884,864 |
8.61% |
| x86-64 |
29,629,040 |
5,751,984 |
19.41% |
Let me remind you that not only do we need to read these relocations at startup (at least the dynamic ones, but the PLT ones are just negligible), but we only read them by chunks, and need to read other data in between.
Of the many existing types of relocations, only a few are actually used in dynamic libraries. Here is a summary of those in use in
libxul.so:
| x86 relocation type |
number |
x86-64 relocation type |
number |
| dynamic relocations |
R_386_TLS_DTPMOD32 |
1 |
R_X86_64_DTPMOD64 |
1 |
R_386_GLOB_DAT |
213 |
R_X86_64_GLOB_DAT |
238 |
R_386_32 |
27,643 |
R_X86_64_64 |
27,611 |
R_386_RELATIVE |
203,979 |
R_X86_64_RELATIVE |
208,043 |
| PLT relocations |
R_386_JUMP_SLOT |
3,772 |
R_X86_64_JUMP_SLOT |
3,773 |
The above types can be separated in two distinct categories:
- Requiring symbols resolution (
R_*_GLOB_DAT, R_*_JUMP_SLOT, R_386_32, R_X86_64_64)
- Not requiring symbols resolution (
R_*_RELATIVE, R_386_TLS_DTPMOD32, R_X86_64_TLS_DTPMOD64)
In the second category, it means we are wasting all the bits for the symbol reference in each entry: 24 on x86 and 32 on x86-64. Unfortunately, the vast majority of the relocations in
libxul.so are from that category. At this point, this is how much waste we identified:
| description |
num. entries |
waste per entry (bytes) |
total |
% of relocation size |
| x86 |
| Relocation without symbol ref. |
203,980 |
3 |
611,937 |
32.46% |
| x86-64 |
| Duplicated addend |
239,666 |
8 |
1,917,328 |
33.33% |
| Relocation type encoded on 32 bits |
239,666 |
3 |
718,998 |
12.49% |
| Relocation without symbol ref. |
208,044 |
4 |
832,176 |
14.46% |
| Total |
3,468,502 |
60.30% |
On top of that, one could argue that we don t need 24 or 32 bits for symbol reference (which is the entry number in the symbol table), and that we re really far from requiring 64 bits for
r_offset on 64 bits systems, as
libxul.so is far from being bigger than 4GB. Anyways, that means we have room for improvement here, and it means that the ELF format, especially on 64 bits systems with RELA relocations, really doesn t help with big programs or libraries with a lot of relocations. (For that matter, the mach-o format used on OS-X has some kind of similar issues ; I don t know for the DLL format)
Another interesting data point is looking at how relocations
r_offset are following each other, once relocations are reordered (to avoid too much symbol resolution, they are actually grouped by symbol). It turns out 206,739 relocations
r_offset are at 4 bytes from the previous one on x86 (i.e. strictly following it), and 210,364 at 8 bytes from the previous on x86-64. The main reason why this happens is that most relocations are happening in pointer tables, and
libxul.so has lots of them:
- That s what you get with virtual methods in C++.
- That s also what you get in
.ctors and .dtors sections, which are relocated as well (but not .init_array and .fini_array sections).
- That s what you get when you use function tables.
- Obvously, that s what you get when you use pointer tables.
And when I say
libxul.so has lots of them, that s not an understatement: there are 184,320 relocations due to vtables (function tables you get when using virtual methods in C++) on x86 and 184,098 on x86-64. That s respectively 78.23% and 76.81% of the total number of relocations. Interestingly, while most of these relocations are
R_*_RELATIVE, 26,853 are
R_386_32, and 26,829 are
R_X86_64_64. Except for a very few, these non relative relocations are for the
__cxa_pure_virtual symbol, which is a dummy function that does nothing, used for pure virtual methods, such as the following:
class Abstract
public:
virtual void pure_virtual() = 0;
;
As for the remaining relative relocations, there are a few pointer tables responsible for several thousand relocations, such as
JSString::length2StringTable,
gEntries,
GkAtoms_info,
Html5Atoms_info,
kUnixCharsets,
nsIDOMCSS2Properties_properties, etc.
Packing relocations
While they are not detrimental to most binaries, we saw that relocations can have a bad effect on startup I/O for big binaries. Reducing how much space they take would have a direct impact on these startup I/Os. One way to do so is obviously to reduce the number of relocations. But as we saw above, the vast majority are due to vtables. While reducing vtables would be a nice goal, it s a long way before this can have a significant impact on the relocations number. So another possible way is to try to avoid wasting so much space in relocations.
The main problem is that relocations are applied by
ld.so, and that, as mentioned in the introduction, while we can hack
ld.so to do what we want, it won t work everywhere before a long time. Moreover, it s difficult to test various implementations, and binary compatibility needs to be guaranteed once something is applied in the upstream libc.
The idea I started to test a few weeks ago, is to effectively apply relocations by hand instead of relying on
ld.so doing it. Considering the first thing
ld.so does with a library after applying relocations is to call its
DT_INIT function, the idea was to replace the dynamic relocations we can with a new
DT_INIT function we would inject that d apply those relocations, while storing them in a more efficient manner. The function would obviously need to call the original
DT_INIT function once done. Some parts of the
PT_DYNAMIC section also obviously need to be adjusted accordingly.
The first iteration I tested a few weeks ago helped validating the idea, but didn t change much of the binary: the dynamic relocation section still was taking all the space it took before, though its content was mostly empty (we ll see further below how efficient even the current dumb format is). Once the theory that an injected
DT_INIT function could apply the relocations without breaking everything, I went on to implement a program that would actually strip the ELF binary. I won t get too much into the gory details, but it required
PT_LOAD splitting, thus program headers growth, which means moving the following sections, then removing a huge part of the relocations, shrinking the relocations section, injecting our code and the packed relocations as sections, and moving the remaining sections after these new sections, to avoid empty space, but still respecting the proper offsets for both
PT_LOAD and the code itself.
So far, I only took care of the
R_*_RELATIVE relocations. Some but not all other relocations could be taken care of, too, but everything involving symbol resolution from other libraries would be really difficult to handle from the injected code. The relocations are currently stored with a quite dumb format:
- a 32 bits word containing
r_offset
- a 32 bits word containing the number of relocations to apply consecutively
As we only take care of one type of relocations, we can skip any information about the type. Also, the addend already being stored at
r_offset, we just strip it from RELA relocations ; the binary being far from 4GB big, 32 bits is enough on 64 bits systems too. We also saw that a lot of relocations were next to the following ones, so instead of storing
r_offset for each one, storing some kind of range is more efficient. As I ve so far been focusing on getting something that actually works more than on getting something really efficient, I only tested this format, but the results are already nice:
|
x86 |
x86-64 |
| before |
| dynamic relocations (bytes) |
1,854,688 |
5,661,432 |
libxul.so size |
21,869,684 |
29,629,040 |
| after |
| dynamic relocations (bytes) |
222,856 |
668,400 |
| injected code size |
129 |
84 |
| packed relative relocations (bytes) |
224,816 |
228,568 |
libxul.so size |
20,464,836 (-6.42%) |
24,865,520 (-16.07%) |
Getting rid of the
__cxa_pure_virtual relocations would help getting this even further down, and an even better storage format could be used, too. Gathering new
startup coverage data should be interesting as well.
The code is
available via mercurial. Please note the
Makefile deeply sucks, and that the code is in the middle of its third refactoring. Anyways, once you get the code to compile, you just need to run
test-x86 or
test-x64 depending on your architecture, from the build directory, and give it the
libxul.so file as an argument. It will create a
libxul.so.new file that you can use to replace
libxul.so. You may successfully use the tool on other libraries, but chances are you ll bump into an
assert(), or in the worst case, that the resulting library ends up broken. The tool might work on PIE executables, but most probably not on other executables. If you wonder, Chrome is not PIE. It s not even relocatable (which means ASLR won t work with it) ; or at least the x86-64 binaries I just got aren t.
More possible ELF hacking
The code I wrote to pack relocations allows to do various tricks on ELF files, and it opens various opportunities, such as:
- Aligning
.bss. As I wrote on this blog a while ago, ld.so fills the last page from the .data section with zeroes, starting at the offset of the .bss section. Unfortunately, this means reading ahead at most 128KB of data nobody needs, and the corresponding disk seek. Inserting a section full of zeroes between .data and .bss would get rid of that, while minimally wasting space (less than 4KB in a 20MB+ binary).
- Trying to move the
PT_DYNAMIC section. It is one of the first bunch of data to be read from programs and libraries, yet it is near the end of the binary.
- Replacing
.ctors/.dtors with .init_array/.fini_array (thus removing the corresponding relocations, though there s only around 300 of them).
- Replacing the
__cxa_pure_virtual relocations with relative relocations pointing to an injected dummy function (it could even just point to any ret code in any existing function).
- Replacing some internal symbol resolutions with relative relocations (which should be equivalent to building with
-Bsymbolic)
- etc.
Some of the above could probably be done with linker scripts, but using linker scripts is unnecessarily over complicated: as soon as you start using a linker script to fiddle with sections, you need to reimplement the entire default linker script (the one you can see with
ld --verbose). And it s not guaranteed to work (Taras told me he had a hard time failing to align the
.bss section). And as far as I know, you can t use the same thing depending whether you use
ld or
gold (AIUI,
gold doesn t support the whole
ld linker script syntax).
I mentioned this briefly yesterday, but now I'll try to summarize the
story of a great surprise and a big moment for me.
All this started when my wife
Elizabeth and my son Jean-Baptiste wanted to do something special for
my 50th birthday. So, it indeed all started months ago, probably early
March or something (I don't yet have all the details).
Jean-Baptiste described this well on the web site, so I won't go again
into details, but basically, this was about getting birthday
wishes from my "free software family" in, as you might guess, as many
languages as possible.
Elizabeth brought the original idea and JB helped her by setting up
the website and collecting e-mail addresses of people I usually work
with: he grabbed addresses from PO files on Debian website, plus some
in his own set of GPG signatures and here we go. And then he started poking
dozens of you folks in order to get your wishes for this birthday.
Gradually, contributions accumulated on the website, with
many challenges for them: be sure to get as many people as possible,
poking and re-poking all those FLOSS people who keep forgetting
things... It seems that poking people is something that's probably in
the Perrier's genes!
And they were doing all this without me noticing.
As usually in Debian, releasing on time is a no-no. So, it quickly
turned out that having everything ready by April 2nd wouldn't be
possible. So, their new goal was offering this to me on Pentecost
Sunday, which was yesterday. And...here comes the gift.
Aha, this looks like a photo album. Could it be a "50 years of
Christian" album?
But, EH, why is that pic of me, with the red Debconf5 tee-shirt (that
features a world map) and a "bubulle" sign, in front of the book?
But, EH EH EH, what the .... are doing these word by H0lger, then Fil,
then Joey doing on the following pages?
And only then, OMG, I discover the real gift they prepared. 106, often
bilingual, wishes from 110 people (some were couples!). 18 postcards
(one made of wood). 45 languages. One postcard with wishes from nearly every distro
representatives at LinuxTag 2011. Dozens of photos from my friends all
around the world. All this in a wonderful album.
I can't tell what I said. Anyway, JB was shooting a video, so...we'll see. OK, I didn't cry...but it wasn't that far and
emotion was really really intense.
Guys, ladies, gentlemen, friends....it took me a while to realize what
you contributed to. It took me the entire afternoon to realize the
investment put by Elizabeth and JB (and JB's sisters support) into
this. Yes, as many of you wrote, I have an awesome family and they
really know how to share their love. I also have an awesome virtual
family all around the world. Your words are wholeheartedly appreciated
and some were indeed much much much appreciated.
Of course, I'll have the book in Banja Luka so that you can see the
result. I know (because JB and Elizabeth told me) that many of you
were really awaiting to see how it would be received (yes, that
includes you, in Germany, who I visited in early May!!!).
Again, thank you so much for this incredible gift. Thank you Holger Levsen, Phil Hands, Joey Hess, Lior Kaplan, Martin
Michlmayr, Alberto Gonzalez Iniesta, Kenshi "best friend" Muto,
Praveen Arimbrathodiyil, Felipe Augusto van de Wiel, Ana Carolina
Comandulli (5 postcards!), Stefano Zacchiroli (1st contribution
received by JB, of course), Gunnar Wolf, Enriiiiiico Zini, Clytie Siddall,
Frans Pop (by way of Clytie), Tenzin Dendup, Otavio Salvador, Neil
McGovern, Konstantinos Margaritis, Luk Claes, Jonas Smedegaard, Pema
Geyleg, Meike "sp tzle queen" Reichle, Alexander Reichle-Schmehl,
Torsten Werner, "nette BSD" folks, CentOS Ralph and
Brian, Fedora people, SUSE's Jan, Ubuntu's Lucia Tamara, Skolelinux'
Paul, Rapha l Hertzog, Lars Wirzenius, Andrew McMillan (revenge in
September!), Yasa Giridhar Appaji Nag (now I know my name in Telugu),
Amaya Rodrigo, St phane Glondu, Martin Krafft, Jon "maddog" Hall (and
God save the queen), Eddy Petri or, Daniel Nylander, Aiet Kolkhi,
Andreas "die Katze geht in die K che, wunderbar" Tille, Paul "lets
bend the elbow" Wise, Jordi "half-marathon in Banja Luka" Mallach,
Steve "as ever-young as I am" Langasek, Obey Arthur Liu, YAMANE
Hideki, Jaldhar H. Vyas, Vikram Vincent, Margarita "Bronx
cross-country queen" Manterola, Patty Langasek, Aigars Mahinovs
(finding a pic *with* you on it is tricky!), Thepittak
Karoonboonyanan, Javier "nobody expects the Spanish inquisition"
Fern ndez-Sanguino, Varun Hiremath, Moray Allan, David Moreno Garza,
Ralf "marathon-man" Treinen, Arief S Fitrianto, Penny Leach, Adam
D. Barrat, Wolfgang Martin Borgert, Christine "the mentee overtakes
the mentor" Spang, Arjuna Rao Chevala, Gerfried "my best contradictor"
Fuchs, Stefano Canepa, Samuel Thibault, Eloy "first samba maintainer"
Par s, Josip Rodin, Daniel Kahn Gillmor, Steve McIntyre, Guntupalli
Karunakar, Jano Gulja , Karolina Kali , Ben Hutchings, Matej Kova i ,
Khoem Sokhem, Lisandro "I have the longest name in this list" Dami n
Nicanor P rez-Meyer, Amanpreet Singh Alam, H ctor Or n, Hans
Nordhaugn, Ivan Mas r, Dr. Tirumurti Vasudevan, John "yes, Kansas is
as flat as you can imagine" Goerzen, Jean-Baptiste "Piwet" Perrier,
Elizabeth "I love you" Perrier, Peter Eisentraut, Jesus "enemy by
nature" Climent, Peter Palfrader, Vasudev Kamath, Miroslav "Chicky"
Ku e, Mart n Ferrari, Ollivier Robert, Jure uhalev, Yunqiang Su,
Jonathan McDowell, Sampada Nakhare, Nayan Nakhare, Dirk "rendez-vous
for Chicago marathon" Eddelbuettel, Elian Myftiu, Tim Retout, Giuseppe
Sacco, Changwoo Ryu, Pedro Ribeoro, Miguel "oh no, not him again" Figueiredo, Ana Guerrero,
Aur lien Jarno, Kumar Appaiah, Arangel Angov, Faidon Liambotis, Mehdi
Dogguy, Andrew Lee, Russ Allbery, Bj rn Steensrud, Mathieu Parent,
Davide Viti, Steinar H. Gunderson, Kurt Gramlich, Vanja Cvelbar, Adam
Conrad, Armi Be irovi , Nattie Mayer-Hutchings, Joerg "dis shuld be
REJECTed" Jaspert and Luca Capello.
Let's say it gain:
The 
Last night I wanted to buy 
I guess it won't be very many people reading this blog to know the name, even though he was without any doubt one of the biggest entertainers. Lots of movies, his own TV show, and an enormous amount of albums made him well known far outside the borders of Austria, his home country. Last saturday he died in the age of 84, yesterday was his funeral. This is a special dedication to him. 
This object from the old 6bone whois database is the earliest trace I could find of my IPv6-related activities:
Sometimes, 
During DebConf, I managed to squeeze out of the middle of everything for long enough to write a column, a short article for a participation I have every three months, for Mexican 
Sadly, I cannot find this book in English, as it is very well worth a read. But if the topic sounds interesting and you can understand the language, don't hesitate and pick up the book. It gives an interesting insight on the topic, for a group of people (us techies) used to looking at things in a much more human-cognitive-process-oriented way.
[update] I found this nice 