Line data    Source code

       1             : /* SPDX-License-Identifier: GPL-2.0-or-later */
       2             : /* QUIC kernel implementation
       3             :  * (C) Copyright Red Hat Corp. 2023
       4             :  *
       5             :  * This file is part of the QUIC kernel implementation
       6             :  *
       7             :  * Written or modified by:
       8             :  *    Xin Long <lucien.xin@gmail.com>
       9             :  */
      10             : 
      11             : #define QUIC_PN_MAX_GABS        32
      12             : #define QUIC_PN_MAP_MAX_PN      (BIT_ULL(62) - 1)
      13             : 
      14             : #define QUIC_PN_MAP_INITIAL     64
      15             : #define QUIC_PN_MAP_INCREMENT   QUIC_PN_MAP_INITIAL
      16             : #define QUIC_PN_MAP_SIZE        4096
      17             : #define QUIC_PN_MAP_LIMIT       (QUIC_PN_MAP_SIZE * 3 / 4)
      18             : 
      19             : #define QUIC_PNSPACE_MAX        (QUIC_CRYPTO_MAX - 1)
      20             : #define QUIC_PNSPACE_NEXT_PN    0
      21             : #define QUIC_PNSPACE_TIME_LIMIT (333000 * 3)
      22             : 
      23             : enum {
      24             :         QUIC_ECN_ECT1,
      25             :         QUIC_ECN_ECT0,
      26             :         QUIC_ECN_CE,
      27             :         QUIC_ECN_MAX
      28             : };
      29             : 
      30             : enum {
      31             :         QUIC_ECN_LOCAL,         /* ECN bits from incoming IP headers */
      32             :         QUIC_ECN_PEER,          /* ECN bits reported by peer in ACK frames */
      33             :         QUIC_ECN_DIR_MAX
      34             : };
      35             : 
      36             : /* Represents a gap (range of missing packets) in the ACK map.  The values are offsets from
      37             :  * base_pn, with both 'start' and 'end' being +1.
      38             :  */
      39             : struct quic_gap_ack_block {
      40             :         u16 start;
      41             :         u16 end;
      42             : };
      43             : 
      44             : /* Packet Number Map (pn_map) Layout:
      45             :  *
      46             :  *     min_pn_seen -->++-----------------------+---------------------+---
      47             :  *         base_pn -----^   last_max_pn_seen --^       max_pn_seen --^
      48             :  *
      49             :  * Map Advancement Logic:
      50             :  *   - min_pn_seen = last_max_pn_seen;
      51             :  *   - base_pn = first zero bit after last_max_pn_seen;
      52             :  *   - last_max_pn_seen = max_pn_seen;
      53             :  *   - last_max_pn_time = current time;
      54             :  *
      55             :  * Conditions to Advance pn_map:
      56             :  *   - (max_pn_time - last_max_pn_time) >= max_time_limit, or
      57             :  *   - (max_pn_seen - last_max_pn_seen) > QUIC_PN_MAP_LIMIT
      58             :  *
      59             :  * Gap Search Range:
      60             :  *   - From (base_pn - 1) to max_pn_seen
      61             :  */
      62             : struct quic_pnspace {
      63             :         /* ECN counters indexed by direction (TX/RX) and ECN codepoint (ECT1, ECT0, CE) */
      64             :         u64 ecn_count[QUIC_ECN_DIR_MAX][QUIC_ECN_MAX];
      65             :         unsigned long *pn_map;  /* Bit map tracking received packet numbers for ACK generation */
      66             :         u16 pn_map_len;         /* Length of the packet number bit map (in bits) */
      67             :         u8  need_sack:1;        /* Flag indicating a SACK frame should be sent for this space */
      68             :         u8  sack_path:1;        /* Path used for sending the SACK frame */
      69             : 
      70             :         s64 last_max_pn_seen;   /* Highest packet number seen before pn_map advanced */
      71             :         u32 last_max_pn_time;   /* Timestamp when last_max_pn_seen was received */
      72             :         u32 max_time_limit;     /* Time threshold to trigger pn_map advancement on packet receipt */
      73             :         s64 min_pn_seen;        /* Smallest packet number received in this space */
      74             :         s64 max_pn_seen;        /* Largest packet number received in this space */
      75             :         u32 max_pn_time;        /* Time at which max_pn_seen was received */
      76             :         s64 base_pn;            /* Packet number corresponding to the start of the pn_map */
      77             :         u32 time;               /* Cached current time, or time accept a socket (listen socket) */
      78             : 
      79             :         s64 max_pn_acked_seen;  /* Largest packet number acknowledged by the peer */
      80             :         u32 max_pn_acked_time;  /* Time at which max_pn_acked_seen was acknowledged */
      81             :         u32 last_sent_time;     /* Time when the last ack-eliciting packet was sent */
      82             :         u32 loss_time;          /* Time after which the next packet can be declared lost */
      83             :         u32 inflight;           /* Bytes of all ack-eliciting frames in flight in this space */
      84             :         s64 next_pn;            /* Next packet number to send in this space */
      85             : };
      86             : 
      87      369410 : static inline void quic_pnspace_set_max_pn_acked_seen(struct quic_pnspace *space,
      88             :                                                       s64 max_pn_acked_seen)
      89             : {
      90      369410 :         if (space->max_pn_acked_seen >= max_pn_acked_seen)
      91             :                 return;
      92      368402 :         space->max_pn_acked_seen = max_pn_acked_seen;
      93      368402 :         space->max_pn_acked_time = jiffies_to_usecs(jiffies);
      94             : }
      95             : 
      96        2980 : static inline void quic_pnspace_set_base_pn(struct quic_pnspace *space, s64 pn)
      97             : {
      98        2980 :         space->base_pn = pn;
      99        2980 :         space->max_pn_seen = space->base_pn - 1;
     100        2980 :         space->last_max_pn_seen = space->max_pn_seen;
     101        2980 :         space->min_pn_seen = space->max_pn_seen;
     102             : 
     103        2980 :         space->max_pn_time = space->time;
     104        2980 :         space->last_max_pn_time = space->max_pn_time;
     105             : }
     106             : 
     107     6867565 : static inline bool quic_pnspace_has_gap(const struct quic_pnspace *space)
     108             : {
     109     6867565 :         return space->base_pn != space->max_pn_seen + 1;
     110             : }
     111             : 
     112     6575110 : static inline void quic_pnspace_inc_ecn_count(struct quic_pnspace *space, u8 ecn)
     113             : {
     114     6575110 :         if (!ecn)
     115             :                 return;
     116     6456258 :         space->ecn_count[QUIC_ECN_LOCAL][ecn - 1]++;
     117             : }
     118             : 
     119             : /* Check if any ECN-marked packets were received. */
     120      378481 : static inline bool quic_pnspace_has_ecn_count(struct quic_pnspace *space)
     121             : {
     122      403465 :         return space->ecn_count[QUIC_ECN_LOCAL][QUIC_ECN_ECT0] ||
     123      378481 :                space->ecn_count[QUIC_ECN_LOCAL][QUIC_ECN_ECT1] ||
     124       24972 :                space->ecn_count[QUIC_ECN_LOCAL][QUIC_ECN_CE];
     125             : }
     126             : 
     127             : /* Updates the stored ECN counters based on values received in the peer's ACK
     128             :  * frame. Each counter is updated only if the new value is higher.
     129             :  *
     130             :  * Returns: 1 if CE count was increased (congestion indicated), 0 otherwise.
     131             :  */
     132      382736 : static inline int quic_pnspace_set_ecn_count(struct quic_pnspace *space, u64 *ecn_count)
     133             : {
     134      382736 :         if (space->ecn_count[QUIC_ECN_PEER][QUIC_ECN_ECT0] < ecn_count[QUIC_ECN_ECT0])
     135      362855 :                 space->ecn_count[QUIC_ECN_PEER][QUIC_ECN_ECT0] = ecn_count[QUIC_ECN_ECT0];
     136      382736 :         if (space->ecn_count[QUIC_ECN_PEER][QUIC_ECN_ECT1] < ecn_count[QUIC_ECN_ECT1])
     137           0 :                 space->ecn_count[QUIC_ECN_PEER][QUIC_ECN_ECT1] = ecn_count[QUIC_ECN_ECT1];
     138      382736 :         if (space->ecn_count[QUIC_ECN_PEER][QUIC_ECN_CE] < ecn_count[QUIC_ECN_CE]) {
     139           0 :                 space->ecn_count[QUIC_ECN_PEER][QUIC_ECN_CE] = ecn_count[QUIC_ECN_CE];
     140           0 :                 return 1;
     141             :         }
     142             :         return 0;
     143             : }
     144             : 
     145             : u16 quic_pnspace_num_gabs(struct quic_pnspace *space, struct quic_gap_ack_block *gabs);
     146             : int quic_pnspace_check(struct quic_pnspace *space, s64 pn);
     147             : int quic_pnspace_mark(struct quic_pnspace *space, s64 pn);
     148             : 
     149             : void quic_pnspace_free(struct quic_pnspace *space);
     150             : int quic_pnspace_init(struct quic_pnspace *space);