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