aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSupriti Singh <supritisingh08@gmail.com>2014-05-27 14:43:12 +0000
committerSupriti Singh <supritisingh08@gmail.com>2014-05-27 14:43:12 +0000
commit30266f09b66c2ceda6a7608626d30c6244d57891 (patch)
treee7e005e9f893ae26e07265aa369667d3275bb522
parent548353c4b32e151a965d2512ff9a4fc053f0f2ca (diff)
downloadgnunet-30266f09b66c2ceda6a7608626d30c6244d57891.tar.gz
gnunet-30266f09b66c2ceda6a7608626d30c6244d57891.zip
Using trail id
Finger table add functionality complete Adding a new message trail compression
-rw-r--r--src/dht/gnunet-service-xdht_neighbours.c4314
-rw-r--r--src/dht/gnunet-service-xdht_routing.c320
-rw-r--r--src/dht/gnunet-service-xdht_routing.h104
-rw-r--r--src/include/gnunet_protocols.h7
4 files changed, 1582 insertions, 3163 deletions
diff --git a/src/dht/gnunet-service-xdht_neighbours.c b/src/dht/gnunet-service-xdht_neighbours.c
index 38309d5d4..3aac5ad59 100644
--- a/src/dht/gnunet-service-xdht_neighbours.c
+++ b/src/dht/gnunet-service-xdht_neighbours.c
@@ -44,7 +44,6 @@
44#include <fenv.h> 44#include <fenv.h>
45#include "dht.h" 45#include "dht.h"
46 46
47
48/** 47/**
49 * Maximum possible fingers of a peer. 48 * Maximum possible fingers of a peer.
50 */ 49 */
@@ -73,191 +72,30 @@
73/** 72/**
74 * Maximum number of trails stored per finger. 73 * Maximum number of trails stored per finger.
75 */ 74 */
76#define TRAILS_COUNT 2 75#define MAXIMUM_TRAILS_PER_FINGER 2
77 76
78/** 77/**
79 * Used to distinguish put/get request use of find_successor() from others 78 * Used to distinguish put/get request use of find_successor() from others
80 */ 79 */
81#define PUT_GET_REQUEST 65 80#define PUT_GET_REQUEST 65
82 81
83
84GNUNET_NETWORK_STRUCT_BEGIN
85
86/**
87 * P2P PUT message
88 */
89struct PeerPutMessage
90{
91 /**
92 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
93 */
94 struct GNUNET_MessageHeader header;
95
96 /**
97 * Processing options
98 */
99 uint32_t options GNUNET_PACKED;
100
101 /**
102 * Content type.
103 */
104 uint32_t block_type GNUNET_PACKED;
105
106 /**
107 * Hop count
108 */
109 uint32_t hop_count GNUNET_PACKED;
110
111 /**
112 * Replication level for this message
113 * In the current implementation, this value is not used.
114 */
115 uint32_t desired_replication_level GNUNET_PACKED;
116
117 /**
118 * Length of the PUT path that follows (if tracked).
119 */
120 uint32_t put_path_length GNUNET_PACKED;
121
122 /**
123 * Current destination to which this message is forwarded.
124 */
125 struct GNUNET_PeerIdentity current_destination;
126
127 /**
128 * Peer whose finger is current_destination.
129 */
130 struct GNUNET_PeerIdentity current_source;
131
132 /**
133 * When does the content expire?
134 */
135 struct GNUNET_TIME_AbsoluteNBO expiration_time;
136
137 /**
138 * The key to store the value under.
139 */
140 struct GNUNET_HashCode key GNUNET_PACKED;
141
142 /* put path (if tracked) */
143
144 /* Payload */
145
146};
147
148
149/** 82/**
150 * P2P Result message 83 * Finger map index for predecessor entry in finger peermap.
151 */ 84 */
152struct PeerGetResultMessage 85#define PREDECESSOR_FINGER_ID 64
153{
154 /**
155 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT
156 */
157 struct GNUNET_MessageHeader header;
158
159 /**
160 * The type for the data.
161 */
162 uint32_t type GNUNET_PACKED;
163
164 /**
165 * Number of peers recorded in the outgoing path from source to the
166 * stored location of this message.
167 */
168 uint32_t put_path_length GNUNET_PACKED;
169
170 /**
171 * Length of the GET path that follows (if tracked).
172 */
173 uint32_t get_path_length GNUNET_PACKED;
174
175 /**
176 * Peer which will receive the get result message.
177 */
178 struct GNUNET_PeerIdentity source_peer;
179
180 /**
181 * When does the content expire?
182 */
183 struct GNUNET_TIME_Absolute expiration_time;
184
185 /**
186 * The key of the corresponding GET request.
187 */
188 struct GNUNET_HashCode key;
189
190 /* put path (if tracked) */
191
192 /* get path (if tracked) */
193
194 /* Payload */
195
196};
197
198 86
199/** 87/**
200 * P2P GET message 88 * Maximum number of trails allowed to go through a friend.
201 */ 89 */
202struct PeerGetMessage 90#define TRAILS_THROUGH_FRIEND_THRESHOLD 64
203{
204 /**
205 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
206 */
207 struct GNUNET_MessageHeader header;
208
209 /**
210 * Processing options
211 */
212 uint32_t options GNUNET_PACKED;
213
214 /**
215 * Desired content type.
216 */
217 uint32_t block_type GNUNET_PACKED;
218
219 /**
220 * Hop count
221 */
222 uint32_t hop_count GNUNET_PACKED;
223
224 /**
225 * Desired replication level for this request.
226 * In the current implementation, this value is not used.
227 */
228 uint32_t desired_replication_level GNUNET_PACKED;
229
230 /**
231 * Total number of peers in get path.
232 */
233 unsigned int get_path_length;
234
235 /**
236 * Peer which is an intermediate destination.
237 */
238 struct GNUNET_PeerIdentity current_destination;
239
240 /**
241 * Source for which current_destination is the finger.
242 */
243 struct GNUNET_PeerIdentity current_source;
244
245 /**
246 * The key we are looking for.
247 */
248 struct GNUNET_HashCode key;
249
250 /* Get path. */
251
252};
253 91
92GNUNET_NETWORK_STRUCT_BEGIN
254 93
255/** 94/**
256 * P2P Trail setup message 95 * P2P Trail setup message
257 */ 96 */
258struct PeerTrailSetupMessage 97struct PeerTrailSetupMessage
259{ 98{
260
261 /** 99 /**
262 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP 100 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
263 */ 101 */
@@ -266,7 +104,7 @@ struct PeerTrailSetupMessage
266 /** 104 /**
267 * Peer closest to this value will be our finger. 105 * Peer closest to this value will be our finger.
268 */ 106 */
269 uint64_t destination_finger; 107 uint64_t ultimate_destination_finger;
270 108
271 /** 109 /**
272 * Source peer which wants to setup the trail to one of its finger. 110 * Source peer which wants to setup the trail to one of its finger.
@@ -276,15 +114,7 @@ struct PeerTrailSetupMessage
276 /** 114 /**
277 * Peer to which this packet is forwarded. 115 * Peer to which this packet is forwarded.
278 */ 116 */
279 struct GNUNET_PeerIdentity current_destination; 117 struct GNUNET_PeerIdentity next_destination;
280
281 /**
282 * In case the packet is forwarded to an intermediate finger, then
283 * current_source contains the peer id whose finger is the intermediate
284 * finger. In case the packet is forwarded to a friend, then it is NULL.
285 * FIXME: check the usage of current_source and fix this comment.
286 */
287 struct GNUNET_PeerIdentity current_source;
288 118
289 /** 119 /**
290 * Index into finger peer map, in Network Byte Order. 120 * Index into finger peer map, in Network Byte Order.
@@ -296,12 +126,21 @@ struct PeerTrailSetupMessage
296 */ 126 */
297 uint32_t trail_length GNUNET_PACKED; 127 uint32_t trail_length GNUNET_PACKED;
298 128
129 /**
130 * Trail id of any intermediate trail we may encounter while doing trail setup.
131 */
132 struct GNUNET_HashCode intermediate_trail_id;
133
134 /**
135 * Trail id for trail which we are trying to setup.
136 */
137 struct GNUNET_HashCode new_trail_id;
138
299 /* Trail formed in the process. */ 139 /* Trail formed in the process. */
300}; 140};
301 141
302
303/** 142/**
304 * P2P Trail Setup Result message 143 * P2P Trail Setup Result message
305 */ 144 */
306struct PeerTrailSetupResultMessage 145struct PeerTrailSetupResultMessage
307{ 146{
@@ -331,63 +170,16 @@ struct PeerTrailSetupResultMessage
331 */ 170 */
332 uint32_t trail_length GNUNET_PACKED; 171 uint32_t trail_length GNUNET_PACKED;
333 172
334 /* Trail from destination_peer to finger_identity */
335
336};
337
338
339/**
340 * P2P Trail Rejection Message.
341 */
342struct PeerTrailRejectionMessage
343{
344 /**
345 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
346 */
347 struct GNUNET_MessageHeader header;
348
349 /**
350 * Source peer which wants to set up the trail.
351 */
352 struct GNUNET_PeerIdentity source_peer;
353
354 /**
355 * Peer which sent trail rejection message.
356 */
357 struct GNUNET_PeerIdentity congested_peer;
358
359 /** 173 /**
360 * Peer identity which will be successor to this value will be finger of 174 * Identifier of the trail.
361 * source_peer.
362 */ 175 */
363 uint64_t finger_identity_value; 176 struct GNUNET_HashCode trail_id;
364 177 /* Trail from destination_peer to finger_identity */
365 /**
366 * Index in finger peer map of source peer.
367 */
368 uint32_t finger_map_index;
369
370 /**
371 * Total number of peers in the trail.
372 */
373 uint32_t trail_length;
374
375 /**
376 * Relative time for which congested_peer will remain congested.
377 */
378 struct GNUNET_TIME_Relative congestion_time;
379 178
380 /* Trail_list from source_peer to peer which sent the message for trail setup
381 * to congested peer.*/
382}; 179};
383 180
384
385/**
386 * P2P Verify Successor message.
387 */
388struct PeerVerifySuccessorMessage 181struct PeerVerifySuccessorMessage
389{ 182{
390
391 /** 183 /**
392 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR 184 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
393 */ 185 */
@@ -404,20 +196,13 @@ struct PeerVerifySuccessorMessage
404 struct GNUNET_PeerIdentity successor; 196 struct GNUNET_PeerIdentity successor;
405 197
406 /** 198 /**
407 * Total number of peers in trail to current successor. 199 * Identifier of trail to reach from source_peer to successor.
408 */ 200 */
409 uint32_t trail_length; 201 struct GNUNET_HashCode trail_id;
410
411 /* Trail to reach to from source_peer to successor. */
412}; 202};
413 203
414
415/**
416 * P2P Verify Successor Result message.
417 */
418struct PeerVerifySuccessorResultMessage 204struct PeerVerifySuccessorResultMessage
419{ 205{
420
421 /** 206 /**
422 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT 207 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
423 */ 208 */
@@ -439,21 +224,21 @@ struct PeerVerifySuccessorResultMessage
439 struct GNUNET_PeerIdentity my_predecessor; 224 struct GNUNET_PeerIdentity my_predecessor;
440 225
441 /** 226 /**
442 * Total number of peers in trail. 227 * Trail identifier of trail from my_predecessor to source_successor.
228 */
229 struct GNUNET_HashCode trail_id;
230
231 enum GDS_ROUTING_trail_direction trail_direction;
232 /**
233 * Total number of peers in trail from source_successor to my_predecessor
234 * if my_predecessor is not same as destination_peer.
443 */ 235 */
444 uint32_t trail_length; 236 uint32_t trail_length;
445 237
446 /* Trail to reach from destination_peer to its correct successor. 238 /* Trail from source_successor to my_predecessor where
447 * If source_successor is not destination peer, then trail is from destination_peer 239 * my_predecessor != destination_peer*/
448 * to my_predecessor.
449 * If source_successor is destination peer, then trail is from destination_peer
450 * to source_successor. */
451}; 240};
452 241
453
454/**
455 * P2P Notify New Successor message.
456 */
457struct PeerNotifyNewSuccessorMessage 242struct PeerNotifyNewSuccessorMessage
458{ 243{
459 /** 244 /**
@@ -466,28 +251,25 @@ struct PeerNotifyNewSuccessorMessage
466 */ 251 */
467 struct GNUNET_PeerIdentity source_peer; 252 struct GNUNET_PeerIdentity source_peer;
468 253
469 /**
470 * Old successor of source peer.
471 */
472 struct GNUNET_PeerIdentity old_successor;
473
474 /** 254 /**
475 * New successor identity. 255 * New successor identity.
476 */ 256 */
477 struct GNUNET_PeerIdentity destination_peer; 257 struct GNUNET_PeerIdentity destination_peer;
478 258
479 /** 259 unsigned int trail_length;
480 * Number of peers in trail from source_peer to new successor. 260
481 */ 261 struct GNUNET_HashCode trail_id;
482 uint32_t trail_length;
483 262
484 /* Trail to from source_peer to destination_peer. */ 263 /* Trail. */
485}; 264};
486 265
487struct PeerTrailTearDownMessage 266/**
267 * Trail compressiong message.
268 */
269struct PeerTrailCompressionMessage
488{ 270{
489 /** 271 /**
490 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN 272 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION
491 */ 273 */
492 struct GNUNET_MessageHeader header; 274 struct GNUNET_MessageHeader header;
493 275
@@ -497,7 +279,7 @@ struct PeerTrailTearDownMessage
497 struct GNUNET_PeerIdentity source_peer; 279 struct GNUNET_PeerIdentity source_peer;
498 280
499 /** 281 /**
500 * Destination peer of this trail. 282 * Destination of this trail.
501 */ 283 */
502 struct GNUNET_PeerIdentity destination_peer; 284 struct GNUNET_PeerIdentity destination_peer;
503 285
@@ -507,44 +289,75 @@ struct PeerTrailTearDownMessage
507 * destination. 289 * destination.
508 */ 290 */
509 struct GNUNET_PeerIdentity new_first_friend; 291 struct GNUNET_PeerIdentity new_first_friend;
292
510 /** 293 /**
511 * Number of peers in trail from source_peer to new first friend. 294 * Unique identifier of trail.
512 */ 295 */
513 uint32_t trail_length; 296 struct GNUNET_HashCode trail_id;
514
515 /* Trail from source_peer to new first friend. */
516}; 297};
517 298
299/**
300 * Trail Tear Down message.
301 */
302struct PeerTrailTearDownMessage
303{
304 /**
305 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN
306 */
307 struct GNUNET_MessageHeader header;
308};
518 309
519struct PeerAddTrailMessage 310/**
311 * Trail Rejection Message.
312 */
313struct PeerTrailRejectionMessage
520{ 314{
521 /** 315 /**
522 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL 316 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION
523 */ 317 */
524 struct GNUNET_MessageHeader header; 318 struct GNUNET_MessageHeader header;
525 319
526 /** 320 /**
527 * Source peer of the routing trail. 321 * Source peer which wants to set up the trail.
528 */ 322 */
529 struct GNUNET_PeerIdentity source_peer; 323 struct GNUNET_PeerIdentity source_peer;
530 324
531 /** 325 /**
532 * Destination peer of the routing trail. 326 * Peer which sent trail rejection message.
533 */ 327 */
534 struct GNUNET_PeerIdentity destination_peer; 328 struct GNUNET_PeerIdentity congested_peer;
535 329
536 /** 330 /**
537 * Total number of peers from source peer to destination peer. 331 * Peer identity which will be successor to this value will be finger of
332 * source_peer.
538 */ 333 */
539 unsigned int trail_length; 334 uint64_t ultimate_destination_finger_identity_value;
540 335
541 /* Trail from source peer to destination peer. */ 336 /**
337 * Index in finger peer map of source peer.
338 */
339 uint32_t finger_map_index;
340
341 /**
342 * Total number of peers in the trail.
343 */
344 uint32_t trail_length;
345
346 /**
347 * Identifier for the trail source peer is trying to setup.
348 */
349 struct GNUNET_HashCode trail_id;
350 /**
351 * Relative time for which congested_peer will remain congested.
352 */
353 struct GNUNET_TIME_Relative congestion_time;
542 354
355 /* Trail_list from source_peer to peer which sent the message for trail setup
356 * to congested peer.*/
543}; 357};
544 358
545GNUNET_NETWORK_STRUCT_END 359GNUNET_NETWORK_STRUCT_END
546 360
547
548/** 361/**
549 * Linked list of messages to send to a particular other peer. 362 * Linked list of messages to send to a particular other peer.
550 */ 363 */
@@ -579,32 +392,8 @@ struct P2PPendingMessage
579 392
580}; 393};
581 394
582 395
583/**
584 * Linked List of peers which are part of trail to reach a particular Finger.
585 */
586struct TrailPeerList
587{
588 /**
589 * Pointer to next item in the list
590 */
591 struct TrailPeerList *next;
592
593 /**
594 * Pointer to previous item in the list
595 */
596 struct TrailPeerList *prev;
597
598 /**
599 * An element in this trail list
600 */
601 struct GNUNET_PeerIdentity peer;
602
603};
604
605
606/** 396/**
607 * FIXME: for congested peer just define a relative time as #define.
608 * Entry in friend_peermap. 397 * Entry in friend_peermap.
609 */ 398 */
610struct FriendInfo 399struct FriendInfo
@@ -646,100 +435,83 @@ struct FriendInfo
646 435
647}; 436};
648 437
649
650/** 438/**
651 * Entry in finger_peermap. 439 * An individual trail to reach to a finger.
652 */ 440 */
653struct FingerInfo 441struct Trail
654{ 442{
655 /** 443 /**
656 * Finger identity. 444 * Pointer to next item in the list
657 */ 445 */
658 struct GNUNET_PeerIdentity finger_identity; 446 struct Trail *next;
659
660 /**
661 * Index in finger peer map
662 */
663 unsigned int finger_map_index;
664
665 /**
666 * Number of trails to reach to this finger.
667 */
668 unsigned int trail_count;
669 447
670 /** 448 /**
671 * Total number of entries in first trail from (me,finger) 449 * Pointer to prev item in the list
672 */ 450 */
673 unsigned int first_trail_length; 451 struct Trail *prev;
674 452
675 /** 453 /**
676 * Total number of entries in second trail from (me,finger) 454 * An element in this trail.
677 */ 455 */
678 unsigned int second_trail_length; 456 struct GNUNET_PeerIdentity peer;
679 457};
680 458
459/**
460 * List of all trails to reach a particular finger.
461 */
462struct TrailList
463{
681 /** 464 /**
682 * Number of trail of which the first element to reach to this finger is 465 * Head of trail.
683 * part of.
684 */ 466 */
685 unsigned int first_friend_trails_count; 467 struct Trail *trail_head;
686 468
687 /** 469 /**
688 * Head of first trail to reach this finger. 470 * Tail of trail.
689 */ 471 */
690 struct TrailPeerList *first_trail_head; 472 struct Trail *trail_tail;
691 473
692 /** 474 /**
693 * Tail of first trail to reach this finger. 475 * Unique identifier of this trail.
694 */ 476 */
695 struct TrailPeerList *first_trail_tail; 477 struct GNUNET_HashCode trail_id;
696 478
697 /** 479 /**
698 * Head of second trail to reach this finger. 480 * Length of trail pointed
699 */ 481 */
700 struct TrailPeerList *second_trail_head; 482 unsigned int trail_length;
701 483
702 /** 484 /**
703 * Tail of second trail to reach this finger. 485 * Number of trails that the first friend of this trail is a part of.
704 */ 486 */
705 struct TrailPeerList *second_trail_tail; 487 unsigned int first_friend_trail_count;
706
707};
708
709
710/**
711 * FIXME: The name is not correct.
712 * Used to specify the kind of value stored in the array all_known_peers.
713 */
714enum current_destination_type
715{
716 FRIEND,
717 FINGER,
718 VALUE,
719 MY_ID
720}; 488};
721 489
722 490
723/** 491/**
724 * Data structure passed to sorting algorithm in find_successor(). 492 * An entry in finger_hashmap.
725 */ 493 */
726struct Sorting_List 494struct FingerInfo
727{ 495{
728 /** 496 /**
729 * 64 bit value of peer identity 497 * Finger identity.
730 */ 498 */
731 uint64_t peer_id; 499 struct GNUNET_PeerIdentity finger_identity;
732 500
733 /** 501 /**
734 * FIXME: think of a better name for both the struct and destination_type 502 * Index in finger peer map
735 * Type : MY_ID, FINGER, FINGER, Value
736 */ 503 */
737 enum current_destination_type type; 504 unsigned int finger_map_index;
738 505
739 /** 506 /**
740 * Pointer to original data structure linked to peer id. 507 * Number of trails setup so far for this finger.
741 */ 508 */
742 void *data; 509 unsigned int trails_count;
510
511 /**
512 * Array of trails.
513 */
514 struct TrailList trail_list[MAXIMUM_TRAILS_PER_FINGER];
743}; 515};
744 516
745 517
@@ -755,14 +527,14 @@ static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
755static struct GNUNET_PeerIdentity my_identity; 527static struct GNUNET_PeerIdentity my_identity;
756 528
757/** 529/**
758 * Hash map of all the friends of a peer 530 * Peer map of all the friends of a peer
759 */ 531 */
760static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap; 532static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
761 533
762/** 534/**
763 * Hash map of all the fingers of a peer 535 * Hash map of all the fingers of a peer
764 */ 536 */
765static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap; 537static struct GNUNET_CONTAINER_MultiHashMap32 *finger_hashmap;
766 538
767/** 539/**
768 * Handle to CORE. 540 * Handle to CORE.
@@ -770,170 +542,15 @@ static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
770static struct GNUNET_CORE_Handle *core_api; 542static struct GNUNET_CORE_Handle *core_api;
771 543
772/** 544/**
773 * Finger map index for predecessor entry in finger peermap. 545 * The current finger index that we have want to find trail to. We start the
774 */ 546 * search with value = 0, i.e. successor peer and then go to PREDCESSOR_FINGER_ID
775#define PREDECESSOR_FINGER_ID 64 547 * and decrement it. For any index 63 <= index < 0, if finger is same as successor,
776 548 * we reset this index to 0.
777/**
778 * Maximum number of trails allowed to go through a friend.
779 * FIXME: Better name, Random value at the moment, need to be adjusted to maintain a balance
780 * between performance and Sybil tolerance.
781 */
782#define TRAIL_THROUGH_FRIEND_THRESHOLD 64
783
784/**
785 * Possible number of different trails to reach to a finger. (Redundant routing)
786 */
787#define TRAIL_COUNT 2
788
789/**
790 * The current finger index that we have want to find trail to.
791 */ 549 */
792static unsigned int current_search_finger_index; 550static unsigned int current_search_finger_index;
793 551
794 552
795/** 553/**
796 * Iterate over trail and search your index location in the array.
797 * @param trail Trail which contains list of peers.
798 * @param trail_length Number of peers in the trail.
799 * @return Index in the array.
800 * #GNUNET_SYSERR, in case there is no entry which should not be the case ideally.
801 */
802static int
803search_my_index (const struct GNUNET_PeerIdentity *trail,
804 int trail_length)
805{
806 int i = 0;
807
808 while (i < trail_length)
809 {
810 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
811 {
812 return i;
813 }
814 i++;
815 }
816 return GNUNET_SYSERR;
817}
818
819
820/**
821 * Compare two peer identities.
822 * @param p1 Peer identity
823 * @param p2 Peer identity
824 * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
825 */
826static int
827compare_peer_id (const void *p1, const void *p2)
828{
829 struct Sorting_List *p11;
830 struct Sorting_List *p22;
831 int ret;
832 p11 = GNUNET_malloc (sizeof (struct Sorting_List));
833 p22 = GNUNET_malloc (sizeof (struct Sorting_List));
834 p11 = (struct Sorting_List *)p1;
835 p22 = (struct Sorting_List *)p2;
836 ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
837 ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
838 return ret;
839}
840
841
842/**
843 * Return the predecessor of value in all_known_peers.
844 * @param all_known_peers list of all the peers
845 * @param value value we have to search in the all_known_peers.
846 * @param size Total numbers of elements
847 * @return Predecessor
848 */
849static struct Sorting_List *
850find_closest_predecessor(struct Sorting_List *all_known_peers, uint64_t value,
851 unsigned int size)
852{
853 int first;
854 int last;
855 int middle;
856
857 first = 0;
858 last = size - 1;
859 middle = (first + last)/2;
860
861 while(first <= last)
862 {
863 if(all_known_peers[middle].peer_id < value)
864 {
865 first = middle + 1;
866 }
867 else if(all_known_peers[middle].peer_id == value)
868 {
869 if(middle == 0)
870 {
871 return &all_known_peers[size - 1];
872 }
873 else
874 {
875 return &all_known_peers[middle - 1];
876 }
877 }
878 else
879 {
880 last = middle - 1;
881 }
882
883 middle = (first + last)/2;
884 }
885 return NULL;
886}
887
888
889/**
890 * Return the successor of value in all_known_peers.
891 * @param all_known_peers list of all the peers
892 * @param value value we have to search in the all_known_peers.
893 * @param size Total numbers of elements
894 * @return Successor
895 */
896static struct Sorting_List *
897find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
898 unsigned int size)
899{
900 int first;
901 int last;
902 int middle;
903
904 first = 0;
905 last = size - 1;
906 middle = (first + last)/2;
907
908 while(first <= last)
909 {
910 if(all_known_peers[middle].peer_id < value)
911 {
912 first = middle + 1;
913 }
914 else if(all_known_peers[middle].peer_id == value)
915 {
916 if(middle == (size -1))
917 {
918 return &all_known_peers[0];
919 }
920 else
921 {
922 return &all_known_peers[middle+1];
923 }
924 }
925 else
926 {
927 last = middle - 1;
928 }
929
930 middle = (first + last)/2;
931 }
932 return NULL;
933}
934
935
936/**
937 * Called when core is ready to send a message we asked for 554 * Called when core is ready to send a message we asked for
938 * out to the destination. 555 * out to the destination.
939 * 556 *
@@ -1038,27 +655,31 @@ process_friend_queue (struct FriendInfo *peer)
1038 655
1039 656
1040/** 657/**
1041 * Construct a trail setup message and forward it to a friend. 658 * Construct a trail setup message and forward it to target_friend
1042 * @param source_peer Peer which wants to set up the trail to one of its finger. 659 * @param source_peer Source peer which wants to setup the trail
1043 * @param destination_finger Peer identity closest to this value will be 660 * @param ultimate_destination_finger Peer identity closest to this value will
1044 * @a source_peer's finger. 661 * be finger to @a source_peer
1045 * @param current_destination next destination corresponding to @a current_source, 662 * @param next_destination Peer which should get the packet. I can be same as
1046 * can be either a finger or a friend of @a current_source. 663 * target_friend or different.
1047 * @param current_source Peer for which @a current_destination is its finger/friend. 664 * @param target_friend Friend to which message is forwarded now.
1048 * @param target_friend Friend to which this message should be forwarded. 665 * @param trail_length Total number of peers in trail setup so far.
1049 * @param trail_length Numbers of peers in the trail found so far. 666 * @param trail_peer_list Trail setup so far
1050 * @param trail_peer_list Peers this request has traversed so far 667 * @param finger_map_index Index in finger map for which we are looking for finger.
1051 * @param finger_map_index Index in finger peer map 668 * @param trail_id Unique identifier for the trail we are trying to setup.
669 * @param intermediate_trail_id Trail id of any intermediate trail we may have to
670 * traverse during trail setup. If not used then set to
671 * 0.
1052 */ 672 */
1053void 673void
1054GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer, 674GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity source_peer,
1055 uint64_t destination_finger, 675 uint64_t ultimate_destination_finger,
1056 struct GNUNET_PeerIdentity *current_destination, 676 struct GNUNET_PeerIdentity next_destination,
1057 struct GNUNET_PeerIdentity *current_source,
1058 struct FriendInfo *target_friend, 677 struct FriendInfo *target_friend,
1059 unsigned int trail_length, 678 unsigned int trail_length,
1060 const struct GNUNET_PeerIdentity *trail_peer_list, 679 const struct GNUNET_PeerIdentity *trail_peer_list,
1061 unsigned int finger_map_index) 680 unsigned int finger_map_index,
681 struct GNUNET_HashCode new_trail_id,
682 struct GNUNET_HashCode intermediate_trail_id)
1062{ 683{
1063 struct P2PPendingMessage *pending; 684 struct P2PPendingMessage *pending;
1064 struct PeerTrailSetupMessage *tsm; 685 struct PeerTrailSetupMessage *tsm;
@@ -1086,13 +707,13 @@ GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
1086 pending->msg = &tsm->header; 707 pending->msg = &tsm->header;
1087 tsm->header.size = htons (msize); 708 tsm->header.size = htons (msize);
1088 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP); 709 tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
1089 memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t)); 710 tsm->ultimate_destination_finger = GNUNET_htonll (ultimate_destination_finger);
1090 memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity)); 711 tsm->source_peer = source_peer;
1091 memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity)); 712 tsm->next_destination = next_destination;
1092 memcpy (&(tsm->current_source), current_source, sizeof (struct GNUNET_PeerIdentity));
1093 tsm->trail_length = htonl (trail_length); 713 tsm->trail_length = htonl (trail_length);
1094 tsm->finger_map_index = htonl (finger_map_index); 714 tsm->finger_map_index = htonl (finger_map_index);
1095 715 tsm->new_trail_id = new_trail_id;
716 tsm->intermediate_trail_id = intermediate_trail_id;
1096 if (trail_length > 0) 717 if (trail_length > 0)
1097 { 718 {
1098 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1]; 719 peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
@@ -1106,21 +727,23 @@ GDS_NEIGHBOURS_send_trail_setup (const struct GNUNET_PeerIdentity *source_peer,
1106 727
1107 728
1108/** 729/**
1109 * Construct a trail setup result message and forward it to a friend. 730 * Construct a trail setup result message and forward it to target friend.
1110 * @param destination_peer Peer which will get the trail to one of its finger. 731 * @param destination_peer
1111 * @param source_finger Peer to which the trail has been setup to. 732 * @param source_finger
1112 * @param target_friend Friend to which this message should be forwarded. 733 * @param target_friend
1113 * @param trail_length Numbers of peers in the trail. 734 * @param trail_length
1114 * @param trail_peer_list Peers which are part of the trail from source to destination. 735 * @param trail_peer_list
1115 * @param finger_map_index Index in finger peer map 736 * @param finger_map_index
737 * @param trail_id
1116 */ 738 */
1117void 739void
1118GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *destination_peer, 740GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity destination_peer,
1119 const struct GNUNET_PeerIdentity *source_finger, 741 struct GNUNET_PeerIdentity source_finger,
1120 struct FriendInfo *target_friend, 742 struct FriendInfo *target_friend,
1121 unsigned int trail_length, 743 unsigned int trail_length,
1122 const struct GNUNET_PeerIdentity *trail_peer_list, 744 const struct GNUNET_PeerIdentity *trail_peer_list,
1123 unsigned int finger_map_index) 745 unsigned int finger_map_index,
746 struct GNUNET_HashCode trail_id)
1124{ 747{
1125 struct P2PPendingMessage *pending; 748 struct P2PPendingMessage *pending;
1126 struct PeerTrailSetupResultMessage *tsrm; 749 struct PeerTrailSetupResultMessage *tsrm;
@@ -1149,11 +772,12 @@ GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *destin
1149 pending->msg = &tsrm->header; 772 pending->msg = &tsrm->header;
1150 tsrm->header.size = htons (msize); 773 tsrm->header.size = htons (msize);
1151 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT); 774 tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
1152 memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity)); 775 tsrm->destination_peer = destination_peer;
1153 memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity)); 776 tsrm->finger_identity = source_finger;
1154 tsrm->trail_length = htonl (trail_length); 777 tsrm->trail_length = htonl (trail_length);
1155 tsrm->finger_map_index = htonl (finger_map_index); 778 tsrm->finger_map_index = htonl (finger_map_index);
1156 779 tsrm->trail_id = trail_id;
780
1157 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1]; 781 peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
1158 if (trail_length > 0) 782 if (trail_length > 0)
1159 { 783 {
@@ -1167,25 +791,36 @@ GDS_NEIGHBOURS_send_trail_setup_result (const struct GNUNET_PeerIdentity *destin
1167 791
1168 792
1169/** 793/**
1170 * Construct a PeerVerifySuccessor message and send it to friend. 794 * Send trail rejection message to next_hop
1171 * @param source_peer Peer which wants to verify its successor 795 * @param source_peer Source peer which is trying to setup the trail.
1172 * @param successor Peer which is our current successor 796 * @param finger_identity Peer closest to this value will be @a source_peer's finger
1173 * @param target_friend Friend to which this message should be forwarded. 797 * @param congested_peer Peer which sent this message as it is congested.
1174 * @param trail_peer_list Peer which are part of trail from source to destination 798 * @param next_hop Peer to which we are forwarding this message.
1175 * @param trail_length Number of peers in the trail list. 799 * @param finger_map_index Index in finger peermap for which we are searching for finger.
800 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
801 * by congested_peer
802 * @param trail_length Total number of peers in trail_peer_list
803 * @param trail_id Unique identifier of this trail.
804 * @param congestion_timeout Duration given by congested peer as an estimate of
805 * how long it may remain congested.
1176 */ 806 */
1177void GDS_NEIGHBOURS_send_verify_successor(const struct GNUNET_PeerIdentity *source_peer, 807void
1178 const struct GNUNET_PeerIdentity *successor, 808GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1179 struct FriendInfo *target_friend, 809 uint64_t finger_identity,
1180 const struct GNUNET_PeerIdentity *trail_peer_list, 810 struct GNUNET_PeerIdentity congested_peer,
1181 unsigned int trail_length) 811 unsigned int finger_map_index,
812 struct GNUNET_PeerIdentity *trail_peer_list,
813 unsigned int trail_length,
814 struct GNUNET_HashCode trail_id,
815 struct FriendInfo *target_friend,
816 const struct GNUNET_TIME_Relative congestion_timeout)
1182{ 817{
1183 struct PeerVerifySuccessorMessage *vsm; 818 struct PeerTrailRejectionMessage *trm;
1184 struct P2PPendingMessage *pending; 819 struct P2PPendingMessage *pending;
1185 struct GNUNET_PeerIdentity *peer_list; 820 struct GNUNET_PeerIdentity *peer_list;
1186 size_t msize; 821 size_t msize;
1187 822
1188 msize = sizeof (struct PeerVerifySuccessorMessage) + 823 msize = sizeof (struct PeerTrailRejectionMessage) +
1189 (trail_length * sizeof (struct GNUNET_PeerIdentity)); 824 (trail_length * sizeof (struct GNUNET_PeerIdentity));
1190 825
1191 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE) 826 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
@@ -1193,6 +828,61 @@ void GDS_NEIGHBOURS_send_verify_successor(const struct GNUNET_PeerIdentity *sour
1193 GNUNET_break (0); 828 GNUNET_break (0);
1194 return; 829 return;
1195 } 830 }
831
832 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
833 {
834 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
835 1, GNUNET_NO);
836 }
837
838 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
839 pending->importance = 0;
840 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
841 trm = (struct PeerTrailRejectionMessage *)&pending[1];
842 pending->msg = &trm->header;
843 trm->header.size = htons (msize);
844 trm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION);
845 trm->source_peer = source_peer;
846 trm->congested_peer = congested_peer;
847 trm->congestion_time = congestion_timeout;
848 trm->finger_map_index = htonl (finger_map_index);
849 trm->trail_id = trail_id;
850
851 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
852 if (trail_length > 0)
853 {
854 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
855 }
856 /* Send the message to chosen friend. */
857 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
858 target_friend->pending_count++;
859 process_friend_queue (target_friend);
860}
861
862
863/**
864 * Construct a verify successor message and forward it to target_friend.
865 * @param source_peer Peer which wants to verify its successor.
866 * @param successor Peer which is @a source_peer's current successor.
867 * @param trail_id Identifier of trail to reach successor.
868 * @param target_friend Message send to this friend.
869 */
870void
871GDS_NEIGHBOURS_send_verify_successor_message (struct GNUNET_PeerIdentity source_peer,
872 struct GNUNET_PeerIdentity successor,
873 const struct GNUNET_HashCode trail_id,
874 struct FriendInfo *target_friend)
875{
876 struct PeerVerifySuccessorMessage *vsm;
877 struct P2PPendingMessage *pending;
878 size_t msize;
879
880 msize = sizeof (struct PeerVerifySuccessorMessage);
881 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
882 {
883 GNUNET_break (0);
884 return;
885 }
1196 886
1197 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) 887 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1198 { 888 {
@@ -1207,39 +897,55 @@ void GDS_NEIGHBOURS_send_verify_successor(const struct GNUNET_PeerIdentity *sour
1207 pending->msg = &vsm->header; 897 pending->msg = &vsm->header;
1208 vsm->header.size = htons (msize); 898 vsm->header.size = htons (msize);
1209 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR); 899 vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
1210 memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity)); 900 vsm->source_peer = source_peer;
1211 memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity)); 901 vsm->successor = successor;
1212 vsm->trail_length = htonl (trail_length); 902 vsm->trail_id = trail_id;
1213
1214 if (trail_length > 0)
1215 {
1216 peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
1217 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1218 }
1219 903
1220 /* Send the message to chosen friend. */ 904 /* Send the message to chosen friend. */
1221 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); 905 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1222 target_friend->pending_count++; 906 target_friend->pending_count++;
1223 process_friend_queue (target_friend); 907 process_friend_queue (target_friend);
908}
909
910
911/**
912 *
913 * @param source_peer
914 * @param destination_peer
915 * @param trail_id
916 * @param trail_direction
917 * @param target_friend
918 */
919void
920GDS_NEIGHBOURS_send_trail_teardown (struct GNUNET_PeerIdentity source_peer,
921 struct GNUNET_PeerIdentity destination_peer,
922 struct GNUNET_HashCode trail_id,
923 enum GDS_ROUTING_trail_direction trail_direction,
924 struct FriendInfo *target_friend)
925{
1224 926
1225} 927}
1226 928
1227 929
1228/** 930/**
1229 * Construct a PeerVerifySuccessorResult message and send it to friend. 931 *
1230 * @param destination_peer Peer which sent verify successor message 932 * @param destination_peer
1231 * @param source_successor Peer to which verify successor message was sent. 933 * @param source_successor
1232 * @param my_predecessor source_successor's predecessor. 934 * @param succ_predecessor
1233 * @param target_friend Friend to which this message should be forwarded. 935 * @param trail_id
1234 * @param trail_peer_list Peers which are part of trail from source to destination 936 * @param trail
1235 * @param trail_length Number of peers in the trail list. 937 * @param trail_length
938 * @param target_friend
1236 */ 939 */
1237void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdentity *destination_peer, 940void
1238 const struct GNUNET_PeerIdentity *source_successor, 941GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity destination_peer,
1239 const struct GNUNET_PeerIdentity *my_predecessor, 942 struct GNUNET_PeerIdentity source_successor,
1240 struct FriendInfo *target_friend, 943 struct GNUNET_PeerIdentity succ_predecessor,
1241 const struct GNUNET_PeerIdentity *trail_peer_list, 944 struct GNUNET_HashCode trail_id,
1242 unsigned int trail_length) 945 const struct GNUNET_PeerIdentity *trail,
946 unsigned int trail_length,
947 enum GDS_ROUTING_trail_direction trail_direction,
948 struct FriendInfo *target_friend)
1243{ 949{
1244 struct PeerVerifySuccessorResultMessage *vsmr; 950 struct PeerVerifySuccessorResultMessage *vsmr;
1245 struct P2PPendingMessage *pending; 951 struct P2PPendingMessage *pending;
@@ -1255,7 +961,6 @@ void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdenti
1255 return; 961 return;
1256 } 962 }
1257 963
1258
1259 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) 964 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1260 { 965 {
1261 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), 966 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
@@ -1269,14 +974,15 @@ void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdenti
1269 pending->msg = &vsmr->header; 974 pending->msg = &vsmr->header;
1270 vsmr->header.size = htons (msize); 975 vsmr->header.size = htons (msize);
1271 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT); 976 vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
1272 memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity)); 977 vsmr->destination_peer = destination_peer;
1273 memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity)); 978 vsmr->my_predecessor = succ_predecessor;
1274 memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity)); 979 vsmr->source_successor = source_successor;
1275 vsmr->trail_length = htonl (trail_length); 980 vsmr->trail_direction = htonl (trail_direction);
981
1276 if (trail_length > 0) 982 if (trail_length > 0)
1277 { 983 {
1278 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1]; 984 peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
1279 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity)); 985 memcpy (peer_list, trail, trail_length * sizeof (struct GNUNET_PeerIdentity));
1280 } 986 }
1281 987
1282 /* Send the message to chosen friend. */ 988 /* Send the message to chosen friend. */
@@ -1287,20 +993,20 @@ void GDS_NEIGHBOURS_send_verify_successor_result (const struct GNUNET_PeerIdenti
1287 993
1288 994
1289/** 995/**
1290 * Construct a PeerNotifyNewSuccessor message and send it to friend. 996 *
1291 * @param source_peer Peer which is sending notify message to its new successor. 997 * @param source_peer
1292 * @param destination_peer Peer which is the new destination. 998 * @param new_successor
1293 * @param target_friend Next friend to pass this message to. 999 * @param new_successor_trail
1294 * @param peer_list List of peers in the trail to reach to destination_peer. 1000 * @param new_successor_trail_length
1295 * @param trail_length Total number of peers in peer list 1001 * @param new_succesor_trail_id
1296 */ 1002 */
1297void 1003void
1298GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *source_peer, 1004GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity source_peer,
1299 const struct GNUNET_PeerIdentity *destination_peer, 1005 struct GNUNET_PeerIdentity new_successor,
1300 const struct GNUNET_PeerIdentity *old_successor, 1006 struct GNUNET_PeerIdentity *new_successor_trail,
1301 struct FriendInfo *target_friend, 1007 unsigned int new_successor_trail_length,
1302 const struct GNUNET_PeerIdentity *trail_peer_list, 1008 struct GNUNET_HashCode new_succesor_trail_id,
1303 unsigned int trail_length) 1009 struct FriendInfo *target_friend)
1304{ 1010{
1305 struct PeerNotifyNewSuccessorMessage *nsm; 1011 struct PeerNotifyNewSuccessorMessage *nsm;
1306 struct P2PPendingMessage *pending; 1012 struct P2PPendingMessage *pending;
@@ -1308,7 +1014,7 @@ GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *sour
1308 size_t msize; 1014 size_t msize;
1309 1015
1310 msize = sizeof (struct PeerNotifyNewSuccessorMessage) + 1016 msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1311 (trail_length * sizeof(struct GNUNET_PeerIdentity)); 1017 (new_successor_trail_length * sizeof(struct GNUNET_PeerIdentity));
1312 1018
1313 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE) 1019 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1314 { 1020 {
@@ -1329,16 +1035,17 @@ GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *sour
1329 pending->msg = &nsm->header; 1035 pending->msg = &nsm->header;
1330 nsm->header.size = htons (msize); 1036 nsm->header.size = htons (msize);
1331 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR); 1037 nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1332 memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity)); 1038 nsm->source_peer = source_peer;
1333 memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity)); 1039 nsm->destination_peer = new_successor;
1334 memcpy (&(nsm->old_successor), old_successor, sizeof (struct GNUNET_PeerIdentity)); 1040 nsm->trail_length = htonl (new_successor_trail_length);
1335 nsm->trail_length = htonl (trail_length); 1041 nsm->trail_id = new_succesor_trail_id;
1336 1042 if (new_successor_trail_length > 0)
1337 if (trail_length > 0)
1338 { 1043 {
1339 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1]; 1044 peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1340 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity)); 1045 memcpy (peer_list, new_successor_trail,
1046 new_successor_trail_length * sizeof (struct GNUNET_PeerIdentity));
1341 } 1047 }
1048
1342 /* Send the message to chosen friend. */ 1049 /* Send the message to chosen friend. */
1343 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); 1050 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1344 target_friend->pending_count++; 1051 target_friend->pending_count++;
@@ -1347,30 +1054,25 @@ GDS_NEIGHBOURS_send_notify_new_successor (const struct GNUNET_PeerIdentity *sour
1347 1054
1348 1055
1349/** 1056/**
1350 * Send a trail tear down message 1057 * Send a trail compression message to target_friend.
1351 * @param source_peer Source of the trail. 1058 * @param source_peer Source of the trail.
1352 * @param destination_peer Destination of the trail. 1059 * @param destination_finger Destination of trail.
1353 * @param discarded_trail Discarded trail from source to destination. 1060 * @param trail_id Unique identifier of trail.
1354 * @param discarded_trail_length Total number of peers in trail_list. 1061 * @param first_friend First hop in compressed trail to reach from source to finger
1355 * @pararm target_peer Next peer to forward this message to. 1062 * @param target_friend Next friend to get this message.
1356 * @param new_first_friend The new first hop in the new trail from source to destination
1357 * peer.
1358 */ 1063 */
1359void 1064void
1360GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_PeerIdentity *source_peer, 1065GDS_NEIGHBOURS_send_trail_compression (struct GNUNET_PeerIdentity source_peer,
1361 const struct GNUNET_PeerIdentity *destination_peer, 1066 struct GNUNET_PeerIdentity destination_peer,
1362 const struct GNUNET_PeerIdentity *discarded_trail, 1067 struct GNUNET_HashCode trail_id,
1363 unsigned int discarded_trail_length, 1068 struct GNUNET_PeerIdentity first_friend,
1364 struct FriendInfo *target_friend, 1069 struct FriendInfo *target_friend)
1365 const struct GNUNET_PeerIdentity *new_first_friend)
1366{ 1070{
1367 struct P2PPendingMessage *pending; 1071 struct P2PPendingMessage *pending;
1368 struct PeerTrailTearDownMessage *ttdm; 1072 struct PeerTrailCompressionMessage *tcm;
1369 struct GNUNET_PeerIdentity *peer_list;
1370 size_t msize; 1073 size_t msize;
1371 1074
1372 msize = sizeof (struct PeerTrailTearDownMessage) + 1075 msize = sizeof (struct PeerTrailCompressionMessage);
1373 (discarded_trail_length * sizeof(struct GNUNET_PeerIdentity));
1374 1076
1375 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE) 1077 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1376 { 1078 {
@@ -1380,150 +1082,268 @@ GDS_NEIGHBOURS_send_trail_teardown (const struct GNUNET_PeerIdentity *source_pee
1380 1082
1381 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) 1083 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1382 { 1084 {
1383 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), 1085 GNUNET_STATISTICS_update (GDS_stats,
1384 1, GNUNET_NO); 1086 gettext_noop ("# P2P messages dropped due to full queue"),
1087 1, GNUNET_NO);
1385 } 1088 }
1386 1089
1387 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); 1090 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1388 pending->importance = 0; /* FIXME */ 1091 pending->importance = 0; /* FIXME */
1389 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT); 1092 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1390 ttdm = (struct PeerTrailTearDownMessage *) &pending[1]; 1093 tcm = (struct PeerTrailCompressionMessage *) &pending[1];
1391 pending->msg = &ttdm->header; 1094 pending->msg = &tcm->header;
1392 ttdm->header.size = htons (msize); 1095 tcm->header.size = htons (msize);
1393 ttdm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN); 1096 tcm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION);
1394 memcpy (&(ttdm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity)); 1097 tcm->source_peer = source_peer;
1395 memcpy (&(ttdm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity)); 1098 tcm->new_first_friend = first_friend;
1396 memcpy (&(ttdm->new_first_friend),new_first_friend, sizeof (struct GNUNET_PeerIdentity)); 1099 tcm->trail_id = trail_id;
1397 ttdm->trail_length = htonl (discarded_trail_length); 1100 tcm->destination_peer = destination_peer;
1398 1101
1399 if (discarded_trail_length > 0)
1400 {
1401 peer_list = (struct GNUNET_PeerIdentity *) &ttdm[1];
1402 memcpy (peer_list, discarded_trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1403 }
1404 /* Send the message to chosen friend. */
1405 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); 1102 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1406 target_friend->pending_count++; 1103 target_friend->pending_count++;
1407 process_friend_queue (target_friend); 1104 process_friend_queue (target_friend);
1105
1408} 1106}
1409 1107
1108/**
1109 * Construct a Put message and send it to target_peer.
1110 * @param key Key for the content
1111 * @param block_type Type of the block
1112 * @param options Routing options
1113 * @param desired_replication_level Desired replication count
1114 * @param current_destination Next current destination which will get this message.
1115 * @param current_source Source for @a current_destination
1116 * @param target_peer Peer to which this message will be forwarded.
1117 * @param hop_count Number of hops traversed so far.
1118 * @param put_path_length Total number of peers in @a put_path
1119 * @param put_path Number of peers traversed so far
1120 * @param expiration_time When does the content expire
1121 * @param data Content to store
1122 * @param data_size Size of content @a data in bytes
1123 */
1124void
1125GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key,
1126 enum GNUNET_BLOCK_Type block_type,
1127 enum GNUNET_DHT_RouteOption options,
1128 uint32_t desired_replication_level,
1129 struct GNUNET_PeerIdentity current_destination,
1130 struct GNUNET_PeerIdentity current_source,
1131 struct GNUNET_PeerIdentity *target_peer,
1132 uint32_t hop_count,
1133 uint32_t put_path_length,
1134 struct GNUNET_PeerIdentity *put_path,
1135 struct GNUNET_TIME_Absolute expiration_time,
1136 const void *data, size_t data_size)
1137{
1138
1139}
1410 1140
1411/** 1141/**
1412 * Construct an add_trail_message and send it to target_friend 1142 * Construct a Get message and send it to target_peer.
1413 * @param source_peer Source of the trail to be added 1143 * @param key Key for the content
1414 * @param destination_peer Destination of the trail to be added 1144 * @param block_type Type of the block
1415 * @param trail Trail from source to destination 1145 * @param options Routing options
1416 * @param trail_length Total number of peers in the trail 1146 * @param desired_replication_level Desired replication count
1417 * @param target_friend Friend to forward this message. 1147 * @param current_destination Next current destination which will get this message.
1148 * @param current_source Source for @a current_destination
1149 * @param target_peer Peer to which this message will be forwarded.
1150 * @param hop_count Number of hops traversed so far.
1151 * @param data Content to store
1152 * @param data_size Size of content @a data in bytes
1153 * @param get_path_length Total number of peers in @a get_path
1154 * @param get_path Number of peers traversed so far
1418 */ 1155 */
1419void 1156void
1420GDS_NEIGHBOURS_send_add_trail_message (struct GNUNET_PeerIdentity *source_peer, 1157GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key,
1421 struct GNUNET_PeerIdentity *destination_peer, 1158 enum GNUNET_BLOCK_Type block_type,
1422 struct GNUNET_PeerIdentity *trail, 1159 enum GNUNET_DHT_RouteOption options,
1423 unsigned int trail_length, 1160 uint32_t desired_replication_level,
1424 struct FriendInfo *target_friend) 1161 struct GNUNET_PeerIdentity current_destination,
1162 struct GNUNET_PeerIdentity current_source,
1163 struct GNUNET_PeerIdentity *target_peer,
1164 uint32_t hop_count,
1165 uint32_t get_path_length,
1166 struct GNUNET_PeerIdentity *get_path)
1425{ 1167{
1426 struct P2PPendingMessage *pending;
1427 struct PeerAddTrailMessage *adm;
1428 struct GNUNET_PeerIdentity *peer_list;
1429 size_t msize;
1430 1168
1431 msize = sizeof (struct PeerAddTrailMessage) + 1169}
1432 (trail_length * sizeof(struct GNUNET_PeerIdentity)); 1170
1171
1172/**
1173 * Send the get result to requesting client.
1174 * @param key Key of the requested data.
1175 * @param type Block type
1176 * @param target_peer Next peer to forward the message to.
1177 * @param source_peer Peer which has the data for the key.
1178 * @param put_path_length Number of peers in @a put_path
1179 * @param put_path Path taken to put the data at its stored location.
1180 * @param get_path_length Number of peers in @a get_path
1181 * @param get_path Path taken to reach to the location of the key.
1182 * @param expiration When will this result expire?
1183 * @param data Payload to store
1184 * @param data_size Size of the @a data
1185 */
1186void
1187GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
1188 enum GNUNET_BLOCK_Type type,
1189 struct GNUNET_PeerIdentity *target_peer,
1190 struct GNUNET_PeerIdentity *source_peer,
1191 unsigned int put_path_length,
1192 const struct GNUNET_PeerIdentity *put_path,
1193 unsigned int get_path_length,
1194 struct GNUNET_PeerIdentity *get_path,
1195 struct GNUNET_TIME_Absolute expiration,
1196 const void *data, size_t data_size)
1197{
1433 1198
1434 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE) 1199}
1435 { 1200
1436 GNUNET_break (0); 1201
1437 return; 1202/**
1438 } 1203 * Seach my location in trail.
1204 * @param trail List of peers
1205 * @return my_index if found
1206 * #GNUNET_SYSERR if no entry found.
1207 */
1208static int
1209search_my_index (const struct GNUNET_PeerIdentity *trail,
1210 int trail_length)
1211{
1212 int i;
1439 1213
1440 if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND) 1214 for (i = 0; i < trail_length; i++)
1441 { 1215 {
1442 GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"), 1216 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &trail[i]))
1443 1, GNUNET_NO); 1217 return i;
1444 } 1218 }
1445 1219
1446 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); 1220 return GNUNET_SYSERR;
1447 pending->importance = 0; /* FIXME */ 1221}
1448 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT); 1222
1449 adm = (struct PeerAddTrailMessage *) &pending[1]; 1223
1450 pending->msg = &adm->header; 1224/**
1451 adm->header.size = htons (msize); 1225 * Find the successor for destination_finger_value among my_identity, all my
1452 adm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL); 1226 * friend and all my fingers. Don't consider friends/ fingers with first friend in
1453 memcpy (&(adm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity)); 1227 * the trail which are congested or have crossed the threshold.
1454 memcpy (&(adm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity)); 1228 * @param destination_finger_value Peer closest to this value will be the next successor.
1455 adm->trail_length = htonl (trail_length); 1229 * @param next_destination [out] Updated to friend identity in case a friend is
1230 * successor, updated to first friend to reach to finger
1231 * in case finger is the destination.
1232 * @param new_intermediate_trail_id [out] In case we finger is the @a next_destination,
1233 * then we updated the field with trail id to reach
1234 * to that finger.
1235 * @param finger_map_index Index in finger peermap for which we are looking for a finger.
1236 * @return
1237 */
1238static struct GNUNET_PeerIdentity *
1239find_successor (uint64_t destination_finger_value,
1240 struct GNUNET_PeerIdentity *next_destination,
1241 struct GNUNET_HashCode *new_intermediate_trail_id,
1242 unsigned int finger_map_index)
1243{
1244 /* FIXME; IMPLEMENT*/
1245 return NULL;
1246}
1247
1248
1249/**
1250 * Select closest finger to value.
1251 * @param peer1 First peer
1252 * @param peer2 Second peer
1253 * @param value Value to be compare
1254 * @return Closest peer
1255 */
1256static struct GNUNET_PeerIdentity *
1257select_closest_finger (struct GNUNET_PeerIdentity *peer1,
1258 struct GNUNET_PeerIdentity *peer2,
1259 uint64_t value)
1260{
1261 uint64_t peer1_value;
1262 uint64_t peer2_value;
1456 1263
1457 if (trail_length > 0) 1264 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1458 { 1265 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1459 peer_list = (struct GNUNET_PeerIdentity *)&adm[1];
1460 memcpy (peer_list, trail, sizeof (struct GNUNET_PeerIdentity) * trail_length);
1461 }
1462 1266
1463 /* Send the message to chosen friend. */ 1267 if ((peer1_value <= value) && (value <= peer2_value))
1464 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); 1268 return peer2;
1465 target_friend->pending_count++; 1269 else if ((peer2_value <= value) && (value <= peer1_value))
1466 process_friend_queue (target_friend); 1270 return peer1;
1271 else if ((peer1_value <= peer2_value) && (peer2_value <= value))
1272 return peer1;
1273 else if ((peer2_value <= peer1_value) && (peer1_value <= value))
1274 return peer2;
1275 else if ((value <= peer1_value) && (peer1_value <= peer2_value))
1276 return peer1;
1277 else /*if ((value <= peer2_value) && (peer2_value <= peer1_value))*/
1278 return peer2;
1467} 1279}
1468 1280
1469 1281
1470/** 1282/**
1471 * FIXME: CONGESTION: check the code once basic code is all correct. s 1283 * Select closest predecessor to value.
1472 * FIXME: call GNUNET_CONTAINER_multipeermap_iterator_destroy (iter); 1284 * @param peer1 First peer
1473 * In case the friend chosen in select_random_friend() is congested or 1285 * @param peer2 Second peer
1474 * has crossed trail_threshold, then get next friend which is not congested or 1286 * @param value Value to be compare
1475 * has not crossed trail threshold from friend peermap. 1287 * @return Closest peer
1476 * @param current_index Index in finger peermap chosen randomly
1477 * @param friend_peermap_size Total number of entries in friend peermap.
1478 * @param count Total number of time this function has been called, in case
1479 * count == sizeof(friend_peermap) - 1, it means none of the friends are free.
1480 * @return Friend Friend found.
1481 * NULL in case all the friends are congested or have crossed trail threshold.
1482 */ 1288 */
1483static struct FriendInfo * 1289static struct GNUNET_PeerIdentity *
1484get_next_friend (unsigned int current_index, 1290select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1485 unsigned int friend_peermap_size, 1291 struct GNUNET_PeerIdentity *peer2,
1486 unsigned int count) 1292 uint64_t value)
1487{ 1293{
1488 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter; 1294 uint64_t peer1_value;
1489 struct GNUNET_PeerIdentity key_ret; 1295 uint64_t peer2_value;
1490 struct FriendInfo *friend;
1491 int j = 0;
1492 1296
1493 current_index = (current_index + 1) % friend_peermap_size; 1297 memcpy (&peer1_value, peer1, sizeof (uint64_t));
1494 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap); 1298 memcpy (&peer2_value, peer2, sizeof (uint64_t));
1495 while(j < (current_index)) 1299
1496 { 1300 if ((peer1_value <= value) && (value <= peer2_value))
1497 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL)) 1301 return peer1;
1498 { 1302 else if ((peer2_value <= value) && (value <= peer1_value))
1499 j++; 1303 return peer2;
1500 } 1304 else if ((peer1_value <= peer2_value) && (peer2_value <= value))
1501 else 1305 return peer2;
1502 return NULL; 1306 else if ((peer2_value <= peer1_value) && (peer1_value <= value))
1503 } 1307 return peer1;
1308 else if ((value <= peer1_value) && (peer1_value <= peer2_value))
1309 return peer2;
1310 else /*if ((value <= peer2_value) && (peer2_value <= peer1_value))*/
1311 return peer1;
1312}
1504 1313
1505 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend)) 1314
1506 { 1315/**
1507 if ((friend->trails_count > TRAIL_THROUGH_FRIEND_THRESHOLD) || 1316 * Select the closest peer among two peers (which should not be same)
1508 (0 != GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us)) 1317 * with respect to value and finger_map_index
1509 { 1318 * @param peer1 First peer
1510 count++; 1319 * @param peer2 Second peer
1511 if (count == (friend_peermap_size -1)) 1320 * @param value Value relative to which we find the closest
1512 return NULL; 1321 * @param finger_map_index Index in finger map. If equal to PREDECESSOR_FINGER_ID,
1513 else 1322 * then we use different logic than other
1514 return get_next_friend (j,friend_peermap_size,count); 1323 * finger_map_index
1515 } 1324 * @return Closest peer among two peers.
1516 return friend; 1325 */
1517 } 1326static struct GNUNET_PeerIdentity *
1327select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1328 struct GNUNET_PeerIdentity *peer2,
1329 uint64_t value,
1330 unsigned int finger_map_index)
1331{
1332 struct GNUNET_PeerIdentity *closest_peer;
1333
1334 if (PREDECESSOR_FINGER_ID == finger_map_index)
1335 closest_peer = select_closest_predecessor (peer1, peer2, value);
1518 else 1336 else
1519 return NULL; 1337 closest_peer = select_closest_finger (peer1, peer2, value);
1338
1339 return closest_peer;
1520} 1340}
1521 1341
1522 1342
1343
1523/** 1344/**
1524 * FIXME: CONGESTION: check the code once basic code is all correct. 1345 * Randomly choose one of your friends (which is not congested and have not crossed
1525 * FIXME: call GNUNET_CONTAINER_multipeermap_iterator_destroy (iter); 1346 * trail threshold) from the friends_peer map
1526 * Randomly choose one of your friends from the friends_peer map
1527 * @return Friend Randomly chosen friend. 1347 * @return Friend Randomly chosen friend.
1528 * NULL in case friend peermap is empty, or all the friends are either 1348 * NULL in case friend peermap is empty, or all the friends are either
1529 * congested or have crossed trail threshold. 1349 * congested or have crossed trail threshold.
@@ -1532,7 +1352,7 @@ static struct FriendInfo *
1532select_random_friend () 1352select_random_friend ()
1533{ 1353{
1534 unsigned int current_size; 1354 unsigned int current_size;
1535 unsigned int *index; 1355 uint32_t index;
1536 unsigned int j = 0; 1356 unsigned int j = 0;
1537 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter; 1357 struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1538 struct GNUNET_PeerIdentity key_ret; 1358 struct GNUNET_PeerIdentity key_ret;
@@ -1542,32 +1362,38 @@ select_random_friend ()
1542 if (0 == current_size) 1362 if (0 == current_size)
1543 return NULL; 1363 return NULL;
1544 1364
1545 index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size); 1365 index = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1546 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap); 1366 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1547 1367
1548 while(j < (*index)) 1368 for (j = 0; j < index ; j++)
1369 GNUNET_assert (GNUNET_YES ==
1370 GNUNET_CONTAINER_multipeermap_iterator_next (iter, NULL, NULL));
1371 do
1549 { 1372 {
1550 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL)) 1373 if (j == current_size)
1551 { 1374 {
1552 j++; 1375 j = 0;
1376 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1377 iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1378
1553 } 1379 }
1554 else 1380 GNUNET_assert (GNUNET_YES ==
1381 GNUNET_CONTAINER_multipeermap_iterator_next (iter,
1382 &key_ret,
1383 (const void **)&friend));
1384
1385
1386 if ((TRAILS_THROUGH_FRIEND_THRESHOLD > friend->trails_count) &&
1387 (0 == GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us))
1555 { 1388 {
1556 return NULL; 1389 break;
1557 } 1390 }
1558 } 1391 friend = NULL;
1559 1392 j++;
1560 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend)) 1393 } while (j != index);
1561 { 1394
1562 if ((TRAIL_THROUGH_FRIEND_THRESHOLD == friend->trails_count) || 1395 GNUNET_CONTAINER_multipeermap_iterator_destroy (iter);
1563 (0 != GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us)) 1396 return friend;
1564 {
1565 return get_next_friend (*index, current_size, 1);
1566 }
1567 return friend;
1568 }
1569 else
1570 return NULL;
1571} 1397}
1572 1398
1573 1399
@@ -1578,7 +1404,7 @@ select_random_friend ()
1578static uint64_t 1404static uint64_t
1579compute_finger_identity() 1405compute_finger_identity()
1580{ 1406{
1581 uint64_t my_id64 ; 1407 uint64_t my_id64;
1582 1408
1583 memcpy (&my_id64, &my_identity, sizeof (uint64_t)); 1409 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1584 my_id64 = GNUNET_ntohll (my_id64); 1410 my_id64 = GNUNET_ntohll (my_id64);
@@ -1601,78 +1427,7 @@ compute_predecessor_identity()
1601} 1427}
1602 1428
1603 1429
1604/** 1430/*
1605 * Ping your successor to verify if it is still your successor or not.
1606 */
1607static void
1608send_verify_successor_message()
1609{
1610 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1611 struct GNUNET_PeerIdentity key_ret;
1612 struct FriendInfo *target_friend;
1613 struct GNUNET_PeerIdentity next_hop;
1614 struct GNUNET_PeerIdentity *peer_list;
1615 struct FingerInfo *finger;
1616 unsigned int finger_index;
1617 int flag = 0;
1618
1619 /* Find the successor from the finger peermap.*/
1620 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1621 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1622 {
1623 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1624 (const void **)&finger))
1625 {
1626 if (0 == finger->finger_map_index)
1627 {
1628 flag = 1;
1629 break;
1630 }
1631 }
1632 }
1633 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1634
1635 /* Either you don't have a successor or you are your own successor, then don't
1636 send a successor message. */
1637 if(( flag == 0) ||
1638 (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &(finger->finger_identity))))
1639 {
1640 return;
1641 }
1642
1643 if (finger->first_trail_length > 0)
1644 {
1645 struct TrailPeerList *iterate;
1646 int i = 0;
1647 peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->first_trail_length);
1648 iterate = finger->first_trail_head;
1649
1650 while ( i < (finger->first_trail_length))
1651 {
1652 memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1653 iterate = iterate->next;
1654 i++;
1655 }
1656 memcpy (&next_hop, &peer_list[0], sizeof (struct GNUNET_PeerIdentity));
1657 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
1658 }
1659 else
1660 {
1661 /* If trail length = 0, then our successor is our friend. */
1662 peer_list = NULL;
1663 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1664 &(finger->finger_identity));
1665 }
1666
1667 GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1668 &(finger->finger_identity),
1669 target_friend,
1670 peer_list,
1671 finger->first_trail_length);
1672}
1673
1674
1675/**
1676 * Choose a random friend and start looking for the trail to reach to 1431 * Choose a random friend and start looking for the trail to reach to
1677 * finger identity through this random friend. 1432 * finger identity through this random friend.
1678 * 1433 *
@@ -1685,8 +1440,10 @@ send_find_finger_trail_message (void *cls,
1685{ 1440{
1686 struct FriendInfo *target_friend; 1441 struct FriendInfo *target_friend;
1687 struct GNUNET_TIME_Relative next_send_time; 1442 struct GNUNET_TIME_Relative next_send_time;
1688 uint64_t finger_identity; 1443 struct GNUNET_HashCode trail_id;
1444 struct GNUNET_HashCode intermediate_trail_id;
1689 unsigned int finger_map_index; 1445 unsigned int finger_map_index;
1446 uint64_t finger_identity;
1690 1447
1691 next_send_time.rel_value_us = 1448 next_send_time.rel_value_us =
1692 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us + 1449 DHT_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
@@ -1712,213 +1469,18 @@ send_find_finger_trail_message (void *cls,
1712 } 1469 }
1713 1470
1714 finger_map_index = current_search_finger_index; 1471 finger_map_index = current_search_finger_index;
1715 GDS_NEIGHBOURS_send_trail_setup (&my_identity, finger_identity, &(target_friend->id),
1716 &my_identity, target_friend, 0, NULL, finger_map_index);
1717}
1718
1719
1720/**
1721 * FIXME: TRAIL_LIST URGENT. Send trail teardown message along each of the trail.
1722 * Scan the trail to check if any of my own friend is part of trail. If yes
1723 * then shortcut the trail, send a trail teardown for the discarded trail,
1724 * update trail list and trail_length.
1725 * @param trail[Out] Current trail to reach to @a finger, will be updated
1726 * in case we compress the trail.
1727 * @param trail_length[Out] Number of peers in @a finger_trail, will be updated
1728 * in case we compress the trail.
1729 * @param finger Finger identity
1730 */
1731static void
1732scan_and_compress_trail (struct GNUNET_PeerIdentity *trail,
1733 unsigned int *trail_length,
1734 const struct GNUNET_PeerIdentity *finger)
1735{
1736 int i;
1737 struct FriendInfo *target_friend;
1738
1739 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger))
1740 {
1741 /* Here you don't send a trail teardown as no one added this in their
1742 routing table. */
1743 *trail_length = 0;
1744 trail = NULL;
1745 return;
1746 }
1747 if (GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger))
1748 {
1749 int discarded_trail_length = *trail_length;
1750 target_friend = GNUNET_CONTAINER_multipeermap_get(friend_peermap, &trail[0]);
1751 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, trail,
1752 discarded_trail_length, target_friend, finger);
1753 *trail_length = 0;
1754 trail = NULL;
1755 return;
1756 }
1757
1758 i = *trail_length - 1;
1759
1760 while (i > 1)
1761 {
1762 if (NULL == GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
1763 {
1764 /* This element of trail is not my friend. */
1765 i--;
1766 }
1767 else
1768 {
1769 /* A --> B(friend 1) --> C(friend 2)--> D ---> E, then we can rewrite the trail as
1770 * C --> D --> E,
1771 * Now, we should remove the entry from A's routing table, B's routing table
1772 * and update the entry in C's routing table. Rest everything will be same.
1773 * C's routing table should have source peer as the prev.hop.
1774 */
1775 struct GNUNET_PeerIdentity *discarded_trail;
1776 struct FriendInfo *target_friend;
1777 int discarded_trail_length;
1778 int j = 0;
1779
1780 discarded_trail_length = i - 1;
1781 discarded_trail = GNUNET_malloc (discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1782 memcpy (discarded_trail, trail, discarded_trail_length * sizeof (struct GNUNET_PeerIdentity));
1783 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[0]);
1784 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, finger, discarded_trail,
1785 discarded_trail_length, target_friend,
1786 &trail[i]);
1787
1788 /* Copy the trail from index i to index trail_length -1 and change
1789 trail length and return */
1790 while (i < *trail_length)
1791 {
1792 memcpy (&trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
1793 j++;
1794 i++;
1795 }
1796 *trail_length = j+1;
1797 return;
1798 }
1799 }
1800 return;
1801}
1802
1803
1804/**
1805 * FIXME: URGENT:Adapt the code for List of trails.
1806 * Free finger and its trail.
1807 * @param finger Finger to be freed.
1808 */
1809static void
1810free_finger (struct FingerInfo *finger)
1811{
1812 struct TrailPeerList *peer;
1813
1814 if(finger->first_trail_head != NULL)
1815 {
1816 while (NULL != (peer = finger->first_trail_head))
1817 {
1818 GNUNET_CONTAINER_DLL_remove (finger->first_trail_head, finger->first_trail_tail, peer);
1819 GNUNET_free (peer);
1820 }
1821 }
1822 1472
1823 if (finger->second_trail_head != NULL) 1473 /* FIXME: Find the correct function to generate a random trail id which is of
1824 { 1474 * type struct GNUNET_HashCode. */
1825 while (NULL != (peer = finger->second_trail_head)) 1475 //trail_id = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_STRONG, UINT64_MAX);
1826 { 1476
1827 GNUNET_CONTAINER_DLL_remove (finger->second_trail_head, finger->second_trail_tail, peer); 1477 GDS_NEIGHBOURS_send_trail_setup (my_identity, finger_identity,
1828 GNUNET_free (peer); 1478 target_friend->id, target_friend, 0, NULL,
1829 } 1479 finger_map_index, trail_id, intermediate_trail_id);
1830 GNUNET_free (finger);
1831 }
1832}
1833
1834
1835/**
1836 * FIXME: URGENT: TRAIL_LIST First check if both the trails are present if yes
1837 * then send it for both of them. Currently sending it only for one trail.
1838 * Send a trail teardown message for the trail of removed finger from the finger
1839 * peermap.
1840 * @param existing_finger Finger to removed from the finger peermap.
1841 */
1842static
1843void send_trail_teardown (struct FingerInfo *removed_finger)
1844{
1845 struct GNUNET_PeerIdentity *peer_list;
1846 struct FriendInfo *friend;
1847 struct TrailPeerList *finger_trail;
1848 int removed_finger_trail_length = removed_finger->first_trail_length;
1849 int i = 0;
1850
1851 if (removed_finger->first_trail_length == 0)
1852 return;
1853
1854 finger_trail = removed_finger->first_trail_head;
1855 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(finger_trail->peer));
1856 peer_list = GNUNET_malloc ( removed_finger_trail_length * sizeof (struct GNUNET_PeerIdentity));
1857 while (i < removed_finger->first_trail_length)
1858 {
1859 memcpy (&peer_list[i], &(finger_trail->peer), sizeof (struct GNUNET_PeerIdentity));
1860 finger_trail = finger_trail->next;
1861 i++;
1862 }
1863
1864 GDS_NEIGHBOURS_send_trail_teardown (&my_identity, &(removed_finger->finger_identity),
1865 peer_list, removed_finger_trail_length, friend,
1866 &(removed_finger->finger_identity));
1867}
1868
1869
1870/**
1871 * FIXME: URGENT Adapt it to trail list.
1872 * Add a new trail to reach an existing finger in finger peermap and increment
1873 * the count of number of trails to reach to this finger.
1874 * @param existing_finger Finger
1875 * @param trail New trail to be added
1876 * @param trail_length Total number of peers in the trail.
1877 */
1878static
1879void add_new_trail (struct FingerInfo *existing_finger,
1880 struct GNUNET_PeerIdentity *trail,
1881 unsigned int trail_length)
1882{
1883 int i;
1884 i = 0;
1885 /* FIXME: Here you need to understand which trail is there and which not.
1886 In case first_trail_head != NULL, then that trail is present
1887 so you should add the second one. Need to verify this logic. */
1888 if (existing_finger->first_trail_head != NULL)
1889 {
1890 while (i < trail_length)
1891 {
1892 struct TrailPeerList *element;
1893 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1894 element->next = NULL;
1895 element->prev = NULL;
1896
1897 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1898 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1899 i++;
1900 }
1901 }
1902 else if (existing_finger->second_trail_head != NULL)
1903 {
1904 while (i < trail_length)
1905 {
1906 struct TrailPeerList *element;
1907 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1908 element->next = NULL;
1909 element->prev = NULL;
1910
1911 memcpy (&(element->peer), &trail[i], sizeof(struct GNUNET_PeerIdentity));
1912 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->first_trail_head, existing_finger->first_trail_tail, element);
1913 i++;
1914 }
1915 }
1916 existing_finger->trail_count++;
1917} 1480}
1918 1481
1919 1482
1920/** 1483/**
1921 * FIXME: URGENT: adapt it to TRAIL LIST.
1922 * In case there are already maximum number of possible trail to reach to a finger, 1484 * In case there are already maximum number of possible trail to reach to a finger,
1923 * then check if the new trail's length is lesser than any of the existing trails. 1485 * then check if the new trail's length is lesser than any of the existing trails.
1924 * If yes then replace that old trail by new trail. 1486 * If yes then replace that old trail by new trail.
@@ -1927,1062 +1489,561 @@ void add_new_trail (struct FingerInfo *existing_finger,
1927 * trail - older the better. 2. if the new trail is completely disjoint than the 1489 * trail - older the better. 2. if the new trail is completely disjoint than the
1928 * other trails, then may be choosing it is better. 1490 * other trails, then may be choosing it is better.
1929 * @param existing_finger 1491 * @param existing_finger
1930 * @param trail 1492 * @param new_finger_trail
1931 * @param trail_length 1493 * @param new_finger_trail_length
1932 * @return #GNUNET_YES 1494 * @param new_finger_trail_id
1933 * #GNUNET_NO
1934 */
1935static
1936void select_and_replace_trail (struct FingerInfo *existing_finger,
1937 struct GNUNET_PeerIdentity *new_trail,
1938 unsigned int new_trail_length)
1939{
1940 if (existing_finger->first_trail_length == existing_finger->second_trail_length)
1941 {
1942 if (new_trail_length < existing_finger->first_trail_length)
1943 {
1944 /* Randomly choose one of the trail. FIXME:currently I am just replacing the
1945 first trail.*/
1946 struct TrailPeerList *peer;
1947 int i = 0;
1948
1949 while (NULL != (peer = existing_finger->first_trail_head))
1950 {
1951 GNUNET_CONTAINER_DLL_remove (existing_finger->first_trail_head, existing_finger->first_trail_tail, peer);
1952 GNUNET_free (peer);
1953 }
1954
1955 while (i < new_trail_length)
1956 {
1957 struct TrailPeerList *element;
1958 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1959 element->next = NULL;
1960 element->prev = NULL;
1961
1962 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1963 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1964 i++;
1965 }
1966 }
1967 }
1968 else if ((new_trail_length < existing_finger->second_trail_length) &&
1969 (existing_finger->second_trail_length < existing_finger->first_trail_length))
1970 {
1971 /* Replace the first trail by the new trail. */
1972 struct TrailPeerList *peer;
1973 int i = 0;
1974
1975 while (NULL != (peer = existing_finger->first_trail_head))
1976 {
1977 GNUNET_CONTAINER_DLL_remove (existing_finger->first_trail_head, existing_finger->first_trail_tail, peer);
1978 GNUNET_free (peer);
1979 }
1980
1981 while (i < new_trail_length)
1982 {
1983 struct TrailPeerList *element;
1984 element = GNUNET_malloc (sizeof (struct TrailPeerList));
1985 element->next = NULL;
1986 element->prev = NULL;
1987
1988 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
1989 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
1990 i++;
1991 }
1992 }
1993 else if ( (new_trail_length < existing_finger->first_trail_length) &&
1994 (existing_finger->first_trail_length < existing_finger->second_trail_length))
1995 {
1996 /* Replace the second trail by the new trail. */
1997 struct TrailPeerList *peer;
1998 int i = 0;
1999
2000 while (NULL != (peer = existing_finger->second_trail_head))
2001 {
2002 GNUNET_CONTAINER_DLL_remove (existing_finger->second_trail_head, existing_finger->second_trail_tail, peer);
2003 GNUNET_free (peer);
2004 }
2005
2006 while (i < new_trail_length)
2007 {
2008 struct TrailPeerList *element;
2009 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2010 element->next = NULL;
2011 element->prev = NULL;
2012
2013 memcpy (&(element->peer), &new_trail[i], sizeof(struct GNUNET_PeerIdentity));
2014 GNUNET_CONTAINER_DLL_insert_tail(existing_finger->second_trail_head, existing_finger->second_trail_tail, element);
2015 i++;
2016 }
2017 }
2018}
2019
2020
2021/**
2022 * FIXME: URGENT: Adapat it for trail list.
2023 * FIXME: If we remove a finger which is our friend, then how should we handle it.
2024 * Ideally only in case if the trail_length > 0,we increment the trail count
2025 * of the first friend in the trail to reach to the finger. in case finger is
2026 * our friend then trail length = 0, and hence, we have never incremented the
2027 * trail count associated with that friend.
2028 * Decrement the trail count for the first friend to reach to the finger.
2029 * @param finger
2030 */ 1495 */
2031static void 1496static void
2032decrement_friend_trail_count (struct FingerInfo *finger) 1497select_and_replace_trail (struct FingerInfo *existing_finger,
1498 struct GNUNET_PeerIdentity *new_trail,
1499 unsigned int new_trail_length,
1500 struct GNUNET_HashCode new_trail_id)
2033{ 1501{
2034 struct FriendInfo *first_trail_friend; 1502 struct TrailList *trail_list_iterator;
2035 struct FriendInfo *second_trail_friend; 1503 unsigned int largest_trail_length;
1504 unsigned int largest_trail_index;
1505 struct Trail *trail_element;
1506 unsigned int i;
2036 1507
2037 if(finger->first_trail_head != NULL) 1508 largest_trail_length = new_trail_length;
2038 { 1509 largest_trail_index = MAXIMUM_TRAILS_PER_FINGER + 1;
2039 first_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2040 &(finger->first_trail_head->peer));
2041 first_trail_friend->trails_count--;
2042 }
2043
2044 if(finger->second_trail_head != NULL)
2045 {
2046 second_trail_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2047 &(finger->second_trail_head->peer));
2048 second_trail_friend->trails_count--;
2049 }
2050 1510
2051#if 0 1511 GNUNET_assert (MAXIMUM_TRAILS_PER_FINGER == existing_finger->trails_count);
2052 /* We will not need this variable any more, all_friends_trail_threshold, 1512
2053 FIXME: REMOVE IT. */ 1513 for (i = 0; i < existing_finger->trails_count; i++)
2054 if (GNUNET_YES == all_friends_trail_threshold)
2055 { 1514 {
2056 all_friends_trail_threshold = GNUNET_NO; 1515 trail_list_iterator = &existing_finger->trail_list[i];
2057 /* FIXME; Here you should reschedule the send_find_finger_task here. or 1516 if (trail_list_iterator->trail_length > largest_trail_length)
2058 make a call.*/ 1517 {
1518 largest_trail_length = trail_list_iterator->trail_length;
1519 largest_trail_index = i;
1520 }
2059 } 1521 }
2060#endif
2061}
2062
2063
2064/**
2065 * FIXME: create a different data structure for storing the peer ids here.
2066 * Select the closest finger. Used for both predecessor and other fingers..
2067 * But internally calls different functions for predecessor and other fingers.
2068 * @param existing_finger Finger in finger peermap.
2069 * @param new_finger New finger identity
2070 * @param finger_map_index Index in finger peermap where @a existing_finger is stored.
2071 * @return #GNUNET_YES if the new finger is closest.
2072 * #GNUNET_NO if the old finger is closest.
2073 * #GNUNET_SYSERR in case our own identity is closest (should never happen).
2074 */
2075static
2076int select_finger (struct FingerInfo *existing_finger,
2077 const struct GNUNET_PeerIdentity *new_finger,
2078 unsigned int finger_map_index)
2079{
2080 struct Sorting_List peers[3]; /* 3 for existing_finger, new_finger, my_identity */
2081 struct Sorting_List *closest_finger;
2082 uint64_t value;
2083 int k;
2084
2085 for (k = 0; k < 3; k++)
2086 peers[k].data = 0;
2087 1522
2088 /* Add your entry to peers. */ 1523 if (largest_trail_index == (MAXIMUM_TRAILS_PER_FINGER + 1))
2089 memcpy (&peers[0], &my_identity, sizeof (uint64_t)); 1524 return;
2090 peers[0].type = MY_ID;
2091 peers[0].data = NULL;
2092
2093 /* Add existing_finger identity to the peers. */
2094 memcpy (&peers[1], &(existing_finger->finger_identity), sizeof (uint64_t));
2095 peers[1].type = FINGER;
2096 peers[1].data = existing_finger;
2097
2098 /* Add new_finger identity to the peers. s*/
2099 memcpy (&peers[2], &new_finger, sizeof (uint64_t));
2100 peers[2].type = VALUE;
2101 peers[2].data = NULL;
2102
2103 memcpy (&value, &my_identity, sizeof (uint64_t));
2104 qsort (&peers, 3, sizeof (struct Sorting_List), &compare_peer_id);
2105 1525
2106 if (PREDECESSOR_FINGER_ID == finger_map_index) 1526 /* Send trail teardown message across the replaced trail. */
2107 closest_finger = find_closest_predecessor (peers, value, 3); 1527 struct TrailList *replace_trail = &existing_finger->trail_list[largest_trail_index];
2108 else 1528 struct FriendInfo *target_friend =
2109 closest_finger = find_closest_successor (peers, value, 3); 1529 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1530 &replace_trail->trail_head->peer);
2110 1531
2111 if (closest_finger->type == FINGER) 1532 GDS_NEIGHBOURS_send_trail_teardown (my_identity,
1533 existing_finger->finger_identity,
1534 replace_trail->trail_id,
1535 GDS_ROUTING_SRC_TO_DEST, target_friend);
1536 /* Free the trail .*/
1537 while (NULL != (trail_element = replace_trail->trail_head))
2112 { 1538 {
2113 return GNUNET_NO; 1539 GNUNET_CONTAINER_DLL_remove (replace_trail->trail_head,
1540 replace_trail->trail_tail, trail_element);
1541 GNUNET_free (trail_element);
2114 } 1542 }
2115 else if (closest_finger->type == VALUE) 1543
2116 { 1544 /* Add new trial at that location. */
2117 return GNUNET_YES; 1545 i = 0;
2118 } 1546 while ( i < new_trail_length)
2119 else if (closest_finger->type == MY_ID);
2120 { 1547 {
2121 return GNUNET_SYSERR; 1548 struct Trail *element = GNUNET_new (struct Trail);
1549 element->next = NULL;
1550 element->prev = NULL;
1551 element->peer = new_trail[0];
1552
1553 GNUNET_CONTAINER_DLL_insert_tail (replace_trail->trail_head,
1554 replace_trail->trail_tail,
1555 element);
2122 } 1556 }
2123} 1557}
2124 1558
2125 1559
2126/** 1560/**
2127 * FIXME: Better name, and make the code more cleaner. 1561 * Check if the new trail to reach to finger is unique or do we already have
2128 * Compare the new finger entry added and our successor. 1562 * such a trail present for finger.
2129 * @return #GNUNET_YES if same. 1563 * @param existing_finger Finger identity
2130 * #GNUNET_NO if not. 1564 * @param new_trail New trail to reach @a existing_finger
1565 * @param trail_length Total number of peers in new_trail.
1566 * @return #GNUNET_YES if the new trail is unique
1567 * #GNUNET_NO if same trail is already present.
2131 */ 1568 */
2132static int 1569static int
2133compare_new_entry_and_successor (const struct GNUNET_PeerIdentity *new_finger, 1570is_new_trail_unique (struct FingerInfo *existing_finger,
2134 int finger_map_index) 1571 struct GNUNET_PeerIdentity *new_trail,
1572 unsigned int trail_length)
2135{ 1573{
2136 int successor_flag = 0; 1574 struct TrailList *trail_list_iterator;
2137 struct FingerInfo *successor_finger; 1575 struct Trail *trail_element;
2138 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2139 int i; 1576 int i;
2140 1577 int j;
2141 if (PREDECESSOR_FINGER_ID == finger_map_index) 1578 int trail_unique = GNUNET_NO;
2142 return GNUNET_NO;
2143 1579
2144 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap); 1580 for (i = 0; i < existing_finger->trails_count; i++)
2145 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++)
2146 { 1581 {
2147 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL, 1582 trail_list_iterator = &existing_finger->trail_list[i];
2148 (const void **)&successor_finger)) 1583 trail_element = trail_list_iterator->trail_head;
1584 for (j = 0; j < trail_list_iterator->trail_length; j++)
2149 { 1585 {
2150 if (successor_finger->finger_map_index == 0) 1586 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&new_trail[j],
1587 &trail_element->peer))
2151 { 1588 {
2152 successor_flag = 1; 1589 trail_unique = GNUNET_YES;
2153 break; 1590 break;
2154 } 1591 }
2155 } 1592 }
2156 } 1593 }
2157 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter); 1594 return trail_unique;
2158
2159 /* Ideally we should never reach here. */
2160 if (successor_flag == 0)
2161 {
2162 GNUNET_break (0);
2163 return GNUNET_NO;
2164 }
2165
2166 if (0 == GNUNET_CRYPTO_cmp_peer_identity (new_finger, &(successor_finger->finger_identity)))
2167 return GNUNET_YES;
2168 else
2169 return GNUNET_NO;
2170} 1595}
2171 1596
2172 1597
2173/** 1598/**
2174 * FIXME: URGENT: Adapat it for trail list. 1599 * Add a new trail to existing finger.
2175 * Add a new entry in finger table. 1600 * @param existing_finger
2176 * @param finger_identity PeerIdentity of the new finger 1601 * @param new_finger_trail
2177 * @param finger_trail Trail to reach to the finger, can be NULL in case I am my own 1602 * @param new_finger_trail_length
2178 * finger. 1603 * @param new_finger_trail_id
2179 * @param finger_trail_length Number of peers in the trail, can be 0 in case finger
2180 * is a friend or I am my own finger.
2181 * @param finger_map_index Index in finger map.
2182 */ 1604 */
2183static int 1605static void
2184add_new_entry (const struct GNUNET_PeerIdentity *finger_identity, 1606add_new_trail (struct FingerInfo *existing_finger,
2185 struct GNUNET_PeerIdentity *finger_trail, 1607 struct GNUNET_PeerIdentity *new_trail,
2186 uint32_t finger_trail_length, 1608 unsigned int new_trail_length,
2187 uint32_t finger_map_index) 1609 struct GNUNET_HashCode new_trail_id)
2188{ 1610{
2189 struct FriendInfo *first_friend_trail; 1611 struct TrailList *trail_list_iterator;
2190 struct FingerInfo *new_finger_entry; 1612 struct FriendInfo *first_friend;
2191 int i; 1613 int i = 0;
1614 int j;
2192 1615
2193 /* Add a new entry. */ 1616 if (GNUNET_NO == is_new_trail_unique (existing_finger,
2194 new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo)); 1617 new_trail,
2195 memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity)); 1618 new_trail_length))
2196 new_finger_entry->finger_map_index = finger_map_index; 1619 return;
2197 new_finger_entry->first_trail_length = finger_trail_length;
2198 new_finger_entry->trail_count = 1;
2199 1620
2200 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger_identity)) /* finger_trail is NULL in case I am my own finger identity. */ 1621 do
2201 { 1622 {
2202 /* Incrementing the friend trails count. */ 1623 trail_list_iterator = &existing_finger->trail_list[i];
2203 if (finger_trail_length > 0) 1624 i++;
2204 { 1625 } while (trail_list_iterator->trail_head != NULL);
2205 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_trail[0]); 1626
2206 first_friend_trail->trails_count++; 1627 if (new_trail_length > 0)
2207 } 1628 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2208 else 1629 &new_trail[0]);
2209 { 1630 else
2210 /* It means the finger is my friend. */ 1631 first_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2211 first_friend_trail = GNUNET_CONTAINER_multipeermap_get (friend_peermap, finger_identity); 1632 &(existing_finger->finger_identity));
2212 first_friend_trail->trails_count++; 1633 first_friend->trails_count++;
2213 } 1634 trail_list_iterator->first_friend_trail_count = first_friend->trails_count;
2214 new_finger_entry->first_friend_trails_count = first_friend_trail->trails_count; 1635 trail_list_iterator->trail_length = new_trail_length;
2215 1636
2216 /* Copy the trail. */ 1637 for (j = 0; j < new_trail_length; j++)
2217 i = 0;
2218 while (i < finger_trail_length)
2219 {
2220 struct TrailPeerList *element;
2221 element = GNUNET_malloc (sizeof (struct TrailPeerList));
2222 element->next = NULL;
2223 element->prev = NULL;
2224
2225 memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
2226 GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->first_trail_head, new_finger_entry->first_trail_tail, element);
2227 i++;
2228 }
2229 }
2230
2231 return GNUNET_CONTAINER_multipeermap_put (finger_peermap,
2232 &(new_finger_entry->finger_identity),
2233 new_finger_entry,
2234 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
2235}
2236
2237
2238/**
2239 * Choose the closest finger between existing finger and new finger.
2240 * If the new finger is closest, then send a trail_teardown message along
2241 * existing_finger's trail. In case both the id's are same, and there is a place
2242 * to add more trails, then store both of them. In case there is no space to
2243 * store any more trail, then choose the best trail (best - depends on length in
2244 * current_implementation) and discard the others.
2245 * @param existing_finger
2246 * @param new_finger Existing finger in finger_peermap for @a finger_map_index
2247 * @param trail Trail to reach from me to @a new_finger
2248 * @param trail_length Total number of peers in @a trail.
2249 * @param finger_map_index Index in finger peermap.
2250 * @return #GNUNET_YES In case we want to store the new entry.
2251 * #GNUNET_NO In case we want the existing entry.
2252 * #GNUNET_SYSERR Error.
2253 */
2254static
2255int select_closest_finger (struct FingerInfo *existing_finger,
2256 const struct GNUNET_PeerIdentity *new_finger,
2257 struct GNUNET_PeerIdentity *trail,
2258 unsigned int trail_length,
2259 unsigned int finger_map_index)
2260{
2261 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), new_finger))
2262 {
2263 /* New entry and existing entry are same. */
2264 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), &my_identity))
2265 {
2266 /* If existing_finger is my_identity then trail_length = 0, trail = NULL. In
2267 this case you don't need to check the trails. Exit. */
2268 return GNUNET_NO;
2269 }
2270 if (trail_length > 0)
2271 {
2272 scan_and_compress_trail (trail, &trail_length, new_finger);
2273 }
2274 if (existing_finger->trail_count < TRAIL_COUNT)
2275 {
2276 add_new_trail (existing_finger, trail, trail_length);
2277 return GNUNET_NO;
2278 }
2279 else
2280 {
2281 select_and_replace_trail (existing_finger, trail, trail_length);
2282 return GNUNET_NO;
2283 }
2284 }
2285 else if (GNUNET_YES == select_finger (existing_finger, new_finger, finger_map_index))
2286 { 1638 {
2287 /* New finger is the closest finger. */ 1639 struct Trail *element;
2288 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, new_finger)) 1640 element = GNUNET_new (struct Trail);
2289 {
2290 /* FIXME: Here in case the new finger is my_identity and old entry is not,
2291 should we keep the old entry even if the old entry is not the closest? */
2292 return GNUNET_NO;
2293 }
2294 send_trail_teardown (existing_finger);
2295 decrement_friend_trail_count (existing_finger);
2296 free_finger (existing_finger);
2297 1641
2298 if (trail_length > 0) 1642 element->next = NULL;
2299 { 1643 element->prev = NULL;
2300 scan_and_compress_trail (trail, &trail_length, new_finger); 1644 element->peer = new_trail[j];
2301 } 1645 GNUNET_CONTAINER_DLL_insert_tail (trail_list_iterator->trail_head,
2302 return GNUNET_YES; 1646 trail_list_iterator->trail_tail,
2303 } 1647 element);
2304 else if (GNUNET_NO == select_finger (existing_finger, new_finger,finger_map_index)) 1648 }
2305 { 1649 existing_finger->trails_count++;
2306 /* existing_finger is the closest finger. */
2307 return GNUNET_NO;
2308 }
2309 return GNUNET_SYSERR;
2310} 1650}
2311 1651
2312 1652
2313/** 1653/**
2314 * FIXME: TRAIL LIST urgent. 1654 * Send trail teardown message on all trails associated with finger.
2315 * Check if there is already an entry for finger map index in finger table. 1655 * @param finger_to_be_removed
2316 * If yes then choose the closest finger.
2317 * @param finger_identity Peer Identity of finger.
2318 * @param finger_trail Trail to reach from me to @a finger_identity
2319 * @param finger_trail_length Total number of peers in finger_trail.
2320 * @param finger_map_index Index in finger_peermap.
2321 * @return #GNUNET_YES if the new entry is added.
2322 * #GNUNET_NO if the new entry is discarded.
2323 */ 1656 */
2324static 1657static void
2325int finger_table_add (const struct GNUNET_PeerIdentity *finger_identity, 1658send_trail_teardown (struct FingerInfo *finger)
2326 struct GNUNET_PeerIdentity *finger_trail,
2327 uint32_t finger_trail_length,
2328 uint32_t finger_map_index)
2329{ 1659{
2330 struct FingerInfo *existing_finger; 1660 struct TrailList *trail_list_iterator;
2331 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter; 1661 struct GNUNET_HashCode trail_id;
1662 struct FriendInfo *target_friend;
2332 int i; 1663 int i;
2333 int old_entry_found = GNUNET_NO;
2334 int new_entry_added = GNUNET_NO;
2335 1664
2336 /* Check if there is already an entry for the finger map index in the finger peer map. */ 1665 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity, &my_identity)
2337 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap); 1666 || (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2338 for (i= 0; i < GNUNET_CONTAINER_multipeermap_size (finger_peermap); i++) 1667 &finger->finger_identity)))
2339 { 1668 return;
2340 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, NULL,
2341 (const void **)&existing_finger))
2342 {
2343 if (existing_finger->finger_map_index == finger_map_index)
2344 {
2345 old_entry_found = GNUNET_YES;
2346 if ( GNUNET_NO == select_closest_finger (existing_finger, finger_identity,
2347 finger_trail, finger_trail_length,
2348 finger_map_index))
2349 goto update_current_search_finger_index;
2350 else
2351 break;
2352 }
2353 }
2354 }
2355 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2356 1669
2357 if (GNUNET_NO == old_entry_found) 1670 for (i = 0; i < finger->trails_count; i++)
2358 { 1671 {
2359 if (finger_trail_length > 0) 1672 trail_list_iterator = &finger->trail_list[i];
1673 if (trail_list_iterator->trail_length > 0)
2360 { 1674 {
2361 scan_and_compress_trail (finger_trail, &finger_trail_length, finger_identity); 1675 trail_id = trail_list_iterator->trail_id;
1676 target_friend =
1677 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1678 &trail_list_iterator->trail_head->peer);
1679 GDS_NEIGHBOURS_send_trail_teardown (my_identity, finger->finger_identity,
1680 trail_id, GDS_ROUTING_SRC_TO_DEST,
1681 target_friend);
2362 } 1682 }
2363 } 1683 }
2364
2365 /* FIXME: handle the case when addition in peer map failed. */
2366 if(GNUNET_OK == add_new_entry (finger_identity,finger_trail,finger_trail_length, finger_map_index))
2367 new_entry_added = GNUNET_YES;
2368 else
2369 return GNUNET_NO;
2370
2371 update_current_search_finger_index:
2372 if (0 == finger_map_index)
2373 {
2374 current_search_finger_index = PREDECESSOR_FINGER_ID;
2375 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,finger_identity))
2376 send_verify_successor_message();
2377 }
2378 else if (GNUNET_YES == compare_new_entry_and_successor (finger_identity,finger_map_index))
2379 {
2380 current_search_finger_index = 0;
2381 }
2382 else
2383 {
2384 current_search_finger_index = current_search_finger_index - 1;
2385 }
2386
2387 return new_entry_added;
2388} 1684}
2389 1685
2390 1686
2391/** 1687/**
2392 * FIXME: URGNET: adapt it for trail list. 1688 * Decrement the trail count of the first friend to reach the finger
2393 * Check if the successor chosen is congested or has crossed trail threshold. 1689 * In case finger is the friend, then decrement its trail count.
2394 * @param successor Successor to be checked. 1690 * @param finger
2395 * @return #GNUNET_YES in case its is either congested or has crossed trail threshold.
2396 * #GNUNET_NO if its good to go.
2397 */ 1691 */
2398static int 1692static void
2399check_friend_threshold_and_congestion (struct Sorting_List *successor) 1693decrement_friend_trail_count (struct FingerInfo *finger)
2400{ 1694{
2401 struct FriendInfo *friend; 1695 struct TrailList *trail_list_iterator;
1696 struct FriendInfo *target_friend;
1697 int i = 0;
2402 1698
2403 if (successor->type == FRIEND) 1699 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger->finger_identity,
2404 { 1700 &my_identity))
2405 friend = successor->data; 1701 return;
2406 }
2407 else if (successor->type == FINGER)
2408 {
2409 struct FingerInfo *finger = successor->data;
2410 if (finger->first_trail_length > 0)
2411 {
2412 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2413 &(finger->first_trail_head->peer));
2414 }
2415 else
2416 {
2417 if (0 != GNUNET_CRYPTO_cmp_peer_identity(&my_identity, &finger->finger_identity))
2418 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(finger->finger_identity));
2419 else
2420 return GNUNET_YES;
2421 }
2422 }
2423 1702
2424 if ((friend->trails_count == TRAIL_THROUGH_FRIEND_THRESHOLD)|| 1703 for (i = 0; i < finger->trails_count; i++)
2425 ((0 != GNUNET_TIME_absolute_get_remaining (friend->congestion_duration).rel_value_us)))
2426 { 1704 {
2427 return GNUNET_YES; 1705 trail_list_iterator = &finger->trail_list[i];
1706 if (trail_list_iterator->trail_length > 0)
1707 target_friend =
1708 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1709 &trail_list_iterator->trail_head->peer);
1710 else
1711 target_friend =
1712 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1713 &finger->finger_identity);
1714
1715 target_friend->trails_count--;
1716 trail_list_iterator->first_friend_trail_count--;
2428 } 1717 }
2429 else 1718 return;
2430 return GNUNET_NO;
2431} 1719}
2432 1720
2433 1721
2434/** 1722/**
2435 * Find the next successor for key_value as the earlier selected successor is either 1723 * Free finger and its trail.
2436 * congested or have crossed trail threshold. 1724 * @param finger Finger to be freed.
2437 * @param all_known_peers Array that contains my_identity, value, friends and fingers.
2438 * @param array_size Total number of entries in @a all_known_peers.
2439 * @param start_index Index at which original successor is located.
2440 * @param search_index Index at which our possible current successor is located.
2441 * @param count Number of times this function has been called.
2442 * @return successor, in case found.
2443 * NULL, in case of error.
2444 */ 1725 */
2445static struct Sorting_List * 1726static void
2446get_next_successor (struct Sorting_List *all_known_peers, 1727free_finger (struct FingerInfo *finger)
2447 unsigned int array_size, int start_index,
2448 int search_index, int count)
2449{ 1728{
2450 struct Sorting_List *next_peer; 1729 struct TrailList *trail_list_iterator;
2451 1730 struct Trail *trail_element;
2452 if (search_index == start_index) 1731 unsigned int i;
2453 return NULL;
2454 next_peer = GNUNET_malloc (sizeof (struct Sorting_List));
2455 memcpy (next_peer, &all_known_peers[search_index], sizeof (struct Sorting_List));
2456
2457 if (next_peer->type == MY_ID)
2458 return next_peer;
2459 1732
2460 if ((next_peer->type == VALUE) || 1733 for (i = 0; i < finger->trails_count; i++)
2461 (GNUNET_YES == check_friend_threshold_and_congestion (next_peer)))
2462 { 1734 {
2463 search_index = (search_index + 1) % array_size; 1735 trail_list_iterator = &finger->trail_list[i];
2464 count++; 1736 while (NULL != (trail_element = trail_list_iterator->trail_head))
2465 return get_next_successor (all_known_peers, array_size, start_index, search_index, count); 1737 {
1738 GNUNET_CONTAINER_DLL_remove (trail_list_iterator->trail_head,
1739 trail_list_iterator->trail_tail, trail_element);
1740 GNUNET_free (trail_element);
1741 }
2466 } 1742 }
2467 else 1743 GNUNET_free (finger);
2468 return next_peer;
2469} 1744}
2470 1745
2471 1746
2472/** 1747/**
2473 * Search the current location of successor in all_known_peers array. 1748 * Check if new finger is closer than existing_finger. If both new finger and
2474 * @param all_known_peers Array which contains my_id, key value, friends and fingers. 1749 * existing finger are same then we may add a new trail (if there is space)
2475 * @param array_size Total number of entries in @a all_known_peers 1750 * or choose the best trail among existing trails and new trails.
2476 * @param search_value 64 bit value of successor. 1751 * @param existing_finger Finger present in finger_peermap at @a finger_map_index
2477 * @return Index of array at which value is stored, 1752 * @param new_finger_identity Peer identity of new finger.
2478 * #GNUNET_SYSERR in case of error. 1753 * @param new_finger_trail Trail to reach from source to new_finger.
1754 * @param new_finger_trail_length Total number of peers in @a new_finger_trail.
1755 * @param trail_id Unique identifier of trail.
1756 * @param finger_map_index Index in finger map.
1757 * @return #GNUNET_YES if the new finger is closest.
1758 * #GNUNET_NO either new_finger and existing_finger are same, or
1759 * existing_finger is closest.
2479 */ 1760 */
2480static int 1761static int
2481get_successor_location (struct Sorting_List *all_known_peers, size_t array_size, 1762is_new_finger_closest (struct FingerInfo *existing_finger,
2482 uint64_t search_value) 1763 struct GNUNET_PeerIdentity new_finger_identity,
2483{ 1764 struct GNUNET_PeerIdentity *new_finger_trail,
2484 int k; 1765 unsigned int new_finger_trail_length,
1766 struct GNUNET_HashCode new_finger_trail_id,
1767 unsigned int finger_map_index)
1768{
1769 struct GNUNET_PeerIdentity *closest_peer;
1770 uint64_t my_id64;
2485 1771
2486 while (0 != memcmp (&all_known_peers[k].data, &search_value, sizeof (uint64_t))) 1772 if (NULL == existing_finger)
2487 { 1773 return GNUNET_YES;
2488 k++; 1774
2489 } 1775 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
2490 if (k == array_size) 1776 &new_finger_identity))
2491 return GNUNET_SYSERR;
2492 else
2493 return k;
2494}
2495
2496
2497/**
2498 * Initialize all_known_peers with my_id, value, friends and fingers.
2499 * @param all_known_peers Empty all_known_peers
2500 * @param size Total number of elements in all_known_peers
2501 */
2502static void
2503init_all_known_peers (struct Sorting_List *all_known_peers, int size, uint64_t value)
2504{
2505 struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
2506 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2507 struct GNUNET_PeerIdentity key_ret;
2508 struct FriendInfo *friend;
2509 struct FingerInfo *finger;
2510 unsigned int finger_index;
2511 unsigned int friend_index;
2512 int k;
2513 int j;
2514
2515 for (k = 0; k < size; k++)
2516 all_known_peers[k].peer_id = 0;
2517
2518 /* Copy your identity at 0th index in all_known_peers. */
2519 j = 0;
2520 memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
2521 all_known_peers[j].type = MY_ID;
2522 all_known_peers[j].data = 0;
2523 j++;
2524
2525 /* Copy value */
2526 all_known_peers[j].peer_id = value;
2527 all_known_peers[j].type = VALUE;
2528 all_known_peers[j].data = 0;
2529 j++;
2530
2531 /* Iterate over friend peer map and copy all the elements into array. */
2532 friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
2533 for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
2534 { 1777 {
2535 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend)) 1778 memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1779 closest_peer = select_closest_peer (&existing_finger->finger_identity,
1780 &new_finger_identity,
1781 my_id64, finger_map_index);
1782
1783 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&new_finger_identity, closest_peer))
2536 { 1784 {
2537 memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t)); 1785 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity,
2538 all_known_peers[j].type = FRIEND; 1786 &new_finger_identity)) /* FIXME: not sure what to do here? */
2539 all_known_peers[j].data = friend; 1787 return GNUNET_NO;
2540 j++; 1788
1789 send_trail_teardown (existing_finger);
1790 decrement_friend_trail_count (existing_finger);
1791 free_finger (existing_finger);
1792 return GNUNET_YES;
2541 } 1793 }
2542 } 1794 }
2543 1795 else
2544
2545 /* Iterate over finger map and copy all the entries into all_known_peers array. */
2546 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2547 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2548 { 1796 {
2549 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger)) 1797 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
1798 &my_identity))
2550 { 1799 {
2551 memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t)); 1800 if (NULL ==
2552 all_known_peers[j].type = FINGER; 1801 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2553 all_known_peers[j].data = finger; 1802 &(existing_finger->finger_identity)))
2554 j++; 1803 {
1804 if (existing_finger->trails_count < MAXIMUM_TRAILS_PER_FINGER)
1805 add_new_trail (existing_finger, new_finger_trail,
1806 new_finger_trail_length, new_finger_trail_id);
1807 else
1808 select_and_replace_trail (existing_finger, new_finger_trail,
1809 new_finger_trail_length, new_finger_trail_id);
1810 }
2555 } 1811 }
2556 } 1812 }
2557 1813 return GNUNET_NO;
2558 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2559 GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
2560} 1814}
2561 1815
2562 1816
2563/** 1817/**
2564 * FIXME: 1. In case all the peers are congested/threshold then by default my_id is 1818 * Add a new entry in finger hashmap at finger_map_index
2565 * chosen. There is no limit on number of peers which can keep me as their finger. 1819 * @param finger_identity Peer Identity of new finger
2566 * Should there be limit? If yes then we need to keep a counter of number of peers 1820 * @param finger_trail Trail to reach from me to finger (excluding both end points).
2567 * that keep me as fingers. This counter may/may not give the correct value as 1821 * @param finger_trail_length Total number of peers in @a finger_trail.
2568 * that peer may have found a better finger. So should reset the limit at some 1822 * @param trail_id Unique identifier of the trail.
2569 * interval. 1823 * @param finger_map_index Index in finger hashmap.
2570 * 2. Change the finger code, TRAIL_LIST. URGENT 1824 * @return #GNUNET_OK if new entry is added
2571 * Find closest successor for the value. 1825 * #GNUNET_NO -- FIXME: need to check what value does hahsmap put
2572 * @param value Value for which we are looking for successor 1826 * returns on failure.
2573 * @param[out] current_destination set to my_identity in case I am the final destination,
2574 * set to friend identity in case friend is final destination,
2575 * set to first friend to reach to finger, in case finger
2576 * is final destination.
2577 * @param[out] current_source set to my_identity.
2578 * @param finger_map_index Index in finger peer map.
2579 * @return Peer identity of next hop to send trail setup message to
2580 */ 1827 */
2581static struct GNUNET_PeerIdentity * 1828static int
2582find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination, 1829add_new_entry (struct GNUNET_PeerIdentity finger_identity,
2583 struct GNUNET_PeerIdentity *current_source, unsigned int finger_map_index) 1830 struct GNUNET_PeerIdentity *finger_trail,
1831 unsigned int finger_trail_length,
1832 struct GNUNET_HashCode trail_id,
1833 unsigned int finger_map_index)
2584{ 1834{
2585 struct Sorting_List *successor; 1835 struct FingerInfo *new_entry;
2586 unsigned int size; 1836 struct FriendInfo *first_trail_hop;
2587 1837 struct TrailList *first_trail;
2588 size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+ 1838 int i = 0;
2589 GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
2590 2;
2591
2592 struct Sorting_List all_known_peers[size];
2593 init_all_known_peers (all_known_peers, size, value);
2594 qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
2595 1839
2596 if (PREDECESSOR_FINGER_ID == finger_map_index) 1840 new_entry = GNUNET_new (struct FingerInfo);
2597 successor = find_closest_predecessor (all_known_peers, value, size); 1841 new_entry->finger_identity = finger_identity;
2598 else 1842 new_entry->finger_map_index = finger_map_index;
2599 successor = find_closest_successor (all_known_peers, value, size); 1843 new_entry->trails_count = 1;
2600 1844
2601 if ((successor->type != MY_ID) && (successor->type != VALUE)) 1845 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2602 { 1846 {
2603 if (GNUNET_YES == check_friend_threshold_and_congestion (successor)) 1847 if (finger_trail_length > 0)
2604 { 1848 {
2605 int search_index = get_successor_location (all_known_peers, size, successor->peer_id); 1849 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2606 successor = get_next_successor (all_known_peers, size, search_index, search_index + 1, 0); 1850 &finger_trail[0]);
2607 } 1851 }
2608 } 1852 else
2609
2610 if (successor->type == MY_ID)
2611 {
2612 memcpy (current_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2613 return &my_identity;
2614 }
2615 else if (successor->type == FRIEND)
2616 {
2617 struct FriendInfo *target_friend = successor->data;
2618 memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
2619 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity));
2620 return current_destination;
2621 }
2622 else if (successor->type == FINGER)
2623 {
2624 struct GNUNET_PeerIdentity *next_hop;
2625 struct FingerInfo *finger;
2626 finger = successor->data;
2627 next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2628
2629 if (finger->first_trail_length > 0)
2630 { 1853 {
2631 struct TrailPeerList *iterator; 1854 first_trail_hop = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2632 iterator = GNUNET_malloc (sizeof (struct TrailPeerList)); 1855 &finger_identity);
2633 iterator = finger->first_trail_head;
2634 memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2635 } 1856 }
2636 else /* This means finger is our friend. */
2637 memcpy (next_hop, &(finger->finger_identity), sizeof(struct GNUNET_PeerIdentity));
2638 1857
2639 memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity)); 1858 first_trail_hop->trails_count++;
2640 memcpy (current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity)); 1859 first_trail = &new_entry->trail_list[0];
2641 return next_hop; 1860 first_trail->first_friend_trail_count = first_trail_hop->trails_count;
2642 } 1861
2643 else 1862 while (i < finger_trail_length)
2644 { 1863 {
2645 return NULL; 1864 struct Trail *element = GNUNET_new (struct Trail);
1865
1866 element->next = NULL;
1867 element->prev = NULL;
1868 element->peer = finger_trail[i];
1869 GNUNET_CONTAINER_DLL_insert_tail (first_trail->trail_head,
1870 first_trail->trail_tail,
1871 element);
1872 i++;
1873 }
2646 } 1874 }
1875
1876 return GNUNET_CONTAINER_multihashmap32_put (finger_hashmap,
1877 new_entry->finger_map_index,
1878 new_entry,
1879 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
2647} 1880}
2648 1881
2649 1882
2650/** 1883/**
2651 * Construct a Put message and send it to target_peer. 1884 * Scan the trail to check if there is any other friend in the trail other than
2652 * @param key Key for the content 1885 * first hop. If yes the shortcut the trail, send trail compression message to
2653 * @param block_type Type of the block 1886 * peers which are no longer part of trail and send back the updated trail
2654 * @param options Routing options 1887 * and trail_length to calling function.
2655 * @param desired_replication_level Desired replication count 1888 * @param finger_identity Finger whose trail we will scan.
2656 * @param current_destination Next current destination which will get this message. 1889 * @param finger_trail [in, out] Trail to reach from source to finger,
2657 * @param current_source Source for @a current_destination 1890 * @param finger_trail_length Total number of peers in original finger_trail.
2658 * @param target_peer Peer to which this message will be forwarded. 1891 * @param finger_trail_id Unique identifier of the finger trail.
2659 * @param hop_count Number of hops traversed so far. 1892 * @return updated trail length in case we shortcut the trail, else original
2660 * @param put_path_length Total number of peers in @a put_path 1893 * trail length.
2661 * @param put_path Number of peers traversed so far
2662 * @param expiration_time When does the content expire
2663 * @param data Content to store
2664 * @param data_size Size of content @a data in bytes
2665 */ 1894 */
2666void 1895static int
2667GDS_NEIGHBOURS_send_put (const struct GNUNET_HashCode *key, 1896scan_and_compress_trail (struct GNUNET_PeerIdentity finger_identity,
2668 enum GNUNET_BLOCK_Type block_type, 1897 struct GNUNET_PeerIdentity *trail,
2669 enum GNUNET_DHT_RouteOption options, 1898 unsigned int trail_length,
2670 uint32_t desired_replication_level, 1899 struct GNUNET_HashCode trail_id)
2671 struct GNUNET_PeerIdentity current_destination,
2672 struct GNUNET_PeerIdentity current_source,
2673 struct GNUNET_PeerIdentity *target_peer,
2674 uint32_t hop_count,
2675 uint32_t put_path_length,
2676 struct GNUNET_PeerIdentity *put_path,
2677 struct GNUNET_TIME_Absolute expiration_time,
2678 const void *data, size_t data_size)
2679{ 1900{
2680 struct PeerPutMessage *ppm;
2681 struct P2PPendingMessage *pending;
2682 struct FriendInfo *target_friend; 1901 struct FriendInfo *target_friend;
2683 struct GNUNET_PeerIdentity *pp; 1902 int i;
2684 size_t msize;
2685
2686 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size +
2687 sizeof (struct PeerPutMessage);
2688 1903
2689 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE) 1904 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &finger_identity))
2690 { 1905 {
2691 put_path_length = 0; 1906 trail = NULL;
2692 msize = data_size + sizeof (struct PeerPutMessage); 1907 return 0;
2693 } 1908 }
2694 1909
2695 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE) 1910 if (GNUNET_CONTAINER_multipeermap_get (friend_peermap, &finger_identity))
2696 { 1911 {
2697 GNUNET_break (0); 1912 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
2698 return; 1913 &trail[0]);
1914 GDS_NEIGHBOURS_send_trail_compression (my_identity, finger_identity,
1915 trail_id, finger_identity,
1916 target_friend);
1917 trail = NULL;
1918 return 0;
2699 } 1919 }
2700 1920
2701 /* This is the first call made from clients file. So, we should search for the 1921 for ( i = trail_length - 1; i > 0; i--)
2702 target_friend. */
2703 if (NULL == target_peer)
2704 { 1922 {
2705 uint64_t key_value; 1923 if (NULL != GNUNET_CONTAINER_multipeermap_get (friend_peermap, &trail[i]))
2706 struct GNUNET_PeerIdentity *next_hop;
2707
2708 memcpy (&key_value, key, sizeof (uint64_t));
2709 next_hop = find_successor (key_value, &current_destination, &current_source,PUT_GET_REQUEST);
2710 if (0 == GNUNET_CRYPTO_cmp_peer_identity(next_hop, &my_identity))
2711 { 1924 {
2712 /* I am the destination but we have already done datacache_put in client file. */ 1925 struct FriendInfo *target_friend;
2713 return; 1926 int j = 0;
1927
1928 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1929 &trail[0]);
1930 GDS_NEIGHBOURS_send_trail_compression (my_identity, finger_identity,
1931 trail_id, trail[i],
1932 target_friend);
1933
1934 /* Copy the trail from index i to index trail_length -1 and change
1935 trail length and return */
1936 while (i < trail_length)
1937 {
1938 memcpy (&trail[j], &trail[i], sizeof(struct GNUNET_PeerIdentity));
1939 j++;
1940 i++;
1941 }
1942 trail_length = j+1;
1943 break;
2714 } 1944 }
2715 else
2716 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2717 }
2718
2719 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2720 pending->timeout = expiration_time;
2721 ppm = (struct PeerPutMessage *) &pending[1];
2722 pending->msg = &ppm->header;
2723 ppm->header.size = htons (msize);
2724 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
2725 ppm->options = htonl (options);
2726 ppm->block_type = htonl (block_type);
2727 ppm->hop_count = htonl (hop_count + 1);
2728 ppm->desired_replication_level = htonl (desired_replication_level);
2729 ppm->put_path_length = htonl (put_path_length);
2730 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
2731 ppm->key = *key;
2732 ppm->current_destination = current_destination;
2733 ppm->current_source = current_source;
2734
2735 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
2736 if (put_path_length != 0)
2737 {
2738 memcpy (pp, put_path,
2739 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2740 } 1945 }
2741 memcpy (&pp[put_path_length], data, data_size); 1946 return trail_length;
2742 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2743 target_friend->pending_count++;
2744 process_friend_queue (target_friend);
2745} 1947}
2746 1948
2747 1949
2748/** 1950/**
2749 * Construct a Get message and send it to target_peer. 1951 * Send verify successor message to your successor on all trails to reach successor.
2750 * @param key Key for the content 1952 * @param successor My current successor
2751 * @param block_type Type of the block
2752 * @param options Routing options
2753 * @param desired_replication_level Desired replication count
2754 * @param current_destination Next current destination which will get this message.
2755 * @param current_source Source for @a current_destination
2756 * @param target_peer Peer to which this message will be forwarded.
2757 * @param hop_count Number of hops traversed so far.
2758 * @param data Content to store
2759 * @param data_size Size of content @a data in bytes
2760 * @param get_path_length Total number of peers in @a get_path
2761 * @param get_path Number of peers traversed so far
2762 */ 1953 */
2763void 1954static void
2764GDS_NEIGHBOURS_send_get (const struct GNUNET_HashCode *key, 1955send_verify_successor_message (struct FingerInfo *successor)
2765 enum GNUNET_BLOCK_Type block_type,
2766 enum GNUNET_DHT_RouteOption options,
2767 uint32_t desired_replication_level,
2768 struct GNUNET_PeerIdentity current_destination,
2769 struct GNUNET_PeerIdentity current_source,
2770 struct GNUNET_PeerIdentity *target_peer,
2771 uint32_t hop_count,
2772 uint32_t get_path_length,
2773 struct GNUNET_PeerIdentity *get_path)
2774{ 1956{
2775 struct PeerGetMessage *pgm; 1957 struct TrailList *trail_list_iterator;
2776 struct P2PPendingMessage *pending; 1958 struct GNUNET_HashCode trail_id;
1959 struct GNUNET_PeerIdentity next_hop;
2777 struct FriendInfo *target_friend; 1960 struct FriendInfo *target_friend;
2778 struct GNUNET_PeerIdentity *gp; 1961 int i;
2779 size_t msize;
2780
2781 msize = sizeof (struct PeerGetMessage) +
2782 (get_path_length * sizeof (struct GNUNET_PeerIdentity));
2783
2784 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2785 {
2786 GNUNET_break (0);
2787 return;
2788 }
2789 1962
2790 if (NULL == target_peer) 1963 for (i = 0; i < successor->trails_count; i++)
2791 { 1964 {
2792 struct GNUNET_PeerIdentity *next_hop; 1965 trail_list_iterator = &successor->trail_list[i];
2793 uint64_t key_value; 1966 if (trail_list_iterator->trail_length > 0)
2794 1967 next_hop = trail_list_iterator->trail_head->peer;
2795 memcpy (&key_value, key, sizeof (uint64_t));
2796 // FIXME: endianess of key_value!?
2797 next_hop = find_successor (key_value, &current_destination, &current_source, PUT_GET_REQUEST);
2798 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity,next_hop))
2799 {
2800 GDS_DATACACHE_handle_get (key,block_type, NULL, 0,
2801 NULL, 0, 1, &my_identity, NULL,&my_identity);
2802 return;
2803 }
2804 else 1968 else
2805 { 1969 next_hop = successor->finger_identity;
2806 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop); 1970
2807 } 1971 trail_id = trail_list_iterator->trail_id;
2808 } 1972 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2809 1973 GDS_NEIGHBOURS_send_verify_successor_message (my_identity,
2810 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); 1974 successor->finger_identity,
2811 pending->importance = 0; /* FIXME */ 1975 trail_id, target_friend);
2812 pgm = (struct PeerGetMessage *) &pending[1];
2813 pending->msg = &pgm->header;
2814 pgm->header.size = htons (msize);
2815 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
2816 pgm->get_path_length = htonl (get_path_length);
2817 pgm->key = *key;
2818 pgm->current_destination = current_destination;
2819 pgm->current_source = current_source;
2820 pgm->hop_count = htonl (hop_count + 1);
2821
2822 if (get_path != 0)
2823 {
2824 gp = (struct GNUNET_PeerIdentity *) &pgm[1];
2825 memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity));
2826 } 1976 }
2827 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2828 target_friend->pending_count++;
2829 process_friend_queue (target_friend);
2830} 1977}
2831 1978
2832 1979
2833/** 1980/**
2834 * Send the get result to requesting client. 1981 * Check if there is already an entry in finger peermap for given finger map index.
2835 * @param key Key of the requested data. 1982 * If yes, then select the closest finger. If new and existing finger are same,
2836 * @param type Block type 1983 * the check if you can store more trails. If yes then add trail, else keep the best
2837 * @param target_peer Next peer to forward the message to. 1984 * trails to reach to the finger. If the new finger is closest, add it.
2838 * @param source_peer Peer which has the data for the key. 1985 * Then, update current_search_finger_index.
2839 * @param put_path_length Number of peers in @a put_path 1986 * @param new_finger_identity Peer Identity of new finger
2840 * @param put_path Path taken to put the data at its stored location. 1987 * @param new_finger_trail Trail to reach the new finger
2841 * @param get_path_length Number of peers in @a get_path 1988 * @param new_finger_length Total number of peers in @a new_finger_trail.
2842 * @param get_path Path taken to reach to the location of the key. 1989 * @param finger_map_index Index in finger peermap.
2843 * @param expiration When will this result expire? 1990 * @param new_finger_trail_id Unique identifier of @new_finger_trail.
2844 * @param data Payload to store 1991 * @return #GNUNET_YES if the new entry is added
2845 * @param data_size Size of the @a data 1992 * #GNUNET_NO if new entry is not added, either it was discarded or
1993 * it was same as existing finger at finger map index.
2846 */ 1994 */
2847void 1995static int
2848GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key, 1996finger_table_add (struct GNUNET_PeerIdentity new_finger_identity,
2849 enum GNUNET_BLOCK_Type type, 1997 struct GNUNET_PeerIdentity *new_finger_trail,
2850 struct GNUNET_PeerIdentity *next_hop, 1998 unsigned int new_finger_trail_length,
2851 struct GNUNET_PeerIdentity *source_peer, 1999 unsigned int finger_map_index,
2852 unsigned int put_path_length, 2000 struct GNUNET_HashCode new_finger_trail_id)
2853 const struct GNUNET_PeerIdentity *put_path,
2854 unsigned int get_path_length,
2855 struct GNUNET_PeerIdentity *get_path,
2856 struct GNUNET_TIME_Absolute expiration,
2857 const void *data, size_t data_size)
2858{ 2001{
2859 struct PeerGetResultMessage *get_result; 2002 struct FingerInfo *existing_finger;
2860 struct GNUNET_PeerIdentity *get_result_path; 2003 struct FingerInfo *successor;
2861 struct GNUNET_PeerIdentity *pp; 2004 unsigned int new_entry_added = GNUNET_NO;
2862 struct P2PPendingMessage *pending;
2863 struct FriendInfo *target_friend;
2864 int current_path_index;
2865 size_t msize;
2866 2005
2867 msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size + 2006 int new_finger_updated_trail_length =
2868 sizeof (struct PeerPutMessage); 2007 scan_and_compress_trail (new_finger_identity, new_finger_trail,
2008 new_finger_trail_length, new_finger_trail_id);
2869 2009
2870 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE) 2010 successor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2871 { 2011 finger_map_index);
2872 GNUNET_break (0); 2012 existing_finger = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
2873 return; 2013 finger_map_index);
2014
2015 if (GNUNET_YES == is_new_finger_closest (existing_finger,
2016 new_finger_identity,
2017 new_finger_trail,
2018 new_finger_updated_trail_length,
2019 new_finger_trail_id, finger_map_index))
2020 {
2021 GNUNET_assert (GNUNET_YES == add_new_entry (new_finger_identity,
2022 new_finger_trail,
2023 new_finger_updated_trail_length,
2024 new_finger_trail_id,
2025 finger_map_index));
2026 new_entry_added = GNUNET_YES;
2874 } 2027 }
2875 2028
2876 if(get_path_length > 0) 2029 if (0 == finger_map_index)
2877 { 2030 {
2878 current_path_index = search_my_index(get_path, get_path_length); 2031 current_search_finger_index = PREDECESSOR_FINGER_ID;
2879 if (GNUNET_SYSERR == current_path_index) 2032
2033 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_identity,&new_finger_identity))
2880 { 2034 {
2881 GNUNET_break (0); 2035 send_verify_successor_message (successor);
2882 return;
2883 } 2036 }
2884 } 2037 }
2885 if (0 == current_path_index) 2038 else if (0 == GNUNET_CRYPTO_cmp_peer_identity (&new_finger_identity,
2039 &(successor->finger_identity)))
2886 { 2040 {
2887 GDS_CLIENTS_handle_reply (expiration, key, get_path_length, get_path, put_path_length, 2041 current_search_finger_index = 0;
2888 put_path, type, data_size, data);
2889 return;
2890 }
2891
2892 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2893 pending->importance = 0;
2894 get_result = (struct PeerGetResultMessage *)&pending[1];
2895 pending->msg = &get_result->header;
2896 get_result->header.size = htons (msize);
2897 get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT);
2898 get_result->key = *key;
2899 memcpy (&(get_result->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2900 get_result->expiration_time = expiration;
2901
2902 if (get_path_length != 0)
2903 {
2904 get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1];
2905 memcpy (get_result_path, get_path,
2906 sizeof (struct GNUNET_PeerIdentity) * get_path_length);
2907 }
2908 memcpy (&get_result_path[get_path_length], data, data_size);
2909
2910 /* FIXME: Is this correct? */
2911 if (put_path_length != 0)
2912 {
2913 pp = (struct GNUNET_PeerIdentity *)&get_result_path[1];
2914 memcpy (pp, put_path,sizeof (struct GNUNET_PeerIdentity) * put_path_length);
2915 }
2916 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2917 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2918 target_friend->pending_count++;
2919 process_friend_queue (target_friend);
2920}
2921
2922
2923/**
2924 * Send trail rejection message to the peer which sent me a trail setup message.
2925 * @param source_peer Source peer which wants to set up the trail.
2926 * @param finger_identity Value whose successor will be the finger of @a source_peer.
2927 * @param congested_peer Peer which has send trail rejection message.
2928 * @param next_hop Peer to which this message should be forwarded.
2929 * @param finger_map_index Index in @a source_peer finger peermap.
2930 * @param trail_peer_list Trail followed to reach from @a source_peer to next_hop,
2931 * NULL, in case the @a congested_peer was the first peer
2932 * to which trail setup message was forwarded.
2933 * @param trail_length Number of peers in trail_peer_list.
2934 * @param congestion_timeout Time duration for which @a congested peer will be
2935 * congested.
2936 */
2937void
2938GDS_NEIGHBOURS_send_trail_rejection (const struct GNUNET_PeerIdentity *source_peer,
2939 uint64_t finger_identity,
2940 const struct GNUNET_PeerIdentity *congested_peer,
2941 const struct GNUNET_PeerIdentity *next_hop,
2942 unsigned int finger_map_index,
2943 struct GNUNET_PeerIdentity *trail_peer_list,
2944 unsigned int trail_length,
2945 struct GNUNET_TIME_Relative congestion_timeout)
2946{
2947 struct PeerTrailRejectionMessage *trail_rejection;
2948 struct GNUNET_PeerIdentity *trail_list;
2949 struct P2PPendingMessage *pending;
2950 struct FriendInfo *target_friend;
2951 size_t msize;
2952
2953 msize = trail_length * sizeof(struct GNUNET_PeerIdentity) +
2954 sizeof (struct PeerTrailRejectionMessage);
2955
2956 if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
2957 {
2958 GNUNET_break (0);
2959 return;
2960 }
2961
2962 pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
2963 pending->importance = 0;
2964 pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
2965 trail_rejection = (struct PeerTrailRejectionMessage *) &pending[1];
2966 pending->msg = &trail_rejection->header;
2967 trail_rejection->header.size = htons (msize);
2968 trail_rejection->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
2969 memcpy (&(trail_rejection->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
2970 memcpy (&(trail_rejection->congested_peer), congested_peer, sizeof (struct GNUNET_PeerIdentity));
2971 memcpy (&(trail_rejection->finger_identity_value), &finger_identity, sizeof (uint64_t));
2972 trail_rejection->finger_map_index = htonl (finger_map_index);
2973 trail_rejection->trail_length = htonl (trail_length);
2974 trail_rejection->congestion_time = congestion_timeout;
2975
2976 if (trail_length != 0)
2977 {
2978 trail_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
2979 memcpy (trail_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
2980 } 2042 }
2043 else
2044 current_search_finger_index = current_search_finger_index - 1;
2981 2045
2982 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop); 2046 return new_entry_added;
2983 GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
2984 target_friend->pending_count++;
2985 process_friend_queue (target_friend);
2986} 2047}
2987 2048
2988 2049
@@ -2998,155 +2059,7 @@ static int
2998handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer, 2059handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer,
2999 const struct GNUNET_MessageHeader *message) 2060 const struct GNUNET_MessageHeader *message)
3000{ 2061{
3001 struct PeerPutMessage *put; 2062 return GNUNET_OK;
3002 struct GNUNET_PeerIdentity *put_path;
3003 struct GNUNET_HashCode test_key;
3004 enum GNUNET_DHT_RouteOption options;
3005 struct GNUNET_PeerIdentity current_destination;
3006 struct GNUNET_PeerIdentity current_source;
3007 struct GNUNET_PeerIdentity *next_hop;
3008 void *payload;
3009 size_t msize;
3010 uint32_t putlen;
3011 size_t payload_size;
3012 uint64_t key_value;
3013
3014 msize = ntohs (message->size);
3015 if (msize < sizeof (struct PeerPutMessage))
3016 {
3017 GNUNET_break_op (0);
3018 return GNUNET_YES;
3019 }
3020
3021 put = (struct PeerPutMessage *) message;
3022 putlen = ntohl (put->put_path_length);
3023
3024 if ((msize <
3025 sizeof (struct PeerPutMessage) +
3026 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3027 (putlen >
3028 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3029 {
3030 GNUNET_break_op (0);
3031 return GNUNET_YES;
3032 }
3033
3034 current_destination = put->current_destination;
3035 current_source = put->current_source;
3036 put_path = (struct GNUNET_PeerIdentity *) &put[1];
3037 payload = &put_path[putlen];
3038 options = ntohl (put->options);
3039 payload_size = msize - (sizeof (struct PeerPutMessage) +
3040 putlen * sizeof (struct GNUNET_PeerIdentity));
3041
3042 switch (GNUNET_BLOCK_get_key (GDS_block_context, ntohl (put->block_type),
3043 payload, payload_size, &test_key))
3044 {
3045 case GNUNET_YES:
3046 if (0 != memcmp (&test_key, &put->key, sizeof (struct GNUNET_HashCode)))
3047 {
3048 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
3049 GNUNET_break_op (0);
3050 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
3051 "PUT with key `%s' for block with key %s\n",
3052 put_s, GNUNET_h2s_full (&test_key));
3053 GNUNET_free (put_s);
3054 return GNUNET_YES;
3055 }
3056 break;
3057 case GNUNET_NO:
3058 GNUNET_break_op (0);
3059 return GNUNET_YES;
3060 case GNUNET_SYSERR:
3061 /* cannot verify, good luck */
3062 break;
3063 }
3064
3065 if (ntohl (put->block_type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
3066 {
3067 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
3068 ntohl (put->block_type),
3069 NULL, /* query */
3070 NULL, 0, /* bloom filer */
3071 NULL, 0, /* xquery */
3072 payload, payload_size))
3073 {
3074 case GNUNET_BLOCK_EVALUATION_OK_MORE:
3075 case GNUNET_BLOCK_EVALUATION_OK_LAST:
3076 break;
3077
3078 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
3079 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
3080 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
3081 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
3082 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
3083 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
3084 default:
3085 GNUNET_break_op (0);
3086 return GNUNET_OK;
3087 }
3088 }
3089
3090 /* extend 'put path' by sender */
3091 struct GNUNET_PeerIdentity pp[putlen + 1];
3092 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
3093 {
3094 memcpy (pp, put_path, putlen * sizeof (struct GNUNET_PeerIdentity));
3095 pp[putlen] = *peer;
3096 putlen++;
3097 }
3098 else
3099 putlen = 0;
3100
3101 memcpy (&key_value, &(put->key), sizeof (uint64_t));
3102 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&current_destination, &my_identity)))
3103 {
3104 next_hop = GDS_ROUTING_search (&current_source, &current_destination, peer);
3105 }
3106 else
3107 {
3108 next_hop = find_successor (key_value, &current_destination, &current_source,PUT_GET_REQUEST);
3109 }
3110
3111 if (NULL == next_hop)
3112 {
3113 GNUNET_STATISTICS_update (GDS_stats,
3114 gettext_noop ("# Next hop to forward the packet not found "
3115 "trail setup request, packet dropped."),
3116 1, GNUNET_NO);
3117 return GNUNET_SYSERR;
3118 }
3119
3120 GDS_CLIENTS_process_put (options,
3121 ntohl (put->block_type),
3122 ntohl (put->hop_count),
3123 ntohl (put->desired_replication_level),
3124 putlen, pp,
3125 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3126 &put->key,
3127 payload,
3128 payload_size);
3129
3130 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop)) /* I am the final destination */
3131 {
3132 GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put->expiration_time),
3133 &(put->key),putlen, pp, ntohl (put->block_type),
3134 payload_size, payload);
3135 return GNUNET_YES;
3136 }
3137 else
3138 {
3139 GDS_NEIGHBOURS_send_put (&put->key,
3140 ntohl (put->block_type),ntohl (put->options),
3141 ntohl (put->desired_replication_level),
3142 current_destination, current_source, next_hop,
3143 ntohl (put->hop_count), putlen, pp,
3144 GNUNET_TIME_absolute_ntoh (put->expiration_time),
3145 payload, payload_size);
3146
3147 return GNUNET_YES;
3148 }
3149 return GNUNET_SYSERR;
3150} 2063}
3151 2064
3152 2065
@@ -3163,86 +2076,7 @@ static int
3163handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer, 2076handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
3164 const struct GNUNET_MessageHeader *message) 2077 const struct GNUNET_MessageHeader *message)
3165{ 2078{
3166 struct PeerGetMessage *get; 2079 return GNUNET_OK;
3167 struct GNUNET_PeerIdentity *get_path;
3168 struct GNUNET_PeerIdentity current_destination;
3169 struct GNUNET_PeerIdentity current_source;
3170 struct GNUNET_PeerIdentity *next_hop;
3171 uint32_t get_length;
3172 uint64_t key_value;
3173 size_t msize;
3174
3175 msize = ntohs (message->size);
3176 if (msize < sizeof (struct PeerGetMessage))
3177 {
3178 GNUNET_break_op (0);
3179 return GNUNET_YES;
3180 }
3181
3182 get = (struct PeerGetMessage *)message;
3183 get_length = ntohl (get->get_path_length);
3184 current_destination = get->current_destination;
3185 current_source = get->current_source;
3186 if (get_length > 0)
3187 get_path = (struct GNUNET_PeerIdentity *)&get[1];
3188
3189 if ((msize <
3190 sizeof (struct PeerGetMessage) +
3191 get_length * sizeof (struct GNUNET_PeerIdentity)) ||
3192 (get_length >
3193 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3194 {
3195 GNUNET_break_op (0);
3196 return GNUNET_YES;
3197 }
3198
3199 /* Add sender to get path */
3200 struct GNUNET_PeerIdentity gp[get_length + 1];
3201 memcpy (gp, get_path, get_length * sizeof (struct GNUNET_PeerIdentity));
3202 gp[get_length + 1] = *peer;
3203 get_length = get_length + 1;
3204
3205 memcpy (&key_value, &(get->key), sizeof (uint64_t));
3206 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&current_destination, &my_identity)))
3207 {
3208 next_hop = GDS_ROUTING_search (&current_source, &current_destination, peer);
3209 }
3210 else
3211 {
3212 next_hop = find_successor (key_value, &current_destination, &current_source,PUT_GET_REQUEST);
3213 }
3214
3215 if (NULL == next_hop)
3216 {
3217 GNUNET_STATISTICS_update (GDS_stats,
3218 gettext_noop ("# Next hop to forward the packet not found "
3219 "trail setup request, packet dropped."),
3220 1, GNUNET_NO);
3221 return GNUNET_SYSERR;
3222 }
3223 if (0 == GNUNET_CRYPTO_cmp_peer_identity(&my_identity, next_hop))
3224 {
3225 /* I am the destination.*/
3226 struct GNUNET_PeerIdentity final_get_path[get_length+1];
3227 struct GNUNET_PeerIdentity next_hop;
3228
3229 memcpy (final_get_path, gp, get_length * sizeof (struct GNUNET_PeerIdentity));
3230 memcpy (&final_get_path[get_length+1], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3231 get_length = get_length + 1;
3232 memcpy (&next_hop, &final_get_path[get_length-2], sizeof (struct GNUNET_PeerIdentity));
3233 GDS_DATACACHE_handle_get (&(get->key),(get->block_type), NULL, 0, NULL, 0,
3234 get_length, final_get_path,&next_hop, &my_identity);
3235
3236 return GNUNET_YES;
3237 }
3238 else
3239 {
3240 GDS_NEIGHBOURS_send_get (&(get->key), get->block_type, get->options,
3241 get->desired_replication_level,current_destination,
3242 current_source, next_hop, 0,
3243 get_length, gp);
3244 }
3245 return GNUNET_SYSERR;
3246} 2080}
3247 2081
3248 2082
@@ -3258,157 +2092,11 @@ static int
3258handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer, 2092handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer,
3259 const struct GNUNET_MessageHeader *message) 2093 const struct GNUNET_MessageHeader *message)
3260{ 2094{
3261 struct PeerGetResultMessage *get_result; 2095 return GNUNET_OK;
3262 struct GNUNET_PeerIdentity *get_path;
3263 struct GNUNET_PeerIdentity *put_path;
3264 void *payload;
3265 size_t payload_size;
3266 size_t msize;
3267 unsigned int getlen;
3268 unsigned int putlen;
3269 int current_path_index;
3270
3271 msize = ntohs (message->size);
3272 if (msize < sizeof (struct PeerGetResultMessage))
3273 {
3274 GNUNET_break_op (0);
3275 return GNUNET_YES;
3276 }
3277
3278 get_result = (struct PeerGetResultMessage *)message;
3279 getlen = ntohl (get_result->get_path_length);
3280 putlen = ntohl (get_result->put_path_length);
3281
3282 if ((msize <
3283 sizeof (struct PeerGetResultMessage) +
3284 getlen * sizeof (struct GNUNET_PeerIdentity) +
3285 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
3286 (getlen >
3287 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity) ||
3288 (putlen >
3289 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))))
3290 {
3291 GNUNET_break_op (0);
3292 return GNUNET_YES;
3293 }
3294
3295 if (getlen > 0)
3296 get_path = (struct GNUNET_PeerIdentity *) &get_result[1];
3297 payload = &get_path[getlen];
3298 payload_size = msize - (sizeof (struct PeerGetResultMessage) +
3299 getlen * sizeof (struct GNUNET_PeerIdentity));
3300
3301 if (putlen > 0)
3302 put_path = &get_path[1];
3303 else
3304 put_path = NULL;
3305
3306 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_path[0]))))
3307 {
3308 GDS_CLIENTS_handle_reply (get_result->expiration_time, &(get_result->key),
3309 getlen, get_path, putlen,
3310 put_path, get_result->type, payload_size, payload);
3311 return GNUNET_YES;
3312 }
3313 else
3314 {
3315 current_path_index = search_my_index (get_path, getlen);
3316 if (GNUNET_SYSERR == current_path_index )
3317 {
3318 GNUNET_break (0);
3319 return GNUNET_SYSERR;
3320 }
3321 GDS_NEIGHBOURS_send_get_result (&(get_result->key), get_result->type,
3322 &get_path[current_path_index - 1],
3323 &(get_result->source_peer), putlen, put_path,
3324 getlen, get_path, get_result->expiration_time,
3325 payload, payload_size);
3326 return GNUNET_YES;
3327 }
3328 return GNUNET_SYSERR;
3329}
3330
3331
3332/**
3333 * Select the closest peer between peer returned from routing table and from
3334 * find_successor()
3335 * @param prev_hop Peer which sent the trail setup message.
3336 * @param current_destination[out] Next peer which will receive this message.
3337 * @param current_source[out] Source of the @a current_destination.
3338 * @param value Key value to which the peer should be closest.
3339 * @para finger_map_index Index in finger map.
3340 * @return Peer which is closest, in case of error NULL.
3341 */
3342struct GNUNET_PeerIdentity *
3343select_closest_peer (const struct GNUNET_PeerIdentity *prev_hop,
3344 struct GNUNET_PeerIdentity *current_destination,
3345 struct GNUNET_PeerIdentity *current_source,
3346 uint64_t value,
3347 unsigned int finger_map_index)
3348{
3349 struct GNUNET_PeerIdentity *peer1;
3350 struct GNUNET_PeerIdentity *peer2;
3351 struct Sorting_List peers[3];
3352 struct Sorting_List *closest_finger;
3353 struct GNUNET_PeerIdentity current_dest;
3354 struct GNUNET_PeerIdentity current_src;
3355
3356 peer1 = GDS_ROUTING_search (current_source, current_destination, prev_hop);
3357 peer2 = find_successor (value, &current_dest, &current_src,finger_map_index);
3358
3359 if( (peer1 != NULL) && (peer2 != NULL))
3360 {
3361 memcpy (&peers[0], &peer1, sizeof (uint64_t));
3362 peers[0].type = FRIEND;
3363 peers[0].data = NULL;
3364
3365 memcpy (&peers[1], &value, sizeof (uint64_t));
3366 peers[1].type = VALUE;
3367 peers[1].data = NULL;
3368
3369 memcpy (&peers[2], &peer2, sizeof (uint64_t));
3370 peers[2].type = FINGER;
3371 peers[1].data = NULL;
3372
3373 qsort (&peers, 3, sizeof (struct Sorting_List), &compare_peer_id);
3374 if (PREDECESSOR_FINGER_ID == finger_map_index)
3375 closest_finger = find_closest_predecessor (peers, value, 3);
3376 else
3377 closest_finger = find_closest_successor (peers, value, 3);
3378
3379 if (closest_finger->type == FINGER)
3380 {
3381 memcpy (current_destination, &current_dest, sizeof (struct GNUNET_PeerIdentity));
3382 memcpy (current_source, &current_src, sizeof (struct GNUNET_PeerIdentity));
3383 return peer2;
3384 }
3385 else if (closest_finger->type == VALUE)
3386 {
3387 return NULL;
3388 }
3389 else if (closest_finger->type == FRIEND);
3390 {
3391 return peer1;
3392 }
3393 }
3394 else if ((peer1 == NULL) && (peer2 == NULL))
3395 {
3396 return NULL;
3397 }
3398 else if (peer1 == NULL)
3399 {
3400 return peer2;
3401 }
3402 else if (peer2 == NULL)
3403 {
3404 return peer1;
3405 }
3406 return NULL;
3407} 2096}
3408 2097
3409 2098
3410/** 2099/* Core handle for PeerTrailSetupMessage.
3411 * Core handle for PeerTrailSetupMessage.
3412 * @param cls closure 2100 * @param cls closure
3413 * @param message message 2101 * @param message message
3414 * @param peer peer identity this notification is about 2102 * @param peer peer identity this notification is about
@@ -3418,30 +2106,32 @@ static int
3418handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer, 2106handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3419 const struct GNUNET_MessageHeader *message) 2107 const struct GNUNET_MessageHeader *message)
3420{ 2108{
3421 const struct PeerTrailSetupMessage *trail_setup; 2109 struct PeerTrailSetupMessage *trail_setup;
3422 struct GNUNET_PeerIdentity current_destination; 2110 struct GNUNET_PeerIdentity *trail_peer_list;
3423 struct GNUNET_PeerIdentity current_source; 2111 struct GNUNET_PeerIdentity next_destination;
3424 struct GNUNET_PeerIdentity source; 2112 struct GNUNET_PeerIdentity *current_destination;
3425 struct GNUNET_PeerIdentity *next_hop; 2113 struct GNUNET_PeerIdentity *next_hop;
3426 struct GNUNET_PeerIdentity next_peer; 2114 struct GNUNET_PeerIdentity next_peer;
3427 struct GNUNET_PeerIdentity *trail_peer_list;
3428 struct FriendInfo *target_friend; 2115 struct FriendInfo *target_friend;
3429 uint64_t destination_finger_value; 2116 struct GNUNET_PeerIdentity source;
2117 uint64_t ultimate_destination_finger_value;
2118 struct GNUNET_HashCode new_intermediate_trail_id;
2119 struct GNUNET_HashCode intermediate_trail_id;
2120 struct GNUNET_HashCode new_trail_id;
2121 unsigned int finger_map_index;
3430 uint32_t trail_length; 2122 uint32_t trail_length;
3431 uint32_t finger_map_index;
3432 size_t msize; 2123 size_t msize;
3433 2124
3434 msize = ntohs (message->size); 2125 msize = ntohs (message->size);
3435 if (msize < sizeof (struct PeerTrailSetupMessage)) 2126 if (msize != sizeof (struct PeerTrailSetupMessage))
3436 { 2127 {
3437 GNUNET_break_op (0); 2128 GNUNET_break_op (0);
3438 return GNUNET_YES; 2129 return GNUNET_YES;
3439 } 2130 }
3440 2131
3441 trail_setup = (const struct PeerTrailSetupMessage *) message; 2132 trail_setup = (struct PeerTrailSetupMessage *) message;
3442 trail_length = ntohl (trail_setup->trail_length); 2133 trail_length = ntohl (trail_setup->trail_length);
3443 2134 if ((msize != sizeof (struct PeerTrailSetupMessage) +
3444 if ((msize < sizeof (struct PeerTrailSetupMessage) +
3445 trail_length * sizeof (struct GNUNET_PeerIdentity)) || 2135 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3446 (trail_length > 2136 (trail_length >
3447 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))) 2137 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
@@ -3450,78 +2140,78 @@ handle_dht_p2p_trail_setup (void *cls, const struct GNUNET_PeerIdentity *peer,
3450 return GNUNET_OK; 2140 return GNUNET_OK;
3451 } 2141 }
3452 2142
3453 if (trail_length > 0) 2143 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1];
3454 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1]; 2144 current_destination = &trail_setup->next_destination;
3455 memcpy (&current_destination, &(trail_setup->current_destination), sizeof (struct GNUNET_PeerIdentity)); 2145 intermediate_trail_id = trail_setup->intermediate_trail_id;
3456 memcpy (&current_source,&(trail_setup->current_source), sizeof (struct GNUNET_PeerIdentity)); 2146 new_trail_id = trail_setup->new_trail_id;
3457 memcpy (&source, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity)); 2147 ultimate_destination_finger_value = GNUNET_ntohll (trail_setup->ultimate_destination_finger);
2148 source = trail_setup->source_peer;
3458 finger_map_index = ntohl (trail_setup->finger_map_index); 2149 finger_map_index = ntohl (trail_setup->finger_map_index);
3459 destination_finger_value = ntohl (trail_setup->destination_finger);
3460 2150
3461 /* Check your routing table size, and if you can handle any more trails through you. */ 2151 if (GNUNET_YES == GDS_ROUTING_threshold_reached())
3462 if (GNUNET_YES == GDS_ROUTING_check_threshold())
3463 { 2152 {
3464 GDS_NEIGHBOURS_send_trail_rejection (&source, destination_finger_value, &my_identity, 2153 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
3465 peer, finger_map_index, trail_peer_list, trail_length, 2154 GDS_NEIGHBOURS_send_trail_rejection (source, ultimate_destination_finger_value,
2155 my_identity, finger_map_index,
2156 trail_peer_list, trail_length,
2157 new_trail_id, target_friend,
3466 CONGESTION_TIMEOUT); 2158 CONGESTION_TIMEOUT);
3467 return GNUNET_OK; 2159 return GNUNET_OK;
3468 } 2160 }
3469 2161
3470 /* Check if you are current_destination or not. */ 2162 next_hop = find_successor (ultimate_destination_finger_value, &next_destination,
3471 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&current_destination, &my_identity))) 2163 &new_intermediate_trail_id, finger_map_index);
3472 {
3473 next_hop = select_closest_peer (peer, &current_destination, &current_source,
3474 destination_finger_value, finger_map_index);
3475 }
3476 else
3477 {
3478 next_hop = find_successor (destination_finger_value, &current_destination,
3479 &current_source,finger_map_index);
3480 }
3481 2164
3482 if (NULL == next_hop) 2165 if (0 != (GNUNET_CRYPTO_cmp_peer_identity(&my_identity, current_destination)))
3483 { 2166 {
3484 GNUNET_STATISTICS_update (GDS_stats, 2167 struct GNUNET_PeerIdentity *closest_peer;
3485 gettext_noop ("# Next hop to forward the packet not found " 2168 struct GNUNET_PeerIdentity *peer1 =
3486 "trail setup request, packet dropped."), 2169 GDS_ROUTING_get_next_hop (intermediate_trail_id, GDS_ROUTING_SRC_TO_DEST);
3487 1, GNUNET_NO); 2170 if (0 != GNUNET_CRYPTO_cmp_peer_identity (peer1, next_hop))
3488 return GNUNET_SYSERR; 2171 {
2172 closest_peer = select_closest_peer (peer1, next_hop,
2173 ultimate_destination_finger_value,
2174 finger_map_index);
2175 }
2176 if (0 == GNUNET_CRYPTO_cmp_peer_identity (peer1, closest_peer) ||
2177 (0 == GNUNET_CRYPTO_cmp_peer_identity (peer1, next_hop)))
2178 {
2179 next_hop = peer1;
2180 next_destination = *current_destination;
2181 new_intermediate_trail_id = intermediate_trail_id;
2182 }
3489 } 2183 }
3490 else if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */ 2184
2185 GNUNET_assert (NULL != next_hop);
2186 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
3491 { 2187 {
3492 if (trail_length == 0) 2188 if (0 == trail_length)
3493 {
3494 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity)); 2189 memcpy (&next_peer, &source, sizeof (struct GNUNET_PeerIdentity));
3495 }
3496 else 2190 else
3497 {
3498 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity)); 2191 memcpy (&next_peer, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3499 }
3500 2192
3501 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer); 2193 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
3502 GDS_NEIGHBOURS_send_trail_setup_result (&source, 2194 GDS_NEIGHBOURS_send_trail_setup_result (source,
3503 &(my_identity), 2195 my_identity,
3504 target_friend, trail_length, 2196 target_friend, trail_length,
3505 trail_peer_list, 2197 trail_peer_list,
3506 finger_map_index); 2198 finger_map_index, new_trail_id);
3507 return GNUNET_OK;
3508 } 2199 }
3509 else 2200 else
3510 { 2201 {
3511 /* Now add yourself to the trail. */
3512 struct GNUNET_PeerIdentity peer_list[trail_length + 1]; 2202 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
3513 if (trail_length != 0) 2203
3514 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity)); 2204 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
3515 peer_list[trail_length] = my_identity; 2205 peer_list[trail_length] = my_identity;
3516 trail_length++;
3517 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop); 2206 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
3518 GDS_NEIGHBOURS_send_trail_setup (&source, 2207 GDS_NEIGHBOURS_send_trail_setup (source,
3519 destination_finger_value, 2208 ultimate_destination_finger_value,
3520 &current_destination, &current_source, 2209 next_destination,
3521 target_friend, trail_length, peer_list, 2210 target_friend, trail_length + 1, peer_list,
3522 finger_map_index); 2211 finger_map_index, new_trail_id,
3523 return GNUNET_OK; 2212 new_intermediate_trail_id);
3524 } 2213 }
2214 return GNUNET_OK;
3525} 2215}
3526 2216
3527 2217
@@ -3536,25 +2226,26 @@ static int
3536handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer, 2226handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3537 const struct GNUNET_MessageHeader *message) 2227 const struct GNUNET_MessageHeader *message)
3538{ 2228{
3539 const struct PeerTrailSetupResultMessage *trail_result; 2229 struct PeerTrailSetupResultMessage *trail_result;
3540 struct GNUNET_PeerIdentity *trail_peer_list; 2230 struct GNUNET_PeerIdentity *trail_peer_list;
3541 struct GNUNET_PeerIdentity destination_peer; 2231 struct GNUNET_PeerIdentity destination_peer;
3542 struct GNUNET_PeerIdentity finger_identity; 2232 struct GNUNET_PeerIdentity finger_identity;
3543 uint32_t trail_length; 2233 uint32_t trail_length;
3544 uint32_t finger_map_index; 2234 uint32_t finger_map_index;
2235 struct GNUNET_HashCode trail_id;
3545 size_t msize; 2236 size_t msize;
3546 2237
3547 msize = ntohs (message->size); 2238 msize = ntohs (message->size);
3548 if (msize < sizeof (struct PeerTrailSetupResultMessage)) 2239 if (msize != sizeof (struct PeerTrailSetupResultMessage))
3549 { 2240 {
3550 GNUNET_break_op (0); 2241 GNUNET_break_op (0);
3551 return GNUNET_YES; 2242 return GNUNET_YES;
3552 } 2243 }
3553 2244
3554 trail_result = (const struct PeerTrailSetupResultMessage *) message; 2245 trail_result = (struct PeerTrailSetupResultMessage *) message;
3555 trail_length = ntohl (trail_result->trail_length); 2246 trail_length = ntohl (trail_result->trail_length);
3556 2247
3557 if ((msize < 2248 if ((msize !=
3558 sizeof (struct PeerTrailSetupResultMessage) + 2249 sizeof (struct PeerTrailSetupResultMessage) +
3559 trail_length * sizeof (struct GNUNET_PeerIdentity)) || 2250 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3560 (trail_length > 2251 (trail_length >
@@ -3565,95 +2256,47 @@ handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *p
3565 } 2256 }
3566 2257
3567 finger_map_index = htonl (trail_result->finger_map_index); 2258 finger_map_index = htonl (trail_result->finger_map_index);
3568 memcpy (&destination_peer, &(trail_result->destination_peer), sizeof (struct GNUNET_PeerIdentity)); 2259 destination_peer = trail_result->destination_peer;
3569 memcpy (&finger_identity, &(trail_result->finger_identity), sizeof (struct GNUNET_PeerIdentity)); 2260 finger_identity = trail_result->finger_identity;
3570 2261 trail_id = trail_result->trail_id;
3571 if (trail_length > 0) 2262 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
3572 trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
3573
3574 2263
3575 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer), 2264 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&destination_peer,
3576 &my_identity))) 2265 &my_identity)))
3577 { 2266 {
3578 finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length, 2267 finger_table_add (finger_identity, trail_peer_list,
3579 finger_map_index); 2268 trail_length,
2269 finger_map_index, trail_id);
3580 return GNUNET_YES; 2270 return GNUNET_YES;
3581 } 2271 }
3582 else
3583 {
3584 struct GNUNET_PeerIdentity next_hop;
3585 struct FriendInfo *target_friend;
3586 int my_index;
3587
3588 my_index = search_my_index (trail_peer_list, trail_length);
3589 if (my_index == GNUNET_SYSERR)
3590 return GNUNET_SYSERR;
3591
3592 if (my_index == 0)
3593 next_hop = trail_result->destination_peer;
3594 else
3595 next_hop = trail_peer_list[my_index - 1];
3596 2272
3597 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer), 2273 struct GNUNET_PeerIdentity next_hop;
3598 &(trail_result->finger_identity)))) 2274 struct FriendInfo *target_friend;
3599 { 2275 int my_index;
3600 struct GNUNET_PeerIdentity *routing_next_hop;
3601
3602 routing_next_hop = GDS_ROUTING_search (&destination_peer,&finger_identity,
3603 peer);
3604 if ((NULL == routing_next_hop) ||
3605 (0 != GNUNET_CRYPTO_cmp_peer_identity(routing_next_hop, &next_hop)))
3606 {
3607 GDS_ROUTING_add (&(trail_result->destination_peer), &(trail_result->finger_identity),
3608 peer, &next_hop);
3609 }
3610 }
3611
3612 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3613 GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
3614 &(trail_result->finger_identity),
3615 target_friend, trail_length,
3616 trail_peer_list,
3617 finger_map_index);
3618 return GNUNET_YES;
3619 }
3620 return GNUNET_SYSERR;
3621}
3622
3623 2276
3624/** 2277 my_index = search_my_index(trail_peer_list, trail_length);
3625 * Get my current predecessor from the finger peer map 2278 if (my_index == GNUNET_SYSERR)
3626 * @return Current predecessor.
3627 */
3628static struct FingerInfo *
3629get_predecessor()
3630{
3631 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
3632 struct GNUNET_PeerIdentity key_ret;
3633 unsigned int finger_index;
3634 struct FingerInfo *my_predecessor;
3635 int flag = 0;
3636
3637 /* Iterate over finger peer map and extract your predecessor. */
3638 finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
3639 for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
3640 { 2279 {
3641 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next 2280 GNUNET_break_op(0);
3642 (finger_iter,&key_ret,(const void **)&my_predecessor)) 2281 return GNUNET_SYSERR;
3643 {
3644 if(PREDECESSOR_FINGER_ID == my_predecessor->finger_map_index)
3645 {
3646 flag = 1;
3647 break;
3648 }
3649 }
3650 } 2282 }
3651 GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
3652 2283
3653 if (0 == flag) 2284 if (my_index == 0)
3654 return NULL; 2285 next_hop = trail_result->destination_peer;
3655 else 2286 else
3656 return my_predecessor; 2287 next_hop = trail_peer_list[my_index - 1];
2288
2289 if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2290 &(trail_result->finger_identity))))
2291 {
2292 GDS_ROUTING_add (trail_id, &next_hop, peer);
2293 }
2294
2295 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
2296 GDS_NEIGHBOURS_send_trail_setup_result (destination_peer, finger_identity,
2297 target_friend, trail_length, trail_peer_list,
2298 finger_map_index, trail_id);
2299 return GNUNET_OK;
3657} 2300}
3658 2301
3659 2302
@@ -3668,127 +2311,70 @@ static int
3668handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer, 2311handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
3669 const struct GNUNET_MessageHeader *message) 2312 const struct GNUNET_MessageHeader *message)
3670{ 2313{
3671 const struct PeerVerifySuccessorMessage *vsm; 2314 struct PeerVerifySuccessorMessage *vsm;
3672 const struct GNUNET_PeerIdentity *trail_peer_list; 2315 struct GNUNET_PeerIdentity successor;
3673 struct GNUNET_PeerIdentity source_peer; 2316 struct GNUNET_PeerIdentity source_peer;
3674 struct GNUNET_PeerIdentity next_hop; 2317 struct GNUNET_PeerIdentity *next_hop;
3675 struct FriendInfo *target_friend; 2318 struct FriendInfo *target_friend;
2319 //struct FingerInfo *my_predecessor;
2320 //struct GNUNET_PeerIdentity *my_predecessor_trail;
2321 //unsigned int my_predecessor_trail_length;
2322 struct GNUNET_HashCode trail_id;
3676 size_t msize; 2323 size_t msize;
3677 uint32_t trail_length; 2324
3678
3679 msize = ntohs (message->size); 2325 msize = ntohs (message->size);
3680 if (msize < sizeof (struct PeerVerifySuccessorMessage)) 2326 if (msize != sizeof (struct PeerVerifySuccessorMessage))
3681 { 2327 {
3682 GNUNET_break_op (0); 2328 GNUNET_break_op (0);
3683 return GNUNET_YES; 2329 return GNUNET_YES;
3684 } 2330 }
3685 2331
3686 vsm = (struct PeerVerifySuccessorMessage *) message; 2332 vsm = (struct PeerVerifySuccessorMessage *) message;
3687 trail_length = ntohl (vsm->trail_length); 2333 source_peer = vsm->source_peer;
2334 successor = vsm->successor;
2335 trail_id = vsm->trail_id;
3688 2336
3689 if ((msize < sizeof (struct PeerVerifySuccessorMessage) + 2337 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&successor, &my_identity)))
3690 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
3691 (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3692 { 2338 {
3693 GNUNET_break_op (0); 2339 GNUNET_assert (NULL != (next_hop =
3694 return GNUNET_YES; 2340 GDS_ROUTING_get_next_hop (trail_id,
2341 GDS_ROUTING_SRC_TO_DEST)));
2342 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2343 GDS_NEIGHBOURS_send_verify_successor_message (source_peer, successor,
2344 trail_id, target_friend);
2345 return GNUNET_OK;
3695 } 2346 }
3696 if (trail_length > 0) 2347#if 0
3697 trail_peer_list = (const struct GNUNET_PeerIdentity *)&vsm[1]; 2348 my_predecessor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap,
3698 memcpy (&source_peer, &(vsm->source_peer), sizeof(struct GNUNET_PeerIdentity)); 2349 PREDECESSOR_FINGER_ID);
2350 if (NULL == my_predecessor) /* FIXME: not sure how to handle this case */
2351 return GNUNET_OK;
3699 2352
3700 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity))) 2353 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
2354 &(my_predecessor->finger_identity))))
3701 { 2355 {
3702 struct FingerInfo *my_predecessor; 2356 my_predecessor_trail = NULL;
3703 2357 my_predecessor_trail_length = 0;
3704 my_predecessor = get_predecessor();
3705 if (NULL == my_predecessor)
3706 {
3707 /* FIXME: should we just return. */
3708 return GNUNET_OK;
3709 }
3710
3711 if (trail_length == 0)
3712 {
3713 memcpy (&next_hop, &source_peer, sizeof (struct GNUNET_PeerIdentity));
3714 }
3715 else
3716 {
3717 memcpy (&next_hop, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
3718 }
3719 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3720
3721 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&source_peer,
3722 &(my_predecessor->finger_identity))))
3723 {
3724 /* Source peer and my predecessor, both are same. */
3725
3726 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3727 &(my_identity),
3728 &(my_predecessor->finger_identity),
3729 target_friend,
3730 trail_peer_list,
3731 trail_length);
3732 }
3733 else
3734 {
3735 struct GNUNET_PeerIdentity *new_successor_trail;
3736 struct TrailPeerList *iterator;
3737 int new_trail_length;
3738 int i;
3739
3740 new_trail_length = trail_length + my_predecessor->first_trail_length + 1;
3741 new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * new_trail_length);
3742 if (trail_length > 0)
3743 memcpy (new_successor_trail, trail_peer_list, (trail_length) * sizeof (struct GNUNET_PeerIdentity));
3744
3745 memcpy (&new_successor_trail[trail_length], &my_identity, sizeof (struct GNUNET_PeerIdentity));
3746
3747 if (my_predecessor->first_trail_length)
3748 {
3749 iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
3750 iterator = my_predecessor->first_trail_head;
3751 i = trail_length + 1;
3752 while (i < new_trail_length)
3753 {
3754 memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
3755 iterator = iterator->next;
3756 i++;
3757 }
3758 }
3759 GDS_NEIGHBOURS_send_verify_successor_result (&source_peer,
3760 &(my_identity),
3761 &(my_predecessor->finger_identity),
3762 target_friend,
3763 new_successor_trail,
3764 new_trail_length);
3765 }
3766
3767 } 2358 }
3768 else 2359 else
3769 { 2360 {
3770 int my_index; 2361 /* FIXME: copy from my_predecessor trail. now we may have multiple routes
3771 2362 choose the one with shortest length and send that one. */
3772 my_index = search_my_index (trail_peer_list, trail_length);
3773 if (my_index == GNUNET_SYSERR)
3774 {
3775 GNUNET_break (0);
3776 return GNUNET_SYSERR;
3777 }
3778 if (my_index == (trail_length - 1))
3779 {
3780 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(vsm->successor));
3781 }
3782 else
3783 {
3784 memcpy (&next_hop, &trail_peer_list[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
3785 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3786 }
3787
3788 GDS_NEIGHBOURS_send_verify_successor (&(vsm->source_peer), &(vsm->successor),target_friend,
3789 trail_peer_list, trail_length);
3790 } 2363 }
3791 return GNUNET_SYSERR; 2364
2365 /* Here you are sending the result back along the trail through which the source
2366 peer send the message to you. now you have to specify the direction such
2367 that the trail id is used but now prev_hop is next_hop. */
2368
2369 GDS_NEIGHBOURS_send_verify_successor_result (source_peer, my_identity,
2370 my_predecessor->finger_identity,
2371 trail_id,
2372 my_predecessor_trail,
2373 my_predecessor_trail_length,
2374 GDS_ROUTING_DEST_TO_SRC,
2375 target_friend);
2376#endif
2377 return GNUNET_OK;
3792} 2378}
3793 2379
3794 2380
@@ -3803,207 +2389,208 @@ static int
3803handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer, 2389handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3804 const struct GNUNET_MessageHeader *message) 2390 const struct GNUNET_MessageHeader *message)
3805{ 2391{
3806 const struct PeerVerifySuccessorResultMessage *vsrm; 2392 struct PeerVerifySuccessorResultMessage *vsrm;
3807 struct GNUNET_PeerIdentity *trail_peer_list; 2393 enum GDS_ROUTING_trail_direction trail_direction;
3808 struct GNUNET_PeerIdentity next_hop; 2394 struct GNUNET_HashCode trail_id;
2395 unsigned int successor_current_predecessor_trail_length;
2396 struct GNUNET_PeerIdentity *successor_current_predecessor_trail;
2397 struct GNUNET_PeerIdentity destination_peer;
2398 struct GNUNET_PeerIdentity my_new_successor;
2399 struct GNUNET_PeerIdentity *next_hop;
3809 struct FriendInfo *target_friend; 2400 struct FriendInfo *target_friend;
3810 size_t msize; 2401 size_t msize;
3811 uint32_t trail_length;
3812 2402
3813 msize = ntohs (message->size); 2403 msize = ntohs (message->size);
3814 if (msize < sizeof (struct PeerVerifySuccessorResultMessage)) 2404 if (msize != sizeof (struct PeerVerifySuccessorResultMessage))
3815 { 2405 {
3816 GNUNET_break_op (0); 2406 GNUNET_break_op (0);
3817 return GNUNET_YES; 2407 return GNUNET_YES;
3818 } 2408 }
3819 vsrm = (const struct PeerVerifySuccessorResultMessage *) message; 2409 vsrm = (struct PeerVerifySuccessorResultMessage *) message;
3820 trail_length = ntohl (vsrm->trail_length); 2410 successor_current_predecessor_trail_length = ntohl (vsrm->trail_length);
2411 trail_direction = ntohl (vsrm->trail_direction);
2412 trail_id = vsrm->trail_id;
3821 2413
3822 if ((msize < 2414 if ((msize !=
3823 sizeof (struct PeerVerifySuccessorResultMessage) + 2415 sizeof (struct PeerVerifySuccessorResultMessage) +
3824 trail_length * sizeof (struct GNUNET_PeerIdentity)) || 2416 successor_current_predecessor_trail_length *
3825 (trail_length > 2417 sizeof (struct GNUNET_PeerIdentity)) ||
2418 (successor_current_predecessor_trail_length >
3826 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))) 2419 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3827 { 2420 {
3828 GNUNET_break_op (0); 2421 GNUNET_break_op (0);
3829 return GNUNET_YES; 2422 return GNUNET_YES;
3830 } 2423 }
3831 2424
3832 if (trail_length > 0) 2425 successor_current_predecessor_trail = (struct GNUNET_PeerIdentity *) &vsrm[1];
3833 trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1]; 2426 destination_peer = vsrm->destination_peer;
2427 my_new_successor = vsrm->my_predecessor;
3834 2428
3835 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), &(my_identity)))) 2429 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&destination_peer, &my_identity)))
3836 {
3837 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), &(my_identity))))
3838 {
3839 if (GNUNET_YES == finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0))
3840 {
3841 memcpy (&next_hop, &trail_peer_list[0], sizeof (struct GNUNET_PeerIdentity));
3842 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3843 scan_and_compress_trail (trail_peer_list, &trail_length, &(vsrm->my_predecessor));
3844 GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
3845 &(vsrm->source_successor),
3846 target_friend, trail_peer_list,
3847 trail_length);
3848 }
3849 return GNUNET_OK;
3850 }
3851 }
3852 else
3853 { 2430 {
3854 int my_index;
3855 2431
3856 my_index = search_my_index (trail_peer_list, trail_length);
3857 if (GNUNET_SYSERR == my_index)
3858 {
3859 GNUNET_break (0);
3860 return GNUNET_SYSERR;
3861 }
3862 if (my_index == 0)
3863 {
3864 memcpy (&next_hop, &(vsrm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
3865 }
3866 else
3867 {
3868 memcpy (&next_hop, &trail_peer_list[my_index-1], sizeof (struct GNUNET_PeerIdentity));
3869 }
3870
3871 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
3872 GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
3873 &(vsrm->source_successor),
3874 &(vsrm->my_predecessor),
3875 target_friend,
3876 trail_peer_list,
3877 trail_length);
3878 return GNUNET_OK;
3879 } 2432 }
3880 return GNUNET_SYSERR; 2433
2434 next_hop = GDS_ROUTING_get_next_hop (trail_id, trail_direction);
2435 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2436 GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
2437 vsrm->source_successor,
2438 my_new_successor, trail_id,
2439 successor_current_predecessor_trail,
2440 successor_current_predecessor_trail_length,
2441 trail_direction, target_friend);
2442 return GNUNET_OK;
3881} 2443}
3882 2444
3883 2445
2446#if 0
3884/** 2447/**
3885 * Core handle for p2p notify new successor messages. 2448 * Adapt it to use trail list array.
2449 * Core handle for p2p verify successor result messages.
3886 * @param cls closure 2450 * @param cls closure
3887 * @param message message 2451 * @param message message
3888 * @param peer peer identity this notification is about 2452 * @param peer peer identity this notification is about
3889 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error 2453 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3890 */ 2454 */
3891static int 2455static int
3892handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer, 2456handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
3893 const struct GNUNET_MessageHeader *message) 2457 const struct GNUNET_MessageHeader *message)
3894{ 2458{
3895 const struct PeerNotifyNewSuccessorMessage *nsm; 2459
3896 struct GNUNET_PeerIdentity *trail_peer_list; 2460 const struct PeerVerifySuccessorResultMessage *vsrm;
3897 struct GNUNET_PeerIdentity source_peer; 2461 unsigned int trail_length;
3898 struct GNUNET_PeerIdentity old_successor; 2462 struct GNUNET_HashCode trail_id;
3899 struct GNUNET_PeerIdentity new_successor; 2463 struct GNUNET_PeerIdentity *trail;
3900 struct FriendInfo *target_friend; 2464 struct FriendInfo *target_friend;
2465 struct GNUNET_PeerIdentity *next_hop;
2466 struct GNUNET_PeerIdentity destination_peer;
2467 struct GNUNET_PeerIdentity my_new_successor;
2468 struct FingerInfo *current_successor;
2469 struct GNUNET_HashCode old_successor_trail_id;
3901 size_t msize; 2470 size_t msize;
3902 uint32_t trail_length;
3903 2471
3904 msize = ntohs (message->size); 2472 msize = ntohs (message->size);
3905 if (msize < sizeof (struct PeerNotifyNewSuccessorMessage)) 2473 if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
3906 { 2474 {
3907 GNUNET_break_op (0); 2475 GNUNET_break_op (0);
3908 return GNUNET_YES; 2476 return GNUNET_YES;
3909 } 2477 }
3910 nsm = (const struct PeerNotifyNewSuccessorMessage *) message; 2478 vsrm = (const struct PeerVerifySuccessorResultMessage *) message;
3911 trail_length = ntohl (nsm->trail_length); 2479 trail_length = ntohl (vsrm->trail_length);
2480 trail_id = vsrm->trail_id;
3912 2481
3913 if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) + 2482 if ((msize <
3914 trail_length * sizeof (struct GNUNET_PeerIdentity)) || 2483 sizeof (struct PeerVerifySuccessorResultMessage) +
3915 (trail_length > 2484 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2485 (trail_length >
3916 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))) 2486 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
3917 { 2487 {
3918 GNUNET_break_op (0); 2488 GNUNET_break_op (0);
3919 return GNUNET_YES; 2489 return GNUNET_YES;
3920 } 2490 }
3921 2491
3922 if( trail_length > 0) 2492 trail = (struct GNUNET_PeerIdentity *) &vsrm[1];
3923 trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1]; 2493 destination_peer = vsrm->destination_peer;
3924 memcpy (&source_peer, &(nsm->source_peer), sizeof (struct GNUNET_PeerIdentity)); 2494 my_new_successor = vsrm->my_predecessor;
3925 memcpy (&old_successor, &(nsm->old_successor), sizeof (struct GNUNET_PeerIdentity));
3926 memcpy (&new_successor, &(nsm->destination_peer), sizeof (struct GNUNET_PeerIdentity));
3927 2495
3928 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&new_successor, &my_identity))) 2496 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&destination_peer, &my_identity)))
3929 { 2497 {
3930 /* I am the new successor. */ 2498 unsigned int *new_trail_length;
3931 struct GNUNET_PeerIdentity *new_predecessor; 2499 struct GNUNET_PeerIdentity *new_trail;
3932 2500 struct GNUNET_HashCode new_finger_trail_id;
3933 new_predecessor = GNUNET_new (struct GNUNET_PeerIdentity);
3934 memcpy (new_predecessor, &(nsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
3935 if (GNUNET_YES == finger_table_add (new_predecessor, trail_peer_list, trail_length, PREDECESSOR_FINGER_ID))
3936 {
3937 if (trail_length > 0)
3938 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(trail_peer_list[trail_length - 1]));
3939 else
3940 target_friend = NULL;
3941 GDS_NEIGHBOURS_send_add_trail_message (&my_identity, new_predecessor,
3942 trail_peer_list, trail_length, target_friend);
3943 }
3944 return GNUNET_OK;
3945 }
3946 else
3947 {
3948 struct GNUNET_PeerIdentity next_hop;
3949 int my_index;
3950 2501
3951 my_index = search_my_index (trail_peer_list, trail_length); 2502 /* FIXME: generate a new_finger_trail_id */
3952 if (GNUNET_SYSERR == my_index) 2503 current_successor = GNUNET_CONTAINER_multihashmap32_get (finger_hashmap, 0);
3953 { 2504 old_successor_trail_id = current_successor->head->trail_id;
3954 GNUNET_break(0); 2505 target_friend =
3955 return GNUNET_SYSERR; 2506 GNUNET_CONTAINER_multipeermap_get (friend_peermap,
3956 } 2507 &(current_successor->head->head->peer));
3957 2508
3958 if (my_index == (trail_length - 1)) 2509 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&my_new_successor,
3959 { 2510 &current_successor->finger_identity))
3960 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &(nsm->destination_peer));
3961 }
3962 else
3963 { 2511 {
3964 memcpy (&next_hop, &trail_peer_list[my_index+1], sizeof (struct GNUNET_PeerIdentity)); 2512 *new_trail_length = 0;
3965 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop); 2513 new_trail = update_trail_to_new_predecessor (current_successor,
2514 trail_length, trail,
2515 new_trail_length);
2516
2517 if (GNUNET_OK == finger_table_add (&my_new_successor, new_trail,
2518 new_trail_length , 0, new_finger_trail_id))
2519 {
2520 /*FIXME:
2521 *Here you should send a trail teardown message for old trail id
2522 and trail add for new trail. */
2523 }
2524 GDS_NEIGHBOURS_send_notify_new_successor (my_identity, my_new_successor,
2525 new_trail, new_trail_length,
2526 new_finger_trail_id, target_friend);
3966 } 2527 }
3967 GDS_ROUTING_remove_trail (&source_peer, &old_successor, peer);
3968 GDS_ROUTING_add (&(nsm->source_peer), &(nsm->destination_peer), &next_hop, peer);
3969 GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
3970 &(nsm->destination_peer),
3971 &(nsm->old_successor),
3972 target_friend, trail_peer_list,
3973 trail_length);
3974 return GNUNET_OK;
3975 } 2528 }
3976 return GNUNET_SYSERR; 2529
2530 next_hop = GDS_ROUTING_get_next_hop (trail_id);
2531 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2532 GDS_NEIGHBOURS_send_verify_successor_result (vsrm->destination_peer,
2533 vsrm->source_successor,
2534 vsrm->my_predecessor,
2535 vsrm->trail_id, trail,
2536
2537 return GNUNET_OK;
2538}
2539 trail_length, target_friend);
2540#endif
2541
2542
2543/**
2544 * Core handle for p2p notify new successor messages.
2545 * @param cls closure
2546 * @param message message
2547 * @param peer peer identity this notification is about
2548 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2549 */
2550static int
2551handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2552 const struct GNUNET_MessageHeader *message)
2553{
2554 /* Here we need to pass the whole trail to reach to new successor as we
2555 don't have that stored in our routing table. while passing through each
2556 peer we will have to add an entry. also when you are the destination and
2557 if you have added it back as pred, then you also need to add the trail in
2558 your own finger table and send add trail message to add this trail. you
2559 shoudl generate a new trail id. although they are same trails but you have
2560 to ahve different trail id. */
2561 return GNUNET_OK;
3977} 2562}
3978 2563
3979 2564
3980/** 2565/**
2566 * FIXME: Here you should keep the trail id with you.
3981 * Core handler for P2P trail rejection message 2567 * Core handler for P2P trail rejection message
3982 * @param cls closure 2568 * @param cls closure
3983 * @param message message 2569 * @param message message
3984 * @param peer peer identity this notification is about 2570 * @param peer peer identity this notification is about
3985 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error 2571 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
3986 */ 2572 */
3987static 2573static int
3988int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer, 2574handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *peer,
3989 const struct GNUNET_MessageHeader *message) 2575 const struct GNUNET_MessageHeader *message)
3990{ 2576{
3991 const struct PeerTrailRejectionMessage *trail_rejection; 2577 struct PeerTrailRejectionMessage *trail_rejection;
2578 unsigned int trail_length;
3992 struct GNUNET_PeerIdentity *trail_peer_list; 2579 struct GNUNET_PeerIdentity *trail_peer_list;
3993 struct FriendInfo *target_friend; 2580 struct FriendInfo *target_friend;
3994 struct GNUNET_PeerIdentity next_hop;
3995 struct GNUNET_PeerIdentity *next_peer;
3996 struct GNUNET_PeerIdentity source;
3997 struct GNUNET_PeerIdentity current_destination;
3998 struct GNUNET_PeerIdentity current_source;
3999 uint32_t trail_length;
4000 uint32_t finger_map_index;
4001 uint64_t destination_finger_value;
4002 struct GNUNET_TIME_Relative congestion_timeout; 2581 struct GNUNET_TIME_Relative congestion_timeout;
2582 struct GNUNET_HashCode trail_id;
2583 struct GNUNET_PeerIdentity next_destination;
2584 struct GNUNET_HashCode new_intermediate_trail_id;
2585 struct GNUNET_PeerIdentity next_peer;
2586 struct GNUNET_PeerIdentity source;
2587 struct GNUNET_PeerIdentity *next_hop;
2588 uint64_t ultimate_destination_finger_value;
2589 unsigned int finger_map_index;
4003 size_t msize; 2590 size_t msize;
4004 2591
4005 msize = ntohs (message->size); 2592 msize = ntohs (message->size);
4006 if (msize < sizeof (struct PeerTrailRejectionMessage)) 2593 if (msize != sizeof (struct PeerTrailRejectionMessage))
4007 { 2594 {
4008 GNUNET_break_op (0); 2595 GNUNET_break_op (0);
4009 return GNUNET_YES; 2596 return GNUNET_YES;
@@ -4012,7 +2599,7 @@ int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *
4012 trail_rejection = (struct PeerTrailRejectionMessage *) message; 2599 trail_rejection = (struct PeerTrailRejectionMessage *) message;
4013 trail_length = ntohl (trail_rejection->trail_length); 2600 trail_length = ntohl (trail_rejection->trail_length);
4014 2601
4015 if ((msize < sizeof (struct PeerTrailRejectionMessage) + 2602 if ((msize != sizeof (struct PeerTrailRejectionMessage) +
4016 trail_length * sizeof (struct GNUNET_PeerIdentity)) || 2603 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
4017 (trail_length > 2604 (trail_length >
4018 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))) 2605 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
@@ -4021,24 +2608,26 @@ int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *
4021 return GNUNET_YES; 2608 return GNUNET_YES;
4022 } 2609 }
4023 2610
4024 if (trail_length > 0) 2611 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
4025 trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_rejection[1];
4026 finger_map_index = ntohl (trail_rejection->finger_map_index); 2612 finger_map_index = ntohl (trail_rejection->finger_map_index);
4027 memcpy (&destination_finger_value, &(trail_rejection->finger_identity_value), sizeof (uint64_t));
4028 memcpy (&source, &(trail_rejection->source_peer), sizeof (struct GNUNET_PeerIdentity));
4029 congestion_timeout = trail_rejection->congestion_time; 2613 congestion_timeout = trail_rejection->congestion_time;
2614 source = trail_rejection->source_peer;
2615 trail_id = trail_rejection->trail_id;
2616 ultimate_destination_finger_value =
2617 trail_rejection->ultimate_destination_finger_identity_value;
4030 2618
4031 /* First set the congestion time of the friend that sent you this message. */ 2619 /* First set the congestion time of the friend that sent you this message. */
4032 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer); 2620 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4033 target_friend->congestion_duration = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(), 2621 target_friend->congestion_duration = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(),
4034 congestion_timeout); 2622 congestion_timeout);
4035 2623
4036 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(trail_rejection->source_peer)))) 2624 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &source)))
4037 { 2625 {
4038 return GNUNET_OK; 2626 return GNUNET_OK;
4039 } 2627 }
4040 2628
4041 if(GNUNET_YES == GDS_ROUTING_check_threshold()) 2629 /* If I am congested then pass this message to peer before me in trail. */
2630 if(GNUNET_YES == GDS_ROUTING_threshold_reached())
4042 { 2631 {
4043 struct GNUNET_PeerIdentity *new_trail; 2632 struct GNUNET_PeerIdentity *new_trail;
4044 unsigned int new_trail_length; 2633 unsigned int new_trail_length;
@@ -4047,65 +2636,62 @@ int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *
4047 { 2636 {
4048 new_trail = NULL; 2637 new_trail = NULL;
4049 new_trail_length = 0; 2638 new_trail_length = 0;
4050 memcpy (&next_hop, &(trail_rejection->source_peer), sizeof (struct GNUNET_PeerIdentity)); 2639 next_hop = &source;
4051 } 2640 }
4052 else 2641 else
4053 { 2642 {
4054 memcpy (&next_hop, &trail_peer_list[trail_length - 2], sizeof (struct GNUNET_PeerIdentity)); 2643 next_hop = &trail_peer_list[trail_length - 2];
4055 /* Remove myself from the trail. */ 2644 /* Remove myself from the trail. */
4056 new_trail_length = trail_length -1; 2645 new_trail_length = trail_length -1;
4057 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity)); 2646 new_trail = GNUNET_malloc (new_trail_length * sizeof (struct GNUNET_PeerIdentity));
4058 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity)); 2647 memcpy (new_trail, trail_peer_list, new_trail_length * sizeof (struct GNUNET_PeerIdentity));
4059 } 2648 }
4060 GDS_NEIGHBOURS_send_trail_rejection (&(trail_rejection->source_peer), 2649
4061 destination_finger_value, 2650 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4062 &my_identity, &next_hop,finger_map_index, 2651 GDS_NEIGHBOURS_send_trail_rejection (source,
4063 new_trail,new_trail_length, CONGESTION_TIMEOUT); 2652 ultimate_destination_finger_value,
2653 my_identity, finger_map_index,
2654 new_trail,new_trail_length,trail_id,
2655 target_friend, CONGESTION_TIMEOUT);
4064 return GNUNET_YES; 2656 return GNUNET_YES;
4065 } 2657 }
4066 2658
2659 /* Look for next_hop to pass the trail setup message */
2660 next_hop = find_successor (ultimate_destination_finger_value,
2661 &next_destination,
2662 &new_intermediate_trail_id,
2663 finger_map_index);
2664
2665 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_hop, &my_identity)))/* This means I am the final destination */
4067 { 2666 {
4068 memcpy (&current_destination, &my_identity, sizeof (struct GNUNET_PeerIdentity)); 2667 if (0 == trail_length)
4069 memcpy (&current_source, &my_identity, sizeof (struct GNUNET_PeerIdentity)); 2668 next_peer = source;
4070 next_peer = find_successor (destination_finger_value,&current_destination, 2669 else
4071 &current_source, finger_map_index); 2670 next_peer = trail_peer_list[trail_length-1];
4072 if (NULL == next_peer) 2671
4073 { 2672 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_peer);
4074 GNUNET_STATISTICS_update (GDS_stats, 2673 GDS_NEIGHBOURS_send_trail_setup_result (source,
4075 gettext_noop ("# Next hop not found" 2674 my_identity,
4076 "trail setup request, packet dropped."),
4077 1, GNUNET_NO);
4078 return GNUNET_SYSERR;
4079 }
4080 else if (0 == (GNUNET_CRYPTO_cmp_peer_identity (next_peer, &my_identity)))/* This means I am the final destination */
4081 {
4082 memcpy (&next_hop, &trail_peer_list[trail_length-1], sizeof (struct GNUNET_PeerIdentity));
4083 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4084 GDS_NEIGHBOURS_send_trail_setup_result (&source,
4085 &(my_identity),
4086 target_friend, trail_length, 2675 target_friend, trail_length,
4087 trail_peer_list, 2676 trail_peer_list,
4088 finger_map_index); 2677 finger_map_index, trail_id);
4089 return GNUNET_OK;
4090 } 2678 }
4091 else 2679 else
4092 { 2680 {
4093 /* Now add yourself to the trail. */
4094 struct GNUNET_PeerIdentity peer_list[trail_length + 1]; 2681 struct GNUNET_PeerIdentity peer_list[trail_length + 1];
4095 if (trail_length != 0) 2682
4096 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity)); 2683 memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
4097 peer_list[trail_length] = my_identity; 2684 peer_list[trail_length] = my_identity;
4098 trail_length++; 2685
4099 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop); 2686 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
4100 GDS_NEIGHBOURS_send_trail_setup (&source, 2687 GDS_NEIGHBOURS_send_trail_setup (source,
4101 destination_finger_value, 2688 ultimate_destination_finger_value,
4102 &current_destination, &current_source, 2689 next_destination,
4103 target_friend, trail_length, peer_list, 2690 target_friend, trail_length + 1, peer_list,
4104 finger_map_index); 2691 finger_map_index, trail_id,
4105 return GNUNET_OK; 2692 new_intermediate_trail_id);
4106 }
4107 } 2693 }
4108 2694 return GNUNET_OK;
4109} 2695}
4110 2696
4111 2697
@@ -4116,83 +2702,72 @@ int handle_dht_p2p_trail_rejection(void *cls, const struct GNUNET_PeerIdentity *
4116 * @param peer peer identity this notification is about 2702 * @param peer peer identity this notification is about
4117 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error 2703 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
4118 */ 2704 */
4119static 2705static int
4120int handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer, 2706handle_dht_p2p_trail_compression (void *cls, const struct GNUNET_PeerIdentity *peer,
4121 const struct GNUNET_MessageHeader *message) 2707 const struct GNUNET_MessageHeader *message)
4122{ 2708{
4123 struct PeerTrailTearDownMessage *trail_teardown; 2709 struct PeerTrailCompressionMessage *trail_compression;
4124 struct GNUNET_PeerIdentity *discarded_trail; 2710 struct GNUNET_PeerIdentity *next_hop;
4125 struct GNUNET_PeerIdentity next_hop; 2711 struct GNUNET_HashCode trail_id;
4126 struct FriendInfo *target_friend; 2712 struct FriendInfo *target_friend;
4127 uint32_t discarded_trail_length;
4128 size_t msize; 2713 size_t msize;
4129 int my_index;
4130 2714
4131 msize = ntohs (message->size); 2715 msize = ntohs (message->size);
4132 if (msize < sizeof (struct PeerTrailTearDownMessage)) 2716 if (msize != sizeof (struct PeerTrailCompressionMessage))
4133 { 2717 {
4134 GNUNET_break_op (0); 2718 GNUNET_break_op (0);
4135 return GNUNET_OK; 2719 return GNUNET_OK;
4136 } 2720 }
4137 2721
4138 trail_teardown = (struct PeerTrailTearDownMessage *) message; 2722 trail_compression = (struct PeerTrailCompressionMessage *) message;
4139 discarded_trail_length = ntohl (trail_teardown->trail_length); 2723 trail_id = trail_compression->trail_id;
4140 2724
4141 if ((msize < sizeof (struct PeerTrailTearDownMessage) + 2725 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_compression->new_first_friend),
4142 discarded_trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
4143 (discarded_trail_length >
4144 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
4145 {
4146 GNUNET_break_op (0);
4147 return GNUNET_OK;
4148 }
4149
4150 if (discarded_trail_length > 0)
4151 discarded_trail = (struct GNUNET_PeerIdentity *) &trail_teardown[1];
4152
4153 if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->new_first_friend),
4154 &my_identity))) 2726 &my_identity)))
4155 { 2727 {
4156 if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_teardown->destination_peer), 2728 if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_compression->destination_peer),
4157 &my_identity))) 2729 &my_identity)))
4158 { 2730 {
4159 return GNUNET_OK; 2731 GDS_ROUTING_update_trail_prev_hop (trail_id,
4160 } 2732 trail_compression->source_peer);
4161 else
4162 {
4163 return GDS_ROUTING_trail_update (&(trail_teardown->source_peer),
4164 &(trail_teardown->destination_peer), peer);
4165 } 2733 }
2734 return GNUNET_OK;
4166 } 2735 }
4167 else 2736
2737 next_hop = GDS_ROUTING_get_next_hop (trail_id, GDS_ROUTING_SRC_TO_DEST);
2738 if (NULL == next_hop)
4168 { 2739 {
4169 my_index = search_my_index (discarded_trail, discarded_trail_length); 2740 GNUNET_break (0); /*FIXME: How to handle this case. */
4170 if(GNUNET_SYSERR == my_index) 2741 return GNUNET_OK;
4171 return GNUNET_SYSERR;
4172
4173 if (GNUNET_NO == GDS_ROUTING_remove_trail (&(trail_teardown->source_peer),
4174 &(trail_teardown->destination_peer),peer))
4175 {
4176 GNUNET_break (0); /* no matching entry found. Should not happen */
4177 return GNUNET_SYSERR;
4178 }
4179
4180 if (my_index == (discarded_trail_length - 1))
4181 return GNUNET_OK;
4182
4183 memcpy (&next_hop, &discarded_trail[my_index + 1], sizeof (struct GNUNET_PeerIdentity));
4184 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4185 GDS_NEIGHBOURS_send_trail_teardown (&(trail_teardown->source_peer),
4186 &(trail_teardown->destination_peer),
4187 discarded_trail, discarded_trail_length,
4188 target_friend, &(trail_teardown->new_first_friend));
4189 return GNUNET_YES;
4190 } 2742 }
4191 return GNUNET_SYSERR; 2743 GNUNET_assert (GNUNET_YES == GDS_ROUTING_remove_trail (trail_id));
2744 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2745 GDS_NEIGHBOURS_send_trail_compression (trail_compression->source_peer,
2746 trail_compression->destination_peer,
2747 trail_id,
2748 trail_compression->new_first_friend,
2749 target_friend);
2750 return GNUNET_OK;
2751}
2752
2753
2754/**
2755 * Core handler for trail teardown message.
2756 * @param cls closure
2757 * @param message message
2758 * @param peer peer identity this notification is about
2759 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2760 */
2761static int
2762handle_dht_p2p_trail_teardown (void *cls, const struct GNUNET_PeerIdentity *peer,
2763 const struct GNUNET_MessageHeader *message)
2764{
2765 return GNUNET_OK;
4192} 2766}
4193 2767
4194 2768
4195/** 2769/**
2770 * TRAIL ID and each peer should add an entry in the routing table.
4196 * Core handle for p2p add trail message. 2771 * Core handle for p2p add trail message.
4197 * @param cls closure 2772 * @param cls closure
4198 * @param message message 2773 * @param message message
@@ -4203,68 +2778,19 @@ static int
4203handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer, 2778handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
4204 const struct GNUNET_MessageHeader *message) 2779 const struct GNUNET_MessageHeader *message)
4205{ 2780{
4206 struct PeerAddTrailMessage *add_trail; 2781 return GNUNET_OK;
4207 struct GNUNET_PeerIdentity *trail;
4208 struct GNUNET_PeerIdentity next_hop;
4209 struct FriendInfo *target_friend;
4210 size_t msize;
4211 uint32_t trail_length;
4212 int my_index;
4213
4214 msize = ntohs (message->size);
4215 if (msize < sizeof (struct PeerAddTrailMessage))
4216 {
4217 GNUNET_break_op (0);
4218 return GNUNET_OK;
4219 }
4220
4221 add_trail = (struct PeerAddTrailMessage *) message;
4222 trail_length = ntohl (add_trail->trail_length);
4223
4224 if ((msize < sizeof (struct PeerAddTrailMessage) +
4225 trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
4226 (trail_length >
4227 GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
4228 {
4229 GNUNET_break_op (0);
4230 return GNUNET_OK;
4231 }
4232
4233 if (trail_length > 0)
4234 trail = (struct GNUNET_PeerIdentity *)&add_trail[1];
4235
4236 my_index = search_my_index (trail, trail_length);
4237 if (GNUNET_SYSERR == my_index)
4238 {
4239 GNUNET_break (0);
4240 return GNUNET_SYSERR;
4241 }
4242
4243 if (GNUNET_YES == GDS_ROUTING_add (&(add_trail->source_peer), &(add_trail->destination_peer),
4244 peer,&next_hop))
4245 {
4246 if (my_index != 0)
4247 {
4248 memcpy (&next_hop, &trail[my_index - 1], sizeof (struct GNUNET_PeerIdentity));
4249 target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, &next_hop);
4250 GDS_NEIGHBOURS_send_add_trail_message (&(add_trail->source_peer),
4251 &(add_trail->destination_peer),
4252 trail, trail_length,target_friend);
4253 }
4254 return GNUNET_OK;
4255 }
4256 else
4257 {
4258 /* No space left in my routing table. How should we handle this case? */
4259 return GNUNET_SYSERR;
4260 }
4261} 2782}
4262 2783
4263 2784
4264/** 2785/**
4265 * FIXME: Adapt the code for List of trails. 2786 *FIXME; call send_trail_teardown_message on all the trails of the finger that
4266 * Iterate over finger_peermap, and remove entries with peer as the first element 2787 * you remove. Also you don't need to decerement friend trail count as that
4267 * of their trail. 2788 * friend is removed. But you can not send trail teardown message as the friend
2789 * is disconnected. then you don't have any next_hop. and in case there are
2790 * multiple trails. and friend is the first trail then you remove only the trail.
2791 * Iterate over finger_hashmap, and remove entries if finger is the disconnected
2792 * peer or if disconnected peer is the first friend in the trail to reach the
2793 * finger.
4268 * @param cls closure 2794 * @param cls closure
4269 * @param key current public key 2795 * @param key current public key
4270 * @param value value in the hash map 2796 * @param value value in the hash map
@@ -4274,31 +2800,37 @@ handle_dht_p2p_add_trail (void *cls, const struct GNUNET_PeerIdentity *peer,
4274 */ 2800 */
4275static int 2801static int
4276remove_matching_finger (void *cls, 2802remove_matching_finger (void *cls,
4277 const struct GNUNET_PeerIdentity *key, 2803 uint32_t key,
4278 void *value) 2804 void *value)
4279{ 2805{
4280 struct FingerInfo *remove_finger = value; 2806 struct FingerInfo *remove_finger = value;
4281 const struct GNUNET_PeerIdentity *disconnected_peer = cls; 2807 const struct GNUNET_PeerIdentity *disconnected_peer = cls;
2808 struct TrailList *trail_list;
2809 int i;
4282 2810
4283 if (remove_finger->first_trail_length > 0) 2811 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->finger_identity,
4284 { 2812 disconnected_peer))
4285 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_finger->first_trail_head->peer, disconnected_peer))
4286 {
4287 GNUNET_assert (GNUNET_YES ==
4288 GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
4289 key,
4290 remove_finger));
4291 free_finger (remove_finger);
4292 }
4293 }
4294 else if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_finger->finger_identity),
4295 disconnected_peer))
4296 { 2813 {
4297 GNUNET_assert (GNUNET_YES == 2814 GNUNET_assert (GNUNET_YES ==
4298 GNUNET_CONTAINER_multipeermap_remove (finger_peermap, 2815 GNUNET_CONTAINER_multihashmap32_remove (finger_hashmap,
4299 key, 2816 key,
4300 remove_finger)); 2817 remove_finger));
4301 free_finger (remove_finger); 2818 free_finger (remove_finger);
2819 return GNUNET_YES;
2820 }
2821
2822 for (i = 0; i< remove_finger->trails_count; i++)
2823 {
2824 trail_list = &remove_finger->trail_list[i];
2825 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&trail_list->trail_head->peer,
2826 disconnected_peer))
2827 {
2828 GNUNET_assert (GNUNET_YES ==
2829 GNUNET_CONTAINER_multihashmap32_remove (finger_hashmap,
2830 key,
2831 remove_finger));
2832 free_finger (remove_finger);
2833 }
4302 } 2834 }
4303 2835
4304 return GNUNET_YES; 2836 return GNUNET_YES;
@@ -4317,11 +2849,9 @@ handle_core_disconnect (void *cls,
4317{ 2849{
4318 struct FriendInfo *remove_friend; 2850 struct FriendInfo *remove_friend;
4319 2851
4320 /* Check for self message. */
4321 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity))) 2852 if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
4322 return; 2853 return;
4323 2854
4324 /* Search for peer to remove in your friend_peermap. */
4325 remove_friend = 2855 remove_friend =
4326 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer); 2856 GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
4327 2857
@@ -4330,14 +2860,12 @@ handle_core_disconnect (void *cls,
4330 GNUNET_break (0); 2860 GNUNET_break (0);
4331 return; 2861 return;
4332 } 2862 }
4333
4334 /* Remove fingers for which this peer is the first element in the trail or if
4335 * the friend is a finger. */
4336 GNUNET_CONTAINER_multipeermap_iterate (finger_peermap,
4337 &remove_matching_finger, (void *)peer);
4338 GDS_ROUTING_remove_entry (peer);
4339 2863
4340 /* Remove the peer from friend_peermap. */ 2864 GNUNET_assert (GNUNET_SYSERR !=
2865 GNUNET_CONTAINER_multihashmap32_iterate (finger_hashmap,
2866 &remove_matching_finger,
2867 (void *)peer));
2868 GDS_ROUTING_remove_trail_by_peer (peer);
4341 GNUNET_assert (GNUNET_YES == 2869 GNUNET_assert (GNUNET_YES ==
4342 GNUNET_CONTAINER_multipeermap_remove (friend_peermap, 2870 GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
4343 peer, 2871 peer,
@@ -4385,7 +2913,6 @@ handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
4385 2913
4386 friend = GNUNET_new (struct FriendInfo); 2914 friend = GNUNET_new (struct FriendInfo);
4387 friend->id = *peer_identity; 2915 friend->id = *peer_identity;
4388 friend->trails_count = 0;
4389 2916
4390 GNUNET_assert (GNUNET_OK == 2917 GNUNET_assert (GNUNET_OK ==
4391 GNUNET_CONTAINER_multipeermap_put (friend_peermap, 2918 GNUNET_CONTAINER_multipeermap_put (friend_peermap,
@@ -4429,6 +2956,7 @@ GDS_NEIGHBOURS_init (void)
4429 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0}, 2956 {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
4430 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0}, 2957 {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
4431 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0}, 2958 {&handle_dht_p2p_trail_rejection, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_REJECTION, 0},
2959 {&handle_dht_p2p_trail_compression, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION, 0},
4432 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0}, 2960 {&handle_dht_p2p_trail_teardown, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_TEARDOWN, 0},
4433 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL, 0}, 2961 {&handle_dht_p2p_add_trail, GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL, 0},
4434 {NULL, 0, 0} 2962 {NULL, 0, 0}
@@ -4442,12 +2970,11 @@ GDS_NEIGHBOURS_init (void)
4442 return GNUNET_SYSERR; 2970 return GNUNET_SYSERR;
4443 2971
4444 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO); 2972 friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
4445 finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS * 4/3, GNUNET_NO); 2973 finger_hashmap = GNUNET_CONTAINER_multihashmap32_create (MAX_FINGERS * 4/3);
4446 2974
4447 return GNUNET_OK; 2975 return GNUNET_OK;
4448} 2976}
4449 2977
4450
4451/** 2978/**
4452 * Shutdown neighbours subsystem. 2979 * Shutdown neighbours subsystem.
4453 */ 2980 */
@@ -4464,9 +2991,9 @@ GDS_NEIGHBOURS_done (void)
4464 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap); 2991 GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
4465 friend_peermap = NULL; 2992 friend_peermap = NULL;
4466 2993
4467 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap)); 2994 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap32_size (finger_hashmap));
4468 GNUNET_CONTAINER_multipeermap_destroy (finger_peermap); 2995 GNUNET_CONTAINER_multihashmap32_destroy (finger_hashmap);
4469 finger_peermap = NULL; 2996 finger_hashmap = NULL;
4470 2997
4471 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task) 2998 if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
4472 { 2999 {
@@ -4486,7 +3013,4 @@ struct GNUNET_PeerIdentity
4486GDS_NEIGHBOURS_get_my_id (void) 3013GDS_NEIGHBOURS_get_my_id (void)
4487{ 3014{
4488 return my_identity; 3015 return my_identity;
4489} 3016} \ No newline at end of file
4490
4491
4492/* end of gnunet-service-xdht_neighbours.c */ \ No newline at end of file
diff --git a/src/dht/gnunet-service-xdht_routing.c b/src/dht/gnunet-service-xdht_routing.c
index 32faa25fe..ad7c9a276 100644
--- a/src/dht/gnunet-service-xdht_routing.c
+++ b/src/dht/gnunet-service-xdht_routing.c
@@ -28,31 +28,25 @@
28#include "gnunet-service-xdht_routing.h" 28#include "gnunet-service-xdht_routing.h"
29#include "gnunet-service-xdht.h" 29#include "gnunet-service-xdht.h"
30 30
31/* TODO
32 1. to understand if we really need all the four fields.
33 2. if we can merge remove_peer and remove_trail
34 3. do we need next_hop to uniquely identify a trail in remove_trail. */
35
36/** 31/**
37 * Maximum number of entries in routing table. 32 * Maximum number of entries in routing table.
38 */ 33 */
39#define ROUTING_TABLE_THRESHOLD 64 34#define ROUTING_TABLE_THRESHOLD 64
40 35
36
41/** 37/**
38 * FIXME: do we need to store destination and source.
39 * because in trail teardown we will reach destination but it will not find any
40 * entry in routing table. so we should store destination and source.
42 * Routing table entry . 41 * Routing table entry .
43 */ 42 */
44struct RoutingTrail 43struct RoutingTrail
45{ 44{
46 /** 45 /**
47 * Source peer . 46 * Global Unique identifier of the trail.
48 */
49 struct GNUNET_PeerIdentity source;
50
51 /**
52 * Destination peer.
53 */ 47 */
54 struct GNUNET_PeerIdentity destination; 48 struct GNUNET_HashCode trail_id;
55 49
56 /** 50 /**
57 * The peer to which this request should be passed to. 51 * The peer to which this request should be passed to.
58 */ 52 */
@@ -62,264 +56,172 @@ struct RoutingTrail
62 * Peer just before next hop in the trail. 56 * Peer just before next hop in the trail.
63 */ 57 */
64 struct GNUNET_PeerIdentity prev_hop; 58 struct GNUNET_PeerIdentity prev_hop;
65
66}; 59};
67 60
68
69/** 61/**
70 * Routing table of the peer 62 * Routing table of the peer
71 */ 63 */
72static struct GNUNET_CONTAINER_MultiPeerMap *routing_table; 64static struct GNUNET_CONTAINER_MultiHashMap *routing_table;
73
74 65
75/** 66/**
76 * Get next hop from the trail with source peer, destination peer and next hop 67 * Update the prev. hop of the trail. Call made by trail teardown where
77 * same as the argument to this function. 68 * if you are the first friend now in the trail then you need to update
78 * @param source_peer Source peer of the trail. 69 * your prev. hop.
79 * @param destination_peer Destination peer of the trail. 70 * @param trail_id
80 * @param prev_hop Previous hop of the trail. 71 * @return #GNUNET_OK success
81 * @return #GNUNET_YES if we found the matching trail. 72 * #GNUNET_SYSERR in case no matching entry found in routing table.
82 * #GNUNET_NO if we found no matching trail.
83 */
84static int
85get_next_hop (struct RoutingTrail *trail,
86 struct GNUNET_PeerIdentity *source_peer,
87 struct GNUNET_PeerIdentity *destination_peer,
88 const struct GNUNET_PeerIdentity *prev_hop)
89{
90 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->source),source_peer))
91 {
92 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->prev_hop),prev_hop))
93 {
94 return GNUNET_YES;
95 }
96 else
97 return GNUNET_NO;
98 }
99 return GNUNET_NO;
100}
101
102
103/**
104 * FIXME: How to ensure that with only 3 fields also we have a unique trail.
105 * in case of redundant routes we can have different next hop.
106 * in that case we have to call this function on each entry of routing table
107 * and from multiple next hop we return one. Here also we are going to return one.
108 * URGENT.
109 * Assumption - there can be only on one trail with all these fields. But if
110 * we consider only 3 fields then it is possible that next hop is differet.
111 * Update prev_hop field to source_peer. Trail from source peer to destination
112 * peer is compressed such that I am the first friend in the trail.
113 * @param source_peer Source of the trail.
114 * @param destination_peer Destination of the trail.
115 * @param prev_hop Peer before me in the trail.
116 * @return #GNUNET_YES trail is updated.
117 * #GNUNET_NO, trail not found.
118 */ 73 */
119int 74int
120GDS_ROUTING_trail_update (struct GNUNET_PeerIdentity *source_peer, 75GDS_ROUTING_update_trail_prev_hop (const struct GNUNET_HashCode trail_id,
121 struct GNUNET_PeerIdentity *destination_peer, 76 struct GNUNET_PeerIdentity prev_hop)
122 const struct GNUNET_PeerIdentity *prev_hop)
123{ 77{
124 /* 1. find the trail corresponding to these values.
125 2. update the prev hop to source peer. */
126 struct RoutingTrail *trail; 78 struct RoutingTrail *trail;
127 struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator;
128 int i;
129 79
130 iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table); 80 trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
131 for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++) 81
132 { 82 if (NULL == trail)
133 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL, 83 return GNUNET_SYSERR;
134 (const void **)&trail)) 84
135 { 85 trail->prev_hop = prev_hop;
136 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer)) 86 return GNUNET_OK;
137 {
138 if (GNUNET_YES == get_next_hop (trail, source_peer, destination_peer, prev_hop))
139 {
140 memcpy (&(trail->prev_hop), source_peer, sizeof (struct GNUNET_PeerIdentity));
141 return GNUNET_YES;
142 }
143 }
144 }
145 }
146 return GNUNET_NO;
147} 87}
148 88
149 89
150/** 90/**
151 * It can happen that a particular peer removed the entry because one of the peers 91 * Get the next hop for trail corresponding to trail_id
152 * (source, destination, next , prev) was friend which got disconnected. So, 92 * @param trail_id Trail id to be searched.
153 * no matching trail is found. In this case we return NULL. Its on calling function 93 * @return Next_hop if found
154 * to handle the return value. 94 * NULL If next hop not found.
155 * Find the next hop to send packet to.
156 * @param source_peer Source of the trail.
157 * @param destination_peer Destination of the trail.
158 * @param prev_hop Previous hop in the trail.
159 * @return Next hop in the trail from source to destination.
160 * NULL in case no matching trail found in routing table.
161 */ 95 */
162struct GNUNET_PeerIdentity * 96struct GNUNET_PeerIdentity *
163GDS_ROUTING_search (struct GNUNET_PeerIdentity *source_peer, 97GDS_ROUTING_get_next_hop (const struct GNUNET_HashCode trail_id,
164 struct GNUNET_PeerIdentity *destination_peer, 98 enum GDS_ROUTING_trail_direction trail_direction)
165 const struct GNUNET_PeerIdentity *prev_hop)
166{ 99{
167 struct RoutingTrail *trail; 100 struct RoutingTrail *trail;
168 struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator; 101
169 int i; 102 trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
103
104 if (NULL == trail)
105 return NULL;
170 106
171 iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table); 107 switch (trail_direction)
172 for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++)
173 { 108 {
174 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL, 109 case GDS_ROUTING_SRC_TO_DEST:
175 (const void **)&trail)) 110 return &(trail->next_hop);
176 { 111 case GDS_ROUTING_DEST_TO_SRC:
177 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer)) 112 return &(trail->prev_hop);
178 {
179 if (GNUNET_YES == get_next_hop (trail, source_peer, destination_peer, prev_hop))
180 {
181 return &(trail->next_hop);
182 }
183 }
184 }
185 } 113 }
186 GNUNET_CONTAINER_multipeermap_iterator_destroy (iterator);
187 return NULL; 114 return NULL;
188} 115}
189 116
190 117
191/** 118/**
192 * FIXME: first search in routing table and if same entry found then don't add 119 * Remove trail with trail_id
193 * it. 120 * @param trail_id Trail id to be removed
194 * Add a new entry to our routing table. 121 * @return #GNUNET_YES success
195 * @param source peer Source of the trail. 122 * #GNUNET_NO if entry not found.
196 * @param destintation Destination of the trail.
197 * @param next_hop Next peer to forward the message to reach the destination.
198 * @return GNUNET_YES
199 * GNUNET_SYSERR If the number of routing entries crossed thershold.
200 */ 123 */
201int 124int
202GDS_ROUTING_add (const struct GNUNET_PeerIdentity *source, 125GDS_ROUTING_remove_trail (const struct GNUNET_HashCode remove_trail_id)
203 const struct GNUNET_PeerIdentity *dest,
204 const struct GNUNET_PeerIdentity *next_hop,
205 const struct GNUNET_PeerIdentity *prev_hop)
206{ 126{
207 struct RoutingTrail *new_routing_entry; 127 struct RoutingTrail *remove_entry;
208
209 if (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD)
210 return GNUNET_SYSERR;
211
212 new_routing_entry = GNUNET_malloc (sizeof (struct RoutingTrail));
213 memcpy (&(new_routing_entry->source) , source, sizeof (struct GNUNET_PeerIdentity));
214 memcpy (&(new_routing_entry->next_hop), next_hop, sizeof (struct GNUNET_PeerIdentity));
215 memcpy (&(new_routing_entry->destination), dest, sizeof (struct GNUNET_PeerIdentity));
216 memcpy (&(new_routing_entry->prev_hop), prev_hop, sizeof (struct GNUNET_PeerIdentity));
217 128
218 GNUNET_assert (GNUNET_OK == 129 remove_entry = GNUNET_CONTAINER_multihashmap_get (routing_table, &remove_trail_id);
219 GNUNET_CONTAINER_multipeermap_put (routing_table, 130
220 dest, new_routing_entry, 131 if (NULL == remove_entry)
221 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE)); 132 return GNUNET_NO;
222 133
223 return GNUNET_YES; 134 if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove (routing_table,
135 &remove_trail_id,
136 remove_entry))
137 {
138 GNUNET_free (remove_entry);
139 return GNUNET_YES;
140 }
141 return GNUNET_NO;
224} 142}
225 143
226 144
227/** 145/**
228 * Iterate over routing table and remove entries for which peer is a part. 146 * Iterate over routing table and remove entries with value as part of any trail.
229 * @param cls closure 147 * @param cls closure
230 * @param key current public key 148 * @param key current public key
231 * @param value value in the hash map 149 * @param value value in the hash map
232 * @return #GNUNET_YES if we should continue to 150 * @return #GNUNET_YES if we should continue to iterate,
233 * iterate,
234 * #GNUNET_NO if not. 151 * #GNUNET_NO if not.
235 */ 152 */
236static int 153static int remove_matching_trails (void *cls,
237remove_routing_entry (void *cls, 154 const struct GNUNET_HashCode *key,
238 const struct GNUNET_PeerIdentity *key, 155 void *value)
239 void *value)
240{ 156{
241 struct RoutingTrail *remove_entry = value; 157 struct RoutingTrail *remove_trail = cls;
242 const struct GNUNET_PeerIdentity *disconnected_peer = cls; 158 struct GNUNET_PeerIdentity *peer = value;
243 159
244 if ((0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->source), disconnected_peer)) || 160 if ((0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->next_hop, peer)) ||
245 (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->destination), disconnected_peer)) || 161 (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->prev_hop, peer)))
246 (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->next_hop), disconnected_peer)) ||
247 (0 == GNUNET_CRYPTO_cmp_peer_identity (&(remove_entry->prev_hop), disconnected_peer)))
248 { 162 {
249 GNUNET_assert (GNUNET_YES == 163 GNUNET_assert (GNUNET_YES ==
250 GNUNET_CONTAINER_multipeermap_remove (routing_table, 164 GNUNET_CONTAINER_multihashmap_remove (routing_table,
251 key, 165 &remove_trail->trail_id,
252 remove_entry)); 166 remove_trail));
253 } 167 GNUNET_free (remove_trail);
254 return GNUNET_YES; 168 }
169 return GNUNET_YES;
255} 170}
256 171
257 172
258/** 173/**
259 * FIXME: add a return value. 174 * * FIXME: when a friend gets disconnected, then we remove the entry from routing
260 * Iterate over routing table and remove all entries for which peer is a part. 175 * table where this friend is either a next_hop or prev_hop. But we don't communicate
261 * @param peer Peer to be searched for in the trail to remove that trail. 176 * that the trail is broken to any one who is part of trail. Should we communicate or
177 * not. And if not then the cases where trail setup fails because next_hop = NULL
178 * or something like that. VERY URGENT.
179 * Remove every trail where peer is either next_hop or prev_hop
180 * @param peer Peer to be searched.
262 */ 181 */
263void 182void
264GDS_ROUTING_remove_entry (const struct GNUNET_PeerIdentity *peer) 183GDS_ROUTING_remove_trail_by_peer (const struct GNUNET_PeerIdentity *peer)
265{ 184{
266 GNUNET_CONTAINER_multipeermap_iterate (routing_table, &remove_routing_entry, 185 GNUNET_CONTAINER_multihashmap_iterate (routing_table, &remove_matching_trails,
267 (void *)peer); 186 (void *)peer);
268} 187}
269 188
270 189
271/** 190/**
272 * In response to trail teardown message, remove the trail with source peer, 191 * Add a new entry in routing table
273 * destination peer and next hop same as the argument to this function. 192 * @param new_trail_id
274 * Assumption - there can be only one possible trail with these 4 values. 193 * @param prev_hop
275 * @param source_peer Source of the trail. 194 * @param next_hop
276 * @param destination_peer Destination of the trail. 195 * @return #GNUNET_OK success
277 * @param next_hop Next hop 196 * #GNUNET_SYSERR in case new_trail_id already exists in the network
278 * @param prev_hop Previous hop. 197 * but with different prev_hop/next_hop
279 * @return #GNUNET_YES Matching trail deleted from routing table.
280 * #GNUNET_NO No matching trail found.
281 *
282 */ 198 */
283int 199int
284GDS_ROUTING_remove_trail (struct GNUNET_PeerIdentity *source_peer, 200GDS_ROUTING_add (struct GNUNET_HashCode new_trail_id,
285 struct GNUNET_PeerIdentity *destination_peer, 201 struct GNUNET_PeerIdentity *prev_hop,
286 const struct GNUNET_PeerIdentity *prev_hop) 202 const struct GNUNET_PeerIdentity *next_hop)
287{ 203{
288 struct RoutingTrail *trail; 204 struct RoutingTrail *new_entry;
289 struct GNUNET_CONTAINER_MultiPeerMapIterator *iterator;
290 int i;
291 205
292 iterator = GNUNET_CONTAINER_multipeermap_iterator_create (routing_table); 206 new_entry = GNUNET_malloc (sizeof (struct RoutingTrail));
293 for (i = 0; i< GNUNET_CONTAINER_multipeermap_size(routing_table); i++) 207 new_entry->trail_id = new_trail_id;
294 { 208 new_entry->next_hop = *next_hop;
295 if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iterator, NULL, 209 new_entry->prev_hop = *prev_hop;
296 (const void **)&trail)) 210 return GNUNET_CONTAINER_multihashmap_put (routing_table,
297 { 211 &new_trail_id, new_entry,
298 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(trail->destination), destination_peer)) 212 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
299 {
300 GNUNET_assert (GNUNET_YES ==
301 GNUNET_CONTAINER_multipeermap_remove (routing_table,
302 &(trail->destination),
303 trail));
304 return GNUNET_YES;
305 }
306 }
307 }
308 GNUNET_CONTAINER_multipeermap_iterator_destroy (iterator);
309 return GNUNET_NO;
310} 213}
311 214
312 215
313
314/** 216/**
315 * Check if the size of routing table has crossed threshold. 217 * Check if the size of routing table has crossed threshold.
316 * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO. 218 * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO.
317 */ 219 */
318int 220int
319GDS_ROUTING_check_threshold () 221GDS_ROUTING_threshold_reached (void)
320{ 222{
321 return (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD) ? 223 return (GNUNET_CONTAINER_multihashmap_size(routing_table) >
322 GNUNET_YES:GNUNET_NO; 224 ROUTING_TABLE_THRESHOLD) ? GNUNET_YES:GNUNET_NO;
323} 225}
324 226
325 227
@@ -329,25 +231,19 @@ GDS_ROUTING_check_threshold ()
329void 231void
330GDS_ROUTING_init (void) 232GDS_ROUTING_init (void)
331{ 233{
332 routing_table = GNUNET_CONTAINER_multipeermap_create (ROUTING_TABLE_THRESHOLD * 4 / 3, 234 routing_table = GNUNET_CONTAINER_multihashmap_create (ROUTING_TABLE_THRESHOLD * 4 / 3,
333 GNUNET_NO); 235 GNUNET_NO);
334} 236}
335 237
336 238
337/** 239/**
338 * FIXME: here you can have routing table with size 0, only when you delete
339 * the entries correctly. Possible scenarios where we delete the entries are
340 * 1. when one of my friend gets disconnected then I remove any trail (does not
341 * matter if that friend is source, destination, next hop or previous hop).
342 * 2. if I get a trail teardown message then I remove the entry.
343 * Is there any other case that I may have missed?
344 * Shutdown routing subsystem. 240 * Shutdown routing subsystem.
345 */ 241 */
346void 242void
347GDS_ROUTING_done (void) 243GDS_ROUTING_done (void)
348{ 244{
349 GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (routing_table)); 245 GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (routing_table));
350 GNUNET_CONTAINER_multipeermap_destroy (routing_table); 246 GNUNET_CONTAINER_multihashmap_destroy (routing_table);
351} 247}
352 248
353/* end of gnunet-service-xdht_routing.c */ \ No newline at end of file 249/* end of gnunet-service-xdht_routing.c */ \ No newline at end of file
diff --git a/src/dht/gnunet-service-xdht_routing.h b/src/dht/gnunet-service-xdht_routing.h
index 2475741c4..f186f5f8c 100644
--- a/src/dht/gnunet-service-xdht_routing.h
+++ b/src/dht/gnunet-service-xdht_routing.h
@@ -30,81 +30,77 @@
30#include "gnunet_block_lib.h" 30#include "gnunet_block_lib.h"
31#include "gnunet_dht_service.h" 31#include "gnunet_dht_service.h"
32 32
33
34/** 33/**
35 * Add a new entry to our routing table. 34 * To understand the direction in which trial should be read.
36 * @param source peer Source of the trail.
37 * @param destintation Destination of the trail.
38 * @param next_hop Next peer to forward the message to reach the destination.
39 * @return GNUNET_YES
40 * GNUNET_SYSERR If the number of routing entries crossed thershold.
41 */ 35 */
42int 36enum GDS_ROUTING_trail_direction
43GDS_ROUTING_add (const struct GNUNET_PeerIdentity *source, 37{
44 const struct GNUNET_PeerIdentity *dest, 38 GDS_ROUTING_SRC_TO_DEST,
45 const struct GNUNET_PeerIdentity *next_hop, 39 GDS_ROUTING_DEST_TO_SRC
46 const struct GNUNET_PeerIdentity *prev_hop); 40};
47 41
48 42
49/** 43/**
50 * Iterate over routing table and remove entries for which peer is a part. 44 * Update the prev. hop of the trail. Call made by trail teardown where
51 * @param peer 45 * if you are the first friend now in the trail then you need to update
52 * @return 46 * your prev. hop.
47 * @param trail_id
48 * @return #GNUNET_OK success
49 * #GNUNET_SYSERR in case no matching entry found in routing table.
53 */ 50 */
54void 51int
55GDS_ROUTING_remove_entry (const struct GNUNET_PeerIdentity *peer); 52GDS_ROUTING_update_trail_prev_hop (struct GNUNET_HashCode trail_id,
56 53 struct GNUNET_PeerIdentity prev_hop);
57 54
58/** 55/**
59 * Search the next hop to send the packet to in routing table. 56 * Get the next hop for trail corresponding to trail_id
60 * @return next hop peer id 57 * @param trail_id Trail id to be searched.
58 * @return Next_hop if found
59 * NULL If next hop not found.
61 */ 60 */
62struct GNUNET_PeerIdentity * 61struct GNUNET_PeerIdentity *
63GDS_ROUTING_search(struct GNUNET_PeerIdentity *source_peer, 62GDS_ROUTING_get_next_hop (struct GNUNET_HashCode trail_id,
64 struct GNUNET_PeerIdentity *destination_peer, 63 enum GDS_ROUTING_trail_direction trail_direction);
65 const struct GNUNET_PeerIdentity *prev_hop); 64
66 65
67/** 66/**
68 * FIXME: How to ensure that with only 3 fields also we have a unique trail. 67 * Remove every trail where peer is either next_hop or prev_hop
69 * in case of redundant routes we can have different next hop. 68 * @param peer Peer to be searched.
70 * in that case we have to call this function on each entry of routing table 69 */
71 * and from multiple next hop we return one. Here also we are going to return one. 70void
72 * URGENT. 71GDS_ROUTING_remove_trail_by_peer (const struct GNUNET_PeerIdentity *peer);
73 * Assumption - there can be only on one trail with all these fields. But if 72/**
74 * we consider only 3 fields then it is possible that next hop is differet. 73 * Remove trail with trail_id
75 * Update prev_hop field to source_peer. Trail from source peer to destination 74 * @param trail_id Trail id to be removed
76 * peer is compressed such that I am the first friend in the trail. 75 * @return #GNUNET_YES success
77 * @param source_peer Source of the trail. 76 * #GNUNET_NO if entry not found.
78 * @param destination_peer Destination of the trail.
79 * @param prev_hop Peer before me in the trail.
80 * @return #GNUNET_YES trail is updated.
81 * #GNUNET_NO, trail not found.
82 */ 77 */
83int 78int
84GDS_ROUTING_trail_update (struct GNUNET_PeerIdentity *source_peer, 79GDS_ROUTING_remove_trail (struct GNUNET_HashCode remove_trail_id);
85 struct GNUNET_PeerIdentity *destination_peer,
86 const struct GNUNET_PeerIdentity *prev_hop);
87 80
88 81
89/** 82/**
90 * Remove the trail as result of trail tear down message. 83 * Add a new entry in routing table
91 * @param source_peer Source of the trail. 84 * @param new_trail_id
92 * @param destination_peer Destination of the trail. 85 * @param prev_hop
93 * @param next_hop Next hop 86 * @param next_hop
94 * @param prev_hop Previous hop. 87 * @return #GNUNET_OK success
95 * @return #GNUNET_YES if successful 88 * #GNUNET_SYSERR in case new_trail_id already exists in the network
96 * #GNUNET_NO if not successful. 89 * but with different prev_hop/next_hop
97 */ 90 */
98int 91int
99GDS_ROUTING_remove_trail (struct GNUNET_PeerIdentity *source_peer, 92GDS_ROUTING_add (struct GNUNET_HashCode new_trail_id,
100 struct GNUNET_PeerIdentity *destination_peer, 93 struct GNUNET_PeerIdentity *prev_hop,
101 const struct GNUNET_PeerIdentity *prev_hop); 94 const struct GNUNET_PeerIdentity *next_hop);
102 95
103/** 96/**
104 * Check if size of routing table is greater than threshold or not. 97 * Check if the size of routing table has crossed threshold.
98 * @return #GNUNET_YES, if threshold crossed
99 * #GNUNET_NO, if size is within threshold
105 */ 100 */
106int 101int
107GDS_ROUTING_check_threshold (void); 102GDS_ROUTING_threshold_reached (void);
103
108 104
109/** 105/**
110 * Initialize routing subsystem. 106 * Initialize routing subsystem.
@@ -112,11 +108,9 @@ GDS_ROUTING_check_threshold (void);
112void 108void
113GDS_ROUTING_init (void); 109GDS_ROUTING_init (void);
114 110
115
116/** 111/**
117 * Shutdown routing subsystem. 112 * Shutdown routing subsystem.
118 */ 113 */
119void 114void
120GDS_ROUTING_done (void); 115GDS_ROUTING_done (void);
121 116#endif \ No newline at end of file
122#endif
diff --git a/src/include/gnunet_protocols.h b/src/include/gnunet_protocols.h
index 855ee0703..5a698a8d4 100644
--- a/src/include/gnunet_protocols.h
+++ b/src/include/gnunet_protocols.h
@@ -653,7 +653,12 @@ extern "C"
653/** 653/**
654 * Routing table add message. 654 * Routing table add message.
655 */ 655 */
656#define GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL 165 656#define GNUNET_MESSAGE_TYPE_DHT_P2P_ADD_TRAIL 165
657
658/**
659 * Trail compessiong message.
660 */
661#define GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_COMPRESSION 166
657/******************************************************************************* 662/*******************************************************************************
658 * HOSTLIST message types 663 * HOSTLIST message types
659 ******************************************************************************/ 664 ******************************************************************************/