6.2 Call stacks and symbol tables

As stated in the section on stack memory allocations (see Stack memory allocations), when a function is called, a copy of the caller's state information (including local variables and registers) is saved on the stack so that it can be restored when the called function returns. On many operating systems there is a calling convention¹ which defines the layout of such stack entries so that code compiled in different languages and with different compilers can be intermixed. This usually specifies at which stack offsets the stack pointer, program counter and local variables for the calling function can be found, although on some processor architectures the function calling conventions are specified by the hardware and so the operating system must use these instead.

On systems that have consistent calling conventions, it is usually possible to perform call stack tracebacks from within the current function in order to determine the stack of function calls that led to the current function. This is extremely useful for debugging purposes and is done by examining the current stack frame to see if there is a pointer to the previous stack frame. If there is, then it can be followed to find out all of the state information about the calling function. This can be repeated until there are no more stack frames². This is generally how this information is determined by debuggers when a call stack traceback is requested.

In addition to the pointer to the previous stack frame, the saved state information also always contains the saved program counter register, which contains either the address of the instruction that performed the function call, or the address of the instruction at which to continue execution when the called function returns³. This information can be used to identify which function performed the call, since the address of the instruction must lie between the start and end of one of the functions in the process.

There are several different ways to perform stack unwinding. The first requires compiler support and uses builtin functions to determine the next stack frame and the return address. The GNU C compiler, gcc, supports this but unfortunately the number of stack frames to traverse must be known at compile-time rather than run-time. The second method uses the glibc backtrace() function to perform the stack traversal but has a finite limit on the number of stack frames that can be traversed and does not return any frame pointers. The third method requires operating system support, with a library of routines provided to perform call stack traversal. Unfortunately, such routines can be quite time consuming and may require a lot of resources, but on the other hand they are likely to be very reliable at obtaining the necessary information. There is also support for using the libunwind library instead of such operating system libraries, which will be valuable as libunwind gradually supports more processor architectures. The mpatrol library can be built to support any of these methods, with the MP_BUILTINSTACK_SUPPORT, MP_GLIBCBACKTRACE_SUPPORT, MP_LIBRARYSTACK_SUPPORT and the MP_LIBUNWIND_SUPPORT preprocessor macros.

A fourth way to perform stack unwinding involves reading (or effectively disassembling) the instructions that are being executed in order to determine the size of the stack frame being used and the address of the instruction at which execution will resume when the function returns. This can also be quite a reliable method of obtaining call stack information but is only likely to be feasible on a processor architecture which has a very simple instruction set, such as a RISC⁴ architecture. MIPS processors are a good example of this.

The final method of stack unwinding requires that the frame pointer and return address are both stored on the stack whenever a new function is called. The chain of frame pointers can then be followed down the stack, and the return addresses can be read at a given offset from the frame pointers. This is usually possible with CISC⁵ processor architectures that have dedicated call instructions which automatically save such information on the stack, although some RISC processors also save these as well. However, inline functions and compiler optimisations can sometimes result in the frame pointer being omitted, usually resulting in an inability to walk the stack.

However, in order to determine this symbolic information, it must be possible to find out where the start and end addresses of all of the functions in the process are. This can usually only be read from object files, since they contain the symbol tables that were used by the linker to generate the final executable file for the program. The object file's symbol tables normally contain information about the start address, size, name and visibility of every symbol that was defined, but this depends on the format of the object file and if the symbol tables have been stripped from the final executable file.

If the object file was created by a compiler then it may also contain debugging information that was generated by the compiler for use with a debugger. Such information may include a mapping of code addresses to source lines⁶, and this information can be used by the mpatrol library to provide more meaningful information in call stack tracebacks.

On systems that support shared libraries, additional work must be done to determine the symbolic information for all of the functions which have been defined in them. The symbols for functions that are defined in shared libraries normally appear as undefined symbols in the executable file for the program and so must be searched in the system in order to get the necessary information. It is usually necessary to liaise with the dynamic linker⁷ on many systems.