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   // ... FIXME
 624 }
 625
 626
 627 /**
 628  * Send the get result to requesting client.
 629  *
 630  * @param key Key of the requested data.
 631  * @param type Block type
 632  * @param target_peer Next peer to forward the message to.
 633  * @param source_peer Peer which has the data for the key.
 634  * @param put_path_length Number of peers in @a put_path
 635  * @param put_path Path taken to put the data at its stored location.
 636  * @param get_path_length Number of peers in @a get_path
 637  * @param get_path Path taken to reach to the location of the key.
 638  * @param expiration When will this result expire?
 639  * @param data Payload to store
 640  * @param data_size Size of the @a data
 641  */
 642 void
 643 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
 644                                 enum GNUNET_BLOCK_Type type,
 645                                 const struct GNUNET_PeerIdentity *target_peer,
 646                                 const struct GNUNET_PeerIdentity *source_peer,
 647                                 unsigned int put_path_length,
 648                                 const struct GNUNET_PeerIdentity *put_path,
 649                                 unsigned int get_path_length,
 650                                 const struct GNUNET_PeerIdentity *get_path,
 651                                 struct GNUNET_TIME_Absolute expiration,
 652                                 const void *data, size_t data_size)
 653 {
 654   // TRICKY: need to introduce some context to remember trail from
 655   // the lookup...
 656 }
 657
 658
 659 /**
 660  * Method called whenever a peer disconnects.
 661  *
 662  * @param cls closure
 663  * @param peer peer identity this notification is about
 664  */
 665 static void
 666 handle_core_disconnect (void *cls,
 667                         const struct GNUNET_PeerIdentity *peer)
 668 {
 669   struct FriendInfo *remove_friend;
 670   struct Trail *t;
 671
 672   /* If disconnected to own identity, then return. */
 673   if (0 == memcmp (&my_identity,
 674                    peer,
 675                    sizeof (struct GNUNET_PeerIdentity)))
 676     return;
 677
 678   if (NULL == (remove_friend =
 679                GNUNET_CONTAINER_multipeermap_get (friends_peermap,
 680                                                   peer)))
 681   {
 682     GNUNET_break (0);
 683     return;
 684   }
 685
 686   GNUNET_assert (GNUNET_YES ==
 687                  GNUNET_CONTAINER_multipeermap_remove (friends_peermap,
 688                                                        peer,
 689                                                        remove_friend));
 690   while (NULL != (t = remove_friend->succ_head))
 691     delete_trail (t,
 692                   GNUNET_YES,
 693                   GNUNET_NO);
 694   while (NULL != (t = remove_friend->pred_head))
 695     delete_trail (t,
 696                   GNUNET_NO,
 697                   GNUNET_YES);
 698   GNUNET_MQ_destroy (remove_friend->mq);
 699   GNUNET_free (remove_friend);
 700   if (0 ==
 701       GNUNET_CONTAINER_multipeermap_size (friends_peermap))
 702   {
 703     GNUNET_SCHEDULER_cancel (random_walk_task);
 704     random_walk_task = NULL;
 705   }
 706 }
 707
 708
 709 /**
 710  * Pick random friend from friends for random walk.
 711  */
 712 static struct FriendInfo *
 713 pick_random_friend ()
 714 {
 715   // TODO: need to extend peermap API to return random entry...
 716   // (Note: same extension exists for hashmap API).
 717   return NULL; // FIXME...
 718 }
 719
 720
 721 /**
 722  * Initiate a random walk.
 723  *
 724  * @param cls NULL
 725  * @param tc unused
 726  */
 727 static void
 728 do_random_walk (void *cls,
 729                 const struct GNUNET_SCHEDULER_TaskContext *tc)
 730 {
 731   static unsigned int walk_layer;
 732   struct FriendInfo *friend;
 733   struct GNUNET_MQ_Envelope *env;
 734   struct RandomWalkMessage *rwm;
 735   struct FingerTable *ft;
 736   struct Finger *finger;
 737   struct Trail *trail;
 738
 739   random_walk_task = NULL;
 740   friend = pick_random_friend ();
 741
 742   trail = GNUNET_new (struct Trail);
 743   /* We create the random walk so, no predecessor */
 744   trail->succ = friend;
 745   GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
 746                                     &trail->succ_id);
 747   if (GNUNET_OK !=
 748       GNUNET_CONTAINER_multihashmap_put (trail_map,
 749                                          &trail->succ_id,
 750                                          trail,
 751                                          GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
 752   {
 753     GNUNET_break (0);
 754     GNUNET_free (trail);
 755     return;
 756   }
 757   GNUNET_CONTAINER_MDLL_insert (succ,
 758                                 friend->succ_head,
 759                                 friend->succ_tail,
 760                                 trail);
 761   env = GNUNET_MQ_msg (rwm,
 762                        GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
 763   rwm->hops_taken = htonl (0);
 764   rwm->trail_id = trail->succ_id;
 765   GNUNET_MQ_send (friend->mq,
 766                   env);
 767   /* clean up 'old' entry (implicitly via trail cleanup) */
 768   ft = &fingers[walk_layer];
 769
 770   if ( (NULL != ft->fingers) &&
 771        (NULL != (finger = ft->fingers[ft->walk_offset])) )
 772     delete_trail (finger->trail,
 773                   GNUNET_NO,
 774                   GNUNET_YES);
 775   if (ft->finger_array_size < 42)
 776   {
 777     // FIXME: must have finger array of the right size here,
 778     // FIXME: growing / shrinking are tricy -- with pointers
 779     // from Trails!!!
 780   }
 781
 782   GNUNET_assert (NULL == ft->fingers[ft->walk_offset]);
 783
 784   finger = GNUNET_new (struct Finger);
 785   finger->trail = trail;
 786   trail->finger = &ft->fingers[ft->walk_offset];
 787   finger->ft = ft;
 788   ft->fingers[ft->walk_offset] = finger;
 789   ft->is_sorted = GNUNET_NO;
 790   ft->walk_offset = (ft->walk_offset + 1) % ft->finger_array_size;
 791
 792   walk_layer = (walk_layer + 1) % NUMBER_LAYERED_ID;
 793   random_walk_task = GNUNET_SCHEDULER_add_delayed (RANDOM_WALK_DELAY,
 794                                                    &do_random_walk,
 795                                                    NULL);
 796 }
 797
 798
 799 /**
 800  * Method called whenever a peer connects.
 801  *
 802  * @param cls closure
 803  * @param peer_identity peer identity this notification is about
 804  */
 805 static void
 806 handle_core_connect (void *cls,
 807                      const struct GNUNET_PeerIdentity *peer_identity)
 808 {
 809   struct FriendInfo *friend;
 810
 811   /* Check for connect to self message */
 812   if (0 == memcmp (&my_identity,
 813                    peer_identity,
 814                    sizeof (struct GNUNET_PeerIdentity)))
 815     return;
 816
 817   /* If peer already exists in our friend_peermap, then exit. */
 818   if (GNUNET_YES ==
 819       GNUNET_CONTAINER_multipeermap_contains (friends_peermap,
 820                                               peer_identity))
 821   {
 822     GNUNET_break (0);
 823     return;
 824   }
 825
 826   friend = GNUNET_new (struct FriendInfo);
 827   friend->id = *peer_identity;
 828   friend->mq = GNUNET_CORE_mq_create (core_api,
 829                                       peer_identity);
 830   GNUNET_assert (GNUNET_OK ==
 831                  GNUNET_CONTAINER_multipeermap_put (friends_peermap,
 832                                                     peer_identity,
 833                                                     friend,
 834                                                     GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 835   if (NULL == random_walk_task)
 836   {
 837     /* random walk needs to be started -- we have a first connection */
 838     random_walk_task = GNUNET_SCHEDULER_add_now (&do_random_walk,
 839                                                  NULL);
 840   }
 841 }
 842
 843
 844 /**
 845  * To be called on core init/fail.
 846  *
 847  * @param cls service closure
 848  * @param identity the public identity of this peer
 849  */
 850 static void
 851 core_init (void *cls,
 852            const struct GNUNET_PeerIdentity *identity)
 853 {
 854   my_identity = *identity;
 855 }
 856
 857
 858 /**
 859  * Handle a `struct RandomWalkMessage` from a
 860  * #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK message.
 861  *
 862  * @param cls closure (NULL)
 863  * @param peer sender identity
 864  * @param message the setup message
 865  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
 866  */
 867 static int
 868 handle_dht_p2p_random_walk (void *cls,
 869                             const struct GNUNET_PeerIdentity *peer,
 870                             const struct GNUNET_MessageHeader *message)
 871 {
 872   const struct RandomWalkMessage *m;
 873   struct Trail *t;
 874   struct FriendInfo *pred;
 875
 876   m = (const struct RandomWalkMessage *) message;
 877   pred = GNUNET_CONTAINER_multipeermap_get (friends_peermap,
 878                                             peer);
 879   t = GNUNET_new (struct Trail);
 880   t->pred_id = m->trail_id;
 881   t->pred = pred;
 882   t->expiration_time = GNUNET_TIME_relative_to_absolute (TRAIL_TIMEOUT);
 883   if (GNUNET_OK !=
 884       GNUNET_CONTAINER_multihashmap_put (trail_map,
 885                                          &t->pred_id,
 886                                          t,
 887                                          GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
 888   {
 889     GNUNET_break_op (0);
 890     GNUNET_free (t);
 891     return GNUNET_SYSERR;
 892   }
 893   GNUNET_CONTAINER_MDLL_insert (pred,
 894                                 pred->pred_head,
 895                                 pred->pred_tail,
 896                                 t);
 897   if (ntohl (m->hops_taken) > GDS_NSE_get ())
 898   {
 899     /* We are the last hop, generate response */
 900     struct GNUNET_MQ_Envelope *env;
 901     struct RandomWalkResponseMessage *rwrm;
 902     uint16_t layer;
 903
 904     env = GNUNET_MQ_msg (rwrm,
 905                          GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE);
 906     rwrm->reserved = htonl (0);
 907     rwrm->trail_id = m->trail_id;
 908     layer = ntohs (m->layer);
 909     if (0 == layer)
 910       (void) GDS_DATACACHE_get_random_key (&rwrm->location);
 911     else
 912     {
 913       struct FingerTable *ft;
 914
 915       if (layer > NUMBER_LAYERED_ID)
 916       {
 917         GNUNET_break_op (0);
 918         // FIXME: clean up 't'...
 919         return GNUNET_SYSERR;
 920       }
 921       ft = &fingers[layer-1];
 922       if (0 == ft->number_valid_fingers)
 923       {
 924         GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
 925                                           &rwrm->location);
 926       }
 927       else
 928       {
 929         struct Finger *f;
 930
 931         f = ft->fingers[GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
 932                                                   ft->number_valid_fingers)];
 933         rwrm->location = f->destination;
 934       }
 935     }
 936     GNUNET_MQ_send (pred->mq,
 937                     env);
 938   }
 939   else
 940   {
 941     struct GNUNET_MQ_Envelope *env;
 942     struct RandomWalkMessage *rwm;
 943     struct FriendInfo *succ;
 944
 945     /* extend the trail by another random hop */
 946     succ = pick_random_friend ();
 947     GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
 948                                       &t->succ_id);
 949     t->succ = succ;
 950     if (GNUNET_OK !=
 951         GNUNET_CONTAINER_multihashmap_put (trail_map,
 952                                            &t->succ_id,
 953                                            t,
 954                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
 955     {
 956       GNUNET_break (0);
 957       GNUNET_CONTAINER_MDLL_remove (pred,
 958                                     pred->pred_head,
 959                                     pred->pred_tail,
 960                                     t);
 961       GNUNET_free (t);
 962       return GNUNET_OK;
 963     }
 964     GNUNET_CONTAINER_MDLL_insert (succ,
 965                                   succ->succ_head,
 966                                   succ->succ_tail,
 967                                   t);
 968     env = GNUNET_MQ_msg (rwm,
 969                          GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
 970     rwm->hops_taken = htons (1 + ntohs (m->hops_taken));
 971     rwm->layer = m->layer;
 972     rwm->trail_id = t->succ_id;
 973     GNUNET_MQ_send (succ->mq,
 974                     env);
 975   }
 976   return GNUNET_OK;
 977 }
 978
 979
 980 /**
 981  * Handle a `struct RandomWalkResponseMessage` from a GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE
 982  * message.
 983  *
 984  * @param cls closure (NULL)
 985  * @param peer sender identity
 986  * @param message the setup response message
 987  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
 988  */
 989 static int
 990 handle_dht_p2p_random_walk_response (void *cls,
 991                                      const struct GNUNET_PeerIdentity *peer,
 992                                      const struct GNUNET_MessageHeader *message)
 993 {
 994   const struct RandomWalkResponseMessage *rwrm;
 995
 996   rwrm = (const struct RandomWalkResponseMessage *) message;
 997   // 1) lookup trail => find Finger entry => fill in 'destination' and mark valid, move to end of sorted array, mark unsorted, update links from 'trails'
 998   /*
 999    * Steps :
1000    *  1 check if we are the correct layer
1001    *  1.a if true : add the returned value (finger) in the db structure
1002    *  1.b if true : do nothing
1003    */
1004   /* FIXME: add the value in db structure 1.a */
1005
1006   return GNUNET_OK;
1007 }
1008
1009
1010 /**
1011  * Handle a `struct TrailDestroyMessage`.
1012  *
1013  * @param cls closure (NULL)
1014  * @param peer sender identity
1015  * @param message the finger destroy message
1016  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1017  */
1018 static int
1019 handle_dht_p2p_trail_destroy (void *cls,
1020                              const struct GNUNET_PeerIdentity *peer,
1021                              const struct GNUNET_MessageHeader *message)
1022 {
1023   const struct TrailDestroyMessage *tdm;
1024
1025   tdm = (const struct TrailDestroyMessage *) message;
1026
1027   /*
1028    * Steps :
1029    *  1 check if message comme from a trail (that we still remember...)
1030    *  1.a.1 if true: send the destroy message to the rest trail
1031    *  1.a.2 clean the trail structure
1032    *  1.a.3 did i have to remove the trail and ID from the db structure?
1033    *  1.b if false: do nothing
1034    */
1035
1036   return GNUNET_OK;
1037 }
1038
1039
1040 /**
1041  * Handle a `struct TrailRouteMessage`.
1042  *
1043  * @param cls closure (NULL)
1044  * @param peer sender identity
1045  * @param message the finger destroy message
1046  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1047  */
1048 static int
1049 handle_dht_p2p_trail_route (void *cls,
1050                              const struct GNUNET_PeerIdentity *peer,
1051                              const struct GNUNET_MessageHeader *message)
1052 {
1053   const struct TrailRouteMessage *trm;
1054
1055   trm = (const struct TrailRouteMessage *) message;
1056
1057   /*
1058    * Steps :
1059    *  1 check if message comme from a trail
1060    *  1.a.1 if trail not finished with us, continue to forward
1061    *  1.a.2 otherwise handle body message embedded in trail
1062    */
1063
1064   return GNUNET_OK;
1065 }
1066
1067
1068 /**
1069  * Handle a `struct FindSuccessorMessage` from a #GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND
1070  * message.
1071  *
1072  * @param cls closure (NULL)
1073  * @param peer sender identity
1074  * @param message the finger setup message
1075  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1076  */
1077 static int
1078 handle_dht_p2p_successor_find (void *cls,
1079                                const struct GNUNET_PeerIdentity *peer,
1080                                const struct GNUNET_MessageHeader *message)
1081 {
1082   const struct FindSuccessorMessage *fsm;
1083
1084   fsm = (const struct FindSuccessorMessage *) message;
1085   // locate trail (for sending reply), if not exists, fail nicely.
1086   // otherwise, go to datacache and return 'top k' elements closest to 'key'
1087   // as "PUT" messages via the trail (need to extend DB API!)
1088
1089   return GNUNET_OK;
1090 }
1091
1092
1093 /**
1094  * Handle a `struct PeerGetMessage`.
1095  *
1096  * @param cls closure (NULL)
1097  * @param peer sender identity
1098  * @param message the peer get message
1099  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1100  */
1101 static int
1102 handle_dht_p2p_peer_get (void *cls,
1103                          const struct GNUNET_PeerIdentity *peer,
1104                          const struct GNUNET_MessageHeader *message)
1105 {
1106   const struct PeerGetMessage *pgm;
1107
1108   // FIXME: note: never called like this, message embedded with trail route!
1109   pgm = (const struct PeerGetMessage *) message;
1110   // -> lookup in datacache (figure out way to remember trail!)
1111      /*
1112     * steps :
1113     *   1 extract the result
1114     *   2 save the peer
1115     *   3 send it using the good trail
1116     *
1117     * What do i do when i don't have the key/value?
1118     */
1119
1120   return GNUNET_OK;
1121 }
1122
1123
1124 /**
1125  * Handle a `struct PeerGetResultMessage`.
1126  *
1127  * @param cls closure (NULL)
1128  * @param peer sender identity
1129  * @param message the peer get result message
1130  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1131  */
1132 static int
1133 handle_dht_p2p_peer_get_result (void *cls,
1134                              const struct GNUNET_PeerIdentity *peer,
1135                              const struct GNUNET_MessageHeader *message)
1136 {
1137   const struct PeerGetResultMessage *pgrm;
1138
1139   pgrm = (const struct PeerGetResultMessage *) message;
1140   // pretty much: parse, & pass to client (there is some call for that...)
1141
1142   return GNUNET_OK;
1143 }
1144
1145
1146 /**
1147  * Handle a `struct PeerPutMessage`.
1148  *
1149  * @param cls closure (NULL)
1150  * @param peer sender identity
1151  * @param message the peer put message
1152  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1153  */
1154 static int
1155 handle_dht_p2p_peer_put (void *cls,
1156                              const struct GNUNET_PeerIdentity *peer,
1157                              const struct GNUNET_MessageHeader *message)
1158 {
1159   const struct PeerGetResultMessage *pgrm;
1160
1161   pgrm = (const struct PeerGetResultMessage *) message;
1162   // parse & store in datacache, this is in response to us asking for successors.
1163   /*
1164    * steps :
1165    * 1 check the size of the message
1166    * 2 use the API to add the value in the "database". Check on the xdht file, how to do it.
1167    * 3 Did i a have to return a notification or did i have to return GNUNET_[OK|SYSERR]?
1168    */
1169   return GNUNET_OK;
1170 }
1171
1172
1173 /**
1174  * Initialize neighbours subsystem.
1175  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1176  */
1177 int
1178 GDS_NEIGHBOURS_init (void)
1179 {
1180   static const struct GNUNET_CORE_MessageHandler core_handlers[] = {
1181     { &handle_dht_p2p_random_walk,
1182       GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK,
1183       sizeof (struct RandomWalkMessage) },
1184     { &handle_dht_p2p_random_walk_response,
1185       GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE,
1186       sizeof (struct RandomWalkResponseMessage) },
1187     { &handle_dht_p2p_trail_destroy,
1188       GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY,
1189       sizeof (struct TrailDestroyMessage) },
1190     { &handle_dht_p2p_trail_route,
1191       GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE,
1192       0},
1193     { &handle_dht_p2p_successor_find,
1194       GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND,
1195       sizeof (struct FindSuccessorMessage) },
1196     { &handle_dht_p2p_peer_get,
1197       GNUNET_MESSAGE_TYPE_WDHT_GET,
1198       sizeof (struct PeerGetMessage) },
1199     { &handle_dht_p2p_peer_get_result,
1200       GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT,
1201       0},
1202     { &handle_dht_p2p_peer_put,
1203       GNUNET_MESSAGE_TYPE_WDHT_PUT,
1204       0},
1205     {NULL, 0, 0}
1206   };
1207
1208   core_api =
1209     GNUNET_CORE_connect (GDS_cfg, NULL,
1210                          &core_init,
1211                          &handle_core_connect,
1212                          &handle_core_disconnect,
1213                          NULL, GNUNET_NO,
1214                          NULL, GNUNET_NO,
1215                          core_handlers);
1216
1217   if (NULL == core_api)
1218     return GNUNET_SYSERR;
1219   friends_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1220   trail_map = GNUNET_CONTAINER_multihashmap_create (1024, GNUNET_YES);
1221   trail_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
1222   return GNUNET_OK;
1223 }
1224
1225
1226 /**
1227  * Shutdown neighbours subsystem.
1228  */
1229 void
1230 GDS_NEIGHBOURS_done (void)
1231 {
1232   if (NULL == core_api)
1233     return;
1234   GNUNET_CORE_disconnect (core_api);
1235   core_api = NULL;
1236   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friends_peermap));
1237   GNUNET_CONTAINER_multipeermap_destroy (friends_peermap);
1238   friends_peermap = NULL;
1239   GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (trail_map));
1240   GNUNET_CONTAINER_multihashmap_destroy (trail_map);
1241   trail_map = NULL;
1242   GNUNET_CONTAINER_heap_destroy (trail_heap);
1243   trail_heap = NULL;
1244 }
1245
1246
1247 /**
1248  * Get my identity
1249  *
1250  * @return my identity
1251  */
1252 struct GNUNET_PeerIdentity
1253 GDS_NEIGHBOURS_get_my_id (void)
1254 {
1255   return my_identity;
1256 }
1257
1258 /* end of gnunet-service-wdht_neighbours.c */