cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

test_min_heap.c (4425B)

      1// SPDX-License-Identifier: GPL-2.0-only
      2#define pr_fmt(fmt) "min_heap_test: " fmt
      3
      4/*
      5 * Test cases for the min max heap.
      6 */
      7
      8#include <linux/log2.h>
      9#include <linux/min_heap.h>
     10#include <linux/module.h>
     11#include <linux/printk.h>
     12#include <linux/random.h>
     13
     14static __init bool less_than(const void *lhs, const void *rhs)
     15{
     16	return *(int *)lhs < *(int *)rhs;
     17}
     18
     19static __init bool greater_than(const void *lhs, const void *rhs)
     20{
     21	return *(int *)lhs > *(int *)rhs;
     22}
     23
     24static __init void swap_ints(void *lhs, void *rhs)
     25{
     26	int temp = *(int *)lhs;
     27
     28	*(int *)lhs = *(int *)rhs;
     29	*(int *)rhs = temp;
     30}
     31
     32static __init int pop_verify_heap(bool min_heap,
     33				struct min_heap *heap,
     34				const struct min_heap_callbacks *funcs)
     35{
     36	int *values = heap->data;
     37	int err = 0;
     38	int last;
     39
     40	last = values[0];
     41	min_heap_pop(heap, funcs);
     42	while (heap->nr > 0) {
     43		if (min_heap) {
     44			if (last > values[0]) {
     45				pr_err("error: expected %d <= %d\n", last,
     46					values[0]);
     47				err++;
     48			}
     49		} else {
     50			if (last < values[0]) {
     51				pr_err("error: expected %d >= %d\n", last,
     52					values[0]);
     53				err++;
     54			}
     55		}
     56		last = values[0];
     57		min_heap_pop(heap, funcs);
     58	}
     59	return err;
     60}
     61
     62static __init int test_heapify_all(bool min_heap)
     63{
     64	int values[] = { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0,
     65			 -3, -1, -2, -4, 0x8000000, 0x7FFFFFF };
     66	struct min_heap heap = {
     67		.data = values,
     68		.nr = ARRAY_SIZE(values),
     69		.size =  ARRAY_SIZE(values),
     70	};
     71	struct min_heap_callbacks funcs = {
     72		.elem_size = sizeof(int),
     73		.less = min_heap ? less_than : greater_than,
     74		.swp = swap_ints,
     75	};
     76	int i, err;
     77
     78	/* Test with known set of values. */
     79	min_heapify_all(&heap, &funcs);
     80	err = pop_verify_heap(min_heap, &heap, &funcs);
     81
     82
     83	/* Test with randomly generated values. */
     84	heap.nr = ARRAY_SIZE(values);
     85	for (i = 0; i < heap.nr; i++)
     86		values[i] = get_random_int();
     87
     88	min_heapify_all(&heap, &funcs);
     89	err += pop_verify_heap(min_heap, &heap, &funcs);
     90
     91	return err;
     92}
     93
     94static __init int test_heap_push(bool min_heap)
     95{
     96	const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0,
     97			     -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF };
     98	int values[ARRAY_SIZE(data)];
     99	struct min_heap heap = {
    100		.data = values,
    101		.nr = 0,
    102		.size =  ARRAY_SIZE(values),
    103	};
    104	struct min_heap_callbacks funcs = {
    105		.elem_size = sizeof(int),
    106		.less = min_heap ? less_than : greater_than,
    107		.swp = swap_ints,
    108	};
    109	int i, temp, err;
    110
    111	/* Test with known set of values copied from data. */
    112	for (i = 0; i < ARRAY_SIZE(data); i++)
    113		min_heap_push(&heap, &data[i], &funcs);
    114
    115	err = pop_verify_heap(min_heap, &heap, &funcs);
    116
    117	/* Test with randomly generated values. */
    118	while (heap.nr < heap.size) {
    119		temp = get_random_int();
    120		min_heap_push(&heap, &temp, &funcs);
    121	}
    122	err += pop_verify_heap(min_heap, &heap, &funcs);
    123
    124	return err;
    125}
    126
    127static __init int test_heap_pop_push(bool min_heap)
    128{
    129	const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0,
    130			     -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF };
    131	int values[ARRAY_SIZE(data)];
    132	struct min_heap heap = {
    133		.data = values,
    134		.nr = 0,
    135		.size =  ARRAY_SIZE(values),
    136	};
    137	struct min_heap_callbacks funcs = {
    138		.elem_size = sizeof(int),
    139		.less = min_heap ? less_than : greater_than,
    140		.swp = swap_ints,
    141	};
    142	int i, temp, err;
    143
    144	/* Fill values with data to pop and replace. */
    145	temp = min_heap ? 0x80000000 : 0x7FFFFFFF;
    146	for (i = 0; i < ARRAY_SIZE(data); i++)
    147		min_heap_push(&heap, &temp, &funcs);
    148
    149	/* Test with known set of values copied from data. */
    150	for (i = 0; i < ARRAY_SIZE(data); i++)
    151		min_heap_pop_push(&heap, &data[i], &funcs);
    152
    153	err = pop_verify_heap(min_heap, &heap, &funcs);
    154
    155	heap.nr = 0;
    156	for (i = 0; i < ARRAY_SIZE(data); i++)
    157		min_heap_push(&heap, &temp, &funcs);
    158
    159	/* Test with randomly generated values. */
    160	for (i = 0; i < ARRAY_SIZE(data); i++) {
    161		temp = get_random_int();
    162		min_heap_pop_push(&heap, &temp, &funcs);
    163	}
    164	err += pop_verify_heap(min_heap, &heap, &funcs);
    165
    166	return err;
    167}
    168
    169static int __init test_min_heap_init(void)
    170{
    171	int err = 0;
    172
    173	err += test_heapify_all(true);
    174	err += test_heapify_all(false);
    175	err += test_heap_push(true);
    176	err += test_heap_push(false);
    177	err += test_heap_pop_push(true);
    178	err += test_heap_pop_push(false);
    179	if (err) {
    180		pr_err("test failed with %d errors\n", err);
    181		return -EINVAL;
    182	}
    183	pr_info("test passed\n");
    184	return 0;
    185}
    186module_init(test_min_heap_init);
    187
    188static void __exit test_min_heap_exit(void)
    189{
    190	/* do nothing */
    191}
    192module_exit(test_min_heap_exit);
    193
    194MODULE_LICENSE("GPL");