Guys,
I can't follow this code 100%, but here is an analysis of
what I can
understand. Summary: Ian is correct (I think).
From Ian's patch, it appears that the OLD code DID NOT
include the most
recent loss interval (i.e., the incomplete loss interval,
the one that has no
losses) in its calculation of i_tot1. Ian has added the
following line to do
this:
> + i_tot1 += non_loss * dccp_li_hist_w[0];
This is correct. The RFC requires that one of the i_tots
include the
incomplete loss interval. So this part of the patch is
required for RFC
compliance.
I am assuming however that the incomplete loss interval is
NOT included in the
'hcrx->ccid3hcrx_li_hist' list. If that list DOES
include the incomplete loss
interval, then the code would need to be different.
I don't quite get why one needs
dccp_li_hist_recalc_recalcloss. One could do
probably do that simpler, and maybe Ian can explain his
reasoning. Why is it
necessary at all? But RFC3448 does require that one use the
incomplete loss
interval in the i_tot calculations.
One nit. If you are following RFC terminology i_tot0 should
include non_loss,
but in the code i_tot1 does. The code seems correct except
for the switching
of i_tot0 and i_tot1.
Eddie
Ian McDonald wrote:
> This works out when to recalculate the loss rate due to
significant
> non-loss interval. We do this at time of recalulating
loss rate to save
> having to do it every packet. Instead we just check if
it's time to
> recalculate. It looked like there was an early attempt
to do this but it
> was quite wrong in its implementation.
>
> This is making the code conform to RFC 3448, section
5.4
>
> I've added some extra debugging which is useful in
testing as well. In
> loss_interval.c I've just used dccp_pr_debug. I tried
to use ccid3_pr_debug
> but ran into problems with circular references.
>
> This patch applies on top of Gerrit's patches.
>
> If possible I'd like this to go into 2.6.21 as it's
been reported broken by
> about 4 or 5 people.
>
> Signed-off-by: Ian McDonald <ian.mcdonald jandi.co.nz>
> ---
> diff --git a/net/dccp/ccids/ccid3.c
b/net/dccp/ccids/ccid3.c
> index e7eeeeb..a74f905 100644
> --- a/net/dccp/ccids/ccid3.c
> +++ b/net/dccp/ccids/ccid3.c
> -36,9 +36,9
> #include "../ccid.h"
> #include "../dccp.h"
> #include "lib/packet_history.h"
> -#include "lib/loss_interval.h"
> #include "lib/tfrc.h"
> #include "ccid3.h"
> +#include "lib/loss_interval.h"
>
> static struct dccp_tx_hist *ccid3_tx_hist;
> static struct dccp_rx_hist *ccid3_rx_hist;
> -384,6 +384,9 static void
ccid3_hc_tx_packet_sent(struct sock *sk, int more,
> packet->dccphtx_rtt = hctx->ccid3hctx_rtt;
> packet->dccphtx_sent = 1;
> hctx->ccid3hctx_idle = 0;
> +
> + ccid3_pr_debug("seqno = %llu, rtt = %un",
> + (long long unsigned)packet->dccphtx_seqno,
packet->dccphtx_rtt);
> }
>
> static void ccid3_hc_tx_packet_recv(struct sock *sk,
struct sk_buff *skb)
> -810,7 +813,7 static int
ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff
*skb)
> *
> * returns estimated loss interval in usecs */
>
> -static u32 ccid3_hc_rx_calc_first_li(struct sock *sk)
> +static u32 ccid3_hc_rx_calc_first_li(struct sock *sk,
struct sk_buff *skb)
> {
> struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
> struct dccp_rx_hist_entry *entry, *next, *tail =
NULL;
> -901,13 +904,31 found:
> ccid3_pr_debug("%s(%p), receive rate=%u bytes/s,
implied "
> "loss rate=%un", dccp_role(sk),
sk, x_recv, p);
>
> - if (p == 0)
> + if (p == 0) {
> + DCCP_WARN("p==0, fval = %llun", fval);
> return ~0;
> - else
> - return 1000000 / p;
> + } else {
> + u32 new_interval = 1000000 / p;
> + u64 recalc_interval;
> +
> + if (new_interval < 150)
> + recalc_interval = new_interval + 1;
> + else
> + recalc_interval = (new_interval *
> + (DCCP_RECALC_LOSS_FACTOR+1)) /
DCCP_RECALC_LOSS_FACTOR;
> + hcrx->ccid3hcrx_seq_recalc_loss =
dccp_hdr_seq(skb);
> + add48(&hcrx->ccid3hcrx_seq_recalc_loss,
recalc_interval);
> + ccid3_pr_debug("%s(%p), interval=%u,
recalc_interval=%llu, "
> + "seqno=%llu recalc_loss=%llun",
dccp_role(sk), sk,
> + new_interval, recalc_interval, dccp_hdr_seq(skb),
> + hcrx->ccid3hcrx_seq_recalc_loss);
> +
> + return new_interval;
> + }
> }
>
> -static void ccid3_hc_rx_update_li(struct sock *sk, u64
seq_loss, u8 win_loss)
> +static void ccid3_hc_rx_update_li(struct sock *sk,
struct sk_buff *skb,
> + u64 seq_loss, u8
win_loss)
> {
> struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
> struct dccp_li_hist_entry *head;
> -920,7 +941,7 static void ccid3_hc_rx_update_li(struct
sock *sk, u64 seq_loss, u8 win_loss)
>
> 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);
> + head->dccplih_interval =
ccid3_hc_rx_calc_first_li(sk, skb);
> } else {
> struct dccp_li_hist_entry *entry;
> struct list_head *tail;
> -951,10 +972,12 static void
ccid3_hc_rx_update_li(struct sock *sk, u64 seq_loss, u8
win_loss)
> entry->dccplih_seqno = seq_loss;
> entry->dccplih_interval = seq_temp;
> entry->dccplih_win_count = win_loss;
> + ccid3_pr_debug("adding node seqno=%llu,
interval=%un",
> + (u64)entry->dccplih_seqno,
entry->dccplih_interval);
> }
> }
>
> -static int ccid3_hc_rx_detect_loss(struct sock *sk,
> +static int ccid3_hc_rx_detect_loss(struct sock *sk,
struct sk_buff *skb,
> struct
dccp_rx_hist_entry *packet)
> {
> struct ccid3_hc_rx_sock *hcrx = ccid3_hc_rx_sk(sk);
> -979,7 +1002,7 static int ccid3_hc_rx_detect_loss(struct
sock *sk,
> 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,
> + ccid3_hc_rx_update_li(sk, skb,
hcrx->ccid3hcrx_seqno_nonloss,
> hcrx->ccid3hcrx_ccval_nonloss);
> tmp_seqno = hcrx->ccid3hcrx_seqno_nonloss;
> dccp_inc_seqno(&tmp_seqno);
> -1067,7 +1090,7 static void
ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff
*skb)
> return;
> }
>
> - loss = ccid3_hc_rx_detect_loss(sk, packet);
> + loss = ccid3_hc_rx_detect_loss(sk, skb, packet);
>
> if (DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK)
> return;
> -1088,6 +1111,15 static void
ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff
*skb)
> if (loss)
> break;
>
> + if (hcrx->ccid3hcrx_seq_recalc_loss &&
> + after48(dccp_hdr_seq(skb),
hcrx->ccid3hcrx_seq_recalc_loss)) {
> + ccid3_pr_debug("%s(%p, state=%s) checking loss
"
> + "recalc skb=%llu, recalc_loss =
%llun",
> + dccp_role(sk), sk,
dccp_state_name(sk->sk_state),
> +
dccp_hdr_seq(skb),hcrx->ccid3hcrx_seq_recalc_loss);
> + break;
> + }
> +
> dccp_timestamp(sk, &now);
> if ((timeval_delta(&now,
&hcrx->ccid3hcrx_tstamp_last_ack) -
> (suseconds_t)hcrx->ccid3hcrx_rtt) >= 0) {
> -1100,15 +1132,16 static void
ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff
*skb)
> return;
> }
>
> - /* Dealing with packet loss */
> - ccid3_pr_debug("%s(%p, state=%s), data loss!
Reacting...n",
> + /* Dealing with loss intervals*/
> + if (loss)
> + ccid3_pr_debug("%s(%p, state=%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);
> + u32 i_mean = dccp_li_hist_calc_i_mean(hcrx, skb);
>
> /* Scaling up by 1000000 as fixed decimal */
> if (i_mean != 0)
> -1116,7 +1149,9 static void
ccid3_hc_rx_packet_recv(struct sock *sk, struct sk_buff
*skb)
> } else
> DCCP_BUG("empty loss history");
>
> - if (hcrx->ccid3hcrx_p > p_prev) {
> + if (hcrx->ccid3hcrx_p != p_prev) {
> + ccid3_pr_debug("p_prev = %u, hcrx_p =
%un", p_prev,
> + hcrx->ccid3hcrx_p);
> ccid3_hc_rx_send_feedback(sk);
> return;
> }
> -1135,6 +1170,7 static int
ccid3_hc_rx_init(struct ccid *ccid, struct sock *sk)
> hcrx->ccid3hcrx_tstamp_last_feedback =
hcrx->ccid3hcrx_tstamp_last_ack;
> hcrx->ccid3hcrx_s = 0;
> hcrx->ccid3hcrx_rtt = 0;
> + hcrx->ccid3hcrx_seqno_nonloss = 0;
> return 0;
> }
>
> diff --git a/net/dccp/ccids/ccid3.h
b/net/dccp/ccids/ccid3.h
> index 2b18db4..99182bf 100644
> --- a/net/dccp/ccids/ccid3.h
> +++ b/net/dccp/ccids/ccid3.h
> -158,6 +158,7 enum ccid3_hc_rx_states {
> * ccid3hcrx_s - Received packet size in bytes
> * ccid3hcrx_pinv - Inverse of Loss Event Rate (RFC
4342, sec. 8.5)
> * ccid3hcrx_elapsed_time - Time since packet
reception
> + * ccid3hcrx_seq_recalc_loss - recalc loss due to
nonloss (RFC 3448, 5.4)
> */
> struct ccid3_hc_rx_sock {
> struct tfrc_rx_info ccid3hcrx_tfrc;
> -176,6 +177,7 struct ccid3_hc_rx_sock {
> u16 ccid3hcrx_s;
> u32 ccid3hcrx_pinv;
> u32 ccid3hcrx_elapsed_time;
> + u64 ccid3hcrx_seq_recalc_loss;
> };
>
> static inline struct ccid3_hc_tx_sock
*ccid3_hc_tx_sk(const struct sock *sk)
> diff --git a/net/dccp/ccids/lib/loss_interval.c
b/net/dccp/ccids/lib/loss_interval.c
> index 372d7e7..cd03ae0 100644
> --- a/net/dccp/ccids/lib/loss_interval.c
> +++ b/net/dccp/ccids/lib/loss_interval.c
> -14,6 +14,7
> #include <linux/module.h>
> #include <net/sock.h>
> #include "../../dccp.h"
> +#include "../ccid3.h"
> #include "loss_interval.h"
>
> struct dccp_li_hist *dccp_li_hist_new(const char
*name)
> -81,31 +82,106 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)
> +/* This code implements the part of section 5.4 of
RFC3448 which says we should
> + * recalculate the average loss interval if we have a
sufficient long loss
> + * interval.
> + *
> + * Given that i_mean = weighted average of loss then
we can say that
> + * 4*n + 4*i[0] + 4*i[1] + 4*i[2] + 3*i[3] + 2*i[4] +
i[5] + i[6] =
> + * y*(4*i[0] + 4*i[i] + 4*i[2] + 4*i[3] + 3*i[4]+
2*i[5] + i[6] + i[7])
> + *
> + * where y is a factor so that we don't check as soon
as we hit average
> + * interval and waste CPU cycles needlessly. n is the
non-loss interval
> + * and i[x] are the loss intervals. We don't need to
divide by the sum
> + * of the weighting as these cancel out on each side.
> + *
> + * We can solve for this equation for n which yields:
> + * n =
> + * ((4*i[0] + 4*i[1] + 4*i[2] + 4*i[3] + 3*i[4]+
2*i[5] + i[6] + i[7])/4) -
> + * (y*(4*i[0] + 4*i[1] + 4*i[2] + 3*i[3] + 2*i[4] +
i[5] + i[6])/4) */
> +
> +static u64 dccp_li_hist_recalc_recalcloss(struct
sk_buff *skb,
> + u32 i_tot0,
u32 i_tot1)
> +{
> + u64 recalcloss_seq = dccp_hdr_seq(skb);
> +
> + dccp_pr_debug("recalcloss_seq=%llun",
recalcloss_seq);
> +
> + if (!i_tot0) {
> + DCCP_WARN("i_tot0 == 0n");
> + return 0;
> + }
> +
> + /* We don't adjust if > 1 million as will get
overflow
> + * in calculations and not so serious anyway */
> + if (i_tot0 > 1000000) {
> + DCCP_WARN("i_mean > 100000n");
> + return 0;
> + }
> +
> + i_tot0 /= 4;
> + i_tot1 = (i_tot1 * (DCCP_RECALC_LOSS_FACTOR+1))/
> + (DCCP_RECALC_LOSS_FACTOR*4);
> +
> + if (i_tot1 >= i_tot0) {
> + dccp_pr_debug("only incrementing by 1n");
> + add48(&recalcloss_seq, 1);
> + } else
> + add48(&recalcloss_seq,(u64)(i_tot0 - i_tot1));
> +
> + dccp_pr_debug("recalcloss_seq=%llu, i_tot0=%u,
i_tot1=%un",
> + recalcloss_seq, i_tot0, i_tot1);
> +
> + return recalcloss_seq;
> +}
> +
> +u32 dccp_li_hist_calc_i_mean(struct ccid3_hc_rx_sock
*hcrx, struct sk_buff *skb)
> {
> struct dccp_li_hist_entry *li_entry, *li_next;
> - int i = 0;
> + unsigned int i = 0;
> u32 i_tot;
> u32 i_tot0 = 0;
> u32 i_tot1 = 0;
> u32 w_tot = 0;
> + u64 non_loss = 0;
> + u32 i_mean;
> + struct list_head *list =
&hcrx->ccid3hcrx_li_hist;
>
> list_for_each_entry_safe(li_entry, li_next, list,
dccplih_node) {
> if (li_entry->dccplih_interval != ~0U) {
> 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];
> - }
> -
> + if (i != 7)
> + i_tot1 += li_entry->dccplih_interval
> + * dccp_li_hist_w[i + 1];
> + if (i == 0) {
> + non_loss = dccp_hdr_seq(skb);
> + sub48(&non_loss, li_entry->dccplih_seqno);
> + }
> + dccp_pr_debug("i=%d, interval=%u, seqno=%llu,
"
> + "i_tot0=%u, i_tot1=%u, w_tot=%un", i,
> + li_entry->dccplih_interval,
> + (u64)li_entry->dccplih_seqno,i_tot0, i_tot1,
w_tot);
> + } else
> + dccp_pr_debug("empty loss intervaln");
>
> if (++i > DCCP_LI_HIST_IVAL_F_LENGTH)
> break;
> }
>
> - if (i != DCCP_LI_HIST_IVAL_F_LENGTH)
> + if (i != DCCP_LI_HIST_IVAL_F_LENGTH) {
> + DCCP_BUG("Length of loss interval list is
%un", i);
> return 0;
> + }
>
> + hcrx->ccid3hcrx_seq_recalc_loss =
> + dccp_li_hist_recalc_recalcloss(skb, i_tot0,
i_tot1);
> +
> + i_tot1 += non_loss * dccp_li_hist_w[0];
> + if (i_tot1 > i_tot0)
> + dccp_pr_debug("i_mean recalculateed due to high
nonloss "
> + " interval seqno=%llu nonloss=%llu
i_tot0=%u, i_tot1=%un",
> + dccp_hdr_seq(skb), non_loss, i_tot0, i_tot1);
> i_tot = max(i_tot0, i_tot1);
>
> if (!w_tot) {
> -113,7 +189,10 u32 dccp_li_hist_calc_i_mean(struct
list_head *list)
> return 1;
> }
>
> - return i_tot / w_tot;
> + i_mean = i_tot / w_tot;
> + dccp_pr_debug("i_mean=%un", i_mean);
> +
> + return i_mean;
> }
>
> EXPORT_SYMBOL_GPL(dccp_li_hist_calc_i_mean);
> -131,7 +210,7 int dccp_li_hist_interval_new(struct
dccp_li_hist *hist,
> DCCP_BUG("loss interval list entry is
NULL");
> return 0;
> }
> - entry->dccplih_interval = ~0;
> + entry->dccplih_interval = ~0U;
> list_add(&entry->dccplih_node, list);
> }
>
> diff --git a/net/dccp/ccids/lib/loss_interval.h
b/net/dccp/ccids/lib/loss_interval.h
> index eb25701..6fed81b 100644
> --- a/net/dccp/ccids/lib/loss_interval.h
> +++ b/net/dccp/ccids/lib/loss_interval.h
> -50,7 +50,8 static inline void
dccp_li_hist_entry_delete(struct dccp_li_hist *hist,
> extern void dccp_li_hist_purge(struct dccp_li_hist
*hist,
> struct list_head *list);
>
> -extern u32 dccp_li_hist_calc_i_mean(struct list_head
*list);
> +extern u32 dccp_li_hist_calc_i_mean(struct
ccid3_hc_rx_sock *hcrx,
> + struct sk_buff *skb);
>
> extern int dccp_li_hist_interval_new(struct
dccp_li_hist *hist,
> struct list_head *list, const u64 seq_loss, const
u8 win_loss);
> diff --git a/net/dccp/dccp.h b/net/dccp/dccp.h
> index dd0a986..546ca70 100644
> --- a/net/dccp/dccp.h
> +++ b/net/dccp/dccp.h
> -80,6 +80,11 extern void dccp_time_wait(struct sock
*sk, int state, int timeo);
>
> #define DCCP_RTO_MAX ((unsigned)(120 * HZ)) /* FIXME:
using TCP value */
>
> +/* Value as a reciprocal to check for change in loss
through long
> + * non-loss intervals. If you change this you must
recheck existing
> + * code for overflow possibilities */
> +#define DCCP_RECALC_LOSS_FACTOR 100
> +
> /* sysctl variables for DCCP */
> extern int sysctl_dccp_request_retries;
> extern int sysctl_dccp_retries1;
> -
> To unsubscribe from this list: send the line
"unsubscribe dccp" in
> the body of a message to majordomovger.kernel.org
> More majordomo info at http://vge
r.kernel.org/majordomo-info.html
|