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
  52 /* FIXME:
  53  1. Add content and route replication later.
  54  *2. Algorithm to shorten the trail length - one possible solution could be
  55  * when we are in trail seutp result part. each peer in the trail check if any of
  56  * the corresponding peers is its friend list. Then it can shortcut the path.
  57  * But this will have O(n) run time at each peer, where n = trail_length.\
  58  * or rather O(n)+O(n-1)+..O(1) =O(n).
  59  * 3. Add a new field finger index to keep track of which finger respongs to which
  60  * entry.
  61  * 4. As we start looking for finger from i = 0, using this parameter to
  62  * generate random value does not look smart in send_find_finger_trail_message.
  63  * 5. Need to store the interval in finger and friend table which will be used
  64  * to find the correct successor.
  65  */
  66
  67
  68 /**
  69  * Maximum possible fingers of a peer.
  70  */
  71 #define MAX_FINGERS 256
  72
  73 /**
  74  * Maximum allowed number of pending messages per friend peer.
  75  */
  76 #define MAXIMUM_PENDING_PER_FRIEND 64
  77
  78 /**
  79  * How long at least to wait before sending another find finger trail request.
  80  */
  81 #define DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30)
  82
  83 /**
  84  * How long at most to wait before sending another find finger trail request.
  85  */
  86 #define DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 10)
  87
  88 /**
  89  * FIXME: Currently used in GDS_NEIGHBOURS_handle_trail_setup.
  90  * I have just copied it from gnunet-service-dht_neighbours. Will it work here?
  91  * How long at most to wait for transmission of a GET request to another peer?
  92  */
  93 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
  94
  95 GNUNET_NETWORK_STRUCT_BEGIN
  96
  97 /* FIXME:
  98  * 1) Bloomfilter is not required for X-Vine.
  99  * Keep the field now but remove it when implementing PUT/GET.
 100  * 2) also, check the field of put/get/result if all are required for
 101  * x-vine or not. */
 102
 103 /**
 104  * P2P PUT message
 105  */
 106 struct PeerPutMessage
 107 {
 108   /**
 109    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
 110    */
 111   struct GNUNET_MessageHeader header;
 112
 113   /**
 114    * Processing options
 115    */
 116   uint32_t options GNUNET_PACKED;
 117
 118   /**
 119    * Content type.
 120    */
 121   uint32_t type GNUNET_PACKED;
 122
 123   /**
 124    * Hop count
 125    */
 126   uint32_t hop_count GNUNET_PACKED;
 127
 128   /**
 129    * Replication level for this message
 130    */
 131   uint32_t desired_replication_level GNUNET_PACKED;
 132
 133   /**
 134    * Length of the PUT path that follows (if tracked).
 135    */
 136   uint32_t put_path_length GNUNET_PACKED;
 137
 138   /**
 139    * When does the content expire?
 140    */
 141   struct GNUNET_TIME_AbsoluteNBO expiration_time;
 142
 143   /**
 144    * Bloomfilter (for peer identities) to stop circular routes
 145    */
 146   char bloomfilter[DHT_BLOOM_SIZE];
 147
 148   /**
 149    * The key we are storing under.
 150    */
 151   struct GNUNET_HashCode key;
 152
 153   /* put path (if tracked) */
 154
 155   /* Payload */
 156
 157 };
 158
 159
 160 /**
 161  * P2P Result message
 162  */
 163 struct PeerResultMessage
 164 {
 165   /**
 166    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
 167    */
 168   struct GNUNET_MessageHeader header;
 169
 170   /**
 171    * Content type.
 172    */
 173   uint32_t type GNUNET_PACKED;
 174
 175   /**
 176    * Length of the PUT path that follows (if tracked).
 177    */
 178   uint32_t put_path_length GNUNET_PACKED;
 179
 180   /**
 181    * Length of the GET path that follows (if tracked).
 182    */
 183   uint32_t get_path_length GNUNET_PACKED;
 184
 185   /**
 186    * When does the content expire?
 187    */
 188   struct GNUNET_TIME_AbsoluteNBO expiration_time;
 189
 190   /**
 191    * The key of the corresponding GET request.
 192    */
 193   struct GNUNET_HashCode key;
 194
 195   /* put path (if tracked) */
 196
 197   /* get path (if tracked) */
 198
 199   /* Payload */
 200
 201 };
 202
 203
 204 /**
 205  * P2P GET message
 206  */
 207 struct PeerGetMessage
 208 {
 209   /**
 210    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
 211    */
 212   struct GNUNET_MessageHeader header;
 213
 214   /**
 215    * Processing options
 216    */
 217   uint32_t options GNUNET_PACKED;
 218
 219   /**
 220    * Desired content type.
 221    */
 222   uint32_t type GNUNET_PACKED;
 223
 224   /**
 225    * Hop count
 226    */
 227   uint32_t hop_count GNUNET_PACKED;
 228
 229   /**
 230    * Desired replication level for this request.
 231    */
 232   uint32_t desired_replication_level GNUNET_PACKED;
 233
 234   /**
 235    * Size of the extended query.
 236    */
 237   uint32_t xquery_size;
 238
 239   /**
 240    * Bloomfilter mutator.
 241    */
 242   uint32_t bf_mutator;
 243
 244   /**
 245    * Bloomfilter (for peer identities) to stop circular routes
 246    */
 247   char bloomfilter[DHT_BLOOM_SIZE];
 248
 249   /**
 250    * The key we are looking for.
 251    */
 252   struct GNUNET_HashCode key;
 253
 254 };
 255
 256
 257 /**
 258  * A destination can be either a friend or finger.
 259  */
 260 enum current_destination_type
 261 {
 262   /* Friend */
 263   FRIEND ,
 264
 265   /* Finger */
 266   FINGER
 267
 268 };
 269
 270 /**
 271  * P2P Trail setup message
 272  * TODO: Take reference from put_path and get_path to understand how to use size of trail list.
 273  */
 274 struct PeerTrailSetupMessage
 275 {
 276   /**
 277    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
 278    */
 279   struct GNUNET_MessageHeader header;
 280
 281   /**
 282    * Source peer which wants to find trail to one of its finger.
 283    */
 284   struct GNUNET_PeerIdentity source_peer;
 285
 286   /**
 287    * Finger id to which we want to set up the trail to.
 288    */
 289   struct GNUNET_PeerIdentity destination_finger;
 290
 291   /* FIXME: Temporary field to handle current_destination properly.
 292    If flag = 0, then this message's current_destination is a friend.
 293    If flag = 1, then the message's current destination is a finger. */
 294   //int flag;
 295
 296   enum current_destination_type current_destination_type;
 297
 298   /**
 299    * This field contains the peer to which this packet is forwarded.
 300    */
 301   struct GNUNET_PeerIdentity current_destination;
 302
 303   /**
 304    * Number of entries in trail list.
 305    * FIXME: Is this data type correct?
 306    * FIMXE: Is usage of GNUNET_PACKED correct?
 307    */
 308   uint32_t trail_length GNUNET_PACKED;
 309
 310   /* FIXME: Add this field later.
 311    * The finger index in finger map.
 312   unsigned int finger_index;*/
 313
 314 };
 315
 316
 317 /**
 318  * P2P Trail setup Result message
 319  */
 320 struct PeerTrailSetupResultMessage
 321 {
 322   /**
 323    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_RESULT_SETUP
 324    */
 325   struct GNUNET_MessageHeader header;
 326
 327   /**
 328    * Finger to which we have found the path.
 329    */
 330   struct GNUNET_PeerIdentity finger;
 331
 332   /**
 333    * Peer which was looking for the trail to finger.
 334    */
 335   struct GNUNET_PeerIdentity destination_peer;
 336
 337   /**
 338    * This field contains the peer to which this packet is forwarded.
 339    */
 340   struct GNUNET_PeerIdentity current_destination;
 341
 342   /**
 343    * FIXME: Temporary field used to remember at which index we should read
 344    * to get our next peer.
 345    */
 346   unsigned int current_index;
 347
 348   /**
 349    * Number of entries in trail list.
 350    * FIXME: Is this data type correct?
 351    * FIXME: Is usage of GNUNET_PACKED correct?
 352    */
 353   uint32_t trail_length GNUNET_PACKED;
 354
 355 };
 356
 357 GNUNET_NETWORK_STRUCT_END
 358
 359
 360 /**
 361  * Linked list of messages to send to a particular other peer.
 362  */
 363 struct P2PPendingMessage
 364 {
 365   /**
 366    * Pointer to next item in the list
 367    */
 368   struct P2PPendingMessage *next;
 369
 370   /**
 371    * Pointer to previous item in the list
 372    */
 373   struct P2PPendingMessage *prev;
 374
 375   /**
 376    * When does this message time out?
 377    */
 378   struct GNUNET_TIME_Absolute timeout;
 379
 380    /**
 381    * Message importance level.  FIXME: used? useful?
 382    */
 383   unsigned int importance;
 384
 385   /**
 386    * Actual message to be sent, allocated at the end of the struct:
 387    * // msg = (cast) &pm[1];
 388    * // memcpy (&pm[1], data, len);
 389    */
 390   const struct GNUNET_MessageHeader *msg;
 391
 392 };
 393
 394
 395  /**
 396   * Linked List of peers which are part of trail to reach a particular Finger.
 397   */
 398 struct TrailPeerList
 399 {
 400    /**
 401    * Pointer to next item in the list
 402    */
 403    struct TrailPeerList *next;
 404
 405    /**
 406    * Pointer to previous item in the list
 407    */
 408    struct TrailPeerList *prev;
 409
 410    /**
 411     * An element in this trail list
 412     */
 413    struct GNUNET_PeerIdentity peer;
 414
 415 };
 416
 417
 418 /**
 419  *  Entry in friend_peermap.
 420  */
 421 struct FriendInfo
 422 {
 423   /**
 424    * What is the identity of the peer?
 425    */
 426   struct GNUNET_PeerIdentity id;
 427
 428   /**
 429    * Count of outstanding messages for peer.
 430    */
 431   unsigned int pending_count;
 432
 433   /**
 434    * FIXME:
 435    * 1. We need some mechanism to check the interval of values for which
 436    * a peer is responsible. If we can somehow maintain the peer id of
 437    * next peer in the friend map, then we will be able to check. Or else
 438    * we iterate over friend map twice will results in O(n^2) complexity.
 439    * So, the tradeoff is between space and run time complexity.
 440    * Peer id of next friend in friend peermap in 64 bit format.
 441    */
 442   uint64_t interval_end;
 443
 444   /**
 445    * Head of pending messages to be sent to this peer.
 446    */
 447  struct P2PPendingMessage *head;
 448
 449  /**
 450   * Tail of pending messages to be sent to this peer.
 451   */
 452  struct P2PPendingMessage *tail;
 453
 454  /**
 455   * TODO - How and where to use this?
 456   * Core handle for sending messages to this peer.
 457   */
 458  struct GNUNET_CORE_TransmitHandle *th;
 459
 460 };
 461
 462
 463 /**
 464  * Entry in finger_peermap.
 465  */
 466 struct FingerInfo
 467 {
 468   /**
 469    * What is the identity of the finger peer?
 470    */
 471   struct GNUNET_PeerIdentity id;
 472
 473   /**
 474    * Start of the interval of keys for which this finger is responsible.
 475    */
 476   unsigned int interval_start;
 477
 478   /**
 479    * End of the interval of keys for which this finger is responsible.
 480    */
 481   unsigned int interval_end;
 482
 483   /**
 484    * List of peers in the trail.
 485    */
 486   const struct GNUNET_PeerIdentity *trail_peer_list;
 487
 488   /**
 489    * Finger index.
 490    */
 491   unsigned int finger_index;
 492 };
 493
 494
 495 /**
 496  * Task that sends FIND FINGER TRAIL requests.
 497  */
 498 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
 499
 500 /**
 501  * Identity of this peer.
 502  */
 503 static struct GNUNET_PeerIdentity my_identity;
 504
 505 /**
 506  * FIXME: Not used anywhere in the code yet.
 507  * Hash of the identity of this peer.
 508  */
 509 static struct GNUNET_HashCode my_identity_hash;
 510
 511 /**
 512  * Hash map of all the friends of a peer
 513  */
 514 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap;
 515
 516 /**
 517  * Hash map of all the fingers of a peer
 518  */
 519 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap;
 520
 521 /**
 522  * TODO: Ask whats the use of ATS.
 523  * Handle to ATS.
 524  */
 525 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
 526
 527 /**
 528  * Handle to CORE.
 529  */
 530 static struct GNUNET_CORE_Handle *core_api;
 531
 532 /**
 533  * The current finger index that we have found trail to.
 534  */
 535 static unsigned int current_finger_index;
 536
 537
 538 /**
 539  * Called when core is ready to send a message we asked for
 540  * out to the destination.
 541  *
 542  * @param cls the 'struct PeerInfo' of the target peer
 543  * @param size number of bytes available in buf
 544  * @param buf where the callee should write the message
 545  * @return number of bytes written to buf
 546  */
 547 static size_t
 548 core_transmit_notify (void *cls, size_t size, void *buf)
 549 {
 550   struct FriendInfo *peer = cls;
 551   char *cbuf = buf;
 552   struct P2PPendingMessage *pending;
 553   size_t off;
 554   size_t msize;
 555
 556   peer->th = NULL;
 557   while ((NULL != (pending = peer->head)) &&
 558          (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
 559   {
 560     peer->pending_count--;
 561     GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
 562     GNUNET_free (pending);
 563   }
 564   if (NULL == pending)
 565   {
 566     /* no messages pending */
 567     return 0;
 568   }
 569   if (NULL == buf)
 570   {
 571     peer->th =
 572         GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
 573                                            GNUNET_CORE_PRIO_BEST_EFFORT,
 574                                            GNUNET_TIME_absolute_get_remaining
 575                                            (pending->timeout), &peer->id,
 576                                            ntohs (pending->msg->size),
 577                                            &core_transmit_notify, peer);
 578     GNUNET_break (NULL != peer->th);
 579     return 0;
 580   }
 581   off = 0;
 582   while ((NULL != (pending = peer->head)) &&
 583          (size - off >= (msize = ntohs (pending->msg->size))))
 584   {
 585     GNUNET_STATISTICS_update (GDS_stats,
 586                               gettext_noop
 587                               ("# Bytes transmitted to other peers"), msize,
 588                               GNUNET_NO);
 589     memcpy (&cbuf[off], pending->msg, msize);
 590     off += msize;
 591     peer->pending_count--;
 592     GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
 593     GNUNET_free (pending);
 594   }
 595   if (peer->head != NULL)
 596   {
 597     peer->th =
 598         GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
 599                                            GNUNET_CORE_PRIO_BEST_EFFORT,
 600                                            GNUNET_TIME_absolute_get_remaining
 601                                            (pending->timeout), &peer->id, msize,
 602                                            &core_transmit_notify, peer);
 603     GNUNET_break (NULL != peer->th);
 604   }
 605   return off;
 606 }
 607
 608
 609 /**
 610  * Transmit all messages in the friend's message queue.
 611  *
 612  * @param peer message queue to process
 613  */
 614 static void
 615 process_friend_queue (struct FriendInfo *peer)
 616 {
 617   struct P2PPendingMessage *pending;
 618
 619   if (NULL == (pending = peer->head))
 620     return;
 621   if (NULL != peer->th)
 622     return;
 623
 624   GNUNET_STATISTICS_update (GDS_stats,
 625                             gettext_noop
 626                             ("# Bytes of bandwidth requested from core"),
 627                             ntohs (pending->msg->size), GNUNET_NO);
 628
 629   /* FIXME: Are we correctly initializing importance and pending. */
 630   peer->th =
 631       GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
 632                                          pending->importance,
 633                                          GNUNET_TIME_absolute_get_remaining
 634                                          (pending->timeout), &peer->id,
 635                                          ntohs (pending->msg->size),
 636                                          &core_transmit_notify, peer);
 637   GNUNET_break (NULL != peer->th);
 638 }
 639
 640
 641 /**
 642  * SUPU:
 643  * 1. trail_length is already incremented in the calling function
 644  * i.e. in send_find_finger_trail, we send trail_length = 1, and then we
 645  * add the peer.
 646  * 2. in handle_dht_p2p_trail_setup, we send trail_length = trail_length+1;
 647  * and we already have added the id of current_destination in our peer_list so
 648  * we need not to do anything else.
 649  * Setup the trail message and forward it to a friend.
 650  * @param source_peer Peer which wants to set up the trail to one of its finger.
 651  * @param destination_finger Peer to which we want to set up the trail to.
 652  * @param current_destination Current peer to which this message should be forwarded.
 653  * @param trail_length Numbers of peers in the trail.
 654  * @param trail_peer_list peers this request has traversed so far
 655  */
 656 void
 657 GDS_NEIGHBOURS_handle_trail_setup(struct GNUNET_PeerIdentity *source_peer,
 658                                   struct GNUNET_PeerIdentity *destination_finger,
 659                                   struct FriendInfo *current_destination,
 660                                   unsigned int trail_length,
 661                                   struct GNUNET_PeerIdentity *trail_peer_list)
 662 {
 663   struct P2PPendingMessage *pending;
 664   struct PeerTrailSetupMessage *tsm;
 665   struct GNUNET_PeerIdentity *peer_list;
 666   size_t msize;
 667
 668   msize = sizeof(struct PeerTrailSetupMessage) +
 669           (trail_length * sizeof(struct GNUNET_PeerIdentity));
 670
 671   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
 672   {
 673     GNUNET_break (0);
 674     return;
 675   }
 676
 677   if (current_destination->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
 678   {
 679     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
 680                                 1, GNUNET_NO);
 681   }
 682
 683   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
 684   pending->importance = 0;    /* FIXME */
 685   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
 686   tsm = (struct PeerTrailSetupMessage *) &pending[1];
 687   pending->msg = &tsm->header;
 688   tsm->header.size = htons (msize);
 689   tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
 690   memcpy(&(tsm->destination_finger), destination_finger, sizeof (struct GNUNET_PeerIdentity));
 691   memcpy(&(tsm->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity));
 692   memcpy(&(tsm->current_destination),&(current_destination->id), sizeof (struct GNUNET_PeerIdentity));
 693   tsm->current_destination_type = htonl(FRIEND);
 694   tsm->trail_length = htonl(trail_length);
 695   peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length);
 696   peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
 697
 698   if(NULL == trail_peer_list)
 699   {
 700    /* FIXME: Shift this logic to send_find_finger_trail_message. */
 701    memcpy(peer_list, &(current_destination->id), sizeof(struct GNUNET_PeerIdentity));
 702   }
 703   else
 704   {
 705    memcpy(peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
 706   }
 707
 708   GNUNET_CONTAINER_DLL_insert_tail (current_destination->head, current_destination->tail, pending);
 709   current_destination->pending_count++;
 710   process_friend_queue (current_destination);
 711
 712 }
 713
 714 /**
 715  * Handle a tail setup result message.
 716  * @param destination_peer Peer which will get the trail to one of its finger.
 717  * @param source_finger Peer to which the trail has been setup to.
 718  * @param current_destination Current peer to which this message should be forwarded.
 719  * @param trail_length Numbers of peers in the trail.
 720  * @param trail_peer_list peers this request has traversed so far
 721  * @param current_trail_index Index in trail_peer_list.
 722  */
 723 void
 724 GDS_NEIGHBOURS_handle_trail_setup_result(struct GNUNET_PeerIdentity *destination_peer,
 725                                   struct GNUNET_PeerIdentity *source_finger,
 726                                   struct FriendInfo *current_destination,
 727                                   unsigned int trail_length,
 728                                   const struct GNUNET_PeerIdentity *trail_peer_list,
 729                                   unsigned int current_trial_index)
 730 {
 731   struct P2PPendingMessage *pending;
 732   struct PeerTrailSetupResultMessage *tsrm;
 733   struct GNUNET_PeerIdentity *peer_list;
 734   size_t msize;
 735
 736   msize = sizeof(struct PeerTrailSetupMessage) +
 737           (trail_length * sizeof(struct GNUNET_PeerIdentity));
 738
 739   if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
 740   {
 741     GNUNET_break (0);
 742     return;
 743   }
 744
 745   if (current_destination->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
 746   {
 747     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
 748                                 1, GNUNET_NO);
 749   }
 750
 751   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
 752   pending->importance = 0;    /* FIXME */
 753   pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
 754   tsrm = (struct PeerTrailSetupResultMessage *) &pending[1];
 755   pending->msg = &tsrm->header;
 756   tsrm->header.size = htons (msize);
 757   tsrm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT);
 758   memcpy(&(tsrm->current_destination), &(current_destination->id), sizeof(struct GNUNET_PeerIdentity));
 759   memcpy(&(tsrm->destination_peer), destination_peer, sizeof(struct GNUNET_PeerIdentity));
 760   memcpy(&(tsrm->finger), source_finger, sizeof(struct GNUNET_PeerIdentity));
 761   tsrm->trail_length = htonl(trail_length);
 762   tsrm->current_index = htonl(current_trial_index);
 763   peer_list = (struct GNUNET_PeerIdentity *) &tsrm[1];
 764   memcpy(peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity));
 765
 766   /* Send the message to chosen friend. */
 767   GNUNET_CONTAINER_DLL_insert_tail (current_destination->head, current_destination->tail, pending);
 768   current_destination->pending_count++;
 769   process_friend_queue (current_destination);
 770 }
 771
 772
 773 /**FIXME: Old implementation just to remove error
 774  * TODO: Modify this function to handle our get request.
 775  * Perform a GET operation.  Forwards the given request to other
 776  * peers.  Does not lookup the key locally.  May do nothing if this is
 777  * the only peer in the network (or if we are the closest peer in the
 778  * network).
 779  *
 780  * @param type type of the block
 781  * @param options routing options
 782  * @param desired_replication_level desired replication count
 783  * @param hop_count how many hops did this request traverse so far?
 784  * @param key key for the content
 785  * @param xquery extended query
 786  * @param xquery_size number of bytes in @a xquery
 787  * @param reply_bf bloomfilter to filter duplicates
 788  * @param reply_bf_mutator mutator for @a reply_bf
 789  * @param peer_bf filter for peers not to select (again)
 790  */
 791 void
 792 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
 793                            enum GNUNET_DHT_RouteOption options,
 794                            uint32_t desired_replication_level,
 795                            uint32_t hop_count, const struct GNUNET_HashCode * key,
 796                            const void *xquery, size_t xquery_size,
 797                            const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
 798                            uint32_t reply_bf_mutator,
 799                            struct GNUNET_CONTAINER_BloomFilter *peer_bf)
 800 {
 801
 802 }
 803
 804 /**FIXME: Old implementation just to remove error.
 805  * TODO: Modify this function to handle our put request.
 806  * Perform a PUT operation.   Forwards the given request to other
 807  * peers.   Does not store the data locally.  Does not give the
 808  * data to local clients.  May do nothing if this is the only
 809  * peer in the network (or if we are the closest peer in the
 810  * network).
 811  *
 812  * @param type type of the block
 813  * @param options routing options
 814  * @param desired_replication_level desired replication count
 815  * @param expiration_time when does the content expire
 816  * @param hop_count how many hops has this message traversed so far
 817  * @param bf Bloom filter of peers this PUT has already traversed
 818  * @param key key for the content
 819  * @param put_path_length number of entries in @a put_path
 820  * @param put_path peers this request has traversed so far (if tracked)
 821  * @param data payload to store
 822  * @param data_size number of bytes in @a data
 823  */
 824 void
 825 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
 826                            enum GNUNET_DHT_RouteOption options,
 827                            uint32_t desired_replication_level,
 828                            struct GNUNET_TIME_Absolute expiration_time,
 829                            uint32_t hop_count,
 830                            struct GNUNET_CONTAINER_BloomFilter *bf,
 831                            const struct GNUNET_HashCode *key,
 832                            unsigned int put_path_length,
 833                            struct GNUNET_PeerIdentity *put_path,
 834                            const void *data, size_t data_size)
 835 {
 836
 837 }
 838
 839
 840 /**FIXME: Old implementation just to remove error.
 841  * Handle a reply (route to origin).  Only forwards the reply back to
 842  * other peers waiting for it.  Does not do local caching or
 843  * forwarding to local clients.
 844  *
 845  * @param target neighbour that should receive the block (if still connected)
 846  * @param type type of the block
 847  * @param expiration_time when does the content expire
 848  * @param key key for the content
 849  * @param put_path_length number of entries in put_path
 850  * @param put_path peers the original PUT traversed (if tracked)
 851  * @param get_path_length number of entries in put_path
 852  * @param get_path peers this reply has traversed so far (if tracked)
 853  * @param data payload of the reply
 854  * @param data_size number of bytes in data
 855  */
 856 void
 857 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
 858                              enum GNUNET_BLOCK_Type type,
 859                              struct GNUNET_TIME_Absolute expiration_time,
 860                              const struct GNUNET_HashCode * key,
 861                              unsigned int put_path_length,
 862                              const struct GNUNET_PeerIdentity *put_path,
 863                              unsigned int get_path_length,
 864                              const struct GNUNET_PeerIdentity *get_path,
 865                              const void *data, size_t data_size)
 866 {
 867
 868 }
 869
 870
 871 /**
 872  * Randomly choose one of your friends from the friends_peer map
 873  * @return Friend
 874  */
 875 static struct FriendInfo *
 876 select_random_friend()
 877 {
 878   unsigned int current_size;
 879   unsigned int *index;
 880   unsigned int j = 0;
 881   struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
 882   struct GNUNET_PeerIdentity key_ret;
 883   struct FriendInfo *friend;
 884
 885   current_size = GNUNET_CONTAINER_multipeermap_size(friend_peermap);
 886
 887   /* Element stored at this index in friend_peermap should be selected friend. */
 888   index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
 889
 890   /* Create an iterator for friend_peermap. */
 891   iter = GNUNET_CONTAINER_multipeermap_iterator_create(friend_peermap);
 892
 893   /* Set the position of iterator to index. */
 894   while(j < (*index))
 895   {
 896     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,NULL,NULL))
 897       j++;
 898     else
 899       return NULL;
 900   }
 901
 902   if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,&key_ret,(const void **)&friend))
 903   {
 904     return friend;
 905   }
 906
 907   return NULL;
 908 }
 909
 910
 911 /**
 912  * Compute finger_identity to which we want to setup the trail
 913  * FIXME: If we maintain a index that is value of current_finger_index
 914  * to which a particular entry in finger map corresponds then should we first
 915  * check if there is already an entry for that index. If yes then don't
 916  * search for trail to that finger.
 917  * @return finger_identity
 918  */
 919 static
 920 struct GNUNET_PeerIdentity *
 921 compute_finger_identity()
 922 {
 923   struct GNUNET_PeerIdentity *finger_identity;
 924
 925   finger_identity = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
 926   finger_identity = GNUNET_CRYPTO_compute_finger_identity(&my_identity,current_finger_index );
 927
 928   current_finger_index = (current_finger_index+1) % MAX_FINGERS;
 929
 930   /* Check if you already have an entry in finger_peermap for this finger_id.
 931      If yes then again look for a new finger_id.
 932      FIXME: Should we return NULL here?
 933   if(NULL != GNUNET_CONTAINER_multipeermap_get(finger_peermap,finger_peer_id))
 934   {
 935     finger_peer_id = compute_finger_identity();
 936   }*/
 937
 938   return finger_identity;
 939 }
 940
 941
 942 /**
 943  * TODO: Implement after testing friend/finger map.
 944  * TODO: Handle the case when we already have a trail to our predecessor in
 945  * the network.
 946  * This function will be needed when we are handling node joins/fails
 947  * to maintain correct pointer to our predecessor and successor in the network.
 948  * Find immediate predecessor in the network.
 949  * @param me my own identity
 950  * @return peer identity of immediate predecessor.
 951  */
 952 static
 953 struct GNUNET_PeerIdentity *
 954 find_immediate_predecessor()
 955 {
 956   /* Using your own peer identity, calculate your predecessor
 957    * in the network. Try to setup path to this predecessor using
 958    * the same logic as used for other fingers.
 959    * If we already have a trail to our predecessor then send NULL and
 960    * calling function should be able to handle that case.
 961   */
 962   return NULL;
 963 }
 964
 965
 966 /**
 967  * Task to send a find finger trail message. We attempt to find trail
 968  * to our finger in the network.
 969  *
 970  * @param cls closure for this task
 971  * @param tc the context under which the task is running
 972  */
 973 static void
 974 send_find_finger_trail_message (void *cls,
 975                         const struct GNUNET_SCHEDULER_TaskContext *tc)
 976 {
 977   struct GNUNET_PeerIdentity *finger_identity;
 978   struct FriendInfo *friend;
 979   struct GNUNET_TIME_Relative next_send_time;
 980
 981   /* We already have found trail to each of our possible fingers in the network. */
 982   if (GNUNET_CONTAINER_multipeermap_size (finger_peermap) == MAX_FINGERS)
 983   {
 984     /* FIXME: I call find_immediate_predecessor when I have found trail to
 985      * all the possible fingers in the network. But we need to find immediate
 986      * predecessor when there is a node failure/join. It may happen before.
 987      * Think of a better strategy to decide when to call this function.
 988      * We can find trail to our immediate predecessor in the network.
 989      */
 990     finger_identity = find_immediate_predecessor();
 991
 992     if(NULL == finger_identity)
 993     {
 994       /* We already have a trail to reach to immediate predecessor. */
 995       goto new_find_finger_trail_request;
 996     }
 997   }
 998   else
 999   {
1000     /* Find the finger_peer_id for which we want to setup the trail */
1001     finger_identity = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1002     finger_identity = compute_finger_identity();
1003
1004     if(finger_identity == NULL)
1005     {
1006       goto new_find_finger_trail_request;
1007     }
1008   }
1009
1010   friend = GNUNET_malloc (sizeof (struct FriendInfo));
1011   friend = select_random_friend();
1012
1013   /* We found a friend.*/
1014   if(NULL != friend)
1015   {
1016     GDS_NEIGHBOURS_handle_trail_setup(&my_identity,finger_identity,friend,1,NULL);
1017   }
1018
1019   /* FIXME: Should we be using current_finger_index to generate random interval.*/
1020   new_find_finger_trail_request:
1021   next_send_time.rel_value_us =
1022       DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
1023       GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
1024                                 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
1025                                 (current_finger_index + 1));
1026
1027   find_finger_trail_task =
1028       GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
1029                                     NULL);
1030 }
1031
1032
1033 /**
1034  * Method called whenever a peer connects.
1035  *
1036  * @param cls closure
1037  * @param peer peer identity this notification is about
1038  */
1039 static void
1040 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer)
1041 {
1042   struct FriendInfo *ret;
1043
1044   /* Check for connect to self message */
1045   if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
1046     return;
1047
1048   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1049               "Connected to %s\n",
1050               GNUNET_i2s (peer));
1051
1052   /* If peer already exists in our friend_peermap, then exit. */
1053   if (GNUNET_YES ==
1054       GNUNET_CONTAINER_multipeermap_contains (friend_peermap,
1055                                               peer))
1056   {
1057     GNUNET_break (0);
1058     return;
1059   }
1060
1061   GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
1062                             GNUNET_NO);
1063
1064   ret = GNUNET_new (struct FriendInfo);
1065   ret->id = *peer;
1066
1067   GNUNET_assert (GNUNET_OK ==
1068                  GNUNET_CONTAINER_multipeermap_put (friend_peermap,
1069                                                     peer, ret,
1070                                                     GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1071
1072   /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
1073   if (1 == GNUNET_CONTAINER_multipeermap_size (friend_peermap))
1074     find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
1075 }
1076
1077
1078 /**
1079  * FIXME: Implement after testing finger/friend table setup.
1080  * Method called whenever a peer disconnects.
1081  *
1082  * @param cls closure
1083  * @param peer peer identity this notification is about
1084  */
1085 static void
1086 handle_core_disconnect (void *cls,
1087                         const struct GNUNET_PeerIdentity *peer)
1088 {
1089   /**
1090    * 1. remove the friend from the friend map.
1091    * 2. remove the trail for the fingers for which this peer was the first hop.
1092    * 3. start send_find_finger_trail for these fingers to find a new trail
1093    * in the network.
1094    * 4. Also when a node gets disconnected, how should we update pointers of its
1095    * immediate successor and predecessor in the network ?
1096    * 5. Also how do we distribute the keys in the network?
1097    * 6. Here is case where we started put operation but a peer got disconnected and
1098       we removed the entry from the table. How to handle such a case.
1099    */
1100 }
1101
1102
1103 /**
1104  * To be called on core init/fail.
1105  *
1106  * @param cls service closure
1107  * @param identity the public identity of this peer
1108  */
1109 static void
1110 core_init (void *cls,
1111            const struct GNUNET_PeerIdentity *identity)
1112 {
1113   my_identity = *identity;
1114   GNUNET_CRYPTO_hash (identity,
1115                       sizeof (struct GNUNET_PeerIdentity),
1116                       &my_identity_hash);
1117 }
1118
1119
1120 /**
1121  * Core handler for p2p put requests.
1122  *
1123  * @param cls closure
1124  * @param peer sender of the request
1125  * @param message message
1126  * @param peer peer identity this notification is about
1127  * @return #GNUNET_OK to keep the connection open,
1128  *         #GNUNET_SYSERR to close it (signal serious error)
1129  */
1130 static int
1131 handle_dht_p2p_put (void *cls,
1132                     const struct GNUNET_PeerIdentity *peer,
1133                     const struct GNUNET_MessageHeader *message)
1134 {
1135     /**
1136      1. Search the friend,finger and check your own id to find the closest
1137      * predecessor the given key. --> find_predecessor()
1138      2. If self then datache_store
1139      3. If friend, then add to peer queue
1140      4. If finger, then add to the peer queue of the first hop.
1141      * in put message also maintain a field current_destination and use
1142      * same logic as trail setup to understand if you are just part of trail
1143      * to reach to a particular peer or you are endpoint of trail or just a friend.
1144      *
1145      */
1146   return 0;
1147 }
1148
1149
1150 /**
1151  * Core handler for p2p get requests.
1152  *
1153  * @param cls closure
1154  * @param peer sender of the request
1155  * @param message message
1156  * @return #GNUNET_OK to keep the connection open,
1157  *         #GNUNET_SYSERR to close it (signal serious error)
1158  */
1159 static int
1160 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1161                     const struct GNUNET_MessageHeader *message)
1162 {
1163   return 0;
1164 }
1165
1166
1167 /**
1168  * Core handler for p2p result messages.
1169  *
1170  * @param cls closure
1171  * @param message message
1172  * @param peer peer identity this notification is about
1173  * @return #GNUNET_YES (do not cut p2p connection)
1174  */
1175 static int
1176 handle_dht_p2p_result (void *cls, const struct GNUNET_PeerIdentity *peer,
1177                        const struct GNUNET_MessageHeader *message)
1178 {
1179   return 0;
1180 }
1181
1182
1183 /**
1184  * FIXME:
1185  * 1. Where do we use mod MAX_FINGERS?
1186  * 2. You are not using mod when searching for the closest successor of a finger.
1187  * 3. * 6. When I change the logic for find_successor, then I need to compare the interval
1188  * of two fingers. for that do I need to maintain a finger index and calculate
1189  * the interval?
1190  * @param destination
1191  * @param flag Set the value of flag to 0, if next_hop = friend/1 if next_hop = finger.
1192  * @param current_destination We should set this field to finger id/friend id chosen to be next_hop.
1193  * @return
1194  */
1195 static struct GNUNET_PeerIdentity *
1196 find_successor(struct GNUNET_PeerIdentity *destination,
1197                struct GNUNET_PeerIdentity *current_destination,
1198                enum current_destination_type *type)
1199 {
1200   /*
1201    * 1. Compare your identity with destination identity.
1202    * 2. Iterate over friend_map to find the peer identity with identity >= destination
1203    * 3. Iterate over finger_map to find the peer identity with identity >= destination
1204    * 4. Compare id,friend and finger to select one which is the least and still >= destination.
1205    * 5. If friend/my_identity then flag = 0
1206    * 6. If finger, then flag = 1.
1207    * 7. Set the current_destination value with chosen friend/finger/my_identity
1208    * 8. If finger, then search in your own finger table send the next hop to reach that finger.
1209    */
1210   unsigned int friend_index;
1211   unsigned int finger_index;
1212   struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1213   struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1214   struct GNUNET_PeerIdentity key_ret;
1215   struct FriendInfo *friend;
1216   struct FingerInfo *finger;
1217   struct GNUNET_PeerIdentity *current_successor;
1218
1219   /* FIXME: Temporary field used to understand if we got a friend or finger
1220      as next successor. find something better. */
1221   int successor;
1222   int finger_peer = 0;
1223   int friend_peer = 1;
1224   int me = 2;
1225
1226   current_successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1227
1228   /* initialize current_successor with your own identity. */
1229   memcpy(current_successor,&my_identity,sizeof(struct GNUNET_PeerIdentity));
1230   successor = me;
1231
1232   friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap);
1233
1234   /*iterate over friend map till you reach a peer id such that destination <= peer id */
1235   for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peermap); friend_index++)
1236   {
1237     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1238     {
1239       if(0 > GNUNET_CRYPTO_cmp_peer_identity(&friend->id,destination) ||
1240         (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id,destination)))
1241       {
1242         /* If yes then check if finger <= current_successor */
1243         if(0 < GNUNET_CRYPTO_cmp_peer_identity(&friend->id,current_successor) ||
1244           (0 == GNUNET_CRYPTO_cmp_peer_identity(&friend->id,current_successor)))
1245         {
1246           memcpy(current_successor,friend,sizeof(struct GNUNET_PeerIdentity));
1247           successor = friend_peer;
1248         }
1249       }
1250     }
1251   }
1252
1253
1254   finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap);
1255   /* iterate over finger map till you reach a peer id such that destination <= peer id */
1256   for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++)
1257   {
1258     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1259     {
1260       if(0 > GNUNET_CRYPTO_cmp_peer_identity(&finger->id,destination) ||
1261          (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->id,destination)))
1262       {
1263         /* If yes then check if finger <= current_friend_successor */
1264         if(0 < GNUNET_CRYPTO_cmp_peer_identity(&finger->id,current_successor)
1265         || (0 == GNUNET_CRYPTO_cmp_peer_identity(&finger->id,current_successor)))
1266         {
1267           memcpy(current_successor,finger,sizeof(struct GNUNET_PeerIdentity));
1268           successor = finger_peer;
1269         }
1270       }
1271     }
1272   }
1273
1274   memcpy(current_destination,current_successor,sizeof(struct GNUNET_PeerIdentity));
1275
1276   if(successor == finger_peer)
1277   {
1278     *type = FINGER;
1279   }
1280   else
1281   {
1282     /* The successor is either my_identity or friend. */
1283     *type = FRIEND;
1284   }
1285
1286   return current_successor;
1287 }
1288
1289
1290 /**
1291  * @param cls closure
1292  * @param message message
1293  * @param peer peer identity this notification is about
1294  * @return #GNUNET_YES
1295  */
1296 static int
1297 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1298                     const struct GNUNET_MessageHeader *message)
1299 {
1300   struct PeerTrailSetupMessage *trail_setup;
1301   struct GNUNET_PeerIdentity *next_hop;
1302   struct FriendInfo *target_friend;
1303   struct FriendInfo *new_target_friend;
1304   size_t msize;
1305   uint32_t trail_length;
1306   enum current_destination_type peer_type;
1307   struct GNUNET_PeerIdentity *trail_peer_list;
1308   uint32_t current_trail_index;
1309   struct GNUNET_PeerIdentity *next_peer;
1310
1311   /* parse and validate message. */
1312   msize = ntohs (message->size);
1313   if (msize < sizeof (struct PeerTrailSetupMessage))
1314   {
1315     GNUNET_break_op (0);
1316     return GNUNET_YES;
1317   }
1318
1319   trail_setup = (struct PeerTrailSetupMessage *) message;
1320   trail_length = ntohl (trail_setup->trail_length);
1321   peer_type = ntohl (trail_setup->current_destination_type);
1322   trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_setup[1];
1323
1324   if ((msize <
1325        sizeof (struct PeerTrailSetupMessage) +
1326        trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1327       (trail_length >
1328        GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1329   {
1330     GNUNET_break_op (0);
1331     return GNUNET_YES;
1332   }
1333
1334
1335   GNUNET_STATISTICS_update (GDS_stats,
1336                             gettext_noop ("# TRAIL SETUP requests received"), 1,
1337                             GNUNET_NO);
1338   GNUNET_STATISTICS_update (GDS_stats,
1339                             gettext_noop ("# TRAIL SETUP bytes received"), msize,
1340                             GNUNET_NO);
1341
1342   if(peer_type == FRIEND)
1343   {
1344     if(0 == (GNUNET_CRYPTO_cmp_peer_identity(&(trail_setup->current_destination),&my_identity)))
1345     {
1346       next_hop = find_successor(&(trail_setup->destination_finger),&(trail_setup->current_destination),&(peer_type));
1347     }
1348     else
1349       return GNUNET_SYSERR;
1350   }
1351   else
1352   {
1353     if(0 != (GNUNET_CRYPTO_cmp_peer_identity(&(trail_setup->current_destination),&my_identity)))
1354     {
1355       /* I am part of trail. */
1356       next_hop = GDS_ROUTING_search(&(trail_setup->source_peer),&(trail_setup->destination_finger));
1357
1358       /*TODO:
1359        call find_successor and compare the two peer ids
1360        and choose whichever is closest to the destination finger. */
1361     }
1362     else
1363     {
1364       /* I am the current_destination finger */
1365       next_hop = find_successor(&(trail_setup->destination_finger),&(trail_setup->current_destination),&(peer_type));
1366     }
1367   }
1368
1369   target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
1370
1371   /* Add yourself to list of peers that trail setup message have traversed so far
1372    and increment trail length. */
1373   struct GNUNET_PeerIdentity *peer_list;
1374   peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length + 1));
1375   memcpy(peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity));
1376   memcpy(&peer_list[trail_length], next_hop, sizeof (struct GNUNET_PeerIdentity));
1377   trail_length++;
1378
1379   /* Check if you are next hop, if yes then you have reached the final destination. */
1380   if(0 == (GNUNET_CRYPTO_cmp_peer_identity(next_hop,&my_identity)))
1381   {
1382     /* FIXME: Trail length should be const. */
1383     if(trail_length >= 1)
1384     {
1385       current_trail_index = trail_length - 2;
1386       next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); //FIXME: Do we need to allocate the memory?
1387       memcpy(next_peer, &peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity));
1388
1389       new_target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
1390
1391       /* FIXME: It does not find a friend. Could be possible error in find_successor
1392        function. Change the logic in find_successor and change it again. */
1393       /*if(GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains(friend_peermap,new_target_friend))
1394       {
1395
1396         return GNUNET_SYSERR;
1397       }
1398       */
1399       GDS_NEIGHBOURS_handle_trail_setup_result(&(trail_setup->source_peer),
1400                                              &(trail_setup->destination_finger),
1401                                              new_target_friend, trail_length,
1402                                              peer_list,current_trail_index);
1403     }
1404     return GNUNET_YES;
1405   }
1406
1407   if(peer_type == FINGER)
1408   {
1409     GDS_ROUTING_add(&(trail_setup->source_peer),&(trail_setup->current_destination),next_hop);
1410   }
1411
1412   GDS_NEIGHBOURS_handle_trail_setup(&(trail_setup->source_peer),
1413                                     &(trail_setup->destination_finger),
1414                                     target_friend,
1415                                     trail_setup->trail_length,
1416                                     peer_list);
1417 return GNUNET_YES;
1418 }
1419
1420
1421 /**
1422  * FIXME : Add interval field.
1423  * Add an entry in finger table.
1424  * @param finger Finger to be added to finger table
1425  * @param peer_list peers this request has traversed so far
1426  * @param trail_length Numbers of peers in the trail.
1427  */
1428 static
1429 void finger_table_add(struct GNUNET_PeerIdentity *finger,
1430                       const struct GNUNET_PeerIdentity *peer_list,
1431                       unsigned int trail_length)
1432 {
1433   struct FingerInfo *finger_entry;
1434   finger_entry = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
1435   memcpy(&(finger_entry->id), finger, sizeof(struct GNUNET_PeerIdentity));
1436   memcpy(&(finger_entry->trail_peer_list), peer_list, sizeof(struct GNUNET_PeerIdentity)
1437                                                       * trail_length);
1438 }
1439
1440
1441 /**
1442  * Core handle for p2p trail construction result messages.
1443  * @param cls closure
1444  * @param message message
1445  * @param peer peer identity this notification is about
1446  * @return #GNUNET_YES
1447  */
1448 static int
1449 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
1450                     const struct GNUNET_MessageHeader *message)
1451 {
1452   struct PeerTrailSetupResultMessage *trail_result;
1453   size_t msize;
1454   uint32_t trail_length;
1455   const struct GNUNET_PeerIdentity *trail_peer_list;
1456   uint32_t current_trail_index;
1457   struct GNUNET_PeerIdentity *next_peer;
1458   struct FriendInfo *target_friend;
1459
1460   msize = ntohs (message->size);
1461   if (msize < sizeof (struct PeerTrailSetupMessage))
1462   {
1463     GNUNET_break_op (0);
1464     return GNUNET_YES;
1465   }
1466
1467   trail_result = (struct PeerTrailSetupResultMessage *) message;
1468   trail_length = ntohl (trail_result->trail_length);
1469   current_trail_index = ntohl(trail_result->current_index);
1470   trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1];
1471
1472   if ((msize <
1473        sizeof (struct PeerTrailSetupResultMessage) +
1474        trail_length * sizeof (struct GNUNET_PeerIdentity)) ||
1475       (trail_length >
1476        GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1477   {
1478     GNUNET_break_op (0);
1479     return GNUNET_YES;
1480   }
1481
1482   if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->current_destination), &my_identity)))
1483   {
1484     /* Am I the destination? */
1485     if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(&(trail_result->destination_peer), &my_identity)))
1486     {
1487       finger_table_add(&(trail_result->finger), trail_peer_list,trail_length);
1488       return GNUNET_YES;
1489     }
1490     else
1491     {
1492       next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
1493       current_trail_index = current_trail_index - 1;
1494       memcpy(next_peer, &(trail_peer_list[trail_length-1]), sizeof (struct GNUNET_PeerIdentity));
1495       target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer);
1496
1497       GDS_NEIGHBOURS_handle_trail_setup_result(&(trail_result->destination_peer),
1498                                                &(trail_result->finger),
1499                                                target_friend, trail_length,
1500                                                trail_peer_list,current_trail_index);
1501       return GNUNET_YES;
1502     }
1503   }
1504   else
1505     return GNUNET_SYSERR;
1506 }
1507
1508
1509 /**
1510  * Initialize neighbours subsystem.
1511  * @return GNUNET_OK on success, GNUNET_SYSERR on error
1512  */
1513 int
1514 GDS_NEIGHBOURS_init()
1515 {
1516   static struct GNUNET_CORE_MessageHandler core_handlers[] = {
1517     {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
1518     {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
1519     {&handle_dht_p2p_result, GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT, 0},
1520     {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
1521     {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
1522     {NULL, 0, 0}
1523   };
1524
1525   /*ASK: What is ATS? Why do we need it? */
1526   atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
1527   core_api =
1528     GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
1529                            &handle_core_disconnect, NULL, GNUNET_NO, NULL,
1530                            GNUNET_NO, core_handlers);
1531   if (core_api == NULL)
1532     return GNUNET_SYSERR;
1533
1534   friend_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1535   finger_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1536
1537   return GNUNET_OK;
1538 }
1539
1540
1541 /**
1542  * Shutdown neighbours subsystem.
1543  */
1544 void
1545 GDS_NEIGHBOURS_done ()
1546 {
1547   if (NULL == core_api)
1548     return;
1549
1550   GNUNET_CORE_disconnect (core_api);
1551   core_api = NULL;
1552   GNUNET_ATS_performance_done (atsAPI);
1553   atsAPI = NULL;
1554
1555   /* FIXME: Once handle_core_disconnect is implemented, both below assertion should not
1556    fail. */
1557   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap));
1558   GNUNET_CONTAINER_multipeermap_destroy (friend_peermap);
1559   friend_peermap = NULL;
1560
1561   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap));
1562   GNUNET_CONTAINER_multipeermap_destroy (finger_peermap);
1563   finger_peermap = NULL;
1564
1565   if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
1566   {
1567     GNUNET_SCHEDULER_cancel (find_finger_trail_task);
1568     find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
1569   }
1570 }
1571
1572
1573 /**
1574  * Get the ID of the local node.
1575  *
1576  * @return identity of the local node
1577  */
1578 struct GNUNET_PeerIdentity *
1579 GDS_NEIGHBOURS_get_id ()
1580 {
1581   return &my_identity;
1582 }
1583
1584
1585 /* end of gnunet-service-xdht_neighbours.c */