/src/openssl/include/internal/ring_buf.h

Source
/*
 * Copyright 2022-2023 The OpenSSL Project Authors. All Rights Reserved.
 *
 * Licensed under the Apache License 2.0 (the "License").  You may not use
 * this file except in compliance with the License.  You can obtain a copy
 * in the file LICENSE in the source distribution or at
 * https://www.openssl.org/source/license.html
 */

#ifndef OSSL_INTERNAL_RING_BUF_H
#define OSSL_INTERNAL_RING_BUF_H
#pragma once

#include <assert.h>
#include <string.h>

#include <openssl/e_os2.h> /* For 'ossl_inline' */
#include <openssl/crypto.h>

#include "internal/safe_math.h"

/*
 * ==================================================================
 * Byte-wise ring buffer which supports pushing and popping blocks of multiple
 * bytes at a time. The logical offset of each byte for the purposes of a QUIC
 * stream is tracked. Bytes can be popped from the ring buffer in two stages;
 * first they are popped, and then they are culled. Bytes which have been popped
 * but not yet culled will not be overwritten, and can be restored.
 */
struct ring_buf {
    void *start;
    size_t alloc; /* size of buffer allocation in bytes */

    /*
     * Logical offset of the head (where we append to). This is the current size
     * of the QUIC stream. This increases monotonically.
     */
    uint64_t head_offset;

    /*
     * Logical offset of the cull tail. Data is no longer needed and is
     * deallocated as the cull tail advances, which occurs as data is
     * acknowledged. This increases monotonically.
     */
    uint64_t ctail_offset;
};

OSSL_SAFE_MATH_UNSIGNED(u64, uint64_t)

#define MAX_OFFSET (((uint64_t)1) << 62) /* QUIC-imposed limit */

static ossl_inline int ring_buf_init(struct ring_buf *r)
{
    r->start = NULL;
    r->alloc = 0;
    r->head_offset = r->ctail_offset = 0;
    return 1;
}

static ossl_inline void ring_buf_destroy(struct ring_buf *r, int cleanse)
{
    if (cleanse)
        OPENSSL_clear_free(r->start, r->alloc);
    else
        OPENSSL_free(r->start);
    r->start = NULL;
    r->alloc = 0;
}

static ossl_inline size_t ring_buf_used(struct ring_buf *r)
{
    return (size_t)(r->head_offset - r->ctail_offset);
}

static ossl_inline size_t ring_buf_avail(struct ring_buf *r)
{
    return r->alloc - ring_buf_used(r);
}

static ossl_inline int ring_buf_write_at(struct ring_buf *r,
    uint64_t logical_offset,
    const unsigned char *buf,
    size_t buf_len)
{
    size_t avail, idx, l;
    unsigned char *start = r->start;
    int i, err = 0;

    avail = ring_buf_avail(r);
    if (logical_offset < r->ctail_offset
        || safe_add_u64(logical_offset, buf_len, &err)
            > safe_add_u64(r->head_offset, avail, &err)
        || safe_add_u64(r->head_offset, buf_len, &err)
            > MAX_OFFSET
        || err)
        return 0;

    for (i = 0; buf_len > 0 && i < 2; ++i) {
        idx = logical_offset % r->alloc;
        l = r->alloc - idx;
        if (buf_len < l)
            l = buf_len;

        memcpy(start + idx, buf, l);
        if (r->head_offset < logical_offset + l)
            r->head_offset = logical_offset + l;

        logical_offset += l;
        buf += l;
        buf_len -= l;
    }

    assert(buf_len == 0);

    return 1;
}

static ossl_inline size_t ring_buf_push(struct ring_buf *r,
    const unsigned char *buf,
    size_t buf_len)
{
    size_t pushed = 0, avail, idx, l;
    unsigned char *start = r->start;

    for (;;) {
        avail = ring_buf_avail(r);
        if (buf_len > avail)
            buf_len = avail;

        if (buf_len > MAX_OFFSET - r->head_offset)
            buf_len = (size_t)(MAX_OFFSET - r->head_offset);

        if (buf_len == 0)
            break;

        idx = r->head_offset % r->alloc;
        l = r->alloc - idx;
        if (buf_len < l)
            l = buf_len;

        memcpy(start + idx, buf, l);
        r->head_offset += l;
        buf += l;
        buf_len -= l;
        pushed += l;
    }

    return pushed;
}

static ossl_inline const unsigned char *ring_buf_get_ptr(const struct ring_buf *r,
    uint64_t logical_offset,
    size_t *max_len)
{
    unsigned char *start = r->start;
    size_t idx;

    if (logical_offset >= r->head_offset || logical_offset < r->ctail_offset)
        return NULL;
    idx = logical_offset % r->alloc;
    *max_len = r->alloc - idx;
    return start + idx;
}

/*
 * Retrieves data out of the read side of the ring buffer starting at the given
 * logical offset. *buf is set to point to a contiguous span of bytes and
 * *buf_len is set to the number of contiguous bytes. After this function
 * returns, there may or may not be more bytes available at the logical offset
 * of (logical_offset + *buf_len) by calling this function again. If the logical
 * offset is out of the range retained by the ring buffer, returns 0, else
 * returns 1. A logical offset at the end of the range retained by the ring
 * buffer is not considered an error and is returned with a *buf_len of 0.
 *
 * The ring buffer state is not changed.
 */
static ossl_inline int ring_buf_get_buf_at(const struct ring_buf *r,
    uint64_t logical_offset,
    const unsigned char **buf,
    size_t *buf_len)
{
    const unsigned char *start = r->start;
    size_t idx, l;

    if (logical_offset > r->head_offset || logical_offset < r->ctail_offset)
        return 0;

    if (r->alloc == 0) {
        *buf = NULL;
        *buf_len = 0;
        return 1;
    }

    idx = logical_offset % r->alloc;
    l = (size_t)(r->head_offset - logical_offset);
    if (l > r->alloc - idx)
        l = r->alloc - idx;

    *buf = start + idx;
    *buf_len = l;
    return 1;
}

static ossl_inline void ring_buf_cpop_range(struct ring_buf *r,
    uint64_t start, uint64_t end,
    int cleanse)
{
    assert(end >= start);

    if (start > r->ctail_offset || end >= MAX_OFFSET)
        return;

    if (cleanse && r->alloc > 0 && end > r->ctail_offset) {
        size_t idx = r->ctail_offset % r->alloc;
        uint64_t cleanse_end = end + 1;
        size_t l;

        if (cleanse_end > r->head_offset)
            cleanse_end = r->head_offset;
        l = (size_t)(cleanse_end - r->ctail_offset);
        if (l > r->alloc - idx) {
            OPENSSL_cleanse((unsigned char *)r->start + idx, r->alloc - idx);
            l -= r->alloc - idx;
            idx = 0;
        }
        if (l > 0)
            OPENSSL_cleanse((unsigned char *)r->start + idx, l);
    }

    r->ctail_offset = end + 1;
    /* Allow culling unpushed data */
    if (r->head_offset < r->ctail_offset)
        r->head_offset = r->ctail_offset;
}

static ossl_inline int ring_buf_resize(struct ring_buf *r, size_t num_bytes,
    int cleanse)
{
    struct ring_buf rnew = { 0 };
    const unsigned char *src = NULL;
    size_t src_len = 0, copied = 0;

    if (num_bytes == r->alloc)
        return 1;

    if (num_bytes < ring_buf_used(r))
        return 0;

    rnew.start = OPENSSL_malloc(num_bytes);
    if (rnew.start == NULL)
        return 0;

    rnew.alloc = num_bytes;
    rnew.head_offset = r->head_offset - ring_buf_used(r);
    rnew.ctail_offset = rnew.head_offset;

    for (;;) {
        if (!ring_buf_get_buf_at(r, r->ctail_offset + copied, &src, &src_len)) {
            OPENSSL_free(rnew.start);
            return 0;
        }

        if (src_len == 0)
            break;

        if (ring_buf_push(&rnew, src, src_len) != src_len) {
            OPENSSL_free(rnew.start);
            return 0;
        }

        copied += src_len;
    }

    assert(rnew.head_offset == r->head_offset);
    rnew.ctail_offset = r->ctail_offset;

    ring_buf_destroy(r, cleanse);
    memcpy(r, &rnew, sizeof(*r));
    return 1;
}

#endif /* OSSL_INTERNAL_RING_BUF_H */

Coverage Report

Created: 2026-05-20 07:05

Line	Count	Source
1		/*
2		* Copyright 2022-2023 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_RING_BUF_H
11		#define OSSL_INTERNAL_RING_BUF_H
12		#pragma once
13
14		#include <assert.h>
15		#include <string.h>
16
17		#include <openssl/e_os2.h> /* For 'ossl_inline' */
18		#include <openssl/crypto.h>
19
20		#include "internal/safe_math.h"
21
22		/*
23		* ==================================================================
24		* Byte-wise ring buffer which supports pushing and popping blocks of multiple
25		* bytes at a time. The logical offset of each byte for the purposes of a QUIC
26		* stream is tracked. Bytes can be popped from the ring buffer in two stages;
27		* first they are popped, and then they are culled. Bytes which have been popped
28		* but not yet culled will not be overwritten, and can be restored.
29		*/
30		struct ring_buf {
31		void *start;
32		size_t alloc; /* size of buffer allocation in bytes */
33
34		/*
35		* Logical offset of the head (where we append to). This is the current size
36		* of the QUIC stream. This increases monotonically.
37		*/
38		uint64_t head_offset;
39
40		/*
41		* Logical offset of the cull tail. Data is no longer needed and is
42		* deallocated as the cull tail advances, which occurs as data is
43		* acknowledged. This increases monotonically.
44		*/
45		uint64_t ctail_offset;
46		};
47
48		OSSL_SAFE_MATH_UNSIGNED(u64, uint64_t)
49
50	0	#define MAX_OFFSET (((uint64_t)1) << 62) /* QUIC-imposed limit */
51
52		static ossl_inline int ring_buf_init(struct ring_buf *r)
53	0	{
54	0	r->start = NULL;
55	0	r->alloc = 0;
56	0	r->head_offset = r->ctail_offset = 0;
57	0	return 1;
58	0	} Unexecuted instantiation: quic_rstream.c:ring_buf_init Unexecuted instantiation: quic_sstream.c:ring_buf_init
59
60		static ossl_inline void ring_buf_destroy(struct ring_buf *r, int cleanse)
61	0	{
62	0	if (cleanse)
63	0	OPENSSL_clear_free(r->start, r->alloc);
64	0	else
65	0	OPENSSL_free(r->start);
66	0	r->start = NULL;
67	0	r->alloc = 0;
68	0	} Unexecuted instantiation: quic_rstream.c:ring_buf_destroy Unexecuted instantiation: quic_sstream.c:ring_buf_destroy
69
70		static ossl_inline size_t ring_buf_used(struct ring_buf *r)
71	0	{
72	0	return (size_t)(r->head_offset - r->ctail_offset);
73	0	} Unexecuted instantiation: quic_rstream.c:ring_buf_used Unexecuted instantiation: quic_sstream.c:ring_buf_used
74
75		static ossl_inline size_t ring_buf_avail(struct ring_buf *r)
76	0	{
77	0	return r->alloc - ring_buf_used(r);
78	0	} Unexecuted instantiation: quic_rstream.c:ring_buf_avail Unexecuted instantiation: quic_sstream.c:ring_buf_avail
79
80		static ossl_inline int ring_buf_write_at(struct ring_buf *r,
81		uint64_t logical_offset,
82		const unsigned char *buf,
83		size_t buf_len)
84	0	{
85	0	size_t avail, idx, l;
86	0	unsigned char *start = r->start;
87	0	int i, err = 0;
88
89	0	avail = ring_buf_avail(r);
90	0	if (logical_offset < r->ctail_offset
91	0	\|\| safe_add_u64(logical_offset, buf_len, &err)
92	0	> safe_add_u64(r->head_offset, avail, &err)
93	0	\|\| safe_add_u64(r->head_offset, buf_len, &err)
94	0	> MAX_OFFSET
95	0	\|\| err)
96	0	return 0;
97
98	0	for (i = 0; buf_len > 0 && i < 2; ++i) {
99	0	idx = logical_offset % r->alloc;
100	0	l = r->alloc - idx;
101	0	if (buf_len < l)
102	0	l = buf_len;
103
104	0	memcpy(start + idx, buf, l);
105	0	if (r->head_offset < logical_offset + l)
106	0	r->head_offset = logical_offset + l;
107
108	0	logical_offset += l;
109	0	buf += l;
110	0	buf_len -= l;
111	0	}
112
113	0	assert(buf_len == 0);
114
115	0	return 1;
116	0	} Unexecuted instantiation: quic_rstream.c:ring_buf_write_at Unexecuted instantiation: quic_sstream.c:ring_buf_write_at
117
118		static ossl_inline size_t ring_buf_push(struct ring_buf *r,
119		const unsigned char *buf,
120		size_t buf_len)
121	0	{
122	0	size_t pushed = 0, avail, idx, l;
123	0	unsigned char *start = r->start;
124
125	0	for (;;) {
126	0	avail = ring_buf_avail(r);
127	0	if (buf_len > avail)
128	0	buf_len = avail;
129
130	0	if (buf_len > MAX_OFFSET - r->head_offset)
131	0	buf_len = (size_t)(MAX_OFFSET - r->head_offset);
132
133	0	if (buf_len == 0)
134	0	break;
135
136	0	idx = r->head_offset % r->alloc;
137	0	l = r->alloc - idx;
138	0	if (buf_len < l)
139	0	l = buf_len;
140
141	0	memcpy(start + idx, buf, l);
142	0	r->head_offset += l;
143	0	buf += l;
144	0	buf_len -= l;
145	0	pushed += l;
146	0	}
147
148	0	return pushed;
149	0	} Unexecuted instantiation: quic_rstream.c:ring_buf_push Unexecuted instantiation: quic_sstream.c:ring_buf_push
150
151		static ossl_inline const unsigned char ring_buf_get_ptr(const struct ring_buf r,
152		uint64_t logical_offset,
153		size_t *max_len)
154	0	{
155	0	unsigned char *start = r->start;
156	0	size_t idx;
157
158	0	if (logical_offset >= r->head_offset \|\| logical_offset < r->ctail_offset)
159	0	return NULL;
160	0	idx = logical_offset % r->alloc;
161	0	*max_len = r->alloc - idx;
162	0	return start + idx;
163	0	} Unexecuted instantiation: quic_rstream.c:ring_buf_get_ptr Unexecuted instantiation: quic_sstream.c:ring_buf_get_ptr
164
165		/*
166		* Retrieves data out of the read side of the ring buffer starting at the given
167		* logical offset. *buf is set to point to a contiguous span of bytes and
168		* *buf_len is set to the number of contiguous bytes. After this function
169		* returns, there may or may not be more bytes available at the logical offset
170		* of (logical_offset + *buf_len) by calling this function again. If the logical
171		* offset is out of the range retained by the ring buffer, returns 0, else
172		* returns 1. A logical offset at the end of the range retained by the ring
173		* buffer is not considered an error and is returned with a *buf_len of 0.
174		*
175		* The ring buffer state is not changed.
176		*/
177		static ossl_inline int ring_buf_get_buf_at(const struct ring_buf *r,
178		uint64_t logical_offset,
179		const unsigned char **buf,
180		size_t *buf_len)
181	0	{
182	0	const unsigned char *start = r->start;
183	0	size_t idx, l;
184
185	0	if (logical_offset > r->head_offset \|\| logical_offset < r->ctail_offset)
186	0	return 0;
187
188	0	if (r->alloc == 0) {
189	0	*buf = NULL;
190	0	*buf_len = 0;
191	0	return 1;
192	0	}
193
194	0	idx = logical_offset % r->alloc;
195	0	l = (size_t)(r->head_offset - logical_offset);
196	0	if (l > r->alloc - idx)
197	0	l = r->alloc - idx;
198
199	0	*buf = start + idx;
200	0	*buf_len = l;
201	0	return 1;
202	0	} Unexecuted instantiation: quic_rstream.c:ring_buf_get_buf_at Unexecuted instantiation: quic_sstream.c:ring_buf_get_buf_at
203
204		static ossl_inline void ring_buf_cpop_range(struct ring_buf *r,
205		uint64_t start, uint64_t end,
206		int cleanse)
207	0	{
208	0	assert(end >= start);
209
210	0	if (start > r->ctail_offset \|\| end >= MAX_OFFSET)
211	0	return;
212
213	0	if (cleanse && r->alloc > 0 && end > r->ctail_offset) {
214	0	size_t idx = r->ctail_offset % r->alloc;
215	0	uint64_t cleanse_end = end + 1;
216	0	size_t l;
217
218	0	if (cleanse_end > r->head_offset)
219	0	cleanse_end = r->head_offset;
220	0	l = (size_t)(cleanse_end - r->ctail_offset);
221	0	if (l > r->alloc - idx) {
222	0	OPENSSL_cleanse((unsigned char *)r->start + idx, r->alloc - idx);
223	0	l -= r->alloc - idx;
224	0	idx = 0;
225	0	}
226	0	if (l > 0)
227	0	OPENSSL_cleanse((unsigned char *)r->start + idx, l);
228	0	}
229
230	0	r->ctail_offset = end + 1;
231		/* Allow culling unpushed data */
232	0	if (r->head_offset < r->ctail_offset)
233	0	r->head_offset = r->ctail_offset;
234	0	} Unexecuted instantiation: quic_rstream.c:ring_buf_cpop_range Unexecuted instantiation: quic_sstream.c:ring_buf_cpop_range
235
236		static ossl_inline int ring_buf_resize(struct ring_buf *r, size_t num_bytes,
237		int cleanse)
238	0	{
239	0	struct ring_buf rnew = { 0 };
240	0	const unsigned char *src = NULL;
241	0	size_t src_len = 0, copied = 0;
242
243	0	if (num_bytes == r->alloc)
244	0	return 1;
245
246	0	if (num_bytes < ring_buf_used(r))
247	0	return 0;
248
249	0	rnew.start = OPENSSL_malloc(num_bytes);
250	0	if (rnew.start == NULL)
251	0	return 0;
252
253	0	rnew.alloc = num_bytes;
254	0	rnew.head_offset = r->head_offset - ring_buf_used(r);
255	0	rnew.ctail_offset = rnew.head_offset;
256
257	0	for (;;) {
258	0	if (!ring_buf_get_buf_at(r, r->ctail_offset + copied, &src, &src_len)) {
259	0	OPENSSL_free(rnew.start);
260	0	return 0;
261	0	}
262
263	0	if (src_len == 0)
264	0	break;
265
266	0	if (ring_buf_push(&rnew, src, src_len) != src_len) {
267	0	OPENSSL_free(rnew.start);
268	0	return 0;
269	0	}
270
271	0	copied += src_len;
272	0	}
273
274	0	assert(rnew.head_offset == r->head_offset);
275	0	rnew.ctail_offset = r->ctail_offset;
276
277	0	ring_buf_destroy(r, cleanse);
278	0	memcpy(r, &rnew, sizeof(*r));
279	0	return 1;
280	0	} Unexecuted instantiation: quic_rstream.c:ring_buf_resize Unexecuted instantiation: quic_sstream.c:ring_buf_resize
281
282		#endif /* OSSL_INTERNAL_RING_BUF_H */