1 // SPDX-License-Identifier: GPL-2.0-or-later
4  *  Copyright (c) 2005-7 The University of Waikato, Hamilton, New Zealand.
10  *  or e-mail Ian McDonald - ian.mcdonald@jandi.co.nz
14  *  Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
17  *  and to make it work as a loadable module in the DCCP stack written by
38 	return tfrc_tx_hist_slab == NULL ? -ENOBUFS : 0;  in tfrc_tx_packet_history_init()
54 		return -ENOBUFS;  in tfrc_tx_hist_add()
55 	entry->seqno = seqno;  in tfrc_tx_hist_add()
56 	entry->stamp = ktime_get_real();  in tfrc_tx_hist_add()
57 	entry->next  = *headp;  in tfrc_tx_hist_add()
67 		struct tfrc_tx_hist_entry *next = head->next;  in tfrc_tx_hist_purge()
86 	return tfrc_rx_hist_slab == NULL ? -ENOBUFS : 0;  in tfrc_rx_packet_history_init()
103 	entry->tfrchrx_seqno = DCCP_SKB_CB(skb)->dccpd_seq;  in tfrc_rx_hist_entry_from_skb()
104 	entry->tfrchrx_ccval = dh->dccph_ccval;  in tfrc_rx_hist_entry_from_skb()
105 	entry->tfrchrx_type  = dh->dccph_type;  in tfrc_rx_hist_entry_from_skb()
106 	entry->tfrchrx_ndp   = ndp;  in tfrc_rx_hist_entry_from_skb()
107 	entry->tfrchrx_tstamp = ktime_get_real();  in tfrc_rx_hist_entry_from_skb()
119 /* has the packet contained in skb been seen before? */
122 	const u64 seq = DCCP_SKB_CB(skb)->dccpd_seq;  in tfrc_rx_hist_duplicate()
125 	if (dccp_delta_seqno(tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno, seq) <= 0)  in tfrc_rx_hist_duplicate()
128 	for (i = 1; i <= h->loss_count; i++)  in tfrc_rx_hist_duplicate()
129 		if (tfrc_rx_hist_entry(h, i)->tfrchrx_seqno == seq)  in tfrc_rx_hist_duplicate()
140 	swap(h->ring[idx_a], h->ring[idx_b]);  in tfrc_rx_hist_swap()
146  * In the descriptions, `Si' refers to the sequence number of entry number i,
154 	u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno,  in __do_track_loss()
155 	    s1 = DCCP_SKB_CB(skb)->dccpd_seq;  in __do_track_loss()
157 	if (!dccp_loss_free(s0, s1, n1)) {	/* gap between S0 and S1 */  in __do_track_loss()
158 		h->loss_count = 1;  in __do_track_loss()
165 	u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno,  in __one_after_loss()
166 	    s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno,  in __one_after_loss()
167 	    s2 = DCCP_SKB_CB(skb)->dccpd_seq;  in __one_after_loss()
170 		h->loss_count = 2;  in __one_after_loss()
178 		u64 n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp;  in __one_after_loss()
182 			h->loss_count = 0;  in __one_after_loss()
183 			h->loss_start = tfrc_rx_hist_index(h, 1);  in __one_after_loss()
185 			/* gap between S2 and S1: just update loss_prev */  in __one_after_loss()
188 	} else {	/* gap between S0 and S2 */  in __one_after_loss()
190 		 * Reorder history to insert S2 between S0 and S1  in __one_after_loss()
193 		h->loss_start = tfrc_rx_hist_index(h, 3);  in __one_after_loss()
195 		h->loss_count = 2;  in __one_after_loss()
202 	u64 s0 = tfrc_rx_hist_loss_prev(h)->tfrchrx_seqno,  in __two_after_loss()
203 	    s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno,  in __two_after_loss()
204 	    s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno,  in __two_after_loss()
205 	    s3 = DCCP_SKB_CB(skb)->dccpd_seq;  in __two_after_loss()
208 		h->loss_count = 3;  in __two_after_loss()
217 		 * Reorder history to insert S3 between S1 and S2  in __two_after_loss()
221 		h->loss_count = 3;  in __two_after_loss()
228 		u64 n1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_ndp;  in __two_after_loss()
231 			/* hole between S0 and S1 filled by S3 */  in __two_after_loss()
232 			u64 n2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_ndp;  in __two_after_loss()
236 				h->loss_start = tfrc_rx_hist_index(h, 2);  in __two_after_loss()
237 				h->loss_count = 0;  in __two_after_loss()
239 				/* gap remains between S1 and S2 */  in __two_after_loss()
240 				h->loss_start = tfrc_rx_hist_index(h, 1);  in __two_after_loss()
241 				h->loss_count = 1;  in __two_after_loss()
244 		} else /* gap exists between S3 and S1, loss_count stays at 2 */  in __two_after_loss()
251 	 * The remaining case:  S0  <  S3  <  S1  <  S2;  gap between S0 and S3  in __two_after_loss()
252 	 * Reorder history to insert S3 between S0 and S1.  in __two_after_loss()
255 	h->loss_start = tfrc_rx_hist_index(h, 3);  in __two_after_loss()
257 	h->loss_count = 3;  in __two_after_loss()
266 	 * At this stage we know already that there is a gap between S0 and S1  in __three_after_loss()
269 	 * check for other possible gaps between S1/S2 and between S2/S3.  in __three_after_loss()
271 	u64 s1 = tfrc_rx_hist_entry(h, 1)->tfrchrx_seqno,  in __three_after_loss()
272 	    s2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_seqno,  in __three_after_loss()
273 	    s3 = tfrc_rx_hist_entry(h, 3)->tfrchrx_seqno;  in __three_after_loss()
274 	u64 n2 = tfrc_rx_hist_entry(h, 2)->tfrchrx_ndp,  in __three_after_loss()
275 	    n3 = tfrc_rx_hist_entry(h, 3)->tfrchrx_ndp;  in __three_after_loss()
280 			/* no gap between S2 and S3: entire hole is filled */  in __three_after_loss()
281 			h->loss_start = tfrc_rx_hist_index(h, 3);  in __three_after_loss()
282 			h->loss_count = 0;  in __three_after_loss()
284 			/* gap between S2 and S3 */  in __three_after_loss()
285 			h->loss_start = tfrc_rx_hist_index(h, 2);  in __three_after_loss()
286 			h->loss_count = 1;  in __three_after_loss()
289 	} else {	/* gap between S1 and S2 */  in __three_after_loss()
290 		h->loss_start = tfrc_rx_hist_index(h, 1);  in __three_after_loss()
291 		h->loss_count = 2;  in __three_after_loss()
296  *  tfrc_rx_handle_loss  -  Loss detection and further processing
297  *  @h:		    The non-empty RX history object
301  *  @calc_first_li: Caller-dependent computation of first loss interval in @lh
305  *  loss was detected, and does required post-processing. Returns 1 when caller
318 	if (h->loss_count == 0) {  in tfrc_rx_handle_loss()
320 	} else if (h->loss_count == 1) {  in tfrc_rx_handle_loss()
322 	} else if (h->loss_count != 2) {  in tfrc_rx_handle_loss()
323 		DCCP_BUG("invalid loss_count %d", h->loss_count);  in tfrc_rx_handle_loss()
339 		h->ring[i] = kmem_cache_alloc(tfrc_rx_hist_slab, GFP_ATOMIC);  in tfrc_rx_hist_alloc()
340 		if (h->ring[i] == NULL)  in tfrc_rx_hist_alloc()
344 	h->loss_count = h->loss_start = 0;  in tfrc_rx_hist_alloc()
348 	while (i-- != 0) {  in tfrc_rx_hist_alloc()
349 		kmem_cache_free(tfrc_rx_hist_slab, h->ring[i]);  in tfrc_rx_hist_alloc()
350 		h->ring[i] = NULL;  in tfrc_rx_hist_alloc()
352 	return -ENOBUFS;  in tfrc_rx_hist_alloc()
360 		if (h->ring[i] != NULL) {  in tfrc_rx_hist_purge()
361 			kmem_cache_free(tfrc_rx_hist_slab, h->ring[i]);  in tfrc_rx_hist_purge()
362 			h->ring[i] = NULL;  in tfrc_rx_hist_purge()
367  * tfrc_rx_hist_rtt_last_s - reference entry to compute RTT samples against
368  * @h:	The non-empty RX history object
373 	return h->ring[0];  in tfrc_rx_hist_rtt_last_s()
377  * tfrc_rx_hist_rtt_prev_s - previously suitable (wrt rtt_last_s) RTT-sampling entry
378  * @h:	The non-empty RX history object
383 	return h->ring[h->rtt_sample_prev];  in tfrc_rx_hist_rtt_prev_s()
387  * tfrc_rx_hist_sample_rtt  -  Sample RTT from timestamp / CCVal
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.
397 	    delta_v = SUB16(dccp_hdr(skb)->dccph_ccval,  in tfrc_rx_hist_sample_rtt()
398 			    tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval);  in tfrc_rx_hist_sample_rtt()
401 		if (h->rtt_sample_prev == 2) {	/* previous candidate stored */  in tfrc_rx_hist_sample_rtt()
402 			sample = SUB16(tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_ccval,  in tfrc_rx_hist_sample_rtt()
403 				       tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval);  in tfrc_rx_hist_sample_rtt()
406 				         ktime_us_delta(tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_tstamp,  in tfrc_rx_hist_sample_rtt()
407 							tfrc_rx_hist_rtt_last_s(h)->tfrchrx_tstamp);  in tfrc_rx_hist_sample_rtt()
409 				 * FIXME: This condition is in principle not  in tfrc_rx_hist_sample_rtt()
411 				 * two-way data traffic. I have tried to trace  in tfrc_rx_hist_sample_rtt()
416 					 tfrc_rx_hist_rtt_prev_s(h)->tfrchrx_ccval,  in tfrc_rx_hist_sample_rtt()
417 					 tfrc_rx_hist_rtt_last_s(h)->tfrchrx_ccval);  in tfrc_rx_hist_sample_rtt()
419 			h->rtt_sample_prev = 1;  in tfrc_rx_hist_sample_rtt()
424 		sample = ktime_to_us(net_timedelta(tfrc_rx_hist_rtt_last_s(h)->tfrchrx_tstamp));  in tfrc_rx_hist_sample_rtt()
426 		h->rtt_sample_prev = 2;  in tfrc_rx_hist_sample_rtt()
435 	h->rtt_sample_prev = 0;	       /* use current entry as next reference */  in tfrc_rx_hist_sample_rtt()