From 9a9e7ffe6e13d60009e749e0811dcc7b997a764c Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Mon, 27 Apr 2015 12:00:16 +0000 Subject: starting with whanu --- src/dht/Makefile.am | 4 +- src/dht/gnunet-service-wdht_neighbours.c | 6556 ++++-------------------------- src/include/gnunet_protocols.h | 53 +- 3 files changed, 923 insertions(+), 5690 deletions(-) diff --git a/src/dht/Makefile.am b/src/dht/Makefile.am index 0dca26901..039cdb038 100644 --- a/src/dht/Makefile.am +++ b/src/dht/Makefile.am @@ -48,8 +48,8 @@ libgnunet_plugin_block_dht_la_LDFLAGS = \ libexec_PROGRAMS = \ gnunet-service-dht \ - gnunet-service-dht-xvine\ - gnunet-service-dht-whanau + gnunet-service-dht-xvine +# gnunet-service-dht-whanau noinst_PROGRAMS = \ gnunet-dht-monitor \ diff --git a/src/dht/gnunet-service-wdht_neighbours.c b/src/dht/gnunet-service-wdht_neighbours.c index c91b78a69..858c0457d 100644 --- a/src/dht/gnunet-service-wdht_neighbours.c +++ b/src/dht/gnunet-service-wdht_neighbours.c @@ -44,91 +44,125 @@ #include #include "dht.h" -/** - * TODO: - * 1. In X-Vine paper, there is no policy defined for replicating the data to - * recover in case of peer failure. We can do it in Chord way. In R5N, the key - * is hashed and then data is stored according to the key value generated after - * hashing. - */ - #define DEBUG(...) \ GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__) /** - * Maximum possible fingers (including predecessor) of a peer + * FIXME */ -#define MAX_FINGERS 65 +#define FOO_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2) -/** - * Maximum allowed number of pending messages per friend peer. - */ -#define MAXIMUM_PENDING_PER_FRIEND 64 -/** - * How long to wait before sending another find finger trail request - */ -#define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2) +GNUNET_NETWORK_STRUCT_BEGIN /** - * How long to wait before sending another verify successor message. + * Setup a finger using the underlay topology ("social network"). */ -#define DHT_SEND_VERIFY_SUCCESSOR_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2) +struct FingerSetupMessage +{ + /** + * Type: #GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP + */ + struct GNUNET_MessageHeader header; -/** - * How long to wait before sending another verify successor message. - */ -#define DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30) + /** + * Number of hops this message has taken so far, we stop at + * log(NSE), in NBO. + */ + uint16_t hops_taken GNUNET_PACKED; -/** - * How long to wait before retrying notify successor. - */ -#define DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30) + /** + * Layer for the request, in NBO. + */ + uint16_t layer GNUNET_PACKED; -/** - * How long at most to wait for transmission of a request to a friend ? - */ -#define PENDING_MESSAGE_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2) + /** + * Unique (random) identifier this peer will use to + * identify the finger (in future messages). + */ + struct GNUNET_HashCode finger_id; -/** - * Duration for which I may remain congested. - * Note: Its a static value. In future, a peer may do some analysis and calculate - * congestion_timeout based on 'some' parameters. - */ -#define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2) +}; -/** - * In case we don't hear back from the current successor, then we can start - * verify successor. - */ -#define WAIT_NOTIFY_CONFIRMATION GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 200) /** - * Maximum number of trails allowed to go through a friend. + * Response to a `struct FingerSetupMessage`. */ -#define TRAILS_THROUGH_FRIEND_THRESHOLD 64 +struct FingerSetupResponseMessage +{ + /** + * Type: #GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP_RESPONSE + */ + struct GNUNET_MessageHeader header; + + /** + * Zero, for alignment. + */ + uint32_t reserved GNUNET_PACKED; + + /** + * Unique (random) identifier this peer will use to + * identify the finger (in future messages). + */ + struct GNUNET_HashCode finger_id; + + /** + * Random location in the respective layer where the + * random path of the finger setup terminated. + */ + struct GNUNET_HashCode location; + +}; -/** - * Maximum number of trails stored per finger. - */ -#define MAXIMUM_TRAILS_PER_FINGER 4 /** - * Finger map index for predecessor entry in finger table. + * Response to an event that causes a finger to die. */ -#define PREDECESSOR_FINGER_ID 64 +struct FingerDestroyMessage +{ + /** + * Type: #GNUNET_MESSAGE_TYPE_WDHT_FINGER_DESTROY + */ + struct GNUNET_MessageHeader header; + + /** + * Zero, for alignment. + */ + uint32_t reserved GNUNET_PACKED; + + /** + * Unique (random) identifier this peer will use to + * identify the finger (in future messages). + */ + struct GNUNET_HashCode finger_id; + +}; + /** - * FIXME: Its use only at 3 places check if you can remove it. - * To check if a finger is predecessor or not. + * Send a message along a finger. */ -enum GDS_NEIGHBOURS_finger_type +struct FingerRouteMessage { - GDS_FINGER_TYPE_PREDECESSOR = 1, - GDS_FINGER_TYPE_NON_PREDECESSOR = 0 + /** + * Type: #GNUNET_MESSAGE_TYPE_WDHT_FINGER_ROUTE + */ + struct GNUNET_MessageHeader header; + + /** + * Zero, for alignment. + */ + uint32_t reserved GNUNET_PACKED; + + /** + * Unique (random) identifier this peer will use to + * identify the finger (in future messages). + */ + struct GNUNET_HashCode finger_id; + + /* followed by payload to send along the finger */ }; -GNUNET_NETWORK_STRUCT_BEGIN /** * P2P PUT message @@ -136,7 +170,7 @@ GNUNET_NETWORK_STRUCT_BEGIN struct PeerPutMessage { /** - * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT + * Type: #GNUNET_MESSAGE_TYPE_WDHT_P2P_PUT */ struct GNUNET_MessageHeader header; @@ -166,18 +200,6 @@ struct PeerPutMessage */ uint32_t put_path_length GNUNET_PACKED; - /** - * Best known destination (could be my friend or finger) which should - * get this message next. - */ - struct GNUNET_PeerIdentity best_known_destination; - - /** - * In case best_known_destination is a finger, then trail to reach - * to that finger. Else its default value is 0. - */ - struct GNUNET_HashCode intermediate_trail_id; - /** * When does the content expire? */ @@ -200,7 +222,7 @@ struct PeerPutMessage struct PeerGetMessage { /** - * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET + * Type: #GNUNET_MESSAGE_TYPE_WDHT_P2P_GET */ struct GNUNET_MessageHeader header; @@ -230,18 +252,6 @@ struct PeerGetMessage */ unsigned int get_path_length; - /** - * Best known destination (could be my friend or finger) which should - * get this message next. - */ - struct GNUNET_PeerIdentity best_known_destination; - - /** - * In case best_known_destination is a finger, then trail to reach - * to that finger. Else its default value is 0. - */ - struct GNUNET_HashCode intermediate_trail_id; - /** * The key we are looking for. */ @@ -251,13 +261,14 @@ struct PeerGetMessage /* struct GNUNET_PeerIdentity[]*/ }; + /** * P2P Result message */ struct PeerGetResultMessage { /** - * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT + * Type: #GNUNET_MESSAGE_TYPE_WDHT_P2P_GET_RESULT */ struct GNUNET_MessageHeader header; @@ -300,5711 +311,988 @@ struct PeerGetResultMessage }; +GNUNET_NETWORK_STRUCT_END + /** - * P2P Trail setup message + * Entry in friend_peermap. */ -struct PeerTrailSetupMessage -{ - /** - * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP - */ - struct GNUNET_MessageHeader header; - - /** - * Is source_peer trying to setup the trail to a predecessor or any finger. - */ - uint32_t is_predecessor; - - /** - * Peer closest to this value will be our finger. - */ - uint64_t final_destination_finger_value; - - /** - * Source peer which wants to setup the trail to one of its finger. - */ - struct GNUNET_PeerIdentity source_peer; - - /** - * Best known destination (could be my friend or finger) which should - * get this message next. - * - * FIXME: this could be removed if we include trail_source / trail_dest - * in the routing table. This way we save 32 bytes of bandwidth by using - * extra 8 bytes of memory (2 * sizeof (GNUNET_PEER_ID)) - */ - struct GNUNET_PeerIdentity best_known_destination; - - /** - * In case best_known_destination is a finger, then trail id of trail to - * reach to this finger. - */ - struct GNUNET_HashCode intermediate_trail_id; - - /** - * Trail id for trail which we are trying to setup. - */ - struct GNUNET_HashCode trail_id; +struct FriendInfo; - /* List of peers which are part of trail setup so far. - * Trail does NOT include source_peer and peer which will be closest to - * ultimate_destination_finger_value. - * struct GNUNET_PeerIdentity trail[] - */ -}; /** - * P2P Trail Setup Result message + * Information we keep per trail. */ -struct PeerTrailSetupResultMessage +struct Trail { /** - * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT - */ - struct GNUNET_MessageHeader header; - - /** - * Finger to which we have found the path. + * MDLL entry in the list of all trails with the same predecessor. */ - struct GNUNET_PeerIdentity finger_identity; + struct Tail *prev_succ; /** - * Peer which started trail_setup to find trail to finger_identity + * MDLL entry in the list of all trails with the same predecessor. */ - struct GNUNET_PeerIdentity querying_peer; + struct Tail *next_succ; /** - * Is the trail setup to querying_peer's predecessor or finger? + * MDLL entry in the list of all trails with the same predecessor. */ - uint32_t is_predecessor; + struct Tail *prev_pred; /** - * Value to which finger_identity is the closest peer. + * MDLL entry in the list of all trails with the same predecessor. */ - uint64_t ulitmate_destination_finger_value; + struct Tail *next_pred; /** - * Identifier of the trail from querying peer to finger_identity, NOT - * including both endpoints. - */ - struct GNUNET_HashCode trail_id; - - /* List of peers which are part of the trail from querying peer to - * finger_identity, NOT including both endpoints. - * struct GNUNET_PeerIdentity trail[] + * Our predecessor in the trail, NULL if we are initiator (?). */ -}; + struct FriendInfo *pred; -/** - * P2P Verify Successor Message. - */ -struct PeerVerifySuccessorMessage -{ /** - * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR + * Our successor in the trail, NULL if we are the last peer. */ - struct GNUNET_MessageHeader header; + struct FriendInfo *succ; /** - * Peer which wants to verify its successor. + * Identifier of the trail with the predecessor. */ - struct GNUNET_PeerIdentity source_peer; + struct GNUNET_HashCode pred_id; /** - * Source Peer's current successor. + * Identifier of the trail with the successor. */ - struct GNUNET_PeerIdentity successor; + struct GNUNET_HashCode succ_id; /** - * Identifier of trail to reach from source_peer to successor. + * When does this trail expire. */ - struct GNUNET_HashCode trail_id; + struct GNUNET_TIME_Absolute expiration_time; - /* List of the peers which are part of trail to reach from source_peer - * to successor, NOT including them - * struct GNUNET_PeerIdentity trail[] - */ }; + /** - * P2P Verify Successor Result Message + * Entry in friend_peermap. */ -struct PeerVerifySuccessorResultMessage +struct FriendInfo { /** - * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT + * Friend Identity */ - struct GNUNET_MessageHeader header; + struct GNUNET_PeerIdentity id; - /** - * Peer which sent the request to verify its successor. - */ - struct GNUNET_PeerIdentity querying_peer; + struct Tail *pred_head; - /** - * Successor to which PeerVerifySuccessorMessage was sent. - */ - struct GNUNET_PeerIdentity current_successor; + struct Tail *pred_tail; - /** - * Current Predecessor of source_successor. It can be same as querying peer - * or different. In case it is different then it can be querying_peer's - * probable successor. - */ - struct GNUNET_PeerIdentity probable_successor; + struct Tail *succ_head; - /** - * Trail identifier of trail from querying_peer to current_successor. - */ - struct GNUNET_HashCode trail_id; + struct Tail *succ_tail; /** - * Direction in which we are looking at the trail. + * Core handle for sending messages to this friend. + * FIXME: use MQ? */ - uint32_t trail_direction; + struct GNUNET_CORE_TransmitHandle *th; - /* In case probable_successor != querying_peer, then trail to reach from - * querying_peer to probable_successor, NOT including end points. - * struct GNUNET_PeerIdentity trail[] - */ }; -/** - * P2P Notify New Successor Message. - */ -struct PeerNotifyNewSuccessorMessage -{ - /** - * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR - */ - struct GNUNET_MessageHeader header; - - /** - * Peer which wants to notify its new successor. - */ - struct GNUNET_PeerIdentity source_peer; - - /** - * New successor of source_peer. - */ - struct GNUNET_PeerIdentity new_successor; - - /** - * Unique identifier of the trail from source_peer to new_successor, - * NOT including the endpoints. - */ - struct GNUNET_HashCode trail_id; - /* List of peers in trail from source_peer to new_successor, - * NOT including the endpoints. - * struct GNUNET_PeerIdentity trail[] - */ -}; /** - * P2P Notify Successor Confirmation message. + * Task to timeout trails that have expired. */ -struct PeerNotifyConfirmationMessage -{ - /** - * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN - */ - struct GNUNET_MessageHeader header; - - /** - * Unique identifier of the trail. - */ - struct GNUNET_HashCode trail_id; - - /** - * Direction of trail. - */ - uint32_t trail_direction; -}; - +static struct GNUNET_SCHEDULER_Task *trail_timeout_task; /** - * P2P Trail Tear Down message. + * Identity of this peer. */ -struct PeerTrailTearDownMessage -{ - /** - * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN - */ - struct GNUNET_MessageHeader header; - - /** - * Unique identifier of the trail. - */ - struct GNUNET_HashCode trail_id; +static struct GNUNET_PeerIdentity my_identity; - /** - * Direction of trail. - */ - uint32_t trail_direction; -}; +/** + * Peer map of all the friends of a peer + */ +static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap; +/** + * Tail map, mapping tail identifiers to `struct Trail`s + */ +static struct GNUNET_CONTAINER_MultiHashMap *tail_map; /** - * P2P Trail Rejection Message. + * Tail heap, organizing trails by expiration time. */ -struct PeerTrailRejectionMessage -{ - /** - * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION - */ - struct GNUNET_MessageHeader header; +static struct GNUNET_CONTAINER_Heap *tail_heap; - /** - * Peer which wants to set up the trail. - */ - struct GNUNET_PeerIdentity source_peer; +/** + * Handle to CORE. + */ +static struct GNUNET_CORE_Handle *core_api; - /** - * Peer which sent trail rejection message as it it congested. - */ - struct GNUNET_PeerIdentity congested_peer; - /** - * Peer identity closest to this value will be finger of - * source_peer. - */ - uint64_t ultimate_destination_finger_value; - /** - * Is source_peer trying to setup the trail to its predecessor or finger. - */ - uint32_t is_predecessor; - /** - * Identifier for the trail that source peer is trying to setup. - */ - struct GNUNET_HashCode trail_id; - /** - * Relative time for which congested_peer will remain congested. - */ - struct GNUNET_TIME_Relative congestion_time; - /* Trail_list from source_peer to peer which sent the message for trail setup - * to congested peer. This trail does NOT include source_peer. - struct GNUNET_PeerIdnetity trail[]*/ -}; /** - * P2P Add Trail Message. + * Construct a trail setup message and forward it to target_friend + * @param source_peer Peer which wants to setup the trail + * @param ultimate_destination_finger_value Peer identity closest to this value + * will be finger to @a source_peer + * @param best_known_destination Best known destination (could be finger or friend) + * which should get this message. In case it is + * friend, then it is same as target_friend + * @param target_friend Friend to which message is forwarded now. + * @param trail_length Total number of peers in trail setup so far. + * @param trail_peer_list Trail setup so far + * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not. + * @param trail_id Unique identifier for the trail we are trying to setup. + * @param intermediate_trail_id Trail id of intermediate trail to reach to + * best_known_destination when its a finger. If not + * used then set to 0. */ -struct PeerAddTrailMessage +void +GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer, + uint64_t ultimate_destination_finger_value, + struct GNUNET_PeerIdentity best_known_destination, + struct FriendInfo *target_friend, + unsigned int trail_length, + const struct GNUNET_PeerIdentity *trail_peer_list, + unsigned int is_predecessor, + struct GNUNET_HashCode trail_id, + struct GNUNET_HashCode intermediate_trail_id) { - /** - * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL - */ - struct GNUNET_MessageHeader header; + struct P2PPendingMessage *pending; + struct PeerTrailSetupMessage *tsm; + struct GNUNET_PeerIdentity *peer_list; + size_t msize; - /** - * Source of the routing trail. - */ - struct GNUNET_PeerIdentity source_peer; + msize = sizeof (struct PeerTrailSetupMessage) + + (trail_length * sizeof (struct GNUNET_PeerIdentity)); - /** - * Destination of the routing trail. - */ - struct GNUNET_PeerIdentity destination_peer; + if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) + { + GNUNET_break (0); + return; + } - /** - * Unique identifier of the trail from source_peer to destination_peer, - * NOT including the endpoints. - */ - struct GNUNET_HashCode trail_id; - - /* Trail from source peer to destination peer, NOT including them. - * struct GNUNET_PeerIdentity trail[] - */ -}; - - -GNUNET_NETWORK_STRUCT_END - -/** - * Linked list of messages to send to a particular other peer. - */ -struct P2PPendingMessage -{ - /** - * Pointer to next item in the list - */ - struct P2PPendingMessage *next; - - /** - * Pointer to previous item in the list - */ - struct P2PPendingMessage *prev; - - /** - * Message importance level. FIXME: used? useful? - */ - unsigned int importance; - - /** - * When does this message time out? - */ - struct GNUNET_TIME_Absolute timeout; - - /** - * Actual message to be sent, allocated at the end of the struct: - * // msg = (cast) &pm[1]; - * // memcpy (&pm[1], data, len); - */ - const struct GNUNET_MessageHeader *msg; - -}; - -/** - * Entry in friend_peermap. - */ -struct FriendInfo -{ - /** - * Friend Identity - */ - struct GNUNET_PeerIdentity id; - - /** - * Number of trails for which this friend is the first hop or if the friend - * is finger. - */ - unsigned int trails_count; - - /** - * Count of outstanding messages for this friend. - */ - unsigned int pending_count; - - /** - * In case not 0, then amount of time for which this friend is congested. - */ - struct GNUNET_TIME_Absolute congestion_timestamp; - - - // TODO : Change name of head and tail to pending_messages_list_head and so. - /** - * Head of pending messages to be sent to this friend. - */ - struct P2PPendingMessage *head; - - /** - * Tail of pending messages to be sent to this friend. - */ - struct P2PPendingMessage *tail; - - /** - * Core handle for sending messages to this friend. - */ - struct GNUNET_CORE_TransmitHandle *th; - -}; - -/** - * An individual element of the trail to reach to a finger. - */ -struct Trail_Element -{ - /** - * Pointer to next item in the list - */ - struct Trail_Element *next; - - /** - * Pointer to prev item in the list - */ - struct Trail_Element *prev; - - /** - * An element in this trail. - */ - struct GNUNET_PeerIdentity peer; -}; - -/** - * Information about an individual trail. - */ -struct Trail -{ - /** - * Head of trail. - */ - struct Trail_Element *trail_head; - - /** - * Tail of trail. - */ - struct Trail_Element *trail_tail; - - /** - * Unique identifier of this trail. - */ - struct GNUNET_HashCode trail_id; - - /** - * Length of trail pointed - */ - unsigned int trail_length; - - /** - * Is there a valid trail entry. - */ - unsigned int is_present; -}; - -/** - * An entry in finger_table - */ -struct FingerInfo -{ - /** - * Finger identity. - */ - struct GNUNET_PeerIdentity finger_identity; - - /** - * In case not 0, this amount is time to wait for notify successor message. - * Used ONLY for successor. NOT for any other finger. - */ - struct GNUNET_TIME_Absolute wait_notify_confirmation; - - /** - * Is any finger stored at this finger index. - */ - unsigned int is_present; - - /** - * Index in finger peer map - */ - uint32_t finger_table_index; - - /** - * Number of trails setup so far for this finger. - * Should not cross MAXIMUM_TRAILS_PER_FINGER. - */ - uint32_t trails_count; - - /** - * Array of trails to reach to this finger. - */ - struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER]; -}; - - -/** - * Stores information about the peer which is closest to destination_finger_value. - * 'closest' can be either successor or predecessor depending on is_predecessor - * flag. - */ -struct Closest_Peer -{ - /** - * Destination finger value. - */ - uint64_t destination_finger_value; - - /** - * Is finger_value a predecessor or any other finger. - */ - unsigned int is_predecessor; - - /** - * Trail id to reach to peer. - * In case peer is my identity or friend, it is set to 0. - */ - struct GNUNET_HashCode trail_id; - - /** - * Next destination. In case of friend and my_identity , it is same as next_hop - * In case of finger it is finger identity. - */ - struct GNUNET_PeerIdentity best_known_destination; - - /** - * In case best_known_destination is a finger, then first friend in the trail - * to reach to it. In other case, same as best_known_destination. - */ - struct GNUNET_PeerIdentity next_hop; - - /** - * In case finger is the next hop, it contains a valid finger table index - * at which the finger is stored. Else, It contains 65, which is out of range - * of finger table index. - */ - unsigned int finger_table_index; -}; - -/** - * Context for send_verify_successor_task. - */ -struct VerifySuccessorContext -{ - /** - * Number of times this has been scheduled. - */ - unsigned int num_retries_scheduled; -}; - -/** - * Task that sends FIND FINGER TRAIL requests. This task is started when we have - * get our first friend. - */ -static struct GNUNET_SCHEDULER_Task * find_finger_trail_task; - -/** - * Task that sends verify successor message. This task is started when we get - * our successor for the first time. - */ -static struct GNUNET_SCHEDULER_Task * send_verify_successor_task; - -/** - * Task that sends verify successor message. This task is started when we get - * our successor for the first time. - */ -static struct GNUNET_SCHEDULER_Task * send_verify_successor_retry_task; - -/** - * Task that sends verify successor message. This task is started when we get - * our successor for the first time. - */ -static struct GNUNET_SCHEDULER_Task * send_notify_new_successor_retry_task; - -/** - * Identity of this peer. - */ -static struct GNUNET_PeerIdentity my_identity; - -/** - * Peer map of all the friends of a peer - */ -static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap; - -/** - * Array of all the fingers. - */ -static struct FingerInfo finger_table [MAX_FINGERS]; - -/** - * Handle to CORE. - */ -static struct GNUNET_CORE_Handle *core_api; - -/** - * Handle for the statistics service. - */ -//extern struct GNUNET_STATISTICS_Handle *GDS_stats; - -/** - * The current finger index that we have want to find trail to. We start the - * search with value = 0, i.e. successor and then go to PREDCESSOR_FINGER_ID - * and decrement it. For any index 63 <= index < 0, if finger is same as successor, - * we reset this index to 0. - */ -static unsigned int current_search_finger_index; - -/** - * Time duration to schedule find finger trail task. - */ -static struct GNUNET_TIME_Relative find_finger_trail_task_next_send_time; - -/** - * Time duration to schedule verify successor task. - */ -static struct GNUNET_TIME_Relative verify_successor_next_send_time; - -/** - * Time duration to send verify successor again, if result was not received in time. - */ -static struct GNUNET_TIME_Relative verify_successor_retry_time; - -/** - * Time duration to retry send_notify_successor. - */ -static struct GNUNET_TIME_Relative notify_successor_retry_time; - -/** - * Are we waiting for confirmation from our new successor that it got the - * message - */ -//static unsigned int waiting_for_notify_confirmation; - -/* Below variables are used only for testing, and statistics collection. */ -/** - * Should we store our topology predecessor and successor IDs into statistics? - */ -unsigned int track_topology; - -/** - * Should I be a malicious peer and drop the PUT/GET packets? - * if 0 then NOT malicious. - */ -unsigned int act_malicious; - -/** - * Count of fingers found. Ideally we should have O(logn) fingers for a - * stable network. - */ -static unsigned int total_fingers_found; - -/** - * Number of times we found the same successor. - */ -static unsigned int successor_times; - -/** - * Number of rounds for which we should search for finger. - */ -static unsigned int fingers_round_count; -/** - * Called when core is ready to send a message we asked for - * out to the destination. - * - * @param cls the 'struct FriendInfo' of the target friend - * @param size number of bytes available in buf - * @param buf where the callee should write the message - * @return number of bytes written to buf - */ -static size_t -core_transmit_notify (void *cls, size_t size, void *buf) -{ - struct FriendInfo *peer = cls; - char *cbuf = buf; - struct P2PPendingMessage *pending; - size_t off; - size_t msize; - - peer->th = NULL; - while ( (NULL != (pending = peer->head)) && - (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us) ) - { - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Messages dropped (CORE timeout)"), - 1, - GNUNET_NO); - peer->pending_count--; - GNUNET_CONTAINER_DLL_remove (peer->head, - peer->tail, - pending); - GNUNET_free (pending); - } - if (NULL == pending) - { - /* no messages pending */ - return 0; - } - if (NULL == buf) - { - peer->th = - GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO, - GNUNET_CORE_PRIO_BEST_EFFORT, - GNUNET_TIME_absolute_get_remaining - (pending->timeout), &peer->id, - ntohs (pending->msg->size), - &core_transmit_notify, peer); - GNUNET_break (NULL != peer->th); - return 0; - } - off = 0; - while ((NULL != (pending = peer->head)) && - (size - off >= (msize = ntohs (pending->msg->size)))) - { - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes transmitted to other peers"), - msize, - GNUNET_NO); - memcpy (&cbuf[off], pending->msg, msize); - off += msize; - peer->pending_count--; - GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending); - GNUNET_free (pending); - } - if (peer->head != NULL) - { - peer->th = - GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO, - GNUNET_CORE_PRIO_BEST_EFFORT, - GNUNET_TIME_absolute_get_remaining - (pending->timeout), &peer->id, msize, - &core_transmit_notify, peer); - GNUNET_break (NULL != peer->th); - } - return off; -} - - -/** - * Transmit all messages in the friend's message queue. - * - * @param peer message queue to process - */ -static void -process_friend_queue (struct FriendInfo *peer) -{ - struct P2PPendingMessage *pending; - - if (NULL == (pending = peer->head)) - { - return; - } - if (NULL != peer->th) - { - return; - } - - peer->th = - GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO, - pending->importance, - GNUNET_TIME_absolute_get_remaining - (pending->timeout), &peer->id, - ntohs (pending->msg->size), - &core_transmit_notify, peer); - GNUNET_break (NULL != peer->th); -} - - -#if ENABLE_MALICIOUS -/** - * Set the ENABLE_MALICIOUS value to malicious. - * @param malicious - */ -int -GDS_NEIGHBOURS_act_malicious (unsigned int malicious) -{ - act_malicious = malicious; - return GNUNET_OK; -} -#endif - -/** - * Construct a trail setup message and forward it to target_friend - * @param source_peer Peer which wants to setup the trail - * @param ultimate_destination_finger_value Peer identity closest to this value - * will be finger to @a source_peer - * @param best_known_destination Best known destination (could be finger or friend) - * which should get this message. In case it is - * friend, then it is same as target_friend - * @param target_friend Friend to which message is forwarded now. - * @param trail_length Total number of peers in trail setup so far. - * @param trail_peer_list Trail setup so far - * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not. - * @param trail_id Unique identifier for the trail we are trying to setup. - * @param intermediate_trail_id Trail id of intermediate trail to reach to - * best_known_destination when its a finger. If not - * used then set to 0. - */ -void -GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer, - uint64_t ultimate_destination_finger_value, - struct GNUNET_PeerIdentity best_known_destination, - struct FriendInfo *target_friend, - unsigned int trail_length, - const struct GNUNET_PeerIdentity *trail_peer_list, - unsigned int is_predecessor, - struct GNUNET_HashCode trail_id, - struct GNUNET_HashCode intermediate_trail_id) -{ - struct P2PPendingMessage *pending; - struct PeerTrailSetupMessage *tsm; - struct GNUNET_PeerIdentity *peer_list; - size_t msize; - - msize = sizeof (struct PeerTrailSetupMessage) + - (trail_length * sizeof (struct GNUNET_PeerIdentity)); - - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - GNUNET_break (0); - return; - } - - if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) - { - GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), - 1, GNUNET_NO); - } - pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); - pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); - tsm = (struct PeerTrailSetupMessage *) &pending[1]; - pending->msg = &(tsm->header); - tsm->header.size = htons (msize); - tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP); - tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value); - tsm->source_peer = source_peer; - tsm->best_known_destination = best_known_destination; - tsm->is_predecessor = htonl (is_predecessor); - tsm->trail_id = trail_id; - tsm->intermediate_trail_id = intermediate_trail_id; - - if (trail_length > 0) - { - peer_list = (struct GNUNET_PeerIdentity *) &tsm[1]; - memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity)); - } - - GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); - target_friend->pending_count++; - process_friend_queue (target_friend); -} - - -/** - * Construct a trail setup result message and forward it to target friend. - * @param querying_peer Peer which sent the trail setup request and should get - * the result back. - * @param Finger Peer to which the trail has been setup to. - * @param target_friend Friend to which this message should be forwarded. - * @param trail_length Numbers of peers in the trail. - * @param trail_peer_list Peers which are part of the trail from - * querying_peer to Finger, NOT including them. - * @param is_predecessor Is @a Finger predecessor to @a querying_peer ? - * @param ultimate_destination_finger_value Value to which @a finger is the closest - * peer. - * @param trail_id Unique identifier of the trail. - */ -void -GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer, - struct GNUNET_PeerIdentity finger, - struct FriendInfo *target_friend, - unsigned int trail_length, - const struct GNUNET_PeerIdentity *trail_peer_list, - unsigned int is_predecessor, - uint64_t ultimate_destination_finger_value, - struct GNUNET_HashCode trail_id) -{ - struct P2PPendingMessage *pending; - struct PeerTrailSetupResultMessage *tsrm; - struct GNUNET_PeerIdentity *peer_list; - size_t msize; - - msize = sizeof (struct PeerTrailSetupResultMessage) + - (trail_length * sizeof (struct GNUNET_PeerIdentity)); - - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - GNUNET_break (0); - return; - } - - if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) - { - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop ("# P2P messages dropped due to full queue"), - 1, GNUNET_NO); - } - - pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); - pending->importance = 0; - pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); - tsrm = (struct PeerTrailSetupResultMessage *) &pending[1]; - pending->msg = &tsrm->header; - tsrm->header.size = htons (msize); - tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT); - tsrm->querying_peer = querying_peer; - tsrm->finger_identity = finger; - tsrm->is_predecessor = htonl (is_predecessor); - tsrm->trail_id = trail_id; - tsrm->ulitmate_destination_finger_value = - GNUNET_htonll (ultimate_destination_finger_value); - peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1]; - memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity)); - - /* Send the message to chosen friend. */ - GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); - target_friend->pending_count++; - process_friend_queue (target_friend); -} - -/** - * Send notify successor confirmation message. - * @param trail_id Unique Identifier of the trail. - * @param trail_direction Destination to Source. - * @param target_friend Friend to get this message next. - */ -void -GDS_NEIGHBOURS_send_notify_succcessor_confirmation (struct GNUNET_HashCode trail_id, - unsigned int trail_direction, - struct FriendInfo *target_friend) -{ - struct PeerNotifyConfirmationMessage *ncm; - struct P2PPendingMessage *pending; - size_t msize; - - msize = sizeof (struct PeerNotifyConfirmationMessage); - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - GNUNET_break (0); - return; - } - - if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) - { - GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), - 1, GNUNET_NO); - } - - pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); - pending->importance = 0; /* FIXME */ - pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); - ncm = (struct PeerNotifyConfirmationMessage *) &pending[1]; - pending->msg = &ncm->header; - ncm->header.size = htons (msize); - ncm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION); - ncm->trail_id = trail_id; - ncm->trail_direction = htonl (trail_direction); - - /* Send the message to chosen friend. */ - GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); - target_friend->pending_count++; - process_friend_queue (target_friend); -} - - -/** - * Send trail rejection message to target friend - * @param source_peer Peer which is trying to setup the trail. - * @param ultimate_destination_finger_value Peer closest to this value will be - * @a source_peer's finger - * @param congested_peer Peer which sent this message as it is congested. - * @param is_predecessor Is source_peer looking for trail to a predecessor or not. - * @param trail_peer_list Trails seen so far in trail setup before getting rejected - * by congested_peer. This does NOT include @a source_peer - * and congested_peer. - * @param trail_length Total number of peers in trail_peer_list, NOT including - * @a source_peer and @a congested_peer - * @param trail_id Unique identifier of this trail. - * @param congestion_timeout Duration given by congested peer as an estimate of - * how long it may remain congested. - */ -void -GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer, - uint64_t ultimate_destination_finger_value, - struct GNUNET_PeerIdentity congested_peer, - unsigned int is_predecessor, - const struct GNUNET_PeerIdentity *trail_peer_list, - unsigned int trail_length, - struct GNUNET_HashCode trail_id, - struct FriendInfo *target_friend, - const struct GNUNET_TIME_Relative congestion_timeout) -{ - struct PeerTrailRejectionMessage *trm; - struct P2PPendingMessage *pending; - struct GNUNET_PeerIdentity *peer_list; - size_t msize; - - msize = sizeof (struct PeerTrailRejectionMessage) + - (trail_length * sizeof (struct GNUNET_PeerIdentity)); - - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - GNUNET_break (0); - return; - } - - if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) - { - GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), - 1, GNUNET_NO); - } - - pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); - pending->importance = 0; - pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); - trm = (struct PeerTrailRejectionMessage *)&pending[1]; - pending->msg = &trm->header; - trm->header.size = htons (msize); - trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION); - trm->source_peer = source_peer; - trm->congested_peer = congested_peer; - trm->congestion_time = congestion_timeout; - trm->is_predecessor = htonl (is_predecessor); - trm->trail_id = trail_id; - trm->ultimate_destination_finger_value = - GNUNET_htonll (ultimate_destination_finger_value); - - peer_list = (struct GNUNET_PeerIdentity *) &trm[1]; - if (trail_length > 0) - { - memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity)); - } - - /* Send the message to chosen friend. */ - GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); - target_friend->pending_count++; - process_friend_queue (target_friend); -} - - -/** - * Construct a verify successor message and forward it to target_friend. - * @param source_peer Peer which wants to verify its successor. - * @param successor Peer which is @a source_peer's current successor. - * @param trail_id Unique Identifier of trail from @a source_peer to @a successor, - * NOT including them. - * @param trail List of peers which are part of trail to reach from @a source_peer - * to @a successor, NOT including them. - * @param trail_length Total number of peers in @a trail. - * @param target_friend Next friend to get this message. - */ -void -GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer, - struct GNUNET_PeerIdentity successor, - struct GNUNET_HashCode trail_id, - struct GNUNET_PeerIdentity *trail, - unsigned int trail_length, - struct FriendInfo *target_friend) -{ - struct PeerVerifySuccessorMessage *vsm; - struct P2PPendingMessage *pending; - struct GNUNET_PeerIdentity *peer_list; - size_t msize; - - msize = sizeof (struct PeerVerifySuccessorMessage) + - (trail_length * sizeof (struct GNUNET_PeerIdentity)); - - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - GNUNET_break (0); - return; - } - - if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) - { - GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), - 1, GNUNET_NO); - } - - pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); - pending->importance = 0; /* FIXME */ - pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); - vsm = (struct PeerVerifySuccessorMessage *) &pending[1]; - pending->msg = &vsm->header; - vsm->header.size = htons (msize); - vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR); - vsm->source_peer = source_peer; - vsm->successor = successor; - vsm->trail_id = trail_id; - peer_list = (struct GNUNET_PeerIdentity *) &vsm[1]; - memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity)); - - /* Send the message to chosen friend. */ - GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); - target_friend->pending_count++; - process_friend_queue (target_friend); -} - - -/** - * FIXME: In every function we pass target friend except for this one. - * so, either change everything or this one. also, should se just store - * the pointer to friend in routing table rather than gnunet_peeridentity. - * if yes then we should keep friend info in.h andmake lot of changes. - * Construct a trail teardown message and forward it to target friend. - * - * @param trail_id Unique identifier of the trail. - * @param trail_direction Direction of trail. - * @param target_friend Friend to get this message. - */ -void -GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_HashCode *trail_id, - unsigned int trail_direction, - const struct GNUNET_PeerIdentity *peer) -{ - struct PeerTrailTearDownMessage *ttdm; - struct P2PPendingMessage *pending; - struct FriendInfo *target_friend; - size_t msize; - - msize = sizeof (struct PeerTrailTearDownMessage); - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - GNUNET_break (0); - return; - } - - if (NULL == (target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer))) - { - /* FIXME: In what case friend can be null. ?*/ - GNUNET_break (0); - return; - } - - if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) - { - GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), - 1, GNUNET_NO); - } - - pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); - pending->importance = 0; /* FIXME */ - pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); - ttdm = (struct PeerTrailTearDownMessage *) &pending[1]; - pending->msg = &ttdm->header; - ttdm->header.size = htons (msize); - ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN); - ttdm->trail_id = *trail_id; - ttdm->trail_direction = htonl (trail_direction); - - /* Send the message to chosen friend. */ - GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); - target_friend->pending_count++; - process_friend_queue (target_friend); -} - - -/** - * Construct a verify successor result message and send it to target_friend - * @param querying_peer Peer which sent the verify successor message. - * @param source_successor Current_successor of @a querying_peer. - * @param current_predecessor Current predecessor of @a successor. Could be same - * or different from @a querying_peer. - * @param trail_id Unique identifier of the trail from @a querying_peer to - * @a successor, NOT including them. - * @param trail List of peers which are part of trail from @a querying_peer to - * @a successor, NOT including them. - * @param trail_length Total number of peers in @a trail - * @param trail_direction Direction in which we are sending the message. In this - * case we are sending result from @a successor to @a querying_peer. - * @param target_friend Next friend to get this message. - */ -void -GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer, - struct GNUNET_PeerIdentity current_successor, - struct GNUNET_PeerIdentity probable_successor, - struct GNUNET_HashCode trail_id, - const struct GNUNET_PeerIdentity *trail, - unsigned int trail_length, - enum GDS_ROUTING_trail_direction trail_direction, - struct FriendInfo *target_friend) -{ - struct PeerVerifySuccessorResultMessage *vsmr; - struct P2PPendingMessage *pending; - struct GNUNET_PeerIdentity *peer_list; - size_t msize; - - msize = sizeof (struct PeerVerifySuccessorResultMessage) + - (trail_length * sizeof(struct GNUNET_PeerIdentity)); - - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - GNUNET_break (0); - return; - } - - if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) - { - GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), - 1, GNUNET_NO); - } - - pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); - pending->importance = 0; /* FIXME */ - pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); - vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1]; - pending->msg = &vsmr->header; - vsmr->header.size = htons (msize); - vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT); - vsmr->querying_peer = querying_peer; - vsmr->current_successor = current_successor; - vsmr->probable_successor = probable_successor; - vsmr->trail_direction = htonl (trail_direction); - vsmr->trail_id = trail_id; - peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1]; - memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity)); - - /* Send the message to chosen friend. */ - GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); - target_friend->pending_count++; - process_friend_queue (target_friend); -} - - -/** - * Construct a notify new successor message and send it to target_friend - * @param source_peer Peer which wants to notify to its new successor that it - * could be its predecessor. - * @param successor New successor of @a source_peer - * @param successor_trail List of peers in Trail to reach from - * @a source_peer to @a new_successor, NOT including - * the endpoints. - * @param successor_trail_length Total number of peers in @a new_successor_trail. - * @param successor_trail_id Unique identifier of @a new_successor_trail. - * @param target_friend Next friend to get this message. - */ -void -GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer, - struct GNUNET_PeerIdentity successor, - const struct GNUNET_PeerIdentity *successor_trail, - unsigned int successor_trail_length, - struct GNUNET_HashCode succesor_trail_id, - struct FriendInfo *target_friend) -{ - struct PeerNotifyNewSuccessorMessage *nsm; - struct P2PPendingMessage *pending; - struct GNUNET_PeerIdentity *peer_list; - size_t msize; - - msize = sizeof (struct PeerNotifyNewSuccessorMessage) + - (successor_trail_length * sizeof(struct GNUNET_PeerIdentity)); - - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - GNUNET_break (0); - return; - } - - if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) - { - GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), - 1, GNUNET_NO); - } - - pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); - pending->importance = 0; /* FIXME */ - pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); - nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1]; - pending->msg = &nsm->header; - nsm->header.size = htons (msize); - nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR); - nsm->new_successor = successor; - nsm->source_peer = source_peer; - nsm->trail_id = succesor_trail_id; - peer_list = (struct GNUNET_PeerIdentity *) &nsm[1]; - memcpy (peer_list, successor_trail, - successor_trail_length * sizeof (struct GNUNET_PeerIdentity)); - - /* Send the message to chosen friend. */ - GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); - target_friend->pending_count++; - process_friend_queue (target_friend); -} - - -/** - * Construct an add_trail message and send it to target_friend - * @param source_peer Source of the trail. - * @param destination_peer Destination of the trail. - * @param trail_id Unique identifier of the trail from - * @a source_peer to @a destination_peer, NOT including the endpoints. - * @param trail List of peers in Trail from @a source_peer to @a destination_peer, - * NOT including the endpoints. - * @param trail_length Total number of peers in @a trail. - * @param target_friend Next friend to get this message. - */ -void -GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer, - struct GNUNET_PeerIdentity destination_peer, - struct GNUNET_HashCode trail_id, - const struct GNUNET_PeerIdentity *trail, - unsigned int trail_length, - struct FriendInfo *target_friend) -{ - struct PeerAddTrailMessage *adm; - struct GNUNET_PeerIdentity *peer_list; - struct P2PPendingMessage *pending; - size_t msize; - - msize = sizeof (struct PeerAddTrailMessage) + - (trail_length * sizeof(struct GNUNET_PeerIdentity)); - - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - GNUNET_break (0); - return; - } - - if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) - { - GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), - 1, GNUNET_NO); - } - - pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); - pending->importance = 0; /* FIXME */ - pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); - adm = (struct PeerAddTrailMessage *) &pending[1]; - pending->msg = &adm->header; - adm->header.size = htons (msize); - adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL); - adm->source_peer = source_peer; - adm->destination_peer = destination_peer; - adm->trail_id = trail_id; - peer_list = (struct GNUNET_PeerIdentity *)&adm[1]; - memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length); - - /* Send the message to chosen friend. */ - GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); - target_friend->pending_count++; - process_friend_queue (target_friend); - -} - - -/** - * Search my location in trail. In case I am present more than once in the - * trail (can happen during trail setup), then return my lowest index. - * @param trail List of peers - * @return my_index if found - * trail_length + 1 if an entry is present twice, It is an error. - * -1 if no entry found. - */ -static int -search_my_index (const struct GNUNET_PeerIdentity *trail, - int trail_length) -{ - int i; - int index_seen = trail_length + 1; - int flag = 0; - - for (i = 0; i < trail_length; i++) - { - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i])) - { - flag = 1; - if(index_seen == (trail_length + 1)) - index_seen = i; - else - { - DEBUG("Entry is present twice in trail. Its not allowed\n"); - } - break; - } - } - - if (1 == flag) - return index_seen; - else - return -1; -} - - -/** - * Check if the friend is congested or have reached maximum number of trails - * it can be part of of. - * @param friend Friend to be checked. - * @return #GNUNET_NO if friend is not congested or have not crossed threshold. - * #GNUNET_YES if friend is either congested or have crossed threshold - */ -static int -is_friend_congested (struct FriendInfo *friend) -{ - if (( friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) && - ((0 == GNUNET_TIME_absolute_get_remaining - (friend->congestion_timestamp).rel_value_us))) - return GNUNET_NO; - else - return GNUNET_YES; -} - - -/** - * Select closest finger to value. - * @param peer1 First peer - * @param peer2 Second peer - * @param value Value to be compare - * @return Closest peer - */ -static struct GNUNET_PeerIdentity -select_closest_finger (const struct GNUNET_PeerIdentity *peer1, - const struct GNUNET_PeerIdentity *peer2, - uint64_t value) -{ - uint64_t peer1_value; - uint64_t peer2_value; - - memcpy (&peer1_value, peer1, sizeof (uint64_t)); - memcpy (&peer2_value, peer2, sizeof (uint64_t)); - peer1_value = GNUNET_ntohll (peer1_value); - peer2_value = GNUNET_ntohll (peer2_value); - - if (peer1_value == value) - { - return *peer1; - } - - if (peer2_value == value) - { - return *peer2; - } - - if (value < peer1_value && peer1_value < peer2_value) - { - return *peer1; - } - else if (value < peer2_value && peer2_value < peer1_value) - { - return *peer2; - } - else if (peer1_value < value && value < peer2_value) - { - return *peer2; - } - else if (peer2_value < value && value < peer1_value) - { - return *peer1; - } - else if (peer1_value < peer2_value && peer2_value < value) - { - return *peer1; - } - else // if (peer2_value < peer1_value && peer1_value < value) - { - return *peer2; - } -} - - -/** - * Select closest predecessor to value. - * @param peer1 First peer - * @param peer2 Second peer - * @param value Value to be compare - * @return Peer which precedes value in the network. - */ -static struct GNUNET_PeerIdentity -select_closest_predecessor (const struct GNUNET_PeerIdentity *peer1, - const struct GNUNET_PeerIdentity *peer2, - uint64_t value) -{ - uint64_t peer1_value; - uint64_t peer2_value; - - memcpy (&peer1_value, peer1, sizeof (uint64_t)); - memcpy (&peer2_value, peer2, sizeof (uint64_t)); - peer1_value = GNUNET_ntohll (peer1_value); - peer2_value = GNUNET_ntohll (peer2_value); - - if (peer1_value == value) - { - return *peer1; - } - - if (peer2_value == value) - { - return *peer2; - } - - if (value < peer1_value && peer1_value < peer2_value) - { - return *peer2; - } - else if (value < peer2_value && peer2_value < peer1_value) - { - return *peer1; - } - else if (peer1_value < value && value < peer2_value) - { - return *peer1; - } - else if (peer2_value < value && value < peer1_value) - { - return *peer2; - } - else if (peer1_value < peer2_value && peer2_value < value) - { - return *peer2; - } - else // if (peer2_value < peer1_value && peer1_value < value) - { - return *peer1; - } -} - -#if 0 -/** - * - * - */ -void -test_print_trail (struct GNUNET_PeerIdentity *trail, - unsigned int trail_length) -{ - struct GNUNET_PeerIdentity print_peer; - int i; - - FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail_length = %d"), - __FILE__, __func__,__LINE__,trail_length); - for (i =0 ; i< trail_length; i++) - { - print_peer = trail[i]; - FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d]=%s"), - __FILE__, __func__,__LINE__,i,GNUNET_i2s(&print_peer)); - } -} -#endif - -#if 0 -/** - * This is a test function to print all the entries of friend table. - */ -static void -test_friend_peermap_print () -{ - struct FriendInfo *friend; - struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter; - struct GNUNET_PeerIdentity print_peer; - struct GNUNET_PeerIdentity key_ret; - int i; - - print_peer = my_identity; - FPRINTF (stderr,_("\nSUPU************ FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer)); - friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap); - - for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++) - { - if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter, - &key_ret, - (const void **)&friend)) - { - memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity)); - FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"), - __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count); - } - } -} -#endif - -#if 0 -/** - * This is a test function, to print all the entries of finger table. - */ -static void -test_finger_table_print() -{ - struct FingerInfo *finger; - struct GNUNET_PeerIdentity print_peer; - //struct Trail *trail; - int i; - //int j; - //int k; - print_peer = my_identity; - FPRINTF (stderr,_("\nSUPU************ FINGER_TABLE of %s"),GNUNET_i2s(&print_peer)); - for (i = 0; i < MAX_FINGERS; i++) - { - finger = &finger_table[i]; - - if (GNUNET_NO == finger->is_present) - continue; - - print_peer = finger->finger_identity; - FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"), - __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count); - -#if 0 - for (j = 0; j < finger->trails_count; j++) - { - trail = &finger->trail_list[j]; - FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id)); - struct Trail_Element *element; - element = trail->trail_head; - for (k = 0; k < trail->trail_length; k++) - { - print_peer = element->peer; - FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer)); - element = element->next; - } - } - #endif - } -} -#endif - -/** - * Select the closest peer among two peers (which should not be same) - * with respect to value and finger_table_index - * NOTE: peer1 != peer2 - * @param peer1 First peer - * @param peer2 Second peer - * @param value Value relative to which we find the closest - * @param is_predecessor Is value a predecessor or any other finger. - * @return Closest peer among two peers. - */ -static struct GNUNET_PeerIdentity -select_closest_peer (const struct GNUNET_PeerIdentity *peer1, - const struct GNUNET_PeerIdentity *peer2, - uint64_t value, - unsigned int is_predecessor) -{ - /* This check is here to ensure that calling function never sends - same peer value in peer1 and peer2. Remove it later. */ - GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, peer2)); - if (1 == is_predecessor) - return select_closest_predecessor (peer1, peer2, value); - - // TODO: Change name to something like select_closest_successor!! - return select_closest_finger (peer1, peer2, value); -} - - -/** - * Iterate over the list of all the trails of a finger. In case the first - * friend to reach the finger has reached trail threshold or is congested, - * then don't select it. In case there multiple available good trails to reach - * to Finger, choose the one with shortest trail length. - * Note: We use length as parameter. But we can use any other suitable parameter - * also. - * @param finger Finger Finger whose trail we have to select. - * @return Trail Selected Trail. - */ -static struct Trail * -select_finger_trail (struct FingerInfo *finger) -{ - struct FriendInfo *friend; - struct Trail *current_finger_trail; - struct Trail *best_trail = NULL; - unsigned int i; - - GNUNET_assert (finger->trails_count > 0); - for (i = 0; i < finger->trails_count; i++) - { - current_finger_trail = &finger->trail_list[i]; - - /* No trail stored at this index. */ - if (GNUNET_NO == current_finger_trail->is_present) - continue; - - GNUNET_assert (NULL != - (friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - ¤t_finger_trail->trail_head->peer))); - - /* First friend to reach trail is not free. */ - if (GNUNET_YES == is_friend_congested (friend)) - continue; - - if (NULL == best_trail || - best_trail->trail_length > current_finger_trail->trail_length) - { - best_trail = current_finger_trail; - } - } - - return best_trail; -} - - -/** - * Compare FINGER entry with current successor. If finger's first friend of all - * its trail is not congested and has not crossed trail threshold, then check - * if finger peer identity is closer to final_destination_finger_value than - * current_successor. If yes then update current_successor. - * @param current_successor[in/out] - * @return - */ -static void -compare_finger_and_current_closest_peer (struct Closest_Peer *current_closest_peer) -{ - struct FingerInfo *finger; - struct GNUNET_PeerIdentity closest_peer; - struct Trail *finger_trail; - int i; - - /* Iterate over finger table. */ - for (i = 0; i < MAX_FINGERS; i++) - { - finger = &finger_table[i]; - - if (GNUNET_NO == finger->is_present) - continue; - - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity, - ¤t_closest_peer->best_known_destination)) - continue; - - /* If I am my own finger, then ignore this finger. */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity, - &my_identity)) - continue; - - /* If finger is a friend, we have already checked it in previous function. */ - if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &finger->finger_identity))) - { - continue; - } - - closest_peer = select_closest_peer (&finger->finger_identity, - ¤t_closest_peer->best_known_destination, - current_closest_peer->destination_finger_value, - current_closest_peer->is_predecessor); - - if (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->finger_identity, &closest_peer)) - { - /* Choose one of the trail to reach to finger. */ - finger_trail = select_finger_trail (finger); - - /* In case no trail found, ignore this finger. */ - if (NULL == finger_trail) - continue; - - current_closest_peer->best_known_destination = closest_peer; - current_closest_peer->next_hop = finger_trail->trail_head->peer; - current_closest_peer->trail_id = finger_trail->trail_id; - current_closest_peer->finger_table_index = i; - } - continue; - } -} - - -/** - * Compare friend entry with current successor. - * If friend identity and current_successor is same, then do nothing. - * If friend is not congested and has not crossed trail threshold, then check - * if friend peer identity is closer to final_destination_finger_value than - * current_successor. If yes then update current_successor. - * @param cls closure - * @param key current public key - * @param value struct Closest_Peer - * @return #GNUNET_YES if we should continue to iterate, - * #GNUNET_NO if not. - */ -static int -compare_friend_and_current_closest_peer (void *cls, - const struct GNUNET_PeerIdentity *key, - void *value) -{ - struct FriendInfo *friend = value; - struct Closest_Peer *current_closest_peer = cls; - struct GNUNET_PeerIdentity closest_peer; - - /* Friend is either congested or has crossed threshold. */ - if (GNUNET_YES == is_friend_congested (friend)) - return GNUNET_YES; - - /* If current_closest_peer and friend identity are same, then do nothing.*/ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id, - ¤t_closest_peer->best_known_destination)) - { - GNUNET_break (0); - return GNUNET_YES; - } - - closest_peer = select_closest_peer (&friend->id, - ¤t_closest_peer->best_known_destination, - current_closest_peer->destination_finger_value, - current_closest_peer->is_predecessor); - - /* Is friend the closest successor? */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id, &closest_peer)) - { - current_closest_peer->best_known_destination = friend->id; - current_closest_peer->next_hop = friend->id; - } - - return GNUNET_YES; -} - - -/** - * Initialize current_successor to my_identity. - * @param my_identity My peer identity - * @return Updated closest_peer - */ -static struct Closest_Peer -init_closest_peer (struct GNUNET_PeerIdentity my_identity, - uint64_t destination_finger_value, - unsigned int is_predecessor) -{ - struct Closest_Peer current_closest_peer; - - memset (¤t_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode)); - current_closest_peer.destination_finger_value = destination_finger_value; - current_closest_peer.is_predecessor = is_predecessor; - current_closest_peer.next_hop = my_identity; - current_closest_peer.best_known_destination = my_identity; - current_closest_peer.finger_table_index = 65; //65 is a for non valid finger table index. - return current_closest_peer; -} - - -/** - * Find locally best known peer, among your own identity, friend and finger list, - * which is closest to given destination_finger_value. - * - * NOTE: In case a friend is also a finger, then it is always chosen as friend - * not a finger. - * @param destination_finger_value Peer closest to this value will be the next destination. - * @param is_predecessor Are we looking for predecessor or finger? - * @return Closest_Peer that contains all the relevant field to reach to - * @a destination_finger_value - */ -static struct Closest_Peer -find_local_best_known_next_hop (uint64_t destination_finger_value, - unsigned int is_predecessor) -{ - struct Closest_Peer current_closest_peer; - - /* Initialize current_successor to my_identity. */ - current_closest_peer = init_closest_peer (my_identity, - destination_finger_value, - is_predecessor); - - /* Compare each friend entry with current_successor and update current_successor - * with friend if its closest. */ - GNUNET_assert - (GNUNET_SYSERR != - GNUNET_CONTAINER_multipeermap_iterate (friend_peermap, - &compare_friend_and_current_closest_peer, - ¤t_closest_peer)); - - /* Compare each finger entry with current_successor and update current_successor - * with finger if its closest. */ - compare_finger_and_current_closest_peer (¤t_closest_peer); - return current_closest_peer; -} - - -/** - * Construct a Put message and send it to target_peer. - * @param key Key for the content - * @param block_type Type of the block - * @param options Routing options - * @param desired_replication_level Desired replication count - * @param best_known_dest Peer to which this message should reach eventually, - * as it is best known destination to me. - * @param intermediate_trail_id Trail id in case - * @param target_peer Peer to which this message will be forwarded. - * @param hop_count Number of hops traversed so far. - * @param put_path_length Total number of peers in @a put_path - * @param put_path Number of peers traversed so far - * @param expiration_time When does the content expire - * @param data Content to store - * @param data_size Size of content @a data in bytes - */ -void -GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key, - enum GNUNET_BLOCK_Type block_type, - enum GNUNET_DHT_RouteOption options, - uint32_t desired_replication_level, - struct GNUNET_PeerIdentity best_known_dest, - struct GNUNET_HashCode intermediate_trail_id, - struct GNUNET_PeerIdentity *target_peer, - uint32_t hop_count, - uint32_t put_path_length, - struct GNUNET_PeerIdentity *put_path, - struct GNUNET_TIME_Absolute expiration_time, - const void *data, size_t data_size) -{ - struct PeerPutMessage *ppm; - struct P2PPendingMessage *pending; - struct FriendInfo *target_friend; - struct GNUNET_PeerIdentity *pp; - size_t msize; - - msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size + - sizeof (struct PeerPutMessage); - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - put_path_length = 0; - msize = data_size + sizeof (struct PeerPutMessage); - } - - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - DEBUG("msize = %lu\n",msize); - GNUNET_break (0); - return; - } - - GNUNET_assert (NULL != - (target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); - pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); - pending->timeout = expiration_time; - ppm = (struct PeerPutMessage *) &pending[1]; - pending->msg = &ppm->header; - ppm->header.size = htons (msize); - ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT); - ppm->options = htonl (options); - ppm->block_type = htonl (block_type); - ppm->hop_count = htonl (hop_count + 1); - ppm->desired_replication_level = htonl (desired_replication_level); - ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time); - ppm->best_known_destination = best_known_dest; - ppm->intermediate_trail_id = intermediate_trail_id; - ppm->key = *key; - pp = (struct GNUNET_PeerIdentity *) &ppm[1]; - ppm->put_path_length = htonl (put_path_length); - if(put_path_length > 0) - { - memcpy (pp, put_path, - sizeof (struct GNUNET_PeerIdentity) * put_path_length); - } - memcpy (&pp[put_path_length], data, data_size); - GNUNET_assert (NULL != target_friend); - GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); - target_friend->pending_count++; - process_friend_queue (target_friend); -} - - -/** - * Handle the put request from the client. - * @param key Key for the content - * @param block_type Type of the block - * @param options Routing options - * @param desired_replication_level Desired replication count - * @param expiration_time When does the content expire - * @param data Content to store - * @param data_size Size of content @a data in bytes - */ -void -GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key, - enum GNUNET_BLOCK_Type block_type, - enum GNUNET_DHT_RouteOption options, - uint32_t desired_replication_level, - struct GNUNET_TIME_Absolute expiration_time, - const void *data, size_t data_size) -{ - struct GNUNET_PeerIdentity best_known_dest; - struct GNUNET_HashCode intermediate_trail_id; - struct GNUNET_PeerIdentity next_hop; - uint64_t key_value; - struct Closest_Peer successor; - - memcpy (&key_value, key, sizeof (uint64_t)); - key_value = GNUNET_ntohll (key_value); - successor = find_local_best_known_next_hop (key_value, - GDS_FINGER_TYPE_NON_PREDECESSOR); - best_known_dest = successor.best_known_destination; - next_hop = successor.next_hop; - intermediate_trail_id = successor.trail_id; - - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)) - { - DEBUG("\n PUT_REQUEST_SUCCESSFUL for key = %s",GNUNET_h2s(key)); - /* I am the destination. */ - GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL, - block_type,data_size,data); - GDS_CLIENTS_process_put (options, block_type, 0, - ntohl (desired_replication_level), - 1, &my_identity, expiration_time, //FIXME: GNUNETnthoh something on expiration time. - key, data, data_size); - return; - } - /* In case we are sending the request to a finger, then send across all of its - trail.*/ -#if ENABLE_MALICIOUS - if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination, - &successor.next_hop)) - { - struct FingerInfo *next_hop_finger; - unsigned int i; - - next_hop_finger = &finger_table[successor.finger_table_index]; - for (i = 0; i < next_hop_finger->trails_count; i++) - { - if (GNUNET_YES == next_hop_finger->trail_list[i].is_present) - { - if(0 == next_hop_finger->trail_list[i].trail_length) - { - GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level, - best_known_dest, intermediate_trail_id, &next_hop, - 0, 1, &my_identity, expiration_time, - data, data_size); - return; - } - next_hop = next_hop_finger->trail_list[i].trail_head->peer; - GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level, - best_known_dest, - next_hop_finger->trail_list[i].trail_id, - &next_hop, 0, 1, &my_identity, - expiration_time, - data, data_size); - } - } - return; - } -#endif - GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level, - best_known_dest, intermediate_trail_id, &next_hop, - 0, 1, &my_identity, expiration_time, - data, data_size); -} - -/** - * Construct a Get message and send it to target_peer. - * @param key Key for the content - * @param block_type Type of the block - * @param options Routing options - * @param desired_replication_level Desired replication count - * @param best_known_dest Peer which should get this message. Same as target peer - * if best_known_dest is a friend else its a finger. - * @param intermediate_trail_id Trail id to reach to @a best_known_dest - * in case it is a finger else set to 0. - * @param target_peer Peer to which this message will be forwarded. - * @param hop_count Number of hops traversed so far. - * @param data Content to store - * @param data_size Size of content @a data in bytes - * @param get_path_length Total number of peers in @a get_path - * @param get_path Number of peers traversed so far - */ -void -GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key, - enum GNUNET_BLOCK_Type block_type, - enum GNUNET_DHT_RouteOption options, - uint32_t desired_replication_level, - struct GNUNET_PeerIdentity best_known_dest, - struct GNUNET_HashCode intermediate_trail_id, - struct GNUNET_PeerIdentity *target_peer, - uint32_t hop_count, - uint32_t get_path_length, - struct GNUNET_PeerIdentity *get_path) -{ - struct PeerGetMessage *pgm; - struct P2PPendingMessage *pending; - struct FriendInfo *target_friend; - struct GNUNET_PeerIdentity *gp; - size_t msize; - - msize = sizeof (struct PeerGetMessage) + - (get_path_length * sizeof (struct GNUNET_PeerIdentity)); - - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - GNUNET_break (0); - return; - } - GNUNET_assert (NULL != - (target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); - - pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); - pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); - pending->importance = 0; /* FIXME */ - pgm = (struct PeerGetMessage *) &pending[1]; - pending->msg = &pgm->header; - pgm->header.size = htons (msize); - pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET); - pgm->get_path_length = htonl (get_path_length); - pgm->best_known_destination = best_known_dest; - pgm->key = *key; - pgm->intermediate_trail_id = intermediate_trail_id; - pgm->hop_count = htonl (hop_count + 1); - pgm->get_path_length = htonl (get_path_length); - gp = (struct GNUNET_PeerIdentity *) &pgm[1]; - memcpy (gp, get_path, - sizeof (struct GNUNET_PeerIdentity) * get_path_length); - GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); - target_friend->pending_count++; - process_friend_queue (target_friend); -} - - -/** - * Handle the get request from the client file. If I am destination do - * datacache put and return. Else find the target friend and forward message - * to it. - * @param key Key for the content - * @param block_type Type of the block - * @param options Routing options - * @param desired_replication_level Desired replication count - */ -void -GDS_NEIGHBOURS_handle_get(const struct GNUNET_HashCode *key, - enum GNUNET_BLOCK_Type block_type, - enum GNUNET_DHT_RouteOption options, - uint32_t desired_replication_level) -{ - struct Closest_Peer successor; - struct GNUNET_PeerIdentity best_known_dest; - struct GNUNET_HashCode intermediate_trail_id; - uint64_t key_value; - - memcpy (&key_value, key, sizeof (uint64_t)); - key_value = GNUNET_ntohll (key_value); - - successor = find_local_best_known_next_hop (key_value, - GDS_FINGER_TYPE_NON_PREDECESSOR); - - best_known_dest = successor.best_known_destination; - intermediate_trail_id = successor.trail_id; - - /* I am the destination. I have the data. */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, - &best_known_dest)) - { - GDS_DATACACHE_handle_get (key,block_type, NULL, 0, - NULL, 0, 1, &my_identity, NULL,&my_identity); - return; - } - -#if ENABLE_MALICIOUS - struct GNUNET_PeerIdentity next_hop; - if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination, - &successor.next_hop)) - { - struct FingerInfo *next_hop_finger; - unsigned int i; - - next_hop_finger = &finger_table[successor.finger_table_index]; - for (i = 0; i < next_hop_finger->trails_count; i++) - { - if (GNUNET_YES == next_hop_finger->trail_list[i].is_present) - { - if(0 == next_hop_finger->trail_list[i].trail_length) - { - GDS_NEIGHBOURS_send_get (key, block_type, options, - desired_replication_level, - best_known_dest,intermediate_trail_id, - &successor.next_hop, - 0, 1, &my_identity); - return; - } - next_hop = next_hop_finger->trail_list[i].trail_head->peer; - GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level, - best_known_dest, - next_hop_finger->trail_list[i].trail_id, - &next_hop, 0, 1, &my_identity); - } - } - return; - } -#endif - GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level, - best_known_dest,intermediate_trail_id, &successor.next_hop, - 0, 1, &my_identity); -} - - -/** - * Send the get result to requesting client. - * - * @param key Key of the requested data. - * @param type Block type - * @param target_peer Next peer to forward the message to. - * @param source_peer Peer which has the data for the key. - * @param put_path_length Number of peers in @a put_path - * @param put_path Path taken to put the data at its stored location. - * @param get_path_length Number of peers in @a get_path - * @param get_path Path taken to reach to the location of the key. - * @param expiration When will this result expire? - * @param data Payload to store - * @param data_size Size of the @a data - */ -void -GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key, - enum GNUNET_BLOCK_Type type, - const struct GNUNET_PeerIdentity *target_peer, - const struct GNUNET_PeerIdentity *source_peer, - unsigned int put_path_length, - const struct GNUNET_PeerIdentity *put_path, - unsigned int get_path_length, - const struct GNUNET_PeerIdentity *get_path, - struct GNUNET_TIME_Absolute expiration, - const void *data, size_t data_size) -{ - struct PeerGetResultMessage *get_result; - struct GNUNET_PeerIdentity *paths; - struct P2PPendingMessage *pending; - struct FriendInfo *target_friend; - int current_path_index; - size_t msize; - - msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) + - data_size + - sizeof (struct PeerGetResultMessage); - - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - put_path_length = 0; - msize = msize - put_path_length * sizeof (struct GNUNET_PeerIdentity); - } - - if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) - { - GNUNET_break(0); - return; - } - current_path_index = 0; - if(get_path_length > 0) - { - current_path_index = search_my_index(get_path, get_path_length); - if (-1 == current_path_index) - { - GNUNET_break (0); - return; - } - if ((get_path_length + 1) == current_path_index) - { - DEBUG ("Peer found twice in get path. Not allowed \n"); - GNUNET_break (0); - return; - } - } - if (0 == current_path_index) - { - DEBUG ("GET_RESULT TO CLIENT KEY = %s, Peer = %s",GNUNET_h2s(key),GNUNET_i2s(&my_identity)); - GDS_CLIENTS_handle_reply (expiration, key, get_path_length, - get_path, put_path_length, - put_path, type, data_size, data); - return; - } - - pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); - pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); - pending->importance = 0; - get_result = (struct PeerGetResultMessage *)&pending[1]; - pending->msg = &get_result->header; - get_result->header.size = htons (msize); - get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT); - get_result->key = *key; - get_result->querying_peer = *source_peer; - get_result->expiration_time = expiration; - get_result->get_path_length = htonl (get_path_length); - get_result->put_path_length = htonl (put_path_length); - paths = (struct GNUNET_PeerIdentity *)&get_result[1]; - memcpy (paths, put_path, - put_path_length * sizeof (struct GNUNET_PeerIdentity)); - memcpy (&paths[put_path_length], get_path, - get_path_length * sizeof (struct GNUNET_PeerIdentity)); - memcpy (&paths[put_path_length + get_path_length], data, data_size); - - GNUNET_assert (NULL != - (target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &get_path[current_path_index - 1]))); - GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); - target_friend->pending_count++; - process_friend_queue (target_friend); -} - - -/** - * Randomly choose one of your friends (which is not congested and have not crossed - * trail threshold) from the friend_peermap - * @return Friend Randomly chosen friend. - * NULL in case friend peermap is empty, or all the friends are either - * congested or have crossed trail threshold. - */ -static struct FriendInfo * -select_random_friend () -{ - unsigned int current_size; - uint32_t index; - unsigned int j = 0; - struct GNUNET_CONTAINER_MultiPeerMapIterator *iter; - struct GNUNET_PeerIdentity key_ret; - struct FriendInfo *friend; - - current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap); - - /* No friends.*/ - if (0 == current_size) - return NULL; - - index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size); - iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap); - - /* Iterate till you don't reach to index. */ - for (j = 0; j < index ; j++) - GNUNET_assert (GNUNET_YES == - GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL)); - - do - { - /* Reset the index in friend peermap to 0 as we reached to the end. */ - if (j == current_size) - { - j = 0; - GNUNET_CONTAINER_multipeermap_iterator_destroy (iter); - iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap); - - } - - /* Get the friend stored at the index, j*/ - GNUNET_assert (GNUNET_YES == - GNUNET_CONTAINER_multipeermap_iterator_next (iter, - &key_ret, - (const void **)&friend)); - - /* This friend is not congested and has not crossed trail threshold. */ - if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) && - (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us)) - { - break; - } - friend = NULL; - j++; - } while (j != index); - - GNUNET_CONTAINER_multipeermap_iterator_destroy (iter); - return friend; -} - - -/** - * Compute 64 bit value of finger_identity corresponding to a finger index using - * chord formula. - * For all fingers, n.finger[i] = n + pow (2,i), - * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where - * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value - * @param finger_index Index corresponding to which we calculate 64 bit value. - * @return 64 bit value. - */ -static uint64_t -compute_finger_identity_value (unsigned int finger_index) -{ - uint64_t my_id64; - - memcpy (&my_id64, &my_identity, sizeof (uint64_t)); - my_id64 = GNUNET_ntohll (my_id64); - - /* Are we looking for immediate predecessor? */ - if (PREDECESSOR_FINGER_ID == finger_index) - return (my_id64 - 1); - else - { - uint64_t add = (uint64_t)1 << finger_index; - return (my_id64 + add); - } -} - - -/* - * Choose a random friend. Calculate the next finger identity to search,from - * current_search_finger_index. Start looking for the trail to reach to - * finger identity through this random friend. - * - * @param cls closure for this task - * @param tc the context under which the task is running - */ -static void -send_find_finger_trail_message (void *cls, - const struct GNUNET_SCHEDULER_TaskContext *tc) -{ - struct FriendInfo *target_friend; - struct GNUNET_HashCode trail_id; - struct GNUNET_HashCode intermediate_trail_id; - unsigned int is_predecessor = 0; - uint64_t finger_id_value; - - /* Schedule another send_find_finger_trail_message task. After one round of - * finger search, this time is exponentially backoff. */ - find_finger_trail_task_next_send_time.rel_value_us = - find_finger_trail_task_next_send_time.rel_value_us + - GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, - DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us); - find_finger_trail_task = - GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time, - &send_find_finger_trail_message, - NULL); - - /* No space in my routing table. (Source and destination peers also store entries - * in their routing table). */ - if (GNUNET_YES == GDS_ROUTING_threshold_reached()) - return; - - target_friend = select_random_friend (); - if (NULL == target_friend) - { - return; - } - - finger_id_value = compute_finger_identity_value (current_search_finger_index); - if (PREDECESSOR_FINGER_ID == current_search_finger_index) - is_predecessor = 1; - - /* Generate a unique trail id for trail we are trying to setup. */ - GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG, - &trail_id, sizeof (trail_id)); - memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode)); - GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value, - target_friend->id, target_friend, 0, NULL, - is_predecessor, trail_id, - intermediate_trail_id); -} - - -/** - * In case there are already maximum number of possible trails to reach to a - * finger, then check if the new trail's length is lesser than any of the - * existing trails. - * If yes then replace that old trail by new trail. - * - * Note: Here we are taking length as a parameter to choose the best possible - * trail, but there could be other parameters also like: - * 1. duration of existence of a trail - older the better. - * 2. if the new trail is completely disjoint than the - * other trails, then may be choosing it is better. - * - * @param finger Finger - * @param new_finger_trail List of peers to reach from me to @a finger, NOT - * including the endpoints. - * @param new_finger_trail_length Total number of peers in @a new_finger_trail - * @param new_finger_trail_id Unique identifier of @a new_finger_trail. - */ -static void -select_and_replace_trail (struct FingerInfo *finger, - const struct GNUNET_PeerIdentity *new_trail, - unsigned int new_trail_length, - struct GNUNET_HashCode new_trail_id) -{ - struct Trail *current_trail; - unsigned int largest_trail_length; - unsigned int largest_trail_index; - struct Trail_Element *trail_element; - struct GNUNET_PeerIdentity *next_hop; - unsigned int i; - - largest_trail_length = new_trail_length; - largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1; - - GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count); - - for (i = 0; i < finger->trails_count; i++) - { - current_trail = &finger->trail_list[i]; - GNUNET_assert (GNUNET_YES == current_trail->is_present); - if (current_trail->trail_length > largest_trail_length) - { - largest_trail_length = current_trail->trail_length; - largest_trail_index = i; - } - } - - /* New trail is not better than existing ones. Send trail teardown. */ - if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1)) - { - next_hop = GDS_ROUTING_get_next_hop (new_trail_id, GDS_ROUTING_SRC_TO_DEST); - GDS_ROUTING_remove_trail (new_trail_id); - GDS_NEIGHBOURS_send_trail_teardown (&new_trail_id, - GDS_ROUTING_SRC_TO_DEST, - next_hop); - return; - } - - /* Send trail teardown message across the replaced trail. */ - struct Trail *replace_trail = &finger->trail_list[largest_trail_index]; - next_hop = GDS_ROUTING_get_next_hop (replace_trail->trail_id, GDS_ROUTING_SRC_TO_DEST); - GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id)); - GDS_NEIGHBOURS_send_trail_teardown (&replace_trail->trail_id, - GDS_ROUTING_SRC_TO_DEST, - next_hop); - - /* Free the trail. */ - while (NULL != (trail_element = replace_trail->trail_head)) - { - GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head, - replace_trail->trail_tail, trail_element); - GNUNET_free_non_null (trail_element); - } - - /* Add new trial at that location. */ - replace_trail->is_present = GNUNET_YES; - replace_trail->trail_length = new_trail_length; - replace_trail->trail_id = new_trail_id; - - for (i = 0; i < new_trail_length; i++) - { - struct Trail_Element *element = GNUNET_new (struct Trail_Element); - element->peer = new_trail[i]; - - GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head, - replace_trail->trail_tail, - element); - } - /* FIXME: URGENT Are we adding the trail back to the list. */ -} - - -/** - * Check if the new trail to reach to finger is unique or do we already have - * such a trail present for finger. - * @param existing_finger Finger identity - * @param new_trail New trail to reach @a existing_finger - * @param trail_length Total number of peers in new_trail. - * @return #GNUNET_YES if the new trail is unique - * #GNUNET_NO if same trail is already present. - */ -static int -is_new_trail_unique (struct FingerInfo *existing_finger, - const struct GNUNET_PeerIdentity *new_trail, - unsigned int trail_length) -{ - struct Trail *current_trail; - struct Trail_Element *trail_element; - int i; - int j; - - GNUNET_assert (existing_finger->trails_count > 0); - - /* Iterate over list of trails. */ - for (i = 0; i < existing_finger->trails_count; i++) - { - current_trail = &(existing_finger->trail_list[i]); - if(GNUNET_NO == current_trail->is_present) - continue; - - /* New trail and existing trail length are not same. */ - if (current_trail->trail_length != trail_length) - { - return GNUNET_YES; - } - - trail_element = current_trail->trail_head; - for (j = 0; j < current_trail->trail_length; j++) - { - if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j], - &trail_element->peer)) - { - return GNUNET_YES; - } - trail_element = trail_element->next; - } - } - return GNUNET_NO; -} - -/** - * FIXME; In case of multiple trails, we may have a case where a trail from in - * between has been removed, then we should try to find a free slot , not simply - * add a trail at then end of the list. - * Add a new trail at a free slot in trail array of existing finger. - * @param existing_finger Finger - * @param new_finger_trail New trail from me to finger, NOT including endpoints - * @param new_finger_trail_length Total number of peers in @a new_finger_trail - * @param new_finger_trail_id Unique identifier of the trail. - */ -static void -add_new_trail (struct FingerInfo *existing_finger, - const struct GNUNET_PeerIdentity *new_trail, - unsigned int new_trail_length, - struct GNUNET_HashCode new_trail_id) -{ - struct FriendInfo *friend; - struct Trail *trail; - unsigned int i; - int free_slot = -1; - - if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail, - new_trail_length)) - return; - - for (i = 0; i < existing_finger->trails_count; i++) - { - if (GNUNET_NO == existing_finger->trail_list[i].is_present) - { - free_slot = i; - break; - } - } - - if (-1 == free_slot) - free_slot = i; - - trail = &existing_finger->trail_list[free_slot]; - GNUNET_assert (GNUNET_NO == trail->is_present); - trail->trail_id = new_trail_id; - trail->trail_length = new_trail_length; - existing_finger->trails_count++; - trail->is_present = GNUNET_YES; - if (0 == new_trail_length) - { - friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &existing_finger->finger_identity); - } - else - { - friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &new_trail[0]); - } - GNUNET_assert (NULL != friend); - friend->trails_count++; - for (i = 0; i < new_trail_length; i++) - { - struct Trail_Element *element; - - element = GNUNET_new (struct Trail_Element); - element->peer = new_trail[i]; - GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head, - trail->trail_tail, - element); - } - - existing_finger->trail_list[free_slot].trail_head = trail->trail_head; - existing_finger->trail_list[free_slot].trail_tail = trail->trail_tail; - existing_finger->trail_list[free_slot].trail_length = new_trail_length; - existing_finger->trail_list[free_slot].trail_id = new_trail_id; - existing_finger->trail_list[free_slot].is_present = GNUNET_YES; -} - - -#if 0 -/** - * FIXME; In case of multiple trails, we may have a case where a trail from in - * between has been removed, then we should try to find a free slot , not simply - * add a trail at then end of the list. - * Add a new trail at a free slot in trail array of existing finger. - * @param existing_finger Finger - * @param new_finger_trail New trail from me to finger, NOT including endpoints - * @param new_finger_trail_length Total number of peers in @a new_finger_trail - * @param new_finger_trail_id Unique identifier of the trail. - */ -static void -add_new_trail (struct FingerInfo *existing_finger, - const struct GNUNET_PeerIdentity *new_trail, - unsigned int new_trail_length, - struct GNUNET_HashCode new_trail_id) -{ - struct Trail *trail; - struct FriendInfo *first_friend; - int i; - int index; - - if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail, - new_trail_length)) - return; - - index = existing_finger->trails_count; - trail = &existing_finger->trail_list[index]; - GNUNET_assert (GNUNET_NO == trail->is_present); - trail->trail_id = new_trail_id; - trail->trail_length = new_trail_length; - existing_finger->trails_count++; - trail->is_present = GNUNET_YES; - - GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &existing_finger->finger_identity))); - /* If finger is a friend then we never call this function. */ - GNUNET_assert (new_trail_length > 0); - - first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &new_trail[0]); - first_friend->trails_count++; - - for (i = 0; i < new_trail_length; i++) - { - struct Trail_Element *element; - - element = GNUNET_new (struct Trail_Element); - element->peer = new_trail[i]; - GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head, - trail->trail_tail, - element); - } - /* Do we need to add trail head and trail tail in the trail list itearator.*/ - existing_finger->trail_list[index].trail_head = trail->trail_head; - existing_finger->trail_list[index].trail_tail = trail->trail_tail; - existing_finger->trail_list[index].trail_length = new_trail_length; - existing_finger->trail_list[index].trail_id = new_trail_id; - existing_finger->trail_list[index].is_present = GNUNET_YES; -} -#endif - -/** - * Get the next hop to send trail teardown message from routing table and - * then delete the entry from routing table. Send trail teardown message for a - * specific trail of a finger. - * @param finger Finger whose trail is to be removed. - * @param trail List of peers in trail from me to a finger, NOT including - * endpoints. - */ -static void -send_trail_teardown (struct FingerInfo *finger, - struct Trail *trail) -{ - struct FriendInfo *friend; - struct GNUNET_PeerIdentity *next_hop; - - next_hop = GDS_ROUTING_get_next_hop (trail->trail_id, - GDS_ROUTING_SRC_TO_DEST); - if (NULL == next_hop) - { -// DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line=%d,traillength = %d", -// GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__,trail->trail_length); - return; - } - GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity, - &my_identity)); - - GNUNET_assert(GNUNET_YES == trail->is_present); - if (trail->trail_length > 0) - { - friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &trail->trail_head->peer); - } - else - { - friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &finger->finger_identity); - } - - if(NULL == friend) - { - DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d", - __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length); - return; - } - if (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id) - && (0 == trail->trail_length)) - { - DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d", - __LINE__,GNUNET_h2s(&trail->trail_id), GNUNET_i2s(&my_identity),trail->trail_length); - return; - } - GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id)); - friend->trails_count--; - GDS_NEIGHBOURS_send_trail_teardown (&trail->trail_id, - GDS_ROUTING_SRC_TO_DEST, - &friend->id); -} - - -/** - * Send trail teardown message across all the trails to reach to finger. - * @param finger Finger whose all the trail should be freed. - */ -static void -send_all_finger_trails_teardown (struct FingerInfo *finger) -{ - unsigned int i; - - for (i = 0; i < finger->trails_count; i++) - { - struct Trail *trail; - - trail = &finger->trail_list[i]; - if (GNUNET_YES == trail->is_present) - { - send_trail_teardown (finger, trail); - trail->is_present = GNUNET_NO; - } - } -} - - -/** - * Free a specific trail - * @param trail List of peers to be freed. - */ -static void -free_trail (struct Trail *trail) -{ - struct Trail_Element *trail_element; - - while (NULL != (trail_element = trail->trail_head)) - { - GNUNET_CONTAINER_DLL_remove (trail->trail_head, - trail->trail_tail, - trail_element); - GNUNET_free_non_null (trail_element); - } - trail->trail_head = NULL; - trail->trail_tail = NULL; -} - - -/** - * Free finger and its trail. - * @param finger Finger to be freed. - * @param finger_table_index Index at which finger is stored. - */ -static void -free_finger (struct FingerInfo *finger, unsigned int finger_table_index) -{ - struct Trail *trail; - unsigned int i; - for (i = 0; i < finger->trails_count; i++) - { - trail = &finger->trail_list[i]; - if (GNUNET_NO == trail->is_present) - continue; - - if (trail->trail_length > 0) - free_trail (trail); - trail->is_present = GNUNET_NO; - } - - finger->is_present = GNUNET_NO; - memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index])); -} - - -/** - * Add a new entry in finger table at finger_table_index. - * In case I am my own finger, then we don't have a trail. In case of a friend, - * we have a trail with unique id and '0' trail length. - * In case a finger is a friend, then increment the trails count of the friend. - * @param finger_identity Peer Identity of new finger - * @param finger_trail Trail to reach from me to finger (excluding both end points). - * @param finger_trail_length Total number of peers in @a finger_trail. - * @param trail_id Unique identifier of the trail. - * @param finger_table_index Index in finger table. - */ -static void -add_new_finger (struct GNUNET_PeerIdentity finger_identity, - const struct GNUNET_PeerIdentity *finger_trail, - unsigned int finger_trail_length, - struct GNUNET_HashCode trail_id, - unsigned int finger_table_index) -{ - struct FingerInfo *new_entry; - struct FriendInfo *first_trail_hop; - struct Trail *trail; - unsigned int i; - - new_entry = GNUNET_new (struct FingerInfo); - new_entry->finger_identity = finger_identity; - new_entry->finger_table_index = finger_table_index; - new_entry->is_present = GNUNET_YES; - - /* If the new entry is my own identity. */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, - &finger_identity)) - { - new_entry->trails_count = 0; - finger_table[finger_table_index] = *new_entry; - GNUNET_free (new_entry); - return; - } - - /* Finger is a friend. */ - if (0 == finger_trail_length) - { - new_entry->trail_list[0].trail_id = trail_id; - new_entry->trails_count = 1; - new_entry->trail_list[0].is_present = GNUNET_YES; - new_entry->trail_list[0].trail_length = 0; - new_entry->trail_list[0].trail_head = NULL; - new_entry->trail_list[0].trail_tail = NULL; - finger_table[finger_table_index] = *new_entry; - GNUNET_assert (NULL != - (first_trail_hop = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &finger_identity))); - - first_trail_hop->trails_count++; - GNUNET_free (new_entry); - return; - } - - GNUNET_assert (NULL != - (first_trail_hop = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &finger_trail[0]))); - new_entry->trails_count = 1; - first_trail_hop->trails_count++; - /* Copy the finger trail into trail. */ - trail = &new_entry->trail_list[0]; - for(i = 0; i < finger_trail_length; i++) - { - struct Trail_Element *element = GNUNET_new (struct Trail_Element); - - element->next = NULL; - element->prev = NULL; - element->peer = finger_trail[i]; - GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head, - trail->trail_tail, - element); - } - - /* Add trail to trail list. */ - trail->trail_length = finger_trail_length; - trail->trail_id = trail_id; - trail->is_present = GNUNET_YES; - finger_table[finger_table_index] = *new_entry; - GNUNET_free (new_entry); -} - - -/** - * Periodic task to verify current successor. There can be multiple trails to reach - * to successor, choose the shortest one and send verify successor message - * across that trail. - * @param cls closure for this task - * @param tc the context under which the task is running - */ -static void -send_verify_successor_message (void *cls, - const struct GNUNET_SCHEDULER_TaskContext *tc) -{ - struct FriendInfo *target_friend; - struct GNUNET_HashCode trail_id; - struct Trail *trail; - struct Trail_Element *element; - unsigned int trail_length; - unsigned int i = 0; - struct FingerInfo *successor; - - successor = &finger_table[0]; - - /* This task will be scheduled when the result for Verify Successor is received. */ - send_verify_successor_task = NULL; - - /* When verify successor is being called for first time *for current context* - * cls will be NULL. If send_verify_successor_retry_task is not NO_TASK, we - * must cancel the retry task scheduled for verify_successor of previous - * context. - */ - if (NULL == cls) - { - /* FIXME: Here we are scheduling a new verify successor task, as we - got a new successor. But a send verify successor task may be in progress. - 1. We need to be sure that this is indeed a new successor. As this function - is called even if we add a new trail to reach t old successor. - 2. Assuming the new successor is different, then verify successor message - * to old successor may be following stages. - * --> Waiting for verify successor result. Don't wait anymore. there is - * no trail to reach from old successor to me, hence, routing - * lookup will fail. - * --> Waiting for notify confirmation. again don't wait for it. notify - * confirmation will not succeded. - */ - if (send_verify_successor_retry_task != NULL) - { - /* FIXME: Are we scheduling retry task as soon as we send verify message. - If yes then here before making this task, first check if the message - is for the same peer again. */ - struct VerifySuccessorContext *old_ctx = - GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task); - /* old_ctx must not be NULL, as the retry task had been scheduled */ - GNUNET_assert(NULL != old_ctx); - GNUNET_free(old_ctx); - /* FIXME: Why don't we reset the task to NO_TASK here? */ - } - - struct VerifySuccessorContext *ctx; - ctx = GNUNET_new(struct VerifySuccessorContext); - - ctx->num_retries_scheduled++; - send_verify_successor_retry_task = - GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time, - &send_verify_successor_message, - ctx); - } - else - { - /* This is a retry attempt for verify_successor for a previous context */ - struct VerifySuccessorContext *ctx; - - ctx = cls; - ctx->num_retries_scheduled++; - send_verify_successor_retry_task = - GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time, - &send_verify_successor_message, - ctx); - } - - /* Among all the trails to reach to successor, select first one which is present.*/ - for (i = 0; i < successor->trails_count; i++) - { - trail = &successor->trail_list[i]; - if(GNUNET_YES == trail->is_present) - break; - } - - /* No valid trail found to reach to successor. */ - if (i == successor->trails_count) - return; - - GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, - &successor->finger_identity)); - /* Trail stored at this index. */ - GNUNET_assert (GNUNET_YES == trail->is_present); - trail_id = trail->trail_id; - if (NULL == GDS_ROUTING_get_next_hop(trail_id,GDS_ROUTING_SRC_TO_DEST)) - { - DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line", - GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__); - GNUNET_break(0); - return; - } - trail_length = trail->trail_length; - if (trail_length > 0) - { - /* Copy the trail into peer list. */ - struct GNUNET_PeerIdentity peer_list[trail_length]; - element = trail->trail_head; - for(i = 0; i < trail_length; i++) - { - peer_list[i] = element->peer; - element = element->next; - } - GNUNET_assert (NULL != (target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &peer_list[0]))); - GDS_NEIGHBOURS_send_verify_successor_message (my_identity, - successor->finger_identity, - trail_id, peer_list, trail_length, - target_friend); - } - else - { - GNUNET_assert (NULL != (target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &successor->finger_identity))); - GDS_NEIGHBOURS_send_verify_successor_message (my_identity, - successor->finger_identity, - trail_id, NULL, 0, - target_friend); - } -} - - -/** - * FIXME: should this be a periodic task, incrementing the search finger index? - * Update the current search finger index. - * @a finger_identity - * @a finger_table_index - */ -static void -update_current_search_finger_index (unsigned int finger_table_index) -{ - struct FingerInfo *successor; - - /* FIXME correct this: only move current index periodically */ - if (finger_table_index != current_search_finger_index) - return; - - successor = &finger_table[0]; - GNUNET_assert (GNUNET_YES == successor->is_present); - - /* We were looking for immediate successor. */ - if (0 == current_search_finger_index) - { - current_search_finger_index = PREDECESSOR_FINGER_ID; - if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &successor->finger_identity)) - { - if (NULL == send_verify_successor_task) - { - send_verify_successor_task = - GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL); - } - } - return; - } - - current_search_finger_index = current_search_finger_index - 1; - return; -} - - -/** - * Get the least significant bit set in val. - * - * @param val Value - * @return Position of first bit set, 65 in case of error. - */ -static unsigned int -find_set_bit (uint64_t val) -{ - uint64_t i; - unsigned int pos; - - i = 1; - pos = 0; - - while (!(i & val)) - { - i = i << 1; - pos++; - if (pos > 63) - { - GNUNET_break (0); - return 65; - } - } - - if (val/i != 1) - return 65; /* Some other bit was set to 1 as well. */ - - return pos; -} - - -/** - * Calculate finger_table_index from initial 64 bit finger identity value that - * we send in trail setup message. - * @param ultimate_destination_finger_value Value that we calculated from our - * identity and finger_table_index. - * @param is_predecessor Is the entry for predecessor or not? - * @return finger_table_index Value between 0 <= finger_table_index <= 64 - * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs. - */ -static unsigned int -get_finger_table_index (uint64_t ultimate_destination_finger_value, - unsigned int is_predecessor) -{ - uint64_t my_id64; - uint64_t diff; - unsigned int finger_table_index; - - memcpy (&my_id64, &my_identity, sizeof (uint64_t)); - my_id64 = GNUNET_ntohll (my_id64); - - /* Is this a predecessor finger? */ - if (1 == is_predecessor) - { - diff = my_id64 - ultimate_destination_finger_value; - if (1 == diff) - finger_table_index = PREDECESSOR_FINGER_ID; - else - finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value - - } - else - { - diff = ultimate_destination_finger_value - my_id64; - finger_table_index = find_set_bit (diff); - } - return finger_table_index; -} - - -/** - * Remove finger and its associated data structures from finger table. - * @param existing_finger Finger to be removed which is in finger table. - * @param finger_table_index Index in finger table where @a existing_finger - * is stored. - */ -static void -remove_existing_finger (struct FingerInfo *existing_finger, - unsigned int finger_table_index) -{ - GNUNET_assert (GNUNET_YES == existing_finger->is_present); - - /* If I am my own finger, then we have no trails. */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity, - &my_identity)) - { - existing_finger->is_present = GNUNET_NO; - memset ((void *)&finger_table[finger_table_index], 0, - sizeof (finger_table[finger_table_index])); - return; - } - - /* For all other fingers, send trail teardown across all the trails to reach - finger, and free the finger. */ - send_all_finger_trails_teardown (existing_finger); - free_finger (existing_finger, finger_table_index); -} - - -/** - * Check if there is already an entry in finger_table at finger_table_index. - * We get the finger_table_index from 64bit finger value we got from the network. - * -- If yes, then select the closest finger. - * -- If new and existing finger are same, then check if you can store more - * trails. - * -- If yes then add trail, else keep the best trails to reach to the - * finger. - * -- If the new finger is closest, remove the existing entry, send trail - * teardown message across all the trails to reach the existing entry. - * Add the new finger. - * -- If new and existing finger are different, and existing finger is closest - * then do nothing. - * -- Update current_search_finger_index. - * @param finger_identity Peer Identity of new finger - * @param finger_trail Trail to reach the new finger - * @param finger_trail_length Total number of peers in @a new_finger_trail. - * @param is_predecessor Is this entry for predecessor in finger_table? - * @param finger_value 64 bit value of finger identity that we got from network. - * @param finger_trail_id Unique identifier of @finger_trail. - */ -static void -finger_table_add (struct GNUNET_PeerIdentity finger_identity, - const struct GNUNET_PeerIdentity *finger_trail, - unsigned int finger_trail_length, - unsigned int is_predecessor, - uint64_t finger_value, - struct GNUNET_HashCode finger_trail_id) -{ - struct FingerInfo *existing_finger; - struct GNUNET_PeerIdentity closest_peer; - struct FingerInfo *successor; - unsigned int finger_table_index; - - /* Get the finger_table_index corresponding to finger_value we got from network.*/ - finger_table_index = get_finger_table_index (finger_value, is_predecessor); - - /* Invalid finger_table_index. */ - if ((finger_table_index > PREDECESSOR_FINGER_ID)) - { - GNUNET_break_op (0); - return; - } - - /* Check if new entry is same as successor. */ - if ((0 != finger_table_index) && - (PREDECESSOR_FINGER_ID != finger_table_index)) - { - successor = &finger_table[0]; - if (GNUNET_NO == successor->is_present) - { - GNUNET_break (0); //ASSERTION FAILS HERE. FIXME - return; - } - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, - &successor->finger_identity)) - { - if (0 == fingers_round_count) - { - find_finger_trail_task_next_send_time = - GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time); - } - else - fingers_round_count--; - current_search_finger_index = 0; - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# FINGERS_COUNT"), (int64_t) total_fingers_found, - GNUNET_NO); - total_fingers_found = 0; - return; - } - - struct FingerInfo prev_finger; - prev_finger = finger_table[finger_table_index - 1]; - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, - &prev_finger.finger_identity)) - { - current_search_finger_index--; - return; - } - } - - total_fingers_found++; - existing_finger = &finger_table[finger_table_index]; - - /* No entry present in finger_table for given finger map index. */ - if (GNUNET_NO == existing_finger->is_present) - { - /* Shorten the trail if possible. */ - add_new_finger (finger_identity, finger_trail, - finger_trail_length, - finger_trail_id, finger_table_index); - update_current_search_finger_index (finger_table_index); - return; - } - - /* If existing entry and finger identity are not same. */ - if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), - &finger_identity)) - { - closest_peer = select_closest_peer (&existing_finger->finger_identity, - &finger_identity, - finger_value, - is_predecessor); - - /* If the new finger is the closest peer. */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &closest_peer)) - { - remove_existing_finger (existing_finger, finger_table_index); - add_new_finger (finger_identity, finger_trail, finger_trail_length, - finger_trail_id, finger_table_index); - } - else - { - /* Existing finger is the closest one. We need to send trail teardown - across the trail setup in routing table of all the peers. */ - if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity)) - { - if (finger_trail_length > 0) - GDS_NEIGHBOURS_send_trail_teardown (&finger_trail_id, - GDS_ROUTING_SRC_TO_DEST, - &finger_trail[0]); - else - GDS_NEIGHBOURS_send_trail_teardown (&finger_trail_id, - GDS_ROUTING_SRC_TO_DEST, - &finger_identity); - } - } - } - else - { - /* If both new and existing entry are same as my_identity, then do nothing. */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), - &my_identity)) - { - return; - } - - /* If there is space to store more trails. */ - if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER) - add_new_trail (existing_finger, finger_trail, - finger_trail_length, finger_trail_id); - else - select_and_replace_trail (existing_finger, finger_trail, - finger_trail_length, finger_trail_id); - } - update_current_search_finger_index (finger_table_index); - return; -} - - -/** - * Core handler for P2P put messages. - * @param cls closure - * @param peer sender of the request - * @param message message - * @return #GNUNET_OK to keep the connection open, - * #GNUNET_SYSERR to close it (signal serious error) - */ -static int -handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) -{ - struct PeerPutMessage *put; - struct GNUNET_PeerIdentity *put_path; - struct GNUNET_PeerIdentity current_best_known_dest; - struct GNUNET_PeerIdentity best_known_dest; - struct GNUNET_HashCode received_intermediate_trail_id; - struct GNUNET_HashCode intermediate_trail_id; - struct GNUNET_PeerIdentity next_hop; - struct GNUNET_PeerIdentity *next_routing_hop; - enum GNUNET_DHT_RouteOption options; - struct GNUNET_HashCode test_key; - void *payload; - size_t msize; - uint32_t putlen; - uint32_t hop_count; - size_t payload_size; - uint64_t key_value; - - msize = ntohs (message->size); - if (msize < sizeof (struct PeerPutMessage)) - { - GNUNET_break_op (0); - return GNUNET_OK; - } - - put = (struct PeerPutMessage *) message; - putlen = ntohl (put->put_path_length); - if ((msize < - sizeof (struct PeerPutMessage) + - putlen * sizeof (struct GNUNET_PeerIdentity)) || - (putlen > - GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))) - { - GNUNET_break_op (0); - return GNUNET_OK; - } -#if ENABLE_MALICIOUS - if(1 == act_malicious) - { - DEBUG("\n I AM MALICIOUS PUT_REQUEST_DROPPED for key = %ss",GNUNET_h2s(&put->key)); - return GNUNET_OK; - } -#endif - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes received from other peers"), (int64_t) msize, - GNUNET_NO); - - current_best_known_dest = put->best_known_destination; - put_path = (struct GNUNET_PeerIdentity *) &put[1]; - payload = &put_path[putlen]; - options = ntohl (put->options); - received_intermediate_trail_id = put->intermediate_trail_id; - hop_count = ntohl(put->hop_count); - payload_size = msize - (sizeof (struct PeerPutMessage) + - putlen * sizeof (struct GNUNET_PeerIdentity)); - hop_count++; - switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type), - payload, payload_size, &test_key)) - { - case GNUNET_YES: - if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode))) - { - char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key)); - GNUNET_break_op (0); - GNUNET_log (GNUNET_ERROR_TYPE_WARNING, - "PUT with key `%s' for block with key %s\n", - put_s, GNUNET_h2s_full (&test_key)); - GNUNET_free (put_s); - return GNUNET_OK; - } - break; - case GNUNET_NO: - GNUNET_break_op (0); - return GNUNET_OK; - case GNUNET_SYSERR: - /* cannot verify, good luck */ - break; - } - - if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */ - { - switch (GNUNET_BLOCK_evaluate (GDS_block_context, - ntohl (put->block_type), - GNUNET_BLOCK_EO_NONE, - NULL, /* query */ - NULL, 0, /* bloom filer */ - NULL, 0, /* xquery */ - payload, payload_size)) - { - case GNUNET_BLOCK_EVALUATION_OK_MORE: - case GNUNET_BLOCK_EVALUATION_OK_LAST: - break; - - case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE: - case GNUNET_BLOCK_EVALUATION_RESULT_INVALID: - case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT: - case GNUNET_BLOCK_EVALUATION_REQUEST_VALID: - case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID: - case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED: - default: - GNUNET_break_op (0); - return GNUNET_OK; - } - } - - /* Check if you are already a part of put path. */ - unsigned int i; - for (i = 0; i < putlen; i++) - { - if(0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &put_path[i])) - { - putlen = i; - break; - } - } - - /* Add yourself to the list. */ - struct GNUNET_PeerIdentity pp[putlen + 1]; - //if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE)) - if (1) - { - memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity)); - pp[putlen] = my_identity; - putlen++; - } - else - putlen = 0; - - memcpy (&key_value, &(put->key), sizeof (uint64_t)); - struct Closest_Peer successor; - key_value = GNUNET_ntohll (key_value); - successor = find_local_best_known_next_hop (key_value, - GDS_FINGER_TYPE_NON_PREDECESSOR); - next_hop = successor.next_hop; - intermediate_trail_id = successor.trail_id; - best_known_dest = successor.best_known_destination; - - if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity))) - { - next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id, - GDS_ROUTING_SRC_TO_DEST); - if (NULL != next_routing_hop) - { - next_hop = *next_routing_hop; - intermediate_trail_id = received_intermediate_trail_id; - best_known_dest = current_best_known_dest; - } - } - - GDS_CLIENTS_process_put (options, - ntohl (put->block_type), - hop_count, - ntohl (put->desired_replication_level), - putlen, pp, - GNUNET_TIME_absolute_ntoh (put->expiration_time), - &put->key, - payload, - payload_size); - - /* I am the final destination */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest)) - { - DEBUG("\n PUT_REQUEST_SUCCESSFUL for key = %s",GNUNET_h2s(&put->key)); - GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time), - &(put->key),putlen, pp, ntohl (put->block_type), - payload_size, payload); - } - else - { -#if ENABLE_MALICIOUS - if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination, - &successor.next_hop)) - { - struct FingerInfo *next_hop_finger; - unsigned int i; - - next_hop_finger = &finger_table[successor.finger_table_index]; - for (i = 0; i < next_hop_finger->trails_count; i++) - { - if (GNUNET_YES == next_hop_finger->trail_list[i].is_present) - { - if(0 == next_hop_finger->trail_list[i].trail_length) - { - GDS_NEIGHBOURS_send_put (&put->key, - ntohl (put->block_type),ntohl (put->options), - ntohl (put->desired_replication_level), - best_known_dest, intermediate_trail_id, &next_hop, - hop_count, putlen, pp, - GNUNET_TIME_absolute_ntoh (put->expiration_time), - payload, payload_size); - return GNUNET_OK; - } - next_hop = next_hop_finger->trail_list[i].trail_head->peer; - GDS_NEIGHBOURS_send_put (&put->key, - ntohl (put->block_type),ntohl (put->options), - ntohl (put->desired_replication_level), - best_known_dest, - next_hop_finger->trail_list[i].trail_id, - &next_hop, hop_count, putlen, pp, - GNUNET_TIME_absolute_ntoh (put->expiration_time), - payload, payload_size); - } - } - return GNUNET_OK; - } -#endif - GDS_NEIGHBOURS_send_put (&put->key, - ntohl (put->block_type),ntohl (put->options), - ntohl (put->desired_replication_level), - best_known_dest, intermediate_trail_id, &next_hop, - hop_count, putlen, pp, - GNUNET_TIME_absolute_ntoh (put->expiration_time), - payload, payload_size); - } - return GNUNET_OK; -} - - -/** - * FIXME: Check for loop in the request. If you already are part of get path, - * then you need to reset the get path length. - * Core handler for p2p get requests. - * - * @param cls closure - * @param peer sender of the request - * @param message message - * @return #GNUNET_OK to keep the connection open, - * #GNUNET_SYSERR to close it (signal serious error) - */ -static int -handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) -{ - const struct PeerGetMessage *get; - const struct GNUNET_PeerIdentity *get_path; - struct GNUNET_PeerIdentity best_known_dest; - struct GNUNET_PeerIdentity current_best_known_dest; - struct GNUNET_HashCode intermediate_trail_id; - struct GNUNET_HashCode received_intermediate_trail_id; - struct Closest_Peer successor; - struct GNUNET_PeerIdentity next_hop; - struct GNUNET_PeerIdentity *next_routing_hop; - uint32_t get_length; - uint64_t key_value; - uint32_t hop_count; - size_t msize; - - msize = ntohs (message->size); - if (msize < sizeof (struct PeerGetMessage)) - { - GNUNET_break_op (0); - return GNUNET_YES; - } - - get = (const struct PeerGetMessage *)message; - get_length = ntohl (get->get_path_length); - if ((msize < - sizeof (struct PeerGetMessage) + - get_length * sizeof (struct GNUNET_PeerIdentity)) || - (get_length > - GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))) - { - GNUNET_break_op (0); - return GNUNET_YES; - } - -#if ENABLE_MALICIOUS - if(1 == act_malicious) - { - DEBUG("I am malicious,GET_REQUEST_DROPPED for key = %s. \n",GNUNET_h2s(&get->key)); - return GNUNET_OK; - } -#endif - current_best_known_dest = get->best_known_destination; - received_intermediate_trail_id = get->intermediate_trail_id; - get_path = (const struct GNUNET_PeerIdentity *)&get[1]; - hop_count = get->hop_count; - hop_count++; - - - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes received from other peers"), msize, - GNUNET_NO); - - memcpy (&key_value, &(get->key), sizeof (uint64_t)); - key_value = GNUNET_ntohll (key_value); - - /* Check if you are already a part of get path. */ - unsigned int i; - for (i = 0; i < get_length; i++) - { - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &get_path[i])) - { - get_length = i; - break; - } - } - - /* Add yourself in the get path. */ - struct GNUNET_PeerIdentity gp[get_length + 1]; - memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity)); - gp[get_length] = my_identity; - get_length = get_length + 1; - GDS_CLIENTS_process_get (get->options, get->block_type, hop_count, - get->desired_replication_level, get->get_path_length, - gp, &get->key); - - - successor = find_local_best_known_next_hop (key_value, - GDS_FINGER_TYPE_NON_PREDECESSOR); - next_hop = successor.next_hop; - best_known_dest = successor.best_known_destination; - intermediate_trail_id = successor.trail_id; - /* I am not the final destination. I am part of trail to reach final dest. */ - if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_best_known_dest, &my_identity))) - { - next_routing_hop = GDS_ROUTING_get_next_hop (received_intermediate_trail_id, - GDS_ROUTING_SRC_TO_DEST); - if (NULL != next_routing_hop) - { - next_hop = *next_routing_hop; - best_known_dest = current_best_known_dest; - intermediate_trail_id = received_intermediate_trail_id; - } - } - - /* I am the final destination. */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest)) - { - if (1 == get_length) - { - DEBUG("\n GET_REQUEST DONE for key = %s",GNUNET_h2s(&get->key)); - GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, - NULL, 0, 1, &my_identity, NULL,&my_identity); - } - else - { - GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0, - get_length, gp, &gp[get_length - 2], - &my_identity); - } - } - else - { - -#if ENABLE_MALICIOUS - if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination, - &successor.next_hop)) - { - struct FingerInfo *next_hop_finger; - unsigned int i; - - next_hop_finger = &finger_table[successor.finger_table_index]; - for (i = 0; i < next_hop_finger->trails_count; i++) - { - if(0 == next_hop_finger->trail_list[i].trail_length) - { - GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options, - get->desired_replication_level, best_known_dest, - intermediate_trail_id, &next_hop, hop_count, - get_length, gp); - return GNUNET_OK; - } - if (GNUNET_YES == next_hop_finger->trail_list[i].is_present) - { - next_hop = next_hop_finger->trail_list[i].trail_head->peer; - GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options, - get->desired_replication_level, best_known_dest, - next_hop_finger->trail_list[i].trail_id, - &next_hop, hop_count, - get_length, gp); - } - } - return GNUNET_OK; - } -#endif - GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options, - get->desired_replication_level, best_known_dest, - intermediate_trail_id, &next_hop, hop_count, - get_length, gp); - } - return GNUNET_YES; -} - - -/** - * Core handler for get result - * @param cls closure - * @param peer sender of the request - * @param message message - * @return #GNUNET_OK to keep the connection open, - * #GNUNET_SYSERR to close it (signal serious error) - */ -static int -handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) -{ - const struct PeerGetResultMessage *get_result; - const struct GNUNET_PeerIdentity *get_path; - const struct GNUNET_PeerIdentity *put_path; - const void *payload; - size_t payload_size; - size_t msize; - unsigned int getlen; - unsigned int putlen; - int current_path_index; - - msize = ntohs (message->size); - if (msize < sizeof (struct PeerGetResultMessage)) - { - GNUNET_break_op (0); - return GNUNET_YES; - } - - get_result = (const struct PeerGetResultMessage *)message; - getlen = ntohl (get_result->get_path_length); - putlen = ntohl (get_result->put_path_length); - - if ((msize < - sizeof (struct PeerGetResultMessage) + - getlen * sizeof (struct GNUNET_PeerIdentity) + - putlen * sizeof (struct GNUNET_PeerIdentity)) || - (getlen > - GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) || - (putlen > - GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))) - { - GNUNET_break_op (0); - return GNUNET_YES; - } - DEBUG("GET_RESULT FOR DATA_SIZE = %lu\n",msize); - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes received from other peers"), msize, - GNUNET_NO); - - put_path = (const struct GNUNET_PeerIdentity *) &get_result[1]; - get_path = &put_path[putlen]; - payload = (const void *) &get_path[getlen]; - payload_size = msize - (sizeof (struct PeerGetResultMessage) + - (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity)); - - if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0])))) - { - GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key), - getlen, get_path, putlen, - put_path, get_result->type, payload_size, payload); - return GNUNET_YES; - } - else - { - current_path_index = search_my_index (get_path, getlen); - if (-1 == current_path_index ) - { - DEBUG ("No entry found in get path.\n"); - GNUNET_break (0); - return GNUNET_SYSERR; - } - if((getlen + 1) == current_path_index) - { - DEBUG("Present twice in get path. Not allowed. \n"); - GNUNET_break (0); - return GNUNET_SYSERR; - } - GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type, - &get_path[current_path_index - 1], - &(get_result->querying_peer), putlen, put_path, - getlen, get_path, get_result->expiration_time, - payload, payload_size); - return GNUNET_YES; - } - return GNUNET_SYSERR; -} - - -/** - * Find the next hop to pass trail setup message. First find the local best known - * hop from your own identity, friends and finger. If you were part of trail, - * then get the next hop from routing table. Compare next_hop from routing table - * and local best known hop, and return the closest one to final_dest_finger_val - * @param final_dest_finger_val 64 bit value of finger identity - * @param intermediate_trail_id If you are part of trail to reach to some other - * finger, then it is the trail id to reach to - * that finger, else set to 0. - * @param is_predecessor Are we looking for closest successor or predecessor. - * @param source Source of trail setup message. - * @param current_dest In case you are part of trail, then finger to which - * we should forward the message. Else my own identity - * @return Closest Peer for @a final_dest_finger_val - */ -static struct Closest_Peer -get_local_best_known_next_hop (uint64_t final_dest_finger_val, - struct GNUNET_HashCode intermediate_trail_id, - unsigned int is_predecessor, - struct GNUNET_PeerIdentity source, - struct GNUNET_PeerIdentity *current_dest) -{ - struct Closest_Peer peer; - - peer = find_local_best_known_next_hop (final_dest_finger_val, is_predecessor); - - /* Am I just a part of a trail towards a finger (current_destination)? */ - if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest) && - 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination, - current_dest)) - { - struct GNUNET_PeerIdentity closest_peer; - - /* Select best successor among one found locally and current_destination - * that we got from network.*/ - closest_peer = select_closest_peer (&peer.best_known_destination, - current_dest, - final_dest_finger_val, - is_predecessor); - - /* Is current dest (end point of the trail of which I am a part) closest_peer? */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, &closest_peer)) - { - struct GNUNET_PeerIdentity *next_hop; - - next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id, - GDS_ROUTING_SRC_TO_DEST); - /* next_hop NULL is a valid case. This intermediate trail id is set by - some other finger, and while this trail setup is in progress, that other - peer might have found a better trail ,and send trail teardown message - across the network. In case we got the trail teardown message first, - then next_hop will be NULL. A possible solution could be to keep track - * of all removed trail id, and be sure that there is no other reason . */ - if(NULL != next_hop) - { - peer.next_hop = *next_hop; - peer.best_known_destination = *current_dest; - peer.trail_id = intermediate_trail_id; - } - } - } - return peer; -} - - -/* - * Core handle for PeerTrailSetupMessage. - * @param cls closure - * @param message message - * @param peer peer identity this notification is about - * @return #GNUNET_OK on success, #GNUNET_SYSERR on error - */ -static int -handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) -{ - const struct PeerTrailSetupMessage *trail_setup; - const struct GNUNET_PeerIdentity *trail_peer_list; - struct GNUNET_PeerIdentity current_dest; - struct FriendInfo *target_friend; - struct GNUNET_PeerIdentity source; - struct GNUNET_HashCode intermediate_trail_id; - struct GNUNET_HashCode trail_id; - unsigned int is_predecessor; - uint32_t trail_length; - uint64_t final_dest_finger_val; - int i; - size_t msize; - - msize = ntohs (message->size); - if (msize < sizeof (struct PeerTrailSetupMessage)) - { - GNUNET_break_op (0); - return GNUNET_SYSERR; - } - - trail_setup = (const struct PeerTrailSetupMessage *) message; - if ((msize - sizeof (struct PeerTrailSetupMessage)) % - sizeof (struct GNUNET_PeerIdentity) != 0) - { - GNUNET_break_op (0); - return GNUNET_OK; - } - trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/ - sizeof (struct GNUNET_PeerIdentity); - - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes received from other peers"), msize, - GNUNET_NO); - - trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1]; - current_dest = trail_setup->best_known_destination; - trail_id = trail_setup->trail_id; - final_dest_finger_val = - GNUNET_ntohll (trail_setup->final_destination_finger_value); - source = trail_setup->source_peer; - is_predecessor = ntohl (trail_setup->is_predecessor); - intermediate_trail_id = trail_setup->intermediate_trail_id; - - /* Did the friend insert its ID in the trail list? */ - if (trail_length > 0 && - 0 != memcmp (&trail_peer_list[trail_length-1], peer, sizeof (struct GNUNET_PeerIdentity))) - { - GNUNET_break_op (0); - return GNUNET_SYSERR; - } - - /* If I was the source and got the message back, then set trail length to 0.*/ - if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source)) - { - trail_length = 0; - } - - /* Check if you are present in the trail seen so far? */ - for (i = 0; i < trail_length ; i++) - { - if(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail_peer_list[i],&my_identity)) - { - /* We will add ourself later in code, if NOT destination. */ - trail_length = i; - break; - } - } - - /* Is my routing table full? */ - if (GNUNET_YES == GDS_ROUTING_threshold_reached()) - { - if (trail_length > 0) - target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &trail_peer_list[trail_length - 1]); - else - target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &source); - if(NULL == target_friend) - { - DEBUG ("\n friend not found"); - GNUNET_break(0); - return GNUNET_OK; - } - GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val, - my_identity, is_predecessor, - trail_peer_list, trail_length, - trail_id, target_friend, - CONGESTION_TIMEOUT); - return GNUNET_OK; - } - - /* Get the next hop to forward the trail setup request. */ - struct Closest_Peer next_peer = - get_local_best_known_next_hop (final_dest_finger_val, - intermediate_trail_id, - is_predecessor, - source, - ¤t_dest); - - /* Am I the final destination? */ - if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination, - &my_identity))) - { - if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity)) - { - finger_table_add (my_identity, NULL, 0, is_predecessor, - final_dest_finger_val, trail_id); - return GNUNET_OK; - } - - if (trail_length > 0) - target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &trail_peer_list[trail_length-1]); - else - target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source); - if (NULL == target_friend) - { - GNUNET_break_op (0); - return GNUNET_SYSERR; - } - GDS_ROUTING_add (trail_id, target_friend->id, my_identity); - GDS_NEIGHBOURS_send_trail_setup_result (source, - my_identity, - target_friend, trail_length, - trail_peer_list, - is_predecessor, - final_dest_finger_val,trail_id); - } - else /* I'm not the final destination. */ - { - target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &next_peer.next_hop); - if(NULL == target_friend) - { - DEBUG ("\n target friend not found for peer = %s", GNUNET_i2s(&next_peer.next_hop)); - GNUNET_break (0); - return GNUNET_OK; - } - if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source)) - { - /* Add yourself to list of peers. */ - struct GNUNET_PeerIdentity peer_list[trail_length + 1]; - - memcpy (peer_list, trail_peer_list, - trail_length * sizeof (struct GNUNET_PeerIdentity)); - peer_list[trail_length] = my_identity; - GDS_NEIGHBOURS_send_trail_setup (source, - final_dest_finger_val, - next_peer.best_known_destination, - target_friend, trail_length + 1, peer_list, - is_predecessor, trail_id, - next_peer.trail_id); - } - else - GDS_NEIGHBOURS_send_trail_setup (source, - final_dest_finger_val, - next_peer.best_known_destination, - target_friend, 0, NULL, - is_predecessor, trail_id, - next_peer.trail_id); - } - return GNUNET_OK; -} - - -/** - * Core handle for p2p trail setup result messages. - * @param closure - * @param message message - * @param peer sender of this message. - * @return #GNUNET_OK on success, #GNUNET_SYSERR on error - */ -static int -handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) -{ - const struct PeerTrailSetupResultMessage *trail_result; - const struct GNUNET_PeerIdentity *trail_peer_list; - struct GNUNET_PeerIdentity next_hop; - struct FriendInfo *target_friend; - struct GNUNET_PeerIdentity querying_peer; - struct GNUNET_PeerIdentity finger_identity; - uint32_t trail_length; - uint64_t ulitmate_destination_finger_value; - uint32_t is_predecessor; - struct GNUNET_HashCode trail_id; - int my_index; - size_t msize; - - msize = ntohs (message->size); - if (msize < sizeof (struct PeerTrailSetupResultMessage)) - { - GNUNET_break_op (0); - return GNUNET_YES; - } - - trail_result = (const struct PeerTrailSetupResultMessage *) message; - if ((msize - sizeof (struct PeerTrailSetupResultMessage)) % - sizeof (struct GNUNET_PeerIdentity) != 0) - { - GNUNET_break_op (0); - return GNUNET_OK; - } - trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/ - sizeof (struct GNUNET_PeerIdentity); - - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes received from other peers"), msize, - GNUNET_NO); - - is_predecessor = ntohl (trail_result->is_predecessor); - querying_peer = trail_result->querying_peer; - finger_identity = trail_result->finger_identity; - trail_id = trail_result->trail_id; - trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1]; - ulitmate_destination_finger_value = - GNUNET_ntohll (trail_result->ulitmate_destination_finger_value); - - /* Am I the one who initiated the query? */ - if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity))) - { - /* Check that you got the message from the correct peer. */ - if (trail_length > 0) - { - GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0], - peer)); - } - else - { - GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, - peer)); - } - GDS_ROUTING_add (trail_id, my_identity, *peer); - finger_table_add (finger_identity, trail_peer_list, trail_length, - is_predecessor, ulitmate_destination_finger_value, trail_id); - return GNUNET_YES; - } - - /* Get my location in the trail. */ - my_index = search_my_index (trail_peer_list, trail_length); - if (-1 == my_index) - { - DEBUG ("Not found in trail\n"); - GNUNET_break_op(0); - return GNUNET_SYSERR; - } - //TODO; return -2. - if ((trail_length + 1) == my_index) - { - DEBUG ("Found twice in trail.\n"); - GNUNET_break_op(0); - return GNUNET_SYSERR; - } - - //TODO; Refactor code here and above to check if sender peer is correct - if (my_index == 0) - { - if(trail_length > 1) - GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1], - peer)); - else - GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, - peer)); - next_hop = trail_result->querying_peer; - } - else - { - if(my_index == trail_length - 1) - { - GNUNET_assert(0 == - GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, - peer)); - } - else - GNUNET_assert(0 == - GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1], - peer)); - next_hop = trail_peer_list[my_index - 1]; - } - - target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop); - if (NULL == target_friend) - { - GNUNET_break_op (0); - return GNUNET_SYSERR; - } - GDS_ROUTING_add (trail_id, next_hop, *peer); - GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity, - target_friend, trail_length, trail_peer_list, - is_predecessor, - ulitmate_destination_finger_value, - trail_id); - return GNUNET_OK; -} - - -/** - * Invert the trail. - * @param trail Trail to be inverted - * @param trail_length Total number of peers in the trail. - * @return Updated trail - */ -static struct GNUNET_PeerIdentity * -invert_trail (const struct GNUNET_PeerIdentity *trail, - unsigned int trail_length) -{ - int i; - int j; - struct GNUNET_PeerIdentity *inverted_trail; - - inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) * - trail_length); - i = 0; - j = trail_length - 1; - while (i < trail_length) - { - inverted_trail[i] = trail[j]; - i++; - j--; - } - - GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap, - &inverted_trail[0])); - return inverted_trail; -} - - -/** - * Return the shortest trail among all the trails to reach to finger from me. - * @param finger Finger - * @param shortest_trail_length[out] Trail length of shortest trail from me - * to @a finger - * @return Shortest trail. - */ -static struct GNUNET_PeerIdentity * -get_shortest_trail (struct FingerInfo *finger, - unsigned int *trail_length) -{ - struct Trail *trail; - unsigned int flag = 0; - unsigned int shortest_trail_index = 0; - int shortest_trail_length = -1; - struct Trail_Element *trail_element; - struct GNUNET_PeerIdentity *trail_list; - unsigned int i; - - /* Get the shortest trail to reach to current successor. */ - for (i = 0; i < finger->trails_count; i++) + if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) { - trail = &finger->trail_list[i]; - - if (0 == flag) - { - shortest_trail_index = i; - shortest_trail_length = trail->trail_length; - flag = 1; - continue; - } - - if (shortest_trail_length > trail->trail_length) - { - shortest_trail_index = i; - shortest_trail_length = trail->trail_length; - } - continue; + GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), + 1, GNUNET_NO); } + pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); + pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); + tsm = (struct PeerTrailSetupMessage *) &pending[1]; + pending->msg = &(tsm->header); + tsm->header.size = htons (msize); + tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP); + tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value); + tsm->source_peer = source_peer; + tsm->best_known_destination = best_known_destination; + tsm->is_predecessor = htonl (is_predecessor); + tsm->trail_id = trail_id; + tsm->intermediate_trail_id = intermediate_trail_id; - /* Copy the shortest trail and return. */ - trail = &finger->trail_list[shortest_trail_index]; - trail_element = trail->trail_head; - - trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)* - shortest_trail_length); - - for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next) + if (trail_length > 0) { - trail_list[i] = trail_element->peer; + peer_list = (struct GNUNET_PeerIdentity *) &tsm[1]; + memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity)); } - GNUNET_assert(shortest_trail_length != -1); - - *trail_length = shortest_trail_length; - return trail_list; + GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); + target_friend->pending_count++; + process_friend_queue (target_friend); } /** - * Check if trail_1 and trail_2 have any common element. If yes then join - * them at common element. trail_1 always preceeds trail_2 in joined trail. - * @param trail_1 Trail from source to me, NOT including endpoints. - * @param trail_1_len Total number of peers @a trail_1 - * @param trail_2 Trail from me to current predecessor, NOT including endpoints. - * @param trail_2_len Total number of peers @a trail_2 - * @param joined_trail_len Total number of peers in combined trail of trail_1 - * trail_2. - * @return Joined trail. + * Construct a trail setup result message and forward it to target friend. + * @param querying_peer Peer which sent the trail setup request and should get + * the result back. + * @param Finger Peer to which the trail has been setup to. + * @param target_friend Friend to which this message should be forwarded. + * @param trail_length Numbers of peers in the trail. + * @param trail_peer_list Peers which are part of the trail from + * querying_peer to Finger, NOT including them. + * @param is_predecessor Is @a Finger predecessor to @a querying_peer ? + * @param ultimate_destination_finger_value Value to which @a finger is the closest + * peer. + * @param trail_id Unique identifier of the trail. */ -static struct GNUNET_PeerIdentity * -check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1, - unsigned int trail_1_len, - struct GNUNET_PeerIdentity *trail_2, - unsigned int trail_2_len, - unsigned int *joined_trail_len) +void +GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer, + struct GNUNET_PeerIdentity finger, + struct FriendInfo *target_friend, + unsigned int trail_length, + const struct GNUNET_PeerIdentity *trail_peer_list, + unsigned int is_predecessor, + uint64_t ultimate_destination_finger_value, + struct GNUNET_HashCode trail_id) { - struct GNUNET_PeerIdentity *joined_trail; - unsigned int i; - unsigned int j; - unsigned int k; - - for (i = 0; i < trail_1_len; i++) - { - for (j = 0; j < trail_2_len; j++) - { - if(0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],&trail_2[j])) - continue; - - *joined_trail_len = i + (trail_2_len - j); - joined_trail = GNUNET_malloc (*joined_trail_len * - sizeof(struct GNUNET_PeerIdentity)); - - - /* Copy all the elements from 0 to i into joined_trail. */ - for(k = 0; k < ( i+1); k++) - { - joined_trail[k] = trail_1[k]; - } - - /* Increment j as entry stored is same as entry stored at i*/ - j = j+1; - - /* Copy all the elements from j to trail_2_len-1 to joined trail.*/ - while(k <= (*joined_trail_len - 1)) - { - joined_trail[k] = trail_2[j]; - j++; - k++; - } - - return joined_trail; - } - } - - /* Here you should join the trails. */ - *joined_trail_len = trail_1_len + trail_2_len + 1; - joined_trail = GNUNET_malloc (*joined_trail_len * - sizeof(struct GNUNET_PeerIdentity)); - - - for(i = 0; i < trail_1_len;i++) - { - joined_trail[i] = trail_1[i]; - } + struct P2PPendingMessage *pending; + struct PeerTrailSetupResultMessage *tsrm; + struct GNUNET_PeerIdentity *peer_list; + size_t msize; - joined_trail[i] = my_identity; - i++; + msize = sizeof (struct PeerTrailSetupResultMessage) + + (trail_length * sizeof (struct GNUNET_PeerIdentity)); - for (j = 0; i < *joined_trail_len; i++,j++) + if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) { - joined_trail[i] = trail_2[j]; + GNUNET_break (0); + return; } - return joined_trail; -} - - -/** - * Return the trail from source to my current predecessor. Check if source - * is already part of the this trail, if yes then return the shorten trail. - * @param current_trail Trail from source to me, NOT including the endpoints. - * @param current_trail_length Number of peers in @a current_trail. - * @param trail_src_to_curr_pred_length[out] Number of peers in trail from - * source to my predecessor, NOT including - * the endpoints. - * @return Trail from source to my predecessor. - */ -static struct GNUNET_PeerIdentity * -get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer, - const struct GNUNET_PeerIdentity *trail_src_to_me, - unsigned int trail_src_to_me_len, - unsigned int *trail_src_to_curr_pred_length) -{ - struct GNUNET_PeerIdentity *trail_me_to_curr_pred; - struct GNUNET_PeerIdentity *trail_src_to_curr_pred; - unsigned int trail_me_to_curr_pred_length; - struct FingerInfo *current_predecessor; - int i; - unsigned int j; - unsigned int len; - - current_predecessor = &finger_table[PREDECESSOR_FINGER_ID]; - - /* Check if trail_src_to_me contains current_predecessor. */ - for (i = 0; i < trail_src_to_me_len; i++) + if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) { - if (0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i], - ¤t_predecessor->finger_identity)) - continue; - - - *trail_src_to_curr_pred_length = i; - - if(0 == i) - return NULL; - - trail_src_to_curr_pred = GNUNET_malloc (*trail_src_to_curr_pred_length * - sizeof(struct GNUNET_PeerIdentity)); - for (j = 0; j < i; j++) - trail_src_to_curr_pred[j] = trail_src_to_me[j]; - return trail_src_to_curr_pred; + GNUNET_STATISTICS_update (GDS_stats, + gettext_noop ("# P2P messages dropped due to full queue"), + 1, GNUNET_NO); } + pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); + pending->importance = 0; + pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); + tsrm = (struct PeerTrailSetupResultMessage *) &pending[1]; + pending->msg = &tsrm->header; + tsrm->header.size = htons (msize); + tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT); + tsrm->querying_peer = querying_peer; + tsrm->finger_identity = finger; + tsrm->is_predecessor = htonl (is_predecessor); + tsrm->trail_id = trail_id; + tsrm->ulitmate_destination_finger_value = + GNUNET_htonll (ultimate_destination_finger_value); + peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1]; + memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity)); - trail_me_to_curr_pred = get_shortest_trail (current_predecessor, - &trail_me_to_curr_pred_length); - - /* Check if trail contains the source_peer. */ - for (i = trail_me_to_curr_pred_length - 1; i >= 0; i--) - { - if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer, - &trail_me_to_curr_pred[i])) - continue; - - /* Source is NOT part of trail. */ - i++; - - /* Source is the last element in the trail to reach to my pred. - Source is direct friend of the pred. */ - if (trail_me_to_curr_pred_length == i) - { - *trail_src_to_curr_pred_length = 0; - GNUNET_free_non_null (trail_me_to_curr_pred); - return NULL; - } - - *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i; - trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)* - *trail_src_to_curr_pred_length); - - for (j = 0; j < *trail_src_to_curr_pred_length; i++,j++) - trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i]; - GNUNET_free_non_null (trail_me_to_curr_pred); - return trail_src_to_curr_pred; - } - - trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me, - trail_src_to_me_len, - trail_me_to_curr_pred, - trail_me_to_curr_pred_length, - &len); - *trail_src_to_curr_pred_length = len; - GNUNET_free_non_null(trail_me_to_curr_pred); - return trail_src_to_curr_pred; + /* Send the message to chosen friend. */ + GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); + target_friend->pending_count++; + process_friend_queue (target_friend); } - /** - * Add finger as your predecessor. To add, first generate a new trail id, invert - * the trail to get the trail from me to finger, add an entry in your routing - * table, send add trail message to peers which are part of trail from me to - * finger and add finger in finger table. - * @param finger - * @param trail - * @param trail_length - */ -static void -update_predecessor (struct GNUNET_PeerIdentity finger, - struct GNUNET_PeerIdentity *trail, - unsigned int trail_length) -{ - struct GNUNET_HashCode trail_to_new_predecessor_id; - struct GNUNET_PeerIdentity *trail_to_new_predecessor; - struct FriendInfo *target_friend; - - /* Generate trail id for trail from me to new predecessor = finger. */ - GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG, - &trail_to_new_predecessor_id, - sizeof (trail_to_new_predecessor_id)); - - if (0 == trail_length) - { - trail_to_new_predecessor = NULL; - GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger); - target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger); - if (NULL == target_friend) - { - GNUNET_break (0); - return; - } - } - else - { - /* Invert the trail to get the trail from me to finger, NOT including the - endpoints.*/ - GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap, - &trail[trail_length-1])); - trail_to_new_predecessor = invert_trail (trail, trail_length); - - /* Add an entry in your routing table. */ - GDS_ROUTING_add (trail_to_new_predecessor_id, - my_identity, - trail_to_new_predecessor[0]); - - GNUNET_assert (NULL != (target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &trail_to_new_predecessor[0]))); - } - - /* Add entry in routing table of all peers that are part of trail from me - to finger, including finger. */ - GDS_NEIGHBOURS_send_add_trail (my_identity, - finger, - trail_to_new_predecessor_id, - trail_to_new_predecessor, - trail_length, - target_friend); - - add_new_finger (finger, trail_to_new_predecessor, trail_length, - trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID); - GNUNET_free_non_null(trail_to_new_predecessor); -} - - -/* - * Check if you already have a predecessor. If not then add finger as your - * predecessor. If you have predecessor, then compare two peer identites. - * If finger is correct predecessor, then remove the old entry, add finger in - * finger table and send add_trail message to add the trail in the routing - * table of all peers which are part of trail to reach from me to finger. - * @param finger New peer which may be our predecessor. - * @param trail List of peers to reach from @finger to me. - * @param trail_length Total number of peer in @a trail. + * Send notify successor confirmation message. + * @param trail_id Unique Identifier of the trail. + * @param trail_direction Destination to Source. + * @param target_friend Friend to get this message next. */ -static void -compare_and_update_predecessor (struct GNUNET_PeerIdentity finger, - struct GNUNET_PeerIdentity *trail, - unsigned int trail_length) +void +GDS_NEIGHBOURS_send_notify_succcessor_confirmation (struct GNUNET_HashCode trail_id, + unsigned int trail_direction, + struct FriendInfo *target_friend) { - struct FingerInfo *current_predecessor; - struct GNUNET_PeerIdentity closest_peer; - uint64_t predecessor_value; - unsigned int is_predecessor = 1; - - current_predecessor = &finger_table[PREDECESSOR_FINGER_ID]; - GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity)); + struct PeerNotifyConfirmationMessage *ncm; + struct P2PPendingMessage *pending; + size_t msize; - /* No predecessor. Add finger as your predecessor. */ - if (GNUNET_NO == current_predecessor->is_present) + msize = sizeof (struct PeerNotifyConfirmationMessage); + if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) { - update_predecessor (finger, trail, trail_length); + GNUNET_break (0); return; } - if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor->finger_identity, - &finger)) + if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) { - return; + GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), + 1, GNUNET_NO); } - predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID); - closest_peer = select_closest_peer (&finger, - ¤t_predecessor->finger_identity, - predecessor_value, is_predecessor); + pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); + pending->importance = 0; /* FIXME */ + pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); + ncm = (struct PeerNotifyConfirmationMessage *) &pending[1]; + pending->msg = &ncm->header; + ncm->header.size = htons (msize); + ncm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION); + ncm->trail_id = trail_id; + ncm->trail_direction = htonl (trail_direction); - /* Finger is the closest predecessor. Remove the existing one and add the new - one. */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity(&closest_peer, &finger)) - { - remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID); - update_predecessor (finger, trail, trail_length); - return; - } - return; + /* Send the message to chosen friend. */ + GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); + target_friend->pending_count++; + process_friend_queue (target_friend); } -/* - * Core handle for p2p verify successor messages. - * @param cls closure - * @param message message - * @param peer peer identity this notification is about - * @return #GNUNET_OK on success, #GNUNET_SYSERR on error +/** + * Send trail rejection message to target friend + * @param source_peer Peer which is trying to setup the trail. + * @param ultimate_destination_finger_value Peer closest to this value will be + * @a source_peer's finger + * @param congested_peer Peer which sent this message as it is congested. + * @param is_predecessor Is source_peer looking for trail to a predecessor or not. + * @param trail_peer_list Trails seen so far in trail setup before getting rejected + * by congested_peer. This does NOT include @a source_peer + * and congested_peer. + * @param trail_length Total number of peers in trail_peer_list, NOT including + * @a source_peer and @a congested_peer + * @param trail_id Unique identifier of this trail. + * @param congestion_timeout Duration given by congested peer as an estimate of + * how long it may remain congested. */ -static int -handle_dht_p2p_verify_successor(void *cls, - const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) +void +GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer, + uint64_t ultimate_destination_finger_value, + struct GNUNET_PeerIdentity congested_peer, + unsigned int is_predecessor, + const struct GNUNET_PeerIdentity *trail_peer_list, + unsigned int trail_length, + struct GNUNET_HashCode trail_id, + struct FriendInfo *target_friend, + const struct GNUNET_TIME_Relative congestion_timeout) { - const struct PeerVerifySuccessorMessage *vsm; - struct GNUNET_HashCode trail_id; - struct GNUNET_PeerIdentity successor; - struct GNUNET_PeerIdentity source_peer; - struct GNUNET_PeerIdentity *trail; - struct GNUNET_PeerIdentity *next_hop; - struct FingerInfo current_predecessor; - struct FriendInfo *target_friend; - unsigned int trail_src_to_curr_pred_len = 0; - struct GNUNET_PeerIdentity *trail_src_to_curr_pred; - unsigned int trail_length; + struct PeerTrailRejectionMessage *trm; + struct P2PPendingMessage *pending; + struct GNUNET_PeerIdentity *peer_list; size_t msize; - msize = ntohs (message->size); - - if (msize < sizeof (struct PeerVerifySuccessorMessage)) - { - GNUNET_break_op (0); - return GNUNET_YES; - } + msize = sizeof (struct PeerTrailRejectionMessage) + + (trail_length * sizeof (struct GNUNET_PeerIdentity)); - vsm = (const struct PeerVerifySuccessorMessage *) message; - trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/ - sizeof (struct GNUNET_PeerIdentity); - if ((msize - sizeof (struct PeerVerifySuccessorMessage)) % - sizeof (struct GNUNET_PeerIdentity) != 0) + if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) { - GNUNET_break_op (0); - return GNUNET_OK; + GNUNET_break (0); + return; } - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes received from other peers"), msize, - GNUNET_NO); - - trail_id = vsm->trail_id; - source_peer = vsm->source_peer; - successor = vsm->successor; - trail = (struct GNUNET_PeerIdentity *)&vsm[1]; - - /* I am NOT the successor of source_peer. Pass the message to next_hop on - * the trail. */ - if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity))) + if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) { - next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST); - if (NULL == next_hop) - { - return GNUNET_OK; - } - - target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop); - - if(NULL == target_friend) - { - GNUNET_break_op(0); - return GNUNET_OK; - } - GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor, - trail_id, trail, trail_length, - target_friend); - return GNUNET_OK; + GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), + 1, GNUNET_NO); } - /* I am the destination of this message. */ - - /* Check if the source_peer could be our predecessor and if yes then update - * it. */ - compare_and_update_predecessor (source_peer, trail, trail_length); - current_predecessor = finger_table[PREDECESSOR_FINGER_ID]; + pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); + pending->importance = 0; + pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); + trm = (struct PeerTrailRejectionMessage *)&pending[1]; + pending->msg = &trm->header; + trm->header.size = htons (msize); + trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION); + trm->source_peer = source_peer; + trm->congested_peer = congested_peer; + trm->congestion_time = congestion_timeout; + trm->is_predecessor = htonl (is_predecessor); + trm->trail_id = trail_id; + trm->ultimate_destination_finger_value = + GNUNET_htonll (ultimate_destination_finger_value); - /* Is source of this message NOT my predecessor. */ - if (0 != (GNUNET_CRYPTO_cmp_peer_identity (¤t_predecessor.finger_identity, - &source_peer))) - { - trail_src_to_curr_pred = - get_trail_src_to_curr_pred (source_peer, - trail, - trail_length, - &trail_src_to_curr_pred_len); - } - else + peer_list = (struct GNUNET_PeerIdentity *) &trm[1]; + if (trail_length > 0) { - trail_src_to_curr_pred_len = trail_length; - unsigned int i; - - trail_src_to_curr_pred = - GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) - *trail_src_to_curr_pred_len); - for(i = 0; i < trail_src_to_curr_pred_len; i++) - { - trail_src_to_curr_pred[i] = trail[i]; - } + memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity)); } - GNUNET_assert (NULL != - (target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer))); - GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity, - current_predecessor.finger_identity, - trail_id, trail_src_to_curr_pred, - trail_src_to_curr_pred_len, - GDS_ROUTING_DEST_TO_SRC, - target_friend); - GNUNET_free_non_null(trail_src_to_curr_pred); - return GNUNET_OK; + /* Send the message to chosen friend. */ + GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); + target_friend->pending_count++; + process_friend_queue (target_friend); } /** - * If the trail from me to my probable successor contains a friend not - * at index 0, then we can shorten the trail. - * @param probable_successor Peer which is our probable successor - * @param trail_me_to_probable_successor Peers in path from me to my probable - * successor, NOT including the endpoints. - * @param trail_me_to_probable_successor_len Total number of peers in - * @a trail_me_to_probable_succesor. - * @return Updated trail, if any friend found. - * Else the trail_me_to_probable_successor. + * Construct a verify successor message and forward it to target_friend. + * @param source_peer Peer which wants to verify its successor. + * @param successor Peer which is @a source_peer's current successor. + * @param trail_id Unique Identifier of trail from @a source_peer to @a successor, + * NOT including them. + * @param trail List of peers which are part of trail to reach from @a source_peer + * to @a successor, NOT including them. + * @param trail_length Total number of peers in @a trail. + * @param target_friend Next friend to get this message. */ -struct GNUNET_PeerIdentity * -check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor, - const struct GNUNET_PeerIdentity *trail_me_to_probable_successor, - unsigned int trail_me_to_probable_successor_len, - unsigned int *trail_to_new_successor_length) +void +GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer, + struct GNUNET_PeerIdentity successor, + struct GNUNET_HashCode trail_id, + struct GNUNET_PeerIdentity *trail, + unsigned int trail_length, + struct FriendInfo *target_friend) { - unsigned int i; - unsigned int j; - struct GNUNET_PeerIdentity *trail_to_new_successor; + struct PeerVerifySuccessorMessage *vsm; + struct P2PPendingMessage *pending; + struct GNUNET_PeerIdentity *peer_list; + size_t msize; - /* Probable successor is a friend */ - if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &probable_successor)) + msize = sizeof (struct PeerVerifySuccessorMessage) + + (trail_length * sizeof (struct GNUNET_PeerIdentity)); + + if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) { - trail_to_new_successor = NULL; - *trail_to_new_successor_length = 0; - return trail_to_new_successor; + GNUNET_break (0); + return; } - /* Is there any friend of yours in this trail. */ - if(trail_me_to_probable_successor_len > 1) + if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) { - for (i = trail_me_to_probable_successor_len - 1; i > 0; i--) - { - if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &trail_me_to_probable_successor[i])) - continue; - - *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i); - trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)* - *trail_to_new_successor_length); - - - for(j = 0; j < *trail_to_new_successor_length; i++,j++) - { - trail_to_new_successor[j] = trail_me_to_probable_successor[i]; - } - - return trail_to_new_successor; - } + GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), + 1, GNUNET_NO); } - *trail_to_new_successor_length = trail_me_to_probable_successor_len; - return (struct GNUNET_PeerIdentity*)trail_me_to_probable_successor; -} + pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); + pending->importance = 0; /* FIXME */ + pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); + vsm = (struct PeerVerifySuccessorMessage *) &pending[1]; + pending->msg = &vsm->header; + vsm->header.size = htons (msize); + vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR); + vsm->source_peer = source_peer; + vsm->successor = successor; + vsm->trail_id = trail_id; + peer_list = (struct GNUNET_PeerIdentity *) &vsm[1]; + memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity)); -// TODO: Move up -struct SendNotifyContext -{ - struct GNUNET_PeerIdentity source_peer; - struct GNUNET_PeerIdentity successor; - struct GNUNET_PeerIdentity *successor_trail; - unsigned int successor_trail_length; - struct GNUNET_HashCode succesor_trail_id; - struct FriendInfo *target_friend; - unsigned int num_retries_scheduled; -}; + /* Send the message to chosen friend. */ + GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); + target_friend->pending_count++; + process_friend_queue (target_friend); +} -void -send_notify_new_successor (void *cls, - const struct GNUNET_SCHEDULER_TaskContext - * tc); /** - * Check if the peer which sent us verify successor result message is still ours - * successor or not. If not, then compare existing successor and probable successor. - * In case probable successor is the correct successor, remove the existing - * successor. Add probable successor as new successor. Send notify new successor - * message to new successor. - * @param curr_succ Peer to which we sent the verify successor message. It may - * or may not be our real current successor, as we may have few iterations of - * find finger trail task. - * @param probable_successor Peer which should be our successor accroding to @a - * curr_succ - * @param trail List of peers to reach from me to @a probable successor, NOT including - * endpoints. - * @param trail_length Total number of peers in @a trail. + * FIXME: In every function we pass target friend except for this one. + * so, either change everything or this one. also, should se just store + * the pointer to friend in routing table rather than gnunet_peeridentity. + * if yes then we should keep friend info in.h andmake lot of changes. + * Construct a trail teardown message and forward it to target friend. + * + * @param trail_id Unique identifier of the trail. + * @param trail_direction Direction of trail. + * @param target_friend Friend to get this message. */ -static void -compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ, - struct GNUNET_PeerIdentity probable_successor, - const struct GNUNET_PeerIdentity *trail, - unsigned int trail_length) +void +GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_HashCode *trail_id, + unsigned int trail_direction, + const struct GNUNET_PeerIdentity *peer) { - struct FingerInfo *current_successor; - struct GNUNET_PeerIdentity closest_peer; - struct GNUNET_HashCode trail_id; - struct GNUNET_PeerIdentity *trail_me_to_probable_succ; + struct PeerTrailTearDownMessage *ttdm; + struct P2PPendingMessage *pending; struct FriendInfo *target_friend; - unsigned int trail_me_to_probable_succ_len; - unsigned int is_predecessor = 0; - uint64_t successor_value; - - current_successor = &finger_table[0]; - successor_value = compute_finger_identity_value(0); + size_t msize; - /* If probable successor is same as current_successor, do nothing. */ - if(0 == GNUNET_CRYPTO_cmp_peer_identity (&probable_successor, - ¤t_successor->finger_identity)) + msize = sizeof (struct PeerTrailTearDownMessage); + if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) { - if ((NULL != GDS_stats)) - { - char *my_id_str; - uint64_t succ; - char *key; - uint64_t my_id; - memcpy (&my_id, &my_identity, sizeof(uint64_t)); - my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity)); - memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t)); - succ = GNUNET_ntohll(succ); - GNUNET_asprintf (&key, "XDHT:%s:", my_id_str); - GNUNET_free (my_id_str); - - GNUNET_STATISTICS_set (GDS_stats, key, succ, 0); - GNUNET_free (key); - } - if (send_verify_successor_task == NULL) - send_verify_successor_task = - GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time, - &send_verify_successor_message, - NULL); + GNUNET_break (0); return; } - closest_peer = select_closest_peer (&probable_successor, - ¤t_successor->finger_identity, - successor_value, is_predecessor); - /* If the current_successor in the finger table is closest, then do nothing. */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (&closest_peer , - ¤t_successor->finger_identity)) + if (NULL == (target_friend = + GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer))) { - //FIXME: Is this a good place to return the stats. - if ((NULL != GDS_stats)) - { - char *my_id_str; - uint64_t succ; - char *key; - - my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity)); - memcpy(&succ, ¤t_successor->finger_identity, sizeof(uint64_t)); - GNUNET_asprintf (&key, "XDHT:%s:", my_id_str); - GNUNET_free (my_id_str); - GNUNET_STATISTICS_set (GDS_stats, key, succ, 0); - GNUNET_free (key); - } - - if(0 == successor_times) - { -// successor_times = 3; - verify_successor_next_send_time = - GNUNET_TIME_STD_BACKOFF (verify_successor_next_send_time); - } - else - successor_times--; - - - if (send_verify_successor_task == NULL) - send_verify_successor_task = - GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time, - &send_verify_successor_message, - NULL); + /* FIXME: In what case friend can be null. ?*/ + GNUNET_break (0); return; } - /* Probable successor is the closest peer.*/ - if(trail_length > 0) - { - GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap, - &trail[0])); - } - else - { - GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap, - &probable_successor)); - } - - trail_me_to_probable_succ_len = 0; - trail_me_to_probable_succ = - check_trail_me_to_probable_succ (probable_successor, - trail, trail_length, - &trail_me_to_probable_succ_len); - - /* Remove the existing successor. */ - remove_existing_finger (current_successor, 0); - /* Generate a new trail id to reach to your new successor. */ - GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG, - &trail_id, sizeof (trail_id)); - - if (trail_me_to_probable_succ_len > 0) - { - GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]); - GNUNET_assert (NULL != - (target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &trail_me_to_probable_succ[0]))); - } - else + if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) { - GDS_ROUTING_add (trail_id, my_identity, probable_successor); - GNUNET_assert (NULL != - (target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &probable_successor))); + GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), + 1, GNUNET_NO); } - add_new_finger (probable_successor, trail_me_to_probable_succ, - trail_me_to_probable_succ_len, trail_id, 0); - - struct SendNotifyContext *notify_ctx; - - notify_ctx = GNUNET_new(struct SendNotifyContext); - - notify_ctx->source_peer = my_identity; - notify_ctx->successor = probable_successor; - notify_ctx->successor_trail = - GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len); - memcpy(notify_ctx->successor_trail, trail_me_to_probable_succ, - sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len); - notify_ctx->successor_trail_length = trail_me_to_probable_succ_len; - notify_ctx->succesor_trail_id = trail_id; - notify_ctx->target_friend = target_friend; - notify_ctx->num_retries_scheduled = 0; - GNUNET_free_non_null (trail_me_to_probable_succ); + pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); + pending->importance = 0; /* FIXME */ + pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); + ttdm = (struct PeerTrailTearDownMessage *) &pending[1]; + pending->msg = &ttdm->header; + ttdm->header.size = htons (msize); + ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN); + ttdm->trail_id = *trail_id; + ttdm->trail_direction = htonl (trail_direction); - // TODO: Check if we should verify before schedule if already scheduled. - GNUNET_SCHEDULER_add_now(&send_notify_new_successor, (void*)notify_ctx); + /* Send the message to chosen friend. */ + GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); + target_friend->pending_count++; + process_friend_queue (target_friend); } - -void -send_notify_new_successor (void *cls, - const struct GNUNET_SCHEDULER_TaskContext - * tc) -{ - struct SendNotifyContext *ctx = (struct SendNotifyContext *) cls; - - GDS_NEIGHBOURS_send_notify_new_successor (ctx->source_peer, - ctx->successor, - ctx->successor_trail, - ctx->successor_trail_length, - ctx->succesor_trail_id, - ctx->target_friend); - - if (0 == ctx->num_retries_scheduled && - send_notify_new_successor_retry_task != NULL) - { - // Result from previous notify successos hasn't arrived, so the retry task - // hasn't been cancelled! Already a new notify successor must be called. - // We will cancel the retry request. - struct SendNotifyContext *old_notify_ctx; - old_notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task); - GNUNET_free (old_notify_ctx->successor_trail); - GNUNET_free (old_notify_ctx); - send_notify_new_successor_retry_task = NULL; - } - - ctx->num_retries_scheduled++; - send_notify_new_successor_retry_task = GNUNET_SCHEDULER_add_delayed(notify_successor_retry_time, - &send_notify_new_successor, - cls); -} - -/* - * Core handle for p2p verify successor result messages. - * @param cls closure - * @param message message - * @param peer peer identity this notification is about - * @return #GNUNET_OK on success, #GNUNET_SYSERR on error +/** + * Construct a verify successor result message and send it to target_friend + * @param querying_peer Peer which sent the verify successor message. + * @param source_successor Current_successor of @a querying_peer. + * @param current_predecessor Current predecessor of @a successor. Could be same + * or different from @a querying_peer. + * @param trail_id Unique identifier of the trail from @a querying_peer to + * @a successor, NOT including them. + * @param trail List of peers which are part of trail from @a querying_peer to + * @a successor, NOT including them. + * @param trail_length Total number of peers in @a trail + * @param trail_direction Direction in which we are sending the message. In this + * case we are sending result from @a successor to @a querying_peer. + * @param target_friend Next friend to get this message. */ -static int -handle_dht_p2p_verify_successor_result(void *cls, - const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) +void +GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer, + struct GNUNET_PeerIdentity current_successor, + struct GNUNET_PeerIdentity probable_successor, + struct GNUNET_HashCode trail_id, + const struct GNUNET_PeerIdentity *trail, + unsigned int trail_length, + enum GDS_ROUTING_trail_direction trail_direction, + struct FriendInfo *target_friend) { - const struct PeerVerifySuccessorResultMessage *vsrm; - enum GDS_ROUTING_trail_direction trail_direction; - struct GNUNET_PeerIdentity querying_peer; - struct GNUNET_HashCode trail_id; - struct GNUNET_PeerIdentity *next_hop; - struct FriendInfo *target_friend; - struct GNUNET_PeerIdentity probable_successor; - struct GNUNET_PeerIdentity current_successor; - const struct GNUNET_PeerIdentity *trail; - unsigned int trail_length; + struct PeerVerifySuccessorResultMessage *vsmr; + struct P2PPendingMessage *pending; + struct GNUNET_PeerIdentity *peer_list; size_t msize; - msize = ntohs (message->size); - if (msize < sizeof (struct PeerVerifySuccessorResultMessage)) - { - GNUNET_break_op (0); - return GNUNET_YES; - } + msize = sizeof (struct PeerVerifySuccessorResultMessage) + + (trail_length * sizeof(struct GNUNET_PeerIdentity)); - vsrm = (const struct PeerVerifySuccessorResultMessage *) message; - if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) % - sizeof (struct GNUNET_PeerIdentity) != 0) - { - GNUNET_break_op (0); - return GNUNET_OK; - } - trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/ - sizeof (struct GNUNET_PeerIdentity); - - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes received from other peers"), msize, - GNUNET_NO); - - trail = (const struct GNUNET_PeerIdentity *) &vsrm[1]; - querying_peer = vsrm->querying_peer; - trail_direction = ntohl (vsrm->trail_direction); - trail_id = vsrm->trail_id; - probable_successor = vsrm->probable_successor; - current_successor = vsrm->current_successor; - - /* I am the querying_peer. */ - if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity))) + if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) { - /* Cancel Retry Task */ - if (NULL != send_verify_successor_retry_task) - { - struct VerifySuccessorContext *ctx; - ctx = GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task); - GNUNET_free(ctx); - send_verify_successor_retry_task = NULL; - } - compare_and_update_successor (current_successor, - probable_successor, trail, trail_length); - return GNUNET_OK; + GNUNET_break (0); + return; } - /*If you are not the querying peer then pass on the message */ - if(NULL == (next_hop = - GDS_ROUTING_get_next_hop (trail_id, trail_direction))) - { - /* Here it may happen that source peer has found a new successor, and removed - the trail, Hence no entry found in the routing table. Fail silently.*/ - DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line", - GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__); - GNUNET_break_op(0); - return GNUNET_OK; - } - if (NULL == (target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop))) + if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) { - GNUNET_break_op(0); - return GNUNET_OK; + GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), + 1, GNUNET_NO); } - GDS_NEIGHBOURS_send_verify_successor_result (querying_peer, - vsrm->current_successor, - probable_successor, trail_id, - trail, - trail_length, - trail_direction, target_friend); - return GNUNET_OK; -} + pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); + pending->importance = 0; /* FIXME */ + pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); + vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1]; + pending->msg = &vsmr->header; + vsmr->header.size = htons (msize); + vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT); + vsmr->querying_peer = querying_peer; + vsmr->current_successor = current_successor; + vsmr->probable_successor = probable_successor; + vsmr->trail_direction = htonl (trail_direction); + vsmr->trail_id = trail_id; + peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1]; + memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity)); -/* - * Core handle for p2p notify new successor messages. - * @param cls closure - * @param message message - * @param peer peer identity this notification is about - * @return #GNUNET_OK on success, #GNUNET_SYSERR on error + /* Send the message to chosen friend. */ + GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); + target_friend->pending_count++; + process_friend_queue (target_friend); +} + +/** + * Construct a Put message and send it to target_peer. + * @param key Key for the content + * @param block_type Type of the block + * @param options Routing options + * @param desired_replication_level Desired replication count + * @param best_known_dest Peer to which this message should reach eventually, + * as it is best known destination to me. + * @param intermediate_trail_id Trail id in case + * @param target_peer Peer to which this message will be forwarded. + * @param hop_count Number of hops traversed so far. + * @param put_path_length Total number of peers in @a put_path + * @param put_path Number of peers traversed so far + * @param expiration_time When does the content expire + * @param data Content to store + * @param data_size Size of content @a data in bytes */ -static int -handle_dht_p2p_notify_new_successor(void *cls, - const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) +void +GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key, + enum GNUNET_BLOCK_Type block_type, + enum GNUNET_DHT_RouteOption options, + uint32_t desired_replication_level, + struct GNUNET_PeerIdentity best_known_dest, + struct GNUNET_HashCode intermediate_trail_id, + struct GNUNET_PeerIdentity *target_peer, + uint32_t hop_count, + uint32_t put_path_length, + struct GNUNET_PeerIdentity *put_path, + struct GNUNET_TIME_Absolute expiration_time, + const void *data, size_t data_size) { - const struct PeerNotifyNewSuccessorMessage *nsm; - struct GNUNET_PeerIdentity *trail; - struct GNUNET_PeerIdentity source; - struct GNUNET_PeerIdentity new_successor; - struct GNUNET_HashCode trail_id; - struct GNUNET_PeerIdentity next_hop; + struct PeerPutMessage *ppm; + struct P2PPendingMessage *pending; struct FriendInfo *target_friend; - int my_index; + struct GNUNET_PeerIdentity *pp; size_t msize; - uint32_t trail_length; - msize = ntohs (message->size); - if (msize < sizeof (struct PeerNotifyNewSuccessorMessage)) - { - GNUNET_break_op (0); - return GNUNET_YES; - } - nsm = (const struct PeerNotifyNewSuccessorMessage *) message; - if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) % - sizeof (struct GNUNET_PeerIdentity) != 0) - { - GNUNET_break_op (0); - return GNUNET_OK; - } - trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/ - sizeof (struct GNUNET_PeerIdentity); - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes received from other peers"), msize, - GNUNET_NO); - - trail = (struct GNUNET_PeerIdentity *) &nsm[1]; - source = nsm->source_peer; - new_successor = nsm->new_successor; - trail_id = nsm->trail_id; - - /* I am the new_successor to source_peer. */ - if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor)) + msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size + + sizeof (struct PeerPutMessage); + if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) { - if(trail_length > 0) - GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&trail[trail_length - 1], - peer)); - else - GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity(&source, peer)); - - compare_and_update_predecessor (source, trail, trail_length); - target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer); - GNUNET_assert (NULL != target_friend); - GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id, - GDS_ROUTING_DEST_TO_SRC, - target_friend); - return GNUNET_OK; + put_path_length = 0; + msize = data_size + sizeof (struct PeerPutMessage); } - GNUNET_assert(trail_length > 0); - /* I am part of trail to reach to successor. */ - my_index = search_my_index (trail, trail_length); - if (-1 == my_index) - { - DEBUG ("No entry found in trail\n"); - GNUNET_break_op (0); - return GNUNET_SYSERR; - } - if((trail_length + 1) == my_index) + if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) { - DEBUG ("Found twice in trail.\n"); - GNUNET_break_op (0); - return GNUNET_SYSERR; + DEBUG("msize = %lu\n",msize); + GNUNET_break (0); + return; } - if ((trail_length-1) == my_index) - next_hop = new_successor; - else - next_hop = trail[my_index + 1]; - - GDS_ROUTING_add(trail_id, *peer, next_hop); - target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop); - if (NULL == target_friend) + + GNUNET_assert (NULL != + (target_friend = + GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); + pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); + pending->timeout = expiration_time; + ppm = (struct PeerPutMessage *) &pending[1]; + pending->msg = &ppm->header; + ppm->header.size = htons (msize); + ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT); + ppm->options = htonl (options); + ppm->block_type = htonl (block_type); + ppm->hop_count = htonl (hop_count + 1); + ppm->desired_replication_level = htonl (desired_replication_level); + ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time); + ppm->best_known_destination = best_known_dest; + ppm->intermediate_trail_id = intermediate_trail_id; + ppm->key = *key; + pp = (struct GNUNET_PeerIdentity *) &ppm[1]; + ppm->put_path_length = htonl (put_path_length); + if(put_path_length > 0) { - GNUNET_break(0); - return GNUNET_OK; + memcpy (pp, put_path, + sizeof (struct GNUNET_PeerIdentity) * put_path_length); } - GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail, - trail_length, - trail_id, target_friend); - return GNUNET_OK; - + memcpy (&pp[put_path_length], data, data_size); + GNUNET_assert (NULL != target_friend); + GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); + target_friend->pending_count++; + process_friend_queue (target_friend); } /** - * Core handler for P2P notify successor message - * @param cls closure - * @param message message - * @param peer peer identity this notification is about - * @return #GNUNET_OK on success, #GNUNET_SYSERR on error + * Handle the put request from the client. + * @param key Key for the content + * @param block_type Type of the block + * @param options Routing options + * @param desired_replication_level Desired replication count + * @param expiration_time When does the content expire + * @param data Content to store + * @param data_size Size of content @a data in bytes */ -static int -handle_dht_p2p_notify_succ_confirmation (void *cls, - const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) +void +GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key, + enum GNUNET_BLOCK_Type block_type, + enum GNUNET_DHT_RouteOption options, + uint32_t desired_replication_level, + struct GNUNET_TIME_Absolute expiration_time, + const void *data, size_t data_size) { - const struct PeerNotifyConfirmationMessage *notify_confirmation; - enum GDS_ROUTING_trail_direction trail_direction; - struct GNUNET_HashCode trail_id; - struct FriendInfo *target_friend; - struct GNUNET_PeerIdentity *next_hop; - size_t msize; + struct GNUNET_PeerIdentity best_known_dest; + struct GNUNET_HashCode intermediate_trail_id; + struct GNUNET_PeerIdentity next_hop; + uint64_t key_value; + struct Closest_Peer successor; - msize = ntohs (message->size); + memcpy (&key_value, key, sizeof (uint64_t)); + key_value = GNUNET_ntohll (key_value); + successor = find_local_best_known_next_hop (key_value, + GDS_FINGER_TYPE_NON_PREDECESSOR); + best_known_dest = successor.best_known_destination; + next_hop = successor.next_hop; + intermediate_trail_id = successor.trail_id; - if (msize != sizeof (struct PeerNotifyConfirmationMessage)) + if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)) { - GNUNET_break_op (0); - return GNUNET_OK; + DEBUG("\n PUT_REQUEST_SUCCESSFUL for key = %s",GNUNET_h2s(key)); + /* I am the destination. */ + GDS_DATACACHE_handle_put (expiration_time, key, 0, NULL, + block_type,data_size,data); + GDS_CLIENTS_process_put (options, block_type, 0, + ntohl (desired_replication_level), + 1, &my_identity, expiration_time, //FIXME: GNUNETnthoh something on expiration time. + key, data, data_size); + return; } - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes received from other peers"), msize, - GNUNET_NO); - - notify_confirmation = (const struct PeerNotifyConfirmationMessage *) message; - trail_direction = ntohl (notify_confirmation->trail_direction); - trail_id = notify_confirmation->trail_id; - - next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction); - if (NULL == next_hop) + /* In case we are sending the request to a finger, then send across all of its + trail.*/ +#if ENABLE_MALICIOUS + if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination, + &successor.next_hop)) { - /* The source of notify new successor, might have found even a better - successor. In that case it send a trail teardown message, and hence, - the next hop is NULL. */ - //Fixme: Add some print to confirm the above theory. - return GNUNET_OK; - } + struct FingerInfo *next_hop_finger; + unsigned int i; - /* I peer which sent the notify successor message to the successor. */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)) - { - /* - * Schedule another round of verify sucessor with your current successor - * which may or may not be source of this message. This message is used - * only to ensure that we have a path setup to reach to our successor. - */ - - // TODO: cancel schedule of notify_successor_retry_task - if (send_notify_new_successor_retry_task != NULL) - { - struct SendNotifyContext *notify_ctx; - notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task); - GNUNET_free (notify_ctx->successor_trail); - GNUNET_free (notify_ctx); - send_notify_new_successor_retry_task = NULL; - } - if (send_verify_successor_task == NULL) - { - verify_successor_next_send_time.rel_value_us = - DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us + - GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, - DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us); - send_verify_successor_task = - GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time, - &send_verify_successor_message, - NULL); - } - } - else - { - target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop); - if (NULL == target_friend) + next_hop_finger = &finger_table[successor.finger_table_index]; + for (i = 0; i < next_hop_finger->trails_count; i++) { - DEBUG ("\n friend not found, line number = %d",__LINE__); - return GNUNET_SYSERR; + if (GNUNET_YES == next_hop_finger->trail_list[i].is_present) + { + if(0 == next_hop_finger->trail_list[i].trail_length) + { + GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level, + best_known_dest, intermediate_trail_id, &next_hop, + 0, 1, &my_identity, expiration_time, + data, data_size); + return; + } + next_hop = next_hop_finger->trail_list[i].trail_head->peer; + GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level, + best_known_dest, + next_hop_finger->trail_list[i].trail_id, + &next_hop, 0, 1, &my_identity, + expiration_time, + data, data_size); + } } - GDS_NEIGHBOURS_send_notify_succcessor_confirmation (trail_id, - GDS_ROUTING_DEST_TO_SRC, - target_friend); + return; } - return GNUNET_OK; +#endif + GDS_NEIGHBOURS_send_put (key, block_type, options, desired_replication_level, + best_known_dest, intermediate_trail_id, &next_hop, + 0, 1, &my_identity, expiration_time, + data, data_size); } - /** - * Core handler for P2P trail rejection message - * @param cls closure - * @param message message - * @param peer peer identity this notification is about - * @return #GNUNET_OK on success, #GNUNET_SYSERR on error + * Construct a Get message and send it to target_peer. + * @param key Key for the content + * @param block_type Type of the block + * @param options Routing options + * @param desired_replication_level Desired replication count + * @param best_known_dest Peer which should get this message. Same as target peer + * if best_known_dest is a friend else its a finger. + * @param intermediate_trail_id Trail id to reach to @a best_known_dest + * in case it is a finger else set to 0. + * @param target_peer Peer to which this message will be forwarded. + * @param hop_count Number of hops traversed so far. + * @param data Content to store + * @param data_size Size of content @a data in bytes + * @param get_path_length Total number of peers in @a get_path + * @param get_path Number of peers traversed so far */ -static int -handle_dht_p2p_trail_setup_rejection (void *cls, - const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) +void +GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key, + enum GNUNET_BLOCK_Type block_type, + enum GNUNET_DHT_RouteOption options, + uint32_t desired_replication_level, + struct GNUNET_PeerIdentity best_known_dest, + struct GNUNET_HashCode intermediate_trail_id, + struct GNUNET_PeerIdentity *target_peer, + uint32_t hop_count, + uint32_t get_path_length, + struct GNUNET_PeerIdentity *get_path) { - const struct PeerTrailRejectionMessage *trail_rejection; - unsigned int trail_length; - const struct GNUNET_PeerIdentity *trail_peer_list; + struct PeerGetMessage *pgm; + struct P2PPendingMessage *pending; struct FriendInfo *target_friend; - struct GNUNET_TIME_Relative congestion_timeout; - struct GNUNET_HashCode trail_id; - struct GNUNET_PeerIdentity next_peer; - struct GNUNET_PeerIdentity source; - uint64_t ultimate_destination_finger_value; - unsigned int is_predecessor; + struct GNUNET_PeerIdentity *gp; size_t msize; - msize = ntohs (message->size); - if (msize < sizeof (struct PeerTrailRejectionMessage)) - { - GNUNET_break_op (0); - return GNUNET_YES; - } - trail_rejection = (const struct PeerTrailRejectionMessage *) message; - if ((msize - sizeof (struct PeerTrailRejectionMessage)) % - sizeof (struct GNUNET_PeerIdentity) != 0) - { - GNUNET_break_op (0); - return GNUNET_OK; - } - trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/ - sizeof (struct GNUNET_PeerIdentity); - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes received from other peers"), msize, - GNUNET_NO); - - trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1]; - is_predecessor = ntohl (trail_rejection->is_predecessor); - congestion_timeout = trail_rejection->congestion_time; - source = trail_rejection->source_peer; - trail_id = trail_rejection->trail_id; - ultimate_destination_finger_value = - GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value); - /* First set the congestion time of the friend that sent you this message. */ - target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer); - if (NULL == target_friend) - { - DEBUG ("\nLINE = %d ,No friend found.",__LINE__); - GNUNET_break(0); - return GNUNET_OK; - } - target_friend->congestion_timestamp = - GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(), - congestion_timeout); - - /* I am the source peer which wants to setup the trail. Do nothing. - * send_find_finger_trail_task is scheduled periodically.*/ - if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source))) - return GNUNET_OK; - - /* If I am congested then pass this message to peer before me in trail. */ - if(GNUNET_YES == GDS_ROUTING_threshold_reached()) - { - /* First remove yourself from the trail. */ - unsigned int new_trail_length = trail_length - 1; - struct GNUNET_PeerIdentity trail[new_trail_length]; - - memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity)); - if (0 == trail_length) - next_peer = source; - else - next_peer = trail[new_trail_length-1]; - - target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer); - if (NULL == target_friend) - { - DEBUG ("\nLINE = %d ,No friend found.",__LINE__); - GNUNET_break(0); - return GNUNET_OK; - } - GDS_NEIGHBOURS_send_trail_rejection (source, - ultimate_destination_finger_value, - my_identity, is_predecessor, - trail, new_trail_length, trail_id, - target_friend, CONGESTION_TIMEOUT); - return GNUNET_OK; - } - - struct Closest_Peer successor; - successor = find_local_best_known_next_hop (ultimate_destination_finger_value, is_predecessor); + msize = sizeof (struct PeerGetMessage) + + (get_path_length * sizeof (struct GNUNET_PeerIdentity)); - /* Am I the final destination? */ - if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination, - &my_identity))) + if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) { - /*Here you are already part of trail. Copy the trail removing yourself. */ - unsigned int new_trail_length = trail_length - 1; - struct GNUNET_PeerIdentity trail[new_trail_length]; - - memcpy (trail, trail_peer_list, new_trail_length * sizeof(struct GNUNET_PeerIdentity)); - - if (0 == new_trail_length) - next_peer = source; - else - { - next_peer = trail[new_trail_length-1]; - } - target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer); - - if (NULL == target_friend) - { - DEBUG ("\nLINE = %d ,No friend found.",__LINE__); - GNUNET_break(0); - return GNUNET_OK; - } - GDS_NEIGHBOURS_send_trail_setup_result (source, - my_identity, - target_friend, new_trail_length, - trail, - is_predecessor, - ultimate_destination_finger_value, - trail_id); + GNUNET_break (0); + return; } - else - { - /* Here I was already part of trail. So no need to add. */ - target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - &successor.next_hop); - if (NULL == target_friend) - { - DEBUG ("\nLINE = %d ,No friend found.",__LINE__); - GNUNET_break(0); - return GNUNET_OK; - } + GNUNET_assert (NULL != + (target_friend = + GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); - GDS_NEIGHBOURS_send_trail_setup (source, - ultimate_destination_finger_value, - successor.best_known_destination, - target_friend, trail_length, trail_peer_list, - is_predecessor, trail_id, - successor.trail_id); - } - return GNUNET_OK; + pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); + pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); + pending->importance = 0; /* FIXME */ + pgm = (struct PeerGetMessage *) &pending[1]; + pending->msg = &pgm->header; + pgm->header.size = htons (msize); + pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET); + pgm->get_path_length = htonl (get_path_length); + pgm->best_known_destination = best_known_dest; + pgm->key = *key; + pgm->intermediate_trail_id = intermediate_trail_id; + pgm->hop_count = htonl (hop_count + 1); + pgm->get_path_length = htonl (get_path_length); + gp = (struct GNUNET_PeerIdentity *) &pgm[1]; + memcpy (gp, get_path, + sizeof (struct GNUNET_PeerIdentity) * get_path_length); + GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); + target_friend->pending_count++; + process_friend_queue (target_friend); } /** - * Core handler for trail teardown message. - * @param cls closure - * @param message message - * @param peer sender of this messsage. - * @return #GNUNET_OK on success, #GNUNET_SYSERR on error + * Handle the get request from the client file. If I am destination do + * datacache put and return. Else find the target friend and forward message + * to it. + * @param key Key for the content + * @param block_type Type of the block + * @param options Routing options + * @param desired_replication_level Desired replication count */ -static int -handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) +void +GDS_NEIGHBOURS_handle_get(const struct GNUNET_HashCode *key, + enum GNUNET_BLOCK_Type block_type, + enum GNUNET_DHT_RouteOption options, + uint32_t desired_replication_level) { - const struct PeerTrailTearDownMessage *trail_teardown; - enum GDS_ROUTING_trail_direction trail_direction; - struct GNUNET_HashCode trail_id; - struct GNUNET_PeerIdentity *next_hop; - size_t msize; + struct Closest_Peer successor; + struct GNUNET_PeerIdentity best_known_dest; + struct GNUNET_HashCode intermediate_trail_id; + uint64_t key_value; - msize = ntohs (message->size); + memcpy (&key_value, key, sizeof (uint64_t)); + key_value = GNUNET_ntohll (key_value); - /* Here we pass only the trail id. */ - if (msize != sizeof (struct PeerTrailTearDownMessage)) - { - GNUNET_break_op (0); - return GNUNET_OK; - } + successor = find_local_best_known_next_hop (key_value, + GDS_FINGER_TYPE_NON_PREDECESSOR); - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes received from other peers"), msize, - GNUNET_NO); - - trail_teardown = (const struct PeerTrailTearDownMessage *) message; - trail_direction = ntohl (trail_teardown->trail_direction); - trail_id = trail_teardown->trail_id; - - /* Check if peer is the real peer from which we should get this message.*/ - /* Get the prev_hop for this trail by getting the next hop in opposite direction. */ -#if 0 - GNUNET_assert (NULL != (prev_hop = - GDS_ROUTING_get_next_hop (trail_id, !trail_direction))); - if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer)) - { - GNUNET_break (0); - return GNUNET_SYSERR; - } -#endif + best_known_dest = successor.best_known_destination; + intermediate_trail_id = successor.trail_id; - next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction); - if (NULL == next_hop) + /* I am the destination. I have the data. */ + if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, + &best_known_dest)) { - DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line", - GNUNET_i2s(&my_identity), GNUNET_h2s(&trail_id), __LINE__); - GNUNET_break (0); - return GNUNET_SYSERR; + GDS_DATACACHE_handle_get (key,block_type, NULL, 0, + NULL, 0, 1, &my_identity, NULL,&my_identity); + return; } - /* I am the next hop, which means I am the final destination. */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)) - { - GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id)); - return GNUNET_OK; - } - else +#if ENABLE_MALICIOUS + struct GNUNET_PeerIdentity next_hop; + if (0 != GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination, + &successor.next_hop)) { - /* If not final destination, then send a trail teardown message to next hop.*/ - GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)); - GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id)); - GDS_NEIGHBOURS_send_trail_teardown (&trail_id, trail_direction, next_hop); - } + struct FingerInfo *next_hop_finger; + unsigned int i; - return GNUNET_OK; + next_hop_finger = &finger_table[successor.finger_table_index]; + for (i = 0; i < next_hop_finger->trails_count; i++) + { + if (GNUNET_YES == next_hop_finger->trail_list[i].is_present) + { + if(0 == next_hop_finger->trail_list[i].trail_length) + { + GDS_NEIGHBOURS_send_get (key, block_type, options, + desired_replication_level, + best_known_dest,intermediate_trail_id, + &successor.next_hop, + 0, 1, &my_identity); + return; + } + next_hop = next_hop_finger->trail_list[i].trail_head->peer; + GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level, + best_known_dest, + next_hop_finger->trail_list[i].trail_id, + &next_hop, 0, 1, &my_identity); + } + } + return; + } +#endif + GDS_NEIGHBOURS_send_get (key, block_type, options, desired_replication_level, + best_known_dest,intermediate_trail_id, &successor.next_hop, + 0, 1, &my_identity); } /** - * Core handle for p2p add trail message. - * @param cls closure - * @param message message - * @param peer peer identity this notification is about - * @return #GNUNET_OK on success, #GNUNET_SYSERR on error + * Send the get result to requesting client. + * + * @param key Key of the requested data. + * @param type Block type + * @param target_peer Next peer to forward the message to. + * @param source_peer Peer which has the data for the key. + * @param put_path_length Number of peers in @a put_path + * @param put_path Path taken to put the data at its stored location. + * @param get_path_length Number of peers in @a get_path + * @param get_path Path taken to reach to the location of the key. + * @param expiration When will this result expire? + * @param data Payload to store + * @param data_size Size of the @a data */ -static int -handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer, - const struct GNUNET_MessageHeader *message) +void +GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key, + enum GNUNET_BLOCK_Type type, + const struct GNUNET_PeerIdentity *target_peer, + const struct GNUNET_PeerIdentity *source_peer, + unsigned int put_path_length, + const struct GNUNET_PeerIdentity *put_path, + unsigned int get_path_length, + const struct GNUNET_PeerIdentity *get_path, + struct GNUNET_TIME_Absolute expiration, + const void *data, size_t data_size) { - const struct PeerAddTrailMessage *add_trail; - const struct GNUNET_PeerIdentity *trail; - struct GNUNET_HashCode trail_id; - struct GNUNET_PeerIdentity destination_peer; - struct GNUNET_PeerIdentity source_peer; - struct GNUNET_PeerIdentity next_hop; - unsigned int trail_length; - unsigned int my_index; + struct PeerGetResultMessage *get_result; + struct GNUNET_PeerIdentity *paths; + struct P2PPendingMessage *pending; + struct FriendInfo *target_friend; + int current_path_index; size_t msize; - msize = ntohs (message->size); - /* In this message we pass the whole trail from source to destination as we - * are adding that trail.*/ - //FIXME: failed when run with 1000 pears. check why. - if (msize < sizeof (struct PeerAddTrailMessage)) + msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) + + data_size + + sizeof (struct PeerGetResultMessage); + + if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) { - GNUNET_break_op (0); - return GNUNET_OK; + put_path_length = 0; + msize = msize - put_path_length * sizeof (struct GNUNET_PeerIdentity); } - add_trail = (const struct PeerAddTrailMessage *) message; - trail_length = (msize - sizeof (struct PeerAddTrailMessage))/ - sizeof (struct GNUNET_PeerIdentity); - if ((msize - sizeof (struct PeerAddTrailMessage)) % - sizeof (struct GNUNET_PeerIdentity) != 0) + if (msize >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE) { - GNUNET_break_op (0); - return GNUNET_OK; + GNUNET_break(0); + return; } - - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Bytes received from other peers"), msize, - GNUNET_NO); - - trail = (const struct GNUNET_PeerIdentity *)&add_trail[1]; - destination_peer = add_trail->destination_peer; - source_peer = add_trail->source_peer; - trail_id = add_trail->trail_id; - - /* I am not the destination of the trail. */ - if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer)) + current_path_index = 0; + if(get_path_length > 0) { - struct FriendInfo *target_friend; - - /* Get my location in the trail. */ - my_index = search_my_index (trail, trail_length); - if (-1 == my_index) - { - GNUNET_break_op (0); - return GNUNET_SYSERR; - } - if((trail_length + 1) == my_index) - { - DEBUG ("Found twice in trail.\n"); - GNUNET_break_op (0); - return GNUNET_SYSERR; - } - if ((trail_length - 1) == my_index) + current_path_index = search_my_index(get_path, get_path_length); + if (-1 == current_path_index) { - next_hop = destination_peer; + GNUNET_break (0); + return; } - else + if ((get_path_length + 1) == current_path_index) { - next_hop = trail[my_index + 1]; + DEBUG ("Peer found twice in get path. Not allowed \n"); + GNUNET_break (0); + return; } - /* Add in your routing table. */ - GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop)); - //GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer)); - GNUNET_assert (NULL != - (target_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop))); - GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id, - trail, trail_length, target_friend); - return GNUNET_OK; } - /* I am the destination. Add an entry in routing table. */ - GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity)); - return GNUNET_OK; -} - - -/** - * Free the finger trail in which the first friend to reach to a finger is - * disconnected_friend. Also remove entry from routing table for that particular - * trail id. - * @param disconnected_friend PeerIdentity of friend which got disconnected - * @param remove_finger Finger whose trail we need to check if it has - * disconnected_friend as the first hop. - * @return Total number of trails in which disconnected_friend was the first - * hop. - */ -static int -remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend, - struct FingerInfo *finger) -{ - struct GNUNET_PeerIdentity *next_hop; - struct FriendInfo *remove_friend; - struct Trail *current_trail; - unsigned int matching_trails_count = 0; - int i; - - /* Iterate over all the trails of finger. */ - for (i = 0; i < finger->trails_count; i++) + if (0 == current_path_index) { - current_trail = &finger->trail_list[i]; - if (GNUNET_NO == current_trail->is_present) - continue; - - /* First friend to reach to finger is disconnected_peer. */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_trail->trail_head->peer, - disconnected_friend)) - { - remove_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, - disconnected_friend); - GNUNET_assert (NULL != remove_friend); - next_hop = GDS_ROUTING_get_next_hop (current_trail->trail_id, - GDS_ROUTING_SRC_TO_DEST); - - /* Here it may happen that as all the peers got disconnected, the entry in - routing table for that particular trail has been removed, because the - previously disconnected peer was either a next hop or prev hop of that - peer. */ - if (NULL != next_hop) - { - GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend, - next_hop))); - GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (current_trail->trail_id)); - } - matching_trails_count++; - free_trail (current_trail); - current_trail->is_present = GNUNET_NO; - } + DEBUG ("GET_RESULT TO CLIENT KEY = %s, Peer = %s",GNUNET_h2s(key),GNUNET_i2s(&my_identity)); + GDS_CLIENTS_handle_reply (expiration, key, get_path_length, + get_path, put_path_length, + put_path, type, data_size, data); + return; } - return matching_trails_count; -} - - -/** - * Iterate over finger_table entries. - * 0. Ignore finger which is my_identity or if no valid entry present at - * that finger index. - * 1. If disconnected_friend is a finger, then remove the routing entry from - your own table. Free the trail. - * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger. - * 2.1 Remove all the trails and entry from routing table in which disconnected - * friend is the first friend in the trail. If disconnected_friend is the - * first friend in all the trails to reach finger, then remove the finger. - * @param disconnected_friend Peer identity of friend which got disconnected. - */ -static void -remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer) -{ - struct FingerInfo *current_finger; - int removed_trails_count; - int i; - - /* Iterate over finger table entries. */ - for (i = 0; i < MAX_FINGERS; i++) - { - current_finger = &finger_table[i]; - - /* No finger stored at this trail index or I am the finger. */ - if ((GNUNET_NO == current_finger->is_present) || - (0 == GNUNET_CRYPTO_cmp_peer_identity (¤t_finger->finger_identity, - &my_identity))) - continue; - /* Is disconnected_peer a finger? */ - if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer, - ¤t_finger->finger_identity)) - { - remove_existing_finger (current_finger, i); - } + pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); + pending->timeout = GNUNET_TIME_relative_to_absolute (PENDING_MESSAGE_TIMEOUT); + pending->importance = 0; + get_result = (struct PeerGetResultMessage *)&pending[1]; + pending->msg = &get_result->header; + get_result->header.size = htons (msize); + get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT); + get_result->key = *key; + get_result->querying_peer = *source_peer; + get_result->expiration_time = expiration; + get_result->get_path_length = htonl (get_path_length); + get_result->put_path_length = htonl (put_path_length); + paths = (struct GNUNET_PeerIdentity *)&get_result[1]; + memcpy (paths, put_path, + put_path_length * sizeof (struct GNUNET_PeerIdentity)); + memcpy (&paths[put_path_length], get_path, + get_path_length * sizeof (struct GNUNET_PeerIdentity)); + memcpy (&paths[put_path_length + get_path_length], data, data_size); - /* If finger is a friend but not disconnected_friend, then continue. */ - if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, - ¤t_finger->finger_identity)) - continue; - - /* Iterate over the list of trails to reach remove_finger. Check if - * disconnected_friend is the first friend in any of the trail. */ - removed_trails_count = remove_matching_trails (disconnected_peer, - current_finger); - current_finger->trails_count = - current_finger->trails_count - removed_trails_count; - if (0 == current_finger->trails_count) - { - current_finger->is_present = GNUNET_NO; - memset ((void *)&finger_table[i], 0, sizeof (finger_table[i])); - } - } + GNUNET_assert (NULL != + (target_friend = + GNUNET_CONTAINER_multipeermap_get (friend_peermap, + &get_path[current_path_index - 1]))); + GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); + target_friend->pending_count++; + process_friend_queue (target_friend); } @@ -6016,61 +1304,29 @@ remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer) */ static void handle_core_disconnect (void *cls, - const struct GNUNET_PeerIdentity *peer) + const struct GNUNET_PeerIdentity *peer) { struct FriendInfo *remove_friend; - struct P2PPendingMessage *pos; - unsigned int discarded; /* If disconnected to own identity, then return. */ - if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity))) + if (0 == memcmp (&my_identity, + peer, + sizeof (struct GNUNET_PeerIdentity))) return; - if(NULL == (remove_friend = - GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer))) + if (NULL == (remove_friend = + GNUNET_CONTAINER_multipeermap_get (friend_peermap, + peer))) { - DEBUG("\n friend already disconnected."); + GNUNET_break (0); return; } - remove_matching_fingers (peer); - GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer)); GNUNET_assert (GNUNET_YES == GNUNET_CONTAINER_multipeermap_remove (friend_peermap, peer, remove_friend)); - - /* Remove all the messages queued in pending list of this peer is discarded.*/ - if (remove_friend->th != NULL) - { - GNUNET_CORE_notify_transmit_ready_cancel(remove_friend->th); - remove_friend->th = NULL; - } - - discarded = 0; - while (NULL != (pos = remove_friend->head)) - { - GNUNET_CONTAINER_DLL_remove (remove_friend->head, remove_friend->tail, pos); - discarded++; - GNUNET_free (pos); - } - - GNUNET_STATISTICS_update (GDS_stats, - gettext_noop - ("# Queued messages discarded (peer disconnected)"), - discarded, GNUNET_NO); - //GNUNET_free (remove_friend); - - if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap)) - return; - - if (NULL != find_finger_trail_task) - { - GNUNET_SCHEDULER_cancel (find_finger_trail_task); - find_finger_trail_task = NULL; - } - else - GNUNET_break (0); + /* FIXME: do stuff */ } @@ -6081,17 +1337,21 @@ handle_core_disconnect (void *cls, * @param peer_identity peer identity this notification is about */ static void -handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity) +handle_core_connect (void *cls, + const struct GNUNET_PeerIdentity *peer_identity) { struct FriendInfo *friend; /* Check for connect to self message */ - if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity))) + if (0 == memcmp (&my_identity, + peer_identity, + sizeof (struct GNUNET_PeerIdentity))) return; /* If peer already exists in our friend_peermap, then exit. */ - if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, - peer_identity)) + if (GNUNET_YES == + GNUNET_CONTAINER_multipeermap_contains (friend_peermap, + peer_identity)) { GNUNET_break (0); return; @@ -6102,18 +1362,10 @@ handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity) GNUNET_assert (GNUNET_OK == GNUNET_CONTAINER_multipeermap_put (friend_peermap, - peer_identity, friend, + peer_identity, + friend, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); - - /* FIXME: now we are not making a distinction between fingers which are friends - * also.But later, we should add a congestion timestamp on the friend, so that it is - * selected after some time out. This is to ensure that both peers have added - * each other as their friend. */ - /* Got a first connection, good time to start with FIND FINGER TRAIL requests...*/ - if (NULL == find_finger_trail_task) - { - find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL); - } + /* do work? */ } @@ -6132,15 +1384,27 @@ core_init (void *cls, /** - * Initialize finger table entries. + * Handle a `struct FingerSetupMessage`. + * + * @param cls closure (NULL) + * @param peer sender identity + * @param message the setup message + * @return #GNUNET_OK on success, #GNUNET_SYSERR on error */ -static void -finger_table_init () +static int +handle_dht_p2p_finger_setup (void *cls, + const struct GNUNET_PeerIdentity *peer, + const struct GNUNET_MessageHeader *message) { - memset (&finger_table, 0, sizeof (finger_table)); + const struct FingerSetupMessage *fsm; + + fsm = (const struct FingerSetupMessage *) message; + + return GNUNET_OK; } + /** * Initialize neighbours subsystem. * @return #GNUNET_OK on success, #GNUNET_SYSERR on error @@ -6148,21 +1412,10 @@ finger_table_init () int GDS_NEIGHBOURS_init (void) { - static struct GNUNET_CORE_MessageHandler core_handlers[] = { - {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0}, - {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0}, - {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0}, - {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0}, - {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0}, - {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0}, - {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0}, - {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0}, - {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0}, - {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN, - sizeof (struct PeerTrailTearDownMessage)}, - {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0}, - {&handle_dht_p2p_notify_succ_confirmation, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION, - sizeof (struct PeerNotifyConfirmationMessage)}, + static const struct GNUNET_CORE_MessageHandler core_handlers[] = { + { &handle_dht_p2p_finger_setup, + GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP, + sizeof (struct FingerSetupMessage) }, {NULL, 0, 0} }; @@ -6171,63 +1424,23 @@ GDS_NEIGHBOURS_init (void) #endif core_api = - GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect, - &handle_core_disconnect, NULL, GNUNET_NO, NULL, - GNUNET_NO, core_handlers); + GNUNET_CORE_connect (GDS_cfg, NULL, + &core_init, + &handle_core_connect, + &handle_core_disconnect, + NULL, GNUNET_NO, + NULL, GNUNET_NO, + core_handlers); if (NULL == core_api) return GNUNET_SYSERR; //TODO: check size of this peer map? friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO); - finger_table_init (); - successor_times = 10; - fingers_round_count = 5; - find_finger_trail_task_next_send_time.rel_value_us = - DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us + - GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, - DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us); - - verify_successor_next_send_time.rel_value_us = - DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us + - GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, - DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us); - - verify_successor_retry_time.rel_value_us = - DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us + - GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, - DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us); - - notify_successor_retry_time.rel_value_us = - DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us + - GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, - DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us); - - return GNUNET_OK; } -/** - * Free the memory held up by trails of a finger. - */ -static void -delete_finger_table_entries() -{ - unsigned int i; - unsigned int j; - - for(i = 0; i < MAX_FINGERS; i++) - { - if(GNUNET_YES == finger_table[i].is_present) - { - for(j = 0; j < finger_table[i].trails_count; j++) - free_trail(&finger_table[i].trail_list[j]); - } - } -} - - /** * Shutdown neighbours subsystem. */ @@ -6236,43 +1449,12 @@ GDS_NEIGHBOURS_done (void) { if (NULL == core_api) return; - GNUNET_CORE_disconnect (core_api); core_api = NULL; - delete_finger_table_entries(); GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap)); GNUNET_CONTAINER_multipeermap_destroy (friend_peermap); friend_peermap = NULL; - - if (NULL != find_finger_trail_task) - { - GNUNET_SCHEDULER_cancel (find_finger_trail_task); - find_finger_trail_task = NULL; - } - - if (NULL != send_verify_successor_task) - { - GNUNET_SCHEDULER_cancel (send_verify_successor_task); - send_verify_successor_task = NULL; - } - - if (NULL != send_verify_successor_retry_task) - { - struct VerifySuccessorContext *ctx; - ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task); - GNUNET_free(ctx); - send_verify_successor_retry_task = NULL; - } - - if (send_notify_new_successor_retry_task != NULL) - { - struct SendNotifyContext *notify_ctx; - notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task); - GNUNET_free (notify_ctx->successor_trail); - GNUNET_free (notify_ctx); - send_notify_new_successor_retry_task = NULL; - } } @@ -6287,4 +1469,4 @@ GDS_NEIGHBOURS_get_my_id (void) return my_identity; } -/* end of gnunet-service-xdht_neighbours.c */ +/* end of gnunet-service-wdht_neighbours.c */ diff --git a/src/include/gnunet_protocols.h b/src/include/gnunet_protocols.h index a7824edc0..0db2ba756 100644 --- a/src/include/gnunet_protocols.h +++ b/src/include/gnunet_protocols.h @@ -1,6 +1,6 @@ /* This file is part of GNUnet. - Copyright (C) 2001-2014 Christian Grothoff (and other contributing authors) + Copyright (C) 2001--2015 Christian Grothoff (and other contributing authors) GNUnet is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published @@ -2638,6 +2638,57 @@ extern "C" #endif + +/******************************************************************************* + * Whanau DHT messages + ******************************************************************************/ + +/** + * + */ +#define GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP 910 + +/** + * + */ +#define GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP_RESPONSE 911 + +/** + * + */ +#define GNUNET_MESSAGE_TYPE_WDHT_FINGER_DESTROY 912 + +/** + * + */ +#define GNUNET_MESSAGE_TYPE_WDHT_FINGER_ROUTE 913 + +/** + * + */ +#define GNUNET_MESSAGE_TYPE_WDHT_NEIGHBOUR_FIND 914 + +/** + * + */ +#define GNUNET_MESSAGE_TYPE_WDHT_NEIGHBOUR_FOUND 915 + +/** + * + */ +#define GNUNET_MESSAGE_TYPE_WDHT_GET 916 + +/** + * + */ +#define GNUNET_MESSAGE_TYPE_WDHT_PUT 917 + +/** + * + */ +#define GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT 918 + + /******************************************************************************* * RPS messages ******************************************************************************/ -- cgit v1.2.3