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