/*
 * lib/test_parman.c - Test module for parman
 * Copyright (c) 2017 Mellanox Technologies. All rights reserved.
 * Copyright (c) 2017 Jiri Pirko <jiri@mellanox.com>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the names of the copyright holders nor the names of its
 *    contributors may be used to endorse or promote products derived from
 *    this software without specific prior written permission.
 *
 * Alternatively, this software may be distributed under the terms of the
 * GNU General Public License ("GPL") version 2 as published by the Free
 * Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/bitops.h>
#include <linux/err.h>
#include <linux/prandom.h>
#include <linux/parman.h>

#define TEST_PARMAN_PRIO_SHIFT 7 /* defines number of prios for testing */
#define TEST_PARMAN_PRIO_COUNT BIT(TEST_PARMAN_PRIO_SHIFT)
#define TEST_PARMAN_PRIO_MASK (TEST_PARMAN_PRIO_COUNT - 1)

#define TEST_PARMAN_ITEM_SHIFT 13 /* defines a total number
                                   * of items for testing
                                   */
#define TEST_PARMAN_ITEM_COUNT BIT(TEST_PARMAN_ITEM_SHIFT)
#define TEST_PARMAN_ITEM_MASK (TEST_PARMAN_ITEM_COUNT - 1)

#define TEST_PARMAN_BASE_SHIFT 8
#define TEST_PARMAN_BASE_COUNT BIT(TEST_PARMAN_BASE_SHIFT)
#define TEST_PARMAN_RESIZE_STEP_SHIFT 7
#define TEST_PARMAN_RESIZE_STEP_COUNT BIT(TEST_PARMAN_RESIZE_STEP_SHIFT)

#define TEST_PARMAN_BULK_MAX_SHIFT (2 + TEST_PARMAN_RESIZE_STEP_SHIFT)
#define TEST_PARMAN_BULK_MAX_COUNT BIT(TEST_PARMAN_BULK_MAX_SHIFT)
#define TEST_PARMAN_BULK_MAX_MASK (TEST_PARMAN_BULK_MAX_COUNT - 1)

#define TEST_PARMAN_RUN_BUDGET (TEST_PARMAN_ITEM_COUNT * 256)

struct test_parman_prio {
        struct parman_prio parman_prio;
        unsigned long priority;
};

struct test_parman_item {
        struct parman_item parman_item;
        struct test_parman_prio *prio;
        bool used;
};

struct test_parman {
        struct parman *parman;
        struct test_parman_item **prio_array;
        unsigned long prio_array_limit;
        struct test_parman_prio prios[TEST_PARMAN_PRIO_COUNT];
        struct test_parman_item items[TEST_PARMAN_ITEM_COUNT];
        struct rnd_state rnd;
        unsigned long run_budget;
        unsigned long bulk_budget;
        bool bulk_noop;
        unsigned int used_items;
};

#define ITEM_PTRS_SIZE(count) (sizeof(struct test_parman_item *) * (count))

static int test_parman_resize(void *priv, unsigned long new_count)
{
        struct test_parman *test_parman = priv;
        struct test_parman_item **prio_array;
        unsigned long old_count;

        prio_array = krealloc(test_parman->prio_array,
                              ITEM_PTRS_SIZE(new_count), GFP_KERNEL);
        if (new_count == 0)
                return 0;
        if (!prio_array)
                return -ENOMEM;
        old_count = test_parman->prio_array_limit;
        if (new_count > old_count)
                memset(&prio_array[old_count], 0,
                       ITEM_PTRS_SIZE(new_count - old_count));
        test_parman->prio_array = prio_array;
        test_parman->prio_array_limit = new_count;
        return 0;
}

static void test_parman_move(void *priv, unsigned long from_index,
                             unsigned long to_index, unsigned long count)
{
        struct test_parman *test_parman = priv;
        struct test_parman_item **prio_array = test_parman->prio_array;

        memmove(&prio_array[to_index], &prio_array[from_index],
                ITEM_PTRS_SIZE(count));
        memset(&prio_array[from_index], 0, ITEM_PTRS_SIZE(count));
}

static const struct parman_ops test_parman_lsort_ops = {
        .base_count     = TEST_PARMAN_BASE_COUNT,
        .resize_step    = TEST_PARMAN_RESIZE_STEP_COUNT,
        .resize         = test_parman_resize,
        .move           = test_parman_move,
        .algo           = PARMAN_ALGO_TYPE_LSORT,
};

static void test_parman_rnd_init(struct test_parman *test_parman)
{
        prandom_seed_state(&test_parman->rnd, 3141592653589793238ULL);
}

static u32 test_parman_rnd_get(struct test_parman *test_parman)
{
        return prandom_u32_state(&test_parman->rnd);
}

static unsigned long test_parman_priority_gen(struct test_parman *test_parman)
{
        unsigned long priority;
        int i;

again:
        priority = test_parman_rnd_get(test_parman);
        if (priority == 0)
                goto again;

        for (i = 0; i < TEST_PARMAN_PRIO_COUNT; i++) {
                struct test_parman_prio *prio = &test_parman->prios[i];

                if (prio->priority == 0)
                        break;
                if (prio->priority == priority)
                        goto again;
        }
        return priority;
}

static void test_parman_prios_init(struct test_parman *test_parman)
{
        int i;

        for (i = 0; i < TEST_PARMAN_PRIO_COUNT; i++) {
                struct test_parman_prio *prio = &test_parman->prios[i];

                /* Assign random uniqueue priority to each prio structure */
                prio->priority = test_parman_priority_gen(test_parman);
                parman_prio_init(test_parman->parman, &prio->parman_prio,
                                 prio->priority);
        }
}

static void test_parman_prios_fini(struct test_parman *test_parman)
{
        int i;

        for (i = 0; i < TEST_PARMAN_PRIO_COUNT; i++) {
                struct test_parman_prio *prio = &test_parman->prios[i];

                parman_prio_fini(&prio->parman_prio);
        }
}

static void test_parman_items_init(struct test_parman *test_parman)
{
        int i;

        for (i = 0; i < TEST_PARMAN_ITEM_COUNT; i++) {
                struct test_parman_item *item = &test_parman->items[i];
                unsigned int prio_index = test_parman_rnd_get(test_parman) &
                                          TEST_PARMAN_PRIO_MASK;

                /* Assign random prio to each item structure */
                item->prio = &test_parman->prios[prio_index];
        }
}

static void test_parman_items_fini(struct test_parman *test_parman)
{
        int i;

        for (i = 0; i < TEST_PARMAN_ITEM_COUNT; i++) {
                struct test_parman_item *item = &test_parman->items[i];

                if (!item->used)
                        continue;
                parman_item_remove(test_parman->parman,
                                   &item->prio->parman_prio,
                                   &item->parman_item);
        }
}

static struct test_parman *test_parman_create(const struct parman_ops *ops)
{
        struct test_parman *test_parman;
        int err;

        test_parman = kzalloc_obj(*test_parman);
        if (!test_parman)
                return ERR_PTR(-ENOMEM);
        err = test_parman_resize(test_parman, TEST_PARMAN_BASE_COUNT);
        if (err)
                goto err_resize;
        test_parman->parman = parman_create(ops, test_parman);
        if (!test_parman->parman) {
                err = -ENOMEM;
                goto err_parman_create;
        }
        test_parman_rnd_init(test_parman);
        test_parman_prios_init(test_parman);
        test_parman_items_init(test_parman);
        test_parman->run_budget = TEST_PARMAN_RUN_BUDGET;
        return test_parman;

err_parman_create:
        test_parman_resize(test_parman, 0);
err_resize:
        kfree(test_parman);
        return ERR_PTR(err);
}

static void test_parman_destroy(struct test_parman *test_parman)
{
        test_parman_items_fini(test_parman);
        test_parman_prios_fini(test_parman);
        parman_destroy(test_parman->parman);
        test_parman_resize(test_parman, 0);
        kfree(test_parman);
}

static bool test_parman_run_check_budgets(struct test_parman *test_parman)
{
        if (test_parman->run_budget-- == 0)
                return false;
        if (test_parman->bulk_budget-- != 0)
                return true;

        test_parman->bulk_budget = test_parman_rnd_get(test_parman) &
                                   TEST_PARMAN_BULK_MAX_MASK;
        test_parman->bulk_noop = test_parman_rnd_get(test_parman) & 1;
        return true;
}

static int test_parman_run(struct test_parman *test_parman)
{
        unsigned int i = test_parman_rnd_get(test_parman);
        int err;

        while (test_parman_run_check_budgets(test_parman)) {
                unsigned int item_index = i++ & TEST_PARMAN_ITEM_MASK;
                struct test_parman_item *item = &test_parman->items[item_index];

                if (test_parman->bulk_noop)
                        continue;

                if (!item->used) {
                        err = parman_item_add(test_parman->parman,
                                              &item->prio->parman_prio,
                                              &item->parman_item);
                        if (err)
                                return err;
                        test_parman->prio_array[item->parman_item.index] = item;
                        test_parman->used_items++;
                } else {
                        test_parman->prio_array[item->parman_item.index] = NULL;
                        parman_item_remove(test_parman->parman,
                                           &item->prio->parman_prio,
                                           &item->parman_item);
                        test_parman->used_items--;
                }
                item->used = !item->used;
        }
        return 0;
}

static int test_parman_check_array(struct test_parman *test_parman,
                                   bool gaps_allowed)
{
        unsigned int last_unused_items = 0;
        unsigned long last_priority = 0;
        unsigned int used_items = 0;
        int i;

        if (test_parman->prio_array_limit < TEST_PARMAN_BASE_COUNT) {
                pr_err("Array limit is lower than the base count (%lu < %lu)\n",
                       test_parman->prio_array_limit, TEST_PARMAN_BASE_COUNT);
                return -EINVAL;
        }

        for (i = 0; i < test_parman->prio_array_limit; i++) {
                struct test_parman_item *item = test_parman->prio_array[i];

                if (!item) {
                        last_unused_items++;
                        continue;
                }
                if (last_unused_items && !gaps_allowed) {
                        pr_err("Gap found in array even though they are forbidden\n");
                        return -EINVAL;
                }

                last_unused_items = 0;
                used_items++;

                if (item->prio->priority < last_priority) {
                        pr_err("Item belongs under higher priority then the last one (current: %lu, previous: %lu)\n",
                               item->prio->priority, last_priority);
                        return -EINVAL;
                }
                last_priority = item->prio->priority;

                if (item->parman_item.index != i) {
                        pr_err("Item has different index in compare to where it actually is (%lu != %d)\n",
                               item->parman_item.index, i);
                        return -EINVAL;
                }
        }

        if (used_items != test_parman->used_items) {
                pr_err("Number of used items in array does not match (%u != %u)\n",
                       used_items, test_parman->used_items);
                return -EINVAL;
        }

        if (last_unused_items >= TEST_PARMAN_RESIZE_STEP_COUNT) {
                pr_err("Number of unused item at the end of array is bigger than resize step (%u >= %lu)\n",
                       last_unused_items, TEST_PARMAN_RESIZE_STEP_COUNT);
                return -EINVAL;
        }

        pr_info("Priority array check successful\n");

        return 0;
}

static int test_parman_lsort(void)
{
        struct test_parman *test_parman;
        int err;

        test_parman = test_parman_create(&test_parman_lsort_ops);
        if (IS_ERR(test_parman))
                return PTR_ERR(test_parman);

        err = test_parman_run(test_parman);
        if (err)
                goto out;

        err = test_parman_check_array(test_parman, false);
        if (err)
                goto out;
out:
        test_parman_destroy(test_parman);
        return err;
}

static int __init test_parman_init(void)
{
        return test_parman_lsort();
}

static void __exit test_parman_exit(void)
{
}

module_init(test_parman_init);
module_exit(test_parman_exit);

MODULE_LICENSE("Dual BSD/GPL");
MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
MODULE_DESCRIPTION("Test module for parman");