diff options
Diffstat (limited to 'net/dccp/ccids')
| -rw-r--r-- | net/dccp/ccids/Kconfig | 84 | ||||
| -rw-r--r-- | net/dccp/ccids/Makefile | 9 | ||||
| -rw-r--r-- | net/dccp/ccids/ccid2.c | 1002 | ||||
| -rw-r--r-- | net/dccp/ccids/ccid2.h | 123 | ||||
| -rw-r--r-- | net/dccp/ccids/ccid3.c | 1606 | ||||
| -rw-r--r-- | net/dccp/ccids/ccid3.h | 179 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/Makefile | 3 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/loss_interval.c | 242 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/loss_interval.h | 76 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/packet_history.c | 562 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/packet_history.h | 217 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/tfrc.c | 45 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/tfrc.h | 73 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/tfrc_equation.c | 263 |
14 files changed, 2165 insertions, 2319 deletions
diff --git a/net/dccp/ccids/Kconfig b/net/dccp/ccids/Kconfig index 32752f75044..8ba3fc9d6d1 100644 --- a/net/dccp/ccids/Kconfig +++ b/net/dccp/ccids/Kconfig @@ -1,72 +1,54 @@ -menu "DCCP CCIDs Configuration (EXPERIMENTAL)" - depends on IP_DCCP && EXPERIMENTAL +menu "DCCP CCIDs Configuration" -config IP_DCCP_CCID2 - tristate "CCID2 (TCP-Like) (EXPERIMENTAL)" - depends on IP_DCCP - def_tristate IP_DCCP - select IP_DCCP_ACKVEC +config IP_DCCP_CCID2_DEBUG + bool "CCID-2 debugging messages" ---help--- - CCID 2, TCP-like Congestion Control, denotes Additive Increase, - Multiplicative Decrease (AIMD) congestion control with behavior - modelled directly on TCP, including congestion window, slow start, - timeouts, and so forth [RFC 2581]. CCID 2 achieves maximum - bandwidth over the long term, consistent with the use of end-to-end - congestion control, but halves its congestion window in response to - each congestion event. This leads to the abrupt rate changes - typical of TCP. Applications should use CCID 2 if they prefer - maximum bandwidth utilization to steadiness of rate. This is often - the case for applications that are not playing their data directly - to the user. For example, a hypothetical application that - transferred files over DCCP, using application-level retransmissions - for lost packets, would prefer CCID 2 to CCID 3. On-line games may - also prefer CCID 2. - - CCID 2 is further described in: - http://www.icir.org/kohler/dccp/draft-ietf-dccp-ccid2-10.txt + Enable CCID-2 specific debugging messages. - This text was extracted from: - http://www.icir.org/kohler/dccp/draft-ietf-dccp-spec-13.txt + The debugging output can additionally be toggled by setting the + ccid2_debug parameter to 0 or 1. - If in doubt, say M. - -config IP_DCCP_CCID2_DEBUG - bool "CCID2 debug" - depends on IP_DCCP_CCID2 - ---help--- - Enable CCID2 debug messages. - - If in doubt, say N. + If in doubt, say N. config IP_DCCP_CCID3 - tristate "CCID3 (TCP-Friendly) (EXPERIMENTAL)" - depends on IP_DCCP - def_tristate IP_DCCP + bool "CCID-3 (TCP-Friendly)" + def_bool y if (IP_DCCP = y || IP_DCCP = m) ---help--- - CCID 3 denotes TCP-Friendly Rate Control (TFRC), an equation-based + CCID-3 denotes TCP-Friendly Rate Control (TFRC), an equation-based rate-controlled congestion control mechanism. TFRC is designed to be reasonably fair when competing for bandwidth with TCP-like flows, where a flow is "reasonably fair" if its sending rate is generally within a factor of two of the sending rate of a TCP flow under the same conditions. However, TFRC has a much lower variation of - throughput over time compared with TCP, which makes CCID 3 more - suitable than CCID 2 for applications such streaming media where a + throughput over time compared with TCP, which makes CCID-3 more + suitable than CCID-2 for applications such streaming media where a relatively smooth sending rate is of importance. - CCID 3 is further described in: - - http://www.icir.org/kohler/dccp/draft-ietf-dccp-ccid3-11.txt. + CCID-3 is further described in RFC 4342, + http://www.ietf.org/rfc/rfc4342.txt The TFRC congestion control algorithms were initially described in - RFC 3448. + RFC 5348. - This text was extracted from: - http://www.icir.org/kohler/dccp/draft-ietf-dccp-spec-13.txt - - If in doubt, say M. + This text was extracted from RFC 4340 (sec. 10.2), + http://www.ietf.org/rfc/rfc4340.txt -config IP_DCCP_TFRC_LIB + If in doubt, say N. + +config IP_DCCP_CCID3_DEBUG + bool "CCID-3 debugging messages" depends on IP_DCCP_CCID3 - def_tristate IP_DCCP_CCID3 + ---help--- + Enable CCID-3 specific debugging messages. + + The debugging output can additionally be toggled by setting the + ccid3_debug parameter to 0 or 1. + + If in doubt, say N. + +config IP_DCCP_TFRC_LIB + def_bool y if IP_DCCP_CCID3 +config IP_DCCP_TFRC_DEBUG + def_bool y if IP_DCCP_CCID3_DEBUG endmenu diff --git a/net/dccp/ccids/Makefile b/net/dccp/ccids/Makefile deleted file mode 100644 index 438f20bccff..00000000000 --- a/net/dccp/ccids/Makefile +++ /dev/null @@ -1,9 +0,0 @@ -obj-$(CONFIG_IP_DCCP_CCID3) += dccp_ccid3.o - -dccp_ccid3-y := ccid3.o - -obj-$(CONFIG_IP_DCCP_CCID2) += dccp_ccid2.o - -dccp_ccid2-y := ccid2.o - -obj-y += lib/ diff --git a/net/dccp/ccids/ccid2.c b/net/dccp/ccids/ccid2.c index 2efb505aeb3..f053198e730 100644 --- a/net/dccp/ccids/ccid2.c +++ b/net/dccp/ccids/ccid2.c @@ -1,6 +1,4 @@ /* - * net/dccp/ccids/ccid2.c - * * Copyright (c) 2005, 2006 Andrea Bittau <a.bittau@cs.ucl.ac.uk> * * Changes to meet Linux coding standards, and DCCP infrastructure fixes. @@ -23,308 +21,290 @@ */ /* - * This implementation should follow: draft-ietf-dccp-ccid2-10.txt - * - * BUGS: - * - sequence number wrapping + * This implementation should follow RFC 4341 */ - -#include "../ccid.h" -#include "../dccp.h" +#include <linux/slab.h> +#include "../feat.h" #include "ccid2.h" -static int ccid2_debug; #ifdef CONFIG_IP_DCCP_CCID2_DEBUG -#define ccid2_pr_debug(format, a...) \ - do { if (ccid2_debug) \ - printk(KERN_DEBUG "%s: " format, __FUNCTION__, ##a); \ - } while (0) +static bool ccid2_debug; +#define ccid2_pr_debug(format, a...) DCCP_PR_DEBUG(ccid2_debug, format, ##a) #else #define ccid2_pr_debug(format, a...) #endif -#ifdef CONFIG_IP_DCCP_CCID2_DEBUG -static void ccid2_hc_tx_check_sanity(const struct ccid2_hc_tx_sock *hctx) -{ - int len = 0; - int pipe = 0; - struct ccid2_seq *seqp = hctx->ccid2hctx_seqh; - - /* there is data in the chain */ - if (seqp != hctx->ccid2hctx_seqt) { - seqp = seqp->ccid2s_prev; - len++; - if (!seqp->ccid2s_acked) - pipe++; - - while (seqp != hctx->ccid2hctx_seqt) { - struct ccid2_seq *prev = seqp->ccid2s_prev; - - len++; - if (!prev->ccid2s_acked) - pipe++; - - /* packets are sent sequentially */ - BUG_ON(seqp->ccid2s_seq <= prev->ccid2s_seq); - BUG_ON(time_before(seqp->ccid2s_sent, - prev->ccid2s_sent)); - - seqp = prev; - } - } - - BUG_ON(pipe != hctx->ccid2hctx_pipe); - ccid2_pr_debug("len of chain=%d\n", len); - - do { - seqp = seqp->ccid2s_prev; - len++; - } while (seqp != hctx->ccid2hctx_seqh); - - ccid2_pr_debug("total len=%d\n", len); - BUG_ON(len != hctx->ccid2hctx_seqbufc * CCID2_SEQBUF_LEN); -} -#else -#define ccid2_hc_tx_check_sanity(hctx) do {} while (0) -#endif - -static int ccid2_hc_tx_alloc_seq(struct ccid2_hc_tx_sock *hctx, int num, - gfp_t gfp) +static int ccid2_hc_tx_alloc_seq(struct ccid2_hc_tx_sock *hc) { struct ccid2_seq *seqp; int i; /* check if we have space to preserve the pointer to the buffer */ - if (hctx->ccid2hctx_seqbufc >= (sizeof(hctx->ccid2hctx_seqbuf) / - sizeof(struct ccid2_seq*))) + if (hc->tx_seqbufc >= (sizeof(hc->tx_seqbuf) / + sizeof(struct ccid2_seq *))) return -ENOMEM; /* allocate buffer and initialize linked list */ - seqp = kmalloc(sizeof(*seqp) * num, gfp); + seqp = kmalloc(CCID2_SEQBUF_LEN * sizeof(struct ccid2_seq), gfp_any()); if (seqp == NULL) return -ENOMEM; - for (i = 0; i < (num - 1); i++) { + for (i = 0; i < (CCID2_SEQBUF_LEN - 1); i++) { seqp[i].ccid2s_next = &seqp[i + 1]; seqp[i + 1].ccid2s_prev = &seqp[i]; } - seqp[num - 1].ccid2s_next = seqp; - seqp->ccid2s_prev = &seqp[num - 1]; + seqp[CCID2_SEQBUF_LEN - 1].ccid2s_next = seqp; + seqp->ccid2s_prev = &seqp[CCID2_SEQBUF_LEN - 1]; /* This is the first allocation. Initiate the head and tail. */ - if (hctx->ccid2hctx_seqbufc == 0) - hctx->ccid2hctx_seqh = hctx->ccid2hctx_seqt = seqp; + if (hc->tx_seqbufc == 0) + hc->tx_seqh = hc->tx_seqt = seqp; else { /* link the existing list with the one we just created */ - hctx->ccid2hctx_seqh->ccid2s_next = seqp; - seqp->ccid2s_prev = hctx->ccid2hctx_seqh; + hc->tx_seqh->ccid2s_next = seqp; + seqp->ccid2s_prev = hc->tx_seqh; - hctx->ccid2hctx_seqt->ccid2s_prev = &seqp[num - 1]; - seqp[num - 1].ccid2s_next = hctx->ccid2hctx_seqt; + hc->tx_seqt->ccid2s_prev = &seqp[CCID2_SEQBUF_LEN - 1]; + seqp[CCID2_SEQBUF_LEN - 1].ccid2s_next = hc->tx_seqt; } /* store the original pointer to the buffer so we can free it */ - hctx->ccid2hctx_seqbuf[hctx->ccid2hctx_seqbufc] = seqp; - hctx->ccid2hctx_seqbufc++; + hc->tx_seqbuf[hc->tx_seqbufc] = seqp; + hc->tx_seqbufc++; return 0; } -static int ccid2_hc_tx_send_packet(struct sock *sk, - struct sk_buff *skb, int len) +static int ccid2_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb) { - struct ccid2_hc_tx_sock *hctx; - - switch (DCCP_SKB_CB(skb)->dccpd_type) { - case 0: /* XXX data packets from userland come through like this */ - case DCCP_PKT_DATA: - case DCCP_PKT_DATAACK: - break; - /* No congestion control on other packets */ - default: - return 0; - } - - hctx = ccid2_hc_tx_sk(sk); - - ccid2_pr_debug("pipe=%d cwnd=%d\n", hctx->ccid2hctx_pipe, - hctx->ccid2hctx_cwnd); - - if (hctx->ccid2hctx_pipe < hctx->ccid2hctx_cwnd) { - /* OK we can send... make sure previous packet was sent off */ - if (!hctx->ccid2hctx_sendwait) { - hctx->ccid2hctx_sendwait = 1; - return 0; - } - } - - return 1; /* XXX CCID should dequeue when ready instead of polling */ + if (ccid2_cwnd_network_limited(ccid2_hc_tx_sk(sk))) + return CCID_PACKET_WILL_DEQUEUE_LATER; + return CCID_PACKET_SEND_AT_ONCE; } -static void ccid2_change_l_ack_ratio(struct sock *sk, int val) +static void ccid2_change_l_ack_ratio(struct sock *sk, u32 val) { - struct dccp_sock *dp = dccp_sk(sk); + u32 max_ratio = DIV_ROUND_UP(ccid2_hc_tx_sk(sk)->tx_cwnd, 2); + /* - * XXX I don't really agree with val != 2. If cwnd is 1, ack ratio - * should be 1... it shouldn't be allowed to become 2. - * -sorbo. + * Ensure that Ack Ratio does not exceed ceil(cwnd/2), which is (2) from + * RFC 4341, 6.1.2. We ignore the statement that Ack Ratio 2 is always + * acceptable since this causes starvation/deadlock whenever cwnd < 2. + * The same problem arises when Ack Ratio is 0 (ie. Ack Ratio disabled). */ - if (val != 2) { - const struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); - int max = hctx->ccid2hctx_cwnd / 2; - - /* round up */ - if (hctx->ccid2hctx_cwnd & 1) - max++; - - if (val > max) - val = max; + if (val == 0 || val > max_ratio) { + DCCP_WARN("Limiting Ack Ratio (%u) to %u\n", val, max_ratio); + val = max_ratio; } - - ccid2_pr_debug("changing local ack ratio to %d\n", val); - WARN_ON(val <= 0); - dp->dccps_l_ack_ratio = val; + dccp_feat_signal_nn_change(sk, DCCPF_ACK_RATIO, + min_t(u32, val, DCCPF_ACK_RATIO_MAX)); } -static void ccid2_change_cwnd(struct ccid2_hc_tx_sock *hctx, int val) +static void ccid2_check_l_ack_ratio(struct sock *sk) { - if (val == 0) - val = 1; - - /* XXX do we need to change ack ratio? */ - ccid2_pr_debug("change cwnd to %d\n", val); + struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk); - BUG_ON(val < 1); - hctx->ccid2hctx_cwnd = val; -} - -static void ccid2_change_srtt(struct ccid2_hc_tx_sock *hctx, long val) -{ - ccid2_pr_debug("change SRTT to %ld\n", val); - hctx->ccid2hctx_srtt = val; + /* + * After a loss, idle period, application limited period, or RTO we + * need to check that the ack ratio is still less than the congestion + * window. Otherwise, we will send an entire congestion window of + * packets and got no response because we haven't sent ack ratio + * packets yet. + * If the ack ratio does need to be reduced, we reduce it to half of + * the congestion window (or 1 if that's zero) instead of to the + * congestion window. This prevents problems if one ack is lost. + */ + if (dccp_feat_nn_get(sk, DCCPF_ACK_RATIO) > hc->tx_cwnd) + ccid2_change_l_ack_ratio(sk, hc->tx_cwnd/2 ? : 1U); } -static void ccid2_change_pipe(struct ccid2_hc_tx_sock *hctx, long val) +static void ccid2_change_l_seq_window(struct sock *sk, u64 val) { - hctx->ccid2hctx_pipe = val; + dccp_feat_signal_nn_change(sk, DCCPF_SEQUENCE_WINDOW, + clamp_val(val, DCCPF_SEQ_WMIN, + DCCPF_SEQ_WMAX)); } -static void ccid2_start_rto_timer(struct sock *sk); - static void ccid2_hc_tx_rto_expire(unsigned long data) { struct sock *sk = (struct sock *)data; - struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); - long s; + struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk); + const bool sender_was_blocked = ccid2_cwnd_network_limited(hc); bh_lock_sock(sk); if (sock_owned_by_user(sk)) { - sk_reset_timer(sk, &hctx->ccid2hctx_rtotimer, - jiffies + HZ / 5); + sk_reset_timer(sk, &hc->tx_rtotimer, jiffies + HZ / 5); goto out; } ccid2_pr_debug("RTO_EXPIRE\n"); - ccid2_hc_tx_check_sanity(hctx); - /* back-off timer */ - hctx->ccid2hctx_rto <<= 1; - - s = hctx->ccid2hctx_rto / HZ; - if (s > 60) - hctx->ccid2hctx_rto = 60 * HZ; - - ccid2_start_rto_timer(sk); + hc->tx_rto <<= 1; + if (hc->tx_rto > DCCP_RTO_MAX) + hc->tx_rto = DCCP_RTO_MAX; /* adjust pipe, cwnd etc */ - ccid2_change_pipe(hctx, 0); - hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd >> 1; - if (hctx->ccid2hctx_ssthresh < 2) - hctx->ccid2hctx_ssthresh = 2; - ccid2_change_cwnd(hctx, 1); + hc->tx_ssthresh = hc->tx_cwnd / 2; + if (hc->tx_ssthresh < 2) + hc->tx_ssthresh = 2; + hc->tx_cwnd = 1; + hc->tx_pipe = 0; /* clear state about stuff we sent */ - hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqh; - hctx->ccid2hctx_ssacks = 0; - hctx->ccid2hctx_acks = 0; - hctx->ccid2hctx_sent = 0; + hc->tx_seqt = hc->tx_seqh; + hc->tx_packets_acked = 0; /* clear ack ratio state. */ - hctx->ccid2hctx_arsent = 0; - hctx->ccid2hctx_ackloss = 0; - hctx->ccid2hctx_rpseq = 0; - hctx->ccid2hctx_rpdupack = -1; + hc->tx_rpseq = 0; + hc->tx_rpdupack = -1; ccid2_change_l_ack_ratio(sk, 1); - ccid2_hc_tx_check_sanity(hctx); + + /* if we were blocked before, we may now send cwnd=1 packet */ + if (sender_was_blocked) + tasklet_schedule(&dccp_sk(sk)->dccps_xmitlet); + /* restart backed-off timer */ + sk_reset_timer(sk, &hc->tx_rtotimer, jiffies + hc->tx_rto); out: bh_unlock_sock(sk); sock_put(sk); } -static void ccid2_start_rto_timer(struct sock *sk) +/* + * Congestion window validation (RFC 2861). + */ +static bool ccid2_do_cwv = true; +module_param(ccid2_do_cwv, bool, 0644); +MODULE_PARM_DESC(ccid2_do_cwv, "Perform RFC2861 Congestion Window Validation"); + +/** + * ccid2_update_used_window - Track how much of cwnd is actually used + * This is done in addition to CWV. The sender needs to have an idea of how many + * packets may be in flight, to set the local Sequence Window value accordingly + * (RFC 4340, 7.5.2). The CWV mechanism is exploited to keep track of the + * maximum-used window. We use an EWMA low-pass filter to filter out noise. + */ +static void ccid2_update_used_window(struct ccid2_hc_tx_sock *hc, u32 new_wnd) +{ + hc->tx_expected_wnd = (3 * hc->tx_expected_wnd + new_wnd) / 4; +} + +/* This borrows the code of tcp_cwnd_application_limited() */ +static void ccid2_cwnd_application_limited(struct sock *sk, const u32 now) +{ + struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk); + /* don't reduce cwnd below the initial window (IW) */ + u32 init_win = rfc3390_bytes_to_packets(dccp_sk(sk)->dccps_mss_cache), + win_used = max(hc->tx_cwnd_used, init_win); + + if (win_used < hc->tx_cwnd) { + hc->tx_ssthresh = max(hc->tx_ssthresh, + (hc->tx_cwnd >> 1) + (hc->tx_cwnd >> 2)); + hc->tx_cwnd = (hc->tx_cwnd + win_used) >> 1; + } + hc->tx_cwnd_used = 0; + hc->tx_cwnd_stamp = now; + + ccid2_check_l_ack_ratio(sk); +} + +/* This borrows the code of tcp_cwnd_restart() */ +static void ccid2_cwnd_restart(struct sock *sk, const u32 now) { - struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); + struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk); + u32 cwnd = hc->tx_cwnd, restart_cwnd, + iwnd = rfc3390_bytes_to_packets(dccp_sk(sk)->dccps_mss_cache); + + hc->tx_ssthresh = max(hc->tx_ssthresh, (cwnd >> 1) + (cwnd >> 2)); + + /* don't reduce cwnd below the initial window (IW) */ + restart_cwnd = min(cwnd, iwnd); + cwnd >>= (now - hc->tx_lsndtime) / hc->tx_rto; + hc->tx_cwnd = max(cwnd, restart_cwnd); - ccid2_pr_debug("setting RTO timeout=%ld\n", hctx->ccid2hctx_rto); + hc->tx_cwnd_stamp = now; + hc->tx_cwnd_used = 0; - BUG_ON(timer_pending(&hctx->ccid2hctx_rtotimer)); - sk_reset_timer(sk, &hctx->ccid2hctx_rtotimer, - jiffies + hctx->ccid2hctx_rto); + ccid2_check_l_ack_ratio(sk); } -static void ccid2_hc_tx_packet_sent(struct sock *sk, int more, int len) +static void ccid2_hc_tx_packet_sent(struct sock *sk, unsigned int len) { struct dccp_sock *dp = dccp_sk(sk); - struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); + struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk); + const u32 now = ccid2_time_stamp; struct ccid2_seq *next; - u64 seq; - ccid2_hc_tx_check_sanity(hctx); + /* slow-start after idle periods (RFC 2581, RFC 2861) */ + if (ccid2_do_cwv && !hc->tx_pipe && + (s32)(now - hc->tx_lsndtime) >= hc->tx_rto) + ccid2_cwnd_restart(sk, now); - BUG_ON(!hctx->ccid2hctx_sendwait); - hctx->ccid2hctx_sendwait = 0; - ccid2_change_pipe(hctx, hctx->ccid2hctx_pipe + 1); - BUG_ON(hctx->ccid2hctx_pipe < 0); + hc->tx_lsndtime = now; + hc->tx_pipe += 1; - /* There is an issue. What if another packet is sent between - * packet_send() and packet_sent(). Then the sequence number would be - * wrong. - * -sorbo. - */ - seq = dp->dccps_gss; + /* see whether cwnd was fully used (RFC 2861), update expected window */ + if (ccid2_cwnd_network_limited(hc)) { + ccid2_update_used_window(hc, hc->tx_cwnd); + hc->tx_cwnd_used = 0; + hc->tx_cwnd_stamp = now; + } else { + if (hc->tx_pipe > hc->tx_cwnd_used) + hc->tx_cwnd_used = hc->tx_pipe; - hctx->ccid2hctx_seqh->ccid2s_seq = seq; - hctx->ccid2hctx_seqh->ccid2s_acked = 0; - hctx->ccid2hctx_seqh->ccid2s_sent = jiffies; + ccid2_update_used_window(hc, hc->tx_cwnd_used); - next = hctx->ccid2hctx_seqh->ccid2s_next; - /* check if we need to alloc more space */ - if (next == hctx->ccid2hctx_seqt) { - int rc; + if (ccid2_do_cwv && (s32)(now - hc->tx_cwnd_stamp) >= hc->tx_rto) + ccid2_cwnd_application_limited(sk, now); + } - ccid2_pr_debug("allocating more space in history\n"); - rc = ccid2_hc_tx_alloc_seq(hctx, CCID2_SEQBUF_LEN, GFP_KERNEL); - BUG_ON(rc); /* XXX what do we do? */ + hc->tx_seqh->ccid2s_seq = dp->dccps_gss; + hc->tx_seqh->ccid2s_acked = 0; + hc->tx_seqh->ccid2s_sent = now; - next = hctx->ccid2hctx_seqh->ccid2s_next; - BUG_ON(next == hctx->ccid2hctx_seqt); + next = hc->tx_seqh->ccid2s_next; + /* check if we need to alloc more space */ + if (next == hc->tx_seqt) { + if (ccid2_hc_tx_alloc_seq(hc)) { + DCCP_CRIT("packet history - out of memory!"); + /* FIXME: find a more graceful way to bail out */ + return; + } + next = hc->tx_seqh->ccid2s_next; + BUG_ON(next == hc->tx_seqt); } - hctx->ccid2hctx_seqh = next; + hc->tx_seqh = next; - ccid2_pr_debug("cwnd=%d pipe=%d\n", hctx->ccid2hctx_cwnd, - hctx->ccid2hctx_pipe); - - hctx->ccid2hctx_sent++; + ccid2_pr_debug("cwnd=%d pipe=%d\n", hc->tx_cwnd, hc->tx_pipe); + /* + * FIXME: The code below is broken and the variables have been removed + * from the socket struct. The `ackloss' variable was always set to 0, + * and with arsent there are several problems: + * (i) it doesn't just count the number of Acks, but all sent packets; + * (ii) it is expressed in # of packets, not # of windows, so the + * comparison below uses the wrong formula: Appendix A of RFC 4341 + * comes up with the number K = cwnd / (R^2 - R) of consecutive windows + * of data with no lost or marked Ack packets. If arsent were the # of + * consecutive Acks received without loss, then Ack Ratio needs to be + * decreased by 1 when + * arsent >= K * cwnd / R = cwnd^2 / (R^3 - R^2) + * where cwnd / R is the number of Acks received per window of data + * (cf. RFC 4341, App. A). The problems are that + * - arsent counts other packets as well; + * - the comparison uses a formula different from RFC 4341; + * - computing a cubic/quadratic equation each time is too complicated. + * Hence a different algorithm is needed. + */ +#if 0 /* Ack Ratio. Need to maintain a concept of how many windows we sent */ - hctx->ccid2hctx_arsent++; + hc->tx_arsent++; /* We had an ack loss in this window... */ - if (hctx->ccid2hctx_ackloss) { - if (hctx->ccid2hctx_arsent >= hctx->ccid2hctx_cwnd) { - hctx->ccid2hctx_arsent = 0; - hctx->ccid2hctx_ackloss = 0; + if (hc->tx_ackloss) { + if (hc->tx_arsent >= hc->tx_cwnd) { + hc->tx_arsent = 0; + hc->tx_ackloss = 0; } } else { /* No acks lost up to now... */ @@ -334,246 +314,203 @@ static void ccid2_hc_tx_packet_sent(struct sock *sk, int more, int len) int denom = dp->dccps_l_ack_ratio * dp->dccps_l_ack_ratio - dp->dccps_l_ack_ratio; - denom = hctx->ccid2hctx_cwnd * hctx->ccid2hctx_cwnd / denom; + denom = hc->tx_cwnd * hc->tx_cwnd / denom; - if (hctx->ccid2hctx_arsent >= denom) { + if (hc->tx_arsent >= denom) { ccid2_change_l_ack_ratio(sk, dp->dccps_l_ack_ratio - 1); - hctx->ccid2hctx_arsent = 0; + hc->tx_arsent = 0; } } else { /* we can't increase ack ratio further [1] */ - hctx->ccid2hctx_arsent = 0; /* or maybe set it to cwnd*/ + hc->tx_arsent = 0; /* or maybe set it to cwnd*/ } } +#endif - /* setup RTO timer */ - if (!timer_pending(&hctx->ccid2hctx_rtotimer)) - ccid2_start_rto_timer(sk); + sk_reset_timer(sk, &hc->tx_rtotimer, jiffies + hc->tx_rto); #ifdef CONFIG_IP_DCCP_CCID2_DEBUG - ccid2_pr_debug("pipe=%d\n", hctx->ccid2hctx_pipe); - ccid2_pr_debug("Sent: seq=%llu\n", seq); do { - struct ccid2_seq *seqp = hctx->ccid2hctx_seqt; + struct ccid2_seq *seqp = hc->tx_seqt; - while (seqp != hctx->ccid2hctx_seqh) { - ccid2_pr_debug("out seq=%llu acked=%d time=%lu\n", - seqp->ccid2s_seq, seqp->ccid2s_acked, - seqp->ccid2s_sent); + while (seqp != hc->tx_seqh) { + ccid2_pr_debug("out seq=%llu acked=%d time=%u\n", + (unsigned long long)seqp->ccid2s_seq, + seqp->ccid2s_acked, seqp->ccid2s_sent); seqp = seqp->ccid2s_next; } } while (0); ccid2_pr_debug("=========\n"); - ccid2_hc_tx_check_sanity(hctx); #endif } -/* XXX Lame code duplication! - * returns -1 if none was found. - * else returns the next offset to use in the function call. +/** + * ccid2_rtt_estimator - Sample RTT and compute RTO using RFC2988 algorithm + * This code is almost identical with TCP's tcp_rtt_estimator(), since + * - it has a higher sampling frequency (recommended by RFC 1323), + * - the RTO does not collapse into RTT due to RTTVAR going towards zero, + * - it is simple (cf. more complex proposals such as Eifel timer or research + * which suggests that the gain should be set according to window size), + * - in tests it was found to work well with CCID2 [gerrit]. */ -static int ccid2_ackvector(struct sock *sk, struct sk_buff *skb, int offset, - unsigned char **vec, unsigned char *veclen) +static void ccid2_rtt_estimator(struct sock *sk, const long mrtt) { - const struct dccp_hdr *dh = dccp_hdr(skb); - unsigned char *options = (unsigned char *)dh + dccp_hdr_len(skb); - unsigned char *opt_ptr; - const unsigned char *opt_end = (unsigned char *)dh + - (dh->dccph_doff * 4); - unsigned char opt, len; - unsigned char *value; - - BUG_ON(offset < 0); - options += offset; - opt_ptr = options; - if (opt_ptr >= opt_end) - return -1; - - while (opt_ptr != opt_end) { - opt = *opt_ptr++; - len = 0; - value = NULL; - - /* Check if this isn't a single byte option */ - if (opt > DCCPO_MAX_RESERVED) { - if (opt_ptr == opt_end) - goto out_invalid_option; - - len = *opt_ptr++; - if (len < 3) - goto out_invalid_option; - /* - * Remove the type and len fields, leaving - * just the value size - */ - len -= 2; - value = opt_ptr; - opt_ptr += len; - - if (opt_ptr > opt_end) - goto out_invalid_option; - } - - switch (opt) { - case DCCPO_ACK_VECTOR_0: - case DCCPO_ACK_VECTOR_1: - *vec = value; - *veclen = len; - return offset + (opt_ptr - options); - } - } + struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk); + long m = mrtt ? : 1; - return -1; + if (hc->tx_srtt == 0) { + /* First measurement m */ + hc->tx_srtt = m << 3; + hc->tx_mdev = m << 1; -out_invalid_option: - BUG_ON(1); /* should never happen... options were previously parsed ! */ - return -1; -} - -static void ccid2_hc_tx_kill_rto_timer(struct sock *sk) -{ - struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); - - sk_stop_timer(sk, &hctx->ccid2hctx_rtotimer); - ccid2_pr_debug("deleted RTO timer\n"); -} + hc->tx_mdev_max = max(hc->tx_mdev, tcp_rto_min(sk)); + hc->tx_rttvar = hc->tx_mdev_max; -static inline void ccid2_new_ack(struct sock *sk, - struct ccid2_seq *seqp, - unsigned int *maxincr) -{ - struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); - - /* slow start */ - if (hctx->ccid2hctx_cwnd < hctx->ccid2hctx_ssthresh) { - hctx->ccid2hctx_acks = 0; - - /* We can increase cwnd at most maxincr [ack_ratio/2] */ - if (*maxincr) { - /* increase every 2 acks */ - hctx->ccid2hctx_ssacks++; - if (hctx->ccid2hctx_ssacks == 2) { - ccid2_change_cwnd(hctx, hctx->ccid2hctx_cwnd+1); - hctx->ccid2hctx_ssacks = 0; - *maxincr = *maxincr - 1; - } + hc->tx_rtt_seq = dccp_sk(sk)->dccps_gss; + } else { + /* Update scaled SRTT as SRTT += 1/8 * (m - SRTT) */ + m -= (hc->tx_srtt >> 3); + hc->tx_srtt += m; + + /* Similarly, update scaled mdev with regard to |m| */ + if (m < 0) { + m = -m; + m -= (hc->tx_mdev >> 2); + /* + * This neutralises RTO increase when RTT < SRTT - mdev + * (see P. Sarolahti, A. Kuznetsov,"Congestion Control + * in Linux TCP", USENIX 2002, pp. 49-62). + */ + if (m > 0) + m >>= 3; } else { - /* increased cwnd enough for this single ack */ - hctx->ccid2hctx_ssacks = 0; + m -= (hc->tx_mdev >> 2); } - } else { - hctx->ccid2hctx_ssacks = 0; - hctx->ccid2hctx_acks++; + hc->tx_mdev += m; - if (hctx->ccid2hctx_acks >= hctx->ccid2hctx_cwnd) { - ccid2_change_cwnd(hctx, hctx->ccid2hctx_cwnd + 1); - hctx->ccid2hctx_acks = 0; + if (hc->tx_mdev > hc->tx_mdev_max) { + hc->tx_mdev_max = hc->tx_mdev; + if (hc->tx_mdev_max > hc->tx_rttvar) + hc->tx_rttvar = hc->tx_mdev_max; } - } - /* update RTO */ - if (hctx->ccid2hctx_srtt == -1 || - time_after(jiffies, hctx->ccid2hctx_lastrtt + hctx->ccid2hctx_srtt)) { - unsigned long r = (long)jiffies - (long)seqp->ccid2s_sent; - int s; - - /* first measurement */ - if (hctx->ccid2hctx_srtt == -1) { - ccid2_pr_debug("R: %lu Time=%lu seq=%llu\n", - r, jiffies, seqp->ccid2s_seq); - ccid2_change_srtt(hctx, r); - hctx->ccid2hctx_rttvar = r >> 1; - } else { - /* RTTVAR */ - long tmp = hctx->ccid2hctx_srtt - r; - long srtt; - - if (tmp < 0) - tmp *= -1; - - tmp >>= 2; - hctx->ccid2hctx_rttvar *= 3; - hctx->ccid2hctx_rttvar >>= 2; - hctx->ccid2hctx_rttvar += tmp; - - /* SRTT */ - srtt = hctx->ccid2hctx_srtt; - srtt *= 7; - srtt >>= 3; - tmp = r >> 3; - srtt += tmp; - ccid2_change_srtt(hctx, srtt); + /* + * Decay RTTVAR at most once per flight, exploiting that + * 1) pipe <= cwnd <= Sequence_Window = W (RFC 4340, 7.5.2) + * 2) AWL = GSS-W+1 <= GAR <= GSS (RFC 4340, 7.5.1) + * GAR is a useful bound for FlightSize = pipe. + * AWL is probably too low here, as it over-estimates pipe. + */ + if (after48(dccp_sk(sk)->dccps_gar, hc->tx_rtt_seq)) { + if (hc->tx_mdev_max < hc->tx_rttvar) + hc->tx_rttvar -= (hc->tx_rttvar - + hc->tx_mdev_max) >> 2; + hc->tx_rtt_seq = dccp_sk(sk)->dccps_gss; + hc->tx_mdev_max = tcp_rto_min(sk); } - s = hctx->ccid2hctx_rttvar << 2; - /* clock granularity is 1 when based on jiffies */ - if (!s) - s = 1; - hctx->ccid2hctx_rto = hctx->ccid2hctx_srtt + s; - - /* must be at least a second */ - s = hctx->ccid2hctx_rto / HZ; - /* DCCP doesn't require this [but I like it cuz my code sux] */ -#if 1 - if (s < 1) - hctx->ccid2hctx_rto = HZ; -#endif - /* max 60 seconds */ - if (s > 60) - hctx->ccid2hctx_rto = HZ * 60; - - hctx->ccid2hctx_lastrtt = jiffies; - - ccid2_pr_debug("srtt: %ld rttvar: %ld rto: %ld (HZ=%d) R=%lu\n", - hctx->ccid2hctx_srtt, hctx->ccid2hctx_rttvar, - hctx->ccid2hctx_rto, HZ, r); - hctx->ccid2hctx_sent = 0; } - /* we got a new ack, so re-start RTO timer */ - ccid2_hc_tx_kill_rto_timer(sk); - ccid2_start_rto_timer(sk); + /* + * Set RTO from SRTT and RTTVAR + * As in TCP, 4 * RTTVAR >= TCP_RTO_MIN, giving a minimum RTO of 200 ms. + * This agrees with RFC 4341, 5: + * "Because DCCP does not retransmit data, DCCP does not require + * TCP's recommended minimum timeout of one second". + */ + hc->tx_rto = (hc->tx_srtt >> 3) + hc->tx_rttvar; + + if (hc->tx_rto > DCCP_RTO_MAX) + hc->tx_rto = DCCP_RTO_MAX; } -static void ccid2_hc_tx_dec_pipe(struct sock *sk) +static void ccid2_new_ack(struct sock *sk, struct ccid2_seq *seqp, + unsigned int *maxincr) { - struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); + struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk); + struct dccp_sock *dp = dccp_sk(sk); + int r_seq_used = hc->tx_cwnd / dp->dccps_l_ack_ratio; + + if (hc->tx_cwnd < dp->dccps_l_seq_win && + r_seq_used < dp->dccps_r_seq_win) { + if (hc->tx_cwnd < hc->tx_ssthresh) { + if (*maxincr > 0 && ++hc->tx_packets_acked >= 2) { + hc->tx_cwnd += 1; + *maxincr -= 1; + hc->tx_packets_acked = 0; + } + } else if (++hc->tx_packets_acked >= hc->tx_cwnd) { + hc->tx_cwnd += 1; + hc->tx_packets_acked = 0; + } + } - ccid2_change_pipe(hctx, hctx->ccid2hctx_pipe-1); - BUG_ON(hctx->ccid2hctx_pipe < 0); + /* + * Adjust the local sequence window and the ack ratio to allow about + * 5 times the number of packets in the network (RFC 4340 7.5.2) + */ + if (r_seq_used * CCID2_WIN_CHANGE_FACTOR >= dp->dccps_r_seq_win) + ccid2_change_l_ack_ratio(sk, dp->dccps_l_ack_ratio * 2); + else if (r_seq_used * CCID2_WIN_CHANGE_FACTOR < dp->dccps_r_seq_win/2) + ccid2_change_l_ack_ratio(sk, dp->dccps_l_ack_ratio / 2 ? : 1U); + + if (hc->tx_cwnd * CCID2_WIN_CHANGE_FACTOR >= dp->dccps_l_seq_win) + ccid2_change_l_seq_window(sk, dp->dccps_l_seq_win * 2); + else if (hc->tx_cwnd * CCID2_WIN_CHANGE_FACTOR < dp->dccps_l_seq_win/2) + ccid2_change_l_seq_window(sk, dp->dccps_l_seq_win / 2); - if (hctx->ccid2hctx_pipe == 0) - ccid2_hc_tx_kill_rto_timer(sk); + /* + * FIXME: RTT is sampled several times per acknowledgment (for each + * entry in the Ack Vector), instead of once per Ack (as in TCP SACK). + * This causes the RTT to be over-estimated, since the older entries + * in the Ack Vector have earlier sending times. + * The cleanest solution is to not use the ccid2s_sent field at all + * and instead use DCCP timestamps: requires changes in other places. + */ + ccid2_rtt_estimator(sk, ccid2_time_stamp - seqp->ccid2s_sent); } -static void ccid2_congestion_event(struct ccid2_hc_tx_sock *hctx, - struct ccid2_seq *seqp) +static void ccid2_congestion_event(struct sock *sk, struct ccid2_seq *seqp) { - if (time_before(seqp->ccid2s_sent, hctx->ccid2hctx_last_cong)) { + struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk); + + if ((s32)(seqp->ccid2s_sent - hc->tx_last_cong) < 0) { ccid2_pr_debug("Multiple losses in an RTT---treating as one\n"); return; } - hctx->ccid2hctx_last_cong = jiffies; + hc->tx_last_cong = ccid2_time_stamp; + + hc->tx_cwnd = hc->tx_cwnd / 2 ? : 1U; + hc->tx_ssthresh = max(hc->tx_cwnd, 2U); - ccid2_change_cwnd(hctx, hctx->ccid2hctx_cwnd >> 1); - hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd; - if (hctx->ccid2hctx_ssthresh < 2) - hctx->ccid2hctx_ssthresh = 2; + ccid2_check_l_ack_ratio(sk); +} + +static int ccid2_hc_tx_parse_options(struct sock *sk, u8 packet_type, + u8 option, u8 *optval, u8 optlen) +{ + struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk); + + switch (option) { + case DCCPO_ACK_VECTOR_0: + case DCCPO_ACK_VECTOR_1: + return dccp_ackvec_parsed_add(&hc->tx_av_chunks, optval, optlen, + option - DCCPO_ACK_VECTOR_0); + } + return 0; } static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) { struct dccp_sock *dp = dccp_sk(sk); - struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); + struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk); + const bool sender_was_blocked = ccid2_cwnd_network_limited(hc); + struct dccp_ackvec_parsed *avp; u64 ackno, seqno; struct ccid2_seq *seqp; - unsigned char *vector; - unsigned char veclen; - int offset = 0; int done = 0; unsigned int maxincr = 0; - ccid2_hc_tx_check_sanity(hctx); /* check reverse path congestion */ seqno = DCCP_SKB_CB(skb)->dccpd_seq; @@ -582,68 +519,81 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) * -sorbo. */ /* need to bootstrap */ - if (hctx->ccid2hctx_rpdupack == -1) { - hctx->ccid2hctx_rpdupack = 0; - hctx->ccid2hctx_rpseq = seqno; + if (hc->tx_rpdupack == -1) { + hc->tx_rpdupack = 0; + hc->tx_rpseq = seqno; } else { /* check if packet is consecutive */ - if ((hctx->ccid2hctx_rpseq + 1) == seqno) - hctx->ccid2hctx_rpseq++; + if (dccp_delta_seqno(hc->tx_rpseq, seqno) == 1) + hc->tx_rpseq = seqno; /* it's a later packet */ - else if (after48(seqno, hctx->ccid2hctx_rpseq)) { - hctx->ccid2hctx_rpdupack++; + else if (after48(seqno, hc->tx_rpseq)) { + hc->tx_rpdupack++; /* check if we got enough dupacks */ - if (hctx->ccid2hctx_rpdupack >= - hctx->ccid2hctx_numdupack) { - hctx->ccid2hctx_rpdupack = -1; /* XXX lame */ - hctx->ccid2hctx_rpseq = 0; - - ccid2_change_l_ack_ratio(sk, dp->dccps_l_ack_ratio << 1); + if (hc->tx_rpdupack >= NUMDUPACK) { + hc->tx_rpdupack = -1; /* XXX lame */ + hc->tx_rpseq = 0; +#ifdef __CCID2_COPES_GRACEFULLY_WITH_ACK_CONGESTION_CONTROL__ + /* + * FIXME: Ack Congestion Control is broken; in + * the current state instabilities occurred with + * Ack Ratios greater than 1; causing hang-ups + * and long RTO timeouts. This needs to be fixed + * before opening up dynamic changes. -- gerrit + */ + ccid2_change_l_ack_ratio(sk, 2 * dp->dccps_l_ack_ratio); +#endif } } } /* check forward path congestion */ - /* still didn't send out new data packets */ - if (hctx->ccid2hctx_seqh == hctx->ccid2hctx_seqt) + if (dccp_packet_without_ack(skb)) return; - switch (DCCP_SKB_CB(skb)->dccpd_type) { - case DCCP_PKT_ACK: - case DCCP_PKT_DATAACK: - break; - default: - return; - } + /* still didn't send out new data packets */ + if (hc->tx_seqh == hc->tx_seqt) + goto done; ackno = DCCP_SKB_CB(skb)->dccpd_ack_seq; - seqp = hctx->ccid2hctx_seqh->ccid2s_prev; + if (after48(ackno, hc->tx_high_ack)) + hc->tx_high_ack = ackno; + + seqp = hc->tx_seqt; + while (before48(seqp->ccid2s_seq, ackno)) { + seqp = seqp->ccid2s_next; + if (seqp == hc->tx_seqh) { + seqp = hc->tx_seqh->ccid2s_prev; + break; + } + } - /* If in slow-start, cwnd can increase at most Ack Ratio / 2 packets for - * this single ack. I round up. - * -sorbo. + /* + * In slow-start, cwnd can increase up to a maximum of Ack Ratio/2 + * packets per acknowledgement. Rounding up avoids that cwnd is not + * advanced when Ack Ratio is 1 and gives a slight edge otherwise. */ - maxincr = dp->dccps_l_ack_ratio >> 1; - maxincr++; + if (hc->tx_cwnd < hc->tx_ssthresh) + maxincr = DIV_ROUND_UP(dp->dccps_l_ack_ratio, 2); /* go through all ack vectors */ - while ((offset = ccid2_ackvector(sk, skb, offset, - &vector, &veclen)) != -1) { + list_for_each_entry(avp, &hc->tx_av_chunks, node) { /* go through this ack vector */ - while (veclen--) { - const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK; - u64 ackno_end_rl; - - dccp_set_seqno(&ackno_end_rl, ackno - rl); - ccid2_pr_debug("ackvec start:%llu end:%llu\n", ackno, - ackno_end_rl); + for (; avp->len--; avp->vec++) { + u64 ackno_end_rl = SUB48(ackno, + dccp_ackvec_runlen(avp->vec)); + + ccid2_pr_debug("ackvec %llu |%u,%u|\n", + (unsigned long long)ackno, + dccp_ackvec_state(avp->vec) >> 6, + dccp_ackvec_runlen(avp->vec)); /* if the seqno we are analyzing is larger than the * current ackno, then move towards the tail of our * seqnos. */ while (after48(seqp->ccid2s_seq, ackno)) { - if (seqp == hctx->ccid2hctx_seqt) { + if (seqp == hc->tx_seqt) { done = 1; break; } @@ -656,37 +606,33 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) * run length */ while (between48(seqp->ccid2s_seq,ackno_end_rl,ackno)) { - const u8 state = *vector & - DCCP_ACKVEC_STATE_MASK; + const u8 state = dccp_ackvec_state(avp->vec); /* new packet received or marked */ - if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED && + if (state != DCCPAV_NOT_RECEIVED && !seqp->ccid2s_acked) { - if (state == - DCCP_ACKVEC_STATE_ECN_MARKED) { - ccid2_congestion_event(hctx, + if (state == DCCPAV_ECN_MARKED) + ccid2_congestion_event(sk, seqp); - } else + else ccid2_new_ack(sk, seqp, &maxincr); seqp->ccid2s_acked = 1; ccid2_pr_debug("Got ack for %llu\n", - seqp->ccid2s_seq); - ccid2_hc_tx_dec_pipe(sk); + (unsigned long long)seqp->ccid2s_seq); + hc->tx_pipe--; } - if (seqp == hctx->ccid2hctx_seqt) { + if (seqp == hc->tx_seqt) { done = 1; break; } - seqp = seqp->ccid2s_next; + seqp = seqp->ccid2s_prev; } if (done) break; - - dccp_set_seqno(&ackno, ackno_end_rl - 1); - vector++; + ackno = SUB48(ackno_end_rl, 1); } if (done) break; @@ -695,15 +641,22 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) /* The state about what is acked should be correct now * Check for NUMDUPACK */ - seqp = hctx->ccid2hctx_seqh->ccid2s_prev; + seqp = hc->tx_seqt; + while (before48(seqp->ccid2s_seq, hc->tx_high_ack)) { + seqp = seqp->ccid2s_next; + if (seqp == hc->tx_seqh) { + seqp = hc->tx_seqh->ccid2s_prev; + break; + } + } done = 0; while (1) { if (seqp->ccid2s_acked) { done++; - if (done == hctx->ccid2hctx_numdupack) + if (done == NUMDUPACK) break; } - if (seqp == hctx->ccid2hctx_seqt) + if (seqp == hc->tx_seqt) break; seqp = seqp->ccid2s_prev; } @@ -711,132 +664,121 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) /* If there are at least 3 acknowledgements, anything unacknowledged * below the last sequence number is considered lost */ - if (done == hctx->ccid2hctx_numdupack) { + if (done == NUMDUPACK) { struct ccid2_seq *last_acked = seqp; /* check for lost packets */ while (1) { if (!seqp->ccid2s_acked) { ccid2_pr_debug("Packet lost: %llu\n", - seqp->ccid2s_seq); + (unsigned long long)seqp->ccid2s_seq); /* XXX need to traverse from tail -> head in * order to detect multiple congestion events in * one ack vector. */ - ccid2_congestion_event(hctx, seqp); - ccid2_hc_tx_dec_pipe(sk); + ccid2_congestion_event(sk, seqp); + hc->tx_pipe--; } - if (seqp == hctx->ccid2hctx_seqt) + if (seqp == hc->tx_seqt) break; seqp = seqp->ccid2s_prev; } - hctx->ccid2hctx_seqt = last_acked; + hc->tx_seqt = last_acked; } /* trim acked packets in tail */ - while (hctx->ccid2hctx_seqt != hctx->ccid2hctx_seqh) { - if (!hctx->ccid2hctx_seqt->ccid2s_acked) + while (hc->tx_seqt != hc->tx_seqh) { + if (!hc->tx_seqt->ccid2s_acked) break; - hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqt->ccid2s_next; + hc->tx_seqt = hc->tx_seqt->ccid2s_next; } - ccid2_hc_tx_check_sanity(hctx); + /* restart RTO timer if not all outstanding data has been acked */ + if (hc->tx_pipe == 0) + sk_stop_timer(sk, &hc->tx_rtotimer); + else + sk_reset_timer(sk, &hc->tx_rtotimer, jiffies + hc->tx_rto); +done: + /* check if incoming Acks allow pending packets to be sent */ + if (sender_was_blocked && !ccid2_cwnd_network_limited(hc)) + tasklet_schedule(&dccp_sk(sk)->dccps_xmitlet); + dccp_ackvec_parsed_cleanup(&hc->tx_av_chunks); } static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk) { - struct ccid2_hc_tx_sock *hctx = ccid_priv(ccid); + struct ccid2_hc_tx_sock *hc = ccid_priv(ccid); + struct dccp_sock *dp = dccp_sk(sk); + u32 max_ratio; - ccid2_change_cwnd(hctx, 1); - /* Initialize ssthresh to infinity. This means that we will exit the - * initial slow-start after the first packet loss. This is what we - * want. - */ - hctx->ccid2hctx_ssthresh = ~0; - hctx->ccid2hctx_numdupack = 3; - hctx->ccid2hctx_seqbufc = 0; + /* RFC 4341, 5: initialise ssthresh to arbitrarily high (max) value */ + hc->tx_ssthresh = ~0U; - /* XXX init ~ to window size... */ - if (ccid2_hc_tx_alloc_seq(hctx, CCID2_SEQBUF_LEN, GFP_ATOMIC) != 0) - return -ENOMEM; + /* Use larger initial windows (RFC 4341, section 5). */ + hc->tx_cwnd = rfc3390_bytes_to_packets(dp->dccps_mss_cache); + hc->tx_expected_wnd = hc->tx_cwnd; - hctx->ccid2hctx_sent = 0; - hctx->ccid2hctx_rto = 3 * HZ; - ccid2_change_srtt(hctx, -1); - hctx->ccid2hctx_rttvar = -1; - hctx->ccid2hctx_lastrtt = 0; - hctx->ccid2hctx_rpdupack = -1; - hctx->ccid2hctx_last_cong = jiffies; + /* Make sure that Ack Ratio is enabled and within bounds. */ + max_ratio = DIV_ROUND_UP(hc->tx_cwnd, 2); + if (dp->dccps_l_ack_ratio == 0 || dp->dccps_l_ack_ratio > max_ratio) + dp->dccps_l_ack_ratio = max_ratio; - hctx->ccid2hctx_rtotimer.function = &ccid2_hc_tx_rto_expire; - hctx->ccid2hctx_rtotimer.data = (unsigned long)sk; - init_timer(&hctx->ccid2hctx_rtotimer); + /* XXX init ~ to window size... */ + if (ccid2_hc_tx_alloc_seq(hc)) + return -ENOMEM; - ccid2_hc_tx_check_sanity(hctx); + hc->tx_rto = DCCP_TIMEOUT_INIT; + hc->tx_rpdupack = -1; + hc->tx_last_cong = hc->tx_lsndtime = hc->tx_cwnd_stamp = ccid2_time_stamp; + hc->tx_cwnd_used = 0; + setup_timer(&hc->tx_rtotimer, ccid2_hc_tx_rto_expire, + (unsigned long)sk); + INIT_LIST_HEAD(&hc->tx_av_chunks); return 0; } static void ccid2_hc_tx_exit(struct sock *sk) { - struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); + struct ccid2_hc_tx_sock *hc = ccid2_hc_tx_sk(sk); int i; - ccid2_hc_tx_kill_rto_timer(sk); + sk_stop_timer(sk, &hc->tx_rtotimer); - for (i = 0; i < hctx->ccid2hctx_seqbufc; i++) - kfree(hctx->ccid2hctx_seqbuf[i]); - hctx->ccid2hctx_seqbufc = 0; + for (i = 0; i < hc->tx_seqbufc; i++) + kfree(hc->tx_seqbuf[i]); + hc->tx_seqbufc = 0; } static void ccid2_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) { - const struct dccp_sock *dp = dccp_sk(sk); - struct ccid2_hc_rx_sock *hcrx = ccid2_hc_rx_sk(sk); - - switch (DCCP_SKB_CB(skb)->dccpd_type) { - case DCCP_PKT_DATA: - case DCCP_PKT_DATAACK: - hcrx->ccid2hcrx_data++; - if (hcrx->ccid2hcrx_data >= dp->dccps_r_ack_ratio) { - dccp_send_ack(sk); - hcrx->ccid2hcrx_data = 0; - } - break; - } -} - -static struct ccid_operations ccid2 = { - .ccid_id = DCCPC_CCID2, - .ccid_name = "ccid2", - .ccid_owner = THIS_MODULE, - .ccid_hc_tx_obj_size = sizeof(struct ccid2_hc_tx_sock), - .ccid_hc_tx_init = ccid2_hc_tx_init, - .ccid_hc_tx_exit = ccid2_hc_tx_exit, - .ccid_hc_tx_send_packet = ccid2_hc_tx_send_packet, - .ccid_hc_tx_packet_sent = ccid2_hc_tx_packet_sent, - .ccid_hc_tx_packet_recv = ccid2_hc_tx_packet_recv, - .ccid_hc_rx_obj_size = sizeof(struct ccid2_hc_rx_sock), - .ccid_hc_rx_packet_recv = ccid2_hc_rx_packet_recv, -}; + struct ccid2_hc_rx_sock *hc = ccid2_hc_rx_sk(sk); -module_param(ccid2_debug, int, 0444); -MODULE_PARM_DESC(ccid2_debug, "Enable debug messages"); + if (!dccp_data_packet(skb)) + return; -static __init int ccid2_module_init(void) -{ - return ccid_register(&ccid2); + if (++hc->rx_num_data_pkts >= dccp_sk(sk)->dccps_r_ack_ratio) { + dccp_send_ack(sk); + hc->rx_num_data_pkts = 0; + } } -module_init(ccid2_module_init); -static __exit void ccid2_module_exit(void) -{ - ccid_unregister(&ccid2); -} -module_exit(ccid2_module_exit); +struct ccid_operations ccid2_ops = { + .ccid_id = DCCPC_CCID2, + .ccid_name = "TCP-like", + .ccid_hc_tx_obj_size = sizeof(struct ccid2_hc_tx_sock), + .ccid_hc_tx_init = ccid2_hc_tx_init, + .ccid_hc_tx_exit = ccid2_hc_tx_exit, + .ccid_hc_tx_send_packet = ccid2_hc_tx_send_packet, + .ccid_hc_tx_packet_sent = ccid2_hc_tx_packet_sent, + .ccid_hc_tx_parse_options = ccid2_hc_tx_parse_options, + .ccid_hc_tx_packet_recv = ccid2_hc_tx_packet_recv, + .ccid_hc_rx_obj_size = sizeof(struct ccid2_hc_rx_sock), + .ccid_hc_rx_packet_recv = ccid2_hc_rx_packet_recv, +}; -MODULE_AUTHOR("Andrea Bittau <a.bittau@cs.ucl.ac.uk>"); -MODULE_DESCRIPTION("DCCP TCP-Like (CCID2) CCID"); -MODULE_LICENSE("GPL"); -MODULE_ALIAS("net-dccp-ccid-2"); +#ifdef CONFIG_IP_DCCP_CCID2_DEBUG +module_param(ccid2_debug, bool, 0644); +MODULE_PARM_DESC(ccid2_debug, "Enable CCID-2 debug messages"); +#endif diff --git a/net/dccp/ccids/ccid2.h b/net/dccp/ccids/ccid2.h index 5b2ef4acb30..18c97543e52 100644 --- a/net/dccp/ccids/ccid2.h +++ b/net/dccp/ccids/ccid2.h @@ -1,6 +1,4 @@ /* - * net/dccp/ccids/ccid2.h - * * Copyright (c) 2005 Andrea Bittau <a.bittau@cs.ucl.ac.uk> * * This program is free software; you can redistribute it and/or modify @@ -20,62 +18,107 @@ #ifndef _DCCP_CCID2_H_ #define _DCCP_CCID2_H_ -#include <linux/dccp.h> #include <linux/timer.h> #include <linux/types.h> #include "../ccid.h" +#include "../dccp.h" + +/* + * CCID-2 timestamping faces the same issues as TCP timestamping. + * Hence we reuse/share as much of the code as possible. + */ +#define ccid2_time_stamp tcp_time_stamp -struct sock; +/* NUMDUPACK parameter from RFC 4341, p. 6 */ +#define NUMDUPACK 3 struct ccid2_seq { u64 ccid2s_seq; - unsigned long ccid2s_sent; + u32 ccid2s_sent; int ccid2s_acked; struct ccid2_seq *ccid2s_prev; struct ccid2_seq *ccid2s_next; }; -#define CCID2_SEQBUF_LEN 256 +#define CCID2_SEQBUF_LEN 1024 #define CCID2_SEQBUF_MAX 128 -/** struct ccid2_hc_tx_sock - CCID2 TX half connection - * - * @ccid2hctx_ssacks - ACKs recv in slow start - * @ccid2hctx_acks - ACKS recv in AI phase - * @ccid2hctx_sent - packets sent in this window - * @ccid2hctx_lastrtt -time RTT was last measured - * @ccid2hctx_arsent - packets sent [ack ratio] - * @ccid2hctx_ackloss - ack was lost in this win - * @ccid2hctx_rpseq - last consecutive seqno - * @ccid2hctx_rpdupack - dupacks since rpseq -*/ +/* + * Multiple of congestion window to keep the sequence window at + * (RFC 4340 7.5.2) + */ +#define CCID2_WIN_CHANGE_FACTOR 5 + +/** + * struct ccid2_hc_tx_sock - CCID2 TX half connection + * @tx_{cwnd,ssthresh,pipe}: as per RFC 4341, section 5 + * @tx_packets_acked: Ack counter for deriving cwnd growth (RFC 3465) + * @tx_srtt: smoothed RTT estimate, scaled by 2^3 + * @tx_mdev: smoothed RTT variation, scaled by 2^2 + * @tx_mdev_max: maximum of @mdev during one flight + * @tx_rttvar: moving average/maximum of @mdev_max + * @tx_rto: RTO value deriving from SRTT and RTTVAR (RFC 2988) + * @tx_rtt_seq: to decay RTTVAR at most once per flight + * @tx_cwnd_used: actually used cwnd, W_used of RFC 2861 + * @tx_expected_wnd: moving average of @tx_cwnd_used + * @tx_cwnd_stamp: to track idle periods in CWV + * @tx_lsndtime: last time (in jiffies) a data packet was sent + * @tx_rpseq: last consecutive seqno + * @tx_rpdupack: dupacks since rpseq + * @tx_av_chunks: list of Ack Vectors received on current skb + */ struct ccid2_hc_tx_sock { - int ccid2hctx_cwnd; - int ccid2hctx_ssacks; - int ccid2hctx_acks; - unsigned int ccid2hctx_ssthresh; - int ccid2hctx_pipe; - int ccid2hctx_numdupack; - struct ccid2_seq *ccid2hctx_seqbuf[CCID2_SEQBUF_MAX]; - int ccid2hctx_seqbufc; - struct ccid2_seq *ccid2hctx_seqh; - struct ccid2_seq *ccid2hctx_seqt; - long ccid2hctx_rto; - long ccid2hctx_srtt; - long ccid2hctx_rttvar; - int ccid2hctx_sent; - unsigned long ccid2hctx_lastrtt; - struct timer_list ccid2hctx_rtotimer; - unsigned long ccid2hctx_arsent; - int ccid2hctx_ackloss; - u64 ccid2hctx_rpseq; - int ccid2hctx_rpdupack; - int ccid2hctx_sendwait; - unsigned long ccid2hctx_last_cong; + u32 tx_cwnd; + u32 tx_ssthresh; + u32 tx_pipe; + u32 tx_packets_acked; + struct ccid2_seq *tx_seqbuf[CCID2_SEQBUF_MAX]; + int tx_seqbufc; + struct ccid2_seq *tx_seqh; + struct ccid2_seq *tx_seqt; + + /* RTT measurement: variables/principles are the same as in TCP */ + u32 tx_srtt, + tx_mdev, + tx_mdev_max, + tx_rttvar, + tx_rto; + u64 tx_rtt_seq:48; + struct timer_list tx_rtotimer; + + /* Congestion Window validation (optional, RFC 2861) */ + u32 tx_cwnd_used, + tx_expected_wnd, + tx_cwnd_stamp, + tx_lsndtime; + + u64 tx_rpseq; + int tx_rpdupack; + u32 tx_last_cong; + u64 tx_high_ack; + struct list_head tx_av_chunks; }; +static inline bool ccid2_cwnd_network_limited(struct ccid2_hc_tx_sock *hc) +{ + return hc->tx_pipe >= hc->tx_cwnd; +} + +/* + * Convert RFC 3390 larger initial window into an equivalent number of packets. + * This is based on the numbers specified in RFC 5681, 3.1. + */ +static inline u32 rfc3390_bytes_to_packets(const u32 smss) +{ + return smss <= 1095 ? 4 : (smss > 2190 ? 2 : 3); +} + +/** + * struct ccid2_hc_rx_sock - Receiving end of CCID-2 half-connection + * @rx_num_data_pkts: number of data packets received since last feedback + */ struct ccid2_hc_rx_sock { - int ccid2hcrx_data; + u32 rx_num_data_pkts; }; static inline struct ccid2_hc_tx_sock *ccid2_hc_tx_sk(const struct sock *sk) diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c index 67d2dc0e7c6..119c04317d4 100644 --- a/net/dccp/ccids/ccid3.c +++ b/net/dccp/ccids/ccid3.c @@ -1,8 +1,7 @@ /* - * net/dccp/ccids/ccid3.c - * - * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand. - * Copyright (c) 2005-6 Ian McDonald <ian.mcdonald@jandi.co.nz> + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK + * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. + * Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz> * * An implementation of the DCCP protocol * @@ -33,64 +32,28 @@ * along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ - -#include "../ccid.h" #include "../dccp.h" -#include "lib/packet_history.h" -#include "lib/loss_interval.h" -#include "lib/tfrc.h" #include "ccid3.h" -/* - * Reason for maths here is to avoid 32 bit overflow when a is big. - * With this we get close to the limit. - */ -static u32 usecs_div(const u32 a, const u32 b) -{ - const u32 div = a < (UINT_MAX / (USEC_PER_SEC / 10)) ? 10 : - a < (UINT_MAX / (USEC_PER_SEC / 50)) ? 50 : - a < (UINT_MAX / (USEC_PER_SEC / 100)) ? 100 : - a < (UINT_MAX / (USEC_PER_SEC / 500)) ? 500 : - a < (UINT_MAX / (USEC_PER_SEC / 1000)) ? 1000 : - a < (UINT_MAX / (USEC_PER_SEC / 5000)) ? 5000 : - a < (UINT_MAX / (USEC_PER_SEC / 10000)) ? 10000 : - a < (UINT_MAX / (USEC_PER_SEC / 50000)) ? 50000 : - 100000; - const u32 tmp = a * (USEC_PER_SEC / div); - return (b >= 2 * div) ? tmp / (b / div) : tmp; -} +#include <asm/unaligned.h> -static int ccid3_debug; - -#ifdef CCID3_DEBUG -#define ccid3_pr_debug(format, a...) \ - do { if (ccid3_debug) \ - printk(KERN_DEBUG "%s: " format, __FUNCTION__, ##a); \ - } while (0) +#ifdef CONFIG_IP_DCCP_CCID3_DEBUG +static bool ccid3_debug; +#define ccid3_pr_debug(format, a...) DCCP_PR_DEBUG(ccid3_debug, format, ##a) #else #define ccid3_pr_debug(format, a...) #endif -static struct dccp_tx_hist *ccid3_tx_hist; -static struct dccp_rx_hist *ccid3_rx_hist; -static struct dccp_li_hist *ccid3_li_hist; - -/* TFRC sender states */ -enum ccid3_hc_tx_states { - TFRC_SSTATE_NO_SENT = 1, - TFRC_SSTATE_NO_FBACK, - TFRC_SSTATE_FBACK, - TFRC_SSTATE_TERM, -}; - -#ifdef CCID3_DEBUG +/* + * Transmitter Half-Connection Routines + */ +#ifdef CONFIG_IP_DCCP_CCID3_DEBUG static const char *ccid3_tx_state_name(enum ccid3_hc_tx_states state) { - static char *ccid3_state_names[] = { + static const char *const ccid3_state_names[] = { [TFRC_SSTATE_NO_SENT] = "NO_SENT", [TFRC_SSTATE_NO_FBACK] = "NO_FBACK", [TFRC_SSTATE_FBACK] = "FBACK", - [TFRC_SSTATE_TERM] = "TERM", }; return ccid3_state_names[state]; @@ -100,609 +63,517 @@ static const char *ccid3_tx_state_name(enum ccid3_hc_tx_states state) static void ccid3_hc_tx_set_state(struct sock *sk, enum ccid3_hc_tx_states state) { - struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); - enum ccid3_hc_tx_states oldstate = hctx->ccid3hctx_state; + struct ccid3_hc_tx_sock *hc = ccid3_hc_tx_sk(sk); + enum ccid3_hc_tx_states oldstate = hc->tx_state; ccid3_pr_debug("%s(%p) %-8.8s -> %s\n", dccp_role(sk), sk, ccid3_tx_state_name(oldstate), ccid3_tx_state_name(state)); WARN_ON(state == oldstate); - hctx->ccid3hctx_state = state; + hc->tx_state = state; +} + +/* + * Compute the initial sending rate X_init in the manner of RFC 3390: + * + * X_init = min(4 * s, max(2 * s, 4380 bytes)) / RTT + * + * Note that RFC 3390 uses MSS, RFC 4342 refers to RFC 3390, and rfc3448bis + * (rev-02) clarifies the use of RFC 3390 with regard to the above formula. + * For consistency with other parts of the code, X_init is scaled by 2^6. + */ +static inline u64 rfc3390_initial_rate(struct sock *sk) +{ + const struct ccid3_hc_tx_sock *hc = ccid3_hc_tx_sk(sk); + const __u32 w_init = clamp_t(__u32, 4380U, 2 * hc->tx_s, 4 * hc->tx_s); + + return scaled_div(w_init << 6, hc->tx_rtt); } -/* Calculate new t_ipi (inter packet interval) by t_ipi = s / X_inst */ -static inline void ccid3_calc_new_t_ipi(struct ccid3_hc_tx_sock *hctx) +/** + * ccid3_update_send_interval - Calculate new t_ipi = s / X_inst + * This respects the granularity of X_inst (64 * bytes/second). + */ +static void ccid3_update_send_interval(struct ccid3_hc_tx_sock *hc) { + hc->tx_t_ipi = scaled_div32(((u64)hc->tx_s) << 6, hc->tx_x); + + DCCP_BUG_ON(hc->tx_t_ipi == 0); + ccid3_pr_debug("t_ipi=%u, s=%u, X=%u\n", hc->tx_t_ipi, + hc->tx_s, (unsigned int)(hc->tx_x >> 6)); +} + +static u32 ccid3_hc_tx_idle_rtt(struct ccid3_hc_tx_sock *hc, ktime_t now) +{ + u32 delta = ktime_us_delta(now, hc->tx_t_last_win_count); + + return delta / hc->tx_rtt; +} + +/** + * ccid3_hc_tx_update_x - Update allowed sending rate X + * @stamp: most recent time if available - can be left NULL. + * + * This function tracks draft rfc3448bis, check there for latest details. + * + * Note: X and X_recv are both stored in units of 64 * bytes/second, to support + * fine-grained resolution of sending rates. This requires scaling by 2^6 + * throughout the code. Only X_calc is unscaled (in bytes/second). + * + */ +static void ccid3_hc_tx_update_x(struct sock *sk, ktime_t *stamp) +{ + struct ccid3_hc_tx_sock *hc = ccid3_hc_tx_sk(sk); + __u64 min_rate = 2 * hc->tx_x_recv; + const __u64 old_x = hc->tx_x; + ktime_t now = stamp ? *stamp : ktime_get_real(); + /* - * If no feedback spec says t_ipi is 1 second (set elsewhere and then - * doubles after every no feedback timer (separate function) + * Handle IDLE periods: do not reduce below RFC3390 initial sending rate + * when idling [RFC 4342, 5.1]. Definition of idling is from rfc3448bis: + * a sender is idle if it has not sent anything over a 2-RTT-period. + * For consistency with X and X_recv, min_rate is also scaled by 2^6. */ - if (hctx->ccid3hctx_state != TFRC_SSTATE_NO_FBACK) - hctx->ccid3hctx_t_ipi = usecs_div(hctx->ccid3hctx_s, - hctx->ccid3hctx_x); + if (ccid3_hc_tx_idle_rtt(hc, now) >= 2) { + min_rate = rfc3390_initial_rate(sk); + min_rate = max(min_rate, 2 * hc->tx_x_recv); + } + + if (hc->tx_p > 0) { + + hc->tx_x = min(((__u64)hc->tx_x_calc) << 6, min_rate); + hc->tx_x = max(hc->tx_x, (((__u64)hc->tx_s) << 6) / TFRC_T_MBI); + + } else if (ktime_us_delta(now, hc->tx_t_ld) - (s64)hc->tx_rtt >= 0) { + + hc->tx_x = min(2 * hc->tx_x, min_rate); + hc->tx_x = max(hc->tx_x, + scaled_div(((__u64)hc->tx_s) << 6, hc->tx_rtt)); + hc->tx_t_ld = now; + } + + if (hc->tx_x != old_x) { + ccid3_pr_debug("X_prev=%u, X_now=%u, X_calc=%u, " + "X_recv=%u\n", (unsigned int)(old_x >> 6), + (unsigned int)(hc->tx_x >> 6), hc->tx_x_calc, + (unsigned int)(hc->tx_x_recv >> 6)); + + ccid3_update_send_interval(hc); + } } -/* Calculate new delta by delta = min(t_ipi / 2, t_gran / 2) */ -static inline void ccid3_calc_new_delta(struct ccid3_hc_tx_sock *hctx) +/** + * ccid3_hc_tx_update_s - Track the mean packet size `s' + * @len: DCCP packet payload size in bytes + * + * cf. RFC 4342, 5.3 and RFC 3448, 4.1 + */ +static inline void ccid3_hc_tx_update_s(struct ccid3_hc_tx_sock *hc, int len) { - hctx->ccid3hctx_delta = min_t(u32, hctx->ccid3hctx_t_ipi / 2, - TFRC_OPSYS_HALF_TIME_GRAN); + const u16 old_s = hc->tx_s; + + hc->tx_s = tfrc_ewma(hc->tx_s, len, 9); + + if (hc->tx_s != old_s) + ccid3_update_send_interval(hc); } /* - * Update X by - * If (p > 0) - * x_calc = calcX(s, R, p); - * X = max(min(X_calc, 2 * X_recv), s / t_mbi); - * Else - * If (now - tld >= R) - * X = max(min(2 * X, 2 * X_recv), s / R); - * tld = now; - */ -static void ccid3_hc_tx_update_x(struct sock *sk) + * Update Window Counter using the algorithm from [RFC 4342, 8.1]. + * As elsewhere, RTT > 0 is assumed by using dccp_sample_rtt(). + */ +static inline void ccid3_hc_tx_update_win_count(struct ccid3_hc_tx_sock *hc, + ktime_t now) { - struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); - - /* To avoid large error in calcX */ - if (hctx->ccid3hctx_p >= TFRC_SMALLEST_P) { - hctx->ccid3hctx_x_calc = tfrc_calc_x(hctx->ccid3hctx_s, - hctx->ccid3hctx_rtt, - hctx->ccid3hctx_p); - hctx->ccid3hctx_x = max_t(u32, min_t(u32, hctx->ccid3hctx_x_calc, - 2 * hctx->ccid3hctx_x_recv), - (hctx->ccid3hctx_s / - TFRC_MAX_BACK_OFF_TIME)); - } else { - struct timeval now; - - dccp_timestamp(sk, &now); - if (timeval_delta(&now, &hctx->ccid3hctx_t_ld) >= - hctx->ccid3hctx_rtt) { - hctx->ccid3hctx_x = max_t(u32, min_t(u32, hctx->ccid3hctx_x_recv, - hctx->ccid3hctx_x) * 2, - usecs_div(hctx->ccid3hctx_s, - hctx->ccid3hctx_rtt)); - hctx->ccid3hctx_t_ld = now; - } + u32 delta = ktime_us_delta(now, hc->tx_t_last_win_count), + quarter_rtts = (4 * delta) / hc->tx_rtt; + + if (quarter_rtts > 0) { + hc->tx_t_last_win_count = now; + hc->tx_last_win_count += min(quarter_rtts, 5U); + hc->tx_last_win_count &= 0xF; /* mod 16 */ } } static void ccid3_hc_tx_no_feedback_timer(unsigned long data) { struct sock *sk = (struct sock *)data; - unsigned long next_tmout = 0; - struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); + struct ccid3_hc_tx_sock *hc = ccid3_hc_tx_sk(sk); + unsigned long t_nfb = USEC_PER_SEC / 5; bh_lock_sock(sk); if (sock_owned_by_user(sk)) { /* Try again later. */ /* XXX: set some sensible MIB */ - sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer, - jiffies + HZ / 5); - goto out; + goto restart_timer; } - ccid3_pr_debug("%s, sk=%p, state=%s\n", dccp_role(sk), sk, - ccid3_tx_state_name(hctx->ccid3hctx_state)); - - switch (hctx->ccid3hctx_state) { - case TFRC_SSTATE_TERM: + ccid3_pr_debug("%s(%p, state=%s) - entry\n", dccp_role(sk), sk, + ccid3_tx_state_name(hc->tx_state)); + + /* Ignore and do not restart after leaving the established state */ + if ((1 << sk->sk_state) & ~(DCCPF_OPEN | DCCPF_PARTOPEN)) goto out; - case TFRC_SSTATE_NO_FBACK: - /* Halve send rate */ - hctx->ccid3hctx_x /= 2; - if (hctx->ccid3hctx_x < (hctx->ccid3hctx_s / - TFRC_MAX_BACK_OFF_TIME)) - hctx->ccid3hctx_x = (hctx->ccid3hctx_s / - TFRC_MAX_BACK_OFF_TIME); - - ccid3_pr_debug("%s, sk=%p, state=%s, updated tx rate to %d " - "bytes/s\n", - dccp_role(sk), sk, - ccid3_tx_state_name(hctx->ccid3hctx_state), - hctx->ccid3hctx_x); - next_tmout = max_t(u32, 2 * usecs_div(hctx->ccid3hctx_s, - hctx->ccid3hctx_x), - TFRC_INITIAL_TIMEOUT); - /* - * FIXME - not sure above calculation is correct. See section - * 5 of CCID3 11 should adjust tx_t_ipi and double that to - * achieve it really - */ - break; - case TFRC_SSTATE_FBACK: + + /* Reset feedback state to "no feedback received" */ + if (hc->tx_state == TFRC_SSTATE_FBACK) + ccid3_hc_tx_set_state(sk, TFRC_SSTATE_NO_FBACK); + + /* + * Determine new allowed sending rate X as per draft rfc3448bis-00, 4.4 + * RTO is 0 if and only if no feedback has been received yet. + */ + if (hc->tx_t_rto == 0 || hc->tx_p == 0) { + + /* halve send rate directly */ + hc->tx_x = max(hc->tx_x / 2, + (((__u64)hc->tx_s) << 6) / TFRC_T_MBI); + ccid3_update_send_interval(hc); + } else { /* - * Check if IDLE since last timeout and recv rate is less than - * 4 packets per RTT + * Modify the cached value of X_recv + * + * If (X_calc > 2 * X_recv) + * X_recv = max(X_recv / 2, s / (2 * t_mbi)); + * Else + * X_recv = X_calc / 4; + * + * Note that X_recv is scaled by 2^6 while X_calc is not */ - if (!hctx->ccid3hctx_idle || - (hctx->ccid3hctx_x_recv >= - 4 * usecs_div(hctx->ccid3hctx_s, hctx->ccid3hctx_rtt))) { - ccid3_pr_debug("%s, sk=%p, state=%s, not idle\n", - dccp_role(sk), sk, - ccid3_tx_state_name(hctx->ccid3hctx_state)); - /* Halve sending rate */ - - /* If (X_calc > 2 * X_recv) - * X_recv = max(X_recv / 2, s / (2 * t_mbi)); - * Else - * X_recv = X_calc / 4; - */ - BUG_ON(hctx->ccid3hctx_p >= TFRC_SMALLEST_P && - hctx->ccid3hctx_x_calc == 0); - - /* check also if p is zero -> x_calc is infinity? */ - if (hctx->ccid3hctx_p < TFRC_SMALLEST_P || - hctx->ccid3hctx_x_calc > 2 * hctx->ccid3hctx_x_recv) - hctx->ccid3hctx_x_recv = max_t(u32, hctx->ccid3hctx_x_recv / 2, - hctx->ccid3hctx_s / (2 * TFRC_MAX_BACK_OFF_TIME)); - else - hctx->ccid3hctx_x_recv = hctx->ccid3hctx_x_calc / 4; - - /* Update sending rate */ - ccid3_hc_tx_update_x(sk); + if (hc->tx_x_calc > (hc->tx_x_recv >> 5)) + hc->tx_x_recv = + max(hc->tx_x_recv / 2, + (((__u64)hc->tx_s) << 6) / (2*TFRC_T_MBI)); + else { + hc->tx_x_recv = hc->tx_x_calc; + hc->tx_x_recv <<= 4; } - /* - * Schedule no feedback timer to expire in - * max(4 * R, 2 * s / X) - */ - next_tmout = max_t(u32, hctx->ccid3hctx_t_rto, - 2 * usecs_div(hctx->ccid3hctx_s, - hctx->ccid3hctx_x)); - break; - default: - printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n", - __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state); - dump_stack(); - goto out; + ccid3_hc_tx_update_x(sk, NULL); } + ccid3_pr_debug("Reduced X to %llu/64 bytes/sec\n", + (unsigned long long)hc->tx_x); + + /* + * Set new timeout for the nofeedback timer. + * See comments in packet_recv() regarding the value of t_RTO. + */ + if (unlikely(hc->tx_t_rto == 0)) /* no feedback received yet */ + t_nfb = TFRC_INITIAL_TIMEOUT; + else + t_nfb = max(hc->tx_t_rto, 2 * hc->tx_t_ipi); - sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer, - jiffies + max_t(u32, 1, usecs_to_jiffies(next_tmout))); - hctx->ccid3hctx_idle = 1; +restart_timer: + sk_reset_timer(sk, &hc->tx_no_feedback_timer, + jiffies + usecs_to_jiffies(t_nfb)); out: bh_unlock_sock(sk); sock_put(sk); } -static int ccid3_hc_tx_send_packet(struct sock *sk, - struct sk_buff *skb, int len) +/** + * ccid3_hc_tx_send_packet - Delay-based dequeueing of TX packets + * @skb: next packet candidate to send on @sk + * + * This function uses the convention of ccid_packet_dequeue_eval() and + * returns a millisecond-delay value between 0 and t_mbi = 64000 msec. + */ +static int ccid3_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb) { struct dccp_sock *dp = dccp_sk(sk); - struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); - struct dccp_tx_hist_entry *new_packet; - struct timeval now; - long delay; - int rc = -ENOTCONN; - - BUG_ON(hctx == NULL || hctx->ccid3hctx_state == TFRC_SSTATE_TERM); + struct ccid3_hc_tx_sock *hc = ccid3_hc_tx_sk(sk); + ktime_t now = ktime_get_real(); + s64 delay; - /* Check if pure ACK or Terminating*/ /* - * XXX: We only call this function for DATA and DATAACK, on, these - * packets can have zero length, but why the comment about "pure ACK"? + * This function is called only for Data and DataAck packets. Sending + * zero-sized Data(Ack)s is theoretically possible, but for congestion + * control this case is pathological - ignore it. */ - if (unlikely(len == 0)) - goto out; + if (unlikely(skb->len == 0)) + return -EBADMSG; - /* See if last packet allocated was not sent */ - new_packet = dccp_tx_hist_head(&hctx->ccid3hctx_hist); - if (new_packet == NULL || new_packet->dccphtx_sent) { - new_packet = dccp_tx_hist_entry_new(ccid3_tx_hist, - SLAB_ATOMIC); - - rc = -ENOBUFS; - if (unlikely(new_packet == NULL)) { - LIMIT_NETDEBUG(KERN_WARNING "%s: %s, sk=%p, not enough " - "mem to add to history, send refused\n", - __FUNCTION__, dccp_role(sk), sk); - goto out; - } + if (hc->tx_state == TFRC_SSTATE_NO_SENT) { + sk_reset_timer(sk, &hc->tx_no_feedback_timer, (jiffies + + usecs_to_jiffies(TFRC_INITIAL_TIMEOUT))); + hc->tx_last_win_count = 0; + hc->tx_t_last_win_count = now; - dccp_tx_hist_add_entry(&hctx->ccid3hctx_hist, new_packet); - } + /* Set t_0 for initial packet */ + hc->tx_t_nom = now; - dccp_timestamp(sk, &now); + hc->tx_s = skb->len; + + /* + * Use initial RTT sample when available: recommended by erratum + * to RFC 4342. This implements the initialisation procedure of + * draft rfc3448bis, section 4.2. Remember, X is scaled by 2^6. + */ + if (dp->dccps_syn_rtt) { + ccid3_pr_debug("SYN RTT = %uus\n", dp->dccps_syn_rtt); + hc->tx_rtt = dp->dccps_syn_rtt; + hc->tx_x = rfc3390_initial_rate(sk); + hc->tx_t_ld = now; + } else { + /* + * Sender does not have RTT sample: + * - set fallback RTT (RFC 4340, 3.4) since a RTT value + * is needed in several parts (e.g. window counter); + * - set sending rate X_pps = 1pps as per RFC 3448, 4.2. + */ + hc->tx_rtt = DCCP_FALLBACK_RTT; + hc->tx_x = hc->tx_s; + hc->tx_x <<= 6; + } + ccid3_update_send_interval(hc); - switch (hctx->ccid3hctx_state) { - case TFRC_SSTATE_NO_SENT: - sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer, - jiffies + usecs_to_jiffies(TFRC_INITIAL_TIMEOUT)); - hctx->ccid3hctx_last_win_count = 0; - hctx->ccid3hctx_t_last_win_count = now; ccid3_hc_tx_set_state(sk, TFRC_SSTATE_NO_FBACK); - hctx->ccid3hctx_t_ipi = TFRC_INITIAL_IPI; - - /* Set nominal send time for initial packet */ - hctx->ccid3hctx_t_nom = now; - timeval_add_usecs(&hctx->ccid3hctx_t_nom, - hctx->ccid3hctx_t_ipi); - ccid3_calc_new_delta(hctx); - rc = 0; - break; - case TFRC_SSTATE_NO_FBACK: - case TFRC_SSTATE_FBACK: - delay = (timeval_delta(&now, &hctx->ccid3hctx_t_nom) - - hctx->ccid3hctx_delta); - delay /= -1000; - /* divide by -1000 is to convert to ms and get sign right */ - rc = delay > 0 ? delay : 0; - break; - default: - printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n", - __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state); - dump_stack(); - rc = -EINVAL; - break; - } - /* Can we send? if so add options and add to packet history */ - if (rc == 0) { - dp->dccps_hc_tx_insert_options = 1; - new_packet->dccphtx_ccval = - DCCP_SKB_CB(skb)->dccpd_ccval = - hctx->ccid3hctx_last_win_count; - timeval_add_usecs(&hctx->ccid3hctx_t_nom, - hctx->ccid3hctx_t_ipi); - } -out: - return rc; -} + } else { + delay = ktime_us_delta(hc->tx_t_nom, now); + ccid3_pr_debug("delay=%ld\n", (long)delay); + /* + * Scheduling of packet transmissions (RFC 5348, 8.3) + * + * if (t_now > t_nom - delta) + * // send the packet now + * else + * // send the packet in (t_nom - t_now) milliseconds. + */ + if (delay >= TFRC_T_DELTA) + return (u32)delay / USEC_PER_MSEC; -static void ccid3_hc_tx_packet_sent(struct sock *sk, int more, int len) -{ - const struct dccp_sock *dp = dccp_sk(sk); - struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); - struct timeval now; + ccid3_hc_tx_update_win_count(hc, now); + } - BUG_ON(hctx == NULL || hctx->ccid3hctx_state == TFRC_SSTATE_TERM); + /* prepare to send now (add options etc.) */ + dp->dccps_hc_tx_insert_options = 1; + DCCP_SKB_CB(skb)->dccpd_ccval = hc->tx_last_win_count; - dccp_timestamp(sk, &now); + /* set the nominal send time for the next following packet */ + hc->tx_t_nom = ktime_add_us(hc->tx_t_nom, hc->tx_t_ipi); + return CCID_PACKET_SEND_AT_ONCE; +} - /* check if we have sent a data packet */ - if (len > 0) { - unsigned long quarter_rtt; - struct dccp_tx_hist_entry *packet; +static void ccid3_hc_tx_packet_sent(struct sock *sk, unsigned int len) +{ + struct ccid3_hc_tx_sock *hc = ccid3_hc_tx_sk(sk); - packet = dccp_tx_hist_head(&hctx->ccid3hctx_hist); - if (unlikely(packet == NULL)) { - LIMIT_NETDEBUG(KERN_WARNING "%s: packet doesn't " - "exists in history!\n", __FUNCTION__); - return; - } - if (unlikely(packet->dccphtx_sent)) { - LIMIT_NETDEBUG(KERN_WARNING "%s: no unsent packet in " - "history!\n", __FUNCTION__); - return; - } - packet->dccphtx_tstamp = now; - packet->dccphtx_seqno = dp->dccps_gss; - /* - * Check if win_count have changed - * Algorithm in "8.1. Window Counter Valuer" in - * draft-ietf-dccp-ccid3-11.txt - */ - quarter_rtt = timeval_delta(&now, &hctx->ccid3hctx_t_last_win_count); - if (likely(hctx->ccid3hctx_rtt > 8)) - quarter_rtt /= hctx->ccid3hctx_rtt / 4; - - if (quarter_rtt > 0) { - hctx->ccid3hctx_t_last_win_count = now; - hctx->ccid3hctx_last_win_count = (hctx->ccid3hctx_last_win_count + - min_t(unsigned long, quarter_rtt, 5)) % 16; - ccid3_pr_debug("%s, sk=%p, window changed from " - "%u to %u!\n", - dccp_role(sk), sk, - packet->dccphtx_ccval, - hctx->ccid3hctx_last_win_count); - } + ccid3_hc_tx_update_s(hc, len); - hctx->ccid3hctx_idle = 0; - packet->dccphtx_rtt = hctx->ccid3hctx_rtt; - packet->dccphtx_sent = 1; - } else - ccid3_pr_debug("%s, sk=%p, seqno=%llu NOT inserted!\n", - dccp_role(sk), sk, dp->dccps_gss); - - switch (hctx->ccid3hctx_state) { - case TFRC_SSTATE_NO_SENT: - /* if first wasn't pure ack */ - if (len != 0) - printk(KERN_CRIT "%s: %s, First packet sent is noted " - "as a data packet\n", - __FUNCTION__, dccp_role(sk)); - return; - case TFRC_SSTATE_NO_FBACK: - case TFRC_SSTATE_FBACK: - if (len > 0) { - timeval_sub_usecs(&hctx->ccid3hctx_t_nom, - hctx->ccid3hctx_t_ipi); - ccid3_calc_new_t_ipi(hctx); - ccid3_calc_new_delta(hctx); - timeval_add_usecs(&hctx->ccid3hctx_t_nom, - hctx->ccid3hctx_t_ipi); - } - break; - default: - printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n", - __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state); - dump_stack(); - break; - } + if (tfrc_tx_hist_add(&hc->tx_hist, dccp_sk(sk)->dccps_gss)) + DCCP_CRIT("packet history - out of memory!"); } static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) { - const struct dccp_sock *dp = dccp_sk(sk); - struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); - struct ccid3_options_received *opt_recv; - struct dccp_tx_hist_entry *packet; - struct timeval now; - unsigned long next_tmout; - u32 t_elapsed; - u32 pinv; - u32 x_recv; + struct ccid3_hc_tx_sock *hc = ccid3_hc_tx_sk(sk); + struct tfrc_tx_hist_entry *acked; + ktime_t now; + unsigned long t_nfb; u32 r_sample; - BUG_ON(hctx == NULL || hctx->ccid3hctx_state == TFRC_SSTATE_TERM); - /* we are only interested in ACKs */ if (!(DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK || DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_DATAACK)) return; + /* + * Locate the acknowledged packet in the TX history. + * + * Returning "entry not found" here can for instance happen when + * - the host has not sent out anything (e.g. a passive server), + * - the Ack is outdated (packet with higher Ack number was received), + * - it is a bogus Ack (for a packet not sent on this connection). + */ + acked = tfrc_tx_hist_find_entry(hc->tx_hist, dccp_hdr_ack_seq(skb)); + if (acked == NULL) + return; + /* For the sake of RTT sampling, ignore/remove all older entries */ + tfrc_tx_hist_purge(&acked->next); - opt_recv = &hctx->ccid3hctx_options_received; - - t_elapsed = dp->dccps_options_received.dccpor_elapsed_time * 10; - x_recv = opt_recv->ccid3or_receive_rate; - pinv = opt_recv->ccid3or_loss_event_rate; + /* Update the moving average for the RTT estimate (RFC 3448, 4.3) */ + now = ktime_get_real(); + r_sample = dccp_sample_rtt(sk, ktime_us_delta(now, acked->stamp)); + hc->tx_rtt = tfrc_ewma(hc->tx_rtt, r_sample, 9); - switch (hctx->ccid3hctx_state) { - case TFRC_SSTATE_NO_SENT: - /* FIXME: what to do here? */ - return; - case TFRC_SSTATE_NO_FBACK: - case TFRC_SSTATE_FBACK: - /* Calculate new round trip sample by - * R_sample = (now - t_recvdata) - t_delay */ - /* get t_recvdata from history */ - packet = dccp_tx_hist_find_entry(&hctx->ccid3hctx_hist, - DCCP_SKB_CB(skb)->dccpd_ack_seq); - if (unlikely(packet == NULL)) { - LIMIT_NETDEBUG(KERN_WARNING "%s: %s, sk=%p, seqno " - "%llu(%s) does't exist in history!\n", - __FUNCTION__, dccp_role(sk), sk, - (unsigned long long)DCCP_SKB_CB(skb)->dccpd_ack_seq, - dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type)); - return; - } + /* + * Update allowed sending rate X as per draft rfc3448bis-00, 4.2/3 + */ + if (hc->tx_state == TFRC_SSTATE_NO_FBACK) { + ccid3_hc_tx_set_state(sk, TFRC_SSTATE_FBACK); - /* Update RTT */ - dccp_timestamp(sk, &now); - r_sample = timeval_delta(&now, &packet->dccphtx_tstamp); - if (unlikely(r_sample <= t_elapsed)) - LIMIT_NETDEBUG(KERN_WARNING "%s: r_sample=%uus, " - "t_elapsed=%uus\n", - __FUNCTION__, r_sample, t_elapsed); - else - r_sample -= t_elapsed; + if (hc->tx_t_rto == 0) { + /* + * Initial feedback packet: Larger Initial Windows (4.2) + */ + hc->tx_x = rfc3390_initial_rate(sk); + hc->tx_t_ld = now; - /* Update RTT estimate by - * If (No feedback recv) - * R = R_sample; - * Else - * R = q * R + (1 - q) * R_sample; - * - * q is a constant, RFC 3448 recomments 0.9 - */ - if (hctx->ccid3hctx_state == TFRC_SSTATE_NO_FBACK) { - ccid3_hc_tx_set_state(sk, TFRC_SSTATE_FBACK); - hctx->ccid3hctx_rtt = r_sample; - } else - hctx->ccid3hctx_rtt = (hctx->ccid3hctx_rtt * 9) / 10 + - r_sample / 10; - - ccid3_pr_debug("%s, sk=%p, New RTT estimate=%uus, " - "r_sample=%us\n", dccp_role(sk), sk, - hctx->ccid3hctx_rtt, r_sample); - - /* Update timeout interval */ - hctx->ccid3hctx_t_rto = max_t(u32, 4 * hctx->ccid3hctx_rtt, - USEC_PER_SEC); - - /* Update receive rate */ - hctx->ccid3hctx_x_recv = x_recv;/* X_recv in bytes per sec */ - - /* Update loss event rate */ - if (pinv == ~0 || pinv == 0) - hctx->ccid3hctx_p = 0; - else { - hctx->ccid3hctx_p = 1000000 / pinv; + ccid3_update_send_interval(hc); - if (hctx->ccid3hctx_p < TFRC_SMALLEST_P) { - hctx->ccid3hctx_p = TFRC_SMALLEST_P; - ccid3_pr_debug("%s, sk=%p, Smallest p used!\n", - dccp_role(sk), sk); - } + goto done_computing_x; + } else if (hc->tx_p == 0) { + /* + * First feedback after nofeedback timer expiry (4.3) + */ + goto done_computing_x; } + } - /* unschedule no feedback timer */ - sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer); - - /* Update sending rate */ - ccid3_hc_tx_update_x(sk); + /* Update sending rate (step 4 of [RFC 3448, 4.3]) */ + if (hc->tx_p > 0) + hc->tx_x_calc = tfrc_calc_x(hc->tx_s, hc->tx_rtt, hc->tx_p); + ccid3_hc_tx_update_x(sk, &now); - /* Update next send time */ - timeval_sub_usecs(&hctx->ccid3hctx_t_nom, - hctx->ccid3hctx_t_ipi); - ccid3_calc_new_t_ipi(hctx); - timeval_add_usecs(&hctx->ccid3hctx_t_nom, - hctx->ccid3hctx_t_ipi); - ccid3_calc_new_delta(hctx); +done_computing_x: + ccid3_pr_debug("%s(%p), RTT=%uus (sample=%uus), s=%u, " + "p=%u, X_calc=%u, X_recv=%u, X=%u\n", + dccp_role(sk), sk, hc->tx_rtt, r_sample, + hc->tx_s, hc->tx_p, hc->tx_x_calc, + (unsigned int)(hc->tx_x_recv >> 6), + (unsigned int)(hc->tx_x >> 6)); - /* remove all packets older than the one acked from history */ - dccp_tx_hist_purge_older(ccid3_tx_hist, - &hctx->ccid3hctx_hist, packet); - /* - * As we have calculated new ipi, delta, t_nom it is possible that - * we now can send a packet, so wake up dccp_wait_for_ccids. - */ - sk->sk_write_space(sk); + /* unschedule no feedback timer */ + sk_stop_timer(sk, &hc->tx_no_feedback_timer); - /* - * Schedule no feedback timer to expire in - * max(4 * R, 2 * s / X) - */ - next_tmout = max(hctx->ccid3hctx_t_rto, - 2 * usecs_div(hctx->ccid3hctx_s, - hctx->ccid3hctx_x)); - - ccid3_pr_debug("%s, sk=%p, Scheduled no feedback timer to " - "expire in %lu jiffies (%luus)\n", - dccp_role(sk), sk, - usecs_to_jiffies(next_tmout), next_tmout); - - sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer, - jiffies + max_t(u32, 1, usecs_to_jiffies(next_tmout))); - - /* set idle flag */ - hctx->ccid3hctx_idle = 1; - break; - default: - printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n", - __FUNCTION__, dccp_role(sk), sk, hctx->ccid3hctx_state); - dump_stack(); - break; - } -} + /* + * As we have calculated new ipi, delta, t_nom it is possible + * that we now can send a packet, so wake up dccp_wait_for_ccid + */ + sk->sk_write_space(sk); -static int ccid3_hc_tx_insert_options(struct sock *sk, struct sk_buff *skb) -{ - const struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); + /* + * Update timeout interval for the nofeedback timer. In order to control + * rate halving on networks with very low RTTs (<= 1 ms), use per-route + * tunable RTAX_RTO_MIN value as the lower bound. + */ + hc->tx_t_rto = max_t(u32, 4 * hc->tx_rtt, + USEC_PER_SEC/HZ * tcp_rto_min(sk)); + /* + * Schedule no feedback timer to expire in + * max(t_RTO, 2 * s/X) = max(t_RTO, 2 * t_ipi) + */ + t_nfb = max(hc->tx_t_rto, 2 * hc->tx_t_ipi); - BUG_ON(hctx == NULL); + ccid3_pr_debug("%s(%p), Scheduled no feedback timer to " + "expire in %lu jiffies (%luus)\n", + dccp_role(sk), sk, usecs_to_jiffies(t_nfb), t_nfb); - if (sk->sk_state == DCCP_OPEN || sk->sk_state == DCCP_PARTOPEN) - DCCP_SKB_CB(skb)->dccpd_ccval = hctx->ccid3hctx_last_win_count; - return 0; + sk_reset_timer(sk, &hc->tx_no_feedback_timer, + jiffies + usecs_to_jiffies(t_nfb)); } -static int ccid3_hc_tx_parse_options(struct sock *sk, unsigned char option, - unsigned char len, u16 idx, - unsigned char *value) +static int ccid3_hc_tx_parse_options(struct sock *sk, u8 packet_type, + u8 option, u8 *optval, u8 optlen) { - int rc = 0; - const struct dccp_sock *dp = dccp_sk(sk); - struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); - struct ccid3_options_received *opt_recv; - - BUG_ON(hctx == NULL); - - opt_recv = &hctx->ccid3hctx_options_received; - - if (opt_recv->ccid3or_seqno != dp->dccps_gsr) { - opt_recv->ccid3or_seqno = dp->dccps_gsr; - opt_recv->ccid3or_loss_event_rate = ~0; - opt_recv->ccid3or_loss_intervals_idx = 0; - opt_recv->ccid3or_loss_intervals_len = 0; - opt_recv->ccid3or_receive_rate = 0; - } + struct ccid3_hc_tx_sock *hc = ccid3_hc_tx_sk(sk); + __be32 opt_val; switch (option) { + case TFRC_OPT_RECEIVE_RATE: case TFRC_OPT_LOSS_EVENT_RATE: - if (unlikely(len != 4)) { - LIMIT_NETDEBUG(KERN_WARNING "%s: %s, sk=%p, invalid " - "len for TFRC_OPT_LOSS_EVENT_RATE\n", - __FUNCTION__, dccp_role(sk), sk); - rc = -EINVAL; - } else { - opt_recv->ccid3or_loss_event_rate = ntohl(*(__be32 *)value); - ccid3_pr_debug("%s, sk=%p, LOSS_EVENT_RATE=%u\n", - dccp_role(sk), sk, - opt_recv->ccid3or_loss_event_rate); + /* Must be ignored on Data packets, cf. RFC 4342 8.3 and 8.5 */ + if (packet_type == DCCP_PKT_DATA) + break; + if (unlikely(optlen != 4)) { + DCCP_WARN("%s(%p), invalid len %d for %u\n", + dccp_role(sk), sk, optlen, option); + return -EINVAL; } - break; - case TFRC_OPT_LOSS_INTERVALS: - opt_recv->ccid3or_loss_intervals_idx = idx; - opt_recv->ccid3or_loss_intervals_len = len; - ccid3_pr_debug("%s, sk=%p, LOSS_INTERVALS=(%u, %u)\n", - dccp_role(sk), sk, - opt_recv->ccid3or_loss_intervals_idx, - opt_recv->ccid3or_loss_intervals_len); - break; - case TFRC_OPT_RECEIVE_RATE: - if (unlikely(len != 4)) { - LIMIT_NETDEBUG(KERN_WARNING "%s: %s, sk=%p, invalid " - "len for TFRC_OPT_RECEIVE_RATE\n", - __FUNCTION__, dccp_role(sk), sk); - rc = -EINVAL; + opt_val = ntohl(get_unaligned((__be32 *)optval)); + + if (option == TFRC_OPT_RECEIVE_RATE) { + /* Receive Rate is kept in units of 64 bytes/second */ + hc->tx_x_recv = opt_val; + hc->tx_x_recv <<= 6; + + ccid3_pr_debug("%s(%p), RECEIVE_RATE=%u\n", + dccp_role(sk), sk, opt_val); } else { - opt_recv->ccid3or_receive_rate = ntohl(*(__be32 *)value); - ccid3_pr_debug("%s, sk=%p, RECEIVE_RATE=%u\n", - dccp_role(sk), sk, - opt_recv->ccid3or_receive_rate); + /* Update the fixpoint Loss Event Rate fraction */ + hc->tx_p = tfrc_invert_loss_event_rate(opt_val); + + ccid3_pr_debug("%s(%p), LOSS_EVENT_RATE=%u\n", + dccp_role(sk), sk, opt_val); } - break; } - - return rc; + return 0; } static int ccid3_hc_tx_init(struct ccid *ccid, struct sock *sk) { - struct dccp_sock *dp = dccp_sk(sk); - struct ccid3_hc_tx_sock *hctx = ccid_priv(ccid); + struct ccid3_hc_tx_sock *hc = ccid_priv(ccid); - if (dp->dccps_packet_size >= TFRC_MIN_PACKET_SIZE && - dp->dccps_packet_size <= TFRC_MAX_PACKET_SIZE) - hctx->ccid3hctx_s = dp->dccps_packet_size; - else - hctx->ccid3hctx_s = TFRC_STD_PACKET_SIZE; + hc->tx_state = TFRC_SSTATE_NO_SENT; + hc->tx_hist = NULL; + setup_timer(&hc->tx_no_feedback_timer, + ccid3_hc_tx_no_feedback_timer, (unsigned long)sk); + return 0; +} - /* Set transmission rate to 1 packet per second */ - hctx->ccid3hctx_x = hctx->ccid3hctx_s; - hctx->ccid3hctx_t_rto = USEC_PER_SEC; - hctx->ccid3hctx_state = TFRC_SSTATE_NO_SENT; - INIT_LIST_HEAD(&hctx->ccid3hctx_hist); +static void ccid3_hc_tx_exit(struct sock *sk) +{ + struct ccid3_hc_tx_sock *hc = ccid3_hc_tx_sk(sk); - hctx->ccid3hctx_no_feedback_timer.function = ccid3_hc_tx_no_feedback_timer; - hctx->ccid3hctx_no_feedback_timer.data = (unsigned long)sk; - init_timer(&hctx->ccid3hctx_no_feedback_timer); + sk_stop_timer(sk, &hc->tx_no_feedback_timer); + tfrc_tx_hist_purge(&hc->tx_hist); +} - return 0; +static void ccid3_hc_tx_get_info(struct sock *sk, struct tcp_info *info) +{ + info->tcpi_rto = ccid3_hc_tx_sk(sk)->tx_t_rto; + info->tcpi_rtt = ccid3_hc_tx_sk(sk)->tx_rtt; } -static void ccid3_hc_tx_exit(struct sock *sk) +static int ccid3_hc_tx_getsockopt(struct sock *sk, const int optname, int len, + u32 __user *optval, int __user *optlen) { - struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); + const struct ccid3_hc_tx_sock *hc = ccid3_hc_tx_sk(sk); + struct tfrc_tx_info tfrc; + const void *val; - BUG_ON(hctx == NULL); + switch (optname) { + case DCCP_SOCKOPT_CCID_TX_INFO: + if (len < sizeof(tfrc)) + return -EINVAL; + memset(&tfrc, 0, sizeof(tfrc)); + tfrc.tfrctx_x = hc->tx_x; + tfrc.tfrctx_x_recv = hc->tx_x_recv; + tfrc.tfrctx_x_calc = hc->tx_x_calc; + tfrc.tfrctx_rtt = hc->tx_rtt; + tfrc.tfrctx_p = hc->tx_p; + tfrc.tfrctx_rto = hc->tx_t_rto; + tfrc.tfrctx_ipi = hc->tx_t_ipi; + len = sizeof(tfrc); + val = &tfrc; + break; + default: + return -ENOPROTOOPT; + } - ccid3_hc_tx_set_state(sk, TFRC_SSTATE_TERM); - sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer); + if (put_user(len, optlen) || copy_to_user(optval, val, len)) + return -EFAULT; - /* Empty packet history */ - dccp_tx_hist_purge(ccid3_tx_hist, &hctx->ccid3hctx_hist); + return 0; } /* - * RX Half Connection methods + * Receiver Half-Connection Routines */ -/* TFRC receiver states */ -enum ccid3_hc_rx_states { - TFRC_RSTATE_NO_DATA = 1, - TFRC_RSTATE_DATA, - TFRC_RSTATE_TERM = 127, +/* CCID3 feedback types */ +enum ccid3_fback_type { + CCID3_FBACK_NONE = 0, + CCID3_FBACK_INITIAL, + CCID3_FBACK_PERIODIC, + CCID3_FBACK_PARAM_CHANGE }; -#ifdef CCID3_DEBUG +#ifdef CONFIG_IP_DCCP_CCID3_DEBUG static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state) { - static char *ccid3_rx_state_names[] = { + static const char *const ccid3_rx_state_names[] = { [TFRC_RSTATE_NO_DATA] = "NO_DATA", [TFRC_RSTATE_DATA] = "DATA", - [TFRC_RSTATE_TERM] = "TERM", }; return ccid3_rx_state_names[state]; @@ -712,522 +583,255 @@ static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state) static void ccid3_hc_rx_set_state(struct sock *sk, enum ccid3_hc_rx_states state) { - struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); - enum ccid3_hc_rx_states oldstate = hcrx->ccid3hcrx_state; + struct ccid3_hc_rx_sock *hc = ccid3_hc_rx_sk(sk); + enum ccid3_hc_rx_states oldstate = hc->rx_state; ccid3_pr_debug("%s(%p) %-8.8s -> %s\n", dccp_role(sk), sk, ccid3_rx_state_name(oldstate), ccid3_rx_state_name(state)); WARN_ON(state == oldstate); - hcrx->ccid3hcrx_state = state; + hc->rx_state = state; } -static void ccid3_hc_rx_send_feedback(struct sock *sk) +static void ccid3_hc_rx_send_feedback(struct sock *sk, + const struct sk_buff *skb, + enum ccid3_fback_type fbtype) { - struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); + struct ccid3_hc_rx_sock *hc = ccid3_hc_rx_sk(sk); struct dccp_sock *dp = dccp_sk(sk); - struct dccp_rx_hist_entry *packet; - struct timeval now; - - ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk); + ktime_t now = ktime_get_real(); + s64 delta = 0; - dccp_timestamp(sk, &now); - - switch (hcrx->ccid3hcrx_state) { - case TFRC_RSTATE_NO_DATA: - hcrx->ccid3hcrx_x_recv = 0; + switch (fbtype) { + case CCID3_FBACK_INITIAL: + hc->rx_x_recv = 0; + hc->rx_pinv = ~0U; /* see RFC 4342, 8.5 */ break; - case TFRC_RSTATE_DATA: { - const u32 delta = timeval_delta(&now, - &hcrx->ccid3hcrx_tstamp_last_feedback); - hcrx->ccid3hcrx_x_recv = usecs_div(hcrx->ccid3hcrx_bytes_recv, - delta); - } + case CCID3_FBACK_PARAM_CHANGE: + /* + * When parameters change (new loss or p > p_prev), we do not + * have a reliable estimate for R_m of [RFC 3448, 6.2] and so + * need to reuse the previous value of X_recv. However, when + * X_recv was 0 (due to early loss), this would kill X down to + * s/t_mbi (i.e. one packet in 64 seconds). + * To avoid such drastic reduction, we approximate X_recv as + * the number of bytes since last feedback. + * This is a safe fallback, since X is bounded above by X_calc. + */ + if (hc->rx_x_recv > 0) + break; + /* fall through */ + case CCID3_FBACK_PERIODIC: + delta = ktime_us_delta(now, hc->rx_tstamp_last_feedback); + if (delta <= 0) + DCCP_BUG("delta (%ld) <= 0", (long)delta); + else + hc->rx_x_recv = scaled_div32(hc->rx_bytes_recv, delta); break; default: - printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n", - __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state); - dump_stack(); return; } - packet = dccp_rx_hist_find_data_packet(&hcrx->ccid3hcrx_hist); - if (unlikely(packet == NULL)) { - LIMIT_NETDEBUG(KERN_WARNING "%s: %s, sk=%p, no data packet " - "in history!\n", - __FUNCTION__, dccp_role(sk), sk); - return; - } + ccid3_pr_debug("Interval %ldusec, X_recv=%u, 1/p=%u\n", (long)delta, + hc->rx_x_recv, hc->rx_pinv); - hcrx->ccid3hcrx_tstamp_last_feedback = now; - hcrx->ccid3hcrx_ccval_last_counter = packet->dccphrx_ccval; - hcrx->ccid3hcrx_bytes_recv = 0; + hc->rx_tstamp_last_feedback = now; + hc->rx_last_counter = dccp_hdr(skb)->dccph_ccval; + hc->rx_bytes_recv = 0; - /* Convert to multiples of 10us */ - hcrx->ccid3hcrx_elapsed_time = - timeval_delta(&now, &packet->dccphrx_tstamp) / 10; - if (hcrx->ccid3hcrx_p == 0) - hcrx->ccid3hcrx_pinv = ~0; - else - hcrx->ccid3hcrx_pinv = 1000000 / hcrx->ccid3hcrx_p; dp->dccps_hc_rx_insert_options = 1; dccp_send_ack(sk); } static int ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb) { - const struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); + const struct ccid3_hc_rx_sock *hc = ccid3_hc_rx_sk(sk); __be32 x_recv, pinv; - BUG_ON(hcrx == NULL); - if (!(sk->sk_state == DCCP_OPEN || sk->sk_state == DCCP_PARTOPEN)) return 0; - DCCP_SKB_CB(skb)->dccpd_ccval = hcrx->ccid3hcrx_ccval_last_counter; - if (dccp_packet_without_ack(skb)) return 0; - x_recv = htonl(hcrx->ccid3hcrx_x_recv); - pinv = htonl(hcrx->ccid3hcrx_pinv); - - if ((hcrx->ccid3hcrx_elapsed_time != 0 && - dccp_insert_option_elapsed_time(sk, skb, - hcrx->ccid3hcrx_elapsed_time)) || - dccp_insert_option_timestamp(sk, skb) || - dccp_insert_option(sk, skb, TFRC_OPT_LOSS_EVENT_RATE, - &pinv, sizeof(pinv)) || - dccp_insert_option(sk, skb, TFRC_OPT_RECEIVE_RATE, - &x_recv, sizeof(x_recv))) + x_recv = htonl(hc->rx_x_recv); + pinv = htonl(hc->rx_pinv); + + if (dccp_insert_option(skb, TFRC_OPT_LOSS_EVENT_RATE, + &pinv, sizeof(pinv)) || + dccp_insert_option(skb, TFRC_OPT_RECEIVE_RATE, + &x_recv, sizeof(x_recv))) return -1; return 0; } -/* calculate first loss interval +/** + * ccid3_first_li - Implements [RFC 5348, 6.3.1] * - * returns estimated loss interval in usecs */ - -static u32 ccid3_hc_rx_calc_first_li(struct sock *sk) + * Determine the length of the first loss interval via inverse lookup. + * Assume that X_recv can be computed by the throughput equation + * s + * X_recv = -------- + * R * fval + * Find some p such that f(p) = fval; return 1/p (scaled). + */ +static u32 ccid3_first_li(struct sock *sk) { - struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); - struct dccp_rx_hist_entry *entry, *next, *tail = NULL; - u32 rtt, delta, x_recv, fval, p, tmp2; - struct timeval tstamp = { 0, }; - int interval = 0; - int win_count = 0; - int step = 0; - u64 tmp1; - - list_for_each_entry_safe(entry, next, &hcrx->ccid3hcrx_hist, - dccphrx_node) { - if (dccp_rx_hist_entry_data_packet(entry)) { - tail = entry; - - switch (step) { - case 0: - tstamp = entry->dccphrx_tstamp; - win_count = entry->dccphrx_ccval; - step = 1; - break; - case 1: - interval = win_count - entry->dccphrx_ccval; - if (interval < 0) - interval += TFRC_WIN_COUNT_LIMIT; - if (interval > 4) - goto found; - break; - } + struct ccid3_hc_rx_sock *hc = ccid3_hc_rx_sk(sk); + u32 x_recv, p, delta; + u64 fval; + + if (hc->rx_rtt == 0) { + DCCP_WARN("No RTT estimate available, using fallback RTT\n"); + hc->rx_rtt = DCCP_FALLBACK_RTT; + } + + delta = ktime_to_us(net_timedelta(hc->rx_tstamp_last_feedback)); + x_recv = scaled_div32(hc->rx_bytes_recv, delta); + if (x_recv == 0) { /* would also trigger divide-by-zero */ + DCCP_WARN("X_recv==0\n"); + if (hc->rx_x_recv == 0) { + DCCP_BUG("stored value of X_recv is zero"); + return ~0U; } + x_recv = hc->rx_x_recv; } - if (unlikely(step == 0)) { - LIMIT_NETDEBUG(KERN_WARNING "%s: %s, sk=%p, packet history " - "contains no data packets!\n", - __FUNCTION__, dccp_role(sk), sk); - return ~0; - } - - if (unlikely(interval == 0)) { - LIMIT_NETDEBUG(KERN_WARNING "%s: %s, sk=%p, Could not find a " - "win_count interval > 0. Defaulting to 1\n", - __FUNCTION__, dccp_role(sk), sk); - interval = 1; - } -found: - if (!tail) { - LIMIT_NETDEBUG(KERN_WARNING "%s: tail is null\n", - __FUNCTION__); - return ~0; - } - rtt = timeval_delta(&tstamp, &tail->dccphrx_tstamp) * 4 / interval; - ccid3_pr_debug("%s, sk=%p, approximated RTT to %uus\n", - dccp_role(sk), sk, rtt); - if (rtt == 0) - rtt = 1; - - dccp_timestamp(sk, &tstamp); - delta = timeval_delta(&tstamp, &hcrx->ccid3hcrx_tstamp_last_feedback); - x_recv = usecs_div(hcrx->ccid3hcrx_bytes_recv, delta); - - if (x_recv == 0) - x_recv = hcrx->ccid3hcrx_x_recv; - - tmp1 = (u64)x_recv * (u64)rtt; - do_div(tmp1,10000000); - tmp2 = (u32)tmp1; - - if (!tmp2) { - LIMIT_NETDEBUG(KERN_WARNING "tmp2 = 0 " - "%s: x_recv = %u, rtt =%u\n", - __FUNCTION__, x_recv, rtt); - return ~0; - } - - fval = (hcrx->ccid3hcrx_s * 100000) / tmp2; - /* do not alter order above or you will get overflow on 32 bit */ + fval = scaled_div(hc->rx_s, hc->rx_rtt); + fval = scaled_div32(fval, x_recv); p = tfrc_calc_x_reverse_lookup(fval); - ccid3_pr_debug("%s, sk=%p, receive rate=%u bytes/s, implied " - "loss rate=%u\n", dccp_role(sk), sk, x_recv, p); - - if (p == 0) - return ~0; - else - return 1000000 / p; -} - -static void ccid3_hc_rx_update_li(struct sock *sk, u64 seq_loss, u8 win_loss) -{ - struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); - struct dccp_li_hist_entry *head; - u64 seq_temp; - - if (list_empty(&hcrx->ccid3hcrx_li_hist)) { - if (!dccp_li_hist_interval_new(ccid3_li_hist, - &hcrx->ccid3hcrx_li_hist, seq_loss, win_loss)) - return; - - head = list_entry(hcrx->ccid3hcrx_li_hist.next, - struct dccp_li_hist_entry, dccplih_node); - head->dccplih_interval = ccid3_hc_rx_calc_first_li(sk); - } else { - struct dccp_li_hist_entry *entry; - struct list_head *tail; - - head = list_entry(hcrx->ccid3hcrx_li_hist.next, - struct dccp_li_hist_entry, dccplih_node); - /* FIXME win count check removed as was wrong */ - /* should make this check with receive history */ - /* and compare there as per section 10.2 of RFC4342 */ - - /* new loss event detected */ - /* calculate last interval length */ - seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_loss); - entry = dccp_li_hist_entry_new(ccid3_li_hist, SLAB_ATOMIC); - - if (entry == NULL) { - printk(KERN_CRIT "%s: out of memory\n",__FUNCTION__); - dump_stack(); - return; - } - - list_add(&entry->dccplih_node, &hcrx->ccid3hcrx_li_hist); - tail = hcrx->ccid3hcrx_li_hist.prev; - list_del(tail); - kmem_cache_free(ccid3_li_hist->dccplih_slab, tail); + ccid3_pr_debug("%s(%p), receive rate=%u bytes/s, implied " + "loss rate=%u\n", dccp_role(sk), sk, x_recv, p); - /* Create the newest interval */ - entry->dccplih_seqno = seq_loss; - entry->dccplih_interval = seq_temp; - entry->dccplih_win_count = win_loss; - } + return p == 0 ? ~0U : scaled_div(1, p); } -static int ccid3_hc_rx_detect_loss(struct sock *sk, - struct dccp_rx_hist_entry *packet) +static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) { - struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); - struct dccp_rx_hist_entry *rx_hist = dccp_rx_hist_head(&hcrx->ccid3hcrx_hist); - u64 seqno = packet->dccphrx_seqno; - u64 tmp_seqno; - int loss = 0; - u8 ccval; - - - tmp_seqno = hcrx->ccid3hcrx_seqno_nonloss; - - if (!rx_hist || - follows48(packet->dccphrx_seqno, hcrx->ccid3hcrx_seqno_nonloss)) { - hcrx->ccid3hcrx_seqno_nonloss = seqno; - hcrx->ccid3hcrx_ccval_nonloss = packet->dccphrx_ccval; - goto detect_out; - } - - - while (dccp_delta_seqno(hcrx->ccid3hcrx_seqno_nonloss, seqno) - > TFRC_RECV_NUM_LATE_LOSS) { - loss = 1; - ccid3_hc_rx_update_li(sk, hcrx->ccid3hcrx_seqno_nonloss, - hcrx->ccid3hcrx_ccval_nonloss); - tmp_seqno = hcrx->ccid3hcrx_seqno_nonloss; - dccp_inc_seqno(&tmp_seqno); - hcrx->ccid3hcrx_seqno_nonloss = tmp_seqno; - dccp_inc_seqno(&tmp_seqno); - while (dccp_rx_hist_find_entry(&hcrx->ccid3hcrx_hist, - tmp_seqno, &ccval)) { - hcrx->ccid3hcrx_seqno_nonloss = tmp_seqno; - hcrx->ccid3hcrx_ccval_nonloss = ccval; - dccp_inc_seqno(&tmp_seqno); + struct ccid3_hc_rx_sock *hc = ccid3_hc_rx_sk(sk); + enum ccid3_fback_type do_feedback = CCID3_FBACK_NONE; + const u64 ndp = dccp_sk(sk)->dccps_options_received.dccpor_ndp; + const bool is_data_packet = dccp_data_packet(skb); + + if (unlikely(hc->rx_state == TFRC_RSTATE_NO_DATA)) { + if (is_data_packet) { + const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4; + do_feedback = CCID3_FBACK_INITIAL; + ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA); + hc->rx_s = payload; + /* + * Not necessary to update rx_bytes_recv here, + * since X_recv = 0 for the first feedback packet (cf. + * RFC 3448, 6.3) -- gerrit + */ } + goto update_records; } - /* FIXME - this code could be simplified with above while */ - /* but works at moment */ - if (follows48(packet->dccphrx_seqno, hcrx->ccid3hcrx_seqno_nonloss)) { - hcrx->ccid3hcrx_seqno_nonloss = seqno; - hcrx->ccid3hcrx_ccval_nonloss = packet->dccphrx_ccval; - } - -detect_out: - dccp_rx_hist_add_packet(ccid3_rx_hist, &hcrx->ccid3hcrx_hist, - &hcrx->ccid3hcrx_li_hist, packet, - hcrx->ccid3hcrx_seqno_nonloss); - return loss; -} - -static void ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) -{ - struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); - const struct dccp_options_received *opt_recv; - struct dccp_rx_hist_entry *packet; - struct timeval now; - u8 win_count; - u32 p_prev, rtt_prev, r_sample, t_elapsed; - int loss; - - BUG_ON(hcrx == NULL || - !(hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA || - hcrx->ccid3hcrx_state == TFRC_RSTATE_DATA)); - - opt_recv = &dccp_sk(sk)->dccps_options_received; - - switch (DCCP_SKB_CB(skb)->dccpd_type) { - case DCCP_PKT_ACK: - if (hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA) - return; - case DCCP_PKT_DATAACK: - if (opt_recv->dccpor_timestamp_echo == 0) - break; - rtt_prev = hcrx->ccid3hcrx_rtt; - dccp_timestamp(sk, &now); - timeval_sub_usecs(&now, opt_recv->dccpor_timestamp_echo * 10); - r_sample = timeval_usecs(&now); - t_elapsed = opt_recv->dccpor_elapsed_time * 10; - - if (unlikely(r_sample <= t_elapsed)) - LIMIT_NETDEBUG(KERN_WARNING "%s: r_sample=%uus, " - "t_elapsed=%uus\n", - __FUNCTION__, r_sample, t_elapsed); - else - r_sample -= t_elapsed; - - if (hcrx->ccid3hcrx_state == TFRC_RSTATE_NO_DATA) - hcrx->ccid3hcrx_rtt = r_sample; - else - hcrx->ccid3hcrx_rtt = (hcrx->ccid3hcrx_rtt * 9) / 10 + - r_sample / 10; + if (tfrc_rx_hist_duplicate(&hc->rx_hist, skb)) + return; /* done receiving */ - if (rtt_prev != hcrx->ccid3hcrx_rtt) - ccid3_pr_debug("%s, New RTT=%uus, elapsed time=%u\n", - dccp_role(sk), hcrx->ccid3hcrx_rtt, - opt_recv->dccpor_elapsed_time); - break; - case DCCP_PKT_DATA: - break; - default: /* We're not interested in other packet types, move along */ - return; + if (is_data_packet) { + const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4; + /* + * Update moving-average of s and the sum of received payload bytes + */ + hc->rx_s = tfrc_ewma(hc->rx_s, payload, 9); + hc->rx_bytes_recv += payload; } - packet = dccp_rx_hist_entry_new(ccid3_rx_hist, sk, opt_recv->dccpor_ndp, - skb, SLAB_ATOMIC); - if (unlikely(packet == NULL)) { - LIMIT_NETDEBUG(KERN_WARNING "%s: %s, sk=%p, Not enough mem to " - "add rx packet to history, consider it lost!\n", - __FUNCTION__, dccp_role(sk), sk); - return; + /* + * Perform loss detection and handle pending losses + */ + if (tfrc_rx_handle_loss(&hc->rx_hist, &hc->rx_li_hist, + skb, ndp, ccid3_first_li, sk)) { + do_feedback = CCID3_FBACK_PARAM_CHANGE; + goto done_receiving; } - win_count = packet->dccphrx_ccval; - - loss = ccid3_hc_rx_detect_loss(sk, packet); + if (tfrc_rx_hist_loss_pending(&hc->rx_hist)) + return; /* done receiving */ - if (DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK) - return; + /* + * Handle data packets: RTT sampling and monitoring p + */ + if (unlikely(!is_data_packet)) + goto update_records; - switch (hcrx->ccid3hcrx_state) { - case TFRC_RSTATE_NO_DATA: - ccid3_pr_debug("%s, sk=%p(%s), skb=%p, sending initial " - "feedback\n", - dccp_role(sk), sk, - dccp_state_name(sk->sk_state), skb); - ccid3_hc_rx_send_feedback(sk); - ccid3_hc_rx_set_state(sk, TFRC_RSTATE_DATA); - return; - case TFRC_RSTATE_DATA: - hcrx->ccid3hcrx_bytes_recv += skb->len - - dccp_hdr(skb)->dccph_doff * 4; - if (loss) - break; + if (!tfrc_lh_is_initialised(&hc->rx_li_hist)) { + const u32 sample = tfrc_rx_hist_sample_rtt(&hc->rx_hist, skb); + /* + * Empty loss history: no loss so far, hence p stays 0. + * Sample RTT values, since an RTT estimate is required for the + * computation of p when the first loss occurs; RFC 3448, 6.3.1. + */ + if (sample != 0) + hc->rx_rtt = tfrc_ewma(hc->rx_rtt, sample, 9); - dccp_timestamp(sk, &now); - if (timeval_delta(&now, &hcrx->ccid3hcrx_tstamp_last_ack) >= - hcrx->ccid3hcrx_rtt) { - hcrx->ccid3hcrx_tstamp_last_ack = now; - ccid3_hc_rx_send_feedback(sk); - } - return; - default: - printk(KERN_CRIT "%s: %s, sk=%p, Illegal state (%d)!\n", - __FUNCTION__, dccp_role(sk), sk, hcrx->ccid3hcrx_state); - dump_stack(); - return; + } else if (tfrc_lh_update_i_mean(&hc->rx_li_hist, skb)) { + /* + * Step (3) of [RFC 3448, 6.1]: Recompute I_mean and, if I_mean + * has decreased (resp. p has increased), send feedback now. + */ + do_feedback = CCID3_FBACK_PARAM_CHANGE; } - /* Dealing with packet loss */ - ccid3_pr_debug("%s, sk=%p(%s), data loss! Reacting...\n", - dccp_role(sk), sk, dccp_state_name(sk->sk_state)); - - p_prev = hcrx->ccid3hcrx_p; - - /* Calculate loss event rate */ - if (!list_empty(&hcrx->ccid3hcrx_li_hist)) { - u32 i_mean = dccp_li_hist_calc_i_mean(&hcrx->ccid3hcrx_li_hist); + /* + * Check if the periodic once-per-RTT feedback is due; RFC 4342, 10.3 + */ + if (SUB16(dccp_hdr(skb)->dccph_ccval, hc->rx_last_counter) > 3) + do_feedback = CCID3_FBACK_PERIODIC; - /* Scaling up by 1000000 as fixed decimal */ - if (i_mean != 0) - hcrx->ccid3hcrx_p = 1000000 / i_mean; - } else { - printk(KERN_CRIT "%s: empty loss hist\n",__FUNCTION__); - dump_stack(); - } +update_records: + tfrc_rx_hist_add_packet(&hc->rx_hist, skb, ndp); - if (hcrx->ccid3hcrx_p > p_prev) { - ccid3_hc_rx_send_feedback(sk); - return; - } +done_receiving: + if (do_feedback) + ccid3_hc_rx_send_feedback(sk, skb, do_feedback); } static int ccid3_hc_rx_init(struct ccid *ccid, struct sock *sk) { - struct dccp_sock *dp = dccp_sk(sk); - struct ccid3_hc_rx_sock *hcrx = ccid_priv(ccid); - - ccid3_pr_debug("%s, sk=%p\n", dccp_role(sk), sk); + struct ccid3_hc_rx_sock *hc = ccid_priv(ccid); - if (dp->dccps_packet_size >= TFRC_MIN_PACKET_SIZE && - dp->dccps_packet_size <= TFRC_MAX_PACKET_SIZE) - hcrx->ccid3hcrx_s = dp->dccps_packet_size; - else - hcrx->ccid3hcrx_s = TFRC_STD_PACKET_SIZE; - - hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA; - INIT_LIST_HEAD(&hcrx->ccid3hcrx_hist); - INIT_LIST_HEAD(&hcrx->ccid3hcrx_li_hist); - dccp_timestamp(sk, &hcrx->ccid3hcrx_tstamp_last_ack); - hcrx->ccid3hcrx_tstamp_last_feedback = hcrx->ccid3hcrx_tstamp_last_ack; - hcrx->ccid3hcrx_rtt = 5000; /* XXX 5ms for now... */ - return 0; + hc->rx_state = TFRC_RSTATE_NO_DATA; + tfrc_lh_init(&hc->rx_li_hist); + return tfrc_rx_hist_alloc(&hc->rx_hist); } static void ccid3_hc_rx_exit(struct sock *sk) { - struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); - - BUG_ON(hcrx == NULL); + struct ccid3_hc_rx_sock *hc = ccid3_hc_rx_sk(sk); - ccid3_hc_rx_set_state(sk, TFRC_RSTATE_TERM); - - /* Empty packet history */ - dccp_rx_hist_purge(ccid3_rx_hist, &hcrx->ccid3hcrx_hist); - - /* Empty loss interval history */ - dccp_li_hist_purge(ccid3_li_hist, &hcrx->ccid3hcrx_li_hist); + tfrc_rx_hist_purge(&hc->rx_hist); + tfrc_lh_cleanup(&hc->rx_li_hist); } static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info) { - const struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); - - /* Listen socks doesn't have a private CCID block */ - if (sk->sk_state == DCCP_LISTEN) - return; - - BUG_ON(hcrx == NULL); - - info->tcpi_ca_state = hcrx->ccid3hcrx_state; - info->tcpi_options |= TCPI_OPT_TIMESTAMPS; - info->tcpi_rcv_rtt = hcrx->ccid3hcrx_rtt; -} - -static void ccid3_hc_tx_get_info(struct sock *sk, struct tcp_info *info) -{ - const struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); - - /* Listen socks doesn't have a private CCID block */ - if (sk->sk_state == DCCP_LISTEN) - return; - - BUG_ON(hctx == NULL); - - info->tcpi_rto = hctx->ccid3hctx_t_rto; - info->tcpi_rtt = hctx->ccid3hctx_rtt; + info->tcpi_ca_state = ccid3_hc_rx_sk(sk)->rx_state; + info->tcpi_options |= TCPI_OPT_TIMESTAMPS; + info->tcpi_rcv_rtt = ccid3_hc_rx_sk(sk)->rx_rtt; } static int ccid3_hc_rx_getsockopt(struct sock *sk, const int optname, int len, u32 __user *optval, int __user *optlen) { - const struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk); + const struct ccid3_hc_rx_sock *hc = ccid3_hc_rx_sk(sk); + struct tfrc_rx_info rx_info; const void *val; - - /* Listen socks doesn't have a private CCID block */ - if (sk->sk_state == DCCP_LISTEN) - return -EINVAL; switch (optname) { case DCCP_SOCKOPT_CCID_RX_INFO: - if (len < sizeof(hcrx->ccid3hcrx_tfrc)) - return -EINVAL; - len = sizeof(hcrx->ccid3hcrx_tfrc); - val = &hcrx->ccid3hcrx_tfrc; - break; - default: - return -ENOPROTOOPT; - } - - if (put_user(len, optlen) || copy_to_user(optval, val, len)) - return -EFAULT; - - return 0; -} - -static int ccid3_hc_tx_getsockopt(struct sock *sk, const int optname, int len, - u32 __user *optval, int __user *optlen) -{ - const struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); - const void *val; - - /* Listen socks doesn't have a private CCID block */ - if (sk->sk_state == DCCP_LISTEN) - return -EINVAL; - - switch (optname) { - case DCCP_SOCKOPT_CCID_TX_INFO: - if (len < sizeof(hctx->ccid3hctx_tfrc)) + if (len < sizeof(rx_info)) return -EINVAL; - len = sizeof(hctx->ccid3hctx_tfrc); - val = &hctx->ccid3hctx_tfrc; + rx_info.tfrcrx_x_recv = hc->rx_x_recv; + rx_info.tfrcrx_rtt = hc->rx_rtt; + rx_info.tfrcrx_p = tfrc_invert_loss_event_rate(hc->rx_pinv); + len = sizeof(rx_info); + val = &rx_info; break; default: return -ENOPROTOOPT; @@ -1239,17 +843,15 @@ static int ccid3_hc_tx_getsockopt(struct sock *sk, const int optname, int len, return 0; } -static struct ccid_operations ccid3 = { +struct ccid_operations ccid3_ops = { .ccid_id = DCCPC_CCID3, - .ccid_name = "ccid3", - .ccid_owner = THIS_MODULE, + .ccid_name = "TCP-Friendly Rate Control", .ccid_hc_tx_obj_size = sizeof(struct ccid3_hc_tx_sock), .ccid_hc_tx_init = ccid3_hc_tx_init, .ccid_hc_tx_exit = ccid3_hc_tx_exit, .ccid_hc_tx_send_packet = ccid3_hc_tx_send_packet, .ccid_hc_tx_packet_sent = ccid3_hc_tx_packet_sent, .ccid_hc_tx_packet_recv = ccid3_hc_tx_packet_recv, - .ccid_hc_tx_insert_options = ccid3_hc_tx_insert_options, .ccid_hc_tx_parse_options = ccid3_hc_tx_parse_options, .ccid_hc_rx_obj_size = sizeof(struct ccid3_hc_rx_sock), .ccid_hc_rx_init = ccid3_hc_rx_init, @@ -1261,66 +863,8 @@ static struct ccid_operations ccid3 = { .ccid_hc_rx_getsockopt = ccid3_hc_rx_getsockopt, .ccid_hc_tx_getsockopt = ccid3_hc_tx_getsockopt, }; - -module_param(ccid3_debug, int, 0444); -MODULE_PARM_DESC(ccid3_debug, "Enable debug messages"); - -static __init int ccid3_module_init(void) -{ - int rc = -ENOBUFS; - - ccid3_rx_hist = dccp_rx_hist_new("ccid3"); - if (ccid3_rx_hist == NULL) - goto out; - - ccid3_tx_hist = dccp_tx_hist_new("ccid3"); - if (ccid3_tx_hist == NULL) - goto out_free_rx; - - ccid3_li_hist = dccp_li_hist_new("ccid3"); - if (ccid3_li_hist == NULL) - goto out_free_tx; - - rc = ccid_register(&ccid3); - if (rc != 0) - goto out_free_loss_interval_history; -out: - return rc; - -out_free_loss_interval_history: - dccp_li_hist_delete(ccid3_li_hist); - ccid3_li_hist = NULL; -out_free_tx: - dccp_tx_hist_delete(ccid3_tx_hist); - ccid3_tx_hist = NULL; -out_free_rx: - dccp_rx_hist_delete(ccid3_rx_hist); - ccid3_rx_hist = NULL; - goto out; -} -module_init(ccid3_module_init); - -static __exit void ccid3_module_exit(void) -{ - ccid_unregister(&ccid3); - - if (ccid3_tx_hist != NULL) { - dccp_tx_hist_delete(ccid3_tx_hist); - ccid3_tx_hist = NULL; - } - if (ccid3_rx_hist != NULL) { - dccp_rx_hist_delete(ccid3_rx_hist); - ccid3_rx_hist = NULL; - } - if (ccid3_li_hist != NULL) { - dccp_li_hist_delete(ccid3_li_hist); - ccid3_li_hist = NULL; - } -} -module_exit(ccid3_module_exit); -MODULE_AUTHOR("Ian McDonald <ian.mcdonald@jandi.co.nz>, " - "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>"); -MODULE_DESCRIPTION("DCCP TFRC CCID3 CCID"); -MODULE_LICENSE("GPL"); -MODULE_ALIAS("net-dccp-ccid-3"); +#ifdef CONFIG_IP_DCCP_CCID3_DEBUG +module_param(ccid3_debug, bool, 0644); +MODULE_PARM_DESC(ccid3_debug, "Enable CCID-3 debug messages"); +#endif diff --git a/net/dccp/ccids/ccid3.h b/net/dccp/ccids/ccid3.h index 0a2cb7536d2..1a9933c2967 100644 --- a/net/dccp/ccids/ccid3.h +++ b/net/dccp/ccids/ccid3.h @@ -1,7 +1,6 @@ /* - * net/dccp/ccids/ccid3.h - * - * Copyright (c) 2005-6 The University of Waikato, Hamilton, New Zealand. + * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK * * An implementation of the DCCP protocol * @@ -36,28 +35,31 @@ #ifndef _DCCP_CCID3_H_ #define _DCCP_CCID3_H_ +#include <linux/ktime.h> #include <linux/list.h> -#include <linux/time.h> #include <linux/types.h> #include <linux/tfrc.h> +#include "lib/tfrc.h" #include "../ccid.h" -#define TFRC_MIN_PACKET_SIZE 16 -#define TFRC_STD_PACKET_SIZE 256 -#define TFRC_MAX_PACKET_SIZE 65535 - -/* Two seconds as per CCID3 spec */ +/* Two seconds as per RFC 5348, 4.2 */ #define TFRC_INITIAL_TIMEOUT (2 * USEC_PER_SEC) -#define TFRC_INITIAL_IPI (USEC_PER_SEC / 4) - -/* In usecs - half the scheduling granularity as per RFC3448 4.6 */ -#define TFRC_OPSYS_HALF_TIME_GRAN (USEC_PER_SEC / (2 * HZ)) +/* Parameter t_mbi from [RFC 3448, 4.3]: backoff interval in seconds */ +#define TFRC_T_MBI 64 -/* In seconds */ -#define TFRC_MAX_BACK_OFF_TIME 64 - -#define TFRC_SMALLEST_P 40 +/* + * The t_delta parameter (RFC 5348, 8.3): delays of less than %USEC_PER_MSEC are + * rounded down to 0, since sk_reset_timer() here uses millisecond granularity. + * Hence we can use a constant t_delta = %USEC_PER_MSEC when HZ >= 500. A coarse + * resolution of HZ < 500 means that the error is below one timer tick (t_gran) + * when using the constant t_delta = t_gran / 2 = %USEC_PER_SEC / (2 * HZ). + */ +#if (HZ >= 500) +# define TFRC_T_DELTA USEC_PER_MSEC +#else +# define TFRC_T_DELTA (USEC_PER_SEC / (2 * HZ)) +#endif enum ccid3_options { TFRC_OPT_LOSS_EVENT_RATE = 192, @@ -65,83 +67,94 @@ enum ccid3_options { TFRC_OPT_RECEIVE_RATE = 194, }; -struct ccid3_options_received { - u64 ccid3or_seqno:48, - ccid3or_loss_intervals_idx:16; - u16 ccid3or_loss_intervals_len; - u32 ccid3or_loss_event_rate; - u32 ccid3or_receive_rate; +/* TFRC sender states */ +enum ccid3_hc_tx_states { + TFRC_SSTATE_NO_SENT = 1, + TFRC_SSTATE_NO_FBACK, + TFRC_SSTATE_FBACK, }; -/** struct ccid3_hc_tx_sock - CCID3 sender half connection sock - * - * @ccid3hctx_state - Sender state - * @ccid3hctx_x - Current sending rate - * @ccid3hctx_x_recv - Receive rate - * @ccid3hctx_x_calc - Calculated send (?) rate - * @ccid3hctx_s - Packet size - * @ccid3hctx_rtt - Estimate of current round trip time in usecs - * @@ccid3hctx_p - Current loss event rate (0-1) scaled by 1000000 - * @ccid3hctx_last_win_count - Last window counter sent - * @ccid3hctx_t_last_win_count - Timestamp of earliest packet - * with last_win_count value sent - * @ccid3hctx_no_feedback_timer - Handle to no feedback timer - * @ccid3hctx_idle - FIXME - * @ccid3hctx_t_ld - Time last doubled during slow start - * @ccid3hctx_t_nom - Nominal send time of next packet - * @ccid3hctx_t_ipi - Interpacket (send) interval - * @ccid3hctx_delta - Send timer delta - * @ccid3hctx_hist - Packet history - */ +/** + * struct ccid3_hc_tx_sock - CCID3 sender half-connection socket + * @tx_x: Current sending rate in 64 * bytes per second + * @tx_x_recv: Receive rate in 64 * bytes per second + * @tx_x_calc: Calculated rate in bytes per second + * @tx_rtt: Estimate of current round trip time in usecs + * @tx_p: Current loss event rate (0-1) scaled by 1000000 + * @tx_s: Packet size in bytes + * @tx_t_rto: Nofeedback Timer setting in usecs + * @tx_t_ipi: Interpacket (send) interval (RFC 3448, 4.6) in usecs + * @tx_state: Sender state, one of %ccid3_hc_tx_states + * @tx_last_win_count: Last window counter sent + * @tx_t_last_win_count: Timestamp of earliest packet + * with last_win_count value sent + * @tx_no_feedback_timer: Handle to no feedback timer + * @tx_t_ld: Time last doubled during slow start + * @tx_t_nom: Nominal send time of next packet + * @tx_hist: Packet history + */ struct ccid3_hc_tx_sock { - struct tfrc_tx_info ccid3hctx_tfrc; -#define ccid3hctx_x ccid3hctx_tfrc.tfrctx_x -#define ccid3hctx_x_recv ccid3hctx_tfrc.tfrctx_x_recv -#define ccid3hctx_x_calc ccid3hctx_tfrc.tfrctx_x_calc -#define ccid3hctx_rtt ccid3hctx_tfrc.tfrctx_rtt -#define ccid3hctx_p ccid3hctx_tfrc.tfrctx_p -#define ccid3hctx_t_rto ccid3hctx_tfrc.tfrctx_rto -#define ccid3hctx_t_ipi ccid3hctx_tfrc.tfrctx_ipi - u16 ccid3hctx_s; - u8 ccid3hctx_state; - u8 ccid3hctx_last_win_count; - u8 ccid3hctx_idle; - struct timeval ccid3hctx_t_last_win_count; - struct timer_list ccid3hctx_no_feedback_timer; - struct timeval ccid3hctx_t_ld; - struct timeval ccid3hctx_t_nom; - u32 ccid3hctx_delta; - struct list_head ccid3hctx_hist; - struct ccid3_options_received ccid3hctx_options_received; -}; - -struct ccid3_hc_rx_sock { - struct tfrc_rx_info ccid3hcrx_tfrc; -#define ccid3hcrx_x_recv ccid3hcrx_tfrc.tfrcrx_x_recv -#define ccid3hcrx_rtt ccid3hcrx_tfrc.tfrcrx_rtt -#define ccid3hcrx_p ccid3hcrx_tfrc.tfrcrx_p - u64 ccid3hcrx_seqno_nonloss:48, - ccid3hcrx_ccval_nonloss:4, - ccid3hcrx_state:8, - ccid3hcrx_ccval_last_counter:4; - u32 ccid3hcrx_bytes_recv; - struct timeval ccid3hcrx_tstamp_last_feedback; - struct timeval ccid3hcrx_tstamp_last_ack; - struct list_head ccid3hcrx_hist; - struct list_head ccid3hcrx_li_hist; - u16 ccid3hcrx_s; - u32 ccid3hcrx_pinv; - u32 ccid3hcrx_elapsed_time; + u64 tx_x; + u64 tx_x_recv; + u32 tx_x_calc; + u32 tx_rtt; + u32 tx_p; + u32 tx_t_rto; + u32 tx_t_ipi; + u16 tx_s; + enum ccid3_hc_tx_states tx_state:8; + u8 tx_last_win_count; + ktime_t tx_t_last_win_count; + struct timer_list tx_no_feedback_timer; + ktime_t tx_t_ld; + ktime_t tx_t_nom; + struct tfrc_tx_hist_entry *tx_hist; }; static inline struct ccid3_hc_tx_sock *ccid3_hc_tx_sk(const struct sock *sk) { - return ccid_priv(dccp_sk(sk)->dccps_hc_tx_ccid); + struct ccid3_hc_tx_sock *hctx = ccid_priv(dccp_sk(sk)->dccps_hc_tx_ccid); + BUG_ON(hctx == NULL); + return hctx; } +/* TFRC receiver states */ +enum ccid3_hc_rx_states { + TFRC_RSTATE_NO_DATA = 1, + TFRC_RSTATE_DATA, +}; + +/** + * struct ccid3_hc_rx_sock - CCID3 receiver half-connection socket + * @rx_last_counter: Tracks window counter (RFC 4342, 8.1) + * @rx_state: Receiver state, one of %ccid3_hc_rx_states + * @rx_bytes_recv: Total sum of DCCP payload bytes + * @rx_x_recv: Receiver estimate of send rate (RFC 3448, sec. 4.3) + * @rx_rtt: Receiver estimate of RTT + * @rx_tstamp_last_feedback: Time at which last feedback was sent + * @rx_hist: Packet history (loss detection + RTT sampling) + * @rx_li_hist: Loss Interval database + * @rx_s: Received packet size in bytes + * @rx_pinv: Inverse of Loss Event Rate (RFC 4342, sec. 8.5) + */ +struct ccid3_hc_rx_sock { + u8 rx_last_counter:4; + enum ccid3_hc_rx_states rx_state:8; + u32 rx_bytes_recv; + u32 rx_x_recv; + u32 rx_rtt; + ktime_t rx_tstamp_last_feedback; + struct tfrc_rx_hist rx_hist; + struct tfrc_loss_hist rx_li_hist; + u16 rx_s; +#define rx_pinv rx_li_hist.i_mean +}; + static inline struct ccid3_hc_rx_sock *ccid3_hc_rx_sk(const struct sock *sk) { - return ccid_priv(dccp_sk(sk)->dccps_hc_rx_ccid); + struct ccid3_hc_rx_sock *hcrx = ccid_priv(dccp_sk(sk)->dccps_hc_rx_ccid); + BUG_ON(hcrx == NULL); + return hcrx; } #endif /* _DCCP_CCID3_H_ */ diff --git a/net/dccp/ccids/lib/Makefile b/net/dccp/ccids/lib/Makefile deleted file mode 100644 index 5f940a6cbac..00000000000 --- a/net/dccp/ccids/lib/Makefile +++ /dev/null @@ -1,3 +0,0 @@ -obj-$(CONFIG_IP_DCCP_TFRC_LIB) += dccp_tfrc_lib.o - -dccp_tfrc_lib-y := loss_interval.o packet_history.o tfrc_equation.o diff --git a/net/dccp/ccids/lib/loss_interval.c b/net/dccp/ccids/lib/loss_interval.c index 906c81ab9d4..57f9fd78c4d 100644 --- a/net/dccp/ccids/lib/loss_interval.c +++ b/net/dccp/ccids/lib/loss_interval.c @@ -1,8 +1,7 @@ /* - * net/dccp/ccids/lib/loss_interval.c - * - * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand. - * Copyright (c) 2005-6 Ian McDonald <ian.mcdonald@jandi.co.nz> + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK + * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. + * Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz> * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br> * * This program is free software; you can redistribute it and/or modify @@ -10,134 +9,177 @@ * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. */ - -#include <linux/module.h> #include <net/sock.h> +#include "tfrc.h" -#include "loss_interval.h" +static struct kmem_cache *tfrc_lh_slab __read_mostly; +/* Loss Interval weights from [RFC 3448, 5.4], scaled by 10 */ +static const int tfrc_lh_weights[NINTERVAL] = { 10, 10, 10, 10, 8, 6, 4, 2 }; -struct dccp_li_hist *dccp_li_hist_new(const char *name) +/* implements LIFO semantics on the array */ +static inline u8 LIH_INDEX(const u8 ctr) { - struct dccp_li_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC); - static const char dccp_li_hist_mask[] = "li_hist_%s"; - char *slab_name; - - if (hist == NULL) - goto out; - - slab_name = kmalloc(strlen(name) + sizeof(dccp_li_hist_mask) - 1, - GFP_ATOMIC); - if (slab_name == NULL) - goto out_free_hist; - - sprintf(slab_name, dccp_li_hist_mask, name); - hist->dccplih_slab = kmem_cache_create(slab_name, - sizeof(struct dccp_li_hist_entry), - 0, SLAB_HWCACHE_ALIGN, - NULL, NULL); - if (hist->dccplih_slab == NULL) - goto out_free_slab_name; -out: - return hist; -out_free_slab_name: - kfree(slab_name); -out_free_hist: - kfree(hist); - hist = NULL; - goto out; + return LIH_SIZE - 1 - (ctr % LIH_SIZE); } -EXPORT_SYMBOL_GPL(dccp_li_hist_new); +/* the `counter' index always points at the next entry to be populated */ +static inline struct tfrc_loss_interval *tfrc_lh_peek(struct tfrc_loss_hist *lh) +{ + return lh->counter ? lh->ring[LIH_INDEX(lh->counter - 1)] : NULL; +} -void dccp_li_hist_delete(struct dccp_li_hist *hist) +/* given i with 0 <= i <= k, return I_i as per the rfc3448bis notation */ +static inline u32 tfrc_lh_get_interval(struct tfrc_loss_hist *lh, const u8 i) { - const char* name = kmem_cache_name(hist->dccplih_slab); + BUG_ON(i >= lh->counter); + return lh->ring[LIH_INDEX(lh->counter - i - 1)]->li_length; +} - kmem_cache_destroy(hist->dccplih_slab); - kfree(name); - kfree(hist); +/* + * On-demand allocation and de-allocation of entries + */ +static struct tfrc_loss_interval *tfrc_lh_demand_next(struct tfrc_loss_hist *lh) +{ + if (lh->ring[LIH_INDEX(lh->counter)] == NULL) + lh->ring[LIH_INDEX(lh->counter)] = kmem_cache_alloc(tfrc_lh_slab, + GFP_ATOMIC); + return lh->ring[LIH_INDEX(lh->counter)]; } -EXPORT_SYMBOL_GPL(dccp_li_hist_delete); +void tfrc_lh_cleanup(struct tfrc_loss_hist *lh) +{ + if (!tfrc_lh_is_initialised(lh)) + return; + + for (lh->counter = 0; lh->counter < LIH_SIZE; lh->counter++) + if (lh->ring[LIH_INDEX(lh->counter)] != NULL) { + kmem_cache_free(tfrc_lh_slab, + lh->ring[LIH_INDEX(lh->counter)]); + lh->ring[LIH_INDEX(lh->counter)] = NULL; + } +} -void dccp_li_hist_purge(struct dccp_li_hist *hist, struct list_head *list) +static void tfrc_lh_calc_i_mean(struct tfrc_loss_hist *lh) { - struct dccp_li_hist_entry *entry, *next; + u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0; + int i, k = tfrc_lh_length(lh) - 1; /* k is as in rfc3448bis, 5.4 */ - list_for_each_entry_safe(entry, next, list, dccplih_node) { - list_del_init(&entry->dccplih_node); - kmem_cache_free(hist->dccplih_slab, entry); + if (k <= 0) + return; + + for (i = 0; i <= k; i++) { + i_i = tfrc_lh_get_interval(lh, i); + + if (i < k) { + i_tot0 += i_i * tfrc_lh_weights[i]; + w_tot += tfrc_lh_weights[i]; + } + if (i > 0) + i_tot1 += i_i * tfrc_lh_weights[i-1]; } -} -EXPORT_SYMBOL_GPL(dccp_li_hist_purge); + lh->i_mean = max(i_tot0, i_tot1) / w_tot; +} -/* Weights used to calculate loss event rate */ -/* - * These are integers as per section 8 of RFC3448. We can then divide by 4 * - * when we use it. +/** + * tfrc_lh_update_i_mean - Update the `open' loss interval I_0 + * For recomputing p: returns `true' if p > p_prev <=> 1/p < 1/p_prev */ -static const int dccp_li_hist_w[DCCP_LI_HIST_IVAL_F_LENGTH] = { - 4, 4, 4, 4, 3, 2, 1, 1, -}; - -u32 dccp_li_hist_calc_i_mean(struct list_head *list) +u8 tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *skb) { - struct dccp_li_hist_entry *li_entry, *li_next; - int i = 0; - u32 i_tot; - u32 i_tot0 = 0; - u32 i_tot1 = 0; - u32 w_tot = 0; - - list_for_each_entry_safe(li_entry, li_next, list, dccplih_node) { - if (li_entry->dccplih_interval != ~0) { - i_tot0 += li_entry->dccplih_interval * dccp_li_hist_w[i]; - w_tot += dccp_li_hist_w[i]; - if (i != 0) - i_tot1 += li_entry->dccplih_interval * dccp_li_hist_w[i - 1]; - } + struct tfrc_loss_interval *cur = tfrc_lh_peek(lh); + u32 old_i_mean = lh->i_mean; + s64 len; + if (cur == NULL) /* not initialised */ + return 0; - if (++i > DCCP_LI_HIST_IVAL_F_LENGTH) - break; - } + len = dccp_delta_seqno(cur->li_seqno, DCCP_SKB_CB(skb)->dccpd_seq) + 1; - if (i != DCCP_LI_HIST_IVAL_F_LENGTH) + if (len - (s64)cur->li_length <= 0) /* duplicate or reordered */ return 0; - i_tot = max(i_tot0, i_tot1); + if (SUB16(dccp_hdr(skb)->dccph_ccval, cur->li_ccval) > 4) + /* + * Implements RFC 4342, 10.2: + * If a packet S (skb) exists whose seqno comes `after' the one + * starting the current loss interval (cur) and if the modulo-16 + * distance from C(cur) to C(S) is greater than 4, consider all + * subsequent packets as belonging to a new loss interval. This + * test is necessary since CCVal may wrap between intervals. + */ + cur->li_is_closed = 1; + + if (tfrc_lh_length(lh) == 1) /* due to RFC 3448, 6.3.1 */ + return 0; - if (!w_tot) { - LIMIT_NETDEBUG(KERN_WARNING "%s: w_tot = 0\n", __FUNCTION__); - return 1; - } + cur->li_length = len; + tfrc_lh_calc_i_mean(lh); - return i_tot / w_tot; + return lh->i_mean < old_i_mean; } -EXPORT_SYMBOL_GPL(dccp_li_hist_calc_i_mean); +/* Determine if `new_loss' does begin a new loss interval [RFC 4342, 10.2] */ +static inline u8 tfrc_lh_is_new_loss(struct tfrc_loss_interval *cur, + struct tfrc_rx_hist_entry *new_loss) +{ + return dccp_delta_seqno(cur->li_seqno, new_loss->tfrchrx_seqno) > 0 && + (cur->li_is_closed || SUB16(new_loss->tfrchrx_ccval, cur->li_ccval) > 4); +} -int dccp_li_hist_interval_new(struct dccp_li_hist *hist, - struct list_head *list, const u64 seq_loss, const u8 win_loss) +/** + * tfrc_lh_interval_add - Insert new record into the Loss Interval database + * @lh: Loss Interval database + * @rh: Receive history containing a fresh loss event + * @calc_first_li: Caller-dependent routine to compute length of first interval + * @sk: Used by @calc_first_li in caller-specific way (subtyping) + * + * Updates I_mean and returns 1 if a new interval has in fact been added to @lh. + */ +int tfrc_lh_interval_add(struct tfrc_loss_hist *lh, struct tfrc_rx_hist *rh, + u32 (*calc_first_li)(struct sock *), struct sock *sk) { - struct dccp_li_hist_entry *entry; - int i; - - for (i = 0; i < DCCP_LI_HIST_IVAL_F_LENGTH; i++) { - entry = dccp_li_hist_entry_new(hist, SLAB_ATOMIC); - if (entry == NULL) { - dccp_li_hist_purge(hist, list); - dump_stack(); - return 0; - } - entry->dccplih_interval = ~0; - list_add(&entry->dccplih_node, list); + struct tfrc_loss_interval *cur = tfrc_lh_peek(lh), *new; + + if (cur != NULL && !tfrc_lh_is_new_loss(cur, tfrc_rx_hist_loss_prev(rh))) + return 0; + + new = tfrc_lh_demand_next(lh); + if (unlikely(new == NULL)) { + DCCP_CRIT("Cannot allocate/add loss record."); + return 0; } - entry->dccplih_seqno = seq_loss; - entry->dccplih_win_count = win_loss; + new->li_seqno = tfrc_rx_hist_loss_prev(rh)->tfrchrx_seqno; + new->li_ccval = tfrc_rx_hist_loss_prev(rh)->tfrchrx_ccval; + new->li_is_closed = 0; + + if (++lh->counter == 1) + lh->i_mean = new->li_length = (*calc_first_li)(sk); + else { + cur->li_length = dccp_delta_seqno(cur->li_seqno, new->li_seqno); + new->li_length = dccp_delta_seqno(new->li_seqno, + tfrc_rx_hist_last_rcv(rh)->tfrchrx_seqno) + 1; + if (lh->counter > (2*LIH_SIZE)) + lh->counter -= LIH_SIZE; + + tfrc_lh_calc_i_mean(lh); + } return 1; } -EXPORT_SYMBOL_GPL(dccp_li_hist_interval_new); +int __init tfrc_li_init(void) +{ + tfrc_lh_slab = kmem_cache_create("tfrc_li_hist", + sizeof(struct tfrc_loss_interval), 0, + SLAB_HWCACHE_ALIGN, NULL); + return tfrc_lh_slab == NULL ? -ENOBUFS : 0; +} + +void tfrc_li_exit(void) +{ + if (tfrc_lh_slab != NULL) { + kmem_cache_destroy(tfrc_lh_slab); + tfrc_lh_slab = NULL; + } +} diff --git a/net/dccp/ccids/lib/loss_interval.h b/net/dccp/ccids/lib/loss_interval.h index 0ae85f0340b..57f631a86cc 100644 --- a/net/dccp/ccids/lib/loss_interval.h +++ b/net/dccp/ccids/lib/loss_interval.h @@ -1,10 +1,9 @@ #ifndef _DCCP_LI_HIST_ #define _DCCP_LI_HIST_ /* - * net/dccp/ccids/lib/loss_interval.h - * - * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand. - * Copyright (c) 2005 Ian McDonald <ian.mcdonald@jandi.co.nz> + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK + * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. + * Copyright (c) 2005-7 Ian McDonald <ian.mcdonald@jandi.co.nz> * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br> * * This program is free software; you can redistribute it and/or modify it @@ -12,46 +11,63 @@ * Software Foundation; either version 2 of the License, or (at your option) * any later version. */ - +#include <linux/ktime.h> #include <linux/list.h> #include <linux/slab.h> -#include <linux/time.h> -#define DCCP_LI_HIST_IVAL_F_LENGTH 8 +/* + * Number of loss intervals (RFC 4342, 8.6.1). The history size is one more than + * NINTERVAL, since the `open' interval I_0 is always stored as the first entry. + */ +#define NINTERVAL 8 +#define LIH_SIZE (NINTERVAL + 1) -struct dccp_li_hist { - kmem_cache_t *dccplih_slab; +/** + * tfrc_loss_interval - Loss history record for TFRC-based protocols + * @li_seqno: Highest received seqno before the start of loss + * @li_ccval: The CCVal belonging to @li_seqno + * @li_is_closed: Whether @li_seqno is older than 1 RTT + * @li_length: Loss interval sequence length + */ +struct tfrc_loss_interval { + u64 li_seqno:48, + li_ccval:4, + li_is_closed:1; + u32 li_length; }; -extern struct dccp_li_hist *dccp_li_hist_new(const char *name); -extern void dccp_li_hist_delete(struct dccp_li_hist *hist); - -struct dccp_li_hist_entry { - struct list_head dccplih_node; - u64 dccplih_seqno:48, - dccplih_win_count:4; - u32 dccplih_interval; +/** + * tfrc_loss_hist - Loss record database + * @ring: Circular queue managed in LIFO manner + * @counter: Current count of entries (can be more than %LIH_SIZE) + * @i_mean: Current Average Loss Interval [RFC 3448, 5.4] + */ +struct tfrc_loss_hist { + struct tfrc_loss_interval *ring[LIH_SIZE]; + u8 counter; + u32 i_mean; }; -static inline struct dccp_li_hist_entry * - dccp_li_hist_entry_new(struct dccp_li_hist *hist, - const gfp_t prio) +static inline void tfrc_lh_init(struct tfrc_loss_hist *lh) +{ + memset(lh, 0, sizeof(struct tfrc_loss_hist)); +} + +static inline u8 tfrc_lh_is_initialised(struct tfrc_loss_hist *lh) { - return kmem_cache_alloc(hist->dccplih_slab, prio); + return lh->counter > 0; } -static inline void dccp_li_hist_entry_delete(struct dccp_li_hist *hist, - struct dccp_li_hist_entry *entry) +static inline u8 tfrc_lh_length(struct tfrc_loss_hist *lh) { - if (entry != NULL) - kmem_cache_free(hist->dccplih_slab, entry); + return min(lh->counter, (u8)LIH_SIZE); } -extern void dccp_li_hist_purge(struct dccp_li_hist *hist, - struct list_head *list); +struct tfrc_rx_hist; -extern u32 dccp_li_hist_calc_i_mean(struct list_head *list); +int tfrc_lh_interval_add(struct tfrc_loss_hist *, struct tfrc_rx_hist *, + u32 (*first_li)(struct sock *), struct sock *); +u8 tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *); +void tfrc_lh_cleanup(struct tfrc_loss_hist *lh); -extern int dccp_li_hist_interval_new(struct dccp_li_hist *hist, - struct list_head *list, const u64 seq_loss, const u8 win_loss); #endif /* _DCCP_LI_HIST_ */ diff --git a/net/dccp/ccids/lib/packet_history.c b/net/dccp/ccids/lib/packet_history.c index b876c9c81c6..08df7a3acb3 100644 --- a/net/dccp/ccids/lib/packet_history.c +++ b/net/dccp/ccids/lib/packet_history.c @@ -1,7 +1,6 @@ /* - * net/dccp/packet_history.c - * - * Copyright (c) 2005-6 The University of Waikato, Hamilton, New Zealand. + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK + * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. * * An implementation of the DCCP protocol * @@ -34,262 +33,417 @@ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ -#include <linux/module.h> #include <linux/string.h> - +#include <linux/slab.h> #include "packet_history.h" +#include "../../dccp.h" + +/* + * Transmitter History Routines + */ +static struct kmem_cache *tfrc_tx_hist_slab; + +int __init tfrc_tx_packet_history_init(void) +{ + tfrc_tx_hist_slab = kmem_cache_create("tfrc_tx_hist", + sizeof(struct tfrc_tx_hist_entry), + 0, SLAB_HWCACHE_ALIGN, NULL); + return tfrc_tx_hist_slab == NULL ? -ENOBUFS : 0; +} -struct dccp_rx_hist *dccp_rx_hist_new(const char *name) +void tfrc_tx_packet_history_exit(void) { - struct dccp_rx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC); - static const char dccp_rx_hist_mask[] = "rx_hist_%s"; - char *slab_name; - - if (hist == NULL) - goto out; - - slab_name = kmalloc(strlen(name) + sizeof(dccp_rx_hist_mask) - 1, - GFP_ATOMIC); - if (slab_name == NULL) - goto out_free_hist; - - sprintf(slab_name, dccp_rx_hist_mask, name); - hist->dccprxh_slab = kmem_cache_create(slab_name, - sizeof(struct dccp_rx_hist_entry), - 0, SLAB_HWCACHE_ALIGN, - NULL, NULL); - if (hist->dccprxh_slab == NULL) - goto out_free_slab_name; -out: - return hist; -out_free_slab_name: - kfree(slab_name); -out_free_hist: - kfree(hist); - hist = NULL; - goto out; + if (tfrc_tx_hist_slab != NULL) { + kmem_cache_destroy(tfrc_tx_hist_slab); + tfrc_tx_hist_slab = NULL; + } } -EXPORT_SYMBOL_GPL(dccp_rx_hist_new); +int tfrc_tx_hist_add(struct tfrc_tx_hist_entry **headp, u64 seqno) +{ + struct tfrc_tx_hist_entry *entry = kmem_cache_alloc(tfrc_tx_hist_slab, gfp_any()); + + if (entry == NULL) + return -ENOBUFS; + entry->seqno = seqno; + entry->stamp = ktime_get_real(); + entry->next = *headp; + *headp = entry; + return 0; +} -void dccp_rx_hist_delete(struct dccp_rx_hist *hist) +void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry **headp) { - const char* name = kmem_cache_name(hist->dccprxh_slab); + struct tfrc_tx_hist_entry *head = *headp; + + while (head != NULL) { + struct tfrc_tx_hist_entry *next = head->next; - kmem_cache_destroy(hist->dccprxh_slab); - kfree(name); - kfree(hist); + kmem_cache_free(tfrc_tx_hist_slab, head); + head = next; + } + + *headp = NULL; } -EXPORT_SYMBOL_GPL(dccp_rx_hist_delete); +/* + * Receiver History Routines + */ +static struct kmem_cache *tfrc_rx_hist_slab; -void dccp_rx_hist_purge(struct dccp_rx_hist *hist, struct list_head *list) +int __init tfrc_rx_packet_history_init(void) { - struct dccp_rx_hist_entry *entry, *next; + tfrc_rx_hist_slab = kmem_cache_create("tfrc_rxh_cache", + sizeof(struct tfrc_rx_hist_entry), + 0, SLAB_HWCACHE_ALIGN, NULL); + return tfrc_rx_hist_slab == NULL ? -ENOBUFS : 0; +} - list_for_each_entry_safe(entry, next, list, dccphrx_node) { - list_del_init(&entry->dccphrx_node); - kmem_cache_free(hist->dccprxh_slab, entry); +void tfrc_rx_packet_history_exit(void) +{ + if (tfrc_rx_hist_slab != NULL) { + kmem_cache_destroy(tfrc_rx_hist_slab); + tfrc_rx_hist_slab = NULL; } } -EXPORT_SYMBOL_GPL(dccp_rx_hist_purge); +static inline void tfrc_rx_hist_entry_from_skb(struct tfrc_rx_hist_entry *entry, + const struct sk_buff *skb, + const u64 ndp) +{ + const struct dccp_hdr *dh = dccp_hdr(skb); + + entry->tfrchrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq; + entry->tfrchrx_ccval = dh->dccph_ccval; + entry->tfrchrx_type = dh->dccph_type; + entry->tfrchrx_ndp = ndp; + entry->tfrchrx_tstamp = ktime_get_real(); +} -struct dccp_rx_hist_entry * - dccp_rx_hist_find_data_packet(const struct list_head *list) +void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, + const struct sk_buff *skb, + const u64 ndp) { - struct dccp_rx_hist_entry *entry, *packet = NULL; + struct tfrc_rx_hist_entry *entry = tfrc_rx_hist_last_rcv(h); - list_for_each_entry(entry, list, dccphrx_node) - if (entry->dccphrx_type == DCCP_PKT_DATA || - entry->dccphrx_type == DCCP_PKT_DATAACK) { - packet = entry; - break; - } + tfrc_rx_hist_entry_from_skb(entry, skb, ndp); +} - return packet; +/* has the packet contained in skb been seen before? */ +int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb) +{ + const u64 seq = DCCP_SKB_CB(skb)->dccpd_seq; + int i; + + if (dccp_delta_seqno(tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, seq) <= 0) + return 1; + + for (i = 1; i <= h->loss_count; i++) + if (tfrc_rx_hist_entry(h, i)->tfrchrx_seqno == seq) + return 1; + + return 0; } -EXPORT_SYMBOL_GPL(dccp_rx_hist_find_data_packet); +static void tfrc_rx_hist_swap(struct tfrc_rx_hist *h, const u8 a, const u8 b) +{ + const u8 idx_a = tfrc_rx_hist_index(h, a), + idx_b = tfrc_rx_hist_index(h, b); + struct tfrc_rx_hist_entry *tmp = h->ring[idx_a]; -void dccp_rx_hist_add_packet(struct dccp_rx_hist *hist, - struct list_head *rx_list, - struct list_head *li_list, - struct dccp_rx_hist_entry *packet, - u64 nonloss_seqno) + h->ring[idx_a] = h->ring[idx_b]; + h->ring[idx_b] = tmp; +} + +/* + * Private helper functions for loss detection. + * + * In the descriptions, `Si' refers to the sequence number of entry number i, + * whose NDP count is `Ni' (lower case is used for variables). + * Note: All __xxx_loss functions expect that a test against duplicates has been + * performed already: the seqno of the skb must not be less than the seqno + * of loss_prev; and it must not equal that of any valid history entry. + */ +static void __do_track_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u64 n1) { - struct dccp_rx_hist_entry *entry, *next; - u8 num_later = 0; - - list_add(&packet->dccphrx_node, rx_list); - - num_later = TFRC_RECV_NUM_LATE_LOSS + 1; - - if (!list_empty(li_list)) { - list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) { - if (num_later == 0) { - if (after48(nonloss_seqno, - entry->dccphrx_seqno)) { - list_del_init(&entry->dccphrx_node); - dccp_rx_hist_entry_delete(hist, entry); - } - } else if (dccp_rx_hist_entry_data_packet(entry)) - --num_later; - } - } else { - int step = 0; - u8 win_count = 0; /* Not needed, but lets shut up gcc */ - int tmp; + u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, + s1 = DCCP_SKB_CB(skb)->dccpd_seq; + + if (!dccp_loss_free(s0, s1, n1)) { /* gap between S0 and S1 */ + h->loss_count = 1; + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 1), skb, n1); + } +} + +static void __one_after_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u32 n2) +{ + u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, + s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno, + s2 = DCCP_SKB_CB(skb)->dccpd_seq; + + if (likely(dccp_delta_seqno(s1, s2) > 0)) { /* S1 < S2 */ + h->loss_count = 2; + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 2), skb, n2); + return; + } + + /* S0 < S2 < S1 */ + + if (dccp_loss_free(s0, s2, n2)) { + u64 n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp; + + if (dccp_loss_free(s2, s1, n1)) { + /* hole is filled: S0, S2, and S1 are consecutive */ + h->loss_count = 0; + h->loss_start = tfrc_rx_hist_index(h, 1); + } else + /* gap between S2 and S1: just update loss_prev */ + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h), skb, n2); + + } else { /* gap between S0 and S2 */ /* - * We have no loss interval history so we need at least one - * rtt:s of data packets to approximate rtt. + * Reorder history to insert S2 between S0 and S1 */ - list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) { - if (num_later == 0) { - switch (step) { - case 0: - step = 1; - /* OK, find next data packet */ - num_later = 1; - break; - case 1: - step = 2; - /* OK, find next data packet */ - num_later = 1; - win_count = entry->dccphrx_ccval; - break; - case 2: - tmp = win_count - entry->dccphrx_ccval; - if (tmp < 0) - tmp += TFRC_WIN_COUNT_LIMIT; - if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) { - /* - * We have found a packet older - * than one rtt remove the rest - */ - step = 3; - } else /* OK, find next data packet */ - num_later = 1; - break; - case 3: - list_del_init(&entry->dccphrx_node); - dccp_rx_hist_entry_delete(hist, entry); - break; - } - } else if (dccp_rx_hist_entry_data_packet(entry)) - --num_later; - } + tfrc_rx_hist_swap(h, 0, 3); + h->loss_start = tfrc_rx_hist_index(h, 3); + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 1), skb, n2); + h->loss_count = 2; } } -EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet); - -struct dccp_tx_hist *dccp_tx_hist_new(const char *name) +/* return 1 if a new loss event has been identified */ +static int __two_after_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u32 n3) { - struct dccp_tx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC); - static const char dccp_tx_hist_mask[] = "tx_hist_%s"; - char *slab_name; - - if (hist == NULL) - goto out; - - slab_name = kmalloc(strlen(name) + sizeof(dccp_tx_hist_mask) - 1, - GFP_ATOMIC); - if (slab_name == NULL) - goto out_free_hist; - - sprintf(slab_name, dccp_tx_hist_mask, name); - hist->dccptxh_slab = kmem_cache_create(slab_name, - sizeof(struct dccp_tx_hist_entry), - 0, SLAB_HWCACHE_ALIGN, - NULL, NULL); - if (hist->dccptxh_slab == NULL) - goto out_free_slab_name; -out: - return hist; -out_free_slab_name: - kfree(slab_name); -out_free_hist: - kfree(hist); - hist = NULL; - goto out; -} + u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, + s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno, + s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno, + s3 = DCCP_SKB_CB(skb)->dccpd_seq; + + if (likely(dccp_delta_seqno(s2, s3) > 0)) { /* S2 < S3 */ + h->loss_count = 3; + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 3), skb, n3); + return 1; + } -EXPORT_SYMBOL_GPL(dccp_tx_hist_new); + /* S3 < S2 */ -void dccp_tx_hist_delete(struct dccp_tx_hist *hist) -{ - const char* name = kmem_cache_name(hist->dccptxh_slab); + if (dccp_delta_seqno(s1, s3) > 0) { /* S1 < S3 < S2 */ + /* + * Reorder history to insert S3 between S1 and S2 + */ + tfrc_rx_hist_swap(h, 2, 3); + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 2), skb, n3); + h->loss_count = 3; + return 1; + } - kmem_cache_destroy(hist->dccptxh_slab); - kfree(name); - kfree(hist); -} + /* S0 < S3 < S1 */ -EXPORT_SYMBOL_GPL(dccp_tx_hist_delete); + if (dccp_loss_free(s0, s3, n3)) { + u64 n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp; -struct dccp_tx_hist_entry * - dccp_tx_hist_find_entry(const struct list_head *list, const u64 seq) -{ - struct dccp_tx_hist_entry *packet = NULL, *entry; + if (dccp_loss_free(s3, s1, n1)) { + /* hole between S0 and S1 filled by S3 */ + u64 n2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_ndp; + + if (dccp_loss_free(s1, s2, n2)) { + /* entire hole filled by S0, S3, S1, S2 */ + h->loss_start = tfrc_rx_hist_index(h, 2); + h->loss_count = 0; + } else { + /* gap remains between S1 and S2 */ + h->loss_start = tfrc_rx_hist_index(h, 1); + h->loss_count = 1; + } + + } else /* gap exists between S3 and S1, loss_count stays at 2 */ + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h), skb, n3); - list_for_each_entry(entry, list, dccphtx_node) - if (entry->dccphtx_seqno == seq) { - packet = entry; - break; + return 0; + } + + /* + * The remaining case: S0 < S3 < S1 < S2; gap between S0 and S3 + * Reorder history to insert S3 between S0 and S1. + */ + tfrc_rx_hist_swap(h, 0, 3); + h->loss_start = tfrc_rx_hist_index(h, 3); + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 1), skb, n3); + h->loss_count = 3; + + return 1; +} + +/* recycle RX history records to continue loss detection if necessary */ +static void __three_after_loss(struct tfrc_rx_hist *h) +{ + /* + * At this stage we know already that there is a gap between S0 and S1 + * (since S0 was the highest sequence number received before detecting + * the loss). To recycle the loss record, it is thus only necessary to + * check for other possible gaps between S1/S2 and between S2/S3. + */ + u64 s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno, + s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno, + s3 = tfrc_rx_hist_entry(h, 3)->tfrchrx_seqno; + u64 n2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_ndp, + n3 = tfrc_rx_hist_entry(h, 3)->tfrchrx_ndp; + + if (dccp_loss_free(s1, s2, n2)) { + + if (dccp_loss_free(s2, s3, n3)) { + /* no gap between S2 and S3: entire hole is filled */ + h->loss_start = tfrc_rx_hist_index(h, 3); + h->loss_count = 0; + } else { + /* gap between S2 and S3 */ + h->loss_start = tfrc_rx_hist_index(h, 2); + h->loss_count = 1; } - return packet; + } else { /* gap between S1 and S2 */ + h->loss_start = tfrc_rx_hist_index(h, 1); + h->loss_count = 2; + } } -EXPORT_SYMBOL_GPL(dccp_tx_hist_find_entry); +/** + * tfrc_rx_handle_loss - Loss detection and further processing + * @h: The non-empty RX history object + * @lh: Loss Intervals database to update + * @skb: Currently received packet + * @ndp: The NDP count belonging to @skb + * @calc_first_li: Caller-dependent computation of first loss interval in @lh + * @sk: Used by @calc_first_li (see tfrc_lh_interval_add) + * + * Chooses action according to pending loss, updates LI database when a new + * loss was detected, and does required post-processing. Returns 1 when caller + * should send feedback, 0 otherwise. + * Since it also takes care of reordering during loss detection and updates the + * records accordingly, the caller should not perform any more RX history + * operations when loss_count is greater than 0 after calling this function. + */ +int tfrc_rx_handle_loss(struct tfrc_rx_hist *h, + struct tfrc_loss_hist *lh, + struct sk_buff *skb, const u64 ndp, + u32 (*calc_first_li)(struct sock *), struct sock *sk) +{ + int is_new_loss = 0; + + if (h->loss_count == 0) { + __do_track_loss(h, skb, ndp); + } else if (h->loss_count == 1) { + __one_after_loss(h, skb, ndp); + } else if (h->loss_count != 2) { + DCCP_BUG("invalid loss_count %d", h->loss_count); + } else if (__two_after_loss(h, skb, ndp)) { + /* + * Update Loss Interval database and recycle RX records + */ + is_new_loss = tfrc_lh_interval_add(lh, h, calc_first_li, sk); + __three_after_loss(h); + } + return is_new_loss; +} -int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq, - u8 *ccval) +int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h) { - struct dccp_rx_hist_entry *packet = NULL, *entry; + int i; - list_for_each_entry(entry, list, dccphrx_node) - if (entry->dccphrx_seqno == seq) { - packet = entry; - break; - } + for (i = 0; i <= TFRC_NDUPACK; i++) { + h->ring[i] = kmem_cache_alloc(tfrc_rx_hist_slab, GFP_ATOMIC); + if (h->ring[i] == NULL) + goto out_free; + } - if (packet) - *ccval = packet->dccphrx_ccval; + h->loss_count = h->loss_start = 0; + return 0; - return packet != NULL; +out_free: + while (i-- != 0) { + kmem_cache_free(tfrc_rx_hist_slab, h->ring[i]); + h->ring[i] = NULL; + } + return -ENOBUFS; } -EXPORT_SYMBOL_GPL(dccp_rx_hist_find_entry); - -void dccp_tx_hist_purge_older(struct dccp_tx_hist *hist, - struct list_head *list, - struct dccp_tx_hist_entry *packet) +void tfrc_rx_hist_purge(struct tfrc_rx_hist *h) { - struct dccp_tx_hist_entry *next; + int i; - list_for_each_entry_safe_continue(packet, next, list, dccphtx_node) { - list_del_init(&packet->dccphtx_node); - dccp_tx_hist_entry_delete(hist, packet); - } + for (i = 0; i <= TFRC_NDUPACK; ++i) + if (h->ring[i] != NULL) { + kmem_cache_free(tfrc_rx_hist_slab, h->ring[i]); + h->ring[i] = NULL; + } +} + +/** + * tfrc_rx_hist_rtt_last_s - reference entry to compute RTT samples against + */ +static inline struct tfrc_rx_hist_entry * + tfrc_rx_hist_rtt_last_s(const struct tfrc_rx_hist *h) +{ + return h->ring[0]; } -EXPORT_SYMBOL_GPL(dccp_tx_hist_purge_older); +/** + * tfrc_rx_hist_rtt_prev_s - previously suitable (wrt rtt_last_s) RTT-sampling entry + */ +static inline struct tfrc_rx_hist_entry * + tfrc_rx_hist_rtt_prev_s(const struct tfrc_rx_hist *h) +{ + return h->ring[h->rtt_sample_prev]; +} -void dccp_tx_hist_purge(struct dccp_tx_hist *hist, struct list_head *list) +/** + * tfrc_rx_hist_sample_rtt - Sample RTT from timestamp / CCVal + * Based on ideas presented in RFC 4342, 8.1. Returns 0 if it was not able + * to compute a sample with given data - calling function should check this. + */ +u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb) { - struct dccp_tx_hist_entry *entry, *next; + u32 sample = 0, + delta_v = SUB16(dccp_hdr(skb)->dccph_ccval, + tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval); + + if (delta_v < 1 || delta_v > 4) { /* unsuitable CCVal delta */ + if (h->rtt_sample_prev == 2) { /* previous candidate stored */ + sample = SUB16(tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_ccval, + tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval); + if (sample) + sample = 4 / sample * + ktime_us_delta(tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_tstamp, + tfrc_rx_hist_rtt_last_s(h)->tfrchrx_tstamp); + else /* + * FIXME: This condition is in principle not + * possible but occurs when CCID is used for + * two-way data traffic. I have tried to trace + * it, but the cause does not seem to be here. + */ + DCCP_BUG("please report to dccp@vger.kernel.org" + " => prev = %u, last = %u", + tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_ccval, + tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval); + } else if (delta_v < 1) { + h->rtt_sample_prev = 1; + goto keep_ref_for_next_time; + } - list_for_each_entry_safe(entry, next, list, dccphtx_node) { - list_del_init(&entry->dccphtx_node); - dccp_tx_hist_entry_delete(hist, entry); + } else if (delta_v == 4) /* optimal match */ + sample = ktime_to_us(net_timedelta(tfrc_rx_hist_rtt_last_s(h)->tfrchrx_tstamp)); + else { /* suboptimal match */ + h->rtt_sample_prev = 2; + goto keep_ref_for_next_time; } -} -EXPORT_SYMBOL_GPL(dccp_tx_hist_purge); + if (unlikely(sample > DCCP_SANE_RTT_MAX)) { + DCCP_WARN("RTT sample %u too large, using max\n", sample); + sample = DCCP_SANE_RTT_MAX; + } -MODULE_AUTHOR("Ian McDonald <ian.mcdonald@jandi.co.nz>, " - "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>"); -MODULE_DESCRIPTION("DCCP TFRC library"); -MODULE_LICENSE("GPL"); + h->rtt_sample_prev = 0; /* use current entry as next reference */ +keep_ref_for_next_time: + + return sample; +} diff --git a/net/dccp/ccids/lib/packet_history.h b/net/dccp/ccids/lib/packet_history.h index 067cf1c85a3..ee362b0b630 100644 --- a/net/dccp/ccids/lib/packet_history.h +++ b/net/dccp/ccids/lib/packet_history.h @@ -1,10 +1,9 @@ /* - * net/dccp/packet_history.h + * Packet RX/TX history data structures and routines for TFRC-based protocols. * + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK * Copyright (c) 2005-6 The University of Waikato, Hamilton, New Zealand. * - * An implementation of the DCCP protocol - * * This code has been developed by the University of Waikato WAND * research group. For further information please see http://www.wand.net.nz/ * or e-mail Ian McDonald - ian.mcdonald@jandi.co.nz @@ -39,158 +38,118 @@ #include <linux/list.h> #include <linux/slab.h> -#include <linux/time.h> - -#include "../../dccp.h" - -/* Number of later packets received before one is considered lost */ -#define TFRC_RECV_NUM_LATE_LOSS 3 - -#define TFRC_WIN_COUNT_PER_RTT 4 -#define TFRC_WIN_COUNT_LIMIT 16 - -struct dccp_tx_hist_entry { - struct list_head dccphtx_node; - u64 dccphtx_seqno:48, - dccphtx_ccval:4, - dccphtx_sent:1; - u32 dccphtx_rtt; - struct timeval dccphtx_tstamp; -}; - -struct dccp_rx_hist_entry { - struct list_head dccphrx_node; - u64 dccphrx_seqno:48, - dccphrx_ccval:4, - dccphrx_type:4; - u32 dccphrx_ndp; /* In fact it is from 8 to 24 bits */ - struct timeval dccphrx_tstamp; -}; - -struct dccp_tx_hist { - kmem_cache_t *dccptxh_slab; -}; +#include "tfrc.h" -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; +/** + * tfrc_tx_hist_entry - Simple singly-linked TX history list + * @next: next oldest entry (LIFO order) + * @seqno: sequence number of this entry + * @stamp: send time of packet with sequence number @seqno + */ +struct tfrc_tx_hist_entry { + struct tfrc_tx_hist_entry *next; + u64 seqno; + ktime_t stamp; }; -extern struct dccp_rx_hist *dccp_rx_hist_new(const char *name); -extern void dccp_rx_hist_delete(struct dccp_rx_hist *hist); -extern struct dccp_rx_hist_entry * - dccp_rx_hist_find_data_packet(const struct list_head *list); - -static inline struct dccp_tx_hist_entry * - dccp_tx_hist_entry_new(struct dccp_tx_hist *hist, - const gfp_t prio) +static inline struct tfrc_tx_hist_entry * + tfrc_tx_hist_find_entry(struct tfrc_tx_hist_entry *head, u64 seqno) { - struct dccp_tx_hist_entry *entry = kmem_cache_alloc(hist->dccptxh_slab, - prio); - - if (entry != NULL) - entry->dccphtx_sent = 0; - - return entry; + while (head != NULL && head->seqno != seqno) + head = head->next; + return head; } -static inline void dccp_tx_hist_entry_delete(struct dccp_tx_hist *hist, - struct dccp_tx_hist_entry *entry) -{ - if (entry != NULL) - kmem_cache_free(hist->dccptxh_slab, entry); -} +int tfrc_tx_hist_add(struct tfrc_tx_hist_entry **headp, u64 seqno); +void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry **headp); -extern struct dccp_tx_hist_entry * - dccp_tx_hist_find_entry(const struct list_head *list, - const u64 seq); -extern int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq, - u8 *ccval); +/* Subtraction a-b modulo-16, respects circular wrap-around */ +#define SUB16(a, b) (((a) + 16 - (b)) & 0xF) -static inline void dccp_tx_hist_add_entry(struct list_head *list, - struct dccp_tx_hist_entry *entry) -{ - list_add(&entry->dccphtx_node, list); -} +/* Number of packets to wait after a missing packet (RFC 4342, 6.1) */ +#define TFRC_NDUPACK 3 -extern void dccp_tx_hist_purge_older(struct dccp_tx_hist *hist, - struct list_head *list, - struct dccp_tx_hist_entry *next); +/** + * tfrc_rx_hist_entry - Store information about a single received packet + * @tfrchrx_seqno: DCCP packet sequence number + * @tfrchrx_ccval: window counter value of packet (RFC 4342, 8.1) + * @tfrchrx_ndp: the NDP count (if any) of the packet + * @tfrchrx_tstamp: actual receive time of packet + */ +struct tfrc_rx_hist_entry { + u64 tfrchrx_seqno:48, + tfrchrx_ccval:4, + tfrchrx_type:4; + u64 tfrchrx_ndp:48; + ktime_t tfrchrx_tstamp; +}; -extern void dccp_tx_hist_purge(struct dccp_tx_hist *hist, - struct list_head *list); +/** + * tfrc_rx_hist - RX history structure for TFRC-based protocols + * @ring: Packet history for RTT sampling and loss detection + * @loss_count: Number of entries in circular history + * @loss_start: Movable index (for loss detection) + * @rtt_sample_prev: Used during RTT sampling, points to candidate entry + */ +struct tfrc_rx_hist { + struct tfrc_rx_hist_entry *ring[TFRC_NDUPACK + 1]; + u8 loss_count:2, + loss_start:2; +#define rtt_sample_prev loss_start +}; -static inline struct dccp_tx_hist_entry * - dccp_tx_hist_head(struct list_head *list) +/** + * tfrc_rx_hist_index - index to reach n-th entry after loss_start + */ +static inline u8 tfrc_rx_hist_index(const struct tfrc_rx_hist *h, const u8 n) { - struct dccp_tx_hist_entry *head = NULL; - - if (!list_empty(list)) - head = list_entry(list->next, struct dccp_tx_hist_entry, - dccphtx_node); - return head; + return (h->loss_start + n) & TFRC_NDUPACK; } -static inline struct dccp_rx_hist_entry * - dccp_rx_hist_entry_new(struct dccp_rx_hist *hist, - const struct sock *sk, - const u32 ndp, - const struct sk_buff *skb, - const gfp_t prio) +/** + * tfrc_rx_hist_last_rcv - entry with highest-received-seqno so far + */ +static inline struct tfrc_rx_hist_entry * + tfrc_rx_hist_last_rcv(const struct tfrc_rx_hist *h) { - struct dccp_rx_hist_entry *entry = kmem_cache_alloc(hist->dccprxh_slab, - prio); - - if (entry != NULL) { - const struct dccp_hdr *dh = dccp_hdr(skb); - - entry->dccphrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq; - entry->dccphrx_ccval = dh->dccph_ccval; - entry->dccphrx_type = dh->dccph_type; - entry->dccphrx_ndp = ndp; - dccp_timestamp(sk, &entry->dccphrx_tstamp); - } - - return entry; + return h->ring[tfrc_rx_hist_index(h, h->loss_count)]; } -static inline void dccp_rx_hist_entry_delete(struct dccp_rx_hist *hist, - struct dccp_rx_hist_entry *entry) +/** + * tfrc_rx_hist_entry - return the n-th history entry after loss_start + */ +static inline struct tfrc_rx_hist_entry * + tfrc_rx_hist_entry(const struct tfrc_rx_hist *h, const u8 n) { - if (entry != NULL) - kmem_cache_free(hist->dccprxh_slab, entry); + return h->ring[tfrc_rx_hist_index(h, n)]; } -extern void dccp_rx_hist_purge(struct dccp_rx_hist *hist, - struct list_head *list); - -static inline struct dccp_rx_hist_entry * - dccp_rx_hist_head(struct list_head *list) +/** + * tfrc_rx_hist_loss_prev - entry with highest-received-seqno before loss was detected + */ +static inline struct tfrc_rx_hist_entry * + tfrc_rx_hist_loss_prev(const struct tfrc_rx_hist *h) { - struct dccp_rx_hist_entry *head = NULL; - - if (!list_empty(list)) - head = list_entry(list->next, struct dccp_rx_hist_entry, - dccphrx_node); - return head; + return h->ring[h->loss_start]; } -static inline int - dccp_rx_hist_entry_data_packet(const struct dccp_rx_hist_entry *entry) +/* indicate whether previously a packet was detected missing */ +static inline bool tfrc_rx_hist_loss_pending(const struct tfrc_rx_hist *h) { - return entry->dccphrx_type == DCCP_PKT_DATA || - entry->dccphrx_type == DCCP_PKT_DATAACK; + return h->loss_count > 0; } -extern void dccp_rx_hist_add_packet(struct dccp_rx_hist *hist, - struct list_head *rx_list, - struct list_head *li_list, - struct dccp_rx_hist_entry *packet, - u64 nonloss_seqno); +void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, const struct sk_buff *skb, + const u64 ndp); + +int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb); -extern u64 dccp_rx_hist_detect_loss(struct list_head *rx_list, - struct list_head *li_list, u8 *win_loss); +struct tfrc_loss_hist; +int tfrc_rx_handle_loss(struct tfrc_rx_hist *h, struct tfrc_loss_hist *lh, + struct sk_buff *skb, const u64 ndp, + u32 (*first_li)(struct sock *sk), struct sock *sk); +u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb); +int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h); +void tfrc_rx_hist_purge(struct tfrc_rx_hist *h); #endif /* _DCCP_PKT_HIST_ */ diff --git a/net/dccp/ccids/lib/tfrc.c b/net/dccp/ccids/lib/tfrc.c new file mode 100644 index 00000000000..62b5828acde --- /dev/null +++ b/net/dccp/ccids/lib/tfrc.c @@ -0,0 +1,45 @@ +/* + * TFRC library initialisation + * + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK + * Copyright (c) 2007 Arnaldo Carvalho de Melo <acme@redhat.com> + */ +#include <linux/moduleparam.h> +#include "tfrc.h" + +#ifdef CONFIG_IP_DCCP_TFRC_DEBUG +bool tfrc_debug; +module_param(tfrc_debug, bool, 0644); +MODULE_PARM_DESC(tfrc_debug, "Enable TFRC debug messages"); +#endif + +int __init tfrc_lib_init(void) +{ + int rc = tfrc_li_init(); + + if (rc) + goto out; + + rc = tfrc_tx_packet_history_init(); + if (rc) + goto out_free_loss_intervals; + + rc = tfrc_rx_packet_history_init(); + if (rc) + goto out_free_tx_history; + return 0; + +out_free_tx_history: + tfrc_tx_packet_history_exit(); +out_free_loss_intervals: + tfrc_li_exit(); +out: + return rc; +} + +void tfrc_lib_exit(void) +{ + tfrc_rx_packet_history_exit(); + tfrc_tx_packet_history_exit(); + tfrc_li_exit(); +} diff --git a/net/dccp/ccids/lib/tfrc.h b/net/dccp/ccids/lib/tfrc.h index 45f30f59ea2..40ee7d62b65 100644 --- a/net/dccp/ccids/lib/tfrc.h +++ b/net/dccp/ccids/lib/tfrc.h @@ -1,22 +1,77 @@ #ifndef _TFRC_H_ #define _TFRC_H_ /* - * net/dccp/ccids/lib/tfrc.h - * - * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand. - * Copyright (c) 2005 Ian McDonald <ian.mcdonald@jandi.co.nz> - * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br> - * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK + * Copyright (c) 2005-6 The University of Waikato, Hamilton, New Zealand. + * Copyright (c) 2005-6 Ian McDonald <ian.mcdonald@jandi.co.nz> + * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br> + * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon * * This program 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 of the License, or * (at your option) any later version. */ - #include <linux/types.h> +#include <linux/math64.h> +#include "../../dccp.h" + +/* internal includes that this library exports: */ +#include "loss_interval.h" +#include "packet_history.h" + +#ifdef CONFIG_IP_DCCP_TFRC_DEBUG +extern bool tfrc_debug; +#define tfrc_pr_debug(format, a...) DCCP_PR_DEBUG(tfrc_debug, format, ##a) +#else +#define tfrc_pr_debug(format, a...) +#endif + +/* integer-arithmetic divisions of type (a * 1000000)/b */ +static inline u64 scaled_div(u64 a, u64 b) +{ + BUG_ON(b == 0); + return div64_u64(a * 1000000, b); +} + +static inline u32 scaled_div32(u64 a, u64 b) +{ + u64 result = scaled_div(a, b); + + if (result > UINT_MAX) { + DCCP_CRIT("Overflow: %llu/%llu > UINT_MAX", + (unsigned long long)a, (unsigned long long)b); + return UINT_MAX; + } + return result; +} + +/** + * tfrc_ewma - Exponentially weighted moving average + * @weight: Weight to be used as damping factor, in units of 1/10 + */ +static inline u32 tfrc_ewma(const u32 avg, const u32 newval, const u8 weight) +{ + return avg ? (weight * avg + (10 - weight) * newval) / 10 : newval; +} + +u32 tfrc_calc_x(u16 s, u32 R, u32 p); +u32 tfrc_calc_x_reverse_lookup(u32 fvalue); +u32 tfrc_invert_loss_event_rate(u32 loss_event_rate); + +int tfrc_tx_packet_history_init(void); +void tfrc_tx_packet_history_exit(void); +int tfrc_rx_packet_history_init(void); +void tfrc_rx_packet_history_exit(void); -extern u32 tfrc_calc_x(u16 s, u32 R, u32 p); -extern u32 tfrc_calc_x_reverse_lookup(u32 fvalue); +int tfrc_li_init(void); +void tfrc_li_exit(void); +#ifdef CONFIG_IP_DCCP_TFRC_LIB +int tfrc_lib_init(void); +void tfrc_lib_exit(void); +#else +#define tfrc_lib_init() (0) +#define tfrc_lib_exit() +#endif #endif /* _TFRC_H_ */ diff --git a/net/dccp/ccids/lib/tfrc_equation.c b/net/dccp/ccids/lib/tfrc_equation.c index 44076e0c659..88ef98285be 100644 --- a/net/dccp/ccids/lib/tfrc_equation.c +++ b/net/dccp/ccids/lib/tfrc_equation.c @@ -1,6 +1,4 @@ /* - * net/dccp/ccids/lib/tfrc_equation.c - * * Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand. * Copyright (c) 2005 Ian McDonald <ian.mcdonald@jandi.co.nz> * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br> @@ -13,16 +11,83 @@ */ #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,117 +591,115 @@ 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). + */ u32 tfrc_calc_x(u16 s, u32 R, u32 p) { - int index; + u16 index; u32 f; - u64 tmp1, tmp2; + u64 result; + + /* 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 (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 (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; - - if (index < 0) - /* p should be 0 unless there is a bug in my code */ - index = 0; - - if (R == 0) - R = 1; /* RTT can't be zero or else divide by zero */ - - BUG_ON(index >= TFRC_CALC_X_ARRSIZE); - - if (p >= TFRC_CALC_X_SPLIT) - f = tfrc_calc_x_lookup[index][0]; - else f = tfrc_calc_x_lookup[index][1]; - 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 */ + } else { /* 0.05 < p <= 1.00 */ + index = p/(1000000/TFRC_CALC_X_ARRSIZE) - 1; - return (u32)tmp1; + f = tfrc_calc_x_lookup[index][0]; + } + + /* + * Compute 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. To avoid overflow, the result is computed in two stages. + * This works under almost all reasonable operational conditions, for a + * wide range of parameters. Yet, should some strange combination of + * parameters result in overflow, the use of scaled_div32 will catch + * this and return UINT_MAX - which is a logically adequate consequence. + */ + result = scaled_div(s, R); + return scaled_div32(result, f); } -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) + * @fvalue: function value to match, scaled by 1000000 * - * both fvalue and p are multiplied by 1,000,000 to use ints + * 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 %u smaller than resolution\n", fvalue); + return TFRC_SMALLEST_P; + } + if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0]) { + DCCP_WARN("fvalue %u exceeds bounds!\n", fvalue); return 1000000; - else - small = 0; + } - while (fvalue > tfrc_calc_x_lookup[ctr][small]) - ctr++; + 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; + } - if (small) - return TFRC_CALC_X_SPLIT * ctr / TFRC_CALC_X_ARRSIZE; - else - return 1000000 * ctr / 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); +/** + * tfrc_invert_loss_event_rate - Compute p so that 10^6 corresponds to 100% + * When @loss_event_rate is large, there is a chance that p is truncated to 0. + * To avoid re-entering slow-start in that case, we set p = TFRC_SMALLEST_P > 0. + */ +u32 tfrc_invert_loss_event_rate(u32 loss_event_rate) +{ + if (loss_event_rate == UINT_MAX) /* see RFC 4342, 8.5 */ + return 0; + if (unlikely(loss_event_rate == 0)) /* map 1/0 into 100% */ + return 1000000; + return max_t(u32, scaled_div(1, loss_event_rate), TFRC_SMALLEST_P); +} |