1 /* SPDX-License-Identifier: GPL-2.0-or-later */ 2 /* 3 * Packet RX/TX history data structures and routines for TFRC-based protocols. 4 * 5 * Copyright (c) 2007 The University of Aberdeen, Scotland, UK 6 * Copyright (c) 2005-6 The University of Waikato, Hamilton, New Zealand. 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 #ifndef _DCCP_PKT_HIST_ 24 #define _DCCP_PKT_HIST_ 25 26 #include <linux/list.h> 27 #include <linux/slab.h> 28 #include "tfrc.h" 29 30 /** 31 * tfrc_tx_hist_entry - Simple singly-linked TX history list 32 * @next: next oldest entry (LIFO order) 33 * @seqno: sequence number of this entry 34 * @stamp: send time of packet with sequence number @seqno 35 */ 36 struct tfrc_tx_hist_entry { 37 struct tfrc_tx_hist_entry *next; 38 u64 seqno; 39 ktime_t stamp; 40 }; 41 42 static inline struct tfrc_tx_hist_entry * 43 tfrc_tx_hist_find_entry(struct tfrc_tx_hist_entry *head, u64 seqno) 44 { 45 while (head != NULL && head->seqno != seqno) 46 head = head->next; 47 return head; 48 } 49 50 int tfrc_tx_hist_add(struct tfrc_tx_hist_entry **headp, u64 seqno); 51 void tfrc_tx_hist_purge(struct tfrc_tx_hist_entry **headp); 52 53 /* Subtraction a-b modulo-16, respects circular wrap-around */ 54 #define SUB16(a, b) (((a) + 16 - (b)) & 0xF) 55 56 /* Number of packets to wait after a missing packet (RFC 4342, 6.1) */ 57 #define TFRC_NDUPACK 3 58 59 /** 60 * tfrc_rx_hist_entry - Store information about a single received packet 61 * @tfrchrx_seqno: DCCP packet sequence number 62 * @tfrchrx_ccval: window counter value of packet (RFC 4342, 8.1) 63 * @tfrchrx_ndp: the NDP count (if any) of the packet 64 * @tfrchrx_tstamp: actual receive time of packet 65 */ 66 struct tfrc_rx_hist_entry { 67 u64 tfrchrx_seqno:48, 68 tfrchrx_ccval:4, 69 tfrchrx_type:4; 70 u64 tfrchrx_ndp:48; 71 ktime_t tfrchrx_tstamp; 72 }; 73 74 /** 75 * tfrc_rx_hist - RX history structure for TFRC-based protocols 76 * @ring: Packet history for RTT sampling and loss detection 77 * @loss_count: Number of entries in circular history 78 * @loss_start: Movable index (for loss detection) 79 * @rtt_sample_prev: Used during RTT sampling, points to candidate entry 80 */ 81 struct tfrc_rx_hist { 82 struct tfrc_rx_hist_entry *ring[TFRC_NDUPACK + 1]; 83 u8 loss_count:2, 84 loss_start:2; 85 #define rtt_sample_prev loss_start 86 }; 87 88 /** 89 * tfrc_rx_hist_index - index to reach n-th entry after loss_start 90 */ 91 static inline u8 tfrc_rx_hist_index(const struct tfrc_rx_hist *h, const u8 n) 92 { 93 return (h->loss_start + n) & TFRC_NDUPACK; 94 } 95 96 /** 97 * tfrc_rx_hist_last_rcv - entry with highest-received-seqno so far 98 */ 99 static inline struct tfrc_rx_hist_entry * 100 tfrc_rx_hist_last_rcv(const struct tfrc_rx_hist *h) 101 { 102 return h->ring[tfrc_rx_hist_index(h, h->loss_count)]; 103 } 104 105 /** 106 * tfrc_rx_hist_entry - return the n-th history entry after loss_start 107 */ 108 static inline struct tfrc_rx_hist_entry * 109 tfrc_rx_hist_entry(const struct tfrc_rx_hist *h, const u8 n) 110 { 111 return h->ring[tfrc_rx_hist_index(h, n)]; 112 } 113 114 /** 115 * tfrc_rx_hist_loss_prev - entry with highest-received-seqno before loss was detected 116 */ 117 static inline struct tfrc_rx_hist_entry * 118 tfrc_rx_hist_loss_prev(const struct tfrc_rx_hist *h) 119 { 120 return h->ring[h->loss_start]; 121 } 122 123 /* indicate whether previously a packet was detected missing */ 124 static inline bool tfrc_rx_hist_loss_pending(const struct tfrc_rx_hist *h) 125 { 126 return h->loss_count > 0; 127 } 128 129 void tfrc_rx_hist_add_packet(struct tfrc_rx_hist *h, const struct sk_buff *skb, 130 const u64 ndp); 131 132 int tfrc_rx_hist_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb); 133 134 struct tfrc_loss_hist; 135 int tfrc_rx_handle_loss(struct tfrc_rx_hist *h, struct tfrc_loss_hist *lh, 136 struct sk_buff *skb, const u64 ndp, 137 u32 (*first_li)(struct sock *sk), struct sock *sk); 138 u32 tfrc_rx_hist_sample_rtt(struct tfrc_rx_hist *h, const struct sk_buff *skb); 139 int tfrc_rx_hist_alloc(struct tfrc_rx_hist *h); 140 void tfrc_rx_hist_purge(struct tfrc_rx_hist *h); 141 142 #endif /* _DCCP_PKT_HIST_ */ 143