Mono Runtime Notes

April 22, 2009

Interface Method Dispatch (IM Table and Thunks)

Interface Method Dispatch (IM Table and Thunks)

1 Introduction

In this post, I seek to explore how Interface Method Dispatch is
implemented in the Mono Runtime.

Firstly I advance a simple example that illustrate how Dispatching
via an Interface Handle differs from Dispatching via non-Interface
Handles. Next I consider runtime data structures – IM Table (IMT)
and Thunks – that accomplish Interface Method Dispatch.

Before we proceed ahead, let me add that IM dispatch relies on
Generic / Specific JIT trampolines and Magic trampolines. These
trampolines were introduced in one of my earlier posts1.

2 Motivation for IMT – Interface Methods and Virtual Slots

The main problem with an Interface Method is the following:

Classes that implement a given interface method, can implement the
same at potentially different VTable slots.

For the sake of illustration consider a simple class structure and
the corresponding VTable as laid out by the runtime. Specifically
note that the interface method IPrint.Print is assigned Slot 5 in
PrintHate’s VTable while it is assigned Slot 4 in PrintLove’s
VTable.

  // A Simple Class Structure

  using System;

  interface IPrint
  {
      void Print ();
  }

  class PrintLove : IPrint
  {
      public void Print () {}
  }

  class Hate
  {
      public virtual void Something ()
      {
          ;
      }
  }

  class PrintHate : Hate, IPrint
  {

      public override void Something ()
      {
          ;
      }

      public void Print () {}
  }

  // VTable for above Class Hierarchy

  VTable Hate (vtable entries = 5, interfaces = 0)
    slot assigned: 000, slot index: 000 object:Equals (object)
    slot assigned: 001, slot index: 001 object:Finalize ()
    slot assigned: 002, slot index: 002 object:GetHashCode ()
    slot assigned: 003, slot index: 003 object:ToString ()
    slot assigned: 004, slot index: 004 Hate:Something ()

  VTable PrintHate (vtable entries = 6, interfaces = 1)
    slot assigned: 000, slot index: 000 object:Equals (object)
    slot assigned: 001, slot index: 001 object:Finalize ()
    slot assigned: 002, slot index: 002 object:GetHashCode ()
    slot assigned: 003, slot index: 003 object:ToString ()
    slot assigned: 004, slot index: 004 PrintHate:Something ()
    slot assigned: 005, slot index: 005 PrintHate:Print ()


  VTable PrintLove (vtable entries = 5, interfaces = 1)
    slot assigned: 000, slot index: 000 object:Equals (object)
    slot assigned: 001, slot index: 001 object:Finalize ()
    slot assigned: 002, slot index: 002 object:GetHashCode ()
    slot assigned: 003, slot index: 003 object:ToString ()
    slot assigned: 004, slot index: 004 PrintLove:Print ()

Given the above scenario, it is clear that IM dispatch has to
involve a lookup in a class-specific table that maps between the IM
Handle and it’s target VTable slot. This table is called as an
Interface Method Table or IMT for short.

We now proceed to see how this IM Table is Lookup is done in the
Mono Runtime. At this point, it suffices to remark that the
specific choice of data structure, detailed below, is driven by a
requirement on the runtime to provide a optimal hosting environment
for it’s applications 2.

3 Example Assembly

We will reference the following assembly throughout the following
sections

  // file interface.cs

  using System;

  interface IPrint
  {
       void Print_4 ();
       void Print_5 ();
       void Print_6 ();

       void Print_14 ();
       void Print_21 ();

       void Print_42 ();
       void Print_44 ();
       void Print_46 ();
  }

  class PrintLove : IPrint
  {
       public void Print_4 () {}
       public void Print_5 () {}
       public void Print_6 () {}

       public void Print_14 () {}
       public void Print_21 () {}

       public void Print_42 () {}
       public void Print_44 () {}
       public void Print_46 () {}
  }

  class HelloWorld
  {
       public static void Main ()
       {
           PrintLove love = new PrintLove ();

           IPrint obj = love;

           obj.Print_5 ();

           obj.Print_4 ();

           obj.Print_6 ();

           Console.ReadLine ();
       }
  }
  $ mcs Interface.cs
  $ mono Interface.exe

Let’s look at the sequence of steps that the runtime does to
accomplish IM calls obj.Print_5 (), obj.Print_4 () and obj.Print_6
().

4 Initial VTable

Consider the code fragment below. It initializes VTable for a class
that provides one or more Interface methods.

Examine the following code in light of the PrintLove class in our
example.


   // Struct MonoVTable

   struct MonoVTable {
       MonoClass  *klass;
       void *gc_descr;
       MonoDomain *domain;

       ---> snip, snip, snip <----

       // VTable Slots start here
       gpointer    vtable [MONO_ZERO_LEN_ARRAY];
   }

   // Snippet of relevant code for initial VTable setup
   // Lines of code not of interest to us currently is snipped

   # define MONO_IMT_SIZE 19

   static MonoVTable *
   mono_class_create_runtime_vtable (MonoDomain *domain, MonoClass *class)
   {
       MonoVTable *vt;
       guint32 vtable_size;
       gpointer *interface_offsets;

       // Init the Class
       mono_class_init (class);

       if (!class->vtable_size)
           mono_class_setup_vtable (class);

       // Compute VTable size.
       vtable_size = sizeof (MonoVTable) +
           class->vtable_size * sizeof (gpointer);

       vtable_size + = sizeof (gpointer) * (MONO_IMT_SIZE);

       // Allocate space for VTable
       interface_offsets = mono_domain_alloc0 (domain, vtable_size);

       vt = (MonoVTable*) ((char*)interface_offsets +
                   sizeof (gpointer) * (MONO_IMT_SIZE);

       // Init IMT and VTable slots with trampolines
       for (i = 0; i < MONO_IMT_SIZE; ++i)
           interface_offsets [i] = imt_trampoline;

       for (i = 0; i < class->vtable_size; ++i) {
           vt->vtable [i] = vtable_trampoline;
   }
  // Define IMT Trampoline

  #define MONO_FAKE_IMT_METHOD ((MonoMethod*)GINT_TO_POINTER(-1))
  imt_trampoline = 
   mono_create_specific_trampoline (MONO_FAKE_IMT_METHOD, 
                                    MONO_TRAMPOLINE_JIT, 
                                    mono_get_root_domain (), 
                                    NULL)

 // Define VTable Trampoline

 #define MONO_FAKE_VTABLE_METHOD ((MonoMethod*)GINT_TO_POINTER(-2))
  vtable_trampoline = 
   mono_create_specific_trampoline (MONO_FAKE_VTABLE_METHOD, 
                                       MONO_TRAMPOLINE_JIT, 
                                   mono_get_root_domain (), 
                                   NULL);

VTable for PrintLove class has a total of 12 virtual method
entries, 4 inherited from System.Object and 8 implemented by the
class (as mandated by IPrint interface class). The slot assignment
chosen by the runtime is shown below.

  VTable PrintLove (vtable entries = 12, interfaces = 1)         
    slot assigned: 000, slot index: 000 object:Equals (object)  
    slot assigned: 001, slot index: 001 object:Finalize ()   
    slot assigned: 002, slot index: 002 object:GetHashCode ()    
    slot assigned: 003, slot index: 003 object:ToString ()   
    slot assigned: 004, slot index: 004 PrintLove:Print_4 ()     
    slot assigned: 005, slot index: 005 PrintLove:Print_5 ()     
    slot assigned: 006, slot index: 006 PrintLove:Print_6 ()     
    slot assigned: 007, slot index: 007 PrintLove:Print_14 ()    
    slot assigned: 008, slot index: 008 PrintLove:Print_21 ()    
    slot assigned: 009, slot index: 009 PrintLove:Print_42 ()    
    slot assigned: 010, slot index: 010 PrintLove:Print_44 ()    
    slot assigned: 011, slot index: 011 PrintLove:Print_46 ()   

The figure down below captures the state of the PrintLove class’s
VTable right after initial setup.

Note there are 19 IMT slots and 12 VTable slots in the VTable. Their
entry points is set to point to IMT and VTable Trampolines
respectively.

An IMT trampoline and VTable trampolines are Specific JIT
trampolines associated with no particular method and created in root
domain. We know from our previous discussions that a Specific JIT
trampoline ultimately calls a Magic Trampoline that does the
required magic. We will come to the details of the magic shortly.


                                                         ^
   0-> +-----------+     imt_tramp: @ 0xb7981000         |
       |  imt_tramp|         push   0xffffffff   // -1   |
   1-> +-----------+         jmp    0xb7bcf028           |
       |  imt_tramp|                                     |
   2-> +-----------+                                     |
       |  imt_tramp|                                     |
   3-> +-----------+                                     |
       |  imt_tramp|                                     |
   4-> +-----------+                                     |
       |  imt_tramp|                                     |
   5-> +-----------+                                     |
       |  imt_tramp|                                     |   IMT Slots
   6-> +-----------+                                     | 19 hash entries
       |  imt_tramp|                                     |
   7-> +-----------+                                     | Initied to imt_tramp
       |  imt_tramp|                                     |
   8-> +-----------+                                     |
       |  imt_tramp|                                     |
       +-----------+                                     |
       |           |                                     |
       |           |   /---                              |
               /-------                                  |
       /-------    |                                     |
    ---            |                                     |
       |           |                                     |
 16->  +-----------+                                     |
       |  imt_tramp|                                     |
 17->  +-----------+                                     |
       |  imt_tramp|                                     |
 18->  +-----------+                                     V
       |  imt_tramp|
       +-----------+ <--- 0x82c0c00 (= vt)               ^
       |           |                                     |
       |           |                                     |
       |           |                                     |
       |           |                                     |   struct MonoVTable
       |           |                                     |   (size = 36 bytes)
       |           |                                     |
       |           |                                     |
       |           |                                     |
       |           |                                     |
       |           |                                     |
       |           |                                     |
       |           |                                     |
       |           |                                     |
       |           |   vt_tramp: @ 0xb798100c            |                            
       |           |     push   0xfffffffe    // -2      |                            
       |           |     jmp    0xb7bcf028               |                            
       |           |                                     |
       |           |                                     |
       |           |                                     V
       |           |
   0-> +-----------+ <--- 0x82c0c24                      ^
       |  vt_tramp | // for Object:Equals (object)       |
   1-> +-----------+                                     |
       |  vt_tramp | // for object:Finalize ()           |
   2-> +-----------+                                     |
       |  vt_tramp | // for object:GetHashCode ()        |
   3-> +-----------+                                     |
       |  vt_tramp | // for object:ToString ()           |     VTable slots
   4-> +-----------+                                     |     one for each
       |  vt_tramp | // for PrintLove:Print_4 ()         |    virtual method
   5-> +-----------+                                     |
       |  vt_tramp | // for PrintLove:Print_5 ()         |  Initied to vt_tramp
   6-> +-----------+                                     |
       |  vt_tramp | // for PrintLove:Print_6 ()         |
   7-> +-----------+                                     |
       |  vt_tramp | // for PrintLove:Print_14 ()        |
   8-> +-----------+                                     |
       |  vt_tramp | // for PrintLove:Print_21 ()        |
   9-> +-----------+                                     |
       |  vt_tramp | // for PrintLove:Print_42 ()        |
  10-> +-----------+                                     |
       |  vt_tramp | // for PrintLove:Print_44 ()        |
  11-> +-----------+                                     |
       |  vt_tramp | // for PrintLove:Print_46 ()        V
       +-----------+

5 Code Generation

Before we proceed ahead let’s focus our attention on the
intermediate and target code generated for the Main method. We are
only interested in the IM calls.

 // Object layout in the runtime. Note that VTable is at offset 0.
                                         
  typedef struct {                   
       MonoVTable *vtable;               
       MonoThreadsSync *synchronisation; 
  } MonoObject;                         

  // Snippet of code from mono_emit_method_call_full

  int vtable_reg, slot_reg, this_reg;

  // Internal opocode for 'callvirt' CLR instruction
  call->inst.opcode = callvirt_to_call_membase (call->inst.opcode);

  // Allocate a register to hold VTable. 
  // Comment: VTable is at offset 0 of a MonoObject 

  vtable_reg = alloc_preg (cfg);
  MONO_EMIT_NEW_LOAD_MEMBASE (cfg, vtable_reg, this_reg, G_STRUCT_OFFSET (MonoObject, vtable));
  
  // Compute IMT slot for the Interface Method . This is a hash of
  components that constitute the interface method signature

  guint32 imt_slot = mono_method_get_imt_slot (method);
  
  // Arrange for Method Handle to be available in a well-known register.
  // This register is EDX in case of Intel 

  emit_imt_argument (cfg, call, imt_arg);


  // Emit 'call vtable [imt_slot - MONO_IMT_SIZE]'
  // Note specifically that the vtable is indexed at a negative offset
  // 

  slot_reg = vtable_reg;
  call->inst.inst_offset = ((gint32)imt_slot - MONO_IMT_SIZE) * SIZEOF_VOID_P;
  
  call->inst.sreg1 = slot_reg;
  call->virtual = TRUE;

  // Add the call instruction to the Code Flow Graph
  MONO_ADD_INS (cfg->cbb, (MonoInst*)call);

The code generator generates the following native code –

  // Native Code

  30:  8b 45 f8                mov    eax,DWORD PTR [ebp-8]    // eax = this
  33:  83 ec 0c                sub    esp,0xc
  36:  50                      push   eax
  37:  89 45 fc                mov    DWORD PTR [ebp-4],eax
  3a:  8b 00                   mov    eax,DWORD PTR [eax]      // eax = vtable
  3c:  ba 64 4c 2f 08          mov    edx,0x82f4c64            // edx = Method handle for IPrint.Print_4
  41:  ff 50 b8                call   DWORD PTR [eax-72]       // Call the method at IMT slot 1.
  44:  83 c4 10                add    esp,0x10

For the very first call to Print4, the call is directed to the IMT
Trampoline which in turn ends up in the magic trampoline.

6 IMT call Handling in Magic Trampoline

Let’s consider here how the magic trampoline handles IMT calls. The
magic trampoline understands that it is doing IMT handling via the
MONOFAKEIMTMETHOD handle passed to it.

Note that the magic trampoline has access to all information it
needs to do the needed magic.

One would recall that the Magic Trampoline gets a snapshot of the
state of registers at the call site through a regs array arg. It
implies that Magic Trampoline has access to the Interface Method
Handle (EDX component of regs array) as well as the IMT slot (via
opcode probing at the call site)

The magic trampoline now has the responsibility of

  1. Locating the VTable slot for the Interface Method.
  2. Compiling the target IM method and get a native entry point for it.
  3. Creating a IM Handle-to-Entry Point mapping
  4. Doing some house work so that future invocation to the IM doesn’t
    go through the trampoline. This involves replacing IMT slot
    entries and VTable Slot entries.

Steps 3 and 4 are accomplished by what are known as IMT thunks.

7 IMT Thunks Explained

One can intuitively guess how and what goes on in to the IMT Thunks
by simply looking at the VTable of the PrintLove class right after
the three interface method invocations obj.Print5, obj.Print4 and
obj.Print6 and by looking at the IMT Thunks themselves.

After some deep consideration of the wealth of information captured
in the next section one make the following inferences –

  1. IMT Thunks are generated only for colliding IMT slots
  2. IMT Thunks compare the target interface method (which is in EDX)
    and jump to the method entry point defined in the rightful VTable
    slot.
  3. IMT Thunks generated for slots with small collisions ( < 4)
    employ a linear search while that with more entries employ binary
    search
  4. IM table entries are lazy filled i.e., only upon invocation. Only
    exception to this rule are other Interface Methods that contend
    for the same IM slot as the Target IM. Note that contending
    methods continue to remain uncompiled. Only their map is set
    eagerly.
  5. IM Thunks introduce a small lookup overhead for some IM
    dispatches. This overhead is always there throughout the lifetime
    of the program.

8 VTable after JIT compilation and Execution


  // LEGEND:

  |----------+-----------+--------------------+----------+-------------+---------------|
  | IM       | IM Handle | Native Entry Point | IMT Slot | VTable Slot | *IMT Slot     |
  |----------+-----------+--------------------+----------+-------------+---------------|
  |          |           |                    |          |             |               |
  |----------+-----------+--------------------+----------+-------------+---------------|
  | Print_5  | 0x82f4c84 | 0xb79813f0         |       16 |           5 | 0xb79813f0    |
  |----------+-----------+--------------------+----------+-------------+---------------|
  |          |           |                    |          |             |               |
  |----------+-----------+--------------------+----------+-------------+---------------|
  | Print_4  | 0x82f4c64 | 0xb7981410         |        1 |           4 | 0xb79813f8    |
  |          |           |                    |          |             | (IMT Thunk 1) |
  |----------+-----------+--------------------+----------+-------------+---------------|
  | Print_21 | 0x82ed54c | Not Known          |        1 |           8 | - ditto -     |
  |----------+-----------+--------------------+----------+-------------+---------------|
  |          |           |                    |          |             |               |
  |----------+-----------+--------------------+----------+-------------+---------------|
  | Print_6  | 0x82f4ca4 | 0xb7981458         |        8 |           6 | 0xb7981418    |
  |          |           |                    |          |             | (IMT Thunk 2) |
  |----------+-----------+--------------------+----------+-------------+---------------|
  | Print_14 | 0x82f4cc4 | Not Known          |        8 |           7 | - ditto -     |
  |----------+-----------+--------------------+----------+-------------+---------------|
  | Print_42 | 0x82ed56c | Not Known          |        8 |           9 | - ditto -     |
  |----------+-----------+--------------------+----------+-------------+---------------|
  | Print_44 | 0x82ed58c | Not Known          |        8 |          10 | - ditto -     |
  |----------+-----------+--------------------+----------+-------------+---------------|
  | Print_46 | 0x82ed5ac | Not Known          |        8 |          11 | - ditto -     |
  |----------+-----------+--------------------+----------+-------------+---------------|

VTable after JIT compilation and Execution

                        +-----> @ 0xb79813f8:
                        |
                        |           cmp    edx,0x82ed54c          // Print_21?
                        |           jne    0x0e
                        |           jmp    DWORD PTR ds:0x82c0c44 // jmp vt_slot [3] if Print_21
                        |     0x0e: jmp    DWORD PTR ds:0x82c0c34 // jmp vt_slot [4] if Print_4
                        |           add    BYTE PTR [eax],al
   0-> +-----------+    |           add    BYTE PTR [eax],al
       |  imt_tramp|    |           push   ebp
   1-> +-----------+    |           mov    ebp,esp
       |imt_thunk-1|----+           sub    esp,0x8
   2-> +-----------+                leave
       |  imt_tramp|                ret
   3-> +-----------+
       |  imt_tramp|
   4-> +-----------+    +---> @ 0xb7981418:
       |  imt_tramp|    |
   5-> +-----------+    |           cmp    edx,0x82ed5ac          // Print_46?
       |  imt_tramp|    |           jae    0x1c
   6-> +-----------+    |           cmp    edx,0x82ed56c          // Print_42?
       |  imt_tramp|    |           jne    0x16
   7-> +-----------+    |           jmp    DWORD PTR ds:0x82c0c48 // jmp vt_slot [5]
       |  imt_tramp|    |     0x16: jmp    DWORD PTR ds:0x82c0c4c // jmp vt_slot [6]
   8-> +-----------+    |     0x1c: jne    0x24
       |imt_thunk_2|----+           jmp    DWORD PTR ds:0x82c0c50 // jmp vt_slot [7]
       +-----------+          0x24: cmp    edx,0x82f4ca4          // Print_6?
       |           |                jne    0x32
       |           |   /---         jmp    DWORD PTR ds:0x82c0c3c // jmp vt_slot [8]
               /-------       0x32: jmp    DWORD PTR ds:0x82c0c40 // jmp vt_slot [9]
       /-------    |                add    BYTE PTR [eax],al
    ---            |                add    BYTE PTR [eax],al
       |           |                add    BYTE PTR [eax],al
 16->  +-----------+                add    BYTE PTR [eax],al
       |0xb79813f0 |                push   ebp
 17->  +-----------+                mov    ebp,esp
       |  imt_tramp|                sub    esp,0x8
 18->  +-----------+                leave
       |  imt_tramp|                ret
       +-----------+ <-- 0x82c0c00
       |           |      ( = vt)
       |           |
       |           |
       |           |
       |           |
       |           |
       |           |
   0-> +-----------+ <--- 0x82c0c24
       |  vt_tramp | // for Object:Equals (object)
   1-> +-----------+
       |  vt_tramp | // for object:Finalize ()
   2-> +-----------+
       |  vt_tramp | // for object:GetHashCode ()
   3-> +-----------+
       |  vt_tramp | // for object:ToString ()
   4-> +-----------+
       | 0xb7981410| // PrintLove:Print_4 () -------------+      vtable trampolines
   5-> +-----------+                                      |       replaced with
       |  vt_tramp | // for PrintLove:Print_5 ()          +---->  pointer to native
   6-> +-----------+                                      |        method ptrs
       |0xb7981458 | // PrintLove:Print_6 () o------------+
   7-> +-----------+                                           Not yet invoked methods
       |  vt_tramp | // for PrintLove:Print_14 ()               continue to point to
   8-> +-----------+                                              vtable trampolines
       |  vt_tramp | // for PrintLove:Print_21 ()
   9-> +-----------+
       |  vt_tramp | // for PrintLove:Print_42 ()
  10-> +-----------+
       |  vt_tramp | // for PrintLove:Print_44 ()
  11-> +-----------+
       |  vt_tramp | // for PrintLove:Print_46 ()
       +-----------+

Footnotes:

1 Refer Magic (of) Trampolines

2 Refer Trimming VTables in the Mono runtime for a detailed
consideration of this issue.

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

Date: 2009-04-22 02:45:56 IST

Advertisements

Blog at WordPress.com.