Instead of just posting a diff of the changes, I thought it would be appropirate
to highlight the significant sections of the code which under went change so
that one can grasp how the R-B Tree replaces the Static Array implementation

  • Introduction of uvm_physseg_t

    The new abstraction uvm_physseg_t now encapsulates the handle that is
    used to access the current “segment” or “node”, this concept is also
    back-ported into the existing static array impementation, so that the
    consumers of the uvm_physseg API does not get broken.

  • Introduction of itetrators

    I am not sure if I would call it iterators, but it is the closest I can think
    of when thinking about this. With the introduction of a new handle, we cannot
    assume we can loop through an array using just integers like we did in the
    current code base so this has lead to the introduction of new supporting
    function calls like

    uvm_physseg_get_first()

    uvm_physseg_get_last()

    uvm_physseg_get_next()

    uvm_physseg_get_prev()

    uvm_physseg_valid()

    This allowed us to re-write loops that looked like this

    for (lcv = 0 ; lcv < vm_nphysmem ; lcv++) {
	  seg = VM_PHYSMEM_PTR(lcv);
	  freepages += (seg->end - seg->start);
}

    into loops that looked like this.

    for (bank = uvm_physseg_get_first();
     uvm_physseg_valid(bank);
     bank = uvm_physseg_get_next(bank)) {
	   freepages += (uvm_physseg_get_end(bank) - uvm_physseg_get_start(bank));
}

    They are more agnostic and do not assume an underlying data structure for the
    “segment”. This means that all of these changes need to propagate through the
    MI and MD Part of the code Cherry (cherry@) is working on these changes as I
    work on the implementation of the tree.

  • Semantics of first, last, next, previous.

    This is quite an important change in the uvm_physseg API, in the old one
    which assumed an Array backing structure. Here is a list of changes to make
    things easier to understand and how they vary in the respective implementation

    Static Array

    uvm_physseg_first() - First segment in the array.
    uvm_physseg_last() - Last segment in the array.
    uvm_physseg_next() - Next segment to the current one in the array.
    uvm_physseg_prev() - Previous segment to the current one in the array.

    R-B Tree

    uvm_physseg_first() - Lowest Valued segment in the Tree.
    uvm_physseg_last() - Highest Valued segment in the Tree.
    uvm_physseg_next() - Next higher valued segment to the current one (sorted order).
    uvm_physseg_prev() - Previous lower valued segment to the current one (sorted order).

    The semantics of Static Array and R-B Tree coincide when the strategy used is
    BSEARCH.

  • Introduction of uvm_physseg_valid()

    This is a function call that can be used to check the validity of a given
    segment. And returns a boolean depending on the validity of the passed
    segment.

    In addition to this Cherry (cherry@) introduced 3 macros to deal with the different
    possible invalid types that one may encounter.

    UVM_PHYSMEM_TYPE_INVALID - Generic Invalid

    UVM_PHYSMEM_TYPE_INVALID_EMPTY - Accessing empty segment

    UVM_PHYSMEM_TYPE_INVALID_OVERFLOW - Accessing segment beyond the last one

  • Introduction of uvm_physseg_init()

    A new function had to introduced which acts as the init for the uvm_physseg
    functionalities, this, is needed to be called before utilizing any functions
    that may use the API exposed by uvm_physseg this is due to the fact that
    rbtree(3) requires a bit of initializations before the data structure can be
    used.

In addition the above exposed changes there are also some internal changes that have
been made that is not exposed to the consumer of the API but are visible if you are
looking at the internals of the API these changes will be significant.

  • Replacing VM_PHYSMEM_PTR() macro

    Since to hide the backing implementation this is now referred to as
    HANDLE_TO_PHYSMEM_NODE()

    The use of this macro is very much identical to the current one.

  • Modifying struct vm_physseg

    struct vm_physseg was modified to accommodate the struct rb_node so that it
    behaves as a node in rbtree(3).

  • Added struct vm_physmem

    This new struct will act as the entry point into the R-B Tree, is also has a
    variable keeping track of the number of nodes in the R-B Tree int nentries
    which acts are the replacement for int vm_nphysseg.

  • Compare functions for rbtree(3)

    These were just standard compare functions for doing node operations on R-B
    Tree. One assumption made is, we have no overlapping memory regions being
    inserted into the tree, i.e. all segments are mutually exclusive.

So that is pretty much it for this update, I can hear Cherry typing away on his keyboard
updating the various Machine Dependent areas for each of 78 ports where these changes
will be affected.