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