After the re-organization of the code related to uvm hotplug into a separate
file uvm_physseg.c, the exposed API via uvm_physseg.h and the introduction
of a handle uvm_physseg_t which is used to access data structure that keeps
physical segment information, we came across a failing ATF test case in the
static array implementation which was working as expected in the RB tree
implementation. For the static array implementation we were using the
VM_PSTRAT_BSEARCH strategy.
The specific test case in question is uvm_physseg_get_prev which had the
segements being inserted into the system out-of-order, this meant that the page
frames of the segments that were inserted in chunks were not in a sorted
order. So the first chunk may be in the 256 to 512 range and the second chunk
was in the 0 to 256 range. The same chunks if inserted in sorted order resulted
in a passing test.
After some amount of debugging we found out why this rather seemingly trivial
change in the order of insertion was causing the tests to fail, this was a
consequence of changing the way the segment was being referenced in the
underlying data structure from static array implementation to RB Tree
implementation.
So in the static array implementation the reference to a segment was done via
the index of the array. For example, in the above example the first segment
regardless of the address range of the segment would be inserted in index 0 of
the array. Now the handle of the inserted segment will be the index of
the array and this is the important distinction.
Now let us insert a second segment into the above said array, and depending on
if the address range is greater or lesser than the current segement at 0
it would end up either on the right or left of the given segment respectively.
This is done to maintain sorted order during insertion of segments to comply
with the VM_PSTRAT_BSEARCH strategy. Now whenever an insert occurs, it means
shifting contents of the array to the left or right to make room for the new
segment, hence in the example above inserting left implies you are shifting
index of the first segment by one effectively making it 1 and the new segment
is inserted at 0
For an external caller of the API, this is how it looks.
upm = uvm_page_physload(VALID_START_PFN_2, VALID_END_PFN_2,
VALID_AVAIL_START_PFN_2, VALID_AVAIL_END_PFN_2, VM_FREELIST_DEFAULT);Now upm points to the segment that was inserted by uvm_page_physload() and
at this point it is 0.
Let us do a second insert,
uvm_page_physload(VALID_START_PFN_1, VALID_END_PFN_1,
VALID_AVAIL_START_PFN_1, VALID_AVAIL_END_PFN_1, VM_FREELIST_DEFAULT);NOTE: This insertion is done in such a way the second segement is in a lesser
address range than the first one which was interested. Also I do not assign the
handle returned by the call to any variable.
So what does upm handle point to now? My expectation (since the tests were
written agnostic to the backing data structure) was that upm will still point
to the first one inserted. But in the case of static array implementation, this
will not be true, since the position of the first segment was shifted to make
space for the second one.
So the question arises, should the handle be mutable when you do inserts /
deletes on the backing data structure? In my opinion “No”, a handle to a given
segment should always point to that segment and should not matter if the
position of the segment has changed in the backing data structure.
RB Tree, does not suffer from this issue since the handle to the segment is the
physical address of struct uvm_physseg in the system.
In order to separately identifiy this property of mutability we added a new test
case in ATF uvm_physseg_handle_immutable which should always fail for static
array implementation.