CLR implementation of virtual method calls to interface members

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.

Illassorted

The link in the question no longer points to a specific article. Please could you tell us which issue the article appeared in (month & year)? – Cloud

@buffjape It was the MSDN magazine's May 2005 issue. I updated the link to point to the internet archive instead. – Illassorted

Please don't award a large bounty to a badly outdated copy-paste answer that was irrelevant even by the time it was posted. That doesn't help anybody. – Cauterize

Lot of interesting info can be found in the answer of this question : softwareengineering.stackexchange.com/questions/373806/… – Cheddar

Answer 1

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.

Etoile

I don't follow the laid out with offsets, so everything has a relatively set area on where it would be. But, yes I can imagine that the CLR does a linear search through the IVMap, as stated in my post. But I want to know how it works in practice. Surely, for something like interface method calls that may happen so often, doing a linear search seams awfully naive. – Illassorted

@Virtlink If you look at the image above, you'll notice that there is the number based on the heap for method table. So GCInfo is at -12, Basic Instance Size is at 4, etc. Using those set, standardized offsets you would be able to do find fields by just doing something like dword ptr [eax+0Ch] – Etoile

Okay, yes, you are correct. But I never mentioned the word fields anywhere in my question :). I want to know what the IVMap looks like and how the CLR uses it to get from a known interface + method slot index and an object reference to the sub table in the object type's VTable containing the interface's method slots. – Illassorted

@Virtlink please see my edit. I hope I cleared things up. If not please let me know. – Etoile

The x86 example under this heading doesn't show anything that resembles a linear search. Do you have any sources? – Illassorted

@Virtlink The x86 example doesn't show finding the class, it just shows how to execute the certain classes's implementation of the interface, which isn't what you asked. I'm not 100% on how it would be found, I'm betting somebody from MS would be able to give 100% specifics but don't know if they will. I'm just pointing out a linear search isn't as bad as it seems in theory based on the layout of the IVMap – Etoile

@Virtlink thanks, I've edited again. Maybe more clarity will come – Etoile

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.

Nola

Answer 3

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.

Orthotropic

If you read my post completely, you'd have seen that I already quoted the same quote that you did, and that I know how the VTable has a subsection for each interface with pointers to the method implementations. My question is specifically how the CLR knows which subsection to use. – Illassorted

Answer 4

Or some kind of direct indexing and have a map with possibly many empty entries in it?

After researching the topic - this seems to have been the case before the new Virtual Stub Dispatch mechanism was introduced (BookOftheRuntime link)

One of the reasons mentioned -> Working Set Reduction

Interface dispatch was previously implemented using a large, somewhat sparse vtable lookup map dealing with process-wide interface identifiers.

And from the Introduction

This requirement meant that all interfaces and all classes that implemented interfaces had to be restored at runtime in NGEN scenarios, causing significant startup working set increases.

So, it looks like there was a Class-Interface table with a fixed order of interfaces for each class. This would enable the following example (from the excellent "Pro .NET Performance" book by Sasha Goldshtein et al.

mov ecx, dword ptr [ebp-64] ; object reference
mov eax, dword ptr [ecx] ; method table pointer
mov eax, dword ptr [eax+12] ; interface map pointer
mov eax, dword ptr [eax+48] ; compile time offset for this interface in the map
call dword ptr [eax] ; first method at EAX, second method at EAX+4, etc.

At offset 12 we had a pointer to offset for Class A in the Global Interface Map. Then to access the specific Interface Table we had a fixed offset at +48. The address there was pointing back to the beginning of the Interface Map for the speficic interface in our own Method Table. As the order of the methods for the interface is fixed we can use offset for the specific method slot. The above assembly would work without walking any hierarchies just by dereferencing and relying on a large matrix class x interface.

This also is shown in Figure 9 from the 2005 Article about the .NET CLR Internals

Another confirmation for this is the following paragraph from "Essential .NET, Vol. 1 The common language runtime" by Don Box and Chris Sells (2002):

the interface offset table is an array of offsets into the type's method table. There is one entry in this table for every interface type that has been initialized by the CLR independent of whether or not the type supports the interface. As the CLR initializes interface types, it assigns them a zero-based index into this table. When the CLR initializes a concrete type, the CLR allocates a new interface offset table for the type. The interface offset table will be sparsely populated, but it must be at least as long as the index of any of its declared interfaces. When the CLR initializes a concrete type, the CLR populates its interface offset table by storing the appropriate method table offsets into the entries for supported interfaces. Because the CLR's verifier ensures that interface-based references refer only to objects that support the declared type, interface offset table entries for unsupported interfaces are never used and their contents are immaterial.

Electrolyse