task for radix tree test suite

task for radix tree test suite

[Gargi Sharma]

Hello Mentors,

No task is listed for the radix tree test suite project on the
Outreachy Kernel Page. Will a timeline for the proposed project be
sufficient? Is there a small task I can do before the deadline
tomorrow?

Thanks
Gargi

Re: task for radix tree test suite

[Rik van Riel]

[-- Attachment #1: Type: text/plain, Size: 450 bytes --]

On Sun, 2016-10-16 at 14:44 +0530, Gargi Sharma wrote:
> Hello Mentors,
> 
> No task is listed for the radix tree test suite project on the
> Outreachy Kernel Page. Will a timeline for the proposed project be
> sufficient? Is there a small task I can do before the deadline
> tomorrow?

A timeline, and a piece of text with your understanding
of how the radix tree works, and how it can be used, will
be enough.

-- 
All Rights Reversed.

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

task for radix tree test suite

[Gargi Sharma]

Radix Tree

Radix tree is a compressed trie that is used to associate a pointer
value with an integer.
The radix tree root structure contains the height of the tree, the gfp
mask and a pointer to the child node.
The gfp mask decides how the memory allocations are performed. The
radix tree node contains a pointer to the parent, count of child node,
information to free the node ,count of child nodes.

Each layer of the Radix Tree contains 64 pointers and the next 6 bits
of the index are used to determine which pointer to use
The pointer at the last level is the user pointer. All other pointers
at the intermediate level point to the next layer.
In the radix trees, all data resides at the leaves and no data in the
intermediate nodes. The radix tree does not need re-balancing.
To insert an a pointer that has an index greater than the current
maximum index, one can insert new node above the top node to increase
the levels in the radix tree. While deleting an element, if we get a
tree where the top node has only one child with index 0, we can
replace the node to decrease the levels in the radix tree.

radix tree is used for checking pages in cache, the PowPC architecture
uses a radix tree to map real and virtual IRQ numbers. The NFS code
uses a radix tree to index inode structures to keep track of
outstanding requests. The address_space structure used to keep track
of backing store contains a radix tree which tracks in-core pages tied
to that mapping.

radix tree can also be used of pid allocation as well as fd
allocation. Radix tree is a better choice than IDR API since the size
of the pointer is 64 bits in radix tree as compared to 128 bits in IDR
API. Hence, the IDR API unnecessarily wastes space which can be saved
by using the radix tree API.

Timeline:

Week 1 and 2: Find out the current code coverage and the modules that
do not have tests written for them. Use tools like gocv, gct, etc. for
the code coverage. Look at past radix tree test suite patches to find

Week 3 to 6: Write tests for the modules that were missing coverage
found in the preliminary study.

Week 7 to 10: Add benchmarks for radix tree modules for example, radix
tree iterator.

Week 11 to 12: Add documentation for all the modules that have been
covered by the test suites and the modules that are left. Also
document some of the difficulties that might have come while writing
test for a few of these modules to ease the transition for people
writing the tests in future.