Work in progress: Path canonicalization refactor.

6 files changed, 120 insertions, 171 deletions

diff --git a/node/Constants.hpp b/node/Constants.hpp
index b9308abd..8a596fb3 100644
--- a/node/Constants.hpp
+++ b/node/Constants.hpp
@@ -270,11 +270,6 @@
 #define ZT_PEER_ACTIVITY_TIMEOUT 500000
 
 /**
- * Timeout for path activity
- */
-#define ZT_PATH_ACTIVITY_TIMEOUT ZT_PEER_ACTIVITY_TIMEOUT
-
-/**
  * No answer timeout to trigger dead path detection
  */
 #define ZT_PEER_DEAD_PATH_DETECTION_NO_ANSWER_TIMEOUT 2000
diff --git a/node/IncomingPacket.hpp b/node/IncomingPacket.hpp
index 303ac5f8..35438f4f 100644
--- a/node/IncomingPacket.hpp
+++ b/node/IncomingPacket.hpp
@@ -22,7 +22,7 @@
 #include <stdexcept>
 
 #include "Packet.hpp"
-#include "InetAddress.hpp"
+#include "Path.hpp"
 #include "Utils.hpp"
 #include "MulticastGroup.hpp"
 #include "Peer.hpp"
@@ -56,41 +56,24 @@ class IncomingPacket : public Packet
 public:
 	IncomingPacket() :
 		Packet(),
-		_receiveTime(0),
-		_localAddress(),
-		_remoteAddress()
+		_receiveTime(0)
 	{
 	}
 
-	IncomingPacket(const IncomingPacket &p)
-	{
-		// All fields including InetAddress are memcpy'able
-		memcpy(this,&p,sizeof(IncomingPacket));
-	}
-
 	/**
 	 * Create a new packet-in-decode
 	 *
 	 * @param data Packet data
 	 * @param len Packet length
-	 * @param localAddress Local interface address
-	 * @param remoteAddress Address from which packet came
+	 * @param path Path over which packet arrived
 	 * @param now Current time
 	 * @throws std::out_of_range Range error processing packet
 	 */
-	IncomingPacket(const void *data,unsigned int len,const InetAddress &localAddress,const InetAddress &remoteAddress,uint64_t now) :
+	IncomingPacket(const void *data,unsigned int len,const SharedPtr<Path> &path,uint64_t now) :
 		Packet(data,len),
 		_receiveTime(now),
-		_localAddress(localAddress),
-		_remoteAddress(remoteAddress)
-	{
-	}
-
-	inline IncomingPacket &operator=(const IncomingPacket &p)
+		_path(path)
 	{
-		// All fields including InetAddress are memcpy'able
-		memcpy(this,&p,sizeof(IncomingPacket));
-		return *this;
 	}
 
 	/**
@@ -98,17 +81,15 @@ public:
 	 *
 	 * @param data Packet data
 	 * @param len Packet length
-	 * @param localAddress Local interface address
-	 * @param remoteAddress Address from which packet came
+	 * @param path Path over which packet arrived
 	 * @param now Current time
 	 * @throws std::out_of_range Range error processing packet
 	 */
-	inline void init(const void *data,unsigned int len,const InetAddress &localAddress,const InetAddress &remoteAddress,uint64_t now)
+	inline void init(const void *data,unsigned int len,const SharedPtr<Path> &path,uint64_t now)
 	{
 		copyFrom(data,len);
 		_receiveTime = now;
-		_localAddress = localAddress;
-		_remoteAddress = remoteAddress;
+		_path = path;
 	}
 
 	/**
@@ -174,8 +155,7 @@ private:
 	bool _doREQUEST_PROOF_OF_WORK(const RuntimeEnvironment *RR,const SharedPtr<Peer> &peer);
 
 	uint64_t _receiveTime;
-	InetAddress _localAddress;
-	InetAddress _remoteAddress;
+	SharedPtr<Path> _path;
 };
 
 } // namespace ZeroTier
diff --git a/node/Path.cpp b/node/Path.cpp
index 5692af66..5592bacc 100644
--- a/node/Path.cpp
+++ b/node/Path.cpp
@@ -25,7 +25,7 @@ namespace ZeroTier {
 bool Path::send(const RuntimeEnvironment *RR,const void *data,unsigned int len,uint64_t now)
 {
 	if (RR->node->putPacket(_localAddress,address(),data,len)) {
-		sent(now);
+		_lastOut = now;
 		return true;
 	}
 	return false;
diff --git a/node/Path.hpp b/node/Path.hpp
index ca5dd98f..f8d84d4b 100644
--- a/node/Path.hpp
+++ b/node/Path.hpp
@@ -27,27 +27,8 @@
 
 #include "Constants.hpp"
 #include "InetAddress.hpp"
-
-// Note: if you change these flags check the logic below. Some of it depends
-// on these bits being what they are.
-
-/**
- * Flag indicating that this path is suboptimal
- *
- * Clusters set this flag on remote paths if GeoIP or other routing decisions
- * indicate that a peer should be handed off to another cluster member.
- */
-#define ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL 0x0001
-
-/**
- * Flag indicating that this path is optimal
- *
- * Peers set this flag on paths that are pushed by a cluster and indicated as
- * optimal. A second flag is needed since we want to prioritize cluster optimal
- * paths and de-prioritize sub-optimal paths and for new paths we don't know
- * which one they are. So we want a trinary state: optimal, suboptimal, unknown.
- */
-#define ZT_PATH_FLAG_CLUSTER_OPTIMAL 0x0002
+#include "SharedPtr.hpp"
+#include "AtomicCounter.hpp"
 
 /**
  * Maximum return value of preferenceRank()
@@ -59,34 +40,83 @@ namespace ZeroTier {
 class RuntimeEnvironment;
 
 /**
- * Base class for paths
- *
- * The base Path class is an immutable value.
+ * A path across the physical network
  */
 class Path
 {
+	friend class SharedPtr<Path>;
+
 public:
+	/**
+	 * Efficient unique key for paths in a Hashtable
+	 */
+	class HashKey
+	{
+	public:
+		HashKey() {}
+
+		HashKey(const InetAddress &l,const InetAddress &r)
+		{
+			// This is an ad-hoc bit packing algorithm to yield unique keys for
+			// remote addresses and their local-side counterparts if defined.
+			// Portability across runtimes is not needed.
+			if (r.ss_family == AF_INET) {
+				_k[0] = (uint64_t)reinterpret_cast<const struct sockaddr_in *>(&r)->sin_addr.s_addr;
+				_k[1] = (uint64_t)reinterpret_cast<const struct sockaddr_in *>(&r)->sin_port;
+				if (l.ss_family == AF_INET) {
+					_k[2] = (uint64_t)reinterpret_cast<const struct sockaddr_in *>(&l)->sin_addr.s_addr;
+					_k[3] = (uint64_t)reinterpret_cast<const struct sockaddr_in *>(&r)->sin_port;
+				} else {
+					_k[2] = 0;
+					_k[3] = 0;
+				}
+			} else if (r.ss_family == AF_INET6) {
+				const uint8_t *a = reinterpret_cast<const uint8_t *>(reinterpret_cast<const struct sockaddr_in6 *>(&r)->sin6_addr.s6_addr);
+				uint8_t *b = reinterpret_cast<uint8_t *>(_k);
+				for(unsigned int i=0;i<16;++i) b[i] = a[i];
+				_k[2] = ~((uint64_t)reinterpret_cast<const struct sockaddr_in6 *>(&r)->sin6_port);
+				if (l.ss_family == AF_INET6) {
+					_k[2] ^= ((uint64_t)reinterpret_cast<const struct sockaddr_in6 *>(&r)->sin6_port) << 32;
+					a = reinterpret_cast<const uint8_t *>(reinterpret_cast<const struct sockaddr_in6 *>(&l)->sin6_addr.s6_addr);
+					b += 24;
+					for(unsigned int i=0;i<8;++i) b[i] = a[i];
+					a += 8;
+					for(unsigned int i=0;i<8;++i) b[i] ^= a[i];
+				}
+			} else {
+				_k[0] = 0;
+				_k[1] = 0;
+				_k[2] = 0;
+				_k[3] = 0;
+			}
+		}
+
+		inline unsigned long hashCode() const { return (unsigned long)(_k[0] + _k[1] + _k[2] + _k[3]); }
+
+		inline bool operator==(const HashKey &k) const { return ( (_k[0] == k._k[0]) && (_k[1] == k._k[1]) && (_k[2] == k._k[2]) && (_k[3] == k._k[3]) ); }
+		inline bool operator!=(const HashKey &k) const { return (!(*this == k)); }
+
+	private:
+		uint64_t _k[4];
+	};
+
 	Path() :
-		_lastSend(0),
-		_lastPing(0),
-		_lastKeepalive(0),
-		_lastReceived(0),
+		_lastOut(0),
+		_lastIn(0),
 		_addr(),
 		_localAddress(),
-		_flags(0),
-		_ipScope(InetAddress::IP_SCOPE_NONE)
+		_ipScope(InetAddress::IP_SCOPE_NONE),
+		_clusterSuboptimal(false)
 	{
 	}
 
 	Path(const InetAddress &localAddress,const InetAddress &addr) :
-		_lastSend(0),
-		_lastPing(0),
-		_lastKeepalive(0),
-		_lastReceived(0),
+		_lastOut(0),
+		_lastIn(0),
 		_addr(addr),
 		_localAddress(localAddress),
-		_flags(0),
-		_ipScope(addr.ipScope())
+		_ipScope(addr.ipScope()),
+		_clusterSuboptimal(false)
 	{
 	}
 
@@ -104,44 +134,17 @@ public:
 	 *
 	 * @param t Time of send
 	 */
-	inline void sent(uint64_t t) { _lastSend = t; }
-
-	/**
-	 * Called when we've sent a ping or echo
-	 *
-	 * @param t Time of send
-	 */
-	inline void pinged(uint64_t t) { _lastPing = t; }
+	inline void sent(const uint64_t t) { _lastOut = t; }
 
 	/**
-	 * Called when we send a NAT keepalive
-	 *
-	 * @param t Time of send
-	 */
-	inline void sentKeepalive(uint64_t t) { _lastKeepalive = t; }
-
-	/**
-	 * Called when a packet is received from this remote path
+	 * Called when a packet is received from this remote path, regardless of content
 	 *
 	 * @param t Time of receive
 	 */
-	inline void received(uint64_t t)
-	{
-		_lastReceived = t;
-		_probation = 0;
-	}
+	inline void received(const uint64_t t) { _lastIn = t; }
 
 	/**
-	 * @param now Current time
-	 * @return True if this path appears active
-	 */
-	inline bool active(uint64_t now) const
-	{
-		return ( ((now - _lastReceived) < ZT_PATH_ACTIVITY_TIMEOUT) && (_probation < ZT_PEER_DEAD_PATH_DETECTION_MAX_PROBATION) );
-	}
-
-	/**
-	 * Send a packet via this path
+	 * Send a packet via this path (last out time is also updated)
 	 *
 	 * @param RR Runtime environment
 	 * @param data Packet data
@@ -157,26 +160,6 @@ public:
 	inline const InetAddress &localAddress() const throw() { return _localAddress; }
 
 	/**
-	 * @return Time of last send to this path
-	 */
-	inline uint64_t lastSend() const throw() { return _lastSend; }
-
-	/**
-	 * @return Time we last pinged or dead path checked this link
-	 */
-	inline uint64_t lastPing() const throw() { return _lastPing; }
-
-	/**
-	 * @return Time of last keepalive
-	 */
-	inline uint64_t lastKeepalive() const throw() { return _lastKeepalive; }
-
-	/**
-	 * @return Time of last receive from this path
-	 */
-	inline uint64_t lastReceived() const throw() { return _lastReceived; }
-
-	/**
 	 * @return Physical address
 	 */
 	inline const InetAddress &address() const throw() { return _addr; }
@@ -187,26 +170,19 @@ public:
 	inline InetAddress::IpScope ipScope() const throw() { return _ipScope; }
 
 	/**
-	 * @param f Valuve of ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL and inverse of ZT_PATH_FLAG_CLUSTER_OPTIMAL (both are changed)
+	 * @param f Is this path cluster-suboptimal?
 	 */
-	inline void setClusterSuboptimal(bool f)
-	{
-		if (f) {
-			_flags = (_flags | ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL) & ~ZT_PATH_FLAG_CLUSTER_OPTIMAL;
-		} else {
-			_flags = (_flags | ZT_PATH_FLAG_CLUSTER_OPTIMAL) & ~ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL;
-		}
-	}
+	inline void setClusterSuboptimal(const bool f) { _clusterSuboptimal = f; }
 
 	/**
-	 * @return True if ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL is set
+	 * @return True if cluster-suboptimal (for someone)
 	 */
-	inline bool isClusterSuboptimal() const { return ((_flags & ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL) != 0); }
+	inline bool isClusterSuboptimal() const { return _clusterSuboptimal; }
 
 	/**
-	 * @return True if ZT_PATH_FLAG_CLUSTER_OPTIMAL is set
+	 * @return True if cluster-optimal (for someone) (the default)
 	 */
-	inline bool isClusterOptimal() const { return ((_flags & ZT_PATH_FLAG_CLUSTER_OPTIMAL) != 0); }
+	inline bool isClusterOptimal() const { return (!(_clusterSuboptimal)); }
 
 	/**
 	 * @return Preference rank, higher == better (will be less than 255)
@@ -230,29 +206,18 @@ public:
 		// This is a little bit convoluted because we try to be branch-free, using multiplication instead of branches for boolean flags
 
 		// Start with the last time this path was active, and add a fudge factor to prevent integer underflow if _lastReceived is 0
-		uint64_t score = _lastReceived + (ZT_PEER_DIRECT_PING_DELAY * (ZT_PEER_DEAD_PATH_DETECTION_MAX_PROBATION + 1));
+		uint64_t score = _lastIn + (ZT_PEER_DIRECT_PING_DELAY * (ZT_PEER_DEAD_PATH_DETECTION_MAX_PROBATION + 1));
 
 		// Increase score based on path preference rank, which is based on IP scope and address family
 		score += preferenceRank() * (ZT_PEER_DIRECT_PING_DELAY / ZT_PATH_MAX_PREFERENCE_RANK);
 
-		// Increase score if this is known to be an optimal path to a cluster
-		score += (uint64_t)(_flags & ZT_PATH_FLAG_CLUSTER_OPTIMAL) * (ZT_PEER_DIRECT_PING_DELAY / 2); // /2 because CLUSTER_OPTIMAL is flag 0x0002
-
 		// Decrease score if this is known to be a sub-optimal path to a cluster
-		score -= (uint64_t)(_flags & ZT_PATH_FLAG_CLUSTER_SUBOPTIMAL) * ZT_PEER_DIRECT_PING_DELAY;
-
-		// Penalize for missed ECHO tests in dead path detection
-		score -= (uint64_t)((ZT_PEER_DIRECT_PING_DELAY / 2) * _probation);
+		score -= ((uint64_t)_clusterSuboptimal) * ZT_PEER_DIRECT_PING_DELAY;
 
 		return score;
 	}
 
 	/**
-	 * @return True if address is non-NULL
-	 */
-	inline operator bool() const throw() { return (_addr); }
-
-	/**
 	 * Check whether this address is valid for a ZeroTier path
 	 *
 	 * This checks the address type and scope against address types and scopes
@@ -293,29 +258,14 @@ public:
 		return false;
 	}
 
-	/**
-	 * @return Current path probation count (for dead path detect)
-	 */
-	inline unsigned int probation() const { return _probation; }
-
-	/**
-	 * Increase this path's probation violation count (for dead path detect)
-	 */
-	inline void increaseProbation() { ++_probation; }
-
-	inline bool operator==(const Path &p) const { return ((p._addr == _addr)&&(p._localAddress == _localAddress)); }
-	inline bool operator!=(const Path &p) const { return ((p._addr != _addr)||(p._localAddress != _localAddress)); }
-
 private:
-	uint64_t _lastSend;
-	uint64_t _lastPing;
-	uint64_t _lastKeepalive;
-	uint64_t _lastReceived;
+	uint64_t _lastOut;
+	uint64_t _lastIn;
 	InetAddress _addr;
 	InetAddress _localAddress;
-	unsigned int _flags;
-	unsigned int _probation;
 	InetAddress::IpScope _ipScope; // memoize this since it's a computed value checked often
+	AtomicCounter __refCount;
+	bool _clusterSuboptimal;
 };
 
 } // namespace ZeroTier
diff --git a/node/Switch.cpp b/node/Switch.cpp
index aae16001..dc238607 100644
--- a/node/Switch.cpp
+++ b/node/Switch.cpp
@@ -73,6 +73,9 @@ void Switch::onRemotePacket(const InetAddress &localAddr,const InetAddress &from
 	try {
 		const uint64_t now = RR->node->now();
 
+		SharedPtr<Path> path(RR->topology->getPath(localAddr,fromAddr));
+		path->received(now);
+
 		if (len == 13) {
 			/* LEGACY: before VERB_PUSH_DIRECT_PATHS, peers used broadcast
 			 * announcements on the LAN to solve the 'same network problem.' We
@@ -90,7 +93,7 @@ void Switch::onRemotePacket(const InetAddress &localAddr,const InetAddress &from
 					_lastBeaconResponse = now;
 					Packet outp(peer->address(),RR->identity.address(),Packet::VERB_NOP);
 					outp.armor(peer->key(),true);
-					RR->node->putPacket(localAddr,fromAddr,outp.data(),outp.size());
+					path->send(RR,outp.data(),outp.size(),now);
 				}
 			}
 
@@ -259,7 +262,7 @@ void Switch::onRemotePacket(const InetAddress &localAddr,const InetAddress &from
 							// We have all fragments -- assemble and process full Packet
 							//TRACE("packet %.16llx is complete, assembling and processing...",pid);
 
-							rq->frag0.init(data,len,localAddr,fromAddr,now);
+							rq->frag0.init(data,len,path,now);
 							for(unsigned int f=1;f<rq->totalFragments;++f)
 								rq->frag0.append(rq->frags[f - 1].payload(),rq->frags[f - 1].payloadLength());
 
@@ -270,12 +273,12 @@ void Switch::onRemotePacket(const InetAddress &localAddr,const InetAddress &from
 							}
 						} else {
 							// Still waiting on more fragments, but keep the head
-							rq->frag0.init(data,len,localAddr,fromAddr,now);
+							rq->frag0.init(data,len,path,now);
 						}
 					} // else this is a duplicate head, ignore
 				} else {
 					// Packet is unfragmented, so just process it
-					IncomingPacket packet(data,len,localAddr,fromAddr,now);
+					IncomingPacket packet(data,len,path,now);
 					if (!packet.tryDecode(RR)) {
 						Mutex::Lock _l(_rxQueue_m);
 						RXQueueEntry *rq = &(_rxQueue[ZT_RX_QUEUE_SIZE - 1]);
diff --git a/node/Topology.hpp b/node/Topology.hpp
index b8213cf8..e63766cb 100644
--- a/node/Topology.hpp
+++ b/node/Topology.hpp
@@ -33,6 +33,7 @@
 #include "Address.hpp"
 #include "Identity.hpp"
 #include "Peer.hpp"
+#include "Path.hpp"
 #include "Mutex.hpp"
 #include "InetAddress.hpp"
 #include "Hashtable.hpp"
@@ -90,6 +91,22 @@ public:
 	}
 
 	/**
+	 * Get a Path object for a given local and remote physical address, creating if needed
+	 *
+	 * @param l Local address or NULL for 'any' or 'wildcard'
+	 * @param r Remote address
+	 * @return Pointer to canonicalized Path object
+	 */
+	inline SharedPtr<Path> getPath(const InetAddress &l,const InetAddress &r)
+	{
+		Mutex::Lock _l(_lock);
+		SharedPtr<Path> &p = _paths[Path::HashKey(l,r)];
+		if (!p)
+			p.setToUnsafe(new Path(l,r));
+		return p;
+	}
+
+	/**
 	 * Get the identity of a peer
 	 *
 	 * @param zta ZeroTier address of peer
@@ -319,8 +336,12 @@ private:
 	uint64_t _trustedPathIds[ZT_MAX_TRUSTED_PATHS];
 	InetAddress _trustedPathNetworks[ZT_MAX_TRUSTED_PATHS];
 	unsigned int _trustedPathCount;
+
 	World _world;
+
 	Hashtable< Address,SharedPtr<Peer> > _peers;
+	Hashtable< Path::HashKey,SharedPtr<Path> > _paths;
+
 	std::vector< Address > _rootAddresses;
 	std::vector< SharedPtr<Peer> > _rootPeers;
 	bool _amRoot;