This is an old revision of the document!

Title

• VM Algorithm Improvement: Better Data Structures and Algorithms to Support Large VM Objects.

Objective

For management of resident pages the splay trees are used, which are not suitable for the purpose. The objective is to replace the splay tree with another data-structure such that even ordered traversal is possible. The ordered traversal will allow us to reduce size of structure vm_page.

Plan

• To implement the new data structure in user-space first. Test for memory leaks and correctness. Evaluate space and time efficiency.
• The new data structure is generalized radix tree. (different number of bits at each level)
• Move the code to kernel and run the new data structure parallel to old data structure, test for identical functionality.
• Performance evaluation.

TODO

• Implement user-mode generalized radix tree.
• Test for memory leaks and functional correctness.
  • Test strategy: Using Valgrind for memory leaks and random add/remove/lookup operations for long time.
  • Test for different tree configurations.
• Integrate the radix tree with kernel code and run in parallel with the existing splay tree, check if the values returned are identical. (*)
• Remove the splay tree and measure performance for the new data structure.

(* There are couple of more sub tasks in kernel integration such as preallocation of nodes and provision for ordered traversal, more details on the task will be added as we make progress) UPDATES * The user mode mode implementation is complete and is under testing.

• After preliminary testing the code does not show any memory leaks or illegal pointer reference, stress-testing is being carried out.
• The code will be checked (along with the test programs) in to perforce once the unit testing is over. (Expected date: 14th June)