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.c6261
1 files changed, 0 insertions, 6261 deletions
diff --git a/src/dht/gnunet-service-xdht_neighbours.c b/src/dht/gnunet-service-xdht_neighbours.c
deleted file mode 100644
index dd45d5a4b..000000000
--- a/src/dht/gnunet-service-xdht_neighbours.c
+++ /dev/null
@@ -1,6261 +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 bg group to filter duplicates
2305 * @param peer_bf filter for peers not to select (again, updated)
2306 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
2307 */
2308int
2309GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type block_type,
2310 enum GNUNET_DHT_RouteOption options,
2311 uint32_t desired_replication_level,
2312 uint32_t hop_count,
2313 const struct GNUNET_HashCode *key,
2314 const void *xquery,
2315 size_t xquery_size,
2316 struct GNUNET_BLOCK_Group *bg,
2317 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
2318{
2319 struct Closest_Peer successor;
2320 struct GNUNET_PeerIdentity best_known_dest;
2321 struct GNUNET_HashCode intermediate_trail_id;
2322 uint64_t key_value;
2323
2324 GNUNET_memcpy (&key_value,
2325 key,
2326 sizeof (uint64_t));
2327 key_value = GNUNET_ntohll (key_value);
2328 successor = find_local_best_known_next_hop (key_value,
2329 GDS_FINGER_TYPE_NON_PREDECESSOR);
2330 best_known_dest = successor.best_known_destination;
2331 intermediate_trail_id = successor.trail_id;
2332
2333 /* I am the destination. I have the data. */
2334 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2335 &best_known_dest))
2336 {
2337 GDS_DATACACHE_handle_get (key,
2338 block_type,
2339 NULL,
2340 0,
2341 bg,
2342 &get_cb,
2343 NULL);
2344 return GNUNET_NO;
2345 }
2346
2347 GDS_NEIGHBOURS_send_get (key,
2348 block_type,
2349 options,
2350 desired_replication_level,
2351 &best_known_dest,
2352 &intermediate_trail_id,
2353 &successor.next_hop,
2354 0,
2355 1,
2356 &my_identity);
2357 return GNUNET_OK;
2358}
2359
2360
2361/**
2362 * Randomly choose one of your friends (which is not congested and have not crossed
2363 * trail threshold) from the friend_peermap
2364 * @return Friend Randomly chosen friend.
2365 * NULL in case friend peermap is empty, or all the friends are either
2366 * congested or have crossed trail threshold.
2367 */
2368static struct FriendInfo *
2369select_random_friend ()
2370{
2371 unsigned int current_size;
2372 uint32_t index;
2373 unsigned int j = 0;
2374 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
2375 struct GNUNET_PeerIdentity key_ret;
2376 struct FriendInfo *friend;
2377
2378 current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
2379
2380 /* No friends.*/
2381 if (0 == current_size)
2382 return NULL;
2383
2384 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
2385 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2386
2387 /* Iterate till you don't reach to index. */
2388 for (j = 0; j < index ; j++)
2389 GNUNET_assert (GNUNET_YES ==
2390 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
2391
2392 do
2393 {
2394 /* Reset the index in friend peermap to 0 as we reached to the end. */
2395 if (j == current_size)
2396 {
2397 j = 0;
2398 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2399 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2400
2401 }
2402
2403 /* Get the friend stored at the index, j*/
2404 GNUNET_assert (GNUNET_YES ==
2405 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
2406 &key_ret,
2407 (const void **)&friend));
2408
2409 /* This friend is not congested and has not crossed trail threshold. */
2410 if ((friend->trails_count < TRAILS_THROUGH_FRIEND_THRESHOLD) &&
2411 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_timestamp).rel_value_us))
2412 {
2413 break;
2414 }
2415 friend = NULL;
2416 j++;
2417 } while (j != index);
2418
2419 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
2420 return friend;
2421}
2422
2423
2424/**
2425 * Compute 64 bit value of finger_identity corresponding to a finger index using
2426 * Chord formula.
2427 * For all fingers, n.finger[i] = n + pow (2,i),
2428 * For predecessor, n.finger[PREDECESSOR_FINGER_ID] = n - 1, where
2429 * n = my_identity, i = finger_index, n.finger[i] = 64 bit finger value
2430 *
2431 * @param finger_index Index corresponding to which we calculate 64 bit value.
2432 * @return 64 bit value.
2433 */
2434static uint64_t
2435compute_finger_identity_value (unsigned int finger_index)
2436{
2437 uint64_t my_id64;
2438
2439 GNUNET_memcpy (&my_id64,
2440 &my_identity,
2441 sizeof (uint64_t));
2442 my_id64 = GNUNET_ntohll (my_id64);
2443
2444 /* Are we looking for immediate predecessor? */
2445 if (PREDECESSOR_FINGER_ID == finger_index)
2446 return (my_id64 - 1);
2447 uint64_t add = (uint64_t)1 << finger_index;
2448 return (my_id64 + add);
2449}
2450
2451
2452/**
2453 * Choose a random friend. Calculate the next finger identity to search,from
2454 * current_search_finger_index. Start looking for the trail to reach to
2455 * finger identity through this random friend.
2456 *
2457 * @param cls closure for this task
2458 */
2459static void
2460send_find_finger_trail_message (void *cls)
2461{
2462 struct FriendInfo *target_friend;
2463 struct GNUNET_HashCode trail_id;
2464 struct GNUNET_HashCode intermediate_trail_id;
2465 unsigned int is_predecessor = 0;
2466 uint64_t finger_id_value;
2467
2468 /* Schedule another send_find_finger_trail_message task. After one round of
2469 * finger search, this time is exponentially backoff. */
2470 find_finger_trail_task_next_send_time.rel_value_us =
2471 find_finger_trail_task_next_send_time.rel_value_us +
2472 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
2473 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
2474 find_finger_trail_task =
2475 GNUNET_SCHEDULER_add_delayed (find_finger_trail_task_next_send_time,
2476 &send_find_finger_trail_message,
2477 NULL);
2478
2479 /* No space in my routing table. (Source and destination peers also store entries
2480 * in their routing table). */
2481 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
2482 return;
2483
2484 target_friend = select_random_friend ();
2485 if (NULL == target_friend)
2486 return;
2487
2488 finger_id_value = compute_finger_identity_value (current_search_finger_index);
2489 if (PREDECESSOR_FINGER_ID == current_search_finger_index)
2490 is_predecessor = 1;
2491
2492 /* Generate a unique trail id for trail we are trying to setup. */
2493 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
2494 &trail_id,
2495 sizeof (trail_id));
2496 memset (&intermediate_trail_id,
2497 0,
2498 sizeof (struct GNUNET_HashCode));
2499 GDS_NEIGHBOURS_send_trail_setup (&my_identity,
2500 finger_id_value,
2501 target_friend->id,
2502 target_friend,
2503 0, NULL,
2504 is_predecessor,
2505 &trail_id,
2506 &intermediate_trail_id);
2507}
2508
2509
2510/**
2511 * In case there are already maximum number of possible trails to reach to a
2512 * finger, then check if the new trail's length is lesser than any of the
2513 * existing trails.
2514 * If yes then replace that old trail by new trail.
2515 *
2516 * Note: Here we are taking length as a parameter to choose the best possible
2517 * trail, but there could be other parameters also like:
2518 * 1. duration of existence of a trail - older the better.
2519 * 2. if the new trail is completely disjoint than the
2520 * other trails, then may be choosing it is better.
2521 *
2522 * @param finger Finger
2523 * @param new_finger_trail List of peers to reach from me to @a finger, NOT
2524 * including the endpoints.
2525 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2526 * @param new_finger_trail_id Unique identifier of @a new_finger_trail.
2527 */
2528static void
2529select_and_replace_trail (struct FingerInfo *finger,
2530 const struct GNUNET_PeerIdentity *new_trail,
2531 unsigned int new_trail_length,
2532 const struct GNUNET_HashCode *new_trail_id)
2533{
2534 struct Trail *current_trail;
2535 unsigned int largest_trail_length;
2536 unsigned int largest_trail_index;
2537 struct Trail_Element *trail_element;
2538 const struct GNUNET_PeerIdentity *next_hop;
2539 unsigned int i;
2540
2541 largest_trail_length = new_trail_length;
2542 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2543
2544 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == finger->trails_count);
2545
2546 for (i = 0; i < finger->trails_count; i++)
2547 {
2548 current_trail = &finger->trail_list[i];
2549 GNUNET_assert (GNUNET_YES == current_trail->is_present);
2550 if (current_trail->trail_length > largest_trail_length)
2551 {
2552 largest_trail_length = current_trail->trail_length;
2553 largest_trail_index = i;
2554 }
2555 }
2556
2557 /* New trail is not better than existing ones. Send trail teardown. */
2558 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2559 {
2560 next_hop = GDS_ROUTING_get_next_hop (new_trail_id,
2561 GDS_ROUTING_SRC_TO_DEST);
2562 GDS_ROUTING_remove_trail (new_trail_id);
2563 GDS_NEIGHBOURS_send_trail_teardown (new_trail_id,
2564 GDS_ROUTING_SRC_TO_DEST,
2565 next_hop);
2566 return;
2567 }
2568
2569 /* Send trail teardown message across the replaced trail. */
2570 struct Trail *replace_trail = &finger->trail_list[largest_trail_index];
2571 next_hop = GDS_ROUTING_get_next_hop (&replace_trail->trail_id,
2572 GDS_ROUTING_SRC_TO_DEST);
2573 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (&replace_trail->trail_id));
2574 GDS_NEIGHBOURS_send_trail_teardown (&replace_trail->trail_id,
2575 GDS_ROUTING_SRC_TO_DEST,
2576 next_hop);
2577
2578 /* Free the trail. */
2579 while (NULL != (trail_element = replace_trail->trail_head))
2580 {
2581 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
2582 replace_trail->trail_tail,
2583 trail_element);
2584 GNUNET_free_non_null (trail_element);
2585 }
2586
2587 /* Add new trial at that location. */
2588 replace_trail->is_present = GNUNET_YES;
2589 replace_trail->trail_length = new_trail_length;
2590 replace_trail->trail_id = *new_trail_id;
2591
2592 for (i = 0; i < new_trail_length; i++)
2593 {
2594 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
2595 element->peer = new_trail[i];
2596
2597 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
2598 replace_trail->trail_tail,
2599 element);
2600 }
2601 /* FIXME: URGENT Are we adding the trail back to the list. */
2602}
2603
2604
2605/**
2606 * Check if the new trail to reach to finger is unique or do we already have
2607 * such a trail present for finger.
2608 * @param existing_finger Finger identity
2609 * @param new_trail New trail to reach @a existing_finger
2610 * @param trail_length Total number of peers in new_trail.
2611 * @return #GNUNET_YES if the new trail is unique
2612 * #GNUNET_NO if same trail is already present.
2613 */
2614static int
2615is_new_trail_unique (struct FingerInfo *existing_finger,
2616 const struct GNUNET_PeerIdentity *new_trail,
2617 unsigned int trail_length)
2618{
2619 struct Trail *current_trail;
2620 struct Trail_Element *trail_element;
2621 int i;
2622 int j;
2623
2624 GNUNET_assert (existing_finger->trails_count > 0);
2625
2626 /* Iterate over list of trails. */
2627 for (i = 0; i < existing_finger->trails_count; i++)
2628 {
2629 current_trail = &(existing_finger->trail_list[i]);
2630 if(GNUNET_NO == current_trail->is_present)
2631 continue;
2632
2633 /* New trail and existing trail length are not same. */
2634 if (current_trail->trail_length != trail_length)
2635 {
2636 return GNUNET_YES;
2637 }
2638
2639 trail_element = current_trail->trail_head;
2640 for (j = 0; j < current_trail->trail_length; j++)
2641 {
2642 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
2643 &trail_element->peer))
2644 {
2645 return GNUNET_YES;
2646 }
2647 trail_element = trail_element->next;
2648 }
2649 }
2650 return GNUNET_NO;
2651}
2652
2653
2654/**
2655 * FIXME; In case of multiple trails, we may have a case where a trail from in
2656 * between has been removed, then we should try to find a free slot , not simply
2657 * add a trail at then end of the list.
2658 * Add a new trail at a free slot in trail array of existing finger.
2659 * @param existing_finger Finger
2660 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2661 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2662 * @param new_finger_trail_id Unique identifier of the trail.
2663 */
2664static void
2665add_new_trail (struct FingerInfo *existing_finger,
2666 const struct GNUNET_PeerIdentity *new_trail,
2667 unsigned int new_trail_length,
2668 const struct GNUNET_HashCode *new_trail_id)
2669{
2670 struct FriendInfo *friend;
2671 struct Trail *trail;
2672 unsigned int i;
2673 int free_slot = -1;
2674
2675 if (GNUNET_NO == is_new_trail_unique (existing_finger,
2676 new_trail,
2677 new_trail_length))
2678 return;
2679
2680 for (i = 0; i < existing_finger->trails_count; i++)
2681 {
2682 if (GNUNET_NO == existing_finger->trail_list[i].is_present)
2683 {
2684 free_slot = i;
2685 break;
2686 }
2687 }
2688
2689 if (-1 == free_slot)
2690 free_slot = i;
2691
2692 trail = &existing_finger->trail_list[free_slot];
2693 GNUNET_assert (GNUNET_NO == trail->is_present);
2694 trail->trail_id = *new_trail_id;
2695 trail->trail_length = new_trail_length;
2696 existing_finger->trails_count++;
2697 trail->is_present = GNUNET_YES;
2698 if (0 == new_trail_length)
2699 {
2700 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2701 &existing_finger->finger_identity);
2702 }
2703 else
2704 {
2705 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2706 &new_trail[0]);
2707 }
2708 GNUNET_assert (NULL != friend);
2709 friend->trails_count++;
2710 for (i = 0; i < new_trail_length; i++)
2711 {
2712 struct Trail_Element *element;
2713
2714 element = GNUNET_new (struct Trail_Element);
2715 element->peer = new_trail[i];
2716 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2717 trail->trail_tail,
2718 element);
2719 }
2720
2721 existing_finger->trail_list[free_slot].trail_head = trail->trail_head;
2722 existing_finger->trail_list[free_slot].trail_tail = trail->trail_tail;
2723 existing_finger->trail_list[free_slot].trail_length = new_trail_length;
2724 existing_finger->trail_list[free_slot].trail_id = *new_trail_id;
2725 existing_finger->trail_list[free_slot].is_present = GNUNET_YES;
2726}
2727
2728
2729#if 0
2730/**
2731 * FIXME; In case of multiple trails, we may have a case where a trail from in
2732 * between has been removed, then we should try to find a free slot , not simply
2733 * add a trail at then end of the list.
2734 * Add a new trail at a free slot in trail array of existing finger.
2735 * @param existing_finger Finger
2736 * @param new_finger_trail New trail from me to finger, NOT including endpoints
2737 * @param new_finger_trail_length Total number of peers in @a new_finger_trail
2738 * @param new_finger_trail_id Unique identifier of the trail.
2739 */
2740static void
2741add_new_trail (struct FingerInfo *existing_finger,
2742 const struct GNUNET_PeerIdentity *new_trail,
2743 unsigned int new_trail_length,
2744 const struct GNUNET_HashCode *new_trail_id)
2745{
2746 struct Trail *trail;
2747 struct FriendInfo *first_friend;
2748 int i;
2749 int index;
2750
2751 if (GNUNET_NO == is_new_trail_unique (existing_finger,
2752 new_trail,
2753 new_trail_length))
2754 return;
2755
2756 index = existing_finger->trails_count;
2757 trail = &existing_finger->trail_list[index];
2758 GNUNET_assert (GNUNET_NO == trail->is_present);
2759 trail->trail_id = *new_trail_id;
2760 trail->trail_length = new_trail_length;
2761 existing_finger->trails_count++;
2762 trail->is_present = GNUNET_YES;
2763
2764 GNUNET_assert (NULL == (GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2765 &existing_finger->finger_identity)));
2766 /* If finger is a friend then we never call this function. */
2767 GNUNET_assert (new_trail_length > 0);
2768
2769 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2770 &new_trail[0]);
2771 first_friend->trails_count++;
2772
2773 for (i = 0; i < new_trail_length; i++)
2774 {
2775 struct Trail_Element *element;
2776
2777 element = GNUNET_new (struct Trail_Element);
2778 element->peer = new_trail[i];
2779 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
2780 trail->trail_tail,
2781 element);
2782 }
2783 /* Do we need to add trail head and trail tail in the trail list itearator.*/
2784 existing_finger->trail_list[index].trail_head = trail->trail_head;
2785 existing_finger->trail_list[index].trail_tail = trail->trail_tail;
2786 existing_finger->trail_list[index].trail_length = new_trail_length;
2787 existing_finger->trail_list[index].trail_id = *new_trail_id;
2788 existing_finger->trail_list[index].is_present = GNUNET_YES;
2789}
2790#endif
2791
2792/**
2793 * Get the next hop to send trail teardown message from routing table and
2794 * then delete the entry from routing table. Send trail teardown message for a
2795 * specific trail of a finger.
2796 * @param finger Finger whose trail is to be removed.
2797 * @param trail List of peers in trail from me to a finger, NOT including
2798 * endpoints.
2799 */
2800static void
2801send_trail_teardown (struct FingerInfo *finger,
2802 struct Trail *trail)
2803{
2804 struct FriendInfo *friend;
2805 const struct GNUNET_PeerIdentity *next_hop;
2806
2807 next_hop = GDS_ROUTING_get_next_hop (&trail->trail_id,
2808 GDS_ROUTING_SRC_TO_DEST);
2809 if (NULL == next_hop)
2810 {
2811// DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line=%d,traillength = %d",
2812// GNUNET_i2s(&my_identity), GNUNET_h2s(&trail->trail_id), __LINE__,trail->trail_length);
2813 return;
2814 }
2815 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2816 &my_identity));
2817
2818 GNUNET_assert(GNUNET_YES == trail->is_present);
2819 if (trail->trail_length > 0)
2820 {
2821 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2822 &trail->trail_head->peer);
2823 }
2824 else
2825 {
2826 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2827 &finger->finger_identity);
2828 }
2829
2830 if(NULL == friend)
2831 {
2832 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2833 __LINE__,
2834 GNUNET_h2s (&trail->trail_id),
2835 GNUNET_i2s(&my_identity),
2836 trail->trail_length);
2837 return;
2838 }
2839 if ( (0 != GNUNET_CRYPTO_cmp_peer_identity (next_hop,
2840 friend->id) ) &&
2841 (0 == trail->trail_length))
2842 {
2843 DEBUG ("\n LINE NO: = %d, Friend not found for trail id %s of peer %s trail length = %d",
2844 __LINE__,
2845 GNUNET_h2s (&trail->trail_id),
2846 GNUNET_i2s (&my_identity),
2847 trail->trail_length);
2848 return;
2849 }
2850 GNUNET_assert (GNUNET_YES ==
2851 GDS_ROUTING_remove_trail (&trail->trail_id));
2852 friend->trails_count--;
2853 GDS_NEIGHBOURS_send_trail_teardown (&trail->trail_id,
2854 GDS_ROUTING_SRC_TO_DEST,
2855 friend->id);
2856}
2857
2858
2859/**
2860 * Send trail teardown message across all the trails to reach to finger.
2861 * @param finger Finger whose all the trail should be freed.
2862 */
2863static void
2864send_all_finger_trails_teardown (struct FingerInfo *finger)
2865{
2866 for (unsigned int i = 0; i < finger->trails_count; i++)
2867 {
2868 struct Trail *trail;
2869
2870 trail = &finger->trail_list[i];
2871 if (GNUNET_YES == trail->is_present)
2872 {
2873 send_trail_teardown (finger, trail);
2874 trail->is_present = GNUNET_NO;
2875 }
2876 }
2877}
2878
2879
2880/**
2881 * Free a specific trail
2882 * @param trail List of peers to be freed.
2883 */
2884static void
2885free_trail (struct Trail *trail)
2886{
2887 struct Trail_Element *trail_element;
2888
2889 while (NULL != (trail_element = trail->trail_head))
2890 {
2891 GNUNET_CONTAINER_DLL_remove (trail->trail_head,
2892 trail->trail_tail,
2893 trail_element);
2894 GNUNET_free_non_null (trail_element);
2895 }
2896 trail->trail_head = NULL;
2897 trail->trail_tail = NULL;
2898}
2899
2900
2901/**
2902 * Free finger and its trail.
2903 *
2904 * @param finger Finger to be freed.
2905 * @param finger_table_index Index at which finger is stored.
2906 */
2907static void
2908free_finger (struct FingerInfo *finger,
2909 unsigned int finger_table_index)
2910{
2911 struct Trail *trail;
2912
2913 for (unsigned int i = 0; i < finger->trails_count; i++)
2914 {
2915 trail = &finger->trail_list[i];
2916 if (GNUNET_NO == trail->is_present)
2917 continue;
2918
2919 if (trail->trail_length > 0)
2920 free_trail (trail);
2921 trail->is_present = GNUNET_NO;
2922 }
2923
2924 finger->is_present = GNUNET_NO;
2925 memset (&finger_table[finger_table_index],
2926 0,
2927 sizeof (finger_table[finger_table_index]));
2928}
2929
2930
2931/**
2932 * Add a new entry in finger table at finger_table_index.
2933 * In case I am my own finger, then we don't have a trail. In case of a friend,
2934 * we have a trail with unique id and '0' trail length.
2935 * In case a finger is a friend, then increment the trails count of the friend.
2936 *
2937 * @param finger_identity Peer Identity of new finger
2938 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2939 * @param finger_trail_length Total number of peers in @a finger_trail.
2940 * @param trail_id Unique identifier of the trail.
2941 * @param finger_table_index Index in finger table.
2942 */
2943static void
2944add_new_finger (const struct GNUNET_PeerIdentity *finger_identity,
2945 const struct GNUNET_PeerIdentity *finger_trail,
2946 unsigned int finger_trail_length,
2947 const struct GNUNET_HashCode *trail_id,
2948 unsigned int finger_table_index)
2949{
2950 struct FingerInfo *new_entry;
2951 struct FriendInfo *first_trail_hop;
2952 struct Trail *trail;
2953 unsigned int i;
2954
2955 new_entry = GNUNET_new (struct FingerInfo);
2956 new_entry->finger_identity = *finger_identity;
2957 new_entry->finger_table_index = finger_table_index;
2958 new_entry->is_present = GNUNET_YES;
2959
2960 /* If the new entry is my own identity. */
2961 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2962 finger_identity))
2963 {
2964 new_entry->trails_count = 0;
2965 finger_table[finger_table_index] = *new_entry;
2966 GNUNET_free (new_entry);
2967 return;
2968 }
2969
2970 /* Finger is a friend. */
2971 if (0 == finger_trail_length)
2972 {
2973 new_entry->trail_list[0].trail_id = *trail_id;
2974 new_entry->trails_count = 1;
2975 new_entry->trail_list[0].is_present = GNUNET_YES;
2976 new_entry->trail_list[0].trail_length = 0;
2977 new_entry->trail_list[0].trail_head = NULL;
2978 new_entry->trail_list[0].trail_tail = NULL;
2979 finger_table[finger_table_index] = *new_entry;
2980 GNUNET_assert (NULL !=
2981 (first_trail_hop =
2982 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2983 finger_identity)));
2984
2985 first_trail_hop->trails_count++;
2986 GNUNET_free (new_entry);
2987 return;
2988 }
2989
2990 GNUNET_assert (NULL !=
2991 (first_trail_hop =
2992 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2993 &finger_trail[0])));
2994 new_entry->trails_count = 1;
2995 first_trail_hop->trails_count++;
2996 /* Copy the finger trail into trail. */
2997 trail = &new_entry->trail_list[0];
2998 for(i = 0; i < finger_trail_length; i++)
2999 {
3000 struct Trail_Element *element = GNUNET_new (struct Trail_Element);
3001
3002 element->next = NULL;
3003 element->prev = NULL;
3004 element->peer = finger_trail[i];
3005 GNUNET_CONTAINER_DLL_insert_tail (trail->trail_head,
3006 trail->trail_tail,
3007 element);
3008 }
3009
3010 /* Add trail to trail list. */
3011 trail->trail_length = finger_trail_length;
3012 trail->trail_id = *trail_id;
3013 trail->is_present = GNUNET_YES;
3014 finger_table[finger_table_index] = *new_entry;
3015 GNUNET_free (new_entry);
3016}
3017
3018
3019/**
3020 * Periodic task to verify current successor. There can be multiple trails to reach
3021 * to successor, choose the shortest one and send verify successor message
3022 * across that trail.
3023 *
3024 * @param cls closure for this task
3025 */
3026static void
3027send_verify_successor_message (void *cls)
3028{
3029 struct FriendInfo *target_friend;
3030 struct Trail *trail;
3031 struct Trail_Element *element;
3032 unsigned int trail_length;
3033 unsigned int i = 0;
3034 struct FingerInfo *successor;
3035
3036 successor = &finger_table[0];
3037
3038 /* This task will be scheduled when the result for Verify Successor is received. */
3039 send_verify_successor_task = NULL;
3040
3041 /* When verify successor is being called for first time *for current context*
3042 * cls will be NULL. If send_verify_successor_retry_task is not NO_TASK, we
3043 * must cancel the retry task scheduled for verify_successor of previous
3044 * context.
3045 */
3046 if (NULL == cls)
3047 {
3048 /* FIXME: Here we are scheduling a new verify successor task, as we
3049 got a new successor. But a send verify successor task may be in progress.
3050 1. We need to be sure that this is indeed a new successor. As this function
3051 is called even if we add a new trail to reach t old successor.
3052 2. Assuming the new successor is different, then verify successor message
3053 * to old successor may be following stages.
3054 * --> Waiting for verify successor result. Don't wait anymore. there is
3055 * no trail to reach from old successor to me, hence, routing
3056 * lookup will fail.
3057 * --> Waiting for notify confirmation. again don't wait for it. notify
3058 * confirmation will not succeded.
3059 */
3060 if (send_verify_successor_retry_task != NULL)
3061 {
3062 /* FIXME: Are we scheduling retry task as soon as we send verify message.
3063 If yes then here before making this task, first check if the message
3064 is for the same peer again. */
3065 struct VerifySuccessorContext *old_ctx =
3066 GNUNET_SCHEDULER_cancel(send_verify_successor_retry_task);
3067 /* old_ctx must not be NULL, as the retry task had been scheduled */
3068 GNUNET_assert(NULL != old_ctx);
3069 GNUNET_free(old_ctx);
3070 /* FIXME: Why don't we reset the task to NO_TASK here? */
3071 }
3072
3073 struct VerifySuccessorContext *ctx;
3074 ctx = GNUNET_new (struct VerifySuccessorContext);
3075
3076 ctx->num_retries_scheduled++;
3077 send_verify_successor_retry_task =
3078 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3079 &send_verify_successor_message,
3080 ctx);
3081 }
3082 else
3083 {
3084 /* This is a retry attempt for verify_successor for a previous context */
3085 struct VerifySuccessorContext *ctx;
3086
3087 ctx = cls;
3088 ctx->num_retries_scheduled++;
3089 send_verify_successor_retry_task =
3090 GNUNET_SCHEDULER_add_delayed (verify_successor_retry_time,
3091 &send_verify_successor_message,
3092 ctx);
3093 }
3094
3095 /* Among all the trails to reach to successor, select first one which is present.*/
3096 for (i = 0; i < successor->trails_count; i++)
3097 {
3098 trail = &successor->trail_list[i];
3099 if (GNUNET_YES == trail->is_present)
3100 break;
3101 }
3102
3103 /* No valid trail found to reach to successor. */
3104 if (i == successor->trails_count)
3105 return;
3106
3107 GNUNET_assert(0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3108 &successor->finger_identity));
3109 /* Trail stored at this index. */
3110 GNUNET_assert (GNUNET_YES == trail->is_present);
3111 if (NULL == GDS_ROUTING_get_next_hop (&trail->trail_id,
3112 GDS_ROUTING_SRC_TO_DEST))
3113 {
3114 DEBUG (" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
3115 GNUNET_i2s (&my_identity),
3116 GNUNET_h2s (&trail->trail_id),
3117 __LINE__);
3118 GNUNET_break(0);
3119 return;
3120 }
3121 trail_length = trail->trail_length;
3122 if (trail_length > 0)
3123 {
3124 /* Copy the trail into peer list. */
3125 struct GNUNET_PeerIdentity peer_list[trail_length];
3126
3127 element = trail->trail_head;
3128 for(i = 0; i < trail_length; i++)
3129 {
3130 peer_list[i] = element->peer;
3131 element = element->next;
3132 }
3133 GNUNET_assert (NULL != (target_friend =
3134 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3135 &peer_list[0])));
3136 GDS_NEIGHBOURS_send_verify_successor_message (&my_identity,
3137 &successor->finger_identity,
3138 &trail->trail_id,
3139 peer_list,
3140 trail_length,
3141 target_friend);
3142 }
3143 else
3144 {
3145 GNUNET_assert (NULL != (target_friend =
3146 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3147 &successor->finger_identity)));
3148 GDS_NEIGHBOURS_send_verify_successor_message (&my_identity,
3149 &successor->finger_identity,
3150 &trail->trail_id,
3151 NULL,
3152 0,
3153 target_friend);
3154 }
3155}
3156
3157
3158/**
3159 * FIXME: should this be a periodic task, incrementing the search finger index?
3160 * Update the current search finger index.
3161 * @a finger_identity
3162 * @a finger_table_index
3163 */
3164static void
3165update_current_search_finger_index (unsigned int finger_table_index)
3166{
3167 struct FingerInfo *successor;
3168
3169 /* FIXME correct this: only move current index periodically */
3170 if (finger_table_index != current_search_finger_index)
3171 return;
3172
3173 successor = &finger_table[0];
3174 GNUNET_assert (GNUNET_YES == successor->is_present);
3175
3176 /* We were looking for immediate successor. */
3177 if (0 == current_search_finger_index)
3178 {
3179 current_search_finger_index = PREDECESSOR_FINGER_ID;
3180 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3181 &successor->finger_identity))
3182 {
3183 if (NULL == send_verify_successor_task)
3184 {
3185 send_verify_successor_task
3186 = GNUNET_SCHEDULER_add_now (&send_verify_successor_message,
3187 NULL);
3188 }
3189 }
3190 return;
3191 }
3192 current_search_finger_index--;
3193}
3194
3195
3196/**
3197 * Get the least significant bit set in val.
3198 *
3199 * @param val Value
3200 * @return Position of first bit set, 65 in case of error.
3201 */
3202static unsigned int
3203find_set_bit (uint64_t val)
3204{
3205 uint64_t i;
3206 unsigned int pos;
3207
3208 i = 1;
3209 pos = 0;
3210
3211 while (!(i & val))
3212 {
3213 i = i << 1;
3214 pos++;
3215 if (pos > 63)
3216 {
3217 GNUNET_break (0);
3218 return 65;
3219 }
3220 }
3221
3222 if (val/i != 1)
3223 return 65; /* Some other bit was set to 1 as well. */
3224
3225 return pos;
3226}
3227
3228
3229/**
3230 * Calculate finger_table_index from initial 64 bit finger identity value that
3231 * we send in trail setup message.
3232 * @param ultimate_destination_finger_value Value that we calculated from our
3233 * identity and finger_table_index.
3234 * @param is_predecessor Is the entry for predecessor or not?
3235 * @return finger_table_index Value between 0 <= finger_table_index <= 64
3236 * finger_table_index > PREDECESSOR_FINGER_ID, if error occurs.
3237 */
3238static unsigned int
3239get_finger_table_index (uint64_t ultimate_destination_finger_value,
3240 unsigned int is_predecessor)
3241{
3242 uint64_t my_id64;
3243 uint64_t diff;
3244 unsigned int finger_table_index;
3245
3246 GNUNET_memcpy (&my_id64, &my_identity, sizeof (uint64_t));
3247 my_id64 = GNUNET_ntohll (my_id64);
3248
3249 /* Is this a predecessor finger? */
3250 if (1 == is_predecessor)
3251 {
3252 diff = my_id64 - ultimate_destination_finger_value;
3253 if (1 == diff)
3254 finger_table_index = PREDECESSOR_FINGER_ID;
3255 else
3256 finger_table_index = PREDECESSOR_FINGER_ID + 1; //error value
3257
3258 }
3259 else
3260 {
3261 diff = ultimate_destination_finger_value - my_id64;
3262 finger_table_index = find_set_bit (diff);
3263 }
3264 return finger_table_index;
3265}
3266
3267
3268/**
3269 * Remove finger and its associated data structures from finger table.
3270 * @param existing_finger Finger to be removed which is in finger table.
3271 * @param finger_table_index Index in finger table where @a existing_finger
3272 * is stored.
3273 */
3274static void
3275remove_existing_finger (struct FingerInfo *existing_finger,
3276 unsigned int finger_table_index)
3277{
3278 GNUNET_assert (GNUNET_YES == existing_finger->is_present);
3279
3280 /* If I am my own finger, then we have no trails. */
3281 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3282 &my_identity))
3283 {
3284 existing_finger->is_present = GNUNET_NO;
3285 memset ((void *)&finger_table[finger_table_index], 0,
3286 sizeof (finger_table[finger_table_index]));
3287 return;
3288 }
3289
3290 /* For all other fingers, send trail teardown across all the trails to reach
3291 finger, and free the finger. */
3292 send_all_finger_trails_teardown (existing_finger);
3293 free_finger (existing_finger, finger_table_index);
3294}
3295
3296
3297/**
3298 * Check if there is already an entry in finger_table at finger_table_index.
3299 * We get the finger_table_index from 64bit finger value we got from the network.
3300 * -- If yes, then select the closest finger.
3301 * -- If new and existing finger are same, then check if you can store more
3302 * trails.
3303 * -- If yes then add trail, else keep the best trails to reach to the
3304 * finger.
3305 * -- If the new finger is closest, remove the existing entry, send trail
3306 * teardown message across all the trails to reach the existing entry.
3307 * Add the new finger.
3308 * -- If new and existing finger are different, and existing finger is closest
3309 * then do nothing.
3310 * -- Update current_search_finger_index.
3311 * @param finger_identity Peer Identity of new finger
3312 * @param finger_trail Trail to reach the new finger
3313 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3314 * @param is_predecessor Is this entry for predecessor in finger_table?
3315 * @param finger_value 64 bit value of finger identity that we got from network.
3316 * @param finger_trail_id Unique identifier of @finger_trail.
3317 */
3318static void
3319finger_table_add (const struct GNUNET_PeerIdentity *finger_identity,
3320 const struct GNUNET_PeerIdentity *finger_trail,
3321 unsigned int finger_trail_length,
3322 unsigned int is_predecessor,
3323 uint64_t finger_value,
3324 const struct GNUNET_HashCode *finger_trail_id)
3325{
3326 struct FingerInfo *existing_finger;
3327 const struct GNUNET_PeerIdentity *closest_peer;
3328 struct FingerInfo *successor;
3329 unsigned int finger_table_index;
3330
3331 /* Get the finger_table_index corresponding to finger_value we got from network.*/
3332 finger_table_index = get_finger_table_index (finger_value, is_predecessor);
3333
3334 /* Invalid finger_table_index. */
3335 if ((finger_table_index > PREDECESSOR_FINGER_ID))
3336 {
3337 GNUNET_break_op (0);
3338 return;
3339 }
3340
3341 /* Check if new entry is same as successor. */
3342 if ((0 != finger_table_index) &&
3343 (PREDECESSOR_FINGER_ID != finger_table_index))
3344 {
3345 successor = &finger_table[0];
3346 if (GNUNET_NO == successor->is_present)
3347 {
3348 GNUNET_break (0); //ASSERTION FAILS HERE. FIXME
3349 return;
3350 }
3351 if (0 == GNUNET_CRYPTO_cmp_peer_identity (finger_identity,
3352 &successor->finger_identity))
3353 {
3354 if (0 == fingers_round_count)
3355 {
3356 find_finger_trail_task_next_send_time =
3357 GNUNET_TIME_STD_BACKOFF(find_finger_trail_task_next_send_time);
3358 }
3359 else
3360 fingers_round_count--;
3361 current_search_finger_index = 0;
3362 GNUNET_STATISTICS_update (GDS_stats,
3363 gettext_noop
3364 ("# FINGERS_COUNT"), (int64_t) total_fingers_found,
3365 GNUNET_NO);
3366 total_fingers_found = 0;
3367 return;
3368 }
3369
3370 struct FingerInfo prev_finger;
3371 prev_finger = finger_table[finger_table_index - 1];
3372 if (0 == GNUNET_CRYPTO_cmp_peer_identity (finger_identity,
3373 &prev_finger.finger_identity))
3374 {
3375 current_search_finger_index--;
3376 return;
3377 }
3378 }
3379
3380 total_fingers_found++;
3381 existing_finger = &finger_table[finger_table_index];
3382
3383 /* No entry present in finger_table for given finger map index. */
3384 if (GNUNET_NO == existing_finger->is_present)
3385 {
3386 /* Shorten the trail if possible. */
3387 add_new_finger (finger_identity,
3388 finger_trail,
3389 finger_trail_length,
3390 finger_trail_id,
3391 finger_table_index);
3392 update_current_search_finger_index (finger_table_index);
3393 return;
3394 }
3395
3396 /* If existing entry and finger identity are not same. */
3397 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3398 finger_identity))
3399 {
3400 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3401 finger_identity,
3402 finger_value,
3403 is_predecessor);
3404
3405 /* If the new finger is the closest peer. */
3406 if (0 == GNUNET_CRYPTO_cmp_peer_identity (finger_identity,
3407 closest_peer))
3408 {
3409 remove_existing_finger (existing_finger,
3410 finger_table_index);
3411 add_new_finger (finger_identity,
3412 finger_trail,
3413 finger_trail_length,
3414 finger_trail_id,
3415 finger_table_index);
3416 }
3417 else
3418 {
3419 /* Existing finger is the closest one. We need to send trail teardown
3420 across the trail setup in routing table of all the peers. */
3421 if (0 != GNUNET_CRYPTO_cmp_peer_identity (finger_identity,
3422 &my_identity))
3423 {
3424 if (finger_trail_length > 0)
3425 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3426 GDS_ROUTING_SRC_TO_DEST,
3427 &finger_trail[0]);
3428 else
3429 GDS_NEIGHBOURS_send_trail_teardown (finger_trail_id,
3430 GDS_ROUTING_SRC_TO_DEST,
3431 finger_identity);
3432 }
3433 }
3434 }
3435 else
3436 {
3437 /* If both new and existing entry are same as my_identity, then do nothing. */
3438 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&existing_finger->finger_identity,
3439 &my_identity))
3440 {
3441 return;
3442 }
3443
3444 /* If there is space to store more trails. */
3445 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
3446 add_new_trail (existing_finger,
3447 finger_trail,
3448 finger_trail_length,
3449 finger_trail_id);
3450 else
3451 select_and_replace_trail (existing_finger,
3452 finger_trail,
3453 finger_trail_length,
3454 finger_trail_id);
3455 }
3456 update_current_search_finger_index (finger_table_index);
3457 return;
3458}
3459
3460
3461/**
3462 * Verify validity of P2P put messages.
3463 *
3464 * @param cls closure
3465 * @param put the message
3466 * @return #GNUNET_OK if the message is well-formed
3467 */
3468static int
3469check_dht_p2p_put (void *cls,
3470 const struct PeerPutMessage *put)
3471{
3472 size_t msize;
3473 uint32_t putlen;
3474
3475 msize = ntohs (put->header.size);
3476 putlen = ntohl (put->put_path_length);
3477 if ((msize <
3478 sizeof (struct PeerPutMessage) +
3479 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3480 (putlen >
3481 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3482 {
3483 GNUNET_break_op (0);
3484 return GNUNET_SYSERR;
3485 }
3486 return GNUNET_OK;
3487}
3488
3489
3490/**
3491 * Core handler for P2P put messages.
3492 *
3493 * @param cls closure
3494 * @param put the message
3495 */
3496static void
3497handle_dht_p2p_put (void *cls,
3498 const struct PeerPutMessage *put)
3499{
3500 struct GNUNET_PeerIdentity *put_path;
3501 struct GNUNET_PeerIdentity current_best_known_dest;
3502 struct GNUNET_PeerIdentity best_known_dest;
3503 struct GNUNET_HashCode received_intermediate_trail_id;
3504 struct GNUNET_HashCode intermediate_trail_id;
3505 struct GNUNET_PeerIdentity next_hop;
3506 const struct GNUNET_PeerIdentity *next_routing_hop;
3507 enum GNUNET_DHT_RouteOption options;
3508 struct GNUNET_HashCode test_key;
3509 struct Closest_Peer successor;
3510 void *payload;
3511 size_t msize;
3512 uint32_t putlen = ntohl (put->put_path_length);
3513 struct GNUNET_PeerIdentity pp[putlen + 1];
3514 uint32_t hop_count;
3515 size_t payload_size;
3516 uint64_t key_value;
3517
3518 msize = ntohs (put->header.size);
3519 GNUNET_STATISTICS_update (GDS_stats,
3520 gettext_noop ("# Bytes received from other peers"),
3521 (int64_t) msize,
3522 GNUNET_NO);
3523
3524 current_best_known_dest = put->best_known_destination;
3525 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3526 payload = &put_path[putlen];
3527 options = ntohl (put->options);
3528 received_intermediate_trail_id = put->intermediate_trail_id;
3529 hop_count = ntohl(put->hop_count);
3530 payload_size = msize - (sizeof (struct PeerPutMessage) +
3531 putlen * sizeof (struct GNUNET_PeerIdentity));
3532 hop_count++;
3533 switch (GNUNET_BLOCK_get_key (GDS_block_context,
3534 ntohl (put->block_type),
3535 payload,
3536 payload_size,
3537 &test_key))
3538 {
3539 case GNUNET_YES:
3540 if (0 != memcmp (&test_key,
3541 &put->key,
3542 sizeof (struct GNUNET_HashCode)))
3543 {
3544 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3545 GNUNET_break_op (0);
3546 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3547 "PUT with key `%s' for block with key %s\n",
3548 put_s,
3549 GNUNET_h2s_full (&test_key));
3550 GNUNET_free (put_s);
3551 return;
3552 }
3553 break;
3554 case GNUNET_NO:
3555 GNUNET_break_op (0);
3556 return;
3557 case GNUNET_SYSERR:
3558 /* cannot verify, good luck */
3559 break;
3560 }
3561
3562 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3563 {
3564 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3565 ntohl (put->block_type),
3566 NULL,
3567 GNUNET_BLOCK_EO_NONE,
3568 NULL, /* query */
3569 NULL, 0, /* xquery */
3570 payload,
3571 payload_size))
3572 {
3573 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3574 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3575 break;
3576
3577 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3578 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3579 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3580 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3581 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3582 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3583 default:
3584 GNUNET_break_op (0);
3585 return;
3586 }
3587 }
3588
3589 /* Check if you are already a part of put path. */
3590 unsigned int i;
3591 for (i = 0; i < putlen; i++)
3592 {
3593 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3594 &put_path[i]))
3595 {
3596 putlen = i;
3597 break;
3598 }
3599 }
3600
3601 /* Add yourself to the list. */
3602 //if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3603 if (1)
3604 {
3605 GNUNET_memcpy (pp,
3606 put_path,
3607 putlen * sizeof (struct GNUNET_PeerIdentity));
3608 pp[putlen] = my_identity;
3609 putlen++;
3610 }
3611 else
3612 {
3613 putlen = 0;
3614 }
3615 GNUNET_memcpy (&key_value,
3616 &put->key,
3617 sizeof (uint64_t));
3618 key_value = GNUNET_ntohll (key_value);
3619 successor = find_local_best_known_next_hop (key_value,
3620 GDS_FINGER_TYPE_NON_PREDECESSOR);
3621 next_hop = successor.next_hop;
3622 intermediate_trail_id = successor.trail_id;
3623 best_known_dest = successor.best_known_destination;
3624
3625 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&current_best_known_dest,
3626 &my_identity)))
3627 {
3628 next_routing_hop = GDS_ROUTING_get_next_hop (&received_intermediate_trail_id,
3629 GDS_ROUTING_SRC_TO_DEST);
3630 if (NULL != next_routing_hop)
3631 {
3632 next_hop = *next_routing_hop;
3633 intermediate_trail_id = received_intermediate_trail_id;
3634 best_known_dest = current_best_known_dest;
3635 }
3636 }
3637
3638 GDS_CLIENTS_process_put (options,
3639 ntohl (put->block_type),
3640 hop_count,
3641 ntohl (put->desired_replication_level),
3642 putlen,
3643 pp,
3644 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3645 &put->key,
3646 payload,
3647 payload_size);
3648
3649 /* I am the final destination */
3650 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3651 &best_known_dest))
3652 {
3653 DEBUG ("\n PUT_REQUEST_SUCCESSFUL for key = %s",
3654 GNUNET_h2s(&put->key));
3655 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3656 &put->key,
3657 putlen,
3658 pp,
3659 ntohl (put->block_type),
3660 payload_size,
3661 payload);
3662 }
3663 GDS_NEIGHBOURS_send_put (&put->key,
3664 ntohl (put->block_type),
3665 ntohl (put->options),
3666 ntohl (put->desired_replication_level),
3667 best_known_dest,
3668 intermediate_trail_id,
3669 &next_hop,
3670 hop_count,
3671 putlen,
3672 pp,
3673 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3674 payload,
3675 payload_size);
3676}
3677
3678
3679/**
3680 * Check integrity of @a get message.
3681 *
3682 * @param cls closure
3683 * @param get the message
3684 * @return #GNUNET_OK if @a get is well-formed
3685 */
3686static int
3687check_dht_p2p_get (void *cls,
3688 const struct PeerGetMessage *get)
3689{
3690 uint32_t get_length;
3691 size_t msize;
3692
3693 msize = ntohs (get->header.size);
3694 get_length = ntohl (get->get_path_length);
3695 if ((msize <
3696 sizeof (struct PeerGetMessage) +
3697 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3698 (get_length >
3699 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3700 {
3701 GNUNET_break_op (0);
3702 return GNUNET_SYSERR;
3703 }
3704 return GNUNET_OK;
3705}
3706
3707
3708/**
3709 * FIXME: Check for loop in the request. If you already are part of get path,
3710 * then you need to reset the get path length.
3711 * Core handler for p2p get requests.
3712 *
3713 * @param cls closure
3714 * @param get the message
3715 */
3716static void
3717handle_dht_p2p_get (void *cls,
3718 const struct PeerGetMessage *get)
3719{
3720 const struct GNUNET_PeerIdentity *get_path;
3721 struct GNUNET_PeerIdentity best_known_dest;
3722 struct GNUNET_PeerIdentity current_best_known_dest;
3723 struct GNUNET_HashCode intermediate_trail_id;
3724 struct GNUNET_HashCode received_intermediate_trail_id;
3725 struct Closest_Peer successor;
3726 struct GNUNET_PeerIdentity next_hop;
3727 const struct GNUNET_PeerIdentity *next_routing_hop;
3728 uint32_t get_length;
3729 uint64_t key_value;
3730 uint32_t hop_count;
3731 size_t msize;
3732
3733 msize = ntohs (get->header.size);
3734 get_length = ntohl (get->get_path_length);
3735 current_best_known_dest = get->best_known_destination;
3736 received_intermediate_trail_id = get->intermediate_trail_id;
3737 get_path = (const struct GNUNET_PeerIdentity *) &get[1];
3738 hop_count = get->hop_count;
3739 hop_count++;
3740 GNUNET_STATISTICS_update (GDS_stats,
3741 gettext_noop ("# Bytes received from other peers"),
3742 msize,
3743 GNUNET_NO);
3744 GNUNET_memcpy (&key_value,
3745 &get->key,
3746 sizeof (uint64_t));
3747 key_value = GNUNET_ntohll (key_value);
3748
3749 /* Check if you are already a part of get path. */
3750 for (unsigned int i = 0; i < get_length; i++)
3751 {
3752 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3753 &get_path[i]))
3754 {
3755 get_length = i;
3756 break;
3757 }
3758 }
3759
3760 /* Add yourself in the get path. */
3761 struct GNUNET_PeerIdentity gp[get_length + 1];
3762 GNUNET_memcpy (gp,
3763 get_path,
3764 get_length * sizeof (struct GNUNET_PeerIdentity));
3765 gp[get_length] = my_identity;
3766 get_length = get_length + 1;
3767 GDS_CLIENTS_process_get (get->options,
3768 get->block_type,
3769 hop_count,
3770 get->desired_replication_level,
3771 get->get_path_length,
3772 gp,
3773 &get->key);
3774
3775
3776 successor = find_local_best_known_next_hop (key_value,
3777 GDS_FINGER_TYPE_NON_PREDECESSOR);
3778 next_hop = successor.next_hop;
3779 best_known_dest = successor.best_known_destination;
3780 intermediate_trail_id = successor.trail_id;
3781 /* I am not the final destination. I am part of trail to reach final dest. */
3782 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&current_best_known_dest, &my_identity)))
3783 {
3784 next_routing_hop = GDS_ROUTING_get_next_hop (&received_intermediate_trail_id,
3785 GDS_ROUTING_SRC_TO_DEST);
3786 if (NULL != next_routing_hop)
3787 {
3788 next_hop = *next_routing_hop;
3789 best_known_dest = current_best_known_dest;
3790 intermediate_trail_id = received_intermediate_trail_id;
3791 }
3792 }
3793
3794 /* I am the final destination. */
3795 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3796 &best_known_dest))
3797 {
3798 if (1 == get_length)
3799 {
3800 DEBUG ("\n GET_REQUEST DONE for key = %s",
3801 GNUNET_h2s(&get->key));
3802 GDS_DATACACHE_handle_get (&get->key,
3803 get->block_type, /* FIXME: endianess? */
3804 NULL,
3805 0,
3806 NULL,
3807 &get_cb,
3808 NULL);
3809 }
3810 else
3811 {
3812 GDS_DATACACHE_handle_get (&get->key,
3813 get->block_type, /* FIXME: endianess? */
3814 NULL,
3815 0,
3816 NULL,
3817 &get_cb,
3818 &gp[get_length - 2]);
3819 }
3820 }
3821 else
3822 {
3823 GDS_NEIGHBOURS_send_get (&get->key,
3824 get->block_type, /* FIXME: endianess? */
3825 get->options,
3826 get->desired_replication_level,
3827 &best_known_dest,
3828 &intermediate_trail_id,
3829 &next_hop,
3830 hop_count,
3831 get_length,
3832 gp);
3833 }
3834}
3835
3836
3837/**
3838 * Check validity of @a get_result message.
3839 *
3840 * @param cls closure
3841 * @param get_result the message
3842 * @return #GNUNET_OK if @a get_result is well-formed
3843 */
3844static int
3845check_dht_p2p_get_result (void *cls,
3846 const struct PeerGetResultMessage *get_result)
3847{
3848 size_t msize;
3849 unsigned int getlen;
3850 unsigned int putlen;
3851
3852 msize = ntohs (get_result->header.size);
3853 getlen = ntohl (get_result->get_path_length);
3854 putlen = ntohl (get_result->put_path_length);
3855 if ((msize <
3856 sizeof (struct PeerGetResultMessage) +
3857 getlen * sizeof (struct GNUNET_PeerIdentity) +
3858 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3859 (getlen >
3860 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3861 (putlen >
3862 GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3863 {
3864 GNUNET_break_op (0);
3865 return GNUNET_SYSERR;
3866 }
3867 return GNUNET_OK;
3868}
3869
3870
3871/**
3872 * Core handler for get result
3873 *
3874 * @param cls closure
3875 * @param get_result the message
3876 */
3877static void
3878handle_dht_p2p_get_result (void *cls,
3879 const struct PeerGetResultMessage *get_result)
3880{
3881 const struct GNUNET_PeerIdentity *get_path;
3882 const struct GNUNET_PeerIdentity *put_path;
3883 const void *payload;
3884 size_t payload_size;
3885 size_t msize;
3886 unsigned int getlen;
3887 unsigned int putlen;
3888 int current_path_index;
3889
3890 msize = ntohs (get_result->header.size);
3891 getlen = ntohl (get_result->get_path_length);
3892 putlen = ntohl (get_result->put_path_length);
3893 DEBUG ("GET_RESULT FOR DATA_SIZE = %u\n",
3894 (unsigned int) msize);
3895 GNUNET_STATISTICS_update (GDS_stats,
3896 gettext_noop ("# Bytes received from other peers"),
3897 msize,
3898 GNUNET_NO);
3899 put_path = (const struct GNUNET_PeerIdentity *) &get_result[1];
3900 get_path = &put_path[putlen];
3901 payload = (const void *) &get_path[getlen];
3902 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3903 (getlen + putlen) * sizeof (struct GNUNET_PeerIdentity));
3904
3905 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3906 &get_path[0])))
3907 {
3908 GDS_CLIENTS_handle_reply (GNUNET_TIME_absolute_ntoh (get_result->expiration_time),
3909 &get_result->key,
3910 getlen,
3911 get_path,
3912 putlen,
3913 put_path,
3914 get_result->type,
3915 payload_size,
3916 payload);
3917 return;
3918 }
3919 current_path_index = search_my_index (get_path,
3920 getlen);
3921 if (-1 == current_path_index)
3922 {
3923 DEBUG ("No entry found in get path.\n");
3924 GNUNET_break (0);
3925 return;
3926 }
3927 if ((getlen + 1) == current_path_index)
3928 {
3929 DEBUG("Present twice in get path. Not allowed. \n");
3930 GNUNET_break (0);
3931 return;
3932 }
3933 GDS_NEIGHBOURS_send_get_result (&get_result->key,
3934 get_result->type, /* FIXME: endianess? */
3935 &get_path[current_path_index - 1],
3936 &get_result->querying_peer,
3937 putlen,
3938 put_path,
3939 getlen,
3940 get_path,
3941 GNUNET_TIME_absolute_ntoh (get_result->expiration_time),
3942 payload,
3943 payload_size);
3944}
3945
3946
3947/**
3948 * Find the next hop to pass trail setup message. First find the local best known
3949 * hop from your own identity, friends and finger. If you were part of trail,
3950 * then get the next hop from routing table. Compare next_hop from routing table
3951 * and local best known hop, and return the closest one to final_dest_finger_val
3952 * @param final_dest_finger_val 64 bit value of finger identity
3953 * @param intermediate_trail_id If you are part of trail to reach to some other
3954 * finger, then it is the trail id to reach to
3955 * that finger, else set to 0.
3956 * @param is_predecessor Are we looking for closest successor or predecessor.
3957 * @param source Source of trail setup message.
3958 * @param current_dest In case you are part of trail, then finger to which
3959 * we should forward the message. Else my own identity
3960 * @return Closest Peer for @a final_dest_finger_val
3961 */
3962static struct Closest_Peer
3963get_local_best_known_next_hop (uint64_t final_dest_finger_val,
3964 const struct GNUNET_HashCode *intermediate_trail_id,
3965 unsigned int is_predecessor,
3966 const struct GNUNET_PeerIdentity *source,
3967 const struct GNUNET_PeerIdentity *current_dest)
3968{
3969 struct Closest_Peer peer;
3970
3971 peer = find_local_best_known_next_hop (final_dest_finger_val,
3972 is_predecessor);
3973
3974 /* Am I just a part of a trail towards a finger (current_destination)? */
3975 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
3976 current_dest) &&
3977 0 != GNUNET_CRYPTO_cmp_peer_identity (&peer.best_known_destination,
3978 current_dest))
3979 {
3980 const struct GNUNET_PeerIdentity *closest_peer;
3981
3982 /* Select best successor among one found locally and current_destination
3983 * that we got from network.*/
3984 closest_peer = select_closest_peer (&peer.best_known_destination,
3985 current_dest,
3986 final_dest_finger_val,
3987 is_predecessor);
3988
3989 /* Is current dest (end point of the trail of which I am a part) closest_peer? */
3990 if (0 == GNUNET_CRYPTO_cmp_peer_identity (current_dest,
3991 closest_peer))
3992 {
3993 const struct GNUNET_PeerIdentity *next_hop;
3994
3995 next_hop = GDS_ROUTING_get_next_hop (intermediate_trail_id,
3996 GDS_ROUTING_SRC_TO_DEST);
3997 /* next_hop NULL is a valid case. This intermediate trail id is set by
3998 some other finger, and while this trail setup is in progress, that other
3999 peer might have found a better trail ,and send trail teardown message
4000 across the network. In case we got the trail teardown message first,
4001 then next_hop will be NULL. A possible solution could be to keep track
4002 * of all removed trail id, and be sure that there is no other reason . */
4003 if(NULL != next_hop)
4004 {
4005 peer.next_hop = *next_hop;
4006 peer.best_known_destination = *current_dest;
4007 peer.trail_id = *intermediate_trail_id;
4008 }
4009 }
4010 }
4011 return peer;
4012}
4013
4014
4015/**
4016 * Check format of a PeerTrailSetupMessage.
4017 *
4018 * @param cls closure
4019 * @param trail_setup the message
4020 * @return #GNUNET_OK if @a trail_setup is well-formed
4021 */
4022static int
4023check_dht_p2p_trail_setup (void *cls,
4024 const struct PeerTrailSetupMessage *trail_setup)
4025{
4026 size_t msize;
4027
4028 msize = ntohs (trail_setup->header.size);
4029 if ((msize - sizeof (struct PeerTrailSetupMessage)) %
4030 sizeof (struct GNUNET_PeerIdentity) != 0)
4031 {
4032 GNUNET_break_op (0);
4033 return GNUNET_SYSERR;
4034 }
4035 return GNUNET_OK;
4036}
4037
4038
4039/**
4040 * Core handle for PeerTrailSetupMessage.
4041 *
4042 * @param cls closure
4043 * @param trail_setup the message
4044 */
4045static void
4046handle_dht_p2p_trail_setup (void *cls,
4047 const struct PeerTrailSetupMessage *trail_setup)
4048{
4049 struct FriendInfo *friend = cls;
4050 const struct GNUNET_PeerIdentity *trail_peer_list;
4051 struct GNUNET_PeerIdentity current_dest;
4052 struct FriendInfo *target_friend;
4053 struct GNUNET_PeerIdentity source;
4054 struct GNUNET_HashCode intermediate_trail_id;
4055 struct GNUNET_HashCode trail_id;
4056 unsigned int is_predecessor;
4057 uint32_t trail_length;
4058 uint64_t final_dest_finger_val;
4059 int i;
4060 size_t msize;
4061
4062 msize = ntohs (trail_setup->header.size);
4063 trail_length = (msize - sizeof (struct PeerTrailSetupMessage))/
4064 sizeof (struct GNUNET_PeerIdentity);
4065 GNUNET_STATISTICS_update (GDS_stats,
4066 gettext_noop ("# Bytes received from other peers"),
4067 msize,
4068 GNUNET_NO);
4069 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_setup[1];
4070 current_dest = trail_setup->best_known_destination;
4071 trail_id = trail_setup->trail_id;
4072 final_dest_finger_val
4073 = GNUNET_ntohll (trail_setup->final_destination_finger_value);
4074 source = trail_setup->source_peer;
4075 is_predecessor = ntohl (trail_setup->is_predecessor);
4076 intermediate_trail_id = trail_setup->intermediate_trail_id;
4077
4078 /* Did the friend insert its ID in the trail list? */
4079 if ( (trail_length > 0) &&
4080 (0 != memcmp (&trail_peer_list[trail_length-1],
4081 friend->id,
4082 sizeof (struct GNUNET_PeerIdentity))) )
4083 {
4084 GNUNET_break_op (0);
4085 return;
4086 }
4087
4088 /* If I was the source and got the message back, then set trail length to 0.*/
4089 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
4090 &source))
4091 {
4092 trail_length = 0;
4093 }
4094
4095 /* Check if you are present in the trail seen so far? */
4096 for (i = 0; i < trail_length; i++)
4097 {
4098 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[i],
4099 &my_identity))
4100 {
4101 /* We will add ourself later in code, if NOT destination. */
4102 trail_length = i;
4103 break;
4104 }
4105 }
4106
4107 /* Is my routing table full? */
4108 if (GNUNET_YES == GDS_ROUTING_threshold_reached ())
4109 {
4110 target_friend
4111 = (trail_length > 0)
4112 ? GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4113 &trail_peer_list[trail_length - 1])
4114 : GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4115 &source);
4116 if (NULL == target_friend)
4117 {
4118 DEBUG ("\n friend not found");
4119 GNUNET_break(0);
4120 return;
4121 }
4122 GDS_NEIGHBOURS_send_trail_rejection (&source,
4123 final_dest_finger_val,
4124 &my_identity,
4125 is_predecessor,
4126 trail_peer_list,
4127 trail_length,
4128 &trail_id,
4129 target_friend,
4130 CONGESTION_TIMEOUT);
4131 return;
4132 }
4133
4134 /* Get the next hop to forward the trail setup request. */
4135 struct Closest_Peer next_peer
4136 = get_local_best_known_next_hop (final_dest_finger_val,
4137 &intermediate_trail_id,
4138 is_predecessor,
4139 &source,
4140 &current_dest);
4141
4142 /* Am I the final destination? */
4143 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&next_peer.best_known_destination,
4144 &my_identity))
4145 {
4146 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&source,
4147 &my_identity))
4148 {
4149 finger_table_add (&my_identity,
4150 NULL,
4151 0,
4152 is_predecessor,
4153 final_dest_finger_val,
4154 &trail_id);
4155 return;
4156 }
4157
4158 target_friend
4159 = (trail_length > 0)
4160 ? GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4161 &trail_peer_list[trail_length-1])
4162 : GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4163 &source);
4164 if (NULL == target_friend)
4165 {
4166 GNUNET_break_op (0);
4167 return;
4168 }
4169 GDS_ROUTING_add (&trail_id,
4170 target_friend->id,
4171 &my_identity);
4172 GDS_NEIGHBOURS_send_trail_setup_result (&source,
4173 &my_identity,
4174 target_friend,
4175 trail_length,
4176 trail_peer_list,
4177 is_predecessor,
4178 final_dest_finger_val,
4179 &trail_id);
4180 return;
4181 }
4182 /* I'm not the final destination. */
4183 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4184 &next_peer.next_hop);
4185 if (NULL == target_friend)
4186 {
4187 DEBUG ("\n target friend not found for peer = %s",
4188 GNUNET_i2s(&next_peer.next_hop));
4189 GNUNET_break (0);
4190 return;
4191 }
4192 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
4193 &source))
4194 {
4195 /* Add yourself to list of peers. */
4196 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4197
4198 GNUNET_memcpy (peer_list,
4199 trail_peer_list,
4200 trail_length * sizeof (struct GNUNET_PeerIdentity));
4201 peer_list[trail_length] = my_identity;
4202 GDS_NEIGHBOURS_send_trail_setup (&source,
4203 final_dest_finger_val,
4204 &next_peer.best_known_destination,
4205 target_friend,
4206 trail_length + 1,
4207 peer_list,
4208 is_predecessor,
4209 &trail_id,
4210 &next_peer.trail_id);
4211 return;
4212 }
4213 GDS_NEIGHBOURS_send_trail_setup (&source,
4214 final_dest_finger_val,
4215 &next_peer.best_known_destination,
4216 target_friend,
4217 0,
4218 NULL,
4219 is_predecessor,
4220 &trail_id,
4221 &next_peer.trail_id);
4222}
4223
4224
4225/**
4226 * Validate format of trail setup result messages.
4227 *
4228 * @param closure
4229 * @param trail_result the message
4230 * @return #GNUNET_OK if @a trail_result is well-formed
4231 */
4232static int
4233check_dht_p2p_trail_setup_result (void *cls,
4234 const struct PeerTrailSetupResultMessage *trail_result)
4235{
4236 size_t msize;
4237
4238 msize = ntohs (trail_result->header.size);
4239 if ((msize - sizeof (struct PeerTrailSetupResultMessage)) %
4240 sizeof (struct GNUNET_PeerIdentity) != 0)
4241 {
4242 GNUNET_break_op (0);
4243 return GNUNET_SYSERR;
4244 }
4245 return GNUNET_OK;
4246}
4247
4248
4249/**
4250 * Core handle for p2p trail setup result messages.
4251 *
4252 * @param closure
4253 * @param trail_result the message
4254 */
4255static void
4256handle_dht_p2p_trail_setup_result (void *cls,
4257 const struct PeerTrailSetupResultMessage *trail_result)
4258{
4259 struct FriendInfo *friend = cls;
4260 const struct GNUNET_PeerIdentity *trail_peer_list;
4261 struct GNUNET_PeerIdentity next_hop;
4262 struct FriendInfo *target_friend;
4263 struct GNUNET_PeerIdentity querying_peer;
4264 struct GNUNET_PeerIdentity finger_identity;
4265 uint32_t trail_length;
4266 uint64_t ultimate_destination_finger_value;
4267 uint32_t is_predecessor;
4268 struct GNUNET_HashCode trail_id;
4269 int my_index;
4270 size_t msize;
4271
4272 msize = ntohs (trail_result->header.size);
4273 trail_length = (msize - sizeof (struct PeerTrailSetupResultMessage))/
4274 sizeof (struct GNUNET_PeerIdentity);
4275
4276 GNUNET_STATISTICS_update (GDS_stats,
4277 gettext_noop ("# Bytes received from other peers"),
4278 msize,
4279 GNUNET_NO);
4280
4281 is_predecessor = ntohl (trail_result->is_predecessor);
4282 querying_peer = trail_result->querying_peer;
4283 finger_identity = trail_result->finger_identity;
4284 trail_id = trail_result->trail_id;
4285 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_result[1];
4286 ultimate_destination_finger_value
4287 = GNUNET_ntohll (trail_result->ultimate_destination_finger_value);
4288
4289 /* Am I the one who initiated the query? */
4290 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer,
4291 &my_identity)))
4292 {
4293 /* Check that you got the message from the correct peer. */
4294 if (trail_length > 0)
4295 {
4296 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[0],
4297 friend->id));
4298 }
4299 else
4300 {
4301 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4302 friend->id));
4303 }
4304 GDS_ROUTING_add (&trail_id,
4305 &my_identity,
4306 friend->id);
4307 finger_table_add (&finger_identity,
4308 trail_peer_list,
4309 trail_length,
4310 is_predecessor,
4311 ultimate_destination_finger_value,
4312 &trail_id);
4313 return;
4314 }
4315
4316 /* Get my location in the trail. */
4317 my_index = search_my_index (trail_peer_list,
4318 trail_length);
4319 if (-1 == my_index)
4320 {
4321 DEBUG ("Not found in trail\n");
4322 GNUNET_break_op(0);
4323 return;
4324 }
4325 //TODO; return -2.
4326 if ((trail_length + 1) == my_index)
4327 {
4328 DEBUG ("Found twice in trail.\n");
4329 GNUNET_break_op(0);
4330 return;
4331 }
4332
4333 //TODO; Refactor code here and above to check if sender peer is correct
4334 if (my_index == 0)
4335 {
4336 if (trail_length > 1)
4337 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[1],
4338 friend->id));
4339 else
4340 GNUNET_assert (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4341 friend->id));
4342 next_hop = trail_result->querying_peer;
4343 }
4344 else
4345 {
4346 if (my_index == trail_length - 1)
4347 {
4348 GNUNET_assert (0 ==
4349 GNUNET_CRYPTO_cmp_peer_identity (&finger_identity,
4350 friend->id));
4351 }
4352 else
4353 GNUNET_assert (0 ==
4354 GNUNET_CRYPTO_cmp_peer_identity (&trail_peer_list[my_index + 1],
4355 friend->id));
4356 next_hop = trail_peer_list[my_index - 1];
4357 }
4358
4359 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4360 &next_hop);
4361 if (NULL == target_friend)
4362 {
4363 GNUNET_break_op (0);
4364 return;
4365 }
4366 GDS_ROUTING_add (&trail_id,
4367 &next_hop,
4368 friend->id);
4369 GDS_NEIGHBOURS_send_trail_setup_result (&querying_peer,
4370 &finger_identity,
4371 target_friend,
4372 trail_length,
4373 trail_peer_list,
4374 is_predecessor,
4375 ultimate_destination_finger_value,
4376 &trail_id);
4377}
4378
4379
4380/**
4381 * Invert the trail.
4382 *
4383 * @param trail Trail to be inverted
4384 * @param trail_length Total number of peers in the trail.
4385 * @return Updated trail
4386 */
4387static struct GNUNET_PeerIdentity *
4388invert_trail (const struct GNUNET_PeerIdentity *trail,
4389 unsigned int trail_length)
4390{
4391 int i;
4392 int j;
4393 struct GNUNET_PeerIdentity *inverted_trail;
4394
4395 inverted_trail = GNUNET_new_array (trail_length,
4396 struct GNUNET_PeerIdentity);
4397 i = 0;
4398 j = trail_length - 1;
4399 while (i < trail_length)
4400 {
4401 inverted_trail[i] = trail[j];
4402 i++;
4403 j--;
4404 }
4405
4406 GNUNET_assert (NULL !=
4407 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4408 &inverted_trail[0]));
4409 return inverted_trail;
4410}
4411
4412
4413/**
4414 * Return the shortest trail among all the trails to reach to finger from me.
4415 *
4416 * @param finger Finger
4417 * @param shortest_trail_length[out] Trail length of shortest trail from me
4418 * to @a finger
4419 * @return Shortest trail.
4420 */
4421static struct GNUNET_PeerIdentity *
4422get_shortest_trail (struct FingerInfo *finger,
4423 unsigned int *trail_length)
4424{
4425 struct Trail *trail;
4426 unsigned int flag = 0;
4427 unsigned int shortest_trail_index = 0;
4428 int shortest_trail_length = -1;
4429 struct Trail_Element *trail_element;
4430 struct GNUNET_PeerIdentity *trail_list;
4431 unsigned int i;
4432
4433 /* Get the shortest trail to reach to current successor. */
4434 for (i = 0; i < finger->trails_count; i++)
4435 {
4436 trail = &finger->trail_list[i];
4437
4438 if (0 == flag)
4439 {
4440 shortest_trail_index = i;
4441 shortest_trail_length = trail->trail_length;
4442 flag = 1;
4443 continue;
4444 }
4445
4446 if (shortest_trail_length > trail->trail_length)
4447 {
4448 shortest_trail_index = i;
4449 shortest_trail_length = trail->trail_length;
4450 }
4451 continue;
4452 }
4453
4454 /* Copy the shortest trail and return. */
4455 trail = &finger->trail_list[shortest_trail_index];
4456 trail_element = trail->trail_head;
4457
4458 trail_list = GNUNET_new_array (shortest_trail_length,
4459 struct GNUNET_PeerIdentity);
4460
4461 for (i = 0; i < shortest_trail_length; i++,trail_element = trail_element->next)
4462 {
4463 trail_list[i] = trail_element->peer;
4464 }
4465
4466 GNUNET_assert(shortest_trail_length != -1);
4467
4468 *trail_length = shortest_trail_length;
4469 return trail_list;
4470}
4471
4472
4473/**
4474 * Check if @a trail_1 and @a trail_2 have any common element. If yes then join
4475 * them at common element. @a trail_1 always preceeds @a trail_2 in joined trail.
4476 *
4477 * @param trail_1 Trail from source to me, NOT including endpoints.
4478 * @param trail_1_len Total number of peers @a trail_1
4479 * @param trail_2 Trail from me to current predecessor, NOT including endpoints.
4480 * @param trail_2_len Total number of peers @a trail_2
4481 * @param joined_trail_len Total number of peers in combined trail of @a trail_1
4482 * @a trail_2.
4483 * @return Joined trail.
4484 */
4485static struct GNUNET_PeerIdentity *
4486check_for_duplicate_entries (const struct GNUNET_PeerIdentity *trail_1,
4487 unsigned int trail_1_len,
4488 const struct GNUNET_PeerIdentity *trail_2,
4489 unsigned int trail_2_len,
4490 unsigned int *joined_trail_len)
4491{
4492 struct GNUNET_PeerIdentity *joined_trail;
4493 unsigned int i;
4494 unsigned int j;
4495 unsigned int k;
4496
4497 for (i = 0; i < trail_1_len; i++)
4498 {
4499 for (j = 0; j < trail_2_len; j++)
4500 {
4501 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&trail_1[i],
4502 &trail_2[j]))
4503 continue;
4504
4505 *joined_trail_len = i + (trail_2_len - j);
4506 joined_trail = GNUNET_new_array (*joined_trail_len,
4507 struct GNUNET_PeerIdentity);
4508
4509
4510 /* Copy all the elements from 0 to i into joined_trail. */
4511 for(k = 0; k < ( i+1); k++)
4512 {
4513 joined_trail[k] = trail_1[k];
4514 }
4515
4516 /* Increment j as entry stored is same as entry stored at i*/
4517 j = j+1;
4518
4519 /* Copy all the elements from j to trail_2_len-1 to joined trail.*/
4520 while(k <= (*joined_trail_len - 1))
4521 {
4522 joined_trail[k] = trail_2[j];
4523 j++;
4524 k++;
4525 }
4526
4527 return joined_trail;
4528 }
4529 }
4530
4531 /* Here you should join the trails. */
4532 *joined_trail_len = trail_1_len + trail_2_len + 1;
4533 joined_trail = GNUNET_new_array (*joined_trail_len,
4534 struct GNUNET_PeerIdentity);
4535
4536
4537 for(i = 0; i < trail_1_len;i++)
4538 {
4539 joined_trail[i] = trail_1[i];
4540 }
4541
4542 joined_trail[i] = my_identity;
4543 i++;
4544
4545 for (j = 0; i < *joined_trail_len; i++,j++)
4546 {
4547 joined_trail[i] = trail_2[j];
4548 }
4549
4550 return joined_trail;
4551}
4552
4553
4554/**
4555 * Return the trail from source to my current predecessor. Check if source
4556 * is already part of the this trail, if yes then return the shorten trail.
4557 *
4558 * @param current_trail Trail from source to me, NOT including the endpoints.
4559 * @param current_trail_length Number of peers in @a current_trail.
4560 * @param trail_src_to_curr_pred_length[out] Number of peers in trail from
4561 * source to my predecessor, NOT including
4562 * the endpoints.
4563 * @return Trail from source to my predecessor.
4564 */
4565static struct GNUNET_PeerIdentity *
4566get_trail_src_to_curr_pred (struct GNUNET_PeerIdentity source_peer,
4567 const struct GNUNET_PeerIdentity *trail_src_to_me,
4568 unsigned int trail_src_to_me_len,
4569 unsigned int *trail_src_to_curr_pred_length)
4570{
4571 struct GNUNET_PeerIdentity *trail_me_to_curr_pred;
4572 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4573 unsigned int trail_me_to_curr_pred_length;
4574 struct FingerInfo *current_predecessor;
4575 int i;
4576 unsigned int j;
4577 unsigned int len;
4578
4579 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4580
4581 /* Check if trail_src_to_me contains current_predecessor. */
4582 for (i = 0; i < trail_src_to_me_len; i++)
4583 {
4584 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&trail_src_to_me[i],
4585 &current_predecessor->finger_identity))
4586 continue;
4587
4588
4589 *trail_src_to_curr_pred_length = i;
4590
4591 if(0 == i)
4592 return NULL;
4593
4594 trail_src_to_curr_pred = GNUNET_new_array (*trail_src_to_curr_pred_length,
4595 struct GNUNET_PeerIdentity);
4596 for (j = 0; j < i; j++)
4597 trail_src_to_curr_pred[j] = trail_src_to_me[j];
4598 return trail_src_to_curr_pred;
4599 }
4600
4601
4602 trail_me_to_curr_pred = get_shortest_trail (current_predecessor,
4603 &trail_me_to_curr_pred_length);
4604
4605 /* Check if trail contains the source_peer. */
4606 for (i = trail_me_to_curr_pred_length - 1; i >= 0; i--)
4607 {
4608 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
4609 &trail_me_to_curr_pred[i]))
4610 continue;
4611
4612 /* Source is NOT part of trail. */
4613 i++;
4614
4615 /* Source is the last element in the trail to reach to my pred.
4616 Source is direct friend of the pred. */
4617 if (trail_me_to_curr_pred_length == i)
4618 {
4619 *trail_src_to_curr_pred_length = 0;
4620 GNUNET_free_non_null (trail_me_to_curr_pred);
4621 return NULL;
4622 }
4623
4624 *trail_src_to_curr_pred_length = trail_me_to_curr_pred_length - i;
4625 trail_src_to_curr_pred = GNUNET_new_array (*trail_src_to_curr_pred_length,
4626 struct GNUNET_PeerIdentity);
4627
4628
4629 for (j = 0; j < *trail_src_to_curr_pred_length; i++,j++)
4630 trail_src_to_curr_pred[j] = trail_me_to_curr_pred[i];
4631 GNUNET_free_non_null (trail_me_to_curr_pred);
4632 return trail_src_to_curr_pred;
4633 }
4634
4635 trail_src_to_curr_pred = check_for_duplicate_entries (trail_src_to_me,
4636 trail_src_to_me_len,
4637 trail_me_to_curr_pred,
4638 trail_me_to_curr_pred_length,
4639 &len);
4640 *trail_src_to_curr_pred_length = len;
4641 GNUNET_free_non_null(trail_me_to_curr_pred);
4642 return trail_src_to_curr_pred;
4643}
4644
4645
4646/**
4647 * Add finger as your predecessor. To add, first generate a new trail id, invert
4648 * the trail to get the trail from me to finger, add an entry in your routing
4649 * table, send add trail message to peers which are part of trail from me to
4650 * finger and add finger in finger table.
4651 *
4652 * @param finger
4653 * @param trail
4654 * @param trail_length
4655 */
4656static void
4657update_predecessor (const struct GNUNET_PeerIdentity *finger,
4658 const struct GNUNET_PeerIdentity *trail,
4659 unsigned int trail_length)
4660{
4661 struct GNUNET_HashCode trail_to_new_predecessor_id;
4662 struct GNUNET_PeerIdentity *trail_to_new_predecessor;
4663 struct FriendInfo *target_friend;
4664
4665 /* Generate trail id for trail from me to new predecessor = finger. */
4666 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
4667 &trail_to_new_predecessor_id,
4668 sizeof (trail_to_new_predecessor_id));
4669
4670 if (0 == trail_length)
4671 {
4672 trail_to_new_predecessor = NULL;
4673 GDS_ROUTING_add (&trail_to_new_predecessor_id,
4674 &my_identity,
4675 finger);
4676 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4677 finger);
4678 if (NULL == target_friend)
4679 {
4680 GNUNET_break (0);
4681 return;
4682 }
4683 }
4684 else
4685 {
4686 /* Invert the trail to get the trail from me to finger, NOT including the
4687 endpoints.*/
4688 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4689 &trail[trail_length-1]));
4690 trail_to_new_predecessor = invert_trail (trail,
4691 trail_length);
4692
4693 /* Add an entry in your routing table. */
4694 GDS_ROUTING_add (&trail_to_new_predecessor_id,
4695 &my_identity,
4696 &trail_to_new_predecessor[0]);
4697
4698 GNUNET_assert (NULL != (target_friend =
4699 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4700 &trail_to_new_predecessor[0])));
4701 }
4702
4703 /* Add entry in routing table of all peers that are part of trail from me
4704 to finger, including finger. */
4705 GDS_NEIGHBOURS_send_add_trail (&my_identity,
4706 finger,
4707 &trail_to_new_predecessor_id,
4708 trail_to_new_predecessor,
4709 trail_length,
4710 target_friend);
4711
4712 add_new_finger (finger,
4713 trail_to_new_predecessor,
4714 trail_length,
4715 &trail_to_new_predecessor_id,
4716 PREDECESSOR_FINGER_ID);
4717 GNUNET_free_non_null (trail_to_new_predecessor);
4718}
4719
4720
4721/**
4722 * Check if you already have a predecessor. If not then add finger as your
4723 * predecessor. If you have predecessor, then compare two peer identites.
4724 * If finger is correct predecessor, then remove the old entry, add finger in
4725 * finger table and send add_trail message to add the trail in the routing
4726 * table of all peers which are part of trail to reach from me to finger.
4727 * @param finger New peer which may be our predecessor.
4728 * @param trail List of peers to reach from @finger to me.
4729 * @param trail_length Total number of peer in @a trail.
4730 */
4731static void
4732compare_and_update_predecessor (const struct GNUNET_PeerIdentity *finger,
4733 const struct GNUNET_PeerIdentity *trail,
4734 unsigned int trail_length)
4735{
4736 struct FingerInfo *current_predecessor;
4737 const struct GNUNET_PeerIdentity *closest_peer;
4738 uint64_t predecessor_value;
4739 unsigned int is_predecessor = 1;
4740
4741 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4742 GNUNET_assert (0 != GNUNET_CRYPTO_cmp_peer_identity (finger,
4743 &my_identity));
4744
4745 /* No predecessor. Add finger as your predecessor. */
4746 if (GNUNET_NO == current_predecessor->is_present)
4747 {
4748 update_predecessor (finger,
4749 trail,
4750 trail_length);
4751 return;
4752 }
4753
4754 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&current_predecessor->finger_identity,
4755 finger))
4756 {
4757 return;
4758 }
4759
4760 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4761 closest_peer = select_closest_peer (finger,
4762 &current_predecessor->finger_identity,
4763 predecessor_value,
4764 is_predecessor);
4765
4766 /* Finger is the closest predecessor. Remove the existing one and add the new
4767 one. */
4768 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
4769 finger))
4770 {
4771 remove_existing_finger (current_predecessor,
4772 PREDECESSOR_FINGER_ID);
4773 update_predecessor (finger,
4774 trail,
4775 trail_length);
4776 return;
4777 }
4778}
4779
4780
4781/**
4782 * Check format of a p2p verify successor messages.
4783 *
4784 * @param cls closure
4785 * @param vsm the message
4786 * @return #GNUNET_OK if @a vsm is well-formed
4787 */
4788static int
4789check_dht_p2p_verify_successor (void *cls,
4790 const struct PeerVerifySuccessorMessage *vsm)
4791{
4792 size_t msize;
4793
4794 msize = ntohs (vsm->header.size);
4795 if ((msize - sizeof (struct PeerVerifySuccessorMessage)) %
4796 sizeof (struct GNUNET_PeerIdentity) != 0)
4797 {
4798 GNUNET_break_op (0);
4799 return GNUNET_SYSERR;
4800 }
4801 return GNUNET_OK;
4802}
4803
4804
4805/**
4806 * Core handle for p2p verify successor messages.
4807 *
4808 * @param cls closure
4809 * @param vsm the message
4810 */
4811static void
4812handle_dht_p2p_verify_successor (void *cls,
4813 const struct PeerVerifySuccessorMessage *vsm)
4814{
4815 struct FriendInfo *friend = cls;
4816 struct GNUNET_HashCode trail_id;
4817 struct GNUNET_PeerIdentity successor;
4818 struct GNUNET_PeerIdentity source_peer;
4819 struct GNUNET_PeerIdentity *trail;
4820 const struct GNUNET_PeerIdentity *next_hop;
4821 struct FingerInfo current_predecessor;
4822 struct FriendInfo *target_friend;
4823 unsigned int trail_src_to_curr_pred_len = 0;
4824 struct GNUNET_PeerIdentity *trail_src_to_curr_pred;
4825 unsigned int trail_length;
4826 size_t msize;
4827
4828 msize = ntohs (vsm->header.size);
4829 trail_length = (msize - sizeof (struct PeerVerifySuccessorMessage))/
4830 sizeof (struct GNUNET_PeerIdentity);
4831 GNUNET_STATISTICS_update (GDS_stats,
4832 gettext_noop ("# Bytes received from other peers"),
4833 msize,
4834 GNUNET_NO);
4835
4836 trail_id = vsm->trail_id;
4837 source_peer = vsm->source_peer;
4838 successor = vsm->successor;
4839 trail = (struct GNUNET_PeerIdentity *)&vsm[1];
4840
4841 /* I am NOT the successor of source_peer. Pass the message to next_hop on
4842 * the trail. */
4843 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor,
4844 &my_identity)))
4845 {
4846 next_hop = GDS_ROUTING_get_next_hop (&trail_id,
4847 GDS_ROUTING_SRC_TO_DEST);
4848 if (NULL == next_hop)
4849 return;
4850
4851 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4852 next_hop);
4853 if (NULL == target_friend)
4854 {
4855 GNUNET_break_op(0);
4856 return;
4857 }
4858 GDS_NEIGHBOURS_send_verify_successor_message (&source_peer,
4859 &successor,
4860 &trail_id,
4861 trail,
4862 trail_length,
4863 target_friend);
4864 return;
4865 }
4866
4867 /* I am the destination of this message. */
4868 /* Check if the source_peer could be our predecessor and if yes then update
4869 * it. */
4870 compare_and_update_predecessor (&source_peer,
4871 trail,
4872 trail_length);
4873 current_predecessor = finger_table[PREDECESSOR_FINGER_ID];
4874
4875 /* Is source of this message NOT my predecessor. */
4876 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&current_predecessor.finger_identity,
4877 &source_peer)))
4878 {
4879 trail_src_to_curr_pred
4880 = get_trail_src_to_curr_pred (source_peer,
4881 trail,
4882 trail_length,
4883 &trail_src_to_curr_pred_len);
4884 }
4885 else
4886 {
4887 trail_src_to_curr_pred_len = trail_length;
4888 trail_src_to_curr_pred = GNUNET_new_array (trail_src_to_curr_pred_len,
4889 struct GNUNET_PeerIdentity);
4890
4891 for (unsigned int i = 0; i < trail_src_to_curr_pred_len; i++)
4892 {
4893 trail_src_to_curr_pred[i] = trail[i];
4894 }
4895 }
4896
4897 GNUNET_assert (NULL !=
4898 (target_friend =
4899 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4900 friend->id)));
4901 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
4902 &my_identity,
4903 &current_predecessor.finger_identity,
4904 &trail_id,
4905 trail_src_to_curr_pred,
4906 trail_src_to_curr_pred_len,
4907 GDS_ROUTING_DEST_TO_SRC,
4908 target_friend);
4909 GNUNET_free_non_null (trail_src_to_curr_pred);
4910}
4911
4912
4913/**
4914 * If the trail from me to my probable successor contains a friend not
4915 * at index 0, then we can shorten the trail.
4916 *
4917 * @param probable_successor Peer which is our probable successor
4918 * @param trail_me_to_probable_successor Peers in path from me to my probable
4919 * successor, NOT including the endpoints.
4920 * @param trail_me_to_probable_successor_len Total number of peers in
4921 * @a trail_me_to_probable_succesor.
4922 * @return Updated trail, if any friend found.
4923 * Else the trail_me_to_probable_successor.
4924 */
4925const struct GNUNET_PeerIdentity *
4926check_trail_me_to_probable_succ (const struct GNUNET_PeerIdentity *probable_successor,
4927 const struct GNUNET_PeerIdentity *trail_me_to_probable_successor,
4928 unsigned int trail_me_to_probable_successor_len,
4929 unsigned int *trail_to_new_successor_length)
4930{
4931 unsigned int i;
4932 unsigned int j;
4933 struct GNUNET_PeerIdentity *trail_to_new_successor;
4934
4935 /* Probable successor is a friend */
4936 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4937 probable_successor))
4938 {
4939 trail_to_new_successor = NULL;
4940 *trail_to_new_successor_length = 0;
4941 return trail_to_new_successor;
4942 }
4943
4944 /* Is there any friend of yours in this trail. */
4945 if (trail_me_to_probable_successor_len > 1)
4946 {
4947 for (i = trail_me_to_probable_successor_len - 1; i > 0; i--)
4948 {
4949 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap,
4950 &trail_me_to_probable_successor[i]))
4951 continue;
4952
4953 *trail_to_new_successor_length = (trail_me_to_probable_successor_len - i);
4954 trail_to_new_successor = GNUNET_new_array (*trail_to_new_successor_length,
4955 struct GNUNET_PeerIdentity);
4956 for (j = 0; j < *trail_to_new_successor_length; i++,j++)
4957 {
4958 trail_to_new_successor[j] = trail_me_to_probable_successor[i];
4959 }
4960
4961 return trail_to_new_successor;
4962 }
4963 }
4964
4965 *trail_to_new_successor_length = trail_me_to_probable_successor_len;
4966 return trail_me_to_probable_successor;
4967}
4968
4969
4970// TODO: Move up
4971struct SendNotifyContext
4972{
4973 struct GNUNET_PeerIdentity source_peer;
4974 struct GNUNET_PeerIdentity successor;
4975 struct GNUNET_PeerIdentity *successor_trail;
4976 unsigned int successor_trail_length;
4977 struct GNUNET_HashCode succesor_trail_id;
4978 struct FriendInfo *target_friend;
4979 unsigned int num_retries_scheduled;
4980};
4981
4982
4983void
4984send_notify_new_successor (void *cls);
4985
4986
4987/**
4988 * Check if the peer which sent us verify successor result message is still ours
4989 * successor or not. If not, then compare existing successor and probable successor.
4990 * In case probable successor is the correct successor, remove the existing
4991 * successor. Add probable successor as new successor. Send notify new successor
4992 * message to new successor.
4993 * @param curr_succ Peer to which we sent the verify successor message. It may
4994 * or may not be our real current successor, as we may have few iterations of
4995 * find finger trail task.
4996 * @param probable_successor Peer which should be our successor accroding to @a
4997 * curr_succ
4998 * @param trail List of peers to reach from me to @a probable successor, NOT including
4999 * endpoints.
5000 * @param trail_length Total number of peers in @a trail.
5001 */
5002static void
5003compare_and_update_successor (const struct GNUNET_PeerIdentity *curr_succ,
5004 const struct GNUNET_PeerIdentity *probable_successor,
5005 const struct GNUNET_PeerIdentity *trail,
5006 unsigned int trail_length)
5007{
5008 struct FingerInfo *current_successor;
5009 const struct GNUNET_PeerIdentity *closest_peer;
5010 struct GNUNET_HashCode trail_id;
5011 const struct GNUNET_PeerIdentity *trail_me_to_probable_succ;
5012 struct FriendInfo *target_friend;
5013 unsigned int trail_me_to_probable_succ_len;
5014 unsigned int is_predecessor = 0;
5015 uint64_t successor_value;
5016 struct SendNotifyContext *notify_ctx;
5017
5018 current_successor = &finger_table[0];
5019 successor_value = compute_finger_identity_value(0);
5020
5021 /* If probable successor is same as current_successor, do nothing. */
5022 if(0 == GNUNET_CRYPTO_cmp_peer_identity (probable_successor,
5023 &current_successor->finger_identity))
5024 {
5025 if ((NULL != GDS_stats))
5026 {
5027 char *my_id_str;
5028 uint64_t succ;
5029 char *key;
5030 uint64_t my_id;
5031 GNUNET_memcpy (&my_id, &my_identity, sizeof(uint64_t));
5032 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5033 GNUNET_memcpy (&succ,
5034 &current_successor->finger_identity,
5035 sizeof(uint64_t));
5036 succ = GNUNET_ntohll(succ);
5037 GNUNET_asprintf (&key,
5038 "XDHT:%s:",
5039 my_id_str);
5040 GNUNET_free (my_id_str);
5041
5042 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5043 GNUNET_free (key);
5044 }
5045 if (send_verify_successor_task == NULL)
5046 send_verify_successor_task =
5047 GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5048 &send_verify_successor_message,
5049 NULL);
5050 return;
5051 }
5052 closest_peer = select_closest_peer (probable_successor,
5053 &current_successor->finger_identity,
5054 successor_value,
5055 is_predecessor);
5056
5057 /* If the current_successor in the finger table is closest, then do nothing. */
5058 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
5059 &current_successor->finger_identity))
5060 {
5061 //FIXME: Is this a good place to return the stats.
5062 if ((NULL != GDS_stats))
5063 {
5064 char *my_id_str;
5065 uint64_t succ;
5066 char *key;
5067
5068 my_id_str = GNUNET_strdup (GNUNET_i2s_full (&my_identity));
5069 GNUNET_memcpy(&succ, &current_successor->finger_identity, sizeof(uint64_t));
5070 GNUNET_asprintf (&key, "XDHT:%s:", my_id_str);
5071 GNUNET_free (my_id_str);
5072 GNUNET_STATISTICS_set (GDS_stats, key, succ, 0);
5073 GNUNET_free (key);
5074 }
5075
5076 if(0 == successor_times)
5077 {
5078// successor_times = 3;
5079 verify_successor_next_send_time =
5080 GNUNET_TIME_STD_BACKOFF (verify_successor_next_send_time);
5081 }
5082 else
5083 successor_times--;
5084
5085
5086 if (send_verify_successor_task == NULL)
5087 send_verify_successor_task =
5088 GNUNET_SCHEDULER_add_delayed (verify_successor_next_send_time,
5089 &send_verify_successor_message,
5090 NULL);
5091 return;
5092 }
5093
5094 /* Probable successor is the closest peer.*/
5095 if(trail_length > 0)
5096 {
5097 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5098 &trail[0]));
5099 }
5100 else
5101 {
5102 GNUNET_assert(NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5103 probable_successor));
5104 }
5105
5106 trail_me_to_probable_succ_len = 0;
5107 trail_me_to_probable_succ = check_trail_me_to_probable_succ (probable_successor,
5108 trail,
5109 trail_length,
5110 &trail_me_to_probable_succ_len);
5111
5112 /* Remove the existing successor. */
5113 remove_existing_finger (current_successor, 0);
5114 /* Generate a new trail id to reach to your new successor. */
5115 GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_STRONG,
5116 &trail_id,
5117 sizeof (trail_id));
5118
5119 if (trail_me_to_probable_succ_len > 0)
5120 {
5121 GDS_ROUTING_add (&trail_id,
5122 &my_identity,
5123 &trail_me_to_probable_succ[0]);
5124 GNUNET_assert (NULL !=
5125 (target_friend =
5126 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5127 &trail_me_to_probable_succ[0])));
5128 }
5129 else
5130 {
5131 GDS_ROUTING_add (&trail_id,
5132 &my_identity,
5133 probable_successor);
5134 GNUNET_assert (NULL !=
5135 (target_friend =
5136 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5137 probable_successor)));
5138 }
5139
5140 add_new_finger (probable_successor,
5141 trail_me_to_probable_succ,
5142 trail_me_to_probable_succ_len,
5143 &trail_id,
5144 0);
5145
5146 notify_ctx = GNUNET_new (struct SendNotifyContext);
5147
5148 notify_ctx->source_peer = my_identity;
5149 notify_ctx->successor = *probable_successor;
5150 notify_ctx->successor_trail = GNUNET_new_array (trail_me_to_probable_succ_len,
5151 struct GNUNET_PeerIdentity);
5152 GNUNET_memcpy (notify_ctx->successor_trail,
5153 trail_me_to_probable_succ,
5154 sizeof(struct GNUNET_PeerIdentity) * trail_me_to_probable_succ_len);
5155 notify_ctx->successor_trail_length = trail_me_to_probable_succ_len;
5156 notify_ctx->succesor_trail_id = trail_id;
5157 notify_ctx->target_friend = target_friend;
5158 notify_ctx->num_retries_scheduled = 0;
5159
5160 // TODO: Check if we should verify before schedule if already scheduled.
5161 GNUNET_SCHEDULER_add_now (&send_notify_new_successor,
5162 notify_ctx);
5163}
5164
5165
5166void
5167send_notify_new_successor (void *cls)
5168{
5169 struct SendNotifyContext *ctx = cls;
5170
5171 GDS_NEIGHBOURS_send_notify_new_successor (&ctx->source_peer,
5172 &ctx->successor,
5173 ctx->successor_trail,
5174 ctx->successor_trail_length,
5175 &ctx->succesor_trail_id,
5176 ctx->target_friend);
5177
5178 if ( (0 == ctx->num_retries_scheduled) &&
5179 (send_notify_new_successor_retry_task != NULL) )
5180 {
5181 // Result from previous notify successos hasn't arrived, so the retry task
5182 // hasn't been cancelled! Already a new notify successor must be called.
5183 // We will cancel the retry request.
5184 struct SendNotifyContext *old_notify_ctx;
5185
5186 old_notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5187 GNUNET_free (old_notify_ctx->successor_trail);
5188 GNUNET_free (old_notify_ctx);
5189 send_notify_new_successor_retry_task = NULL;
5190 }
5191
5192 ctx->num_retries_scheduled++;
5193 send_notify_new_successor_retry_task
5194 = GNUNET_SCHEDULER_add_delayed (notify_successor_retry_time,
5195 &send_notify_new_successor,
5196 cls);
5197}
5198
5199
5200/**
5201 * Check integrity of verify successor result messages.
5202 *
5203 * @param cls closure
5204 * @param vsrm the message
5205 * @return #GNUNET_OK if @a vrsm is well-formed
5206 */
5207static int
5208check_dht_p2p_verify_successor_result (void *cls,
5209 const struct PeerVerifySuccessorResultMessage *vsrm)
5210{
5211 size_t msize;
5212
5213 msize = ntohs (vsrm->header.size);
5214 if ((msize - sizeof (struct PeerVerifySuccessorResultMessage)) %
5215 sizeof (struct GNUNET_PeerIdentity) != 0)
5216 {
5217 GNUNET_break_op (0);
5218 return GNUNET_SYSERR;
5219 }
5220 return GNUNET_OK;
5221}
5222
5223
5224/**
5225 * Core handle for p2p verify successor result messages.
5226 *
5227 * @param cls closure
5228 * @param vsrm the message
5229 */
5230static void
5231handle_dht_p2p_verify_successor_result (void *cls,
5232 const struct PeerVerifySuccessorResultMessage *vsrm)
5233{
5234 enum GDS_ROUTING_trail_direction trail_direction;
5235 struct GNUNET_PeerIdentity querying_peer;
5236 struct GNUNET_HashCode trail_id;
5237 const struct GNUNET_PeerIdentity *next_hop;
5238 struct FriendInfo *target_friend;
5239 struct GNUNET_PeerIdentity probable_successor;
5240 struct GNUNET_PeerIdentity current_successor;
5241 const struct GNUNET_PeerIdentity *trail;
5242 unsigned int trail_length;
5243 size_t msize;
5244
5245 msize = ntohs (vsrm->header.size);
5246 trail_length = (msize - sizeof (struct PeerVerifySuccessorResultMessage))
5247 / sizeof (struct GNUNET_PeerIdentity);
5248
5249 GNUNET_STATISTICS_update (GDS_stats,
5250 gettext_noop ("# Bytes received from other peers"),
5251 msize,
5252 GNUNET_NO);
5253
5254 trail = (const struct GNUNET_PeerIdentity *) &vsrm[1];
5255 querying_peer = vsrm->querying_peer;
5256 trail_direction = ntohl (vsrm->trail_direction);
5257 trail_id = vsrm->trail_id;
5258 probable_successor = vsrm->probable_successor;
5259 current_successor = vsrm->current_successor;
5260
5261 /* Am I the querying_peer? */
5262 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&querying_peer,
5263 &my_identity)))
5264 {
5265 /* Cancel Retry Task */
5266 if (NULL != send_verify_successor_retry_task)
5267 {
5268 struct VerifySuccessorContext *ctx;
5269
5270 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
5271 GNUNET_free (ctx);
5272 send_verify_successor_retry_task = NULL;
5273 }
5274 compare_and_update_successor (&current_successor,
5275 &probable_successor,
5276 trail,
5277 trail_length);
5278 return;
5279 }
5280
5281 /*If you are not the querying peer then pass on the message */
5282 if(NULL == (next_hop =
5283 GDS_ROUTING_get_next_hop (&trail_id,
5284 trail_direction)))
5285 {
5286 /* Here it may happen that source peer has found a new successor, and removed
5287 the trail, Hence no entry found in the routing table. Fail silently.*/
5288 DEBUG (" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
5289 GNUNET_i2s (&my_identity),
5290 GNUNET_h2s (&trail_id),
5291 __LINE__);
5292 GNUNET_break_op(0);
5293 return;
5294 }
5295 if (NULL == (target_friend =
5296 GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop)))
5297 {
5298 GNUNET_break_op(0);
5299 return;
5300 }
5301 GDS_NEIGHBOURS_send_verify_successor_result (&querying_peer,
5302 &vsrm->current_successor,
5303 &probable_successor,
5304 &trail_id,
5305 trail,
5306 trail_length,
5307 trail_direction,
5308 target_friend);
5309}
5310
5311
5312/**
5313 * Check integrity of p2p notify new successor messages.
5314 *
5315 * @param cls closure
5316 * @param nsm the message
5317 * @return #GNUNET_OK if @a nsm is well-formed
5318 */
5319static int
5320check_dht_p2p_notify_new_successor (void *cls,
5321 const struct PeerNotifyNewSuccessorMessage *nsm)
5322{
5323 size_t msize;
5324
5325 msize = ntohs (nsm->header.size);
5326 if ((msize - sizeof (struct PeerNotifyNewSuccessorMessage)) %
5327 sizeof (struct GNUNET_PeerIdentity) != 0)
5328 {
5329 GNUNET_break_op (0);
5330 return GNUNET_SYSERR;
5331 }
5332 return GNUNET_OK;
5333}
5334
5335
5336/**
5337 * Core handle for p2p notify new successor messages.
5338 *
5339 * @param cls closure
5340 * @param nsm the message
5341 */
5342static void
5343handle_dht_p2p_notify_new_successor (void *cls,
5344 const struct PeerNotifyNewSuccessorMessage *nsm)
5345{
5346 struct FriendInfo *friend = cls;
5347 const struct GNUNET_PeerIdentity *trail;
5348 struct GNUNET_PeerIdentity source;
5349 struct GNUNET_PeerIdentity new_successor;
5350 struct GNUNET_HashCode trail_id;
5351 struct GNUNET_PeerIdentity next_hop;
5352 struct FriendInfo *target_friend;
5353 int my_index;
5354 size_t msize;
5355 uint32_t trail_length;
5356
5357 msize = ntohs (nsm->header.size);
5358 trail_length = (msize - sizeof (struct PeerNotifyNewSuccessorMessage))/
5359 sizeof (struct GNUNET_PeerIdentity);
5360 GNUNET_STATISTICS_update (GDS_stats,
5361 gettext_noop ("# Bytes received from other peers"),
5362 msize,
5363 GNUNET_NO);
5364 trail = (const struct GNUNET_PeerIdentity *) &nsm[1];
5365 source = nsm->source_peer;
5366 new_successor = nsm->new_successor;
5367 trail_id = nsm->trail_id;
5368
5369 /* I am the new_successor to source_peer. */
5370 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
5371 &new_successor))
5372 {
5373 if (trail_length > 0)
5374 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&trail[trail_length - 1],
5375 friend->id));
5376 else
5377 GNUNET_assert(0 == GNUNET_CRYPTO_cmp_peer_identity (&source,
5378 friend->id));
5379
5380 compare_and_update_predecessor (&source,
5381 trail,
5382 trail_length);
5383 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5384 friend->id);
5385 GNUNET_assert (NULL != target_friend);
5386 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (&trail_id,
5387 GDS_ROUTING_DEST_TO_SRC,
5388 target_friend);
5389 return;
5390 }
5391
5392 GNUNET_assert(trail_length > 0);
5393 /* I am part of trail to reach to successor. */
5394 my_index = search_my_index (trail, trail_length);
5395 if (-1 == my_index)
5396 {
5397 DEBUG ("No entry found in trail\n");
5398 GNUNET_break_op (0);
5399 return;
5400 }
5401 if((trail_length + 1) == my_index)
5402 {
5403 DEBUG ("Found twice in trail.\n");
5404 GNUNET_break_op (0);
5405 return;
5406 }
5407 if ((trail_length-1) == my_index)
5408 next_hop = new_successor;
5409 else
5410 next_hop = trail[my_index + 1];
5411
5412 GDS_ROUTING_add (&trail_id,
5413 friend->id,
5414 &next_hop);
5415 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5416 &next_hop);
5417 if (NULL == target_friend)
5418 {
5419 GNUNET_break(0);
5420 return;
5421 }
5422 GDS_NEIGHBOURS_send_notify_new_successor (&source,
5423 &new_successor,
5424 trail,
5425 trail_length,
5426 &trail_id,
5427 target_friend);
5428}
5429
5430
5431/**
5432 * Core handler for P2P notify successor message
5433 *
5434 * @param cls closure
5435 * @param notify_confirmation the message
5436 */
5437static void
5438handle_dht_p2p_notify_succ_confirmation (void *cls,
5439 const struct PeerNotifyConfirmationMessage *notify_confirmation)
5440{
5441 enum GDS_ROUTING_trail_direction trail_direction;
5442 struct GNUNET_HashCode trail_id;
5443 struct FriendInfo *target_friend;
5444 const struct GNUNET_PeerIdentity *next_hop;
5445
5446 GNUNET_STATISTICS_update (GDS_stats,
5447 gettext_noop ("# Bytes received from other peers"),
5448 ntohs (notify_confirmation->header.size),
5449 GNUNET_NO);
5450 trail_direction = ntohl (notify_confirmation->trail_direction);
5451 trail_id = notify_confirmation->trail_id;
5452
5453 next_hop = GDS_ROUTING_get_next_hop (&trail_id,
5454 trail_direction);
5455 if (NULL == next_hop)
5456 {
5457 /* The source of notify new successor, might have found even a better
5458 successor. In that case it send a trail teardown message, and hence,
5459 the next hop is NULL. */
5460 //Fixme: Add some print to confirm the above theory.
5461 return;
5462 }
5463
5464 /* I peer which sent the notify successor message to the successor. */
5465 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop,
5466 &my_identity))
5467 {
5468 /*
5469 * Schedule another round of verify sucessor with your current successor
5470 * which may or may not be source of this message. This message is used
5471 * only to ensure that we have a path setup to reach to our successor.
5472 */
5473
5474 // TODO: cancel schedule of notify_successor_retry_task
5475 if (send_notify_new_successor_retry_task != NULL)
5476 {
5477 struct SendNotifyContext *notify_ctx;
5478 notify_ctx = GNUNET_SCHEDULER_cancel(send_notify_new_successor_retry_task);
5479 GNUNET_free (notify_ctx->successor_trail);
5480 GNUNET_free (notify_ctx);
5481 send_notify_new_successor_retry_task = NULL;
5482 }
5483 if (send_verify_successor_task == NULL)
5484 {
5485 verify_successor_next_send_time.rel_value_us =
5486 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
5487 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
5488 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
5489 send_verify_successor_task
5490 = GNUNET_SCHEDULER_add_delayed(verify_successor_next_send_time,
5491 &send_verify_successor_message,
5492 NULL);
5493 }
5494 }
5495 else
5496 {
5497 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5498 next_hop);
5499 if (NULL == target_friend)
5500 {
5501 DEBUG ("\n friend not found, line number = %d",
5502 __LINE__);
5503 return;
5504 }
5505 GDS_NEIGHBOURS_send_notify_succcessor_confirmation (&trail_id,
5506 GDS_ROUTING_DEST_TO_SRC,
5507 target_friend);
5508 }
5509}
5510
5511
5512/**
5513 * Check integrity of P2P trail rejection message
5514 *
5515 * @param cls closure
5516 * @param trail_rejection the message
5517 * @return #GNUNET_OK if @a trail_rejection is well-formed
5518 */
5519static int
5520check_dht_p2p_trail_setup_rejection (void *cls,
5521 const struct PeerTrailRejectionMessage *trail_rejection)
5522{
5523 size_t msize;
5524
5525 msize = ntohs (trail_rejection->header.size);
5526 if ((msize - sizeof (struct PeerTrailRejectionMessage)) %
5527 sizeof (struct GNUNET_PeerIdentity) != 0)
5528 {
5529 GNUNET_break_op (0);
5530 return GNUNET_SYSERR;
5531 }
5532 return GNUNET_OK;
5533}
5534
5535
5536/**
5537 * Core handler for P2P trail rejection message
5538 *
5539 * @param cls closure
5540 * @param trail_rejection the message
5541 */
5542static void
5543handle_dht_p2p_trail_setup_rejection (void *cls,
5544 const struct PeerTrailRejectionMessage *trail_rejection)
5545{
5546 struct FriendInfo *friend = cls;
5547 unsigned int trail_length;
5548 const struct GNUNET_PeerIdentity *trail_peer_list;
5549 struct FriendInfo *target_friend;
5550 struct GNUNET_TIME_Relative congestion_timeout;
5551 struct GNUNET_HashCode trail_id;
5552 struct GNUNET_PeerIdentity next_peer;
5553 struct GNUNET_PeerIdentity source;
5554 uint64_t ultimate_destination_finger_value;
5555 unsigned int is_predecessor;
5556 struct Closest_Peer successor;
5557 size_t msize;
5558
5559 msize = ntohs (trail_rejection->header.size);
5560 trail_length = (msize - sizeof (struct PeerTrailRejectionMessage))/
5561 sizeof (struct GNUNET_PeerIdentity);
5562 GNUNET_STATISTICS_update (GDS_stats,
5563 gettext_noop ("# Bytes received from other peers"),
5564 msize,
5565 GNUNET_NO);
5566
5567 trail_peer_list = (const struct GNUNET_PeerIdentity *) &trail_rejection[1];
5568 is_predecessor = ntohl (trail_rejection->is_predecessor);
5569 congestion_timeout = trail_rejection->congestion_time;
5570 source = trail_rejection->source_peer;
5571 trail_id = trail_rejection->trail_id;
5572 ultimate_destination_finger_value
5573 = GNUNET_ntohll (trail_rejection->ultimate_destination_finger_value);
5574 /* First set the congestion time of the friend that sent you this message. */
5575 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5576 friend->id);
5577 if (NULL == target_friend)
5578 {
5579 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5580 GNUNET_break(0);
5581 return;
5582 }
5583 target_friend->congestion_timestamp
5584 = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
5585 congestion_timeout);
5586
5587 /* I am the source peer which wants to setup the trail. Do nothing.
5588 * send_find_finger_trail_task is scheduled periodically.*/
5589 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
5590 return;
5591
5592 /* If I am congested then pass this message to peer before me in trail. */
5593 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
5594 {
5595 /* First remove yourself from the trail. */
5596 unsigned int new_trail_length = trail_length - 1;
5597 struct GNUNET_PeerIdentity trail[new_trail_length];
5598
5599 GNUNET_memcpy (trail,
5600 trail_peer_list,
5601 new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5602 if (0 == trail_length)
5603 next_peer = source;
5604 else
5605 next_peer = trail[new_trail_length-1];
5606
5607 target_friend
5608 = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5609 &next_peer);
5610 if (NULL == target_friend)
5611 {
5612 DEBUG ("\nLINE = %d ,No friend found.",
5613 __LINE__);
5614 GNUNET_break(0);
5615 return;
5616 }
5617 GDS_NEIGHBOURS_send_trail_rejection (&source,
5618 ultimate_destination_finger_value,
5619 &my_identity,
5620 is_predecessor,
5621 trail,
5622 new_trail_length,
5623 &trail_id,
5624 target_friend,
5625 CONGESTION_TIMEOUT);
5626 return;
5627 }
5628
5629 successor = find_local_best_known_next_hop (ultimate_destination_finger_value,
5630 is_predecessor);
5631
5632 /* Am I the final destination? */
5633 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&successor.best_known_destination,
5634 &my_identity))
5635 {
5636 /*Here you are already part of trail. Copy the trail removing yourself. */
5637 unsigned int new_trail_length = trail_length - 1;
5638 struct GNUNET_PeerIdentity trail[new_trail_length];
5639
5640 GNUNET_memcpy (trail,
5641 trail_peer_list,
5642 new_trail_length * sizeof(struct GNUNET_PeerIdentity));
5643
5644 if (0 == new_trail_length)
5645 next_peer = source;
5646 else
5647 {
5648 next_peer = trail[new_trail_length-1];
5649 }
5650 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5651 &next_peer);
5652
5653 if (NULL == target_friend)
5654 {
5655 DEBUG ("\nLINE = %d ,No friend found.",
5656 __LINE__);
5657 GNUNET_break(0);
5658 return;
5659 }
5660 GDS_NEIGHBOURS_send_trail_setup_result (&source,
5661 &my_identity,
5662 target_friend,
5663 new_trail_length,
5664 trail,
5665 is_predecessor,
5666 ultimate_destination_finger_value,
5667 &trail_id);
5668 return;
5669 }
5670 /* Here I was already part of trail. So no need to add. */
5671 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5672 &successor.next_hop);
5673 if (NULL == target_friend)
5674 {
5675 DEBUG ("\nLINE = %d ,No friend found.",__LINE__);
5676 GNUNET_break (0);
5677 return;
5678 }
5679 GDS_NEIGHBOURS_send_trail_setup (&source,
5680 ultimate_destination_finger_value,
5681 &successor.best_known_destination,
5682 target_friend,
5683 trail_length,
5684 trail_peer_list,
5685 is_predecessor,
5686 &trail_id,
5687 &successor.trail_id);
5688}
5689
5690
5691/**
5692 * Core handler for trail teardown message.
5693 *
5694 * @param cls closure
5695 * @param trail_teardown the message
5696 */
5697static void
5698handle_dht_p2p_trail_teardown (void *cls,
5699 const struct PeerTrailTearDownMessage *trail_teardown)
5700{
5701 enum GDS_ROUTING_trail_direction trail_direction;
5702 struct GNUNET_HashCode trail_id;
5703 const struct GNUNET_PeerIdentity *next_hop;
5704 size_t msize;
5705
5706 msize = ntohs (trail_teardown->header.size);
5707 GNUNET_STATISTICS_update (GDS_stats,
5708 gettext_noop ("# Bytes received from other peers"),
5709 msize,
5710 GNUNET_NO);
5711 trail_direction = ntohl (trail_teardown->trail_direction);
5712 trail_id = trail_teardown->trail_id;
5713
5714 /* Check if peer is the real peer from which we should get this message.*/
5715 /* Get the prev_hop for this trail by getting the next hop in opposite direction. */
5716#if 0
5717 GNUNET_assert (NULL != (prev_hop =
5718 GDS_ROUTING_get_next_hop (trail_id, ! trail_direction)));
5719 if (0 != GNUNET_CRYPTO_cmp_peer_identity (prev_hop,
5720 friend->id))
5721 {
5722 GNUNET_break (0);
5723 return;
5724 }
5725#endif
5726
5727 next_hop = GDS_ROUTING_get_next_hop (&trail_id,
5728 trail_direction);
5729 if (NULL == next_hop)
5730 {
5731 DEBUG(" NO ENTRY FOUND IN %s ROUTING TABLE for trail id %s, line %u",
5732 GNUNET_i2s (&my_identity),
5733 GNUNET_h2s (&trail_id),
5734 __LINE__);
5735 GNUNET_break (0);
5736 return;
5737 }
5738
5739 /* I am the next hop, which means I am the final destination. */
5740 if (0 == GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity))
5741 {
5742 GNUNET_assert (GNUNET_YES ==
5743 GDS_ROUTING_remove_trail (&trail_id));
5744 return;
5745 }
5746 /* If not final destination, then send a trail teardown message to next hop.*/
5747 GNUNET_assert (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5748 next_hop));
5749 GNUNET_assert (GNUNET_YES ==
5750 GDS_ROUTING_remove_trail (&trail_id));
5751 GDS_NEIGHBOURS_send_trail_teardown (&trail_id,
5752 trail_direction,
5753 next_hop);
5754}
5755
5756
5757/**
5758 * Check validity of p2p add trail message.
5759 *
5760 * @param cls closure
5761 * @param add_trail the message
5762 * @return #GNUNET_OK if @a add_trail is well-formed
5763 */
5764static int
5765check_dht_p2p_add_trail (void *cls,
5766 const struct PeerAddTrailMessage *add_trail)
5767{
5768 size_t msize;
5769
5770 msize = ntohs (add_trail->header.size);
5771 if ((msize - sizeof (struct PeerAddTrailMessage)) %
5772 sizeof (struct GNUNET_PeerIdentity) != 0)
5773 {
5774 GNUNET_break_op (0);
5775 return GNUNET_SYSERR;
5776 }
5777 return GNUNET_OK;
5778}
5779
5780
5781/**
5782 * Core handle for p2p add trail message.
5783 *
5784 * @param cls closure
5785 * @param add_trail the message
5786 */
5787static void
5788handle_dht_p2p_add_trail (void *cls,
5789 const struct PeerAddTrailMessage *add_trail)
5790{
5791 struct FriendInfo *friend = cls;
5792 const struct GNUNET_PeerIdentity *trail;
5793 struct GNUNET_HashCode trail_id;
5794 struct GNUNET_PeerIdentity destination_peer;
5795 struct GNUNET_PeerIdentity source_peer;
5796 struct GNUNET_PeerIdentity next_hop;
5797 unsigned int trail_length;
5798 unsigned int my_index;
5799 size_t msize;
5800
5801 msize = ntohs (add_trail->header.size);
5802 /* In this message we pass the whole trail from source to destination as we
5803 * are adding that trail.*/
5804 //FIXME: failed when run with 1000 pears. check why.
5805 trail_length = (msize - sizeof (struct PeerAddTrailMessage))/
5806 sizeof (struct GNUNET_PeerIdentity);
5807 GNUNET_STATISTICS_update (GDS_stats,
5808 gettext_noop ("# Bytes received from other peers"),
5809 msize,
5810 GNUNET_NO);
5811
5812 trail = (const struct GNUNET_PeerIdentity *) &add_trail[1];
5813 destination_peer = add_trail->destination_peer;
5814 source_peer = add_trail->source_peer;
5815 trail_id = add_trail->trail_id;
5816
5817 /* I am not the destination of the trail. */
5818 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
5819 &destination_peer))
5820 {
5821 struct FriendInfo *target_friend;
5822
5823 /* Get my location in the trail. */
5824 my_index = search_my_index (trail, trail_length);
5825 if (-1 == my_index)
5826 {
5827 GNUNET_break_op (0);
5828 return;
5829 }
5830 if((trail_length + 1) == my_index)
5831 {
5832 DEBUG ("Found twice in trail.\n");
5833 GNUNET_break_op (0);
5834 return;
5835 }
5836 if ((trail_length - 1) == my_index)
5837 {
5838 next_hop = destination_peer;
5839 }
5840 else
5841 {
5842 next_hop = trail[my_index + 1];
5843 }
5844 /* Add in your routing table. */
5845 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (&trail_id,
5846 friend->id,
5847 &next_hop));
5848 //GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (trail_id, next_hop, *peer));
5849 GNUNET_assert (NULL !=
5850 (target_friend =
5851 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5852 &next_hop)));
5853 GDS_NEIGHBOURS_send_add_trail (&source_peer,
5854 &destination_peer,
5855 &trail_id,
5856 trail,
5857 trail_length,
5858 target_friend);
5859 return;
5860 }
5861 /* I am the destination. Add an entry in routing table. */
5862 GNUNET_assert (GNUNET_OK == GDS_ROUTING_add (&trail_id,
5863 friend->id,
5864 &my_identity));
5865}
5866
5867
5868/**
5869 * Free the finger trail in which the first friend to reach to a finger is
5870 * disconnected_friend. Also remove entry from routing table for that particular
5871 * trail id.
5872 * @param disconnected_friend PeerIdentity of friend which got disconnected
5873 * @param remove_finger Finger whose trail we need to check if it has
5874 * disconnected_friend as the first hop.
5875 * @return Total number of trails in which disconnected_friend was the first
5876 * hop.
5877 */
5878static int
5879remove_matching_trails (const struct GNUNET_PeerIdentity *disconnected_friend,
5880 struct FingerInfo *finger)
5881{
5882 const struct GNUNET_PeerIdentity *next_hop;
5883 struct FriendInfo *remove_friend;
5884 struct Trail *current_trail;
5885 unsigned int matching_trails_count = 0;
5886 int i;
5887
5888 /* Iterate over all the trails of finger. */
5889 for (i = 0; i < finger->trails_count; i++)
5890 {
5891 current_trail = &finger->trail_list[i];
5892 if (GNUNET_NO == current_trail->is_present)
5893 continue;
5894
5895 /* First friend to reach to finger is disconnected_peer. */
5896 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&current_trail->trail_head->peer,
5897 disconnected_friend))
5898 {
5899 remove_friend =
5900 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5901 disconnected_friend);
5902 GNUNET_assert (NULL != remove_friend);
5903 next_hop = GDS_ROUTING_get_next_hop (&current_trail->trail_id,
5904 GDS_ROUTING_SRC_TO_DEST);
5905
5906 /* Here it may happen that as all the peers got disconnected, the entry in
5907 routing table for that particular trail has been removed, because the
5908 previously disconnected peer was either a next hop or prev hop of that
5909 peer. */
5910 if (NULL != next_hop)
5911 {
5912 GNUNET_assert (0 == (GNUNET_CRYPTO_cmp_peer_identity (disconnected_friend,
5913 next_hop)));
5914 GNUNET_assert (GNUNET_YES ==
5915 GDS_ROUTING_remove_trail (&current_trail->trail_id));
5916 }
5917 matching_trails_count++;
5918 free_trail (current_trail);
5919 current_trail->is_present = GNUNET_NO;
5920 }
5921 }
5922 return matching_trails_count;
5923}
5924
5925
5926/**
5927 * Iterate over finger_table entries.
5928 * 0. Ignore finger which is my_identity or if no valid entry present at
5929 * that finger index.
5930 * 1. If disconnected_friend is a finger, then remove the routing entry from
5931 your own table. Free the trail.
5932 * 2. Check if disconnected_friend is the first friend in the trail to reach to a finger.
5933 * 2.1 Remove all the trails and entry from routing table in which disconnected
5934 * friend is the first friend in the trail. If disconnected_friend is the
5935 * first friend in all the trails to reach finger, then remove the finger.
5936 * @param disconnected_friend Peer identity of friend which got disconnected.
5937 */
5938static void
5939remove_matching_fingers (const struct GNUNET_PeerIdentity *disconnected_peer)
5940{
5941 struct FingerInfo *current_finger;
5942 int removed_trails_count;
5943 int i;
5944
5945 /* Iterate over finger table entries. */
5946 for (i = 0; i < MAX_FINGERS; i++)
5947 {
5948 current_finger = &finger_table[i];
5949
5950 /* No finger stored at this trail index or I am the finger. */
5951 if ((GNUNET_NO == current_finger->is_present) ||
5952 (0 == GNUNET_CRYPTO_cmp_peer_identity (&current_finger->finger_identity,
5953 &my_identity)))
5954 continue;
5955
5956 /* Is disconnected_peer a finger? */
5957 if (0 == GNUNET_CRYPTO_cmp_peer_identity (disconnected_peer,
5958 &current_finger->finger_identity))
5959 {
5960 remove_existing_finger (current_finger, i);
5961 }
5962
5963 /* If finger is a friend but not disconnected_friend, then continue. */
5964 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
5965 &current_finger->finger_identity))
5966 continue;
5967
5968 /* Iterate over the list of trails to reach remove_finger. Check if
5969 * disconnected_friend is the first friend in any of the trail. */
5970 removed_trails_count = remove_matching_trails (disconnected_peer,
5971 current_finger);
5972 current_finger->trails_count =
5973 current_finger->trails_count - removed_trails_count;
5974 if (0 == current_finger->trails_count)
5975 {
5976 current_finger->is_present = GNUNET_NO;
5977 memset (&finger_table[i],
5978 0,
5979 sizeof (finger_table[i]));
5980 }
5981 }
5982}
5983
5984
5985/**
5986 * Method called whenever a peer disconnects.
5987 *
5988 * @param cls closure
5989 * @param peer peer identity this notification is about
5990 * @param internal_cls our `struct FriendInfo` for @a peer
5991 */
5992static void
5993handle_core_disconnect (void *cls,
5994 const struct GNUNET_PeerIdentity *peer,
5995 void *internal_cls)
5996{
5997 struct FriendInfo *remove_friend = internal_cls;
5998
5999 /* If disconnected to own identity, then return. */
6000 if (NULL == remove_friend)
6001 return;
6002 remove_matching_fingers (peer);
6003 GNUNET_assert (GNUNET_SYSERR !=
6004 GDS_ROUTING_remove_trail_by_peer (peer));
6005 GNUNET_assert (GNUNET_YES ==
6006 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
6007 peer,
6008 remove_friend));
6009 if (0 != GNUNET_CONTAINER_multipeermap_size (friend_peermap))
6010 return;
6011
6012 if (NULL != find_finger_trail_task)
6013 {
6014 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6015 find_finger_trail_task = NULL;
6016 }
6017 else
6018 GNUNET_break (0);
6019}
6020
6021
6022/**
6023 * Method called whenever a peer connects.
6024 *
6025 * @param cls closure
6026 * @param peer_identity peer identity this notification is about
6027 * @param mq message queue for sending data to @a peer
6028 * @return our `struct FriendInfo` for this peer
6029 */
6030static void *
6031handle_core_connect (void *cls,
6032 const struct GNUNET_PeerIdentity *peer_identity,
6033 struct GNUNET_MQ_Handle *mq)
6034{
6035 struct FriendInfo *friend;
6036
6037 /* Check for connect to self message */
6038 if (0 == memcmp (&my_identity,
6039 peer_identity,
6040 sizeof (struct GNUNET_PeerIdentity)))
6041 return NULL;
6042 friend = GNUNET_new (struct FriendInfo);
6043 friend->id = peer_identity;
6044 friend->mq = mq;
6045 GNUNET_assert (GNUNET_OK ==
6046 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
6047 friend->id,
6048 friend,
6049 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
6050
6051 /* FIXME: now we are not making a distinction between fingers which are friends
6052 * also.But later, we should add a congestion timestamp on the friend, so that it is
6053 * selected after some time out. This is to ensure that both peers have added
6054 * each other as their friend. */
6055 /* Got a first connection, good time to start with FIND FINGER TRAIL requests...*/
6056 if (NULL == find_finger_trail_task)
6057 {
6058 find_finger_trail_task
6059 = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message,
6060 NULL);
6061 }
6062 return friend;
6063}
6064
6065
6066/**
6067 * To be called on core init/fail.
6068 *
6069 * @param cls service closure
6070 * @param identity the public identity of this peer
6071 */
6072static void
6073core_init (void *cls,
6074 const struct GNUNET_PeerIdentity *identity)
6075{
6076 my_identity = *identity;
6077}
6078
6079
6080/**
6081 * Initialize finger table entries.
6082 */
6083static void
6084finger_table_init ()
6085{
6086 memset (&finger_table, 0, sizeof (finger_table));
6087}
6088
6089
6090/**
6091 * Initialize neighbours subsystem.
6092 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
6093 */
6094int
6095GDS_NEIGHBOURS_init (void)
6096{
6097 struct GNUNET_MQ_MessageHandler core_handlers[] = {
6098 GNUNET_MQ_hd_var_size (dht_p2p_put,
6099 GNUNET_MESSAGE_TYPE_XDHT_P2P_PUT,
6100 struct PeerPutMessage,
6101 NULL),
6102 GNUNET_MQ_hd_var_size (dht_p2p_get,
6103 GNUNET_MESSAGE_TYPE_XDHT_P2P_GET,
6104 struct PeerGetMessage,
6105 NULL),
6106 GNUNET_MQ_hd_var_size (dht_p2p_get_result,
6107 GNUNET_MESSAGE_TYPE_XDHT_P2P_GET_RESULT,
6108 struct PeerGetResultMessage,
6109 NULL),
6110 GNUNET_MQ_hd_var_size (dht_p2p_trail_setup,
6111 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP,
6112 struct PeerTrailSetupMessage,
6113 NULL),
6114 GNUNET_MQ_hd_var_size (dht_p2p_trail_setup_result,
6115 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_RESULT,
6116 struct PeerTrailSetupResultMessage,
6117 NULL),
6118 GNUNET_MQ_hd_var_size (dht_p2p_verify_successor,
6119 GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR,
6120 struct PeerVerifySuccessorMessage,
6121 NULL),
6122 GNUNET_MQ_hd_var_size (dht_p2p_verify_successor_result,
6123 GNUNET_MESSAGE_TYPE_XDHT_P2P_VERIFY_SUCCESSOR_RESULT,
6124 struct PeerVerifySuccessorResultMessage,
6125 NULL),
6126 GNUNET_MQ_hd_var_size (dht_p2p_notify_new_successor,
6127 GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_NEW_SUCCESSOR,
6128 struct PeerNotifyNewSuccessorMessage,
6129 NULL),
6130 GNUNET_MQ_hd_var_size (dht_p2p_trail_setup_rejection,
6131 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_SETUP_REJECTION,
6132 struct PeerTrailRejectionMessage,
6133 NULL),
6134 GNUNET_MQ_hd_fixed_size (dht_p2p_trail_teardown,
6135 GNUNET_MESSAGE_TYPE_XDHT_P2P_TRAIL_TEARDOWN,
6136 struct PeerTrailTearDownMessage,
6137 NULL),
6138 GNUNET_MQ_hd_var_size (dht_p2p_add_trail,
6139 GNUNET_MESSAGE_TYPE_XDHT_P2P_ADD_TRAIL,
6140 struct PeerAddTrailMessage,
6141 NULL),
6142 GNUNET_MQ_hd_fixed_size (dht_p2p_notify_succ_confirmation,
6143 GNUNET_MESSAGE_TYPE_XDHT_P2P_NOTIFY_SUCCESSOR_CONFIRMATION,
6144 struct PeerNotifyConfirmationMessage,
6145 NULL),
6146 GNUNET_MQ_handler_end ()
6147 };
6148
6149 core_api = GNUNET_CORE_connect (GDS_cfg,
6150 NULL,
6151 &core_init,
6152 &handle_core_connect,
6153 &handle_core_disconnect,
6154 core_handlers);
6155 if (NULL == core_api)
6156 return GNUNET_SYSERR;
6157 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256,
6158 GNUNET_YES);
6159 finger_table_init ();
6160 successor_times = 10;
6161 fingers_round_count = 5;
6162 find_finger_trail_task_next_send_time.rel_value_us =
6163 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
6164 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6165 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us);
6166
6167 verify_successor_next_send_time.rel_value_us =
6168 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us +
6169 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6170 DHT_SEND_VERIFY_SUCCESSOR_INTERVAL.rel_value_us);
6171
6172 verify_successor_retry_time.rel_value_us =
6173 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6174 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6175 DHT_SEND_VERIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6176
6177 notify_successor_retry_time.rel_value_us =
6178 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us +
6179 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
6180 DHT_SEND_NOTIFY_SUCCESSOR_RETRY_INTERVAL.rel_value_us);
6181
6182 return GNUNET_OK;
6183}
6184
6185
6186/**
6187 * Free the memory held up by trails of a finger.
6188 */
6189static void
6190delete_finger_table_entries()
6191{
6192 for (unsigned int i = 0; i < MAX_FINGERS; i++)
6193 {
6194 if (GNUNET_YES != finger_table[i].is_present)
6195 continue;
6196 for (unsigned int j = 0; j < finger_table[i].trails_count; j++)
6197 free_trail(&finger_table[i].trail_list[j]);
6198 }
6199}
6200
6201
6202/**
6203 * Shutdown neighbours subsystem.
6204 */
6205void
6206GDS_NEIGHBOURS_done (void)
6207{
6208 if (NULL == core_api)
6209 return;
6210
6211 GNUNET_CORE_disconnect (core_api);
6212 core_api = NULL;
6213
6214 delete_finger_table_entries();
6215 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
6216 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
6217 friend_peermap = NULL;
6218
6219 if (NULL != find_finger_trail_task)
6220 {
6221 GNUNET_SCHEDULER_cancel (find_finger_trail_task);
6222 find_finger_trail_task = NULL;
6223 }
6224
6225 if (NULL != send_verify_successor_task)
6226 {
6227 GNUNET_SCHEDULER_cancel (send_verify_successor_task);
6228 send_verify_successor_task = NULL;
6229 }
6230 if (NULL != send_verify_successor_retry_task)
6231 {
6232 struct VerifySuccessorContext *ctx;
6233
6234 ctx = GNUNET_SCHEDULER_cancel (send_verify_successor_retry_task);
6235 GNUNET_free (ctx);
6236 send_verify_successor_retry_task = NULL;
6237 }
6238 if (NULL != send_notify_new_successor_retry_task)
6239 {
6240 struct SendNotifyContext *notify_ctx;
6241
6242 notify_ctx = GNUNET_SCHEDULER_cancel (send_notify_new_successor_retry_task);
6243 GNUNET_free (notify_ctx->successor_trail);
6244 GNUNET_free (notify_ctx);
6245 send_notify_new_successor_retry_task = NULL;
6246 }
6247}
6248
6249
6250/**
6251 * Get my identity
6252 *
6253 * @return my identity
6254 */
6255struct GNUNET_PeerIdentity *
6256GDS_NEIGHBOURS_get_id (void)
6257{
6258 return &my_identity;
6259}
6260
6261/* end of gnunet-service-xdht_neighbours.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-02 02:40:30 +0000