From f3128a18fee6745317cdf1918fe3c3901958b1de Mon Sep 17 00:00:00 2001 From: Adam Ierymenko Date: Wed, 25 Sep 2013 10:55:27 -0400 Subject: Work in progress... --- node/Multicaster.hpp | 121 ++++++++++++++++++--------------------------------- 1 file changed, 42 insertions(+), 79 deletions(-) (limited to 'node/Multicaster.hpp') diff --git a/node/Multicaster.hpp b/node/Multicaster.hpp index cd8b447e..b83e1f31 100644 --- a/node/Multicaster.hpp +++ b/node/Multicaster.hpp @@ -33,109 +33,61 @@ #include #include +#include #include #include #include "Constants.hpp" #include "Mutex.hpp" #include "MulticastGroup.hpp" -#include "Utils.hpp" #include "Address.hpp" namespace ZeroTier { /** - * Multicast propagation algorithm + * Multicast propagation algorithm core and database */ class Multicaster { public: - Multicaster() {} + Multicaster(); + ~Multicaster(); /** * Add or renew a peer's subscription to a multicast group * + * @param nwid Network ID * @param a Address that LIKEd * @param mg Multicast group * @param now Current time */ - inline void likesGroup(const Address &a,const MulticastGroup &mg,uint64_t now) - { - Mutex::Lock _l(_lock); - _SubInfo &si = _subscriptions[_Subscription(a,mg)]; - if (!si.lastLike) { // on first LIKE, we must add to _proximity[mg] - std::list< Address > &p = _proximity[mg]; - p.push_front(a); - si.proximitySlot = p.begin(); // list's iterators remain valid until erase() - } - si.lastLike = now; - } + void likesGroup(uint64_t nwid,const Address &a,const MulticastGroup &mg,uint64_t now); /** * Bring a peer closer in terms of propagation priority * + * @param nwid Network ID * @param a Address to bring closer (e.g. due to unicast message) * @param now Current time */ - inline void bringCloser(const Address &a) - { - Mutex::Lock _l(_lock); - - // _subscriptions contains pairs of , so we can - // easily iterate through all subscriptions for a given address by - // starting with the default all-zero MulticastGroup() as lower bound - // and stopping when we're not looking at the right address anymore. - // Then we can look up _proximity and rapidly splice() the list using - // the saved iterator in _SubInfo. - std::map< _Subscription,_SubInfo >::iterator s(_subscriptions.lower_bound(_Subscription(a,MulticastGroup()))); - while ((s != _subscriptions.end())&&(s->first.first == a)) { - std::map< MulticastGroup,std::list< Address > >::iterator p(_proximity.find(s->first.second)); - if (s->second.proximitySlot != p->second.begin()) - p->second.splice(p->second.begin(),p->second,s->second.proximitySlot); - ++s; - } - } + void bringCloser(uint64_t nwid,const Address &a); /** * Indicate that a peer reported that it GOT a multicast * * This only happens on magnet nodes for a propagation. * + * @param nwid Network ID * @param mcGuid Multicast GUID * @param peer Peer that GOT multicast * @param now Current time */ - inlien void got(const Address &peer,uint64_t mcGuid,uint64_t now) - { - Mutex::Lock _l(_lock); - std::pair< uint64_t,std::set
> &g = _got[mcGuid]; - g.first = now; - g.second.insert(peer); - } + void got(uint64_t nwid,const Address &peer,uint64_t mcGuid,uint64_t now); /** * Erase entries for expired LIKEs and GOT records */ - inline void clean(uint64_t now) - { - Mutex::Lock _l(_lock); - - for(std::map< uint64_t,std::pair< uint64_t,std::set
> >::iterator g(_got.begin());g!=_got.end();) { - if ((now - g->second.first) > ZT_MULTICAST_MAGNET_STATE_EXPIRE) - _got.erase(g++); - else ++g; - } - - for(std::map< _Subscription,_SubInfo >::iterator s(_subscriptions.begin());s!=_subscriptions.end();) { - if ((now - s->second.lastLike) > ZT_MULTICAST_LIKE_EXPIRE) { - std::map< MulticastGroup,std::list< Address > > p(_proximity.find(s->first.second)); - p->second.erase(s->second.proximitySlot); - if (p->second.empty()) - _proximity.erase(p); - _subscriptions.erase(s++); - } else ++s; - } - } + void clean(uint64_t now); /** * Pick next hops for a multicast by proximity @@ -143,36 +95,33 @@ public: * The function or function object must return true if more hops are desired * or false to stop finding new hops and return. * + * @param nwid Network ID * @param mg Multicast group * @param mcGuid Multicast message GUID (signer and signer unique ID) * @param nextHopFunc Function to call for each address, search stops if it returns false */ template - inline void getNextHops(const MulticastGroup &mg,uint64_t mcGuid,F nextHopFunc) + inline void getNextHops(uint64_t nwid,const MulticastGroup &mg,uint64_t mcGuid,F nextHopFunc) { Mutex::Lock _l(_lock); - std::map< uint64_t,std::pair< uint64_t,std::set< Address > > > g(_got.find(mcGuid)); - std::map< MulticastGroup,std::list< Address > > p(_proximity.find(mg)); - if (p != _proximity.end()) { - for(std::list< Address >::iterator a(p->second.begin());a!=p->second.end();++a) { - if ((g == _got.end())||(!g->second.second.count(*a))) { - if (!nextHopFunc(*a)) - break; - } + + std::map< uint64_t,_NetInfo >::iterator n(_nets.find(nwid)); + if (n == _nets.end()) + return; + std::map< MulticastGroup,std::list< Address > >::iterator p(n->second.proximity.find(mg)); + if (p == n->second.proximity.end()) + return; + std::map< uint64_t,std::pair< uint64_t,std::set< Address > > >::iterator g(n->second.got.find(mcGuid)); + + for(std::list< Address >::iterator a(p->second.begin());a!=p->second.end();++a) { + if ((g == n->second.got.end())||(!g->second.second.count(*a))) { + if (!nextHopFunc(*a)) + break; } } } private: - // GOTs by multicast GUID: time of last GOT, addresses that GOT - std::map< uint64_t,std::pair< uint64_t,std::set< Address > > > _got; - - // Peer proximity ordering for peers subscribed to each group - std::map< MulticastGroup,std::list< Address > > _proximity; - - // An address and multicast group tuple - typedef std::pair _Subscription; - // Information about a subscription struct _SubInfo { @@ -187,9 +136,23 @@ private: std::list< Address >::iterator proximitySlot; }; - // Peer subscriptions to multicast groups - std::map< _Subscription,_SubInfo > _subscriptions; + // An address and multicast group tuple + typedef std::pair _Subscription; + + // Multicast info for a given network + struct _NetInfo + { + // GOTs by multicast GUID: time of last GOT, addresses that GOT + std::map< uint64_t,std::pair< uint64_t,std::set< Address > > > got; + + // Peer proximity ordering for peers subscribed to each group + std::map< MulticastGroup,std::list< Address > > proximity; + + // Peer subscriptions to multicast groups + std::map< _Subscription,_SubInfo > subscriptions; + }; + std::map< uint64_t,_NetInfo > _nets; Mutex _lock; }; -- cgit v1.2.3