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 /*TODO
  53  1. Add logic to get connected to your predecessor
  54  because when nodes join/fail , you need to maintain correct
  55  pointers to predecessor and your successor (your first finger),
  56  to update tables.
  57  2. Remove extra comments - FIXME,TODO,SUPU
  58  3. When do we call GDS_Routing_add()?  */
  59
  60 /**
  61  * Maximum possible fingers of a peer.
  62  */
  63 #define MAX_FINGERS 256
  64
  65 /**
  66  * Maximum allowed number of pending messages per friend peer.
  67  */
  68 #define MAXIMUM_PENDING_PER_FRIEND 64
  69
  70 /**
  71  * How long at least to wait before sending another find finger trail request.
  72  */
  73 #define DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30)
  74
  75 /**
  76  * How long at most to wait before sending another find finger trail request.
  77  */
  78 #define DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 10)
  79
  80
  81 GNUNET_NETWORK_STRUCT_BEGIN
  82
  83 /* FIXME:
  84  * 1) Bloomfilter is not required for X-Vine.
  85  * Keep the field now but remove it when implementing PUT/GET.
  86  * 2) also, check the field of put/get/result if all are required for
  87  * x-vine or not. */
  88
  89 /**
  90  * P2P PUT message
  91  */
  92 struct PeerPutMessage
  93 {
  94   /**
  95    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
  96    */
  97   struct GNUNET_MessageHeader header;
  98
  99   /**
 100    * Processing options
 101    */
 102   uint32_t options GNUNET_PACKED;
 103
 104   /**
 105    * Content type.
 106    */
 107   uint32_t type GNUNET_PACKED;
 108
 109   /**
 110    * Hop count
 111    */
 112   uint32_t hop_count GNUNET_PACKED;
 113
 114   /**
 115    * Replication level for this message
 116    */
 117   uint32_t desired_replication_level GNUNET_PACKED;
 118
 119   /**
 120    * Length of the PUT path that follows (if tracked).
 121    */
 122   uint32_t put_path_length GNUNET_PACKED;
 123
 124   /**
 125    * When does the content expire?
 126    */
 127   struct GNUNET_TIME_AbsoluteNBO expiration_time;
 128
 129   /**
 130    * Bloomfilter (for peer identities) to stop circular routes
 131    */
 132   char bloomfilter[DHT_BLOOM_SIZE];
 133
 134   /**
 135    * The key we are storing under.
 136    */
 137   struct GNUNET_HashCode key;
 138
 139   /* put path (if tracked) */
 140
 141   /* Payload */
 142
 143 };
 144
 145
 146 /**
 147  * P2P Result message
 148  */
 149 struct PeerResultMessage
 150 {
 151   /**
 152    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
 153    */
 154   struct GNUNET_MessageHeader header;
 155
 156   /**
 157    * Content type.
 158    */
 159   uint32_t type GNUNET_PACKED;
 160
 161   /**
 162    * Length of the PUT path that follows (if tracked).
 163    */
 164   uint32_t put_path_length GNUNET_PACKED;
 165
 166   /**
 167    * Length of the GET path that follows (if tracked).
 168    */
 169   uint32_t get_path_length GNUNET_PACKED;
 170
 171   /**
 172    * When does the content expire?
 173    */
 174   struct GNUNET_TIME_AbsoluteNBO expiration_time;
 175
 176   /**
 177    * The key of the corresponding GET request.
 178    */
 179   struct GNUNET_HashCode key;
 180
 181   /* put path (if tracked) */
 182
 183   /* get path (if tracked) */
 184
 185   /* Payload */
 186
 187 };
 188
 189
 190 /**
 191  * P2P GET message
 192  */
 193 struct PeerGetMessage
 194 {
 195   /**
 196    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
 197    */
 198   struct GNUNET_MessageHeader header;
 199
 200   /**
 201    * Processing options
 202    */
 203   uint32_t options GNUNET_PACKED;
 204
 205   /**
 206    * Desired content type.
 207    */
 208   uint32_t type GNUNET_PACKED;
 209
 210   /**
 211    * Hop count
 212    */
 213   uint32_t hop_count GNUNET_PACKED;
 214
 215   /**
 216    * Desired replication level for this request.
 217    */
 218   uint32_t desired_replication_level GNUNET_PACKED;
 219
 220   /**
 221    * Size of the extended query.
 222    */
 223   uint32_t xquery_size;
 224
 225   /**
 226    * Bloomfilter mutator.
 227    */
 228   uint32_t bf_mutator;
 229
 230   /**
 231    * Bloomfilter (for peer identities) to stop circular routes
 232    */
 233   char bloomfilter[DHT_BLOOM_SIZE];
 234
 235   /**
 236    * The key we are looking for.
 237    */
 238   struct GNUNET_HashCode key;
 239
 240 };
 241
 242
 243 /**
 244  * FIXME: I have defined this struct between GNUNET_NETWORK_STRUCT_BEGIN. Is
 245  * it correct? Also, I am using the same struct inside finger info and trailsetup
 246  * trailsetupresult message. Is it correct? */
 247  /**
 248   * Linked List of peers which are part of trail to reach a particular Finger.
 249   */
 250 struct TrailPeerList
 251 {
 252    /**
 253    * Pointer to next item in the list
 254    */
 255    struct TrailPeerList *next;
 256
 257    /**
 258    * Pointer to previous item in the list
 259    */
 260    struct TrailPeerList *prev;
 261
 262    /**
 263     * An element in this trail list
 264     */
 265    struct GNUNET_PeerIdentity *peer;
 266
 267 };
 268
 269
 270 /**
 271  * FIXME : I am using the same structure trail list in both finger info
 272  * and peertrailsetupmessage. Verify if its okay.
 273  * P2P Trail setup message
 274  */
 275 struct PeerTrailSetupMessage
 276 {
 277   /**
 278    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP
 279    */
 280   struct GNUNET_MessageHeader header;
 281
 282   /**
 283    * Source peer which wants to find trail to one of its finger.
 284    */
 285   struct GNUNET_PeerIdentity *source_peer;
 286
 287   /**
 288    * Finger id to which we want to set up the trail to.
 289    */
 290   struct GNUNET_PeerIdentity *destination_finger;
 291
 292   /**
 293    * This field contains the peer to which this packet is forwarded.
 294    */
 295   struct GNUNET_PeerIdentity *current_destination;
 296
 297   /**
 298    * Head of trail list.
 299    */
 300   struct TrailPeerList *head;
 301
 302   /**
 303    * Tail of trail list.
 304    */
 305   struct TrailPeerList *tail;
 306
 307 };
 308
 309
 310 /**
 311  * P2P Trail setup Result message
 312  * FIXME: There seem to be no difference between trail_setup and trailsetupresult
 313  * Can we somehow merge these two. As in result we don't have to do any
 314  * search in our finger or friend table thats why I kept it separate. But is it
 315  * actually required to keep these two things different.
 316  */
 317 struct PeerTrailSetupResultMessage
 318 {
 319   /**
 320    * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_RESULT_SETUP
 321    */
 322   struct GNUNET_MessageHeader header;
 323
 324   /* SUPU: It should contain the list of peers which form the trail.
 325    and also maintain a pointer to the current_peer to which we have to forward
 326    the packet. We have to maintain the whole list in this message because
 327    at the end source peer will store this list in its finger table. */
 328
 329   /**
 330    * Source peer which wants to find trail to one of its finger.
 331    */
 332   struct GNUNET_PeerIdentity *source_peer;
 333
 334   /**
 335    * Finger id to which we want to set up the trail to.
 336    */
 337   struct GNUNET_PeerIdentity *destination_finger;
 338
 339   /**
 340    * This field contains the peer to which this packet is forwarded.
 341    */
 342   struct GNUNET_PeerIdentity *current_destination;
 343
 344   /**
 345    * Head of trail list.
 346    */
 347   struct TrailPeerList *head;
 348
 349   /**
 350    * Tail of trail list.
 351    */
 352   struct TrailPeerList *tail;
 353
 354 };
 355
 356 GNUNET_NETWORK_STRUCT_END
 357
 358
 359 /**
 360  * Linked list of messages to send to a particular other peer.
 361  */
 362 struct P2PPendingMessage
 363 {
 364   /**
 365    * Pointer to next item in the list
 366    */
 367   struct P2PPendingMessage *next;
 368
 369   /**
 370    * Pointer to previous item in the list
 371    */
 372   struct P2PPendingMessage *prev;
 373
 374   /**
 375    * When does this message time out?
 376    */
 377   struct GNUNET_TIME_Absolute timeout;
 378
 379    /**
 380    * Message importance level.  FIXME: used? useful?
 381    */
 382   unsigned int importance;
 383
 384   /**
 385    * Actual message to be sent, allocated at the end of the struct:
 386    * // msg = (cast) &pm[1];
 387    * // memcpy (&pm[1], data, len);
 388    */
 389   const struct GNUNET_MessageHeader *msg;
 390
 391 };
 392
 393 /**
 394  *  Entry in friend_peers map.
 395  */
 396 struct FriendInfo
 397 {
 398
 399  /**
 400   * What is the identity of the peer?
 401   */
 402   struct GNUNET_PeerIdentity id;
 403
 404  /**
 405   * Count of outstanding messages for peer.
 406   */
 407  unsigned int pending_count;
 408
 409  /**
 410   * Head of pending messages to be sent to this peer.
 411   */
 412  struct P2PPendingMessage *head;
 413
 414  /**
 415   * Tail of pending messages to be sent to this peer.
 416   */
 417  struct P2PPendingMessage *tail;
 418
 419  /**
 420   * TODO - How and where to use this?
 421   * Core handle for sending messages to this peer.
 422   */
 423  struct GNUNET_CORE_TransmitHandle *th;
 424
 425 };
 426
 427 /**
 428  * Entry in finger_peers map.
 429  */
 430 struct FingerInfo
 431 {
 432   /**
 433    * What is the identity of the peer?
 434    */
 435   struct GNUNET_PeerIdentity id;
 436
 437
 438   /**
 439    * Start of the interval of keys for which this finger is responsible.
 440    */
 441   unsigned int interval_start;
 442
 443   /**
 444    * End of the interval of keys for which this finger is responsible.
 445    */
 446   unsigned int interval_end;
 447
 448   /**
 449    * Head of trail list.
 450    */
 451   struct TrailPeerList *head;
 452
 453   /**
 454    * Tail of trail list.
 455    */
 456   struct TrailPeerList *tail;
 457
 458 };
 459
 460
 461 /**
 462  * Task that sends FIND FINGER TRAIL requests.
 463  */
 464 static GNUNET_SCHEDULER_TaskIdentifier find_finger_trail_task;
 465
 466 /**
 467  * Identity of this peer.
 468  */
 469 static struct GNUNET_PeerIdentity my_identity;
 470
 471 /**
 472  * Hash of the identity of this peer.
 473  */
 474 static struct GNUNET_HashCode my_identity_hash;
 475
 476 /**
 477  * Hash map of all the friends of a peer
 478  */
 479 static struct GNUNET_CONTAINER_MultiPeerMap *friend_peers;
 480
 481 /**
 482  * Hash map of all the fingers of a peer
 483  */
 484 static struct GNUNET_CONTAINER_MultiPeerMap *finger_peers;
 485
 486 /**
 487  * Handle to ATS.
 488  */
 489 static struct GNUNET_ATS_PerformanceHandle *atsAPI;
 490
 491 /**
 492  * Handle to CORE.
 493  */
 494 static struct GNUNET_CORE_Handle *core_api;
 495
 496 /**
 497  * FIXME:where are we using this field.
 498  * The highest finger_id that we have found trail to.
 499  */
 500 static unsigned int finger_id;
 501
 502
 503 /**
 504  * TODO: Check this function again.
 505  * Called when core is ready to send a message we asked for
 506  * out to the destination.
 507  *
 508  * @param cls the 'struct FriendInfo' of the target friend peer
 509  * @param size number of bytes available in buf
 510  * @param buf where the callee should write the message
 511  * @return number of bytes written to buf
 512  */
 513 static size_t
 514 core_transmit_notify (void *cls, size_t size, void *buf)
 515 {
 516   struct FriendInfo *peer = cls;
 517   char *cbuf = buf;
 518   struct P2PPendingMessage *pending;
 519   size_t off;
 520   size_t msize;
 521
 522   peer->th = NULL;
 523   while ((NULL != (pending = peer->head)) &&
 524          (0 == GNUNET_TIME_absolute_get_remaining (pending->timeout).rel_value_us))
 525   {
 526     peer->pending_count--;
 527     GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
 528     GNUNET_free (pending);
 529   }
 530   if (pending == NULL)
 531   {
 532     /* no messages pending */
 533     return 0;
 534   }
 535   if (buf == NULL)
 536   {
 537     peer->th =
 538         GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
 539                                            pending->importance,
 540                                            GNUNET_TIME_absolute_get_remaining
 541                                            (pending->timeout), &peer->id,
 542                                            ntohs (pending->msg->size),
 543                                            &core_transmit_notify, peer);
 544     GNUNET_break (NULL != peer->th);
 545     return 0;
 546   }
 547   off = 0;
 548   while ((NULL != (pending = peer->head)) &&
 549          (size - off >= (msize = ntohs (pending->msg->size))))
 550   {
 551     GNUNET_STATISTICS_update (GDS_stats,
 552                               gettext_noop
 553                               ("# Bytes transmitted to other peers"), msize,
 554                               GNUNET_NO);
 555     memcpy (&cbuf[off], pending->msg, msize);
 556     off += msize;
 557     peer->pending_count--;
 558     GNUNET_CONTAINER_DLL_remove (peer->head, peer->tail, pending);
 559     GNUNET_free (pending);
 560   }
 561   if (peer->head != NULL)
 562   {
 563     peer->th =
 564         GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
 565                                            pending->importance,
 566                                            GNUNET_TIME_absolute_get_remaining
 567                                            (pending->timeout), &peer->id, msize,
 568                                            &core_transmit_notify, peer);
 569     GNUNET_break (NULL != peer->th);
 570   }
 571   return off;
 572 }
 573
 574
 575 /**
 576  * Transmit all messages in the friend's message queue.
 577  *
 578  * @param peer message queue to process
 579  */
 580 static void
 581 process_friend_queue (struct FriendInfo *peer)
 582 {
 583
 584   struct P2PPendingMessage *pending;
 585
 586   if (NULL == (pending = peer->head))
 587     return;
 588   if (NULL != peer->th)
 589     return;
 590   GNUNET_STATISTICS_update (GDS_stats,
 591                             gettext_noop
 592                             ("# Bytes of bandwidth requested from core"),
 593                             ntohs (pending->msg->size), GNUNET_NO);
 594
 595   /*FIXME : here I don't know the use of importance, time out
 596     Will check at run time if its all correct. */
 597   peer->th =
 598       GNUNET_CORE_notify_transmit_ready (core_api, GNUNET_NO,
 599                                          pending->importance,
 600                                          GNUNET_TIME_absolute_get_remaining
 601                                          (pending->timeout), &peer->id,
 602                                          ntohs (pending->msg->size),
 603                                          &core_transmit_notify, peer);
 604   GNUNET_break (NULL != peer->th);
 605 }
 606
 607
 608 /**
 609  * FIXME: Check the parameters.
 610  * Set up the trial message and forwards this message to friend.
 611  *
 612  * @param Finger id to which we want to setup the trail.
 613  * @param Friend id through which we will try to setup the trail.
 614  */
 615 void
 616 GDS_NEIGHBOURS_trail_setup(struct GNUNET_PeerIdentity *finger_id,
 617                                   struct FriendInfo *target_friend)
 618 {
 619   /*
 620    * FIXME: check if pending message actually contains the correct data.
 621    */
 622   struct P2PPendingMessage *pending;
 623   /* FIXME: why I have defined as **? verify by testing. */
 624   struct PeerTrailSetupMessage *tsm;
 625
 626
 627   if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
 628   {
 629     GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped due to full queue"),
 630                                 1, GNUNET_NO);
 631   }
 632
 633   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
 634   tsm = (struct PeerTrailSetupMessage *) &pending[1];
 635   pending->msg = &tsm->header;
 636   tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
 637   tsm->destination_finger = finger_id;
 638   tsm->source_peer = &my_identity;
 639   GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending);
 640   target_friend->pending_count++;
 641   process_friend_queue(target_friend);
 642 }
 643
 644
 645 /**FIXME: Old implementation just to remove error
 646  * TODO: Modify this function to handle our get request.
 647  * Perform a GET operation.  Forwards the given request to other
 648  * peers.  Does not lookup the key locally.  May do nothing if this is
 649  * the only peer in the network (or if we are the closest peer in the
 650  * network).
 651  *
 652  * @param type type of the block
 653  * @param options routing options
 654  * @param desired_replication_level desired replication count
 655  * @param hop_count how many hops did this request traverse so far?
 656  * @param key key for the content
 657  * @param xquery extended query
 658  * @param xquery_size number of bytes in @a xquery
 659  * @param reply_bf bloomfilter to filter duplicates
 660  * @param reply_bf_mutator mutator for @a reply_bf
 661  * @param peer_bf filter for peers not to select (again)
 662  */
 663 void
 664 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
 665                            enum GNUNET_DHT_RouteOption options,
 666                            uint32_t desired_replication_level,
 667                            uint32_t hop_count, const struct GNUNET_HashCode * key,
 668                            const void *xquery, size_t xquery_size,
 669                            const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
 670                            uint32_t reply_bf_mutator,
 671                            struct GNUNET_CONTAINER_BloomFilter *peer_bf)
 672 {
 673
 674 }
 675
 676 /**FIXME: Old implementation just to remove error.
 677  * TODO: Modify this function to handle our put request.
 678  * Perform a PUT operation.   Forwards the given request to other
 679  * peers.   Does not store the data locally.  Does not give the
 680  * data to local clients.  May do nothing if this is the only
 681  * peer in the network (or if we are the closest peer in the
 682  * network).
 683  *
 684  * @param type type of the block
 685  * @param options routing options
 686  * @param desired_replication_level desired replication count
 687  * @param expiration_time when does the content expire
 688  * @param hop_count how many hops has this message traversed so far
 689  * @param bf Bloom filter of peers this PUT has already traversed
 690  * @param key key for the content
 691  * @param put_path_length number of entries in @a put_path
 692  * @param put_path peers this request has traversed so far (if tracked)
 693  * @param data payload to store
 694  * @param data_size number of bytes in @a data
 695  */
 696 void
 697 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
 698                            enum GNUNET_DHT_RouteOption options,
 699                            uint32_t desired_replication_level,
 700                            struct GNUNET_TIME_Absolute expiration_time,
 701                            uint32_t hop_count,
 702                            struct GNUNET_CONTAINER_BloomFilter *bf,
 703                            const struct GNUNET_HashCode *key,
 704                            unsigned int put_path_length,
 705                            struct GNUNET_PeerIdentity *put_path,
 706                            const void *data, size_t data_size)
 707 {
 708
 709 }
 710
 711
 712 /**FIXME: Old implementation just to remove error.
 713  * Handle a reply (route to origin).  Only forwards the reply back to
 714  * other peers waiting for it.  Does not do local caching or
 715  * forwarding to local clients.
 716  *
 717  * @param target neighbour that should receive the block (if still connected)
 718  * @param type type of the block
 719  * @param expiration_time when does the content expire
 720  * @param key key for the content
 721  * @param put_path_length number of entries in put_path
 722  * @param put_path peers the original PUT traversed (if tracked)
 723  * @param get_path_length number of entries in put_path
 724  * @param get_path peers this reply has traversed so far (if tracked)
 725  * @param data payload of the reply
 726  * @param data_size number of bytes in data
 727  */
 728 void
 729 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
 730                              enum GNUNET_BLOCK_Type type,
 731                              struct GNUNET_TIME_Absolute expiration_time,
 732                              const struct GNUNET_HashCode * key,
 733                              unsigned int put_path_length,
 734                              const struct GNUNET_PeerIdentity *put_path,
 735                              unsigned int get_path_length,
 736                              const struct GNUNET_PeerIdentity *get_path,
 737                              const void *data, size_t data_size)
 738 {
 739
 740 }
 741
 742
 743 /**
 744  * SUPU: Check again.
 745  * I have written a code where
 746  * 1. I choose a random index from 0 to current size of my map.
 747  * 2. Create an iterator.
 748  * 3. set the iterator value to the current index id.
 749  * 4. get the element stored at that index id.
 750  * 5. return the index to calling function.
 751  * I have not yet tested this function and I am not sure if its correct.
 752  * Randomly choose one of your friends from the friends_peer map
 753  * @return Friend
 754  */
 755 static struct FriendInfo *
 756 get_random_friend()
 757 {
 758   unsigned int current_size;
 759   unsigned int *index;
 760   unsigned int j = 0;
 761   struct GNUNET_CONTAINER_MultiPeerMapIterator *iter;
 762   struct GNUNET_PeerIdentity key_ret;
 763   struct FriendInfo *friend;
 764
 765   current_size = GNUNET_CONTAINER_multipeermap_size(friend_peers);
 766
 767   /* Element stored at this index in friend_peers map should be chosen friend. */
 768   index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size);
 769
 770   /* Create an iterator for friend_peers map. */
 771   iter = GNUNET_CONTAINER_multipeermap_iterator_create(friend_peers);
 772
 773   /* Set the position of iterator to index. */
 774   while(j < (*index))
 775   {
 776       if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,NULL,NULL))
 777         j++;
 778       else
 779         return NULL;
 780   }
 781
 782   if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(iter,&key_ret,(const void **)&friend))
 783   {
 784       return friend;
 785   }
 786
 787   return NULL;
 788 }
 789
 790
 791 /**
 792  * TODO: Complete this function.
 793  * Use Chord formula finger[i]=(n+2^(i-1))mod m,
 794  * where i = current finger map index.
 795  * n = own peer identity
 796  * m = number of bits in peer id.
 797  * @return finger_peer_id for which we have to find the trail through network.
 798  */
 799 static
 800 struct GNUNET_PeerIdentity *
 801 finger_id_to_search()
 802 {
 803
 804   //struct GNUNET_PeerIdentity *finger_peer_id;
 805
 806   /*TODO: Add a wrapper in crypto_ecc.c to add an integer do mod operation on integer
 807     to find peer id. Take care of parameters. You should work on the value of
 808    finger_id not on its pointer.
 809    Increment the value of finger_id. */
 810
 811   //return finger_peer_id;
 812   return NULL;
 813 }
 814
 815
 816 /**
 817  * FIXME: Implement after testing friend/finger map.
 818  * This function will be needed when we are handling node joins/fails
 819  * to maintain correct pointer to our predecessor and successor in the network.
 820  * Find immediate predecessor in the network.
 821  * @param me my own identity
 822  * @return peer identity of immediate predecessor.
 823  */
 824 static
 825 struct GNUNET_PeerIdentity*
 826 find_immediate_predecessor()
 827 {
 828     /* Using your own peer identity, calculate your predecessor
 829      in the network. Try to setup path to this predecessor using
 830      the same logic as used for other fingers. */
 831     return NULL;
 832 }
 833
 834
 835 /**
 836  * Task to send a find finger trail message. We attempt to find trail
 837  * to our finger in the network.
 838  *
 839  * @param cls closure for this task
 840  * @param tc the context under which the task is running
 841  */
 842 static void
 843 send_find_finger_trail_message (void *cls,
 844                         const struct GNUNET_SCHEDULER_TaskContext *tc)
 845 {
 846   struct GNUNET_PeerIdentity *finger_peer_id;
 847   struct FriendInfo *friend_peer_id;
 848   struct GNUNET_TIME_Relative next_send_time;
 849
 850   /* We already have found trail to each of our possible fingers in the network. */
 851   if (GNUNET_CONTAINER_multipeermap_size(finger_peers) == MAX_FINGERS)
 852   {
 853     /* We can find trail to our immediate predecessor in the network. */
 854     finger_peer_id = find_immediate_predecessor();
 855   }
 856   else
 857   {
 858     /* Find the finger_peer_id for which we want to setup the trial */
 859     finger_peer_id = finger_id_to_search();
 860   }
 861
 862   /* Choose a friend randomly from your friend_peers map. */
 863   friend_peer_id = get_random_friend();
 864
 865   /* Check if we found a friend or not. */
 866   if(NULL != friend_peer_id)
 867     GDS_NEIGHBOURS_trail_setup(finger_peer_id, friend_peer_id);
 868
 869
 870   next_send_time.rel_value_us =
 871       DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
 872       GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
 873                                 DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
 874                                 (finger_id + 1));
 875
 876   find_finger_trail_task =
 877       GNUNET_SCHEDULER_add_delayed (next_send_time, &send_find_finger_trail_message,
 878                                     NULL);
 879 }
 880
 881
 882 /**
 883  * Method called whenever a peer connects.
 884  *
 885  * @param cls closure
 886  * @param peer peer identity this notification is about
 887  */
 888 static void
 889 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer)
 890 {
 891   struct FriendInfo *ret;
 892
 893   /* Check for connect to self message */
 894   if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity)))
 895     return;
 896
 897   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 898               "Connected to %s\n",
 899               GNUNET_i2s (peer));
 900
 901   /* If peer already exists in our friend_peers, then exit. */
 902   if (GNUNET_YES ==
 903       GNUNET_CONTAINER_multipeermap_contains (friend_peers,
 904                                               peer))
 905   {
 906     GNUNET_break (0);
 907     return;
 908   }
 909
 910   GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# peers connected"), 1,
 911                             GNUNET_NO);
 912
 913   ret = GNUNET_new (struct FriendInfo);
 914   ret->id = *peer;
 915
 916   GNUNET_assert (GNUNET_OK ==
 917                  GNUNET_CONTAINER_multipeermap_put (friend_peers,
 918                                                     peer, ret,
 919                                                     GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 920
 921   /* got a first connection, good time to start with FIND FINGER TRAIL requests... */
 922   if (1 == GNUNET_CONTAINER_multipeermap_size(friend_peers))
 923    find_finger_trail_task = GNUNET_SCHEDULER_add_now (&send_find_finger_trail_message, NULL);
 924 }
 925
 926
 927 /**
 928  * FIXME: Implement after testing finger/friend table setup.
 929  * Method called whenever a peer disconnects.
 930  *
 931  * @param cls closure
 932  * @param peer peer identity this notification is about
 933  */
 934 static void
 935 handle_core_disconnect (void *cls,
 936                         const struct GNUNET_PeerIdentity *peer)
 937 {
 938   /**
 939    * 1. remove the friend from the friend map.
 940    * 2. remove the trail for the fingers for which this peer was the first hop.
 941    * 3. start send_find_finger_trail for these fingers to find a new trail
 942    * in the network.
 943    * 4. Also when a node gets disconnected, how should we update pointers of its
 944    * immediate successor and predecessor in the network ?
 945    * 5. Also how do we distribute the keys in the network?
 946    * 6. Here is case where we started put operation but a peer got disconnected and
 947       we removed the entry from the table. How to handle such a case.
 948    */
 949
 950 }
 951
 952
 953 /**
 954  * To be called on core init/fail.
 955  *
 956  * @param cls service closure
 957  * @param identity the public identity of this peer
 958  */
 959 static void
 960 core_init (void *cls,
 961            const struct GNUNET_PeerIdentity *identity)
 962 {
 963   my_identity = *identity;
 964   GNUNET_CRYPTO_hash (identity,
 965                       sizeof (struct GNUNET_PeerIdentity),
 966                       &my_identity_hash);
 967 }
 968
 969
 970 /**
 971  * Core handler for p2p put requests.
 972  *
 973  * @param cls closure
 974  * @param peer sender of the request
 975  * @param message message
 976  * @param peer peer identity this notification is about
 977  * @return #GNUNET_OK to keep the connection open,
 978  *         #GNUNET_SYSERR to close it (signal serious error)
 979  */
 980 static int
 981 handle_dht_p2p_put (void *cls,
 982                     const struct GNUNET_PeerIdentity *peer,
 983                     const struct GNUNET_MessageHeader *message)
 984 {
 985     /**
 986      1. Search the friend,finger and check your own id to find the closest
 987      * predecessor the given key. --> find_predecessor()
 988      2. If self then datache_store
 989      3. If friend, then add to peer queue
 990      4. If finger, then add to the peer queue of the first hop.
 991      * in put message also maintain a field current_destination and use
 992      * same logic as trail setup to understand if you are just part of trail
 993      * to reach to a particular peer or you are endpoint of trail or just a friend.
 994      *
 995      */
 996     return 0;
 997 }
 998
 999
1000 /**
1001  * Core handler for p2p get requests.
1002  *
1003  * @param cls closure
1004  * @param peer sender of the request
1005  * @param message message
1006  * @return #GNUNET_OK to keep the connection open,
1007  *         #GNUNET_SYSERR to close it (signal serious error)
1008  */
1009 static int
1010 handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer,
1011                     const struct GNUNET_MessageHeader *message)
1012 {
1013     return 0;
1014 }
1015
1016
1017 /**
1018  * Core handler for p2p result messages.
1019  *
1020  * @param cls closure
1021  * @param message message
1022  * @param peer peer identity this notification is about
1023  * @return #GNUNET_YES (do not cut p2p connection)
1024  */
1025 static int
1026 handle_dht_p2p_result (void *cls, const struct GNUNET_PeerIdentity *peer,
1027                        const struct GNUNET_MessageHeader *message)
1028 {
1029     return 0;
1030 }
1031
1032
1033 /**
1034  * Read the trail setup message backwards to find which is the next hop to which
1035  * it should be send to.
1036  * @return
1037
1038 static
1039 struct GNUNET_PeerIdentity *
1040 find_next_hop()
1041 {
1042     return NULL;
1043 }*/
1044
1045
1046 /**
1047  * FIXME:
1048  * Are we comparing the predecessor with our own identity also.
1049  * Its important.
1050  * Here also we would be comparing the numeric value of
1051  * peer identity. We read the element from our map. Extract
1052  * the peer id and compare it with destination id. But again
1053  * this comparison is on values. Same issue again.
1054  * Find the predecessor for given finger_id from the
1055  * friend and finger table.
1056  * if friend, then just return the friend
1057  * if finger, then return the next hop to forward the packet to and also
1058  * set the current_destination field to finger_id.
1059  * @param destination peer id's predecessor we are looking for.
1060  * @return
1061  */
1062 static struct GNUNET_PeerIdentity *
1063 find_successor(struct GNUNET_PeerIdentity *destination)
1064 {
1065   unsigned int friend_index;
1066   unsigned int finger_index;
1067   struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
1068   struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
1069   struct GNUNET_PeerIdentity key_ret;
1070   struct FriendInfo *friend;
1071   struct FingerInfo *finger;
1072
1073   /* Should I keep a variable to remember if GNUNET_PeerIdentity is
1074    friend or finger. */
1075   friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peers);
1076
1077   /*iterate over friend map till you reach a peer id such that destination <= peer id */
1078   for (friend_index = 0; friend_index < GNUNET_CONTAINER_multipeermap_size (friend_peers); friend_index++)
1079   {
1080       if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void **)&friend))
1081       {
1082           /*
1083            * 1. Check if friend >= destination.
1084            * 2. If yes then check if friend <= current_predecessor,
1085            *    if yes then curret_predecessor = friend.
1086            * 3 If not then do nothing.
1087            */
1088       }
1089   }
1090
1091
1092   finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peers);
1093   /*iterate over finger map till you reach a peer id such that destination <= peer id */
1094   for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (friend_peers); finger_index++)
1095   {
1096     if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void **)&finger))
1097     {
1098       /*
1099        * 1. Check if finger >= destination.
1100        * 2. If yes then check if finger <= current_predecessor,
1101        *    if yes then curret_predecessor = finger.
1102        * 3 If not then do nothing.
1103        */
1104     }
1105   }
1106
1107
1108   /* Check between friend and finger value to decide which is the predecessor.
1109      If friend, then send the friend id.
1110      If finger, then send the next hop. */
1111   return NULL;
1112 }
1113
1114
1115 /**
1116  * FIXME:
1117  * 1. Check if we are maintaining the 64k size of struct PeerTrailSetupMessage.
1118  * when we add ourself to the trail list.
1119  * 2. Ensure every case is handled for current_destination.
1120  * Core handler for P2P trail setup message.
1121  * @param cls closure
1122  * @param message message
1123  * @param peer peer identity this notification is about
1124  * @return #GNUNET_YES
1125  */
1126 static int
1127 handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer,
1128                     const struct GNUNET_MessageHeader *message)
1129 {
1130   const struct PeerTrailSetupMessage *trail_setup;
1131   struct GNUNET_PeerIdentity *next_hop;
1132   struct FriendInfo *friend;
1133   struct TrailPeerList *peer_entry;
1134   struct P2PPendingMessage *pending;
1135
1136   uint16_t msize;
1137
1138   msize = ntohs (message->size);
1139   if (msize < sizeof (struct PeerTrailSetupMessage))
1140   {
1141     GNUNET_break_op (0);
1142     return GNUNET_YES;
1143   }
1144
1145   trail_setup = (const struct PeerTrailSetupMessage *) message;
1146
1147   GNUNET_STATISTICS_update (GDS_stats,
1148                             gettext_noop ("# TRAIL SETUP requests received"), 1,
1149                             GNUNET_NO);
1150   GNUNET_STATISTICS_update (GDS_stats,
1151                             gettext_noop ("# TRAIL SETUP bytes received"), msize,
1152                             GNUNET_NO);
1153
1154
1155   /* Check the value of current_destination and handle the respective case. */
1156   if(trail_setup->current_destination == NULL)
1157   {
1158     /* Find the next peer to pass the trail setup message. */
1159     next_hop = find_successor(trail_setup->destination_finger);
1160   }
1161   else if( 0 == (GNUNET_CRYPTO_cmp_peer_identity(trail_setup->current_destination,&my_identity)))
1162   {
1163     /* I am current destination, find the next peer to pass the trail setup message. */
1164     next_hop = find_successor(trail_setup->destination_finger);
1165   }
1166   else
1167   {
1168     /* I am part of the trail to reach to current_destination. */
1169     next_hop = GDS_Routing_search(trail_setup->source_peer, trail_setup->current_destination, trail_setup->tail->peer);
1170   }
1171
1172
1173   if(0 == (GNUNET_CRYPTO_cmp_peer_identity(next_hop,&my_identity)))
1174   {
1175     /* I am the closest successor of the destination finger in the network. */
1176     /*SUPU::
1177       1. Prepare a trail setup result message.
1178       2. Add yourself to trail list.
1179       3. send packet to last element in the list.
1180     */
1181     return GNUNET_YES;
1182   }
1183
1184   /* Insert next hop into trial list. */
1185   peer_entry = GNUNET_malloc (sizeof (struct TrailPeerList));
1186   peer_entry->peer = &my_identity;
1187   peer_entry->next = NULL;
1188   peer_entry->prev = NULL;
1189
1190   /*SUPU what is this stupid code that I have written. */
1191   GNUNET_CONTAINER_DLL_insert_tail(trail_setup->head->next,trail_setup->tail->prev,peer_entry);
1192
1193   /* Find the struct FriendInfo for next_hop peer id. */
1194   friend = GNUNET_CONTAINER_multipeermap_get(friend_peers,next_hop);
1195
1196   /* Send trail setup message to next hop friend. */
1197   pending = GNUNET_malloc (sizeof (struct P2PPendingMessage));
1198   GNUNET_CONTAINER_DLL_insert_tail (friend->head, friend->tail, pending);
1199   friend->pending_count++;
1200   process_friend_queue(friend);
1201   return GNUNET_YES;
1202 }
1203
1204
1205 /**
1206  * Core handle for p2p trail construction result messages.
1207  * @param cls closure
1208  * @param message message
1209  * @param peer peer identity this notification is about
1210  * @return #GNUNET_YES (do not cut p2p connection)
1211  * @return
1212  */
1213 static int
1214 handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *peer,
1215                     const struct GNUNET_MessageHeader *message)
1216 {
1217   /**
1218    * Just read the linked list backwards and send the packet to next hop
1219    * till you don't reach the source
1220    * but if you are source, then add an entry in finger table for given finger id.
1221    *
1222    *
1223    */
1224   //const struct PeerTrailSetupResultMessage *trail_result;
1225   //trail_result = (const struct PeerTrailSetupResultMessage *) message;
1226
1227   /*FIXME: This code is wrong, I am writing just to understand the flow,
1228   if(trail_result->destination == message->destination)
1229   {
1230     This condition holds true, then we should add an entry in our
1231     routing table and store this finger and its trail.
1232     struct finger_info = with interval .
1233     GNUNET_multipeer_map_insert(finger_map)
1234      * GDS_Routing_add();
1235   }
1236   else
1237   {
1238     Read the trail list, Check the next_hop and pass the packet to it.
1239     FIXME: Should we an entry in our own routing table.
1240   }*/
1241
1242   return 0;
1243 }
1244
1245
1246 /**
1247  * Initialize neighbours subsystem.
1248  * @return GNUNET_OK on success, GNUNET_SYSERR on error
1249  */
1250 int
1251 GDS_NEIGHBOURS_init()
1252 {
1253   static struct GNUNET_CORE_MessageHandler core_handlers[] = {
1254     {&handle_dht_p2p_get, GNUNET_MESSAGE_TYPE_DHT_P2P_GET, 0},
1255     {&handle_dht_p2p_put, GNUNET_MESSAGE_TYPE_DHT_P2P_PUT, 0},
1256     {&handle_dht_p2p_result, GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT, 0},
1257     {&handle_dht_p2p_trail_setup, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP, 0},
1258     {&handle_dht_p2p_trail_setup_result, GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP_RESULT, 0},
1259     {NULL, 0, 0}
1260   };
1261
1262   atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL);
1263   core_api =
1264     GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect,
1265                            &handle_core_disconnect, NULL, GNUNET_NO, NULL,
1266                            GNUNET_NO, core_handlers);
1267   if (core_api == NULL)
1268     return GNUNET_SYSERR;
1269
1270   friend_peers = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1271   finger_peers = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1272
1273
1274   return GNUNET_OK;
1275
1276 }
1277
1278
1279 /**
1280  * Shutdown neighbours subsystem.
1281  */
1282 void
1283 GDS_NEIGHBOURS_done ()
1284 {
1285   if (NULL == core_api)
1286     return;
1287   GNUNET_CORE_disconnect (core_api);
1288   core_api = NULL;
1289   GNUNET_ATS_performance_done (atsAPI);
1290   atsAPI = NULL;
1291
1292   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peers));
1293   GNUNET_CONTAINER_multipeermap_destroy (friend_peers);
1294   friend_peers = NULL;
1295
1296   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peers));
1297   GNUNET_CONTAINER_multipeermap_destroy (finger_peers);
1298   finger_peers = NULL;
1299
1300   if (GNUNET_SCHEDULER_NO_TASK != find_finger_trail_task)
1301   {
1302     GNUNET_SCHEDULER_cancel (find_finger_trail_task);
1303     find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK;
1304   }
1305 }
1306
1307
1308 /**
1309  * Get the ID of the local node.
1310  *
1311  * @return identity of the local node
1312  */
1313 struct GNUNET_PeerIdentity *
1314 GDS_NEIGHBOURS_get_id ()
1315 {
1316     return &my_identity;
1317 }
1318
1319
1320 /* end of gnunet-service-xdht_neighbours.c */