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 <linux/slab.h> 40 #include "packet_history.h" 41 #include "../../dccp.h" 42 43 /** 44 * tfrc_tx_hist_entry - Simple singly-linked TX history list 45 * @next: next oldest entry (LIFO order) 46 * @seqno: sequence number of this entry 47 * @stamp: send time of packet with sequence number @seqno 48 */ 49 struct tfrc_tx_hist_entry { 50 struct tfrc_tx_hist_entry *next; 51 u64 seqno; 52 ktime_t stamp; 53 }; 54 55 /* 56 * Transmitter History Routines 57 */ 58 static struct kmem_cache *tfrc_tx_hist_slab; 59 60 int __init tfrc_tx_packet_history_init(void) 61 { 62 tfrc_tx_hist_slab = kmem_cache_create("tfrc_tx_hist", 63 sizeof(struct tfrc_tx_hist_entry), 64 0, SLAB_HWCACHE_ALIGN, NULL); 65 return tfrc_tx_hist_slab == NULL ? -ENOBUFS : 0; 66 } 67 68 void tfrc_tx_packet_history_exit(void) 69 { 70 if (tfrc_tx_hist_slab != NULL) { 71 kmem_cache_destroy(tfrc_tx_hist_slab); 72 tfrc_tx_hist_slab = NULL; 73 } 74 } 75 76 static struct tfrc_tx_hist_entry * 77 tfrc_tx_hist_find_entry(struct tfrc_tx_hist_entry *head, u64 seqno) 78 { 79 while (head != NULL && head->seqno != seqno) 80 head = head->next; 81 82 return head; 83 } 84 85 int tfrc_tx_hist_add(struct tfrc_tx_hist_entry **headp, u64 seqno) 86 { 87 struct tfrc_tx_hist_entry *entry = kmem_cache_alloc(tfrc_tx_hist_slab, gfp_any()); 88 89 if (entry == NULL) 90 return -ENOBUFS; 91 entry->seqno = seqno; 92 entry->stamp = ktime_get_real(); 93 entry->next = *headp; 94 *headp = entry; 95 return 0; 96 } 97 EXPORT_SYMBOL_GPL(tfrc_tx_hist_add); 98 99 void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry **headp) 100 { 101 struct tfrc_tx_hist_entry *head = *headp; 102 103 while (head != NULL) { 104 struct tfrc_tx_hist_entry *next = head->next; 105 106 kmem_cache_free(tfrc_tx_hist_slab, head); 107 head = next; 108 } 109 110 *headp = NULL; 111 } 112 EXPORT_SYMBOL_GPL(tfrc_tx_hist_purge); 113 114 u32 tfrc_tx_hist_rtt(struct tfrc_tx_hist_entry *head, const u64 seqno, 115 const ktime_t now) 116 { 117 u32 rtt = 0; 118 struct tfrc_tx_hist_entry *packet = tfrc_tx_hist_find_entry(head, seqno); 119 120 if (packet != NULL) { 121 rtt = ktime_us_delta(now, packet->stamp); 122 /* 123 * Garbage-collect older (irrelevant) entries: 124 */ 125 tfrc_tx_hist_purge(&packet->next); 126 } 127 128 return rtt; 129 } 130 EXPORT_SYMBOL_GPL(tfrc_tx_hist_rtt); 131 132 133 /* 134 * Receiver History Routines 135 */ 136 static struct kmem_cache *tfrc_rx_hist_slab; 137 138 int __init tfrc_rx_packet_history_init(void) 139 { 140 tfrc_rx_hist_slab = kmem_cache_create("tfrc_rxh_cache", 141 sizeof(struct tfrc_rx_hist_entry), 142 0, SLAB_HWCACHE_ALIGN, NULL); 143 return tfrc_rx_hist_slab == NULL ? -ENOBUFS : 0; 144 } 145 146 void tfrc_rx_packet_history_exit(void) 147 { 148 if (tfrc_rx_hist_slab != NULL) { 149 kmem_cache_destroy(tfrc_rx_hist_slab); 150 tfrc_rx_hist_slab = NULL; 151 } 152 } 153 154 static inline void tfrc_rx_hist_entry_from_skb(struct tfrc_rx_hist_entry *entry, 155 const struct sk_buff *skb, 156 const u64 ndp) 157 { 158 const struct dccp_hdr *dh = dccp_hdr(skb); 159 160 entry->tfrchrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq; 161 entry->tfrchrx_ccval = dh->dccph_ccval; 162 entry->tfrchrx_type = dh->dccph_type; 163 entry->tfrchrx_ndp = ndp; 164 entry->tfrchrx_tstamp = ktime_get_real(); 165 } 166 167 void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, 168 const struct sk_buff *skb, 169 const u64 ndp) 170 { 171 struct tfrc_rx_hist_entry *entry = tfrc_rx_hist_last_rcv(h); 172 173 tfrc_rx_hist_entry_from_skb(entry, skb, ndp); 174 } 175 EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet); 176 177 /* has the packet contained in skb been seen before? */ 178 int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb) 179 { 180 const u64 seq = DCCP_SKB_CB(skb)->dccpd_seq; 181 int i; 182 183 if (dccp_delta_seqno(tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, seq) <= 0) 184 return 1; 185 186 for (i = 1; i <= h->loss_count; i++) 187 if (tfrc_rx_hist_entry(h, i)->tfrchrx_seqno == seq) 188 return 1; 189 190 return 0; 191 } 192 EXPORT_SYMBOL_GPL(tfrc_rx_hist_duplicate); 193 194 static void tfrc_rx_hist_swap(struct tfrc_rx_hist *h, const u8 a, const u8 b) 195 { 196 const u8 idx_a = tfrc_rx_hist_index(h, a), 197 idx_b = tfrc_rx_hist_index(h, b); 198 struct tfrc_rx_hist_entry *tmp = h->ring[idx_a]; 199 200 h->ring[idx_a] = h->ring[idx_b]; 201 h->ring[idx_b] = tmp; 202 } 203 204 /* 205 * Private helper functions for loss detection. 206 * 207 * In the descriptions, `Si' refers to the sequence number of entry number i, 208 * whose NDP count is `Ni' (lower case is used for variables). 209 * Note: All __after_loss functions expect that a test against duplicates has 210 * been performed already: the seqno of the skb must not be less than the 211 * seqno of loss_prev; and it must not equal that of any valid hist_entry. 212 */ 213 static void __one_after_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u32 n2) 214 { 215 u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, 216 s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno, 217 s2 = DCCP_SKB_CB(skb)->dccpd_seq; 218 219 if (likely(dccp_delta_seqno(s1, s2) > 0)) { /* S1 < S2 */ 220 h->loss_count = 2; 221 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 2), skb, n2); 222 return; 223 } 224 225 /* S0 < S2 < S1 */ 226 227 if (dccp_loss_free(s0, s2, n2)) { 228 u64 n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp; 229 230 if (dccp_loss_free(s2, s1, n1)) { 231 /* hole is filled: S0, S2, and S1 are consecutive */ 232 h->loss_count = 0; 233 h->loss_start = tfrc_rx_hist_index(h, 1); 234 } else 235 /* gap between S2 and S1: just update loss_prev */ 236 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h), skb, n2); 237 238 } else { /* gap between S0 and S2 */ 239 /* 240 * Reorder history to insert S2 between S0 and S1 241 */ 242 tfrc_rx_hist_swap(h, 0, 3); 243 h->loss_start = tfrc_rx_hist_index(h, 3); 244 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 1), skb, n2); 245 h->loss_count = 2; 246 } 247 } 248 249 /* return 1 if a new loss event has been identified */ 250 static int __two_after_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u32 n3) 251 { 252 u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, 253 s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno, 254 s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno, 255 s3 = DCCP_SKB_CB(skb)->dccpd_seq; 256 257 if (likely(dccp_delta_seqno(s2, s3) > 0)) { /* S2 < S3 */ 258 h->loss_count = 3; 259 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 3), skb, n3); 260 return 1; 261 } 262 263 /* S3 < S2 */ 264 265 if (dccp_delta_seqno(s1, s3) > 0) { /* S1 < S3 < S2 */ 266 /* 267 * Reorder history to insert S3 between S1 and S2 268 */ 269 tfrc_rx_hist_swap(h, 2, 3); 270 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 2), skb, n3); 271 h->loss_count = 3; 272 return 1; 273 } 274 275 /* S0 < S3 < S1 */ 276 277 if (dccp_loss_free(s0, s3, n3)) { 278 u64 n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp; 279 280 if (dccp_loss_free(s3, s1, n1)) { 281 /* hole between S0 and S1 filled by S3 */ 282 u64 n2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_ndp; 283 284 if (dccp_loss_free(s1, s2, n2)) { 285 /* entire hole filled by S0, S3, S1, S2 */ 286 h->loss_start = tfrc_rx_hist_index(h, 2); 287 h->loss_count = 0; 288 } else { 289 /* gap remains between S1 and S2 */ 290 h->loss_start = tfrc_rx_hist_index(h, 1); 291 h->loss_count = 1; 292 } 293 294 } else /* gap exists between S3 and S1, loss_count stays at 2 */ 295 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h), skb, n3); 296 297 return 0; 298 } 299 300 /* 301 * The remaining case: S0 < S3 < S1 < S2; gap between S0 and S3 302 * Reorder history to insert S3 between S0 and S1. 303 */ 304 tfrc_rx_hist_swap(h, 0, 3); 305 h->loss_start = tfrc_rx_hist_index(h, 3); 306 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 1), skb, n3); 307 h->loss_count = 3; 308 309 return 1; 310 } 311 312 /* recycle RX history records to continue loss detection if necessary */ 313 static void __three_after_loss(struct tfrc_rx_hist *h) 314 { 315 /* 316 * At this stage we know already that there is a gap between S0 and S1 317 * (since S0 was the highest sequence number received before detecting 318 * the loss). To recycle the loss record, it is thus only necessary to 319 * check for other possible gaps between S1/S2 and between S2/S3. 320 */ 321 u64 s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno, 322 s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno, 323 s3 = tfrc_rx_hist_entry(h, 3)->tfrchrx_seqno; 324 u64 n2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_ndp, 325 n3 = tfrc_rx_hist_entry(h, 3)->tfrchrx_ndp; 326 327 if (dccp_loss_free(s1, s2, n2)) { 328 329 if (dccp_loss_free(s2, s3, n3)) { 330 /* no gap between S2 and S3: entire hole is filled */ 331 h->loss_start = tfrc_rx_hist_index(h, 3); 332 h->loss_count = 0; 333 } else { 334 /* gap between S2 and S3 */ 335 h->loss_start = tfrc_rx_hist_index(h, 2); 336 h->loss_count = 1; 337 } 338 339 } else { /* gap between S1 and S2 */ 340 h->loss_start = tfrc_rx_hist_index(h, 1); 341 h->loss_count = 2; 342 } 343 } 344 345 /** 346 * tfrc_rx_handle_loss - Loss detection and further processing 347 * @h: The non-empty RX history object 348 * @lh: Loss Intervals database to update 349 * @skb: Currently received packet 350 * @ndp: The NDP count belonging to @skb 351 * @calc_first_li: Caller-dependent computation of first loss interval in @lh 352 * @sk: Used by @calc_first_li (see tfrc_lh_interval_add) 353 * Chooses action according to pending loss, updates LI database when a new 354 * loss was detected, and does required post-processing. Returns 1 when caller 355 * should send feedback, 0 otherwise. 356 */ 357 int tfrc_rx_handle_loss(struct tfrc_rx_hist *h, 358 struct tfrc_loss_hist *lh, 359 struct sk_buff *skb, const u64 ndp, 360 u32 (*calc_first_li)(struct sock *), struct sock *sk) 361 { 362 int is_new_loss = 0; 363 364 if (h->loss_count == 1) { 365 __one_after_loss(h, skb, ndp); 366 } else if (h->loss_count != 2) { 367 DCCP_BUG("invalid loss_count %d", h->loss_count); 368 } else if (__two_after_loss(h, skb, ndp)) { 369 /* 370 * Update Loss Interval database and recycle RX records 371 */ 372 is_new_loss = tfrc_lh_interval_add(lh, h, calc_first_li, sk); 373 __three_after_loss(h); 374 } 375 return is_new_loss; 376 } 377 EXPORT_SYMBOL_GPL(tfrc_rx_handle_loss); 378 379 int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h) 380 { 381 int i; 382 383 for (i = 0; i <= TFRC_NDUPACK; i++) { 384 h->ring[i] = kmem_cache_alloc(tfrc_rx_hist_slab, GFP_ATOMIC); 385 if (h->ring[i] == NULL) 386 goto out_free; 387 } 388 389 h->loss_count = h->loss_start = 0; 390 return 0; 391 392 out_free: 393 while (i-- != 0) { 394 kmem_cache_free(tfrc_rx_hist_slab, h->ring[i]); 395 h->ring[i] = NULL; 396 } 397 return -ENOBUFS; 398 } 399 EXPORT_SYMBOL_GPL(tfrc_rx_hist_alloc); 400 401 void tfrc_rx_hist_purge(struct tfrc_rx_hist *h) 402 { 403 int i; 404 405 for (i = 0; i <= TFRC_NDUPACK; ++i) 406 if (h->ring[i] != NULL) { 407 kmem_cache_free(tfrc_rx_hist_slab, h->ring[i]); 408 h->ring[i] = NULL; 409 } 410 } 411 EXPORT_SYMBOL_GPL(tfrc_rx_hist_purge); 412 413 /** 414 * tfrc_rx_hist_rtt_last_s - reference entry to compute RTT samples against 415 */ 416 static inline struct tfrc_rx_hist_entry * 417 tfrc_rx_hist_rtt_last_s(const struct tfrc_rx_hist *h) 418 { 419 return h->ring[0]; 420 } 421 422 /** 423 * tfrc_rx_hist_rtt_prev_s: previously suitable (wrt rtt_last_s) RTT-sampling entry 424 */ 425 static inline struct tfrc_rx_hist_entry * 426 tfrc_rx_hist_rtt_prev_s(const struct tfrc_rx_hist *h) 427 { 428 return h->ring[h->rtt_sample_prev]; 429 } 430 431 /** 432 * tfrc_rx_hist_sample_rtt - Sample RTT from timestamp / CCVal 433 * Based on ideas presented in RFC 4342, 8.1. Returns 0 if it was not able 434 * to compute a sample with given data - calling function should check this. 435 */ 436 u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb) 437 { 438 u32 sample = 0, 439 delta_v = SUB16(dccp_hdr(skb)->dccph_ccval, 440 tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval); 441 442 if (delta_v < 1 || delta_v > 4) { /* unsuitable CCVal delta */ 443 if (h->rtt_sample_prev == 2) { /* previous candidate stored */ 444 sample = SUB16(tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_ccval, 445 tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval); 446 if (sample) 447 sample = 4 / sample * 448 ktime_us_delta(tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_tstamp, 449 tfrc_rx_hist_rtt_last_s(h)->tfrchrx_tstamp); 450 else /* 451 * FIXME: This condition is in principle not 452 * possible but occurs when CCID is used for 453 * two-way data traffic. I have tried to trace 454 * it, but the cause does not seem to be here. 455 */ 456 DCCP_BUG("please report to dccp@vger.kernel.org" 457 " => prev = %u, last = %u", 458 tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_ccval, 459 tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval); 460 } else if (delta_v < 1) { 461 h->rtt_sample_prev = 1; 462 goto keep_ref_for_next_time; 463 } 464 465 } else if (delta_v == 4) /* optimal match */ 466 sample = ktime_to_us(net_timedelta(tfrc_rx_hist_rtt_last_s(h)->tfrchrx_tstamp)); 467 else { /* suboptimal match */ 468 h->rtt_sample_prev = 2; 469 goto keep_ref_for_next_time; 470 } 471 472 if (unlikely(sample > DCCP_SANE_RTT_MAX)) { 473 DCCP_WARN("RTT sample %u too large, using max\n", sample); 474 sample = DCCP_SANE_RTT_MAX; 475 } 476 477 h->rtt_sample_prev = 0; /* use current entry as next reference */ 478 keep_ref_for_next_time: 479 480 return sample; 481 } 482 EXPORT_SYMBOL_GPL(tfrc_rx_hist_sample_rtt); 483