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.
17 * @file util/bandwidth.c
18 * @brief functions related to bandwidth (unit)
19 * @author Christian Grothoff
22 #include "gnunet_util_lib.h"
25 #define LOG(kind,...) GNUNET_log_from (kind, "util-bandwidth", __VA_ARGS__)
28 * Create a new bandwidth value.
30 * @param bytes_per_second value to create
31 * @return the new bandwidth value
33 struct GNUNET_BANDWIDTH_Value32NBO
34 GNUNET_BANDWIDTH_value_init (uint32_t bytes_per_second)
36 struct GNUNET_BANDWIDTH_Value32NBO ret;
38 ret.value__ = htonl (bytes_per_second);
44 * Compute the MIN of two bandwidth values.
46 * @param b1 first value
47 * @param b2 second value
48 * @return the min of b1 and b2
50 struct GNUNET_BANDWIDTH_Value32NBO
51 GNUNET_BANDWIDTH_value_min (struct GNUNET_BANDWIDTH_Value32NBO b1,
52 struct GNUNET_BANDWIDTH_Value32NBO b2)
55 GNUNET_BANDWIDTH_value_init (GNUNET_MIN
62 * Compute the MAX of two bandwidth values.
64 * @param b1 first value
65 * @param b2 second value
66 * @return the min of b1 and b2
68 struct GNUNET_BANDWIDTH_Value32NBO
69 GNUNET_BANDWIDTH_value_max (struct GNUNET_BANDWIDTH_Value32NBO b1,
70 struct GNUNET_BANDWIDTH_Value32NBO b2)
73 GNUNET_BANDWIDTH_value_init (GNUNET_MAX
80 * At the given bandwidth, calculate how much traffic will be
81 * available until the given deadline.
83 * @param bps bandwidth
84 * @param deadline when is the deadline
85 * @return number of bytes available at bps until deadline
88 GNUNET_BANDWIDTH_value_get_available_until (struct GNUNET_BANDWIDTH_Value32NBO bps,
89 struct GNUNET_TIME_Relative deadline)
93 b = ntohl (bps.value__);
94 LOG (GNUNET_ERROR_TYPE_DEBUG,
95 "Bandwidth has %llu bytes available until deadline in %s\n",
96 (unsigned long long) ((b * deadline.rel_value_us + 500000LL) / 1000000LL),
97 GNUNET_STRINGS_relative_time_to_string (deadline, GNUNET_YES));
98 return (b * deadline.rel_value_us + 500000LL) / 1000000LL;
103 * At the given bandwidth, calculate how long it would take for
104 * @a size bytes to be transmitted.
106 * @param bps bandwidth
107 * @param size number of bytes we want to have available
108 * @return how long it would take
110 struct GNUNET_TIME_Relative
111 GNUNET_BANDWIDTH_value_get_delay_for (struct GNUNET_BANDWIDTH_Value32NBO bps,
115 struct GNUNET_TIME_Relative ret;
117 b = ntohl (bps.value__);
120 LOG (GNUNET_ERROR_TYPE_DEBUG,
121 "Bandwidth suggests delay of infinity (zero bandwidth)\n");
122 return GNUNET_TIME_UNIT_FOREVER_REL;
124 ret.rel_value_us = size * 1000LL * 1000LL / b;
125 LOG (GNUNET_ERROR_TYPE_DEBUG,
126 "Bandwidth suggests delay of %s for %llu bytes of traffic\n",
127 GNUNET_STRINGS_relative_time_to_string (ret, GNUNET_YES),
128 (unsigned long long) size);
134 * Task run whenever we hit the bandwidth limit for a tracker.
136 * @param cls the `struct GNUNET_BANDWIDTH_Tracker`
139 excess_trigger (void *cls)
141 struct GNUNET_BANDWIDTH_Tracker *av = cls;
143 av->excess_task = NULL;
144 if (NULL != av->excess_cb)
146 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
147 "Notifying application about excess bandwidth\n");
148 av->excess_cb (av->excess_cb_cls);
154 * Recalculate when we might need to call the excess callback.
157 update_excess (struct GNUNET_BANDWIDTH_Tracker *av)
159 struct GNUNET_TIME_Relative delay;
160 struct GNUNET_TIME_Absolute now;
162 uint64_t delta_avail;
165 int64_t current_consumption;
167 if (NULL == av->excess_cb)
168 return; /* nothing to do */
169 now = GNUNET_TIME_absolute_get ();
170 delta_time = now.abs_value_us - av->last_update__.abs_value_us;
172 (delta_time * ((unsigned long long) av->available_bytes_per_s__) +
173 500000LL) / 1000000LL;
174 current_consumption = av->consumption_since_last_update__ - delta_avail;
175 if (current_consumption > av->consumption_since_last_update__)
177 /* integer underflow, cap! */
178 current_consumption = INT64_MIN;
180 /* negative current_consumption means that we have savings */
181 max_carry = ((uint64_t) av->available_bytes_per_s__) * av->max_carry_s__;
182 if (max_carry < GNUNET_MAX_MESSAGE_SIZE)
183 max_carry = GNUNET_MAX_MESSAGE_SIZE;
184 if (max_carry > INT64_MAX)
185 max_carry = INT64_MAX;
186 left_bytes = current_consumption + max_carry;
187 if (left_bytes < current_consumption)
189 /* integer overflow, cap! */
190 left_bytes = INT64_MAX;
192 /* left_bytes now contains the number of bytes needed until
193 we have more savings than allowed */
196 /* having excess already */
197 delay = GNUNET_TIME_UNIT_ZERO;
201 double factor = 1.0 * left_bytes / (double) av->available_bytes_per_s__;
202 delay = GNUNET_TIME_relative_saturating_multiply (GNUNET_TIME_UNIT_SECONDS,
203 (unsigned long long) factor);
205 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
206 "At %llu bps it will take us %s for %lld bytes to reach excess threshold\n",
207 (unsigned long long) av->available_bytes_per_s__,
208 GNUNET_STRINGS_relative_time_to_string (delay,
210 (long long) left_bytes);
211 if (NULL != av->excess_task)
212 GNUNET_SCHEDULER_cancel (av->excess_task);
213 av->excess_task = GNUNET_SCHEDULER_add_delayed (delay,
220 * Initialize bandwidth tracker. Note that in addition to the
221 * 'max_carry_s' limit, we also always allow at least
222 * #GNUNET_MAX_MESSAGE_SIZE to accumulate. So if the
223 * bytes-per-second limit is so small that within 'max_carry_s' not
224 * even #GNUNET_MAX_MESSAGE_SIZE is allowed to accumulate, it is
225 * ignored and replaced by #GNUNET_MAX_MESSAGE_SIZE (which is in
228 * To stop notifications about updates and excess callbacks use
229 * #GNUNET_BANDWIDTH_tracker_notification_stop().
231 * @param av tracker to initialize
232 * @param update_cb callback to notify a client about the tracker being updated
233 * @param update_cb_cls cls for the callback
234 * @param bytes_per_second_limit initial limit to assume
235 * @param max_carry_s maximum number of seconds unused bandwidth
236 * may accumulate before it expires
237 * @param excess_cb callback to notify if we have excess bandwidth
238 * @param excess_cb_cls closure for @a excess_cb
241 GNUNET_BANDWIDTH_tracker_init2 (struct GNUNET_BANDWIDTH_Tracker *av,
242 GNUNET_BANDWIDTH_TrackerUpdateCallback update_cb,
244 struct GNUNET_BANDWIDTH_Value32NBO bytes_per_second_limit,
245 uint32_t max_carry_s,
246 GNUNET_BANDWIDTH_ExcessNotificationCallback excess_cb,
249 av->update_cb = update_cb;
250 av->update_cb_cls = update_cb_cls;
251 av->consumption_since_last_update__ = 0;
252 av->last_update__ = GNUNET_TIME_absolute_get ();
253 av->available_bytes_per_s__ = ntohl (bytes_per_second_limit.value__);
254 av->max_carry_s__ = max_carry_s;
255 av->excess_cb = excess_cb;
256 av->excess_cb_cls = excess_cb_cls;
257 LOG (GNUNET_ERROR_TYPE_DEBUG,
258 "Tracker %p initialized with %u Bps and max carry %u\n",
260 (unsigned int) av->available_bytes_per_s__,
261 (unsigned int) max_carry_s);
267 * Initialize bandwidth tracker. Note that in addition to the
268 * 'max_carry_s' limit, we also always allow at least
269 * #GNUNET_MAX_MESSAGE_SIZE to accumulate. So if the
270 * bytes-per-second limit is so small that within 'max_carry_s' not
271 * even #GNUNET_MAX_MESSAGE_SIZE is allowed to accumulate, it is
272 * ignored and replaced by #GNUNET_MAX_MESSAGE_SIZE (which is in
275 * @param av tracker to initialize
276 * @param update_cb callback to notify a client about the tracker being updated
277 * @param update_cb_cls cls for the callback
278 * @param bytes_per_second_limit initial limit to assume
279 * @param max_carry_s maximum number of seconds unused bandwidth
280 * may accumulate before it expires
283 GNUNET_BANDWIDTH_tracker_init (struct GNUNET_BANDWIDTH_Tracker *av,
284 GNUNET_BANDWIDTH_TrackerUpdateCallback update_cb,
286 struct GNUNET_BANDWIDTH_Value32NBO bytes_per_second_limit,
287 uint32_t max_carry_s)
289 GNUNET_BANDWIDTH_tracker_init2 (av, update_cb,
291 bytes_per_second_limit,
298 * Stop notifying about tracker updates and excess notifications
300 * @param av the respective trackers
303 GNUNET_BANDWIDTH_tracker_notification_stop (struct GNUNET_BANDWIDTH_Tracker *av)
305 if (NULL != av->excess_task)
306 GNUNET_SCHEDULER_cancel (av->excess_task);
307 av->excess_task = NULL;
308 av->excess_cb = NULL;
309 av->excess_cb_cls = NULL;
310 av->update_cb = NULL;
311 av->update_cb_cls = NULL;
316 * Update the tracker, looking at the current time and
317 * bandwidth consumption data.
319 * @param av tracker to update
322 update_tracker (struct GNUNET_BANDWIDTH_Tracker *av)
324 struct GNUNET_TIME_Absolute now;
326 uint64_t delta_avail;
330 now = GNUNET_TIME_absolute_get ();
331 delta_time = now.abs_value_us - av->last_update__.abs_value_us;
333 (delta_time * ((unsigned long long) av->available_bytes_per_s__) +
334 500000LL) / 1000000LL;
335 av->consumption_since_last_update__ -= delta_avail;
336 av->last_update__ = now;
337 if (av->consumption_since_last_update__ < 0)
339 left_bytes = - av->consumption_since_last_update__;
340 max_carry = ((unsigned long long) av->available_bytes_per_s__) *
342 if (max_carry < GNUNET_MAX_MESSAGE_SIZE)
343 max_carry = GNUNET_MAX_MESSAGE_SIZE;
344 if (max_carry > INT64_MAX)
345 max_carry = INT64_MAX;
346 if (max_carry > left_bytes)
347 av->consumption_since_last_update__ = - left_bytes;
349 av->consumption_since_last_update__ = - max_carry;
351 #if !defined(GNUNET_CULL_LOGGING)
353 struct GNUNET_TIME_Relative delta;
355 delta.rel_value_us = delta_time;
356 LOG (GNUNET_ERROR_TYPE_DEBUG,
357 "Tracker %p updated, consumption at %lld at %u Bps, last update was %s ago\n",
359 (long long) av->consumption_since_last_update__,
360 (unsigned int) av->available_bytes_per_s__,
361 GNUNET_STRINGS_relative_time_to_string (delta,
369 * Notify the tracker that a certain number of bytes of bandwidth have
370 * been consumed. Note that it is legal to consume bytes even if not
371 * enough bandwidth is available (in that case,
372 * #GNUNET_BANDWIDTH_tracker_get_delay may return non-zero delay values
373 * even for a size of zero for a while).
375 * @param av tracker to update
376 * @param size number of bytes consumed
377 * @return #GNUNET_YES if this consumption is above the limit
380 GNUNET_BANDWIDTH_tracker_consume (struct GNUNET_BANDWIDTH_Tracker *av,
385 LOG (GNUNET_ERROR_TYPE_DEBUG,
386 "Tracker %p consumes %d bytes\n",
391 nc = av->consumption_since_last_update__ + size;
392 if (nc < av->consumption_since_last_update__)
394 /* integer overflow, very bad */
396 return GNUNET_SYSERR;
398 av->consumption_since_last_update__ = nc;
401 if (av->consumption_since_last_update__ > 0)
403 LOG (GNUNET_ERROR_TYPE_DEBUG,
404 "Tracker %p consumption %llu bytes above limit\n",
406 (unsigned long long) av->consumption_since_last_update__);
412 nc = av->consumption_since_last_update__ + size;
413 if (nc > av->consumption_since_last_update__)
415 /* integer underflow, very bad */
417 return GNUNET_SYSERR;
419 av->consumption_since_last_update__ = nc;
427 * Compute how long we should wait until consuming 'size'
428 * bytes of bandwidth in order to stay within the given
431 * @param av tracker to query
432 * @param size number of bytes we would like to consume
433 * @return time in ms to wait for consumption to be OK
435 struct GNUNET_TIME_Relative
436 GNUNET_BANDWIDTH_tracker_get_delay (struct GNUNET_BANDWIDTH_Tracker *av,
439 struct GNUNET_TIME_Relative ret;
440 int64_t bytes_needed;
442 if (0 == av->available_bytes_per_s__)
444 LOG (GNUNET_ERROR_TYPE_DEBUG,
445 "Tracker %p delay is infinity\n", av);
446 return GNUNET_TIME_UNIT_FOREVER_REL;
449 bytes_needed = size + av->consumption_since_last_update__;
450 if (bytes_needed <= 0)
452 LOG (GNUNET_ERROR_TYPE_DEBUG,
453 "Tracker %p delay for %u bytes is zero\n", av,
454 (unsigned int) size);
455 return GNUNET_TIME_UNIT_ZERO;
458 (1000LL * 1000LL * bytes_needed) /
459 (unsigned long long) av->available_bytes_per_s__;
460 LOG (GNUNET_ERROR_TYPE_DEBUG,
461 "Tracker %p delay for %u bytes is %s\n",
464 GNUNET_STRINGS_relative_time_to_string (ret, GNUNET_YES));
470 * Compute how many bytes are available for consumption right now.
473 * @param av tracker to query
474 * @return number of bytes available for consumption right now
477 GNUNET_BANDWIDTH_tracker_get_available (struct GNUNET_BANDWIDTH_Tracker *av)
479 struct GNUNET_BANDWIDTH_Value32NBO bps;
484 bps = GNUNET_BANDWIDTH_value_init (av->available_bytes_per_s__);
486 GNUNET_BANDWIDTH_value_get_available_until (bps,
487 GNUNET_TIME_absolute_get_duration
488 (av->last_update__));
489 used = av->consumption_since_last_update__;
490 LOG (GNUNET_ERROR_TYPE_DEBUG,
491 "Tracker %p available bandwidth is %lld bytes\n", av,
492 (long long) (int64_t) (avail - used));
493 return (int64_t) (avail - used);
498 * Update quota of bandwidth tracker.
500 * @param av tracker to initialize
501 * @param bytes_per_second_limit new limit to assume
504 GNUNET_BANDWIDTH_tracker_update_quota (struct GNUNET_BANDWIDTH_Tracker *av,
505 struct GNUNET_BANDWIDTH_Value32NBO bytes_per_second_limit)
510 new_limit = ntohl (bytes_per_second_limit.value__);
511 LOG (GNUNET_ERROR_TYPE_DEBUG,
512 "Tracker %p bandwidth changed to %u Bps\n", av,
513 (unsigned int) new_limit);
515 old_limit = av->available_bytes_per_s__;
516 av->available_bytes_per_s__ = new_limit;
517 if (NULL != av->update_cb)
518 av->update_cb (av->update_cb_cls);
519 if (old_limit > new_limit)
520 update_tracker (av); /* maximum excess might be less now */
525 /* end of bandwidth.c */