ZeroTierOne/node/Topology.hpp

547 lines
14 KiB
C++
Raw Permalink Normal View History

/*
2019-08-23 16:23:39 +00:00
* Copyright (c)2019 ZeroTier, Inc.
*
2019-08-23 16:23:39 +00:00
* Use of this software is governed by the Business Source License included
* in the LICENSE.TXT file in the project's root directory.
*
2019-08-23 16:23:39 +00:00
* Change Date: 2023-01-01
*
2019-08-23 16:23:39 +00:00
* On the date above, in accordance with the Business Source License, use
* of this software will be governed by version 2.0 of the Apache License.
*/
2019-08-23 16:23:39 +00:00
/****/
#ifndef ZT_TOPOLOGY_HPP
#define ZT_TOPOLOGY_HPP
#include <stdio.h>
#include <string.h>
2013-09-17 19:53:59 +00:00
#include <vector>
#include <stdexcept>
#include <algorithm>
2015-10-13 15:49:36 +00:00
#include <utility>
#include <set>
#include "Constants.hpp"
#include "../include/ZeroTierOne.h"
#include "Address.hpp"
#include "Identity.hpp"
#include "Peer.hpp"
#include "Path.hpp"
#include "Mutex.hpp"
#include "InetAddress.hpp"
#include "Hashtable.hpp"
#include "Locator.hpp"
2019-08-21 21:36:56 +00:00
#include "SharedPtr.hpp"
#include "ScopedPtr.hpp"
namespace ZeroTier {
class RuntimeEnvironment;
/**
* Database of network topology
*/
class Topology
{
private:
2019-09-16 21:51:02 +00:00
struct _RootRankingFunction
{
ZT_ALWAYS_INLINE _RootRankingFunction() : bestRoot(),bestRootLatency(0xffff) {}
ZT_ALWAYS_INLINE bool operator()(const SharedPtr<Peer> &peer,const std::vector<InetAddress> &phy)
{
const unsigned int lat = peer->latency(now);
if ((!bestRoot)||((lat <= bestRootLatency)&&(peer->getAppropriatePath(now,false)))) {
bestRoot = peer;
bestRootLatency = lat;
}
return true;
}
int64_t now;
SharedPtr<Peer> bestRoot;
unsigned int bestRootLatency;
};
2019-09-17 01:03:17 +00:00
ZT_ALWAYS_INLINE void _updateDynamicRootIdentities()
{
2019-09-26 20:35:56 +00:00
// assumes _roots_l is locked
_rootIdentities.clear();
Hashtable< Str,Locator >::Iterator i(_roots);
2019-09-17 01:03:17 +00:00
Str *k = (Str *)0;
Locator *v = (Locator *)0;
while (i.next(k,v)) {
2019-09-19 16:47:12 +00:00
if (*v)
2019-09-26 20:35:56 +00:00
_rootIdentities.set(v->id(),true);
2019-09-17 01:03:17 +00:00
}
}
public:
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE Topology(const RuntimeEnvironment *renv,const Identity &myId) :
RR(renv),
_myIdentity(myId),
2019-09-30 16:32:00 +00:00
_numConfiguredPhysicalPaths(0),
2019-09-26 20:35:56 +00:00
_peers(64),
_paths(128),
_roots(8),
_rootIdentities(8),
_lastUpdatedBestRoot(0) {}
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE ~Topology() {}
/**
* Add a peer to database
*
* This will not replace existing peers. In that case the existing peer
* record is returned.
*
* @param tPtr Thread pointer to be handed through to any callbacks called as a result of this call
* @param peer Peer to add
* @return New or existing peer (should replace 'peer')
*/
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE SharedPtr<Peer> add(const SharedPtr<Peer> &peer)
{
SharedPtr<Peer> np;
{
Mutex::Lock _l(_peers_l);
SharedPtr<Peer> &hp = _peers[peer->address()];
if (!hp)
hp = peer;
np = hp;
}
return np;
}
/**
* Get a peer from its address
*
* @param tPtr Thread pointer to be handed through to any callbacks called as a result of this call
* @param zta ZeroTier address of peer
* @return Peer or NULL if not found
*/
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE SharedPtr<Peer> get(const Address &zta)
{
if (zta == _myIdentity.address())
return SharedPtr<Peer>();
Mutex::Lock l1(_peers_l);
2019-08-14 19:48:45 +00:00
const SharedPtr<Peer> *const ap = _peers.get(zta);
if (ap)
return *ap;
return SharedPtr<Peer>();
}
2017-07-06 17:25:36 +00:00
/**
* @param tPtr Thread pointer to be handed through to any callbacks called as a result of this call
* @param zta ZeroTier address of peer
* @return Identity or NULL identity if not found
*/
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE Identity getIdentity(void *tPtr,const Address &zta)
{
if (zta == _myIdentity.address()) {
return _myIdentity;
} else {
Mutex::Lock _l(_peers_l);
const SharedPtr<Peer> *const ap = _peers.get(zta);
if (ap)
return (*ap)->identity();
}
return Identity();
}
2019-08-14 19:48:45 +00:00
/**
* Get a Path object for a given local and remote physical address, creating if needed
*
2017-07-06 18:45:22 +00:00
* @param l Local socket
* @param r Remote address
* @return Pointer to canonicalized Path object
*/
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE SharedPtr<Path> getPath(const int64_t l,const InetAddress &r)
{
Mutex::Lock _l(_paths_l);
SharedPtr<Path> &p = _paths[Path::HashKey(l,r)];
if (!p)
p.set(new Path(l,r));
return p;
}
/**
* @param id Identity to check
* @return True if this identity corresponds to a root
*/
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE bool isRoot(const Identity &id) const
{
2019-09-26 20:35:56 +00:00
Mutex::Lock l(_roots_l);
return _rootIdentities.contains(id);
}
2019-08-14 19:48:45 +00:00
/**
* Do periodic tasks such as database cleanup
*/
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE void doPeriodicTasks(int64_t now)
{
{
Mutex::Lock _l1(_peers_l);
Hashtable< Address,SharedPtr<Peer> >::Iterator i(_peers);
Address *a = (Address *)0;
SharedPtr<Peer> *p = (SharedPtr<Peer> *)0;
while (i.next(a,p)) {
2019-08-22 20:06:08 +00:00
if (!(*p)->alive(now)) {
_peers.erase(*a);
}
}
}
{
Mutex::Lock _l(_paths_l);
Hashtable< Path::HashKey,SharedPtr<Path> >::Iterator i(_paths);
Path::HashKey *k = (Path::HashKey *)0;
SharedPtr<Path> *p = (SharedPtr<Path> *)0;
while (i.next(k,p)) {
if (p->references() <= 1)
_paths.erase(*k);
}
}
}
2015-10-26 19:41:08 +00:00
/**
* @param now Current time
2015-10-28 21:29:08 +00:00
* @return Number of peers with active direct paths
2015-10-26 19:41:08 +00:00
*/
2019-09-19 16:47:12 +00:00
inline unsigned long countActive(int64_t now) const
{
unsigned long cnt = 0;
Mutex::Lock _l(_peers_l);
Hashtable< Address,SharedPtr<Peer> >::Iterator i(const_cast<Topology *>(this)->_peers);
Address *a = (Address *)0;
SharedPtr<Peer> *p = (SharedPtr<Peer> *)0;
while (i.next(a,p)) {
2018-05-01 23:32:15 +00:00
const SharedPtr<Path> pp((*p)->getAppropriatePath(now,false));
if (pp)
++cnt;
}
return cnt;
}
2015-10-26 19:41:08 +00:00
/**
* Apply a function or function object to all peers
*
* This locks the peer map during execution, so calls to get() etc. during
* eachPeer() will deadlock.
*
* @param f Function to apply
* @tparam F Function or function object type
*/
template<typename F>
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE void eachPeer(F f)
{
Mutex::Lock l(_peers_l);
2015-10-02 00:09:01 +00:00
Hashtable< Address,SharedPtr<Peer> >::Iterator i(_peers);
Address *a = (Address *)0;
SharedPtr<Peer> *p = (SharedPtr<Peer> *)0;
while (i.next(a,p)) {
2019-09-17 02:58:21 +00:00
if (!f(*((const SharedPtr<Peer> *)p)))
break;
}
}
/**
* Apply a function or function object to all roots
*
* This locks the root list during execution but other operations
* are fine.
*
* @param f Function to apply f(peer,IPs)
* @tparam F function or function object type
*/
template<typename F>
2019-09-17 01:03:17 +00:00
ZT_ALWAYS_INLINE void eachRoot(F f)
{
2019-09-26 20:35:56 +00:00
Mutex::Lock l(_roots_l);
Hashtable< Str,Locator >::Iterator i(_roots);
Str *k = (Str *)0;
Locator *v = (Locator *)0;
while (i.next(k,v)) {
if (*v) {
for(std::vector<Identity>::const_iterator id(v->virt().begin());id!=v->virt().end();++id) {
const SharedPtr<Peer> *ap;
{
Mutex::Lock l2(_peers_l);
2019-09-26 20:35:56 +00:00
ap = _peers.get(id->address());
}
if (ap) {
2019-09-26 20:35:56 +00:00
if (!f(*ap,v->phy()))
return;
} else {
2019-09-26 20:35:56 +00:00
SharedPtr<Peer> p(new Peer(RR,_myIdentity,*id));
{
Mutex::Lock l2(_peers_l);
2019-09-26 20:35:56 +00:00
_peers.set(id->address(),p);
}
2019-09-26 20:35:56 +00:00
if (!f(p,v->phy()))
return;
}
}
}
}
}
/**
* @return Current best root (updated automatically each second)
*/
inline SharedPtr<Peer> root(const int64_t now)
{
Mutex::Lock l(_bestRoot_l);
if ((!_bestRoot)||((now - _lastUpdatedBestRoot) > 1000)) {
_lastUpdatedBestRoot = now;
_RootRankingFunction rrf;
rrf.now = now;
eachRoot(rrf);
_bestRoot = rrf.bestRoot;
}
return _bestRoot;
}
/**
2019-09-26 20:35:56 +00:00
* Iterate through all root names
2019-09-19 16:47:12 +00:00
*
* @param f Function of (Str,Locator)
*/
2019-09-19 16:47:12 +00:00
template<typename F>
2019-09-26 20:35:56 +00:00
ZT_ALWAYS_INLINE void eachRootName(F f) const
{
2019-09-26 20:35:56 +00:00
Mutex::Lock l(_roots_l);
2019-09-19 16:47:12 +00:00
Str *k = (Str *)0;
Locator *v = (Locator *)0;
2019-09-26 20:35:56 +00:00
Hashtable< Str,Locator >::Iterator i(const_cast<Topology *>(this)->_roots);
2019-09-19 16:47:12 +00:00
while (i.next(k,v)) {
if (!f(*k,*v))
break;
}
}
/**
2019-09-17 01:03:17 +00:00
* Set or update dynamic root if new locator is newer
*
2019-09-17 01:03:17 +00:00
* This does not check signatures or internal validity of the locator.
*
2019-09-26 20:35:56 +00:00
* @param name DNS name used to retrive root or simply the address for static roots
* @param latestLocator Latest locator
2019-09-19 16:47:12 +00:00
* @return True if locator is newer or if a new entry was created
*/
2019-09-26 20:35:56 +00:00
inline bool setRoot(const Str &name,const Locator &latestLocator)
{
2019-09-26 20:35:56 +00:00
Mutex::Lock l(_roots_l);
2019-09-19 16:47:12 +00:00
if (latestLocator) {
2019-09-26 20:35:56 +00:00
Locator &ll = _roots[name];
2019-09-19 16:47:12 +00:00
if (ll.timestamp() < latestLocator.timestamp()) {
ll = latestLocator;
_updateDynamicRootIdentities();
return true;
}
2019-09-26 20:35:56 +00:00
} else if (!_roots.contains(name)) {
_roots[name];
return true;
}
return false;
}
/**
* Remove a dynamic root entry
*/
2019-09-26 20:35:56 +00:00
inline void removeRoot(const Str &name)
{
2019-09-26 20:35:56 +00:00
Mutex::Lock l(_roots_l);
_roots.erase(name);
_updateDynamicRootIdentities();
}
/**
2019-09-19 16:47:12 +00:00
* @param Current time
* @return ZT_RootList as returned by the external CAPI
*/
inline ZT_RootList *apiRoots(const int64_t now) const
{
2019-09-30 23:12:08 +00:00
ScopedPtr< Buffer<65536> > lbuf(new Buffer<65536>());
2019-09-26 20:35:56 +00:00
Mutex::Lock l2(_roots_l);
2019-09-30 23:12:08 +00:00
ZT_RootList *rl = (ZT_RootList *)malloc(sizeof(ZT_RootList) + (sizeof(ZT_Root) * _roots.size()) + (256 * _roots.size()) + (65536 * _roots.size()));
if (!rl)
2019-09-19 16:47:12 +00:00
return nullptr;
2019-09-30 23:12:08 +00:00
char *nptr = ((char *)rl) + sizeof(ZT_RootList) + (sizeof(ZT_Root) * _roots.size());
uint8_t *lptr = ((uint8_t *)nptr) + (256 * _roots.size());
2019-09-19 16:47:12 +00:00
unsigned int c = 0;
2019-09-30 23:12:08 +00:00
Str *k = (Str *)0;
Locator *v = (Locator *)0;
Hashtable< Str,Locator >::Iterator i(const_cast<Topology *>(this)->_roots);
while (i.next(k,v)) {
Utils::scopy(nptr,256,k->c_str());
rl->roots[c].name = nptr;
nptr += 256;
lbuf->clear();
v->serialize(*lbuf);
memcpy(lptr,lbuf->unsafeData(),lbuf->size());
rl->roots[c].locator = lptr;
rl->roots[c].locatorSize = lbuf->size();
lptr += 65536;
++c;
2019-09-19 16:47:12 +00:00
}
rl->count = c;
return rl;
}
/**
* Get the best relay to a given address, which may or may not be a root
*
* @param now Current time
* @param toAddr Destination address
* @return Best current relay or NULL if none
*/
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE SharedPtr<Peer> findRelayTo(const int64_t now,const Address &toAddr)
{
// TODO: in the future this will check 'mesh-like' relays and if enabled consult LF for other roots (for if this is a root)
2019-09-17 01:03:17 +00:00
return root(now);
}
/**
* @param allPeers vector to fill with all current peers
*/
2019-09-17 01:03:17 +00:00
ZT_ALWAYS_INLINE void getAllPeers(std::vector< SharedPtr<Peer> > &allPeers) const
{
Mutex::Lock l(_peers_l);
allPeers.clear();
allPeers.reserve(_peers.size());
Hashtable< Address,SharedPtr<Peer> >::Iterator i(*(const_cast<Hashtable< Address,SharedPtr<Peer> > *>(&_peers)));
Address *a = (Address *)0;
SharedPtr<Peer> *p = (SharedPtr<Peer> *)0;
while (i.next(a,p)) {
allPeers.push_back(*p);
}
}
2017-09-01 23:25:34 +00:00
/**
* Get info about a path
*
* The supplied result variables are not modified if no special config info is found.
*
* @param physicalAddress Physical endpoint address
* @param mtu Variable set to MTU
* @param trustedPathId Variable set to trusted path ID
*/
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE void getOutboundPathInfo(const InetAddress &physicalAddress,unsigned int &mtu,uint64_t &trustedPathId)
2017-09-01 23:25:34 +00:00
{
for(unsigned int i=0,j=_numConfiguredPhysicalPaths;i<j;++i) {
if (_physicalPathConfig[i].first.containsAddress(physicalAddress)) {
trustedPathId = _physicalPathConfig[i].second.trustedPathId;
mtu = _physicalPathConfig[i].second.mtu;
return;
}
}
}
/**
* Get the payload MTU for an outbound physical path (returns default if not configured)
*
* @param physicalAddress Physical endpoint address
* @return MTU
*/
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE unsigned int getOutboundPathMtu(const InetAddress &physicalAddress)
2017-09-01 23:25:34 +00:00
{
for(unsigned int i=0,j=_numConfiguredPhysicalPaths;i<j;++i) {
if (_physicalPathConfig[i].first.containsAddress(physicalAddress))
return _physicalPathConfig[i].second.mtu;
}
return ZT_DEFAULT_PHYSMTU;
}
/**
* Get the outbound trusted path ID for a physical address, or 0 if none
*
* @param physicalAddress Physical address to which we are sending the packet
* @return Trusted path ID or 0 if none (0 is not a valid trusted path ID)
*/
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE uint64_t getOutboundPathTrust(const InetAddress &physicalAddress)
{
2017-09-01 23:25:34 +00:00
for(unsigned int i=0,j=_numConfiguredPhysicalPaths;i<j;++i) {
if (_physicalPathConfig[i].first.containsAddress(physicalAddress))
return _physicalPathConfig[i].second.trustedPathId;
}
return 0;
}
/**
* Check whether in incoming trusted path marked packet is valid
*
* @param physicalAddress Originating physical address
* @param trustedPathId Trusted path ID from packet (from MAC field)
*/
2019-09-12 17:37:26 +00:00
ZT_ALWAYS_INLINE bool shouldInboundPathBeTrusted(const InetAddress &physicalAddress,const uint64_t trustedPathId)
{
2017-09-01 23:25:34 +00:00
for(unsigned int i=0,j=_numConfiguredPhysicalPaths;i<j;++i) {
if ((_physicalPathConfig[i].second.trustedPathId == trustedPathId)&&(_physicalPathConfig[i].first.containsAddress(physicalAddress)))
return true;
}
return false;
}
/**
2017-09-01 23:25:34 +00:00
* Set or clear physical path configuration (called via Node::setPhysicalPathConfiguration)
*/
inline void setPhysicalPathConfiguration(const struct sockaddr_storage *pathNetwork,const ZT_PhysicalPathConfiguration *pathConfig)
{
if (!pathNetwork) {
_numConfiguredPhysicalPaths = 0;
} else {
std::map<InetAddress,ZT_PhysicalPathConfiguration> cpaths;
for(unsigned int i=0,j=_numConfiguredPhysicalPaths;i<j;++i)
cpaths[_physicalPathConfig[i].first] = _physicalPathConfig[i].second;
if (pathConfig) {
ZT_PhysicalPathConfiguration pc(*pathConfig);
if (pc.mtu <= 0)
pc.mtu = ZT_DEFAULT_PHYSMTU;
else if (pc.mtu < ZT_MIN_PHYSMTU)
pc.mtu = ZT_MIN_PHYSMTU;
else if (pc.mtu > ZT_MAX_PHYSMTU)
pc.mtu = ZT_MAX_PHYSMTU;
cpaths[*(reinterpret_cast<const InetAddress *>(pathNetwork))] = pc;
} else {
cpaths.erase(*(reinterpret_cast<const InetAddress *>(pathNetwork)));
}
unsigned int cnt = 0;
for(std::map<InetAddress,ZT_PhysicalPathConfiguration>::const_iterator i(cpaths.begin());((i!=cpaths.end())&&(cnt<ZT_MAX_CONFIGURABLE_PATHS));++i) {
_physicalPathConfig[cnt].first = i->first;
_physicalPathConfig[cnt].second = i->second;
++cnt;
}
_numConfiguredPhysicalPaths = cnt;
}
}
private:
const RuntimeEnvironment *const RR;
const Identity _myIdentity;
2017-09-01 23:25:34 +00:00
std::pair<InetAddress,ZT_PhysicalPathConfiguration> _physicalPathConfig[ZT_MAX_CONFIGURABLE_PATHS];
2019-08-06 21:46:13 +00:00
unsigned int _numConfiguredPhysicalPaths;
2015-10-02 00:09:01 +00:00
Hashtable< Address,SharedPtr<Peer> > _peers;
Hashtable< Path::HashKey,SharedPtr<Path> > _paths;
2019-09-26 20:35:56 +00:00
Hashtable< Str,Locator > _roots;
Hashtable< Identity,bool > _rootIdentities;
int64_t _lastUpdatedBestRoot;
SharedPtr<Peer> _bestRoot;
Mutex _peers_l;
Mutex _paths_l;
2019-09-26 20:35:56 +00:00
Mutex _roots_l;
Mutex _bestRoot_l;
};
} // namespace ZeroTier
#endif