src/dht/gnunet-service-wdht_neighbours.c

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