1 /* $OpenBSD: bio_chain.c,v 1.16 2023/08/07 11:00:54 tb Exp $ */
2 /*
3 * Copyright (c) 2022 Theo Buehler <tb@openbsd.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18 #include <err.h>
19 #include <stdio.h>
20 #include <string.h>
21
22 #include <openssl/bio.h>
23
24 #include "bio_local.h"
25
26 #ifndef nitems
27 #define nitems(_a) (sizeof((_a)) / sizeof((_a)[0]))
28 #endif
29
30 #define CHAIN_POP_LEN 5
31 #define LINK_CHAIN_A_LEN 8
32 #define LINK_CHAIN_B_LEN 5
33
34 static BIO *
BIO_prev(BIO * bio)35 BIO_prev(BIO *bio)
36 {
37 if (bio == NULL)
38 return NULL;
39
40 return bio->prev_bio;
41 }
42
43 static void bio_chain_destroy(BIO **, size_t);
44
45 static int
bio_chain_create(const BIO_METHOD * meth,BIO * chain[],size_t len)46 bio_chain_create(const BIO_METHOD *meth, BIO *chain[], size_t len)
47 {
48 BIO *prev;
49 size_t i;
50
51 memset(chain, 0, len * sizeof(BIO *));
52
53 prev = NULL;
54 for (i = 0; i < len; i++) {
55 if ((chain[i] = BIO_new(meth)) == NULL) {
56 fprintf(stderr, "BIO_new failed\n");
57 goto err;
58 }
59 if ((prev = BIO_push(prev, chain[i])) == NULL) {
60 fprintf(stderr, "BIO_push failed\n");
61 goto err;
62 }
63 }
64
65 return 1;
66
67 err:
68 bio_chain_destroy(chain, len);
69
70 return 0;
71 }
72
73 static void
bio_chain_destroy(BIO * chain[],size_t len)74 bio_chain_destroy(BIO *chain[], size_t len)
75 {
76 size_t i;
77
78 for (i = 0; i < len; i++)
79 BIO_free(chain[i]);
80
81 memset(chain, 0, len * sizeof(BIO *));
82 }
83
84 static int
bio_chain_pop_test(void)85 bio_chain_pop_test(void)
86 {
87 BIO *bio[CHAIN_POP_LEN];
88 BIO *prev, *next;
89 size_t i, j;
90 int failed = 1;
91
92 for (i = 0; i < nitems(bio); i++) {
93 memset(bio, 0, sizeof(bio));
94 prev = NULL;
95
96 if (!bio_chain_create(BIO_s_null(), bio, nitems(bio)))
97 goto err;
98
99 /* Check that the doubly-linked list was set up as expected. */
100 if (BIO_prev(bio[0]) != NULL) {
101 fprintf(stderr,
102 "i = %zu: first BIO has predecessor\n", i);
103 goto err;
104 }
105 if (BIO_next(bio[nitems(bio) - 1]) != NULL) {
106 fprintf(stderr, "i = %zu: last BIO has successor\n", i);
107 goto err;
108 }
109 for (j = 0; j < nitems(bio); j++) {
110 if (j > 0) {
111 if (BIO_prev(bio[j]) != bio[j - 1]) {
112 fprintf(stderr, "i = %zu: "
113 "BIO_prev(bio[%zu]) != bio[%zu]\n",
114 i, j, j - 1);
115 goto err;
116 }
117 }
118 if (j < nitems(bio) - 1) {
119 if (BIO_next(bio[j]) != bio[j + 1]) {
120 fprintf(stderr, "i = %zu: "
121 "BIO_next(bio[%zu]) != bio[%zu]\n",
122 i, j, j + 1);
123 goto err;
124 }
125 }
126 }
127
128 /* Drop the ith bio from the chain. */
129 next = BIO_pop(bio[i]);
130
131 if (BIO_prev(bio[i]) != NULL || BIO_next(bio[i]) != NULL) {
132 fprintf(stderr,
133 "BIO_pop() didn't isolate bio[%zu]\n", i);
134 goto err;
135 }
136
137 if (i < nitems(bio) - 1) {
138 if (next != bio[i + 1]) {
139 fprintf(stderr, "BIO_pop(bio[%zu]) did not "
140 "return bio[%zu]\n", i, i + 1);
141 goto err;
142 }
143 } else {
144 if (next != NULL) {
145 fprintf(stderr, "i = %zu: "
146 "BIO_pop(last) != NULL\n", i);
147 goto err;
148 }
149 }
150
151 /*
152 * Walk the remainder of the chain and see if the doubly linked
153 * list checks out.
154 */
155 if (i == 0) {
156 prev = bio[1];
157 j = 2;
158 } else {
159 prev = bio[0];
160 j = 1;
161 }
162
163 for (; j < nitems(bio); j++) {
164 if (j == i)
165 continue;
166 if (BIO_next(prev) != bio[j]) {
167 fprintf(stderr, "i = %zu, j = %zu: "
168 "BIO_next(prev) != bio[%zu]\n", i, j, j);
169 goto err;
170 }
171 if (BIO_prev(bio[j]) != prev) {
172 fprintf(stderr, "i = %zu, j = %zu: "
173 "BIO_prev(bio[%zu]) != prev\n", i, j, j);
174 goto err;
175 }
176 prev = bio[j];
177 }
178
179 if (BIO_next(prev) != NULL) {
180 fprintf(stderr, "i = %zu: BIO_next(prev) != NULL\n", i);
181 goto err;
182 }
183
184 bio_chain_destroy(bio, nitems(bio));
185 }
186
187 failed = 0;
188
189 err:
190 bio_chain_destroy(bio, nitems(bio));
191
192 return failed;
193 }
194
195 static void
walk(BIO * (* step)(BIO *),BIO * start,BIO ** end,size_t * len)196 walk(BIO *(*step)(BIO *), BIO *start, BIO **end, size_t *len)
197 {
198 BIO *current = NULL;
199 BIO *next = start;
200
201 *len = 0;
202 while (next != NULL) {
203 current = next;
204 next = step(current);
205 (*len)++;
206 }
207 *end = current;
208 }
209
210 static int
walk_report(BIO * last,BIO * expected_last,size_t len,size_t expected_len,size_t i,size_t j,const char * fn,const char * description,const char * direction,const char * last_name)211 walk_report(BIO *last, BIO *expected_last, size_t len, size_t expected_len,
212 size_t i, size_t j, const char *fn, const char *description,
213 const char *direction, const char *last_name)
214 {
215 if (last != expected_last) {
216 fprintf(stderr, "%s case (%zu, %zu) %s %s has unexpected %s\n",
217 fn, i, j, description, direction, last_name);
218 return 0;
219 }
220
221 if (len != expected_len) {
222 fprintf(stderr, "%s case (%zu, %zu) %s %s want %zu, got %zu\n",
223 fn, i, j, description, direction, expected_len, len);
224 return 0;
225 }
226
227 return 1;
228 }
229
230 static int
walk_forward(BIO * start,BIO * expected_end,size_t expected_len,size_t i,size_t j,const char * fn,const char * description)231 walk_forward(BIO *start, BIO *expected_end, size_t expected_len,
232 size_t i, size_t j, const char *fn, const char *description)
233 {
234 BIO *end;
235 size_t len;
236
237 walk(BIO_next, start, &end, &len);
238
239 return walk_report(end, expected_end, len, expected_len,
240 i, j, fn, description, "forward", "end");
241 }
242
243 static int
walk_backward(BIO * expected_start,BIO * end,size_t expected_len,size_t i,size_t j,const char * fn,const char * description)244 walk_backward(BIO *expected_start, BIO *end, size_t expected_len,
245 size_t i, size_t j, const char *fn, const char *description)
246 {
247 BIO *start;
248 size_t len;
249
250 walk(BIO_prev, end, &start, &len);
251
252 return walk_report(start, expected_start, len, expected_len,
253 i, j, fn, description, "backward", "start");
254 }
255
256 static int
check_chain(BIO * start,BIO * end,size_t expected_len,size_t i,size_t j,const char * fn,const char * description)257 check_chain(BIO *start, BIO *end, size_t expected_len, size_t i, size_t j,
258 const char *fn, const char *description)
259 {
260 if (!walk_forward(start, end, expected_len, i, j, fn, description))
261 return 0;
262
263 if (!walk_backward(start, end, expected_len, i, j, fn, description))
264 return 0;
265
266 return 1;
267 }
268
269 /*
270 * Link two linear chains of BIOs A[] and B[] together using either
271 * BIO_push(A[i], B[j]) or BIO_set_next(A[i], B[j]).
272 *
273 * BIO_push() first walks the chain A[] to its end and then appends the tail
274 * of chain B[] starting at B[j]. If j > 0, we get two chains
275 *
276 * A[0] -- ... -- A[nitems(A) - 1] -- B[j] -- ... -- B[nitems(B) - 1]
277 * `- link created by BIO_push()
278 * B[0] -- ... -- B[j-1]
279 * |<-- oldhead -->|
280 *
281 * of lengths nitems(A) + nitems(B) - j and j, respectively.
282 * If j == 0, the second chain (oldhead) is empty. One quirk of BIO_push() is
283 * that the outcome of BIO_push(A[i], B[j]) apart from the return value is
284 * independent of i.
285 *
286 * Prior to bio_lib.c r1.41, BIO_push(A[i], B[j]) would fail to dissociate the
287 * two chains and leave B[j] with two parents for 0 < j < nitems(B).
288 * B[j]->prev_bio would point at A[nitems(A) - 1], while both B[j - 1] and
289 * A[nitems(A) - 1] would point at B[j]. In particular, BIO_free_all(A[0])
290 * followed by BIO_free_all(B[0]) results in a double free of B[j].
291 *
292 * The result for BIO_set_next() is different: three chains are created.
293 *
294 * |--- oldtail -->
295 * ... -- A[i-1] -- A[i] -- A[i+1] -- ...
296 * \
297 * \ link created by BIO_set_next()
298 * --- oldhead -->| \
299 * ... -- B[j-1] -- B[j] -- B[j+1] -- ...
300 *
301 * After creating a new link, the new chain has length i + 1 + nitems(B) - j,
302 * oldtail has length nitems(A) - i - 1 and oldhead has length j.
303 *
304 * Prior to bio_lib.c r1.40, BIO_set_next(A[i], B[j]) would result in both A[i]
305 * and B[j - 1] pointing at B[j] while B[j] would point back at A[i]. Calling
306 * BIO_free_all(A[0]) and BIO_free_all(B[0]) results in a double free of B[j].
307 *
308 * XXX: Should check that the callback is called on BIO_push() as expected.
309 */
310
311 static int
link_chains_at(size_t i,size_t j,int use_bio_push)312 link_chains_at(size_t i, size_t j, int use_bio_push)
313 {
314 const char *fn = use_bio_push ? "BIO_push" : "BIO_set_next";
315 BIO *A[LINK_CHAIN_A_LEN], *B[LINK_CHAIN_B_LEN];
316 BIO *new_start, *new_end;
317 BIO *oldhead_start, *oldhead_end, *oldtail_start, *oldtail_end;
318 size_t new_len, oldhead_len, oldtail_len;
319 int failed = 1;
320
321 memset(A, 0, sizeof(A));
322 memset(B, 0, sizeof(B));
323
324 if (i >= nitems(A) || j >= nitems(B))
325 goto err;
326
327 /* Create two linear chains of BIOs. */
328 if (!bio_chain_create(BIO_s_null(), A, nitems(A)))
329 goto err;
330 if (!bio_chain_create(BIO_s_null(), B, nitems(B)))
331 goto err;
332
333 /*
334 * Set our expectations. ... it's complicated.
335 */
336
337 new_start = A[0];
338 new_end = B[nitems(B) - 1];
339 /* new_len depends on use_bio_push. It is set a few lines down. */
340
341 oldhead_start = B[0];
342 oldhead_end = BIO_prev(B[j]);
343 oldhead_len = j;
344
345 /* If we push B[0] or set next to B[0], the oldhead chain is empty. */
346 if (j == 0) {
347 oldhead_start = NULL;
348 oldhead_end = NULL;
349 oldhead_len = 0;
350 }
351
352 if (use_bio_push) {
353 new_len = nitems(A) + nitems(B) - j;
354
355 /* oldtail doesn't exist in the BIO_push() case. */
356 oldtail_start = NULL;
357 oldtail_end = NULL;
358 oldtail_len = 0;
359 } else {
360 new_len = i + 1 + nitems(B) - j;
361
362 oldtail_start = BIO_next(A[i]);
363 oldtail_end = A[nitems(A) - 1];
364 oldtail_len = nitems(A) - i - 1;
365
366 /* If we set next on end of A[], the oldtail chain is empty. */
367 if (i == nitems(A) - 1) {
368 oldtail_start = NULL;
369 oldtail_end = NULL;
370 oldtail_len = 0;
371 }
372 }
373
374 /* The two chains A[] and B[] are split into three disjoint pieces. */
375 if (nitems(A) + nitems(B) != new_len + oldtail_len + oldhead_len) {
376 fprintf(stderr, "%s case (%zu, %zu) inconsistent lengths: "
377 "%zu + %zu != %zu + %zu + %zu\n", fn, i, j,
378 nitems(A), nitems(B), new_len, oldtail_len, oldhead_len);
379 goto err;
380 }
381
382 /*
383 * Now actually push or set next.
384 */
385
386 if (use_bio_push) {
387 if (BIO_push(A[i], B[j]) != A[i]) {
388 fprintf(stderr, "BIO_push(A[%zu], B[%zu]) != A[%zu]\n",
389 i, j, i);
390 goto err;
391 }
392 } else {
393 BIO_set_next(A[i], B[j]);
394 }
395
396 /*
397 * Check that all the chains match our expectations.
398 */
399
400 if (!check_chain(new_start, new_end, new_len, i, j, fn, "new chain"))
401 goto err;
402
403 if (!check_chain(oldhead_start, oldhead_end, oldhead_len, i, j, fn,
404 "oldhead"))
405 goto err;
406
407 if (!check_chain(oldtail_start, oldtail_end, oldtail_len, i, j, fn,
408 "oldtail"))
409 goto err;
410
411 /*
412 * All sanity checks passed. We can now free the chains
413 * with the BIO API without risk of leaks or double frees.
414 */
415
416 BIO_free_all(new_start);
417 BIO_free_all(oldhead_start);
418 BIO_free_all(oldtail_start);
419
420 memset(A, 0, sizeof(A));
421 memset(B, 0, sizeof(B));
422
423 failed = 0;
424
425 err:
426 bio_chain_destroy(A, nitems(A));
427 bio_chain_destroy(B, nitems(B));
428
429 return failed;
430 }
431
432 static int
link_chains(int use_bio_push)433 link_chains(int use_bio_push)
434 {
435 size_t i, j;
436 int failure = 0;
437
438 for (i = 0; i < LINK_CHAIN_A_LEN; i++) {
439 for (j = 0; j < LINK_CHAIN_B_LEN; j++) {
440 failure |= link_chains_at(i, j, use_bio_push);
441 }
442 }
443
444 return failure;
445 }
446
447 static int
bio_push_link_test(void)448 bio_push_link_test(void)
449 {
450 int use_bio_push = 1;
451
452 return link_chains(use_bio_push);
453 }
454
455 static int
bio_set_next_link_test(void)456 bio_set_next_link_test(void)
457 {
458 int use_bio_push = 0;
459
460 return link_chains(use_bio_push);
461 }
462
463 static long
dup_leak_cb(BIO * bio,int cmd,const char * argp,int argi,long argl,long ret)464 dup_leak_cb(BIO *bio, int cmd, const char *argp, int argi, long argl, long ret)
465 {
466 if (argi == BIO_CTRL_DUP)
467 return 0;
468
469 return ret;
470 }
471
472 static int
bio_dup_chain_leak(void)473 bio_dup_chain_leak(void)
474 {
475 BIO *bio[CHAIN_POP_LEN];
476 BIO *dup;
477 int failed = 1;
478
479 if (!bio_chain_create(BIO_s_null(), bio, nitems(bio)))
480 goto err;
481
482 if ((dup = BIO_dup_chain(bio[0])) == NULL) {
483 fprintf(stderr, "BIO_set_callback() failed\n");
484 goto err;
485 }
486
487 BIO_set_callback(bio[CHAIN_POP_LEN - 1], dup_leak_cb);
488
489 BIO_free_all(dup);
490 if ((dup = BIO_dup_chain(bio[0])) != NULL) {
491 fprintf(stderr, "BIO_dup_chain() succeeded unexpectedly\n");
492 BIO_free_all(dup);
493 goto err;
494 }
495
496 failed = 0;
497
498 err:
499 bio_chain_destroy(bio, nitems(bio));
500
501 return failed;
502 }
503
504 int
main(int argc,char ** argv)505 main(int argc, char **argv)
506 {
507 int failed = 0;
508
509 failed |= bio_chain_pop_test();
510 failed |= bio_push_link_test();
511 failed |= bio_set_next_link_test();
512 failed |= bio_dup_chain_leak();
513
514 return failed;
515 }
516