**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