kademlia.h

P2P模拟器

// {{{ headers
/*
 * Copyright (c) 2003-2005 Thomer M. Gil
 *                    Massachusetts Institute of Technology
 * 
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef __KADEMLIA_H
#define __KADEMLIA_H

#include "p2psim/p2protocol.h"
#include "consistenthash.h"
#include <list>
#include <iostream>
#include "p2psim/bighashmap.hh"
using namespace std;

// }}}
// {{{ class k_nodeinfo
class k_nodeinfo {
public:
  typedef ConsistentHash::CHID NodeID;
  k_nodeinfo() { id = 0; ip = 0; lastts = 0; timeouts = 0; RTT = 0;}
  k_nodeinfo(NodeID, IPAddress, Time = 0);
  k_nodeinfo(k_nodeinfo*);
  NodeID id;
  IPAddress ip;
  Time lastts;   // last time we know it was alive

  unsigned timeouts; // how often we did not get a reply
  Time RTT;

  inline void checkrep() const;
};
// }}}
// {{{ class Kademlia
class k_bucket;
class Kademlia : public P2Protocol {
public:
  typedef ConsistentHash::CHID NodeID;

private:
// class k_nodeinfo_pool {{{
  struct k_nodeinfo_buffer
  {
    k_nodeinfo_buffer() {
      ki = 0;
      next = prev = 0;
    }

    ~k_nodeinfo_buffer() {
      delete ki;
    }

    k_nodeinfo *ki;
    k_nodeinfo_buffer *next;
    k_nodeinfo_buffer *prev;
  };

  class k_nodeinfo_pool
  {
  public:
    k_nodeinfo_pool() {
      _head = _tail = New k_nodeinfo_buffer;
      _count = 0;
    }

    ~k_nodeinfo_pool() {
      k_nodeinfo_buffer *i = _head;
      while(i) {
        k_nodeinfo_buffer *next = i->next;
        delete i;
        i = next;
      }
    }

    k_nodeinfo* pop(Kademlia::NodeID id, IPAddress ip, Time RTT, char timeouts)
    {
      if(!_count)
        return New k_nodeinfo(id, ip, RTT);

      k_nodeinfo *newki = _pop();
      newki->id = id;
      newki->ip = ip;
      newki->lastts = 0;
      newki->timeouts = timeouts;
      newki->RTT = RTT;
      _count--;
      return newki;
    }

    void push(k_nodeinfo *ki)
    {
      // verify that this pointer isn't in here yet.
      if(Kademlia::docheckrep) {
        k_nodeinfo_buffer *i = _head;
        do {
          assert(i->ki != ki);
        } while(i->next == 0);
      }

      // allocate new space
      if(_tail->next == 0) {
        _tail->next = New k_nodeinfo_buffer;
        _tail->next->prev = _tail;
      }

      _tail = _tail->next;
      _tail->ki = ki;
      _count++;
      ki->ip = 0;
      ki->id = 0;
      ki->lastts = 0;
      ki->timeouts = 0;
      ki->RTT = 0;
    }

  private:
    k_nodeinfo* _pop()
    {
      _tail = _tail->prev;
      return _tail->next->ki;
    }

  private:
    unsigned _count;
    k_nodeinfo_buffer* _head;
    k_nodeinfo_buffer* _tail;
  };
// }}}
// {{{ public
public:
  Kademlia(IPAddress, Args);
  ~Kademlia();

  virtual void join(Args*);
  virtual void crash(Args*);
  virtual void lookup(Args*);
  virtual void initstate();
  virtual void nodeevent (Args *) {};

  //
  // functors
  //
  class closer { public:
    bool operator()(const k_nodeinfo p1, const k_nodeinfo p2) const {
      if(p1.id == p2.id)
        return false;
      Kademlia::NodeID dist1 = Kademlia::distance(p1.id, n);
      Kademlia::NodeID dist2 = Kademlia::distance(p2.id, n);
      if(dist1 == dist2)
        return p1.id < p2.id;
      return dist1 < dist2;
    }
    static NodeID n;
  };

  //
  // same as closer, but takes RTT into account
  //
  class closerRTT { public:
    bool operator()(const k_nodeinfo p1, const k_nodeinfo p2) const {
      if(p1.id == p2.id)
        return false;
      unsigned cp1 = Kademlia::common_prefix(p1.id, n);
      unsigned cp2 = Kademlia::common_prefix(p2.id, n);
      if(cp1 == cp2) {
        if(p1.RTT == p2.RTT) {
          return p1.id < p2.id;

        // prefer non-zero over zero
        } else if(p1.RTT == 0 && p2.RTT != 0) {
          return false;
        } else if(p1.RTT != 0 && p2.RTT == 0) {
          return true;
        } else {
          return p1.RTT < p2.RTT;
        }
      }
      return cp1 > cp2;
    }
    static NodeID n;
  };


  //
  // static utility methods
  //
  static string printbits(NodeID);
  static string printID(NodeID id);
  static NodeID distance(const NodeID, const NodeID);
  static unsigned common_prefix(NodeID, NodeID);
  static unsigned getbit(NodeID, unsigned);
  static void reap(void*);

  //
  // observer methods
  //
  NodeID id() const { return _id; }
  k_bucket *root() { return _root; }
  bool stabilized(vector<NodeID>*);

  // statistics
  enum stat_type {
    STAT_LOOKUP = 0,
    STAT_STABILIZE,
    STAT_JOIN,
    STAT_PING,
    STAT_ERASE
  };

  //
  // RPC arguments
  // 
  // {{{ find_value_args and find_value_args
  struct find_value_args {
    find_value_args(NodeID xid, IPAddress xip, NodeID k = 0) :
      id(xid), ip(xip), key(k), stattype(STAT_LOOKUP) {}
    NodeID id;
    IPAddress ip;
    NodeID key;
    stat_type stattype; // for stats
  };

  class find_value_result { public:
    find_value_result() { rpcs = hops = timeouts = 0; latency = 0; }
    ~find_value_result() { }
    k_nodeinfo succ;
    NodeID rid;
    
    // statistics
    unsigned rpcs;      // total number of RPCs we sent
    unsigned hops;      // number of hops for lookups
    unsigned timeouts;  // number of !ok replies
    Time latency;       // latency from nodes that make hopcount go up
  };
  // }}}
  // {{{ find_node_args and find_node_result
  struct find_node_args {
    find_node_args(NodeID xid, IPAddress xip, NodeID k) :
      id(xid), ip(xip), key(k), stattype(STAT_LOOKUP) {}
    NodeID id;
    IPAddress ip;
    NodeID key;
    stat_type stattype;
  };

  class find_node_result { public:
    find_node_result() {}
    vector<k_nodeinfo> results;
    unsigned hops;
    unsigned which_alpha;
    NodeID rid;
  };
  // }}}
  // {{{ lookup_args and lookup_result
  struct lookup_args {
    lookup_args(NodeID xid, IPAddress xip, NodeID k = 0, bool ri = false) :
      id(xid), ip(xip), key(k), stattype(STAT_LOOKUP) {}
    NodeID id;
    IPAddress ip;
    NodeID key;
    stat_type stattype;
  };

  class lookup_result { public:
    lookup_result() { results.clear(); hops = 0; }
    ~lookup_result() { }
    set<k_nodeinfo, closer> results;
    NodeID rid;     // the guy who's replying
    unsigned hops;
  };

  struct lookup_wrapper_args {
    IPAddress ipkey;
    NodeID key;
    Time starttime;
    unsigned attempts;
  };
  // }}}
  // {{{ ping_args and ping_result
  struct ping_args {
    ping_args(NodeID id, IPAddress ip) : id(id), ip(ip) {}
    NodeID id;
    IPAddress ip;
  };