xref: /openbsd/regress/lib/libcrypto/bio/bio_chain.c (revision 3bef86f7) 
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 *
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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