Mapping the program counter back to the function name in your code

Compilers are commonly used to convert human-readable source code into a series of instructions that are directly executed by the computer. A common question is "How do the debuggers and error handlers report the place in the source code where the processor is currently at?" There are various methods to map instructions back to locations in the source code. With the compiler optimizing the code, there are also some complications in mapping the instructions back to the source code. This first article in the series describes how tools map the program counter (also known as the instruction pointer) back to the function name. Subsequent articles in this series will cover mapping the program counter back to the specific line in a source file. It also provides a backtrace describing the series of calls that resulted in the processor being in the current function.

The function entry symbols

When translating source code into an executable binary, the compiler keeps symbol information about the entry to each function. Keeping this information available makes it possible for the linker to assemble multiple object files (.o suffix) into a single executable file. Before the object files are processed by the linker, the final addresses of functions and variables are not known. The object files have placeholders for the symbols that do not yet have addresses. The linker will resolve the addresses when creating the executable. Assuming that the resulting executable is not stripped, those symbols describing the entry of each function are still available. You can see an example of this by compiling the following simple program:

#include <stdlib.h>
#include <stdio.h>

int a;
double b;

int
main(int argc, char* argv[])
{
	a = atoi(argv[1]);
	b = atof(argv[2]);
	a = a + 1;
	b = b / 42.0;
	printf ("a = %d, b = %f\n", a, b);
	return 0;
}

Compile the code:

$ gcc -O2 example.c -o example

You can see where the main function starts at 0x401060 with the following command:

$ nm example |grep main
U __libc_start_main@GLIBC_2.34
0000000000401060 T main

Even though the code is compiled without debugging information (-g option), gdb can still find the start of the main function with the symbol information:

$ gdb example

GNU gdb (GDB) Fedora 12.1-1.fc36
…
(No debugging symbols found in example)
(gdb) break main
Breakpoint 1 at 0x401060

Step through the code with the GDB nexti command. GDB reports the address it is currently at in the main function:

(gdb) nexti
0x0000000000401061 in main ()
(gdb) nexti
0x0000000000401065 in main ()
(gdb) where
#0 0x0000000000401065 in main ()

This minimal information is useful but is not ideal. The compiler can optimize functions and split functions into non-contiguous sections to make code associated with the function not obviously tied to the listed function entry. A portion of the function's instructions might be separated from the function entry by other functions' entries. Also, the compiler may generate alternative names that do not directly match the original function names. This makes it more difficult to determine which function in the source code the instructions are associated with.

DWARF information

Code compiled with the -g option includes additional information to map between the source code and the binary executable. By default RPMs with code compiled on Fedora have the debug information generation enabled. Then this information is put into a separate debuginfo RPM, which can be installed as a supplement to the RPMs containing the binaries. This makes it easier to analyze crash dumps and debug programs. With debuginfo, you can get address ranges that map back to particular function names. It also provides the line number and file name that each instruction maps back to. The mapping information is encoded in the DWARF standard.

The DWARF function description

For each function with a function entry there is a DWARF Debug Information Entry (DIE) describing it. This information is in a machine-readable format, but there are a number of tools including llvm-dwarfdump and eu-readelf that produce human-readable output of the DWARF debug information. Below is the llvm-dwarfdump output of the example main function DIE describing the main function of the earlier example.c program.

The DIE starts with the DW_TAG_subprogram to indicate it describes a function. There are other kinds of DWARF tags used to describe other components of programs such as types and variables.

The DIE for the function has multiple attributes each starting with DW_AT_ that describe the characteristics of the function. These attributes provide information about the function, such as where the function is located in the executable binary. It also points where to find it in the original source code.

A few lines down from the DW_TAG_subprogram is the DW_AT_name attribute that describes the source code function name as main. The DW_AT_decl_file and DW_AT_decl_line DWARF attributes describe the file and line number respectively where the function came from. This allows the debugger to find the appropriate location in a file to show you the source code associated with the function. Column information is also included with the DW_AT_decl_column.

The other key pieces of information for mapping between the binary instructions and the source code are the DW_AT_low_pc and DW_AT_high_pc attributes. The use of the DW_AT_low_pc and DW_AT_high_pc indicates that the code for this function is contiguous, ranging from 0x401060 (the same value as provided by nm command earlier) up to but not including 0x4010b7. The DW_AT_ranges attribute is used to describe functions if the function covers non-contiguous regions.

With the program counter, you can map the processor's program counter to the function name and find the file and line number where the function is:

$ llvm-dwarfdump example --name=main
example:	file format elf64-x86-64

0x00000113: DW_TAG_subprogram
              DW_AT_external	(true)
              DW_AT_name	("main")
              DW_AT_decl_file	("/home/wcohen/present/202207youarehere/example.c")
              DW_AT_decl_line	(8)
              DW_AT_decl_column	(0x01)
              DW_AT_prototyped	(true)
              DW_AT_type	(0x00000031 "int")
              DW_AT_low_pc	(0x0000000000401060)
              DW_AT_high_pc	(0x00000000004010b7)
              DW_AT_frame_base	(DW_OP_call_frame_cfa)
              DW_AT_call_all_calls	(true)
              DW_AT_sibling	(0x000001ea)

Inlined functions

A compiler can optimize code by replacing a call to another function with instructions that implement the operations of that called function. An inlined function eliminates control flow changes caused by function call and return instructions to implement the traditional function calls. For an inlined function, there is no need for executing additional function prologue and epilogue instructions required to conform to the Application Binary Interface (ABI) of traditional function calls.

Inline functions also provide additional opportunities for optimizations as the compiler can intermix instructions between the caller and the inlined invoked function. This provides a complete picture of what code can safely be eliminated. However, if you just used the address ranges from the real functions described by the DW_TAG_subprogram, then you might misattribute an instruction to the function that called the inlined function, rather than the actual inlined function containing it. For that reason, DWARF has the DW_TAG_inlined_subroutine to provide information about inlined functions.

Surprisingly, even example.c, the simple example provided in this article, has inlined functions in the generated code, atoi and atof. The code block below shows the output of llvm-dwarfdump for atoi. There are two parts, a DW_TAG_inlined_subroutine to describe each place atoi was actually inlined and a DW_TAG_subprogram describing the generic information that does not change between the multiple inlined copies.

The DW_AT_abstract_origin in the DW_TAG_inlined_subroutine points to the associated DW_TAG_subprogram that describes the file with DW_AT_decl_file and DW_AT_decl_line just like a DWARF DIE describing a regular function. In this case, you see that this inlined function is coming from line 362 of system file /usr/include/stdlib.h.

The actual range of addresses that are associated with atof is non-contiguous and described by DW_AT_ranges, [0x401060,0x401060), [0x401061, 0x401065), [0x401068,0x401074), and [0x40107a,0x41080). The DW_TAG_inlined_subroutine has a DW_AT_entry_pc to indicate what location is considered to be the start of the inlined function. With the compiler reordering instructions it may not be obvious what would be considered the first instruction of an inlined function:

$ llvm-dwarfdump example --name=atoi
example:	file format elf64-x86-64

0x00000159: DW_TAG_inlined_subroutine
              DW_AT_abstract_origin	(0x00000208 "atoi")
              DW_AT_entry_pc	(0x0000000000401060)
              DW_AT_GNU_entry_view	(0x02)
              DW_AT_ranges	(0x0000000c
                 [0x0000000000401060, 0x0000000000401060)
                 [0x0000000000401061, 0x0000000000401065)
                 [0x0000000000401068, 0x0000000000401074)
                 [0x000000000040107a, 0x0000000000401080))
              DW_AT_call_file	("/home/wcohen/present/202207youarehere/example.c")
              DW_AT_call_line	(10)
              DW_AT_call_column	(6)
              DW_AT_sibling	(0x00000196)

0x00000208: DW_TAG_subprogram
              DW_AT_external	(true)
              DW_AT_name	("atoi")
              DW_AT_decl_file	("/usr/include/stdlib.h")
              DW_AT_decl_line	(362)
              DW_AT_decl_column	(0x01)
              DW_AT_prototyped	(true)
              DW_AT_type	(0x00000031 "int")
              DW_AT_inline	(DW_INL_declared_inlined)

Implications of inline functions

Most programmers think of the processor completely executing one line in the source code before moving on to the next. Similarly, with the expected function call ABI  programmers think of where the caller function completes operations in the statements before the call and statements after the call are not started until the callee function return may not hold. With inlined function, the boundaries between functions become fuzzy. Instructions from the caller function may be scheduled before or after the instructions from the inlined functions regardless of where they were in the source code if the compiler determines that the final result will be the same. This may lead to unexpected values when inspecting variables before and after the inlined functions.

Further reading

This article covers a very small part of how the mapping between source code and the executable binary is implemented with DWARF. As a starting point to learn more about DWARF, you might read Introduction to the DWARF Debugging Format by Michael J. Eager. Look for upcoming articles about how the instructions in the functions are mapped back to the source code and how backtraces are generated.