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, id: 20); |
39 | ida_free(ida, id: 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, id: 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, base: 0); |
74 | ida_check_destroy_1(ida, base: 1); |
75 | ida_check_destroy_1(ida, base: 1023); |
76 | ida_check_destroy_1(ida, base: 1024); |
77 | ida_check_destroy_1(ida, base: 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, id: 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, id: i + 1); |
136 | ida_free(ida, id: 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, id: 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, id: i - 1); |
150 | IDA_BUG_ON(ida, !ida_is_empty(ida)); |
151 | } |
152 | |
153 | static DEFINE_IDA(ida); |
154 | |
155 | static int ida_checks(void) |
156 | { |
157 | IDA_BUG_ON(&ida, !ida_is_empty(&ida)); |
158 | ida_check_alloc(ida: &ida); |
159 | ida_check_destroy(ida: &ida); |
160 | ida_check_leaf(ida: &ida, base: 0); |
161 | ida_check_leaf(ida: &ida, base: 1024); |
162 | ida_check_leaf(ida: &ida, base: 1024 * 64); |
163 | ida_check_max(ida: &ida); |
164 | ida_check_conv(ida: &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 | |
170 | static void ida_exit(void) |
171 | { |
172 | } |
173 | |
174 | module_init(ida_checks); |
175 | module_exit(ida_exit); |
176 | MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>" ); |
177 | MODULE_LICENSE("GPL" ); |
178 | |