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 12 static unsigned int tests_run; 13 static unsigned int tests_passed; 14 15 #ifdef __KERNEL__ 16 void 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 */ 31 static 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 */ 57 static 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 */ 66 static 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 */ 84 static 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 */ 107 static 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 */ 127 static 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 153 /* 154 * Check various situations where we attempt to free an ID we don't own. 155 */ 156 static void ida_check_bad_free(struct ida *ida) 157 { 158 unsigned long i; 159 160 printk("vvv Ignore \"not allocated\" warnings\n"); 161 /* IDA is empty; all of these will fail */ 162 ida_free(ida, 0); 163 for (i = 0; i < 31; i++) 164 ida_free(ida, 1 << i); 165 166 /* IDA contains a single value entry */ 167 IDA_BUG_ON(ida, ida_alloc_min(ida, 3, GFP_KERNEL) != 3); 168 ida_free(ida, 0); 169 for (i = 0; i < 31; i++) 170 ida_free(ida, 1 << i); 171 172 /* IDA contains a single bitmap */ 173 IDA_BUG_ON(ida, ida_alloc_min(ida, 1023, GFP_KERNEL) != 1023); 174 ida_free(ida, 0); 175 for (i = 0; i < 31; i++) 176 ida_free(ida, 1 << i); 177 178 /* IDA contains a tree */ 179 IDA_BUG_ON(ida, ida_alloc_min(ida, (1 << 20) - 1, GFP_KERNEL) != (1 << 20) - 1); 180 ida_free(ida, 0); 181 for (i = 0; i < 31; i++) 182 ida_free(ida, 1 << i); 183 printk("^^^ \"not allocated\" warnings over\n"); 184 185 ida_free(ida, 3); 186 ida_free(ida, 1023); 187 ida_free(ida, (1 << 20) - 1); 188 189 IDA_BUG_ON(ida, !ida_is_empty(ida)); 190 } 191 192 static DEFINE_IDA(ida); 193 194 static int ida_checks(void) 195 { 196 IDA_BUG_ON(&ida, !ida_is_empty(&ida)); 197 ida_check_alloc(&ida); 198 ida_check_destroy(&ida); 199 ida_check_leaf(&ida, 0); 200 ida_check_leaf(&ida, 1024); 201 ida_check_leaf(&ida, 1024 * 64); 202 ida_check_max(&ida); 203 ida_check_conv(&ida); 204 ida_check_bad_free(&ida); 205 206 printk("IDA: %u of %u tests passed\n", tests_passed, tests_run); 207 return (tests_run != tests_passed) ? 0 : -EINVAL; 208 } 209 210 static void ida_exit(void) 211 { 212 } 213 214 module_init(ida_checks); 215 module_exit(ida_exit); 216 MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>"); 217 MODULE_LICENSE("GPL"); 218