// SPDX-License-Identifier: GPL-2.0
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <assert.h>
#include <limits.h>

#include <linux/slab.h>
#include <linux/radix-tree.h>

#include "test.h"
#include "regression.h"

void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
{
        long idx;
        RADIX_TREE(tree, GFP_KERNEL);

        middle = 1 << 30;

        for (idx = -down; idx < up; idx++)
                item_insert(&tree, middle + idx);

        item_check_absent(&tree, middle - down - 1);
        for (idx = -down; idx < up; idx++)
                item_check_present(&tree, middle + idx);
        item_check_absent(&tree, middle + up);

        if (chunk > 0) {
                item_gang_check_present(&tree, middle - down, up + down,
                                chunk, hop);
                item_full_scan(&tree, middle - down, down + up, chunk);
        }
        item_kill_tree(&tree);
}

void gang_check(void)
{
        __gang_check(1UL << 30, 128, 128, 35, 2);
        __gang_check(1UL << 31, 128, 128, 32, 32);
        __gang_check(1UL << 31, 128, 128, 32, 100);
        __gang_check(1UL << 31, 128, 128, 17, 7);
        __gang_check(0xffff0000UL, 0, 65536, 17, 7);
        __gang_check(0xfffffffeUL, 1, 1, 17, 7);
}

void __big_gang_check(void)
{
        unsigned long start;
        int wrapped = 0;

        start = 0;
        do {
                unsigned long old_start;

//              printf("0x%08lx\n", start);
                __gang_check(start, rand() % 113 + 1, rand() % 71,
                                rand() % 157, rand() % 91 + 1);
                old_start = start;
                start += rand() % 1000000;
                start %= 1ULL << 33;
                if (start < old_start)
                        wrapped = 1;
        } while (!wrapped);
}

void big_gang_check(bool long_run)
{
        int i;

        for (i = 0; i < (long_run ? 1000 : 3); i++) {
                __big_gang_check();
                printv(2, "%d ", i);
                fflush(stdout);
        }
}

void add_and_check(void)
{
        RADIX_TREE(tree, GFP_KERNEL);

        item_insert(&tree, 44);
        item_check_present(&tree, 44);
        item_check_absent(&tree, 43);
        item_kill_tree(&tree);
}

void dynamic_height_check(void)
{
        int i;
        RADIX_TREE(tree, GFP_KERNEL);
        tree_verify_min_height(&tree, 0);

        item_insert(&tree, 42);
        tree_verify_min_height(&tree, 42);

        item_insert(&tree, 1000000);
        tree_verify_min_height(&tree, 1000000);

        assert(item_delete(&tree, 1000000));
        tree_verify_min_height(&tree, 42);

        assert(item_delete(&tree, 42));
        tree_verify_min_height(&tree, 0);

        for (i = 0; i < 1000; i++) {
                item_insert(&tree, i);
                tree_verify_min_height(&tree, i);
        }

        i--;
        for (;;) {
                assert(item_delete(&tree, i));
                if (i == 0) {
                        tree_verify_min_height(&tree, 0);
                        break;
                }
                i--;
                tree_verify_min_height(&tree, i);
        }

        item_kill_tree(&tree);
}

void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag)
{
        int i;

        for (i = 0; i < count; i++) {
/*              if (i % 1000 == 0)
                        putchar('.'); */
                if (idx[i] < start || idx[i] > end) {
                        if (item_tag_get(tree, idx[i], totag)) {
                                printv(2, "%lu-%lu: %lu, tags %d-%d\n", start,
                                       end, idx[i], item_tag_get(tree, idx[i],
                                                                 fromtag),
                                       item_tag_get(tree, idx[i], totag));
                        }
                        assert(!item_tag_get(tree, idx[i], totag));
                        continue;
                }
                if (item_tag_get(tree, idx[i], fromtag) ^
                        item_tag_get(tree, idx[i], totag)) {
                        printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, end,
                               idx[i], item_tag_get(tree, idx[i], fromtag),
                               item_tag_get(tree, idx[i], totag));
                }
                assert(!(item_tag_get(tree, idx[i], fromtag) ^
                         item_tag_get(tree, idx[i], totag)));
        }
}

#define ITEMS 50000

void copy_tag_check(void)
{
        RADIX_TREE(tree, GFP_KERNEL);
        unsigned long idx[ITEMS];
        unsigned long start, end, count = 0, tagged, cur, tmp;
        int i;

//      printf("generating radix tree indices...\n");
        start = rand();
        end = rand();
        if (start > end && (rand() % 10)) {
                cur = start;
                start = end;
                end = cur;
        }
        /* Specifically create items around the start and the end of the range
         * with high probability to check for off by one errors */
        cur = rand();
        if (cur & 1) {
                item_insert(&tree, start);
                if (cur & 2) {
                        if (start <= end)
                                count++;
                        item_tag_set(&tree, start, 0);
                }
        }
        if (cur & 4) {
                item_insert(&tree, start-1);
                if (cur & 8)
                        item_tag_set(&tree, start-1, 0);
        }
        if (cur & 16) {
                item_insert(&tree, end);
                if (cur & 32) {
                        if (start <= end)
                                count++;
                        item_tag_set(&tree, end, 0);
                }
        }
        if (cur & 64) {
                item_insert(&tree, end+1);
                if (cur & 128)
                        item_tag_set(&tree, end+1, 0);
        }

        for (i = 0; i < ITEMS; i++) {
                do {
                        idx[i] = rand();
                } while (item_lookup(&tree, idx[i]));

                item_insert(&tree, idx[i]);
                if (rand() & 1) {
                        item_tag_set(&tree, idx[i], 0);
                        if (idx[i] >= start && idx[i] <= end)
                                count++;
                }
/*              if (i % 1000 == 0)
                        putchar('.'); */
        }

//      printf("\ncopying tags...\n");
        tagged = tag_tagged_items(&tree, start, end, ITEMS, XA_MARK_0, XA_MARK_1);

//      printf("checking copied tags\n");
        assert(tagged == count);
        check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);

        /* Copy tags in several rounds */
//      printf("\ncopying tags...\n");
        tmp = rand() % (count / 10 + 2);
        tagged = tag_tagged_items(&tree, start, end, tmp, XA_MARK_0, XA_MARK_2);
        assert(tagged == count);

//      printf("%lu %lu %lu\n", tagged, tmp, count);
//      printf("checking copied tags\n");
        check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
        verify_tag_consistency(&tree, 0);
        verify_tag_consistency(&tree, 1);
        verify_tag_consistency(&tree, 2);
//      printf("\n");
        item_kill_tree(&tree);
}

static void single_thread_tests(bool long_run)
{
        int i;

        printv(1, "starting single_thread_tests: %d allocated, preempt %d\n",
                nr_allocated, preempt_count);
        multiorder_checks();
        rcu_barrier();
        printv(2, "after multiorder_check: %d allocated, preempt %d\n",
                nr_allocated, preempt_count);
        tag_check();
        rcu_barrier();
        printv(2, "after tag_check: %d allocated, preempt %d\n",
                nr_allocated, preempt_count);
        gang_check();
        rcu_barrier();
        printv(2, "after gang_check: %d allocated, preempt %d\n",
                nr_allocated, preempt_count);
        add_and_check();
        rcu_barrier();
        printv(2, "after add_and_check: %d allocated, preempt %d\n",
                nr_allocated, preempt_count);
        dynamic_height_check();
        rcu_barrier();
        printv(2, "after dynamic_height_check: %d allocated, preempt %d\n",
                nr_allocated, preempt_count);
        idr_checks();
        ida_tests();
        rcu_barrier();
        printv(2, "after idr_checks: %d allocated, preempt %d\n",
                nr_allocated, preempt_count);
        big_gang_check(long_run);
        rcu_barrier();
        printv(2, "after big_gang_check: %d allocated, preempt %d\n",
                nr_allocated, preempt_count);
        for (i = 0; i < (long_run ? 2000 : 3); i++) {
                copy_tag_check();
                printv(2, "%d ", i);
                fflush(stdout);
        }
        rcu_barrier();
        printv(2, "after copy_tag_check: %d allocated, preempt %d\n",
                nr_allocated, preempt_count);
}

int main(int argc, char **argv)
{
        bool long_run = false;
        int opt;
        unsigned int seed = time(NULL);

        while ((opt = getopt(argc, argv, "ls:v")) != -1) {
                if (opt == 'l')
                        long_run = true;
                else if (opt == 's')
                        seed = strtoul(optarg, NULL, 0);
                else if (opt == 'v')
                        test_verbose++;
        }

        printf("random seed %u\n", seed);
        srand(seed);

        printf("running tests\n");

        rcu_register_thread();
        radix_tree_init();

        xarray_tests();
        regression1_test();
        regression2_test();
        regression3_test();
        regression4_test();
        iteration_test(0, 10 + 90 * long_run);
        iteration_test(7, 10 + 90 * long_run);
        iteration_test2(10 + 90 * long_run);
        single_thread_tests(long_run);

        /* Free any remaining preallocated nodes */
        radix_tree_cpu_dead(0);

        benchmark();

        rcu_barrier();
        printv(2, "after rcu_barrier: %d allocated, preempt %d\n",
                nr_allocated, preempt_count);
        rcu_unregister_thread();

        printf("tests completed\n");

        exit(0);
}