[TASKS] Report for project: radix tree test suite

[TASKS] Report for project: radix tree test suite

[Rehas Sachdeva]

Here is what I read about Kernel radix trees:

There are two implementations.
One is in <include/linux/idr.h> and <lib/idr.c>, the other in
<include/linux/radix-tree.h> and <lib/radix-tree.c>. Both provide a mapping
from a number (unsigned long) to an arbitrary pointer (void *), though
radix-tree also allows up to two "tags" to be stored with each entry.

At each level, starting from most significant 6 bits at the root, we use the
next 6 bits of the key to choose the slot at that node. At the last level, we
have the desired value (user pointer), otherwise we have a pointer to a next
level node.

I took a look at the implementation of insert, delete, lookup, preload and
tag processing functions.

Radix tree is used for checking presence of pages in cache, finding pages with
dirty/ under writeback tag etc, many places where we want resizable arrays like
drivers, example NVM Express, File Systems like NFS, interrupt controllers.

Project: radix tree test suite

The Radix Tree Test Suite was first merged into Linux 4.6. It can be enhanced
in the following ways:
(From the project introduction)
-Providing test coverage by adding missing tests. We can use tools like gcov
for this.
-Adding performance measures.
-Make it share common test infrastructure, macros, for example using
tools/include.

I looked at many patches, about tests for insertion and lookup, tests for
multiorder entries, about using common kernel macros, to allow option for less
testing time, or ad-hoc tests for corner cases and benchmark test for iterators.
I think they are a good starting point to learn about what is expected from this
project.

Some more thoughts:
-Running tests in parallel (I did see single_thread_tests for regression tests)
-I could also look at other types of tests, performance benchmarks in other
parts of the kernel, used for other data structures and see if we can
incorporate them/similar ones into radix tree test suite.
-If IDR is re-written on Radix tree core, we might need test suite to be part
generic to both, and part specific.

Timeline for project - radix tree test suite:
- Get a deeper understanding of Radix tree implementation, clear any doubts about it.(1 week)
- Try gcov, and look for other ways/scripts to identify corner cases or functions that need coverage, Add missing tests identified. (2-3 weeks)
- Use more common, generic kernel code instead of specific, example from tools/include. (1-2 weeks)
- Add performance/Benchmark tests based on memory, time usage etc. (1-2 weeks)
- Document the changes. Any other cleanups/refactoring/modifications required to radix_tree or test suite. (1-2 weeks).
- Buffer time for unexpected delays, or necessary work unidentified in the beginning. (1-2 weeks).