aboutsummaryrefslogtreecommitdiff
path: root/src/util/bandwidth.c
blob: a059fc73808d517e0955b325d48e35b4bb1fd647 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
/*
     This file is part of GNUnet.
     Copyright (C) 2010, 2013 GNUnet e.V.

     GNUnet is free software; you can redistribute it and/or modify
     it under the terms of the GNU General Public License as published
     by the Free Software Foundation; either version 3, or (at your
     option) any later version.

     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     General Public License for more details.

     You should have received a copy of the GNU General Public License
     along with GNUnet; see the file COPYING.  If not, write to the
     Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
     Boston, MA 02110-1301, USA.
*/

/**
 * @file util/bandwidth.c
 * @brief functions related to bandwidth (unit)
 * @author Christian Grothoff
 */
#include "platform.h"
#include "gnunet_util_lib.h"


#define LOG(kind,...) GNUNET_log_from (kind, "util-bandwidth", __VA_ARGS__)

/**
 * Create a new bandwidth value.
 *
 * @param bytes_per_second value to create
 * @return the new bandwidth value
 */
struct GNUNET_BANDWIDTH_Value32NBO
GNUNET_BANDWIDTH_value_init (uint32_t bytes_per_second)
{
  struct GNUNET_BANDWIDTH_Value32NBO ret;

  ret.value__ = htonl (bytes_per_second);
  return ret;
}


/**
 * Compute the MIN of two bandwidth values.
 *
 * @param b1 first value
 * @param b2 second value
 * @return the min of b1 and b2
 */
struct GNUNET_BANDWIDTH_Value32NBO
GNUNET_BANDWIDTH_value_min (struct GNUNET_BANDWIDTH_Value32NBO b1,
                            struct GNUNET_BANDWIDTH_Value32NBO b2)
{
  return
      GNUNET_BANDWIDTH_value_init (GNUNET_MIN
                                   (ntohl (b1.value__),
                                    ntohl (b2.value__)));
}


/**
 * Compute the MAX of two bandwidth values.
 *
 * @param b1 first value
 * @param b2 second value
 * @return the min of b1 and b2
 */
struct GNUNET_BANDWIDTH_Value32NBO
GNUNET_BANDWIDTH_value_max (struct GNUNET_BANDWIDTH_Value32NBO b1,
                            struct GNUNET_BANDWIDTH_Value32NBO b2)
{
  return
      GNUNET_BANDWIDTH_value_init (GNUNET_MAX
                                   (ntohl (b1.value__),
                                    ntohl (b2.value__)));
}


/**
 * At the given bandwidth, calculate how much traffic will be
 * available until the given deadline.
 *
 * @param bps bandwidth
 * @param deadline when is the deadline
 * @return number of bytes available at bps until deadline
 */
uint64_t
GNUNET_BANDWIDTH_value_get_available_until (struct GNUNET_BANDWIDTH_Value32NBO bps,
                                            struct GNUNET_TIME_Relative deadline)
{
  uint64_t b;

  b = ntohl (bps.value__);
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Bandwidth has %llu bytes available until deadline in %s\n",
       (unsigned long long) ((b * deadline.rel_value_us + 500000LL) / 1000000LL),
       GNUNET_STRINGS_relative_time_to_string (deadline, GNUNET_YES));
  return (b * deadline.rel_value_us + 500000LL) / 1000000LL;
}


/**
 * At the given bandwidth, calculate how long it would take for
 * @a size bytes to be transmitted.
 *
 * @param bps bandwidth
 * @param size number of bytes we want to have available
 * @return how long it would take
 */
struct GNUNET_TIME_Relative
GNUNET_BANDWIDTH_value_get_delay_for (struct GNUNET_BANDWIDTH_Value32NBO bps,
                                      uint64_t size)
{
  uint64_t b;
  struct GNUNET_TIME_Relative ret;

  b = ntohl (bps.value__);
  if (0 == b)
  {
    LOG (GNUNET_ERROR_TYPE_DEBUG,
         "Bandwidth suggests delay of infinity (zero bandwidth)\n");
    return GNUNET_TIME_UNIT_FOREVER_REL;
  }
  ret.rel_value_us = size * 1000LL * 1000LL / b;
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Bandwidth suggests delay of %s for %llu bytes of traffic\n",
       GNUNET_STRINGS_relative_time_to_string (ret, GNUNET_YES),
       (unsigned long long) size);
  return ret;
}


/**
 * Task run whenever we hit the bandwidth limit for a tracker.
 *
 * @param cls the `struct GNUNET_BANDWIDTH_Tracker`
 */
static void
excess_trigger (void *cls)
{
  struct GNUNET_BANDWIDTH_Tracker *av = cls;

  av->excess_task = NULL;
  if (NULL != av->excess_cb)
  {
    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
		"Notifying application about excess bandwidth\n");
    av->excess_cb (av->excess_cb_cls);
  }
}


/**
 * Recalculate when we might need to call the excess callback.
 */
static void
update_excess (struct GNUNET_BANDWIDTH_Tracker *av)
{
  struct GNUNET_TIME_Relative delay;
  struct GNUNET_TIME_Absolute now;
  uint64_t delta_time;
  uint64_t delta_avail;
  int64_t left_bytes;
  uint64_t max_carry;
  int64_t current_consumption;

  if (NULL == av->excess_cb)
    return; /* nothing to do */
  now = GNUNET_TIME_absolute_get ();
  delta_time = now.abs_value_us - av->last_update__.abs_value_us;
  delta_avail =
      (delta_time * ((unsigned long long) av->available_bytes_per_s__) +
       500000LL) / 1000000LL;
  current_consumption = av->consumption_since_last_update__ - delta_avail;
  if (current_consumption > av->consumption_since_last_update__)
  {
    /* integer underflow, cap! */
    current_consumption = INT64_MIN;
  }
  /* negative current_consumption means that we have savings */
  max_carry = ((uint64_t) av->available_bytes_per_s__) * av->max_carry_s__;
  if (max_carry < GNUNET_SERVER_MAX_MESSAGE_SIZE)
    max_carry = GNUNET_SERVER_MAX_MESSAGE_SIZE;
  if (max_carry > INT64_MAX)
    max_carry = INT64_MAX;
  left_bytes = current_consumption + max_carry;
  if (left_bytes < current_consumption)
  {
    /* integer overflow, cap! */
    left_bytes = INT64_MAX;
  }
  /* left_bytes now contains the number of bytes needed until
     we have more savings than allowed */
  if (left_bytes < 0)
  {
    /* having excess already */
    delay = GNUNET_TIME_UNIT_ZERO;
  }
  else
  {
    double factor = 1.0 * left_bytes / (double) av->available_bytes_per_s__; 
    delay = GNUNET_TIME_relative_saturating_multiply (GNUNET_TIME_UNIT_SECONDS,
                                                      (unsigned long long) factor);
  }
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
	      "At %llu bps it will take us %s for %lld bytes to reach excess threshold\n",
	      (unsigned long long) av->available_bytes_per_s__,
	      GNUNET_STRINGS_relative_time_to_string (delay,
						      GNUNET_NO),
	      (long long) left_bytes);
  if (NULL != av->excess_task)
    GNUNET_SCHEDULER_cancel (av->excess_task);
  av->excess_task = GNUNET_SCHEDULER_add_delayed (delay,
                                                  &excess_trigger,
                                                  av);
}


/**
 * Initialize bandwidth tracker.  Note that in addition to the
 * 'max_carry_s' limit, we also always allow at least
 * #GNUNET_SERVER_MAX_MESSAGE_SIZE to accumulate.  So if the
 * bytes-per-second limit is so small that within 'max_carry_s' not
 * even #GNUNET_SERVER_MAX_MESSAGE_SIZE is allowed to accumulate, it is
 * ignored and replaced by #GNUNET_SERVER_MAX_MESSAGE_SIZE (which is in
 * bytes).
 *
 * To stop notifications about updates and excess callbacks use
 * #GNUNET_BANDWIDTH_tracker_notification_stop().
 *
 * @param av tracker to initialize
 * @param update_cb callback to notify a client about the tracker being updated
 * @param update_cb_cls cls for the callback
 * @param bytes_per_second_limit initial limit to assume
 * @param max_carry_s maximum number of seconds unused bandwidth
 *        may accumulate before it expires
 * @param excess_cb callback to notify if we have excess bandwidth
 * @param excess_cb_cls closure for @a excess_cb
 */
void
GNUNET_BANDWIDTH_tracker_init2 (struct GNUNET_BANDWIDTH_Tracker *av,
                                GNUNET_BANDWIDTH_TrackerUpdateCallback update_cb,
                                void *update_cb_cls,
                                struct GNUNET_BANDWIDTH_Value32NBO bytes_per_second_limit,
                                uint32_t max_carry_s,
                                GNUNET_BANDWIDTH_ExcessNotificationCallback excess_cb,
                                void *excess_cb_cls)
{
  av->update_cb = update_cb;
  av->update_cb_cls = update_cb_cls;
  av->consumption_since_last_update__ = 0;
  av->last_update__ = GNUNET_TIME_absolute_get ();
  av->available_bytes_per_s__ = ntohl (bytes_per_second_limit.value__);
  av->max_carry_s__ = max_carry_s;
  av->excess_cb = excess_cb;
  av->excess_cb_cls = excess_cb_cls;
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Tracker %p initialized with %u Bps and max carry %u\n",
       av,
       (unsigned int) av->available_bytes_per_s__,
       (unsigned int) max_carry_s);
  update_excess (av);
}


/**
 * Initialize bandwidth tracker.  Note that in addition to the
 * 'max_carry_s' limit, we also always allow at least
 * #GNUNET_SERVER_MAX_MESSAGE_SIZE to accumulate.  So if the
 * bytes-per-second limit is so small that within 'max_carry_s' not
 * even #GNUNET_SERVER_MAX_MESSAGE_SIZE is allowed to accumulate, it is
 * ignored and replaced by #GNUNET_SERVER_MAX_MESSAGE_SIZE (which is in
 * bytes).
 *
 * @param av tracker to initialize
 * @param update_cb callback to notify a client about the tracker being updated
 * @param update_cb_cls cls for the callback
 * @param bytes_per_second_limit initial limit to assume
 * @param max_carry_s maximum number of seconds unused bandwidth
 *        may accumulate before it expires
 */
void
GNUNET_BANDWIDTH_tracker_init (struct GNUNET_BANDWIDTH_Tracker *av,
                               GNUNET_BANDWIDTH_TrackerUpdateCallback update_cb,
                               void *update_cb_cls,
                               struct GNUNET_BANDWIDTH_Value32NBO bytes_per_second_limit,
                               uint32_t max_carry_s)
{
  GNUNET_BANDWIDTH_tracker_init2 (av, update_cb,
                                  update_cb_cls,
                                  bytes_per_second_limit,
                                  max_carry_s,
                                  NULL, NULL);
}


/**
 * Stop notifying about tracker updates and excess notifications
 *
 * @param av the respective trackers
 */
void
GNUNET_BANDWIDTH_tracker_notification_stop (struct GNUNET_BANDWIDTH_Tracker *av)
{
  if (NULL != av->excess_task)
    GNUNET_SCHEDULER_cancel (av->excess_task);
  av->excess_task = NULL;
  av->excess_cb = NULL;
  av->excess_cb_cls = NULL;
  av->update_cb = NULL;
  av->update_cb_cls = NULL;
}


/**
 * Update the tracker, looking at the current time and
 * bandwidth consumption data.
 *
 * @param av tracker to update
 */
static void
update_tracker (struct GNUNET_BANDWIDTH_Tracker *av)
{
  struct GNUNET_TIME_Absolute now;
  struct GNUNET_TIME_Relative delta;
  uint64_t delta_time;
  uint64_t delta_avail;
  uint64_t left_bytes;
  uint64_t max_carry;

  now = GNUNET_TIME_absolute_get ();
  delta_time = now.abs_value_us - av->last_update__.abs_value_us;
  delta_avail =
      (delta_time * ((unsigned long long) av->available_bytes_per_s__) +
       500000LL) / 1000000LL;
  av->consumption_since_last_update__ -= delta_avail;
  av->last_update__ = now;
  if (av->consumption_since_last_update__ < 0)
  {
    left_bytes = - av->consumption_since_last_update__;
    max_carry = ((unsigned long long) av->available_bytes_per_s__) *
                av->max_carry_s__;
    if (max_carry < GNUNET_SERVER_MAX_MESSAGE_SIZE)
      max_carry = GNUNET_SERVER_MAX_MESSAGE_SIZE;
    if (max_carry > INT64_MAX)
      max_carry = INT64_MAX;
    if (max_carry > left_bytes)
      av->consumption_since_last_update__ = - left_bytes;
    else
      av->consumption_since_last_update__ = - max_carry;
  }
  delta.rel_value_us = delta_time;
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Tracker %p updated, consumption at %lld at %u Bps, last update was %s ago\n",
       av,
       (long long) av->consumption_since_last_update__,
       (unsigned int) av->available_bytes_per_s__,
       GNUNET_STRINGS_relative_time_to_string (delta,
					       GNUNET_YES));
}


/**
 * Notify the tracker that a certain number of bytes of bandwidth have
 * been consumed.  Note that it is legal to consume bytes even if not
 * enough bandwidth is available (in that case,
 * #GNUNET_BANDWIDTH_tracker_get_delay may return non-zero delay values
 * even for a size of zero for a while).
 *
 * @param av tracker to update
 * @param size number of bytes consumed
 * @return #GNUNET_YES if this consumption is above the limit
 */
int
GNUNET_BANDWIDTH_tracker_consume (struct GNUNET_BANDWIDTH_Tracker *av,
                                  ssize_t size)
{
  int64_t nc;

  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Tracker %p consumes %d bytes\n",
       av,
       (int) size);
  if (size > 0)
  {
    nc = av->consumption_since_last_update__ + size;
    if (nc < av->consumption_since_last_update__)
    {
      /* integer overflow, very bad */
      GNUNET_break (0);
      return GNUNET_SYSERR;
    }
    av->consumption_since_last_update__ = nc;
    update_tracker (av);
    update_excess (av);
    if (av->consumption_since_last_update__ > 0)
    {
      LOG (GNUNET_ERROR_TYPE_DEBUG,
           "Tracker %p consumption %llu bytes above limit\n",
	   av,
           (unsigned long long) av->consumption_since_last_update__);
      return GNUNET_YES;
    }
  }
  else
  {
    nc = av->consumption_since_last_update__ + size;
    if (nc > av->consumption_since_last_update__)
    {
      /* integer underflow, very bad */
      GNUNET_break (0);
      return GNUNET_SYSERR;
    }
    av->consumption_since_last_update__ = nc;
    update_excess (av);
  }
  return GNUNET_NO;
}


/**
 * Compute how long we should wait until consuming 'size'
 * bytes of bandwidth in order to stay within the given
 * quota.
 *
 * @param av tracker to query
 * @param size number of bytes we would like to consume
 * @return time in ms to wait for consumption to be OK
 */
struct GNUNET_TIME_Relative
GNUNET_BANDWIDTH_tracker_get_delay (struct GNUNET_BANDWIDTH_Tracker *av,
                                    size_t size)
{
  struct GNUNET_TIME_Relative ret;
  int64_t bytes_needed;

  if (0 == av->available_bytes_per_s__)
  {
    LOG (GNUNET_ERROR_TYPE_DEBUG,
	 "Tracker %p delay is infinity\n", av);
    return GNUNET_TIME_UNIT_FOREVER_REL;
  }
  update_tracker (av);
  bytes_needed = size + av->consumption_since_last_update__;
  if (bytes_needed <= 0)
  {
    LOG (GNUNET_ERROR_TYPE_DEBUG,
	 "Tracker %p delay for %u bytes is zero\n", av,
         (unsigned int) size);
    return GNUNET_TIME_UNIT_ZERO;
  }
  ret.rel_value_us =
      (1000LL * 1000LL * bytes_needed) /
      (unsigned long long) av->available_bytes_per_s__;
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Tracker %p delay for %u bytes is %s\n",
       av,
       (unsigned int) size,
       GNUNET_STRINGS_relative_time_to_string (ret, GNUNET_YES));
  return ret;
}


/**
 * Compute how many bytes are available for consumption right now.
 * quota.
 *
 * @param av tracker to query
 * @return number of bytes available for consumption right now
 */
int64_t
GNUNET_BANDWIDTH_tracker_get_available (struct GNUNET_BANDWIDTH_Tracker *av)
{
  struct GNUNET_BANDWIDTH_Value32NBO bps;
  uint64_t avail;
  int64_t used;

  update_tracker (av);
  bps = GNUNET_BANDWIDTH_value_init (av->available_bytes_per_s__);
  avail =
      GNUNET_BANDWIDTH_value_get_available_until (bps,
                                                  GNUNET_TIME_absolute_get_duration
                                                  (av->last_update__));
  used = av->consumption_since_last_update__;
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Tracker %p available bandwidth is %lld bytes\n", av,
       (long long) (int64_t) (avail - used));
  return (int64_t) (avail - used);
}


/**
 * Update quota of bandwidth tracker.
 *
 * @param av tracker to initialize
 * @param bytes_per_second_limit new limit to assume
 */
void
GNUNET_BANDWIDTH_tracker_update_quota (struct GNUNET_BANDWIDTH_Tracker *av,
                                       struct GNUNET_BANDWIDTH_Value32NBO bytes_per_second_limit)
{
  uint32_t old_limit;
  uint32_t new_limit;

  new_limit = ntohl (bytes_per_second_limit.value__);
  LOG (GNUNET_ERROR_TYPE_DEBUG,
       "Tracker %p bandwidth changed to %u Bps\n", av,
       (unsigned int) new_limit);
  update_tracker (av);
  old_limit = av->available_bytes_per_s__;
  av->available_bytes_per_s__ = new_limit;
  if (NULL != av->update_cb)
    av->update_cb (av->update_cb_cls);
  if (old_limit > new_limit)
    update_tracker (av);        /* maximum excess might be less now */
  update_excess (av);
}


/* end of bandwidth.c */