Chapter 2: From Source File to Executable File

Overview

Transformation of a source file to a load (executable) module. Why we can and do discuss source programs and their behavior as if they were executing somewhere in memory in their source form. Concepts of static memory allocation, dynamic memory allocation, program address space, and program system stack.

It is useful and practical to discuss the behavior (often referred to as the semantics) of a computer program written in a high-level language like C or C++ as if it were executing in computer memory in its source form. For instance, the semantics of the statement x = x+1 might be described as "the value of the variable x is incremented by 1 ", yet nothing could be farther from the truth because the program in its source form is a simple ASCII text file sitting quietly somewhere on a disk doing nothing. On the other hand, speaking conceptually, this is exactly what happens to the variable x when the program executes - although, to confuse matters even more, there is no variable x to speak of when the program is running. In order to understand all of this, we must discuss the process of compilation, linking, loading, and execution of programs. Most of the facts discussed in this chapter can be found in various books and texts dealing with compilation and compilers, operating systems, and computer architecture.

Both C and C++ belong to a family of high-level symbolic languages, meaning that certain entities in such programs can be referenced by their names (symbols). In C these entities can be data items called variables (innate data like char or int , or user -defined structures using the struct construct or the array construct) and functions, whereas in C++ the data items also include objects (defined by the user via classes) and functions include class methods . In order to discuss C and C++ as if they were the same language, we will thus use the term objects to denote innate data, data structures, or arrays in C and innate data, data structures, arrays, or true objects in C++. The term function will refer to functions in C and to functions and class methods in C++.

High-level symbolic languages were invented for one and only one purpose: to make it simpler and more convenient for the programmer to write a program. Toward this end, such languages exhibit (in highly simplified and reduced form) the syntax and symbolic character of natural languages. As such they are not suitable for computers that understand only one language, the machine code in its binary form. The instructions of machine code can (oversimply) be described as instructions of the type "copy data from memory to register", "copy data from register to memory", "copy data within memory", or "do some calculation with data in one or two registers". It is the role of a computer program known as the compiler to translate the program written in a high-level symbolic language to the machine code. It is quite standard to call the simple ASCII text file in which the "sentences" of the high-level symbolic language are stored the source file or source module. The high-level symbolic language in which the program is written is customarily referred to as source language, while the program written in the source language is referred to as source code. The main purposes of the compiler are translating each complex instruction of the source language into a set of machine instructions and, of most interest to us, replacing each symbolic reference by an address reference.

Usually, the result of compilation is a binary file referred to as object file or object module , in which is stored the object code. Very often the program we are interested in is divided (for convenience) into a set of many source files, and thus the compiler will produce a set of object files. Almost any program written in C/C++ uses so-called standard functions (i.e., subprograms written by others and included with the compiler for the convenience of its users) that are prepared in object form. Therefore, after compilation, we are presented with a group of object files. These must be somehow forged together - in a process known as linking - into a single binary file called the load file (or load module ) or the executable file ( module ). The careful reader should note that the term "linking" is commonly but misleadingly used for the whole process, which actually consists of two distinct phases and activities, relocation and linking; similarly, the term "compilation" is often used for the whole two-step process of compilation and linking. See Figure 2.1.

Figure 2.1: Compilation and linking

The load module is ready to be executed. The term "load" indicates the main purpose of the file: it can be loaded into memory (i.e., a complete copy of the file is stored in the memory with some additional changes to address references in the load module) and executed. The process of loading is rather complex and so we do not explain it in any fine detail; instead, we simply paint a broad picture that is relevant to how a program executes in memory.

Before we can embark on describing the main features of an object module, we must clarify some important terminology concerning programs written in C and C++ languages. The structure of a C program is rather simple. It is often called a flat-table approach, when a program consists of at least one function (and possibly more) and some definitions of objects. In C++ the picture becomes a bit more complicated because functions, data definitions, and objects can be lumped together into classes, but for the time being we may ignore this added complexity. Objects defined outside of functions have storage class static, meaning that they exist for the duration of the execution of the program. They are often referred to as global objects, for they can be referenced by their name in any function of the program (with some restrictions) regardless of the particular source file in which they reside. Confusingly enough, defining a global object with the keyword "static" does not change its storage class but does make it impossible for the object to be referenced in a different source file. Objects defined within functions (or within blocks) are referred to as local objects (i.e., local to the function or to the block). Their storage class is by default auto, for they are "created" automatically upon activation of their function and are automatically destroyed upon deactivation of that function. However, if a local object is defined with the keyword "static" then its storage class is changed, and it becomes a static object that exists throughout the duration of the program's execution (yet this does not make it a global object for the purpose of symbolic reference). Thus, when we speak of static data, we mean all global objects and all local objects that are defined as static. In Figure 2.2, objects 1 “6 are static.

Figure 2.2: Layout of a C/C++ source program and static objects

In order to discuss how an object module is created, we use the following simple C program. The array a[] represents the initialized (global) static data, the local variable k in main() represents the initialized (local) static data, and the array b[] represents the uninitialized (global) static data. The local variable i in main() does not enter our discussion until the end of this chapter.

 #include <stdio.h>    int a[10]={0,1,2,3,4,5,6,7,8,9};    int b[10];    /* function main ----------------------------------- */    void main()    {       int i;       static int k = 3;       for(i = 0; i < 10; i++) {        printf("%d\n",a[i]);        b[i] = k*a[i];       }/*endfor*/    }/*end main*/ 

An object module contains all source code statements translated to machine instructions (this is one of the reasons why an object file must be binary). The header section (see Figure 2.3) contains the sizes of all the other sections involved - including the size of the uninitialized data section, which is not created until load time - in order to parse the object module (because it is a binary file, no binary value can be used to indicate the end or beginning of a section). We are mostly interested in the initialized data and symbol table sections.

Figure 2.3: Object module structure

Figure 2.4 shows a simplified version of the object module for the sample program. The X indicates some binary data whose precise nature is not important and would be overly technical for understanding the principles behind creation of an object module. An important aspect for our discussion is the transformation of symbolic references (of the arrays a[] and b[] , the variable k , the function main() , and the standard function printf() ) into address references in terms of offset (distance in bytes) from the beginning of the object module (or a section). Thus "start executing function x() " will become "start executing instructions at address y ". Likewise, "store value in variable x " will become "store value at address y " and "get value of variable x " will become "fetch value from address y ".

Figure 2.4: Object module (simplified) of the sample program

The object module of our sample program is then linked together with at least two library object modules, one for the standard function printf() and the other containing the code for program termination. In the first phase, relocation, the object files are merged together and the internal address references within each object module must be updated to reflect the offset changes brought on by merging all three object modules into one. In the following phase, linking, external address references in each object module must be resolved. In our example, the linker must resolve the explicit reference from the object module of our sample program to the standard function printf() (i.e., replace it by the appropriate address reference through the offset with respect to the beginning of the load module being created) in the library object module and also resolve the implicit reference from the object module of our sample program to program termination code in another library object module. See Figure 2.5 for a schematic diagram of the whole process.

Figure 2.5: Creation of load module

The load module (still without the uninitialized data section) represents the abstract notion of the program address space. The loader finds all the required information about the program address space in the load module. As mentioned previously, all address references in the load module are in the form of the offset from the beginning of the load module. Such addresses are often called relative (or logical ) addresses. The loader and/or operating system must map the logical addresses to physical addresses in the main memory and then copy the binary information or data to these memory locations.

The process of memory mapping is quite complicated and depends in its technical details on the particular operating system and hardware platform. In the simplest case, a logical address is mapped onto a physical address by a simple addition of the logical address (offset) to the base register (starting address of the loaded program). The issue of memory mapping is complicated by the fact that most modern operating systems (like UNIX or Windows) employ virtual memory systems, which allow execution of programs with address spaces that are larger than the physical memory. Moreover, such memory systems allow for noncontiguous mapping - that is, two logical addresses that are consecutive in the logical address space of a program are mapped onto two nonconsecutive physical addresses. Caching, which is offered by most modern hardware platforms to speed up the execution of software, further complicates the issue of memory mapping. As we discuss in Chapter 11 (which covers the fundamentals of interprocess communication related to memory), shared memory segments are treated as memory-mapped files, and this makes memory mapping even more complicated. Figure 2.6 - rather schematic, but sufficient for our purpose - illustrates a program being loaded into memory.

Figure 2.6: Loading and memory mapping

Notice that the loader "created" the uninitialized data as a part of static data of the program address space; to do so, the loader only needs to know the section's size, which is stored in the header section of the load module. We have seen that there is a well-defined unequivocal process that leads from the source file (or files) to the program address space. The program address space is mapped also in a well-defined unequivocal process to various segments in the physical memory. It is thus possible for us to make a mental quantum leap and discuss the behavior of a program based on its address space as it is mapped into the memory; this is illustrated in Figure 2.7.

Figure 2.7: From source program to its "placement" in memory during execution

The code and the static data parts of the program address space were in essence prepared by the compiler and thus we speak of static memory allocation (or memory allocation at compile time or memory allocated by the compiler ) even though, strictly speaking, the compiler does not allocate any memory when the program is run. It may even be the case that, when a program is run, the compiler used to compile the program no longer exists. The size and structure of code and static data sections will not change during the execution of the program, though at various times they may be mapped into various segments of physical memory.

The curious reader may at this point have three questions.

1. Where is the variable i located in the physical memory?

2. What is the stack section pictured in Figure 2.6?

3. What is the dynamic data section pictured in Figure 2.6?

The rest of this chapter is devoted to answering these questions that deal with dynamic memory allocation.

Both C and C++ are recursive languages. We will discuss this in detail in Chapter 5, but for now suffice it to say that this allows a function to eventually call itself (it may be a direct call when a function A() calls the function A() , or an indirect call when a function A() calls a function B() that calls a function C() ... that calls the function A() ). There is a certain penalty to be paid in speed of execution and memory requirements for facilitating recursion, but it is more than balanced out by the problem-solving power gained . The memory role in recursion is what interests us, bringing us to the program system stack and dynamic memory allocation.

Very often a running program requires more memory than anticipated during its design or even when its execution begins. Take, for example, a simple program that repeatedly prompts the user for a word and then stores the word in the memory until the user enters quit . Nobody can anticipate how much memory will be required. Thus, programs in general need the ability to request and obtain more memory dynamically - that is, during the program's execution. We will discuss the details of dynamic allocation and deallocation in Chapter 4, but for now we simply state that the section marked as "dynamic data" in the address space of a program (see e.g. Figure 2.6) can be increased to accommodate the requested increase in memory (using high logical addresses from the unused logical address space) and properly mapped to the physical memory, as illustrated in Figure 2.8. This memory allocation is managed by the program memory manager (which basically is the C allocator malloc() or the C++ allocator new ).

Figure 2.8: Dynamic memory allocation

When a function is called, an activation frame (or activation record )is dynamically created (i.e., the required memory is dynamically allocated using low addresses of the unused logical address space and the required data are stored in it) and pushed on the stack. (Simply stated, a stack is a data structure resembling a deck of cards: you can only put a new card on the top of the deck, which is called operation push, or remove the top card from the deck, which is called operation pop .) The activation frame of the function is its "address space", and all local automatic variables are "located" there. That is why the variable i in our sample program has not figured in our discussion so far. It is located in - and is part of the activation frame for - the function main() . The compiler translates the symbolic references of the variable i to address references relative to the beginning of the activation frame. Thus, when a function is called many times, there will be many unrelated activation frames on the stack for that function and hence many unrelated copies of the local variables of that function.

We conclude with a short note: For the purist, a program in execution is usually called a process. Therefore, it would be more precise to talk of "process address space", "process memory management", and a "process system stack". We will use such proper terminology in later chapters, but in this introductory chapter we really wanted to focus on what happens to a program and did not wish to sidetrack a reader not well versed in operating system terminology. For the sake of simplicity, we will often refer to the "system stack" instead of the "process system stack".