while (2): compilers | Just Another Computer Science Blog

Home » Posts filed under compilers

Recursion And Stack Overflow

Few days ago, the Twitter account of StackOverflow (the famous site of technical questions and answers) has published the following tweet:

int main() { return main(); } pic.twitter.com/SfQv6E8wht
— Stack Overflow (@StackOverflow) 22 Luglio 2015

The intention was to recall the name of the site by presenting a situation that every developer has been warned about.

Of course I got the pun but a light bulb has turned on in my mind: tail calls. Some years ago I've read something about it on the blog of Gustavo Duarte: Tail Calls, Optimization, and ES6.

Do It Yourself

It's not that I don't trust Gustavo, but I've tried to do my own test (on x86-64bits with gcc 4.8):

#include <stdio.h>

int main()
{
        fprintf(stderr, "Go!\n");
        return main();
}

Compiled with the optimization enabled:

gcc -O2 -o so so.c

Launching the executable so (that stands for stack overflow), it prints a never ending series of "Go!", without crashing. The explanation is exactly the same Gustavo presented in his old post: the compiler optimizes this call with a jump. So basically it transforms a recursion in a loop. This is clear looking at the disassembled code, with the following command:

objdump -d so

This is the result (leaving only the interesting part):

0000000000400480 <main>:
  400480:   48 83 ec 08            sub    $0x8,%rsp
  400484:   0f 1f 40 00            nopl   0x0(%rax)
  400488:   48 8b 0d b1 0b 20 00   mov    0x200bb1(%rip),%rcx   # 601040 <__TMC_END__>
  40048f:   ba 04 00 00 00         mov    $0x4,%edx
  400494:   be 01 00 00 00         mov    $0x1,%esi
  400499:   bf 14 06 40 00         mov    $0x400614,%edi
  40049e:   e8 cd ff ff ff         callq  400470 <fwrite@plt>
  4004a3:   eb e3                  jmp    400488 <main+0x8>

As you can see, fprintf is mapped with a callq to fwrite, while the recursion is made by the instruction jmp

Conclusions

Basically there are three considerations that can be done:

Gustavo was right;
compilers are smarter than you think;
the same thing I've wrote about goto and do-while loops apply also for recursion.

Image taken from Wikimedia Commons (public domain).

C, compilers, development, stackoverflow Sunday, July 26, 2015 No comments

How C Compilers Work Part 4: Linker

Now we are at the point where we have produced one or more object files and we want to create an executable. Under GNU/Linux systems, this job is done by ld, the GNU linker.

As seen in the previous part, the compiler always works on one file at once, so, every time there is the need to access a symbol (function or variable) defined somewhere else, a reference is used. The first work of the linker is to check the correctness of all these references.

ELF layout

Once this operation has ended successfully, it's time to produce the executable. To do this, all the object files are split into their basic components which are reassembled according to the ELF format. For example, all the fixed strings go in the string table, the names of the used symbols in the symbol table, etc.

This also happens to static libraries (that are just a set of object files packed in an archive) and shared objects if the flag -static has been specified.

In case of dynamic linking (that happens 99% of the times), the linker appends:

a section called dynamic symbol table (.dynsym) containing the names of the external symbols, and
a section called simply .dynamic that, among other things, contains also the name of the shared objects needed at runtime.

When the process will be executed, the dynamic linker will append to the process image the images of the shared objects listed in the .dynamic section (but this is a different story).

Troubleshooting

"Undefined reference" is the most common error that you can get. It means that a function or a variable defined as extern has not been found. The most common case is a typo or a missing shared object.

When working with multiple toolchains or different versions of a shared object, it may happen that the linker signals errors for undefined references even if everything seems correct. This happens because the reference to the symbol (usually added by a .h file) does not match what's inside the shared object being linked. Or, to say it in other words, the shared object the linker is referring to, is not consistent with the header file that has been included. A solution is to check the path of the header and the library (flags -I and -L in gcc).

Another sneaky error may appear when a program is executed in a system different from the one where it has been created. The message usually shown is the pretty misleading "No such file or directory". But the message is absolutely correct, a file is missing (or it's in an unexpected location). The missing file is a dynamically linked shared object. To check which one is, you have to use readelf.

$ readelf -d <process_name>

The first rows show the names of the needed shared objects. Now you only have to make sure they are present in your system. If you are able to find them but you get the same error, try to specify additional paths for them.

How C Compilers Work Part 3: Compiler

The properly so called compiler is a really complicated piece of software. It performs many different tasks on single files. This means that no matter if your project is made of thousand source files: they will be compiled one by one.

Now let's see the common operations. First of all, it does a lexical and syntax analysis over the code. Many of the errors about missing semicolons and misspelled variables will be caught here. For functions there is a small caveat. According to C standard, if a function has not been declared, the compiler assumes that:

it exists in some other file of your project, linked library or common library (such as libc), and
it returns an integer value.

This will lead to warnings like this:

warning: implicit declaration of function ‘fprintf’ [-Wimplicit-function-declaration]
        fprintf(stderr, "Error! Expected %d param\n", ARGS);

or this:

warning: initialization makes pointer from integer without a cast
        char *token = strtok(my_string, "/");

To remove them, you just have to add the declaration of the functions you are using, by including the right header file.

Other things that the compiler checks:

types of variables in assignments;
type and number of parameters of called functions must match the corresponding prototypes (usually declared in header files included by the preprocessor);
const variables and parameters have to remain untouched.

Another important task that is performed is the optimization. This task can improve your code mainly in two ways: increasing the speed or reducing the size of the final output. There are many things that can be done to achieve one of these goals. GCC, for example, has lots of options to let you do a fine tuning but, in the end, the more used are -O2 (to optimize for speed) and -Os (to optimize for size).

Eventually, the compiler produces a binary file (often called object file) full of references to unknown things. To make those things known is the job of the linker.

How C Compilers Work Part 2 - Preprocessor

As said in the previous post, in modern compilers, preprocessing is not a separate phase but it's made together with compilation. Nevertheless, understanding the role of preprocessor is really helpful. The first thing to say is that it basically understands only rows that start with character hash (#).

In a standard program, those rows specifies header files to include and constants/macro to substitute in the rest of the file. Another frequent used feature is the conditional compilation (#if, #ifdef, etc.) to enable some part of code only if a condition is met at compile time. In this case the flag -D of GCC can be really useful.

A strange thing is the #pragma directive, used to issue commands directly to the compiler, in some cases to enable some vendor specific option. Other directives commonly used are #warning and #error; they force the compiler to present a warning or an error in special situations (usually depending on which other files are included or not included in the project).

An Example

Now let's see what a preprocessor does. Look at this simple program:

#include <stdio.h>
#include <string.h>

#define ARGS    1
#define TEST    "test_arg"

/* Main function */
int main (int argc, char **argv)
{
        if (argc != ARGS + 1) {
                fprintf(stderr, "Error! Expected %d param\n", ARGS);
                return 1;
        }

        if (strcmp(argv[1], TEST) != 0) {
                fprintf(stderr, "Error! Expected %s\n", TEST);
                return 2;
        }

        fputs("OK!\n", stdout);
        return 0;
}

Now if you compile it with:

gcc -Wall -E -o main_pp.c main.c

you'll get another C file named main_pp.c as a result (the flag -E tells GCC to only execute the preprocessor). If you don't have a compiler available, you can look at it here. Pretty big, isn't it?

What you should notice is that #include and #define directives have been processed and the comment has been removed. This obviously helps the programmer but basically almost all the work done by the preprocessor can be bypassed. In other words, the preprocessor is not indispensable. If you compile the following piece of code, you'll notice no differences in program execution compared to the original one.

typedef struct foo FILE;
FILE *stdout;
FILE *stderr;

int fprintf(FILE*, char*, ...);
int fputs(char*, FILE*);
int strcmp(const char*, const char *);

int main (int argc, char **argv)
{
        if (argc != 1 + 1) {
                fprintf(stderr, "Error! Expected %d param\n", 1);
                return 1;
        }

        if (strcmp(argv[1], "test_arg") != 0) {
                fprintf(stderr, "Error! Expected %s\n", "test_arg");
                return 2;
        }

        fputs("OK!\n", stdout);
        return 0;
}

How is this possible? How can it be that struct foo is a FILE? And what about other functions? For the answer, you'll have to wait the next two chapters of this series.

Troubleshooting

Usually preprocessor errors are easily understandable. For example:

failed.c:1:21: fatal error: missing.h

means that the header file missing.h does not exist or is not in the path. Another comprehensible error is the following:

failed.c:3:0: error: unterminated #ifdef

which remind us that an #endif is missing.

References

If you want to play with the above examples, source files are here.
A full explanation of the GCC preprocessor can be found at this page.
The idea for the second example has been taken from this blog post.

How C Compilers Work Part 1 - Introduction

I'm writing this series of posts because it seems to me that many young programmers lack a clear idea about what's behind the "Build" button on their IDE. In my opinion, this happens because nowadays the interpreted languages (such as JavaScript, Python or Lua) are perceived to be more fancy and cool to learn.

The truth is that many companies still use compiled languages like C and C++. This ends in several developers (some of them absolutely remarkable) that keep losing time to understand how to fix an "undefined symbol" error.

An Overview

Operating diagram of a C compiler

The main purpose of a C compiler is to generate a binary file starting from one or more C source files. The generated file may be an executable or a library but in every case it contains low level machine-code instructions that a processor can execute.

A C compiler (such as GCC) is made of three logical blocks: the preprocessor, the compiler properly so called and the linker. Each block performs a set of specific tasks and produces an output for the next block but for performances reasons, usually the first two are implemented together.

Just as a side note, the first C++ compilers were implemented as preprocessors for C compilers.