2 This file is part of GNUnet.
3 (C) 2009-2014 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_ats_service.h"
34 #include "gnunet_core_service.h"
35 #include "gnunet_datacache_lib.h"
36 #include "gnunet_transport_service.h"
37 #include "gnunet_dht_service.h"
38 #include "gnunet_statistics_service.h"
39 #include "gnunet-service-xdht.h"
40 #include "gnunet-service-xdht_clients.h"
41 #include "gnunet-service-xdht_datacache.h"
42 #include "gnunet-service-xdht_neighbours.h"
43 #include "gnunet-service-xdht_routing.h"
48 1. Use a global array of all known peers in find_successor, Only when
49 a new peer is added in finger or friend peer map, then re calculate
50 the array. Or else use the old one.*/
53 * Maximum possible fingers of a peer.
55 #define MAX_FINGERS 63
58 * Maximum allowed number of pending messages per friend peer.
60 #define MAXIMUM_PENDING_PER_FRIEND 64
63 * How long at least to wait before sending another find finger trail request,
64 * at most we wait twice this long.
66 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
69 * How long at most to wait for transmission of a GET request to another peer?
71 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
74 * Maximum number of trails allowed to go through a friend.
75 * FIXME: Random value at the moment, need to be adjusted to maintain a balance
76 * between performance and Sybil tolerance.
78 #define LINK_THRESHOLD 64
81 GNUNET_NETWORK_STRUCT_BEGIN
89 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
91 struct GNUNET_MessageHeader header;
96 uint32_t options GNUNET_PACKED;
101 uint32_t block_type GNUNET_PACKED;
106 uint32_t hop_count GNUNET_PACKED;
109 * Replication level for this message
111 uint32_t desired_replication_level GNUNET_PACKED;
114 * Length of the PUT path that follows (if tracked).
116 uint32_t put_path_length GNUNET_PACKED;
119 * Current destination to which this message is forwarded.
121 struct GNUNET_PeerIdentity current_destination;
124 * Peer whose finger is current_destination.
126 struct GNUNET_PeerIdentity current_source;
129 * When does the content expire?
131 struct GNUNET_TIME_AbsoluteNBO expiration_time;
134 * The key to store the value under.
136 struct GNUNET_HashCode key GNUNET_PACKED;
138 /* put path (if tracked) */
148 struct PeerGetResultMessage
151 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT
153 struct GNUNET_MessageHeader header;
156 * The type for the data.
158 uint32_t type GNUNET_PACKED;
161 * Peer which will receive the get result message.
163 struct GNUNET_PeerIdentity source_peer;
166 * Number of peers recorded in the outgoing path from source to the
167 * stored location of this message.
169 uint32_t put_path_length GNUNET_PACKED;
172 * Length of the GET path that follows (if tracked).
174 uint32_t get_path_length GNUNET_PACKED;
177 * When does the content expire?
179 struct GNUNET_TIME_Absolute expiration_time;
182 * The key of the corresponding GET request.
184 struct GNUNET_HashCode key;
186 /* put path (if tracked) */
188 /* get path (if tracked) */
198 struct PeerGetMessage
201 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
203 struct GNUNET_MessageHeader header;
208 uint32_t options GNUNET_PACKED;
211 * Desired content type.
213 uint32_t block_type GNUNET_PACKED;
218 uint32_t hop_count GNUNET_PACKED;
221 * Desired replication level for this request.
223 uint32_t desired_replication_level GNUNET_PACKED;
226 * Total number of peers in get path.
228 unsigned int get_path_length;
231 * Peer which is an intermediate destination.
233 struct GNUNET_PeerIdentity current_destination;
236 * Source for which current_destination is the finger.
238 struct GNUNET_PeerIdentity current_source;
241 * The key we are looking for.
243 struct GNUNET_HashCode key;
251 * FIXME: Check the alignment in all the struct
252 * P2P Trail setup message
254 struct PeerTrailSetupMessage
258 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
260 struct GNUNET_MessageHeader header;
263 * Successor of this finger value will be our finger peer.
265 uint64_t destination_finger;
268 * Source peer which wants to setup the trail to one of its finger.
270 struct GNUNET_PeerIdentity source_peer;
273 * Peer to which this packet is forwarded.
275 struct GNUNET_PeerIdentity current_destination;
278 * In case the packet is forwarded to an intermediate finger, then
279 * current_source contains the peer id whose finger is the intermediate
280 * finger. In case the packet is forwarded to a friend, then it is NULL.
282 struct GNUNET_PeerIdentity current_source;
285 * Index into finger peer map, in NBO.
287 uint32_t finger_map_index;
290 * Number of entries in trail list, in NBO.
292 uint32_t trail_length GNUNET_PACKED;
298 * P2P Trail Setup Result message
300 struct PeerTrailSetupResultMessage
304 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
306 struct GNUNET_MessageHeader header;
309 * Finger to which we have found the path.
311 struct GNUNET_PeerIdentity finger_identity;
314 * Peer which was looking for the trail to finger.
316 struct GNUNET_PeerIdentity destination_peer;
319 * Index into finger peer map
321 uint32_t finger_map_index;
324 * Number of entries in trail list.
326 uint32_t trail_length GNUNET_PACKED;
333 struct PeerTrailRejectionMessage
336 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
338 struct GNUNET_MessageHeader header;
341 * Source peer which wants to set up the trail.
343 struct GNUNET_PeerIdentity source_peer;
346 * Peer which sent trail rejection message.
348 struct GNUNET_PeerIdentity congested_peer;
351 * Finger identity value.
353 uint64_t finger_identity;
356 * Index in finger peer map of source peer.
358 uint32_t finger_map_index;
361 * Total number of peers in the trail.
363 uint32_t trail_length;
370 * P2P Verify Successor message.
372 struct PeerVerifySuccessorMessage
376 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
378 struct GNUNET_MessageHeader header;
381 * Source peer which wants to verify its successor.
383 struct GNUNET_PeerIdentity source_peer;
386 * My current successor.
388 struct GNUNET_PeerIdentity successor;
391 * Total number of peers in trail to current successor.
393 uint32_t trail_length;
398 * P2P Verify Successor Result message.
400 struct PeerVerifySuccessorResultMessage
404 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
406 struct GNUNET_MessageHeader header;
409 * Destination peer which sent the request to verify its successor.
411 struct GNUNET_PeerIdentity destination_peer;
414 * Successor to which PeerVerifySuccessorMessage was sent.
416 struct GNUNET_PeerIdentity source_successor;
419 * source_successor's predecessor
421 struct GNUNET_PeerIdentity my_predecessor;
424 * Total number of peers in trail.
425 * If source_successor is not destination peer, then trail is from destination_peer
427 * If source_successor is destination peer, then trail is from destination_peer
428 * to source_successor.
430 uint32_t trail_length;
434 * P2P Notify New Successor message.
436 struct PeerNotifyNewSuccessorMessage
439 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
441 struct GNUNET_MessageHeader header;
444 * Source peer which wants to notify its new successor.
446 struct GNUNET_PeerIdentity source_peer;
449 * New successor identity.
451 struct GNUNET_PeerIdentity destination_peer;
454 * Number of peers in trail from source_peer to new successor.
456 uint32_t trail_length;
460 GNUNET_NETWORK_STRUCT_END
464 * Linked list of messages to send to a particular other peer.
466 struct P2PPendingMessage
469 * Pointer to next item in the list
471 struct P2PPendingMessage *next;
474 * Pointer to previous item in the list
476 struct P2PPendingMessage *prev;
479 * Message importance level. FIXME: used? useful?
481 unsigned int importance;
484 * When does this message time out?
486 struct GNUNET_TIME_Absolute timeout;
489 * Actual message to be sent, allocated at the end of the struct:
490 * // msg = (cast) &pm[1];
491 * // memcpy (&pm[1], data, len);
493 const struct GNUNET_MessageHeader *msg;
499 * Linked List of peers which are part of trail to reach a particular Finger.
504 * Pointer to next item in the list
506 struct TrailPeerList *next;
509 * Pointer to previous item in the list
511 struct TrailPeerList *prev;
514 * An element in this trail list
516 struct GNUNET_PeerIdentity peer;
522 * Entry in friend_peermap.
529 struct GNUNET_PeerIdentity id;
532 * Number of trail of which this friend is the first hop.
534 unsigned int trail_links;
537 * Count of outstanding messages for this friend.
539 unsigned int pending_count;
542 * Head of pending messages to be sent to this friend.
544 struct P2PPendingMessage *head;
547 * Tail of pending messages to be sent to this friend.
549 struct P2PPendingMessage *tail;
552 * Core handle for sending messages to this friend.
554 struct GNUNET_CORE_TransmitHandle *th;
560 * Entry in finger_peermap.
567 struct GNUNET_PeerIdentity finger_identity;
570 * Index in finger peer map
572 unsigned int finger_map_index;
575 * Total number of entries in trail from (me,finger]
577 unsigned int trail_length;
580 * Head of trail to reach this finger.
582 struct TrailPeerList *head;
585 * Tail of trail to reach this finger.
587 struct TrailPeerList *tail;
591 enum current_destination_type
600 * FIXME: Think of a better name.
601 * Data structure passed to sorting algorithm in find_successor.
606 * 64 bit value of peer identity
611 * Type : MY_ID, FINGER, FINGER, Value
613 enum current_destination_type type;
616 * Pointer to original data structure linked to peer id.
623 * FIXME: Think of better comments.
624 * An entry in Failed_Trail_List
629 * Source peer which was trying to setup up the trail to @a destination_finger_value
631 struct GNUNET_PeerIdentity source_peer;
634 * Value to which we were trying to find the closest successor.
636 uint64_t destination_finger_value;
639 * Peer which has crossed the threshold limit on its routing table size.
641 struct GNUNET_PeerIdentity congested_peer;
647 * Task that sends FIND FINGER TRAIL requests.
649 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
653 * Task that periodically verifies my successor.
655 static GNUNET_SCHEDULER_TaskIdentifier verify_successor;
658 * Identity of this peer.
660 static struct GNUNET_PeerIdentity my_identity;
663 * Hash map of all the friends of a peer
665 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
668 * Hash map of all the fingers of a peer
670 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
673 * Hash maps of all the trail which failed due to a congested peer.
675 static struct GNUNET_CONTAINER_MultiPeerMap *failed_trail_list;
680 static struct GNUNET_CORE_Handle *core_api;
683 * Finger map index for predecessor entry in finger peermap.
685 #define PREDECESSOR_FINGER_ID 64
688 * The current finger index that we have found trail to.
690 static unsigned int current_finger_index;
693 * Iterate over trail and search your index location in the array.
694 * @param trail Trail which contains list of peers.
695 * @return Index in the array.
698 search_my_index (const struct GNUNET_PeerIdentity *trail)
704 * Called when core is ready to send a message we asked for
705 * out to the destination.
707 * @param cls the 'struct FriendInfo' of the target friend
708 * @param size number of bytes available in buf
709 * @param buf where the callee should write the message
710 * @return number of bytes written to buf
713 core_transmit_notify (void *cls, size_t size, void *buf)
715 struct FriendInfo *peer = cls;
717 struct P2PPendingMessage *pending;
722 while ((NULL != (pending = peer->head)) &&
723 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
725 peer->pending_count--;
726 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
727 GNUNET_free (pending);
731 /* no messages pending */
737 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
738 GNUNET_CORE_PRIO_BEST_EFFORT,
739 GNUNET_TIME_absolute_get_remaining
740 (pending->timeout), &peer->id,
741 ntohs (pending->msg->size),
742 &core_transmit_notify, peer);
743 GNUNET_break (NULL != peer->th);
747 while ((NULL != (pending = peer->head)) &&
748 (size - off >= (msize = ntohs (pending->msg->size))))
750 GNUNET_STATISTICS_update (GDS_stats,
752 ("# Bytes transmitted to other peers"), msize,
754 memcpy (&cbuf[off], pending->msg, msize);
756 peer->pending_count--;
757 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
758 GNUNET_free (pending);
760 if (peer->head != NULL)
763 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
764 GNUNET_CORE_PRIO_BEST_EFFORT,
765 GNUNET_TIME_absolute_get_remaining
766 (pending->timeout), &peer->id, msize,
767 &core_transmit_notify, peer);
768 GNUNET_break (NULL != peer->th);
775 * Transmit all messages in the friend's message queue.
777 * @param peer message queue to process
780 process_friend_queue (struct FriendInfo *peer)
782 struct P2PPendingMessage *pending;
784 if (NULL == (pending = peer->head))
786 if (NULL != peer->th)
789 GNUNET_STATISTICS_update (GDS_stats,
791 ("# Bytes of bandwidth requested from core"),
792 ntohs (pending->msg->size), GNUNET_NO);
794 /* FIXME: Are we correctly initializing importance and pending. */
796 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
798 GNUNET_TIME_absolute_get_remaining
799 (pending->timeout), &peer->id,
800 ntohs (pending->msg->size),
801 &core_transmit_notify, peer);
802 GNUNET_break (NULL != peer->th);
807 * FIXME: In this function using const, does it affect only here right? not in
808 * the struct P2PTrailSetupMessage as their fields are not defined as const.
809 * Also, I changed current_destination and current_source from const to not,
810 * because when we make a call from handle_dht_p2p_trail_setup, then we are
811 * passing struct for current_destination and not current_source, as we are writing
812 * to these variables and we can not decalre them as const.
813 * Construct a trail message and forward it to a friend.
814 * @param source_peer Peer which wants to set up the trail to one of its finger.
815 * @param destination_finger Peer identity closest to this value will be
816 * @a source_peer's finger.
817 * @param current_destination Finger of the @a current_source, for which among
818 * its friends, its own identity and all fingers, this
819 * finger is the closest to the @a destination_finger
820 * @param current_source Peer for which @a current_destination is its finger.
821 * @param target_friend Friend to which this message should be forwarded.
822 * @param trail_length Numbers of peers in the trail found so far.
823 * @param trail_peer_list Peers this request has traversed so far
824 * @param finger_map_index Index in finger peer map
827 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
828 uint64_t destination_finger,
829 struct GNUNET_PeerIdentity *current_destination,
830 struct GNUNET_PeerIdentity *current_source,
831 struct FriendInfo *target_friend,
832 unsigned int trail_length,
833 const struct GNUNET_PeerIdentity *trail_peer_list,
834 unsigned int finger_map_index)
836 struct P2PPendingMessage *pending;
837 struct PeerTrailSetupMessage *tsm;
838 struct GNUNET_PeerIdentity *peer_list;
841 msize = sizeof (struct PeerTrailSetupMessage) +
842 (trail_length * sizeof (struct GNUNET_PeerIdentity));
844 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
850 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
852 /* SUPU: Its important to have such statistics as you need to keep track of
853 the packets lost due to full queue. */
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->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
860 tsm = (struct PeerTrailSetupMessage *) &pending[1];
861 pending->msg = &tsm->header;
862 tsm->header.size = htons (msize);
863 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
864 /* FIXME: understand where you need to use memcpy or direct assignment. */
865 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
866 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
867 memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
868 memcpy (&(tsm->current_source), current_source, sizeof (struct GNUNET_PeerIdentity));
869 tsm->trail_length = htonl (trail_length);
870 tsm->finger_map_index = htonl (finger_map_index);
872 /* SUPU: here i guess its okay to have it as NULL as it is added at the end of
873 the struct but in case of current_destination and current_source, it is part
874 of the struct. thats why the confusion. */
875 if (trail_peer_list != NULL)
877 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
878 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
881 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
882 target_friend->pending_count++;
883 process_friend_queue (target_friend);
889 * Construct a trail setup result message and forward it to a friend.
890 * @param destination_peer Peer which will get the trail to one of its finger.
891 * @param source_finger Peer to which the trail has been setup to.
892 * @param target_friend Friend to which this message should be forwarded.
893 * @param trail_length Numbers of peers in the trail.
894 * @param trail_peer_list Peers which are part of the trail from source to destination.
895 * @param finger_map_index Index in finger peer map
898 GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *destination_peer,
899 const struct GNUNET_PeerIdentity *source_finger,
900 struct FriendInfo *target_friend,
901 unsigned int trail_length,
902 const struct GNUNET_PeerIdentity *trail_peer_list,
903 unsigned int finger_map_index)
905 struct P2PPendingMessage *pending;
906 struct PeerTrailSetupResultMessage *tsrm;
907 struct GNUNET_PeerIdentity *peer_list;
910 msize = sizeof (struct PeerTrailSetupResultMessage) +
911 (trail_length * sizeof (struct GNUNET_PeerIdentity));
913 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
919 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
921 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
925 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
926 pending->importance = 0;
927 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
928 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
929 pending->msg = &tsrm->header;
930 tsrm->header.size = htons (msize);
931 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
932 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
933 memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity));
934 tsrm->trail_length = htonl (trail_length);
935 tsrm->finger_map_index = htonl (finger_map_index);
936 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
937 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
939 /* Send the message to chosen friend. */
940 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
941 target_friend->pending_count++;
942 process_friend_queue (target_friend);
947 * Construct a PeerVerifySuccessor message and send it to friend.
948 * @param source_peer Peer which wants to verify its successor
949 * @param successor Peer which is our current successor
950 * @param target_friend Friend to which this message should be forwarded.
951 * @param trail_peer_list Peer which are part of trail from source to destination
952 * @param trail_length Number of peers in the trail list.
954 void GDS_NEIGHBOURS_send_verify_successor(const struct GNUNET_PeerIdentity *source_peer,
955 const struct GNUNET_PeerIdentity *successor,
956 struct FriendInfo *target_friend,
957 const struct GNUNET_PeerIdentity *trail_peer_list,
958 unsigned int trail_length)
960 struct PeerVerifySuccessorMessage *vsm;
961 struct P2PPendingMessage *pending;
962 struct GNUNET_PeerIdentity *peer_list;
965 msize = sizeof (struct PeerVerifySuccessorMessage) +
966 (trail_length * sizeof (struct GNUNET_PeerIdentity));
968 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
974 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
976 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
980 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
981 pending->importance = 0; /* FIXME */
982 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
983 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
984 pending->msg = &vsm->header;
985 vsm->header.size = htons (msize);
986 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
987 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
988 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
989 vsm->trail_length = htonl (trail_length);
990 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
991 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
993 /* Send the message to chosen friend. */
994 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
995 target_friend->pending_count++;
996 process_friend_queue (target_friend);
1002 * Construct a PeerVerifySuccessorResult message and send it to friend.
1003 * @param destination_peer Peer which sent verify successor message
1004 * @param source_successor Peer to which verify successor message was sent.
1005 * @param my_predecessor source_successor's predecessor.
1006 * @param target_friend Friend to which this message should be forwarded.
1007 * @param trail_peer_list Peers which are part of trail from source to destination
1008 * @param trail_length Number of peers in the trail list.
1010 void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdentity *destination_peer,
1011 const struct GNUNET_PeerIdentity *source_successor,
1012 const struct GNUNET_PeerIdentity *my_predecessor,
1013 struct FriendInfo *target_friend,
1014 const struct GNUNET_PeerIdentity *trail_peer_list,
1015 unsigned int trail_length)
1017 struct PeerVerifySuccessorResultMessage *vsmr;
1018 struct P2PPendingMessage *pending;
1019 struct GNUNET_PeerIdentity *peer_list;
1022 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1023 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1025 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1032 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1034 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1038 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1039 pending->importance = 0; /* FIXME */
1040 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1041 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1042 pending->msg = &vsmr->header;
1043 vsmr->header.size = htons (msize);
1044 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1045 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1046 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
1047 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
1048 vsmr->trail_length = htonl (trail_length);
1049 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1050 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1052 /* Send the message to chosen friend. */
1053 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1054 target_friend->pending_count++;
1055 process_friend_queue (target_friend);
1060 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1061 * @param source_peer Peer which is sending notify message to its new successor.
1062 * @param destination_peer Peer which is the new destination.
1063 * @param target_friend Next friend to pass this message to.
1064 * @param peer_list List of peers in the trail to reach to destination_peer.
1065 * @param trail_length Total number of peers in peer list
1068 GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *source_peer,
1069 const struct GNUNET_PeerIdentity *destination_peer,
1070 struct FriendInfo *target_friend,
1071 const struct GNUNET_PeerIdentity *trail_peer_list,
1072 unsigned int trail_length)
1074 struct PeerNotifyNewSuccessorMessage *nsm;
1075 struct P2PPendingMessage *pending;
1076 struct GNUNET_PeerIdentity *peer_list;
1079 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1080 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1082 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1088 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1090 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1094 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1095 pending->importance = 0; /* FIXME */
1096 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1097 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1098 pending->msg = &nsm->header;
1099 nsm->header.size = htons (msize);
1100 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1101 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1102 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1103 nsm->trail_length = htonl (trail_length);
1105 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1106 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1108 /* Send the message to chosen friend. */
1109 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1110 target_friend->pending_count++;
1111 process_friend_queue (target_friend);
1116 * FIXME: Optimizaiton Once the basic code is running. Add the optimization
1117 * where you check if the threshold on number of links that should go through
1118 * a particular friend has crossed. If yes then again choose a different
1119 * friend. Important that the new friend chosen should be different. How to
1120 * ensure this? This is an important optimization as without this one x-vine
1121 * is actually not a sybil tolerant DHT.
1122 * Randomly choose one of your friends from the friends_peer map
1125 static struct FriendInfo *
1126 select_random_friend (struct GNUNET_PeerIdentity *congested_peer)
1128 unsigned int current_size;
1129 unsigned int *index;
1131 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1132 struct GNUNET_PeerIdentity key_ret;
1133 struct FriendInfo *friend;
1135 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1136 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1137 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1139 if (GNUNET_CONTAINER_multipeermap_size (friend_peermap) == 0)
1141 /* FIXME: It may happen that there is not friend in friend peermap but
1142 as this task has already been started it failed.*/
1148 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1156 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1158 /* TODO: Here you have chosen a random friend. Now you should check the size
1159 of its routing table size, and if its more than threshold, then check which
1160 of the entries has trail length greater than trail length threshold. we
1161 should without checking the routing table size also we should check the
1162 trail with trail length greater than threshold. then
1163 you should try to find a new route through this new node that has joined in
1164 only for those finger entries whose trail length is greater than threshold.
1165 But I don't want the new node to wait for this process to get over. so
1166 should i declare a function which will be called after some interval.*/
1175 * FIMXE: pass current_finger_index as argument.
1176 * Compute finger_identity to which we want to setup the trail
1177 * @return finger_identity
1180 compute_finger_identity()
1184 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1185 my_id64 = GNUNET_ntohll (my_id64);
1186 /*FIXME: Do we need a mod finger = ((my_id + pow(2, finger_index)) mod (pow (2, MAX_FINGERS))*/
1187 return (my_id64 + (unsigned long) pow (2, current_finger_index));
1192 * Compute immediate predecessor identity in the network.
1193 * @return peer identity of immediate predecessor.
1196 compute_predecessor_identity()
1200 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1201 my_id64 = GNUNET_ntohll (my_id64);
1202 return (my_id64 -1);
1207 * Periodically ping your successor to ask its current predecessor
1209 * @param cls closure for this task
1210 * @param tc the context under which the task is running
1213 send_verify_successor_message (void *cls,
1214 const struct GNUNET_SCHEDULER_TaskContext *tc )
1216 struct GNUNET_TIME_Relative next_send_time;
1217 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1218 struct GNUNET_PeerIdentity key_ret;
1219 struct FriendInfo *target_friend;
1220 struct GNUNET_PeerIdentity *next_hop;
1221 struct GNUNET_PeerIdentity *peer_list;
1222 struct FingerInfo *finger;
1223 unsigned int finger_index;
1227 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1228 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1230 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1231 (const void **)&finger))
1233 if (0 == finger->finger_map_index)
1240 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1243 goto send_new_request;
1245 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->trail_length);
1247 struct TrailPeerList *iterate;
1248 iterate = finger->head;
1250 while ( i < (finger->trail_length))
1252 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1253 iterate = iterate->next;
1257 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1258 memcpy (next_hop, &peer_list[0], sizeof (struct GNUNET_PeerIdentity));
1259 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1261 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1262 &(finger->finger_identity),
1265 finger->trail_length);
1268 /* FIXME: Understand what this function is actually doing here. */
1270 next_send_time.rel_value_us =
1271 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1272 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1273 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1276 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
1282 * FIXME - the main logic of handling the finger map index has changed.
1283 * first we start with finger index = 64, that index is reserved for the
1284 * predecessor always. Then we start going backwards, finger_index = 63 to 0
1285 * and once its 0 we again go back to 64. now, when you start looking for the finger
1286 * then your successor is always the finger with lowest finger index. in finger_table_add
1287 * whenever you do an entry you check for predecessor , if the new finger identity
1288 * is greater than existing one, then that should be your predecessor. In case of
1289 * other fingers also, if the new entry is smaller than existing one. If yes
1290 * then that is correct finger for that finger index. Also, the lowest finger index and
1291 * its corresponding finger identity is your successor.
1293 * Choose a random friend and start looking for the trail to reach to
1294 * finger identity through this random friend.
1296 * @param cls closure for this task
1297 * @param tc the context under which the task is running
1300 send_find_finger_trail_message (void *cls,
1301 const struct GNUNET_SCHEDULER_TaskContext *tc)
1303 struct FriendInfo *target_friend;
1304 struct GNUNET_TIME_Relative next_send_time;
1305 uint64_t finger_identity;
1306 unsigned int finger_map_index;
1308 /* FIXME: understand how does this scheduling of processes take place? */
1309 next_send_time.rel_value_us =
1310 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1311 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1312 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1313 /* FIXME: here we are just adding the process to the scheduling list. only
1314 when this function is executed, it may get scheduled. */
1315 find_finger_trail_task =
1316 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1318 target_friend = select_random_friend (NULL);
1320 if (NULL == target_friend)
1322 /* SUPU: Here we can get NULL in the case there is no friend in the peer map
1323 or all of the friends have reached their threshold. The first case should ideally
1324 never happen because in handle_core_disconnect we have already canceled the task
1325 but it may happen if we already started the process and we reached here and
1326 we cancelled the next task. So, it can return NULL in that case also. Should
1327 we handle both cases in same way or not? */
1331 /* FIXME: start with current_finger_index = 64, */
1332 if (PREDECESSOR_FINGER_ID == current_finger_index)
1334 /* FIXME: Where do we set the value back to PREDECESSR_FINGER_ID? Only
1335 when current_finger_index = 0, do we set it back to PREDECESSOR_FINGER_ID,
1336 in finger_table_add? Or is there any other possible condition, where we
1337 may need to set it to PREDECESSOR_FINGER_ID*/
1338 finger_identity = compute_predecessor_identity();
1342 finger_identity = compute_finger_identity();
1345 finger_map_index = current_finger_index;
1347 /* FIXME: verify if its correct to set current_destination and current_source
1348 as my identity. Check what should be the best value to set for current_dest
1349 * and current_source. */
1350 GDS_NEIGHBOURS_send_trail_setup (&my_identity, finger_identity, &(target_friend->id),
1351 &(target_friend->id), target_friend, 0, NULL, finger_map_index);
1356 * Invert the trail list.
1357 * @param destination_peer
1358 * @param existing_trail
1359 * @param trail_length
1362 static struct GNUNET_PeerIdentity *
1363 invert_trail_list (struct GNUNET_PeerIdentity *destination_peer,
1364 struct GNUNET_PeerIdentity *existing_trail,
1365 unsigned int trail_length)
1369 struct GNUNET_PeerIdentity *new_trail;
1372 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
1374 if (trail_length > 1)
1376 i = trail_length - 2;
1379 memcpy( &new_trail[j], &existing_trail[i], sizeof (struct GNUNET_PeerIdentity));
1384 memcpy (&new_trail[j], destination_peer, sizeof(struct GNUNET_PeerIdentity));
1393 * @param existing_finger
1398 compare_finger_identity (struct GNUNET_PeerIdentity *existing_finger,
1399 struct GNUNET_PeerIdentity *new_finger)
1402 ret = (existing_finger > new_finger) ? 1 :
1403 (existing_finger == new_finger) ? 0 : -1;
1410 * Check if there is a predecessor in our finger peer map or not.
1411 * If no, then return GNUNET_YES
1412 * else compare existing predecessor and peer, and find the correct
1414 * @param existing_predecessor
1415 * @param new_predecessor
1416 * @return #GNUNET_YES if new peer is predecessor
1417 * #GNUNET_NO if new peer is not the predecessor.
1420 compare_predecessor(struct GNUNET_PeerIdentity *peer)
1422 /* FIXME: here you should first check if you already have an entry in the
1423 finger peer map for finger index = 64, if yes then compare it with peer
1424 if not then just add the peer. */
1432 static struct GNUNET_PeerIdentity *
1433 check_for_successor ()
1438 * Scan the trail, check if there is a friend in the trail, then shortcut
1439 * the trail and return the new trail and trail length.
1440 * FIXME: How to send the trail length? Should I create a new array and copy into
1441 * it or modify the existing trail. also, how can it be done optimally?
1442 * @param finger_trail
1446 static struct GNUNET_PeerIdentity *
1447 scan_trail (struct GNUNET_PeerIdentity *finger_trail)
1453 /* @param cls closure
1454 * @param key current public key
1455 * @param value value in the hash map
1456 * @return #GNUNET_YES if we should continue to
1458 * #GNUNET_NO if not.
1461 get_existing_finger (void *cls,
1462 const struct GNUNET_PeerIdentity *key,
1465 struct FingerInfo *existing_finger = value;
1466 uint32_t finger_map_index = (uint32_t) cls;
1468 if (existing_finger->finger_map_index == finger_map_index)
1470 /* SUPU: How do I communicate this finger to the calling function. */
1477 * If you remove an entry from finger table, and if the finger is not your friend
1478 * and the trail length > 1 for the finger that you removed, then you should send
1479 * a trail_teardown message along the trail. so that the peers which have an
1480 * entry in their routing table for this trail can remove it from their routing
1482 * 2. how to handle the case in which same finger identity is stored for different
1483 * finger map index. because this will just increase the size of finger map and
1484 * also size of the array we use in find_successor.
1485 * Add an entry in finger table. Before adding, check if there is already an
1486 * entry in finger peermap for the same index, if yes then choose the closest one.
1487 * In case both the existing identity and new identity are same, keep both the trail
1488 * only if the trails are different (Redundant routing). Also, a peer stored at index,i
1489 * if its same as peer stored index, i+1, and 'i' is the lowest finger map index
1490 * seen so far, then that peer is the successor. In case finger_map_index is PREDECESSOR_INDEX,
1491 * then simply add it as handle rest of the cases for it in a different function.
1492 * Also while adding an entry check the trail, scan the trail and check if there
1493 * is a friend in between, then shortcut the path.
1494 * @param finger_identity
1495 * @param finger_trail
1496 * @param finger_trail_length
1497 * @param finger_map_index
1500 void finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
1501 const struct GNUNET_PeerIdentity *finger_trail,
1502 uint32_t finger_trail_length,
1503 uint32_t finger_map_index)
1505 struct FingerInfo new_finger_entry;
1508 /* If I am my own finger, then return. */
1509 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, finger_identity))
1511 GNUNET_break (0); /* SUPU: Its here because I need to see when it happens. */
1515 if (finger_map_index == PREDECESSOR_FINGER_ID)
1518 /* For rest of current_finger_index, choose the correct finger and correct trail. */
1519 /* SUPU: Here I want to iterate over all the entries and see if there is already
1520 an entry for the finger map index. if yes then check if finger identity are same
1521 if yes then check the trail. if I use gnuent_container_multipeermap_iterate,
1522 i should stop after I found the finger map index, and just return the
1523 struct finger info. then I should call another function which takes care of
1524 finding the closest peer */
1525 GNUNET_CONTAINER_multipeermap_iterate (finger_peermap, &get_existing_finger,
1526 (void *)finger_map_index);
1529 memcpy (&(new_finger_entry.finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
1530 new_finger_entry.finger_map_index = finger_map_index;
1531 /* FIXME: How do I get the length as well as the trail.
1532 * scan_trail (finger_trail);
1534 new_finger_entry.trail_length = finger_trail_length;
1537 while (i < finger_trail_length)
1539 struct TrailPeerList *element;
1540 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1541 element->next = NULL;
1542 element->prev = NULL;
1544 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
1545 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry.head, new_finger_entry.tail, element);
1549 GNUNET_assert (GNUNET_OK ==
1550 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
1551 &(new_finger_entry.finger_identity),
1553 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
1555 /* FIXME: after adding an entry, I want to check if there is a successor, if yes
1556 then this function will return it and then we should schedule a verify successor
1558 if (NULL != check_for_successor())
1560 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1561 /* FIXME: Is it safe to set the finger index to predecessor_finger_id here? */
1562 current_finger_index = PREDECESSOR_FINGER_ID;
1566 /* FIXME: Not sure if this is the correct place to set the values. Look into
1567 send_find_finger_trail_message and check. */
1568 if(current_finger_index == 0)
1569 current_finger_index = PREDECESSOR_FINGER_ID;
1571 current_finger_index = current_finger_index - 1;
1576 /*FIXME: Here you need to set the correct value of finger_map_index,
1577 * in case it is 0, then you set it back to 64, and in case it is x,
1578 * then you set it back to x-1. current_finger_index = ( current_finger_index - 1) % MAX_FINGERS
1579 * we also need to change the logic of starting the process to look for a successor.
1580 * when you add an entry then go through whole trail and check if there is an entry
1581 * which is your friend, if yes then just collapse the trail. if you are not doing it
1582 * here then you need to do it in handle_core_disconnect where you will have to search
1583 * through whole trail find peer and then delete the finger.
1584 * Add an entry in finger table.
1585 * @param finger_identity Peer identity of finger
1586 * @param finger_trail Trail to reach the finger
1587 * @param trail_length Number of peers in the trail.
1588 * @param finger_map_index Index in finger peer map.
1591 void finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
1592 const struct GNUNET_PeerIdentity *finger_trail,
1593 unsigned int trail_length,
1594 const unsigned int finger_map_index)
1596 struct FingerInfo *new_finger_entry;
1597 //struct GNUNET_PeerIdentity key_ret;
1599 //struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1600 //struct FingerInfo *existing_finger;
1603 /* SUPU Here we trying to check if we already have an entry. If yes then we
1604 can keep two trails for redundant routing. if they are different then we
1605 need to choose the closest one. and remove the other one. */
1607 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1609 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1611 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1612 (const void **)&existing_finger))
1614 if ((finger_map_index == existing_finger->finger_map_index))
1616 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),finger_identity))
1618 /* FIXME: Here you should check if the trail is same. If yes then don't add the entry. it
1619 seems to be very suboptimal. */
1620 if ((existing_finger->trail_length) == trail_length)
1622 struct TrailPeerList *iterate;
1623 iterate = existing_finger->head;
1626 while (k < trail_length)
1628 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(iterate->peer), &finger_trail[k]))
1631 iterate = iterate->next;
1634 if (k == trail_length)
1644 if (finger_map_index == 1)
1646 ret = compare_predecessor (&(existing_finger->finger_identity),
1652 ret = compare_finger_identity (&(existing_finger->finger_identity),
1657 GNUNET_assert (GNUNET_YES ==
1658 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
1659 &(existing_finger->finger_identity),
1674 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
1675 memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
1676 new_finger_entry->finger_map_index = finger_map_index;
1678 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, finger_identity))
1680 /* I am the finger */
1681 new_finger_entry->trail_length = 0;
1682 /* FIXME: If I am the finger then why do we even do an entry. don't add any
1683 * field because it is of no use. you may just send a message to yourself
1684 * when another peer send you a trail setup or put request. */
1689 while (i < trail_length)
1691 struct TrailPeerList *element;
1692 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1693 element->next = NULL;
1694 element->prev = NULL;
1696 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
1697 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head, new_finger_entry->tail, element);
1700 new_finger_entry->trail_length = trail_length;
1703 /* FIXME: Here we are keeping multiple hashmap option so that there are
1704 multiple routes to reach to same finger, redundant routing.
1705 * Also same peers could be our fingers for different finger map index
1706 * Should we handle the case where we have same fingers at the different
1707 * finger index but with different trail to reach. */
1708 GNUNET_assert (GNUNET_OK ==
1709 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
1710 &(new_finger_entry->finger_identity),
1712 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
1714 if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap)
1715 && (new_finger_entry->finger_map_index!= 1))
1717 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1723 * Compare two peer identities.
1724 * @param p1 Peer identity
1725 * @param p2 Peer identity
1726 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
1729 compare_peer_id (const void *p1, const void *p2)
1731 struct Sorting_List *p11;
1732 struct Sorting_List *p22;
1734 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
1735 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
1736 p11 = (struct Sorting_List *)p1;
1737 p22 = (struct Sorting_List *)p2;
1738 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
1739 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
1745 * Return the successor of value in all_known_peers.
1746 * @param all_known_peers list of all the peers
1747 * @param value value we have to search in the all_known_peers.
1750 static struct Sorting_List *
1751 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
1760 middle = (first + last)/2;
1762 while(first <= last)
1764 if(all_known_peers[middle].peer_id < value)
1768 else if(all_known_peers[middle].peer_id == value)
1770 if(middle == (size -1))
1772 return &all_known_peers[0];
1776 return &all_known_peers[middle+1];
1784 middle = (first + last)/2;
1791 * here you should set the current source instead of destination type.
1792 * so current_source is actual source till we don't find another current_source
1793 * but is it good. why are we wasting space in case current_Destination is just us.
1794 * also in many case current_destination is just me. so again it does not seem
1796 * Find closest successor for the value.
1797 * @param value Value for which we are looking for successor
1798 * FIXME: pass the correct value for current_destination
1799 * @param[out] current_destination set to the end of the finger to traverse next
1800 * @param type Next destination type
1801 * @return Peer identity of next hop, NULL if we are the
1802 * ultimate destination
1804 static struct GNUNET_PeerIdentity *
1805 find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination,
1806 struct GNUNET_PeerIdentity *current_source)
1808 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1809 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1810 struct GNUNET_PeerIdentity key_ret;
1811 struct FriendInfo *friend;
1812 struct FingerInfo *finger;
1813 unsigned int finger_index;
1814 unsigned int friend_index;
1815 struct Sorting_List *successor;
1819 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
1820 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
1821 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
1824 struct Sorting_List all_known_peers[size];
1827 for (k = 0; k < size; k++)
1828 all_known_peers[k].peer_id = 0;
1830 /* Copy your identity at 0th index in all_known_peers. */
1832 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
1833 all_known_peers[j].type = MY_ID;
1834 all_known_peers[j].data = 0;
1838 all_known_peers[j].peer_id = value;
1839 all_known_peers[j].type = VALUE;
1840 all_known_peers[j].data = 0;
1843 /* Iterate over friend peer map and copy all the elements into array. */
1844 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1845 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
1847 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1849 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
1850 all_known_peers[j].type = FRIEND;
1851 all_known_peers[j].data = friend;
1856 /* Iterate over finger map and copy all the entries into all_known_peers array. */
1857 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1858 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1860 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1862 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
1863 all_known_peers[j].type = FINGER;
1864 all_known_peers[j].data = finger;
1869 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1870 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
1872 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
1874 /* search value in all_known_peers array. */
1875 successor = find_closest_successor (all_known_peers, value, size);
1877 if (successor->type == MY_ID)
1881 else if (successor->type == FRIEND)
1883 struct FriendInfo *target_friend;
1884 target_friend = (struct FriendInfo *)successor->data;
1885 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
1886 return current_destination;
1888 else if (successor->type == FINGER)
1890 struct GNUNET_PeerIdentity *next_hop;
1891 struct FingerInfo *finger;
1892 struct TrailPeerList *iterator;
1893 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
1894 finger = successor->data;
1895 iterator = finger->head;
1896 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1897 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
1898 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
1899 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
1910 /** FIXME: by default I keep current_source, and destination as my own id.
1911 * in case we find a finger then we update current_source in the
1912 * find_successor message.
1913 * Construct a Put message and send it to target_peer.
1914 * @param key Key for the content
1915 * @param data Content to store
1916 * @param data_size Size of content @a data in bytes
1917 * @param block_type Type of the block
1918 * @param options Routing options
1919 * @param desired_replication_level Desired replication count
1920 * @param expiration_time When does the content expire
1921 * @param current_destination
1922 * @param current_source
1923 * @param target_peer Peer to which this message will be forwarded.
1924 * @param hop_count Number of hops traversed so far.
1925 * @param put_path_length Total number of peers in @a put_path
1926 * @param put_path Number of peers traversed so far
1929 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
1930 const void *data, size_t data_size,
1931 enum GNUNET_BLOCK_Type block_type,
1932 enum GNUNET_DHT_RouteOption options,
1933 uint32_t desired_replication_level,
1934 struct GNUNET_TIME_Absolute expiration_time,
1935 struct GNUNET_PeerIdentity current_destination,
1936 struct GNUNET_PeerIdentity current_source,
1937 struct GNUNET_PeerIdentity *target_peer,
1939 uint32_t put_path_length,
1940 struct GNUNET_PeerIdentity *put_path)
1942 struct PeerPutMessage *ppm;
1943 struct P2PPendingMessage *pending;
1944 struct FriendInfo *target_friend;
1945 struct GNUNET_PeerIdentity *pp;
1948 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
1949 sizeof (struct PeerPutMessage);
1951 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1953 put_path_length = 0;
1954 msize = data_size + sizeof (struct PeerPutMessage);
1957 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1963 /* This is the first call made from clients file. So, we should search for the
1965 if (NULL == target_peer)
1968 struct GNUNET_PeerIdentity *next_hop;
1970 memcpy (&key_value, key, sizeof (uint64_t));
1971 struct GNUNET_PeerIdentity curr_dest;
1972 struct GNUNET_PeerIdentity curr_src;
1973 memcpy (&curr_dest, ¤t_destination, sizeof (struct GNUNET_PeerIdentity));
1974 memcpy (&curr_src, ¤t_source, sizeof (struct GNUNET_PeerIdentity));
1975 next_hop = find_successor (key_value, &curr_dest, &curr_src);
1976 /* FIXME: I am copying back current_destination and current_source. but I am not
1977 sure, if its correct. I am doing so just to remove the code from client file.*/
1978 memcpy (¤t_destination, &curr_dest, sizeof (struct GNUNET_PeerIdentity));
1979 memcpy (¤t_source, &curr_src, sizeof (struct GNUNET_PeerIdentity));
1981 if (NULL == next_hop) /* I am the destination do datacache_put */
1983 GDS_DATACACHE_handle_put (expiration_time, key, put_path_length, put_path,
1984 block_type, data_size, data);
1988 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1991 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1992 pending->timeout = expiration_time;
1993 ppm = (struct PeerPutMessage *) &pending[1];
1994 pending->msg = &ppm->header;
1995 ppm->header.size = htons (msize);
1996 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
1997 ppm->options = htonl (options);
1998 ppm->block_type = htonl (block_type);
1999 ppm->hop_count = htonl (hop_count + 1);
2000 ppm->desired_replication_level = htonl (desired_replication_level);
2001 ppm->put_path_length = htonl (put_path_length);
2002 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2004 ppm->current_destination = current_destination;
2005 ppm->current_source = current_source;
2007 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2008 if (put_path_length != 0)
2010 memcpy (pp, put_path,
2011 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2013 memcpy (&pp[put_path_length], data, data_size);
2014 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2015 target_friend->pending_count++;
2016 process_friend_queue (target_friend);
2021 /** FIXME: by default I keep current_source, and destination as my own id.
2022 * in case we find a finger then we update current_source in the
2023 * find_successor message.
2024 * Construct a Get message and send it to target_peer.
2025 * @param key Key for the content
2026 * @param block_type Type of the block
2027 * @param options Routing options
2028 * @param desired_replication_level Desired replication count
2029 * @param expiration_time When does the content expire
2030 * @param current_destination
2031 * @param current_source
2032 * @param target_peer Peer to which this message will be forwarded.
2033 * @param hop_count Number of hops traversed so far.
2034 * @param put_path_length Total number of peers in @a put_path
2035 * @param put_path Number of peers traversed so far
2038 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2039 enum GNUNET_BLOCK_Type block_type,
2040 enum GNUNET_DHT_RouteOption options,
2041 uint32_t desired_replication_level,
2042 struct GNUNET_PeerIdentity current_destination,
2043 struct GNUNET_PeerIdentity current_source,
2044 struct GNUNET_PeerIdentity *target_peer,
2046 uint32_t get_path_length,
2047 struct GNUNET_PeerIdentity *get_path)
2049 struct PeerGetMessage *pgm;
2050 struct P2PPendingMessage *pending;
2051 struct FriendInfo *target_friend;
2052 struct GNUNET_PeerIdentity *gp;
2055 msize = sizeof (struct PeerGetMessage) +
2056 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2058 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2064 if (NULL == target_peer)
2066 /* This is the first call from client file, we need to search for next_hop*/
2067 struct GNUNET_PeerIdentity *next_hop;
2069 struct GNUNET_PeerIdentity curr_dest;
2070 struct GNUNET_PeerIdentity curr_src;
2071 memcpy (&curr_dest, ¤t_destination, sizeof (struct GNUNET_PeerIdentity));
2072 memcpy (&curr_src, ¤t_source, sizeof (struct GNUNET_PeerIdentity));
2073 memcpy (&key_value, key, sizeof (struct GNUNET_PeerIdentity));
2074 next_hop = find_successor (key_value, &curr_dest, &curr_src);
2075 /* FIXME: Again I am copying back value of current_destination, current_source,
2076 Think of a better solution. */
2077 memcpy (¤t_destination, &curr_dest, sizeof (struct GNUNET_PeerIdentity));
2078 memcpy (¤t_source, &curr_src, sizeof (struct GNUNET_PeerIdentity));
2079 if (NULL == next_hop) /* I am the destination do datacache_put */
2081 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2082 NULL, 0, 1, &my_identity, NULL,&my_identity);
2087 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2091 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2092 pending->importance = 0; /* FIXME */
2093 pgm = (struct PeerGetMessage *) &pending[1];
2094 pending->msg = &pgm->header;
2095 pgm->header.size = htons (msize);
2096 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
2097 pgm->get_path_length = htonl (get_path_length);
2099 pgm->current_destination = current_destination;
2100 pgm->current_source = current_source;
2101 pgm->hop_count = htonl (hop_count + 1);
2103 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2104 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2105 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2106 target_friend->pending_count++;
2107 process_friend_queue (target_friend);
2112 * Send the get result to requesting client.
2113 * @param expiration When will this result expire?
2114 * @param key Key of the requested data.
2115 * @param put_path_length Number of peers in @a put_path
2116 * @param put_path Path taken to put the data at its stored location.
2117 * @param type Block type
2118 * @param data_size Size of the @a data
2119 * @param data Payload to store
2120 * @param get_path Path taken to reach to the location of the key.
2121 * @param get_path_length Number of peers in @a get_path
2122 * @param next_hop Next peer to forward the message to.
2123 * @param source_peer Peer which has the data for the key.
2126 GDS_NEIGHBOURS_send_get_result (struct GNUNET_TIME_Absolute expiration,
2127 const struct GNUNET_HashCode *key,
2128 unsigned int put_path_length,
2129 const struct GNUNET_PeerIdentity *put_path,
2130 enum GNUNET_BLOCK_Type type, size_t data_size,
2132 struct GNUNET_PeerIdentity *get_path,
2133 unsigned int get_path_length,
2134 struct GNUNET_PeerIdentity *next_hop,
2135 struct GNUNET_PeerIdentity *source_peer)
2137 struct PeerGetResultMessage *get_result;
2138 struct GNUNET_PeerIdentity *get_result_path;
2139 struct GNUNET_PeerIdentity *pp;
2140 struct P2PPendingMessage *pending;
2141 struct FriendInfo *target_friend;
2142 int current_path_index;
2145 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2146 sizeof (struct PeerPutMessage);
2148 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2154 current_path_index = search_my_index(get_path);
2155 if (0 == current_path_index)
2157 FPRINTF (stderr,_("\nSUPU %s, %s, %d"),__FILE__, __func__,__LINE__);
2158 GDS_CLIENTS_handle_reply (expiration, key, get_path_length, get_path, put_path_length,
2159 put_path, type, data_size, data);
2162 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2163 pending->importance = 0;
2164 get_result = (struct PeerGetResultMessage *)&pending[1];
2165 pending->msg = &get_result->header;
2166 get_result->header.size = htons (msize);
2167 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2168 get_result->key = *key;
2169 memcpy (&(get_result->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2170 get_result->expiration_time = expiration;
2172 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2173 memcpy (get_result_path, get_path,
2174 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2175 memcpy (&get_result_path[get_path_length], data, data_size);
2176 /* FIXME: Is this correct? */
2177 pp = (struct GNUNET_PeerIdentity *)&get_result_path[1];
2178 memcpy (pp, put_path,sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2180 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2181 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2182 target_friend->pending_count++;
2183 process_friend_queue (target_friend);
2188 * Send tral rejection message
2189 * @param source_peer Source peer which wants to set up the trail.
2190 * @param finger_identity Finger identity to which it want to setup the trail.
2191 * @param congested_peer Peer which has send trail rejection message
2192 * @param next_hop Peer to which this message should be forwarded.
2193 * @param finger_map_index
2194 * @param trail_peer_list
2195 * @param trail_length
2198 GDS_NEIGHBOURS_send_trail_rejection_message(struct GNUNET_PeerIdentity *source_peer,
2199 uint64_t finger_identity,
2200 struct GNUNET_PeerIdentity *congested_peer,
2201 const struct GNUNET_PeerIdentity *next_hop,
2202 unsigned int finger_map_index,
2203 struct GNUNET_PeerIdentity *trail_peer_list,
2204 unsigned int trail_length)
2206 struct PeerTrailRejectionMessage *trail_rejection;
2207 struct GNUNET_PeerIdentity *trail_list;
2208 struct P2PPendingMessage *pending;
2209 struct FriendInfo *target_friend;
2212 msize = sizeof (struct PeerTrailRejectionMessage);
2214 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2215 pending->importance = 0; /* FIXME */
2216 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2217 trail_rejection = (struct PeerTrailRejectionMessage *) &pending[1];
2218 pending->msg = &trail_rejection->header;
2219 trail_rejection->header.size = htons (msize);
2220 trail_rejection->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
2221 memcpy (&(trail_rejection->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2222 memcpy (&(trail_rejection->congested_peer), congested_peer, sizeof (struct GNUNET_PeerIdentity));
2223 memcpy (&(trail_rejection->finger_identity), &finger_identity, sizeof (uint64_t));
2224 trail_rejection->finger_map_index = htonl(finger_map_index);
2225 trail_rejection->trail_length = htonl (trail_length);
2227 trail_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
2228 memcpy (trail_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2230 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2231 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2232 target_friend->pending_count++;
2233 process_friend_queue (target_friend);
2245 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2246 const struct GNUNET_MessageHeader *message)
2248 struct PeerPutMessage *put;
2249 struct GNUNET_PeerIdentity *put_path;
2250 struct GNUNET_HashCode test_key;
2251 enum GNUNET_DHT_RouteOption options;
2252 struct GNUNET_PeerIdentity current_destination;
2253 struct GNUNET_PeerIdentity current_source;
2254 struct GNUNET_PeerIdentity *next_hop;
2258 size_t payload_size;
2261 msize = ntohs (message->size);
2262 if (msize < sizeof (struct PeerPutMessage))
2264 GNUNET_break_op (0);
2268 put = (struct PeerPutMessage *) message;
2269 putlen = ntohl (put->put_path_length);
2272 sizeof (struct PeerPutMessage) +
2273 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2275 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2277 GNUNET_break_op (0);
2281 current_destination = put->current_destination;
2282 current_source = put->current_source;
2283 put_path = (struct GNUNET_PeerIdentity *) &put[1];
2284 payload = &put_path[putlen];
2285 options = ntohl (put->options);
2286 payload_size = msize - (sizeof (struct PeerPutMessage) +
2287 putlen * sizeof (struct GNUNET_PeerIdentity));
2289 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
2290 payload, payload_size, &test_key))
2293 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
2295 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
2296 GNUNET_break_op (0);
2297 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2298 "PUT with key `%s' for block with key %s\n",
2299 put_s, GNUNET_h2s_full (&test_key));
2300 GNUNET_free (put_s);
2305 GNUNET_break_op (0);
2308 /* cannot verify, good luck */
2312 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
2314 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
2315 ntohl (put->block_type),
2317 NULL, 0, /* bloom filer */
2318 NULL, 0, /* xquery */
2319 payload, payload_size))
2321 case GNUNET_BLOCK_EVALUATION_OK_MORE:
2322 case GNUNET_BLOCK_EVALUATION_OK_LAST:
2325 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
2326 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
2327 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
2328 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
2329 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
2330 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
2332 GNUNET_break_op (0);
2337 struct GNUNET_PeerIdentity pp[putlen + 1];
2338 /* extend 'put path' by sender */
2339 /* FIXME: Check what are we doing here? */
2340 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
2342 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
2349 memcpy (&key_value, &(put->key), sizeof (uint64_t));
2350 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2352 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2353 if (next_hop == NULL)
2355 /* refer to handle_dht_p2p_trail_setup. */
2360 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2363 if (NULL == next_hop) /* I am the final destination */
2365 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
2366 &(put->key),putlen, pp, ntohl (put->block_type),
2367 payload_size, payload);
2372 GDS_CLIENTS_process_put (options,
2373 ntohl (put->block_type),
2374 ntohl (put->hop_count),
2375 ntohl (put->desired_replication_level),
2377 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2382 GDS_NEIGHBOURS_send_put (&put->key, payload, payload_size,
2383 ntohl (put->block_type),ntohl (put->options),
2384 ntohl (put->desired_replication_level),
2385 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2386 current_destination, current_source, next_hop,
2387 ntohl (put->hop_count), putlen, pp);
2391 return GNUNET_SYSERR;
2396 * Core handler for p2p get requests.
2398 * @param cls closure
2399 * @param peer sender of the request
2400 * @param message message
2401 * @return #GNUNET_OK to keep the connection open,
2402 * #GNUNET_SYSERR to close it (signal serious error)
2405 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
2406 const struct GNUNET_MessageHeader *message)
2408 struct PeerGetMessage *get;
2409 struct GNUNET_PeerIdentity *get_path;
2410 struct GNUNET_PeerIdentity current_destination;
2411 struct GNUNET_PeerIdentity current_source;
2412 struct GNUNET_PeerIdentity *next_hop;
2413 uint32_t get_length;
2417 msize = ntohs (message->size);
2418 if (msize < sizeof (struct PeerGetMessage))
2420 GNUNET_break_op (0);
2424 get = (struct PeerGetMessage *)message;
2425 get_length = ntohl (get->get_path_length);
2426 get_path = (struct GNUNET_PeerIdentity *)&get[1];
2427 current_destination = get->current_destination;
2428 current_source = get->current_source;
2431 sizeof (struct PeerGetMessage) +
2432 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
2434 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2436 GNUNET_break_op (0);
2440 /* Add sender to get path */
2441 struct GNUNET_PeerIdentity gp[get_length + 1];
2442 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
2443 gp[get_length + 1] = *peer;
2444 get_length = get_length + 1;
2446 memcpy (&key_value, &(get->key), sizeof (uint64_t));
2447 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2449 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2450 if (next_hop == NULL)
2452 /* refer to handle_dht_p2p_trail_setup. */
2457 next_hop = find_successor (key_value, ¤t_destination, ¤t_source);
2460 if (NULL == next_hop)
2462 /* FIXME: Try to make this code also short and remove useless variables. */
2463 struct GNUNET_PeerIdentity final_get_path[get_length+1];
2464 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
2465 memcpy (&final_get_path[get_length+1], &my_identity, sizeof (struct GNUNET_PeerIdentity));
2466 get_length = get_length + 1;
2467 struct GNUNET_PeerIdentity *next_hop;
2468 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2469 memcpy (next_hop, &final_get_path[get_length-2], sizeof (struct GNUNET_PeerIdentity));
2470 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
2471 get_length, final_get_path,next_hop, &my_identity);
2477 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
2478 get->desired_replication_level,current_destination,
2479 current_source, next_hop, 0,
2482 return GNUNET_SYSERR;
2488 * Core handler for get result
2489 * @param cls closure
2490 * @param peer sender of the request
2491 * @param message message
2492 * @return #GNUNET_OK to keep the connection open,
2493 * #GNUNET_SYSERR to close it (signal serious error)
2496 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
2497 const struct GNUNET_MessageHeader *message)
2499 /* If you are the source, go back to the client file and there search for
2500 the requesting client and send back the result. */
2501 struct PeerGetResultMessage *get_result;
2502 struct GNUNET_PeerIdentity *get_path;
2503 struct GNUNET_PeerIdentity *put_path;
2505 size_t payload_size;
2507 unsigned int getlen;
2508 unsigned int putlen;
2509 int current_path_index;
2511 msize = ntohs (message->size);
2512 if (msize < sizeof (struct PeerGetResultMessage))
2514 GNUNET_break_op (0);
2518 get_result = (struct PeerGetResultMessage *)message;
2519 getlen = ntohl (get_result->get_path_length);
2520 putlen = ntohl (get_result->put_path_length);
2523 sizeof (struct PeerGetResultMessage) +
2524 getlen * sizeof (struct GNUNET_PeerIdentity) +
2525 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2527 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
2529 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
2531 GNUNET_break_op (0);
2535 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
2536 payload = &get_path[getlen];
2537 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
2538 getlen * sizeof (struct GNUNET_PeerIdentity));
2539 /* FIXME: Check if its correct or not. */
2542 put_path = &get_path[1];
2546 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
2548 //GDS_CLIENTS_process_get_result();
2549 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
2550 getlen, get_path, putlen,
2551 put_path, get_result->type, payload_size, payload);
2556 struct GNUNET_PeerIdentity *next_hop;
2557 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2558 current_path_index = search_my_index (get_path);
2559 /* FIXME: First check if you are adding yourself to the get path or not.
2560 if yes then don't check if current_path_index == 0, if not then check
2561 and next_hop == source_peer. */
2562 memcpy (next_hop, &get_path[current_path_index - 1], sizeof (struct GNUNET_PeerIdentity));
2564 GDS_NEIGHBOURS_send_get_result (get_result->expiration_time, &(get_result->key),
2566 get_result->type, payload_size,payload,
2568 next_hop, &(get_result->source_peer));
2571 return GNUNET_SYSERR;
2576 * Handle a PeerTrailSetupMessage.
2577 * @param cls closure
2578 * @param message message
2579 * @param peer peer identity this notification is about
2580 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2583 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
2584 const struct GNUNET_MessageHeader *message)
2586 const struct PeerTrailSetupMessage *trail_setup;
2587 struct GNUNET_PeerIdentity current_destination;
2588 struct GNUNET_PeerIdentity current_source;
2589 struct GNUNET_PeerIdentity source;
2590 struct GNUNET_PeerIdentity *next_hop;
2591 struct GNUNET_PeerIdentity next_peer;
2592 struct GNUNET_PeerIdentity *trail_peer_list;
2593 struct FriendInfo *target_friend;
2594 uint64_t destination_finger_value;
2595 uint32_t trail_length;
2596 uint32_t finger_map_index;
2599 msize = ntohs (message->size);
2600 if (msize < sizeof (struct PeerTrailSetupMessage))
2602 GNUNET_break_op (0);
2606 trail_setup = (const struct PeerTrailSetupMessage *) message;
2607 trail_length = ntohl (trail_setup->trail_length);
2609 if ((msize < sizeof (struct PeerTrailSetupMessage) +
2610 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2612 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2614 GNUNET_break_op (0);
2618 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
2619 current_destination = trail_setup->current_destination;
2620 current_source = trail_setup->current_source;
2621 source = trail_setup->source_peer;
2622 finger_map_index = ntohl (trail_setup->finger_map_index);
2623 destination_finger_value = ntohl (trail_setup->destination_finger);
2625 /* Check if you are part of the trail or current destination, and accordingly
2626 * find the next peer to send the message to. */
2627 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2629 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2630 /* ADDNOW: OPTIMIZATION: do find_successor also and get a better path if possible. */
2632 if (next_hop == NULL)
2634 /* FIXME next_hop to NULL, 1. statistics update, drop the message.
2635 2. complain to sender with new message: trail lost */
2641 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source);
2644 /* Now add yourself to the trail. */
2645 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
2646 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2647 peer_list[trail_length] = my_identity;
2650 /* Check next_hop type and make the judgment what to do next. */
2651 if (NULL == next_hop) /* This means I am the final destination */
2653 if (trail_length == 1)
2655 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
2659 memcpy (&next_peer, &trail_peer_list[trail_length-2], sizeof (struct GNUNET_PeerIdentity));
2662 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
2663 /* FIXME: URGENT change it to handle the change in current_finger_index.
2664 compare to your own predecessor */
2665 if (compare_predecessor (&source) /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */)
2667 struct GNUNET_PeerIdentity *new_trail_list;
2668 new_trail_list = invert_trail_list (&source, peer_list, trail_length);
2669 finger_table_add (&source, new_trail_list, trail_length, PREDECESSOR_FINGER_ID);
2671 GDS_NEIGHBOURS_send_trail_setup_result (&source,
2673 target_friend, trail_length,
2680 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2681 GDS_NEIGHBOURS_send_trail_setup (&source,
2682 destination_finger_value,
2683 ¤t_destination, ¤t_source,
2684 target_friend, trail_length, peer_list,
2688 return GNUNET_SYSERR;
2693 * Core handle for p2p trail construction result messages.
2695 * @param message message
2696 * @param peer peer identity this notification is about
2697 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2700 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2701 const struct GNUNET_MessageHeader *message)
2703 const struct PeerTrailSetupResultMessage *trail_result;
2704 const struct GNUNET_PeerIdentity *trail_peer_list;
2705 uint32_t trail_length;
2706 uint32_t finger_map_index;
2709 msize = ntohs (message->size);
2710 if (msize < sizeof (struct PeerTrailSetupResultMessage))
2712 GNUNET_break_op (0);
2716 trail_result = (const struct PeerTrailSetupResultMessage *) message;
2717 trail_length = ntohl (trail_result->trail_length);
2720 sizeof (struct PeerTrailSetupResultMessage) +
2721 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2723 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2725 GNUNET_break_op (0);
2729 finger_map_index = htonl (trail_result->finger_map_index);
2730 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
2732 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2735 finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length,
2741 struct GNUNET_PeerIdentity next_hop;
2742 struct FriendInfo *target_friend;
2745 my_index = search_my_index (trail_peer_list);
2748 next_hop = trail_result->destination_peer;
2751 next_hop = trail_peer_list[my_index - 1];
2753 /* Finger table of destination peer will not contain any trail for the case
2754 * where destination peer is its own finger identity. */
2755 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2756 &(trail_result->finger_identity))))
2758 GDS_ROUTING_add (&(trail_result->destination_peer), &(trail_result->finger_identity),
2762 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2763 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
2764 &(trail_result->finger_identity),
2765 target_friend, trail_length,
2770 return GNUNET_SYSERR;
2775 * FIXME: Use flag in the case finger peer map does not contain predcessor
2776 * then its NULL. Ideally it should never happen.
2777 * Get my current predecessor from the finger peer map
2778 * @return Current predecessor.
2780 static struct FingerInfo *
2783 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2784 struct GNUNET_PeerIdentity key_ret;
2785 unsigned int finger_index;
2786 struct FingerInfo *my_predecessor;
2788 /* Iterate over finger peer map and extract your predecessor. */
2789 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2790 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2792 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
2793 (finger_iter,&key_ret,(const void **)&my_predecessor))
2795 if(1 == my_predecessor->finger_map_index)
2801 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2802 return my_predecessor;
2807 * Core handle for p2p verify successor messages.
2808 * @param cls closure
2809 * @param message message
2810 * @param peer peer identity this notification is about
2811 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2814 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2815 const struct GNUNET_MessageHeader *message)
2817 const struct PeerVerifySuccessorMessage *vsm;
2818 const struct GNUNET_PeerIdentity *trail_peer_list;
2819 struct GNUNET_PeerIdentity next_hop;
2820 struct FriendInfo *target_friend;
2822 uint32_t trail_length;
2824 msize = ntohs (message->size);
2825 if (msize < sizeof (struct PeerVerifySuccessorMessage))
2827 GNUNET_break_op (0);
2831 vsm = (struct PeerVerifySuccessorMessage *) message;
2832 trail_length = ntohl (vsm->trail_length);
2834 if ((msize < sizeof (struct PeerVerifySuccessorMessage) +
2835 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2836 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2838 GNUNET_break_op (0);
2842 trail_peer_list = (const struct GNUNET_PeerIdentity *)&vsm[1];
2843 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity)))
2845 /*FIXME:URGENT:IMPLEMENT Here you are the successor, here you should check your predecessor
2846 and if there is no predecessor then just add this peer and send result
2847 if there is some other predecessor, then construct a new trial and then
2848 send back the list to requesting peer. */
2854 my_index = search_my_index (trail_peer_list);
2855 memcpy (&next_hop, &trail_peer_list[my_index], sizeof (struct GNUNET_PeerIdentity));
2856 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2858 GDS_NEIGHBOURS_send_verify_successor (&(vsm->source_peer), &(vsm->successor),target_friend,
2859 trail_peer_list, trail_length);
2861 return GNUNET_SYSERR;
2866 * Core handle for p2p verify successor messages.
2867 * @param cls closure
2868 * @param message message
2869 * @param peer peer identity this notification is about
2870 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2873 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2874 const struct GNUNET_MessageHeader *message)
2876 struct PeerVerifySuccessorMessage *vsm;
2877 struct GNUNET_PeerIdentity *trail_peer_list;
2878 struct FriendInfo *target_friend;
2879 struct GNUNET_PeerIdentity *next_hop;
2880 struct GNUNET_PeerIdentity *source_peer;
2881 unsigned int trail_length;
2884 msize = ntohs (message->size);
2885 if (msize < sizeof (struct PeerVerifySuccessorMessage))
2887 GNUNET_break_op (0);
2891 vsm = (struct PeerVerifySuccessorMessage *) message;
2892 trail_length = ntohl (vsm->trail_length);
2894 if ((msize < sizeof (struct PeerVerifySuccessorMessage) +
2895 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2896 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2898 GNUNET_break_op (0);
2902 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
2903 source_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2904 memcpy (source_peer, &(vsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
2906 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2908 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity)))
2910 struct FingerInfo *my_predecessor;
2911 if (trail_length == 1)
2912 memcpy (next_hop, source_peer, sizeof (struct GNUNET_PeerIdentity));
2915 int current_trail_index;
2916 current_trail_index = search_my_index (trail_peer_list);
2917 memcpy (next_hop, &trail_peer_list[current_trail_index-1], sizeof (struct GNUNET_PeerIdentity));
2919 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2920 GNUNET_free (next_hop);
2922 my_predecessor = get_predecessor();
2923 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (source_peer,
2924 &(my_predecessor->finger_identity))))
2926 GDS_NEIGHBOURS_send_verify_successor_result (source_peer,
2928 &(my_predecessor->finger_identity),
2935 struct GNUNET_PeerIdentity *new_successor_trail;
2936 int new_trail_length;
2939 new_trail_length = trail_length + my_predecessor->trail_length;
2940 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * new_trail_length);
2941 memcpy (new_successor_trail, trail_peer_list, (trail_length) * sizeof (struct GNUNET_PeerIdentity));
2942 struct TrailPeerList *iterator;
2943 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
2944 iterator = my_predecessor->head;
2946 while (i < new_trail_length)
2948 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2949 iterator = iterator->next;
2953 GDS_NEIGHBOURS_send_verify_successor_result (source_peer,
2955 &(my_predecessor->finger_identity),
2957 new_successor_trail,
2964 unsigned int current_trail_index;
2965 current_trail_index = search_my_index (trail_peer_list);
2966 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2967 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2968 GNUNET_free (next_hop);
2970 GDS_NEIGHBOURS_send_verify_successor (source_peer, &(vsm->successor),target_friend,
2971 trail_peer_list, trail_length);
2978 * Core handle for p2p verify successor result messages.
2979 * @param cls closure
2980 * @param message message
2981 * @param peer peer identity this notification is about
2982 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2985 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2986 const struct GNUNET_MessageHeader *message)
2988 const struct PeerVerifySuccessorResultMessage *vsrm;
2989 const struct GNUNET_PeerIdentity *trail_peer_list;
2990 struct GNUNET_PeerIdentity next_hop;
2991 struct FriendInfo *target_friend;
2993 uint32_t trail_length;
2995 msize = ntohs (message->size);
2996 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
2998 GNUNET_break_op (0);
3002 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
3003 trail_length = ntohl (vsrm->trail_length);
3006 sizeof (struct PeerVerifySuccessorResultMessage) +
3007 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3009 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3011 GNUNET_break_op (0);
3015 trail_peer_list = (const struct GNUNET_PeerIdentity *) &vsrm[1];
3017 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), &(my_identity))))
3019 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), &(my_identity))))
3021 finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0);
3022 memcpy (&next_hop, &trail_peer_list[0], sizeof (struct GNUNET_PeerIdentity));
3023 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3024 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
3025 target_friend, trail_peer_list,
3034 my_index = search_my_index (trail_peer_list);
3036 memcpy (&next_hop, &(vsrm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
3038 memcpy (&next_hop, &trail_peer_list[my_index-1], sizeof (struct GNUNET_PeerIdentity));
3039 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3040 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
3041 &(vsrm->source_successor),
3042 &(vsrm->my_predecessor),
3048 return GNUNET_SYSERR;
3053 * Check if there is already an entry in finger_peermap for predecessor,
3054 * If not then add peer as your predecessor.
3055 * Else compare existing entry and peer, and choose the closest one as predecessor.
3056 * @param peer Peer identity
3057 * @param trail_peer_list Trail to reach from @a peer to me.
3060 update_predecessor (const struct GNUNET_PeerIdentity *peer,
3061 const struct GNUNET_PeerIdentity *trail_peer_list)
3063 /*FIXME: URGENT: Here you should first check if there is already an entry for predecessor
3064 field or not. if not then add peer. else compare existing entry and peer,
3065 and choose the closest one as predecessor. I am confused should I call a
3066 function which just checks if this peer can be predecessor or not, and then
3067 call another function to add it. Or call a single function which checks
3068 it all and add the entry. we are never going to communicate with the peer
3069 if it is my predecessor or not. so, we don't care about the result. */
3075 * Core handle for p2p notify new successor messages.
3076 * @param cls closure
3077 * @param message message
3078 * @param peer peer identity this notification is about
3079 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3082 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3083 const struct GNUNET_MessageHeader *message)
3085 const struct PeerNotifyNewSuccessorMessage *nsm;
3086 const struct GNUNET_PeerIdentity *trail_peer_list;
3088 uint32_t trail_length;
3090 msize = ntohs (message->size);
3091 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
3093 GNUNET_break_op (0);
3097 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
3098 trail_length = ntohl (nsm->trail_length);
3100 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
3101 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3103 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3105 GNUNET_break_op (0);
3109 trail_peer_list = (const struct GNUNET_PeerIdentity *) &nsm[1];
3111 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer), &my_identity)))
3113 update_predecessor (&(nsm->destination_peer), trail_peer_list);
3118 struct FriendInfo *target_friend;
3119 struct GNUNET_PeerIdentity next_hop;
3122 my_index = search_my_index (trail_peer_list);
3123 memcpy (&next_hop, &trail_peer_list[my_index+1], sizeof (struct GNUNET_PeerIdentity));
3124 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3125 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
3126 &(nsm->destination_peer),
3127 target_friend, trail_peer_list,
3131 return GNUNET_SYSERR;
3136 * FIXME: I am not sure if this is correct or not. once I am done with
3137 * basic implementation then will handle threshold limits.
3138 * Does it matter if the packet was going to a finger or friend?
3139 * Core handle for p2p trail rejection messages.
3140 * @param cls closure
3141 * @param message message
3142 * @param peer peer identity this notification is about
3143 * @return GNUNET_OK on success, GNUNET_SYSERR on error
3146 int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3147 const struct GNUNET_MessageHeader *message)
3149 struct PeerTrailRejectionMessage *trail_rejection;
3150 struct FailedTrail *trail_fail;
3151 struct FriendInfo *target_friend;
3152 struct GNUNET_PeerIdentity *trail_peer_list;
3153 unsigned int finger_map_index;
3156 msize = ntohs (message->size);
3157 if (msize < sizeof (struct PeerTrailRejectionMessage))
3159 GNUNET_break_op (0);
3163 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3164 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3165 finger_map_index = ntohl (trail_rejection->finger_map_index);
3166 trail_fail = GNUNET_malloc (sizeof (struct FailedTrail));
3167 memcpy (&(trail_fail->source_peer), &(trail_rejection->source_peer), sizeof (struct GNUNET_PeerIdentity));
3168 memcpy (&(trail_fail->congested_peer), &(trail_rejection->congested_peer), sizeof (struct GNUNET_PeerIdentity));
3169 memcpy (&(trail_fail->destination_finger_value), &(trail_rejection->finger_identity), sizeof (uint64_t));
3171 GNUNET_assert (GNUNET_OK ==
3172 GNUNET_CONTAINER_multipeermap_put (failed_trail_list, &(trail_fail->source_peer),
3173 trail_fail, GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
3175 /* FIXME: Is it okay if I pass the struct as parameter. */
3176 target_friend = select_random_friend (&(trail_fail->congested_peer));
3178 if(NULL != target_friend)
3180 GDS_NEIGHBOURS_send_trail_setup (&(trail_fail->source_peer),
3181 trail_fail->destination_finger_value,
3182 &(target_friend->id),
3183 NULL, target_friend, ntohl (trail_rejection->trail_length),
3188 return GNUNET_SYSERR;
3192 * Core handle for p2p trail tear down messages.
3193 * @param cls closure
3194 * @param message message
3195 * @param peer peer identity this notification is about
3196 * @return GNUNET_OK on success, GNUNET_SYSERR on error
3199 int handle_dht_p2p_trail_treadown (void *cls, const struct GNUNET_PeerIdentity *peer,
3200 const struct GNUNET_MessageHeader *message)
3202 /* Call is made to this function when the source peer removes an existing
3203 finger entry and it need to inform the peers which are part of the trail to remove
3204 the trail from their routing table. So, this peer should first
3205 get the next hop and then delete the entry. */
3211 * FIXME: free_finger(remove_finger); Call this function at finger_table_add,
3212 when you replace an existing entry
3213 * Free finger and its trail.
3214 * @param remove_finger Finger to be freed.
3217 free_finger (struct FingerInfo *finger)
3219 struct TrailPeerList *peer;
3221 while (NULL != (peer = finger->head))
3223 GNUNET_CONTAINER_DLL_remove (finger->head, finger->tail, peer);
3227 GNUNET_free (finger);
3232 * Iterate over finger_peermap, and remove entries with peer as the first element
3234 * @param cls closure
3235 * @param key current public key
3236 * @param value value in the hash map
3237 * @return #GNUNET_YES if we should continue to
3239 * #GNUNET_NO if not.
3242 remove_matching_finger (void *cls,
3243 const struct GNUNET_PeerIdentity *key,
3246 struct FingerInfo *remove_finger = value;
3247 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
3249 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->head->peer, disconnected_peer))
3251 GNUNET_assert (GNUNET_YES ==
3252 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
3255 free_finger (remove_finger);
3262 * Method called whenever a peer disconnects.
3264 * @param cls closure
3265 * @param peer peer identity this notification is about
3268 handle_core_disconnect (void *cls,
3269 const struct GNUNET_PeerIdentity *peer)
3271 struct FriendInfo *remove_friend;
3273 /* Check for self message. */
3274 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
3277 /* Search for peer to remove in your friend_peermap. */
3279 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
3281 if (NULL == remove_friend)
3287 /* Remove fingers for which this peer is the first element in the trail. */
3288 GNUNET_CONTAINER_multipeermap_iterate (finger_peermap,
3289 &remove_matching_finger, (void *)peer);
3291 /* Remove routing trails of which this peer is a part. */
3292 GDS_ROUTING_remove_entry (peer);
3294 /* Remove the peer from friend_peermap. */
3295 GNUNET_assert (GNUNET_YES ==
3296 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
3300 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
3303 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3305 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3306 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3311 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
3313 GNUNET_SCHEDULER_cancel (verify_successor);
3314 verify_successor = GNUNET_SCHEDULER_NO_TASK;
3320 * Method called whenever a peer connects.
3322 * @param cls closure
3323 * @param peer_identity peer identity this notification is about
3326 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
3328 struct FriendInfo *friend;
3330 /* Check for connect to self message */
3331 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
3334 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
3336 /* If peer already exists in our friend_peermap, then exit. */
3337 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
3343 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
3346 friend = GNUNET_new (struct FriendInfo);
3347 friend->id = *peer_identity;
3349 GNUNET_assert (GNUNET_OK ==
3350 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
3351 peer_identity, friend,
3352 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
3354 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
3355 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
3356 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
3361 * To be called on core init/fail.
3363 * @param cls service closure
3364 * @param identity the public identity of this peer
3367 core_init (void *cls,
3368 const struct GNUNET_PeerIdentity *identity)
3370 my_identity = *identity;
3375 * Initialize neighbours subsystem.
3376 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3379 GDS_NEIGHBOURS_init (void)
3381 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
3382 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
3383 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
3384 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
3385 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
3386 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
3387 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
3388 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
3389 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
3390 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
3391 {&handle_dht_p2p_trail_treadown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
3396 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
3397 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
3398 GNUNET_NO, core_handlers);
3399 if (NULL == core_api)
3400 return GNUNET_SYSERR;
3402 /* Initialize the current index in the finger map. */
3403 current_finger_index = PREDECESSOR_FINGER_ID;
3405 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
3406 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS * 4/3, GNUNET_NO);
3407 /* FIXME: Not sure if this value is correct for this data structure. also
3408 * not sure if we actually need any such data structure. Once done with other functions,
3409 * will revisit this part. */
3410 failed_trail_list = GNUNET_CONTAINER_multipeermap_create (LINK_THRESHOLD * 4/3, GNUNET_NO);
3416 * Shutdown neighbours subsystem.
3419 GDS_NEIGHBOURS_done (void)
3421 if (NULL == core_api)
3424 GNUNET_CORE_disconnect (core_api);
3427 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
3428 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
3429 friend_peermap = NULL;
3431 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
3432 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
3433 finger_peermap = NULL;
3435 /* FIXME: Here I have added GNUNET_break(0) as ideally if friend_peermap
3436 is already zero, then we really don't need to cancel it again. If this
3437 condition happens it mean we might have missed some corner case. */
3438 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3441 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3442 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3445 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
3448 GNUNET_SCHEDULER_cancel (verify_successor);
3449 verify_successor = GNUNET_SCHEDULER_NO_TASK;
3455 * FIXME: Here I want to send only the value not the address. Initially
3456 * I wanted to make it const struct * so that no other function can change it.
3457 * then in client file, i make a copy and send that copy. now I have made this
3461 * @return my identity
3463 struct GNUNET_PeerIdentity
3464 GDS_NEIGHBOURS_get_my_id (void)
3470 /* end of gnunet-service-xdht_neighbours.c */