WARNING - OLD ARCHIVES

This is an archived copy of the Xen.org mailing list, which we have preserved to ensure that existing links to archives are not broken. The live archive, which contains the latest emails, can be found at http://lists.xen.org/
   
 
 
Xen 
 
Home Products Support Community News
 
   
 

xen-changelog

[Xen-changelog] add a metadata cache to the radix io calls.

ChangeSet 1.1348.1.1, 2005/03/23 23:16:17+00:00, akw27@xxxxxxxxxxxxxxxxxxxxxx

        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));


-------------------------------------------------------
This SF.net email is sponsored by Microsoft Mobile & Embedded DevCon 2005
Attend MEDC 2005 May 9-12 in Vegas. Learn more about the latest Windows
Embedded(r) & Windows Mobile(tm) platforms, applications & content.  Register
by 3/29 & save $300 http://ads.osdn.com/?ad_id=6883&alloc_id=15149&op=click
_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxxxxxxxxxx
https://lists.sourceforge.net/lists/listinfo/xen-changelog

<Prev in Thread] Current Thread [Next in Thread>
  • [Xen-changelog] add a metadata cache to the radix io calls., BitKeeper Bot <=