From cfd101c9b85b20e5911445998a6f040089e3e414 Mon Sep 17 00:00:00 2001 From: Adam Ierymenko Date: Fri, 4 Sep 2015 11:50:12 -0700 Subject: Add entries() to go with keys() for future use. --- node/Hashtable.hpp | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) (limited to 'node/Hashtable.hpp') diff --git a/node/Hashtable.hpp b/node/Hashtable.hpp index 5076751d..6f7541c4 100644 --- a/node/Hashtable.hpp +++ b/node/Hashtable.hpp @@ -30,6 +30,8 @@ #include #include +#include +#include namespace ZeroTier { @@ -196,6 +198,24 @@ public: return k; } + /** + * @return Vector of all entries (pairs of K,V) + */ + inline typename std::vector< std::pair > entries() + { + typename std::vector< std::pair > k; + if (_s) { + for(unsigned long i=0;i<_bc;++i) { + _Bucket *b = _t[i]; + while (b) { + k.push_back(std::pair(b->k,b->v)); + b = b->next; + } + } + } + return k; + } + /** * @param k Key * @return Pointer to value or NULL if not found -- cgit v1.2.3 From 3a959a7763b44ffcddce557167169150a28b9059 Mon Sep 17 00:00:00 2001 From: Adam Ierymenko Date: Fri, 4 Sep 2015 12:14:21 -0700 Subject: Swap out std::map<> for Hashtable<> for main peer database in Topology. (ongoing std::map-ectomy) --- node/Address.hpp | 14 +++++++++++--- node/Hashtable.hpp | 6 ++++-- node/Node.cpp | 5 +++-- node/Topology.cpp | 18 ++++++++++-------- node/Topology.hpp | 14 +++++++++----- 5 files changed, 37 insertions(+), 20 deletions(-) (limited to 'node/Hashtable.hpp') diff --git a/node/Address.hpp b/node/Address.hpp index 137e4f4f..0b38ec62 100644 --- a/node/Address.hpp +++ b/node/Address.hpp @@ -166,6 +166,15 @@ public: return _a; } + /** + * @return Hash code for use with Hashtable + */ + inline unsigned long hashCode() const + throw() + { + return (unsigned long)_a; + } + /** * @return Hexadecimal string */ @@ -197,11 +206,11 @@ public: /** * Check if this address is reserved - * + * * The all-zero null address and any address beginning with 0xff are * reserved. (0xff is reserved for future use to designate possibly * longer addresses, addresses based on IPv6 innards, etc.) - * + * * @return True if address is reserved and may not be used */ inline bool isReserved() const @@ -230,4 +239,3 @@ private: } // namespace ZeroTier #endif - diff --git a/node/Hashtable.hpp b/node/Hashtable.hpp index 6f7541c4..84b5be0e 100644 --- a/node/Hashtable.hpp +++ b/node/Hashtable.hpp @@ -183,10 +183,11 @@ public: /** * @return Vector of all keys */ - inline typename std::vector keys() + inline typename std::vector keys() const { typename std::vector k; if (_s) { + k.reserve(_s); for(unsigned long i=0;i<_bc;++i) { _Bucket *b = _t[i]; while (b) { @@ -201,10 +202,11 @@ public: /** * @return Vector of all entries (pairs of K,V) */ - inline typename std::vector< std::pair > entries() + inline typename std::vector< std::pair > entries() const { typename std::vector< std::pair > k; if (_s) { + k.reserve(_s); for(unsigned long i=0;i<_bc;++i) { _Bucket *b = _t[i]; while (b) { diff --git a/node/Node.cpp b/node/Node.cpp index 534c085d..c8c50d66 100644 --- a/node/Node.cpp +++ b/node/Node.cpp @@ -355,7 +355,8 @@ void Node::status(ZT1_NodeStatus *status) const ZT1_PeerList *Node::peers() const { - std::map< Address,SharedPtr > peers(RR->topology->allPeers()); + std::vector< std::pair< Address,SharedPtr > > peers(RR->topology->allPeers()); + std::sort(peers.begin(),peers.end()); char *buf = (char *)::malloc(sizeof(ZT1_PeerList) + (sizeof(ZT1_Peer) * peers.size())); if (!buf) @@ -364,7 +365,7 @@ ZT1_PeerList *Node::peers() const pl->peers = (ZT1_Peer *)(buf + sizeof(ZT1_PeerList)); pl->peerCount = 0; - for(std::map< Address,SharedPtr >::iterator pi(peers.begin());pi!=peers.end();++pi) { + for(std::vector< std::pair< Address,SharedPtr > >::iterator pi(peers.begin());pi!=peers.end();++pi) { ZT1_Peer *p = &(pl->peers[pl->peerCount++]); p->address = pi->second->address().toInt(); p->lastUnicastFrame = pi->second->lastUnicastFrame(); diff --git a/node/Topology.cpp b/node/Topology.cpp index b255080e..25a92acd 100644 --- a/node/Topology.cpp +++ b/node/Topology.cpp @@ -103,7 +103,7 @@ SharedPtr Topology::addPeer(const SharedPtr &peer) const uint64_t now = RR->node->now(); Mutex::Lock _l(_lock); - SharedPtr p(_activePeers.insert(std::pair< Address,SharedPtr >(peer->address(),peer)).first->second); + SharedPtr &p = _activePeers.set(peer->address(),peer); p->use(now); _saveIdentity(p->identity()); @@ -160,9 +160,9 @@ SharedPtr Topology::getBestRoot(const Address *avoid,unsigned int avoidCou if (++sna == _rootAddresses.end()) sna = _rootAddresses.begin(); // wrap around at end if (*sna != RR->identity.address()) { // pick one other than us -- starting from me+1 in sorted set order - std::map< Address,SharedPtr >::const_iterator p(_activePeers.find(*sna)); - if ((p != _activePeers.end())&&(p->second->hasActiveDirectPath(now))) { - bestRoot = p->second; + SharedPtr *p = _activePeers.get(*sna); + if ((p)&&((*p)->hasActiveDirectPath(now))) { + bestRoot = *p; break; } } @@ -249,10 +249,12 @@ bool Topology::isRoot(const Identity &id) const void Topology::clean(uint64_t now) { Mutex::Lock _l(_lock); - for(std::map< Address,SharedPtr >::iterator p(_activePeers.begin());p!=_activePeers.end();) { - if (((now - p->second->lastUsed()) >= ZT_PEER_IN_MEMORY_EXPIRATION)&&(std::find(_rootAddresses.begin(),_rootAddresses.end(),p->first) == _rootAddresses.end())) { - _activePeers.erase(p++); - } else ++p; + Hashtable< Address,SharedPtr >::Iterator i(_activePeers); + Address *a = (Address *)0; + SharedPtr *p = (SharedPtr *)0; + while (i.next(a,p)) + if (((now - (*p)->lastUsed()) >= ZT_PEER_IN_MEMORY_EXPIRATION)&&(std::find(_rootAddresses.begin(),_rootAddresses.end(),*a) == _rootAddresses.end())) { + _activePeers.erase(*a); } } diff --git a/node/Topology.hpp b/node/Topology.hpp index 1c5cca00..3066b50c 100644 --- a/node/Topology.hpp +++ b/node/Topology.hpp @@ -44,6 +44,7 @@ #include "Mutex.hpp" #include "InetAddress.hpp" #include "Dictionary.hpp" +#include "Hashtable.hpp" namespace ZeroTier { @@ -163,17 +164,20 @@ public: inline void eachPeer(F f) { Mutex::Lock _l(_lock); - for(std::map< Address,SharedPtr >::const_iterator p(_activePeers.begin());p!=_activePeers.end();++p) - f(*this,p->second); + Hashtable< Address,SharedPtr >::Iterator i(_activePeers); + Address *a = (Address *)0; + SharedPtr *p = (SharedPtr *)0; + while (i.next(a,p)) + f(*this,*p); } /** * @return All currently active peers by address */ - inline std::map< Address,SharedPtr > allPeers() const + inline std::vector< std::pair< Address,SharedPtr > > allPeers() const { Mutex::Lock _l(_lock); - return _activePeers; + return _activePeers.entries(); } /** @@ -190,7 +194,7 @@ private: const RuntimeEnvironment *RR; - std::map< Address,SharedPtr > _activePeers; + Hashtable< Address,SharedPtr > _activePeers; std::map< Identity,std::vector > _roots; std::vector< Address > _rootAddresses; std::vector< SharedPtr > _rootPeers; -- cgit v1.2.3 From 7b8ce1605781f14d909e0aa099455b86d738c60a Mon Sep 17 00:00:00 2001 From: Adam Ierymenko Date: Fri, 4 Sep 2015 13:42:19 -0700 Subject: Another std::map<> dies. --- node/Hashtable.hpp | 35 +++++++++++++++++++++++++++++++++++ node/Network.cpp | 21 ++++++++++++--------- node/Network.hpp | 3 ++- node/Peer.hpp | 1 + 4 files changed, 50 insertions(+), 10 deletions(-) (limited to 'node/Hashtable.hpp') diff --git a/node/Hashtable.hpp b/node/Hashtable.hpp index 84b5be0e..59a57726 100644 --- a/node/Hashtable.hpp +++ b/node/Hashtable.hpp @@ -199,6 +199,26 @@ public: return k; } + /** + * Append all keys (in unspecified order) to the supplied vector or list + * + * @param v Vector, list, or other compliant container + * @tparam Type of V (generally inferred) + */ + template + inline void appendKeys(C &v) const + { + if (_s) { + for(unsigned long i=0;i<_bc;++i) { + _Bucket *b = _t[i]; + while (b) { + v.push_back(b->k); + b = b->next; + } + } + } + } + /** * @return Vector of all entries (pairs of K,V) */ @@ -234,6 +254,21 @@ public: } inline const V *get(const K &k) const { return const_cast(this)->get(k); } + /** + * @param k Key to check + * @return True if key is present + */ + inline bool contains(const K &k) const + { + _Bucket *b = _t[_hc(k) % _bc]; + while (b) { + if (b->k == k) + return true; + b = b->next; + } + return false; + } + /** * @param k Key * @return True if value was present diff --git a/node/Network.cpp b/node/Network.cpp index 39042fab..8317cad9 100644 --- a/node/Network.cpp +++ b/node/Network.cpp @@ -147,7 +147,7 @@ bool Network::subscribedToMulticastGroup(const MulticastGroup &mg,bool includeBr if (std::binary_search(_myMulticastGroups.begin(),_myMulticastGroups.end(),mg)) return true; else if (includeBridgedGroups) - return (_multicastGroupsBehindMe.find(mg) != _multicastGroupsBehindMe.end()); + return _multicastGroupsBehindMe.contains(mg); else return false; } @@ -373,10 +373,14 @@ void Network::clean() } // Clean learned multicast groups if we haven't heard from them in a while - for(std::map::iterator mg(_multicastGroupsBehindMe.begin());mg!=_multicastGroupsBehindMe.end();) { - if ((now - mg->second) > (ZT_MULTICAST_LIKE_EXPIRE * 2)) - _multicastGroupsBehindMe.erase(mg++); - else ++mg; + { + Hashtable< MulticastGroup,uint64_t >::Iterator i(_multicastGroupsBehindMe); + MulticastGroup *mg = (MulticastGroup *)0; + uint64_t *ts = (uint64_t *)0; + while (i.next(mg,ts)) { + if ((now - *ts) > (ZT_MULTICAST_LIKE_EXPIRE * 2)) + _multicastGroupsBehindMe.erase(*mg); + } } } @@ -408,8 +412,8 @@ void Network::learnBridgeRoute(const MAC &mac,const Address &addr) void Network::learnBridgedMulticastGroup(const MulticastGroup &mg,uint64_t now) { Mutex::Lock _l(_lock); - unsigned long tmp = (unsigned long)_multicastGroupsBehindMe.size(); - _multicastGroupsBehindMe[mg] = now; + const unsigned long tmp = (unsigned long)_multicastGroupsBehindMe.size(); + _multicastGroupsBehindMe.set(mg,now); if (tmp != _multicastGroupsBehindMe.size()) _announceMulticastGroups(); } @@ -510,8 +514,7 @@ std::vector Network::_allMulticastGroups() const std::vector mgs; mgs.reserve(_myMulticastGroups.size() + _multicastGroupsBehindMe.size() + 1); mgs.insert(mgs.end(),_myMulticastGroups.begin(),_myMulticastGroups.end()); - for(std::map< MulticastGroup,uint64_t >::const_iterator i(_multicastGroupsBehindMe.begin());i!=_multicastGroupsBehindMe.end();++i) - mgs.push_back(i->first); + _multicastGroupsBehindMe.appendKeys(mgs); if ((_config)&&(_config->enableBroadcast())) mgs.push_back(Network::BROADCAST); std::sort(mgs.begin(),mgs.end()); diff --git a/node/Network.hpp b/node/Network.hpp index d7320d46..47d2efc0 100644 --- a/node/Network.hpp +++ b/node/Network.hpp @@ -40,6 +40,7 @@ #include "Constants.hpp" #include "NonCopyable.hpp" +#include "Hashtable.hpp" #include "Address.hpp" #include "Mutex.hpp" #include "SharedPtr.hpp" @@ -359,7 +360,7 @@ private: volatile bool _portInitialized; std::vector< MulticastGroup > _myMulticastGroups; // multicast groups that we belong to including those behind us (updated periodically) - std::map< MulticastGroup,uint64_t > _multicastGroupsBehindMe; // multicast groups bridged to us and when we last saw activity on each + Hashtable< MulticastGroup,uint64_t > _multicastGroupsBehindMe; // multicast groups bridged to us and when we last saw activity on each std::map _remoteBridgeRoutes; // remote addresses where given MACs are reachable diff --git a/node/Peer.hpp b/node/Peer.hpp index 283e3f33..ef436cd9 100644 --- a/node/Peer.hpp +++ b/node/Peer.hpp @@ -40,6 +40,7 @@ #include "../include/ZeroTierOne.h" #include "RuntimeEnvironment.hpp" +#include "CertificateOfMembership.hpp" #include "RemotePath.hpp" #include "Address.hpp" #include "Utils.hpp" -- cgit v1.2.3 From 0ab3e49be91ed7a8723c8b58750aef77c01e8d08 Mon Sep 17 00:00:00 2001 From: Adam Ierymenko Date: Fri, 4 Sep 2015 14:44:22 -0700 Subject: Starting in on Switch... kill map in defrag queue, which will probably improve performance pretty decently under high load with lots of peers. --- node/Hashtable.hpp | 9 ++++++--- node/Switch.cpp | 49 ++++++++++++++++++++++++++----------------------- node/Switch.hpp | 4 +++- 3 files changed, 35 insertions(+), 27 deletions(-) (limited to 'node/Hashtable.hpp') diff --git a/node/Hashtable.hpp b/node/Hashtable.hpp index 59a57726..29c54838 100644 --- a/node/Hashtable.hpp +++ b/node/Hashtable.hpp @@ -372,9 +372,12 @@ private: } static inline unsigned long _hc(const uint64_t i) { - // NOTE: this is fine for network IDs, but might be bad for other kinds - // of IDs if they are not evenly or randomly distributed. - return (unsigned long)((i ^ (i >> 32)) * 2654435761ULL); + /* NOTE: this assumes that 'i' is evenly distributed, which is the case for + * packet IDs and network IDs -- the two use cases in ZT for uint64_t keys. + * These values are also greater than 0xffffffff so they'll map onto a full + * bucket count just fine no matter what happens. Normally you'd want to + * hash an integer key index in a hash table. */ + return (unsigned long)i; } inline void _grow() diff --git a/node/Switch.cpp b/node/Switch.cpp index 989f497a..3dcb7002 100644 --- a/node/Switch.cpp +++ b/node/Switch.cpp @@ -531,11 +531,14 @@ unsigned long Switch::doTimerTasks(uint64_t now) { // Time out packets that didn't get all their fragments. Mutex::Lock _l(_defragQueue_m); - for(std::map< uint64_t,DefragQueueEntry >::iterator i(_defragQueue.begin());i!=_defragQueue.end();) { - if ((now - i->second.creationTime) > ZT_FRAGMENTED_PACKET_RECEIVE_TIMEOUT) { + Hashtable< uint64_t,DefragQueueEntry >::Iterator i(_defragQueue); + uint64_t *packetId = (uint64_t *)0; + DefragQueueEntry *qe = (DefragQueueEntry *)0; + while (i.next(packetId,qe)) { + if ((now - qe->creationTime) > ZT_FRAGMENTED_PACKET_RECEIVE_TIMEOUT) { TRACE("incomplete fragmented packet %.16llx timed out, fragments discarded",i->first); - _defragQueue.erase(i++); - } else ++i; + _defragQueue.erase(*packetId); + } } } @@ -577,32 +580,31 @@ void Switch::_handleRemotePacketFragment(const InetAddress &fromAddr,const void // seeing a Packet::Fragment? Mutex::Lock _l(_defragQueue_m); - std::map< uint64_t,DefragQueueEntry >::iterator dqe(_defragQueue.find(pid)); + DefragQueueEntry &dq = _defragQueue[pid]; - if (dqe == _defragQueue.end()) { + if (!dq.creationTime) { // We received a Packet::Fragment without its head, so queue it and wait - DefragQueueEntry &dq = _defragQueue[pid]; dq.creationTime = RR->node->now(); dq.frags[fno - 1] = fragment; dq.totalFragments = tf; // total fragment count is known dq.haveFragments = 1 << fno; // we have only this fragment //TRACE("fragment (%u/%u) of %.16llx from %s",fno + 1,tf,pid,fromAddr.toString().c_str()); - } else if (!(dqe->second.haveFragments & (1 << fno))) { + } else if (!(dq.haveFragments & (1 << fno))) { // We have other fragments and maybe the head, so add this one and check - dqe->second.frags[fno - 1] = fragment; - dqe->second.totalFragments = tf; + dq.frags[fno - 1] = fragment; + dq.totalFragments = tf; //TRACE("fragment (%u/%u) of %.16llx from %s",fno + 1,tf,pid,fromAddr.toString().c_str()); - if (Utils::countBits(dqe->second.haveFragments |= (1 << fno)) == tf) { + if (Utils::countBits(dq.haveFragments |= (1 << fno)) == tf) { // We have all fragments -- assemble and process full Packet //TRACE("packet %.16llx is complete, assembling and processing...",pid); - SharedPtr packet(dqe->second.frag0); + SharedPtr packet(dq.frag0); for(unsigned int f=1;fappend(dqe->second.frags[f - 1].payload(),dqe->second.frags[f - 1].payloadLength()); - _defragQueue.erase(dqe); + packet->append(dq.frags[f - 1].payload(),dq.frags[f - 1].payloadLength()); + _defragQueue.erase(pid); // dq no longer valid after this if (!packet->tryDecode(RR)) { Mutex::Lock _l(_rxQueue_m); @@ -645,26 +647,27 @@ void Switch::_handleRemotePacketHead(const InetAddress &fromAddr,const void *dat uint64_t pid = packet->packetId(); Mutex::Lock _l(_defragQueue_m); - std::map< uint64_t,DefragQueueEntry >::iterator dqe(_defragQueue.find(pid)); + DefragQueueEntry &dq = _defragQueue[pid]; - if (dqe == _defragQueue.end()) { + if (!dq.creationTime) { // If we have no other fragments yet, create an entry and save the head - DefragQueueEntry &dq = _defragQueue[pid]; + dq.creationTime = RR->node->now(); dq.frag0 = packet; dq.totalFragments = 0; // 0 == unknown, waiting for Packet::Fragment dq.haveFragments = 1; // head is first bit (left to right) //TRACE("fragment (0/?) of %.16llx from %s",pid,fromAddr.toString().c_str()); - } else if (!(dqe->second.haveFragments & 1)) { + } else if (!(dq.haveFragments & 1)) { // If we have other fragments but no head, see if we are complete with the head - if ((dqe->second.totalFragments)&&(Utils::countBits(dqe->second.haveFragments |= 1) == dqe->second.totalFragments)) { + + if ((dq.totalFragments)&&(Utils::countBits(dq.haveFragments |= 1) == dq.totalFragments)) { // We have all fragments -- assemble and process full Packet //TRACE("packet %.16llx is complete, assembling and processing...",pid); // packet already contains head, so append fragments - for(unsigned int f=1;fsecond.totalFragments;++f) - packet->append(dqe->second.frags[f - 1].payload(),dqe->second.frags[f - 1].payloadLength()); - _defragQueue.erase(dqe); + for(unsigned int f=1;fappend(dq.frags[f - 1].payload(),dq.frags[f - 1].payloadLength()); + _defragQueue.erase(pid); // dq no longer valid after this if (!packet->tryDecode(RR)) { Mutex::Lock _l(_rxQueue_m); @@ -672,7 +675,7 @@ void Switch::_handleRemotePacketHead(const InetAddress &fromAddr,const void *dat } } else { // Still waiting on more fragments, so queue the head - dqe->second.frag0 = packet; + dq.frag0 = packet; } } // else this is a duplicate head, ignore } else { diff --git a/node/Switch.hpp b/node/Switch.hpp index ac85606e..a1b36014 100644 --- a/node/Switch.hpp +++ b/node/Switch.hpp @@ -45,6 +45,7 @@ #include "Network.hpp" #include "SharedPtr.hpp" #include "IncomingPacket.hpp" +#include "Hashtable.hpp" /* Ethernet frame types that might be relevant to us */ #define ZT_ETHERTYPE_IPV4 0x0800 @@ -199,13 +200,14 @@ private: // Packet defragmentation queue -- comes before RX queue in path struct DefragQueueEntry { + DefragQueueEntry() : creationTime(0),totalFragments(0),haveFragments(0) {} uint64_t creationTime; SharedPtr frag0; Packet::Fragment frags[ZT_MAX_PACKET_FRAGMENTS - 1]; unsigned int totalFragments; // 0 if only frag0 received, waiting for frags uint32_t haveFragments; // bit mask, LSB to MSB }; - std::map< uint64_t,DefragQueueEntry > _defragQueue; + Hashtable< uint64_t,DefragQueueEntry > _defragQueue; Mutex _defragQueue_m; // ZeroTier-layer RX queue of incoming packets in the process of being decoded -- cgit v1.2.3 From 3dba016a9354d9c50743877988c8d928d25f7a2b Mon Sep 17 00:00:00 2001 From: Adam Ierymenko Date: Fri, 4 Sep 2015 15:21:22 -0700 Subject: Almost done... very few std::map<>s remaining in any spot that matters. --- node/Hashtable.hpp | 5 +++-- node/Switch.cpp | 38 ++++++++++++++++++-------------------- node/Switch.hpp | 19 ++++++++++++++++++- 3 files changed, 39 insertions(+), 23 deletions(-) (limited to 'node/Hashtable.hpp') diff --git a/node/Hashtable.hpp b/node/Hashtable.hpp index 29c54838..bcc111e3 100644 --- a/node/Hashtable.hpp +++ b/node/Hashtable.hpp @@ -39,8 +39,9 @@ namespace ZeroTier { * A minimal hash table implementation for the ZeroTier core * * This is not a drop-in replacement for STL containers, and has several - * limitations. It's designed to be small and fast for use in the - * ZeroTier core. + * limitations. Keys can be uint64_t or an object, and if the latter they + * must implement a method called hashCode() that returns an unsigned long + * value that is evenly distributed. */ template class Hashtable diff --git a/node/Switch.cpp b/node/Switch.cpp index 7d6f8094..d5ee3e23 100644 --- a/node/Switch.cpp +++ b/node/Switch.cpp @@ -309,31 +309,18 @@ bool Switch::unite(const Address &p1,const Address &p2,bool force) const uint64_t now = RR->node->now(); - std::pair cg(Peer::findCommonGround(*p1p,*p2p,now)); - if (!(cg.first)) - return false; - - if (cg.first.ipScope() != cg.second.ipScope()) - return false; - - // Addresses are sorted in key for last unite attempt map for order - // invariant lookup: (p1,p2) == (p2,p1) - Array uniteKey; - if (p1 >= p2) { - uniteKey[0] = p2; - uniteKey[1] = p1; - } else { - uniteKey[0] = p1; - uniteKey[1] = p2; - } { Mutex::Lock _l(_lastUniteAttempt_m); - std::map< Array< Address,2 >,uint64_t >::const_iterator e(_lastUniteAttempt.find(uniteKey)); - if ((!force)&&(e != _lastUniteAttempt.end())&&((now - e->second) < ZT_MIN_UNITE_INTERVAL)) + uint64_t &luts = _lastUniteAttempt[_LastUniteKey(p1,p2)]; + if (((now - luts) < ZT_MIN_UNITE_INTERVAL)&&(!force)) return false; - else _lastUniteAttempt[uniteKey] = now; + luts = now; } + std::pair cg(Peer::findCommonGround(*p1p,*p2p,now)); + if ((!(cg.first))||(cg.first.ipScope() != cg.second.ipScope())) + return false; + TRACE("unite: %s(%s) <> %s(%s)",p1.toString().c_str(),cg.second.toString().c_str(),p2.toString().c_str(),cg.first.toString().c_str()); /* Tell P1 where to find P2 and vice versa, sending the packets to P1 and @@ -543,6 +530,17 @@ unsigned long Switch::doTimerTasks(uint64_t now) } } + { // Remove really old last unite attempt entries to keep table size controlled + Mutex::Lock _l(_lastUniteAttempt_m); + Hashtable< _LastUniteKey,uint64_t >::Iterator i(_lastUniteAttempt); + _LastUniteKey *k = (_LastUniteKey *)0; + uint64_t *v = (uint64_t *)0; + while (i.next(k,v)) { + if ((now - *v) >= (ZT_MIN_UNITE_INTERVAL * 16)) + _lastUniteAttempt.erase(*k); + } + } + return nextDelay; } diff --git a/node/Switch.hpp b/node/Switch.hpp index 0791681f..2d83b70c 100644 --- a/node/Switch.hpp +++ b/node/Switch.hpp @@ -235,7 +235,24 @@ private: Mutex _txQueue_m; // Tracks sending of VERB_RENDEZVOUS to relaying peers - std::map< Array< Address,2 >,uint64_t > _lastUniteAttempt; // key is always sorted in ascending order, for set-like behavior + struct _LastUniteKey + { + _LastUniteKey() : x(0),y(0) {} + _LastUniteKey(const Address &a1,const Address &a2) + { + if (a1 > a2) { + x = a2.toInt(); + y = a1.toInt(); + } else { + x = a1.toInt(); + y = a2.toInt(); + } + } + inline unsigned long hashCode() const throw() { return ((unsigned long)x ^ (unsigned long)y); } + inline bool operator==(const _LastUniteKey &k) const throw() { return ((x == k.x)&&(y == k.y)); } + uint64_t x,y; + }; + Hashtable< _LastUniteKey,uint64_t > _lastUniteAttempt; // key is always sorted in ascending order, for set-like behavior Mutex _lastUniteAttempt_m; // Active attempts to contact remote peers, including state of multi-phase NAT traversal -- cgit v1.2.3