/* $OpenBSD: bio_chain.c,v 1.16 2023/08/07 11:00:54 tb Exp $ */ /* * Copyright (c) 2022 Theo Buehler * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include #include #include #include #include "bio_local.h" #ifndef nitems #define nitems(_a) (sizeof((_a)) / sizeof((_a)[0])) #endif #define CHAIN_POP_LEN 5 #define LINK_CHAIN_A_LEN 8 #define LINK_CHAIN_B_LEN 5 static BIO * BIO_prev(BIO *bio) { if (bio == NULL) return NULL; return bio->prev_bio; } static void bio_chain_destroy(BIO **, size_t); static int bio_chain_create(const BIO_METHOD *meth, BIO *chain[], size_t len) { BIO *prev; size_t i; memset(chain, 0, len * sizeof(BIO *)); prev = NULL; for (i = 0; i < len; i++) { if ((chain[i] = BIO_new(meth)) == NULL) { fprintf(stderr, "BIO_new failed\n"); goto err; } if ((prev = BIO_push(prev, chain[i])) == NULL) { fprintf(stderr, "BIO_push failed\n"); goto err; } } return 1; err: bio_chain_destroy(chain, len); return 0; } static void bio_chain_destroy(BIO *chain[], size_t len) { size_t i; for (i = 0; i < len; i++) BIO_free(chain[i]); memset(chain, 0, len * sizeof(BIO *)); } static int bio_chain_pop_test(void) { BIO *bio[CHAIN_POP_LEN]; BIO *prev, *next; size_t i, j; int failed = 1; for (i = 0; i < nitems(bio); i++) { memset(bio, 0, sizeof(bio)); prev = NULL; if (!bio_chain_create(BIO_s_null(), bio, nitems(bio))) goto err; /* Check that the doubly-linked list was set up as expected. */ if (BIO_prev(bio[0]) != NULL) { fprintf(stderr, "i = %zu: first BIO has predecessor\n", i); goto err; } if (BIO_next(bio[nitems(bio) - 1]) != NULL) { fprintf(stderr, "i = %zu: last BIO has successor\n", i); goto err; } for (j = 0; j < nitems(bio); j++) { if (j > 0) { if (BIO_prev(bio[j]) != bio[j - 1]) { fprintf(stderr, "i = %zu: " "BIO_prev(bio[%zu]) != bio[%zu]\n", i, j, j - 1); goto err; } } if (j < nitems(bio) - 1) { if (BIO_next(bio[j]) != bio[j + 1]) { fprintf(stderr, "i = %zu: " "BIO_next(bio[%zu]) != bio[%zu]\n", i, j, j + 1); goto err; } } } /* Drop the ith bio from the chain. */ next = BIO_pop(bio[i]); if (BIO_prev(bio[i]) != NULL || BIO_next(bio[i]) != NULL) { fprintf(stderr, "BIO_pop() didn't isolate bio[%zu]\n", i); goto err; } if (i < nitems(bio) - 1) { if (next != bio[i + 1]) { fprintf(stderr, "BIO_pop(bio[%zu]) did not " "return bio[%zu]\n", i, i + 1); goto err; } } else { if (next != NULL) { fprintf(stderr, "i = %zu: " "BIO_pop(last) != NULL\n", i); goto err; } } /* * Walk the remainder of the chain and see if the doubly linked * list checks out. */ if (i == 0) { prev = bio[1]; j = 2; } else { prev = bio[0]; j = 1; } for (; j < nitems(bio); j++) { if (j == i) continue; if (BIO_next(prev) != bio[j]) { fprintf(stderr, "i = %zu, j = %zu: " "BIO_next(prev) != bio[%zu]\n", i, j, j); goto err; } if (BIO_prev(bio[j]) != prev) { fprintf(stderr, "i = %zu, j = %zu: " "BIO_prev(bio[%zu]) != prev\n", i, j, j); goto err; } prev = bio[j]; } if (BIO_next(prev) != NULL) { fprintf(stderr, "i = %zu: BIO_next(prev) != NULL\n", i); goto err; } bio_chain_destroy(bio, nitems(bio)); } failed = 0; err: bio_chain_destroy(bio, nitems(bio)); return failed; } static void walk(BIO *(*step)(BIO *), BIO *start, BIO **end, size_t *len) { BIO *current = NULL; BIO *next = start; *len = 0; while (next != NULL) { current = next; next = step(current); (*len)++; } *end = current; } 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) { if (last != expected_last) { fprintf(stderr, "%s case (%zu, %zu) %s %s has unexpected %s\n", fn, i, j, description, direction, last_name); return 0; } if (len != expected_len) { fprintf(stderr, "%s case (%zu, %zu) %s %s want %zu, got %zu\n", fn, i, j, description, direction, expected_len, len); return 0; } return 1; } 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) { BIO *end; size_t len; walk(BIO_next, start, &end, &len); return walk_report(end, expected_end, len, expected_len, i, j, fn, description, "forward", "end"); } 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) { BIO *start; size_t len; walk(BIO_prev, end, &start, &len); return walk_report(start, expected_start, len, expected_len, i, j, fn, description, "backward", "start"); } static int check_chain(BIO *start, BIO *end, size_t expected_len, size_t i, size_t j, const char *fn, const char *description) { if (!walk_forward(start, end, expected_len, i, j, fn, description)) return 0; if (!walk_backward(start, end, expected_len, i, j, fn, description)) return 0; return 1; } /* * Link two linear chains of BIOs A[] and B[] together using either * BIO_push(A[i], B[j]) or BIO_set_next(A[i], B[j]). * * BIO_push() first walks the chain A[] to its end and then appends the tail * of chain B[] starting at B[j]. If j > 0, we get two chains * * A[0] -- ... -- A[nitems(A) - 1] -- B[j] -- ... -- B[nitems(B) - 1] * `- link created by BIO_push() * B[0] -- ... -- B[j-1] * |<-- oldhead -->| * * of lengths nitems(A) + nitems(B) - j and j, respectively. * If j == 0, the second chain (oldhead) is empty. One quirk of BIO_push() is * that the outcome of BIO_push(A[i], B[j]) apart from the return value is * independent of i. * * Prior to bio_lib.c r1.41, BIO_push(A[i], B[j]) would fail to dissociate the * two chains and leave B[j] with two parents for 0 < j < nitems(B). * B[j]->prev_bio would point at A[nitems(A) - 1], while both B[j - 1] and * A[nitems(A) - 1] would point at B[j]. In particular, BIO_free_all(A[0]) * followed by BIO_free_all(B[0]) results in a double free of B[j]. * * The result for BIO_set_next() is different: three chains are created. * * |--- oldtail --> * ... -- A[i-1] -- A[i] -- A[i+1] -- ... * \ * \ link created by BIO_set_next() * --- oldhead -->| \ * ... -- B[j-1] -- B[j] -- B[j+1] -- ... * * After creating a new link, the new chain has length i + 1 + nitems(B) - j, * oldtail has length nitems(A) - i - 1 and oldhead has length j. * * Prior to bio_lib.c r1.40, BIO_set_next(A[i], B[j]) would result in both A[i] * and B[j - 1] pointing at B[j] while B[j] would point back at A[i]. Calling * BIO_free_all(A[0]) and BIO_free_all(B[0]) results in a double free of B[j]. * * XXX: Should check that the callback is called on BIO_push() as expected. */ static int link_chains_at(size_t i, size_t j, int use_bio_push) { const char *fn = use_bio_push ? "BIO_push" : "BIO_set_next"; BIO *A[LINK_CHAIN_A_LEN], *B[LINK_CHAIN_B_LEN]; BIO *new_start, *new_end; BIO *oldhead_start, *oldhead_end, *oldtail_start, *oldtail_end; size_t new_len, oldhead_len, oldtail_len; int failed = 1; memset(A, 0, sizeof(A)); memset(B, 0, sizeof(B)); if (i >= nitems(A) || j >= nitems(B)) goto err; /* Create two linear chains of BIOs. */ if (!bio_chain_create(BIO_s_null(), A, nitems(A))) goto err; if (!bio_chain_create(BIO_s_null(), B, nitems(B))) goto err; /* * Set our expectations. ... it's complicated. */ new_start = A[0]; new_end = B[nitems(B) - 1]; /* new_len depends on use_bio_push. It is set a few lines down. */ oldhead_start = B[0]; oldhead_end = BIO_prev(B[j]); oldhead_len = j; /* If we push B[0] or set next to B[0], the oldhead chain is empty. */ if (j == 0) { oldhead_start = NULL; oldhead_end = NULL; oldhead_len = 0; } if (use_bio_push) { new_len = nitems(A) + nitems(B) - j; /* oldtail doesn't exist in the BIO_push() case. */ oldtail_start = NULL; oldtail_end = NULL; oldtail_len = 0; } else { new_len = i + 1 + nitems(B) - j; oldtail_start = BIO_next(A[i]); oldtail_end = A[nitems(A) - 1]; oldtail_len = nitems(A) - i - 1; /* If we set next on end of A[], the oldtail chain is empty. */ if (i == nitems(A) - 1) { oldtail_start = NULL; oldtail_end = NULL; oldtail_len = 0; } } /* The two chains A[] and B[] are split into three disjoint pieces. */ if (nitems(A) + nitems(B) != new_len + oldtail_len + oldhead_len) { fprintf(stderr, "%s case (%zu, %zu) inconsistent lengths: " "%zu + %zu != %zu + %zu + %zu\n", fn, i, j, nitems(A), nitems(B), new_len, oldtail_len, oldhead_len); goto err; } /* * Now actually push or set next. */ if (use_bio_push) { if (BIO_push(A[i], B[j]) != A[i]) { fprintf(stderr, "BIO_push(A[%zu], B[%zu]) != A[%zu]\n", i, j, i); goto err; } } else { BIO_set_next(A[i], B[j]); } /* * Check that all the chains match our expectations. */ if (!check_chain(new_start, new_end, new_len, i, j, fn, "new chain")) goto err; if (!check_chain(oldhead_start, oldhead_end, oldhead_len, i, j, fn, "oldhead")) goto err; if (!check_chain(oldtail_start, oldtail_end, oldtail_len, i, j, fn, "oldtail")) goto err; /* * All sanity checks passed. We can now free the chains * with the BIO API without risk of leaks or double frees. */ BIO_free_all(new_start); BIO_free_all(oldhead_start); BIO_free_all(oldtail_start); memset(A, 0, sizeof(A)); memset(B, 0, sizeof(B)); failed = 0; err: bio_chain_destroy(A, nitems(A)); bio_chain_destroy(B, nitems(B)); return failed; } static int link_chains(int use_bio_push) { size_t i, j; int failure = 0; for (i = 0; i < LINK_CHAIN_A_LEN; i++) { for (j = 0; j < LINK_CHAIN_B_LEN; j++) { failure |= link_chains_at(i, j, use_bio_push); } } return failure; } static int bio_push_link_test(void) { int use_bio_push = 1; return link_chains(use_bio_push); } static int bio_set_next_link_test(void) { int use_bio_push = 0; return link_chains(use_bio_push); } static long dup_leak_cb(BIO *bio, int cmd, const char *argp, int argi, long argl, long ret) { if (argi == BIO_CTRL_DUP) return 0; return ret; } static int bio_dup_chain_leak(void) { BIO *bio[CHAIN_POP_LEN]; BIO *dup; int failed = 1; if (!bio_chain_create(BIO_s_null(), bio, nitems(bio))) goto err; if ((dup = BIO_dup_chain(bio[0])) == NULL) { fprintf(stderr, "BIO_set_callback() failed\n"); goto err; } BIO_set_callback(bio[CHAIN_POP_LEN - 1], dup_leak_cb); BIO_free_all(dup); if ((dup = BIO_dup_chain(bio[0])) != NULL) { fprintf(stderr, "BIO_dup_chain() succeeded unexpectedly\n"); BIO_free_all(dup); goto err; } failed = 0; err: bio_chain_destroy(bio, nitems(bio)); return failed; } int main(int argc, char **argv) { int failed = 0; failed |= bio_chain_pop_test(); failed |= bio_push_link_test(); failed |= bio_set_next_link_test(); failed |= bio_dup_chain_leak(); return failed; }