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