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, n: 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 | |