src/util/bandwidth.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C) 2010, 2013 GNUnet e.V.
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your 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      Affero General Public License for more details.
  14
  15      You should have received a copy of the GNU Affero General Public License
  16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 /**
  20  * @file util/bandwidth.c
  21  * @brief functions related to bandwidth (unit)
  22  * @author Christian Grothoff
  23  */
  24 #include "platform.h"
  25 #include "gnunet_util_lib.h"
  26
  27
  28 #define LOG(kind,...) GNUNET_log_from (kind, "util-bandwidth", __VA_ARGS__)
  29
  30 /**
  31  * Create a new bandwidth value.
  32  *
  33  * @param bytes_per_second value to create
  34  * @return the new bandwidth value
  35  */
  36 struct GNUNET_BANDWIDTH_Value32NBO
  37 GNUNET_BANDWIDTH_value_init (uint32_t bytes_per_second)
  38 {
  39   struct GNUNET_BANDWIDTH_Value32NBO ret;
  40
  41   ret.value__ = htonl (bytes_per_second);
  42   return ret;
  43 }
  44
  45
  46 /**
  47  * Compute the MIN of two bandwidth values.
  48  *
  49  * @param b1 first value
  50  * @param b2 second value
  51  * @return the min of b1 and b2
  52  */
  53 struct GNUNET_BANDWIDTH_Value32NBO
  54 GNUNET_BANDWIDTH_value_min (struct GNUNET_BANDWIDTH_Value32NBO b1,
  55                             struct GNUNET_BANDWIDTH_Value32NBO b2)
  56 {
  57   return
  58       GNUNET_BANDWIDTH_value_init (GNUNET_MIN
  59                                    (ntohl (b1.value__),
  60                                     ntohl (b2.value__)));
  61 }
  62
  63
  64 /**
  65  * Compute the MAX of two bandwidth values.
  66  *
  67  * @param b1 first value
  68  * @param b2 second value
  69  * @return the min of b1 and b2
  70  */
  71 struct GNUNET_BANDWIDTH_Value32NBO
  72 GNUNET_BANDWIDTH_value_max (struct GNUNET_BANDWIDTH_Value32NBO b1,
  73                             struct GNUNET_BANDWIDTH_Value32NBO b2)
  74 {
  75   return
  76       GNUNET_BANDWIDTH_value_init (GNUNET_MAX
  77                                    (ntohl (b1.value__),
  78                                     ntohl (b2.value__)));
  79 }
  80
  81
  82 /**
  83  * At the given bandwidth, calculate how much traffic will be
  84  * available until the given deadline.
  85  *
  86  * @param bps bandwidth
  87  * @param deadline when is the deadline
  88  * @return number of bytes available at bps until deadline
  89  */
  90 uint64_t
  91 GNUNET_BANDWIDTH_value_get_available_until (struct GNUNET_BANDWIDTH_Value32NBO bps,
  92                                             struct GNUNET_TIME_Relative deadline)
  93 {
  94   uint64_t b;
  95
  96   b = ntohl (bps.value__);
  97   LOG (GNUNET_ERROR_TYPE_DEBUG,
  98        "Bandwidth has %llu bytes available until deadline in %s\n",
  99        (unsigned long long) ((b * deadline.rel_value_us + 500000LL) / 1000000LL),
 100        GNUNET_STRINGS_relative_time_to_string (deadline, GNUNET_YES));
 101   return (b * deadline.rel_value_us + 500000LL) / 1000000LL;
 102 }
 103
 104
 105 /**
 106  * At the given bandwidth, calculate how long it would take for
 107  * @a size bytes to be transmitted.
 108  *
 109  * @param bps bandwidth
 110  * @param size number of bytes we want to have available
 111  * @return how long it would take
 112  */
 113 struct GNUNET_TIME_Relative
 114 GNUNET_BANDWIDTH_value_get_delay_for (struct GNUNET_BANDWIDTH_Value32NBO bps,
 115                                       uint64_t size)
 116 {
 117   uint64_t b;
 118   struct GNUNET_TIME_Relative ret;
 119
 120   b = ntohl (bps.value__);
 121   if (0 == b)
 122   {
 123     LOG (GNUNET_ERROR_TYPE_DEBUG,
 124          "Bandwidth suggests delay of infinity (zero bandwidth)\n");
 125     return GNUNET_TIME_UNIT_FOREVER_REL;
 126   }
 127   ret.rel_value_us = size * 1000LL * 1000LL / b;
 128   LOG (GNUNET_ERROR_TYPE_DEBUG,
 129        "Bandwidth suggests delay of %s for %llu bytes of traffic\n",
 130        GNUNET_STRINGS_relative_time_to_string (ret, GNUNET_YES),
 131        (unsigned long long) size);
 132   return ret;
 133 }
 134
 135
 136 /**
 137  * Task run whenever we hit the bandwidth limit for a tracker.
 138  *
 139  * @param cls the `struct GNUNET_BANDWIDTH_Tracker`
 140  */
 141 static void
 142 excess_trigger (void *cls)
 143 {
 144   struct GNUNET_BANDWIDTH_Tracker *av = cls;
 145
 146   av->excess_task = NULL;
 147   if (NULL != av->excess_cb)
 148   {
 149     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 150                 "Notifying application about excess bandwidth\n");
 151     av->excess_cb (av->excess_cb_cls);
 152   }
 153 }
 154
 155
 156 /**
 157  * Recalculate when we might need to call the excess callback.
 158  */
 159 static void
 160 update_excess (struct GNUNET_BANDWIDTH_Tracker *av)
 161 {
 162   struct GNUNET_TIME_Relative delay;
 163   struct GNUNET_TIME_Absolute now;
 164   uint64_t delta_time;
 165   uint64_t delta_avail;
 166   int64_t left_bytes;
 167   uint64_t max_carry;
 168   int64_t current_consumption;
 169
 170   if (NULL == av->excess_cb)
 171     return; /* nothing to do */
 172   now = GNUNET_TIME_absolute_get ();
 173   delta_time = now.abs_value_us - av->last_update__.abs_value_us;
 174   delta_avail =
 175       (delta_time * ((unsigned long long) av->available_bytes_per_s__) +
 176        500000LL) / 1000000LL;
 177   current_consumption = av->consumption_since_last_update__ - delta_avail;
 178   if (current_consumption > av->consumption_since_last_update__)
 179   {
 180     /* integer underflow, cap! */
 181     current_consumption = INT64_MIN;
 182   }
 183   /* negative current_consumption means that we have savings */
 184   max_carry = ((uint64_t) av->available_bytes_per_s__) * av->max_carry_s__;
 185   if (max_carry < GNUNET_MAX_MESSAGE_SIZE)
 186     max_carry = GNUNET_MAX_MESSAGE_SIZE;
 187   if (max_carry > INT64_MAX)
 188     max_carry = INT64_MAX;
 189   left_bytes = current_consumption + max_carry;
 190   if (left_bytes < current_consumption)
 191   {
 192     /* integer overflow, cap! */
 193     left_bytes = INT64_MAX;
 194   }
 195   /* left_bytes now contains the number of bytes needed until
 196      we have more savings than allowed */
 197   if (left_bytes < 0)
 198   {
 199     /* having excess already */
 200     delay = GNUNET_TIME_UNIT_ZERO;
 201   }
 202   else
 203   {
 204     double factor = 1.0 * left_bytes / (double) av->available_bytes_per_s__;
 205     delay = GNUNET_TIME_relative_saturating_multiply (GNUNET_TIME_UNIT_SECONDS,
 206                                                       (unsigned long long) factor);
 207   }
 208   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 209               "At %llu bps it will take us %s for %lld bytes to reach excess threshold\n",
 210               (unsigned long long) av->available_bytes_per_s__,
 211               GNUNET_STRINGS_relative_time_to_string (delay,
 212                                                       GNUNET_NO),
 213               (long long) left_bytes);
 214   if (NULL != av->excess_task)
 215     GNUNET_SCHEDULER_cancel (av->excess_task);
 216   av->excess_task = GNUNET_SCHEDULER_add_delayed (delay,
 217                                                   &excess_trigger,
 218                                                   av);
 219 }
 220
 221
 222 /**
 223  * Initialize bandwidth tracker.  Note that in addition to the
 224  * 'max_carry_s' limit, we also always allow at least
 225  * #GNUNET_MAX_MESSAGE_SIZE to accumulate.  So if the
 226  * bytes-per-second limit is so small that within 'max_carry_s' not
 227  * even #GNUNET_MAX_MESSAGE_SIZE is allowed to accumulate, it is
 228  * ignored and replaced by #GNUNET_MAX_MESSAGE_SIZE (which is in
 229  * bytes).
 230  *
 231  * To stop notifications about updates and excess callbacks use
 232  * #GNUNET_BANDWIDTH_tracker_notification_stop().
 233  *
 234  * @param av tracker to initialize
 235  * @param update_cb callback to notify a client about the tracker being updated
 236  * @param update_cb_cls cls for the callback
 237  * @param bytes_per_second_limit initial limit to assume
 238  * @param max_carry_s maximum number of seconds unused bandwidth
 239  *        may accumulate before it expires
 240  * @param excess_cb callback to notify if we have excess bandwidth
 241  * @param excess_cb_cls closure for @a excess_cb
 242  */
 243 void
 244 GNUNET_BANDWIDTH_tracker_init2 (struct GNUNET_BANDWIDTH_Tracker *av,
 245                                 GNUNET_BANDWIDTH_TrackerUpdateCallback update_cb,
 246                                 void *update_cb_cls,
 247                                 struct GNUNET_BANDWIDTH_Value32NBO bytes_per_second_limit,
 248                                 uint32_t max_carry_s,
 249                                 GNUNET_BANDWIDTH_ExcessNotificationCallback excess_cb,
 250                                 void *excess_cb_cls)
 251 {
 252   av->update_cb = update_cb;
 253   av->update_cb_cls = update_cb_cls;
 254   av->consumption_since_last_update__ = 0;
 255   av->last_update__ = GNUNET_TIME_absolute_get ();
 256   av->available_bytes_per_s__ = ntohl (bytes_per_second_limit.value__);
 257   av->max_carry_s__ = max_carry_s;
 258   av->excess_cb = excess_cb;
 259   av->excess_cb_cls = excess_cb_cls;
 260   LOG (GNUNET_ERROR_TYPE_DEBUG,
 261        "Tracker %p initialized with %u Bps and max carry %u\n",
 262        av,
 263        (unsigned int) av->available_bytes_per_s__,
 264        (unsigned int) max_carry_s);
 265   update_excess (av);
 266 }
 267
 268
 269 /**
 270  * Initialize bandwidth tracker.  Note that in addition to the
 271  * 'max_carry_s' limit, we also always allow at least
 272  * #GNUNET_MAX_MESSAGE_SIZE to accumulate.  So if the
 273  * bytes-per-second limit is so small that within 'max_carry_s' not
 274  * even #GNUNET_MAX_MESSAGE_SIZE is allowed to accumulate, it is
 275  * ignored and replaced by #GNUNET_MAX_MESSAGE_SIZE (which is in
 276  * bytes).
 277  *
 278  * @param av tracker to initialize
 279  * @param update_cb callback to notify a client about the tracker being updated
 280  * @param update_cb_cls cls for the callback
 281  * @param bytes_per_second_limit initial limit to assume
 282  * @param max_carry_s maximum number of seconds unused bandwidth
 283  *        may accumulate before it expires
 284  */
 285 void
 286 GNUNET_BANDWIDTH_tracker_init (struct GNUNET_BANDWIDTH_Tracker *av,
 287                                GNUNET_BANDWIDTH_TrackerUpdateCallback update_cb,
 288                                void *update_cb_cls,
 289                                struct GNUNET_BANDWIDTH_Value32NBO bytes_per_second_limit,
 290                                uint32_t max_carry_s)
 291 {
 292   GNUNET_BANDWIDTH_tracker_init2 (av, update_cb,
 293                                   update_cb_cls,
 294                                   bytes_per_second_limit,
 295                                   max_carry_s,
 296                                   NULL, NULL);
 297 }
 298
 299
 300 /**
 301  * Stop notifying about tracker updates and excess notifications
 302  *
 303  * @param av the respective trackers
 304  */
 305 void
 306 GNUNET_BANDWIDTH_tracker_notification_stop (struct GNUNET_BANDWIDTH_Tracker *av)
 307 {
 308   if (NULL != av->excess_task)
 309     GNUNET_SCHEDULER_cancel (av->excess_task);
 310   av->excess_task = NULL;
 311   av->excess_cb = NULL;
 312   av->excess_cb_cls = NULL;
 313   av->update_cb = NULL;
 314   av->update_cb_cls = NULL;
 315 }
 316
 317
 318 /**
 319  * Update the tracker, looking at the current time and
 320  * bandwidth consumption data.
 321  *
 322  * @param av tracker to update
 323  */
 324 static void
 325 update_tracker (struct GNUNET_BANDWIDTH_Tracker *av)
 326 {
 327   struct GNUNET_TIME_Absolute now;
 328   uint64_t delta_time;
 329   uint64_t delta_avail;
 330   uint64_t left_bytes;
 331   uint64_t max_carry;
 332
 333   now = GNUNET_TIME_absolute_get ();
 334   delta_time = now.abs_value_us - av->last_update__.abs_value_us;
 335   delta_avail =
 336       (delta_time * ((unsigned long long) av->available_bytes_per_s__) +
 337        500000LL) / 1000000LL;
 338   av->consumption_since_last_update__ -= delta_avail;
 339   av->last_update__ = now;
 340   if (av->consumption_since_last_update__ < 0)
 341   {
 342     left_bytes = - av->consumption_since_last_update__;
 343     max_carry = ((unsigned long long) av->available_bytes_per_s__) *
 344                 av->max_carry_s__;
 345     if (max_carry < GNUNET_MAX_MESSAGE_SIZE)
 346       max_carry = GNUNET_MAX_MESSAGE_SIZE;
 347     if (max_carry > INT64_MAX)
 348       max_carry = INT64_MAX;
 349     if (max_carry > left_bytes)
 350       av->consumption_since_last_update__ = - left_bytes;
 351     else
 352       av->consumption_since_last_update__ = - max_carry;
 353   }
 354 #if !defined(GNUNET_CULL_LOGGING)
 355   {
 356     struct GNUNET_TIME_Relative delta;
 357
 358     delta.rel_value_us = delta_time;
 359     LOG (GNUNET_ERROR_TYPE_DEBUG,
 360          "Tracker %p updated, consumption at %lld at %u Bps, last update was %s ago\n",
 361          av,
 362          (long long) av->consumption_since_last_update__,
 363          (unsigned int) av->available_bytes_per_s__,
 364          GNUNET_STRINGS_relative_time_to_string (delta,
 365                                                  GNUNET_YES));
 366   }
 367 #endif
 368 }
 369
 370
 371 /**
 372  * Notify the tracker that a certain number of bytes of bandwidth have
 373  * been consumed.  Note that it is legal to consume bytes even if not
 374  * enough bandwidth is available (in that case,
 375  * #GNUNET_BANDWIDTH_tracker_get_delay may return non-zero delay values
 376  * even for a size of zero for a while).
 377  *
 378  * @param av tracker to update
 379  * @param size number of bytes consumed
 380  * @return #GNUNET_YES if this consumption is above the limit
 381  */
 382 int
 383 GNUNET_BANDWIDTH_tracker_consume (struct GNUNET_BANDWIDTH_Tracker *av,
 384                                   ssize_t size)
 385 {
 386   int64_t nc;
 387
 388   LOG (GNUNET_ERROR_TYPE_DEBUG,
 389        "Tracker %p consumes %d bytes\n",
 390        av,
 391        (int) size);
 392   if (size > 0)
 393   {
 394     nc = av->consumption_since_last_update__ + size;
 395     if (nc < av->consumption_since_last_update__)
 396     {
 397       /* integer overflow, very bad */
 398       GNUNET_break (0);
 399       return GNUNET_SYSERR;
 400     }
 401     av->consumption_since_last_update__ = nc;
 402     update_tracker (av);
 403     update_excess (av);
 404     if (av->consumption_since_last_update__ > 0)
 405     {
 406       LOG (GNUNET_ERROR_TYPE_DEBUG,
 407            "Tracker %p consumption %llu bytes above limit\n",
 408            av,
 409            (unsigned long long) av->consumption_since_last_update__);
 410       return GNUNET_YES;
 411     }
 412   }
 413   else
 414   {
 415     nc = av->consumption_since_last_update__ + size;
 416     if (nc > av->consumption_since_last_update__)
 417     {
 418       /* integer underflow, very bad */
 419       GNUNET_break (0);
 420       return GNUNET_SYSERR;
 421     }
 422     av->consumption_since_last_update__ = nc;
 423     update_excess (av);
 424   }
 425   return GNUNET_NO;
 426 }
 427
 428
 429 /**
 430  * Compute how long we should wait until consuming 'size'
 431  * bytes of bandwidth in order to stay within the given
 432  * quota.
 433  *
 434  * @param av tracker to query
 435  * @param size number of bytes we would like to consume
 436  * @return time in ms to wait for consumption to be OK
 437  */
 438 struct GNUNET_TIME_Relative
 439 GNUNET_BANDWIDTH_tracker_get_delay (struct GNUNET_BANDWIDTH_Tracker *av,
 440                                     size_t size)
 441 {
 442   struct GNUNET_TIME_Relative ret;
 443   int64_t bytes_needed;
 444
 445   if (0 == av->available_bytes_per_s__)
 446   {
 447     LOG (GNUNET_ERROR_TYPE_DEBUG,
 448          "Tracker %p delay is infinity\n", av);
 449     return GNUNET_TIME_UNIT_FOREVER_REL;
 450   }
 451   update_tracker (av);
 452   bytes_needed = size + av->consumption_since_last_update__;
 453   if (bytes_needed <= 0)
 454   {
 455     LOG (GNUNET_ERROR_TYPE_DEBUG,
 456          "Tracker %p delay for %u bytes is zero\n", av,
 457          (unsigned int) size);
 458     return GNUNET_TIME_UNIT_ZERO;
 459   }
 460   ret.rel_value_us =
 461       (1000LL * 1000LL * bytes_needed) /
 462       (unsigned long long) av->available_bytes_per_s__;
 463   LOG (GNUNET_ERROR_TYPE_DEBUG,
 464        "Tracker %p delay for %u bytes is %s\n",
 465        av,
 466        (unsigned int) size,
 467        GNUNET_STRINGS_relative_time_to_string (ret, GNUNET_YES));
 468   return ret;
 469 }
 470
 471
 472 /**
 473  * Compute how many bytes are available for consumption right now.
 474  * quota.
 475  *
 476  * @param av tracker to query
 477  * @return number of bytes available for consumption right now
 478  */
 479 int64_t
 480 GNUNET_BANDWIDTH_tracker_get_available (struct GNUNET_BANDWIDTH_Tracker *av)
 481 {
 482   struct GNUNET_BANDWIDTH_Value32NBO bps;
 483   uint64_t avail;
 484   int64_t used;
 485
 486   update_tracker (av);
 487   bps = GNUNET_BANDWIDTH_value_init (av->available_bytes_per_s__);
 488   avail =
 489       GNUNET_BANDWIDTH_value_get_available_until (bps,
 490                                                   GNUNET_TIME_absolute_get_duration
 491                                                   (av->last_update__));
 492   used = av->consumption_since_last_update__;
 493   LOG (GNUNET_ERROR_TYPE_DEBUG,
 494        "Tracker %p available bandwidth is %lld bytes\n", av,
 495        (long long) (int64_t) (avail - used));
 496   return (int64_t) (avail - used);
 497 }
 498
 499
 500 /**
 501  * Update quota of bandwidth tracker.
 502  *
 503  * @param av tracker to initialize
 504  * @param bytes_per_second_limit new limit to assume
 505  */
 506 void
 507 GNUNET_BANDWIDTH_tracker_update_quota (struct GNUNET_BANDWIDTH_Tracker *av,
 508                                        struct GNUNET_BANDWIDTH_Value32NBO bytes_per_second_limit)
 509 {
 510   uint32_t old_limit;
 511   uint32_t new_limit;
 512
 513   new_limit = ntohl (bytes_per_second_limit.value__);
 514   LOG (GNUNET_ERROR_TYPE_DEBUG,
 515        "Tracker %p bandwidth changed to %u Bps\n", av,
 516        (unsigned int) new_limit);
 517   update_tracker (av);
 518   old_limit = av->available_bytes_per_s__;
 519   av->available_bytes_per_s__ = new_limit;
 520   if (NULL != av->update_cb)
 521     av->update_cb (av->update_cb_cls);
 522   if (old_limit > new_limit)
 523     update_tracker (av);        /* maximum excess might be less now */
 524   update_excess (av);
 525 }
 526
 527
 528 /* end of bandwidth.c */