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