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