Stack Trace

A stack trace is debugging output, normally sent to a log file or a debug window that shows the hierarchy of callers that called the current function. A stack trace is generated by analysing the stack to find each stack frame. The addresses of the functions called can be retrieved from each stack frame and the names of the functions displayed.

To implement a stack trace you have to know the structure of the stack frames, which is shown in the article Stack for X86 CDECL.

Walking the stack

Often a stack trace is written in assembly as it involves finding the current value of the EBP register. To write a stack trace routine in a higher-level language you will need to find EBP. This can be done by finding the address of an object in a known location on the stack or by using __builtin_frame_address(0) if you use the GCC compiler. One thing we always know is in a fixed location on the stack is the first argument to the current function. Taking the address of this argument gives us the value of the EBP plus 8 bytes. On some platform (e.g. x86), the compiler does not necessary save the EBP on the stack. For example, for gcc, use the -fno-omit-frame-pointer to make sure that the EBP is saved.

The following C++ code shows how (given the existence of a Trace function) this can be used to walk up the stack:

void Debug::TraceStackTrace(unsigned int MaxFrames)
{
    // Stack contains:
    //  Second function argument
    //  First function argument (MaxFrames)
    //  Return address in calling function
    //  EBP of calling function (pointed to by current EBP)
    unsigned int * ebp = &MaxFrames - 2;
    Trace("Stack trace:\n");
    for(unsigned int frame = 0; frame < MaxFrames; ++frame)
    {
        unsigned int eip = ebp[1];
        if(eip == 0)
            // No caller on stack
            break;
        // Unwind to previous stack frame
        ebp = reinterpret_cast<unsigned int *>(ebp[0]);
        unsigned int * arguments = &ebp[2];
        Trace("  0x{0:16}     \n", eip);
    }
}

Note that the above code requires a NULL return address, and GDB backtracing requires a NULL %ebp, to know when to stop. Otherwise the traces will run off into garbage. To account for this, set up a NULL stack frame before you jump to your C entry point:

mov $stack_end, %esp ; Initialize %esp
...
xor %ebp, %ebp       ; Set %ebp to NULL
push %ebp            ; Push a NULL return address to the stack
jmp kmain            ; According to calling convention, kmain will save %ebp (=NULL) to the stack

With this, stack tracers will see the NULL %ebp and/or return address as the end of the trace. You can use call in place of push/jmp, but your tracer will need to check for a NULL %ebp, rather than a NULL return address.

Assembly Implementation

This assembly implementation for x86 uses the same algorithm as above and similarly relies on a NULL return address to be placed near the top of the stack. Rather than print the contents of the stack, however, it builds an array of addresses which can then be resolved into symbol names.

; Walks backwards through the call stack and builds a list of return addresses.
; Args:
;  * Array of 32-bit addresses.
;  * Maximum number of elements in array.
; Return value: The number of addresses stored in the array.
; Calling convention: cdecl
[global walk_stack]
walk_stack:
    ; Create stack frame & save caller's EDI and EBX.
    push ebp
    mov  ebp,       esp
    mov  [ebp - 4], edi
    mov  [ebp - 8], ebx
    ; Set up local registers.
    xor  eax,       eax         ; EAX = return value (number of stack frames found).
    mov  ebx,       [esp +  0]  ; EBX = old EBP.
    mov  edi,       [esp +  8]  ; Destination array pointer in EDI.
    mov  ecx,       [esp + 12]  ; Maximum array size in ECX.
.walk:
    ; Walk backwards through EBP linked list, storing return addresses in EDI array.
    mov  edx,       [ebx +  4]  ; EDX = previous stack frame's IP.
    test edx,       edx
    jz   .done                  ; Leave if it is 0.
    mov  ebx,       [ebx +  0]  ; EBX = previous stack frame's BP.
    mov  [edi],     edx         ; Copy IP.
    add  edi,       4
    inc  eax
    loop .walk
.done:
    ; Restore caller's EDI and EBX, leave stack frame & return EAX.
    mov  edi,       [ebp - 4]
    mov  ebx,       [ebp - 8]
    mov  esp,       ebp
    pop  ebp
    ret

Resolving Function Names

The next step in producing meaningful output from a stack trace is to find the names of the functions containing the addresses found during the stack walk.

When looking up the name of a function you have to find the biggest address smaller than the value you are looking for. This is because the return address saved by the call is the address of the jsr instruction, which will be offset within the function that is making the call.

To get the information you need to lookup function names you will need to either include debugging symbols in your kernel or load the map file created by your linker into the kernel's memory space. The map file shows the addresses of each of your functions. While you could include the entire map file, it is often quite large and inefficiently stored. Not only this but often functions are not listed in the order that they appear in the object file and the format is not amenable to tracing through to find a specific function.

One possible solution is to pre-process your map file to produce a smaller, more useful format for it. You could do this in a way that allows either binary or linear searching for a particular address. See NobleTech's Web site[1] for C# code showing a way of reading the map file produced by GNU ld and outputting a binary file that allows more efficient linear searching for symbols. A binary Win32 console application to do the pre-processing is also available for free from that site. C++ code that can be used in your kernel to look up function names in the pre-processed file format is also shown.