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