kademlia.c

P2P模拟器

    return;

  assert(id);
  assert(ip);
}
// }}}

// {{{ k_bucket::k_bucket
k_bucket::k_bucket(k_bucket *parent, Kademlia *k) : parent(parent), _kademlia(k)
{
  child[0] = child[1] = 0;
  nodes = 0;
  replacement_cache = 0;
  leaf = false;
}
// }}}
// {{{ k_bucket::~k_bucket
k_bucket::~k_bucket()
{
  if(leaf) {
    delete nodes;
    delete replacement_cache;
    return;
  }

  delete child[0];
  delete child[1];
}
// }}}
// {{{ k_bucket::traverse
void
k_bucket::traverse(k_traverser *traverser, Kademlia *k, string prefix, unsigned depth, unsigned leftright)
{
//  Kademlia::NodeID _id = kademlia()->id();
  // KDEBUG(1) << "k_bucket::traverser for " << traverser->type() << ", prefix = " << prefix << endl;
  checkrep();

  if(!leaf) {
    if(!k->alive() || !child[0])
      return;
    child[0]->traverse(traverser, k, prefix + "0", depth+1, 0);
    if(!k->alive() || !child[1] || leaf)
      return;
    child[1]->traverse(traverser, k, prefix + "1", depth+1, 1);
    if(!k->alive())
      return;
    checkrep();
    return;
  }


  if(!k->alive())
    return;

  // we're a leaf
  traverser->execute(this, prefix, depth, leftright);

  checkrep();
}
// }}}
// {{{ k_bucket::find_node
void
k_bucket::find_node(Kademlia::NodeID key, vector<k_nodeinfo*> *v,
    unsigned nhits, unsigned depth)
{
  checkrep();

//  // Kademlia::NodeID _id = kademlia()->id();
  Kademlia::closer::n = key;

  // recurse deeper in the right direction if we can
  if(!leaf) {
    unsigned leftmostbit = Kademlia::getbit(key, depth);
    if(v->size() < nhits)
      child[leftmostbit]->find_node(key, v, nhits, depth+1);
    if(v->size() < nhits)
      child[leftmostbit^1]->find_node(key, v, nhits, depth+1);
    checkrep();
    return;
  }

  // collect stuff from the k-bucket itself
  for(unsigned i=0; i<nodes->size(); i++) {
    v->push_back(nodes->get(i));
    if(v->size() >= nhits) {
      checkrep();
      return;
    }
  }

  if(Kademlia::use_replacement_cache != Kademlia::FULL) {
    checkrep();
    return;
  }

  // NB: optimization.
  // collect stuff from replacement cache.
  for(int i = replacement_cache->size()-1; i >= 0; i--) {
    v->push_back(replacement_cache->get(i));
    if(v->size() >= nhits) {
      checkrep();
      return;
    }
  }

  checkrep();
}
// }}}
// {{{ k_bucket::insert
// pre: id is in flyweight, its timestamp (lastts) has been set.
// post: if id was already in k-bucket, its position is updated.
//       if id was not in k-bucket :
//              if k-bucket has space, id is added
//              if k-bucket is full, id is put in replacement cache
void
k_bucket::insert(Kademlia::NodeID id, bool touch, bool init_state, string prefix, unsigned depth)
{
  checkrep();
  // assert(kademlia()->flyweight.find(id, 0));

  // Kademlia::NodeID _id = kademlia()->id();
  // KDEBUG(1) << "k_bucket::insert " << Kademlia::printbits(id) << ", prefix = " << prefix << endl;

  // recurse deeper if we can
  if(!leaf) {
    unsigned leftmostbit = Kademlia::getbit(id, depth);
    // KDEBUG(1) << "k_bucket::insert heading towards " << leftmostbit << endl;
    child[leftmostbit]->insert(id, touch, init_state, prefix + (leftmostbit ? "1" : "0"), depth+1);
    checkrep();
    return;
  }

  // if not in k-bucket yet, or there's more space: insert it.
  if(nodes->contains(id) || !nodes->full()) {
    nodes->insert(id, touch);
    nodes->checkrep();
    return;
  }

  if(Kademlia::use_replacement_cache == Kademlia::DISABLED) {
    checkrep();
    return;
  }

  // we're full.  put in replacement_cache.
  replacement_cache->insert(id, touch);
  replacement_cache->checkrep();

  checkrep();
}
// }}}
// {{{ k_bucket::erase
void
k_bucket::erase(Kademlia::NodeID id, string prefix, unsigned depth)
{
  checkrep();

  // recurse deeper
  if(!leaf) {
    unsigned leftmostbit = Kademlia::getbit(id, depth);
    child[leftmostbit]->erase(id, prefix + (leftmostbit ? "1" : "0"), depth+1);
    checkrep();
    return;
  }

  // if not in k-bucket itself, it must be in replacement_cache.  remove from
  // there.
  if(!nodes->contains(id)) {
    k_nodeinfo *ki = kademlia()->flyweight[id];
    if(replacement_cache->contains(ki->id))
      replacement_cache->erase(ki->id);
    checkrep();
    return;
  }

  // remove from k-bucket
  nodes->erase(id);

  // get latest from replacement_cache to nodes
  if(Kademlia::use_replacement_cache == Kademlia::DISABLED || !replacement_cache->size()) {
    checkrep();
    return;
  }

  k_nodeinfo *ki = replacement_cache->last(); // youngest
  // assert(ki);
  // assert(ki->id);
  // assert(kademlia()->flyweight.find(ki->id, 0));
  nodes->insert(ki->id, false);
  replacement_cache->erase(ki->id);

  checkrep();
}
// }}}
// {{{ k_bucket::collapse
// transform back from node to leaf
void
k_bucket::collapse()
{
  // Kademlia::NodeID _id = kademlia()->id();
  // KDEBUG(2) << "k_bucket::collapse" << endl;
  checkrep();

  if(!leaf) {
    child[0]->collapse();
    child[1]->collapse();
  } else {
    nodes->clear();
    replacement_cache->clear();
  }

  checkrep();
}
// }}}
// {{{ k_bucket::checkrep
void
k_bucket::checkrep()
{
  if(!Kademlia::docheckrep)
    return;

  assert(_kademlia);

  if(!leaf) {
    assert(child[0] && child[1]);
    return;
  }


  // checkreps for leaf
  assert(nodes);
  assert(replacement_cache);
  nodes->checkrep();
  replacement_cache->checkrep();
}
// }}}

// {{{ k_stabilizer::execute
void
k_stabilizer::execute(k_bucket *k, string prefix, unsigned depth, unsigned leftright)
{
  // for // KDEBUG purposes
  Kademlia *mykademlia = k->kademlia();
  Kademlia::NodeID _id = mykademlia->id();

  if(!k->leaf || !mykademlia->alive())
    return;

  // return if any entry in this k-bucket is fresh
  if(!Kademlia::force_stabilization) {
    for(unsigned i = 0; i < k->nodes->size(); i++) {
      // XXX: this is the sign of bad shit going on.  get out.
      // it doesn't really, really matter that we're not completing this round of
      // stabilization.  better than crashing the simulator, anyway.
      k_nodeinfo *ki = k->nodes->get(i);
      if(!mykademlia->flyweight[ki->id])
        return;

      if(now() - ki->lastts < Kademlia::refresh_rate)
        return;
    }
  }

  // Oh.  stuff in this k-bucket is old, or we don't know anything. Lookup a
  // random key in this range.
  Kademlia::NodeID mask = 0L;
  for(unsigned i=0; i<Kademlia::idsize; i++) {
    unsigned bit = 1;
    if(i > depth)
      bit = (unsigned) random() & 0x1;
    mask |= (((Kademlia::NodeID) bit) << (Kademlia::idsize-i));
  }

  Kademlia::NodeID random_key = _id & mask;
  // KDEBUG(2) << "k_stabilizer: prefix = " << prefix << ", mask = " << Kademlia::printbits(mask) << ", random_key = " << Kademlia::printbits(random_key) << endl;

  // lookup the random key and update this k-bucket with what we learn
  Kademlia::lookup_args la(mykademlia->id(), mykademlia->ip(), random_key);
  la.stattype = Kademlia::STAT_STABILIZE;
  Kademlia::lookup_result lr;

  mykademlia->do_lookup(&la, &lr);
  if(!mykademlia->alive())
    return;

  // update our k-buckets
  NODES_ITER(&lr.results) {
    mykademlia->update_k_bucket(i->id, i->ip);
  }
}
// }}}
// {{{ k_stabilized::execute
void
k_stabilized::execute(k_bucket *k, string prefix, unsigned depth, unsigned leftright)
{
  // for // KDEBUG purposes
  Kademlia::NodeID _id = k->kademlia()->id();

  // if we know about nodes in this part of the ID space, great.
  if(!k->nodes->empty())
    return;

  // KDEBUG(2) << "stabilized: " << prefix << " not present, depth = " << depth << ", prefix = " << prefix << ", leftright = " << leftright << endl;

  //
  // Node claims there is no node to satisfy this entry in the finger table.
  // Check whether that is true.
  //
  Kademlia::NodeID upper = 0, lower = 0;
  for(unsigned i=0; i<Kademlia::idsize; i++) {
    if(i < (depth-1)) {
      unsigned bit = Kademlia::getbit(_id, i);
      lower |= (((Kademlia::NodeID) bit) << Kademlia::idsize-i-1);
      upper |= (((Kademlia::NodeID) bit) << Kademlia::idsize-i-1);
    } else if(i == (depth-1) && leftright) {
      lower |= (((Kademlia::NodeID) leftright) << Kademlia::idsize-i-1);
      upper |= (((Kademlia::NodeID) leftright) << Kademlia::idsize-i-1);
    } else if(i > (depth-1))
      upper |= (((Kademlia::NodeID) 1) << Kademlia::idsize-i-1);
  }

  // KDEBUG(2) << "stabilized: lower = " << Kademlia::printID(lower) << endl;
  // KDEBUG(2) << "stabilized: upper = " << Kademlia::printID(upper) << endl;

  // yields the node with smallest id greater than lower
  vector<Kademlia::NodeID>::const_iterator it = upper_bound(_v->begin(), _v->end(), lower);

  // check that this is smaller than upper.  if so, then this node would
  // qualify for this entry in the finger table, so the node that says there
  // is no such is WRONG.
  if(it != _v->end() && *it <= upper) {
    // KDEBUG(2) << "stabilized: prefix " << prefix << " on depth " << depth << " is invalid, but " << Kademlia::printID(*it) << " matches " << endl;
    _stabilized = false;
  }
  // // assert(false);
}
// }}}
// {{{ k_finder::execute
void
k_finder::execute(k_bucket *k, string prefix, unsigned depth, unsigned leftright)
{
  if(!k->leaf)
    return;

  k->checkrep();
  for(unsigned i = 0; i < k->nodes->size(); i++) {
    if(k->nodes->get(i)->id == _n)
      _found++;
  }

  for(int i = k->replacement_cache->size()-1; i >= 0; i--)
    if(k->replacement_cache->get(i)->id == _n)
      _found++;
}
// }}}
// {{{ k_dumper::execute
void
k_dumper::execute(k_bucket *k, string prefix, unsigned depth, unsigned leftright)
{
  string spaces = "";
  for(unsigned i=0; i<depth; i++)
    spaces += "  ";
  cout << spaces << "prefix: " << prefix << ", depth " << depth << endl;
  for(unsigned i = 0; i < k->nodes->size(); i++) {
    k_nodeinfo *ki = k->nodes->get(i);

    cout << spaces << "  " << Kademlia::printbits(ki->id) << ", lastts = " << ki->lastts << endl;
  }

  cout << spaces << "prefix: " << prefix << ", depth " << depth << ", replacement cache: " << endl;
  for(int i = k->replacement_cache->size()-1; i >= 0; i--) {
    cout << spaces << "  " << Kademlia::printID(k->replacement_cache->get(i)->id) << ", lastts = " << k->replacement_cache->get(i)->lastts << endl;
  }
}
// }}}
// {{{ k_check::execute
void
k_check::execute(k_bucket *k, string prefix, unsigned depth, unsigned leftright)
{
  if(!k->leaf)
    return;

  k->checkrep();

  const set<Node*> *l = Network::Instance()->getallnodes();

  // go through all pointers in node
  for(unsigned i = 0; i < k->nodes->size(); i++) {
    // k_nodeinfo *ki = k->nodes->get(i);
    for(set<Node*>::iterator pos = l->begin(); pos != l->end(); ++pos) {
      Kademlia *kad = (Kademlia*) *pos;
      if(kad->id() == k->kademlia()->id())
        continue;
      /*
      for(HashMap<Kademlia::NodeID, k_nodeinfo*>::const_iterator j = kad->flyweight.begin(); j; j++)
          // assert(j.value() != ki);
      */
    }
  }

  for(int i = k->replacement_cache->size()-1; i >= 0; i--) {
    for(set<Node*>::iterator pos = l->begin(); pos != l->end(); ++pos) {
      Kademlia *kad = (Kademlia*) *pos;
      if(kad->id() == k->kademlia()->id())
        continue;
      /*
      for(HashMap<Kademlia::NodeID, k_nodeinfo*>::const_iterator j = kad->flyweight.begin(); j; j++)
          // assert(j.value() != *i);
      */
    }
  }
}
// }}}

#include "p2psim/bighashmap.cc"