First draft of block caching

mehfooz09 · May 27, 2018 · 75e8d35 · 75e8d35
1 parent bff119e
commit 75e8d35
Show file tree

Hide file tree

Showing 4 changed files with 100 additions and 65 deletions.
diff --git a/emu/gen.c b/emu/gen.c
@@ -4,6 +4,37 @@
 #include "emu/cpuid.h"
 #include "emu/interrupt.h"
 
+static void gen(struct gen_state *state, unsigned long thing) {
+    assert(state->size <= state->capacity);
+    if (state->size >= state->capacity) {
+        state->capacity *= 2;
+        struct jit_block *bigger_block = realloc(state->block,
+                sizeof(struct jit_block) + state->capacity * sizeof(unsigned long));
+        if (bigger_block == NULL) {
+            println("out of memory while jitting");
+            abort();
+        }
+        state->block = bigger_block;
+    }
+    assert(state->size < state->capacity);
+    state->block->code[state->size++] = thing;
+}
+
+void gen_start(addr_t addr, struct gen_state *state) {
+    state->capacity = JIT_BLOCK_INITIAL_CAPACITY;
+    state->size = 0;
+    state->block = malloc(sizeof(struct jit_block) + state->capacity * sizeof(unsigned long));
+    state->block->addr = addr;
+    state->ip = addr;
+}
+
+void gen_exit(struct gen_state *state) {
+    extern void gadget_exit();
+    // in case the last instruction didn't end the block
+    gen(state, (unsigned long) gadget_exit);
+    gen(state, state->ip);
+}
+
 #define DECLARE_LOCALS \
     dword_t saved_ip = state->ip; \
     dword_t addr_offset = 0; \

diff --git a/emu/gen.h b/emu/gen.h
@@ -11,7 +11,9 @@ struct gen_state {
     unsigned capacity;
 };
 
-void gen(struct gen_state *state, unsigned long thing);
+void gen_start(addr_t addr, struct gen_state *state);
+void gen_exit(struct gen_state *state);
+
 int gen_step32(struct gen_state *state, struct tlb *tlb);
 int gen_step16(struct gen_state *state, struct tlb *tlb);
 

diff --git a/emu/jit.c b/emu/jit.c
@@ -6,78 +6,73 @@
 #include "emu/gen.h"
 #include "kernel/calls.h"
 
-static void jit_block_free(struct jit_block *block) {
-    free(block);
-}
-
-void gen_start(addr_t addr, struct gen_state *state) {
-    state->capacity = JIT_BLOCK_INITIAL_CAPACITY;
-    state->size = 0;
-    state->block = malloc(sizeof(struct jit_block) + state->capacity * sizeof(unsigned long));
-    state->block->addr = addr;
-    state->ip = addr;
+struct jit *jit_new(struct mem *mem) {
+    struct jit *jit = malloc(sizeof(struct jit));
+    jit->mem = mem;
+    for (int i = 0; i < JIT_HASH_SIZE; i++)
+        list_init(&jit->hash[i]);
+    return jit;
 }
 
-void gen_end(struct gen_state *state) {
+void jit_free(struct jit *jit) {
+    for (int i = 0; i < JIT_HASH_SIZE; i++) {
+        struct jit_block *block, *tmp;
+        list_for_each_entry_safe(&jit->hash[i], block, tmp, chain) {
+            list_remove(&block->chain);
+            free(block);
+        }
+    }
+    free(jit);
 }
 
-void gen_exit(struct gen_state *state) {
-    extern void gadget_exit();
-    // in case the last instruction didn't end the block
-    gen(state, (unsigned long) gadget_exit);
-    gen(state, state->ip);
+void jit_insert(struct jit *jit, struct jit_block *block) {
+    list_add(&jit->hash[block->addr % JIT_HASH_SIZE], &block->chain);
 }
 
-void gen(struct gen_state *state, unsigned long thing) {
-    assert(state->size <= state->capacity);
-    if (state->size >= state->capacity) {
-        state->capacity *= 2;
-        struct jit_block *bigger_block = realloc(state->block,
-                sizeof(struct jit_block) + state->capacity * sizeof(unsigned long));
-        if (bigger_block == NULL) {
-            println("out of memory while jitting");
-            abort();
-        }
-        state->block = bigger_block;
+struct jit_block *jit_lookup(struct jit *jit, addr_t addr) {
+    struct jit_block *block;
+    list_for_each_entry(&jit->hash[addr % JIT_HASH_SIZE], block, chain) {
+        if (block->addr == addr)
+            return block;
     }
-    assert(state->size < state->capacity);
-    state->block->code[state->size++] = thing;
+    return NULL;
 }
 
-// assembler function
-int jit_enter(struct jit_block *block, struct cpu_state *cpu, struct tlb *tlb);
+static void jit_block_free(struct jit_block *block) {
+    free(block);
+}
 
-int cpu_step32(struct cpu_state *cpu, struct tlb *tlb) {
+struct jit_block *jit_block_compile(addr_t ip, struct tlb *tlb) {
     struct gen_state state;
-    gen_start(cpu->eip, &state);
-    gen_step32(&state, tlb);
-    gen_exit(&state);
-    gen_end(&state);
-
-    struct jit_block *block = state.block;
-    int interrupt = jit_enter(block, cpu, tlb);
-    jit_block_free(block);
-    return interrupt;
+    gen_start(ip, &state);
+    bool in_block = true;
+    while (in_block)
+        in_block = gen_step32(&state, tlb);
+    return state.block;
 }
 
+// assembler function
+int jit_enter(struct jit_block *block, struct cpu_state *cpu, struct tlb *tlb);
+
 void cpu_run(struct cpu_state *cpu) {
+    struct tlb *tlb = tlb_new(cpu->mem);
+    struct jit *jit = jit_new(cpu->mem);
+
     int i = 0;
-    struct tlb tlb = {.mem = cpu->mem};
-    tlb_flush(&tlb);
     read_wrlock(&cpu->mem->lock);
     int changes = cpu->mem->changes;
 
-    while (true) {
-        struct gen_state state;
-        gen_start(cpu->eip, &state);
-        bool in_block = true;
-        while (in_block)
-            in_block = gen_step32(&state, &tlb);
-        gen_end(&state);
-        struct jit_block *block = state.block;
-        int interrupt = jit_enter(block, cpu, &tlb);
-        jit_block_free(block);
+    // look to see if we have a matching block
+    // if so, (link it into the previous block and) run it
+    // otherwise, make a new block and stick it in the hash
 
+    while (true) {
+        struct jit_block *block = jit_lookup(jit, cpu->eip);
+        if (block == NULL) {
+            block = jit_block_compile(cpu->eip, tlb);
+            jit_insert(jit, block);
+        }
+        int interrupt = jit_enter(block, cpu, tlb);
         if (interrupt == INT_NONE && i++ >= 100000) {
             i = 0;
             interrupt = INT_TIMER;
@@ -87,21 +82,25 @@ void cpu_run(struct cpu_state *cpu) {
             read_wrunlock(&cpu->mem->lock);
             handle_interrupt(interrupt);
             read_wrlock(&cpu->mem->lock);
-            if (tlb.mem != cpu->mem)
-                tlb.mem = cpu->mem;
+            if (tlb->mem != cpu->mem)
+                tlb->mem = cpu->mem;
             if (cpu->mem->changes != changes) {
-                tlb_flush(&tlb);
+                tlb_flush(tlb);
                 changes = cpu->mem->changes;
             }
         }
     }
 }
 
-// these functions are never used, but will be someday
-struct jit *jit_new(struct mem *mem) {
-    struct jit *jit = malloc(sizeof(struct jit));
-    return jit;
-}
-void jit_free(struct jit *jit) {
-    free(jit);
+// really only here for ptraceomatic
+int cpu_step32(struct cpu_state *cpu, struct tlb *tlb) {
+    struct gen_state state;
+    gen_start(cpu->eip, &state);
+    gen_step32(&state, tlb);
+    gen_exit(&state);
+
+    struct jit_block *block = state.block;
+    int interrupt = jit_enter(block, cpu, tlb);
+    jit_block_free(block);
+    return interrupt;
 }
diff --git a/emu/jit.h b/emu/jit.h
@@ -8,12 +8,15 @@
 struct jit {
     // there is one jit per address space
     struct mem *mem;
+    struct list hash[JIT_HASH_SIZE];
 };
 
 // this is roughly the average number of instructions in a basic block according to anonymous sources
-#define JIT_BLOCK_INITIAL_CAPACITY 8
+// times 4, roughly the average number of gadgets/parameters in an instruction
+#define JIT_BLOCK_INITIAL_CAPACITY 32
 
 struct jit_block {
+    struct list chain;
     addr_t addr;
     unsigned long code[];
 };