<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
Operating Systems MSc(Conversion)
Linking and Loading Experiment
Assessed
exercise - Handout Mon 13 Nov, Handin Mon 20 Nov <!-- Linking and Loading Experiment --><!-- -->
This exercise supports the Architecture, Operating Systems and Compilers courses, and aims to give some practical experience of what compilers, assemblers, linkers and loaders do.
You need to use Linux, not Windows, to do this exercise. This is because linking is simpler on Linux (or, more precisely, it is easier to keep it simple). Linux also has tools which make it easy to see what is going on. However, the principles are the same on practically all operating systems. We hope you will also find it useful and interesting to get the opportunity to become familiar with Linux, a very powerful system of growing importance.
You are encouraged to work through the exercise, discussing it with friends. The exercise is assessed: as you proceed through the instructions below, watch out for the five questions. Very short answers should be sufficient to get full marks.
2. Getting started with Linux
Log-in to one of the Department's Linux machines. You can do this either by finding a machine which is running Linux, or by using a Windows NT machine and connecting to a Linux machine over the network, or by rebooting a Windows NT machine and selecting “RedHat Linux” during the reboot sequence (all our lab machines can be rebooted this way).
· To access a Linux machine from one of the Windows NT machines,
1. double click on the "Exceed" shortcut on your Windows desktop.
2. After a (fairly) short delay, you should get a dialog box inviting you to select a host to connect to.
3. Click "Host list"
4. Click on any one of the machines listed, and click "Accept"
5. After a (fairly) short delay, you should get a dialog box inviting you to login to the machine you selected. Type your login name and password in the boxes indicated, and press the Enter key.
6. After a (fairly) short delay, you should get a window which lets you type commands for the remote Linux machine, as required for this exercise. You can check that this is working by typing the Linux command "who" (followed by pressing the Enter key); this will list the current users of the machine to which you have connected.
7. When you have finished using Linux, right-click the "Exceed" panel in the Windows taskbar (at the bottom of your screen), select "Close"
8. If for some reason this doesn't work, start again from step 1 - but make sure Exceed is closed first, see step 7.
· To use a Linux machine instead,
1. Find a PC which is running Linux, which is showing the login dialogue box.
2. Type your login identifier and password
3. After a (fairly) short delay, you should get various windows. The important window which you need for this exercise is called "xterm". This is running the Linux command interpreter - called a "shell".
4. For more help see the Department's introductory guides; a good starting point is http://www.doc.ic.ac.uk/~phjk/OperatingSystemsConcepts/Exercises/Tutorial-03/LinuxHelp.html
5. When you are ready to finish your session, click the K button on the taskbar and choose the Logout option.
· Some hints for those new to Unix and/or Linux
1. Linux is one of several versions of the Unix operating system
2. Although graphical windowing environments are available for Linux, the normal way to interact with Linux is to type commands. A command line always begins with the command name, may be followed by some options, and may be followed by some arguments. You can edit your command line using the keyboard's arrow and delete keys. At the end of the command, you must press the "Enter" (or "return") key.
3. Linux has several editor and file-viewer programs. For this exercise, you are advised to use "nedit". To view a file "Message" type the command
nedit Message &
The "nedit" application will shortly appear in a new window. The ampersand "&" is useful.
4. If the output of a command (such as "who") turns out to be too big to view using your shell window, try this:
who > myfile
nedit myfile &
The ">" symbol redirects the output from "who" into the file "myfile" (you can choose any filename). Then you can use nedit to inspect it.
5. If you ever need to stop a Linux program, try control-c (ie hold down the "control" key and press "c").
6. If you want to know more about a Linux command, such as "who", type "man who". The "man" command provides access to the on-line manual.
2. The linking and loading exercise: What To Do
Copy the files you need into your working directory</SF>. To do this, type the following command, which has been set up specially for this exercise:
exercise linkload
Now, list your working directory: type the command "ls". You should[1] have the following files:
assembler.s
a very simple intel assembly language program.
cversion.c
a C version of the same program.
writeexit.s
another assembly language file that provides some support for the C version.
example.c
a slightly more complex C program, with procedures and arrays that is useful for experimenting with optimization.
Now, work through the remainder of this document, trying out the suggested commands.
The principles of Linux assembler programs are similar to other assembler programs you may have seen, though the Linux assembler's syntax differs from the msdos assembler's.
Appendix assemsyntax contains a summary of the differences you need to know about.
.text
.globl _start
_start:
movl $0x4,%eax # eax = code for 'write' system call
movl $1,%ebx # ebx = file descriptor to standard output
movl $message,%ecx # ecx = pointer to the message
movl $13,%edx # edx = length of the message
int $0x80 # make the system call
movl $0x1,%eax # eax = code for 'exit' system call
int $0x80 # make the system call
.data
.globl message
message:
.string "Hello world\n" # The message as data
In assembler.s , the int instruction is a software interrupt (trap), used here to make requests to the Linux operating system. The value in register eax indicates which system call is to be made, and depending on the call, other information is passed to Linux in other registers. The mysterious "$0x4" is the assembler's syntax for a hexadecimal number.
The program as is the Unix assembler, the flag -o specifies the name of the output file, here assembler.o. Type the command
as assembler.s -o assembler.o
The resulting file contains binary machine instructions, initialized values and other data.
The program called file identifies the type of a file by analyzing its contents. Enter the command file assembler.o to get:
assembler.o: ELF 32-bit LSB relocatable, Intel 80386, version 1, not stripped
Executable code on Linux is usually stored in a file in 'ELF' format (Executable and Linkable Format)[P H J1].
Each executable file starts with an elf header. The header contains information about the program and what kind of machine it is meant to run on. The program entry point, and the address where execution should start is stored there. The header is described by the C structure declaration taken from the include file /usr/include/elf.h below:
typedef struct
{
unsigned char e_ident[EI_NIDENT]; /* Magic number and other info */
Elf32_Half e_type; /* Object file type */
Elf32_Half e_machine; /* Architecture */
Elf32_Word e_version; /* Object file version */
Elf32_Addr e_entry; /* Entry point virtual address */
Elf32_Off e_phoff; /* Program header table file offset */
Elf32_Off e_shoff; /* Section header table file offset */
Elf32_Word e_flags; /* Processor-specific flags */
Elf32_Half e_ehsize; /* ELF header size in bytes */
Elf32_Half e_phentsize; /* Program header table entry size */
Elf32_Half e_phnum; /* Program header table entry count */
Elf32_Half e_shentsize; /* Section header table entry size */
Elf32_Half e_shnum; /* Section header table entry count */
Elf32_Half e_shstrndx; /* Section header string table index */
} Elf32_Ehdr;
A C structure is the equivalent of a Turing or Pascal record, and is a primitive version of a class in C++ or Java. The most important fields in this header are pointers to the rest of the information about the file, organized in two tables like the content pages of a book. Each table entry is a fixed sized header, which contains information about sections (parts of the file): the text (executable part of the program), data, symbol table and relocation information.
Examine the contents of a non-text file like assembler.o using the Unix octal-dumping utility od. Type:
od -xc -Ax assembler.o
The flags -xc and -Ax tell od to show the file in hexadecimal and ASCII, giving addresses in hexadecimal, starting from zero. The od output is a sequence of pairs of lines. Each pair shows the starting address, the next 16 bytes as 8 hexadecimal words, and the same 16 bytes as ASCII characters if they represent printable characters.
The result should start something like this (only the relevant
output is shown to make the picture smaller). <FIGURE><EPS FILE="elf.eps"></FIGURE>
The magic number
identifies the file as ELF
the next 4 bytes
say how to read it: that the file contains 32 bit words, and the order of bytes in a word, on Intel machines the lowest significant byte is in the lowest address i.e. little-endian (look at the order of the bytes in the first and second rows). Machines with other architectures can identify and read the file even if they can't run it.
the file is relocatable code
for an Intel386 (or upwards compatible) cpu
the entry point of the program
( the address of first instruction to run) is 0. The value is filled in later.
A relocatable file cannot be run yet, so there are no 'program headers'. The rest of information is held in "sections": there are 8 sections, the header for the first section starts at 0x9C and the headers are 0x28 bytes long, so the second one starts at 0xC4. The definition is given in the Linux file "/usr/include/elf.h", an extract of which is shown below:
/* Section header. */
typedef struct {
Elf32_Word sh_name; /* Section name (string tbl index) */
Elf32_Word sh_type; /* Section type */
Elf32_Word sh_flags; /* Section flags */
Elf32_Addr sh_addr; /* Section virtual addr at execution */
Elf32_Off sh_offset; /* Section file offset */
Elf32_Word sh_size; /* Section size in bytes */
Elf32_Word sh_link; /* Link to another section */
Elf32_Word sh_info; /* Additional section information */
Elf32_Word sh_addralign; /* Section alignment */
Elf32_Word sh_entsize; /* Entry size if section holds table */
} Elf32_Shdr;
/* Legal values for sh_type (section type). */
#define SHT_NULL 0 /* Section header table entry unused */
#define SHT_PROGBITS 1 /* Program data */
#define SHT_SYMTAB 2 /* Symbol table */
#define SHT_STRTAB 3 /* String table */
#define SHT_RELA 4 /* Relocation entries with addends */
#define SHT_HASH 5 /* Symbol hash table */
#define SHT_DYNAMIC 6 /* Dynamic linking information */
#define SHT_NOTE 7 /* Notes */
#define SHT_NOBITS 8 /* Program space with no data (bss) */
#define SHT_REL 9 /* Relocation entries, no addends */
#define SHT_SHLIB 10 /* Reserved */
#define SHT_DYNSYM 11 /* Dynamic linker symbol table */
#define SHT_NUM 12 /* Number of defined types. */
The first section header is not used
and not printed,
The second header starts at 0xC4
and shows where the program code is in the file. Adding 0x64 to its first field, the sh_name word (0x1B) , gives a pointer 0x7F in the file to the section name string ".text". This is the section which contains the binary instructions to be executed.
relocation
The next header (not shown) says that relocation information starts at address 0x24c (the last thing in the file): details how the program should be modified to load it to a different address.
data
Then comes the header that points at the data for the program.
symbol table
The other important information is the symbol table, found near the end of the file. The symbol table is a list of labels (procedures names, variable names) in the program.
5. Examining the symbol table
The Unix symbol names utility nm lists all the symbols defined or used in an elf format file. Try running:
nm assembler.o
The only labels defined in this program are start and message. The Unix manual page man;nm explains what the output means.
The utility objdump is handy for looking at executable files, it displays information about the format and the sections of the file, try:
objdump --all-headers assembler.o
Use the option --disassemble to make objdump display the executable part of the file as assembler code.
Question 1: How
big (how many bytes) is the program code section of file
"assembler.o"?
Question 2: How
many relocation records are there in "assembler.o"?
The purpose of the linker program ld is to manage labels in a program which may consist of modules which have been compiled separately. In the simple example given above all that needs to be done is to relocate the text and data so that it resides at the right start address. To do this type
ld -N assembler.o -o assembler
This command takes the code from assembler.o and relocates it for loading at address 0x08048074 where the Unix loader expects it to be, and saves the resulting executable program in the file assembler . This is in the same format as assembler.o , but examining it using od shows that it now has the entry point 0x08048074 and a few other bits and pieces have also changed. You may wish to examine it again, either using od or objdump.
Question 3: How
many relocation records are there in "assembler"?
Just type "./assembler" to run the program[2]. At this point the data structure contained in the file assembler is interpreted by the operating system loader. It checks the machine type and examines the header to determine what kind of environment the process will need. Having set up a new process of the appropriate kind, the instructions and initialized data are loaded into free memory, and the operating system branches to the entry point. This behavior is described in detail by the manual page for the execve system call.
The C version of the same simple program is given in cversion.c :
extern void write(int, char [], int );
extern void exit(int);
char message [] = "Hello World!\n";
#define MESSAGELENGTH 13
int main(){
write(1,message,MESSAGELENGTH);
exit(1);
}
This program imports two externally-defined functions write() and exit() which are defined in writeexit.s:
.text
# an implementation of write and exit
.globl write
write:
pushl %ebx
movl 0x10(%esp,1),%edx
movl 0xc(%esp,1),%ecx
movl 0x8(%esp,1),%ebx
movl $0x4,%eax
int $0x80
popl %ebx
ret
.globl exit
exit:
movl %ebx,%edx
movl 0x4(%esp,1),%ebx
movl $0x1,%eax
int $0x80
The rest of the exercise concentrates on constructing a running program from these two parts, examining the intermediate files at every stage. The steps involved in producing a runnable program are :
- Use the C compiler gcc to translate the C program into an assembler program. Type:
gcc -S cversion.c
The -S flag means stop after producing the assembler version. Examine the results in an assembler file called cversion.s .
- Assemble this file using as, type:
as cversion.s -o cversion.o
This results in the file cversion.o, which is in elf format.
- Assemble the file writeexit.s:
as writeexit.s -o writeexit.o
Try nm on this. What does its output mean this time?
- Link the two using ld. Type:
ld -N cversion.o writeexit.o -o cversion
This results in a file called cversion, which is also in the elf format. Run it and then examine its contents using od, nm and objdump.
Question 4: What happens if you try to link
"cversion.o" using ld, as you did
with assembler.o? Try nm on it. What does its output mean?
Question
5: Why does "cversion.s" end with a "ret" instruction, but
"assembler.s" does not?
10. Experimenting with optimisation (optional and unassessed)
Now you know how to run the C compiler and examine its output, you can experiment to see how clever the C compiler can be. For example, does it replace constant expressions by their values? Does it avoid recomputing an expression's value inside a loop if that value cannot change during the lifetime of the loop?
To perform experiments like this, use the slightly more complex C program provided to start with, example.c
/*
* This shows a procedure call with a single parameter.
* It looks simple enough, but at high optimisation levels
* produces some pretty weird code.
*/
int i;
int a[100];
int b;
void f(int c){
for (i = 1; i < 100-2*25; i = i + 1){
a[i] = c*3+10;
}
}
int main(){
f(b);
return 0;
}
Use the C compiler to compile example.c into an assembly language version:
gcc -S example.c
Normally the C compiler tries to compile quickly rather than to produce very good code. But if you use the -O flag, it will try to optimise the code.
gcc -O -S example.c
or
gcc -O2 -S example.c
or even
gcc -O2 -finline-functions -S example.c
Examine the assembly code produced by each level of optimisation -- you may find that the code gets rather complicated at high optimization levels.
The exercise has been carefully constructed to avoid using some of the more advanced features which would normally come into play when compiling under Linux. In particular:
· Normally, write() and exit() would be found in the C standard library /usr/lib/libc.a. The standard library and the C run-time system /usr/lib/crt1.o are normally linked with C programs automatically -- linking is normally done using gcc not ld. This was prevented here by performing the link phase explicitly, forcing the linker to omit all such libraries. You can inspect /usr/lib/libc.a and /usr/lib/crt1.o using objdump.
· The -N flag of the ld program prevents the use of Linux's shared libraries mechanism. The shared libraries scheme does not link in all the library routines with each executable thus making the stored executables smaller. Instead, a single copy of the library routines is loaded into memory at run-time and shared between all programs running on the same machine at the same time. This speeds program loading, reduces disk swapping, and therefore speeds program execution.
· Adding the option -v to gcc will show what it is doing and which files are used. To convert a C program into a binary file gcc runs four programs, cpp the C pre-processor, cc1 the compiler, as and ld.
Appendix
The assembler used on Linux has a syntax similar to other Unix assemblers and differs from the MS-DOS assembler:
· Unix tools like the assembler and C compiler, when they read or write numbers, prefix 0x to indicate the number is written in hexadecimal and 0 that it is octal.
· Register names start with "%", 'e' at the start of a register name e.g. %eax shows the full 32 bits are used.
· The operands written are in the order: source, destination, the opposite order to MS-DOS assembler.
· Constants in the assembler source are written with a leading $.
(This
document is based on the CS2 lab exercise on Linking and Loading, available
on-line at http://www.doc.ic.ac.uk/lab/secondyear/linkload;
it has been modified to add assessment, and to include additional guidance for
students new to Unix/Linux).
Paul
Kelly Imperial College November 2000