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