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