include/internal/quic_stream_map.h

   1 /*
   2 * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved.
   3 *
   4 * Licensed under the Apache License 2.0 (the "License").  You may not use
   5 * this file except in compliance with the License.  You can obtain a copy
   6 * in the file LICENSE in the source distribution or at
   7 * https://www.openssl.org/source/license.html
   8 */
   9
  10 #ifndef OSSL_INTERNAL_QUIC_STREAM_MAP_H
  11 # define OSSL_INTERNAL_QUIC_STREAM_MAP_H
  12 # pragma once
  13
  14 # include "internal/e_os.h"
  15 # include "internal/time.h"
  16 # include "internal/quic_types.h"
  17 # include "internal/quic_stream.h"
  18 # include "internal/quic_fc.h"
  19 # include <openssl/lhash.h>
  20
  21 # ifndef OPENSSL_NO_QUIC
  22
  23 /*
  24  * QUIC Stream
  25  * ===========
  26  *
  27  * Logical QUIC stream composing all relevant send and receive components.
  28  */
  29 typedef struct quic_stream_st QUIC_STREAM;
  30
  31 typedef struct quic_stream_list_node_st QUIC_STREAM_LIST_NODE;
  32
  33 struct quic_stream_list_node_st {
  34     QUIC_STREAM_LIST_NODE *prev, *next;
  35 };
  36
  37 struct quic_stream_st {
  38     QUIC_STREAM_LIST_NODE active_node; /* for use by QUIC_STREAM_MAP */
  39     QUIC_STREAM_LIST_NODE accept_node; /* accept queue of remotely-created streams */
  40     QUIC_STREAM_LIST_NODE ready_for_gc_node; /* queue of streams now ready for GC */
  41
  42     /* Temporary link used by TXP. */
  43     QUIC_STREAM    *txp_next;
  44
  45     /*
  46      * QUIC Stream ID. Do not assume that this encodes a type as this is a
  47      * version-specific property and may change between QUIC versions; instead,
  48      * use the type field.
  49      */
  50     uint64_t        id;
  51
  52     /*
  53      * Application Error Code (AEC) used for STOP_SENDING frame.
  54      * This is only valid if stop_sending is 1.
  55      */
  56     uint64_t        stop_sending_aec;
  57
  58     /*
  59      * Application Error Code (AEC) used for RESET_STREAM frame.
  60      * This is only valid if reset_stream is 1.
  61      */
  62     uint64_t        reset_stream_aec;
  63
  64     /*
  65      * Application Error Code (AEC) for incoming STOP_SENDING frame.
  66      * This is only valid if peer_stop_sending is 1.
  67      */
  68     uint64_t        peer_stop_sending_aec;
  69
  70     /*
  71      * Application Error Code (AEC) for incoming RESET_STREAM frame.
  72      * This  is only valid if peer_reset_stream is 1.
  73      */
  74     uint64_t        peer_reset_stream_aec;
  75
  76     /* Temporary value used by TXP. */
  77     uint64_t        txp_txfc_new_credit_consumed;
  78
  79     QUIC_SSTREAM    *sstream;   /* NULL if RX-only */
  80     QUIC_RSTREAM    *rstream;   /* NULL if TX only */
  81     QUIC_TXFC       txfc;       /* NULL if RX-only */
  82     QUIC_RXFC       rxfc;       /* NULL if TX-only */
  83     unsigned int    type   : 8; /* QUIC_STREAM_INITIATOR_*, QUIC_STREAM_DIR_* */
  84     unsigned int    active : 1;
  85
  86     /*
  87      * Has STOP_SENDING been requested (by us)? Note that this is not the same
  88      * as want_stop_sending below, as a STOP_SENDING frame may already have been
  89      * sent and fully acknowledged.
  90      */
  91     unsigned int    stop_sending            : 1;
  92
  93     /*
  94      * Has RESET_STREAM been requested (by us)? Works identically to
  95      * STOP_SENDING for transmission purposes.
  96      */
  97     unsigned int    reset_stream            : 1;
  98
  99     /* Has our peer sent a STOP_SENDING frame? */
 100     unsigned int    peer_stop_sending       : 1;
 101     /* Has our peer sent a RESET_STREAM frame? */
 102     unsigned int    peer_reset_stream       : 1;
 103
 104     /* Temporary flags used by TXP. */
 105     unsigned int    txp_sent_fc             : 1;
 106     unsigned int    txp_sent_stop_sending   : 1;
 107     unsigned int    txp_sent_reset_stream   : 1;
 108     unsigned int    txp_drained             : 1;
 109     unsigned int    txp_blocked             : 1;
 110
 111     /* Frame regeneration flags. */
 112     unsigned int    want_max_stream_data    : 1; /* used for regen only */
 113     unsigned int    want_stop_sending       : 1; /* used for gen or regen */
 114     unsigned int    want_reset_stream       : 1; /* used for gen or regen */
 115
 116     /* Flags set when frames *we* sent were acknowledged. */
 117     unsigned int    acked_stop_sending      : 1;
 118     unsigned int    acked_reset_stream      : 1;
 119
 120     /* A FIN has been retired from the rstream buffer. */
 121     unsigned int    recv_fin_retired        : 1;
 122
 123     /*
 124      * The stream's XSO has been deleted. Pending GC.
 125      *
 126      * Here is how stream deletion works:
 127      *
 128      *   - A QUIC_STREAM cannot be deleted until it is neither in the accept
 129      *     queue nor has an associated XSO. This condition occurs when and only
 130      *     when deleted is true.
 131      *
 132      *   - Once there is the case (i.e., no user-facing API object exposing the
 133      *     stream), we can delete the stream once we determine that all of our
 134      *     protocol obligations requiring us to keep the QUIC_STREAM around have
 135      *     been met.
 136      *
 137      *     The following frames relate to the streams layer for a specific
 138      *     stream:
 139      *
 140      *          STREAM
 141      *
 142      *              RX Obligations:
 143      *                  Ignore for a deleted stream.
 144      *
 145      *                  (This is different from our obligation for a
 146      *                  locally-initiated stream ID we have not created yet,
 147      *                  which we must treat as a protocol error. This can be
 148      *                  distinguished via a simple monotonic counter.)
 149      *
 150      *              TX Obligations:
 151      *                  None, once we've decided to (someday) delete the stream.
 152      *
 153      *          STOP_SENDING
 154      *
 155      *              We cannot delete the stream until we have finished informing
 156      *              the peer that we are not going to be listening to it
 157      *              anymore.
 158      *
 159      *              RX Obligations:
 160      *                  When we delete a stream we must have already had a FIN
 161      *                  or RESET_STREAM we transmitted acknowledged by the peer.
 162      *                  Thus we can ignore STOP_SENDING frames for deleted
 163      *                  streams (if they occur, they are probably just
 164      *                  retransmissions).
 165      *
 166      *              TX Obligations:
 167      *                  _Acknowledged_ receipt of a STOP_SENDING frame by the
 168      *                  peer (unless the peer's send part has already FIN'd).
 169      *
 170      *          RESET_STREAM
 171      *
 172      *              We cannot delete the stream until we have finished informing
 173      *              the peer that we are not going to be transmitting on it
 174      *              anymore.
 175      *
 176      *              RX Obligations:
 177      *                  This indicates the peer is not going to send any more
 178      *                  data on the stream. We don't need to care about this
 179      *                  since once a stream is marked for deletion we don't care
 180      *                  about any data it does send. We can ignore this for
 181      *                  deleted streams. The important criterion is that the
 182      *                  peer has been successfully delivered our STOP_SENDING
 183      *                  frame.
 184      *
 185      *              TX Obligations:
 186      *                  _Acknowledged_ receipt of a RESET_STREAM frame or FIN by
 187      *                  the peer.
 188      *
 189      *          MAX_STREAM_DATA
 190      *
 191      *              RX Obligations:
 192      *                 Ignore. Since we are not going to be sending any more
 193      *                 data on a stream once it has been marked for deletion,
 194      *                 we don't need to care about flow control information.
 195      *
 196      *              TX Obligations:
 197      *                  None.
 198      *
 199      *     In other words, our protocol obligation is simply:
 200      *
 201      *       - either:
 202      *         - the peer has acknowledged receipt of a STOP_SENDING frame sent
 203      *            by us; -or-
 204      *         - we have received a FIN and all preceding segments from the peer
 205      *
 206      *            [NOTE: The actual criterion required here is simply 'we have
 207      *            received a FIN from the peer'. However, due to reordering and
 208      *            retransmissions we might subsequently receive non-FIN segments
 209      *            out of order. The FIN means we know the peer will stop
 210      *            transmitting on the stream at *some* point, but by sending
 211      *            STOP_SENDING we can avoid these needless retransmissions we
 212      *            will just ignore anyway. In actuality we could just handle all
 213      *            cases by sending a STOP_SENDING. The strategy we choose is to
 214      *            only avoid sending a STOP_SENDING and rely on a received FIN
 215      *            when we have received all preceding data, as this makes it
 216      *            reasonably certain no benefit would be gained by sending
 217      *            STOP_SENDING.]
 218      *
 219      *            TODO(QUIC): Implement the latter case (currently we just
 220      *                        always do STOP_SENDING).
 221      *
 222      *         and;
 223      *
 224      *       - we have drained our send stream (for a finished send stream)
 225      *         and got acknowledgement all parts of it including the FIN, or
 226      *         sent a RESET_STREAM frame and got acknowledgement of that frame.
 227      *
 228      *      Once these conditions are met, we can GC the QUIC_STREAM.
 229      *
 230      */
 231     unsigned int    deleted                 : 1;
 232     /* Set to 1 once the above conditions are actually met. */
 233     unsigned int    ready_for_gc            : 1;
 234 };
 235
 236 /*
 237  * QUIC Stream Map
 238  * ===============
 239  *
 240  * The QUIC stream map:
 241  *
 242  *   - maps stream IDs to QUIC_STREAM objects;
 243  *   - tracks which streams are 'active' (currently have data for transmission);
 244  *   - allows iteration over the active streams only.
 245  *
 246  */
 247 typedef struct quic_stream_map_st {
 248     LHASH_OF(QUIC_STREAM)   *map;
 249     QUIC_STREAM_LIST_NODE   active_list;
 250     QUIC_STREAM_LIST_NODE   accept_list;
 251     QUIC_STREAM_LIST_NODE   ready_for_gc_list;
 252     size_t                  rr_stepping, rr_counter, num_accept;
 253     QUIC_STREAM             *rr_cur;
 254     uint64_t                (*get_stream_limit_cb)(int uni, void *arg);
 255     void                    *get_stream_limit_cb_arg;
 256     QUIC_RXFC               *max_streams_bidi_rxfc;
 257     QUIC_RXFC               *max_streams_uni_rxfc;
 258 } QUIC_STREAM_MAP;
 259
 260 /*
 261  * get_stream_limit is a callback which is called to retrieve the current stream
 262  * limit for streams created by us. This mechanism is not used for
 263  * peer-initiated streams. If a stream's stream ID is x, a stream is allowed if
 264  * (x >> 2) < returned limit value; i.e., the returned value is exclusive.
 265  *
 266  * If uni is 1, get the limit for locally-initiated unidirectional streams, else
 267  * get the limit for locally-initiated bidirectional streams.
 268  *
 269  * If the callback is NULL, stream limiting is not applied.
 270  * Stream limiting is used to determine if frames can currently be produced for
 271  * a stream.
 272  */
 273 int ossl_quic_stream_map_init(QUIC_STREAM_MAP *qsm,
 274                               uint64_t (*get_stream_limit_cb)(int uni, void *arg),
 275                               void *get_stream_limit_cb_arg,
 276                               QUIC_RXFC *max_streams_bidi_rxfc,
 277                               QUIC_RXFC *max_streams_uni_rxfc);
 278
 279 /*
 280  * Any streams still in the map will be released as though
 281  * ossl_quic_stream_map_release was called on them.
 282  */
 283 void ossl_quic_stream_map_cleanup(QUIC_STREAM_MAP *qsm);
 284
 285 #define QUIC_STREAM_INITIATOR_CLIENT        0
 286 #define QUIC_STREAM_INITIATOR_SERVER        1
 287 #define QUIC_STREAM_INITIATOR_MASK          1
 288
 289 #define QUIC_STREAM_DIR_BIDI                0
 290 #define QUIC_STREAM_DIR_UNI                 2
 291 #define QUIC_STREAM_DIR_MASK                2
 292
 293 static ossl_inline ossl_unused int ossl_quic_stream_is_server_init(QUIC_STREAM *s)
 294 {
 295     return (s->type & QUIC_STREAM_INITIATOR_MASK) == QUIC_STREAM_INITIATOR_SERVER;
 296 }
 297
 298 static ossl_inline ossl_unused int ossl_quic_stream_is_bidi(QUIC_STREAM *s)
 299 {
 300     return (s->type & QUIC_STREAM_DIR_MASK) == QUIC_STREAM_DIR_BIDI;
 301 }
 302
 303 /*
 304  * Allocate a new stream. type is a combination of one QUIC_STREAM_INITIATOR_*
 305  * value and one QUIC_STREAM_DIR_* value. Note that clients can e.g. allocate
 306  * server-initiated streams as they will need to allocate a QUIC_STREAM
 307  * structure to track any stream created by the server, etc.
 308  *
 309  * stream_id must be a valid value. Returns NULL if a stream already exists
 310  * with the given ID.
 311  */
 312 QUIC_STREAM *ossl_quic_stream_map_alloc(QUIC_STREAM_MAP *qsm,
 313                                         uint64_t stream_id,
 314                                         int type);
 315
 316 /*
 317  * Releases a stream object. Note that this must only be done once the teardown
 318  * process is entirely complete and the object will never be referenced again.
 319  */
 320 void ossl_quic_stream_map_release(QUIC_STREAM_MAP *qsm, QUIC_STREAM *stream);
 321
 322 /*
 323  * Calls visit_cb() for each stream in the map. visit_cb_arg is an opaque
 324  * argument which is passed through.
 325  */
 326 void ossl_quic_stream_map_visit(QUIC_STREAM_MAP *qsm,
 327                                 void (*visit_cb)(QUIC_STREAM *stream, void *arg),
 328                                 void *visit_cb_arg);
 329
 330 /*
 331  * Retrieves a stream by stream ID. Returns NULL if it does not exist.
 332  */
 333 QUIC_STREAM *ossl_quic_stream_map_get_by_id(QUIC_STREAM_MAP *qsm,
 334                                             uint64_t stream_id);
 335
 336 /*
 337  * Marks the given stream as active or inactive based on its state. Idempotent.
 338  *
 339  * When a stream is marked active, it becomes available in the iteration list,
 340  * and when a stream is marked inactive, it no longer appears in the iteration
 341  * list.
 342  *
 343  * Calling this function invalidates any iterator currently pointing at the
 344  * given stream object, but iterators not currently pointing at the given stream
 345  * object are not invalidated.
 346  */
 347 void ossl_quic_stream_map_update_state(QUIC_STREAM_MAP *qsm, QUIC_STREAM *s);
 348
 349 /*
 350  * Sets the RR stepping value, n. The RR rotation will be advanced every n
 351  * packets. The default value is 1.
 352  */
 353 void ossl_quic_stream_map_set_rr_stepping(QUIC_STREAM_MAP *qsm, size_t stepping);
 354
 355 /*
 356  * Resets the sending part of a stream.
 357  *
 358  * Returns 1 if the sending part of a stream was not already reset.
 359  * Returns 0 otherwise, which need not be considered an error.
 360  */
 361 int ossl_quic_stream_map_reset_stream_send_part(QUIC_STREAM_MAP *qsm,
 362                                                 QUIC_STREAM *qs,
 363                                                 uint64_t aec);
 364
 365 /*
 366  * Marks the receiving part of a stream for STOP_SENDING.
 367  *
 368  * Returns  1 if the receiving part of a stream was not already marked for
 369  * STOP_SENDING.
 370  * Returns 0 otherwise, which need not be considered an error.
 371  */
 372 int ossl_quic_stream_map_stop_sending_recv_part(QUIC_STREAM_MAP *qsm,
 373                                                 QUIC_STREAM *qs,
 374                                                 uint64_t aec);
 375
 376 /*
 377  * Adds a stream to the accept queue.
 378  */
 379 void ossl_quic_stream_map_push_accept_queue(QUIC_STREAM_MAP *qsm,
 380                                             QUIC_STREAM *s);
 381
 382 /*
 383  * Returns the next item to be popped from the accept queue, or NULL if it is
 384  * empty.
 385  */
 386 QUIC_STREAM *ossl_quic_stream_map_peek_accept_queue(QUIC_STREAM_MAP *qsm);
 387
 388 /*
 389  * Removes a stream from the accept queue. rtt is the estimated connection RTT.
 390  * The stream is retired for the purposes of MAX_STREAMS RXFC.
 391  *
 392  * Precondition: s is in the accept queue.
 393  */
 394 void ossl_quic_stream_map_remove_from_accept_queue(QUIC_STREAM_MAP *qsm,
 395                                                    QUIC_STREAM *s,
 396                                                    OSSL_TIME rtt);
 397
 398 /* Returns the length of the accept queue. */
 399 size_t ossl_quic_stream_map_get_accept_queue_len(QUIC_STREAM_MAP *qsm);
 400
 401 /*
 402  * Delete streams ready for GC. Pointers to those QUIC_STREAM objects become
 403  * invalid.
 404  */
 405 void ossl_quic_stream_map_gc(QUIC_STREAM_MAP *qsm);
 406
 407 /*
 408  * QUIC Stream Iterator
 409  * ====================
 410  *
 411  * Allows the current set of active streams to be walked using a RR-based
 412  * algorithm. Each time ossl_quic_stream_iter_init is called, the RR algorithm
 413  * is stepped. The RR algorithm rotates the iteration order such that the next
 414  * active stream is returned first after n calls to ossl_quic_stream_iter_init,
 415  * where n is the stepping value configured via
 416  * ossl_quic_stream_map_set_rr_stepping.
 417  *
 418  * Suppose there are three active streams and the configured stepping is n:
 419  *
 420  *   Iteration 0n:  [Stream 1] [Stream 2] [Stream 3]
 421  *   Iteration 1n:  [Stream 2] [Stream 3] [Stream 1]
 422  *   Iteration 2n:  [Stream 3] [Stream 1] [Stream 2]
 423  *
 424  */
 425 typedef struct quic_stream_iter_st {
 426     QUIC_STREAM_MAP     *qsm;
 427     QUIC_STREAM         *first_stream, *stream;
 428 } QUIC_STREAM_ITER;
 429
 430 /*
 431  * Initialise an iterator, advancing the RR algorithm as necessary (if
 432  * advance_rr is 1). After calling this, it->stream will be the first stream in
 433  * the iteration sequence, or NULL if there are no active streams.
 434  */
 435 void ossl_quic_stream_iter_init(QUIC_STREAM_ITER *it, QUIC_STREAM_MAP *qsm,
 436                                 int advance_rr);
 437
 438 /*
 439  * Advances to next stream in iteration sequence. You do not need to call this
 440  * immediately after calling ossl_quic_stream_iter_init(). If the end of the
 441  * list is reached, it->stream will be NULL after calling this.
 442  */
 443 void ossl_quic_stream_iter_next(QUIC_STREAM_ITER *it);
 444
 445 # endif
 446
 447 #endif