ia64/xen-unstable

changeset 4284:6d3b2d99e2a0

bitkeeper revision 1.1236.41.1 (4241f8c1RPqucowH4YAH-X69s_MQcw)

add a metadata cache to the radix io calls.
author akw27@arcadians.cl.cam.ac.uk
date Wed Mar 23 23:16:17 2005 +0000 (2005-03-23)
parents 04400e772fd7
children 3f85b523b318
files tools/blktap/Makefile tools/blktap/radix.c tools/blktap/radix.h tools/blktap/vdi.c
line diff
     1.1 --- a/tools/blktap/Makefile	Tue Mar 22 17:30:13 2005 +0000
     1.2 +++ b/tools/blktap/Makefile	Wed Mar 23 23:16:17 2005 +0000
     1.3 @@ -174,5 +174,5 @@ bb-tls: $(LIB) blockstore-benchmark.c
     1.4  bb-trans: $(LIB) blockstore-benchmark.c
     1.5  	$(CC) $(CFLAGS) -o bb-trans blockstore-benchmark.c blockstore.c -lpthread
     1.6  
     1.7 -radix-test: $(LIB) radix.c blockstore-threaded-trans.c
     1.8 +radix-test: $(LIB) radix.c blockstore.c
     1.9  	$(CC) $(CFLAGS) -g3 -D RADIX_STANDALONE -o radix-test radix.c blockstore-threaded-trans.c
     2.1 --- a/tools/blktap/radix.c	Tue Mar 22 17:30:13 2005 +0000
     2.2 +++ b/tools/blktap/radix.c	Wed Mar 23 23:16:17 2005 +0000
     2.3 @@ -13,6 +13,7 @@
     2.4  #include <stdlib.h>
     2.5  #include <assert.h>
     2.6  #include <string.h>
     2.7 +#include <pthread.h>
     2.8  #include "blockstore.h"
     2.9  #include "radix.h"
    2.10  
    2.11 @@ -24,6 +25,10 @@
    2.12  #define DEBUG
    2.13  */
    2.14  
    2.15 +/*
    2.16 +#define STAGED
    2.17 +*/
    2.18 +
    2.19  #define ZERO 0LL
    2.20  #define ONE 1LL
    2.21  #define ONEMASK 0xffffffffffffffeLL
    2.22 @@ -31,6 +36,203 @@
    2.23  
    2.24  typedef u64 *radix_tree_node;
    2.25  
    2.26 +
    2.27 +/* Experimental radix cache. */
    2.28 +
    2.29 +static  pthread_mutex_t rcache_mutex = PTHREAD_MUTEX_INITIALIZER;
    2.30 +static  int rcache_count = 0;
    2.31 +#define RCACHE_MAX 1024
    2.32 +
    2.33 +typedef struct rcache_st {
    2.34 +    radix_tree_node  *node;
    2.35 +    u64               id;
    2.36 +    struct rcache_st *hash_next;
    2.37 +    struct rcache_st *cache_next;
    2.38 +    struct rcache_st *cache_prev;
    2.39 +} rcache_t;
    2.40 +
    2.41 +static rcache_t *rcache_head = NULL;
    2.42 +static rcache_t *rcache_tail = NULL;
    2.43 +
    2.44 +#define RCHASH_SIZE 512ULL
    2.45 +rcache_t *rcache[RCHASH_SIZE];
    2.46 +#define RCACHE_HASH(_id) ((_id) & (RCHASH_SIZE - 1))
    2.47 +
    2.48 +void __rcache_init(void)
    2.49 +{
    2.50 +    int i;
    2.51 +printf("rcache_init!\n");
    2.52 +
    2.53 +    for (i=0; i<RCHASH_SIZE; i++)
    2.54 +        rcache[i] = NULL;
    2.55 +}
    2.56 +    
    2.57 +
    2.58 +void rcache_write(u64 id, radix_tree_node *node)
    2.59 +{
    2.60 +    rcache_t *r, *tmp, **curs;
    2.61 +    
    2.62 +    pthread_mutex_lock(&rcache_mutex);
    2.63 +    
    2.64 +    /* Is it already in the cache? */
    2.65 +    r = rcache[RCACHE_HASH(id)];
    2.66 +    
    2.67 +    for (;;) {
    2.68 +        if (r == NULL) 
    2.69 +            break;
    2.70 +        if (r->id == id) 
    2.71 +        {
    2.72 +            memcpy(r->node, node, BLOCK_SIZE);
    2.73 +            
    2.74 +            /* bring to front. */
    2.75 +            if (r != rcache_head) {
    2.76 +                
    2.77 +                if (r == rcache_tail) {
    2.78 +                    if (r->cache_prev != NULL) rcache_tail = r->cache_prev;
    2.79 +                    rcache_tail->cache_next = NULL;
    2.80 +                }
    2.81 +
    2.82 +                tmp = r->cache_next;
    2.83 +                if (r->cache_next != NULL) r->cache_next->cache_prev 
    2.84 +                                                     = r->cache_prev;
    2.85 +                if (r->cache_prev != NULL) r->cache_prev->cache_next = tmp;
    2.86 +
    2.87 +                r->cache_prev = NULL;
    2.88 +                r->cache_next = rcache_head;
    2.89 +                if (rcache_head != NULL) rcache_head->cache_prev = r;
    2.90 +                rcache_head = r;
    2.91 +            }
    2.92 +
    2.93 +//printf("Update (%Ld)\n", r->id);
    2.94 +            goto done;
    2.95 +        }
    2.96 +        r = r->hash_next;
    2.97 +    }
    2.98 +    
    2.99 +    if ( rcache_count == RCACHE_MAX ) 
   2.100 +    {
   2.101 +        /* Remove an entry */
   2.102 +        
   2.103 +        r = rcache_tail;
   2.104 +        if (r->cache_prev != NULL) rcache_tail = r->cache_prev;
   2.105 +        rcache_tail->cache_next = NULL;
   2.106 +        freeblock(r->node);
   2.107 +        
   2.108 +        curs = &rcache[RCACHE_HASH(r->id)];
   2.109 +        while ((*curs) != r)
   2.110 +            curs = &(*curs)->hash_next;
   2.111 +        *curs = r->hash_next;
   2.112 +//printf("Evict (%Ld)\n", r->id);
   2.113 +        
   2.114 +    } else {
   2.115 +        
   2.116 +        r = (rcache_t *)malloc(sizeof(rcache_t));
   2.117 +        rcache_count++;
   2.118 +    }
   2.119 +    
   2.120 +    r->node = newblock();
   2.121 +    memcpy(r->node, node, BLOCK_SIZE);
   2.122 +    r->id = id;
   2.123 +    
   2.124 +    r->hash_next = rcache[RCACHE_HASH(id)];
   2.125 +    rcache[RCACHE_HASH(id)] = r;
   2.126 +    
   2.127 +    r->cache_prev = NULL;
   2.128 +    r->cache_next = rcache_head;
   2.129 +    if (rcache_head != NULL) rcache_head->cache_prev = r;
   2.130 +    rcache_head = r;
   2.131 +    if (rcache_tail == NULL) rcache_tail = r;
   2.132 +    
   2.133 +//printf("Added (%Ld, %p)\n", id, r->node);
   2.134 +done:
   2.135 +    pthread_mutex_unlock(&rcache_mutex);
   2.136 +}
   2.137 +
   2.138 +radix_tree_node *rcache_read(u64 id)
   2.139 +{
   2.140 +    rcache_t *r, *tmp;
   2.141 +    radix_tree_node *node = NULL;
   2.142 +    
   2.143 +    pthread_mutex_lock(&rcache_mutex);
   2.144 +
   2.145 +    r = rcache[RCACHE_HASH(id)];
   2.146 +    
   2.147 +    for (;;) {
   2.148 +        if (r == NULL) {
   2.149 +//printf("Miss (%Ld)\n", id);
   2.150 +            goto done;
   2.151 +        }
   2.152 +        if (r->id == id) break;
   2.153 +        r = r->hash_next;
   2.154 +    }
   2.155 +   
   2.156 +    /* bring to front. */
   2.157 +    if (r != rcache_head) 
   2.158 +    {
   2.159 +        if (r == rcache_tail) {
   2.160 +            if (r->cache_prev != NULL) rcache_tail = r->cache_prev;
   2.161 +            rcache_tail->cache_next = NULL;
   2.162 +        }
   2.163 +        tmp = r->cache_next;
   2.164 +        if (r->cache_next != NULL) r->cache_next->cache_prev = r->cache_prev;
   2.165 +        if (r->cache_prev != NULL) r->cache_prev->cache_next = tmp;
   2.166 +
   2.167 +        r->cache_prev = NULL;
   2.168 +        r->cache_next = rcache_head;
   2.169 +        if (rcache_head != NULL) rcache_head->cache_prev = r;
   2.170 +        rcache_head = r;
   2.171 +    }
   2.172 +    
   2.173 +    node = newblock();
   2.174 +    memcpy(node, r->node, BLOCK_SIZE);
   2.175 +    
   2.176 +//printf("Hit (%Ld, %p)\n", id, r->node);
   2.177 +done:
   2.178 +    pthread_mutex_unlock(&rcache_mutex);
   2.179 +    
   2.180 +    return(node);
   2.181 +}
   2.182 +
   2.183 +
   2.184 +void *rc_readblock(u64 id)
   2.185 +{
   2.186 +    void *ret;
   2.187 +    
   2.188 +    ret = (void *)rcache_read(id);
   2.189 +    
   2.190 +    if (ret != NULL) return ret;
   2.191 +    
   2.192 +    ret = readblock(id);
   2.193 +    
   2.194 +    if (ret != NULL)
   2.195 +        rcache_write(id, ret);
   2.196 +    
   2.197 +    return(ret);
   2.198 +}
   2.199 +
   2.200 +u64 rc_allocblock(void *block)
   2.201 +{
   2.202 +    u64 ret;
   2.203 +    
   2.204 +    ret = allocblock(block);
   2.205 +    
   2.206 +    if (ret != ZERO)
   2.207 +        rcache_write(ret, block);
   2.208 +    
   2.209 +    return(ret);
   2.210 +}
   2.211 +
   2.212 +int rc_writeblock(u64 id, void *block)
   2.213 +{
   2.214 +    int ret;
   2.215 +    
   2.216 +    ret = writeblock(id, block);
   2.217 +    rcache_write(id, block);
   2.218 +    
   2.219 +    return(ret);
   2.220 +}
   2.221 +
   2.222 +
   2.223  /*
   2.224   * block device interface and other helper functions
   2.225   * with these functions, block id is just a 63-bit number, with
   2.226 @@ -74,6 +276,8 @@ radix_tree_node cloneblock(radix_tree_no
   2.227   *
   2.228   *   @return: value on success, zero on error
   2.229   */
   2.230 +#ifndef STAGED
   2.231 +
   2.232  u64 lookup(int height, u64 root, u64 key) {
   2.233      radix_tree_node node;
   2.234      u64 mask = ONE;
   2.235 @@ -97,7 +301,7 @@ u64 lookup(int height, u64 root, u64 key
   2.236              return ZERO;
   2.237  
   2.238          oldroot = root;
   2.239 -        node = (radix_tree_node) readblock(getid(root));
   2.240 +        node = (radix_tree_node) rc_readblock(getid(root));
   2.241          if (node == NULL)
   2.242              return ZERO;
   2.243  
   2.244 @@ -114,6 +318,92 @@ u64 lookup(int height, u64 root, u64 key
   2.245      return ZERO;
   2.246  }
   2.247  
   2.248 +#else /* STAGED */
   2.249 +
   2.250 +
   2.251 +/* non-recursive staged lookup, assume height is 35. */
   2.252 +u64 lookup(int height, u64 root, u64 key) {
   2.253 +    radix_tree_node node;
   2.254 +    u64 mask = ONE;
   2.255 +
   2.256 +printf("lookup!\n");    
   2.257 +    assert(key >> 35 == 0);
   2.258 +
   2.259 +    /* the root block may be smaller to ensure all leaves are full */
   2.260 +    height = 27;
   2.261 +
   2.262 +    /* now carve off equal sized chunks at each step */
   2.263 +    
   2.264 +    /* ROOT: (LEVEL 0) KEYLEN=35*/
   2.265 +    if (getid(root) == ZERO)
   2.266 +        return ZERO;
   2.267 +
   2.268 +    node = (radix_tree_node) readblock(getid(root));
   2.269 +    if (node == NULL)
   2.270 +        return ZERO;
   2.271 +
   2.272 +    root = node[(key >> height) & RADIX_TREE_MAP_MASK];
   2.273 +    mask &= root;
   2.274 +    freeblock(node);
   2.275 +
   2.276 +    if (height == 0)
   2.277 +        return ( root & ONEMASK ) | mask;
   2.278 +
   2.279 +    height -= RADIX_TREE_MAP_SHIFT; /* == 18 */
   2.280 +
   2.281 +    /* LEVEL 1: KEYLEN=26*/
   2.282 +    if (getid(root) == ZERO)
   2.283 +        return ZERO;
   2.284 +
   2.285 +    node = (radix_tree_node) readblock(getid(root));
   2.286 +    if (node == NULL)
   2.287 +        return ZERO;
   2.288 +
   2.289 +    root = node[(key >> height) & RADIX_TREE_MAP_MASK];
   2.290 +    mask &= root;
   2.291 +    freeblock(node);
   2.292 +
   2.293 +    if (height == 0)
   2.294 +        return ( root & ONEMASK ) | mask;
   2.295 +
   2.296 +    height -= RADIX_TREE_MAP_SHIFT; /* == 9 */
   2.297 +    
   2.298 +    /* LEVEL 2: KEYLEN=17*/
   2.299 +    if (getid(root) == ZERO)
   2.300 +        return ZERO;
   2.301 +
   2.302 +    node = (radix_tree_node) readblock(getid(root));
   2.303 +    if (node == NULL)
   2.304 +        return ZERO;
   2.305 +
   2.306 +    root = node[(key >> height) & RADIX_TREE_MAP_MASK];
   2.307 +    mask &= root;
   2.308 +    freeblock(node);
   2.309 +
   2.310 +    if (height == 0)
   2.311 +        return ( root & ONEMASK ) | mask;
   2.312 +
   2.313 +    height -= RADIX_TREE_MAP_SHIFT; /* == 0 */
   2.314 +    
   2.315 +    /* LEVEL 3: KEYLEN=8*/
   2.316 +    if (getid(root) == ZERO)
   2.317 +        return ZERO;
   2.318 +
   2.319 +    node = (radix_tree_node) readblock(getid(root));
   2.320 +    if (node == NULL)
   2.321 +        return ZERO;
   2.322 +
   2.323 +    root = node[(key >> height) & RADIX_TREE_MAP_MASK];
   2.324 +    mask &= root;
   2.325 +    freeblock(node);
   2.326 +
   2.327 +    // if (height == 0)
   2.328 +        return ( root & ONEMASK ) | mask;
   2.329 +
   2.330 +}
   2.331 +
   2.332 +#endif
   2.333 +
   2.334  /*
   2.335   * update: set a radix tree entry, doing copy-on-write as necessary
   2.336   *   @height: height in bits of the radix tree
   2.337 @@ -123,6 +413,10 @@ u64 lookup(int height, u64 root, u64 key
   2.338   *
   2.339   *   @returns: (possibly new) root id on success (with LSB=1), 0 on failure
   2.340   */
   2.341 +
   2.342 +#ifndef STAGED
   2.343 +
   2.344 +
   2.345  u64 update(int height, u64 root, u64 key, u64 val) {
   2.346      int offset;
   2.347      u64 child;
   2.348 @@ -145,7 +439,7 @@ u64 update(int height, u64 root, u64 key
   2.349      if (root == ZERO) {
   2.350          node = (radix_tree_node) newblock();
   2.351      } else {
   2.352 -        node = (radix_tree_node) readblock(getid(root));
   2.353 +        node = (radix_tree_node) rc_readblock(getid(root));
   2.354  
   2.355          if (!iswritable(root)) {
   2.356              /* need to clone this node */
   2.357 @@ -181,10 +475,10 @@ u64 update(int height, u64 root, u64 key
   2.358      /* new/cloned blocks need to be saved */
   2.359      if (root == ZERO) {
   2.360          /* mark this as an owned block */
   2.361 -        root = allocblock(node);
   2.362 +        root = rc_allocblock(node);
   2.363          if (root)
   2.364              root = writable(root);
   2.365 -    } else if (writeblock(getid(root), node) < 0) {
   2.366 +    } else if (rc_writeblock(getid(root), node) < 0) {
   2.367          freeblock(node);
   2.368          return ZERO;
   2.369      }
   2.370 @@ -193,6 +487,320 @@ u64 update(int height, u64 root, u64 key
   2.371      return root;
   2.372  }
   2.373  
   2.374 +
   2.375 +#else /* STAGED */
   2.376 +
   2.377 +/* When update is called, state->next points to the thing to call after 
   2.378 + * update is finished. */
   2.379 +
   2.380 +struct cb_state_st;
   2.381 +
   2.382 +typedef struct {
   2.383 +    /* public stuff */
   2.384 +    u64 val;
   2.385 +    u64 key;
   2.386 +    u64 result;
   2.387 +    
   2.388 +    /* internal state */
   2.389 +    u64 root[4];
   2.390 +    radix_tree_node node[4];
   2.391 +    void (*next)(struct cb_state_st *);
   2.392 +    int err;
   2.393 +} radix_update_t;
   2.394 +
   2.395 +typedef struct cb_state_st{
   2.396 +    void (*next)(struct cb_state_st *); /* Next continuation. */
   2.397 +    union {
   2.398 +        radix_update_t update;
   2.399 +    } radix;
   2.400 +} cb_state_t;
   2.401 +
   2.402 +void s_readblock(cb_state_t *state, u64 id, void **ret)
   2.403 +{
   2.404 +    *ret = readblock(id);
   2.405 +    state->next(state);
   2.406 +}
   2.407 +
   2.408 +void s_allocblock(cb_state_t *state, void *block, u64 *ret)
   2.409 +{
   2.410 +    *ret = allocblock(block);
   2.411 +    state->next(state);
   2.412 +}
   2.413 +        
   2.414 +void s_writeblock(cb_state_t *state, u64 id, void *block, int *ret)
   2.415 +{
   2.416 +    *ret = writeblock(id, block);
   2.417 +    state->next(state);
   2.418 +}
   2.419 +
   2.420 +void cb_done(cb_state_t *state)
   2.421 +{
   2.422 +    printf("*** done ***\n");
   2.423 +}
   2.424 +
   2.425 +/* forward prototypes. */
   2.426 +void up0(cb_state_t *state);
   2.427 +void up1(cb_state_t *state);
   2.428 +void up2(cb_state_t *state);
   2.429 +void up3(cb_state_t *state);
   2.430 +void up4(cb_state_t *state);
   2.431 +void up5(cb_state_t *state);
   2.432 +void up6(cb_state_t *state);
   2.433 +void up7(cb_state_t *state);
   2.434 +void up8(cb_state_t *state);
   2.435 +void up9(cb_state_t *state);
   2.436 +void up10(cb_state_t *state);
   2.437 +void up11(cb_state_t *state);
   2.438 +void up12(cb_state_t *state);
   2.439 +
   2.440 +u64 update(int height, u64 root, u64 key, u64 val)
   2.441 +{
   2.442 +    cb_state_t state;
   2.443 +    radix_update_t *u = &state.radix.update;
   2.444 +    
   2.445 +    u->val = val;
   2.446 +    u->key = key;
   2.447 +    u->root[0] = root;
   2.448 +    u->root[1] = u->root[2] = u->root[3] = ZERO;
   2.449 +    u->node[0] = u->node[1] = u->node[2] = u->node[3] = NULL;
   2.450 +    
   2.451 +    /* take a copy of the higher-scoped next continuation. */
   2.452 +    u->next = state->next;
   2.453 +    
   2.454 +    /* update start state */
   2.455 +    state->next = up0;
   2.456 +    
   2.457 +    for (;;)
   2.458 +    {
   2.459 +        state->next(state);
   2.460 +        if (state->next == NULL) 
   2.461 +            break;
   2.462 +    }
   2.463 +    
   2.464 +    return u->result;
   2.465 +}
   2.466 +
   2.467 +/* c0:*/
   2.468 +void up0(cb_state_t *state) {
   2.469 +    radix_update_t *u = &state->radix.update;
   2.470 +    
   2.471 +    state->next = up1;
   2.472 +    s_readblock(state, getid(u->root[0]), (void **)&(u->node[0]));
   2.473 +}
   2.474 +    
   2.475 +/* c1: */
   2.476 +void up1(cb_state_t *state) {
   2.477 +    radix_update_t *u = &state->radix.update;
   2.478 +    
   2.479 +    u->root[1] = u->node[0][u->key >> 27 & RADIX_TREE_MAP_MASK];
   2.480 +    if (u->root[1] == ZERO) {
   2.481 +        u->node[1] = (radix_tree_node) newblock();
   2.482 +        /* goto next continuation (c2)*/ up2(state);return;
   2.483 +    } else {
   2.484 +        state->next = up2;
   2.485 +        s_readblock(state, getid(u->root[1]), (void **)&(u->node[1]));
   2.486 +    }
   2.487 +}
   2.488 +
   2.489 +/* c2: */
   2.490 +void up2(cb_state_t *state) {
   2.491 +    radix_update_t *u = &state->radix.update;
   2.492 +    
   2.493 +    if ((u->root[1] != ZERO) && (!iswritable(u->root[1]))) {
   2.494 +        /* need to clone this node */
   2.495 +        radix_tree_node oldnode = u->node[1];
   2.496 +        u->node[1] = cloneblock(u->node[1]);
   2.497 +        freeblock(oldnode);
   2.498 +        u->root[1] = ZERO;
   2.499 +    }
   2.500 +    u->root[2] = u->node[1][u->key >> 18 & RADIX_TREE_MAP_MASK];
   2.501 +    if (u->root[2] == ZERO) {
   2.502 +        u->node[2] = (radix_tree_node) newblock();
   2.503 +        /* goto next continuation (c3)*/ up3(state);return;
   2.504 +    } else {
   2.505 +        state->next = up3;
   2.506 +        s_readblock(state, getid(u->root[2]), (void **)&(u->node[2]));
   2.507 +    }
   2.508 +}
   2.509 +    
   2.510 +/* c3: */
   2.511 +void up3(cb_state_t *state) {
   2.512 +    radix_update_t *u = &state->radix.update;
   2.513 +    
   2.514 +    if ((u->root[2] != ZERO) && (!iswritable(u->root[2]))) {
   2.515 +        /* need to clone this node */
   2.516 +        radix_tree_node oldnode = u->node[2];
   2.517 +        u->node[2] = cloneblock(u->node[2]);
   2.518 +        freeblock(oldnode);
   2.519 +        u->root[2] = ZERO;
   2.520 +    }
   2.521 +    u->root[3] = u->node[2][u->key >> 9 & RADIX_TREE_MAP_MASK];
   2.522 +    if (u->root[3] == ZERO) {
   2.523 +        u->node[3] = (radix_tree_node) newblock();
   2.524 +        /* goto next continuation (c4)*/ up4(state);return;
   2.525 +    } else {
   2.526 +        state->next = up4;
   2.527 +        s_readblock(state, getid(u->root[3]), (void **)&(u->node[3]));
   2.528 +    }
   2.529 +}
   2.530 +    
   2.531 +/* c4: */
   2.532 +void up4(cb_state_t *state) {
   2.533 +    radix_update_t *u = &state->radix.update;
   2.534 +    
   2.535 +    if ((u->root[3] != ZERO) && (!iswritable(u->root[3]))) {
   2.536 +        /* need to clone this node */
   2.537 +        radix_tree_node oldnode = u->node[3];
   2.538 +        u->node[3] = cloneblock(u->node[3]);
   2.539 +        freeblock(oldnode);
   2.540 +        u->root[3] = ZERO;
   2.541 +    }
   2.542 +    
   2.543 +    if (u->node[3][u->key & RADIX_TREE_MAP_MASK] == u->val){
   2.544 +        /* no change, so we already owned the child */
   2.545 +        /* goto last continuation (c12) */ up12(state);return;
   2.546 +    }
   2.547 +
   2.548 +    u->node[3][u->key & RADIX_TREE_MAP_MASK] = u->val;
   2.549 +
   2.550 +    /* new/cloned blocks need to be saved */
   2.551 +    if (u->root[3] == ZERO) {
   2.552 +        /* mark this as an owned block */
   2.553 +        state->next = up5;
   2.554 +        s_allocblock(state, u->node[3], &u->root[3]);
   2.555 +        /* goto continuation (c5) */ return;
   2.556 +    } else {
   2.557 +        state->next = up6;
   2.558 +        s_writeblock(state, getid(u->root[3]), u->node[3], &u->err);
   2.559 +        /* goto continuation (c6) */ return;
   2.560 +    }
   2.561 +}
   2.562 +
   2.563 +/* c5: */
   2.564 +void up5(cb_state_t *state) {
   2.565 +    radix_update_t *u = &state->radix.update;
   2.566 +    
   2.567 +    if (u->root[3])
   2.568 +        u->root[3] = writable(u->root[3]);
   2.569 +    /* goto continuation (c6) */ up6(state);return;
   2.570 +}
   2.571 +    
   2.572 +/* c6: */
   2.573 +void up6(cb_state_t *state) {
   2.574 +    radix_update_t *u = &state->radix.update;
   2.575 +    
   2.576 +    if (u->node[2][u->key >> 9 & RADIX_TREE_MAP_MASK] == u->root[3]){
   2.577 +        /* no change, so we already owned the child */
   2.578 +        /* goto last continuation (c12) */ up12(state);return;
   2.579 +    }
   2.580 +    
   2.581 +    u->node[2][u->key >> 9 & RADIX_TREE_MAP_MASK] = u->root[3];
   2.582 +
   2.583 +    /* new/cloned blocks need to be saved */
   2.584 +    if (u->root[2] == ZERO) {
   2.585 +        /* mark this as an owned block */
   2.586 +        state->next = up7;
   2.587 +        s_allocblock(state, u->node[2], &u->root[2]);
   2.588 +        /* goto continuation (c7) */return;
   2.589 +    } else {
   2.590 +        state->next = up8;
   2.591 +        s_writeblock(state, getid(u->root[2]), u->node[2], &u->err);
   2.592 +        /* goto continuation (c8) */return;
   2.593 +    }
   2.594 +}
   2.595 +
   2.596 +/* c7: */
   2.597 +void up7(cb_state_t *state) {
   2.598 +    radix_update_t *u = &state->radix.update;
   2.599 +    
   2.600 +    if (u->root[2])
   2.601 +        u->root[2] = writable(u->root[2]);
   2.602 +    /* goto continuation (c8) */ up8(state);return;
   2.603 +}
   2.604 +    
   2.605 +/* c8: */
   2.606 +void up8(cb_state_t *state) {
   2.607 +    radix_update_t *u = &state->radix.update;
   2.608 +    
   2.609 +    if (u->node[1][u->key >> 18 & RADIX_TREE_MAP_MASK] == u->root[2]){
   2.610 +        /* no change, so we already owned the child */
   2.611 +        /* goto last continuation (c12) */ up12(state);return;
   2.612 +    }
   2.613 +    
   2.614 +    u->node[1][u->key >> 18 & RADIX_TREE_MAP_MASK] = u->root[2];
   2.615 +
   2.616 +    /* new/cloned blocks need to be saved */
   2.617 +    if (u->root[1] == ZERO) {
   2.618 +        /* mark this as an owned block */
   2.619 +        state->next = up9;
   2.620 +        s_allocblock(state, u->node[1], &u->root[1]);
   2.621 +        /* goto continuation (c9) */return;
   2.622 +    } else {
   2.623 +        state->next = up10;
   2.624 +        s_writeblock(state, getid(u->root[1]), u->node[1], &u->err);
   2.625 +        /* goto continuation (c10) */return;
   2.626 +    }
   2.627 +}
   2.628 +
   2.629 +/* c9: */
   2.630 +void up9(cb_state_t *state) {
   2.631 +    radix_update_t *u = &state->radix.update;
   2.632 +    
   2.633 +    if (u->root[1])
   2.634 +        u->root[1] = writable(u->root[1]);
   2.635 +    /* goto continuation (c10) */ up10(state);return;
   2.636 +}
   2.637 +    
   2.638 +/* c10: */
   2.639 +void up10(cb_state_t *state) {
   2.640 +    radix_update_t *u = &state->radix.update;
   2.641 +    
   2.642 +    if (u->node[0][u->key >> 27 & RADIX_TREE_MAP_MASK] == u->root[1]){
   2.643 +        /* no change, so we already owned the child */
   2.644 +        /* goto last continuation (c12) */ up12(state);return;
   2.645 +    }
   2.646 +    
   2.647 +    u->node[0][u->key >> 27 & RADIX_TREE_MAP_MASK] = u->root[1];
   2.648 +
   2.649 +    /* new/cloned blocks need to be saved */
   2.650 +    if (u->root[0] == ZERO) {
   2.651 +        /* mark this as an owned block */
   2.652 +        state->next = up11;
   2.653 +        s_allocblock(state, u->node[0], &u->root[0]);
   2.654 +        /* goto continuation (c11) */ return;
   2.655 +    } else {
   2.656 +        state->next = up10;
   2.657 +        s_writeblock(state, getid(u->root[0]), u->node[0], &u->err);
   2.658 +        /* goto continuation (c12) */ return;
   2.659 +    }
   2.660 +}
   2.661 +
   2.662 +/* c11: */
   2.663 +void up11(cb_state_t *state) {
   2.664 +    radix_update_t *u = &state->radix.update;
   2.665 +    
   2.666 +    if (u->root[0])
   2.667 +        u->root[0] = writable(u->root[0]);
   2.668 +    /* goto continuation (c12) */ up12(state);return;
   2.669 +}
   2.670 +    
   2.671 +/* c12: */
   2.672 +void up12(cb_state_t *state) {
   2.673 +    radix_update_t *u = &state->radix.update;
   2.674 +    
   2.675 +    int i;
   2.676 +    for (i=0;i<4;i++)
   2.677 +        if(u->node[i] != NULL) freeblock(u->node[i]);
   2.678 +    
   2.679 +    u->result = u->root[0];
   2.680 +    state->next = u->next;
   2.681 +    
   2.682 +    state->next(state);return;
   2.683 +}
   2.684 +    
   2.685 +#endif
   2.686 +
   2.687 +
   2.688  /**
   2.689   * snapshot: create a snapshot
   2.690   *   @root: old root node
   2.691 @@ -202,7 +810,7 @@ u64 update(int height, u64 root, u64 key
   2.692  u64 snapshot(u64 root) {
   2.693      radix_tree_node node, newnode;
   2.694  
   2.695 -    if ((node = readblock(getid(root))) == NULL)
   2.696 +    if ((node = rc_readblock(getid(root))) == NULL)
   2.697          return ZERO;
   2.698  
   2.699      newnode = cloneblock(node);
   2.700 @@ -210,7 +818,7 @@ u64 snapshot(u64 root) {
   2.701      if (newnode == NULL)
   2.702          return ZERO;
   2.703      
   2.704 -    root = allocblock(newnode);
   2.705 +    root = rc_allocblock(newnode);
   2.706      freeblock(newnode);
   2.707  
   2.708      if (root == ZERO)
     3.1 --- a/tools/blktap/radix.h	Tue Mar 22 17:30:13 2005 +0000
     3.2 +++ b/tools/blktap/radix.h	Wed Mar 23 23:16:17 2005 +0000
     3.3 @@ -29,4 +29,7 @@ u64 snapshot(u64 root);
     3.4  int collapse(int height, u64 proot, u64 croot);
     3.5  int isprivate(int height, u64 root, u64 key);
     3.6  
     3.7 +
     3.8 +void __rcache_init(void);
     3.9 +
    3.10  #endif /* __RADIX_H__ */
     4.1 --- a/tools/blktap/vdi.c	Tue Mar 22 17:30:13 2005 +0000
     4.2 +++ b/tools/blktap/vdi.c	Wed Mar 23 23:16:17 2005 +0000
     4.3 @@ -171,6 +171,9 @@ void vdi_snapshot(vdi_t *vdi)
     4.4      
     4.5  int __init_vdi()
     4.6  {
     4.7 +    /* sneak this in here for the moment. */
     4.8 +    __rcache_init();
     4.9 +    
    4.10      /* force the registry to be created if it doesn't exist. */
    4.11      vdi_registry_t *vdi_reg = get_vdi_registry();
    4.12      if (vdi_reg == NULL) {
    4.13 @@ -179,6 +182,7 @@ int __init_vdi()
    4.14      }
    4.15      freeblock(vdi_reg);
    4.16      
    4.17 +    
    4.18      return 0;
    4.19  }
    4.20