RumorMill.c 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147
  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 <http://www.gnu.org/licenses/>.
  14. */
  15. #include "dht/dhtcore/RumorMill.h"
  16. #include "dht/Address.h"
  17. #include "memory/Allocator.h"
  18. #include "util/Identity.h"
  19. #include "util/Assert.h"
  20. #include "util/Bits.h"
  21. #include "util/Defined.h"
  22. /**
  23. * The rumor mill is for new nodes which have been discovered by search and getPeers requests
  24. * but we have never actually communicated with them so we are not sure if they exist.
  25. *
  26. * More importantly, we *cannot* link them into the nodeStore tree because we are not sure of
  27. * their encoding scheme.
  28. */
  29. struct RumorMill_pvt
  30. {
  31. struct RumorMill pub;
  32. struct Address* selfAddr;
  33. struct Address* addresses;
  34. int capacity;
  35. struct Log* log;
  36. const char* name;
  37. Identity
  38. };
  39. static int getBadness(struct Address* badAddr, struct Address* selfAddr)
  40. {
  41. uint64_t xor = Endian_bigEndianToHost64(badAddr->ip6.longs.one_be ^ selfAddr->ip6.longs.one_be);
  42. return Bits_log2x64(xor) + Bits_log2x64(badAddr->path);
  43. }
  44. static struct Address* getWorst(struct RumorMill_pvt* rm)
  45. {
  46. struct Address* worst = NULL;
  47. int howBadIsTheWorst = 0;
  48. for (int i = 0; i < rm->pub.count; i++) {
  49. int howBad = getBadness(&rm->addresses[i], rm->selfAddr);
  50. if (howBad > howBadIsTheWorst) {
  51. howBadIsTheWorst = howBad;
  52. worst = &rm->addresses[i];
  53. }
  54. }
  55. Assert_true(worst);
  56. return worst;
  57. }
  58. static struct Address* getBest(struct RumorMill_pvt* rm)
  59. {
  60. if (rm->pub.count == 0) { return NULL; }
  61. struct Address* best = NULL;
  62. int howBadIsTheBest = -1;
  63. for (int i = 0; i < rm->pub.count; i++) {
  64. int howBad = getBadness(&rm->addresses[i], rm->selfAddr);
  65. if (howBad < howBadIsTheBest || !best) {
  66. howBadIsTheBest = howBad;
  67. best = &rm->addresses[i];
  68. }
  69. }
  70. Assert_true(best);
  71. return best;
  72. }
  73. void RumorMill__addNode(struct RumorMill* mill, struct Address* addr, const char* file, int line)
  74. {
  75. struct RumorMill_pvt* rm = Identity_check((struct RumorMill_pvt*) mill);
  76. Address_getPrefix(addr);
  77. for (int i = 0; i < rm->pub.count; i++) {
  78. if (rm->addresses[i].path == addr->path &&
  79. !Bits_memcmp(rm->addresses[i].key, addr->key, 32))
  80. {
  81. return;
  82. }
  83. }
  84. if (!Bits_memcmp(addr->key, rm->selfAddr->key, 32)) { return; }
  85. struct Address* replace;
  86. if (rm->pub.count < rm->capacity) {
  87. replace = &rm->addresses[rm->pub.count++];
  88. } else {
  89. replace = getWorst(rm);
  90. }
  91. Bits_memcpyConst(replace, addr, sizeof(struct Address));
  92. if (Defined(Log_DEBUG)) {
  93. uint8_t addrStr[60];
  94. Address_print(addrStr, addr);
  95. Log_debug(rm->log, "[%s] addNode(%s) count[%d] from [%s:%d]",
  96. rm->name, addrStr, rm->pub.count, file, line);
  97. }
  98. }
  99. bool RumorMill_getNode(struct RumorMill* mill, struct Address* output)
  100. {
  101. struct RumorMill_pvt* rm = Identity_check((struct RumorMill_pvt*) mill);
  102. if (!rm->pub.count) { return false; }
  103. struct Address* best = getBest(rm);
  104. Bits_memcpyConst(output, best, sizeof(struct Address));
  105. rm->pub.count--;
  106. if (&rm->addresses[rm->pub.count] != best) {
  107. Bits_memcpyConst(best, &rm->addresses[rm->pub.count], sizeof(struct Address));
  108. }
  109. return true;
  110. }
  111. struct RumorMill* RumorMill_new(struct Allocator* allocator,
  112. struct Address* selfAddr,
  113. int capacity,
  114. struct Log* log,
  115. const char* name)
  116. {
  117. struct Allocator* alloc = Allocator_child(allocator);
  118. Address_getPrefix(selfAddr);
  119. struct RumorMill_pvt* rm = Allocator_calloc(alloc, sizeof(struct RumorMill_pvt), 1);
  120. rm->addresses = Allocator_calloc(alloc, sizeof(struct Address), capacity);
  121. rm->capacity = capacity;
  122. rm->selfAddr = Allocator_clone(alloc, selfAddr);
  123. rm->log = log;
  124. rm->name = name;
  125. Identity_set(rm);
  126. return &rm->pub;
  127. }