(this post was going to be about something else, but after getting
this far, I think it stands on its own as an introduction to dynamic
linking)
The shared library is an integral part of a modern system, but
often the mechanisms behind the implementation are less well
understood. There are, of course, many guides to this sort of thing.
Hopefully this adds another perspective that resonates with
someone.
Let's start at the beginning - relocations are
entries in binaries that are left to be filled in later -- at link
time by the toolchain linker or at runtime by the dynamic linker. A
relocation in a binary is a descriptor which essentially says
"determine the value of X, and put that value into the binary at
offset Y" each relocation has a specific type, defined
in the ABI documentation, which describes exactly how "determine the
value of" is actually determined.
Here's the simplest example:
$ cat a.c
extern int foo;
int function(void)
return foo;
$ gcc -c a.c
$ readelf --relocs ./a.o
Relocation section '.rel.text' at offset 0x2dc contains 1 entries:
Offset Info Type Sym.Value Sym. Name
00000004 00000801 R_386_32 00000000 foo
The value of
foo is not known at the time you make
a.o, so the compiler leaves behind a relocation (of
type
R_386_32) which is saying "in the final binary, patch
the value at offset 0x4 in this object file with the address of symbol
foo". If you take a look at the output, you can see at
offset 0x4 there are 4-bytes of zeros just waiting for a real
address:
$ objdump --disassemble ./a.o
./a.o: file format elf32-i386
Disassembly of section .text:
00000000 <function>:
0: 55 push %ebp
1: 89 e5 mov %esp,%ebp
3: a1 00 00 00 00 mov 0x0,%eax
8: 5d pop %ebp
9: c3 ret
That's link time; if you build another object file with a value of
foo and build that into a final executable, the relocation can go
away. But there is a whole bunch of stuff for a fully linked
executable or shared-library that just can't be resolved until
runtime. The major reason, as I shall try to explain, is
position-independent code (PIC). When you look at an
executable file, you'll notice it has a fixed load address
$ readelf --headers /bin/ls
[...]
ELF Header:
[...]
Entry point address: 0x8049bb0
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
[...]
LOAD 0x000000 0x08048000 0x08048000 0x16f88 0x16f88 R E 0x1000
LOAD 0x016f88 0x0805ff88 0x0805ff88 0x01543 0x01543 RW 0x1000
This is not position-independent. The code section (with
permissions
R E; i.e. read and execute) must be loaded at
virtual address
0x08048000, and the data section
(
RW) must be loaded above that at exactly
0x0805ff88.
This is fine for an executable, because each time you start a new
process (
fork and
exec) you have your own fresh
address space. Thus it is a considerable time saving to pre-calculate
addresses from and have them fixed in the final output (you can make
position-independent executables, but that's another story).
This is not fine for a shared library (
.so). The whole
point of a shared library is that applications pick-and-choose random
permutations of libraries to achieve what they want. If your shared
library is built to only work when loaded at one particular address
everything may be fine until another library comes along that
was built also using that address. The problem is actually somewhat
tractable you can just enumerate every single shared library
on the system and assign them all unique address ranges, ensuring that
whatever combinations of library are loaded they never overlap. This
is essentially what prelinking does (although that is a hint,
rather than a fixed, required address base). Apart from being a
maintenance nightmare, with 32-bit systems you rapidly start to run
out of address-space if you try to give every possible library a
unique location. Thus when you examine a shared library, they do not
specify a particular base address to be loaded at:
$ readelf --headers /lib/libc.so.6
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
[...]
LOAD 0x000000 0x00000000 0x00000000 0x236ac 0x236ac R E 0x1000
LOAD 0x023edc 0x00024edc 0x00024edc 0x0015c 0x001a4 RW 0x1000
Shared libraries also have a second goal code sharing. If
a hundred processes use a shared library, it makes no sense to have
100 copies of the code in memory taking up space. If the code is
completely read-only, and hence never, ever, modified, then every
process can share the same code. However, we have the constraint that
the shared library must still have a unqiue data instance in each
process. While it would be possible to put the library data anywhere
we want at runtime, this would require leaving behind relocations to
patch the code and inform it where to actually find the data
destroying the always read-only property of the code and thus
sharability. As you can see from the above headers, the solution is
that the read-write data section is always put at a known offset from
the code section of the library. This way, via the magic of
virtual-memory, every process sees its own data section but can share
the unmodified code. All that is needed to access data is some simple
maths; address of thing I want = my current address + known fixed
offset.
Well, simple maths is all relative! "My current address" may or
may not be easy to find. Consider the following:
$ cat test.c
static int foo = 100;
int function(void)
return foo;
$ gcc -fPIC -shared -o libtest.so test.c
So
foo will be in data, at a fixed offset from the code in
function, and all we need to do is find it! On amd64, this
is quite easy, check the disassembly:
000000000000056c <function>:
56c: 55 push %rbp
56d: 48 89 e5 mov %rsp,%rbp
570: 8b 05 b2 02 20 00 mov 0x2002b2(%rip),%eax # 200828 <foo>
576: 5d pop %rbp
This says "put the value at offset 0x2002b2 from the current
instruction pointer (
%rip) into
%eax. That's it
we know the data is at that fixed offset so we're done. i386,
on the other hand, doesn't have the ability to offset from the current
instruction pointer. Some trickery is required there:
0000040c <function>:
40c: 55 push %ebp
40d: 89 e5 mov %esp,%ebp
40f: e8 0e 00 00 00 call 422 <__i686.get_pc_thunk.cx>
414: 81 c1 5c 11 00 00 add $0x115c,%ecx
41a: 8b 81 18 00 00 00 mov 0x18(%ecx),%eax
420: 5d pop %ebp
421: c3 ret
00000422 <__i686.get_pc_thunk.cx>:
422: 8b 0c 24 mov (%esp),%ecx
425: c3 ret
The magic here is
__i686.get_pc_thunk.cx. The
architecture does not let us get the current instruction address, but
we can get a known fixed address the value
__i686.get_pc_thunk.cx pushes into
cx is the return
value from the
call, i.e in this case
0x414. Then
we can do the maths for the
add instruction;
0x115c +
0x414 = 0x1570, the final move goes
0x18 bytes past that
to
0x1588 ... checking the disassembly
00001588 <global>:
1588: 64 00 00 add %al,%fs:(%eax)
i.e., the value 100 in decimal, stored in the data section.
We are getting closer, but there are still some issues to deal
with. If a shared library can be loaded at any address, then how does
an executable, or other shared library, know how to access data or
call functions in it? We could, theoretically, load the library and
patch up any data references or calls into that library; however as
just described this would destroy code-sharability. As we know, all
problems can be solved with a layer of indirection, in this case
called global offset table or GOT.
Consider the following library:
$ cat test.c
extern int foo;
int function(void)
return foo;
$ gcc -shared -fPIC -o libtest.so test.c
Note this looks exactly like before, but in this case the foo is
extern; presumably provided by some other library. Let's
take a closer look at how this works, on amd64:
$ objdump --disassemble libtest.so
[...]
00000000000005ac <function>:
5ac: 55 push %rbp
5ad: 48 89 e5 mov %rsp,%rbp
5b0: 48 8b 05 71 02 20 00 mov 0x200271(%rip),%rax # 200828 <_DYNAMIC+0x1a0>
5b7: 8b 00 mov (%rax),%eax
5b9: 5d pop %rbp
5ba: c3 retq
$ readelf --sections libtest.so
Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
[...]
[20] .got PROGBITS 0000000000200818 00000818
0000000000000020 0000000000000008 WA 0 0 8
$ readelf --relocs libtest.so
Relocation section '.rela.dyn' at offset 0x418 contains 5 entries:
Offset Info Type Sym. Value Sym. Name + Addend
[...]
000000200828 000400000006 R_X86_64_GLOB_DAT 0000000000000000 foo + 0
The disassembly shows that the value to be returned is loaded from
an offset of
0x200271 from the current
%rip;
i.e.
0x0200828. Looking at the section headers, we see that
this is part of the
.got section. When we examine the
relocations, we see a
R_X86_64_GLOB_DAT relocation that says
"find the value of symbol
foo and put it into address
0x200828.
So, when this library is loaded, the dynamic loader will examine
the relocation, go and find the value of
foo and patch the
.got entry as required. When it comes time for the code
loads to load that value, it will point to the right place and
everything just works; without having to modify any code values and
thus destroy code sharability.
This handles data, but what about function calls? The indirection
used here is called a procedure linkage table or PLT. Code
does not call an external function directly, but only via a PLT
stub. Let's examine this:
$ cat test.c
int foo(void);
int function(void)
return foo();
$ gcc -shared -fPIC -o libtest.so test.c
$ objdump --disassemble libtest.so
[...]
00000000000005bc <function>:
5bc: 55 push %rbp
5bd: 48 89 e5 mov %rsp,%rbp
5c0: e8 0b ff ff ff callq 4d0 <foo@plt>
5c5: 5d pop %rbp
$ objdump --disassemble-all libtest.so
00000000000004d0 <foo@plt>:
4d0: ff 25 82 03 20 00 jmpq *0x200382(%rip) # 200858 <_GLOBAL_OFFSET_TABLE_+0x18>
4d6: 68 00 00 00 00 pushq $0x0
4db: e9 e0 ff ff ff jmpq 4c0 <_init+0x18>
$ readelf --relocs libtest.so
Relocation section '.rela.plt' at offset 0x478 contains 2 entries:
Offset Info Type Sym. Value Sym. Name + Addend
000000200858 000400000007 R_X86_64_JUMP_SLO 0000000000000000 foo + 0
So, we see that function makes a call to code at
0x4d0.
Disassembling this, we see an interesting call, we jump to the value
stored in
0x200382 past the current
%rip
(i.e.
0x200858), which we can then see the relocation for
the symbol
foo.
It is interesting to keep following this through; let's look at the
initial value that is jumped to:
$ objdump --disassemble-all libtest.so
Disassembly of section .got.plt:
0000000000200840 <.got.plt>:
200840: 98 cwtl
200841: 06 (bad)
200842: 20 00 and %al,(%rax)
...
200858: d6 (bad)
200859: 04 00 add $0x0,%al
20085b: 00 00 add %al,(%rax)
20085d: 00 00 add %al,(%rax)
20085f: 00 e6 add %ah,%dh
200861: 04 00 add $0x0,%al
200863: 00 00 add %al,(%rax)
200865: 00 00 add %al,(%rax)
...
Unscrambling
0x200858 we see its initial value is
0x4d6 i.e. the next instruction! Which then pushes
the value
0 and jumps to
0x4c0. Looking at that
code we can see it pushes a value from the GOT, and then jumps to a
second value in the GOT:
00000000000004c0 <foo@plt-0x10>:
4c0: ff 35 82 03 20 00 pushq 0x200382(%rip) # 200848 <_GLOBAL_OFFSET_TABLE_+0x8>
4c6: ff 25 84 03 20 00 jmpq *0x200384(%rip) # 200850 <_GLOBAL_OFFSET_TABLE_+0x10>
4cc: 0f 1f 40 00 nopl 0x0(%rax)
What's going on here? What's actually happening is lazy
binding by convention when the dynamic linker loads a
library, it will put an identifier and resolution function into known
places in the GOT. Therefore, what happens is roughly this: on the
first call of a function, it falls through to call the default stub,
which loads the identifier and calls into the dynamic linker, which at
that point has enough information to figure out "hey, this
libtest.so is trying to find the function
foo". It
will go ahead and find it, and then patch the address into the GOT
such that the next time the original PLT entry is called, it
will load the actual address of the function, rather than the lookup
stub. Ingenious!
Out of this indirection falls another handy thing the
ability to modify the symbol binding order.
LD_PRELOAD, for
example, simply tells the dynamic loader it should insert a library as
first to be looked-up for symbols; therefore when the above binding
happens if the preloaded library declares a
foo, it will be
chosen over any other one provided.
In summary code should be read-only always, and to make it
so that you can still access data from other libraries and call
external functions these accesses are indirected through a GOT and PLT
which live at compile-time known offsets.
In a future post I'll discuss some of the security issues around
this implementation, but that post won't make sense unless I can refer
back to this one :)
This week saw again some progress for samba packages. May is indeed my
samba month..:-).
So, I uploaded samba 3.5.8~dfsg-3 and -4. For whatever reason, -3 was
rejected three times and, as I already tagged it in our SVN then
started adding changes for an upcoming -4, I finally uploaded that -4.
It fixed about 10 more bugs and the bug count is now 62.
Upstream also release 3.6.0-rc1, which I uploaded in experimental and
which fixed an RC bug.
I also began working on Pootle 2.1.6 as an attempt to resync with
upstream. I integrated patches by Alaa Abd El Fattah to have it use
dbconfig-common to setup a database. However, this revealed that more
invasive work is needed to satisfy dependencies...that may depend on
the database backend chosen by users. As I'm quite ignorant with these
things, I might need some help, here.
I uploaded a new release of xgridfit to fix an important bug and avoid
an NMU. xgridfit is team-maintained in pkg-fonts. I'm not very active
in this team ATM. I shoul dresume work for it as I proposed a talk
about it at Debconf11..:-)
I continued hard work on French DDTP. Martijn made changes to stats
pages and it makes interesting challenges to complete. You know I like
challenges..
Smith reviews continue to go on: I launched a call for translations
for slapos.tool.format and started the review of ntfs-3g.
Finally, on Saturday....I upgraded churro (aka i18n.debian.net) to
squeeze. Really. All alone..:-)...on a server that lies in
Spain. "Meme pas peur" (not even scared) as we say in French. I'm
really highly confident in squeeze upgrades now....and I was
right. After only 5 hours work (mostly looking at packages downloads
and configuration), nearly everything was back to work. As of now, we
got three glitches, with only one bignot yet fixed:
The 
long time no post about my RC bug fixing activities. & indeed, I haven't
been very active during the last weeks. here's a quick update; it includes
two NMUs done for the perl 5.12 transition, the rest is just
"normal" maintainance work (interesting to see how much stuff can
break behind our backs ...).
This has been several months since I didn t use much my laptop, an
Asus 
Here is the configuration that I bought:
Most probably haven't noticed yet but I finished the 
There is a reason it's called experimental isn't there?
In 
I recently set up debian on a 
For the past couple years I had been reading very little, two or three books a year.
Although I promised in my previous entry that I'd made my last mention of the 
This appears to be kind of useful:
Continuing my series about my 
Google provides a handy 
There are many ways to run some commands simultaneously on multiple
hosts like 
In Ubuntu, the use of