class VmPageList

Returns a slot that was empty after LookupOrAllocate, and that the caller did not end up

filling.

This ensures that if LookupOrAllocate allocated a new underlying list node, then that list node

needs to be free'd otherwise it might not get cleaned up for the lifetime of the page list.

This is only correct to call on an offset for which LookupOrAllocate had just returned a non

null slot, and that slot was Empty and is still Empty.

Removes any item at |offset| from the list and returns it, or VmPageOrMarker::Empty() if none.

Returns true if the page list does not own any pages or references. Meant to check whether the

page list has any resource that needs to be returned.

Populates individual interval slots in the range [start_offset, end_offset) that falls inside a

sparse interval. The intent of this function is to allow the caller to prepare the range for

overwriting (replacing with pages) by populating the required slots upfront, so that slot

lookup does not fail after this call. Essentially simulates interval splits

(LookupOrAllocateCheckForInterval) for every offset in the specified range, but does so more

efficiently, instead of having to search the tree repeatedly for every single offset.

Helper to return an unused interval slot so that it can be merged back into the interval it was

populated/split from.

Returns true if the specified offset falls in a sparse zero interval.

walk the page tree, calling the passed in function on every tree node.

similar to ForEveryPage, but the per_page_func gets called with a VmPageOrMarkerRef instead of

a const VmPageOrMarker*, allowing for limited mutation.

walk the page tree, calling the passed in function on every tree node.

similar to ForEveryPageInRange but uses a valid VMPLCursor as the starting point.

similar to ForEveryPageInRange, but the per_page_func gets called with a VmPageOrMarkerRef

instead of a const VmPageOrMarker*, allowing for limited mutation.

walk the page tree, calling |per_page_func| on every page/marker and |per_gap_func| on every

gap.

walk the page tree, calling |per_page_func| on every page/marker/interval that fulfills

(returns true) the |compare_func|. Also call |contiguous_run_func| on every contiguous range of

such pages/markers/intervals encountered, whose signature is:

zx_status_t contiguous_run_func(uint64_t start, uint64_t end, bool is_interval)

Intervals are treated as distinct contiguous runs, i.e. they won't be merged into a contiguous

run of pages/markers for invocation of |contiguous_run_func|. For intervals,

|contiguous_run_func| will be called with |is_interval| set to true; for other page types it

will be false. Additionally, the entire interval should fulfill |compare_func| for

|contiguous_run_func| to be called on the portion that falls in [start_offset, end_offset).

Returns true if any pages (actual pages, references, or markers) are in the given range, or if

the range forms a part of a sparse page interval.

Clips an interval from the start by len, i.e. moves the start from interval_start to

interval_start + len. The total length of the interval must be larger than len.

Clips an interval from the end by len, i.e. moves the end from interval_end to

interval_end - len. The total length of the interval must be larger than len.

Replace an existing page at offset with a zero interval, and return the released page. The

caller takes ownership of the released page and is responsible for freeing it.

Similar to |AnyPagesOrIntervalsInRange| but skips over any ParentContent markers, as these do

not represent content owned by this page list, but rather content owned by a parent.

Takes the content out of this page list and places them in the provided |splice| list, which

must have already been initialized but still be empty. The range to be taken is determined by

the provided |offset| and the length of the |splice| list, and will be |Finalize|d before

returning. May return ZX_ERR_OUT_OF_MEMORY, in which case an unspecified number of pages will

have been moved into |splice|.

Overwrite a zero interval either fully or partially with a new zero interval, breaking off the

old interval into two if required. old_start_offset and old_end_offset specify the start and

end sentinels of the old interval that is being overwritten; either one of these or both can be

specified, with the other set to UINT64_MAX. The new zero interval that overwrites the old

spans [new_start_offset, new_end_offset] with its state set to new_dirty_state.

- For full overwrites, both old_start_offset and old_end_offset must be provided, and should

be equal to new_start_offset and new_end_offset respectively. At the end of the call, the old

interval will have been completely replaced by the new one.

- For partial overwrites from the start, old_start_offset must be provided and be equal to

new_start_offset, and old_end_offset must be UINT64_MAX. At the end of this call, the start of

the old interval will have been overwritten by the new interval, with the remainder of the old

interval now starting at |new_end_offset + kPageSize|.

- For partial overwrites from the end, old_end_offset must be provided and be equal to

new_end_offset, and old_start_offset must be UINT64_MAX. At the end of this call, the end of

the old interval will have been overwritten by the new interval, with the remainder of the old

interval now ending at |new_start_offset - kPageSize|.

- Partial overwrites in the middle are not allowed. In other words, either old_start_offset

must be the same as new_start_offset, or old_end_offset must be the same as new_end_offset, or

both.

Attempts to return a reference to the VmPageOrMarker at the specified offset. The returned

pointer is valid until the VmPageList is destroyed or any of the Remove*/Take/Merge etc

functions are called.

Lookup may return 'nullptr' if there is no slot allocated for the given offset. If non-null

is returned it may still be the case that IsEmpty() on the returned PageOrMarker is true.

Similar to `Lookup` but returns a VmPageOrMarkerRef that allows for limited mutation of the

slot. General mutation requires calling `LookupOrAllocate`.

Similar to `LookupMutable` but returns a VMPLCursor that allows for iterating over any

contiguous slots from the provided offset.

Similar to `LookupMutableCursor` but does a lower_bound search instead of a find, returning the

first slot >= offset, if any exists.

Similar to `Lookup` but only returns `nullptr` if a slot cannot be allocated either due to out

of memory, due to offset being invalid, or |interval_handling| not allowing for a slot to be

safely returned.

The returned slot, if not a `nullptr`, may generally be freely manipulated with the exception

that if it started !Empty, then it is an error to set it to Empty. In this case the

`RemovePage` method must be used.

If the returned slot started Empty, as it not made !Empty, then the slot must be returned with

ReturnEmptySlot, to ensure no empty nodes are retained.

The bool in the ktl::pair returns whether the offset falls inside a sparse interval. And

whether a valid VmPageOrMarker* is returned in the ktl::pair depends on the specified

|interval_handling|.

- NoIntervals: The page list does not contain any intervals, so there is no special handling

to check for or split intervals. In other words, each slot in the page list can be manipulated

independently.

- CheckForIntervals: The page list can contain intervals, and the bool in the returned

ktl::pair indicates whether the offset fell inside an interval. Note that this only checks for

intervals but does not allow manipulating them, so a valid VmPageOrMarker* will be returned

only if the offset can safely be manipulated independently.

- SplitInterval: The page list can contain intervals and we are allowed to split intervals to

return the required slot. The returned VmPageOrMarker* can be manipulated freely. (See

comments near LookupOrAllocateCheckForInterval for an explanation of how splitting works.)

Release every item in the page list and calls free_content_fn on any content, giving it

ownership. Any markers are cleared.

Clears the tree of any remaining slots, leaving it in the initially allocated state. It is an

error, and will trigger a panic, for any of the slots to hold pages or references, as clearing

them would otherwise result in a memory leak.

Calls the provided callback for every page or marker in the range [start_offset, end_offset).

The callback can modify the VmPageOrMarker and take ownership of any pages, or leave them in

place. The difference between this and ForEveryPage is as this allows for modifying the

underlying pages any intermediate data structures can be checked and potentially freed if no

longer needed.

Similar to RemovePages but also takes a |per_gap_fn| callback to allow for iterating over any

gaps encountered as well. This can be used when the intent is to modify the underlying pages

and/or gaps, while checking any intermediate data structures to potentially free ones that are

no longer needed.

Returns true if there are no pages, references, markers, or intervals in the page list.

Merges the pages in the specified range in |this| onto the |other| with |offset| in this

mapping to the offset of 0 in |other|.

For any offset in |this| that is not empty then the given |migrate_fn| is called with a

reference to |this| and the corresponding slot in |other| and has the signature of:

void migrate_fn(VmPageOrMarker* this_slot, VmPageOrMarker* other_slot, uint64_t other_offset);

If this returns |true| then migrate_fn was called on everything in range of |offset| to

|end_offset|. If false is returned then merging did not complete due to inability to allocates

nodes in |other|. The partial merge is not rolled back and is up to the caller to deal with.

Add a sparse zero interval spanning the range [start_offset, end_offset) with the specified

dirty_state. The specified range must be previously unpopulated. This will try to merge the new

zero interval with existing intervals to the left and/or right, if the dirty_state allows it.

The interval handling flag to be used by LookupOrAllocate. See comments near LookupOrAllocate.