Janitor.c 28 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717
  1. /* vim: set expandtab ts=4 sw=4: */
  2. /*
  3. * You may redistribute this program and/or modify it under the terms of
  4. * the GNU General Public License as published by the Free Software Foundation,
  5. * either version 3 of the License, or (at your option) any later version.
  6. *
  7. * This program is distributed in the hope that it will be useful,
  8. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  9. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  10. * GNU General Public License for more details.
  11. *
  12. * You should have received a copy of the GNU General Public License
  13. * along with this program. If not, see <https://www.gnu.org/licenses/>.
  14. */
  15. #include "crypto/AddressCalc.h"
  16. #include "crypto/random/Random.h"
  17. #include "dht/Address.h"
  18. #include "dht/dhtcore/Janitor.h"
  19. #include "dht/dhtcore/Node.h"
  20. #include "dht/dhtcore/NodeList.h"
  21. #include "dht/dhtcore/RumorMill.h"
  22. #include "dht/dhtcore/RouterModule.h"
  23. #include "dht/dhtcore/SearchRunner.h"
  24. #include "dht/dhtcore/ReplySerializer.h"
  25. #include "benc/Object.h"
  26. #include "memory/Allocator.h"
  27. #include "switch/LabelSplicer.h"
  28. #include "util/AddrTools.h"
  29. #include "util/AverageRoller.h"
  30. #include "util/Bits.h"
  31. #include "util/events/EventBase.h"
  32. #include "util/Hex.h"
  33. #include "util/events/Timeout.h"
  34. #include "util/events/Time.h"
  35. #include "util/Defined.h"
  36. #include <stdint.h>
  37. #include <stdbool.h>
  38. #define MAX_SEARCHES 10
  39. /** A path which has recently been probed will be quiet for blacklistPathForMilliseconds */
  40. struct Janitor_Blacklist
  41. {
  42. int64_t timeAdded;
  43. uint64_t path;
  44. };
  45. /**
  46. * The goal of this is to run searches in the local area of this node.
  47. * it searches for hashes every localMaintainenceSearchPeriod milliseconds.
  48. * it runs searches by picking hashes at random, if a hash is chosen and there is a
  49. * non-zero-reach node which services that space, it stops. This way it will run many
  50. * searches early on but as the number of known nodes increases, it begins to taper off.
  51. */
  52. struct Janitor_pvt
  53. {
  54. struct Janitor pub;
  55. struct RouterModule* routerModule;
  56. struct NodeStore* nodeStore;
  57. struct SearchRunner* searchRunner;
  58. struct Timeout* timeout;
  59. struct Log* logger;
  60. #define Janitor_pvt_blacklist_NUM 64
  61. struct Janitor_Blacklist blacklist[Janitor_pvt_blacklist_NUM];
  62. uint64_t timeOfNextGlobalMaintainence;
  63. struct Allocator* allocator;
  64. uint64_t timeOfNextSearchRepeat;
  65. uint64_t searchRepeatMilliseconds;
  66. struct EventBase* eventBase;
  67. struct Random* rand;
  68. /** Number of concurrent searches taking place. */
  69. int searches;
  70. Identity
  71. };
  72. struct Janitor_Search
  73. {
  74. struct Janitor_pvt* janitor;
  75. struct Address best;
  76. uint8_t target[16];
  77. struct Allocator* alloc;
  78. Identity
  79. };
  80. static bool isBlacklisted(struct Janitor_pvt* j, uint64_t path)
  81. {
  82. int64_t now = Time_currentTimeMilliseconds(j->eventBase);
  83. for (int i = 0; i < Janitor_pvt_blacklist_NUM; i++) {
  84. struct Janitor_Blacklist* qp = &j->blacklist[i];
  85. if (qp->path == path && now - qp->timeAdded < j->pub.blacklistPathForMilliseconds) {
  86. return true;
  87. }
  88. }
  89. return false;
  90. }
  91. static void blacklist(struct Janitor_pvt* j, uint64_t path)
  92. {
  93. int64_t now = Time_currentTimeMilliseconds(j->eventBase);
  94. int oldestIndex = 0;
  95. int64_t oldestTime = INT64_MAX;
  96. for (int i = 0; i < Janitor_pvt_blacklist_NUM; i++) {
  97. struct Janitor_Blacklist* qp = &j->blacklist[i];
  98. if (qp->path == path || now - qp->timeAdded > j->pub.blacklistPathForMilliseconds) {
  99. qp->timeAdded = now;
  100. qp->path = path;
  101. return;
  102. } else if (qp->timeAdded < oldestTime) {
  103. oldestIndex = i;
  104. oldestTime = qp->timeAdded;
  105. }
  106. }
  107. Log_debug(j->logger, "Replacing [%lld]ms old blacklist node because blacklist is full",
  108. (long long)(now - oldestTime));
  109. j->blacklist[oldestIndex].timeAdded = now;
  110. j->blacklist[oldestIndex].path = path;
  111. }
  112. static void responseCallback(struct RouterModule_Promise* promise,
  113. uint32_t lagMilliseconds,
  114. struct Address* from,
  115. Dict* result)
  116. {
  117. struct Janitor_Search* search = Identity_check((struct Janitor_Search*)promise->userData);
  118. if (from) {
  119. blacklist(search->janitor, from->path);
  120. Bits_memcpy(&search->best, from, sizeof(struct Address));
  121. return;
  122. }
  123. search->janitor->searches--;
  124. if (!search->best.path) {
  125. Log_debug(search->janitor->logger, "Search completed with no nodes found");
  126. }
  127. Allocator_free(search->alloc);
  128. }
  129. static void search(uint8_t target[16], struct Janitor_pvt* janitor)
  130. {
  131. if (janitor->searches >= MAX_SEARCHES) {
  132. Log_debug(janitor->logger, "Skipping search because 20 are in progress");
  133. return;
  134. }
  135. #ifdef Log_DEBUG
  136. uint8_t targetStr[40];
  137. AddrTools_printIp(targetStr, target);
  138. Log_debug(janitor->logger, "Beginning search for [%s]", targetStr);
  139. #endif
  140. struct Allocator* searchAlloc = Allocator_child(janitor->allocator);
  141. struct RouterModule_Promise* rp =
  142. SearchRunner_search(target, -1, -1, janitor->searchRunner, searchAlloc);
  143. if (!rp) {
  144. Log_debug(janitor->logger, "SearchRunner_search() returned NULL, probably full.");
  145. Allocator_free(searchAlloc);
  146. return;
  147. }
  148. janitor->searches++;
  149. struct Janitor_Search* search = Allocator_clone(rp->alloc, (&(struct Janitor_Search) {
  150. .janitor = janitor,
  151. .alloc = searchAlloc,
  152. }));
  153. Identity_set(search);
  154. Bits_memcpy(search->target, target, 16);
  155. rp->callback = responseCallback;
  156. rp->userData = search;
  157. }
  158. static void searchNoDupe(uint8_t target[Address_SEARCH_TARGET_SIZE], struct Janitor_pvt* janitor)
  159. {
  160. // See if we're already searching for this address.
  161. struct Allocator* seachListAlloc = Allocator_child(janitor->allocator);
  162. struct SearchRunner_SearchData* searchData;
  163. for (int i = 0; i < SearchRunner_DEFAULT_MAX_CONCURRENT_SEARCHES; i++) {
  164. searchData = SearchRunner_showActiveSearch(janitor->searchRunner,
  165. i,
  166. seachListAlloc);
  167. if (!searchData) { continue; }
  168. if (!Bits_memcmp(searchData->target, target, Address_SEARCH_TARGET_SIZE)) {
  169. // Already have a search going for this address, so nothing to do.
  170. Allocator_free(seachListAlloc);
  171. return;
  172. }
  173. }
  174. Allocator_free(seachListAlloc);
  175. // There's no search running for this address, so we start one.
  176. search(target, janitor);
  177. #ifdef Log_DEBUG
  178. uint8_t addrStr[40];
  179. AddrTools_printIp(addrStr, target);
  180. Log_debug(janitor->logger, "No active search for [%s], starting one.", addrStr);
  181. #endif
  182. }
  183. static void dhtResponseCallback(struct RouterModule_Promise* promise,
  184. uint32_t lagMilliseconds,
  185. struct Address* from,
  186. Dict* result)
  187. {
  188. struct Janitor_pvt* janitor = Identity_check((struct Janitor_pvt*)promise->userData);
  189. if (!from) { return; }
  190. blacklist(janitor, from->path);
  191. struct Address_List* addresses =
  192. ReplySerializer_parse(from, result, janitor->logger, true, promise->alloc);
  193. struct Node_Two* parent = NodeStore_nodeForAddr(janitor->nodeStore, from->ip6.bytes);
  194. if (!parent) { return; }
  195. struct Address* selfAddr = janitor->nodeStore->selfAddress;
  196. for (int i = 0; addresses && i < addresses->length; i++) {
  197. if (addresses->elems[i].path == NodeStore_optimizePath_INVALID) {
  198. // Impossible to ping this (label is probably too large).
  199. continue;
  200. }
  201. if (Address_closest(selfAddr, from, &addresses->elems[i]) < 0) {
  202. // Address is further from us than the node we asked. Skip it.
  203. // FIXME(arceliar): Probably need stronger requirements than this.
  204. continue;
  205. }
  206. struct Node_Link* link = NodeStore_linkForPath(janitor->nodeStore,
  207. addresses->elems[i].path);
  208. if (link) {
  209. // We already know about this path and mill space is precious. Skip it.
  210. continue;
  211. }
  212. // Possibly interesting for dht reasons.
  213. RumorMill_addNode(janitor->pub.dhtMill, &addresses->elems[i]);
  214. }
  215. }
  216. static void peersResponseCallback(struct RouterModule_Promise* promise,
  217. uint32_t lagMilliseconds,
  218. struct Address* from,
  219. Dict* result)
  220. {
  221. struct Janitor_pvt* janitor = Identity_check((struct Janitor_pvt*)promise->userData);
  222. if (!from) { return; }
  223. blacklist(janitor, from->path);
  224. if (Defined(Log_DEBUG)) {
  225. String* addr = Address_toString(from, promise->alloc);
  226. Log_debug(janitor->logger, "Got peers response from [%s]", addr->bytes);
  227. }
  228. struct Address_List* addresses =
  229. ReplySerializer_parse(from, result, janitor->logger, true, promise->alloc);
  230. struct Node_Two* parent = NodeStore_nodeForAddr(janitor->nodeStore, from->ip6.bytes);
  231. if (!parent) { return; }
  232. int loopCount = 0;
  233. for (int i = 0; addresses && i < addresses->length; i++) {
  234. // they're telling us about themselves, how helpful...
  235. if (!Bits_memcmp(addresses->elems[i].key, from->key, 32)) { continue; }
  236. struct Node_Link* nl = NodeStore_linkForPath(janitor->nodeStore, addresses->elems[i].path);
  237. if (!nl || nl->linkCost == UINT32_MAX || Bits_memcmp(nl->child->address.ip6.bytes,
  238. addresses->elems[i].ip6.bytes,
  239. Address_SEARCH_TARGET_SIZE))
  240. {
  241. struct Node_Two* node = NodeStore_nodeForAddr(janitor->nodeStore,
  242. addresses->elems[i].ip6.bytes);
  243. if (node) {
  244. RumorMill_addNode(janitor->pub.linkMill, &addresses->elems[i]);
  245. } else {
  246. // First check if this node would be useful for keyspace reasons.
  247. uint16_t bucketNodes = 0;
  248. uint16_t bucket = NodeStore_bucketForAddr(janitor->nodeStore->selfAddress,
  249. &addresses->elems[i]);
  250. struct Allocator* nodeListAlloc = Allocator_child(janitor->allocator);
  251. struct NodeList* nodeList = NodeStore_getNodesForBucket(janitor->nodeStore,
  252. nodeListAlloc,
  253. bucket,
  254. NodeStore_bucketSize);
  255. for (uint32_t i = 0 ; i < nodeList->size ; i++) {
  256. if (nodeList->nodes[i] == janitor->nodeStore->selfNode) { continue; }
  257. if (nodeList->nodes[i]->address.path == UINT64_MAX) { continue; }
  258. bucketNodes++;
  259. }
  260. Allocator_free(nodeListAlloc);
  261. if (bucketNodes < NodeStore_bucketSize) {
  262. // Add it and move on to the next address.
  263. RumorMill_addNode(janitor->pub.nodeMill, &addresses->elems[i]);
  264. continue;
  265. }
  266. /*
  267. // If it's not required for keyspace, then check if it can split a path.
  268. node = NodeStore_getNextNode(janitor->nodeStore, NULL);
  269. while (node) {
  270. if (LabelSplicer_routesThrough(node->address.path, addresses->elems[i].path)) {
  271. RumorMill_addNode(janitor->pub.nodeMill, &addresses->elems[i]);
  272. break;
  273. }
  274. node = NodeStore_getNextNode(janitor->nodeStore, node);
  275. }
  276. */
  277. // Check if this node can split an existing link.
  278. struct Node_Link* link = NULL;
  279. while ((link = NodeStore_nextLink(parent, link))) {
  280. if (Node_isOneHopLink(link)) { continue; }
  281. uint64_t label = NodeStore_getRouteLabel(janitor->nodeStore,
  282. from->path,
  283. link->cannonicalLabel);
  284. if (!LabelSplicer_routesThrough(label, addresses->elems[i].path)) { continue; }
  285. RumorMill_addNode(janitor->pub.nodeMill, &addresses->elems[i]);
  286. }
  287. }
  288. } else if (!Address_isSameIp(&addresses->elems[i], &nl->child->address)) {
  289. if (nl->parent != parent) {
  290. #ifdef Log_INFO
  291. uint8_t newAddr[60];
  292. Address_print(newAddr, from);
  293. uint8_t labelStr[20];
  294. AddrTools_printPath(labelStr, nl->cannonicalLabel);
  295. Log_info(janitor->logger, "Apparently [%s] reported [%s] as it's peer",
  296. newAddr, labelStr);
  297. #endif
  298. continue;
  299. }
  300. #ifdef Log_INFO
  301. uint8_t newAddr[60];
  302. Address_print(newAddr, from);
  303. Log_info(janitor->logger, "Apparently [%s] has renumbered it's switch", newAddr);
  304. #endif
  305. struct Node_Link* link = NodeStore_nextLink(parent, NULL);
  306. while (link) {
  307. struct Node_Link* nextLink = NodeStore_nextLink(parent, link);
  308. NodeStore_unlinkNodes(janitor->nodeStore, link);
  309. link = nextLink;
  310. // restart from the beginning...
  311. i = 0;
  312. Assert_true(!loopCount);
  313. }
  314. Assert_true(!NodeStore_nextLink(parent, NULL));
  315. loopCount++;
  316. }
  317. }
  318. }
  319. /**
  320. * For a Distributed Hash Table to work, each node must know a valid next hop for every possible
  321. * lookup, unless no such node exists in the network (i.e. the final hop is either us or offline).
  322. *
  323. * This function queries other nodes to find valid next hops for any address.
  324. */
  325. static void keyspaceMaintenance(struct Janitor_pvt* janitor)
  326. {
  327. struct Address addr;
  328. struct Address* selfAddr = janitor->nodeStore->selfAddress;
  329. if (!RumorMill_getNode(janitor->pub.dhtMill, &addr)) {
  330. // Try to fill the dhtMill for next time.
  331. for (uint16_t bucket = 0; bucket < NodeStore_bucketNumber ; bucket++) {
  332. // Check if there's a valid next hop for this bit in keyspace.
  333. struct Allocator* nodeListAlloc = Allocator_child(janitor->allocator);
  334. struct NodeList* nodeList = NodeStore_getNodesForBucket(janitor->nodeStore,
  335. nodeListAlloc,
  336. bucket,
  337. NodeStore_bucketSize);
  338. for (uint32_t i = 0 ; i < nodeList->size ; i++) {
  339. if (nodeList->nodes[i] == janitor->nodeStore->selfNode) { continue; }
  340. if (nodeList->nodes[i]->address.path == UINT64_MAX) { continue; }
  341. // There's a valid next hop.
  342. RumorMill_addNode(janitor->pub.dhtMill, &nodeList->nodes[i]->address);
  343. }
  344. Allocator_free(nodeListAlloc);
  345. }
  346. return;
  347. }
  348. struct Node_Two* node = NodeStore_nodeForAddr(janitor->nodeStore, addr.ip6.bytes);
  349. if (node && node->address.path == addr.path) {
  350. //FIXME(arceliar): This target probably isn't optimal.
  351. uint16_t bucket = NodeStore_bucketForAddr(selfAddr, &addr);
  352. struct Address target = NodeStore_addrForBucket(&addr, bucket);
  353. struct RouterModule_Promise* rp = RouterModule_findNode(&addr,
  354. target.ip6.bytes,
  355. 0,
  356. janitor->routerModule,
  357. janitor->allocator);
  358. rp->callback = dhtResponseCallback;
  359. rp->userData = janitor;
  360. #ifdef Log_DEBUG
  361. uint8_t addrStr[60];
  362. Address_print(addrStr, &addr);
  363. Log_debug(janitor->logger, "Sending findNode to [%s] from "
  364. "dht-checking RumorMill", addrStr);
  365. #endif
  366. } else {
  367. // Node not already in our routing table.
  368. // Ping them. If they're good, we'll ask them to findNodes our next round.
  369. RouterModule_pingNode(&addr, 0, janitor->routerModule, janitor->allocator);
  370. #ifdef Log_DEBUG
  371. uint8_t addrStr[60];
  372. Address_print(addrStr, &addr);
  373. Log_debug(janitor->logger, "Pinging possible node [%s] from "
  374. "dht-checking RumorMill", addrStr);
  375. #endif
  376. }
  377. return;
  378. searchNoDupe(addr.ip6.bytes, janitor); // The last search, unaccessible.
  379. }
  380. static struct Node_Two* getRandomNode(struct Random* rand, struct NodeStore* store)
  381. {
  382. uint32_t index = Random_uint32(rand) % (store->nodeCount);
  383. struct Node_Two* node = NULL;
  384. do {
  385. node = NodeStore_getNextNode(store, node);
  386. } while (index--);
  387. // there's always the self node
  388. Assert_true(node);
  389. return node;
  390. }
  391. static void getPeersMill(struct Janitor_pvt* janitor, struct Address* addr)
  392. {
  393. // If we have a node in the store and we ping the same path with a different address
  394. // it can cause an error packet which causes the *good* link to be destroyed.
  395. // Therefore we will always ping the node which we believe to be at the end of the
  396. // path and if there is an error, we will flush the link rediscover the path later.
  397. // Don't use a random target if we actually know a useful one.
  398. uint64_t targetLabel = Random_uint32(janitor->rand);
  399. struct Node_Link* nl = NodeStore_linkForPath(janitor->nodeStore, addr->path);
  400. if (nl) {
  401. addr = &nl->child->address;
  402. struct Node_Link* link = NULL;
  403. while ((link = NodeStore_nextLink(nl->child, link))) {
  404. if (!Node_isOneHopLink(link) && link == Node_getBestParent(link->child)) {
  405. targetLabel = nl->cannonicalLabel;
  406. break;
  407. }
  408. }
  409. }
  410. struct RouterModule_Promise* rp =
  411. RouterModule_getPeers(addr,
  412. targetLabel,
  413. 0,
  414. janitor->routerModule,
  415. janitor->allocator);
  416. rp->callback = peersResponseCallback;
  417. rp->userData = janitor;
  418. }
  419. #define debugAddr(janitor, msg, addr) \
  420. if (Defined(Log_DEBUG)) { \
  421. uint8_t addrStr[60]; \
  422. Address_print(addrStr, (addr)); \
  423. Log_debug((janitor)->logger, "%s [%s]", (msg), addrStr); \
  424. } \
  425. do { } while (0)
  426. // CHECKFILES_IGNORE expecting a { or ;
  427. static bool tryExistingNode(struct Janitor_pvt* janitor)
  428. {
  429. struct Node_Two* worst = NULL;
  430. uint64_t worstTime = 0;
  431. struct Node_Two* node = NodeStore_getNextNode(janitor->nodeStore, NULL);
  432. while (node) {
  433. uint64_t nodeTime = NodeStore_timeSinceLastPing(janitor->nodeStore, node);
  434. if (node == janitor->nodeStore->selfNode) {
  435. // No reason to ping the selfNode.
  436. } else if (node->address.path != UINT64_MAX &&
  437. (!worst || nodeTime > worstTime))
  438. {
  439. worst = node;
  440. worstTime = nodeTime;
  441. }
  442. node = NodeStore_getNextNode(janitor->nodeStore, node);
  443. }
  444. if (worst) {
  445. getPeersMill(janitor, &worst->address);
  446. debugAddr(janitor, "Pinging existing node", &worst->address);
  447. return true;
  448. }
  449. return false;
  450. }
  451. #define tryMill_rules_CAN_PING (1<<0)
  452. #define tryMill_rules_IN_NODESTORE (1<<1)
  453. static bool tryMill(struct Janitor_pvt* janitor, struct RumorMill* mill, int rules)
  454. {
  455. struct Address addr = { .protocolVersion = 0 };
  456. while (RumorMill_getNode(mill, &addr)) {
  457. if (rules & tryMill_rules_CAN_PING) {
  458. if (isBlacklisted(janitor, addr.path)) {
  459. debugAddr(janitor, "Not pinging blacklisted node", &addr);
  460. continue;
  461. }
  462. }
  463. if (rules & tryMill_rules_IN_NODESTORE) {
  464. if (!NodeStore_nodeForAddr(janitor->nodeStore, addr.ip6.bytes)) {
  465. debugAddr(janitor, "Not pinging node not in nodeStore", &addr);
  466. continue;
  467. }
  468. }
  469. getPeersMill(janitor, &addr);
  470. if (Defined(Log_DEBUG)) {
  471. uint8_t addrStr[60];
  472. Address_print(addrStr, &addr);
  473. Log_debug(janitor->logger, "Pinging possible node [%s] from RumorMill [%s]",
  474. addrStr, mill->name);
  475. }
  476. return true;
  477. }
  478. return false;
  479. }
  480. // Iterate over all nodes in the table. Try to split any split-able links.
  481. static bool splitLinks(struct Janitor_pvt* janitor)
  482. {
  483. struct Node_Link* link = NULL;
  484. if (!janitor->pub.splitMill->count) {
  485. while ((link = NodeStore_getNextLink(janitor->nodeStore, link))) {
  486. if (link != Node_getBestParent(link->child)) { continue; }
  487. if (Node_isOneHopLink(link)) { continue; }
  488. if (link->child == janitor->nodeStore->selfNode) { continue; }
  489. RumorMill_addNode(janitor->pub.splitMill, &link->parent->address);
  490. }
  491. }
  492. return tryMill(janitor, janitor->pub.splitMill, tryMill_rules_CAN_PING);
  493. }
  494. static bool tryRandomLink(struct Janitor_pvt* janitor)
  495. {
  496. // There's not an obvious way to get a random link directly, so first get a random node.
  497. struct Node_Two* node = getRandomNode(janitor->rand, janitor->nodeStore);
  498. // Count the number of links leading from this node.
  499. struct Node_Link* link = NodeStore_nextLink(node, NULL);
  500. uint32_t linkCount = 0;
  501. while (link) {
  502. linkCount++;
  503. link = NodeStore_nextLink(node, link);
  504. }
  505. if (linkCount) {
  506. // Now pick one of these links at random.
  507. uint32_t randLinkIndex = Random_uint32(janitor->rand) % linkCount;
  508. link = NodeStore_nextLink(node, NULL);
  509. linkCount = 0;
  510. while (linkCount < randLinkIndex) {
  511. linkCount++;
  512. link = NodeStore_nextLink(node, link);
  513. }
  514. }
  515. if (link && link->parent != link->child) {
  516. struct Address addr = link->child->address;
  517. uint64_t path = NodeStore_getRouteLabel(janitor->nodeStore,
  518. link->parent->address.path,
  519. link->cannonicalLabel);
  520. if (path != NodeStore_getRouteLabel_PARENT_NOT_FOUND &&
  521. path != NodeStore_getRouteLabel_CHILD_NOT_FOUND)
  522. {
  523. addr.path = path;
  524. }
  525. if (addr.path < UINT64_MAX) {
  526. getPeersMill(janitor, &addr);
  527. #ifdef Log_DEBUG
  528. uint8_t addrStr[60];
  529. Address_print(addrStr, &addr);
  530. Log_debug(janitor->logger, "Pinging random node link [%s] for maintenance.",
  531. addrStr);
  532. #endif
  533. return true;
  534. }
  535. }
  536. return false;
  537. }
  538. static void maintanenceCycle(void* vcontext)
  539. {
  540. struct Janitor_pvt* const janitor = Identity_check((struct Janitor_pvt*) vcontext);
  541. uint64_t now = Time_currentTimeMilliseconds(janitor->eventBase);
  542. uint64_t nextTimeout = (janitor->pub.localMaintainenceMilliseconds / 2);
  543. nextTimeout += Random_uint32(janitor->rand) % (nextTimeout * 2);
  544. Timeout_resetTimeout(janitor->timeout, nextTimeout);
  545. if (janitor->nodeStore->nodeCount == 0 && janitor->pub.externalMill->count == 0) {
  546. if (now > janitor->timeOfNextGlobalMaintainence) {
  547. Log_warn(janitor->logger,
  548. "No nodes in routing table, check network connection and configuration.");
  549. janitor->timeOfNextGlobalMaintainence += janitor->pub.globalMaintainenceMilliseconds;
  550. }
  551. return;
  552. }
  553. struct Address addr = { .protocolVersion = 0 };
  554. if (tryMill(janitor, janitor->pub.externalMill, tryMill_rules_CAN_PING)) {
  555. // Always try the external mill first, this is low-traffic.
  556. } else if (tryMill(janitor,
  557. janitor->pub.linkMill,
  558. tryMill_rules_CAN_PING | tryMill_rules_IN_NODESTORE))
  559. {
  560. // Try to find a new link to a known node.
  561. } else if (tryMill(janitor, janitor->pub.nodeMill, tryMill_rules_CAN_PING)) {
  562. // Try to find a new node.
  563. } else if (splitLinks(janitor)) {
  564. // Try to split links which are not 1 hop.
  565. } else if (tryRandomLink(janitor)) {
  566. // Ping a random link from a random node.
  567. } else {
  568. Log_debug(janitor->logger, "Could not find anything to do");
  569. }
  570. // Try to ping the existing node we have heard from least recently.
  571. tryExistingNode(janitor);
  572. // Look for better nodes for the dht.
  573. keyspaceMaintenance(janitor);
  574. // random search
  575. Random_bytes(janitor->rand, addr.ip6.bytes, 16);
  576. // Make this a valid address.
  577. AddressCalc_makeValidAddress(addr.ip6.bytes);
  578. struct Node_Two* n = NodeStore_getBest(janitor->nodeStore, addr.ip6.bytes);
  579. // If the best next node doesn't exist or has maximum cost, run a local maintenance search.
  580. if (n == NULL || Node_getCost(n) == UINT64_MAX) {
  581. // or actually, don't
  582. //search(addr.ip6.bytes, janitor);
  583. //plugLargestKeyspaceHole(janitor, true);
  584. //return;
  585. }
  586. Log_debug(janitor->logger,
  587. "Global Mean Response Time: %u nodes [%d] links [%d]",
  588. RouterModule_globalMeanResponseTime(janitor->routerModule),
  589. janitor->nodeStore->nodeCount,
  590. janitor->nodeStore->linkCount);
  591. if (now > janitor->timeOfNextGlobalMaintainence) {
  592. //search(addr.ip6.bytes, janitor);
  593. janitor->timeOfNextGlobalMaintainence += janitor->pub.globalMaintainenceMilliseconds;
  594. }
  595. }
  596. struct Janitor* Janitor_new(struct RouterModule* routerModule,
  597. struct NodeStore* nodeStore,
  598. struct SearchRunner* searchRunner,
  599. struct RumorMill* rumorMill,
  600. struct Log* logger,
  601. struct Allocator* allocator,
  602. struct EventBase* eventBase,
  603. struct Random* rand)
  604. {
  605. struct Allocator* alloc = Allocator_child(allocator);
  606. struct Janitor_pvt* janitor = Allocator_clone(alloc, (&(struct Janitor_pvt) {
  607. .eventBase = eventBase,
  608. .routerModule = routerModule,
  609. .nodeStore = nodeStore,
  610. .searchRunner = searchRunner,
  611. .logger = logger,
  612. .allocator = alloc,
  613. .rand = rand
  614. }));
  615. Identity_set(janitor);
  616. janitor->pub.externalMill = rumorMill;
  617. janitor->pub.linkMill = RumorMill_new(alloc, nodeStore->selfAddress, 64, logger, "linkMill");
  618. janitor->pub.nodeMill = RumorMill_new(alloc, nodeStore->selfAddress, 64, logger, "nodeMill");
  619. janitor->pub.dhtMill = RumorMill_new(alloc,
  620. nodeStore->selfAddress,
  621. (NodeStore_bucketNumber * NodeStore_bucketSize),
  622. logger,
  623. "dhtMill");
  624. janitor->pub.splitMill = RumorMill_new(alloc, nodeStore->selfAddress, 16, logger, "splitMill");
  625. janitor->pub.globalMaintainenceMilliseconds = Janitor_GLOBAL_MAINTENANCE_MILLISECONDS_DEFAULT;
  626. janitor->pub.localMaintainenceMilliseconds = Janitor_LOCAL_MAINTENANCE_MILLISECONDS_DEFAULT;
  627. janitor->pub.blacklistPathForMilliseconds = Janitor_BLACKLIST_PATH_FOR_MILLISECONDS_DEFAULT;
  628. janitor->timeOfNextGlobalMaintainence = Time_currentTimeMilliseconds(eventBase);
  629. janitor->timeout = Timeout_setTimeout(maintanenceCycle,
  630. janitor,
  631. janitor->pub.localMaintainenceMilliseconds,
  632. eventBase,
  633. alloc);
  634. return &janitor->pub;
  635. }