dcsimg

Building the Perfect Executable

Your program has compiled with no errors. You type its name and watch it run. It seems so simple, but there's a lot that had to happen behind the scenes at the time the program was compiled in order to make it look so easy. For one thing, in order to make it possible for the kernel to properly load and execute your program, the compiler toolchain has to know exactly how the kernel will expect the new process's virtual address space to look. In other words, the toolchain has to be able to build the executable according to specifications that the kernel understands and expects.

Your program has compiled with no errors. You type its name and watch it run. It seems so simple, but there’s a lot that had to happen behind the scenes at the time the program was compiled in order to make it look so easy. For one thing, in order to make it possible for the kernel to properly load and execute your program, the compiler toolchain has to know exactly how the kernel will expect the new process’s virtual address space to look. In other words, the toolchain has to be able to build the executable according to specifications that the kernel understands and expects.

The part of the toolchain that makes sure that your program meets the kernel’s expectations is the linker, ld. Actually, the linker performs several functions that are crucial to the process of building a working executable, and so it’s worth taking a deeper look at this little-known portion of the compiler toolchain.

What the Linker Does

Any time you run an executable, the kernel must create a new virtual address space for the process to run in and then load (or copy) the executable into that newly created space. We briefly looked into this topic in the July 2001 issue (available on the Web at http://www.linux-mag.com/2001-07/compile_01.html).

As we discussed in that column, each process is given its own virtual address space, which is partitioned into identical large sections (as depicted in Figure One). The kernel expects that the start of these large sections of a process will always be located at the same virtual address.








Figure 1
Figure One: A process’s virtual address space.

In order for that to be possible, every program must be set up according to the specifications that the kernel expects at the time that it’s compiled, and that’s one of the linker’s jobs. The linker and the kernel share an understanding of how the virtual address space should be laid out, and the linker knows how to put all the pieces of a program that you’re compiling into the proper sections of the virtual address space. It also adjusts things so that all of the different addresses that are used by the program point where they should. (We’ll talk more about this in minute.)

One section of the virtual address space contains the actual machine code instructions that make up the program — the section labeled “Other Program Data,” which contains the code (or text) segment. Let’s see how the linker builds this part of the executable.

Object Files

As we discussed in last month’s column, after the compiler (gcc) and the assembler (as) finish their respective jobs, they hand off a set of relocatable object modules to the linker, which must then make a functioning executable out of them.

You might be wondering what “relocatable” means in this particular context. In this case, it doesn’t mean “may be relocated,” but rather “must be relocated.” The linker builds the code segment by placing the code from each object module — one after another — in the code segment portion of the virtual address space as though it were placing different sized books in a bookshelf.

When the assembler builds each object module, there’s absolutely no way that it can know exactly where that module will reside in the virtual address space, so it doesn’t bother to try to figure it out. Instead, it lets the linker adjust the addresses in every module. This adjustment process is known as “relocation” (and this is where the term “relocatable object module” comes from).

Disassembling Object Files

In order to appreciate what the linker has to do in order to make all of this work, let’s take a closer look at an object file and see just what it contains. Since they contain assembly code that’s been run through the assembler, we can “disassemble” the object file in order to recover the original assembly code.

Figure Two contains listings of a short program contained in three files: a.c, b.c, and main.c. Once they’ve been compiled into the object modules a.o, b.o, and main.o, we can run the command objdump -d on each of them in order to see what their assembly code looks like. These are listed in Figure Three (the output has been slightly edited for space reasons).




Figure Two: Code for a.c, b.c, and main.c


a.c b.c main.c

int a () { int b () { int main () {
int i = 0; a(); a ();
i++; } b ();
foo: }
i–;
goto foo;
}




Figure Three: Disassembly for a.o, b.o, and main.o


a.o: file format elf32-i386
00000000 <a>:
0: push %ebp
1: mov %esp,%ebp
3: sub $0×4,%esp
6: movl $0×0,0xfffffffc(%ebp)
d: lea 0xfffffffc(%ebp),%eax
10: incl (%eax)
12: lea 0xfffffffc(%ebp),%eax
15: decl (%eax)
17: jmp 12 <a+0×12>

b.o: file format elf32-i386
00000000 <b>:
0: push %ebp
1: mov %esp,%ebp
3: sub $0×8,%esp
6: call 7 <b+0×7>
b: mov %ebp,%esp
d: pop %ebp
e: ret

main.o: file format elf32-i386
00000000 <main>:
0: push %ebp
1: mov %esp,%ebp
3: sub $0×8,%esp
6: call 7 <main+0×7>
b: call c <main+0xc>
10: mov %ebp,%esp
12: pop %ebp
13: ret

In each listing, the first column starts at 0 and increases. This is the location (or address) of the assembly language instruction which is listed in the subsequent columns. The assembler always starts building an object module at address 0. The linker must relocate all of these instructions to their new virtual addresses.

There are two other areas of importance in the address to the linker: the jumps (or branches) made by the code, and calls to functions.

Relative Jumps

In the assembly code for a.o, notice that the instruction at address 17 reads “jmp 12 <a+0×12>” (and corresponds to the goto in a.c). That means that the program should jump to the instruction at address 12 (which is “lea 0x fffffffc(%ebp),%eax“).

However, the destination address 12 was specified as being relative to the start of the a() function. That’s what the “<a+0×12>” means: jump to the instruction that’s 12 bytes after the start of the a() function. This means that no matter where the a() function is placed in the virtual address space, the jump always knows where to go. This is called a relative jump, and nearly every compiler creates code that uses them.

The use of relative jumps is one characteristic of what’s known as “position-independent code” (PIC). In addition to being relocatable, modules compiled in PIC mode can be turned into shared libraries, which can also be used simultaneously by multiple processes, reducing the memory use of the entire system. We’ll talk more about shared libraries in next month’s column.

Because the compiler generated the relative jump, the linker only needs to relocate the jump instruction to its new place in the virtual address space. The actual instruction itself doesn’t need to be changed. However, the linker does need to change an instruction whenever functions are being called.

Calling Functions in Other Modules

Let’s look at disassembly for b.o, specifically the instruction at address 6: “call 7 <b+0×7>“. This means we should call a function. However, it looks like the call is to a function at address 7, which is right in the middle of an instruction. What’s going on here?

It turns out that 7 is not an actual address, but rather an offset or index into a table. As b.c is compiled, a table of functions that are called from within b.c is created. This table contains “relocation records” and can be listed by running “objdump -x” on b.o.

The relocation records for b.o and main.o are shown in Figure Four (note that they have been slightly edited for space reasons). You can see that the value for the offset of 7 is “a“, which corresponds to the call to the function a() in b.c.




Figure Four: Relocation Records for b.o and main.o


b.o:
RELOCATION RECORDS FOR [.text]:
OFFSET VALUE
00000007 a

main.o:
RELOCATION RECORDS FOR [.text]:
OFFSET VALUE
00000007 a
0000000c b

When the linker processes b.o, it takes a look at the relocation records and sees if the function a() is present in any of the other object modules (or system libraries). If the relocation record were not found, an “unsatisfied reference” error would be generated.

However, since the function a() does exist (in a.o), the call instruction is then rewritten — or patched — in order to be able to use the virtual address of the a() function within a.o.

You can examine for yourself the two call instructions in main.o and how that generates two relocation records (to the functions a() and b()).

The Finished Product

Let’s take a look at what the three modules look like once the linker has finished its task. Figure Five contains a dump of the final executable (obtained by running “objdump -d” on the executable).




Figure Five: How a(), b(), and main() Appear in the Final Executable


08048430 <a>:
8048430: push %ebp
8048431: mov %esp,%ebp
8048433: sub $0×4,%esp
8048436: movl $0×0,0xfffffffc(%ebp)
804843d: lea 0xfffffffc(%ebp),%eax
8048440: incl (%eax)
8048442: lea 0xfffffffc(%ebp),%eax
8048445: decl (%eax)
8048447: jmp 8048442 <a+0×12>

08048450 <b>:
8048450: push %ebp
8048451: mov %esp,%ebp
8048453: sub $0×8,%esp
8048456: call 8048430 <a>
804845b: mov %ebp,%esp
804845d: pop %ebp

08048460 <main>:
8048460: push %ebp
8048461: mov %esp,%ebp
8048463: sub $0×8,%esp
8048466: call 8048430 <a>
804846b: call 8048450 <b>
8048470: mov %ebp,%esp
8048472: pop %ebp

One thing to notice is that the jmp instruction at 0x 8048447 in the a() function is the same as it was in the a.o file. Although the “12″ has been replaced in the output with the correct virtual address, it’s still really “<a+0×12>“. The call instructions to a() and b() have also had the correct addresses inserted.

So Much Work, So Well Hidden From You

We’ve only covered a small (though rather significant) portion of what the linker does to build an executable. Hopefully, you will now have a better understanding of how the linker places each module in the virtual address space and then adjusts addresses to make sure that everything works correctly.

But that’s not all the linker does. In coming columns, we’ll talk about how the linker can build shared libraries and how the linker gets the kernel to start your program at the main() function.

In the meantime, happy hacking!



Benjamin Chelf is an author and engineer at CodeSourcery, LCC. He can be reached at chelf@codesourcery.com.

Fatal error: Call to undefined function aa_author_bios() in /opt/apache/dms/b2b/linux-mag.com/site/www/htdocs/wp-content/themes/linuxmag/single.php on line 62