^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0-only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * idr-test.c: Test the IDR API
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) * Copyright (c) 2016 Matthew Wilcox <willy@infradead.org>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) #include <linux/bitmap.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #include <linux/idr.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #include <linux/errno.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) #include "test.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) #define DUMMY_PTR ((void *)0x10)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) int item_idr_free(int id, void *p, void *data)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) struct item *item = p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) assert(item->index == id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) free(p);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) void item_idr_remove(struct idr *idr, int id)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) struct item *item = idr_find(idr, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) assert(item->index == id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) idr_remove(idr, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) free(item);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) void idr_alloc_test(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) unsigned long i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) DEFINE_IDR(idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0, 0x4000, GFP_KERNEL) == 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0x3ffd, 0x4000, GFP_KERNEL) == 0x3ffd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) idr_remove(&idr, 0x3ffd);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) idr_remove(&idr, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) for (i = 0x3ffe; i < 0x4003; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) int id;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) struct item *item;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) if (i < 0x4000)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) item = item_create(i, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) item = item_create(i - 0x3fff, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) id = idr_alloc_cyclic(&idr, item, 1, 0x4000, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) assert(id == item->index);
^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) idr_for_each(&idr, item_idr_free, &idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) idr_destroy(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) void idr_replace_test(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) DEFINE_IDR(idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) idr_alloc(&idr, (void *)-1, 10, 11, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) idr_replace(&idr, &idr, 10);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) idr_destroy(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) * Unlike the radix tree, you can put a NULL pointer -- with care -- into
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) * the IDR. Some interfaces, like idr_find() do not distinguish between
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) * "present, value is NULL" and "not present", but that's exactly what some
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) * users want.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) void idr_null_test(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) DEFINE_IDR(idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) assert(idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) assert(!idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) idr_remove(&idr, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) assert(idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) assert(!idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) idr_destroy(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) assert(idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) for (i = 0; i < 10; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) assert(idr_replace(&idr, DUMMY_PTR, 3) == NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) assert(idr_replace(&idr, DUMMY_PTR, 4) == NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) assert(idr_replace(&idr, NULL, 4) == DUMMY_PTR);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) assert(idr_replace(&idr, DUMMY_PTR, 11) == ERR_PTR(-ENOENT));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) idr_remove(&idr, 5);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 5);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) idr_remove(&idr, 5);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) for (i = 0; i < 9; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) idr_remove(&idr, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) assert(!idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) idr_remove(&idr, 8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) assert(!idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) idr_remove(&idr, 9);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) assert(idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) assert(idr_replace(&idr, DUMMY_PTR, 3) == ERR_PTR(-ENOENT));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) assert(idr_replace(&idr, DUMMY_PTR, 0) == NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) assert(idr_replace(&idr, NULL, 0) == DUMMY_PTR);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) idr_destroy(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) assert(idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) for (i = 1; i < 10; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) assert(idr_alloc(&idr, NULL, 1, 0, GFP_KERNEL) == i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) idr_destroy(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) assert(idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) void idr_nowait_test(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) DEFINE_IDR(idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) idr_preload(GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) for (i = 0; i < 3; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) struct item *item = item_create(i, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) assert(idr_alloc(&idr, item, i, i + 1, GFP_NOWAIT) == i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) idr_preload_end();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) idr_for_each(&idr, item_idr_free, &idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) idr_destroy(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) void idr_get_next_test(int base)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) unsigned long i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) int nextid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) DEFINE_IDR(idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) idr_init_base(&idr, base);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) int indices[] = {4, 7, 9, 15, 65, 128, 1000, 99999, 0};
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) for(i = 0; indices[i]; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) struct item *item = item_create(indices[i], 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) assert(idr_alloc(&idr, item, indices[i], indices[i+1],
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) GFP_KERNEL) == indices[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) for(i = 0, nextid = 0; indices[i]; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) idr_get_next(&idr, &nextid);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) assert(nextid == indices[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) nextid++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) idr_for_each(&idr, item_idr_free, &idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) idr_destroy(&idr);
^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) int idr_u32_cb(int id, void *ptr, void *data)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) BUG_ON(id < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) BUG_ON(ptr != DUMMY_PTR);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) void idr_u32_test1(struct idr *idr, u32 handle)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) static bool warned = false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) u32 id = handle;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) int sid = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) void *ptr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) BUG_ON(idr_alloc_u32(idr, DUMMY_PTR, &id, id, GFP_KERNEL));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) BUG_ON(id != handle);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) BUG_ON(idr_alloc_u32(idr, DUMMY_PTR, &id, id, GFP_KERNEL) != -ENOSPC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) BUG_ON(id != handle);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) if (!warned && id > INT_MAX)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) printk("vvv Ignore these warnings\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) ptr = idr_get_next(idr, &sid);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) if (id > INT_MAX) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) BUG_ON(ptr != NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) BUG_ON(sid != 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) BUG_ON(ptr != DUMMY_PTR);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) BUG_ON(sid != id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) idr_for_each(idr, idr_u32_cb, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) if (!warned && id > INT_MAX) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) printk("^^^ Warnings over\n");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) warned = true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) BUG_ON(idr_remove(idr, id) != DUMMY_PTR);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) BUG_ON(!idr_is_empty(idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) void idr_u32_test(int base)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) DEFINE_IDR(idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) idr_init_base(&idr, base);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) idr_u32_test1(&idr, 10);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) idr_u32_test1(&idr, 0x7fffffff);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) idr_u32_test1(&idr, 0x80000000);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) idr_u32_test1(&idr, 0x80000001);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) idr_u32_test1(&idr, 0xffe00000);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) idr_u32_test1(&idr, 0xffffffff);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) static void idr_align_test(struct idr *idr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) char name[] = "Motorola 68000";
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) int i, id;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) void *entry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) for (i = 0; i < 9; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) idr_for_each_entry(idr, entry, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) idr_destroy(idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) for (i = 1; i < 10; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) idr_for_each_entry(idr, entry, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) idr_destroy(idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) for (i = 2; i < 11; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) idr_for_each_entry(idr, entry, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) idr_destroy(idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) for (i = 3; i < 12; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 3);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) idr_for_each_entry(idr, entry, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) idr_destroy(idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) for (i = 0; i < 8; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) BUG_ON(idr_alloc(idr, &name[i + 1], 0, 0, GFP_KERNEL) != 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) idr_for_each_entry(idr, entry, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) idr_remove(idr, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) idr_for_each_entry(idr, entry, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) idr_remove(idr, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) BUG_ON(!idr_is_empty(idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) for (i = 0; i < 8; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) BUG_ON(idr_alloc(idr, NULL, 0, 0, GFP_KERNEL) != 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) idr_for_each_entry(idr, entry, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) idr_replace(idr, &name[i], 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) idr_for_each_entry(idr, entry, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) BUG_ON(idr_find(idr, 0) != &name[i]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) idr_remove(idr, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) for (i = 0; i < 8; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) BUG_ON(idr_alloc(idr, NULL, 0, 0, GFP_KERNEL) != 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) idr_remove(idr, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) idr_for_each_entry(idr, entry, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) idr_replace(idr, &name[i + 1], 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) idr_for_each_entry(idr, entry, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) idr_remove(idr, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) DEFINE_IDR(find_idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) static void *idr_throbber(void *arg)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) time_t start = time(NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) int id = *(int *)arg;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) rcu_register_thread();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) idr_alloc(&find_idr, xa_mk_value(id), id, id + 1, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) idr_remove(&find_idr, id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) } while (time(NULL) < start + 10);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) rcu_unregister_thread();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) void idr_find_test_1(int anchor_id, int throbber_id)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) pthread_t throbber;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) time_t start = time(NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) BUG_ON(idr_alloc(&find_idr, xa_mk_value(anchor_id), anchor_id,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) anchor_id + 1, GFP_KERNEL) != anchor_id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) pthread_create(&throbber, NULL, idr_throbber, &throbber_id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) rcu_read_lock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) int id = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) void *entry = idr_get_next(&find_idr, &id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) rcu_read_unlock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) BUG_ON(entry != xa_mk_value(id));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) rcu_read_lock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) } while (time(NULL) < start + 11);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) rcu_read_unlock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) pthread_join(throbber, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) idr_remove(&find_idr, anchor_id);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) BUG_ON(!idr_is_empty(&find_idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) void idr_find_test(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) idr_find_test_1(100000, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) idr_find_test_1(0, 100000);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) void idr_checks(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) unsigned long i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) DEFINE_IDR(idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) for (i = 0; i < 10000; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) struct item *item = item_create(i, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) assert(idr_alloc(&idr, item, 0, 20000, GFP_KERNEL) == i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) assert(idr_alloc(&idr, DUMMY_PTR, 5, 30, GFP_KERNEL) < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) for (i = 0; i < 5000; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) item_idr_remove(&idr, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) idr_remove(&idr, 3);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) idr_for_each(&idr, item_idr_free, &idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) idr_destroy(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) assert(idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) idr_remove(&idr, 3);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) idr_remove(&idr, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) idr_remove(&idr, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) for (i = 1; i < RADIX_TREE_MAP_SIZE; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) idr_remove(&idr, 1 << 30);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) idr_destroy(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) struct item *item = item_create(i, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i, GFP_KERNEL) == -ENOSPC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i + 10, GFP_KERNEL) == -ENOSPC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) idr_for_each(&idr, item_idr_free, &idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) idr_destroy(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) idr_destroy(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) assert(idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) idr_set_cursor(&idr, INT_MAX - 3UL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) for (i = INT_MAX - 3UL; i < INT_MAX + 3UL; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) struct item *item;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) unsigned int id;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) if (i <= INT_MAX)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) item = item_create(i, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) item = item_create(i - INT_MAX - 1, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) id = idr_alloc_cyclic(&idr, item, 0, 0, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) assert(id == item->index);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) idr_for_each(&idr, item_idr_free, &idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) idr_destroy(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) assert(idr_is_empty(&idr));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) for (i = 1; i < 10000; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) struct item *item = item_create(i, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) assert(idr_alloc(&idr, item, 1, 20000, GFP_KERNEL) == i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) idr_for_each(&idr, item_idr_free, &idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) idr_destroy(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) idr_replace_test();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) idr_alloc_test();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) idr_null_test();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) idr_nowait_test();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) idr_get_next_test(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) idr_get_next_test(1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) idr_get_next_test(4);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) idr_u32_test(4);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) idr_u32_test(1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) idr_u32_test(0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) idr_align_test(&idr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) idr_find_test();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) #define module_init(x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) #define module_exit(x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) #define MODULE_AUTHOR(x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) #define MODULE_LICENSE(x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) #define dump_stack() assert(0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) void ida_dump(struct ida *);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) #include "../../../lib/test_ida.c"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) * Check that we get the correct error when we run out of memory doing
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) * allocations. In userspace, GFP_NOWAIT will always fail an allocation.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) * The first test is for not having a bitmap available, and the second test
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) * is for not being able to allocate a level of the radix tree.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) void ida_check_nomem(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) DEFINE_IDA(ida);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) int id;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) id = ida_alloc_min(&ida, 256, GFP_NOWAIT);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) IDA_BUG_ON(&ida, id != -ENOMEM);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) id = ida_alloc_min(&ida, 1UL << 30, GFP_NOWAIT);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) IDA_BUG_ON(&ida, id != -ENOMEM);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) IDA_BUG_ON(&ida, !ida_is_empty(&ida));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) * Check handling of conversions between exceptional entries and full bitmaps.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) void ida_check_conv_user(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) DEFINE_IDA(ida);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) unsigned long i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) for (i = 0; i < 1000000; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) int id = ida_alloc(&ida, GFP_NOWAIT);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) if (id == -ENOMEM) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) IDA_BUG_ON(&ida, ((i % IDA_BITMAP_BITS) !=
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) BITS_PER_XA_VALUE) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) ((i % IDA_BITMAP_BITS) != 0));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) id = ida_alloc(&ida, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) IDA_BUG_ON(&ida, (i % IDA_BITMAP_BITS) ==
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) BITS_PER_XA_VALUE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) IDA_BUG_ON(&ida, id != i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) ida_destroy(&ida);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) void ida_check_random(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) DEFINE_IDA(ida);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) DECLARE_BITMAP(bitmap, 2048);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) unsigned int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) time_t s = time(NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) repeat:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) memset(bitmap, 0, sizeof(bitmap));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) for (i = 0; i < 100000; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) int i = rand();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) int bit = i & 2047;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) if (test_bit(bit, bitmap)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) __clear_bit(bit, bitmap);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) ida_free(&ida, bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) __set_bit(bit, bitmap);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) IDA_BUG_ON(&ida, ida_alloc_min(&ida, bit, GFP_KERNEL)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) != bit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) ida_destroy(&ida);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) if (time(NULL) < s + 10)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) goto repeat;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) void ida_simple_get_remove_test(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) DEFINE_IDA(ida);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) unsigned long i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) for (i = 0; i < 10000; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) assert(ida_simple_get(&ida, 0, 20000, GFP_KERNEL) == i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) assert(ida_simple_get(&ida, 5, 30, GFP_KERNEL) < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) for (i = 0; i < 10000; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) ida_simple_remove(&ida, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) assert(ida_is_empty(&ida));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) ida_destroy(&ida);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) void user_ida_checks(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) radix_tree_cpu_dead(1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) ida_check_nomem();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) ida_check_conv_user();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) ida_check_random();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) ida_simple_get_remove_test();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) radix_tree_cpu_dead(1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522) static void *ida_random_fn(void *arg)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) rcu_register_thread();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) ida_check_random();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) rcu_unregister_thread();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) static void *ida_leak_fn(void *arg)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) struct ida *ida = arg;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) time_t s = time(NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) int i, ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) rcu_register_thread();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) do for (i = 0; i < 1000; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) ret = ida_alloc_range(ida, 128, 128, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) if (ret >= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) ida_free(ida, 128);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) } while (time(NULL) < s + 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) rcu_unregister_thread();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) void ida_thread_tests(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) DEFINE_IDA(ida);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) pthread_t threads[20];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) for (i = 0; i < ARRAY_SIZE(threads); i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) if (pthread_create(&threads[i], NULL, ida_random_fn, NULL)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) perror("creating ida thread");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) exit(1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) while (i--)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) pthread_join(threads[i], NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) for (i = 0; i < ARRAY_SIZE(threads); i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) if (pthread_create(&threads[i], NULL, ida_leak_fn, &ida)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565) perror("creating ida thread");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) exit(1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) while (i--)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) pthread_join(threads[i], NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) assert(ida_is_empty(&ida));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) void ida_tests(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) user_ida_checks();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) ida_checks();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) ida_exit();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) ida_thread_tests();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) int __weak main(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) rcu_register_thread();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585) radix_tree_init();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) idr_checks();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) ida_tests();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) radix_tree_cpu_dead(1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) rcu_barrier();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590) if (nr_allocated)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) printf("nr_allocated = %d\n", nr_allocated);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592) rcu_unregister_thread();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags
| Donate