ida: Use exceptional entries for small IDAs
We can use the root entry as a bitmap and save allocating a 128 byte
bitmap for an IDA that contains only a few entries (30 on a 32-bit
machine, 62 on a 64-bit machine). This costs about 300 bytes of kernel
text on x86-64, so as long as 3 IDAs fall into this category, this
is a net win for memory consumption.
Thanks to Rasmus Villemoes for his work documenting the problem and
collecting statistics on IDAs.
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 4dffad9..5908112 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -11,6 +11,7 @@
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
* more details.
*/
+#include <linux/bitmap.h>
#include <linux/idr.h>
#include <linux/slab.h>
#include <linux/kernel.h>
@@ -214,7 +215,7 @@ void ida_check_nomem(void)
DEFINE_IDA(ida);
int id, err;
- err = ida_get_new(&ida, &id);
+ err = ida_get_new_above(&ida, 256, &id);
assert(err == -EAGAIN);
err = ida_get_new_above(&ida, 1UL << 30, &id);
assert(err == -EAGAIN);
@@ -247,6 +248,66 @@ void ida_check_leaf(void)
}
/*
+ * Check handling of conversions between exceptional entries and full bitmaps.
+ */
+void ida_check_conv(void)
+{
+ DEFINE_IDA(ida);
+ int id;
+ unsigned long i;
+
+ for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) {
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new_above(&ida, i + 1, &id));
+ assert(id == i + 1);
+ assert(!ida_get_new_above(&ida, i + BITS_PER_LONG, &id));
+ assert(id == i + BITS_PER_LONG);
+ ida_remove(&ida, i + 1);
+ ida_remove(&ida, i + BITS_PER_LONG);
+ assert(ida_is_empty(&ida));
+ }
+
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+
+ for (i = 0; i < IDA_BITMAP_BITS * 2; i++) {
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new(&ida, &id));
+ assert(id == i);
+ }
+
+ for (i = IDA_BITMAP_BITS * 2; i > 0; i--) {
+ ida_remove(&ida, i - 1);
+ }
+ assert(ida_is_empty(&ida));
+
+ for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++) {
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ assert(!ida_get_new(&ida, &id));
+ assert(id == i);
+ }
+
+ for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--) {
+ ida_remove(&ida, i - 1);
+ }
+ assert(ida_is_empty(&ida));
+
+ radix_tree_cpu_dead(1);
+ for (i = 0; i < 1000000; i++) {
+ int err = ida_get_new(&ida, &id);
+ if (err == -EAGAIN) {
+ assert((i % IDA_BITMAP_BITS) == (BITS_PER_LONG - 2));
+ assert(ida_pre_get(&ida, GFP_KERNEL));
+ err = ida_get_new(&ida, &id);
+ } else {
+ assert((i % IDA_BITMAP_BITS) != (BITS_PER_LONG - 2));
+ }
+ assert(!err);
+ assert(id == i);
+ }
+ ida_destroy(&ida);
+}
+
+/*
* Check allocations up to and slightly above the maximum allowed (2^31-1) ID.
* Allocating up to 2^31-1 should succeed, and then allocating the next one
* should fail.
@@ -273,6 +334,34 @@ void ida_check_max(void)
}
}
+void ida_check_random(void)
+{
+ DEFINE_IDA(ida);
+ DECLARE_BITMAP(bitmap, 2048);
+ int id;
+ unsigned int i;
+ time_t s = time(NULL);
+
+ repeat:
+ memset(bitmap, 0, sizeof(bitmap));
+ for (i = 0; i < 100000; i++) {
+ int i = rand();
+ int bit = i & 2047;
+ if (test_bit(bit, bitmap)) {
+ __clear_bit(bit, bitmap);
+ ida_remove(&ida, bit);
+ } else {
+ __set_bit(bit, bitmap);
+ ida_pre_get(&ida, GFP_KERNEL);
+ assert(!ida_get_new_above(&ida, bit, &id));
+ assert(id == bit);
+ }
+ }
+ ida_destroy(&ida);
+ if (time(NULL) < s + 10)
+ goto repeat;
+}
+
void ida_checks(void)
{
DEFINE_IDA(ida);
@@ -337,6 +426,8 @@ void ida_checks(void)
ida_check_leaf();
ida_check_max();
+ ida_check_conv();
+ ida_check_random();
radix_tree_cpu_dead(1);
}