2 This file is part of GNUnet.
3 (C) 2009-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 dht/gnunet-service-xdht_neighbours.c
23 * @brief GNUnet DHT service's finger and friend table management code
24 * @author Supriti Singh
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_nse_service.h"
34 #include "gnunet_ats_service.h"
35 #include "gnunet_core_service.h"
36 #include "gnunet_datacache_lib.h"
37 #include "gnunet_transport_service.h"
38 #include "gnunet_hello_lib.h"
39 #include "gnunet_dht_service.h"
40 #include "gnunet_statistics_service.h"
41 #include "gnunet-service-xdht.h"
42 #include "gnunet-service-xdht_clients.h"
43 #include "gnunet-service-xdht_datacache.h"
44 #include "gnunet-service-xdht_hello.h"
45 #include "gnunet-service-xdht_neighbours.h"
46 #include "gnunet-service-xdht_nse.h"
47 #include "gnunet-service-xdht_routing.h"
52 1. Use a global array of all known peers in find_successor, Only when
53 a new peer is added in finger or friend peer map, then re calculate
54 the array. Or else use the old one.
55 2. Should we be using const in all the handle for the message we received
56 * and then copy the fields and make changes to the fields instead of sending
58 * 3. Everywhere you are storing yourself as the first element in the trail.
59 * It is obviously taking too much space. Try to remove it and think of something
63 * Maximum possible fingers of a peer.
65 #define MAX_FINGERS 64
68 * Maximum allowed number of pending messages per friend peer.
70 #define MAXIMUM_PENDING_PER_FRIEND 64
73 * How long at least to wait before sending another find finger trail request.
75 #define DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
78 * How long at most to wait before sending another find finger trail request.
80 #define DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 10)
83 * How long at most to wait for transmission of a GET request to another peer?
85 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
88 * FIXME: Use this variable. Should it be moved to routing.c
89 * Threshold on routing table entries for a peer.
91 #define ROUTING_TABLE_THRESHOLD 64
94 * FIXME: Use this variable. When adding an entry in finger table, check
95 * this threshold value. At the moment, its just a random value. Also,
96 * implement teardown feature from the paper.
97 * Threshold on number of peers in a trail length
99 #define TRAIL_LENGTH_THRESHOLD 64
102 GNUNET_NETWORK_STRUCT_BEGIN
107 struct PeerPutMessage
110 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
112 struct GNUNET_MessageHeader header;
117 uint32_t options GNUNET_PACKED;
122 uint32_t type GNUNET_PACKED;
127 uint32_t hop_count GNUNET_PACKED;
130 * Replication level for this message
132 uint32_t desired_replication_level GNUNET_PACKED;
135 * Length of the PUT path that follows (if tracked).
137 uint32_t put_path_length GNUNET_PACKED;
142 struct GNUNET_PeerIdentity source_peer;
145 * Current destination
147 struct GNUNET_PeerIdentity current_destination;
150 * Current destination type
152 enum current_destination_type current_destination_type;
155 * When does the content expire?
157 struct GNUNET_TIME_AbsoluteNBO expiration_time;
160 * The key to store the value under.
162 struct GNUNET_HashCode key GNUNET_PACKED;
165 /* put path (if tracked) */
175 struct PeerGetResultMessage
178 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT
180 struct GNUNET_MessageHeader header;
183 * Peer which is sending get result message.
185 struct GNUNET_PeerIdentity source_peer;
188 * Peer which will receive the get result message.
190 struct GNUNET_PeerIdentity destination_peer;
193 * Current index in get path.
195 unsigned int current_path_index;
198 * Length of the GET path that follows (if tracked).
200 uint32_t get_path_length GNUNET_PACKED;
203 * When does the content expire?
205 struct GNUNET_TIME_AbsoluteNBO expiration_time;
208 * The key of the corresponding GET request.
210 struct GNUNET_HashCode key;
212 /* put path (if tracked) */
214 /* get path (if tracked) */
224 struct PeerGetMessage
227 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
229 struct GNUNET_MessageHeader header;
234 struct GNUNET_PeerIdentity source_peer;
237 * Total number of peers in get path.
239 unsigned int get_path_length;
244 struct GNUNET_PeerIdentity current_destination;
249 enum current_destination_type dest_type;
252 * When does the content expire?
254 struct GNUNET_TIME_AbsoluteNBO expiration_time;
257 * The key we are looking for.
259 struct GNUNET_HashCode key;
267 * P2P Trail setup message
269 struct PeerTrailSetupMessage
273 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
275 struct GNUNET_MessageHeader header;
278 * Source peer which wants to setup the trail to one of its finger.
280 struct GNUNET_PeerIdentity source_peer;
283 * Successor of this finger value will be our finger peer.
285 uint64_t destination_finger;
288 * Peer which gets this message can be either an intermediate finger or friend.
290 enum current_destination_type current_destination_type;
293 * Peer to which this packet is forwarded.
295 struct GNUNET_PeerIdentity current_destination;
298 * Index into finger peer map.
300 unsigned int finger_map_index;
303 * Number of entries in trail list.
305 uint32_t trail_length GNUNET_PACKED;
311 * P2P Trail Setup Result message
313 struct PeerTrailSetupResultMessage
317 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_RESULT_SETUP
319 struct GNUNET_MessageHeader header;
322 * Finger to which we have found the path.
324 struct GNUNET_PeerIdentity finger_identity;
327 * Peer which was looking for the trail to finger.
329 struct GNUNET_PeerIdentity destination_peer;
332 * Trail index which points to next destination to send this message.
334 unsigned int current_index;
337 * Index into finger peer map
339 unsigned int finger_map_index;
342 * Number of entries in trail list.
344 uint32_t trail_length GNUNET_PACKED;
350 * P2P Verify Successor message.
352 struct PeerVerifySuccessorMessage
356 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
358 struct GNUNET_MessageHeader header;
361 * Source peer which wants to verify its successor.
363 struct GNUNET_PeerIdentity source_peer;
366 * My current successor.
368 struct GNUNET_PeerIdentity successor;
371 * Total number of peers in trail to current successor.
373 unsigned int trail_length;
376 * Trail index which points to next destination to send this message.
378 unsigned int current_trail_index;
384 * P2P Verify Successor Result message.
386 struct PeerVerifySuccessorResultMessage
390 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
392 struct GNUNET_MessageHeader header;
395 * Destination peer which sent the request to verify its successor.
397 struct GNUNET_PeerIdentity destination_peer;
400 * Successor to which PeerVerifySuccessorMessage was sent.
402 struct GNUNET_PeerIdentity source_successor;
405 * source_successor's predecessor
407 struct GNUNET_PeerIdentity my_predecessor;
410 * Total number of peers in trail.
411 * If source_successor is not destination peer, then trail is from destination_peer
413 * If source_successor is destination peer, then trail is from destination_peer
414 * to source_successor.
416 unsigned int trail_length;
419 * Trail index which points to next destination to send this message.
421 unsigned int current_index;
426 * P2P Notify New Successor message.
428 struct PeerNotifyNewSuccessorMessage
431 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
433 struct GNUNET_MessageHeader header;
436 * Source peer which wants to notify its new successor.
438 struct GNUNET_PeerIdentity source_peer;
441 * New successor identity.
443 struct GNUNET_PeerIdentity destination_peer;
446 * Number of peers in trail from source_peer to new successor.
448 unsigned int trail_length;
451 * Trail index which points to next destination to send this message.
453 unsigned int current_index;
458 GNUNET_NETWORK_STRUCT_END
462 * Linked list of messages to send to a particular other peer.
464 struct P2PPendingMessage
467 * Pointer to next item in the list
469 struct P2PPendingMessage *next;
472 * Pointer to previous item in the list
474 struct P2PPendingMessage *prev;
477 * When does this message time out?
479 struct GNUNET_TIME_Absolute timeout;
482 * Message importance level. FIXME: used? useful?
484 unsigned int importance;
487 * Actual message to be sent, allocated at the end of the struct:
488 * // msg = (cast) &pm[1];
489 * // memcpy (&pm[1], data, len);
491 const struct GNUNET_MessageHeader *msg;
497 * Linked List of peers which are part of trail to reach a particular Finger.
502 * Pointer to next item in the list
504 struct TrailPeerList *next;
507 * Pointer to previous item in the list
509 struct TrailPeerList *prev;
512 * An element in this trail list
514 struct GNUNET_PeerIdentity peer;
520 * Entry in friend_peermap.
527 struct GNUNET_PeerIdentity id;
530 * Count of outstanding messages for this friend.
532 unsigned int pending_count;
535 * Head of pending messages to be sent to this friend.
537 struct P2PPendingMessage *head;
540 * Tail of pending messages to be sent to this friend.
542 struct P2PPendingMessage *tail;
545 * Core handle for sending messages to this friend.
547 struct GNUNET_CORE_TransmitHandle *th;
553 * Entry in finger_peermap.
560 struct GNUNET_PeerIdentity finger_identity;
563 * Index in finger peer map
565 unsigned int finger_map_index;
568 * Total number of entries in trail from [me,finger]
570 unsigned int trail_length;
573 * Head of trail to reach this finger.
575 struct TrailPeerList *head;
578 * Tail of trail to reach this finger.
580 struct TrailPeerList *tail;
586 * FIXME: Think of a better name.
587 * Data structure passed to sorting algorithm in find_successor.
592 * 64 bit value of peer identity
597 * Type : MY_ID, FINGER, FINGER, Value
599 enum current_destination_type type;
602 * Pointer to original data structure linked to peer id.
609 * Task that sends FIND FINGER TRAIL requests.
611 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
615 * Task that periodically verifies my successor.
617 static GNUNET_SCHEDULER_TaskIdentifier verify_successor;
620 * Identity of this peer.
622 static struct GNUNET_PeerIdentity my_identity;
625 * Hash map of all the friends of a peer
627 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
630 * Hash map of all the fingers of a peer
632 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
637 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
642 static struct GNUNET_CORE_Handle *core_api;
645 * FIXME: Is it safe to assume its initialized to 0 by default.
646 * The current finger index that we have found trail to.
648 static unsigned int current_finger_index;
652 * Called when core is ready to send a message we asked for
653 * out to the destination.
655 * @param cls the 'struct FriendInfo' of the target friend
656 * @param size number of bytes available in buf
657 * @param buf where the callee should write the message
658 * @return number of bytes written to buf
661 core_transmit_notify (void *cls, size_t size, void *buf)
663 struct FriendInfo *peer = cls;
665 struct P2PPendingMessage *pending;
670 while ((NULL != (pending = peer->head)) &&
671 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
673 peer->pending_count--;
674 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
675 GNUNET_free (pending);
679 /* no messages pending */
685 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
686 GNUNET_CORE_PRIO_BEST_EFFORT,
687 GNUNET_TIME_absolute_get_remaining
688 (pending->timeout), &peer->id,
689 ntohs (pending->msg->size),
690 &core_transmit_notify, peer);
691 GNUNET_break (NULL != peer->th);
695 while ((NULL != (pending = peer->head)) &&
696 (size - off >= (msize = ntohs (pending->msg->size))))
698 GNUNET_STATISTICS_update (GDS_stats,
700 ("# Bytes transmitted to other peers"), msize,
702 memcpy (&cbuf[off], pending->msg, msize);
704 peer->pending_count--;
705 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
706 GNUNET_free (pending);
708 if (peer->head != NULL)
711 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
712 GNUNET_CORE_PRIO_BEST_EFFORT,
713 GNUNET_TIME_absolute_get_remaining
714 (pending->timeout), &peer->id, msize,
715 &core_transmit_notify, peer);
716 GNUNET_break (NULL != peer->th);
723 * Transmit all messages in the friend's message queue.
725 * @param peer message queue to process
728 process_friend_queue (struct FriendInfo *peer)
730 struct P2PPendingMessage *pending;
732 if (NULL == (pending = peer->head))
734 if (NULL != peer->th)
737 GNUNET_STATISTICS_update (GDS_stats,
739 ("# Bytes of bandwidth requested from core"),
740 ntohs (pending->msg->size), GNUNET_NO);
742 /* FIXME: Are we correctly initializing importance and pending. */
744 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
746 GNUNET_TIME_absolute_get_remaining
747 (pending->timeout), &peer->id,
748 ntohs (pending->msg->size),
749 &core_transmit_notify, peer);
750 GNUNET_break (NULL != peer->th);
755 * Construct a trail message and forward it to a friend.
756 * @param source_peer Peer which wants to set up the trail to one of its finger.
757 * @param destination_finger Value whose successor we are searching the network.
758 * @param current_destination Peer which gets this message.
759 * @param target_friend Current friend to which this message should be forwarded.
760 * @param trail_length Numbers of peers in the trail.
761 * @param trail_peer_list peers this request has traversed so far
762 * @param finger_map_index Index in finger peer map
763 * @param type Type of current destination can be either FRIEND or FINGER
766 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity *source_peer,
767 uint64_t destination_finger,
768 struct GNUNET_PeerIdentity *current_destination,
769 struct FriendInfo *target_friend,
770 unsigned int trail_length,
771 struct GNUNET_PeerIdentity *trail_peer_list,
772 unsigned int finger_map_index,
773 enum current_destination_type type)
775 struct P2PPendingMessage *pending;
776 struct PeerTrailSetupMessage *tsm;
777 struct GNUNET_PeerIdentity *peer_list;
780 msize = sizeof (struct PeerTrailSetupMessage) +
781 (trail_length * sizeof (struct GNUNET_PeerIdentity));
783 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
789 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
791 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
795 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
796 pending->importance = 0; /* FIXME */
797 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
798 tsm = (struct PeerTrailSetupMessage *) &pending[1];
799 pending->msg = &tsm->header;
800 tsm->header.size = htons (msize);
801 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
802 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
803 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
804 memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
805 tsm->current_destination_type = htonl (type);
806 tsm->trail_length = htonl (trail_length);
807 tsm->finger_map_index = htonl (finger_map_index);
809 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
810 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
811 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
812 target_friend->pending_count++;
813 process_friend_queue (target_friend);
819 * Construct a trail setup result message and forward it to a friend.
820 * @param destination_peer Peer which will get the trail to one of its finger.
821 * @param source_finger Peer to which the trail has been setup to.
822 * @param target_friend Friend to which this message should be forwarded.
823 * @param trail_length Numbers of peers in the trail.
824 * @param trail_peer_list Peers which are part of the trail from source to destination.
825 * @param current_trail_index Index in the trial list at which receiving peer should
826 * read the next element.
827 * @param finger_map_index Index in finger peer map
830 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity *destination_peer,
831 struct GNUNET_PeerIdentity *source_finger,
832 struct FriendInfo *target_friend,
833 unsigned int trail_length,
834 struct GNUNET_PeerIdentity *trail_peer_list,
835 unsigned int current_trail_index,
836 unsigned int finger_map_index)
838 struct P2PPendingMessage *pending;
839 struct PeerTrailSetupResultMessage *tsrm;
840 struct GNUNET_PeerIdentity *peer_list;
843 msize = sizeof (struct PeerTrailSetupResultMessage) +
844 (trail_length * sizeof (struct GNUNET_PeerIdentity));
846 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
852 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
854 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
858 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
859 pending->importance = 0;
860 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
861 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
862 pending->msg = &tsrm->header;
863 tsrm->header.size = htons (msize);
864 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
865 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
866 memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity));
867 tsrm->trail_length = htonl (trail_length);
868 tsrm->current_index = htonl (current_trail_index);
869 tsrm->finger_map_index = htonl (finger_map_index);
870 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
871 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
873 /* Send the message to chosen friend. */
874 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
875 target_friend->pending_count++;
876 process_friend_queue (target_friend);
881 * Construct a PeerVerifySuccessor message and send it to friend.
882 * @param source_peer Peer which wants to verify its successor
883 * @param successor Peer which is our current successor
884 * @param target_friend Friend to which this message should be forwarded.
885 * @param trail_peer_list Peer which are part of trail from source to destination
886 * @param trail_length Number of peers in the trail list.
887 * @param current_trail_index Index in the trial list at which receiving peer should
888 * read the next element.
890 void GDS_NEIGHBOURS_send_verify_successor(struct GNUNET_PeerIdentity *source_peer,
891 struct GNUNET_PeerIdentity *successor,
892 struct FriendInfo *target_friend,
893 struct GNUNET_PeerIdentity *trail_peer_list,
894 unsigned int trail_length,
895 unsigned int current_trail_index)
897 struct PeerVerifySuccessorMessage *vsm;
898 struct P2PPendingMessage *pending;
899 struct GNUNET_PeerIdentity *peer_list;
902 msize = sizeof (struct PeerVerifySuccessorMessage) +
903 (trail_length * sizeof (struct GNUNET_PeerIdentity));
905 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
911 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
913 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
917 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
918 pending->importance = 0; /* FIXME */
919 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
920 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
921 pending->msg = &vsm->header;
922 vsm->header.size = htons (msize);
923 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
924 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
925 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
926 vsm->trail_length = htonl (trail_length);
927 vsm->current_trail_index = htonl (current_trail_index);
928 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
929 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
931 /* Send the message to chosen friend. */
932 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
933 target_friend->pending_count++;
934 process_friend_queue (target_friend);
940 * Construct a PeerVerifySuccessorResult message and send it to friend.
941 * @param destination_peer Peer which sent verify successor message
942 * @param source_successor Peer to which verify successor message was sent.
943 * @param my_predecessor source_successor's predecessor.
944 * @param target_friend Friend to which this message should be forwarded.
945 * @param trail_peer_list Peers which are part of trail from source to destination
946 * @param trail_length Number of peers in the trail list.
947 * @param current_trail_index Index in the trial list at which receiving peer should
948 * get the next element.
950 void GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity *destination_peer,
951 struct GNUNET_PeerIdentity *source_successor,
952 struct GNUNET_PeerIdentity *my_predecessor,
953 struct FriendInfo *target_friend,
954 struct GNUNET_PeerIdentity *trail_peer_list,
955 unsigned int trail_length,
956 unsigned int current_trail_index)
958 struct PeerVerifySuccessorResultMessage *vsmr;
959 struct P2PPendingMessage *pending;
960 struct GNUNET_PeerIdentity *peer_list;
963 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
964 (trail_length * sizeof(struct GNUNET_PeerIdentity));
966 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
973 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
975 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
979 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
980 pending->importance = 0; /* FIXME */
981 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
982 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
983 pending->msg = &vsmr->header;
984 vsmr->header.size = htons (msize);
985 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
986 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
987 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
988 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
989 vsmr->trail_length = htonl (trail_length);
990 vsmr->current_index = htonl (current_trail_index);
992 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
993 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
995 /* Send the message to chosen friend. */
996 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
997 target_friend->pending_count++;
998 process_friend_queue (target_friend);
1003 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1004 * @param source_peer Peer which is sending notify message to its new successor.
1005 * @param destination_peer Peer which is the new destination.
1006 * @param target_friend Next friend to pass this message to.
1007 * @param peer_list List of peers in the trail to reach to destination_peer.
1008 * @param current_trail_index Index of peer_list for next target friend position.
1009 * @param trail_length Total number of peers in peer list
1012 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity *source_peer,
1013 struct GNUNET_PeerIdentity *destination_peer,
1014 struct FriendInfo *target_friend,
1015 struct GNUNET_PeerIdentity *trail_peer_list,
1016 unsigned int trail_length,
1017 unsigned int current_trail_index)
1019 struct PeerNotifyNewSuccessorMessage *nsm;
1020 struct P2PPendingMessage *pending;
1021 struct GNUNET_PeerIdentity *peer_list;
1024 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1025 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1027 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1033 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1035 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1039 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1040 pending->importance = 0; /* FIXME */
1041 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1042 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1043 pending->msg = &nsm->header;
1044 nsm->header.size = htons (msize);
1045 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1046 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1047 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1048 nsm->trail_length = htonl (trail_length);
1049 nsm->current_index = htonl (current_trail_index);
1051 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1052 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1054 /* Send the message to chosen friend. */
1055 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1056 target_friend->pending_count++;
1057 process_friend_queue (target_friend);
1062 * Randomly choose one of your friends from the friends_peer map
1065 static struct FriendInfo *
1066 select_random_friend()
1068 unsigned int current_size;
1069 unsigned int *index;
1071 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1072 struct GNUNET_PeerIdentity key_ret;
1073 struct FriendInfo *friend;
1075 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1077 /* Element stored at this index in friend_peermap should be selected friend. */
1078 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1080 /* Create an iterator for friend_peermap. */
1081 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1083 /* Set the position of iterator to index. */
1086 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1095 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1105 * Compute finger_identity to which we want to setup the trail
1106 * @return finger_identity
1109 compute_finger_identity()
1112 uint64_t *finger_identity64;
1114 finger_identity64 = GNUNET_malloc (sizeof (uint64_t));
1116 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1118 /*FIXME: Do we need a mod finger = ((my_id + pow(2, finger_index)) mod (pow (2, MAX_FINGERS))*/
1119 *finger_identity64 = (my_id64 + (unsigned long) pow (2,current_finger_index));
1121 return finger_identity64;
1126 * Compute immediate predecessor identity in the network.
1127 * @return peer identity of immediate predecessor.
1130 compute_predecessor_identity()
1133 uint64_t *predecessor;
1135 predecessor = GNUNET_malloc (sizeof (uint64_t));
1136 memcpy (&my_id, &my_identity, sizeof (uint64_t));
1137 /* FIXME: Do we need to use mod pow(2, MAX_FINGERS) here? */
1138 *predecessor = (my_id -1);
1145 * Periodically ping your successor to ask its current predecessor
1147 * @param cls closure for this task
1148 * @param tc the context under which the task is running
1151 send_verify_successor_message (void *cls,
1152 const struct GNUNET_SCHEDULER_TaskContext *tc )
1154 struct GNUNET_TIME_Relative next_send_time;
1155 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1156 struct GNUNET_PeerIdentity key_ret;
1157 struct FriendInfo *target_friend;
1158 struct GNUNET_PeerIdentity *next_hop;
1159 struct GNUNET_PeerIdentity *peer_list;
1160 unsigned int finger_trail_current_index;
1161 struct FingerInfo *finger;
1162 unsigned int finger_index;
1165 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1166 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1168 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1169 (const void **)&finger))
1171 if (0 == finger->finger_map_index)
1178 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1181 goto send_new_request;
1183 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->trail_length);
1185 struct TrailPeerList *iterate;
1186 iterate = finger->head;
1188 while ( i < (finger->trail_length))
1190 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1191 iterate = iterate->next;
1195 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1196 memcpy (next_hop, &peer_list[1], sizeof (struct GNUNET_PeerIdentity));
1197 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1198 finger_trail_current_index = 2;
1200 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1201 &(finger->finger_identity),
1204 finger->trail_length,
1205 finger_trail_current_index);
1208 /* FIXME: Use a random value so that this message is send not at the same
1209 interval as send_find_finger_trail_message. */
1211 next_send_time.rel_value_us =
1212 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1213 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1214 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1215 (current_finger_index + 50));
1218 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
1224 * Task to send a find finger trail message. We attempt to find trail
1225 * to our fingers, successor and predecessor in the network.
1227 * @param cls closure for this task
1228 * @param tc the context under which the task is running
1231 send_find_finger_trail_message (void *cls,
1232 const struct GNUNET_SCHEDULER_TaskContext *tc)
1234 struct FriendInfo *target_friend;
1235 struct GNUNET_TIME_Relative next_send_time;
1236 struct GNUNET_PeerIdentity *peer_list;
1237 uint64_t *finger_identity;
1238 unsigned int finger_map_index;
1240 if (1 == current_finger_index)
1242 /* We have started the process to find the successor. We should search
1243 for our predecessor. */
1244 finger_identity = compute_predecessor_identity();
1249 finger_identity = compute_finger_identity();
1253 target_friend = select_random_friend();
1256 finger_map_index = current_finger_index;
1257 current_finger_index = ( current_finger_index + 1) % MAX_FINGERS;
1259 /* We found a friend.*/
1260 if(NULL != target_friend)
1262 /* Add yourself and selected friend in the trail list. */
1263 unsigned int trail_length = 2;
1264 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
1265 memcpy (&peer_list[0], &(my_identity), sizeof (struct GNUNET_PeerIdentity));
1266 memcpy (&peer_list[1], &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
1268 GDS_NEIGHBOURS_send_trail_setup (&my_identity, *finger_identity, &(target_friend->id),
1269 target_friend, trail_length, peer_list,
1270 finger_map_index, FRIEND);
1273 /* FIXME: Should we be using current_finger_index to generate random interval.*/
1274 next_send_time.rel_value_us =
1275 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1276 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1277 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1278 (current_finger_index + 10));
1280 find_finger_trail_task =
1281 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1287 * Method called whenever a peer connects.
1289 * @param cls closure
1290 * @param peer_identity peer identity this notification is about
1293 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
1295 struct FriendInfo *friend;
1297 /* Check for connect to self message */
1298 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
1301 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
1303 /* If peer already exists in our friend_peermap, then exit. */
1304 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
1310 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
1313 friend = GNUNET_new (struct FriendInfo);
1314 friend->id = *peer_identity;
1316 GNUNET_assert (GNUNET_OK ==
1317 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
1318 peer_identity, friend,
1319 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1321 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
1322 if (1 == GNUNET_CONTAINER_multipeermap_size (friend_peermap))
1323 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
1328 * Method called whenever a peer disconnects.
1330 * @param cls closure
1331 * @param peer peer identity this notification is about
1334 handle_core_disconnect (void *cls,
1335 const struct GNUNET_PeerIdentity *peer)
1337 struct FriendInfo *remove_friend;
1338 struct FingerInfo *remove_finger;
1339 struct GNUNET_PeerIdentity key_ret;
1340 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1341 struct TrailPeerList *iterator;
1342 struct GNUNET_PeerIdentity *finger_identity;
1345 /* Check for self message. */
1346 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1349 /* Search for peer to remove in your friend_peermap. */
1351 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
1353 if (NULL == remove_friend)
1359 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
1360 finger_identity = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1361 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1362 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1364 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1365 (const void **)&remove_finger))
1367 iterator = remove_finger->head->next;
1368 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(iterator->peer), &(remove_friend->id)))
1370 memcpy (finger_identity, &(remove_finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
1371 GNUNET_assert (GNUNET_YES ==
1372 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
1379 /* Remove the friend from friend_peermap. */
1380 GNUNET_assert (GNUNET_YES ==
1381 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
1388 * To be called on core init/fail.
1390 * @param cls service closure
1391 * @param identity the public identity of this peer
1394 core_init (void *cls,
1395 const struct GNUNET_PeerIdentity *identity)
1397 my_identity = *identity;
1406 * FIXME: When we add a successor or predecessor should we check the entry in
1407 * finger map index. If we don't replace the old entry then should we notify
1408 * peer which think it is our predecessor or successor. Or will send verify
1409 * successor message will handle this case on its own.
1410 * * FIXME: For redundant routing, we may start looking for different
1411 * paths to reach to same finger. So, in send_find_finger, we are starting
1412 * the search for trail to a finger, even if we already have found trail to
1413 * reach to it. There are several reasons for doing so
1414 * 1. We may reach to a closer successor than we have at the moment. So, we
1415 * should keep looking for the successor.
1416 * 2. We may reach to the same successor but through a shorter path.
1417 * 3. As I don't know how keys are distributed and how put/get will react
1418 * because of this, I have to think further before implementing it.
1419 * Add an entry in finger table.
1420 * Add an entry into finger table
1421 * @param finger_identity Peer identity of finger
1422 * @param finger_trail Trail to reach the finger
1423 * @param trail_length Number of peers in the trail.
1424 * @param finger_map_index Index in finger peer map.
1427 void finger_table_add (struct GNUNET_PeerIdentity *finger_identity,
1428 struct GNUNET_PeerIdentity *finger_trail,
1429 unsigned int trail_length,
1430 unsigned int finger_map_index)
1432 struct FingerInfo *new_finger_entry;
1433 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1434 struct GNUNET_PeerIdentity key_ret;
1435 struct FingerInfo *existing_finger;
1439 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1441 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1443 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1444 (const void **)&existing_finger))
1446 /* If we already have an entry at the finger map index. */
1447 if ((finger_map_index == existing_finger->finger_map_index))
1449 /* Check if the finger entry are same. */
1450 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),finger_identity))
1452 /* Compare the trail length. */
1453 if ((trail_length == existing_finger->trail_length)||
1454 (trail_length > existing_finger->trail_length))
1458 else if (trail_length < existing_finger->trail_length)
1460 /* FIXME: As an optimization, when you add limit on trail length
1461 going through a particular friend, then check if the friend to
1462 reach the two trails are same or not. If not then choose one
1463 whose threshold value has not yet reached. Also, think about
1464 redundant routing, where you want to keep multiple paths
1465 to reach to the same finger. In that case you should allow multiple
1466 entries with same finger identity. */
1467 if ( GNUNET_YES == GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
1468 &(existing_finger->finger_identity),
1477 /* FIXME: Here you are if you got different finger identity then one
1478 you already have at that index. Then you should choose the
1479 one which is closest. */
1486 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
1487 memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
1490 while (i < trail_length)
1492 struct TrailPeerList *element;
1493 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1494 element->next = NULL;
1495 element->prev = NULL;
1497 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
1498 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head, new_finger_entry->tail, element);
1502 new_finger_entry->finger_map_index = finger_map_index;
1503 new_finger_entry->trail_length = trail_length;
1505 /* FIXME: Here we are keeping multiple hashmap option so that there are
1506 multiple routes to reach to same finger, redundant routing. */
1507 GNUNET_assert (GNUNET_OK ==
1508 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
1509 &(new_finger_entry->finger_identity),
1511 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
1513 if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap)
1514 && (new_finger_entry->finger_map_index!= 1))
1516 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1522 * Compare two peer identities.
1523 * @param p1 Peer identity
1524 * @param p2 Peer identity
1525 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
1528 compare_peer_id (const void *p1, const void *p2)
1530 struct Sorting_List *p11;
1531 struct Sorting_List *p22;
1533 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
1534 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
1535 p11 = (struct Sorting_List *)p1;
1536 p22 = (struct Sorting_List *)p2;
1537 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
1538 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
1544 * Return the successor of value in all_known_peers.
1545 * @param all_known_peers list of all the peers
1546 * @param value value we have to search in the all_known_peers.
1549 static struct Sorting_List *
1550 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
1559 middle = (first + last)/2;
1561 while(first <= last)
1563 if(all_known_peers[middle].peer_id < value)
1567 else if(all_known_peers[middle].peer_id == value)
1569 if(middle == (size -1))
1571 return &all_known_peers[0];
1575 return &all_known_peers[middle+1];
1583 middle = (first + last)/2;
1590 * Find closest successor for the value.
1591 * @param value Value for which we are looking for successor
1592 * @param current_destination NULL if my_identity is successor else finger/friend
1594 * @param type Next destination type
1595 * @return Peer identity of next destination i.e. successor of value.
1597 static struct GNUNET_PeerIdentity *
1598 find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination,
1599 enum current_destination_type *type)
1601 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1602 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1603 struct GNUNET_PeerIdentity key_ret;
1604 struct FriendInfo *friend;
1605 struct FingerInfo *finger;
1606 unsigned int finger_index;
1607 unsigned int friend_index;
1608 struct Sorting_List *successor;
1612 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
1613 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
1614 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
1617 struct Sorting_List all_known_peers[size];
1620 for (k = 0; k < size; k++)
1621 all_known_peers[k].peer_id = 0;
1623 /* Copy your identity at 0th index in all_known_peers. */
1625 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
1626 all_known_peers[j].type = MY_ID;
1627 all_known_peers[j].data = 0;
1631 all_known_peers[j].peer_id = value;
1632 all_known_peers[j].type = VALUE;
1633 all_known_peers[j].data = 0;
1636 /* Iterate over friend peer map and copy all the elements into array. */
1637 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1638 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
1640 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1642 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
1643 all_known_peers[j].type = FRIEND;
1644 all_known_peers[j].data = friend;
1649 /* Iterate over finger map and copy all the entries into all_known_peers array. */
1650 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1651 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1653 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1655 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
1656 all_known_peers[j].type = FINGER;
1657 all_known_peers[j].data = finger;
1662 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1663 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
1665 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
1667 /* search value in all_known_peers array. */
1668 successor = find_closest_successor (all_known_peers, value, size);
1670 if (successor->type == MY_ID)
1675 else if (successor->type == FRIEND)
1678 struct FriendInfo *target_friend;
1679 target_friend = (struct FriendInfo *)successor->data;
1680 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
1681 return current_destination;
1683 else if (successor->type == FINGER)
1686 struct GNUNET_PeerIdentity *next_hop;
1687 struct FingerInfo *finger;
1688 struct TrailPeerList *iterator;
1689 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
1690 finger = successor->data;
1691 iterator = finger->head->next;
1692 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1693 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
1694 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
1708 /* In this function, you should find 'r' (r = desired replication level) successors
1709 and send put message to all of these r successors. Now, I really don't know
1710 if in case of node failure it will be able to find data. Or if we start with
1711 a random peer id, do we even reach to correct successor ever in case of
1718 * @param source_peer
1720 * @param get_path_length
1724 GDS_NEIGHBOURS_handle_get (struct GNUNET_PeerIdentity *source_peer,
1725 struct GNUNET_PeerIdentity *get_path,
1726 unsigned int get_path_length,
1727 struct GNUNET_HashCode *key,
1728 struct GNUNET_PeerIdentity *target_peer,
1729 struct GNUNET_PeerIdentity *current_destination,
1730 enum current_destination_type *type)
1732 struct PeerGetMessage *get_msg;
1733 struct P2PPendingMessage *pending;
1734 struct GNUNET_PeerIdentity *gp;
1735 struct FriendInfo *target_friend;
1739 msize = sizeof (struct PeerGetMessage) +
1740 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
1742 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1748 memcpy (&key_value, key, sizeof (uint64_t));
1750 if (NULL == target_peer)
1752 /* This is the first call made from client file. */
1753 struct GNUNET_PeerIdentity *next_hop;
1754 next_hop = find_successor (key_value, current_destination, type);
1758 struct GNUNET_PeerIdentity *destination_peer;
1759 int current_path_index;
1761 /* FIXME: You enter in this part of code only if the call is made from the
1762 client file. And in client file you already have done the datacache_get.
1763 So, ideally you don't need it. Remove it after checking. */
1764 if (get_path_length != 1)
1765 current_path_index = get_path_length - 2;
1766 destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1767 memcpy (destination_peer, source_peer, sizeof (struct GNUNET_PeerIdentity));
1768 /* I am the final destination, then call GDS_NEIGHBOURS_send_get_result.*/
1769 GDS_NEIGHBOURS_send_get_result (&my_identity,get_path, get_path_length,
1770 destination_peer, current_path_index);
1775 /* Find the friend corresponding to next_hop */
1776 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1780 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer);
1782 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1783 pending->importance = 0; /* FIXME */
1784 /* FIXME: Do we have an expiration time for get request */
1785 get_msg = (struct PeerGetMessage *) &pending[1];
1786 pending->msg = &get_msg->header;
1787 get_msg->header.size = htons (msize);
1788 get_msg->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
1789 get_msg->get_path_length = htonl (get_path_length);
1790 get_msg->key = *key;
1791 memcpy (&(get_msg->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1792 memcpy (&(get_msg->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
1793 get_msg->dest_type = htonl (*type);
1795 gp = (struct GNUNET_PeerIdentity *) &get_msg[1];
1796 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
1797 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1798 target_friend->pending_count++;
1799 process_friend_queue (target_friend);
1805 * FIXME: In this function, you just find the target friend and send the message
1806 * to next peer. In handle_dht_p2p_put, you should check the options and type
1807 * and check if you are final destination or not. if not then find the next
1808 * destination and send the message forward.
1809 * @param type type of the block
1810 * @param options routing options
1811 * @param desired_replication_level desired replication count
1812 * @param expiration_time when does the content expire
1813 * @param hop_count how many hops has this message traversed so far
1814 * @param key key for the content
1815 * @param put_path_length number of entries in @a put_path
1816 * @param put_path peers this request has traversed so far (if tracked)
1817 * @param data payload to store
1818 * @param data_size number of bytes in @a data
1819 * @param current_destination
1821 * @param target_peer_id
1824 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
1825 enum GNUNET_DHT_RouteOption options,
1826 uint32_t desired_replication_level,
1827 struct GNUNET_TIME_Absolute expiration_time,
1829 struct GNUNET_HashCode *key,
1830 unsigned int put_path_length,
1831 struct GNUNET_PeerIdentity *put_path,
1832 const void *data, size_t data_size,
1833 struct GNUNET_PeerIdentity *current_destination,
1834 enum current_destination_type *dest_type,
1835 struct GNUNET_PeerIdentity *target_peer)
1837 struct PeerPutMessage *ppm;
1838 struct P2PPendingMessage *pending;
1839 struct FriendInfo *target_friend;
1840 struct GNUNET_PeerIdentity *pp;
1844 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
1845 sizeof (struct PeerPutMessage);
1847 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1849 put_path_length = 0;
1850 msize = data_size + sizeof (struct PeerPutMessage);
1853 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1859 memcpy (&key_value, key, sizeof (uint64_t));
1860 if (target_peer == NULL)
1862 /* This is the first time the call has been made from handle_dht_local_put.
1863 So, you need to search for the next peer to send this message to. */
1864 struct GNUNET_PeerIdentity *next_hop;
1865 next_hop = find_successor (key_value, current_destination, dest_type);
1867 if (*dest_type == MY_ID)
1869 /* FIXME: How do we handle different block types? */
1870 /* FIXME: Here depending on the replication level choose 'r' successors
1871 to this peer and send put to all of these peers. */
1873 GDS_DATACACHE_handle_put (expiration_time, key, put_path_length, put_path,
1874 type, data_size, data);
1879 /* Find the friend corresponding to next_hop */
1880 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1884 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer);
1886 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1887 pending->importance = 0; /* FIXME */
1888 pending->timeout = expiration_time;
1889 ppm = (struct PeerPutMessage *) &pending[1];
1890 pending->msg = &ppm->header;
1891 ppm->header.size = htons (msize);
1892 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
1893 ppm->options = htonl (options);
1894 ppm->type = htonl (type);
1895 ppm->hop_count = htonl (hop_count + 1);
1896 ppm->desired_replication_level = htonl (desired_replication_level);
1897 ppm->put_path_length = htonl (put_path_length);
1898 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1899 memcpy (&(ppm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
1900 ppm->current_destination_type = htonl (*dest_type);
1903 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
1904 memcpy (pp, put_path,
1905 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
1906 memcpy (&pp[put_path_length], data, data_size);
1907 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1908 target_friend->pending_count++;
1909 process_friend_queue (target_friend);
1915 * @param source_peer
1917 * @param get_path_length
1918 * @param destination_peer
1921 GDS_NEIGHBOURS_send_get_result (struct GNUNET_PeerIdentity *source_peer,
1922 struct GNUNET_PeerIdentity *get_path,
1923 unsigned int get_path_length,
1924 struct GNUNET_PeerIdentity *destination_peer,
1925 unsigned int current_path_index)
1927 /* Add get_result into pending message and send the data to target friend. */
1929 struct PeerGetResultMessage *get_result;
1930 struct P2PPendingMessage *pending;
1933 msize = (get_path_length * sizeof (struct GNUNET_PeerIdentity)) +
1934 sizeof (struct PeerGetResultMessage);
1936 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1951 handle_dht_p2p_get_result ()
1953 /* If you are the source, go back to the client file and there search for
1954 the requesting client and send back the result. */
1961 * Core handler for p2p put requests.
1963 * @param cls closure
1964 * @param peer sender of the request
1965 * @param message message
1966 * @param peer peer identity this notification is about
1967 * @return #GNUNET_OK to keep the connection open,
1968 * #GNUNET_SYSERR to close it (signal serious error)
1971 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
1972 const struct GNUNET_MessageHeader *message)
1974 struct PeerPutMessage *put;
1975 struct GNUNET_PeerIdentity *put_path;
1976 enum GNUNET_DHT_RouteOption options;
1977 enum current_destination_type current_dst_type;
1978 struct GNUNET_PeerIdentity *current_destination;
1979 struct GNUNET_PeerIdentity *source_peer;
1980 struct GNUNET_PeerIdentity *next_hop;
1981 struct GNUNET_HashCode test_key;
1984 size_t payload_size;
1988 msize = ntohs (message->size);
1989 if (msize < sizeof (struct PeerPutMessage))
1991 GNUNET_break_op (0);
1995 put = (struct PeerPutMessage *) message;
1996 putlen = ntohl (put->put_path_length);
1998 sizeof (struct PeerPutMessage) +
1999 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2001 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2003 GNUNET_break_op (0);
2007 put_path = (struct GNUNET_PeerIdentity *) &put[1];
2008 payload = &put_path[putlen];
2009 options = ntohl (put->options);
2010 payload_size = msize - (sizeof (struct PeerPutMessage) +
2011 putlen * sizeof (struct GNUNET_PeerIdentity));
2013 /* FIXME: I don't understand what exactly are we doing here. */
2014 switch (GNUNET_BLOCK_get_key
2015 (GDS_block_context, ntohl (put->type), payload, payload_size,
2019 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
2021 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
2022 GNUNET_break_op (0);
2023 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2024 "PUT with key `%s' for block with key %s\n",
2025 put_s, GNUNET_h2s_full (&test_key));
2026 GNUNET_free (put_s);
2031 GNUNET_break_op (0);
2034 /* cannot verify, good luck */
2038 /* FIXME: This part is also not clear to me.*/
2039 if (ntohl (put->type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
2041 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
2044 NULL, 0, /* bloom filer */
2045 NULL, 0, /* xquery */
2046 payload, payload_size))
2048 case GNUNET_BLOCK_EVALUATION_OK_MORE:
2049 case GNUNET_BLOCK_EVALUATION_OK_LAST:
2052 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
2053 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
2054 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
2055 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
2056 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
2057 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
2059 GNUNET_break_op (0);
2064 struct GNUNET_PeerIdentity pp[putlen + 1];
2066 /* extend 'put path' by sender */
2067 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
2069 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
2076 /* Copy the fields of message, call find successor or gds_routing_search,
2077 depending on the destination_type and if you are the final destination,
2078 do a datache put or if option is. else call gds_neighbours_handle_get with
2079 correct parameters. */
2080 current_destination = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2081 memcpy (current_destination, &(put->current_destination), sizeof (struct GNUNET_PeerIdentity));
2082 current_dst_type = ntohl (put->current_destination_type);
2083 memcpy (&key_value, &(put->key), sizeof (uint64_t));
2084 source_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2085 memcpy (source_peer, &(put->source_peer), sizeof (struct GNUNET_PeerIdentity));
2087 if (current_dst_type == FRIEND)
2089 next_hop = find_successor (key_value, current_destination, ¤t_dst_type);
2091 else if (current_dst_type == FINGER)
2093 next_hop = GDS_ROUTING_search (source_peer, current_destination);
2096 if (current_dst_type == MY_ID)
2098 /* Here datacache_put*/
2099 /* FIXME: Here depending on replication, call replicate_put() to do the
2100 put operation on 'r' successors. */
2101 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
2102 &(put->key),putlen, pp, ntohl (put->type), payload_size,
2108 /* here call gds_neighbours*/
2109 GDS_NEIGHBOURS_handle_put (ntohl (put->type),ntohl (put->options),
2110 ntohl (put->desired_replication_level),
2111 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2112 ntohl (put->hop_count),&put->key, putlen,
2113 pp, payload, payload_size,
2114 current_destination, ¤t_dst_type, next_hop);
2117 return GNUNET_SYSERR;
2122 * FIXME: Handle expiration, options, block type, replication
2123 * referring the old code.
2124 * Core handler for p2p get requests.
2126 * @param cls closure
2127 * @param peer sender of the request
2128 * @param message message
2129 * @return #GNUNET_OK to keep the connection open,
2130 * #GNUNET_SYSERR to close it (signal serious error)
2133 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
2134 const struct GNUNET_MessageHeader *message)
2136 struct PeerGetMessage *get;
2137 struct GNUNET_PeerIdentity *current_destination;
2139 enum current_destination_type dest_type;
2140 struct GNUNET_PeerIdentity *next_hop;
2141 struct GNUNET_PeerIdentity *get_path;
2143 unsigned int get_length;
2145 msize = ntohs (message->size);
2146 if (msize < sizeof (struct PeerGetMessage))
2148 GNUNET_break_op (0);
2152 get = (struct PeerGetMessage *)message;
2153 get_length = ntohl (get->get_path_length);
2154 get_path = (struct GNUNET_PeerIdentity *)&get[1];
2157 sizeof (struct PeerGetMessage) +
2158 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
2160 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2162 GNUNET_break_op (0);
2166 get = (struct PeerGetMessage *) message;
2167 current_destination = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2168 memcpy (current_destination, &(get->current_destination), sizeof (struct GNUNET_PeerIdentity));
2169 memcpy (&key_value, &(get->key), sizeof (uint64_t));
2170 dest_type = ntohl (get->dest_type);
2172 if (dest_type == FRIEND)
2174 next_hop = find_successor (key_value, current_destination, &dest_type);
2176 else if (dest_type == FINGER)
2178 next_hop = GDS_ROUTING_search (&(get->source_peer), current_destination);
2181 if (dest_type == MY_ID)
2183 struct GNUNET_PeerIdentity *destination_peer;
2184 int current_path_index;
2186 /* Add yourself to the get path, increment the get length. */
2187 destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2188 memcpy (destination_peer, &(get->source_peer), sizeof (struct GNUNET_PeerIdentity));
2189 current_path_index = get_length - 2;
2191 /* I am the final destination. Call GDS_NEIGHBOURS_send_get_result. */
2192 GDS_NEIGHBOURS_send_get_result (&my_identity, get_path, get_length,
2193 destination_peer, current_path_index);
2198 /* FIXME: Add your self to the get path and increment the get length. */
2200 /* FIXME: Does it matter if the dest_type is friend or finger. */
2201 GDS_NEIGHBOURS_handle_get (&(get->source_peer), get_path, get_length, &(get->key),
2202 next_hop, current_destination,&dest_type);
2206 return GNUNET_SYSERR;
2211 * Handle a PeerTrailSetupMessage.
2212 * @param cls closure
2213 * @param message message
2214 * @param peer peer identity this notification is about
2215 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2218 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
2219 const struct GNUNET_MessageHeader *message)
2221 struct PeerTrailSetupMessage *trail_setup;
2222 struct GNUNET_PeerIdentity *next_hop;
2223 struct FriendInfo *target_friend;
2224 struct GNUNET_PeerIdentity *current_destination;
2225 struct GNUNET_PeerIdentity *next_peer;
2226 struct GNUNET_PeerIdentity *trail_peer_list;
2227 enum current_destination_type peer_type;
2228 unsigned int trail_length;
2229 uint32_t current_trail_index;
2230 unsigned int finger_map_index;
2231 uint64_t finger_value;
2234 /* parse and validate message. */
2235 msize = ntohs (message->size);
2236 if (msize < sizeof (struct PeerTrailSetupMessage))
2238 GNUNET_break_op (0);
2242 trail_setup = (struct PeerTrailSetupMessage *) message;
2243 trail_length = ntohl (trail_setup->trail_length);
2246 sizeof (struct PeerTrailSetupMessage) +
2247 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2249 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2251 GNUNET_break_op (0);
2255 peer_type = ntohl (trail_setup->current_destination_type);
2256 finger_map_index = ntohl (trail_setup->finger_map_index);
2257 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_setup[1];
2258 finger_value = trail_setup->destination_finger;
2259 current_destination = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2260 memcpy (current_destination, &(trail_setup->current_destination), sizeof (struct GNUNET_PeerIdentity));
2262 if (peer_type == FRIEND)
2264 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
2267 next_hop = find_successor (finger_value, current_destination, &(peer_type));
2270 return GNUNET_SYSERR;
2272 else if (peer_type == FINGER)
2274 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
2277 next_hop = GDS_ROUTING_search (&(trail_setup->source_peer),
2278 &(trail_setup->current_destination));
2281 /* This is an optimization. Uncomment when basic code is running first. */
2282 /* I am part of trail.*/
2283 struct GNUNET_PeerIdentity *next_peer_routing_table;
2284 next_peer_routing_table = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2285 next_peer_routing_table = GDS_ROUTING_search (&(trail_setup->source_peer),
2286 &(trail_setup->current_destination));
2288 struct GNUNET_PeerIdentity *next_peer_find_successor;
2289 next_peer_find_successor = find_successor (&(trail_setup->destination_finger),
2290 &(trail_setup->current_destination),
2293 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2294 next_hop = find_closest_destination (next_peer_routing_table,
2295 next_peer_find_successor,
2296 &(trail_setup->destination_finger) );
2301 /* I am the current_destination finger */
2302 next_hop = find_successor (finger_value, current_destination, &(peer_type));
2306 /* If you are the next hop, then you are the final destination */
2307 if (peer_type == MY_ID)
2309 struct GNUNET_PeerIdentity *source;
2310 source = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2311 memcpy (source, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity));
2312 current_trail_index = trail_length - 2;
2313 next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2314 memcpy (next_peer, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2315 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
2316 GNUNET_free (next_peer);
2318 if(current_trail_index != 0)
2319 current_trail_index = current_trail_index - 1;
2321 if (0 == trail_setup->finger_map_index)
2323 struct GNUNET_PeerIdentity *new_trail;
2327 i = trail_length - 1;
2329 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
2333 memcpy( &new_trail[j], &trail_peer_list[i], sizeof (struct GNUNET_PeerIdentity));
2337 memcpy (&new_trail[j], &trail_peer_list[i], sizeof(struct GNUNET_PeerIdentity));
2338 finger_table_add (source, new_trail, trail_length, 1);
2341 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_setup->source_peer),
2343 target_friend, trail_length,
2344 trail_peer_list, current_trail_index,
2350 /* Add next hop to list of peers. */
2351 struct GNUNET_PeerIdentity *peer_list;
2352 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length + 1));
2353 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2354 memcpy (&peer_list[trail_length], next_hop, sizeof (struct GNUNET_PeerIdentity));
2357 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2359 if(peer_type == FINGER)
2361 GDS_ROUTING_add (&(trail_setup->source_peer),
2362 &(trail_setup->current_destination),
2366 GDS_NEIGHBOURS_send_trail_setup (&(trail_setup->source_peer),
2367 trail_setup->destination_finger,
2368 current_destination, target_friend, trail_length,
2369 peer_list, finger_map_index, peer_type);
2376 * Core handle for p2p trail construction result messages.
2377 * @param cls closure
2378 * @param message message
2379 * @param peer peer identity this notification is about
2380 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2383 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2384 const struct GNUNET_MessageHeader *message)
2386 struct PeerTrailSetupResultMessage *trail_result;
2387 struct GNUNET_PeerIdentity *trail_peer_list;
2388 struct GNUNET_PeerIdentity *next_peer;
2389 struct FriendInfo *target_friend;
2390 unsigned int current_trail_index;
2391 unsigned int finger_map_index;
2392 unsigned int trail_length;
2395 msize = ntohs (message->size);
2396 if (msize < sizeof (struct PeerTrailSetupResultMessage))
2398 GNUNET_break_op (0);
2402 trail_result = (struct PeerTrailSetupResultMessage *) message;
2403 trail_length = ntohl (trail_result->trail_length);
2406 sizeof (struct PeerTrailSetupResultMessage) +
2407 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2409 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2411 GNUNET_break_op (0);
2415 current_trail_index = ntohl (trail_result->current_index);
2416 finger_map_index = ntohl (trail_result->finger_map_index);
2418 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
2420 if ( 0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2424 /* SUPU: Here I have removed myself from the trail before storing it in
2425 th finger table - to save space, but in case of verify successor result
2426 the result trail does not contain me, and I will never get the message back.
2427 So, keeping myself in the trail list. Think of better solution.*/
2428 struct GNUNET_PeerIdentity *finger_trail;
2429 finger_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - 1));
2431 /* Copy the whole trail_peer_list except the first element into trail */
2433 i = trail_length - 1;
2436 memcpy (&finger_trail[i], &trail_peer_list[i], sizeof (struct GNUNET_PeerIdentity));
2439 trail_length = trail_length -1 ; SUPU: As you removed yourself from the trail.*/
2442 finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length,
2449 next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2450 memcpy (next_peer, &(trail_peer_list[current_trail_index]),
2451 sizeof (struct GNUNET_PeerIdentity));
2452 /* SUPU: here current trail index will always be greater than 0.
2453 so no need for this check here. trail index = 0, contains the final
2454 destination, and if we are in this loop we have not yet reached the
2455 final destination. */
2456 current_trail_index = current_trail_index - 1;
2458 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
2459 GNUNET_free (next_peer);
2461 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
2462 &(trail_result->finger_identity),
2463 target_friend, trail_length,
2464 trail_peer_list,current_trail_index,
2469 return GNUNET_SYSERR;
2474 * Core handle for p2p verify successor messages.
2475 * @param cls closure
2476 * @param message message
2477 * @param peer peer identity this notification is about
2478 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2481 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2482 const struct GNUNET_MessageHeader *message)
2484 struct PeerVerifySuccessorMessage *vsm;
2485 struct GNUNET_PeerIdentity *trail_peer_list;
2486 struct FriendInfo *target_friend;
2487 struct GNUNET_PeerIdentity *next_hop;
2488 struct GNUNET_PeerIdentity *source_peer;
2489 unsigned int trail_length;
2490 unsigned int current_trail_index;
2493 msize = ntohs (message->size);
2494 if (msize < sizeof (struct PeerVerifySuccessorMessage))
2496 GNUNET_break_op (0);
2500 vsm = (struct PeerVerifySuccessorMessage *) message;
2501 trail_length = ntohl (vsm->trail_length);
2504 sizeof (struct PeerVerifySuccessorMessage) +
2505 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2507 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2509 GNUNET_break_op (0);
2513 current_trail_index = ntohl (vsm->current_trail_index);
2514 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
2515 source_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2516 memcpy (source_peer, &(vsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
2518 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2520 /* SUPU: If I am the destination. */
2521 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),
2524 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2525 struct GNUNET_PeerIdentity key_ret;
2526 unsigned int finger_index;
2527 struct FingerInfo *my_predecessor;
2528 struct GNUNET_PeerIdentity *destination_peer;
2530 /* Iterate over finger peer map and extract your predecessor. */
2531 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2532 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2534 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
2535 (finger_iter,&key_ret,(const void **)&my_predecessor))
2537 if(1 == my_predecessor->finger_map_index)
2543 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2545 destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2546 memcpy (destination_peer, source_peer, sizeof (struct GNUNET_PeerIdentity));
2547 current_trail_index = trail_length - 2;
2548 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2549 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2550 GNUNET_free (next_hop);
2552 if (current_trail_index != 0)
2553 current_trail_index = current_trail_index - 1;
2555 /*SUPU: Remove this later*/
2556 struct GNUNET_PeerIdentity *predecessor;
2557 predecessor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2558 if (NULL == my_predecessor)
2560 /* FIXME: Ideally my_predecessor should not be NULL. If some one sent
2561 me a request to verify it I am the successor or not, then I would have
2562 added that peer to my_predecessor list. Check trail setup and see if
2563 you are adding predecessor when you get the request for successor. */
2565 update_predecessor (source_peer, trail_peer_list, trail_length);
2567 GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
2573 current_trail_index);
2578 /* FIXME: some times my_predecssor->finger_identity has no valid value.
2580 memcpy (predecessor, &(my_predecessor->finger_identity), sizeof (struct GNUNET_PeerIdentity));
2583 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (source_peer,
2584 &(my_predecessor->finger_identity))))
2586 /* SUPU: If source peer is my predecessor .*/
2587 GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
2589 &(my_predecessor->finger_identity),
2593 current_trail_index);
2597 struct GNUNET_PeerIdentity *new_successor_trail;
2598 int new_trail_length;
2601 new_trail_length = trail_length + my_predecessor->trail_length - 1;
2602 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
2603 * new_trail_length);
2605 /* Copy the trail from source peer to me. */
2606 memcpy (new_successor_trail, trail_peer_list,
2607 (trail_length) * sizeof (struct GNUNET_PeerIdentity));
2609 /* Copy the trail from me to my predecessor excluding me. */
2610 struct TrailPeerList *iterator;
2611 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
2612 iterator = my_predecessor->head->next;
2614 while (i < new_trail_length)
2616 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2617 iterator = iterator->next;
2621 GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
2623 &(my_predecessor->finger_identity),
2625 new_successor_trail,
2627 current_trail_index);
2633 /* If I am not the destination. */
2634 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2635 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2636 GNUNET_free (next_hop);
2638 current_trail_index = current_trail_index + 1;
2640 GDS_NEIGHBOURS_send_verify_successor(source_peer, &(vsm->successor),target_friend,
2641 trail_peer_list, trail_length, current_trail_index);
2648 * Core handle for p2p notify new successor messages.
2649 * @param cls closure
2650 * @param message message
2651 * @param peer peer identity this notification is about
2652 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2655 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2656 const struct GNUNET_MessageHeader *message)
2658 struct PeerNotifyNewSuccessorMessage *nsm;
2659 struct GNUNET_PeerIdentity *trail_peer_list;
2660 unsigned int current_trail_index;
2662 unsigned int trail_length;
2664 msize = ntohs (message->size);
2665 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
2667 GNUNET_break_op (0);
2671 nsm = (struct PeerNotifyNewSuccessorMessage *) message;
2672 trail_length = ntohl (nsm->trail_length);
2675 sizeof (struct PeerNotifyNewSuccessorMessage) +
2676 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2678 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2680 GNUNET_break_op (0);
2684 current_trail_index = ntohl (nsm->current_index);
2685 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
2687 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer),
2690 struct GNUNET_PeerIdentity *new_trail;
2694 i = trail_length - 1;
2696 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
2700 memcpy( &new_trail[j], &trail_peer_list[i], sizeof (struct GNUNET_PeerIdentity));
2704 memcpy (&new_trail[j], &trail_peer_list[i], sizeof(struct GNUNET_PeerIdentity));
2705 finger_table_add (&(nsm->source_peer), new_trail, trail_length, 1);
2711 struct FriendInfo *target_friend;
2712 target_friend = GNUNET_malloc (sizeof (struct FriendInfo));
2713 struct GNUNET_PeerIdentity *next_hop;
2714 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2715 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2716 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2717 GNUNET_free (next_hop);
2718 current_trail_index = current_trail_index + 1;
2720 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
2721 &(nsm->destination_peer),
2722 target_friend, trail_peer_list,
2723 trail_length, current_trail_index);
2730 * Core handle for p2p verify successor result messages.
2731 * @param cls closure
2732 * @param message message
2733 * @param peer peer identity this notification is about
2734 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2737 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2738 const struct GNUNET_MessageHeader *message)
2740 struct PeerVerifySuccessorResultMessage *vsrm;
2741 struct FriendInfo *target_friend;
2742 struct GNUNET_PeerIdentity *trail_peer_list;
2743 struct GNUNET_PeerIdentity *next_hop;
2744 unsigned int trail_length;
2745 unsigned int current_trail_index;
2748 msize = ntohs (message->size);
2749 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
2751 GNUNET_break_op (0);
2755 vsrm = (struct PeerVerifySuccessorResultMessage *) message;
2756 trail_length = ntohl (vsrm->trail_length);
2759 sizeof (struct PeerVerifySuccessorResultMessage) +
2760 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2762 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2764 GNUNET_break_op (0);
2768 current_trail_index = ntohl (vsrm->current_index);
2769 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
2771 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer),
2774 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor),
2777 finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0);
2778 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2779 memcpy (next_hop, &trail_peer_list[1], sizeof (struct GNUNET_PeerIdentity));
2780 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2781 current_trail_index = 2;
2782 GNUNET_free (next_hop);
2784 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
2785 target_friend, trail_peer_list,
2786 trail_length, current_trail_index);
2791 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2792 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2793 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2794 GNUNET_free (next_hop);
2795 current_trail_index = current_trail_index - 1;
2797 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
2798 &(vsrm->source_successor),
2799 &(vsrm->my_predecessor),
2803 current_trail_index);
2810 * Initialize neighbours subsystem.
2811 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2814 GDS_NEIGHBOURS_init()
2816 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
2817 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
2818 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
2819 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
2820 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
2821 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
2822 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
2823 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
2824 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
2829 /*TODO: What is ATS? Why do we need it? */
2830 atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
2832 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
2833 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
2834 GNUNET_NO, core_handlers);
2835 if (NULL == core_api)
2836 return GNUNET_SYSERR;
2838 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
2839 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS, GNUNET_NO);
2846 * Shutdown neighbours subsystem.
2849 GDS_NEIGHBOURS_done ()
2851 if (NULL == core_api)
2854 GNUNET_CORE_disconnect (core_api);
2856 GNUNET_ATS_performance_done (atsAPI);
2859 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
2860 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
2861 friend_peermap = NULL;
2864 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
2865 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
2866 finger_peermap = NULL;
2868 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
2870 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
2871 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
2875 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
2877 GNUNET_SCHEDULER_cancel (verify_successor);
2878 verify_successor = GNUNET_SCHEDULER_NO_TASK;
2885 * Get the ID of the local node.
2887 * @return identity of the local node
2889 struct GNUNET_PeerIdentity *
2890 GDS_NEIGHBOURS_get_id ()
2892 return &my_identity;
2896 /* end of gnunet-service-xdht_neighbours.c */