219 lines · c
1// SPDX-License-Identifier: GPL-2.0+2/*3 * test_ida.c: Test the IDA API4 * Copyright (c) 2016-2018 Microsoft Corporation5 * Copyright (c) 2018 Oracle Corporation6 * Author: Matthew Wilcox <willy@infradead.org>7 */8 9#include <linux/idr.h>10#include <linux/module.h>11 12static unsigned int tests_run;13static unsigned int tests_passed;14 15#ifdef __KERNEL__16static void ida_dump(struct ida *ida) { }17#endif18#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 */31static 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, 20);39 ida_free(ida, 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, 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 */57static 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 */66static 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, 0);74 ida_check_destroy_1(ida, 1);75 ida_check_destroy_1(ida, 1023);76 ida_check_destroy_1(ida, 1024);77 ida_check_destroy_1(ida, 12345678);78}79 80/*81 * Check what happens when we fill a leaf and then delete it. This may82 * discover mishandling of IDR_FREE.83 */84static 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, 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 one105 * should fail.106 */107static 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 */127static 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, i + 1);136 ida_free(ida, 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, 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, i - 1);150 IDA_BUG_ON(ida, !ida_is_empty(ida));151}152 153/*154 * Check various situations where we attempt to free an ID we don't own.155 */156static void ida_check_bad_free(struct ida *ida)157{158 unsigned long i;159 160 printk("vvv Ignore \"not allocated\" warnings\n");161 /* IDA is empty; all of these will fail */162 ida_free(ida, 0);163 for (i = 0; i < 31; i++)164 ida_free(ida, 1 << i);165 166 /* IDA contains a single value entry */167 IDA_BUG_ON(ida, ida_alloc_min(ida, 3, GFP_KERNEL) != 3);168 ida_free(ida, 0);169 for (i = 0; i < 31; i++)170 ida_free(ida, 1 << i);171 172 /* IDA contains a single bitmap */173 IDA_BUG_ON(ida, ida_alloc_min(ida, 1023, GFP_KERNEL) != 1023);174 ida_free(ida, 0);175 for (i = 0; i < 31; i++)176 ida_free(ida, 1 << i);177 178 /* IDA contains a tree */179 IDA_BUG_ON(ida, ida_alloc_min(ida, (1 << 20) - 1, GFP_KERNEL) != (1 << 20) - 1);180 ida_free(ida, 0);181 for (i = 0; i < 31; i++)182 ida_free(ida, 1 << i);183 printk("^^^ \"not allocated\" warnings over\n");184 185 ida_free(ida, 3);186 ida_free(ida, 1023);187 ida_free(ida, (1 << 20) - 1);188 189 IDA_BUG_ON(ida, !ida_is_empty(ida));190}191 192static DEFINE_IDA(ida);193 194static int ida_checks(void)195{196 IDA_BUG_ON(&ida, !ida_is_empty(&ida));197 ida_check_alloc(&ida);198 ida_check_destroy(&ida);199 ida_check_leaf(&ida, 0);200 ida_check_leaf(&ida, 1024);201 ida_check_leaf(&ida, 1024 * 64);202 ida_check_max(&ida);203 ida_check_conv(&ida);204 ida_check_bad_free(&ida);205 206 printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);207 return (tests_run != tests_passed) ? 0 : -EINVAL;208}209 210static void ida_exit(void)211{212}213 214module_init(ida_checks);215module_exit(ida_exit);216MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");217MODULE_DESCRIPTION("Test the IDA API");218MODULE_LICENSE("GPL");219