Commit | Line | Data |
---|---|---|
8c60f3fa | 1 | /* |
f3166c07 | 2 | * net/dccp/packet_history.c |
8c60f3fa | 3 | * |
276f2edc ACM |
4 | * Copyright (c) 2007 The University of Aberdeen, Scotland, UK |
5 | * Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand. | |
8c60f3fa ACM |
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/ | |
e6bccd35 | 11 | * or e-mail Ian McDonald - ian.mcdonald@jandi.co.nz |
8c60f3fa ACM |
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 | ||
8c60f3fa | 38 | #include <linux/string.h> |
b84a2189 | 39 | #include <linux/slab.h> |
8c60f3fa | 40 | #include "packet_history.h" |
b84a2189 | 41 | #include "../../dccp.h" |
8c60f3fa | 42 | |
7af5af30 | 43 | /* |
276f2edc | 44 | * Transmitter History Routines |
7af5af30 | 45 | */ |
e9c8b24a | 46 | static struct kmem_cache *tfrc_tx_hist_slab; |
7af5af30 | 47 | |
df8f83fd GR |
48 | int __init tfrc_tx_packet_history_init(void) |
49 | { | |
50 | tfrc_tx_hist_slab = kmem_cache_create("tfrc_tx_hist", | |
51 | sizeof(struct tfrc_tx_hist_entry), | |
52 | 0, SLAB_HWCACHE_ALIGN, NULL); | |
53 | return tfrc_tx_hist_slab == NULL ? -ENOBUFS : 0; | |
54 | } | |
55 | ||
56 | void tfrc_tx_packet_history_exit(void) | |
57 | { | |
58 | if (tfrc_tx_hist_slab != NULL) { | |
59 | kmem_cache_destroy(tfrc_tx_hist_slab); | |
60 | tfrc_tx_hist_slab = NULL; | |
61 | } | |
62 | } | |
63 | ||
276f2edc | 64 | int tfrc_tx_hist_add(struct tfrc_tx_hist_entry **headp, u64 seqno) |
7af5af30 | 65 | { |
e9c8b24a | 66 | struct tfrc_tx_hist_entry *entry = kmem_cache_alloc(tfrc_tx_hist_slab, gfp_any()); |
276f2edc ACM |
67 | |
68 | if (entry == NULL) | |
69 | return -ENOBUFS; | |
70 | entry->seqno = seqno; | |
71 | entry->stamp = ktime_get_real(); | |
72 | entry->next = *headp; | |
73 | *headp = entry; | |
74 | return 0; | |
7af5af30 | 75 | } |
276f2edc | 76 | EXPORT_SYMBOL_GPL(tfrc_tx_hist_add); |
7af5af30 | 77 | |
276f2edc | 78 | void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry **headp) |
7af5af30 | 79 | { |
276f2edc | 80 | struct tfrc_tx_hist_entry *head = *headp; |
7af5af30 | 81 | |
276f2edc ACM |
82 | while (head != NULL) { |
83 | struct tfrc_tx_hist_entry *next = head->next; | |
7af5af30 | 84 | |
e9c8b24a | 85 | kmem_cache_free(tfrc_tx_hist_slab, head); |
276f2edc | 86 | head = next; |
7af5af30 | 87 | } |
7af5af30 | 88 | |
276f2edc ACM |
89 | *headp = NULL; |
90 | } | |
91 | EXPORT_SYMBOL_GPL(tfrc_tx_hist_purge); | |
7af5af30 | 92 | |
78282d2a GR |
93 | /* |
94 | * Receiver History Routines | |
95 | */ | |
96 | static struct kmem_cache *tfrc_rx_hist_slab; | |
97 | ||
df8f83fd GR |
98 | int __init tfrc_rx_packet_history_init(void) |
99 | { | |
100 | tfrc_rx_hist_slab = kmem_cache_create("tfrc_rxh_cache", | |
101 | sizeof(struct tfrc_rx_hist_entry), | |
102 | 0, SLAB_HWCACHE_ALIGN, NULL); | |
103 | return tfrc_rx_hist_slab == NULL ? -ENOBUFS : 0; | |
104 | } | |
105 | ||
106 | void tfrc_rx_packet_history_exit(void) | |
107 | { | |
108 | if (tfrc_rx_hist_slab != NULL) { | |
109 | kmem_cache_destroy(tfrc_rx_hist_slab); | |
110 | tfrc_rx_hist_slab = NULL; | |
111 | } | |
112 | } | |
113 | ||
8a9c7e92 GR |
114 | static inline void tfrc_rx_hist_entry_from_skb(struct tfrc_rx_hist_entry *entry, |
115 | const struct sk_buff *skb, | |
5b5d0e70 | 116 | const u64 ndp) |
8c60f3fa | 117 | { |
b84a2189 ACM |
118 | const struct dccp_hdr *dh = dccp_hdr(skb); |
119 | ||
120 | entry->tfrchrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq; | |
121 | entry->tfrchrx_ccval = dh->dccph_ccval; | |
122 | entry->tfrchrx_type = dh->dccph_type; | |
123 | entry->tfrchrx_ndp = ndp; | |
124 | entry->tfrchrx_tstamp = ktime_get_real(); | |
8c60f3fa | 125 | } |
8a9c7e92 GR |
126 | |
127 | void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, | |
128 | const struct sk_buff *skb, | |
5b5d0e70 | 129 | const u64 ndp) |
8a9c7e92 GR |
130 | { |
131 | struct tfrc_rx_hist_entry *entry = tfrc_rx_hist_last_rcv(h); | |
132 | ||
133 | tfrc_rx_hist_entry_from_skb(entry, skb, ndp); | |
134 | } | |
b84a2189 | 135 | EXPORT_SYMBOL_GPL(tfrc_rx_hist_add_packet); |
8c60f3fa | 136 | |
b84a2189 ACM |
137 | /* has the packet contained in skb been seen before? */ |
138 | int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb) | |
139 | { | |
140 | const u64 seq = DCCP_SKB_CB(skb)->dccpd_seq; | |
141 | int i; | |
142 | ||
143 | if (dccp_delta_seqno(tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, seq) <= 0) | |
144 | return 1; | |
8c60f3fa | 145 | |
b84a2189 ACM |
146 | for (i = 1; i <= h->loss_count; i++) |
147 | if (tfrc_rx_hist_entry(h, i)->tfrchrx_seqno == seq) | |
148 | return 1; | |
8c60f3fa | 149 | |
b84a2189 | 150 | return 0; |
7af5af30 | 151 | } |
b84a2189 | 152 | EXPORT_SYMBOL_GPL(tfrc_rx_hist_duplicate); |
7af5af30 | 153 | |
2b81143a GR |
154 | |
155 | static void __tfrc_rx_hist_swap(struct tfrc_rx_hist *h, const u8 a, const u8 b) | |
156 | { | |
157 | struct tfrc_rx_hist_entry *tmp = h->ring[a]; | |
158 | ||
159 | h->ring[a] = h->ring[b]; | |
160 | h->ring[b] = tmp; | |
161 | } | |
162 | ||
8a9c7e92 GR |
163 | static void tfrc_rx_hist_swap(struct tfrc_rx_hist *h, const u8 a, const u8 b) |
164 | { | |
2b81143a GR |
165 | __tfrc_rx_hist_swap(h, tfrc_rx_hist_index(h, a), |
166 | tfrc_rx_hist_index(h, b)); | |
167 | } | |
8a9c7e92 | 168 | |
2b81143a GR |
169 | /** |
170 | * tfrc_rx_hist_resume_rtt_sampling - Prepare RX history for RTT sampling | |
171 | * This is called after loss detection has finished, when the history entry | |
172 | * with the index of `loss_count' holds the highest-received sequence number. | |
173 | * RTT sampling requires this information at ring[0] (tfrc_rx_hist_sample_rtt). | |
174 | */ | |
175 | static inline void tfrc_rx_hist_resume_rtt_sampling(struct tfrc_rx_hist *h) | |
176 | { | |
177 | __tfrc_rx_hist_swap(h, 0, tfrc_rx_hist_index(h, h->loss_count)); | |
178 | h->loss_count = h->loss_start = 0; | |
8a9c7e92 GR |
179 | } |
180 | ||
181 | /* | |
182 | * Private helper functions for loss detection. | |
183 | * | |
184 | * In the descriptions, `Si' refers to the sequence number of entry number i, | |
185 | * whose NDP count is `Ni' (lower case is used for variables). | |
b552c623 GR |
186 | * Note: All __xxx_loss functions expect that a test against duplicates has been |
187 | * performed already: the seqno of the skb must not be less than the seqno | |
188 | * of loss_prev; and it must not equal that of any valid history entry. | |
8a9c7e92 | 189 | */ |
b552c623 GR |
190 | static void __do_track_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u64 n1) |
191 | { | |
192 | u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, | |
193 | s1 = DCCP_SKB_CB(skb)->dccpd_seq; | |
194 | ||
88e97a93 | 195 | if (!dccp_loss_free(s0, s1, n1)) /* gap between S0 and S1 */ |
b552c623 | 196 | h->loss_count = 1; |
b552c623 GR |
197 | } |
198 | ||
8a9c7e92 GR |
199 | static void __one_after_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u32 n2) |
200 | { | |
201 | u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, | |
202 | s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno, | |
203 | s2 = DCCP_SKB_CB(skb)->dccpd_seq; | |
8a9c7e92 | 204 | |
2013c7e3 | 205 | if (likely(dccp_delta_seqno(s1, s2) > 0)) { /* S1 < S2 */ |
8a9c7e92 GR |
206 | h->loss_count = 2; |
207 | tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 2), skb, n2); | |
208 | return; | |
209 | } | |
210 | ||
211 | /* S0 < S2 < S1 */ | |
8a9c7e92 | 212 | |
2013c7e3 GR |
213 | if (dccp_loss_free(s0, s2, n2)) { |
214 | u64 n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp; | |
8a9c7e92 | 215 | |
2013c7e3 | 216 | if (dccp_loss_free(s2, s1, n1)) { |
8a9c7e92 | 217 | /* hole is filled: S0, S2, and S1 are consecutive */ |
2b81143a | 218 | tfrc_rx_hist_resume_rtt_sampling(h); |
8a9c7e92 GR |
219 | } else |
220 | /* gap between S2 and S1: just update loss_prev */ | |
221 | tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h), skb, n2); | |
222 | ||
2013c7e3 | 223 | } else { /* gap between S0 and S2 */ |
8a9c7e92 | 224 | /* |
2013c7e3 | 225 | * Reorder history to insert S2 between S0 and S1 |
8a9c7e92 GR |
226 | */ |
227 | tfrc_rx_hist_swap(h, 0, 3); | |
228 | h->loss_start = tfrc_rx_hist_index(h, 3); | |
229 | tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 1), skb, n2); | |
230 | h->loss_count = 2; | |
231 | } | |
232 | } | |
233 | ||
234 | /* return 1 if a new loss event has been identified */ | |
235 | static int __two_after_loss(struct tfrc_rx_hist *h, struct sk_buff *skb, u32 n3) | |
236 | { | |
237 | u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, | |
238 | s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno, | |
239 | s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno, | |
240 | s3 = DCCP_SKB_CB(skb)->dccpd_seq; | |
8a9c7e92 | 241 | |
2013c7e3 | 242 | if (likely(dccp_delta_seqno(s2, s3) > 0)) { /* S2 < S3 */ |
8a9c7e92 GR |
243 | h->loss_count = 3; |
244 | tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 3), skb, n3); | |
245 | return 1; | |
246 | } | |
247 | ||
248 | /* S3 < S2 */ | |
8a9c7e92 | 249 | |
2013c7e3 | 250 | if (dccp_delta_seqno(s1, s3) > 0) { /* S1 < S3 < S2 */ |
8a9c7e92 | 251 | /* |
2013c7e3 | 252 | * Reorder history to insert S3 between S1 and S2 |
8a9c7e92 GR |
253 | */ |
254 | tfrc_rx_hist_swap(h, 2, 3); | |
255 | tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 2), skb, n3); | |
256 | h->loss_count = 3; | |
257 | return 1; | |
258 | } | |
259 | ||
260 | /* S0 < S3 < S1 */ | |
8a9c7e92 | 261 | |
2013c7e3 GR |
262 | if (dccp_loss_free(s0, s3, n3)) { |
263 | u64 n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp; | |
8a9c7e92 | 264 | |
2013c7e3 | 265 | if (dccp_loss_free(s3, s1, n1)) { |
8a9c7e92 | 266 | /* hole between S0 and S1 filled by S3 */ |
2013c7e3 | 267 | u64 n2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_ndp; |
8a9c7e92 | 268 | |
2013c7e3 | 269 | if (dccp_loss_free(s1, s2, n2)) { |
8a9c7e92 | 270 | /* entire hole filled by S0, S3, S1, S2 */ |
2b81143a | 271 | tfrc_rx_hist_resume_rtt_sampling(h); |
8a9c7e92 GR |
272 | } else { |
273 | /* gap remains between S1 and S2 */ | |
274 | h->loss_start = tfrc_rx_hist_index(h, 1); | |
275 | h->loss_count = 1; | |
276 | } | |
277 | ||
278 | } else /* gap exists between S3 and S1, loss_count stays at 2 */ | |
279 | tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_loss_prev(h), skb, n3); | |
280 | ||
281 | return 0; | |
282 | } | |
283 | ||
284 | /* | |
2013c7e3 GR |
285 | * The remaining case: S0 < S3 < S1 < S2; gap between S0 and S3 |
286 | * Reorder history to insert S3 between S0 and S1. | |
8a9c7e92 GR |
287 | */ |
288 | tfrc_rx_hist_swap(h, 0, 3); | |
289 | h->loss_start = tfrc_rx_hist_index(h, 3); | |
290 | tfrc_rx_hist_entry_from_skb(tfrc_rx_hist_entry(h, 1), skb, n3); | |
291 | h->loss_count = 3; | |
292 | ||
293 | return 1; | |
294 | } | |
295 | ||
8a9c7e92 GR |
296 | /* recycle RX history records to continue loss detection if necessary */ |
297 | static void __three_after_loss(struct tfrc_rx_hist *h) | |
298 | { | |
299 | /* | |
2013c7e3 GR |
300 | * At this stage we know already that there is a gap between S0 and S1 |
301 | * (since S0 was the highest sequence number received before detecting | |
302 | * the loss). To recycle the loss record, it is thus only necessary to | |
303 | * check for other possible gaps between S1/S2 and between S2/S3. | |
8a9c7e92 | 304 | */ |
2013c7e3 GR |
305 | u64 s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno, |
306 | s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno, | |
307 | s3 = tfrc_rx_hist_entry(h, 3)->tfrchrx_seqno; | |
308 | u64 n2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_ndp, | |
8a9c7e92 GR |
309 | n3 = tfrc_rx_hist_entry(h, 3)->tfrchrx_ndp; |
310 | ||
2013c7e3 | 311 | if (dccp_loss_free(s1, s2, n2)) { |
8a9c7e92 | 312 | |
2013c7e3 GR |
313 | if (dccp_loss_free(s2, s3, n3)) { |
314 | /* no gap between S2 and S3: entire hole is filled */ | |
2b81143a | 315 | tfrc_rx_hist_resume_rtt_sampling(h); |
8a9c7e92 GR |
316 | } else { |
317 | /* gap between S2 and S3 */ | |
318 | h->loss_start = tfrc_rx_hist_index(h, 2); | |
319 | h->loss_count = 1; | |
320 | } | |
321 | ||
2013c7e3 | 322 | } else { /* gap between S1 and S2 */ |
8a9c7e92 GR |
323 | h->loss_start = tfrc_rx_hist_index(h, 1); |
324 | h->loss_count = 2; | |
325 | } | |
326 | } | |
327 | ||
328 | /** | |
88e97a93 GR |
329 | * tfrc_rx_congestion_event - Loss detection and further processing |
330 | * @h: The non-empty RX history object | |
331 | * @lh: Loss Intervals database to update | |
332 | * @skb: Currently received packet | |
333 | * @ndp: The NDP count belonging to @skb | |
334 | * @first_li: Caller-dependent computation of first loss interval in @lh | |
335 | * @sk: Used by @calc_first_li (see tfrc_lh_interval_add) | |
8a9c7e92 GR |
336 | * Chooses action according to pending loss, updates LI database when a new |
337 | * loss was detected, and does required post-processing. Returns 1 when caller | |
338 | * should send feedback, 0 otherwise. | |
b552c623 GR |
339 | * Since it also takes care of reordering during loss detection and updates the |
340 | * records accordingly, the caller should not perform any more RX history | |
341 | * operations when loss_count is greater than 0 after calling this function. | |
8a9c7e92 | 342 | */ |
88e97a93 GR |
343 | bool tfrc_rx_congestion_event(struct tfrc_rx_hist *h, |
344 | struct tfrc_loss_hist *lh, | |
345 | struct sk_buff *skb, const u64 ndp, | |
346 | u32 (*first_li)(struct sock *), struct sock *sk) | |
8a9c7e92 | 347 | { |
88e97a93 | 348 | bool new_event = false; |
8a9c7e92 | 349 | |
d20ed95f GR |
350 | if (tfrc_rx_hist_duplicate(h, skb)) |
351 | return 0; | |
352 | ||
b552c623 GR |
353 | if (h->loss_count == 0) { |
354 | __do_track_loss(h, skb, ndp); | |
2b81143a | 355 | tfrc_rx_hist_sample_rtt(h, skb); |
88e97a93 | 356 | tfrc_rx_hist_add_packet(h, skb, ndp); |
b552c623 | 357 | } else if (h->loss_count == 1) { |
8a9c7e92 GR |
358 | __one_after_loss(h, skb, ndp); |
359 | } else if (h->loss_count != 2) { | |
360 | DCCP_BUG("invalid loss_count %d", h->loss_count); | |
361 | } else if (__two_after_loss(h, skb, ndp)) { | |
362 | /* | |
363 | * Update Loss Interval database and recycle RX records | |
364 | */ | |
88e97a93 | 365 | new_event = tfrc_lh_interval_add(lh, h, first_li, sk); |
8a9c7e92 GR |
366 | __three_after_loss(h); |
367 | } | |
3ca7aea0 | 368 | |
34a081be GR |
369 | /* |
370 | * Update moving-average of `s' and the sum of received payload bytes. | |
371 | */ | |
372 | if (dccp_data_packet(skb)) { | |
373 | const u32 payload = skb->len - dccp_hdr(skb)->dccph_doff * 4; | |
374 | ||
375 | h->packet_size = tfrc_ewma(h->packet_size, payload, 9); | |
376 | h->bytes_recvd += payload; | |
377 | } | |
378 | ||
3ca7aea0 | 379 | /* RFC 3448, 6.1: update I_0, whose growth implies p <= p_prev */ |
88e97a93 | 380 | if (!new_event) |
3ca7aea0 GR |
381 | tfrc_lh_update_i_mean(lh, skb); |
382 | ||
88e97a93 | 383 | return new_event; |
8a9c7e92 | 384 | } |
88e97a93 | 385 | EXPORT_SYMBOL_GPL(tfrc_rx_congestion_event); |
8a9c7e92 | 386 | |
68c89ee5 GR |
387 | /* Compute the sending rate X_recv measured between feedback intervals */ |
388 | u32 tfrc_rx_hist_x_recv(struct tfrc_rx_hist *h, const u32 last_x_recv) | |
389 | { | |
390 | u64 bytes = h->bytes_recvd, last_rtt = h->rtt_estimate; | |
391 | s64 delta = ktime_to_us(net_timedelta(h->bytes_start)); | |
392 | ||
393 | WARN_ON(delta <= 0); | |
394 | /* | |
395 | * Ensure that the sampling interval for X_recv is at least one RTT, | |
396 | * by extending the sampling interval backwards in time, over the last | |
397 | * R_(m-1) seconds, as per rfc3448bis-06, 6.2. | |
398 | * To reduce noise (e.g. when the RTT changes often), this is only | |
399 | * done when delta is smaller than RTT/2. | |
400 | */ | |
401 | if (last_x_recv > 0 && delta < last_rtt/2) { | |
402 | tfrc_pr_debug("delta < RTT ==> %ld us < %u us\n", | |
403 | (long)delta, (unsigned)last_rtt); | |
404 | ||
405 | delta = (bytes ? delta : 0) + last_rtt; | |
406 | bytes += div_u64((u64)last_x_recv * last_rtt, USEC_PER_SEC); | |
407 | } | |
408 | ||
409 | if (unlikely(bytes == 0)) { | |
410 | DCCP_WARN("X_recv == 0, using old value of %u\n", last_x_recv); | |
411 | return last_x_recv; | |
412 | } | |
413 | return scaled_div32(bytes, delta); | |
414 | } | |
415 | EXPORT_SYMBOL_GPL(tfrc_rx_hist_x_recv); | |
416 | ||
b84a2189 | 417 | void tfrc_rx_hist_purge(struct tfrc_rx_hist *h) |
072ab6c6 | 418 | { |
b84a2189 ACM |
419 | int i; |
420 | ||
421 | for (i = 0; i <= TFRC_NDUPACK; ++i) | |
422 | if (h->ring[i] != NULL) { | |
423 | kmem_cache_free(tfrc_rx_hist_slab, h->ring[i]); | |
424 | h->ring[i] = NULL; | |
072ab6c6 | 425 | } |
072ab6c6 | 426 | } |
b84a2189 | 427 | EXPORT_SYMBOL_GPL(tfrc_rx_hist_purge); |
072ab6c6 | 428 | |
24b8d343 GR |
429 | static int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h) |
430 | { | |
431 | int i; | |
432 | ||
433 | memset(h, 0, sizeof(*h)); | |
434 | ||
435 | for (i = 0; i <= TFRC_NDUPACK; i++) { | |
436 | h->ring[i] = kmem_cache_alloc(tfrc_rx_hist_slab, GFP_ATOMIC); | |
437 | if (h->ring[i] == NULL) { | |
438 | tfrc_rx_hist_purge(h); | |
439 | return -ENOBUFS; | |
440 | } | |
441 | } | |
442 | return 0; | |
443 | } | |
444 | ||
445 | int tfrc_rx_hist_init(struct tfrc_rx_hist *h, struct sock *sk) | |
446 | { | |
447 | if (tfrc_rx_hist_alloc(h)) | |
448 | return -ENOBUFS; | |
449 | /* | |
450 | * Initialise first entry with GSR to start loss detection as early as | |
451 | * possible. Code using this must not use any other fields. The entry | |
452 | * will be overwritten once the CCID updates its received packets. | |
453 | */ | |
454 | tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno = dccp_sk(sk)->dccps_gsr; | |
455 | return 0; | |
456 | } | |
457 | EXPORT_SYMBOL_GPL(tfrc_rx_hist_init); | |
458 | ||
b84a2189 ACM |
459 | /** |
460 | * tfrc_rx_hist_sample_rtt - Sample RTT from timestamp / CCVal | |
22338f09 GR |
461 | * Based on ideas presented in RFC 4342, 8.1. This function expects that no loss |
462 | * is pending and uses the following history entries (via rtt_sample_prev): | |
463 | * - h->ring[0] contains the most recent history entry prior to @skb; | |
464 | * - h->ring[1] is an unused `dummy' entry when the current difference is 0; | |
b84a2189 | 465 | */ |
2b81143a | 466 | void tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb) |
b84a2189 | 467 | { |
22338f09 GR |
468 | struct tfrc_rx_hist_entry *last = h->ring[0]; |
469 | u32 sample, delta_v; | |
2b81143a GR |
470 | |
471 | /* | |
472 | * When not to sample: | |
473 | * - on non-data packets | |
474 | * (RFC 4342, 8.1: CCVal only fully defined for data packets); | |
475 | * - when no data packets have been received yet | |
476 | * (FIXME: using sampled packet size as indicator here); | |
477 | * - as long as there are gaps in the sequence space (pending loss). | |
478 | */ | |
479 | if (!dccp_data_packet(skb) || h->packet_size == 0 || | |
480 | tfrc_rx_hist_loss_pending(h)) | |
481 | return; | |
482 | ||
22338f09 | 483 | h->rtt_sample_prev = 0; /* reset previous candidate */ |
8c60f3fa | 484 | |
22338f09 GR |
485 | delta_v = SUB16(dccp_hdr(skb)->dccph_ccval, last->tfrchrx_ccval); |
486 | if (delta_v == 0) { /* less than RTT/4 difference */ | |
487 | h->rtt_sample_prev = 1; | |
488 | return; | |
b84a2189 | 489 | } |
22338f09 | 490 | sample = dccp_sane_rtt(ktime_to_us(net_timedelta(last->tfrchrx_tstamp))); |
b84a2189 | 491 | |
22338f09 GR |
492 | if (delta_v <= 4) /* between RTT/4 and RTT */ |
493 | sample *= 4 / delta_v; | |
494 | else if (!(sample < h->rtt_estimate && sample > h->rtt_estimate/2)) | |
495 | /* | |
496 | * Optimisation: CCVal difference is greater than 1 RTT, yet the | |
497 | * sample is less than the local RTT estimate; which means that | |
498 | * the RTT estimate is too high. | |
499 | * To avoid noise, it is not done if the sample is below RTT/2. | |
500 | */ | |
501 | return; | |
b84a2189 | 502 | |
22338f09 GR |
503 | /* Use a lower weight than usual to increase responsiveness */ |
504 | h->rtt_estimate = tfrc_ewma(h->rtt_estimate, sample, 5); | |
b84a2189 ACM |
505 | } |
506 | EXPORT_SYMBOL_GPL(tfrc_rx_hist_sample_rtt); |