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 static struct tfrc_tx_hist_entry
*
61 tfrc_tx_hist_find_entry(struct tfrc_tx_hist_entry
*head
, u64 seqno
)
63 while (head
!= NULL
&& head
->seqno
!= seqno
)
69 int tfrc_tx_hist_add(struct tfrc_tx_hist_entry
**headp
, u64 seqno
)
71 struct tfrc_tx_hist_entry
*entry
= kmem_cache_alloc(tfrc_tx_hist_slab
, gfp_any());
76 entry
->stamp
= ktime_get_real();
81 EXPORT_SYMBOL_GPL(tfrc_tx_hist_add
);
83 void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry
**headp
)
85 struct tfrc_tx_hist_entry
*head
= *headp
;
87 while (head
!= NULL
) {
88 struct tfrc_tx_hist_entry
*next
= head
->next
;
90 kmem_cache_free(tfrc_tx_hist_slab
, head
);
96 EXPORT_SYMBOL_GPL(tfrc_tx_hist_purge
);
98 u32
tfrc_tx_hist_rtt(struct tfrc_tx_hist_entry
*head
, const u64 seqno
,
102 struct tfrc_tx_hist_entry
*packet
= tfrc_tx_hist_find_entry(head
, seqno
);
104 if (packet
!= NULL
) {
105 rtt
= ktime_us_delta(now
, packet
->stamp
);
107 * Garbage-collect older (irrelevant) entries:
109 tfrc_tx_hist_purge(&packet
->next
);
114 EXPORT_SYMBOL_GPL(tfrc_tx_hist_rtt
);
118 * tfrc_rx_hist_index - index to reach n-th entry after loss_start
120 static inline u8
tfrc_rx_hist_index(const struct tfrc_rx_hist
*h
, const u8 n
)
122 return (h
->loss_start
+ n
) & TFRC_NDUPACK
;
126 * tfrc_rx_hist_last_rcv - entry with highest-received-seqno so far
128 static inline struct tfrc_rx_hist_entry
*
129 tfrc_rx_hist_last_rcv(const struct tfrc_rx_hist
*h
)
131 return h
->ring
[tfrc_rx_hist_index(h
, h
->loss_count
)];
135 * Receiver History Routines
137 static struct kmem_cache
*tfrc_rx_hist_slab
;
139 void tfrc_rx_hist_add_packet(struct tfrc_rx_hist
*h
,
140 const struct sk_buff
*skb
,
143 struct tfrc_rx_hist_entry
*entry
= tfrc_rx_hist_last_rcv(h
);
144 const struct dccp_hdr
*dh
= dccp_hdr(skb
);
146 entry
->tfrchrx_seqno
= DCCP_SKB_CB(skb
)->dccpd_seq
;
147 entry
->tfrchrx_ccval
= dh
->dccph_ccval
;
148 entry
->tfrchrx_type
= dh
->dccph_type
;
149 entry
->tfrchrx_ndp
= ndp
;
150 entry
->tfrchrx_tstamp
= ktime_get_real();
152 EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet
);
154 static inline void tfrc_rx_hist_entry_delete(struct tfrc_rx_hist_entry
*entry
)
156 kmem_cache_free(tfrc_rx_hist_slab
, entry
);
160 * tfrc_rx_hist_entry - return the n-th history entry after loss_start
162 static inline struct tfrc_rx_hist_entry
*
163 tfrc_rx_hist_entry(const struct tfrc_rx_hist
*h
, const u8 n
)
165 return h
->ring
[tfrc_rx_hist_index(h
, n
)];
169 * tfrc_rx_hist_loss_prev - entry with highest-received-seqno before loss was detected
171 static inline struct tfrc_rx_hist_entry
*
172 tfrc_rx_hist_loss_prev(const struct tfrc_rx_hist
*h
)
174 return h
->ring
[h
->loss_start
];
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 int tfrc_rx_hist_alloc(struct tfrc_rx_hist
*h
)
224 for (i
= 0; i
<= TFRC_NDUPACK
; i
++) {
225 h
->ring
[i
] = kmem_cache_alloc(tfrc_rx_hist_slab
, GFP_ATOMIC
);
226 if (h
->ring
[i
] == NULL
)
230 h
->loss_count
= h
->loss_start
= 0;
235 kmem_cache_free(tfrc_rx_hist_slab
, h
->ring
[i
]);
240 EXPORT_SYMBOL_GPL(tfrc_rx_hist_alloc
);
242 void tfrc_rx_hist_purge(struct tfrc_rx_hist
*h
)
246 for (i
= 0; i
<= TFRC_NDUPACK
; ++i
)
247 if (h
->ring
[i
] != NULL
) {
248 kmem_cache_free(tfrc_rx_hist_slab
, h
->ring
[i
]);
252 EXPORT_SYMBOL_GPL(tfrc_rx_hist_purge
);
255 * tfrc_rx_hist_rtt_last_s - reference entry to compute RTT samples against
257 static inline struct tfrc_rx_hist_entry
*
258 tfrc_rx_hist_rtt_last_s(const struct tfrc_rx_hist
*h
)
264 * tfrc_rx_hist_rtt_prev_s: previously suitable (wrt rtt_last_s) RTT-sampling entry
266 static inline struct tfrc_rx_hist_entry
*
267 tfrc_rx_hist_rtt_prev_s(const struct tfrc_rx_hist
*h
)
269 return h
->ring
[h
->rtt_sample_prev
];
273 * tfrc_rx_hist_sample_rtt - Sample RTT from timestamp / CCVal
274 * Based on ideas presented in RFC 4342, 8.1. Returns 0 if it was not able
275 * to compute a sample with given data - calling function should check this.
277 u32
tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist
*h
, const struct sk_buff
*skb
)
280 delta_v
= SUB16(dccp_hdr(skb
)->dccph_ccval
,
281 tfrc_rx_hist_rtt_last_s(h
)->tfrchrx_ccval
);
283 if (delta_v
< 1 || delta_v
> 4) { /* unsuitable CCVal delta */
284 if (h
->rtt_sample_prev
== 2) { /* previous candidate stored */
285 sample
= SUB16(tfrc_rx_hist_rtt_prev_s(h
)->tfrchrx_ccval
,
286 tfrc_rx_hist_rtt_last_s(h
)->tfrchrx_ccval
);
288 sample
= 4 / sample
*
289 ktime_us_delta(tfrc_rx_hist_rtt_prev_s(h
)->tfrchrx_tstamp
,
290 tfrc_rx_hist_rtt_last_s(h
)->tfrchrx_tstamp
);
292 * FIXME: This condition is in principle not
293 * possible but occurs when CCID is used for
294 * two-way data traffic. I have tried to trace
295 * it, but the cause does not seem to be here.
297 DCCP_BUG("please report to dccp@vger.kernel.org"
298 " => prev = %u, last = %u",
299 tfrc_rx_hist_rtt_prev_s(h
)->tfrchrx_ccval
,
300 tfrc_rx_hist_rtt_last_s(h
)->tfrchrx_ccval
);
301 } else if (delta_v
< 1) {
302 h
->rtt_sample_prev
= 1;
303 goto keep_ref_for_next_time
;
306 } else if (delta_v
== 4) /* optimal match */
307 sample
= ktime_to_us(net_timedelta(tfrc_rx_hist_rtt_last_s(h
)->tfrchrx_tstamp
));
308 else { /* suboptimal match */
309 h
->rtt_sample_prev
= 2;
310 goto keep_ref_for_next_time
;
313 if (unlikely(sample
> DCCP_SANE_RTT_MAX
)) {
314 DCCP_WARN("RTT sample %u too large, using max\n", sample
);
315 sample
= DCCP_SANE_RTT_MAX
;
318 h
->rtt_sample_prev
= 0; /* use current entry as next reference */
319 keep_ref_for_next_time
:
323 EXPORT_SYMBOL_GPL(tfrc_rx_hist_sample_rtt
);
325 __init
int packet_history_init(void)
327 tfrc_tx_hist_slab
= kmem_cache_create("tfrc_tx_hist",
328 sizeof(struct tfrc_tx_hist_entry
), 0,
329 SLAB_HWCACHE_ALIGN
, NULL
);
330 if (tfrc_tx_hist_slab
== NULL
)
333 tfrc_rx_hist_slab
= kmem_cache_create("tfrc_rx_hist",
334 sizeof(struct tfrc_rx_hist_entry
), 0,
335 SLAB_HWCACHE_ALIGN
, NULL
);
336 if (tfrc_rx_hist_slab
== NULL
)
342 kmem_cache_destroy(tfrc_tx_hist_slab
);
343 tfrc_tx_hist_slab
= NULL
;
348 void packet_history_exit(void)
350 if (tfrc_tx_hist_slab
!= NULL
) {
351 kmem_cache_destroy(tfrc_tx_hist_slab
);
352 tfrc_tx_hist_slab
= NULL
;
355 if (tfrc_rx_hist_slab
!= NULL
) {
356 kmem_cache_destroy(tfrc_rx_hist_slab
);
357 tfrc_rx_hist_slab
= NULL
;