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 33140875 : # 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 16622273 : (PKT_META_PTR)->key.type = (uchar)((TYPE)&0x0f)
40 :
41 18567255 : #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 16890261 : (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 33973282 : 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 33973282 : ulong q_b = q.b[0];
99 33973282 : ulong e_b = e->key.b[0];
100 33973282 : ulong q_s = q.stream_id;
101 33973282 : ulong e_s = e->key.stream_id;
102 :
103 33973282 : int pkt_num_type_cmp = -2*(q_b < e_b) + ((q_b > e_b)<<1);
104 33973282 : int stream_id_cmp = -1*(q_s < e_s) + (q_s > e_s);
105 33973282 : return pkt_num_type_cmp + stream_id_cmp;
106 33973282 : }
107 :
108 : static inline int
109 : fd_quic_pkt_meta_lt( const fd_quic_pkt_meta_t * e1,
110 16337461 : const fd_quic_pkt_meta_t * e2 ) {
111 16337461 : ulong e1_b0 = e1->key.b[0];
112 16337461 : ulong e2_b0 = e2->key.b[0];
113 16337461 : return e1_b0 < e2_b0 || (e1_b0 == e2_b0 && e1->key.stream_id < e2->key.stream_id);
114 16337461 : }
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 33973273 : #define TREAP_CMP(q,e) fd_quic_pkt_meta_cmp( q, e )
120 16337461 : #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 67853221 : fd_quic_pkt_meta_t * pool ) {
138 67853221 : return fd_quic_pkt_meta_treap_fwd_iter_init( ds, pool );
139 67853221 : }
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 49791912 : fd_quic_pkt_meta_t * pool ) {
150 49791912 : return fd_quic_pkt_meta_treap_fwd_iter_ele( iter, pool );
151 49791912 : }
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 33227428 : fd_quic_pkt_meta_t * pool ) {
162 33227428 : return fd_quic_pkt_meta_treap_fwd_iter_next( iter, pool );
163 33227428 : }
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 102192414 : fd_quic_pkt_meta_ds_fwd_iter_done( fd_quic_pkt_meta_ds_fwd_iter_t iter ) {
172 102192414 : return fd_quic_pkt_meta_treap_fwd_iter_done( iter );
173 102192414 : }
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 783423 : fd_quic_pkt_meta_t * pool ) {
196 783423 : return fd_quic_pkt_meta_treap_rev_iter_ele( iter, pool );
197 783423 : }
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 783423 : fd_quic_pkt_meta_t * pool ) {
208 783423 : return fd_quic_pkt_meta_treap_rev_iter_next( iter, pool );
209 783423 : }
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 1062814 : fd_quic_pkt_meta_ds_rev_iter_done( fd_quic_pkt_meta_ds_rev_iter_t iter ) {
218 1062814 : return fd_quic_pkt_meta_treap_rev_iter_done( iter );
219 1062814 : }
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 559106 : fd_quic_pkt_meta_t * pool ) {
233 559106 : return fd_quic_pkt_meta_treap_idx_ge( ds,
234 559106 : (fd_quic_pkt_meta_key_t){
235 559106 : .pkt_num = pkt_number & FD_QUIC_PKT_META_PKT_NUM_MASK,
236 559106 : .type = 0,
237 559106 : .stream_id = 0},
238 559106 : pool );
239 559106 : }
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
|
