src/dht/gnunet-service-wdht_neighbours.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2009-2016 GNUnet e.V.
   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., 51 Franklin Street, Fifth Floor,
  18      Boston, MA 02110-1301, 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  * @author Christian Grothoff
  25  * @author Arthur Dewarumez
  26  *
  27  * TODO:
  28  * - initiate finding of successors
  29  */
  30 #include "platform.h"
  31 #include "gnunet_util_lib.h"
  32 #include "gnunet_block_lib.h"
  33 #include "gnunet_hello_lib.h"
  34 #include "gnunet_constants.h"
  35 #include "gnunet_protocols.h"
  36 #include "gnunet_ats_service.h"
  37 #include "gnunet_core_service.h"
  38 #include "gnunet_datacache_lib.h"
  39 #include "gnunet_transport_service.h"
  40 #include "gnunet_dht_service.h"
  41 #include "gnunet_statistics_service.h"
  42 #include "gnunet-service-dht.h"
  43 #include "gnunet-service-dht_datacache.h"
  44 #include "gnunet-service-dht_neighbours.h"
  45 #include "gnunet-service-dht_nse.h"
  46 #include "dht.h"
  47
  48 #define DEBUG(...)                                           \
  49   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
  50
  51 /**
  52  * Trail timeout. After what time do trails always die?
  53  */
  54 #define TRAIL_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 42)
  55
  56 /**
  57  * Random walk delay. How often do we walk the overlay?
  58  */
  59 #define RANDOM_WALK_DELAY GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 42)
  60
  61 /**
  62  * The number of layered ID to use.
  63  */
  64 #define NUMBER_LAYERED_ID 8
  65
  66 /**
  67  * The number of random walk to launch at the beginning of the initialization
  68  */
  69 /* FIXME: find a better value */
  70 #define NUMBER_RANDOM_WALK 20
  71
  72
  73 /******************* The db structure and related functions *******************/
  74
  75 /**
  76  * Entry in #friends_peermap.
  77  */
  78 struct FriendInfo;
  79
  80 /**
  81  *
  82  */
  83 struct FingerTable;
  84
  85 /**
  86  * Information we keep per trail.
  87  */
  88 struct Trail
  89 {
  90
  91   /**
  92    * Identifier of the trail with the predecessor.
  93    */
  94   struct GNUNET_HashCode pred_id;
  95
  96   /**
  97    * Identifier of the trail with the successor.
  98    */
  99   struct GNUNET_HashCode succ_id;
 100
 101   /**
 102    * When does this trail expire.
 103    */
 104   struct GNUNET_TIME_Absolute expiration_time;
 105
 106   /**
 107    * MDLL entry in the list of all trails with the same predecessor.
 108    */
 109   struct Trail *prev_succ;
 110
 111   /**
 112    * MDLL entry in the list of all trails with the same predecessor.
 113    */
 114   struct Trail *next_succ;
 115
 116   /**
 117    * MDLL entry in the list of all trails with the same predecessor.
 118    */
 119   struct Trail *prev_pred;
 120
 121   /**
 122    * MDLL entry in the list of all trails with the same predecessor.
 123    */
 124   struct Trail *next_pred;
 125
 126   /**
 127    * Our predecessor in the trail, NULL if we are initiator (?).
 128    */
 129   struct FriendInfo *pred;
 130
 131   /**
 132    * Our successor in the trail, NULL if we are the last peer.
 133    */
 134   struct FriendInfo *succ;
 135
 136   /**
 137    * Location of this trail in the heap.
 138    */
 139   struct GNUNET_CONTAINER_HeapNode *hn;
 140
 141   /**
 142    * If this peer started the to create a Finger (and thus @e pred is
 143    * NULL), this is the finger table of the finger we are trying to
 144    * intialize.
 145    */
 146   struct FingerTable *ft;
 147
 148   /**
 149    * If this peer started the trail to create a Finger (and thus @e
 150    * pred is NULL), this is the offset of the finger we are trying to
 151    * intialize in the unsorted array.
 152    */
 153   unsigned int finger_off;
 154
 155 };
 156
 157
 158 /**
 159  *  Entry in #friends_peermap.
 160  */
 161 struct FriendInfo
 162 {
 163   /**
 164    * Friend Identity
 165    */
 166   const struct GNUNET_PeerIdentity *id;
 167
 168   /**
 169    *
 170    */
 171   struct Trail *pred_head;
 172
 173   /**
 174    *
 175    */
 176   struct Trail *pred_tail;
 177
 178   /**
 179    *
 180    */
 181   struct Trail *succ_head;
 182
 183   /**
 184    *
 185    */
 186   struct Trail *succ_tail;
 187
 188   /**
 189    * Core handle for sending messages to this friend.
 190    */
 191   struct GNUNET_MQ_Handle *mq;
 192
 193 };
 194
 195
 196 /**
 197  *
 198  */
 199 struct Finger
 200 {
 201   /**
 202    *
 203    */
 204   struct Trail *trail;
 205
 206   /**
 207    *
 208    */
 209   struct FingerTable *ft;
 210
 211   /**
 212    *
 213    */
 214   struct GNUNET_HashCode destination;
 215
 216   /**
 217    * #GNUNET_YES if a response has been received. Otherwise #GNUNET_NO.
 218    */
 219   int valid;
 220 };
 221
 222
 223 struct FingerTable
 224 {
 225   /**
 226    * Array of our fingers, unsorted.
 227    */
 228   struct Finger **fingers;
 229
 230   /**
 231    * Size of the finger array.
 232    */
 233   unsigned int finger_array_size;
 234
 235   /**
 236    * Number of valid entries in @e fingers
 237    */
 238   unsigned int number_valid_fingers;
 239
 240   /**
 241    * Which offset in @e fingers will we redo next.
 242    */
 243   unsigned int walk_offset;
 244
 245   /**
 246    * Is the finger array sorted?
 247    */
 248   int is_sorted;
 249
 250 };
 251
 252
 253 /***********************  end of the db structure part  ***********************/
 254
 255
 256 GNUNET_NETWORK_STRUCT_BEGIN
 257
 258 /**
 259  * Setup a finger using the underlay topology ("social network").
 260  */
 261 struct RandomWalkMessage
 262 {
 263   /**
 264    * Type: #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK
 265    */
 266   struct GNUNET_MessageHeader header;
 267
 268   /**
 269    * Number of hops this message has taken so far, we stop at
 270    * log(NSE), in NBO.
 271    */
 272   uint16_t hops_taken GNUNET_PACKED;
 273
 274   /**
 275    * Layer for the request, in NBO.
 276    */
 277   uint16_t layer GNUNET_PACKED;
 278
 279   /**
 280    * Unique (random) identifier this peer will use to
 281    * identify the trail (in future messages).
 282    */
 283   struct GNUNET_HashCode trail_id;
 284
 285 };
 286
 287 /**
 288  * Response to a `struct RandomWalkMessage`.
 289  */
 290 struct RandomWalkResponseMessage
 291 {
 292   /**
 293    * Type: #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE
 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 from the
 304    * `struct RandomWalkMessage`.
 305    */
 306   struct GNUNET_HashCode trail_id;
 307
 308   /**
 309    * Random location in the respective layer where the
 310    * random path of the finger setup terminated.
 311    */
 312   struct GNUNET_HashCode location;
 313
 314 };
 315
 316 /**
 317  * Response to an event that causes a trail to die.
 318  */
 319 struct TrailDestroyMessage
 320 {
 321   /**
 322    * Type: #GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY
 323    */
 324   struct GNUNET_MessageHeader header;
 325
 326   /**
 327    * Zero, for alignment.
 328    */
 329   uint32_t reserved GNUNET_PACKED;
 330
 331   /**
 332    * Unique (random) identifier this peer will use to
 333    * identify the finger (in future messages).
 334    */
 335   struct GNUNET_HashCode trail_id;
 336
 337 };
 338
 339
 340 /**
 341  * Send a message along a trail.
 342  */
 343 struct FindSuccessorMessage
 344 {
 345   /**
 346    * Type: #GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND
 347    */
 348   struct GNUNET_MessageHeader header;
 349
 350   /**
 351    * Zero, for alignment.
 352    */
 353   uint32_t reserved GNUNET_PACKED;
 354
 355   /**
 356    * Key for which we would like close values returned.
 357    * identify the finger (in future messages).
 358    */
 359   struct GNUNET_HashCode key;
 360
 361 };
 362
 363
 364 /**
 365  * Send a message along a trail.
 366  */
 367 struct TrailRouteMessage
 368 {
 369   /**
 370    * Type: #GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE
 371    */
 372   struct GNUNET_MessageHeader header;
 373
 374   /**
 375    * #GNUNET_YES if the path should be recorded, #GNUNET_NO if not; in NBO.
 376    */
 377   uint16_t record_path GNUNET_PACKED;
 378
 379   /**
 380    * Length of the recorded trail, 0 if @e record_path is #GNUNET_NO; in NBO.
 381    */
 382   uint16_t path_length GNUNET_PACKED;
 383
 384   /**
 385    * Unique (random) identifier this peer will use to
 386    * identify the finger (in future messages).
 387    */
 388   struct GNUNET_HashCode trail_id;
 389
 390   /**
 391    * Path the message has taken so far (excluding sender).
 392    */
 393   /* struct GNUNET_PeerIdentity path[path_length]; */
 394
 395   /* followed by payload (another `struct GNUNET_MessageHeader`) to
 396      send along the trail */
 397 };
 398
 399
 400 /**
 401  * P2P PUT message
 402  */
 403 struct PeerPutMessage
 404 {
 405   /**
 406    * Type: #GNUNET_MESSAGE_TYPE_WDHT_PUT
 407    */
 408   struct GNUNET_MessageHeader header;
 409
 410   /**
 411    * Processing options
 412    */
 413   uint32_t options GNUNET_PACKED;
 414
 415   /**
 416    * Content type.
 417    */
 418   uint32_t block_type GNUNET_PACKED;
 419
 420   /**
 421    * Hop count
 422    */
 423   uint32_t hop_count GNUNET_PACKED;
 424
 425   /**
 426    * Replication level for this message
 427    * In the current implementation, this value is not used.
 428    */
 429   uint32_t desired_replication_level GNUNET_PACKED;
 430
 431   /**
 432    * Length of the PUT path that follows (if tracked).
 433    */
 434   uint32_t put_path_length GNUNET_PACKED;
 435
 436   /**
 437    * When does the content expire?
 438    */
 439   struct GNUNET_TIME_AbsoluteNBO expiration_time;
 440
 441   /**
 442    * The key to store the value under.
 443    */
 444   struct GNUNET_HashCode key GNUNET_PACKED;
 445
 446   /* put path (if tracked) */
 447
 448   /* Payload */
 449
 450 };
 451
 452 /**
 453  * P2P GET message
 454  */
 455 struct PeerGetMessage
 456 {
 457   /**
 458    * Type: #GNUNET_MESSAGE_TYPE_WDHT_GET
 459    */
 460   struct GNUNET_MessageHeader header;
 461
 462   /**
 463    * Processing options
 464    */
 465   uint32_t options GNUNET_PACKED;
 466
 467   /**
 468    * Desired content type.
 469    */
 470   uint32_t block_type GNUNET_PACKED;
 471
 472   /**
 473    * Hop count
 474    */
 475   uint32_t hop_count GNUNET_PACKED;
 476
 477   /**
 478    * Desired replication level for this request.
 479    * In the current implementation, this value is not used.
 480    */
 481   uint32_t desired_replication_level GNUNET_PACKED;
 482
 483   /**
 484    * Total number of peers in get path.
 485    */
 486   unsigned int get_path_length;
 487
 488   /**
 489    * The key we are looking for.
 490    */
 491   struct GNUNET_HashCode key;
 492
 493   /* Get path. */
 494   /* struct GNUNET_PeerIdentity[]*/
 495 };
 496
 497
 498 /**
 499  * P2P Result message
 500  */
 501 struct PeerGetResultMessage
 502 {
 503   /**
 504    * Type: #GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT
 505    */
 506   struct GNUNET_MessageHeader header;
 507
 508   /**
 509    * The type for the data in NBO.
 510    */
 511   uint32_t type GNUNET_PACKED;
 512
 513   /**
 514    * Number of peers recorded in the outgoing path from source to the
 515    * stored location of this message.
 516    */
 517   uint32_t put_path_length GNUNET_PACKED;
 518
 519   /**
 520    * When does the content expire?
 521    */
 522   struct GNUNET_TIME_AbsoluteNBO expiration_time;
 523
 524   /**
 525    * The key of the corresponding GET request.
 526    */
 527   struct GNUNET_HashCode key;
 528
 529   /* put path (if tracked) */
 530
 531   /* Payload */
 532
 533 };
 534
 535 GNUNET_NETWORK_STRUCT_END
 536
 537
 538 /**
 539  * Contains all the layered IDs of this peer.
 540  */
 541 struct GNUNET_PeerIdentity layered_id[NUMBER_LAYERED_ID];
 542
 543 /**
 544  * Task to timeout trails that have expired.
 545  */
 546 static struct GNUNET_SCHEDULER_Task *trail_timeout_task;
 547
 548 /**
 549  * Task to perform random walks.
 550  */
 551 static struct GNUNET_SCHEDULER_Task *random_walk_task;
 552
 553 /**
 554  * Identity of this peer.
 555  */
 556 static struct GNUNET_PeerIdentity my_identity;
 557
 558 /**
 559  * Peer map of all the friends of a peer
 560  */
 561 static struct GNUNET_CONTAINER_MultiPeerMap *friends_peermap;
 562
 563 /**
 564  * Fingers per layer.
 565  */
 566 static struct FingerTable fingers[NUMBER_LAYERED_ID];
 567
 568 /**
 569  * Tail map, mapping tail identifiers to `struct Trail`s
 570  */
 571 static struct GNUNET_CONTAINER_MultiHashMap *trail_map;
 572
 573 /**
 574  * Tail heap, organizing trails by expiration time.
 575  */
 576 static struct GNUNET_CONTAINER_Heap *trail_heap;
 577
 578 /**
 579  * Handle to CORE.
 580  */
 581 static struct GNUNET_CORE_Handle *core_api;
 582
 583
 584 /**
 585  * Handle the put request from the client.
 586  *
 587  * @param block_type Type of the block
 588  * @param options routing options
 589  * @param desired_replication_level desired replication level
 590  * @param expiration_time when does the content expire
 591  * @param hop_count how many hops has this message traversed so far
 592  * @param bf Bloom filter of peers this PUT has already traversed
 593  * @param key key for the content
 594  * @param put_path_length number of entries in put_path
 595  * @param put_path peers this request has traversed so far (if tracked)
 596  * @param data payload to store
 597  * @param data_size number of bytes in data
 598  * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
 599  */
 600 int
 601 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type block_type,
 602                            enum GNUNET_DHT_RouteOption options,
 603                            uint32_t desired_replication_level,
 604                            struct GNUNET_TIME_Absolute expiration_time,
 605                            uint32_t hop_count,
 606                            struct GNUNET_CONTAINER_BloomFilter *bf,
 607                            const struct GNUNET_HashCode *key,
 608                            unsigned int put_path_length,
 609                            struct GNUNET_PeerIdentity *put_path,
 610                            const void *data,
 611                            size_t data_size)
 612 {
 613   GDS_DATACACHE_handle_put (expiration_time,
 614                             key,
 615                             0, NULL,
 616                             block_type,
 617                             data_size,
 618                             data);
 619   GDS_CLIENTS_process_put (options,
 620                            block_type,
 621                            hop_count,
 622                            desired_replication_level,
 623                            put_path_length, put_path,
 624                            expiration_time,
 625                            key,
 626                            data,
 627                            data_size);
 628   return GNUNET_OK; /* FIXME... */
 629 }
 630
 631
 632 /**
 633  * Perform a GET operation.  Forwards the given request to other
 634  * peers.  Does not lookup the key locally.  May do nothing if this is
 635  * the only peer in the network (or if we are the closest peer in the
 636  * network).
 637  *
 638  * @param type type of the block
 639  * @param options routing options
 640  * @param desired_replication_level desired replication count
 641  * @param hop_count how many hops did this request traverse so far?
 642  * @param key key for the content
 643  * @param xquery extended query
 644  * @param xquery_size number of bytes in @a xquery
 645  * @param reply_bf bloomfilter to filter duplicates
 646  * @param reply_bf_mutator mutator for @a reply_bf
 647  * @param peer_bf filter for peers not to select (again, updated)
 648  * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
 649  */
 650 int
 651 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
 652                            enum GNUNET_DHT_RouteOption options,
 653                            uint32_t desired_replication_level,
 654                            uint32_t hop_count,
 655                            const struct GNUNET_HashCode *key,
 656                            const void *xquery, size_t xquery_size,
 657                            const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
 658                            uint32_t reply_bf_mutator,
 659                            struct GNUNET_CONTAINER_BloomFilter *peer_bf)
 660 {
 661   // find closest finger(s) on all layers
 662   // use TrailRoute with PeerGetMessage embedded to contact peer
 663   // NOTE: actually more complicated, see paper!
 664   GNUNET_break (0); // not implemented!
 665   return GNUNET_SYSERR;
 666 }
 667
 668
 669 /**
 670  * Delete a trail, it died (timeout, link failure, etc.).
 671  *
 672  * @param trail trail to delete from all data structures
 673  * @param inform_pred should we notify the predecessor?
 674  * @param inform_succ should we inform the successor?
 675  */
 676 static void
 677 delete_trail (struct Trail *trail,
 678               int inform_pred,
 679               int inform_succ)
 680 {
 681   struct FriendInfo *friend;
 682   struct GNUNET_MQ_Envelope *env;
 683   struct TrailDestroyMessage *tdm;
 684   struct Finger *finger;
 685
 686   friend = trail->pred;
 687   if (NULL != friend)
 688   {
 689     if (GNUNET_YES == inform_pred)
 690     {
 691       env = GNUNET_MQ_msg (tdm,
 692                            GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
 693       tdm->trail_id = trail->pred_id;
 694       GNUNET_MQ_send (friend->mq,
 695                       env);
 696     }
 697     GNUNET_CONTAINER_MDLL_remove (pred,
 698                                   friend->pred_head,
 699                                   friend->pred_tail,
 700                                   trail);
 701   }
 702   friend = trail->succ;
 703   if (NULL != friend)
 704   {
 705     if (GNUNET_YES == inform_succ)
 706     {
 707       env = GNUNET_MQ_msg (tdm,
 708                            GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
 709       tdm->trail_id = trail->pred_id;
 710       GNUNET_MQ_send (friend->mq,
 711                       env);
 712     }
 713     GNUNET_CONTAINER_MDLL_remove (succ,
 714                                   friend->pred_head,
 715                                   friend->pred_tail,
 716                                   trail);
 717   }
 718   GNUNET_break (trail ==
 719                 GNUNET_CONTAINER_heap_remove_node (trail->hn));
 720   finger = trail->ft->fingers[trail->finger_off];
 721   if (NULL != finger)
 722   {
 723     trail->ft->fingers[trail->finger_off] = NULL;
 724     trail->ft->number_valid_fingers--;
 725     GNUNET_free (finger);
 726   }
 727   GNUNET_free (trail);
 728 }
 729
 730
 731 /**
 732  * Forward the given payload message along the trail.
 733  *
 734  * @param next_target which direction along the trail should we forward
 735  * @param trail_id which trail should we forward along
 736  * @param have_path do we track the forwarding path?
 737  * @param predecessor which peer do we tack on to the path?
 738  * @param path path the message has taken so far along the trail
 739  * @param path_length number of entries in @a path
 740  * @param payload payload of the message
 741  */
 742 static void
 743 forward_message_on_trail (struct FriendInfo *next_target,
 744                           const struct GNUNET_HashCode *trail_id,
 745                           int have_path,
 746                           const struct GNUNET_PeerIdentity *predecessor,
 747                           const struct GNUNET_PeerIdentity *path,
 748                           uint16_t path_length,
 749                           const struct GNUNET_MessageHeader *payload)
 750 {
 751   struct GNUNET_MQ_Envelope *env;
 752   struct TrailRouteMessage *trm;
 753   struct GNUNET_PeerIdentity *new_path;
 754   unsigned int plen;
 755   uint16_t payload_len;
 756
 757   payload_len = ntohs (payload->size);
 758   if (have_path)
 759   {
 760     plen = path_length + 1;
 761     if (plen >= (GNUNET_SERVER_MAX_MESSAGE_SIZE
 762                  - payload_len
 763                  - sizeof (struct TrailRouteMessage))
 764         / sizeof (struct GNUNET_PeerIdentity))
 765     {
 766       /* Should really not have paths this long... */
 767       GNUNET_break_op (0);
 768       plen = 0;
 769       have_path = 0;
 770     }
 771   }
 772   else
 773   {
 774     GNUNET_break_op (0 == path_length);
 775     path_length = 0;
 776     plen = 0;
 777   }
 778   env = GNUNET_MQ_msg_extra (trm,
 779                              payload_len +
 780                              plen * sizeof (struct GNUNET_PeerIdentity),
 781                              GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE);
 782   trm->record_path = htons (have_path);
 783   trm->path_length = htons (plen);
 784   trm->trail_id = *trail_id;
 785   new_path = (struct GNUNET_PeerIdentity *) &trm[1];
 786   if (have_path)
 787   {
 788     GNUNET_memcpy (new_path,
 789             path,
 790             path_length * sizeof (struct GNUNET_PeerIdentity));
 791     new_path[path_length] = *predecessor;
 792   }
 793   GNUNET_memcpy (&new_path[plen],
 794           payload,
 795           payload_len);
 796   GNUNET_MQ_send (next_target->mq,
 797                   env);
 798 }
 799
 800
 801 /**
 802  * Send the get result to requesting client.
 803  *
 804  * @param cls trail identifying where to send the result to, NULL for us
 805  * @param options routing options (from GET request)
 806  * @param key Key of the requested data.
 807  * @param type Block type
 808  * @param put_path_length Number of peers in @a put_path
 809  * @param put_path Path taken to put the data at its stored location.
 810  * @param expiration When will this result expire?
 811  * @param data Payload to store
 812  * @param data_size Size of the @a data
 813  */
 814 void
 815 GDS_NEIGHBOURS_send_get_result (void *cls,
 816                                 enum GNUNET_DHT_RouteOption options,
 817                                 const struct GNUNET_HashCode *key,
 818                                 enum GNUNET_BLOCK_Type type,
 819                                 unsigned int put_path_length,
 820                                 const struct GNUNET_PeerIdentity *put_path,
 821                                 struct GNUNET_TIME_Absolute expiration,
 822                                 const void *data,
 823                                 size_t data_size)
 824 {
 825   const struct GNUNET_HashCode *trail_id = cls;
 826   struct GNUNET_MessageHeader *payload;
 827   struct Trail *trail;
 828
 829   trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
 830                                              trail_id);
 831   if (NULL == trail)
 832   {
 833     /* TODO: inform statistics */
 834     return;
 835   }
 836   if (NULL == trail->pred)
 837   {
 838     /* result is for *us* (local client) */
 839     GDS_CLIENTS_handle_reply (expiration,
 840                               key,
 841                               0, NULL,
 842                               put_path_length, put_path,
 843                               type,
 844                               data_size,
 845                               data);
 846     return;
 847   }
 848
 849   payload = GNUNET_malloc(sizeof(struct GNUNET_MessageHeader) + data_size);
 850   payload->size = data_size;
 851   payload->type = GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT;
 852
 853   forward_message_on_trail (trail->pred,
 854                             trail_id,
 855                             0 != (options & GNUNET_DHT_RO_RECORD_ROUTE),
 856                             &my_identity,
 857                             NULL, 0,
 858                             payload);
 859   GNUNET_free (payload);
 860 }
 861
 862
 863 /**
 864  * Method called whenever a peer disconnects.
 865  *
 866  * @param cls closure
 867  * @param peer peer identity this notification is about
 868  * @param internal_cls our `struct FriendInfo` for @a peer
 869  */
 870 static void
 871 handle_core_disconnect (void *cls,
 872                         const struct GNUNET_PeerIdentity *peer,
 873                         void *internal_cls)
 874 {
 875   struct FriendInfo *remove_friend = internal_cls;
 876   struct Trail *t;
 877
 878   /* If disconnected to own identity, then return. */
 879   if (NULL == remove_friend)
 880     return;
 881   GNUNET_assert (GNUNET_YES ==
 882                  GNUNET_CONTAINER_multipeermap_remove (friends_peermap,
 883                                                        peer,
 884                                                        remove_friend));
 885   while (NULL != (t = remove_friend->succ_head))
 886     delete_trail (t,
 887                   GNUNET_YES,
 888                   GNUNET_NO);
 889   while (NULL != (t = remove_friend->pred_head))
 890     delete_trail (t,
 891                   GNUNET_NO,
 892                   GNUNET_YES);
 893   GNUNET_free (remove_friend);
 894   if (0 == GNUNET_CONTAINER_multipeermap_size (friends_peermap))
 895   {
 896     GNUNET_SCHEDULER_cancel (random_walk_task);
 897     random_walk_task = NULL;
 898   }
 899 }
 900
 901
 902 /**
 903  * Function called with a random friend to be returned.
 904  *
 905  * @param cls a `struct FriendInfo **` with where to store the result
 906  * @param peer the peer identity of the friend (ignored)
 907  * @param value the `struct FriendInfo *` that was selected at random
 908  * @return #GNUNET_OK (all good)
 909  */
 910 static int
 911 pick_random_helper (void *cls,
 912                     const struct GNUNET_PeerIdentity *peer,
 913                     void *value)
 914 {
 915   struct FriendInfo **fi = cls;
 916   struct FriendInfo *v = value;
 917
 918   *fi = v;
 919   return GNUNET_OK;
 920 }
 921
 922
 923 /**
 924  * Pick random friend from friends for random walk.
 925  *
 926  * @return NULL if we have no friends
 927  */
 928 static struct FriendInfo *
 929 pick_random_friend ()
 930 {
 931   struct FriendInfo *ret;
 932
 933   ret = NULL;
 934   if (0 ==
 935       GNUNET_CONTAINER_multipeermap_get_random (friends_peermap,
 936                                                 &pick_random_helper,
 937                                                 &ret))
 938     return NULL;
 939   return ret;
 940 }
 941
 942
 943 /**
 944  * One of our trails might have timed out, check and
 945  * possibly initiate cleanup.
 946  *
 947  * @param cls NULL
 948  */
 949 static void
 950 trail_timeout_callback (void *cls)
 951 {
 952   struct Trail *trail;
 953   struct GNUNET_TIME_Relative left;
 954
 955   trail_timeout_task = NULL;
 956   while (NULL != (trail = GNUNET_CONTAINER_heap_peek (trail_heap)))
 957   {
 958     left = GNUNET_TIME_absolute_get_remaining (trail->expiration_time);
 959     if (0 != left.rel_value_us)
 960       break;
 961     delete_trail (trail,
 962                   GNUNET_YES,
 963                   GNUNET_YES);
 964   }
 965   if (NULL != trail)
 966     trail_timeout_task = GNUNET_SCHEDULER_add_delayed (left,
 967                                                        &trail_timeout_callback,
 968                                                        NULL);
 969 }
 970
 971
 972 /**
 973  * Compute how big our finger arrays should be (at least).
 974  *
 975  * @return size of the finger array, never 0
 976  */
 977 static unsigned int
 978 get_desired_finger_array_size ()
 979 {
 980   /* FIXME: This is just a stub... */
 981   return 64;
 982 }
 983
 984
 985 /**
 986  * Initiate a random walk.
 987  *
 988  * @param cls NULL
 989  */
 990 static void
 991 do_random_walk (void *cls)
 992 {
 993   static unsigned int walk_layer;
 994   struct FriendInfo *friend;
 995   struct GNUNET_MQ_Envelope *env;
 996   struct RandomWalkMessage *rwm;
 997   struct FingerTable *ft;
 998   struct Finger *finger;
 999   struct Trail *trail;
1000   unsigned int nsize;
1001
1002   random_walk_task = NULL;
1003   friend = pick_random_friend ();
1004
1005   trail = GNUNET_new (struct Trail);
1006   /* We create the random walk so, no predecessor */
1007   trail->succ = friend;
1008   GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1009                                     &trail->succ_id);
1010   if (GNUNET_OK !=
1011       GNUNET_CONTAINER_multihashmap_put (trail_map,
1012                                          &trail->succ_id,
1013                                          trail,
1014                                          GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1015   {
1016     GNUNET_break (0);
1017     GNUNET_free (trail);
1018     return;
1019   }
1020   GNUNET_CONTAINER_MDLL_insert (succ,
1021                                 friend->succ_head,
1022                                 friend->succ_tail,
1023                                 trail);
1024   trail->expiration_time = GNUNET_TIME_relative_to_absolute (TRAIL_TIMEOUT);
1025   trail->hn = GNUNET_CONTAINER_heap_insert (trail_heap,
1026                                             trail,
1027                                             trail->expiration_time.abs_value_us);
1028   if (NULL == trail_timeout_task)
1029     trail_timeout_task = GNUNET_SCHEDULER_add_delayed (TRAIL_TIMEOUT,
1030                                                        &trail_timeout_callback,
1031                                                        NULL);
1032   env = GNUNET_MQ_msg (rwm,
1033                        GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
1034   rwm->hops_taken = htonl (0);
1035   rwm->trail_id = trail->succ_id;
1036   GNUNET_MQ_send (friend->mq,
1037                   env);
1038   /* clean up 'old' entry (implicitly via trail cleanup) */
1039   ft = &fingers[walk_layer];
1040
1041   if ( (NULL != ft->fingers) &&
1042        (NULL != (finger = ft->fingers[ft->walk_offset])) )
1043     delete_trail (finger->trail,
1044                   GNUNET_NO,
1045                   GNUNET_YES);
1046   if (ft->finger_array_size < (nsize = get_desired_finger_array_size()) )
1047     GNUNET_array_grow (ft->fingers,
1048                        ft->finger_array_size,
1049                        nsize);
1050   GNUNET_assert (NULL == ft->fingers[ft->walk_offset]);
1051   trail->ft = ft;
1052   trail->finger_off = ft->walk_offset;
1053   finger = GNUNET_new (struct Finger);
1054   finger->trail = trail;
1055   finger->ft = ft;
1056   ft->fingers[ft->walk_offset] = finger;
1057   ft->is_sorted = GNUNET_NO;
1058   ft->number_valid_fingers++;
1059   ft->walk_offset = (ft->walk_offset + 1) % ft->finger_array_size;
1060
1061   walk_layer = (walk_layer + 1) % NUMBER_LAYERED_ID;
1062   random_walk_task = GNUNET_SCHEDULER_add_delayed (RANDOM_WALK_DELAY,
1063                                                    &do_random_walk,
1064                                                    NULL);
1065 }
1066
1067
1068 /**
1069  * Method called whenever a peer connects.
1070  *
1071  * @param cls closure
1072  * @param peer_identity peer identity this notification is about
1073  * @param mq message queue for transmission to @a peer_identity
1074  * @return the `struct FriendInfo` for the @a peer_identity, NULL for us
1075  */
1076 static void *
1077 handle_core_connect (void *cls,
1078                      const struct GNUNET_PeerIdentity *peer_identity,
1079                      struct GNUNET_MQ_Handle *mq)
1080 {
1081   struct FriendInfo *friend;
1082
1083   /* Check for connect to self message */
1084   if (0 == memcmp (&my_identity,
1085                    peer_identity,
1086                    sizeof (struct GNUNET_PeerIdentity)))
1087     return NULL;
1088
1089   friend = GNUNET_new (struct FriendInfo);
1090   friend->id = peer_identity;
1091   friend->mq = mq;
1092   GNUNET_assert (GNUNET_OK ==
1093                  GNUNET_CONTAINER_multipeermap_put (friends_peermap,
1094                                                     peer_identity,
1095                                                     friend,
1096                                                     GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1097   if (NULL == random_walk_task)
1098   {
1099     /* random walk needs to be started -- we have a first connection */
1100     random_walk_task = GNUNET_SCHEDULER_add_now (&do_random_walk,
1101                                                  NULL);
1102   }
1103   return friend;
1104 }
1105
1106
1107 /**
1108  * To be called on core init/fail.
1109  *
1110  * @param cls service closure
1111  * @param identity the public identity of this peer
1112  */
1113 static void
1114 core_init (void *cls,
1115            const struct GNUNET_PeerIdentity *identity)
1116 {
1117   my_identity = *identity;
1118 }
1119
1120
1121 /**
1122  * Handle a `struct RandomWalkMessage` from a
1123  * #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK message.
1124  *
1125  * @param cls the `struct FriendInfo` for the sender
1126  * @param m the setup message
1127  */
1128 static void
1129 handle_dht_p2p_random_walk (void *cls,
1130                             const struct RandomWalkMessage *m)
1131 {
1132   struct FriendInfo *pred = cls;
1133   struct Trail *t;
1134   uint16_t layer;
1135
1136   layer = ntohs (m->layer);
1137   if (layer > NUMBER_LAYERED_ID)
1138   {
1139     GNUNET_break_op (0);
1140     return;
1141   }
1142   t = GNUNET_new (struct Trail);
1143   t->pred_id = m->trail_id;
1144   t->pred = pred;
1145   if (GNUNET_OK !=
1146       GNUNET_CONTAINER_multihashmap_put (trail_map,
1147                                          &t->pred_id,
1148                                          t,
1149                                          GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1150   {
1151     GNUNET_break_op (0);
1152     GNUNET_free (t);
1153     return;
1154   }
1155   GNUNET_CONTAINER_MDLL_insert (pred,
1156                                 pred->pred_head,
1157                                 pred->pred_tail,
1158                                 t);
1159   t->expiration_time = GNUNET_TIME_relative_to_absolute (TRAIL_TIMEOUT);
1160   t->hn = GNUNET_CONTAINER_heap_insert (trail_heap,
1161                                         t,
1162                                         t->expiration_time.abs_value_us);
1163   if (NULL == trail_timeout_task)
1164     trail_timeout_task = GNUNET_SCHEDULER_add_delayed (TRAIL_TIMEOUT,
1165                                                        &trail_timeout_callback,
1166                                                        NULL);
1167
1168   if (ntohl (m->hops_taken) > GDS_NSE_get ())
1169   {
1170     /* We are the last hop, generate response */
1171     struct GNUNET_MQ_Envelope *env;
1172     struct RandomWalkResponseMessage *rwrm;
1173
1174     env = GNUNET_MQ_msg (rwrm,
1175                          GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE);
1176     rwrm->reserved = htonl (0);
1177     rwrm->trail_id = m->trail_id;
1178     if (0 == layer)
1179       (void) GDS_DATACACHE_get_random_key (&rwrm->location);
1180     else
1181     {
1182       struct FingerTable *ft;
1183
1184       ft = &fingers[layer-1];
1185       if (0 == ft->number_valid_fingers)
1186       {
1187         GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1188                                           &rwrm->location);
1189       }
1190       else
1191       {
1192         struct Finger *f;
1193         unsigned int off;
1194         unsigned int i;
1195
1196         off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
1197                                         ft->number_valid_fingers);
1198         for (i=0; (NULL == (f = ft->fingers[i])) || (off > 0); i++)
1199           if (NULL != f) off--;
1200         rwrm->location = f->destination;
1201       }
1202     }
1203     GNUNET_MQ_send (pred->mq,
1204                     env);
1205   }
1206   else
1207   {
1208     struct GNUNET_MQ_Envelope *env;
1209     struct RandomWalkMessage *rwm;
1210     struct FriendInfo *succ;
1211
1212     /* extend the trail by another random hop */
1213     succ = pick_random_friend ();
1214     GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1215                                       &t->succ_id);
1216     t->succ = succ;
1217     if (GNUNET_OK !=
1218         GNUNET_CONTAINER_multihashmap_put (trail_map,
1219                                            &t->succ_id,
1220                                            t,
1221                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1222     {
1223       GNUNET_break (0);
1224       GNUNET_CONTAINER_MDLL_remove (pred,
1225                                     pred->pred_head,
1226                                     pred->pred_tail,
1227                                     t);
1228       GNUNET_free (t);
1229       return;
1230     }
1231     GNUNET_CONTAINER_MDLL_insert (succ,
1232                                   succ->succ_head,
1233                                   succ->succ_tail,
1234                                   t);
1235     env = GNUNET_MQ_msg (rwm,
1236                          GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
1237     rwm->hops_taken = htons (1 + ntohs (m->hops_taken));
1238     rwm->layer = m->layer;
1239     rwm->trail_id = t->succ_id;
1240     GNUNET_MQ_send (succ->mq,
1241                     env);
1242   }
1243 }
1244
1245
1246 /**
1247  * Handle a `struct RandomWalkResponseMessage`.
1248  *
1249  * @param cls closure
1250  * @param rwrm the setup response message
1251  */
1252 static void
1253 handle_dht_p2p_random_walk_response (void *cls,
1254                                      const struct RandomWalkResponseMessage *rwrm)
1255 {
1256   struct Trail *trail;
1257   struct FriendInfo *pred;
1258   struct FingerTable *ft;
1259   struct Finger *finger;
1260
1261   trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
1262                                              &rwrm->trail_id);
1263   if (NULL == trail)
1264   {
1265     /* TODO: log/statistics: we didn't find the trail (can happen) */
1266     return;
1267   }
1268   if (NULL != (pred = trail->pred))
1269   {
1270     /* We are not the first hop, keep forwarding */
1271     struct GNUNET_MQ_Envelope *env;
1272     struct RandomWalkResponseMessage *rwrm2;
1273
1274     env = GNUNET_MQ_msg (rwrm2,
1275                          GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE);
1276     rwrm2->reserved = htonl (0);
1277     rwrm2->location = rwrm->location;
1278     rwrm2->trail_id = trail->pred_id;
1279     GNUNET_MQ_send (pred->mq,
1280                     env);
1281     return;
1282   }
1283   /* We are the first hop, complete finger */
1284   if (NULL == (ft = trail->ft))
1285   {
1286     /* Eh, why did we create the trail if we have no FT? */
1287     GNUNET_break (0);
1288     delete_trail (trail,
1289                   GNUNET_NO,
1290                   GNUNET_YES);
1291     return;
1292   }
1293   if (NULL == (finger = ft->fingers[trail->finger_off]))
1294   {
1295     /* Eh, finger got deleted, but why not the trail as well? */
1296     GNUNET_break (0);
1297     delete_trail (trail,
1298                   GNUNET_NO,
1299                   GNUNET_YES);
1300     return;
1301   }
1302
1303
1304   // 1) lookup trail => find Finger entry => fill in 'destination' and mark valid, move to end of sorted array,
1305   //mark unsorted, update links from 'trails'
1306   /*
1307    * Steps :
1308    *  1 check if we are the correct layer
1309    *  1.a if true : add the returned value (finger) in the db structure
1310    *  1.b if true : do nothing
1311    */
1312   /* FIXME: add the value in db structure 1.a */
1313
1314 }
1315
1316
1317 /**
1318  * Handle a `struct TrailDestroyMessage`.
1319  *
1320  * @param cls closure
1321  * @param tdm the trail destroy message
1322  */
1323 static void
1324 handle_dht_p2p_trail_destroy (void *cls,
1325                               const struct TrailDestroyMessage *tdm)
1326 {
1327   struct FriendInfo *sender = cls;
1328   struct Trail *trail;
1329
1330   trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
1331                                              &tdm->trail_id);
1332   delete_trail (trail,
1333                 ( (NULL != trail->succ) &&
1334                   (0 == memcmp (sender->id,
1335                                 &trail->succ->id,
1336                                 sizeof (struct GNUNET_PeerIdentity))) ),
1337                 ( (NULL != trail->pred) &&
1338                   (0 == memcmp (sender->id,
1339                                 &trail->pred->id,
1340                                 sizeof (struct GNUNET_PeerIdentity))) ));
1341 }
1342
1343
1344 /**
1345  * Handle a `struct FindSuccessorMessage` from a #GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND
1346  * message.
1347  *
1348  * @param cls closure (NULL)
1349  * @param trail_id path to the originator
1350  * @param trail_path path the message took on the trail, if available
1351  * @param trail_path_length number of entries on the @a trail_path
1352  * @param message the finger setup message
1353  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1354  */
1355 static int
1356 handle_dht_p2p_successor_find (void *cls,
1357                                const struct GNUNET_HashCode *trail_id,
1358                                const struct GNUNET_PeerIdentity *trail_path,
1359                                unsigned int trail_path_length,
1360                                const struct GNUNET_MessageHeader *message)
1361 {
1362   const struct FindSuccessorMessage *fsm;
1363
1364   /* We do not expect to track trails for the forward-direction
1365      of successor finding... */
1366   GNUNET_break_op (0 == trail_path_length);
1367   fsm = (const struct FindSuccessorMessage *) message;
1368   GDS_DATACACHE_get_successors (&fsm->key,
1369                                 &GDS_NEIGHBOURS_send_get_result,
1370                                 (void *) trail_id);
1371   return GNUNET_OK;
1372 }
1373
1374
1375 /**
1376  * Handle a `struct PeerGetMessage`.
1377  *
1378  * @param cls closure (NULL)
1379  * @param trail_id path to the originator
1380  * @param trail_path path the message took on the trail, if available
1381  * @param trail_path_length number of entries on the @a trail_path
1382  * @param message the peer get message
1383  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1384  */
1385 static int
1386 handle_dht_p2p_peer_get (void *cls,
1387                          const struct GNUNET_HashCode *trail_id,
1388                          const struct GNUNET_PeerIdentity *trail_path,
1389                          unsigned int trail_path_length,
1390                          const struct GNUNET_MessageHeader *message)
1391 {
1392 #if 0
1393   const struct PeerGetMessage *pgm;
1394
1395   // FIXME: note: never called like this, message embedded with trail route!
1396   pgm = (const struct PeerGetMessage *) message;
1397 #endif
1398   // -> lookup in datacache (figure out way to remember trail!)
1399      /*
1400     * steps :
1401     *   1 extract the result
1402     *   2 save the peer
1403     *   3 send it using the good trail
1404     *
1405     * What do i do when i don't have the key/value?
1406     */
1407
1408   return GNUNET_OK;
1409 }
1410
1411
1412 /**
1413  * Handle a `struct PeerGetResultMessage`.
1414  *
1415  * @param cls closure (NULL)
1416  * @param trail_id path to the originator
1417  * @param trail_path path the message took on the trail, if available
1418  * @param trail_path_length number of entries on the @a trail_path
1419  * @param message the peer get result message
1420  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1421  */
1422 static int
1423 handle_dht_p2p_peer_get_result (void *cls,
1424                                 const struct GNUNET_HashCode *trail_id,
1425                                 const struct GNUNET_PeerIdentity *trail_path,
1426                                 unsigned int trail_path_length,
1427                                 const struct GNUNET_MessageHeader *message)
1428 {
1429 #if 0
1430   const struct PeerGetResultMessage *pgrm;
1431
1432   pgrm = (const struct PeerGetResultMessage *) message;
1433 #endif
1434   // pretty much: parse, & pass to client (there is some call for that...)
1435
1436 #if 0
1437   GDS_CLIENTS_process_get (options,
1438                            type,
1439                            0, 0,
1440                            path_length, path,
1441                            key);
1442   (void) GDS_DATACACHE_handle_get (trail_id,
1443                                    key,
1444                                    type,
1445                                    xquery,
1446                                    xquery_size,
1447                                    &reply_bf,
1448                                    reply_bf_mutator);
1449 #endif
1450   return GNUNET_OK;
1451 }
1452
1453
1454 /**
1455  * Handle a `struct PeerPutMessage`.
1456  *
1457  * @param cls closure (NULL)
1458  * @param trail_id path to the originator
1459  * @param trail_path path the message took on the trail, if available
1460  * @param trail_path_length number of entries on the @a trail_path
1461  * @param message the peer put message
1462  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1463  */
1464 static int
1465 handle_dht_p2p_peer_put (void *cls,
1466                          const struct GNUNET_HashCode *trail_id,
1467                          const struct GNUNET_PeerIdentity *trail_path,
1468                          unsigned int trail_path_length,
1469                          const struct GNUNET_MessageHeader *message)
1470 {
1471 #if 0
1472   const struct PeerGetResultMessage *pgrm;
1473
1474   pgrm = (const struct PeerGetResultMessage *) message;
1475 #endif
1476   // parse & store in datacache, this is in response to us asking for successors.
1477   /*
1478    * steps :
1479    * 1 check the size of the message
1480    * 2 use the API to add the value in the "database". Check on the xdht file, how to do it.
1481    * 3 Did i a have to return a notification or did i have to return GNUNET_[OK|SYSERR]?
1482    */
1483 #if 0
1484   GDS_DATACACHE_handle_put (expiration_time,
1485                             key,
1486                             combined_path_length, combined_path,
1487                             block_type,
1488                             data_size,
1489                             data);
1490   GDS_CLIENTS_process_put (options,
1491                            block_type,
1492                            0, 0,
1493                            combined_path_length, combined_path,
1494                            expiration_time,
1495                            key,
1496                            data,
1497                            data_size);
1498 #endif
1499   return GNUNET_OK;
1500 }
1501
1502
1503 /**
1504  * Handler for a message we received along some trail.
1505  *
1506  * @param cls closure
1507  * @param trail_id trail identifier
1508  * @param trail_path path the message took on the trail, if available
1509  * @param trail_path_length number of entries on the @a trail_path
1510  * @param message the message we got
1511  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1512  */
1513 typedef int
1514 (*TrailHandlerCallback)(void *cls,
1515                         const struct GNUNET_HashCode *trail_id,
1516                         const struct GNUNET_PeerIdentity *trail_path,
1517                         unsigned int trail_path_length,
1518                         const struct GNUNET_MessageHeader *message);
1519
1520
1521 /**
1522  * Definition of a handler for a message received along some trail.
1523  */
1524 struct TrailHandler
1525 {
1526   /**
1527    * NULL for end-of-list.
1528    */
1529   TrailHandlerCallback callback;
1530
1531   /**
1532    * Closure for @e callback.
1533    */
1534   void *cls;
1535
1536   /**
1537    * Message type this handler addresses.
1538    */
1539   uint16_t message_type;
1540
1541   /**
1542    * Use 0 for variable-size.
1543    */
1544   uint16_t message_size;
1545 };
1546
1547
1548 /**
1549  * Check that a `struct TrailRouteMessage` is well-formed.
1550  *
1551  * @param cls closure
1552  * @param trm the finger destroy message
1553  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1554  */
1555 static int
1556 check_dht_p2p_trail_route (void *cls,
1557                            const struct TrailRouteMessage *trm)
1558 {
1559   const struct GNUNET_PeerIdentity *path;
1560   uint16_t path_length;
1561   const struct GNUNET_MessageHeader *payload;
1562   size_t msize;
1563
1564   msize = ntohs (trm->header.size);
1565   path_length = ntohs (trm->path_length);
1566   if (msize < sizeof (struct TrailRouteMessage) +
1567       path_length * sizeof (struct GNUNET_PeerIdentity) +
1568       sizeof (struct GNUNET_MessageHeader) )
1569   {
1570     GNUNET_break_op (0);
1571     return GNUNET_SYSERR;
1572   }
1573   path = (const struct GNUNET_PeerIdentity *) &trm[1];
1574   payload = (const struct GNUNET_MessageHeader *) &path[path_length];
1575   if (msize != (ntohs (payload->size) +
1576                 sizeof (struct TrailRouteMessage) +
1577                 path_length * sizeof (struct GNUNET_PeerIdentity)))
1578   {
1579     GNUNET_break_op (0);
1580     return GNUNET_SYSERR;
1581   }
1582   /* FIXME: verify payload is OK!? */
1583   return GNUNET_OK;
1584 }
1585
1586
1587 /**
1588  * Handle a `struct TrailRouteMessage`.
1589  *
1590  * @param cls closure
1591  * @param trm the finger destroy message
1592  */
1593 static void
1594 handle_dht_p2p_trail_route (void *cls,
1595                             const struct TrailRouteMessage *trm)
1596 {
1597   static const struct TrailHandler handlers[] = {
1598     { &handle_dht_p2p_successor_find, NULL,
1599       GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND,
1600       sizeof (struct FindSuccessorMessage) },
1601     { &handle_dht_p2p_peer_get, NULL,
1602       GNUNET_MESSAGE_TYPE_WDHT_GET,
1603       0 },
1604     { &handle_dht_p2p_peer_get_result, NULL,
1605       GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT,
1606       0 },
1607     { &handle_dht_p2p_peer_put, NULL,
1608       GNUNET_MESSAGE_TYPE_WDHT_PUT,
1609       0 },
1610     { NULL, NULL, 0, 0 }
1611   };
1612   struct FriendInfo *sender = cls;
1613   unsigned int i;
1614   const struct GNUNET_PeerIdentity *path;
1615   uint16_t path_length;
1616   const struct GNUNET_MessageHeader *payload;
1617   const struct TrailHandler *th;
1618   struct Trail *trail;
1619
1620   path_length = ntohs (trm->path_length);
1621   path = (const struct GNUNET_PeerIdentity *) &trm[1];
1622   payload = (const struct GNUNET_MessageHeader *) &path[path_length];
1623   /* Is this message for us? */
1624   trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
1625                                              &trm->trail_id);
1626   if ( (NULL != trail->pred) &&
1627        (0 == memcmp (sender->id,
1628                      &trail->pred->id,
1629                      sizeof (struct GNUNET_PeerIdentity))) )
1630   {
1631     /* forward to 'successor' */
1632     if (NULL != trail->succ)
1633     {
1634       forward_message_on_trail (trail->succ,
1635                                 &trail->succ_id,
1636                                 ntohs (trm->record_path),
1637                                 sender->id,
1638                                 path,
1639                                 path_length,
1640                                 payload);
1641       return;
1642     }
1643   }
1644   else
1645   {
1646     /* forward to 'predecessor' */
1647     GNUNET_break_op ( (NULL != trail->succ) &&
1648                       (0 == memcmp (sender->id,
1649                                     &trail->succ->id,
1650                                     sizeof (struct GNUNET_PeerIdentity))) );
1651     if (NULL != trail->pred)
1652     {
1653       forward_message_on_trail (trail->pred,
1654                                 &trail->pred_id,
1655                                 ntohs (trm->record_path),
1656                                 sender->id,
1657                                 path,
1658                                 path_length,
1659                                 payload);
1660       return;
1661     }
1662   }
1663
1664   /* Message is for us, dispatch to handler */
1665   th = NULL;
1666   for (i=0; NULL != handlers[i].callback; i++)
1667   {
1668     th = &handlers[i];
1669     if (ntohs (payload->type) == th->message_type)
1670     {
1671       if ( (0 == th->message_size) ||
1672            (ntohs (payload->size) == th->message_size) )
1673         th->callback (th->cls,
1674                       &trm->trail_id,
1675                       path,
1676                       path_length,
1677                       payload);
1678       else
1679         GNUNET_break_op (0);
1680       break;
1681     }
1682   }
1683   GNUNET_break_op (NULL != th);
1684 }
1685
1686
1687 /**
1688  * Initialize neighbours subsystem.
1689  *
1690  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1691  */
1692 int
1693 GDS_NEIGHBOURS_init (void)
1694 {
1695   struct GNUNET_MQ_MessageHandler core_handlers[] = {
1696     GNUNET_MQ_hd_fixed_size (dht_p2p_random_walk,
1697                              GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK,
1698                              struct RandomWalkMessage,
1699                              NULL),
1700     GNUNET_MQ_hd_fixed_size (dht_p2p_random_walk_response,
1701                              GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE,
1702                              struct RandomWalkResponseMessage,
1703                              NULL),
1704     GNUNET_MQ_hd_fixed_size (dht_p2p_trail_destroy,
1705                              GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY,
1706                              struct TrailDestroyMessage,
1707                              NULL),
1708     GNUNET_MQ_hd_var_size (dht_p2p_trail_route,
1709                            GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE,
1710                            struct TrailRouteMessage,
1711                            NULL),
1712     GNUNET_MQ_handler_end ()
1713   };
1714
1715   core_api = GNUNET_CORE_connect (GDS_cfg, NULL,
1716                                   &core_init,
1717                                   &handle_core_connect,
1718                                   &handle_core_disconnect,
1719                                   core_handlers);
1720   if (NULL == core_api)
1721     return GNUNET_SYSERR;
1722   friends_peermap = GNUNET_CONTAINER_multipeermap_create (256,
1723                                                           GNUNET_NO);
1724   trail_map = GNUNET_CONTAINER_multihashmap_create (1024,
1725                                                     GNUNET_YES);
1726   trail_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
1727   return GNUNET_OK;
1728 }
1729
1730
1731 /**
1732  * Shutdown neighbours subsystem.
1733  */
1734 void
1735 GDS_NEIGHBOURS_done (void)
1736 {
1737   if (NULL == core_api)
1738     return;
1739   GNUNET_CORE_disconnect (core_api);
1740   core_api = NULL;
1741   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friends_peermap));
1742   GNUNET_CONTAINER_multipeermap_destroy (friends_peermap);
1743   friends_peermap = NULL;
1744   GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (trail_map));
1745   GNUNET_CONTAINER_multihashmap_destroy (trail_map);
1746   trail_map = NULL;
1747   GNUNET_CONTAINER_heap_destroy (trail_heap);
1748   trail_heap = NULL;
1749   if (NULL != trail_timeout_task)
1750   {
1751     GNUNET_SCHEDULER_cancel (trail_timeout_task);
1752     trail_timeout_task = NULL;
1753   }
1754 }
1755
1756
1757 /**
1758  * Get my identity
1759  *
1760  * @return my identity
1761  */
1762 struct GNUNET_PeerIdentity *
1763 GDS_NEIGHBOURS_get_id (void)
1764 {
1765   return &my_identity;
1766 }
1767
1768 /* end of gnunet-service-wdht_neighbours.c */