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.