This patch adds:
1. A space in the class struct where we can store the itable
2. Collecting the interface methods implemented by the class and its
superclasses
3. Tracing (debug output) of the collected itable
Signed-off-by: Vegard Nossum <vegard.nos...@gmail.com>
---
Makefile | 1 +
include/vm/class.h | 3 +
include/vm/itable.h | 17 ++++
test/arch-x86/Makefile | 1 +
vm/class.c | 8 +-
vm/itable.c | 215 ++++++++++++++++++++++++++++++++++++++++++++++++
vm/jato.c | 3 +
7 files changed, 245 insertions(+), 3 deletions(-)
create mode 100644 include/vm/itable.h
create mode 100644 vm/itable.c
diff --git a/Makefile b/Makefile
index dd2febe..e61a220 100644
--- a/Makefile
+++ b/Makefile
@@ -95,6 +95,7 @@ VM_OBJS = \
vm/die.o \
vm/field.o \
vm/guard-page.o \
+ vm/itable.o \
vm/jato.o \
vm/method.o \
vm/natives.o \
diff --git a/include/vm/class.h b/include/vm/class.h
index c84efe5..c04cf52 100644
--- a/include/vm/class.h
+++ b/include/vm/class.h
@@ -2,6 +2,7 @@
#define __CLASS_H
#include <vm/field.h>
+#include <vm/itable.h>
#include <vm/method.h>
#include <vm/static.h>
#include <vm/types.h>
@@ -60,6 +61,8 @@ struct vm_class {
/* For array classes this points to array element's class */
struct vm_class *array_element_class;
};
+
+ void *imt_table[VM_ITABLE_SIZE];
};
int vm_class_link(struct vm_class *vmc, const struct cafebabe_class *class);
diff --git a/include/vm/itable.h b/include/vm/itable.h
new file mode 100644
index 0000000..d5e5c87
--- /dev/null
+++ b/include/vm/itable.h
@@ -0,0 +1,17 @@
+#ifndef _VM_ITABLE_H
+#define _VM_ITABLE_H
+
+#include <stdbool.h>
+
+extern bool opt_trace_itable;
+
+/* Tunable for the interface method table. Set it too low and we will get
+ * conflicts between different methods wanting the same slot in the itable.
+ * Set it too high, and we waste a lot of memory per class we load. */
+#define VM_ITABLE_SIZE 64
+
+struct vm_class;
+
+int vm_itable_setup(struct vm_class *vmc);
+
+#endif
diff --git a/test/arch-x86/Makefile b/test/arch-x86/Makefile
index 21d039c..af3dd88 100644
--- a/test/arch-x86/Makefile
+++ b/test/arch-x86/Makefile
@@ -65,6 +65,7 @@ OBJS = \
../../vm/die.o \
../../vm/field.o \
../../vm/guard-page.o \
+ ../../vm/itable.o \
../../vm/method.o \
../../vm/object.o \
../../vm/stack.o \
diff --git a/vm/class.c b/vm/class.c
index 7ed79e8..acd1fa5 100644
--- a/vm/class.c
+++ b/vm/class.c
@@ -1,5 +1,6 @@
/*
* Copyright (c) 2008 Saeed Siam
+ * Copyright (c) 2009 Vegard Nossum
*
* This file is released under the GPL version 2 with the following
* clarification and special exception:
@@ -38,6 +39,7 @@
#include <vm/classloader.h>
#include <vm/die.h>
#include <vm/field.h>
+#include <vm/itable.h>
#include <vm/java_lang.h>
#include <vm/method.h>
#include <vm/object.h>
@@ -120,8 +122,6 @@ setup_vtable(struct vm_class *vmc)
}
}
-extern struct vm_class *vm_java_lang_Class;
-
int vm_class_link(struct vm_class *vmc, const struct cafebabe_class *class)
{
vmc->class = class;
@@ -246,8 +246,10 @@ int vm_class_link(struct vm_class *vmc, const struct
cafebabe_class *class)
}
}
- if (!vm_class_is_interface(vmc))
+ if (!vm_class_is_interface(vmc)) {
setup_vtable(vmc);
+ vm_itable_setup(vmc);
+ }
INIT_LIST_HEAD(&vmc->static_fixup_site_list);
diff --git a/vm/itable.c b/vm/itable.c
new file mode 100644
index 0000000..b7c2f1a
--- /dev/null
+++ b/vm/itable.c
@@ -0,0 +1,215 @@
+/*
+ * Copyright (c) 2009 Vegard Nossum
+ *
+ * This file is released under the GPL version 2 with the following
+ * clarification and special exception:
+ *
+ * Linking this library statically or dynamically with other modules is
+ * making a combined work based on this library. Thus, the terms and
+ * conditions of the GNU General Public License cover the whole
+ * combination.
+ *
+ * As a special exception, the copyright holders of this library give you
+ * permission to link this library with independent modules to produce an
+ * executable, regardless of the license terms of these independent
+ * modules, and to copy and distribute the resulting executable under terms
+ * of your choice, provided that you also meet, for each linked independent
+ * module, the terms and conditions of the license of that module. An
+ * independent module is a module which is not derived from or based on
+ * this library. If you modify this library, you may extend this exception
+ * to your version of the library, but you are not obligated to do so. If
+ * you do not wish to do so, delete this exception statement from your
+ * version.
+ *
+ * Please refer to the file LICENSE for details.
+ */
+
+#include <errno.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <vm/classloader.h>
+#include <vm/class.h>
+#include <vm/itable.h>
+#include <vm/method.h>
+
+bool opt_trace_itable;
+
+struct itable_entry {
+ struct vm_method *method;
+
+ struct list_head node;
+};
+
+static uint32_t itable_hash_string(const char *str)
+{
+ /* Stolen shamelessly from
+ * http://en.wikipedia.org/wiki/Jenkins_hash_function */
+
+ uint32_t hash = 0;
+ for (unsigned int i = 0, n = strlen(str); i < n; ++i) {
+ hash += str[i];
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ }
+
+ hash += (hash << 3);
+ hash ^= (hash >> 11);
+ hash += (hash << 15);
+ return hash;
+}
+
+static uint32_t itable_hash_combine(uint32_t a, uint32_t b)
+{
+ /* The itable can't be longer than 256 entries anyway, so we can
+ * compress those 32 bits from each argument into a combined 8 bit
+ * result. */
+ return ((a >> 24) ^ (a >> 16) ^ (a >> 8) ^ a)
+ ^ ((b >> 24) ^ (b >> 16) ^ (b >> 8) ^ b);
+}
+
+static unsigned int itable_hash(struct vm_method *vmm)
+{
+#if 0
+ /* Very simple hash based on the middle bits of the method pointer.
+ * This is probably not sufficient because the result depends
+ * implicitly on the way the memory allocator works. */
+ return ((unsigned long) vmm / 8) % VM_ITABLE_SIZE;
+#endif
+
+ return itable_hash_combine(itable_hash_string(vmm->name),
+ itable_hash_string(vmm->type)) % VM_ITABLE_SIZE;
+}
+
+static int itable_add_entries(struct vm_class *vmc, struct list_head *itable)
+{
+ const struct cafebabe_class *class = vmc->class;
+
+ /* Note about error handling: We don't actually clean up on error,
+ * but assume that the caller will free the entries that have been
+ * added to the itable so far. That really simplifies this whole
+ * function. */
+ if (vm_class_is_interface(vmc)) {
+ for (unsigned int i = 0; i < class->methods_count; ++i) {
+ struct vm_method *vmm = &vmc->methods[i];
+ unsigned int bucket = itable_hash(vmm);
+
+ struct itable_entry *entry = malloc(sizeof *entry);
+ if (!entry)
+ return -1;
+
+ entry->method = vmm;
+ list_add(&entry->node, &itable[bucket]);
+ }
+ }
+
+ /* XXX: Move this to class linking? */
+ for (unsigned int i = 0; i < class->interfaces_count; ++i) {
+ uint16_t idx = class->interfaces[i];
+
+ const struct cafebabe_constant_info_class *interface;
+ if (cafebabe_class_constant_get_class(class, idx, &interface))
+ return -1;
+
+ const struct cafebabe_constant_info_utf8 *name;
+ if (cafebabe_class_constant_get_utf8(class,
+ interface->name_index, &name))
+ return -1;
+
+ char *c_name = strndup((char *) name->bytes, name->length);
+ if (!c_name)
+ return -1;
+
+ struct vm_class *vmi = classloader_load(c_name);
+ free(c_name);
+ if (!vmi)
+ return -1;
+
+ int ret = itable_add_entries(vmi, itable);
+ if (ret)
+ return ret;
+ }
+
+ /* Yay for tail recursion. */
+ if (vmc->super)
+ return itable_add_entries(vmc->super, itable);
+
+ return 0;
+}
+
+static void *itable_create_conflict_resolver(struct list_head *methods)
+{
+ /* No methods at this index -- return something that will choke the
+ * caller. */
+ if (list_is_empty(methods))
+ return NULL;
+
+ /* If it's not empty, and the first element is the same as the last,
+ * there can only be one element in the list. If so, we can put the
+ * trampoline of that method directly into the itable. */
+ if (list_first(methods) == list_last(methods)) {
+ struct itable_entry *entry = list_first_entry(methods,
+ struct itable_entry, node);
+
+ return vm_method_trampoline_ptr(entry->method);
+ }
+
+ /* XXX: Actually create the resolver stub */
+ return NULL;
+}
+
+static void trace_itable(struct vm_class *vmc, struct list_head *itable)
+{
+ printf("trace itable: %s\n", vmc->name);
+
+ for (unsigned int i = 0; i < VM_ITABLE_SIZE; ++i) {
+ if (list_is_empty(&itable[i]))
+ continue;
+
+ printf(" %d: ", i);
+
+ struct itable_entry *entry;
+ list_for_each_entry(entry, &itable[i], node) {
+ printf("%s.%s%s%s",
+ entry->method->class->name,
+ entry->method->name, entry->method->type,
+ &entry->node == list_last(&itable[i])
+ ? "" : ", ");
+ }
+
+ printf("\n");
+ }
+}
+
+int vm_itable_setup(struct vm_class *vmc)
+{
+ /* We need a temporary array of lists for storing multiple results.
+ * The final itable (the one that gets stored in the class struct
+ * itself) will only have one method per slot. */
+ struct list_head *itable = malloc(sizeof(*itable) * VM_ITABLE_SIZE);
+ if (!itable)
+ return -ENOMEM;
+
+ for (unsigned int i = 0; i < VM_ITABLE_SIZE; ++i)
+ INIT_LIST_HEAD(&itable[i]);
+
+ itable_add_entries(vmc, itable);
+
+ for (unsigned int i = 0; i < VM_ITABLE_SIZE; ++i)
+ vmc->imt_table[i] = itable_create_conflict_resolver(&itable[i]);
+
+ if (opt_trace_itable)
+ trace_itable(vmc, itable);
+
+ /* Free the temporary itable */
+ for (unsigned int i = 0; i < VM_ITABLE_SIZE; ++i) {
+ struct itable_entry *entry, *tmp;
+
+ list_for_each_entry_safe(entry, tmp, &itable[i], node)
+ free(entry);
+ }
+
+ free(itable);
+ return 0;
+}
diff --git a/vm/jato.c b/vm/jato.c
index 3ee9bd6..a4ada8d 100644
--- a/vm/jato.c
+++ b/vm/jato.c
@@ -42,6 +42,7 @@
#include "vm/class.h"
#include "vm/classloader.h"
+#include "vm/itable.h"
#include "vm/java_lang.h"
#include "vm/method.h"
#include "vm/natives.h"
@@ -422,6 +423,8 @@ main(int argc, char *argv[])
opt_trace_classloader = true;
} else if (!strcmp(argv[i], "-Xtrace:invoke")) {
opt_trace_invoke = true;
+ } else if (!strcmp(argv[i], "-Xtrace:itable")) {
+ opt_trace_itable = true;
} else if (!strcmp(argv[i], "-Xtrace:jit")) {
opt_trace_method = true;
opt_trace_cfg = true;
--
1.6.0.4
------------------------------------------------------------------------------
_______________________________________________
Jatovm-devel mailing list
Jatovm-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jatovm-devel
