/*      $OpenBSD: bio_chain.c,v 1.16 2023/08/07 11:00:54 tb Exp $       */
/*
 * Copyright (c) 2022 Theo Buehler <tb@openbsd.org>
 *
 * 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 <err.h>
#include <stdio.h>
#include <string.h>

#include <openssl/bio.h>

#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;
}