Line data Source code
1 : #ifndef HEADER_fd_src_waltz_quic_fd_quic_pkt_meta_h
2 : #define HEADER_fd_src_waltz_quic_fd_quic_pkt_meta_h
3 :
4 : #include "fd_quic_common.h"
5 :
6 : typedef struct fd_quic_pkt_meta fd_quic_pkt_meta_t;
7 : typedef struct fd_quic_pkt_meta_list fd_quic_pkt_meta_list_t;
8 : typedef struct fd_quic_pkt_meta_tracker fd_quic_pkt_meta_tracker_t;
9 :
10 : /* fd_quic_pkt_meta_key used as key for tracking sent frames
11 : *
12 : * pkt_num: packet number that carried this data
13 : * type: type of data for retx (~frame type)
14 : * stream_id: if stream type, the stream id
15 : */
16 :
17 : union fd_quic_pkt_meta_key {
18 : struct {
19 : /* which frame type is recorded:
20 : FD_QUIC_PKT_META_TYPE_HS_DATA handshake data
21 : FD_QUIC_PKT_META_TYPE_STREAM stream data
22 : FD_QUIC_PKT_META_TYPE_HS_DONE handshake-done frame
23 : FD_QUIC_PKT_META_TYPE_MAX_DATA max_data frame
24 : FD_QUIC_PKT_META_TYPE_MAX_STREAMS_UNIDIR max_streams frame (unidir)
25 : FD_QUIC_PKT_META_TYPE_CLOSE close frame
26 : FD_QUIC_PKT_META_TYPE_PING set to send a PING frame
27 : FD_QUIC_PKT_META_TYPE_DATAGRAM DATAGRAM frame, never retransmitted (RFC 9221 Section 5.2)
28 : */
29 49479 : # define FD_QUIC_PKT_META_TYPE_HS_DATA (0)
30 15265352 : # define FD_QUIC_PKT_META_TYPE_STREAM (1)
31 12132 : # define FD_QUIC_PKT_META_TYPE_HS_DONE (2)
32 0 : # define FD_QUIC_PKT_META_TYPE_MAX_DATA (3)
33 0 : # define FD_QUIC_PKT_META_TYPE_MAX_STREAMS_UNIDIR (4)
34 12027 : # define FD_QUIC_PKT_META_TYPE_CLOSE (5)
35 12303 : # define FD_QUIC_PKT_META_TYPE_PING (6)
36 63 : # define FD_QUIC_PKT_META_TYPE_DATAGRAM (7)
37 : uchar type: 4;
38 :
39 : ulong pkt_num: 60;
40 : #define FD_QUIC_PKT_META_SET_TYPE(PKT_META_PTR, TYPE) \
41 7684358 : (PKT_META_PTR)->key.type = (uchar)((TYPE)&0x0f)
42 :
43 8654363 : #define FD_QUIC_PKT_META_PKT_NUM_MASK ( (1UL<<60) - 1 )
44 : #define FD_QUIC_PKT_META_SET_PKT_NUM(PKT_META_PTR, PKT_NUM) \
45 7818467 : (PKT_META_PTR)->key.pkt_num = (PKT_NUM)&FD_QUIC_PKT_META_PKT_NUM_MASK
46 :
47 : ulong stream_id;
48 : };
49 : ulong b[2];
50 : };
51 : typedef union fd_quic_pkt_meta_key fd_quic_pkt_meta_key_t;
52 : FD_STATIC_ASSERT( sizeof(fd_quic_pkt_meta_key_t) == 16, fd_quic_pkt_meta_key_t );
53 :
54 : union fd_quic_pkt_meta_value {
55 : ulong scalar;
56 : fd_quic_range_t range;
57 : };
58 : typedef union fd_quic_pkt_meta_value fd_quic_pkt_meta_value_t;
59 :
60 :
61 : /* fd_quic_pkt_meta
62 :
63 : tracks the metadata of data sent to the peer
64 : used when acks arrive to determine what is being acked specifically */
65 : struct fd_quic_pkt_meta {
66 : /* stores metadata about what was sent in the identified packet */
67 : fd_quic_pkt_meta_key_t key;
68 : fd_quic_pkt_meta_value_t val;
69 : uchar enc_level: 2;
70 : uchar pn_space; /* packet number space (derived from enc_level) */
71 : long tx_time; /* transmit time */
72 : long expiry; /* time pkt_meta expires... this is the time the
73 : ack is expected by */
74 :
75 : /* treap fields */
76 : ulong parent;
77 : ulong left;
78 : ulong right;
79 : ulong prio;
80 : ulong next;
81 : ulong prev;
82 : };
83 : typedef struct fd_quic_pkt_meta fd_quic_pkt_meta_t;
84 :
85 : #define POOL_NAME fd_quic_pkt_meta_pool
86 660 : #define POOL_T fd_quic_pkt_meta_t
87 : #include "../../util/tmpl/fd_pool.c"
88 :
89 : /* if <pkt_nums,type> are diff, returns sign of difference
90 : *
91 : * else, returns sign of difference in stream_id */
92 : static inline int
93 : fd_quic_pkt_meta_cmp( const fd_quic_pkt_meta_key_t q,
94 15688320 : const fd_quic_pkt_meta_t * e ) {
95 : /* branchless implementation of:
96 : diff = q.b[0] - e->key.b[0]
97 : if( diff )
98 : return diff
99 : return q.stream_id - e->key.stream_id */
100 15688320 : ulong q_b = q.b[0];
101 15688320 : ulong e_b = e->key.b[0];
102 15688320 : ulong q_s = q.stream_id;
103 15688320 : ulong e_s = e->key.stream_id;
104 :
105 15688320 : int pkt_num_type_cmp = -2*(q_b < e_b) + ((q_b > e_b)<<1);
106 15688320 : int stream_id_cmp = -1*(q_s < e_s) + (q_s > e_s);
107 15688320 : return pkt_num_type_cmp + stream_id_cmp;
108 15688320 : }
109 :
110 : static inline int
111 : fd_quic_pkt_meta_lt( const fd_quic_pkt_meta_t * e1,
112 7526414 : const fd_quic_pkt_meta_t * e2 ) {
113 7526414 : ulong e1_b0 = e1->key.b[0];
114 7526414 : ulong e2_b0 = e2->key.b[0];
115 7526414 : return e1_b0 < e2_b0 || (e1_b0 == e2_b0 && e1->key.stream_id < e2->key.stream_id);
116 7526414 : }
117 :
118 : #define TREAP_NAME fd_quic_pkt_meta_treap
119 : #define TREAP_T fd_quic_pkt_meta_t
120 : #define TREAP_QUERY_T fd_quic_pkt_meta_key_t
121 15688311 : #define TREAP_CMP(q,e) fd_quic_pkt_meta_cmp( q, e )
122 7526414 : #define TREAP_LT(e0,e1) fd_quic_pkt_meta_lt( e0, e1 )
123 : #define TREAP_OPTIMIZE_ITERATION 1
124 : #include "../../util/tmpl/fd_treap.c"
125 :
126 : /* begin aliasing to abstract data structure */
127 : typedef fd_quic_pkt_meta_treap_t fd_quic_pkt_meta_ds_t;
128 : typedef fd_quic_pkt_meta_treap_fwd_iter_t fd_quic_pkt_meta_ds_fwd_iter_t;
129 : typedef fd_quic_pkt_meta_treap_rev_iter_t fd_quic_pkt_meta_ds_rev_iter_t;
130 :
131 : /* fd_quic_pkt_meta_ds_fwd_iter_init is equivalent of ds.begin()
132 : @arguments:
133 : - ds: pointer to the ds
134 : - pool: pointer to the backing pool
135 : @returns:
136 : - beginning iterator */
137 : static inline fd_quic_pkt_meta_ds_fwd_iter_t
138 : fd_quic_pkt_meta_ds_fwd_iter_init( fd_quic_pkt_meta_ds_t * ds,
139 31422113 : fd_quic_pkt_meta_t * pool ) {
140 31422113 : return fd_quic_pkt_meta_treap_fwd_iter_init( ds, pool );
141 31422113 : }
142 :
143 : /* fd_quic_pkt_meta_ds_fwd_iter_ele returns pkt_meta* from iter
144 : @arguments:
145 : - iter: iterator
146 : - pool: pointer to the backing pool
147 : @returns:
148 : - pointer to pkt_meta */
149 : static inline fd_quic_pkt_meta_t *
150 : fd_quic_pkt_meta_ds_fwd_iter_ele( fd_quic_pkt_meta_ds_fwd_iter_t iter,
151 22977331 : fd_quic_pkt_meta_t * pool ) {
152 22977331 : return fd_quic_pkt_meta_treap_fwd_iter_ele( iter, pool );
153 22977331 : }
154 :
155 : /* fd_quic_pkt_meta_ds_fwd_iter_next is equivalent of iter++
156 : @arguments:
157 : - iter: iterator
158 : - pool: pointer to the backing pool
159 : @returns:
160 : - next iterator */
161 : static inline fd_quic_pkt_meta_ds_fwd_iter_t
162 : fd_quic_pkt_meta_ds_fwd_iter_next( fd_quic_pkt_meta_ds_fwd_iter_t iter,
163 15351875 : fd_quic_pkt_meta_t * pool ) {
164 15351875 : return fd_quic_pkt_meta_treap_fwd_iter_next( iter, pool );
165 15351875 : }
166 :
167 : /* fd_quic_pkt_meta_ds_fwd_iter_done returns boolean
168 : @arguments
169 : - iter: iterator
170 : @returns
171 : - non-zero if iterator marks end, 0 otherwise */
172 : static inline int
173 47312845 : fd_quic_pkt_meta_ds_fwd_iter_done( fd_quic_pkt_meta_ds_fwd_iter_t iter ) {
174 47312845 : return fd_quic_pkt_meta_treap_fwd_iter_done( iter );
175 47312845 : }
176 :
177 : /* fd_quic_pkt_meta_ds_rev_iter_init is equivalent of ds.end()
178 : @arguments:
179 : - ds: pointer to the ds
180 : - pool: pointer to the backing pool
181 : @returns:
182 : - beginning iterator */
183 : static inline fd_quic_pkt_meta_ds_rev_iter_t
184 : fd_quic_pkt_meta_ds_rev_iter_init( fd_quic_pkt_meta_ds_t * ds,
185 0 : fd_quic_pkt_meta_t * pool ) {
186 0 : return fd_quic_pkt_meta_treap_rev_iter_init( ds, pool );
187 0 : }
188 :
189 : /* fd_quic_pkt_meta_ds_rev_iter_ele returns pkt_meta* from iter
190 : @arguments:
191 : - iter: iterator
192 : - pool: pointer to the backing pool
193 : @returns:
194 : - pointer to pkt_meta */
195 : static inline fd_quic_pkt_meta_t *
196 : fd_quic_pkt_meta_ds_rev_iter_ele( fd_quic_pkt_meta_ds_rev_iter_t iter,
197 362877 : fd_quic_pkt_meta_t * pool ) {
198 362877 : return fd_quic_pkt_meta_treap_rev_iter_ele( iter, pool );
199 362877 : }
200 :
201 : /* fd_quic_pkt_meta_ds_rev_iter_next is equivalent of iter--
202 : @arguments:
203 : - iter: iterator
204 : - pool: pointer to the backing pool
205 : @returns:
206 : - next iterator */
207 : static inline fd_quic_pkt_meta_ds_fwd_iter_t
208 : fd_quic_pkt_meta_ds_rev_iter_next( fd_quic_pkt_meta_ds_rev_iter_t iter,
209 362877 : fd_quic_pkt_meta_t * pool ) {
210 362877 : return fd_quic_pkt_meta_treap_rev_iter_next( iter, pool );
211 362877 : }
212 :
213 : /* fd_quic_pkt_meta_ds_rev_iter_done returns boolean
214 : @arguments
215 : - iter: iterator
216 : @returns
217 : - non-zero if iterator marks end, 0 otherwise */
218 : static inline int
219 489903 : fd_quic_pkt_meta_ds_rev_iter_done( fd_quic_pkt_meta_ds_rev_iter_t iter ) {
220 489903 : return fd_quic_pkt_meta_treap_rev_iter_done( iter );
221 489903 : }
222 :
223 : /* fd_quic_pkt_meta_ds_idx_ge returns iterator pointing to first pkt_meta
224 : whose packet number is >= pkt_number
225 : @arguments
226 : - ds: pointer to the ds
227 : - pkt_number: pkt_number to search for
228 : - pool: pointer to the backing pool
229 : @returns
230 : - iterator to first pkt_meta with pkt number >= pkt_number */
231 : static inline fd_quic_pkt_meta_ds_fwd_iter_t
232 : fd_quic_pkt_meta_ds_idx_ge( fd_quic_pkt_meta_ds_t * ds,
233 : ulong pkt_number,
234 290922 : fd_quic_pkt_meta_t * pool ) {
235 290922 : return fd_quic_pkt_meta_treap_idx_ge( ds,
236 290922 : (fd_quic_pkt_meta_key_t){
237 290922 : .pkt_num = pkt_number & FD_QUIC_PKT_META_PKT_NUM_MASK,
238 290922 : .type = 0,
239 290922 : .stream_id = 0},
240 290922 : pool );
241 290922 : }
242 :
243 : /* fd_quic_pkt_meta_ds_idx_le returns iterator pointing to first pkt_meta
244 : whose packet number is <= pkt_number. NOT just simple alias of treap_idx_le
245 : @arguments
246 : - ds: pointer to the ds
247 : - pkt_number: pkt_number to search for
248 : - pool: pointer to the backing pool
249 : @returns
250 : - iterator to last pkt_meta with pkt number <= pkt_number */
251 : fd_quic_pkt_meta_ds_fwd_iter_t
252 : fd_quic_pkt_meta_ds_idx_le( fd_quic_pkt_meta_ds_t * ds,
253 : fd_quic_pkt_meta_t * pool,
254 : ulong pkt_number );
255 :
256 : /* fd_quic_pkt_meta_ds_ele_cnt returns count of elements in ds */
257 : static inline ulong
258 97689 : fd_quic_pkt_meta_ds_ele_cnt( fd_quic_pkt_meta_ds_t * ds ) {
259 97689 : return fd_quic_pkt_meta_treap_ele_cnt( ds );
260 97689 : }
261 :
262 : /* end aliasing to abstract data structure */
263 :
264 : struct fd_quic_pkt_meta_tracker {
265 : fd_quic_pkt_meta_ds_t sent_pkt_metas[4];
266 : fd_quic_pkt_meta_t * pool;
267 : };
268 : typedef struct fd_quic_pkt_meta_tracker fd_quic_pkt_meta_tracker_t;
269 :
270 : /* fd_quic_pkt_meta_ds_init_pool does any data structure-particular setup
271 : on the entire pool at once. Useful for e.g. treap randomness
272 : @arguments:
273 : - pool: pointer pkt_meta pool
274 : - total_meta_cnt: total pool size */
275 : void
276 : fd_quic_pkt_meta_ds_init_pool( fd_quic_pkt_meta_t * pool,
277 : ulong total_meta_cnt );
278 :
279 : /* fd_quic_pkt_meta_tracker_init initializes the metadata tracker for each enc level
280 : @arguments:
281 : - tracker: pointer to the tracker
282 : - total_meta_cnt: total number of max pkt_meta entries in this tracker
283 : (shared across all encoding levels)
284 : - pool: pointer to the backing pool
285 : @returns:
286 : - pointer to tracker if successful, NULL otherwise */
287 : void *
288 : fd_quic_pkt_meta_tracker_init( fd_quic_pkt_meta_tracker_t * tracker,
289 : ulong total_meta_cnt,
290 : fd_quic_pkt_meta_t * pool );
291 :
292 : /* fd_quic_pkt_meta_insert inserts a pkt_meta into the ds
293 : @arguments:
294 : - ds: pointer to the ds
295 : - pkt_meta: pointer to the pkt_meta to insert. This pkt_meta
296 : should have been acquired from the pool
297 : - pool: pointer to the backing pool */
298 : void
299 : fd_quic_pkt_meta_insert( fd_quic_pkt_meta_ds_t * ds,
300 : fd_quic_pkt_meta_t * pkt_meta,
301 : fd_quic_pkt_meta_t * pool );
302 :
303 : /*
304 : remove all pkt_meta in the range [pkt_number_lo, pkt_number_hi]
305 : rm from treap and return to pool
306 : */
307 : /* fd_quic_pkt_meta_remove_range removes all pkt_meta in the range
308 : [pkt_number_lo, pkt_number_hi] from the ds and returns them to the pool.
309 : Any part of the range that's missing simply gets skipped
310 : @arguments:
311 : - ds: pointer to the ds
312 : - pool: pointer to the backing pool
313 : - pkt_number_lo: lower bound of the range
314 : - pkt_number_hi: upper bound of the range
315 : @returns:
316 : - number of pkt_meta removed */
317 : ulong
318 : fd_quic_pkt_meta_remove_range( fd_quic_pkt_meta_ds_t * ds,
319 : fd_quic_pkt_meta_t * pool,
320 : ulong pkt_number_lo,
321 : ulong pkt_number_hi );
322 :
323 : /* fd_quic_pkt_meta_remove removes a single pkt_meta from the ds and returns it to the pool.
324 : @arguments:
325 : - ds: pointer to the ds
326 : - pool: pointer to the backing pool
327 : - pkt_meta: pointer to the pkt_meta to remove. Assumed non-null */
328 : void
329 : fd_quic_pkt_meta_remove( fd_quic_pkt_meta_ds_t * ds,
330 : fd_quic_pkt_meta_t * pool,
331 : fd_quic_pkt_meta_t * pkt_meta );
332 :
333 : /* fd_quic_pkt_meta_min returns pointer to pkt_meta with smallest pkt_number in the ds
334 : @arguments:
335 : - ds: pointer to the ds
336 : - pool: pointer to the backing pool
337 : @returns:
338 : - pointer to pkt_meta with smallest pkt_number in the ds */
339 : fd_quic_pkt_meta_t *
340 : fd_quic_pkt_meta_min( fd_quic_pkt_meta_ds_t * ds,
341 : fd_quic_pkt_meta_t * pool );
342 :
343 : /* fd_quic_pkt_meta_ds_clear clears all pkt_meta tracking for a given encryption level
344 : @arguments:
345 : - tracker: pointer to the pkt_meta tracker
346 : - enc_level: encryption level to clear */
347 : void
348 : fd_quic_pkt_meta_ds_clear( fd_quic_pkt_meta_tracker_t * tracker,
349 : uint enc_level );
350 :
351 : FD_PROTOTYPES_END
352 :
353 : #endif // HEADER_fd_src_waltz_quic_fd_quic_pkt_meta_h
|
