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