src/nse/gnunet-service-nse.c

   1 /*
   2  This file is part of GNUnet.
   3  (C) 2009, 2010, 2011 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 /**
  22  * @file nse/gnunet-service-nse.c
  23  * @brief network size estimation service
  24  * @author Nathan Evans
  25  *
  26  * The purpose of this service is to estimate the size of the network.
  27  * Given a specified interval, each peer hashes the most recent
  28  * timestamp which is evenly divisible by that interval.  This hash
  29  * is compared in distance to the peer identity to choose an offset.
  30  * The closer the peer identity to the hashed timestamp, the earlier
  31  * the peer sends out a "nearest peer" message.  The closest peer's
  32  * message should thus be received before any others, which stops
  33  * those peer from sending their messages at a later duration.  So
  34  * every peer should receive the same nearest peer message, and
  35  * from this can calculate the expected number of peers in the
  36  * network.
  37  *
  38  */
  39 #include "platform.h"
  40 #include "gnunet_client_lib.h"
  41 #include "gnunet_constants.h"
  42 #include "gnunet_container_lib.h"
  43 #include "gnunet_protocols.h"
  44 #include "gnunet_signatures.h"
  45 #include "gnunet_service_lib.h"
  46 #include "gnunet_server_lib.h"
  47 #include "gnunet_statistics_service.h"
  48 #include "gnunet_core_service.h"
  49 #include "gnunet_time_lib.h"
  50 #include "gnunet_nse_service.h"
  51 #include "nse.h"
  52
  53 #define DEFAULT_HISTORY_SIZE 50
  54
  55 #define DEFAULT_CORE_QUEUE_SIZE 32
  56
  57 #define DEFAULT_NSE_PRIORITY 5
  58
  59 /**
  60  * Entry in the list of clients which
  61  * should be notified upon a new network
  62  * size estimate calculation.
  63  */
  64 struct ClientListEntry
  65 {
  66   /**
  67    *  Pointer to previous entry
  68    */
  69   struct ClientListEntry *prev;
  70
  71   /**
  72    *  Pointer to next entry
  73    */
  74   struct ClientListEntry *next;
  75
  76   /**
  77    * Client to notify.
  78    */
  79   struct GNUNET_SERVER_Client *client;
  80 };
  81
  82 /**
  83  * Per-peer information.
  84  */
  85 struct NSEPeerEntry
  86 {
  87   /**
  88    * Next peer entry (DLL)
  89    */
  90   struct NSEPeerEntry *next;
  91
  92   /**
  93    *  Prev peer entry (DLL)
  94    */
  95   struct NSEPeerEntry *prev;
  96
  97   /**
  98    * Pending message for this peer.
  99    */
 100   struct GNUNET_MessageHeader *pending_message;
 101
 102   /**
 103    * Core handle for sending messages to this peer.
 104    */
 105   struct GNUNET_CORE_TransmitHandle *th;
 106
 107   /**
 108    * What is the identity of the peer?
 109    */
 110   struct GNUNET_PeerIdentity id;
 111 };
 112
 113 /**
 114  * Handle to our current configuration.
 115  */
 116 static const struct GNUNET_CONFIGURATION_Handle *cfg;
 117
 118 /**
 119  * Handle to the statistics service.
 120  */
 121 static struct GNUNET_STATISTICS_Handle *stats;
 122
 123 /**
 124  * Handle to the core service.
 125  */
 126 static struct GNUNET_CORE_Handle *coreAPI;
 127
 128 /**
 129  * Head of global list of peers.
 130  */
 131 static struct NSEPeerEntry *peers_head;
 132
 133 /**
 134  * Head of global list of clients.
 135  */
 136 static struct NSEPeerEntry *peers_tail;
 137
 138 /**
 139  * Head of global list of clients.
 140  */
 141 static struct ClientListEntry *cle_head;
 142
 143 /**
 144  * Tail of global list of clients.
 145  */
 146 static struct ClientListEntry *cle_tail;
 147
 148 /**
 149  * The current network size estimate.
 150  * Number of bits matching on average
 151  * thus far.
 152  */
 153 static double current_size_estimate;
 154
 155 /**
 156  * The standard deviation of the last
 157  * DEFAULT_HISTORY_SIZE network size estimates.
 158  */
 159 static double current_std_dev;
 160
 161 /**
 162  * Array of the last DEFAULT_HISTORY_SIZE
 163  * network size estimates (matching bits, actually).
 164  */
 165 static unsigned int size_estimates[DEFAULT_HISTORY_SIZE];
 166
 167 /**
 168  * Array of size estimate messages.
 169  */
 170 static struct GNUNET_NSE_FloodMessage
 171     size_estimate_messages[DEFAULT_HISTORY_SIZE];
 172
 173 /**
 174  * Index of most recent estimate.
 175  */
 176 static unsigned int estimate_index;
 177
 178 /**
 179  * Task scheduled to send flood message.
 180  */
 181 static GNUNET_SCHEDULER_TaskIdentifier flood_task;
 182
 183 /**
 184  * Task to schedule flood message and update state.
 185  */
 186 static GNUNET_SCHEDULER_TaskIdentifier schedule_flood_task;
 187
 188 /**
 189  * Notification context, simplifies client broadcasts.
 190  */
 191 static struct GNUNET_SERVER_NotificationContext *nc;
 192
 193 /**
 194  * The previous major time.
 195  */
 196 static struct GNUNET_TIME_Absolute previous_timestamp;
 197
 198 /**
 199  * The next major time.
 200  */
 201 static struct GNUNET_TIME_Absolute next_timestamp;
 202
 203 /**
 204  * Base increment of time to add to send time.
 205  */
 206 static struct GNUNET_TIME_Relative increment;
 207
 208 /**
 209  * The current network size estimate message.
 210  */
 211 static struct GNUNET_NSE_ClientMessage current_estimate_message;
 212
 213 /**
 214  * The public key of this peer.
 215  */
 216 static struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded my_public_key;
 217
 218 /**
 219  * The private key of this peer.
 220  */
 221 static struct GNUNET_CRYPTO_RsaPrivateKey *my_private_key;
 222
 223 /**
 224  * The peer identity of this peer.
 225  */
 226 static struct GNUNET_PeerIdentity my_identity;
 227
 228 /**
 229  * Our flood message, updated whenever a flood is sent.
 230  */
 231 static struct GNUNET_NSE_FloodMessage flood_message;
 232
 233 /**
 234  * Handler for START message from client, triggers an
 235  * immediate current network estimate notification.
 236  * Also, we remember the client for updates upon future
 237  * estimate measurements.
 238  *
 239  * @param cls unused
 240  * @param client who sent the message
 241  * @param message the message received
 242  */
 243 static void
 244 handle_start_message(void *cls, struct GNUNET_SERVER_Client *client,
 245                      const struct GNUNET_MessageHeader *message)
 246 {
 247   if ((ntohs (message->size) != sizeof(struct GNUNET_MessageHeader))
 248       || (ntohs (message->type) != GNUNET_MESSAGE_TYPE_NSE_START))
 249     return;
 250
 251 #if DEBUG_NSE
 252   GNUNET_log_from (GNUNET_ERROR_TYPE_DEBUG, "NSE",
 253       "Received START message from client\n");
 254 #endif
 255   GNUNET_SERVER_notification_context_add (nc, client);
 256   GNUNET_SERVER_receive_done (client, GNUNET_OK);
 257 }
 258
 259 /**
 260  * Called when core is ready to send a message we asked for
 261  * out to the destination.
 262  *
 263  * @param cls closure (NULL)
 264  * @param size number of bytes available in buf
 265  * @param buf where the callee should write the message
 266  * @return number of bytes written to buf
 267  */
 268 static size_t
 269 transmit_ready(void *cls, size_t size, void *buf)
 270 {
 271   struct NSEPeerEntry *peer_entry = cls;
 272   char *cbuf = buf;
 273
 274   size_t msize;
 275   peer_entry->th = NULL;
 276 #if DEBUG_NSE
 277   GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%s: transmit_ready called\n",
 278       GNUNET_i2s (&my_identity));
 279 #endif
 280   if (buf == NULL) /* client disconnected */
 281     {
 282       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 283                   "%s: transmit_ready called (disconnect)\n",
 284                   GNUNET_i2s (&my_identity));
 285       return 0;
 286     }
 287
 288   if (peer_entry->pending_message == NULL)
 289     {
 290       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 291                   "%s: transmit_ready called (no message)\n",
 292                   GNUNET_i2s (&my_identity));
 293       return 0;
 294     }
 295
 296   msize = ntohs (peer_entry->pending_message->size);
 297   if (msize <= size)
 298     memcpy (cbuf, peer_entry->pending_message, msize);
 299 #if DEBUG_NSE
 300   GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 301       "%s: transmit_ready called (transmit %d bytes)\n",
 302       GNUNET_i2s (&my_identity), msize);
 303 #endif
 304   return msize;
 305 }
 306
 307 /**
 308  * We sent on our flood message or one that we received
 309  * which was validated and closer than ours.  Update the
 310  * global list of recent messages and the average.  Also
 311  * re-broadcast the message to any clients.
 312  *
 313  * @param message the network flood message
 314  */
 315 static void
 316 update_network_size_estimate(struct GNUNET_NSE_FloodMessage *message)
 317 {
 318   unsigned int i;
 319   unsigned int count;
 320   double average;
 321   double std_dev;
 322   double diff;
 323
 324   size_estimates[estimate_index] = htonl (message->distance);
 325   memcpy (&size_estimate_messages[estimate_index], message,
 326           sizeof(struct GNUNET_NSE_FloodMessage));
 327
 328   count = 0;
 329   std_dev = 0.0;
 330   average = 0.0;
 331   for (i = 0; i < DEFAULT_HISTORY_SIZE; i++)
 332     {
 333       if (size_estimate_messages[i].distance != 0)
 334         {
 335 #if AVERAGE_SQUARE
 336           average += (1 << htonl (size_estimate_messages[i].distance));
 337 #else
 338           average += htonl (size_estimate_messages[i].distance);
 339 #endif
 340           count++;
 341         }
 342     }
 343
 344   if (count > 0)
 345     {
 346       average /= (double) count;
 347       for (i = 0; i < DEFAULT_HISTORY_SIZE; i++)
 348         {
 349           if (size_estimate_messages[i].distance != 0)
 350             {
 351 #if DEBUG_NSE
 352               GNUNET_log(GNUNET_ERROR_TYPE_WARNING, "%s: estimate %d %d\n", GNUNET_i2s(&my_identity), i, (1 << htonl(size_estimate_messages[i].distance)));
 353 #endif
 354 #if AVERAGE_SQUARE
 355               diff = average
 356                   - (1 << htonl (size_estimate_messages[i].distance));
 357 #else
 358               diff = average - htonl (size_estimate_messages[i].distance);
 359 #endif
 360               std_dev += diff * diff;
 361             }
 362         }
 363       std_dev /= count;
 364       std_dev = sqrt (std_dev);
 365       current_estimate_message.header.size
 366           = htons (sizeof(struct GNUNET_NSE_ClientMessage));
 367       current_estimate_message.header.type
 368           = htons (GNUNET_MESSAGE_TYPE_NSE_ESTIMATE);
 369       current_estimate_message.size_estimate = average;
 370       current_estimate_message.std_deviation = std_dev;
 371       /* Finally, broadcast the current estimate to all clients */
 372 #if DEBUG_NSE
 373       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 374           "%s: sending estimate %f -- %f to client\n",
 375           GNUNET_i2s (&my_identity),
 376           average,
 377           std_dev);
 378 #endif
 379       GNUNET_SERVER_notification_context_broadcast (
 380                                                     nc,
 381                                                     &current_estimate_message.header,
 382                                                     GNUNET_NO);
 383
 384       GNUNET_STATISTICS_set (stats, "Current network size estimate",
 385                              (uint64_t) average, GNUNET_NO);
 386     }
 387 }
 388
 389 static void
 390 send_flood_message(void *cls, const struct GNUNET_SCHEDULER_TaskContext * tc);
 391
 392 /**
 393  * Schedule a flood message to be sent.
 394  *
 395  * @param cls unused
 396  * @param tc context for this message
 397  *
 398  * This should be called on startup,
 399  * when a valid flood message is received (and
 400  * the next send flood message hasn't been
 401  * scheduled yet) and when this peer sends
 402  * a valid flood message.  As such, there should
 403  * always be a message scheduled to be sent.
 404  */
 405 static void
 406 schedule_flood_message(void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
 407 {
 408   GNUNET_HashCode timestamp_hash;
 409   struct GNUNET_TIME_Absolute curr_time;
 410   struct GNUNET_TIME_Relative offset;
 411   unsigned int matching_bits;
 412   double millisecond_offset;
 413
 414   schedule_flood_task = GNUNET_SCHEDULER_NO_TASK;
 415   if ((tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0)
 416     return;
 417
 418   GNUNET_assert(flood_task == GNUNET_SCHEDULER_NO_TASK);
 419
 420   if (0 != GNUNET_TIME_absolute_get_remaining (next_timestamp).rel_value)
 421     {
 422       GNUNET_break(0); /* Shouldn't ever happen! */
 423       schedule_flood_task
 424           = GNUNET_SCHEDULER_add_delayed (
 425                                           GNUNET_TIME_absolute_get_remaining (
 426                                                                               next_timestamp),
 427                                           &schedule_flood_message, NULL);
 428     }
 429
 430   /* Get the current UTC time */
 431   curr_time = GNUNET_TIME_absolute_get ();
 432   /* Find the previous interval start time */
 433   previous_timestamp.abs_value = (curr_time.abs_value / GNUNET_NSE_INTERVAL)
 434       * GNUNET_NSE_INTERVAL;
 435   /* Find the next interval start time */
 436   next_timestamp.abs_value = previous_timestamp.abs_value + GNUNET_NSE_INTERVAL;
 437 #if DEBUG_NSE
 438   GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 439       "%s: curr_time %lu, prev timestamp %lu, next timestamp %lu\n",
 440       GNUNET_i2s (&my_identity), curr_time.abs_value,
 441       previous_timestamp.abs_value, next_timestamp.abs_value);
 442 #endif
 443   GNUNET_CRYPTO_hash (&next_timestamp.abs_value,
 444                       sizeof(next_timestamp.abs_value), &timestamp_hash);
 445   matching_bits = GNUNET_CRYPTO_hash_matching_bits (&timestamp_hash,
 446                                                     &my_identity.hashPubKey);
 447
 448   flood_message.header.size = htons (sizeof(struct GNUNET_NSE_FloodMessage));
 449   flood_message.header.type = htons (GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD);
 450   flood_message.purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_NSE_SEND);
 451   flood_message.purpose.size = htonl (sizeof(struct GNUNET_NSE_FloodMessage)
 452       - sizeof(struct GNUNET_MessageHeader) - sizeof(flood_message.signature));
 453   flood_message.distance = htonl (matching_bits);
 454   flood_message.timestamp = GNUNET_TIME_absolute_hton (next_timestamp);
 455   memcpy (&flood_message.pkey, &my_public_key,
 456           sizeof(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded));
 457   flood_message.proof_of_work = htonl (0);
 458   GNUNET_CRYPTO_rsa_sign (my_private_key, &flood_message.purpose,
 459                           &flood_message.signature);
 460
 461   /*S + f/2 - (f / pi) * (atan(x - p'))*/
 462
 463   // S is next_timestamp
 464   // f is frequency (GNUNET_NSE_INTERVAL)
 465   // x is matching_bits
 466   // p' is current_size_estimate
 467   millisecond_offset = ((double) GNUNET_NSE_INTERVAL / (double) 2)
 468       - ((GNUNET_NSE_INTERVAL / M_PI) * atan (matching_bits
 469           - current_size_estimate));
 470 #if DEBUG_NSE
 471   GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 472       "%s: id matches %d bits, offset is %lu\n\n",
 473       GNUNET_i2s (&my_identity), matching_bits,
 474       (uint64_t) millisecond_offset);
 475 #endif
 476   /* Stop initial call from incrementing */
 477   if (size_estimate_messages[estimate_index].distance != 0)
 478     estimate_index += 1;
 479
 480   if (estimate_index >= DEFAULT_HISTORY_SIZE)
 481     estimate_index = 0;
 482
 483   if (millisecond_offset < curr_time.abs_value - previous_timestamp.abs_value)
 484     offset.rel_value = 0;
 485   else
 486     offset.rel_value = (uint64_t) millisecond_offset + curr_time.abs_value
 487         - previous_timestamp.abs_value;
 488 #if DEBUG_NSE
 489   GNUNET_log (
 490       GNUNET_ERROR_TYPE_WARNING,
 491       "%s: milliseconds until next timestamp %lu, sending flood in %lu\n",
 492       GNUNET_i2s (&my_identity),
 493       GNUNET_TIME_absolute_get_remaining (next_timestamp).rel_value,
 494       offset.rel_value);
 495 #endif
 496   flood_task = GNUNET_SCHEDULER_add_delayed (offset, &send_flood_message, NULL);
 497
 498 }
 499
 500 #if VERIFY_CRYPTO
 501 /**
 502  * Check whether the given public key
 503  * and integer are a valid proof of work.
 504  *
 505  * @param pkey the public key
 506  * @param val the integer
 507  * @param want the number of trailing zeroes
 508  *
 509  * @return GNUNET_YES if valid, GNUNET_NO if not
 510  */
 511 static int check_proof_of_work(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded pkey, uint64_t val, unsigned int want)
 512   {
 513
 514     return GNUNET_YES;
 515   }
 516
 517 /**
 518  * Count the trailing zeroes in hash.
 519  *
 520  * @param hash
 521  *
 522  * @return the number of trailing zero bits.
 523  */
 524 static unsigned int count_trailing_zeroes(GNUNET_HashCode *hash)
 525   {
 526     unsigned int hash_count;
 527
 528     hash_count = sizeof(GNUNET_HashCode) * 8;
 529     while ((0 == GNUNET_CRYPTO_hash_get_bit(hash, hash_count)))
 530     hash_count--;
 531     return (sizeof(GNUNET_HashCode) * 8) - hash_count;
 532   }
 533
 534 /**
 535  * Given a public key, find an integer such that
 536  * the hash of the key concatenated with the integer
 537  * has <param>want</param> trailing 0 bits.
 538  *
 539  * @param pkey the public key
 540  * @param want the number of trailing 0 bits
 541  *
 542  * @return 64 bit number that satisfies the
 543  *         requirements
 544  *
 545  * FIXME: use pointer and return GNUNET_YES or
 546  *        GNUNET_NO in case no such number works?
 547  */
 548 static uint64_t find_proof_of_work(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded *pkey, unsigned int want)
 549   {
 550     uint64_t counter;
 551     static char buf[sizeof(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded) + sizeof(uint64_t)];
 552     unsigned int data_size;
 553     static GNUNET_HashCode result;
 554
 555     data_size = sizeof(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded) + sizeof(uint64_t);
 556     memcpy(buf, pkey, sizeof(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded));
 557     counter = 0;
 558     while (counter != (uint64_t)-1)
 559       {
 560         memcpy(&buf[sizeof(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded)], &counter, sizeof(uint64_t));
 561         GNUNET_CRYPTO_hash(buf, data_size, &result);
 562         if (want == count_trailing_zeroes(&result)) /* Found good proof of work! */
 563         break;
 564         counter++;
 565       }
 566     if (counter < (uint64_t)-1)
 567     return counter; /* Found valid proof of work */
 568     else
 569     return 0; /* Did not find valid proof of work */
 570   }
 571
 572 /**
 573  * An incoming flood message has been received which claims
 574  * to have more bits matching than any we know in this time
 575  * period.  Verify the signature and/or proof of work.
 576  *
 577  * @param incoming_flood the message to verify
 578  *
 579  * @return GNUNET_YES if the message is verified
 580  *         GNUNET_NO if the key/signature don't verify
 581  */
 582 static int verify_message_crypto(struct GNUNET_NSE_FloodMessage *incoming_flood)
 583   {
 584     int ret;
 585     if (GNUNET_OK == (ret
 586             = GNUNET_CRYPTO_rsa_verify (GNUNET_SIGNATURE_PURPOSE_NSE_SEND,
 587                 &incoming_flood->purpose,
 588                 &incoming_flood->signature,
 589                 &incoming_flood->pkey)))
 590     return GNUNET_YES;
 591
 592     return GNUNET_NO;
 593   }
 594 #endif
 595
 596 /**
 597  * Core handler for size estimate flooding messages.
 598  *
 599  * @param cls closure unused
 600  * @param message message
 601  * @param peer peer identity this message is from (ignored)
 602  * @param atsi performance data (ignored)
 603  *
 604  */
 605 static int
 606 handle_p2p_size_estimate(void *cls, const struct GNUNET_PeerIdentity *peer,
 607                          const struct GNUNET_MessageHeader *message,
 608                          const struct GNUNET_TRANSPORT_ATS_Information *atsi)
 609 {
 610   struct GNUNET_NSE_FloodMessage *incoming_flood;
 611   struct GNUNET_TIME_Absolute curr_time;
 612   uint64_t drift;
 613
 614 #if DEBUG_NSE
 615   GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%s: received flood message!\n",
 616       GNUNET_i2s (&my_identity));
 617 #endif
 618   if (ntohs (message->size) != sizeof(struct GNUNET_NSE_FloodMessage))
 619     {
 620       GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%s: bad message size!\n",
 621                   GNUNET_i2s (&my_identity));
 622       return GNUNET_NO;
 623     }
 624
 625   GNUNET_STATISTICS_update (stats, "# flood messages received", 1, GNUNET_NO);
 626   incoming_flood = (struct GNUNET_NSE_FloodMessage *) message;
 627   if (ntohl (incoming_flood->distance)
 628       <= ntohl (size_estimate_messages[estimate_index].distance)) /* Not closer than our most recent message */
 629     {
 630 #if DEBUG_NSE
 631       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 632           "%s: distance %d not greater than %d, discarding\n",
 633           GNUNET_i2s (&my_identity), ntohl (incoming_flood->distance),
 634           ntohl (size_estimate_messages[estimate_index].distance));
 635 #endif
 636       GNUNET_STATISTICS_update (stats,
 637                                 "# flood messages discarded (had closer)", 1,
 638                                 GNUNET_NO);
 639       return GNUNET_OK;
 640     }
 641
 642   curr_time = GNUNET_TIME_absolute_get ();
 643   if (curr_time.abs_value
 644       > GNUNET_TIME_absolute_ntoh (incoming_flood->timestamp).abs_value)
 645     drift = curr_time.abs_value
 646         - GNUNET_TIME_absolute_ntoh (incoming_flood->timestamp).abs_value;
 647   else
 648     drift = GNUNET_TIME_absolute_ntoh (incoming_flood->timestamp).abs_value
 649         - curr_time.abs_value;
 650
 651   if (drift > GNUNET_NSE_DRIFT_TOLERANCE)
 652     {
 653       GNUNET_STATISTICS_update (
 654                                 stats,
 655                                 "# flood messages discarded (clock skew too high)",
 656                                 1, GNUNET_NO);
 657       return GNUNET_OK;
 658     }
 659
 660 #if VERIFY_CRYPTO
 661   if (GNUNET_YES != verify_message_crypto(incoming_flood))
 662     {
 663       GNUNET_STATISTICS_update (stats,
 664           "# flood messages discarded (bad crypto)",
 665           1, GNUNET_NO);
 666       return GNUNET_OK;
 667     }
 668 #endif
 669
 670   /* Have a new, better size estimate! */
 671   update_network_size_estimate (incoming_flood);
 672
 673   if (flood_task != GNUNET_SCHEDULER_NO_TASK)
 674     {
 675 #if DEBUG_NSE
 676       GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "%s: received closer message, canceling my flood task!\n", GNUNET_i2s(&my_identity));
 677 #endif
 678       GNUNET_SCHEDULER_cancel (flood_task);
 679       flood_task = GNUNET_SCHEDULER_NO_TASK;
 680     }
 681
 682   /** Commenting out prevents forwarding of messages */
 683 #if DO_FORWARD
 684   GNUNET_SCHEDULER_add_now(&send_flood_message, &size_estimate_messages[estimate_index]);
 685 #endif
 686   if (schedule_flood_task != GNUNET_SCHEDULER_NO_TASK)
 687     GNUNET_SCHEDULER_cancel (schedule_flood_task);
 688
 689   schedule_flood_task
 690       = GNUNET_SCHEDULER_add_delayed (
 691                                       GNUNET_TIME_absolute_get_remaining (
 692                                                                           next_timestamp),
 693                                       &schedule_flood_message, NULL);
 694
 695   return GNUNET_OK;
 696 }
 697
 698 /**
 699  * Send a flood message.
 700  *
 701  * If we've gotten here, it means either we haven't received
 702  * a network size estimate message closer than ours, or
 703  * we need to forward a message we received which was closer
 704  * than ours.
 705  */
 706 static void
 707 send_flood_message(void *cls, const struct GNUNET_SCHEDULER_TaskContext * tc)
 708 {
 709   struct NSEPeerEntry *peer_entry;
 710   struct GNUNET_NSE_FloodMessage *to_send;
 711
 712   if (cls == NULL) /* Means we are sending our OWN flood message */
 713     to_send = &flood_message;
 714   else
 715     /* Received a message from another peer that should be forwarded */
 716     to_send = (struct GNUNET_NSE_FloodMessage *) cls;
 717
 718   flood_task = GNUNET_SCHEDULER_NO_TASK;
 719   if ((tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0)
 720     return;
 721 #if DEBUG_NSE
 722   GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 723       "%s: my time has come, sending flood message of size %d!\n",
 724       GNUNET_i2s (&my_identity), ntohs (to_send->header.size));
 725 #endif
 726   peer_entry = peers_head;
 727
 728   while (peer_entry != NULL)
 729     {
 730       peer_entry->pending_message = &to_send->header;
 731       peer_entry->th
 732           = GNUNET_CORE_notify_transmit_ready (
 733                                                coreAPI,
 734                                                GNUNET_NO,
 735                                                DEFAULT_NSE_PRIORITY,
 736                                                GNUNET_TIME_absolute_get_remaining (
 737                                                                                    next_timestamp),
 738                                                &peer_entry->id,
 739                                                ntohs (to_send->header.size),
 740                                                &transmit_ready, peer_entry);
 741       if (peer_entry->th == NULL)
 742         GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 743                     "%s: transmit handle is null!\n", GNUNET_i2s (&my_identity));
 744 #if DEBUG_NSE
 745       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 746           "%s: Sending flood message (distance %d) to %s!\n",
 747           GNUNET_i2s (&my_identity), ntohl (to_send->distance),
 748           GNUNET_h2s (&peer_entry->id.hashPubKey));
 749 #endif
 750       peer_entry = peer_entry->next;
 751     }
 752
 753   if (cls == NULL) /* Need to update our size estimate */
 754     {
 755       update_network_size_estimate (to_send);
 756       GNUNET_STATISTICS_update (stats, "# flood messages sent", 1, GNUNET_NO);
 757     }
 758   else
 759     GNUNET_STATISTICS_update (stats, "# flood messages forwarded", 1, GNUNET_NO);
 760
 761 #if DEBUG_NSE
 762   GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 763       "%s: scheduling schedule_flood_message in %lu\n",
 764       GNUNET_i2s (&my_identity),
 765       GNUNET_TIME_absolute_get_remaining (next_timestamp).rel_value);
 766 #endif
 767   if (schedule_flood_task != GNUNET_SCHEDULER_NO_TASK)
 768     GNUNET_SCHEDULER_cancel (schedule_flood_task);
 769
 770   schedule_flood_task
 771       = GNUNET_SCHEDULER_add_delayed (
 772                                       GNUNET_TIME_absolute_get_remaining (
 773                                                                           next_timestamp),
 774                                       &schedule_flood_message, NULL);
 775 }
 776
 777 /**
 778  * Method called whenever a peer connects.
 779  *
 780  * @param cls closure
 781  * @param peer peer identity this notification is about
 782  * @param atsi performance data
 783  */
 784 static void
 785 handle_core_connect(void *cls, const struct GNUNET_PeerIdentity *peer,
 786                     const struct GNUNET_TRANSPORT_ATS_Information *atsi)
 787 {
 788   struct NSEPeerEntry *peer_entry;
 789
 790   if (0 == (memcmp (peer, &my_identity, sizeof(struct GNUNET_PeerIdentity))))
 791     return; /* Do not connect to self... */
 792
 793   peer_entry = GNUNET_malloc(sizeof(struct NSEPeerEntry));
 794   memcpy (&peer_entry->id, peer, sizeof(struct GNUNET_PeerIdentity));
 795   GNUNET_CONTAINER_DLL_insert(peers_head, peers_tail, peer_entry);
 796 }
 797
 798 /**
 799  * Method called whenever a peer disconnects.
 800  *
 801  * @param cls closure
 802  * @param peer peer identity this notification is about
 803  */
 804 static void
 805 handle_core_disconnect(void *cls, const struct GNUNET_PeerIdentity *peer)
 806 {
 807   struct NSEPeerEntry *pos;
 808
 809   if (0 == (memcmp (peer, &my_identity, sizeof(struct GNUNET_PeerIdentity))))
 810     return; /* Ignore disconnect from self... */
 811
 812   pos = peers_head;
 813   while ((NULL != pos) && (0 != memcmp (&pos->id, peer,
 814                                         sizeof(struct GNUNET_PeerIdentity))))
 815     pos = pos->next;
 816   if (pos == NULL)
 817     {
 818       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 819                   "Received disconnect before connect!\n");
 820       GNUNET_break(0); /* Should never receive a disconnect message for a peer we don't know about... */
 821       return;
 822     }
 823
 824   /* TODO: decide whether to copy the message, or always use the static pointer */
 825 #if TODO
 826   if (pos->pending_message != NULL)
 827   GNUNET_free(pos->pending_message);
 828 #endif
 829
 830   if (pos->th != NULL)
 831     GNUNET_CORE_notify_transmit_ready_cancel (pos->th);
 832   GNUNET_CONTAINER_DLL_remove(peers_head, peers_tail, pos);
 833   GNUNET_free(pos);
 834 }
 835
 836 /**
 837  * A client disconnected. Remove it from the
 838  * global DLL of clients.
 839  *
 840  * @param cls closure, NULL
 841  * @param client identification of the client
 842  */
 843 static void
 844 handle_client_disconnect(void *cls, struct GNUNET_SERVER_Client* client)
 845 {
 846   struct ClientListEntry *cle;
 847
 848   while (NULL != (cle = cle_head))
 849     cle = cle->next;
 850
 851   if (cle != NULL)
 852     {
 853       GNUNET_SERVER_client_drop (cle->client);
 854       GNUNET_CONTAINER_DLL_remove(cle_head,
 855           cle_tail,
 856           cle);
 857       GNUNET_free(cle);
 858     }
 859   if (coreAPI != NULL)
 860     {
 861       GNUNET_CORE_disconnect (coreAPI);
 862       coreAPI = NULL;
 863     }
 864 }
 865
 866 /**
 867  * Task run during shutdown.
 868  *
 869  * @param cls unused
 870  * @param tc unused
 871  */
 872 static void
 873 shutdown_task(void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
 874 {
 875   struct ClientListEntry *cle;
 876
 877   if (flood_task != GNUNET_SCHEDULER_NO_TASK)
 878     GNUNET_SCHEDULER_cancel (flood_task);
 879   GNUNET_SERVER_notification_context_destroy (nc);
 880   nc = NULL;
 881   while (NULL != (cle = cle_head))
 882     {
 883       GNUNET_SERVER_client_drop (cle->client);
 884       GNUNET_CONTAINER_DLL_remove (cle_head,
 885           cle_tail,
 886           cle);
 887       GNUNET_free (cle);
 888     }
 889
 890   if (coreAPI != NULL)
 891     {
 892       GNUNET_CORE_disconnect (coreAPI);
 893       coreAPI = NULL;
 894     }
 895
 896   if (stats != NULL)
 897     GNUNET_STATISTICS_destroy (stats, GNUNET_NO);
 898
 899 }
 900
 901 /**
 902  * Called on core init/fail.
 903  *
 904  * @param cls service closure
 905  * @param server handle to the server for this service
 906  * @param identity the public identity of this peer
 907  * @param publicKey the public key of this peer
 908  */
 909 void
 910 core_init(void *cls, struct GNUNET_CORE_Handle *server,
 911           const struct GNUNET_PeerIdentity *identity,
 912           const struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded *publicKey)
 913 {
 914   struct GNUNET_TIME_Absolute curr_time;
 915   if (server == NULL)
 916     {
 917 #if DEBUG_NSE
 918       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%s: Connection to core FAILED!\n",
 919           "nse", GNUNET_i2s (identity));
 920 #endif
 921       GNUNET_SCHEDULER_add_now (&shutdown_task, NULL);
 922       return;
 923     }
 924
 925   /* Copy our identity so we can use it */
 926   memcpy (&my_identity, identity, sizeof(struct GNUNET_PeerIdentity));
 927   /* Copy our public key for inclusion in flood messages */
 928   memcpy (&my_public_key, publicKey,
 929           sizeof(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded));
 930
 931   if (flood_task != GNUNET_SCHEDULER_NO_TASK)
 932     GNUNET_SCHEDULER_cancel (flood_task);
 933
 934   /* Get the current UTC time */
 935   curr_time = GNUNET_TIME_absolute_get ();
 936   /* Find the previous interval start time */
 937   previous_timestamp.abs_value = (curr_time.abs_value / GNUNET_NSE_INTERVAL)
 938       * GNUNET_NSE_INTERVAL;
 939   /* Find the next interval start time */
 940   next_timestamp.abs_value = previous_timestamp.abs_value + GNUNET_NSE_INTERVAL;
 941
 942 #if DEBUG_NSE
 943   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 944       "%s: Core connection initialized, I am peer: %s, scheduling flood task in %lu\n", "nse",
 945       GNUNET_i2s (identity), GNUNET_TIME_absolute_get_remaining(next_timestamp));
 946 #endif
 947   /* FIXME: In production, we'd likely want to do this immediately, but in test-beds it causes stupid behavior */
 948   if (schedule_flood_task != GNUNET_SCHEDULER_NO_TASK)
 949     GNUNET_SCHEDULER_cancel (schedule_flood_task);
 950   schedule_flood_task
 951       = GNUNET_SCHEDULER_add_delayed (
 952                                       GNUNET_TIME_absolute_get_remaining (
 953                                                                           next_timestamp),
 954                                       &schedule_flood_message, NULL);
 955
 956   GNUNET_SERVER_notification_context_broadcast (
 957                                                 nc,
 958                                                 &current_estimate_message.header,
 959                                                 GNUNET_NO);
 960 }
 961
 962 /**
 963  * Handle network size estimate clients.
 964  *
 965  * @param cls closure
 966  * @param server the initialized server
 967  * @param c configuration to use
 968  */
 969 static void
 970 run(void *cls, struct GNUNET_SERVER_Handle *server,
 971     const struct GNUNET_CONFIGURATION_Handle *c)
 972 {
 973   char *keyfile;
 974   static const struct GNUNET_SERVER_MessageHandler handlers[] =
 975     {
 976       { &handle_start_message, NULL, GNUNET_MESSAGE_TYPE_NSE_START, 0 },
 977       { NULL, NULL, 0, 0 } };
 978
 979   static const struct GNUNET_CORE_MessageHandler core_handlers[] =
 980     {
 981       { &handle_p2p_size_estimate, GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD, 0 },
 982       { NULL, 0, 0 } };
 983
 984   cfg = c;
 985
 986   if (GNUNET_OK
 987       != GNUNET_CONFIGURATION_get_value_filename (c, "GNUNETD", "HOSTKEY",
 988                                                   &keyfile))
 989     {
 990       GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _
 991       ("NSE service is lacking key configuration settings.  Exiting.\n"));
 992       GNUNET_SCHEDULER_shutdown ();
 993       return;
 994     }
 995
 996   my_private_key = GNUNET_CRYPTO_rsa_key_create_from_file (keyfile);
 997   GNUNET_free (keyfile);
 998   if (my_private_key == NULL)
 999     {
1000       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1001                   _("NSE Service could not access hostkey.  Exiting.\n"));
1002       GNUNET_SCHEDULER_shutdown ();
1003       return;
1004     }
1005
1006   GNUNET_SERVER_add_handlers (server, handlers);
1007   nc = GNUNET_SERVER_notification_context_create (server, 16);
1008   GNUNET_SERVER_disconnect_notify (server, &handle_client_disconnect, NULL);
1009
1010   flood_task = GNUNET_SCHEDULER_NO_TASK;
1011   /** Connect to core service and register core handlers */
1012   coreAPI = GNUNET_CORE_connect (cfg, /* Main configuration */
1013   DEFAULT_CORE_QUEUE_SIZE, /* queue size */
1014   NULL, /* Closure passed to functions */
1015   &core_init, /* Call core_init once connected */
1016   &handle_core_connect, /* Handle connects */
1017   &handle_core_disconnect, /* Handle disconnects */
1018   NULL, /* Do we care about "status" updates? */
1019   NULL, /* Don't want notified about all incoming messages */
1020   GNUNET_NO, /* For header only inbound notification */
1021   NULL, /* Don't want notified about all outbound messages */
1022   GNUNET_NO, /* For header only outbound notification */
1023   core_handlers); /* Register these handlers */
1024
1025   if (coreAPI == NULL)
1026     {
1027       GNUNET_SCHEDULER_add_now (&shutdown_task, NULL);
1028       return;
1029     }
1030
1031   stats = GNUNET_STATISTICS_create ("NSE", cfg);
1032
1033   increment
1034       = GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS,
1035                                        GNUNET_NSE_INTERVAL
1036                                            / (sizeof(GNUNET_HashCode) * 8));
1037   /* Set we have no idea defaults for network size estimate */
1038   current_size_estimate = 0.0;
1039   current_std_dev = NAN;
1040   size_estimates[estimate_index] = 0;
1041   current_estimate_message.header.size
1042       = htons (sizeof(struct GNUNET_NSE_ClientMessage));
1043   current_estimate_message.header.type
1044       = htons (GNUNET_MESSAGE_TYPE_NSE_ESTIMATE);
1045   current_estimate_message.size_estimate = current_size_estimate;
1046   current_estimate_message.std_deviation = current_std_dev;
1047   GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_FOREVER_REL, &shutdown_task,
1048                                 NULL);
1049 }
1050
1051 /**
1052  * The main function for the statistics service.
1053  *
1054  * @param argc number of arguments from the command line
1055  * @param argv command line arguments
1056  * @return 0 ok, 1 on error
1057  */
1058 int
1059 main(int argc, char * const *argv)
1060 {
1061   return (GNUNET_OK == GNUNET_SERVICE_run (argc, argv, "nse",
1062                                            GNUNET_SERVICE_OPTION_NONE, &run,
1063                                            NULL)) ? 0 : 1;
1064 }
1065
1066 /* End of gnunet-service-nse.c */
1067