/*

 * Copyright 2024 The OpenSSL Project Authors. All Rights Reserved.

 *

 * Licensed under the Apache License 2.0 (the "License");

 * you may not use this file except in compliance with the License.

 * You may obtain a copy of the License at

 * https://www.openssl.org/source/license.html

 * or in the file LICENSE in the source distribution.

 */

/*

 * Test hashtable operation.

 */

#include <limits.h>

#include <openssl/err.h>

#include <openssl/bio.h>

#include <internal/common.h>

#include <internal/hashtable.h>

#include "fuzzer.h"

/*

 * Make the key space very small here to make lookups

 * easy to predict for the purposes of validation

 * A two byte key gives us 65536 possible entries

 * so we can allocate a flat table to compare to

 */

HT_START_KEY_DEFN(fuzzer_key)

HT_DEF_KEY_FIELD(fuzzkey, uint16_t)

HT_END_KEY_DEFN(FUZZER_KEY)

#define FZ_FLAG_ALLOCATED (1 << 0)

typedef struct fuzzer_value_st {

    uint64_t flags;

    uint64_t value;

} FUZZER_VALUE;

IMPLEMENT_HT_VALUE_TYPE_FNS(FUZZER_VALUE, fz, static)

static size_t skipped_values = 0;

static size_t inserts = 0;

static size_t replacements = 0;

static size_t deletes = 0;

static size_t flushes = 0;

static size_t lookups = 0;

static size_t foreaches = 0;

static size_t filters = 0;

static int valfound;

static FUZZER_VALUE *prediction_table = NULL;

static HT *fuzzer_table = NULL;

/*

 * Operational values

 */

#define OP_INSERT  0

#define OP_DELETE  1

#define OP_LOOKUP  2

#define OP_FLUSH   3

#define OP_FOREACH 4

#define OP_FILTER  5

#define OP_END     6 

#define OP_MASK 0x3f

#define INSERT_REPLACE_MASK 0x40

#define OPERATION(x) (((x) & OP_MASK) % OP_END)

#define IS_REPLACE(x) ((x) & INSERT_REPLACE_MASK)

static int table_iterator(HT_VALUE *v, void *arg)

{

    uint16_t keyval = (*(uint16_t *)arg);

    FUZZER_VALUE *f = ossl_ht_fz_FUZZER_VALUE_from_value(v);

    if (f != NULL && f == &prediction_table[keyval]) {

        valfound = 1;

        return 0;

    }

    return 1;

}

static int filter_iterator(HT_VALUE *v, void *arg)

{

    uint16_t keyval = (*(uint16_t *)arg);

    FUZZER_VALUE *f = ossl_ht_fz_FUZZER_VALUE_from_value(v);

    if (f != NULL && f == &prediction_table[keyval])

        return 1;

    return 0;

}

static void fuzz_free_cb(HT_VALUE *v)

{

    FUZZER_VALUE *f = ossl_ht_fz_FUZZER_VALUE_from_value(v);

    if (f != NULL)

        f->flags &= ~FZ_FLAG_ALLOCATED;

}

int FuzzerInitialize(int *argc, char ***argv)

{

    HT_CONFIG fuzz_conf = {NULL, fuzz_free_cb, NULL, 0, 1};

    OPENSSL_init_crypto(OPENSSL_INIT_LOAD_CRYPTO_STRINGS, NULL);

    ERR_clear_error();

    prediction_table = OPENSSL_zalloc(sizeof(FUZZER_VALUE) * 65537);

    if (prediction_table == NULL)

        return -1;

    fuzzer_table = ossl_ht_new(&fuzz_conf);

    if (fuzzer_table == NULL) {

        OPENSSL_free(prediction_table);

        return -1;

    }

    return 0;

}

int FuzzerTestOneInput(const uint8_t *buf, size_t len)

{

    uint8_t op_flags;

    uint16_t keyval;

    int rc;

    int rc_prediction = 1;

    size_t i;

    FUZZER_VALUE *valptr, *lval;

    FUZZER_KEY key;

    HT_VALUE *v = NULL;

    HT_VALUE tv;

    HT_VALUE_LIST *htvlist;

    /*

     * We need at least 11 bytes to be able to do anything here

     * 1 byte to detect the operation to perform, 2 bytes

     * for the lookup key, and 8 bytes of value

     */

    if (len < 11) {

        skipped_values++;

        return -1;

    }

    /*

     * parse out our operation flags and key

     */

    op_flags = buf[0];

    memcpy(&keyval, &buf[1], sizeof(uint16_t));

    /*

     * Initialize our key

     */

    HT_INIT_KEY(&key);

    /*

     * Now do our operation

     */

    switch(OPERATION(op_flags)) {

    case OP_INSERT:

        valptr = &prediction_table[keyval];

        /* reset our key */

        HT_KEY_RESET(&key);

        /* set the proper key value */

        HT_SET_KEY_FIELD(&key, fuzzkey, keyval);

        /* lock the table */

        ossl_ht_write_lock(fuzzer_table);

        /*

         * If the value to insert is already allocated

         * then we expect a conflict in the insert

         * i.e. we predict a return code of 0 instead

         * of 1. On replacement, we expect it to succeed

         * always

         */

        if (valptr->flags & FZ_FLAG_ALLOCATED) {

            if (!IS_REPLACE(op_flags))

                rc_prediction = 0;

        }

        memcpy(&valptr->value, &buf[3], sizeof(uint64_t));

        /*

         * do the insert/replace

         */

        if (IS_REPLACE(op_flags))

            rc = ossl_ht_fz_FUZZER_VALUE_insert(fuzzer_table, TO_HT_KEY(&key),

                                                valptr, &lval);

        else

            rc = ossl_ht_fz_FUZZER_VALUE_insert(fuzzer_table, TO_HT_KEY(&key),

                                                valptr, NULL);

        if (rc == -1)

            /* failed to grow the hash table due to too many collisions */

            break;

        /*

         * mark the entry as being allocated

         */

        valptr->flags |= FZ_FLAG_ALLOCATED;

        /*

         * unlock the table

         */

        ossl_ht_write_unlock(fuzzer_table);

        /*

         * Now check to make sure we did the right thing

         */

        OPENSSL_assert(rc == rc_prediction);

        /*

         * successful insertion if there wasn't a conflict

         */

        if (rc_prediction == 1)

            IS_REPLACE(op_flags) ? replacements++ : inserts++;

        break;

    case OP_DELETE:

        valptr = &prediction_table[keyval];

        /* reset our key */

        HT_KEY_RESET(&key);

        /* set the proper key value */

        HT_SET_KEY_FIELD(&key, fuzzkey, keyval);

        /* lock the table */

        ossl_ht_write_lock(fuzzer_table);

        /*

         * If the value to delete is not already allocated

         * then we expect a miss in the delete

         * i.e. we predict a return code of 0 instead

         * of 1

         */

        if (!(valptr->flags & FZ_FLAG_ALLOCATED))

            rc_prediction = 0;

        /*

         * do the delete

         */

        rc = ossl_ht_delete(fuzzer_table, TO_HT_KEY(&key));

        /*

         * unlock the table

         */

        ossl_ht_write_unlock(fuzzer_table);

        /*

         * Now check to make sure we did the right thing

         */

        OPENSSL_assert(rc == rc_prediction);

        /*

         * once the unlock is done, the table rcu will have synced

         * meaning the free function has run, so we can confirm now

         * that the valptr is no longer allocated

         */

        OPENSSL_assert(!(valptr->flags & FZ_FLAG_ALLOCATED));

        /*

         * successful deletion if there wasn't a conflict

         */

        if (rc_prediction == 1)

            deletes++;

        break;

    case OP_LOOKUP:

        valptr = &prediction_table[keyval];

        lval = NULL;

        /* reset our key */

        HT_KEY_RESET(&key);

        /* set the proper key value */

        HT_SET_KEY_FIELD(&key, fuzzkey, keyval);

        /* lock the table for reading */

        ossl_ht_read_lock(fuzzer_table);

        /*

         * If the value to find is not already allocated

         * then we expect a miss in the lookup

         * i.e. we predict a return code of NULL instead

         * of a pointer

         */

        if (!(valptr->flags & FZ_FLAG_ALLOCATED))

            valptr = NULL;

        /*

         * do the lookup

         */

        lval = ossl_ht_fz_FUZZER_VALUE_get(fuzzer_table, TO_HT_KEY(&key), &v);

        /*

         * unlock the table

         */

        ossl_ht_read_unlock(fuzzer_table);

        /*

         * Now check to make sure we did the right thing

         */

        OPENSSL_assert(lval == valptr);

        /*

         * if we expect a positive lookup, make sure that

         * we can use the _type and to_value functions

         */

        if (valptr != NULL) {

            OPENSSL_assert(ossl_ht_fz_FUZZER_VALUE_type(v) == 1);

            v = ossl_ht_fz_FUZZER_VALUE_to_value(lval, &tv);

            OPENSSL_assert(v->value == lval);

        }

        /*

         * successful lookup if we didn't expect a miss

         */

        if (valptr != NULL)

            lookups++;

        break;

    case OP_FLUSH:

        /*

         * only flush the table rarely 

         */

        if ((flushes % 100000) != 1) {

            skipped_values++;

            flushes++;

            return 0;

        }

        /*

         * lock the table

         */

        ossl_ht_write_lock(fuzzer_table);

        ossl_ht_flush(fuzzer_table);

        ossl_ht_write_unlock(fuzzer_table);

        /*

         * now check to make sure everything is free

         */

       for (i = 0; i < USHRT_MAX; i++)

            OPENSSL_assert((prediction_table[i].flags & FZ_FLAG_ALLOCATED) == 0);

        /* good flush */

        flushes++;

        break;

    case OP_FOREACH:

        valfound = 0;

        valptr = &prediction_table[keyval];

        rc_prediction = 0;

        if (valptr->flags & FZ_FLAG_ALLOCATED)

            rc_prediction = 1;

        ossl_ht_foreach_until(fuzzer_table, table_iterator, &keyval);

        OPENSSL_assert(valfound == rc_prediction);

        foreaches++;

        break;

    case OP_FILTER:

        valptr = &prediction_table[keyval];

        rc_prediction = 0;

        if (valptr->flags & FZ_FLAG_ALLOCATED)

            rc_prediction = 1;

        htvlist = ossl_ht_filter(fuzzer_table, 1, filter_iterator, &keyval);

        OPENSSL_assert(htvlist->list_len == (size_t)rc_prediction);

        ossl_ht_value_list_free(htvlist);

        filters++;

        break;

    default:

        return -1;

    }

    return 0;

}

void FuzzerCleanup(void)

{

    ossl_ht_free(fuzzer_table);

    OPENSSL_free(prediction_table);

    OPENSSL_cleanup();

}