A Tale of Two Handles

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.