1
0

SwitchCore.c 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378
  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 "memory/Allocator.h"
  16. #include "interface/Interface.h"
  17. #include "util/log/Log.h"
  18. #include "switch/SwitchCore.h"
  19. #include "switch/NumberCompress.h"
  20. #include "util/Bits.h"
  21. #include "util/Checksum.h"
  22. #include "util/Endian.h"
  23. #include "wire/Control.h"
  24. #include "wire/Error.h"
  25. #include "wire/Headers.h"
  26. #include "wire/Message.h"
  27. #include <inttypes.h>
  28. #include <stdbool.h>
  29. struct SwitchInterface
  30. {
  31. struct Interface* iface;
  32. struct SwitchCore* core;
  33. struct Allocator_OnFreeJob* onFree;
  34. /**
  35. * How much traffic has flowed down an interface as the sum of all packet priority.
  36. * If this number reaches bufferMax, further incoming traffic is dropped to prevent flooding.
  37. * Users should periodically adjust the buffer toward zero to fairly meter out priority in
  38. * congestion situations.
  39. */
  40. int64_t buffer;
  41. /**
  42. * How high the buffer is allowed to get before beginning to drop packets.
  43. * For nodes in the core, this number should be large because a buffer
  44. * limit of a core link will cause route flapping.
  45. * For edge nodes it is a measure of how much the ISP trusts the end user not to flood.
  46. */
  47. int64_t bufferMax;
  48. /**
  49. * How congested an interface is.
  50. * this number is subtraced from packet priority when the packet is sent down this interface.
  51. */
  52. uint32_t congestion;
  53. };
  54. struct SwitchCore
  55. {
  56. struct SwitchInterface interfaces[NumberCompress_INTERFACES];
  57. uint32_t interfaceCount;
  58. bool routerAdded;
  59. struct Log* logger;
  60. struct Allocator* allocator;
  61. };
  62. struct SwitchCore* SwitchCore_new(struct Log* logger, struct Allocator* allocator)
  63. {
  64. struct SwitchCore* core = Allocator_calloc(allocator, sizeof(struct SwitchCore), 1);
  65. core->allocator = allocator;
  66. core->interfaceCount = 0;
  67. core->logger = logger;
  68. return core;
  69. }
  70. static inline uint16_t sendMessage(const struct SwitchInterface* switchIf,
  71. struct Message* toSend,
  72. struct Log* logger)
  73. {
  74. struct Headers_SwitchHeader* switchHeader = (struct Headers_SwitchHeader*) toSend->bytes;
  75. uint32_t priority = Headers_getPriority(switchHeader);
  76. if (switchIf->buffer + priority > switchIf->bufferMax) {
  77. uint32_t messageType = Headers_getMessageType(switchHeader);
  78. Headers_setPriorityAndMessageType(switchHeader, 0, messageType);
  79. }
  80. return Interface_sendMessage(switchIf->iface, toSend);
  81. }
  82. struct ErrorPacket {
  83. struct Headers_SwitchHeader switchHeader;
  84. struct Control ctrl;
  85. };
  86. Assert_compileTime(
  87. sizeof(struct ErrorPacket) == Headers_SwitchHeader_SIZE + sizeof(struct Control));
  88. static inline void sendError(struct SwitchInterface* iface,
  89. struct Message* cause,
  90. uint32_t code,
  91. struct Log* logger)
  92. {
  93. struct Headers_SwitchHeader* header = (struct Headers_SwitchHeader*) cause->bytes;
  94. if (Headers_getMessageType(header) == Headers_SwitchHeader_TYPE_CONTROL
  95. && ((struct ErrorPacket*) cause->bytes)->ctrl.type_be == Control_ERROR_be)
  96. {
  97. // Errors never cause other errors to be sent.
  98. return;
  99. }
  100. // limit of 256 bytes
  101. cause->length =
  102. (cause->length < Control_Error_MAX_SIZE) ? cause->length : Control_Error_MAX_SIZE;
  103. // Shift back so we can add another header.
  104. Message_shift(cause,
  105. Headers_SwitchHeader_SIZE + Control_HEADER_SIZE + Control_Error_HEADER_SIZE,
  106. NULL);
  107. struct ErrorPacket* err = (struct ErrorPacket*) cause->bytes;
  108. err->switchHeader.label_be = Bits_bitReverse64(header->label_be);
  109. Headers_setPriorityAndMessageType(&err->switchHeader,
  110. Headers_getPriority(header),
  111. Headers_SwitchHeader_TYPE_CONTROL);
  112. err->ctrl.type_be = Control_ERROR_be;
  113. err->ctrl.content.error.errorType_be = Endian_hostToBigEndian32(code);
  114. err->ctrl.checksum_be = 0;
  115. err->ctrl.checksum_be =
  116. Checksum_engine((uint8_t*) &err->ctrl, cause->length - Headers_SwitchHeader_SIZE);
  117. sendMessage(iface, cause, logger);
  118. }
  119. #define DEBUG_SRC_DST(logger, message) \
  120. Log_debug(logger, message " ([%u] to [%u])", sourceIndex, destIndex)
  121. /** This never returns an error, it sends an error packet instead. */
  122. static uint8_t receiveMessage(struct Message* message, struct Interface* iface)
  123. {
  124. struct SwitchInterface* sourceIf = (struct SwitchInterface*) iface->receiverContext;
  125. if (sourceIf->buffer > sourceIf->bufferMax) {
  126. Log_warn(sourceIf->core->logger, "DROP because node seems to be flooding.");
  127. return Error_NONE;
  128. }
  129. if (message->length < Headers_SwitchHeader_SIZE) {
  130. Log_debug(sourceIf->core->logger, "DROP runt packet.");
  131. return Error_NONE;
  132. }
  133. struct SwitchCore* core = sourceIf->core;
  134. struct Headers_SwitchHeader* header = (struct Headers_SwitchHeader*) message->bytes;
  135. const uint64_t label = Endian_bigEndianToHost64(header->label_be);
  136. uint32_t bits = NumberCompress_bitsUsedForLabel(label);
  137. const uint32_t sourceIndex = sourceIf - core->interfaces;
  138. const uint32_t destIndex = NumberCompress_getDecompressed(label, bits);
  139. const uint32_t sourceBits = NumberCompress_bitsUsedForNumber(sourceIndex);
  140. Assert_true(destIndex < NumberCompress_INTERFACES);
  141. Assert_true(sourceIndex < NumberCompress_INTERFACES);
  142. if (1 == destIndex) {
  143. if (1 != (label & 0xf)) {
  144. /* routing interface: must always be compressed as 0001 */
  145. DEBUG_SRC_DST(sourceIf->core->logger,
  146. "DROP packet for this router because the destination "
  147. "discriminator was wrong");
  148. sendError(sourceIf, message, Error_MALFORMED_ADDRESS, sourceIf->core->logger);
  149. return Error_NONE;
  150. }
  151. //Assert_true(bits == 4);
  152. }
  153. if (sourceBits > bits) {
  154. if (destIndex == 1) {
  155. // If the destination index is this router, don't drop the packet since there no
  156. // way for a node to know the size of the representation of its source label.
  157. // - label ends in 0001; if there are enough zeroes at the end after removing the 1,
  158. // we can still fit in the source discriminator
  159. // - the return path probably doesn't start with 3 zeroes, but it will still be working,
  160. // as the source discriminator is large enough to make space for 3 zeroes between
  161. // reverse return path and forward path (see below)
  162. if (0 != ((label ^ 1) & (UINT64_MAX >> (64 - sourceBits - 4)))) {
  163. // This is a bug.
  164. // https://github.com/cjdelisle/cjdns/issues/93
  165. // The problem is that there is no way to splice a route and know for certain
  166. // that you've not spliced one which will end up in this if statement.
  167. // Unfortunately there seems no clean way around this issue at the moment.
  168. // If this router and switch communicated using labels with "64 + four less
  169. // than the number of bits in largest discriminator" bits wide, it could handle
  170. // this situation, this solution is obviously non-trivial.
  171. DEBUG_SRC_DST(sourceIf->core->logger,
  172. "DROP packet for this router because there is no way to "
  173. "represent the return path.");
  174. sendError(sourceIf, message, Error_RETURN_PATH_INVALID, sourceIf->core->logger);
  175. return Error_NONE;
  176. }
  177. bits = sourceBits;
  178. } else if (1 == sourceIndex) {
  179. // - we need at least 3 zeroes between reverse return path and forward path:
  180. // right now the label only contains the forward path
  181. // - sourceBits == 4, bits < 4 -> bits + 64 - sourceBits < 64
  182. // - the reverse source discriminator "1000" and the target discriminator "0001"
  183. // can overlap as "10001" (or "100001" or ...)
  184. if (0 != label >> (bits + 64 - sourceBits)) {
  185. // not enough zeroes
  186. DEBUG_SRC_DST(sourceIf->core->logger, "DROP packet because source address is "
  187. "larger than destination address.");
  188. sendError(sourceIf, message, Error_MALFORMED_ADDRESS, sourceIf->core->logger);
  189. return Error_NONE;
  190. }
  191. } else {
  192. Log_info(sourceIf->core->logger, "source exceeds dest");
  193. DEBUG_SRC_DST(sourceIf->core->logger, "DROP packet because source address is "
  194. "larger than destination address.");
  195. sendError(sourceIf, message, Error_MALFORMED_ADDRESS, sourceIf->core->logger);
  196. return Error_NONE;
  197. }
  198. }
  199. if (core->interfaces[destIndex].iface == NULL) {
  200. Log_info(sourceIf->core->logger, "no such iface");
  201. DEBUG_SRC_DST(sourceIf->core->logger, "DROP packet because there is no interface "
  202. "where the bits specify.");
  203. sendError(sourceIf, message, Error_MALFORMED_ADDRESS, sourceIf->core->logger);
  204. return Error_NONE;
  205. }
  206. /*if (sourceIndex == destIndex && sourceIndex != 1) {
  207. DEBUG_SRC_DST(sourceIf->core->logger, "DROP Packet with redundant route.");
  208. sendError(sourceIf, message, Error_LOOP_ROUTE, sourceIf->core->logger);
  209. return Error_NONE;
  210. }*/
  211. uint64_t sourceLabel = Bits_bitReverse64(NumberCompress_getCompressed(sourceIndex, bits));
  212. uint64_t targetLabel = (label >> bits) | sourceLabel;
  213. header->label_be = Endian_hostToBigEndian64(targetLabel);
  214. /* Too much noise.
  215. Log_debug(sourceIf->core->logger,
  216. "Forwarding packet ([%u] to [%u]), labels [0x%016" PRIx64 "] -> [0x%016" PRIx64 "]",
  217. sourceIndex, destIndex, label, targetLabel);
  218. */
  219. int cloneLength = (message->length < Control_Error_MAX_SIZE) ?
  220. message->length : Control_Error_MAX_SIZE;
  221. uint8_t messageClone[Control_Error_MAX_SIZE];
  222. Bits_memcpy(messageClone, message->bytes, cloneLength);
  223. const uint16_t err = sendMessage(&core->interfaces[destIndex], message, sourceIf->core->logger);
  224. if (err) {
  225. Log_debug(sourceIf->core->logger, "Sending packet caused an error [%s]",
  226. Error_strerror(err));
  227. // be careful, the message could have decrypted content in it
  228. // and we don't want to spill it out over the wire.
  229. message->length = message->capacity;
  230. Message_shift(message, -message->length, NULL);
  231. Message_shift(message, Control_Error_MAX_SIZE, NULL);
  232. Bits_memcpy(message->bytes, messageClone, cloneLength);
  233. message->length = cloneLength;
  234. header = (struct Headers_SwitchHeader*) message->bytes;
  235. header->label_be = Endian_bigEndianToHost64(label);
  236. sendError(sourceIf, message, err, sourceIf->core->logger);
  237. return Error_NONE;
  238. }
  239. return Error_NONE;
  240. }
  241. static int removeInterface(struct Allocator_OnFreeJob* job)
  242. {
  243. struct SwitchInterface* si = (struct SwitchInterface*) job->userData;
  244. Bits_memset(si, 0, sizeof(struct SwitchInterface));
  245. return 0;
  246. }
  247. void SwitchCore_swapInterfaces(struct Interface* if1, struct Interface* if2)
  248. {
  249. struct SwitchInterface* si1 = (struct SwitchInterface*) if1->receiverContext;
  250. struct SwitchInterface* si2 = (struct SwitchInterface*) if2->receiverContext;
  251. Assert_true(Allocator_cancelOnFree(si1->onFree) > -1);
  252. Assert_true(Allocator_cancelOnFree(si2->onFree) > -1);
  253. struct SwitchInterface si3;
  254. Bits_memcpyConst(&si3, si1, sizeof(struct SwitchInterface));
  255. Bits_memcpyConst(si1, si2, sizeof(struct SwitchInterface));
  256. Bits_memcpyConst(si2, &si3, sizeof(struct SwitchInterface));
  257. // Now the if#'s are in reverse order :)
  258. si1->onFree = Allocator_onFree(if2->allocator, removeInterface, si1);
  259. si2->onFree = Allocator_onFree(if1->allocator, removeInterface, si2);
  260. if1->receiverContext = si2;
  261. if2->receiverContext = si1;
  262. }
  263. /**
  264. * @param trust a positive integer representing how much you trust the
  265. * connected node not to send a flood.
  266. * @param labelOut an integer pointer which will be set to the path to the newly added node
  267. * in host endian order.
  268. * @return 0 if all goes well, -1 if the list is full.
  269. */
  270. int SwitchCore_addInterface(struct Interface* iface,
  271. const uint64_t trust,
  272. uint64_t* labelOut,
  273. struct SwitchCore* core)
  274. {
  275. // This is some hackery to make sure the router interface is always index 1.
  276. uint32_t ifIndex = core->interfaceCount;
  277. if (ifIndex > 0 && !core->routerAdded) {
  278. ifIndex++;
  279. } else if (ifIndex == 1) {
  280. ifIndex--;
  281. }
  282. // If there's a vacent spot where another iface was before it was removed, use that.
  283. for (uint32_t i = 0; i < ifIndex; i++) {
  284. if (core->interfaces[i].iface == NULL && i != 1) {
  285. ifIndex = i;
  286. break;
  287. }
  288. }
  289. if (ifIndex == NumberCompress_INTERFACES) {
  290. return SwitchCore_addInterface_OUT_OF_SPACE;
  291. }
  292. struct SwitchInterface* newIf = &core->interfaces[ifIndex];
  293. Bits_memcpyConst(newIf, (&(struct SwitchInterface) {
  294. .iface = iface,
  295. .core = core,
  296. .buffer = 0,
  297. .bufferMax = trust,
  298. .congestion = 0
  299. }), sizeof(struct SwitchInterface));
  300. newIf->onFree = Allocator_onFree(iface->allocator, removeInterface, newIf);
  301. iface->receiverContext = &core->interfaces[ifIndex];
  302. iface->receiveMessage = receiveMessage;
  303. uint32_t bits = NumberCompress_bitsUsedForNumber(ifIndex);
  304. *labelOut = NumberCompress_getCompressed(ifIndex, bits) | (1 << bits);
  305. core->interfaceCount++;
  306. return 0;
  307. }
  308. int SwitchCore_setRouterInterface(struct Interface* iface, struct SwitchCore* core)
  309. {
  310. Bits_memcpyConst(&core->interfaces[1], (&(struct SwitchInterface) {
  311. .iface = iface,
  312. .core = core,
  313. .buffer = 0,
  314. .bufferMax = INT64_MAX,
  315. .congestion = 0
  316. }), sizeof(struct SwitchInterface));
  317. iface->receiverContext = &core->interfaces[1];
  318. iface->receiveMessage = receiveMessage;
  319. core->interfaceCount++;
  320. core->routerAdded = true;
  321. return 0;
  322. }