2 * Copyright 2022-2023 The OpenSSL Project Authors. All Rights Reserved.
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
10 #include "internal/quic_stream.h"
11 #include "internal/uint_set.h"
12 #include "internal/common.h"
13 #include "internal/ring_buf.h"
16 * ==================================================================
19 struct quic_sstream_st
{
20 struct ring_buf ring_buf
;
23 * Any logical byte in the stream is in one of these states:
25 * - NEW: The byte has not yet been transmitted, or has been lost and is
26 * in need of retransmission.
28 * - IN_FLIGHT: The byte has been transmitted but is awaiting
29 * acknowledgement. We continue to store the data in case we return
32 * - ACKED: The byte has been acknowledged and we can cease storing it.
33 * We do not necessarily cull it immediately, so there may be a delay
34 * between reaching the ACKED state and the buffer space actually being
37 * A logical byte in the stream is
39 * - in the NEW state if it is in new_set;
40 * - is in the ACKED state if it is in acked_set
41 * (and may or may not have been culled);
42 * - is in the IN_FLIGHT state otherwise.
44 * Invariant: No logical byte is ever in both new_set and acked_set.
46 UINT_SET new_set
, acked_set
;
49 * The current size of the stream is ring_buf.head_offset. If
50 * have_final_size is true, this is also the final size of the stream.
52 unsigned int have_final_size
: 1;
53 unsigned int sent_final_size
: 1;
54 unsigned int acked_final_size
: 1;
55 unsigned int cleanse
: 1;
58 static void qss_cull(QUIC_SSTREAM
*qss
);
60 QUIC_SSTREAM
*ossl_quic_sstream_new(size_t init_buf_size
)
64 qss
= OPENSSL_zalloc(sizeof(QUIC_SSTREAM
));
68 ring_buf_init(&qss
->ring_buf
);
69 if (!ring_buf_resize(&qss
->ring_buf
, init_buf_size
, 0)) {
70 ring_buf_destroy(&qss
->ring_buf
, 0);
75 ossl_uint_set_init(&qss
->new_set
);
76 ossl_uint_set_init(&qss
->acked_set
);
80 void ossl_quic_sstream_free(QUIC_SSTREAM
*qss
)
85 ossl_uint_set_destroy(&qss
->new_set
);
86 ossl_uint_set_destroy(&qss
->acked_set
);
87 ring_buf_destroy(&qss
->ring_buf
, qss
->cleanse
);
91 int ossl_quic_sstream_get_stream_frame(QUIC_SSTREAM
*qss
,
93 OSSL_QUIC_FRAME_STREAM
*hdr
,
97 size_t num_iov_
= 0, src_len
= 0, total_len
= 0, i
;
99 const unsigned char *src
= NULL
;
100 UINT_SET_ITEM
*range
= ossl_list_uint_set_head(&qss
->new_set
);
105 for (i
= 0; i
< skip
&& range
!= NULL
; ++i
)
106 range
= ossl_list_uint_set_next(range
);
110 /* Don't return FIN for infinitely increasing skip */
113 /* No new bytes to send, but we might have a FIN */
114 if (!qss
->have_final_size
|| qss
->sent_final_size
)
117 hdr
->offset
= qss
->ring_buf
.head_offset
;
125 * We can only send a contiguous range of logical bytes in a single
126 * stream frame, so limit ourselves to the range of the first set entry.
128 * Set entries never have 'adjacent' entries so we don't have to worry
131 max_len
= range
->range
.end
- range
->range
.start
+ 1;
134 if (total_len
>= max_len
)
137 if (!ring_buf_get_buf_at(&qss
->ring_buf
,
138 range
->range
.start
+ total_len
,
147 if (total_len
+ src_len
> max_len
)
148 src_len
= (size_t)(max_len
- total_len
);
150 iov
[num_iov_
].buf
= src
;
151 iov
[num_iov_
].buf_len
= src_len
;
153 total_len
+= src_len
;
157 hdr
->offset
= range
->range
.start
;
158 hdr
->len
= total_len
;
159 hdr
->is_fin
= qss
->have_final_size
160 && hdr
->offset
+ hdr
->len
== qss
->ring_buf
.head_offset
;
166 int ossl_quic_sstream_has_pending(QUIC_SSTREAM
*qss
)
168 OSSL_QUIC_FRAME_STREAM shdr
;
169 OSSL_QTX_IOVEC iov
[2];
170 size_t num_iov
= OSSL_NELEM(iov
);
172 return ossl_quic_sstream_get_stream_frame(qss
, 0, &shdr
, iov
, &num_iov
);
175 uint64_t ossl_quic_sstream_get_cur_size(QUIC_SSTREAM
*qss
)
177 return qss
->ring_buf
.head_offset
;
180 int ossl_quic_sstream_mark_transmitted(QUIC_SSTREAM
*qss
,
189 if (!ossl_uint_set_remove(&qss
->new_set
, &r
))
195 int ossl_quic_sstream_mark_transmitted_fin(QUIC_SSTREAM
*qss
,
199 * We do not really need final_size since we already know the size of the
200 * stream, but this serves as a sanity check.
202 if (!qss
->have_final_size
|| final_size
!= qss
->ring_buf
.head_offset
)
205 qss
->sent_final_size
= 1;
209 int ossl_quic_sstream_mark_lost(QUIC_SSTREAM
*qss
,
218 * We lost a range of stream data bytes, so reinsert them into the new set,
219 * so that they are returned once more by ossl_quic_sstream_get_stream_frame.
221 if (!ossl_uint_set_insert(&qss
->new_set
, &r
))
227 int ossl_quic_sstream_mark_lost_fin(QUIC_SSTREAM
*qss
)
229 if (qss
->acked_final_size
)
230 /* Does not make sense to lose a FIN after it has been ACKed */
233 /* FIN was lost, so we need to transmit it again. */
234 qss
->sent_final_size
= 0;
238 int ossl_quic_sstream_mark_acked(QUIC_SSTREAM
*qss
,
246 if (!ossl_uint_set_insert(&qss
->acked_set
, &r
))
253 int ossl_quic_sstream_mark_acked_fin(QUIC_SSTREAM
*qss
)
255 if (!qss
->have_final_size
)
256 /* Cannot ack final size before we have a final size */
259 qss
->acked_final_size
= 1;
263 void ossl_quic_sstream_fin(QUIC_SSTREAM
*qss
)
265 if (qss
->have_final_size
)
268 qss
->have_final_size
= 1;
271 int ossl_quic_sstream_get_final_size(QUIC_SSTREAM
*qss
, uint64_t *final_size
)
273 if (!qss
->have_final_size
)
276 if (final_size
!= NULL
)
277 *final_size
= qss
->ring_buf
.head_offset
;
282 int ossl_quic_sstream_append(QUIC_SSTREAM
*qss
,
283 const unsigned char *buf
,
287 size_t l
, consumed_
= 0;
289 struct ring_buf old_ring_buf
= qss
->ring_buf
;
291 if (qss
->have_final_size
) {
297 * Note: It is assumed that ossl_quic_sstream_append will be called during a
298 * call to e.g. SSL_write and this function is therefore designed to support
299 * such semantics. In particular, the buffer pointed to by buf is only
300 * assumed to be valid for the duration of this call, therefore we must copy
301 * the data here. We will later copy-and-encrypt the data during packet
302 * encryption, so this is a two-copy design. Supporting a one-copy design in
303 * the future will require applications to use a different kind of API.
304 * Supporting such changes in future will require corresponding enhancements
307 while (buf_len
> 0) {
308 l
= ring_buf_push(&qss
->ring_buf
, buf
, buf_len
);
318 r
.start
= old_ring_buf
.head_offset
;
319 r
.end
= r
.start
+ consumed_
- 1;
320 assert(r
.end
+ 1 == qss
->ring_buf
.head_offset
);
321 if (!ossl_uint_set_insert(&qss
->new_set
, &r
)) {
322 qss
->ring_buf
= old_ring_buf
;
328 *consumed
= consumed_
;
332 static void qss_cull(QUIC_SSTREAM
*qss
)
334 UINT_SET_ITEM
*h
= ossl_list_uint_set_head(&qss
->acked_set
);
337 * Potentially cull data from our ring buffer. This can happen once data has
338 * been ACKed and we know we are never going to have to transmit it again.
340 * Since we use a ring buffer design for simplicity, we cannot cull byte n +
341 * k (for k > 0) from the ring buffer until byte n has also been culled.
342 * This means if parts of the stream get acknowledged out of order we might
343 * keep around some data we technically don't need to for a while. The
344 * impact of this is likely to be small and limited to quite a short
345 * duration, and doesn't justify the use of a more complex design.
349 * We only need to check the first range entry in the integer set because we
350 * can only cull contiguous areas at the start of the ring buffer anyway.
353 ring_buf_cpop_range(&qss
->ring_buf
, h
->range
.start
, h
->range
.end
,
357 int ossl_quic_sstream_set_buffer_size(QUIC_SSTREAM
*qss
, size_t num_bytes
)
359 return ring_buf_resize(&qss
->ring_buf
, num_bytes
, qss
->cleanse
);
362 size_t ossl_quic_sstream_get_buffer_size(QUIC_SSTREAM
*qss
)
364 return qss
->ring_buf
.alloc
;
367 size_t ossl_quic_sstream_get_buffer_used(QUIC_SSTREAM
*qss
)
369 return ring_buf_used(&qss
->ring_buf
);
372 size_t ossl_quic_sstream_get_buffer_avail(QUIC_SSTREAM
*qss
)
374 return ring_buf_avail(&qss
->ring_buf
);
377 int ossl_quic_sstream_is_totally_acked(QUIC_SSTREAM
*qss
)
382 if ((qss
->have_final_size
&& !qss
->acked_final_size
)
383 || ossl_list_uint_set_num(&qss
->acked_set
) != 1)
386 r
= ossl_list_uint_set_head(&qss
->acked_set
)->range
;
387 cur_size
= qss
->ring_buf
.head_offset
;
390 * The invariants of UINT_SET guarantee a single list element if we have a
391 * single contiguous range, which is what we should have if everything has
394 assert(r
.end
+ 1 <= cur_size
);
395 return r
.start
== 0 && r
.end
+ 1 == cur_size
;
398 void ossl_quic_sstream_adjust_iov(size_t len
,
402 size_t running
= 0, i
, iovlen
;
404 for (i
= 0, running
= 0; i
< num_iov
; ++i
) {
405 iovlen
= iov
[i
].buf_len
;
409 else if (running
+ iovlen
> len
)
410 iov
[i
].buf_len
= len
- running
;
416 void ossl_quic_sstream_set_cleanse(QUIC_SSTREAM
*qss
, int cleanse
)
418 qss
->cleanse
= cleanse
;