lsquic_packet_out.c revision 4026a4b6 
1/* Copyright (c) 2017 - 2021 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_packet_out.c
4 */
5
6#include <assert.h>
7#include <errno.h>
8#include <stdlib.h>
9#include <string.h>
10#include <sys/queue.h>
11
12#include "lsquic.h"
13#include "lsquic_int_types.h"
14#include "lsquic_malo.h"
15#include "lsquic_mm.h"
16#include "lsquic_engine_public.h"
17#include "lsquic_packet_common.h"
18#include "lsquic_packet_gquic.h"
19#include "lsquic_packet_in.h"
20#include "lsquic_packet_out.h"
21#include "lsquic_parse.h"
22#include "lsquic_sfcw.h"
23#include "lsquic_varint.h"
24#include "lsquic_hq.h"
25#include "lsquic_hash.h"
26#include "lsquic_stream.h"
27#include "lsquic_logger.h"
28#include "lsquic_ev_log.h"
29#include "lsquic_conn.h"
30#include "lsquic_enc_sess.h"
31
32typedef char _stream_rec_arr_is_at_most_64bytes[
33                                (sizeof(struct frame_rec_arr) <= 64)? 1: - 1];
34
35static struct frame_rec *
36frec_one_pofi_first (struct packet_out_frec_iter *pofi,
37                     struct lsquic_packet_out *packet_out)
38{
39    if (packet_out->po_frecs.one.fe_frame_type)
40        return &packet_out->po_frecs.one;
41    else
42        return NULL;
43}
44
45
46static struct frame_rec *
47frec_one_pofi_next (struct packet_out_frec_iter *pofi)
48{
49    return NULL;
50}
51
52
53static struct frame_rec *
54frec_arr_pofi_next (struct packet_out_frec_iter *pofi)
55{
56    while (pofi->cur_frec_arr)
57    {
58        for (; pofi->frec_idx < sizeof(pofi->cur_frec_arr->frecs) / sizeof(pofi->cur_frec_arr->frecs[0]);
59                ++pofi->frec_idx)
60        {
61            if (pofi->cur_frec_arr->frecs[ pofi->frec_idx ].fe_frame_type)
62                return &pofi->cur_frec_arr->frecs[ pofi->frec_idx++ ];
63        }
64        pofi->cur_frec_arr = TAILQ_NEXT(pofi->cur_frec_arr, next_stream_rec_arr);
65        pofi->frec_idx = 0;
66    }
67    return NULL;
68}
69
70
71static struct frame_rec *
72frec_arr_pofi_first (struct packet_out_frec_iter *pofi,
73                     struct lsquic_packet_out *packet_out)
74{
75    pofi->packet_out = packet_out;
76    pofi->cur_frec_arr = TAILQ_FIRST(&packet_out->po_frecs.arr);
77    pofi->frec_idx = 0;
78    return frec_arr_pofi_next(pofi);
79}
80
81
82static struct frame_rec * (* const pofi_firsts[])
83    (struct packet_out_frec_iter *, struct lsquic_packet_out *) =
84{
85    frec_one_pofi_first,
86    frec_arr_pofi_first,
87};
88
89
90static struct frame_rec * (* const pofi_nexts[])
91    (struct packet_out_frec_iter *pofi) =
92{
93    frec_one_pofi_next,
94    frec_arr_pofi_next,
95};
96
97
98struct frame_rec *
99lsquic_pofi_first (struct packet_out_frec_iter *pofi,
100            lsquic_packet_out_t *packet_out)
101{
102    pofi->impl_idx = !!(packet_out->po_flags & PO_FREC_ARR);
103    return pofi_firsts[pofi->impl_idx](pofi, packet_out);
104}
105
106
107struct frame_rec *
108lsquic_pofi_next (struct packet_out_frec_iter *pofi)
109{
110    return pofi_nexts[pofi->impl_idx](pofi);
111}
112
113
114/*
115 * Assumption: frames are added to the packet_out in order of their placement
116 * in packet_out->po_data.  There is no assertion to guard for for this.
117 */
118int
119lsquic_packet_out_add_frame (lsquic_packet_out_t *packet_out,
120                              struct lsquic_mm *mm,
121                              uintptr_t data,
122                              enum quic_frame_type frame_type,
123                              unsigned short off, unsigned short len)
124{
125    struct frame_rec_arr *frec_arr;
126    int last_taken;
127    unsigned i;
128
129    if (!(packet_out->po_flags & PO_FREC_ARR))
130    {
131        if (!frec_taken(&packet_out->po_frecs.one))
132        {
133            packet_out->po_frecs.one.fe_frame_type  = frame_type;
134            packet_out->po_frecs.one.fe_u.data      = data;
135            packet_out->po_frecs.one.fe_off         = off;
136            packet_out->po_frecs.one.fe_len         = len;
137            return 0;                           /* Insert in first slot */
138        }
139        frec_arr = lsquic_malo_get(mm->malo.frame_rec_arr);
140        if (!frec_arr)
141            return -1;
142        memset(frec_arr, 0, sizeof(*frec_arr));
143        frec_arr->frecs[0] = packet_out->po_frecs.one;
144        TAILQ_INIT(&packet_out->po_frecs.arr);
145        TAILQ_INSERT_TAIL(&packet_out->po_frecs.arr, frec_arr,
146                           next_stream_rec_arr);
147        packet_out->po_flags |= PO_FREC_ARR;
148        i = 1;
149        goto set_elem;
150    }
151
152    /* New records go at the very end: */
153    frec_arr = TAILQ_LAST(&packet_out->po_frecs.arr, frame_rec_arr_tailq);
154    last_taken = -1;
155    for (i = 0; i < sizeof(frec_arr->frecs) / sizeof(frec_arr->frecs[0]); ++i)
156        if (frec_taken(&frec_arr->frecs[i]))
157            last_taken = i;
158
159    i = last_taken + 1;
160    if (i < sizeof(frec_arr->frecs) / sizeof(frec_arr->frecs[0]))
161    {
162  set_elem:
163        frec_arr->frecs[i].fe_frame_type  = frame_type;
164        frec_arr->frecs[i].fe_u.data      = data;
165        frec_arr->frecs[i].fe_off         = off;
166        frec_arr->frecs[i].fe_len         = len;
167        return 0;                   /* Insert in existing frec */
168    }
169
170    frec_arr = lsquic_malo_get(mm->malo.frame_rec_arr);
171    if (!frec_arr)
172        return -1;
173
174    memset(frec_arr, 0, sizeof(*frec_arr));
175    frec_arr->frecs[0].fe_frame_type  = frame_type;
176    frec_arr->frecs[0].fe_u.data      = data;
177    frec_arr->frecs[0].fe_off         = off;
178    frec_arr->frecs[0].fe_len         = len;
179    TAILQ_INSERT_TAIL(&packet_out->po_frecs.arr, frec_arr, next_stream_rec_arr);
180    return 0;                               /* Insert in new frec */
181}
182
183
184int
185lsquic_packet_out_add_stream (struct lsquic_packet_out *packet_out,
186      struct lsquic_mm *mm, struct lsquic_stream *new_stream,
187      enum quic_frame_type frame_type, unsigned short off, unsigned short len)
188{
189    assert(!(new_stream->stream_flags & STREAM_FINISHED));
190    assert((1 << frame_type)
191                & (QUIC_FTBIT_STREAM|QUIC_FTBIT_CRYPTO|QUIC_FTBIT_RST_STREAM));
192    if (0 == lsquic_packet_out_add_frame(packet_out, mm,
193                            (uintptr_t) new_stream, frame_type, off, len))
194    {
195        ++new_stream->n_unacked;
196        return 0;
197    }
198    else
199        return -1;
200}
201
202
203lsquic_packet_out_t *
204lsquic_packet_out_new (struct lsquic_mm *mm, struct malo *malo, int use_cid,
205                const struct lsquic_conn *lconn, enum packno_bits bits,
206                const lsquic_ver_tag_t *ver_tag, const unsigned char *nonce,
207                const struct network_path *path, enum header_type header_type)
208{
209    lsquic_packet_out_t *packet_out;
210    enum packet_out_flags flags;
211    size_t header_size, tag_len, max_size;
212
213    flags = bits << POBIT_SHIFT;
214    if (ver_tag)
215        flags |= PO_VERSION;
216    if (nonce)
217        flags |= PO_NONCE;
218    if (use_cid)
219        flags |= PO_CONN_ID;
220    if ((lconn->cn_flags & (LSCONN_MINI|LSCONN_HANDSHAKE_DONE))
221                                                != LSCONN_HANDSHAKE_DONE)
222        flags |= PO_LONGHEAD;
223
224    header_size = lconn->cn_pf->pf_packout_max_header_size(lconn, flags,
225                                            path->np_dcid.len, header_type);
226    tag_len = lconn->cn_esf_c->esf_tag_len;
227    max_size = path->np_pack_size;
228    if (header_size + tag_len >= max_size)
229    {
230        errno = EINVAL;
231        return NULL;
232    }
233
234    packet_out = lsquic_mm_get_packet_out(mm, malo, max_size - header_size
235                                                - tag_len);
236    if (!packet_out)
237        return NULL;
238
239    packet_out->po_flags = flags;
240    if ((1 << lconn->cn_version) & LSQUIC_GQUIC_HEADER_VERSIONS)
241        packet_out->po_lflags = POL_GQUIC;
242    if (ver_tag)
243        packet_out->po_ver_tag = *ver_tag;
244    if (nonce)
245    {
246        /* Nonces are allocated for a very small number of packets.  This
247         * memory is too expensive to carry in every packet.
248         */
249        packet_out->po_nonce = malloc(32);
250        if (!packet_out->po_nonce)
251        {
252            lsquic_mm_put_packet_out(mm, packet_out);
253            return NULL;
254        }
255        memcpy(packet_out->po_nonce, nonce, 32);
256    }
257    if (flags & PO_LONGHEAD)
258    {
259        if (lconn->cn_version == LSQVER_050)
260        {
261            if (lconn->cn_flags & (LSCONN_SERVER|LSCONN_HANDSHAKE_DONE))
262                packet_out->po_header_type = HETY_0RTT;
263            else
264                packet_out->po_header_type = HETY_INITIAL;
265        }
266        else
267            packet_out->po_header_type = HETY_HANDSHAKE;
268    }
269    packet_out->po_path = path;
270
271    return packet_out;
272}
273
274
275void
276lsquic_packet_out_destroy (lsquic_packet_out_t *packet_out,
277                           struct lsquic_engine_public *enpub, void *peer_ctx)
278{
279    if (packet_out->po_flags & PO_FREC_ARR)
280    {
281        struct frame_rec_arr *frec_arr, *next;
282        for (frec_arr = TAILQ_FIRST(&packet_out->po_frecs.arr);
283                                             frec_arr; frec_arr = next)
284        {
285            next = TAILQ_NEXT(frec_arr, next_stream_rec_arr);
286            lsquic_malo_put(frec_arr);
287        }
288    }
289    if (packet_out->po_flags & PO_ENCRYPTED)
290        enpub->enp_pmi->pmi_release(enpub->enp_pmi_ctx, peer_ctx,
291                packet_out->po_enc_data, lsquic_packet_out_ipv6(packet_out));
292    if (packet_out->po_nonce)
293        free(packet_out->po_nonce);
294    if (packet_out->po_bwp_state)
295        lsquic_malo_put(packet_out->po_bwp_state);
296    lsquic_mm_put_packet_out(&enpub->enp_mm, packet_out);
297}
298
299
300/* If `stream_id' is UINT64_MAX, stream frames from all reset streams are elided.
301 * Otherwise, elision is limited to the specified stream.
302 */
303unsigned
304lsquic_packet_out_elide_reset_stream_frames (lsquic_packet_out_t *packet_out,
305                                             lsquic_stream_id_t stream_id)
306{
307    struct packet_out_frec_iter pofi;
308    struct frame_rec *frec;
309    unsigned short adj = 0;
310    int n_stream_frames = 0, n_elided = 0;
311    int victim;
312
313    for (frec = lsquic_pofi_first(&pofi, packet_out); frec;
314                                            frec = lsquic_pofi_next(&pofi))
315    {
316        /* Offsets of all frame records should be adjusted */
317        frec->fe_off -= adj;
318
319        if (frec->fe_frame_type == QUIC_FRAME_STREAM)
320        {
321            ++n_stream_frames;
322
323            if (stream_id != UINT64_MAX)
324            {
325                victim = frec->fe_stream->id == stream_id;
326                if (victim)
327                {
328                    assert(lsquic_stream_is_write_reset(frec->fe_stream));
329                }
330            }
331            else
332                victim = lsquic_stream_is_write_reset(frec->fe_stream);
333
334            if (victim)
335            {
336                ++n_elided;
337
338                /* Move the data and adjust sizes */
339                adj += frec->fe_len;
340                memmove(packet_out->po_data + frec->fe_off,
341                        packet_out->po_data + frec->fe_off + frec->fe_len,
342                        packet_out->po_data_sz - frec->fe_off - frec->fe_len);
343                packet_out->po_data_sz -= frec->fe_len;
344
345                lsquic_stream_acked(frec->fe_stream, frec->fe_frame_type);
346                frec->fe_frame_type = 0;
347            }
348        }
349    }
350
351    assert(n_stream_frames);
352    if (n_elided == n_stream_frames)
353    {
354        packet_out->po_frame_types &= ~(1 << QUIC_FRAME_STREAM);
355        packet_out->po_flags &= ~PO_STREAM_END;
356    }
357
358    return adj;
359}
360
361
362void
363lsquic_packet_out_chop_regen (lsquic_packet_out_t *packet_out)
364{
365    struct packet_out_frec_iter pofi;
366    struct frame_rec *frec;
367    unsigned short adj;
368
369    adj = 0;
370    for (frec = lsquic_pofi_first(&pofi, packet_out); frec;
371                                                frec = lsquic_pofi_next(&pofi))
372    {
373        frec->fe_off -= adj;
374        if (BQUIC_FRAME_REGEN_MASK & (1 << frec->fe_frame_type))
375        {
376            adj += frec->fe_len;
377            memmove(packet_out->po_data + frec->fe_off,
378                    packet_out->po_data + frec->fe_off + frec->fe_len,
379                    packet_out->po_data_sz - frec->fe_off - frec->fe_len);
380            packet_out->po_data_sz -= frec->fe_len;
381            frec->fe_frame_type = 0;
382        }
383    }
384
385    assert(adj);    /* Otherwise why are we called? */
386    packet_out->po_regen_sz = 0;
387    packet_out->po_frame_types &= ~BQUIC_FRAME_REGEN_MASK;
388}
389
390
391void
392lsquic_packet_out_ack_streams (lsquic_packet_out_t *packet_out)
393{
394    struct packet_out_frec_iter pofi;
395    struct frame_rec *frec;
396    for (frec = lsquic_pofi_first(&pofi, packet_out); frec;
397                                                frec = lsquic_pofi_next(&pofi))
398        if ((1 << frec->fe_frame_type)
399                & (QUIC_FTBIT_STREAM|QUIC_FTBIT_CRYPTO|QUIC_FTBIT_RST_STREAM))
400            lsquic_stream_acked(frec->fe_stream, frec->fe_frame_type);
401}
402
403
404void
405lsquic_packet_out_zero_pad (lsquic_packet_out_t *packet_out)
406{
407    if (packet_out->po_n_alloc > packet_out->po_data_sz)
408    {
409        memset(packet_out->po_data + packet_out->po_data_sz, 0,
410                            packet_out->po_n_alloc - packet_out->po_data_sz);
411        packet_out->po_data_sz = packet_out->po_n_alloc;
412        packet_out->po_frame_types |= 1 << QUIC_FRAME_PADDING;
413    }
414}
415
416
417size_t
418lsquic_packet_out_mem_used (const struct lsquic_packet_out *packet_out)
419{
420    const struct frame_rec_arr *frec_arr;
421    size_t size;
422
423    size = 0;   /* The struct is allocated using malo */
424    if (packet_out->po_enc_data)
425        size += packet_out->po_enc_data_sz;
426    if (packet_out->po_data)
427        size += packet_out->po_n_alloc;
428    if (packet_out->po_nonce)
429        size += 32;
430
431    if (packet_out->po_flags & PO_FREC_ARR)
432        TAILQ_FOREACH(frec_arr, &packet_out->po_frecs.arr, next_stream_rec_arr)
433            size += sizeof(*frec_arr);
434
435    return size;
436}
437
438
439int
440lsquic_packet_out_turn_on_fin (struct lsquic_packet_out *packet_out,
441                               const struct parse_funcs *pf,
442                               const struct lsquic_stream *stream)
443{
444    struct packet_out_frec_iter pofi;
445    const struct frame_rec *frec;
446    struct stream_frame stream_frame;
447    uint64_t last_offset;
448    int len;
449
450    for (frec = lsquic_pofi_first(&pofi, packet_out); frec;
451                                                frec = lsquic_pofi_next(&pofi))
452        if (frec->fe_frame_type == QUIC_FRAME_STREAM
453            && frec->fe_stream == stream)
454        {
455            len = pf->pf_parse_stream_frame(packet_out->po_data + frec->fe_off,
456                                            frec->fe_len, &stream_frame);
457            assert(len >= 0);
458            if (len < 0)
459                return -1;
460            last_offset = stream_frame.data_frame.df_offset
461                        + stream_frame.data_frame.df_size;
462            if (last_offset == stream->tosend_off)
463            {
464                pf->pf_turn_on_fin(packet_out->po_data + frec->fe_off);
465                EV_LOG_UPDATED_STREAM_FRAME(
466                    lsquic_conn_log_cid(lsquic_stream_conn(stream)),
467                    pf, packet_out->po_data + frec->fe_off, frec->fe_len);
468                return 0;
469            }
470        }
471
472    return -1;
473}
474
475
476static unsigned
477offset_to_dcid (const struct lsquic_packet_out *packet_out)
478{
479    if (packet_out->po_header_type == HETY_NOT_SET)
480        return 1;
481    else
482    {
483        assert(!(packet_out->po_lflags & POL_GQUIC));
484        return 6;
485    }
486}
487
488
489/* Return true if DCIDs of the two packets are equal, false otherwise. */
490int
491lsquic_packet_out_equal_dcids (const struct lsquic_packet_out *a,
492                               const struct lsquic_packet_out *b)
493{
494    const int a_encrypted = !!(a->po_flags & PO_ENCRYPTED);
495    const int b_encrypted = !!(b->po_flags & PO_ENCRYPTED);
496    const unsigned char *dcids[2];
497    size_t sizes[2];
498
499    switch ((a_encrypted << 1) | b_encrypted)
500    {
501    case    (0           << 1) | 0:
502        return a->po_path == b->po_path;
503    case    (0           << 1) | 1:
504        dcids[0] = a->po_path->np_dcid.idbuf;
505        sizes[0] = a->po_path->np_dcid.len;
506        dcids[1] = b->po_enc_data + offset_to_dcid(b);
507        sizes[1] = b->po_dcid_len;
508        break;
509    case    (1           << 1) | 0:
510        dcids[0] = a->po_enc_data + offset_to_dcid(a);
511        sizes[0] = a->po_dcid_len;
512        dcids[1] = b->po_path->np_dcid.idbuf;
513        sizes[1] = b->po_path->np_dcid.len;
514        break;
515    default:
516        dcids[0] = a->po_enc_data + offset_to_dcid(a);
517        sizes[0] = a->po_dcid_len;
518        dcids[1] = b->po_enc_data + offset_to_dcid(b);
519        sizes[1] = b->po_dcid_len;
520        break;
521    }
522
523    return sizes[0] == sizes[1]
524        && 0 == memcmp(dcids[0], dcids[1], sizes[0]);
525}
526
527
528void
529lsquic_packet_out_pad_over (struct lsquic_packet_out *packet_out,
530                                                enum quic_ft_bit frame_types)
531{
532    struct packet_out_frec_iter pofi;
533    struct frame_rec *frec;
534
535    for (frec = lsquic_pofi_first(&pofi, packet_out); frec;
536                                                frec = lsquic_pofi_next(&pofi))
537    {
538        if ((1 << frec->fe_frame_type) & frame_types)
539        {
540            memset(packet_out->po_data + frec->fe_off, 0, frec->fe_len);
541            frec->fe_frame_type = QUIC_FRAME_PADDING;
542        }
543    }
544
545    packet_out->po_frame_types &= ~frame_types;
546}
547