1 /*
2 * Copyright (c)2019 ZeroTier, Inc.
3 *
4 * Use of this software is governed by the Business Source License included
5 * in the LICENSE.TXT file in the project's root directory.
6 *
7 * Change Date: 2025-01-01
8 *
9 * On the date above, in accordance with the Business Source License, use
10 * of this software will be governed by version 2.0 of the Apache License.
11 */
12 /****/
13
14 #include "Constants.hpp"
15 #include "Topology.hpp"
16 #include "RuntimeEnvironment.hpp"
17 #include "Node.hpp"
18 #include "Network.hpp"
19 #include "NetworkConfig.hpp"
20 #include "Buffer.hpp"
21 #include "Switch.hpp"
22
23 namespace ZeroTier {
24
25 #define ZT_DEFAULT_WORLD_LENGTH 570
26 static const unsigned char ZT_DEFAULT_WORLD[ZT_DEFAULT_WORLD_LENGTH] = {0x01,0x00,0x00,0x00,0x00,0x08,0xea,0xc9,0x0a,0x00,0x00,0x01,0x78,0xcc,0x8e,0xf8,0xcb,0xb8,0xb3,0x88,0xa4,0x69,0x22,0x14,0x91,0xaa,0x9a,0xcd,0x66,0xcc,0x76,0x4c,0xde,0xfd,0x56,0x03,0x9f,0x10,0x67,0xae,0x15,0xe6,0x9c,0x6f,0xb4,0x2d,0x7b,0x55,0x33,0x0e,0x3f,0xda,0xac,0x52,0x9c,0x07,0x92,0xfd,0x73,0x40,0xa6,0xaa,0x21,0xab,0xa8,0xa4,0x89,0xfd,0xae,0xa4,0x4a,0x39,0xbf,0x2d,0x00,0x65,0x9a,0xc9,0xc8,0x18,0xeb,0x31,0xdc,0x40,0xa9,0xc7,0xb5,0xd2,0xf9,0x8e,0xd9,0x7b,0xf6,0x41,0x27,0x29,0x02,0xb6,0xb3,0x34,0x6f,0x56,0x16,0x11,0x45,0x82,0x44,0x55,0x85,0x78,0x79,0xb9,0x30,0xcb,0x01,0x51,0x15,0x49,0xf3,0x38,0x24,0xd8,0xd4,0x78,0x7d,0x77,0x23,0xda,0xc3,0x51,0x50,0x0b,0xe7,0xdf,0x5b,0x8f,0x72,0xdd,0x25,0x81,0xa5,0x0b,0x4a,0x36,0x01,0x46,0x85,0x95,0xbe,0x4d,0x5e,0xe6,0x3b,0x46,0xc2,0x9b,0x15,0x3c,0x43,0x8a,0x30,0xe0,0xa2,0xbf,0xba,0x1a,0x57,0xfc,0x98,0x7b,0x42,0x71,0xde,0x9c,0x53,0x6c,0x00,0x04,0x61,0xd2,0x94,0xb9,0xcb,0x00,0xe6,0x53,0xef,0x7a,0xd9,0x25,0x59,0x52,0xb7,0xc9,0xfc,0xa1,0x68,0x6d,0x3b,0x17,0xc6,0x10,0xb0,0x4e,0x6b,0x6c,0x82,0xd2,0xd3,0x7c,0xd3,0xa6,0xef,0xb2,0x56,0x3d,0x57,0x7f,0x81,0x22,0x24,0x37,0x62,0x02,0x09,0xe9,0x23,0x48,0xad,0x33,0x7b,0xd1,0x91,0xac,0x00,0xb7,0x49,0x2c,0xfd,0x55,0xce,0x0f,0xa0,0x36,0xd8,0xc5,0x62,0x83,0x00,0x02,0x04,0x32,0x07,0x49,0x22,0x27,0x09,0x06,0x20,0x01,0x49,0xf0,0xd0,0x02,0x00,0x06,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x02,0x27,0x09,0x77,0x8c,0xde,0x71,0x90,0x00,0x3f,0x66,0x81,0xa9,0x9e,0x5a,0xd1,0x89,0x5e,0x9f,0xba,0x33,0xe6,0x21,0x2d,0x44,0x54,0xe1,0x68,0xbc,0xec,0x71,0x12,0x10,0x1b,0xf0,0x00,0x95,0x6e,0xd8,0xe9,0x2e,0x42,0x89,0x2c,0xb6,0xf2,0xec,0x41,0x08,0x81,0xa8,0x4a,0xb1,0x9d,0xa5,0x0e,0x12,0x87,0xba,0x3d,0x92,0x6c,0x3a,0x1f,0x75,0x5c,0xcc,0xf2,0x99,0xa1,0x20,0x70,0x55,0x00,0x02,0x04,0x67,0xc3,0x67,0x42,0x27,0x09,0x06,0x26,0x05,0x98,0x80,0x04,0x00,0x00,0xc3,0x02,0x54,0xf2,0xbc,0xa1,0xf7,0x00,0x19,0x27,0x09,0x62,0xf8,0x65,0xae,0x71,0x00,0xe2,0x07,0x6c,0x57,0xde,0x87,0x0e,0x62,0x88,0xd7,0xd5,0xe7,0x40,0x44,0x08,0xb1,0x54,0x5e,0xfc,0xa3,0x7d,0x67,0xf7,0x7b,0x87,0xe9,0xe5,0x41,0x68,0xc2,0x5d,0x3e,0xf1,0xa9,0xab,0xf2,0x90,0x5e,0xa5,0xe7,0x85,0xc0,0x1d,0xff,0x23,0x88,0x7a,0xd4,0x23,0x2d,0x95,0xc7,0xa8,0xfd,0x2c,0x27,0x11,0x1a,0x72,0xbd,0x15,0x93,0x22,0xdc,0x00,0x02,0x04,0x32,0x07,0xfc,0x8a,0x27,0x09,0x06,0x20,0x01,0x49,0xf0,0xd0,0xdb,0x00,0x02,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x02,0x27,0x09,0x99,0x2f,0xcf,0x1d,0xb7,0x00,0x20,0x6e,0xd5,0x93,0x50,0xb3,0x19,0x16,0xf7,0x49,0xa1,0xf8,0x5d,0xff,0xb3,0xa8,0x78,0x7d,0xcb,0xf8,0x3b,0x8c,0x6e,0x94,0x48,0xd4,0xe3,0xea,0x0e,0x33,0x69,0x30,0x1b,0xe7,0x16,0xc3,0x60,0x93,0x44,0xa9,0xd1,0x53,0x38,0x50,0xfb,0x44,0x60,0xc5,0x0a,0xf4,0x33,0x22,0xbc,0xfc,0x8e,0x13,0xd3,0x30,0x1a,0x1f,0x10,0x03,0xce,0xb6,0x00,0x02,0x04,0xc3,0xb5,0xad,0x9f,0x27,0x09,0x06,0x2a,0x02,0x6e,0xa0,0xc0,0x24,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x27,0x09};
27
Topology(const RuntimeEnvironment * renv,void * tPtr)28 Topology::Topology(const RuntimeEnvironment *renv,void *tPtr) :
29 RR(renv),
30 _numConfiguredPhysicalPaths(0),
31 _amUpstream(false)
32 {
33 uint8_t tmp[ZT_WORLD_MAX_SERIALIZED_LENGTH];
34 uint64_t idtmp[2];
35 idtmp[0] = 0; idtmp[1] = 0;
36 int n = RR->node->stateObjectGet(tPtr,ZT_STATE_OBJECT_PLANET,idtmp,tmp,sizeof(tmp));
37 if (n > 0) {
38 try {
39 World cachedPlanet;
40 cachedPlanet.deserialize(Buffer<ZT_WORLD_MAX_SERIALIZED_LENGTH>(tmp,(unsigned int)n),0);
41 addWorld(tPtr,cachedPlanet,false);
42 } catch ( ... ) {} // ignore invalid cached planets
43 }
44
45 World defaultPlanet;
46 {
47 Buffer<ZT_DEFAULT_WORLD_LENGTH> wtmp(ZT_DEFAULT_WORLD,ZT_DEFAULT_WORLD_LENGTH);
48 defaultPlanet.deserialize(wtmp,0); // throws on error, which would indicate a bad static variable up top
49 }
50 addWorld(tPtr,defaultPlanet,false);
51 }
52
~Topology()53 Topology::~Topology()
54 {
55 Hashtable< Address,SharedPtr<Peer> >::Iterator i(_peers);
56 Address *a = (Address *)0;
57 SharedPtr<Peer> *p = (SharedPtr<Peer> *)0;
58 while (i.next(a,p))
59 _savePeer((void *)0,*p);
60 }
61
addPeer(void * tPtr,const SharedPtr<Peer> & peer)62 SharedPtr<Peer> Topology::addPeer(void *tPtr,const SharedPtr<Peer> &peer)
63 {
64 SharedPtr<Peer> np;
65 {
66 Mutex::Lock _l(_peers_m);
67 SharedPtr<Peer> &hp = _peers[peer->address()];
68 if (!hp)
69 hp = peer;
70 np = hp;
71 }
72 return np;
73 }
74
getPeer(void * tPtr,const Address & zta)75 SharedPtr<Peer> Topology::getPeer(void *tPtr,const Address &zta)
76 {
77 if (zta == RR->identity.address())
78 return SharedPtr<Peer>();
79
80 {
81 Mutex::Lock _l(_peers_m);
82 const SharedPtr<Peer> *const ap = _peers.get(zta);
83 if (ap)
84 return *ap;
85 }
86
87 try {
88 Buffer<ZT_PEER_MAX_SERIALIZED_STATE_SIZE> buf;
89 uint64_t idbuf[2]; idbuf[0] = zta.toInt(); idbuf[1] = 0;
90 int len = RR->node->stateObjectGet(tPtr,ZT_STATE_OBJECT_PEER,idbuf,buf.unsafeData(),ZT_PEER_MAX_SERIALIZED_STATE_SIZE);
91 if (len > 0) {
92 buf.setSize(len);
93 Mutex::Lock _l(_peers_m);
94 SharedPtr<Peer> &ap = _peers[zta];
95 if (ap)
96 return ap;
97 ap = Peer::deserializeFromCache(RR->node->now(),tPtr,buf,RR);
98 if (!ap) {
99 _peers.erase(zta);
100 }
101 return SharedPtr<Peer>();
102 }
103 } catch ( ... ) {} // ignore invalid identities or other strange failures
104
105 return SharedPtr<Peer>();
106 }
107
getIdentity(void * tPtr,const Address & zta)108 Identity Topology::getIdentity(void *tPtr,const Address &zta)
109 {
110 if (zta == RR->identity.address()) {
111 return RR->identity;
112 } else {
113 Mutex::Lock _l(_peers_m);
114 const SharedPtr<Peer> *const ap = _peers.get(zta);
115 if (ap)
116 return (*ap)->identity();
117 }
118 return Identity();
119 }
120
getUpstreamPeer()121 SharedPtr<Peer> Topology::getUpstreamPeer()
122 {
123 const int64_t now = RR->node->now();
124 unsigned int bestq = ~((unsigned int)0);
125 const SharedPtr<Peer> *best = (const SharedPtr<Peer> *)0;
126
127 Mutex::Lock _l2(_peers_m);
128 Mutex::Lock _l1(_upstreams_m);
129
130 for(std::vector<Address>::const_iterator a(_upstreamAddresses.begin());a!=_upstreamAddresses.end();++a) {
131 const SharedPtr<Peer> *p = _peers.get(*a);
132 if (p) {
133 const unsigned int q = (*p)->relayQuality(now);
134 if (q <= bestq) {
135 bestq = q;
136 best = p;
137 }
138 }
139 }
140
141 if (!best)
142 return SharedPtr<Peer>();
143 return *best;
144 }
145
isUpstream(const Identity & id) const146 bool Topology::isUpstream(const Identity &id) const
147 {
148 Mutex::Lock _l(_upstreams_m);
149 return (std::find(_upstreamAddresses.begin(),_upstreamAddresses.end(),id.address()) != _upstreamAddresses.end());
150 }
151
shouldAcceptWorldUpdateFrom(const Address & addr) const152 bool Topology::shouldAcceptWorldUpdateFrom(const Address &addr) const
153 {
154 Mutex::Lock _l(_upstreams_m);
155 if (std::find(_upstreamAddresses.begin(),_upstreamAddresses.end(),addr) != _upstreamAddresses.end())
156 return true;
157 for(std::vector< std::pair< uint64_t,Address> >::const_iterator s(_moonSeeds.begin());s!=_moonSeeds.end();++s) {
158 if (s->second == addr)
159 return true;
160 }
161 return false;
162 }
163
role(const Address & ztaddr) const164 ZT_PeerRole Topology::role(const Address &ztaddr) const
165 {
166 Mutex::Lock _l(_upstreams_m);
167 if (std::find(_upstreamAddresses.begin(),_upstreamAddresses.end(),ztaddr) != _upstreamAddresses.end()) {
168 for(std::vector<World::Root>::const_iterator i(_planet.roots().begin());i!=_planet.roots().end();++i) {
169 if (i->identity.address() == ztaddr)
170 return ZT_PEER_ROLE_PLANET;
171 }
172 return ZT_PEER_ROLE_MOON;
173 }
174 return ZT_PEER_ROLE_LEAF;
175 }
176
isProhibitedEndpoint(const Address & ztaddr,const InetAddress & ipaddr) const177 bool Topology::isProhibitedEndpoint(const Address &ztaddr,const InetAddress &ipaddr) const
178 {
179 Mutex::Lock _l(_upstreams_m);
180
181 // For roots the only permitted addresses are those defined. This adds just a little
182 // bit of extra security against spoofing, replaying, etc.
183 if (std::find(_upstreamAddresses.begin(),_upstreamAddresses.end(),ztaddr) != _upstreamAddresses.end()) {
184 for(std::vector<World::Root>::const_iterator r(_planet.roots().begin());r!=_planet.roots().end();++r) {
185 if (r->identity.address() == ztaddr) {
186 if (r->stableEndpoints.empty())
187 return false; // no stable endpoints specified, so allow dynamic paths
188 for(std::vector<InetAddress>::const_iterator e(r->stableEndpoints.begin());e!=r->stableEndpoints.end();++e) {
189 if (ipaddr.ipsEqual(*e))
190 return false;
191 }
192 }
193 }
194 for(std::vector<World>::const_iterator m(_moons.begin());m!=_moons.end();++m) {
195 for(std::vector<World::Root>::const_iterator r(m->roots().begin());r!=m->roots().end();++r) {
196 if (r->identity.address() == ztaddr) {
197 if (r->stableEndpoints.empty())
198 return false; // no stable endpoints specified, so allow dynamic paths
199 for(std::vector<InetAddress>::const_iterator e(r->stableEndpoints.begin());e!=r->stableEndpoints.end();++e) {
200 if (ipaddr.ipsEqual(*e))
201 return false;
202 }
203 }
204 }
205 }
206 return true;
207 }
208
209 return false;
210 }
211
addWorld(void * tPtr,const World & newWorld,bool alwaysAcceptNew)212 bool Topology::addWorld(void *tPtr,const World &newWorld,bool alwaysAcceptNew)
213 {
214 if ((newWorld.type() != World::TYPE_PLANET)&&(newWorld.type() != World::TYPE_MOON))
215 return false;
216
217 Mutex::Lock _l2(_peers_m);
218 Mutex::Lock _l1(_upstreams_m);
219
220 World *existing = (World *)0;
221 switch(newWorld.type()) {
222 case World::TYPE_PLANET:
223 existing = &_planet;
224 break;
225 case World::TYPE_MOON:
226 for(std::vector< World >::iterator m(_moons.begin());m!=_moons.end();++m) {
227 if (m->id() == newWorld.id()) {
228 existing = &(*m);
229 break;
230 }
231 }
232 break;
233 default:
234 return false;
235 }
236
237 if (existing) {
238 if (existing->shouldBeReplacedBy(newWorld))
239 *existing = newWorld;
240 else return false;
241 } else if (newWorld.type() == World::TYPE_MOON) {
242 if (alwaysAcceptNew) {
243 _moons.push_back(newWorld);
244 existing = &(_moons.back());
245 } else {
246 for(std::vector< std::pair<uint64_t,Address> >::iterator m(_moonSeeds.begin());m!=_moonSeeds.end();++m) {
247 if (m->first == newWorld.id()) {
248 for(std::vector<World::Root>::const_iterator r(newWorld.roots().begin());r!=newWorld.roots().end();++r) {
249 if (r->identity.address() == m->second) {
250 _moonSeeds.erase(m);
251 _moons.push_back(newWorld);
252 existing = &(_moons.back());
253 break;
254 }
255 }
256 if (existing)
257 break;
258 }
259 }
260 }
261 if (!existing)
262 return false;
263 } else {
264 return false;
265 }
266
267 try {
268 Buffer<ZT_WORLD_MAX_SERIALIZED_LENGTH> sbuf;
269 existing->serialize(sbuf,false);
270 uint64_t idtmp[2];
271 idtmp[0] = existing->id(); idtmp[1] = 0;
272 RR->node->stateObjectPut(tPtr,(existing->type() == World::TYPE_PLANET) ? ZT_STATE_OBJECT_PLANET : ZT_STATE_OBJECT_MOON,idtmp,sbuf.data(),sbuf.size());
273 } catch ( ... ) {}
274
275 _memoizeUpstreams(tPtr);
276
277 return true;
278 }
279
addMoon(void * tPtr,const uint64_t id,const Address & seed)280 void Topology::addMoon(void *tPtr,const uint64_t id,const Address &seed)
281 {
282 char tmp[ZT_WORLD_MAX_SERIALIZED_LENGTH];
283 uint64_t idtmp[2];
284 idtmp[0] = id; idtmp[1] = 0;
285 int n = RR->node->stateObjectGet(tPtr,ZT_STATE_OBJECT_MOON,idtmp,tmp,sizeof(tmp));
286 if (n > 0) {
287 try {
288 World w;
289 w.deserialize(Buffer<ZT_WORLD_MAX_SERIALIZED_LENGTH>(tmp,(unsigned int)n));
290 if ((w.type() == World::TYPE_MOON)&&(w.id() == id)) {
291 addWorld(tPtr,w,true);
292 return;
293 }
294 } catch ( ... ) {}
295 }
296
297 if (seed) {
298 Mutex::Lock _l(_upstreams_m);
299 if (std::find(_moonSeeds.begin(),_moonSeeds.end(),std::pair<uint64_t,Address>(id,seed)) == _moonSeeds.end())
300 _moonSeeds.push_back(std::pair<uint64_t,Address>(id,seed));
301 }
302 }
303
removeMoon(void * tPtr,const uint64_t id)304 void Topology::removeMoon(void *tPtr,const uint64_t id)
305 {
306 Mutex::Lock _l2(_peers_m);
307 Mutex::Lock _l1(_upstreams_m);
308
309 std::vector<World> nm;
310 for(std::vector<World>::const_iterator m(_moons.begin());m!=_moons.end();++m) {
311 if (m->id() != id) {
312 nm.push_back(*m);
313 } else {
314 uint64_t idtmp[2];
315 idtmp[0] = id; idtmp[1] = 0;
316 RR->node->stateObjectDelete(tPtr,ZT_STATE_OBJECT_MOON,idtmp);
317 }
318 }
319 _moons.swap(nm);
320
321 std::vector< std::pair<uint64_t,Address> > cm;
322 for(std::vector< std::pair<uint64_t,Address> >::const_iterator m(_moonSeeds.begin());m!=_moonSeeds.end();++m) {
323 if (m->first != id)
324 cm.push_back(*m);
325 }
326 _moonSeeds.swap(cm);
327
328 _memoizeUpstreams(tPtr);
329 }
330
doPeriodicTasks(void * tPtr,int64_t now)331 void Topology::doPeriodicTasks(void *tPtr,int64_t now)
332 {
333 {
334 Mutex::Lock _l1(_peers_m);
335 Mutex::Lock _l2(_upstreams_m);
336 Hashtable< Address,SharedPtr<Peer> >::Iterator i(_peers);
337 Address *a = (Address *)0;
338 SharedPtr<Peer> *p = (SharedPtr<Peer> *)0;
339 while (i.next(a,p)) {
340 if ( (!(*p)->isAlive(now)) && (std::find(_upstreamAddresses.begin(),_upstreamAddresses.end(),*a) == _upstreamAddresses.end()) ) {
341 _savePeer(tPtr,*p);
342 _peers.erase(*a);
343 }
344 }
345 }
346
347 {
348 Mutex::Lock _l(_paths_m);
349 Hashtable< Path::HashKey,SharedPtr<Path> >::Iterator i(_paths);
350 Path::HashKey *k = (Path::HashKey *)0;
351 SharedPtr<Path> *p = (SharedPtr<Path> *)0;
352 while (i.next(k,p)) {
353 if (p->references() <= 1)
354 _paths.erase(*k);
355 }
356 }
357 }
358
_memoizeUpstreams(void * tPtr)359 void Topology::_memoizeUpstreams(void *tPtr)
360 {
361 // assumes _upstreams_m and _peers_m are locked
362 _upstreamAddresses.clear();
363 _amUpstream = false;
364
365 for(std::vector<World::Root>::const_iterator i(_planet.roots().begin());i!=_planet.roots().end();++i) {
366 const Identity &id = i->identity;
367 if (id == RR->identity) {
368 _amUpstream = true;
369 } else if (std::find(_upstreamAddresses.begin(),_upstreamAddresses.end(),id.address()) == _upstreamAddresses.end()) {
370 _upstreamAddresses.push_back(id.address());
371 SharedPtr<Peer> &hp = _peers[id.address()];
372 if (!hp) {
373 hp = new Peer(RR,RR->identity,id);
374 }
375 }
376 }
377
378 for(std::vector<World>::const_iterator m(_moons.begin());m!=_moons.end();++m) {
379 for(std::vector<World::Root>::const_iterator i(m->roots().begin());i!=m->roots().end();++i) {
380 if (i->identity == RR->identity) {
381 _amUpstream = true;
382 } else if (std::find(_upstreamAddresses.begin(),_upstreamAddresses.end(),i->identity.address()) == _upstreamAddresses.end()) {
383 _upstreamAddresses.push_back(i->identity.address());
384 SharedPtr<Peer> &hp = _peers[i->identity.address()];
385 if (!hp)
386 hp = new Peer(RR,RR->identity,i->identity);
387 }
388 }
389 }
390
391 std::sort(_upstreamAddresses.begin(),_upstreamAddresses.end());
392 }
393
_savePeer(void * tPtr,const SharedPtr<Peer> & peer)394 void Topology::_savePeer(void *tPtr,const SharedPtr<Peer> &peer)
395 {
396 try {
397 Buffer<ZT_PEER_MAX_SERIALIZED_STATE_SIZE> buf;
398 peer->serializeForCache(buf);
399 uint64_t tmpid[2]; tmpid[0] = peer->address().toInt(); tmpid[1] = 0;
400 RR->node->stateObjectPut(tPtr,ZT_STATE_OBJECT_PEER,tmpid,buf.data(),buf.size());
401 } catch ( ... ) {} // sanity check, discard invalid entries
402 }
403
404 } // namespace ZeroTier
405