x-vine:fixes
[oweals/gnunet.git] / src / dht / gnunet-service-xdht_neighbours.c
1 /*
2      This file is part of GNUnet.
3      (C) 2009-2014 Christian Grothoff (and other contributing authors)
4
5      GNUnet is free software; you can redistribute it and/or modify
6      it under the terms of the GNU General Public License as published
7      by the Free Software Foundation; either version 3, or (at your
8      option) any later version.
9
10      GNUnet is distributed in the hope that it will be useful, but
11      WITHOUT ANY WARRANTY; without even the implied warranty of
12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13      General Public License for more details.
14
15      You should have received a copy of the GNU General Public License
16      along with GNUnet; see the file COPYING.  If not, write to the
17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18      Boston, MA 02111-1307, USA.
19 */
20
21 /**
22  * @file dht/gnunet-service-xdht_neighbours.c
23  * @brief GNUnet DHT service's finger and friend table management code
24  * @author Supriti Singh
25  */
26
27 #include "platform.h"
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_ats_service.h"
34 #include "gnunet_core_service.h"
35 #include "gnunet_datacache_lib.h"
36 #include "gnunet_transport_service.h"
37 #include "gnunet_dht_service.h"
38 #include "gnunet_statistics_service.h"
39 #include "gnunet-service-xdht.h"
40 #include "gnunet-service-xdht_clients.h"
41 #include "gnunet-service-xdht_datacache.h"
42 #include "gnunet-service-xdht_neighbours.h"
43 #include "gnunet-service-xdht_routing.h"
44 #include <fenv.h>
45 #include "dht.h"
46
47 /**
48  * TODO: 
49  * 1. In X-Vine paper, there is no policy defined for replicating the data to
50  * recover in case of peer failure. We can do it in Chord way. In R5N, the key
51  * is hashed and then data is stored according to the key value generated after
52  * hashing.
53  */
54
55
56 /**
57  * Maximum possible fingers (including predecessor) of a peer 
58  */
59 #define MAX_FINGERS 65
60
61 /**
62  * Maximum allowed number of pending messages per friend peer.
63  */
64 #define MAXIMUM_PENDING_PER_FRIEND 64
65
66 /**
67  * How long to wait before sending another find finger trail request
68  */
69 #define DHT_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 2)
70
71 /**
72  * How long to wait before sending another verify successor message. 
73  */
74 #define DHT_SEND_VERIFY_SUCCESSOR_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 1)
75
76 /**
77  * How long at most to wait for transmission of a request to a friend ?
78  */
79 #define GET_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
80
81 /**
82  * Duration for which I may remain congested. 
83  * Note: Its a static value. In future, a peer may do some analysis and calculate 
84  * congestion_timeout based on 'some' parameters. 
85  */
86 #define CONGESTION_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
87
88 /**
89  * Maximum number of trails allowed to go through a friend.
90  */
91 #define TRAILS_THROUGH_FRIEND_THRESHOLD 64
92
93 /**
94  * Maximum number of trails stored per finger.
95  */
96 #define MAXIMUM_TRAILS_PER_FINGER 1
97
98 /**
99  * Finger map index for predecessor entry in finger table.
100  */
101 #define PREDECESSOR_FINGER_ID 64
102
103 /**
104  * Wrap around in peer identity circle. 
105  */
106 #define PEER_IDENTITES_WRAP_AROUND pow(2, 64) - 1
107
108 /**
109  * FIXME: Its use only at 3 places check if you can remove it.
110  * To check if a finger is predecessor or not. 
111  */
112 enum GDS_NEIGHBOURS_finger_type
113 {
114   GDS_FINGER_TYPE_PREDECESSOR = 1,
115   GDS_FINGER_TYPE_NON_PREDECESSOR = 0
116 };
117
118 GNUNET_NETWORK_STRUCT_BEGIN
119
120 /**
121  * P2P PUT message
122  */
123 struct PeerPutMessage
124 {
125   /**
126    * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT
127    */
128   struct GNUNET_MessageHeader header;
129
130   /**
131    * Processing options
132    */
133   uint32_t options GNUNET_PACKED;
134
135   /**
136    * Content type.
137    */
138   uint32_t block_type GNUNET_PACKED;
139
140   /**
141    * Hop count
142    */
143   uint32_t hop_count GNUNET_PACKED;
144
145   /**
146    * Replication level for this message
147    * In the current implementation, this value is not used. 
148    */
149   uint32_t desired_replication_level GNUNET_PACKED;
150
151   /**
152    * Length of the PUT path that follows (if tracked).
153    */
154   uint32_t put_path_length GNUNET_PACKED;
155   
156   /** 
157    * Best known destination (could be my friend or finger) which should
158    * get this message next. 
159    */
160   struct GNUNET_PeerIdentity best_known_destination;
161   
162   /**
163    * In case best_known_destination is a finger, then trail to reach
164    * to that finger. Else its default value is 0. 
165    */
166   struct GNUNET_HashCode intermediate_trail_id;
167   
168   /**
169    * When does the content expire?
170    */
171   struct GNUNET_TIME_AbsoluteNBO expiration_time;
172   
173   /**
174    * The key to store the value under.
175    */
176   struct GNUNET_HashCode key GNUNET_PACKED;
177
178   /* put path (if tracked) */
179
180   /* Payload */
181  
182 };
183
184 /**
185  * P2P GET message
186  */
187 struct PeerGetMessage
188 {
189   /**
190    * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET
191    */
192   struct GNUNET_MessageHeader header;
193   
194   /**
195    * Processing options
196    */
197   uint32_t options GNUNET_PACKED;
198
199   /**
200    * Desired content type.
201    */
202   uint32_t block_type GNUNET_PACKED;
203   
204   /**
205    * Hop count
206    */
207   uint32_t hop_count GNUNET_PACKED;
208  
209   /**
210    * Desired replication level for this request.
211    * In the current implementation, this value is not used. 
212    */
213   uint32_t desired_replication_level GNUNET_PACKED;
214   
215   /**
216    * Total number of peers in get path. 
217    */
218   unsigned int get_path_length;
219   
220   /**
221    * Best known destination (could be my friend or finger) which should
222    * get this message next. 
223    */
224   struct GNUNET_PeerIdentity best_known_destination;
225   
226   /**
227    * In case best_known_destination is a finger, then trail to reach
228    * to that finger. Else its default value is 0. 
229    */
230   struct GNUNET_HashCode intermediate_trail_id;
231  
232   /**
233    * The key we are looking for.
234    */
235   struct GNUNET_HashCode key;
236   
237   /* Get path. */
238   /* struct GNUNET_PeerIdentity[]*/
239 };
240
241 /**
242  * P2P Result message
243  */
244 struct PeerGetResultMessage
245 {
246   /**
247    * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT
248    */
249   struct GNUNET_MessageHeader header;
250
251   /**
252    * The type for the data.
253    */
254   uint32_t type GNUNET_PACKED;
255   
256   /**
257    * Number of peers recorded in the outgoing path from source to the
258    * stored location of this message.
259    */
260   uint32_t put_path_length GNUNET_PACKED;
261   
262   /**
263    * Length of the GET path that follows (if tracked).
264    */
265   uint32_t get_path_length GNUNET_PACKED;
266   
267   /**
268    * Peer which queried for get and should get the result. 
269    */
270   struct GNUNET_PeerIdentity querying_peer;
271   
272   /**
273    * When does the content expire?
274    */
275   struct GNUNET_TIME_Absolute expiration_time;
276
277   /**
278    * The key of the corresponding GET request.
279    */
280   struct GNUNET_HashCode key;
281  
282   /* put path (if tracked) */
283
284   /* get path (if tracked) */
285
286   /* Payload */
287
288 };
289
290 /**
291  * P2P Trail setup message
292  */
293 struct PeerTrailSetupMessage
294 {
295   /**
296    * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP
297    */
298   struct GNUNET_MessageHeader header;
299   
300   /**
301    * Is source_peer trying to setup the trail to a predecessor or any finger.
302    */
303   uint32_t is_predecessor; 
304   
305   /**
306    * Peer closest to this value will be our finger.
307    */
308   uint64_t final_destination_finger_value;
309
310   /**
311    * Source peer which wants to setup the trail to one of its finger.
312    */
313   struct GNUNET_PeerIdentity source_peer;
314
315   /**
316    * Best known destination (could be my friend or finger) which should
317    * get this message next. 
318    */
319   struct GNUNET_PeerIdentity best_known_destination; 
320
321   /**
322    * In case best_known_destination is a finger, then trail id of trail to
323    * reach to this finger.
324    */
325   struct GNUNET_HashCode intermediate_trail_id;
326   
327   /**
328    * Trail id for trail which we are trying to setup.
329    */
330   struct GNUNET_HashCode trail_id; 
331
332   /* List of peers which are part of trail setup so far.
333    * Trail does NOT include source_peer and peer which will be closest to
334    * ultimate_destination_finger_value.
335    * struct GNUNET_PeerIdentity trail[]
336    */
337 };
338
339 /**
340   * P2P Trail Setup Result message
341  */
342 struct PeerTrailSetupResultMessage
343 {
344
345   /**
346    * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT
347    */
348   struct GNUNET_MessageHeader header;
349
350   /**
351    * Finger to which we have found the path.
352    */
353   struct GNUNET_PeerIdentity finger_identity;
354
355   /**
356    * Peer which started trail_setup to find trail to finger_identity
357    */
358   struct GNUNET_PeerIdentity querying_peer; 
359
360   /**
361    * Is the trail setup to querying_peer's predecessor or finger?
362    */
363   uint32_t is_predecessor; 
364
365   /**
366    * Value to which finger_identity is the closest peer. 
367    */
368   uint64_t ulitmate_destination_finger_value;
369   
370   /**
371    * Identifier of the trail from querying peer to finger_identity, NOT
372    * including both endpoints. 
373    */
374   struct GNUNET_HashCode trail_id;
375
376   /* List of peers which are part of the trail from querying peer to 
377    * finger_identity, NOT including both endpoints.
378    * struct GNUNET_PeerIdentity trail[] 
379    */
380 };
381
382 /**
383  * P2P Verify Successor Message.
384  */
385 struct PeerVerifySuccessorMessage
386 {
387   /**
388    * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR
389    */
390   struct GNUNET_MessageHeader header;
391
392   /**
393    * Peer which wants to verify its successor.
394    */
395   struct GNUNET_PeerIdentity source_peer;
396
397   /**
398    * Source Peer's current successor.
399    */
400   struct GNUNET_PeerIdentity successor;
401
402   /**
403    * Identifier of trail to reach from source_peer to successor.
404    */
405   struct GNUNET_HashCode trail_id;
406
407   /* List of the peers which are part of trail to reach  from source_peer 
408    * to successor, NOT including them
409    * struct GNUNET_PeerIdentity trail[] 
410    */
411 };
412
413 /**
414  * P2P Verify Successor Result Message
415  */
416 struct PeerVerifySuccessorResultMessage
417 {
418   /**
419    * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT
420    */
421   struct GNUNET_MessageHeader header;
422
423   /**
424    * Peer which sent the request to verify its successor.
425    */
426   struct GNUNET_PeerIdentity querying_peer;
427
428   /**
429    * Successor to which PeerVerifySuccessorMessage was sent.
430    */
431   struct GNUNET_PeerIdentity current_successor;
432
433   /**
434    * Current Predecessor of source_successor. It can be same as querying peer
435    * or different. In case it is different then it can be querying_peer's
436    * probable successor. 
437    */
438   struct GNUNET_PeerIdentity probable_successor;
439
440   /**
441    * Trail identifier of trail from querying_peer to current_successor.
442    */
443   struct GNUNET_HashCode trail_id;
444
445   /**
446    * Direction in which we are looking at the trail.
447    */
448   uint32_t trail_direction;
449
450   /* In case probable_successor != querying_peer, then trail to reach from
451    * querying_peer to probable_successor, NOT including end points.
452    * struct GNUNET_PeerIdentity trail[]
453    */
454 };
455
456 /**
457  * P2P Notify New Successor Message.
458  */
459 struct PeerNotifyNewSuccessorMessage
460 {
461   /**
462    * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR
463    */
464   struct GNUNET_MessageHeader header;
465
466   /**
467    * Peer which wants to notify its new successor.
468    */
469   struct GNUNET_PeerIdentity source_peer;
470
471   /**
472    * New successor of source_peer.
473    */
474   struct GNUNET_PeerIdentity new_successor;
475
476   /**
477    * Unique identifier of the trail from source_peer to new_successor,
478    * NOT including the endpoints.
479    */
480   struct GNUNET_HashCode trail_id;
481
482   /* List of peers in trail from source_peer to new_successor, 
483    * NOT including the endpoints. 
484    * struct GNUNET_PeerIdentity trail[]
485    */
486 };
487
488 /**
489  * P2P Trail Compression Message.
490  */
491 struct PeerTrailCompressionMessage
492 {
493   /**
494    * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION
495    */
496   struct GNUNET_MessageHeader header;
497
498   /**
499    * Source peer of this trail.
500    */
501   struct GNUNET_PeerIdentity source_peer;
502
503   /**
504    * Trail from source_peer to destination_peer compressed such that
505    * new_first_friend is the first hop in the trail from source to
506    * destination.
507    */
508   struct GNUNET_PeerIdentity new_first_friend;
509
510   /**
511    * Unique identifier of trail.
512    */
513   struct GNUNET_HashCode trail_id;
514 };
515
516
517 /**
518  * P2P Trail Tear Down message.
519  */
520 struct PeerTrailTearDownMessage
521 {
522   /**
523    * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN
524    */
525   struct GNUNET_MessageHeader header;
526
527   /**
528    * Unique identifier of the trail.
529    */
530   struct GNUNET_HashCode trail_id;
531
532   /**
533    * Direction of trail.
534    */
535   uint32_t trail_direction;
536 };
537
538
539 /**
540  * P2P Trail Rejection Message.
541  */
542 struct PeerTrailRejectionMessage
543 {
544   /**
545    * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION
546    */
547   struct GNUNET_MessageHeader header;
548
549   /**
550    * Peer which wants to set up the trail.
551    */
552   struct GNUNET_PeerIdentity source_peer;
553
554   /**
555    * Peer which sent trail rejection message as it it congested. 
556    */
557   struct GNUNET_PeerIdentity congested_peer;
558
559   /**
560    * Peer identity closest to this value will be finger of
561    * source_peer.
562    */
563   uint64_t ultimate_destination_finger_value;
564
565   /**
566    * Is source_peer trying to setup the trail to its predecessor or finger.
567    */
568   uint32_t is_predecessor;
569
570   /**
571    * Identifier for the trail that source peer is trying to setup.
572    */
573   struct GNUNET_HashCode trail_id;
574   
575   /**
576    * Relative time for which congested_peer will remain congested.
577    */
578   struct GNUNET_TIME_Relative congestion_time;
579
580   /* Trail_list from source_peer to peer which sent the message for trail setup
581    * to congested peer. This trail does NOT include source_peer.
582    struct GNUNET_PeerIdnetity trail[]*/
583 };
584
585 /**
586  * P2P Add Trail Message.
587  */
588 struct PeerAddTrailMessage
589 {
590   /**
591    * Type: #GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL
592    */
593   struct GNUNET_MessageHeader header;
594
595   /**
596    * Source of the routing trail.
597    */
598   struct GNUNET_PeerIdentity source_peer;
599
600   /**
601    * Destination of the routing trail.
602    */
603   struct GNUNET_PeerIdentity destination_peer;
604
605   /**
606    * Unique identifier of the trail from source_peer to destination_peer,
607    * NOT including the endpoints.
608    */
609   struct GNUNET_HashCode trail_id;
610
611   /* Trail from source peer to destination peer, NOT including them.
612    * struct GNUNET_PeerIdentity trail[]
613    */
614 };
615
616 GNUNET_NETWORK_STRUCT_END
617
618 /**
619  * Linked list of messages to send to a particular other peer.
620  */
621 struct P2PPendingMessage
622 {
623   /**
624    * Pointer to next item in the list
625    */
626   struct P2PPendingMessage *next;
627
628   /**
629    * Pointer to previous item in the list
630    */
631   struct P2PPendingMessage *prev;
632
633   /**
634    * Message importance level.  FIXME: used? useful?
635    */
636   unsigned int importance;
637
638   /**
639    * When does this message time out?
640    */
641   struct GNUNET_TIME_Absolute timeout;
642
643   /**
644    * Actual message to be sent, allocated at the end of the struct:
645    * // msg = (cast) &pm[1];
646    * // memcpy (&pm[1], data, len);
647    */
648   const struct GNUNET_MessageHeader *msg;
649
650 };
651
652 /**
653  *  Entry in friend_peermap.
654  */
655 struct FriendInfo
656 {
657   /**
658    * Friend Identity
659    */
660   struct GNUNET_PeerIdentity id;
661
662   /**
663    * Number of trails for which this friend is the first hop or if the friend
664    * is finger. 
665    */
666   unsigned int trails_count;
667
668   /**
669    * Count of outstanding messages for this friend.
670    */
671   unsigned int pending_count;
672
673   /**
674    * In case not 0, then amount of time for which this friend is congested.
675    */
676   struct GNUNET_TIME_Absolute congestion_timestamp;
677
678   /**
679    * Head of pending messages to be sent to this friend.
680    */
681   struct P2PPendingMessage *head;
682
683   /**
684    * Tail of pending messages to be sent to this friend.
685    */
686   struct P2PPendingMessage *tail;
687
688   /**
689    * Core handle for sending messages to this friend.
690    */
691   struct GNUNET_CORE_TransmitHandle *th;
692
693 };
694
695 /**
696  * An individual element of the trail to reach to a finger.
697  */
698 struct Trail_Element 
699 {
700   /**
701     * Pointer to next item in the list
702     */
703   struct Trail_Element *next;
704
705   /**
706     * Pointer to prev item in the list
707     */
708   struct Trail_Element *prev;
709
710   /**
711    * An element in this trail.
712    */
713   struct GNUNET_PeerIdentity peer;
714 };
715
716 /**
717  * FIXME: removed first_friend_trails_count, need to write a function
718  * to calculate each time we need it. Else, keep a pointer to first
719  * friend of in the trail. 
720  * Information about an individual trail. 
721  */
722 struct Trail 
723 {
724   /**
725    * Head of trail.
726    */
727   struct Trail_Element *trail_head;
728
729   /**
730    * Tail of trail.
731    */
732   struct Trail_Element *trail_tail;
733
734   /**
735    * Unique identifier of this trail.
736    */
737   struct GNUNET_HashCode trail_id;
738
739   /**
740    * Length of trail pointed
741    */
742   unsigned int trail_length;
743   
744   /**
745    * Is there a valid trail entry. 
746    */
747   unsigned int is_present;
748 };
749
750 /**
751  * An entry in finger_table
752  */
753 struct FingerInfo
754 {
755   /**
756    * Finger identity.
757    */
758   struct GNUNET_PeerIdentity finger_identity;
759
760   /**
761    * Is any finger stored at this finger index. 
762    */
763   unsigned int is_present;
764   
765   /**
766    * Index in finger peer map
767    */
768   uint32_t finger_table_index;
769
770   /**
771    * Number of trails setup so far for this finger.
772    * Should not cross MAXIMUM_TRAILS_PER_FINGER.
773    */
774   uint32_t trails_count;
775
776   /**
777    * Array of trails to reach to this finger.
778    */
779   struct Trail trail_list[MAXIMUM_TRAILS_PER_FINGER]; 
780 };
781
782
783 /**
784  * Stores information about the peer which is closest to destination_finger_value.
785  * 'closest' can be either successor or predecessor depending on is_predecessor
786  * flag.
787  */
788 struct Closest_Peer
789 {
790   /**
791    * Destination finger value. 
792    */
793   uint64_t destination_finger_value;
794   
795   /**
796    * Is finger_value a predecessor or any other finger. 
797    */
798   unsigned int is_predecessor;
799   
800   /**
801    * Trail id to reach to peer.
802    * In case peer is my identity or friend, it is set to 0.
803    */
804   struct GNUNET_HashCode trail_id;
805
806   /**
807    * Next destination. In case of friend and my_identity , it is same as next_hop
808    * In case of finger it is finger identity.
809    */
810   struct GNUNET_PeerIdentity best_known_destination;
811   
812   /**
813    * In case best_known_destination is a finger, then first friend in the trail
814    * to reach to it. In other case, same as best_known_destination.
815    */
816   struct GNUNET_PeerIdentity next_hop;
817 };
818
819
820 /**
821  * Data structure to store the trail chosen to reach to finger.
822  */
823 struct Selected_Finger_Trail
824 {
825   /**
826    * First friend in the trail to reach finger.
827    */
828   struct FriendInfo friend;
829
830   /**
831    * Identifier of this trail.
832    */
833   struct GNUNET_HashCode trail_id;
834
835   /**
836    * Total number of peers in this trail.
837    */
838   unsigned int trail_length;
839 };
840
841 /**
842  * Task that sends FIND FINGER TRAIL requests. This task is started when we have
843  * get our first friend.
844  */
845 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
846
847 /**
848  * Task that sends verify successor message. This task is started when we get 
849  * our successor for the first time. 
850  */
851 static GNUNET_SCHEDULER_TaskIdentifier send_verify_successor_task;
852
853 /**
854  * Identity of this peer.
855  */
856 static struct GNUNET_PeerIdentity my_identity;
857
858 /**
859  * Peer map of all the friends of a peer
860  */
861 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
862
863 /**
864  * Array of all the fingers. 
865  */
866 static struct FingerInfo finger_table [MAX_FINGERS];
867
868 /**
869  * Handle to CORE.
870  */
871 static struct GNUNET_CORE_Handle *core_api;
872
873 /**
874  * Handle for the statistics service.
875  */
876 extern struct GNUNET_STATISTICS_Handle *GDS_stats;
877
878 /**
879  * The current finger index that we have want to find trail to. We start the
880  * search with value = 0, i.e. successor  and then go to PREDCESSOR_FINGER_ID
881  * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
882  * we reset this index to 0.
883  */
884 static unsigned int current_search_finger_index;
885
886 /**
887  * Should we store our topology predecessor and successor IDs into statistics?
888  */
889 unsigned int track_topology;
890
891
892 /**
893  * Called when core is ready to send a message we asked for
894  * out to the destination.
895  *
896  * @param cls the 'struct FriendInfo' of the target friend
897  * @param size number of bytes available in buf
898  * @param buf where the callee should write the message
899  * @return number of bytes written to buf
900  */
901 static size_t
902 core_transmit_notify (void *cls, size_t size, void *buf)
903 {
904   struct FriendInfo *peer = cls;
905   char *cbuf = buf;
906   struct P2PPendingMessage *pending;
907   size_t off;
908   size_t msize;
909  
910   peer->th = NULL;
911   while ((NULL != (pending = peer->head)) &&
912          (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
913   {
914     peer->pending_count--;
915     GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
916     GNUNET_free (pending);
917   }
918   if (NULL == pending)
919   {
920     /* no messages pending */
921     return 0;
922   }
923   if (NULL == buf)
924   {
925     peer->th =
926         GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
927                                            GNUNET_CORE_PRIO_BEST_EFFORT,
928                                            GNUNET_TIME_absolute_get_remaining
929                                            (pending->timeout), &peer->id,
930                                            ntohs (pending->msg->size),
931                                            &core_transmit_notify, peer);
932     GNUNET_break (NULL != peer->th);
933     return 0;
934   }
935   off = 0;
936   while ((NULL != (pending = peer->head)) &&
937          (size - off >= (msize = ntohs (pending->msg->size))))
938   {
939     /*GNUNET_STATISTICS_update (GDS_stats,
940                               gettext_noop
941                               ("# Bytes transmitted to other peers"), msize,
942                               GNUNET_NO);*/
943     memcpy (&cbuf[off], pending->msg, msize);
944     off += msize;
945     peer->pending_count--;
946     GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
947     GNUNET_free (pending);
948   }
949   if (peer->head != NULL)
950   {
951     peer->th =
952         GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
953                                            GNUNET_CORE_PRIO_BEST_EFFORT,
954                                            GNUNET_TIME_absolute_get_remaining
955                                            (pending->timeout), &peer->id, msize,
956                                            &core_transmit_notify, peer);
957     GNUNET_break (NULL != peer->th);
958   }
959   return off;
960 }
961
962
963 /**
964  * Transmit all messages in the friend's message queue.
965  *
966  * @param peer message queue to process
967  */
968 static void
969 process_friend_queue (struct FriendInfo *peer)
970 {
971   struct P2PPendingMessage *pending;
972
973   if (NULL == (pending = peer->head))
974     return;
975   if (NULL != peer->th)
976     return;
977  
978   GNUNET_STATISTICS_update (GDS_stats,
979                             gettext_noop
980                             ("# Bytes of bandwidth requested from core"),
981                             ntohs (pending->msg->size), GNUNET_NO);
982
983   peer->th =
984       GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
985                                          pending->importance,
986                                          GNUNET_TIME_absolute_get_remaining
987                                          (pending->timeout), &peer->id,
988                                          ntohs (pending->msg->size),
989                                          &core_transmit_notify, peer);
990   GNUNET_break (NULL != peer->th);
991 }
992
993
994 /**
995  * Construct a trail setup message and forward it to target_friend
996  * @param source_peer Peer which wants to setup the trail
997  * @param ultimate_destination_finger_value Peer identity closest to this value 
998  *                                          will be finger to @a source_peer
999  * @param best_known_destination Best known destination (could be finger or friend)
1000  *                               which should get this message. In case it is 
1001  *                               friend, then it is same as target_friend
1002  * @param target_friend Friend to which message is forwarded now.
1003  * @param trail_length Total number of peers in trail setup so far.
1004  * @param trail_peer_list Trail setup so far
1005  * @param is_predecessor Is @a source_peer looking for trail to a predecessor or not.
1006  * @param trail_id Unique identifier for the trail we are trying to setup.
1007  * @param intermediate_trail_id Trail id of intermediate trail to reach to 
1008  *                              best_known_destination when its a finger. If not 
1009  *                              used then set to 0.
1010  */
1011 void
1012 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1013                                  uint64_t ultimate_destination_finger_value,
1014                                  struct GNUNET_PeerIdentity best_known_destination,
1015                                  struct FriendInfo *target_friend,
1016                                  unsigned int trail_length,
1017                                  const struct GNUNET_PeerIdentity *trail_peer_list,
1018                                  unsigned int is_predecessor,
1019                                  struct GNUNET_HashCode trail_id,
1020                                  struct GNUNET_HashCode intermediate_trail_id)
1021 {
1022   struct P2PPendingMessage *pending;
1023   struct PeerTrailSetupMessage *tsm;
1024   struct GNUNET_PeerIdentity *peer_list;
1025   size_t msize;
1026
1027   msize = sizeof (struct PeerTrailSetupMessage) +
1028           (trail_length * sizeof (struct GNUNET_PeerIdentity));
1029
1030   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1031   {
1032     GNUNET_break (0);
1033     return;
1034   }
1035
1036   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1037   {
1038     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1039                                 1, GNUNET_NO);
1040   }
1041  
1042   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1043   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1044   tsm = (struct PeerTrailSetupMessage *) &pending[1];
1045   pending->msg = &tsm->header;
1046   tsm->header.size = htons (msize);
1047   tsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP);
1048   tsm->final_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value);
1049   tsm->source_peer = source_peer;
1050   tsm->best_known_destination = best_known_destination;
1051   tsm->is_predecessor = htonl (is_predecessor);
1052   tsm->trail_id = trail_id;
1053   tsm->intermediate_trail_id = intermediate_trail_id;
1054
1055   if (trail_length > 0)
1056   {
1057     peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
1058     memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
1059   }
1060  
1061   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1062   target_friend->pending_count++;
1063   process_friend_queue (target_friend);
1064 }
1065
1066
1067 /**
1068  * Construct a trail setup result message and forward it to target friend.
1069  * @param querying_peer Peer which sent the trail setup request and should get
1070  *                      the result back. 
1071  * @param Finger Peer to which the trail has been setup to.
1072  * @param target_friend Friend to which this message should be forwarded.
1073  * @param trail_length Numbers of peers in the trail.
1074  * @param trail_peer_list Peers which are part of the trail from 
1075  *                        querying_peer to Finger, NOT including them. 
1076  * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1077  * @param ultimate_destination_finger_value Value to which @a finger is the closest
1078  *                                          peer. 
1079  * @param trail_id Unique identifier of the trail.
1080  */
1081 void
1082 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer,
1083                                         struct GNUNET_PeerIdentity finger,
1084                                         struct FriendInfo *target_friend,
1085                                         unsigned int trail_length,
1086                                         const struct GNUNET_PeerIdentity *trail_peer_list,
1087                                         unsigned int is_predecessor,
1088                                         uint64_t ultimate_destination_finger_value,
1089                                         struct GNUNET_HashCode trail_id)
1090 {
1091   struct P2PPendingMessage *pending;
1092   struct PeerTrailSetupResultMessage *tsrm;
1093   struct GNUNET_PeerIdentity *peer_list;
1094   size_t msize;
1095
1096   msize = sizeof (struct PeerTrailSetupResultMessage) +
1097           (trail_length * sizeof (struct GNUNET_PeerIdentity));
1098
1099   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1100   {
1101     GNUNET_break (0);
1102     return;
1103   }
1104
1105   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1106   {
1107     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1108                                 1, GNUNET_NO);
1109   }
1110
1111   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1112   pending->importance = 0;
1113   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1114   tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
1115   pending->msg = &tsrm->header;
1116   tsrm->header.size = htons (msize);
1117   tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT);
1118   tsrm->querying_peer = querying_peer;
1119   tsrm->finger_identity = finger;
1120   tsrm->is_predecessor = htonl (is_predecessor);
1121   tsrm->trail_id = trail_id;
1122   tsrm->ulitmate_destination_finger_value = 
1123           GNUNET_htonll (ultimate_destination_finger_value);
1124   peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1125
1126   if (trail_length > 0)
1127   {
1128     memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1129   }
1130   /* Send the message to chosen friend. */
1131   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1132   target_friend->pending_count++;
1133   process_friend_queue (target_friend);
1134 }
1135
1136
1137 /**
1138  * Send trail rejection message to target friend
1139  * @param source_peer Peer which is trying to setup the trail.
1140  * @param ultimate_destination_finger_value Peer closest to this value will be 
1141  *                                          @a source_peer's finger
1142  * @param congested_peer Peer which sent this message as it is congested.
1143  * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1144  * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1145  *                        by congested_peer. This does NOT include @a source_peer
1146  *                        and congested_peer.
1147  * @param trail_length Total number of peers in trail_peer_list, NOT including
1148  *                     @a source_peer and @a congested_peer
1149  * @param trail_id Unique identifier of this trail.
1150  * @param congestion_timeout Duration given by congested peer as an estimate of
1151  *                           how long it may remain congested.
1152  */
1153 void
1154 GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1155                                      uint64_t ultimate_destination_finger_value,
1156                                      struct GNUNET_PeerIdentity congested_peer,
1157                                      unsigned int is_predecessor,
1158                                      const struct GNUNET_PeerIdentity *trail_peer_list,
1159                                      unsigned int trail_length,
1160                                      struct GNUNET_HashCode trail_id,
1161                                      struct FriendInfo *target_friend,
1162                                      const struct GNUNET_TIME_Relative congestion_timeout)
1163 {
1164   struct PeerTrailRejectionMessage *trm;
1165   struct P2PPendingMessage *pending;
1166   struct GNUNET_PeerIdentity *peer_list;
1167   size_t msize;
1168   
1169   msize = sizeof (struct PeerTrailRejectionMessage) +
1170           (trail_length * sizeof (struct GNUNET_PeerIdentity));
1171
1172   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1173   {
1174     GNUNET_break (0);
1175     return;
1176   }
1177
1178   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1179   {
1180     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1181                                 1, GNUNET_NO);
1182   }
1183   
1184   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1185   pending->importance = 0;
1186   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1187   trm = (struct PeerTrailRejectionMessage *)&pending[1];
1188   pending->msg = &trm->header;
1189   trm->header.size = htons (msize);
1190   trm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION);
1191   trm->source_peer = source_peer;
1192   trm->congested_peer = congested_peer;
1193   trm->congestion_time = congestion_timeout;
1194   trm->is_predecessor = htonl (is_predecessor);
1195   trm->trail_id = trail_id;
1196   trm->ultimate_destination_finger_value = 
1197           GNUNET_htonll (ultimate_destination_finger_value);
1198
1199   peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1200   if (trail_length > 0)
1201   {
1202     memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1203   }
1204   
1205   /* Send the message to chosen friend. */
1206   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1207   target_friend->pending_count++;
1208   process_friend_queue (target_friend);
1209 }
1210
1211
1212 /**
1213  * Construct a verify successor message and forward it to target_friend.
1214  * @param source_peer Peer which wants to verify its successor.
1215  * @param successor Peer which is @a source_peer's current successor.
1216  * @param trail_id Unique Identifier of trail from @a source_peer to @a successor,
1217  *                 NOT including them. 
1218  * @param trail List of peers which are part of trail to reach from @a source_peer
1219  *              to @a successor, NOT including them. 
1220  * @param trail_length Total number of peers in @a trail.
1221  * @param target_friend Next friend to get this message. 
1222  */
1223 void
1224 GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
1225                                               struct GNUNET_PeerIdentity successor,
1226                                               struct GNUNET_HashCode trail_id,
1227                                               struct GNUNET_PeerIdentity *trail,
1228                                               unsigned int trail_length,
1229                                               struct FriendInfo *target_friend)
1230 {
1231   struct PeerVerifySuccessorMessage *vsm;
1232   struct P2PPendingMessage *pending;
1233   struct GNUNET_PeerIdentity *peer_list;
1234   size_t msize;
1235
1236   msize = sizeof (struct PeerVerifySuccessorMessage) +
1237          (trail_length * sizeof (struct GNUNET_PeerIdentity));;
1238   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1239   {
1240     GNUNET_break (0);
1241     return;
1242   }
1243
1244   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1245   {
1246     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1247                                 1, GNUNET_NO);
1248   }
1249   
1250   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1251   pending->importance = 0;    /* FIXME */
1252   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1253   vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
1254   pending->msg = &vsm->header;
1255   vsm->header.size = htons (msize);
1256   vsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR);
1257   vsm->source_peer = source_peer;
1258   vsm->successor = successor;
1259   vsm->trail_id = trail_id;
1260   
1261   if (trail_length != 0)
1262   {
1263     peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1264     memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1265   }
1266
1267   /* Send the message to chosen friend. */
1268   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1269   target_friend->pending_count++;
1270   process_friend_queue (target_friend);
1271 }
1272
1273
1274 /**
1275  * FIXME: In every function we pass target friend except for this one.
1276  * so, either change everything or this one. also, should se just store
1277  * the pointer to friend in routing table rather than gnunet_peeridentity.
1278  * if yes then we should keep friend info in.h  andmake lot of changes. 
1279  * Construct a trail teardown message and forward it to target friend. 
1280  * @param trail_id Unique identifier of the trail.
1281  * @param trail_direction Direction of trail.
1282  * @param target_friend Friend to get this message.
1283  */
1284 void
1285 GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_HashCode trail_id,
1286                                     unsigned int trail_direction,
1287                                     struct GNUNET_PeerIdentity peer)
1288 {
1289   struct PeerTrailTearDownMessage *ttdm;
1290   struct P2PPendingMessage *pending;
1291   struct FriendInfo *target_friend;
1292   size_t msize;
1293
1294   msize = sizeof (struct PeerTrailTearDownMessage);
1295
1296   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1297   {
1298     GNUNET_break (0);
1299     return;
1300   }
1301   
1302   /*FIXME:In what case friend can be null. ?*/
1303   if (NULL == (target_friend = 
1304                  GNUNET_CONTAINER_multipeermap_get (friend_peermap, &peer)));
1305   return;
1306   
1307   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1308   {
1309     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1310                                 1, GNUNET_NO);
1311   }
1312
1313   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1314   pending->importance = 0;    /* FIXME */
1315   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1316   ttdm = (struct PeerTrailTearDownMessage *) &pending[1];
1317   pending->msg = &ttdm->header;
1318   ttdm->header.size = htons (msize);
1319   ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN);
1320   ttdm->trail_id = trail_id;
1321   ttdm->trail_direction = htonl (trail_direction);
1322
1323   /* Send the message to chosen friend. */
1324   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1325   target_friend->pending_count++;
1326   process_friend_queue (target_friend);
1327 }
1328
1329
1330 /**
1331  * Construct a verify successor result message and send it to target_friend
1332  * @param querying_peer Peer which sent the verify successor message. 
1333  * @param source_successor Current_successor of @a querying_peer. 
1334  * @param current_predecessor Current predecessor of @a successor. Could be same
1335  *                            or different from @a querying_peer.
1336  * @param trail_id Unique identifier of the trail from @a querying_peer to 
1337  *                 @a successor, NOT including them.
1338  * @param trail List of peers which are part of trail from @a querying_peer to 
1339  *                 @a successor, NOT including them.
1340  * @param trail_length Total number of peers in @a trail
1341  * @param trail_direction Direction in which we are sending the message. In this
1342  *                        case we are sending result from @a successor to @a querying_peer.
1343  * @param target_friend Next friend to get this message. 
1344  */
1345 void
1346 GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity querying_peer,
1347                                              struct GNUNET_PeerIdentity current_successor,
1348                                              struct GNUNET_PeerIdentity probable_successor,
1349                                              struct GNUNET_HashCode trail_id,
1350                                              const struct GNUNET_PeerIdentity *trail,
1351                                              unsigned int trail_length,
1352                                              enum GDS_ROUTING_trail_direction trail_direction,
1353                                              struct FriendInfo *target_friend)
1354 {
1355   struct PeerVerifySuccessorResultMessage *vsmr;
1356   struct P2PPendingMessage *pending;
1357   struct GNUNET_PeerIdentity *peer_list;
1358   size_t msize;
1359
1360   msize = sizeof (struct PeerVerifySuccessorResultMessage) +
1361           (trail_length * sizeof(struct GNUNET_PeerIdentity));
1362
1363   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1364   {
1365     GNUNET_break (0);
1366     return;
1367   }
1368
1369   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1370   {
1371     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1372                                 1, GNUNET_NO);
1373   }
1374
1375   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1376   pending->importance = 0;    /* FIXME */
1377   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1378   vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
1379   pending->msg = &vsmr->header;
1380   vsmr->header.size = htons (msize);
1381   vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT);
1382   vsmr->querying_peer = querying_peer;
1383   vsmr->current_successor = current_successor;
1384   vsmr->probable_successor = probable_successor;
1385   vsmr->trail_direction = htonl (trail_direction);
1386   vsmr->trail_id = trail_id;
1387   
1388   if (trail_length > 0)
1389   {
1390     peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1391     memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1392   }
1393
1394    /* Send the message to chosen friend. */
1395   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1396   target_friend->pending_count++;
1397   process_friend_queue (target_friend);
1398 }
1399
1400
1401 /**
1402  * Construct a notify new successor message and send it to target_friend
1403  * @param source_peer Peer which wants to notify to its new successor that it
1404  *                    could be its predecessor. 
1405  * @param successor New successor of @a source_peer
1406  * @param successor_trail List of peers in Trail to reach from 
1407  *                            @a source_peer to @a new_successor, NOT including 
1408  *                            the endpoints. 
1409  * @param successor_trail_length Total number of peers in @a new_successor_trail.
1410  * @param successor_trail_id Unique identifier of @a new_successor_trail. 
1411  * @param target_friend Next friend to get this message. 
1412  */
1413 void
1414 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1415                                           struct GNUNET_PeerIdentity successor,
1416                                           const struct GNUNET_PeerIdentity *successor_trail,
1417                                           unsigned int successor_trail_length,
1418                                           struct GNUNET_HashCode succesor_trail_id,
1419                                           struct FriendInfo *target_friend)
1420 {
1421   struct PeerNotifyNewSuccessorMessage *nsm;
1422   struct P2PPendingMessage *pending;
1423   struct GNUNET_PeerIdentity *peer_list;
1424   size_t msize;
1425
1426   msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1427           (successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1428
1429   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1430   {
1431     GNUNET_break (0);
1432     return;
1433   }
1434
1435   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1436   {
1437     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1438                                 1, GNUNET_NO);
1439   }
1440
1441   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1442   pending->importance = 0;    /* FIXME */
1443   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1444   nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1445   pending->msg = &nsm->header;
1446   nsm->header.size = htons (msize);
1447   nsm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR);
1448   nsm->new_successor = successor;
1449   nsm->source_peer = source_peer;
1450   nsm->trail_id = succesor_trail_id;
1451   
1452   if (successor_trail_length > 0)
1453   {
1454     peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1455     memcpy (peer_list, successor_trail,
1456             successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1457   }
1458
1459    /* Send the message to chosen friend. */
1460   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1461   target_friend->pending_count++;
1462   process_friend_queue (target_friend);
1463 }
1464
1465
1466 /**
1467  * Construct an add_trail message and send it to target_friend
1468  * @param source_peer Source of the trail.
1469  * @param destination_peer Destination of the trail.
1470  * @param trail_id Unique identifier of the trail from 
1471  *                 @a source_peer to @a destination_peer, NOT including the endpoints.
1472  * @param trail List of peers in Trail from @a source_peer to @a destination_peer,
1473  *              NOT including the endpoints. 
1474  * @param trail_length Total number of peers in @a trail.
1475  * @param target_friend Next friend to get this message.
1476  */
1477 void
1478 GDS_NEIGHBOURS_send_add_trail (struct GNUNET_PeerIdentity source_peer,
1479                                struct GNUNET_PeerIdentity destination_peer,
1480                                struct GNUNET_HashCode trail_id,
1481                                const struct GNUNET_PeerIdentity *trail,
1482                                unsigned int trail_length,
1483                                struct FriendInfo *target_friend)
1484 {
1485   struct PeerAddTrailMessage *adm;
1486   struct GNUNET_PeerIdentity *peer_list;
1487   struct P2PPendingMessage *pending;
1488   size_t msize;
1489
1490   msize = sizeof (struct PeerAddTrailMessage) +
1491           (trail_length * sizeof(struct GNUNET_PeerIdentity));
1492
1493   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1494   {
1495     GNUNET_break (0);
1496     return;
1497   }
1498
1499   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1500   {
1501     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1502                                 1, GNUNET_NO);
1503   }
1504
1505   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1506   pending->importance = 0;    /* FIXME */
1507   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1508   adm = (struct PeerAddTrailMessage *) &pending[1];
1509   pending->msg = &adm->header;
1510   adm->header.size = htons (msize);
1511   adm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL);
1512   adm->source_peer = source_peer;
1513   adm->destination_peer = destination_peer;
1514   adm->trail_id = trail_id;
1515   
1516   if (trail_length > 0)
1517   {
1518     peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1519     memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1520   }
1521   /* Send the message to chosen friend. */
1522   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1523   target_friend->pending_count++;
1524   process_friend_queue (target_friend);
1525
1526 }
1527
1528
1529 /**
1530  * Construct a trail compression message and send it to target_friend.
1531  * @param source_peer Source of the trail.
1532  * @param trail_id Unique identifier of trail.
1533  * @param first_friend First hop in compressed trail to reach from source to finger
1534  * @param target_friend Next friend to get this message.
1535  */
1536 void
1537 GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1538                                        struct GNUNET_HashCode trail_id,
1539                                        struct GNUNET_PeerIdentity first_friend,
1540                                        struct FriendInfo *target_friend)
1541 {
1542   struct P2PPendingMessage *pending;
1543   struct PeerTrailCompressionMessage *tcm;
1544   size_t msize;
1545
1546   msize = sizeof (struct PeerTrailCompressionMessage);
1547
1548   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1549   {
1550     GNUNET_break (0);
1551     return;
1552   }
1553
1554   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1555   {
1556     GNUNET_STATISTICS_update (GDS_stats,
1557                               gettext_noop ("# P2P messages dropped due to full queue"),
1558                                                       1, GNUNET_NO);
1559   }
1560  
1561   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1562   pending->importance = 0;    /* FIXME */
1563   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1564   tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1565   pending->msg = &tcm->header;
1566   tcm->header.size = htons (msize);
1567   tcm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION);
1568   tcm->source_peer = source_peer;
1569   tcm->new_first_friend = first_friend;
1570   tcm->trail_id = trail_id;
1571
1572   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1573   target_friend->pending_count++;
1574   process_friend_queue (target_friend);
1575
1576 }
1577
1578
1579 /**
1580  * Search my location in trail. In case I am present more than once in the
1581  * trail (can happen during trail setup), then return my lowest index.
1582  * @param trail List of peers
1583  * @return my_index if found
1584  *         -1 if no entry found.
1585  */
1586 static int
1587 search_my_index (const struct GNUNET_PeerIdentity *trail,
1588                  int trail_length)
1589 {
1590   int i;
1591   int lowest_index = -1;
1592   
1593   for (i = 0; i < trail_length; i++)
1594   {
1595     if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1596       //lowest_index = i;
1597       return i;
1598   }
1599
1600   return lowest_index;
1601 }
1602
1603
1604 /**
1605  * Check if the friend is congested or have reached maximum number of trails
1606  * it can be part of of. 
1607  * @param friend Friend to be checked.
1608  * @return #GNUNET_NO if friend is not congested or have not crossed threshold.
1609  *         #GNUNET_YES if friend is either congested or have crossed threshold 
1610  */
1611 static int
1612 is_friend_congested (struct FriendInfo *friend)
1613 {
1614   if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) && 
1615       ((0 == GNUNET_TIME_absolute_get_remaining
1616              (friend->congestion_timestamp).rel_value_us)))
1617     return GNUNET_NO;
1618   else
1619     return GNUNET_YES;
1620 }
1621
1622
1623 /**
1624  * FIXME; not handling the wrap around logic correctly. 
1625  * Select closest finger to value.
1626  * @param peer1 First peer
1627  * @param peer2 Second peer
1628  * @param value Value to be compare
1629  * @return Closest peer
1630  */
1631 static struct GNUNET_PeerIdentity *
1632 select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1633                        struct GNUNET_PeerIdentity *peer2,
1634                        uint64_t value)
1635 {
1636   uint64_t peer1_value;
1637   uint64_t peer2_value;
1638   
1639   memcpy (&peer1_value, peer1, sizeof (uint64_t));
1640   memcpy (&peer2_value, peer2, sizeof (uint64_t));
1641   peer1_value = GNUNET_ntohll (peer1_value);
1642   peer2_value = GNUNET_ntohll (peer2_value);
1643   
1644   if (peer1_value == value)
1645   {
1646     return peer1;
1647   }
1648   
1649   if (peer2_value == value)
1650   {
1651     return peer2;
1652   }
1653    
1654   if (peer2_value < peer1_value)
1655   {
1656     if ((peer2_value < value) && (value < peer1_value))
1657     {
1658       return peer1;
1659     }
1660     else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1661              ((0 < value) && (value < peer2_value)))
1662     {
1663       return peer2;
1664     }
1665   }  
1666    
1667   if (peer1_value < peer2_value)
1668   {
1669     if ((peer1_value < value) && (value < peer2_value))
1670     {
1671       return peer2;
1672     }
1673     else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1674              ((0 < value) && (value < peer1_value)))
1675     {
1676       return peer1;
1677     }
1678   }
1679   return NULL;
1680 }
1681
1682
1683 /**
1684  * Select closest predecessor to value.
1685  * @param peer1 First peer
1686  * @param peer2 Second peer
1687  * @param value Value to be compare
1688  * @return Peer which precedes value in the network.
1689  */
1690 static struct GNUNET_PeerIdentity *
1691 select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1692                             struct GNUNET_PeerIdentity *peer2,
1693                             uint64_t value)
1694 {
1695   uint64_t peer1_value;
1696   uint64_t peer2_value;
1697   
1698   memcpy (&peer1_value, peer1, sizeof (uint64_t));
1699   memcpy (&peer2_value, peer2, sizeof (uint64_t));
1700   peer1_value = GNUNET_ntohll (peer1_value);
1701   peer2_value = GNUNET_ntohll (peer2_value);
1702   
1703   if (peer1_value == value)
1704     return peer1;
1705   
1706   if (peer2_value == value)
1707     return peer2;
1708   
1709   if (peer1_value < peer2_value)
1710   {
1711     if ((peer1_value < value) && (value < peer2_value))
1712     {
1713       return peer1;
1714     }
1715     else if (((peer2_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1716              ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer1_value)))
1717     {
1718       return peer2;
1719     }
1720   }
1721   
1722   if (peer2_value < peer1_value)
1723   {
1724     if ((peer2_value < value) && (value < peer1_value))
1725     {
1726       return peer2;
1727     }
1728     else if (((peer1_value < value) && (value < PEER_IDENTITES_WRAP_AROUND)) ||
1729              ((PEER_IDENTITES_WRAP_AROUND > value) && (value < peer2_value)))
1730     {
1731       return peer1;
1732     }
1733   }
1734   return NULL;
1735 }
1736
1737 #if 0
1738 /**
1739  * This is a test function to print all the entries of friend table.
1740  */
1741 static void
1742 test_friend_peermap_print ()
1743 {
1744   struct FriendInfo *friend;
1745   struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1746   struct GNUNET_PeerIdentity print_peer;
1747   struct GNUNET_PeerIdentity key_ret;
1748   int i;
1749   
1750   print_peer = my_identity;
1751   FPRINTF (stderr,_("\nSUPU************  FRIEND_PEERMAP of %s"),GNUNET_i2s(&print_peer));
1752   friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1753   
1754   for (i = 0; i < GNUNET_CONTAINER_multipeermap_size (friend_peermap); i++)
1755   {
1756     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (friend_iter,
1757                                                                   &key_ret,
1758                                                                   (const void **)&friend))
1759     {
1760       memcpy (&print_peer, &key_ret, sizeof (struct GNUNET_PeerIdentity));
1761       FPRINTF (stderr,_("\nSUPU %s, %s, %d, friend = %s, friend->trails_count = %d"),
1762               __FILE__, __func__,__LINE__, GNUNET_i2s(&print_peer), friend->trails_count);
1763     }
1764   }
1765 }
1766
1767 /**
1768  * This is a test function, to print all the entries of finger table.
1769  */
1770 static void
1771 test_finger_table_print()
1772 {
1773   struct FingerInfo *finger;
1774   struct GNUNET_PeerIdentity print_peer;
1775   //struct Trail *trail;
1776   int i;
1777   //int j;
1778   //int k;
1779   print_peer = my_identity;
1780   FPRINTF (stderr,_("\nSUPU************  FINGER_TABLE of %s"),GNUNET_i2s(&print_peer));
1781   for (i = 0; i < MAX_FINGERS; i++)
1782   {
1783     finger = &finger_table[i];
1784     
1785     if (GNUNET_NO == finger->is_present)
1786       continue;
1787     
1788     print_peer = finger->finger_identity;
1789     FPRINTF (stderr,_("\nSUPU %s, %s, %d, finger_table[%d] = %s, trails_count = %d"),
1790             __FILE__, __func__,__LINE__,i,GNUNET_i2s (&print_peer), finger->trails_count);
1791     
1792 #if 0
1793     for (j = 0; j < finger->trails_count; j++)
1794     {
1795       trail = &finger->trail_list[j];
1796       FPRINTF (stderr,_("\nSUPU %s, %s, %d, trail_id[%d]=%s"),__FILE__, __func__,__LINE__,j, GNUNET_h2s(&trail->trail_id));
1797       struct Trail_Element *element;
1798       element = trail->trail_head;
1799       for (k = 0; k < trail->trail_length; k++)
1800       {  
1801         print_peer = element->peer;
1802         FPRINTF (stderr,_("\nSUPU %s, %s, %d,trail[%d] = %s "),__FILE__, __func__,__LINE__,k, GNUNET_i2s(&print_peer));
1803         element = element->next;
1804       }
1805     }
1806     #endif
1807   }
1808 }
1809 #endif
1810
1811 /**
1812  * Select the closest peer among two peers (which should not be same)
1813  * with respect to value and finger_table_index
1814  * NOTE: peer1 != peer2
1815  * @param peer1 First peer
1816  * @param peer2 Second peer
1817  * @param value Value relative to which we find the closest
1818  * @param is_predecessor Is value a predecessor or any other finger. 
1819  * @return Closest peer among two peers.
1820  */
1821 static struct GNUNET_PeerIdentity *
1822 select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1823                      struct GNUNET_PeerIdentity *peer2,
1824                      uint64_t value,
1825                      unsigned int is_predecessor)
1826 {
1827   struct GNUNET_PeerIdentity *closest_peer;
1828   
1829   if (1 == is_predecessor)
1830   {
1831     closest_peer = select_closest_predecessor (peer1, peer2, value);
1832     
1833   }
1834   else
1835   {
1836     closest_peer = select_closest_finger (peer1, peer2, value);
1837   }
1838   return closest_peer;
1839 }
1840
1841
1842 /**
1843  * Iterate over the list of all the trails of a finger. In case the first
1844  * friend to reach the finger has reached trail threshold or is congested,
1845  * then don't select it. In case there multiple available good trails to reach
1846  * to Finger, choose the one with shortest trail length.
1847  * Note: We use length as parameter. But we can use any other suitable parameter
1848  * also. 
1849  * @param finger Finger
1850  * @return struct Selected_Finger_Trail which contains the first friend , trail id
1851  * and trail length. NULL in case none of the trails are free.
1852  */
1853 static struct Selected_Finger_Trail *
1854 select_finger_trail (struct FingerInfo *finger)
1855 {
1856   struct FriendInfo *friend;
1857   struct Trail *iterator;
1858   struct Selected_Finger_Trail *finger_trail;
1859   unsigned int i;
1860   unsigned int flag = 0;
1861   unsigned int j = 0;
1862  
1863   finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1864   GNUNET_assert (finger->trails_count > 0);
1865   
1866   for (i = 0; i < finger->trails_count; i++)
1867   {
1868     iterator = &finger->trail_list[i];
1869     
1870     /* No trail stored at this index. */
1871     if (GNUNET_NO == iterator->is_present)
1872       continue;
1873
1874     GNUNET_assert (NULL != 
1875                   (friend = 
1876                    GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1877                                                       &iterator->trail_head->peer)));
1878     
1879     /* First friend to reach trail is not free. */
1880     if (GNUNET_YES == is_friend_congested (friend))
1881     {
1882       j++;
1883       continue;
1884     }
1885     
1886     if (!flag)
1887     {
1888       flag = 1;
1889       finger_trail->trail_length = iterator->trail_length;
1890       finger_trail->friend = *friend;
1891       finger_trail->trail_id = iterator->trail_id;   
1892     }
1893     else if (finger_trail->trail_length > iterator->trail_length)
1894     {
1895       finger_trail->friend = *friend;
1896       finger_trail->trail_id = iterator->trail_id;
1897       finger_trail->trail_length = iterator->trail_length;
1898     }
1899   }
1900
1901   /* All the first friend in all the trails to reach to finger are either 
1902    congested or have crossed trail threshold. */
1903   if (j == finger->trails_count)
1904     return NULL;
1905   
1906   return finger_trail;
1907 }
1908
1909
1910 /**
1911  * Compare FINGER entry with current successor. If finger's first friend of all
1912  * its trail is not congested and  has not crossed trail threshold, then check 
1913  * if finger peer identity is closer to final_destination_finger_value than
1914  * current_successor. If yes then update current_successor. 
1915  * @param current_successor[in/out]
1916  * @return 
1917  */
1918 static void
1919 compare_finger_and_current_successor (struct Closest_Peer *current_closest_peer)
1920 {
1921   struct FingerInfo *finger;
1922   struct GNUNET_PeerIdentity *closest_peer;
1923   struct Selected_Finger_Trail *finger_trail;
1924   int i;
1925   
1926   /* Iterate over finger table. */
1927   for (i = 0; i < MAX_FINGERS; i++)
1928   {
1929     finger = &finger_table[i];
1930     
1931     if (GNUNET_NO == finger->is_present)
1932       continue;
1933
1934     /* If my identity is same as current closest peer then don't consider me*/
1935     if (0 == 
1936             GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1937                                              &current_closest_peer->best_known_destination))
1938       continue;
1939     
1940     /* If I am my own finger, then ignore this finger. */
1941     if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1942                                               &my_identity))
1943       continue;
1944     
1945     /* If finger is a friend, then do nothing. As we have already checked
1946      * for each friend in compare_friend_and_current_successor(). */
1947     if (NULL != (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1948                                                     &finger->finger_identity)))
1949     {
1950       continue;
1951     }
1952     
1953     /* Choose one of the trail to reach to finger. */
1954     finger_trail = select_finger_trail (finger);
1955     
1956     /* In case no trail found, ignore this finger. */
1957     if (NULL == finger_trail)
1958       continue;
1959
1960     closest_peer = select_closest_peer (&finger->finger_identity, 
1961                                         &current_closest_peer->best_known_destination,
1962                                         current_closest_peer->destination_finger_value,
1963                                         current_closest_peer->is_predecessor);
1964     
1965     if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
1966                                               closest_peer))
1967     {
1968       current_closest_peer->best_known_destination = finger->finger_identity;
1969       current_closest_peer->next_hop = finger_trail->friend.id;
1970       current_closest_peer->trail_id = finger_trail->trail_id;
1971       //GNUNET_free(finger_trail);//FIXME: where should we free the finger trail.
1972     }
1973     continue;
1974   }
1975 }
1976
1977
1978 /**
1979  * Compare friend entry with current successor.
1980  * If friend identity and current_successor is same, then do nothing. 
1981  * If friend is not congested and has not crossed trail threshold, then check 
1982  * if friend peer identity is closer to final_destination_finger_value than 
1983  * current_successor. If yes then update current_successor. 
1984  * @param cls closure
1985  * @param key current public key
1986  * @param value struct Closest_Peer
1987  * @return #GNUNET_YES if we should continue to iterate,
1988  *         #GNUNET_NO if not.
1989  */
1990 static int
1991 compare_friend_and_current_closest_peer (void *cls,
1992                                          const struct GNUNET_PeerIdentity *key,
1993                                          void *value)
1994 {
1995   struct FriendInfo *friend = value;
1996   struct Closest_Peer *current_closest_peer = cls;
1997   struct GNUNET_PeerIdentity *closest_peer;
1998   
1999   /* Friend is either congested or has crossed threshold. */
2000   if (GNUNET_YES == is_friend_congested (friend))
2001     return GNUNET_YES;
2002  
2003   /* If current_closest_peer and friend identity are same, then do nothing.*/
2004   if (0 == 
2005         GNUNET_CRYPTO_cmp_peer_identity (&friend->id,
2006                                          &current_closest_peer->best_known_destination))
2007     return GNUNET_YES;
2008
2009   closest_peer = select_closest_peer (&friend->id, 
2010                                       &current_closest_peer->best_known_destination,
2011                                       current_closest_peer->destination_finger_value,
2012                                       current_closest_peer->is_predecessor);
2013
2014   /* Is friend the closest successor? */
2015   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&friend->id, closest_peer))
2016   {
2017     current_closest_peer->best_known_destination = friend->id;
2018     current_closest_peer->next_hop = friend->id;
2019   }
2020   
2021   return GNUNET_YES;
2022 }
2023
2024
2025 /**
2026  * Initialize current_successor to my_identity.
2027  * @param my_identity My peer identity
2028  * @return Updated closest_peer
2029  */
2030 static struct Closest_Peer 
2031 init_current_successor (struct GNUNET_PeerIdentity my_identity,
2032                         uint64_t destination_finger_value,
2033                         unsigned int is_predecessor)
2034 {
2035   struct Closest_Peer current_closest_peer;
2036   
2037   memset (&current_closest_peer.trail_id, 0, sizeof(struct GNUNET_HashCode));
2038   current_closest_peer.destination_finger_value = destination_finger_value;
2039   current_closest_peer.is_predecessor = is_predecessor;
2040   current_closest_peer.next_hop = my_identity;
2041   current_closest_peer.best_known_destination = my_identity;
2042   
2043   return current_closest_peer;
2044 }
2045
2046
2047 /**
2048  * FIXME: at the moment, there is not 100% get and put in case of non-malicious
2049  * peer. It could be because of the logic we wrote here. Verify if its correct.
2050  * If not then return immediate_successor. 
2051  * 
2052  * Find the successor for destination_finger_value among my_identity, my
2053  * friends and my fingers. Don't consider friends or fingers which are either
2054  * congested or have crossed the threshold.
2055  * NOTE: In case a friend is also a finger, then it is always chosen as friend
2056  * not a finger. 
2057  * @param destination_finger_value Peer closest to this value will be the next successor.
2058  * @param is_predecessor Are we looking for predecessor or finger?
2059  * @return Successor It is never NULL, in case none of friend or finger is closest,
2060  *                   then we return my_identity.
2061  */
2062 static struct Closest_Peer
2063 find_successor (uint64_t destination_finger_value,
2064                 unsigned int is_predecessor)
2065 {
2066   struct Closest_Peer current_closest_peer;
2067   
2068    /* Initialize current_successor to my_identity. */
2069   current_closest_peer = init_current_successor (my_identity,
2070                                                  destination_finger_value,
2071                                                  is_predecessor);
2072  
2073   /* Compare each friend entry with current_successor and update current_successor
2074    * with friend if its closest. */
2075   GNUNET_assert 
2076           (GNUNET_SYSERR != 
2077            GNUNET_CONTAINER_multipeermap_iterate (friend_peermap, 
2078                                                   &compare_friend_and_current_closest_peer,
2079                                                   &current_closest_peer));
2080    
2081   /* Compare each finger entry with current_successor and update current_successor
2082    * with finger if its closest. */
2083   compare_finger_and_current_successor (&current_closest_peer);
2084  
2085   return current_closest_peer;
2086 }
2087
2088
2089 /**
2090  * Construct a Put message and send it to target_peer.
2091  * @param key Key for the content
2092  * @param block_type Type of the block
2093  * @param options Routing options
2094  * @param desired_replication_level Desired replication count
2095  * @param best_known_dest Peer to which this message should reach eventually,
2096  *                        as it is best known destination to me. 
2097  * @param intermediate_trail_id Trail id in case 
2098  * @param target_peer Peer to which this message will be forwarded.
2099  * @param hop_count Number of hops traversed so far.
2100  * @param put_path_length Total number of peers in @a put_path
2101  * @param put_path Number of peers traversed so far
2102  * @param expiration_time When does the content expire
2103  * @param data Content to store
2104  * @param data_size Size of content @a data in bytes
2105  */
2106 void
2107 GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
2108                          enum GNUNET_BLOCK_Type block_type,
2109                                            enum GNUNET_DHT_RouteOption options,
2110                                            uint32_t desired_replication_level,
2111                                            struct GNUNET_PeerIdentity best_known_dest,
2112                                            struct GNUNET_HashCode intermediate_trail_id,
2113                                            struct GNUNET_PeerIdentity *target_peer,
2114                          uint32_t hop_count,
2115                          uint32_t put_path_length,
2116                          struct GNUNET_PeerIdentity *put_path,
2117                          struct GNUNET_TIME_Absolute expiration_time,
2118                          const void *data, size_t data_size)
2119 {
2120   struct PeerPutMessage *ppm;
2121   struct P2PPendingMessage *pending;
2122   struct FriendInfo *target_friend;
2123   struct GNUNET_PeerIdentity *pp;
2124   struct GNUNET_PeerIdentity next_hop;
2125
2126   size_t msize;
2127   
2128   msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2129           sizeof (struct PeerPutMessage);
2130   
2131   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2132   {
2133     put_path_length = 0;
2134     msize = data_size + sizeof (struct PeerPutMessage);
2135   }
2136
2137   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2138   {
2139     GNUNET_break (0);
2140     return;
2141   }
2142  
2143   /* This is the first call made from clients file. So, we should search for the
2144      target_friend. */
2145   if (NULL == target_peer)
2146   {
2147     uint64_t key_value;
2148     struct Closest_Peer successor;
2149
2150     memcpy (&key_value, key, sizeof (uint64_t));  
2151     key_value = GNUNET_ntohll (key_value);
2152     
2153     successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2154     best_known_dest = successor.best_known_destination;
2155     next_hop = successor.next_hop;
2156     intermediate_trail_id = successor.trail_id;
2157
2158     if (0 == GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)) 
2159     {
2160       /* I am the destination but we have already done datacache_put in client file.  */
2161       return;
2162     }
2163     else
2164       GNUNET_assert (NULL != 
2165                     (target_friend = 
2166                      GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));  
2167   }
2168   else
2169   {
2170     GNUNET_assert (NULL !=
2171                    (target_friend = 
2172                    GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); 
2173   }
2174   
2175   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2176   pending->timeout = expiration_time;
2177   ppm = (struct PeerPutMessage *) &pending[1];
2178   pending->msg = &ppm->header;
2179   ppm->header.size = htons (msize);
2180   ppm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT);
2181   ppm->options = htonl (options);
2182   ppm->block_type = htonl (block_type);
2183   ppm->hop_count = htonl (hop_count + 1);
2184   ppm->desired_replication_level = htonl (desired_replication_level);
2185   ppm->put_path_length = htonl (put_path_length);
2186   ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2187   ppm->best_known_destination = best_known_dest;
2188   ppm->key = *key;
2189   
2190   pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2191   if (put_path_length != 0)
2192   {
2193     memcpy (pp, put_path,
2194             sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2195   }
2196   memcpy (&pp[put_path_length], data, data_size);
2197   
2198   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2199   target_friend->pending_count++;
2200   process_friend_queue (target_friend);
2201 }
2202
2203
2204 /**
2205  * Construct a Get message and send it to target_peer.
2206  * @param key Key for the content
2207  * @param block_type Type of the block
2208  * @param options Routing options
2209  * @param desired_replication_level Desired replication count
2210  * @param best_known_dest Peer which should get this message. Same as target peer
2211  *                        if best_known_dest is a friend else its a finger.
2212  * @param intermediate_trail_id  Trail id to reach to @a best_known_dest
2213  *                              in case it is a finger else set to 0.
2214  * @param target_peer Peer to which this message will be forwarded.
2215  * @param hop_count Number of hops traversed so far.
2216  * @param data Content to store
2217  * @param data_size Size of content @a data in bytes
2218  * @param get_path_length Total number of peers in @a get_path
2219  * @param get_path Number of peers traversed so far
2220  */
2221 void
2222 GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
2223                          enum GNUNET_BLOCK_Type block_type,
2224                          enum GNUNET_DHT_RouteOption options,
2225                          uint32_t desired_replication_level,
2226                          struct GNUNET_PeerIdentity best_known_dest,
2227                          struct GNUNET_HashCode intermediate_trail_id,
2228                          struct GNUNET_PeerIdentity *target_peer,
2229                          uint32_t hop_count,
2230                          uint32_t get_path_length,
2231                          struct GNUNET_PeerIdentity *get_path)
2232 {
2233   struct PeerGetMessage *pgm;
2234   struct P2PPendingMessage *pending;
2235   struct FriendInfo *target_friend;
2236   struct GNUNET_PeerIdentity *gp;
2237   size_t msize;
2238   
2239   msize = sizeof (struct PeerGetMessage) + 
2240           (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2241   
2242   /* In this case we don't make get_path_length = 0, as we need get path to
2243    * return the message back to querying client. */
2244   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2245   {
2246     GNUNET_break (0);
2247     return;
2248   }
2249  
2250   /* This is the first time we got request from our own client file. */
2251   if (NULL == target_peer)
2252   {
2253     uint64_t key_value;
2254     struct Closest_Peer successor;
2255     
2256     memcpy (&key_value, key, sizeof (uint64_t)); 
2257     key_value = GNUNET_ntohll (key_value);
2258     successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
2259     
2260     best_known_dest = successor.best_known_destination;
2261     intermediate_trail_id = successor.trail_id;
2262     
2263     /* I am the destination. I have the data. */
2264     if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2265                                               &best_known_dest)) 
2266     {
2267       GDS_DATACACHE_handle_get (key,block_type, NULL, 0, 
2268                                 NULL, 0, 1, &my_identity, NULL,&my_identity);
2269       
2270       return;
2271     }
2272     else
2273     {
2274       GNUNET_assert (NULL != 
2275                     (target_friend = 
2276                      GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
2277                                                         &successor.next_hop)));
2278     }
2279     
2280   }
2281   else
2282   {
2283     GNUNET_assert (NULL != 
2284                   (target_friend = 
2285                    GNUNET_CONTAINER_multipeermap_get (friend_peermap, target_peer))); //FIXME: assertion fails.
2286   }
2287   
2288   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2289   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2290   pending->importance = 0;    /* FIXME */
2291   pgm = (struct PeerGetMessage *) &pending[1];
2292   pending->msg = &pgm->header;
2293   pgm->header.size = htons (msize);
2294   pgm->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET);
2295   pgm->get_path_length = htonl (get_path_length);
2296   pgm->best_known_destination = best_known_dest;
2297   pgm->key = *key;
2298   pgm->intermediate_trail_id = intermediate_trail_id;
2299   pgm->hop_count = htonl (hop_count + 1);
2300   gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2301   
2302   if (get_path_length != 0)
2303   {
2304     memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2305   }
2306   
2307   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2308   target_friend->pending_count++;
2309   process_friend_queue (target_friend);
2310 }
2311
2312
2313 /**
2314  * Send the get result to requesting client.
2315  * @param key Key of the requested data.
2316  * @param type Block type
2317  * @param target_peer Next peer to forward the message to.
2318  * @param source_peer Peer which has the data for the key.
2319  * @param put_path_length Number of peers in @a put_path
2320  * @param put_path Path taken to put the data at its stored location.
2321  * @param get_path_length Number of peers in @a get_path
2322  * @param get_path Path taken to reach to the location of the key.
2323  * @param expiration When will this result expire?
2324  * @param data Payload to store
2325  * @param data_size Size of the @a data
2326  */
2327 void
2328 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
2329                                 enum GNUNET_BLOCK_Type type,
2330                                 const struct GNUNET_PeerIdentity *target_peer,
2331                                 const struct GNUNET_PeerIdentity *source_peer,
2332                                 unsigned int put_path_length,
2333                                 const struct GNUNET_PeerIdentity *put_path,
2334                                 unsigned int get_path_length,
2335                                 const struct GNUNET_PeerIdentity *get_path,
2336                                 struct GNUNET_TIME_Absolute expiration,
2337                                 const void *data, size_t data_size)
2338 {
2339   struct PeerGetResultMessage *get_result;
2340   struct GNUNET_PeerIdentity *paths;
2341   struct P2PPendingMessage *pending;
2342   struct FriendInfo *target_friend;
2343   int current_path_index;
2344   size_t msize;
2345
2346   msize = (put_path_length + get_path_length )* sizeof (struct GNUNET_PeerIdentity) + 
2347           data_size +
2348           sizeof (struct PeerGetResultMessage);
2349
2350   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2351   {
2352     GNUNET_break (0);
2353     return;
2354   }
2355   
2356   current_path_index = 0;
2357   if(get_path_length > 0)
2358   {
2359     current_path_index = search_my_index(get_path, get_path_length);
2360     if (-1 == current_path_index)
2361     {
2362       GNUNET_break (0);
2363       return;
2364     }
2365   }
2366   if (0 == current_path_index)
2367   {
2368     GDS_CLIENTS_handle_reply (expiration, key, get_path_length, 
2369                               get_path, put_path_length,
2370                               put_path, type, data_size, data);
2371     return;
2372   }
2373
2374   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2375   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2376   pending->importance = 0;   
2377   get_result = (struct PeerGetResultMessage *)&pending[1];
2378   pending->msg = &get_result->header;
2379   get_result->header.size = htons (msize);
2380   get_result->header.type = htons (GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT);
2381   get_result->key = *key;
2382   get_result->querying_peer = *source_peer;
2383   get_result->expiration_time = expiration;
2384   get_result->get_path_length = htonl (get_path_length);
2385   get_result->put_path_length = htonl (put_path_length);
2386   paths = (struct GNUNET_PeerIdentity *)&get_result[1];
2387   memcpy (paths, put_path,
2388           put_path_length * sizeof (struct GNUNET_PeerIdentity));
2389   memcpy (&paths[put_path_length], get_path,
2390           get_path_length * sizeof (struct GNUNET_PeerIdentity));
2391   memcpy (&paths[put_path_length + get_path_length], data, data_size);
2392   
2393   GNUNET_assert (NULL != 
2394                 (target_friend = 
2395                  GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
2396                                                     &get_path[current_path_index - 1])));
2397   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2398   target_friend->pending_count++;
2399   process_friend_queue (target_friend);
2400 }
2401
2402
2403 /**
2404  * Randomly choose one of your friends (which is not congested and have not crossed
2405  * trail threshold) from the friend_peermap
2406  * @return Friend Randomly chosen friend.
2407  *         NULL in case friend peermap is empty, or all the friends are either
2408  *              congested or have crossed trail threshold.
2409  */
2410 static struct FriendInfo *
2411 select_random_friend ()
2412 {
2413   unsigned int current_size;
2414   uint32_t index;
2415   unsigned int j = 0;
2416   struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2417   struct GNUNET_PeerIdentity key_ret;
2418   struct FriendInfo *friend;
2419
2420   current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2421   
2422   /* No friends.*/
2423   if (0 == current_size)
2424     return NULL;
2425
2426   index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2427   iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2428
2429   /* Iterate till you don't reach to index. */
2430   for (j = 0; j < index ; j++)
2431     GNUNET_assert (GNUNET_YES ==
2432                    GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2433   do
2434   {
2435     /* Reset the index in friend peermap to 0 as we reached to the end. */
2436     if (j == current_size)
2437     {
2438       j = 0;
2439       GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2440       iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2441
2442     }
2443     
2444     /* Get the friend stored at the index, j*/
2445     GNUNET_assert (GNUNET_YES ==
2446                    GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2447                                                                 &key_ret,
2448                                                                 (const void **)&friend));
2449
2450     /* This friend is not congested and has not crossed trail threshold. */
2451     if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
2452         (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2453     {
2454       break;
2455     }
2456     friend = NULL;
2457     j++;
2458   } while (j != index);
2459
2460   GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2461   return friend;
2462 }
2463
2464
2465 /**
2466  * Compute 64 bit value of finger_identity corresponding to a finger index using 
2467  * chord formula. 
2468  * For all fingers, n.finger[i] = n + pow (2,i),
2469  * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2470  * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2471  * @param finger_index Index corresponding to which we calculate 64 bit value.
2472  * @return 64 bit value.
2473  */
2474 static uint64_t
2475 compute_finger_identity_value (unsigned int finger_index)
2476 {
2477   uint64_t my_id64;
2478
2479   memcpy (&my_id64, &my_identity, sizeof (uint64_t));
2480   my_id64 = GNUNET_ntohll (my_id64);
2481   
2482   /* Are we looking for immediate predecessor? */
2483   if (PREDECESSOR_FINGER_ID == finger_index)
2484     return (my_id64 - 1);
2485   else
2486   {
2487     uint64_t add = (uint64_t)1 << finger_index;  
2488     return (my_id64 + add);
2489   }
2490 }
2491
2492
2493 /*
2494  * Choose a random friend. Calculate the next finger identity to search,from 
2495  * current_search_finger_index. Start looking for the trail to reach to
2496  * finger identity through this random friend.
2497  *
2498  * @param cls closure for this task
2499  * @param tc the context under which the task is running
2500  */
2501 static void
2502 send_find_finger_trail_message (void *cls,
2503                                 const struct GNUNET_SCHEDULER_TaskContext *tc)
2504 {
2505   struct FriendInfo *target_friend;
2506   struct GNUNET_TIME_Relative next_send_time;
2507   struct GNUNET_HashCode trail_id;
2508   struct GNUNET_HashCode intermediate_trail_id;
2509   unsigned int is_predecessor;
2510   uint64_t finger_id_value;
2511
2512   /* Schedule another send_find_finger_trail_message task. */
2513   next_send_time.rel_value_us =
2514       DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
2515       GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2516                                 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2517   find_finger_trail_task =
2518       GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
2519                                     NULL);
2520
2521   //FIXME: adding this check, so that once we found an entry for 0 and 64 then
2522   //don't schedule. Remove it afterwards.
2523   struct FingerInfo *succ;
2524   struct FingerInfo *pred;
2525   succ = &finger_table[0];
2526   pred = &finger_table[PREDECESSOR_FINGER_ID];
2527   
2528   if((GNUNET_YES == succ->is_present) &&
2529      (GNUNET_YES == pred->is_present))
2530     return;
2531   
2532    /* No space in my routing table. (Source and destination peers also store entries
2533    * in their routing table).  */
2534   if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2535     return;
2536   
2537     
2538   target_friend = select_random_friend ();
2539   if (NULL == target_friend)
2540   {
2541     return;
2542   }
2543   
2544   finger_id_value = compute_finger_identity_value (current_search_finger_index);
2545   
2546   if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2547     is_predecessor = 1;
2548   else
2549     is_predecessor = 0;
2550   
2551   /* Generate a unique trail id for trail we are trying to setup. */
2552   GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2553                               &trail_id, sizeof (trail_id));
2554   memset(&intermediate_trail_id, 0, sizeof (struct GNUNET_HashCode));
2555   
2556   GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_id_value,
2557                                    target_friend->id, target_friend, 0, NULL,
2558                                    is_predecessor, trail_id, 
2559                                    intermediate_trail_id);
2560 }
2561
2562
2563 /**
2564  * In case there are already maximum number of possible trails to reach to a
2565  * finger, then check if the new trail's length is lesser than any of the
2566  * existing trails.
2567  * If yes then replace that old trail by new trail.
2568  *
2569  * Note: Here we are taking length as a parameter to choose the best possible
2570  * trail, but there could be other parameters also like:
2571  * 1. duration of existence of a trail - older the better.
2572  * 2. if the new trail is completely disjoint than the
2573  *    other trails, then may be choosing it is better.
2574  *
2575  * @param existing_finger
2576  * @param new_finger_trail
2577  * @param new_finger_trail_length
2578  * @param new_finger_trail_id
2579  */
2580 static void
2581 select_and_replace_trail (struct FingerInfo *existing_finger,
2582                           const struct GNUNET_PeerIdentity *new_trail,
2583                           unsigned int new_trail_length,
2584                           struct GNUNET_HashCode new_trail_id)
2585 {
2586   struct Trail *trail_list_iterator;
2587   unsigned int largest_trail_length;
2588   unsigned int largest_trail_index;
2589   struct Trail_Element *trail_element;
2590   unsigned int i;
2591
2592   largest_trail_length = new_trail_length;
2593   largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2594
2595   GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2596
2597   for (i = 0; i < existing_finger->trails_count; i++)
2598   {
2599     trail_list_iterator = &existing_finger->trail_list[i];
2600     if (trail_list_iterator->trail_length > largest_trail_length)
2601     {
2602       largest_trail_length = trail_list_iterator->trail_length;
2603       largest_trail_index = i;
2604     }
2605   }
2606
2607   /* New trail is not better than existing ones. Send trail teardown. */
2608   if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2609   {
2610     struct GNUNET_PeerIdentity next_hop;
2611     
2612     memcpy (&next_hop, &new_trail[0], sizeof(struct GNUNET_PeerIdentity));
2613     GDS_ROUTING_remove_trail (new_trail_id);
2614     GDS_NEIGHBOURS_send_trail_teardown (new_trail_id, 
2615                                         GDS_ROUTING_SRC_TO_DEST,
2616                                         next_hop);
2617     return;
2618   }
2619
2620   /* Send trail teardown message across the replaced trail. */
2621   struct Trail *replace_trail = &existing_finger->trail_list[largest_trail_index];
2622   existing_finger->trail_list[largest_trail_index].is_present = GNUNET_NO;
2623   GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (replace_trail->trail_id));
2624   GDS_NEIGHBOURS_send_trail_teardown (replace_trail->trail_id,
2625                                       GDS_ROUTING_SRC_TO_DEST,
2626                                       replace_trail->trail_head->peer);
2627   /* Free the trail. */
2628   while (NULL != (trail_element = replace_trail->trail_head))
2629   {
2630     GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2631                                  replace_trail->trail_tail, trail_element);
2632     GNUNET_free_non_null (trail_element);
2633   }
2634
2635   /* Add new trial at that location. */
2636   replace_trail->is_present = GNUNET_YES;
2637   replace_trail->trail_length = new_trail_length;
2638   replace_trail->trail_id = new_trail_id;
2639   //FIXME: Do we need to add pointers for head and tail. 
2640   i = 0;
2641   while (i < new_trail_length)
2642   {
2643     struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2644     element->peer = new_trail[i];
2645
2646     GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2647                                       replace_trail->trail_tail,
2648                                       element);
2649   }
2650 }
2651
2652
2653 /**
2654  * Check if the new trail to reach to finger is unique or do we already have
2655  * such a trail present for finger.
2656  * @param existing_finger Finger identity
2657  * @param new_trail New trail to reach @a existing_finger
2658  * @param trail_length Total number of peers in new_trail.
2659  * @return #GNUNET_YES if the new trail is unique
2660  *         #GNUNET_NO if same trail is already present.
2661  */
2662 static int
2663 is_new_trail_unique (struct FingerInfo *existing_finger,
2664                      const struct GNUNET_PeerIdentity *new_trail,
2665                      unsigned int trail_length)
2666 {
2667   struct Trail *trail_list_iterator;
2668   struct Trail_Element *trail_element;
2669   int i;
2670   int j;
2671   int trail_unique = GNUNET_NO;
2672
2673   GNUNET_assert (existing_finger->trails_count > 0);
2674   
2675   /* Iterate over list of trails. */
2676   for (i = 0; i < existing_finger->trails_count; i++)
2677   {
2678     trail_list_iterator = &existing_finger->trail_list[i];
2679     GNUNET_assert (GNUNET_YES == trail_list_iterator->is_present);
2680     
2681     /* New trail and existing trail length are not same. */
2682     if (trail_list_iterator->trail_length != trail_length)
2683     {
2684       trail_unique = GNUNET_YES;
2685       continue;
2686     }
2687     
2688     trail_element = trail_list_iterator->trail_head;
2689     for (j = 0; j < trail_list_iterator->trail_length; j++)
2690     {
2691       if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2692                                                 &trail_element->peer))
2693       {
2694         trail_unique = GNUNET_YES;
2695         continue;
2696       }
2697       trail_element = trail_element->next;
2698     }
2699     
2700     trail_unique = GNUNET_NO;
2701   }
2702   
2703   return trail_unique;
2704 }
2705
2706
2707 /**
2708  * Add a new trail to existing finger. This function is called only when finger 
2709  * is not my own identity or a friend.
2710  * @param existing_finger Finger 
2711  * @param new_finger_trail New trail from me to finger, NOT including endpoints
2712  * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2713  * @param new_finger_trail_id Unique identifier of the trail.
2714  */
2715 static void
2716 add_new_trail (struct FingerInfo *existing_finger,
2717                const struct GNUNET_PeerIdentity *new_trail,
2718                unsigned int new_trail_length,
2719                struct GNUNET_HashCode new_trail_id)
2720 {
2721   struct Trail *trail_list_iterator;
2722   struct FriendInfo *first_friend;
2723   int i;
2724
2725   if (GNUNET_NO == is_new_trail_unique (existing_finger, new_trail,
2726                                         new_trail_length))
2727   {
2728     return;
2729   }
2730   
2731   trail_list_iterator = &existing_finger->trail_list[existing_finger->trails_count];
2732   GNUNET_assert (GNUNET_NO == trail_list_iterator->is_present);
2733   trail_list_iterator->trail_id = new_trail_id;
2734   trail_list_iterator->trail_length = new_trail_length;
2735   existing_finger->trails_count++;
2736   trail_list_iterator->is_present = GNUNET_YES;
2737   
2738   GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2739                                                              &existing_finger->finger_identity)));
2740   /* If finger is a friend then we never call this function. */
2741   GNUNET_assert (new_trail_length > 0);
2742   
2743   first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2744                                                     &new_trail[0]);
2745   first_friend->trails_count++;
2746   
2747   for (i = 0; i < new_trail_length; i++)
2748   {
2749     struct Trail_Element *element;
2750     
2751     element = GNUNET_new (struct Trail_Element);
2752     element->peer = new_trail[i];
2753     GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2754                                       trail_list_iterator->trail_tail,
2755                                       element);
2756   }
2757   /* Do we need to add trail head and trail tail in the trail list itearator.*/
2758   
2759 }
2760
2761
2762 /**
2763  * FIXME Check if this function is called for opposite direction if yes then 
2764  * take it as parameter. 
2765  * Get the next hop to send trail teardown message from routing table and
2766  * then delete the entry from routing table. Send trail teardown message for a 
2767  * specific trail of a finger. 
2768  * @param finger Finger whose trail is to be removed. 
2769  * @param trail List of peers in trail from me to a finger, NOT including 
2770  *              endpoints. 
2771  */
2772 static void
2773 send_trail_teardown (struct FingerInfo *finger,
2774                      struct Trail *trail)
2775 {
2776   struct FriendInfo *friend;
2777   struct GNUNET_PeerIdentity *next_hop;
2778   
2779   GNUNET_assert (NULL != 
2780                 (next_hop = GDS_ROUTING_get_next_hop (trail->trail_id, 
2781                                                       GDS_ROUTING_SRC_TO_DEST)));
2782   
2783   GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2784                                                        &my_identity));
2785
2786   GNUNET_assert (trail->is_present == GNUNET_YES);
2787   
2788   /* Finger is not a friend. */
2789   if (trail->trail_length > 0)
2790   {
2791     GNUNET_assert (NULL != (friend = 
2792                    GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2793                                                       &trail->trail_head->peer)));
2794   }
2795   else
2796   {
2797     GNUNET_assert (NULL != (friend = 
2798                    GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2799                                                       &finger->finger_identity)));
2800   }
2801     
2802   GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &friend->id)); //Fixme: assertion fails. 
2803   GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
2804   friend->trails_count--;
2805   GDS_NEIGHBOURS_send_trail_teardown (trail->trail_id,
2806                                       GDS_ROUTING_SRC_TO_DEST,
2807                                       friend->id);
2808 }
2809
2810
2811 /**
2812  * Send trail teardown message across all the trails to reach to finger. 
2813  * @param finger Finger whose all the trail should be freed. 
2814  */
2815 static void
2816 send_all_finger_trails_teardown (struct FingerInfo *finger)
2817 {
2818   unsigned int i;
2819   
2820   for (i = 0; i < finger->trails_count; i++)
2821   {
2822     struct Trail *trail;
2823     
2824     trail = &finger->trail_list[i];
2825     GNUNET_assert (trail->is_present == GNUNET_YES);
2826     send_trail_teardown (finger, trail);
2827     trail->is_present = GNUNET_NO;
2828    }
2829 }
2830
2831
2832 /**
2833  * Free a specific trail
2834  * @param trail List of peers to be freed. 
2835  */
2836 static void
2837 free_trail (struct Trail *trail)
2838 {
2839   struct Trail_Element *trail_element;
2840
2841   while (NULL != (trail_element = trail->trail_head))
2842   {
2843     GNUNET_CONTAINER_DLL_remove (trail->trail_head, 
2844                                  trail->trail_tail,
2845                                  trail_element);
2846     GNUNET_free_non_null (trail_element);
2847   }  
2848   trail->trail_head = NULL;
2849   trail->trail_tail = NULL;
2850 }
2851
2852
2853 /**
2854  * Free finger and its trail.
2855  * @param finger Finger to be freed.
2856  */
2857 static void
2858 free_finger (struct FingerInfo *finger, unsigned int finger_table_index)
2859 {
2860   struct Trail *trail;
2861   unsigned int i;
2862
2863   /* Free all the trails to reach to finger */
2864   for (i = 0; i < finger->trails_count; i++)
2865   {
2866     trail = &finger->trail_list[i];
2867     //FIXME: Check if there are any missing entry in this list because of 
2868     // how we insert. If not then no need of this check.
2869     if (GNUNET_NO == trail->is_present)
2870       continue;
2871     
2872     if (trail->trail_length > 0)
2873     {
2874       free_trail (trail);
2875     }
2876     trail->is_present = GNUNET_NO;
2877   }
2878   
2879   finger->is_present = GNUNET_NO;
2880   memset ((void *)&finger_table[finger_table_index], 0, sizeof (finger_table[finger_table_index]));
2881 }
2882
2883
2884 /**
2885  * FIXME: ensure that you are not adding any trail to reach to a friend which
2886  * is a finger. Also decide on should you increment trails count of a friend
2887  * which is also a finger. 
2888  * Add a new entry in finger table at finger_table_index. 
2889  * In case finger identity is me or a friend, then don't add a trail. NOTE
2890  * trail length to reach to a finger can be 0 only if the finger is a friend
2891  * or my identity.
2892  * In case a finger is a friend, then increment the trails count of the friend.
2893  * @param finger_identity Peer Identity of new finger
2894  * @param finger_trail Trail to reach from me to finger (excluding both end points).
2895  * @param finger_trail_length Total number of peers in @a finger_trail.
2896  * @param trail_id Unique identifier of the trail.
2897  * @param finger_table_index Index in finger table.
2898  */
2899 static void
2900 add_new_finger (struct GNUNET_PeerIdentity finger_identity,
2901                 const struct GNUNET_PeerIdentity *finger_trail,
2902                 unsigned int finger_trail_length,
2903                 struct GNUNET_HashCode trail_id,
2904                 unsigned int finger_table_index)
2905 {
2906   struct FingerInfo *new_entry;
2907   struct FriendInfo *first_trail_hop;
2908   struct Trail *trail;
2909   int i = 0;
2910   
2911   new_entry = GNUNET_new (struct FingerInfo);
2912   new_entry->finger_identity = finger_identity;
2913   new_entry->finger_table_index = finger_table_index;
2914   new_entry->is_present = GNUNET_YES;
2915   
2916   /* If the new entry is my own identity. */
2917   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2918   {
2919     new_entry->trails_count = 0;
2920     finger_table[finger_table_index] = *new_entry;
2921     GNUNET_free (new_entry);
2922     return;
2923   }
2924   
2925   /* If finger is a friend, then we don't actually have a trail.
2926    *  Just a trail id */
2927   if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
2928                                                  &finger_identity))
2929   {
2930     new_entry->trail_list[0].trail_id = trail_id;
2931     new_entry->trails_count = 1;
2932     new_entry->trail_list[0].is_present = GNUNET_YES;
2933     new_entry->trail_list[0].trail_length = 0;
2934     new_entry->trail_list[0].trail_head = NULL;
2935     new_entry->trail_list[0].trail_tail = NULL;
2936     finger_table[finger_table_index] = *new_entry;
2937     GNUNET_assert (NULL != 
2938                 (first_trail_hop = 
2939                        GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2940                                                           &finger_identity)));
2941
2942     first_trail_hop->trails_count++;
2943     GNUNET_free (new_entry);
2944     return;
2945   }
2946   
2947   /* finger trail length can be 0 only in case if finger is my identity or
2948    finger is friend. We should never reach here. */
2949   GNUNET_assert (finger_trail_length > 0);
2950   
2951   GNUNET_assert (NULL != 
2952                 (first_trail_hop = 
2953                        GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2954                                                           &finger_trail[0])));
2955   new_entry->trails_count = 1;
2956   first_trail_hop->trails_count++;
2957    
2958   /* Copy the finger trail into trail. */
2959   trail = GNUNET_new (struct Trail);
2960   while (i < finger_trail_length)
2961   {
2962     struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2963
2964     element->next = NULL;
2965     element->prev = NULL;
2966     element->peer = finger_trail[i];
2967     GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2968                                       trail->trail_tail,
2969                                       element);
2970     i++;
2971   }
2972   
2973   /* Add trail to trail list. */
2974   new_entry->trail_list[0].trail_head = trail->trail_head;
2975   new_entry->trail_list[0].trail_tail = trail->trail_tail;
2976   new_entry->trail_list[0].trail_length = finger_trail_length;
2977   new_entry->trail_list[0].trail_id = trail_id;
2978   new_entry->trail_list[0].is_present = GNUNET_YES;
2979   finger_table[finger_table_index] = *new_entry;
2980   //GNUNET_free (new_entry);
2981   //GNUNET_free (trail);
2982   return;
2983 }
2984
2985
2986 /**
2987  * Scan the trail to check if there is any other friend in the trail other than
2988  * first hop. If yes then shortcut the trail, send trail compression message to
2989  * peers which are no longer part of trail and send back the updated trail
2990  * and trail_length to calling function.
2991  * @param finger_identity Finger whose trail we will scan.
2992  * @param finger_trail [in, out] Trail to reach from source to finger,
2993  * @param finger_trail_length  Total number of peers in original finger_trail.
2994  * @param finger_trail_id Unique identifier of the finger trail.
2995  * @return updated trail length in case we shortcut the trail, else original
2996  *         trail length.
2997  */
2998 static struct GNUNET_PeerIdentity *
2999 scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
3000                          const struct GNUNET_PeerIdentity *trail,
3001                          unsigned int trail_length,
3002                          struct GNUNET_HashCode trail_id,
3003                          int *new_trail_length)
3004 {
3005   struct FriendInfo *target_friend;
3006   struct GNUNET_PeerIdentity *new_trail;
3007   unsigned int i;
3008   
3009   /* I am my own finger. */
3010   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3011   {
3012     *new_trail_length = 0;
3013     return NULL;
3014   }
3015
3016   if (0 == trail_length)
3017   {
3018     *new_trail_length = 0;
3019     return NULL;
3020   }
3021   
3022   /* If finger identity is a friend. */
3023   if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
3024   {
3025     *new_trail_length = 0;
3026     
3027     /* If there is trail to reach this finger/friend */
3028     if (trail_length > 0)
3029     {
3030       /* Finger is your first friend. */
3031       GDS_ROUTING_update_trail_next_hop (trail_id, finger_identity);
3032       GNUNET_assert (NULL != 
3033                     (target_friend = 
3034                      GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3035                                                         &trail[0])));
3036       
3037
3038       GDS_NEIGHBOURS_send_trail_compression (my_identity, 
3039                                              trail_id, finger_identity,
3040                                              target_friend);
3041     }
3042     return NULL;
3043   }
3044
3045   /*  For other cases, when its neither a friend nor my own identity.*/
3046   for (i = trail_length - 1; i > 0; i--)
3047   {
3048     /* If the element at this index in trail is a friend. */
3049     if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
3050     {
3051       struct FriendInfo *target_friend;
3052       int j = 0;
3053
3054       GNUNET_assert (NULL != 
3055                     (target_friend = 
3056                      GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3057                                                         &trail[0])));
3058       GDS_ROUTING_update_trail_next_hop (trail_id, trail[i]);
3059       GDS_NEIGHBOURS_send_trail_compression (my_identity, 
3060                                              trail_id, trail[i],
3061                                              target_friend);
3062
3063     
3064       /* Copy the trail from index i to index (trail_length -1) into a new trail
3065        *  and update new trail length */
3066       new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - i));
3067       while (i < trail_length)
3068       {
3069         memcpy (&new_trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
3070         j++;
3071         i++;
3072       }
3073       *new_trail_length = j+1;
3074       GNUNET_assert((j+1) == (trail_length - 1)); //FIXME: remove it afterwards.
3075       return new_trail;
3076     }
3077   }
3078   
3079   /* If we did not compress the trail, return the original trail back.*/
3080   new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length); 
3081   *new_trail_length = trail_length;
3082   memcpy (new_trail, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
3083   return new_trail;
3084 }
3085
3086
3087 /**
3088  * Periodic task to verify current successor. There can be multiple trails to reach
3089  * to successor, choose the shortest one and send verify successor message
3090  * across that trail. 
3091  * @param cls closure for this task
3092  * @param tc the context under which the task is running
3093  */
3094 static void
3095 send_verify_successor_message (void *cls,
3096                                 const struct GNUNET_SCHEDULER_TaskContext *tc)
3097 {
3098   struct FriendInfo *target_friend;
3099   struct GNUNET_HashCode trail_id;
3100   int i;
3101   struct GNUNET_TIME_Relative next_send_time;
3102   struct Trail *trail;
3103   struct Trail_Element *element;
3104   unsigned int trail_length;
3105   unsigned int j = 0;
3106   struct FingerInfo *successor;
3107    
3108   /* Schedule another send_find_finger_trail_message task. */
3109   next_send_time.rel_value_us =
3110       DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
3111       GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
3112                                 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
3113   send_verify_successor_task =
3114       GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
3115                                     NULL);
3116   
3117   successor = &finger_table[0];
3118   i = 0;
3119   trail = &successor->trail_list[i];
3120   
3121   /* Store the successor for path tracking */
3122   if (track_topology &&  (NULL != GDS_stats))
3123   {
3124     char *my_id_str;
3125     char *succ_id_str;
3126     char *key;
3127
3128     my_id_str = GNUNET_strdup (GNUNET_i2s (&my_identity));
3129     succ_id_str = GNUNET_strdup (GNUNET_i2s
3130                                  (&successor->finger_identity));
3131     GNUNET_asprintf (&key, "XDHT:0:%.4s:%.4s", my_id_str, succ_id_str);
3132     GNUNET_free (my_id_str);
3133     GNUNET_free (succ_id_str);
3134     GNUNET_STATISTICS_update (GDS_stats, "key", 1, 0);
3135     GNUNET_free (key);
3136   }
3137   
3138   GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, 
3139                                                       &successor->finger_identity));
3140   
3141   /* Trail stored at this index. */
3142   GNUNET_assert (GNUNET_YES == trail->is_present);
3143     
3144   trail_id = trail->trail_id;
3145   trail_length = trail->trail_length;
3146        
3147   if (trail_length > 0)
3148   {
3149      /* Copy the trail into peer list. */
3150     struct GNUNET_PeerIdentity peer_list[trail_length];
3151     
3152     element = trail->trail_head;
3153     while (j < trail_length)
3154     {
3155       peer_list[j] = element->peer;
3156       element = element->next;
3157       j++;
3158     }
3159       
3160     GNUNET_assert (NULL != (target_friend = 
3161                             GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
3162                                                                &peer_list[0])));
3163     GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3164                                                   successor->finger_identity,
3165                                                   trail_id, peer_list, trail_length,
3166                                                   target_friend);
3167     return;
3168   }
3169   else
3170   {
3171     GNUNET_assert (NULL != (target_friend = 
3172                             GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
3173                                                                &successor->finger_identity)));
3174     GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
3175                                                   successor->finger_identity,
3176                                                   trail_id, NULL, 0,
3177                                                   target_friend);
3178     return;
3179   }
3180 }
3181
3182
3183 /**
3184  * Update the current search finger index. 
3185  */
3186 static void
3187 update_current_search_finger_index (struct GNUNET_PeerIdentity finger_identity,
3188                                     unsigned int finger_table_index)
3189 {
3190   struct FingerInfo *successor;
3191   
3192   if (finger_table_index != current_search_finger_index)
3193     return;
3194   
3195   successor = &finger_table[0];
3196   GNUNET_assert (GNUNET_YES == successor->is_present);
3197  
3198   /* We were looking for immediate successor.  */
3199   if (0 == current_search_finger_index)
3200   {
3201     /* Start looking for immediate predecessor. */
3202     current_search_finger_index = PREDECESSOR_FINGER_ID;
3203   
3204     /* If I am not my own successor, then send a verify successor message. */
3205     //if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3206     //{
3207       //send_verify_successor_message (successor);
3208     //}
3209     
3210     if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
3211     {
3212       if (GNUNET_SCHEDULER_NO_TASK == send_verify_successor_task) 
3213         send_verify_successor_task = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
3214     }
3215     
3216     return;
3217   }
3218   
3219   current_search_finger_index = current_search_finger_index - 1;
3220   return;
3221 }
3222
3223
3224 /**
3225  * Get the first set bit in val. 
3226  * @param val Value
3227  * @return Position of first bit set.
3228  */
3229 static unsigned int
3230 find_set_bit(uint64_t val)
3231 {
3232   uint64_t i;
3233   unsigned int pos;
3234   
3235   i = 1;
3236   pos = 0;
3237   
3238   while(!(i && val))
3239   {
3240     i = i << val;
3241     pos++;
3242   }
3243   return pos;
3244 }
3245
3246 /**
3247  * Calculate finger_table_index from initial 64 bit finger identity value that 
3248  * we send in trail setup message. 
3249  * @param ultimate_destination_finger_value Value that we calculated from our
3250  *                                          identity and finger_table_index.
3251  * @param is_predecessor Is the entry for predecessor or not?
3252  * @return finger_table_index Value between 0 <= finger_table_index <= 64
3253  *                            finger_table_index > PREDECESSOR_FINGER_ID , 
3254  *                            if no valid finger_table_index is found. 
3255  */
3256 static unsigned int
3257 get_finger_table_index (uint64_t ultimate_destination_finger_value,
3258                         unsigned int is_predecessor)
3259 {
3260   uint64_t my_id64;
3261   uint64_t diff;
3262   unsigned int finger_table_index;
3263
3264   memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3265   my_id64 = GNUNET_ntohll (my_id64);
3266   
3267   /* Is this a predecessor finger? */
3268   if (1 == is_predecessor)
3269   {
3270     diff =  my_id64 - ultimate_destination_finger_value;
3271     if (1 == diff)
3272       finger_table_index = PREDECESSOR_FINGER_ID;
3273     else
3274       finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3275     
3276   }
3277   else 
3278   {
3279     diff = ultimate_destination_finger_value - my_id64;
3280     finger_table_index = find_set_bit(diff);
3281   }
3282   
3283   return finger_table_index;
3284 }
3285
3286
3287 /**
3288  * Remove finger and its associated data structures from finger table. 
3289  * @param finger Finger to be removed.
3290  */
3291 static void
3292 remove_existing_finger (struct FingerInfo *existing_finger, 
3293                         unsigned int finger_table_index)
3294 {
3295   struct FingerInfo *finger;
3296
3297   finger = &finger_table[finger_table_index];
3298   GNUNET_assert (GNUNET_YES == finger->is_present);
3299   
3300   /* If I am my own finger, then we have no trails. */
3301   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
3302                                             &my_identity))
3303   {
3304     finger->is_present = GNUNET_NO;
3305     memset ((void *)&finger_table[finger_table_index], 0,
3306             sizeof (finger_table[finger_table_index]));
3307     return;
3308   }
3309   
3310   /* For all other fingers, send trail teardown across all the trails to reach
3311    finger, and free the finger. */
3312   send_all_finger_trails_teardown (finger);
3313   free_finger (finger, finger_table_index);
3314   return;
3315 }
3316
3317
3318 /**
3319  * Check if there is already an entry in finger_table at finger_table_index.
3320  * We get the finger_table_index from 64bit finger value we got from the network.
3321  * -- If yes, then select the closest finger.
3322  *   -- If new and existing finger are same, then check if you can store more 
3323  *      trails. 
3324  *      -- If yes then add trail, else keep the best trails to reach to the 
3325  *         finger. 
3326  *   -- If the new finger is closest, remove the existing entry, send trail
3327  *      teardown message across all the trails to reach the existing entry.
3328  *      Add the new finger.
3329  *  -- If new and existing finger are different, and existing finger is closest
3330  *     then do nothing.  
3331  * -- Update current_search_finger_index.
3332  * @param finger_identity Peer Identity of new finger
3333  * @param finger_trail Trail to reach the new finger
3334  * @param finger_trail_length Total number of peers in @a new_finger_trail.
3335  * @param is_predecessor Is this entry for predecessor in finger_table?
3336  * @param finger_value 64 bit value of finger identity that we got from network.
3337  * @param finger_trail_id Unique identifier of @finger_trail.
3338  */
3339 static void
3340 finger_table_add (struct GNUNET_PeerIdentity finger_identity, 
3341                   const struct GNUNET_PeerIdentity *finger_trail, 
3342                   unsigned int finger_trail_length,
3343                   unsigned int is_predecessor,
3344                   uint64_t finger_value,
3345                   struct GNUNET_HashCode finger_trail_id)
3346 {
3347   struct FingerInfo *existing_finger;
3348   struct GNUNET_PeerIdentity *closest_peer;
3349   struct FingerInfo *successor;
3350   int updated_finger_trail_length; 
3351   unsigned int finger_table_index;
3352   
3353   /* Get the finger_table_index corresponding to finger_value we got from network.*/
3354   finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3355    
3356   /* Invalid finger_table_index. */
3357   if ((finger_table_index > PREDECESSOR_FINGER_ID))
3358   {
3359     GNUNET_break_op (0);
3360     return;
3361   }
3362
3363   /* New entry same as successor. */
3364   if ((0 != finger_table_index) && 
3365       (PREDECESSOR_FINGER_ID != finger_table_index)) 
3366   {
3367     successor = &finger_table[0];
3368     GNUNET_assert (GNUNET_YES == successor->is_present);
3369     if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
3370                                               &successor->finger_identity))
3371     {
3372       current_search_finger_index = 0;
3373       return;
3374     }
3375   }
3376   
3377   existing_finger = &finger_table[finger_table_index];
3378  
3379   /* No entry present in finger_table for given finger map index. */
3380   if (GNUNET_NO == existing_finger->is_present)
3381   {
3382     struct GNUNET_PeerIdentity *updated_trail;
3383      
3384     /* Shorten the trail if possible. */
3385     updated_finger_trail_length = finger_trail_length;
3386     updated_trail =
3387          scan_and_compress_trail (finger_identity, finger_trail,
3388                                   finger_trail_length, finger_trail_id, 
3389                                   &updated_finger_trail_length);
3390
3391     add_new_finger (finger_identity, updated_trail, 
3392                     updated_finger_trail_length,
3393                     finger_trail_id, finger_table_index);
3394     update_current_search_finger_index (finger_identity, 
3395                                         finger_table_index);
3396     return;
3397   }
3398   
3399   
3400   /* If existing entry and finger identity are not same. */
3401   if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3402                                             &finger_identity))
3403   {
3404     closest_peer = select_closest_peer (&existing_finger->finger_identity,
3405                                         &finger_identity,
3406                                         finger_value, 
3407                                         is_predecessor);
3408     
3409     /* If the new finger is the closest peer. */
3410     if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
3411     {
3412       struct GNUNET_PeerIdentity *updated_trail;
3413       /* Shorten the trail if possible. */
3414       updated_finger_trail_length = finger_trail_length;
3415       updated_trail =
3416         scan_and_compress_trail (finger_identity, finger_trail,
3417                                  finger_trail_length, finger_trail_id, 
3418                                  &updated_finger_trail_length);
3419       remove_existing_finger (existing_finger, finger_table_index);
3420       add_new_finger (finger_identity, updated_trail, updated_finger_trail_length,
3421                       finger_trail_id, finger_table_index);
3422       
3423     }
3424     else
3425     {
3426       /* Existing finger is the closest one. We need to send trail teardown  
3427          across the trail setup in routing table of all the peers. */
3428       if (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, &my_identity))
3429       {
3430         if (finger_trail_length > 0)
3431           GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id, 
3432                                               GDS_ROUTING_SRC_TO_DEST,
3433                                               finger_trail[0]);
3434         else
3435           GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id, 
3436                                               GDS_ROUTING_SRC_TO_DEST,
3437                                               finger_identity);
3438       }
3439     }
3440   }
3441   else
3442   {
3443     /* If both new and existing entry are same as my_identity, then do nothing. */
3444     if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3445                                               &my_identity))
3446     {
3447       return;
3448     }
3449     /* If the existing finger is not a friend. */
3450     if (NULL ==
3451         GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3452                                            &existing_finger->finger_identity))
3453     {
3454       struct GNUNET_PeerIdentity *updated_trail;
3455       
3456       /* Shorten the trail if possible. */
3457       updated_finger_trail_length = finger_trail_length;
3458       updated_trail =
3459          scan_and_compress_trail (finger_identity, finger_trail,
3460                                   finger_trail_length, finger_trail_id, 
3461                                   &updated_finger_trail_length);
3462       /* If there is space to store more trails. */
3463       if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3464         add_new_trail (existing_finger, updated_trail,
3465                        updated_finger_trail_length, finger_trail_id);
3466       else
3467         select_and_replace_trail (existing_finger, updated_trail,
3468                                   updated_finger_trail_length, finger_trail_id);
3469        
3470     }
3471   }
3472   update_current_search_finger_index (finger_identity, finger_table_index);
3473   return;
3474 }
3475
3476 /**
3477  * Core handler for P2P put messages.
3478  * @param cls closure
3479  * @param peer sender of the request
3480  * @param message message
3481  * @return #GNUNET_OK to keep the connection open,
3482  *         #GNUNET_SYSERR to close it (signal serious error)
3483  */
3484 static int
3485 handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
3486                     const struct GNUNET_MessageHeader *message)
3487 {
3488   struct PeerPutMessage *put;
3489   struct GNUNET_PeerIdentity *put_path;
3490   struct GNUNET_PeerIdentity best_known_dest;
3491   struct GNUNET_HashCode intermediate_trail_id;
3492   struct GNUNET_PeerIdentity *next_hop;
3493   enum GNUNET_DHT_RouteOption options;
3494   struct GNUNET_HashCode test_key;
3495   void *payload;
3496   size_t msize;
3497   uint32_t putlen;
3498   size_t payload_size;
3499   uint64_t key_value;
3500   
3501   msize = ntohs (message->size);
3502   if (msize < sizeof (struct PeerPutMessage))
3503   { 
3504     GNUNET_break_op (0);
3505     return GNUNET_OK;
3506   }
3507   
3508   put = (struct PeerPutMessage *) message;
3509   putlen = ntohl (put->put_path_length);
3510    
3511   if ((msize <
3512        sizeof (struct PeerPutMessage) +
3513        putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3514       (putlen >
3515        GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3516   {
3517     GNUNET_break_op (0);
3518     return GNUNET_OK;
3519   }
3520
3521   best_known_dest = put->best_known_destination;
3522   put_path = (struct GNUNET_PeerIdentity *) &put[1];
3523   payload = &put_path[putlen];
3524   options = ntohl (put->options);
3525   intermediate_trail_id = put->intermediate_trail_id;
3526   
3527   payload_size = msize - (sizeof (struct PeerPutMessage) + 
3528                           putlen * sizeof (struct GNUNET_PeerIdentity));
3529   
3530   switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3531                                 payload, payload_size, &test_key))
3532   {
3533     case GNUNET_YES:
3534       if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3535       {
3536         char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3537         GNUNET_break_op (0);
3538         GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3539                     "PUT with key `%s' for block with key %s\n",
3540                      put_s, GNUNET_h2s_full (&test_key));
3541         GNUNET_free (put_s);
3542         return GNUNET_OK;
3543       }
3544     break;
3545     case GNUNET_NO:
3546       GNUNET_break_op (0);
3547       return GNUNET_OK;
3548     case GNUNET_SYSERR:
3549       /* cannot verify, good luck */
3550       break;
3551   }
3552   
3553    if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3554   {
3555     switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3556                                    ntohl (put->block_type),
3557                                    NULL,    /* query */
3558                                    NULL, 0, /* bloom filer */
3559                                    NULL, 0, /* xquery */
3560                                    payload, payload_size))
3561     {
3562     case GNUNET_BLOCK_EVALUATION_OK_MORE:
3563     case GNUNET_BLOCK_EVALUATION_OK_LAST:
3564       break;
3565
3566     case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3567     case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3568     case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3569     case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3570     case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3571     case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3572     default:
3573       GNUNET_break_op (0);
3574       return GNUNET_OK;
3575     }
3576   }
3577   
3578   /* extend 'put path' by sender */
3579   struct GNUNET_PeerIdentity pp[putlen + 1];
3580   if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3581   {
3582     memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3583     pp[putlen] = *peer;
3584     putlen++;
3585   }
3586   else
3587     putlen = 0;
3588   
3589   memcpy (&key_value, &(put->key), sizeof (uint64_t));
3590   if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3591   {
3592     next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id, 
3593                                          GDS_ROUTING_SRC_TO_DEST);
3594     if (NULL == next_hop)
3595     {
3596       GNUNET_STATISTICS_update (GDS_stats,
3597                                 gettext_noop ("# Next hop to forward the packet not found "
3598                                 "trail setup request, packet dropped."),
3599                                 1, GNUNET_NO);
3600       return GNUNET_SYSERR;
3601     }
3602   }
3603   else
3604   {
3605     struct Closest_Peer successor;
3606     key_value = GNUNET_ntohll (key_value);
3607     successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3608     
3609     next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3610     *next_hop = successor.next_hop;
3611     intermediate_trail_id = successor.trail_id;
3612     best_known_dest = successor.best_known_destination;
3613   }
3614   
3615   GDS_CLIENTS_process_put (options,
3616                            ntohl (put->block_type),
3617                            ntohl (put->hop_count),
3618                            ntohl (put->desired_replication_level),
3619                            putlen, pp,
3620                            GNUNET_TIME_absolute_ntoh (put->expiration_time),
3621                            &put->key,
3622                            payload,
3623                            payload_size);
3624   
3625   /* I am the final destination */
3626   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &best_known_dest)) 
3627   {
3628     GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3629                               &(put->key),putlen, pp, ntohl (put->block_type), 
3630                               payload_size, payload);
3631   }
3632   else
3633   {
3634     GDS_NEIGHBOURS_send_put (&put->key,  
3635                              ntohl (put->block_type),ntohl (put->options),
3636                              ntohl (put->desired_replication_level),
3637                              best_known_dest, intermediate_trail_id, next_hop,
3638                              ntohl (put->hop_count), putlen, pp,
3639                              GNUNET_TIME_absolute_ntoh (put->expiration_time),
3640                              payload, payload_size);
3641   }
3642   return GNUNET_OK;
3643 }
3644
3645
3646 /**
3647  * Core handler for p2p get requests.
3648  *
3649  * @param cls closure
3650  * @param peer sender of the request
3651  * @param message message
3652  * @return #GNUNET_OK to keep the connection open,
3653  *         #GNUNET_SYSERR to close it (signal serious error)
3654  */
3655 static int
3656 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3657                     const struct GNUNET_MessageHeader *message)
3658 {
3659   const struct PeerGetMessage *get;
3660   const struct GNUNET_PeerIdentity *get_path;
3661   struct GNUNET_PeerIdentity best_known_dest;
3662   struct GNUNET_HashCode intermediate_trail_id;
3663   struct GNUNET_PeerIdentity *next_hop;
3664   uint32_t get_length;
3665   uint64_t key_value;
3666   size_t msize;
3667   
3668   msize = ntohs (message->size);
3669   if (msize < sizeof (struct PeerGetMessage))
3670   {
3671     GNUNET_break_op (0);
3672     return GNUNET_YES;
3673   }
3674
3675   get = (const struct PeerGetMessage *)message;
3676   get_length = ntohl (get->get_path_length);
3677   best_known_dest = get->best_known_destination;
3678   intermediate_trail_id = get->intermediate_trail_id;
3679   get_path = (const struct GNUNET_PeerIdentity *)&get[1];
3680
3681   if ((msize <
3682        sizeof (struct PeerGetMessage) +
3683        get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3684        (get_length >
3685         GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3686   {
3687     GNUNET_break_op (0);
3688     return GNUNET_YES; 
3689   }
3690   
3691   /* Add sender to get path */
3692   struct GNUNET_PeerIdentity gp[get_length + 1];
3693   if (get_length > 0)
3694     memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3695   gp[get_length] = *peer;
3696   get_length = get_length + 1;
3697   
3698   memcpy (&key_value, &(get->key), sizeof (uint64_t));
3699   key_value = GNUNET_ntohll (key_value);
3700
3701   /* I am not the final destination. I am part of trail to reach final dest. */
3702   if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&best_known_dest, &my_identity)))
3703   {
3704     next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id, 
3705                                          GDS_ROUTING_SRC_TO_DEST);
3706     if (NULL == next_hop)
3707     {
3708       GNUNET_STATISTICS_update (GDS_stats,
3709                                 gettext_noop ("# Next hop to forward the packet not found "
3710                                 "GET request, packet dropped."),
3711                                 1, GNUNET_NO);
3712       return GNUNET_SYSERR;
3713     }
3714   }
3715   else
3716   {
3717     struct Closest_Peer successor;
3718
3719     successor = find_successor (key_value, GDS_FINGER_TYPE_NON_PREDECESSOR);
3720     next_hop = GNUNET_new (struct GNUNET_PeerIdentity);
3721     *next_hop = successor.next_hop;
3722     best_known_dest = successor.best_known_destination;
3723     intermediate_trail_id = successor.trail_id;
3724   }
3725   
3726   GDS_CLIENTS_process_get (get->options, get->block_type,get->hop_count,
3727                            get->desired_replication_level, get->get_path_length,
3728                            gp, &get->key);
3729   /* I am the final destination. */
3730   if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &best_known_dest))
3731   {
3732     struct GNUNET_PeerIdentity final_get_path[get_length+1];
3733
3734     memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3735     memcpy (&final_get_path[get_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3736     get_length = get_length + 1;
3737     /* FIXME: here it may happen that we find our identity closest to key, but
3738      we don't have the data. then in that case, we should forward the packet
3739      to the next closest peer. */
3740     GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3741                               get_length, final_get_path, 
3742                               &final_get_path[get_length-2], &my_identity);
3743   }
3744   else
3745   {
3746     GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options, 
3747                              get->desired_replication_level, best_known_dest,
3748                              intermediate_trail_id, next_hop, 0,
3749                              get_length, gp); 
3750   }
3751   return GNUNET_YES;
3752 }
3753
3754
3755 /**
3756  * Core handler for get result
3757  * @param cls closure
3758  * @param peer sender of the request
3759  * @param message message
3760  * @return #GNUNET_OK to keep the connection open,
3761  *         #GNUNET_SYSERR to close it (signal serious error)
3762  */
3763 static int
3764 handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3765                            const struct GNUNET_MessageHeader *message)
3766 {
3767   const struct PeerGetResultMessage *get_result;
3768   const struct GNUNET_PeerIdentity *get_path;
3769   const struct GNUNET_PeerIdentity *put_path;
3770   const void *payload;
3771   size_t payload_size;
3772   size_t msize;
3773   unsigned int getlen;
3774   unsigned int putlen;
3775   int current_path_index;
3776   
3777   msize = ntohs (message->size);
3778   if (msize < sizeof (struct PeerGetResultMessage))
3779   {
3780     GNUNET_break_op (0);
3781     return GNUNET_YES;
3782   }
3783
3784   get_result = (const struct PeerGetResultMessage *)message;
3785   getlen = ntohl (get_result->get_path_length);
3786   putlen = ntohl (get_result->put_path_length);
3787   
3788   if ((msize <
3789        sizeof (struct PeerGetResultMessage) +
3790        getlen * sizeof (struct GNUNET_PeerIdentity) + 
3791        putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3792       (getlen >
3793        GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3794       (putlen >
3795          GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3796   {
3797     GNUNET_break_op (0);
3798     return GNUNET_YES;
3799   }
3800   
3801   put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3802   get_path = &put_path[putlen];
3803   payload = (const void *) &get_path[getlen];
3804   payload_size = msize - (sizeof (struct PeerGetResultMessage) + 
3805                          (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3806
3807   if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3808   {
3809     GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key), 
3810                               getlen, get_path, putlen,
3811                               put_path, get_result->type, payload_size, payload);
3812     return GNUNET_YES;
3813   }
3814   else
3815   {
3816     current_path_index = search_my_index (get_path, getlen);
3817     if (-1 == current_path_index )
3818     {
3819       GNUNET_break (0);
3820       return GNUNET_SYSERR;
3821     }
3822     GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3823                                     &get_path[current_path_index - 1],
3824                                     &(get_result->querying_peer), putlen, put_path,
3825                                     getlen, get_path, get_result->expiration_time,
3826                                     payload, payload_size);
3827     return GNUNET_YES;
3828   }  
3829   return GNUNET_SYSERR;
3830 }
3831
3832
3833 /**
3834  * Find the next hop to pass trail setup message. First find the local best known
3835  * hop from your own identity, friends and finger. If you were part of trail,
3836  * then get the next hop from routing table. Compare next_hop from routing table
3837  * and local best known hop, and return the closest one to final_dest_finger_val
3838  * @param final_dest_finger_val 64 bit value of finger identity
3839  * @param intermediate_trail_id If you are part of trail to reach to some other 
3840  *                              finger, then it is the trail id to reach to
3841  *                              that finger, else set to 0.
3842  * @param is_predecessor Are we looking for closest successor or predecessor. 
3843  * @param current_dest In case you are part of trail, then finger to which 
3844  *                     we should forward the message. Else my own identity
3845  * @return Closest Peer for @a final_dest_finger_val
3846  */
3847 static struct Closest_Peer
3848 get_local_best_known_next_hop (uint64_t final_dest_finger_val, 
3849                                struct GNUNET_HashCode intermediate_trail_id,
3850                                unsigned int is_predecessor,
3851                                 struct GNUNET_PeerIdentity prev_hop,
3852                                struct GNUNET_PeerIdentity source,
3853                                struct GNUNET_PeerIdentity *current_dest)
3854 {
3855   struct Closest_Peer peer;
3856   
3857   /* Find a local best known peer. */
3858   peer = find_successor (final_dest_finger_val, is_predecessor);//FIXME: chnage to better name
3859   
3860   /* Am I just a part of a trail towards a finger (current_destination)? */
3861   if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, current_dest)))
3862   {
3863     /* Select best successor among one found locally and current_destination 
3864      * that we got from network.*/
3865     if (0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3866                                               current_dest))
3867     { 
3868       struct GNUNET_PeerIdentity *closest_peer;
3869       struct GNUNET_PeerIdentity *local_best_known_dest;
3870       local_best_known_dest = GNUNET_new(struct GNUNET_PeerIdentity);
3871       memcpy(local_best_known_dest, &peer.best_known_destination, sizeof(struct GNUNET_PeerIdentity));
3872       
3873       closest_peer = select_closest_peer (local_best_known_dest,
3874                                           current_dest,
3875                                           final_dest_finger_val,
3876                                           is_predecessor);
3877
3878       GNUNET_free(local_best_known_dest);
3879       /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3880       if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest, closest_peer))
3881       {
3882         struct GNUNET_PeerIdentity *next_hop;
3883         next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3884                                              GDS_ROUTING_SRC_TO_DEST);
3885         GNUNET_assert (NULL != next_hop);
3886
3887         peer.next_hop = *next_hop;
3888         peer.best_known_destination =  *current_dest;
3889         peer.trail_id = intermediate_trail_id;
3890       }
3891     }  
3892   }
3893   return peer;
3894 }
3895
3896
3897 /* 
3898  * Core handle for PeerTrailSetupMessage.
3899  * @param cls closure
3900  * @param message message
3901  * @param peer peer identity this notification is about
3902  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3903  */
3904 static int
3905 handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3906                             const struct GNUNET_MessageHeader *message)
3907 {
3908   const struct PeerTrailSetupMessage *trail_setup;
3909   const struct GNUNET_PeerIdentity *trail_peer_list;
3910   struct GNUNET_PeerIdentity current_dest;
3911   struct FriendInfo *target_friend;
3912   struct GNUNET_PeerIdentity source;
3913   uint64_t final_dest_finger_val;
3914   struct GNUNET_HashCode intermediate_trail_id;
3915   struct GNUNET_HashCode trail_id;
3916   unsigned int is_predecessor;
3917   uint32_t trail_length;
3918   size_t msize;
3919
3920   msize = ntohs (message->size);
3921   if (msize < sizeof (struct PeerTrailSetupMessage))
3922   {
3923     GNUNET_break_op (0);
3924     return GNUNET_SYSERR;
3925   }
3926
3927   trail_setup = (const struct PeerTrailSetupMessage *) message;
3928   trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
3929                   sizeof (struct GNUNET_PeerIdentity);
3930   if ((msize - sizeof (struct PeerTrailSetupMessage)) % 
3931       sizeof (struct GNUNET_PeerIdentity) != 0)
3932   {
3933     GNUNET_break_op (0);
3934     return GNUNET_OK;      
3935   }           
3936   
3937   trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_setup[1];
3938   current_dest = trail_setup->best_known_destination;
3939   trail_id = trail_setup->trail_id;
3940   final_dest_finger_val = 
3941           GNUNET_ntohll (trail_setup->final_destination_finger_value);
3942   source = trail_setup->source_peer;
3943   is_predecessor = ntohl (trail_setup->is_predecessor);
3944   intermediate_trail_id = trail_setup->intermediate_trail_id;
3945   
3946    /* If I was the source and got the message back, then set trail length to 0.*/
3947   if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
3948   {
3949    trail_length = 0;  
3950   }
3951   
3952   /* Is my routing table full?  */
3953   if (GNUNET_YES == GDS_ROUTING_threshold_reached())
3954   {
3955     GNUNET_assert (NULL != 
3956                   (target_friend = 
3957                    GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
3958     GDS_NEIGHBOURS_send_trail_rejection (source, final_dest_finger_val,
3959                                          my_identity, is_predecessor,
3960                                          trail_peer_list, trail_length,
3961                                          trail_id, target_friend,
3962                                          CONGESTION_TIMEOUT);
3963     return GNUNET_OK;
3964   }
3965  
3966   /* Get the next hop to forward the trail setup request. */
3967   struct Closest_Peer next_peer = 
3968           get_local_best_known_next_hop (final_dest_finger_val, 
3969                                          intermediate_trail_id,
3970                                          is_predecessor,
3971                                          *peer,
3972                                          source,
3973                                          &current_dest);
3974  
3975   /* Am I the final destination? */
3976   if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
3977                                              &my_identity)))
3978   {
3979     //
3980     /* If I was not the source of this message for which now I am destination */
3981     if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
3982     {
3983       GDS_ROUTING_add (trail_id, *peer, my_identity);
3984     }
3985    
3986     if(trail_length > 0)
3987     {
3988       GNUNET_assert (NULL != 
3989                     (target_friend = 
3990                     GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
3991                                                        &trail_peer_list[trail_length-1])));
3992     }
3993     else
3994     {
3995       if(0 == GNUNET_CRYPTO_cmp_peer_identity (&source, &my_identity))
3996       {
3997         finger_table_add (my_identity, NULL, 0, is_predecessor, 
3998                           final_dest_finger_val, trail_id);
3999         return GNUNET_OK;
4000       }
4001       GNUNET_assert (NULL != 
4002                     (target_friend = 
4003                      GNUNET_CONTAINER_multipeermap_get (friend_peermap, &source)));
4004     }
4005    
4006     GDS_NEIGHBOURS_send_trail_setup_result (source,
4007                                             my_identity,
4008                                             target_friend, trail_length,
4009                                             trail_peer_list,
4010                                             is_predecessor, 
4011                                             final_dest_finger_val,trail_id);
4012   }
4013   else
4014   {
4015     GNUNET_assert (NULL != 
4016                     (target_friend = 
4017                       GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4018                                                           &next_peer.next_hop)));
4019     
4020     if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &source))
4021     {
4022       /* Add yourself to list of peers. */
4023       struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4024  
4025       memcpy (peer_list, trail_peer_list, 
4026               trail_length * sizeof (struct GNUNET_PeerIdentity));
4027       peer_list[trail_length] = my_identity;
4028      
4029       GDS_NEIGHBOURS_send_trail_setup (source,
4030                                        final_dest_finger_val,
4031                                        next_peer.best_known_destination,
4032                                        target_friend, trail_length + 1, peer_list,
4033                                        is_predecessor, trail_id,
4034                                        next_peer.trail_id);
4035     }
4036     else
4037         GDS_NEIGHBOURS_send_trail_setup (source,
4038                                          final_dest_finger_val,
4039                                          next_peer.best_known_destination,
4040                                          target_friend, 0, NULL,
4041                                          is_predecessor, trail_id,
4042                                          next_peer.trail_id);
4043   }
4044   return GNUNET_OK;
4045 }
4046
4047 #if 0
4048 /* FIXME: here we are calculating my_index and comparing also in this function.
4049    And we are doing it again here in this function. Re factor the code. */
4050 /**
4051  * FIXME: Should we call this function everywhere in all the handle functions
4052  * where we have a trail to verify from or a trail id. something like
4053  * if prev hop is not same then drop the message. 
4054  * Check if sender_peer and peer from which we should receive the message are
4055  * same or different.
4056  * @param trail_peer_list List of peers in trail
4057  * @param trail_length Total number of peers in @a trail_peer_list
4058  * @param sender_peer Peer from which we got the message. 
4059  * @param finger_identity Finger to which trail is setup. It is not part of trail.
4060  * @return #GNUNET_YES if sender_peer and peer from which we should receive the
4061  *                    message are different.
4062  *         #GNUNET_NO if sender_peer and peer from which we should receive the
4063  *                    message are different. 
4064  */
4065 static int
4066 is_sender_peer_correct (const struct GNUNET_PeerIdentity *trail_peer_list,
4067                         unsigned int trail_length,
4068                         const struct GNUNET_PeerIdentity *sender_peer,
4069                         struct GNUNET_PeerIdentity finger_identity,
4070                         struct GNUNET_PeerIdentity source_peer)
4071 {
4072   int my_index;
4073   
4074   /* I am the source peer. */
4075   if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4076                                              &my_identity)))
4077   {
4078     /* Is the first element of the trail is sender_peer.*/
4079     if (trail_length > 0)
4080     {
4081       if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4082                                                 sender_peer))
4083         return GNUNET_NO;
4084     }
4085     else
4086     {
4087       /* Is finger the sender peer? */
4088       if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4089                                                 &finger_identity))
4090         return GNUNET_NO;
4091     }
4092   }
4093   else
4094   {
4095     /* Get my current location in the trail. */
4096     my_index = search_my_index (trail_peer_list, trail_length);
4097     if (-1 == my_index)
4098       return GNUNET_NO;
4099     
4100     /* I am the last element in the trail. */
4101     if ((trail_length - 1) == my_index)
4102     {
4103       /* Is finger the sender_peer? */
4104       if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4105                                                 &finger_identity))
4106         return GNUNET_NO;
4107     }
4108     else
4109     {
4110       /* Is peer after me in trail the sender peer? */
4111       if (0 != GNUNET_CRYPTO_cmp_peer_identity (sender_peer,
4112                                                 &trail_peer_list[my_index + 1]))
4113         return GNUNET_NO;
4114     }
4115   }
4116   return GNUNET_YES;
4117 }
4118 #endif
4119
4120
4121 /**
4122  * FIXME: we should also add a case where we search if we are present in the trail
4123  * twice.
4124  * Core handle for p2p trail setup result messages.
4125  * @param closure
4126  * @param message message
4127  * @param peer sender of this message. 
4128  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4129  */
4130 static int
4131 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
4132                                   const struct GNUNET_MessageHeader *message)
4133 {
4134   const struct PeerTrailSetupResultMessage *trail_result;
4135   const struct GNUNET_PeerIdentity *trail_peer_list;
4136   struct GNUNET_PeerIdentity next_hop;
4137   struct FriendInfo *target_friend;
4138   struct GNUNET_PeerIdentity querying_peer;
4139   struct GNUNET_PeerIdentity finger_identity;
4140   uint32_t trail_length;
4141   uint64_t ulitmate_destination_finger_value;
4142   uint32_t is_predecessor;
4143   struct GNUNET_HashCode trail_id;
4144   int my_index;
4145   size_t msize;
4146
4147   msize = ntohs (message->size);
4148   if (msize < sizeof (struct PeerTrailSetupResultMessage))
4149   {
4150     GNUNET_break_op (0);
4151     return GNUNET_YES;
4152   }
4153
4154   trail_result = (const struct PeerTrailSetupResultMessage *) message;
4155   trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4156                   sizeof (struct GNUNET_PeerIdentity);
4157   if ((msize - sizeof (struct PeerTrailSetupResultMessage)) % 
4158       sizeof (struct GNUNET_PeerIdentity) != 0)
4159   {
4160     GNUNET_break_op (0);
4161     return GNUNET_OK;      
4162   }       
4163
4164   is_predecessor = ntohl (trail_result->is_predecessor);
4165   querying_peer = trail_result->querying_peer;
4166   finger_identity = trail_result->finger_identity;
4167   trail_id = trail_result->trail_id;
4168   trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4169   ulitmate_destination_finger_value = 
4170           GNUNET_ntohll (trail_result->ulitmate_destination_finger_value);
4171
4172   /* FIXME: here we are calculating my_index and comparing also in this function.
4173    And we are doing it again here in this function. Re factor the code. */
4174   /* Ensure that sender peer is the peer from which we were expecting the message. */
4175 #if 0
4176   if (GNUNET_NO == is_sender_peer_correct (trail_peer_list,
4177                                            trail_length,
4178                                            peer, finger_identity, querying_peer))
4179   {
4180     GNUNET_break_op (0);
4181     return GNUNET_SYSERR;
4182   }
4183 #endif
4184   
4185   /* Am I the one who initiated the query? */
4186   if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4187   {
4188     /* If I am not my own finger identity, then add routing table entry. */
4189     if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
4190     {
4191       GDS_ROUTING_add (trail_id, my_identity, *peer);
4192     }
4193    
4194     finger_table_add (finger_identity, trail_peer_list, trail_length,
4195                       is_predecessor, ulitmate_destination_finger_value, trail_id);
4196     return GNUNET_YES;
4197   }
4198   
4199   /* Get my location in the trail. */
4200   my_index = search_my_index (trail_peer_list, trail_length);
4201   if (-1 == my_index)
4202   {
4203     GNUNET_break_op(0);
4204     return GNUNET_SYSERR;
4205   }
4206   
4207   if (my_index == 0)
4208     next_hop = trail_result->querying_peer;
4209   else
4210     next_hop = trail_peer_list[my_index - 1];
4211   
4212   if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->querying_peer),
4213                                              &(trail_result->finger_identity))))
4214   {
4215     GDS_ROUTING_add (trail_id, next_hop, *peer);
4216   }
4217
4218   GNUNET_assert (NULL != 
4219                 (target_friend = 
4220                  GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
4221   GDS_NEIGHBOURS_send_trail_setup_result (querying_peer, finger_identity,
4222                                           target_friend, trail_length, trail_peer_list,
4223                                           is_predecessor, 
4224                                           ulitmate_destination_finger_value,
4225                                           trail_id);
4226   return GNUNET_OK;
4227 }
4228
4229
4230 /**
4231  * Invert the trail.
4232  * @param trail Trail to be inverted
4233  * @param trail_length Total number of peers in the trail.
4234  * @return Updated trail
4235  */
4236 static struct GNUNET_PeerIdentity *
4237 invert_trail (const struct GNUNET_PeerIdentity *trail,
4238               unsigned int trail_length)
4239 {
4240   int i;
4241   int j;
4242   struct GNUNET_PeerIdentity *inverted_trail;
4243
4244   inverted_trail = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity) *
4245                                   trail_length);
4246   i = 0;
4247   j = trail_length - 1;
4248   while (i < trail_length)
4249   {
4250     inverted_trail[i] = trail[j];
4251     i++;
4252     j--;
4253   }
4254   
4255   GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4256                                                           &inverted_trail[0]));
4257   return inverted_trail;
4258 }
4259
4260
4261 /**
4262  * Return the shortest trail among all the trails to reach to finger from me.
4263  * @param finger Finger 
4264  * @param shortest_trail_length[out] Trail length of shortest trail from me
4265  *                                   to @a finger
4266  * @return Shortest trail. 
4267  */
4268 static struct GNUNET_PeerIdentity *
4269 get_shortest_trail (struct FingerInfo *finger,
4270                     unsigned int *trail_length)
4271 {
4272   struct Trail *trail;
4273   unsigned int flag = 0;
4274   unsigned int shortest_trail_index = 0;
4275   int shortest_trail_length = -1;
4276   struct Trail_Element *trail_element;
4277   struct GNUNET_PeerIdentity *trail_list;
4278   unsigned int i;
4279   
4280   trail = GNUNET_new (struct Trail);
4281   
4282   /* Get the shortest trail to reach to current successor. */
4283   for (i = 0; i < finger->trails_count; i++)
4284   {
4285     trail = &finger->trail_list[i];
4286    
4287     if (0 == flag)
4288     {
4289       shortest_trail_index = i;
4290       shortest_trail_length = trail->trail_length; 
4291       flag = 1;
4292       continue;
4293     }
4294     
4295     if (shortest_trail_length > trail->trail_length)
4296     {
4297       shortest_trail_index = i;
4298       shortest_trail_length = trail->trail_length;
4299     }
4300     continue;
4301   }
4302   
4303   /* Copy the shortest trail and return. */
4304   trail = &finger->trail_list[shortest_trail_index];
4305   trail_element = trail->trail_head;
4306   trail_list = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4307                               shortest_trail_length);
4308   
4309   for(i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4310   {
4311     trail_list[i] = trail_element->peer; 
4312   }
4313   
4314   GNUNET_assert(shortest_trail_length != -1);
4315   
4316   *trail_length = shortest_trail_length;
4317   return trail_list;
4318 }
4319
4320
4321 /**
4322  * Return the trail from source to my current predecessor. Check if source
4323  * is already part of the this trail, if yes then return the shorten trail. 
4324  * @param current_trail Trail from source to me, NOT including the endpoints.
4325  * @param current_trail_length Number of peers in @a current_trail.
4326  * @param trail_src_to_curr_pred_length[out] Number of peers in trail from 
4327  *                                           source to my predecessor, NOT including
4328  *                                           the endpoints.
4329  * @return Trail from source to my predecessor. 
4330  */
4331 static struct GNUNET_PeerIdentity *
4332 get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4333                             const struct GNUNET_PeerIdentity *trail_src_to_me,
4334                             unsigned int trail_src_to_me_len,
4335                             unsigned int *trail_src_to_curr_pred_length)
4336 {
4337   struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4338   struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4339   unsigned int trail_me_to_curr_pred_length;
4340   struct FingerInfo *current_predecessor;
4341   unsigned int i;
4342   unsigned int j;
4343   
4344   current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4345   trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4346                                               &trail_me_to_curr_pred_length);
4347     
4348   /* Check if trail_me_to_curr_pred contains source. */
4349   if (trail_me_to_curr_pred_length > 0)
4350   {
4351     for(i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4352     {
4353       if(0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4354                                                &trail_me_to_curr_pred[i]))
4355         continue;
4356        
4357        i = i+1;
4358       
4359       /* Source is the last element in the trail to reach to my pred. 
4360          Source is direct friend of the pred. */
4361       if (trail_me_to_curr_pred_length == i)
4362       {
4363         *trail_src_to_curr_pred_length = 0;
4364         return NULL;
4365       }
4366       
4367       *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4368       trail_src_to_curr_pred = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4369                                               *trail_src_to_curr_pred_length);
4370       for(j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4371       {
4372         trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4373       }
4374       
4375       return trail_src_to_curr_pred;
4376     }
4377   }
4378   
4379   /* Append trail from source to me to my current_predecessor. */
4380   *trail_src_to_curr_pred_length = trail_src_to_me_len +
4381                                    trail_me_to_curr_pred_length + 1;
4382
4383   trail_src_to_curr_pred = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4384                                           *trail_src_to_curr_pred_length);
4385   
4386   for (i = 0; i < trail_src_to_me_len; i++)
4387     trail_src_to_curr_pred[i] = trail_src_to_me[i];
4388   
4389   trail_src_to_curr_pred[i] = my_identity;
4390   i++;
4391   
4392   for (j = 0; i < *trail_src_to_curr_pred_length; i++,j++)
4393     trail_src_to_curr_pred[i] = trail_me_to_curr_pred[j];
4394  
4395   return trail_src_to_curr_pred;
4396 }
4397
4398
4399 /**
4400  * Add finger as your predecessor. To add, first generate a new trail id, invert
4401  * the trail to get the trail from me to finger, add an entry in your routing 
4402  * table, send add trail message to peers which are part of trail from me to 
4403  * finger and add finger in finger table.
4404  * @param finger
4405  * @param trail
4406  * @param trail_length
4407  */
4408 static void
4409 update_predecessor (struct GNUNET_PeerIdentity finger, 
4410                     struct GNUNET_PeerIdentity *trail, 
4411                     unsigned int trail_length)
4412 {
4413   struct GNUNET_HashCode trail_to_new_predecessor_id;
4414   struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4415   struct FriendInfo *target_friend;
4416   
4417   /* Generate trail id for trail from me to new predecessor = finger. */
4418   GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4419                               &trail_to_new_predecessor_id, 
4420                               sizeof (trail_to_new_predecessor_id));
4421   
4422   /* Finger is a friend. */
4423   if (trail_length == 0)
4424   {
4425     trail_to_new_predecessor = NULL;
4426     GDS_ROUTING_add (trail_to_new_predecessor_id, my_identity, finger); 
4427     GNUNET_assert (NULL != (target_friend = 
4428                             GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4429                                                                &finger)));
4430   }
4431   else
4432   {
4433     /* Invert the trail to get the trail from me to finger, NOT including the
4434        endpoints.*/
4435     trail_to_new_predecessor = invert_trail (trail, trail_length);
4436   
4437     /* Add an entry in your routing table. */
4438     GDS_ROUTING_add (trail_to_new_predecessor_id, 
4439                      my_identity,
4440                      trail_to_new_predecessor[0]);
4441    
4442     GNUNET_assert (NULL != (target_friend = 
4443                    GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
4444                                                       &trail_to_new_predecessor[0])));
4445     GNUNET_assert (NULL != (
4446                    GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
4447                                                       &trail[trail_length - 1])));
4448   }
4449   
4450   /* Add entry in routing table of all peers that are part of trail from me
4451      to finger, including finger. */
4452   GDS_NEIGHBOURS_send_add_trail (my_identity, 
4453                                  finger,
4454                                  trail_to_new_predecessor_id,
4455                                  trail_to_new_predecessor,
4456                                  trail_length,
4457                                  target_friend);
4458
4459   add_new_finger (finger, trail_to_new_predecessor, trail_length,
4460                   trail_to_new_predecessor_id, PREDECESSOR_FINGER_ID);
4461   GNUNET_free_non_null (trail_to_new_predecessor);
4462 }
4463
4464
4465 /* 
4466  * Check if you already have a predecessor. If not then add finger as your
4467  * predecessor. If you have predecessor, then compare two peer identites.
4468  * If finger is correct predecessor, then remove the old entry, add finger in
4469  * finger table and send add_trail message to add the trail in the routing
4470  * table of all peers which are part of trail to reach from me to finger. 
4471  * @param finger New peer which may be our predecessor. 
4472  * @param trail List of peers to reach from @finger to me. 
4473  * @param trail_length Total number of peer in @a trail.
4474  */
4475 static void
4476 compare_and_update_predecessor (struct GNUNET_PeerIdentity finger, 
4477                                 struct GNUNET_PeerIdentity *trail, 
4478                                 unsigned int trail_length)
4479 {
4480   struct FingerInfo *current_predecessor;
4481   struct GNUNET_PeerIdentity *closest_peer;
4482   uint64_t predecessor_value;
4483   unsigned int is_predecessor = 1;
4484   
4485   current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4486   
4487   GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger, &my_identity));
4488   
4489   /* No predecessor. Add finger as your predecessor. */
4490   if (GNUNET_NO == current_predecessor->is_present) 
4491   {
4492     update_predecessor (finger, trail, trail_length);
4493     return;
4494   }
4495   
4496   if (0 == GNUNET_CRYPTO_cmp_peer_identity (&current_predecessor->finger_identity,
4497                                             &finger))
4498   {
4499     return;
4500   }
4501   
4502   predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4503   closest_peer = select_closest_peer (&finger, 
4504                                       &current_predecessor->finger_identity,
4505                                       predecessor_value, is_predecessor);
4506   
4507   /* Finger is the closest predecessor. Remove the existing one and add the new
4508      one. */
4509   if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer, &finger))
4510   {
4511     remove_existing_finger (current_predecessor, PREDECESSOR_FINGER_ID);
4512     update_predecessor (finger, trail, trail_length);
4513     return;
4514   }
4515   return;
4516 }
4517
4518
4519 /* 
4520  * Core handle for p2p verify successor messages.
4521  * @param cls closure
4522  * @param message message
4523  * @param peer peer identity this notification is about
4524  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4525  */
4526 static int
4527 handle_dht_p2p_verify_successor(void *cls, 
4528                                 const struct GNUNET_PeerIdentity *peer,
4529                                 const struct GNUNET_MessageHeader *message)
4530 {
4531   const struct PeerVerifySuccessorMessage *vsm;
4532   struct GNUNET_HashCode trail_id;
4533   struct GNUNET_PeerIdentity successor;
4534   struct GNUNET_PeerIdentity source_peer;
4535   struct GNUNET_PeerIdentity *trail;
4536   struct GNUNET_PeerIdentity *next_hop;
4537   struct FingerInfo *current_predecessor;
4538   struct FriendInfo *target_friend;
4539   unsigned int trail_src_to_curr_pred_len = 0;
4540   struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4541   size_t msize;
4542   unsigned int trail_length;
4543   
4544   msize = ntohs (message->size);
4545   
4546   if (msize < sizeof (struct PeerVerifySuccessorMessage)) 
4547   {
4548     GNUNET_break_op (0);
4549     return GNUNET_YES;
4550   }
4551   
4552   vsm = (const struct PeerVerifySuccessorMessage *) message;
4553   trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4554                   sizeof (struct GNUNET_PeerIdentity);
4555   if ((msize - sizeof (struct PeerVerifySuccessorMessage)) % 
4556       sizeof (struct GNUNET_PeerIdentity) != 0)
4557   {
4558     GNUNET_break_op (0);
4559     return GNUNET_OK;      
4560   } 
4561   
4562   trail_id = vsm->trail_id;
4563   source_peer = vsm->source_peer;
4564   successor = vsm->successor;
4565   trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4566   
4567  
4568   /* I am NOT the successor of source_peer. Pass the message to next_hop on
4569    * the trail. */
4570   if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
4571   {
4572     next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
4573     if (NULL == next_hop)
4574     {
4575       GNUNET_break (0);
4576       return GNUNET_SYSERR;
4577     }
4578     GNUNET_assert (NULL != 
4579                   (target_friend = 
4580                    GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4581
4582     GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
4583                                                   trail_id, trail, trail_length,
4584                                                   target_friend);
4585     return GNUNET_OK;
4586   }
4587   
4588   /* I am the destination of this message. */
4589   
4590   /* Check if the source_peer could be our predecessor and if yes then update
4591    * it.  */
4592   compare_and_update_predecessor (source_peer, trail, trail_length);
4593   current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4594   
4595   /* Is source of this message NOT my predecessor. */
4596   if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&current_predecessor->finger_identity,
4597                                              &source_peer)))
4598   {
4599     trail_src_to_curr_pred = get_trail_src_to_curr_pred (source_peer,
4600                                                          trail,
4601                                                          trail_length,
4602                                                          &trail_src_to_curr_pred_len);    
4603   }
4604   else
4605   {
4606     trail_src_to_curr_pred_len = trail_length;
4607     int i;
4608     trail_src_to_curr_pred = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity)*trail_length);
4609     for(i = 0; i < trail_src_to_curr_pred_len; i++)
4610     {
4611       trail_src_to_curr_pred[i] = trail[i];
4612     }
4613
4614   }
4615   
4616   GNUNET_assert (NULL != 
4617                 (target_friend = 
4618                  GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
4619   GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
4620                                                current_predecessor->finger_identity,
4621                                                trail_id, trail_src_to_curr_pred,
4622                                                trail_src_to_curr_pred_len,
4623                                                GDS_ROUTING_DEST_TO_SRC,
4624                                                target_friend);
4625
4626   return GNUNET_OK;
4627 }
4628
4629
4630 /**
4631  * If the trail from me to my probable successor contains a friend not
4632  * at index 0, then we can shorten the trail.
4633  * @param probable_successor Peer which is our probable successor
4634  * @param trail_me_to_probable_successor Peers in path from me to my probable 
4635  *                                       successor, NOT including the endpoints.
4636  * @param trail_me_to_probable_successor_len Total number of peers in 
4637  *                                           @a trail_me_to_probable_succesor.
4638  * @return Updated trail, if any friend found.
4639  *         Else the trail_me_to_probable_successor. 
4640  */
4641 struct GNUNET_PeerIdentity *
4642 check_trail_me_to_probable_succ (struct GNUNET_PeerIdentity probable_successor,
4643                                  const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4644                                  unsigned int trail_me_to_probable_successor_len,
4645                                  unsigned int *trail_to_new_successor_length)
4646 {
4647   unsigned int i;
4648   unsigned int j;
4649   struct GNUNET_PeerIdentity *trail_to_new_successor;
4650     
4651   /* Probable successor is  a friend */
4652   if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
4653                                                  &probable_successor))
4654   {
4655     trail_to_new_successor = NULL;
4656     *trail_to_new_successor_length = 0;
4657     return trail_to_new_successor;
4658   }
4659   
4660   /* Is there any friend of yours in this trail. */
4661   if(trail_me_to_probable_successor_len > 1)
4662   {
4663     for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4664     {
4665       if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
4666                                                      &trail_me_to_probable_successor[i]))
4667         continue;
4668     
4669       j = 0;
4670       *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4671       trail_to_new_successor = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity)*
4672                                                 *trail_to_new_successor_length);
4673     
4674       for(j = 0;i < trail_me_to_probable_successor_len;i++,j++)    
4675       {
4676         trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4677       }
4678       return trail_to_new_successor;
4679     }
4680   }
4681   
4682   *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4683   trail_to_new_successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)*
4684                                           *trail_to_new_successor_length);
4685   
4686   for(i = 0; i < *trail_to_new_successor_length; i++)
4687     trail_to_new_successor[i] = trail_me_to_probable_successor[i];
4688   
4689   return trail_to_new_successor;
4690 }
4691
4692
4693 /**
4694  * Check if the peer which sent us verify successor result message is still ours
4695  * successor or not. If not, then compare existing successor and probable successor.
4696  * In case probable successor is the correct successor, remove the existing
4697  * successor. Add probable successor as new successor. Send notify new successor
4698  * message to new successor. 
4699  * @param curr_succ
4700  * @param probable_successor
4701  * @param trail
4702  * @param trail_length
4703  */
4704 static void
4705 compare_and_update_successor (struct GNUNET_PeerIdentity curr_succ,
4706                               struct GNUNET_PeerIdentity probable_successor,
4707                               const struct GNUNET_PeerIdentity *trail,
4708                               unsigned int trail_length)
4709 {
4710   struct FingerInfo *current_successor;
4711   struct GNUNET_PeerIdentity *closest_peer;
4712   struct GNUNET_HashCode trail_id;
4713   struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
4714   struct FriendInfo *target_friend;
4715   unsigned int trail_me_to_probable_succ_len;
4716   unsigned int is_predecessor = GNUNET_NO;
4717   uint64_t successor_value;
4718   
4719   current_successor = &finger_table[0];
4720   successor_value = compute_finger_identity_value(0);
4721   
4722   /* Have we found some other successor, while waiting for verify successor result. */
4723   if(0 != GNUNET_CRYPTO_cmp_peer_identity(&curr_succ, &current_successor->finger_identity))
4724   {
4725     /* We could have added this new successor, only if it was closer the old one. */
4726     closest_peer = select_closest_peer (&curr_succ,
4727                                         &current_successor->finger_identity,
4728                                         successor_value, is_predecessor);
4729     
4730     /* FIXME: it may fail in case we have done more number of iterations of
4731      find _finger_trail_task. */
4732     GNUNET_assert (0 == 
4733                    GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4734                                                     &current_successor->finger_identity));
4735     
4736   }
4737   
4738   closest_peer = select_closest_peer (&probable_successor,
4739                                       &current_successor->finger_identity,
4740                                       successor_value, is_predecessor);
4741   
4742   /* If the current_successor in the finger table is closest, then do nothing. */
4743   if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4744                                             &current_successor->finger_identity))
4745     return;
4746   
4747   /* Probable successor is the closest peer.*/
4748   if(trail_length > 0)
4749     GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4750                                                             &trail[0]));
4751   else
4752     GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get(friend_peermap,
4753                                                             &probable_successor));
4754   
4755   trail_me_to_probable_succ_len = 0;
4756   /* TODO: Check if the path to reach to probable successor contains a friend. */
4757   trail_me_to_probable_succ = 
4758           check_trail_me_to_probable_succ (probable_successor,
4759                                            trail, trail_length,
4760                                            &trail_me_to_probable_succ_len);
4761
4762   /* Remove the existing successor. */
4763   remove_existing_finger (current_successor, 0);
4764   
4765    /* Generate a new trail id to reach to your new successor. */
4766   GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4767                               &trail_id, sizeof (trail_id));
4768   
4769   if (trail_me_to_probable_succ_len > 0)
4770   {
4771     GDS_ROUTING_add (trail_id, my_identity, trail_me_to_probable_succ[0]);
4772     GNUNET_assert (NULL != 
4773                   (target_friend =
4774                       GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
4775                                                         &trail_me_to_probable_succ[0])));
4776   }
4777   else
4778   {
4779     GDS_ROUTING_add (trail_id, my_identity, probable_successor);
4780     GNUNET_assert (NULL != 
4781                   (target_friend = 
4782                    GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
4783                                                        &probable_successor)));
4784   }
4785   
4786   add_new_finger (probable_successor, trail_me_to_probable_succ, 
4787                   trail_me_to_probable_succ_len, trail_id, 0);
4788   
4789   GDS_NEIGHBOURS_send_notify_new_successor (my_identity, probable_successor,
4790                                             trail_me_to_probable_succ,
4791                                             trail_me_to_probable_succ_len,
4792                                             trail_id,
4793                                             target_friend);
4794   return;
4795 }
4796
4797
4798 /*
4799  * Core handle for p2p verify successor result messages.
4800  * @param cls closure
4801  * @param message message
4802  * @param peer peer identity this notification is about
4803  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4804  */
4805 static int
4806 handle_dht_p2p_verify_successor_result(void *cls, 
4807                                        const struct GNUNET_PeerIdentity *peer,
4808                                        const struct GNUNET_MessageHeader *message)
4809 {
4810   const struct PeerVerifySuccessorResultMessage *vsrm;
4811   enum GDS_ROUTING_trail_direction trail_direction;
4812   struct GNUNET_PeerIdentity querying_peer;
4813   struct GNUNET_HashCode trail_id;
4814   struct GNUNET_PeerIdentity *next_hop;
4815   struct FriendInfo *target_friend;
4816   struct GNUNET_PeerIdentity probable_successor;
4817   struct GNUNET_PeerIdentity current_successor;
4818   const struct GNUNET_PeerIdentity *trail;
4819   unsigned int trail_length;
4820   size_t msize;
4821
4822   msize = ntohs (message->size);
4823   /* We send a trail to reach from old successor to new successor, if
4824    * old_successor != new_successor.*/
4825   if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
4826   {
4827     GNUNET_break_op (0);
4828     return GNUNET_YES;
4829   }
4830   
4831   vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
4832   trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))/
4833                       sizeof (struct GNUNET_PeerIdentity);
4834   
4835   if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) % 
4836       sizeof (struct GNUNET_PeerIdentity) != 0)
4837   {
4838     GNUNET_break_op (0);
4839     return GNUNET_OK;      
4840   }  
4841   
4842   trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
4843   querying_peer = vsrm->querying_peer;
4844   trail_direction = ntohl (vsrm->trail_direction);
4845   trail_id = vsrm->trail_id;
4846   probable_successor = vsrm->probable_successor;
4847   current_successor = vsrm->current_successor;
4848
4849   /* I am the querying_peer. */
4850   if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer, &my_identity)))
4851   {
4852     compare_and_update_successor (current_successor,
4853                                   probable_successor, trail, trail_length);
4854     return GNUNET_OK;
4855   }
4856   
4857   /*If you are not the querying peer then pass on the message */
4858   GNUNET_assert (NULL != (next_hop =
4859                          GDS_ROUTING_get_next_hop (trail_id, trail_direction)));
4860   GNUNET_assert (NULL != 
4861                 (target_friend = 
4862                  GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
4863   GDS_NEIGHBOURS_send_verify_successor_result (querying_peer,
4864                                                vsrm->current_successor,
4865                                                probable_successor, trail_id,
4866                                                trail,
4867                                                trail_length,
4868                                                trail_direction, target_friend);
4869   return GNUNET_OK;
4870 }
4871
4872
4873 /* 
4874  * Core handle for p2p notify new successor messages.
4875  * @param cls closure
4876  * @param message message
4877  * @param peer peer identity this notification is about
4878  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4879  */
4880 static int
4881 handle_dht_p2p_notify_new_successor(void *cls, 
4882                                     const struct GNUNET_PeerIdentity *peer,
4883                                     const struct GNUNET_MessageHeader *message)
4884 {
4885   const struct PeerNotifyNewSuccessorMessage *nsm;
4886   struct GNUNET_PeerIdentity *trail;
4887   struct GNUNET_PeerIdentity source;
4888   struct GNUNET_PeerIdentity new_successor;
4889   struct GNUNET_HashCode trail_id;
4890   struct GNUNET_PeerIdentity next_hop;
4891   struct FriendInfo *target_friend;
4892   int my_index;
4893   size_t msize;
4894   uint32_t trail_length;
4895
4896   msize = ntohs (message->size);
4897   
4898   /* We have the trail to reach from source to new successor. */
4899   if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
4900   {
4901     GNUNET_break_op (0);
4902     return GNUNET_YES;
4903   }
4904
4905   nsm = (const struct PeerNotifyNewSuccessorMessage *) message;
4906   trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
4907                   sizeof (struct GNUNET_PeerIdentity);
4908   if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) % 
4909       sizeof (struct GNUNET_PeerIdentity) != 0)
4910   {
4911     GNUNET_break_op (0);
4912     return GNUNET_OK;      
4913   }
4914   
4915   trail = (struct GNUNET_PeerIdentity *) &nsm[1];
4916   source  = nsm->source_peer;
4917   new_successor = nsm->new_successor;
4918   trail_id = nsm->trail_id;  
4919
4920   //FIXME: add a check to make sure peer is correct. 
4921   
4922   /* I am the new_successor to source_peer. */
4923   if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &new_successor))
4924   {
4925     GDS_ROUTING_add (trail_id, *peer, my_identity);
4926     compare_and_update_predecessor (source, trail, trail_length);
4927     return GNUNET_OK;
4928   }
4929   
4930   GNUNET_assert(trail_length > 0);
4931   /* I am part of trail to reach to successor. */
4932   my_index = search_my_index (trail, trail_length);
4933   if (-1 == my_index) 
4934   {
4935     GNUNET_break_op (0);
4936     return GNUNET_SYSERR;
4937   }
4938  
4939   if ((trail_length-1) == my_index) //FIXMe: SHOULD IT BE TRAIL_LENGTH - 1.s
4940     next_hop = new_successor;
4941   else
4942     next_hop = trail[my_index + 1];
4943  
4944
4945   /* Add an entry in routing table for trail from source to its new successor. */
4946   GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, next_hop));
4947
4948   GNUNET_assert (NULL != 
4949                 (target_friend = 
4950                  GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
4951   GDS_NEIGHBOURS_send_notify_new_successor (source, new_successor, trail,
4952                                             trail_length,
4953                                             trail_id, target_friend);
4954   return GNUNET_OK;
4955   
4956 }
4957
4958
4959 /**
4960  * Core handler for P2P trail rejection message
4961  * @param cls closure
4962  * @param message message
4963  * @param peer peer identity this notification is about
4964  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4965  */
4966 static int
4967 handle_dht_p2p_trail_setup_rejection (void *cls,
4968                                       const struct GNUNET_PeerIdentity *peer,
4969                                       const struct GNUNET_MessageHeader *message)
4970 {
4971   const struct PeerTrailRejectionMessage *trail_rejection;
4972   unsigned int trail_length;
4973   const struct GNUNET_PeerIdentity *trail_peer_list;
4974   struct FriendInfo *target_friend;
4975   struct GNUNET_TIME_Relative congestion_timeout;
4976   struct GNUNET_HashCode trail_id;
4977   struct GNUNET_PeerIdentity next_peer;
4978   struct GNUNET_PeerIdentity source;
4979   struct GNUNET_PeerIdentity *next_hop;
4980   uint64_t ultimate_destination_finger_value;
4981   unsigned int is_predecessor;
4982   size_t msize;
4983
4984   msize = ntohs (message->size);
4985   /* We are passing the trail setup so far. */
4986   if (msize < sizeof (struct PeerTrailRejectionMessage))
4987   {
4988     GNUNET_break_op (0);
4989     return GNUNET_YES;
4990   }
4991   
4992   trail_rejection = (const struct PeerTrailRejectionMessage *) message;
4993   trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
4994                   sizeof (struct GNUNET_PeerIdentity);
4995   if ((msize - sizeof (struct PeerTrailRejectionMessage)) % 
4996       sizeof (struct GNUNET_PeerIdentity) != 0)
4997   {
4998     GNUNET_break_op (0);
4999     return GNUNET_OK;      
5000   }           
5001
5002   trail_peer_list = (const struct GNUNET_PeerIdentity *)&trail_rejection[1];
5003   is_predecessor = ntohl (trail_rejection->is_predecessor);
5004   congestion_timeout = trail_rejection->congestion_time;
5005   source = trail_rejection->source_peer;
5006   trail_id = trail_rejection->trail_id;
5007   ultimate_destination_finger_value = 
5008           GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5009
5010   /* First set the congestion time of the friend that sent you this message. */
5011   GNUNET_assert (NULL != 
5012                  (target_friend = 
5013                   GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5014   target_friend->congestion_timestamp = 
5015           GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5016                                     congestion_timeout);
5017
5018   /* I am the source peer which wants to setup the trail. Do nothing. 
5019    * send_find_finger_trail_task is scheduled periodically.*/
5020   if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5021     return GNUNET_OK;
5022
5023   /* If I am congested then pass this message to peer before me in trail. */
5024   if(GNUNET_YES == GDS_ROUTING_threshold_reached())
5025   {
5026     struct GNUNET_PeerIdentity *new_trail;
5027     unsigned int new_trail_length;
5028     
5029     /* Remove yourself from the trail setup so far. */
5030     if (trail_length == 1)
5031     {
5032       new_trail = NULL;
5033       new_trail_length = 0;
5034       next_hop = &source;
5035     }
5036     else
5037     {
5038       memcpy (&next_hop , &trail_peer_list[trail_length - 2], 
5039               sizeof (struct GNUNET_PeerIdentity));
5040       
5041       /* Remove myself from the trail. */
5042       new_trail_length = trail_length -1;
5043       new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5044       memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
5045     }
5046
5047     GNUNET_assert (NULL != 
5048                   (target_friend = 
5049                     GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5050     GDS_NEIGHBOURS_send_trail_rejection (source,
5051                                          ultimate_destination_finger_value,
5052                                          my_identity, is_predecessor,
5053                                          new_trail,new_trail_length,trail_id,
5054                                          target_friend, CONGESTION_TIMEOUT);
5055     GNUNET_free (new_trail);
5056     return GNUNET_OK;
5057   }
5058   
5059   struct Closest_Peer successor;
5060   successor = find_successor (ultimate_destination_finger_value, is_predecessor);
5061   
5062   /* Am I the final destination? */
5063   if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination, 
5064                                              &my_identity)))
5065   {
5066     if (0 == trail_length)
5067       next_peer = source;
5068     else
5069       next_peer = trail_peer_list[trail_length-1];
5070     
5071     GNUNET_assert (NULL != 
5072                   (target_friend = 
5073                    GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer)));
5074     
5075     GDS_NEIGHBOURS_send_trail_setup_result (source,
5076                                             my_identity,
5077                                             target_friend, trail_length,
5078                                             trail_peer_list,
5079                                             is_predecessor, 
5080                                             ultimate_destination_finger_value,
5081                                             trail_id);
5082   }
5083   else
5084   {
5085     struct GNUNET_PeerIdentity peer_list[trail_length + 1];
5086
5087     memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
5088     peer_list[trail_length] = my_identity;
5089
5090     GNUNET_assert (NULL != 
5091                   (target_friend = 
5092                    GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5093
5094     GDS_NEIGHBOURS_send_trail_setup (source,
5095                                      ultimate_destination_finger_value,
5096                                      successor.best_known_destination,
5097                                      target_friend, trail_length + 1, peer_list,
5098                                      is_predecessor, trail_id,
5099                                      successor.trail_id);
5100   }
5101   return GNUNET_OK;
5102 }
5103
5104
5105 /*
5106  * Core handle for p2p trail tear compression messages.
5107  * @param cls closure
5108  * @param message message
5109  * @param peer peer identity this notification is about
5110  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5111  */
5112 static int
5113 handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
5114                                   const struct GNUNET_MessageHeader *message)
5115 {
5116   const struct PeerTrailCompressionMessage *trail_compression;
5117   struct GNUNET_PeerIdentity *next_hop;
5118   struct FriendInfo *target_friend;
5119   struct GNUNET_HashCode trail_id;
5120   size_t msize;
5121
5122   msize = ntohs (message->size);
5123
5124   if (msize != sizeof (struct PeerTrailCompressionMessage))
5125   {
5126     GNUNET_break_op (0);
5127     return GNUNET_OK;
5128   }
5129   
5130   trail_compression = (const struct PeerTrailCompressionMessage *) message;
5131   trail_id = trail_compression->trail_id;
5132  
5133   /* Am I the new first friend to reach to finger of this trail. */
5134   if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&trail_compression->new_first_friend,
5135                                              &my_identity)))
5136   {
5137     GNUNET_assert (NULL != 
5138                   (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5139                                                       &trail_compression->source_peer)));
5140     
5141     /* Update your prev hop to source of this message. */
5142     GNUNET_assert (GNUNET_SYSERR != 
5143                   (GDS_ROUTING_update_trail_prev_hop (trail_id,
5144                                                       trail_compression->source_peer)));
5145     return GNUNET_OK;
5146   }
5147   
5148   /* Pass the message to next hop to finally reach to new_first_friend. */
5149   next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
5150   
5151   if (NULL == next_hop) 
5152   {
5153     GNUNET_break (0); 
5154     return GNUNET_OK;
5155   }
5156   
5157   GNUNET_assert (NULL != 
5158                 (target_friend = 
5159                  GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)));
5160   
5161   GDS_ROUTING_remove_trail (trail_id);
5162   
5163   GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
5164                                          trail_id,
5165                                          trail_compression->new_first_friend,
5166                                          target_friend);
5167   return GNUNET_OK;
5168 }
5169
5170
5171 /**
5172  * Core handler for trail teardown message.
5173  * @param cls closure
5174  * @param message message
5175  * @param peer sender of this messsage. 
5176  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5177  */
5178 static int
5179 handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
5180                                const struct GNUNET_MessageHeader *message)
5181 {
5182   const struct PeerTrailTearDownMessage *trail_teardown;
5183   enum GDS_ROUTING_trail_direction trail_direction;
5184   struct GNUNET_HashCode trail_id;
5185   struct GNUNET_PeerIdentity *next_hop;
5186   size_t msize;
5187   
5188   msize = ntohs (message->size);
5189   
5190   /* Here we pass only the trail id. */
5191   if (msize != sizeof (struct PeerTrailTearDownMessage))
5192   {
5193     GNUNET_break_op (0);
5194     return GNUNET_OK;
5195   }
5196   
5197   trail_teardown = (const struct PeerTrailTearDownMessage *) message;
5198   trail_direction = ntohl (trail_teardown->trail_direction);
5199   trail_id = trail_teardown->trail_id;
5200   
5201   /* Check if peer is the real peer from which we should get this message.*/
5202   /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5203   /* FIXME: is using negation of trail direction correct. */
5204 #if 0
5205   GNUNET_assert (NULL != (prev_hop = 
5206                  GDS_ROUTING_get_next_hop (trail_id, !trail_direction)));
5207   if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop, peer))
5208   {
5209     GNUNET_break (0);
5210     return GNUNET_SYSERR;
5211   }
5212 #endif
5213   
5214   next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
5215   
5216   if (NULL == next_hop)
5217   {
5218     GNUNET_break (0);
5219     return GNUNET_SYSERR;
5220   }
5221  
5222   /* I am the next hop, which means I am the final destination. */
5223   if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5224   {
5225     GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5226     return GNUNET_OK;
5227   }
5228   else 
5229   {
5230     /* If not final destination, then send a trail teardown message to next hop.*/
5231     GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop));
5232     GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5233     GDS_NEIGHBOURS_send_trail_teardown (trail_id, trail_direction, *next_hop);
5234   }
5235   
5236   return GNUNET_OK;
5237 }
5238
5239
5240 /**
5241  * Core handle for p2p add trail message. 
5242  * @param cls closure
5243  * @param message message
5244  * @param peer peer identity this notification is about
5245  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5246  */
5247 static int
5248 handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
5249                           const struct GNUNET_MessageHeader *message)
5250 {
5251   const struct PeerAddTrailMessage *add_trail;
5252   const struct GNUNET_PeerIdentity *trail;
5253   struct GNUNET_HashCode trail_id;
5254   struct GNUNET_PeerIdentity destination_peer;
5255   struct GNUNET_PeerIdentity source_peer;
5256   struct GNUNET_PeerIdentity next_hop;
5257   unsigned int trail_length;
5258   unsigned int my_index;
5259   size_t msize;
5260
5261   msize = ntohs (message->size);
5262   /* In this message we pass the whole trail from source to destination as we
5263    * are adding that trail.*/
5264   if (msize < sizeof (struct PeerAddTrailMessage))
5265   {
5266     GNUNET_break_op (0);
5267     return GNUNET_OK;
5268   }
5269
5270   add_trail = (const struct PeerAddTrailMessage *) message;
5271   trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5272                   sizeof (struct GNUNET_PeerIdentity);
5273   if ((msize - sizeof (struct PeerAddTrailMessage)) % 
5274       sizeof (struct GNUNET_PeerIdentity) != 0)
5275   {
5276     GNUNET_break_op (0);
5277     return GNUNET_OK;      
5278   }           
5279
5280   trail = (const struct GNUNET_PeerIdentity *)&add_trail[1];
5281   destination_peer = add_trail->destination_peer;
5282   source_peer = add_trail->source_peer;
5283   trail_id = add_trail->trail_id;
5284
5285   //FIXME: add a check that sender peer is not malicious. Make it a generic
5286   // function so that it can be used in all other functions where we need the
5287   // same functionality.
5288   
5289   /* I am not the destination of the trail. */
5290   if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &destination_peer))
5291   {
5292     struct FriendInfo *target_friend;
5293    
5294     /* Get my location in the trail. */
5295     my_index = search_my_index (trail, trail_length);
5296     if (-1 == my_index)
5297     {
5298       
5299       GNUNET_break_op (0);
5300       return GNUNET_SYSERR;
5301     }
5302     
5303     
5304     if ((trail_length - 1) == my_index)
5305     { 
5306       
5307       next_hop = destination_peer;
5308     }
5309     else
5310     {
5311       next_hop = trail[my_index + 1];
5312     }
5313     /* FIXME: check that you always add trail entry even if your finger is 
5314      friend. */
5315     /* Add in your routing table. */
5316     GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5317     GNUNET_assert (NULL != 
5318                   (target_friend = 
5319                    GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop)));
5320     GDS_NEIGHBOURS_send_add_trail (source_peer, destination_peer, trail_id,
5321                                    trail, trail_length, target_friend);
5322     return GNUNET_OK;
5323   }
5324   /* FIXME: check that you always add trail entry even if your finger is 
5325      friend. */
5326   /* I am the destination. Add an entry in routing table. */
5327   GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, *peer, my_identity));
5328   return GNUNET_OK;
5329 }
5330
5331
5332 /**
5333  * Free the finger trail in which the first friend to reach to a finger is 
5334  * disconnected_friend. Also remove entry from routing table for that particular
5335  * trail id. 
5336  * @param disconnected_friend PeerIdentity of friend which got disconnected
5337  * @param remove_finger Finger whose trail we need to check if it has 
5338  *                      disconnected_friend as the first hop.
5339  * @return Total number of trails in which disconnected_friend was the first
5340  *         hop.
5341  */
5342 static int
5343 remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5344                         struct FingerInfo *remove_finger)
5345 {
5346   unsigned int matching_trails_count;
5347   int i;
5348   
5349   /* Number of trails with disconnected_friend as the first hop in the trail
5350    * to reach from me to remove_finger, NOT including endpoints. */
5351   matching_trails_count = 0;
5352   
5353   /* Iterate over all the trails of finger. */
5354   for (i = 0; i < remove_finger->trails_count; i++)
5355   {
5356     struct Trail *trail;
5357     trail = &remove_finger->trail_list[i];
5358     
5359     /* This assertion is ensure that there are no gaps in the trail list. 
5360      REMOVE IT AFTERWARDS. */
5361     GNUNET_assert (GNUNET_YES == trail->is_present);
5362     
5363     /* First friend to reach to finger is disconnected_peer. */
5364     if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail->trail_head->peer,
5365                                               disconnected_friend))
5366     {
5367       struct GNUNET_PeerIdentity *next_hop;
5368       struct FriendInfo *remove_friend;
5369       
5370       GNUNET_assert (NULL != 
5371                     (remove_friend = 
5372                      GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
5373                                                         disconnected_friend)));
5374       /* FIXME: removing no but check it. */
5375       //remove_friend->trails_count--;
5376       next_hop = GDS_ROUTING_get_next_hop (trail->trail_id, 
5377                                            GDS_ROUTING_SRC_TO_DEST);
5378       
5379       /* Here it may happen that as all the peers got disconnected, the entry in
5380        routing table for that particular trail has been removed, because the
5381        previously disconnected peer was either a next hop or prev hop of that
5382        peer. */
5383       if (NULL == next_hop)
5384         continue;
5385       
5386       GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5387                                                             next_hop)));
5388       matching_trails_count++;
5389       GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail->trail_id));
5390       
5391       free_trail (trail);
5392       trail->is_present = GNUNET_NO;
5393     }
5394   }  
5395   return matching_trails_count;
5396 }
5397
5398
5399 /**
5400  * Iterate over finger_table entries. 
5401  * 0. Ignore finger which is my_identity or if no valid entry present at 
5402  *    that finger index. 
5403  * 1. If disconnected_friend is a finger, then remove the routing entry from
5404       your own table. Free the trail. 
5405  * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5406  *   2.1 Remove all the trails and entry from routing table in which disconnected 
5407  *       friend is the first friend in the trail. If disconnected_friend is the 
5408  *       first friend in all the trails to reach finger, then remove the finger. 
5409  * @param disconnected_friend Peer identity of friend which got disconnected.
5410  */
5411 static void
5412 remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5413 {
5414   struct FingerInfo *remove_finger;
5415   struct FriendInfo *remove_friend;
5416   int removed_trails_count;
5417   int i;
5418   
5419   /* Iterate over finger table entries. */
5420   for (i = 0; i < MAX_FINGERS; i++)
5421   {
5422     remove_finger = &finger_table[i];
5423
5424     /* No finger stored at this trail index. */
5425     if (GNUNET_NO == remove_finger->is_present)
5426       continue;
5427     
5428     /* I am my own finger, then ignore this finger. */
5429     if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
5430                                               &my_identity))
5431       continue;
5432     
5433     /* Is disconnected_peer a finger? */
5434     if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5435                                               &remove_finger->finger_identity))
5436     {
5437       struct GNUNET_PeerIdentity *next_hop;
5438       struct GNUNET_HashCode trail_id;
5439       
5440       
5441       GNUNET_assert (GNUNET_YES == (remove_finger->trail_list[0].is_present));
5442       trail_id = remove_finger->trail_list[0].trail_id;
5443      
5444       if(NULL != 
5445               (next_hop = 
5446                GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST)))
5447       {
5448         /* FIXME: This assertion fails check why*/
5449         GNUNET_assert (0 ==
5450                       (GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5451                                                         &remove_finger->finger_identity)));
5452         GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
5453         GNUNET_assert (NULL !=
5454                        (remove_friend = 
5455                         GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
5456                                                            disconnected_peer)));
5457       }
5458       
5459       remove_finger->trail_list[0].is_present = GNUNET_NO;
5460       //GNUNET_assert (0 != remove_friend->trails_count);
5461       //remove_friend->trails_count--; //FIXME; CHECK WHY IT FAILS AND THEN UNCOMMENT.
5462       remove_finger->is_present = GNUNET_NO;
5463       memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5464       continue;
5465     }
5466     
5467     /* If finger is a friend but not disconnected_friend, then continue. */
5468     if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, 
5469                                                    &remove_finger->finger_identity))
5470       continue;
5471     
5472     /* Iterate over the list of trails to reach remove_finger. Check if 
5473      * disconnected_friend is the first friend in any of the trail. */
5474     removed_trails_count = remove_matching_trails (disconnected_peer, 
5475                                                    remove_finger);
5476     remove_finger->trails_count = 
5477             remove_finger->trails_count - removed_trails_count;
5478     /* All the finger trails had disconnected_friend as the first friend,
5479      * so free the finger. */
5480     if (remove_finger->trails_count == 0)
5481     {
5482       remove_finger->is_present = GNUNET_NO;
5483       memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5484     }      
5485   }
5486 }
5487
5488
5489 /**
5490  * Method called whenever a peer disconnects.
5491  *
5492  * @param cls closure
5493  * @param peer peer identity this notification is about
5494  */
5495 static void
5496 handle_core_disconnect (void *cls,
5497                                           const struct GNUNET_PeerIdentity *peer)
5498 {
5499   struct FriendInfo *remove_friend;
5500
5501   /* If disconnected to own identity, then return. */
5502   if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
5503     return;
5504
5505   GNUNET_assert (NULL != (remove_friend =
5506                           GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer)));
5507
5508   /* Remove fingers with peer as first friend or if peer is a finger. */
5509   remove_matching_fingers (peer);
5510   
5511   /* Remove any trail from routing table of which peer is a part of. This function
5512    * internally sends a trail teardown message in the direction of which
5513    * disconnected peer is not part of. */
5514   GNUNET_assert (GNUNET_SYSERR != GDS_ROUTING_remove_trail_by_peer (peer));
5515   
5516   //GNUNET_assert (0 == remove_friend->trails_count); //FIXME; why should this fai.
5517   
5518   /* Remove peer from friend_peermap. */
5519   GNUNET_assert (GNUNET_YES ==
5520                  GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
5521                                                        peer,
5522                                                        remove_friend));
5523   
5524   if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
5525     return;
5526   
5527   if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5528   {
5529       GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5530       find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5531   }
5532   else
5533     GNUNET_break (0);
5534
5535 }
5536
5537
5538 /**
5539  * Method called whenever a peer connects.
5540  *
5541  * @param cls closure
5542  * @param peer_identity peer identity this notification is about
5543  */
5544 static void
5545 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
5546 {
5547   struct FriendInfo *friend;
5548
5549   /* Check for connect to self message */
5550   if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
5551     return;
5552
5553   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
5554
5555   /* If peer already exists in our friend_peermap, then exit. */
5556   if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, 
5557                                                             peer_identity))
5558   {
5559     GNUNET_break (0);
5560     return;
5561   }
5562
5563   GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
5564                             GNUNET_NO);
5565
5566   friend = GNUNET_new (struct FriendInfo);
5567   friend->id = *peer_identity;
5568
5569   GNUNET_assert (GNUNET_OK ==
5570                  GNUNET_CONTAINER_multipeermap_put (friend_peermap,
5571                                                     peer_identity, friend,
5572                                                     GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
5573
5574
5575   /* got a first connection, good time to start with FIND FINGER TRAIL requests...*/ 
5576   if (GNUNET_SCHEDULER_NO_TASK == find_finger_trail_task) 
5577     find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
5578 }
5579
5580
5581 /**
5582  * To be called on core init/fail.
5583  *
5584  * @param cls service closure
5585  * @param identity the public identity of this peer
5586  */
5587 static void
5588 core_init (void *cls,
5589            const struct GNUNET_PeerIdentity *identity)
5590 {
5591   my_identity = *identity;
5592   
5593   uint64_t my_id64;
5594   memcpy (&my_id64, &my_identity, sizeof (uint64_t));
5595   my_id64 = GNUNET_ntohll (my_id64);
5596   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
5597               "my_indentity = %s, my_id64=%llu\n",GNUNET_i2s(&my_identity),(unsigned long long)my_id64);
5598
5599 }
5600
5601
5602 /**
5603  * Initialize finger table entries.
5604  */
5605 static void
5606 finger_table_init ()
5607 {
5608   unsigned int i;
5609   unsigned int j;
5610  
5611   for(i = 0; i < MAX_FINGERS; i++)
5612   {
5613     finger_table[i].is_present = GNUNET_NO;
5614     for (j = 0; j < MAXIMUM_TRAILS_PER_FINGER; j++)
5615       finger_table[i].trail_list[j].is_present = GNUNET_NO;
5616     memset ((void *)&finger_table[i], 0, sizeof (finger_table[i]));
5617   }
5618 }
5619
5620
5621 /**
5622  * Initialize neighbours subsystem.
5623  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
5624  */
5625 int
5626 GDS_NEIGHBOURS_init (void)
5627 {
5628   static struct GNUNET_CORE_MessageHandler core_handlers[] = {
5629     {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT, 0},
5630     {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET, 0},
5631     {&handle_dht_p2p_get_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT, 0},
5632     {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP, 0},
5633     {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT, 0},
5634     {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR, 0},
5635     {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
5636     {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
5637     {&handle_dht_p2p_trail_setup_rejection, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION, 0},
5638     {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_COMPRESSION, 
5639                                         sizeof (struct PeerTrailCompressionMessage)},
5640     {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN, 
5641                                      sizeof (struct PeerTrailTearDownMessage)},
5642     {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL, 0},
5643     {NULL, 0, 0}
5644   };
5645
5646   core_api =
5647     GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
5648                          &handle_core_disconnect, NULL, GNUNET_NO, NULL,
5649                          GNUNET_NO, core_handlers);
5650   if (NULL == core_api)
5651     return GNUNET_SYSERR;
5652
5653   friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
5654   finger_table_init ();
5655   
5656   return GNUNET_OK;
5657 }
5658
5659
5660 /**
5661  * Shutdown neighbours subsystem.
5662  */
5663 void
5664 GDS_NEIGHBOURS_done (void)
5665 {
5666   if (NULL == core_api)
5667     return;
5668
5669   GNUNET_CORE_disconnect (core_api);
5670   core_api = NULL;
5671
5672   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
5673   GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
5674   friend_peermap = NULL;
5675
5676   if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
5677   {
5678     GNUNET_break (0);
5679     GNUNET_SCHEDULER_cancel (find_finger_trail_task);
5680     find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
5681   }
5682   
5683   if (GNUNET_SCHEDULER_NO_TASK != send_verify_successor_task)
5684   {
5685     GNUNET_SCHEDULER_cancel (send_verify_successor_task);
5686     send_verify_successor_task = GNUNET_SCHEDULER_NO_TASK;
5687   }
5688 }
5689
5690
5691 /**
5692  * Get my identity
5693  *
5694  * @return my identity
5695  */
5696 struct GNUNET_PeerIdentity
5697 GDS_NEIGHBOURS_get_my_id (void)
5698 {
5699   return my_identity;
5700 }
5701
5702 /* end of gnunet-service-xdht_neighbours.c */