diff options
author | Matthew Wilcox <mawilcox@microsoft.com> | 2016-12-17 08:18:17 -0500 |
---|---|---|
committer | Matthew Wilcox <mawilcox@microsoft.com> | 2017-02-13 21:44:02 -0500 |
commit | d37cacc5adace7f3e0824e1f559192ad7299d029 (patch) | |
tree | 9932ecc9ba3010ecc53bdbf5cd299eb0842106ec /tools/testing | |
parent | 7ad3d4d85c7af9632055a6ac0aa15b6b6a321c6b (diff) | |
download | linux-d37cacc5adace7f3e0824e1f559192ad7299d029.tar.gz linux-d37cacc5adace7f3e0824e1f559192ad7299d029.tar.bz2 linux-d37cacc5adace7f3e0824e1f559192ad7299d029.zip |
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>
Diffstat (limited to 'tools/testing')
-rw-r--r-- | tools/testing/radix-tree/idr-test.c | 93 |
1 files changed, 92 insertions, 1 deletions
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 4dffad9284e0..59081122c63d 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); } |