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