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