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_ida.c (4392B)

      1// SPDX-License-Identifier: GPL-2.0+
      2/*
      3 * test_ida.c: Test the IDA API
      4 * Copyright (c) 2016-2018 Microsoft Corporation
      5 * Copyright (c) 2018 Oracle Corporation
      6 * Author: Matthew Wilcox <willy@infradead.org>
      7 */
      8
      9#include <linux/idr.h>
     10#include <linux/module.h>
     11
     12static unsigned int tests_run;
     13static unsigned int tests_passed;
     14
     15#ifdef __KERNEL__
     16void ida_dump(struct ida *ida) { }
     17#endif
     18#define IDA_BUG_ON(ida, x) do {						\
     19	tests_run++;							\
     20	if (x) {							\
     21		ida_dump(ida);						\
     22		dump_stack();						\
     23	} else {							\
     24		tests_passed++;						\
     25	}								\
     26} while (0)
     27
     28/*
     29 * Straightforward checks that allocating and freeing IDs work.
     30 */
     31static void ida_check_alloc(struct ida *ida)
     32{
     33	int i, id;
     34
     35	for (i = 0; i < 10000; i++)
     36		IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
     37
     38	ida_free(ida, 20);
     39	ida_free(ida, 21);
     40	for (i = 0; i < 3; i++) {
     41		id = ida_alloc(ida, GFP_KERNEL);
     42		IDA_BUG_ON(ida, id < 0);
     43		if (i == 2)
     44			IDA_BUG_ON(ida, id != 10000);
     45	}
     46
     47	for (i = 0; i < 5000; i++)
     48		ida_free(ida, i);
     49
     50	IDA_BUG_ON(ida, ida_alloc_min(ida, 5000, GFP_KERNEL) != 10001);
     51	ida_destroy(ida);
     52
     53	IDA_BUG_ON(ida, !ida_is_empty(ida));
     54}
     55
     56/* Destroy an IDA with a single entry at @base */
     57static void ida_check_destroy_1(struct ida *ida, unsigned int base)
     58{
     59	IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) != base);
     60	IDA_BUG_ON(ida, ida_is_empty(ida));
     61	ida_destroy(ida);
     62	IDA_BUG_ON(ida, !ida_is_empty(ida));
     63}
     64
     65/* Check that ida_destroy and ida_is_empty work */
     66static void ida_check_destroy(struct ida *ida)
     67{
     68	/* Destroy an already-empty IDA */
     69	IDA_BUG_ON(ida, !ida_is_empty(ida));
     70	ida_destroy(ida);
     71	IDA_BUG_ON(ida, !ida_is_empty(ida));
     72
     73	ida_check_destroy_1(ida, 0);
     74	ida_check_destroy_1(ida, 1);
     75	ida_check_destroy_1(ida, 1023);
     76	ida_check_destroy_1(ida, 1024);
     77	ida_check_destroy_1(ida, 12345678);
     78}
     79
     80/*
     81 * Check what happens when we fill a leaf and then delete it.  This may
     82 * discover mishandling of IDR_FREE.
     83 */
     84static void ida_check_leaf(struct ida *ida, unsigned int base)
     85{
     86	unsigned long i;
     87
     88	for (i = 0; i < IDA_BITMAP_BITS; i++) {
     89		IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
     90				base + i);
     91	}
     92
     93	ida_destroy(ida);
     94	IDA_BUG_ON(ida, !ida_is_empty(ida));
     95
     96	IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != 0);
     97	IDA_BUG_ON(ida, ida_is_empty(ida));
     98	ida_free(ida, 0);
     99	IDA_BUG_ON(ida, !ida_is_empty(ida));
    100}
    101
    102/*
    103 * Check allocations up to and slightly above the maximum allowed (2^31-1) ID.
    104 * Allocating up to 2^31-1 should succeed, and then allocating the next one
    105 * should fail.
    106 */
    107static void ida_check_max(struct ida *ida)
    108{
    109	unsigned long i, j;
    110
    111	for (j = 1; j < 65537; j *= 2) {
    112		unsigned long base = (1UL << 31) - j;
    113		for (i = 0; i < j; i++) {
    114			IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
    115					base + i);
    116		}
    117		IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
    118				-ENOSPC);
    119		ida_destroy(ida);
    120		IDA_BUG_ON(ida, !ida_is_empty(ida));
    121	}
    122}
    123
    124/*
    125 * Check handling of conversions between exceptional entries and full bitmaps.
    126 */
    127static void ida_check_conv(struct ida *ida)
    128{
    129	unsigned long i;
    130
    131	for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) {
    132		IDA_BUG_ON(ida, ida_alloc_min(ida, i + 1, GFP_KERNEL) != i + 1);
    133		IDA_BUG_ON(ida, ida_alloc_min(ida, i + BITS_PER_LONG,
    134					GFP_KERNEL) != i + BITS_PER_LONG);
    135		ida_free(ida, i + 1);
    136		ida_free(ida, i + BITS_PER_LONG);
    137		IDA_BUG_ON(ida, !ida_is_empty(ida));
    138	}
    139
    140	for (i = 0; i < IDA_BITMAP_BITS * 2; i++)
    141		IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
    142	for (i = IDA_BITMAP_BITS * 2; i > 0; i--)
    143		ida_free(ida, i - 1);
    144	IDA_BUG_ON(ida, !ida_is_empty(ida));
    145
    146	for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++)
    147		IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
    148	for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--)
    149		ida_free(ida, i - 1);
    150	IDA_BUG_ON(ida, !ida_is_empty(ida));
    151}
    152
    153static DEFINE_IDA(ida);
    154
    155static int ida_checks(void)
    156{
    157	IDA_BUG_ON(&ida, !ida_is_empty(&ida));
    158	ida_check_alloc(&ida);
    159	ida_check_destroy(&ida);
    160	ida_check_leaf(&ida, 0);
    161	ida_check_leaf(&ida, 1024);
    162	ida_check_leaf(&ida, 1024 * 64);
    163	ida_check_max(&ida);
    164	ida_check_conv(&ida);
    165
    166	printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
    167	return (tests_run != tests_passed) ? 0 : -EINVAL;
    168}
    169
    170static void ida_exit(void)
    171{
    172}
    173
    174module_init(ida_checks);
    175module_exit(ida_exit);
    176MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
    177MODULE_LICENSE("GPL");