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. 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.

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);
    }
}

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.