summaryrefslogtreecommitdiffstats
path: root/net/dccp/ccids/lib
diff options
context:
space:
mode:
Diffstat (limited to 'net/dccp/ccids/lib')
-rw-r--r--net/dccp/ccids/lib/loss_interval.c8
-rw-r--r--net/dccp/ccids/lib/loss_interval.h2
-rw-r--r--net/dccp/ccids/lib/packet_history.h4
-rw-r--r--net/dccp/ccids/lib/tfrc_equation.c223
4 files changed, 147 insertions, 90 deletions
diff --git a/net/dccp/ccids/lib/loss_interval.c b/net/dccp/ccids/lib/loss_interval.c
index 906c81a..0a0baef 100644
--- a/net/dccp/ccids/lib/loss_interval.c
+++ b/net/dccp/ccids/lib/loss_interval.c
@@ -13,7 +13,7 @@
#include <linux/module.h>
#include <net/sock.h>
-
+#include "../../dccp.h"
#include "loss_interval.h"
struct dccp_li_hist *dccp_li_hist_new(const char *name)
@@ -109,7 +109,7 @@ u32 dccp_li_hist_calc_i_mean(struct list_head *list)
i_tot = max(i_tot0, i_tot1);
if (!w_tot) {
- LIMIT_NETDEBUG(KERN_WARNING "%s: w_tot = 0\n", __FUNCTION__);
+ DCCP_WARN("w_tot = 0\n");
return 1;
}
@@ -125,10 +125,10 @@ int dccp_li_hist_interval_new(struct dccp_li_hist *hist,
int i;
for (i = 0; i < DCCP_LI_HIST_IVAL_F_LENGTH; i++) {
- entry = dccp_li_hist_entry_new(hist, SLAB_ATOMIC);
+ entry = dccp_li_hist_entry_new(hist, GFP_ATOMIC);
if (entry == NULL) {
dccp_li_hist_purge(hist, list);
- dump_stack();
+ DCCP_BUG("loss interval list entry is NULL");
return 0;
}
entry->dccplih_interval = ~0;
diff --git a/net/dccp/ccids/lib/loss_interval.h b/net/dccp/ccids/lib/loss_interval.h
index 0ae85f0..eb25701 100644
--- a/net/dccp/ccids/lib/loss_interval.h
+++ b/net/dccp/ccids/lib/loss_interval.h
@@ -20,7 +20,7 @@
#define DCCP_LI_HIST_IVAL_F_LENGTH 8
struct dccp_li_hist {
- kmem_cache_t *dccplih_slab;
+ struct kmem_cache *dccplih_slab;
};
extern struct dccp_li_hist *dccp_li_hist_new(const char *name);
diff --git a/net/dccp/ccids/lib/packet_history.h b/net/dccp/ccids/lib/packet_history.h
index 067cf1c..9a8bcf2 100644
--- a/net/dccp/ccids/lib/packet_history.h
+++ b/net/dccp/ccids/lib/packet_history.h
@@ -68,14 +68,14 @@ struct dccp_rx_hist_entry {
};
struct dccp_tx_hist {
- kmem_cache_t *dccptxh_slab;
+ struct kmem_cache *dccptxh_slab;
};
extern struct dccp_tx_hist *dccp_tx_hist_new(const char *name);
extern void dccp_tx_hist_delete(struct dccp_tx_hist *hist);
struct dccp_rx_hist {
- kmem_cache_t *dccprxh_slab;
+ struct kmem_cache *dccprxh_slab;
};
extern struct dccp_rx_hist *dccp_rx_hist_new(const char *name);
diff --git a/net/dccp/ccids/lib/tfrc_equation.c b/net/dccp/ccids/lib/tfrc_equation.c
index 44076e0..ddac2c5 100644
--- a/net/dccp/ccids/lib/tfrc_equation.c
+++ b/net/dccp/ccids/lib/tfrc_equation.c
@@ -13,16 +13,84 @@
*/
#include <linux/module.h>
-
#include <asm/div64.h>
-
+#include "../../dccp.h"
#include "tfrc.h"
#define TFRC_CALC_X_ARRSIZE 500
+#define TFRC_CALC_X_SPLIT 50000 /* 0.05 * 1000000, details below */
+#define TFRC_SMALLEST_P (TFRC_CALC_X_SPLIT/TFRC_CALC_X_ARRSIZE)
-#define TFRC_CALC_X_SPLIT 50000
-/* equivalent to 0.05 */
-
+/*
+ TFRC TCP Reno Throughput Equation Lookup Table for f(p)
+
+ The following two-column lookup table implements a part of the TCP throughput
+ equation from [RFC 3448, sec. 3.1]:
+
+ s
+ X_calc = --------------------------------------------------------------
+ R * sqrt(2*b*p/3) + (3 * t_RTO * sqrt(3*b*p/8) * (p + 32*p^3))
+
+ Where:
+ X is the transmit rate in bytes/second
+ s is the packet size in bytes
+ R is the round trip time in seconds
+ p is the loss event rate, between 0 and 1.0, of the number of loss
+ events as a fraction of the number of packets transmitted
+ t_RTO is the TCP retransmission timeout value in seconds
+ b is the number of packets acknowledged by a single TCP ACK
+
+ We can assume that b = 1 and t_RTO is 4 * R. The equation now becomes:
+
+ s
+ X_calc = -------------------------------------------------------
+ R * sqrt(p*2/3) + (12 * R * sqrt(p*3/8) * (p + 32*p^3))
+
+ which we can break down into:
+
+ s
+ X_calc = ---------
+ R * f(p)
+
+ where f(p) is given for 0 < p <= 1 by:
+
+ f(p) = sqrt(2*p/3) + 12 * sqrt(3*p/8) * (p + 32*p^3)
+
+ Since this is kernel code, floating-point arithmetic is avoided in favour of
+ integer arithmetic. This means that nearly all fractional parameters are
+ scaled by 1000000:
+ * the parameters p and R
+ * the return result f(p)
+ The lookup table therefore actually tabulates the following function g(q):
+
+ g(q) = 1000000 * f(q/1000000)
+
+ Hence, when p <= 1, q must be less than or equal to 1000000. To achieve finer
+ granularity for the practically more relevant case of small values of p (up to
+ 5%), the second column is used; the first one ranges up to 100%. This split
+ corresponds to the value of q = TFRC_CALC_X_SPLIT. At the same time this also
+ determines the smallest resolution possible with this lookup table:
+
+ TFRC_SMALLEST_P = TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE
+
+ The entire table is generated by:
+ for(i=0; i < TFRC_CALC_X_ARRSIZE; i++) {
+ lookup[i][0] = g((i+1) * 1000000/TFRC_CALC_X_ARRSIZE);
+ lookup[i][1] = g((i+1) * TFRC_CALC_X_SPLIT/TFRC_CALC_X_ARRSIZE);
+ }
+
+ With the given configuration, we have, with M = TFRC_CALC_X_ARRSIZE-1,
+ lookup[0][0] = g(1000000/(M+1)) = 1000000 * f(0.2%)
+ lookup[M][0] = g(1000000) = 1000000 * f(100%)
+ lookup[0][1] = g(TFRC_SMALLEST_P) = 1000000 * f(0.01%)
+ lookup[M][1] = g(TFRC_CALC_X_SPLIT) = 1000000 * f(5%)
+
+ In summary, the two columns represent f(p) for the following ranges:
+ * The first column is for 0.002 <= p <= 1.0
+ * The second column is for 0.0001 <= p <= 0.05
+ Where the columns overlap, the second (finer-grained) is given preference,
+ i.e. the first column is used only for p >= 0.05.
+ */
static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = {
{ 37172, 8172 },
{ 53499, 11567 },
@@ -526,83 +594,69 @@ static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = {
{ 243315981, 271305 }
};
-/* Calculate the send rate as per section 3.1 of RFC3448
-
-Returns send rate in bytes per second
-
-Integer maths and lookups are used as not allowed floating point in kernel
-
-The function for Xcalc as per section 3.1 of RFC3448 is:
-
-X = s
- -------------------------------------------------------------
- R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2)))
-
-where
-X is the trasmit rate in bytes/second
-s is the packet size in bytes
-R is the round trip time in seconds
-p is the loss event rate, between 0 and 1.0, of the number of loss events
- as a fraction of the number of packets transmitted
-t_RTO is the TCP retransmission timeout value in seconds
-b is the number of packets acknowledged by a single TCP acknowledgement
-
-we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:
-
-X = s
- -----------------------------------------------------------------------
- R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))
-
-
-which we can break down into:
-
-X = s
- --------
- R * f(p)
-
-where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))
-
-Function parameters:
-s - bytes
-R - RTT in usecs
-p - loss rate (decimal fraction multiplied by 1,000,000)
-
-Returns Xcalc in bytes per second
-
-DON'T alter this code unless you run test cases against it as the code
-has been manipulated to stop underflow/overlow.
+/* return largest index i such that fval <= lookup[i][small] */
+static inline u32 tfrc_binsearch(u32 fval, u8 small)
+{
+ u32 try, low = 0, high = TFRC_CALC_X_ARRSIZE - 1;
+
+ while (low < high) {
+ try = (low + high) / 2;
+ if (fval <= tfrc_calc_x_lookup[try][small])
+ high = try;
+ else
+ low = try + 1;
+ }
+ return high;
+}
-*/
+/**
+ * tfrc_calc_x - Calculate the send rate as per section 3.1 of RFC3448
+ *
+ * @s: packet size in bytes
+ * @R: RTT scaled by 1000000 (i.e., microseconds)
+ * @p: loss ratio estimate scaled by 1000000
+ * Returns X_calc in bytes per second (not scaled).
+ *
+ * Note: DO NOT alter this code unless you run test cases against it,
+ * as the code has been optimized to stop underflow/overflow.
+ */
u32 tfrc_calc_x(u16 s, u32 R, u32 p)
{
int index;
u32 f;
u64 tmp1, tmp2;
- if (p < TFRC_CALC_X_SPLIT)
- index = (p / (TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE)) - 1;
- else
- index = (p / (1000000 / TFRC_CALC_X_ARRSIZE)) - 1;
+ /* check against invalid parameters and divide-by-zero */
+ BUG_ON(p > 1000000); /* p must not exceed 100% */
+ BUG_ON(p == 0); /* f(0) = 0, divide by zero */
+ if (R == 0) { /* possible divide by zero */
+ DCCP_CRIT("WARNING: RTT is 0, returning maximum X_calc.");
+ return ~0U;
+ }
- if (index < 0)
- /* p should be 0 unless there is a bug in my code */
- index = 0;
+ if (p <= TFRC_CALC_X_SPLIT) { /* 0.0000 < p <= 0.05 */
+ if (p < TFRC_SMALLEST_P) { /* 0.0000 < p < 0.0001 */
+ DCCP_WARN("Value of p (%d) below resolution. "
+ "Substituting %d\n", p, TFRC_SMALLEST_P);
+ index = 0;
+ } else /* 0.0001 <= p <= 0.05 */
+ index = p/TFRC_SMALLEST_P - 1;
- if (R == 0)
- R = 1; /* RTT can't be zero or else divide by zero */
+ f = tfrc_calc_x_lookup[index][1];
- BUG_ON(index >= TFRC_CALC_X_ARRSIZE);
+ } else { /* 0.05 < p <= 1.00 */
+ index = p/(1000000/TFRC_CALC_X_ARRSIZE) - 1;
- if (p >= TFRC_CALC_X_SPLIT)
f = tfrc_calc_x_lookup[index][0];
- else
- f = tfrc_calc_x_lookup[index][1];
+ }
+ /* The following computes X = s/(R*f(p)) in bytes per second. Since f(p)
+ * and R are both scaled by 1000000, we need to multiply by 1000000^2.
+ * ==> DO NOT alter this unless you test against overflow on 32 bit */
tmp1 = ((u64)s * 100000000);
tmp2 = ((u64)R * (u64)f);
do_div(tmp2, 10000);
do_div(tmp1, tmp2);
- /* Don't alter above math unless you test due to overflow on 32 bit */
return (u32)tmp1;
}
@@ -610,33 +664,36 @@ u32 tfrc_calc_x(u16 s, u32 R, u32 p)
EXPORT_SYMBOL_GPL(tfrc_calc_x);
/*
- * args: fvalue - function value to match
- * returns: p closest to that value
+ * tfrc_calc_x_reverse_lookup - try to find p given f(p)
*
- * both fvalue and p are multiplied by 1,000,000 to use ints
+ * @fvalue: function value to match, scaled by 1000000
+ * Returns closest match for p, also scaled by 1000000
*/
u32 tfrc_calc_x_reverse_lookup(u32 fvalue)
{
- int ctr = 0;
- int small;
+ int index;
- if (fvalue < tfrc_calc_x_lookup[0][1])
+ if (fvalue == 0) /* f(p) = 0 whenever p = 0 */
return 0;
- if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1])
- small = 1;
- else if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0])
+ /* Error cases. */
+ if (fvalue < tfrc_calc_x_lookup[0][1]) {
+ DCCP_WARN("fvalue %d smaller than resolution\n", fvalue);
+ return tfrc_calc_x_lookup[0][1];
+ }
+ if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0]) {
+ DCCP_WARN("fvalue %d exceeds bounds!\n", fvalue);
return 1000000;
- else
- small = 0;
-
- while (fvalue > tfrc_calc_x_lookup[ctr][small])
- ctr++;
+ }
- if (small)
- return TFRC_CALC_X_SPLIT * ctr / TFRC_CALC_X_ARRSIZE;
- else
- return 1000000 * ctr / TFRC_CALC_X_ARRSIZE;
+ if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1]) {
+ index = tfrc_binsearch(fvalue, 1);
+ return (index + 1) * TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE;
+ }
+
+ /* else ... it must be in the coarse-grained column */
+ index = tfrc_binsearch(fvalue, 0);
+ return (index + 1) * 1000000 / TFRC_CALC_X_ARRSIZE;
}
EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup);
OpenPOWER on IntegriCloud