Switch.cpp 41 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154
  1. /*
  2. * Copyright (c)2013-2020 ZeroTier, Inc.
  3. *
  4. * Use of this software is governed by the Business Source License included
  5. * in the LICENSE.TXT file in the project's root directory.
  6. *
  7. * Change Date: 2025-01-01
  8. *
  9. * On the date above, in accordance with the Business Source License, use
  10. * of this software will be governed by version 2.0 of the Apache License.
  11. */
  12. /****/
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15. #include <algorithm>
  16. #include <utility>
  17. #include <stdexcept>
  18. #include "../version.h"
  19. #include "../include/ZeroTierOne.h"
  20. #include "Constants.hpp"
  21. #include "RuntimeEnvironment.hpp"
  22. #include "Switch.hpp"
  23. #include "Node.hpp"
  24. #include "InetAddress.hpp"
  25. #include "Topology.hpp"
  26. #include "Peer.hpp"
  27. #include "SelfAwareness.hpp"
  28. #include "Packet.hpp"
  29. #include "Trace.hpp"
  30. #include "Metrics.hpp"
  31. namespace ZeroTier {
  32. Switch::Switch(const RuntimeEnvironment *renv) :
  33. RR(renv),
  34. _lastBeaconResponse(0),
  35. _lastCheckedQueues(0),
  36. _lastUniteAttempt(8) // only really used on root servers and upstreams, and it'll grow there just fine
  37. {
  38. }
  39. // Returns true if packet appears valid; pos and proto will be set
  40. static bool _ipv6GetPayload(const uint8_t *frameData,unsigned int frameLen,unsigned int &pos,unsigned int &proto)
  41. {
  42. if (frameLen < 40)
  43. return false;
  44. pos = 40;
  45. proto = frameData[6];
  46. while (pos <= frameLen) {
  47. switch(proto) {
  48. case 0: // hop-by-hop options
  49. case 43: // routing
  50. case 60: // destination options
  51. case 135: // mobility options
  52. if ((pos + 8) > frameLen)
  53. return false; // invalid!
  54. proto = frameData[pos];
  55. pos += ((unsigned int)frameData[pos + 1] * 8) + 8;
  56. break;
  57. //case 44: // fragment -- we currently can't parse these and they are deprecated in IPv6 anyway
  58. //case 50:
  59. //case 51: // IPSec ESP and AH -- we have to stop here since this is encrypted stuff
  60. default:
  61. return true;
  62. }
  63. }
  64. return false; // overflow == invalid
  65. }
  66. void Switch::onRemotePacket(void *tPtr,const int64_t localSocket,const InetAddress &fromAddr,const void *data,unsigned int len)
  67. {
  68. int32_t flowId = ZT_QOS_NO_FLOW;
  69. try {
  70. const int64_t now = RR->node->now();
  71. const SharedPtr<Path> path(RR->topology->getPath(localSocket,fromAddr));
  72. path->received(now);
  73. if (len == 13) {
  74. /* LEGACY: before VERB_PUSH_DIRECT_PATHS, peers used broadcast
  75. * announcements on the LAN to solve the 'same network problem.' We
  76. * no longer send these, but we'll listen for them for a while to
  77. * locate peers with versions <1.0.4. */
  78. const Address beaconAddr(reinterpret_cast<const char *>(data) + 8,5);
  79. if (beaconAddr == RR->identity.address())
  80. return;
  81. if (!RR->node->shouldUsePathForZeroTierTraffic(tPtr,beaconAddr,localSocket,fromAddr))
  82. return;
  83. const SharedPtr<Peer> peer(RR->topology->getPeer(tPtr,beaconAddr));
  84. if (peer) { // we'll only respond to beacons from known peers
  85. if ((now - _lastBeaconResponse) >= 2500) { // limit rate of responses
  86. _lastBeaconResponse = now;
  87. Packet outp(peer->address(),RR->identity.address(),Packet::VERB_NOP);
  88. outp.armor(peer->key(),true,peer->aesKeysIfSupported());
  89. path->send(RR,tPtr,outp.data(),outp.size(),now);
  90. }
  91. }
  92. } else if (len > ZT_PROTO_MIN_FRAGMENT_LENGTH) { // SECURITY: min length check is important since we do some C-style stuff below!
  93. if (reinterpret_cast<const uint8_t *>(data)[ZT_PACKET_FRAGMENT_IDX_FRAGMENT_INDICATOR] == ZT_PACKET_FRAGMENT_INDICATOR) {
  94. // Handle fragment ----------------------------------------------------
  95. Packet::Fragment fragment(data,len);
  96. const Address destination(fragment.destination());
  97. if (destination != RR->identity.address()) {
  98. if ( (!RR->topology->amUpstream()) && (!path->trustEstablished(now)) )
  99. return;
  100. if (fragment.hops() < ZT_RELAY_MAX_HOPS) {
  101. fragment.incrementHops();
  102. // Note: we don't bother initiating NAT-t for fragments, since heads will set that off.
  103. // It wouldn't hurt anything, just redundant and unnecessary.
  104. SharedPtr<Peer> relayTo = RR->topology->getPeer(tPtr,destination);
  105. if ((!relayTo)||(!relayTo->sendDirect(tPtr,fragment.data(),fragment.size(),now,false))) {
  106. // Don't know peer or no direct path -- so relay via someone upstream
  107. relayTo = RR->topology->getUpstreamPeer();
  108. if (relayTo)
  109. relayTo->sendDirect(tPtr,fragment.data(),fragment.size(),now,true);
  110. }
  111. }
  112. } else {
  113. // Fragment looks like ours
  114. const uint64_t fragmentPacketId = fragment.packetId();
  115. const unsigned int fragmentNumber = fragment.fragmentNumber();
  116. const unsigned int totalFragments = fragment.totalFragments();
  117. if ((totalFragments <= ZT_MAX_PACKET_FRAGMENTS)&&(fragmentNumber < ZT_MAX_PACKET_FRAGMENTS)&&(fragmentNumber > 0)&&(totalFragments > 1)) {
  118. // Fragment appears basically sane. Its fragment number must be
  119. // 1 or more, since a Packet with fragmented bit set is fragment 0.
  120. // Total fragments must be more than 1, otherwise why are we
  121. // seeing a Packet::Fragment?
  122. RXQueueEntry *const rq = _findRXQueueEntry(fragmentPacketId);
  123. Mutex::Lock rql(rq->lock);
  124. if (rq->packetId != fragmentPacketId) {
  125. // No packet found, so we received a fragment without its head.
  126. rq->flowId = flowId;
  127. rq->timestamp = now;
  128. rq->packetId = fragmentPacketId;
  129. rq->frags[fragmentNumber - 1] = fragment;
  130. rq->totalFragments = totalFragments; // total fragment count is known
  131. rq->haveFragments = 1 << fragmentNumber; // we have only this fragment
  132. rq->complete = false;
  133. } else if (!(rq->haveFragments & (1 << fragmentNumber))) {
  134. // We have other fragments and maybe the head, so add this one and check
  135. rq->frags[fragmentNumber - 1] = fragment;
  136. rq->totalFragments = totalFragments;
  137. if (Utils::countBits(rq->haveFragments |= (1 << fragmentNumber)) == totalFragments) {
  138. // We have all fragments -- assemble and process full Packet
  139. for(unsigned int f=1;f<totalFragments;++f)
  140. rq->frag0.append(rq->frags[f - 1].payload(),rq->frags[f - 1].payloadLength());
  141. if (rq->frag0.tryDecode(RR,tPtr,flowId)) {
  142. rq->timestamp = 0; // packet decoded, free entry
  143. } else {
  144. rq->complete = true; // set complete flag but leave entry since it probably needs WHOIS or something
  145. }
  146. }
  147. } // else this is a duplicate fragment, ignore
  148. }
  149. }
  150. // --------------------------------------------------------------------
  151. } else if (len >= ZT_PROTO_MIN_PACKET_LENGTH) { // min length check is important!
  152. // Handle packet head -------------------------------------------------
  153. const Address destination(reinterpret_cast<const uint8_t *>(data) + 8,ZT_ADDRESS_LENGTH);
  154. const Address source(reinterpret_cast<const uint8_t *>(data) + 13,ZT_ADDRESS_LENGTH);
  155. if (source == RR->identity.address())
  156. return;
  157. if (destination != RR->identity.address()) {
  158. if ( (!RR->topology->amUpstream()) && (!path->trustEstablished(now)) && (source != RR->identity.address()) )
  159. return;
  160. Packet packet(data,len);
  161. if (packet.hops() < ZT_RELAY_MAX_HOPS) {
  162. packet.incrementHops();
  163. SharedPtr<Peer> relayTo = RR->topology->getPeer(tPtr,destination);
  164. if ((relayTo)&&(relayTo->sendDirect(tPtr,packet.data(),packet.size(),now,false))) {
  165. if ((source != RR->identity.address())&&(_shouldUnite(now,source,destination))) {
  166. const SharedPtr<Peer> sourcePeer(RR->topology->getPeer(tPtr,source));
  167. if (sourcePeer)
  168. relayTo->introduce(tPtr,now,sourcePeer);
  169. }
  170. } else {
  171. relayTo = RR->topology->getUpstreamPeer();
  172. if ((relayTo)&&(relayTo->address() != source)) {
  173. if (relayTo->sendDirect(tPtr,packet.data(),packet.size(),now,true)) {
  174. const SharedPtr<Peer> sourcePeer(RR->topology->getPeer(tPtr,source));
  175. if (sourcePeer)
  176. relayTo->introduce(tPtr,now,sourcePeer);
  177. }
  178. }
  179. }
  180. }
  181. } else if ((reinterpret_cast<const uint8_t *>(data)[ZT_PACKET_IDX_FLAGS] & ZT_PROTO_FLAG_FRAGMENTED) != 0) {
  182. // Packet is the head of a fragmented packet series
  183. const uint64_t packetId = (
  184. (((uint64_t)reinterpret_cast<const uint8_t *>(data)[0]) << 56) |
  185. (((uint64_t)reinterpret_cast<const uint8_t *>(data)[1]) << 48) |
  186. (((uint64_t)reinterpret_cast<const uint8_t *>(data)[2]) << 40) |
  187. (((uint64_t)reinterpret_cast<const uint8_t *>(data)[3]) << 32) |
  188. (((uint64_t)reinterpret_cast<const uint8_t *>(data)[4]) << 24) |
  189. (((uint64_t)reinterpret_cast<const uint8_t *>(data)[5]) << 16) |
  190. (((uint64_t)reinterpret_cast<const uint8_t *>(data)[6]) << 8) |
  191. ((uint64_t)reinterpret_cast<const uint8_t *>(data)[7])
  192. );
  193. RXQueueEntry *const rq = _findRXQueueEntry(packetId);
  194. Mutex::Lock rql(rq->lock);
  195. if (rq->packetId != packetId) {
  196. // If we have no other fragments yet, create an entry and save the head
  197. rq->flowId = flowId;
  198. rq->timestamp = now;
  199. rq->packetId = packetId;
  200. rq->frag0.init(data,len,path,now);
  201. rq->totalFragments = 0;
  202. rq->haveFragments = 1;
  203. rq->complete = false;
  204. } else if (!(rq->haveFragments & 1)) {
  205. // If we have other fragments but no head, see if we are complete with the head
  206. if ((rq->totalFragments > 1)&&(Utils::countBits(rq->haveFragments |= 1) == rq->totalFragments)) {
  207. // We have all fragments -- assemble and process full Packet
  208. rq->frag0.init(data,len,path,now);
  209. for(unsigned int f=1;f<rq->totalFragments;++f)
  210. rq->frag0.append(rq->frags[f - 1].payload(),rq->frags[f - 1].payloadLength());
  211. if (rq->frag0.tryDecode(RR,tPtr,flowId)) {
  212. rq->timestamp = 0; // packet decoded, free entry
  213. } else {
  214. rq->complete = true; // set complete flag but leave entry since it probably needs WHOIS or something
  215. }
  216. } else {
  217. // Still waiting on more fragments, but keep the head
  218. rq->frag0.init(data,len,path,now);
  219. }
  220. } // else this is a duplicate head, ignore
  221. } else {
  222. // Packet is unfragmented, so just process it
  223. IncomingPacket packet(data,len,path,now);
  224. if (!packet.tryDecode(RR,tPtr,flowId)) {
  225. RXQueueEntry *const rq = _nextRXQueueEntry();
  226. Mutex::Lock rql(rq->lock);
  227. rq->flowId = flowId;
  228. rq->timestamp = now;
  229. rq->packetId = packet.packetId();
  230. rq->frag0 = packet;
  231. rq->totalFragments = 1;
  232. rq->haveFragments = 1;
  233. rq->complete = true;
  234. }
  235. }
  236. // --------------------------------------------------------------------
  237. }
  238. }
  239. } catch ( ... ) {} // sanity check, should be caught elsewhere
  240. }
  241. void Switch::onLocalEthernet(void *tPtr,const SharedPtr<Network> &network,const MAC &from,const MAC &to,unsigned int etherType,unsigned int vlanId,const void *data,unsigned int len)
  242. {
  243. if (!network->hasConfig())
  244. return;
  245. // Check if this packet is from someone other than the tap -- i.e. bridged in
  246. bool fromBridged;
  247. if ((fromBridged = (from != network->mac()))) {
  248. if (!network->config().permitsBridging(RR->identity.address())) {
  249. RR->t->outgoingNetworkFrameDropped(tPtr,network,from,to,etherType,vlanId,len,"not a bridge");
  250. return;
  251. }
  252. }
  253. uint8_t qosBucket = ZT_AQM_DEFAULT_BUCKET;
  254. /**
  255. * A pseudo-unique identifier used by balancing and bonding policies to
  256. * categorize individual flows/conversations for assignment to a specific
  257. * physical path. This identifier consists of the source port and
  258. * destination port of the encapsulated frame.
  259. *
  260. * A flowId of -1 will indicate that there is no preference for how this
  261. * packet shall be sent. An example of this would be an ICMP packet.
  262. */
  263. int32_t flowId = ZT_QOS_NO_FLOW;
  264. if (etherType == ZT_ETHERTYPE_IPV4 && (len >= 20)) {
  265. uint16_t srcPort = 0;
  266. uint16_t dstPort = 0;
  267. uint8_t proto = (reinterpret_cast<const uint8_t *>(data)[9]);
  268. const unsigned int headerLen = 4 * (reinterpret_cast<const uint8_t *>(data)[0] & 0xf);
  269. switch(proto) {
  270. case 0x01: // ICMP
  271. //flowId = 0x01;
  272. break;
  273. // All these start with 16-bit source and destination port in that order
  274. case 0x06: // TCP
  275. case 0x11: // UDP
  276. case 0x84: // SCTP
  277. case 0x88: // UDPLite
  278. if (len > (headerLen + 4)) {
  279. unsigned int pos = headerLen + 0;
  280. srcPort = (reinterpret_cast<const uint8_t *>(data)[pos++]) << 8;
  281. srcPort |= (reinterpret_cast<const uint8_t *>(data)[pos]);
  282. pos++;
  283. dstPort = (reinterpret_cast<const uint8_t *>(data)[pos++]) << 8;
  284. dstPort |= (reinterpret_cast<const uint8_t *>(data)[pos]);
  285. flowId = dstPort ^ srcPort ^ proto;
  286. }
  287. break;
  288. }
  289. }
  290. if (etherType == ZT_ETHERTYPE_IPV6 && (len >= 40)) {
  291. uint16_t srcPort = 0;
  292. uint16_t dstPort = 0;
  293. unsigned int pos;
  294. unsigned int proto;
  295. _ipv6GetPayload((const uint8_t *)data, len, pos, proto);
  296. switch(proto) {
  297. case 0x3A: // ICMPv6
  298. //flowId = 0x3A;
  299. break;
  300. // All these start with 16-bit source and destination port in that order
  301. case 0x06: // TCP
  302. case 0x11: // UDP
  303. case 0x84: // SCTP
  304. case 0x88: // UDPLite
  305. if (len > (pos + 4)) {
  306. srcPort = (reinterpret_cast<const uint8_t *>(data)[pos++]) << 8;
  307. srcPort |= (reinterpret_cast<const uint8_t *>(data)[pos]);
  308. pos++;
  309. dstPort = (reinterpret_cast<const uint8_t *>(data)[pos++]) << 8;
  310. dstPort |= (reinterpret_cast<const uint8_t *>(data)[pos]);
  311. flowId = dstPort ^ srcPort ^ proto;
  312. }
  313. break;
  314. default:
  315. break;
  316. }
  317. }
  318. if (to.isMulticast()) {
  319. MulticastGroup multicastGroup(to,0);
  320. if (to.isBroadcast()) {
  321. if ( (etherType == ZT_ETHERTYPE_ARP) && (len >= 28) && ((((const uint8_t *)data)[2] == 0x08)&&(((const uint8_t *)data)[3] == 0x00)&&(((const uint8_t *)data)[4] == 6)&&(((const uint8_t *)data)[5] == 4)&&(((const uint8_t *)data)[7] == 0x01)) ) {
  322. /* IPv4 ARP is one of the few special cases that we impose upon what is
  323. * otherwise a straightforward Ethernet switch emulation. Vanilla ARP
  324. * is dumb old broadcast and simply doesn't scale. ZeroTier multicast
  325. * groups have an additional field called ADI (additional distinguishing
  326. * information) which was added specifically for ARP though it could
  327. * be used for other things too. We then take ARP broadcasts and turn
  328. * them into multicasts by stuffing the IP address being queried into
  329. * the 32-bit ADI field. In practice this uses our multicast pub/sub
  330. * system to implement a kind of extended/distributed ARP table. */
  331. multicastGroup = MulticastGroup::deriveMulticastGroupForAddressResolution(InetAddress(((const unsigned char *)data) + 24,4,0));
  332. } else if (!network->config().enableBroadcast()) {
  333. // Don't transmit broadcasts if this network doesn't want them
  334. RR->t->outgoingNetworkFrameDropped(tPtr,network,from,to,etherType,vlanId,len,"broadcast disabled");
  335. return;
  336. }
  337. } else if ((etherType == ZT_ETHERTYPE_IPV6)&&(len >= (40 + 8 + 16))) {
  338. // IPv6 NDP emulation for certain very special patterns of private IPv6 addresses -- if enabled
  339. if ((network->config().ndpEmulation())&&(reinterpret_cast<const uint8_t *>(data)[6] == 0x3a)&&(reinterpret_cast<const uint8_t *>(data)[40] == 0x87)) { // ICMPv6 neighbor solicitation
  340. Address v6EmbeddedAddress;
  341. const uint8_t *const pkt6 = reinterpret_cast<const uint8_t *>(data) + 40 + 8;
  342. const uint8_t *my6 = (const uint8_t *)0;
  343. // ZT-RFC4193 address: fdNN:NNNN:NNNN:NNNN:NN99:93DD:DDDD:DDDD / 88 (one /128 per actual host)
  344. // ZT-6PLANE address: fcXX:XXXX:XXDD:DDDD:DDDD:####:####:#### / 40 (one /80 per actual host)
  345. // (XX - lower 32 bits of network ID XORed with higher 32 bits)
  346. // For these to work, we must have a ZT-managed address assigned in one of the
  347. // above formats, and the query must match its prefix.
  348. for(unsigned int sipk=0;sipk<network->config().staticIpCount;++sipk) {
  349. const InetAddress *const sip = &(network->config().staticIps[sipk]);
  350. if (sip->ss_family == AF_INET6) {
  351. my6 = reinterpret_cast<const uint8_t *>(reinterpret_cast<const struct sockaddr_in6 *>(&(*sip))->sin6_addr.s6_addr);
  352. const unsigned int sipNetmaskBits = Utils::ntoh((uint16_t)reinterpret_cast<const struct sockaddr_in6 *>(&(*sip))->sin6_port);
  353. if ((sipNetmaskBits == 88)&&(my6[0] == 0xfd)&&(my6[9] == 0x99)&&(my6[10] == 0x93)) { // ZT-RFC4193 /88 ???
  354. unsigned int ptr = 0;
  355. while (ptr != 11) {
  356. if (pkt6[ptr] != my6[ptr])
  357. break;
  358. ++ptr;
  359. }
  360. if (ptr == 11) { // prefix match!
  361. v6EmbeddedAddress.setTo(pkt6 + ptr,5);
  362. break;
  363. }
  364. } else if (sipNetmaskBits == 40) { // ZT-6PLANE /40 ???
  365. const uint32_t nwid32 = (uint32_t)((network->id() ^ (network->id() >> 32)) & 0xffffffff);
  366. if ( (my6[0] == 0xfc) && (my6[1] == (uint8_t)((nwid32 >> 24) & 0xff)) && (my6[2] == (uint8_t)((nwid32 >> 16) & 0xff)) && (my6[3] == (uint8_t)((nwid32 >> 8) & 0xff)) && (my6[4] == (uint8_t)(nwid32 & 0xff))) {
  367. unsigned int ptr = 0;
  368. while (ptr != 5) {
  369. if (pkt6[ptr] != my6[ptr])
  370. break;
  371. ++ptr;
  372. }
  373. if (ptr == 5) { // prefix match!
  374. v6EmbeddedAddress.setTo(pkt6 + ptr,5);
  375. break;
  376. }
  377. }
  378. }
  379. }
  380. }
  381. if ((v6EmbeddedAddress)&&(v6EmbeddedAddress != RR->identity.address())) {
  382. const MAC peerMac(v6EmbeddedAddress,network->id());
  383. uint8_t adv[72];
  384. adv[0] = 0x60; adv[1] = 0x00; adv[2] = 0x00; adv[3] = 0x00;
  385. adv[4] = 0x00; adv[5] = 0x20;
  386. adv[6] = 0x3a; adv[7] = 0xff;
  387. for(int i=0;i<16;++i) adv[8 + i] = pkt6[i];
  388. for(int i=0;i<16;++i) adv[24 + i] = my6[i];
  389. adv[40] = 0x88; adv[41] = 0x00;
  390. adv[42] = 0x00; adv[43] = 0x00; // future home of checksum
  391. adv[44] = 0x60; adv[45] = 0x00; adv[46] = 0x00; adv[47] = 0x00;
  392. for(int i=0;i<16;++i) adv[48 + i] = pkt6[i];
  393. adv[64] = 0x02; adv[65] = 0x01;
  394. adv[66] = peerMac[0]; adv[67] = peerMac[1]; adv[68] = peerMac[2]; adv[69] = peerMac[3]; adv[70] = peerMac[4]; adv[71] = peerMac[5];
  395. uint16_t pseudo_[36];
  396. uint8_t *const pseudo = reinterpret_cast<uint8_t *>(pseudo_);
  397. for(int i=0;i<32;++i) pseudo[i] = adv[8 + i];
  398. pseudo[32] = 0x00; pseudo[33] = 0x00; pseudo[34] = 0x00; pseudo[35] = 0x20;
  399. pseudo[36] = 0x00; pseudo[37] = 0x00; pseudo[38] = 0x00; pseudo[39] = 0x3a;
  400. for(int i=0;i<32;++i) pseudo[40 + i] = adv[40 + i];
  401. uint32_t checksum = 0;
  402. for(int i=0;i<36;++i) checksum += Utils::hton(pseudo_[i]);
  403. while ((checksum >> 16)) checksum = (checksum & 0xffff) + (checksum >> 16);
  404. checksum = ~checksum;
  405. adv[42] = (checksum >> 8) & 0xff;
  406. adv[43] = checksum & 0xff;
  407. RR->node->putFrame(tPtr,network->id(),network->userPtr(),peerMac,from,ZT_ETHERTYPE_IPV6,0,adv,72);
  408. return; // NDP emulation done. We have forged a "fake" reply, so no need to send actual NDP query.
  409. } // else no NDP emulation
  410. } // else no NDP emulation
  411. }
  412. // Check this after NDP emulation, since that has to be allowed in exactly this case
  413. if (network->config().multicastLimit == 0) {
  414. RR->t->outgoingNetworkFrameDropped(tPtr,network,from,to,etherType,vlanId,len,"multicast disabled");
  415. return;
  416. }
  417. /* Learn multicast groups for bridged-in hosts.
  418. * Note that some OSes, most notably Linux, do this for you by learning
  419. * multicast addresses on bridge interfaces and subscribing each slave.
  420. * But in that case this does no harm, as the sets are just merged. */
  421. if (fromBridged)
  422. network->learnBridgedMulticastGroup(tPtr,multicastGroup,RR->node->now());
  423. // First pass sets noTee to false, but noTee is set to true in OutboundMulticast to prevent duplicates.
  424. if (!network->filterOutgoingPacket(tPtr,false,RR->identity.address(),Address(),from,to,(const uint8_t *)data,len,etherType,vlanId,qosBucket)) {
  425. RR->t->outgoingNetworkFrameDropped(tPtr,network,from,to,etherType,vlanId,len,"filter blocked");
  426. return;
  427. }
  428. RR->mc->send(
  429. tPtr,
  430. RR->node->now(),
  431. network,
  432. Address(),
  433. multicastGroup,
  434. (fromBridged) ? from : MAC(),
  435. etherType,
  436. data,
  437. len);
  438. } else if (to == network->mac()) {
  439. // Destination is this node, so just reinject it
  440. RR->node->putFrame(tPtr,network->id(),network->userPtr(),from,to,etherType,vlanId,data,len);
  441. } else if (to[0] == MAC::firstOctetForNetwork(network->id())) {
  442. // Destination is another ZeroTier peer on the same network
  443. Address toZT(to.toAddress(network->id())); // since in-network MACs are derived from addresses and network IDs, we can reverse this
  444. SharedPtr<Peer> toPeer(RR->topology->getPeer(tPtr,toZT));
  445. if (!network->filterOutgoingPacket(tPtr,false,RR->identity.address(),toZT,from,to,(const uint8_t *)data,len,etherType,vlanId,qosBucket)) {
  446. RR->t->outgoingNetworkFrameDropped(tPtr,network,from,to,etherType,vlanId,len,"filter blocked");
  447. return;
  448. }
  449. network->pushCredentialsIfNeeded(tPtr,toZT,RR->node->now());
  450. if (!fromBridged) {
  451. Packet outp(toZT,RR->identity.address(),Packet::VERB_FRAME);
  452. outp.append(network->id());
  453. outp.append((uint16_t)etherType);
  454. outp.append(data,len);
  455. // 1.4.8: disable compression for unicast as it almost never helps
  456. //if (!network->config().disableCompression())
  457. // outp.compress();
  458. aqm_enqueue(tPtr,network,outp,true,qosBucket,flowId);
  459. } else {
  460. Packet outp(toZT,RR->identity.address(),Packet::VERB_EXT_FRAME);
  461. outp.append(network->id());
  462. outp.append((unsigned char)0x00);
  463. to.appendTo(outp);
  464. from.appendTo(outp);
  465. outp.append((uint16_t)etherType);
  466. outp.append(data,len);
  467. // 1.4.8: disable compression for unicast as it almost never helps
  468. //if (!network->config().disableCompression())
  469. // outp.compress();
  470. aqm_enqueue(tPtr,network,outp,true,qosBucket,flowId);
  471. }
  472. } else {
  473. // Destination is bridged behind a remote peer
  474. // We filter with a NULL destination ZeroTier address first. Filtrations
  475. // for each ZT destination are also done below. This is the same rationale
  476. // and design as for multicast.
  477. if (!network->filterOutgoingPacket(tPtr,false,RR->identity.address(),Address(),from,to,(const uint8_t *)data,len,etherType,vlanId,qosBucket)) {
  478. RR->t->outgoingNetworkFrameDropped(tPtr,network,from,to,etherType,vlanId,len,"filter blocked");
  479. return;
  480. }
  481. Address bridges[ZT_MAX_BRIDGE_SPAM];
  482. unsigned int numBridges = 0;
  483. /* Create an array of up to ZT_MAX_BRIDGE_SPAM recipients for this bridged frame. */
  484. bridges[0] = network->findBridgeTo(to);
  485. std::vector<Address> activeBridges(network->config().activeBridges());
  486. if ((bridges[0])&&(bridges[0] != RR->identity.address())&&(network->config().permitsBridging(bridges[0]))) {
  487. /* We have a known bridge route for this MAC, send it there. */
  488. ++numBridges;
  489. } else if (!activeBridges.empty()) {
  490. /* If there is no known route, spam to up to ZT_MAX_BRIDGE_SPAM active
  491. * bridges. If someone responds, we'll learn the route. */
  492. std::vector<Address>::const_iterator ab(activeBridges.begin());
  493. if (activeBridges.size() <= ZT_MAX_BRIDGE_SPAM) {
  494. // If there are <= ZT_MAX_BRIDGE_SPAM active bridges, spam them all
  495. while (ab != activeBridges.end()) {
  496. bridges[numBridges++] = *ab;
  497. ++ab;
  498. }
  499. } else {
  500. // Otherwise pick a random set of them
  501. while (numBridges < ZT_MAX_BRIDGE_SPAM) {
  502. if (ab == activeBridges.end())
  503. ab = activeBridges.begin();
  504. if (((unsigned long)RR->node->prng() % (unsigned long)activeBridges.size()) == 0) {
  505. bridges[numBridges++] = *ab;
  506. ++ab;
  507. } else ++ab;
  508. }
  509. }
  510. }
  511. for(unsigned int b=0;b<numBridges;++b) {
  512. if (network->filterOutgoingPacket(tPtr,true,RR->identity.address(),bridges[b],from,to,(const uint8_t *)data,len,etherType,vlanId,qosBucket)) {
  513. Packet outp(bridges[b],RR->identity.address(),Packet::VERB_EXT_FRAME);
  514. outp.append(network->id());
  515. outp.append((uint8_t)0x00);
  516. to.appendTo(outp);
  517. from.appendTo(outp);
  518. outp.append((uint16_t)etherType);
  519. outp.append(data,len);
  520. // 1.4.8: disable compression for unicast as it almost never helps
  521. //if (!network->config().disableCompression())
  522. // outp.compress();
  523. aqm_enqueue(tPtr,network,outp,true,qosBucket,flowId);
  524. } else {
  525. RR->t->outgoingNetworkFrameDropped(tPtr,network,from,to,etherType,vlanId,len,"filter blocked (bridge replication)");
  526. }
  527. }
  528. }
  529. }
  530. void Switch::aqm_enqueue(void *tPtr, const SharedPtr<Network> &network, Packet &packet,bool encrypt,int qosBucket,int32_t flowId)
  531. {
  532. if(!network->qosEnabled()) {
  533. send(tPtr, packet, encrypt, flowId);
  534. return;
  535. }
  536. NetworkQoSControlBlock *nqcb = _netQueueControlBlock[network->id()];
  537. if (!nqcb) {
  538. nqcb = new NetworkQoSControlBlock();
  539. _netQueueControlBlock[network->id()] = nqcb;
  540. // Initialize ZT_QOS_NUM_BUCKETS queues and place them in the INACTIVE list
  541. // These queues will be shuffled between the new/old/inactive lists by the enqueue/dequeue algorithm
  542. for (int i=0; i<ZT_AQM_NUM_BUCKETS; i++) {
  543. nqcb->inactiveQueues.push_back(new ManagedQueue(i));
  544. }
  545. }
  546. // Don't apply QoS scheduling to ZT protocol traffic
  547. if (packet.verb() != Packet::VERB_FRAME && packet.verb() != Packet::VERB_EXT_FRAME) {
  548. send(tPtr, packet, encrypt, flowId);
  549. }
  550. _aqm_m.lock();
  551. // Enqueue packet and move queue to appropriate list
  552. const Address dest(packet.destination());
  553. TXQueueEntry *txEntry = new TXQueueEntry(dest,RR->node->now(),packet,encrypt,flowId);
  554. ManagedQueue *selectedQueue = nullptr;
  555. for (size_t i=0; i<ZT_AQM_NUM_BUCKETS; i++) {
  556. if (i < nqcb->oldQueues.size()) { // search old queues first (I think this is best since old would imply most recent usage of the queue)
  557. if (nqcb->oldQueues[i]->id == qosBucket) {
  558. selectedQueue = nqcb->oldQueues[i];
  559. }
  560. } if (i < nqcb->newQueues.size()) { // search new queues (this would imply not often-used queues)
  561. if (nqcb->newQueues[i]->id == qosBucket) {
  562. selectedQueue = nqcb->newQueues[i];
  563. }
  564. } if (i < nqcb->inactiveQueues.size()) { // search inactive queues
  565. if (nqcb->inactiveQueues[i]->id == qosBucket) {
  566. selectedQueue = nqcb->inactiveQueues[i];
  567. // move queue to end of NEW queue list
  568. selectedQueue->byteCredit = ZT_AQM_QUANTUM;
  569. // DEBUG_INFO("moving q=%p from INACTIVE to NEW list", selectedQueue);
  570. nqcb->newQueues.push_back(selectedQueue);
  571. nqcb->inactiveQueues.erase(nqcb->inactiveQueues.begin() + i);
  572. }
  573. }
  574. }
  575. if (!selectedQueue) {
  576. _aqm_m.unlock();
  577. return;
  578. }
  579. selectedQueue->q.push_back(txEntry);
  580. selectedQueue->byteLength+=txEntry->packet.payloadLength();
  581. nqcb->_currEnqueuedPackets++;
  582. // DEBUG_INFO("nq=%2lu, oq=%2lu, iq=%2lu, nqcb.size()=%3d, bucket=%2d, q=%p", nqcb->newQueues.size(), nqcb->oldQueues.size(), nqcb->inactiveQueues.size(), nqcb->_currEnqueuedPackets, qosBucket, selectedQueue);
  583. // Drop a packet if necessary
  584. ManagedQueue *selectedQueueToDropFrom = nullptr;
  585. if (nqcb->_currEnqueuedPackets > ZT_AQM_MAX_ENQUEUED_PACKETS)
  586. {
  587. // DEBUG_INFO("too many enqueued packets (%d), finding packet to drop", nqcb->_currEnqueuedPackets);
  588. int maxQueueLength = 0;
  589. for (size_t i=0; i<ZT_AQM_NUM_BUCKETS; i++) {
  590. if (i < nqcb->oldQueues.size()) {
  591. if (nqcb->oldQueues[i]->byteLength > maxQueueLength) {
  592. maxQueueLength = nqcb->oldQueues[i]->byteLength;
  593. selectedQueueToDropFrom = nqcb->oldQueues[i];
  594. }
  595. } if (i < nqcb->newQueues.size()) {
  596. if (nqcb->newQueues[i]->byteLength > maxQueueLength) {
  597. maxQueueLength = nqcb->newQueues[i]->byteLength;
  598. selectedQueueToDropFrom = nqcb->newQueues[i];
  599. }
  600. } if (i < nqcb->inactiveQueues.size()) {
  601. if (nqcb->inactiveQueues[i]->byteLength > maxQueueLength) {
  602. maxQueueLength = nqcb->inactiveQueues[i]->byteLength;
  603. selectedQueueToDropFrom = nqcb->inactiveQueues[i];
  604. }
  605. }
  606. }
  607. if (selectedQueueToDropFrom) {
  608. // DEBUG_INFO("dropping packet from head of largest queue (%d payload bytes)", maxQueueLength);
  609. int sizeOfDroppedPacket = selectedQueueToDropFrom->q.front()->packet.payloadLength();
  610. delete selectedQueueToDropFrom->q.front();
  611. selectedQueueToDropFrom->q.pop_front();
  612. selectedQueueToDropFrom->byteLength-=sizeOfDroppedPacket;
  613. nqcb->_currEnqueuedPackets--;
  614. }
  615. }
  616. _aqm_m.unlock();
  617. aqm_dequeue(tPtr);
  618. }
  619. uint64_t Switch::control_law(uint64_t t, int count)
  620. {
  621. return (uint64_t)(t + ZT_AQM_INTERVAL / sqrt(count));
  622. }
  623. Switch::dqr Switch::dodequeue(ManagedQueue *q, uint64_t now)
  624. {
  625. dqr r;
  626. r.ok_to_drop = false;
  627. r.p = q->q.front();
  628. if (r.p == NULL) {
  629. q->first_above_time = 0;
  630. return r;
  631. }
  632. uint64_t sojourn_time = now - r.p->creationTime;
  633. if (sojourn_time < ZT_AQM_TARGET || q->byteLength <= ZT_DEFAULT_MTU) {
  634. // went below - stay below for at least interval
  635. q->first_above_time = 0;
  636. } else {
  637. if (q->first_above_time == 0) {
  638. // just went above from below. if still above at
  639. // first_above_time, will say it's ok to drop.
  640. q->first_above_time = now + ZT_AQM_INTERVAL;
  641. } else if (now >= q->first_above_time) {
  642. r.ok_to_drop = true;
  643. }
  644. }
  645. return r;
  646. }
  647. Switch::TXQueueEntry * Switch::CoDelDequeue(ManagedQueue *q, bool isNew, uint64_t now)
  648. {
  649. dqr r = dodequeue(q, now);
  650. if (q->dropping) {
  651. if (!r.ok_to_drop) {
  652. q->dropping = false;
  653. }
  654. while (now >= q->drop_next && q->dropping) {
  655. q->q.pop_front(); // drop
  656. r = dodequeue(q, now);
  657. if (!r.ok_to_drop) {
  658. // leave dropping state
  659. q->dropping = false;
  660. } else {
  661. ++(q->count);
  662. // schedule the next drop.
  663. q->drop_next = control_law(q->drop_next, q->count);
  664. }
  665. }
  666. } else if (r.ok_to_drop) {
  667. q->q.pop_front(); // drop
  668. r = dodequeue(q, now);
  669. q->dropping = true;
  670. q->count = (q->count > 2 && now - q->drop_next < 8*ZT_AQM_INTERVAL)?
  671. q->count - 2 : 1;
  672. q->drop_next = control_law(now, q->count);
  673. }
  674. return r.p;
  675. }
  676. void Switch::aqm_dequeue(void *tPtr)
  677. {
  678. // Cycle through network-specific QoS control blocks
  679. for(std::map<uint64_t,NetworkQoSControlBlock*>::iterator nqcb(_netQueueControlBlock.begin());nqcb!=_netQueueControlBlock.end();) {
  680. if (!(*nqcb).second->_currEnqueuedPackets) {
  681. return;
  682. }
  683. uint64_t now = RR->node->now();
  684. TXQueueEntry *entryToEmit = nullptr;
  685. std::vector<ManagedQueue*> *currQueues = &((*nqcb).second->newQueues);
  686. std::vector<ManagedQueue*> *oldQueues = &((*nqcb).second->oldQueues);
  687. std::vector<ManagedQueue*> *inactiveQueues = &((*nqcb).second->inactiveQueues);
  688. _aqm_m.lock();
  689. // Attempt dequeue from queues in NEW list
  690. bool examiningNewQueues = true;
  691. while (currQueues->size()) {
  692. ManagedQueue *queueAtFrontOfList = currQueues->front();
  693. if (queueAtFrontOfList->byteCredit < 0) {
  694. queueAtFrontOfList->byteCredit += ZT_AQM_QUANTUM;
  695. // Move to list of OLD queues
  696. // DEBUG_INFO("moving q=%p from NEW to OLD list", queueAtFrontOfList);
  697. oldQueues->push_back(queueAtFrontOfList);
  698. currQueues->erase(currQueues->begin());
  699. } else {
  700. entryToEmit = CoDelDequeue(queueAtFrontOfList, examiningNewQueues, now);
  701. if (!entryToEmit) {
  702. // Move to end of list of OLD queues
  703. // DEBUG_INFO("moving q=%p from NEW to OLD list", queueAtFrontOfList);
  704. oldQueues->push_back(queueAtFrontOfList);
  705. currQueues->erase(currQueues->begin());
  706. }
  707. else {
  708. int len = entryToEmit->packet.payloadLength();
  709. queueAtFrontOfList->byteLength -= len;
  710. queueAtFrontOfList->byteCredit -= len;
  711. // Send the packet!
  712. queueAtFrontOfList->q.pop_front();
  713. send(tPtr, entryToEmit->packet, entryToEmit->encrypt, entryToEmit->flowId);
  714. (*nqcb).second->_currEnqueuedPackets--;
  715. }
  716. if (queueAtFrontOfList) {
  717. //DEBUG_INFO("dequeuing from q=%p, len=%lu in NEW list (byteCredit=%d)", queueAtFrontOfList, queueAtFrontOfList->q.size(), queueAtFrontOfList->byteCredit);
  718. }
  719. break;
  720. }
  721. }
  722. // Attempt dequeue from queues in OLD list
  723. examiningNewQueues = false;
  724. currQueues = &((*nqcb).second->oldQueues);
  725. while (currQueues->size()) {
  726. ManagedQueue *queueAtFrontOfList = currQueues->front();
  727. if (queueAtFrontOfList->byteCredit < 0) {
  728. queueAtFrontOfList->byteCredit += ZT_AQM_QUANTUM;
  729. oldQueues->push_back(queueAtFrontOfList);
  730. currQueues->erase(currQueues->begin());
  731. } else {
  732. entryToEmit = CoDelDequeue(queueAtFrontOfList, examiningNewQueues, now);
  733. if (!entryToEmit) {
  734. //DEBUG_INFO("moving q=%p from OLD to INACTIVE list", queueAtFrontOfList);
  735. // Move to inactive list of queues
  736. inactiveQueues->push_back(queueAtFrontOfList);
  737. currQueues->erase(currQueues->begin());
  738. }
  739. else {
  740. int len = entryToEmit->packet.payloadLength();
  741. queueAtFrontOfList->byteLength -= len;
  742. queueAtFrontOfList->byteCredit -= len;
  743. queueAtFrontOfList->q.pop_front();
  744. send(tPtr, entryToEmit->packet, entryToEmit->encrypt, entryToEmit->flowId);
  745. (*nqcb).second->_currEnqueuedPackets--;
  746. }
  747. if (queueAtFrontOfList) {
  748. //DEBUG_INFO("dequeuing from q=%p, len=%lu in OLD list (byteCredit=%d)", queueAtFrontOfList, queueAtFrontOfList->q.size(), queueAtFrontOfList->byteCredit);
  749. }
  750. break;
  751. }
  752. }
  753. nqcb++;
  754. _aqm_m.unlock();
  755. }
  756. }
  757. void Switch::removeNetworkQoSControlBlock(uint64_t nwid)
  758. {
  759. NetworkQoSControlBlock *nq = _netQueueControlBlock[nwid];
  760. if (nq) {
  761. _netQueueControlBlock.erase(nwid);
  762. delete nq;
  763. nq = NULL;
  764. }
  765. }
  766. void Switch::send(void *tPtr,Packet &packet,bool encrypt,int32_t flowId)
  767. {
  768. const Address dest(packet.destination());
  769. if (dest == RR->identity.address()) {
  770. return;
  771. }
  772. _recordOutgoingPacketMetrics(packet);
  773. if (!_trySend(tPtr,packet,encrypt,flowId)) {
  774. {
  775. Mutex::Lock _l(_txQueue_m);
  776. if (_txQueue.size() >= ZT_TX_QUEUE_SIZE) {
  777. _txQueue.pop_front();
  778. }
  779. _txQueue.push_back(TXQueueEntry(dest,RR->node->now(),packet,encrypt,flowId));
  780. }
  781. if (!RR->topology->getPeer(tPtr,dest))
  782. requestWhois(tPtr,RR->node->now(),dest);
  783. }
  784. }
  785. void Switch::requestWhois(void *tPtr,const int64_t now,const Address &addr)
  786. {
  787. if (addr == RR->identity.address())
  788. return;
  789. {
  790. Mutex::Lock _l(_lastSentWhoisRequest_m);
  791. int64_t &last = _lastSentWhoisRequest[addr];
  792. if ((now - last) < ZT_WHOIS_RETRY_DELAY)
  793. return;
  794. else last = now;
  795. }
  796. const SharedPtr<Peer> upstream(RR->topology->getUpstreamPeer());
  797. if (upstream) {
  798. int32_t flowId = ZT_QOS_NO_FLOW;
  799. Packet outp(upstream->address(),RR->identity.address(),Packet::VERB_WHOIS);
  800. addr.appendTo(outp);
  801. send(tPtr,outp,true,flowId);
  802. }
  803. }
  804. void Switch::doAnythingWaitingForPeer(void *tPtr,const SharedPtr<Peer> &peer)
  805. {
  806. {
  807. Mutex::Lock _l(_lastSentWhoisRequest_m);
  808. _lastSentWhoisRequest.erase(peer->address());
  809. }
  810. const int64_t now = RR->node->now();
  811. for(unsigned int ptr=0;ptr<ZT_RX_QUEUE_SIZE;++ptr) {
  812. RXQueueEntry *const rq = &(_rxQueue[ptr]);
  813. Mutex::Lock rql(rq->lock);
  814. if ((rq->timestamp)&&(rq->complete)) {
  815. if ((rq->frag0.tryDecode(RR,tPtr,rq->flowId))||((now - rq->timestamp) > ZT_RECEIVE_QUEUE_TIMEOUT))
  816. rq->timestamp = 0;
  817. }
  818. }
  819. {
  820. Mutex::Lock _l(_txQueue_m);
  821. for(std::list< TXQueueEntry >::iterator txi(_txQueue.begin());txi!=_txQueue.end();) {
  822. if (txi->dest == peer->address()) {
  823. if (_trySend(tPtr,txi->packet,txi->encrypt,txi->flowId)) {
  824. _txQueue.erase(txi++);
  825. } else {
  826. ++txi;
  827. }
  828. } else {
  829. ++txi;
  830. }
  831. }
  832. }
  833. }
  834. unsigned long Switch::doTimerTasks(void *tPtr,int64_t now)
  835. {
  836. const uint64_t timeSinceLastCheck = now - _lastCheckedQueues;
  837. if (timeSinceLastCheck < ZT_WHOIS_RETRY_DELAY)
  838. return (unsigned long)(ZT_WHOIS_RETRY_DELAY - timeSinceLastCheck);
  839. _lastCheckedQueues = now;
  840. std::vector<Address> needWhois;
  841. {
  842. Mutex::Lock _l(_txQueue_m);
  843. for(std::list< TXQueueEntry >::iterator txi(_txQueue.begin());txi!=_txQueue.end();) {
  844. if (_trySend(tPtr,txi->packet,txi->encrypt,txi->flowId)) {
  845. _txQueue.erase(txi++);
  846. } else if ((now - txi->creationTime) > ZT_TRANSMIT_QUEUE_TIMEOUT) {
  847. _txQueue.erase(txi++);
  848. } else {
  849. if (!RR->topology->getPeer(tPtr,txi->dest))
  850. needWhois.push_back(txi->dest);
  851. ++txi;
  852. }
  853. }
  854. }
  855. for(std::vector<Address>::const_iterator i(needWhois.begin());i!=needWhois.end();++i)
  856. requestWhois(tPtr,now,*i);
  857. for(unsigned int ptr=0;ptr<ZT_RX_QUEUE_SIZE;++ptr) {
  858. RXQueueEntry *const rq = &(_rxQueue[ptr]);
  859. Mutex::Lock rql(rq->lock);
  860. if ((rq->timestamp)&&(rq->complete)) {
  861. if ((rq->frag0.tryDecode(RR,tPtr,rq->flowId))||((now - rq->timestamp) > ZT_RECEIVE_QUEUE_TIMEOUT)) {
  862. rq->timestamp = 0;
  863. } else {
  864. const Address src(rq->frag0.source());
  865. if (!RR->topology->getPeer(tPtr,src))
  866. requestWhois(tPtr,now,src);
  867. }
  868. }
  869. }
  870. {
  871. Mutex::Lock _l(_lastUniteAttempt_m);
  872. Hashtable< _LastUniteKey,uint64_t >::Iterator i(_lastUniteAttempt);
  873. _LastUniteKey *k = (_LastUniteKey *)0;
  874. uint64_t *v = (uint64_t *)0;
  875. while (i.next(k,v)) {
  876. if ((now - *v) >= (ZT_MIN_UNITE_INTERVAL * 8))
  877. _lastUniteAttempt.erase(*k);
  878. }
  879. }
  880. {
  881. Mutex::Lock _l(_lastSentWhoisRequest_m);
  882. Hashtable< Address,int64_t >::Iterator i(_lastSentWhoisRequest);
  883. Address *a = (Address *)0;
  884. int64_t *ts = (int64_t *)0;
  885. while (i.next(a,ts)) {
  886. if ((now - *ts) > (ZT_WHOIS_RETRY_DELAY * 2))
  887. _lastSentWhoisRequest.erase(*a);
  888. }
  889. }
  890. return ZT_WHOIS_RETRY_DELAY;
  891. }
  892. bool Switch::_shouldUnite(const int64_t now,const Address &source,const Address &destination)
  893. {
  894. Mutex::Lock _l(_lastUniteAttempt_m);
  895. uint64_t &ts = _lastUniteAttempt[_LastUniteKey(source,destination)];
  896. if ((now - ts) >= ZT_MIN_UNITE_INTERVAL) {
  897. ts = now;
  898. return true;
  899. }
  900. return false;
  901. }
  902. bool Switch::_trySend(void *tPtr,Packet &packet,bool encrypt,int32_t flowId)
  903. {
  904. SharedPtr<Path> viaPath;
  905. const int64_t now = RR->node->now();
  906. const Address destination(packet.destination());
  907. const SharedPtr<Peer> peer(RR->topology->getPeer(tPtr,destination));
  908. if (peer) {
  909. if ((peer->bondingPolicy() == ZT_BOND_POLICY_BROADCAST)
  910. && (packet.verb() == Packet::VERB_FRAME || packet.verb() == Packet::VERB_EXT_FRAME)) {
  911. const SharedPtr<Peer> relay(RR->topology->getUpstreamPeer());
  912. Mutex::Lock _l(peer->_paths_m);
  913. for(int i=0;i<ZT_MAX_PEER_NETWORK_PATHS;++i) {
  914. if (peer->_paths[i].p && peer->_paths[i].p->alive(now)) {
  915. uint16_t userSpecifiedMtu = peer->_paths[i].p->mtu();
  916. _sendViaSpecificPath(tPtr,peer,peer->_paths[i].p, userSpecifiedMtu,now,packet,encrypt,flowId);
  917. }
  918. }
  919. return true;
  920. }
  921. else {
  922. viaPath = peer->getAppropriatePath(now,false,flowId);
  923. if (!viaPath) {
  924. peer->tryMemorizedPath(tPtr,now); // periodically attempt memorized or statically defined paths, if any are known
  925. const SharedPtr<Peer> relay(RR->topology->getUpstreamPeer());
  926. if ( (!relay) || (!(viaPath = relay->getAppropriatePath(now,false,flowId))) ) {
  927. if (!(viaPath = peer->getAppropriatePath(now,true,flowId)))
  928. return false;
  929. }
  930. }
  931. if (viaPath) {
  932. uint16_t userSpecifiedMtu = viaPath->mtu();
  933. _sendViaSpecificPath(tPtr,peer,viaPath,userSpecifiedMtu,now,packet,encrypt,flowId);
  934. return true;
  935. }
  936. }
  937. }
  938. return false;
  939. }
  940. void Switch::_sendViaSpecificPath(void *tPtr,SharedPtr<Peer> peer,SharedPtr<Path> viaPath,uint16_t userSpecifiedMtu, int64_t now,Packet &packet,bool encrypt,int32_t flowId)
  941. {
  942. unsigned int mtu = ZT_DEFAULT_PHYSMTU;
  943. uint64_t trustedPathId = 0;
  944. RR->topology->getOutboundPathInfo(viaPath->address(),mtu,trustedPathId);
  945. if (userSpecifiedMtu > 0) {
  946. mtu = userSpecifiedMtu;
  947. }
  948. unsigned int chunkSize = std::min(packet.size(),mtu);
  949. packet.setFragmented(chunkSize < packet.size());
  950. if (trustedPathId) {
  951. packet.setTrusted(trustedPathId);
  952. } else {
  953. if (!packet.isEncrypted()) {
  954. packet.armor(peer->key(),encrypt,peer->aesKeysIfSupported());
  955. }
  956. RR->node->expectReplyTo(packet.packetId());
  957. }
  958. peer->recordOutgoingPacket(viaPath, packet.packetId(), packet.payloadLength(), packet.verb(), flowId, now);
  959. if (viaPath->send(RR,tPtr,packet.data(),chunkSize,now)) {
  960. if (chunkSize < packet.size()) {
  961. // Too big for one packet, fragment the rest
  962. unsigned int fragStart = chunkSize;
  963. unsigned int remaining = packet.size() - chunkSize;
  964. unsigned int fragsRemaining = (remaining / (mtu - ZT_PROTO_MIN_FRAGMENT_LENGTH));
  965. if ((fragsRemaining * (mtu - ZT_PROTO_MIN_FRAGMENT_LENGTH)) < remaining)
  966. ++fragsRemaining;
  967. const unsigned int totalFragments = fragsRemaining + 1;
  968. for(unsigned int fno=1;fno<totalFragments;++fno) {
  969. chunkSize = std::min(remaining,(unsigned int)(mtu - ZT_PROTO_MIN_FRAGMENT_LENGTH));
  970. Packet::Fragment frag(packet,fragStart,chunkSize,fno,totalFragments);
  971. viaPath->send(RR,tPtr,frag.data(),frag.size(),now);
  972. fragStart += chunkSize;
  973. remaining -= chunkSize;
  974. }
  975. }
  976. }
  977. }
  978. void Switch::_recordOutgoingPacketMetrics(const Packet &p) {
  979. switch (p.verb()) {
  980. case Packet::VERB_NOP:
  981. Metrics::pkt_nop_out++;
  982. break;
  983. case Packet::VERB_HELLO:
  984. Metrics::pkt_hello_out++;
  985. break;
  986. case Packet::VERB_ERROR:
  987. Metrics::pkt_error_out++;
  988. break;
  989. case Packet::VERB_OK:
  990. Metrics::pkt_ok_out++;
  991. break;
  992. case Packet::VERB_WHOIS:
  993. Metrics::pkt_whois_out++;
  994. break;
  995. case Packet::VERB_RENDEZVOUS:
  996. Metrics::pkt_rendezvous_out++;
  997. break;
  998. case Packet::VERB_FRAME:
  999. Metrics::pkt_frame_out++;
  1000. break;
  1001. case Packet::VERB_EXT_FRAME:
  1002. Metrics::pkt_ext_frame_out++;
  1003. break;
  1004. case Packet::VERB_ECHO:
  1005. Metrics::pkt_echo_out++;
  1006. break;
  1007. case Packet::VERB_MULTICAST_LIKE:
  1008. Metrics::pkt_multicast_like_out++;
  1009. break;
  1010. case Packet::VERB_NETWORK_CREDENTIALS:
  1011. Metrics::pkt_network_credentials_out++;
  1012. break;
  1013. case Packet::VERB_NETWORK_CONFIG_REQUEST:
  1014. Metrics::pkt_network_config_request_out++;
  1015. break;
  1016. case Packet::VERB_NETWORK_CONFIG:
  1017. Metrics::pkt_network_config_out++;
  1018. break;
  1019. case Packet::VERB_MULTICAST_GATHER:
  1020. Metrics::pkt_multicast_gather_out++;
  1021. break;
  1022. case Packet::VERB_MULTICAST_FRAME:
  1023. Metrics::pkt_multicast_frame_out++;
  1024. break;
  1025. case Packet::VERB_PUSH_DIRECT_PATHS:
  1026. Metrics::pkt_push_direct_paths_out++;
  1027. break;
  1028. case Packet::VERB_ACK:
  1029. Metrics::pkt_ack_out++;
  1030. break;
  1031. case Packet::VERB_QOS_MEASUREMENT:
  1032. Metrics::pkt_qos_out++;
  1033. break;
  1034. case Packet::VERB_USER_MESSAGE:
  1035. Metrics::pkt_user_message_out++;
  1036. break;
  1037. case Packet::VERB_REMOTE_TRACE:
  1038. Metrics::pkt_remote_trace_out++;
  1039. break;
  1040. case Packet::VERB_PATH_NEGOTIATION_REQUEST:
  1041. Metrics::pkt_path_negotiation_request_out++;
  1042. break;
  1043. }
  1044. }
  1045. } // namespace ZeroTier