2 This file is part of GNUnet.
3 (C) 2013 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file dv/gnunet-service-dv.c
23 * @brief the distance vector service, primarily handles gossip of nearby
24 * peers and sending/receiving DV messages from core and decapsulating
27 * @author Christian Grothoff
28 * @author Nathan Evans
31 * - distance updates are not properly communicate to US by core,
32 * and conversely we don't give distance updates properly to the plugin yet
33 * - we send 'ACK' even if a message was dropped due to no route (may
34 * be harmless, but should at least be documented -- or support NACK)
37 #include "gnunet_util_lib.h"
38 #include "gnunet_protocols.h"
39 #include "gnunet_core_service.h"
40 #include "gnunet_hello_lib.h"
41 #include "gnunet_peerinfo_service.h"
42 #include "gnunet_statistics_service.h"
43 #include "gnunet_consensus_service.h"
48 * How often do we establish the consensu?
50 #define GNUNET_DV_CONSENSUS_FREQUENCY GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 5)
53 * Maximum number of messages we queue per peer.
55 #define MAX_QUEUE_SIZE 16
58 * The default fisheye depth, from how many hops away will
61 #define DEFAULT_FISHEYE_DEPTH 3
64 * How many hops is a direct neighbor away?
66 #define DIRECT_NEIGHBOR_COST 1
69 GNUNET_NETWORK_STRUCT_BEGIN
72 * Information about a peer DV can route to. These entries are what
73 * we use as the binary format to establish consensus to create our
74 * routing table and as the address format in the HELLOs.
80 * Identity of the peer we can reach.
82 struct GNUNET_PeerIdentity peer;
85 * How many hops (1-3) is this peer away? in network byte order
87 uint32_t distance GNUNET_PACKED;
93 * Message exchanged between DV services (via core), requesting a
94 * message to be routed.
99 * Type: GNUNET_MESSAGE_TYPE_DV_ROUTE
101 struct GNUNET_MessageHeader header;
104 * Expected (remaining) distance. Must be always smaller than
105 * DEFAULT_FISHEYE_DEPTH, should be zero at the target. Must
106 * be decremented by one at each hop. Peers must not forward
107 * these messages further once the counter has reached zero.
109 uint32_t distance GNUNET_PACKED;
112 * The (actual) target of the message (this peer, if distance is zero).
114 struct GNUNET_PeerIdentity target;
117 * The (actual) sender of the message.
119 struct GNUNET_PeerIdentity sender;
123 GNUNET_NETWORK_STRUCT_END
127 * Linked list of messages to send to clients.
129 struct PendingMessage
132 * Pointer to next item in the list
134 struct PendingMessage *next;
137 * Pointer to previous item in the list
139 struct PendingMessage *prev;
142 * Actual message to be sent, allocated after this struct.
144 const struct GNUNET_MessageHeader *msg;
147 * Ultimate target for the message.
149 struct GNUNET_PeerIdentity ultimate_target;
152 * Unique ID of the message.
160 * Information about a direct neighbor (core-level, excluding
161 * DV-links, only DV-enabled peers).
163 struct DirectNeighbor
167 * Identity of the peer.
169 struct GNUNET_PeerIdentity peer;
172 * Head of linked list of messages to send to this peer.
174 struct PendingMessage *pm_head;
177 * Tail of linked list of messages to send to this peer.
179 struct PendingMessage *pm_tail;
182 * Transmit handle to core service.
184 struct GNUNET_CORE_TransmitHandle *cth;
187 * Routing table of the neighbor, NULL if not yet established.
188 * Keys are peer identities, values are 'struct Target' entries.
189 * Note that the distances in the targets are from the point-of-view
190 * of the peer, not from us!
192 struct GNUNET_CONTAINER_MultiHashMap *neighbor_table;
195 * Updated routing table of the neighbor, under construction,
196 * NULL if we are not currently building it.
197 * Keys are peer identities, values are 'struct Target' entries.
198 * Note that the distances in the targets are from the point-of-view
199 * of the peer, not from us!
201 struct GNUNET_CONTAINER_MultiHashMap *neighbor_table_consensus;
204 * Active consensus, if we are currently synchronizing the
207 struct GNUNET_CONSENSUS_Handle *consensus;
210 * ID of the task we use to (periodically) update our consensus
213 GNUNET_SCHEDULER_TaskIdentifier consensus_task;
216 * At what offset are we, with respect to inserting our own routes
217 * into the consensus?
219 unsigned int consensus_insertion_offset;
222 * At what distance are we, with respect to inserting our own routes
223 * into the consensus?
225 unsigned int consensus_insertion_distance;
228 * Number of messages currently in the 'pm_XXXX'-DLL.
230 unsigned int pm_queue_size;
233 * Flag set within 'check_target_removed' to trigger full global route refresh.
241 * A route includes information about the next hop,
242 * the target, and the ultimate distance to the
249 * Which peer do we need to forward the message to?
251 struct DirectNeighbor *next_hop;
254 * What would be the target, and how far is it away?
256 struct Target target;
259 * Offset of this target in the respective consensus set.
261 unsigned int set_offset;
267 * Set of targets we bring to a consensus; all targets in a set have a
268 * distance equal to the sets distance (which is implied by the array
275 * Array of targets in the set, may include NULL entries if a
276 * neighbor has disconnected; the targets are allocated with the
277 * respective container (all_routes), not here.
279 struct Route **targets;
282 * Size of the 'targets' array.
284 unsigned int array_length;
290 * Hashmap of all of our direct neighbors (no DV routing).
292 static struct GNUNET_CONTAINER_MultiHashMap *direct_neighbors;
295 * Hashmap with all routes that we currently support; contains
296 * routing information for all peers from distance 2
297 * up to distance DEFAULT_FISHEYE_DEPTH.
299 static struct GNUNET_CONTAINER_MultiHashMap *all_routes;
302 * Array of consensus sets we expose to the outside world. Sets
303 * are structured by the distance to the target.
305 static struct ConsensusSet consensi[DEFAULT_FISHEYE_DEPTH - 1];
308 * Handle to the core service api.
310 static struct GNUNET_CORE_Handle *core_api;
313 * The identity of our peer.
315 static struct GNUNET_PeerIdentity my_identity;
318 * The configuration for this service.
320 static const struct GNUNET_CONFIGURATION_Handle *cfg;
323 * The client, the DV plugin connected to us. Hopefully
324 * this client will never change, although if the plugin dies
325 * and returns for some reason it may happen.
327 static struct GNUNET_SERVER_Client *client_handle;
330 * Transmit handle to the plugin.
332 static struct GNUNET_SERVER_TransmitHandle *plugin_transmit_handle;
335 * Head of DLL for client messages
337 static struct PendingMessage *plugin_pending_head;
340 * Tail of DLL for client messages
342 static struct PendingMessage *plugin_pending_tail;
345 * Handle for the statistics service.
347 struct GNUNET_STATISTICS_Handle *stats;
351 * Get distance information from 'atsi'.
353 * @param atsi performance data
354 * @param atsi_count number of entries in atsi
355 * @return connected transport distance
358 get_atsi_distance (const struct GNUNET_ATS_Information *atsi,
359 unsigned int atsi_count)
363 for (i = 0; i < atsi_count; i++)
364 if (ntohl (atsi[i].type) == GNUNET_ATS_QUALITY_NET_DISTANCE)
365 return ntohl (atsi->value);
366 /* FIXME: we do not have distance data? Assume direct neighbor. */
367 return DIRECT_NEIGHBOR_COST;
372 * Function called to notify a client about the socket
373 * begin ready to queue more data. "buf" will be
374 * NULL and "size" zero if the socket was closed for
375 * writing in the meantime.
378 * @param size number of bytes available in buf
379 * @param buf where the callee should write the message
380 * @return number of bytes written to buf
383 transmit_to_plugin (void *cls, size_t size, void *buf)
386 struct PendingMessage *reply;
390 plugin_transmit_handle = NULL;
393 /* client disconnected */
397 while ( (NULL != (reply = plugin_pending_head)) &&
398 (size >= off + (msize = ntohs (reply->msg->size))))
400 GNUNET_CONTAINER_DLL_remove (plugin_pending_head, plugin_pending_tail,
402 memcpy (&cbuf[off], reply->msg, msize);
406 if (NULL != plugin_pending_head)
407 plugin_transmit_handle =
408 GNUNET_SERVER_notify_transmit_ready (client_handle,
410 GNUNET_TIME_UNIT_FOREVER_REL,
411 &transmit_to_plugin, NULL);
417 * Forward a message from another peer to the plugin.
419 * @param message the message to send to the plugin
420 * @param origin the original sender of the message
421 * @param distnace distance to the original sender of the message
424 send_data_to_plugin (const struct GNUNET_MessageHeader *message,
425 const struct GNUNET_PeerIdentity *origin,
428 struct GNUNET_DV_ReceivedMessage *received_msg;
429 struct PendingMessage *pending_message;
432 if (NULL == client_handle)
434 GNUNET_STATISTICS_update (stats,
435 "# messages discarded (no plugin)",
437 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
438 _("Refusing to queue messages, DV plugin not active.\n"));
441 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
442 "Delivering message from peer `%s'\n",
443 GNUNET_i2s (origin));
444 size = sizeof (struct GNUNET_DV_ReceivedMessage) +
445 ntohs (message->size);
446 if (size >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
448 GNUNET_break (0); /* too big */
451 pending_message = GNUNET_malloc (sizeof (struct PendingMessage) + size);
452 received_msg = (struct GNUNET_DV_ReceivedMessage *) &pending_message[1];
453 received_msg->header.size = htons (size);
454 received_msg->header.type = htons (GNUNET_MESSAGE_TYPE_DV_RECV);
455 received_msg->distance = htonl (distance);
456 received_msg->sender = *origin;
457 memcpy (&received_msg[1], message, ntohs (message->size));
458 GNUNET_CONTAINER_DLL_insert_tail (plugin_pending_head,
461 if (NULL == plugin_transmit_handle)
462 plugin_transmit_handle =
463 GNUNET_SERVER_notify_transmit_ready (client_handle, size,
464 GNUNET_TIME_UNIT_FOREVER_REL,
465 &transmit_to_plugin, NULL);
470 * Forward a control message to the plugin.
472 * @param message the message to send to the plugin
473 * @param distant_neighbor the original sender of the message
474 * @param distnace distance to the original sender of the message
477 send_control_to_plugin (const struct GNUNET_MessageHeader *message)
479 struct PendingMessage *pending_message;
482 if (NULL == client_handle)
484 GNUNET_STATISTICS_update (stats,
485 "# control messages discarded (no plugin)",
487 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
488 _("Refusing to queue messages, DV plugin not active.\n"));
491 size = ntohs (message->size);
492 pending_message = GNUNET_malloc (sizeof (struct PendingMessage) + size);
493 memcpy (&pending_message[1], message, size);
494 GNUNET_CONTAINER_DLL_insert_tail (plugin_pending_head,
497 if (NULL == plugin_transmit_handle)
498 plugin_transmit_handle =
499 GNUNET_SERVER_notify_transmit_ready (client_handle, size,
500 GNUNET_TIME_UNIT_FOREVER_REL,
501 &transmit_to_plugin, NULL);
506 * Give an ACK message to the plugin, we transmitted a message for it.
508 * @param target peer that received the message
509 * @param uid plugin-chosen UID for the message
512 send_ack_to_plugin (const struct GNUNET_PeerIdentity *target,
515 struct GNUNET_DV_AckMessage ack_msg;
517 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
518 "Delivering ACK for message to peer `%s'\n",
519 GNUNET_i2s (target));
520 ack_msg.header.size = htons (sizeof (ack_msg));
521 ack_msg.header.type = htons (GNUNET_MESSAGE_TYPE_DV_SEND_ACK);
522 ack_msg.uid = htonl (uid);
523 ack_msg.target = *target;
524 send_control_to_plugin (&ack_msg.header);
529 * Give a CONNECT message to the plugin.
531 * @param target peer that connected
532 * @param distance distance to the target
535 send_connect_to_plugin (const struct GNUNET_PeerIdentity *target,
538 struct GNUNET_DV_ConnectMessage cm;
540 if (NULL == client_handle)
542 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
543 "Delivering CONNECT about peer `%s'\n",
544 GNUNET_i2s (target));
545 cm.header.size = htons (sizeof (cm));
546 cm.header.type = htons (GNUNET_MESSAGE_TYPE_DV_CONNECT);
547 cm.distance = htonl (distance);
549 send_control_to_plugin (&cm.header);
554 * Give a DISCONNECT message to the plugin.
556 * @param target peer that disconnected
559 send_disconnect_to_plugin (const struct GNUNET_PeerIdentity *target)
561 struct GNUNET_DV_DisconnectMessage dm;
563 if (NULL == client_handle)
565 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
566 "Delivering DISCONNECT about peer `%s'\n",
567 GNUNET_i2s (target));
568 dm.header.size = htons (sizeof (dm));
569 dm.header.type = htons (GNUNET_MESSAGE_TYPE_DV_DISCONNECT);
570 dm.reserved = htonl (0);
572 send_control_to_plugin (&dm.header);
577 * Function called to transfer a message to another peer
580 * @param cls closure with the direct neighbor
581 * @param size number of bytes available in buf
582 * @param buf where the callee should write the message
583 * @return number of bytes written to buf
586 core_transmit_notify (void *cls, size_t size, void *buf)
588 struct DirectNeighbor *dn = cls;
590 struct PendingMessage *pending;
597 /* peer disconnected */
601 pending = dn->pm_head;
603 while ( (NULL != (pending = dn->pm_head)) &&
604 (size >= off + (msize = ntohs (pending->msg->size))))
607 GNUNET_CONTAINER_DLL_remove (dn->pm_head,
610 memcpy (&cbuf[off], pending->msg, msize);
611 if (0 != pending->uid)
612 send_ack_to_plugin (&pending->ultimate_target,
614 GNUNET_free (pending);
617 if (NULL != dn->pm_head)
619 GNUNET_CORE_notify_transmit_ready (core_api,
620 GNUNET_YES /* cork */,
622 GNUNET_TIME_UNIT_FOREVER_REL,
625 &core_transmit_notify, dn);
631 * Forward the given payload to the given target.
633 * @param target where to send the message
634 * @param uid unique ID for the message
635 * @param ultimate_target ultimate recipient for the message
636 * @param distance expected (remaining) distance to the target
637 * @param sender original sender of the message
638 * @param payload payload of the message
641 forward_payload (struct DirectNeighbor *target,
644 const struct GNUNET_PeerIdentity *sender,
645 const struct GNUNET_PeerIdentity *ultimate_target,
646 const struct GNUNET_MessageHeader *payload)
648 struct PendingMessage *pm;
649 struct RouteMessage *rm;
652 if ( (target->pm_queue_size >= MAX_QUEUE_SIZE) &&
653 (0 != memcmp (sender,
655 sizeof (struct GNUNET_PeerIdentity))) )
657 GNUNET_break (0 == uid);
660 msize = sizeof (struct RouteMessage) + ntohs (payload->size);
661 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
666 pm = GNUNET_malloc (sizeof (struct PendingMessage) + msize);
667 pm->ultimate_target = *ultimate_target;
669 pm->msg = (const struct GNUNET_MessageHeader *) &pm[1];
670 rm = (struct RouteMessage *) &pm[1];
671 rm->header.size = htons ((uint16_t) msize);
672 rm->header.type = htons (GNUNET_MESSAGE_TYPE_DV_ROUTE);
673 rm->distance = htonl (distance);
674 rm->target = target->peer;
675 rm->sender = *sender;
676 memcpy (&rm[1], payload, ntohs (payload->size));
677 GNUNET_CONTAINER_DLL_insert_tail (target->pm_head,
680 target->pm_queue_size++;
681 if (NULL == target->cth)
682 target->cth = GNUNET_CORE_notify_transmit_ready (core_api,
683 GNUNET_YES /* cork */,
685 GNUNET_TIME_UNIT_FOREVER_REL,
688 &core_transmit_notify, target);
693 * Find a free slot for storing a 'route' in the 'consensi'
694 * set at the given distance.
696 * @param distance distance to use for the set slot
699 get_consensus_slot (uint32_t distance)
701 struct ConsensusSet *cs;
704 cs = &consensi[distance];
706 while ( (i < cs->array_length) &&
707 (NULL != cs->targets[i]) ) i++;
708 if (i == cs->array_length)
709 GNUNET_array_grow (cs->targets,
711 cs->array_length * 2 + 2);
717 * Allocate a slot in the consensus set for a route.
719 * @param route route to initialize
720 * @param distance which consensus set to use
723 allocate_route (struct Route *route,
728 i = get_consensus_slot (distance);
729 route->set_offset = i;
730 consensi[distance].targets[i] = route;
731 route->target.distance = htonl (distance);
736 * Release a slot in the consensus set for a route.
738 * @param route route to release the slot from
741 release_route (struct Route *route)
743 consensi[ntohl (route->target.distance)].targets[route->set_offset] = NULL;
744 route->set_offset = UINT_MAX; /* indicate invalid slot */
749 * Move a route from one consensus set to another.
751 * @param route route to move
752 * @param new_distance new distance for the route (destination set)
755 move_route (struct Route *route,
756 uint32_t new_distance)
760 release_route (route);
761 i = get_consensus_slot (new_distance);
762 route->set_offset = i;
763 consensi[new_distance].targets[i] = route;
764 route->target.distance = htonl (new_distance);
769 * Start creating a new consensus from scratch.
771 * @param cls the 'struct DirectNeighbor' of the peer we're building
772 * a routing consensus with
773 * @param tc scheduler context
776 start_consensus (void *cls,
777 const struct GNUNET_SCHEDULER_TaskContext *tc);
781 * Method called whenever a peer connects.
784 * @param peer peer identity this notification is about
785 * @param atsi performance data
786 * @param atsi_count number of entries in atsi
789 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer,
790 const struct GNUNET_ATS_Information *atsi,
791 unsigned int atsi_count)
793 struct DirectNeighbor *neighbor;
797 /* Check for connect to self message */
798 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
800 distance = get_atsi_distance (atsi, atsi_count);
801 neighbor = GNUNET_CONTAINER_multihashmap_get (direct_neighbors,
803 if (NULL != neighbor)
808 if (DIRECT_NEIGHBOR_COST != distance)
809 return; /* is a DV-neighbor */
810 neighbor = GNUNET_malloc (sizeof (struct DirectNeighbor));
811 neighbor->peer = *peer;
812 GNUNET_assert (GNUNET_YES ==
813 GNUNET_CONTAINER_multihashmap_put (direct_neighbors,
816 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
817 route = GNUNET_CONTAINER_multihashmap_get (all_routes,
821 send_disconnect_to_plugin (peer);
822 release_route (route);
825 route->next_hop = neighbor;
826 neighbor->consensus_task = GNUNET_SCHEDULER_add_now (&start_consensus,
832 * Called for each 'target' in a neighbor table to free the associated memory.
835 * @param key key of the value
836 * @param value value to free
837 * @return GNUNET_OK to continue to iterate
840 free_targets (void *cls,
841 const struct GNUNET_HashCode *key,
850 * Multihashmap iterator for checking if a given route is
851 * (now) useful to this peer.
853 * @param cls the direct neighbor for the given route
854 * @param key key value stored under
855 * @param value a 'struct Target' that may or may not be useful; not that
856 * the distance in 'target' does not include the first hop yet
857 * @return GNUNET_YES to continue iteration, GNUNET_NO to stop
860 check_possible_route (void *cls, const struct GNUNET_HashCode * key, void *value)
862 struct DirectNeighbor *neighbor = cls;
863 struct Target *target = value;
866 route = GNUNET_CONTAINER_multihashmap_get (all_routes,
870 if (ntohl (route->target.distance) > ntohl (target->distance) + 1)
872 /* this 'target' is cheaper than the existing route; switch to alternative route! */
873 move_route (route, ntohl (target->distance) + 1);
874 route->next_hop = neighbor;
875 // FIXME: notify plugin about distance update?
877 return GNUNET_YES; /* got a route to this target already */
879 route = GNUNET_malloc (sizeof (struct Route));
880 route->next_hop = neighbor;
881 route->target.distance = htonl (ntohl (target->distance) + 1);
882 route->target.peer = target->peer;
883 allocate_route (route, ntohl (route->target.distance));
884 GNUNET_assert (GNUNET_YES ==
885 GNUNET_CONTAINER_multihashmap_put (all_routes,
886 &route->target.peer.hashPubKey,
888 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
889 send_connect_to_plugin (&route->target.peer, ntohl (target->distance));
895 * Multihashmap iterator for finding routes that were previously
896 * "hidden" due to a better route (called after a disconnect event).
899 * @param key peer identity of the given direct neighbor
900 * @param value a 'struct DirectNeighbor' to check for additional routes
901 * @return GNUNET_YES to continue iteration
904 refresh_routes (void *cls, const struct GNUNET_HashCode * key, void *value)
906 struct DirectNeighbor *neighbor = value;
908 if (NULL != neighbor->neighbor_table)
909 GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table,
910 &check_possible_route,
917 * Check if a target was removed from the set of the other peer; if so,
918 * if we also used it for our route, we need to remove it from our
919 * 'all_routes' set (and later check if an alternative path now exists).
921 * @param cls the 'struct DirectNeighbor'
922 * @param key peer identity for the target
923 * @param value a 'struct Target' previously reachable via the given neighbor
926 check_target_removed (void *cls,
927 const struct GNUNET_HashCode *key,
930 struct DirectNeighbor *neighbor = cls;
931 struct Target *new_target;
932 struct Route *current_route;
934 new_target = GNUNET_CONTAINER_multihashmap_get (neighbor->neighbor_table_consensus,
936 if (NULL == new_target)
938 /* target was revoked, check if it was used */
939 current_route = GNUNET_CONTAINER_multihashmap_get (all_routes,
941 if ( (NULL == current_route) ||
942 (current_route->next_hop != neighbor) )
944 /* didn't matter, wasn't used */
947 /* remove existing route */
948 GNUNET_assert (GNUNET_YES ==
949 GNUNET_CONTAINER_multihashmap_remove (all_routes, key, current_route));
950 send_disconnect_to_plugin (¤t_route->target.peer);
951 GNUNET_free (current_route);
952 neighbor->target_removed = GNUNET_YES;
960 * Check if a target was added to the set of the other peer; if it
961 * was added or impoves the existing route, do the needed updates.
963 * @param cls the 'struct DirectNeighbor'
964 * @param key peer identity for the target
965 * @param value a 'struct Target' now reachable via the given neighbor
968 check_target_added (void *cls,
969 const struct GNUNET_HashCode *key,
972 struct DirectNeighbor *neighbor = cls;
973 struct Target *target = value;
974 struct Route *current_route;
976 /* target was revoked, check if it was used */
977 current_route = GNUNET_CONTAINER_multihashmap_get (all_routes,
979 if (NULL != current_route)
982 if (current_route->next_hop == neighbor)
984 /* we had the same route before, no change */
985 if (ntohl (target->distance) != ntohl (current_route->target.distance))
987 current_route->target.distance = target->distance;
988 // FIXME: notify about distance change...
992 if (ntohl (current_route->target.distance) >= ntohl (target->distance))
994 /* alternative, shorter route exists, ignore */
997 /* new route is better than the existing one, take over! */
998 /* NOTE: minor security issue: malicious peers may advertise
999 very short routes to take over longer paths; as we don't
1000 check that the shorter routes actually work, a malicious
1001 direct neighbor can use this to DoS our long routes */
1002 current_route->next_hop = neighbor;
1003 current_route->target.distance = target->distance;
1004 // FIXME: notify about distance change
1008 current_route = GNUNET_malloc (sizeof (struct Route));
1009 current_route->next_hop = neighbor;
1010 current_route->target.peer = target->peer;
1011 current_route->target.distance = htonl (ntohl (target->distance) + 1);
1012 GNUNET_assert (GNUNET_YES ==
1013 GNUNET_CONTAINER_multihashmap_put (all_routes,
1014 ¤t_route->target.peer.hashPubKey,
1016 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1017 send_connect_to_plugin (¤t_route->target.peer,
1018 ntohl (current_route->target.distance));
1025 * The consensus has concluded, clean up and schedule the next one.
1027 * @param cls the 'struct GNUNET_DirectNeighbor' with which we created the consensus
1028 * @param group FIXME
1031 consensus_done_cb (void *cls,
1032 const struct GNUNET_CONSENSUS_Group *group)
1034 struct DirectNeighbor *neighbor = cls;
1036 GNUNET_CONSENSUS_destroy (neighbor->consensus);
1037 neighbor->consensus = NULL;
1038 /* remove targets that disappeared */
1039 neighbor->target_removed = GNUNET_NO;
1040 GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table,
1041 &check_target_removed,
1043 if (GNUNET_YES == neighbor->target_removed)
1045 /* check if we got an alternative for the removed routes */
1046 GNUNET_CONTAINER_multihashmap_iterate (direct_neighbors,
1050 /* add targets that appeared (and check for improved routes) */
1051 GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table_consensus,
1052 &check_target_added,
1054 if (NULL != neighbor->neighbor_table)
1056 GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table,
1059 GNUNET_CONTAINER_multihashmap_destroy (neighbor->neighbor_table);
1060 neighbor->neighbor_table = NULL;
1062 neighbor->neighbor_table = neighbor->neighbor_table_consensus;
1063 neighbor->neighbor_table_consensus = NULL;
1064 neighbor->consensus_task = GNUNET_SCHEDULER_add_delayed (GNUNET_DV_CONSENSUS_FREQUENCY,
1071 * We inserted the last element into the consensus, get ready to
1072 * insert the next element into the consensus or conclude if
1075 * @param cls the 'struct DirectNeighbor' of the peer we're building
1076 * a routing consensus with
1077 * @param success GNUNET_OK if the last element was added successfully,
1078 * GNUNET_SYSERR if we failed
1081 insert_next_element (void *cls,
1084 struct DirectNeighbor *neighbor = cls;
1085 struct GNUNET_CONSENSUS_Element element;
1087 while ( (DEFAULT_FISHEYE_DEPTH - 1 > neighbor->consensus_insertion_distance) &&
1088 (consensi[neighbor->consensus_insertion_distance].array_length == neighbor->consensus_insertion_offset) )
1090 neighbor->consensus_insertion_offset = 0;
1091 neighbor->consensus_insertion_distance++;
1092 /* skip over NULL entries */
1093 while ( (DEFAULT_FISHEYE_DEPTH - 1 > neighbor->consensus_insertion_distance) &&
1094 (consensi[neighbor->consensus_insertion_distance].array_length < neighbor->consensus_insertion_offset) &&
1095 (NULL == consensi[neighbor->consensus_insertion_distance].targets[neighbor->consensus_insertion_offset]) )
1096 neighbor->consensus_insertion_offset++;
1098 if (DEFAULT_FISHEYE_DEPTH - 1 == neighbor->consensus_insertion_distance)
1100 /* we're done, conclude! */
1101 GNUNET_CONSENSUS_conclude (neighbor->consensus,
1102 GNUNET_DV_CONSENSUS_FREQUENCY,
1108 element.size = sizeof (struct Target);
1109 element.data = &consensi[neighbor->consensus_insertion_distance].targets[neighbor->consensus_insertion_offset++]->target;
1111 /* skip over NULL entries */
1112 while ( (DEFAULT_FISHEYE_DEPTH - 1 > neighbor->consensus_insertion_distance) &&
1113 (consensi[neighbor->consensus_insertion_distance].array_length < neighbor->consensus_insertion_offset) &&
1114 (NULL == consensi[neighbor->consensus_insertion_distance].targets[neighbor->consensus_insertion_offset]) )
1115 neighbor->consensus_insertion_offset++;
1116 GNUNET_CONSENSUS_insert (neighbor->consensus,
1118 &insert_next_element,
1124 * We have learned a new route from the other peer. Add it to the
1125 * route set we're building.
1127 * @param cls the 'struct DirectNeighbor' we're building the consensus with
1128 * @param element the new element we have learned
1129 * @return GNUNET_OK if the valid is well-formed and should be added to the consensus,
1130 * GNUNET_SYSERR if the element should be ignored and not be propagated
1133 learn_route_cb (void *cls,
1134 const struct GNUNET_CONSENSUS_Element *element)
1136 struct DirectNeighbor *neighbor = cls;
1137 struct Target *target;
1139 if (sizeof (struct Target) != element->size)
1141 GNUNET_break_op (0);
1142 return GNUNET_SYSERR;
1144 target = GNUNET_malloc (sizeof (struct Target));
1145 memcpy (target, element->data, sizeof (struct Target));
1147 GNUNET_CONTAINER_multihashmap_put (neighbor->neighbor_table_consensus,
1148 &target->peer.hashPubKey,
1150 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1152 GNUNET_break_op (0);
1153 GNUNET_free (target);
1154 return GNUNET_SYSERR;
1161 * Start creating a new consensus from scratch.
1163 * @param cls the 'struct DirectNeighbor' of the peer we're building
1164 * a routing consensus with
1165 * @param tc scheduler context
1168 start_consensus (void *cls,
1169 const struct GNUNET_SCHEDULER_TaskContext *tc)
1171 struct DirectNeighbor *neighbor = cls;
1172 struct GNUNET_HashCode session_id;
1173 struct GNUNET_HashCode real_session_id;
1175 neighbor->consensus_task = GNUNET_SCHEDULER_NO_TASK;
1176 neighbor->consensus_insertion_offset = 0;
1177 neighbor->consensus_insertion_distance = 0;
1178 GNUNET_assert (NULL == neighbor->neighbor_table_consensus);
1179 GNUNET_assert (NULL == neighbor->consensus);
1180 neighbor->neighbor_table_consensus = GNUNET_CONTAINER_multihashmap_create (1024, GNUNET_YES);
1181 /* construct session ID seed as XOR of both peer's identities */
1182 GNUNET_CRYPTO_hash_xor (&my_identity.hashPubKey,
1183 &neighbor->peer.hashPubKey,
1185 /* make sure session ID is unique across applications by salting it with 'DV' */
1186 GNUNET_CRYPTO_hkdf (&real_session_id, sizeof (real_session_id),
1187 GCRY_MD_SHA512, GCRY_MD_SHA256,
1189 &session_id, sizeof (session_id),
1191 neighbor->consensus = GNUNET_CONSENSUS_create (cfg,
1197 if (NULL == neighbor->consensus)
1199 neighbor->consensus_task = GNUNET_SCHEDULER_add_delayed (GNUNET_DV_CONSENSUS_FREQUENCY,
1204 insert_next_element (neighbor, GNUNET_OK);
1209 * Core handler for DV data messages. Whatever this message
1210 * contains all we really have to do is rip it out of its
1211 * DV layering and give it to our pal the DV plugin to report
1214 * @param cls closure
1215 * @param peer peer which sent the message (immediate sender)
1216 * @param message the message
1217 * @param atsi transport ATS information (latency, distance, etc.)
1218 * @param atsi_count number of entries in atsi
1219 * @return GNUNET_OK on success, GNUNET_SYSERR if the other peer violated the protocol
1222 handle_dv_route_message (void *cls, const struct GNUNET_PeerIdentity *peer,
1223 const struct GNUNET_MessageHeader *message,
1224 const struct GNUNET_ATS_Information *atsi,
1225 unsigned int atsi_count)
1227 const struct RouteMessage *rm;
1228 const struct GNUNET_MessageHeader *payload;
1229 struct Route *route;
1231 if (ntohs (message->size) < sizeof (struct RouteMessage) + sizeof (struct GNUNET_MessageHeader))
1233 GNUNET_break_op (0);
1234 return GNUNET_SYSERR;
1236 rm = (const struct RouteMessage *) message;
1237 payload = (const struct GNUNET_MessageHeader *) &rm[1];
1238 if (ntohs (message->size) != sizeof (struct RouteMessage) + ntohs (payload->size))
1240 GNUNET_break_op (0);
1241 return GNUNET_SYSERR;
1243 if (0 == memcmp (&rm->target,
1245 sizeof (struct GNUNET_PeerIdentity)))
1247 /* message is for me, check reverse route! */
1248 route = GNUNET_CONTAINER_multihashmap_get (all_routes,
1249 &rm->sender.hashPubKey);
1252 /* don't have reverse route, drop */
1253 GNUNET_STATISTICS_update (stats,
1254 "# message discarded (no reverse route)",
1258 send_data_to_plugin (payload,
1260 ntohl (route->target.distance));
1263 route = GNUNET_CONTAINER_multihashmap_get (all_routes,
1264 &rm->target.hashPubKey);
1267 GNUNET_STATISTICS_update (stats,
1268 "# messages discarded (no route)",
1272 if (ntohl (route->target.distance) > ntohl (rm->distance) + 1)
1274 GNUNET_STATISTICS_update (stats,
1275 "# messages discarded (target too far)",
1279 forward_payload (route->next_hop,
1280 ntohl (route->target.distance),
1290 * Service server's handler for message send requests (which come
1291 * bubbling up to us through the DV plugin).
1293 * @param cls closure
1294 * @param client identification of the client
1295 * @param message the actual message
1298 handle_dv_send_message (void *cls, struct GNUNET_SERVER_Client *client,
1299 const struct GNUNET_MessageHeader *message)
1301 struct Route *route;
1302 const struct GNUNET_DV_SendMessage *msg;
1303 const struct GNUNET_MessageHeader *payload;
1305 if (ntohs (message->size) < sizeof (struct GNUNET_DV_SendMessage) + sizeof (struct GNUNET_MessageHeader))
1308 GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
1311 msg = (const struct GNUNET_DV_SendMessage *) message;
1312 GNUNET_break (0 != ntohl (msg->uid));
1313 payload = (const struct GNUNET_MessageHeader *) &msg[1];
1314 if (ntohs (message->size) != sizeof (struct GNUNET_DV_SendMessage) + ntohs (payload->size))
1317 GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
1320 route = GNUNET_CONTAINER_multihashmap_get (all_routes,
1321 &msg->target.hashPubKey);
1324 /* got disconnected, send ACK anyway?
1325 FIXME: What we really want is an 'NACK' here... */
1326 GNUNET_STATISTICS_update (stats,
1327 "# local messages discarded (no route)",
1329 send_ack_to_plugin (&msg->target, ntohl (msg->uid));
1330 GNUNET_SERVER_receive_done (client, GNUNET_OK);
1333 forward_payload (route->next_hop,
1334 ntohl (route->target.distance),
1339 GNUNET_SERVER_receive_done (client, GNUNET_OK);
1344 * Multihashmap iterator for freeing routes that go via a particular
1345 * neighbor that disconnected and is thus no longer available.
1347 * @param cls the direct neighbor that is now unavailable
1348 * @param key key value stored under
1349 * @param value a 'struct Route' that may or may not go via neighbor
1351 * @return GNUNET_YES to continue iteration, GNUNET_NO to stop
1354 cull_routes (void *cls, const struct GNUNET_HashCode * key, void *value)
1356 struct DirectNeighbor *neighbor = cls;
1357 struct Route *route = value;
1359 if (route->next_hop != neighbor)
1360 return GNUNET_YES; /* not affected */
1361 GNUNET_assert (GNUNET_YES ==
1362 GNUNET_CONTAINER_multihashmap_remove (all_routes, key, value));
1363 release_route (route);
1364 send_disconnect_to_plugin (&route->target.peer);
1365 GNUNET_free (route);
1371 * Cleanup all of the data structures associated with a given neighbor.
1373 * @param neighbor neighbor to clean up
1376 cleanup_neighbor (struct DirectNeighbor *neighbor)
1378 struct PendingMessage *pending;
1380 while (NULL != (pending = neighbor->pm_head))
1382 neighbor->pm_queue_size--;
1383 GNUNET_CONTAINER_DLL_remove (neighbor->pm_head,
1386 GNUNET_free (pending);
1388 GNUNET_CONTAINER_multihashmap_iterate (all_routes,
1391 if (NULL != neighbor->cth)
1393 GNUNET_CORE_notify_transmit_ready_cancel (neighbor->cth);
1394 neighbor->cth = NULL;
1396 if (NULL != neighbor->neighbor_table_consensus)
1398 GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table_consensus,
1401 GNUNET_CONTAINER_multihashmap_destroy (neighbor->neighbor_table_consensus);
1402 neighbor->neighbor_table_consensus = NULL;
1404 if (NULL != neighbor->neighbor_table)
1406 GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table,
1409 GNUNET_CONTAINER_multihashmap_destroy (neighbor->neighbor_table);
1410 neighbor->neighbor_table = NULL;
1412 if (GNUNET_SCHEDULER_NO_TASK != neighbor->consensus_task)
1414 GNUNET_SCHEDULER_cancel (neighbor->consensus_task);
1415 neighbor->consensus_task = GNUNET_SCHEDULER_NO_TASK;
1417 if (NULL != neighbor->consensus)
1419 GNUNET_CONSENSUS_destroy (neighbor->consensus);
1420 neighbor->consensus = NULL;
1422 GNUNET_assert (GNUNET_YES ==
1423 GNUNET_CONTAINER_multihashmap_remove (direct_neighbors,
1424 &neighbor->peer.hashPubKey,
1426 GNUNET_free (neighbor);
1431 * Method called whenever a given peer disconnects.
1433 * @param cls closure
1434 * @param peer peer identity this notification is about
1437 handle_core_disconnect (void *cls, const struct GNUNET_PeerIdentity *peer)
1439 struct DirectNeighbor *neighbor;
1441 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1442 "Received core peer disconnect message for peer `%s'!\n",
1444 /* Check for disconnect from self message */
1445 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1448 GNUNET_CONTAINER_multihashmap_get (direct_neighbors, &peer->hashPubKey);
1449 if (NULL == neighbor)
1451 /* must have been a DV-neighbor, ignore */
1454 cleanup_neighbor (neighbor);
1455 GNUNET_CONTAINER_multihashmap_iterate (direct_neighbors,
1462 * Multihashmap iterator for freeing routes. Should never be called.
1465 * @param key key value stored under
1466 * @param value the route to be freed
1468 * @return GNUNET_YES to continue iteration, GNUNET_NO to stop
1471 free_route (void *cls, const struct GNUNET_HashCode * key, void *value)
1473 struct Route *route = value;
1476 GNUNET_assert (GNUNET_YES ==
1477 GNUNET_CONTAINER_multihashmap_remove (all_routes, key, value));
1478 release_route (route);
1479 send_disconnect_to_plugin (&route->target.peer);
1480 GNUNET_free (route);
1486 * Multihashmap iterator for freeing direct neighbors. Should never be called.
1489 * @param key key value stored under
1490 * @param value the direct neighbor to be freed
1492 * @return GNUNET_YES to continue iteration, GNUNET_NO to stop
1495 free_direct_neighbors (void *cls, const struct GNUNET_HashCode * key, void *value)
1497 struct DirectNeighbor *neighbor = value;
1500 cleanup_neighbor (neighbor);
1506 * Task run during shutdown.
1512 shutdown_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
1514 struct PendingMessage *pending;
1517 GNUNET_CONTAINER_multihashmap_iterate (direct_neighbors,
1518 &free_direct_neighbors, NULL);
1519 GNUNET_CONTAINER_multihashmap_destroy (direct_neighbors);
1520 GNUNET_CONTAINER_multihashmap_iterate (all_routes,
1522 GNUNET_CONTAINER_multihashmap_destroy (all_routes);
1523 GNUNET_CORE_disconnect (core_api);
1525 GNUNET_STATISTICS_destroy (stats, GNUNET_NO);
1527 while (NULL != (pending = plugin_pending_head))
1529 GNUNET_CONTAINER_DLL_remove (plugin_pending_head,
1530 plugin_pending_tail,
1532 GNUNET_free (pending);
1534 for (i=0;i<DEFAULT_FISHEYE_DEPTH - 1;i++)
1535 GNUNET_array_grow (consensi[i].targets,
1536 consensi[i].array_length,
1542 * Handle START-message. This is the first message sent to us
1543 * by the client (can only be one!).
1545 * @param cls closure (always NULL)
1546 * @param client identification of the client
1547 * @param message the actual message
1550 handle_start (void *cls, struct GNUNET_SERVER_Client *client,
1551 const struct GNUNET_MessageHeader *message)
1553 if (NULL != client_handle)
1555 /* forcefully drop old client */
1556 GNUNET_SERVER_client_disconnect (client_handle);
1557 GNUNET_SERVER_client_drop (client_handle);
1559 client_handle = client;
1560 GNUNET_SERVER_client_keep (client_handle);
1561 GNUNET_SERVER_receive_done (client, GNUNET_OK);
1566 * Called on core init.
1569 * @param server legacy
1570 * @param identity this peer's identity
1573 core_init (void *cls, struct GNUNET_CORE_Handle *server,
1574 const struct GNUNET_PeerIdentity *identity)
1576 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1578 GNUNET_i2s (identity));
1579 my_identity = *identity;
1584 * Process dv requests.
1586 * @param cls closure
1587 * @param server the initialized server
1588 * @param c configuration to use
1591 run (void *cls, struct GNUNET_SERVER_Handle *server,
1592 const struct GNUNET_CONFIGURATION_Handle *c)
1594 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
1595 {&handle_dv_route_message, GNUNET_MESSAGE_TYPE_DV_ROUTE, 0},
1598 static struct GNUNET_SERVER_MessageHandler plugin_handlers[] = {
1599 {&handle_start, NULL,
1600 GNUNET_MESSAGE_TYPE_DV_START,
1601 sizeof (struct GNUNET_MessageHeader) },
1602 { &handle_dv_send_message, NULL,
1603 GNUNET_MESSAGE_TYPE_DV_SEND,
1609 direct_neighbors = GNUNET_CONTAINER_multihashmap_create (128, GNUNET_NO);
1610 all_routes = GNUNET_CONTAINER_multihashmap_create (65536, GNUNET_NO);
1611 core_api = GNUNET_CORE_connect (cfg, NULL,
1613 &handle_core_connect,
1614 &handle_core_disconnect,
1619 if (NULL == core_api)
1621 stats = GNUNET_STATISTICS_create ("dv", cfg);
1622 GNUNET_SERVER_add_handlers (server, plugin_handlers);
1623 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_FOREVER_REL,
1624 &shutdown_task, NULL);
1629 * The main function for the dv service.
1631 * @param argc number of arguments from the command line
1632 * @param argv command line arguments
1633 * @return 0 ok, 1 on error
1636 main (int argc, char *const *argv)
1638 return (GNUNET_OK ==
1639 GNUNET_SERVICE_run (argc, argv, "dv", GNUNET_SERVICE_OPTION_NONE,
1640 &run, NULL)) ? 0 : 1;
1643 /* end of gnunet-service-dv.c */