net/dccp/ackvec.c

   1 /*
   2  *  net/dccp/ackvec.c
   3  *
   4  *  An implementation of Ack Vectors for the DCCP protocol
   5  *  Copyright (c) 2007 University of Aberdeen, Scotland, UK
   6  *  Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@ghostprotocols.net>
   7  *
   8  *      This program is free software; you can redistribute it and/or modify it
   9  *      under the terms of the GNU General Public License as published by the
  10  *      Free Software Foundation; version 2 of the License;
  11  */
  12
  13 #include "ackvec.h"
  14 #include "dccp.h"
  15
  16 #include <linux/init.h>
  17 #include <linux/errno.h>
  18 #include <linux/kernel.h>
  19 #include <linux/skbuff.h>
  20 #include <linux/slab.h>
  21
  22 #include <net/sock.h>
  23
  24 static struct kmem_cache *dccp_ackvec_slab;
  25 static struct kmem_cache *dccp_ackvec_record_slab;
  26
  27 struct dccp_ackvec *dccp_ackvec_alloc(const gfp_t priority)
  28 {
  29         struct dccp_ackvec *av = kmem_cache_zalloc(dccp_ackvec_slab, priority);
  30
  31         if (av != NULL) {
  32                 av->av_buf_head = DCCPAV_MAX_ACKVEC_LEN - 1;
  33                 INIT_LIST_HEAD(&av->av_records);
  34         }
  35         return av;
  36 }
  37
  38 static void dccp_ackvec_purge_records(struct dccp_ackvec *av)
  39 {
  40         struct dccp_ackvec_record *cur, *next;
  41
  42         list_for_each_entry_safe(cur, next, &av->av_records, avr_node)
  43                 kmem_cache_free(dccp_ackvec_record_slab, cur);
  44         INIT_LIST_HEAD(&av->av_records);
  45 }
  46
  47 void dccp_ackvec_free(struct dccp_ackvec *av)
  48 {
  49         if (likely(av != NULL)) {
  50                 dccp_ackvec_purge_records(av);
  51                 kmem_cache_free(dccp_ackvec_slab, av);
  52         }
  53 }
  54
  55 static void dccp_ackvec_insert_avr(struct dccp_ackvec *av,
  56                                    struct dccp_ackvec_record *avr)
  57 {
  58         /*
  59          * AVRs are sorted by seqno. Since we are sending them in order, we
  60          * just add the AVR at the head of the list.
  61          * -sorbo.
  62          */
  63         if (!list_empty(&av->av_records)) {
  64                 const struct dccp_ackvec_record *head =
  65                                         list_entry(av->av_records.next,
  66                                                    struct dccp_ackvec_record,
  67                                                    avr_node);
  68                 BUG_ON(before48(avr->avr_ack_seqno, head->avr_ack_seqno));
  69         }
  70
  71         list_add(&avr->avr_node, &av->av_records);
  72 }
  73
  74 int dccp_insert_option_ackvec(struct sock *sk, struct sk_buff *skb)
  75 {
  76         struct dccp_sock *dp = dccp_sk(sk);
  77         struct dccp_ackvec *av = dp->dccps_hc_rx_ackvec;
  78         /* Figure out how many options do we need to represent the ackvec */
  79         const u8 nr_opts = DIV_ROUND_UP(av->av_vec_len, DCCP_SINGLE_OPT_MAXLEN);
  80         u16 len = av->av_vec_len + 2 * nr_opts;
  81         u8 i, nonce = 0;
  82         const unsigned char *tail, *from;
  83         unsigned char *to;
  84         struct dccp_ackvec_record *avr;
  85
  86         if (DCCP_SKB_CB(skb)->dccpd_opt_len + len > DCCP_MAX_OPT_LEN)
  87                 return -1;
  88
  89         avr = kmem_cache_alloc(dccp_ackvec_record_slab, GFP_ATOMIC);
  90         if (avr == NULL)
  91                 return -1;
  92
  93         DCCP_SKB_CB(skb)->dccpd_opt_len += len;
  94
  95         to   = skb_push(skb, len);
  96         len  = av->av_vec_len;
  97         from = av->av_buf + av->av_buf_head;
  98         tail = av->av_buf + DCCPAV_MAX_ACKVEC_LEN;
  99
 100         for (i = 0; i < nr_opts; ++i) {
 101                 int copylen = len;
 102
 103                 if (len > DCCP_SINGLE_OPT_MAXLEN)
 104                         copylen = DCCP_SINGLE_OPT_MAXLEN;
 105
 106                 /*
 107                  * RFC 4340, 12.2: Encode the Nonce Echo for this Ack Vector via
 108                  * its type; ack_nonce is the sum of all individual buf_nonce's.
 109                  */
 110                 nonce ^= av->av_buf_nonce[i];
 111
 112                 *to++ = DCCPO_ACK_VECTOR_0 + av->av_buf_nonce[i];
 113                 *to++ = copylen + 2;
 114
 115                 /* Check if buf_head wraps */
 116                 if (from + copylen > tail) {
 117                         const u16 tailsize = tail - from;
 118
 119                         memcpy(to, from, tailsize);
 120                         to      += tailsize;
 121                         len     -= tailsize;
 122                         copylen -= tailsize;
 123                         from    = av->av_buf;
 124                 }
 125
 126                 memcpy(to, from, copylen);
 127                 from += copylen;
 128                 to   += copylen;
 129                 len  -= copylen;
 130         }
 131
 132         /*
 133          * Each sent Ack Vector is recorded in the list, as per A.2 of RFC 4340.
 134          */
 135         avr->avr_ack_seqno  = DCCP_SKB_CB(skb)->dccpd_seq;
 136         avr->avr_ack_ptr    = av->av_buf_head;
 137         avr->avr_ack_ackno  = av->av_buf_ackno;
 138         avr->avr_ack_nonce  = nonce;
 139         avr->avr_ack_runlen = dccp_ackvec_runlen(av->av_buf + av->av_buf_head);
 140
 141         dccp_ackvec_insert_avr(av, avr);
 142
 143         dccp_pr_debug("%s ACK Vector 0, len=%d, ack_seqno=%llu, "
 144                       "ack_ackno=%llu\n",
 145                       dccp_role(sk), avr->avr_ack_runlen,
 146                       (unsigned long long)avr->avr_ack_seqno,
 147                       (unsigned long long)avr->avr_ack_ackno);
 148         return 0;
 149 }
 150
 151 /*
 152  * If several packets are missing, the HC-Receiver may prefer to enter multiple
 153  * bytes with run length 0, rather than a single byte with a larger run length;
 154  * this simplifies table updates if one of the missing packets arrives.
 155  */
 156 static inline int dccp_ackvec_set_buf_head_state(struct dccp_ackvec *av,
 157                                                  const unsigned int packets,
 158                                                  const unsigned char state)
 159 {
 160         long gap;
 161         long new_head;
 162
 163         if (av->av_vec_len + packets > DCCPAV_MAX_ACKVEC_LEN)
 164                 return -ENOBUFS;
 165
 166         gap      = packets - 1;
 167         new_head = av->av_buf_head - packets;
 168
 169         if (new_head < 0) {
 170                 if (gap > 0) {
 171                         memset(av->av_buf, DCCPAV_NOT_RECEIVED,
 172                                gap + new_head + 1);
 173                         gap = -new_head;
 174                 }
 175                 new_head += DCCPAV_MAX_ACKVEC_LEN;
 176         }
 177
 178         av->av_buf_head = new_head;
 179
 180         if (gap > 0)
 181                 memset(av->av_buf + av->av_buf_head + 1,
 182                        DCCPAV_NOT_RECEIVED, gap);
 183
 184         av->av_buf[av->av_buf_head] = state;
 185         av->av_vec_len += packets;
 186         return 0;
 187 }
 188
 189 /*
 190  * Implements the RFC 4340, Appendix A
 191  */
 192 int dccp_ackvec_add(struct dccp_ackvec *av, const struct sock *sk,
 193                     const u64 ackno, const u8 state)
 194 {
 195         u8 *cur_head = av->av_buf + av->av_buf_head,
 196            *buf_end  = av->av_buf + DCCPAV_MAX_ACKVEC_LEN;
 197         /*
 198          * Check at the right places if the buffer is full, if it is, tell the
 199          * caller to start dropping packets till the HC-Sender acks our ACK
 200          * vectors, when we will free up space in av_buf.
 201          *
 202          * We may well decide to do buffer compression, etc, but for now lets
 203          * just drop.
 204          *
 205          * From Appendix A.1.1 (`New Packets'):
 206          *
 207          *      Of course, the circular buffer may overflow, either when the
 208          *      HC-Sender is sending data at a very high rate, when the
 209          *      HC-Receiver's acknowledgements are not reaching the HC-Sender,
 210          *      or when the HC-Sender is forgetting to acknowledge those acks
 211          *      (so the HC-Receiver is unable to clean up old state). In this
 212          *      case, the HC-Receiver should either compress the buffer (by
 213          *      increasing run lengths when possible), transfer its state to
 214          *      a larger buffer, or, as a last resort, drop all received
 215          *      packets, without processing them whatsoever, until its buffer
 216          *      shrinks again.
 217          */
 218
 219         /* See if this is the first ackno being inserted */
 220         if (av->av_vec_len == 0) {
 221                 *cur_head = state;
 222                 av->av_vec_len = 1;
 223         } else if (after48(ackno, av->av_buf_ackno)) {
 224                 const u64 delta = dccp_delta_seqno(av->av_buf_ackno, ackno);
 225
 226                 /*
 227                  * Look if the state of this packet is the same as the
 228                  * previous ackno and if so if we can bump the head len.
 229                  */
 230                 if (delta == 1 && dccp_ackvec_state(cur_head) == state &&
 231                     dccp_ackvec_runlen(cur_head) < DCCPAV_MAX_RUNLEN)
 232                         *cur_head += 1;
 233                 else if (dccp_ackvec_set_buf_head_state(av, delta, state))
 234                         return -ENOBUFS;
 235         } else {
 236                 /*
 237                  * A.1.2.  Old Packets
 238                  *
 239                  *      When a packet with Sequence Number S <= buf_ackno
 240                  *      arrives, the HC-Receiver will scan the table for
 241                  *      the byte corresponding to S. (Indexing structures
 242                  *      could reduce the complexity of this scan.)
 243                  */
 244                 u64 delta = dccp_delta_seqno(ackno, av->av_buf_ackno);
 245
 246                 while (1) {
 247                         const u8 len = dccp_ackvec_runlen(cur_head);
 248                         /*
 249                          * valid packets not yet in av_buf have a reserved
 250                          * entry, with a len equal to 0.
 251                          */
 252                         if (*cur_head == DCCPAV_NOT_RECEIVED && delta == 0) {
 253                                 dccp_pr_debug("Found %llu reserved seat!\n",
 254                                               (unsigned long long)ackno);
 255                                 *cur_head = state;
 256                                 goto out;
 257                         }
 258                         /* len == 0 means one packet */
 259                         if (delta < len + 1)
 260                                 goto out_duplicate;
 261
 262                         delta -= len + 1;
 263                         if (++cur_head == buf_end)
 264                                 cur_head = av->av_buf;
 265                 }
 266         }
 267
 268         av->av_buf_ackno = ackno;
 269 out:
 270         return 0;
 271
 272 out_duplicate:
 273         /* Duplicate packet */
 274         dccp_pr_debug("Received a dup or already considered lost "
 275                       "packet: %llu\n", (unsigned long long)ackno);
 276         return -EILSEQ;
 277 }
 278
 279 static void dccp_ackvec_throw_record(struct dccp_ackvec *av,
 280                                      struct dccp_ackvec_record *avr)
 281 {
 282         struct dccp_ackvec_record *next;
 283
 284         /* sort out vector length */
 285         if (av->av_buf_head <= avr->avr_ack_ptr)
 286                 av->av_vec_len = avr->avr_ack_ptr - av->av_buf_head;
 287         else
 288                 av->av_vec_len = DCCPAV_MAX_ACKVEC_LEN - 1 -
 289                                  av->av_buf_head + avr->avr_ack_ptr;
 290
 291         /* free records */
 292         list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) {
 293                 list_del(&avr->avr_node);
 294                 kmem_cache_free(dccp_ackvec_record_slab, avr);
 295         }
 296 }
 297
 298 void dccp_ackvec_check_rcv_ackno(struct dccp_ackvec *av, struct sock *sk,
 299                                  const u64 ackno)
 300 {
 301         struct dccp_ackvec_record *avr;
 302
 303         /*
 304          * If we traverse backwards, it should be faster when we have large
 305          * windows. We will be receiving ACKs for stuff we sent a while back
 306          * -sorbo.
 307          */
 308         list_for_each_entry_reverse(avr, &av->av_records, avr_node) {
 309                 if (ackno == avr->avr_ack_seqno) {
 310                         dccp_pr_debug("%s ACK packet 0, len=%d, ack_seqno=%llu, "
 311                                       "ack_ackno=%llu, ACKED!\n",
 312                                       dccp_role(sk), avr->avr_ack_runlen,
 313                                       (unsigned long long)avr->avr_ack_seqno,
 314                                       (unsigned long long)avr->avr_ack_ackno);
 315                         dccp_ackvec_throw_record(av, avr);
 316                         break;
 317                 } else if (avr->avr_ack_seqno > ackno)
 318                         break; /* old news */
 319         }
 320 }
 321
 322 static void dccp_ackvec_check_rcv_ackvector(struct dccp_ackvec *av,
 323                                             struct sock *sk, u64 *ackno,
 324                                             const unsigned char len,
 325                                             const unsigned char *vector)
 326 {
 327         unsigned char i;
 328         struct dccp_ackvec_record *avr;
 329
 330         /* Check if we actually sent an ACK vector */
 331         if (list_empty(&av->av_records))
 332                 return;
 333
 334         i = len;
 335         /*
 336          * XXX
 337          * I think it might be more efficient to work backwards. See comment on
 338          * rcv_ackno. -sorbo.
 339          */
 340         avr = list_entry(av->av_records.next, struct dccp_ackvec_record, avr_node);
 341         while (i--) {
 342                 const u8 rl = dccp_ackvec_runlen(vector);
 343                 u64 ackno_end_rl;
 344
 345                 dccp_set_seqno(&ackno_end_rl, *ackno - rl);
 346
 347                 /*
 348                  * If our AVR sequence number is greater than the ack, go
 349                  * forward in the AVR list until it is not so.
 350                  */
 351                 list_for_each_entry_from(avr, &av->av_records, avr_node) {
 352                         if (!after48(avr->avr_ack_seqno, *ackno))
 353                                 goto found;
 354                 }
 355                 /* End of the av_records list, not found, exit */
 356                 break;
 357 found:
 358                 if (between48(avr->avr_ack_seqno, ackno_end_rl, *ackno)) {
 359                         if (dccp_ackvec_state(vector) != DCCPAV_NOT_RECEIVED) {
 360                                 dccp_pr_debug("%s ACK vector 0, len=%d, "
 361                                               "ack_seqno=%llu, ack_ackno=%llu, "
 362                                               "ACKED!\n",
 363                                               dccp_role(sk), len,
 364                                               (unsigned long long)
 365                                               avr->avr_ack_seqno,
 366                                               (unsigned long long)
 367                                               avr->avr_ack_ackno);
 368                                 dccp_ackvec_throw_record(av, avr);
 369                                 break;
 370                         }
 371                         /*
 372                          * If it wasn't received, continue scanning... we might
 373                          * find another one.
 374                          */
 375                 }
 376
 377                 dccp_set_seqno(ackno, ackno_end_rl - 1);
 378                 ++vector;
 379         }
 380 }
 381
 382 int dccp_ackvec_parse(struct sock *sk, const struct sk_buff *skb,
 383                       u64 *ackno, const u8 opt, const u8 *value, const u8 len)
 384 {
 385         if (len > DCCP_SINGLE_OPT_MAXLEN)
 386                 return -1;
 387
 388         /* dccp_ackvector_print(DCCP_SKB_CB(skb)->dccpd_ack_seq, value, len); */
 389         dccp_ackvec_check_rcv_ackvector(dccp_sk(sk)->dccps_hc_rx_ackvec, sk,
 390                                         ackno, len, value);
 391         return 0;
 392 }
 393
 394 int __init dccp_ackvec_init(void)
 395 {
 396         dccp_ackvec_slab = kmem_cache_create("dccp_ackvec",
 397                                              sizeof(struct dccp_ackvec), 0,
 398                                              SLAB_HWCACHE_ALIGN, NULL);
 399         if (dccp_ackvec_slab == NULL)
 400                 goto out_err;
 401
 402         dccp_ackvec_record_slab = kmem_cache_create("dccp_ackvec_record",
 403                                              sizeof(struct dccp_ackvec_record),
 404                                              0, SLAB_HWCACHE_ALIGN, NULL);
 405         if (dccp_ackvec_record_slab == NULL)
 406                 goto out_destroy_slab;
 407
 408         return 0;
 409
 410 out_destroy_slab:
 411         kmem_cache_destroy(dccp_ackvec_slab);
 412         dccp_ackvec_slab = NULL;
 413 out_err:
 414         DCCP_CRIT("Unable to create Ack Vector slab cache");
 415         return -ENOBUFS;
 416 }
 417
 418 void dccp_ackvec_exit(void)
 419 {
 420         if (dccp_ackvec_slab != NULL) {
 421                 kmem_cache_destroy(dccp_ackvec_slab);
 422                 dccp_ackvec_slab = NULL;
 423         }
 424         if (dccp_ackvec_record_slab != NULL) {
 425                 kmem_cache_destroy(dccp_ackvec_record_slab);
 426                 dccp_ackvec_record_slab = NULL;
 427         }
 428 }