2 This file is part of GNUnet.
3 Copyright (C) 2010, 2013 GNUnet e.V.
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.
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.
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/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
22 * @file util/bandwidth.c
23 * @brief functions related to bandwidth (unit)
24 * @author Christian Grothoff
27 #include "gnunet_util_lib.h"
30 #define LOG(kind, ...) GNUNET_log_from (kind, "util-bandwidth", __VA_ARGS__)
33 * Create a new bandwidth value.
35 * @param bytes_per_second value to create
36 * @return the new bandwidth value
38 struct GNUNET_BANDWIDTH_Value32NBO
39 GNUNET_BANDWIDTH_value_init (uint32_t bytes_per_second)
41 struct GNUNET_BANDWIDTH_Value32NBO ret;
43 ret.value__ = htonl (bytes_per_second);
49 * Compute the MIN of two bandwidth values.
51 * @param b1 first value
52 * @param b2 second value
53 * @return the min of b1 and b2
55 struct GNUNET_BANDWIDTH_Value32NBO
56 GNUNET_BANDWIDTH_value_min (struct GNUNET_BANDWIDTH_Value32NBO b1,
57 struct GNUNET_BANDWIDTH_Value32NBO b2)
59 return GNUNET_BANDWIDTH_value_init (
60 GNUNET_MIN (ntohl (b1.value__), ntohl (b2.value__)));
65 * Compute the MAX of two bandwidth values.
67 * @param b1 first value
68 * @param b2 second value
69 * @return the min of b1 and b2
71 struct GNUNET_BANDWIDTH_Value32NBO
72 GNUNET_BANDWIDTH_value_max (struct GNUNET_BANDWIDTH_Value32NBO b1,
73 struct GNUNET_BANDWIDTH_Value32NBO b2)
75 return GNUNET_BANDWIDTH_value_init (
76 GNUNET_MAX (ntohl (b1.value__), ntohl (b2.value__)));
81 * Compute the SUM of two bandwidth values.
83 * @param b1 first value
84 * @param b2 second value
85 * @return the sum of b1 and b2
87 struct GNUNET_BANDWIDTH_Value32NBO
88 GNUNET_BANDWIDTH_value_sum (struct GNUNET_BANDWIDTH_Value32NBO b1,
89 struct GNUNET_BANDWIDTH_Value32NBO b2)
91 return GNUNET_BANDWIDTH_value_init (ntohl (b1.value__) + ntohl (b2.value__));
96 * At the given bandwidth, calculate how much traffic will be
97 * available until the given deadline.
99 * @param bps bandwidth
100 * @param deadline when is the deadline
101 * @return number of bytes available at bps until deadline
104 GNUNET_BANDWIDTH_value_get_available_until (
105 struct GNUNET_BANDWIDTH_Value32NBO bps,
106 struct GNUNET_TIME_Relative deadline)
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)
115 GNUNET_STRINGS_relative_time_to_string (deadline, GNUNET_YES));
116 return (b * deadline.rel_value_us + 500000LL) / 1000000LL;
121 * At the given bandwidth, calculate how long it would take for
122 * @a size bytes to be transmitted.
124 * @param bps bandwidth
125 * @param size number of bytes we want to have available
126 * @return how long it would take
128 struct GNUNET_TIME_Relative
129 GNUNET_BANDWIDTH_value_get_delay_for (struct GNUNET_BANDWIDTH_Value32NBO bps,
133 struct GNUNET_TIME_Relative ret;
135 b = ntohl (bps.value__);
138 LOG (GNUNET_ERROR_TYPE_DEBUG,
139 "Bandwidth suggests delay of infinity (zero bandwidth)\n");
140 return GNUNET_TIME_UNIT_FOREVER_REL;
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);
152 * Task run whenever we hit the bandwidth limit for a tracker.
154 * @param cls the `struct GNUNET_BANDWIDTH_Tracker`
157 excess_trigger (void *cls)
159 struct GNUNET_BANDWIDTH_Tracker *av = cls;
161 av->excess_task = NULL;
162 if (NULL != av->excess_cb)
164 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
165 "Notifying application about excess bandwidth\n");
166 av->excess_cb (av->excess_cb_cls);
172 * Recalculate when we might need to call the excess callback.
175 update_excess (struct GNUNET_BANDWIDTH_Tracker *av)
177 struct GNUNET_TIME_Relative delay;
178 struct GNUNET_TIME_Absolute now;
180 uint64_t delta_avail;
183 int64_t current_consumption;
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;
190 (delta_time * ((unsigned long long) av->available_bytes_per_s__)
193 current_consumption = av->consumption_since_last_update__ - delta_avail;
194 if (current_consumption > av->consumption_since_last_update__)
196 /* integer underflow, cap! */
197 current_consumption = INT64_MIN;
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)
208 /* integer overflow, cap! */
209 left_bytes = INT64_MAX;
211 /* left_bytes now contains the number of bytes needed until
212 we have more savings than allowed */
215 /* having excess already */
216 delay = GNUNET_TIME_UNIT_ZERO;
220 double factor = 1.0 * left_bytes / (double) av->available_bytes_per_s__;
222 GNUNET_TIME_relative_saturating_multiply (GNUNET_TIME_UNIT_SECONDS,
223 (unsigned long long) factor);
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);
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
246 * To stop notifications about updates and excess callbacks use
247 * #GNUNET_BANDWIDTH_tracker_notification_stop().
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
259 GNUNET_BANDWIDTH_tracker_init2 (
260 struct GNUNET_BANDWIDTH_Tracker *av,
261 GNUNET_BANDWIDTH_TrackerUpdateCallback update_cb,
263 struct GNUNET_BANDWIDTH_Value32NBO bytes_per_second_limit,
264 uint32_t max_carry_s,
265 GNUNET_BANDWIDTH_ExcessNotificationCallback excess_cb,
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",
279 (unsigned int) av->available_bytes_per_s__,
280 (unsigned int) max_carry_s);
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
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
302 GNUNET_BANDWIDTH_tracker_init (
303 struct GNUNET_BANDWIDTH_Tracker *av,
304 GNUNET_BANDWIDTH_TrackerUpdateCallback update_cb,
306 struct GNUNET_BANDWIDTH_Value32NBO bytes_per_second_limit,
307 uint32_t max_carry_s)
309 GNUNET_BANDWIDTH_tracker_init2 (av,
312 bytes_per_second_limit,
320 * Stop notifying about tracker updates and excess notifications
322 * @param av the respective trackers
325 GNUNET_BANDWIDTH_tracker_notification_stop (struct GNUNET_BANDWIDTH_Tracker *av)
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;
338 * Update the tracker, looking at the current time and
339 * bandwidth consumption data.
341 * @param av tracker to update
344 update_tracker (struct GNUNET_BANDWIDTH_Tracker *av)
346 struct GNUNET_TIME_Absolute now;
348 uint64_t delta_avail;
352 now = GNUNET_TIME_absolute_get ();
353 delta_time = now.abs_value_us - av->last_update__.abs_value_us;
355 (delta_time * ((unsigned long long) av->available_bytes_per_s__)
358 av->consumption_since_last_update__ -= delta_avail;
359 av->last_update__ = now;
360 if (av->consumption_since_last_update__ < 0)
362 left_bytes = -av->consumption_since_last_update__;
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;
372 av->consumption_since_last_update__ = -max_carry;
374 #if ! defined(GNUNET_CULL_LOGGING)
376 struct GNUNET_TIME_Relative delta;
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",
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));
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).
397 * @param av tracker to update
398 * @param size number of bytes consumed
399 * @return #GNUNET_YES if this consumption is above the limit
402 GNUNET_BANDWIDTH_tracker_consume (struct GNUNET_BANDWIDTH_Tracker *av,
407 LOG (GNUNET_ERROR_TYPE_DEBUG,
408 "Tracker %p consumes %d bytes\n",
413 nc = av->consumption_since_last_update__ + size;
414 if (nc < av->consumption_since_last_update__)
416 /* integer overflow, very bad */
418 return GNUNET_SYSERR;
420 av->consumption_since_last_update__ = nc;
423 if (av->consumption_since_last_update__ > 0)
425 LOG (GNUNET_ERROR_TYPE_DEBUG,
426 "Tracker %p consumption %llu bytes above limit\n",
428 (unsigned long long) av->consumption_since_last_update__);
434 nc = av->consumption_since_last_update__ + size;
435 if (nc > av->consumption_since_last_update__)
437 /* integer underflow, very bad */
439 return GNUNET_SYSERR;
441 av->consumption_since_last_update__ = nc;
449 * Compute how long we should wait until consuming 'size'
450 * bytes of bandwidth in order to stay within the given
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
457 struct GNUNET_TIME_Relative
458 GNUNET_BANDWIDTH_tracker_get_delay (struct GNUNET_BANDWIDTH_Tracker *av,
461 struct GNUNET_TIME_Relative ret;
462 int64_t bytes_needed;
464 if (0 == av->available_bytes_per_s__)
466 LOG (GNUNET_ERROR_TYPE_DEBUG, "Tracker %p delay is infinity\n", av);
467 return GNUNET_TIME_UNIT_FOREVER_REL;
470 bytes_needed = size + av->consumption_since_last_update__;
471 if (bytes_needed <= 0)
473 LOG (GNUNET_ERROR_TYPE_DEBUG,
474 "Tracker %p delay for %u bytes is zero\n",
476 (unsigned int) size);
477 return GNUNET_TIME_UNIT_ZERO;
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",
485 GNUNET_STRINGS_relative_time_to_string (ret, GNUNET_YES));
491 * Compute how many bytes are available for consumption right now.
494 * @param av tracker to query
495 * @return number of bytes available for consumption right now
498 GNUNET_BANDWIDTH_tracker_get_available (struct GNUNET_BANDWIDTH_Tracker *av)
500 struct GNUNET_BANDWIDTH_Value32NBO bps;
505 bps = GNUNET_BANDWIDTH_value_init (av->available_bytes_per_s__);
507 GNUNET_BANDWIDTH_value_get_available_until (bps,
508 GNUNET_TIME_absolute_get_duration (
510 used = av->consumption_since_last_update__;
511 LOG (GNUNET_ERROR_TYPE_DEBUG,
512 "Tracker %p available bandwidth is %lld bytes\n",
514 (long long) (int64_t) (avail - used));
515 return (int64_t) (avail - used);
520 * Update quota of bandwidth tracker.
522 * @param av tracker to initialize
523 * @param bytes_per_second_limit new limit to assume
526 GNUNET_BANDWIDTH_tracker_update_quota (
527 struct GNUNET_BANDWIDTH_Tracker *av,
528 struct GNUNET_BANDWIDTH_Value32NBO bytes_per_second_limit)
533 new_limit = ntohl (bytes_per_second_limit.value__);
534 LOG (GNUNET_ERROR_TYPE_DEBUG,
535 "Tracker %p bandwidth changed to %u Bps\n",
537 (unsigned int) new_limit);
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 */
549 /* end of bandwidth.c */