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