This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "Triton Repository".
The branch, btree has been updated
via 4914cc7272dfa26a81399cf787ae46011fbbd3ba (commit)
from 0c7313481495a7ebc8f7f7f54aa3d20b046391e2 (commit)
Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.
- Log -----------------------------------------------------------------
commit 4914cc7272dfa26a81399cf787ae46011fbbd3ba
Author: Ellis Wilson <ellis(a)runnersroll.com>
Date: Fri Aug 27 13:24:12 2010 -0400
- changes from August on the btree - not yet stable but approaching such
- metadata benchmark file generator
- changes from August on btree-bench - also not yet stable
-----------------------------------------------------------------------
Summary of changes:
code/src/btree/btree.ae | 233 +++++++++++++++++++++-------
code/src/btree/btree.hae | 10 +-
code/src/btree/tests/btree-bench.ae | 184 ++++++++++++++++++++++
code/src/btree/tests/metadata-bench-gen.ae | 54 +++++++
code/src/btree/tests/module.mk.in | 3 +
5 files changed, 421 insertions(+), 63 deletions(-)
create mode 100644 code/src/btree/tests/metadata-bench-gen.ae
Diff of changes:
diff --git a/code/src/btree/btree.ae b/code/src/btree/btree.ae
index 148f013..3ccbb4d 100644
--- a/code/src/btree/btree.ae
+++ b/code/src/btree/btree.ae
@@ -1,46 +1,55 @@
-#include "btree.hae"
+#include "src/btree/btree.hae"
#include <stdlib.h>
#include <stdio.h>
+
static int t = MIN_FACTOR;
+
//function prototypes:
-static __blocking void read_node(uint128_t oid, uint64_t fork, int64_t offset, Node ** node);
+static __blocking Node * read_node(uint128_t oid, uint64_t fork, int64_t offset);
static __blocking void write_node(Node * node);
-static void allocate_node(Node ** node);
-static void move_key(Node * from, int key_from, Node * to, int key_to);
+Node * allocate_node();
+void move_key(Node * from, int key_from, Node * to, int key_to);
void print_tabs(int num);
__blocking void print_node(Node * node, int depth);
-__blocking void print_tree(Node * root);
-__blocking Node * btree_create(uint128_t oid, uint64_t fork);
+__blocking void print_tree();
+__blocking Node * get_root();
+__blocking void update_vroot(Node * root);
+__blocking void btree_create(uint128_t oid, uint64_t fork);
void btree_close(Node * root);
__blocking Node* btree_searchNode(Node * node, Item * item);
__blocking Node* btree_search(Node * node, Item * item);
__blocking int SplitChild(Node * x, int i, Node * y);
__blocking int insert_nonfull(Node * node, Item * item);
-__blocking int btree_insert(Node * root, Item * item);
+__blocking void btree_insert(Item * item);
+
//helper functions:
-static __blocking void read_node(uint128_t oid, uint64_t fork, int64_t offset, Node ** node){
+static __blocking Node * read_node(uint128_t oid, uint64_t fork, int64_t offset){
+ Node * node;
int ret;
int64_t out_size;
- char* buffer = NULL;
- int64_t obj_size = sizeof(**node);
+ int64_t obj_size;
triton_ret_t tret;
- ret = posix_memalign((void**)&buffer, 4096, obj_size);
- assert(ret == 0);
+ node = allocate_node();
+ obj_size = sizeof(*node);
- tret = vosd_read(oid, fork, &buffer, &obj_size, 1, &offset, &obj_size, 1, &out_size, 0);
+ tret = vosd_read(oid, fork, ((char**)&node), &obj_size, 1, &offset, &obj_size, 1, &out_size, 0);
assert(tret == TRITON_SUCCESS);
assert(out_size == obj_size);
+ return node;
+
}
+
+
static __blocking void write_node(Node * node){
int w_flags = VOSD_FLAG_AUTO_TXN;
@@ -48,7 +57,7 @@ static __blocking void write_node(Node * node){
int64_t version;
triton_ret_t tret;
- if(node->keyCount != -1){
+ if(node->offset != -1){
tret = vosd_get_version(node->oid, &version);
assert(tret == TRITON_SUCCESS);
@@ -59,8 +68,6 @@ static __blocking void write_node(Node * node){
}else{
- node->keyCount = 0;
-
tret = vosd_get_version(node->oid, &version);
assert(tret == TRITON_SUCCESS);
version++;
@@ -75,23 +82,31 @@ static __blocking void write_node(Node * node){
}
-static void allocate_node(Node ** node){
-
+
+
+Node * allocate_node(){
+
+ Node * node;
int i;
- *node = malloc(sizeof(Node));
- (*node)->keyCount = -1;
- (*node)->leaf = 1;
+ node = malloc(sizeof(*node));
+ node->oid = triton_uint128_from_uint64(0);
+ node->fork = lld(0);
+ node->offset = lld(-1);
+ node->keyCount = 0;
+ node->leaf = 1;
for(i = 0; i < t*2-1; i++){
- (*node)->keys[i].key = -1;
- (*node)->keys[i].value = -1;
- (*node)->children_offset[i] = lld(-1);
+ node->keys[i].key = -1;
+ node->keys[i].value = -1;
+ node->children_offset[i] = lld(-1);
}
- (*node)->children_offset[t*2-1] = lld(-1);
+ node->children_offset[t*2-1] = lld(-1);
}
-static void move_key(Node * from, int key_from, Node * to, int key_to){
+
+
+void move_key(Node * from, int key_from, Node * to, int key_to){
to->keys[key_to].key = from->keys[key_from].key;
to->keys[key_to].value = from->keys[key_from].value;
@@ -102,6 +117,8 @@ static void move_key(Node * from, int key_from, Node * to, int key_to){
}
+
+
void print_tabs(int num){
int i;
@@ -110,6 +127,8 @@ void print_tabs(int num){
}
+
+
__blocking void print_node(Node * node, int depth){
Node * child;
@@ -121,6 +140,8 @@ __blocking void print_node(Node * node, int depth){
// print_tabs(depth);
printf("fork:\t%lld\n", node->fork);
print_tabs(depth);
+ printf("offset:\t%lld\n", node->offset);
+ print_tabs(depth);
printf("leaf:\t%d\n", node->leaf);
print_tabs(depth);
printf("keyCount:\t%d\n", node->keyCount);
@@ -131,56 +152,124 @@ __blocking void print_node(Node * node, int depth){
}
for(i = 0; i < t*2; i++){
print_tabs(depth);
-// printf("Child %d:\t%ld\t%ld\t%ld\n", i, node->children_oid[i], node->children_fork[i], node->children_offset[i]);
- printf("Child %d:\t%lld\t%lld\n", i, node->children_fork[i], node->children_offset[i]);
+ printf("Child %d:\t%lld\n", i, node->children_offset[i]);
}
- allocate_node(&child);
+ child = allocate_node();
for(i = 0; i < t*2; i++){
if(node->children_offset[i] != lld(-1)){
- read_node(node->children_oid[i], node->children_fork[i], node->children_offset[i], &child);
+ child = read_node(node->children_oid[i], node->children_fork[i], node->children_offset[i]);
print_node(child, depth+1);
}
}
}
-__blocking void print_tree(Node * root){
+
+
+__blocking void print_tree(){
+
+ Node * root;
+ root = allocate_node();
+ root = get_root();
print_node(root, 0);
}
-__blocking Node * btree_create(uint128_t oid, uint64_t fork){
+
+
+__blocking void update_vroot(Node * root){
+
+ int w_flags = VOSD_FLAG_AUTO_TXN;
+ int64_t obj_size = sizeof(*root);
+ int64_t version;
+ int64_t offset = lld(0);
+ triton_ret_t tret;
+
+ tret = vosd_get_version(root->oid, &version);
+ assert(tret == TRITON_SUCCESS);
+ version++;
+
+ tret = vosd_write(root->oid, root->fork, version, ((char**)&root), &obj_size, 1, &(offset), &obj_size, 1, w_flags, 0);
+ assert(tret == TRITON_SUCCESS);
+
+}
+
+
+
+__blocking Node * get_root(){
+
+ Node * root;
+ int ret;
+ int64_t out_size;
+ int64_t obj_size = sizeof(Node);
+ int64_t offset = 0;
+ triton_ret_t tret;
+
+ root = malloc(obj_size);
+ assert(root);
+
+ tret = vosd_read(triton_uint128_from_uint64(OID), FORK, ((char**)&root), &obj_size, 1, &offset, &obj_size, 1, &out_size, 0);
+ assert(tret == TRITON_SUCCESS);
+ assert(out_size == obj_size);
+
+ tret = vosd_read(root->oid, root->fork, ((char**)&root), &obj_size, 1, &(root->offset), &obj_size, 1, &out_size, 0);
+ assert(tret == TRITON_SUCCESS);
+ assert(out_size == obj_size);
+
+ return root;
+
+}
+
+
+
+//public btree functions
+__blocking void btree_create(uint128_t oid, uint64_t fork){
triton_ret_t tret;
Node * root;
//create the vosd at the oid specified
tret = vosd_create(oid, 0);
- assert(tret == TRITON_SUCCESS);
+ if(tret == TRITON_ERR_EXIST){
+ printf("# operating on existing object.\n");
+ /* TODO: destroy tret */
+ }
+ assert(tret == TRITON_ERR_EXIST || tret == TRITON_SUCCESS);
//malloc the new tree's root
- allocate_node(&root);
+ root = allocate_node();
+
+ //initialize vroot with passed parameters
- //initialize root with passed parameters
- root->oid = oid;
- root->fork = fork;
+//TODO: implement dynamic oid/fork assignment & remove from allocate_node
+// root->oid = oid;
+// root->fork = fork;
root->offset = 0;
- //write root to newly created object
+ //write vroot to head of the fork
write_node(root);
- return root;
+ //adjust and write the real root
+ root->offset = -1;
+ write_node(root);
+
+ //update the vroot based on the position the real root was written
+ update_vroot(root);
}
+
+
void btree_close(Node * root){
//TODO: Closing calls
}
+
+
__blocking Node* btree_searchNode(Node * node, Item * item){
int i = 0;
@@ -195,7 +284,7 @@ __blocking Node* btree_searchNode(Node * node, Item * item){
if(node->leaf){
return NULL;
}else{
- read_node(node->children_oid[i], node->children_fork[i], node->children_offset[i], &node);
+ node = read_node(node->children_oid[i], node->children_fork[i], node->children_offset[i]);
return btree_search(node, item);
}
@@ -204,21 +293,33 @@ __blocking Node* btree_searchNode(Node * node, Item * item){
}
+
+
__blocking Node* btree_search(Node * node, Item * item){
- return btree_searchNode(node, item);
+ Node * root;
+ root = allocate_node();
+ root = get_root();
+
+ return btree_searchNode(root, item);
}
+
+
__blocking int SplitChild(Node * x, int i, Node * y){
int j;
Node * z;
- allocate_node(&z);
+ z = allocate_node();
/*duplicate leaf setting*/
z->leaf = y->leaf;
+ /*duplicate oid/fork settings*/
+ z->oid = y->oid;
+ z->fork = y->fork;
+
/*move t-1 keys from the right of the median
* in the y to the new node*/
for(j = 0; j < t - 1; j++){
@@ -262,6 +363,8 @@ __blocking int SplitChild(Node * x, int i, Node * y){
}
+
+
__blocking int insert_nonfull(Node * node, Item * item){
int i = node->keyCount - 1;
@@ -280,14 +383,16 @@ __blocking int insert_nonfull(Node * node, Item * item){
i--;
}
i++;
- allocate_node(&child);
- read_node(node->children_oid[i], node->children_fork[i], node->children_offset[i], &child);
+ child = allocate_node();
+ assert(child);
+ child = read_node(node->children_oid[i], node->children_fork[i], node->children_offset[i]);
+ assert(child);
if(child->keyCount == 2*t - 1){
SplitChild(node, i, child);
if(item->key > node->keys[i].key){
i++;
}
- read_node(node->children_oid[i], node->children_fork[i], node->children_offset[i], &child);
+ child = read_node(node->children_oid[i], node->children_fork[i], node->children_offset[i]);
}
insert_nonfull(child, item);
@@ -298,25 +403,35 @@ __blocking int insert_nonfull(Node * node, Item * item){
}
-__blocking int btree_insert(Node * root, Item * item){
- Node * root_temp = root;
- Node * new_node;
+
+__blocking void btree_insert(Item * item){
+
+ Node * root;
+ Node * root_temp;
+ Node * new_root;
+
+ root = get_root();
+ assert(root);
+ root_temp = root;
+ assert(root_temp);
if(root->keyCount == 2*t - 1){
- allocate_node(&new_node);
- root = new_node;
- new_node->leaf = 0;
- new_node->children_oid[0] = root_temp->oid;
- new_node->children_fork[0] = root_temp->fork;
- new_node->children_offset[0] = root_temp->offset;
- SplitChild(new_node, 0, root_temp);
- insert_nonfull(new_node, item);
+ new_root = allocate_node();
+ assert(new_root);
+ root = new_root;
+ assert(root);
+ new_root->oid = root_temp->oid;
+ new_root->fork = root_temp->fork;
+ new_root->leaf = 0;
+ new_root->children_oid[0] = root_temp->oid;
+ new_root->children_fork[0] = root_temp->fork;
+ new_root->children_offset[0] = root_temp->offset;
+ SplitChild(new_root, 0, root_temp);
+ update_vroot(new_root);
+ insert_nonfull(new_root, item);
}else{
insert_nonfull(root, item);
}
-
- //TODO: This should return something useful we can check
- return 0;
}
diff --git a/code/src/btree/btree.hae b/code/src/btree/btree.hae
index 0020a1d..ebdb4d3 100644
--- a/code/src/btree/btree.hae
+++ b/code/src/btree/btree.hae
@@ -13,6 +13,8 @@
#include "src/aesop/aesop.h"
#define MIN_FACTOR 2
+#define OID 0
+#define FORK 0
/**
* A key-value pair.
@@ -29,7 +31,7 @@ typedef struct Node{
int keyCount;
uint128_t oid;
uint64_t fork;
- uint64_t offset;
+ int64_t offset;
int leaf;
Item keys[MIN_FACTOR*2-1];
uint128_t children_oid[MIN_FACTOR*2];
@@ -41,13 +43,13 @@ typedef struct Node{
* Prints the entire B-Tree to stdout.
* \param[in] btree Pointer to a B-Tree.
*/
-__blocking void print_tree(Node * root);
+__blocking void print_tree();
/**
* Create a new B-Tree.
* \return A pointer to the newly allocated B-Tree.
*/
-__blocking Node * btree_create(uint128_t oid, uint64_t fork);
+__blocking void btree_create(uint128_t oid, uint64_t fork);
/**
* Search a B-Tree for a specific key.
@@ -63,7 +65,7 @@ __blocking Node* btree_search(Node * node, Item * item);
* \param[in] item The new Item to insert.
* \return Code indicating success or failure.
*/
-__blocking int btree_insert(Node * root, Item * item);
+__blocking void btree_insert(Item * item);
/**
* Delete a node in the B-Tree.
diff --git a/code/src/btree/tests/btree-bench.ae b/code/src/btree/tests/btree-bench.ae
index 1c3bc13..ef9cb35 100644
--- a/code/src/btree/tests/btree-bench.ae
+++ b/code/src/btree/tests/btree-bench.ae
@@ -6,13 +6,197 @@
#include "src/versioned-osd/prototype/versioned-osd.hae"
#include "src/btree/btree.hae"
+static uint128_t oid;
+static char sync_mode;
+int done = 0;
+
+enum op_type{
+ INSERT,
+ SEARCH
+};
+
+struct bench_op{
+ int64_t key;
+ int64_t value;
+ enum op_type type;
+ struct triton_list_link list_link;
+};
+
+TRITON_LIST_DEFINE(op_list);
+triton_mutex_t op_list_mutex = TRITON_MUTEX_INITIALIZER;
+
+int print_usage_error(){
+
+ fprintf(stderr, "Usage: btree-bench <vosd db dir> <vosd log dir> <db highwater mark> <log highwater mark> <alignment> <o|s|b|n> <input file>\n");
+ fprintf(stderr, " # o for odirect, s for sync, b for both, n for neither\n");
+
+ return(-1);
+
+}
+
+static __blocking int do_btree_test(void){
+
+ Item * new_item = malloc(sizeof(*new_item));
+ struct triton_list_link * tmp_link;
+ struct bench_op * tmp_op;
+ int loop_iter = 0;
+
+ printf("before item set\n");fflush(stdout);
+ new_item->key = lld(10);
+ new_item->value = 5;
+
+ printf("before btree create\n");fflush(stdout);
+ btree_create(oid, 0);
+ print_tree();
+ printf("---\n");fflush(stdout);
+
+ printf("entering loop\n");fflush(stdout);
+ tmp_link = triton_stack_pop(&op_list);
+ while(tmp_link){
+ printf("loop %d\n", loop_iter++);fflush(stdout);
+ tmp_op = triton_list_get_entry(tmp_link, struct bench_op, list_link);
+ if(tmp_op->type == INSERT){
+ new_item->key = tmp_op->key;
+ new_item->value = tmp_op->value;
+ btree_insert(new_item);
+ }
+ print_tree();
+ printf("---\n");fflush(stdout);
+ tmp_link = triton_stack_pop(&op_list);
+ }
+
+ free(new_item);
+
+ return 0;
+
+}
+
+static void done_callback(void *up, int ret)
+{
+ done = 1;
+}
+
int main(int argc, char *argv[]){
ae_context_t ctx;
ae_op_id_t op_id;
+ int pc = 0;
+ int ret;
+ triton_ret_t tret;
+ int db_highwater = 0;
+ int log_highwater = 0;
+ int alignment = 0;
+ int vosd_init_flags = 0;
+ FILE * desc = 0;
+ char line[2048];
+ char op_string[100];
+ int64_t key;
+ int64_t value;
+ struct bench_op * tmp_op;
+
+ oid = triton_uint128_from_uint64(0);
+
+ //verify correct # of arguments have been passed in
+ if(argc != 8){
+ return print_usage_error();
+ }
+
+ //parse command line
+ ret += sscanf(argv[3], "%d", &db_highwater);
+ ret += sscanf(argv[4], "%d", &log_highwater);
+ ret += sscanf(argv[5], "%d", &alignment);
+ ret += sscanf(argv[6], "%c", &sync_mode);
+
+ //verify parsed values are valid
+ if(ret != 4 ||
+ db_highwater < 0 ||
+ log_highwater < 0 ||
+ alignment < 1 ||
+ (sync_mode != 'o' && sync_mode != 's' && sync_mode != 'b' && sync_mode != 'n')){
+ return print_usage_error();
+ }
+
+ //debugging business
+ tret = triton_debug_init();
+ assert(tret == TRITON_SUCCESS);
+#if 0
+ tret = triton_debug_stderr_enable("all");
+#else
+ tret = triton_debug_stderr_enable("none");
+#endif
+ assert(tret == TRITON_SUCCESS);
+
+ //setup flags for vosd
+ switch(sync_mode){
+ case 'o':
+ vosd_init_flags = VOSD_INIT_FLAG_DATA_ODIRECT;
+ break;
+ case 's':
+ vosd_init_flags = VOSD_INIT_FLAG_DATA_SYNC;
+ break;
+ case 'b':
+ vosd_init_flags = VOSD_INIT_FLAG_DATA_SYNC|VOSD_INIT_FLAG_DATA_ODIRECT;
+ break;
+ default:
+ vosd_init_flags = 0;
+ break;
+ }
+
+ /* parse description of workload */
+ desc = fopen(argv[7], "r");
+ if(!desc){
+ perror("fopen");
+ return(-1);
+ }
+ while(fgets(line, 2048, desc)){
+ if(line[0] == '#'){
+ continue;
+ }
+#if SIZEOF_LONG_INT == 4
+ ret = sscanf(line, "%s %lld %lld", op_string, &key, &value);
+#else
+ ret = sscanf(line, "%s %ld %ld", op_string, &key, &value);
+#endif
+ if(ret != 3){
+ fprintf(stderr, "Error: bad line: %s\n", line);
+ return(-1);
+ }
+ tmp_op = malloc(sizeof(*tmp_op));
+ assert(tmp_op);
+
+ if(strcmp(op_string, "insert") == 0){
+ tmp_op->type = INSERT;
+ }else{
+ if(strcmp(op_string, "search") == 0){
+ tmp_op->type = SEARCH;
+ }else{
+ assert(0);
+ }
+ }
+ tmp_op->key = key;
+ tmp_op->value = value;
+ triton_list_add_back(&tmp_op->list_link, &op_list);
+ }
+ fclose(desc);
+
+ tret = triton_debug_init();
+ assert(tret == TRITON_SUCCESS);
+
+ tret = vosd_init(argv[1], argv[2], db_highwater, log_highwater, alignment, vosd_init_flags);
+ assert(tret == TRITON_SUCCESS);
+ ae_context_create(&ctx, 3, "bdb", "file", "sched");
+ done = 0;
+ ae_post_blocking(do_btree_test, done_callback, NULL, NULL, ctx, &op_id);
+ while(done == 0)
+ {
+ pc++;
+ ae_poll(ctx, 10000);
+ }
+ printf("here");fflush(stdout);
+ vosd_finalize();
return 0;
}
diff --git a/code/src/btree/tests/metadata-bench-gen.ae b/code/src/btree/tests/metadata-bench-gen.ae
new file mode 100644
index 0000000..621777e
--- /dev/null
+++ b/code/src/btree/tests/metadata-bench-gen.ae
@@ -0,0 +1,54 @@
+#include <stdio.h>
+#include <errno.h>
+#include <assert.h>
+#include <stdlib.h>
+
+#include "src/aesop/aesop.h"
+
+int main(int argc, char **argv) {
+
+ int total_ops = 0;
+ int * key_list;
+ int i, index;
+
+ if(argc != 2){
+ fprintf(stderr, "Usage: %s <total ops>\n", argv[0]);
+ return(-1);
+ }
+
+ sscanf(argv[1], "%d", &total_ops);
+
+ if(total_ops < 1){
+ fprintf(stderr, "Usage: %s <total ops>\n", argv[0]);
+ return(-1);
+ }
+
+ key_list = malloc(sizeof(int)*total_ops);
+
+ for(i = 1; i <= total_ops; i++){
+ key_list[i-1] = i;
+ }
+
+ for(i = 0; i < total_ops; i++){
+ index = (int)(rand() / (((double)RAND_MAX + 1) / total_ops));
+ while(key_list[index] == -1){
+ index++;
+ if(index == total_ops){
+ index = 0;
+ }
+ }
+ printf("insert\t%d\t%d\n", key_list[index], rand());
+ key_list[index] = -1;
+ }
+
+ return(0);
+}
+
+/*
+ * Local variables:
+ * c-indent-level: 4
+ * c-basic-offset: 4
+ * End:
+ *
+ * vim: ft=c ts=8 sts=4 sw=4 expandtab
+ */
diff --git a/code/src/btree/tests/module.mk.in b/code/src/btree/tests/module.mk.in
index 8747cf3..d6ac7ad 100644
--- a/code/src/btree/tests/module.mk.in
+++ b/code/src/btree/tests/module.mk.in
@@ -1,3 +1,6 @@
DIR := src/btree/tests
AETESTSRC += $(DIR)/btree-bench.ae
+AETESTSRC += $(DIR)/metadata-bench-gen.ae
+
+MODLIBS_$(DIR) = -lpthread -ldb
hooks/post-receive
--
Triton Repository
