Menu
▾
▴
[Xen-changelog] add a metadata cache to the radix io calls.
|
From: BitKeeper B. <ri...@su...> - 2005-03-24 10:03:01
|
ChangeSet 1.1348.1.1, 2005/03/23 23:16:17+00:00, ak...@ar...
add a metadata cache to the radix io calls.
Makefile | 2
radix.c | 620 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
radix.h | 3
vdi.c | 4
4 files changed, 622 insertions(+), 7 deletions(-)
diff -Nru a/tools/blktap/Makefile b/tools/blktap/Makefile
--- a/tools/blktap/Makefile 2005-03-24 05:02:50 -05:00
+++ b/tools/blktap/Makefile 2005-03-24 05:02:50 -05:00
@@ -174,5 +174,5 @@
bb-trans: $(LIB) blockstore-benchmark.c
$(CC) $(CFLAGS) -o bb-trans blockstore-benchmark.c blockstore.c -lpthread
-radix-test: $(LIB) radix.c blockstore-threaded-trans.c
+radix-test: $(LIB) radix.c blockstore.c
$(CC) $(CFLAGS) -g3 -D RADIX_STANDALONE -o radix-test radix.c blockstore-threaded-trans.c
diff -Nru a/tools/blktap/radix.c b/tools/blktap/radix.c
--- a/tools/blktap/radix.c 2005-03-24 05:02:50 -05:00
+++ b/tools/blktap/radix.c 2005-03-24 05:02:50 -05:00
@@ -13,6 +13,7 @@
#include <stdlib.h>
#include <assert.h>
#include <string.h>
+#include <pthread.h>
#include "blockstore.h"
#include "radix.h"
@@ -24,6 +25,10 @@
#define DEBUG
*/
+/*
+#define STAGED
+*/
+
#define ZERO 0LL
#define ONE 1LL
#define ONEMASK 0xffffffffffffffeLL
@@ -31,6 +36,203 @@
typedef u64 *radix_tree_node;
+
+/* Experimental radix cache. */
+
+static pthread_mutex_t rcache_mutex = PTHREAD_MUTEX_INITIALIZER;
+static int rcache_count = 0;
+#define RCACHE_MAX 1024
+
+typedef struct rcache_st {
+ radix_tree_node *node;
+ u64 id;
+ struct rcache_st *hash_next;
+ struct rcache_st *cache_next;
+ struct rcache_st *cache_prev;
+} rcache_t;
+
+static rcache_t *rcache_head = NULL;
+static rcache_t *rcache_tail = NULL;
+
+#define RCHASH_SIZE 512ULL
+rcache_t *rcache[RCHASH_SIZE];
+#define RCACHE_HASH(_id) ((_id) & (RCHASH_SIZE - 1))
+
+void __rcache_init(void)
+{
+ int i;
+printf("rcache_init!\n");
+
+ for (i=0; i<RCHASH_SIZE; i++)
+ rcache[i] = NULL;
+}
+
+
+void rcache_write(u64 id, radix_tree_node *node)
+{
+ rcache_t *r, *tmp, **curs;
+
+ pthread_mutex_lock(&rcache_mutex);
+
+ /* Is it already in the cache? */
+ r = rcache[RCACHE_HASH(id)];
+
+ for (;;) {
+ if (r == NULL)
+ break;
+ if (r->id == id)
+ {
+ memcpy(r->node, node, BLOCK_SIZE);
+
+ /* bring to front. */
+ if (r != rcache_head) {
+
+ if (r == rcache_tail) {
+ if (r->cache_prev != NULL) rcache_tail = r->cache_prev;
+ rcache_tail->cache_next = NULL;
+ }
+
+ tmp = r->cache_next;
+ if (r->cache_next != NULL) r->cache_next->cache_prev
+ = r->cache_prev;
+ if (r->cache_prev != NULL) r->cache_prev->cache_next = tmp;
+
+ r->cache_prev = NULL;
+ r->cache_next = rcache_head;
+ if (rcache_head != NULL) rcache_head->cache_prev = r;
+ rcache_head = r;
+ }
+
+//printf("Update (%Ld)\n", r->id);
+ goto done;
+ }
+ r = r->hash_next;
+ }
+
+ if ( rcache_count == RCACHE_MAX )
+ {
+ /* Remove an entry */
+
+ r = rcache_tail;
+ if (r->cache_prev != NULL) rcache_tail = r->cache_prev;
+ rcache_tail->cache_next = NULL;
+ freeblock(r->node);
+
+ curs = &rcache[RCACHE_HASH(r->id)];
+ while ((*curs) != r)
+ curs = &(*curs)->hash_next;
+ *curs = r->hash_next;
+//printf("Evict (%Ld)\n", r->id);
+
+ } else {
+
+ r = (rcache_t *)malloc(sizeof(rcache_t));
+ rcache_count++;
+ }
+
+ r->node = newblock();
+ memcpy(r->node, node, BLOCK_SIZE);
+ r->id = id;
+
+ r->hash_next = rcache[RCACHE_HASH(id)];
+ rcache[RCACHE_HASH(id)] = r;
+
+ r->cache_prev = NULL;
+ r->cache_next = rcache_head;
+ if (rcache_head != NULL) rcache_head->cache_prev = r;
+ rcache_head = r;
+ if (rcache_tail == NULL) rcache_tail = r;
+
+//printf("Added (%Ld, %p)\n", id, r->node);
+done:
+ pthread_mutex_unlock(&rcache_mutex);
+}
+
+radix_tree_node *rcache_read(u64 id)
+{
+ rcache_t *r, *tmp;
+ radix_tree_node *node = NULL;
+
+ pthread_mutex_lock(&rcache_mutex);
+
+ r = rcache[RCACHE_HASH(id)];
+
+ for (;;) {
+ if (r == NULL) {
+//printf("Miss (%Ld)\n", id);
+ goto done;
+ }
+ if (r->id == id) break;
+ r = r->hash_next;
+ }
+
+ /* bring to front. */
+ if (r != rcache_head)
+ {
+ if (r == rcache_tail) {
+ if (r->cache_prev != NULL) rcache_tail = r->cache_prev;
+ rcache_tail->cache_next = NULL;
+ }
+ tmp = r->cache_next;
+ if (r->cache_next != NULL) r->cache_next->cache_prev = r->cache_prev;
+ if (r->cache_prev != NULL) r->cache_prev->cache_next = tmp;
+
+ r->cache_prev = NULL;
+ r->cache_next = rcache_head;
+ if (rcache_head != NULL) rcache_head->cache_prev = r;
+ rcache_head = r;
+ }
+
+ node = newblock();
+ memcpy(node, r->node, BLOCK_SIZE);
+
+//printf("Hit (%Ld, %p)\n", id, r->node);
+done:
+ pthread_mutex_unlock(&rcache_mutex);
+
+ return(node);
+}
+
+
+void *rc_readblock(u64 id)
+{
+ void *ret;
+
+ ret = (void *)rcache_read(id);
+
+ if (ret != NULL) return ret;
+
+ ret = readblock(id);
+
+ if (ret != NULL)
+ rcache_write(id, ret);
+
+ return(ret);
+}
+
+u64 rc_allocblock(void *block)
+{
+ u64 ret;
+
+ ret = allocblock(block);
+
+ if (ret != ZERO)
+ rcache_write(ret, block);
+
+ return(ret);
+}
+
+int rc_writeblock(u64 id, void *block)
+{
+ int ret;
+
+ ret = writeblock(id, block);
+ rcache_write(id, block);
+
+ return(ret);
+}
+
+
/*
* block device interface and other helper functions
* with these functions, block id is just a 63-bit number, with
@@ -74,6 +276,8 @@
*
* @return: value on success, zero on error
*/
+#ifndef STAGED
+
u64 lookup(int height, u64 root, u64 key) {
radix_tree_node node;
u64 mask = ONE;
@@ -97,7 +301,7 @@
return ZERO;
oldroot = root;
- node = (radix_tree_node) readblock(getid(root));
|