# 2020q3: Java 虛擬機器
## stack frame
- [github commit](https://github.com/hankluo6/pitifulvm/commit/50d78942c95eeb6744465670cb36457747e41879)
原本 pitifulVM 中實現 stack frame 的 `op_stack` 為 `int32_t` type 的陣列，但在 Dhrystone 中需要可以存放 `long` 大小的 stack，且為了之後可以支援浮點數，將 stack 重新改寫，用 `stack_frame_t` 結構表示 JVM 中的一個 stack frame：
```c
typedef struct {
int max_size;
int size;
stack_entry_t *store;
} stack_frame_t;
```
其中 `stack_entry_t` 為主要存放資料的地方，結構如下：
```c
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](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html) 的結構來減少空間浪費。
在 JVM 中操作 stack 的指令存有 `bipush`, `sipush`，但相對算術運算的指令只有 `int` 型態，`bipush` 會將資料放在 `entry[0]` 上，`short` 則將資料放在 `entry[1]` 上。n所以在取出資料時，為了方便處理，我使用 `stack_to_int` 函式將取出來的資料轉型成 64 bits 的整數：
```c
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](https://github.com/hankluo6/pitifulvm/commit/a16ea0ea4fcaa9e97cbe620c1d3d8a4d122fa704)
> 根據 [Java Virtual Machine Specification](https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-2.html#jvms-2.5.3)
>
> 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` 用來儲存所有類別資訊：
```c
typedef struct
{
u2 length;
meta_class_t **class_info;
} class_heap_t;
```
其內部有一個 type 為 `meta_class_t *` 的陣列，而 `meta_class_t` 實作如下：
```c
typedef struct
{
class_file_t *clazz;
char *path;
char *name;
} meta_class_t;
```
用來存放 class 的 meta data，而 `class_file_t` 則當作 Runtime Area，存放程式執行時所需資料。
* `object heap` 用來儲存所有 `new` 產生的物件資訊：
```c
typedef struct
{
u2 length;
object_t** objects;
} object_heap_t;
```
與 `class heap` 一樣為陣列，其 `object_t` 用來當作 Java 物件：
```c
typedef struct
{
variable_t* ptr;
class_file_t *type;
size_t field_count;
} object_t;
```
`type` 指向此物件的類別資訊，而 `ptr` 則指向一個陣列，此陣列之長度是由此物件的類別內 field 的數量決定。
```c
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` 當中。
```c
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](https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-2.html#jvms-2.9)，有的話也在此時呼叫。
> 根據 [Java: What is the difference between <init> and <clinit>?
](https://stackoverflow.com/a/8517155)`<clinit>` 是用來初始化 static field，此過程需比 `<init> (初始化 non static field)` 還要早。
* `invokespecial`
為呼叫 constructor (`<init>`) 時的指令，先找到 class 及 method，與 `invokestatic` 一樣將所需參數從 stack 中取出放入 local variable 中，且 local variable 的第 0 個位置存放該物件的指標。
```c
own_locals[0].entry.ptr = obj;
own_locals[0].type = STACK_ENTRY_REF;
```
再執行 `execute` 即可。如有繼承關係時，在 `<init>` method 中會透過 `invokespecial` 執行 parent class 的 `<init>`，此過程會一直持續直到呼叫 java.lang.Object 的 `<init>` 停止。
:::info
```
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](hhttps://docs.oracle.com/javase/8/docs/api/java/lang/invoke/CallSite.html) 物件，當下次再執行相同的 `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 則是在編譯時期就定義好的。
考慮以下程式：
```java
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 直到找到匹配的名字後回傳。
```c
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`
```c=
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 比對名字與類型，找到後回傳：
```c
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 位置回傳。
```c
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 當中。
```c
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 的位置。
```c
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 沒有實作的部份被讀取到產生錯誤。
:::danger
直接編譯 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
###### tags: `linux2020`
Sign in with Wallet
Connect another wallet