1 /* 2 * idr-test.c: Test the IDR API 3 * Copyright (c) 2016 Matthew Wilcox <willy@infradead.org> 4 * 5 * This program is free software; you can redistribute it and/or modify it 6 * under the terms and conditions of the GNU General Public License, 7 * version 2, as published by the Free Software Foundation. 8 * 9 * This program is distributed in the hope it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 12 * more details. 13 */ 14 #include <linux/bitmap.h> 15 #include <linux/idr.h> 16 #include <linux/slab.h> 17 #include <linux/kernel.h> 18 #include <linux/errno.h> 19 20 #include "test.h" 21 22 #define DUMMY_PTR ((void *)0x12) 23 24 int item_idr_free(int id, void *p, void *data) 25 { 26 struct item *item = p; 27 assert(item->index == id); 28 free(p); 29 30 return 0; 31 } 32 33 void item_idr_remove(struct idr *idr, int id) 34 { 35 struct item *item = idr_find(idr, id); 36 assert(item->index == id); 37 idr_remove(idr, id); 38 free(item); 39 } 40 41 void idr_alloc_test(void) 42 { 43 unsigned long i; 44 DEFINE_IDR(idr); 45 46 assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0, 0x4000, GFP_KERNEL) == 0); 47 assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0x3ffd, 0x4000, GFP_KERNEL) == 0x3ffd); 48 idr_remove(&idr, 0x3ffd); 49 idr_remove(&idr, 0); 50 51 for (i = 0x3ffe; i < 0x4003; i++) { 52 int id; 53 struct item *item; 54 55 if (i < 0x4000) 56 item = item_create(i, 0); 57 else 58 item = item_create(i - 0x3fff, 0); 59 60 id = idr_alloc_cyclic(&idr, item, 1, 0x4000, GFP_KERNEL); 61 assert(id == item->index); 62 } 63 64 idr_for_each(&idr, item_idr_free, &idr); 65 idr_destroy(&idr); 66 } 67 68 void idr_replace_test(void) 69 { 70 DEFINE_IDR(idr); 71 72 idr_alloc(&idr, (void *)-1, 10, 11, GFP_KERNEL); 73 idr_replace(&idr, &idr, 10); 74 75 idr_destroy(&idr); 76 } 77 78 /* 79 * Unlike the radix tree, you can put a NULL pointer -- with care -- into 80 * the IDR. Some interfaces, like idr_find() do not distinguish between 81 * "present, value is NULL" and "not present", but that's exactly what some 82 * users want. 83 */ 84 void idr_null_test(void) 85 { 86 int i; 87 DEFINE_IDR(idr); 88 89 assert(idr_is_empty(&idr)); 90 91 assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0); 92 assert(!idr_is_empty(&idr)); 93 idr_remove(&idr, 0); 94 assert(idr_is_empty(&idr)); 95 96 assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0); 97 assert(!idr_is_empty(&idr)); 98 idr_destroy(&idr); 99 assert(idr_is_empty(&idr)); 100 101 for (i = 0; i < 10; i++) { 102 assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == i); 103 } 104 105 assert(idr_replace(&idr, DUMMY_PTR, 3) == NULL); 106 assert(idr_replace(&idr, DUMMY_PTR, 4) == NULL); 107 assert(idr_replace(&idr, NULL, 4) == DUMMY_PTR); 108 assert(idr_replace(&idr, DUMMY_PTR, 11) == ERR_PTR(-ENOENT)); 109 idr_remove(&idr, 5); 110 assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 5); 111 idr_remove(&idr, 5); 112 113 for (i = 0; i < 9; i++) { 114 idr_remove(&idr, i); 115 assert(!idr_is_empty(&idr)); 116 } 117 idr_remove(&idr, 8); 118 assert(!idr_is_empty(&idr)); 119 idr_remove(&idr, 9); 120 assert(idr_is_empty(&idr)); 121 122 assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0); 123 assert(idr_replace(&idr, DUMMY_PTR, 3) == ERR_PTR(-ENOENT)); 124 assert(idr_replace(&idr, DUMMY_PTR, 0) == NULL); 125 assert(idr_replace(&idr, NULL, 0) == DUMMY_PTR); 126 127 idr_destroy(&idr); 128 assert(idr_is_empty(&idr)); 129 130 for (i = 1; i < 10; i++) { 131 assert(idr_alloc(&idr, NULL, 1, 0, GFP_KERNEL) == i); 132 } 133 134 idr_destroy(&idr); 135 assert(idr_is_empty(&idr)); 136 } 137 138 void idr_nowait_test(void) 139 { 140 unsigned int i; 141 DEFINE_IDR(idr); 142 143 idr_preload(GFP_KERNEL); 144 145 for (i = 0; i < 3; i++) { 146 struct item *item = item_create(i, 0); 147 assert(idr_alloc(&idr, item, i, i + 1, GFP_NOWAIT) == i); 148 } 149 150 idr_preload_end(); 151 152 idr_for_each(&idr, item_idr_free, &idr); 153 idr_destroy(&idr); 154 } 155 156 void idr_checks(void) 157 { 158 unsigned long i; 159 DEFINE_IDR(idr); 160 161 for (i = 0; i < 10000; i++) { 162 struct item *item = item_create(i, 0); 163 assert(idr_alloc(&idr, item, 0, 20000, GFP_KERNEL) == i); 164 } 165 166 assert(idr_alloc(&idr, DUMMY_PTR, 5, 30, GFP_KERNEL) < 0); 167 168 for (i = 0; i < 5000; i++) 169 item_idr_remove(&idr, i); 170 171 idr_remove(&idr, 3); 172 173 idr_for_each(&idr, item_idr_free, &idr); 174 idr_destroy(&idr); 175 176 assert(idr_is_empty(&idr)); 177 178 idr_remove(&idr, 3); 179 idr_remove(&idr, 0); 180 181 for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) { 182 struct item *item = item_create(i, 0); 183 assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i); 184 } 185 assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i, GFP_KERNEL) == -ENOSPC); 186 187 idr_for_each(&idr, item_idr_free, &idr); 188 idr_destroy(&idr); 189 idr_destroy(&idr); 190 191 assert(idr_is_empty(&idr)); 192 193 for (i = 1; i < 10000; i++) { 194 struct item *item = item_create(i, 0); 195 assert(idr_alloc(&idr, item, 1, 20000, GFP_KERNEL) == i); 196 } 197 198 idr_for_each(&idr, item_idr_free, &idr); 199 idr_destroy(&idr); 200 201 idr_replace_test(); 202 idr_alloc_test(); 203 idr_null_test(); 204 idr_nowait_test(); 205 } 206 207 /* 208 * Check that we get the correct error when we run out of memory doing 209 * allocations. To ensure we run out of memory, just "forget" to preload. 210 * The first test is for not having a bitmap available, and the second test 211 * is for not being able to allocate a level of the radix tree. 212 */ 213 void ida_check_nomem(void) 214 { 215 DEFINE_IDA(ida); 216 int id, err; 217 218 err = ida_get_new_above(&ida, 256, &id); 219 assert(err == -EAGAIN); 220 err = ida_get_new_above(&ida, 1UL << 30, &id); 221 assert(err == -EAGAIN); 222 } 223 224 /* 225 * Check what happens when we fill a leaf and then delete it. This may 226 * discover mishandling of IDR_FREE. 227 */ 228 void ida_check_leaf(void) 229 { 230 DEFINE_IDA(ida); 231 int id; 232 unsigned long i; 233 234 for (i = 0; i < IDA_BITMAP_BITS; i++) { 235 assert(ida_pre_get(&ida, GFP_KERNEL)); 236 assert(!ida_get_new(&ida, &id)); 237 assert(id == i); 238 } 239 240 ida_destroy(&ida); 241 assert(ida_is_empty(&ida)); 242 243 assert(ida_pre_get(&ida, GFP_KERNEL)); 244 assert(!ida_get_new(&ida, &id)); 245 assert(id == 0); 246 ida_destroy(&ida); 247 assert(ida_is_empty(&ida)); 248 } 249 250 /* 251 * Check handling of conversions between exceptional entries and full bitmaps. 252 */ 253 void ida_check_conv(void) 254 { 255 DEFINE_IDA(ida); 256 int id; 257 unsigned long i; 258 259 for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) { 260 assert(ida_pre_get(&ida, GFP_KERNEL)); 261 assert(!ida_get_new_above(&ida, i + 1, &id)); 262 assert(id == i + 1); 263 assert(!ida_get_new_above(&ida, i + BITS_PER_LONG, &id)); 264 assert(id == i + BITS_PER_LONG); 265 ida_remove(&ida, i + 1); 266 ida_remove(&ida, i + BITS_PER_LONG); 267 assert(ida_is_empty(&ida)); 268 } 269 270 assert(ida_pre_get(&ida, GFP_KERNEL)); 271 272 for (i = 0; i < IDA_BITMAP_BITS * 2; i++) { 273 assert(ida_pre_get(&ida, GFP_KERNEL)); 274 assert(!ida_get_new(&ida, &id)); 275 assert(id == i); 276 } 277 278 for (i = IDA_BITMAP_BITS * 2; i > 0; i--) { 279 ida_remove(&ida, i - 1); 280 } 281 assert(ida_is_empty(&ida)); 282 283 for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++) { 284 assert(ida_pre_get(&ida, GFP_KERNEL)); 285 assert(!ida_get_new(&ida, &id)); 286 assert(id == i); 287 } 288 289 for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--) { 290 ida_remove(&ida, i - 1); 291 } 292 assert(ida_is_empty(&ida)); 293 294 radix_tree_cpu_dead(1); 295 for (i = 0; i < 1000000; i++) { 296 int err = ida_get_new(&ida, &id); 297 if (err == -EAGAIN) { 298 assert((i % IDA_BITMAP_BITS) == (BITS_PER_LONG - 2)); 299 assert(ida_pre_get(&ida, GFP_KERNEL)); 300 err = ida_get_new(&ida, &id); 301 } else { 302 assert((i % IDA_BITMAP_BITS) != (BITS_PER_LONG - 2)); 303 } 304 assert(!err); 305 assert(id == i); 306 } 307 ida_destroy(&ida); 308 } 309 310 /* 311 * Check allocations up to and slightly above the maximum allowed (2^31-1) ID. 312 * Allocating up to 2^31-1 should succeed, and then allocating the next one 313 * should fail. 314 */ 315 void ida_check_max(void) 316 { 317 DEFINE_IDA(ida); 318 int id, err; 319 unsigned long i, j; 320 321 for (j = 1; j < 65537; j *= 2) { 322 unsigned long base = (1UL << 31) - j; 323 for (i = 0; i < j; i++) { 324 assert(ida_pre_get(&ida, GFP_KERNEL)); 325 assert(!ida_get_new_above(&ida, base, &id)); 326 assert(id == base + i); 327 } 328 assert(ida_pre_get(&ida, GFP_KERNEL)); 329 err = ida_get_new_above(&ida, base, &id); 330 assert(err == -ENOSPC); 331 ida_destroy(&ida); 332 assert(ida_is_empty(&ida)); 333 rcu_barrier(); 334 } 335 } 336 337 void ida_check_random(void) 338 { 339 DEFINE_IDA(ida); 340 DECLARE_BITMAP(bitmap, 2048); 341 int id; 342 unsigned int i; 343 time_t s = time(NULL); 344 345 repeat: 346 memset(bitmap, 0, sizeof(bitmap)); 347 for (i = 0; i < 100000; i++) { 348 int i = rand(); 349 int bit = i & 2047; 350 if (test_bit(bit, bitmap)) { 351 __clear_bit(bit, bitmap); 352 ida_remove(&ida, bit); 353 } else { 354 __set_bit(bit, bitmap); 355 ida_pre_get(&ida, GFP_KERNEL); 356 assert(!ida_get_new_above(&ida, bit, &id)); 357 assert(id == bit); 358 } 359 } 360 ida_destroy(&ida); 361 if (time(NULL) < s + 10) 362 goto repeat; 363 } 364 365 void ida_checks(void) 366 { 367 DEFINE_IDA(ida); 368 int id; 369 unsigned long i; 370 371 radix_tree_cpu_dead(1); 372 ida_check_nomem(); 373 374 for (i = 0; i < 10000; i++) { 375 assert(ida_pre_get(&ida, GFP_KERNEL)); 376 assert(!ida_get_new(&ida, &id)); 377 assert(id == i); 378 } 379 380 ida_remove(&ida, 20); 381 ida_remove(&ida, 21); 382 for (i = 0; i < 3; i++) { 383 assert(ida_pre_get(&ida, GFP_KERNEL)); 384 assert(!ida_get_new(&ida, &id)); 385 if (i == 2) 386 assert(id == 10000); 387 } 388 389 for (i = 0; i < 5000; i++) 390 ida_remove(&ida, i); 391 392 assert(ida_pre_get(&ida, GFP_KERNEL)); 393 assert(!ida_get_new_above(&ida, 5000, &id)); 394 assert(id == 10001); 395 396 ida_destroy(&ida); 397 398 assert(ida_is_empty(&ida)); 399 400 assert(ida_pre_get(&ida, GFP_KERNEL)); 401 assert(!ida_get_new_above(&ida, 1, &id)); 402 assert(id == 1); 403 404 ida_remove(&ida, id); 405 assert(ida_is_empty(&ida)); 406 ida_destroy(&ida); 407 assert(ida_is_empty(&ida)); 408 409 assert(ida_pre_get(&ida, GFP_KERNEL)); 410 assert(!ida_get_new_above(&ida, 1, &id)); 411 ida_destroy(&ida); 412 assert(ida_is_empty(&ida)); 413 414 assert(ida_pre_get(&ida, GFP_KERNEL)); 415 assert(!ida_get_new_above(&ida, 1, &id)); 416 assert(id == 1); 417 assert(ida_pre_get(&ida, GFP_KERNEL)); 418 assert(!ida_get_new_above(&ida, 1025, &id)); 419 assert(id == 1025); 420 assert(ida_pre_get(&ida, GFP_KERNEL)); 421 assert(!ida_get_new_above(&ida, 10000, &id)); 422 assert(id == 10000); 423 ida_remove(&ida, 1025); 424 ida_destroy(&ida); 425 assert(ida_is_empty(&ida)); 426 427 ida_check_leaf(); 428 ida_check_max(); 429 ida_check_conv(); 430 ida_check_random(); 431 432 radix_tree_cpu_dead(1); 433 } 434 435 int __weak main(void) 436 { 437 radix_tree_init(); 438 idr_checks(); 439 ida_checks(); 440 rcu_barrier(); 441 if (nr_allocated) 442 printf("nr_allocated = %d\n", nr_allocated); 443 return 0; 444 } 445