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 49074 : # define FD_QUIC_PKT_META_TYPE_HS_DATA (0) 29 26588443 : # define FD_QUIC_PKT_META_TYPE_STREAM (1) 30 12042 : # 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 12108 : # define FD_QUIC_PKT_META_TYPE_CLOSE (5) 34 102 : # 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 13336594 : (PKT_META_PTR)->key.type = (uchar)((TYPE)&0x0f) 40 : 41 14588131 : #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 13582681 : (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 : ulong tx_time; /* transmit time */ 70 : ulong 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 6762 : #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 38599830 : 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 38599830 : ulong q_b = q.b[0]; 99 38599830 : ulong e_b = e->key.b[0]; 100 38599830 : ulong q_s = q.stream_id; 101 38599830 : ulong e_s = e->key.stream_id; 102 : 103 38599830 : int pkt_num_type_cmp = -2*(q_b < e_b) + ((q_b > e_b)<<1); 104 38599830 : int stream_id_cmp = -1*(q_s < e_s) + (q_s > e_s); 105 38599830 : return pkt_num_type_cmp + stream_id_cmp; 106 38599830 : } 107 : 108 : static inline int 109 : fd_quic_pkt_meta_lt( const fd_quic_pkt_meta_t * e1, 110 37042783 : const fd_quic_pkt_meta_t * e2 ) { 111 37042783 : ulong e1_b0 = e1->key.b[0]; 112 37042783 : ulong e2_b0 = e2->key.b[0]; 113 37042783 : return e1_b0 < e2_b0 || (e1_b0 == e2_b0 && e1->key.stream_id < e2->key.stream_id); 114 37042783 : } 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 38599821 : #define TREAP_CMP(q,e) fd_quic_pkt_meta_cmp( q, e ) 120 37042783 : #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 : 128 : /* fd_quic_pkt_meta_ds_fwd_iter_init is equivalent of ds.begin() 129 : @arguments: 130 : - ds: pointer to the ds 131 : - pool: pointer to the backing pool 132 : @returns: 133 : - beginning iterator */ 134 : static inline fd_quic_pkt_meta_ds_fwd_iter_t 135 : fd_quic_pkt_meta_ds_fwd_iter_init( fd_quic_pkt_meta_ds_t * ds, 136 54463192 : fd_quic_pkt_meta_t * pool ) { 137 54463192 : return fd_quic_pkt_meta_treap_fwd_iter_init( ds, pool ); 138 54463192 : } 139 : 140 : /* fd_quic_pkt_meta_ds_fwd_iter_ele returns pkt_meta* from iter 141 : @arguments: 142 : - iter: iterator 143 : - pool: pointer to the backing pool 144 : @returns: 145 : - pointer to pkt_meta */ 146 : static inline fd_quic_pkt_meta_t * 147 : fd_quic_pkt_meta_ds_fwd_iter_ele( fd_quic_pkt_meta_ds_fwd_iter_t iter, 148 39742945 : fd_quic_pkt_meta_t * pool ) { 149 39742945 : return fd_quic_pkt_meta_treap_fwd_iter_ele( iter, pool ); 150 39742945 : } 151 : 152 : /* fd_quic_pkt_meta_ds_fwd_iter_next is equivalent of iter++ 153 : @arguments: 154 : - iter: iterator 155 : - pool: pointer to the backing pool 156 : @returns: 157 : - next iterator */ 158 : static inline fd_quic_pkt_meta_ds_fwd_iter_t 159 : fd_quic_pkt_meta_ds_fwd_iter_next( fd_quic_pkt_meta_ds_fwd_iter_t iter, 160 26638209 : fd_quic_pkt_meta_t * pool ) { 161 26638209 : return fd_quic_pkt_meta_treap_fwd_iter_next( iter, pool ); 162 26638209 : } 163 : 164 : /* fd_quic_pkt_meta_ds_fwd_iter_done returns boolean 165 : @arguments 166 : - iter: iterator 167 : @returns 168 : - non-zero if iterator marks end, 0 otherwise */ 169 : static inline int 170 81652249 : fd_quic_pkt_meta_ds_fwd_iter_done( fd_quic_pkt_meta_ds_fwd_iter_t iter ) { 171 81652249 : return fd_quic_pkt_meta_treap_fwd_iter_done( iter ); 172 81652249 : } 173 : 174 : /* fd_quic_pkt_meta_ds_idx_ge returns iterator pointing to first pkt_meta 175 : whose packet number is >= pkt_number 176 : @arguments 177 : - ds: pointer to the ds 178 : - pkt_number: pkt_number to search for 179 : - pool: pointer to the backing pool 180 : @returns 181 : - iterator to first pkt_meta with pkt number >= pkt_number */ 182 : static inline fd_quic_pkt_meta_ds_fwd_iter_t 183 : fd_quic_pkt_meta_ds_idx_ge( fd_quic_pkt_meta_ds_t * ds, 184 : ulong pkt_number, 185 502725 : fd_quic_pkt_meta_t * pool ) { 186 502725 : return fd_quic_pkt_meta_treap_idx_ge( ds, 187 502725 : (fd_quic_pkt_meta_key_t){ 188 502725 : .pkt_num = pkt_number & FD_QUIC_PKT_META_PKT_NUM_MASK, 189 502725 : .type = 0, 190 502725 : .stream_id = 0}, 191 502725 : pool ); 192 502725 : } 193 : 194 : /* fd_quic_pkt_meta_ds_ele_cnt returns count of elements in ds */ 195 : static inline ulong 196 96423 : fd_quic_pkt_meta_ds_ele_cnt( fd_quic_pkt_meta_ds_t * ds ) { 197 96423 : return fd_quic_pkt_meta_treap_ele_cnt( ds ); 198 96423 : } 199 : 200 : /* end aliasing to abstract data structure */ 201 : 202 : struct fd_quic_pkt_meta_tracker { 203 : fd_quic_pkt_meta_ds_t sent_pkt_metas[4]; 204 : fd_quic_pkt_meta_t * pool; 205 : }; 206 : typedef struct fd_quic_pkt_meta_tracker fd_quic_pkt_meta_tracker_t; 207 : 208 : /* fd_quic_pkt_meta_ds_init_pool does any data structure-particular setup 209 : on the entire pool at once. Useful for e.g. treap randomness 210 : @arguments: 211 : - pool: pointer pkt_meta pool 212 : - total_meta_cnt: total pool size */ 213 : void 214 : fd_quic_pkt_meta_ds_init_pool( fd_quic_pkt_meta_t * pool, 215 : ulong total_meta_cnt ); 216 : 217 : /* fd_quic_pkt_meta_tracker_init initializes the metadata tracker for each enc level 218 : @arguments: 219 : - tracker: pointer to the tracker 220 : - total_meta_cnt: total number of max pkt_meta entries in this tracker 221 : (shared across all encoding levels) 222 : - pool: pointer to the backing pool 223 : @returns: 224 : - pointer to tracker if successful, NULL otherwise */ 225 : void * 226 : fd_quic_pkt_meta_tracker_init( fd_quic_pkt_meta_tracker_t * tracker, 227 : ulong total_meta_cnt, 228 : fd_quic_pkt_meta_t * pool ); 229 : 230 : /* fd_quic_pkt_meta_insert inserts a pkt_meta into the ds 231 : @arguments: 232 : - ds: pointer to the ds 233 : - pkt_meta: pointer to the pkt_meta to insert. This pkt_meta 234 : should have been acquired from the pool 235 : - pool: pointer to the backing pool */ 236 : void 237 : fd_quic_pkt_meta_insert( fd_quic_pkt_meta_ds_t * ds, 238 : fd_quic_pkt_meta_t * pkt_meta, 239 : fd_quic_pkt_meta_t * pool ); 240 : 241 : /* 242 : remove all pkt_meta in the range [pkt_number_lo, pkt_number_hi] 243 : rm from treap and return to pool 244 : */ 245 : /* fd_quic_pkt_meta_remove_range removes all pkt_meta in the range 246 : [pkt_number_lo, pkt_number_hi] from the ds and returns them to the pool. 247 : Any part of the range that's missing simply gets skipped 248 : @arguments: 249 : - ds: pointer to the ds 250 : - pool: pointer to the backing pool 251 : - pkt_number_lo: lower bound of the range 252 : - pkt_number_hi: upper bound of the range 253 : @returns: 254 : - number of pkt_meta removed */ 255 : ulong 256 : fd_quic_pkt_meta_remove_range( fd_quic_pkt_meta_ds_t * ds, 257 : fd_quic_pkt_meta_t * pool, 258 : ulong pkt_number_lo, 259 : ulong pkt_number_hi ); 260 : 261 : /* fd_quic_pkt_meta_min returns pointer to pkt_meta with smallest pkt_number in the ds 262 : @arguments: 263 : - ds: pointer to the ds 264 : - pool: pointer to the backing pool 265 : @returns: 266 : - pointer to pkt_meta with smallest pkt_number in the ds */ 267 : fd_quic_pkt_meta_t * 268 : fd_quic_pkt_meta_min( fd_quic_pkt_meta_ds_t * ds, 269 : fd_quic_pkt_meta_t * pool ); 270 : 271 : /* fd_quic_pkt_meta_ds_clear clears all pkt_meta tracking for a given encoding level 272 : @arguments: 273 : - tracker: pointer to the pkt_meta tracker 274 : - enc_level: encoding level to clear */ 275 : void 276 : fd_quic_pkt_meta_ds_clear( fd_quic_pkt_meta_tracker_t * tracker, 277 : uint enc_level ); 278 : 279 : FD_PROTOTYPES_END 280 : 281 : #endif // HEADER_fd_src_waltz_quic_fd_quic_pkt_meta_h