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 }