Currently radix tree is used for mapping compilation unit pointers to method entry native addresses.
Signed-off-by: Tomek Grabiec <[email protected]> --- Makefile | 3 +- include/jit/cu-mapping.h | 2 +- include/vm/alloc.h | 1 + include/vm/radix-tree.h | 15 ++ jit/alloc.c | 13 ++ jit/cu-mapping.c | 231 +++---------------------------- jit/trampoline.c | 3 +- test/arch-x86/Makefile | 1 + test/jit/Makefile | 2 + test/vm/Makefile | 4 +- test/vm/radix-tree-test.c | 55 ++++++++ vm/radix-tree.c | 327 +++++++++++++++++++++++++++++++++++++++++++++ 12 files changed, 445 insertions(+), 212 deletions(-) create mode 100644 include/vm/radix-tree.h create mode 100644 test/vm/radix-tree-test.c create mode 100644 vm/radix-tree.c diff --git a/Makefile b/Makefile index f791416..0baeb11 100644 --- a/Makefile +++ b/Makefile @@ -98,7 +98,8 @@ VM_OBJS = \ vm/types.o \ vm/zalloc.o \ vm/class.o \ - vm/list.o + vm/list.o \ + vm/radix-tree.o JAMVM_OBJS = \ vm/jato.o \ diff --git a/include/jit/cu-mapping.h b/include/jit/cu-mapping.h index 5630209..2720951 100644 --- a/include/jit/cu-mapping.h +++ b/include/jit/cu-mapping.h @@ -3,7 +3,7 @@ struct compilation_unit; -void add_cu_mapping(struct compilation_unit *cu); +int 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(); diff --git a/include/vm/alloc.h b/include/vm/alloc.h index a175502..d5ce8f0 100644 --- a/include/vm/alloc.h +++ b/include/vm/alloc.h @@ -5,6 +5,7 @@ struct buffer; +int get_buffer_align_bits(); void *alloc_exec(size_t); int expand_buffer_exec(struct buffer *); diff --git a/include/vm/radix-tree.h b/include/vm/radix-tree.h new file mode 100644 index 0000000..18f1790 --- /dev/null +++ b/include/vm/radix-tree.h @@ -0,0 +1,15 @@ +#ifndef _VM_RADIX_TREE +#define _VM_RADIX_TREE + +struct radix_tree; + +struct radix_tree *alloc_radix_tree(unsigned int bits_per_level, + unsigned int key_bits); +void free_radix_tree(struct radix_tree *tree); + +int tree_put(struct radix_tree *tree, unsigned long key, void *value); +void tree_remove(struct radix_tree *tree, unsigned long key); +void *tree_lookup(struct radix_tree *tree, unsigned long key); +void *tree_lookup_preceeding(struct radix_tree *tree, unsigned long key); + +#endif /* _VM_RADIX_TREE */ diff --git a/jit/alloc.c b/jit/alloc.c index e1e33be..2a43491 100644 --- a/jit/alloc.c +++ b/jit/alloc.c @@ -21,6 +21,19 @@ #include <stdlib.h> #include <string.h> +int get_buffer_align_bits() +{ + int page_size = getpagesize(); + int bits = 0; + + while (page_size) { + bits++; + page_size >>= 1; + } + + return bits; +} + static void *__alloc_exec(size_t size) { int page_size; diff --git a/jit/cu-mapping.c b/jit/cu-mapping.c index 8cb9558..2209e10 100644 --- a/jit/cu-mapping.c +++ b/jit/cu-mapping.c @@ -27,246 +27,61 @@ #include <jit/compilation-unit.h> #include <jit/cu-mapping.h> +#include <vm/alloc.h> +#include <vm/radix-tree.h> #include <vm/buffer.h> -#include <vm/stdlib.h> #include <vm/die.h> -#include <unistd.h> -#include <malloc.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 | - * +------------------+ - * + * is fast. */ +struct radix_tree *cu_map; -#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]; -}; - -static int buffer_alignment_bits; -struct radix_tree_node *root; - -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; -} +#define BITS_PER_LEVEL 6 void init_cu_mapping(void) { - int page_size = getpagesize(); - int viable_key_bits; - - while (page_size > 0) { - buffer_alignment_bits++; - page_size >>= 1; - } + int key_bits = sizeof(unsigned long) * 8; + int viable_key_bits = key_bits - get_buffer_align_bits(); - 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); - if (!root) + cu_map = alloc_radix_tree(BITS_PER_LEVEL, viable_key_bits); + if (!cu_map) die("out of memory"); } -static void *tree_last(struct radix_tree_node *node, int level) +static unsigned long addr_key(unsigned long addr) { - 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; + return addr >> get_buffer_align_bits(); } -static unsigned long get_index(unsigned long key, int level) +static unsigned long cu_key(struct compilation_unit *cu) { - int shift = ((level_count - level - 1) * KEY_BITS); - - return (key >> shift) & key_mask; + return addr_key((unsigned long)buffer_ptr(cu->objcode)); } -static void *tree_previous(struct radix_tree_node *node, unsigned long key, - int level) +int add_cu_mapping(struct compilation_unit *cu) { - 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); - } + return tree_put(cu_map, cu_key(cu), cu); } 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; + tree_remove(cu_map, cu_key(cu)); } 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); + struct compilation_unit *cu; + unsigned long method_addr; + + cu = tree_lookup_preceeding(cu_map, addr_key(addr)); + if (cu == NULL) + return NULL; + method_addr = (unsigned long)buffer_ptr(cu->objcode); if (method_addr + buffer_offset(cu->objcode) <= addr) return NULL; diff --git a/jit/trampoline.c b/jit/trampoline.c index a123d7a..c7e426b 100644 --- a/jit/trampoline.c +++ b/jit/trampoline.c @@ -53,7 +53,8 @@ static void *jit_java_trampoline(struct compilation_unit *cu) if (!cu->is_compiled) compile(cu); - add_cu_mapping(cu); + if (add_cu_mapping(cu) != 0) + die("out of memory"); return buffer_ptr(cu->objcode); } diff --git a/test/arch-x86/Makefile b/test/arch-x86/Makefile index 9a77fcc..0d3cea1 100644 --- a/test/arch-x86/Makefile +++ b/test/arch-x86/Makefile @@ -35,6 +35,7 @@ OBJS = \ ../../vm/types.o \ ../../vm/zalloc.o \ ../../vm/class.o \ + ../../vm/radix-tree.o \ ../../jit/alloc.o \ ../../jit/basic-block.o \ ../../jit/compilation-unit.o \ diff --git a/test/jit/Makefile b/test/jit/Makefile index 568b69f..4d26480 100644 --- a/test/jit/Makefile +++ b/test/jit/Makefile @@ -13,6 +13,8 @@ OBJS = \ ../../vm/string.o \ ../../vm/types.o \ ../../vm/zalloc.o \ + ../../vm/radix-tree.o \ + ../../jit/alloc.o \ ../../jit/arithmetic-bc.o \ ../../jit/basic-block.o \ ../../jit/branch-bc.o \ diff --git a/test/vm/Makefile b/test/vm/Makefile index 9e065ad..fea3170 100644 --- a/test/vm/Makefile +++ b/test/vm/Makefile @@ -15,6 +15,7 @@ OBJS = \ ../../vm/zalloc.o \ ../../vm/types.o \ ../../vm/list.o \ + ../../vm/radix-tree.o \ bitset-test.o \ buffer-test.o \ bytecodes-test.o \ @@ -22,6 +23,7 @@ OBJS = \ natives-test.o \ stack-test.o \ string-test.o \ - types-test.o + types-test.o \ + radix-tree-test.o include ../../scripts/build/test.mk diff --git a/test/vm/radix-tree-test.c b/test/vm/radix-tree-test.c new file mode 100644 index 0000000..b59b96f --- /dev/null +++ b/test/vm/radix-tree-test.c @@ -0,0 +1,55 @@ +/* + * Copyright (C) 2009 Tomasz Grabiec + */ + +#include <libharness.h> +#include <limits.h> +#include <vm/radix-tree.h> + +void test_tree_put_and_lookup() +{ + unsigned long key; + struct radix_tree *tree; + void *result; + + tree = alloc_radix_tree(2, sizeof(key)*8); + + key = 1; + tree_put(tree, key, (void*)0xcafebabe); + result = tree_lookup(tree, key); + assert_ptr_equals((void*)0xcafebabe, result); + + key = ULONG_MAX; + tree_put(tree, key, (void*)0xdeadbeef); + result = tree_lookup(tree, key); + assert_ptr_equals((void*)0xdeadbeef, result); + + key = key - 1; + result = tree_lookup_preceeding(tree, key); + assert_ptr_equals((void*)0xcafebabe, result); + + free_radix_tree(tree); +} + +void test_tree_remove() +{ + struct radix_tree *tree; + unsigned long key; + void *value; + void *result; + + tree = alloc_radix_tree(2, sizeof(key)*8); + + key = 0xdeadbeef; + value = (void*)0xcafebabe; + + tree_put(tree, key, value); + result = tree_lookup(tree, key); + assert_ptr_equals(value, result); + + tree_remove(tree, key); + result = tree_lookup(tree, key); + assert_ptr_equals(NULL, result); + + free_radix_tree(tree); +} diff --git a/vm/radix-tree.c b/vm/radix-tree.c new file mode 100644 index 0000000..8e71f56 --- /dev/null +++ b/vm/radix-tree.c @@ -0,0 +1,327 @@ +/* + * Copyright (c) 2009 Tomasz Grabiec + * + * 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 <vm/radix-tree.h> +#include <vm/stdlib.h> +#include <assert.h> +#include <malloc.h> +#include <errno.h> +#include <stdbool.h> + +/* + * Below is a schematic ilustration how values are mapped to keys in + * radix tree. In this example it is assumed that key is 22 bits long + * and bits_per_level is equal to 6. + * + * + * key --> 0000 0000 00xx xxxx xxxx xxxx xxxx xxxx + * | || | | || | + * \-----/\-----/ \-----/\-----/ + * | | | | + * / / | | + * / / | \ + * / / | \ + * / | | \ + * / | | \ + * | | | \ + * +----+-+-+-+-+..+-+ | | \ + * root: |NULL| | | | | | | | | \ + * +----+-+-+-+-+..+-+ | | | + * level 0 | | | | + * | +----+-+-+-+-+..+-+ | | + * > | | | | | | | | | | + * +----+-+-+-+-+..+-+ | | + * level 1 | | | + * | +----+-+-+-+-+..+-+ | + * -> | | | | | | | | | + * +----+-+-+-+-+..+-+ | + * level 2 | | + * | +----+-+-+-+-+..+-+ + * -> | | | | | | | | + * +----+-+-+-+-+..+-+ + * level 3 | + * | + * v + * value + * + */ + +struct radix_tree { + int level_count; + int bits_per_level; + + struct radix_tree_node *root; +}; + +struct radix_tree_node { + struct radix_tree_node *parent; + int count; /* number of nonempty slots */ + void *slots[0]; +}; + +static unsigned long level_mask(struct radix_tree *tree) +{ + return (1ul << tree->bits_per_level) - 1; +} + +static int slot_count(struct radix_tree *tree) +{ + return 1 << tree->bits_per_level; +} + +static int level_count(struct radix_tree *tree) +{ + return tree->level_count; +} + +static struct radix_tree_node * +alloc_radix_tree_node(struct radix_tree *tree, struct radix_tree_node *parent) +{ + struct radix_tree_node *node; + int slots_size = sizeof(struct radix_tree_node*) * slot_count(tree); + + node = zalloc(sizeof(struct radix_tree_node) + slots_size); + if (!node) + return NULL; + + node->parent = parent; + + return node; +} + +struct radix_tree *alloc_radix_tree(unsigned int bits_per_level, + unsigned int key_bits) +{ + struct radix_tree *tree; + + assert(bits_per_level < key_bits); + assert(key_bits <= sizeof(unsigned long) * 8); + + tree = malloc(sizeof(struct radix_tree)); + if (!tree) + return NULL; + + tree->bits_per_level = bits_per_level; + + tree->level_count = (key_bits + bits_per_level - 1) + / bits_per_level; + + tree->root = alloc_radix_tree_node(tree, NULL); + if (!tree->root) { + free(tree); + return NULL; + } + + return tree; +} + +static void free_radix_tree_node(struct radix_tree *tree, + struct radix_tree_node *node, int level) +{ + int i; + + if (level < level_count(tree) - 1) + for (i = 0; i < slot_count(tree); i++) + if (node->slots[i] != NULL) + free_radix_tree_node(tree, node->slots[i], + level + 1); + + free(node); +} + +void free_radix_tree(struct radix_tree *tree) +{ + free_radix_tree_node(tree, tree->root, 0); + free(tree); +} + +static void *tree_last(struct radix_tree *tree, struct radix_tree_node *node, + int level) +{ + int i; + + while (level < level_count(tree)) { + + for (i = slot_count(tree) - 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(struct radix_tree *tree, unsigned long key, + int level) +{ + int shift = ((level_count(tree) - level - 1) * tree->bits_per_level); + + return (key >> shift) & level_mask(tree); +} + +static void * +tree_previous(struct radix_tree *tree, struct radix_tree_node *node, + unsigned long key, int level) +{ + int 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(tree, key, level) - 1; index >= 0; index--) + if (node->slots[index] != NULL) + return tree_last(tree, node->slots[index], level + 1); + + return tree_previous(tree, node->parent, key, level - 1); +} + +/** + * tree_put - put key->value mapping into the tree. Returns 0 upon success. + * + * @tree: a radix tree to put into. + * @key: the search key + * @value: the value to associate key with + */ +int tree_put(struct radix_tree *tree, unsigned long key, void *value) +{ + struct radix_tree_node *node = tree->root; + int i; + + assert(value != NULL); + + for (i = 0; i < level_count(tree) - 1; i++) { + int index = get_index(tree, key, i); + + if (node->slots[index] == NULL) { + node->slots[index] = alloc_radix_tree_node(tree, node); + if (node->slots[index] == NULL) + return -ENOMEM; + + node->count++; + } + + node = node->slots[index]; + } + + node->count++; + node->slots[get_index(tree, key, i)] = value; + + return 0; +} + +static void free_slot(struct radix_tree *tree, struct radix_tree_node *node, + int key, int level) +{ + node->slots[get_index(tree, key, level)] = NULL; + node->count--; + + if (node->count == 0 && node->parent != NULL) { + free_slot(tree, node->parent, key, level - 1); + free(node); + } +} + +/** + * tree_remove - remove mapping from tree. + * @tree: a radix tree to remove from. + * @key: a key to remove. + */ +void tree_remove(struct radix_tree *tree, unsigned long key) +{ + int i; + struct radix_tree_node *node = tree->root; + + for (i = 0; i < level_count(tree) - 1; i++) { + int index = get_index(tree, key, i); + + if (node->slots[index] == NULL) + return; /* no mapping exists */ + + node = node->slots[index]; + } + + free_slot(tree, node, key, i); +} + +static void *__tree_lookup(struct radix_tree *tree, unsigned long key, + bool try_preceeding) +{ + int i; + struct radix_tree_node *node = tree->root; + + for (i = 0; i < level_count(tree); i++) { + int index = get_index(tree, key, i); + + if (node->slots[index] == NULL) { + if (try_preceeding) + return tree_previous(tree, node, key, i); + else + return NULL; + } + + node = node->slots[index]; + } + + return node; +} + + +/** + * tree_lookup - get the value associated with @key. Returns NULL when no + * mapping exists. + * + * @tree: a radix tree to lookup in. + * @key: a key which value should be abtained. + */ +void *tree_lookup(struct radix_tree *tree, unsigned long key) +{ + return __tree_lookup(tree, key, false); +} + +/** + * tree_lookup_preceeding - get the value associated with @key or + * the value associated with the preceeding key. + * Returns NULL when no preceeding key exists. + * + * @tree: a radix tree to lookup in. + * @key: a key which value should be returned. + */ +void *tree_lookup_preceeding(struct radix_tree *tree, unsigned long key) +{ + return __tree_lookup(tree, key, true); +} -- 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
