1 // SPDX-License-Identifier: GPL-2.0-only
5  *  An implementation of Ack Vectors for the DCCP protocol
22 		av->av_buf_head	= av->av_buf_tail = DCCPAV_MAX_ACKVEC_LEN - 1;  in dccp_ackvec_alloc()
23 		INIT_LIST_HEAD(&av->av_records);  in dccp_ackvec_alloc()
32 	list_for_each_entry_safe(cur, next, &av->av_records, avr_node)  in dccp_ackvec_purge_records()
34 	INIT_LIST_HEAD(&av->av_records);  in dccp_ackvec_purge_records()
46  * dccp_ackvec_update_records  -  Record information about sent Ack Vectors
57 		return -ENOBUFS;  in dccp_ackvec_update_records()
59 	avr->avr_ack_seqno  = seqno;  in dccp_ackvec_update_records()
60 	avr->avr_ack_ptr    = av->av_buf_head;  in dccp_ackvec_update_records()
61 	avr->avr_ack_ackno  = av->av_buf_ackno;  in dccp_ackvec_update_records()
62 	avr->avr_ack_nonce  = nonce_sum;  in dccp_ackvec_update_records()
63 	avr->avr_ack_runlen = dccp_ackvec_runlen(av->av_buf + av->av_buf_head);  in dccp_ackvec_update_records()
66 	 * the simplest way of disambiguating sender-Acks dating from before the  in dccp_ackvec_update_records()
67 	 * overflow from sender-Acks which refer to after the overflow; a simple  in dccp_ackvec_update_records()
70 	if (av->av_overflow)  in dccp_ackvec_update_records()
76 	list_add(&avr->avr_node, &av->av_records);  in dccp_ackvec_update_records()
79 		      (unsigned long long)avr->avr_ack_seqno,  in dccp_ackvec_update_records()
80 		      (unsigned long long)avr->avr_ack_ackno,  in dccp_ackvec_update_records()
81 		      avr->avr_ack_runlen);  in dccp_ackvec_update_records()
95 		if (avr->avr_ack_seqno == ackno)  in dccp_ackvec_lookup()
97 		if (before48(ackno, avr->avr_ack_seqno))  in dccp_ackvec_lookup()
104  * Buffer index and length computation using modulo-buffersize arithmetic.
114 	return __ackvec_idx_add(a, DCCPAV_MAX_ACKVEC_LEN - b);  in __ackvec_idx_sub()
119 	if (unlikely(av->av_overflow))  in dccp_ackvec_buflen()
121 	return __ackvec_idx_sub(av->av_buf_tail, av->av_buf_head);  in dccp_ackvec_buflen()
125  * dccp_ackvec_update_old  -  Update previous state as per RFC 4340, 11.4.1
126  * @av:		non-empty buffer to update
134 	u16 ptr = av->av_buf_head;  in dccp_ackvec_update_old()
141 		u8 runlen = dccp_ackvec_runlen(av->av_buf + ptr);  in dccp_ackvec_update_old()
150 			 *              S     +---+---+---+  in dccp_ackvec_update_old()
152 			 *              O     +---+---+---+  in dccp_ackvec_update_old()
154 			 *              E     +---+---+---+  in dccp_ackvec_update_old()
156 			 *                    +---+---+---+  in dccp_ackvec_update_old()
159 			if (av->av_buf[ptr] == DCCPAV_NOT_RECEIVED)  in dccp_ackvec_update_old()
160 				av->av_buf[ptr] = state;  in dccp_ackvec_update_old()
170 	} while (ptr != av->av_buf_tail);  in dccp_ackvec_update_old()
173 /* Mark @num entries after buf_head as "Not yet received". */
174 static void dccp_ackvec_reserve_seats(struct dccp_ackvec *av, u16 num)  in dccp_ackvec_reserve_seats()  argument
176 	u16 start = __ackvec_idx_add(av->av_buf_head, 1),  in dccp_ackvec_reserve_seats()
177 	    len	  = DCCPAV_MAX_ACKVEC_LEN - start;  in dccp_ackvec_reserve_seats()
179 	/* check for buffer wrap-around */  in dccp_ackvec_reserve_seats()
180 	if (num > len) {  in dccp_ackvec_reserve_seats()
181 		memset(av->av_buf + start, DCCPAV_NOT_RECEIVED, len);  in dccp_ackvec_reserve_seats()
183 		num  -= len;  in dccp_ackvec_reserve_seats()
185 	if (num)  in dccp_ackvec_reserve_seats()
186 		memset(av->av_buf + start, DCCPAV_NOT_RECEIVED, num);  in dccp_ackvec_reserve_seats()
190  * dccp_ackvec_add_new  -  Record one or more new entries in Ack Vector buffer
191  * @av:		 container of buffer to update (can be empty or non-empty)
202 		u32 lost_packets = num_packets - 1;  in dccp_ackvec_add_new()
206 		 * We received 1 packet and have a loss of size "num_packets-1"  in dccp_ackvec_add_new()
207 		 * which we squeeze into num_cells-1 rather than reserving an  in dccp_ackvec_add_new()
211 		 * This is a trade-off: if a few packets out of the burst show  in dccp_ackvec_add_new()
220 			av->av_buf_head = __ackvec_idx_sub(av->av_buf_head, 1);  in dccp_ackvec_add_new()
221 			av->av_buf[av->av_buf_head] = DCCPAV_NOT_RECEIVED | len;  in dccp_ackvec_add_new()
223 			lost_packets -= len;  in dccp_ackvec_add_new()
229 		av->av_overflow = true;  in dccp_ackvec_add_new()
232 	av->av_buf_head = __ackvec_idx_sub(av->av_buf_head, num_packets);  in dccp_ackvec_add_new()
233 	if (av->av_overflow)  in dccp_ackvec_add_new()
234 		av->av_buf_tail = av->av_buf_head;  in dccp_ackvec_add_new()
236 	av->av_buf[av->av_buf_head] = state;  in dccp_ackvec_add_new()
237 	av->av_buf_ackno	    = seqno;  in dccp_ackvec_add_new()
240 		dccp_ackvec_reserve_seats(av, num_packets - 1);  in dccp_ackvec_add_new()
244  * dccp_ackvec_input  -  Register incoming packet in the buffer
250 	u64 seqno = DCCP_SKB_CB(skb)->dccpd_seq;  in dccp_ackvec_input()
255 		av->av_tail_ackno = seqno;  in dccp_ackvec_input()
258 		s64 num_packets = dccp_delta_seqno(av->av_buf_ackno, seqno);  in dccp_ackvec_input()
259 		u8 *current_head = av->av_buf + av->av_buf_head;  in dccp_ackvec_input()
266 			av->av_buf_ackno = seqno;  in dccp_ackvec_input()
277  * dccp_ackvec_clear_state  -  Perform house-keeping / garbage-collection
281  * This routine is called when the peer acknowledges the receipt of Ack Vectors
293 	avr = dccp_ackvec_lookup(&av->av_records, ackno);  in dccp_ackvec_clear_state()
299 	 * that case we may still have records that pre-date tail_ackno.  in dccp_ackvec_clear_state()
301 	delta = dccp_delta_seqno(av->av_tail_ackno, avr->avr_ack_ackno);  in dccp_ackvec_clear_state()
305 	 * Deal with overlapping Ack Vectors: don't subtract more than the  in dccp_ackvec_clear_state()
308 	eff_runlen = delta < avr->avr_ack_runlen ? delta : avr->avr_ack_runlen;  in dccp_ackvec_clear_state()
310 	runlen_now = dccp_ackvec_runlen(av->av_buf + avr->avr_ack_ptr);  in dccp_ackvec_clear_state()
316 	 * backwards (towards higher indices), to its next-oldest neighbour.  in dccp_ackvec_clear_state()
320 		av->av_buf[avr->avr_ack_ptr] -= eff_runlen + 1;  in dccp_ackvec_clear_state()
321 		av->av_buf_tail = __ackvec_idx_add(avr->avr_ack_ptr, 1);  in dccp_ackvec_clear_state()
324 		if (av->av_overflow)  in dccp_ackvec_clear_state()
325 			av->av_overflow = (av->av_buf_head == av->av_buf_tail);  in dccp_ackvec_clear_state()
327 		av->av_buf_tail	= avr->avr_ack_ptr;  in dccp_ackvec_clear_state()
333 		av->av_overflow	= 0;  in dccp_ackvec_clear_state()
340 	av->av_tail_ackno = ADD48(avr->avr_ack_ackno, 1);  in dccp_ackvec_clear_state()
343 	list_for_each_entry_safe_from(avr, next, &av->av_records, avr_node) {  in dccp_ackvec_clear_state()
344 		list_del(&avr->avr_node);  in dccp_ackvec_clear_state()
350  *	Routines to keep track of Ack Vectors received in an skb
357 		return -ENOBUFS;  in dccp_ackvec_parsed_add()
358 	new->vec   = vec;  in dccp_ackvec_parsed_add()
359 	new->len   = len;  in dccp_ackvec_parsed_add()
360 	new->nonce = nonce;  in dccp_ackvec_parsed_add()
362 	list_add_tail(&new->node, head);  in dccp_ackvec_parsed_add()
394 	return -ENOBUFS;  in dccp_ackvec_init()