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