From 3caf199795bd1c7b475f9cb7941186ee4b66eaec Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Fri, 5 Mar 2010 15:43:20 +0000 Subject: [PATCH] bwlib --- src/include/gnunet_bandwidth_lib.h | 178 +++++++++++++++++++++++ src/util/Makefile.am | 1 + src/util/bandwidth.c | 221 +++++++++++++++++++++++++++++ 3 files changed, 400 insertions(+) create mode 100644 src/include/gnunet_bandwidth_lib.h create mode 100644 src/util/bandwidth.c diff --git a/src/include/gnunet_bandwidth_lib.h b/src/include/gnunet_bandwidth_lib.h new file mode 100644 index 000000000..2dbe6e562 --- /dev/null +++ b/src/include/gnunet_bandwidth_lib.h @@ -0,0 +1,178 @@ +/* + This file is part of GNUnet. + (C) 2010 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 2, 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 include/gnunet_bandwidth_lib.h + * @brief functions related to bandwidth (unit) + * + * @author Christian Grothoff + */ + +#ifndef GNUNET_BANDWIDTH_LIB_H +#define GNUNET_BANDWIDTH_LIB_H + +#ifdef __cplusplus +extern "C" +{ +#if 0 /* keep Emacsens' auto-indent happy */ +} +#endif +#endif + +#include "gnunet_common.h" +#include "gnunet_time_lib.h" + +/** + * 32-bit bandwidth used for network exchange by GNUnet, in bytes per second. + */ +struct GNUNET_BANDWIDTH_Value32NBO +{ + /** + * The actual value (bytes per second). + */ + uint32_t value__ GNUNET_PACKED; +}; + + +/** + * Struct to track available bandwidth. Combines a time stamp with a + * number of bytes transmitted, a quota and a maximum amount that + * carries over. Not opaque so that it can be inlined into data + * structures (reducing malloc-ing); however, values should not be + * accessed directly by clients (hence the '__'). + */ +struct GNUNET_BANDWIDTH_Tracker +{ + /** + * Number of bytes consumed since we last updated the tracker. + */ + uint64_t consumption_since_last_update__; + + /** + * Time when we last updated the tracker. + */ + struct GNUNET_TIME_Absolute last_update__; + + /** + * Bandwidth limit to enforce in bytes per s. + */ + uint32_t available_bytes_per_s__; + + /** + * Maximum number of seconds over which bandwidth may "accumulate". + * Note that additionally, we also always allow at least + * GNUNET_SERVER_MAX_MESSAGE_SIZE to accumulate. + */ + uint32_t max_carry_s__; +}; + + +/** + * 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); + + +/** + * 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); + + +/** + * 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); + + +/** + * 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 + */ +void +GNUNET_BANDWIDTH_tracker_consume (struct GNUNET_BANDWIDTH_Tracker *av, + size_t size); + + +/** + * 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 to wait for consumption to be OK + */ +struct GNUNET_TIME_Relative +GNUNET_BANDWIDTH_tracker_get_delay (struct GNUNET_BANDWIDTH_Tracker *av, + size_t size); + + +/** + * 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); + + +#if 0 /* keep Emacsens' auto-indent happy */ +{ +#endif +#ifdef __cplusplus +} +#endif + +/* ifndef GNUNET_BANDWIDTH_LIB_H */ +#endif +/* end of gnunet_bandwidth_lib.h */ diff --git a/src/util/Makefile.am b/src/util/Makefile.am index 99cb0af97..81e6f79d8 100644 --- a/src/util/Makefile.am +++ b/src/util/Makefile.am @@ -24,6 +24,7 @@ endif lib_LTLIBRARIES = libgnunetutil.la libgnunetutil_la_SOURCES = \ + bandwidth.c \ bio.c \ client.c \ common_allocation.c \ diff --git a/src/util/bandwidth.c b/src/util/bandwidth.c new file mode 100644 index 000000000..aaf57619f --- /dev/null +++ b/src/util/bandwidth.c @@ -0,0 +1,221 @@ +/* + This file is part of GNUnet. + (C) 2010 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 2, 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_bandwidth_lib.h" +#include "gnunet_server_lib.h" + +/** + * 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__))); +} + + +/** + * 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; +} + + +/** + * 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; + uint64_t avail_per_ms; + uint64_t delta_time; + uint64_t delta_avail; + uint64_t left_bytes; + uint64_t left_time_ms; + + now = GNUNET_TIME_absolute_get (); + delta_time = now.value - av->last_update__.value; + delta_avail = (delta_time * ((unsigned long long) av->available_bytes_per_s__)) / 1000LL; + if (av->consumption_since_last_update__ >= delta_avail) + { + av->consumption_since_last_update__ -= delta_avail; + av->last_update__ = now; + } + else + { + left_bytes = delta_avail - av->consumption_since_last_update__; + avail_per_ms = ((unsigned long long) av->available_bytes_per_s__) / 1000LL; + if (avail_per_ms > 0) + left_time_ms = left_bytes / avail_per_ms; + else + left_time_ms = 0; + if (left_time_ms > ((unsigned long long) av->max_carry_s__) * 1000LL) + { + /* need to limit accumulation of unused bandwidth */ + left_time_ms = ((unsigned long long) av->max_carry_s__) * 1000LL; + if (left_time_ms * avail_per_ms < GNUNET_SERVER_MAX_MESSAGE_SIZE) + { + /* need to still allow GNUNET_SERVER_MAX_MESSAGE_SIZE accumulation */ + if (left_bytes > GNUNET_SERVER_MAX_MESSAGE_SIZE) + left_bytes = GNUNET_SERVER_MAX_MESSAGE_SIZE; + left_time_ms = left_bytes / avail_per_ms; + } + } + av->consumption_since_last_update__ = 0; + av->last_update__.value = now.value - left_time_ms; + } +} + + + +/** + * 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 + */ +void +GNUNET_BANDWIDTH_tracker_consume (struct GNUNET_BANDWIDTH_Tracker *av, + size_t size) +{ + uint64_t nc; + + nc = av->consumption_since_last_update__ + size; + if (nc < av->consumption_since_last_update__) + { + GNUNET_break (0); + return; + } + av->consumption_since_last_update__ += size; + update_tracker (av); +} + + +/** + * 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 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; + struct GNUNET_TIME_Absolute now; + uint64_t delta_avail; + uint64_t delta_time; + uint64_t bytes_needed; + + if (av->available_bytes_per_s__ == 0) + return GNUNET_TIME_UNIT_FOREVER_REL; + update_tracker (av); + now = GNUNET_TIME_absolute_get (); + delta_time = now.value - av->last_update__.value; + delta_avail = (delta_time * ((unsigned long long) av->available_bytes_per_s__)) / 1000LL; + if (delta_avail >= size) + return GNUNET_TIME_UNIT_ZERO; + bytes_needed = size - delta_avail; + ret.value = 1000LL * bytes_needed / (unsigned long long) av->available_bytes_per_s__; + return ret; +} + + +/** + * 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__); + 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 */ -- 2.25.1