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