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