1 /* 2 * net/dccp/packet_history.h 3 * 4 * Copyright (c) 2005 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 - iam4@cs.waikato.ac.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/config.h> 38 #include <linux/module.h> 39 #include <linux/string.h> 40 41 #include "packet_history.h" 42 43 struct dccp_rx_hist *dccp_rx_hist_new(const char *name) 44 { 45 struct dccp_rx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC); 46 static const char dccp_rx_hist_mask[] = "rx_hist_%s"; 47 char *slab_name; 48 49 if (hist == NULL) 50 goto out; 51 52 slab_name = kmalloc(strlen(name) + sizeof(dccp_rx_hist_mask) - 1, 53 GFP_ATOMIC); 54 if (slab_name == NULL) 55 goto out_free_hist; 56 57 sprintf(slab_name, dccp_rx_hist_mask, name); 58 hist->dccprxh_slab = kmem_cache_create(slab_name, 59 sizeof(struct dccp_rx_hist_entry), 60 0, SLAB_HWCACHE_ALIGN, 61 NULL, NULL); 62 if (hist->dccprxh_slab == NULL) 63 goto out_free_slab_name; 64 out: 65 return hist; 66 out_free_slab_name: 67 kfree(slab_name); 68 out_free_hist: 69 kfree(hist); 70 hist = NULL; 71 goto out; 72 } 73 74 EXPORT_SYMBOL_GPL(dccp_rx_hist_new); 75 76 void dccp_rx_hist_delete(struct dccp_rx_hist *hist) 77 { 78 const char* name = kmem_cache_name(hist->dccprxh_slab); 79 80 kmem_cache_destroy(hist->dccprxh_slab); 81 kfree(name); 82 kfree(hist); 83 } 84 85 EXPORT_SYMBOL_GPL(dccp_rx_hist_delete); 86 87 void dccp_rx_hist_purge(struct dccp_rx_hist *hist, struct list_head *list) 88 { 89 struct dccp_rx_hist_entry *entry, *next; 90 91 list_for_each_entry_safe(entry, next, list, dccphrx_node) { 92 list_del_init(&entry->dccphrx_node); 93 kmem_cache_free(hist->dccprxh_slab, entry); 94 } 95 } 96 97 EXPORT_SYMBOL_GPL(dccp_rx_hist_purge); 98 99 struct dccp_rx_hist_entry * 100 dccp_rx_hist_find_data_packet(const struct list_head *list) 101 { 102 struct dccp_rx_hist_entry *entry, *packet = NULL; 103 104 list_for_each_entry(entry, list, dccphrx_node) 105 if (entry->dccphrx_type == DCCP_PKT_DATA || 106 entry->dccphrx_type == DCCP_PKT_DATAACK) { 107 packet = entry; 108 break; 109 } 110 111 return packet; 112 } 113 114 EXPORT_SYMBOL_GPL(dccp_rx_hist_find_data_packet); 115 116 int dccp_rx_hist_add_packet(struct dccp_rx_hist *hist, 117 struct list_head *rx_list, 118 struct list_head *li_list, 119 struct dccp_rx_hist_entry *packet) 120 { 121 struct dccp_rx_hist_entry *entry, *next, *iter; 122 u8 num_later = 0; 123 124 iter = dccp_rx_hist_head(rx_list); 125 if (iter == NULL) 126 dccp_rx_hist_add_entry(rx_list, packet); 127 else { 128 const u64 seqno = packet->dccphrx_seqno; 129 130 if (after48(seqno, iter->dccphrx_seqno)) 131 dccp_rx_hist_add_entry(rx_list, packet); 132 else { 133 if (dccp_rx_hist_entry_data_packet(iter)) 134 num_later = 1; 135 136 list_for_each_entry_continue(iter, rx_list, 137 dccphrx_node) { 138 if (after48(seqno, iter->dccphrx_seqno)) { 139 dccp_rx_hist_add_entry(&iter->dccphrx_node, 140 packet); 141 goto trim_history; 142 } 143 144 if (dccp_rx_hist_entry_data_packet(iter)) 145 num_later++; 146 147 if (num_later == TFRC_RECV_NUM_LATE_LOSS) { 148 dccp_rx_hist_entry_delete(hist, packet); 149 return 1; 150 } 151 } 152 153 if (num_later < TFRC_RECV_NUM_LATE_LOSS) 154 dccp_rx_hist_add_entry(rx_list, packet); 155 /* 156 * FIXME: else what? should we destroy the packet 157 * like above? 158 */ 159 } 160 } 161 162 trim_history: 163 /* 164 * Trim history (remove all packets after the NUM_LATE_LOSS + 1 165 * data packets) 166 */ 167 num_later = TFRC_RECV_NUM_LATE_LOSS + 1; 168 169 if (!list_empty(li_list)) { 170 list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) { 171 if (num_later == 0) { 172 list_del_init(&entry->dccphrx_node); 173 dccp_rx_hist_entry_delete(hist, entry); 174 } else if (dccp_rx_hist_entry_data_packet(entry)) 175 --num_later; 176 } 177 } else { 178 int step = 0; 179 u8 win_count = 0; /* Not needed, but lets shut up gcc */ 180 int tmp; 181 /* 182 * We have no loss interval history so we need at least one 183 * rtt:s of data packets to approximate rtt. 184 */ 185 list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) { 186 if (num_later == 0) { 187 switch (step) { 188 case 0: 189 step = 1; 190 /* OK, find next data packet */ 191 num_later = 1; 192 break; 193 case 1: 194 step = 2; 195 /* OK, find next data packet */ 196 num_later = 1; 197 win_count = entry->dccphrx_ccval; 198 break; 199 case 2: 200 tmp = win_count - entry->dccphrx_ccval; 201 if (tmp < 0) 202 tmp += TFRC_WIN_COUNT_LIMIT; 203 if (tmp > TFRC_WIN_COUNT_PER_RTT + 1) { 204 /* 205 * We have found a packet older 206 * than one rtt remove the rest 207 */ 208 step = 3; 209 } else /* OK, find next data packet */ 210 num_later = 1; 211 break; 212 case 3: 213 list_del_init(&entry->dccphrx_node); 214 dccp_rx_hist_entry_delete(hist, entry); 215 break; 216 } 217 } else if (dccp_rx_hist_entry_data_packet(entry)) 218 --num_later; 219 } 220 } 221 222 return 0; 223 } 224 225 EXPORT_SYMBOL_GPL(dccp_rx_hist_add_packet); 226 227 u64 dccp_rx_hist_detect_loss(struct list_head *rx_list, 228 struct list_head *li_list, u8 *win_loss) 229 { 230 struct dccp_rx_hist_entry *entry, *next, *packet; 231 struct dccp_rx_hist_entry *a_loss = NULL; 232 struct dccp_rx_hist_entry *b_loss = NULL; 233 u64 seq_loss = DCCP_MAX_SEQNO + 1; 234 u8 num_later = TFRC_RECV_NUM_LATE_LOSS; 235 236 list_for_each_entry_safe(entry, next, rx_list, dccphrx_node) { 237 if (num_later == 0) { 238 b_loss = entry; 239 break; 240 } else if (dccp_rx_hist_entry_data_packet(entry)) 241 --num_later; 242 } 243 244 if (b_loss == NULL) 245 goto out; 246 247 num_later = 1; 248 list_for_each_entry_safe_continue(entry, next, rx_list, dccphrx_node) { 249 if (num_later == 0) { 250 a_loss = entry; 251 break; 252 } else if (dccp_rx_hist_entry_data_packet(entry)) 253 --num_later; 254 } 255 256 if (a_loss == NULL) { 257 if (list_empty(li_list)) { 258 /* no loss event have occured yet */ 259 LIMIT_NETDEBUG("%s: TODO: find a lost data packet by " 260 "comparing to initial seqno\n", 261 __FUNCTION__); 262 goto out; 263 } else { 264 LIMIT_NETDEBUG("%s: Less than 4 data pkts in history!", 265 __FUNCTION__); 266 goto out; 267 } 268 } 269 270 /* Locate a lost data packet */ 271 entry = packet = b_loss; 272 list_for_each_entry_safe_continue(entry, next, rx_list, dccphrx_node) { 273 u64 delta = dccp_delta_seqno(entry->dccphrx_seqno, 274 packet->dccphrx_seqno); 275 276 if (delta != 0) { 277 if (dccp_rx_hist_entry_data_packet(packet)) 278 --delta; 279 /* 280 * FIXME: check this, probably this % usage is because 281 * in earlier drafts the ndp count was just 8 bits 282 * long, but now it cam be up to 24 bits long. 283 */ 284 #if 0 285 if (delta % DCCP_NDP_LIMIT != 286 (packet->dccphrx_ndp - 287 entry->dccphrx_ndp) % DCCP_NDP_LIMIT) 288 #endif 289 if (delta != packet->dccphrx_ndp - entry->dccphrx_ndp) { 290 seq_loss = entry->dccphrx_seqno; 291 dccp_inc_seqno(&seq_loss); 292 } 293 } 294 packet = entry; 295 if (packet == a_loss) 296 break; 297 } 298 out: 299 if (seq_loss != DCCP_MAX_SEQNO + 1) 300 *win_loss = a_loss->dccphrx_ccval; 301 else 302 *win_loss = 0; /* Paranoia */ 303 304 return seq_loss; 305 } 306 307 EXPORT_SYMBOL_GPL(dccp_rx_hist_detect_loss); 308 309 struct dccp_tx_hist *dccp_tx_hist_new(const char *name) 310 { 311 struct dccp_tx_hist *hist = kmalloc(sizeof(*hist), GFP_ATOMIC); 312 static const char dccp_tx_hist_mask[] = "tx_hist_%s"; 313 char *slab_name; 314 315 if (hist == NULL) 316 goto out; 317 318 slab_name = kmalloc(strlen(name) + sizeof(dccp_tx_hist_mask) - 1, 319 GFP_ATOMIC); 320 if (slab_name == NULL) 321 goto out_free_hist; 322 323 sprintf(slab_name, dccp_tx_hist_mask, name); 324 hist->dccptxh_slab = kmem_cache_create(slab_name, 325 sizeof(struct dccp_tx_hist_entry), 326 0, SLAB_HWCACHE_ALIGN, 327 NULL, NULL); 328 if (hist->dccptxh_slab == NULL) 329 goto out_free_slab_name; 330 out: 331 return hist; 332 out_free_slab_name: 333 kfree(slab_name); 334 out_free_hist: 335 kfree(hist); 336 hist = NULL; 337 goto out; 338 } 339 340 EXPORT_SYMBOL_GPL(dccp_tx_hist_new); 341 342 void dccp_tx_hist_delete(struct dccp_tx_hist *hist) 343 { 344 const char* name = kmem_cache_name(hist->dccptxh_slab); 345 346 kmem_cache_destroy(hist->dccptxh_slab); 347 kfree(name); 348 kfree(hist); 349 } 350 351 EXPORT_SYMBOL_GPL(dccp_tx_hist_delete); 352 353 struct dccp_tx_hist_entry * 354 dccp_tx_hist_find_entry(const struct list_head *list, const u64 seq) 355 { 356 struct dccp_tx_hist_entry *packet = NULL, *entry; 357 358 list_for_each_entry(entry, list, dccphtx_node) 359 if (entry->dccphtx_seqno == seq) { 360 packet = entry; 361 break; 362 } 363 364 return packet; 365 } 366 367 EXPORT_SYMBOL_GPL(dccp_tx_hist_find_entry); 368 369 void dccp_tx_hist_purge_older(struct dccp_tx_hist *hist, 370 struct list_head *list, 371 struct dccp_tx_hist_entry *packet) 372 { 373 struct dccp_tx_hist_entry *next; 374 375 list_for_each_entry_safe_continue(packet, next, list, dccphtx_node) { 376 list_del_init(&packet->dccphtx_node); 377 dccp_tx_hist_entry_delete(hist, packet); 378 } 379 } 380 381 EXPORT_SYMBOL_GPL(dccp_tx_hist_purge_older); 382 383 void dccp_tx_hist_purge(struct dccp_tx_hist *hist, struct list_head *list) 384 { 385 struct dccp_tx_hist_entry *entry, *next; 386 387 list_for_each_entry_safe(entry, next, list, dccphtx_node) { 388 list_del_init(&entry->dccphtx_node); 389 dccp_tx_hist_entry_delete(hist, entry); 390 } 391 } 392 393 EXPORT_SYMBOL_GPL(dccp_tx_hist_purge); 394 395 MODULE_AUTHOR("Ian McDonald <iam4@cs.waikato.ac.nz>, " 396 "Arnaldo Carvalho de Melo <acme@ghostprotocols.net>"); 397 MODULE_DESCRIPTION("DCCP TFRC library"); 398 MODULE_LICENSE("GPL"); 399