Stack frame iterator

[wks]

Problem

The current stack introspection/OSR API is inefficient.

It selects a frame by a number. For example:

ctx->cur_func(ctx, stack, 1);
ctx->cur_func_ver(ctx, stack, 2);
ctx->cur_inst(ctx, stack, 3);
ctx->dump_keepalives(ctx, stack, 4, &values);

A real-world implementation may need to unwind the stack from the top, one frame at a time, until reached the frame. If the client needs to traverse through stacks of many frames, the O(n^2) complexity may be a performance bottleneck. One application is to use the Client API (or the equivalent Mu IR (common) instructions) to generate the stack trace for exception handling.

This link shows a real-world Java stack trace: https://ptrthomas.wordpress.com/2006/06/06/java-call-stack-from-http-upto-jdbc-as-a-picture/ Or click here: jtrac-callstack.pdf

EDIT: well, this is a call graph, not a stack trace. But imagine something goes wrong in JDBC...

Desired API

The API should provide a "frame cursor" data type, which refers to a frame in a stack. It can be generated for a stack, and iterate through its frames from top to bottom.

The introspection API cur_func, cur_func_ver, cur_inst and dump_keepalives will work on this "cursor" instead of a stack and a number.

The OSR API pop_frame, can, instead of popping one frame at a time, pop all frames above a particular "cursor". Preliminary experiments show that this is possible with C programs and libunwind.

The "frame cursor" type

The "frame cursor" type shall be an opaque reference to a Mu frame a cursor. The cursor holds the context of a "current frame", and can move down to the parent frame.

It must be platform-independent.

It could potentially be large (given the number of registers in a CPU). Therefore it is desirable to be mutable – making a fresh copy for each frame would be costly (Haskell programmers may disagree).

There are some subtle interactions between it and the GC. GC may modify references on the stack, but the API must hide this detail from the client. So the API should not expose raw CPU

The cursor may be allocated on the Mu heap, but also may not.

The cursor is only valid when the stack is still unbound. As soon as the stack is bound again, the stack may change in any ways and the cursor is invalidated.

So I can think of some possible solutions:

1. Create a new type frameref, like our existing threadref and stackref. Create a new type framecursor. It has reference semantics: it refers to a mutable structure internally held by the Mu VM.
   • pro: A dedicated opaque type, the cleanest model.
   • con: A new primitive type, pointing to a large structure, just for introspection? Well... maybe not that bad.
   • choices: Is it managed by the GC? GC is the easiest way, but we may not be able to print stack trace for OutOfMemoryException. (really? I am not sure) Alternatively it may be required to be closed explicitly.
2. Use ref<void> for the "cursor" type. Its content is allocated on the heap, opaque to the client, and may be platform-specific. When invalidated, the object remains live, but the content becomes invalid.
   • pro: No new types introduced
   • con: This implies the data content is on the Mu heap.
   • con: The GC must have special knowledge of such a heap object, which is not a regular Mu object.
3. Use ptr<void>. Similar to ref<void>, but implies it is not GC-ed.
   • pro, con: same as ref<void>

Example Mu API

This example prints a stack trace on Mu.

// This trap handler prints the stack trace.
void stack_printing_trap_handler(
        MuCtx *ctx,                     // Equivalent to JNIEnv
        MuThreadRefValue thread,        // The current thread
        MuStackRefValue stack,          // The current stack
        int wpid,                       // Watchpoint ID. 0 for ordinary traps.
        MuTrapHandlerResult *result,    // How the Mu thread should resume?
        MuStackRefValue *new_stack,     // Which stack shall the Mu thread bind to? Usually the old stack.
        MuValue *values, int *nvalues,  // What values shall be passed on the stack?
        MuRefValue *exception,          // What exception shall be thrown on that stack?
        MuCPtr userdata) {              // Client-specific data

    ClientCompiler *clientCompiler = (ClientCompiler*) userdata; // The client-specific compiler.

    // Get a cursor to the top of the stack.
    MuFrameCursorValue *cursor = ctx->get_stack_cursor(ctx, stack);

    // Iterate through.
    int func_id;
    while((func_id = ctx->cur_func(ctx, cursor)) != ID_OF_MY_STACK_BOTTOM_FUNC) {
        if (func_id == 0) { // func_id == 0 means the frame is a native frame.
            printf("This frame is native");
        } else {    // It is a Mu frame.
            // Get the ID of the current Mu instruction.
            int inst_id = ctx->cur_inst(ctx, cursor);

            // The client looks up the source-level information.
            SourcePosition sp = clientCompiler->getSourcePosition(inst_id);
            printf("File: %s, Function: %s, Line: %d, Column: %d: %d\n",
                    sp.file, sp.func, sp.line, sp.column);
        }
    }
    printf("End of stack trace\n");

    // Close the cursor. (Alternatively let the GC close the cursor.)
    ctx->close_cursor(ctx, cursor);

    // We want to return to the old stack and continue normally,
    *new_stack = stack;
    // but do not pass any values.
    *nvalues = 0;
    // Continue normally (not throwing exception).
    return MU_REBIND_PASS_VALUES. // passing 0 values
}

Existing approaches

libunwind is a portable way to walk stack frames in the C language. There are different implementations on different platforms (OSX has its own implementation), but the API is the same.

unw_getcontext creates a unw_ucontext_t structure for the current stack. unw_init_local creates a unw_cursor_t on the context. Then the user can call unw_step on the cursor to step through stack frames. unw_get_reg gets the value of a machine register from a cursor. The cursor keeps the state of registers (usually it is only able to recover callee-saved registers) at the resumption points (return addreses) of frames.

Example:

#define UNW_LOCAL_ONLY
#include <libunwind.h>

void show_backtrace (void) {
  unw_cursor_t cursor; unw_context_t uc;
  unw_word_t ip, sp;

  unw_getcontext(&uc);
  unw_init_local(&cursor, &uc);
  while (unw_step(&cursor) > 0) {
    unw_get_reg(&cursor, UNW_REG_IP, &ip);
    unw_get_reg(&cursor, UNW_REG_SP, &sp);
    printf ("ip = %lx, sp = %lx\n", (long) ip, (long) sp);
  }
}