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