Monday, April 10, 2006

Hack #9: Dynamic method table structure

One of the compiler magic slots in a class’ virtual method table (VMT) is a pointer to that class’ dynamic method table (DMT). A class only has a DMT if it declares or overrides one or more dynamic (or message) methods. The DMT contains a 16-bit (word) Count followed by an array[0..Count-1] of Smallint indices and an array[0..Count-1] of pointers containing  the code address of the dynamic method’s implementation. Note that the arrays are “inline” in the DMT structure (there is no pointers to the arrays). One approximate way of representing this structure in Pascal would be:

type
TDMTIndex = Smallint;
PDmtIndices = ^TDmtIndices;
TDmtIndices = array[0..High(Word)-1] of TDMTIndex;
PDmtMethods = ^TDmtMethods;
TDmtMethods = array[0..High(Word)-1] of Pointer;
PDmt = ^TDmt;
TDmt = packed record
Count: word;
Indicies: TDmtIndices; // really [0..Count-1]
Methods : TDmtMethods; // really [0..Count-1]
end;

Because Pascal does not support declaring static array types that vary in size depending on a field, we have to perform some pointer tricks to get at the Methods array. We can now update the declaration of our VMT record structure – we change the DynamicTable field from a generic Pointer to our specific PDmt type:

type
PVmt = ^TVmt;
TVmt = packed record
SelfPtr : TClass;
IntfTable : Pointer;
AutoTable : Pointer;
InitTable : Pointer;
TypeInfo : Pointer;
FieldTable : Pointer;
MethodTable : Pointer;
DynamicTable : PDmt;
ClassName : PShortString;
InstanceSize : PLongint;
Parent : PClass;
SafeCallException : PSafeCallException;
AfterConstruction : PAfterConstruction;
BeforeDestruction : PBeforeDestruction;
Dispatch : PDispatch;
DefaultHandler : PDefaultHandler;
NewInstance : PNewInstance;
FreeInstance : PFreeInstance;
Destroy : PDestroy;
{UserDefinedVirtuals: array[0..999] of procedure;}
end;

Compiler magic routines
The System unit contains a number of RTL magic routines. Btw, I’m not making up the phrases “magic routines” and “compiler magic”. Above the declaration of a number of special routines with names that start with an underscore (which maps to an ampersand when compiled) in the System.pas unit you’ll find this comment:

{ Procedures and functions that need compiler magic }

The compiler is hard-coded to find and use these as it is generating code for language features such as strings, dynamic arrays and dynamic methods. They cannot be called explicitly from Pascal – only implicitly by using the language features they implement or explicitly from BASM. As we have seen in a couple of cases, to call a compiler magic routine from BASM you use the syntax CALL System.@MagicName.

The interfaced magic routines that deal with dynamic method dispatching and lookup are:

procedure _CallDynaInst;
procedure _CallDynaClass;
procedure _FindDynaInst;
procedure _FindDynaClass;

There are separate Call and Find routines for instance and class dynamic methods (yes, you can have class level dynamic methods too). The CallDyna routines take a Self (TObject or TClass) parameter in the EAX register and an 16-bit signed Smallint Index parameter in the SI register. Both the CallDyna routines will JMP directly to the dynamic method implementation after finding it. Any parameters the dynamic method in question takes must be assigned to EDX, ECX and pushed to the stack as appropriate. That’s why the normally scratch register SI is used to pass the index.

The two FindDyna routines have no such parameter preserving constraints, so they take a Self (TObject or TClass) in EAX and the Index in EDX, as any normal Register calling convention routine.

All these routines use a common, internal worker routine (GetDynaMethod) that does the actual scanning of the DMT, iterating to scan the parent classes as needed. I was able to reconstruct the TDmt record above by analyzing this code. The implementation uses the fairly efficient REPNE SCASW instruction to quickly scan the array of Smallints for the DMT index.

A debugging tip
If you compile your application with the debug RTL (Project Options | Compiler | [X] Use debug DCUs) – a good idea if you want to get good stack traces from exception stack tracers (such as madExcept or JclDebug) – you might find yourself inside the _CallDynaInst routine if you press F7 to step into the call of a dynamic method. Now you should know why this happens.

procedure       _CallDynaInst;
asm
...
CALL GetDynaMethod
...
JMP ESI
...
end;

To quickly get on to the dynamic method code, you should move the cursor down to the JMP ESI statement, press F4 (Run to Cursor), then press F7 (Step into). Now you’re in the dynamic method proper.

Accessing the DMT from Pascal code
While the compiler and RTL supplies all the DMT dispatching and lookup functionality we need, it could be fun to write our own routines that access these arrays. Given the type definitions above, we can write a few worker routines.

function GetDmt(AClass: TClass): PDmt;
var
Vmt: PVmt;
begin
Vmt := GetVmt(AClass);
if Assigned(Vmt)
then Result := Vmt.DynamicTable
else Result := nil;
end;

function GetDynamicMethodCount(AClass: TClass): integer;
var
Dmt: PDmt;
begin
Dmt := GetDmt(AClass);
if Assigned(Dmt)
then Result := Dmt.Count
else Result := 0;
end;

function GetDynamicMethodIndex(AClass: TClass; Slot: integer): integer;
var
Dmt: PDmt;
begin
Dmt := GetDmt(AClass);
if Assigned(Dmt) and (Slot < Dmt.Count)
then Result := Dmt.Indicies[Slot]
else Result := 0; // Or raise exception
end;

function GetDynamicMethodProc(AClass: TClass; Slot: integer): Pointer;
var
Dmt: PDmt;
DmtMethods: PDmtMethods;
begin
Dmt := GetDmt(AClass);
if Assigned(Dmt) and (Slot < Dmt.Count) then
begin
DmtMethods := @Dmt.Indicies[Dmt.Count];
Result := DmtMethods[Slot];
end
else
Result := nil; // Or raise exception
end;

The GetDmt routine returns a pointer to the DMT given a class reference (such as Instance.ClassType). The three other routines return the number of dynamic methods in a class and let us iterate through all the DMT indices and method pointers. Given these we can now write a routine that will dump information about all the dynamic (and message) methods of a class and all its parent classes.

procedure DumpDynamicMethods(AClass: TClass);
var
i : integer;
Index: integer;
MethodAddr: Pointer;
begin
while Assigned(AClass) do
begin
writeln('Dynamic methods in ', AClass.ClassName);
for i := 0 to GetDynamicMethodCount(AClass)-1 do
begin
Index := GetDynamicMethodIndex(AClass, i);
MethodAddr := GetDynamicMethodProc(AClass, i);
writeln(Format('%d. Index = %2d, MethodAddr = %p',
[i, Index, MethodAddr]));
end;
AClass := AClass.ClassParent;
end;
end;

We can also write the Pascal equivalent of System’s BASM GetDynaMethod to find a dynamic method given its DMT index.

function FindDynamicMethod(AClass: TClass; DMTIndex: TDMTIndex): Pointer;
// Pascal variant of the faster BASM version in System.GetDynaMethod
var
Dmt: PDmt;
DmtMethods: PDmtMethods;
i: integer;
begin
while Assigned(AClass) do
begin
Dmt := GetDmt(AClass);
if Assigned(Dmt) then
for i := 0 to Dmt.Count-1 do
if DMTIndex = Dmt.Indicies[i] then
begin
DmtMethods := @Dmt.Indicies[Dmt.Count];
Result := DmtMethods[i];
Exit;
end;
// Not in this class, try the parent class
AClass := AClass.ClassParent;
end;
Result := nil;
end;

Are we having fun yet? ;)


As a silly example we could use this routine to check if a class has any dynamic methods with a specific (negative) index or any message methods that handle a specific message id.

procedure DumpFoundDynamicMethods(AClass: TClass);
procedure Dump(DMTIndex: TDMTIndex);
var
Proc: Pointer;
begin
Proc := FindDynamicMethod(AClass, DMTIndex);
writeln(Format('Dynamic Method Index = %2d, Method = %p',
[DMTIndex, Proc]));
end;
begin
Dump(-1);
Dump(1);
Dump(13);
Dump(42);
end;

Conclusion
While message methods is a very elegant solution to the problem of handling arbitrary Windows messages without having to maintain an unwieldy case-statement, dynamic methods should be shunned. Now you should have a firm grasp of what dynamic methods are, how they work and why you should avoid them.

[Delphi syntax highlighting provided by DelphiDabbler PasH]

3 comments:

Craig said...

Great post, Hallvard.

Typo: "you might find yourself inside the _CallDynaInst routine if you press D7 to step into..." should read "F7"

Hallvard Vassbotn said...

Thanks, Craig! Fixed now.

Nice picture, btw.

BlackTigerX said...

great post as always, thanks for all this information



Copyright © 2004-2007 by Hallvard Vassbotn