ssl/quic/quic_stream_map.c

   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 #include "internal/quic_stream_map.h"
  11 #include "internal/nelem.h"
  12
  13 /* QUIC Stream
  14  * ===========
  15  */
  16
  17 int ossl_quic_stream_stop_sending(QUIC_STREAM *s, uint64_t aec)
  18 {
  19     if (s->stop_sending)
  20         return 0;
  21
  22     s->stop_sending_aec     = aec;
  23     s->stop_sending         = 1;
  24     s->want_stop_sending    = 1;
  25     return 1;
  26 }
  27
  28 int ossl_quic_stream_reset(QUIC_STREAM *s, uint64_t aec)
  29 {
  30     if (s->reset_stream)
  31         return 0;
  32
  33     s->reset_stream_aec     = aec;
  34     s->reset_stream         = 1;
  35     s->want_reset_stream    = 1;
  36     return 1;
  37 }
  38
  39 /*
  40  * QUIC Stream Map
  41  * ===============
  42  */
  43 DEFINE_LHASH_OF_EX(QUIC_STREAM);
  44
  45 /* Circular list management. */
  46 static void list_insert_tail(QUIC_STREAM_LIST_NODE *l,
  47                              QUIC_STREAM_LIST_NODE *n)
  48 {
  49     /* Must not be in list. */
  50     assert(n->prev == NULL && n->next == NULL);
  51
  52     n->prev = l->prev;
  53     n->prev->next = n;
  54     l->prev = n;
  55     n->next = l;
  56 }
  57
  58 static void list_remove(QUIC_STREAM_LIST_NODE *l,
  59                         QUIC_STREAM_LIST_NODE *n)
  60 {
  61     assert(n->prev != NULL && n->next != NULL
  62            && n->prev != n && n->next != n);
  63
  64     n->prev->next = n->next;
  65     n->next->prev = n->prev;
  66     n->next = n->prev = NULL;
  67 }
  68
  69 static QUIC_STREAM *list_next(QUIC_STREAM_LIST_NODE *l, QUIC_STREAM_LIST_NODE *n,
  70                               size_t off)
  71 {
  72     n = n->next;
  73
  74     if (n == l)
  75         n = n->next;
  76     if (n == l)
  77         return NULL;
  78
  79     return (QUIC_STREAM *)(((char *)n) - off);
  80 }
  81
  82 #define active_next(l, s) list_next((l), &(s)->active_node, \
  83                                     offsetof(QUIC_STREAM, active_node))
  84 #define accept_next(l, s) list_next((l), &(s)->accept_node, \
  85                                     offsetof(QUIC_STREAM, accept_node))
  86 #define accept_head(l)    list_next((l), (l), \
  87                                     offsetof(QUIC_STREAM, accept_node))
  88
  89 static unsigned long hash_stream(const QUIC_STREAM *s)
  90 {
  91     return (unsigned long)s->id;
  92 }
  93
  94 static int cmp_stream(const QUIC_STREAM *a, const QUIC_STREAM *b)
  95 {
  96     if (a->id < b->id)
  97         return -1;
  98     if (a->id > b->id)
  99         return 1;
 100     return 0;
 101 }
 102
 103 int ossl_quic_stream_map_init(QUIC_STREAM_MAP *qsm,
 104                               uint64_t (*get_stream_limit_cb)(int uni, void *arg),
 105                               void *get_stream_limit_cb_arg)
 106 {
 107     qsm->map = lh_QUIC_STREAM_new(hash_stream, cmp_stream);
 108     qsm->active_list.prev = qsm->active_list.next = &qsm->active_list;
 109     qsm->accept_list.prev = qsm->accept_list.next = &qsm->accept_list;
 110     qsm->rr_stepping = 1;
 111     qsm->rr_counter  = 0;
 112     qsm->rr_cur      = NULL;
 113     qsm->num_accept  = 0;
 114
 115     qsm->get_stream_limit_cb        = get_stream_limit_cb;
 116     qsm->get_stream_limit_cb_arg    = get_stream_limit_cb_arg;
 117     return 1;
 118 }
 119
 120 static void release_each(QUIC_STREAM *stream, void *arg)
 121 {
 122     QUIC_STREAM_MAP *qsm = arg;
 123
 124     ossl_quic_stream_map_release(qsm, stream);
 125 }
 126
 127 void ossl_quic_stream_map_cleanup(QUIC_STREAM_MAP *qsm)
 128 {
 129     ossl_quic_stream_map_visit(qsm, release_each, qsm);
 130
 131     lh_QUIC_STREAM_free(qsm->map);
 132     qsm->map = NULL;
 133 }
 134
 135 void ossl_quic_stream_map_visit(QUIC_STREAM_MAP *qsm,
 136                                 void (*visit_cb)(QUIC_STREAM *stream, void *arg),
 137                                 void *visit_cb_arg)
 138 {
 139     lh_QUIC_STREAM_doall_arg(qsm->map, visit_cb, visit_cb_arg);
 140 }
 141
 142 QUIC_STREAM *ossl_quic_stream_map_alloc(QUIC_STREAM_MAP *qsm,
 143                                         uint64_t stream_id,
 144                                         int type)
 145 {
 146     QUIC_STREAM *s;
 147     QUIC_STREAM key;
 148
 149     key.id = stream_id;
 150
 151     s = lh_QUIC_STREAM_retrieve(qsm->map, &key);
 152     if (s != NULL)
 153         return NULL;
 154
 155     s = OPENSSL_zalloc(sizeof(*s));
 156     if (s == NULL)
 157         return NULL;
 158
 159     s->id   = stream_id;
 160     s->type = type;
 161     lh_QUIC_STREAM_insert(qsm->map, s);
 162     return s;
 163 }
 164
 165 void ossl_quic_stream_map_release(QUIC_STREAM_MAP *qsm, QUIC_STREAM *stream)
 166 {
 167     if (stream == NULL)
 168         return;
 169
 170     ossl_quic_sstream_free(stream->sstream);
 171     stream->sstream = NULL;
 172
 173     ossl_quic_rstream_free(stream->rstream);
 174     stream->rstream = NULL;
 175
 176     lh_QUIC_STREAM_delete(qsm->map, stream);
 177     OPENSSL_free(stream);
 178 }
 179
 180 QUIC_STREAM *ossl_quic_stream_map_get_by_id(QUIC_STREAM_MAP *qsm,
 181                                             uint64_t stream_id)
 182 {
 183     QUIC_STREAM key;
 184
 185     key.id = stream_id;
 186
 187     return lh_QUIC_STREAM_retrieve(qsm->map, &key);
 188 }
 189
 190 static void stream_map_mark_active(QUIC_STREAM_MAP *qsm, QUIC_STREAM *s)
 191 {
 192     if (s->active)
 193         return;
 194
 195     list_insert_tail(&qsm->active_list, &s->active_node);
 196
 197     if (qsm->rr_cur == NULL)
 198         qsm->rr_cur = s;
 199
 200     s->active = 1;
 201 }
 202
 203 static void stream_map_mark_inactive(QUIC_STREAM_MAP *qsm, QUIC_STREAM *s)
 204 {
 205     if (!s->active)
 206         return;
 207
 208     list_remove(&qsm->active_list, &s->active_node);
 209
 210     if (qsm->rr_cur == s)
 211         qsm->rr_cur = active_next(&qsm->active_list, s);
 212     if (qsm->rr_cur == s)
 213         qsm->rr_cur = NULL;
 214
 215     s->active = 0;
 216 }
 217
 218 void ossl_quic_stream_map_set_rr_stepping(QUIC_STREAM_MAP *qsm, size_t stepping)
 219 {
 220     qsm->rr_stepping = stepping;
 221     qsm->rr_counter  = 0;
 222 }
 223
 224 static int stream_has_data_to_send(QUIC_STREAM *s)
 225 {
 226     OSSL_QUIC_FRAME_STREAM shdr;
 227     OSSL_QTX_IOVEC iov[2];
 228     size_t num_iov;
 229     uint64_t fc_credit, fc_swm, fc_limit;
 230
 231     if (s->sstream == NULL)
 232         return 0;
 233
 234     /*
 235      * We cannot determine if we have data to send simply by checking if
 236      * ossl_quic_txfc_get_credit() is zero, because we may also have older
 237      * stream data we need to retransmit. The SSTREAM returns older data first,
 238      * so we do a simple comparison of the next chunk the SSTREAM wants to send
 239      * against the TXFC CWM.
 240      */
 241     num_iov = OSSL_NELEM(iov);
 242     if (!ossl_quic_sstream_get_stream_frame(s->sstream, 0, &shdr, iov,
 243                                             &num_iov))
 244         return 0;
 245
 246     fc_credit = ossl_quic_txfc_get_credit(&s->txfc);
 247     fc_swm    = ossl_quic_txfc_get_swm(&s->txfc);
 248     fc_limit  = fc_swm + fc_credit;
 249
 250     return (shdr.is_fin && shdr.len == 0) || shdr.offset < fc_limit;
 251 }
 252
 253 void ossl_quic_stream_map_update_state(QUIC_STREAM_MAP *qsm, QUIC_STREAM *s)
 254 {
 255     int should_be_active, allowed_by_stream_limit = 1;
 256
 257     if (qsm->get_stream_limit_cb != NULL
 258         && (s->type & QUIC_STREAM_INITIATOR_CLIENT) != 0) {
 259         int uni = ((s->type & QUIC_STREAM_DIR_UNI) != 0);
 260         uint64_t stream_limit, stream_ordinal = s->id >> 2;
 261
 262         stream_limit
 263             = qsm->get_stream_limit_cb(uni, qsm->get_stream_limit_cb_arg);
 264
 265         allowed_by_stream_limit = (stream_ordinal < stream_limit);
 266     }
 267
 268     should_be_active
 269         = allowed_by_stream_limit
 270         && !s->peer_stop_sending
 271         && !s->peer_reset_stream
 272         && ((s->rstream != NULL
 273             && (s->want_max_stream_data
 274                 || ossl_quic_rxfc_has_cwm_changed(&s->rxfc, 0)))
 275             || s->want_stop_sending
 276             || s->want_reset_stream
 277             || stream_has_data_to_send(s));
 278
 279     if (should_be_active)
 280         stream_map_mark_active(qsm, s);
 281     else
 282         stream_map_mark_inactive(qsm, s);
 283 }
 284
 285 QUIC_STREAM *ossl_quic_stream_map_peek_accept_queue(QUIC_STREAM_MAP *qsm)
 286 {
 287     return accept_head(&qsm->accept_list);
 288 }
 289
 290 void ossl_quic_stream_map_push_accept_queue(QUIC_STREAM_MAP *qsm,
 291                                             QUIC_STREAM *s)
 292 {
 293     list_insert_tail(&qsm->accept_list, &s->accept_node);
 294     ++qsm->num_accept;
 295 }
 296
 297 void ossl_quic_stream_map_remove_from_accept_queue(QUIC_STREAM_MAP *qsm,
 298                                                    QUIC_STREAM *s)
 299 {
 300     list_remove(&qsm->accept_list, &s->accept_node);
 301     --qsm->num_accept;
 302 }
 303
 304 size_t ossl_quic_stream_map_get_accept_queue_len(QUIC_STREAM_MAP *qsm)
 305 {
 306     return qsm->num_accept;
 307 }
 308
 309 /*
 310  * QUIC Stream Iterator
 311  * ====================
 312  */
 313 void ossl_quic_stream_iter_init(QUIC_STREAM_ITER *it, QUIC_STREAM_MAP *qsm,
 314                                 int advance_rr)
 315 {
 316     it->qsm    = qsm;
 317     it->stream = it->first_stream = qsm->rr_cur;
 318     if (advance_rr && it->stream != NULL
 319         && ++qsm->rr_counter >= qsm->rr_stepping) {
 320         qsm->rr_counter = 0;
 321         qsm->rr_cur     = active_next(&qsm->active_list, qsm->rr_cur);
 322     }
 323 }
 324
 325 void ossl_quic_stream_iter_next(QUIC_STREAM_ITER *it)
 326 {
 327     if (it->stream == NULL)
 328         return;
 329
 330     it->stream = active_next(&it->qsm->active_list, it->stream);
 331     if (it->stream == it->first_stream)
 332         it->stream = NULL;
 333 }