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_SUCCESSOR_FIND
 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   // NOTE: actually more complicated, see paper!
 646 }
 647
 648
 649 /**
 650  * Delete a trail, it died (timeout, link failure, etc.).
 651  *
 652  * @param trail trail to delete from all data structures
 653  * @param inform_pred should we notify the predecessor?
 654  * @param inform_succ should we inform the successor?
 655  */
 656 static void
 657 delete_trail (struct Trail *trail,
 658               int inform_pred,
 659               int inform_succ)
 660 {
 661   struct FriendInfo *friend;
 662   struct GNUNET_MQ_Envelope *env;
 663   struct TrailDestroyMessage *tdm;
 664   struct Finger *finger;
 665
 666   friend = trail->pred;
 667   if (NULL != friend)
 668   {
 669     if (GNUNET_YES == inform_pred)
 670     {
 671       env = GNUNET_MQ_msg (tdm,
 672                            GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
 673       tdm->trail_id = trail->pred_id;
 674       GNUNET_MQ_send (friend->mq,
 675                       env);
 676     }
 677     GNUNET_CONTAINER_MDLL_remove (pred,
 678                                   friend->pred_head,
 679                                   friend->pred_tail,
 680                                   trail);
 681   }
 682   friend = trail->succ;
 683   if (NULL != friend)
 684   {
 685     if (GNUNET_YES == inform_succ)
 686     {
 687       env = GNUNET_MQ_msg (tdm,
 688                            GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
 689       tdm->trail_id = trail->pred_id;
 690       GNUNET_MQ_send (friend->mq,
 691                       env);
 692     }
 693     GNUNET_CONTAINER_MDLL_remove (succ,
 694                                   friend->pred_head,
 695                                   friend->pred_tail,
 696                                   trail);
 697   }
 698   GNUNET_break (trail ==
 699                 GNUNET_CONTAINER_heap_remove_node (trail->hn));
 700   finger = trail->ft->fingers[trail->finger_off];
 701   if (NULL != finger)
 702   {
 703     trail->ft->fingers[trail->finger_off] = NULL;
 704     trail->ft->number_valid_fingers--;
 705     GNUNET_free (finger);
 706   }
 707   GNUNET_free (trail);
 708 }
 709
 710
 711 /**
 712  * Forward the given payload message along the trail.
 713  *
 714  * @param next_target which direction along the trail should we forward
 715  * @param trail_id which trail should we forward along
 716  * @param have_path do we track the forwarding path?
 717  * @param predecessor which peer do we tack on to the path?
 718  * @param path path the message has taken so far along the trail
 719  * @param path_length number of entries in @a path
 720  * @param payload payload of the message
 721  */
 722 static void
 723 forward_message_on_trail (struct FriendInfo *next_target,
 724                           const struct GNUNET_HashCode *trail_id,
 725                           int have_path,
 726                           const struct GNUNET_PeerIdentity *predecessor,
 727                           const struct GNUNET_PeerIdentity *path,
 728                           uint16_t path_length,
 729                           const struct GNUNET_MessageHeader *payload)
 730 {
 731   struct GNUNET_MQ_Envelope *env;
 732   struct TrailRouteMessage *trm;
 733   struct GNUNET_PeerIdentity *new_path;
 734   unsigned int plen;
 735   uint16_t payload_len;
 736
 737   payload_len = ntohs (payload->size);
 738   if (have_path)
 739   {
 740     plen = path_length + 1;
 741     if (plen >= (GNUNET_SERVER_MAX_MESSAGE_SIZE
 742                  - payload_len
 743                  - sizeof (struct TrailRouteMessage))
 744         / sizeof (struct GNUNET_PeerIdentity))
 745     {
 746       /* Should really not have paths this long... */
 747       GNUNET_break_op (0);
 748       plen = 0;
 749       have_path = 0;
 750     }
 751   }
 752   else
 753   {
 754     GNUNET_break_op (0 == path_length);
 755     path_length = 0;
 756     plen = 0;
 757   }
 758   env = GNUNET_MQ_msg_extra (trm,
 759                              payload_len +
 760                              plen * sizeof (struct GNUNET_PeerIdentity),
 761                              GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE);
 762   trm->record_path = htons (have_path);
 763   trm->path_length = htons (plen);
 764   trm->trail_id = *trail_id;
 765   new_path = (struct GNUNET_PeerIdentity *) &trm[1];
 766   if (have_path)
 767   {
 768     memcpy (new_path,
 769             path,
 770             path_length * sizeof (struct GNUNET_PeerIdentity));
 771     new_path[path_length] = *predecessor;
 772   }
 773   memcpy (&new_path[plen],
 774           payload,
 775           payload_len);
 776   GNUNET_MQ_send (next_target->mq,
 777                   env);
 778 }
 779
 780
 781 /**
 782  * Send the get result to requesting client.
 783  *
 784  * @param trail_id trail identifying where to send the result to, NULL for us
 785  * @param options routing options (from GET request)
 786  * @param key Key of the requested data.
 787  * @param type Block type
 788  * @param put_path_length Number of peers in @a put_path
 789  * @param put_path Path taken to put the data at its stored location.
 790  * @param expiration When will this result expire?
 791  * @param data Payload to store
 792  * @param data_size Size of the @a data
 793  */
 794 void
 795 GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *trail_id,
 796                                 enum GNUNET_DHT_RouteOption options,
 797                                 const struct GNUNET_HashCode *key,
 798                                 enum GNUNET_BLOCK_Type type,
 799                                 unsigned int put_path_length,
 800                                 const struct GNUNET_PeerIdentity *put_path,
 801                                 struct GNUNET_TIME_Absolute expiration,
 802                                 const void *data,
 803                                 size_t data_size)
 804 {
 805   struct GNUNET_MessageHeader *payload;
 806   struct Trail *trail;
 807
 808   trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
 809                                              trail_id);
 810   if (NULL == trail)
 811   {
 812     /* TODO: inform statistics */
 813     return;
 814   }
 815   if (NULL == trail->pred)
 816   {
 817     /* result is for *us* (local client) */
 818     GDS_CLIENTS_handle_reply (expiration,
 819                               key,
 820                               0, NULL,
 821                               put_path_length, put_path,
 822                               type,
 823                               data_size,
 824                               data);
 825     return;
 826   }
 827
 828   payload = GNUNET_malloc(sizeof(struct GNUNET_MessageHeader) + data_size);
 829   payload->size = data_size;
 830   payload->type = GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT;
 831
 832   forward_message_on_trail (trail->pred,
 833                             trail_id,
 834                             0 /* FIXME: put something right */,
 835                             &my_identity,
 836                             NULL, 0,
 837                             payload);
 838   GNUNET_free (payload);
 839 }
 840
 841
 842 /**
 843  * Method called whenever a peer disconnects.
 844  *
 845  * @param cls closure
 846  * @param peer peer identity this notification is about
 847  */
 848 static void
 849 handle_core_disconnect (void *cls,
 850                         const struct GNUNET_PeerIdentity *peer)
 851 {
 852   struct FriendInfo *remove_friend;
 853   struct Trail *t;
 854
 855   /* If disconnected to own identity, then return. */
 856   if (0 == memcmp (&my_identity,
 857                    peer,
 858                    sizeof (struct GNUNET_PeerIdentity)))
 859     return;
 860
 861   if (NULL == (remove_friend =
 862                GNUNET_CONTAINER_multipeermap_get (friends_peermap,
 863                                                   peer)))
 864   {
 865     GNUNET_break (0);
 866     return;
 867   }
 868
 869   GNUNET_assert (GNUNET_YES ==
 870                  GNUNET_CONTAINER_multipeermap_remove (friends_peermap,
 871                                                        peer,
 872                                                        remove_friend));
 873   while (NULL != (t = remove_friend->succ_head))
 874     delete_trail (t,
 875                   GNUNET_YES,
 876                   GNUNET_NO);
 877   while (NULL != (t = remove_friend->pred_head))
 878     delete_trail (t,
 879                   GNUNET_NO,
 880                   GNUNET_YES);
 881   GNUNET_MQ_destroy (remove_friend->mq);
 882   GNUNET_free (remove_friend);
 883   if (0 ==
 884       GNUNET_CONTAINER_multipeermap_size (friends_peermap))
 885   {
 886     GNUNET_SCHEDULER_cancel (random_walk_task);
 887     random_walk_task = NULL;
 888   }
 889 }
 890
 891
 892 /**
 893  * Function called with a random friend to be returned.
 894  *
 895  * @param cls a `struct FriendInfo **` with where to store the result
 896  * @param peer the peer identity of the friend (ignored)
 897  * @param value the `struct FriendInfo *` that was selected at random
 898  * @return #GNUNET_OK (all good)
 899  */
 900 static int
 901 pick_random_helper (void *cls,
 902                     const struct GNUNET_PeerIdentity *peer,
 903                     void *value)
 904 {
 905   struct FriendInfo **fi = cls;
 906   struct FriendInfo *v = value;
 907
 908   *fi = v;
 909   return GNUNET_OK;
 910 }
 911
 912
 913 /**
 914  * Pick random friend from friends for random walk.
 915  *
 916  * @return NULL if we have no friends
 917  */
 918 static struct FriendInfo *
 919 pick_random_friend ()
 920 {
 921   struct FriendInfo *ret;
 922
 923   ret = NULL;
 924   if (0 ==
 925       GNUNET_CONTAINER_multipeermap_get_random (friends_peermap,
 926                                                 &pick_random_helper,
 927                                                 &ret))
 928     return NULL;
 929   return ret;
 930 }
 931
 932
 933 /**
 934  * One of our trails might have timed out, check and
 935  * possibly initiate cleanup.
 936  *
 937  * @param cls NULL
 938  * @param tc unused
 939  */
 940 static void
 941 trail_timeout_callback (void *cls,
 942                         const struct GNUNET_SCHEDULER_TaskContext *tc)
 943 {
 944   struct Trail *trail;
 945   struct GNUNET_TIME_Relative left;
 946
 947   trail_timeout_task = NULL;
 948   while (NULL != (trail = GNUNET_CONTAINER_heap_peek (trail_heap)))
 949   {
 950     left = GNUNET_TIME_absolute_get_remaining (trail->expiration_time);
 951     if (0 != left.rel_value_us)
 952       break;
 953     delete_trail (trail,
 954                   GNUNET_YES,
 955                   GNUNET_YES);
 956   }
 957   if (NULL != trail)
 958     trail_timeout_task = GNUNET_SCHEDULER_add_delayed (left,
 959                                                        &trail_timeout_callback,
 960                                                        NULL);
 961 }
 962
 963
 964 /**
 965  * Compute how big our finger arrays should be (at least).
 966  *
 967  * @return size of the finger array, never 0
 968  */
 969 static unsigned int
 970 get_desired_finger_array_size ()
 971 {
 972   /* FIXME: This is just a stub... */
 973   return 64;
 974 }
 975
 976
 977 /**
 978  * Initiate a random walk.
 979  *
 980  * @param cls NULL
 981  * @param tc unused
 982  */
 983 static void
 984 do_random_walk (void *cls,
 985                 const struct GNUNET_SCHEDULER_TaskContext *tc)
 986 {
 987   static unsigned int walk_layer;
 988   struct FriendInfo *friend;
 989   struct GNUNET_MQ_Envelope *env;
 990   struct RandomWalkMessage *rwm;
 991   struct FingerTable *ft;
 992   struct Finger *finger;
 993   struct Trail *trail;
 994   unsigned int nsize;
 995
 996   random_walk_task = NULL;
 997   friend = pick_random_friend ();
 998
 999   trail = GNUNET_new (struct Trail);
1000   /* We create the random walk so, no predecessor */
1001   trail->succ = friend;
1002   GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1003                                     &trail->succ_id);
1004   if (GNUNET_OK !=
1005       GNUNET_CONTAINER_multihashmap_put (trail_map,
1006                                          &trail->succ_id,
1007                                          trail,
1008                                          GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1009   {
1010     GNUNET_break (0);
1011     GNUNET_free (trail);
1012     return;
1013   }
1014   GNUNET_CONTAINER_MDLL_insert (succ,
1015                                 friend->succ_head,
1016                                 friend->succ_tail,
1017                                 trail);
1018   trail->expiration_time = GNUNET_TIME_relative_to_absolute (TRAIL_TIMEOUT);
1019   trail->hn = GNUNET_CONTAINER_heap_insert (trail_heap,
1020                                             trail,
1021                                             trail->expiration_time.abs_value_us);
1022   if (NULL == trail_timeout_task)
1023     trail_timeout_task = GNUNET_SCHEDULER_add_delayed (TRAIL_TIMEOUT,
1024                                                        &trail_timeout_callback,
1025                                                        NULL);
1026   env = GNUNET_MQ_msg (rwm,
1027                        GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
1028   rwm->hops_taken = htonl (0);
1029   rwm->trail_id = trail->succ_id;
1030   GNUNET_MQ_send (friend->mq,
1031                   env);
1032   /* clean up 'old' entry (implicitly via trail cleanup) */
1033   ft = &fingers[walk_layer];
1034
1035   if ( (NULL != ft->fingers) &&
1036        (NULL != (finger = ft->fingers[ft->walk_offset])) )
1037     delete_trail (finger->trail,
1038                   GNUNET_NO,
1039                   GNUNET_YES);
1040   if (ft->finger_array_size < (nsize = get_desired_finger_array_size()) )
1041     GNUNET_array_grow (ft->fingers,
1042                        ft->finger_array_size,
1043                        nsize);
1044   GNUNET_assert (NULL == ft->fingers[ft->walk_offset]);
1045   trail->ft = ft;
1046   trail->finger_off = ft->walk_offset;
1047   finger = GNUNET_new (struct Finger);
1048   finger->trail = trail;
1049   finger->ft = ft;
1050   ft->fingers[ft->walk_offset] = finger;
1051   ft->is_sorted = GNUNET_NO;
1052   ft->number_valid_fingers++;
1053   ft->walk_offset = (ft->walk_offset + 1) % ft->finger_array_size;
1054
1055   walk_layer = (walk_layer + 1) % NUMBER_LAYERED_ID;
1056   random_walk_task = GNUNET_SCHEDULER_add_delayed (RANDOM_WALK_DELAY,
1057                                                    &do_random_walk,
1058                                                    NULL);
1059 }
1060
1061
1062 /**
1063  * Method called whenever a peer connects.
1064  *
1065  * @param cls closure
1066  * @param peer_identity peer identity this notification is about
1067  */
1068 static void
1069 handle_core_connect (void *cls,
1070                      const struct GNUNET_PeerIdentity *peer_identity)
1071 {
1072   struct FriendInfo *friend;
1073
1074   /* Check for connect to self message */
1075   if (0 == memcmp (&my_identity,
1076                    peer_identity,
1077                    sizeof (struct GNUNET_PeerIdentity)))
1078     return;
1079
1080   /* If peer already exists in our friend_peermap, then exit. */
1081   if (GNUNET_YES ==
1082       GNUNET_CONTAINER_multipeermap_contains (friends_peermap,
1083                                               peer_identity))
1084   {
1085     GNUNET_break (0);
1086     return;
1087   }
1088
1089   friend = GNUNET_new (struct FriendInfo);
1090   friend->id = *peer_identity;
1091   friend->mq = GNUNET_CORE_mq_create (core_api,
1092                                       peer_identity);
1093   GNUNET_assert (GNUNET_OK ==
1094                  GNUNET_CONTAINER_multipeermap_put (friends_peermap,
1095                                                     peer_identity,
1096                                                     friend,
1097                                                     GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1098   if (NULL == random_walk_task)
1099   {
1100     /* random walk needs to be started -- we have a first connection */
1101     random_walk_task = GNUNET_SCHEDULER_add_now (&do_random_walk,
1102                                                  NULL);
1103   }
1104 }
1105
1106
1107 /**
1108  * To be called on core init/fail.
1109  *
1110  * @param cls service closure
1111  * @param identity the public identity of this peer
1112  */
1113 static void
1114 core_init (void *cls,
1115            const struct GNUNET_PeerIdentity *identity)
1116 {
1117   my_identity = *identity;
1118 }
1119
1120
1121 /**
1122  * Handle a `struct RandomWalkMessage` from a
1123  * #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK message.
1124  *
1125  * @param cls closure (NULL)
1126  * @param peer sender identity
1127  * @param message the setup message
1128  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1129  */
1130 static int
1131 handle_dht_p2p_random_walk (void *cls,
1132                             const struct GNUNET_PeerIdentity *peer,
1133                             const struct GNUNET_MessageHeader *message)
1134 {
1135   const struct RandomWalkMessage *m;
1136   struct Trail *t;
1137   struct FriendInfo *pred;
1138   uint16_t layer;
1139
1140   m = (const struct RandomWalkMessage *) message;
1141   layer = ntohs (m->layer);
1142   if (layer > NUMBER_LAYERED_ID)
1143   {
1144     GNUNET_break_op (0);
1145     return GNUNET_SYSERR;
1146   }
1147   pred = GNUNET_CONTAINER_multipeermap_get (friends_peermap,
1148                                             peer);
1149   t = GNUNET_new (struct Trail);
1150   t->pred_id = m->trail_id;
1151   t->pred = pred;
1152   if (GNUNET_OK !=
1153       GNUNET_CONTAINER_multihashmap_put (trail_map,
1154                                          &t->pred_id,
1155                                          t,
1156                                          GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1157   {
1158     GNUNET_break_op (0);
1159     GNUNET_free (t);
1160     return GNUNET_SYSERR;
1161   }
1162   GNUNET_CONTAINER_MDLL_insert (pred,
1163                                 pred->pred_head,
1164                                 pred->pred_tail,
1165                                 t);
1166   t->expiration_time = GNUNET_TIME_relative_to_absolute (TRAIL_TIMEOUT);
1167   t->hn = GNUNET_CONTAINER_heap_insert (trail_heap,
1168                                         t,
1169                                         t->expiration_time.abs_value_us);
1170   if (NULL == trail_timeout_task)
1171     trail_timeout_task = GNUNET_SCHEDULER_add_delayed (TRAIL_TIMEOUT,
1172                                                        &trail_timeout_callback,
1173                                                        NULL);
1174
1175   if (ntohl (m->hops_taken) > GDS_NSE_get ())
1176   {
1177     /* We are the last hop, generate response */
1178     struct GNUNET_MQ_Envelope *env;
1179     struct RandomWalkResponseMessage *rwrm;
1180
1181     env = GNUNET_MQ_msg (rwrm,
1182                          GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE);
1183     rwrm->reserved = htonl (0);
1184     rwrm->trail_id = m->trail_id;
1185     if (0 == layer)
1186       (void) GDS_DATACACHE_get_random_key (&rwrm->location);
1187     else
1188     {
1189       struct FingerTable *ft;
1190
1191       ft = &fingers[layer-1];
1192       if (0 == ft->number_valid_fingers)
1193       {
1194         GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1195                                           &rwrm->location);
1196       }
1197       else
1198       {
1199         struct Finger *f;
1200         unsigned int off;
1201         unsigned int i;
1202
1203         off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
1204                                         ft->number_valid_fingers);
1205         for (i=0; (NULL == (f = ft->fingers[i])) || (off > 0); i++)
1206           if (NULL != f) off--;
1207         rwrm->location = f->destination;
1208       }
1209     }
1210     GNUNET_MQ_send (pred->mq,
1211                     env);
1212   }
1213   else
1214   {
1215     struct GNUNET_MQ_Envelope *env;
1216     struct RandomWalkMessage *rwm;
1217     struct FriendInfo *succ;
1218
1219     /* extend the trail by another random hop */
1220     succ = pick_random_friend ();
1221     GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
1222                                       &t->succ_id);
1223     t->succ = succ;
1224     if (GNUNET_OK !=
1225         GNUNET_CONTAINER_multihashmap_put (trail_map,
1226                                            &t->succ_id,
1227                                            t,
1228                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1229     {
1230       GNUNET_break (0);
1231       GNUNET_CONTAINER_MDLL_remove (pred,
1232                                     pred->pred_head,
1233                                     pred->pred_tail,
1234                                     t);
1235       GNUNET_free (t);
1236       return GNUNET_OK;
1237     }
1238     GNUNET_CONTAINER_MDLL_insert (succ,
1239                                   succ->succ_head,
1240                                   succ->succ_tail,
1241                                   t);
1242     env = GNUNET_MQ_msg (rwm,
1243                          GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
1244     rwm->hops_taken = htons (1 + ntohs (m->hops_taken));
1245     rwm->layer = m->layer;
1246     rwm->trail_id = t->succ_id;
1247     GNUNET_MQ_send (succ->mq,
1248                     env);
1249   }
1250   return GNUNET_OK;
1251 }
1252
1253
1254 /**
1255  * Handle a `struct RandomWalkResponseMessage` from a GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE
1256  * message.
1257  *
1258  * @param cls closure (NULL)
1259  * @param peer sender identity
1260  * @param message the setup response message
1261  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1262  */
1263 static int
1264 handle_dht_p2p_random_walk_response (void *cls,
1265                                      const struct GNUNET_PeerIdentity *peer,
1266                                      const struct GNUNET_MessageHeader *message)
1267 {
1268   const struct RandomWalkResponseMessage *rwrm;
1269
1270   rwrm = (const struct RandomWalkResponseMessage *) message;
1271   // 1) lookup trail => find Finger entry => fill in 'destination' and mark valid, move to end of sorted array,
1272   //mark unsorted, update links from 'trails'
1273   /*
1274    * Steps :
1275    *  1 check if we are the correct layer
1276    *  1.a if true : add the returned value (finger) in the db structure
1277    *  1.b if true : do nothing
1278    */
1279   /* FIXME: add the value in db structure 1.a */
1280
1281   return GNUNET_OK;
1282 }
1283
1284
1285 /**
1286  * Handle a `struct TrailDestroyMessage`.
1287  *
1288  * @param cls closure (NULL)
1289  * @param peer sender identity
1290  * @param message the finger destroy message
1291  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1292  */
1293 static int
1294 handle_dht_p2p_trail_destroy (void *cls,
1295                              const struct GNUNET_PeerIdentity *peer,
1296                              const struct GNUNET_MessageHeader *message)
1297 {
1298   const struct TrailDestroyMessage *tdm;
1299   struct Trail *trail;
1300
1301   tdm = (const struct TrailDestroyMessage *) message;
1302   trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
1303                                              &tdm->trail_id);
1304   delete_trail (trail,
1305                 ( (NULL != trail->succ) &&
1306                   (0 == memcmp (peer,
1307                                 &trail->succ->id,
1308                                 sizeof (struct GNUNET_PeerIdentity))) ),
1309                 ( (NULL != trail->pred) &&
1310                   (0 == memcmp (peer,
1311                                 &trail->pred->id,
1312                                 sizeof (struct GNUNET_PeerIdentity))) ));
1313   return GNUNET_OK;
1314 }
1315
1316
1317 /**
1318  * Handle a `struct FindSuccessorMessage` from a #GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND
1319  * message.
1320  *
1321  * @param cls closure (NULL)
1322  * @param trail_id path to the originator
1323  * @param message the finger setup message
1324  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1325  */
1326 static int
1327 handle_dht_p2p_successor_find (void *cls,
1328                                const struct GNUNET_HashCode *trail_id,
1329                                const struct GNUNET_MessageHeader *message)
1330 {
1331   const struct FindSuccessorMessage *fsm;
1332
1333   fsm = (const struct FindSuccessorMessage *) message;
1334   // locate trail (for sending reply), if not exists, fail nicely.
1335   // otherwise, go to datacache and return 'top k' elements closest to 'key'
1336   // as "PUT" messages via the trail (need to extend DB API!)
1337 #if 0
1338   GDS_DATACACHE_get_successors (trail_id,
1339                                 key);
1340 #endif
1341   return GNUNET_OK;
1342 }
1343
1344
1345 /**
1346  * Handle a `struct PeerGetMessage`.
1347  *
1348  * @param cls closure (NULL)
1349  * @param trail_id path to the originator
1350  * @param message the peer get message
1351  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1352  */
1353 static int
1354 handle_dht_p2p_peer_get (void *cls,
1355                          const struct GNUNET_HashCode *trail_id,
1356                          const struct GNUNET_MessageHeader *message)
1357 {
1358   const struct PeerGetMessage *pgm;
1359
1360   // FIXME: note: never called like this, message embedded with trail route!
1361   pgm = (const struct PeerGetMessage *) message;
1362   // -> lookup in datacache (figure out way to remember trail!)
1363      /*
1364     * steps :
1365     *   1 extract the result
1366     *   2 save the peer
1367     *   3 send it using the good trail
1368     *
1369     * What do i do when i don't have the key/value?
1370     */
1371
1372   return GNUNET_OK;
1373 }
1374
1375
1376 /**
1377  * Handle a `struct PeerGetResultMessage`.
1378  *
1379  * @param cls closure (NULL)
1380  * @param trail_id path to the originator
1381  * @param message the peer get result message
1382  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1383  */
1384 static int
1385 handle_dht_p2p_peer_get_result (void *cls,
1386                                 const struct GNUNET_HashCode *trail_id,
1387                                 const struct GNUNET_MessageHeader *message)
1388 {
1389   const struct PeerGetResultMessage *pgrm;
1390
1391   pgrm = (const struct PeerGetResultMessage *) message;
1392   // pretty much: parse, & pass to client (there is some call for that...)
1393
1394 #if 0
1395   GDS_CLIENTS_process_get (options,
1396                            type,
1397                            0, 0,
1398                            path_length, path,
1399                            key);
1400   (void) GDS_DATACACHE_handle_get (trail_id,
1401                                    key,
1402                                    type,
1403                                    xquery,
1404                                    xquery_size,
1405                                    &reply_bf,
1406                                    reply_bf_mutator);
1407 #endif
1408   return GNUNET_OK;
1409 }
1410
1411
1412 /**
1413  * Handle a `struct PeerPutMessage`.
1414  *
1415  * @param cls closure (NULL)
1416  * @param trail_id path to the originator
1417  * @param message the peer put message
1418  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1419  */
1420 static int
1421 handle_dht_p2p_peer_put (void *cls,
1422                          const struct GNUNET_HashCode *trail_id,
1423                          const struct GNUNET_MessageHeader *message)
1424 {
1425   const struct PeerGetResultMessage *pgrm;
1426
1427   pgrm = (const struct PeerGetResultMessage *) message;
1428   // parse & store in datacache, this is in response to us asking for successors.
1429   /*
1430    * steps :
1431    * 1 check the size of the message
1432    * 2 use the API to add the value in the "database". Check on the xdht file, how to do it.
1433    * 3 Did i a have to return a notification or did i have to return GNUNET_[OK|SYSERR]?
1434    */
1435 #if 0
1436   GDS_DATACACHE_handle_put (expiration_time,
1437                             key,
1438                             path_length, path,
1439                             block_type,
1440                             data_size,
1441                             data);
1442   GDS_CLIENTS_process_put (options,
1443                            block_type,
1444                            0, 0,
1445                            path_length, path,
1446                            expiration_time,
1447                            key,
1448                            data,
1449                            data_size);
1450 #endif
1451   return GNUNET_OK;
1452 }
1453
1454
1455
1456
1457 /**
1458  * Handler for a message we received along some trail.
1459  *
1460  * @param cls closure
1461  * @param trail_id trail identifier
1462  * @param message the message we got
1463  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1464  */
1465 typedef int
1466 (*TrailHandlerCallback)(void *cls,
1467                         const struct GNUNET_HashCode *trail_id,
1468                         const struct GNUNET_MessageHeader *message);
1469
1470
1471 /**
1472  * Definition of a handler for a message received along some trail.
1473  */
1474 struct TrailHandler
1475 {
1476   /**
1477    * NULL for end-of-list.
1478    */
1479   TrailHandlerCallback callback;
1480
1481   /**
1482    * Closure for @e callback.
1483    */
1484   void *cls;
1485
1486   /**
1487    * Message type this handler addresses.
1488    */
1489   uint16_t message_type;
1490
1491   /**
1492    * Use 0 for variable-size.
1493    */
1494   uint16_t message_size;
1495 };
1496
1497
1498 /**
1499  * Handle a `struct TrailRouteMessage`.
1500  *
1501  * @param cls closure (NULL)
1502  * @param peer sender identity
1503  * @param message the finger destroy message
1504  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1505  */
1506 static int
1507 handle_dht_p2p_trail_route (void *cls,
1508                             const struct GNUNET_PeerIdentity *peer,
1509                             const struct GNUNET_MessageHeader *message)
1510 {
1511   static const struct TrailHandler handlers[] = {
1512     { &handle_dht_p2p_successor_find, NULL,
1513       GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND,
1514       sizeof (struct FindSuccessorMessage) },
1515     { &handle_dht_p2p_peer_get, NULL,
1516       GNUNET_MESSAGE_TYPE_WDHT_GET,
1517       sizeof (struct FindSuccessorMessage) },
1518     { &handle_dht_p2p_peer_get_result, NULL,
1519       GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT,
1520       0 },
1521     { &handle_dht_p2p_peer_put, NULL,
1522       GNUNET_MESSAGE_TYPE_WDHT_PUT,
1523       0 },
1524     { NULL, NULL, 0, 0 }
1525   };
1526   unsigned int i;
1527   const struct TrailRouteMessage *trm;
1528   const struct GNUNET_PeerIdentity *path;
1529   uint16_t path_length;
1530   const struct GNUNET_MessageHeader *payload;
1531   const struct TrailHandler *th;
1532   struct Trail *trail;
1533   size_t msize;
1534
1535   /* Parse and check message is well-formed */
1536   msize = ntohs (message->size);
1537   if (msize < sizeof (struct TrailRouteMessage))
1538   {
1539     GNUNET_break_op (0);
1540     return GNUNET_YES;
1541   }
1542   trm = (const struct TrailRouteMessage *) message;
1543   path_length = ntohs (trm->path_length);
1544   if (msize < sizeof (struct TrailRouteMessage) +
1545       path_length * sizeof (struct GNUNET_PeerIdentity) +
1546       sizeof (struct GNUNET_MessageHeader) )
1547   {
1548     GNUNET_break_op (0);
1549     return GNUNET_YES;
1550   }
1551   path = (const struct GNUNET_PeerIdentity *) &trm[1];
1552   payload = (const struct GNUNET_MessageHeader *) &path[path_length];
1553   if (msize != (ntohs (payload->size) +
1554                 sizeof (struct TrailRouteMessage) +
1555                 path_length * sizeof (struct GNUNET_PeerIdentity)))
1556   {
1557     GNUNET_break_op (0);
1558     return GNUNET_YES;
1559   }
1560
1561   /* Is this message for us? */
1562   trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
1563                                              &trm->trail_id);
1564   if ( (NULL != trail->pred) &&
1565        (0 == memcmp (peer,
1566                      &trail->pred->id,
1567                      sizeof (struct GNUNET_PeerIdentity))) )
1568   {
1569     /* forward to 'successor' */
1570     if (NULL != trail->succ)
1571     {
1572       forward_message_on_trail (trail->succ,
1573                                 &trail->succ_id,
1574                                 ntohs (trm->record_path),
1575                                 peer,
1576                                 path,
1577                                 path_length,
1578                                 payload);
1579       return GNUNET_OK;
1580     }
1581   }
1582   else
1583   {
1584     /* forward to 'predecessor' */
1585     GNUNET_break_op ( (NULL != trail->succ) &&
1586                       (0 == memcmp (peer,
1587                                     &trail->succ->id,
1588                                     sizeof (struct GNUNET_PeerIdentity))) );
1589     if (NULL != trail->pred)
1590     {
1591       forward_message_on_trail (trail->pred,
1592                                 &trail->pred_id,
1593                                 ntohs (trm->record_path),
1594                                 peer,
1595                                 path,
1596                                 path_length,
1597                                 payload);
1598       return GNUNET_OK;
1599     }
1600   }
1601
1602   /* Message is for us, dispatch to handler */
1603   th = NULL;
1604   for (i=0; NULL != handlers[i].callback; i++)
1605   {
1606     th = &handlers[i];
1607     if (ntohs (payload->type) == th->message_type)
1608     {
1609       if ( (0 == th->message_size) ||
1610            (ntohs (payload->size) == th->message_size) )
1611         th->callback (th->cls,
1612                       &trm->trail_id,
1613                       payload);
1614       else
1615         GNUNET_break_op (0);
1616       break;
1617     }
1618   }
1619   GNUNET_break_op (NULL != th);
1620   return GNUNET_OK;
1621 }
1622
1623
1624 /**
1625  * Initialize neighbours subsystem.
1626  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
1627  */
1628 int
1629 GDS_NEIGHBOURS_init (void)
1630 {
1631   static const struct GNUNET_CORE_MessageHandler core_handlers[] = {
1632     { &handle_dht_p2p_random_walk,
1633       GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK,
1634       sizeof (struct RandomWalkMessage) },
1635     { &handle_dht_p2p_random_walk_response,
1636       GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE,
1637       sizeof (struct RandomWalkResponseMessage) },
1638     { &handle_dht_p2p_trail_destroy,
1639       GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY,
1640       sizeof (struct TrailDestroyMessage) },
1641     { &handle_dht_p2p_trail_route,
1642       GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE,
1643       0},
1644     {NULL, 0, 0}
1645   };
1646
1647   core_api =
1648     GNUNET_CORE_connect (GDS_cfg, NULL,
1649                          &core_init,
1650                          &handle_core_connect,
1651                          &handle_core_disconnect,
1652                          NULL, GNUNET_NO,
1653                          NULL, GNUNET_NO,
1654                          core_handlers);
1655
1656   if (NULL == core_api)
1657     return GNUNET_SYSERR;
1658   friends_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
1659   trail_map = GNUNET_CONTAINER_multihashmap_create (1024, GNUNET_YES);
1660   trail_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
1661   return GNUNET_OK;
1662 }
1663
1664
1665 /**
1666  * Shutdown neighbours subsystem.
1667  */
1668 void
1669 GDS_NEIGHBOURS_done (void)
1670 {
1671   if (NULL == core_api)
1672     return;
1673   GNUNET_CORE_disconnect (core_api);
1674   core_api = NULL;
1675   GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friends_peermap));
1676   GNUNET_CONTAINER_multipeermap_destroy (friends_peermap);
1677   friends_peermap = NULL;
1678   GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (trail_map));
1679   GNUNET_CONTAINER_multihashmap_destroy (trail_map);
1680   trail_map = NULL;
1681   GNUNET_CONTAINER_heap_destroy (trail_heap);
1682   trail_heap = NULL;
1683   if (NULL != trail_timeout_task)
1684   {
1685     GNUNET_SCHEDULER_cancel (trail_timeout_task);
1686     trail_timeout_task = NULL;
1687   }
1688 }
1689
1690
1691 /**
1692  * Get my identity
1693  *
1694  * @return my identity
1695  */
1696 struct GNUNET_PeerIdentity
1697 GDS_NEIGHBOURS_get_my_id (void)
1698 {
1699   return my_identity;
1700 }
1701
1702 /* end of gnunet-service-wdht_neighbours.c */