Archive for February, 2012

By now, most tech sites have talked about Boot to Gecko, following MWC announcement and demos, and how it's based on standards from the open web to build the entire user interface.

One thing I would like to stress is that more than being tied to the open web, Boot to Gecko is also open source at its core. If you want to build Boot to Gecko today and use it on your phone, you can. Sure, you may have some difficulties if your phone is not a Galaxy S2, but I'm pretty sure the community at large (XDA and others) will soon have a solution for a lot of other phones or if you are skilled enough, you can do it yourself. And that is the great strength of Boot to Gecko's open source nature.

And that strength is also a major difference with Android. Android is open source, but it also is developed behind closed doors. Boot to Gecko code has been available on github for months. Android 5.0 Jelly Bean, which is expected for the end of the year, has been in development at Google for months too. Want to test it? Want to see the source code? Want to participate? Well, you'll have to wait for it to be shipped on an actual phone, since Google doesn't release the source code until then.

Consider the following foo.c source file:

extern int bar() __attribute__((weak));
int foo() {
  return bar();
}

And the following bar.c source file:

int bar() {
  return 42;
}

Compile both sources:

$ gcc -o foo.o -c foo.c -fPIC
$ gcc -o bar.o -c bar.c -fPIC

In the resulting object for foo.c, we have an undefined symbol reference to bar. That symbol is marked weak.

In the resulting object for bar.c, the bar symbol is defined and not weak.

What we expect from linking both objects is that the weak reference is fulfilled by the existence of the bar symbol in the second object, and that in the resulting binary, the foo function calls bar.

$ ld -shared -o test1.so foo.o bar.o

And indeed, this is what happens.

$ objdump -T test1.so | grep "\(foo\|bar\)"
0000000000000260 g    DF .text  0000000000000007 foo
0000000000000270 g    DF .text  0000000000000006 bar

What do you think happens if the bar.o object file is embedded in a static library?

$ ar cr libbar.a bar.o
$ ld -shared -o test2.so foo.o libbar.a
$ objdump -T test2.so | grep "\(foo\|bar\)"
0000000000000260 g    DF .text  0000000000000007 foo
0000000000000000  w   D  *UND*  0000000000000000 bar

The bar function is now undefined and there is a weak reference for the symbol. Calling foo will crash at runtime.

This is apparently a feature of the linker. If anyone knows why, I would be interested to hear about it. Good to know, though.

Here are the few noteworthy news about Mozilla packages in Debian:

• Iceape 2.7 made its way to unstable. This is a huge jump from the previously available 2.0.14, and finally happened because Iceape was finally the top item on my TODO list.
• Iceape 2.7 is also available for Squeeze users, on the Debian Mozilla team APT archive.
• Localization is now part of Iceweasel uploads, which means that upgrades won't break localization anymore. It also means the Debian Mozilla team APT archive now also ships Iceweasel locales.

const char *foo = "foo";

This was recently mentioned on bugzilla, and the problem is usually underestimated, so I thought I would give some details about what is wrong with the code above.

The first common mistake here is to believe foo is a constant. It is a pointer to a constant. In practical ELF terms, this means the pointer lives in the .data section, and the string constant in .rodata. The following code defines a constant pointer to a constant:

const char * const foo = "foo";

The above code will put both the pointer and the string constant in .rodata. But keeping a constant pointer to a constant string is pointless. In the above examples, the string itself is 4 bytes (3 characters and a zero termination). On 32-bits architectures, a pointer is 4 bytes, so storing the pointer and the string takes 8 bytes. A 100% overhead. On 64-bits architectures, a pointer is 8 bytes, putting the total weight at 12 bytes, a 200% overhead.

The overhead is always the same size, though, so the longer the string, the smaller the overhead, relatively to the string size.

But there is another, not well known, hidden overhead: relocations. When loading a library in memory, its base address varies depending on how many other libraries were loaded beforehand, or depending on the use of address space layout randomization (ASLR). This also applies to programs built as position independent executables (PIE). For pointers embedded in the library or program image to point to the appropriate place, they need to be adjusted to the base address where the program or library is loaded. This process is called relocation.

The relocation process requires information which is stored in .rel.* or .rela.* ELF sections. Each pointer needs one relocation. The relocation overhead varies depending on the relocation type and the architecture. REL relocations use 2 words, and RELA relocations use 3 words, where a word is 4 bytes on 32-bits architectures and 8 bytes on 64-bits architectures.

On x86 and ARM, to mention the most popular 32-bits architectures nowadays, REL relocations are used, which makes a relocation weigh 8 bytes. This puts the pointer overhead for our example string to 12 bytes, or 300% of the string size.

On x86-64, RELA relocations are used, making a relocation weigh 24 bytes! This puts the pointer overhead for our example string to 32 bytes, or 800% of the string size!

Another hidden cost of using a pointer to a constant is that every time it is used in the code, there will be pointer dereference. A function as simple as

int bar() { return foo; }

weighs one instruction more when foo is defined const char *. On x86, that instruction weighs 2 bytes. On x86-64, 3 bytes. On ARM, 4 bytes (or 2 in Thumb). That weight can vary depending on the additional instructions required, but you get the idea: using a pointer to a constant also adds overhead to the code, both in time and space. Also, if the string is defined as a constant instead of being used as a literal in the code, chances are it's used several times, multiplying the number of such instructions. Update: Note that in the case of const char * const, the compiler will optimize these instruction and avoid reading the pointer, since it's never going to change.

The symbol for foo is also exported, making it available from other libraries or programs, which might not be required, but also adds its own overhead: an entry in the symbols table (5 words), an entry in the string table for the symbol name (strlen("foo") + 1) and an entry in the symbols hash chain table (4 bytes if only one type of hash table (sysv or GNU) is present, 8 if both are present), and possibly an entry in the symbols hash bucket table, depending on the other exported symbols (4 or 8 bytes, as chain table). It can also affect the size of the bloom filter table in the GNU symbol hash table.

So here we are, with a seemingly tiny 3 character string possibly taking 64 bytes or more! Now imagine what happens when you have an array of such tiny strings. This also doesn't only apply to strings, it applies to any kind of global pointer to constants.

In conclusion, using a definition like

const char *foo = "foo";

is almost never what you want. Instead, you want to use one of the following forms:

• For a string meant to be exported:
  

  const char foo[] = "foo";

• For a string meant to be used in the same source file:
  

  static const char foo[] = "foo";

• For a string meant to be used across several source files for the same library:
  

  __attribute__((visibility("hidden"))) const char foo[] = "foo";