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