aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorGerrit Renker <gerrit@erg.abdn.ac.uk>2008-09-04 01:30:19 -0400
committerGerrit Renker <gerrit@erg.abdn.ac.uk>2008-09-04 01:45:37 -0400
commit68b1de15765f2b0e0925e692dab2b2fa2abd93fc (patch)
tree893594a088a7d9ba4bff6c1820ec014740ca62bf
parentd7dc7e5f49299739e610ea8febf9ea91a4dc1ae9 (diff)
dccp ccid-2: Algorithm to update buffer state
This provides a routine to consistently update the buffer state when the peer acknowledges receipt of Ack Vectors; updating state in the list of Ack Vectors as well as in the circular buffer. While based on RFC 4340, several additional (and necessary) precautions were added to protect the consistency of the buffer state. These additions are essential, since analysis and experience showed that the basic algorithm was insufficient for this task (which lead to problems that were hard to debug). The algorithm now * deals with HC-sender acknowledging to HC-receiver and vice versa, * keeps track of the last unacknowledged but received seqno in tail_ackno, * has special cases to reset the overflow condition when appropriate, * is protected against receiving older information (would mess up buffer state). Note: The older code performed an unnecessary step, where the sender cleared Ack Vector state by parsing the Ack Vector received by the HC-receiver. Doing this was entirely redundant, since * the receiver always puts the full acknowledgment window (groups 2,3 in 11.4.2) into the Ack Vectors it sends; hence the HC-receiver is only interested in the highest state that the HC-sender received; * this means that the acknowledgment number on the (Data)Ack from the HC-sender is sufficient; and work done in parsing earlier state is not necessary, since the later state subsumes the earlier one (see also RFC 4340, A.4). This older interface (dccp_ackvec_parse()) is therefore removed. Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
-rw-r--r--net/dccp/ackvec.c88
-rw-r--r--net/dccp/ackvec.h6
-rw-r--r--net/dccp/input.c4
-rw-r--r--net/dccp/options.c6
4 files changed, 98 insertions, 6 deletions
diff --git a/net/dccp/ackvec.c b/net/dccp/ackvec.c
index 1184d5e5dc96..f1341a617f96 100644
--- a/net/dccp/ackvec.c
+++ b/net/dccp/ackvec.c
@@ -92,6 +92,24 @@ int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seqno, u8 nonce_sum)
92 return 0; 92 return 0;
93} 93}
94 94
95static struct dccp_ackvec_record *dccp_ackvec_lookup(struct list_head *av_list,
96 const u64 ackno)
97{
98 struct dccp_ackvec_record *avr;
99 /*
100 * Exploit that records are inserted in descending order of sequence
101 * number, start with the oldest record first. If @ackno is `before'
102 * the earliest ack_ackno, the packet is too old to be considered.
103 */
104 list_for_each_entry_reverse(avr, av_list, avr_node) {
105 if (avr->avr_ack_seqno == ackno)
106 return avr;
107 if (before48(ackno, avr->avr_ack_seqno))
108 break;
109 }
110 return NULL;
111}
112
95/* 113/*
96 * Buffer index and length computation using modulo-buffersize arithmetic. 114 * Buffer index and length computation using modulo-buffersize arithmetic.
97 * Note that, as pointers move from right to left, head is `before' tail. 115 * Note that, as pointers move from right to left, head is `before' tail.
@@ -356,6 +374,76 @@ int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb,
356 return 0; 374 return 0;
357} 375}
358 376
377/**
378 * dccp_ackvec_clear_state - Perform house-keeping / garbage-collection
379 * This routine is called when the peer acknowledges the receipt of Ack Vectors
380 * up to and including @ackno. While based on on section A.3 of RFC 4340, here
381 * are additional precautions to prevent corrupted buffer state. In particular,
382 * we use tail_ackno to identify outdated records; it always marks the earliest
383 * packet of group (2) in 11.4.2.
384 */
385void dccp_ackvec_clear_state(struct dccp_ackvec *av, const u64 ackno)
386 {
387 struct dccp_ackvec_record *avr, *next;
388 u8 runlen_now, eff_runlen;
389 s64 delta;
390
391 avr = dccp_ackvec_lookup(&av->av_records, ackno);
392 if (avr == NULL)
393 return;
394 /*
395 * Deal with outdated acknowledgments: this arises when e.g. there are
396 * several old records and the acks from the peer come in slowly. In
397 * that case we may still have records that pre-date tail_ackno.
398 */
399 delta = dccp_delta_seqno(av->av_tail_ackno, avr->avr_ack_ackno);
400 if (delta < 0)
401 goto free_records;
402 /*
403 * Deal with overlapping Ack Vectors: don't subtract more than the
404 * number of packets between tail_ackno and ack_ackno.
405 */
406 eff_runlen = delta < avr->avr_ack_runlen ? delta : avr->avr_ack_runlen;
407
408 runlen_now = dccp_ackvec_runlen(av->av_buf + avr->avr_ack_ptr);
409 /*
410 * The run length of Ack Vector cells does not decrease over time. If
411 * the run length is the same as at the time the Ack Vector was sent, we
412 * free the ack_ptr cell. That cell can however not be freed if the run
413 * length has increased: in this case we need to move the tail pointer
414 * backwards (towards higher indices), to its next-oldest neighbour.
415 */
416 if (runlen_now > eff_runlen) {
417
418 av->av_buf[avr->avr_ack_ptr] -= eff_runlen + 1;
419 av->av_buf_tail = __ackvec_idx_add(avr->avr_ack_ptr, 1);
420
421 /* This move may not have cleared the overflow flag. */
422 if (av->av_overflow)
423 av->av_overflow = (av->av_buf_head == av->av_buf_tail);
424 } else {
425 av->av_buf_tail = avr->avr_ack_ptr;
426 /*
427 * We have made sure that avr points to a valid cell within the
428 * buffer. This cell is either older than head, or equals head
429 * (empty buffer): in both cases we no longer have any overflow.
430 */
431 av->av_overflow = 0;
432 }
433
434 /*
435 * The peer has acknowledged up to and including ack_ackno. Hence the
436 * first packet in group (2) of 11.4.2 is the successor of ack_ackno.
437 */
438 av->av_tail_ackno = ADD48(avr->avr_ack_ackno, 1);
439
440free_records:
441 list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) {
442 list_del(&avr->avr_node);
443 kmem_cache_free(dccp_ackvec_record_slab, avr);
444 }
445}
446
359int __init dccp_ackvec_init(void) 447int __init dccp_ackvec_init(void)
360{ 448{
361 dccp_ackvec_slab = kmem_cache_create("dccp_ackvec", 449 dccp_ackvec_slab = kmem_cache_create("dccp_ackvec",
diff --git a/net/dccp/ackvec.h b/net/dccp/ackvec.h
index 92f65b0fef5b..b757e9b4110f 100644
--- a/net/dccp/ackvec.h
+++ b/net/dccp/ackvec.h
@@ -118,6 +118,7 @@ extern int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb,
118 const u8 *value, const u8 len); 118 const u8 *value, const u8 len);
119 119
120extern int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seq, u8 sum); 120extern int dccp_ackvec_update_records(struct dccp_ackvec *av, u64 seq, u8 sum);
121extern void dccp_ackvec_clear_state(struct dccp_ackvec *av, const u64 ackno);
121extern u16 dccp_ackvec_buflen(const struct dccp_ackvec *av); 122extern u16 dccp_ackvec_buflen(const struct dccp_ackvec *av);
122 123
123static inline bool dccp_ackvec_is_empty(const struct dccp_ackvec *av) 124static inline bool dccp_ackvec_is_empty(const struct dccp_ackvec *av)
@@ -149,6 +150,11 @@ static inline int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
149 return -1; 150 return -1;
150} 151}
151 152
153static inline void dccp_ackvec_clear_state(struct dccp_ackvec *av,
154 const u64 ackno)
155{
156}
157
152static inline void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, 158static inline void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av,
153 struct sock *sk, const u64 ackno) 159 struct sock *sk, const u64 ackno)
154{ 160{
diff --git a/net/dccp/input.c b/net/dccp/input.c
index 70ad0ba72146..77a5d57ab702 100644
--- a/net/dccp/input.c
+++ b/net/dccp/input.c
@@ -164,8 +164,8 @@ static void dccp_event_ack_recv(struct sock *sk, struct sk_buff *skb)
164 struct dccp_sock *dp = dccp_sk(sk); 164 struct dccp_sock *dp = dccp_sk(sk);
165 165
166 if (dp->dccps_hc_rx_ackvec != NULL) 166 if (dp->dccps_hc_rx_ackvec != NULL)
167 dccp_ackvec_check_rcv_ackno(dp->dccps_hc_rx_ackvec, sk, 167 dccp_ackvec_clear_state(dp->dccps_hc_rx_ackvec,
168 DCCP_SKB_CB(skb)->dccpd_ack_seq); 168 DCCP_SKB_CB(skb)->dccpd_ack_seq);
169} 169}
170 170
171static void dccp_deliver_input_to_ccids(struct sock *sk, struct sk_buff *skb) 171static void dccp_deliver_input_to_ccids(struct sock *sk, struct sk_buff *skb)
diff --git a/net/dccp/options.c b/net/dccp/options.c
index 3163ae980f16..b11d7b7167f0 100644
--- a/net/dccp/options.c
+++ b/net/dccp/options.c
@@ -54,7 +54,6 @@ int dccp_parse_options(struct sock *sk, struct dccp_request_sock *dreq,
54 struct dccp_sock *dp = dccp_sk(sk); 54 struct dccp_sock *dp = dccp_sk(sk);
55 const struct dccp_hdr *dh = dccp_hdr(skb); 55 const struct dccp_hdr *dh = dccp_hdr(skb);
56 const u8 pkt_type = DCCP_SKB_CB(skb)->dccpd_type; 56 const u8 pkt_type = DCCP_SKB_CB(skb)->dccpd_type;
57 u64 ackno = DCCP_SKB_CB(skb)->dccpd_ack_seq;
58 unsigned char *options = (unsigned char *)dh + dccp_hdr_len(skb); 57 unsigned char *options = (unsigned char *)dh + dccp_hdr_len(skb);
59 unsigned char *opt_ptr = options; 58 unsigned char *opt_ptr = options;
60 const unsigned char *opt_end = (unsigned char *)dh + 59 const unsigned char *opt_end = (unsigned char *)dh +
@@ -133,9 +132,8 @@ int dccp_parse_options(struct sock *sk, struct dccp_request_sock *dreq,
133 case DCCPO_ACK_VECTOR_1: 132 case DCCPO_ACK_VECTOR_1:
134 if (dccp_packet_without_ack(skb)) /* RFC 4340, 11.4 */ 133 if (dccp_packet_without_ack(skb)) /* RFC 4340, 11.4 */
135 break; 134 break;
136 if (dp->dccps_hc_rx_ackvec != NULL && 135 dccp_pr_debug("%s Ack Vector (len=%u)\n", dccp_role(sk),
137 dccp_ackvec_parse(sk, skb, &ackno, opt, value, len)) 136 len);
138 goto out_invalid_option;
139 break; 137 break;
140 case DCCPO_TIMESTAMP: 138 case DCCPO_TIMESTAMP:
141 if (len != 4) 139 if (len != 4)