SAFE public projects git trees. - safe/jmp/linux-2.6/blob - net/dccp/ccids/lib/packet_history.c

   1 /*
   2  *  net/dccp/packet_history.c
   3  *
   4  *  Copyright (c) 2007   The University of Aberdeen, Scotland, UK
   5  *  Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand.
   6  *
   7  *  An implementation of the DCCP protocol
   8  *
   9  *  This code has been developed by the University of Waikato WAND
  10  *  research group. For further information please see http://www.wand.net.nz/
  11  *  or e-mail Ian McDonald - ian.mcdonald@jandi.co.nz
  12  *
  13  *  This code also uses code from Lulea University, rereleased as GPL by its
  14  *  authors:
  15  *  Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
  16  *
  17  *  Changes to meet Linux coding standards, to make it meet latest ccid3 draft
  18  *  and to make it work as a loadable module in the DCCP stack written by
  19  *  Arnaldo Carvalho de Melo <acme@conectiva.com.br>.
  20  *
  21  *  Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
  22  *
  23  *  This program is free software; you can redistribute it and/or modify
  24  *  it under the terms of the GNU General Public License as published by
  25  *  the Free Software Foundation; either version 2 of the License, or
  26  *  (at your option) any later version.
  27  *
  28  *  This program is distributed in the hope that it will be useful,
  29  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  30  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31  *  GNU General Public License for more details.
  32  *
  33  *  You should have received a copy of the GNU General Public License
  34  *  along with this program; if not, write to the Free Software
  35  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  36  */
  37
  38 #include <linux/string.h>
  39 #include "packet_history.h"
  40
  41 /**
  42  *  tfrc_tx_hist_entry  -  Simple singly-linked TX history list
  43  *  @next:  next oldest entry (LIFO order)
  44  *  @seqno: sequence number of this entry
  45  *  @stamp: send time of packet with sequence number @seqno
  46  */
  47 struct tfrc_tx_hist_entry {
  48         struct tfrc_tx_hist_entry *next;
  49         u64                       seqno;
  50         ktime_t                   stamp;
  51 };
  52
  53 /*
  54  * Transmitter History Routines
  55  */
  56 static struct kmem_cache *tfrc_tx_hist_slab;
  57
  58 static struct tfrc_tx_hist_entry *
  59         tfrc_tx_hist_find_entry(struct tfrc_tx_hist_entry *head, u64 seqno)
  60 {
  61         while (head != NULL && head->seqno != seqno)
  62                 head = head->next;
  63
  64         return head;
  65 }
  66
  67 int tfrc_tx_hist_add(struct tfrc_tx_hist_entry **headp, u64 seqno)
  68 {
  69         struct tfrc_tx_hist_entry *entry = kmem_cache_alloc(tfrc_tx_hist_slab, gfp_any());
  70
  71         if (entry == NULL)
  72                 return -ENOBUFS;
  73         entry->seqno = seqno;
  74         entry->stamp = ktime_get_real();
  75         entry->next  = *headp;
  76         *headp       = entry;
  77         return 0;
  78 }
  79 EXPORT_SYMBOL_GPL(tfrc_tx_hist_add);
  80
  81 void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry **headp)
  82 {
  83         struct tfrc_tx_hist_entry *head = *headp;
  84
  85         while (head != NULL) {
  86                 struct tfrc_tx_hist_entry *next = head->next;
  87
  88                 kmem_cache_free(tfrc_tx_hist_slab, head);
  89                 head = next;
  90         }
  91
  92         *headp = NULL;
  93 }
  94 EXPORT_SYMBOL_GPL(tfrc_tx_hist_purge);
  95
  96 u32 tfrc_tx_hist_rtt(struct tfrc_tx_hist_entry *head, const u64 seqno,
  97                      const ktime_t now)
  98 {
  99         u32 rtt = 0;
 100         struct tfrc_tx_hist_entry *packet = tfrc_tx_hist_find_entry(head, seqno);
 101
 102         if (packet != NULL) {
 103                 rtt = ktime_us_delta(now, packet->stamp);
 104                 /*
 105                  * Garbage-collect older (irrelevant) entries:
 106                  */
 107                 tfrc_tx_hist_purge(&packet->next);
 108         }
 109
 110         return rtt;
 111 }
 112 EXPORT_SYMBOL_GPL(tfrc_tx_hist_rtt);
 113
 114 /*
 115  *      Receiver History Routines
 116  */
 117 static struct kmem_cache *tfrc_rx_hist_slab;
 118
 119 struct dccp_rx_hist_entry *dccp_rx_hist_entry_new(const u32 ndp,
 120                                                   const struct sk_buff *skb,
 121                                                   const gfp_t prio)
 122 {
 123         struct dccp_rx_hist_entry *entry = kmem_cache_alloc(tfrc_rx_hist_slab,
 124                                                             prio);
 125
 126         if (entry != NULL) {
 127                 const struct dccp_hdr *dh = dccp_hdr(skb);
 128
 129                 entry->dccphrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq;
 130                 entry->dccphrx_ccval = dh->dccph_ccval;
 131                 entry->dccphrx_type  = dh->dccph_type;
 132                 entry->dccphrx_ndp   = ndp;
 133                 entry->dccphrx_tstamp = ktime_get_real();
 134         }
 135
 136         return entry;
 137 }
 138 EXPORT_SYMBOL_GPL(dccp_rx_hist_entry_new);
 139
 140 static inline void dccp_rx_hist_entry_delete(struct dccp_rx_hist_entry *entry)
 141 {
 142         kmem_cache_free(tfrc_rx_hist_slab, entry);
 143 }
 144
 145 int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq,
 146                             u8 *ccval)
 147 {
 148         struct dccp_rx_hist_entry *packet = NULL, *entry;
 149
 150         list_for_each_entry(entry, list, dccphrx_node)
 151                 if (entry->dccphrx_seqno == seq) {
 152                         packet = entry;
 153                         break;
 154                 }
 155
 156         if (packet)
 157                 *ccval = packet->dccphrx_ccval;
 158
 159         return packet != NULL;
 160 }
 161
 162 EXPORT_SYMBOL_GPL(dccp_rx_hist_find_entry);
 163 struct dccp_rx_hist_entry *
 164                 dccp_rx_hist_find_data_packet(const struct list_head *list)
 165 {
 166         struct dccp_rx_hist_entry *entry, *packet = NULL;
 167
 168         list_for_each_entry(entry, list, dccphrx_node)
 169                 if (entry->dccphrx_type == DCCP_PKT_DATA ||
 170                     entry->dccphrx_type == DCCP_PKT_DATAACK) {
 171                         packet = entry;
 172                         break;
 173                 }
 174
 175         return packet;
 176 }
 177
 178 EXPORT_SYMBOL_GPL(dccp_rx_hist_find_data_packet);
 179
 180 void dccp_rx_hist_add_packet(struct list_head *rx_list,
 181                              struct list_head *li_list,
 182                              struct dccp_rx_hist_entry *packet,
 183                              u64 nonloss_seqno)
 184 {
 185         struct dccp_rx_hist_entry *entry, *next;
 186         u8 num_later = 0;
 187
 188         list_add(&packet->dccphrx_node, rx_list);
 189
 190         num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
 191
 192         if (!list_empty(li_list)) {
 193                 list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) {
 194                         if (num_later == 0) {
 195                                 if (after48(nonloss_seqno,
 196                                    entry->dccphrx_seqno)) {
 197                                         list_del_init(&entry->dccphrx_node);
 198                                         dccp_rx_hist_entry_delete(entry);
 199                                 }
 200                         } else if (dccp_rx_hist_entry_data_packet(entry))
 201                                 --num_later;
 202                 }
 203         } else {
 204                 int step = 0;
 205                 u8 win_count = 0; /* Not needed, but lets shut up gcc */
 206                 int tmp;
 207                 /*
 208                  * We have no loss interval history so we need at least one
 209                  * rtt:s of data packets to approximate rtt.
 210                  */
 211                 list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) {
 212                         if (num_later == 0) {
 213                                 switch (step) {
 214                                 case 0:
 215                                         step = 1;
 216                                         /* OK, find next data packet */
 217                                         num_later = 1;
 218                                         break;
 219                                 case 1:
 220                                         step = 2;
 221                                         /* OK, find next data packet */
 222                                         num_later = 1;
 223                                         win_count = entry->dccphrx_ccval;
 224                                         break;
 225                                 case 2:
 226                                         tmp = win_count - entry->dccphrx_ccval;
 227                                         if (tmp < 0)
 228                                                 tmp += TFRC_WIN_COUNT_LIMIT;
 229                                         if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) {
 230                                                 /*
 231                                                  * We have found a packet older
 232                                                  * than one rtt remove the rest
 233                                                  */
 234                                                 step = 3;
 235                                         } else /* OK, find next data packet */
 236                                                 num_later = 1;
 237                                         break;
 238                                 case 3:
 239                                         list_del_init(&entry->dccphrx_node);
 240                                         dccp_rx_hist_entry_delete(entry);
 241                                         break;
 242                                 }
 243                         } else if (dccp_rx_hist_entry_data_packet(entry))
 244                                 --num_later;
 245                 }
 246         }
 247 }
 248
 249 EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet);
 250
 251 void dccp_rx_hist_purge(struct list_head *list)
 252 {
 253         struct dccp_rx_hist_entry *entry, *next;
 254
 255         list_for_each_entry_safe(entry, next, list, dccphrx_node) {
 256                 list_del_init(&entry->dccphrx_node);
 257                 dccp_rx_hist_entry_delete(entry);
 258         }
 259 }
 260
 261 EXPORT_SYMBOL_GPL(dccp_rx_hist_purge);
 262
 263 __init int packet_history_init(void)
 264 {
 265         tfrc_tx_hist_slab = kmem_cache_create("tfrc_tx_hist",
 266                                               sizeof(struct tfrc_tx_hist_entry), 0,
 267                                               SLAB_HWCACHE_ALIGN, NULL);
 268         if (tfrc_tx_hist_slab == NULL)
 269                 goto out_err;
 270
 271         tfrc_rx_hist_slab = kmem_cache_create("tfrc_rx_hist",
 272                                               sizeof(struct dccp_rx_hist_entry), 0,
 273                                               SLAB_HWCACHE_ALIGN, NULL);
 274         if (tfrc_rx_hist_slab == NULL)
 275                 goto out_free_tx;
 276
 277         return 0;
 278
 279 out_free_tx:
 280         kmem_cache_destroy(tfrc_tx_hist_slab);
 281         tfrc_tx_hist_slab = NULL;
 282 out_err:
 283         return -ENOBUFS;
 284 }
 285
 286 void packet_history_exit(void)
 287 {
 288         if (tfrc_tx_hist_slab != NULL) {
 289                 kmem_cache_destroy(tfrc_tx_hist_slab);
 290                 tfrc_tx_hist_slab = NULL;
 291         }
 292
 293         if (tfrc_rx_hist_slab != NULL) {
 294                 kmem_cache_destroy(tfrc_rx_hist_slab);
 295                 tfrc_rx_hist_slab = NULL;
 296         }
 297 }