All of the other bandwidth-limiting code stores limits and intermediate (byte)
counters as unsigned integers.
The exception here is freq_ctr_overshoot_period which takes in unsigned values
but returns a signed value.
While this has the benefit of letting the caller know how far away from
overshooting they are, this is not currently
leveraged anywhere in the codebase, and it has the downside of halving the
positive range of the result.
More concretely though, returning a signed integer when all intermediate values
are unsigned (and boundaries are
not checked) could result in an overflow, producing values that are at best
unexpected. In the case of flt_bwlim
(the only usage of freq_ctr_overshoot_period in the codebase at the time of
writing), an overflow could cause the
filter to wait for a large number of milliseconds when in fact it shouldn't
wait at all.
This is a niche possibility, because it requires that a bandwidth limit is
defined in the range [2^31, 2^32).
In this case, the raw limit value would not fit into a signed integer, and
close to the end of the period,
the `(elapsed * freq)/period` calculation could produce a value which also
doesn't fit into a signed integer.
If at the same time `curr` (the number of events counted so far in the current
period) is small, then we could
get a very large negative value which overflows. This is undefined behaviour
and could produce surprising results.
The most obvious outcome is flt_bwlim sometimes waiting for a large amount of
time in a case where it shouldn't
wait at all, thereby incorrectly slowing down the flow of data.
Converting just the return type from signed to unsigned (and checking for the
overflow) prevents this undefined
behaviour. It also makes the range of valid values consistent between the input
and output of freq_ctr_overshoot_period
and with the input and output of other freq_ctr functions, thereby reducing the
potential for surprise in
intermediate calculations: now everything supports the full 0 - 2^32 range.
Disclaimer for the mailing list:
So far I've been unable to reproduce this slowdown using flt_bwlim as-is, this
issue was found while working on
a custom filter that serves a similar purpose.
Conceptually the problem exists either way, and it seems to me like returning
unsigned is less error-prone in
this case (because everything else is unsigned) but I thought it'd be worth
calling out. From my testing
and as far as I can tell conceptually, it at the very least does not hurt the
flt_bwlim functionality.
---
include/haproxy/freq_ctr.h | 2 +-
src/flt_bwlim.c | 4 ++--
src/freq_ctr.c | 19 ++++++++++++-------
3 files changed, 15 insertions(+), 10 deletions(-)
diff --git a/include/haproxy/freq_ctr.h b/include/haproxy/freq_ctr.h
index 6ddcde842..dfb187483 100644
--- a/include/haproxy/freq_ctr.h
+++ b/include/haproxy/freq_ctr.h
@@ -31,7 +31,7 @@
ullong _freq_ctr_total_from_values(uint period, int pend, uint tick, ullong
past, ullong curr);
ullong freq_ctr_total(const struct freq_ctr *ctr, uint period, int pend);
ullong freq_ctr_total_estimate(const struct freq_ctr *ctr, uint period, int
pend);
-int freq_ctr_overshoot_period(const struct freq_ctr *ctr, uint period, uint
freq);
+uint freq_ctr_overshoot_period(const struct freq_ctr *ctr, uint period, uint
freq);
uint update_freq_ctr_period_slow(struct freq_ctr *ctr, uint period, uint inc);
/* Only usable during single threaded startup phase. */
diff --git a/src/flt_bwlim.c b/src/flt_bwlim.c
index 3c75b9bb0..40a876790 100644
--- a/src/flt_bwlim.c
+++ b/src/flt_bwlim.c
@@ -79,9 +79,9 @@ static int bwlim_apply_limit(struct filter *filter, struct
channel *chn, unsigne
struct bwlim_state *st = filter->ctx;
struct freq_ctr *bytes_rate;
uint64_t remain;
- unsigned int period, limit, tokens, users, factor;
+ unsigned int period, limit, tokens, users, factor, overshoot;
unsigned int wait = 0;
- int overshoot, ret = 0;
+ int ret = 0;
/* Don't forward anything if there is nothing to forward or the waiting
* time is not expired
diff --git a/src/freq_ctr.c b/src/freq_ctr.c
index 7f9e346de..571798297 100644
--- a/src/freq_ctr.c
+++ b/src/freq_ctr.c
@@ -184,17 +184,17 @@ ullong freq_ctr_total_estimate(const struct freq_ctr
*ctr, uint period, int pend
return _freq_ctr_total_from_values(period, pend, tick, past, curr);
}
-/* Returns the excess of events (may be negative) over the current period for
- * target frequency <freq>. It returns 0 if the counter is in the future or if
- * the counter is empty. The result considers the position of the current time
- * within the current period.
+/* Returns the excess of events over the current period for target frequency
+ * <freq>. It returns 0 if the counter is in the future or if the counter is
+ * empty. The result considers the position of the current time within the
+ * current period.
*
* The caller may safely add new events if result is negative or null.
*/
-int freq_ctr_overshoot_period(const struct freq_ctr *ctr, uint period, uint
freq)
+uint freq_ctr_overshoot_period(const struct freq_ctr *ctr, uint period, uint
freq)
{
ullong curr, old_curr;
- uint tick, old_tick;
+ uint tick, old_tick, linear_usage;
int elapsed;
tick = HA_ATOMIC_LOAD(&ctr->curr_tick);
@@ -245,7 +245,12 @@ int freq_ctr_overshoot_period(const struct freq_ctr *ctr,
uint period, uint freq
return 0;
}
- return curr - div64_32((uint64_t)elapsed * freq, period);
+ linear_usage = div64_32((uint64_t)elapsed * freq, period);
+ if (curr < linear_usage) {
+ /* The counter is below a uniform linear increase across the period, no
overshoot */
+ return 0;
+ }
+ return curr - linear_usage;
}
/*
--
2.43.0
