src/dht/gnunet-service-wdht_neighbours.c

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