Mono Runtime Notes

April 13, 2009

Magic (of) Trampolines

Filed under: Uncategorized — Tags: , , , — kjambunathan @ 1:58 am

Magic (of) Trampolines

1 Magic (of) Trampolines

In this post I attempt to demystify what Trampolines are and how
they play a crucial role in achieving Just In Time Compilation on
Mono Runtime.

To keep things simple and understandable, let’s consider the high
level functionality of the Mono runtime as it goes about executing a
simple .NET binary – HelloWorld.exe.

The source for binary is HelloWorld.cs

   using System;

   class HelloWorld
   {
           public static void Main()
           {
               Console.WriteLine(13);
           }
   }

It is assumed that it is compiled to the equivalent HelloWorld.exe
with


           $ mcs HelloWorld.exe

and executed with

           $ mono HelloWorld.exe

The following operations take place in the Mono VM as it JIT
compiles and executes the CLR executable.

1.1 Compile ‘Main’

The entry point method of HelloWorld assembly – the Main method –
is compiled to native code. The code looks like this 1

   Main @0xb79f8270:

   0:   55                      push   ebp
   1:   8b ec                   mov    ebp,esp
   3:   83 ec 08                sub    esp,0x8
   6:   b8 0d 00 00 00          mov    eax,0xd
   b:   83 ec 0c                sub    esp,0xc
   e:   6a 0d                   push   0xd
   10:  e8 07 00 00 00          call   1c       /* call 0xb79f828c */
   15:  83 c4 10                add    esp,0x10
   18:  c9                      leave
   19:  c3                      ret

Note that at this point, the target of the call 0xb79f828c is not
to the method System.Console.WriteLine but to a runtime generated
code.

Let’s call the code The Specific Trampoline.

For brevity let’s designate the instruction location at offset 0x10
where a call is made, The Call Site.

1.2 Execute Main’s Native code.

During this process the control transfers to the Specific
Trampoline.

1.2.1 Execute Specific Trampoline

Specific Trampoline looks like this 2

   Specific Trampoline @0xb79f828c:

   0:  68 74 e8 2e 08          push   0x82ee874 /*   push MonoMethod * */
   5:  e9 92 cd 24 00          jmp    24cd9c    /*   jmp 0xb7c45028    */

Here a value 0x82ee874 is pushed on to the stack and control
unconditionally transfers to another target 0xb7c45028.

The value being pushed is pointer to method descriptor for
System.Console.WriteLine. It is of type MonoMethod *. (Note: The
value being pushed is specific to the method invoked at the call
site. This explains why the trampoline is a ‘specific’ one.)

The jump target is to another runtime generated code. Let’s call
this code Generic Jit Trampoline.

1.2.2 Execute Generic Jit Trampoline

At the point of entry to this trampoline the stack state is as
pictured below


          +-----------------+ <-- Top of Stack on entry
          |                 |     to Generic Jit Trampoline
          |       m         |
          |                 |
          |(MonoMethod *)   |
       ^  |                 |
       |  +-----------------+ <-- Top of Stack at entry
       |  |                 |     Specific Trampoline
       |  |                 |
       |  | Main + 0x15     |
       |  | (Return IP)     |
       |  |                 |
       |  +-----------------+
       |  |                 |
       |  |                 |
       |  |       13        |
          |(WriteLine Arg)  |
          |                 |
          +-----------------+


The Generic Jit Trampoline looks like this 3

   Generic Jit Trampoline aka Type-0 Trampoline  @0xb7c45028:

   0:   57                      push   edi
   1:   56                      push   esi
   2:   55                      push   ebp
   3:   54                      push   esp
   4:   53                      push   ebx
   5:   52                      push   edx
   6:   51                      push   ecx
   7:   50                      push   eax
   8:   83 ec 04                sub    esp,0x4

   b:   ff 74 24 28             push   DWORD PTR [esp+40]

   f:   55                      push   ebp
   10:  56                      push   esi
   11:  57                      push   edi
   12:  53                      push   ebx
   13:  54                      push   esp

   14:  83 04 24 40             add    DWORD PTR [esp],0x40
   18:  ff 74 24 3c             push   DWORD PTR [esp+60]
   1c:  e8 07 61 41 50          call   mono_get_lmf_addr
   21:  50                      push   eax
   22:  ff 30                   push   DWORD PTR [eax]
   24:  83 04 24 01             add    DWORD PTR [esp],0x1
   28:  89 20                   mov    DWORD PTR [eax],esp

   call_magic_trampoline:

   2a:  6a 00                   push   0x0
   2c:  ff 74 24 4c             push   DWORD PTR [esp+76]
   30:  ff 74 24 54             push   DWORD PTR [esp+84]
   34:  8d 44 24 34             lea    eax,[esp+52]
   38:  50                      push   eax    /* eax = MONO_TRAMPOLINE_JIT */
   39:  e8 ea 3b 49 50          call   mono_get_trampoline_func (eax) /* call mono_magic_trampoline */
   3e:  83 c4 10                add    esp,0x10

   41:  50                      push   eax   /* eax = Ptr to Compiled Method */
   42:  e8 c1 d5 4e 50          call   mono_thread_force_interruption_checkpoint
   47:  58                      pop    eax

   48:  5b                      pop    ebx
   49:  83 eb 01                sub    ebx,0x1
   4c:  5f                      pop    edi
   4d:  89 1f                   mov    DWORD PTR [edi],ebx
   4f:  5e                      pop    esi
   50:  5e                      pop    esi

   51:  5b                      pop    ebx
   52:  5f                      pop    edi
   53:  5e                      pop    esi
   54:  5d                      pop    ebp

   55:  83 c4 04                add    esp,0x4

   thrust_method_ptr_into_stack:

   58:  89 44 24 24             mov    DWORD PTR [esp+36],eax

   5c:  8b 4c 24 08             mov    ecx,DWORD PTR [esp+8]
   60:  8b 54 24 0c             mov    edx,DWORD PTR [esp+12]
   64:  83 c4 24                add    esp,0x24
   67:  c3                      ret

Leaving aside the nitty gritties of the above code, let’s pay
specific attention to 2 instructions at offsets 0x39 and
0x58. These instructions correspond to

  1. Invocation of Magic Trampoline
  2. Post processing with Magic Trampoline’s return value

1.2.2.1 Invocation of Magic Trampoline

Unlike the Specific and Generic Trampolines mentioned
above, this trampoline is implemented in C.

In the context of this example, the magic trampoline does
the following magic:

    gpointer
    mono_magic_trampoline (gssize *regs, guint8 *code, MonoMethod *m, guint8* tramp)
    {
       gpointer addr;
       MonoJitInfo *ji;


       addr = mono_compile_method (m);
       ji = mono_jit_info_table_find (mono_domain_get (), (char*)code);

       mono_arch_patch_callsite (ji->code_start, code, addr);

       return addr;
    }

There are 3 distinct operations performed here

  1. Compile System.Console.WriteLine
  2. Patch the Call Site
  3. Return a function pointer to System.Console.WriteLine

1.2.2.1.1 Compile System.Console.WriteLine

Firstly WriteLine is compiled to native code. Variable addr
above is a pointer to native WriteLine method.

     System.Console.WriteLine @0xb79f8298:

      0:  55                      push   ebp
      1:  8b ec                   mov    ebp,esp
      3:  83 ec 08                sub    esp,0x8
      6:  e8 1d 00 00 00          call   28 <System_Console_WriteLine__int__0xb79f8298+0x28>
      b:  8b 05 50 ce 02 00       mov    eax,DWORD PTR ds:0x2ce50
     11:  83 ec 08                sub    esp,0x8
     14:  ff 75 08                push   DWORD PTR [ebp+8]
     17:  50                      push   eax
     18:  8b 00                   mov    eax,DWORD PTR [eax]
     1a:  ff 90 b8 00 00 00       call   DWORD PTR [eax+0xb8]
     20:  83 c4 10                add    esp,0x10
     23:  c9                      leave
     24:  c3                      ret
1.2.2.1.2 Patch ‘The Call Site’

Patch the Call Site in Main. With this the call to Specific
Trampoline at offset Main + 0x10 is replaced with a call to
WriteLine method.

At this point in time, the Main method is compiled wholly to
it’s native form and all references to trampoline call is
removed. (Theoretically) all future invocations of the method
directly land up in WriteLine method.

     (After patching)
     Main @0xb79f8270:

      0:  55                      push   ebp
      1:  8b ec                   mov    ebp,esp
      3:  83 ec 08                sub    esp,0x8
      6:  b8 0d 00 00 00          mov    eax,0xd
      b:  83 ec 0c                sub    esp,0xc
      e:  6a 0d                   push   0xd
     10:  e8 07 00 00 00          call   28       /* call 0xb79f8298 */
     15:  83 c4 10                add    esp,0x10
     18:  c9                      leave
     19:  c3                      ret
1.2.2.1.3 Return a pointer to the compiled method

The control now returns to the Specific Jit Trampoline. The
pointer to WriteLine method is returned in eax register.

1.2.2.2 Post processing with Magic Trampoline’s return value

The key action happens at offset 0x58 in Specific Jit Trampoline.

Here the register eax points to the native version of
Console.WriteLine. This is written in to the stack where the
‘Return IP’ is stored.

The net effect is that When Specific Jit Trampoline executes th e
‘ret’ instruction the control is transferred to the WriteLine
method. Furthermore, the state of the stack at this invocation of
WriteLine is exactly as though no magic ever happened.


          +-----------------+ <-- Top of Stack just prior to 'ret' 
          |                 |     from Generic Jit Trampoline
          |                 |
          |Console.WriteLine|
          |                 |
       ^  |                 |
       |  +-----------------+ <-- Top of Stack at entry
       |  |                 |     Specific Trampoline
       |  |                 |
       |  | Main + 0x15     |
       |  | (Return IP)     |
       |  |                 |
       |  +-----------------+
       |  |                 |
       |  |                 |
       |  |       13        |
          |(WriteLine Arg)  |
          |                 |
          +-----------------+

Note: It is instructive to track the stack state as each
instruction in Specific Jit Trampoline is executed.

2 Summary

The Very first invocation of the method also triggers a compilation
of the method. This – Compile only after Execute-Request – is the
fundamental paradigm of Just-In-Time compilers.

The following points are worth noting

  1. The Very first invocation of the method doesn’t happen right at
    the user-specified site in the caller. This invocation is
    simulated by Generic Trampoline by manipulating values on
    caller’s stack.

  2. Second and Subsequent invocations, unlike the first invocation,
    happens right at the user-defined call site as expected. This is
    made possible by Call Site Patching logic in the Magic
    Trampoline.

    Note that the the overheads of trampoline is one-time only.

  3. Compiling to Native Code of the invoked method happens within the
    scope of The Magic Trampoline.

Footnotes:

1 As generated by mono_codegen ()

2 Refer mono_arch_create_specific_trampoline ()

3 Corresponds to mono_arch_create_trampoline_code (MONO_TRAMPOLINE_JIT)

Author: Jambunathan K. Consult About page for my Inbox information.

Advertisements

Create a free website or blog at WordPress.com.

%d bloggers like this: