2 This file is part of GNUnet.
3 (C) 2009-2013 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file dht/gnunet-service-xdht_neighbours.c
23 * @brief GNUnet DHT service's finger and friend table management code
24 * @author Supriti Singh
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_nse_service.h"
34 #include "gnunet_ats_service.h"
35 #include "gnunet_core_service.h"
36 #include "gnunet_datacache_lib.h"
37 #include "gnunet_transport_service.h"
38 #include "gnunet_hello_lib.h"
39 #include "gnunet_dht_service.h"
40 #include "gnunet_statistics_service.h"
41 #include "gnunet-service-xdht.h"
42 #include "gnunet-service-xdht_clients.h"
43 #include "gnunet-service-xdht_datacache.h"
44 #include "gnunet-service-xdht_hello.h"
45 #include "gnunet-service-xdht_neighbours.h"
46 #include "gnunet-service-xdht_nse.h"
47 #include "gnunet-service-xdht_routing.h"
52 1. Use a global array of all known peers in find_successor, Only when
53 a new peer is added in finger or friend peer map, then re calculate
54 the array. Or else use the old one.
55 2. Should we be using const in all the handle for the message we received
56 * and then copy the fields and make changes to the fields instead of sending
58 * 3. Everywhere you are storing yourself as the first element in the trail.
59 * It is obviously taking too much space. Try to remove it and think of something
61 4. Choose the correct interval to send finger and verify message.
62 5. Do we need expiration time for trail setup and all other messages? TTL
63 6. In case of trail setup after TTL, we should again send the request but
64 * through a different route. How do we remeber each time which friend we
65 * chose last time for the trail setup. We will need a data structure where we
66 * add entry in finger table add and when setup is done remove it.
67 * 7. I have not added any authentication on messages exachanged between peers.
68 * Only when basic put/get is correct I will add it. */
71 * Maximum possible fingers of a peer.
73 #define MAX_FINGERS 64
76 * Maximum allowed number of pending messages per friend peer.
78 #define MAXIMUM_PENDING_PER_FRIEND 64
81 * How long at least to wait before sending another find finger trail request.
83 #define DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
86 * How long at most to wait before sending another find finger trail request.
88 #define DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 10)
91 * How long at most to wait for transmission of a GET request to another peer?
93 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
96 * Maximum number of trails allowed to go through a friend.
98 #define LINK_THRESHOLD 64
101 GNUNET_NETWORK_STRUCT_BEGIN
106 struct PeerPutMessage
109 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
111 struct GNUNET_MessageHeader header;
116 uint32_t options GNUNET_PACKED;
121 uint32_t type GNUNET_PACKED;
126 uint32_t hop_count GNUNET_PACKED;
129 * Replication level for this message
131 uint32_t desired_replication_level GNUNET_PACKED;
134 * Length of the PUT path that follows (if tracked).
136 uint32_t put_path_length GNUNET_PACKED;
141 struct GNUNET_PeerIdentity source_peer;
144 * Current destination
146 struct GNUNET_PeerIdentity current_destination;
149 * Current destination type
151 enum current_destination_type current_destination_type;
154 * When does the content expire?
156 struct GNUNET_TIME_AbsoluteNBO expiration_time;
159 * The key to store the value under.
161 struct GNUNET_HashCode key GNUNET_PACKED;
164 /* put path (if tracked) */
174 struct PeerGetResultMessage
177 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT
179 struct GNUNET_MessageHeader header;
182 * Peer which is sending get result message.
184 struct GNUNET_PeerIdentity source_peer;
187 * Peer which will receive the get result message.
189 struct GNUNET_PeerIdentity destination_peer;
192 * Current index in get path.
194 unsigned int current_path_index;
197 * Length of the GET path that follows (if tracked).
199 uint32_t get_path_length GNUNET_PACKED;
202 * When does the content expire?
204 struct GNUNET_TIME_AbsoluteNBO expiration_time;
207 * The key of the corresponding GET request.
209 struct GNUNET_HashCode key;
211 /* put path (if tracked) */
213 /* get path (if tracked) */
223 struct PeerGetMessage
226 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
228 struct GNUNET_MessageHeader header;
233 struct GNUNET_PeerIdentity source_peer;
236 * Total number of peers in get path.
238 unsigned int get_path_length;
243 struct GNUNET_PeerIdentity current_destination;
248 enum current_destination_type current_dest_type;
251 * Unique identifier of the request.
255 * When does the content expire?
257 struct GNUNET_TIME_AbsoluteNBO expiration_time;
260 * The key we are looking for.
262 struct GNUNET_HashCode key;
270 * P2P Trail setup message
272 struct PeerTrailSetupMessage
276 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
278 struct GNUNET_MessageHeader header;
281 * Source peer which wants to setup the trail to one of its finger.
283 struct GNUNET_PeerIdentity source_peer;
286 * Successor of this finger value will be our finger peer.
288 uint64_t destination_finger;
291 * Peer which gets this message can be either an intermediate finger or friend.
293 enum current_destination_type current_destination_type;
296 * Peer to which this packet is forwarded.
298 struct GNUNET_PeerIdentity current_destination;
301 * Index into finger peer map.
303 unsigned int finger_map_index;
306 * Number of entries in trail list.
308 uint32_t trail_length GNUNET_PACKED;
314 * P2P Trail Setup Result message
316 struct PeerTrailSetupResultMessage
320 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
322 struct GNUNET_MessageHeader header;
325 * Finger to which we have found the path.
327 struct GNUNET_PeerIdentity finger_identity;
330 * Peer which was looking for the trail to finger.
332 struct GNUNET_PeerIdentity destination_peer;
335 * Trail index which points to next destination to send this message.
337 unsigned int current_index;
340 * Index into finger peer map
342 unsigned int finger_map_index;
345 * Number of entries in trail list.
347 uint32_t trail_length GNUNET_PACKED;
353 * P2P Verify Successor message.
355 struct PeerVerifySuccessorMessage
359 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
361 struct GNUNET_MessageHeader header;
364 * Source peer which wants to verify its successor.
366 struct GNUNET_PeerIdentity source_peer;
369 * My current successor.
371 struct GNUNET_PeerIdentity successor;
374 * Total number of peers in trail to current successor.
376 unsigned int trail_length;
379 * Trail index which points to next destination to send this message.
381 unsigned int current_trail_index;
387 * P2P Verify Successor Result message.
389 struct PeerVerifySuccessorResultMessage
393 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
395 struct GNUNET_MessageHeader header;
398 * Destination peer which sent the request to verify its successor.
400 struct GNUNET_PeerIdentity destination_peer;
403 * Successor to which PeerVerifySuccessorMessage was sent.
405 struct GNUNET_PeerIdentity source_successor;
408 * source_successor's predecessor
410 struct GNUNET_PeerIdentity my_predecessor;
413 * Total number of peers in trail.
414 * If source_successor is not destination peer, then trail is from destination_peer
416 * If source_successor is destination peer, then trail is from destination_peer
417 * to source_successor.
419 unsigned int trail_length;
422 * Trail index which points to next destination to send this message.
424 unsigned int current_index;
429 * P2P Notify New Successor message.
431 struct PeerNotifyNewSuccessorMessage
434 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
436 struct GNUNET_MessageHeader header;
439 * Source peer which wants to notify its new successor.
441 struct GNUNET_PeerIdentity source_peer;
444 * New successor identity.
446 struct GNUNET_PeerIdentity destination_peer;
449 * Number of peers in trail from source_peer to new successor.
451 unsigned int trail_length;
454 * Trail index which points to next destination to send this message.
456 unsigned int current_index;
461 GNUNET_NETWORK_STRUCT_END
465 * Linked list of messages to send to a particular other peer.
467 struct P2PPendingMessage
470 * Pointer to next item in the list
472 struct P2PPendingMessage *next;
475 * Pointer to previous item in the list
477 struct P2PPendingMessage *prev;
480 * When does this message time out?
482 struct GNUNET_TIME_Absolute timeout;
485 * Message importance level. FIXME: used? useful?
487 unsigned int importance;
490 * Actual message to be sent, allocated at the end of the struct:
491 * // msg = (cast) &pm[1];
492 * // memcpy (&pm[1], data, len);
494 const struct GNUNET_MessageHeader *msg;
500 * Linked List of peers which are part of trail to reach a particular Finger.
505 * Pointer to next item in the list
507 struct TrailPeerList *next;
510 * Pointer to previous item in the list
512 struct TrailPeerList *prev;
515 * An element in this trail list
517 struct GNUNET_PeerIdentity peer;
523 * Entry in friend_peermap.
530 struct GNUNET_PeerIdentity id;
533 * Number of trail of which this friend is the first hop.
535 unsigned int trail_links;
538 * Count of outstanding messages for this friend.
540 unsigned int pending_count;
543 * Head of pending messages to be sent to this friend.
545 struct P2PPendingMessage *head;
548 * Tail of pending messages to be sent to this friend.
550 struct P2PPendingMessage *tail;
553 * Core handle for sending messages to this friend.
555 struct GNUNET_CORE_TransmitHandle *th;
561 * Entry in finger_peermap.
568 struct GNUNET_PeerIdentity finger_identity;
571 * Index in finger peer map
573 unsigned int finger_map_index;
576 * Total number of entries in trail from [me,finger]
578 unsigned int trail_length;
581 * Head of trail to reach this finger.
583 struct TrailPeerList *head;
586 * Tail of trail to reach this finger.
588 struct TrailPeerList *tail;
594 * FIXME: Think of a better name.
595 * Data structure passed to sorting algorithm in find_successor.
600 * 64 bit value of peer identity
605 * Type : MY_ID, FINGER, FINGER, Value
607 enum current_destination_type type;
610 * Pointer to original data structure linked to peer id.
617 * Task that sends FIND FINGER TRAIL requests.
619 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
623 * Task that periodically verifies my successor.
625 static GNUNET_SCHEDULER_TaskIdentifier verify_successor;
628 * Identity of this peer.
630 static struct GNUNET_PeerIdentity my_identity;
633 * Hash map of all the friends of a peer
635 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
638 * Hash map of all the fingers of a peer
640 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
645 static struct GNUNET_CORE_Handle *core_api;
648 * FIXME: Is it safe to assume its initialized to 0 by default.
649 * The current finger index that we have found trail to.
651 static unsigned int current_finger_index;
655 * Called when core is ready to send a message we asked for
656 * out to the destination.
658 * @param cls the 'struct FriendInfo' of the target friend
659 * @param size number of bytes available in buf
660 * @param buf where the callee should write the message
661 * @return number of bytes written to buf
664 core_transmit_notify (void *cls, size_t size, void *buf)
666 struct FriendInfo *peer = cls;
668 struct P2PPendingMessage *pending;
673 while ((NULL != (pending = peer->head)) &&
674 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
676 peer->pending_count--;
677 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
678 GNUNET_free (pending);
682 /* no messages pending */
688 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
689 GNUNET_CORE_PRIO_BEST_EFFORT,
690 GNUNET_TIME_absolute_get_remaining
691 (pending->timeout), &peer->id,
692 ntohs (pending->msg->size),
693 &core_transmit_notify, peer);
694 GNUNET_break (NULL != peer->th);
698 while ((NULL != (pending = peer->head)) &&
699 (size - off >= (msize = ntohs (pending->msg->size))))
701 GNUNET_STATISTICS_update (GDS_stats,
703 ("# Bytes transmitted to other peers"), msize,
705 memcpy (&cbuf[off], pending->msg, msize);
707 peer->pending_count--;
708 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
709 GNUNET_free (pending);
711 if (peer->head != NULL)
714 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
715 GNUNET_CORE_PRIO_BEST_EFFORT,
716 GNUNET_TIME_absolute_get_remaining
717 (pending->timeout), &peer->id, msize,
718 &core_transmit_notify, peer);
719 GNUNET_break (NULL != peer->th);
726 * Transmit all messages in the friend's message queue.
728 * @param peer message queue to process
731 process_friend_queue (struct FriendInfo *peer)
733 struct P2PPendingMessage *pending;
735 if (NULL == (pending = peer->head))
737 if (NULL != peer->th)
740 GNUNET_STATISTICS_update (GDS_stats,
742 ("# Bytes of bandwidth requested from core"),
743 ntohs (pending->msg->size), GNUNET_NO);
745 /* FIXME: Are we correctly initializing importance and pending. */
747 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
749 GNUNET_TIME_absolute_get_remaining
750 (pending->timeout), &peer->id,
751 ntohs (pending->msg->size),
752 &core_transmit_notify, peer);
753 GNUNET_break (NULL != peer->th);
758 * Construct a trail message and forward it to a friend.
759 * @param source_peer Peer which wants to set up the trail to one of its finger.
760 * @param destination_finger Value whose successor we are searching the network.
761 * @param current_destination Peer which gets this message.
762 * @param target_friend Current friend to which this message should be forwarded.
763 * @param trail_length Numbers of peers in the trail.
764 * @param trail_peer_list peers this request has traversed so far
765 * @param finger_map_index Index in finger peer map
766 * @param type Type of current destination can be either FRIEND or FINGER
769 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity *source_peer,
770 uint64_t destination_finger,
771 struct GNUNET_PeerIdentity *current_destination,
772 struct FriendInfo *target_friend,
773 unsigned int trail_length,
774 struct GNUNET_PeerIdentity *trail_peer_list,
775 unsigned int finger_map_index,
776 enum current_destination_type type)
778 struct P2PPendingMessage *pending;
779 struct PeerTrailSetupMessage *tsm;
780 struct GNUNET_PeerIdentity *peer_list;
783 msize = sizeof (struct PeerTrailSetupMessage) +
784 (trail_length * sizeof (struct GNUNET_PeerIdentity));
786 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
792 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
794 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
798 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
799 pending->importance = 0; /* FIXME */
800 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
801 tsm = (struct PeerTrailSetupMessage *) &pending[1];
802 pending->msg = &tsm->header;
803 tsm->header.size = htons (msize);
804 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
805 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
806 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
807 memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
808 tsm->current_destination_type = htonl (type);
809 tsm->trail_length = htonl (trail_length);
810 tsm->finger_map_index = htonl (finger_map_index);
812 if (trail_peer_list != NULL)
814 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
815 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
818 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
819 target_friend->pending_count++;
820 process_friend_queue (target_friend);
826 * Construct a trail setup result message and forward it to a friend.
827 * @param destination_peer Peer which will get the trail to one of its finger.
828 * @param source_finger Peer to which the trail has been setup to.
829 * @param target_friend Friend to which this message should be forwarded.
830 * @param trail_length Numbers of peers in the trail.
831 * @param trail_peer_list Peers which are part of the trail from source to destination.
832 * @param current_trail_index Index at which sender of this message is located.
833 * @param finger_map_index Index in finger peer map
836 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity *destination_peer,
837 struct GNUNET_PeerIdentity *source_finger,
838 struct FriendInfo *target_friend,
839 unsigned int trail_length,
840 struct GNUNET_PeerIdentity *trail_peer_list,
841 unsigned int current_trail_index,
842 unsigned int finger_map_index)
844 struct P2PPendingMessage *pending;
845 struct PeerTrailSetupResultMessage *tsrm;
846 struct GNUNET_PeerIdentity *peer_list;
849 msize = sizeof (struct PeerTrailSetupResultMessage) +
850 (trail_length * sizeof (struct GNUNET_PeerIdentity));
852 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
858 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
860 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
864 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
865 pending->importance = 0;
866 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
867 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
868 pending->msg = &tsrm->header;
869 tsrm->header.size = htons (msize);
870 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
871 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
872 memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity));
873 tsrm->trail_length = htonl (trail_length);
874 tsrm->current_index = htonl (current_trail_index);
875 tsrm->finger_map_index = htonl (finger_map_index);
876 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
877 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
879 /* Send the message to chosen friend. */
880 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
881 target_friend->pending_count++;
882 process_friend_queue (target_friend);
887 * Construct a PeerVerifySuccessor message and send it to friend.
888 * @param source_peer Peer which wants to verify its successor
889 * @param successor Peer which is our current successor
890 * @param target_friend Friend to which this message should be forwarded.
891 * @param trail_peer_list Peer which are part of trail from source to destination
892 * @param trail_length Number of peers in the trail list.
893 * @param current_trail_index Index in the trial list at which receiving peer should
894 * read the next element.
896 void GDS_NEIGHBOURS_send_verify_successor(struct GNUNET_PeerIdentity *source_peer,
897 struct GNUNET_PeerIdentity *successor,
898 struct FriendInfo *target_friend,
899 struct GNUNET_PeerIdentity *trail_peer_list,
900 unsigned int trail_length,
901 unsigned int current_trail_index)
903 struct PeerVerifySuccessorMessage *vsm;
904 struct P2PPendingMessage *pending;
905 struct GNUNET_PeerIdentity *peer_list;
908 msize = sizeof (struct PeerVerifySuccessorMessage) +
909 (trail_length * sizeof (struct GNUNET_PeerIdentity));
911 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
917 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
919 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
923 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
924 pending->importance = 0; /* FIXME */
925 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
926 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
927 pending->msg = &vsm->header;
928 vsm->header.size = htons (msize);
929 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
930 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
931 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
932 vsm->trail_length = htonl (trail_length);
933 vsm->current_trail_index = htonl (current_trail_index);
934 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
935 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
937 /* Send the message to chosen friend. */
938 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
939 target_friend->pending_count++;
940 process_friend_queue (target_friend);
946 * Construct a PeerVerifySuccessorResult message and send it to friend.
947 * @param destination_peer Peer which sent verify successor message
948 * @param source_successor Peer to which verify successor message was sent.
949 * @param my_predecessor source_successor's predecessor.
950 * @param target_friend Friend to which this message should be forwarded.
951 * @param trail_peer_list Peers which are part of trail from source to destination
952 * @param trail_length Number of peers in the trail list.
953 * @param current_trail_index Index in the trial list at which receiving peer should
954 * get the next element.
956 void GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity *destination_peer,
957 struct GNUNET_PeerIdentity *source_successor,
958 struct GNUNET_PeerIdentity *my_predecessor,
959 struct FriendInfo *target_friend,
960 struct GNUNET_PeerIdentity *trail_peer_list,
961 unsigned int trail_length,
962 unsigned int current_trail_index)
964 struct PeerVerifySuccessorResultMessage *vsmr;
965 struct P2PPendingMessage *pending;
966 struct GNUNET_PeerIdentity *peer_list;
969 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
970 (trail_length * sizeof(struct GNUNET_PeerIdentity));
972 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
979 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
981 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
985 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
986 pending->importance = 0; /* FIXME */
987 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
988 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
989 pending->msg = &vsmr->header;
990 vsmr->header.size = htons (msize);
991 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
992 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
993 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
994 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
995 vsmr->trail_length = htonl (trail_length);
996 vsmr->current_index = htonl (current_trail_index);
998 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
999 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1001 /* Send the message to chosen friend. */
1002 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1003 target_friend->pending_count++;
1004 process_friend_queue (target_friend);
1009 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1010 * @param source_peer Peer which is sending notify message to its new successor.
1011 * @param destination_peer Peer which is the new destination.
1012 * @param target_friend Next friend to pass this message to.
1013 * @param peer_list List of peers in the trail to reach to destination_peer.
1014 * @param current_trail_index Index of peer_list for next target friend position.
1015 * @param trail_length Total number of peers in peer list
1018 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity *source_peer,
1019 struct GNUNET_PeerIdentity *destination_peer,
1020 struct FriendInfo *target_friend,
1021 struct GNUNET_PeerIdentity *trail_peer_list,
1022 unsigned int trail_length,
1023 unsigned int current_trail_index)
1025 struct PeerNotifyNewSuccessorMessage *nsm;
1026 struct P2PPendingMessage *pending;
1027 struct GNUNET_PeerIdentity *peer_list;
1030 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1031 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1033 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1039 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1041 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1045 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1046 pending->importance = 0; /* FIXME */
1047 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1048 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1049 pending->msg = &nsm->header;
1050 nsm->header.size = htons (msize);
1051 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1052 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1053 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1054 nsm->trail_length = htonl (trail_length);
1055 nsm->current_index = htonl (current_trail_index);
1057 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1058 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1060 /* Send the message to chosen friend. */
1061 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1062 target_friend->pending_count++;
1063 process_friend_queue (target_friend);
1068 * FIXME: Optimizaiton Once the basic code is running. Add the optimization
1069 * where you check if the threshold on number of links that should go through
1070 * a particular friend has crossed. If yes then again choose a different
1071 * friend. Important that the new friend chosen should be different. How to
1072 * ensure this? This is an important optimization as without this one x-vine
1073 * is actually not a sybil tolerant DHT.
1074 * Randomly choose one of your friends from the friends_peer map
1077 static struct FriendInfo *
1078 select_random_friend()
1080 unsigned int current_size;
1081 unsigned int *index;
1083 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1084 struct GNUNET_PeerIdentity key_ret;
1085 struct FriendInfo *friend;
1087 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1088 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1089 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1093 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1101 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1109 * Compute finger_identity to which we want to setup the trail
1110 * @return finger_identity
1113 compute_finger_identity()
1116 uint64_t *finger_identity64;
1118 finger_identity64 = GNUNET_malloc (sizeof (uint64_t));
1119 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1120 /*FIXME: Do we need a mod finger = ((my_id + pow(2, finger_index)) mod (pow (2, MAX_FINGERS))*/
1121 *finger_identity64 = (my_id64 + (unsigned long) pow (2,current_finger_index));
1123 return finger_identity64;
1128 * Compute immediate predecessor identity in the network.
1129 * @return peer identity of immediate predecessor.
1132 compute_predecessor_identity()
1135 uint64_t *predecessor;
1137 predecessor = GNUNET_malloc (sizeof (uint64_t));
1138 memcpy (&my_id, &my_identity, sizeof (uint64_t));
1139 /* FIXME: Do we need to use mod pow(2, MAX_FINGERS) here? */
1140 *predecessor = (my_id -1);
1147 * Periodically ping your successor to ask its current predecessor
1149 * @param cls closure for this task
1150 * @param tc the context under which the task is running
1153 send_verify_successor_message (void *cls,
1154 const struct GNUNET_SCHEDULER_TaskContext *tc )
1156 struct GNUNET_TIME_Relative next_send_time;
1157 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1158 struct GNUNET_PeerIdentity key_ret;
1159 struct FriendInfo *target_friend;
1160 struct GNUNET_PeerIdentity *next_hop;
1161 struct GNUNET_PeerIdentity *peer_list;
1162 unsigned int finger_trail_current_index;
1163 struct FingerInfo *finger;
1164 unsigned int finger_index;
1168 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1169 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1171 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1172 (const void **)&finger))
1174 if (0 == finger->finger_map_index)
1181 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1184 goto send_new_request;
1186 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->trail_length);
1188 struct TrailPeerList *iterate;
1189 iterate = finger->head;
1191 while ( i < (finger->trail_length))
1193 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1194 iterate = iterate->next;
1198 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1199 memcpy (next_hop, &peer_list[0], sizeof (struct GNUNET_PeerIdentity));
1200 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1201 finger_trail_current_index = 0;
1204 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1205 &(finger->finger_identity),
1208 finger->trail_length,
1209 finger_trail_current_index);
1212 /* FIXME: Use a random value so that this message is send not at the same
1213 interval as send_find_finger_trail_message. */
1215 next_send_time.rel_value_us =
1216 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1217 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1218 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1219 (current_finger_index + 50));
1222 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
1228 * Task to send a find finger trail message. We attempt to find trail
1229 * to our fingers, successor and predecessor in the network.
1231 * @param cls closure for this task
1232 * @param tc the context under which the task is running
1235 send_find_finger_trail_message (void *cls,
1236 const struct GNUNET_SCHEDULER_TaskContext *tc)
1238 struct FriendInfo *target_friend;
1239 struct GNUNET_TIME_Relative next_send_time;
1240 uint64_t *finger_identity;
1241 unsigned int finger_map_index;
1243 if (1 == current_finger_index)
1245 finger_identity = compute_predecessor_identity();
1250 finger_identity = compute_finger_identity();
1254 /* FIXME: Here should we choose randomly or not. */
1255 target_friend = select_random_friend();
1257 finger_map_index = current_finger_index;
1258 current_finger_index = ( current_finger_index + 1) % MAX_FINGERS;
1260 if(NULL != target_friend)
1262 GDS_NEIGHBOURS_send_trail_setup (&my_identity, *finger_identity, &(target_friend->id),
1263 target_friend, 0, NULL,
1264 finger_map_index, FRIEND);
1267 /* FIXME: How to decide the correct interval? */
1268 next_send_time.rel_value_us =
1269 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1270 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1271 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1272 (current_finger_index + 10));
1274 find_finger_trail_task =
1275 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1281 * Method called whenever a peer connects.
1283 * @param cls closure
1284 * @param peer_identity peer identity this notification is about
1287 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
1289 struct FriendInfo *friend;
1291 /* Check for connect to self message */
1292 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
1295 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
1297 /* If peer already exists in our friend_peermap, then exit. */
1298 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
1304 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
1307 friend = GNUNET_new (struct FriendInfo);
1308 friend->id = *peer_identity;
1310 GNUNET_assert (GNUNET_OK ==
1311 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
1312 peer_identity, friend,
1313 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1315 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
1316 if (1 == GNUNET_CONTAINER_multipeermap_size (friend_peermap))
1317 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
1322 * Method called whenever a peer disconnects.
1324 * @param cls closure
1325 * @param peer peer identity this notification is about
1328 handle_core_disconnect (void *cls,
1329 const struct GNUNET_PeerIdentity *peer)
1331 struct FriendInfo *remove_friend;
1332 struct FingerInfo *remove_finger;
1333 struct GNUNET_PeerIdentity key_ret;
1334 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1335 struct TrailPeerList *iterator;
1336 struct GNUNET_PeerIdentity *finger_identity;
1339 /* Check for self message. */
1340 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1343 /* Search for peer to remove in your friend_peermap. */
1345 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
1347 if (NULL == remove_friend)
1353 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
1354 finger_identity = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1355 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1356 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1358 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1359 (const void **)&remove_finger))
1361 iterator = remove_finger->head->next;
1362 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(iterator->peer), &(remove_friend->id)))
1364 memcpy (finger_identity, &(remove_finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
1365 GNUNET_assert (GNUNET_YES ==
1366 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
1373 /* Remove the friend from friend_peermap. */
1374 GNUNET_assert (GNUNET_YES ==
1375 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
1382 * To be called on core init/fail.
1384 * @param cls service closure
1385 * @param identity the public identity of this peer
1388 core_init (void *cls,
1389 const struct GNUNET_PeerIdentity *identity)
1391 my_identity = *identity;
1394 /* SUPU TEST CODE */
1395 struct GNUNET_PeerIdentity *print_peer;
1396 print_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1397 memcpy (print_peer, &my_identity, sizeof (struct GNUNET_PeerIdentity));
1398 FPRINTF (stderr,_("\nSUPU %s, %s, %d,my_identity = %s"),
1399 __FILE__, __func__,__LINE__, GNUNET_i2s (print_peer));
1400 /* SUPU TEST CODE ENDS */
1407 * @param destination_peer
1408 * @param existing_trail
1409 * @param trail_length
1412 static struct GNUNET_PeerIdentity *
1413 invert_trail_list (struct GNUNET_PeerIdentity *destination_peer,
1414 struct GNUNET_PeerIdentity *existing_trail,
1415 unsigned int trail_length)
1419 struct GNUNET_PeerIdentity *new_trail;
1422 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
1424 if (trail_length > 1)
1426 i = trail_length - 2;
1429 memcpy( &new_trail[j], &existing_trail[i], sizeof (struct GNUNET_PeerIdentity));
1434 memcpy (&new_trail[j], destination_peer, sizeof(struct GNUNET_PeerIdentity));
1442 * @param existing_finger
1448 compare_finger_identity (struct GNUNET_PeerIdentity *existing_finger,
1449 struct GNUNET_PeerIdentity *new_finger)
1452 ret = (existing_finger > new_finger) ? 1 :
1453 (existing_finger == new_finger) ? 0 : -1;
1459 * FIXME: Not sure of the logic to find the correct predecessor.
1460 * Given two finger identities, find the closest predecessor.
1461 * @param existing_predecessor
1462 * @param new_predecessor
1467 compare_predecessor(struct GNUNET_PeerIdentity *existing_predecessor,
1468 struct GNUNET_PeerIdentity *new_predecessor)
1471 ret = (existing_predecessor < new_predecessor) ? 1 :
1472 (existing_predecessor == new_predecessor) ? 0 : -1;
1478 * Add an entry in finger table.
1479 * Add an entry into finger table
1480 * @param finger_identity Peer identity of finger
1481 * @param finger_trail Trail to reach the finger
1482 * @param trail_length Number of peers in the trail.
1483 * @param finger_map_index Index in finger peer map.
1486 void finger_table_add (struct GNUNET_PeerIdentity *finger_identity,
1487 struct GNUNET_PeerIdentity *finger_trail,
1488 unsigned int trail_length,
1489 unsigned int finger_map_index)
1491 struct FingerInfo *new_finger_entry;
1494 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1495 struct GNUNET_PeerIdentity key_ret;
1496 struct FingerInfo *existing_finger;
1501 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1503 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1505 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1506 (const void **)&existing_finger))
1508 /* If we already have an entry at the finger map index. */
1509 if ((finger_map_index == existing_finger->finger_map_index))
1511 /* Check if the finger entry are same. */
1512 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),finger_identity))
1514 FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
1519 /* FIXME: here you should have something better to check which finger
1522 if (finger_map_index == 1)
1524 FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
1525 ret = compare_predecessor (&(existing_finger->finger_identity),
1530 FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
1531 ret = compare_finger_identity (&(existing_finger->finger_identity),
1536 FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
1537 GNUNET_assert (GNUNET_YES ==
1538 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
1539 &(existing_finger->finger_identity),
1545 FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
1555 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
1556 memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
1559 while (i < trail_length)
1561 struct TrailPeerList *element;
1562 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1563 element->next = NULL;
1564 element->prev = NULL;
1566 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
1567 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head, new_finger_entry->tail, element);
1571 new_finger_entry->finger_map_index = finger_map_index;
1572 new_finger_entry->trail_length = trail_length;
1574 /* FIXME: Here we are keeping multiple hashmap option so that there are
1575 multiple routes to reach to same finger, redundant routing.
1576 * Also same peers could be our fingers for different finger map index */
1577 GNUNET_assert (GNUNET_OK ==
1578 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
1579 &(new_finger_entry->finger_identity),
1581 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE)); /* Fixme: change to multiple */
1584 if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap)
1585 && (new_finger_entry->finger_map_index!= 1))
1587 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1593 * Compare two peer identities.
1594 * @param p1 Peer identity
1595 * @param p2 Peer identity
1596 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
1599 compare_peer_id (const void *p1, const void *p2)
1601 struct Sorting_List *p11;
1602 struct Sorting_List *p22;
1604 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
1605 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
1606 p11 = (struct Sorting_List *)p1;
1607 p22 = (struct Sorting_List *)p2;
1608 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
1609 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
1615 * Return the successor of value in all_known_peers.
1616 * @param all_known_peers list of all the peers
1617 * @param value value we have to search in the all_known_peers.
1620 static struct Sorting_List *
1621 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
1630 middle = (first + last)/2;
1632 while(first <= last)
1634 if(all_known_peers[middle].peer_id < value)
1638 else if(all_known_peers[middle].peer_id == value)
1640 if(middle == (size -1))
1642 return &all_known_peers[0];
1646 return &all_known_peers[middle+1];
1654 middle = (first + last)/2;
1661 * Find closest successor for the value.
1662 * @param value Value for which we are looking for successor
1663 * @param current_destination NULL if my_identity is successor else finger/friend
1665 * @param type Next destination type
1666 * @return Peer identity of next destination i.e. successor of value.
1668 static struct GNUNET_PeerIdentity *
1669 find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination,
1670 enum current_destination_type *type)
1672 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1673 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1674 struct GNUNET_PeerIdentity key_ret;
1675 struct FriendInfo *friend;
1676 struct FingerInfo *finger;
1677 unsigned int finger_index;
1678 unsigned int friend_index;
1679 struct Sorting_List *successor;
1683 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
1684 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
1685 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
1688 struct Sorting_List all_known_peers[size];
1691 for (k = 0; k < size; k++)
1692 all_known_peers[k].peer_id = 0;
1694 /* Copy your identity at 0th index in all_known_peers. */
1696 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
1697 all_known_peers[j].type = MY_ID;
1698 all_known_peers[j].data = 0;
1702 all_known_peers[j].peer_id = value;
1703 all_known_peers[j].type = VALUE;
1704 all_known_peers[j].data = 0;
1707 /* Iterate over friend peer map and copy all the elements into array. */
1708 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1709 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
1711 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1713 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
1714 all_known_peers[j].type = FRIEND;
1715 all_known_peers[j].data = friend;
1720 /* Iterate over finger map and copy all the entries into all_known_peers array. */
1721 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1722 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1724 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1726 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
1727 all_known_peers[j].type = FINGER;
1728 all_known_peers[j].data = finger;
1733 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1734 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
1736 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
1738 /* search value in all_known_peers array. */
1739 successor = find_closest_successor (all_known_peers, value, size);
1741 if (successor->type == MY_ID)
1746 else if (successor->type == FRIEND)
1749 struct FriendInfo *target_friend;
1750 target_friend = (struct FriendInfo *)successor->data;
1751 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
1752 return current_destination;
1754 else if (successor->type == FINGER)
1757 struct GNUNET_PeerIdentity *next_hop;
1758 struct FingerInfo *finger;
1759 struct TrailPeerList *iterator;
1760 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
1761 finger = successor->data;
1762 iterator = finger->head;
1763 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1764 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
1765 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
1778 * 1. Do we have an expiration time for get request? Yes but I don't know its
1779 * use case and how to handle it
1780 * Send a get message to selected target friend. If target friend in NULL,
1781 * then search for a target friend.
1782 * @param request_id Unique ID identifying this request
1783 * @param source_peer Peer which started get request
1784 * @param get_peer_path Peer list to reach to final destination which contains the data.
1785 * @param get_path_length Total numbers of peer in get_path
1786 * @param key Key key for the content
1787 * @param target_peer Next peer to forward the message to.
1788 * @param current_destination Peer which will get this message.
1789 * @param current_dest_type Type of current destination can be either FRIEND or FINGER
1792 GDS_NEIGHBOURS_handle_get (struct GNUNET_PeerIdentity *source_peer,
1793 struct GNUNET_PeerIdentity *get_peer_path,
1794 unsigned int get_path_length,
1795 struct GNUNET_HashCode *key,
1796 struct GNUNET_PeerIdentity *target_peer,
1797 struct GNUNET_PeerIdentity *current_destination,
1798 enum current_destination_type *current_dest_type)
1800 struct PeerGetMessage *get_request;
1801 struct P2PPendingMessage *pending;
1802 struct GNUNET_PeerIdentity *get_path;
1803 struct FriendInfo *target_friend;
1807 msize = sizeof (struct PeerGetMessage) +
1808 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
1810 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1816 memcpy (&key_value, key, sizeof (uint64_t));
1818 /* FIXME: Is this correct comparison? */
1819 if (NULL == target_peer)
1821 /* This is the first call made from client file. */
1822 struct GNUNET_PeerIdentity *next_hop;
1823 next_hop = find_successor (key_value, current_destination, current_dest_type);
1825 if (*current_dest_type == MY_ID)
1827 struct GNUNET_PeerIdentity *destination_peer;
1828 get_path = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1829 memcpy (get_path, &my_identity, sizeof (struct GNUNET_PeerIdentity));
1830 get_path_length = 1;
1831 destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1832 memcpy (destination_peer, source_peer, sizeof (struct GNUNET_PeerIdentity));
1833 /* FIXME: We enter in this part of code only when this is our first
1834 call from client file. In client file we already have done datacache_get
1835 and if we already have the result. So, ideally code should never reach
1836 here. Remove it after verifying. */
1837 /* FIXME: Call datacache_get but remove after verified above thing. */
1838 GDS_NEIGHBOURS_send_get_result (&my_identity,get_path, get_path_length,
1839 key,destination_peer, 0,
1846 /* Find the friend corresponding to next_hop */
1847 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1851 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer);
1853 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1854 pending->importance = 0; /* FIXME */
1855 /* FIXME: Do we have an expiration time for get request */
1856 get_request = (struct PeerGetMessage *) &pending[1];
1857 pending->msg = &get_request->header;
1858 get_request->header.size = htons (msize);
1859 get_request->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
1860 get_request->get_path_length = htonl (get_path_length);
1861 get_request->key = *key;
1863 memcpy (&(get_request->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1864 memcpy (&(get_request->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
1865 get_request->current_dest_type = htonl (*current_dest_type);
1866 get_path = (struct GNUNET_PeerIdentity *) &get_request[1];
1867 memcpy (get_path, get_peer_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
1868 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1869 target_friend->pending_count++;
1870 process_friend_queue (target_friend);
1876 * FIXME: In this function, you just find the target friend and send the message
1877 * to next peer. In handle_dht_p2p_put, you should check the options and type
1878 * and check if you are final destination or not. if not then find the next
1879 * destination and send the message forward.
1880 * @param type type of the block
1881 * @param options routing options
1882 * @param desired_replication_level desired replication count
1883 * @param expiration_time when does the content expire
1884 * @param hop_count how many hops has this message traversed so far
1885 * @param key key for the content
1886 * @param put_path_length number of entries in @a put_path
1887 * @param put_path peers this request has traversed so far (if tracked)
1888 * @param data payload to store
1889 * @param data_size number of bytes in @a data
1890 * @param current_destination
1892 * @param target_peer_id
1895 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
1896 enum GNUNET_DHT_RouteOption options,
1897 uint32_t desired_replication_level,
1898 struct GNUNET_TIME_Absolute expiration_time,
1900 const struct GNUNET_HashCode *key,
1901 unsigned int put_path_length,
1902 struct GNUNET_PeerIdentity *put_path,
1903 const void *data, size_t data_size,
1904 struct GNUNET_PeerIdentity *current_destination,
1905 enum current_destination_type dest_type,
1906 struct GNUNET_PeerIdentity *target_peer)
1908 struct PeerPutMessage *ppm;
1909 struct P2PPendingMessage *pending;
1910 struct FriendInfo *target_friend;
1911 struct GNUNET_PeerIdentity *pp;
1915 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
1916 sizeof (struct PeerPutMessage);
1918 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1920 put_path_length = 0;
1921 msize = data_size + sizeof (struct PeerPutMessage);
1924 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1930 memcpy (&key_value, key, sizeof (uint64_t));
1931 struct GNUNET_PeerIdentity *current_dest;
1932 current_dest = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1933 if (target_peer == NULL)
1935 /* This is the first time the call has been made from handle_dht_local_put.
1936 So, you need to search for the next peer to send this message to. */
1937 struct GNUNET_PeerIdentity *next_hop;
1939 next_hop = find_successor (key_value, current_dest, &dest_type);
1942 if (dest_type == MY_ID)
1944 /* FIXME: How do we handle different block types? */
1945 /* FIXME: Here depending on the replication level choose 'r' successors
1946 to this peer and send put to all of these peers. */
1948 GDS_DATACACHE_handle_put (expiration_time, key, put_path_length, put_path,
1949 type, data_size, data);
1954 /* Find the friend corresponding to next_hop */
1955 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1959 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer);
1961 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1962 pending->importance = 0; /* FIXME */
1963 pending->timeout = expiration_time;
1964 ppm = (struct PeerPutMessage *) &pending[1];
1965 pending->msg = &ppm->header;
1966 ppm->header.size = htons (msize);
1967 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
1968 ppm->options = htonl (options);
1969 ppm->type = htonl (type);
1970 ppm->hop_count = htonl (hop_count + 1);
1971 ppm->desired_replication_level = htonl (desired_replication_level);
1972 ppm->put_path_length = htonl (put_path_length);
1973 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1974 if (current_destination != NULL)
1975 memcpy (&(ppm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
1977 memcpy (&(ppm->current_destination), current_dest, sizeof (struct GNUNET_PeerIdentity));
1978 ppm->current_destination_type = htonl (dest_type);
1981 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
1982 memcpy (pp, put_path,
1983 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
1984 memcpy (&pp[put_path_length], data, data_size);
1985 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1986 target_friend->pending_count++;
1987 process_friend_queue (target_friend);
1992 * Send get result back to requesting client.
1993 * @param source_peer
1995 * @param target_friend
1996 * @param get_path_length
1998 * @param destination_peer
1999 * @param current_path_index
2004 GDS_NEIGHBOURS_send_get_result (struct GNUNET_PeerIdentity *source_peer,
2005 struct GNUNET_PeerIdentity *get_path,
2006 unsigned int get_path_length,
2007 struct GNUNET_HashCode *key,
2008 struct GNUNET_PeerIdentity *destination_peer,
2009 unsigned int current_path_index,
2010 const void *data, size_t data_size,
2011 struct GNUNET_PeerIdentity *next_hop)
2013 /* Add get_result into pending message and send the data to target friend.
2014 make a call GDS_CLIENTS_process_get_result() with all the fields. */
2015 struct PeerGetResultMessage *get_result;
2016 struct GNUNET_PeerIdentity *get_result_path;
2017 struct P2PPendingMessage *pending;
2018 struct FriendInfo *target_friend;
2021 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2022 sizeof (struct PeerPutMessage);
2024 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2030 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2031 pending->importance = 0; /* FIXME */
2032 /* FIXME: Should we add an expiration time like in put message. */
2033 get_result = (struct PeerGetResultMessage *)&pending[1];
2034 pending->msg = &get_result->header;
2035 get_result->header.size = htons (msize);
2036 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2037 memcpy (&(get_result->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2038 memcpy (&(get_result->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
2039 get_result->current_path_index = current_path_index;
2040 get_result->key = *key;
2042 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2043 memcpy (get_result_path, get_path,
2044 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2045 memcpy (&get_result_path[get_path_length], data, data_size);
2047 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2048 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2049 target_friend->pending_count++;
2050 process_friend_queue (target_friend);
2062 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
2063 const struct GNUNET_MessageHeader *message)
2065 /* If you are the source, go back to the client file and there search for
2066 the requesting client and send back the result. */
2067 struct PeerGetResultMessage *get_result;
2068 struct GNUNET_PeerIdentity *get_path;
2070 size_t payload_size;
2072 unsigned int getlen;
2073 int current_path_index;
2075 msize = ntohs (message->size);
2076 if (msize < sizeof (struct PeerGetResultMessage))
2078 GNUNET_break_op (0);
2082 get_result = (struct PeerGetResultMessage *)message;
2083 getlen = ntohl (get_result->get_path_length);
2086 sizeof (struct PeerGetResultMessage) +
2087 getlen * sizeof (struct GNUNET_PeerIdentity)) ||
2089 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2091 GNUNET_break_op (0);
2095 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
2096 payload = &get_path[getlen];
2097 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
2098 getlen * sizeof (struct GNUNET_PeerIdentity));
2099 current_path_index = ntohl (get_result->current_path_index);
2101 /* Here you just have to check if you are the destination or not if not
2102 then read the next peer and send the message. */
2103 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_result->destination_peer))))
2105 /* I am the destination. Call the function in client file.
2106 * FIXME: Here I don't know how I communicate the result back to client
2108 //GDS_CLIENTS_process_get_result();
2113 /* Read the element from the get path at trail index. set the trail index
2114 and call gds_neighbours_send_get_result.*/
2115 struct GNUNET_PeerIdentity *next_hop;
2117 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2118 memcpy (next_hop, &get_path[current_path_index], sizeof (struct GNUNET_PeerIdentity));
2121 if (current_path_index != 0)
2122 current_path_index--;
2124 GDS_NEIGHBOURS_send_get_result (&my_identity, get_path,
2125 getlen,&(get_result->key),&(get_result->destination_peer),
2127 payload, payload_size, next_hop);
2130 return GNUNET_SYSERR;
2136 * Core handler for p2p put requests.
2138 * @param cls closure
2139 * @param peer sender of the request
2140 * @param message message
2141 * @param peer peer identity this notification is about
2142 * @return #GNUNET_OK to keep the connection open,
2143 * #GNUNET_SYSERR to close it (signal serious error)
2146 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2147 const struct GNUNET_MessageHeader *message)
2149 struct PeerPutMessage *put;
2150 struct GNUNET_PeerIdentity *put_path;
2151 enum GNUNET_DHT_RouteOption options;
2152 enum current_destination_type current_dst_type;
2153 struct GNUNET_PeerIdentity *current_destination;
2154 struct GNUNET_PeerIdentity *source_peer;
2155 struct GNUNET_PeerIdentity *next_hop;
2156 struct GNUNET_HashCode test_key;
2159 size_t payload_size;
2163 put = (struct PeerPutMessage *) message;
2164 putlen = ntohl (put->put_path_length);
2165 msize = ntohs (message->size);
2168 sizeof (struct PeerPutMessage) +
2169 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2171 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2173 GNUNET_break_op (0);
2177 put_path = (struct GNUNET_PeerIdentity *) &put[1];
2178 payload = &put_path[putlen];
2179 options = ntohl (put->options);
2180 payload_size = msize - (sizeof (struct PeerPutMessage) +
2181 putlen * sizeof (struct GNUNET_PeerIdentity));
2183 /* FIXME: I don't understand what exactly are we doing here. */
2184 switch (GNUNET_BLOCK_get_key
2185 (GDS_block_context, ntohl (put->type), payload, payload_size,
2189 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
2191 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
2192 GNUNET_break_op (0);
2193 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2194 "PUT with key `%s' for block with key %s\n",
2195 put_s, GNUNET_h2s_full (&test_key));
2196 GNUNET_free (put_s);
2201 GNUNET_break_op (0);
2204 /* cannot verify, good luck */
2208 /* FIXME: This part is also not clear to me.*/
2209 if (ntohl (put->type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
2211 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
2214 NULL, 0, /* bloom filer */
2215 NULL, 0, /* xquery */
2216 payload, payload_size))
2218 case GNUNET_BLOCK_EVALUATION_OK_MORE:
2219 case GNUNET_BLOCK_EVALUATION_OK_LAST:
2222 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
2223 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
2224 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
2225 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
2226 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
2227 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
2229 GNUNET_break_op (0);
2234 struct GNUNET_PeerIdentity pp[putlen + 1];
2236 /* extend 'put path' by sender */
2237 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
2239 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
2246 /* Copy the fields of message, call find successor or gds_routing_search,
2247 depending on the destination_type and if you are the final destination,
2248 do a datache put or if option is. else call gds_neighbours_handle_get with
2249 correct parameters. */
2250 current_destination = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2251 memcpy (current_destination, &(put->current_destination), sizeof (struct GNUNET_PeerIdentity));
2252 current_dst_type = ntohl (put->current_destination_type);
2253 memcpy (&key_value, &(put->key), sizeof (uint64_t));
2254 source_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2255 memcpy (source_peer, &(put->source_peer), sizeof (struct GNUNET_PeerIdentity));
2257 if (current_dst_type == FRIEND)
2259 next_hop = find_successor (key_value, current_destination, ¤t_dst_type);
2261 else if (current_dst_type == FINGER)
2263 next_hop = GDS_ROUTING_search (source_peer, current_destination, peer);
2266 if (current_dst_type == MY_ID)
2268 /* Here datacache_put*/
2269 /* FIXME: Here depending on replication, call replicate_put() to do the
2270 put operation on 'r' successors. */
2271 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
2272 &(put->key),putlen, pp, ntohl (put->type), payload_size,
2278 /* here call gds_neighbours*/
2279 GDS_NEIGHBOURS_handle_put (ntohl (put->type),ntohl (put->options),
2280 ntohl (put->desired_replication_level),
2281 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2282 ntohl (put->hop_count),&put->key, putlen,
2283 pp, payload, payload_size,
2284 current_destination, current_dst_type, next_hop);
2287 return GNUNET_SYSERR;
2292 * FIXME: Handle expiration, options, block type, replication
2293 * referring the old code.
2294 * Core handler for p2p get requests.
2296 * @param cls closure
2297 * @param peer sender of the request
2298 * @param message message
2299 * @return #GNUNET_OK to keep the connection open,
2300 * #GNUNET_SYSERR to close it (signal serious error)
2303 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
2304 const struct GNUNET_MessageHeader *message)
2306 struct PeerGetMessage *get;
2307 struct GNUNET_PeerIdentity *current_destination;
2309 enum current_destination_type cuurent_dest_type;
2310 struct GNUNET_PeerIdentity *next_hop;
2311 struct GNUNET_PeerIdentity *get_path;
2313 unsigned int get_length;
2315 msize = ntohs (message->size);
2316 if (msize < sizeof (struct PeerGetMessage))
2318 GNUNET_break_op (0);
2322 get = (struct PeerGetMessage *)message;
2323 get_length = ntohl (get->get_path_length);
2324 get_path = (struct GNUNET_PeerIdentity *)&get[1];
2327 sizeof (struct PeerGetMessage) +
2328 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
2330 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2332 GNUNET_break_op (0);
2336 get = (struct PeerGetMessage *) message;
2337 current_destination = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2338 memcpy (current_destination, &(get->current_destination), sizeof (struct GNUNET_PeerIdentity));
2339 memcpy (&key_value, &(get->key), sizeof (uint64_t));
2340 cuurent_dest_type = ntohl (get->current_dest_type);
2342 if (cuurent_dest_type == FRIEND)
2344 next_hop = find_successor (key_value, current_destination, &cuurent_dest_type);
2346 else if (cuurent_dest_type == FINGER)
2348 next_hop = GDS_ROUTING_search (&(get->source_peer), current_destination, peer);
2351 if (cuurent_dest_type == MY_ID)
2353 struct GNUNET_PeerIdentity *destination_peer;
2354 //struct GNUNET_PeerIdentity *next_hop;
2355 //int current_path_index;
2357 /* Add yourself to the get path, increment the get length. */
2358 destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2359 memcpy (destination_peer, &(get->source_peer), sizeof (struct GNUNET_PeerIdentity));
2360 //current_path_index = get_length - 1;
2362 /* I am the final destination. Call GDS_NEIGHBOURS_send_get_result.
2363 * FIXME: Last parameters are data and data size. First implement datacache get
2364 * and get the result and send the data. Also seach for the next friend to pass
2365 * this message to. */
2367 /* FIXME: Here we should call GDS_CLIENT_handle_reply. */
2368 GDS_NEIGHBOURS_send_get_result (get->request_id, &my_identity, get_path,
2369 get_length,&(get->key), destination_peer, current_path_index,
2376 /* FIXME: Add your self to the get path and increment the get length. */
2378 /* FIXME: Does it matter if the dest_type is friend or finger. */
2379 GDS_NEIGHBOURS_handle_get (&(get->source_peer), get_path,
2380 get_length, &(get->key),next_hop,
2381 current_destination,&cuurent_dest_type);
2385 return GNUNET_SYSERR;
2390 * Handle a PeerTrailSetupMessage.
2391 * @param cls closure
2392 * @param message message
2393 * @param peer peer identity this notification is about
2394 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2397 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
2398 const struct GNUNET_MessageHeader *message)
2400 struct PeerTrailSetupMessage *trail_setup;
2401 struct GNUNET_PeerIdentity *next_hop;
2402 struct FriendInfo *target_friend;
2403 struct GNUNET_PeerIdentity *current_destination;
2404 struct GNUNET_PeerIdentity *trail_peer_list;
2405 enum current_destination_type current_dest_type;
2406 struct GNUNET_PeerIdentity *next_peer;
2407 unsigned int trail_length;
2408 uint32_t current_trail_index;
2409 unsigned int finger_map_index;
2410 uint64_t destination_finger_value;
2413 msize = ntohs (message->size);
2414 if (msize < sizeof (struct PeerTrailSetupMessage))
2416 GNUNET_break_op (0);
2420 trail_setup = (struct PeerTrailSetupMessage *) message;
2421 trail_length = ntohl (trail_setup->trail_length);
2423 if ((msize < sizeof (struct PeerTrailSetupMessage) +
2424 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2426 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2428 GNUNET_break_op (0);
2432 current_dest_type = ntohl (trail_setup->current_destination_type);
2433 finger_map_index = ntohl (trail_setup->finger_map_index);
2434 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
2435 destination_finger_value = trail_setup->destination_finger;
2436 current_destination = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2437 memcpy (current_destination, &(trail_setup->current_destination), sizeof (struct GNUNET_PeerIdentity));
2439 /* Find the next hop to send the packet to. */
2440 if (current_dest_type == FRIEND)
2442 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
2445 next_hop = find_successor (destination_finger_value, current_destination, &(current_dest_type));
2448 return GNUNET_SYSERR;
2450 else if (current_dest_type == FINGER)
2452 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
2455 next_hop = GDS_ROUTING_search (&(trail_setup->source_peer),
2456 &(trail_setup->current_destination), peer);
2457 /* As an optimization, find the successor from the find successor and
2458 compare both the ids to find the closest peer. */
2462 next_hop = find_successor (destination_finger_value, current_destination, &(current_dest_type));
2466 /* Add yourself to the trail list and increment the trail length. */
2467 struct GNUNET_PeerIdentity *peer_list;
2468 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length + 1));
2469 if ( trail_length > 0)
2471 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2473 memcpy (&peer_list[trail_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
2476 if (current_dest_type == MY_ID ||
2477 (0 == GNUNET_CRYPTO_cmp_peer_identity(next_hop, &(trail_setup->source_peer))))
2479 struct GNUNET_PeerIdentity *source_peer;
2480 source_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2481 memcpy (source_peer, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity));
2483 current_trail_index = trail_length - 1;
2484 next_peer= GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2485 if (current_trail_index == 0)
2487 memcpy (next_peer, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity));
2491 memcpy (next_peer, &trail_peer_list[current_trail_index-1], sizeof (struct GNUNET_PeerIdentity));
2494 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
2495 GNUNET_free (next_peer);
2497 if (0 == trail_setup->finger_map_index)
2499 struct GNUNET_PeerIdentity *new_trail_list;
2500 new_trail_list = invert_trail_list (source_peer, peer_list, trail_length);
2501 finger_table_add (source_peer, new_trail_list, trail_length, 1);
2504 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_setup->source_peer),
2506 target_friend, trail_length,
2507 peer_list, current_trail_index,
2512 else if (next_hop == NULL)
2514 return GNUNET_SYSERR;
2518 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2519 if(current_dest_type == FINGER)
2521 /* FIXME: Here it can even return err if routing entries have crossed the
2522 threshold. In such a case, you should send back a trail setup fail message
2523 to node just before your. THen its the responsiblity of node before you
2524 to find an alternate path to reach to the current_desintation which doesnot
2527 if ( GNUNET_SYSERR == GDS_ROUTING_add (&(trail_setup->source_peer),
2528 &(trail_setup->current_destination),
2531 //trail_setup_rejection()--> add to a list of fail trails and start
2532 // a new search rejecting this peer.
2536 GDS_NEIGHBOURS_send_trail_setup (&(trail_setup->source_peer),
2537 trail_setup->destination_finger,
2538 current_destination, target_friend, trail_length,
2539 peer_list, finger_map_index, current_dest_type);
2543 return GNUNET_SYSERR;
2548 * Core handle for p2p trail construction result messages.
2549 * @param cls closure
2550 * @param message message
2551 * @param peer peer identity this notification is about
2552 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2555 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2556 const struct GNUNET_MessageHeader *message)
2558 struct PeerTrailSetupResultMessage *trail_result;
2559 struct GNUNET_PeerIdentity *trail_peer_list;
2560 struct GNUNET_PeerIdentity *next_hop;
2561 struct FriendInfo *target_friend;
2562 unsigned int current_trail_index;
2563 unsigned int finger_map_index;
2564 unsigned int trail_length;
2567 msize = ntohs (message->size);
2568 if (msize < sizeof (struct PeerTrailSetupResultMessage))
2570 GNUNET_break_op (0);
2574 trail_result = (struct PeerTrailSetupResultMessage *) message;
2575 trail_length = ntohl (trail_result->trail_length);
2578 sizeof (struct PeerTrailSetupResultMessage) +
2579 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2581 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2583 GNUNET_break_op (0);
2587 current_trail_index = ntohl (trail_result->current_index);
2588 finger_map_index = ntohl (trail_result->finger_map_index);
2590 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
2592 if ( 0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2596 /* I don't remember why I have written this code. */
2597 if (finger_map_index == 1)
2599 struct GNUNET_PeerIdentity *new_trail_list;
2600 new_trail_list = invert_trail_list (&(trail_result->finger_identity),
2601 trail_peer_list, trail_length);
2602 finger_table_add (&(trail_result->finger_identity), new_trail_list, trail_length,
2609 finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length,
2617 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2619 current_trail_index = current_trail_index - 1;
2620 if (current_trail_index == 0)
2622 memcpy (next_hop, &(trail_result->destination_peer),sizeof (struct GNUNET_PeerIdentity));
2626 memcpy (next_hop, &(trail_peer_list[current_trail_index-1]),sizeof (struct GNUNET_PeerIdentity));
2629 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2630 GNUNET_free (next_hop);
2632 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
2633 &(trail_result->finger_identity),
2634 target_friend, trail_length,
2635 trail_peer_list,current_trail_index,
2640 return GNUNET_SYSERR;
2645 * FIXME: Use flag in the case finger peer map does not contain predcessor
2646 * then its NULL. Ideally it should never happen.
2647 * Get my current predecessor from the finger peer map
2648 * @return Current predecessor.
2650 static struct FingerInfo *
2653 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2654 struct GNUNET_PeerIdentity key_ret;
2655 unsigned int finger_index;
2656 struct FingerInfo *my_predecessor;
2658 /* Iterate over finger peer map and extract your predecessor. */
2659 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2660 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2662 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
2663 (finger_iter,&key_ret,(const void **)&my_predecessor))
2665 if(1 == my_predecessor->finger_map_index)
2671 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2672 return my_predecessor;
2677 * Core handle for p2p verify successor messages.
2678 * @param cls closure
2679 * @param message message
2680 * @param peer peer identity this notification is about
2681 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2684 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2685 const struct GNUNET_MessageHeader *message)
2687 struct PeerVerifySuccessorMessage *vsm;
2688 struct GNUNET_PeerIdentity *trail_peer_list;
2689 struct FriendInfo *target_friend;
2690 struct GNUNET_PeerIdentity *next_hop;
2691 struct GNUNET_PeerIdentity *source_peer;
2692 unsigned int trail_length;
2693 unsigned int current_trail_index;
2696 msize = ntohs (message->size);
2697 if (msize < sizeof (struct PeerVerifySuccessorMessage))
2699 GNUNET_break_op (0);
2703 vsm = (struct PeerVerifySuccessorMessage *) message;
2704 trail_length = ntohl (vsm->trail_length);
2706 if ((msize < sizeof (struct PeerVerifySuccessorMessage) +
2707 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2708 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2710 GNUNET_break_op (0);
2714 current_trail_index = ntohl (vsm->current_trail_index);
2715 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
2716 source_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2717 memcpy (source_peer, &(vsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
2719 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2721 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity)))
2723 struct FingerInfo *my_predecessor;
2724 current_trail_index = trail_length - 1;
2725 if (current_trail_index == 0)
2726 memcpy (next_hop, source_peer, sizeof (struct GNUNET_PeerIdentity));
2728 memcpy (next_hop, &trail_peer_list[current_trail_index-1], sizeof (struct GNUNET_PeerIdentity));
2730 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2731 GNUNET_free (next_hop);
2733 my_predecessor = get_predecessor();
2734 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (source_peer,
2735 &(my_predecessor->finger_identity))))
2737 GDS_NEIGHBOURS_send_verify_successor_result (source_peer,
2739 &(my_predecessor->finger_identity),
2743 current_trail_index);
2747 struct GNUNET_PeerIdentity *new_successor_trail;
2748 int new_trail_length;
2751 new_trail_length = trail_length + my_predecessor->trail_length;
2752 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * new_trail_length);
2753 memcpy (new_successor_trail, trail_peer_list, (trail_length) * sizeof (struct GNUNET_PeerIdentity));
2754 struct TrailPeerList *iterator;
2755 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
2756 iterator = my_predecessor->head;
2758 while (i < new_trail_length)
2760 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2761 iterator = iterator->next;
2765 GDS_NEIGHBOURS_send_verify_successor_result (source_peer,
2767 &(my_predecessor->finger_identity),
2769 new_successor_trail,
2771 current_trail_index);
2777 current_trail_index = current_trail_index + 1;
2778 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2779 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2780 GNUNET_free (next_hop);
2782 GDS_NEIGHBOURS_send_verify_successor (source_peer, &(vsm->successor),target_friend,
2783 trail_peer_list, trail_length, current_trail_index);
2790 * Core handle for p2p notify new successor messages.
2791 * @param cls closure
2792 * @param message message
2793 * @param peer peer identity this notification is about
2794 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2797 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2798 const struct GNUNET_MessageHeader *message)
2800 struct PeerNotifyNewSuccessorMessage *nsm;
2801 struct GNUNET_PeerIdentity *trail_peer_list;
2802 unsigned int current_trail_index;
2804 unsigned int trail_length;
2806 msize = ntohs (message->size);
2807 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
2809 GNUNET_break_op (0);
2813 nsm = (struct PeerNotifyNewSuccessorMessage *) message;
2814 trail_length = ntohl (nsm->trail_length);
2816 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
2817 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2819 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2821 GNUNET_break_op (0);
2825 current_trail_index = ntohl (nsm->current_index);
2826 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
2828 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer), &my_identity)))
2830 struct GNUNET_PeerIdentity *new_trail;
2831 new_trail = invert_trail_list (&(nsm->source_peer), trail_peer_list, trail_length);
2832 finger_table_add (&(nsm->source_peer), new_trail, trail_length, 1);
2837 struct FriendInfo *target_friend;
2838 struct GNUNET_PeerIdentity *next_hop;
2840 target_friend = GNUNET_malloc (sizeof (struct FriendInfo));
2841 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2843 current_trail_index = current_trail_index + 1;
2844 memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2845 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2846 GNUNET_free (next_hop);
2848 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
2849 &(nsm->destination_peer),
2850 target_friend, trail_peer_list,
2851 trail_length, current_trail_index);
2858 * Core handle for p2p verify successor result messages.
2859 * @param cls closure
2860 * @param message message
2861 * @param peer peer identity this notification is about
2862 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2865 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2866 const struct GNUNET_MessageHeader *message)
2868 struct PeerVerifySuccessorResultMessage *vsrm;
2869 struct FriendInfo *target_friend;
2870 struct GNUNET_PeerIdentity *trail_peer_list;
2871 struct GNUNET_PeerIdentity *next_hop;
2872 unsigned int trail_length;
2873 unsigned int current_trail_index;
2876 msize = ntohs (message->size);
2877 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
2879 GNUNET_break_op (0);
2883 vsrm = (struct PeerVerifySuccessorResultMessage *) message;
2884 trail_length = ntohl (vsrm->trail_length);
2887 sizeof (struct PeerVerifySuccessorResultMessage) +
2888 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2890 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2892 GNUNET_break_op (0);
2896 current_trail_index = ntohl (vsrm->current_index);
2897 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
2899 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), &(my_identity))))
2901 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), &(my_identity))))
2903 finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0);
2904 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2905 memcpy (next_hop, &trail_peer_list[0], sizeof (struct GNUNET_PeerIdentity));
2906 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2907 current_trail_index = 0;
2908 GNUNET_free (next_hop);
2910 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
2911 target_friend, trail_peer_list,
2912 trail_length, current_trail_index);
2917 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2918 current_trail_index = current_trail_index - 1;
2919 if (current_trail_index == 0)
2920 memcpy (next_hop, &(vsrm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
2922 memcpy (next_hop, &trail_peer_list[current_trail_index-1], sizeof (struct GNUNET_PeerIdentity));
2923 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2924 GNUNET_free (next_hop);
2926 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
2927 &(vsrm->source_successor),
2928 &(vsrm->my_predecessor),
2932 current_trail_index);
2939 * Initialize neighbours subsystem.
2940 * @return GNUNET_OK on success, GNUNET_SYSERR on error
2943 GDS_NEIGHBOURS_init()
2945 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
2946 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
2947 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
2948 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
2949 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
2950 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
2951 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
2952 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
2953 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
2958 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
2959 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
2960 GNUNET_NO, core_handlers);
2961 if (NULL == core_api)
2962 return GNUNET_SYSERR;
2964 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
2965 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS, GNUNET_NO);
2972 * Shutdown neighbours subsystem.
2975 GDS_NEIGHBOURS_done ()
2977 if (NULL == core_api)
2980 GNUNET_CORE_disconnect (core_api);
2983 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
2984 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
2985 friend_peermap = NULL;
2987 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
2988 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
2989 finger_peermap = NULL;
2991 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
2993 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
2994 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
2997 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
2999 GNUNET_SCHEDULER_cancel (verify_successor);
3000 verify_successor = GNUNET_SCHEDULER_NO_TASK;
3007 * Get the ID of the local node.
3009 * @return identity of the local node
3011 struct GNUNET_PeerIdentity *
3012 GDS_NEIGHBOURS_get_id ()
3014 return &my_identity;
3018 /* end of gnunet-service-xdht_neighbours.c */