src/dht/gnunet-service-wdht_neighbours.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2009-2015 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  * @file dht/gnunet-service-wdht_neighbours.c
  22  * @brief GNUnet DHT service's finger and friend table management code
  23  * @author Supriti Singh
  24  */
  25 #include "platform.h"
  26 #include "gnunet_util_lib.h"
  27 #include "gnunet_block_lib.h"
  28 #include "gnunet_hello_lib.h"
  29 #include "gnunet_constants.h"
  30 #include "gnunet_protocols.h"
  31 #include "gnunet_ats_service.h"
  32 #include "gnunet_core_service.h"
  33 #include "gnunet_datacache_lib.h"
  34 #include "gnunet_transport_service.h"
  35 #include "gnunet_dht_service.h"
  36 #include "gnunet_statistics_service.h"
  37 #include "gnunet-service-wdht.h"
  38 #include "gnunet-service-wdht_clients.h"
  39 #include "gnunet-service-wdht_datacache.h"
  40 #include "gnunet-service-wdht_neighbours.h"
  41 #include "gnunet-service-wdht_nse.h"
  42 #include <fenv.h>
  43 #include <stdlib.h>
  44 #include <string.h>
  45 #include "dht.h"
  46
  47 #define DEBUG(...)                                           \
  48   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
  49
  50 /**
  51  * Trail timeout. After what time do trails always die?
  52  */
  53 #define TRAIL_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 42)
  54
  55 /**
  56  * Random walk delay. How often do we walk the overlay?
  57  */
  58 #define RANDOM_WALK_DELAY GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 42)
  59
  60 /**
  61  * The number of layered ID to use.
  62  */
  63 #define NUMBER_LAYERED_ID 8
  64
  65 /**
  66  * The number of random walk to launch at the beginning of the initialization
  67  */
  68 /* FIXME: find a better value */
  69 #define NUMBER_RANDOM_WALK 20
  70
  71
  72 /******************* The db structure and related functions *******************/
  73
  74 /**
  75  * Entry in #friends_peermap.
  76  */
  77 struct FriendInfo;
  78
  79
  80 /**
  81  * Information we keep per trail.
  82  */
  83 struct Trail
  84 {
  85
  86   /**
  87    * MDLL entry in the list of all trails with the same predecessor.
  88    */
  89   struct Trail *prev_succ;
  90
  91   /**
  92    * MDLL entry in the list of all trails with the same predecessor.
  93    */
  94   struct Trail *next_succ;
  95
  96   /**
  97    * MDLL entry in the list of all trails with the same predecessor.
  98    */
  99   struct Trail *prev_pred;
 100
 101   /**
 102    * MDLL entry in the list of all trails with the same predecessor.
 103    */
 104   struct Trail *next_pred;
 105
 106   /**
 107    * Our predecessor in the trail, NULL if we are initiator (?).
 108    */
 109   struct FriendInfo *pred;
 110
 111   /**
 112    * Our successor in the trail, NULL if we are the last peer.
 113    */
 114   struct FriendInfo *succ;
 115
 116   /**
 117    * Identifier of the trail with the predecessor.
 118    */
 119   struct GNUNET_HashCode pred_id;
 120
 121   /**
 122    * Identifier of the trail with the successor.
 123    */
 124   struct GNUNET_HashCode succ_id;
 125
 126   /**
 127    * When does this trail expire.
 128    */
 129   struct GNUNET_TIME_Absolute expiration_time;
 130
 131   /**
 132    * Location of this trail in the heap.
 133    */
 134   struct GNUNET_CONTAINER_HeapNode *hn;
 135
 136   /**
 137    * If this peer started the to create a Finger (and thus @e pred is
 138    * NULL), this is the Finger we are trying to intialize.
 139    */
 140   struct Finger **finger;
 141
 142 };
 143
 144
 145 /**
 146  *  Entry in #friends_peermap.
 147  */
 148 struct FriendInfo
 149 {
 150   /**
 151    * Friend Identity
 152    */
 153   struct GNUNET_PeerIdentity id;
 154
 155   struct Trail *pred_head;
 156
 157   struct Trail *pred_tail;
 158
 159   struct Trail *succ_head;
 160
 161   struct Trail *succ_tail;
 162
 163   /**
 164    * Core handle for sending messages to this friend.
 165    */
 166   struct GNUNET_MQ_Handle *mq;
 167
 168 };
 169
 170
 171 struct FingerTable;
 172
 173
 174 struct Finger
 175 {
 176   struct Trail *trail;
 177
 178   struct FingerTable *ft;
 179
 180   struct GNUNET_HashCode destination;
 181
 182   /**
 183    * #GNUNET_YES if a response has been received. Otherwise #GNUNET_NO.
 184    */
 185   int valid;
 186 };
 187
 188
 189 struct FingerTable
 190 {
 191   /**
 192    * Array of our fingers, unsorted.
 193    */
 194   struct Finger **fingers;
 195
 196   /**
 197    * Array of sorted fingers (sorted by destination, valid fingers first).
 198    */
 199   struct Finger **sorted_fingers;
 200
 201   /**
 202    * Size of the finger array.
 203    */
 204   unsigned int finger_array_size;
 205
 206   /**
 207    * Number of valid entries in @e sorted_fingers (contiguous from offset 0)
 208    */
 209   unsigned int number_valid_fingers;
 210
 211   /**
 212    * Which offset in @e fingers will we redo next.
 213    */
 214   unsigned int walk_offset;
 215
 216   /**
 217    * Is the finger array sorted?
 218    */
 219   int is_sorted;
 220
 221 };
 222
 223
 224 /***********************  end of the db structure part  ***********************/
 225
 226
 227 GNUNET_NETWORK_STRUCT_BEGIN
 228
 229 /**
 230  * Setup a finger using the underlay topology ("social network").
 231  */
 232 struct RandomWalkMessage
 233 {
 234   /**
 235    * Type: #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK
 236    */
 237   struct GNUNET_MessageHeader header;
 238
 239   /**
 240    * Number of hops this message has taken so far, we stop at
 241    * log(NSE), in NBO.
 242    */
 243   uint16_t hops_taken GNUNET_PACKED;
 244
 245   /**
 246    * Layer for the request, in NBO.
 247    */
 248   uint16_t layer GNUNET_PACKED;
 249
 250   /**
 251    * Unique (random) identifier this peer will use to
 252    * identify the trail (in future messages).
 253    */
 254   struct GNUNET_HashCode trail_id;
 255
 256 };
 257
 258 /**
 259  * Response to a `struct RandomWalkMessage`.
 260  */
 261 struct RandomWalkResponseMessage
 262 {
 263   /**
 264    * Type: #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE
 265    */
 266   struct GNUNET_MessageHeader header;
 267
 268   /**
 269    * Zero, for alignment.
 270    */
 271   uint32_t reserved GNUNET_PACKED;
 272
 273   /**
 274    * Unique (random) identifier from the
 275    * `struct RandomWalkMessage`.
 276    */
 277   struct GNUNET_HashCode trail_id;
 278
 279   /**
 280    * Random location in the respective layer where the
 281    * random path of the finger setup terminated.
 282    */
 283   struct GNUNET_HashCode location;
 284
 285 };
 286
 287 /**
 288  * Response to an event that causes a trail to die.
 289  */
 290 struct TrailDestroyMessage
 291 {
 292   /**
 293    * Type: #GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY
 294    */
 295   struct GNUNET_MessageHeader header;
 296
 297   /**
 298    * Zero, for alignment.
 299    */
 300   uint32_t reserved GNUNET_PACKED;
 301
 302   /**
 303    * Unique (random) identifier this peer will use to
 304    * identify the finger (in future messages).
 305    */
 306   struct GNUNET_HashCode trail_id;
 307
 308 };
 309
 310
 311 /**
 312  * Send a message along a trail.
 313  */
 314 struct FindSuccessorMessage
 315 {
 316   /**
 317    * Type: #GNUNET_MESSAGE_TYPE_WDHT_FIND_SUCCESSOR
 318    */
 319   struct GNUNET_MessageHeader header;
 320
 321   /**
 322    * Zero, for alignment.
 323    */
 324   uint32_t reserved GNUNET_PACKED;
 325
 326   /**
 327    * Unique (random) identifier this peer will use to
 328    * identify the finger (in future messages).
 329    */
 330   struct GNUNET_HashCode trail_id;
 331
 332   /**
 333    * Key for which we would like close values returned.
 334    * identify the finger (in future messages).
 335    */
 336   struct GNUNET_HashCode key;
 337
 338 };
 339
 340
 341 /**
 342  * Send a message along a trail.
 343  */
 344 struct TrailRouteMessage
 345 {
 346   /**
 347    * Type: #GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE
 348    */
 349   struct GNUNET_MessageHeader header;
 350
 351   /**
 352    * Zero, for alignment.
 353    */
 354   uint32_t reserved GNUNET_PACKED;
 355
 356   /**
 357    * Unique (random) identifier this peer will use to
 358    * identify the finger (in future messages).
 359    */
 360   struct GNUNET_HashCode trail_id;
 361
 362   /* followed by payload to send along the trail */
 363 };
 364
 365
 366 /**
 367  * P2P PUT message
 368  */
 369 struct PeerPutMessage
 370 {
 371   /**
 372    * Type: #GNUNET_MESSAGE_TYPE_WDHT_PUT
 373    */
 374   struct GNUNET_MessageHeader header;
 375
 376   /**
 377    * Processing options
 378    */
 379   uint32_t options GNUNET_PACKED;
 380
 381   /**
 382    * Content type.
 383    */
 384   uint32_t block_type GNUNET_PACKED;
 385
 386   /**
 387    * Hop count
 388    */
 389   uint32_t hop_count GNUNET_PACKED;
 390
 391   /**
 392    * Replication level for this message
 393    * In the current implementation, this value is not used.
 394    */
 395   uint32_t desired_replication_level GNUNET_PACKED;
 396
 397   /**
 398    * Length of the PUT path that follows (if tracked).
 399    */
 400   uint32_t put_path_length GNUNET_PACKED;
 401
 402   /**
 403    * When does the content expire?
 404    */
 405   struct GNUNET_TIME_AbsoluteNBO expiration_time;
 406
 407   /**
 408    * The key to store the value under.
 409    */
 410   struct GNUNET_HashCode key GNUNET_PACKED;
 411
 412   /* put path (if tracked) */
 413
 414   /* Payload */
 415
 416 };
 417
 418 /**
 419  * P2P GET message
 420  */
 421 struct PeerGetMessage
 422 {
 423   /**
 424    * Type: #GNUNET_MESSAGE_TYPE_WDHT_GET
 425    */
 426   struct GNUNET_MessageHeader header;
 427
 428   /**
 429    * Processing options
 430    */
 431   uint32_t options GNUNET_PACKED;
 432
 433   /**
 434    * Desired content type.
 435    */
 436   uint32_t block_type GNUNET_PACKED;
 437
 438   /**
 439    * Hop count
 440    */
 441   uint32_t hop_count GNUNET_PACKED;
 442
 443   /**
 444    * Desired replication level for this request.
 445    * In the current implementation, this value is not used.
 446    */
 447   uint32_t desired_replication_level GNUNET_PACKED;
 448
 449   /**
 450    * Total number of peers in get path.
 451    */
 452   unsigned int get_path_length;
 453
 454   /**
 455    * The key we are looking for.
 456    */
 457   struct GNUNET_HashCode key;
 458
 459   /* Get path. */
 460   /* struct GNUNET_PeerIdentity[]*/
 461 };
 462
 463
 464 /**
 465  * P2P Result message
 466  */
 467 struct PeerGetResultMessage
 468 {
 469   /**
 470    * Type: #GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT
 471    */
 472   struct GNUNET_MessageHeader header;
 473
 474   /**
 475    * The type for the data.
 476    */
 477   uint32_t type GNUNET_PACKED;
 478
 479   /**
 480    * Number of peers recorded in the outgoing path from source to the
 481    * stored location of this message.
 482    */
 483   uint32_t put_path_length GNUNET_PACKED;
 484
 485   /**
 486    * Length of the GET path that follows (if tracked).
 487    */
 488   uint32_t get_path_length GNUNET_PACKED;
 489
 490   /**
 491    * Peer which queried for get and should get the result.
 492    */
 493   struct GNUNET_PeerIdentity querying_peer;
 494
 495   /**
 496    * When does the content expire?
 497    */
 498   struct GNUNET_TIME_Absolute expiration_time;
 499
 500   /**
 501    * The key of the corresponding GET request.
 502    */
 503   struct GNUNET_HashCode key;
 504
 505   /* put path (if tracked) */
 506
 507   /* get path (if tracked) */
 508
 509   /* Payload */
 510
 511 };
 512
 513 GNUNET_NETWORK_STRUCT_END
 514
 515
 516 /**
 517  * Contains all the layered IDs of this peer.
 518  */
 519 struct GNUNET_PeerIdentity layered_id[NUMBER_LAYERED_ID];
 520
 521 /**
 522  * Task to timeout trails that have expired.
 523  */
 524 static struct GNUNET_SCHEDULER_Task *trail_timeout_task;
 525
 526 /**
 527  * Task to perform random walks.
 528  */
 529 static struct GNUNET_SCHEDULER_Task *random_walk_task;
 530
 531 /**
 532  * Identity of this peer.
 533  */
 534 static struct GNUNET_PeerIdentity my_identity;
 535
 536 /**
 537  * Peer map of all the friends of a peer
 538  */
 539 static struct GNUNET_CONTAINER_MultiPeerMap *friends_peermap;
 540
 541 /**
 542  * Fingers per layer.
 543  */
 544 static struct FingerTable fingers[NUMBER_LAYERED_ID];
 545
 546 /**
 547  * Tail map, mapping tail identifiers to `struct Trail`s
 548  */
 549 static struct GNUNET_CONTAINER_MultiHashMap *trail_map;
 550
 551 /**
 552  * Tail heap, organizing trails by expiration time.
 553  */
 554 static struct GNUNET_CONTAINER_Heap *trail_heap;
 555
 556 /**
 557  * Handle to CORE.
 558  */
 559 static struct GNUNET_CORE_Handle *core_api;
 560
 561
 562 /**
 563  * Handle the put request from the client.
 564  *
 565  * @param key Key for the content
 566  * @param block_type Type of the block
 567  * @param options Routing options
 568  * @param desired_replication_level Desired replication count
 569  * @param expiration_time When does the content expire
 570  * @param data Content to store
 571  * @param data_size Size of content @a data in bytes
 572  */
 573 void
 574 GDS_NEIGHBOURS_handle_put (const struct GNUNET_HashCode *key,
 575                            enum GNUNET_BLOCK_Type block_type,
 576                            enum GNUNET_DHT_RouteOption options,
 577                            uint32_t desired_replication_level,
 578                            struct GNUNET_TIME_Absolute expiration_time,
 579                            const void *data, size_t data_size)
 580 {
 581   GDS_DATACACHE_handle_put (expiration_time,
 582                             key,
 583                             0, NULL,
 584                             block_type,
 585                             data_size,
 586                             data);
 587 }
 588
 589
 590 /**
 591  * Handle the get request from the client file. If I am destination do
 592  * datacache put and return. Else find the target friend and forward message
 593  * to it.
 594  *
 595  * @param key Key for the content
 596  * @param block_type Type of the block
 597  * @param options Routing options
 598  * @param desired_replication_level Desired replication count
 599  */
 600 void
 601 GDS_NEIGHBOURS_handle_get (const struct GNUNET_HashCode *key,
 602                            enum GNUNET_BLOCK_Type block_type,
 603                            enum GNUNET_DHT_RouteOption options,
 604                            uint32_t desired_replication_level)
 605 {
 606   // find closest finger(s) on all layers
 607   // use TrailRoute with PeerGetMessage embedded to contact peer
 608 }
 609
 610
 611 /**
 612  * Delete a trail, it died (timeout, link failure, etc.).
 613  *
 614  * @param trail trail to delete from all data structures
 615  * @param inform_pred should we notify the predecessor?
 616  * @param inform_succ should we inform the successor?
 617  */
 618 static void
 619 delete_trail (struct Trail *trail,
 620               int inform_pred,
 621               int inform_succ)
 622 {
 623   struct FriendInfo *friend;
 624   struct GNUNET_MQ_Envelope *env;
 625   struct TrailDestroyMessage *tdm;
 626   struct Trail *current;
 627
 628   tdm = GNUNET_new(struct TrailDestroyMessage);
 629   current = trail;
 630
 631   if (inform_pred)
 632   {
 633     struct Trail *previous_pred;
 634     struct Trail *next_pred;
 635     tdm->trail_id = current->pred_id;
 636     friend = current->pred;
 637
 638     while( NULL != current)
 639     {
 640       if (NULL != friend)
 641       {
 642         env = GNUNET_MQ_msg (tdm,
 643                              GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
 644         GNUNET_MQ_send (friend->mq,
 645                         env);
 646       }
 647
 648       next_pred = current->next_pred;
 649       previous_pred = current->prev_pred;
 650
 651       /* Freeing current trail memory */
 652       GNUNET_free(current);
 653
 654       /* Destroying the next successor list */
 655       while(NULL != previous_pred)
 656       {
 657         struct Trail *tmp;
 658         if (NULL != friend)
 659         {
 660           env = GNUNET_MQ_msg (tdm,
 661                                GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
 662           GNUNET_MQ_send (friend->mq,
 663                           env);
 664         }
 665
 666         tmp = next_pred;
 667         next_pred = next_pred->next_pred;
 668         GNUNET_free(tmp);
 669       }
 670
 671       /* Destroying the next predecessor list */
 672       while(NULL != next_pred)
 673       {
 674         struct Trail *tmp;
 675         if (NULL != friend)
 676         {
 677           env = GNUNET_MQ_msg (tdm,
 678                                GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
 679           GNUNET_MQ_send (friend->mq,
 680                           env);
 681         }
 682
 683         tmp = next_pred;
 684         next_pred = next_pred->next_pred;
 685         GNUNET_free(tmp);
 686       }
 687     }
 688   }
 689
 690   if (inform_succ)
 691   {
 692     struct Trail *previous_succ;
 693     struct Trail *next_succ;
 694     tdm->trail_id = current->succ_id;
 695     friend = current->succ;
 696
 697     while( NULL != current)
 698     {
 699       if (NULL != friend)
 700       {
 701         env = GNUNET_MQ_msg (tdm,
 702                              GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
 703         GNUNET_MQ_send (friend->mq,
 704                         env);
 705       }
 706
 707       next_succ = current->next_succ;
 708       previous_succ = current->prev_succ;
 709
 710       /* Freeing current trail memory */
 711       GNUNET_free(current);
 712
 713       /* Destroying the next successor list */
 714       while(NULL != previous_succ)
 715       {
 716         struct Trail *tmp;
 717         if (NULL != friend)
 718         {
 719           env = GNUNET_MQ_msg (tdm,
 720                                GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
 721           GNUNET_MQ_send (friend->mq,
 722                           env);
 723         }
 724         tmp = next_succ;
 725         previous_succ = previous_succ->prev_succ;
 726         GNUNET_free(tmp);
 727       }
 728
 729       /* Destroying the next successor list */
 730       while(NULL != next_succ)
 731       {
 732         struct Trail *tmp;
 733         if (NULL != friend)
 734         {
 735           env = GNUNET_MQ_msg (tdm,
 736                                GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
 737           GNUNET_MQ_send (friend->mq,
 738                           env);
 739         }
 740         tmp = next_succ;
 741         next_succ = next_succ->next_pred;
 742         GNUNET_free(tmp);
 743       }
 744     }
 745   }
 746 }
 747
 748
 749 /**
 750  * Send the get result to requesting client.
 751  *
 752  * @param key Key of the requested data.
 753  * @param type Block type
 754  * @param target_peer Next peer to forward the message to.
 755  * @param source_peer Peer which has the data for the key.
 756  * @param put_path_length Number of peers in @a put_path
 757  * @param put_path Path taken to put the data at its stored location.
 758  * @param get_path_length Number of peers in @a get_path
 759  * @param get_path Path taken to reach to the location of the key.
 760  * @param expiration When will this result expire?
 761  * @param data Payload to store
 762  * @param data_size Size of the @a data
 763  */
 764 void
 765 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
 766                                 enum GNUNET_BLOCK_Type type,
 767                                 const struct GNUNET_PeerIdentity *target_peer,
 768                                 const struct GNUNET_PeerIdentity *source_peer,
 769                                 unsigned int put_path_length,
 770                                 const struct GNUNET_PeerIdentity *put_path,
 771                                 unsigned int get_path_length,
 772                                 const struct GNUNET_PeerIdentity *get_path,
 773                                 struct GNUNET_TIME_Absolute expiration,
 774                                 const void *data, size_t data_size)
 775 {
 776   // TRICKY: need to introduce some context to remember trail from
 777   // the lookup...
 778 }
 779
 780 /**
 781  * Method called whenever a peer disconnects.
 782  *
 783  * @param cls closure
 784  * @param peer peer identity this notification is about
 785  */
 786 static void
 787 handle_core_disconnect (void *cls,
 788                         const struct GNUNET_PeerIdentity *peer)
 789 {
 790   struct FriendInfo *remove_friend;
 791   struct Trail *t;
 792
 793   /* If disconnected to own identity, then return. */
 794   if (0 == memcmp (&my_identity,
 795                    peer,
 796                    sizeof (struct GNUNET_PeerIdentity)))
 797     return;
 798
 799   if (NULL == (remove_friend =
 800                GNUNET_CONTAINER_multipeermap_get (friends_peermap,
 801                                                   peer)))
 802   {
 803     GNUNET_break (0);
 804     return;
 805   }
 806
 807   GNUNET_assert (GNUNET_YES ==
 808                  GNUNET_CONTAINER_multipeermap_remove (friends_peermap,
 809                                                        peer,
 810                                                        remove_friend));
 811   while (NULL != (t = remove_friend->succ_head))
 812     delete_trail (t,
 813                   GNUNET_YES,
 814                   GNUNET_NO);
 815   while (NULL != (t = remove_friend->pred_head))
 816     delete_trail (t,
 817                   GNUNET_NO,
 818                   GNUNET_YES);
 819   GNUNET_MQ_destroy (remove_friend->mq);
 820   GNUNET_free (remove_friend);
 821   if (0 ==
 822       GNUNET_CONTAINER_multipeermap_size (friends_peermap))
 823   {
 824     GNUNET_SCHEDULER_cancel (random_walk_task);
 825     random_walk_task = NULL;
 826   }
 827 }
 828
 829
 830 /**
 831  * Pick random friend from friends for random walk.
 832  */
 833 static struct FriendInfo *
 834 pick_random_friend ()
 835 {
 836   // TODO: need to extend peermap API to return random entry...
 837   // (Note: same extension exists for hashmap API).
 838   return NULL; // FIXME...
 839 }
 840
 841
 842 /**
 843  * Initiate a random walk.
 844  *
 845  * @param cls NULL
 846  * @param tc unused
 847  */
 848 static void
 849 do_random_walk (void *cls,
 850                 const struct GNUNET_SCHEDULER_TaskContext *tc)
 851 {
 852   static unsigned int walk_layer;
 853   struct FriendInfo *friend;
 854   struct GNUNET_MQ_Envelope *env;
 855   struct RandomWalkMessage *rwm;
 856   struct FingerTable *ft;
 857   struct Finger *finger;
 858   struct Trail *trail;
 859
 860   random_walk_task = NULL;
 861   friend = pick_random_friend ();
 862
 863   trail = GNUNET_new (struct Trail);
 864   /* We create the random walk so, no predecessor */
 865   trail->succ = friend;
 866   GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
 867                                     &trail->succ_id);
 868   if (GNUNET_OK !=
 869       GNUNET_CONTAINER_multihashmap_put (trail_map,
 870                                          &trail->succ_id,
 871                                          trail,
 872                                          GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
 873   {
 874     GNUNET_break (0);
 875     GNUNET_free (trail);
 876     return;
 877   }
 878   GNUNET_CONTAINER_MDLL_insert (succ,
 879                                 friend->succ_head,
 880                                 friend->succ_tail,
 881                                 trail);
 882   env = GNUNET_MQ_msg (rwm,
 883                        GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
 884   rwm->hops_taken = htonl (0);
 885   rwm->trail_id = trail->succ_id;
 886   GNUNET_MQ_send (friend->mq,
 887                   env);
 888   /* clean up 'old' entry (implicitly via trail cleanup) */
 889   ft = &fingers[walk_layer];
 890
 891   if ( (NULL != ft->fingers) &&
 892        (NULL != (finger = ft->fingers[ft->walk_offset])) )
 893     delete_trail (finger->trail,
 894                   GNUNET_NO,
 895                   GNUNET_YES);
 896   if (ft->finger_array_size < 42)
 897   {
 898     // FIXME: must have finger array of the right size here,
 899     // FIXME: growing / shrinking are tricy -- with pointers
 900     // from Trails!!!
 901   }
 902
 903   GNUNET_assert (NULL == ft->fingers[ft->walk_offset]);
 904
 905   finger = GNUNET_new (struct Finger);
 906   finger->trail = trail;
 907   trail->finger = &ft->fingers[ft->walk_offset];
 908   finger->ft = ft;
 909   ft->fingers[ft->walk_offset] = finger;
 910   ft->is_sorted = GNUNET_NO;
 911   ft->walk_offset = (ft->walk_offset + 1) % ft->finger_array_size;
 912
 913   walk_layer = (walk_layer + 1) % NUMBER_LAYERED_ID;
 914   random_walk_task = GNUNET_SCHEDULER_add_delayed (RANDOM_WALK_DELAY,
 915                                                    &do_random_walk,
 916                                                    NULL);
 917 }
 918
 919
 920 /**
 921  * Method called whenever a peer connects.
 922  *
 923  * @param cls closure
 924  * @param peer_identity peer identity this notification is about
 925  */
 926 static void
 927 handle_core_connect (void *cls,
 928                      const struct GNUNET_PeerIdentity *peer_identity)
 929 {
 930   struct FriendInfo *friend;
 931
 932   /* Check for connect to self message */
 933   if (0 == memcmp (&my_identity,
 934                    peer_identity,
 935                    sizeof (struct GNUNET_PeerIdentity)))
 936     return;
 937
 938   /* If peer already exists in our friend_peermap, then exit. */
 939   if (GNUNET_YES ==
 940       GNUNET_CONTAINER_multipeermap_contains (friends_peermap,
 941                                               peer_identity))
 942   {
 943     GNUNET_break (0);
 944     return;
 945   }
 946
 947   friend = GNUNET_new (struct FriendInfo);
 948   friend->id = *peer_identity;
 949   friend->mq = GNUNET_CORE_mq_create (core_api,
 950                                       peer_identity);
 951   GNUNET_assert (GNUNET_OK ==
 952                  GNUNET_CONTAINER_multipeermap_put (friends_peermap,
 953                                                     peer_identity,
 954                                                     friend,
 955                                                     GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 956   if (NULL == random_walk_task)
 957   {
 958     /* random walk needs to be started -- we have a first connection */
 959     random_walk_task = GNUNET_SCHEDULER_add_now (&do_random_walk,
 960                                                  NULL);
 961   }
 962 }
 963
 964
 965 /**
 966  * To be called on core init/fail.
 967  *
 968  * @param cls service closure
 969  * @param identity the public identity of this peer
 970  */
 971 static void
 972 core_init (void *cls,
 973            const struct GNUNET_PeerIdentity *identity)
 974 {
 975   my_identity = *identity;
 976 }
 977
 978
 979 /**
 980  * Handle a `struct RandomWalkMessage` from a
 981  * #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK message.
 982  *
 983  * @param cls closure (NULL)
 984  * @param peer sender identity
 985  * @param message the setup message
 986  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
 987  */
 988 static int
 989 handle_dht_p2p_random_walk (void *cls,
 990                             const struct GNUNET_PeerIdentity *peer,
 991                             const struct GNUNET_MessageHeader *message)
 992 {
 993   const struct RandomWalkMessage *m;
 994   struct Trail *t;
 995   struct FriendInfo *pred;
 996
 997   m = (const struct RandomWalkMessage *) message;
 998   pred = GNUNET_CONTAINER_multipeermap_get (friends_peermap,
 999                                             peer);
1000   t = GNUNET_new (struct Trail);
1001   t->pred_id = m->trail_id;
1002   t->pred = pred;
1003   t->expiration_time = GNUNET_TIME_relative_to_absolute (TRAIL_TIMEOUT);
1004   if (GNUNET_OK !=
1005       GNUNET_CONTAINER_multihashmap_put (trail_map,
1006                                          &t->pred_id,
1007                                          t,
1008                                          GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1009   {
1010     GNUNET_break_op (0);
1011     GNUNET_free (t);
1012     return GNUNET_SYSERR;
1013   }
1014   GNUNET_CONTAINER_MDLL_insert (pred,
1015                                 pred->pred_head,
1016                                 pred->pred_tail,
1017                                 t);
1018   if (ntohl (m->hops_taken) > GDS_NSE_get ())
1019   {
1020     /* We are the last hop, generate response */
1021     struct GNUNET_MQ_Envelope *env;
1022     struct RandomWalkResponseMessage *rwrm;
1023     uint16_t layer;
1024
1025     env = GNUNET_MQ_msg (rwrm,
1026                          GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE);
1027     rwrm->reserved = htonl (0);
1028     rwrm->trail_id = m->trail_id;
1029     layer = ntohs (m->layer);
1030     if (0 == layer)
1031       (void) GDS_DATACACHE_get_random_key (&rwrm->location);
1032     else
1033     {
1034       struct FingerTable *ft;
1035
1036       if (layer > NUMBER_LAYERED_ID)
1037       {
1038         GNUNET_break_op (0);
1039         // FIXME: clean up 't'...
1040         return GNUNET_SYSERR;
1041       }
1042       ft = &fingers[layer-1];
1043       if (0 == ft->number_valid_fingers)
1044       {
1045         GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1046                                           &rwrm->location);
1047       }
1048       else
1049       {
1050         struct Finger *f;
1051
1052         f = ft->fingers[GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
1053                                                   ft->number_valid_fingers)];
1054         rwrm->location = f->destination;
1055       }
1056     }
1057     GNUNET_MQ_send (pred->mq,
1058                     env);
1059   }
1060   else
1061   {
1062     struct GNUNET_MQ_Envelope *env;
1063     struct RandomWalkMessage *rwm;
1064     struct FriendInfo *succ;
1065
1066     /* extend the trail by another random hop */
1067     succ = pick_random_friend ();
1068     GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1069                                       &t->succ_id);
1070     t->succ = succ;
1071     if (GNUNET_OK !=
1072         GNUNET_CONTAINER_multihashmap_put (trail_map,
1073                                            &t->succ_id,
1074                                            t,
1075                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1076     {
1077       GNUNET_break (0);
1078       GNUNET_CONTAINER_MDLL_remove (pred,
1079                                     pred->pred_head,
1080                                     pred->pred_tail,
1081                                     t);
1082       GNUNET_free (t);
1083       return GNUNET_OK;
1084     }
1085     GNUNET_CONTAINER_MDLL_insert (succ,
1086                                   succ->succ_head,
1087                                   succ->succ_tail,
1088                                   t);
1089     env = GNUNET_MQ_msg (rwm,
1090                          GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
1091     rwm->hops_taken = htons (1 + ntohs (m->hops_taken));
1092     rwm->layer = m->layer;
1093     rwm->trail_id = t->succ_id;
1094     GNUNET_MQ_send (succ->mq,
1095                     env);
1096   }
1097   return GNUNET_OK;
1098 }
1099
1100
1101 /**
1102  * Handle a `struct RandomWalkResponseMessage` from a GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE
1103  * message.
1104  *
1105  * @param cls closure (NULL)
1106  * @param peer sender identity
1107  * @param message the setup response message
1108  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1109  */
1110 static int
1111 handle_dht_p2p_random_walk_response (void *cls,
1112                                      const struct GNUNET_PeerIdentity *peer,
1113                                      const struct GNUNET_MessageHeader *message)
1114 {
1115   const struct RandomWalkResponseMessage *rwrm;
1116
1117   rwrm = (const struct RandomWalkResponseMessage *) message;
1118   // 1) lookup trail => find Finger entry => fill in 'destination' and mark valid, move to end of sorted array, mark unsorted, update links from 'trails'
1119   /*
1120    * Steps :
1121    *  1 check if we are the correct layer
1122    *  1.a if true : add the returned value (finger) in the db structure
1123    *  1.b if true : do nothing
1124    */
1125   /* FIXME: add the value in db structure 1.a */
1126
1127   return GNUNET_OK;
1128 }
1129
1130
1131 /**
1132  * Handle a `struct TrailDestroyMessage`.
1133  *
1134  * @param cls closure (NULL)
1135  * @param peer sender identity
1136  * @param message the finger destroy message
1137  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1138  */
1139 static int
1140 handle_dht_p2p_trail_destroy (void *cls,
1141                              const struct GNUNET_PeerIdentity *peer,
1142                              const struct GNUNET_MessageHeader *message)
1143 {
1144   const struct TrailDestroyMessage *tdm;
1145
1146   tdm = (const struct TrailDestroyMessage *) message;
1147
1148   /*
1149    * Steps :
1150    *  1 check if message comme from a trail (that we still remember...)
1151    *  1.a.1 if true: send the destroy message to the rest trail
1152    *  1.a.2 clean the trail structure
1153    *  1.a.3 did i have to remove the trail and ID from the db structure?
1154    *  1.b if false: do nothing
1155    */
1156
1157   return GNUNET_OK;
1158 }
1159
1160
1161 /**
1162  * Handle a `struct TrailRouteMessage`.
1163  *
1164  * @param cls closure (NULL)
1165  * @param peer sender identity
1166  * @param message the finger destroy message
1167  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1168  */
1169 static int
1170 handle_dht_p2p_trail_route (void *cls,
1171                              const struct GNUNET_PeerIdentity *peer,
1172                              const struct GNUNET_MessageHeader *message)
1173 {
1174   const struct TrailRouteMessage *trm;
1175
1176   trm = (const struct TrailRouteMessage *) message;
1177
1178   /*
1179    * Steps :
1180    *  1 check if message comme from a trail
1181    *  1.a.1 if trail not finished with us, continue to forward
1182    *  1.a.2 otherwise handle body message embedded in trail
1183    */
1184
1185   return GNUNET_OK;
1186 }
1187
1188
1189 /**
1190  * Handle a `struct FindSuccessorMessage` from a #GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND
1191  * message.
1192  *
1193  * @param cls closure (NULL)
1194  * @param peer sender identity
1195  * @param message the finger setup message
1196  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1197  */
1198 static int
1199 handle_dht_p2p_successor_find (void *cls,
1200                                const struct GNUNET_PeerIdentity *peer,
1201                                const struct GNUNET_MessageHeader *message)
1202 {
1203   const struct FindSuccessorMessage *fsm;
1204
1205   fsm = (const struct FindSuccessorMessage *) message;
1206   // locate trail (for sending reply), if not exists, fail nicely.
1207   // otherwise, go to datacache and return 'top k' elements closest to 'key'
1208   // as "PUT" messages via the trail (need to extend DB API!)
1209
1210   return GNUNET_OK;
1211 }
1212
1213
1214 /**
1215  * Handle a `struct PeerGetMessage`.
1216  *
1217  * @param cls closure (NULL)
1218  * @param peer sender identity
1219  * @param message the peer get message
1220  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1221  */
1222 static int
1223 handle_dht_p2p_peer_get (void *cls,
1224                          const struct GNUNET_PeerIdentity *peer,
1225                          const struct GNUNET_MessageHeader *message)
1226 {
1227   const struct PeerGetMessage *pgm;
1228
1229   // FIXME: note: never called like this, message embedded with trail route!
1230   pgm = (const struct PeerGetMessage *) message;
1231   // -> lookup in datacache (figure out way to remember trail!)
1232      /*
1233     * steps :
1234     *   1 extract the result
1235     *   2 save the peer
1236     *   3 send it using the good trail
1237     *
1238     * What do i do when i don't have the key/value?
1239     */
1240
1241   return GNUNET_OK;
1242 }
1243
1244
1245 /**
1246  * Handle a `struct PeerGetResultMessage`.
1247  *
1248  * @param cls closure (NULL)
1249  * @param peer sender identity
1250  * @param message the peer get result message
1251  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1252  */
1253 static int
1254 handle_dht_p2p_peer_get_result (void *cls,
1255                              const struct GNUNET_PeerIdentity *peer,
1256                              const struct GNUNET_MessageHeader *message)
1257 {
1258   const struct PeerGetResultMessage *pgrm;
1259
1260   pgrm = (const struct PeerGetResultMessage *) message;
1261   // pretty much: parse, & pass to client (there is some call for that...)
1262
1263   return GNUNET_OK;
1264 }
1265
1266
1267 /**
1268  * Handle a `struct PeerPutMessage`.
1269  *
1270  * @param cls closure (NULL)
1271  * @param peer sender identity
1272  * @param message the peer put message
1273  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1274  */
1275 static int
1276 handle_dht_p2p_peer_put (void *cls,
1277                              const struct GNUNET_PeerIdentity *peer,
1278                              const struct GNUNET_MessageHeader *message)
1279 {
1280   const struct PeerGetResultMessage *pgrm;
1281
1282   pgrm = (const struct PeerGetResultMessage *) message;
1283   // parse & store in datacache, this is in response to us asking for successors.
1284   /*
1285    * steps :
1286    * 1 check the size of the message
1287    * 2 use the API to add the value in the "database". Check on the xdht file, how to do it.
1288    * 3 Did i a have to return a notification or did i have to return GNUNET_[OK|SYSERR]?
1289    */
1290   return GNUNET_OK;
1291 }
1292
1293
1294 /**
1295  * Initialize neighbours subsystem.
1296  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1297  */
1298 int
1299 GDS_NEIGHBOURS_init (void)
1300 {
1301   static const struct GNUNET_CORE_MessageHandler core_handlers[] = {
1302     { &handle_dht_p2p_random_walk,
1303       GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK,
1304       sizeof (struct RandomWalkMessage) },
1305     { &handle_dht_p2p_random_walk_response,
1306       GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE,
1307       sizeof (struct RandomWalkResponseMessage) },
1308     { &handle_dht_p2p_trail_destroy,
1309       GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY,
1310       sizeof (struct TrailDestroyMessage) },
1311     { &handle_dht_p2p_trail_route,
1312       GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE,
1313       0},
1314     { &handle_dht_p2p_successor_find,
1315       GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND,
1316       sizeof (struct FindSuccessorMessage) },
1317     { &handle_dht_p2p_peer_get,
1318       GNUNET_MESSAGE_TYPE_WDHT_GET,
1319       sizeof (struct PeerGetMessage) },
1320     { &handle_dht_p2p_peer_get_result,
1321       GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT,
1322       0},
1323     { &handle_dht_p2p_peer_put,
1324       GNUNET_MESSAGE_TYPE_WDHT_PUT,
1325       0},
1326     {NULL, 0, 0}
1327   };
1328
1329   core_api =
1330     GNUNET_CORE_connect (GDS_cfg, NULL,
1331                          &core_init,
1332                          &handle_core_connect,
1333                          &handle_core_disconnect,
1334                          NULL, GNUNET_NO,
1335                          NULL, GNUNET_NO,
1336                          core_handlers);
1337
1338   if (NULL == core_api)
1339     return GNUNET_SYSERR;
1340   friends_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1341   trail_map = GNUNET_CONTAINER_multihashmap_create (1024, GNUNET_YES);
1342   trail_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
1343   return GNUNET_OK;
1344 }
1345
1346
1347 /**
1348  * Shutdown neighbours subsystem.
1349  */
1350 void
1351 GDS_NEIGHBOURS_done (void)
1352 {
1353   if (NULL == core_api)
1354     return;
1355   GNUNET_CORE_disconnect (core_api);
1356   core_api = NULL;
1357   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friends_peermap));
1358   GNUNET_CONTAINER_multipeermap_destroy (friends_peermap);
1359   friends_peermap = NULL;
1360   GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (trail_map));
1361   GNUNET_CONTAINER_multihashmap_destroy (trail_map);
1362   trail_map = NULL;
1363   GNUNET_CONTAINER_heap_destroy (trail_heap);
1364   trail_heap = NULL;
1365 }
1366
1367
1368 /**
1369  * Get my identity
1370  *
1371  * @return my identity
1372  */
1373 struct GNUNET_PeerIdentity
1374 GDS_NEIGHBOURS_get_my_id (void)
1375 {
1376   return my_identity;
1377 }
1378
1379 /* end of gnunet-service-wdht_neighbours.c */