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;
  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, 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, 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 struct dccp_rx_hist *dccp_rx_hist_new(const char *name)
 118 {
 119         struct dccp_rx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC);
 120         static const char dccp_rx_hist_mask[] = "rx_hist_%s";
 121         char *slab_name;
 122
 123         if (hist == NULL)
 124                 goto out;
 125
 126         slab_name = kmalloc(strlen(name) + sizeof(dccp_rx_hist_mask) - 1,
 127                             GFP_ATOMIC);
 128         if (slab_name == NULL)
 129                 goto out_free_hist;
 130
 131         sprintf(slab_name, dccp_rx_hist_mask, name);
 132         hist->dccprxh_slab = kmem_cache_create(slab_name,
 133                                              sizeof(struct dccp_rx_hist_entry),
 134                                              0, SLAB_HWCACHE_ALIGN, NULL);
 135         if (hist->dccprxh_slab == NULL)
 136                 goto out_free_slab_name;
 137 out:
 138         return hist;
 139 out_free_slab_name:
 140         kfree(slab_name);
 141 out_free_hist:
 142         kfree(hist);
 143         hist = NULL;
 144         goto out;
 145 }
 146
 147 EXPORT_SYMBOL_GPL(dccp_rx_hist_new);
 148
 149 void dccp_rx_hist_delete(struct dccp_rx_hist *hist)
 150 {
 151         const char* name = kmem_cache_name(hist->dccprxh_slab);
 152
 153         kmem_cache_destroy(hist->dccprxh_slab);
 154         kfree(name);
 155         kfree(hist);
 156 }
 157
 158 EXPORT_SYMBOL_GPL(dccp_rx_hist_delete);
 159
 160 int dccp_rx_hist_find_entry(const struct list_head *list, const u64 seq,
 161                             u8 *ccval)
 162 {
 163         struct dccp_rx_hist_entry *packet = NULL, *entry;
 164
 165         list_for_each_entry(entry, list, dccphrx_node)
 166                 if (entry->dccphrx_seqno == seq) {
 167                         packet = entry;
 168                         break;
 169                 }
 170
 171         if (packet)
 172                 *ccval = packet->dccphrx_ccval;
 173
 174         return packet != NULL;
 175 }
 176
 177 EXPORT_SYMBOL_GPL(dccp_rx_hist_find_entry);
 178 struct dccp_rx_hist_entry *
 179                 dccp_rx_hist_find_data_packet(const struct list_head *list)
 180 {
 181         struct dccp_rx_hist_entry *entry, *packet = NULL;
 182
 183         list_for_each_entry(entry, list, dccphrx_node)
 184                 if (entry->dccphrx_type == DCCP_PKT_DATA ||
 185                     entry->dccphrx_type == DCCP_PKT_DATAACK) {
 186                         packet = entry;
 187                         break;
 188                 }
 189
 190         return packet;
 191 }
 192
 193 EXPORT_SYMBOL_GPL(dccp_rx_hist_find_data_packet);
 194
 195 void dccp_rx_hist_add_packet(struct dccp_rx_hist *hist,
 196                             struct list_head *rx_list,
 197                             struct list_head *li_list,
 198                             struct dccp_rx_hist_entry *packet,
 199                             u64 nonloss_seqno)
 200 {
 201         struct dccp_rx_hist_entry *entry, *next;
 202         u8 num_later = 0;
 203
 204         list_add(&packet->dccphrx_node, rx_list);
 205
 206         num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
 207
 208         if (!list_empty(li_list)) {
 209                 list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) {
 210                         if (num_later == 0) {
 211                                 if (after48(nonloss_seqno,
 212                                    entry->dccphrx_seqno)) {
 213                                         list_del_init(&entry->dccphrx_node);
 214                                         dccp_rx_hist_entry_delete(hist, entry);
 215                                 }
 216                         } else if (dccp_rx_hist_entry_data_packet(entry))
 217                                 --num_later;
 218                 }
 219         } else {
 220                 int step = 0;
 221                 u8 win_count = 0; /* Not needed, but lets shut up gcc */
 222                 int tmp;
 223                 /*
 224                  * We have no loss interval history so we need at least one
 225                  * rtt:s of data packets to approximate rtt.
 226                  */
 227                 list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) {
 228                         if (num_later == 0) {
 229                                 switch (step) {
 230                                 case 0:
 231                                         step = 1;
 232                                         /* OK, find next data packet */
 233                                         num_later = 1;
 234                                         break;
 235                                 case 1:
 236                                         step = 2;
 237                                         /* OK, find next data packet */
 238                                         num_later = 1;
 239                                         win_count = entry->dccphrx_ccval;
 240                                         break;
 241                                 case 2:
 242                                         tmp = win_count - entry->dccphrx_ccval;
 243                                         if (tmp < 0)
 244                                                 tmp += TFRC_WIN_COUNT_LIMIT;
 245                                         if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) {
 246                                                 /*
 247                                                  * We have found a packet older
 248                                                  * than one rtt remove the rest
 249                                                  */
 250                                                 step = 3;
 251                                         } else /* OK, find next data packet */
 252                                                 num_later = 1;
 253                                         break;
 254                                 case 3:
 255                                         list_del_init(&entry->dccphrx_node);
 256                                         dccp_rx_hist_entry_delete(hist, entry);
 257                                         break;
 258                                 }
 259                         } else if (dccp_rx_hist_entry_data_packet(entry))
 260                                 --num_later;
 261                 }
 262         }
 263 }
 264
 265 EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet);
 266
 267 void dccp_rx_hist_purge(struct dccp_rx_hist *hist, struct list_head *list)
 268 {
 269         struct dccp_rx_hist_entry *entry, *next;
 270
 271         list_for_each_entry_safe(entry, next, list, dccphrx_node) {
 272                 list_del_init(&entry->dccphrx_node);
 273                 kmem_cache_free(hist->dccprxh_slab, entry);
 274         }
 275 }
 276
 277 EXPORT_SYMBOL_GPL(dccp_rx_hist_purge);
 278
 279 __init int packet_history_init(void)
 280 {
 281         tfrc_tx_hist = kmem_cache_create("tfrc_tx_hist",
 282                                          sizeof(struct tfrc_tx_hist_entry), 0,
 283                                          SLAB_HWCACHE_ALIGN, NULL);
 284
 285         return tfrc_tx_hist == NULL ? -ENOBUFS : 0;
 286 }
 287
 288 void packet_history_exit(void)
 289 {
 290         if (tfrc_tx_hist != NULL) {
 291                 kmem_cache_destroy(tfrc_tx_hist);
 292                 tfrc_tx_hist = NULL;
 293         }
 294 }