From 37931d8589359580c05baef64b6752315dccbe66 Mon Sep 17 00:00:00 2001 From: Adam Ierymenko Date: Wed, 4 Sep 2013 09:27:56 -0400 Subject: Multicast bandwidth accounting work in progress, and some config field changes and cleanup. --- node/BandwidthAccount.hpp | 132 +++++++++++++++++++++++++++ node/Constants.hpp | 20 ----- node/MulticastGroup.hpp | 2 +- node/Network.cpp | 47 +++++----- node/Network.hpp | 221 +++++++++++++++++++++++++++++++++++----------- node/PacketDecoder.cpp | 6 +- node/RateLimiter.hpp | 132 --------------------------- node/Utils.hpp | 27 ++++-- 8 files changed, 350 insertions(+), 237 deletions(-) create mode 100644 node/BandwidthAccount.hpp delete mode 100644 node/RateLimiter.hpp (limited to 'node') diff --git a/node/BandwidthAccount.hpp b/node/BandwidthAccount.hpp new file mode 100644 index 00000000..12c303e4 --- /dev/null +++ b/node/BandwidthAccount.hpp @@ -0,0 +1,132 @@ +/* + * ZeroTier One - Global Peer to Peer Ethernet + * Copyright (C) 2012-2013 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_BWACCOUNT_HPP +#define _ZT_BWACCOUNT_HPP + +#include + +#include "Constants.hpp" +#include "Utils.hpp" + +#ifdef __WINDOWS__ +#define fmin(a,b) (((a) <= (b)) ? (a) : (b)) +#define fmax(a,b) (((a) >= (b)) ? (a) : (b)) +#endif + +namespace ZeroTier { + +/** + * Bandwidth account used for rate limiting multicast groups + * + * This is used to apply a bank account model to multicast groups. Each + * multicast packet counts against a balance, which accrues at a given + * rate in bytes per second. Debt is possible. These parameters are + * configurable. + * + * A bank account model permits bursting behavior, which correctly models + * how OSes and apps typically use multicast. It's common for things to + * spew lots of multicast messages at once, wait a while, then do it + * again. A consistent bandwidth limit model doesn't fit. + */ +class BandwidthAccount +{ +public: + /** + * Rate of balance accrual and min/max + */ + struct Accrual + { + /** + * Rate of balance accrual in bytes per second + */ + double bytesPerSecond; + + /** + * Maximum balance that can ever be accrued (should be > 0.0) + */ + double maxBalance; + + /** + * Minimum balance, or maximum allowable "debt" (should be <= 0.0) + */ + double minBalance; + }; + + /** + * Create an uninitialized account + * + * init() must be called before this is used. + */ + BandwidthAccount() throw() {} + + /** + * Create and initialize + * + * @param preload Initial balance to place in account + */ + BandwidthAccount(double preload) + throw() + { + init(preload); + } + + /** + * Initialize or re-initialize account + * + * @param preload Initial balance to place in account + */ + inline void init(double preload) + throw() + { + _lastTime = Utils::nowf(); + _balance = preload; + } + + /** + * Update balance by accruing and then deducting + * + * @param ar Current rate of accrual + * @param deduct Amount to deduct, or 0.0 to just update + * @return New balance with deduction applied + */ + inline double update(const Accrual &ar,double deduct) + throw() + { + double lt = _lastTime; + double now = _lastTime = Utils::nowf(); + return (_balance = fmax(ar.minBalance,fmin(ar.maxBalance,(_balance + (ar.bytesPerSecond * (now - lt))) - deduct))); + } + +private: + double _lastTime; + double _balance; +}; + +} // namespace ZeroTier + +#endif diff --git a/node/Constants.hpp b/node/Constants.hpp index adff34ae..c41b7c69 100644 --- a/node/Constants.hpp +++ b/node/Constants.hpp @@ -282,26 +282,6 @@ error_no_ZT_ARCH_defined; */ #define ZT_MULTICAST_LOCAL_POLL_PERIOD 10000 -/** - * Default bytes per second limit for multicasts per peer on a network - */ -#define ZT_MULTICAST_DEFAULT_BYTES_PER_SECOND 100.0 - -/** - * Default balance preload for multicast rate limiters on a network - */ -#define ZT_MULTICAST_DEFAULT_RATE_PRELOAD 25000.0 - -/** - * Default maximum balance for multicast rate limiters - */ -#define ZT_MULTICAST_DEFAULT_RATE_MAX_BALANCE 25000.0 - -/** - * Default minimum balance for multicast rate limiters (max debt) - */ -#define ZT_MULTICAST_DEFAULT_RATE_MIN_BALANCE -5000.0 - /** * Delay between scans of the topology active peer DB for peers that need ping */ diff --git a/node/MulticastGroup.hpp b/node/MulticastGroup.hpp index 9f2b111d..3c31756f 100644 --- a/node/MulticastGroup.hpp +++ b/node/MulticastGroup.hpp @@ -106,7 +106,7 @@ public: inline std::string toString() const { char buf[64]; - Utils::snprintf(buf,sizeof(buf),"%.2x:%.2x:%.2x:%.2x:%.2x:%.2x/%.8lx",(unsigned int)_mac.data[0],(unsigned int)_mac.data[1],(unsigned int)_mac.data[2],(unsigned int)_mac.data[3],(unsigned int)_mac.data[4],(unsigned int)_mac.data[5],(unsigned long)_adi); + Utils::snprintf(buf,sizeof(buf),"%.2x%.2x%.2x%.2x%.2x%.2x/%.8lx",(unsigned int)_mac.data[0],(unsigned int)_mac.data[1],(unsigned int)_mac.data[2],(unsigned int)_mac.data[3],(unsigned int)_mac.data[4],(unsigned int)_mac.data[5],(unsigned long)_adi); return std::string(buf); } diff --git a/node/Network.cpp b/node/Network.cpp index b66cc3b5..11e7c455 100644 --- a/node/Network.cpp +++ b/node/Network.cpp @@ -110,6 +110,9 @@ bool Network::Certificate::qualifyMembership(const Network::Certificate &mc) con return true; } +// A low default global rate, fast enough for something like ARP +const Network::MulticastRates::Rate Network::MulticastRates::GLOBAL_DEFAULT_RATE(256.0,-32.0,256.0,64.0); + const char *Network::statusString(const Status s) throw() { @@ -166,24 +169,31 @@ SharedPtr Network::newInstance(const RuntimeEnvironment *renv,uint64_t void Network::setConfiguration(const Network::Config &conf) { Mutex::Lock _l(_lock); - if ((conf.networkId() == _id)&&(conf.peerAddress() == _r->identity.address())) { // sanity check - //TRACE("network %.16llx got netconf:\n%s",(unsigned long long)_id,conf.toString().c_str()); - _configuration = conf; - _myCertificate = conf.certificateOfMembership(); - _lastConfigUpdate = Utils::now(); + try { + if (conf.networkId() == _id) { // sanity check + //TRACE("network %.16llx got netconf:\n%s",(unsigned long long)_id,conf.toString().c_str()); + _configuration = conf; + _myCertificate = conf.certificateOfMembership(); + _lastConfigUpdate = Utils::now(); - _tap->setIps(conf.staticAddresses()); - _tap->setDisplayName((std::string("ZeroTier One [") + conf.name() + "]").c_str()); + _tap->setIps(conf.staticAddresses()); + _tap->setDisplayName((std::string("ZeroTier One [") + conf.name() + "]").c_str()); - memset(_etWhitelist,0,sizeof(_etWhitelist)); - std::set wl(conf.etherTypes()); - for(std::set::const_iterator t(wl.begin());t!=wl.end();++t) - _etWhitelist[*t / 8] |= (unsigned char)(1 << (*t % 8)); + memset(_etWhitelist,0,sizeof(_etWhitelist)); + std::set wl(conf.etherTypes()); + for(std::set::const_iterator t(wl.begin());t!=wl.end();++t) + _etWhitelist[*t / 8] |= (unsigned char)(1 << (*t % 8)); - std::string confPath(_r->homePath + ZT_PATH_SEPARATOR_S + "networks.d" + ZT_PATH_SEPARATOR_S + toString() + ".conf"); - if (!Utils::writeFile(confPath.c_str(),conf.toString())) { - LOG("error: unable to write network configuration file at: %s",confPath.c_str()); + std::string confPath(_r->homePath + ZT_PATH_SEPARATOR_S + "networks.d" + ZT_PATH_SEPARATOR_S + toString() + ".conf"); + if (!Utils::writeFile(confPath.c_str(),conf.toString())) { + LOG("error: unable to write network configuration file at: %s",confPath.c_str()); + } } + } catch ( ... ) { + _configuration = Config(); + _myCertificate = Certificate(); + _lastConfigUpdate = 0; + LOG("unexpected exception handling config for network %.16llx, retrying fetch...",(unsigned long long)_id); } } @@ -275,7 +285,7 @@ void Network::clean() Network::Status Network::status() const { Mutex::Lock _l(_lock); - if (_configuration.containsAllFields()) + if (_configuration) return NETWORK_OK; return NETWORK_WAITING_FOR_FIRST_AUTOCONF; } @@ -302,11 +312,8 @@ void Network::_restoreState() std::string confs; if (Utils::readFile(confPath.c_str(),confs)) { try { - if (confs.length()) { - Config conf(confs); - if (conf.containsAllFields()) - setConfiguration(conf); - } + if (confs.length()) + setConfiguration(Config(confs)); } catch ( ... ) {} // ignore invalid config on disk, we will re-request } else { // If the conf file isn't present, "touch" it so we'll remember diff --git a/node/Network.hpp b/node/Network.hpp index 4c18d93d..6340c049 100644 --- a/node/Network.hpp +++ b/node/Network.hpp @@ -47,6 +47,7 @@ #include "Dictionary.hpp" #include "Identity.hpp" #include "InetAddress.hpp" +#include "BandwidthAccount.hpp" namespace ZeroTier { @@ -85,24 +86,10 @@ public: class Certificate : private Dictionary { public: - Certificate() - { - } - - Certificate(const char *s) : - Dictionary(s) - { - } - - Certificate(const std::string &s) : - Dictionary(s) - { - } - - inline std::string toString() const - { - return Dictionary::toString(); - } + Certificate() {} + Certificate(const char *s) : Dictionary(s) {} + Certificate(const std::string &s) : Dictionary(s) {} + inline std::string toString() const { return Dictionary::toString(); } inline void setNetworkId(uint64_t id) { @@ -193,58 +180,159 @@ public: }; /** - * A network configuration for a given node + * Preload and rates of accrual for multicast group bandwidth limits + * + * Key is multicast group in lower case hex format: MAC (without :s) / + * ADI (hex). Value is a comma-delimited list of: preload, min, max, + * rate of accrual for bandwidth accounts. A key called '*' indicates + * the default for unlisted groups. */ - class Config : private Dictionary + class MulticastRates : private Dictionary { public: - Config() + /** + * Preload and accrual parameter tuple + */ + struct Rate { - } + Rate() {} + Rate(double pl,double minr,double maxr,double bps) + { + preload = pl; + accrual.bytesPerSecond = bps; + accrual.maxBalance = maxr; + accrual.minBalance = minr; + } - Config(const char *s) : - Dictionary(s) - { - } + double preload; + BandwidthAccount::Accrual accrual; + }; + + MulticastRates() {} + MulticastRates(const char *s) : Dictionary(s) {} + MulticastRates(const std::string &s) : Dictionary(s) {} + inline std::string toString() const { return Dictionary::toString(); } + + /** + * A very minimal default rate, fast enough for ARP + */ + static const Rate GLOBAL_DEFAULT_RATE; - Config(const std::string &s) : - Dictionary(s) + /** + * @return Default rate, or GLOBAL_DEFAULT_RATE if not specified + */ + Rate defaultRate() const { + Rate r; + const_iterator dfl(find("*")); + if (dfl == end()) + return GLOBAL_DEFAULT_RATE; + return _toRate(dfl->second); } - inline bool containsAllFields() const + /** + * Get the rate for a given multicast group + * + * @param mg Multicast group + * @return Rate or default() rate if not specified + */ + Rate get(const MulticastGroup &mg) const { - return (contains("nwid")&&contains("peer")); + const_iterator r(find(mg.toString())); + if (r == end()) + return defaultRate(); + return _toRate(r->second); } - inline std::string toString() const + private: + static inline Rate _toRate(const std::string &s) { - return Dictionary::toString(); + char tmp[16384]; + Utils::scopy(tmp,sizeof(tmp),s.c_str()); + Rate r; + r.preload = 0.0; + r.accrual.bytesPerSecond = 0.0; + r.accrual.maxBalance = 0.0; + r.accrual.minBalance = 0.0; + char *saveptr = (char *)0; + unsigned int fn = 0; + for(char *f=Utils::stok(tmp,",",&saveptr);(f);f=Utils::stok((char *)0,",",&saveptr)) { + switch(fn++) { + case 0: + r.preload = Utils::strToDouble(f); + break; + case 1: + r.accrual.minBalance = Utils::strToDouble(f); + break; + case 2: + r.accrual.maxBalance = Utils::strToDouble(f); + break; + case 3: + r.accrual.bytesPerSecond = Utils::strToDouble(f); + break; + } + } + return r; } + }; + + /** + * A network configuration for a given node + * + * Configuration fields: + * + * nwid= (required) + * name=short name + * desc=long(er) description + * com=Certificate (serialized dictionary) + * mr=MulticastRates (serialized dictionary) + * o=open network? (1 or 0, default false if missing) + * et=ethertype whitelist (comma-delimited list of ethertypes in decimal) + * v4s=IPv4 static assignments / netmasks (comma-delimited) + * v6s=IPv6 static assignments / netmasks (comma-delimited) + */ + class Config : private Dictionary + { + public: + Config() {} + Config(const char *s) : Dictionary(s) {} + Config(const std::string &s) : Dictionary(s) {} + inline std::string toString() const { return Dictionary::toString(); } + + /** + * @return True if configuration is valid and contains required fields + */ + inline operator bool() const throw() { return (find("nwid") != end()); } + /** + * @return Network ID + * @throws std::invalid_argument Network ID field missing + */ inline uint64_t networkId() const throw(std::invalid_argument) { -#ifdef __WINDOWS__ - return _strtoui64(get("nwid").c_str(),(char **)0,16); -#else - return strtoull(get("nwid").c_str(),(char **)0,16); -#endif + return Utils::hexStrToU64(get("nwid").c_str()); } + /** + * Get this network's short name, or its ID in hex if unspecified + * + * @return Short name of this network (e.g. "earth") + */ inline std::string name() const { - if (contains("name")) - return get("name"); - char buf[32]; - Utils::snprintf(buf,sizeof(buf),"%.16llx",(unsigned long long)networkId()); - return std::string(buf); + const_iterator n(find("name")); + if (n == end()) + return get("nwid"); + return n->second; } - inline Address peerAddress() const - throw(std::invalid_argument) + /** + * @return Long description of network or empty string if not present + */ + inline std::string desc() const { - return Address(get("peer")); + return get("desc",std::string()); } /** @@ -258,12 +346,28 @@ public: else return Certificate(cm->second); } + /** + * @return Multicast rates for this network + */ + inline MulticastRates multicastRates() const + { + const_iterator mr(find("mr")); + if (mr == end()) + return MulticastRates(); + else return MulticastRates(mr->second); + } + /** * @return True if this is an open non-access-controlled network */ inline bool isOpen() const { - return (get("isOpen","0") == "1"); + const_iterator o(find("o")); + if (o == end()) + return false; + else if (!o->second.length()) + return false; + else return (o->second[0] == '1'); } /** @@ -274,10 +378,10 @@ public: char tmp[16384]; char *saveptr = (char *)0; std::set et; - if (!Utils::scopy(tmp,sizeof(tmp),get("etherTypes","").c_str())) - return et; // sanity check + if (!Utils::scopy(tmp,sizeof(tmp),get("et","").c_str())) + return et; // sanity check, packet can't really be that big for(char *f=Utils::stok(tmp,",",&saveptr);(f);f=Utils::stok((char *)0,",",&saveptr)) { - unsigned int t = Utils::stoui(f); + unsigned int t = Utils::strToUInt(f); if (t) et.insert(t); } @@ -290,10 +394,10 @@ public: inline std::set staticAddresses() const { std::set sa; - std::vector ips(Utils::split(get("ipv4Static","").c_str(),",","","")); + std::vector ips(Utils::split(get("v4s","").c_str(),",","","")); for(std::vector::const_iterator i(ips.begin());i!=ips.end();++i) sa.insert(InetAddress(*i)); - ips = Utils::split(get("ipv6Static","").c_str(),",","",""); + ips = Utils::split(get("v6s","").c_str(),",","",""); for(std::vector::const_iterator i(ips.begin());i!=ips.end();++i) sa.insert(InetAddress(*i)); return sa; @@ -462,6 +566,8 @@ public: Status status() const; /** + * Determine whether frames of a given ethernet type are allowed on this network + * * @param etherType Ethernet frame type * @return True if network permits this type */ @@ -475,17 +581,26 @@ public: else return ((_etWhitelist[etherType / 8] & (unsigned char)(1 << (etherType % 8))) != 0); } + inline bool updateAndCheckMulticastBalance(const Address &a,const MulticastGroup &mg,unsigned int bytes) + { + Mutex::Lock _l(_lock); + std::map< std::pair,BandwidthAccount >::iterator bal(_multicastRateAccounts.find(std::pair(a,mg))); + } + private: static void _CBhandleTapData(void *arg,const MAC &from,const MAC &to,unsigned int etherType,const Buffer<4096> &data); void _restoreState(); const RuntimeEnvironment *_r; - // Tap and tap multicast memberships + // Multicast bandwidth accounting for peers on this network + std::map< std::pair,BandwidthAccount > _multicastRateAccounts; + + // Tap and tap multicast memberships for this node on this network EthernetTap *_tap; std::set _multicastGroups; - // Membership certificates supplied by peers + // Membership certificates supplied by other peers on this network std::map _membershipCertificates; // Configuration from network master node diff --git a/node/PacketDecoder.cpp b/node/PacketDecoder.cpp index 18d8c4e2..9d8f0cd8 100644 --- a/node/PacketDecoder.cpp +++ b/node/PacketDecoder.cpp @@ -319,10 +319,8 @@ bool PacketDecoder::_doOK(const RuntimeEnvironment *_r,const SharedPtr &pe std::string dict((const char *)field(ZT_PROTO_VERB_NETWORK_CONFIG_REQUEST__OK__IDX_DICT,dictlen),dictlen); if (dict.length()) { Network::Config netconf(dict); - if ((netconf.networkId() == nw->id())&&(netconf.peerAddress() == _r->identity.address())) { // sanity check - LOG("got network configuration for network %.16llx from %s",(unsigned long long)nw->id(),source().toString().c_str()); - nw->setConfiguration(netconf); - } + LOG("got network configuration for network %.16llx from %s",(unsigned long long)nw->id(),source().toString().c_str()); + nw->setConfiguration(netconf); } } } break; diff --git a/node/RateLimiter.hpp b/node/RateLimiter.hpp deleted file mode 100644 index 59dd8d28..00000000 --- a/node/RateLimiter.hpp +++ /dev/null @@ -1,132 +0,0 @@ -/* - * ZeroTier One - Global Peer to Peer Ethernet - * Copyright (C) 2012-2013 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_RATELIMITER_HPP -#define _ZT_RATELIMITER_HPP - -#include - -#include "Constants.hpp" -#include "Utils.hpp" - -#ifdef __WINDOWS__ -#define fmin(a,b) (((a) <= (b)) ? (a) : (b)) -#define fmax(a,b) (((a) >= (b)) ? (a) : (b)) -#endif - -namespace ZeroTier { - -/** - * Data transfer accounting used for multicast groups - * - * This is used to apply a bank account model to multicast groups. Each - * multicast packet counts against a balance, which accrues at a given - * rate in bytes per second. Debt is possible. These parameters are - * configurable. - * - * A bank account model permits bursting behavior, which correctly models - * how OSes and apps typically use multicast. It's common for things to - * spew lots of multicast messages at once, wait a while, then do it - * again. A consistent bandwidth limit model doesn't fit. - */ -class RateLimiter -{ -public: - /** - * Rate and min/max to apply on rate limiter update - */ - struct Rate - { - /** - * Rate of balance accrual in bytes per second - */ - double bytesPerSecond; - - /** - * Maximum balance that can ever be accrued (should be > 0.0) - */ - double maxBalance; - - /** - * Minimum balance, or maximum allowable "debt" (should be <= 0.0) - */ - double minBalance; - }; - - /** - * Create an uninitialized rate limiter - * - * init() must be called before this is used. - */ - RateLimiter() throw() {} - - /** - * Create an initialize rate limiter - * - * @param preload Initial balance to place in account - */ - RateLimiter(double preload) - throw() - { - init(preload); - } - - /** - * Initialize or re-initialize rate limiter - * - * @param preload Initial balance to place in account - */ - inline void init(double preload) - throw() - { - _lastTime = Utils::nowf(); - _balance = preload; - } - - /** - * Update balance based on current clock and supplied rate - * - * @param lim Current limits in effect - * @param deduct Amount to deduct, or 0.0 to just update - * @return New balance with deduction applied - */ - inline double update(const Rate &r,double deduct) - throw() - { - double lt = _lastTime; - double now = _lastTime = Utils::nowf(); - return (_balance = fmax(r.minBalance,fmin(r.maxBalance,(_balance + (r.bytesPerSecond * (now - lt))) - deduct))); - } - -private: - double _lastTime; - double _balance; -}; - -} // namespace ZeroTier - -#endif diff --git a/node/Utils.hpp b/node/Utils.hpp index 0d40e370..15121e28 100644 --- a/node/Utils.hpp +++ b/node/Utils.hpp @@ -461,36 +461,49 @@ public: #endif } - // String to int converters (and hex string to int) - static inline unsigned int stoui(const char *s) + // String to number converters + static inline unsigned int strToUInt(const char *s) throw() { return (unsigned int)strtoul(s,(char **)0,10); } - static inline unsigned long stoul(const char *s) + static inline unsigned long strToULong(const char *s) throw() { return strtoul(s,(char **)0,10); } - static inline unsigned long long stoull(const char *s) + static inline unsigned long long strToU64(const char *s) throw() { +#ifdef __WINDOWS__ + return _strtoui64(s,(char **)0,10); +#else return strtoull(s,(char **)0,10); +#endif } - static inline unsigned int hstoui(const char *s) + static inline unsigned int hexStrToUInt(const char *s) throw() { return (unsigned int)strtoul(s,(char **)0,16); } - static inline unsigned long hstoul(const char *s) + static inline unsigned long hexStrToULong(const char *s) throw() { return strtoul(s,(char **)0,16); } - static inline unsigned long long hstoull(const char *s) + static inline unsigned long long hexStrToU64(const char *s) throw() { +#ifdef __WINDOWS__ + return _strtoui64(s,(char **)0,16); +#else return strtoull(s,(char **)0,16); +#endif + } + static inline double strToDouble(const char *s) + throw() + { + return strtod(s,(char **)0); } /** -- cgit v1.2.3