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