aboutsummaryrefslogtreecommitdiff
path: root/src/util/bandwidth.c
blob: 79497ad5137cf5034d35493db931fe01a78416d7 (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
/*
     This file is part of GNUnet.
     (C) 2010, 2013 Christian Grothoff (and other contributing authors)

     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., 59 Temple Place - Suite 330,
     Boston, MA 02111-1307, 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;

  LOG (GNUNET_ERROR_TYPE_DEBUG, "Initializing bandwidth of %u Bps\n",
       (unsigned int) bytes_per_second);
  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__)));
}


/**
 * 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
 * '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;
}


/**
 * 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 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,
                               struct GNUNET_BANDWIDTH_Value32NBO
                               bytes_per_second_limit, uint32_t max_carry_s)
{
  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;
  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 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 = 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 > 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, have %u Bps, last update was %s ago\n", av,
       (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__)
    {
      GNUNET_break (0);
      return GNUNET_SYSERR;
    }
    av->consumption_since_last_update__ = nc;
    update_tracker (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
  {
    av->consumption_since_last_update__ += size;
  }
  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 (av->available_bytes_per_s__ == 0)
  {
    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 (old_limit > new_limit)
    update_tracker (av);        /* maximum excess might be less now */
}


/* end of bandwidth.c */