June 30, 2012

Quake 3 Source Code Review: Virtual Machine (Part 4 of 5) >>

If previous engines delegated only the gameplay to the Virtual Machine, idtech3 heavily rely on them for essential tasks. Among other things:

Moreover their design is much more elaborated: They combine the security/portability of Quake1 Virtual Machine with the high performances of Quake2's native DLLs. This is achieved by compiling the bytecode to x86 instruction on the fly.

Trivia : The virtual machine was initially supposed to be a plain bytecode interpreter but performances were disappointing so the development team wrote a runtime x86 compiler. According to the .plan from Aug 16, 1999 this was done in one day.

Architecture

In Quake III a virtual machine is called a QVM: Three of them are loaded at any time:


QVM Internals

Before describing how the QVMs are used, let's check how the bytecode is generated. As usual I prefer drawing with a little bit of complementary text:


quake3.exe and its bytecode interpreter are generated via Visual Studio but the VM bytecode takes a very different path:

  1. Each .c file (translation unit) is compiled individually via LCC.
  2. LCC is used with a special parameter so it does not output a PE (Windows Portable Executable) but rather its Intermediate Representation which is text based stack machine assembly. Each file produced features a text, data and bss section with symbols exports and imports.
  3. A special tool from id Software q3asm.exe takes all text assembly files and assembles them together in one .qvm file. It also transform everything from text to binary (for speed in case the native converted cannot kick in). q3asm.exe also recognize which methods are system calls and give those a negative symbol number.
  4. Upon loading the binary bytecode, quake3.exe converts it to x86 instructions (not mandatory).

LCC Internals

Here is a concrete example starting with a function that we want to run in the Virtual Machine:


   
    extern int variableA;
    
    int variableB;
    
    int variableC=0;
    
    int fooFunction(char* string){
	    
        return variableA + strlen(string);
        
    }
    
    


Saved in module.c translation unit, lcc.exe is called with a special flag in order to avoid generating a Windows PE object but rather output the Intermediate Representation. This is the LCC .obj output matching the C function above:


   
    data
    export variableC
    align 4
    LABELV variableC
    byte 4 0
    export fooFunction
    code
    proc fooFunction 4 4
    ADDRFP4 0
    INDIRP4
    ARGP4
    ADDRLP4 0
    ADDRGP4 strlen
    CALLI4
    ASGNI4
    ARGP4 variableA
    INDIRI4
    ADDRLP4 0
    INDIRI4
    ADDI4
    RETI4
    LABELV $1
    endproc fooFunction 4 4
    import strlen
    bss
    export variableB
    align 4
    LABELV variableB
    skip 4
    import variableA

    

A few observations:

Such a text file is generated for each .c in the VM module.

q3asm.exe Internals

q3asm.exe takes the LCC Intermediate representation text files and assembles them together in a .qvm file:


Several things to notice:


QVM: How it works

Again a drawing first illustrating the unique entry point and unique exit point that act as dispatch:


A few details:

Messages (Quake3 -> VM) are send to the Virtual Machine as follow:

You can find the list of Message that can be sent to the Client VM and Server VM (at the bottom of each file).

System calls (VM -> Quake3) go out this way:

You can find the list of system calls that are provided by the Client VM and the Server VM (at the top of each file).

Trivia : Parameters are always very simple types: Either primitives types (char,int,float) or pointer to primitive types (char*,int[]). I suspect this was done to minimize issues due to struct alignment between Visual Studio and LCC.

Trivia : Quake3 VM does not perform dynamic linking so a developer of a QVM mod had no access to any library, not even the C Standard Library (strlen, memset functions are here...but they are actually system calls). Some people still managed to fake it with preallocated buffer: Malloc in QVM !!

Unprecedented freedom

With the kind of task offset to the Virtual Machine the modding community was able to perform much more than modding. The prediction system was rewritten with "backward reconciliation" in Unlagged by Neil "haste" Toronto.

Productivity issue and solution

With such a long toolchain, developing VM code was difficult:

So idTech3 also have the ability to load a native DLL for the VM parts and it solved everything:



Overall the VM system is very versatile since a Virtual Machine is capable of running:

Recommended readings

Next part

The A.I Model

Comments

 

Fabien Sanglard @2012