src/dht/gnunet-service-xdht_neighbours.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2009-2013 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file dht/gnunet-service-xdht_neighbours.c
  23  * @brief GNUnet DHT service's finger and friend table management code
  24  * @author Supriti Singh
  25  */
  26
  27 #include "platform.h"
  28 #include "gnunet_util_lib.h"
  29 #include "gnunet_block_lib.h"
  30 #include "gnunet_hello_lib.h"
  31 #include "gnunet_constants.h"
  32 #include "gnunet_protocols.h"
  33 #include "gnunet_nse_service.h"
  34 #include "gnunet_ats_service.h"
  35 #include "gnunet_core_service.h"
  36 #include "gnunet_datacache_lib.h"
  37 #include "gnunet_transport_service.h"
  38 #include "gnunet_hello_lib.h"
  39 #include "gnunet_dht_service.h"
  40 #include "gnunet_statistics_service.h"
  41 #include "gnunet-service-xdht.h"
  42 #include "gnunet-service-xdht_clients.h"
  43 #include "gnunet-service-xdht_datacache.h"
  44 #include "gnunet-service-xdht_hello.h"
  45 #include "gnunet-service-xdht_neighbours.h"
  46 #include "gnunet-service-xdht_nse.h"
  47 #include "gnunet-service-xdht_routing.h"
  48 #include <fenv.h>
  49 #include "dht.h"
  50
  51 /* TODO:
  52  1. Use a global array of all known peers in find_successor, Only when
  53  a new peer is added in finger or friend peer map, then re calculate
  54  the array. Or else use the old one. */
  55
  56 /**
  57  * Maximum possible fingers of a peer.
  58  */
  59 #define MAX_FINGERS 64
  60
  61 /**
  62  * Maximum allowed number of pending messages per friend peer.
  63  */
  64 #define MAXIMUM_PENDING_PER_FRIEND 64
  65
  66 /**
  67  * How long at least to wait before sending another find finger trail request.
  68  */
  69 #define DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 30)
  70
  71 /**
  72  * How long at most to wait before sending another find finger trail request.
  73  */
  74 #define DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 10)
  75
  76 /**
  77  * How long at most to wait for transmission of a GET request to another peer?
  78  */
  79 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
  80
  81
  82 GNUNET_NETWORK_STRUCT_BEGIN
  83
  84 /**
  85  * P2P PUT message
  86  */
  87 struct PeerPutMessage
  88 {
  89   /**
  90    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
  91    */
  92   struct GNUNET_MessageHeader header;
  93
  94   /**
  95    * Processing options
  96    */
  97   uint32_t options GNUNET_PACKED;
  98
  99   /**
 100    * Content type.
 101    */
 102   uint32_t type GNUNET_PACKED;
 103
 104   /**
 105    * Hop count
 106    */
 107   uint32_t hop_count GNUNET_PACKED;
 108
 109   /**
 110    * Replication level for this message
 111    */
 112   uint32_t desired_replication_level GNUNET_PACKED;
 113
 114   /**
 115    * Length of the PUT path that follows (if tracked).
 116    */
 117   uint32_t put_path_length GNUNET_PACKED;
 118
 119   /**
 120    * When does the content expire?
 121    */
 122   struct GNUNET_TIME_AbsoluteNBO expiration_time;
 123
 124   /**
 125    * Bloomfilter (for peer identities) to stop circular routes
 126    */
 127   char bloomfilter[DHT_BLOOM_SIZE];
 128
 129   /**
 130    * The key we are storing under.
 131    */
 132   struct GNUNET_HashCode key;
 133
 134   /* put path (if tracked) */
 135
 136   /* Payload */
 137
 138 };
 139
 140
 141 /**
 142  * P2P Result message
 143  */
 144 struct PeerResultMessage
 145 {
 146   /**
 147    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
 148    */
 149   struct GNUNET_MessageHeader header;
 150
 151   /**
 152    * Content type.
 153    */
 154   uint32_t type GNUNET_PACKED;
 155
 156   /**
 157    * Length of the PUT path that follows (if tracked).
 158    */
 159   uint32_t put_path_length GNUNET_PACKED;
 160
 161   /**
 162    * Length of the GET path that follows (if tracked).
 163    */
 164   uint32_t get_path_length GNUNET_PACKED;
 165
 166   /**
 167    * When does the content expire?
 168    */
 169   struct GNUNET_TIME_AbsoluteNBO expiration_time;
 170
 171   /**
 172    * The key of the corresponding GET request.
 173    */
 174   struct GNUNET_HashCode key;
 175
 176   /* put path (if tracked) */
 177
 178   /* get path (if tracked) */
 179
 180   /* Payload */
 181
 182 };
 183
 184
 185 /**
 186  * P2P GET message
 187  */
 188 struct PeerGetMessage
 189 {
 190   /**
 191    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
 192    */
 193   struct GNUNET_MessageHeader header;
 194
 195   /**
 196    * Processing options
 197    */
 198   uint32_t options GNUNET_PACKED;
 199
 200   /**
 201    * Desired content type.
 202    */
 203   uint32_t type GNUNET_PACKED;
 204
 205   /**
 206    * Hop count
 207    */
 208   uint32_t hop_count GNUNET_PACKED;
 209
 210   /**
 211    * Desired replication level for this request.
 212    */
 213   uint32_t desired_replication_level GNUNET_PACKED;
 214
 215   /**
 216    * Size of the extended query.
 217    */
 218   uint32_t xquery_size;
 219
 220   /**
 221    * Bloomfilter mutator.
 222    */
 223   uint32_t bf_mutator;
 224
 225   /**
 226    * Bloomfilter (for peer identities) to stop circular routes
 227    */
 228   char bloomfilter[DHT_BLOOM_SIZE];
 229
 230   /**
 231    * The key we are looking for.
 232    */
 233   struct GNUNET_HashCode key;
 234
 235 };
 236
 237
 238 /**
 239  * FIXME: Change the comment to explain about usage of this in find successor.
 240  * Field in trail setup message to understand if the message is sent to an
 241  * intermediate finger, friend or me.
 242  */
 243 enum current_destination_type
 244 {
 245   FRIEND ,
 246   FINGER ,
 247   MY_ID ,
 248   VALUE
 249 };
 250
 251
 252 /**
 253  * P2P Trail setup message
 254  */
 255 struct PeerTrailSetupMessage
 256 {
 257
 258   /**
 259    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
 260    */
 261   struct GNUNET_MessageHeader header;
 262
 263   /**
 264    * Source peer which wants to setup the trail to one of its finger.
 265    */
 266   struct GNUNET_PeerIdentity source_peer;
 267
 268   /**
 269    * Successor of this finger value will be our finger peer.
 270    */
 271   uint64_t destination_finger;
 272
 273   /**
 274    * Peer which gets this message can be either an intermediate finger or friend.
 275    */
 276   enum current_destination_type current_destination_type;
 277
 278   /**
 279    * Peer to which this packet is forwarded.
 280    */
 281   struct GNUNET_PeerIdentity current_destination;
 282
 283   /**
 284    * Index into finger peer map.
 285    */
 286   unsigned int finger_map_index;
 287
 288   /**
 289    * Number of entries in trail list.
 290    */
 291   uint32_t trail_length GNUNET_PACKED;
 292
 293 };
 294
 295
 296 /**
 297  * P2P Trail Setup Result message
 298  */
 299 struct PeerTrailSetupResultMessage
 300 {
 301
 302   /**
 303    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_RESULT_SETUP
 304    */
 305   struct GNUNET_MessageHeader header;
 306
 307   /**
 308    * Finger to which we have found the path.
 309    */
 310   struct GNUNET_PeerIdentity finger_identity;
 311
 312   /**
 313    * Peer which was looking for the trail to finger.
 314    */
 315   struct GNUNET_PeerIdentity destination_peer;
 316
 317   /**
 318    * Trail index which points to next destination to send this message.
 319    */
 320   unsigned int current_index;
 321
 322   /**
 323    * Index into finger peer map
 324    */
 325   unsigned int finger_map_index;
 326
 327   /**
 328    * Number of entries in trail list.
 329    */
 330   uint32_t trail_length GNUNET_PACKED;
 331
 332 };
 333
 334
 335 /**
 336  * P2P Verify Successor message.
 337  */
 338 struct PeerVerifySuccessorMessage
 339 {
 340
 341   /**
 342    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR
 343    */
 344   struct GNUNET_MessageHeader header;
 345
 346   /**
 347    * Source peer which wants to verify its successor.
 348    */
 349   struct GNUNET_PeerIdentity source_peer;
 350
 351   /**
 352    * My current successor.
 353    */
 354   struct GNUNET_PeerIdentity successor;
 355
 356   /**
 357    * Total number of peers in trail to current successor.
 358    */
 359   unsigned int trail_length;
 360
 361   /**
 362    * Trail index which points to next destination to send this message.
 363    */
 364   unsigned int current_trail_index;
 365
 366 };
 367
 368
 369 /**
 370  * P2P Verify Successor Result message.
 371  */
 372 struct PeerVerifySuccessorResultMessage
 373 {
 374
 375   /**
 376    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT
 377    */
 378   struct GNUNET_MessageHeader header;
 379
 380   /**
 381    * Destination peer which sent the request to verify its successor.
 382    */
 383   struct GNUNET_PeerIdentity destination_peer;
 384
 385   /**
 386    * Successor to which PeerVerifySuccessorMessage was sent.
 387    */
 388   struct GNUNET_PeerIdentity source_successor;
 389
 390   /**
 391    * source_successor's predecessor
 392    */
 393   struct GNUNET_PeerIdentity my_predecessor;
 394
 395   /**
 396    * Total number of peers in trail.
 397    * If source_successor is not destination peer, then trail is from destination_peer
 398    * to my_predecessor.
 399    * If source_successor is destination peer, then trail is from destination_peer
 400    * to source_successor.
 401    */
 402   unsigned int trail_length;
 403
 404   /**
 405    * Trail index which points to next destination to send this message.
 406    */
 407   unsigned int current_index;
 408
 409 };
 410
 411 /**
 412  * P2P Notify New Successor message.
 413  */
 414 struct PeerNotifyNewSuccessorMessage
 415 {
 416   /**
 417    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR
 418    */
 419   struct GNUNET_MessageHeader header;
 420
 421   /**
 422    * Source peer which wants to notify its new successor.
 423    */
 424   struct GNUNET_PeerIdentity source_peer;
 425
 426   /**
 427    * New successor identity.
 428    */
 429   struct GNUNET_PeerIdentity destination_peer;
 430
 431   /**
 432    * Number of peers in trail from source_peer to new successor.
 433    */
 434   unsigned int trail_length;
 435
 436   /**
 437    * Trail index which points to next destination to send this message.
 438    */
 439   unsigned int current_index;
 440
 441 };
 442
 443
 444 GNUNET_NETWORK_STRUCT_END
 445
 446
 447 /**
 448  * Linked list of messages to send to a particular other peer.
 449  */
 450 struct P2PPendingMessage
 451 {
 452   /**
 453    * Pointer to next item in the list
 454    */
 455   struct P2PPendingMessage *next;
 456
 457   /**
 458    * Pointer to previous item in the list
 459    */
 460   struct P2PPendingMessage *prev;
 461
 462   /**
 463    * When does this message time out?
 464    */
 465   struct GNUNET_TIME_Absolute timeout;
 466
 467    /**
 468    * Message importance level.  FIXME: used? useful?
 469    */
 470   unsigned int importance;
 471
 472   /**
 473    * Actual message to be sent, allocated at the end of the struct:
 474    * // msg = (cast) &pm[1];
 475    * // memcpy (&pm[1], data, len);
 476    */
 477   const struct GNUNET_MessageHeader *msg;
 478
 479 };
 480
 481
 482 /**
 483  * Linked List of peers which are part of trail to reach a particular Finger.
 484  */
 485 struct TrailPeerList
 486 {
 487    /**
 488     * Pointer to next item in the list
 489     */
 490    struct TrailPeerList *next;
 491
 492    /**
 493     * Pointer to previous item in the list
 494     */
 495    struct TrailPeerList *prev;
 496
 497    /**
 498     * An element in this trail list
 499     */
 500    struct GNUNET_PeerIdentity peer;
 501
 502 };
 503
 504
 505 /**
 506  *  Entry in friend_peermap.
 507  */
 508 struct FriendInfo
 509 {
 510   /**
 511    * Friend Identity
 512    */
 513   struct GNUNET_PeerIdentity id;
 514
 515   /**
 516    * Count of outstanding messages for this friend.
 517    */
 518   unsigned int pending_count;
 519
 520   /**
 521    * Head of pending messages to be sent to this friend.
 522    */
 523   struct P2PPendingMessage *head;
 524
 525   /**
 526    * Tail of pending messages to be sent to this friend.
 527    */
 528   struct P2PPendingMessage *tail;
 529
 530   /**
 531    * Core handle for sending messages to this friend.
 532    */
 533   struct GNUNET_CORE_TransmitHandle *th;
 534
 535 };
 536
 537
 538 /**
 539  * Entry in finger_peermap.
 540  */
 541 struct FingerInfo
 542 {
 543   /**
 544    * Finger identity.
 545    */
 546   struct GNUNET_PeerIdentity finger_identity;
 547
 548   /**
 549    * Index in finger peer map
 550    */
 551   unsigned int finger_map_index;
 552
 553   /**
 554    * Total number of entries in trail from [me,finger]
 555    */
 556   unsigned int trail_length;
 557
 558   /**
 559    * Head of trail to reach this finger.
 560    */
 561   struct TrailPeerList *head;
 562
 563   /**
 564    * Tail of trail to reach this finger.
 565    */
 566   struct TrailPeerList *tail;
 567
 568 };
 569
 570
 571 /**
 572  * FIXME: Think of a better name.
 573  * Data structure passed to sorting algorithm in find_successor.
 574  */
 575 struct Sorting_List
 576 {
 577   /**
 578    * 64 bit value of peer identity
 579    */
 580   uint64_t peer_id;
 581
 582   /**
 583    * Type : MY_ID, FINGER, FINGER, Value
 584    */
 585   enum current_destination_type type;
 586
 587   /**
 588    * Pointer to original data structure linked to peer id.
 589    */
 590   void *data;
 591 };
 592
 593
 594 /**
 595  * Task that sends FIND FINGER TRAIL requests.
 596  */
 597 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
 598
 599 /**
 600  *
 601  * Task that periodically verifies my successor.
 602  */
 603 static GNUNET_SCHEDULER_TaskIdentifier verify_successor;
 604
 605 /**
 606  * Identity of this peer.
 607  */
 608 static struct GNUNET_PeerIdentity my_identity;
 609
 610 /**
 611  * Hash map of all the friends of a peer
 612  */
 613 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
 614
 615 /**
 616  * Hash map of all the fingers of a peer
 617  */
 618 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
 619
 620 /**
 621  * Handle to ATS.
 622  */
 623 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
 624
 625 /**
 626  * Handle to CORE.
 627  */
 628 static struct GNUNET_CORE_Handle *core_api;
 629
 630 /**
 631  * FIXME: Is it safe to assume its initialized to 0 by default.
 632  * The current finger index that we have found trail to.
 633  */
 634 static unsigned int current_finger_index;
 635
 636
 637 /**
 638  * Called when core is ready to send a message we asked for
 639  * out to the destination.
 640  *
 641  * @param cls the 'struct FriendInfo' of the target friend
 642  * @param size number of bytes available in buf
 643  * @param buf where the callee should write the message
 644  * @return number of bytes written to buf
 645  */
 646 static size_t
 647 core_transmit_notify (void *cls, size_t size, void *buf)
 648 {
 649   struct FriendInfo *peer = cls;
 650   char *cbuf = buf;
 651   struct P2PPendingMessage *pending;
 652   size_t off;
 653   size_t msize;
 654
 655   peer->th = NULL;
 656   while ((NULL != (pending = peer->head)) &&
 657          (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
 658   {
 659     peer->pending_count--;
 660     GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
 661     GNUNET_free (pending);
 662   }
 663   if (NULL == pending)
 664   {
 665     /* no messages pending */
 666     return 0;
 667   }
 668   if (NULL == buf)
 669   {
 670     peer->th =
 671         GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
 672                                            GNUNET_CORE_PRIO_BEST_EFFORT,
 673                                            GNUNET_TIME_absolute_get_remaining
 674                                            (pending->timeout), &peer->id,
 675                                            ntohs (pending->msg->size),
 676                                            &core_transmit_notify, peer);
 677     GNUNET_break (NULL != peer->th);
 678     return 0;
 679   }
 680   off = 0;
 681   while ((NULL != (pending = peer->head)) &&
 682          (size - off >= (msize = ntohs (pending->msg->size))))
 683   {
 684     GNUNET_STATISTICS_update (GDS_stats,
 685                               gettext_noop
 686                               ("# Bytes transmitted to other peers"), msize,
 687                               GNUNET_NO);
 688     memcpy (&cbuf[off], pending->msg, msize);
 689     off += msize;
 690     peer->pending_count--;
 691     GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
 692     GNUNET_free (pending);
 693   }
 694   if (peer->head != NULL)
 695   {
 696     peer->th =
 697         GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
 698                                            GNUNET_CORE_PRIO_BEST_EFFORT,
 699                                            GNUNET_TIME_absolute_get_remaining
 700                                            (pending->timeout), &peer->id, msize,
 701                                            &core_transmit_notify, peer);
 702     GNUNET_break (NULL != peer->th);
 703   }
 704   return off;
 705 }
 706
 707
 708 /**
 709  * Transmit all messages in the friend's message queue.
 710  *
 711  * @param peer message queue to process
 712  */
 713 static void
 714 process_friend_queue (struct FriendInfo *peer)
 715 {
 716   struct P2PPendingMessage *pending;
 717
 718   if (NULL == (pending = peer->head))
 719     return;
 720   if (NULL != peer->th)
 721     return;
 722
 723   GNUNET_STATISTICS_update (GDS_stats,
 724                             gettext_noop
 725                             ("# Bytes of bandwidth requested from core"),
 726                             ntohs (pending->msg->size), GNUNET_NO);
 727
 728   /* FIXME: Are we correctly initializing importance and pending. */
 729   peer->th =
 730       GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
 731                                          pending->importance,
 732                                          GNUNET_TIME_absolute_get_remaining
 733                                          (pending->timeout), &peer->id,
 734                                          ntohs (pending->msg->size),
 735                                          &core_transmit_notify, peer);
 736   GNUNET_break (NULL != peer->th);
 737 }
 738
 739
 740 /**
 741  * Construct a trail message and forward it to a friend.
 742  * @param source_peer Peer which wants to set up the trail to one of its finger.
 743  * @param destination_finger Value whose successor we are searching the network.
 744  * @param current_destination Peer which gets this message.
 745  * @param target_friend Current friend to which this message should be forwarded.
 746  * @param trail_length Numbers of peers in the trail.
 747  * @param trail_peer_list peers this request has traversed so far
 748  * @param finger_map_index Index in finger peer map
 749  * @param type Type of current destination can be either FRIEND or FINGER
 750  */
 751 void
 752 GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity *source_peer,
 753                                  uint64_t destination_finger,
 754                                  struct GNUNET_PeerIdentity *current_destination,
 755                                  struct FriendInfo *target_friend,
 756                                  unsigned int trail_length,
 757                                  struct GNUNET_PeerIdentity *trail_peer_list,
 758                                  unsigned int finger_map_index,
 759                                  enum current_destination_type type)
 760 {
 761   struct P2PPendingMessage *pending;
 762   struct PeerTrailSetupMessage *tsm;
 763   struct GNUNET_PeerIdentity *peer_list;
 764   size_t msize;
 765
 766   msize = sizeof (struct PeerTrailSetupMessage) +
 767           (trail_length * sizeof (struct GNUNET_PeerIdentity));
 768
 769   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
 770   {
 771     GNUNET_break (0);
 772     return;
 773   }
 774
 775   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
 776   {
 777     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
 778                                 1, GNUNET_NO);
 779   }
 780
 781   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
 782   pending->importance = 0;    /* FIXME */
 783   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
 784   tsm = (struct PeerTrailSetupMessage *) &pending[1];
 785   pending->msg = &tsm->header;
 786   tsm->header.size = htons (msize);
 787   tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
 788   memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
 789   memcpy (&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
 790   memcpy (&(tsm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity));
 791   tsm->current_destination_type = htonl (type);
 792   tsm->trail_length = htonl (trail_length);
 793   tsm->finger_map_index = htonl (finger_map_index);
 794
 795   peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
 796   memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
 797   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
 798   target_friend->pending_count++;
 799   process_friend_queue (target_friend);
 800
 801 }
 802
 803
 804 /**
 805  * Construct a trail setup result message and forward it to a friend.
 806  * @param destination_peer Peer which will get the trail to one of its finger.
 807  * @param source_finger Peer to which the trail has been setup to.
 808  * @param target_friend Friend to which this message should be forwarded.
 809  * @param trail_length Numbers of peers in the trail.
 810  * @param trail_peer_list Peers which are part of the trail from source to destination.
 811  * @param current_trail_index Index in the trial list at which receiving peer should
 812  *                            read the next element.
 813  * @param finger_map_index Index in finger peer map
 814  */
 815 void
 816 GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity *destination_peer,
 817                                         struct GNUNET_PeerIdentity *source_finger,
 818                                         struct FriendInfo *target_friend,
 819                                         unsigned int trail_length,
 820                                         struct GNUNET_PeerIdentity *trail_peer_list,
 821                                         unsigned int current_trail_index,
 822                                         unsigned int finger_map_index)
 823 {
 824   struct P2PPendingMessage *pending;
 825   struct PeerTrailSetupResultMessage *tsrm;
 826   struct GNUNET_PeerIdentity *peer_list;
 827   size_t msize;
 828
 829   msize = sizeof (struct PeerTrailSetupResultMessage) +
 830           (trail_length * sizeof (struct GNUNET_PeerIdentity));
 831
 832   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
 833   {
 834     GNUNET_break (0);
 835     return;
 836   }
 837
 838   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
 839   {
 840     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
 841                                 1, GNUNET_NO);
 842   }
 843
 844   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
 845   pending->importance = 0;
 846   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
 847   tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
 848   pending->msg = &tsrm->header;
 849   tsrm->header.size = htons (msize);
 850   tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
 851   memcpy (&(tsrm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
 852   memcpy (&(tsrm->finger_identity), source_finger, sizeof (struct GNUNET_PeerIdentity));
 853   tsrm->trail_length = htonl (trail_length);
 854   tsrm->current_index = htonl (current_trail_index);
 855   tsrm->finger_map_index = htonl (finger_map_index);
 856   peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
 857   memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
 858
 859   /* Send the message to chosen friend. */
 860   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
 861   target_friend->pending_count++;
 862   process_friend_queue (target_friend);
 863 }
 864
 865
 866 /**
 867  * Construct a PeerVerifySuccessor message and send it to friend.
 868  * @param source_peer Peer which wants to verify its successor
 869  * @param successor Peer which is our current successor
 870  * @param target_friend Friend to which this message should be forwarded.
 871  * @param trail_peer_list Peer which are part of trail from source to destination
 872  * @param trail_length Number of peers in the trail list.
 873  * @param current_trail_index Index in the trial list at which receiving peer should
 874  *                            read the next element.
 875  */
 876 void GDS_NEIGHBOURS_send_verify_successor(struct GNUNET_PeerIdentity *source_peer,
 877                                           struct GNUNET_PeerIdentity *successor,
 878                                           struct FriendInfo *target_friend,
 879                                           struct GNUNET_PeerIdentity *trail_peer_list,
 880                                           unsigned int trail_length,
 881                                           unsigned int current_trail_index)
 882 {
 883   struct PeerVerifySuccessorMessage *vsm;
 884   struct P2PPendingMessage *pending;
 885   struct GNUNET_PeerIdentity *peer_list;
 886   size_t msize;
 887
 888   msize = sizeof (struct PeerVerifySuccessorMessage) +
 889           (trail_length * sizeof (struct GNUNET_PeerIdentity));
 890
 891   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
 892   {
 893     GNUNET_break (0);
 894     return;
 895   }
 896
 897   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
 898   {
 899     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
 900                                 1, GNUNET_NO);
 901   }
 902
 903   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
 904   pending->importance = 0;    /* FIXME */
 905   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
 906   vsm = (struct PeerVerifySuccessorMessage *) &pending[1];
 907   pending->msg = &vsm->header;
 908   vsm->header.size = htons (msize);
 909   vsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR);
 910   memcpy (&(vsm->successor), successor, sizeof (struct GNUNET_PeerIdentity));
 911   memcpy (&(vsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
 912   vsm->trail_length = htonl (trail_length);
 913   vsm->current_trail_index = htonl (current_trail_index);
 914   peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
 915   memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
 916
 917   /* Send the message to chosen friend. */
 918   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
 919   target_friend->pending_count++;
 920   process_friend_queue (target_friend);
 921
 922 }
 923
 924
 925 /**
 926  * Construct a PeerVerifySuccessorResult message and send it to friend.
 927  * @param destination_peer Peer which sent verify successor message
 928  * @param source_successor Peer to which verify successor message was sent.
 929  * @param my_predecessor source_successor's predecessor.
 930  * @param target_friend Friend to which this message should be forwarded.
 931  * @param trail_peer_list Peers which are part of trail from source to destination
 932  * @param trail_length Number of peers in the trail list.
 933  * @param current_trail_index Index in the trial list at which receiving peer should
 934  *                            get the next element.
 935  */
 936 void GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity *destination_peer,
 937                                                   struct GNUNET_PeerIdentity *source_successor,
 938                                                   struct GNUNET_PeerIdentity *my_predecessor,
 939                                                   struct FriendInfo *target_friend,
 940                                                   struct GNUNET_PeerIdentity *trail_peer_list,
 941                                                   unsigned int trail_length,
 942                                                   unsigned int current_trail_index)
 943 {
 944   struct PeerVerifySuccessorResultMessage *vsmr;
 945   struct P2PPendingMessage *pending;
 946   struct GNUNET_PeerIdentity *peer_list;
 947   size_t msize;
 948
 949   msize = sizeof (struct PeerVerifySuccessorResultMessage) +
 950           (trail_length * sizeof(struct GNUNET_PeerIdentity));
 951
 952   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
 953   {
 954     GNUNET_break (0);
 955     return;
 956   }
 957
 958
 959   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
 960   {
 961     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
 962                                 1, GNUNET_NO);
 963   }
 964
 965   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
 966   pending->importance = 0;    /* FIXME */
 967   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
 968   vsmr = (struct PeerVerifySuccessorResultMessage *) &pending[1];
 969   pending->msg = &vsmr->header;
 970   vsmr->header.size = htons (msize);
 971   vsmr->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT);
 972   memcpy (&(vsmr->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
 973   memcpy (&(vsmr->source_successor), source_successor, sizeof (struct GNUNET_PeerIdentity));
 974   memcpy (&(vsmr->my_predecessor), my_predecessor, sizeof (struct GNUNET_PeerIdentity));
 975   vsmr->trail_length = htonl (trail_length);
 976   vsmr->current_index = htonl (current_trail_index);
 977
 978   peer_list = (struct GNUNET_PeerIdentity *) &vsmr[1];
 979   memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
 980
 981    /* Send the message to chosen friend. */
 982   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
 983   target_friend->pending_count++;
 984   process_friend_queue (target_friend);
 985 }
 986
 987
 988 /**
 989  * Construct a PeerNotifyNewSuccessor message and send it to friend.
 990  * @param source_peer Peer which is sending notify message to its new successor.
 991  * @param destination_peer Peer which is the new destination.
 992  * @param target_friend Next friend to pass this message to.
 993  * @param peer_list List of peers in the trail to reach to destination_peer.
 994  * @param current_trail_index Index of peer_list for next target friend position.
 995  * @param trail_length Total number of peers in peer list
 996  */
 997 void
 998 GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity *source_peer,
 999                                           struct GNUNET_PeerIdentity *destination_peer,
1000                                           struct FriendInfo *target_friend,
1001                                           struct GNUNET_PeerIdentity *trail_peer_list,
1002                                           unsigned int trail_length,
1003                                           unsigned int current_trail_index)
1004 {
1005   struct PeerNotifyNewSuccessorMessage *nsm;
1006   struct P2PPendingMessage *pending;
1007   struct GNUNET_PeerIdentity *peer_list;
1008   size_t msize;
1009
1010   msize = sizeof (struct PeerNotifyNewSuccessorMessage) +
1011           (trail_length * sizeof(struct GNUNET_PeerIdentity));
1012
1013   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
1014   {
1015     GNUNET_break (0);
1016     return;
1017   }
1018
1019   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
1020   {
1021     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
1022                                 1, GNUNET_NO);
1023   }
1024
1025   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
1026   pending->importance = 0;    /* FIXME */
1027   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
1028   nsm = (struct PeerNotifyNewSuccessorMessage *) &pending[1];
1029   pending->msg = &nsm->header;
1030   nsm->header.size = htons (msize);
1031   nsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR);
1032   memcpy (&(nsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
1033   memcpy (&(nsm->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity));
1034   nsm->trail_length = htonl (trail_length);
1035   nsm->current_index = htonl (current_trail_index);
1036
1037   peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
1038   memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1039
1040    /* Send the message to chosen friend. */
1041   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
1042   target_friend->pending_count++;
1043   process_friend_queue (target_friend);
1044 }
1045
1046
1047 /**FIXME: Old implementation just to remove error
1048  * TODO: Modify this function to handle our get request.
1049  * Perform a GET operation.  Forwards the given request to other
1050  * peers.  Does not lookup the key locally.  May do nothing if this is
1051  * the only peer in the network (or if we are the closest peer in the
1052  * network).
1053  *
1054  * @param type type of the block
1055  * @param options routing options
1056  * @param desired_replication_level desired replication count
1057  * @param hop_count how many hops did this request traverse so far?
1058  * @param key key for the content
1059  * @param xquery extended query
1060  * @param xquery_size number of bytes in @a xquery
1061  * @param reply_bf bloomfilter to filter duplicates
1062  * @param reply_bf_mutator mutator for @a reply_bf
1063  * @param peer_bf filter for peers not to select (again)
1064  */
1065 void
1066 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1067                            enum GNUNET_DHT_RouteOption options,
1068                            uint32_t desired_replication_level,
1069                            uint32_t hop_count, const struct GNUNET_HashCode * key,
1070                            const void *xquery, size_t xquery_size,
1071                            const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
1072                            uint32_t reply_bf_mutator,
1073                            struct GNUNET_CONTAINER_BloomFilter *peer_bf)
1074 {
1075
1076   /*
1077    1. take the key, get the 64 bit value of the key.
1078    2. call find_successor to get the successor of the key.
1079    3. successor can be either a friend or finger.
1080    4. update the field in get message to reflect if its a friend or finger table
1081    5. add the put message to pending message and send it.
1082    */
1083
1084 }
1085
1086 /**FIXME: Old implementation just to remove error.
1087  * TODO: Modify this function to handle our put request.
1088  * Perform a PUT operation.   Forwards the given request to other
1089  * peers.   Does not store the data locally.  Does not give the
1090  * data to local clients.  May do nothing if this is the only
1091  * peer in the network (or if we are the closest peer in the
1092  * network).
1093  *
1094  * @param type type of the block
1095  * @param options routing options
1096  * @param desired_replication_level desired replication count
1097  * @param expiration_time when does the content expire
1098  * @param hop_count how many hops has this message traversed so far
1099  * @param bf Bloom filter of peers this PUT has already traversed
1100  * @param key key for the content
1101  * @param put_path_length number of entries in @a put_path
1102  * @param put_path peers this request has traversed so far (if tracked)
1103  * @param data payload to store
1104  * @param data_size number of bytes in @a data
1105  */
1106 void
1107 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
1108                            enum GNUNET_DHT_RouteOption options,
1109                            uint32_t desired_replication_level,
1110                            struct GNUNET_TIME_Absolute expiration_time,
1111                            uint32_t hop_count,
1112                            struct GNUNET_CONTAINER_BloomFilter *bf,
1113                            const struct GNUNET_HashCode *key,
1114                            unsigned int put_path_length,
1115                            struct GNUNET_PeerIdentity *put_path,
1116                            const void *data, size_t data_size)
1117 {
1118
1119    /*
1120    1. take the key, get the 64 bit value of the key.
1121    2. call find_successor to get the successor of the key.
1122    3. successor can be either a friend or finger.
1123    4. update the field in put message to reflect if its a friend or finger table
1124    5. add the put message to pending message and send it.
1125    */
1126   /* SUPU: Call is made to this function from client. It does not seem to be
1127    waiting for a confirmation So, once we got the request, we use the key and
1128    try to find the closest successor, but in this case when we reach to the
1129    closest successor in handle_dht_p2p_put, then just do datacache_put. As the calling
1130    function does not need any confirmation, we don't need the result back. */
1131 }
1132
1133
1134 /**
1135  * Randomly choose one of your friends from the friends_peer map
1136  * @return Friend
1137  */
1138 static struct FriendInfo *
1139 select_random_friend()
1140 {
1141   unsigned int current_size;
1142   unsigned int *index;
1143   unsigned int j = 0;
1144   struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
1145   struct GNUNET_PeerIdentity key_ret;
1146   struct FriendInfo *friend;
1147
1148   current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap);
1149
1150   /* Element stored at this index in friend_peermap should be selected friend. */
1151   index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
1152
1153   /* Create an iterator for friend_peermap. */
1154   iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1155
1156   /* Set the position of iterator to index. */
1157   while(j < (*index))
1158   {
1159     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL))
1160     {
1161       j++;
1162     }
1163     else
1164       return NULL;
1165   }
1166
1167
1168   if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend))
1169   {
1170     return friend;
1171   }
1172
1173   return NULL;
1174 }
1175
1176
1177 /**
1178  * Compute finger_identity to which we want to setup the trail
1179  * @return finger_identity
1180  */
1181 static uint64_t *
1182 compute_finger_identity()
1183 {
1184   uint64_t my_id64 ;
1185   uint64_t *finger_identity64;
1186
1187   finger_identity64 = GNUNET_malloc (sizeof (uint64_t));
1188
1189   memcpy (&my_id64, &my_identity, sizeof (uint64_t));
1190
1191   /*FIXME: Do we need a mod finger = ((my_id + pow(2, finger_index)) mod (pow (2, MAX_FINGERS))*/
1192   *finger_identity64 = (my_id64 + (unsigned long) pow (2,current_finger_index));
1193
1194   return finger_identity64;
1195 }
1196
1197
1198 /**
1199  * Compute immediate predecessor identity in the network.
1200  * @return peer identity of immediate predecessor.
1201  */
1202 static uint64_t *
1203 compute_predecessor_identity()
1204 {
1205   uint64_t my_id ;
1206   uint64_t *predecessor;
1207
1208   predecessor = GNUNET_malloc (sizeof (uint64_t));
1209   memcpy (&my_id, &my_identity, sizeof (uint64_t));
1210   /* FIXME: Do we need to use mod pow(2, MAX_FINGERS) here? */
1211   *predecessor = (my_id -1);
1212
1213   return predecessor;
1214 }
1215
1216
1217 /**
1218  * Periodically ping your successor to ask its current predecessor
1219  *
1220  * @param cls closure for this task
1221  * @param tc the context under which the task is running
1222  */
1223 static void
1224 send_verify_successor_message (void *cls,
1225                                const struct GNUNET_SCHEDULER_TaskContext *tc )
1226 {
1227   struct GNUNET_TIME_Relative next_send_time;
1228   struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1229   struct GNUNET_PeerIdentity key_ret;
1230   struct FriendInfo *target_friend;
1231   struct GNUNET_PeerIdentity *next_hop;
1232   struct GNUNET_PeerIdentity *peer_list;
1233   unsigned int finger_trail_current_index;
1234   struct FingerInfo *finger;
1235   unsigned int finger_index;
1236   unsigned int i;
1237   int flag = 0;
1238   finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1239   for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1240   {
1241     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1242                                                                  (const void **)&finger))
1243     {
1244       if (0 == finger->finger_map_index)
1245       {
1246         flag = 1;
1247         break;
1248       }
1249     }
1250   }
1251   GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1252
1253   if( flag == 0)
1254     goto send_new_request;
1255
1256   peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->trail_length);
1257
1258   struct TrailPeerList *iterate;
1259   iterate = finger->head;
1260   i = 0;
1261   while ( i < (finger->trail_length))
1262   {
1263     memcpy (&peer_list[i], &(iterate->peer), sizeof (struct GNUNET_PeerIdentity));
1264     iterate = iterate->next;
1265     i++;
1266   }
1267
1268   next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1269   memcpy (next_hop, &peer_list[1], sizeof (struct GNUNET_PeerIdentity));
1270   target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1271   finger_trail_current_index = 2;
1272
1273   GDS_NEIGHBOURS_send_verify_successor (&my_identity,
1274                                         &(finger->finger_identity),
1275                                         target_friend,
1276                                         peer_list,
1277                                         finger->trail_length,
1278                                         finger_trail_current_index);
1279
1280
1281   /* FIXME: Use a random value so that this message is send not at the same
1282    interval as send_find_finger_trail_message. */
1283   send_new_request:
1284   next_send_time.rel_value_us =
1285       DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1286       GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1287                                 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1288                                 (current_finger_index + 50));
1289
1290   verify_successor =
1291       GNUNET_SCHEDULER_add_delayed (next_send_time, &send_verify_successor_message,
1292                                     NULL);
1293 }
1294
1295
1296 /**
1297  * Task to send a find finger trail message. We attempt to find trail
1298  * to our fingers, successor and predecessor in the network.
1299  *
1300  * @param cls closure for this task
1301  * @param tc the context under which the task is running
1302  */
1303 static void
1304 send_find_finger_trail_message (void *cls,
1305                                 const struct GNUNET_SCHEDULER_TaskContext *tc)
1306 {
1307   struct FriendInfo *target_friend;
1308   struct GNUNET_TIME_Relative next_send_time;
1309   struct GNUNET_PeerIdentity *peer_list;
1310   uint64_t *finger_identity;
1311   unsigned int finger_map_index;
1312
1313   if (1 == current_finger_index)
1314   {
1315     /* We have started the process to find the successor. We should search
1316      for our predecessor. */
1317     finger_identity = compute_predecessor_identity();
1318     goto select_friend;
1319   }
1320   else
1321   {
1322     finger_identity = compute_finger_identity();
1323   }
1324
1325   select_friend:
1326   target_friend = select_random_friend();
1327
1328
1329   finger_map_index = current_finger_index;
1330   current_finger_index = ( current_finger_index + 1) % MAX_FINGERS;
1331
1332   /* We found a friend.*/
1333   if(NULL != target_friend)
1334   {
1335     /* Add yourself and selected friend in the trail list. */
1336     unsigned int trail_length = 2;
1337     peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
1338     memcpy (&peer_list[0], &(my_identity), sizeof (struct GNUNET_PeerIdentity));
1339     memcpy (&peer_list[1], &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
1340
1341     GDS_NEIGHBOURS_send_trail_setup (&my_identity, *finger_identity, &(target_friend->id),
1342                                      target_friend, trail_length, peer_list,
1343                                      finger_map_index, FRIEND);
1344   }
1345
1346   /* FIXME: Should we be using current_finger_index to generate random interval.*/
1347   next_send_time.rel_value_us =
1348       DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1349       GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1350                                 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1351                                 (current_finger_index + 10));
1352
1353   find_finger_trail_task =
1354       GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1355                                     NULL);
1356 }
1357
1358
1359 /**
1360  * Method called whenever a peer connects.
1361  *
1362  * @param cls closure
1363  * @param peer_identity peer identity this notification is about
1364  */
1365 static void
1366 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer_identity)
1367 {
1368   struct FriendInfo *friend;
1369
1370   /* Check for connect to self message */
1371   if (0 == memcmp (&my_identity, peer_identity, sizeof (struct GNUNET_PeerIdentity)))
1372     return;
1373
1374   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connected to %s\n", GNUNET_i2s (peer_identity));
1375
1376   /* If peer already exists in our friend_peermap, then exit. */
1377   if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (friend_peermap, peer_identity))
1378   {
1379     GNUNET_break (0);
1380     return;
1381   }
1382
1383   GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
1384                             GNUNET_NO);
1385
1386   friend = GNUNET_new (struct FriendInfo);
1387   friend->id = *peer_identity;
1388
1389   GNUNET_assert (GNUNET_OK ==
1390                  GNUNET_CONTAINER_multipeermap_put (friend_peermap,
1391                                                     peer_identity, friend,
1392                                                     GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1393
1394   /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
1395   if (1 == GNUNET_CONTAINER_multipeermap_size (friend_peermap))
1396     find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
1397 }
1398
1399
1400 /**
1401  * Method called whenever a peer disconnects.
1402  *
1403  * @param cls closure
1404  * @param peer peer identity this notification is about
1405  */
1406 static void
1407 handle_core_disconnect (void *cls,
1408                         const struct GNUNET_PeerIdentity *peer)
1409 {
1410   struct FriendInfo *remove_friend;
1411   struct FingerInfo *remove_finger;
1412   struct GNUNET_PeerIdentity key_ret;
1413   struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1414   struct TrailPeerList *iterator;
1415   struct GNUNET_PeerIdentity *finger_identity;
1416   int finger_index;
1417
1418   /* Check for self message. */
1419   if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1420     return;
1421
1422    /* Search for peer to remove in your friend_peermap. */
1423   remove_friend =
1424       GNUNET_CONTAINER_multipeermap_get (friend_peermap, peer);
1425
1426   if (NULL == remove_friend)
1427   {
1428     GNUNET_break (0);
1429     return;
1430   }
1431
1432   iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
1433   finger_identity = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1434   finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1435   for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1436   {
1437     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1438                                                                  (const void **)&remove_finger))
1439     {
1440       iterator = remove_finger->head->next;
1441       if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(iterator->peer), &(remove_friend->id)))
1442       {
1443         memcpy (finger_identity, &(remove_finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
1444         GNUNET_assert (GNUNET_YES ==
1445                        GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
1446                                                              finger_identity,
1447                                                              remove_finger));
1448       }
1449     }
1450   }
1451
1452   /* Remove the friend from friend_peermap. */
1453   GNUNET_assert (GNUNET_YES ==
1454                  GNUNET_CONTAINER_multipeermap_remove (friend_peermap,
1455                                                        peer,
1456                                                        remove_friend));
1457 }
1458
1459
1460 /**
1461  * To be called on core init/fail.
1462  *
1463  * @param cls service closure
1464  * @param identity the public identity of this peer
1465  */
1466 static void
1467 core_init (void *cls,
1468            const struct GNUNET_PeerIdentity *identity)
1469 {
1470   my_identity = *identity;
1471
1472 }
1473
1474
1475 /**
1476  * Core handler for p2p put requests.
1477  *
1478  * @param cls closure
1479  * @param peer sender of the request
1480  * @param message message
1481  * @param peer peer identity this notification is about
1482  * @return #GNUNET_OK to keep the connection open,
1483  *         #GNUNET_SYSERR to close it (signal serious error)
1484  */
1485 static int
1486 handle_dht_p2p_put (void *cls,
1487                     const struct GNUNET_PeerIdentity *peer,
1488                     const struct GNUNET_MessageHeader *message)
1489 {
1490     /**
1491     1. Check if destination is friend or finger.
1492     2. If finger then get the next hop from routing table and
1493      * call GDS_NEGIHBOURS_handle_get.
1494     3. If friend then call find_successor to get the next hop and again
1495      * call GDS_NEIGHBOURS_handle_get to send to chosen hop.
1496      4. If you are the destination then do datacache_store.
1497      */
1498   return 0;
1499 }
1500
1501
1502 /**
1503  * Core handler for p2p get requests.
1504  *
1505  * @param cls closure
1506  * @param peer sender of the request
1507  * @param message message
1508  * @return #GNUNET_OK to keep the connection open,
1509  *         #GNUNET_SYSERR to close it (signal serious error)
1510  */
1511 static int
1512 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1513                     const struct GNUNET_MessageHeader *message)
1514 {
1515   /**
1516     1. Check if destination is friend or finger.
1517     2. If finger then get the next hop from routing table and
1518      * call GDS_NEGIHBOURS_handle_get.
1519     3. If friend then call find_successor to get the next hop and again
1520      * call GDS_NEIGHBOURS_handle_get to send to chosen hop.
1521      4. If you are the destination then send the data back to source peer
1522    * Assuming we have trail setup we can
1523    * either store the whole trail or again do the search process..
1524      */
1525   return 0;
1526 }
1527
1528
1529 /**
1530  * FIXME: When we add a successor or predecessor should we check the entry in
1531  * finger map index. If we don't replace the old entry then should we notify
1532  * peer which think it is our predecessor or successor. Or will send verify
1533  * successor message will handle this case on its own.
1534  * * FIXME: For redundant routing, we may start looking for different
1535  * paths to reach to same finger. So, in send_find_finger, we are starting
1536  * the search for trail to a finger, even if we already have found trail to
1537  * reach to it. There are several reasons for doing so
1538  * 1. We may reach to a closer successor than we have at the moment. So, we
1539  * should keep looking for the successor.
1540  * 2. We may reach to the same successor but through a shorter path.
1541  * 3. As I don't know how keys are distributed and how put/get will react
1542  * because of this, I have to think further before implementing it.
1543  * Add an entry in finger table.
1544  * Add an entry into finger table
1545  * @param finger_identity Peer identity of finger
1546  * @param finger_trail Trail to reach the finger
1547  * @param trail_length Number of peers in the trail.
1548  * @param finger_map_index Index in finger peer map.
1549  */
1550 static
1551 void finger_table_add (struct GNUNET_PeerIdentity *finger_identity,
1552                        struct GNUNET_PeerIdentity *finger_trail,
1553                        unsigned int trail_length,
1554                        unsigned int finger_map_index)
1555 {
1556   struct FingerInfo *new_finger_entry;
1557   struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1558   struct GNUNET_PeerIdentity key_ret;
1559   struct FingerInfo *existing_finger;
1560   int finger_index;
1561   int i;
1562
1563   finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1564
1565   for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1566   {
1567     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter, &key_ret,
1568                                                                  (const void **)&existing_finger))
1569     {
1570       /* If we already have an entry at the finger map index. */
1571       if ((finger_map_index == existing_finger->finger_map_index))
1572       {
1573         /* Check if the finger entry are same. */
1574         if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),finger_identity))
1575         {
1576           /* Compare the trail length. */
1577           if ((trail_length == existing_finger->trail_length)||
1578              (trail_length > existing_finger->trail_length))
1579           {
1580             return;
1581           }
1582           else if (trail_length < existing_finger->trail_length)
1583           {
1584             /* FIXME: As an optimization, when you add limit on trail length
1585             going through a particular friend, then check if the friend to
1586             reach the two trails are same or not. If not then choose one
1587             whose threshold value has not yet reached. Also, think about
1588             redundant routing, where you want to keep multiple paths
1589             to reach to the same finger. In that case you should allow multiple
1590             entries with same finger identity. */
1591             if ( GNUNET_YES == GNUNET_CONTAINER_multipeermap_remove (finger_peermap,
1592                                                  &(existing_finger->finger_identity),
1593                                                  existing_finger))
1594             {
1595               goto add_new_entry;
1596             }
1597           }
1598         }
1599         else
1600         {
1601           /* FIXME: Here you are if you got different finger identity then one
1602            you already have at that index. Then you should choose the
1603            one which is closest. */
1604         }
1605       }
1606     }
1607   }
1608
1609   add_new_entry:
1610   new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
1611   memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity));
1612
1613   i = 0;
1614   while (i < trail_length)
1615   {
1616     struct TrailPeerList *element;
1617     element = GNUNET_malloc (sizeof (struct TrailPeerList));
1618     element->next = NULL;
1619     element->prev = NULL;
1620
1621     memcpy (&(element->peer), &finger_trail[i], sizeof(struct GNUNET_PeerIdentity));
1622     GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head, new_finger_entry->tail, element);
1623     i++;
1624   }
1625
1626   new_finger_entry->finger_map_index = finger_map_index;
1627   new_finger_entry->trail_length = trail_length;
1628
1629   /* FIXME: Here we are keeping multiple hashmap option so that there are
1630    multiple routes to reach to same finger, redundant routing. */
1631   GNUNET_assert (GNUNET_OK ==
1632                  GNUNET_CONTAINER_multipeermap_put (finger_peermap,
1633                                                     &(new_finger_entry->finger_identity),
1634                                                     new_finger_entry,
1635                                                     GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
1636
1637   if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap)
1638       && (new_finger_entry->finger_map_index!= 1))
1639   {
1640     verify_successor = GNUNET_SCHEDULER_add_now (&send_verify_successor_message, NULL);
1641   }
1642 }
1643
1644
1645 /**
1646  * Compare two peer identities.
1647  * @param p1 Peer identity
1648  * @param p2 Peer identity
1649  * @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
1650  */
1651   static int
1652 compare_peer_id (const void *p1, const void *p2)
1653 {
1654   struct Sorting_List *p11;
1655   struct Sorting_List *p22;
1656   int ret;
1657   p11 = GNUNET_malloc (sizeof (struct Sorting_List));
1658   p22 = GNUNET_malloc (sizeof (struct Sorting_List));
1659   p11 = (struct Sorting_List *)p1;
1660   p22 = (struct Sorting_List *)p2;
1661   ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
1662           ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
1663   return ret;
1664 }
1665
1666
1667 /**
1668  * Return the previous element of value in all_known_peers.
1669  * @param all_known_peers list of all the peers
1670  * @param value value we have to search in the all_known_peers.
1671  * @return
1672  */
1673 static struct Sorting_List *
1674 find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
1675                        unsigned int size)
1676 {
1677   int first;
1678   int last;
1679   int middle;
1680
1681   first = 0;
1682   last = size - 1;
1683   middle = (first + last)/2;
1684
1685   while(first <= last)
1686   {
1687     if(all_known_peers[middle].peer_id < value)
1688     {
1689       first = middle + 1;
1690     }
1691     else if(all_known_peers[middle].peer_id == value)
1692     {
1693       if(middle == (size -1))
1694       {
1695         return &all_known_peers[0];
1696       }
1697       else
1698       {
1699         return &all_known_peers[middle+1];
1700       }
1701     }
1702     else
1703     {
1704        last = middle - 1;
1705     }
1706
1707     middle = (first + last)/2;
1708   }
1709   return NULL;
1710 }
1711
1712
1713 /**
1714  * Find closest successor for the value.
1715  * @param value Value for which we are looking for successor
1716  * @param current_destination NULL if my_identity is successor else finger/friend
1717  *                            identity
1718  * @param type Next destination type
1719  * @return Peer identity of next destination i.e. successor of value.
1720  */
1721 static struct GNUNET_PeerIdentity *
1722 find_successor(uint64_t value, struct GNUNET_PeerIdentity *current_destination,
1723                enum current_destination_type *type)
1724 {
1725   struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1726   struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1727   struct GNUNET_PeerIdentity key_ret;
1728   struct FriendInfo *friend;
1729   struct FingerInfo *finger;
1730   unsigned int finger_index;
1731   unsigned int friend_index;
1732   struct Sorting_List *successor;
1733   unsigned int size;
1734   int j;
1735
1736   /* 2 is added in size for my_identity and value which will part of all_known_peers. */
1737   size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
1738          GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
1739          2;
1740
1741   struct Sorting_List all_known_peers[size];
1742
1743   int k;
1744   for (k = 0; k < size; k++)
1745     all_known_peers[k].peer_id = 0;
1746
1747   /* Copy your identity at 0th index in all_known_peers. */
1748   j = 0;
1749   memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
1750   all_known_peers[j].type = MY_ID;
1751   all_known_peers[j].data = 0;
1752   j++;
1753
1754   /* Copy value */
1755   all_known_peers[j].peer_id = value;
1756   all_known_peers[j].type = VALUE;
1757   all_known_peers[j].data = 0;
1758   j++;
1759
1760   /* Iterate over friend peer map and copy all the elements into array. */
1761   friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1762   for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
1763   {
1764     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1765     {
1766       memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
1767       all_known_peers[j].type = FRIEND;
1768       all_known_peers[j].data = friend;
1769       j++;
1770     }
1771   }
1772
1773   /* Iterate over finger map and copy all the entries into all_known_peers array. */
1774   finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1775   for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1776   {
1777     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1778     {
1779       memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity), sizeof (uint64_t));
1780       all_known_peers[j].type = FINGER;
1781       all_known_peers[j].data = finger;
1782       j++;
1783     }
1784   }
1785
1786   GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
1787   GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
1788
1789   qsort (&all_known_peers, size, sizeof (struct Sorting_List), &compare_peer_id);
1790
1791   /* search value in all_known_peers array. */
1792   successor = find_closest_successor (all_known_peers, value, size);
1793
1794   if (successor->type == MY_ID)
1795   {
1796     *type = MY_ID;
1797     return NULL;
1798   }
1799   else if (successor->type == FRIEND)
1800   {
1801     *type = FRIEND;
1802     struct FriendInfo *target_friend;
1803     target_friend = (struct FriendInfo *)successor->data;
1804     memcpy (current_destination, &(target_friend->id), sizeof (struct GNUNET_PeerIdentity));
1805     return current_destination;
1806   }
1807   else if (successor->type == FINGER)
1808   {
1809     *type = FINGER;
1810     struct GNUNET_PeerIdentity *next_hop;
1811     struct FingerInfo *finger;
1812     struct TrailPeerList *iterator;
1813     iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
1814     finger = successor->data;
1815     iterator = finger->head->next;
1816     next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1817     memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
1818     memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity));
1819     return next_hop;
1820   }
1821   else
1822   {
1823    type = NULL;
1824    return NULL;
1825   }
1826 }
1827
1828
1829 /**
1830  * Handle a PeerTrailSetupMessage.
1831  * @param cls closure
1832  * @param message message
1833  * @param peer peer identity this notification is about
1834  * @return GNUNET_OK on success, GNUNET_SYSERR on error
1835  */
1836 static int
1837 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1838                            const struct GNUNET_MessageHeader *message)
1839 {
1840   struct PeerTrailSetupMessage *trail_setup;
1841   struct GNUNET_PeerIdentity *next_hop;
1842   struct FriendInfo *target_friend;
1843   struct GNUNET_PeerIdentity *current_destination;
1844   struct GNUNET_PeerIdentity *next_peer;
1845   struct GNUNET_PeerIdentity *trail_peer_list;
1846   enum current_destination_type peer_type;
1847   unsigned int trail_length;
1848   uint32_t current_trail_index;
1849   unsigned int finger_map_index;
1850   uint64_t finger_value;
1851   size_t msize;
1852
1853   /* parse and validate message. */
1854   msize = ntohs (message->size);
1855   if (msize < sizeof (struct PeerTrailSetupMessage))
1856   {
1857     GNUNET_break_op (0);
1858     return GNUNET_YES;
1859   }
1860
1861   trail_setup = (struct PeerTrailSetupMessage *) message;
1862   trail_length = ntohl (trail_setup->trail_length);
1863
1864   if ((msize <
1865        sizeof (struct PeerTrailSetupMessage) +
1866        trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1867        (trail_length >
1868         GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1869   {
1870     GNUNET_break_op (0);
1871     return GNUNET_YES;
1872   }
1873
1874   peer_type = ntohl (trail_setup->current_destination_type);
1875   finger_map_index = ntohl (trail_setup->finger_map_index);
1876   trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_setup[1];
1877   finger_value = trail_setup->destination_finger;
1878   current_destination = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1879   memcpy (current_destination, &(trail_setup->current_destination), sizeof (struct GNUNET_PeerIdentity));
1880
1881   if (peer_type == FRIEND)
1882   {
1883     if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
1884                                                &my_identity)))
1885     {
1886       next_hop = find_successor (finger_value, current_destination, &(peer_type));
1887     }
1888     else
1889       return GNUNET_SYSERR;
1890   }
1891   else if (peer_type == FINGER)
1892   {
1893     if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination),
1894                                                &my_identity)))
1895     {
1896       next_hop = GDS_ROUTING_search (&(trail_setup->source_peer),
1897                                      &(trail_setup->current_destination));
1898
1899       #if 0
1900       /* This is an optimization. Uncomment when basic code is running first. */
1901       /* I am part of trail.*/
1902       struct GNUNET_PeerIdentity *next_peer_routing_table;
1903       next_peer_routing_table = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1904       next_peer_routing_table = GDS_ROUTING_search (&(trail_setup->source_peer),
1905                                      &(trail_setup->current_destination));
1906
1907       struct GNUNET_PeerIdentity *next_peer_find_successor;
1908       next_peer_find_successor = find_successor (&(trail_setup->destination_finger),
1909                                            &(trail_setup->current_destination),
1910                                            &(peer_type));
1911
1912       next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1913       next_hop = find_closest_destination (next_peer_routing_table,
1914                                            next_peer_find_successor,
1915                                            &(trail_setup->destination_finger) );
1916       #endif
1917     }
1918     else
1919     {
1920       /* I am the current_destination finger */
1921       next_hop = find_successor (finger_value, current_destination, &(peer_type));
1922     }
1923   }
1924
1925   /* If you are the next hop, then you are the final destination */
1926   if (peer_type == MY_ID)
1927   {
1928     struct GNUNET_PeerIdentity *source;
1929     source = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1930     memcpy (source, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity));
1931     current_trail_index = trail_length - 2;
1932     next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1933     memcpy (next_peer, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
1934     target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
1935     GNUNET_free (next_peer);
1936
1937     if(current_trail_index != 0)
1938       current_trail_index = current_trail_index - 1;
1939
1940     if (0 == trail_setup->finger_map_index)
1941     {
1942       struct GNUNET_PeerIdentity *new_trail;
1943       int i;
1944       int j;
1945
1946       i = trail_length - 1;
1947       j = 0;
1948       new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
1949                                    trail_length);
1950       while (i > 0)
1951       {
1952         memcpy( &new_trail[j], &trail_peer_list[i], sizeof (struct GNUNET_PeerIdentity));
1953         i--;
1954         j++;
1955       }
1956       memcpy (&new_trail[j], &trail_peer_list[i], sizeof(struct GNUNET_PeerIdentity));
1957       finger_table_add (source, new_trail, trail_length, 1);
1958     }
1959
1960     GDS_NEIGHBOURS_send_trail_setup_result (&(trail_setup->source_peer),
1961                                             &(my_identity),
1962                                             target_friend, trail_length,
1963                                             trail_peer_list, current_trail_index,
1964                                             finger_map_index);
1965
1966     return GNUNET_YES;
1967   }
1968
1969   /* Add next hop to list of peers. */
1970   struct GNUNET_PeerIdentity *peer_list;
1971   peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length + 1));
1972   memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1973   memcpy (&peer_list[trail_length], next_hop, sizeof (struct GNUNET_PeerIdentity));
1974   trail_length++;
1975
1976   target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1977
1978   if(peer_type == FINGER)
1979   {
1980     GDS_ROUTING_add (&(trail_setup->source_peer),
1981                      &(trail_setup->current_destination),
1982                      next_hop);
1983   }
1984
1985   GDS_NEIGHBOURS_send_trail_setup (&(trail_setup->source_peer),
1986                                    trail_setup->destination_finger,
1987                                    current_destination, target_friend, trail_length,
1988                                    peer_list, finger_map_index, peer_type);
1989
1990 return GNUNET_YES;
1991 }
1992
1993
1994 /**
1995  * Core handle for p2p trail construction result messages.
1996  * @param cls closure
1997  * @param message message
1998  * @param peer peer identity this notification is about
1999  * @return GNUNET_OK on success, GNUNET_SYSERR on error
2000  */
2001 static int
2002 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2003                                   const struct GNUNET_MessageHeader *message)
2004 {
2005   struct PeerTrailSetupResultMessage *trail_result;
2006   struct GNUNET_PeerIdentity *trail_peer_list;
2007   struct GNUNET_PeerIdentity *next_peer;
2008   struct FriendInfo *target_friend;
2009   unsigned int current_trail_index;
2010   unsigned int finger_map_index;
2011   unsigned int trail_length;
2012   size_t msize;
2013
2014   msize = ntohs (message->size);
2015   if (msize < sizeof (struct PeerTrailSetupResultMessage))
2016   {
2017     GNUNET_break_op (0);
2018     return GNUNET_YES;
2019   }
2020
2021   trail_result = (struct PeerTrailSetupResultMessage *) message;
2022   trail_length = ntohl (trail_result->trail_length);
2023
2024   if ((msize <
2025        sizeof (struct PeerTrailSetupResultMessage) +
2026        trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2027        (trail_length >
2028         GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2029   {
2030     GNUNET_break_op (0);
2031     return GNUNET_YES;
2032   }
2033
2034   current_trail_index = ntohl (trail_result->current_index);
2035   finger_map_index = ntohl (trail_result->finger_map_index);
2036
2037   trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
2038
2039   if ( 0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer),
2040                                                 &my_identity)))
2041   {
2042     #if 0
2043       /* SUPU: Here I have removed myself from the trail before storing it in
2044        th finger table - to save space, but in case of verify successor result
2045        the result trail does not contain me, and I will never get the message back.
2046        So, keeping myself in the trail list. Think of better solution.*/
2047       struct GNUNET_PeerIdentity *finger_trail;
2048       finger_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - 1));
2049
2050       /* Copy the whole trail_peer_list except the first element into trail */
2051       unsigned int i;
2052       i = trail_length - 1;
2053       while (i > 0)
2054       {
2055         memcpy (&finger_trail[i], &trail_peer_list[i], sizeof (struct GNUNET_PeerIdentity));
2056         i--;
2057       }
2058       trail_length = trail_length -1 ; SUPU: As you removed yourself from the trail.*/
2059     #endif
2060
2061     finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length,
2062                       finger_map_index);
2063
2064     return GNUNET_YES;
2065   }
2066   else
2067   {
2068     next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2069     memcpy (next_peer, &(trail_peer_list[current_trail_index]),
2070             sizeof (struct GNUNET_PeerIdentity));
2071     /* SUPU: here current trail index will always be greater than 0.
2072        so no need for this check here. trail index = 0, contains the final
2073        destination, and if we are in this loop we have not yet reached the
2074        final destination. */
2075     current_trail_index = current_trail_index - 1;
2076
2077     target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
2078     GNUNET_free (next_peer);
2079
2080     GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer),
2081                                             &(trail_result->finger_identity),
2082                                             target_friend, trail_length,
2083                                             trail_peer_list,current_trail_index,
2084                                             finger_map_index);
2085       return GNUNET_YES;
2086     }
2087
2088   return GNUNET_SYSERR;
2089 }
2090
2091
2092 /**
2093  * Core handle for p2p verify successor messages.
2094  * @param cls closure
2095  * @param message message
2096  * @param peer peer identity this notification is about
2097  * @return GNUNET_OK on success, GNUNET_SYSERR on error
2098  */
2099 static int
2100 handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2101                                 const struct GNUNET_MessageHeader *message)
2102 {
2103   struct PeerVerifySuccessorMessage *vsm;
2104   struct GNUNET_PeerIdentity *trail_peer_list;
2105   struct FriendInfo *target_friend;
2106   struct GNUNET_PeerIdentity *next_hop;
2107   struct GNUNET_PeerIdentity *source_peer;
2108   unsigned int trail_length;
2109   unsigned int current_trail_index;
2110   size_t msize;
2111
2112   msize = ntohs (message->size);
2113   if (msize < sizeof (struct PeerVerifySuccessorMessage))
2114   {
2115     GNUNET_break_op (0);
2116     return GNUNET_YES;
2117   }
2118
2119   vsm = (struct PeerVerifySuccessorMessage *) message;
2120   trail_length = ntohl (vsm->trail_length);
2121
2122   if ((msize <
2123        sizeof (struct PeerVerifySuccessorMessage) +
2124        trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2125        (trail_length >
2126        GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2127        {
2128          GNUNET_break_op (0);
2129          return GNUNET_YES;
2130        }
2131
2132   current_trail_index = ntohl (vsm->current_trail_index);
2133   trail_peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
2134   source_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2135   memcpy (source_peer, &(vsm->source_peer), sizeof (struct GNUNET_PeerIdentity));
2136
2137   next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2138
2139   /* SUPU: If I am the destination. */
2140   if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),
2141                                             &my_identity)))
2142   {
2143     struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
2144     struct GNUNET_PeerIdentity key_ret;
2145     unsigned int finger_index;
2146     struct FingerInfo *my_predecessor;
2147     struct GNUNET_PeerIdentity *destination_peer;
2148
2149     /* Iterate over finger peer map and extract your predecessor. */
2150     finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
2151     for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
2152     {
2153       if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next
2154                        (finger_iter,&key_ret,(const void **)&my_predecessor))
2155       {
2156         if(1 == my_predecessor->finger_map_index)
2157         {
2158           break;
2159         }
2160       }
2161     }
2162     GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
2163
2164     destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2165     memcpy (destination_peer, source_peer, sizeof (struct GNUNET_PeerIdentity));
2166     current_trail_index = trail_length - 2;
2167     memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2168     target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2169     GNUNET_free (next_hop);
2170
2171     if (current_trail_index != 0)
2172     current_trail_index = current_trail_index - 1;
2173
2174     /*SUPU: Remove this later*/
2175     struct GNUNET_PeerIdentity *predecessor;
2176     predecessor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2177     if (NULL == my_predecessor)
2178     {
2179       /* FIXME: Ideally my_predecessor should not be NULL. If some one sent
2180        me a request to verify it I am the successor or not, then I would have
2181        added that peer to my_predecessor list. Check trail setup and see if
2182        you are adding predecessor when you get the request for successor. */
2183 #if 0
2184       update_predecessor (source_peer, trail_peer_list, trail_length);
2185
2186       GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
2187                                                    &(my_identity),
2188                                                    source_peer,
2189                                                    target_friend,
2190                                                    trail_peer_list,
2191                                                    trail_length,
2192                                                    current_trail_index);
2193 #endif
2194     }
2195     else
2196     {
2197       /* FIXME: some times my_predecssor->finger_identity has no valid value.
2198        Check why?*/
2199       memcpy (predecessor, &(my_predecessor->finger_identity), sizeof (struct GNUNET_PeerIdentity));
2200     }
2201
2202     if (0 == (GNUNET_CRYPTO_cmp_peer_identity (source_peer,
2203                                                &(my_predecessor->finger_identity))))
2204     {
2205         /* SUPU: If source peer is my predecessor .*/
2206       GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
2207                                                   &(my_identity),
2208                                                   &(my_predecessor->finger_identity),
2209                                                   target_friend,
2210                                                   trail_peer_list,
2211                                                   trail_length,
2212                                                   current_trail_index);
2213     }
2214     else
2215     {
2216       struct GNUNET_PeerIdentity *new_successor_trail;
2217       int new_trail_length;
2218       int i;
2219
2220       new_trail_length = trail_length + my_predecessor->trail_length - 1;
2221       new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
2222                                            * new_trail_length);
2223
2224       /* Copy the trail from source peer to me. */
2225       memcpy (new_successor_trail, trail_peer_list,
2226               (trail_length) * sizeof (struct GNUNET_PeerIdentity));
2227
2228       /* Copy the trail from me to my predecessor excluding me. */
2229       struct TrailPeerList *iterator;
2230       iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
2231       iterator = my_predecessor->head->next;
2232       i = trail_length;
2233       while (i < new_trail_length)
2234       {
2235         memcpy (&new_successor_trail[i], &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
2236         iterator = iterator->next;
2237         i++;
2238       }
2239
2240       GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
2241                                                     &(my_identity),
2242                                                     &(my_predecessor->finger_identity),
2243                                                     target_friend,
2244                                                     new_successor_trail,
2245                                                     new_trail_length,
2246                                                     current_trail_index);
2247     }
2248
2249   }
2250   else
2251   {
2252     /* If I am not the destination. */
2253     memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2254     target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2255     GNUNET_free (next_hop);
2256
2257     current_trail_index = current_trail_index + 1;
2258
2259     GDS_NEIGHBOURS_send_verify_successor(source_peer, &(vsm->successor),target_friend,
2260                                          trail_peer_list, trail_length, current_trail_index);
2261   }
2262   return GNUNET_YES;
2263 }
2264
2265
2266 /**
2267  * Core handle for p2p notify new successor messages.
2268  * @param cls closure
2269  * @param message message
2270  * @param peer peer identity this notification is about
2271  * @return GNUNET_OK on success, GNUNET_SYSERR on error
2272  */
2273 static int
2274 handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity *peer,
2275                                     const struct GNUNET_MessageHeader *message)
2276 {
2277   struct PeerNotifyNewSuccessorMessage *nsm;
2278   struct GNUNET_PeerIdentity *trail_peer_list;
2279   unsigned int current_trail_index;
2280   size_t msize;
2281   unsigned int trail_length;
2282
2283   msize = ntohs (message->size);
2284   if (msize < sizeof (struct PeerNotifyNewSuccessorMessage))
2285   {
2286     GNUNET_break_op (0);
2287     return GNUNET_YES;
2288   }
2289
2290   nsm = (struct PeerNotifyNewSuccessorMessage *) message;
2291   trail_length = ntohl (nsm->trail_length);
2292
2293   if ((msize <
2294        sizeof (struct PeerNotifyNewSuccessorMessage) +
2295        trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2296        (trail_length >
2297        GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2298   {
2299     GNUNET_break_op (0);
2300     return GNUNET_YES;
2301   }
2302
2303   current_trail_index = ntohl (nsm->current_index);
2304   trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
2305
2306   if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer),
2307                                             &my_identity)))
2308   {
2309     struct GNUNET_PeerIdentity *new_trail;
2310     int i;
2311     int j;
2312
2313     i = trail_length - 1;
2314     j = 0;
2315     new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
2316                                    trail_length);
2317     while (i > 0)
2318     {
2319       memcpy( &new_trail[j], &trail_peer_list[i], sizeof (struct GNUNET_PeerIdentity));
2320       i--;
2321       j++;
2322     }
2323     memcpy (&new_trail[j], &trail_peer_list[i], sizeof(struct GNUNET_PeerIdentity));
2324     finger_table_add (&(nsm->source_peer), new_trail, trail_length, 1);
2325
2326     return GNUNET_YES;
2327   }
2328   else
2329   {
2330     struct FriendInfo *target_friend;
2331     target_friend = GNUNET_malloc (sizeof (struct FriendInfo));
2332     struct GNUNET_PeerIdentity *next_hop;
2333     next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2334     memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2335     target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2336     GNUNET_free (next_hop);
2337     current_trail_index = current_trail_index + 1;
2338
2339     GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
2340                                               &(nsm->destination_peer),
2341                                               target_friend, trail_peer_list,
2342                                               trail_length, current_trail_index);
2343   }
2344   return GNUNET_YES;
2345 }
2346
2347
2348 /**
2349  * Core handle for p2p verify successor result messages.
2350  * @param cls closure
2351  * @param message message
2352  * @param peer peer identity this notification is about
2353  * @return GNUNET_OK on success, GNUNET_SYSERR on error
2354  */
2355 static int
2356 handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdentity *peer,
2357                                        const struct GNUNET_MessageHeader *message)
2358 {
2359   struct PeerVerifySuccessorResultMessage *vsrm;
2360   struct FriendInfo *target_friend;
2361   struct GNUNET_PeerIdentity *trail_peer_list;
2362   struct GNUNET_PeerIdentity *next_hop;
2363   unsigned int trail_length;
2364   unsigned int current_trail_index;
2365   size_t msize;
2366
2367   msize = ntohs (message->size);
2368   if (msize < sizeof (struct PeerVerifySuccessorResultMessage))
2369   {
2370     GNUNET_break_op (0);
2371     return GNUNET_YES;
2372   }
2373
2374   vsrm = (struct PeerVerifySuccessorResultMessage *) message;
2375   trail_length = ntohl (vsrm->trail_length);
2376
2377   if ((msize <
2378        sizeof (struct PeerVerifySuccessorResultMessage) +
2379        trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
2380        (trail_length >
2381        GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2382   {
2383     GNUNET_break_op (0);
2384     return GNUNET_YES;
2385   }
2386
2387   current_trail_index = ntohl (vsrm->current_index);
2388   trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1];
2389
2390   if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer),
2391                                             &(my_identity))))
2392   {
2393     if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor),
2394                                               &(my_identity))))
2395     {
2396       finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0);
2397       next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2398       memcpy (next_hop, &trail_peer_list[1], sizeof (struct GNUNET_PeerIdentity));
2399       target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2400       current_trail_index = 2;
2401       GNUNET_free (next_hop);
2402
2403       GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor),
2404                                                 target_friend, trail_peer_list,
2405                                                 trail_length, current_trail_index);
2406     }
2407   }
2408   else
2409   {
2410     next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
2411     memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
2412     target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
2413     GNUNET_free (next_hop);
2414     current_trail_index = current_trail_index - 1;
2415
2416     GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
2417                                                  &(vsrm->source_successor),
2418                                                  &(vsrm->my_predecessor),
2419                                                  target_friend,
2420                                                  trail_peer_list,
2421                                                  trail_length,
2422                                                  current_trail_index);
2423   }
2424   return GNUNET_YES;
2425 }
2426
2427
2428 /**
2429  * Initialize neighbours subsystem.
2430  * @return GNUNET_OK on success, GNUNET_SYSERR on error
2431  */
2432 int
2433 GDS_NEIGHBOURS_init()
2434 {
2435   static struct GNUNET_CORE_MessageHandler core_handlers[] = {
2436     {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
2437     {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
2438     {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
2439     {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
2440     {&handle_dht_p2p_verify_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR, 0},
2441     {&handle_dht_p2p_verify_successor_result, GNUNET_MESSAGE_TYPE_DHT_P2P_VERIFY_SUCCESSOR_RESULT, 0},
2442     {&handle_dht_p2p_notify_new_successor, GNUNET_MESSAGE_TYPE_DHT_P2P_NOTIFY_NEW_SUCCESSOR, 0},
2443     {NULL, 0, 0}
2444   };
2445
2446
2447   /*TODO: What is ATS? Why do we need it? */
2448   atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
2449   core_api =
2450     GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
2451                          &handle_core_disconnect, NULL, GNUNET_NO, NULL,
2452                          GNUNET_NO, core_handlers);
2453   if (NULL == core_api)
2454     return GNUNET_SYSERR;
2455
2456   friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
2457   finger_peermap = GNUNET_CONTAINER_multipeermap_create (MAX_FINGERS, GNUNET_NO);
2458
2459   return GNUNET_OK;
2460 }
2461
2462
2463 /**
2464  * Shutdown neighbours subsystem.
2465  */
2466 void
2467 GDS_NEIGHBOURS_done ()
2468 {
2469   if (NULL == core_api)
2470     return;
2471
2472   GNUNET_CORE_disconnect (core_api);
2473   core_api = NULL;
2474   GNUNET_ATS_performance_done (atsAPI);
2475   atsAPI = NULL;
2476
2477   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
2478   GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
2479   friend_peermap = NULL;
2480
2481
2482   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
2483   GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
2484   finger_peermap = NULL;
2485
2486   if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
2487   {
2488     GNUNET_SCHEDULER_cancel (find_finger_trail_task);
2489     find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
2490   }
2491
2492
2493   if (GNUNET_SCHEDULER_NO_TASK != verify_successor)
2494   {
2495     GNUNET_SCHEDULER_cancel (verify_successor);
2496     verify_successor = GNUNET_SCHEDULER_NO_TASK;
2497   }
2498
2499 }
2500
2501
2502 /**
2503  * Get the ID of the local node.
2504  *
2505  * @return identity of the local node
2506  */
2507 struct GNUNET_PeerIdentity *
2508 GDS_NEIGHBOURS_get_id ()
2509 {
2510   return &my_identity;
2511 }
2512
2513
2514 /* end of gnunet-service-xdht_neighbours.c */