Home Made Java Virtual Machine ~ GNIIT Solutions

Home Made Java Virtual Machine

INTRODUCTION

Back in year 2004 I had to choose a thesis topic as a prerequisite of completion of my undergraduate course in Computer Science and Engineering. I had choosen Process Migration. And our teacher Mahmud Shahriar Hossain agreed to supervise my work. My partner was Md. Helal Uddin. As part of the thesis I had to implement a Java Virtual Machine. I wanted to write an article since then. But it never actually happened. Today (March 2) is my birth day and I want to start it. The virtual machine is also used in my new project Morpheus - a prototype of Silverlight 1.1. The seminar presentation downloadable from above link shows how a JVM works. You may also look at the JVM source code from above link. Please notethat most the implementation decision taken may not match with other commercially available JVM implementation. Whenever JVM Spec is found to say nothing, the most easiest approach is taken to save time.

JAVA VIRTUAL MACHINE PARTS

CLASS FILE STRUCTURE

The java virtual machine needs an application that is made up of collection of java classes. At the beginning of any class there is a defined structure like JavaClassFileFormat.

Hide Copy Code

struct  JavaClassFileFormat
{
    u4 magic;
    u2 minor_version;
    u2 major_version;
    u2 constant_pool_count;
    cp_info **constant_pool; //[constant_pool_count-1]; 
    u2 access_flags;
    u2 this_class;
    u2 super_class;
    u2 interfaces_count;
    u2* interfaces; //[interfaces_count]; 
    u2 fields_count;
    field_info_ex *fields; //[fields_count]; 
    u2 methods_count;
    method_info_ex* methods; //[methods_count]; 
    u2 attributes_count;
    attribute_info** attributes; //[attributes_count]; 
};

Following are the structures used in the format. They represents constant pool (constant values used in class files), fields, methods and attributes in a class file. I'll describe them in details later.

Hide Shrink

Copy Code

struct cp_info
{
    u1 tag;
    u1* info;
};

struct field_info
{
    u2 access_flags;
    u2 name_index;
    u2 descriptor_index;
    u2 attributes_count;
    attribute_info* attributes; //[attributes_count]; 
};

struct method_info
{
    u2 access_flags;
    u2 name_index;
    u2 descriptor_index;
    u2 attributes_count;
    attribute_info* attributes; //[attributes_count]; 
};

struct attribute_info
{
    u2 attribute_name_index;
    u4 attribute_length;
    u1* info;//[attribute_length];
};

We first load the class file in memory as raw byte and then use JavaClass object to parse the raw bytes and identify the fields, methods, exception table etc. The JavaClass class represent a class in memory in structured form. It holds a pointer to the raw byte stream that was loaded from class file.

JAVA CLASS IN MEMORY

Here we just inherit the JavaClassFileFormat for simplicity of storing the values in in memory class representation. We must parse the raw class file in memory to get the values forJavaClassFileFormat fields.

Hide Shrink

Copy Code

class JavaClass: public JavaClassFileFormat
{
public:
    JavaClass(void);
    virtual ~JavaClass(void);

public:
    virtual BOOL LoadClassFromFile(CString lpszFilePath);
    void SetByteCode(void* pByteCode);

    BOOL ParseClass(void);
    BOOL ParseInterfaces(char* &p);
    BOOL ParseFields(char* &p);
    BOOL ParseMethods(char* &p);
    BOOL ParseAttributes(char* &p);
    BOOL GetConstantPool(u2 nIndex, cp_info& const_pool);

    BOOL GetStringFromConstPool(int nIndex,CString& strValue);
    CString GetName(void);
    CString GetSuperClassName(void);
    BOOL ParseMethodCodeAttribute(int nMethodIndex, Code_attribute* pCode_attr);
    int GetMethodIndex(CString strMethodName, CString strMethodDesc,
          JavaClass* &pClass);
    int GetFieldIndex(CString strName, CString& strDesc);
    void SetClassHeap(ClassHeap *pClassHeap){this->m_pClassHeap=pClassHeap;}
    virtual u4 GetObjectSize(void);
    virtual u4 GetObjectFieldCount(void);
    JavaClass* GetSuperClass(void);
    BOOL CreateObject(u2 index, ObjectHeap *pObjectHeap, Object& object);
    BOOL CreateObjectArray(u2 index, u4 count, ObjectHeap *pObjectHeap,
       Object& object);
private:
    size_t m_nByteCodeLength;
    void *m_pByteCode;
    u2    m_nObjectFieldsCount;
    BOOL ParseConstantPool(char* &p);
    int GetConstantPoolSize(char* p);
    ClassHeap *m_pClassHeap;
};

To do that we first load the file in memory and then call the ParseClass method which is shown in the next section.

CLASS LOADER

As there are some variable length fields it is not possible to directly load the structure. So we load the values one by one. First we load the value of magic which is an unsigned integer (u4) value. It must be value of 0xCafeBabe. If it is not the class file may be either corrupted or not a java class file at all. Then we load other values and structures. To load structures we first load the count and then load the structure. For example first we load short (u2) value constant_pool_count and then load that number of constant pool. To parse I used definitions getu4(p) or similar which just picks 4 bytes starting at p and returns the unsigned int value. To parse structures hare use sepaate methods likeParseConstantPool. It takes the reference of the byte stream pointer and increments in that class. I did this only for simplicity. It would be more readable if I'd return the total length and increent in ParseClass method but that would me less managable.

Hide Shrink

Copy Code

BOOL JavaClass::ParseClass(void )
{
    //just to be safe 
    if (m_pByteCode==NULL ||
            m_nByteCodeLength < sizeof (JavaClassFileFormat)+20)
        return FALSE;
    char *p=( char *)m_pByteCode;
    magic = getu4(p); p+=4;
    ASSERT(magic == 0xCAFEBABE);

    if(magic != 0xCAFEBABE)
        return FALSE;

    minor_version=getu2(p); p+=2;
    major_version=getu2(p); p+=2;
    constant_pool_count=getu2(p); p+=2;

    if (constant_pool_count>0)
        ParseConstantPool(p);

    access_flags=getu2(p); p+=2;
    this_class=getu2(p); p+=2;
    super_class=getu2(p); p+=2;
    interfaces_count=getu2(p); p+=2;

    if (interfaces_count>0)
        ParseInterfaces(p);

    fields_count=getu2(p); p+=2;

    if (fields_count > 0)
        ParseFields(p);

    methods_count = getu2(p);p+=2;

    if (methods_count > 0)
    {
        ParseMethods(p);
    }
    attributes_count = getu2(p);p+=2;

    if (attributes_count > 0)
        ParseAttributes(p);

    return 0;
}

CONSTANT POOL

In a java class several constant value is stored. It stores numeric, string and reference values in a pool and those are used in machine codes known as 'Java Byte Code'. Constant pool contains constant_pool_count items in a sequential list of following structure.

Hide Copy Code

struct cp_info
{
    u1 tag;
    u1* info;
};

Constant pool information structure starts with one byte of tag information that indicates the type of the constant pool. Constant pool structure length is variable depending on the type of constant. Constant pool tag value can be one of the following values depending on the type of constant.

Hide Copy Code

#define CONSTANT_Integer  3
#define CONSTANT_Float  4
#define CONSTANT_Long  5
#define CONSTANT_Double  6
#define CONSTANT_Utf8  1
#define CONSTANT_String  8

#define CONSTANT_Class  7
#define CONSTANT_Fieldref  9
#define CONSTANT_Methodref  10
#define CONSTANT_InterfaceMethodref  11
#define CONSTANT_NameAndType  12

Depending on the value of tag we can cast the cp_info structure in more precise structures listed here.

CONSTANT_Integer_info

If tag value equals CONSTANT_Integer in cp_info structure then it is an integer constant. We can cast the cp_info structure in following structure.

Hide Copy Code

struct CONSTANT_Integer_info {
    u1 tag;
    u4 bytes;
};

This structure does not have any reference to any other constant. It represents direct 4 byte integer value.

CONSTANT_Float_info

If tag value equals CONSTANT_Float in cp_info structure then it is a float constant. We can cast the cp_info structure in following structure.

Hide Copy Code

struct CONSTANT_Float_info {
    u1 tag;
    u4 bytes;
};

It is a direct value constant without any reference.

CONSTANT_Long_info

If tag value equals CONSTANT_Long in cp_info structure then it is a long constant. We can cast the cp_info structure in following structure.

Hide Copy Code

struct CONSTANT_Long_info {
    u1 tag;
    u4 high_bytes;
    u4 low_bytes;
};

It is a direct value constant without any reference. It uses two four bute values to construct the 8 byte long value.

CONSTANT_Long_info

If tag value equals CONSTANT_Double in cp_info structure then it is a double constant. We can cast the cp_info structure in following structure.

Hide Copy Code

struct CONSTANT_Double_info {
    u1 tag;
    u4 high_bytes;
    u4 low_bytes;
};

It is a direct value constant without any reference. It uses two four bute values to construct the 8 byte double value.

CONSTANT_Utf8_info

If tag value equals CONSTANT_Utf8 in cp_info structure then it is a utf8 string constant. We can cast the cp_info structure in following structure.

Hide Copy Code

struct CONSTANT_Utf8_info {
    u1 tag;
    u2 length;
    u1* bytes;//[length];
};

It is a direct value constant without any reference. The short value length defines the length of the byte array followed by length number of bytes.

CONSTANT_String_info

If tag value equals CONSTANT_String in cp_info structure then it is a string reference constant. We can cast the cp_info structure in following structure.

Hide Copy Code

struct CONSTANT_String_info {
    u1 tag;
    u2 string_index;
};

It is a reference value constant. The short value string_index refers to a CONSTANT_Utf8_infoindex in the constant pool.

CONSTANT_Class_info

If tag value equals CONSTANT_Class in cp_info structure then it is a class reference constant. We can cast the cp_info structure in following structure.

Hide Copy Code

struct CONSTANT_Class_info {
     u1 tag;
       u2 name_index;
};

It is a reference value constant. The short value name_index refers to a CONSTANT_Utf8_info index in the constant pool that is the fully qualified name (ie java/lang/String) of the class- dot replaced by slash.

CONSTANT_Fieldref_info

If tag value equals CONSTANT_Fieldref in cp_info structure then it is a field reference constant. We can cast the cp_info structure in following structure.

Hide Copy Code

struct CONSTANT_Fieldref_info {
    u1 tag;
    u2 class_index;
    u2 name_and_type_index;
};

It is a reference value constant. The short value class_index refers to a CONSTANT_Class_infoindex in the constant pool and name_and_type_index refers to a string index in the constant pool that is the fully qualified name (ie java/lang/String@valueOf(F)Ljava/lang/String;) of the class- dot replaced by slash.

CONSTANT_Methodref_info

If tag value equals CONSTANT_Methodref in cp_info structure then it is a method reference constant. We can cast the cp_info structure in following structure.

Hide Copy Code

struct CONSTANT_Methodref_info {
    u1 tag;
    u2 class_index;
    u2 name_and_type_index;
};

CONSTANT_InterfaceMethodref_info

If tag value equals CONSTANT_InterfaceMethodref in cp_info structure then it is an interface method reference constant. We can cast the cp_info structure in following structure.

Hide Copy Code

struct CONSTANT_InterfaceMethodref_info {
    u1 tag;
    u2 class_index;
    u2 name_and_type_index;
};

CONSTANT_NameAndType_info

If tag value equals CONSTANT_NameAndType in cp_info structure then it is an interface methodreference constant. We can cast the cp_info structure in following structure.

Hide Copy Code

struct CONSTANT_NameAndType_info {
    u1 tag;
    u2 name_index;
    u2 descriptor_index;
};

It is a reference value constant. The short value name_index refers to a string index in the constant pool and descriptor_index refers to another string index in the constant pool.

Parsing constant pool

Here we set the values of constant pool list pointers. When we need to retrieve the actual value we look at the tag and pick the value directly.

Hide Copy Code

BOOL JavaClass::ParseConstantPool(char* &p)
{
    constant_pool = new cp_info*[constant_pool_count-1];
    if(constant_pool == NULL) return FALSE;
    for(int i=1;i<constant_pool_count;i++)
    {
        //We set the constant pointer here
        constant_pool[i]=(cp_info*)p;

        //We now calculate constant size. If it is an integer we get size = 5        
        int size = GetConstantPoolSize(p);
        p+= size;

        // If constant type is long or double constant pool takes two entries.
        // Second entry is not used by virtual machine but kept NULL to walk
        // constant pool correctly.
        if(constant_pool[i]->tag == CONSTANT_Long || constant_pool[i]->tag ==
          CONSTANT_Double)
        {
            constant_pool[i+1]=NULL;
            i++;
        }
    }
    return TRUE;
}

INTERFACES

In the interfaces field of a class there are interfaces_count number of short (u2) values. Each value is a reference to a constant pool entry of type CONSTANT_Class. We parse them and store in our in-memory object-

Hide Copy Code

BOOL JavaClass::ParseInterfaces(char* &p)
{
    interfaces = new u2[interfaces_count];
    for(int i=0;i<interfaces_count;i++)
    {
        interfaces[i] = getu2(p); p+=2;
    }

    return TRUE;
}

FIELDS

A class may contain zero, one or more fields. The actual number is stored in the fields_count field. A list of field_info structure followes this value.

Hide Copy Code

struct field_info
{
    u2 access_flags;
    u2 name_index;
    u2 descriptor_index;
    u2 attributes_count;
    attribute_info* attributes;//[attributes_count];
};

The short value access_flags describes the allowed field access. Here is the possible access flags values which is shared also by methods and classes-

Hide Copy Code

#define ACC_PUBLIC  0x0001
/*Declared public; may be accessed from outside its package.  */

#define ACC_PRIVATE  0x0002
/*Declared private; accessible only within the defining class.  */

#define ACC_PROTECTED  0x0004
/*Declared protected; may be accessed within subclasses.  */

#define ACC_STATIC  0x0008  /*Declared static.  */

#define ACC_FINAL  0x0010
/*Declared final; may not be overridden.  */

#define ACC_SYNCHRONIZED  0x0020
/*Declared synchronized; invocation is wrapped in a monitor lock.  */

#define ACC_NATIVE  0x0100
/*Declared native; implemented in a language other than Java.  */

#define ACC_ABSTRACT  0x0400
/*Declared abstract; no implementation is provided.  */

#define ACC_STRICT  0x0800
/*Declared strictfp; floating-point mode is FP-strict  */

The name_index and descriptor_index are reference to two constant pool of type utf8 string. Theattributes field defined the attributes of the field. Attributes are described later. Here is how we parse fields in a class's raw bytes-

Hide Copy Code

BOOL JavaClass::ParseFields(char* &p)
{
    fields = new field_info_ex[fields_count];
    if(fields == NULL) return FALSE;

    for(int i=0;i<fields_count;i++)
    {
        fields[i].pFieldInfoBase = (field_info*)p;

        fields[i].access_flags= getu2(p); p+=2; //access_flags
        fields[i].name_index= getu2(p);p+=2; //
        fields[i].descriptor_index= getu2(p);p+=2; //
        fields[i].attributes_count=getu2(p); p+=2;

        if(fields[i].attributes_count>0)
        {
            //skip attributes - we do not need in simple cases
            for(int a=0;a<fields[i].attributes_count;a++)
            {
                u2 name_index=getu2(p); p+=2;
                //printf("Attribute name index = %d\n", name_index);
                u4 len=getu4(p);p+=4;
                p+=len;
            }
        }
    }
    return TRUE;
}

METHODS

A java class file may contain arbitrary number of methods. The count is stored in methods_countmember of class file structure. As it is a two byte field the theoritical upper limit is essentially 2^16. Like fields info, method info structure contains access flags, name index, descriptor index, and attributes.

Hide Copy Code

struct method_info
{
    u2 access_flags;
    u2 name_index;
    u2 descriptor_index;
    u2 attributes_count;
    attribute_info* attributes;//[attributes_count];
};

Method body (if any) is stored in an attribute named Code- which contains the actual 'Java Byte Code'. Here is how we parse methods in out virtual machine-

Hide Shrink

Copy Code

//TODO: Cashe the findings here
BOOL JavaClass::ParseMethods(char* &p)
{
    methods = new method_info_ex[methods_count];

    if(methods == NULL) return FALSE;

    for(int i=0;i<methods_count;i++)
    {
        //methods[i] = new method_info_ex;
        methods[i].pMethodInfoBase=(method_info*)p;
        methods[i].access_flags= getu2(p);    p+=2; //access_flags
        methods[i].name_index = getu2(p); p+=2; //name_index
        methods[i].descriptor_index= getu2(p); p+=2; //descriptor_index
        methods[i].attributes_count=getu2(p); p+=2;

        CString strName, strDesc;
        GetStringFromConstPool(methods[i].name_index, strName);
        GetStringFromConstPool(methods[i].descriptor_index, strDesc);

        TRACE(_T("Method = %s%s\n"),strName, strDesc);

        TRACE("Method has total %d attributes\n",methods[i].attributes_count);

        methods[i].pCode_attr=NULL;
        if(methods[i].attributes_count>0)
        {
            //skip attributes
            for(int a=0;a<methods[i].attributes_count;a++)
            {
                u2 name_index=getu2(p); p+=2;

                TRACE("Attribute name index = %d\n", name_index);
                u4 len=getu4(p);p+=4;
                p+=len;
            }

            methods[i].pCode_attr = new Code_attribute;
            ParseMethodCodeAttribute(i, methods[i].pCode_attr);
        }
    }

    return TRUE;
}

In case of method structure ( and also same in fields structure) I have used method_info_ex instead of method_info structure. This extended structure on pointer to pint to raw method info in the in-memory bytestream of class file. Here with other fields we parse the Code attribute. The details id given later in attributes section.

ATTRIBUTES

In most classes attributes takes most of the space in file. Class has attributes, method has attributes, field has attributes. The raw definition of attribute is like this-

Hide Copy Code

struct attribute_info
{
    u2 attribute_name_index;
    u4 attribute_length;
    u1* info;//[attribute_length];
};

The attribute_name_index field is the reference index in the constant pool for string type constant. The attribute_length field is the length of info field- which is another structure depending on the type/ name of the attribute. An arrtibute can be a constant value, exception table or code type.

Constant value attribute

Hide Copy Code

struct ConstantValue_attribute {
    u2 attribute_name_index;
    u4 attribute_length;
    u2 constantvalue_index;
};

Code Attribute

It is also a method specific attribute. The name of the attribute is hardcoded as 'Code'. This attribute has maximum stack and maximum local values of the method. The code field is variable length defined by code_length and it contains the actual 'Java Byte Code'.

Hide Copy Code

struct Code_attribute {
    u2 attribute_name_index;
    u4 attribute_length;
    u2 max_stack;
    u2 max_locals;
    u4 code_length;
    u1* code;//[code_length];
    u2 exception_table_length;
    Exception_table* exception_table;//[exception_table_length];
    u2 attributes_count;
    attribute_info* attributes;//[attributes_count];
};

Exception table structure

This structure is used to define the exception table for methods. The exception table describes the exception handler depending on the program counter value or offset of byte code. The handler code is also an offset in the byte code.

Hide Copy Code

struct Exception_table
{
    u2 start_pc;
    u2 end_pc;
    u2  handler_pc;
    u2  catch_type;
};

The field catch_type is a reference to a constant pool entry that describes the type of the exception- for example reference to a class named 'java/lang/Exception'.

JAVA INSTRUCTION SET

Java has more than 200 instructions. The java language file, when compiled, is converted to a class file that contains intrtuctions as byte codes. If we have a method like this-

Hide Copy Code

public int mul(int a, int b)
{
    return a * b;
}

we will get this method in byte code attribute like this- (java has also assembly like representation for instructions to represent byte codes in human readable format)

Hide Copy Code

Code Attribute:
  Stack=2, Locals=3, Args_size=3,  Code Length = 4
  Code:
  0:   iload_1
  1:   iload_2
  2:   imul
  3:   ireturn

Here if we follow the instructions we go like this:

Hide Copy Code

0: Push (load) the local variable 1 on stack
1: Push the local variable 2 on stack
3: Pop two values from stack, do an integer multipucation and push the result
4: Return the integer value from stack top.

What we need to do in our virtual machine is load classes and follow the instructions in methods. There are methods to create new objects, to call methods of object. It is also possible to call native methods from a java method. Please refer to source code for most other codes (opcodes.h) or JavaVirtual Machine Specification for a complete list.

CLASS HEAP

In the virtual machine we must maintain a heap where the class definition objects can be stored. I have implemented it as a separate heap for simplity. In this heap we load classes from files and store it in the heap. The ClassHeap class is responsible for maintaining the class heap in meory.

Hide Copy Code

class ClassHeap
{
    CMapStringToPtr m_ClassMap;
    FilePathManager *pFilePathManager;
public:
    ClassHeap(void);
public:
    virtual ~ClassHeap(void);
public:
    BOOL AddClass(JavaClass* pJavaClass);
    JavaClass* GetClass(CString strClassName);
    BOOL LoadClass(CString strClassName, JavaClass *pClass);


};

We store JavaClass objects pointer in the m_ClassMap member using the class name as key.

OBJECT HEAP

Object heap is virtual machine's RAM. All objects are created on object heap and its reference can be stored in another object or on the stack. Any reference is stored in an union type storage namedVariable. Any field of a class can be represented using variable object. Anything can be stored in aVariable object.

Hide Copy Code

union Variable
{
    u1 charValue;
    u2 shortValue;
    u4 intValue;
    f4 floatValue;
    LONG_PTR ptrValue;
    Object object;
};

Object creation on heap is described later in detail.

Virtual Machine Stack

Java instruction set is designed in such a way that it can work with very limited set of registers. Instead it uses its stack very extensively. The JVM stack element is one item regardless of - it may be primitive ype or object type. Only long and double type takes two stack spaces. The 'Execution Engine' maintains the JVM stack. For example when the execution engine executes iadd instruction it pops two numeric values from the stack and add the values and pushes the result on the stack. The virtual machine has empty stack initially and the stack is populated after the initial thread and the initial method is started for execution. Each method instruction is allowed to operate on stack within a limited boundary of the stack. The compiler sets the upper limit (top) as max_stack field of each methods Code attribute. The lower limit is the top+1 stack position of previous method. This boundary of stack is named as Stack Frame of that method.

The Stack Frame

As we mentioned each methods boundary in the JVM stack is known as 'Stack Frame'. Each stack frame reserves positions for the parameters and local variables of that method. If it is not a static method the first parameter is the object reference ( the this parameter) of type of the class of the method. The Execution Engine operates between the frame and when the method returns a value it pops every element from the current frame including this reference and pushes the return value (if method is not void return type) value on the frame of previous frames top. To keep the implementation simple I used slightly different methodology. I used stack of stack. Each frame is stack type and it is pushed on the JVM stack. The stack grows on method invocation and shrinks on method return.

Local Variables

In a stack frame local variables takes positions from zero to max_locals - 1 positions or less. If the method is not static the object takes the position zero and other locals follow it. Local variables are accessed using putfield and getfield instructions.

Native method stack

Unlike virtual machine stack, native methods stack is not maintained by JVM. It is maintained by the native system. Actually while a native method is being executed the virtual machine component that was managing the java thread waits until the native method completes and returns.

RUNTIME ENVIRONMENT

Each java thread has its own frame stack. All java threads in a process share common class heap and object heap. This things are bundled together in a RuntimeEnvironment object and carried among the execution engine components.

Hide Copy Code

class RuntimeEnvironment
{
   public:
       Frame *pFrameStack;
       ClassHeap *pClassHeap;
       ObjectHeap *pObjectHeap;
};

EXECUTION UNIT

This is the main module of the JVM. It interprates the instructons. Advanced JVMs may use JIT compiler to convert java instructions into native instruction. But I did not do that because of the complexity of the JIT compiler. When a JVM starts it usually takes initial class name as parameter. Our JVM also takes class name as a parameter. The class heap is then requested to load that class. Then the JVM finds its main method (it can be any name like Entry in case of my first implementation), creates the initial stack frame and requests the execution engine to start execution. The heart of the Execution Unit is the Execute method. Here is the skeleton:

Hide Shrink

Copy Code

u4 ExecutionEngine::Execute(Frame* pFrameStack)
{
    ASSERT(pFrameStack);
    ASSERT(pFrame);

    Frame* pFrame=&pFrameStack[0];

    DbgPrint(_T("Current Frame %ld Stack start at %ld\n"),
            pFrame-Frame::pBaseFrame,     pFrame->stack-Frame::pOpStack );

    if(pFrame->pMethod->access_flags & ACC_NATIVE)
    {
        ExecuteNativeMethod(pFrame);
        return 0;
    }

    u1 *bc=pFrame->pMethod->pCode_attr->code + pFrame->pc;

    i4 error=0;
    JavaClass *pClass = pFrame->pClass;

    CString strMethod;
    pClass->GetStringFromConstPool(pFrame->pMethod->name_index, strMethod);

    DbgPrint(_T("Execute At Class %s Method %s \n"), pClass->GetName(), strMethod);
    i4 index=0;
    i8 longVal;
    while(1)
    {
        switch(bc[pFrame->pc])
        {
        case nop: //Do nothing
            pFrame->pc++;
            break;

        //Integer Arithmetic 
        case iadd: //96 : Pop two int values from stack add them and push result
            pFrame->stack[pFrame->sp-1].intValue=pFrame->stack[pFrame->sp-1].intValue
                    + pFrame->stack[pFrame->sp].intValue;
            pFrame->sp--;
            pFrame->pc++;
            break;

        //Method return instructions            
        case ireturn:
            //172 (0xac) : Pop everything from stack and push return value (int)
            pFrame->stack[0].intValue=pFrame->stack[pFrame->sp].intValue;
            return ireturn; // here we break the while loop
            break;

        // Method invokation Instructions

        // Here actually we do a recursive call to Execute
        // to keep things simple- after the java method return we
        // also return from Execute- some memory waste for simplicity
        case invokevirtual: //182: Invoke a virtual method. 
            // The object reference and parameters are on stack by java instructions
            ExecuteInvoke(pFrame, invokevirtual);
            pFrame->pc+=3;
            break;
        }

        //Instructions that deal with objects

        case _new:// 187 (0xbb)
            ExecuteNew(pFrame);
            pFrame->pc+=3;
            break;
        case putfield: //181 (0xb5): Set field in object from stack top
            PutField(pFrame);
            pFrame->sp-=2;
            pFrame->pc+=3;
            break;

        case getfield:
            //180 (0xb4) Fetch field from object and push on stack
            GetField(pFrame);
            pFrame->pc+=3;
            break;
    }
    return 0;
}

Creating object on Object Heap

An object is usually created by JVM when a new or newarray or multinewarray instruction is executed. When a virtual machine creates an object it first calculate the size of the object. To calculate the object size we we first take the fields_count value in the class structure then we add its super classes fields_count value with it then we add super classes super classes fields_count and so on recursively until we reach the final base class java.lang.Object. This way we calculate total fields of the object and add one with it that holds the class pointer in the ClassHeap. Now we multiply thesizeof(Variable) to the count and get number of bytes required for the object. We now allocate the required bytes and return the pointer to that memory in a Variable object on the stack top. Here is the implementation.

Hide Shrink

Copy Code

int ExecutionEngine::ExecuteNew(Frame* pFrame)
{
    pFrame->sp++;
    u1 *bc=pFrame->pMethod->pCode_attr->code;
    u2 index=getu2(&bc[pFrame->pc+1]);
    if(!pFrame->pClass->CreateObject(
        index, this->pObjectHeap, pFrame->stack[pFrame->sp].object))
        return -1;
    return 0;
}

BOOL JavaClass::CreateObject(u2 index, ObjectHeap *pObjectHeap, Object& object)
{
    char *cp=(char*)this->constant_pool[index];
    ASSERT(cp[0] == CONSTANT_Class);
    ASSERT(pObjectHeap);
    if(cp[0] != CONSTANT_Class)
        return FALSE;

    u2 name_index=getu2(&cp[1]);
    CString strClassName;
    if(!this->GetStringFromConstPool(name_index, strClassName))
        return FALSE;

    JavaClass *pNewClass=this->m_pClassHeap->GetClass(strClassName);
    if(pNewClass == NULL) return FALSE;
    object=pObjectHeap->CreateObject(pNewClass);
    return TRUE;
}

Setting or getting value in object

The putfield instruction is used to set a value (from stack) of a field and the getfield instruction is used to load a variables value on the stack. When the execution engine needs to execute a getfieldinstruction it pops two values from the stack. One value is the object pointer another is field position (zero based index). Here is my implementation:

Hide Copy Code

// Gets value or reference from stack and set in object
void ExecutionEngine::PutField(Frame* pFrameStack)
{
    u2 nIndex = getu2(
        &pFrameStack[0].pMethod->pCode_attr->code[pFrameStack[0].pc+1]);
    Variable obj=pFrameStack[0].stack[pFrameStack[0].sp-1];
    Variable value=pFrameStack[0].stack[pFrameStack[0].sp];
    Variable *pVarList=this->pObjectHeap->GetObjectPointer(obj.object);
    pVarList[nIndex+1]=value;
}

//Gets the value from variable and push on stack
void ExecutionEngine::GetField(Frame* pFrame)
{
    //TODO: Bug check for long and double
    u2 nIndex = getu2(
        &pFrame->pMethod->pCode_attr->code[pFrame->pc+1]);
    Variable obj=pFrame->stack[pFrame->sp];
    Variable *pVarList=this->pObjectHeap->GetObjectPointer(obj.object);
    pFrame->stack[pFrame->sp]=pVarList[nIndex+1];
}

Invoking method

When execution engine requires a method invocation it needs to creates a new 'Stack Frame' and thepc or Program Counter is set to the first byte of the methods byte code. Before that, the execution engine must save the current methods pc so that it can come back to resume method execution after the callee method returns. Here is our implementation. Please note how we handle static method invocation - simply we do not have the this reference on our stack.

Hide Shrink

Copy Code

void ExecutionEngine::ExecuteInvoke(Frame* pFrameStack, u2 type)
{
    u2 mi=getu2(
        &pFrameStack[0].pMethod->pCode_attr->code[pFrameStack[0].pc+1]);
    Variable objectRef = pFrameStack[0].stack[pFrameStack[0].sp];
    char *pConstPool = (char *)pFrameStack[0].pClass->constant_pool[mi];

    ASSERT(pConstPool[0] == CONSTANT_Methodref);

    u2 classIndex = getu2(&pConstPool[1]);
    u2 nameAndTypeIndex = getu2(&pConstPool[3]);

    //get class at pool index 
    pConstPool =
        (char *)pFrameStack[0].pClass->constant_pool[classIndex];

    ASSERT(pConstPool[0] == CONSTANT_Class);

    u2 ni=getu2(&pConstPool[1]);

    CString strClassName;
    pFrameStack[0].pClass->GetStringFromConstPool(
            ni, strClassName);


    JavaClass *pClass=pClassHeap->GetClass(strClassName);
    pConstPool =
        (char *)pFrameStack[0].pClass->constant_pool[nameAndTypeIndex];

    ASSERT(pConstPool[0] == CONSTANT_NameAndType);

    method_info_ex method;
    method.name_index = getu2(&pConstPool[1]);
    method.descriptor_index = getu2(&pConstPool[3]);
    method.access_flags = 0; // set later

    CString strName, strDesc;
    pFrameStack[0].pClass->GetStringFromConstPool(
        method.name_index, strName);
    pFrameStack[0].pClass->GetStringFromConstPool(
        method.descriptor_index, strDesc);


    JavaClass *pVirtualClass=pClass;
    int nIndex=pClass->GetMethodIndex(strName, strDesc, pVirtualClass);

    memset(&pFrameStack[1],0,sizeof(pFrameStack[1]));
    pFrameStack[1].pMethod = &pClass->methods[nIndex];

    method.access_flags = getu2((char *)pFrameStack[1].pMethod);
    if( ACC_SUPER & method.access_flags)
    {
        pFrameStack[1].pClass = pVirtualClass->GetSuperClass();
    }
    else
    {
        pFrameStack[1].pClass=pVirtualClass;
    }

    int params=GetMethodParametersStackCount(strDesc)+1;

    //invokestatic - there is no this pointer 
    if(type==invokestatic) params--;
    // else invokevirtual has this pointer

    int nDiscardStack =params;
    if(pFrameStack[1].pMethod->access_flags & ACC_NATIVE)
    {
    }
    else
    {
        nDiscardStack+=pFrameStack[1].pMethod->pCode_attr->max_locals;
    }

    pFrameStack[1].stack =
    &Frame::pOpStack[pFrameStack->stack-Frame::pOpStack+pFrameStack[0].sp-params+1];
    pFrameStack[1].sp=nDiscardStack-1;

    this->Execute(&pFrameStack[1]);

    //if returns then get on stack    
    if(strDesc.Find(_T(")V")) < 0)
    {
        nDiscardStack--;
    }
    //Before we return to caller make the stack of caller right
    pFrameStack[0].sp-=nDiscardStack;
}

Invoking native method

In a java class a method may be marked as native-

Hide Copy Code

public class Test
{
    public native void Print(string message);
}

In byte code ACC_NATIVE is set in the access_flags field of the method_info structure. We decide here like this:

Hide Copy Code

if(pFrame->pMethod->access_flags & ACC_NATIVE)
{
    ExecuteNativeMethod(pFrame);
    return 0;
}

Each native method usually has a fixed predefined prototype. Here is the type definitation for our JVM:

Hide Copy Code

typedef Variable (*pNativeMethod)(RuntimeEnvironment* pRuntimeEnvironment);

Here is how we handle native methods in the JVM:

Hide Shrink

Copy Code

u4 ExecutionEngine::ExecuteNativeMethod(Frame* pFrameStack)
{
    ASSERT(pFrameStack);

    ASSERT(pFrame->pMethod->access_flags & ACC_NATIVE);
    Frame* pFrame=&pFrameStack[0];

    JavaClass *pClass = pFrame->pClass;
    CString strClassName, strMethod, strDesc, strSignature;
    strClassName=pClass->GetName();
    pClass->GetStringFromConstPool(
        pFrame->pMethod->name_index, strMethod);
    pClass->GetStringFromConstPool(
        pFrame->pMethod->descriptor_index, strDesc);
    DbgPrint(_T("Execute At Class %s Method %s%s  \n")
        ,strClassName , strMethod, strDesc);
    strSignature=strClassName+_T("@")+strMethod+strDesc;
    pNativeMethod pNativeMethod=GetNativeMethod(strSignature);
    RuntimeEnvironment rte;
    rte.pFrameStack=pFrameStack;
    rte.pClassHeap= pClassHeap;
    rte.pObjectHeap= pObjectHeap;

    if(pNativeMethod == NULL)
    {
        // what should I do here??
        // System Panic??
        ASSERT(FALSE);
        return -1;
    }
    else
    {
        //Here we go native
        Variable retVal = pNativeMethod(&rte);

        //if returns then get on stack    
        if(strDesc.Find(_T(")V")) < 0)
        {
            pFrame->stack[0]=retVal;
        }
    }
    return 0;
}

Here is the implementation of Print method of Test class:

Hide Copy Code

//Signature: _T("Test@Print(Ljava/lang/String;)V")
 Variable Print(RuntimeEnvironment* pRuntimeEnvironment)
{
    Variable returnVal;
    Frame *pFrame=&pRuntimeEnvironment->pFrameStack[0];
    Object object=pFrame->stack[pFrame->sp].object;
    Variable *pVar
        =pRuntimeEnvironment->pObjectHeap->GetObjectPointer(object);
    if(pVar)
    {
        CString *pString = (CString *)pVar[1].ptrValue;
        if(pString)    wprintf(_T("%s"),*pString);
    }

    returnVal.intValue=0;
    return returnVal;
}

It is the native methods responsibility to correctly operate on stack. The java instruction is here out of scope. Everything is running on real machine here. So, here we pop the string type object reference from stack, convert it to CString object and do our native printing to console. This way we can handle any native operation like creating new window, drawing or do network operation. All these things are done in the implementation of Morpheus project.

THE GARBAGE COLLECTOR

Java language does not have memory release mechanism. So the JVM must take the responsibility to release memory when some objects are out of scope no longer required or referenced by the application. To do this the JVM may take a number of strategy like reference count, mark and sweep etc. I used mark and sweep method because of its simplicily and accuracy. We start from the stack. We mark each object that is being referenced from the stack references. Then we mark all the objects that is being referenced by the marked objects and so on recursively. After the mark operation we know which objects are connected and which are out of scope. Then we take each object one by one and release its memory from heap. Before that we must call the finalize method of that object to do any cleanup required by the object itself programetically.

CONCLUSION

Thats all about to say for now about how we can implement a simple JVM. The JVM I present here is very limited implementation - though most of the java instructions are supported. It lacks heavily for library and native interface. Please look at the seminar presentation downloadable above for a visual description of JVM and how instructions are executed in a JVM. Full screen view of the presentation is best viewed with spacebar to go to next slide. I am busy with the implementation of Morpheus project at my free time and wish to come with that as well as with a new JVM with a new Window subsystem implementation having Windows Vista and Office 2007 look and feel (ok, ok, thats not technically a big deal but good to have for user interface degign) and oh yes also with a .NET Virtual Execution System withMorpheus for .NET support also. The .NET VES is similar except the complex onfile structure is really painfull when I decode them. All these things I do because I love to do- so I do not try to make a zero bug system. I leave when it seems to work for 'Hello World ++' applications.

Friday, February 05, 2016