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.
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: 17th June)
- June 18th : The unit testing is over and the code is checked in. Investigating issues related to VM integration.
- The memory for nodes will be reserved at the boot time, as the insert can not block or fail if malloc fails.
- Initially the tree will function in parallel with the splay tree and eventually it will be removed.
- The new files are added in the kernel configuration and are compiled with the kernel. Once the function calls are made from appropriate places the code will be checked in.
- Some problems in the kernel integration, debugging the code.
- Benchmarking of radix and splay trees done.
- Splay tree removed from struct vm_object, Current kernel functions using radix tree only.
Benchmarking Results:
Here are benchmarking results with preallocation,
[insert operation performs better here compared to malloc.]
Look-up
- Measuring time for 65535 lookup operations on radix tree with 4095 elements
TSC difference after lookups: 1313747
Measuring time for 65535 lookup operations on splay tree with 4095 elements
TSC difference after lookups: 302694361
Insert
Measuring time for 65535 inserts on radix tree with 4095 elements
TSC difference after inserts: 2431122
Measuring time for 65535 inserts on splay tree with 4095 elements
TSC difference after inserts: 127930972
Remove
Measuring time for 65535 removes on radix tree
TSC difference after removes: 168615
Measuring time for 65535 removes on splay tree
TSC difference after removes: 375269656