CLR implementation of virtual method calls to inte

Question

Out of curiosity: how does the CLR dispatch virtual method calls to interface members to the correct implementation?

I know about the VTable that the CLR maintains for each type with method slots for each method, and the fact that for each interface it has an additional list of method slots that point to the associated interface method implementations. But I don't understand the following: how does the CLR efficiently determine which interface method slot list to pick from the type's VTable?

The article Drill Into .NET Framework Internals to See How the CLR Creates Runtime Objects from the May 2005 issue of the MSDN Magazine talks about a process-level mapping table IVMap indexed by interface ID. Does this mean that all types in the same process have the same pointer to the same IVMap?

It also states that:

If MyInterface1 is implemented by two classes, there will be two entries in the IVMap table. The entry will point back to the beginning of the sub-table embedded within the MyClass method table.

How does the CLR know which entry to pick? Does it do a linear search to find the entry that matches the current type? Or a binary search? Or some kind of direct indexing and have a map with possibly many empty entries in it?

I've also read the chapter on Interfaces in CLR via C# 3rd edition but it does not talk about this. Therefore, the answers to this other question do not answer my question.

Answer 1

From the first article that you linked:

If MyInterface1 is implemented by two classes, there will be two entries in the IVMap table. The entry will point back to the beginning of the sub-table embedded within the MyClass method table, as shown in Figure 9

and

The ClassLoader walks through the metadata of the current class, parent class, and interfaces, and creates the method table. In the layout process, it replaces any overridden virtual methods, replaces any parent class methods being hidden, creates new slots, and duplicates slots as necessary. The duplication of slots is necessary to create an illusion that each interface has its own mini vtable. However, the duplicated slots point to the same physical implementation.

This suggests to me that the interface's IVMap has entries keyed by the class name (or some equivalent) pointing to a subsection of the class's vtable, which essentially has duplicate implementations of each of the class's methods that implement that interface, backed by pointers to the same physical implementation as the class's own vtable entries.

Could be completely wrong though.

Answer 2

That article is more than 10 years old, and a lot has changed since then.

IVMaps have now been superseded by Virtual Stub Dispatch.

Virtual stub dispatching (VSD) is the technique of using stubs for virtual method invocations instead of the traditional virtual method table. In the past, interface dispatch required that interfaces had process-unique identifiers, and that every loaded interface was added to a global interface virtual table map.

Go read that article, it has more detail you'll ever need to know. It comes from the Book of the Runtime, which was documentation originally written by the CLR devs for CLR devs but has now been published for everyone. It basically describes the guts of the runtime.

There's no point for me to duplicate the article here, but I'll just state the main points and what they imply:

• When the JIT sees a call to an interface member, it compiles it into a lookup stub. This is a piece of code will invoke a generic resolver.
• The generic resolver is a function which will find out which method to call. It's the most generic and therefore slowest way to invoke such a method. When called for the first time from a lookup stub, it will patch that stub (rewrite its code at runtime) into a dispatch stub. It also generates a resolve stub for later use. The lookup stub goes away at this point.
• A dispatch stub is the fastest way to invoke an interface member, but there's a catch: it is optimistic about the call being monomorphic, which means that it's optimized for the case when the interface call always resolves to the same concrete type. It compares the method table (ie the concrete type) of the object to the previously seen one (which is hardcoded into the stub), and calls the cached method (whose address is also also hardocded) if the comparison succeeds. If it fails, it falls back to the resolve stub.
• The resolve stub handles polymorphic calls (the general case). It uses a cache to find which method to call. If the method is not in the cache, it invokes the generic resolver (which also writes to this cache).

And here's an important consideration, straight from the article:

When a dispatch stub fails frequently enough, the call site is deemed to be polymorphic and the resolve stub will back patch the call site to point directly to the resolve stub to avoid the overhead of a consistently failing dispatch stub. At sync points (currently the end of a GC), polymorphic sites will be randomly promoted back to monomorphic call sites under the assumption that the polymorphic attribute of a call site is usually temporary. If this assumption is incorrect for any particular call site, it will quickly trigger a backpatch to demote it to polymorphic again.

The runtime is really optimistic about monomorphic call sites, which makes a lot of sense in real code, and it will try hard to avoid resolve stubs as much as possible.

Answer 3

If you take a look at diagram that was on the linked site, it may make it easier to understand.

Does this mean that all types in the same process have the same pointer to the same IVMap?

Yes, since it is at the domain level, it means everything in that AppDomain has the same IVMap.

How does the CLR know which entry to pick? Does it do a linear search to find the entry that matches the current type? Or a binary search? Or some kind of direct indexing and have a map with possibly many empty entries in it?

The classes are laid out with offsets, so everything has a relatively set area on where it would be. That makes things easier when looking for methods. It would search the IVMap table and find that method from the interface. From there, it goes to the MethodSlotTable and uses that class' implementation of the interface. The inteface map for the class holds the metadata, however, the implementation is treated just like any other method.

Again from the site you linked:

Each interface implementation will have an entry in IVMap. If MyInterface1 is implemented by two classes, there will be two entries in the IVMap table. The entry will point back to the beginning of the sub-table embedded within the MyClass method table

This means that each time an interface is implemented it has a unique record in the IVMap which points to the MethodSlotTable which in turn points to the implementation. So it knows which implementation to pick based on the class that is calling it as that IVMap record points to the MethodSlotTable in the class calling the method. So I imagine it is just a linear search through the IVMap to find the correct instance and then they are off and running.

---

EDIT: To provide more info on the IVMap.

Again, from the link in the OP:

The first 4 bytes of the first InterfaceInfo entry points to the TypeHandle of MyInterface1 (see Figure 9 and Figure 10). The next WORD (2 bytes) is taken up by Flags (where 0 is inherited from parent, and 1 is implemented in the current class). The WORD right after Flags is Start Slot, which is used by the class loader to lay out the interface implementation sub-table.

So here we have a table where the number is the offset of bytes. This is just one record in the IVMap:

+----------------------------------+
| 0 - InterfaceInfo                |
+----------------------------------+
| 4 - Parent                       |
+----------------------------------+
| 5 - Current Class                |
+----------------------------------+
| 6 - Start Slot (2 Bytes)         |
+----------------------------------+

Suppose there are 100 interface records in this AppDomain and we need to find the implementation for each one. We just compare the 5th byte to see if it matches our current class and if it does, we jump to the code in the 6th byte. Since, each record is 8 bytes long, we would need to do something like this: (Psuedocode)

findclass :
   if (!position == class) 
      findclass adjust offset by 8 and try again

While it is still a linear search, in reality, it isn't going to take that long as the size of data being iterated isn't huge. I hope that helps.

---

EDIT2:

So after looking at the diagram and wondering why there is no Slot 1 in the IVMap for the class in the diagram I re-read the section and found this:

IVMap is created based on the Interface Map information embedded within the method table. Interface Map is created based on the metadata of the class during the MethodTable layout process. Once typeloading is complete, only IVMap is used in method dispatching.

So the IVMap for a class is only loaded with the interfaces that the specific class inherits. It looks like it copies from the Domain IVMap but only keeps the interfaces that are pointed to. This brings up another question, how? Chances are it is the equivalent of how C++ does vtables where each entry has an offset and the Interface Map provides a list of the offsets to include in the IVMap.

If we look at the IVMap that could be for this entire domain:

+-------------------------+
| Slot 1 - YourInterface  |
+-------------------------+
| Slot 2 - MyInterface    |
+-------------------------+
| Slot 3 - MyInterface2   |
+-------------------------+
| Slot 4 - YourInterface2 |
+-------------------------+

Assume there are only 4 implementations of Interface Map in this domain. Each slot would have an offset (similar to the IVMap record I posted earlier) and the IVMap for this class would use those offsets to access the record in the IVMap.

Assume each slot is 8 bytes with slot 1 starting at 0 so if we wanted to get slot 2 and 3 we would do something like this:

mov ecx,edi
mov eax, dword ptr [ecx]
mov eax, dword ptr [ecx+08h] ; slot 2
; do stuff with slot 2
mov eax, dword ptr [ecx+10h] ; slot 3
; do stuff with slot 3

Please excuse my x86 as I'm not that familiar with it but I tried to copy what they have in the article that was linked to.