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/module.h>
  39 #include <linux/string.h>
  40 #include "packet_history.h"
  41
  42 /**
  43  *  tfrc_tx_hist_entry  -  Simple singly-linked TX history list
  44  *  @next:  next oldest entry (LIFO order)
  45  *  @seqno: sequence number of this entry
  46  *  @stamp: send time of packet with sequence number @seqno
  47  */
  48 struct tfrc_tx_hist_entry {
  49         struct tfrc_tx_hist_entry *next;
  50         u64                       seqno;
  51         ktime_t                   stamp;
  52 };
  53
  54 /*
  55  * Transmitter History Routines
  56  */
  57 static struct kmem_cache *tfrc_tx_hist;
  58
  59 static struct tfrc_tx_hist_entry *
  60         tfrc_tx_hist_find_entry(struct tfrc_tx_hist_entry *head, u64 seqno)
  61 {
  62         while (head != NULL && head->seqno != seqno)
  63                 head = head->next;
  64
  65         return head;
  66 }
  67
  68 int tfrc_tx_hist_add(struct tfrc_tx_hist_entry **headp, u64 seqno)
  69 {
  70         struct tfrc_tx_hist_entry *entry = kmem_cache_alloc(tfrc_tx_hist, gfp_any());
  71
  72         if (entry == NULL)
  73                 return -ENOBUFS;
  74         entry->seqno = seqno;
  75         entry->stamp = ktime_get_real();
  76         entry->next  = *headp;
  77         *headp       = entry;
  78         return 0;
  79 }
  80 EXPORT_SYMBOL_GPL(tfrc_tx_hist_add);
  81
  82 void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry **headp)
  83 {
  84         struct tfrc_tx_hist_entry *head = *headp;
  85
  86         while (head != NULL) {
  87                 struct tfrc_tx_hist_entry *next = head->next;
  88
  89                 kmem_cache_free(tfrc_tx_hist, head);
  90                 head = next;
  91         }
  92
  93         *headp = NULL;
  94 }
  95 EXPORT_SYMBOL_GPL(tfrc_tx_hist_purge);
  96
  97 u32 tfrc_tx_hist_rtt(struct tfrc_tx_hist_entry *head, const u64 seqno,
  98                      const ktime_t now)
  99 {
 100         u32 rtt = 0;
 101         struct tfrc_tx_hist_entry *packet = tfrc_tx_hist_find_entry(head, seqno);
 102
 103         if (packet != NULL) {
 104                 rtt = ktime_us_delta(now, packet->stamp);
 105                 /*
 106                  * Garbage-collect older (irrelevant) entries:
 107                  */
 108                 tfrc_tx_hist_purge(&packet->next);
 109         }
 110
 111         return rtt;
 112 }
 113 EXPORT_SYMBOL_GPL(tfrc_tx_hist_rtt);
 114
 115 /*
 116  *      Receiver History Routines
 117  */
 118 struct dccp_rx_hist *dccp_rx_hist_new(const char *name)
 119 {
 120         struct dccp_rx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC);
 121         static const char dccp_rx_hist_mask[] = "rx_hist_%s";
 122         char *slab_name;
 123
 124         if (hist == NULL)
 125                 goto out;
 126
 127         slab_name = kmalloc(strlen(name) + sizeof(dccp_rx_hist_mask) - 1,
 128                             GFP_ATOMIC);
 129         if (slab_name == NULL)
 130                 goto out_free_hist;
 131
 132         sprintf(slab_name, dccp_rx_hist_mask, name);
 133         hist->dccprxh_slab = kmem_cache_create(slab_name,
 134                                              sizeof(struct dccp_rx_hist_entry),
 135                                              0, SLAB_HWCACHE_ALIGN, NULL);
 136         if (hist->dccprxh_slab == NULL)
 137                 goto out_free_slab_name;
 138 out:
 139         return hist;
 140 out_free_slab_name:
 141         kfree(slab_name);
 142 out_free_hist:
 143         kfree(hist);
 144         hist = NULL;
 145         goto out;
 146 }
 147
 148 EXPORT_SYMBOL_GPL(dccp_rx_hist_new);
 149
 150 void dccp_rx_hist_delete(struct dccp_rx_hist *hist)
 151 {
 152         const char* name = kmem_cache_name(hist->dccprxh_slab);
 153
 154         kmem_cache_destroy(hist->dccprxh_slab);
 155         kfree(name);
 156         kfree(hist);
 157 }
 158
 159 EXPORT_SYMBOL_GPL(dccp_rx_hist_delete);
 160
 161 int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq,
 162                             u8 *ccval)
 163 {
 164         struct dccp_rx_hist_entry *packet = NULL, *entry;
 165
 166         list_for_each_entry(entry, list, dccphrx_node)
 167                 if (entry->dccphrx_seqno == seq) {
 168                         packet = entry;
 169                         break;
 170                 }
 171
 172         if (packet)
 173                 *ccval = packet->dccphrx_ccval;
 174
 175         return packet != NULL;
 176 }
 177
 178 EXPORT_SYMBOL_GPL(dccp_rx_hist_find_entry);
 179 struct dccp_rx_hist_entry *
 180                 dccp_rx_hist_find_data_packet(const struct list_head *list)
 181 {
 182         struct dccp_rx_hist_entry *entry, *packet = NULL;
 183
 184         list_for_each_entry(entry, list, dccphrx_node)
 185                 if (entry->dccphrx_type == DCCP_PKT_DATA ||
 186                     entry->dccphrx_type == DCCP_PKT_DATAACK) {
 187                         packet = entry;
 188                         break;
 189                 }
 190
 191         return packet;
 192 }
 193
 194 EXPORT_SYMBOL_GPL(dccp_rx_hist_find_data_packet);
 195
 196 void dccp_rx_hist_add_packet(struct dccp_rx_hist *hist,
 197                             struct list_head *rx_list,
 198                             struct list_head *li_list,
 199                             struct dccp_rx_hist_entry *packet,
 200                             u64 nonloss_seqno)
 201 {
 202         struct dccp_rx_hist_entry *entry, *next;
 203         u8 num_later = 0;
 204
 205         list_add(&packet->dccphrx_node, rx_list);
 206
 207         num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
 208
 209         if (!list_empty(li_list)) {
 210                 list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) {
 211                         if (num_later == 0) {
 212                                 if (after48(nonloss_seqno,
 213                                    entry->dccphrx_seqno)) {
 214                                         list_del_init(&entry->dccphrx_node);
 215                                         dccp_rx_hist_entry_delete(hist, entry);
 216                                 }
 217                         } else if (dccp_rx_hist_entry_data_packet(entry))
 218                                 --num_later;
 219                 }
 220         } else {
 221                 int step = 0;
 222                 u8 win_count = 0; /* Not needed, but lets shut up gcc */
 223                 int tmp;
 224                 /*
 225                  * We have no loss interval history so we need at least one
 226                  * rtt:s of data packets to approximate rtt.
 227                  */
 228                 list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) {
 229                         if (num_later == 0) {
 230                                 switch (step) {
 231                                 case 0:
 232                                         step = 1;
 233                                         /* OK, find next data packet */
 234                                         num_later = 1;
 235                                         break;
 236                                 case 1:
 237                                         step = 2;
 238                                         /* OK, find next data packet */
 239                                         num_later = 1;
 240                                         win_count = entry->dccphrx_ccval;
 241                                         break;
 242                                 case 2:
 243                                         tmp = win_count - entry->dccphrx_ccval;
 244                                         if (tmp < 0)
 245                                                 tmp += TFRC_WIN_COUNT_LIMIT;
 246                                         if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) {
 247                                                 /*
 248                                                  * We have found a packet older
 249                                                  * than one rtt remove the rest
 250                                                  */
 251                                                 step = 3;
 252                                         } else /* OK, find next data packet */
 253                                                 num_later = 1;
 254                                         break;
 255                                 case 3:
 256                                         list_del_init(&entry->dccphrx_node);
 257                                         dccp_rx_hist_entry_delete(hist, entry);
 258                                         break;
 259                                 }
 260                         } else if (dccp_rx_hist_entry_data_packet(entry))
 261                                 --num_later;
 262                 }
 263         }
 264 }
 265
 266 EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet);
 267
 268 void dccp_rx_hist_purge(struct dccp_rx_hist *hist, struct list_head *list)
 269 {
 270         struct dccp_rx_hist_entry *entry, *next;
 271
 272         list_for_each_entry_safe(entry, next, list, dccphrx_node) {
 273                 list_del_init(&entry->dccphrx_node);
 274                 kmem_cache_free(hist->dccprxh_slab, entry);
 275         }
 276 }
 277
 278 EXPORT_SYMBOL_GPL(dccp_rx_hist_purge);
 279
 280 extern int __init dccp_li_init(void);
 281 extern void dccp_li_exit(void);
 282
 283 static __init int packet_history_init(void)
 284 {
 285         if (dccp_li_init() != 0)
 286                 goto out;
 287
 288         tfrc_tx_hist = kmem_cache_create("tfrc_tx_hist",
 289                                          sizeof(struct tfrc_tx_hist_entry), 0,
 290                                          SLAB_HWCACHE_ALIGN, NULL);
 291         if (tfrc_tx_hist == NULL)
 292                 goto out_li_exit;
 293
 294         return 0;
 295 out_li_exit:
 296         dccp_li_exit();
 297 out:
 298         return -ENOBUFS;
 299 }
 300 module_init(packet_history_init);
 301
 302 static __exit void packet_history_exit(void)
 303 {
 304         if (tfrc_tx_hist != NULL) {
 305                 kmem_cache_destroy(tfrc_tx_hist);
 306                 tfrc_tx_hist = NULL;
 307         }
 308         dccp_li_exit();
 309 }
 310 module_exit(packet_history_exit);
 311
 312 MODULE_AUTHOR("Ian McDonald <ian.mcdonald@jandi.co.nz>, "
 313               "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>");
 314 MODULE_DESCRIPTION("DCCP TFRC library");
 315 MODULE_LICENSE("GPL");