Written on 2012-09-10
This note is part of an effort to understand how a PC works. What
happens from the writing of code until the actual physical comptation
of inside the CPU? In particular:
- How does a computer compute? Physical Layout of a CPU, Registers, Boolean Logic.
- How does a computer execute a program?
- What operations are atomic, i.e. hard wired inside the CPU and completed in one cycle?
- How does a computer store data? (RAM or HDD)
Here we follow a simple approach. We write a little program and see how far we can dissect it.
Hello World
We start with a tiny little program which we choose to write in
C, because
people claim it is nearest to the actual processor logic. We call it
“simple.c”:
main(){
int a,b,c;
a=5;
b=8;
c = a+b;
}
We compile this program on a Linux box with the command
and get out an executable file a.out. This file is actually quiet long
it already has 8446 bytes. Lets look inside:
We see that the file starts like that:
00000000 7F 45 4C 46 02 01 01 00 00 00 00 00 00 00 00 00 .ELF............
00000010 02 00 3E 00 01 00 00 00 E0 03 40 00 00 00 00 00 ..>.......@.....
00000020 40 00 00 00 00 00 00 00 60 11 00 00 00 00 00 00 @.......`.......
and goes on and on for quiet a while. The output has the following structure:
- In the middle we see the content of the file in a hexadecimal encoding grouped into bytes:
For example 7F stands for the bit string: 0111 1111.
- The very left colum is a byte counter in a hexadecimal format.
So the 00000010 in the second line means we are starting with byte 16.
- On the right we have a translation of the code into ASCII symbols.
What does ELF mean? A quick search on
wikipedia reveals, that there is a UNIX file format called
Executable and Linkable Format which has this very
abreviation. A call of file a.out reassures that this wilde guess
might be correct.
The ELF File format
The best reference on ELF files on the net I could find is the
John R. Levine - Linkers and Loaders. Our
treatment is similar to
LinuxForums.org - ELF using readelf and objdump.
ELF is a container format for executable files suitable for the Linux operating system.
Before a program can run on the CPU a loader or
dynamic linker program (in our case ld.so) of the OS is called which servers the following tasks:
- Find and load shared libraries
- Load program code and data into the memory
- Translate adresses used inside the program to physical addresses inside the reserved memory block (Relocation
- Puts passed commandline arguments onto the stack
- Setup registers (e.g. stack pointer)
- Jumps to the entry point of the program
Examining the ELF File
According to the
generic format specification an ELF file consists of:
- a File header, which must appear at the beginning of the file.
- Section table
- Program header table: Describes the [..] data structures required for loading a program [..].
- Contents of the sections and segments
The ELF file is used by the loader and by the linker in two different ways:
- The linker works with sections. It rearranges sections and consolidates them over different files.
- The loader works with segments specified by the programm headder’s. A segment consists of several consecutive segments an is loaded into the memory at once.
File Header
Diving further into the specification we find that the headder consists of the following components:
- unsigned char e_ident[16]; /* ELF identification */
- Elf64_Half e_type; /* Object file type */
- Elf64_Half e_machine; /* Machine type */
- Elf64_Word e_version; /* Object file version */
- Elf64_Addr e_entry; /* Entry point address */
- Elf64_Off e_phoff; /* Program header offset */
- Elf64_Off e_shoff; /* Section header offset */
- Elf64_Word e_flags; /* Processor-specific flags */
- Elf64_Half e_ehsize; /* ELF header size */
- Elf64_Half e_phentsize; /* Size of program header entry */
- Elf64_Half e_phnum; /* Number of program header entries */
- Elf64_Half e_shentsize; /* Size of section header entry */
- Elf64_Half e_shnum; /* Number of section header entries */
- Elf64_Half e_shstrndx; /* Section name string table index */
The first column describes the bit length of the corresponding entries.
The first line describes char=byte array of length 16, carrying the ELF Identification
In our example this is:
7F 45 4C 46 02 01 01 00 00 00 00 00 00 00 00 00
These bytes have the following meaning:
- 7F = EI_MAG0 - File identification
- 45 = EI_MAG1 = ‘E’
- 4C = EI_MAG2 = ‘L’
- 46 = EI_MAG3 = ‘F’
- 02 = EI_CLASS - File class - 2 for 64 bit
- 01 = EI_DATA - Data encoding - 1 for [http://en./wiki/Endianness little-endian] byte sorting
- 01 = EI_VERSION - File version
- 00 = EI_OSABI - OS/ABI identification - 0 for System V ABI
- 00 = EI_ABIVERSION - ABI version
- 00 = EI_PAD - Start of padding bytes
- [..]
- 00 = EI_NIDENT - Size of e_ident[]
Fortunately we do not need to do all this byte matching by hand. There is already a linux tool that does that for you:
$ readelf -h a.out
Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
Class: ELF64
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: EXEC (Executable file)
Machine: Advanced Micro Devices X86-64
Version: 0x1
Entry point address: 0x4003e0
Start of program headers: 64 (bytes into file)
Start of section headers: 4448 (bytes into file)
Flags: 0x0
Size of this header: 64 (bytes)
Size of program headers: 56 (bytes)
Number of program headers: 9
Size of section headers: 64 (bytes)
Number of section headers: 31
Section header string table index: 28
What do we learn from this information:
- The file is to be executed on a UNIX - System V compatible machine, with a 64bit Processor
- There are 31 sections with each having a header of size 64 bytes
- There are 9 segments each haveing a program header of size 56 bytes
- The executable code starts at offset 0x3e0 = 992
ELF File structure
We see that the file has the following structure (byte offsets in []-braces):
[0 - 63] File headder (64 bytes)
[64-120][..][511-567] Program headders (9*56 bytes)
[568-4447] ??? (4327 bytes)
[4448-4512][..][6368-6431] Section headders (31*64 bytes)
[6432-8445] ??? (3932 bytes)
Sections
Lets go ahead and instpect the section headders. Fortunately the byte
matching to the reference greatly simplyfied by use ‘readelf
–sections’. We see that there are 31 section headers, starting at
offset 0x1160:
Section Headers:
[Nr] Name Type Address Offset
Size EntSize Flags Link Info Align
[ 0] NULL 0000000000000000 00000000
0000000000000000 0000000000000000 0 0 0
[ 1] .interp PROGBITS 0000000000400238 00000238
000000000000001c 0000000000000000 A 0 0 1
[ 2] .note.ABI-tag NOTE 0000000000400254 00000254
0000000000000020 0000000000000000 A 0 0 4
[..]
[12] .init PROGBITS 00000000004003a8 000003a8
0000000000000018 0000000000000000 AX 0 0 4
[13] .plt PROGBITS 00000000004003c0 000003c0
0000000000000020 0000000000000010 AX 0 0 4
[14] .text PROGBITS 00000000004003e0 000003e0
00000000000001e8 0000000000000000 AX 0 0 16
[15] .fini PROGBITS 00000000004005c8 000005c8
000000000000000e 0000000000000000 AX 0 0 4
[16] .rodata PROGBITS 00000000004005d8 000005d8
0000000000000004 0000000000000004 AM 0 0 4
[..]
[22] .dynamic DYNAMIC 0000000000600e40 00000e40
00000000000001a0 0000000000000010 WA 7 0 8
[..]
[25] .data PROGBITS 0000000000601008 00001008
0000000000000010 0000000000000000 WA 0 0 8
[26] .bss NOBITS 0000000000601018 00001018
0000000000000010 0000000000000000 WA 0 0 8
[27] .comment PROGBITS 0000000000000000 00001018
0000000000000048 0000000000000001 MS 0 0 1
[28] .shstrtab STRTAB 0000000000000000 00001060
00000000000000fe 0000000000000000 0 0 1
[29] .symtab SYMTAB 0000000000000000 00001920
0000000000000600 0000000000000018 30 47 8
[30] .strtab STRTAB 0000000000000000 00001f20
00000000000001de 0000000000000000 0 0 1
Key to Flags:
W (write), A (alloc), X (execute), M (merge), S (strings)
I (info), L (link order), G (group), x (unknown)
O (extra OS processing required) o (OS specific), p (processor specific)
From this table we first read off the ‘‘offsets’’ of the sections,
which is contained in the last column. The first section starts at
00000238 which is the hex code for 568. And indeed the first gap
[568-4447] just starts at this point. Comparing the further offests
we see that the full gap is populated by the sections [1 .interp] -
[28 .shstrtab] . The latter gap [6432-8845] is populated by
sections [29 .symtab] -[30 .strtab] .
Another information we can get from this table is that only the sections:
- [12] .init
- [13] .plt
- [14] .text
- [15] .fini
contain executable data.
Segments
To extract the information about from the Program header we call:
$ readelf --segments a.out
Elf file type is EXEC (Executable file)
Entry point 0x4003e0
There are 9 program headers, starting at offset 64
Program Headers:
Type Offset VirtAddr PhysAddr
FileSiz MemSiz Flags Align
PHDR 0x0000000000000040 0x0000000000400040 0x0000000000400040
0x00000000000001f8 0x00000000000001f8 R E 8
INTERP 0x0000000000000238 0x0000000000400238 0x0000000000400238
0x000000000000001c 0x000000000000001c R 1
[Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]
LOAD 0x0000000000000000 0x0000000000400000 0x0000000000400000
0x000000000000067c 0x000000000000067c R E 200000
LOAD 0x0000000000000e18 0x0000000000600e18 0x0000000000600e18
0x0000000000000200 0x0000000000000210 RW 200000
DYNAMIC 0x0000000000000e40 0x0000000000600e40 0x0000000000600e40
0x00000000000001a0 0x00000000000001a0 RW 8
NOTE 0x0000000000000254 0x0000000000400254 0x0000000000400254
0x0000000000000044 0x0000000000000044 R 4
GNU_EH_FRAME 0x00000000000005dc 0x00000000004005dc 0x00000000004005dc
0x0000000000000024 0x0000000000000024 R 4
GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000
0x0000000000000000 0x0000000000000000 RW 8
GNU_RELRO 0x0000000000000e18 0x0000000000600e18 0x0000000000600e18
0x00000000000001e8 0x00000000000001e8 R 1
Section to Segment mapping:
Segment Sections...
00
01 .interp
02 .interp .note.ABI-tag .note.gnu.build-id .hash .gnu.hash
.dynsym .dynstr .gnu.version .gnu.version_r .rela.dyn
.rela.plt .init .plt .text .fini .rodata .eh_frame_hdr .eh_frame
03 .ctors .dtors .jcr .dynamic .got .got.plt .data .bss
04 .dynamic
05 .note.ABI-tag .note.gnu.build-id
06 .eh_frame_hdr
07
08 .ctors .dtors .jcr .dynamic .got
Program Code with objdump
After identifying the executable parts of the program lets inspect these parts.
We disassemble the parts using objdump.
Disassembly of section .init:
00000000004003a8 <_init>:
4003a8: 48 83 ec 08 sub $0x8,%rsp
4003ac: e8 5b 00 00 00 callq 40040c <call_gmon_start>
4003b1: e8 ea 00 00 00 callq 4004a0 <frame_dummy>
4003b6: e8 d5 01 00 00 callq 400590 <__do_global_ctors_aux>
4003bb: 48 83 c4 08 add $0x8,%rsp
4003bf: c3 retq
Disassembly of section .plt:
00000000004003c0 <__libc_start_main@plt-0x10>:
4003c0: ff 35 2a 0c 20 00 pushq 0x200c2a(%rip)
4003c6: ff 25 2c 0c 20 00 jmpq *0x200c2c(%rip)
4003cc: 0f 1f 40 00 nopl 0x0(%rax)
00000000004003d0 <__libc_start_main@plt>:
4003d0: ff 25 2a 0c 20 00 jmpq *0x200c2a(%rip)
4003d6: 68 00 00 00 00 pushq $0x0
4003db: e9 e0 ff ff ff jmpq 4003c0 <_init+0x18>
Disassembly of section .text:
00000000004003e0 <_start>:
4003e0: 31 ed xor %ebp,%ebp
4003e2: 49 89 d1 mov %rdx,%r9
4003e5: 5e pop %rsi
4003e6: 48 89 e2 mov %rsp,%rdx
4003e9: 48 83 e4 f0 and $0xfffffffffffffff0,%rsp
4003ed: 50 push %rax
4003ee: 54 push %rsp
4003ef: 49 c7 c0 f0 04 40 00 mov $0x4004f0,%r8
4003f6: 48 c7 c1 00 05 40 00 mov $0x400500,%rcx
4003fd: 48 c7 c7 c4 04 40 00 mov $0x4004c4,%rdi
400404: e8 c7 ff ff ff callq 4003d0 <__libc_start_main@plt>
400409: f4 hlt
40040a: 90 nop
40040b: 90 nop
000000000040040c <call_gmon_start>:
40040c: 48 83 ec 08 sub $0x8,%rsp
400410: 48 8b 05 c9 0b 20 00 mov 0x200bc9(%rip),%rax
400417: 48 85 c0 test %rax,%rax
40041a: 74 02 je 40041e <call_gmon_start+0x12>
40041c: ff d0 callq *%rax
...
0000000000400430 <__do_global_dtors_aux>:
400430: 55 push %rbp
400431: 48 89 e5 mov %rsp,%rbp
400434: 53 push %rbx
...
00000000004004a0 <frame_dummy>:
4004a0: 55 push %rbp
4004a1: 48 83 3d 8f 09 20 00 cmpq $0x0,0x20098f(%rip)
4004a8: 00
00000000004004c4 <main>:
4004c4: 55 push %rbp
4004c5: 48 89 e5 mov %rsp,%rbp
4004c8: c7 45 fc 05 00 00 00 movl $0x5,-0x4(%rbp)
4004cf: c7 45 f8 08 00 00 00 movl $0x8,-0x8(%rbp)
4004d6: 8b 45 f8 mov -0x8(%rbp),%eax
4004d9: 8b 55 fc mov -0x4(%rbp),%edx
4004dc: 8d 04 02 lea (%rdx,%rax,1),%eax
4004df: 89 45 f4 mov %eax,-0xc(%rbp)
4004e2: c9 leaveq
4004e3: c3 retq
...
00000000004004f0 <__libc_csu_fini>:
...
0000000000400500 <__libc_csu_init>:
...
0000000000400590 <__do_global_ctors_aux>:
...
Disassembly of section .fini:
00000000004005c8 <_fini>:
4005c8: 48 83 ec 08 sub $0x8,%rsp
4005cc: e8 5f fe ff ff callq 400430 <__do_global_dtors_aux>
4005d1: 48 83 c4 08 add $0x8,%rsp
4005d5: c3 retq
In this view the content of our executable sections grouped into machine operations in the middle column.
The colum to the left is an offset counter and on the right we find a translation of the operations
to the Assembly Language.
Observations:
- The sections are grouped by function names:
< .... >
- The entry point was the adress 0x3e0 and points to the beginning of the
<_start> function
- There is a function
<main> , which is also the name of the function in our c Progam.
Let’s look inside the <main> function:
push %rbp
mov %rsp,%rbp
movl $0x5,-0x4(%rbp)
movl $0x8,-0x8(%rbp)
mov -0x8(%rbp),%eax
mov -0x4(%rbp),%edx
lea (%rdx,%rax,1),%eax
mov %eax,-0xc(%rbp)
leaveq
We find our numbers 5 and 8 declared as constants ($) in hexadecimal
format. These are stored into a memory location specified by the %rbp
register with a certain offset. Then the values are read from memory
and copied into the %eax and %edx registers. Afterwards these
registers are added (lea ) and the result is stored in %eax .
Stepping through the code
We can use the gnu debugger
gdb to see how the program
is executed. Call gdb a.out to start a debuggiong session. Our
comments appear at after (#):
$ gdb a.out
GNU gdb (GDB) 7.1-ubuntu
Copyright (C) 2010 Free Software Foundation, Inc.
[...]
(gdb) b _start # Insert a breakpoint at function _start
Breakpoint 1 at 0x4003e0
(gdb) r # run the program
Starting program: /home/heinrich/Desktop/C_experiments/b.out
Breakpoint 1, 0x00000000004003e0 in _start ()
(gdb) stepi # one step forwards
0x00000000004003e2 in _start ()
Pressing [enter] now repeatedly we can step forwards trough the program.
It will display the offset of the current instruction and the function being executed.
The following functions are called:
- _start ()
- __libc_start_main@plt ()
- ?? ()
- ?? () from /lib64/ld-linux-x86-64.so.2 (ca. 1000 instructions!)
- __do_global_ctors_aux ()
- init ()
- __libc_csu_init ()
- __libc_start_main () from /lib/libc.so.6
- _setjmp () from /lib/libc.so.6
- ?? () from /lib/libc.so.6
- __libc_start_main () from /lib/libc.so.6
- ’'’main ()’’’ ( HERE WE ARE ! – finally )
- __libc_csu_init ()
- ? () from /lib/libc.so.6 (another 500 instructions)
Now we show last command in assembly language using gdb:
(gdb) display/i $pc
=> 0x4003e2 <_start+2>: mov %rdx,%r9
(gdb) stepi
0x00000000004003e5 in _start ()
1: x/i $pc
=> 0x4003e5 <_start+5>: pop %rsi
(gdb) info registers # show contents of registers
rax 0x1c 28
rbx 0x0 0
rcx 0x7ffff7ffd040 140737354125376
rdx 0x7ffff7dec250 140737351959120
rsi 0x7ffff7df7a83 140737352006275
...
r8 0xb 11
r9 0x7ffff7dec250 140737351959120
r10 0xb 11
...
gs 0x0 0
Memory Management
We have been told, that the segments of the ELF file are loaded into the memory
of the computer. Can we see how that really works?
- Which memory segments are reserved for the program?
- What is inside these memoy pages.
A nice explanation of the physical lyout of the memory can be found inside the
GDB documentation.
As explained in the note, each program assumes that it can access all the memory of the computer
and starts writing it offset 0. This is of course not the case. The instead the OS provides
reserved spaces inside the memory (virtual memory pages) which are typically 4kb in size Wikipedia - Virtual Memory.
The translation of the adresses to the physical location is made on the fly by a special coprocessor called Memory Mamagement Unit (MMU).
The OS binds these VMP to a process. Unless explicitly stated, no other process is allowed
to read out this memory.
So how do whe memory pages look like that we got for our sweet little program?
Linux helps us with that. We first run the program inside the debugger in order to have it in the memory.
$ gdb a.out
(gdb) b main
(gdb) r
Then we open another terminal and type (cf. [http://linux./man/5/proc man proc])
$ cat /proc/`pgrep a.out`/maps
and get:
Address Per. Offset Dev. inode. Path name
00400000-00401000 r-xp 00000000 08:05 21775994 /home/.../a.out
00600000-00601000 r--p 00000000 08:05 21775994 /home/.../a.out
00601000-00602000 rw-p 00001000 08:05 21775994 /home/.../a.out
7ffff7a5a000-7ffff7bd4000 r-xp 00000000 08:05 15341246 /lib/libc-2.11.1.so
7ffff7bd4000-7ffff7dd3000 ---p 0017a000 08:05 15341246 /lib/libc-2.11.1.so
7ffff7dd3000-7ffff7dd7000 r--p 00179000 08:05 15341246 /lib/libc-2.11.1.so
7ffff7dd7000-7ffff7dd8000 rw-p 0017d000 08:05 15341246 /lib/libc-2.11.1.so
7ffff7dd8000-7ffff7ddd000 rw-p 00000000 00:00 0
7ffff7ddd000-7ffff7dfd000 r-xp 00000000 08:05 15341231 /lib/ld-2.11.1.so
7ffff7fcf000-7ffff7fd2000 rw-p 00000000 00:00 0
7ffff7ff9000-7ffff7ffb000 rw-p 00000000 00:00 0
7ffff7ffb000-7ffff7ffc000 r-xp 00000000 00:00 0 [vdso]
7ffff7ffc000-7ffff7ffd000 r--p 0001f000 08:05 15341231 /lib/ld-2.11.1.so
7ffff7ffd000-7ffff7ffe000 rw-p 00020000 08:05 15341231 /lib/ld-2.11.1.so
7ffff7ffe000-7ffff7fff000 rw-p 00000000 00:00 0
7ffffffde000-7ffffffff000 rw-p 00000000 00:00 0 [stack]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
An better readble version is produced by
$ cat /proc/`pgrep a.out`/smaps
but uses up too much space to reproduce it here. We need to compare
this to the output of the segmet view:
Type Offset VirtAddr PhysAddr
FileSiz MemSiz Flags Align
PHDR 0x0000000000000040 0x0000000000400040 0x0000000000400040
0x00000000000001f8 0x00000000000001f8 R E 8
INTERP 0x0000000000000238 0x0000000000400238 0x0000000000400238
0x000000000000001c 0x000000000000001c R 1
[Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]
LOAD 0x0000000000000000 0x0000000000400000 0x0000000000400000
0x000000000000067c 0x000000000000067c R E 200000
LOAD 0x0000000000000e18 0x0000000000600e18 0x0000000000600e18
0x0000000000000200 0x0000000000000210 RW 200000
DYNAMIC 0x0000000000000e40 0x0000000000600e40 0x0000000000600e40
0x00000000000001a0 0x00000000000001a0 RW 8
NOTE 0x0000000000000254 0x0000000000400254 0x0000000000400254
0x0000000000000044 0x0000000000000044 R 4
GNU_EH_FRAME 0x00000000000005dc 0x00000000004005dc 0x00000000004005dc
0x0000000000000024 0x0000000000000024 R 4
GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000
0x0000000000000000 0x0000000000000000 RW 8
GNU_RELRO 0x0000000000000e18 0x0000000000600e18 0x0000000000600e18
0x00000000000001e8 0x00000000000001e8 R 1
Comparing the VirtAddr colum to the Address colum above suggests, that the segments:
PHDR 0x0000000000000040 0x0000000000400040 0x0000000000400040
INTERP 0x0000000000000238 0x0000000000400238 0x0000000000400238
LOAD 0x0000000000000000 0x0000000000400000 0x0000000000400000
NOTE 0x0000000000000254 0x0000000000400254 0x0000000000400254
GNU_EH_FRAME 0x00000000000005dc 0x00000000004005dc 0x00000000004005dc
Are mapped into the the first memory page. And segments:
LOAD 0x0000000000000e18 0x0000000000600e18 0x0000000000600e18
DYNAMIC 0x0000000000000e40 0x0000000000600e40 0x0000000000600e40
GNU_RELRO 0x0000000000000e18 0x0000000000600e18 0x0000000000600e18
into the second one. The segment:
GNU_STACK 0x0000000000000000 0x0000000000000000 0x0000000000000000
has only zero entries and seems to have something to do with the program stack,
which has its own VM page:
7ffffffde000-7ffffffff000 rw-p 00000000 00:00 0 [stack]
Inspecting the memory
We can use the GNU debugger to look inside these memory locations!
Lets first display the beginning of the first memory page starting at 0x400000:
(gdb) x/24x 0x00400000
0x400000: 0x7f 0x45 0x4c 0x46 0x02 0x01 0x01 0x00
0x400008: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x400010: 0x02 0x00 0x3e 0x00 0x01 0x00 0x00 0x00
Do you see what this is?? Precisely the beginning of the ELF file: ‘0x7f ELF’
Resources
- General
- Architecture
- ELF Files
- Application Binary Interfaces
- Assembler
- C Programming
- Operating System
View the version history of this post on GitHub.
Comments have been disabled until the dust around the GDPR settled.
|