From 6c87f9f765f524dd212c191511a79f52d01ee2c6 Mon Sep 17 00:00:00 2001 From: Adam Ierymenko Date: Wed, 24 Sep 2014 14:02:16 -0700 Subject: Rename MulticastTopology to Multicaster -- same name as old multicast controller but different code. More descriptive though. --- node/MulticastTopology.cpp | 132 ------------------------------------ node/MulticastTopology.hpp | 165 --------------------------------------------- node/Multicaster.cpp | 132 ++++++++++++++++++++++++++++++++++++ node/Multicaster.hpp | 165 +++++++++++++++++++++++++++++++++++++++++++++ node/Network.hpp | 8 +-- 5 files changed, 301 insertions(+), 301 deletions(-) delete mode 100644 node/MulticastTopology.cpp delete mode 100644 node/MulticastTopology.hpp create mode 100644 node/Multicaster.cpp create mode 100644 node/Multicaster.hpp (limited to 'node') diff --git a/node/MulticastTopology.cpp b/node/MulticastTopology.cpp deleted file mode 100644 index 1db1aa7a..00000000 --- a/node/MulticastTopology.cpp +++ /dev/null @@ -1,132 +0,0 @@ -/* - * ZeroTier One - Global Peer to Peer Ethernet - * Copyright (C) 2011-2014 ZeroTier Networks LLC - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - * - * -- - * - * ZeroTier may be used and distributed under the terms of the GPLv3, which - * are available at: http://www.gnu.org/licenses/gpl-3.0.html - * - * If you would like to embed ZeroTier into a commercial application or - * redistribute it in a modified binary form, please contact ZeroTier Networks - * LLC. Start here: http://www.zerotier.com/ - */ - -#include - -#include "Constants.hpp" -#include "MulticastTopology.hpp" -#include "Topology.hpp" - -namespace ZeroTier { - -MulticastTopology::MulticastTopology() -{ -} - -MulticastTopology::~MulticastTopology() -{ -} - -void MulticastTopology::add(const MulticastGroup &mg,const Address &learnedFrom,const Address &member) -{ -} - -void MulticastTopology::erase(const MulticastGroup &mg,const Address &member) -{ - Mutex::Lock _l(_groups_m); - std::map< MulticastGroup,MulticastGroupStatus >::iterator r(_groups.find(mg)); - if (r != _groups.end()) { - for(std::vector::iterator m(r->second.members.begin());m!=r->second.members.end();++m) { - if (m->address == member) { - r->second.members.erase(m); - if (r->second.members.empty()) - _groups.erase(r); - return; - } - } - } -} - -void send(uint64_t nwid,uint64_t now,const Address &self,const MulticastGroup &mg,const MAC &from,unsigned int etherType,const void *data,unsigned int len) -{ - Mutex::Lock _l(_groups_m); - std::map< MulticastGroup,MulticastGroupStatus >::iterator r(_groups.find(mg)); -} - -unsigned int MulticastTopology::shouldGather(const MulticastGroup &mg,uint64_t now,unsigned int limit,bool updateLastGatheredTimeOnNonzeroReturn) -{ - Mutex::Lock _l(_groups_m); - MulticastGroupStatus &gs = _groups[mg]; - if ((unsigned int)gs.members.size() >= limit) { - // We already caught our limit, don't need to go fishing any more. - return 0; - } else { - // Compute the delay between fishing expeditions from the fraction of the limit that we already have. - const uint64_t rateDelay = (uint64_t)ZT_MULTICAST_TOPOLOGY_GATHER_DELAY_MIN + (uint64_t)(((double)gs.members.size() / (double)limit) * (double)(ZT_MULTICAST_TOPOLOGY_GATHER_DELAY_MAX - ZT_MULTICAST_TOPOLOGY_GATHER_DELAY_MIN)); - - if ((now - gs.lastGatheredMembers) >= rateDelay) { - if (updateLastGatheredTimeOnNonzeroReturn) - gs.lastGatheredMembers = now; - return (limit - (unsigned int)gs.members.size()); - } else return 0; - } -} - -void MulticastTopology::clean(uint64_t now,const Topology &topology) -{ - Mutex::Lock _l(_groups_m); - for(std::map< MulticastGroup,MulticastGroupStatus >::iterator mm(_groups.begin());mm!=_groups.end();) { - std::vector::iterator reader(mm->second.members.begin()); - std::vector::iterator writer(mm->second.members.begin()); - unsigned int count = 0; - while (reader != mm->second.members.end()) { - if ((now - reader->timestamp) < ZT_MULTICAST_LIKE_EXPIRE) { - *writer = *reader; - - /* We rank in ascending order of most recent relevant activity. For peers we've learned - * about by direct LIKEs, we do this in order of their own activity. For indirectly - * acquired peers we do this minus a constant to place these categorically below directly - * learned peers. For peers with no active Peer record, we use the time we last learned - * about them minus one day (a large constant) to put these at the bottom of the list. - * List is sorted in ascending order of rank and multicasts are sent last-to-first. */ - if (writer->learnedFrom) { - SharedPtr p(topology.getPeer(writer->learnedFrom)); - if (p) - writer->rank = p->lastUnicastFrame() - ZT_MULTICAST_LIKE_EXPIRE; - else writer->rank = writer->timestamp - (86400000 + ZT_MULTICAST_LIKE_EXPIRE); - } else { - SharedPtr p(topology.getPeer(writer->address)); - if (p) - writer->rank = p->lastUnicastFrame(); - else writer->rank = writer->timestamp - 86400000; - } - - ++writer; - ++count; - } - ++reader; - } - - if (count) { - std::sort(mm->second.members.begin(),writer); // sorts in ascending order of rank - mm->second.members.resize(count); // trim off the ones we cut, after writer - ++mm; - } else _groups.erase(mm++); - } -} - -} // namespace ZeroTier diff --git a/node/MulticastTopology.hpp b/node/MulticastTopology.hpp deleted file mode 100644 index 0b330df3..00000000 --- a/node/MulticastTopology.hpp +++ /dev/null @@ -1,165 +0,0 @@ -/* - * ZeroTier One - Global Peer to Peer Ethernet - * Copyright (C) 2011-2014 ZeroTier Networks LLC - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - * - * -- - * - * ZeroTier may be used and distributed under the terms of the GPLv3, which - * are available at: http://www.gnu.org/licenses/gpl-3.0.html - * - * If you would like to embed ZeroTier into a commercial application or - * redistribute it in a modified binary form, please contact ZeroTier Networks - * LLC. Start here: http://www.zerotier.com/ - */ - -#ifndef ZT_MULTICASTTOPOLOGY_HPP -#define ZT_MULTICASTTOPOLOGY_HPP - -#include -#include - -#include -#include -#include - -#include "Constants.hpp" -#include "Address.hpp" -#include "MAC.hpp" -#include "MulticastGroup.hpp" -#include "OutboundMulticast.hpp" -#include "Switch.hpp" -#include "Utils.hpp" -#include "Mutex.hpp" - -namespace ZeroTier { - -class Topology; - -/** - * Database of known multicast peers within a network - */ -class MulticastTopology -{ -private: - struct MulticastGroupMember - { - MulticastGroupMember() {} - MulticastGroupMember(const Address &a,const Address &lf,uint64_t ts) : address(a),learnedFrom(lf),timestamp(ts) {} - - Address address; - Address learnedFrom; // NULL/0 for addresses directly learned from LIKE - uint64_t timestamp; // time of last LIKE or OK response to MULTICAST_LONELY - uint64_t rank; // used by sorting algorithm in clean() - - // for sorting in ascending order of rank - inline bool operator<(const MulticastGroupMember &m) const throw() { return (rank < m.rank); } - }; - - struct MulticastGroupStatus - { - MulticastGroupStatus() : lastGatheredMembers(0) {} - - uint64_t lastGatheredMembers; // time we last gathered members - std::vector members; // members of this group - std::list txQueue; // pending outbound multicasts - }; - -public: - MulticastTopology(); - ~MulticastTopology(); - - /** - * Add or update a member in a multicast group - * - * @param mg Multicast group - * @param learnedFrom Address from which we learned this member or NULL/0 Address if direct - * @param member New member address - */ - void add(const MulticastGroup &mg,const Address &learnedFrom,const Address &member); - - /** - * Erase a member from a multicast group (if present) - * - * @param mg Multicast group - * @param member Member to erase - */ - void erase(const MulticastGroup &mg,const Address &member); - - /** - * Send a multicast - * - * @param nwid Network ID - * @param now Current time - * @param sw Switch to use for sending packets - * @param self This node's address - * @param mg Multicast group - * @param from Source Ethernet MAC address - * @param etherType Ethernet frame type - * @param data Packet data - * @param len Length of packet data - */ - void send(uint64_t nwid,uint64_t now,const Switch &sw,const Address &self,const MulticastGroup &mg,const MAC &from,unsigned int etherType,const void *data,unsigned int len); - - /** - * @param mg Multicast group - * @return Tuple of: time we last gathered members (or 0 for never) and number of known members - */ - inline std::pair groupStatus(const MulticastGroup &mg) const - { - Mutex::Lock _l(_groups_m); - std::map< MulticastGroup,MulticastGroupStatus >::const_iterator r(_groups.find(mg)); - return ((r != _groups.end()) ? std::pair(r->second.lastGatheredMembers,r->second.members.size()) : std::pair(0,0)); - } - - /** - * Return the number of new members we should want to gather or 0 for none - * - * @param mg Multicast group - * @param now Current time - * @param limit The maximum number we want per multicast group on this network - * @param updateLastGatheredTimeOnNonzeroReturn If true, reset group's last gathered time to 'now' on non-zero return - */ - unsigned int shouldGather(const MulticastGroup &mg,uint64_t now,unsigned int limit,bool updateLastGatheredTimeOnNonzeroReturn); - - /** - * Update last gathered members time for a group - * - * @param mg Multicast group - * @param now Current time - */ - inline void gatheringMembersNow(const MulticastGroup &mg,uint64_t now) - { - Mutex::Lock _l(_groups_m); - _groups[mg].lastGatheredMembers = now; - } - - /** - * Clean up and resort database - * - * @param now Current time - * @param topology Global peer topology - * @param trim Trim lists to a maximum of this many members per multicast group - */ - void clean(uint64_t now,const Topology &topology); - -private: - std::map< MulticastGroup,MulticastGroupStatus > _groups; - Mutex _groups_m; -}; - -} // namespace ZeroTier - -#endif diff --git a/node/Multicaster.cpp b/node/Multicaster.cpp new file mode 100644 index 00000000..301b394c --- /dev/null +++ b/node/Multicaster.cpp @@ -0,0 +1,132 @@ +/* + * ZeroTier One - Global Peer to Peer Ethernet + * Copyright (C) 2011-2014 ZeroTier Networks LLC + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + * + * -- + * + * ZeroTier may be used and distributed under the terms of the GPLv3, which + * are available at: http://www.gnu.org/licenses/gpl-3.0.html + * + * If you would like to embed ZeroTier into a commercial application or + * redistribute it in a modified binary form, please contact ZeroTier Networks + * LLC. Start here: http://www.zerotier.com/ + */ + +#include + +#include "Constants.hpp" +#include "Multicaster.hpp" +#include "Topology.hpp" + +namespace ZeroTier { + +Multicaster::Multicaster() +{ +} + +Multicaster::~Multicaster() +{ +} + +void Multicaster::add(const MulticastGroup &mg,const Address &learnedFrom,const Address &member) +{ +} + +void Multicaster::erase(const MulticastGroup &mg,const Address &member) +{ + Mutex::Lock _l(_groups_m); + std::map< MulticastGroup,MulticastGroupStatus >::iterator r(_groups.find(mg)); + if (r != _groups.end()) { + for(std::vector::iterator m(r->second.members.begin());m!=r->second.members.end();++m) { + if (m->address == member) { + r->second.members.erase(m); + if (r->second.members.empty()) + _groups.erase(r); + return; + } + } + } +} + +void send(uint64_t nwid,uint64_t now,const Address &self,const MulticastGroup &mg,const MAC &from,unsigned int etherType,const void *data,unsigned int len) +{ + Mutex::Lock _l(_groups_m); + std::map< MulticastGroup,MulticastGroupStatus >::iterator r(_groups.find(mg)); +} + +unsigned int Multicaster::shouldGather(const MulticastGroup &mg,uint64_t now,unsigned int limit,bool updateLastGatheredTimeOnNonzeroReturn) +{ + Mutex::Lock _l(_groups_m); + MulticastGroupStatus &gs = _groups[mg]; + if ((unsigned int)gs.members.size() >= limit) { + // We already caught our limit, don't need to go fishing any more. + return 0; + } else { + // Compute the delay between fishing expeditions from the fraction of the limit that we already have. + const uint64_t rateDelay = (uint64_t)ZT_MULTICAST_TOPOLOGY_GATHER_DELAY_MIN + (uint64_t)(((double)gs.members.size() / (double)limit) * (double)(ZT_MULTICAST_TOPOLOGY_GATHER_DELAY_MAX - ZT_MULTICAST_TOPOLOGY_GATHER_DELAY_MIN)); + + if ((now - gs.lastGatheredMembers) >= rateDelay) { + if (updateLastGatheredTimeOnNonzeroReturn) + gs.lastGatheredMembers = now; + return (limit - (unsigned int)gs.members.size()); + } else return 0; + } +} + +void Multicaster::clean(uint64_t now,const Topology &topology) +{ + Mutex::Lock _l(_groups_m); + for(std::map< MulticastGroup,MulticastGroupStatus >::iterator mm(_groups.begin());mm!=_groups.end();) { + std::vector::iterator reader(mm->second.members.begin()); + std::vector::iterator writer(mm->second.members.begin()); + unsigned int count = 0; + while (reader != mm->second.members.end()) { + if ((now - reader->timestamp) < ZT_MULTICAST_LIKE_EXPIRE) { + *writer = *reader; + + /* We rank in ascending order of most recent relevant activity. For peers we've learned + * about by direct LIKEs, we do this in order of their own activity. For indirectly + * acquired peers we do this minus a constant to place these categorically below directly + * learned peers. For peers with no active Peer record, we use the time we last learned + * about them minus one day (a large constant) to put these at the bottom of the list. + * List is sorted in ascending order of rank and multicasts are sent last-to-first. */ + if (writer->learnedFrom) { + SharedPtr p(topology.getPeer(writer->learnedFrom)); + if (p) + writer->rank = p->lastUnicastFrame() - ZT_MULTICAST_LIKE_EXPIRE; + else writer->rank = writer->timestamp - (86400000 + ZT_MULTICAST_LIKE_EXPIRE); + } else { + SharedPtr p(topology.getPeer(writer->address)); + if (p) + writer->rank = p->lastUnicastFrame(); + else writer->rank = writer->timestamp - 86400000; + } + + ++writer; + ++count; + } + ++reader; + } + + if (count) { + std::sort(mm->second.members.begin(),writer); // sorts in ascending order of rank + mm->second.members.resize(count); // trim off the ones we cut, after writer + ++mm; + } else _groups.erase(mm++); + } +} + +} // namespace ZeroTier diff --git a/node/Multicaster.hpp b/node/Multicaster.hpp new file mode 100644 index 00000000..e8436ce9 --- /dev/null +++ b/node/Multicaster.hpp @@ -0,0 +1,165 @@ +/* + * ZeroTier One - Global Peer to Peer Ethernet + * Copyright (C) 2011-2014 ZeroTier Networks LLC + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + * + * -- + * + * ZeroTier may be used and distributed under the terms of the GPLv3, which + * are available at: http://www.gnu.org/licenses/gpl-3.0.html + * + * If you would like to embed ZeroTier into a commercial application or + * redistribute it in a modified binary form, please contact ZeroTier Networks + * LLC. Start here: http://www.zerotier.com/ + */ + +#ifndef ZT_MULTICASTER_HPP +#define ZT_MULTICASTER_HPP + +#include +#include + +#include +#include +#include + +#include "Constants.hpp" +#include "Address.hpp" +#include "MAC.hpp" +#include "MulticastGroup.hpp" +#include "OutboundMulticast.hpp" +#include "Switch.hpp" +#include "Utils.hpp" +#include "Mutex.hpp" + +namespace ZeroTier { + +class Topology; + +/** + * Database of known multicast peers within a network + */ +class Multicaster +{ +private: + struct MulticastGroupMember + { + MulticastGroupMember() {} + MulticastGroupMember(const Address &a,const Address &lf,uint64_t ts) : address(a),learnedFrom(lf),timestamp(ts) {} + + Address address; + Address learnedFrom; // NULL/0 for addresses directly learned from LIKE + uint64_t timestamp; // time of last LIKE or OK response to MULTICAST_LONELY + uint64_t rank; // used by sorting algorithm in clean() + + // for sorting in ascending order of rank + inline bool operator<(const MulticastGroupMember &m) const throw() { return (rank < m.rank); } + }; + + struct MulticastGroupStatus + { + MulticastGroupStatus() : lastGatheredMembers(0) {} + + uint64_t lastGatheredMembers; // time we last gathered members + std::vector members; // members of this group + std::list txQueue; // pending outbound multicasts + }; + +public: + Multicaster(); + ~Multicaster(); + + /** + * Add or update a member in a multicast group + * + * @param mg Multicast group + * @param learnedFrom Address from which we learned this member or NULL/0 Address if direct + * @param member New member address + */ + void add(const MulticastGroup &mg,const Address &learnedFrom,const Address &member); + + /** + * Erase a member from a multicast group (if present) + * + * @param mg Multicast group + * @param member Member to erase + */ + void erase(const MulticastGroup &mg,const Address &member); + + /** + * Send a multicast + * + * @param nwid Network ID + * @param now Current time + * @param sw Switch to use for sending packets + * @param self This node's address + * @param mg Multicast group + * @param from Source Ethernet MAC address + * @param etherType Ethernet frame type + * @param data Packet data + * @param len Length of packet data + */ + void send(uint64_t nwid,uint64_t now,const Switch &sw,const Address &self,const MulticastGroup &mg,const MAC &from,unsigned int etherType,const void *data,unsigned int len); + + /** + * @param mg Multicast group + * @return Tuple of: time we last gathered members (or 0 for never) and number of known members + */ + inline std::pair groupStatus(const MulticastGroup &mg) const + { + Mutex::Lock _l(_groups_m); + std::map< MulticastGroup,MulticastGroupStatus >::const_iterator r(_groups.find(mg)); + return ((r != _groups.end()) ? std::pair(r->second.lastGatheredMembers,r->second.members.size()) : std::pair(0,0)); + } + + /** + * Return the number of new members we should want to gather or 0 for none + * + * @param mg Multicast group + * @param now Current time + * @param limit The maximum number we want per multicast group on this network + * @param updateLastGatheredTimeOnNonzeroReturn If true, reset group's last gathered time to 'now' on non-zero return + */ + unsigned int shouldGather(const MulticastGroup &mg,uint64_t now,unsigned int limit,bool updateLastGatheredTimeOnNonzeroReturn); + + /** + * Update last gathered members time for a group + * + * @param mg Multicast group + * @param now Current time + */ + inline void gatheringMembersNow(const MulticastGroup &mg,uint64_t now) + { + Mutex::Lock _l(_groups_m); + _groups[mg].lastGatheredMembers = now; + } + + /** + * Clean up and resort database + * + * @param now Current time + * @param topology Global peer topology + * @param trim Trim lists to a maximum of this many members per multicast group + */ + void clean(uint64_t now,const Topology &topology); + +private: + std::map< MulticastGroup,MulticastGroupStatus > _groups; + Mutex _groups_m; +}; + +} // namespace ZeroTier + +#endif diff --git a/node/Network.hpp b/node/Network.hpp index 3849a453..e3f9ff63 100644 --- a/node/Network.hpp +++ b/node/Network.hpp @@ -51,7 +51,7 @@ #include "Identity.hpp" #include "InetAddress.hpp" #include "BandwidthAccount.hpp" -#include "MulticastTopology.hpp" +#include "Multicaster.hpp" #include "NetworkConfig.hpp" #include "CertificateOfMembership.hpp" #include "Thread.hpp" @@ -416,8 +416,8 @@ public: /** * @return Multicast topology for this network */ - inline MulticastTopology &mcTopology() { return _multicastTopology; } - inline const MulticastTopology &mcTopology() const { return _multicastTopology; } + inline Multicaster &mc() { return _multicaster; } + inline const Multicaster &mc() const { return _multicaster; } /** * Destroy this network @@ -453,7 +453,7 @@ private: std::set< 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 std::map< MulticastGroup,BandwidthAccount > _multicastRateAccounts; - MulticastTopology _multicastTopology; + Multicaster _multicaster; std::map _remoteBridgeRoutes; // remote addresses where given MACs are reachable -- cgit v1.2.3