src/dv/gnunet-service-dv.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2009 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 2, 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 /**
  22  * @file dv/gnunet-service-dv.c
  23  * @brief the distance vector service, primarily handles gossip of nearby
  24  * peers and sending/receiving DV messages from core and decapsulating
  25  * them
  26  *
  27  * @author Christian Grothoff
  28  * @author Nathan Evans
  29  *
  30  */
  31 #include "platform.h"
  32 #include "gnunet_client_lib.h"
  33 #include "gnunet_getopt_lib.h"
  34 #include "gnunet_os_lib.h"
  35 #include "gnunet_protocols.h"
  36 #include "gnunet_service_lib.h"
  37 #include "gnunet_core_service.h"
  38 #include "gnunet_signal_lib.h"
  39 #include "gnunet_util_lib.h"
  40 #include "dv.h"
  41
  42 /**
  43  * DV Service Context stuff goes here...
  44  */
  45
  46 /**
  47  * Handle to the core service api.
  48  */
  49 static struct GNUNET_CORE_Handle *coreAPI;
  50
  51 /**
  52  * The identity of our peer.
  53  */
  54 static struct GNUNET_PeerIdentity my_identity;
  55
  56 /**
  57  * The configuration for this service.
  58  */
  59 static const struct GNUNET_CONFIGURATION_Handle *cfg;
  60
  61 /**
  62  * The scheduler for this service.
  63  */
  64 static struct GNUNET_SCHEDULER_Handle *sched;
  65
  66 /**
  67  * How often do we check about sending out more peer information (if
  68  * we are connected to no peers previously).
  69  */
  70 #define GNUNET_DV_DEFAULT_SEND_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MILLISECONDS, 500))
  71
  72 /**
  73  * How long do we wait at most between sending out information?
  74  */
  75 #define GNUNET_DV_MAX_SEND_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 5))
  76
  77 /**
  78  * How long can we have not heard from a peer and
  79  * still have it in our tables?
  80  */
  81 #define GNUNET_DV_PEER_EXPIRATION_TIME GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 1000))
  82
  83 /**
  84  * Priority for gossip.
  85  */
  86 #define GNUNET_DV_DHT_GOSSIP_PRIORITY (GNUNET_EXTREME_PRIORITY / 10)
  87
  88 /**
  89  * How often should we check if expiration time has elapsed for
  90  * some peer?
  91  */
  92 #define GNUNET_DV_MAINTAIN_FREQUENCY GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 5))
  93
  94 /**
  95  * How long to allow a message to be delayed?
  96  */
  97 #define DV_DELAY GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 5))
  98
  99 /**
 100  * Priority to use for DV data messages.
 101  */
 102 #define DV_PRIORITY 0
 103
 104 /**
 105  * The client, should be the DV plugin connected to us.  Hopefully
 106  * this client will never change, although if the plugin dies
 107  * and returns for some reason it may happen.
 108  */
 109 static struct GNUNET_SERVER_Client * client_handle;
 110
 111 /**
 112  * Task to run when we shut down, cleaning up all our trash
 113  */
 114 GNUNET_SCHEDULER_TaskIdentifier cleanup_task;
 115
 116 /**
 117  * Task to run to gossip about peers.  Will reschedule itself forever until shutdown!
 118  */
 119 GNUNET_SCHEDULER_TaskIdentifier gossip_task;
 120
 121 /**
 122  * Struct where neighbor information is stored.
 123  */
 124 struct DistantNeighbor *referees;
 125
 126 static struct GNUNET_TIME_Relative client_transmit_timeout;
 127
 128 static struct GNUNET_TIME_Relative default_dv_delay;
 129
 130 static size_t default_dv_priority = 0;
 131
 132
 133 /**
 134  * Pending message struct, also a test to see if these can
 135  * safely ONLY be freed by callback.
 136  */
 137 struct PendingMessage
 138 {
 139   /**
 140    * Copy of message to be sent
 141    */
 142   struct GNUNET_MessageHeader *msg;
 143
 144   /**
 145    * Size of message to be sent
 146    */
 147   size_t msg_size;
 148
 149   /**
 150    * Transmit handle, for cancellation if necessary.
 151    */
 152   struct GNUNET_CORE_TransmitHandle *transmit_handle;
 153
 154 };
 155
 156
 157 /**
 158  * Context created whenever a direct peer connects to us,
 159  * used to gossip other peers to it.
 160  */
 161 struct NeighborSendContext
 162 {
 163   /**
 164    * The peer we will gossip to.
 165    */
 166   struct DirectNeighbor *toNeighbor;
 167
 168   /**
 169    * The timeout for this task.
 170    */
 171   struct GNUNET_TIME_Relative timeout;
 172
 173   /**
 174    * The task associated with this context.
 175    */
 176   GNUNET_SCHEDULER_TaskIdentifier task;
 177
 178 };
 179
 180
 181 /**
 182  * Struct to hold information for updating existing neighbors
 183  */
 184 struct NeighborUpdateInfo
 185 {
 186   /**
 187    * Cost
 188    */
 189   unsigned int cost;
 190
 191   /**
 192    * The existing neighbor
 193    */
 194   struct DistantNeighbor *neighbor;
 195
 196   /**
 197    * The referrer of the possibly existing peer
 198    */
 199   struct DirectNeighbor *referrer;
 200
 201   /**
 202    * The time we heard about this peer
 203    */
 204   struct GNUNET_TIME_Absolute now;
 205 };
 206
 207 /**
 208  * Struct where actual neighbor information is stored,
 209  * referenced by min_heap and max_heap.  Freeing dealt
 210  * with when items removed from hashmap.
 211  */
 212 struct DirectNeighbor
 213 {
 214   /**
 215    * Identity of neighbor.
 216    */
 217   struct GNUNET_PeerIdentity identity;
 218
 219   /**
 220    * Head of DLL of nodes that this direct neighbor referred to us.
 221    */
 222   struct DistantNeighbor *referee_head;
 223
 224   /**
 225    * Tail of DLL of nodes that this direct neighbor referred to us.
 226    */
 227   struct DistantNeighbor *referee_tail;
 228
 229   /**
 230    * The sending context for gossiping peers to this neighbor.
 231    */
 232   struct NeighborSendContext *send_context;
 233
 234   /**
 235    * Is this one of the direct neighbors that we are "hiding"
 236    * from DV?
 237    */
 238   int hidden;
 239 };
 240
 241
 242 /**
 243  * Struct where actual neighbor information is stored,
 244  * referenced by min_heap and max_heap.  Freeing dealt
 245  * with when items removed from hashmap.
 246  */
 247 struct DistantNeighbor
 248 {
 249   /**
 250    * We keep distant neighbor's of the same referrer in a DLL.
 251    */
 252   struct DistantNeighbor *next;
 253
 254   /**
 255    * We keep distant neighbor's of the same referrer in a DLL.
 256    */
 257   struct DistantNeighbor *prev;
 258
 259   /**
 260    * Node in min heap
 261    */
 262   struct GNUNET_CONTAINER_HeapNode *min_loc;
 263
 264   /**
 265    * Node in max heap
 266    */
 267   struct GNUNET_CONTAINER_HeapNode *max_loc;
 268
 269   /**
 270    * Identity of referrer (next hop towards 'neighbor').
 271    */
 272   struct DirectNeighbor *referrer;
 273
 274   /**
 275    * Identity of neighbor.
 276    */
 277   struct GNUNET_PeerIdentity identity;
 278
 279   /**
 280    * Last time we received routing information from this peer
 281    */
 282   struct GNUNET_TIME_Absolute last_activity;
 283
 284   /**
 285    * Cost to neighbor, used for actual distance vector computations
 286    */
 287   unsigned int cost;
 288
 289   /**
 290    * Random identifier *we* use for this peer, to be used as shortcut
 291    * instead of sending full peer id for each message
 292    */
 293   unsigned int our_id;
 294
 295   /**
 296    * Random identifier the *referrer* uses for this peer.
 297    */
 298   unsigned int referrer_id;
 299
 300   /**
 301    * Is this one of the direct neighbors that we are "hiding"
 302    * from DV?
 303    */
 304   int hidden;
 305 };
 306
 307
 308 /**
 309  * Global construct
 310  */
 311 struct GNUNET_DV_Context
 312 {
 313   /**
 314    * Map of PeerIdentifiers to 'struct GNUNET_dv_neighbor*'s for all
 315    * directly connected peers.
 316    */
 317   struct GNUNET_CONTAINER_MultiHashMap *direct_neighbors;
 318
 319   /**
 320    * Map of PeerIdentifiers to 'struct GNUNET_dv_neighbor*'s for
 321    * peers connected via DV (extended neighborhood).  Does ALSO
 322    * include any peers that are in 'direct_neighbors'; for those
 323    * peers, the cost will be zero and the referrer all zeros.
 324    */
 325   struct GNUNET_CONTAINER_MultiHashMap *extended_neighbors;
 326
 327   /**
 328    * We use the min heap (min refers to cost) to prefer
 329    * gossipping about peers with small costs.
 330    */
 331   struct GNUNET_CONTAINER_Heap *neighbor_min_heap;
 332
 333   /**
 334    * We use the max heap (max refers to cost) for general
 335    * iterations over all peers and to remove the most costly
 336    * connection if we have too many.
 337    */
 338   struct GNUNET_CONTAINER_Heap *neighbor_max_heap;
 339
 340   unsigned long long fisheye_depth;
 341
 342   unsigned long long max_table_size;
 343
 344   unsigned int neighbor_id_loc;
 345
 346   int closing;
 347
 348 };
 349
 350 static struct GNUNET_DV_Context ctx;
 351
 352 struct FindDestinationContext
 353 {
 354   unsigned int tid;
 355   struct DistantNeighbor *dest;
 356 };
 357
 358
 359 /**
 360  * We've been given a target ID based on the random numbers that
 361  * we assigned to our DV-neighborhood.  Find the entry for the
 362  * respective neighbor.
 363  */
 364 static int
 365 find_destination (void *cls,
 366                   struct GNUNET_CONTAINER_HeapNode *node,
 367                   void *element, GNUNET_CONTAINER_HeapCostType cost)
 368 {
 369   struct FindDestinationContext *fdc = cls;
 370   struct DistantNeighbor *dn = element;
 371
 372   if (fdc->tid != dn->our_id)
 373     return GNUNET_YES;
 374   fdc->dest = dn;
 375   return GNUNET_NO;
 376 }
 377
 378 /**
 379  * Function called to notify a client about the socket
 380  * begin ready to queue more data.  "buf" will be
 381  * NULL and "size" zero if the socket was closed for
 382  * writing in the meantime.
 383  *
 384  * @param cls closure
 385  * @param size number of bytes available in buf
 386  * @param buf where the callee should write the message
 387  * @return number of bytes written to buf
 388  */
 389 size_t transmit_to_plugin (void *cls,
 390                size_t size, void *buf)
 391 {
 392   struct GNUNET_DV_MessageReceived *msg = cls;
 393   int msize;
 394
 395   if (buf == NULL)
 396     return 0;
 397
 398   msize = ntohs(msg->header.size);
 399   GNUNET_assert(size >= msize);
 400
 401
 402   memcpy(buf, msg, msize);
 403   GNUNET_free(msg);
 404   return msize;
 405 }
 406
 407
 408 void send_to_plugin(const struct GNUNET_PeerIdentity * sender, const struct GNUNET_MessageHeader *message, size_t message_size, struct DistantNeighbor *distant_neighbor)
 409 {
 410   struct GNUNET_DV_MessageReceived *received_msg;
 411   int size;
 412
 413   size = sizeof(struct GNUNET_DV_MessageReceived) + sizeof(struct GNUNET_PeerIdentity) + message_size;
 414   received_msg = GNUNET_malloc(size);
 415   received_msg->header.size = htons(size);
 416   received_msg->header.type = htons(GNUNET_MESSAGE_TYPE_TRANSPORT_DV_RECEIVE);
 417   received_msg->sender_address_len = sizeof(struct GNUNET_PeerIdentity);
 418   received_msg->distance = htonl(distant_neighbor->cost);
 419   received_msg->msg_len = htons(message_size);
 420   /* Set the sender in this message to be the original sender! */
 421   memcpy(&received_msg->sender, &distant_neighbor->identity, sizeof(struct GNUNET_PeerIdentity));
 422   /* Copy the intermediate sender to the end of the message, this is how the transport identifies this peer */
 423   memcpy(&received_msg[1], sender, sizeof(struct GNUNET_PeerIdentity));
 424   /* Copy the actual message after the sender */
 425   memcpy(&received_msg[1 + sizeof(struct GNUNET_PeerIdentity)], message, message_size);
 426
 427   /* FIXME: Send to the client please */
 428   GNUNET_SERVER_notify_transmit_ready (client_handle,
 429                                        size, client_transmit_timeout,
 430                                        &transmit_to_plugin, &received_msg);
 431
 432 }
 433
 434
 435 /**
 436  * Function called to notify a client about the socket
 437  * begin ready to queue more data.  "buf" will be
 438  * NULL and "size" zero if the socket was closed for
 439  * writing in the meantime.
 440  *
 441  * @param cls closure
 442  * @param size number of bytes available in buf
 443  * @param buf where the callee should write the message
 444  * @return number of bytes written to buf
 445  */
 446 size_t core_transmit_notify (void *cls,
 447                              size_t size, void *buf)
 448 {
 449   struct PendingMessage *pending_message = cls;
 450   size_t ssize;
 451
 452   if (buf == NULL)
 453     {
 454       /* FIXME: error handling: try again? free pending_message? */
 455       return 0;
 456     }
 457   ssize = pending_message->msg_size;
 458   GNUNET_assert(size >= ssize);
 459   memcpy(buf, pending_message->msg, ssize);
 460   GNUNET_free(pending_message->msg);
 461   GNUNET_free(pending_message);
 462   return ssize;
 463 }
 464
 465 /**
 466  * Send a DV data message via DV.
 467  *
 468  * @param recipient the ultimate recipient of this message
 469  * @param the original sender of the message
 470  * @param message the packed message
 471  * @param importance what priority to send this message with
 472  * @param timeout how long to possibly delay sending this message
 473  */
 474 static int
 475 send_message (const struct GNUNET_PeerIdentity * recipient,
 476               const struct GNUNET_PeerIdentity * sender,
 477               const struct GNUNET_MessageHeader * message,
 478               unsigned int importance, struct GNUNET_TIME_Relative timeout)
 479 {
 480   p2p_dv_MESSAGE_Data *toSend;
 481   unsigned int msg_size;
 482   unsigned int cost;
 483   unsigned int recipient_id;
 484   unsigned int sender_id;
 485   struct DistantNeighbor *target;
 486   struct DistantNeighbor *source;
 487   struct PendingMessage *pending_message;
 488
 489   msg_size = ntohs (message->size) + sizeof (p2p_dv_MESSAGE_Data);
 490
 491   target = GNUNET_CONTAINER_multihashmap_get (ctx.extended_neighbors,
 492                                               &recipient->hashPubKey);
 493   if (target == NULL)
 494     {
 495       /* target unknown to us, drop! */
 496       return GNUNET_SYSERR;
 497     }
 498   recipient_id = target->referrer_id;
 499
 500   source = GNUNET_CONTAINER_multihashmap_get (ctx.extended_neighbors,
 501                                       &sender->hashPubKey);
 502   if (source == NULL)
 503     {
 504       if (0 != (memcmp (&my_identity,
 505                         sender, sizeof (struct GNUNET_PeerIdentity))))
 506         {
 507           /* sender unknown to us, drop! */
 508           return GNUNET_SYSERR;
 509         }
 510       sender_id = 0;            /* 0 == us */
 511     }
 512   else
 513     {
 514       /* find out the number that we use when we gossip about
 515          the sender */
 516       sender_id = source->our_id;
 517     }
 518
 519   cost = target->cost;
 520   pending_message = GNUNET_malloc(sizeof(struct PendingMessage));
 521   pending_message->msg = GNUNET_malloc (msg_size);
 522   toSend = (p2p_dv_MESSAGE_Data *)pending_message->msg;
 523   toSend->header.size = htons (msg_size);
 524   toSend->header.type = htons (GNUNET_MESSAGE_TYPE_DV_DATA);
 525   toSend->sender = htonl (sender_id);
 526   toSend->recipient = htonl (recipient_id);
 527   memcpy (&toSend[1], message, ntohs (message->size));
 528   pending_message->msg_size = msg_size;
 529
 530   pending_message->transmit_handle = GNUNET_CORE_notify_transmit_ready(coreAPI, importance, timeout, &target->referrer->identity, msg_size, &core_transmit_notify, pending_message);
 531   if (NULL == pending_message->transmit_handle)
 532     {
 533       GNUNET_free (pending_message->msg);
 534       GNUNET_free (pending_message);
 535       return GNUNET_SYSERR;
 536     }
 537
 538   /*coreAPI->ciphertext_send (&target->referrer->identity,
 539                             &toSend->header, importance, maxdelay);*/
 540   return (int) cost;
 541 }
 542
 543
 544 /**
 545  * Core handler for dv data messages.  Whatever this message
 546  * contains all we really have to do is rip it out of its
 547  * DV layering and give it to our pal the DV plugin to report
 548  * in with.
 549  *
 550  * @param cls closure
 551  * @param peer peer which sent the message (immediate sender)
 552  * @param message the message
 553  * @param latency the latency of the connection we received the message from
 554  * @param distance the distance to the immediate peer
 555  */
 556 static int handle_dv_data_message (void *cls,
 557                              const struct GNUNET_PeerIdentity * peer,
 558                              const struct GNUNET_MessageHeader * message,
 559                              struct GNUNET_TIME_Relative latency,
 560                              uint32_t distance)
 561 {
 562 #if DEBUG_DV
 563   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 564               "%s: Receives %s message!\n", "dv", "DV DATA");
 565 #endif
 566
 567   const p2p_dv_MESSAGE_Data *incoming = (const p2p_dv_MESSAGE_Data *) message;
 568   const struct GNUNET_MessageHeader *packed_message = (const struct GNUNET_MessageHeader *) &incoming[1];
 569   struct DirectNeighbor *dn;
 570   struct DistantNeighbor *pos;
 571   unsigned int sid;             /* Sender id */
 572   unsigned int tid;             /* Target id */
 573   struct GNUNET_PeerIdentity original_sender;
 574   struct GNUNET_PeerIdentity destination;
 575   struct FindDestinationContext fdc;
 576   int ret;
 577
 578   if ((ntohs (incoming->header.size) <
 579        sizeof (p2p_dv_MESSAGE_Data) + sizeof (struct GNUNET_MessageHeader))
 580       || (ntohs (incoming->header.size) !=
 581           (sizeof (p2p_dv_MESSAGE_Data) + ntohs (packed_message->size))))
 582     {
 583       return GNUNET_SYSERR;
 584     }
 585
 586   dn = GNUNET_CONTAINER_multihashmap_get (ctx.direct_neighbors,
 587                                   &peer->hashPubKey);
 588   if (dn == NULL)
 589     {
 590       return GNUNET_OK;
 591     }
 592   sid = ntohl (incoming->sender);
 593   pos = dn->referee_head;
 594   while ((NULL != pos) && (pos->referrer_id != sid))
 595     pos = pos->next;
 596   if (pos == NULL)
 597     {
 598       /* unknown sender */
 599       return GNUNET_OK;
 600     }
 601   original_sender = pos->identity;
 602   tid = ntohl (incoming->recipient);
 603   if (tid == 0)
 604     {
 605       /* 0 == us */
 606
 607       /* FIXME: Will we support wrapped messages being these types? Probably not, they should
 608        * be encrypted messages that need decrypting and junk like that.
 609        */
 610       GNUNET_break_op (ntohs (packed_message->type) != GNUNET_MESSAGE_TYPE_DV_GOSSIP);
 611       GNUNET_break_op (ntohs (packed_message->type) != GNUNET_MESSAGE_TYPE_DV_DATA);
 612       if ( (ntohs (packed_message->type) != GNUNET_MESSAGE_TYPE_DV_GOSSIP) &&
 613           (ntohs (packed_message->type) != GNUNET_MESSAGE_TYPE_DV_DATA) )
 614       {
 615         send_to_plugin(peer, packed_message, ntohs(packed_message->size), pos);
 616       }
 617
 618       return GNUNET_OK;
 619     }
 620
 621   /* FIXME: this is the *only* per-request operation we have in DV
 622      that is O(n) in relation to the number of connected peers; a
 623      hash-table lookup could easily solve this (minor performance
 624      issue) */
 625   fdc.tid = tid;
 626   fdc.dest = NULL;
 627   GNUNET_CONTAINER_heap_iterate (ctx.neighbor_max_heap,
 628                                  &find_destination, &fdc);
 629   if (fdc.dest == NULL)
 630     {
 631       return GNUNET_OK;
 632     }
 633   destination = fdc.dest->identity;
 634
 635   if (0 == memcmp (&destination, peer, sizeof (struct GNUNET_PeerIdentity)))
 636     {
 637       /* FIXME: create stat: routing loop-discard! */
 638       return GNUNET_OK;
 639     }
 640
 641   /* At this point we have a message, and we need to forward it on to the
 642    * next DV hop.
 643    */
 644   /* FIXME: Can't send message on, we have to behave.
 645    * We have to tell core we have a message for the next peer, and let
 646    * transport do transport selection on how to get this message to 'em */
 647   /*ret = send_message (&destination,
 648                       &original_sender,
 649                       packed_message, DV_PRIORITY, DV_DELAY);*/
 650   ret = send_message(&destination, &original_sender, packed_message, default_dv_priority, default_dv_delay);
 651
 652   if (ret != GNUNET_SYSERR)
 653     return GNUNET_OK;
 654   else
 655     return GNUNET_SYSERR;
 656 }
 657
 658
 659 /**
 660  * Thread which chooses a peer to gossip about and a peer to gossip
 661  * to, then constructs the message and sends it out.  Will run until
 662  * done_module_dv is called.
 663  */
 664 static void
 665 neighbor_send_task (void *cls,
 666                       const struct GNUNET_SCHEDULER_TaskContext *tc)
 667 {
 668   struct NeighborSendContext *send_context = cls;
 669 #if DEBUG_DV
 670   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 671               "%s: Entering neighbor_send_task...\n",
 672               GNUNET_i2s(&my_identity));
 673   char * encPeerAbout;
 674   char * encPeerTo;
 675 #endif
 676   struct DistantNeighbor *about;
 677   struct DirectNeighbor *to;
 678
 679   p2p_dv_MESSAGE_NeighborInfo *message;
 680   struct PendingMessage *pending_message;
 681
 682   if (tc->reason == GNUNET_SCHEDULER_REASON_SHUTDOWN)
 683   {
 684 #if DEBUG_DV
 685   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 686               "%s: Called with reason shutdown, shutting down!\n",
 687               GNUNET_i2s(&my_identity));
 688 #endif
 689     send_context->toNeighbor->send_context = NULL;
 690     GNUNET_free(send_context);
 691     return;
 692   }
 693
 694
 695   /* FIXME: this may become a problem, because the heap walk has only one internal "walker".  This means
 696    * that if two neighbor_send_tasks are operating in lockstep (which is quite possible, given default
 697    * values for all connected peers) there may be a serious bias as to which peers get gossiped about!
 698    * Probably the *best* way to fix would be to have an opaque pointer to the walk position passed as
 699    * part of the walk_get_next call.  Then the heap would have to keep a list of walks, or reset the walk
 700    * whenever a modification has been detected.  Yuck either way.  Perhaps we could iterate over the heap
 701    * once to get a list of peers to gossip about and gossip them over time... But then if one goes away
 702    * in the mean time that becomes nasty.  For now we'll just assume that the walking is done
 703    * asynchronously enough to avoid major problems (-;
 704    */
 705   about = GNUNET_CONTAINER_heap_walk_get_next (ctx.neighbor_min_heap);
 706   to = send_context->toNeighbor;
 707
 708   if ((about != NULL) && (to != about->referrer /* split horizon */ ) &&
 709 #if SUPPORT_HIDING
 710       (about->hidden == GNUNET_NO) &&
 711 #endif
 712       (to != NULL) &&
 713       (0 != memcmp (&about->identity,
 714                         &to->identity, sizeof (struct GNUNET_PeerIdentity))))
 715     {
 716 #if DEBUG_DV
 717       encPeerAbout = GNUNET_strdup(GNUNET_i2s(&about->identity));
 718       encPeerTo = GNUNET_strdup(GNUNET_i2s(&to->identity));
 719       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 720                   "%s: Sending info about peer %s to directly connected peer %s\n",
 721                   GNUNET_i2s(&my_identity),
 722                   encPeerAbout, encPeerTo);
 723       GNUNET_free(encPeerAbout);
 724       GNUNET_free(encPeerTo);
 725 #endif
 726       pending_message = GNUNET_malloc(sizeof(struct PendingMessage));
 727       pending_message->msg = GNUNET_malloc(sizeof(p2p_dv_MESSAGE_NeighborInfo));
 728       message = (p2p_dv_MESSAGE_NeighborInfo *)pending_message->msg;
 729       message->header.size = htons (sizeof (p2p_dv_MESSAGE_NeighborInfo));
 730       message->header.type = htons (GNUNET_MESSAGE_TYPE_DV_GOSSIP);
 731       message->cost = htonl (about->cost);
 732       message->neighbor_id = htonl (about->our_id);
 733       memcpy (&message->neighbor,
 734               &about->identity, sizeof (struct GNUNET_PeerIdentity));
 735
 736       pending_message->msg_size = sizeof(p2p_dv_MESSAGE_NeighborInfo);
 737       pending_message->transmit_handle = GNUNET_CORE_notify_transmit_ready(coreAPI, default_dv_priority, default_dv_delay, &to->identity, sizeof(p2p_dv_MESSAGE_NeighborInfo), &core_transmit_notify, pending_message);
 738
 739       if (NULL == pending_message->transmit_handle)
 740         {
 741           GNUNET_free (pending_message->msg);
 742           GNUNET_free (pending_message);
 743           return;
 744         }
 745       /*coreAPI->ciphertext_send (&to->identity, &message.header,
 746                                 GNUNET_DV_DHT_GOSSIP_PRIORITY,
 747                                 ctx.send_interval);*/
 748     }
 749
 750   GNUNET_SCHEDULER_add_delayed(sched, send_context->timeout, &neighbor_send_task, send_context);
 751   return;
 752 }
 753
 754
 755 /**
 756  * Service server's handler for message send requests (which come
 757  * bubbling up to us through the DV plugin).
 758  *
 759  * @param cls closure
 760  * @param client identification of the client
 761  * @param message the actual message
 762  */
 763 void send_dv_message (void *cls,
 764                       struct GNUNET_SERVER_Client * client,
 765                       const struct GNUNET_MessageHeader * message)
 766 {
 767 #if DEBUG_DV
 768   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 769               "%s: Receives %s message!\n", "dv", "SEND");
 770 #endif
 771   if (client_handle == NULL)
 772   {
 773     client_handle = client;
 774 #if DEBUG_DV
 775   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 776               "%s: Setting initial client handle!\n", "dv");
 777 #endif
 778   }
 779   else if (client_handle != client)
 780   {
 781     client_handle = client;
 782     /* What should we do in this case, assert fail or just log the warning? */
 783     GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 784                 "%s: Setting client handle (was a different client!)!\n", "dv");
 785   }
 786
 787   GNUNET_SERVER_receive_done(client, GNUNET_OK);
 788 }
 789
 790 static int handle_dv_gossip_message (void *cls,
 791                                      const struct GNUNET_PeerIdentity *peer,
 792                                      const struct GNUNET_MessageHeader *message,
 793                                      struct GNUNET_TIME_Relative latency,
 794                                      uint32_t distance);
 795
 796 /**
 797  * List of handlers for the messages understood by this
 798  * service.
 799  *
 800  * Hmm... will we need to register some handlers with core and
 801  * some handlers with our server here?  Because core should be
 802  * getting the incoming DV messages (from whichever lower level
 803  * transport) and then our server should be getting messages
 804  * from the dv_plugin, right?
 805  */
 806 static struct GNUNET_CORE_MessageHandler core_handlers[] = {
 807   {&handle_dv_data_message, GNUNET_MESSAGE_TYPE_DV_DATA, 0},
 808   {&handle_dv_gossip_message, GNUNET_MESSAGE_TYPE_DV_GOSSIP, 0},
 809   {NULL, 0, 0}
 810 };
 811
 812
 813 static struct GNUNET_SERVER_MessageHandler plugin_handlers[] = {
 814   {&send_dv_message, NULL, GNUNET_MESSAGE_TYPE_TRANSPORT_DV_SEND, 0},
 815   {NULL, NULL, 0, 0}
 816 };
 817
 818
 819 /**
 820  * Task run during shutdown.
 821  *
 822  * @param cls unused
 823  * @param tc unused
 824  */
 825 static void
 826 shutdown_task (void *cls,
 827                const struct GNUNET_SCHEDULER_TaskContext *tc)
 828 {
 829   GNUNET_CORE_disconnect (coreAPI);
 830 }
 831
 832 /**
 833  * To be called on core init/fail.
 834  */
 835 void core_init (void *cls,
 836                 struct GNUNET_CORE_Handle * server,
 837                 const struct GNUNET_PeerIdentity *identity,
 838                 const struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded * publicKey)
 839 {
 840
 841   if (server == NULL)
 842     {
 843       GNUNET_SCHEDULER_cancel(sched, cleanup_task);
 844       GNUNET_SCHEDULER_add_now(sched, &shutdown_task, NULL);
 845       return;
 846     }
 847 #if DEBUG_DV
 848   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 849               "%s: Core connection initialized, I am peer: %s\n", "dv", GNUNET_i2s(identity));
 850 #endif
 851   memcpy(&my_identity, identity, sizeof(struct GNUNET_PeerIdentity));
 852   coreAPI = server;
 853 }
 854
 855
 856 /**
 857  * Iterator over hash map entries.
 858  *
 859  * @param cls closure
 860  * @param key current key code
 861  * @param value value in the hash map
 862  * @return GNUNET_YES if we should continue to
 863  *         iterate,
 864  *         GNUNET_NO if not.
 865  */
 866 static int update_matching_neighbors (void *cls,
 867                                       const GNUNET_HashCode * key,
 868                                       void *value)
 869 {
 870   struct NeighborUpdateInfo * update_info = cls;
 871   struct DistantNeighbor *distant_neighbor = value;
 872
 873   if (update_info->referrer == distant_neighbor->referrer) /* Direct neighbor matches, update it's info and return GNUNET_NO */
 874   {
 875     /* same referrer, cost change! */
 876     GNUNET_CONTAINER_heap_update_cost (ctx.neighbor_max_heap,
 877                                        update_info->neighbor->max_loc, update_info->cost);
 878     GNUNET_CONTAINER_heap_update_cost (ctx.neighbor_min_heap,
 879                                        update_info->neighbor->min_loc, update_info->cost);
 880     update_info->neighbor->last_activity = update_info->now;
 881     update_info->neighbor->cost = update_info->cost;
 882     return GNUNET_NO;
 883   }
 884
 885   return GNUNET_YES;
 886 }
 887
 888
 889 /**
 890  * Free a DistantNeighbor node, including removing it
 891  * from the referer's list.
 892  */
 893 static void
 894 distant_neighbor_free (struct DistantNeighbor *referee)
 895 {
 896   struct DirectNeighbor *referrer;
 897
 898   referrer = referee->referrer;
 899   if (referrer != NULL)
 900     {
 901       GNUNET_CONTAINER_DLL_remove (referrer->referee_head,
 902                          referrer->referee_tail, referee);
 903     }
 904   GNUNET_CONTAINER_heap_remove_node (ctx.neighbor_max_heap, referee->max_loc);
 905   GNUNET_CONTAINER_heap_remove_node (ctx.neighbor_min_heap, referee->min_loc);
 906   GNUNET_CONTAINER_multihashmap_remove_all (ctx.extended_neighbors,
 907                                     &referee->identity.hashPubKey);
 908   GNUNET_free (referee);
 909 }
 910
 911
 912 /**
 913  * Handles when a peer is either added due to being newly connected
 914  * or having been gossiped about, also called when the cost for a neighbor
 915  * needs to be updated.
 916  *
 917  * @param peer identity of the peer whose info is being added/updated
 918  * @param referrer_peer_id id to use when sending to 'peer'
 919  * @param referrer if this is a gossiped peer, who did we hear it from?
 920  * @param cost the cost of communicating with this peer via 'referrer'
 921  */
 922 static void
 923 addUpdateNeighbor (const struct GNUNET_PeerIdentity * peer,
 924                    unsigned int referrer_peer_id,
 925                    struct DirectNeighbor *referrer, unsigned int cost)
 926 {
 927   struct DistantNeighbor *neighbor;
 928   struct DistantNeighbor *max;
 929   struct GNUNET_TIME_Absolute now;
 930   struct NeighborUpdateInfo *neighbor_update;
 931   unsigned int our_id;
 932
 933   now = GNUNET_TIME_absolute_get ();
 934   our_id = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, RAND_MAX - 1) + 1;
 935
 936   neighbor = GNUNET_CONTAINER_multihashmap_get (ctx.extended_neighbors,
 937                                                 &peer->hashPubKey);
 938   neighbor_update = GNUNET_malloc(sizeof(struct NeighborUpdateInfo));
 939   neighbor_update->neighbor = neighbor;
 940   neighbor_update->cost = cost;
 941   neighbor_update->now = now;
 942   neighbor_update->referrer = referrer;
 943
 944   /* Either we do not know this peer, or we already do but via a different immediate peer */
 945   if ((neighbor == NULL) ||
 946       (GNUNET_CONTAINER_multihashmap_get_multiple(ctx.extended_neighbors,
 947                                                   &peer->hashPubKey,
 948                                                   &update_matching_neighbors,
 949                                                   neighbor_update) != GNUNET_SYSERR))
 950     {
 951       /* new neighbor! */
 952       if (cost > ctx.fisheye_depth)
 953         {
 954           /* too costly */
 955           GNUNET_free(neighbor_update);
 956           return;
 957         }
 958       if (ctx.max_table_size <=
 959           GNUNET_CONTAINER_multihashmap_size (ctx.extended_neighbors))
 960         {
 961           /* remove most expensive entry */
 962           max = GNUNET_CONTAINER_heap_peek (ctx.neighbor_max_heap);
 963           if (cost > max->cost)
 964             {
 965               /* new entry most expensive, don't create */
 966               GNUNET_free(neighbor_update);
 967               return;
 968             }
 969           if (max->cost > 0)
 970             {
 971               /* only free if this is not a direct connection;
 972                  we could theoretically have more direct
 973                  connections than DV entries allowed total! */
 974               distant_neighbor_free (max);
 975             }
 976         }
 977
 978       neighbor = GNUNET_malloc (sizeof (struct DistantNeighbor));
 979       GNUNET_CONTAINER_DLL_insert (referrer->referee_head,
 980                          referrer->referee_tail, neighbor);
 981       neighbor->max_loc = GNUNET_CONTAINER_heap_insert (ctx.neighbor_max_heap,
 982                                                         neighbor, cost);
 983       neighbor->min_loc = GNUNET_CONTAINER_heap_insert (ctx.neighbor_min_heap,
 984                                                         neighbor, cost);
 985       neighbor->referrer = referrer;
 986       memcpy (&neighbor->identity, peer, sizeof (struct GNUNET_PeerIdentity));
 987       neighbor->last_activity = now;
 988       neighbor->cost = cost;
 989       neighbor->referrer_id = referrer_peer_id;
 990       neighbor->our_id = our_id;
 991       neighbor->hidden =
 992         (cost == 0) ? (GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 4) ==
 993                        0) : GNUNET_NO;
 994       GNUNET_CONTAINER_multihashmap_put (ctx.extended_neighbors, &peer->hashPubKey,
 995                                  neighbor,
 996                                  GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
 997     }
 998   else
 999     {
1000 #if DEBUG_DV
1001       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1002                   "%s: Already know peer %s distance %d, referrer id %d!\n", "dv", GNUNET_i2s(peer), cost, referrer_peer_id);
1003 #endif
1004     }
1005 #if DEBUG_DV
1006     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1007                 "%s: Size of extended_neighbors is %d\n", "dv", GNUNET_CONTAINER_multihashmap_size(ctx.extended_neighbors));
1008 #endif
1009   GNUNET_free(neighbor_update);
1010   /* Old logic to remove entry and replace, not needed now as we only want to remove when full
1011    * or when the referring peer disconnects from us.
1012    */
1013   /*
1014   GNUNET_DLL_remove (neighbor->referrer->referee_head,
1015                      neighbor->referrer->referee_tail, neighbor);
1016   neighbor->referrer = referrer;
1017   GNUNET_DLL_insert (referrer->referee_head,
1018                      referrer->referee_tail, neighbor);
1019   GNUNET_CONTAINER_heap_update_cost (ctx.neighbor_max_heap,
1020                                      neighbor->max_loc, cost);
1021   GNUNET_CONTAINER_heap_update_cost (ctx.neighbor_min_heap,
1022                                      neighbor->min_loc, cost);
1023   neighbor->referrer_id = referrer_peer_id;
1024   neighbor->last_activity = now;
1025   neighbor->cost = cost;
1026   */
1027 }
1028
1029 /**
1030  * Core handler for dv gossip messages.  These will be used
1031  * by us to create a HELLO message for the newly peer containing
1032  * which direct peer we can connect through, and what the cost
1033  * is.  This HELLO will then be scheduled for validation by the
1034  * transport service so that it can be used by all others.
1035  *
1036  * @param cls closure
1037  * @param peer peer which sent the message (immediate sender)
1038  * @param message the message
1039  * @param latency the latency of the connection we received the message from
1040  * @param distance the distance to the immediate peer
1041  */
1042 static int handle_dv_gossip_message (void *cls,
1043                                      const struct GNUNET_PeerIdentity *peer,
1044                                      const struct GNUNET_MessageHeader *message,
1045                                      struct GNUNET_TIME_Relative latency,
1046                                      uint32_t distance)
1047 {
1048 #if DEBUG_DV
1049   char * encPeerAbout;
1050   char * encPeerFrom;
1051 #endif
1052   struct DirectNeighbor *referrer;
1053   p2p_dv_MESSAGE_NeighborInfo *enc_message = (p2p_dv_MESSAGE_NeighborInfo *)message;
1054 #if DEBUG_DV
1055   encPeerAbout = GNUNET_strdup(GNUNET_i2s(&enc_message->neighbor));
1056   encPeerFrom = GNUNET_strdup(GNUNET_i2s(peer));
1057   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1058               "%s: Receives %s message from peer %s about peer %s!\n", "dv", "DV GOSSIP", encPeerFrom, encPeerAbout);
1059   GNUNET_free(encPeerAbout);
1060   GNUNET_free(encPeerFrom);
1061 #endif
1062
1063   if (ntohs (message->size) < sizeof (p2p_dv_MESSAGE_NeighborInfo))
1064     {
1065       return GNUNET_SYSERR;     /* invalid message */
1066     }
1067
1068   referrer = GNUNET_CONTAINER_multihashmap_get (ctx.direct_neighbors,
1069                                                 &peer->hashPubKey);
1070   if (referrer == NULL)
1071     return GNUNET_OK;
1072
1073   addUpdateNeighbor (&enc_message->neighbor,
1074                      ntohl (enc_message->neighbor_id),
1075                      referrer, ntohl (enc_message->cost) + 1);
1076
1077   return GNUNET_OK;
1078 }
1079
1080 /**
1081  * Method called whenever a peer connects.
1082  *
1083  * @param cls closure
1084  * @param peer peer identity this notification is about
1085  * @param latency reported latency of the connection with peer
1086  * @param distance reported distance (DV) to peer
1087  */
1088 void handle_core_connect (void *cls,
1089                           const struct GNUNET_PeerIdentity * peer,
1090                           struct GNUNET_TIME_Relative latency,
1091                           uint32_t distance)
1092 {
1093   struct DirectNeighbor *neighbor;
1094 #if DEBUG_DV
1095   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1096               "%s: Receives core connect message for peer %s distance %d!\n", "dv", GNUNET_i2s(peer), distance);
1097 #endif
1098
1099   if ((distance == 0) && (GNUNET_CONTAINER_multihashmap_get(ctx.direct_neighbors, &peer->hashPubKey) == NULL))
1100   {
1101     neighbor = GNUNET_malloc (sizeof (struct DirectNeighbor));
1102     neighbor->send_context = GNUNET_malloc(sizeof(struct NeighborSendContext));
1103     neighbor->send_context->toNeighbor = neighbor;
1104     neighbor->send_context->timeout = default_dv_delay; /* FIXME: base this on total gossip tasks, or bandwidth */
1105     memcpy (&neighbor->identity, peer, sizeof (struct GNUNET_PeerIdentity));
1106     GNUNET_CONTAINER_multihashmap_put (ctx.direct_neighbors,
1107                                &peer->hashPubKey,
1108                                neighbor, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
1109     addUpdateNeighbor (peer, 0, neighbor, 0);
1110     neighbor->send_context->task = GNUNET_SCHEDULER_add_now(sched, &neighbor_send_task, neighbor->send_context);
1111   }
1112   else
1113   {
1114 #if DEBUG_DV
1115   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1116               "%s: Distance (%d) greater than 0 or already know about peer (%s), not re-adding!\n", "dv", distance, GNUNET_i2s(peer));
1117 #endif
1118     return;
1119   }
1120 }
1121
1122 /**
1123  * Method called whenever a given peer either connects.
1124  *
1125  * @param cls closure
1126  * @param peer peer identity this notification is about
1127  */
1128 void handle_core_disconnect (void *cls,
1129                              const struct GNUNET_PeerIdentity * peer)
1130 {
1131   struct DirectNeighbor *neighbor;
1132   struct DistantNeighbor *referee;
1133
1134 #if DEBUG_DV
1135   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1136               "%s: Receives core peer disconnect message!\n", "dv");
1137 #endif
1138
1139   neighbor =
1140     GNUNET_CONTAINER_multihashmap_get (ctx.direct_neighbors, &peer->hashPubKey);
1141   if (neighbor == NULL)
1142     {
1143       return;
1144     }
1145   while (NULL != (referee = neighbor->referee_head))
1146     distant_neighbor_free (referee);
1147   GNUNET_assert (neighbor->referee_tail == NULL);
1148   GNUNET_CONTAINER_multihashmap_remove (ctx.direct_neighbors,
1149                                 &peer->hashPubKey, neighbor);
1150   if ((neighbor->send_context != NULL) && (neighbor->send_context->task != GNUNET_SCHEDULER_NO_TASK))
1151     GNUNET_SCHEDULER_cancel(sched, neighbor->send_context->task);
1152   GNUNET_free (neighbor);
1153 }
1154
1155
1156 /**
1157  * Process dv requests.
1158  *
1159  * @param cls closure
1160  * @param scheduler scheduler to use
1161  * @param server the initialized server
1162  * @param c configuration to use
1163  */
1164 static void
1165 run (void *cls,
1166      struct GNUNET_SCHEDULER_Handle *scheduler,
1167      struct GNUNET_SERVER_Handle *server,
1168      const struct GNUNET_CONFIGURATION_Handle *c)
1169 {
1170   struct GNUNET_TIME_Relative timeout;
1171   unsigned long long max_hosts;
1172   timeout = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 5);
1173   sched = scheduler;
1174   cfg = c;
1175
1176   /* FIXME: Read from config, or calculate, or something other than this! */
1177   max_hosts = 50;
1178   ctx.max_table_size = 100;
1179   ctx.fisheye_depth = 3;
1180
1181   ctx.neighbor_min_heap =
1182     GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
1183   ctx.neighbor_max_heap =
1184     GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MAX);
1185
1186   ctx.direct_neighbors = GNUNET_CONTAINER_multihashmap_create (max_hosts);
1187   ctx.extended_neighbors =
1188     GNUNET_CONTAINER_multihashmap_create (ctx.max_table_size * 3);
1189
1190   client_transmit_timeout = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 5);
1191   default_dv_delay = GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 5);
1192   GNUNET_SERVER_add_handlers (server, plugin_handlers);
1193   coreAPI =
1194   GNUNET_CORE_connect (sched,
1195                        cfg,
1196                        timeout,
1197                        NULL, /* FIXME: anything we want to pass around? */
1198                        &core_init,
1199                        NULL, /* Don't care about pre-connects */
1200                        &handle_core_connect,
1201                        &handle_core_disconnect,
1202                        NULL,
1203                        GNUNET_NO,
1204                        NULL,
1205                        GNUNET_NO,
1206                        core_handlers);
1207
1208   if (coreAPI == NULL)
1209     return;
1210   /* load (server); Huh? */
1211
1212   /* Scheduled the task to clean up when shutdown is called */
1213   cleanup_task = GNUNET_SCHEDULER_add_delayed (sched,
1214                                 GNUNET_TIME_UNIT_FOREVER_REL,
1215                                 &shutdown_task,
1216                                 NULL);
1217 }
1218
1219
1220 /**
1221  * The main function for the dv service.
1222  *
1223  * @param argc number of arguments from the command line
1224  * @param argv command line arguments
1225  * @return 0 ok, 1 on error
1226  */
1227 int
1228 main (int argc, char *const *argv)
1229 {
1230   return (GNUNET_OK ==
1231           GNUNET_SERVICE_run (argc,
1232                               argv,
1233                               "dv",
1234                               GNUNET_SERVICE_OPTION_NONE,
1235                               &run, NULL)) ? 0 : 1;
1236 }