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 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 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 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 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 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