Signed-off-by: Tomek Grabiec <[email protected]>
---
Makefile | 3 +-
include/jit/cu-mapping.h | 11 ++
jit/cu-mapping.c | 245 ++++++++++++++++++++++++++++++++++++++++++++++
jit/trampoline.c | 3 +
test/jit/Makefile | 1 +
vm/jato.c | 2 +
6 files changed, 264 insertions(+), 1 deletions(-)
create mode 100644 include/jit/cu-mapping.h
create mode 100644 jit/cu-mapping.c
diff --git a/Makefile b/Makefile
index e43b634..f791416 100644
--- a/Makefile
+++ b/Makefile
@@ -80,7 +80,8 @@ JIT_OBJS = \
jit/vtable.o \
jit/fixup-site.o \
jit/exception.o \
- jit/bc-offset-mapping.o
+ jit/bc-offset-mapping.o \
+ jit/cu-mapping.o
VM_OBJS = \
vm/bitset.o \
diff --git a/include/jit/cu-mapping.h b/include/jit/cu-mapping.h
new file mode 100644
index 0000000..5630209
--- /dev/null
+++ b/include/jit/cu-mapping.h
@@ -0,0 +1,11 @@
+#ifndef _JIT_CU_MAPPING
+#define _JIT_CU_MAPPING
+
+struct compilation_unit;
+
+void add_cu_mapping(struct compilation_unit *cu);
+void remove_cu_mapping(struct compilation_unit *cu);
+struct compilation_unit *get_cu_from_native_addr(unsigned long addr);
+void init_cu_mapping();
+
+#endif
diff --git a/jit/cu-mapping.c b/jit/cu-mapping.c
new file mode 100644
index 0000000..343e2bb
--- /dev/null
+++ b/jit/cu-mapping.c
@@ -0,0 +1,245 @@
+#include <unistd.h>
+#include <malloc.h>
+
+#include <jit/cu-mapping.h>
+#include <jit/compilation-unit.h>
+#include <vm/buffer.h>
+#include <vm/stdlib.h>
+
+/*
+ * A radix tree is used to associate native method addresses with
+ * compilation unit. Only method entry address is stored in the tree
+ * structure, so that inserting and removing compilation unit mapping
+ * is fast. When we want to find to which compilation unit given
+ * address belongs we first check the location corresponding to that
+ * address. If method code size is less than buffer alignment size
+ * (typically 4096 bytes) then compilation unit will be found
+ * instantly. For larger methods we might end up on some level with no
+ * mapping present for given index. When that happens we search for
+ * the predecessor of that element. Predecessor search time is
+ * proportionall with the distance of the address from method entry.
+ *
+ * Below is a schematic ilustration how pointer to compilation_unit is
+ * stored in the structure based on it's method entry address. In this
+ * example it is assumed that address is 32-bit long, buffer
+ * alignment (page size) is 2^10 and KEY_BITS is equal to 6.
+ *
+ *
+ * /----------/-- buffer alignment
+ * | |
+ * buffer_ptr --> xxxx xxxx xxxx xxxx xxxx xx00 0000 0000
+ * \ \
+ * \ \
+ * \ \
+ * \ \
+ * \ \
+ * \ \
+ * key --> 0000 0000 00xx xxxx xxxx xxxx xxxx xxxx
+ * | || | | || |
+ * \-----/\-----/ \-----/\-----/
+ * | | | |
+ * / / | |
+ * / / | \
+ * / / | \
+ * / | | \
+ * / | | \
+ * | | | \
+ * +----+-+-+-+-+..+-+ | | \
+ * root: |NULL| | | | | | | | | \
+ * +----+-+-+-+-+..+-+ | | |
+ * level 0 | | | |
+ * | +----+-+-+-+-+..+-+ | |
+ * > | | | | | | | | | |
+ * +----+-+-+-+-+..+-+ | |
+ * level 1 | | |
+ * | +----+-+-+-+-+..+-+ |
+ * -> | | | | | | | | |
+ * +----+-+-+-+-+..+-+ |
+ * level 2 | |
+ * | +----+-+-+-+-+..+-+
+ * -> | | | | | | | |
+ * +----+-+-+-+-+..+-+
+ * level 3 |
+ * v
+ * +------------------+
+ * | compilation_unit |
+ * +------------------+
+ *
+ */
+
+#define KEY_BITS 6
+#define SLOT_COUNT (1 << KEY_BITS)
+
+const unsigned long key_mask = ((1ul << KEY_BITS) - 1);
+int level_count;
+
+struct radix_tree_node {
+ struct radix_tree_node *parent;
+ int count; /* number of nonempty slots */
+ void *slots[SLOT_COUNT];
+};
+
+int buffer_alignment_bits;
+
+struct radix_tree_node * root = NULL;
+
+static struct radix_tree_node *
+alloc_radix_tree_node(struct radix_tree_node *parent)
+{
+ struct radix_tree_node *node;
+
+ node = zalloc(sizeof(struct radix_tree_node));
+ if (!node)
+ return NULL;
+
+ node->parent = parent;
+
+ return node;
+}
+
+void init_cu_mapping()
+{
+ int page_size = getpagesize();
+ int viable_key_bits;
+
+ while (page_size > 0) {
+ buffer_alignment_bits++;
+ page_size >>= 1;
+ }
+
+ viable_key_bits = sizeof(unsigned long) * 8 - buffer_alignment_bits;
+ level_count = (viable_key_bits + KEY_BITS - 1) / KEY_BITS;
+
+ root = alloc_radix_tree_node(NULL);
+}
+
+static void *tree_last(struct radix_tree_node *node, int level)
+{
+ int i;
+
+ while (level < level_count) {
+ for (i = SLOT_COUNT - 1; i >= 0; i--)
+ if (node->slots[i] != NULL) {
+ node = node->slots[i];
+ level++;
+ break;
+ }
+
+ if (i < 0)
+ return NULL;
+ }
+
+ return node;
+}
+
+static unsigned long get_index(unsigned long key, int level)
+{
+ int shift = ((level_count - level - 1) * KEY_BITS);
+
+ return (key >> shift) & key_mask;
+}
+
+static void *tree_previous(struct radix_tree_node *node, unsigned long key,
+ int level)
+{
+ unsigned long index;
+
+ /* we don't have to search this level if there are no
+ other slots */
+ while (node != NULL && node->count == 1) {
+ node = node->parent;
+ level--;
+ }
+
+ if (node == NULL)
+ return NULL;
+
+ for (index = get_index(key, level); index >= 0; index--)
+ if (node->slots[index] != NULL)
+ return tree_last(node->slots[index], level + 1);
+
+ return tree_previous(node->parent, key, level - 1);
+}
+
+void add_cu_mapping(struct compilation_unit *cu)
+{
+ struct radix_tree_node *node = root;
+ unsigned long key;
+ int i;
+
+ key = (unsigned long)buffer_ptr(cu->objcode) >> buffer_alignment_bits;
+
+ for (i = 0; i<level_count-1; i++) {
+ int index = get_index(key, i);
+
+ if (node->slots[index] == NULL)
+ node->slots[index] = alloc_radix_tree_node(node);
+
+ node = node->slots[index];
+ }
+
+ node->count++;
+ node->slots[get_index(key, i)] = cu;
+}
+
+static void free_slot(struct radix_tree_node *node, int key, int level)
+{
+ node->slots[get_index(key, level)] = NULL;
+ node->count--;
+
+ if (node->count == 0 && node->parent != NULL) {
+ free(node);
+ free_slot(node->parent, key, level - 1);
+ }
+}
+
+void remove_cu_mapping(struct compilation_unit *cu)
+{
+ int i;
+ struct radix_tree_node *node = root;
+ unsigned long key;
+
+ key = (unsigned long)buffer_ptr(cu->objcode) >> buffer_alignment_bits;
+
+ for (i = 0; i < level_count - 1; i++) {
+ int index = get_index(key, i);
+
+ if (node->slots[index] == NULL)
+ return; /* no mapping exists */
+
+ node = node->slots[index];
+ }
+
+ free_slot(node, key, i);
+}
+
+static struct compilation_unit *find_cu(unsigned long addr)
+{
+ int i;
+ struct radix_tree_node *node = root;
+ unsigned long key;
+
+ key = addr >> buffer_alignment_bits;
+
+ for (i = 0; i < level_count; i++) {
+ int index = get_index(key, i);
+
+ if (node->slots[index] == NULL)
+ return tree_previous(node, key, i);
+
+ node = node->slots[index];
+ }
+
+ return (struct compilation_unit *)node;
+}
+
+struct compilation_unit *get_cu_from_native_addr(unsigned long addr)
+{
+ struct compilation_unit *cu = find_cu(addr);
+ unsigned long method_addr = (unsigned long)buffer_ptr(cu->objcode);
+
+ if (method_addr + buffer_offset(cu->objcode) <= addr)
+ return NULL;
+
+ return cu;
+}
diff --git a/jit/trampoline.c b/jit/trampoline.c
index cab6c09..a123d7a 100644
--- a/jit/trampoline.c
+++ b/jit/trampoline.c
@@ -25,6 +25,7 @@
*/
#include <jit/compiler.h>
+#include <jit/cu-mapping.h>
#include <vm/buffer.h>
#include <vm/natives.h>
#include <vm/vm.h>
@@ -52,6 +53,8 @@ static void *jit_java_trampoline(struct compilation_unit *cu)
if (!cu->is_compiled)
compile(cu);
+ add_cu_mapping(cu);
+
return buffer_ptr(cu->objcode);
}
diff --git a/test/jit/Makefile b/test/jit/Makefile
index 89d1489..3ec6fd4 100644
--- a/test/jit/Makefile
+++ b/test/jit/Makefile
@@ -35,6 +35,7 @@ OBJS = \
../../jit/args.o \
../../jit/exception.o \
../../jit/bc-offset-mapping.o \
+ ../../jit/cu-mapping.o \
../libharness/libharness.o \
../jamvm/alloc-stub.o \
../jamvm/resolve-stub.o \
diff --git a/vm/jato.c b/vm/jato.c
index 9ac1e99..b3c27bd 100644
--- a/vm/jato.c
+++ b/vm/jato.c
@@ -29,6 +29,7 @@
#include <vm/signal.h>
#include <vm/vm.h>
#include <jit/compiler.h>
+#include <jit/cu-mapping.h>
#ifdef USE_ZIP
#define BCP_MESSAGE "<jar/zip files and directories separated by :>"
@@ -297,6 +298,7 @@ int main(int argc, char *argv[]) {
exe_name = argv[0];
setup_signal_handlers();
+ init_cu_mapping();
setDefaultInitArgs(&args);
int class_arg = parseCommandLine(argc, argv, &args);
--
1.6.0.6
------------------------------------------------------------------------------
Crystal Reports - New Free Runtime and 30 Day Trial
Check out the new simplified licensing option that enables
unlimited royalty-free distribution of the report engine
for externally facing server and web deployment.
http://p.sf.net/sfu/businessobjects
_______________________________________________
Jatovm-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jatovm-devel
