2020q3: Java 虛擬機器

stack frame

github commit

原本 pitifulVM 中實現 stack frame 的 op_stack 為 int32_t type 的陣列，但在 Dhrystone 中需要可以存放 long 大小的 stack，且為了之後可以支援浮點數，將 stack 重新改寫，用 stack_frame_t 結構表示 JVM 中的一個 stack frame：

typedef struct {
    int max_size;
    int size;
    stack_entry_t *store;
} stack_frame_t;

其中 stack_entry_t 為主要存放資料的地方，結構如下：

typedef struct {
    unsigned char entry[8];
    stack_entry_type_t type;
} stack_entry_t;

type 用來標示這個 data 的 type，目前支援存放 8 個 bytes 的資料，但這樣實作較浪費空間，不管型態為何都會佔用 8 個 bytes。之後或許可以使用 Arrays of Length Zero 的結構來減少空間浪費。

在 JVM 中操作 stack 的指令存有 bipush, sipush，但相對算術運算的指令只有 int 型態，bipush 會將資料放在 entry[0] 上，short 則將資料放在 entry[1] 上。n所以在取出資料時，為了方便處理，我使用 stack_to_int 函式將取出來的資料轉型成 64 bits 的整數：

int64_t stack_to_int(unsigned char *entry, size_t size)
{
    switch (size)
    {
    /* int8_t */
    case 1: {
        int8_t value;
        memcpy(&value, entry, size);
        return value;
    }
    /* int16_t */
    case 2: {
        int16_t value;
        memcpy(&value, entry, size);
        return value;
    }
    /* int32_t */
    case 4: {
        int32_t value;
        memcpy(&value, entry, size);
        return value;
    }
    /* int64_t */
    case 8: {
        int64_t value;
        memcpy(&value, entry, size);
        return value;
    }
    default:
        assert(0 && "stack entry error");
        return -1;
    }
}

這樣可以保證在 stack 中的操作都為 64 bits 的整數，才不會有類型不同的問題。

JVM Heap

github commit

根據 Java Virtual Machine Specification

The Java Virtual Machine has a heap that is shared among all Java Virtual Machine threads. The heap is the run-time data area from which memory for all class instances and arrays is allocated.

我們需要一個實際空間來存放類別資訊以及物件資訊，這邊我將 heap 分成兩個區塊：

class heap 用來儲存所有類別資訊：

typedef struct 
{
    u2 length;
    meta_class_t **class_info;
} class_heap_t;

其內部有一個 type 為 meta_class_t * 的陣列，而 meta_class_t 實作如下：

typedef struct
{
    class_file_t *clazz;
    char *path;
    char *name;
} meta_class_t;

用來存放 class 的 meta data，而 class_file_t 則當作 Runtime Area，存放程式執行時所需資料。

object heap 用來儲存所有 new 產生的物件資訊：

typedef struct 
{
    u2 length;
    object_t** objects;
} object_heap_t;

與 class heap 一樣為陣列，其 object_t 用來當作 Java 物件：

typedef struct
{
    variable_t* ptr;
    class_file_t *type;
    size_t field_count;
} object_t;

type 指向此物件的類別資訊，而 ptr 則指向一個陣列，此陣列之長度是由此物件的類別內 field 的數量決定。

typedef union
{
    u1 char_value;
    u2 short_value;
    u4 int_value;
    u8 long_value;
    void *ptr_value;
} value_t;

typedef struct
{
    value_t value;
    int type;    
} variable_t;

typedef enum
{
    NONE = 0,
    BYTE = 1,
    SHORT = 2,
    INT = 3,
    LONG = 4,
    PTR = 5,
    ARRAY_PTR = 6,
    MULTARRAY_PTR = 7,
    STR_PTR = 8
} variable_type_t;

每個 variable 代表物件內的一個 field，利用 union 來選擇該 field 的值，ptr_value 為參考 (reference) 時使用。variable_type_t 用來標示 field 的 type。

在每次要使用到 class 的時候，都會先去 class heap 中尋找有無紀錄此類別，如果找不到則開檔並呼叫 get_class 取得該類別的 constant pool 等資訊，並加入至 class_heap 當中。

char *class_name = find_class_name_from_index(index, clazz);
class_file_t *new_class = find_class_from_heap(class_name);

if (new_class == NULL) {
    char *tmp = malloc((strlen(class_name) + 7 + strlen(prefix)) * sizeof(char));
    strcpy(tmp, prefix);
    strcat(tmp, class_name);
    /* attempt to read given class file */
    FILE *class_file = fopen(strcat(tmp, ".class"), "r");
    assert(class_file && "Failed to open file");

    /* parse the class file */
    new_class = malloc(sizeof(class_file_t));
    *new_class = get_class(class_file);

    int error = fclose(class_file);
    assert(!error && "Failed to close file");
    add_class(new_class, NULL, tmp);

    method_t *method = find_method("<clinit>", "()V", new_class);
    if (method) {
        local_variable_t own_locals[method->code.max_locals];
        variable_t *exec_res = execute(method, own_locals, new_class);
        assert(exec_res->type == STACK_ENTRY_NONE && "<clinit> must be no return");
        free(exec_res);
    }

    free(tmp);
}

此過程在每個對 class 操作的指令都會檢查一次 (e.g. new, invoke, getstatic)。

Instruction

new

new 指令會先檢查 class 是否存在 (如上方程式碼)，找到 class 後在 object heap 中新增一個物件，其大小為 field count * sizeof(vaariable_t)。接著尋找該 class 是否有 <clinit> method，有的話也在此時呼叫。

根據 Java: What is the difference between <init> and <clinit>?
<clinit> 是用來初始化 static field，此過程需比 <init> (初始化 non static field) 還要早。
invokespecial

為呼叫 constructor (<init>) 時的指令，先找到 class 及 method，與 invokestatic 一樣將所需參數從 stack 中取出放入 local variable 中，且 local variable 的第 0 個位置存放該物件的指標。
```
own_locals[0].entry.ptr = obj;
own_locals[0].type = STACK_ENTRY_REF;
```
再執行 execute 即可。如有繼承關係時，在 <init> method 中會透過 invokespecial 執行 parent class 的 <init>，此過程會一直持續直到呼叫 java.lang.Object 的 <init> 停止。
```
public java.lang.Object();
descriptor: ()V
flags: (0x0001) ACC_PUBLIC
Code:
  stack=0, locals=1, args_size=1
     0: return
  LineNumberTable:
    line 3: 0
```
java.lang.Object 的 <init> 只有一行 return 指令，不會繼續呼叫 invokespecial。
invokevirtual

invokevirtual 會根據 method 的 access flag，選擇執行 native method 或 java method，java method 的實作與 invokestatic 類似，而 native method 會在下方說明。

invokedynamic

invokedynamic 是 Java 7 中新增的指令

當第一次執行 invokedynamic 指令時，會呼叫對應的 bootstrap method，並回傳一個 CallSite 物件，當下次再執行相同的 invokedynamic 時，利用這個 CallSite 就能更快速的執行 method。這個指令優點在於能夠在執行時期建立需要執行的程式，常見於出現 anonymous class 的應用 (e.g. Lambda, String Concatenation)。

在 Dhrystone 中出現 invokedynamic 的地方為 String Concatenation，且為了實作方便，移除 CallSite 的功能，在每次執行 invokedynamic 時都從 bootstrap method table 尋找對應的方法來呼叫。

首先在 parse class 時透過 read_bootstrap_attribute 把 bootstrap method table 建立起來，在 invokedynamic 時會先從 constant pool 找到 tag 為 InvokeDynamic 的 entry，這個 entry 存有兩個值，分別是對應 bootstrap method 的 index 及所需要的參數的在 constant pool 中的 index。

在 bootstrap method table 找到的 method 會發現為：
java/lang/invoke/StringConcatFactory.makeConcatWithConstants，其只需要一個 String 類型的參數，這個參數會以 unicode 的字元及 constants 組成，unicode 的部份為程式呼叫時給予的參數，而 constants 則是在編譯時期就定義好的。

考慮以下程式：

public class Strings {
    public static void main(String[] args) {
        String str1 = "Hello";
    String str2 = " Jvm ";
    System.out.println(str1 + " constant " + str2);
    }
}

預期 javap -v 以下輸出：

Constant pool:
...
#4 = Fieldref           #20.#21        // java/lang/System.out:Ljava/io/PrintStream;
#5 = InvokeDynamic      #0:#25         // #0:makeConcatWithConstants:(Ljava/lang/String;Ljava/lang/String;)Ljava/lang/String;
...
#23 = MethodHandle       6:#33          // REF_invokeStatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/String;[Ljava/lang/Object;)Ljava/lang/invoke/CallSite;
#24 = String             #34            // \u0001 constant \u0001
...

public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: (0x0009) ACC_PUBLIC, ACC_STATIC
    Code:
      stack=3, locals=3, args_size=1
        ...
        11: invokedynamic #5,  0     // InvokeDynamic#0:makeConcatWithConstants:(Ljava/lang/String;Ljava/lang/String;)Ljava/lang/String;
        ...
        
BootstrapMethods:
  0: #23 REF_invokeStatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/String;[Ljava/lang/Object;)Ljava/lang/invoke/CallSite;
    Method arguments:
      #24 \u0001 constant \u0001

str1 與 str2 被 unicode \u0001 取代，用來標示在執行時要被取代的位置，而 constant 字串則是在編譯時，就已經存入 constant pool #24 當中。

putfield, getfield

class 檔中關於 field 的資訊只有提供 field name, field descriptor 以及 class name，並沒有給予 field 在 class 中的相對位置，所以這邊我先用迴圈找尋每個 field 直到找到匹配的名字後回傳。
```
for (i = 0; i < obj->type->fields_count; i++, field++) {
    if (strcmp(field->name, name) == 0) {
        return &obj->ptr[i];
    }
}
```
TODO：

改用 hash 實作
$O (1)$ 的查找
ldc, ldc2_w

這兩個指令用來將 constant pool 的資料放到 stack 中

ldc 目前只支援 int 與 string。

The run-time constant pool entry at index either must be a run-time constant of type int or float, or a reference to a string literal, or a symbolic reference to a class, method type, or method handle

ldc2_w 則只支援 long。

The run-time constant pool entry at the index must be a run-time constant of type long or double

tableswitch
























int32_t base = pc;

pc += 3;
pc -= (pc % 4);
uint8_t defaultbyte1 = code_buf[pc], defaultbyte2 = code_buf[pc + 1], defaultbyte3 = code_buf[pc + 2], defaultbyte4 = code_buf[pc + 3];
int32_t _default = ((defaultbyte1 << 24) | (defaultbyte2 << 16) | (defaultbyte3 << 8) | defaultbyte4);
pc += 4;
uint8_t lowbyte1 = code_buf[pc], lowbyte2 = code_buf[pc + 1], lowbyte3 = code_buf[pc + 2], lowbyte4 = code_buf[pc + 3];
int32_t low = ((lowbyte1 << 24) | (lowbyte2 << 16) | (lowbyte3 << 8) | lowbyte4);
pc += 4;
uint8_t highbyte1 = code_buf[pc + 1], highbyte2 = code_buf[pc + 1], highbyte3 = code_buf[pc + 2], highbyte4 = code_buf[pc + 3];
int32_t high = ((highbyte1 << 24) | (highbyte2 << 16) | (highbyte3 << 8) | highbyte4);
pc += 4;

int32_t key = pop_int(op_stack);
if (key >= low && key <= high) {
    unsigned index = pc + ((key - low) * 4);
    uint8_t byte1 = code_buf[index], byte2 = code_buf[index + 1], byte3 = code_buf[index + 2], byte4 = code_buf[index + 3];
    uint32_t addr = ((byte1 << 24) | (byte2 << 16) | (byte3 << 8) | byte4);
    pc = base + addr;
} 
else {
    pc = base + _default;
}

根據規格書：

Immediately after the tableswitch opcode, between zero and three bytes must act as padding

第 2 ~ 3 行是為了做 Alignment，5 ~ 13 行決定 default, low, high 的位置，16 ~ 24 行根據 switch 的值決定選擇的位置。

getstatic, putstatic

先找到 class 的資訊，接著從 class 中每個 field 比對名字與類型，找到後回傳：

field_t *find_field(const char *name, const char *desc, class_file_t *clazz)
{
    field_t *field = clazz->fields;
    for (u2 i = 0; i < clazz->fields_count; ++i, field++) {
        if (!(strcmp(name, field->name) || strcmp(desc, field->descriptor)))
            return field;
    }
    return NULL;
}

如果找不到，則以 class 的 parent 繼續尋找。

getfield, putfield

與 getstatic, putstatic 很像，差別在於找 field 時是用 object 去尋找，透過 object 中的 field 比對，將對應的 field 位置回傳。

variable_t *find_field_addr(object_t *obj, char *name)
{
    field_t *field = obj->type->fields;
    u2 i;
    for (i = 0; i < obj->type->fields_count; i++, field++) {
        if (strcmp(field->name, name) == 0) {
            return &obj->ptr[i];
        }
    }
    return NULL;
}

newarray, multianewarray

分別透過 create_array 及 create_two_dimension_array 來實現。為了要正確釋放記憶體，我將分配出來的 array 當成物件存在 object heap 當中。

void *create_array(class_file_t *clazz, int count)
{
    void *arr = malloc(count * sizeof(int));
    object_t *arr_obj = malloc(sizeof(object_t));
    arr_obj->ptr = malloc(sizeof(variable_t));
    arr_obj->ptr->type = ARRAY_PTR;
    arr_obj->ptr->value.ptr_value = arr;
    arr_obj->type = clazz;
    object_heap.objects[object_heap.length++] = arr_obj;
    arr_obj->field_count = 1;

    return arr;
}

create_array 會建立一個 object，其中 object 內的 ptr 欄位為一個 variable_t 空間的位置， variable_t 內部的 ptr_value 存放 array 的位置。

void **create_two_dimension_array(class_file_t *clazz, int count1, int count2)
{
    int **arr = malloc(count1 * sizeof(int *));
    for (int i = 0; i < count1; ++i) {
        arr[i] = malloc(count2 * sizeof(int));
    }
    object_t *arr_obj = malloc(sizeof(object_t));
    arr_obj->ptr = malloc(sizeof(variable_t) * 3);
    arr_obj->ptr[0].type = MULTARRAY_PTR;
    arr_obj->ptr[0].value.ptr_value = arr;
    arr_obj->ptr[1].type = INT;
    arr_obj->ptr[1].value.int_value = count1;
    arr_obj->ptr[2].type = INT;
    arr_obj->ptr[2].value.int_value = count2;
    arr_obj->type = clazz;
    object_heap.objects[object_heap.length++] = arr_obj;
    arr_obj->field_count = 3;

    return (void **)arr;
}

create_two_dimension_array 與 create_array 類似，但這邊需要紀錄二維陣列的欄位數，所以我用一個 object 表示二維陣列，其中有三個 field，第一個 field 為二維陣列的位置，第二個 field 存二維陣列的 row 數量，第三個 field 為 column 的數量。

Native Method

我將 java.lang 與 java.io 中會使用到的類別實作，並建立需要的 method 與 field，如此便能依照喜好決定哪些 method 設定為 native，也不需要把所有需要的 Java 函式庫都載入，造成 pitifulVM 沒有實作的部份被讀取到產生錯誤。

直接編譯 java.lang 與 java.io package 會產生 module conflict，需使用 javac --patch-module java.base=java 來編譯。

當 invokestatic 與 invokevirtual 中 method 的 access flag 為 ACC_NATIVE 時，便會呼叫 native.c 中對應的實做。

到這邊已經能順利執行 Dhrystone 程式，要注意程式沒有垃圾回收功能，當 heap 數量滿時會產生錯誤：

hank@hank-VivoBook-ASUSLaptop-X580GD-N580GD:~/桌面/SystemSoftwareClass/pitifulvm$ ./jvm Dhrystone/dhry.class
Dhrystone Benchmark, Version 2.1 (Language: Java)

Please give the number of runs through the benchmark: 1000
Execution starts, 1000 runs through Dhrystone
total time: 42ms
Result: 23809 dhrystone/sec.

TODO

Garbage collection

2020q3: Java 虛擬機器

stack frame

JVM Heap

Instruction

Native Method

TODO

tags: linux2020

Read more

Linked List Sort

2021q1 Homework5 (sort)

2022q1 Homework5 (quiz5)

2022q1 Homework5 (quiz6)

tags: `linux2020`