tapestry.c

该代码是采用后缀匹配的经典结构化p2p模型

}

void
Tapestry::place_backpointer( RPCSet *bp_rpcset, 
			     HashMap<unsigned, backpointer_args*> *bp_resultmap, 
			     IPAddress bpip, int level, 
			     bool remove )
{
  backpointer_args *bpa = New backpointer_args();
  bpa->ip = ip();
  bpa->id = id();
  bpa->level = level;
  bpa->remove = remove;
  backpointer_return bpr;
  TapDEBUG(3) << "sending bp to " << bpip << endl;
  record_stat(STAT_BACKPOINTER, 1, 2);
  GUID bpid = ((Tapestry *)Network::Instance()->getnode(bpip))->id();
  Time timeout = MAXTIME;
  if( _rt->contains( bpid ) ) {
    timeout = _rtt_timeout_factor*_rt->get_time( bpid );
  }
  unsigned rpc = asyncRPC( bpip, &Tapestry::handle_backpointer, bpa, &bpr, 
			   timeout );
  bp_rpcset->insert(rpc);
  bp_resultmap->insert(rpc, bpa);
  // for now assume no failures
}

void
Tapestry::place_backpointer_end( RPCSet *bp_rpcset,
				 HashMap<unsigned,backpointer_args*>*bp_resultmap) 
{

  // wait for each to finish
  uint setsize = bp_rpcset->size();
  RoutingTable *rt_old = _rt;
  for( unsigned int j = 0; j < setsize; j++ ) {
    bool ok;
    unsigned donerpc = rcvRPC( bp_rpcset, ok );
    if( ok ) {
      record_stat(STAT_BACKPOINTER, 0, 0);
    } else {
      // for now we won't worry about what happens if a bp msg is dropped
    }
    backpointer_args *bpa = (*bp_resultmap)[donerpc];
    delete bpa;
  }
  // must have the lock again before returning
  if( _rt != rt_old ) {
    // the routing table changed while we were away (i.e. we crashed)
    // TODO: in the future, if place_backpointer_end is ever called not at
    // the end of an rt function, we might need to do something here
    TapDEBUG(3) << "rt changed while away in place_backpointer_end" << endl;
  }
}

void 
Tapestry::handle_backpointer(backpointer_args *args, backpointer_return *ret)
{
  TapDEBUG(3) << "got a bp msg from " << args->id << endl;

  TapDEBUG(5) << "bp enter" << endl;
  got_backpointer( args->ip, args->id, args->level, args->remove );
  TapDEBUG(5) << "bp exit" << endl;

  // maybe this person should be in our table?
  //add_to_rt( args->ip, args->id );

}

void
Tapestry::got_backpointer( IPAddress bpip, GUID bpid, uint level, bool remove )
{

  if( remove ) {
    _rt->remove_backpointer( bpip, bpid, level );
  } else {
    _rt->add_backpointer( bpip, bpid, level );
  }

}

IPAddress
Tapestry::next_hop( GUID key )
{
  IPAddress *ip = New IPAddress[1];
  ip[0] = 0;
  next_hop( key, &ip, 1 );
  IPAddress rt = ip[0];
  delete ip;
  return rt;
}

void
Tapestry::next_hop( GUID key, IPAddress** ips, uint size )
{
  // first, figure out how many digits we share, and start looking at 
  // that level
  int level = guid_compare( key, id_digits() );
  if( level == -1 ) {
    // it's us!
    if( size > 0 ) {
      (*ips)[0] = ip();
    }
    return;
  }

  RouteEntry *re = _rt->get_entry( level, get_digit( key, level ) );

  // use the first value passed in in ips as a non-nexthop, that is, if 
  // ips[0] is nonnull, do NOT return that one as a possible next hop
  IPAddress dontuse = (*ips)[0];

  // if it has an entry, use it
  if( re != NULL && re->get_first() != NULL && 
      (re->get_first()->_addr != dontuse || re->size() > 1 ) ) {
    // this cannot be us, since this should be the entry where we differ
    // from the key, but just to be sure . . .
     assert( re->get_first()->_addr != id() );
     uint used = 0;
     for( uint i = 0; i < re->size() && used < size; i++ ) {
       if( re->get_at(i)->_addr != dontuse ) {
	 (*ips)[used] = re->get_at(i)->_addr;
	 used++;
       }
     }
     return;
  } else {
    // if there's no such entry, it's time to surrogate route.  yeah baby.
    // keep adding 1 to the digit until you find a match.  If it's us,
    // go up to the next level and keep on trying till the end
    // (From Fig. 3 in the JSAC paper)

    for( uint i = level; i < _digits_per_id; i++ ) {

      uint j = get_digit( key, i );
      while( re == NULL || re->get_first() == NULL || 
	     (re->get_first()->_addr == dontuse && re->size() == 1) ) {

	// NOTE: we can't start with looking at the j++ entry, since
	// this might be the next level up, and we'd want to start at j
	re = _rt->get_entry( i, j );

	j++;
	if( j == _base ) {
	  // think circularly
	  j = 0;
	}
      }
      TapDEBUG(4) << "looking for key " << print_guid(key) << ", level " <<
	i << ", digit " << j << " is " << print_guid(re->get_first()->_id) << 
	endl;
      // if it is us, go around another time
      // otherwise, we've found the next hop
      if( re->get_first()->_addr != ip() ) {
	uint used = 0;
	for( uint k = 0; k < re->size() && used < size; k++ ) {
	  if( re->get_at(k)->_addr != dontuse ) {
	    (*ips)[used] = re->get_at(k)->_addr;
	    used++;
	  }
	}
	return;
      }
      re = NULL;
    }
    
  }

  // didn't find a better surrogate, so it must be us
  if( size > 0 ) {
    (*ips)[0] = ip();
  }

}

int
Tapestry::guid_compare( GUID key1, GUID key2 )
{

  // if they're the same, return -1
  if( key1 == key2 ) {
    return -1;
  }
  uint i = 0;
  // otherwise, figure out where they differ
  for( ; i < _digits_per_id; i++ ) {
    if( get_digit( key1, i ) != get_digit( key2, i ) ) {
      break;
    }
  }

  return (int) i;

}

int
Tapestry::guid_compare( GUID key1, uint key2_digits[] )
{

  uint i = 0;
  // otherwise, figure out where they differ
  for( ; i < _digits_per_id; i++ ) {
    if( get_digit( key1, i ) != key2_digits[i] ) {
      break;
    }
  }

  // if they're the same, return -1
  if( i == _digits_per_id ) {
    return -1;
  }

  return (int) i;

}

int
Tapestry::guid_compare( uint key1_digits[], uint key2_digits[] )
{

  uint i = 0;
  // otherwise, figure out where they differ
  for( ; i < _digits_per_id; i++ ) {
    if( key1_digits[i] != key2_digits[i] ) {
      break;
    }
  }

  // if they're the same, return -1
  if( i == _digits_per_id ) {
    return -1;
  }

  return (int) i;

}


void
Tapestry::leave(Args *args)
{
  crash (args);
}

void
Tapestry::crash(Args *args)
{
  if( _verbose ) {
    TapDEBUG(0) << "Tapestry crash" << endl;
  }  

  // XXX: Thomer says: not necessary
  // crash();

  // clear out routing table, and any other state that might be lying around
  uint r = _rt->redundancy();
  delete _rt;
  if( _lookup_learn ) {
    delete _cachebag;
  }
  joined = false;

  // clear join state also
  _joining = false;
  for( uint l = 0; l < initlist.size(); l++ ) {
    delete initlist[l];
  }
  initlist.clear();
  _recently_dead.clear();
  _rt = New RoutingTable(this, r);
  if( _lookup_learn ) {
    _cachebag = New RoutingTable(this, r);
  }
  // TODO: should be killing these waiting RPCs instead of allowing them
  // to finish normally.  bah.
  _waiting_for_join->notifyAll();
  TapDEBUG(2) << "crash exit" << endl;

  notifyObservers( (ObserverInfo *) "crash" );
}

string
Tapestry::print_guid( GUID id )
{

  // NOTE: for now only handle up to base 256 (should be plenty)

  uint multiplier = 1;
  uint extra = 1;
  if( _base > 16 ) {
    multiplier++;
    extra += _digits_per_id;
  }

  uint size = _digits_per_id*multiplier+extra;
  char buf[size];

  //printf( "initial guid: %16qx\n", id );
  // print it out, digit by digit
  // (in order to get leading zeros)
  uint j = 0;
  for( uint i = 0; i < size-1; i++ ) {
    uint digit = get_digit( id, j );
    if( _base > 16 ) {
      sprintf( &(buf[i]), "%.2x", digit );
      i += 2;
    } else {
      sprintf( &(buf[i]), "%x", digit );
    }
    j++;
    if( _base > 16 && j != _digits_per_id ) {
      sprintf( &(buf[i]), "-" );
    }
  }

  return string(buf);

}

void
Tapestry::print_guid( GUID id, ostream &s )
{
  
  s << print_guid( id );
}

uint
Tapestry::get_digit( GUID id, uint digit )
{

  // can't request a digit higher than what we have, right?
  // 0-based . . .
  assert( digit < _digits_per_id );

  // shift left to get rid of leading zeros
  GUID shifted_id = id << (digit*_bits_per_digit);
  // shift right to get rid of the others
  shifted_id = shifted_id >> (sizeof(GUID)*8-_bits_per_digit);

  return shifted_id;
}

Tapestry::GUID
Tapestry::lookup_cheat( GUID key ) 
{

  // using global knowledge, figure out who the owner of this key should
  // be, given the set of live nodes
  const set<Node*> *l = Network::Instance()->getallnodes();
  set<Node*>::iterator pos;
  vector<Tapestry::GUID> lid;

  // get the keys digits
  uint key_digits[_digits_per_id];
  for( uint i = 0; i < _digits_per_id; i++ ) {
    key_digits[i] = get_digit( key, i );
  }

  Tapestry *c = 0;
  int maxmatch = -2;
  for (pos = l->begin(); pos != l->end(); ++pos) {
    c = (Tapestry *)(*pos);
    assert(c);
    // only care about live, joined nodes (or live nodes in our rt)
    if( c->alive() && (c->is_joined() || _rt->contains(c->id())) ) {
      int match = guid_compare( c->id_digits(), key_digits );
      if( match == -1 ) {
	return c->id();
      } else if( match > maxmatch ) {
	maxmatch = match;
	lid.clear();
      }
      if( match == maxmatch ) {
	lid.push_back(c->id());
      }
    }
  }

  // now we have a list of all the nodes that match a maximum number of digits
  // find the closest one in terms of surrogate routing.
  GUID bestmatch = lid[0];
  for( uint i = 1; i < lid.size(); i++ ) {
    GUID next = lid[i];
    TapDEBUG(4) << "comparing " << print_guid(bestmatch) << " with " <<
      print_guid( next ) << endl;
    // surrogate routing sucks.  must find the one who has a maxmatch digit
    // closest but greater than the keys.  If not, the one with the lowest
    // maxmatch digit.  For ties, go up a level and repeat
    for( uint j = 0; j < _digits_per_id - maxmatch; j++ ) {
      uint next_digit = get_digit( next, maxmatch+j );
      uint best_digit = get_digit( bestmatch, maxmatch+j );
      uint key_digit = key_digits[maxmatch+j];
      if( (next_digit >= key_digit && best_digit >= key_digit && 
	   next_digit < best_digit ) ||
	  (next_digit < key_digit && best_digit < key_digit &&
	   next_digit < best_digit) ||
	  (next_digit >= key_digit && best_digit < key_digit) ) {

	TapDEBUG(4) << "new best: digit " << (maxmatch+j) << " " << next_digit 
		    << " " << best_digit << " " << key_digit << endl;
	bestmatch = next;
	break;

      } else if( next_digit != best_digit ) {
	// it's not a tie, so no need to go on
	break;
      }

    }

  }

  return bestmatch;

}

//////////  RouteEntry  ///////////

RouteEntry::RouteEntry( uint redundancy )
{
  _size = 0;
  NODES_PER_ENTRY = redundancy;
  _nodes = New NodeInfo *[NODES_PER_ENTRY];
}

RouteEntry::RouteEntry( NodeInfo *first_node, uint redundancy )
{
  assert( first_node );
  NODES_PER_ENTRY = redundancy;
  _nodes = New NodeInfo *[NODES_PER_ENTRY];
  _nodes[0] = first_node;
  _size = 1;
}

RouteEntry::~RouteEntry()
{
  for( uint i = 0; i < _size; i++ ) {

    if( _nodes[i] != NULL ) {
      delete _nodes[i];
      _nodes[i] = NULL;
    }
  }
  delete [] _nodes;
}

NodeInfo *
RouteEntry::get_first()
{
  return _nodes[0];
}

NodeInfo *
RouteEntry::get_at( uint pos )
{
  assert( pos < NODES_PER_ENTRY );
  return _nodes[pos];
}

void
RouteEntry::remove_at( uint pos )
{
  assert( pos < NODES_PER_ENTRY );
  if( pos >= _size ) {
    // don't even have this guy
    return;
  } else {
    // bring everyone else up one
    uint i = pos;
    delete _nodes[i];
    for( ; i+1 < _size; i++ ) {
      _nodes[i] = _nodes[i+1];
    }
    _nodes