2 * net/dccp/packet_history.c
4 * Copyright (c) 2007 The University of Aberdeen, Scotland, UK
5 * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand.
7 * An implementation of the DCCP protocol
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
13 * This code also uses code from Lulea University, rereleased as GPL by its
15 * Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
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>.
21 * Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
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.
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.
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.
38 #include <linux/string.h>
39 #include <linux/slab.h>
40 #include "packet_history.h"
41 #include "../../dccp.h"
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
49 struct tfrc_tx_hist_entry
{
50 struct tfrc_tx_hist_entry
*next
;
56 * Transmitter History Routines
58 static struct kmem_cache
*tfrc_tx_hist_slab
;
60 int __init
tfrc_tx_packet_history_init(void)
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;
68 void tfrc_tx_packet_history_exit(void)
70 if (tfrc_tx_hist_slab
!= NULL
) {
71 kmem_cache_destroy(tfrc_tx_hist_slab
);
72 tfrc_tx_hist_slab
= NULL
;
76 static struct tfrc_tx_hist_entry
*
77 tfrc_tx_hist_find_entry(struct tfrc_tx_hist_entry
*head
, u64 seqno
)
79 while (head
!= NULL
&& head
->seqno
!= seqno
)
85 int tfrc_tx_hist_add(struct tfrc_tx_hist_entry
**headp
, u64 seqno
)
87 struct tfrc_tx_hist_entry
*entry
= kmem_cache_alloc(tfrc_tx_hist_slab
, gfp_any());
92 entry
->stamp
= ktime_get_real();
97 EXPORT_SYMBOL_GPL(tfrc_tx_hist_add
);
99 void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry
**headp
)
101 struct tfrc_tx_hist_entry
*head
= *headp
;
103 while (head
!= NULL
) {
104 struct tfrc_tx_hist_entry
*next
= head
->next
;
106 kmem_cache_free(tfrc_tx_hist_slab
, head
);
112 EXPORT_SYMBOL_GPL(tfrc_tx_hist_purge
);
114 u32
tfrc_tx_hist_rtt(struct tfrc_tx_hist_entry
*head
, const u64 seqno
,
118 struct tfrc_tx_hist_entry
*packet
= tfrc_tx_hist_find_entry(head
, seqno
);
120 if (packet
!= NULL
) {
121 rtt
= ktime_us_delta(now
, packet
->stamp
);
123 * Garbage-collect older (irrelevant) entries:
125 tfrc_tx_hist_purge(&packet
->next
);
130 EXPORT_SYMBOL_GPL(tfrc_tx_hist_rtt
);
134 * Receiver History Routines
136 static struct kmem_cache
*tfrc_rx_hist_slab
;
138 int __init
tfrc_rx_packet_history_init(void)
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;
146 void tfrc_rx_packet_history_exit(void)
148 if (tfrc_rx_hist_slab
!= NULL
) {
149 kmem_cache_destroy(tfrc_rx_hist_slab
);
150 tfrc_rx_hist_slab
= NULL
;
154 static inline void tfrc_rx_hist_entry_from_skb(struct tfrc_rx_hist_entry
*entry
,
155 const struct sk_buff
*skb
,
158 const struct dccp_hdr
*dh
= dccp_hdr(skb
);
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();
167 void tfrc_rx_hist_add_packet(struct tfrc_rx_hist
*h
,
168 const struct sk_buff
*skb
,
171 struct tfrc_rx_hist_entry
*entry
= tfrc_rx_hist_last_rcv(h
);
173 tfrc_rx_hist_entry_from_skb(entry
, skb
, ndp
);
175 EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet
);
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
)
180 const u64 seq
= DCCP_SKB_CB(skb
)->dccpd_seq
;
183 if (dccp_delta_seqno(tfrc_rx_hist_loss_prev(h
)->tfrchrx_seqno
, seq
) <= 0)
186 for (i
= 1; i
<= h
->loss_count
; i
++)
187 if (tfrc_rx_hist_entry(h
, i
)->tfrchrx_seqno
== seq
)
192 EXPORT_SYMBOL_GPL(tfrc_rx_hist_duplicate
);
194 /* initialise loss detection and disable RTT sampling */
195 static inline void tfrc_rx_hist_loss_indicated(struct tfrc_rx_hist
*h
)
200 /* indicate whether previously a packet was detected missing */
201 static inline int tfrc_rx_hist_loss_pending(const struct tfrc_rx_hist
*h
)
203 return h
->loss_count
;
206 /* any data packets missing between last reception and skb ? */
207 int tfrc_rx_hist_new_loss_indicated(struct tfrc_rx_hist
*h
,
208 const struct sk_buff
*skb
, u32 ndp
)
210 int delta
= dccp_delta_seqno(tfrc_rx_hist_last_rcv(h
)->tfrchrx_seqno
,
211 DCCP_SKB_CB(skb
)->dccpd_seq
);
213 if (delta
> 1 && ndp
< delta
)
214 tfrc_rx_hist_loss_indicated(h
);
216 return tfrc_rx_hist_loss_pending(h
);
218 EXPORT_SYMBOL_GPL(tfrc_rx_hist_new_loss_indicated
);
220 static void tfrc_rx_hist_swap(struct tfrc_rx_hist
*h
, const u8 a
, const u8 b
)
222 const u8 idx_a
= tfrc_rx_hist_index(h
, a
),
223 idx_b
= tfrc_rx_hist_index(h
, b
);
224 struct tfrc_rx_hist_entry
*tmp
= h
->ring
[idx_a
];
226 h
->ring
[idx_a
] = h
->ring
[idx_b
];
227 h
->ring
[idx_b
] = tmp
;
231 * Private helper functions for loss detection.
233 * In the descriptions, `Si' refers to the sequence number of entry number i,
234 * whose NDP count is `Ni' (lower case is used for variables).
235 * Note: All __after_loss functions expect that a test against duplicates has
236 * been performed already: the seqno of the skb must not be less than the
237 * seqno of loss_prev; and it must not equal that of any valid hist_entry.
239 static void __one_after_loss(struct tfrc_rx_hist
*h
, struct sk_buff
*skb
, u32 n2
)
241 u64 s0
= tfrc_rx_hist_loss_prev(h
)->tfrchrx_seqno
,
242 s1
= tfrc_rx_hist_entry(h
, 1)->tfrchrx_seqno
,
243 s2
= DCCP_SKB_CB(skb
)->dccpd_seq
;
244 int n1
= tfrc_rx_hist_entry(h
, 1)->tfrchrx_ndp
,
245 d12
= dccp_delta_seqno(s1
, s2
), d2
;
247 if (d12
> 0) { /* S1 < S2 */
249 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h
, 2), skb
, n2
);
254 d2
= dccp_delta_seqno(s0
, s2
);
256 if (d2
== 1 || n2
>= d2
) { /* S2 is direct successor of S0 */
259 if (d21
== 1 || n1
>= d21
) {
260 /* hole is filled: S0, S2, and S1 are consecutive */
262 h
->loss_start
= tfrc_rx_hist_index(h
, 1);
264 /* gap between S2 and S1: just update loss_prev */
265 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h
), skb
, n2
);
267 } else { /* hole between S0 and S2 */
269 * Reorder history to insert S2 between S0 and s1
271 tfrc_rx_hist_swap(h
, 0, 3);
272 h
->loss_start
= tfrc_rx_hist_index(h
, 3);
273 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h
, 1), skb
, n2
);
278 /* return 1 if a new loss event has been identified */
279 static int __two_after_loss(struct tfrc_rx_hist
*h
, struct sk_buff
*skb
, u32 n3
)
281 u64 s0
= tfrc_rx_hist_loss_prev(h
)->tfrchrx_seqno
,
282 s1
= tfrc_rx_hist_entry(h
, 1)->tfrchrx_seqno
,
283 s2
= tfrc_rx_hist_entry(h
, 2)->tfrchrx_seqno
,
284 s3
= DCCP_SKB_CB(skb
)->dccpd_seq
;
285 int n1
= tfrc_rx_hist_entry(h
, 1)->tfrchrx_ndp
,
286 d23
= dccp_delta_seqno(s2
, s3
), d13
, d3
, d31
;
288 if (d23
> 0) { /* S2 < S3 */
290 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h
, 3), skb
, n3
);
295 d13
= dccp_delta_seqno(s1
, s3
);
299 * The sequence number order is S1, S3, S2
300 * Reorder history to insert entry between S1 and S2
302 tfrc_rx_hist_swap(h
, 2, 3);
303 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h
, 2), skb
, n3
);
310 d3
= dccp_delta_seqno(s0
, s3
);
312 if (d3
== 1 || n3
>= d3
) { /* S3 is a successor of S0 */
314 if (d31
== 1 || n1
>= d31
) {
315 /* hole between S0 and S1 filled by S3 */
316 int d2
= dccp_delta_seqno(s1
, s2
),
317 n2
= tfrc_rx_hist_entry(h
, 2)->tfrchrx_ndp
;
319 if (d2
== 1 || n2
>= d2
) {
320 /* entire hole filled by S0, S3, S1, S2 */
321 h
->loss_start
= tfrc_rx_hist_index(h
, 2);
324 /* gap remains between S1 and S2 */
325 h
->loss_start
= tfrc_rx_hist_index(h
, 1);
329 } else /* gap exists between S3 and S1, loss_count stays at 2 */
330 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h
), skb
, n3
);
336 * The remaining case: S3 is not a successor of S0.
337 * Sequence order is S0, S3, S1, S2; reorder to insert between S0 and S1
339 tfrc_rx_hist_swap(h
, 0, 3);
340 h
->loss_start
= tfrc_rx_hist_index(h
, 3);
341 tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h
, 1), skb
, n3
);
347 /* return the signed modulo-2^48 sequence number distance from entry e1 to e2 */
348 static s64
tfrc_rx_hist_delta_seqno(struct tfrc_rx_hist
*h
, u8 e1
, u8 e2
)
350 DCCP_BUG_ON(e1
> h
->loss_count
|| e2
> h
->loss_count
);
352 return dccp_delta_seqno(tfrc_rx_hist_entry(h
, e1
)->tfrchrx_seqno
,
353 tfrc_rx_hist_entry(h
, e2
)->tfrchrx_seqno
);
356 /* recycle RX history records to continue loss detection if necessary */
357 static void __three_after_loss(struct tfrc_rx_hist
*h
)
360 * The distance between S0 and S1 is always greater than 1 and the NDP
361 * count of S1 is smaller than this distance. Otherwise there would
362 * have been no loss. Hence it is only necessary to see whether there
363 * are further missing data packets between S1/S2 and S2/S3.
365 int d2
= tfrc_rx_hist_delta_seqno(h
, 1, 2),
366 d3
= tfrc_rx_hist_delta_seqno(h
, 2, 3),
367 n2
= tfrc_rx_hist_entry(h
, 2)->tfrchrx_ndp
,
368 n3
= tfrc_rx_hist_entry(h
, 3)->tfrchrx_ndp
;
370 if (d2
== 1 || n2
>= d2
) { /* S2 is successor to S1 */
372 if (d3
== 1 || n3
>= d3
) {
373 /* S3 is successor of S2: entire hole is filled */
374 h
->loss_start
= tfrc_rx_hist_index(h
, 3);
377 /* gap between S2 and S3 */
378 h
->loss_start
= tfrc_rx_hist_index(h
, 2);
382 } else { /* gap between S1 and S2 */
383 h
->loss_start
= tfrc_rx_hist_index(h
, 1);
389 * tfrc_rx_handle_loss - Loss detection and further processing
390 * @h: The non-empty RX history object
391 * @lh: Loss Intervals database to update
392 * @skb: Currently received packet
393 * @ndp: The NDP count belonging to @skb
394 * @calc_first_li: Caller-dependent computation of first loss interval in @lh
395 * @sk: Used by @calc_first_li (see tfrc_lh_interval_add)
396 * Chooses action according to pending loss, updates LI database when a new
397 * loss was detected, and does required post-processing. Returns 1 when caller
398 * should send feedback, 0 otherwise.
400 int tfrc_rx_handle_loss(struct tfrc_rx_hist
*h
,
401 struct tfrc_loss_hist
*lh
,
402 struct sk_buff
*skb
, u32 ndp
,
403 u32 (*calc_first_li
)(struct sock
*), struct sock
*sk
)
407 if (h
->loss_count
== 1) {
408 __one_after_loss(h
, skb
, ndp
);
409 } else if (h
->loss_count
!= 2) {
410 DCCP_BUG("invalid loss_count %d", h
->loss_count
);
411 } else if (__two_after_loss(h
, skb
, ndp
)) {
413 * Update Loss Interval database and recycle RX records
415 is_new_loss
= tfrc_lh_interval_add(lh
, h
, calc_first_li
, sk
);
416 __three_after_loss(h
);
420 EXPORT_SYMBOL_GPL(tfrc_rx_handle_loss
);
422 int tfrc_rx_hist_alloc(struct tfrc_rx_hist
*h
)
426 for (i
= 0; i
<= TFRC_NDUPACK
; i
++) {
427 h
->ring
[i
] = kmem_cache_alloc(tfrc_rx_hist_slab
, GFP_ATOMIC
);
428 if (h
->ring
[i
] == NULL
)
432 h
->loss_count
= h
->loss_start
= 0;
437 kmem_cache_free(tfrc_rx_hist_slab
, h
->ring
[i
]);
442 EXPORT_SYMBOL_GPL(tfrc_rx_hist_alloc
);
444 void tfrc_rx_hist_purge(struct tfrc_rx_hist
*h
)
448 for (i
= 0; i
<= TFRC_NDUPACK
; ++i
)
449 if (h
->ring
[i
] != NULL
) {
450 kmem_cache_free(tfrc_rx_hist_slab
, h
->ring
[i
]);
454 EXPORT_SYMBOL_GPL(tfrc_rx_hist_purge
);
457 * tfrc_rx_hist_rtt_last_s - reference entry to compute RTT samples against
459 static inline struct tfrc_rx_hist_entry
*
460 tfrc_rx_hist_rtt_last_s(const struct tfrc_rx_hist
*h
)
466 * tfrc_rx_hist_rtt_prev_s: previously suitable (wrt rtt_last_s) RTT-sampling entry
468 static inline struct tfrc_rx_hist_entry
*
469 tfrc_rx_hist_rtt_prev_s(const struct tfrc_rx_hist
*h
)
471 return h
->ring
[h
->rtt_sample_prev
];
475 * tfrc_rx_hist_sample_rtt - Sample RTT from timestamp / CCVal
476 * Based on ideas presented in RFC 4342, 8.1. Returns 0 if it was not able
477 * to compute a sample with given data - calling function should check this.
479 u32
tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist
*h
, const struct sk_buff
*skb
)
482 delta_v
= SUB16(dccp_hdr(skb
)->dccph_ccval
,
483 tfrc_rx_hist_rtt_last_s(h
)->tfrchrx_ccval
);
485 if (delta_v
< 1 || delta_v
> 4) { /* unsuitable CCVal delta */
486 if (h
->rtt_sample_prev
== 2) { /* previous candidate stored */
487 sample
= SUB16(tfrc_rx_hist_rtt_prev_s(h
)->tfrchrx_ccval
,
488 tfrc_rx_hist_rtt_last_s(h
)->tfrchrx_ccval
);
490 sample
= 4 / sample
*
491 ktime_us_delta(tfrc_rx_hist_rtt_prev_s(h
)->tfrchrx_tstamp
,
492 tfrc_rx_hist_rtt_last_s(h
)->tfrchrx_tstamp
);
494 * FIXME: This condition is in principle not
495 * possible but occurs when CCID is used for
496 * two-way data traffic. I have tried to trace
497 * it, but the cause does not seem to be here.
499 DCCP_BUG("please report to dccp@vger.kernel.org"
500 " => prev = %u, last = %u",
501 tfrc_rx_hist_rtt_prev_s(h
)->tfrchrx_ccval
,
502 tfrc_rx_hist_rtt_last_s(h
)->tfrchrx_ccval
);
503 } else if (delta_v
< 1) {
504 h
->rtt_sample_prev
= 1;
505 goto keep_ref_for_next_time
;
508 } else if (delta_v
== 4) /* optimal match */
509 sample
= ktime_to_us(net_timedelta(tfrc_rx_hist_rtt_last_s(h
)->tfrchrx_tstamp
));
510 else { /* suboptimal match */
511 h
->rtt_sample_prev
= 2;
512 goto keep_ref_for_next_time
;
515 if (unlikely(sample
> DCCP_SANE_RTT_MAX
)) {
516 DCCP_WARN("RTT sample %u too large, using max\n", sample
);
517 sample
= DCCP_SANE_RTT_MAX
;
520 h
->rtt_sample_prev
= 0; /* use current entry as next reference */
521 keep_ref_for_next_time
:
525 EXPORT_SYMBOL_GPL(tfrc_rx_hist_sample_rtt
);