2 This file is part of GNUnet.
3 (C) 2009-2013 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file dht/gnunet-service-xdht_neighbours.c
23 * @brief GNUnet DHT service's finger and friend table management code
24 * @author Supriti Singh
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_nse_service.h"
34 #include "gnunet_ats_service.h"
35 #include "gnunet_core_service.h"
36 #include "gnunet_datacache_lib.h"
37 #include "gnunet_transport_service.h"
38 #include "gnunet_hello_lib.h"
39 #include "gnunet_dht_service.h"
40 #include "gnunet_statistics_service.h"
41 #include "gnunet-service-xdht.h"
42 #include "gnunet-service-xdht_clients.h"
43 #include "gnunet-service-xdht_datacache.h"
44 #include "gnunet-service-xdht_hello.h"
45 #include "gnunet-service-xdht_neighbours.h"
46 #include "gnunet-service-xdht_nse.h"
47 #include "gnunet-service-xdht_routing.h"
53 * 1. Remove extra comments - FIXME,TODO,SUPU
57 * Maximum possible fingers of a peer.
59 #define MAX_FINGERS 256
62 * Maximum allowed number of pending messages per friend peer.
64 #define MAXIMUM_PENDING_PER_FRIEND 64
67 * How long at least to wait before sending another find finger trail request.
69 #define DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30)
72 * How long at most to wait before sending another find finger trail request.
74 #define DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 10)
77 GNUNET_NETWORK_STRUCT_BEGIN
80 * 1) Bloomfilter is not required for X-Vine.
81 * Keep the field now but remove it when implementing PUT/GET.
82 * 2) also, check the field of put/get/result if all are required for
91 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
93 struct GNUNET_MessageHeader header;
98 uint32_t options GNUNET_PACKED;
103 uint32_t type GNUNET_PACKED;
108 uint32_t hop_count GNUNET_PACKED;
111 * Replication level for this message
113 uint32_t desired_replication_level GNUNET_PACKED;
116 * Length of the PUT path that follows (if tracked).
118 uint32_t put_path_length GNUNET_PACKED;
121 * When does the content expire?
123 struct GNUNET_TIME_AbsoluteNBO expiration_time;
126 * Bloomfilter (for peer identities) to stop circular routes
128 char bloomfilter[DHT_BLOOM_SIZE];
131 * The key we are storing under.
133 struct GNUNET_HashCode key;
135 /* put path (if tracked) */
145 struct PeerResultMessage
148 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
150 struct GNUNET_MessageHeader header;
155 uint32_t type GNUNET_PACKED;
158 * Length of the PUT path that follows (if tracked).
160 uint32_t put_path_length GNUNET_PACKED;
163 * Length of the GET path that follows (if tracked).
165 uint32_t get_path_length GNUNET_PACKED;
168 * When does the content expire?
170 struct GNUNET_TIME_AbsoluteNBO expiration_time;
173 * The key of the corresponding GET request.
175 struct GNUNET_HashCode key;
177 /* put path (if tracked) */
179 /* get path (if tracked) */
189 struct PeerGetMessage
192 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
194 struct GNUNET_MessageHeader header;
199 uint32_t options GNUNET_PACKED;
202 * Desired content type.
204 uint32_t type GNUNET_PACKED;
209 uint32_t hop_count GNUNET_PACKED;
212 * Desired replication level for this request.
214 uint32_t desired_replication_level GNUNET_PACKED;
217 * Size of the extended query.
219 uint32_t xquery_size;
222 * Bloomfilter mutator.
227 * Bloomfilter (for peer identities) to stop circular routes
229 char bloomfilter[DHT_BLOOM_SIZE];
232 * The key we are looking for.
234 struct GNUNET_HashCode key;
240 * FIXME: I have defined this struct between GNUNET_NETWORK_STRUCT_BEGIN. Is
241 * it correct? Also, I am using the same struct inside finger info and trailsetup
242 * trailsetupresult message. Is it correct? Verify while testing. */
244 * Linked List of peers which are part of trail to reach a particular Finger.
249 * Pointer to next item in the list
251 struct TrailPeerList *next;
254 * Pointer to previous item in the list
256 struct TrailPeerList *prev;
259 * An element in this trail list
261 struct GNUNET_PeerIdentity *peer;
267 * FIXME : I am using the same struct TrailPeerList in both finger info
268 * and peertrailsetupmessage. Verify if its okay.
269 * P2P Trail setup message
271 struct PeerTrailSetupMessage
274 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
276 struct GNUNET_MessageHeader header;
279 * Source peer which wants to find trail to one of its finger.
281 struct GNUNET_PeerIdentity *source_peer;
284 * Finger id to which we want to set up the trail to.
286 struct GNUNET_PeerIdentity *destination_finger;
289 * This field contains the peer to which this packet is forwarded.
291 struct GNUNET_PeerIdentity *current_destination;
294 * Head of trail list.
296 struct TrailPeerList *head;
299 * Tail of trail list.
301 struct TrailPeerList *tail;
307 * P2P Trail setup Result message
309 struct PeerTrailSetupResultMessage
312 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_RESULT_SETUP
314 struct GNUNET_MessageHeader header;
317 * Finger to which we have found the path.
319 struct GNUNET_PeerIdentity *finger;
322 * Peer which was looking for the trail to finger.
324 struct GNUNET_PeerIdentity *destination_peer;
327 * This field contains the peer to which this packet is forwarded.
329 struct GNUNET_PeerIdentity *current_destination;
332 * Head of trail list.
334 struct TrailPeerList *head;
337 * Tail of trail list.
339 struct TrailPeerList *tail;
343 GNUNET_NETWORK_STRUCT_END
347 * Linked list of messages to send to a particular other peer.
349 struct P2PPendingMessage
352 * Pointer to next item in the list
354 struct P2PPendingMessage *next;
357 * Pointer to previous item in the list
359 struct P2PPendingMessage *prev;
362 * When does this message time out?
364 struct GNUNET_TIME_Absolute timeout;
367 * Message importance level. FIXME: used? useful?
369 unsigned int importance;
372 * Actual message to be sent, allocated at the end of the struct:
373 * // msg = (cast) &pm[1];
374 * // memcpy (&pm[1], data, len);
376 const struct GNUNET_MessageHeader *msg;
381 * Entry in friend_peers map.
387 * What is the identity of the peer?
389 struct GNUNET_PeerIdentity id;
392 * Count of outstanding messages for peer.
394 unsigned int pending_count;
397 * Head of pending messages to be sent to this peer.
399 struct P2PPendingMessage *head;
402 * Tail of pending messages to be sent to this peer.
404 struct P2PPendingMessage *tail;
407 * TODO - How and where to use this?
408 * Core handle for sending messages to this peer.
410 struct GNUNET_CORE_TransmitHandle *th;
415 * Entry in finger_peers map.
420 * What is the identity of the finger peer?
422 struct GNUNET_PeerIdentity id;
425 * Start of the interval of keys for which this finger is responsible.
427 unsigned int interval_start;
430 * End of the interval of keys for which this finger is responsible.
432 unsigned int interval_end;
435 * Head of trail list.
437 struct TrailPeerList *head;
440 * Tail of trail list.
442 struct TrailPeerList *tail;
448 * Task that sends FIND FINGER TRAIL requests.
450 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
453 * Identity of this peer.
455 static struct GNUNET_PeerIdentity my_identity;
458 * FIXME: Not used anywhere in the code yet.
459 * Hash of the identity of this peer.
461 static struct GNUNET_HashCode my_identity_hash;
464 * Hash map of all the friends of a peer
466 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peers;
469 * Hash map of all the fingers of a peer
471 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peers;
474 * TODO: Ask whats the use of ATS.
477 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
482 static struct GNUNET_CORE_Handle *core_api;
485 * The highest finger_id that we have found trail to.
487 static unsigned int highest_finger_id;
491 * Called when core is ready to send a message we asked for
492 * out to the destination.
494 * @param cls the 'struct FriendInfo' of the target friend peer
495 * @param size number of bytes available in buf
496 * @param buf where the callee should write the message
497 * @return number of bytes written to buf
500 core_transmit_notify (void *cls, size_t size, void *buf)
502 struct FriendInfo *peer = cls;
504 struct P2PPendingMessage *pending;
509 while ((NULL != (pending = peer->head)) &&
510 (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
512 peer->pending_count--;
513 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
514 GNUNET_free (pending);
518 /* no messages pending */
524 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
526 GNUNET_TIME_absolute_get_remaining
527 (pending->timeout), &peer->id,
528 ntohs (pending->msg->size),
529 &core_transmit_notify, peer);
530 GNUNET_break (NULL != peer->th);
534 while ((NULL != (pending = peer->head)) &&
535 (size - off >= (msize = ntohs (pending->msg->size))))
537 GNUNET_STATISTICS_update (GDS_stats,
539 ("# Bytes transmitted to other peers"), msize,
541 memcpy (&cbuf[off], pending->msg, msize);
543 peer->pending_count--;
544 GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
545 GNUNET_free (pending);
547 if (peer->head != NULL)
550 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
552 GNUNET_TIME_absolute_get_remaining
553 (pending->timeout), &peer->id, msize,
554 &core_transmit_notify, peer);
555 GNUNET_break (NULL != peer->th);
562 * Transmit all messages in the friend's message queue.
564 * @param peer message queue to process
567 process_friend_queue (struct FriendInfo *peer)
570 struct P2PPendingMessage *pending;
572 if (NULL == (pending = peer->head))
574 if (NULL != peer->th)
576 GNUNET_STATISTICS_update (GDS_stats,
578 ("# Bytes of bandwidth requested from core"),
579 ntohs (pending->msg->size), GNUNET_NO);
581 /*FIXME : here I don't know the use of importance, time out
582 Will check at run time if its all correct. */
584 GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
586 GNUNET_TIME_absolute_get_remaining
587 (pending->timeout), &peer->id,
588 ntohs (pending->msg->size),
589 &core_transmit_notify, peer);
590 GNUNET_break (NULL != peer->th);
595 * FIXME: Check the parameters.
596 * Set up the trial message and forwards this message to friend.
598 * @param Finger id to which we want to setup the trail.
599 * @param Friend id through which we will try to setup the trail.
602 GDS_NEIGHBOURS_trail_setup(struct GNUNET_PeerIdentity *finger_id,
603 struct FriendInfo *target_friend)
606 * FIXME: check if pending message actually contains the correct data.
608 struct P2PPendingMessage *pending;
609 /* FIXME: why I have defined as **? verify by testing. */
610 struct PeerTrailSetupMessage *tsm;
613 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
615 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
619 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
620 tsm = (struct PeerTrailSetupMessage *) &pending[1];
621 pending->msg = &tsm->header;
622 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
623 tsm->destination_finger = finger_id;
624 tsm->source_peer = &my_identity;
625 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
626 target_friend->pending_count++;
627 process_friend_queue(target_friend);
631 /**FIXME: Old implementation just to remove error
632 * TODO: Modify this function to handle our get request.
633 * Perform a GET operation. Forwards the given request to other
634 * peers. Does not lookup the key locally. May do nothing if this is
635 * the only peer in the network (or if we are the closest peer in the
638 * @param type type of the block
639 * @param options routing options
640 * @param desired_replication_level desired replication count
641 * @param hop_count how many hops did this request traverse so far?
642 * @param key key for the content
643 * @param xquery extended query
644 * @param xquery_size number of bytes in @a xquery
645 * @param reply_bf bloomfilter to filter duplicates
646 * @param reply_bf_mutator mutator for @a reply_bf
647 * @param peer_bf filter for peers not to select (again)
650 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
651 enum GNUNET_DHT_RouteOption options,
652 uint32_t desired_replication_level,
653 uint32_t hop_count, const struct GNUNET_HashCode * key,
654 const void *xquery, size_t xquery_size,
655 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
656 uint32_t reply_bf_mutator,
657 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
662 /**FIXME: Old implementation just to remove error.
663 * TODO: Modify this function to handle our put request.
664 * Perform a PUT operation. Forwards the given request to other
665 * peers. Does not store the data locally. Does not give the
666 * data to local clients. May do nothing if this is the only
667 * peer in the network (or if we are the closest peer in the
670 * @param type type of the block
671 * @param options routing options
672 * @param desired_replication_level desired replication count
673 * @param expiration_time when does the content expire
674 * @param hop_count how many hops has this message traversed so far
675 * @param bf Bloom filter of peers this PUT has already traversed
676 * @param key key for the content
677 * @param put_path_length number of entries in @a put_path
678 * @param put_path peers this request has traversed so far (if tracked)
679 * @param data payload to store
680 * @param data_size number of bytes in @a data
683 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
684 enum GNUNET_DHT_RouteOption options,
685 uint32_t desired_replication_level,
686 struct GNUNET_TIME_Absolute expiration_time,
688 struct GNUNET_CONTAINER_BloomFilter *bf,
689 const struct GNUNET_HashCode *key,
690 unsigned int put_path_length,
691 struct GNUNET_PeerIdentity *put_path,
692 const void *data, size_t data_size)
698 /**FIXME: Old implementation just to remove error.
699 * Handle a reply (route to origin). Only forwards the reply back to
700 * other peers waiting for it. Does not do local caching or
701 * forwarding to local clients.
703 * @param target neighbour that should receive the block (if still connected)
704 * @param type type of the block
705 * @param expiration_time when does the content expire
706 * @param key key for the content
707 * @param put_path_length number of entries in put_path
708 * @param put_path peers the original PUT traversed (if tracked)
709 * @param get_path_length number of entries in put_path
710 * @param get_path peers this reply has traversed so far (if tracked)
711 * @param data payload of the reply
712 * @param data_size number of bytes in data
715 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
716 enum GNUNET_BLOCK_Type type,
717 struct GNUNET_TIME_Absolute expiration_time,
718 const struct GNUNET_HashCode * key,
719 unsigned int put_path_length,
720 const struct GNUNET_PeerIdentity *put_path,
721 unsigned int get_path_length,
722 const struct GNUNET_PeerIdentity *get_path,
723 const void *data, size_t data_size)
731 * I have written a code where
732 * 1. I choose a random index from 0 to current size of my map.
733 * 2. Create an iterator.
734 * 3. set the iterator value to the current index id.
735 * 4. get the element stored at that index id.
736 * 5. return the index to calling function.
737 * I have not yet tested this function and I am not sure if its correct.
738 * Randomly choose one of your friends from the friends_peer map
741 static struct FriendInfo *
744 unsigned int current_size;
747 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
748 struct GNUNET_PeerIdentity key_ret;
749 struct FriendInfo *friend;
751 current_size = GNUNET_CONTAINER_multipeermap_size(friend_peers);
753 /* Element stored at this index in friend_peers map should be chosen friend. */
754 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
756 /* Create an iterator for friend_peers map. */
757 iter = GNUNET_CONTAINER_multipeermap_iterator_create(friend_peers);
759 /* Set the position of iterator to index. */
762 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,NULL,NULL))
768 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,&key_ret,(const void **)&friend))
778 * TODO: Complete this function.
779 * Use Chord formula finger[i]=(n+2^(i-1))mod m,
780 * where i = current finger map index - max. 256 bits
781 * n = own peer identity - 256 bits
782 * m = number of bits in peer id - 256 bits
783 * @return finger_peer_id for which we have to find the trail through network.
786 struct GNUNET_PeerIdentity *
787 finger_id_to_search()
790 //struct GNUNET_PeerIdentity *finger_peer_id;
792 /*TODO: Add a wrapper in crypto_ecc.c to add an integer do mod operation on integer
793 to find peer id. Take care of parameters. You should work on the value of
794 finger_id not on its pointer.
795 Increment the value of finger_id. */
797 //return finger_peer_id;
803 * FIXME: Implement after testing friend/finger map.
804 * This function will be needed when we are handling node joins/fails
805 * to maintain correct pointer to our predecessor and successor in the network.
806 * Find immediate predecessor in the network.
807 * @param me my own identity
808 * @return peer identity of immediate predecessor.
811 struct GNUNET_PeerIdentity*
812 find_immediate_predecessor()
814 /* Using your own peer identity, calculate your predecessor
815 in the network. Try to setup path to this predecessor using
816 the same logic as used for other fingers. */
822 * Task to send a find finger trail message. We attempt to find trail
823 * to our finger in the network.
825 * @param cls closure for this task
826 * @param tc the context under which the task is running
829 send_find_finger_trail_message (void *cls,
830 const struct GNUNET_SCHEDULER_TaskContext *tc)
832 struct GNUNET_PeerIdentity *finger_peer_id;
833 struct FriendInfo *friend_peer_id;
834 struct GNUNET_TIME_Relative next_send_time;
836 /* We already have found trail to each of our possible fingers in the network. */
837 if (GNUNET_CONTAINER_multipeermap_size(finger_peers) == MAX_FINGERS)
839 /* We can find trail to our immediate predecessor in the network. */
840 finger_peer_id = find_immediate_predecessor();
844 /* Find the finger_peer_id for which we want to setup the trial */
845 finger_peer_id = finger_id_to_search();
848 /* Choose a friend randomly from your friend_peers map. */
849 friend_peer_id = get_random_friend();
851 /* Check if we found a friend or not. */
852 if(NULL != friend_peer_id)
853 GDS_NEIGHBOURS_trail_setup(finger_peer_id, friend_peer_id);
856 next_send_time.rel_value_us =
857 DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
858 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
859 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
860 (highest_finger_id + 1));
862 find_finger_trail_task =
863 GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
869 * Method called whenever a peer connects.
872 * @param peer peer identity this notification is about
875 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer)
877 struct FriendInfo *ret;
879 /* Check for connect to self message */
880 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
883 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
887 /* If peer already exists in our friend_peers, then exit. */
889 GNUNET_CONTAINER_multipeermap_contains (friend_peers,
896 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
899 ret = GNUNET_new (struct FriendInfo);
902 GNUNET_assert (GNUNET_OK ==
903 GNUNET_CONTAINER_multipeermap_put (friend_peers,
905 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
907 /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
908 if (1 == GNUNET_CONTAINER_multipeermap_size(friend_peers))
909 find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
914 * FIXME: Implement after testing finger/friend table setup.
915 * Method called whenever a peer disconnects.
918 * @param peer peer identity this notification is about
921 handle_core_disconnect (void *cls,
922 const struct GNUNET_PeerIdentity *peer)
925 * 1. remove the friend from the friend map.
926 * 2. remove the trail for the fingers for which this peer was the first hop.
927 * 3. start send_find_finger_trail for these fingers to find a new trail
929 * 4. Also when a node gets disconnected, how should we update pointers of its
930 * immediate successor and predecessor in the network ?
931 * 5. Also how do we distribute the keys in the network?
932 * 6. Here is case where we started put operation but a peer got disconnected and
933 we removed the entry from the table. How to handle such a case.
940 * To be called on core init/fail.
942 * @param cls service closure
943 * @param identity the public identity of this peer
946 core_init (void *cls,
947 const struct GNUNET_PeerIdentity *identity)
949 my_identity = *identity;
950 GNUNET_CRYPTO_hash (identity,
951 sizeof (struct GNUNET_PeerIdentity),
957 * Core handler for p2p put requests.
960 * @param peer sender of the request
961 * @param message message
962 * @param peer peer identity this notification is about
963 * @return #GNUNET_OK to keep the connection open,
964 * #GNUNET_SYSERR to close it (signal serious error)
967 handle_dht_p2p_put (void *cls,
968 const struct GNUNET_PeerIdentity *peer,
969 const struct GNUNET_MessageHeader *message)
972 1. Search the friend,finger and check your own id to find the closest
973 * predecessor the given key. --> find_predecessor()
974 2. If self then datache_store
975 3. If friend, then add to peer queue
976 4. If finger, then add to the peer queue of the first hop.
977 * in put message also maintain a field current_destination and use
978 * same logic as trail setup to understand if you are just part of trail
979 * to reach to a particular peer or you are endpoint of trail or just a friend.
987 * Core handler for p2p get requests.
990 * @param peer sender of the request
991 * @param message message
992 * @return #GNUNET_OK to keep the connection open,
993 * #GNUNET_SYSERR to close it (signal serious error)
996 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
997 const struct GNUNET_MessageHeader *message)
1004 * Core handler for p2p result messages.
1006 * @param cls closure
1007 * @param message message
1008 * @param peer peer identity this notification is about
1009 * @return #GNUNET_YES (do not cut p2p connection)
1012 handle_dht_p2p_result (void *cls, const struct GNUNET_PeerIdentity *peer,
1013 const struct GNUNET_MessageHeader *message)
1021 * Are we comparing the predecessor with our own identity also.
1023 * Here also we would be comparing the numeric value of
1024 * peer identity. We read the element from our map. Extract
1025 * the peer id and compare it with destination id. But again
1026 * this comparison is on values. Same issue again.
1027 * Find the predecessor for given finger_id from the
1028 * friend and finger table.
1029 * if friend, then just return the friend
1030 * if finger, then return the next hop to forward the packet to and also
1031 * set the current_destination field to finger_id.
1032 * @param destination peer id's predecessor we are looking for.
1035 static struct GNUNET_PeerIdentity *
1036 find_successor(struct GNUNET_PeerIdentity *destination)
1038 unsigned int friend_index;
1039 unsigned int finger_index;
1040 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1041 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1042 struct GNUNET_PeerIdentity key_ret;
1043 struct FriendInfo *friend;
1044 struct FingerInfo *finger;
1046 /* Should I keep a variable to remember if GNUNET_PeerIdentity is
1047 friend or finger. */
1048 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peers);
1050 /*iterate over friend map till you reach a peer id such that destination <= peer id */
1051 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peers); friend_index++)
1053 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1056 * 1. Check if friend >= destination.
1057 * 2. If yes then check if friend <= current_predecessor,
1058 * if yes then curret_predecessor = friend.
1059 * 3 If not then do nothing.
1065 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peers);
1066 /*iterate over finger map till you reach a peer id such that destination <= peer id */
1067 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (friend_peers); finger_index++)
1069 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1072 * 1. Check if finger >= destination.
1073 * 2. If yes then check if finger <= current_predecessor,
1074 * if yes then curret_predecessor = finger.
1075 * 3 If not then do nothing.
1081 /* Check between friend and finger value to decide which is the predecessor.
1082 If friend, then send the friend id.
1083 If finger, then send the next hop. */
1090 * 1. Check if we are maintaining the 64k size of struct PeerTrailSetupMessage.
1091 * when we add ourself to the trail list.
1092 * 2. Ensure every case is handled for current_destination.
1093 * 3. When should you call GDS_Routing_Add?
1094 * Core handler for P2P trail setup message.
1095 * @param cls closure
1096 * @param message message
1097 * @param peer peer identity this notification is about
1098 * @return #GNUNET_YES
1101 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1102 const struct GNUNET_MessageHeader *message)
1104 const struct PeerTrailSetupMessage *trail_setup;
1105 struct GNUNET_PeerIdentity *next_hop;
1106 struct FriendInfo *friend;
1107 struct TrailPeerList *peer_entry;
1108 struct P2PPendingMessage *pending;
1112 msize = ntohs (message->size);
1113 if (msize < sizeof (struct PeerTrailSetupMessage))
1115 GNUNET_break_op (0);
1119 trail_setup = (const struct PeerTrailSetupMessage *) message;
1121 GNUNET_STATISTICS_update (GDS_stats,
1122 gettext_noop ("# TRAIL SETUP requests received"), 1,
1124 GNUNET_STATISTICS_update (GDS_stats,
1125 gettext_noop ("# TRAIL SETUP bytes received"), msize,
1129 /* Check the value of current_destination and handle the respective case. */
1130 if(trail_setup->current_destination == NULL)
1132 /* Find the next peer to pass the trail setup message. */
1133 next_hop = find_successor(trail_setup->destination_finger);
1135 else if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_setup->current_destination,&my_identity)))
1137 /* I am current destination, find the next peer to pass the trail setup message. */
1138 next_hop = find_successor(trail_setup->destination_finger);
1139 /* Here we have not reached to final destination, but we found the closest
1140 predecessor. routing table should have an entry only if its a finger. */
1141 //GDS_Routing_add();
1145 /* I am part of the trail to reach to current_destination. */
1146 next_hop = GDS_Routing_search(trail_setup->source_peer, trail_setup->current_destination, trail_setup->tail->peer);
1150 if(0 == (GNUNET_CRYPTO_cmp_peer_identity(next_hop,&my_identity)))
1152 /* I am the closest successor of the destination finger in the network. */
1154 1. Prepare a trail setup result message.
1155 2. Add yourself to trail list.
1156 3. send packet to last element in the list.
1161 /* Insert next hop into trial list. */
1162 peer_entry = GNUNET_malloc (sizeof (struct TrailPeerList));
1163 peer_entry->peer = &my_identity;
1164 peer_entry->next = NULL;
1165 peer_entry->prev = NULL;
1167 /*SUPU what is this stupid code that I have written. */
1168 GNUNET_CONTAINER_DLL_insert_tail(trail_setup->head->next,trail_setup->tail->prev,peer_entry);
1170 /* Find the struct FriendInfo for next_hop peer id. */
1171 friend = GNUNET_CONTAINER_multipeermap_get(friend_peers,next_hop);
1173 /* Send trail setup message to next hop friend. */
1174 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
1175 /*FIXME: This is wrong. Where do you copy the new trail_setup message to
1177 GNUNET_CONTAINER_DLL_insert_tail (friend->head, friend->tail, pending);
1178 friend->pending_count++;
1179 process_friend_queue(friend);
1184 /* Add an entry to finger table. */
1186 void finger_table_add(struct PeerTrailSetupResultMessage *result)
1188 /* Add the whole trail in your finger table,
1189 also add interval. */
1193 /* Traverse the trail list to find the next hop to pass the result message. */
1195 struct GNUNET_PeerIdentity *
1196 find_trail_list_next_hop(struct PeerTrailSetupResultMessage *trail_result)
1198 /* Setup the current_destination value to new next hop found. */
1204 * Core handle for p2p trail construction result messages.
1205 * @param cls closure
1206 * @param message message
1207 * @param peer peer identity this notification is about
1208 * @return #GNUNET_YES (do not cut p2p connection)
1212 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
1213 const struct GNUNET_MessageHeader *message)
1215 /* FIXME: Should it be const? */
1216 struct PeerTrailSetupResultMessage *trail_result;
1217 struct GNUNET_PeerIdentity *next_hop;
1218 struct FriendInfo *friend;
1219 struct P2PPendingMessage *pending;
1220 trail_result = (struct PeerTrailSetupResultMessage *) message;
1224 msize = ntohs (message->size);
1225 if (msize < sizeof (struct PeerTrailSetupResultMessage))
1227 GNUNET_break_op (0);
1231 /* This should always be the case. */
1232 if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_result->current_destination,&my_identity)))
1234 /* Am I the destination ? */
1235 if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_result->destination_peer,&my_identity)))
1237 /* I am the destination. Add the trail to my finger table. */
1238 finger_table_add(trail_result);
1243 /* Find the next peer in the trail list to pass the message to. */
1244 next_hop = find_trail_list_next_hop(trail_result);
1246 /* Find the struct FriendInfo for next_hop peer id. */
1247 friend = GNUNET_CONTAINER_multipeermap_get(friend_peers,next_hop);
1249 /* Send trail setup result message to next hop friend. */
1251 I have not yet written the code to copy struct trail message to
1252 pending message. Also, before sending the message I need to check
1253 the MAXIMUM_PENDNIG_PEER limit is not crossed. Modify the same part
1254 of code for handle_dht_p2p_trail_setup. */
1255 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
1256 GNUNET_CONTAINER_DLL_insert_tail (friend->head, friend->tail, pending);
1257 friend->pending_count++;
1258 process_friend_queue(friend);
1264 return GNUNET_SYSERR;
1269 * Initialize neighbours subsystem.
1270 * @return GNUNET_OK on success, GNUNET_SYSERR on error
1273 GDS_NEIGHBOURS_init()
1275 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
1276 {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
1277 {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
1278 {&handle_dht_p2p_result, GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT, 0},
1279 {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
1280 {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
1284 atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
1286 GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
1287 &handle_core_disconnect, NULL, GNUNET_NO, NULL,
1288 GNUNET_NO, core_handlers);
1289 if (core_api == NULL)
1290 return GNUNET_SYSERR;
1292 friend_peers = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1293 finger_peers = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1300 * Shutdown neighbours subsystem.
1303 GDS_NEIGHBOURS_done ()
1305 if (NULL == core_api)
1307 GNUNET_CORE_disconnect (core_api);
1309 GNUNET_ATS_performance_done (atsAPI);
1312 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peers));
1313 GNUNET_CONTAINER_multipeermap_destroy (friend_peers);
1314 friend_peers = NULL;
1316 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peers));
1317 GNUNET_CONTAINER_multipeermap_destroy (finger_peers);
1318 finger_peers = NULL;
1320 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
1322 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
1323 find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
1329 * Get the ID of the local node.
1331 * @return identity of the local node
1333 struct GNUNET_PeerIdentity *
1334 GDS_NEIGHBOURS_get_id ()
1336 return &my_identity;
1340 /* end of gnunet-service-xdht_neighbours.c */