src/fragmentation/fragmentation.c

   1 /*
   2      This file is part of GNUnet
   3      Copyright (C) 2009-2013 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., 51 Franklin Street, Fifth Floor,
  18      Boston, MA 02110-1301, USA.
  19 */
  20 /**
  21  * @file src/fragmentation/fragmentation.c
  22  * @brief library to help fragment messages
  23  * @author Christian Grothoff
  24  */
  25 #include "platform.h"
  26 #include "gnunet_fragmentation_lib.h"
  27 #include "gnunet_protocols.h"
  28 #include "fragmentation.h"
  29
  30
  31 /**
  32  * Absolute minimum delay we impose between sending and expecting ACK to arrive.
  33  */
  34 #define MIN_ACK_DELAY GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, 1)
  35
  36
  37 /**
  38  * Fragmentation context.
  39  */
  40 struct GNUNET_FRAGMENT_Context
  41 {
  42   /**
  43    * Statistics to use.
  44    */
  45   struct GNUNET_STATISTICS_Handle *stats;
  46
  47   /**
  48    * Tracker for flow control.
  49    */
  50   struct GNUNET_BANDWIDTH_Tracker *tracker;
  51
  52   /**
  53    * Current expected delay for ACKs.
  54    */
  55   struct GNUNET_TIME_Relative ack_delay;
  56
  57   /**
  58    * Current expected delay between messages.
  59    */
  60   struct GNUNET_TIME_Relative msg_delay;
  61
  62   /**
  63    * Next allowed transmission time.
  64    */
  65   struct GNUNET_TIME_Absolute delay_until;
  66
  67   /**
  68    * Time we transmitted the last message of the last round.
  69    */
  70   struct GNUNET_TIME_Absolute last_round;
  71
  72   /**
  73    * Message to fragment (allocated at the end of this struct).
  74    */
  75   const struct GNUNET_MessageHeader *msg;
  76
  77   /**
  78    * Function to call for transmissions.
  79    */
  80   GNUNET_FRAGMENT_MessageProcessor proc;
  81
  82   /**
  83    * Closure for @e proc.
  84    */
  85   void *proc_cls;
  86
  87   /**
  88    * Bitfield, set to 1 for each unacknowledged fragment.
  89    */
  90   uint64_t acks;
  91
  92   /**
  93    * Bitfield with all possible bits for @e acks (used to mask the
  94    * ack we get back).
  95    */
  96   uint64_t acks_mask;
  97
  98   /**
  99    * Task performing work for the fragmenter.
 100    */
 101   struct GNUNET_SCHEDULER_Task *task;
 102
 103   /**
 104    * Our fragmentation ID. (chosen at random)
 105    */
 106   uint32_t fragment_id;
 107
 108   /**
 109    * Round-robin selector for the next transmission.
 110    */
 111   unsigned int next_transmission;
 112
 113   /**
 114    * How many rounds of transmission have we completed so far?
 115    */
 116   unsigned int num_rounds;
 117
 118   /**
 119    * How many transmission have we completed in this round?
 120    */
 121   unsigned int num_transmissions;
 122
 123   /**
 124    * #GNUNET_YES if we called @e proc and are now waiting for #GNUNET_FRAGMENT_context_transmission_done()
 125    */
 126   int8_t proc_busy;
 127
 128   /**
 129    * #GNUNET_YES if we are waiting for an ACK.
 130    */
 131   int8_t wack;
 132
 133   /**
 134    * Target fragment size.
 135    */
 136   uint16_t mtu;
 137
 138 };
 139
 140
 141 /**
 142  * Convert an ACK message to a printable format suitable for logging.
 143  *
 144  * @param ack message to print
 145  * @return ack in human-readable format
 146  */
 147 const char *
 148 GNUNET_FRAGMENT_print_ack (const struct GNUNET_MessageHeader *ack)
 149 {
 150   static char buf[128];
 151   const struct FragmentAcknowledgement *fa;
 152
 153   if (sizeof (struct FragmentAcknowledgement) !=
 154       htons (ack->size))
 155     return "<malformed ack>";
 156   fa = (const struct FragmentAcknowledgement *) ack;
 157   GNUNET_snprintf (buf,
 158                    sizeof (buf),
 159                    "%u-%llX",
 160                    ntohl (fa->fragment_id),
 161                    GNUNET_ntohll (fa->bits));
 162   return buf;
 163 }
 164
 165
 166 /**
 167  * Transmit the next fragment to the other peer.
 168  *
 169  * @param cls the `struct GNUNET_FRAGMENT_Context`
 170  * @param tc scheduler context
 171  */
 172 static void
 173 transmit_next (void *cls,
 174                const struct GNUNET_SCHEDULER_TaskContext *tc)
 175 {
 176   struct GNUNET_FRAGMENT_Context *fc = cls;
 177   char msg[fc->mtu];
 178   const char *mbuf;
 179   struct FragmentHeader *fh;
 180   struct GNUNET_TIME_Relative delay;
 181   unsigned int bit;
 182   size_t size;
 183   size_t fsize;
 184   int wrap;
 185
 186   fc->task = NULL;
 187   GNUNET_assert (GNUNET_NO == fc->proc_busy);
 188   if (0 == fc->acks)
 189     return;                     /* all done */
 190   /* calculate delay */
 191   wrap = 0;
 192   while (0 == (fc->acks & (1LL << fc->next_transmission)))
 193   {
 194     fc->next_transmission = (fc->next_transmission + 1) % 64;
 195     wrap |= (0 == fc->next_transmission);
 196   }
 197   bit = fc->next_transmission;
 198   size = ntohs (fc->msg->size);
 199   if (bit == size / (fc->mtu - sizeof (struct FragmentHeader)))
 200     fsize =
 201         (size % (fc->mtu - sizeof (struct FragmentHeader))) +
 202         sizeof (struct FragmentHeader);
 203   else
 204     fsize = fc->mtu;
 205   if (NULL != fc->tracker)
 206     delay = GNUNET_BANDWIDTH_tracker_get_delay (fc->tracker,
 207                                                 fsize);
 208   else
 209     delay = GNUNET_TIME_UNIT_ZERO;
 210   if (delay.rel_value_us > 0)
 211   {
 212     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 213                 "Fragmentation logic delays transmission of next fragment by %s\n",
 214                 GNUNET_STRINGS_relative_time_to_string (delay,
 215                                                         GNUNET_YES));
 216     fc->task = GNUNET_SCHEDULER_add_delayed (delay,
 217                                              &transmit_next,
 218                                              fc);
 219     return;
 220   }
 221   fc->next_transmission = (fc->next_transmission + 1) % 64;
 222   wrap |= (0 == fc->next_transmission);
 223   while (0 == (fc->acks & (1LL << fc->next_transmission)))
 224   {
 225     fc->next_transmission = (fc->next_transmission + 1) % 64;
 226     wrap |= (0 == fc->next_transmission);
 227   }
 228
 229   /* assemble fragmentation message */
 230   mbuf = (const char *) &fc[1];
 231   fh = (struct FragmentHeader *) msg;
 232   fh->header.size = htons (fsize);
 233   fh->header.type = htons (GNUNET_MESSAGE_TYPE_FRAGMENT);
 234   fh->fragment_id = htonl (fc->fragment_id);
 235   fh->total_size = fc->msg->size;       /* already in big-endian */
 236   fh->offset = htons ((fc->mtu - sizeof (struct FragmentHeader)) * bit);
 237   memcpy (&fh[1], &mbuf[bit * (fc->mtu - sizeof (struct FragmentHeader))],
 238           fsize - sizeof (struct FragmentHeader));
 239   if (NULL != fc->tracker)
 240     GNUNET_BANDWIDTH_tracker_consume (fc->tracker, fsize);
 241   GNUNET_STATISTICS_update (fc->stats,
 242                             _("# fragments transmitted"),
 243                             1,
 244                             GNUNET_NO);
 245   if (0 != fc->last_round.abs_value_us)
 246     GNUNET_STATISTICS_update (fc->stats,
 247                               _("# fragments retransmitted"),
 248                               1,
 249                               GNUNET_NO);
 250
 251   /* select next message to calculate delay */
 252   bit = fc->next_transmission;
 253   size = ntohs (fc->msg->size);
 254   if (bit == size / (fc->mtu - sizeof (struct FragmentHeader)))
 255     fsize = size % (fc->mtu - sizeof (struct FragmentHeader));
 256   else
 257     fsize = fc->mtu;
 258   if (NULL != fc->tracker)
 259     delay = GNUNET_BANDWIDTH_tracker_get_delay (fc->tracker,
 260                                                 fsize);
 261   else
 262     delay = GNUNET_TIME_UNIT_ZERO;
 263   delay = GNUNET_TIME_relative_max (delay,
 264                                     GNUNET_TIME_relative_multiply (fc->msg_delay,
 265                                                                    (1 << fc->num_rounds)));
 266   if (wrap)
 267   {
 268     /* full round transmitted wait 2x delay for ACK before going again */
 269     fc->num_rounds++;
 270     delay = GNUNET_TIME_relative_multiply (fc->ack_delay, 2);
 271     /* never use zero, need some time for ACK always */
 272     delay = GNUNET_TIME_relative_max (MIN_ACK_DELAY, delay);
 273     fc->wack = GNUNET_YES;
 274     fc->last_round = GNUNET_TIME_absolute_get ();
 275     GNUNET_STATISTICS_update (fc->stats,
 276                               _("# fragments wrap arounds"),
 277                               1,
 278                               GNUNET_NO);
 279   }
 280   fc->proc_busy = GNUNET_YES;
 281   fc->delay_until = GNUNET_TIME_relative_to_absolute (delay);
 282   fc->num_transmissions++;
 283   fc->proc (fc->proc_cls,
 284             &fh->header);
 285 }
 286
 287
 288 /**
 289  * Create a fragmentation context for the given message.
 290  * Fragments the message into fragments of size @a mtu or
 291  * less.  Calls @a proc on each un-acknowledged fragment,
 292  * using both the expected @a msg_delay between messages and
 293  * acknowledgements and the given @a tracker to guide the
 294  * frequency of calls to @a proc.
 295  *
 296  * @param stats statistics context
 297  * @param mtu the maximum message size for each fragment
 298  * @param tracker bandwidth tracker to use for flow control (can be NULL)
 299  * @param msg_delay initial delay to insert between fragment transmissions
 300  *              based on previous messages
 301  * @param ack_delay expected delay between fragment transmission
 302  *              and ACK based on previous messages
 303  * @param msg the message to fragment
 304  * @param proc function to call for each fragment to transmit
 305  * @param proc_cls closure for @a proc
 306  * @return the fragmentation context
 307  */
 308 struct GNUNET_FRAGMENT_Context *
 309 GNUNET_FRAGMENT_context_create (struct GNUNET_STATISTICS_Handle *stats,
 310                                 uint16_t mtu,
 311                                 struct GNUNET_BANDWIDTH_Tracker *tracker,
 312                                 struct GNUNET_TIME_Relative msg_delay,
 313                                 struct GNUNET_TIME_Relative ack_delay,
 314                                 const struct GNUNET_MessageHeader *msg,
 315                                 GNUNET_FRAGMENT_MessageProcessor proc,
 316                                 void *proc_cls)
 317 {
 318   struct GNUNET_FRAGMENT_Context *fc;
 319   size_t size;
 320   uint64_t bits;
 321
 322   GNUNET_STATISTICS_update (stats,
 323                             _("# messages fragmented"),
 324                             1,
 325                             GNUNET_NO);
 326   GNUNET_assert (mtu >= 1024 + sizeof (struct FragmentHeader));
 327   size = ntohs (msg->size);
 328   GNUNET_STATISTICS_update (stats,
 329                             _("# total size of fragmented messages"),
 330                             size, GNUNET_NO);
 331   GNUNET_assert (size >= sizeof (struct GNUNET_MessageHeader));
 332   fc = GNUNET_malloc (sizeof (struct GNUNET_FRAGMENT_Context) + size);
 333   fc->stats = stats;
 334   fc->mtu = mtu;
 335   fc->tracker = tracker;
 336   fc->ack_delay = ack_delay;
 337   fc->msg_delay = msg_delay;
 338   fc->msg = (const struct GNUNET_MessageHeader *) &fc[1];
 339   fc->proc = proc;
 340   fc->proc_cls = proc_cls;
 341   fc->fragment_id =
 342       GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 343                                 UINT32_MAX);
 344   memcpy (&fc[1], msg, size);
 345   bits =
 346       (size + mtu - sizeof (struct FragmentHeader) - 1) / (mtu -
 347                                                            sizeof (struct
 348                                                                    FragmentHeader));
 349   GNUNET_assert (bits <= 64);
 350   if (bits == 64)
 351     fc->acks_mask = UINT64_MAX; /* set all 64 bit */
 352   else
 353     fc->acks_mask = (1LL << bits) - 1;  /* set lowest 'bits' bit */
 354   fc->acks = fc->acks_mask;
 355   fc->task = GNUNET_SCHEDULER_add_now (&transmit_next, fc);
 356   return fc;
 357 }
 358
 359
 360 /**
 361  * Continuation to call from the 'proc' function after the fragment
 362  * has been transmitted (and hence the next fragment can now be
 363  * given to proc).
 364  *
 365  * @param fc fragmentation context
 366  */
 367 void
 368 GNUNET_FRAGMENT_context_transmission_done (struct GNUNET_FRAGMENT_Context *fc)
 369 {
 370   GNUNET_assert (fc->proc_busy == GNUNET_YES);
 371   fc->proc_busy = GNUNET_NO;
 372   GNUNET_assert (fc->task == NULL);
 373   fc->task =
 374       GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_absolute_get_remaining
 375                                     (fc->delay_until), &transmit_next, fc);
 376 }
 377
 378
 379 /**
 380  * Process an acknowledgement message we got from the other
 381  * side (to control re-transmits).
 382  *
 383  * @param fc fragmentation context
 384  * @param msg acknowledgement message we received
 385  * @return #GNUNET_OK if this ack completes the work of the 'fc'
 386  *                   (all fragments have been received);
 387  *         #GNUNET_NO if more messages are pending
 388  *         #GNUNET_SYSERR if this ack is not valid for this fc
 389  */
 390 int
 391 GNUNET_FRAGMENT_process_ack (struct GNUNET_FRAGMENT_Context *fc,
 392                              const struct GNUNET_MessageHeader *msg)
 393 {
 394   const struct FragmentAcknowledgement *fa;
 395   uint64_t abits;
 396   struct GNUNET_TIME_Relative ndelay;
 397   unsigned int ack_cnt;
 398   unsigned int snd_cnt;
 399   unsigned int i;
 400
 401   if (sizeof (struct FragmentAcknowledgement) != ntohs (msg->size))
 402   {
 403     GNUNET_break_op (0);
 404     return GNUNET_SYSERR;
 405   }
 406   fa = (const struct FragmentAcknowledgement *) msg;
 407   if (ntohl (fa->fragment_id) != fc->fragment_id)
 408     return GNUNET_SYSERR;       /* not our ACK */
 409   abits = GNUNET_ntohll (fa->bits);
 410   if ( (GNUNET_YES == fc->wack) &&
 411        (0 != fc->num_transmissions) )
 412   {
 413     /* normal ACK, can update running average of delay... */
 414     fc->wack = GNUNET_NO;
 415     ndelay = GNUNET_TIME_absolute_get_duration (fc->last_round);
 416     fc->ack_delay.rel_value_us =
 417         (ndelay.rel_value_us / fc->num_transmissions + 3 * fc->ack_delay.rel_value_us) / 4;
 418     /* calculate ratio msg sent vs. msg acked */
 419     ack_cnt = 0;
 420     snd_cnt = 0;
 421     for (i=0;i<64;i++)
 422     {
 423       if (1 == (fc->acks_mask & (1 << i)))
 424       {
 425         snd_cnt++;
 426         if (0 == (abits & (1 << i)))
 427           ack_cnt++;
 428       }
 429     }
 430     if (0 == ack_cnt)
 431     {
 432       /* complete loss */
 433       fc->msg_delay = GNUNET_TIME_relative_multiply (fc->msg_delay,
 434                                                      snd_cnt);
 435     }
 436     else if (snd_cnt > ack_cnt)
 437     {
 438       /* some loss, slow down proportionally */
 439       fc->msg_delay.rel_value_us = ((fc->msg_delay.rel_value_us * ack_cnt) / snd_cnt);
 440     }
 441     else if (snd_cnt == ack_cnt)
 442     {
 443       fc->msg_delay.rel_value_us =
 444         (ndelay.rel_value_us / fc->num_transmissions + 3 * fc->msg_delay.rel_value_us) / 5;
 445     }
 446     fc->num_transmissions = 0;
 447     fc->msg_delay = GNUNET_TIME_relative_min (fc->msg_delay,
 448                                               GNUNET_TIME_UNIT_SECONDS);
 449     fc->ack_delay = GNUNET_TIME_relative_min (fc->ack_delay,
 450                                               GNUNET_TIME_UNIT_SECONDS);
 451   }
 452   GNUNET_STATISTICS_update (fc->stats,
 453                             _("# fragment acknowledgements received"),
 454                             1,
 455                             GNUNET_NO);
 456   if (abits != (fc->acks & abits))
 457   {
 458     /* ID collission or message reordering, count! This should be rare! */
 459     GNUNET_STATISTICS_update (fc->stats,
 460                               _("# bits removed from fragmentation ACKs"), 1,
 461                               GNUNET_NO);
 462   }
 463   fc->acks = abits & fc->acks_mask;
 464   if (0 != fc->acks)
 465   {
 466     /* more to transmit, do so right now (if tracker permits...) */
 467     if (fc->task != NULL)
 468     {
 469       /* schedule next transmission now, no point in waiting... */
 470       GNUNET_SCHEDULER_cancel (fc->task);
 471       fc->task = GNUNET_SCHEDULER_add_now (&transmit_next, fc);
 472     }
 473     else
 474     {
 475       /* only case where there is no task should be if we're waiting
 476        * for the right to transmit again (proc_busy set to YES) */
 477       GNUNET_assert (GNUNET_YES == fc->proc_busy);
 478     }
 479     return GNUNET_NO;
 480   }
 481
 482   /* all done */
 483   GNUNET_STATISTICS_update (fc->stats,
 484                             _("# fragmentation transmissions completed"),
 485                             1,
 486                             GNUNET_NO);
 487   if (NULL != fc->task)
 488   {
 489     GNUNET_SCHEDULER_cancel (fc->task);
 490     fc->task = NULL;
 491   }
 492   return GNUNET_OK;
 493 }
 494
 495
 496 /**
 497  * Destroy the given fragmentation context (stop calling 'proc', free
 498  * resources).
 499  *
 500  * @param fc fragmentation context
 501  * @param msg_delay where to store average delay between individual message transmissions the
 502  *         last message (OUT only)
 503  * @param ack_delay where to store average delay between transmission and ACK for the
 504  *         last message, set to FOREVER if the message was not fully transmitted (OUT only)
 505  */
 506 void
 507 GNUNET_FRAGMENT_context_destroy (struct GNUNET_FRAGMENT_Context *fc,
 508                                  struct GNUNET_TIME_Relative *msg_delay,
 509                                  struct GNUNET_TIME_Relative *ack_delay)
 510 {
 511   if (fc->task != NULL)
 512     GNUNET_SCHEDULER_cancel (fc->task);
 513   if (NULL != ack_delay)
 514     *ack_delay = fc->ack_delay;
 515   if (NULL != msg_delay)
 516     *msg_delay = GNUNET_TIME_relative_multiply (fc->msg_delay,
 517                                                 fc->num_rounds);
 518   GNUNET_free (fc);
 519 }
 520
 521
 522 /* end of fragmentation.c */