2c77dafbd091f9c4627097b037b0a816bf18301e
[linux-2.6.git] / net / dccp / ackvec.c
1 /*
2  *  net/dccp/ackvec.c
3  *
4  *  An implementation of the DCCP protocol
5  *  Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@ghostprotocols.net>
6  *
7  *      This program is free software; you can redistribute it and/or modify it
8  *      under the terms of the GNU General Public License as published by the
9  *      Free Software Foundation; version 2 of the License;
10  */
11
12 #include "ackvec.h"
13 #include "dccp.h"
14
15 #include <linux/dccp.h>
16 #include <linux/skbuff.h>
17
18 #include <net/sock.h>
19
20 int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb)
21 {
22         struct dccp_sock *dp = dccp_sk(sk);
23         struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec;
24         int len = av->dccpav_vec_len + 2;
25         struct timeval now;
26         u32 elapsed_time;
27         unsigned char *to, *from;
28
29         dccp_timestamp(sk, &now);
30         elapsed_time = timeval_delta(&now, &av->dccpav_time) / 10;
31
32         if (elapsed_time != 0)
33                 dccp_insert_option_elapsed_time(sk, skb, elapsed_time);
34
35         if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN)
36                 return -1;
37
38         /*
39          * XXX: now we have just one ack vector sent record, so
40          * we have to wait for it to be cleared.
41          *
42          * Of course this is not acceptable, but this is just for
43          * basic testing now.
44          */
45         if (av->dccpav_ack_seqno != DCCP_MAX_SEQNO + 1)
46                 return -1;
47
48         DCCP_SKB_CB(skb)->dccpd_opt_len += len;
49
50         to    = skb_push(skb, len);
51         *to++ = DCCPO_ACK_VECTOR_0;
52         *to++ = len;
53
54         len  = av->dccpav_vec_len;
55         from = av->dccpav_buf + av->dccpav_buf_head;
56
57         /* Check if buf_head wraps */
58         if ((int)av->dccpav_buf_head + len > av->dccpav_vec_len) {
59                 const u32 tailsize = av->dccpav_vec_len - av->dccpav_buf_head;
60
61                 memcpy(to, from, tailsize);
62                 to   += tailsize;
63                 len  -= tailsize;
64                 from = av->dccpav_buf;
65         }
66
67         memcpy(to, from, len);
68         /*
69          *      From draft-ietf-dccp-spec-11.txt:
70          *
71          *      For each acknowledgement it sends, the HC-Receiver will add an
72          *      acknowledgement record.  ack_seqno will equal the HC-Receiver
73          *      sequence number it used for the ack packet; ack_ptr will equal
74          *      buf_head; ack_ackno will equal buf_ackno; and ack_nonce will
75          *      equal buf_nonce.
76          *
77          * This implemention uses just one ack record for now.
78          */
79         av->dccpav_ack_seqno = DCCP_SKB_CB(skb)->dccpd_seq;
80         av->dccpav_ack_ptr   = av->dccpav_buf_head;
81         av->dccpav_ack_ackno = av->dccpav_buf_ackno;
82         av->dccpav_ack_nonce = av->dccpav_buf_nonce;
83         av->dccpav_sent_len  = av->dccpav_vec_len;
84
85         dccp_pr_debug("%sACK Vector 0, len=%d, ack_seqno=%llu, "
86                       "ack_ackno=%llu\n",
87                       debug_prefix, av->dccpav_sent_len,
88                       (unsigned long long)av->dccpav_ack_seqno,
89                       (unsigned long long)av->dccpav_ack_ackno);
90         return -1;
91 }
92
93 struct dccp_ackvec *dccp_ackvec_alloc(const unsigned int len,
94                                       const gfp_t priority)
95 {
96         struct dccp_ackvec *av;
97
98         BUG_ON(len == 0);
99
100         if (len > DCCP_MAX_ACKVEC_LEN)
101                 return NULL;
102
103         av = kmalloc(sizeof(*av) + len, priority);
104         if (av != NULL) {
105                 av->dccpav_buf_len      = len;
106                 av->dccpav_buf_head     =
107                         av->dccpav_buf_tail = av->dccpav_buf_len - 1;
108                 av->dccpav_buf_ackno    =
109                         av->dccpav_ack_ackno = av->dccpav_ack_seqno = ~0LLU;
110                 av->dccpav_buf_nonce = av->dccpav_buf_nonce = 0;
111                 av->dccpav_ack_ptr      = 0;
112                 av->dccpav_time.tv_sec  = 0;
113                 av->dccpav_time.tv_usec = 0;
114                 av->dccpav_sent_len     = av->dccpav_vec_len = 0;
115         }
116
117         return av;
118 }
119
120 void dccp_ackvec_free(struct dccp_ackvec *av)
121 {
122         kfree(av);
123 }
124
125 static inline u8 dccp_ackvec_state(const struct dccp_ackvec *av,
126                                    const u8 index)
127 {
128         return av->dccpav_buf[index] & DCCP_ACKVEC_STATE_MASK;
129 }
130
131 static inline u8 dccp_ackvec_len(const struct dccp_ackvec *av,
132                                  const u8 index)
133 {
134         return av->dccpav_buf[index] & DCCP_ACKVEC_LEN_MASK;
135 }
136
137 /*
138  * If several packets are missing, the HC-Receiver may prefer to enter multiple
139  * bytes with run length 0, rather than a single byte with a larger run length;
140  * this simplifies table updates if one of the missing packets arrives.
141  */
142 static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av,
143                                                  const unsigned int packets,
144                                                  const unsigned char state)
145 {
146         unsigned int gap;
147         long new_head;
148
149         if (av->dccpav_vec_len + packets > av->dccpav_buf_len)
150                 return -ENOBUFS;
151
152         gap      = packets - 1;
153         new_head = av->dccpav_buf_head - packets;
154
155         if (new_head < 0) {
156                 if (gap > 0) {
157                         memset(av->dccpav_buf, DCCP_ACKVEC_STATE_NOT_RECEIVED,
158                                gap + new_head + 1);
159                         gap = -new_head;
160                 }
161                 new_head += av->dccpav_buf_len;
162         } 
163
164         av->dccpav_buf_head = new_head;
165
166         if (gap > 0)
167                 memset(av->dccpav_buf + av->dccpav_buf_head + 1,
168                        DCCP_ACKVEC_STATE_NOT_RECEIVED, gap);
169
170         av->dccpav_buf[av->dccpav_buf_head] = state;
171         av->dccpav_vec_len += packets;
172         return 0;
173 }
174
175 /*
176  * Implements the draft-ietf-dccp-spec-11.txt Appendix A
177  */
178 int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
179                     const u64 ackno, const u8 state)
180 {
181         /*
182          * Check at the right places if the buffer is full, if it is, tell the
183          * caller to start dropping packets till the HC-Sender acks our ACK
184          * vectors, when we will free up space in dccpav_buf.
185          *
186          * We may well decide to do buffer compression, etc, but for now lets
187          * just drop.
188          *
189          * From Appendix A:
190          *
191          *      Of course, the circular buffer may overflow, either when the
192          *      HC-Sender is sending data at a very high rate, when the
193          *      HC-Receiver's acknowledgements are not reaching the HC-Sender,
194          *      or when the HC-Sender is forgetting to acknowledge those acks
195          *      (so the HC-Receiver is unable to clean up old state). In this
196          *      case, the HC-Receiver should either compress the buffer (by
197          *      increasing run lengths when possible), transfer its state to
198          *      a larger buffer, or, as a last resort, drop all received
199          *      packets, without processing them whatsoever, until its buffer
200          *      shrinks again.
201          */
202
203         /* See if this is the first ackno being inserted */
204         if (av->dccpav_vec_len == 0) {
205                 av->dccpav_buf[av->dccpav_buf_head] = state;
206                 av->dccpav_vec_len = 1;
207         } else if (after48(ackno, av->dccpav_buf_ackno)) {
208                 const u64 delta = dccp_delta_seqno(av->dccpav_buf_ackno,
209                                                    ackno);
210
211                 /*
212                  * Look if the state of this packet is the same as the
213                  * previous ackno and if so if we can bump the head len.
214                  */
215                 if (delta == 1 &&
216                     dccp_ackvec_state(av, av->dccpav_buf_head) == state &&
217                     (dccp_ackvec_len(av, av->dccpav_buf_head) <
218                      DCCP_ACKVEC_LEN_MASK))
219                         av->dccpav_buf[av->dccpav_buf_head]++;
220                 else if (dccp_ackvec_set_buf_head_state(av, delta, state))
221                         return -ENOBUFS;
222         } else {
223                 /*
224                  * A.1.2.  Old Packets
225                  *
226                  *      When a packet with Sequence Number S arrives, and
227                  *      S <= buf_ackno, the HC-Receiver will scan the table
228                  *      for the byte corresponding to S. (Indexing structures
229                  *      could reduce the complexity of this scan.)
230                  */
231                 u64 delta = dccp_delta_seqno(ackno, av->dccpav_buf_ackno);
232                 u8 index = av->dccpav_buf_head;
233
234                 while (1) {
235                         const u8 len = dccp_ackvec_len(av, index);
236                         const u8 state = dccp_ackvec_state(av, index);
237                         /*
238                          * valid packets not yet in dccpav_buf have a reserved
239                          * entry, with a len equal to 0.
240                          */
241                         if (state == DCCP_ACKVEC_STATE_NOT_RECEIVED &&
242                             len == 0 && delta == 0) { /* Found our
243                                                          reserved seat! */
244                                 dccp_pr_debug("Found %llu reserved seat!\n",
245                                               (unsigned long long)ackno);
246                                 av->dccpav_buf[index] = state;
247                                 goto out;
248                         }
249                         /* len == 0 means one packet */
250                         if (delta < len + 1)
251                                 goto out_duplicate;
252
253                         delta -= len + 1;
254                         if (++index == av->dccpav_buf_len)
255                                 index = 0;
256                 }
257         }
258
259         av->dccpav_buf_ackno = ackno;
260         dccp_timestamp(sk, &av->dccpav_time);
261 out:
262         dccp_pr_debug("");
263         return 0;
264
265 out_duplicate:
266         /* Duplicate packet */
267         dccp_pr_debug("Received a dup or already considered lost "
268                       "packet: %llu\n", (unsigned long long)ackno);
269         return -EILSEQ;
270 }
271
272 #ifdef CONFIG_IP_DCCP_DEBUG
273 void dccp_ackvector_print(const u64 ackno, const unsigned char *vector, int len)
274 {
275         if (!dccp_debug)
276                 return;
277
278         printk("ACK vector len=%d, ackno=%llu |", len,
279                (unsigned long long)ackno);
280
281         while (len--) {
282                 const u8 state = (*vector & DCCP_ACKVEC_STATE_MASK) >> 6;
283                 const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK;
284
285                 printk("%d,%d|", state, rl);
286                 ++vector;
287         }
288
289         printk("\n");
290 }
291
292 void dccp_ackvec_print(const struct dccp_ackvec *av)
293 {
294         dccp_ackvector_print(av->dccpav_buf_ackno,
295                              av->dccpav_buf + av->dccpav_buf_head,
296                              av->dccpav_vec_len);
297 }
298 #endif
299
300 static void dccp_ackvec_throw_away_ack_record(struct dccp_ackvec *av)
301 {
302         /*
303          * As we're keeping track of the ack vector size (dccpav_vec_len) and
304          * the sent ack vector size (dccpav_sent_len) we don't need
305          * dccpav_buf_tail at all, but keep this code here as in the future
306          * we'll implement a vector of ack records, as suggested in
307          * draft-ietf-dccp-spec-11.txt Appendix A. -acme
308          */
309 #if 0
310         u32 new_buf_tail = av->dccpav_ack_ptr + 1;
311         if (new_buf_tail >= av->dccpav_vec_len)
312                 new_buf_tail -= av->dccpav_vec_len;
313         av->dccpav_buf_tail = new_buf_tail;
314 #endif
315         av->dccpav_vec_len -= av->dccpav_sent_len;
316 }
317
318 void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk,
319                                  const u64 ackno)
320 {
321         /* Check if we actually sent an ACK vector */
322         if (av->dccpav_ack_seqno == DCCP_MAX_SEQNO + 1)
323                 return;
324
325         if (ackno == av->dccpav_ack_seqno) {
326 #ifdef CONFIG_IP_DCCP_DEBUG
327                 struct dccp_sock *dp = dccp_sk(sk);
328                 const char *debug_prefix = dp->dccps_role == DCCP_ROLE_CLIENT ?
329                                         "CLIENT rx ack: " : "server rx ack: ";
330 #endif
331                 dccp_pr_debug("%sACK packet 0, len=%d, ack_seqno=%llu, "
332                               "ack_ackno=%llu, ACKED!\n",
333                               debug_prefix, 1,
334                               (unsigned long long)av->dccpav_ack_seqno,
335                               (unsigned long long)av->dccpav_ack_ackno);
336                 dccp_ackvec_throw_away_ack_record(av);
337                 av->dccpav_ack_seqno = DCCP_MAX_SEQNO + 1;
338         }
339 }
340
341 static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av,
342                                             struct sock *sk, u64 ackno,
343                                             const unsigned char len,
344                                             const unsigned char *vector)
345 {
346         unsigned char i;
347
348         /* Check if we actually sent an ACK vector */
349         if (av->dccpav_ack_seqno == DCCP_MAX_SEQNO + 1)
350                 return;
351         /*
352          * We're in the receiver half connection, so if the received an ACK
353          * vector ackno (e.g. 50) before dccpav_ack_seqno (e.g. 52), we're
354          * not interested.
355          *
356          * Extra explanation with example:
357          * 
358          * if we received an ACK vector with ackno 50, it can only be acking
359          * 50, 49, 48, etc, not 52 (the seqno for the ACK vector we sent).
360          */
361         /* dccp_pr_debug("is %llu < %llu? ", ackno, av->dccpav_ack_seqno); */
362         if (before48(ackno, av->dccpav_ack_seqno)) {
363                 /* dccp_pr_debug_cat("yes\n"); */
364                 return;
365         }
366         /* dccp_pr_debug_cat("no\n"); */
367
368         i = len;
369         while (i--) {
370                 const u8 rl = *vector & DCCP_ACKVEC_LEN_MASK;
371                 u64 ackno_end_rl;
372
373                 dccp_set_seqno(&ackno_end_rl, ackno - rl);
374
375                 /*
376                  * dccp_pr_debug("is %llu <= %llu <= %llu? ", ackno_end_rl,
377                  * av->dccpav_ack_seqno, ackno);
378                  */
379                 if (between48(av->dccpav_ack_seqno, ackno_end_rl, ackno)) {
380                         const u8 state = (*vector &
381                                           DCCP_ACKVEC_STATE_MASK) >> 6;
382                         /* dccp_pr_debug_cat("yes\n"); */
383
384                         if (state != DCCP_ACKVEC_STATE_NOT_RECEIVED) {
385 #ifdef CONFIG_IP_DCCP_DEBUG
386                                 struct dccp_sock *dp = dccp_sk(sk);
387                                 const char *debug_prefix =
388                                         dp->dccps_role == DCCP_ROLE_CLIENT ?
389                                         "CLIENT rx ack: " : "server rx ack: ";
390 #endif
391                                 dccp_pr_debug("%sACK vector 0, len=%d, "
392                                               "ack_seqno=%llu, ack_ackno=%llu, "
393                                               "ACKED!\n",
394                                               debug_prefix, len,
395                                               (unsigned long long)
396                                               av->dccpav_ack_seqno,
397                                               (unsigned long long)
398                                               av->dccpav_ack_ackno);
399                                 dccp_ackvec_throw_away_ack_record(av);
400                         }
401                         /*
402                          * If dccpav_ack_seqno was not received, no problem
403                          * we'll send another ACK vector.
404                          */
405                         av->dccpav_ack_seqno = DCCP_MAX_SEQNO + 1;
406                         break;
407                 }
408                 /* dccp_pr_debug_cat("no\n"); */
409
410                 dccp_set_seqno(&ackno, ackno_end_rl - 1);
411                 ++vector;
412         }
413 }
414
415 int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb,
416                       const u8 opt, const u8 *value, const u8 len)
417 {
418         if (len > DCCP_MAX_ACKVEC_LEN)
419                 return -1;
420
421         /* dccp_ackvector_print(DCCP_SKB_CB(skb)->dccpd_ack_seq, value, len); */
422         dccp_ackvec_check_rcv_ackvector(dccp_sk(sk)->dccps_hc_rx_ackvec, sk,
423                                         DCCP_SKB_CB(skb)->dccpd_ack_seq,
424                                         len, value);
425         return 0;
426 }