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