Path.hpp 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319
  1. /*
  2. * ZeroTier One - Network Virtualization Everywhere
  3. * Copyright (C) 2011-2016 ZeroTier, Inc. https://www.zerotier.com/
  4. *
  5. * This program is free software: you can redistribute it and/or modify
  6. * it under the terms of the GNU General Public License as published by
  7. * the Free Software Foundation, either version 3 of the License, or
  8. * (at your option) any later version.
  9. *
  10. * This program is distributed in the hope that it will be useful,
  11. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13. * GNU General Public License for more details.
  14. *
  15. * You should have received a copy of the GNU General Public License
  16. * along with this program. If not, see <http://www.gnu.org/licenses/>.
  17. */
  18. #ifndef ZT_PATH_HPP
  19. #define ZT_PATH_HPP
  20. #include <stdint.h>
  21. #include <string.h>
  22. #include <stdlib.h>
  23. #include <stdexcept>
  24. #include <algorithm>
  25. #include "Constants.hpp"
  26. #include "InetAddress.hpp"
  27. #include "SharedPtr.hpp"
  28. #include "AtomicCounter.hpp"
  29. #include "NonCopyable.hpp"
  30. #include "Utils.hpp"
  31. /**
  32. * Maximum return value of preferenceRank()
  33. */
  34. #define ZT_PATH_MAX_PREFERENCE_RANK ((ZT_INETADDRESS_MAX_SCOPE << 1) | 1)
  35. namespace ZeroTier {
  36. class RuntimeEnvironment;
  37. /**
  38. * A path across the physical network
  39. */
  40. class Path : NonCopyable
  41. {
  42. friend class SharedPtr<Path>;
  43. public:
  44. /**
  45. * Efficient unique key for paths in a Hashtable
  46. */
  47. class HashKey
  48. {
  49. public:
  50. HashKey() {}
  51. HashKey(const InetAddress &l,const InetAddress &r)
  52. {
  53. // This is an ad-hoc bit packing algorithm to yield unique keys for
  54. // remote addresses and their local-side counterparts if defined.
  55. // Portability across runtimes is not needed.
  56. if (r.ss_family == AF_INET) {
  57. _k[0] = (uint64_t)reinterpret_cast<const struct sockaddr_in *>(&r)->sin_addr.s_addr;
  58. _k[1] = (uint64_t)reinterpret_cast<const struct sockaddr_in *>(&r)->sin_port;
  59. if (l.ss_family == AF_INET) {
  60. _k[2] = (uint64_t)reinterpret_cast<const struct sockaddr_in *>(&l)->sin_addr.s_addr;
  61. _k[3] = (uint64_t)reinterpret_cast<const struct sockaddr_in *>(&r)->sin_port;
  62. } else {
  63. _k[2] = 0;
  64. _k[3] = 0;
  65. }
  66. } else if (r.ss_family == AF_INET6) {
  67. const uint8_t *a = reinterpret_cast<const uint8_t *>(reinterpret_cast<const struct sockaddr_in6 *>(&r)->sin6_addr.s6_addr);
  68. uint8_t *b = reinterpret_cast<uint8_t *>(_k);
  69. for(unsigned int i=0;i<16;++i) b[i] = a[i];
  70. _k[2] = ~((uint64_t)reinterpret_cast<const struct sockaddr_in6 *>(&r)->sin6_port);
  71. if (l.ss_family == AF_INET6) {
  72. _k[2] ^= ((uint64_t)reinterpret_cast<const struct sockaddr_in6 *>(&r)->sin6_port) << 32;
  73. a = reinterpret_cast<const uint8_t *>(reinterpret_cast<const struct sockaddr_in6 *>(&l)->sin6_addr.s6_addr);
  74. b += 24;
  75. for(unsigned int i=0;i<8;++i) b[i] = a[i];
  76. a += 8;
  77. for(unsigned int i=0;i<8;++i) b[i] ^= a[i];
  78. }
  79. } else {
  80. _k[0] = 0;
  81. _k[1] = 0;
  82. _k[2] = 0;
  83. _k[3] = 0;
  84. }
  85. }
  86. inline unsigned long hashCode() const { return (unsigned long)(_k[0] + _k[1] + _k[2] + _k[3]); }
  87. 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]) ); }
  88. inline bool operator!=(const HashKey &k) const { return (!(*this == k)); }
  89. private:
  90. uint64_t _k[4];
  91. };
  92. Path() :
  93. _lastOut(0),
  94. _lastIn(0),
  95. _lastTrustEstablishedPacketReceived(0),
  96. _incomingLinkQualityFastLog(0xffffffffffffffffULL),
  97. _incomingLinkQualitySlowLogPtr(0),
  98. _incomingLinkQualitySlowLogCounter(-64), // discard first fast log
  99. _incomingLinkQualityPreviousPacketCounter(0),
  100. _outgoingPacketCounter(0),
  101. _addr(),
  102. _localAddress(),
  103. _ipScope(InetAddress::IP_SCOPE_NONE)
  104. {
  105. for(int i=0;i<(int)sizeof(_incomingLinkQualitySlowLog);++i)
  106. _incomingLinkQualitySlowLog[i] = ZT_PATH_LINK_QUALITY_MAX;
  107. }
  108. Path(const InetAddress &localAddress,const InetAddress &addr) :
  109. _lastOut(0),
  110. _lastIn(0),
  111. _lastTrustEstablishedPacketReceived(0),
  112. _incomingLinkQualityFastLog(0xffffffffffffffffULL),
  113. _incomingLinkQualitySlowLogPtr(0),
  114. _incomingLinkQualitySlowLogCounter(-64), // discard first fast log
  115. _incomingLinkQualityPreviousPacketCounter(0),
  116. _outgoingPacketCounter(0),
  117. _addr(addr),
  118. _localAddress(localAddress),
  119. _ipScope(addr.ipScope())
  120. {
  121. for(int i=0;i<(int)sizeof(_incomingLinkQualitySlowLog);++i)
  122. _incomingLinkQualitySlowLog[i] = ZT_PATH_LINK_QUALITY_MAX;
  123. }
  124. /**
  125. * Called when a packet is received from this remote path, regardless of content
  126. *
  127. * @param t Time of receive
  128. */
  129. inline void received(const uint64_t t) { _lastIn = t; }
  130. /**
  131. * Update link quality using a counter from an incoming packet (or packet head in fragmented case)
  132. *
  133. * @param counter Packet link quality counter (range 0 to 7, must not have other bits set)
  134. */
  135. inline void updateLinkQuality(const unsigned int counter)
  136. {
  137. const unsigned int prev = _incomingLinkQualityPreviousPacketCounter;
  138. _incomingLinkQualityPreviousPacketCounter = counter;
  139. const uint64_t fl = (_incomingLinkQualityFastLog = ((_incomingLinkQualityFastLog << 1) | (uint64_t)(prev == ((counter - 1) & 0x7))));
  140. if (++_incomingLinkQualitySlowLogCounter >= 64) {
  141. _incomingLinkQualitySlowLogCounter = 0;
  142. _incomingLinkQualitySlowLog[_incomingLinkQualitySlowLogPtr++ % sizeof(_incomingLinkQualitySlowLog)] = (uint8_t)Utils::countBits(fl);
  143. }
  144. }
  145. /**
  146. * @return Link quality from 0 (min) to 255 (max)
  147. */
  148. inline unsigned int linkQuality() const
  149. {
  150. unsigned long slsize = _incomingLinkQualitySlowLogPtr;
  151. if (slsize > (unsigned long)sizeof(_incomingLinkQualitySlowLog))
  152. slsize = (unsigned long)sizeof(_incomingLinkQualitySlowLog);
  153. else if (!slsize)
  154. return 255; // ZT_PATH_LINK_QUALITY_MAX
  155. unsigned long lq = 0;
  156. for(unsigned long i=0;i<slsize;++i)
  157. lq += (unsigned long)_incomingLinkQualitySlowLog[i] * 4;
  158. lq /= slsize;
  159. return (unsigned int)((lq >= 255) ? 255 : lq);
  160. }
  161. /**
  162. * Set time last trusted packet was received (done in Peer::received())
  163. */
  164. inline void trustedPacketReceived(const uint64_t t) { _lastTrustEstablishedPacketReceived = t; }
  165. /**
  166. * Send a packet via this path (last out time is also updated)
  167. *
  168. * @param RR Runtime environment
  169. * @param tPtr Thread pointer to be handed through to any callbacks called as a result of this call
  170. * @param data Packet data
  171. * @param len Packet length
  172. * @param now Current time
  173. * @return True if transport reported success
  174. */
  175. bool send(const RuntimeEnvironment *RR,void *tPtr,const void *data,unsigned int len,uint64_t now);
  176. /**
  177. * Manually update last sent time
  178. *
  179. * @param t Time of send
  180. */
  181. inline void sent(const uint64_t t) { _lastOut = t; }
  182. /**
  183. * @return Address of local side of this path or NULL if unspecified
  184. */
  185. inline const InetAddress &localAddress() const { return _localAddress; }
  186. /**
  187. * @return Physical address
  188. */
  189. inline const InetAddress &address() const { return _addr; }
  190. /**
  191. * @return IP scope -- faster shortcut for address().ipScope()
  192. */
  193. inline InetAddress::IpScope ipScope() const { return _ipScope; }
  194. /**
  195. * @return True if path has received a trust established packet (e.g. common network membership) in the past ZT_TRUST_EXPIRATION ms
  196. */
  197. inline bool trustEstablished(const uint64_t now) const { return ((now - _lastTrustEstablishedPacketReceived) < ZT_TRUST_EXPIRATION); }
  198. /**
  199. * @return Preference rank, higher == better
  200. */
  201. inline unsigned int preferenceRank() const
  202. {
  203. // This causes us to rank paths in order of IP scope rank (see InetAdddress.hpp) but
  204. // within each IP scope class to prefer IPv6 over IPv4.
  205. return ( ((unsigned int)_ipScope << 1) | (unsigned int)(_addr.ss_family == AF_INET6) );
  206. }
  207. /**
  208. * Check whether this address is valid for a ZeroTier path
  209. *
  210. * This checks the address type and scope against address types and scopes
  211. * that we currently support for ZeroTier communication.
  212. *
  213. * @param a Address to check
  214. * @return True if address is good for ZeroTier path use
  215. */
  216. static inline bool isAddressValidForPath(const InetAddress &a)
  217. {
  218. if ((a.ss_family == AF_INET)||(a.ss_family == AF_INET6)) {
  219. switch(a.ipScope()) {
  220. /* Note: we don't do link-local at the moment. Unfortunately these
  221. * cause several issues. The first is that they usually require a
  222. * device qualifier, which we don't handle yet and can't portably
  223. * push in PUSH_DIRECT_PATHS. The second is that some OSes assign
  224. * these very ephemerally or otherwise strangely. So we'll use
  225. * private, pseudo-private, shared (e.g. carrier grade NAT), or
  226. * global IP addresses. */
  227. case InetAddress::IP_SCOPE_PRIVATE:
  228. case InetAddress::IP_SCOPE_PSEUDOPRIVATE:
  229. case InetAddress::IP_SCOPE_SHARED:
  230. case InetAddress::IP_SCOPE_GLOBAL:
  231. if (a.ss_family == AF_INET6) {
  232. // TEMPORARY HACK: for now, we are going to blacklist he.net IPv6
  233. // tunnels due to very spotty performance and low MTU issues over
  234. // these IPv6 tunnel links.
  235. const uint8_t *ipd = reinterpret_cast<const uint8_t *>(reinterpret_cast<const struct sockaddr_in6 *>(&a)->sin6_addr.s6_addr);
  236. if ((ipd[0] == 0x20)&&(ipd[1] == 0x01)&&(ipd[2] == 0x04)&&(ipd[3] == 0x70))
  237. return false;
  238. }
  239. return true;
  240. default:
  241. return false;
  242. }
  243. }
  244. return false;
  245. }
  246. /**
  247. * @return True if path appears alive
  248. */
  249. inline bool alive(const uint64_t now) const { return ((now - _lastIn) <= ZT_PATH_ALIVE_TIMEOUT); }
  250. /**
  251. * @return True if this path needs a heartbeat
  252. */
  253. inline bool needsHeartbeat(const uint64_t now) const { return ((now - _lastOut) >= ZT_PATH_HEARTBEAT_PERIOD); }
  254. /**
  255. * @return Last time we sent something
  256. */
  257. inline uint64_t lastOut() const { return _lastOut; }
  258. /**
  259. * @return Last time we received anything
  260. */
  261. inline uint64_t lastIn() const { return _lastIn; }
  262. /**
  263. * Return and increment outgoing packet counter (used with Packet::armor())
  264. *
  265. * @return Next value that should be used for outgoing packet counter (only least significant 3 bits are used)
  266. */
  267. inline unsigned int nextOutgoingCounter() { return _outgoingPacketCounter++; }
  268. private:
  269. volatile uint64_t _lastOut;
  270. volatile uint64_t _lastIn;
  271. volatile uint64_t _lastTrustEstablishedPacketReceived;
  272. volatile uint64_t _incomingLinkQualityFastLog;
  273. volatile unsigned long _incomingLinkQualitySlowLogPtr;
  274. volatile signed int _incomingLinkQualitySlowLogCounter;
  275. volatile unsigned int _incomingLinkQualityPreviousPacketCounter;
  276. volatile unsigned int _outgoingPacketCounter;
  277. InetAddress _addr;
  278. InetAddress _localAddress;
  279. InetAddress::IpScope _ipScope; // memoize this since it's a computed value checked often
  280. volatile uint8_t _incomingLinkQualitySlowLog[32];
  281. AtomicCounter __refCount;
  282. };
  283. } // namespace ZeroTier
  284. #endif