1 // SPDX-License-Identifier: GPL-2.0-only
2 /* Benchmark bitmap, IDA and Maple Tree allocation of variable-sized regions. */
3
4 #include <linux/bitmap.h>
5 #include <linux/idr.h>
6 #include <linux/kernel.h>
7 #include <linux/maple_tree.h>
8 #include <linux/module.h>
9 #include <linux/printk.h>
10 #include <linux/random.h>
11 #include <linux/slab.h>
12 #include <linux/xarray.h>
13
14 #define REGION_MAX_SIZE 32
15
16 static unsigned long *bitmap __initdata;
17 /* One more request guarantees that even an all-ones trace reaches ENOSPC. */
18 static u8 *reg_sz __initdata;
19 static unsigned long *reg_idx __initdata;
20 static unsigned long capacities[64] = { 1000000, 100000, 10000, 1000, 100, 10 };
21 static unsigned int cap_cnt = 6;
22
23 module_param_array(capacities, ulong, &cap_cnt, 0400);
24 MODULE_PARM_DESC(capacities, "Region capacities to benchmark");
25
benchmark_bitmap(unsigned long cap)26 static unsigned long __init benchmark_bitmap(unsigned long cap)
27 {
28 unsigned long cnt, idx;
29 ktime_t alloc_time, free_time;
30 size_t sz;
31
32 bitmap_zero(bitmap, cap);
33 alloc_time = ktime_get();
34 for (cnt = 0; cnt <= cap; cnt++) {
35 idx = bitmap_find_next_zero_area(bitmap, cap, 0, reg_sz[cnt], 0);
36 if (idx >= cap)
37 break;
38
39 reg_idx[cnt] = idx;
40 bitmap_set(bitmap, idx, reg_sz[cnt]);
41 }
42 alloc_time = ktime_get() - alloc_time;
43
44 idx = cnt;
45
46 free_time = ktime_get();
47 while (idx--)
48 bitmap_clear(bitmap, reg_idx[idx], reg_sz[idx]);
49 free_time = ktime_get() - free_time;
50
51 WARN_ON(!bitmap_empty(bitmap, cap));
52
53 sz = BITS_TO_LONGS(cap) * sizeof(unsigned long);
54 pr_err("Bitmap %12llu %12llu %8lu %8lu %10zu\n",
55 alloc_time, free_time, cnt, cap, sz);
56
57 return cnt;
58 }
59
ida_size(unsigned long nr_ids)60 static size_t __init ida_size(unsigned long nr_ids)
61 {
62 unsigned long entries = DIV_ROUND_UP(nr_ids, IDA_BITMAP_BITS);
63 unsigned long bitmaps = nr_ids / IDA_BITMAP_BITS;
64 unsigned long nodes = 0;
65
66 if (nr_ids % IDA_BITMAP_BITS > BITS_PER_XA_VALUE)
67 bitmaps++;
68
69 while (entries > 1) {
70 entries = DIV_ROUND_UP(entries, XA_CHUNK_SIZE);
71 nodes += entries;
72 }
73
74 return sizeof(struct ida) +
75 bitmaps * sizeof(struct ida_bitmap) +
76 nodes * sizeof(struct xa_node);
77 }
78
benchmark_ida(unsigned long cap)79 static unsigned long __init benchmark_ida(unsigned long cap)
80 {
81 struct ida ida = IDA_INIT(ida);
82 unsigned long cnt, idx, off, nr_ids = 0;
83 ktime_t alloc_time, free_time;
84 int id = -ENOSPC;
85
86 alloc_time = ktime_get();
87 for (cnt = 0; cnt <= cap; cnt++) {
88 for (off = 0; off < reg_sz[cnt]; off++) {
89 id = ida_alloc_max(&ida, cap - 1, GFP_KERNEL);
90 if (id < 0)
91 break;
92
93 if (!off)
94 reg_idx[cnt] = id;
95 }
96 if (id < 0) {
97 while (off--)
98 ida_free(&ida, reg_idx[cnt] + off);
99 break;
100 }
101 WARN_ON(id != reg_idx[cnt] + reg_sz[cnt] - 1);
102 nr_ids += reg_sz[cnt];
103 }
104 alloc_time = ktime_get() - alloc_time;
105
106 WARN_ON(id != -ENOSPC);
107
108 idx = cnt;
109
110 free_time = ktime_get();
111 while (idx--) {
112 for (off = 0; off < reg_sz[idx]; off++)
113 ida_free(&ida, reg_idx[idx] + off);
114 }
115 free_time = ktime_get() - free_time;
116
117 WARN_ON(!ida_is_empty(&ida));
118
119 pr_err("IDA %12llu %12llu %8lu %8lu %10zu\n",
120 alloc_time, free_time, cnt, cap, ida_size(nr_ids));
121
122 ida_destroy(&ida);
123 return cnt;
124 }
125
benchmark_maple_tree(unsigned long cap)126 static unsigned long __init benchmark_maple_tree(unsigned long cap)
127 {
128 struct maple_tree mt = MTREE_INIT(mt, MT_FLAGS_ALLOC_RANGE);
129 unsigned long cnt, idx;
130 ktime_t alloc_time, free_time;
131 size_t sz;
132 int ret;
133
134 alloc_time = ktime_get();
135 for (cnt = 0; cnt <= cap; cnt++) {
136 ret = mtree_alloc_range(&mt, &idx, xa_mk_value(cnt + 1),
137 reg_sz[cnt], 0, cap - 1, GFP_KERNEL);
138 if (ret)
139 break;
140
141 reg_idx[cnt] = idx;
142 }
143 alloc_time = ktime_get() - alloc_time;
144
145 WARN_ON(ret != -EBUSY);
146
147 idx = cnt;
148
149 free_time = ktime_get();
150 while (idx--)
151 mtree_erase(&mt, reg_idx[idx]);
152 free_time = ktime_get() - free_time;
153
154 WARN_ON(!mtree_empty(&mt));
155
156 /* Minimum storage assuming fully occupied allocation-range leaf nodes. */
157 sz = sizeof(mt) + DIV_ROUND_UP(cnt, MAPLE_ARANGE64_SLOTS) * sizeof(struct maple_node);
158 pr_err("Maple %12llu %12llu %8lu %8lu %10zu\n",
159 alloc_time, free_time, cnt, cap, sz);
160
161 mtree_destroy(&mt);
162 return cnt;
163 }
164
region_alloc_benchmark(void)165 static int __init region_alloc_benchmark(void)
166 {
167 unsigned long bitmap_count, ida_count, maple_count;
168 unsigned long i, max_cap = 0;
169 int ret = -ENOMEM;
170
171 for (i = 0; i < cap_cnt; i++) {
172 if (capacities[i] == 0) {
173 pr_err("capacity must be nonzero\n");
174 return -EINVAL;
175 }
176 max_cap = max(max_cap, capacities[i]);
177 }
178
179 bitmap = kvmalloc_array(BITS_TO_LONGS(max_cap), sizeof(*bitmap), GFP_KERNEL);
180 reg_sz = kvmalloc_array(max_cap + 1, sizeof(*reg_sz), GFP_KERNEL);
181 reg_idx = kvmalloc_array(max_cap, sizeof(*reg_idx), GFP_KERNEL);
182 if (!bitmap || !reg_sz || !reg_idx)
183 goto out;
184
185 pr_err("\nStart testing bitmap vs IDA vs Maple Tree region allocation\n");
186 pr_err("memory: bitmap is exact; IDA and Maple Tree are lower bounds\n");
187 pr_err("Type alloc (ns) free (ns) regions capacity memory (B)\n");
188
189 for (i = 0; i < cap_cnt; i++) {
190 unsigned long idx, max_size;
191
192 max_size = min(REGION_MAX_SIZE, capacities[i] / 10) ? : 1;
193 for (idx = 0; idx <= capacities[i]; idx++)
194 reg_sz[idx] = get_random_u32_below(max_size) + 1;
195
196 bitmap_count = benchmark_bitmap(capacities[i]);
197 maple_count = benchmark_maple_tree(capacities[i]);
198 ida_count = benchmark_ida(capacities[i]);
199
200 WARN_ON(bitmap_count != ida_count);
201 WARN_ON(bitmap_count != maple_count);
202 }
203
204 /* Return an error so the benchmark can run repeatedly without rmmod. */
205 pr_info("Region allocation benchmark complete\n");
206 ret = -EAGAIN;
207 out:
208 kvfree(reg_idx);
209 kvfree(reg_sz);
210 kvfree(bitmap);
211 return ret;
212 }
213 module_init(region_alloc_benchmark);
214
215 MODULE_AUTHOR("Yury Norov <ynorov@nvidia.com>");
216 MODULE_DESCRIPTION("Benchmark bitmap, IDA and Maple Tree region allocation");
217 MODULE_LICENSE("GPL");
218