Fabcoin Core  0.16.2
P2P Digital Currency
Classes | Public Types | Public Member Functions | Static Public Member Functions | Private Types | Private Member Functions | Private Attributes | Static Private Attributes | Friends | List of all members
dev::p2p::NodeTable Class Reference

NodeTable using modified kademlia for node discovery and preference. More...

#include <NodeTable.h>

Inheritance diagram for dev::p2p::NodeTable:
[legend]
Collaboration diagram for dev::p2p::NodeTable:
[legend]

Classes

struct  NodeBucket
 

Public Types

enum  NodeRelation { Unknown = 0, Known }
 
enum  DiscoverType { Random = 0 }
 

Public Member Functions

 NodeTable (ba::io_service &_io, KeyPair const &_alias, NodeIPEndpoint const &_endpoint, bool _enabled=true)
 Constructor requiring host for I/O, credentials, and IP Address and port to listen on. More...
 
 ~NodeTable ()
 
void setEventHandler (NodeTableEventHandler *_handler)
 Set event handler for NodeEntryAdded and NodeEntryDropped events. More...
 
void processEvents ()
 Called by implementation which provided handler to process NodeEntryAdded/NodeEntryDropped events. Events are coalesced by type whereby old events are ignored. More...
 
std::shared_ptr< NodeEntryaddNode (Node const &_node, NodeRelation _relation=NodeRelation::Unknown)
 Add node. Node will be pinged and empty shared_ptr is returned if node has never been seen or NodeID is empty. More...
 
std::list< NodeIDnodes () const
 Returns list of node ids active in node table. More...
 
unsigned count () const
 Returns node count. More...
 
std::list< NodeEntrysnapshot () const
 Returns snapshot of table. More...
 
bool haveNode (NodeID const &_id)
 Returns true if node id is in node table. More...
 
Node node (NodeID const &_id)
 Returns the Node to the corresponding node id or the empty Node if that id is not found. More...
 

Static Public Member Functions

static unsigned distance (NodeID const &_a, NodeID const &_b)
 Returns distance based on xor metric two node ids. Used by NodeEntry and NodeTable. More...
 

Private Types

using NodeSocket = UDPSocket< NodeTable, 1280 >
 
using TimePoint = std::chrono::steady_clock::time_point
 Steady time point. More...
 
using NodeIdTimePoint = std::pair< NodeID, TimePoint >
 
using EvictionTimeout = std::pair< NodeIdTimePoint, NodeID >
 First NodeID (NodeIdTimePoint) may be evicted and replaced with second NodeID. More...
 

Private Member Functions

void ping (NodeIPEndpoint _to) const
 Used to ping endpoint. More...
 
void ping (NodeEntry *_n) const
 Used ping known node. Used by node table when refreshing buckets and as part of eviction process (see evict). More...
 
NodeEntry center () const
 Returns center node entry which describes this node and used with dist() to calculate xor metric for node table nodes. More...
 
std::shared_ptr< NodeEntrynodeEntry (NodeID _id)
 Used by asynchronous operations to return NodeEntry which is active and managed by node table. More...
 
void doDiscover (NodeID _target, unsigned _round=0, std::shared_ptr< std::set< std::shared_ptr< NodeEntry >>> _tried=std::shared_ptr< std::set< std::shared_ptr< NodeEntry >>>())
 Used to discovery nodes on network which are close to the given target. More...
 
std::vector< std::shared_ptr< NodeEntry > > nearestNodeEntries (NodeID _target)
 Returns nodes from node table which are closest to target. More...
 
void evict (std::shared_ptr< NodeEntry > _leastSeen, std::shared_ptr< NodeEntry > _new)
 Asynchronously drops _leastSeen node if it doesn't reply and adds _new node, otherwise _new node is thrown away. More...
 
void noteActiveNode (Public const &_pubk, bi::udp::endpoint const &_endpoint)
 Called whenever activity is received from a node in order to maintain node table. More...
 
void dropNode (std::shared_ptr< NodeEntry > _n)
 Used to drop node when timeout occurs or when evict() result is to keep previous node. More...
 
NodeBucketbucket_UNSAFE (NodeEntry const *_n)
 Returns references to bucket which corresponds to distance of node id. More...
 
void onReceived (UDPSocketFace *, bi::udp::endpoint const &_from, bytesConstRef _packet)
 General Network Events. More...
 
void onDisconnected (UDPSocketFace *)
 Called by m_socket when socket is disconnected. More...
 
void doCheckEvictions ()
 Tasks. More...
 
void doDiscovery ()
 Looks up a random node at interval. More...
 

Private Attributes

std::chrono::milliseconds const c_evictionCheckInterval = std::chrono::milliseconds(75)
 Intervals. More...
 
std::chrono::milliseconds const c_reqTimeout = std::chrono::milliseconds(300)
 How long to wait for requests (evict, find iterations). More...
 
std::chrono::milliseconds const c_bucketRefresh = std::chrono::milliseconds(7200)
 Refresh interval prevents bucket from becoming stale. [Kademlia]. More...
 
std::unique_ptr< NodeTableEventHandlerm_nodeEventHandler
 Event handler for node events. More...
 
Node m_node
 This node. LOCK x_state if endpoint access or mutation is required. Do not modify id. More...
 
Secret m_secret
 This nodes secret key. More...
 
Mutex x_nodes
 LOCK x_state first if both locks are required. Mutable for thread-safe copy in nodes() const. More...
 
std::unordered_map< NodeID, std::shared_ptr< NodeEntry > > m_nodes
 Known Node Endpoints. More...
 
Mutex x_state
 LOCK x_state first if both x_nodes and x_state locks are required. More...
 
std::array< NodeBucket, s_binsm_state
 State of p2p node network. More...
 
Mutex x_evictions
 LOCK x_evictions first if both x_nodes and x_evictions locks are required. More...
 
std::deque< EvictionTimeoutm_evictions
 Eviction timeouts. More...
 
Mutex x_pubkDiscoverPings
 LOCK x_nodes first if both x_nodes and x_pubkDiscoverPings locks are required. More...
 
std::unordered_map< bi::address, TimePointm_pubkDiscoverPings
 List of pending pings where node entry wasn't created due to unkown pubk. More...
 
Mutex x_findNodeTimeout
 
std::list< NodeIdTimePointm_findNodeTimeout
 Timeouts for pending Ping and FindNode requests. More...
 
std::shared_ptr< NodeSocketm_socket
 Shared pointer for our UDPSocket; ASIO requires shared_ptr. More...
 
NodeSocketm_socketPointer
 Set to m_socket.get(). Socket is created in constructor and disconnected in destructor to ensure access to pointer is safe. More...
 
DeadlineOps m_timers
 this should be the last member - it must be destroyed first More...
 

Static Private Attributes

static unsigned const s_addressByteSize = h256::size
 Constants for Kademlia, derived from address space. More...
 
static unsigned const s_bits = 8 * s_addressByteSize
 Denoted by n in [Kademlia]. More...
 
static unsigned const s_bins = s_bits - 1
 Size of m_state (excludes root, which is us). More...
 
static unsigned const s_maxSteps = boost::static_log2<s_bits>::value
 Max iterations of discovery. (discover) More...
 
static unsigned const s_bucketSize = 16
 Chosen constants. More...
 
static unsigned const s_alpha = 3
 Denoted by in [Kademlia]. Number of concurrent FindNode requests. More...
 

Friends

std::ostream & operator<< (std::ostream &_out, NodeTable const &_nodeTable)
 

Detailed Description

NodeTable using modified kademlia for node discovery and preference.

Node table requires an IO service, creates a socket for incoming UDP messages and implements a kademlia-like protocol. Node requests and responses are used to build a node table which can be queried to obtain a list of potential nodes to connect to, and, passes events to Host whenever a node is added or removed to/from the table.

Thread-safety is ensured by modifying NodeEntry details via shared_ptr replacement instead of mutating values.

NodeTable accepts a port for UDP and will listen to the port on all available interfaces.

[Optimization]

Todo:

serialize evictions per-bucket

store evictions in map, unit-test eviction logic

store root node in table

encapsulate discover into NetworkAlgorithm (task)

expiration and sha3(id) 'to' for messages which are replies (prevents replay)

cache Ping and FindSelf

firewall

^ s_bitsPerStep = 8; // Denoted by b in [Kademlia]. Bits by which address space is divided.

[Networking]

Todo:
eth/upnp/natpmp/stun/ice/etc for public-discovery

[Protocol]

Todo:
optimize knowledge at opposite edges; eg, s_bitsPerStep lookups. (Can be done via pointers to NodeBucket)

Definition at line 121 of file NodeTable.h.

Member Typedef Documentation

First NodeID (NodeIdTimePoint) may be evicted and replaced with second NodeID.

Definition at line 127 of file NodeTable.h.

Definition at line 126 of file NodeTable.h.

Definition at line 124 of file NodeTable.h.

using dev::p2p::NodeTable::TimePoint = std::chrono::steady_clock::time_point
private

Steady time point.

Definition at line 125 of file NodeTable.h.

Member Enumeration Documentation

Enumerator
Random 

Definition at line 131 of file NodeTable.h.

Enumerator
Unknown 
Known 

Definition at line 130 of file NodeTable.h.

Constructor & Destructor Documentation

NodeTable::NodeTable ( ba::io_service &  _io,
KeyPair const &  _alias,
NodeIPEndpoint const &  _endpoint,
bool  _enabled = true 
)

Constructor requiring host for I/O, credentials, and IP Address and port to listen on.

Definition at line 43 of file NodeTable.cpp.

Here is the call graph for this function:

NodeTable::~NodeTable ( )

Definition at line 68 of file NodeTable.cpp.

Here is the call graph for this function:

Member Function Documentation

shared_ptr< NodeEntry > NodeTable::addNode ( Node const &  _node,
NodeRelation  _relation = NodeRelation::Unknown 
)

Add node. Node will be pinged and empty shared_ptr is returned if node has never been seen or NodeID is empty.

Definition at line 80 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

NodeTable::NodeBucket & NodeTable::bucket_UNSAFE ( NodeEntry const *  _n)
private

Returns references to bucket which corresponds to distance of node id.

Warning
Only use the return reference locked x_state mutex.

Definition at line 392 of file NodeTable.cpp.

Here is the caller graph for this function:

NodeEntry dev::p2p::NodeTable::center ( ) const
inlineprivate

Returns center node entry which describes this node and used with dist() to calculate xor metric for node table nodes.

Definition at line 202 of file NodeTable.h.

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned dev::p2p::NodeTable::count ( ) const
inline

Returns node count.

Definition at line 153 of file NodeTable.h.

Here is the caller graph for this function:

static unsigned dev::p2p::NodeTable::distance ( NodeID const &  _a,
NodeID const &  _b 
)
inlinestatic

Returns distance based on xor metric two node ids. Used by NodeEntry and NodeTable.

Definition at line 138 of file NodeTable.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void NodeTable::doCheckEvictions ( )
private

Tasks.

Called by evict() to ensure eviction check is scheduled to run and terminates when no evictions remain. Asynchronous.

Definition at line 531 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void NodeTable::doDiscover ( NodeID  _target,
unsigned  _round = 0,
std::shared_ptr< std::set< std::shared_ptr< NodeEntry >>>  _tried = std::shared_ptr<std::set<std::shared_ptr<NodeEntry>>>() 
)
private

Used to discovery nodes on network which are close to the given target.

Sends s_alpha concurrent requests to nodes nearest to target, for nodes nearest to target, up to s_maxSteps rounds.

Definition at line 155 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void NodeTable::doDiscovery ( )
private

Looks up a random node at interval.

Definition at line 562 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void NodeTable::dropNode ( std::shared_ptr< NodeEntry _n)
private

Used to drop node when timeout occurs or when evict() result is to keep previous node.

Definition at line 377 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void NodeTable::evict ( std::shared_ptr< NodeEntry _leastSeen,
std::shared_ptr< NodeEntry _new 
)
private

Asynchronously drops _leastSeen node if it doesn't reply and adds _new node, otherwise _new node is thrown away.

Definition at line 308 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool dev::p2p::NodeTable::haveNode ( NodeID const &  _id)
inline

Returns true if node id is in node table.

Definition at line 159 of file NodeTable.h.

Here is the caller graph for this function:

vector< shared_ptr< NodeEntry > > NodeTable::nearestNodeEntries ( NodeID  _target)
private

Returns nodes from node table which are closest to target.

Definition at line 217 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Node NodeTable::node ( NodeID const &  _id)

Returns the Node to the corresponding node id or the empty Node if that id is not found.

Definition at line 138 of file NodeTable.cpp.

Here is the caller graph for this function:

shared_ptr< NodeEntry > NodeTable::nodeEntry ( NodeID  _id)
private

Used by asynchronous operations to return NodeEntry which is active and managed by node table.

Definition at line 149 of file NodeTable.cpp.

Here is the caller graph for this function:

list< NodeID > NodeTable::nodes ( ) const

Returns list of node ids active in node table.

Definition at line 118 of file NodeTable.cpp.

Here is the caller graph for this function:

void NodeTable::noteActiveNode ( Public const &  _pubk,
bi::udp::endpoint const &  _endpoint 
)
private

Called whenever activity is received from a node in order to maintain node table.

Definition at line 325 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void dev::p2p::NodeTable::onDisconnected ( UDPSocketFace )
inlineprivatevirtual

Called by m_socket when socket is disconnected.

Reimplemented from dev::p2p::UDPSocketEvents.

Definition at line 234 of file NodeTable.h.

void NodeTable::onReceived ( UDPSocketFace ,
bi::udp::endpoint const &  _from,
bytesConstRef  _packet 
)
privatevirtual

General Network Events.

Called by m_socket when packet is received.

Implements dev::p2p::UDPSocketEvents.

Definition at line 397 of file NodeTable.cpp.

Here is the call graph for this function:

void NodeTable::ping ( NodeIPEndpoint  _to) const
private

Used to ping endpoint.

Definition at line 292 of file NodeTable.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void NodeTable::ping ( NodeEntry _n) const
private

Used ping known node. Used by node table when refreshing buckets and as part of eviction process (see evict).

Definition at line 302 of file NodeTable.cpp.

Here is the call graph for this function:

void NodeTable::processEvents ( )

Called by implementation which provided handler to process NodeEntryAdded/NodeEntryDropped events. Events are coalesced by type whereby old events are ignored.

Definition at line 74 of file NodeTable.cpp.

void dev::p2p::NodeTable::setEventHandler ( NodeTableEventHandler _handler)
inline

Set event handler for NodeEntryAdded and NodeEntryDropped events.

Definition at line 141 of file NodeTable.h.

list< NodeEntry > NodeTable::snapshot ( ) const

Returns snapshot of table.

Definition at line 127 of file NodeTable.cpp.

Here is the caller graph for this function:

Friends And Related Function Documentation

std::ostream& operator<< ( std::ostream &  _out,
NodeTable const &  _nodeTable 
)
friend

Definition at line 270 of file NodeTable.h.

Member Data Documentation

std::chrono::milliseconds const dev::p2p::NodeTable::c_bucketRefresh = std::chrono::milliseconds(7200)
private

Refresh interval prevents bucket from becoming stale. [Kademlia].

Definition at line 187 of file NodeTable.h.

std::chrono::milliseconds const dev::p2p::NodeTable::c_evictionCheckInterval = std::chrono::milliseconds(75)
private

Intervals.

Interval at which eviction timeouts are checked.

Definition at line 185 of file NodeTable.h.

std::chrono::milliseconds const dev::p2p::NodeTable::c_reqTimeout = std::chrono::milliseconds(300)
private

How long to wait for requests (evict, find iterations).

Definition at line 186 of file NodeTable.h.

std::deque<EvictionTimeout> dev::p2p::NodeTable::m_evictions
private

Eviction timeouts.

Definition at line 256 of file NodeTable.h.

std::list<NodeIdTimePoint> dev::p2p::NodeTable::m_findNodeTimeout
private

Timeouts for pending Ping and FindNode requests.

Definition at line 262 of file NodeTable.h.

Node dev::p2p::NodeTable::m_node
private

This node. LOCK x_state if endpoint access or mutation is required. Do not modify id.

Definition at line 246 of file NodeTable.h.

std::unique_ptr<NodeTableEventHandler> dev::p2p::NodeTable::m_nodeEventHandler
private

Event handler for node events.

Definition at line 244 of file NodeTable.h.

std::unordered_map<NodeID, std::shared_ptr<NodeEntry> > dev::p2p::NodeTable::m_nodes
private

Known Node Endpoints.

Definition at line 250 of file NodeTable.h.

std::unordered_map<bi::address, TimePoint> dev::p2p::NodeTable::m_pubkDiscoverPings
private

List of pending pings where node entry wasn't created due to unkown pubk.

Definition at line 259 of file NodeTable.h.

Secret dev::p2p::NodeTable::m_secret
private

This nodes secret key.

Definition at line 247 of file NodeTable.h.

std::shared_ptr<NodeSocket> dev::p2p::NodeTable::m_socket
private

Shared pointer for our UDPSocket; ASIO requires shared_ptr.

Definition at line 264 of file NodeTable.h.

NodeSocket* dev::p2p::NodeTable::m_socketPointer
private

Set to m_socket.get(). Socket is created in constructor and disconnected in destructor to ensure access to pointer is safe.

Definition at line 265 of file NodeTable.h.

std::array<NodeBucket, s_bins> dev::p2p::NodeTable::m_state
private

State of p2p node network.

Definition at line 253 of file NodeTable.h.

DeadlineOps dev::p2p::NodeTable::m_timers
private

this should be the last member - it must be destroyed first

Definition at line 267 of file NodeTable.h.

unsigned const dev::p2p::NodeTable::s_addressByteSize = h256::size
staticprivate

Constants for Kademlia, derived from address space.

Size of address type in bytes.

Definition at line 172 of file NodeTable.h.

unsigned const dev::p2p::NodeTable::s_alpha = 3
staticprivate

Denoted by in [Kademlia]. Number of concurrent FindNode requests.

Definition at line 180 of file NodeTable.h.

unsigned const dev::p2p::NodeTable::s_bins = s_bits - 1
staticprivate

Size of m_state (excludes root, which is us).

Definition at line 174 of file NodeTable.h.

unsigned const dev::p2p::NodeTable::s_bits = 8 * s_addressByteSize
staticprivate

Denoted by n in [Kademlia].

Definition at line 173 of file NodeTable.h.

unsigned const dev::p2p::NodeTable::s_bucketSize = 16
staticprivate

Chosen constants.

Denoted by k in [Kademlia]. Number of nodes stored in each bucket.

Definition at line 179 of file NodeTable.h.

unsigned const dev::p2p::NodeTable::s_maxSteps = boost::static_log2<s_bits>::value
staticprivate

Max iterations of discovery. (discover)

Definition at line 175 of file NodeTable.h.

Mutex dev::p2p::NodeTable::x_evictions
private

LOCK x_evictions first if both x_nodes and x_evictions locks are required.

Definition at line 255 of file NodeTable.h.

Mutex dev::p2p::NodeTable::x_findNodeTimeout
private

Definition at line 261 of file NodeTable.h.

Mutex dev::p2p::NodeTable::x_nodes
mutableprivate

LOCK x_state first if both locks are required. Mutable for thread-safe copy in nodes() const.

Definition at line 249 of file NodeTable.h.

Mutex dev::p2p::NodeTable::x_pubkDiscoverPings
private

LOCK x_nodes first if both x_nodes and x_pubkDiscoverPings locks are required.

Definition at line 258 of file NodeTable.h.

Mutex dev::p2p::NodeTable::x_state
mutableprivate

LOCK x_state first if both x_nodes and x_state locks are required.

Definition at line 252 of file NodeTable.h.


The documentation for this class was generated from the following files: