merkle_tree_disk.c

基于DHT的对等协议

  } else if (_writer) {
    _free_leafs.clear ();
    _free_internals.clear ();

    // read in the free list
    int nfree = _md.num_leaf_free+_md.num_internal_free;
    u_int32_t freelist[nfree];
    int nread = fread (&freelist, sizeof (u_int32_t), nfree, _index);
    assert (nread == nfree);

    for (int i = 0; i < nread; i++) {
      u_int32_t pointer = freelist[i];
      if (pointer % 2 == 0) {
	_free_internals.push_back (pointer >> 1);
      } else {
	_free_leafs.push_back (pointer >> 1);
      }
    }
  }

  return make_node (_md.root);
}

merkle_node *
merkle_tree_disk::make_node (u_int32_t block_no, MERKLE_DISK_TYPE type)
{
  return New merkle_node_disk (_internal, _leaf, type, block_no);
}

merkle_node *
merkle_tree_disk::make_node (u_int32_t pointer)
{
  // even == internal, odd == leaf
  if (pointer % 2 == 0) {
    return make_node (pointer >> 1, MERKLE_DISK_INTERNAL);
  } else {
    return make_node (pointer >> 1, MERKLE_DISK_LEAF);
  }
}

// returns a block_no without the type bit on the end
void
merkle_tree_disk::free_block (u_int32_t block_no, MERKLE_DISK_TYPE type)
{
  assert (_writer);

  // don't want these blocks being used until the root gets switched over
  // in write_metadata, so keep them on a separate list
  if (type == MERKLE_DISK_LEAF) {
    _future_free_leafs.push_back (block_no);
  } else {
    _future_free_internals.push_back (block_no);
  }
}

// returns a block_no without the type bit on the end
u_int32_t
merkle_tree_disk::alloc_free_block (MERKLE_DISK_TYPE type)
{
  assert (_writer);

  u_int32_t ret;
  // if there are any free
  if (type == MERKLE_DISK_LEAF) {
    if (_md.num_leaf_free > 0) {
      ret = _free_leafs.pop_front ();
      _md.num_leaf_free--;
    } else {
      ret = _md.next_leaf;
      _md.next_leaf++; 
    }
  } else {
    if (_md.num_internal_free > 0) {
      ret = _free_internals.pop_front ();
      _md.num_internal_free--;
    } else {
      ret = _md.next_internal;
      _md.next_internal++; 
    }
  }

  return ret;
}

void
merkle_tree_disk::switch_root (merkle_node_disk *n)
{
  assert (_writer);
  u_int32_t newroot = n->get_block_no ();
  newroot <<= 1;
  if (n->isleaf()) {
    newroot |= 0x00000001;
  }
  _md.root = newroot;
  // NOTE: there should only be one thread on the machine that is
  // inserting or removing blocks and writing metadata.  Any others
  // need to be readonly
  write_metadata ();
}

int
merkle_tree_disk::remove (u_int depth, merkle_hash& key, 
			  merkle_node *n)
{
  assert (_writer);

  merkle_node_disk *nd = (merkle_node_disk *) n;
  MERKLE_DISK_TYPE old_type;

  if (n->isleaf ()) {
    chordID k = static_cast<bigint> (key);
    merkle_key *mkey = nd->keylist[k];
    assert(mkey);
    nd->keylist.remove(mkey);
    delete mkey;
    old_type = MERKLE_DISK_LEAF;
  } else {
    u_int32_t branch = key.read_slot(depth);
    merkle_node *child = n->child (branch);
    remove (depth+1, key, child);
    nd->set_child ((merkle_node_disk *) child, branch);
    old_type = MERKLE_DISK_INTERNAL;
  }

  MERKLE_DISK_TYPE new_type = old_type;

  n->count--;
  if (!n->isleaf () && n->count <= 64) {
    // free all the children blocks and copy their keys
    uint added = 0;
    for (uint i = 0; i < 64; i++) {
      merkle_node_disk *child = (merkle_node_disk *) nd->child(i);
      free_block (child->get_block_no(), MERKLE_DISK_LEAF);
      assert (child->isleaf ());
      merkle_key *k = child->keylist.first ();
      uint j = 0;
      while (k != NULL) {
	merkle_key *knew = New merkle_key (k->id);
	nd->keylist.insert (knew);
	added++;
	j++;
	k = child->keylist.next (k);
      }
      assert (j == child->count);
      child->keylist.clear ();
    }
    assert (added == n->count);

    // this will copy the keys around
    n->internal2leaf();
    assert (n->isleaf ());
    new_type = MERKLE_DISK_LEAF;
  }

  nd->rehash ();

  // write this block out to a new place on disk, then switch the root
  // atomically
  u_int32_t block_no = alloc_free_block (new_type);
  free_block (nd->get_block_no(), old_type);
  nd->set_block_no (block_no);
  nd->write_out ();

  return 0;
}

int
merkle_tree_disk::remove (merkle_hash &key)
{
  merkle_node_disk *curr_root = (merkle_node_disk *) get_root();
  int r = remove (0, key, curr_root);
  switch_root (curr_root);
  delete curr_root;
  return r;
}

void
merkle_tree_disk::leaf2internal (uint depth, merkle_node_disk *n)
{
  assert (n->isleaf () && n->count == 64);
  // NOTE: bottom depth may only have 16??
  merkle_key *k = n->keylist.first ();
  array< vec<chordID>, 64> keys;
  uint added = 0;
  while (k != NULL) {
    merkle_hash h (k->id);
    u_int32_t branch = h.read_slot (depth);
    //warn << "picked branch " << branch << " for key " << k->id << ", hash " 
    // << h << "\n";
    keys[branch].push_back(k->id);
    k = n->keylist.next(k);
    added++;
  }
  assert (added == n->count);

  n->leaf2internal ();
  assert (!n->isleaf ());

  added = 0;
  for (uint i = 0; i < 64; i++) {
    // zero the new guy out
    uint block_no = alloc_free_block (MERKLE_DISK_LEAF);
    merkle_leaf_node new_leaf;
    bzero (&new_leaf, sizeof (merkle_leaf_node));
    fseek (_leaf, block_no*sizeof (merkle_leaf_node), SEEK_SET);
    fwrite (&new_leaf, sizeof (merkle_leaf_node), 1, _leaf);

    merkle_node_disk *child = 
      (merkle_node_disk *) make_node (block_no, MERKLE_DISK_LEAF);

    vec<chordID> v = keys[i];
    for (uint j = 0; j < v.size(); j++) {
      child->add_key (v[j]);
    }
    added += child->count;
    child->rehash ();
    n->set_child (child, i);
    child->write_out ();
    delete child;
  }

  assert (added == n->count);
}

int
merkle_tree_disk::insert (u_int depth, merkle_hash& key, merkle_node *n)
{
  int ret = 0;
  merkle_node_disk *nd = (merkle_node_disk *) n;

  MERKLE_DISK_TYPE old_type;
  if (n->isleaf ()) {
    old_type = MERKLE_DISK_LEAF;
    if (n->leaf_is_full ()) {
      leaf2internal (depth, nd);
      assert (!n->isleaf());
    }
  } else {
    old_type = MERKLE_DISK_INTERNAL;
  } 

  MERKLE_DISK_TYPE type;
  if (n->isleaf ()) {
    type = MERKLE_DISK_LEAF;
    nd->add_key (key);
  } else {
    type = MERKLE_DISK_INTERNAL;
    u_int32_t branch = key.read_slot (depth);
    merkle_node *child = n->child (branch);
    //warn << "inserting " << key << " into child " 
    //	 << ((merkle_node_disk *) child)->get_block_no () << " on branch " 
    // 	 << branch << " at depth " << depth << " and leaf " 
    //	 << child->isleaf() << " with count " << child->count << "\n";
    ret = insert (depth+1, key, child);
    nd->set_child ((merkle_node_disk *) child, branch);
    n->count++;
  }

  nd->rehash ();
  
  // write this block out to a new place on disk, then switch the root
  // atomically
  u_int32_t block_no = alloc_free_block(type);
  free_block (nd->get_block_no(), old_type);
  nd->set_block_no (block_no);
  nd->write_out ();

  return ret;
}

int
merkle_tree_disk::insert (merkle_hash &key)
{
  assert (_writer);
  merkle_node_disk *curr_root = (merkle_node_disk *) get_root();
  int ret = insert (0, key, curr_root);
  switch_root (curr_root);
  delete curr_root;
  return ret;
}

void
merkle_tree_disk::lookup_release (merkle_node *n)
{
  delete n;
}

merkle_node *
merkle_tree_disk::lookup (u_int *depth, u_int max_depth,
			  const merkle_hash &key)
{
  *depth = 0;
  merkle_node *curr_root = get_root ();
  merkle_node *ret = merkle_tree::lookup (depth, max_depth, key, 
					  curr_root);
  ret = make_node(((merkle_node_disk *) ret)->get_block_no (),
		  ret->isleaf () ? MERKLE_DISK_LEAF : MERKLE_DISK_INTERNAL);
  delete curr_root;
  return ret;
}

merkle_node *
merkle_tree_disk::lookup (u_int depth, const merkle_hash &key)
{
  u_int depth_ignore = 0;
  merkle_node *curr_root = get_root ();
  merkle_node *ret = merkle_tree::lookup (&depth_ignore, depth, key, 
					  curr_root);
  ret = make_node (((merkle_node_disk *) ret)->get_block_no(),
		   ret->isleaf() ? MERKLE_DISK_LEAF : MERKLE_DISK_INTERNAL);
  delete curr_root;
  return ret;
}

merkle_node *
merkle_tree_disk::lookup_exact (u_int depth, const merkle_hash &key)
{
  u_int realdepth = 0;
  merkle_node *curr_root = get_root ();
  merkle_node *ret = merkle_tree::lookup (&realdepth, depth, key, curr_root);
  assert (realdepth <= depth);
  if (realdepth != depth) {
    ret = NULL;
  } else {
    ret = make_node (((merkle_node_disk *) ret)->get_block_no (), 
		     ret->isleaf () ? MERKLE_DISK_LEAF: MERKLE_DISK_INTERNAL);
  }
  delete curr_root;
  return ret;
}

vec<merkle_hash>
get_all_keys (u_int depth, const merkle_hash &prefix, merkle_node_disk *n)
{
  vec<merkle_hash> keys;
  if (n->isleaf ()) {
    merkle_key *k = n->keylist.first ();
    while (k != NULL) {
      merkle_hash key (k->id);
      if (prefix_match(depth, key, prefix)) {
	keys.push_back (key);
      }
      k = n->keylist.next (k);
    }
  } else {
    for (uint i = 0; i < 64; i++) {
      vec<merkle_hash> child_keys = 
	get_all_keys (depth, prefix, (merkle_node_disk *) n->child (i));
      for (uint j = 0; j < child_keys.size(); j++) {
	keys.push_back (child_keys[j]);
      }
    }
  }

  return keys;
}

vec<merkle_hash>
merkle_tree_disk::database_get_keys (u_int depth, const merkle_hash &prefix)
{
  vec<merkle_hash> keys;

  // find all the keys matching this prefix
  merkle_node *r = get_root ();
  merkle_node *n = r;
  for (u_int i = 0; i < depth && !n->isleaf (); i++) {
    u_int32_t branch = prefix.read_slot (i);
    n = n->child (branch);
  }

  // now we have the node and the right depth that matches the prefix.
  // Read all the keys under this node that match the prefix
  keys = get_all_keys (depth, prefix, (merkle_node_disk *) n);
  delete r;
  return keys;
}

bool
get_keyrange_recurs (merkle_hash min, chordID max, u_int n, 
		     uint depth, vec<chordID> *keys, merkle_node_disk *node,
		     bool start_left)
{
  // go down until you find the leaf responsible for min
  // add all of its keys up to n, less than max.  If you haven't
  // found more than n keys, set min to the last key and keep
  // going

  bool over_max = false;

  if (node->isleaf ()) {
    chordID min_id = static_cast<bigint> (min);
    merkle_key *k = node->keylist.first ();
    merkle_key *last_key = NULL;

    while (k != NULL && keys->size () < n) {
      if (betweenbothincl (min_id, max, k->id)) {
	keys->push_back (k->id);
      }
      last_key = k;
      k = node->keylist.next (k);
    }
    
    // it's only over the maximum if:
    //   a) there's a key in this node, AND
    //   b) some other node has already been tried, AND
    //   c) that key is greater than max
    if (last_key != NULL && start_left && 
	betweenbothincl (min_id, last_key->id, max)) {
      over_max = true;
    } else {
      over_max = false;
    }
    // don't need a special case here, since we look at all the keys
  } else {
    u_int32_t branch = min.read_slot (depth);
    if (start_left) {
      branch = 0;
    }
    bool first_time = true;

    while (keys->size () < n && branch < 64 && !over_max) {
      merkle_node_disk *child = (merkle_node_disk *) node->child (branch);
      bool sl = start_left;
      // if we've already gone down one branch at this depth, don't read the
      // slot for the starting branch on any branch
      if (!first_time) {
	sl = true;
      }
      over_max = get_keyrange_recurs (min, max, n, depth+1, keys, child, sl);
      first_time = false;
      branch++;
    }

    // special case for when we hit the right edge of the ring
    if (depth == 0 && !over_max && keys->size () < n && 
	betweenrightincl (static_cast<bigint> (min), max, 0))
    {
      over_max = get_keyrange_recurs (0, max, n, depth, keys, node, true);
    }
  }

  return over_max;
}

vec<chordID> 
merkle_tree_disk::get_keyrange (chordID min, chordID max, u_int n)
{
  vec<chordID> keys;

  merkle_node *root = get_root ();
  if(root->count > 0) {
    get_keyrange_recurs (min, max, n, 0, &keys, 
			 (merkle_node_disk *) root, false);
  }
  delete root;

  return keys;
}

bool
merkle_tree_disk::key_exists (chordID key)
{
  merkle_node_disk *n = 
    (merkle_node_disk *) merkle_tree::lookup (key);
  merkle_key *mkey = n->keylist[key];
  lookup_release (n);

  return (mkey != NULL);
}