kademlia.h

P2P模拟器

  struct ping_result {
  };
  // }}}
  // {{{ erase_args and erase_result
  struct erase_args {
    erase_args(vector<NodeID> * ids) : ids(ids) {}
    vector<NodeID> *ids;
  };

  struct erase_result {
  };
  // }}}

  //
  // RPCable methods
  //
  void do_lookup(lookup_args*, lookup_result*);
  void find_value(find_value_args*, find_value_result*);
  void do_ping(ping_args*, ping_result*);
  void find_node(find_node_args*, find_node_result*);
  void do_erase(erase_args*, erase_result*);


  //
  // set methods
  //

  // hack to pre-initialize k-buckets
  void reschedule_stabilizer(void*);
  friend class k_bucket;

  // use_replacement_cache values:
  // DISABLED: no
  // ENABLED: yes, but not as aide in find_node
  // FULL: yes
  enum use_replacement_cache_t {
    DISABLED = 0,
    ENABLED,
    FULL
  };

  //
  // member variables
  //
  static bool docheckrep;
  static use_replacement_cache_t use_replacement_cache;
  static unsigned k;                    // number of nodes per k-bucket
  static unsigned k_tell;               // number of values returned by find_node
  static unsigned alpha;                // alpha from kademlia paper; no of simultaneous RPCs
  static unsigned debugcounter;         // 
  static unsigned stabilize_timer;      // how often to stabilize
  static unsigned refresh_rate;         // how often to refresh info
  static unsigned erase_count;          // after how many timeouts to remove
  static bool learn_stabilize_only;     // do we learn from RPCs?
  static bool force_stabilization;      // stabilize all buckets, not only old ones
  static bool death_notification;       // if your neighbor told you about a 
                                        // dead node, tell them about it.
  static Time max_lookup_time;          // how long do we keep retrying
  static Time _default_timeout;         // default timeout
  static unsigned _to_cheat;            // whether to use roundtrip estimates as timeout
  static unsigned _to_multiplier;       // the multiplier used to calculate timeout
  static k_nodeinfo_pool *pool;         // pool of k_nodeinfo_pool
  static const unsigned idsize = 8*sizeof(Kademlia::NodeID);
  HashMap<NodeID, k_nodeinfo*> flyweight;
// }}}
// {{{ private
private:
  Time timeout(IPAddress dst);      //how to calculate timeout for RPC
  void init_k_bucket_tree();       //jy: init k bucket tree root
  void insert(NodeID, IPAddress, Time = 0, char = 0, bool = false);
  void touch(NodeID);
  void erase(NodeID);
  void stabilize();

  NodeID _id;           // my id
  k_nodeinfo _me;      // info about me
  k_bucket *_root;
  bool _joined;

  void record_stat(stat_type, unsigned, unsigned);
  friend class k_stabilizer;
  void update_k_bucket(NodeID, IPAddress, Time = 0);
  void clear();
  void lookup_wrapper(lookup_wrapper_args*);

  // number of instantiated kademlias.
  static unsigned _nkademlias;

  // global statistics
  static long long unsigned _rpc_bytes;
  static long unsigned _good_rpcs;
  static long unsigned _bad_rpcs;
  static long unsigned _ok_by_reaper;
  static long unsigned _timeouts_by_reaper;
  static Time _time_spent_timeouts;

  static long unsigned _good_lookups;
  static long unsigned _good_attempts;
  static long unsigned _bad_attempts;
  static long unsigned _lookup_dead_node;
  static long unsigned _ok_failures;
  static long unsigned _bad_failures;

  static Time _good_total_latency;
  static Time _good_lookup_latency;
  static Time _good_ping_latency;
  static long unsigned _good_timeouts;

  static long unsigned _good_hops;
  static Time _good_hop_latency;

  static Time _bad_lookup_latency;
  static long unsigned _bad_timeouts;
  static long unsigned _bad_hops;
  static Time _bad_hop_latency;



  //
  // utility 
  //
  class callinfo { public:
    callinfo(k_nodeinfo ki, find_node_args *fa, find_node_result *fr)
      : ki(ki), fa(fa), fr(fr) { before = 0; }
    ~callinfo() {
      delete fa;
      delete fr;
    }
    k_nodeinfo ki;
    find_node_args *fa;
    find_node_result *fr;
    Time before;
  };

  struct reap_info {
    reap_info() {}
    ~reap_info() { 
      delete rpcset; 
      delete outstanding_rpcs; 
      delete who_told_me;
      delete is_dead;
    }

    Kademlia *k;
    RPCSet *rpcset;
    HashMap<unsigned, callinfo*>* outstanding_rpcs;
    HashMap<NodeID, vector<IPAddress> * > *who_told_me;
    HashMap<NodeID, bool> *is_dead;
    stat_type stat;
  };

  // hack for initstate
  static NodeID *_all_kademlias;
  static HashMap<NodeID, Kademlia*> *_nodeid2kademlia;
// }}}
};

// }}}
// {{{ class k_nodes
class k_bucket;

int k_nodeinfo_cmp(const void *k1, const void *k2);

/*
 * stores a set of k_nodeinfo*.  the size of the set formally never exceeds
 * Kademlia::k, but internally we let it grow bigger.  only once every so often
 * we truncate it.  (see get())
 */
class k_nodes {
public:
  k_nodes(k_bucket *parent);
  ~k_nodes();
  void insert(Kademlia::NodeID, bool);
  void erase(Kademlia::NodeID);
  bool contains(Kademlia::NodeID);
  bool inrange(Kademlia::NodeID);
  void clear();
  void checkrep();
  unsigned size()       { return _map.size() >= (int) Kademlia::k ? Kademlia::k : _map.size(); }
  k_nodeinfo* last()    { return get(size()-1); }
  bool full() const     { return _map.size() >= (int) Kademlia::k; }
  bool empty() const    { return !_map.size(); }
  k_nodeinfo* get(unsigned);

private:

  k_bucket *_parent;
  HashMap<k_nodeinfo*, bool> _map;

  // 
  k_nodeinfo **_nodes;
  enum redo_t {
    NOTHING = 0,
    RESORT,
    REBUILD
  };
  redo_t _redo; // 0: nothing, 1: resort, 2: refill & resort

  void rebuild();
};
// }}}
// {{{ class k_bucket 
class k_traverser;
class k_bucket {
public:
  k_bucket(k_bucket*, Kademlia*);
  ~k_bucket();

  Kademlia *kademlia()  { return _kademlia; }
  void traverse(k_traverser*, Kademlia*, string = "", unsigned = 0, unsigned = 0);
  void insert(Kademlia::NodeID, bool, bool = false, string = "", unsigned = 0);
  void erase(Kademlia::NodeID, string = "", unsigned = 0);
  void find_node(Kademlia::NodeID, vector<k_nodeinfo*>*, unsigned = Kademlia::k_tell, unsigned = 0);
  void checkrep();

  void divide(unsigned);
  void collapse();

  bool leaf;

  // in case we are a leaf
  k_nodes *nodes;
  k_nodes *replacement_cache;

  // in case are a node, i.e., not a leaf
  k_bucket *child[2];

protected:
  k_bucket *parent;

private:
  Kademlia *_kademlia;

};
// }}}

// {{{ class k_traverser
class k_traverser { public:
  k_traverser(string type = "") : _type(type) {}
  virtual ~k_traverser() {}
  virtual void execute(k_bucket*, string, unsigned, unsigned) = 0;
  string type() { return _type; };

private:
  string _type;
};
// }}}
// {{{ class k_stabilizer
class k_stabilizer : public k_traverser { public:
  k_stabilizer() : k_traverser("k_stabilizer") {}
  virtual ~k_stabilizer() {}
  virtual void execute(k_bucket*, string, unsigned, unsigned);
};
// }}}
// {{{ class k_stabilized
class k_stabilized : public k_traverser { public:
  k_stabilized(vector<Kademlia::NodeID> *v) :
    k_traverser("k_stabilized"), _v(v), _stabilized(true) {}

  virtual ~k_stabilized() {}
  virtual void execute(k_bucket*, string, unsigned, unsigned);
  bool stabilized() { return _stabilized; }

private:
  vector<Kademlia::NodeID> *_v;
  bool _stabilized;
};
// }}}
// {{{ class k_finder
class k_finder : public k_traverser { public:
  k_finder(Kademlia::NodeID n) : k_traverser("k_finder"), _n(n), _found(0) {}

  virtual ~k_finder() {}
  virtual void execute(k_bucket*, string, unsigned, unsigned);
  unsigned found() { return _found; }

private:
  Kademlia::NodeID _n;
  unsigned _found;
};
// }}}
// {{{ class k_dumper
class k_dumper : public k_traverser { public:
  k_dumper() : k_traverser("k_dumper") {}
  virtual ~k_dumper() {}
  virtual void execute(k_bucket*, string, unsigned, unsigned);

private:
};
// }}}
// {{{ class k_check
class k_check : public k_traverser { public:
  k_check() : k_traverser("k_check") {}
  virtual ~k_check() {}
  virtual void execute(k_bucket*, string, unsigned, unsigned);

private:
};
// }}}

#define KDEBUG(x) if(p2psim_verbose >= (x)) cout << Kademlia::debugcounter++ << "(" << now() << ")"<<ip() << " . " << Kademlia::printID(_id) << "(" << taskid() << ") "
#endif // __KADEMLIA_H