diff options
Diffstat (limited to 'net/dccp')
| -rw-r--r-- | net/dccp/Kconfig | 1 | ||||
| -rw-r--r-- | net/dccp/ackvec.c | 163 | ||||
| -rw-r--r-- | net/dccp/ackvec.h | 62 | ||||
| -rw-r--r-- | net/dccp/ccid.c | 8 | ||||
| -rw-r--r-- | net/dccp/ccid.h | 37 | ||||
| -rw-r--r-- | net/dccp/ccids/Kconfig | 30 | ||||
| -rw-r--r-- | net/dccp/ccids/ccid2.c | 228 | ||||
| -rw-r--r-- | net/dccp/ccids/ccid2.h | 21 | ||||
| -rw-r--r-- | net/dccp/ccids/ccid3.c | 710 | ||||
| -rw-r--r-- | net/dccp/ccids/ccid3.h | 41 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/Makefile | 2 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/loss_interval.c | 352 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/loss_interval.h | 64 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/packet_history.c | 599 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/packet_history.h | 220 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/tfrc.c | 63 | ||||
| -rw-r--r-- | net/dccp/ccids/lib/tfrc.h | 29 | ||||
| -rw-r--r-- | net/dccp/dccp.h | 35 | ||||
| -rw-r--r-- | net/dccp/feat.c | 29 | ||||
| -rw-r--r-- | net/dccp/feat.h | 26 | ||||
| -rw-r--r-- | net/dccp/input.c | 155 | ||||
| -rw-r--r-- | net/dccp/ipv4.c | 12 | ||||
| -rw-r--r-- | net/dccp/ipv6.c | 10 | ||||
| -rw-r--r-- | net/dccp/minisocks.c | 33 | ||||
| -rw-r--r-- | net/dccp/options.c | 139 | ||||
| -rw-r--r-- | net/dccp/output.c | 55 | ||||
| -rw-r--r-- | net/dccp/proto.c | 194 | ||||
| -rw-r--r-- | net/dccp/sysctl.c | 36 | ||||
| -rw-r--r-- | net/dccp/timer.c | 5 |
29 files changed, 1777 insertions, 1582 deletions
diff --git a/net/dccp/Kconfig b/net/dccp/Kconfig index 0549e4719b13..7aa2a7acc7ec 100644 --- a/net/dccp/Kconfig +++ b/net/dccp/Kconfig @@ -1,6 +1,7 @@ menuconfig IP_DCCP tristate "The DCCP Protocol (EXPERIMENTAL)" depends on INET && EXPERIMENTAL + select IP_DCCP_CCID2 ---help--- Datagram Congestion Control Protocol (RFC 4340) diff --git a/net/dccp/ackvec.c b/net/dccp/ackvec.c index 83378f379f72..6de4bd195d28 100644 --- a/net/dccp/ackvec.c +++ b/net/dccp/ackvec.c @@ -30,7 +30,7 @@ static struct dccp_ackvec_record *dccp_ackvec_record_new(void) kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC); if (avr != NULL) - INIT_LIST_HEAD(&avr->dccpavr_node); + INIT_LIST_HEAD(&avr->avr_node); return avr; } @@ -40,7 +40,7 @@ static void dccp_ackvec_record_delete(struct dccp_ackvec_record *avr) if (unlikely(avr == NULL)) return; /* Check if deleting a linked record */ - WARN_ON(!list_empty(&avr->dccpavr_node)); + WARN_ON(!list_empty(&avr->avr_node)); kmem_cache_free(dccp_ackvec_record_slab, avr); } @@ -52,16 +52,15 @@ static void dccp_ackvec_insert_avr(struct dccp_ackvec *av, * just add the AVR at the head of the list. * -sorbo. */ - if (!list_empty(&av->dccpav_records)) { + if (!list_empty(&av->av_records)) { const struct dccp_ackvec_record *head = - list_entry(av->dccpav_records.next, + list_entry(av->av_records.next, struct dccp_ackvec_record, - dccpavr_node); - BUG_ON(before48(avr->dccpavr_ack_seqno, - head->dccpavr_ack_seqno)); + avr_node); + BUG_ON(before48(avr->avr_ack_seqno, head->avr_ack_seqno)); } - list_add(&avr->dccpavr_node, &av->dccpav_records); + list_add(&avr->avr_node, &av->av_records); } int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) @@ -69,9 +68,8 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) struct dccp_sock *dp = dccp_sk(sk); struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec; /* Figure out how many options do we need to represent the ackvec */ - const u16 nr_opts = DIV_ROUND_UP(av->dccpav_vec_len, - DCCP_MAX_ACKVEC_OPT_LEN); - u16 len = av->dccpav_vec_len + 2 * nr_opts, i; + const u16 nr_opts = DIV_ROUND_UP(av->av_vec_len, DCCP_MAX_ACKVEC_OPT_LEN); + u16 len = av->av_vec_len + 2 * nr_opts, i; u32 elapsed_time; const unsigned char *tail, *from; unsigned char *to; @@ -81,7 +79,7 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN) return -1; - delta = ktime_us_delta(ktime_get_real(), av->dccpav_time); + delta = ktime_us_delta(ktime_get_real(), av->av_time); elapsed_time = delta / 10; if (elapsed_time != 0 && @@ -95,9 +93,9 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) DCCP_SKB_CB(skb)->dccpd_opt_len += len; to = skb_push(skb, len); - len = av->dccpav_vec_len; - from = av->dccpav_buf + av->dccpav_buf_head; - tail = av->dccpav_buf + DCCP_MAX_ACKVEC_LEN; + len = av->av_vec_len; + from = av->av_buf + av->av_buf_head; + tail = av->av_buf + DCCP_MAX_ACKVEC_LEN; for (i = 0; i < nr_opts; ++i) { int copylen = len; @@ -116,7 +114,7 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) to += tailsize; len -= tailsize; copylen -= tailsize; - from = av->dccpav_buf; + from = av->av_buf; } memcpy(to, from, copylen); @@ -134,19 +132,19 @@ int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb) * buf_head; ack_ackno will equal buf_ackno; and ack_nonce will * equal buf_nonce. */ - avr->dccpavr_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq; - avr->dccpavr_ack_ptr = av->dccpav_buf_head; - avr->dccpavr_ack_ackno = av->dccpav_buf_ackno; - avr->dccpavr_ack_nonce = av->dccpav_buf_nonce; - avr->dccpavr_sent_len = av->dccpav_vec_len; + avr->avr_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq; + avr->avr_ack_ptr = av->av_buf_head; + avr->avr_ack_ackno = av->av_buf_ackno; + avr->avr_ack_nonce = av->av_buf_nonce; + avr->avr_sent_len = av->av_vec_len; dccp_ackvec_insert_avr(av, avr); dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, " "ack_ackno=%llu\n", - dccp_role(sk), avr->dccpavr_sent_len, - (unsigned long long)avr->dccpavr_ack_seqno, - (unsigned long long)avr->dccpavr_ack_ackno); + dccp_role(sk), avr->avr_sent_len, + (unsigned long long)avr->avr_ack_seqno, + (unsigned long long)avr->avr_ack_ackno); return 0; } @@ -155,12 +153,12 @@ struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority) struct dccp_ackvec *av = kmem_cache_alloc(dccp_ackvec_slab, priority); if (av != NULL) { - av->dccpav_buf_head = DCCP_MAX_ACKVEC_LEN - 1; - av->dccpav_buf_ackno = UINT48_MAX + 1; - av->dccpav_buf_nonce = av->dccpav_buf_nonce = 0; - av->dccpav_time = ktime_set(0, 0); - av->dccpav_vec_len = 0; - INIT_LIST_HEAD(&av->dccpav_records); + av->av_buf_head = DCCP_MAX_ACKVEC_LEN - 1; + av->av_buf_ackno = UINT48_MAX + 1; + av->av_buf_nonce = 0; + av->av_time = ktime_set(0, 0); + av->av_vec_len = 0; + INIT_LIST_HEAD(&av->av_records); } return av; @@ -171,12 +169,11 @@ void dccp_ackvec_free(struct dccp_ackvec *av) if (unlikely(av == NULL)) return; - if (!list_empty(&av->dccpav_records)) { + if (!list_empty(&av->av_records)) { struct dccp_ackvec_record *avr, *next; - list_for_each_entry_safe(avr, next, &av->dccpav_records, - dccpavr_node) { - list_del_init(&avr->dccpavr_node); + list_for_each_entry_safe(avr, next, &av->av_records, avr_node) { + list_del_init(&avr->avr_node); dccp_ackvec_record_delete(avr); } } @@ -187,13 +184,13 @@ void dccp_ackvec_free(struct dccp_ackvec *av) static inline u8 dccp_ackvec_state(const struct dccp_ackvec *av, const u32 index) { - return av->dccpav_buf[index] & DCCP_ACKVEC_STATE_MASK; + return av->av_buf[index] & DCCP_ACKVEC_STATE_MASK; } static inline u8 dccp_ackvec_len(const struct dccp_ackvec *av, const u32 index) { - return av->dccpav_buf[index] & DCCP_ACKVEC_LEN_MASK; + return av->av_buf[index] & DCCP_ACKVEC_LEN_MASK; } /* @@ -208,29 +205,29 @@ static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av, unsigned int gap; long new_head; - if (av->dccpav_vec_len + packets > DCCP_MAX_ACKVEC_LEN) + if (av->av_vec_len + packets > DCCP_MAX_ACKVEC_LEN) return -ENOBUFS; gap = packets - 1; - new_head = av->dccpav_buf_head - packets; + new_head = av->av_buf_head - packets; if (new_head < 0) { if (gap > 0) { - memset(av->dccpav_buf, DCCP_ACKVEC_STATE_NOT_RECEIVED, + memset(av->av_buf, DCCP_ACKVEC_STATE_NOT_RECEIVED, gap + new_head + 1); gap = -new_head; } new_head += DCCP_MAX_ACKVEC_LEN; } - av->dccpav_buf_head = new_head; + av->av_buf_head = new_head; if (gap > 0) - memset(av->dccpav_buf + av->dccpav_buf_head + 1, + memset(av->av_buf + av->av_buf_head + 1, DCCP_ACKVEC_STATE_NOT_RECEIVED, gap); - av->dccpav_buf[av->dccpav_buf_head] = state; - av->dccpav_vec_len += packets; + av->av_buf[av->av_buf_head] = state; + av->av_vec_len += packets; return 0; } @@ -243,7 +240,7 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, /* * Check at the right places if the buffer is full, if it is, tell the * caller to start dropping packets till the HC-Sender acks our ACK - * vectors, when we will free up space in dccpav_buf. + * vectors, when we will free up space in av_buf. * * We may well decide to do buffer compression, etc, but for now lets * just drop. @@ -263,22 +260,20 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, */ /* See if this is the first ackno being inserted */ - if (av->dccpav_vec_len == 0) { - av->dccpav_buf[av->dccpav_buf_head] = state; - av->dccpav_vec_len = 1; - } else if (after48(ackno, av->dccpav_buf_ackno)) { - const u64 delta = dccp_delta_seqno(av->dccpav_buf_ackno, - ackno); + if (av->av_vec_len == 0) { + av->av_buf[av->av_buf_head] = state; + av->av_vec_len = 1; + } else if (after48(ackno, av->av_buf_ackno)) { + const u64 delta = dccp_delta_seqno(av->av_buf_ackno, ackno); /* * Look if the state of this packet is the same as the * previous ackno and if so if we can bump the head len. */ if (delta == 1 && - dccp_ackvec_state(av, av->dccpav_buf_head) == state && - (dccp_ackvec_len(av, av->dccpav_buf_head) < - DCCP_ACKVEC_LEN_MASK)) - av->dccpav_buf[av->dccpav_buf_head]++; + dccp_ackvec_state(av, av->av_buf_head) == state && + dccp_ackvec_len(av, av->av_buf_head) < DCCP_ACKVEC_LEN_MASK) + av->av_buf[av->av_buf_head]++; else if (dccp_ackvec_set_buf_head_state(av, delta, state)) return -ENOBUFS; } else { @@ -290,14 +285,14 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, * the byte corresponding to S. (Indexing structures * could reduce the complexity of this scan.) */ - u64 delta = dccp_delta_seqno(ackno, av->dccpav_buf_ackno); - u32 index = av->dccpav_buf_head; + u64 delta = dccp_delta_seqno(ackno, av->av_buf_ackno); + u32 index = av->av_buf_head; while (1) { const u8 len = dccp_ackvec_len(av, index); const u8 state = dccp_ackvec_state(av, index); /* - * valid packets not yet in dccpav_buf have a reserved + * valid packets not yet in av_buf have a reserved * entry, with a len equal to 0. */ if (state == DCCP_ACKVEC_STATE_NOT_RECEIVED && @@ -305,7 +300,7 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, reserved seat! */ dccp_pr_debug("Found %llu reserved seat!\n", (unsigned long long)ackno); - av->dccpav_buf[index] = state; + av->av_buf[index] = state; goto out; } /* len == 0 means one packet */ @@ -318,8 +313,8 @@ int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk, } } - av->dccpav_buf_ackno = ackno; - av->dccpav_time = ktime_get_real(); + av->av_buf_ackno = ackno; + av->av_time = ktime_get_real(); out: return 0; @@ -349,9 +344,9 @@ void dccp_ackvector_print(const u64 ackno, const unsigned char *vector, int len) void dccp_ackvec_print(const struct dccp_ackvec *av) { - dccp_ackvector_print(av->dccpav_buf_ackno, - av->dccpav_buf + av->dccpav_buf_head, - av->dccpav_vec_len); + dccp_ackvector_print(av->av_buf_ackno, + av->av_buf + av->av_buf_head, + av->av_vec_len); } #endif @@ -361,17 +356,15 @@ static void dccp_ackvec_throw_record(struct dccp_ackvec *av, struct dccp_ackvec_record *next; /* sort out vector length */ - if (av->dccpav_buf_head <= avr->dccpavr_ack_ptr) - av->dccpav_vec_len = avr->dccpavr_ack_ptr - av->dccpav_buf_head; + if (av->av_buf_head <= avr->avr_ack_ptr) + av->av_vec_len = avr->avr_ack_ptr - av->av_buf_head; else - av->dccpav_vec_len = DCCP_MAX_ACKVEC_LEN - 1 - - av->dccpav_buf_head - + avr->dccpavr_ack_ptr; + av->av_vec_len = DCCP_MAX_ACKVEC_LEN - 1 - + av->av_buf_head + avr->avr_ack_ptr; /* free records */ - list_for_each_entry_safe_from(avr, next, &av->dccpav_records, - dccpavr_node) { - list_del_init(&avr->dccpavr_node); + list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) { + list_del_init(&avr->avr_node); dccp_ackvec_record_delete(avr); } } @@ -386,16 +379,16 @@ void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk, * windows. We will be receiving ACKs for stuff we sent a while back * -sorbo. */ - list_for_each_entry_reverse(avr, &av->dccpav_records, dccpavr_node) { - if (ackno == avr->dccpavr_ack_seqno) { + list_for_each_entry_reverse(avr, &av->av_records, avr_node) { + if (ackno == avr->avr_ack_seqno) { dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, " "ack_ackno=%llu, ACKED!\n", dccp_role(sk), 1, - (unsigned long long)avr->dccpavr_ack_seqno, - (unsigned long long)avr->dccpavr_ack_ackno); + (unsigned long long)avr->avr_ack_seqno, + (unsigned long long)avr->avr_ack_ackno); dccp_ackvec_throw_record(av, avr); break; - } else if (avr->dccpavr_ack_seqno > ackno) + } else if (avr->avr_ack_seqno > ackno) break; /* old news */ } } @@ -409,7 +402,7 @@ static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av, struct dccp_ackvec_record *avr; /* Check if we actually sent an ACK vector */ - if (list_empty(&av->dccpav_records)) + if (list_empty(&av->av_records)) return; i = len; @@ -418,8 +411,7 @@ static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av, * I think it might be more efficient to work backwards. See comment on * rcv_ackno. -sorbo. */ - avr = list_entry(av->dccpav_records.next, struct dccp_ackvec_record, - dccpavr_node); + avr = list_entry(av->av_records.next, struct dccp_ackvec_record, avr_node); while (i--) { const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK; u64 ackno_end_rl; @@ -430,15 +422,14 @@ static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av, * If our AVR sequence number is greater than the ack, go * forward in the AVR list until it is not so. */ - list_for_each_entry_from(avr, &av->dccpav_records, - dccpavr_node) { - if (!after48(avr->dccpavr_ack_seqno, *ackno)) + list_for_each_entry_from(avr, &av->av_records, avr_node) { + if (!after48(avr->avr_ack_seqno, *ackno)) goto found; } - /* End of the dccpav_records list, not found, exit */ + /* End of the av_records list, not found, exit */ break; found: - if (between48(avr->dccpavr_ack_seqno, ackno_end_rl, *ackno)) { + if (between48(avr->avr_ack_seqno, ackno_end_rl, *ackno)) { const u8 state = *vector & DCCP_ACKVEC_STATE_MASK; if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED) { dccp_pr_debug("%s ACK vector 0, len=%d, " @@ -446,9 +437,9 @@ found: "ACKED!\n", dccp_role(sk), len, (unsigned long long) - avr->dccpavr_ack_seqno, + avr->avr_ack_seqno, (unsigned long long) - avr->dccpavr_ack_ackno); + avr->avr_ack_ackno); dccp_ackvec_throw_record(av, avr); break; } diff --git a/net/dccp/ackvec.h b/net/dccp/ackvec.h index 9671ecd17e00..bcb64fb4acef 100644 --- a/net/dccp/ackvec.h +++ b/net/dccp/ackvec.h @@ -32,54 +32,54 @@ * * This data structure is the one defined in RFC 4340, Appendix A. * - * @dccpav_buf_head - circular buffer head - * @dccpav_buf_tail - circular buffer tail - * @dccpav_buf_ackno - ack # of the most recent packet acknowledgeable in the - * buffer (i.e. %dccpav_buf_head) - * @dccpav_buf_nonce - the one-bit sum of the ECN Nonces on all packets acked + * @av_buf_head - circular buffer head + * @av_buf_tail - circular buffer tail + * @av_buf_ackno - ack # of the most recent packet acknowledgeable in the + * buffer (i.e. %av_buf_head) + * @av_buf_nonce - the one-bit sum of the ECN Nonces on all packets acked * by the buffer with State 0 * * Additionally, the HC-Receiver must keep some information about the * Ack Vectors it has recently sent. For each packet sent carrying an * Ack Vector, it remembers four variables: * - * @dccpav_records - list of dccp_ackvec_record - * @dccpav_ack_nonce - the one-bit sum of the ECN Nonces for all State 0. + * @av_records - list of dccp_ackvec_record + * @av_ack_nonce - the one-bit sum of the ECN Nonces for all State 0. * - * @dccpav_time - the time in usecs - * @dccpav_buf - circular buffer of acknowledgeable packets + * @av_time - the time in usecs + * @av_buf - circular buffer of acknowledgeable packets */ struct dccp_ackvec { - u64 dccpav_buf_ackno; - struct list_head dccpav_records; - ktime_t dccpav_time; - u16 dccpav_buf_head; - u16 dccpav_vec_len; - u8 dccpav_buf_nonce; - u8 dccpav_ack_nonce; - u8 dccpav_buf[DCCP_MAX_ACKVEC_LEN]; + u64 av_buf_ackno; + struct list_head av_records; + ktime_t av_time; + u16 av_buf_head; + u16 av_vec_len; + u8 av_buf_nonce; + u8 av_ack_nonce; + u8 av_buf[DCCP_MAX_ACKVEC_LEN]; }; /** struct dccp_ackvec_record - ack vector record * * ACK vector record as defined in Appendix A of spec. * - * The list is sorted by dccpavr_ack_seqno + * The list is sorted by avr_ack_seqno * - * @dccpavr_node - node in dccpav_records - * @dccpavr_ack_seqno - sequence number of the packet this record was sent on - * @dccpavr_ack_ackno - sequence number being acknowledged - * @dccpavr_ack_ptr - pointer into dccpav_buf where this record starts - * @dccpavr_ack_nonce - dccpav_ack_nonce at the time this record was sent - * @dccpavr_sent_len - length of the record in dccpav_buf + * @avr_node - node in av_records + * @avr_ack_seqno - sequence number of the packet this record was sent on + * @avr_ack_ackno - sequence number being acknowledged + * @avr_ack_ptr - pointer into av_buf where this record starts + * @avr_ack_nonce - av_ack_nonce at the time this record was sent + * @avr_sent_len - lenght of the record in av_buf */ struct dccp_ackvec_record { - struct list_head dccpavr_node; - u64 dccpavr_ack_seqno; - u64 dccpavr_ack_ackno; - u16 dccpavr_ack_ptr; - u16 dccpavr_sent_len; - u8 dccpavr_ack_nonce; + struct list_head avr_node; + u64 avr_ack_seqno; + u64 avr_ack_ackno; + u16 avr_ack_ptr; + u16 avr_sent_len; + u8 avr_ack_nonce; }; struct sock; @@ -105,7 +105,7 @@ extern int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb); static inline int dccp_ackvec_pending(const struct dccp_ackvec *av) { - return av->dccpav_vec_len; + return av->av_vec_len; } #else /* CONFIG_IP_DCCP_ACKVEC */ static inline int dccp_ackvec_init(void) diff --git a/net/dccp/ccid.c b/net/dccp/ccid.c index c45088b5e6fb..4809753d12ae 100644 --- a/net/dccp/ccid.c +++ b/net/dccp/ccid.c @@ -92,15 +92,15 @@ int ccid_register(struct ccid_operations *ccid_ops) ccid_ops->ccid_hc_rx_slab = ccid_kmem_cache_create(ccid_ops->ccid_hc_rx_obj_size, - "%s_hc_rx_sock", - ccid_ops->ccid_name); + "ccid%u_hc_rx_sock", + ccid_ops->ccid_id); if (ccid_ops->ccid_hc_rx_slab == NULL) goto out; ccid_ops->ccid_hc_tx_slab = ccid_kmem_cache_create(ccid_ops->ccid_hc_tx_obj_size, - "%s_hc_tx_sock", - ccid_ops->ccid_name); + "ccid%u_hc_tx_sock", + ccid_ops->ccid_id); if (ccid_ops->ccid_hc_tx_slab == NULL) goto out_free_rx_slab; diff --git a/net/dccp/ccid.h b/net/dccp/ccid.h index c65cb2453e43..fdeae7b57319 100644 --- a/net/dccp/ccid.h +++ b/net/dccp/ccid.h @@ -23,14 +23,37 @@ struct tcp_info; +/** + * struct ccid_operations - Interface to Congestion-Control Infrastructure + * + * @ccid_id: numerical CCID ID (up to %CCID_MAX, cf. table 5 in RFC 4340, 10.) + * @ccid_ccmps: the CCMPS including network/transport headers (0 when disabled) + * @ccid_name: alphabetical identifier string for @ccid_id + * @ccid_owner: module which implements/owns this CCID + * @ccid_hc_{r,t}x_slab: memory pool for the receiver/sender half-connection + * @ccid_hc_{r,t}x_obj_size: size of the receiver/sender half-connection socket + * + * @ccid_hc_{r,t}x_init: CCID-specific initialisation routine (before startup) + * @ccid_hc_{r,t}x_exit: CCID-specific cleanup routine (before destruction) + * @ccid_hc_rx_packet_recv: implements the HC-receiver side + * @ccid_hc_{r,t}x_parse_options: parsing routine for CCID/HC-specific options + * @ccid_hc_{r,t}x_insert_options: insert routine for CCID/HC-specific options + * @ccid_hc_tx_packet_recv: implements feedback processing for the HC-sender + * @ccid_hc_tx_send_packet: implements the sending part of the HC-sender + * @ccid_hc_tx_packet_sent: does accounting for packets in flight by HC-sender + * @ccid_hc_{r,t}x_get_info: INET_DIAG information for HC-receiver/sender + * @ccid_hc_{r,t}x_getsockopt: socket options specific to HC-receiver/sender + */ struct ccid_operations { - unsigned char ccid_id; - const char *ccid_name; - struct module *ccid_owner; - struct kmem_cache *ccid_hc_rx_slab; - __u32 ccid_hc_rx_obj_size; - struct kmem_cache *ccid_hc_tx_slab; - __u32 ccid_hc_tx_obj_size; + unsigned char ccid_id; + __u32 ccid_ccmps; + const char *ccid_name; + struct module *ccid_owner; + struct kmem_cache *ccid_hc_rx_slab, + *ccid_hc_tx_slab; + __u32 ccid_hc_rx_obj_size, + ccid_hc_tx_obj_size; + /* Interface Routines */ int (*ccid_hc_rx_init)(struct ccid *ccid, struct sock *sk); int (*ccid_hc_tx_init)(struct ccid *ccid, struct sock *sk); void (*ccid_hc_rx_exit)(struct sock *sk); diff --git a/net/dccp/ccids/Kconfig b/net/dccp/ccids/Kconfig index 80f469887691..12275943eab8 100644 --- a/net/dccp/ccids/Kconfig +++ b/net/dccp/ccids/Kconfig @@ -1,9 +1,8 @@ menu "DCCP CCIDs Configuration (EXPERIMENTAL)" - depends on IP_DCCP && EXPERIMENTAL + depends on EXPERIMENTAL config IP_DCCP_CCID2 tristate "CCID2 (TCP-Like) (EXPERIMENTAL)" - depends on IP_DCCP def_tristate IP_DCCP select IP_DCCP_ACKVEC ---help--- @@ -20,18 +19,9 @@ config IP_DCCP_CCID2 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. + also prefer CCID 2. See RFC 4341 for further details. - CCID 2 is further described in RFC 4341, - http://www.ietf.org/rfc/rfc4341.txt - - This text was extracted from RFC 4340 (sec. 10.1), - http://www.ietf.org/rfc/rfc4340.txt - - To compile this CCID as a module, choose M here: the module will be - called dccp_ccid2. - - If in doubt, say M. + CCID2 is the default CCID used by DCCP. config IP_DCCP_CCID2_DEBUG bool "CCID2 debugging messages" @@ -47,8 +37,8 @@ config IP_DCCP_CCID2_DEBUG config IP_DCCP_CCID3 tristate "CCID3 (TCP-Friendly) (EXPERIMENTAL)" - depends on IP_DCCP def_tristate IP_DCCP + select IP_DCCP_TFRC_LIB ---help--- CCID 3 denotes TCP-Friendly Rate Control (TFRC), an equation-based rate-controlled congestion control mechanism. TFRC is designed to @@ -74,10 +64,6 @@ config IP_DCCP_CCID3 If in doubt, say M. -config IP_DCCP_TFRC_LIB - depends on IP_DCCP_CCID3 - def_tristate IP_DCCP_CCID3 - config IP_DCCP_CCID3_DEBUG bool "CCID3 debugging messages" depends on IP_DCCP_CCID3 @@ -121,5 +107,13 @@ config IP_DCCP_CCID3_RTO is serious network congestion: experimenting with larger values should therefore not be performed on WANs. +config IP_DCCP_TFRC_LIB + tristate + default n + +config IP_DCCP_TFRC_DEBUG + bool + depends on IP_DCCP_TFRC_LIB + default y if IP_DCCP_CCID3_DEBUG endmenu diff --git a/net/dccp/ccids/ccid2.c b/net/dccp/ccids/ccid2.c index d694656b8800..b5b52ebb2693 100644 --- a/net/dccp/ccids/ccid2.c +++ b/net/dccp/ccids/ccid2.c @@ -24,9 +24,6 @@ /* * This implementation should follow RFC 4341 - * - * BUGS: - * - sequence number wrapping */ #include "../ccid.h" @@ -129,50 +126,35 @@ static int ccid2_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb) { struct ccid2_hc_tx_sock *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; - } - } + if (hctx->ccid2hctx_pipe < hctx->ccid2hctx_cwnd) + return 0; return 1; /* XXX CCID should dequeue when ready instead of polling */ } -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)->ccid2hctx_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; } + if (val > 0xFFFF) /* RFC 4340, 11.3 */ + val = 0xFFFF; - ccid2_pr_debug("changing local ack ratio to %d\n", val); - WARN_ON(val <= 0); - dp->dccps_l_ack_ratio = val; -} + if (val == dp->dccps_l_ack_ratio) + return; -static void ccid2_change_cwnd(struct ccid2_hc_tx_sock *hctx, u32 val) -{ - /* XXX do we need to change ack ratio? */ - hctx->ccid2hctx_cwnd = val? : 1; - ccid2_pr_debug("changed cwnd to %u\n", hctx->ccid2hctx_cwnd); + ccid2_pr_debug("changing local ack ratio to %u\n", val); + dp->dccps_l_ack_ratio = val; } static void ccid2_change_srtt(struct ccid2_hc_tx_sock *hctx, long val) @@ -181,11 +163,6 @@ static void ccid2_change_srtt(struct ccid2_hc_tx_sock *hctx, long val) hctx->ccid2hctx_srtt = val; } -static void ccid2_change_pipe(struct ccid2_hc_tx_sock *hctx, long val) -{ - hctx->ccid2hctx_pipe = val; -} - static void ccid2_start_rto_timer(struct sock *sk); static void ccid2_hc_tx_rto_expire(unsigned long data) @@ -215,21 +192,17 @@ static void ccid2_hc_tx_rto_expire(unsigned long data) ccid2_start_rto_timer(sk); /* adjust pipe, cwnd etc */ - ccid2_change_pipe(hctx, 0); - hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd >> 1; + hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd / 2; if (hctx->ccid2hctx_ssthresh < 2) hctx->ccid2hctx_ssthresh = 2; - ccid2_change_cwnd(hctx, 1); + hctx->ccid2hctx_cwnd = 1; + hctx->ccid2hctx_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; + hctx->ccid2hctx_seqt = hctx->ccid2hctx_seqh; + hctx->ccid2hctx_packets_acked = 0; /* clear ack ratio state. */ - hctx->ccid2hctx_arsent = 0; - hctx->ccid2hctx_ackloss = 0; hctx->ccid2hctx_rpseq = 0; hctx->ccid2hctx_rpdupack = -1; ccid2_change_l_ack_ratio(sk, 1); @@ -255,23 +228,10 @@ static void ccid2_hc_tx_packet_sent(struct sock *sk, int more, unsigned int len) struct dccp_sock *dp = dccp_sk(sk); struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); struct ccid2_seq *next; - u64 seq; - - ccid2_hc_tx_check_sanity(hctx); - BUG_ON(!hctx->ccid2hctx_sendwait); - hctx->ccid2hctx_sendwait = 0; - ccid2_change_pipe(hctx, hctx->ccid2hctx_pipe + 1); - BUG_ON(hctx->ccid2hctx_pipe < 0); + hctx->ccid2hctx_pipe++; - /* 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; - - hctx->ccid2hctx_seqh->ccid2s_seq = seq; + hctx->ccid2hctx_seqh->ccid2s_seq = dp->dccps_gss; hctx->ccid2hctx_seqh->ccid2s_acked = 0; hctx->ccid2hctx_seqh->ccid2s_sent = jiffies; @@ -291,8 +251,26 @@ static void ccid2_hc_tx_packet_sent(struct sock *sk, int more, unsigned int len) ccid2_pr_debug("cwnd=%d pipe=%d\n", hctx->ccid2hctx_cwnd, hctx->ccid2hctx_pipe); - hctx->ccid2hctx_sent++; - + /* + * 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++; /* We had an ack loss in this window... */ @@ -320,14 +298,13 @@ static void ccid2_hc_tx_packet_sent(struct sock *sk, int more, unsigned int len) hctx->ccid2hctx_arsent = 0; /* or maybe set it to cwnd*/ } } +#endif /* setup RTO timer */ if (!timer_pending(&hctx->ccid2hctx_rtotimer)) ccid2_start_rto_timer(sk); #ifdef CONFIG_IP_DCCP_CCID2_DEBUG - ccid2_pr_debug("pipe=%d\n", hctx->ccid2hctx_pipe); - ccid2_pr_debug("Sent: seq=%llu\n", (unsigned long long)seq); do { struct ccid2_seq *seqp = hctx->ccid2hctx_seqt; @@ -419,31 +396,15 @@ static inline void ccid2_new_ack(struct sock *sk, { 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; - } - } else { - /* increased cwnd enough for this single ack */ - hctx->ccid2hctx_ssacks = 0; - } - } else { - hctx->ccid2hctx_ssacks = 0; - hctx->ccid2hctx_acks++; - - if (hctx->ccid2hctx_acks >= hctx->ccid2hctx_cwnd) { - ccid2_change_cwnd(hctx, hctx->ccid2hctx_cwnd + 1); - hctx->ccid2hctx_acks = 0; + if (*maxincr > 0 && ++hctx->ccid2hctx_packets_acked == 2) { + hctx->ccid2hctx_cwnd += 1; + *maxincr -= 1; + hctx->ccid2hctx_packets_acked = 0; } + } else if (++hctx->ccid2hctx_packets_acked >= hctx->ccid2hctx_cwnd) { + hctx->ccid2hctx_cwnd += 1; + hctx->ccid2hctx_packets_acked = 0; } /* update RTO */ @@ -502,7 +463,6 @@ static inline void ccid2_new_ack(struct sock *sk, 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 */ @@ -514,16 +474,19 @@ static void ccid2_hc_tx_dec_pipe(struct sock *sk) { struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); - ccid2_change_pipe(hctx, hctx->ccid2hctx_pipe-1); - BUG_ON(hctx->ccid2hctx_pipe < 0); + if (hctx->ccid2hctx_pipe == 0) + DCCP_BUG("pipe == 0"); + else + hctx->ccid2hctx_pipe--; if (hctx->ccid2hctx_pipe == 0) ccid2_hc_tx_kill_rto_timer(sk); } -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) { + struct ccid2_hc_tx_sock *hctx = ccid2_hc_tx_sk(sk); + if (time_before(seqp->ccid2s_sent, hctx->ccid2hctx_last_cong)) { ccid2_pr_debug("Multiple losses in an RTT---treating as one\n"); return; @@ -531,10 +494,12 @@ static void ccid2_congestion_event(struct ccid2_hc_tx_sock *hctx, hctx->ccid2hctx_last_cong = jiffies; - ccid2_change_cwnd(hctx, hctx->ccid2hctx_cwnd >> 1); - hctx->ccid2hctx_ssthresh = hctx->ccid2hctx_cwnd; - if (hctx->ccid2hctx_ssthresh < 2) - hctx->ccid2hctx_ssthresh = 2; + hctx->ccid2hctx_cwnd = hctx->ccid2hctx_cwnd / 2 ? : 1U; + hctx->ccid2hctx_ssthresh = max(hctx->ccid2hctx_cwnd, 2U); + + /* Avoid spurious timeouts resulting from Ack Ratio > cwnd */ + if (dccp_sk(sk)->dccps_l_ack_ratio > hctx->ccid2hctx_cwnd) + ccid2_change_l_ack_ratio(sk, hctx->ccid2hctx_cwnd); } static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) @@ -570,12 +535,11 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) hctx->ccid2hctx_rpdupack++; /* check if we got enough dupacks */ - if (hctx->ccid2hctx_rpdupack >= - hctx->ccid2hctx_numdupack) { + if (hctx->ccid2hctx_rpdupack >= NUMDUPACK) { hctx->ccid2hctx_rpdupack = -1; /* XXX lame */ hctx->ccid2hctx_rpseq = 0; - ccid2_change_l_ack_ratio(sk, dp->dccps_l_ack_ratio << 1); + ccid2_change_l_ack_ratio(sk, 2 * dp->dccps_l_ack_ratio); } } } @@ -606,12 +570,13 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) } } - /* 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 (hctx->ccid2hctx_cwnd < hctx->ccid2hctx_ssthresh) + maxincr = DIV_ROUND_UP(dp->dccps_l_ack_ratio, 2); /* go through all ack vectors */ while ((offset = ccid2_ackvector(sk, skb, offset, @@ -619,9 +584,8 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) /* go through this ack vector */ while (veclen--) { const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK; - u64 ackno_end_rl; + u64 ackno_end_rl = SUB48(ackno, rl); - dccp_set_seqno(&ackno_end_rl, ackno - rl); ccid2_pr_debug("ackvec start:%llu end:%llu\n", (unsigned long long)ackno, (unsigned long long)ackno_end_rl); @@ -651,7 +615,7 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) !seqp->ccid2s_acked) { if (state == DCCP_ACKVEC_STATE_ECN_MARKED) { - ccid2_congestion_event(hctx, + ccid2_congestion_event(sk, seqp); } else ccid2_new_ack(sk, seqp, @@ -666,13 +630,12 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) done = 1; break; } - seqp = seqp->ccid2s_next; + seqp = seqp->ccid2s_prev; } if (done) break; - - dccp_set_seqno(&ackno, ackno_end_rl - 1); + ackno = SUB48(ackno_end_rl, 1); vector++; } if (done) @@ -694,7 +657,7 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) while (1) { if (seqp->ccid2s_acked) { done++; - if (done == hctx->ccid2hctx_numdupack) + if (done == NUMDUPACK) break; } if (seqp == hctx->ccid2hctx_seqt) @@ -705,7 +668,7 @@ 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 */ @@ -717,7 +680,7 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) * order to detect multiple congestion events in * one ack vector. */ - ccid2_congestion_event(hctx, seqp); + ccid2_congestion_event(sk, seqp); ccid2_hc_tx_dec_pipe(sk); } if (seqp == hctx->ccid2hctx_seqt) @@ -742,14 +705,23 @@ static void ccid2_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk) { struct ccid2_hc_tx_sock *hctx = ccid_priv(ccid); + struct dccp_sock *dp = dccp_sk(sk); + u32 max_ratio; + + /* RFC 4341, 5: initialise ssthresh to arbitrarily high (max) value */ + hctx->ccid2hctx_ssthresh = ~0U; - 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. + /* + * RFC 4341, 5: "The cwnd parameter is initialized to at most four + * packets for new connections, following the rules from [RFC3390]". + * We need to convert the bytes of RFC3390 into the packets of RFC 4341. */ - hctx->ccid2hctx_ssthresh = ~0; - hctx->ccid2hctx_numdupack = 3; + hctx->ccid2hctx_cwnd = min(4U, max(2U, 4380U / dp->dccps_mss_cache)); + + /* Make sure that Ack Ratio is enabled and within bounds. */ + max_ratio = DIV_ROUND_UP(hctx->ccid2hctx_cwnd, 2); + if (dp->dccps_l_ack_ratio == 0 || dp->dccps_l_ack_ratio > max_ratio) + dp->dccps_l_ack_ratio = max_ratio; /* XXX init ~ to window size... */ if (ccid2_hc_tx_alloc_seq(hctx)) @@ -760,10 +732,8 @@ static int ccid2_hc_tx_init(struct ccid *ccid, struct sock *sk) hctx->ccid2hctx_rttvar = -1; hctx->ccid2hctx_rpdupack = -1; hctx->ccid2hctx_last_cong = jiffies; - - hctx->ccid2hctx_rtotimer.function = &ccid2_hc_tx_rto_expire; - hctx->ccid2hctx_rtotimer.data = (unsigned long)sk; - init_timer(&hctx->ccid2hctx_rtotimer); + setup_timer(&hctx->ccid2hctx_rtotimer, ccid2_hc_tx_rto_expire, + (unsigned long)sk); ccid2_hc_tx_check_sanity(hctx); return 0; @@ -800,7 +770,7 @@ static void ccid2_hc_rx_packet_recv(struct sock *sk, struct sk_buff *skb) static struct ccid_operations ccid2 = { .ccid_id = DCCPC_CCID2, - .ccid_name = "ccid2", + .ccid_name = "TCP-like", .ccid_owner = THIS_MODULE, .ccid_hc_tx_obj_size = sizeof(struct ccid2_hc_tx_sock), .ccid_hc_tx_init = ccid2_hc_tx_init, diff --git a/net/dccp/ccids/ccid2.h b/net/dccp/ccids/ccid2.h index d9daa534c9be..2c94ca029010 100644 --- a/net/dccp/ccids/ccid2.h +++ b/net/dccp/ccids/ccid2.h @@ -24,6 +24,8 @@ #include <linux/timer.h> #include <linux/types.h> #include "../ccid.h" +/* NUMDUPACK parameter from RFC 4341, p. 6 */ +#define NUMDUPACK 3 struct sock; @@ -40,22 +42,17 @@ struct ccid2_seq { /** 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_{cwnd,ssthresh,pipe}: as per RFC 4341, section 5 + * @ccid2hctx_packets_acked - Ack counter for deriving cwnd growth (RFC 3465) * @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 */ struct ccid2_hc_tx_sock { u32 ccid2hctx_cwnd; - int ccid2hctx_ssacks; - int ccid2hctx_acks; - unsigned int ccid2hctx_ssthresh; - int ccid2hctx_pipe; - int ccid2hctx_numdupack; + u32 ccid2hctx_ssthresh; + u32 ccid2hctx_pipe; + u32 ccid2hctx_packets_acked; struct ccid2_seq *ccid2hctx_seqbuf[CCID2_SEQBUF_MAX]; int ccid2hctx_seqbufc; struct ccid2_seq *ccid2hctx_seqh; @@ -63,14 +60,10 @@ struct ccid2_hc_tx_sock { 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; u64 ccid2hctx_high_ack; }; diff --git a/net/dccp/ccids/ccid3.c b/net/dccp/ccids/ccid3.c index d133416d3970..e76f460af0ea 100644 --- a/net/dccp/ccids/ccid3.c +++ b/net/dccp/ccids/ccid3.c @@ -1,6 +1,7 @@ /* * net/dccp/ccids/ccid3.c * + * 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> * @@ -33,11 +34,7 @@ * 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" #include <asm/unaligned.h> @@ -49,9 +46,6 @@ static int ccid3_debug; #define ccid3_pr_debug(format, a...) #endif -static struct dccp_tx_hist *ccid3_tx_hist; -static struct dccp_rx_hist *ccid3_rx_hist; - /* * Transmitter Half-Connection Routines */ @@ -83,24 +77,27 @@ static void ccid3_hc_tx_set_state(struct sock *sk, } /* - * Compute the initial sending rate X_init according to RFC 3390: - * w_init = min(4 * MSS, max(2 * MSS, 4380 bytes)) - * X_init = w_init / RTT + * 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 dccp_sock *dp = dccp_sk(sk); - const __u32 w_init = min(4 * dp->dccps_mss_cache, - max(2 * dp->dccps_mss_cache, 4380U)); + const struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); + const __u32 w_init = min_t(__u32, 4 * hctx->ccid3hctx_s, + max_t(__u32, 2 * hctx->ccid3hctx_s, 4380)); - return scaled_div(w_init << 6, ccid3_hc_tx_sk(sk)->ccid3hctx_rtt); + return scaled_div(w_init << 6, hctx->ccid3hctx_rtt); } /* * Recalculate t_ipi and delta (should be called whenever X changes) */ -static inline void ccid3_update_send_interval(struct ccid3_hc_tx_sock *hctx) +static void ccid3_update_send_interval(struct ccid3_hc_tx_sock *hctx) { /* Calculate new t_ipi = s / X_inst (X_inst is in 64 * bytes/second) */ hctx->ccid3hctx_t_ipi = scaled_div32(((u64)hctx->ccid3hctx_s) << 6, @@ -116,6 +113,13 @@ static inline void ccid3_update_send_interval(struct ccid3_hc_tx_sock *hctx) } +static u32 ccid3_hc_tx_idle_rtt(struct ccid3_hc_tx_sock *hctx, ktime_t now) +{ + u32 delta = ktime_us_delta(now, hctx->ccid3hctx_t_last_win_count); + + return delta / hctx->ccid3hctx_rtt; +} + /** * ccid3_hc_tx_update_x - Update allowed sending rate X * @stamp: most recent time if available - can be left NULL. @@ -127,19 +131,19 @@ static inline void ccid3_update_send_interval(struct ccid3_hc_tx_sock *hctx) * */ static void ccid3_hc_tx_update_x(struct sock *sk, ktime_t *stamp) - { struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); __u64 min_rate = 2 * hctx->ccid3hctx_x_recv; const __u64 old_x = hctx->ccid3hctx_x; - ktime_t now = stamp? *stamp : ktime_get_real(); + ktime_t now = stamp ? *stamp : ktime_get_real(); /* * Handle IDLE periods: do not reduce below RFC3390 initial sending rate - * when idling [RFC 4342, 5.1]. See also draft-ietf-dccp-rfc3448bis. + * 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 (unlikely(hctx->ccid3hctx_idle)) { + if (ccid3_hc_tx_idle_rtt(hctx, now) >= 2) { min_rate = rfc3390_initial_rate(sk); min_rate = max(min_rate, 2 * hctx->ccid3hctx_x_recv); } @@ -181,7 +185,7 @@ static inline void ccid3_hc_tx_update_s(struct ccid3_hc_tx_sock *hctx, int len) { const u16 old_s = hctx->ccid3hctx_s; - hctx->ccid3hctx_s = old_s == 0 ? len : (9 * old_s + len) / 10; + hctx->ccid3hctx_s = tfrc_ewma(hctx->ccid3hctx_s, len, 9); if (hctx->ccid3hctx_s != old_s) ccid3_update_send_interval(hctx); @@ -225,29 +229,27 @@ static void ccid3_hc_tx_no_feedback_timer(unsigned long data) ccid3_pr_debug("%s(%p, state=%s) - entry \n", dccp_role(sk), sk, ccid3_tx_state_name(hctx->ccid3hctx_state)); - hctx->ccid3hctx_idle = 1; + if (hctx->ccid3hctx_state == TFRC_SSTATE_FBACK) + ccid3_hc_tx_set_state(sk, TFRC_SSTATE_NO_FBACK); + else if (hctx->ccid3hctx_state != TFRC_SSTATE_NO_FBACK) + goto out; - switch (hctx->ccid3hctx_state) { - case TFRC_SSTATE_NO_FBACK: - /* RFC 3448, 4.4: Halve send rate directly */ + /* + * Determine new allowed sending rate X as per draft rfc3448bis-00, 4.4 + */ + if (hctx->ccid3hctx_t_rto == 0 || /* no feedback received yet */ + hctx->ccid3hctx_p == 0) { + + /* halve send rate directly */ hctx->ccid3hctx_x = max(hctx->ccid3hctx_x / 2, (((__u64)hctx->ccid3hctx_s) << 6) / TFRC_T_MBI); - - ccid3_pr_debug("%s(%p, state=%s), updated tx rate to %u " - "bytes/s\n", dccp_role(sk), sk, - ccid3_tx_state_name(hctx->ccid3hctx_state), - (unsigned)(hctx->ccid3hctx_x >> 6)); - /* The value of R is still undefined and so we can not recompute - * the timeout value. Keep initial value as per [RFC 4342, 5]. */ - t_nfb = TFRC_INITIAL_TIMEOUT; ccid3_update_send_interval(hctx); - break; - case TFRC_SSTATE_FBACK: + } else { /* - * Modify the cached value of X_recv [RFC 3448, 4.4] + * Modify the cached value of X_recv * - * If (p == 0 || X_calc > 2 * X_recv) + * If (X_calc > 2 * X_recv) * X_recv = max(X_recv / 2, s / (2 * t_mbi)); * Else * X_recv = X_calc / 4; @@ -256,32 +258,28 @@ static void ccid3_hc_tx_no_feedback_timer(unsigned long data) */ BUG_ON(hctx->ccid3hctx_p && !hctx->ccid3hctx_x_calc); - if (hctx->ccid3hctx_p == 0 || - (hctx->ccid3hctx_x_calc > (hctx->ccid3hctx_x_recv >> 5))) { - + if (hctx->ccid3hctx_x_calc > (hctx->ccid3hctx_x_recv >> 5)) hctx->ccid3hctx_x_recv = max(hctx->ccid3hctx_x_recv / 2, (((__u64)hctx->ccid3hctx_s) << 6) / (2 * TFRC_T_MBI)); - } else { + else { hctx->ccid3hctx_x_recv = hctx->ccid3hctx_x_calc; hctx->ccid3hctx_x_recv <<= 4; } - /* Now recalculate X [RFC 3448, 4.3, step (4)] */ ccid3_hc_tx_update_x(sk, NULL); - /* - * Schedule no feedback timer to expire in - * max(t_RTO, 2 * s/X) = max(t_RTO, 2 * t_ipi) - * See comments in packet_recv() regarding the value of t_RTO. - */ - t_nfb = max(hctx->ccid3hctx_t_rto, 2 * hctx->ccid3hctx_t_ipi); - break; - case TFRC_SSTATE_NO_SENT: - DCCP_BUG("%s(%p) - Illegal state NO_SENT", dccp_role(sk), sk); - /* fall through */ - case TFRC_SSTATE_TERM: - goto out; } + ccid3_pr_debug("Reduced X to %llu/64 bytes/sec\n", + (unsigned long long)hctx->ccid3hctx_x); + + /* + * Set new timeout for the nofeedback timer. + * See comments in packet_recv() regarding the value of t_RTO. + */ + if (unlikely(hctx->ccid3hctx_t_rto == 0)) /* no feedback yet */ + t_nfb = TFRC_INITIAL_TIMEOUT; + else + t_nfb = max(hctx->ccid3hctx_t_rto, 2 * hctx->ccid3hctx_t_ipi); restart_timer: sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer, @@ -336,8 +334,8 @@ static int ccid3_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb) hctx->ccid3hctx_x = rfc3390_initial_rate(sk); hctx->ccid3hctx_t_ld = now; } else { - /* Sender does not have RTT sample: X = MSS/second */ - hctx->ccid3hctx_x = dp->dccps_mss_cache; + /* Sender does not have RTT sample: X_pps = 1 pkt/sec */ + hctx->ccid3hctx_x = hctx->ccid3hctx_s; hctx->ccid3hctx_x <<= 6; } ccid3_update_send_interval(hctx); @@ -369,7 +367,6 @@ static int ccid3_hc_tx_send_packet(struct sock *sk, struct sk_buff *skb) /* prepare to send now (add options etc.) */ dp->dccps_hc_tx_insert_options = 1; DCCP_SKB_CB(skb)->dccpd_ccval = hctx->ccid3hctx_last_win_count; - hctx->ccid3hctx_idle = 0; /* set the nominal send time for the next following packet */ hctx->ccid3hctx_t_nom = ktime_add_us(hctx->ccid3hctx_t_nom, @@ -381,28 +378,17 @@ static void ccid3_hc_tx_packet_sent(struct sock *sk, int more, unsigned int len) { struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); - struct dccp_tx_hist_entry *packet; ccid3_hc_tx_update_s(hctx, len); - packet = dccp_tx_hist_entry_new(ccid3_tx_hist, GFP_ATOMIC); - if (unlikely(packet == NULL)) { + if (tfrc_tx_hist_add(&hctx->ccid3hctx_hist, dccp_sk(sk)->dccps_gss)) DCCP_CRIT("packet history - out of memory!"); - return; - } - dccp_tx_hist_add_entry(&hctx->ccid3hctx_hist, packet); - - packet->dccphtx_tstamp = ktime_get_real(); - packet->dccphtx_seqno = dccp_sk(sk)->dccps_gss; - packet->dccphtx_rtt = hctx->ccid3hctx_rtt; - packet->dccphtx_sent = 1; } static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) { struct ccid3_hc_tx_sock *hctx = ccid3_hc_tx_sk(sk); struct ccid3_options_received *opt_recv; - struct dccp_tx_hist_entry *packet; ktime_t now; unsigned long t_nfb; u32 pinv, r_sample; @@ -411,131 +397,112 @@ static void ccid3_hc_tx_packet_recv(struct sock *sk, struct sk_buff *skb) if (!(DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK || DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_DATAACK)) return; + /* ... and only in the established state */ + if (hctx->ccid3hctx_state != TFRC_SSTATE_FBACK && + hctx->ccid3hctx_state != TFRC_SSTATE_NO_FBACK) + return; opt_recv = &hctx->ccid3hctx_options_received; + now = ktime_get_real(); - switch (hctx->ccid3hctx_state) { - case TFRC_SSTATE_NO_FBACK: - case TFRC_SSTATE_FBACK: - /* get packet from history to look up t_recvdata */ - packet = dccp_tx_hist_find_entry(&hctx->ccid3hctx_hist, - DCCP_SKB_CB(skb)->dccpd_ack_seq); - if (unlikely(packet == NULL)) { - DCCP_WARN("%s(%p), seqno %llu(%s) doesn't exist " - "in history!\n", 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 receive rate in units of 64 * bytes/second */ - hctx->ccid3hctx_x_recv = opt_recv->ccid3or_receive_rate; - hctx->ccid3hctx_x_recv <<= 6; + /* Estimate RTT from history if ACK number is valid */ + r_sample = tfrc_tx_hist_rtt(hctx->ccid3hctx_hist, + DCCP_SKB_CB(skb)->dccpd_ack_seq, now); + if (r_sample == 0) { + DCCP_WARN("%s(%p): %s with bogus ACK-%llu\n", dccp_role(sk), sk, + dccp_packet_name(DCCP_SKB_CB(skb)->dccpd_type), + (unsigned long long)DCCP_SKB_CB(skb)->dccpd_ack_seq); + return; + } - /* Update loss event rate */ - pinv = opt_recv->ccid3or_loss_event_rate; - if (pinv == ~0U || pinv == 0) /* see RFC 4342, 8.5 */ - hctx->ccid3hctx_p = 0; - else /* can not exceed 100% */ - hctx->ccid3hctx_p = 1000000 / pinv; + /* Update receive rate in units of 64 * bytes/second */ + hctx->ccid3hctx_x_recv = opt_recv->ccid3or_receive_rate; + hctx->ccid3hctx_x_recv <<= 6; - now = ktime_get_real(); - /* - * Calculate new round trip sample as per [RFC 3448, 4.3] by - * R_sample = (now - t_recvdata) - t_elapsed - */ - r_sample = dccp_sample_rtt(sk, ktime_us_delta(now, packet->dccphtx_tstamp)); + /* Update loss event rate (which is scaled by 1e6) */ + pinv = opt_recv->ccid3or_loss_event_rate; + if (pinv == ~0U || pinv == 0) /* see RFC 4342, 8.5 */ + hctx->ccid3hctx_p = 0; + else /* can not exceed 100% */ + hctx->ccid3hctx_p = scaled_div(1, pinv); + /* + * Validate new RTT sample and update moving average + */ + r_sample = dccp_sample_rtt(sk, r_sample); + hctx->ccid3hctx_rtt = tfrc_ewma(hctx->ccid3hctx_rtt, r_sample, 9); + /* + * Update allowed sending rate X as per draft rfc3448bis-00, 4.2/3 + */ + if (hctx->ccid3hctx_state == TFRC_SSTATE_NO_FBACK) { + ccid3_hc_tx_set_state(sk, TFRC_SSTATE_FBACK); - /* - * 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) { + if (hctx->ccid3hctx_t_rto == 0) { /* - * Larger Initial Windows [RFC 4342, sec. 5] + * Initial feedback packet: Larger Initial Windows (4.2) */ - hctx->ccid3hctx_rtt = r_sample; hctx->ccid3hctx_x = rfc3390_initial_rate(sk); hctx->ccid3hctx_t_ld = now; ccid3_update_send_interval(hctx); - ccid3_pr_debug("%s(%p), s=%u, MSS=%u, " - "R_sample=%uus, X=%u\n", dccp_role(sk), - sk, hctx->ccid3hctx_s, - dccp_sk(sk)->dccps_mss_cache, r_sample, - (unsigned)(hctx->ccid3hctx_x >> 6)); - - ccid3_hc_tx_set_state(sk, TFRC_SSTATE_FBACK); - } else { - hctx->ccid3hctx_rtt = (9 * hctx->ccid3hctx_rtt + - r_sample) / 10; - - /* Update sending rate (step 4 of [RFC 3448, 4.3]) */ - if (hctx->ccid3hctx_p > 0) - hctx->ccid3hctx_x_calc = - tfrc_calc_x(hctx->ccid3hctx_s, - hctx->ccid3hctx_rtt, - hctx->ccid3hctx_p); - ccid3_hc_tx_update_x(sk, &now); - - 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, hctx->ccid3hctx_rtt, r_sample, - hctx->ccid3hctx_s, hctx->ccid3hctx_p, - hctx->ccid3hctx_x_calc, - (unsigned)(hctx->ccid3hctx_x_recv >> 6), - (unsigned)(hctx->ccid3hctx_x >> 6)); + goto done_computing_x; + } else if (hctx->ccid3hctx_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 (step 4 of [RFC 3448, 4.3]) */ + if (hctx->ccid3hctx_p > 0) + hctx->ccid3hctx_x_calc = + tfrc_calc_x(hctx->ccid3hctx_s, + hctx->ccid3hctx_rtt, + hctx->ccid3hctx_p); + ccid3_hc_tx_update_x(sk, &now); + +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, hctx->ccid3hctx_rtt, r_sample, + hctx->ccid3hctx_s, hctx->ccid3hctx_p, + hctx->ccid3hctx_x_calc, + (unsigned)(hctx->ccid3hctx_x_recv >> 6), + (unsigned)(hctx->ccid3hctx_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_ccid - */ - sk->sk_write_space(sk); + /* unschedule no feedback timer */ + sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer); - /* - * Update timeout interval for the nofeedback timer. - * We use a configuration option to increase the lower bound. - * This can help avoid triggering the nofeedback timer too - * often ('spinning') on LANs with small RTTs. - */ - hctx->ccid3hctx_t_rto = max_t(u32, 4 * hctx->ccid3hctx_rtt, - CONFIG_IP_DCCP_CCID3_RTO * - (USEC_PER_SEC/1000)); - /* - * Schedule no feedback timer to expire in - * max(t_RTO, 2 * s/X) = max(t_RTO, 2 * t_ipi) - */ - t_nfb = max(hctx->ccid3hctx_t_rto, 2 * hctx->ccid3hctx_t_ipi); + /* + * 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); - 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); + /* + * Update timeout interval for the nofeedback timer. + * We use a configuration option to increase the lower bound. + * This can help avoid triggering the nofeedback timer too + * often ('spinning') on LANs with small RTTs. + */ + hctx->ccid3hctx_t_rto = max_t(u32, 4 * hctx->ccid3hctx_rtt, + (CONFIG_IP_DCCP_CCID3_RTO * + (USEC_PER_SEC / 1000))); + /* + * Schedule no feedback timer to expire in + * max(t_RTO, 2 * s/X) = max(t_RTO, 2 * t_ipi) + */ + t_nfb = max(hctx->ccid3hctx_t_rto, 2 * hctx->ccid3hctx_t_ipi); - sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer, - jiffies + usecs_to_jiffies(t_nfb)); + 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); - /* set idle flag */ - hctx->ccid3hctx_idle = 1; - break; - case TFRC_SSTATE_NO_SENT: /* fall through */ - case TFRC_SSTATE_TERM: /* ignore feedback when closing */ - break; - } + sk_reset_timer(sk, &hctx->ccid3hctx_no_feedback_timer, + jiffies + usecs_to_jiffies(t_nfb)); } static int ccid3_hc_tx_parse_options(struct sock *sk, unsigned char option, @@ -605,12 +572,9 @@ static int ccid3_hc_tx_init(struct ccid *ccid, struct sock *sk) struct ccid3_hc_tx_sock *hctx = ccid_priv(ccid); hctx->ccid3hctx_state = TFRC_SSTATE_NO_SENT; - INIT_LIST_HEAD(&hctx->ccid3hctx_hist); - - 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); + hctx->ccid3hctx_hist = NULL; + setup_timer(&hctx->ccid3hctx_no_feedback_timer, + ccid3_hc_tx_no_feedback_timer, (unsigned long)sk); return 0; } @@ -622,8 +586,7 @@ static void ccid3_hc_tx_exit(struct sock *sk) ccid3_hc_tx_set_state(sk, TFRC_SSTATE_TERM); sk_stop_timer(sk, &hctx->ccid3hctx_no_feedback_timer); - /* Empty packet history */ - dccp_tx_hist_purge(ccid3_tx_hist, &hctx->ccid3hctx_hist); + tfrc_tx_hist_purge(&hctx->ccid3hctx_hist); } static void ccid3_hc_tx_get_info(struct sock *sk, struct tcp_info *info) @@ -670,6 +633,15 @@ static int ccid3_hc_tx_getsockopt(struct sock *sk, const int optname, int len, /* * Receiver Half-Connection Routines */ + +/* CCID3 feedback types */ +enum ccid3_fback_type { + CCID3_FBACK_NONE = 0, + CCID3_FBACK_INITIAL, + CCID3_FBACK_PERIODIC, + CCID3_FBACK_PARAM_CHANGE +}; + #ifdef CONFIG_IP_DCCP_CCID3_DEBUG static const char *ccid3_rx_state_name(enum ccid3_hc_rx_states state) { @@ -696,67 +668,58 @@ static void ccid3_hc_rx_set_state(struct sock *sk, hcrx->ccid3hcrx_state = state; } -static inline void ccid3_hc_rx_update_s(struct ccid3_hc_rx_sock *hcrx, int len) -{ - if (unlikely(len == 0)) /* don't update on empty packets (e.g. ACKs) */ - ccid3_pr_debug("Packet payload length is 0 - not updating\n"); - else - hcrx->ccid3hcrx_s = hcrx->ccid3hcrx_s == 0 ? len : - (9 * hcrx->ccid3hcrx_s + len) / 10; -} - -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 dccp_sock *dp = dccp_sk(sk); - struct dccp_rx_hist_entry *packet; ktime_t now; - suseconds_t delta; + s64 delta = 0; - ccid3_pr_debug("%s(%p) - entry \n", dccp_role(sk), sk); + if (unlikely(hcrx->ccid3hcrx_state == TFRC_RSTATE_TERM)) + return; now = ktime_get_real(); - switch (hcrx->ccid3hcrx_state) { - case TFRC_RSTATE_NO_DATA: + switch (fbtype) { + case CCID3_FBACK_INITIAL: hcrx->ccid3hcrx_x_recv = 0; + hcrx->ccid3hcrx_pinv = ~0U; /* see RFC 4342, 8.5 */ break; - case TFRC_RSTATE_DATA: - delta = ktime_us_delta(now, - hcrx->ccid3hcrx_tstamp_last_feedback); - DCCP_BUG_ON(delta < 0); - hcrx->ccid3hcrx_x_recv = - scaled_div32(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 (hcrx->ccid3hcrx_x_recv > 0) + break; + /* fall through */ + case CCID3_FBACK_PERIODIC: + delta = ktime_us_delta(now, hcrx->ccid3hcrx_tstamp_last_feedback); + if (delta <= 0) + DCCP_BUG("delta (%ld) <= 0", (long)delta); + else + hcrx->ccid3hcrx_x_recv = + scaled_div32(hcrx->ccid3hcrx_bytes_recv, delta); break; - case TFRC_RSTATE_TERM: - DCCP_BUG("%s(%p) - Illegal state TERM", dccp_role(sk), sk); + default: return; } - packet = dccp_rx_hist_find_data_packet(&hcrx->ccid3hcrx_hist); - if (unlikely(packet == NULL)) { - DCCP_WARN("%s(%p), no data packet in history!\n", - dccp_role(sk), sk); - return; - } + ccid3_pr_debug("Interval %ldusec, X_recv=%u, 1/p=%u\n", (long)delta, + hcrx->ccid3hcrx_x_recv, hcrx->ccid3hcrx_pinv); hcrx->ccid3hcrx_tstamp_last_feedback = now; - hcrx->ccid3hcrx_ccval_last_counter = packet->dccphrx_ccval; + hcrx->ccid3hcrx_last_counter = dccp_hdr(skb)->dccph_ccval; hcrx->ccid3hcrx_bytes_recv = 0; - /* Elapsed time information [RFC 4340, 13.2] in units of 10 * usecs */ - delta = ktime_us_delta(now, packet->dccphrx_tstamp); - DCCP_BUG_ON(delta < 0); - hcrx->ccid3hcrx_elapsed_time = delta / 10; - - if (hcrx->ccid3hcrx_p == 0) - hcrx->ccid3hcrx_pinv = ~0U; /* see RFC 4342, 8.5 */ - else if (hcrx->ccid3hcrx_p > 1000000) { - DCCP_WARN("p (%u) > 100%%\n", hcrx->ccid3hcrx_p); - hcrx->ccid3hcrx_pinv = 1; /* use 100% in this case */ - } else - hcrx->ccid3hcrx_pinv = 1000000 / hcrx->ccid3hcrx_p; - dp->dccps_hc_rx_insert_options = 1; dccp_send_ack(sk); } @@ -770,7 +733,6 @@ static int ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb) return 0; hcrx = ccid3_hc_rx_sk(sk); - DCCP_SKB_CB(skb)->dccpd_ccval = hcrx->ccid3hcrx_ccval_last_counter; if (dccp_packet_without_ack(skb)) return 0; @@ -778,11 +740,7 @@ static int ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb) 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, + if (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))) @@ -791,180 +749,139 @@ static int ccid3_hc_rx_insert_options(struct sock *sk, struct sk_buff *skb) return 0; } -static int ccid3_hc_rx_detect_loss(struct sock *sk, - struct dccp_rx_hist_entry *packet) +/** ccid3_first_li - Implements [RFC 3448, 6.3.1] + * + * 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 *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; + u32 x_recv, p, delta; + u64 fval; - 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; + if (hcrx->ccid3hcrx_rtt == 0) { + DCCP_WARN("No RTT estimate available, using fallback RTT\n"); + hcrx->ccid3hcrx_rtt = DCCP_FALLBACK_RTT; } - - while (dccp_delta_seqno(hcrx->ccid3hcrx_seqno_nonloss, seqno) - > TFRC_RECV_NUM_LATE_LOSS) { - loss = 1; - dccp_li_update_li(sk, - &hcrx->ccid3hcrx_li_hist, - &hcrx->ccid3hcrx_hist, - hcrx->ccid3hcrx_tstamp_last_feedback, - hcrx->ccid3hcrx_s, - hcrx->ccid3hcrx_bytes_recv, - hcrx->ccid3hcrx_x_recv, - 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); + delta = ktime_to_us(net_timedelta(hcrx->ccid3hcrx_tstamp_last_feedback)); + x_recv = scaled_div32(hcrx->ccid3hcrx_bytes_recv, delta); + if (x_recv == 0) { /* would also trigger divide-by-zero */ + DCCP_WARN("X_recv==0\n"); + if ((x_recv = hcrx->ccid3hcrx_x_recv) == 0) { + DCCP_BUG("stored value of X_recv is zero"); + return ~0U; } } - /* 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; - } + fval = scaled_div(hcrx->ccid3hcrx_s, hcrx->ccid3hcrx_rtt); + fval = scaled_div32(fval, x_recv); + p = tfrc_calc_x_reverse_lookup(fval); -detect_out: - dccp_rx_hist_add_packet(ccid3_rx_hist, &hcrx->ccid3hcrx_hist, - &hcrx->ccid3hcrx_li_hist, packet, - hcrx->ccid3hcrx_seqno_nonloss); - return loss; + ccid3_pr_debug("%s(%p), receive rate=%u bytes/s, implied " + "loss rate=%u\n", dccp_role(sk), sk, x_recv, p); + + return p == 0 ? ~0U : scaled_div(1, p); } 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; - u32 p_prev, r_sample, rtt_prev; - int loss, payload_size; - ktime_t now; - - 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; - r_sample = dccp_timestamp() - opt_recv->dccpor_timestamp_echo; - rtt_prev = hcrx->ccid3hcrx_rtt; - r_sample = dccp_sample_rtt(sk, 10 * r_sample); + enum ccid3_fback_type do_feedback = CCID3_FBACK_NONE; + const u32 ndp = dccp_sk(sk)->dccps_options_received.dccpor_ndp; + const bool is_data_packet = dccp_data_packet(skb); + + if (unlikely(hcrx->ccid3hcrx_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); + hcrx->ccid3hcrx_s = payload; + /* + * Not necessary to update ccid3hcrx_bytes_recv here, + * since X_recv = 0 for the first feedback packet (cf. + * RFC 3448, 6.3) -- gerrit + */ + } + goto update_records; + } - 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(&hcrx->ccid3hcrx_hist, skb)) + return; /* done receiving */ - if (rtt_prev != hcrx->ccid3hcrx_rtt) - ccid3_pr_debug("%s(%p), New RTT=%uus, elapsed time=%u\n", - dccp_role(sk), 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 + */ + hcrx->ccid3hcrx_s = tfrc_ewma(hcrx->ccid3hcrx_s, payload, 9); + hcrx->ccid3hcrx_bytes_recv += payload; } - packet = dccp_rx_hist_entry_new(ccid3_rx_hist, opt_recv->dccpor_ndp, - skb, GFP_ATOMIC); - if (unlikely(packet == NULL)) { - DCCP_WARN("%s(%p), Not enough mem to add rx packet " - "to history, consider it lost!\n", dccp_role(sk), sk); - return; + /* + * Handle pending losses and otherwise check for new loss + */ + if (tfrc_rx_hist_loss_pending(&hcrx->ccid3hcrx_hist) && + tfrc_rx_handle_loss(&hcrx->ccid3hcrx_hist, + &hcrx->ccid3hcrx_li_hist, + skb, ndp, ccid3_first_li, sk) ) { + do_feedback = CCID3_FBACK_PARAM_CHANGE; + goto done_receiving; } - loss = ccid3_hc_rx_detect_loss(sk, packet); + if (tfrc_rx_hist_new_loss_indicated(&hcrx->ccid3hcrx_hist, skb, ndp)) + goto update_records; - if (DCCP_SKB_CB(skb)->dccpd_type == DCCP_PKT_ACK) - return; - - payload_size = skb->len - dccp_hdr(skb)->dccph_doff * 4; - ccid3_hc_rx_update_s(hcrx, payload_size); + /* + * 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(%p, state=%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 += payload_size; - if (loss) - break; + if (!tfrc_lh_is_initialised(&hcrx->ccid3hcrx_li_hist)) { + const u32 sample = tfrc_rx_hist_sample_rtt(&hcrx->ccid3hcrx_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) + hcrx->ccid3hcrx_rtt = tfrc_ewma(hcrx->ccid3hcrx_rtt, sample, 9); - now = ktime_get_real(); - if ((ktime_us_delta(now, hcrx->ccid3hcrx_tstamp_last_ack) - - (s64)hcrx->ccid3hcrx_rtt) >= 0) { - hcrx->ccid3hcrx_tstamp_last_ack = now; - ccid3_hc_rx_send_feedback(sk); - } - return; - case TFRC_RSTATE_TERM: - DCCP_BUG("%s(%p) - Illegal state TERM", dccp_role(sk), sk); - return; + } else if (tfrc_lh_update_i_mean(&hcrx->ccid3hcrx_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(%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); + /* + * Check if the periodic once-per-RTT feedback is due; RFC 4342, 10.3 + */ + if (SUB16(dccp_hdr(skb)->dccph_ccval, hcrx->ccid3hcrx_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 - DCCP_BUG("empty loss history"); +update_records: + tfrc_rx_hist_add_packet(&hcrx->ccid3hcrx_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 ccid3_hc_rx_sock *hcrx = ccid_priv(ccid); - ccid3_pr_debug("entry\n"); - hcrx->ccid3hcrx_state = TFRC_RSTATE_NO_DATA; - INIT_LIST_HEAD(&hcrx->ccid3hcrx_hist); - INIT_LIST_HEAD(&hcrx->ccid3hcrx_li_hist); - hcrx->ccid3hcrx_tstamp_last_feedback = - hcrx->ccid3hcrx_tstamp_last_ack = ktime_get_real(); - return 0; + tfrc_lh_init(&hcrx->ccid3hcrx_li_hist); + return tfrc_rx_hist_alloc(&hcrx->ccid3hcrx_hist); } static void ccid3_hc_rx_exit(struct sock *sk) @@ -973,11 +890,8 @@ static void ccid3_hc_rx_exit(struct sock *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(&hcrx->ccid3hcrx_li_hist); + tfrc_rx_hist_purge(&hcrx->ccid3hcrx_hist); + tfrc_lh_cleanup(&hcrx->ccid3hcrx_li_hist); } static void ccid3_hc_rx_get_info(struct sock *sk, struct tcp_info *info) @@ -998,6 +912,7 @@ 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; + struct tfrc_rx_info rx_info; const void *val; /* Listen socks doesn't have a private CCID block */ @@ -1007,10 +922,14 @@ static int ccid3_hc_rx_getsockopt(struct sock *sk, const int optname, int len, hcrx = ccid3_hc_rx_sk(sk); switch (optname) { case DCCP_SOCKOPT_CCID_RX_INFO: - if (len < sizeof(hcrx->ccid3hcrx_tfrc)) + if (len < sizeof(rx_info)) return -EINVAL; - len = sizeof(hcrx->ccid3hcrx_tfrc); - val = &hcrx->ccid3hcrx_tfrc; + rx_info.tfrcrx_x_recv = hcrx->ccid3hcrx_x_recv; + rx_info.tfrcrx_rtt = hcrx->ccid3hcrx_rtt; + rx_info.tfrcrx_p = hcrx->ccid3hcrx_pinv == 0 ? ~0U : + scaled_div(1, hcrx->ccid3hcrx_pinv); + len = sizeof(rx_info); + val = &rx_info; break; default: return -ENOPROTOOPT; @@ -1024,7 +943,7 @@ static int ccid3_hc_rx_getsockopt(struct sock *sk, const int optname, int len, static struct ccid_operations ccid3 = { .ccid_id = DCCPC_CCID3, - .ccid_name = "ccid3", + .ccid_name = "TCP-Friendly Rate Control", .ccid_owner = THIS_MODULE, .ccid_hc_tx_obj_size = sizeof(struct ccid3_hc_tx_sock), .ccid_hc_tx_init = ccid3_hc_tx_init, @@ -1051,44 +970,13 @@ 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; - - rc = ccid_register(&ccid3); - if (rc != 0) - goto out_free_tx; -out: - return rc; - -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; + return ccid_register(&ccid3); } 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; - } } module_exit(ccid3_module_exit); diff --git a/net/dccp/ccids/ccid3.h b/net/dccp/ccids/ccid3.h index 0cdc982cfe47..49ca32bd7e79 100644 --- a/net/dccp/ccids/ccid3.h +++ b/net/dccp/ccids/ccid3.h @@ -1,7 +1,8 @@ /* * 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 * @@ -40,6 +41,7 @@ #include <linux/list.h> #include <linux/types.h> #include <linux/tfrc.h> +#include "lib/tfrc.h" #include "../ccid.h" /* Two seconds as per RFC 3448 4.2 */ @@ -88,7 +90,6 @@ enum ccid3_hc_tx_states { * @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 - Flag indicating that sender is idling * @ccid3hctx_t_ld - Time last doubled during slow start * @ccid3hctx_t_nom - Nominal send time of next packet * @ccid3hctx_delta - Send timer delta (RFC 3448, 4.6) in usecs @@ -107,13 +108,12 @@ struct ccid3_hc_tx_sock { u16 ccid3hctx_s; enum ccid3_hc_tx_states ccid3hctx_state:8; u8 ccid3hctx_last_win_count; - u8 ccid3hctx_idle; ktime_t ccid3hctx_t_last_win_count; struct timer_list ccid3hctx_no_feedback_timer; ktime_t ccid3hctx_t_ld; ktime_t ccid3hctx_t_nom; u32 ccid3hctx_delta; - struct list_head ccid3hctx_hist; + struct tfrc_tx_hist_entry *ccid3hctx_hist; struct ccid3_options_received ccid3hctx_options_received; }; @@ -135,37 +135,30 @@ enum ccid3_hc_rx_states { * * @ccid3hcrx_x_recv - Receiver estimate of send rate (RFC 3448 4.3) * @ccid3hcrx_rtt - Receiver estimate of rtt (non-standard) - * @ccid3hcrx_p - current loss event rate (RFC 3448 5.4) - * @ccid3hcrx_seqno_nonloss - Last received non-loss sequence number - * @ccid3hcrx_ccval_nonloss - Last received non-loss Window CCVal - * @ccid3hcrx_ccval_last_counter - Tracks window counter (RFC 4342, 8.1) - * @ccid3hcrx_state - receiver state, one of %ccid3_hc_rx_states + * @ccid3hcrx_p - Current loss event rate (RFC 3448 5.4) + * @ccid3hcrx_last_counter - Tracks window counter (RFC 4342, 8.1) + * @ccid3hcrx_state - Receiver state, one of %ccid3_hc_rx_states * @ccid3hcrx_bytes_recv - Total sum of DCCP payload bytes + * @ccid3hcrx_x_recv - Receiver estimate of send rate (RFC 3448, sec. 4.3) + * @ccid3hcrx_rtt - Receiver estimate of RTT * @ccid3hcrx_tstamp_last_feedback - Time at which last feedback was sent * @ccid3hcrx_tstamp_last_ack - Time at which last feedback was sent - * @ccid3hcrx_hist - Packet history - * @ccid3hcrx_li_hist - Loss Interval History + * @ccid3hcrx_hist - Packet history (loss detection + RTT sampling) + * @ccid3hcrx_li_hist - Loss Interval database * @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 */ 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_ccval_last_counter:4; + u8 ccid3hcrx_last_counter:4; enum ccid3_hc_rx_states ccid3hcrx_state:8; u32 ccid3hcrx_bytes_recv; + u32 ccid3hcrx_x_recv; + u32 ccid3hcrx_rtt; ktime_t ccid3hcrx_tstamp_last_feedback; - ktime_t ccid3hcrx_tstamp_last_ack; - struct list_head ccid3hcrx_hist; - struct list_head ccid3hcrx_li_hist; + struct tfrc_rx_hist ccid3hcrx_hist; + struct tfrc_loss_hist ccid3hcrx_li_hist; u16 ccid3hcrx_s; - u32 ccid3hcrx_pinv; - u32 ccid3hcrx_elapsed_time; +#define ccid3hcrx_pinv ccid3hcrx_li_hist.i_mean }; static inline struct ccid3_hc_rx_sock *ccid3_hc_rx_sk(const struct sock *sk) diff --git a/net/dccp/ccids/lib/Makefile b/net/dccp/ccids/lib/Makefile index 5f940a6cbaca..68c93e3d89dc 100644 --- a/net/dccp/ccids/lib/Makefile +++ b/net/dccp/ccids/lib/Makefile @@ -1,3 +1,3 @@ obj-$(CONFIG_IP_DCCP_TFRC_LIB) += dccp_tfrc_lib.o -dccp_tfrc_lib-y := loss_interval.o packet_history.o tfrc_equation.o +dccp_tfrc_lib-y := tfrc.o tfrc_equation.o packet_history.o loss_interval.o diff --git a/net/dccp/ccids/lib/loss_interval.c b/net/dccp/ccids/lib/loss_interval.c index d26b88dbbb45..849e181e698f 100644 --- a/net/dccp/ccids/lib/loss_interval.c +++ b/net/dccp/ccids/lib/loss_interval.c @@ -1,6 +1,7 @@ /* * net/dccp/ccids/lib/loss_interval.c * + * 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> @@ -10,285 +11,176 @@ * 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 "../../dccp.h" -#include "loss_interval.h" -#include "packet_history.h" #include "tfrc.h" -#define DCCP_LI_HIST_IVAL_F_LENGTH 8 - -struct dccp_li_hist_entry { - struct list_head dccplih_node; - u64 dccplih_seqno:48, - dccplih_win_count:4; - u32 dccplih_interval; -}; +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 }; -static struct kmem_cache *dccp_li_cachep __read_mostly; - -static inline struct dccp_li_hist_entry *dccp_li_hist_entry_new(const gfp_t prio) +/* implements LIFO semantics on the array */ +static inline u8 LIH_INDEX(const u8 ctr) { - return kmem_cache_alloc(dccp_li_cachep, prio); + return (LIH_SIZE - 1 - (ctr % LIH_SIZE)); } -static inline void dccp_li_hist_entry_delete(struct dccp_li_hist_entry *entry) +/* 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) { - if (entry != NULL) - kmem_cache_free(dccp_li_cachep, entry); + return lh->counter ? lh->ring[LIH_INDEX(lh->counter - 1)] : NULL; } -void dccp_li_hist_purge(struct list_head *list) +/* 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) { - struct dccp_li_hist_entry *entry, *next; - - list_for_each_entry_safe(entry, next, list, dccplih_node) { - list_del_init(&entry->dccplih_node); - kmem_cache_free(dccp_li_cachep, entry); - } + BUG_ON(i >= lh->counter); + return lh->ring[LIH_INDEX(lh->counter - i - 1)]->li_length; } -EXPORT_SYMBOL_GPL(dccp_li_hist_purge); - -/* 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. + * On-demand allocation and de-allocation of entries */ -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) +static struct tfrc_loss_interval *tfrc_lh_demand_next(struct tfrc_loss_hist *lh) { - 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 != ~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 > DCCP_LI_HIST_IVAL_F_LENGTH) - break; - } - - if (i != DCCP_LI_HIST_IVAL_F_LENGTH) - return 0; - - i_tot = max(i_tot0, i_tot1); - - if (!w_tot) { - DCCP_WARN("w_tot = 0\n"); - return 1; - } - - return i_tot / w_tot; + 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_calc_i_mean); - -static int dccp_li_hist_interval_new(struct list_head *list, - const u64 seq_loss, const u8 win_loss) +void tfrc_lh_cleanup(struct tfrc_loss_hist *lh) { - 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(GFP_ATOMIC); - if (entry == NULL) { - dccp_li_hist_purge(list); - DCCP_BUG("loss interval list entry is NULL"); - return 0; + 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; } - entry->dccplih_interval = ~0; - list_add(&entry->dccplih_node, list); - } - - entry->dccplih_seqno = seq_loss; - entry->dccplih_win_count = win_loss; - return 1; } +EXPORT_SYMBOL_GPL(tfrc_lh_cleanup); -/* calculate first loss interval - * - * returns estimated loss interval in usecs */ -static u32 dccp_li_calc_first_li(struct sock *sk, - struct list_head *hist_list, - ktime_t last_feedback, - u16 s, u32 bytes_recv, - u32 previous_x_recv) +static void tfrc_lh_calc_i_mean(struct tfrc_loss_hist *lh) { - struct dccp_rx_hist_entry *entry, *next, *tail = NULL; - u32 x_recv, p; - suseconds_t rtt, delta; - ktime_t tstamp = ktime_set(0, 0); - int interval = 0; - int win_count = 0; - int step = 0; - u64 fval; + 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, hist_list, dccphrx_node) { - if (dccp_rx_hist_entry_data_packet(entry)) { - tail = entry; + for (i=0; i <= k; i++) { + i_i = tfrc_lh_get_interval(lh, i); - 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; - } + 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]; } - if (unlikely(step == 0)) { - DCCP_WARN("%s(%p), packet history has no data packets!\n", - dccp_role(sk), sk); - return ~0; - } - - if (unlikely(interval == 0)) { - DCCP_WARN("%s(%p), Could not find a win_count interval > 0. " - "Defaulting to 1\n", dccp_role(sk), sk); - interval = 1; - } -found: - if (!tail) { - DCCP_CRIT("tail is null\n"); - return ~0; - } - - delta = ktime_us_delta(tstamp, tail->dccphrx_tstamp); - DCCP_BUG_ON(delta < 0); + BUG_ON(w_tot == 0); + lh->i_mean = max(i_tot0, i_tot1) / w_tot; +} - rtt = delta * 4 / interval; - dccp_pr_debug("%s(%p), approximated RTT to %dus\n", - dccp_role(sk), sk, (int)rtt); +/** + * 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 + */ +u8 tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *skb) +{ + struct tfrc_loss_interval *cur = tfrc_lh_peek(lh); + u32 old_i_mean = lh->i_mean; + s64 length; - /* - * 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 [RFC 3448, 6.3.1]. - */ - if (rtt == 0) { /* would result in divide-by-zero */ - DCCP_WARN("RTT==0\n"); - return ~0; - } + if (cur == NULL) /* not initialised */ + return 0; - delta = ktime_us_delta(ktime_get_real(), last_feedback); - DCCP_BUG_ON(delta <= 0); + length = dccp_delta_seqno(cur->li_seqno, DCCP_SKB_CB(skb)->dccpd_seq); - x_recv = scaled_div32(bytes_recv, delta); - if (x_recv == 0) { /* would also trigger divide-by-zero */ - DCCP_WARN("X_recv==0\n"); - if (previous_x_recv == 0) { - DCCP_BUG("stored value of X_recv is zero"); - return ~0; - } - x_recv = previous_x_recv; - } + if (length - cur->li_length <= 0) /* duplicate or reordered */ + return 0; - fval = scaled_div(s, rtt); - fval = scaled_div32(fval, x_recv); - p = tfrc_calc_x_reverse_lookup(fval); + 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; - dccp_pr_debug("%s(%p), receive rate=%u bytes/s, implied " - "loss rate=%u\n", dccp_role(sk), sk, x_recv, p); + cur->li_length = length; + tfrc_lh_calc_i_mean(lh); - if (p == 0) - return ~0; - else - return 1000000 / p; + return (lh->i_mean < old_i_mean); } +EXPORT_SYMBOL_GPL(tfrc_lh_update_i_mean); -void dccp_li_update_li(struct sock *sk, - struct list_head *li_hist_list, - struct list_head *hist_list, - ktime_t last_feedback, u16 s, u32 bytes_recv, - u32 previous_x_recv, u64 seq_loss, u8 win_loss) +/* 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) { - struct dccp_li_hist_entry *head; - u64 seq_temp; - - if (list_empty(li_hist_list)) { - if (!dccp_li_hist_interval_new(li_hist_list, seq_loss, - win_loss)) - return; - - head = list_entry(li_hist_list->next, struct dccp_li_hist_entry, - dccplih_node); - head->dccplih_interval = dccp_li_calc_first_li(sk, hist_list, - last_feedback, - s, bytes_recv, - previous_x_recv); - } else { - struct dccp_li_hist_entry *entry; - struct list_head *tail; + 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); +} - head = list_entry(li_hist_list->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 */ +/** 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 tfrc_loss_interval *cur = tfrc_lh_peek(lh), *new; - /* new loss event detected */ - /* calculate last interval length */ - seq_temp = dccp_delta_seqno(head->dccplih_seqno, seq_loss); - entry = dccp_li_hist_entry_new(GFP_ATOMIC); + if (cur != NULL && !tfrc_lh_is_new_loss(cur, tfrc_rx_hist_loss_prev(rh))) + return 0; - if (entry == NULL) { - DCCP_BUG("out of memory - can not allocate entry"); - return; - } + new = tfrc_lh_demand_next(lh); + if (unlikely(new == NULL)) { + DCCP_CRIT("Cannot allocate/add loss record."); + return 0; + } - list_add(&entry->dccplih_node, li_hist_list); + 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; - tail = li_hist_list->prev; - list_del(tail); - kmem_cache_free(dccp_li_cachep, tail); + 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); + if (lh->counter > (2*LIH_SIZE)) + lh->counter -= LIH_SIZE; - /* Create the newest interval */ - entry->dccplih_seqno = seq_loss; - entry->dccplih_interval = seq_temp; - entry->dccplih_win_count = win_loss; + tfrc_lh_calc_i_mean(lh); } + return 1; } +EXPORT_SYMBOL_GPL(tfrc_lh_interval_add); -EXPORT_SYMBOL_GPL(dccp_li_update_li); - -static __init int dccp_li_init(void) +int __init tfrc_li_init(void) { - dccp_li_cachep = kmem_cache_create("dccp_li_hist", - sizeof(struct dccp_li_hist_entry), - 0, SLAB_HWCACHE_ALIGN, NULL); - return dccp_li_cachep == NULL ? -ENOBUFS : 0; + 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; } -static __exit void dccp_li_exit(void) +void tfrc_li_exit(void) { - kmem_cache_destroy(dccp_li_cachep); + if (tfrc_lh_slab != NULL) { + kmem_cache_destroy(tfrc_lh_slab); + tfrc_lh_slab = NULL; + } } - -module_init(dccp_li_init); -module_exit(dccp_li_exit); diff --git a/net/dccp/ccids/lib/loss_interval.h b/net/dccp/ccids/lib/loss_interval.h index 27bee92dae13..246018a3b269 100644 --- a/net/dccp/ccids/lib/loss_interval.h +++ b/net/dccp/ccids/lib/loss_interval.h @@ -3,6 +3,7 @@ /* * net/dccp/ccids/lib/loss_interval.h * + * 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> @@ -12,18 +13,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> + +/* + * 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) + +/** + * 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; +}; + +/** + * 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 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 lh->counter > 0; +} + +static inline u8 tfrc_lh_length(struct tfrc_loss_hist *lh) +{ + return min(lh->counter, (u8)LIH_SIZE); +} -extern void dccp_li_hist_purge(struct list_head *list); +struct tfrc_rx_hist; -extern u32 dccp_li_hist_calc_i_mean(struct list_head *list); +extern int tfrc_lh_interval_add(struct tfrc_loss_hist *, struct tfrc_rx_hist *, + u32 (*first_li)(struct sock *), struct sock *); +extern u8 tfrc_lh_update_i_mean(struct tfrc_loss_hist *lh, struct sk_buff *); +extern void tfrc_lh_cleanup(struct tfrc_loss_hist *lh); -extern void dccp_li_update_li(struct sock *sk, - struct list_head *li_hist_list, - struct list_head *hist_list, - ktime_t last_feedback, u16 s, - u32 bytes_recv, u32 previous_x_recv, - u64 seq_loss, 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 34c4f6047724..20af1a693427 100644 --- a/net/dccp/ccids/lib/packet_history.c +++ b/net/dccp/ccids/lib/packet_history.c @@ -1,7 +1,8 @@ /* * 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,267 +35,465 @@ * 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" + +/** + * 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; +}; /* - * Transmitter History Routines + * Transmitter History Routines */ -struct dccp_tx_hist *dccp_tx_hist_new(const char *name) +static struct kmem_cache *tfrc_tx_hist_slab; + +int __init tfrc_tx_packet_history_init(void) { - 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); - 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; + 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; } -EXPORT_SYMBOL_GPL(dccp_tx_hist_new); - -void dccp_tx_hist_delete(struct dccp_tx_hist *hist) +void tfrc_tx_packet_history_exit(void) { - const char* name = kmem_cache_name(hist->dccptxh_slab); - - kmem_cache_destroy(hist->dccptxh_slab); - kfree(name); - kfree(hist); + if (tfrc_tx_hist_slab != NULL) { + kmem_cache_destroy(tfrc_tx_hist_slab); + tfrc_tx_hist_slab = NULL; + } } -EXPORT_SYMBOL_GPL(dccp_tx_hist_delete); - -struct dccp_tx_hist_entry * - dccp_tx_hist_find_entry(const struct list_head *list, const u64 seq) +static struct tfrc_tx_hist_entry * + tfrc_tx_hist_find_entry(struct tfrc_tx_hist_entry *head, u64 seqno) { - struct dccp_tx_hist_entry *packet = NULL, *entry; - - list_for_each_entry(entry, list, dccphtx_node) - if (entry->dccphtx_seqno == seq) { - packet = entry; - break; - } + while (head != NULL && head->seqno != seqno) + head = head->next; - return packet; + return head; } -EXPORT_SYMBOL_GPL(dccp_tx_hist_find_entry); +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; +} +EXPORT_SYMBOL_GPL(tfrc_tx_hist_add); -void dccp_tx_hist_purge(struct dccp_tx_hist *hist, struct list_head *list) +void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry **headp) { - struct dccp_tx_hist_entry *entry, *next; + struct tfrc_tx_hist_entry *head = *headp; + + while (head != NULL) { + struct tfrc_tx_hist_entry *next = head->next; - list_for_each_entry_safe(entry, next, list, dccphtx_node) { - list_del_init(&entry->dccphtx_node); - dccp_tx_hist_entry_delete(hist, entry); + kmem_cache_free(tfrc_tx_hist_slab, head); + head = next; } -} -EXPORT_SYMBOL_GPL(dccp_tx_hist_purge); + *headp = NULL; +} +EXPORT_SYMBOL_GPL(tfrc_tx_hist_purge); -void dccp_tx_hist_purge_older(struct dccp_tx_hist *hist, - struct list_head *list, - struct dccp_tx_hist_entry *packet) +u32 tfrc_tx_hist_rtt(struct tfrc_tx_hist_entry *head, const u64 seqno, + const ktime_t now) { - struct dccp_tx_hist_entry *next; + u32 rtt = 0; + struct tfrc_tx_hist_entry *packet = tfrc_tx_hist_find_entry(head, seqno); - list_for_each_entry_safe_continue(packet, next, list, dccphtx_node) { - list_del_init(&packet->dccphtx_node); - dccp_tx_hist_entry_delete(hist, packet); + if (packet != NULL) { + rtt = ktime_us_delta(now, packet->stamp); + /* + * Garbage-collect older (irrelevant) entries: + */ + tfrc_tx_hist_purge(&packet->next); } + + return rtt; } +EXPORT_SYMBOL_GPL(tfrc_tx_hist_rtt); -EXPORT_SYMBOL_GPL(dccp_tx_hist_purge_older); /* * Receiver History Routines */ -struct dccp_rx_hist *dccp_rx_hist_new(const char *name) +static struct kmem_cache *tfrc_rx_hist_slab; + +int __init tfrc_rx_packet_history_init(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); - 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; + 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; } -EXPORT_SYMBOL_GPL(dccp_rx_hist_new); +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; + } +} -void dccp_rx_hist_delete(struct dccp_rx_hist *hist) +static inline void tfrc_rx_hist_entry_from_skb(struct tfrc_rx_hist_entry *entry, + const struct sk_buff *skb, + const u32 ndp) { - const char* name = kmem_cache_name(hist->dccprxh_slab); + const struct dccp_hdr *dh = dccp_hdr(skb); - kmem_cache_destroy(hist->dccprxh_slab); - kfree(name); - kfree(hist); + 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(); } -EXPORT_SYMBOL_GPL(dccp_rx_hist_delete); +void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, + const struct sk_buff *skb, + const u32 ndp) +{ + struct tfrc_rx_hist_entry *entry = tfrc_rx_hist_last_rcv(h); + + tfrc_rx_hist_entry_from_skb(entry, skb, ndp); +} +EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet); -int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq, - u8 *ccval) +/* has the packet contained in skb been seen before? */ +int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb) { - struct dccp_rx_hist_entry *packet = NULL, *entry; + const u64 seq = DCCP_SKB_CB(skb)->dccpd_seq; + int i; - list_for_each_entry(entry, list, dccphrx_node) - if (entry->dccphrx_seqno == seq) { - packet = entry; - break; - } + if (dccp_delta_seqno(tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, seq) <= 0) + return 1; - if (packet) - *ccval = packet->dccphrx_ccval; + for (i = 1; i <= h->loss_count; i++) + if (tfrc_rx_hist_entry(h, i)->tfrchrx_seqno == seq) + return 1; - return packet != NULL; + return 0; } +EXPORT_SYMBOL_GPL(tfrc_rx_hist_duplicate); -EXPORT_SYMBOL_GPL(dccp_rx_hist_find_entry); -struct dccp_rx_hist_entry * - dccp_rx_hist_find_data_packet(const struct list_head *list) +static void tfrc_rx_hist_swap(struct tfrc_rx_hist *h, const u8 a, const u8 b) { - struct dccp_rx_hist_entry *entry, *packet = NULL; - - list_for_each_entry(entry, list, dccphrx_node) - if (entry->dccphrx_type == DCCP_PKT_DATA || - entry->dccphrx_type == DCCP_PKT_DATAACK) { - packet = entry; - break; - } + 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]; - return packet; + h->ring[idx_a] = h->ring[idx_b]; + h->ring[idx_b] = tmp; } -EXPORT_SYMBOL_GPL(dccp_rx_hist_find_data_packet); +/* + * 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 __after_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 hist_entry. + */ +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; + int n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp, + d12 = dccp_delta_seqno(s1, s2), d2; + + if (d12 > 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 */ + d2 = dccp_delta_seqno(s0, s2); -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) + if (d2 == 1 || n2 >= d2) { /* S2 is direct successor of S0 */ + int d21 = -d12; + + if (d21 == 1 || n1 >= d21) { + /* 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 { /* hole between S0 and S2 */ + /* + * Reorder history to insert S2 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, n2); + h->loss_count = 2; + } +} + +/* 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_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 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno, + s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno, + s3 = DCCP_SKB_CB(skb)->dccpd_seq; + int n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp, + d23 = dccp_delta_seqno(s2, s3), d13, d3, d31; + + if (d23 > 0) { /* S2 < S3 */ + h->loss_count = 3; + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 3), skb, n3); + return 1; + } + + /* S3 < S2 */ + d13 = dccp_delta_seqno(s1, s3); + + if (d13 > 0) { /* - * We have no loss interval history so we need at least one - * rtt:s of data packets to approximate rtt. + * The sequence number order is S1, S3, S2 + * Reorder history to insert entry between S1 and S2 */ - 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, 2, 3); + tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 2), skb, n3); + h->loss_count = 3; + return 1; + } + + /* S0 < S3 < S1 */ + d31 = -d13; + d3 = dccp_delta_seqno(s0, s3); + + if (d3 == 1 || n3 >= d3) { /* S3 is a successor of S0 */ + + if (d31 == 1 || n1 >= d31) { + /* hole between S0 and S1 filled by S3 */ + int d2 = dccp_delta_seqno(s1, s2), + n2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_ndp; + + if (d2 == 1 || n2 >= d2) { + /* 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); + + return 0; + } + + /* + * The remaining case: S3 is not a successor of S0. + * Sequence order is S0, S3, S1, S2; reorder to insert 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; +} + +/* return the signed modulo-2^48 sequence number distance from entry e1 to e2 */ +static s64 tfrc_rx_hist_delta_seqno(struct tfrc_rx_hist *h, u8 e1, u8 e2) +{ + DCCP_BUG_ON(e1 > h->loss_count || e2 > h->loss_count); + + return dccp_delta_seqno(tfrc_rx_hist_entry(h, e1)->tfrchrx_seqno, + tfrc_rx_hist_entry(h, e2)->tfrchrx_seqno); +} + +/* recycle RX history records to continue loss detection if necessary */ +static void __three_after_loss(struct tfrc_rx_hist *h) +{ + /* + * The distance between S0 and S1 is always greater than 1 and the NDP + * count of S1 is smaller than this distance. Otherwise there would + * have been no loss. Hence it is only necessary to see whether there + * are further missing data packets between S1/S2 and S2/S3. + */ + int d2 = tfrc_rx_hist_delta_seqno(h, 1, 2), + d3 = tfrc_rx_hist_delta_seqno(h, 2, 3), + n2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_ndp, + n3 = tfrc_rx_hist_entry(h, 3)->tfrchrx_ndp; + + if (d2 == 1 || n2 >= d2) { /* S2 is successor to S1 */ + + if (d3 == 1 || n3 >= d3) { + /* S3 is successor of S2: 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; } + + } else { /* gap between S1 and S2 */ + h->loss_start = tfrc_rx_hist_index(h, 1); + h->loss_count = 2; } } -EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet); +/** + * 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. + */ +int tfrc_rx_handle_loss(struct tfrc_rx_hist *h, + struct tfrc_loss_hist *lh, + struct sk_buff *skb, u32 ndp, + u32 (*calc_first_li)(struct sock *), struct sock *sk) +{ + int is_new_loss = 0; -void dccp_rx_hist_purge(struct dccp_rx_hist *hist, struct list_head *list) + 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; +} +EXPORT_SYMBOL_GPL(tfrc_rx_handle_loss); + +int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h) { - struct dccp_rx_hist_entry *entry, *next; + int i; + + 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; + } + + h->loss_count = h->loss_start = 0; + return 0; - list_for_each_entry_safe(entry, next, list, dccphrx_node) { - list_del_init(&entry->dccphrx_node); - kmem_cache_free(hist->dccprxh_slab, entry); +out_free: + while (i-- != 0) { + kmem_cache_free(tfrc_rx_hist_slab, h->ring[i]); + h->ring[i] = NULL; } + return -ENOBUFS; } +EXPORT_SYMBOL_GPL(tfrc_rx_hist_alloc); + +void tfrc_rx_hist_purge(struct tfrc_rx_hist *h) +{ + int i; -EXPORT_SYMBOL_GPL(dccp_rx_hist_purge); + 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; + } +} +EXPORT_SYMBOL_GPL(tfrc_rx_hist_purge); +/** + * 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]; +} -MODULE_AUTHOR("Ian McDonald <ian.mcdonald@jandi.co.nz>, " - "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>"); -MODULE_DESCRIPTION("DCCP TFRC library"); -MODULE_LICENSE("GPL"); +/** + * 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]; +} + +/** + * 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) +{ + 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; + } + + } 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; + } + + if (unlikely(sample > DCCP_SANE_RTT_MAX)) { + DCCP_WARN("RTT sample %u too large, using max\n", sample); + sample = DCCP_SANE_RTT_MAX; + } + + h->rtt_sample_prev = 0; /* use current entry as next reference */ +keep_ref_for_next_time: + + return sample; +} +EXPORT_SYMBOL_GPL(tfrc_rx_hist_sample_rtt); diff --git a/net/dccp/ccids/lib/packet_history.h b/net/dccp/ccids/lib/packet_history.h index 032bb61c6e39..c7eeda49cb20 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 @@ -37,165 +36,128 @@ #ifndef _DCCP_PKT_HIST_ #define _DCCP_PKT_HIST_ -#include <linux/ktime.h> #include <linux/list.h> #include <linux/slab.h> +#include "tfrc.h" -#include "../../dccp.h" +struct tfrc_tx_hist_entry; -/* Number of later packets received before one is considered lost */ -#define TFRC_RECV_NUM_LATE_LOSS 3 +extern int tfrc_tx_hist_add(struct tfrc_tx_hist_entry **headp, u64 seqno); +extern void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry **headp); +extern u32 tfrc_tx_hist_rtt(struct tfrc_tx_hist_entry *head, + const u64 seqno, const ktime_t now); -#define TFRC_WIN_COUNT_PER_RTT 4 -#define TFRC_WIN_COUNT_LIMIT 16 +/* Subtraction a-b modulo-16, respects circular wrap-around */ +#define SUB16(a, b) (((a) + 16 - (b)) & 0xF) -/* - * Transmitter History data structures and declarations +/* Number of packets to wait after a missing packet (RFC 4342, 6.1) */ +#define TFRC_NDUPACK 3 + +/** + * 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 dccp_tx_hist_entry { - struct list_head dccphtx_node; - u64 dccphtx_seqno:48, - dccphtx_sent:1; - u32 dccphtx_rtt; - ktime_t dccphtx_tstamp; +struct tfrc_rx_hist_entry { + u64 tfrchrx_seqno:48, + tfrchrx_ccval:4, + tfrchrx_type:4; + u32 tfrchrx_ndp; /* In fact it is from 8 to 24 bits */ + ktime_t tfrchrx_tstamp; }; -struct dccp_tx_hist { - struct kmem_cache *dccptxh_slab; +/** + * 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 }; -extern struct dccp_tx_hist *dccp_tx_hist_new(const char *name); -extern void dccp_tx_hist_delete(struct dccp_tx_hist *hist); - -static inline struct dccp_tx_hist_entry * - dccp_tx_hist_entry_new(struct dccp_tx_hist *hist, - const gfp_t prio) +/** + * 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 *entry = kmem_cache_alloc(hist->dccptxh_slab, - prio); - - if (entry != NULL) - entry->dccphtx_sent = 0; - - return entry; + return (h->loss_start + n) & TFRC_NDUPACK; } -static inline struct dccp_tx_hist_entry * - dccp_tx_hist_head(struct list_head *list) +/** + * 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_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->ring[tfrc_rx_hist_index(h, h->loss_count)]; } -extern struct dccp_tx_hist_entry * - dccp_tx_hist_find_entry(const struct list_head *list, - const u64 seq); - -static inline void dccp_tx_hist_add_entry(struct list_head *list, - struct dccp_tx_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) { - list_add(&entry->dccphtx_node, list); + return h->ring[tfrc_rx_hist_index(h, n)]; } -static inline void dccp_tx_hist_entry_delete(struct dccp_tx_hist *hist, - struct dccp_tx_hist_entry *entry) +/** + * 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) { - if (entry != NULL) - kmem_cache_free(hist->dccptxh_slab, entry); + return h->ring[h->loss_start]; } -extern void dccp_tx_hist_purge(struct dccp_tx_hist *hist, - struct list_head *list); - -extern void dccp_tx_hist_purge_older(struct dccp_tx_hist *hist, - struct list_head *list, - struct dccp_tx_hist_entry *next); - -/* - * Receiver History data structures and declarations - */ -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 */ - ktime_t dccphrx_tstamp; -}; - -struct dccp_rx_hist { - struct kmem_cache *dccprxh_slab; -}; - -extern struct dccp_rx_hist *dccp_rx_hist_new(const char *name); -extern void dccp_rx_hist_delete(struct dccp_rx_hist *hist); - -static inline struct dccp_rx_hist_entry * - dccp_rx_hist_entry_new(struct dccp_rx_hist *hist, - const u32 ndp, - const struct sk_buff *skb, - const gfp_t prio) +/* initialise loss detection and disable RTT sampling */ +static inline void tfrc_rx_hist_loss_indicated(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; - entry->dccphrx_tstamp = ktime_get_real(); - } - - return entry; + h->loss_count = 1; } -static inline struct dccp_rx_hist_entry * - dccp_rx_hist_head(struct list_head *list) +/* indicate whether previously a packet was detected missing */ +static inline int tfrc_rx_hist_loss_pending(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->loss_count; } -extern int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq, - u8 *ccval); -extern struct dccp_rx_hist_entry * - dccp_rx_hist_find_data_packet(const struct list_head *list); - -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); - -static inline void dccp_rx_hist_entry_delete(struct dccp_rx_hist *hist, - struct dccp_rx_hist_entry *entry) +/* any data packets missing between last reception and skb ? */ +static inline int tfrc_rx_hist_new_loss_indicated(struct tfrc_rx_hist *h, + const struct sk_buff *skb, + u32 ndp) { - if (entry != NULL) - kmem_cache_free(hist->dccprxh_slab, entry); -} + int delta = dccp_delta_seqno(tfrc_rx_hist_last_rcv(h)->tfrchrx_seqno, + DCCP_SKB_CB(skb)->dccpd_seq); -extern void dccp_rx_hist_purge(struct dccp_rx_hist *hist, - struct list_head *list); + if (delta > 1 && ndp < delta) + tfrc_rx_hist_loss_indicated(h); -static inline int - dccp_rx_hist_entry_data_packet(const struct dccp_rx_hist_entry *entry) -{ - return entry->dccphrx_type == DCCP_PKT_DATA || - entry->dccphrx_type == DCCP_PKT_DATAACK; + return tfrc_rx_hist_loss_pending(h); } -extern u64 dccp_rx_hist_detect_loss(struct list_head *rx_list, - struct list_head *li_list, u8 *win_loss); +extern void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, + const struct sk_buff *skb, const u32 ndp); + +extern int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb); + +struct tfrc_loss_hist; +extern int tfrc_rx_handle_loss(struct tfrc_rx_hist *h, + struct tfrc_loss_hist *lh, + struct sk_buff *skb, u32 ndp, + u32 (*first_li)(struct sock *sk), + struct sock *sk); +extern u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, + const struct sk_buff *skb); +extern int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h); +extern 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 000000000000..d1dfbb8de64c --- /dev/null +++ b/net/dccp/ccids/lib/tfrc.c @@ -0,0 +1,63 @@ +/* + * TFRC: main module holding the pieces of the TFRC library together + * + * Copyright (c) 2007 The University of Aberdeen, Scotland, UK + * Copyright (c) 2007 Arnaldo Carvalho de Melo <acme@redhat.com> + */ +#include <linux/module.h> +#include <linux/moduleparam.h> +#include "tfrc.h" + +#ifdef CONFIG_IP_DCCP_TFRC_DEBUG +int tfrc_debug; +module_param(tfrc_debug, bool, 0444); +MODULE_PARM_DESC(tfrc_debug, "Enable debug messages"); +#endif + +extern int tfrc_tx_packet_history_init(void); +extern void tfrc_tx_packet_history_exit(void); +extern int tfrc_rx_packet_history_init(void); +extern void tfrc_rx_packet_history_exit(void); + +extern int tfrc_li_init(void); +extern void tfrc_li_exit(void); + +static int __init tfrc_module_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; +} + +static void __exit tfrc_module_exit(void) +{ + tfrc_rx_packet_history_exit(); + tfrc_tx_packet_history_exit(); + tfrc_li_exit(); +} + +module_init(tfrc_module_init); +module_exit(tfrc_module_exit); + +MODULE_AUTHOR("Gerrit Renker <gerrit@erg.abdn.ac.uk>, " + "Ian McDonald <ian.mcdonald@jandi.co.nz>, " + "Arnaldo Carvalho de Melo <acme@redhat.com>"); +MODULE_DESCRIPTION("DCCP TFRC library"); +MODULE_LICENSE("GPL"); diff --git a/net/dccp/ccids/lib/tfrc.h b/net/dccp/ccids/lib/tfrc.h index faf5f7e219e3..1fb1187bbf1c 100644 --- a/net/dccp/ccids/lib/tfrc.h +++ b/net/dccp/ccids/lib/tfrc.h @@ -3,10 +3,11 @@ /* * 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 @@ -15,6 +16,17 @@ */ #include <linux/types.h> #include <asm/div64.h> +#include "../../dccp.h" +/* internal includes that this module exports: */ +#include "loss_interval.h" +#include "packet_history.h" + +#ifdef CONFIG_IP_DCCP_TFRC_DEBUG +extern int 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, u32 b) @@ -37,6 +49,15 @@ static inline u32 scaled_div32(u64 a, u32 b) 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; +} + extern u32 tfrc_calc_x(u16 s, u32 R, u32 p); extern u32 tfrc_calc_x_reverse_lookup(u32 fvalue); diff --git a/net/dccp/dccp.h b/net/dccp/dccp.h index ee97950d77d1..ebe59d98721a 100644 --- a/net/dccp/dccp.h +++ b/net/dccp/dccp.h @@ -72,11 +72,21 @@ extern void dccp_time_wait(struct sock *sk, int state, int timeo); /* RFC 1122, 4.2.3.1 initial RTO value */ #define DCCP_TIMEOUT_INIT ((unsigned)(3 * HZ)) -#define DCCP_RTO_MAX ((unsigned)(120 * HZ)) /* FIXME: using TCP value */ +/* + * The maximum back-off value for retransmissions. This is needed for + * - retransmitting client-Requests (sec. 8.1.1), + * - retransmitting Close/CloseReq when closing (sec. 8.3), + * - feature-negotiation retransmission (sec. 6.6.3), + * - Acks in client-PARTOPEN state (sec. 8.1.5). + */ +#define DCCP_RTO_MAX ((unsigned)(64 * HZ)) -/* bounds for sampled RTT values from packet exchanges (in usec) */ +/* + * RTT sampling: sanity bounds and fallback RTT value from RFC 4340, section 3.4 + */ #define DCCP_SANE_RTT_MIN 100 -#define DCCP_SANE_RTT_MAX (4 * USEC_PER_SEC) +#define DCCP_FALLBACK_RTT (USEC_PER_SEC / 5) +#define DCCP_SANE_RTT_MAX (3 * USEC_PER_SEC) /* Maximal interval between probes for local resources. */ #define DCCP_RESOURCE_PROBE_INTERVAL ((unsigned)(HZ / 2U)) @@ -143,12 +153,6 @@ static inline u64 max48(const u64 seq1, const u64 seq2) return after48(seq1, seq2) ? seq1 : seq2; } -/* is seq1 next seqno after seq2 */ -static inline int follows48(const u64 seq1, const u64 seq2) -{ - return dccp_delta_seqno(seq2, seq1) == 1; -} - enum { DCCP_MIB_NUM = 0, DCCP_MIB_ACTIVEOPENS, /* ActiveOpens */ @@ -334,6 +338,7 @@ struct dccp_skb_cb { #define DCCP_SKB_CB(__skb) ((struct dccp_skb_cb *)&((__skb)->cb[0])) +/* RFC 4340, sec. 7.7 */ static inline int dccp_non_data_packet(const struct sk_buff *skb) { const __u8 type = DCCP_SKB_CB(skb)->dccpd_type; @@ -346,6 +351,17 @@ static inline int dccp_non_data_packet(const struct sk_buff *skb) type == DCCP_PKT_SYNCACK; } +/* RFC 4340, sec. 7.7 */ +static inline int dccp_data_packet(const struct sk_buff *skb) +{ + const __u8 type = DCCP_SKB_CB(skb)->dccpd_type; + + return type == DCCP_PKT_DATA || + type == DCCP_PKT_DATAACK || + type == DCCP_PKT_REQUEST || + type == DCCP_PKT_RESPONSE; +} + static inline int dccp_packet_without_ack(const struct sk_buff *skb) { const __u8 type = DCCP_SKB_CB(skb)->dccpd_type; @@ -406,6 +422,7 @@ static inline int dccp_ack_pending(const struct sock *sk) } extern int dccp_insert_options(struct sock *sk, struct sk_buff *skb); +extern int dccp_insert_options_rsk(struct dccp_request_sock*, struct sk_buff*); extern int dccp_insert_option_elapsed_time(struct sock *sk, struct sk_buff *skb, u32 elapsed_time); diff --git a/net/dccp/feat.c b/net/dccp/feat.c index 5ebdd86c1b99..4a4f6ce4498d 100644 --- a/net/dccp/feat.c +++ b/net/dccp/feat.c @@ -4,10 +4,16 @@ * An implementation of the DCCP protocol * Andrea Bittau <a.bittau@cs.ucl.ac.uk> * - * 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. + * ASSUMPTIONS + * ----------- + * o All currently known SP features have 1-byte quantities. If in the future + * extensions of RFCs 4340..42 define features with item lengths larger than + * one byte, a feature-specific extension of the code will be required. + * + * 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/module.h> @@ -24,11 +30,7 @@ int dccp_feat_change(struct dccp_minisock *dmsk, u8 type, u8 feature, dccp_feat_debug(type, feature, *val); - if (!dccp_feat_is_valid_type(type)) { - DCCP_WARN("option type %d invalid in negotiation\n", type); - return 1; - } - if (!dccp_feat_is_valid_length(type, feature, len)) { + if (len > 3) { DCCP_WARN("invalid length %d\n", len); return 1; } @@ -99,7 +101,6 @@ static int dccp_feat_update_ccid(struct sock *sk, u8 type, u8 new_ccid_nr) return 0; } -/* XXX taking only u8 vals */ static int dccp_feat_update(struct sock *sk, u8 type, u8 feat, u8 val) { dccp_feat_debug(type, feat, val); @@ -144,7 +145,6 @@ static int dccp_feat_reconcile(struct sock *sk, struct dccp_opt_pend *opt, /* FIXME sanity check vals */ /* Are values in any order? XXX Lame "algorithm" here */ - /* XXX assume values are 1 byte */ for (i = 0; i < slen; i++) { for (j = 0; j < rlen; j++) { if (spref[i] == rpref[j]) { @@ -179,7 +179,6 @@ static int dccp_feat_reconcile(struct sock *sk, struct dccp_opt_pend *opt, } /* need to put result and our preference list */ - /* XXX assume 1 byte vals */ rlen = 1 + opt->dccpop_len; rpref = kmalloc(rlen, GFP_ATOMIC); if (rpref == NULL) @@ -637,12 +636,12 @@ const char *dccp_feat_name(const u8 feat) [DCCPF_MIN_CSUM_COVER] = "Min. Csum Coverage", [DCCPF_DATA_CHECKSUM] = "Send Data Checksum", }; + if (feat > DCCPF_DATA_CHECKSUM && feat < DCCPF_MIN_CCID_SPECIFIC) + return feature_names[DCCPF_RESERVED]; + if (feat >= DCCPF_MIN_CCID_SPECIFIC) return "CCID-specific"; - if (dccp_feat_is_reserved(feat)) - return feature_names[DCCPF_RESERVED]; - return feature_names[feat]; } diff --git a/net/dccp/feat.h b/net/dccp/feat.h index 177f7dee4d10..e272222c7ace 100644 --- a/net/dccp/feat.h +++ b/net/dccp/feat.h @@ -14,32 +14,6 @@ #include <linux/types.h> #include "dccp.h" -static inline int dccp_feat_is_valid_length(u8 type, u8 feature, u8 len) -{ - /* sec. 6.1: Confirm has at least length 3, - * sec. 6.2: Change has at least length 4 */ - if (len < 3) - return 1; - if (len < 4 && (type == DCCPO_CHANGE_L || type == DCCPO_CHANGE_R)) - return 1; - /* XXX: add per-feature length validation (sec. 6.6.8) */ - return 0; -} - -static inline int dccp_feat_is_reserved(const u8 feat) -{ - return (feat > DCCPF_DATA_CHECKSUM && - feat < DCCPF_MIN_CCID_SPECIFIC) || - feat == DCCPF_RESERVED; -} - -/* feature negotiation knows only these four option types (RFC 4340, sec. 6) */ -static inline int dccp_feat_is_valid_type(const u8 optnum) -{ - return optnum >= DCCPO_CHANGE_L && optnum <= DCCPO_CONFIRM_R; - -} - #ifdef CONFIG_IP_DCCP_DEBUG extern const char *dccp_feat_typename(const u8 type); extern const char *dccp_feat_name(const u8 feat); diff --git a/net/dccp/input.c b/net/dccp/input.c index 1ce101062824..08392ed86c25 100644 --- a/net/dccp/input.c +++ b/net/dccp/input.c @@ -22,26 +22,77 @@ /* rate-limit for syncs in reply to sequence-invalid packets; RFC 4340, 7.5.4 */ int sysctl_dccp_sync_ratelimit __read_mostly = HZ / 8; -static void dccp_fin(struct sock *sk, struct sk_buff *skb) +static void dccp_enqueue_skb(struct sock *sk, struct sk_buff *skb) { - sk->sk_shutdown |= RCV_SHUTDOWN; - sock_set_flag(sk, SOCK_DONE); __skb_pull(skb, dccp_hdr(skb)->dccph_doff * 4); __skb_queue_tail(&sk->sk_receive_queue, skb); skb_set_owner_r(skb, sk); sk->sk_data_ready(sk, 0); } -static void dccp_rcv_close(struct sock *sk, struct sk_buff *skb) +static void dccp_fin(struct sock *sk, struct sk_buff *skb) { - dccp_send_reset(sk, DCCP_RESET_CODE_CLOSED); - dccp_fin(sk, skb); - dccp_set_state(sk, DCCP_CLOSED); - sk_wake_async(sk, 1, POLL_HUP); + /* + * On receiving Close/CloseReq, both RD/WR shutdown are performed. + * RFC 4340, 8.3 says that we MAY send further Data/DataAcks after + * receiving the closing segment, but there is no guarantee that such + * data will be processed at all. + */ + sk->sk_shutdown = SHUTDOWN_MASK; + sock_set_flag(sk, SOCK_DONE); + dccp_enqueue_skb(sk, skb); +} + +static int dccp_rcv_close(struct sock *sk, struct sk_buff *skb) +{ + int queued = 0; + + switch (sk->sk_state) { + /* + * We ignore Close when received in one of the following states: + * - CLOSED (may be a late or duplicate packet) + * - PASSIVE_CLOSEREQ (the peer has sent a CloseReq earlier) + * - RESPOND (already handled by dccp_check_req) + */ + case DCCP_CLOSING: + /* + * Simultaneous-close: receiving a Close after sending one. This + * can happen if both client and server perform active-close and + * will result in an endless ping-pong of crossing and retrans- + * mitted Close packets, which only terminates when one of the + * nodes times out (min. 64 seconds). Quicker convergence can be + * achieved when one of the nodes acts as tie-breaker. + * This is ok as both ends are done with data transfer and each + * end is just waiting for the other to acknowledge termination. + */ + if (dccp_sk(sk)->dccps_role != DCCP_ROLE_CLIENT) + break; + /* fall through */ + case DCCP_REQUESTING: + case DCCP_ACTIVE_CLOSEREQ: + dccp_send_reset(sk, DCCP_RESET_CODE_CLOSED); + dccp_done(sk); + break; + case DCCP_OPEN: + case DCCP_PARTOPEN: + /* Give waiting application a chance to read pending data */ + queued = 1; + dccp_fin(sk, skb); + dccp_set_state(sk, DCCP_PASSIVE_CLOSE); + /* fall through */ + case DCCP_PASSIVE_CLOSE: + /* + * Retransmitted Close: we have already enqueued the first one. + */ + sk_wake_async(sk, SOCK_WAKE_WAITD, POLL_HUP); + } + return queued; } -static void dccp_rcv_closereq(struct sock *sk, struct sk_buff *skb) +static int dccp_rcv_closereq(struct sock *sk, struct sk_buff *skb) { + int queued = 0; + /* * Step 7: Check for unexpected packet types * If (S.is_server and P.type == CloseReq) @@ -50,12 +101,26 @@ static void dccp_rcv_closereq(struct sock *sk, struct sk_buff *skb) */ if (dccp_sk(sk)->dccps_role != DCCP_ROLE_CLIENT) { dccp_send_sync(sk, DCCP_SKB_CB(skb)->dccpd_seq, DCCP_PKT_SYNC); - return; + return queued; } - if (sk->sk_state != DCCP_CLOSING) + /* Step 13: process relevant Client states < CLOSEREQ */ + switch (sk->sk_state) { + case DCCP_REQUESTING: + dccp_send_close(sk, 0); dccp_set_state(sk, DCCP_CLOSING); - dccp_send_close(sk, 0); + break; + case DCCP_OPEN: + case DCCP_PARTOPEN: + /* Give waiting application a chance to read pending data */ + queued = 1; + dccp_fin(sk, skb); + dccp_set_state(sk, DCCP_PASSIVE_CLOSEREQ); + /* fall through */ + case DCCP_PASSIVE_CLOSEREQ: + sk_wake_async(sk, SOCK_WAKE_WAITD, POLL_HUP); + } + return queued; } static u8 dccp_reset_code_convert(const u8 code) @@ -90,7 +155,7 @@ static void dccp_rcv_reset(struct sock *sk, struct sk_buff *skb) dccp_fin(sk, skb); if (err && !sock_flag(sk, SOCK_DEAD)) - sk_wake_async(sk, 0, POLL_ERR); + sk_wake_async(sk, SOCK_WAKE_IO, POLL_ERR); dccp_time_wait(sk, DCCP_TIME_WAIT, 0); } @@ -103,6 +168,21 @@ static void dccp_event_ack_recv(struct sock *sk, struct sk_buff *skb) DCCP_SKB_CB(skb)->dccpd_ack_seq); } +static void dccp_deliver_input_to_ccids(struct sock *sk, struct sk_buff *skb) +{ + const struct dccp_sock *dp = dccp_sk(sk); + + /* Don't deliver to RX CCID when node has shut down read end. */ + if (!(sk->sk_shutdown & RCV_SHUTDOWN)) + ccid_hc_rx_packet_recv(dp->dccps_hc_rx_ccid, sk, skb); + /* + * Until the TX queue has been drained, we can not honour SHUT_WR, since + * we need received feedback as input to adjust congestion control. + */ + if (sk->sk_write_queue.qlen > 0 || !(sk->sk_shutdown & SEND_SHUTDOWN)) + ccid_hc_tx_packet_recv(dp->dccps_hc_tx_ccid, sk, skb); +} + static int dccp_check_seqno(struct sock *sk, struct sk_buff *skb) { const struct dccp_hdr *dh = dccp_hdr(skb); @@ -209,13 +289,11 @@ static int __dccp_rcv_established(struct sock *sk, struct sk_buff *skb, case DCCP_PKT_DATAACK: case DCCP_PKT_DATA: /* - * FIXME: check if sk_receive_queue is full, schedule DATA_DROPPED - * option if it is. + * FIXME: schedule DATA_DROPPED (RFC 4340, 11.7.2) if and when + * - sk_shutdown == RCV_SHUTDOWN, use Code 1, "Not Listening" + * - sk_receive_queue is full, use Code 2, "Receive Buffer" */ - __skb_pull(skb, dh->dccph_doff * 4); - __skb_queue_tail(&sk->sk_receive_queue, skb); - skb_set_owner_r(skb, sk); - sk->sk_data_ready(sk, 0); + dccp_enqueue_skb(sk, skb); return 0; case DCCP_PKT_ACK: goto discard; @@ -231,11 +309,13 @@ static int __dccp_rcv_established(struct sock *sk, struct sk_buff *skb, dccp_rcv_reset(sk, skb); return 0; case DCCP_PKT_CLOSEREQ: - dccp_rcv_closereq(sk, skb); + if (dccp_rcv_closereq(sk, skb)) + return 0; goto discard; case DCCP_PKT_CLOSE: - dccp_rcv_close(sk, skb); - return 0; + if (dccp_rcv_close(sk, skb)) + return 0; + goto discard; case DCCP_PKT_REQUEST: /* Step 7 * or (S.is_server and P.type == Response) @@ -289,7 +369,7 @@ int dccp_rcv_established(struct sock *sk, struct sk_buff *skb, if (dccp_check_seqno(sk, skb)) goto discard; - if (dccp_parse_options(sk, skb)) + if (dccp_parse_options(sk, NULL, skb)) goto discard; if (DCCP_SKB_CB(skb)->dccpd_ack_seq != DCCP_PKT_WITHOUT_ACK_SEQ) @@ -300,9 +380,7 @@ int dccp_rcv_established(struct sock *sk, struct sk_buff *skb, DCCP_SKB_CB(skb)->dccpd_seq, DCCP_ACKVEC_STATE_RECEIVED)) goto discard; - - ccid_hc_rx_packet_recv(dp->dccps_hc_rx_ccid, sk, skb); - ccid_hc_tx_packet_recv(dp->dccps_hc_tx_ccid, sk, skb); + dccp_deliver_input_to_ccids(sk, skb); return __dccp_rcv_established(sk, skb, dh, len); discard: @@ -349,7 +427,7 @@ static int dccp_rcv_request_sent_state_process(struct sock *sk, goto out_invalid_packet; } - if (dccp_parse_options(sk, skb)) + if (dccp_parse_options(sk, NULL, skb)) goto out_invalid_packet; /* Obtain usec RTT sample from SYN exchange (used by CCID 3) */ @@ -402,7 +480,7 @@ static int dccp_rcv_request_sent_state_process(struct sock *sk, if (!sock_flag(sk, SOCK_DEAD)) { sk->sk_state_change(sk); - sk_wake_async(sk, 0, POLL_OUT); + sk_wake_async(sk, SOCK_WAKE_IO, POLL_OUT); } if (sk->sk_write_pending || icsk->icsk_ack.pingpong || @@ -531,7 +609,7 @@ int dccp_rcv_state_process(struct sock *sk, struct sk_buff *skb, /* * Step 8: Process options and mark acknowledgeable */ - if (dccp_parse_options(sk, skb)) + if (dccp_parse_options(sk, NULL, skb)) goto discard; if (dcb->dccpd_ack_seq != DCCP_PKT_WITHOUT_ACK_SEQ) @@ -543,8 +621,7 @@ int dccp_rcv_state_process(struct sock *sk, struct sk_buff *skb, DCCP_ACKVEC_STATE_RECEIVED)) goto discard; - ccid_hc_rx_packet_recv(dp->dccps_hc_rx_ccid, sk, skb); - ccid_hc_tx_packet_recv(dp->dccps_hc_tx_ccid, sk, skb); + dccp_deliver_input_to_ccids(sk, skb); } /* @@ -560,16 +637,14 @@ int dccp_rcv_state_process(struct sock *sk, struct sk_buff *skb, return 0; /* * Step 7: Check for unexpected packet types - * If (S.is_server and P.type == CloseReq) - * or (S.is_server and P.type == Response) + * If (S.is_server and P.type == Response) * or (S.is_client and P.type == Request) * or (S.state == RESPOND and P.type == Data), * Send Sync packet acknowledging P.seqno * Drop packet and return */ } else if ((dp->dccps_role != DCCP_ROLE_CLIENT && - (dh->dccph_type == DCCP_PKT_RESPONSE || - dh->dccph_type == DCCP_PKT_CLOSEREQ)) || + dh->dccph_type == DCCP_PKT_RESPONSE) || (dp->dccps_role == DCCP_ROLE_CLIENT && dh->dccph_type == DCCP_PKT_REQUEST) || (sk->sk_state == DCCP_RESPOND && @@ -577,11 +652,13 @@ int dccp_rcv_state_process(struct sock *sk, struct sk_buff *skb, dccp_send_sync(sk, dcb->dccpd_seq, DCCP_PKT_SYNC); goto discard; } else if (dh->dccph_type == DCCP_PKT_CLOSEREQ) { - dccp_rcv_closereq(sk, skb); + if (dccp_rcv_closereq(sk, skb)) + return 0; goto discard; } else if (dh->dccph_type == DCCP_PKT_CLOSE) { - dccp_rcv_close(sk, skb); - return 0; + if (dccp_rcv_close(sk, skb)) + return 0; + goto discard; } switch (sk->sk_state) { @@ -611,7 +688,7 @@ int dccp_rcv_state_process(struct sock *sk, struct sk_buff *skb, switch (old_state) { case DCCP_PARTOPEN: sk->sk_state_change(sk); - sk_wake_async(sk, 0, POLL_OUT); + sk_wake_async(sk, SOCK_WAKE_IO, POLL_OUT); break; } } else if (unlikely(dh->dccph_type == DCCP_PKT_SYNC)) { diff --git a/net/dccp/ipv4.c b/net/dccp/ipv4.c index db17b83e8d3e..9e38b0d6195c 100644 --- a/net/dccp/ipv4.c +++ b/net/dccp/ipv4.c @@ -408,7 +408,7 @@ struct sock *dccp_v4_request_recv_sock(struct sock *sk, struct sk_buff *skb, dccp_sync_mss(newsk, dst_mtu(dst)); - __inet_hash(&dccp_hashinfo, newsk, 0); + __inet_hash_nolisten(&dccp_hashinfo, newsk); __inet_inherit_port(&dccp_hashinfo, sk, newsk); return newsk; @@ -469,7 +469,7 @@ static struct dst_entry* dccp_v4_route_skb(struct sock *sk, }; security_skb_classify_flow(skb, &fl); - if (ip_route_output_flow(&rt, &fl, sk, 0)) { + if (ip_route_output_flow(&init_net, &rt, &fl, sk, 0)) { IP_INC_STATS_BH(IPSTATS_MIB_OUTNOROUTES); return NULL; } @@ -600,11 +600,12 @@ int dccp_v4_conn_request(struct sock *sk, struct sk_buff *skb) if (req == NULL) goto drop; - if (dccp_parse_options(sk, skb)) - goto drop_and_free; - dccp_reqsk_init(req, skb); + dreq = dccp_rsk(req); + if (dccp_parse_options(sk, dreq, skb)) + goto drop_and_free; + if (security_inet_conn_request(sk, skb, req)) goto drop_and_free; @@ -621,7 +622,6 @@ int dccp_v4_conn_request(struct sock *sk, struct sk_buff *skb) * In fact we defer setting S.GSR, S.SWL, S.SWH to * dccp_create_openreq_child. */ - dreq = dccp_rsk(req); dreq->dreq_isr = dcb->dccpd_seq; dreq->dreq_iss = dccp_v4_init_sequence(skb); dreq->dreq_service = service; diff --git a/net/dccp/ipv6.c b/net/dccp/ipv6.c index 87c98fb86fa8..f42b75ce7f5c 100644 --- a/net/dccp/ipv6.c +++ b/net/dccp/ipv6.c @@ -415,11 +415,12 @@ static int dccp_v6_conn_request(struct sock *sk, struct sk_buff *skb) if (req == NULL) goto drop; - if (dccp_parse_options(sk, skb)) - goto drop_and_free; - dccp_reqsk_init(req, skb); + dreq = dccp_rsk(req); + if (dccp_parse_options(sk, dreq, skb)) + goto drop_and_free; + if (security_inet_conn_request(sk, skb, req)) goto drop_and_free; @@ -449,7 +450,6 @@ static int dccp_v6_conn_request(struct sock *sk, struct sk_buff *skb) * In fact we defer setting S.GSR, S.SWL, S.SWH to * dccp_create_openreq_child. */ - dreq = dccp_rsk(req); dreq->dreq_isr = dcb->dccpd_seq; dreq->dreq_iss = dccp_v6_init_sequence(skb); dreq->dreq_service = service; @@ -994,7 +994,7 @@ static int dccp_v6_connect(struct sock *sk, struct sockaddr *uaddr, if (final_p) ipv6_addr_copy(&fl.fl6_dst, final_p); - err = __xfrm_lookup(&dst, &fl, sk, 1); + err = __xfrm_lookup(&dst, &fl, sk, XFRM_LOOKUP_WAIT); if (err < 0) { if (err == -EREMOTE) err = ip6_dst_blackhole(sk, &dst, &fl); diff --git a/net/dccp/minisocks.c b/net/dccp/minisocks.c index 831b76e08d02..027d1814e1ab 100644 --- a/net/dccp/minisocks.c +++ b/net/dccp/minisocks.c @@ -117,11 +117,13 @@ struct sock *dccp_create_openreq_child(struct sock *sk, struct dccp_sock *newdp = dccp_sk(newsk); struct dccp_minisock *newdmsk = dccp_msk(newsk); - newdp->dccps_role = DCCP_ROLE_SERVER; - newdp->dccps_hc_rx_ackvec = NULL; - newdp->dccps_service_list = NULL; - newdp->dccps_service = dreq->dreq_service; - newicsk->icsk_rto = DCCP_TIMEOUT_INIT; + newdp->dccps_role = DCCP_ROLE_SERVER; + newdp->dccps_hc_rx_ackvec = NULL; + newdp->dccps_service_list = NULL; + newdp->dccps_service = dreq->dreq_service; + newdp->dccps_timestamp_echo = dreq->dreq_timestamp_echo; + newdp->dccps_timestamp_time = dreq->dreq_timestamp_time; + newicsk->icsk_rto = DCCP_TIMEOUT_INIT; if (dccp_feat_clone(sk, newsk)) goto out_free; @@ -200,10 +202,10 @@ struct sock *dccp_check_req(struct sock *sk, struct sk_buff *skb, struct request_sock **prev) { struct sock *child = NULL; + struct dccp_request_sock *dreq = dccp_rsk(req); /* Check for retransmitted REQUEST */ if (dccp_hdr(skb)->dccph_type == DCCP_PKT_REQUEST) { - struct dccp_request_sock *dreq = dccp_rsk(req); if (after48(DCCP_SKB_CB(skb)->dccpd_seq, dreq->dreq_isr)) { dccp_pr_debug("Retransmitted REQUEST\n"); @@ -227,22 +229,22 @@ struct sock *dccp_check_req(struct sock *sk, struct sk_buff *skb, goto drop; /* Invalid ACK */ - if (DCCP_SKB_CB(skb)->dccpd_ack_seq != dccp_rsk(req)->dreq_iss) { + if (DCCP_SKB_CB(skb)->dccpd_ack_seq != dreq->dreq_iss) { dccp_pr_debug("Invalid ACK number: ack_seq=%llu, " "dreq_iss=%llu\n", (unsigned long long) DCCP_SKB_CB(skb)->dccpd_ack_seq, - (unsigned long long) - dccp_rsk(req)->dreq_iss); + (unsigned long long) dreq->dreq_iss); goto drop; } + if (dccp_parse_options(sk, dreq, skb)) + goto drop; + child = inet_csk(sk)->icsk_af_ops->syn_recv_sock(sk, skb, req, NULL); if (child == NULL) goto listen_overflow; - /* FIXME: deal with options */ - inet_csk_reqsk_queue_unlink(sk, req, prev); inet_csk_reqsk_queue_removed(sk, req); inet_csk_reqsk_queue_add(sk, req, child); @@ -303,9 +305,12 @@ EXPORT_SYMBOL_GPL(dccp_reqsk_send_ack); void dccp_reqsk_init(struct request_sock *req, struct sk_buff *skb) { - inet_rsk(req)->rmt_port = dccp_hdr(skb)->dccph_sport; - inet_rsk(req)->acked = 0; - req->rcv_wnd = sysctl_dccp_feat_sequence_window; + struct dccp_request_sock *dreq = dccp_rsk(req); + + inet_rsk(req)->rmt_port = dccp_hdr(skb)->dccph_sport; + inet_rsk(req)->acked = 0; + req->rcv_wnd = sysctl_dccp_feat_sequence_window; + dreq->dreq_timestamp_echo = 0; } EXPORT_SYMBOL_GPL(dccp_reqsk_init); diff --git a/net/dccp/options.c b/net/dccp/options.c index d286cffe2c49..d2a84a2fecee 100644 --- a/net/dccp/options.c +++ b/net/dccp/options.c @@ -46,7 +46,13 @@ static u32 dccp_decode_value_var(const unsigned char *bf, const u8 len) return value; } -int dccp_parse_options(struct sock *sk, struct sk_buff *skb) +/** + * dccp_parse_options - Parse DCCP options present in @skb + * @sk: client|server|listening dccp socket (when @dreq != NULL) + * @dreq: request socket to use during connection setup, or NULL + */ +int dccp_parse_options(struct sock *sk, struct dccp_request_sock *dreq, + struct sk_buff *skb) { struct dccp_sock *dp = dccp_sk(sk); const struct dccp_hdr *dh = dccp_hdr(skb); @@ -92,6 +98,20 @@ int dccp_parse_options(struct sock *sk, struct sk_buff *skb) goto out_invalid_option; } + /* + * CCID-Specific Options (from RFC 4340, sec. 10.3): + * + * Option numbers 128 through 191 are for options sent from the + * HC-Sender to the HC-Receiver; option numbers 192 through 255 + * are for options sent from the HC-Receiver to the HC-Sender. + * + * CCID-specific options are ignored during connection setup, as + * negotiation may still be in progress (see RFC 4340, 10.3). + * + */ + if (dreq != NULL && opt >= 128) + goto ignore_option; + switch (opt) { case DCCPO_PADDING: break; @@ -112,6 +132,8 @@ int dccp_parse_options(struct sock *sk, struct sk_buff *skb) case DCCPO_CHANGE_L: /* fall through */ case DCCPO_CHANGE_R: + if (pkt_type == DCCP_PKT_DATA) + break; if (len < 2) goto out_invalid_option; rc = dccp_feat_change_recv(sk, opt, *value, value + 1, @@ -128,7 +150,9 @@ int dccp_parse_options(struct sock *sk, struct sk_buff *skb) case DCCPO_CONFIRM_L: /* fall through */ case DCCPO_CONFIRM_R: - if (len < 2) + if (pkt_type == DCCP_PKT_DATA) + break; + if (len < 2) /* FIXME this disallows empty confirm */ goto out_invalid_option; if (dccp_feat_confirm_recv(sk, opt, *value, value + 1, len - 1)) @@ -136,7 +160,7 @@ int dccp_parse_options(struct sock *sk, struct sk_buff *skb) break; case DCCPO_ACK_VECTOR_0: case DCCPO_ACK_VECTOR_1: - if (pkt_type == DCCP_PKT_DATA) + if (dccp_packet_without_ack(skb)) /* RFC 4340, 11.4 */ break; if (dccp_msk(sk)->dccpms_send_ack_vector && @@ -146,15 +170,27 @@ int dccp_parse_options(struct sock *sk, struct sk_buff *skb) case DCCPO_TIMESTAMP: if (len != 4) goto out_invalid_option; - + /* + * RFC 4340 13.1: "The precise time corresponding to + * Timestamp Value zero is not specified". We use + * zero to indicate absence of a meaningful timestamp. + */ opt_val = get_unaligned((__be32 *)value); - opt_recv->dccpor_timestamp = ntohl(opt_val); - - dp->dccps_timestamp_echo = opt_recv->dccpor_timestamp; - dp->dccps_timestamp_time = ktime_get_real(); + if (unlikely(opt_val == 0)) { + DCCP_WARN("Timestamp with zero value\n"); + break; + } + if (dreq != NULL) { + dreq->dreq_timestamp_echo = ntohl(opt_val); + dreq->dreq_timestamp_time = dccp_timestamp(); + } else { + opt_recv->dccpor_timestamp = + dp->dccps_timestamp_echo = ntohl(opt_val); + dp->dccps_timestamp_time = dccp_timestamp(); + } dccp_pr_debug("%s rx opt: TIMESTAMP=%u, ackno=%llu\n", - dccp_role(sk), opt_recv->dccpor_timestamp, + dccp_role(sk), ntohl(opt_val), (unsigned long long) DCCP_SKB_CB(skb)->dccpd_ack_seq); break; @@ -194,18 +230,17 @@ int dccp_parse_options(struct sock *sk, struct sk_buff *skb) opt_recv->dccpor_elapsed_time = elapsed_time; break; case DCCPO_ELAPSED_TIME: - if (len != 2 && len != 4) - goto out_invalid_option; - - if (pkt_type == DCCP_PKT_DATA) - continue; + if (dccp_packet_without_ack(skb)) /* RFC 4340, 13.2 */ + break; if (len == 2) { __be16 opt_val2 = get_unaligned((__be16 *)value); elapsed_time = ntohs(opt_val2); - } else { + } else if (len == 4) { opt_val = get_unaligned((__be32 *)value); elapsed_time = ntohl(opt_val); + } else { + goto out_invalid_option; } if (elapsed_time > opt_recv->dccpor_elapsed_time) @@ -214,15 +249,6 @@ int dccp_parse_options(struct sock *sk, struct sk_buff *skb) dccp_pr_debug("%s rx opt: ELAPSED_TIME=%d\n", dccp_role(sk), elapsed_time); break; - /* - * From RFC 4340, sec. 10.3: - * - * Option numbers 128 through 191 are for - * options sent from the HC-Sender to the - * HC-Receiver; option numbers 192 through 255 - * are for options sent from the HC-Receiver to - * the HC-Sender. - */ case 128 ... 191: { const u16 idx = value - options; @@ -246,7 +272,7 @@ int dccp_parse_options(struct sock *sk, struct sk_buff *skb) "implemented, ignoring", sk, opt, len); break; } - +ignore_option: if (opt != DCCPO_MANDATORY) mandatory = 0; } @@ -382,16 +408,24 @@ int dccp_insert_option_timestamp(struct sock *sk, struct sk_buff *skb) EXPORT_SYMBOL_GPL(dccp_insert_option_timestamp); -static int dccp_insert_option_timestamp_echo(struct sock *sk, +static int dccp_insert_option_timestamp_echo(struct dccp_sock *dp, + struct dccp_request_sock *dreq, struct sk_buff *skb) { - struct dccp_sock *dp = dccp_sk(sk); __be32 tstamp_echo; - int len, elapsed_time_len; unsigned char *to; - const suseconds_t delta = ktime_us_delta(ktime_get_real(), - dp->dccps_timestamp_time); - u32 elapsed_time = delta / 10; + u32 elapsed_time, elapsed_time_len, len; + + if (dreq != NULL) { + elapsed_time = dccp_timestamp() - dreq->dreq_timestamp_time; + tstamp_echo = htonl(dreq->dreq_timestamp_echo); + dreq->dreq_timestamp_echo = 0; + } else { + elapsed_time = dccp_timestamp() - dp->dccps_timestamp_time; + tstamp_echo = htonl(dp->dccps_timestamp_echo); + dp->dccps_timestamp_echo = 0; + } + elapsed_time_len = dccp_elapsed_time_len(elapsed_time); len = 6 + elapsed_time_len; @@ -404,7 +438,6 @@ static int dccp_insert_option_timestamp_echo(struct sock *sk, *to++ = DCCPO_TIMESTAMP_ECHO; *to++ = len; - tstamp_echo = htonl(dp->dccps_timestamp_echo); memcpy(to, &tstamp_echo, 4); to += 4; @@ -416,8 +449,6 @@ static int dccp_insert_option_timestamp_echo(struct sock *sk, memcpy(to, &var32, 4); } - dp->dccps_timestamp_echo = 0; - dp->dccps_timestamp_time = ktime_set(0, 0); return 0; } @@ -510,6 +541,18 @@ static int dccp_insert_options_feat(struct sock *sk, struct sk_buff *skb) return 0; } +/* The length of all options needs to be a multiple of 4 (5.8) */ +static void dccp_insert_option_padding(struct sk_buff *skb) +{ + int padding = DCCP_SKB_CB(skb)->dccpd_opt_len % 4; + + if (padding != 0) { + padding = 4 - padding; + memset(skb_push(skb, padding), 0, padding); + DCCP_SKB_CB(skb)->dccpd_opt_len += padding; + } +} + int dccp_insert_options(struct sock *sk, struct sk_buff *skb) { struct dccp_sock *dp = dccp_sk(sk); @@ -526,10 +569,6 @@ int dccp_insert_options(struct sock *sk, struct sk_buff *skb) dccp_ackvec_pending(dp->dccps_hc_rx_ackvec) && dccp_insert_option_ackvec(sk, skb)) return -1; - - if (dp->dccps_timestamp_echo != 0 && - dccp_insert_option_timestamp_echo(sk, skb)) - return -1; } if (dp->dccps_hc_rx_insert_options) { @@ -553,18 +592,22 @@ int dccp_insert_options(struct sock *sk, struct sk_buff *skb) dccp_insert_option_timestamp(sk, skb)) return -1; - /* XXX: insert other options when appropriate */ + if (dp->dccps_timestamp_echo != 0 && + dccp_insert_option_timestamp_echo(dp, NULL, skb)) + return -1; + + dccp_insert_option_padding(skb); + return 0; +} - if (DCCP_SKB_CB(skb)->dccpd_opt_len != 0) { - /* The length of all options has to be a multiple of 4 */ - int padding = DCCP_SKB_CB(skb)->dccpd_opt_len % 4; +int dccp_insert_options_rsk(struct dccp_request_sock *dreq, struct sk_buff *skb) +{ + DCCP_SKB_CB(skb)->dccpd_opt_len = 0; - if (padding != 0) { - padding = 4 - padding; - memset(skb_push(skb, padding), 0, padding); - DCCP_SKB_CB(skb)->dccpd_opt_len += padding; - } - } + if (dreq->dreq_timestamp_echo != 0 && + dccp_insert_option_timestamp_echo(NULL, dreq, skb)) + return -1; + dccp_insert_option_padding(skb); return 0; } diff --git a/net/dccp/output.c b/net/dccp/output.c index f49544618f20..3b763db3d863 100644 --- a/net/dccp/output.c +++ b/net/dccp/output.c @@ -133,15 +133,31 @@ static int dccp_transmit_skb(struct sock *sk, struct sk_buff *skb) return -ENOBUFS; } +/** + * dccp_determine_ccmps - Find out about CCID-specfic packet-size limits + * We only consider the HC-sender CCID for setting the CCMPS (RFC 4340, 14.), + * since the RX CCID is restricted to feedback packets (Acks), which are small + * in comparison with the data traffic. A value of 0 means "no current CCMPS". + */ +static u32 dccp_determine_ccmps(const struct dccp_sock *dp) +{ + const struct ccid *tx_ccid = dp->dccps_hc_tx_ccid; + + if (tx_ccid == NULL || tx_ccid->ccid_ops == NULL) + return 0; + return tx_ccid->ccid_ops->ccid_ccmps; +} + unsigned int dccp_sync_mss(struct sock *sk, u32 pmtu) { struct inet_connection_sock *icsk = inet_csk(sk); struct dccp_sock *dp = dccp_sk(sk); - int mss_now = (pmtu - icsk->icsk_af_ops->net_header_len - - sizeof(struct dccp_hdr) - sizeof(struct dccp_hdr_ext)); + u32 ccmps = dccp_determine_ccmps(dp); + int cur_mps = ccmps ? min(pmtu, ccmps) : pmtu; - /* Now subtract optional transport overhead */ - mss_now -= icsk->icsk_ext_hdr_len; + /* Account for header lengths and IPv4/v6 option overhead */ + cur_mps -= (icsk->icsk_af_ops->net_header_len + icsk->icsk_ext_hdr_len + + sizeof(struct dccp_hdr) + sizeof(struct dccp_hdr_ext)); /* * FIXME: this should come from the CCID infrastructure, where, say, @@ -151,13 +167,13 @@ unsigned int dccp_sync_mss(struct sock *sk, u32 pmtu) * make it a multiple of 4 */ - mss_now -= ((5 + 6 + 10 + 6 + 6 + 6 + 3) / 4) * 4; + cur_mps -= ((5 + 6 + 10 + 6 + 6 + 6 + 3) / 4) * 4; /* And store cached results */ icsk->icsk_pmtu_cookie = pmtu; - dp->dccps_mss_cache = mss_now; + dp->dccps_mss_cache = cur_mps; - return mss_now; + return cur_mps; } EXPORT_SYMBOL_GPL(dccp_sync_mss); @@ -170,7 +186,7 @@ void dccp_write_space(struct sock *sk) wake_up_interruptible(sk->sk_sleep); /* Should agree with poll, otherwise some programs break */ if (sock_writeable(sk)) - sk_wake_async(sk, 2, POLL_OUT); + sk_wake_async(sk, SOCK_WAKE_SPACE, POLL_OUT); read_unlock(&sk->sk_callback_lock); } @@ -303,7 +319,7 @@ struct sk_buff *dccp_make_response(struct sock *sk, struct dst_entry *dst, DCCP_SKB_CB(skb)->dccpd_type = DCCP_PKT_RESPONSE; DCCP_SKB_CB(skb)->dccpd_seq = dreq->dreq_iss; - if (dccp_insert_options(sk, skb)) { + if (dccp_insert_options_rsk(dreq, skb)) { kfree_skb(skb); return NULL; } @@ -391,7 +407,7 @@ int dccp_send_reset(struct sock *sk, enum dccp_reset_codes code) * FIXME: what if rebuild_header fails? * Should we be doing a rebuild_header here? */ - int err = inet_sk_rebuild_header(sk); + int err = inet_csk(sk)->icsk_af_ops->rebuild_header(sk); if (err != 0) return err; @@ -567,14 +583,27 @@ void dccp_send_close(struct sock *sk, const int active) /* Reserve space for headers and prepare control bits. */ skb_reserve(skb, sk->sk_prot->max_header); - DCCP_SKB_CB(skb)->dccpd_type = dp->dccps_role == DCCP_ROLE_CLIENT ? - DCCP_PKT_CLOSE : DCCP_PKT_CLOSEREQ; + if (dp->dccps_role == DCCP_ROLE_SERVER && !dp->dccps_server_timewait) + DCCP_SKB_CB(skb)->dccpd_type = DCCP_PKT_CLOSEREQ; + else + DCCP_SKB_CB(skb)->dccpd_type = DCCP_PKT_CLOSE; if (active) { dccp_write_xmit(sk, 1); dccp_skb_entail(sk, skb); dccp_transmit_skb(sk, skb_clone(skb, prio)); - /* FIXME do we need a retransmit timer here? */ + /* + * Retransmission timer for active-close: RFC 4340, 8.3 requires + * to retransmit the Close/CloseReq until the CLOSING/CLOSEREQ + * state can be left. The initial timeout is 2 RTTs. + * Since RTT measurement is done by the CCIDs, there is no easy + * way to get an RTT sample. The fallback RTT from RFC 4340, 3.4 + * is too low (200ms); we use a high value to avoid unnecessary + * retransmissions when the link RTT is > 0.2 seconds. + * FIXME: Let main module sample RTTs and use that instead. + */ + inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS, + DCCP_TIMEOUT_INIT, DCCP_RTO_MAX); } else dccp_transmit_skb(sk, skb); } diff --git a/net/dccp/proto.c b/net/dccp/proto.c index 7a3bea9c28c1..0bed4a6095b7 100644 --- a/net/dccp/proto.c +++ b/net/dccp/proto.c @@ -60,8 +60,7 @@ void dccp_set_state(struct sock *sk, const int state) { const int oldstate = sk->sk_state; - dccp_pr_debug("%s(%p) %-10.10s -> %s\n", - dccp_role(sk), sk, + dccp_pr_debug("%s(%p) %s --> %s\n", dccp_role(sk), sk, dccp_state_name(oldstate), dccp_state_name(state)); WARN_ON(state == oldstate); @@ -72,7 +71,8 @@ void dccp_set_state(struct sock *sk, const int state) break; case DCCP_CLOSED: - if (oldstate == DCCP_CLOSING || oldstate == DCCP_OPEN) + if (oldstate == DCCP_OPEN || oldstate == DCCP_ACTIVE_CLOSEREQ || + oldstate == DCCP_CLOSING) DCCP_INC_STATS(DCCP_MIB_ESTABRESETS); sk->sk_prot->unhash(sk); @@ -93,6 +93,24 @@ void dccp_set_state(struct sock *sk, const int state) EXPORT_SYMBOL_GPL(dccp_set_state); +static void dccp_finish_passive_close(struct sock *sk) +{ + switch (sk->sk_state) { + case DCCP_PASSIVE_CLOSE: + /* Node (client or server) has received Close packet. */ + dccp_send_reset(sk, DCCP_RESET_CODE_CLOSED); + dccp_set_state(sk, DCCP_CLOSED); + break; + case DCCP_PASSIVE_CLOSEREQ: + /* + * Client received CloseReq. We set the `active' flag so that + * dccp_send_close() retransmits the Close as per RFC 4340, 8.3. + */ + dccp_send_close(sk, 1); + dccp_set_state(sk, DCCP_CLOSING); + } +} + void dccp_done(struct sock *sk) { dccp_set_state(sk, DCCP_CLOSED); @@ -134,14 +152,17 @@ EXPORT_SYMBOL_GPL(dccp_packet_name); const char *dccp_state_name(const int state) { static char *dccp_state_names[] = { - [DCCP_OPEN] = "OPEN", - [DCCP_REQUESTING] = "REQUESTING", - [DCCP_PARTOPEN] = "PARTOPEN", - [DCCP_LISTEN] = "LISTEN", - [DCCP_RESPOND] = "RESPOND", - [DCCP_CLOSING] = "CLOSING", - [DCCP_TIME_WAIT] = "TIME_WAIT", - [DCCP_CLOSED] = "CLOSED", + [DCCP_OPEN] = "OPEN", + [DCCP_REQUESTING] = "REQUESTING", + [DCCP_PARTOPEN] = "PARTOPEN", + [DCCP_LISTEN] = "LISTEN", + [DCCP_RESPOND] = "RESPOND", + [DCCP_CLOSING] = "CLOSING", + [DCCP_ACTIVE_CLOSEREQ] = "CLOSEREQ", + [DCCP_PASSIVE_CLOSE] = "PASSIVE_CLOSE", + [DCCP_PASSIVE_CLOSEREQ] = "PASSIVE_CLOSEREQ", + [DCCP_TIME_WAIT] = "TIME_WAIT", + [DCCP_CLOSED] = "CLOSED", }; if (state >= DCCP_MAX_STATES) @@ -174,6 +195,19 @@ int dccp_init_sock(struct sock *sk, const __u8 ctl_sock_initialized) dccp_minisock_init(&dp->dccps_minisock); + icsk->icsk_rto = DCCP_TIMEOUT_INIT; + icsk->icsk_syn_retries = sysctl_dccp_request_retries; + sk->sk_state = DCCP_CLOSED; + sk->sk_write_space = dccp_write_space; + icsk->icsk_sync_mss = dccp_sync_mss; + dp->dccps_mss_cache = 536; + dp->dccps_rate_last = jiffies; + dp->dccps_role = DCCP_ROLE_UNDEFINED; + dp->dccps_service = DCCP_SERVICE_CODE_IS_ABSENT; + dp->dccps_l_ack_ratio = dp->dccps_r_ack_ratio = 1; + + dccp_init_xmit_timers(sk); + /* * FIXME: We're hardcoding the CCID, and doing this at this point makes * the listening (master) sock get CCID control blocks, which is not @@ -213,18 +247,6 @@ int dccp_init_sock(struct sock *sk, const __u8 ctl_sock_initialized) INIT_LIST_HEAD(&dmsk->dccpms_conf); } - dccp_init_xmit_timers(sk); - icsk->icsk_rto = DCCP_TIMEOUT_INIT; - icsk->icsk_syn_retries = sysctl_dccp_request_retries; - sk->sk_state = DCCP_CLOSED; - sk->sk_write_space = dccp_write_space; - icsk->icsk_sync_mss = dccp_sync_mss; - dp->dccps_mss_cache = 536; - dp->dccps_rate_last = jiffies; - dp->dccps_role = DCCP_ROLE_UNDEFINED; - dp->dccps_service = DCCP_SERVICE_CODE_IS_ABSENT; - dp->dccps_l_ack_ratio = dp->dccps_r_ack_ratio = 1; - return 0; } @@ -275,6 +297,12 @@ static inline int dccp_listen_start(struct sock *sk, int backlog) return inet_csk_listen_start(sk, backlog); } +static inline int dccp_need_reset(int state) +{ + return state != DCCP_CLOSED && state != DCCP_LISTEN && + state != DCCP_REQUESTING; +} + int dccp_disconnect(struct sock *sk, int flags) { struct inet_connection_sock *icsk = inet_csk(sk); @@ -285,10 +313,15 @@ int dccp_disconnect(struct sock *sk, int flags) if (old_state != DCCP_CLOSED) dccp_set_state(sk, DCCP_CLOSED); - /* ABORT function of RFC793 */ + /* + * This corresponds to the ABORT function of RFC793, sec. 3.8 + * TCP uses a RST segment, DCCP a Reset packet with Code 2, "Aborted". + */ if (old_state == DCCP_LISTEN) { inet_csk_listen_stop(sk); - /* FIXME: do the active reset thing */ + } else if (dccp_need_reset(old_state)) { + dccp_send_reset(sk, DCCP_RESET_CODE_ABORTED); + sk->sk_err = ECONNRESET; } else if (old_state == DCCP_REQUESTING) sk->sk_err = ECONNRESET; @@ -518,6 +551,12 @@ static int do_dccp_setsockopt(struct sock *sk, int level, int optname, (struct dccp_so_feat __user *) optval); break; + case DCCP_SOCKOPT_SERVER_TIMEWAIT: + if (dp->dccps_role != DCCP_ROLE_SERVER) + err = -EOPNOTSUPP; + else + dp->dccps_server_timewait = (val != 0); + break; case DCCP_SOCKOPT_SEND_CSCOV: /* sender side, RFC 4340, sec. 9.2 */ if (val < 0 || val > 15) err = -EINVAL; @@ -618,15 +657,15 @@ static int do_dccp_getsockopt(struct sock *sk, int level, int optname, (__be32 __user *)optval, optlen); case DCCP_SOCKOPT_GET_CUR_MPS: val = dp->dccps_mss_cache; - len = sizeof(val); + break; + case DCCP_SOCKOPT_SERVER_TIMEWAIT: + val = dp->dccps_server_timewait; break; case DCCP_SOCKOPT_SEND_CSCOV: val = dp->dccps_pcslen; - len = sizeof(val); break; case DCCP_SOCKOPT_RECV_CSCOV: val = dp->dccps_pcrlen; - len = sizeof(val); break; case 128 ... 191: return ccid_hc_rx_getsockopt(dp->dccps_hc_rx_ccid, sk, optname, @@ -638,6 +677,7 @@ static int do_dccp_getsockopt(struct sock *sk, int level, int optname, return -ENOPROTOOPT; } + len = sizeof(val); if (put_user(len, optlen) || copy_to_user(optval, &val, len)) return -EFAULT; @@ -748,19 +788,26 @@ int dccp_recvmsg(struct kiocb *iocb, struct sock *sk, struct msghdr *msg, dh = dccp_hdr(skb); - if (dh->dccph_type == DCCP_PKT_DATA || - dh->dccph_type == DCCP_PKT_DATAACK) + switch (dh->dccph_type) { + case DCCP_PKT_DATA: + case DCCP_PKT_DATAACK: goto found_ok_skb; - if (dh->dccph_type == DCCP_PKT_RESET || - dh->dccph_type == DCCP_PKT_CLOSE) { - dccp_pr_debug("found fin ok!\n"); + case DCCP_PKT_CLOSE: + case DCCP_PKT_CLOSEREQ: + if (!(flags & MSG_PEEK)) + dccp_finish_passive_close(sk); + /* fall through */ + case DCCP_PKT_RESET: + dccp_pr_debug("found fin (%s) ok!\n", + dccp_packet_name(dh->dccph_type)); len = 0; goto found_fin_ok; + default: + dccp_pr_debug("packet_type=%s\n", + dccp_packet_name(dh->dccph_type)); + sk_eat_skb(sk, skb, 0); } - dccp_pr_debug("packet_type=%s\n", - dccp_packet_name(dh->dccph_type)); - sk_eat_skb(sk, skb, 0); verify_sock_status: if (sock_flag(sk, SOCK_DONE)) { len = 0; @@ -862,34 +909,38 @@ out: EXPORT_SYMBOL_GPL(inet_dccp_listen); -static const unsigned char dccp_new_state[] = { - /* current state: new state: action: */ - [0] = DCCP_CLOSED, - [DCCP_OPEN] = DCCP_CLOSING | DCCP_ACTION_FIN, - [DCCP_REQUESTING] = DCCP_CLOSED, - [DCCP_PARTOPEN] = DCCP_CLOSING | DCCP_ACTION_FIN, - [DCCP_LISTEN] = DCCP_CLOSED, - [DCCP_RESPOND] = DCCP_CLOSED, - [DCCP_CLOSING] = DCCP_CLOSED, - [DCCP_TIME_WAIT] = DCCP_CLOSED, - [DCCP_CLOSED] = DCCP_CLOSED, -}; - -static int dccp_close_state(struct sock *sk) +static void dccp_terminate_connection(struct sock *sk) { - const int next = dccp_new_state[sk->sk_state]; - const int ns = next & DCCP_STATE_MASK; + u8 next_state = DCCP_CLOSED; - if (ns != sk->sk_state) - dccp_set_state(sk, ns); + switch (sk->sk_state) { + case DCCP_PASSIVE_CLOSE: + case DCCP_PASSIVE_CLOSEREQ: + dccp_finish_passive_close(sk); + break; + case DCCP_PARTOPEN: + dccp_pr_debug("Stop PARTOPEN timer (%p)\n", sk); + inet_csk_clear_xmit_timer(sk, ICSK_TIME_DACK); + /* fall through */ + case DCCP_OPEN: + dccp_send_close(sk, 1); - return next & DCCP_ACTION_FIN; + if (dccp_sk(sk)->dccps_role == DCCP_ROLE_SERVER && + !dccp_sk(sk)->dccps_server_timewait) + next_state = DCCP_ACTIVE_CLOSEREQ; + else + next_state = DCCP_CLOSING; + /* fall through */ + default: + dccp_set_state(sk, next_state); + } } void dccp_close(struct sock *sk, long timeout) { struct dccp_sock *dp = dccp_sk(sk); struct sk_buff *skb; + u32 data_was_unread = 0; int state; lock_sock(sk); @@ -912,16 +963,21 @@ void dccp_close(struct sock *sk, long timeout) * descriptor close, not protocol-sourced closes, because the *reader process may not have drained the data yet! */ - /* FIXME: check for unread data */ while ((skb = __skb_dequeue(&sk->sk_receive_queue)) != NULL) { + data_was_unread += skb->len; __kfree_skb(skb); } - if (sock_flag(sk, SOCK_LINGER) && !sk->sk_lingertime) { + if (data_was_unread) { + /* Unread data was tossed, send an appropriate Reset Code */ + DCCP_WARN("DCCP: ABORT -- %u bytes unread\n", data_was_unread); + dccp_send_reset(sk, DCCP_RESET_CODE_ABORTED); + dccp_set_state(sk, DCCP_CLOSED); + } else if (sock_flag(sk, SOCK_LINGER) && !sk->sk_lingertime) { /* Check zero linger _after_ checking for unread data. */ sk->sk_prot->disconnect(sk, 0); - } else if (dccp_close_state(sk)) { - dccp_send_close(sk, 1); + } else if (sk->sk_state != DCCP_CLOSED) { + dccp_terminate_connection(sk); } sk_stream_wait_close(sk, timeout); @@ -948,24 +1004,6 @@ adjudge_to_death: if (state != DCCP_CLOSED && sk->sk_state == DCCP_CLOSED) goto out; - /* - * The last release_sock may have processed the CLOSE or RESET - * packet moving sock to CLOSED state, if not we have to fire - * the CLOSE/CLOSEREQ retransmission timer, see "8.3. Termination" - * in draft-ietf-dccp-spec-11. -acme - */ - if (sk->sk_state == DCCP_CLOSING) { - /* FIXME: should start at 2 * RTT */ - /* Timer for repeating the CLOSE/CLOSEREQ until an answer. */ - inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS, - inet_csk(sk)->icsk_rto, - DCCP_RTO_MAX); -#if 0 - /* Yeah, we should use sk->sk_prot->orphan_count, etc */ - dccp_set_state(sk, DCCP_CLOSED); -#endif - } - if (sk->sk_state == DCCP_CLOSED) inet_csk_destroy_sock(sk); @@ -981,7 +1019,7 @@ EXPORT_SYMBOL_GPL(dccp_close); void dccp_shutdown(struct sock *sk, int how) { - dccp_pr_debug("entry\n"); + dccp_pr_debug("called shutdown(%x)\n", how); } EXPORT_SYMBOL_GPL(dccp_shutdown); diff --git a/net/dccp/sysctl.c b/net/dccp/sysctl.c index c62c05039f69..21295993fdb8 100644 --- a/net/dccp/sysctl.c +++ b/net/dccp/sysctl.c @@ -100,41 +100,19 @@ static struct ctl_table dccp_default_table[] = { { .ctl_name = 0, } }; -static struct ctl_table dccp_table[] = { - { - .ctl_name = NET_DCCP_DEFAULT, - .procname = "default", - .mode = 0555, - .child = dccp_default_table, - }, - { .ctl_name = 0, }, -}; - -static struct ctl_table dccp_dir_table[] = { - { - .ctl_name = NET_DCCP, - .procname = "dccp", - .mode = 0555, - .child = dccp_table, - }, - { .ctl_name = 0, }, -}; - -static struct ctl_table dccp_root_table[] = { - { - .ctl_name = CTL_NET, - .procname = "net", - .mode = 0555, - .child = dccp_dir_table, - }, - { .ctl_name = 0, }, +static struct ctl_path dccp_path[] = { + { .procname = "net", .ctl_name = CTL_NET, }, + { .procname = "dccp", .ctl_name = NET_DCCP, }, + { .procname = "default", .ctl_name = NET_DCCP_DEFAULT, }, + { } }; static struct ctl_table_header *dccp_table_header; int __init dccp_sysctl_init(void) { - dccp_table_header = register_sysctl_table(dccp_root_table); + dccp_table_header = register_sysctl_paths(dccp_path, + dccp_default_table); return dccp_table_header != NULL ? 0 : -ENOMEM; } diff --git a/net/dccp/timer.c b/net/dccp/timer.c index 3af067354bd4..8703a792b560 100644 --- a/net/dccp/timer.c +++ b/net/dccp/timer.c @@ -280,9 +280,8 @@ static void dccp_init_write_xmit_timer(struct sock *sk) { struct dccp_sock *dp = dccp_sk(sk); - init_timer(&dp->dccps_xmit_timer); - dp->dccps_xmit_timer.data = (unsigned long)sk; - dp->dccps_xmit_timer.function = dccp_write_xmit_timer; + setup_timer(&dp->dccps_xmit_timer, dccp_write_xmit_timer, + (unsigned long)sk); } void dccp_init_xmit_timers(struct sock *sk) |