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. The benefit of having this list is something
51 * I am not sure. only when the code is complete and working I will do this part.
52 2. Structure alignment.
53 3. In case of trail setup, you can see the comment on top of finger map index,
54 * trial length --> in NBO. Check how do we keep it in NBO, and make sure its
55 * same everywhere. When i send any message across the network i use htonl, so that
56 * converts it into network byte order.
57 4.THAT IN ROUTING TABLE SOURCE PEER IS INDEED THE SOURCE PEER.
58 should trail contain last element as finger or just the last element.? if
59 you can get some value then you should not keep at different places.
60 remove finger as last element in the trail.
61 5. I have removed the last element in the trail which was finger identity as we
62 * are already sending finger identity in the message. handle the case in case
63 * of notify new successor and verify the successor. */
66 * Maximum possible fingers of a peer.
68 #define MAX_FINGERS 65
71 * Maximum allowed number of pending messages per friend peer.
73 #define MAXIMUM_PENDING_PER_FRIEND 64
76 * How long to wait before sending another find finger trail request
78 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
81 * How long at most to wait for transmission of a request to another peer?
83 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
86 * Maximum number of trails allowed to go through a friend.
87 * FIXME: Random value at the moment, need to be adjusted to maintain a balance
88 * between performance and Sybil tolerance.
90 #define TRAIL_THROUGH_FRIEND_THRESHOLD 64.
93 GNUNET_NETWORK_STRUCT_BEGIN
101 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
103 struct GNUNET_MessageHeader header;
108 uint32_t options GNUNET_PACKED;
113 uint32_t block_type GNUNET_PACKED;
118 uint32_t hop_count GNUNET_PACKED;
121 * Replication level for this message
122 * In the current implementation, this value is not used.
124 uint32_t desired_replication_level GNUNET_PACKED;
127 * Length of the PUT path that follows (if tracked).
129 uint32_t put_path_length GNUNET_PACKED;
132 * Current destination to which this message is forwarded.
134 struct GNUNET_PeerIdentity current_destination;
137 * Peer whose finger is current_destination.
139 struct GNUNET_PeerIdentity current_source;
142 * When does the content expire?
144 struct GNUNET_TIME_AbsoluteNBO expiration_time;
147 * The key to store the value under.
149 struct GNUNET_HashCode key GNUNET_PACKED;
151 /* put path (if tracked) */
161 struct PeerGetResultMessage
164 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT
166 struct GNUNET_MessageHeader header;
169 * The type for the data.
171 uint32_t type GNUNET_PACKED;
174 * Peer which will receive the get result message.
176 struct GNUNET_PeerIdentity source_peer;
179 * Number of peers recorded in the outgoing path from source to the
180 * stored location of this message.
182 uint32_t put_path_length GNUNET_PACKED;
185 * Length of the GET path that follows (if tracked).
187 uint32_t get_path_length GNUNET_PACKED;
190 * When does the content expire?
192 struct GNUNET_TIME_Absolute expiration_time;
195 * The key of the corresponding GET request.
197 struct GNUNET_HashCode key;
199 /* put path (if tracked) */
201 /* get path (if tracked) */
211 struct PeerGetMessage
214 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
216 struct GNUNET_MessageHeader header;
221 uint32_t options GNUNET_PACKED;
224 * Desired content type.
226 uint32_t block_type GNUNET_PACKED;
231 uint32_t hop_count GNUNET_PACKED;
234 * Desired replication level for this request.
235 * In the current implementation, this value is not used.
237 uint32_t desired_replication_level GNUNET_PACKED;
240 * Total number of peers in get path.
242 unsigned int get_path_length;
245 * Peer which is an intermediate destination.
247 struct GNUNET_PeerIdentity current_destination;
250 * Source for which current_destination is the finger.
252 struct GNUNET_PeerIdentity current_source;
255 * The key we are looking for.
257 struct GNUNET_HashCode key;
265 * P2P Trail setup message
267 struct PeerTrailSetupMessage
271 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
273 struct GNUNET_MessageHeader header;
276 * Successor of this finger value will be our finger peer.
278 uint64_t destination_finger;
281 * Source peer which wants to setup the trail to one of its finger.
283 struct GNUNET_PeerIdentity source_peer;
286 * Peer to which this packet is forwarded.
288 struct GNUNET_PeerIdentity current_destination;
291 * In case the packet is forwarded to an intermediate finger, then
292 * current_source contains the peer id whose finger is the intermediate
293 * finger. In case the packet is forwarded to a friend, then it is NULL.
294 * FIXME: check the usage of current_source and fix this comment.
296 struct GNUNET_PeerIdentity current_source;
299 * Index into finger peer map, in Network Byte Order.
301 uint32_t finger_map_index;
304 * Number of entries in trail list, in Network Byte Order.
306 uint32_t trail_length GNUNET_PACKED;
308 /* Trail formed in the process. */
313 * P2P Trail Setup Result message
315 struct PeerTrailSetupResultMessage
319 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT
321 struct GNUNET_MessageHeader header;
324 * Finger to which we have found the path.
326 struct GNUNET_PeerIdentity finger_identity;
329 * Peer which was looking for the trail to finger.
331 struct GNUNET_PeerIdentity destination_peer;
334 * Index into finger peer map in NBO.
336 uint32_t finger_map_index;
339 * Number of entries in trail list in NBO.
341 uint32_t trail_length GNUNET_PACKED;
343 /* Trail from destination_peer to finger_identity */
349 * P2P Trail Rejection Message.
351 struct PeerTrailRejectionMessage
354 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
356 struct GNUNET_MessageHeader header;
359 * Source peer which wants to set up the trail.
361 struct GNUNET_PeerIdentity source_peer;
364 * Peer which sent trail rejection message.
366 struct GNUNET_PeerIdentity congested_peer;
369 * Peer identity which will be successor to this value will be finger of
372 uint64_t finger_identity_value;
375 * Index in finger peer map of source peer.
377 uint32_t finger_map_index;
380 * Total number of peers in the trail.
382 uint32_t trail_length;
384 /* Trail_list from source_peer to peer which sent the message for trail setup
385 * to congested peer.*/
390 * P2P Verify Successor message.
392 struct PeerVerifySuccessorMessage
396 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
398 struct GNUNET_MessageHeader header;
401 * Source peer which wants to verify its successor.
403 struct GNUNET_PeerIdentity source_peer;
406 * My current successor.
408 struct GNUNET_PeerIdentity successor;
411 * Total number of peers in trail to current successor.
413 uint32_t trail_length;
415 /* Trail to reach to from source_peer to successor. */
420 * P2P Verify Successor Result message.
422 struct PeerVerifySuccessorResultMessage
426 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
428 struct GNUNET_MessageHeader header;
431 * Destination peer which sent the request to verify its successor.
433 struct GNUNET_PeerIdentity destination_peer;
436 * Successor to which PeerVerifySuccessorMessage was sent.
438 struct GNUNET_PeerIdentity source_successor;
441 * source_successor's predecessor
443 struct GNUNET_PeerIdentity my_predecessor;
446 * Total number of peers in trail.
448 uint32_t trail_length;
450 /* Trail to reach from destination_peer to its correct successor.
451 * If source_successor is not destination peer, then trail is from destination_peer
453 * If source_successor is destination peer, then trail is from destination_peer
454 * to source_successor. */
459 * P2P Notify New Successor message.
461 struct PeerNotifyNewSuccessorMessage
464 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
466 struct GNUNET_MessageHeader header;
469 * Source peer which wants to notify its new successor.
471 struct GNUNET_PeerIdentity source_peer;
474 * New successor identity.
476 struct GNUNET_PeerIdentity destination_peer;
479 * Number of peers in trail from source_peer to new successor.
481 uint32_t trail_length;
483 /* Trail to from source_peer to destination_peer. */
486 struct PeerTrailTearDownMessage
489 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN
491 struct GNUNET_MessageHeader header;
494 * Source peer which wants to notify its new successor.
496 struct GNUNET_PeerIdentity source_peer;
499 * New successor identity.
501 struct GNUNET_PeerIdentity destination_peer;
504 * Number of peers in trail from source_peer to new successor.
506 uint32_t trail_length;
508 /* Trail to from source_peer to destination_peer. */
511 GNUNET_NETWORK_STRUCT_END
515 * Linked list of messages to send to a particular other peer.
517 struct P2PPendingMessage
520 * Pointer to next item in the list
522 struct P2PPendingMessage *next;
525 * Pointer to previous item in the list
527 struct P2PPendingMessage *prev;
530 * Message importance level. FIXME: used? useful?
532 unsigned int importance;
535 * When does this message time out?
537 struct GNUNET_TIME_Absolute timeout;
540 * Actual message to be sent, allocated at the end of the struct:
541 * // msg = (cast) &pm[1];
542 * // memcpy (&pm[1], data, len);
544 const struct GNUNET_MessageHeader *msg;
550 * Linked List of peers which are part of trail to reach a particular Finger.
555 * Pointer to next item in the list
557 struct TrailPeerList *next;
560 * Pointer to previous item in the list
562 struct TrailPeerList *prev;
565 * An element in this trail list
567 struct GNUNET_PeerIdentity peer;
573 * Entry in friend_peermap.
580 struct GNUNET_PeerIdentity id;
583 * 1. used in select_random_friend(), in case the friend has trails_count > TRAILS_THROUGH_FRIEND,
584 * then choose another friend.
585 * 2. in case of find_successor(), if the number of trails going through the friend
586 * has already crossed, then choose another friend.
587 * 3. in case of find_successor(), if we choose a finger, and if friend through
588 * which we reach this finger has crossed the limit then choose another finger/friend.
589 * 4. One way to implement in case of find_successor, is 1) you can have a global
590 * array of the entries and only when an entry is added in finger table, friend table,
591 * then you re calculate the array. In array while adding the element you check
592 * the threshold of the friend in case its friend, and in case of finger check
593 * the threshold of the first friend in the trail. If crossed then don't add the
594 * entries in the array. When the count goes down, then again set a flag and
595 * recalculte the array. Store a field in Finger table also, which will be
596 * equal to number of trails going through the first friend.
597 * Number of trail of which this friend is the first hop.
598 * 5.FIXME: understand where you need to use memcpy or direct assignment.
600 unsigned int trails_count;
603 * Count of outstanding messages for this friend.
605 unsigned int pending_count;
608 * Head of pending messages to be sent to this friend.
610 struct P2PPendingMessage *head;
613 * Tail of pending messages to be sent to this friend.
615 struct P2PPendingMessage *tail;
618 * Core handle for sending messages to this friend.
620 struct GNUNET_CORE_TransmitHandle *th;
626 * Entry in finger_peermap.
633 struct GNUNET_PeerIdentity finger_identity;
636 * Index in finger peer map
638 unsigned int finger_map_index;
641 * Total number of entries in trail from (me,finger]
643 unsigned int trail_length;
646 * Number of trail of which the first element to reach to this finger is
649 unsigned int first_friend_trails_count;
652 * Head of trail to reach this finger.
654 struct TrailPeerList *head;
657 * Tail of trail to reach this finger.
659 struct TrailPeerList *tail;
665 * FIXME: The name is not correct.
666 * Used to specify the kind of value stored in the array all_known_peers.
668 enum current_destination_type
678 * Data structure passed to sorting algorithm in find_successor().
683 * 64 bit value of peer identity
688 * FIXME: think of a better name for both the struct and destination_type
689 * Type : MY_ID, FINGER, FINGER, Value
691 enum current_destination_type type;
694 * Pointer to original data structure linked to peer id.
701 * FIXME: Not sure if we really need any such data structure.
702 * An entry in Failed_Trail_List
707 * Source peer which was trying to setup up the trail to @a destination_finger_value
709 struct GNUNET_PeerIdentity source_peer;
712 * Value to which we were trying to find the closest successor.
714 uint64_t destination_finger_value;
717 * Peer which has crossed the threshold limit on its routing table size.
719 struct GNUNET_PeerIdentity congested_peer;
725 * Task that sends FIND FINGER TRAIL requests. This task is started when we have
726 * get our first friend.
728 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
731 * Task that periodically verifies my successor. This task is started when we
732 * have found our successor.
734 static GNUNET_SCHEDULER_TaskIdentifier verify_successor;
737 * Identity of this peer.
739 static struct GNUNET_PeerIdentity my_identity;
742 * Hash map of all the friends of a peer
744 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
747 * Hash map of all the fingers of a peer
749 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
754 static struct GNUNET_CORE_Handle *core_api;
757 * Finger map index for predecessor entry in finger peermap.
759 #define PREDECESSOR_FINGER_ID 64
761 unsigned int all_friends_trail_threshold;
763 * FIXME: The problem with incrementing this value in find_finger_trail_task
764 * is that it may happen that we started with a request to look for a finger
765 * with current_finger_index = x, and its not yet complete but we are again back
766 * in send_find_finger_trail message and we again start looking for current_finger_index = x.
767 * and only when we get the entry for x, we make it x-1. I am not sure if this is
769 * The current finger index that we have want to find trail to.
771 static unsigned int current_finger_index;
775 * Iterate over trail and search your index location in the array.
776 * @param trail Trail which contains list of peers.
777 * @param trail_length Number of peers in the trail.
778 * @return Index in the array.
779 * #GNUNET_SYSERR, in case there is no entry which should not be the case ideally.
782 search_my_index (const struct GNUNET_PeerIdentity *trail,
787 while (i < trail_length)
789 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
795 return GNUNET_SYSERR;
800 * Invert the trail list.
801 * @param destination_peer Destination of the inverted trail.Trail is always
802 * (me, destination]. I am not part of trail that starts
804 * @param existing_trail Trail
805 * @param trail_length Number of peers in the existing trail.
808 static struct GNUNET_PeerIdentity *
809 invert_trail_list (struct GNUNET_PeerIdentity *destination_peer,
810 struct GNUNET_PeerIdentity *existing_trail,
811 unsigned int trail_length)
815 struct GNUNET_PeerIdentity *new_trail;
818 new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
820 if (trail_length > 1)
822 i = trail_length - 2;
825 memcpy( &new_trail[j], &existing_trail[i], sizeof (struct GNUNET_PeerIdentity));
830 memcpy (&new_trail[j], destination_peer, sizeof(struct GNUNET_PeerIdentity));
837 * Called when core is ready to send a message we asked for
838 * out to the destination.
840 * @param cls the 'struct FriendInfo' of the target friend
841 * @param size number of bytes available in buf
842 * @param buf where the callee should write the message
843 * @return number of bytes written to buf
846 core_transmit_notify (void *cls, size_t size, void *buf)
848 struct FriendInfo *peer = cls;
850 struct P2PPendingMessage *pending;
855 while ((NULL != (pending = peer->head)) &&
856 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
858 peer->pending_count--;
859 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
860 GNUNET_free (pending);
864 /* no messages pending */
870 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
871 GNUNET_CORE_PRIO_BEST_EFFORT,
872 GNUNET_TIME_absolute_get_remaining
873 (pending->timeout), &peer->id,
874 ntohs (pending->msg->size),
875 &core_transmit_notify, peer);
876 GNUNET_break (NULL != peer->th);
880 while ((NULL != (pending = peer->head)) &&
881 (size - off >= (msize = ntohs (pending->msg->size))))
883 GNUNET_STATISTICS_update (GDS_stats,
885 ("# Bytes transmitted to other peers"), msize,
887 memcpy (&cbuf[off], pending->msg, msize);
889 peer->pending_count--;
890 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
891 GNUNET_free (pending);
893 if (peer->head != NULL)
896 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
897 GNUNET_CORE_PRIO_BEST_EFFORT,
898 GNUNET_TIME_absolute_get_remaining
899 (pending->timeout), &peer->id, msize,
900 &core_transmit_notify, peer);
901 GNUNET_break (NULL != peer->th);
908 * Transmit all messages in the friend's message queue.
910 * @param peer message queue to process
913 process_friend_queue (struct FriendInfo *peer)
915 struct P2PPendingMessage *pending;
917 if (NULL == (pending = peer->head))
919 if (NULL != peer->th)
922 GNUNET_STATISTICS_update (GDS_stats,
924 ("# Bytes of bandwidth requested from core"),
925 ntohs (pending->msg->size), GNUNET_NO);
927 /* FIXME: Are we correctly initializing importance and pending. */
929 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
931 GNUNET_TIME_absolute_get_remaining
932 (pending->timeout), &peer->id,
933 ntohs (pending->msg->size),
934 &core_transmit_notify, peer);
935 GNUNET_break (NULL != peer->th);
940 * Construct a trail message and forward it to a friend.
941 * @param source_peer Peer which wants to set up the trail to one of its finger.
942 * @param destination_finger Peer identity closest to this value will be
943 * @a source_peer's finger.
944 * @param current_destination Finger of the @a current_source, for which among
945 * its friends, its own identity and all fingers, this
946 * finger is the closest to the @a destination_finger
947 * @param current_source Peer for which @a current_destination is its finger.
948 * @param target_friend Friend to which this message should be forwarded.
949 * @param trail_length Numbers of peers in the trail found so far.
950 * @param trail_peer_list Peers this request has traversed so far
951 * @param finger_map_index Index in finger peer map
954 GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
955 uint64_t destination_finger,
956 struct GNUNET_PeerIdentity *current_destination,
957 struct GNUNET_PeerIdentity *current_source,
958 struct FriendInfo *target_friend,
959 unsigned int trail_length,
960 const struct GNUNET_PeerIdentity *trail_peer_list,
961 unsigned int finger_map_index)
963 struct P2PPendingMessage *pending;
964 struct PeerTrailSetupMessage *tsm;
965 struct GNUNET_PeerIdentity *peer_list;
968 msize = sizeof (struct PeerTrailSetupMessage) +
969 (trail_length * sizeof (struct GNUNET_PeerIdentity));
971 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
977 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
979 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
983 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
984 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
985 tsm = (struct PeerTrailSetupMessage *) &pending[1];
986 pending->msg = &tsm->header;
987 tsm->header.size = htons (msize);
988 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
989 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
990 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
991 memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
992 memcpy (&(tsm->current_source), current_source, sizeof (struct GNUNET_PeerIdentity));
993 tsm->trail_length = htonl (trail_length);
994 tsm->finger_map_index = htonl (finger_map_index);
996 if (trail_peer_list != NULL)
998 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
999 memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1002 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1003 target_friend->pending_count++;
1004 process_friend_queue (target_friend);
1010 * Construct a trail setup result message and forward it to a friend.
1011 * @param destination_peer Peer which will get the trail to one of its finger.
1012 * @param source_finger Peer to which the trail has been setup to.
1013 * @param target_friend Friend to which this message should be forwarded.
1014 * @param trail_length Numbers of peers in the trail.
1015 * @param trail_peer_list Peers which are part of the trail from source to destination.
1016 * @param finger_map_index Index in finger peer map
1019 GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *destination_peer,
1020 const struct GNUNET_PeerIdentity *source_finger,
1021 struct FriendInfo *target_friend,
1022 unsigned int trail_length,
1023 const struct GNUNET_PeerIdentity *trail_peer_list,
1024 unsigned int finger_map_index)
1026 struct P2PPendingMessage *pending;
1027 struct PeerTrailSetupResultMessage *tsrm;
1028 struct GNUNET_PeerIdentity *peer_list;
1031 msize = sizeof (struct PeerTrailSetupResultMessage) +
1032 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1034 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1040 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1042 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1046 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1047 pending->importance = 0;
1048 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1049 tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1050 pending->msg = &tsrm->header;
1051 tsrm->header.size = htons (msize);
1052 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
1053 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1054 memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity));
1055 tsrm->trail_length = htonl (trail_length);
1056 tsrm->finger_map_index = htonl (finger_map_index);
1057 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[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 * Construct a PeerVerifySuccessor message and send it to friend.
1069 * @param source_peer Peer which wants to verify its successor
1070 * @param successor Peer which is our current successor
1071 * @param target_friend Friend to which this message should be forwarded.
1072 * @param trail_peer_list Peer which are part of trail from source to destination
1073 * @param trail_length Number of peers in the trail list.
1075 void GDS_NEIGHBOURS_send_verify_successor(const struct GNUNET_PeerIdentity *source_peer,
1076 const struct GNUNET_PeerIdentity *successor,
1077 struct FriendInfo *target_friend,
1078 const struct GNUNET_PeerIdentity *trail_peer_list,
1079 unsigned int trail_length)
1081 struct PeerVerifySuccessorMessage *vsm;
1082 struct P2PPendingMessage *pending;
1083 struct GNUNET_PeerIdentity *peer_list;
1086 msize = sizeof (struct PeerVerifySuccessorMessage) +
1087 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1089 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1095 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1097 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1101 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1102 pending->importance = 0; /* FIXME */
1103 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1104 vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1105 pending->msg = &vsm->header;
1106 vsm->header.size = htons (msize);
1107 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1108 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
1109 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1110 vsm->trail_length = htonl (trail_length);
1111 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1112 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1114 /* Send the message to chosen friend. */
1115 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1116 target_friend->pending_count++;
1117 process_friend_queue (target_friend);
1123 * Construct a PeerVerifySuccessorResult message and send it to friend.
1124 * @param destination_peer Peer which sent verify successor message
1125 * @param source_successor Peer to which verify successor message was sent.
1126 * @param my_predecessor source_successor's predecessor.
1127 * @param target_friend Friend to which this message should be forwarded.
1128 * @param trail_peer_list Peers which are part of trail from source to destination
1129 * @param trail_length Number of peers in the trail list.
1131 void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdentity *destination_peer,
1132 const struct GNUNET_PeerIdentity *source_successor,
1133 const struct GNUNET_PeerIdentity *my_predecessor,
1134 struct FriendInfo *target_friend,
1135 const struct GNUNET_PeerIdentity *trail_peer_list,
1136 unsigned int trail_length)
1138 struct PeerVerifySuccessorResultMessage *vsmr;
1139 struct P2PPendingMessage *pending;
1140 struct GNUNET_PeerIdentity *peer_list;
1143 msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1144 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1146 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1153 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1155 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1159 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1160 pending->importance = 0; /* FIXME */
1161 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1162 vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1163 pending->msg = &vsmr->header;
1164 vsmr->header.size = htons (msize);
1165 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1166 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1167 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
1168 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
1169 vsmr->trail_length = htonl (trail_length);
1170 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1171 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1173 /* Send the message to chosen friend. */
1174 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1175 target_friend->pending_count++;
1176 process_friend_queue (target_friend);
1181 * Construct a PeerNotifyNewSuccessor message and send it to friend.
1182 * @param source_peer Peer which is sending notify message to its new successor.
1183 * @param destination_peer Peer which is the new destination.
1184 * @param target_friend Next friend to pass this message to.
1185 * @param peer_list List of peers in the trail to reach to destination_peer.
1186 * @param trail_length Total number of peers in peer list
1189 GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *source_peer,
1190 const struct GNUNET_PeerIdentity *destination_peer,
1191 struct FriendInfo *target_friend,
1192 const struct GNUNET_PeerIdentity *trail_peer_list,
1193 unsigned int trail_length)
1195 struct PeerNotifyNewSuccessorMessage *nsm;
1196 struct P2PPendingMessage *pending;
1197 struct GNUNET_PeerIdentity *peer_list;
1200 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1201 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1203 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1209 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1211 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1215 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1216 pending->importance = 0; /* FIXME */
1217 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1218 nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1219 pending->msg = &nsm->header;
1220 nsm->header.size = htons (msize);
1221 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1222 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1223 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1224 nsm->trail_length = htonl (trail_length);
1226 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1227 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1229 /* Send the message to chosen friend. */
1230 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1231 target_friend->pending_count++;
1232 process_friend_queue (target_friend);
1236 * Send a trail tear down message
1237 * @param source_peer Source of the trail.
1238 * @param destination_peer Destination of the trail.
1239 * @param trail_list Peers in the trail from @a source_peer to @a destination_peer
1240 * @param trail_length Total number of peers in trail_list.
1241 * @pararm target_peer Next peer to forward this message to.
1244 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_PeerIdentity *source_peer,
1245 const struct GNUNET_PeerIdentity *destination_peer,
1246 struct GNUNET_PeerIdentity *trail_peer_list,
1247 unsigned int trail_length,
1248 struct FriendInfo *target_friend)
1250 struct P2PPendingMessage *pending;
1251 struct PeerTrailTearDownMessage *ttdm;
1252 struct GNUNET_PeerIdentity *peer_list;
1255 msize = sizeof (struct PeerTrailTearDownMessage) +
1256 (trail_length * sizeof(struct GNUNET_PeerIdentity));
1258 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1264 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1266 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1270 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1271 pending->importance = 0; /* FIXME */
1272 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1273 ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1274 pending->msg = &ttdm->header;
1275 ttdm->header.size = htons (msize);
1276 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN);
1277 memcpy (&(ttdm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1278 memcpy (&(ttdm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1279 ttdm->trail_length = htonl (trail_length);
1281 peer_list = (struct GNUNET_PeerIdentity *) &ttdm[1];
1282 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1284 /* Send the message to chosen friend. */
1285 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1286 target_friend->pending_count++;
1287 process_friend_queue (target_friend);
1292 * FIXME: Optimizaiton Once the basic code is running. Add the optimization
1293 * where you check if the threshold on number of links that should go through
1294 * a particular friend has crossed. If yes then again choose a different
1295 * friend. Important that the new friend chosen should be different. How to
1296 * ensure this? This is an important optimization as without this one x-vine
1297 * is actually not a sybil tolerant DHT.
1298 * Randomly choose one of your friends from the friends_peer map
1301 static struct FriendInfo *
1302 select_random_friend (struct GNUNET_PeerIdentity *congested_peer)
1304 unsigned int current_size;
1305 unsigned int *index;
1307 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1308 struct GNUNET_PeerIdentity key_ret;
1309 struct FriendInfo *friend;
1311 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1312 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1313 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1317 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1325 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1327 /* TODO: UPDATE: Also, I think I am always looking for better trails, and always
1328 * choosing friends randomly so this solves the problem automatically. I don't
1329 * think I should call this algorithm here. Will read
1330 * the paper again and check if its right or not. Here you have
1331 * chosen a random friend. Now you should check the size
1332 of its routing table size, and if its more than threshold, then check which
1333 of the entries has trail length greater than trail length threshold. we
1334 should without checking the routing table size also we should check the
1335 trail with trail length greater than threshold. then
1336 you should try to find a new route through this new node that has joined in
1337 only for those finger entries whose trail length is greater than threshold.
1338 But I don't want the new node to wait for this process to get over. so
1339 should i declare a function which will be called after some interval.*/
1340 /* here we are checking the value only set by us. but the friend may have its
1341 routing table full. we don't have the access to the value. in trail setup
1342 it will fail. so in case of put/get if we don't have the trail already then
1343 how does the intermediate peer stores the information in routing table.
1344 because in put we don't do the put result. hence, intermediate peers don't
1345 add the path in their routing table. then in get is it problem. */
1346 /* Possible number of trails that can go through this friend has been reached. */
1347 if (friend->trails_count > TRAIL_THROUGH_FRIEND_THRESHOLD)
1349 /* FIXME: What should I do now, should I call this same function again and
1350 remember the index, j so that call random function without j and find
1351 a new friend. Also, I need some way to make sure that if number of times
1352 I have called the function is equal to number of entries in friend peermap.
1353 then I should return NULL. but its much better to have a function which
1354 just eliminates looking at the entries with threshold crossed. URGENT: Whats
1355 the best way to handle this case? */
1365 * Compute finger_identity to which we want to setup the trail
1366 * @return finger_identity
1369 compute_finger_identity()
1373 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1374 my_id64 = GNUNET_ntohll (my_id64);
1375 return (my_id64 + (unsigned long) pow (2, current_finger_index));
1380 * Compute immediate predecessor identity in the network.
1381 * @return peer identity of immediate predecessor.
1384 compute_predecessor_identity()
1388 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1389 my_id64 = GNUNET_ntohll (my_id64);
1390 return (my_id64 -1);
1395 * Periodically ping your successor to ask its current predecessor
1397 * @param cls closure for this task
1398 * @param tc the context under which the task is running
1401 send_verify_successor_message (void *cls,
1402 const struct GNUNET_SCHEDULER_TaskContext *tc )
1404 struct GNUNET_TIME_Relative next_send_time;
1405 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1406 struct GNUNET_PeerIdentity key_ret;
1407 struct FriendInfo *target_friend;
1408 struct GNUNET_PeerIdentity *next_hop;
1409 struct GNUNET_PeerIdentity *peer_list;
1410 struct FingerInfo *finger;
1411 unsigned int finger_index;
1415 /* Find the successor from the finger peermap.*/
1416 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1417 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1419 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1420 (const void **)&finger))
1422 if (0 == finger->finger_map_index)
1429 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1432 goto send_new_request;
1434 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->trail_length);
1436 struct TrailPeerList *iterate;
1437 iterate = finger->head;
1439 while ( i < (finger->trail_length))
1441 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1442 iterate = iterate->next;
1446 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1447 memcpy (next_hop, &peer_list[0], sizeof (struct GNUNET_PeerIdentity));
1448 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1450 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1451 &(finger->finger_identity),
1454 finger->trail_length);
1457 /* FIXME: Understand what this function is actually doing here. */
1459 next_send_time.rel_value_us =
1460 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1461 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1462 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1465 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
1471 * Choose a random friend and start looking for the trail to reach to
1472 * finger identity through this random friend.
1474 * @param cls closure for this task
1475 * @param tc the context under which the task is running
1478 send_find_finger_trail_message (void *cls,
1479 const struct GNUNET_SCHEDULER_TaskContext *tc)
1481 struct FriendInfo *target_friend;
1482 struct GNUNET_TIME_Relative next_send_time;
1483 uint64_t finger_identity;
1484 unsigned int finger_map_index;
1486 next_send_time.rel_value_us =
1487 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1488 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1489 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
1491 /* FIXME; if all the friend have reached their threshold, then don't schedule
1492 the task till the all_friends_trail_threshold gets reset. It will be
1493 scheduled from there. So, in finger table when we remove an entry and the new
1494 * entry does not have the same friend as the first hop, then decrement the
1495 * threshold limit. and schedule this task.
1496 IMPORTANT: reset the value some where. Better name */
1497 if (GNUNET_YES == all_friends_trail_threshold)
1502 find_finger_trail_task =
1503 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1506 /* Friend peermap is empty but this task has already been started it failed.*/
1507 if (GNUNET_CONTAINER_multipeermap_size (friend_peermap) == 0)
1513 target_friend = select_random_friend (NULL);
1515 if (NULL == target_friend)
1517 /* FIXME URGENT: Here we can get NULL all of the friends have reached their threshold.
1518 * At the moment, the code for select_random_friend, is not handling it. In such a
1519 * case I think we can set a flag, and only when any value for any friend gets
1520 * decremented,(which can happen only in finger table, when we remove an entry
1521 * from our finger table, and we are not part of the trail to reach to that
1522 * finger any more, t then reset the flag and schedule the code from there. */
1523 all_friends_trail_threshold = GNUNET_YES;
1527 if (PREDECESSOR_FINGER_ID == current_finger_index)
1529 finger_identity = compute_predecessor_identity();
1533 finger_identity = compute_finger_identity();
1536 finger_map_index = current_finger_index;
1538 /* URGENT :FIXME: In case the packet is not sent to a finger, then current_source is the
1539 * peer which sent the packet and current_destination which recevied it. Now
1540 * these fields are not always used. Think of some way to remove these variables. */
1541 GDS_NEIGHBOURS_send_trail_setup (&my_identity, finger_identity, &(target_friend->id),
1542 &my_identity, target_friend, 0, NULL, finger_map_index);
1547 * Check if there is a predecessor in our finger peer map or not.
1548 * If no, then return GNUNET_YES
1549 * else compare existing predecessor and peer, and find the correct
1551 * @param existing_predecessor
1552 * @param new_predecessor
1553 * @return #GNUNET_YES if new peer is predecessor
1554 * #GNUNET_NO if new peer is not the predecessor.
1557 compare_predecessor(struct GNUNET_PeerIdentity *peer)
1559 /* FIXME: here you should first check if you already have an entry in the
1560 finger peer map for finger index = 64, if yes then compare it with peer
1561 if not then just add the peer. */
1567 update_predecessor (struct GNUNET_PeerIdentity *peer, struct GNUNET_PeerIdentity *trail_peer_list)
1569 /* In this function, we check if there is an entry or not for predecessor.
1570 if not then just add the peer, if no then compare the closest one, and add it
1571 . and remove the older one. There can still be multiple paths to reach to
1572 predecessor so in case both are same then make sure the paths are disjoint
1573 and then do multiple routing options. Also, invert the trail. and then add.
1574 Do all the things here. */
1580 * FIXME: free_finger(remove_finger); Call this function at finger_table_add,
1581 when you replace an existing entry
1582 * Free finger and its trail.
1583 * @param remove_finger Finger to be freed.
1586 free_finger (struct FingerInfo *finger)
1588 struct TrailPeerList *peer;
1590 while (NULL != (peer = finger->head))
1592 GNUNET_CONTAINER_DLL_remove (finger->head, finger->tail, peer);
1596 GNUNET_free (finger);
1604 static struct GNUNET_PeerIdentity *
1605 check_for_successor ()
1612 * FIXME: How do I send back the updated trail.
1613 * Scan the trail to check if any on my own friend is part of trail. If yes
1614 * the shortcut the trail and update the finger_trail and trail_length.
1615 * @param finger_trail
1616 * @param trail_length
1619 static struct GNUNET_PeerIdentity *
1620 scan_trail (struct GNUNET_PeerIdentity *finger_trail, unsigned int trail_length,
1621 const struct GNUNET_PeerIdentity *finger)
1623 /* start from the second element as first element will always be your friend.
1624 In case trail_length = 2, and the last element is also your friend then you
1625 should delete the first element. In other cases go through the list and check
1627 int i = trail_length - 1;
1631 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_trail[i]))
1633 /* This element of trail is not my friend. */
1638 /* If for any i>1 we found a friend, then we can use this friend as the
1639 first link and forget about all the peers behind it. But we need to first
1640 copy the peers behind it. send a trail tear down message along
1642 struct GNUNET_PeerIdentity *discarded_trail;
1643 struct FriendInfo *target_friend;
1644 /* FIXME: Create a new trail. to send back*/
1645 int discarded_trail_length = trail_length - i;
1647 discarded_trail = GNUNET_malloc (discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1649 while (j < (discarded_trail_length + 1))
1651 memcpy (&discarded_trail[j], &finger_trail[j], sizeof (struct GNUNET_PeerIdentity));
1655 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_trail[0]);
1656 /* FIXME: THAT IN ROUTING TABLE SOURCE PEER IS INDEED THE SOURCE PEER.
1657 * should trail contain last element as finger or just the last element.? if
1658 * you can get some value then you should not keep at different places.
1659 * remove finger as last element in the trail. */
1660 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, discarded_trail,
1661 discarded_trail_length, target_friend);
1663 /* fixme: CHANGE IT TO NEW TRAIL */
1672 * 1.* If you remove an entry from finger table, and if the finger is not your friend
1673 * and the trail length > 1 for the finger that you removed, then you should send
1674 * a trail_teardown message along the trail. so that the peers which have an
1675 * entry in their routing table for this trail can remove it from their routing
1678 * Choose the closest successor from existing_finger and new_finger. In case new_finger
1679 * is choosen, then send a tear down message along the trail to reach existing_finger.
1680 * @param existing_finger Existing entry in finger peer map
1681 * @param new_finger New finger
1682 * @param trail Trail to reach to the new finger from me.
1683 * @param trail_length Number of peers in the @a trail
1684 * @param finger_map_index If finger_map_index == PREDECESSOR_FINGER_INDEX,
1685 * then we use a different logic to find the closest
1687 * @return #GNUNET_YES In case we want to store the new entry.
1688 * #GNUNET_NO In case we want the existing entry.
1689 * #GNUNET_SYSERR Error.
1692 int select_correct_entry (struct FingerInfo *existing_finger,
1693 const struct GNUNET_PeerIdentity *new_finger,
1694 struct GNUNET_PeerIdentity *trail,
1695 unsigned int trail_length)
1697 int val = GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), new_finger);
1700 /* FIXME: if the new entry = old entry, then compare the trails, and see if the trails
1701 are disjoint, then send GNUNET_YES, but don't free old finger. But first you
1702 * should collapse the trail and then do comparison. Also, if you are collapsing
1703 * for one case then you should do it for all the cases where you are sending
1705 /* Scan the trail for a friend and shorten if possible. */
1706 scan_trail (trail, trail_length, new_finger);
1711 /* If the new entry is closest one, then free the old entry, send a trail_teardown message.*/
1712 struct GNUNET_PeerIdentity *peer_list;
1713 struct FriendInfo *friend;
1714 struct TrailPeerList *finger_trail;
1715 int existing_finger_trail_length = existing_finger->trail_length;
1718 finger_trail = existing_finger->head;
1719 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(finger_trail->peer));
1720 peer_list = GNUNET_malloc ( existing_finger_trail_length * sizeof (struct GNUNET_PeerIdentity));
1721 while (i < existing_finger->trail_length)
1723 memcpy (&peer_list[i], &(finger_trail->peer), sizeof (struct GNUNET_PeerIdentity));
1724 finger_trail = finger_trail->next;
1728 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, &(existing_finger->finger_identity),
1729 peer_list, existing_finger_trail_length, friend);
1731 free_finger (existing_finger);
1732 scan_trail (trail, trail_length, new_finger);
1737 /* If the old entry is closest then just return GNUNET_NO.*/
1740 return GNUNET_SYSERR;
1745 * SUPU: now the finger trail does not contain finger identity as the last element.
1747 * 1. handle predecessor case differently.
1748 * how to handle the case in which same finger identity is stored for different
1749 * finger map index. because this will just increase the size of finger map and
1750 * also size of the array we use in find_successor.
1751 * Add an entry in finger table. Before adding, check if there is already an
1752 * entry in finger peermap for the same index, if yes then choose the closest one.
1753 * In case both the existing identity and new identity are same, keep both the trail
1754 * only if the trails are different (Redundant routing). Also, a peer stored at index,i
1755 * if its same as peer stored index, i+1, and 'i' is the lowest finger map index
1756 * seen so far, then that peer is the successor. In case finger_map_index is PREDECESSOR_INDEX,
1757 * then simply add it as handle rest of the cases for it in a different function.
1758 * Also while adding an entry check the trail, scan the trail and check if there
1759 * is a friend in between, then shortcut the path.
1760 * @param finger_identity
1761 * @param finger_trail
1762 * @param finger_trail_length
1763 * @param finger_map_index
1766 void finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
1767 struct GNUNET_PeerIdentity *finger_trail,
1768 uint32_t finger_trail_length,
1769 uint32_t finger_map_index)
1771 struct FingerInfo new_finger_entry;
1772 struct FingerInfo *existing_finger;
1773 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1776 /* If I am my own finger, then return. */
1777 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, finger_identity))
1780 /* FIXME:Is there any point in keeping my own identity as finger?
1781 * Also, send a trail tear down message to all the peers which
1782 are in the finger trail, so that they can remove the entries from routing
1787 /* Check if there is already an entry for the finger map index in the finger peer map. */
1788 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1789 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
1791 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
1792 (const void **)&existing_finger))
1794 /* If existing_finger is the closest, then don't add any entry. */
1795 if ( GNUNET_NO == select_correct_entry (existing_finger, finger_identity,
1796 finger_trail, finger_trail_length))
1797 goto increment_finger_index;
1801 /* Add the new entry. */
1802 memcpy (&(new_finger_entry.finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
1803 new_finger_entry.finger_map_index = finger_map_index;
1804 new_finger_entry.trail_length = finger_trail_length;
1806 while (i < finger_trail_length)
1808 struct TrailPeerList *element;
1809 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1810 element->next = NULL;
1811 element->prev = NULL;
1813 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
1814 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry.head, new_finger_entry.tail, element);
1818 GNUNET_assert (GNUNET_OK ==
1819 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
1820 &(new_finger_entry.finger_identity),
1822 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
1824 /* FIXME: after adding an entry, I want to check if there is a successor, if yes
1825 then this function will return it and then we should schedule a verify successor
1826 task Will the successor always be at index 0 */
1827 increment_finger_index:
1828 if (NULL != check_for_successor())
1830 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1831 current_finger_index = PREDECESSOR_FINGER_ID;
1835 /* FIXME: Not sure if this is the correct place to set the values. Look into
1836 send_find_finger_trail_message and check. */
1837 if(current_finger_index == 0)
1838 current_finger_index = PREDECESSOR_FINGER_ID;
1840 current_finger_index = current_finger_index - 1;
1845 /*FIXME: Here you need to set the correct value of finger_map_index,
1846 * in case it is 0, then you set it back to 64, and in case it is x,
1847 * then you set it back to x-1. current_finger_index = ( current_finger_index - 1) % MAX_FINGERS
1848 * we also need to change the logic of starting the process to look for a successor.
1849 * when you add an entry then go through whole trail and check if there is an entry
1850 * which is your friend, if yes then just collapse the trail. if you are not doing it
1851 * here then you need to do it in handle_core_disconnect where you will have to search
1852 * through whole trail find peer and then delete the finger.
1853 * Add an entry in finger table.
1854 * @param finger_identity Peer identity of finger
1855 * @param finger_trail Trail to reach the finger
1856 * @param trail_length Number of peers in the trail.
1857 * @param finger_map_index Index in finger peer map.
1860 void finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
1861 const struct GNUNET_PeerIdentity *finger_trail,
1862 unsigned int trail_length,
1863 const unsigned int finger_map_index)
1865 struct FingerInfo *new_finger_entry;
1866 //struct GNUNET_PeerIdentity key_ret;
1868 //struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1869 //struct FingerInfo *existing_finger;
1872 /* SUPU Here we trying to check if we already have an entry. If yes then we
1873 can keep two trails for redundant routing. if they are different then we
1874 need to choose the closest one. and remove the other one. */
1876 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1878 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1880 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1881 (const void **)&existing_finger))
1883 if ((finger_map_index == existing_finger->finger_map_index))
1885 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),finger_identity))
1887 /* FIXME: Here you should check if the trail is same. If yes then don't add the entry. it
1888 seems to be very suboptimal. */
1889 if ((existing_finger->trail_length) == trail_length)
1891 struct TrailPeerList *iterate;
1892 iterate = existing_finger->head;
1895 while (k < trail_length)
1897 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(iterate->peer), &finger_trail[k]))
1900 iterate = iterate->next;
1903 if (k == trail_length)
1913 if (finger_map_index == 1)
1915 ret = compare_predecessor (&(existing_finger->finger_identity),
1921 ret = compare_finger_identity (&(existing_finger->finger_identity),
1926 GNUNET_assert (GNUNET_YES ==
1927 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
1928 &(existing_finger->finger_identity),
1943 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
1944 memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
1945 new_finger_entry->finger_map_index = finger_map_index;
1947 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, finger_identity))
1949 /* I am the finger */
1950 new_finger_entry->trail_length = 0;
1951 /* FIXME: If I am the finger then why do we even do an entry. don't add any
1952 * field because it is of no use. you may just send a message to yourself
1953 * when another peer send you a trail setup or put request. */
1958 while (i < trail_length)
1960 struct TrailPeerList *element;
1961 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1962 element->next = NULL;
1963 element->prev = NULL;
1965 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
1966 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head, new_finger_entry->tail, element);
1969 new_finger_entry->trail_length = trail_length;
1972 /* FIXME: Here we are keeping multiple hashmap option so that there are
1973 multiple routes to reach to same finger, redundant routing.
1974 * Also same peers could be our fingers for different finger map index
1975 * Should we handle the case where we have same fingers at the different
1976 * finger index but with different trail to reach. */
1977 GNUNET_assert (GNUNET_OK ==
1978 GNUNET_CONTAINER_multipeermap_put (finger_peermap,
1979 &(new_finger_entry->finger_identity),
1981 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
1983 if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap)
1984 && (new_finger_entry->finger_map_index!= 1))
1986 verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1992 * Compare two peer identities.
1993 * @param p1 Peer identity
1994 * @param p2 Peer identity
1995 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
1998 compare_peer_id (const void *p1, const void *p2)
2000 struct Sorting_List *p11;
2001 struct Sorting_List *p22;
2003 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
2004 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
2005 p11 = (struct Sorting_List *)p1;
2006 p22 = (struct Sorting_List *)p2;
2007 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
2008 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
2014 * Return the successor of value in all_known_peers.
2015 * @param all_known_peers list of all the peers
2016 * @param value value we have to search in the all_known_peers.
2019 static struct Sorting_List *
2020 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
2029 middle = (first + last)/2;
2031 while(first <= last)
2033 if(all_known_peers[middle].peer_id < value)
2037 else if(all_known_peers[middle].peer_id == value)
2039 if(middle == (size -1))
2041 return &all_known_peers[0];
2045 return &all_known_peers[middle+1];
2053 middle = (first + last)/2;
2060 * Find closest successor for the value.
2061 * @param value Value for which we are looking for successor
2062 * @param[out] current_destination set to the end of the finger to traverse next
2063 * @param[out] current_source set to my_identity.
2064 * @param congested_peer Peer not to be considered when looking for
2065 * successor. FIXME: IMPLEMENT IT.
2066 * @return Peer identity of next hop, NULL if we are the
2067 * ultimate destination
2069 static struct GNUNET_PeerIdentity *
2070 find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination,
2071 struct GNUNET_PeerIdentity *current_source,
2072 struct GNUNET_PeerIdentity *congested_peer)
2074 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
2075 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2076 struct GNUNET_PeerIdentity key_ret;
2077 struct FriendInfo *friend;
2078 struct FingerInfo *finger;
2079 unsigned int finger_index;
2080 unsigned int friend_index;
2081 struct Sorting_List *successor;
2085 /* 2 is added in size for my_identity and value which will part of all_known_peers. */
2086 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
2087 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
2090 struct Sorting_List all_known_peers[size];
2093 for (k = 0; k < size; k++)
2094 all_known_peers[k].peer_id = 0;
2096 /* Copy your identity at 0th index in all_known_peers. */
2098 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
2099 all_known_peers[j].type = MY_ID;
2100 all_known_peers[j].data = 0;
2104 all_known_peers[j].peer_id = value;
2105 all_known_peers[j].type = VALUE;
2106 all_known_peers[j].data = 0;
2109 /* Iterate over friend peer map and copy all the elements into array. */
2110 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2111 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
2113 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
2115 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
2116 all_known_peers[j].type = FRIEND;
2117 all_known_peers[j].data = friend;
2122 /* Iterate over finger map and copy all the entries into all_known_peers array. */
2123 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2124 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2126 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
2128 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
2129 all_known_peers[j].type = FINGER;
2130 all_known_peers[j].data = finger;
2135 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2136 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
2138 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
2140 /* search value in all_known_peers array. */
2141 successor = find_closest_successor (all_known_peers, value, size);
2143 if (successor->type == MY_ID)
2147 else if (successor->type == FRIEND)
2149 struct FriendInfo *target_friend;
2150 target_friend = (struct FriendInfo *)successor->data;
2151 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
2152 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2153 return current_destination;
2155 else if (successor->type == FINGER)
2157 struct GNUNET_PeerIdentity *next_hop;
2158 struct FingerInfo *finger;
2159 struct TrailPeerList *iterator;
2160 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
2161 finger = successor->data;
2162 iterator = finger->head;
2163 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2164 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2165 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
2166 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2177 /** FIXME: by default I keep current_source, and destination as my own id.
2178 * in case we find a finger then we update current_source in the
2179 * find_successor message.
2180 * Construct a Put message and send it to target_peer.
2181 * @param key Key for the content
2182 * @param data Content to store
2183 * @param data_size Size of content @a data in bytes
2184 * @param block_type Type of the block
2185 * @param options Routing options
2186 * @param desired_replication_level Desired replication count
2187 * @param expiration_time When does the content expire
2188 * @param current_destination
2189 * @param current_source
2190 * @param target_peer Peer to which this message will be forwarded.
2191 * @param hop_count Number of hops traversed so far.
2192 * @param put_path_length Total number of peers in @a put_path
2193 * @param put_path Number of peers traversed so far
2196 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2197 const void *data, size_t data_size,
2198 enum GNUNET_BLOCK_Type block_type,
2199 enum GNUNET_DHT_RouteOption options,
2200 uint32_t desired_replication_level,
2201 struct GNUNET_TIME_Absolute expiration_time,
2202 struct GNUNET_PeerIdentity current_destination,
2203 struct GNUNET_PeerIdentity current_source,
2204 struct GNUNET_PeerIdentity *target_peer,
2206 uint32_t put_path_length,
2207 struct GNUNET_PeerIdentity *put_path)
2209 struct PeerPutMessage *ppm;
2210 struct P2PPendingMessage *pending;
2211 struct FriendInfo *target_friend;
2212 struct GNUNET_PeerIdentity *pp;
2215 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2216 sizeof (struct PeerPutMessage);
2218 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2220 put_path_length = 0;
2221 msize = data_size + sizeof (struct PeerPutMessage);
2224 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2230 /* This is the first call made from clients file. So, we should search for the
2232 if (NULL == target_peer)
2235 struct GNUNET_PeerIdentity *next_hop;
2237 memcpy (&key_value, key, sizeof (uint64_t));
2238 struct GNUNET_PeerIdentity curr_dest;
2239 struct GNUNET_PeerIdentity curr_src;
2240 memcpy (&curr_dest, ¤t_destination, sizeof (struct GNUNET_PeerIdentity));
2241 memcpy (&curr_src, ¤t_source, sizeof (struct GNUNET_PeerIdentity));
2242 next_hop = find_successor (key_value, &curr_dest, &curr_src, NULL);
2243 /* FIXME: I am copying back current_destination and current_source. but I am not
2244 sure, if its correct. I am doing so just to remove the code from client file.*/
2245 memcpy (¤t_destination, &curr_dest, sizeof (struct GNUNET_PeerIdentity));
2246 memcpy (¤t_source, &curr_src, sizeof (struct GNUNET_PeerIdentity));
2248 if (NULL == next_hop) /* I am the destination do datacache_put */
2250 GDS_DATACACHE_handle_put (expiration_time, key, put_path_length, put_path,
2251 block_type, data_size, data);
2255 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2258 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2259 pending->timeout = expiration_time;
2260 ppm = (struct PeerPutMessage *) &pending[1];
2261 pending->msg = &ppm->header;
2262 ppm->header.size = htons (msize);
2263 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
2264 ppm->options = htonl (options);
2265 ppm->block_type = htonl (block_type);
2266 ppm->hop_count = htonl (hop_count + 1);
2267 ppm->desired_replication_level = htonl (desired_replication_level);
2268 ppm->put_path_length = htonl (put_path_length);
2269 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2271 ppm->current_destination = current_destination;
2272 ppm->current_source = current_source;
2274 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2275 if (put_path_length != 0)
2277 memcpy (pp, put_path,
2278 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2280 memcpy (&pp[put_path_length], data, data_size);
2281 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2282 target_friend->pending_count++;
2283 process_friend_queue (target_friend);
2288 /** FIXME: by default I keep current_source, and destination as my own id.
2289 * in case we find a finger then we update current_source in the
2290 * find_successor message.
2291 * Construct a Get message and send it to target_peer.
2292 * @param key Key for the content
2293 * @param block_type Type of the block
2294 * @param options Routing options
2295 * @param desired_replication_level Desired replication count
2296 * @param expiration_time When does the content expire
2297 * @param current_destination
2298 * @param current_source
2299 * @param target_peer Peer to which this message will be forwarded.
2300 * @param hop_count Number of hops traversed so far.
2301 * @param put_path_length Total number of peers in @a put_path
2302 * @param put_path Number of peers traversed so far
2305 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2306 enum GNUNET_BLOCK_Type block_type,
2307 enum GNUNET_DHT_RouteOption options,
2308 uint32_t desired_replication_level,
2309 struct GNUNET_PeerIdentity current_destination,
2310 struct GNUNET_PeerIdentity current_source,
2311 struct GNUNET_PeerIdentity *target_peer,
2313 uint32_t get_path_length,
2314 struct GNUNET_PeerIdentity *get_path)
2316 struct PeerGetMessage *pgm;
2317 struct P2PPendingMessage *pending;
2318 struct FriendInfo *target_friend;
2319 struct GNUNET_PeerIdentity *gp;
2322 msize = sizeof (struct PeerGetMessage) +
2323 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2325 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2331 if (NULL == target_peer)
2333 /* This is the first call from client file, we need to search for next_hop*/
2334 struct GNUNET_PeerIdentity *next_hop;
2336 struct GNUNET_PeerIdentity curr_dest;
2337 struct GNUNET_PeerIdentity curr_src;
2338 memcpy (&curr_dest, ¤t_destination, sizeof (struct GNUNET_PeerIdentity));
2339 memcpy (&curr_src, ¤t_source, sizeof (struct GNUNET_PeerIdentity));
2340 memcpy (&key_value, key, sizeof (struct GNUNET_PeerIdentity));
2341 next_hop = find_successor (key_value, &curr_dest, &curr_src, NULL);
2342 /* FIXME: Again I am copying back value of current_destination, current_source,
2343 Think of a better solution. */
2344 memcpy (¤t_destination, &curr_dest, sizeof (struct GNUNET_PeerIdentity));
2345 memcpy (¤t_source, &curr_src, sizeof (struct GNUNET_PeerIdentity));
2346 if (NULL == next_hop) /* I am the destination do datacache_put */
2348 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2349 NULL, 0, 1, &my_identity, NULL,&my_identity);
2354 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2358 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2359 pending->importance = 0; /* FIXME */
2360 pgm = (struct PeerGetMessage *) &pending[1];
2361 pending->msg = &pgm->header;
2362 pgm->header.size = htons (msize);
2363 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
2364 pgm->get_path_length = htonl (get_path_length);
2366 pgm->current_destination = current_destination;
2367 pgm->current_source = current_source;
2368 pgm->hop_count = htonl (hop_count + 1);
2370 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2371 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2372 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2373 target_friend->pending_count++;
2374 process_friend_queue (target_friend);
2379 * Send the get result to requesting client.
2380 * @param expiration When will this result expire?
2381 * @param key Key of the requested data.
2382 * @param put_path_length Number of peers in @a put_path
2383 * @param put_path Path taken to put the data at its stored location.
2384 * @param type Block type
2385 * @param data_size Size of the @a data
2386 * @param data Payload to store
2387 * @param get_path Path taken to reach to the location of the key.
2388 * @param get_path_length Number of peers in @a get_path
2389 * @param next_hop Next peer to forward the message to.
2390 * @param source_peer Peer which has the data for the key.
2393 GDS_NEIGHBOURS_send_get_result (struct GNUNET_TIME_Absolute expiration,
2394 const struct GNUNET_HashCode *key,
2395 unsigned int put_path_length,
2396 const struct GNUNET_PeerIdentity *put_path,
2397 enum GNUNET_BLOCK_Type type, size_t data_size,
2399 struct GNUNET_PeerIdentity *get_path,
2400 unsigned int get_path_length,
2401 struct GNUNET_PeerIdentity *next_hop,
2402 struct GNUNET_PeerIdentity *source_peer)
2404 struct PeerGetResultMessage *get_result;
2405 struct GNUNET_PeerIdentity *get_result_path;
2406 struct GNUNET_PeerIdentity *pp;
2407 struct P2PPendingMessage *pending;
2408 struct FriendInfo *target_friend;
2409 int current_path_index;
2412 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2413 sizeof (struct PeerPutMessage);
2415 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2421 current_path_index = search_my_index(get_path, get_path_length);
2422 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
2423 if (0 == current_path_index)
2425 GDS_CLIENTS_handle_reply (expiration, key, get_path_length, get_path, put_path_length,
2426 put_path, type, data_size, data);
2429 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2430 pending->importance = 0;
2431 get_result = (struct PeerGetResultMessage *)&pending[1];
2432 pending->msg = &get_result->header;
2433 get_result->header.size = htons (msize);
2434 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2435 get_result->key = *key;
2436 memcpy (&(get_result->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2437 get_result->expiration_time = expiration;
2439 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2440 memcpy (get_result_path, get_path,
2441 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2442 memcpy (&get_result_path[get_path_length], data, data_size);
2443 /* FIXME: Is this correct? */
2444 pp = (struct GNUNET_PeerIdentity *)&get_result_path[1];
2445 memcpy (pp, put_path,sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2447 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2448 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2449 target_friend->pending_count++;
2450 process_friend_queue (target_friend);
2455 * Send tral rejection message to the peer which sent me a trail setup message.
2456 * @param source_peer Source peer which wants to set up the trail.
2457 * @param finger_identity Value whose successor will be the finger of @a source_peer.
2458 * @param congested_peer Peer which has send trail rejection message.
2459 * @param next_hop Peer to which this message should be forwarded.
2460 * @param finger_map_index Index in @a source_peer finger peermap.
2461 * @param trail_peer_list Trail followed to reach from @a source_peer to next_hop,
2462 * NULL, in case the @a congested_peer was the first peer
2463 * to which trail setup message was forwarded.
2464 * @param trail_length Number of peers in trail_peer_list.
2467 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity *source_peer,
2468 uint64_t finger_identity,
2469 struct GNUNET_PeerIdentity *congested_peer,
2470 const struct GNUNET_PeerIdentity *next_hop,
2471 unsigned int finger_map_index,
2472 struct GNUNET_PeerIdentity *trail_peer_list,
2473 unsigned int trail_length)
2475 struct PeerTrailRejectionMessage *trail_rejection;
2476 struct GNUNET_PeerIdentity *trail_list;
2477 struct P2PPendingMessage *pending;
2478 struct FriendInfo *target_friend;
2481 msize = trail_length * sizeof(struct GNUNET_PeerIdentity) +
2482 sizeof (struct PeerTrailRejectionMessage);
2484 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2490 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2491 pending->importance = 0;
2492 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2493 trail_rejection = (struct PeerTrailRejectionMessage *) &pending[1];
2494 pending->msg = &trail_rejection->header;
2495 trail_rejection->header.size = htons (msize);
2496 trail_rejection->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
2497 memcpy (&(trail_rejection->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2498 memcpy (&(trail_rejection->congested_peer), congested_peer, sizeof (struct GNUNET_PeerIdentity));
2499 memcpy (&(trail_rejection->finger_identity_value), &finger_identity, sizeof (uint64_t));
2500 trail_rejection->finger_map_index = htonl(finger_map_index);
2501 trail_rejection->trail_length = htonl (trail_length);
2503 trail_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
2504 if (trail_length != 0)
2505 memcpy (trail_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2507 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2508 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2509 target_friend->pending_count++;
2510 process_friend_queue (target_friend);
2515 * Core handler for P2P put messages.
2516 * @param cls closure
2517 * @param peer sender of the request
2518 * @param message message
2519 * @return #GNUNET_OK to keep the connection open,
2520 * #GNUNET_SYSERR to close it (signal serious error)
2523 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2524 const struct GNUNET_MessageHeader *message)
2526 struct PeerPutMessage *put;
2527 struct GNUNET_PeerIdentity *put_path;
2528 struct GNUNET_HashCode test_key;
2529 enum GNUNET_DHT_RouteOption options;
2530 struct GNUNET_PeerIdentity current_destination;
2531 struct GNUNET_PeerIdentity current_source;
2532 struct GNUNET_PeerIdentity *next_hop;
2536 size_t payload_size;
2539 msize = ntohs (message->size);
2540 if (msize < sizeof (struct PeerPutMessage))
2542 GNUNET_break_op (0);
2546 put = (struct PeerPutMessage *) message;
2547 putlen = ntohl (put->put_path_length);
2550 sizeof (struct PeerPutMessage) +
2551 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2553 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2555 GNUNET_break_op (0);
2559 current_destination = put->current_destination;
2560 current_source = put->current_source;
2561 put_path = (struct GNUNET_PeerIdentity *) &put[1];
2562 payload = &put_path[putlen];
2563 options = ntohl (put->options);
2564 payload_size = msize - (sizeof (struct PeerPutMessage) +
2565 putlen * sizeof (struct GNUNET_PeerIdentity));
2567 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
2568 payload, payload_size, &test_key))
2571 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
2573 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
2574 GNUNET_break_op (0);
2575 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2576 "PUT with key `%s' for block with key %s\n",
2577 put_s, GNUNET_h2s_full (&test_key));
2578 GNUNET_free (put_s);
2583 GNUNET_break_op (0);
2586 /* cannot verify, good luck */
2590 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
2592 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
2593 ntohl (put->block_type),
2595 NULL, 0, /* bloom filer */
2596 NULL, 0, /* xquery */
2597 payload, payload_size))
2599 case GNUNET_BLOCK_EVALUATION_OK_MORE:
2600 case GNUNET_BLOCK_EVALUATION_OK_LAST:
2603 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
2604 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
2605 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
2606 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
2607 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
2608 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
2610 GNUNET_break_op (0);
2615 struct GNUNET_PeerIdentity pp[putlen + 1];
2616 /* extend 'put path' by sender */
2617 /* FIXME: Check what are we doing here? */
2618 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
2620 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
2627 memcpy (&key_value, &(put->key), sizeof (uint64_t));
2628 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2630 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2631 if (next_hop == NULL)
2633 /* refer to handle_dht_p2p_trail_setup. */
2638 next_hop = find_successor (key_value, ¤t_destination, ¤t_source, NULL);
2641 if (NULL == next_hop) /* I am the final destination */
2643 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
2644 &(put->key),putlen, pp, ntohl (put->block_type),
2645 payload_size, payload);
2650 GDS_CLIENTS_process_put (options,
2651 ntohl (put->block_type),
2652 ntohl (put->hop_count),
2653 ntohl (put->desired_replication_level),
2655 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2660 GDS_NEIGHBOURS_send_put (&put->key, payload, payload_size,
2661 ntohl (put->block_type),ntohl (put->options),
2662 ntohl (put->desired_replication_level),
2663 GNUNET_TIME_absolute_ntoh (put->expiration_time),
2664 current_destination, current_source, next_hop,
2665 ntohl (put->hop_count), putlen, pp);
2669 return GNUNET_SYSERR;
2674 * Core handler for p2p get requests.
2676 * @param cls closure
2677 * @param peer sender of the request
2678 * @param message message
2679 * @return #GNUNET_OK to keep the connection open,
2680 * #GNUNET_SYSERR to close it (signal serious error)
2683 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
2684 const struct GNUNET_MessageHeader *message)
2686 struct PeerGetMessage *get;
2687 struct GNUNET_PeerIdentity *get_path;
2688 struct GNUNET_PeerIdentity current_destination;
2689 struct GNUNET_PeerIdentity current_source;
2690 struct GNUNET_PeerIdentity *next_hop;
2691 uint32_t get_length;
2695 msize = ntohs (message->size);
2696 if (msize < sizeof (struct PeerGetMessage))
2698 GNUNET_break_op (0);
2702 get = (struct PeerGetMessage *)message;
2703 get_length = ntohl (get->get_path_length);
2704 get_path = (struct GNUNET_PeerIdentity *)&get[1];
2705 current_destination = get->current_destination;
2706 current_source = get->current_source;
2709 sizeof (struct PeerGetMessage) +
2710 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
2712 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2714 GNUNET_break_op (0);
2718 /* Add sender to get path */
2719 struct GNUNET_PeerIdentity gp[get_length + 1];
2720 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
2721 gp[get_length + 1] = *peer;
2722 get_length = get_length + 1;
2724 memcpy (&key_value, &(get->key), sizeof (uint64_t));
2725 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2727 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2728 if (next_hop == NULL)
2730 /* refer to handle_dht_p2p_trail_setup. */
2735 next_hop = find_successor (key_value, ¤t_destination, ¤t_source, NULL);
2738 if (NULL == next_hop)
2740 /* FIXME: Try to make this code also short and remove useless variables. */
2741 struct GNUNET_PeerIdentity final_get_path[get_length+1];
2742 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
2743 memcpy (&final_get_path[get_length+1], &my_identity, sizeof (struct GNUNET_PeerIdentity));
2744 get_length = get_length + 1;
2745 struct GNUNET_PeerIdentity *next_hop;
2746 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2747 memcpy (next_hop, &final_get_path[get_length-2], sizeof (struct GNUNET_PeerIdentity));
2748 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
2749 get_length, final_get_path,next_hop, &my_identity);
2755 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
2756 get->desired_replication_level,current_destination,
2757 current_source, next_hop, 0,
2760 return GNUNET_SYSERR;
2766 * Core handler for get result
2767 * @param cls closure
2768 * @param peer sender of the request
2769 * @param message message
2770 * @return #GNUNET_OK to keep the connection open,
2771 * #GNUNET_SYSERR to close it (signal serious error)
2774 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
2775 const struct GNUNET_MessageHeader *message)
2777 /* If you are the source, go back to the client file and there search for
2778 the requesting client and send back the result. */
2779 struct PeerGetResultMessage *get_result;
2780 struct GNUNET_PeerIdentity *get_path;
2781 struct GNUNET_PeerIdentity *put_path;
2783 size_t payload_size;
2785 unsigned int getlen;
2786 unsigned int putlen;
2787 int current_path_index;
2789 msize = ntohs (message->size);
2790 if (msize < sizeof (struct PeerGetResultMessage))
2792 GNUNET_break_op (0);
2796 get_result = (struct PeerGetResultMessage *)message;
2797 getlen = ntohl (get_result->get_path_length);
2798 putlen = ntohl (get_result->put_path_length);
2801 sizeof (struct PeerGetResultMessage) +
2802 getlen * sizeof (struct GNUNET_PeerIdentity) +
2803 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
2805 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
2807 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
2809 GNUNET_break_op (0);
2813 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
2814 payload = &get_path[getlen];
2815 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
2816 getlen * sizeof (struct GNUNET_PeerIdentity));
2817 /* FIXME: Check if its correct or not. */
2820 put_path = &get_path[1];
2824 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
2826 //GDS_CLIENTS_process_get_result();
2827 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
2828 getlen, get_path, putlen,
2829 put_path, get_result->type, payload_size, payload);
2834 struct GNUNET_PeerIdentity *next_hop;
2835 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2836 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
2837 current_path_index = search_my_index (get_path, getlen);
2838 /* FIXME: First check if you are adding yourself to the get path or not.
2839 if yes then don't check if current_path_index == 0, if not then check
2840 and next_hop == source_peer. */
2841 memcpy (next_hop, &get_path[current_path_index - 1], sizeof (struct GNUNET_PeerIdentity));
2843 GDS_NEIGHBOURS_send_get_result (get_result->expiration_time, &(get_result->key),
2845 get_result->type, payload_size,payload,
2847 next_hop, &(get_result->source_peer));
2850 return GNUNET_SYSERR;
2855 * Core handle for PeerTrailSetupMessage.
2856 * @param cls closure
2857 * @param message message
2858 * @param peer peer identity this notification is about
2859 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2862 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
2863 const struct GNUNET_MessageHeader *message)
2865 const struct PeerTrailSetupMessage *trail_setup;
2866 struct GNUNET_PeerIdentity current_destination;
2867 struct GNUNET_PeerIdentity current_source;
2868 struct GNUNET_PeerIdentity source;
2869 struct GNUNET_PeerIdentity *next_hop;
2870 struct GNUNET_PeerIdentity next_peer;
2871 struct GNUNET_PeerIdentity *trail_peer_list;
2872 struct FriendInfo *target_friend;
2873 uint64_t destination_finger_value;
2874 uint32_t trail_length;
2875 uint32_t finger_map_index;
2878 msize = ntohs (message->size);
2879 if (msize < sizeof (struct PeerTrailSetupMessage))
2881 GNUNET_break_op (0);
2885 trail_setup = (const struct PeerTrailSetupMessage *) message;
2886 trail_length = ntohl (trail_setup->trail_length);
2888 if ((msize < sizeof (struct PeerTrailSetupMessage) +
2889 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2891 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2893 GNUNET_break_op (0);
2897 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
2898 current_destination = trail_setup->current_destination;
2899 current_source = trail_setup->current_source;
2900 source = trail_setup->source_peer;
2901 finger_map_index = ntohl (trail_setup->finger_map_index);
2902 destination_finger_value = ntohl (trail_setup->destination_finger);
2904 /* My routing state size has crossed the threshold, I can not be part of any more
2906 if(GDS_ROUTING_check_threshold())
2908 /* No more trails possible through me. send a trail rejection message. */
2909 GDS_NEIGHBOURS_send_trail_rejection (&source, destination_finger_value, &my_identity,
2910 peer,finger_map_index, trail_peer_list,trail_length);
2914 /* Check if you are current_destination or not. */
2915 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_destination, &my_identity)))
2917 /* You are not current_destination, you are part of trail to reach to
2918 current_destination. */
2919 next_hop = GDS_ROUTING_search (¤t_source, ¤t_destination, peer);
2920 /* ADDNOW: OPTIMIZATION: do find_successor also and get a better path if possible. */
2922 if (next_hop == NULL)
2925 * next_hop is NULL, in a case when next_hop was a friend which got disconnected
2926 * and we removed the trail from our routing trail. So, I can send the message
2927 * to other peer or can drop the message. VERIFY which will be the correct
2929 * next_hop to NULL, 1. statistics update, drop the message.
2930 2. complain to sender with new message: trail lost */
2936 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source, NULL);
2940 if (NULL == next_hop) /* This means I am the final destination */
2942 /* SUPU: trail length is 0, when I am the friend of the srouce peer. */
2943 if (trail_length == 0)
2945 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
2949 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
2952 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
2954 if (compare_predecessor (&source) /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */)
2956 /* FIXME: In case we have different function update_predecessor then
2957 remove the lines below. */
2958 struct GNUNET_PeerIdentity *new_trail_list;
2959 new_trail_list = invert_trail_list (&source, trail_peer_list, trail_length);
2960 finger_table_add (&source, new_trail_list, trail_length, PREDECESSOR_FINGER_ID);
2962 GDS_NEIGHBOURS_send_trail_setup_result (&source,
2964 target_friend, trail_length,
2971 /* Now add yourself to the trail. */
2972 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
2973 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2974 peer_list[trail_length] = my_identity;
2977 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2978 GDS_NEIGHBOURS_send_trail_setup (&source,
2979 destination_finger_value,
2980 ¤t_destination, ¤t_source,
2981 target_friend, trail_length, peer_list,
2985 return GNUNET_SYSERR;
2990 * Core handle for p2p trail construction result messages.
2992 * @param message message
2993 * @param peer peer identity this notification is about
2994 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2997 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2998 const struct GNUNET_MessageHeader *message)
3000 const struct PeerTrailSetupResultMessage *trail_result;
3001 struct GNUNET_PeerIdentity *trail_peer_list;
3002 uint32_t trail_length;
3003 uint32_t finger_map_index;
3006 msize = ntohs (message->size);
3007 if (msize < sizeof (struct PeerTrailSetupResultMessage))
3009 GNUNET_break_op (0);
3013 trail_result = (const struct PeerTrailSetupResultMessage *) message;
3014 trail_length = ntohl (trail_result->trail_length);
3017 sizeof (struct PeerTrailSetupResultMessage) +
3018 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3020 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3022 GNUNET_break_op (0);
3026 finger_map_index = htonl (trail_result->finger_map_index);
3027 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
3029 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3032 finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length,
3038 struct GNUNET_PeerIdentity next_hop;
3039 struct FriendInfo *target_friend;
3042 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
3043 /* FIXME: Make sure you are passing the current length */
3044 my_index = search_my_index (trail_peer_list, trail_length);
3047 next_hop = trail_result->destination_peer;
3050 next_hop = trail_peer_list[my_index - 1];
3052 /* Finger table of destination peer will not contain any trail for the case
3053 * where destination peer is its own finger identity. */
3054 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
3055 &(trail_result->finger_identity))))
3057 GDS_ROUTING_add (&(trail_result->destination_peer), &(trail_result->finger_identity),
3061 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3062 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
3063 &(trail_result->finger_identity),
3064 target_friend, trail_length,
3069 return GNUNET_SYSERR;
3074 * FIXME: Use flag in the case finger peer map does not contain predcessor
3075 * then its NULL. Ideally it should never happen. Some one sent you are verify
3076 * successor and you don't have any predecessor, then ideally you should
3077 * GNUNET_break_op(0).
3078 * Get my current predecessor from the finger peer map
3079 * @return Current predecessor.
3081 static struct FingerInfo *
3084 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
3085 struct GNUNET_PeerIdentity key_ret;
3086 unsigned int finger_index;
3087 struct FingerInfo *my_predecessor;
3089 /* Iterate over finger peer map and extract your predecessor. */
3090 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
3091 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
3093 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
3094 (finger_iter,&key_ret,(const void **)&my_predecessor))
3096 if(1 == my_predecessor->finger_map_index)
3102 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
3103 return my_predecessor;
3108 * Core handle for p2p verify successor messages.
3109 * @param cls closure
3110 * @param message message
3111 * @param peer peer identity this notification is about
3112 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3115 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3116 const struct GNUNET_MessageHeader *message)
3118 const struct PeerVerifySuccessorMessage *vsm;
3119 const struct GNUNET_PeerIdentity *trail_peer_list;
3120 struct GNUNET_PeerIdentity source_peer;
3121 struct GNUNET_PeerIdentity next_hop;
3122 struct FriendInfo *target_friend;
3124 uint32_t trail_length;
3126 msize = ntohs (message->size);
3127 if (msize < sizeof (struct PeerVerifySuccessorMessage))
3129 GNUNET_break_op (0);
3133 vsm = (struct PeerVerifySuccessorMessage *) message;
3134 trail_length = ntohl (vsm->trail_length);
3136 if ((msize < sizeof (struct PeerVerifySuccessorMessage) +
3137 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3138 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3140 GNUNET_break_op (0);
3144 trail_peer_list = (const struct GNUNET_PeerIdentity *)&vsm[1];
3145 memcpy (&source_peer, &(vsm->source_peer), sizeof(struct GNUNET_PeerIdentity));
3146 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity)))
3148 struct FingerInfo *my_predecessor;
3150 if (trail_length == 0)
3151 memcpy (&next_hop, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3154 int current_trail_index;
3155 current_trail_index = search_my_index (trail_peer_list, trail_length);
3156 memcpy (&next_hop, &trail_peer_list[current_trail_index-1], sizeof (struct GNUNET_PeerIdentity));
3158 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3160 my_predecessor = get_predecessor();
3161 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
3162 &(my_predecessor->finger_identity))))
3165 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3167 &(my_predecessor->finger_identity),
3174 struct GNUNET_PeerIdentity *new_successor_trail;
3175 struct TrailPeerList *iterator;
3176 int new_trail_length;
3179 new_trail_length = trail_length + my_predecessor->trail_length + 1;
3180 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * new_trail_length);
3181 memcpy (new_successor_trail, trail_peer_list, (trail_length) * sizeof (struct GNUNET_PeerIdentity));
3182 memcpy (&new_successor_trail[trail_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3184 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
3185 iterator = my_predecessor->head;
3186 i = trail_length + 1;
3187 while (i < new_trail_length)
3189 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
3190 iterator = iterator->next;
3194 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3196 &(my_predecessor->finger_identity),
3198 new_successor_trail,
3206 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
3207 /* FIXME: make sure you are passing the correct trail length */
3208 my_index = search_my_index (trail_peer_list, trail_length);
3209 memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
3210 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3212 GDS_NEIGHBOURS_send_verify_successor (&(vsm->source_peer), &(vsm->successor),target_friend,
3213 trail_peer_list, trail_length);
3215 return GNUNET_SYSERR;
3220 * Core handle for p2p verify successor result messages.
3221 * @param cls closure
3222 * @param message message
3223 * @param peer peer identity this notification is about
3224 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3227 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3228 const struct GNUNET_MessageHeader *message)
3230 const struct PeerVerifySuccessorResultMessage *vsrm;
3231 struct GNUNET_PeerIdentity *trail_peer_list;
3232 struct GNUNET_PeerIdentity next_hop;
3233 struct FriendInfo *target_friend;
3235 uint32_t trail_length;
3237 msize = ntohs (message->size);
3238 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
3240 GNUNET_break_op (0);
3244 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
3245 trail_length = ntohl (vsrm->trail_length);
3248 sizeof (struct PeerVerifySuccessorResultMessage) +
3249 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3251 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3253 GNUNET_break_op (0);
3257 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
3259 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), &(my_identity))))
3261 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), &(my_identity))))
3263 finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0);
3264 memcpy (&next_hop, &trail_peer_list[0], sizeof (struct GNUNET_PeerIdentity));
3265 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3266 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
3267 target_friend, trail_peer_list,
3275 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
3276 /* FIXME: make sure you are passing the correct trail length */
3277 my_index = search_my_index (trail_peer_list, trail_length);
3279 memcpy (&next_hop, &(vsrm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
3281 memcpy (&next_hop, &trail_peer_list[my_index-1], sizeof (struct GNUNET_PeerIdentity));
3282 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3283 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
3284 &(vsrm->source_successor),
3285 &(vsrm->my_predecessor),
3291 return GNUNET_SYSERR;
3296 * Core handle for p2p notify new successor messages.
3297 * @param cls closure
3298 * @param message message
3299 * @param peer peer identity this notification is about
3300 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3303 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3304 const struct GNUNET_MessageHeader *message)
3306 const struct PeerNotifyNewSuccessorMessage *nsm;
3307 struct GNUNET_PeerIdentity *trail_peer_list;
3309 uint32_t trail_length;
3311 msize = ntohs (message->size);
3312 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
3314 GNUNET_break_op (0);
3318 nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
3319 trail_length = ntohl (nsm->trail_length);
3321 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) +
3322 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3324 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3326 GNUNET_break_op (0);
3330 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
3332 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer), &my_identity)))
3334 //update_predecessor (&(nsm->destination_peer), trail_peer_list);
3339 struct FriendInfo *target_friend;
3340 struct GNUNET_PeerIdentity next_hop;
3343 /* FIXME: handle the case when current_path_index = GNUNET_SYSERR;*/
3344 /* FIXME: check that trail length is correct. */
3345 my_index = search_my_index (trail_peer_list, trail_length);
3346 memcpy (&next_hop, &trail_peer_list[my_index+1], sizeof (struct GNUNET_PeerIdentity));
3347 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3348 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
3349 &(nsm->destination_peer),
3350 target_friend, trail_peer_list,
3354 return GNUNET_SYSERR;
3359 * Core handler for P2P trail rejection message
3360 * @param cls closure
3361 * @param message message
3362 * @param peer peer identity this notification is about
3363 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3366 int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3367 const struct GNUNET_MessageHeader *message)
3369 /* Here you have recevied the message it means that the peer next to you have
3370 failed to setup the trail to the finger identity value. now you should call
3371 find_successor and make sure that you don't choose the peer as next hop
3372 in order to do so, you need to pass a new parameter to find successor,
3373 congested peer - a peer which you should ignore. once you have found this
3374 peer then just send a trail setup message to that peer. In case you are
3375 also congested then remove yourself from the trail as this message
3376 reached to as you are part of the trail. and then send the message to
3377 element before you. Ideally you should be the last element in the trail as
3378 all the the elements before you have rejected you. In case you are source,
3379 then you should call select_random_Friend(congested_peer). in case you don't
3380 find any peer because congested peer then set flag that all friends are busy
3382 const struct PeerTrailRejectionMessage *trail_rejection;
3383 struct GNUNET_PeerIdentity *trail_peer_list;
3384 struct GNUNET_PeerIdentity source_peer;
3385 struct GNUNET_PeerIdentity congested_peer;
3386 struct FriendInfo *target_friend;
3387 struct GNUNET_PeerIdentity next_peer;
3388 struct GNUNET_PeerIdentity *next_hop;
3389 struct GNUNET_PeerIdentity current_source;
3390 struct GNUNET_PeerIdentity current_destination;
3392 uint32_t trail_length;
3393 uint32_t finger_map_index;
3394 uint64_t destination_finger_value;
3396 msize = ntohs (message->size);
3397 if (msize < sizeof (struct PeerTrailRejectionMessage))
3399 GNUNET_break_op (0);
3403 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3404 trail_length = ntohl (trail_rejection->trail_length);
3406 if ((msize < sizeof (struct PeerTrailRejectionMessage) +
3407 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3409 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3411 GNUNET_break_op (0);
3414 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3415 finger_map_index = ntohl (trail_rejection->finger_map_index);
3416 memcpy (&source_peer, &(trail_rejection->source_peer), sizeof(struct GNUNET_PeerIdentity));
3417 memcpy (&destination_finger_value, &(trail_rejection->finger_identity_value), sizeof (uint64_t));
3418 memcpy (&congested_peer, &(trail_rejection->congested_peer), sizeof (struct GNUNET_PeerIdentity));
3420 /* If I am the source of the original trail setup message, then again select
3421 a random friend and send a new trail setup message to this finger identity
3423 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source_peer)))
3425 /* If friend peer map is empty, or all the friends trail threshold has been crossed,
3427 if ((GNUNET_CONTAINER_multipeermap_size (friend_peermap) == 0) ||
3428 (all_friends_trail_threshold == GNUNET_YES))
3431 return GNUNET_SYSERR;
3434 /* Select any random friend except congested peer. */
3435 target_friend = select_random_friend (&congested_peer);
3437 if (NULL == target_friend)
3439 all_friends_trail_threshold = GNUNET_YES;
3440 return GNUNET_SYSERR;
3443 GDS_NEIGHBOURS_send_trail_setup (&my_identity, destination_finger_value, &(target_friend->id),
3444 &my_identity, target_friend, 0, NULL, finger_map_index);
3448 /* My routing state size has crossed the threshold, I can not be part of any more
3450 if(GDS_ROUTING_check_threshold())
3452 struct GNUNET_PeerIdentity *new_trail;
3454 if (trail_length == 1)
3456 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3460 memcpy (&next_peer, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity));
3463 /* Remove myself from the trail. */
3464 new_trail = GNUNET_malloc ((trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3465 memcpy (new_trail, trail_peer_list, (trail_length -1) * sizeof (struct GNUNET_PeerIdentity));
3467 /* No more trails possible through me. send a trail rejection message to next hop. */
3468 GDS_NEIGHBOURS_send_trail_rejection (&source_peer, destination_finger_value, &my_identity,
3469 &next_peer,finger_map_index, new_trail,trail_length - 1);
3473 /* FIXME: In this case I have just written my_identity as current_destination
3474 and current source need ot think more of better values anad if needed or not.
3475 Also, i am adding a new parameter to funciton find_successor so that this peer
3476 is not considered as next hop congested_peer is not being used. FIXME. */
3477 memcpy (¤t_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
3478 memcpy (¤t_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
3479 next_hop = find_successor (destination_finger_value, ¤t_destination, ¤t_source, &congested_peer);
3481 /* FIXME: WE NEED ANOTHER CASE as it may happend that congested peer is the only
3482 friend, and find_successor finds nothig, so check something else
3483 here like if current_destination is me, it means that i am destination
3484 or if current_destination = NULL, then it means found nothing. URGENT. */
3485 if (NULL == next_hop) /* This means I am the final destination */
3487 /* SUPU: trail length is 1, when I am the friend of the srouce peer. */
3488 if (trail_length == 1)
3490 memcpy (&next_peer, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3494 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3497 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3499 if (compare_predecessor (&source_peer) /* ! HAVE A PREDECESSOR || (source_peer closer than existing PREDECESOR) */)
3501 /* FIXME: In case we have different function update_predecessor then
3502 remove the lines below. */
3503 struct GNUNET_PeerIdentity *new_trail_list;
3504 new_trail_list = invert_trail_list (&source_peer, trail_peer_list, trail_length);
3505 finger_table_add (&source_peer, new_trail_list, trail_length, PREDECESSOR_FINGER_ID);
3507 GDS_NEIGHBOURS_send_trail_setup_result (&source_peer,
3509 target_friend, trail_length,
3516 /* Now add yourself to the trail. */
3517 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3518 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3519 peer_list[trail_length] = my_identity;
3522 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3523 GDS_NEIGHBOURS_send_trail_setup (&source_peer,
3524 destination_finger_value,
3525 ¤t_destination, ¤t_source,
3526 target_friend, trail_length, peer_list,
3530 return GNUNET_SYSERR;
3536 * Does it matter if the packet was going to a finger or friend?
3537 * Core handle for p2p trail rejection messages.
3538 * @param cls closure
3539 * @param message message
3540 * @param peer peer identity this notification is about
3541 * @return GNUNET_OK on success, GNUNET_SYSERR on error
3544 int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3545 const struct GNUNET_MessageHeader *message)
3547 struct PeerTrailRejectionMessage *trail_rejection;
3548 struct FriendInfo *target_friend;
3549 struct GNUNET_PeerIdentity *trail_peer_list;
3550 unsigned int finger_map_index;
3551 uint32_t trail_length;
3554 msize = ntohs (message->size);
3555 if (msize < sizeof (struct PeerTrailRejectionMessage))
3557 GNUNET_break_op (0);
3561 trail_rejection = (struct PeerTrailRejectionMessage *) message;
3562 trail_length = ntohl (trail_rejection->trail_length);
3564 if ((msize < sizeof (struct PeerTrailRejectionMessage) +
3565 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3567 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3569 GNUNET_break_op (0);
3572 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
3573 finger_map_index = ntohl (trail_rejection->finger_map_index);
3575 /* FIXME: I don't think we need failed trail list. will remove it once sure.
3576 * only case where I think we can need it in if in case of finger. where
3577 * we would like to send back the message to current source and leave it
3578 * to the current source to find the closest peer.
3579 trail_fail = GNUNET_malloc (sizeof (struct FailedTrail));
3580 memcpy (&(trail_fail->source_peer), &(trail_rejection->source_peer), sizeof (struct GNUNET_PeerIdentity));
3581 memcpy (&(trail_fail->congested_peer), &(trail_rejection->congested_peer), sizeof (struct GNUNET_PeerIdentity));
3582 memcpy (&(trail_fail->destination_finger_value), &(trail_rejection->finger_identity), sizeof (uint64_t));
3584 GNUNET_assert (GNUNET_OK ==
3585 GNUNET_CONTAINER_multipeermap_put (failed_trail_list, &(trail_fail->source_peer),
3586 trail_fail, GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
3589 /* FIXME: Is it okay if I pass the struct as parameter. */
3590 target_friend = select_random_friend (&(trail_rejection->congested_peer));
3592 if(NULL != target_friend)
3594 GDS_NEIGHBOURS_send_trail_setup (&(trail_rejection->source_peer),
3595 trail_rejection->finger_identity,
3596 &(target_friend->id),
3597 NULL, target_friend, ntohl (trail_rejection->trail_length),
3602 return GNUNET_SYSERR;
3607 * Core handle for p2p trail tear down messages.
3608 * @param cls closure
3609 * @param message message
3610 * @param peer peer identity this notification is about
3611 * @return GNUNET_OK on success, GNUNET_SYSERR on error
3614 int handle_dht_p2p_trail_treadown (void *cls, const struct GNUNET_PeerIdentity *peer,
3615 const struct GNUNET_MessageHeader *message)
3617 /* Call is made to this function when the source peer removes an existing
3618 finger entry and it need to inform the peers which are part of the trail to remove
3619 the trail from their routing table. So, this peer should first
3620 get the next hop and then delete the entry. */
3621 struct PeerTrailTearDownMessage *trail_teardown;
3622 struct GNUNET_PeerIdentity *trail_peer_list;
3623 struct GNUNET_PeerIdentity next_hop;
3624 struct FriendInfo *target_friend;
3625 uint32_t trail_length;
3629 msize = ntohs (message->size);
3630 if (msize < sizeof (struct PeerTrailTearDownMessage))
3632 GNUNET_break_op (0);
3636 trail_teardown = (struct PeerTrailTearDownMessage *) message;
3637 trail_length = ntohl (trail_teardown->trail_length);
3639 if ((msize < sizeof (struct PeerTrailTearDownMessage) +
3640 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3642 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3644 GNUNET_break_op (0);
3648 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_teardown[1];
3650 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->destination_peer), &my_identity)))
3652 /* We have reached destination then just return. May be if the peer before this
3653 destination, does not forward the packet to destination. So, this case should never
3659 my_index = search_my_index (trail_peer_list, trail_length);
3660 if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer),
3661 &(trail_teardown->destination_peer),peer))
3663 /* Here we get GNUNET_NO, only if there is no matching entry found in routing
3669 if (my_index == (trail_length - 2))
3670 return GNUNET_SYSERR;
3672 memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
3673 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3675 GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer),
3676 &(trail_teardown->destination_peer),
3677 trail_peer_list, trail_length, target_friend);
3682 * Iterate over finger_peermap, and remove entries with peer as the first element
3684 * @param cls closure
3685 * @param key current public key
3686 * @param value value in the hash map
3687 * @return #GNUNET_YES if we should continue to
3689 * #GNUNET_NO if not.
3692 remove_matching_finger (void *cls,
3693 const struct GNUNET_PeerIdentity *key,
3696 struct FingerInfo *remove_finger = value;
3697 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
3699 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->head->peer, disconnected_peer))
3701 GNUNET_assert (GNUNET_YES ==
3702 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
3705 free_finger (remove_finger);
3712 * Method called whenever a peer disconnects.
3714 * @param cls closure
3715 * @param peer peer identity this notification is about
3718 handle_core_disconnect (void *cls,
3719 const struct GNUNET_PeerIdentity *peer)
3721 struct FriendInfo *remove_friend;
3723 /* Check for self message. */
3724 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
3727 /* Search for peer to remove in your friend_peermap. */
3729 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
3731 if (NULL == remove_friend)
3737 /* Remove fingers for which this peer is the first element in the trail. */
3738 GNUNET_CONTAINER_multipeermap_iterate (finger_peermap,
3739 &remove_matching_finger, (void *)peer);
3741 /* Remove routing trails of which this peer is a part. */
3742 GDS_ROUTING_remove_entry (peer);
3744 /* Remove the peer from friend_peermap. */
3745 GNUNET_assert (GNUNET_YES ==
3746 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
3750 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
3753 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3755 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3756 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3761 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
3763 GNUNET_SCHEDULER_cancel (verify_successor);
3764 verify_successor = GNUNET_SCHEDULER_NO_TASK;
3770 * Method called whenever a peer connects.
3772 * @param cls closure
3773 * @param peer_identity peer identity this notification is about
3776 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
3778 struct FriendInfo *friend;
3780 /* Check for connect to self message */
3781 if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
3784 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
3786 /* If peer already exists in our friend_peermap, then exit. */
3787 if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
3793 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
3796 friend = GNUNET_new (struct FriendInfo);
3797 friend->id = *peer_identity;
3799 GNUNET_assert (GNUNET_OK ==
3800 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
3801 peer_identity, friend,
3802 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
3804 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
3805 if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task)
3806 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
3811 * To be called on core init/fail.
3813 * @param cls service closure
3814 * @param identity the public identity of this peer
3817 core_init (void *cls,
3818 const struct GNUNET_PeerIdentity *identity)
3820 my_identity = *identity;
3825 * Initialize neighbours subsystem.
3826 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3829 GDS_NEIGHBOURS_init (void)
3831 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
3832 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
3833 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
3834 {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT, 0},
3835 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
3836 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
3837 {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
3838 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
3839 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
3840 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
3841 {&handle_dht_p2p_trail_treadown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
3846 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
3847 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
3848 GNUNET_NO, core_handlers);
3849 if (NULL == core_api)
3850 return GNUNET_SYSERR;
3852 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
3853 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS * 4/3, GNUNET_NO);
3855 /* FIXME: Not sure if this value is correct for this data structure. also
3856 * not sure if we actually need any such data structure. Once done with other functions,
3857 * will revisit this part.
3858 failed_trail_list = GNUNET_CONTAINER_multipeermap_create (LINK_THRESHOLD * 4/3, GNUNET_NO);*/
3859 /* This global variable is set to GNUNET_YES, in case all the friends have their
3860 links threshold set. */
3861 all_friends_trail_threshold = GNUNET_NO;
3867 * Shutdown neighbours subsystem.
3870 GDS_NEIGHBOURS_done (void)
3872 if (NULL == core_api)
3875 GNUNET_CORE_disconnect (core_api);
3878 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
3879 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
3880 friend_peermap = NULL;
3882 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
3883 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
3884 finger_peermap = NULL;
3886 /* FIXME: Here I have added GNUNET_break(0) as ideally if friend_peermap
3887 is already zero, then we really don't need to cancel it again. If this
3888 condition happens it mean we might have missed some corner case. */
3889 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
3892 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
3893 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
3896 if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
3899 GNUNET_SCHEDULER_cancel (verify_successor);
3900 verify_successor = GNUNET_SCHEDULER_NO_TASK;
3906 * FIXME: Here I want to send only the value not the address. Initially
3907 * I wanted to make it const struct * so that no other function can change it.
3908 * then in client file, i make a copy and send that copy. now I have made this
3912 * @return my identity
3914 struct GNUNET_PeerIdentity
3915 GDS_NEIGHBOURS_get_my_id (void)
3921 /* end of gnunet-service-xdht_neighbours.c */