ida: Use exceptional entries for small IDAs
authorMatthew Wilcox <mawilcox@microsoft.com>
Sat, 17 Dec 2016 13:18:17 +0000 (08:18 -0500)
committerMatthew Wilcox <mawilcox@microsoft.com>
Tue, 14 Feb 2017 02:44:02 +0000 (21:44 -0500)
commitd37cacc5adace7f3e0824e1f559192ad7299d029
tree9932ecc9ba3010ecc53bdbf5cd299eb0842106ec
parent7ad3d4d85c7af9632055a6ac0aa15b6b6a321c6b
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>
lib/idr.c
lib/radix-tree.c
tools/testing/radix-tree/idr-test.c