After some rounds of discussion with Cherry (cherry@) we finally came to the conclusion that R-B Tree would be a good clean way to re-implement the static array implementation for maintaing segments that is currently done in uvm. Specifically the segment information loaded by uvm_page_physload() and the handling of segment related information as done by the new uvm_physseg.c API.

This post is about the reasoning and the rationale of why we finally decided to use R-B Tree as the backing structure for implementing hotplug in uvm.

I have always been fascinated by Trees (both physical and logical), and when I got introduced to the concept of “Binary Trees” in my undergrad days back in college I just fell in love with the data structure, the traversal of nodes in different ways, the recursive nature in which you could access information and the fact that almost all operations take roughly O(log (n)). Red-Black Trees[1] is a specific implementation of Binary Trees that is self-balancing.

Add to this NetBSD comes with a wonderful API that implements this R-B Tree[2] called rbtree(3). It comes as a part of the standard C Library. Other than the the obvious properties of a R-B Tree, what are the reasons we went for this data structure instead of something like Lists for example.

In no particular order here are some of our thoughts

  • We no longer have to worry about maintaining a Sorted Order, In-order traversal of the R-B Tree always results in sorted order retrival. What makes this easier is the macro provided by the API RB_TREE_FOREACH() which goes through each of the node in sorted order.

  • No more multiple strategies for maintaining the segments. The current one provides 3 seprate strategies RANDOM, BSEARCH and CONTIG depending on how you want to keep the segments. With the choice of R-B Tree implementation, all of the strategies would boil down to BSEARCH.

  • Lesser code clutter, since we are now dependent on the R-B Tree API to do the inserts / removals / retrievals, we do not need to worry about writing loops and code to maintaining and managing the data structure itself, hence making a reliable and robust code base which is less prone to errors.

  • Neat and clean API, compared to queue(3) and tree(3), the rbtree(3) API is cleaner and neater to read and to implement.

However these advantages are not without a challenge

  • The current handle for accessing segment is the index of the array vm_physmem[] which is of type int. For R-B Tree the proposed equivalent handle would be struct vm_physseg *, this also means “loops” that were created for iterating the array would be needed to re-written carefully so as not to break the system.

  • Inorder to ease the transition, we intend to introduce a new abstraction for the above mentioned handle called uvm_physseg_t which will be a typedef over the existing handle and then introduce enough utility functions that can help replace the current assumed properties of the int type which are used in various sections through uvm.

  • Since we are modifying a fundamental part of the Operating System, this implies every single architecture port of NetBSD (which is 78 at the time of writing this) varying from Grandpa’s Atari ST to x86 / amd64 need to be worked on and that is no easy task. Cherry will be more into fixing the MD specific part of these ports. He once compared this task to “Yak Shaving”.

  • Eventually when the system is a go, will it perform as competitive as the current system? Of course sorting an array is O(n log(n)), and retrieval is O(log (n)) when sorted. Can the R-B Tree model meet up with these performance in a head on head benchmark?

More to details to come soon as we progress.

1 - Red-Black Trees - Wikipedia 2 - rbtree(3) NetBSD manpage