zircon/kernel/vm/include/vm/vm_page_list.h - fuchsia - Git at Google

 // Copyright 2016 The Fuchsia Authors
 //
 // Use of this source code is governed by a MIT-style
 // license that can be found in the LICENSE file or at
 // https://opensource.org/licenses/MIT

 #ifndef ZIRCON_KERNEL_VM_INCLUDE_VM_VM_PAGE_LIST_H_
 #define ZIRCON_KERNEL_VM_INCLUDE_VM_VM_PAGE_LIST_H_

 #include <align.h>
 #include <zircon/errors.h>
 #include <zircon/types.h>

 #include <fbl/canary.h>
 #include <fbl/function.h>
 #include <fbl/intrusive_wavl_tree.h>
 #include <fbl/macros.h>
 #include <ktl/algorithm.h>
 #include <ktl/unique_ptr.h>
 #include <vm/page.h>
 #include <vm/pmm.h>
 #include <vm/vm.h>

 // RAII helper for representing owned pages in a page list node. This supports being in one of
 // three states
 //  * Empty - Contains nothing
 //  * Page p - Contains a vm_page 'p'. This 'p' is considered owned by this wrapper and
 //             `ReleasePage` must be called to give up ownership.
 //  * Marker - Indicates that whilst not a page, it is also not empty. Markers can be used to
 //             separate the distinction between "there's no page because we've deduped to the zero
 //             page" and "there's no page because our parent contains the content".
 class VmPageOrMarker {
  public:
   VmPageOrMarker() : page_(nullptr) {}
   ~VmPageOrMarker() { DEBUG_ASSERT(!IsPage()); }
   VmPageOrMarker(VmPageOrMarker&& other) : page_(other.Release()) {}
   VmPageOrMarker(const VmPageOrMarker&) = delete;
   VmPageOrMarker& operator=(const VmPageOrMarker&) = delete;

   // Returns a reference to the underlying vm_page*. Is only valid to call if `IsPage` is true.
   vm_page* Page() const {
     DEBUG_ASSERT(IsPage());
     return page_;
   }

   // If this is a page, moves the underlying vm_page* out and returns it. After this IsPage will
   // be false and IsEmpty will be true.
   vm_page* ReleasePage() {
     DEBUG_ASSERT(IsPage());
     return Release();
   }

   bool IsPage() const { return !IsMarker() && !IsEmpty(); }

   bool IsMarker() const { return page_ == RawMarker(); }

   bool IsEmpty() const { return page_ == nullptr; }

   VmPageOrMarker& operator=(VmPageOrMarker&& other) {
     // Forbid overriding a page, as that would leak it.
     DEBUG_ASSERT(!IsPage());
     page_ = other.Release();
     return *this;
   }

   bool operator==(const VmPageOrMarker& other) const { return page_ == other.page_; }

   bool operator!=(const VmPageOrMarker& other) const { return page_ != other.page_; }

   static VmPageOrMarker Empty() { return {nullptr}; }

   static VmPageOrMarker Marker() { return {RawMarker()}; }

   static VmPageOrMarker Page(vm_page* p) {
     DEBUG_ASSERT(p);
     return {p};
   }

  private:
   VmPageOrMarker(vm_page* p) : page_(p) {}

   static vm_page* RawMarker() { return reinterpret_cast<vm_page*>(1); }

   vm_page* Release() {
     vm_page* p = page_;
     page_ = nullptr;
     return p;
   }

   vm_page* page_;
 };

 class VmPageListNode final : public fbl::WAVLTreeContainable<ktl::unique_ptr<VmPageListNode>> {
  public:
   explicit VmPageListNode(uint64_t offset);
   ~VmPageListNode();

   DISALLOW_COPY_ASSIGN_AND_MOVE(VmPageListNode);

   static const size_t kPageFanOut = 16;

   // accessors
   uint64_t offset() const { return obj_offset_; }
   uint64_t GetKey() const { return obj_offset_; }

   uint64_t end_offset() const { return offset() + kPageFanOut * PAGE_SIZE; }

   void set_offset(uint64_t offset) {
     DEBUG_ASSERT(!InContainer());
     obj_offset_ = offset;
   }

   // for every page or marker in the node call the passed in function.
   template <typename F>
   zx_status_t ForEveryPage(F func, uint64_t skew) {
     return ForEveryPageInRange(this, func, offset(), end_offset(), skew);
   }

   // for every page or marker in the node call the passed in function.
   template <typename F>
   zx_status_t ForEveryPage(F func, uint64_t skew) const {
     return ForEveryPageInRange(this, func, offset(), end_offset(), skew);
   }

   // for every page or marker in the node in the range call the passed in function. The range is
   // assumed to be within the nodes object range.
   template <typename F>
   zx_status_t ForEveryPageInRange(F func, uint64_t start_offset, uint64_t end_offset,
                                   uint64_t skew) {
     return ForEveryPageInRange(this, func, start_offset, end_offset, skew);
   }

   // for every page or marker in the node in the range call the passed in function. The range is
   // assumed to be within the nodes object range.
   template <typename F>
   zx_status_t ForEveryPageInRange(F func, uint64_t start_offset, uint64_t end_offset,
                                   uint64_t skew) const {
     return ForEveryPageInRange(this, func, start_offset, end_offset, skew);
   }

   const VmPageOrMarker& Lookup(size_t index) const {
     canary_.Assert();
     DEBUG_ASSERT(index < kPageFanOut);
     return pages_[index];
   }

   VmPageOrMarker& Lookup(size_t index) {
     canary_.Assert();
     DEBUG_ASSERT(index < kPageFanOut);
     return pages_[index];
   }

   // A node is empty if it contains no pages or markers.
   bool IsEmpty() const {
     for (const auto& p : pages_) {
       if (!p.IsEmpty()) {
         return false;
       }
     }
     return true;
   }

   // Returns true if there are still allocated vm_page_t's owned by this node.
   bool HasNoPages() const {
     for (const auto& p : pages_) {
       if (p.IsPage()) {
         return false;
       }
     }
     return true;
   }

  private:
   template <typename S, typename F>
   static zx_status_t ForEveryPageInRange(S self, F func, uint64_t start_offset, uint64_t end_offset,
                                          uint64_t skew) {
     // Assert that the requested range is sensible and falls within our nodes actual offset range.
     DEBUG_ASSERT(end_offset >= start_offset);
     DEBUG_ASSERT(start_offset >= self->obj_offset_);
     DEBUG_ASSERT(end_offset <= self->end_offset());
     const size_t start = (start_offset - self->obj_offset_) / PAGE_SIZE;
     const size_t end = (end_offset - self->obj_offset_) / PAGE_SIZE;
     for (size_t i = start; i < end; i++) {
       if (!self->pages_[i].IsEmpty()) {
         zx_status_t status = func(&self->pages_[i], self->obj_offset_ + i * PAGE_SIZE - skew);
         if (unlikely(status != ZX_ERR_NEXT)) {
           return status;
         }
       }
     }
     return ZX_ERR_NEXT;
   }

   fbl::Canary<fbl::magic("PLST")> canary_;

   uint64_t obj_offset_ = 0;
   VmPageOrMarker pages_[kPageFanOut];
 };

 class VmPageList;

 // Class which holds the list of vm_page structs removed from a VmPageList
 // by TakePages. The list include information about uncommitted pages and markers.
 class VmPageSpliceList final {
  public:
   VmPageSpliceList();
   VmPageSpliceList(VmPageSpliceList&& other);
   VmPageSpliceList& operator=(VmPageSpliceList&& other_tree);
   ~VmPageSpliceList();

   // Pops the next page off of the splice.
   VmPageOrMarker Pop();

   // Returns true after the whole collection has been processed by Pop.
   bool IsDone() const { return pos_ >= length_; }

   DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(VmPageSpliceList);

  private:
   VmPageSpliceList(uint64_t offset, uint64_t length);
   void FreeAllPages();

   uint64_t offset_;
   uint64_t length_;
   uint64_t pos_ = 0;

   VmPageListNode head_ = VmPageListNode(0);
   fbl::WAVLTree<uint64_t, ktl::unique_ptr<VmPageListNode>> middle_;
   VmPageListNode tail_ = VmPageListNode(0);

   friend VmPageList;
 };

 class VmPageList final {
  public:
   VmPageList();
   ~VmPageList();

   VmPageList& operator=(VmPageList&& other);
   VmPageList(VmPageList&& other);

   void InitializeSkew(uint64_t parent_skew, uint64_t offset) {
     // Checking list_skew_ doesn't catch all instances of double-initialization, but
     // it should catch some of them.
     DEBUG_ASSERT(list_skew_ == 0);
     DEBUG_ASSERT(list_.is_empty());

     list_skew_ = (parent_skew + offset) % (PAGE_SIZE * VmPageListNode::kPageFanOut);
   }
   uint64_t GetSkew() const { return list_skew_; }

   DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(VmPageList);

   // walk the page tree, calling the passed in function on every tree node.
   template <typename F>
   zx_status_t ForEveryPage(F per_page_func) const {
     return ForEveryPage(this, per_page_func);
   }

   // walk the page tree, calling the passed in function on every tree node.
   template <typename F>
   zx_status_t ForEveryPageInRange(F per_page_func, uint64_t start_offset,
                                   uint64_t end_offset) const {
     return ForEveryPageInRange(this, per_page_func, start_offset, end_offset);
   }

   // walk the page tree, calling |per_page_func| on every page/marker and |per_gap_func| on every
   // gap.
   template <typename PAGE_FUNC, typename GAP_FUNC>
   zx_status_t ForEveryPageAndGapInRange(PAGE_FUNC per_page_func, GAP_FUNC per_gap_func,
                                         uint64_t start_offset, uint64_t end_offset) const {
     return ForEveryPageAndGapInRange(this, per_page_func, per_gap_func, start_offset, end_offset);
   }

   // Returns true if any pages or markers are in the given range.
   bool AnyPagesInRange(uint64_t start_offset, uint64_t end_offset) const {
     bool found_page = false;
     ForEveryPageInRange(
         [&found_page](const VmPageOrMarker* page, uint64_t offset) {
           found_page = true;
           return ZX_ERR_STOP;
         },
         start_offset, end_offset);
     return found_page;
   }

   // 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.
   const VmPageOrMarker* Lookup(uint64_t offset) const;
   VmPageOrMarker* Lookup(uint64_t offset);

   // Similar to `Lookup` but only returns `nullptr` if a slot cannot be allocated either due to out
   // of memory or due to offset being invalid.
   VmPageOrMarker* LookupOrAllocate(uint64_t offset);

   // Removes any page at |offset| from the list and returns it, or VmPageOrMarker::Empty() if none.
   VmPageOrMarker RemovePage(uint64_t offset);

   // Release every page in the in the page list and calls free_page_fn on each one, giving it
   // ownership. Any markers are cleared.
   template <typename T>
   void RemoveAllPages(T free_page_fn) {
     // per page get a reference to the page pointer inside the page list node
     auto per_page_func = [&free_page_fn](VmPageOrMarker* p, uint64_t offset) {
       if (p->IsPage()) {
         free_page_fn(p->ReleasePage());
       }
       *p = VmPageOrMarker::Empty();
       return ZX_ERR_NEXT;
     };

     // walk the tree in order, freeing all the pages on every node
     ForEveryPage(this, per_page_func);

     // empty the tree
     list_.clear();
   }

   // 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.
   template <typename T>
   void RemovePages(T per_page_fn, uint64_t start_offset, uint64_t end_offset) {
     ForEveryPageInRange<NodeCheck::CleanupEmpty>(this, per_page_fn, start_offset, end_offset);
   }

   // Returns true if there are no pages or markers in the page list.
   bool IsEmpty() const;

   // Returns true if the page list does not own any vm_page.
   bool HasNoPages() const;

   // Merges the pages in |other| in the range [|offset|, |end_offset|) into |this|
   // page list, starting at offset 0 in this list.
   //
   // For every page in |other| in the given range, if there is no corresponding page or marker
   // in |this|, then they will be passed to |migrate_fn|. If |migrate_fn| leaves the page in the
   // VmPageOrMarker it will be migrated into |this|, otherwise the migrate_fn is assumed to now own
   // the page. For any pages in |other| outside the given range or which conflict with a page in
   // |this|, they will be released given ownership to |release_fn|.
   //
   // The |offset| values passed to |release_fn| and |migrate_fn| are the original offsets
   // in |other|, not the adapted offsets in |this|.
   //
   // **NOTE** unlike MergeOnto, |other| will be empty at the end of this method.
   void MergeFrom(VmPageList& other, uint64_t offset, uint64_t end_offset,
                  fbl::Function<void(vm_page*, uint64_t offset)> release_fn,
                  fbl::Function<void(VmPageOrMarker*, uint64_t offset)> migrate_fn);

   // Merges this pages in |this| onto |other|.
   //
   // For every page (or marker) in |this|, checks the same offset in |other|. If there is no
   // page or marker, then it inserts the page into |other|. Otherwise, it releases the page and
   // gives ownership to |release_fn|.
   //
   // **NOTE** unlike MergeFrom, |this| will be empty at the end of this method.
   void MergeOnto(VmPageList& other, fbl::Function<void(vm_page*)> release_fn);

   // Takes the pages and markers in the range [offset, length) out of this page list.
   VmPageSpliceList TakePages(uint64_t offset, uint64_t length);

   uint64_t HeapAllocationBytes() const { return list_.size() * sizeof(VmPageListNode); }

   // Allow the implementation to use a one-past-the-end for VmPageListNode offsets,
   // plus to account for skew_.
   static constexpr uint64_t MAX_SIZE =
       ROUNDDOWN(UINT64_MAX, 2 * VmPageListNode::kPageFanOut * PAGE_SIZE);

  private:
   template <typename S, typename F>
   static zx_status_t ForEveryPage(S self, F per_page_func) {
     for (auto& pl : self->list_) {
       zx_status_t status = pl.ForEveryPage(per_page_func, self->list_skew_);
       if (unlikely(status != ZX_ERR_NEXT)) {
         if (status == ZX_ERR_STOP) {
           break;
         }
         return status;
       }
     }
     return ZX_OK;
   }

   // Calls the provided callback for every page in the given range. If the CleanupNodes template
   // argument is true then it is assumed the per_page_func may remove pages and page nodes will be
   // checked to see if they are empty and can be cleaned up.
   enum class NodeCheck : bool {
     Skip = false,
     CleanupEmpty = true,
   };
   template <NodeCheck NODE_CHECK = NodeCheck::Skip, typename S, typename F>
   static zx_status_t ForEveryPageInRange(S self, F per_page_func, uint64_t start_offset,
                                          uint64_t end_offset) {
     start_offset += self->list_skew_;
     end_offset += self->list_skew_;

     // Find the first node (if any) that will contain our starting offset.
     auto cur =
         self->list_.lower_bound(ROUNDDOWN(start_offset, VmPageListNode::kPageFanOut * PAGE_SIZE));
     if (!cur) {
       return ZX_OK;
     }

     // Handle scenario where start_offset begins not aligned to a node.
     if (cur->offset() < start_offset) {
       zx_status_t status = cur->ForEveryPageInRange(
           per_page_func, start_offset, ktl::min(end_offset, cur->end_offset()), self->list_skew_);
       auto prev = cur++;
       if constexpr (NODE_CHECK == NodeCheck::CleanupEmpty) {
         if (prev->IsEmpty()) {
           self->list_.erase(prev);
         }
       }
       if (unlikely(status != ZX_ERR_NEXT)) {
         if (status == ZX_ERR_STOP) {
           return ZX_OK;
         }
         return status;
       }
     }
     // Iterate through all full nodes contained in the range.
     while (cur && cur->end_offset() < end_offset) {
       DEBUG_ASSERT(start_offset <= cur->offset());
       zx_status_t status = cur->ForEveryPage(per_page_func, self->list_skew_);
       auto prev = cur++;
       if constexpr (NODE_CHECK == NodeCheck::CleanupEmpty) {
         if (prev->IsEmpty()) {
           self->list_.erase(prev);
         }
       }
       if (unlikely(status != ZX_ERR_NEXT)) {
         if (status == ZX_ERR_STOP) {
           return ZX_OK;
         }
         return status;
       }
     }
     // Handle scenario where the end_offset is not aligned to the end of a node.
     if (cur && cur->offset() < end_offset) {
       DEBUG_ASSERT(cur->end_offset() >= end_offset);
       zx_status_t status =
           cur->ForEveryPageInRange(per_page_func, cur->offset(), end_offset, self->list_skew_);
       if constexpr (NODE_CHECK == NodeCheck::CleanupEmpty) {
         if (cur->IsEmpty()) {
           self->list_.erase(cur);
         }
       }
       if (unlikely(status != ZX_ERR_NEXT)) {
         if (status == ZX_ERR_STOP) {
           return ZX_OK;
         }
         return status;
       }
     }
     return ZX_OK;
   }

   template <typename S, typename PAGE_FUNC, typename GAP_FUNC>
   static zx_status_t ForEveryPageAndGapInRange(S self, PAGE_FUNC per_page_func,
                                                GAP_FUNC per_gap_func, uint64_t start_offset,
                                                uint64_t end_offset) {
     uint64_t expected_next_off = start_offset;
     auto per_page_wrapper_fn = [&expected_next_off, end_offset, per_page_func, &per_gap_func](
                                    auto* p, uint64_t off) {
       zx_status_t status = ZX_ERR_NEXT;
       if (expected_next_off != off) {
         status = per_gap_func(expected_next_off, off);
       }
       if (status == ZX_ERR_NEXT) {
         status = per_page_func(p, off);
       }
       expected_next_off = off + PAGE_SIZE;
       // Prevent the last call to per_gap_func
       if (status == ZX_ERR_STOP) {
         expected_next_off = end_offset;
       }
       return status;
     };

     zx_status_t status = ForEveryPageInRange(self, per_page_wrapper_fn, start_offset, end_offset);
     if (status != ZX_OK) {
       return status;
     }

     if (expected_next_off != end_offset) {
       status = per_gap_func(expected_next_off, end_offset);
       if (status != ZX_ERR_NEXT && status != ZX_ERR_STOP) {
         return status;
       }
     }

     return ZX_OK;
   }

   fbl::WAVLTree<uint64_t, ktl::unique_ptr<VmPageListNode>> list_;
   // A skew added to offsets provided as arguments to VmPageList functions before
   // interfacing with list_. This allows all VmPageLists within a clone tree
   // to place individual vm_page_t entries at the same offsets within their nodes, so
   // that the nodes can be moved between different lists without having to worry
   // about needing to split up a node.
   uint64_t list_skew_ = 0;
 };

 #endif  // ZIRCON_KERNEL_VM_INCLUDE_VM_VM_PAGE_LIST_H_
	// Copyright 2016 The Fuchsia Authors
	//
	// Use of this source code is governed by a MIT-style
	// license that can be found in the LICENSE file or at
	// https://opensource.org/licenses/MIT

	#ifndef ZIRCON_KERNEL_VM_INCLUDE_VM_VM_PAGE_LIST_H_
	#define ZIRCON_KERNEL_VM_INCLUDE_VM_VM_PAGE_LIST_H_

	#include <align.h>
	#include <zircon/errors.h>
	#include <zircon/types.h>

	#include <fbl/canary.h>
	#include <fbl/function.h>
	#include <fbl/intrusive_wavl_tree.h>
	#include <fbl/macros.h>
	#include <ktl/algorithm.h>
	#include <ktl/unique_ptr.h>
	#include <vm/page.h>
	#include <vm/pmm.h>
	#include <vm/vm.h>

	// RAII helper for representing owned pages in a page list node. This supports being in one of
	// three states
	// * Empty - Contains nothing
	// * Page p - Contains a vm_page 'p'. This 'p' is considered owned by this wrapper and
	// `ReleasePage` must be called to give up ownership.
	// * Marker - Indicates that whilst not a page, it is also not empty. Markers can be used to
	// separate the distinction between "there's no page because we've deduped to the zero
	// page" and "there's no page because our parent contains the content".
	class VmPageOrMarker {
	public:
	VmPageOrMarker() : page_(nullptr) {}
	~VmPageOrMarker() { DEBUG_ASSERT(!IsPage()); }
	VmPageOrMarker(VmPageOrMarker&& other) : page_(other.Release()) {}
	VmPageOrMarker(const VmPageOrMarker&) = delete;
	VmPageOrMarker& operator=(const VmPageOrMarker&) = delete;

	// Returns a reference to the underlying vm_page*. Is only valid to call if `IsPage` is true.
	vm_page* Page() const {
	DEBUG_ASSERT(IsPage());
	return page_;
	}

	// If this is a page, moves the underlying vm_page* out and returns it. After this IsPage will
	// be false and IsEmpty will be true.
	vm_page* ReleasePage() {
	DEBUG_ASSERT(IsPage());
	return Release();
	}

	bool IsPage() const { return !IsMarker() && !IsEmpty(); }

	bool IsMarker() const { return page_ == RawMarker(); }

	bool IsEmpty() const { return page_ == nullptr; }

	VmPageOrMarker& operator=(VmPageOrMarker&& other) {
	// Forbid overriding a page, as that would leak it.
	DEBUG_ASSERT(!IsPage());
	page_ = other.Release();
	return *this;
	}

	bool operator==(const VmPageOrMarker& other) const { return page_ == other.page_; }

	bool operator!=(const VmPageOrMarker& other) const { return page_ != other.page_; }

	static VmPageOrMarker Empty() { return {nullptr}; }

	static VmPageOrMarker Marker() { return {RawMarker()}; }

	static VmPageOrMarker Page(vm_page* p) {
	DEBUG_ASSERT(p);
	return {p};
	}

	private:
	VmPageOrMarker(vm_page* p) : page_(p) {}

	static vm_page* RawMarker() { return reinterpret_cast<vm_page*>(1); }

	vm_page* Release() {
	vm_page* p = page_;
	page_ = nullptr;
	return p;
	}

	vm_page* page_;
	};

	class VmPageListNode final : public fbl::WAVLTreeContainable<ktl::unique_ptr<VmPageListNode>> {
	public:
	explicit VmPageListNode(uint64_t offset);
	~VmPageListNode();

	DISALLOW_COPY_ASSIGN_AND_MOVE(VmPageListNode);

	static const size_t kPageFanOut = 16;

	// accessors
	uint64_t offset() const { return obj_offset_; }
	uint64_t GetKey() const { return obj_offset_; }

	uint64_t end_offset() const { return offset() + kPageFanOut * PAGE_SIZE; }

	void set_offset(uint64_t offset) {
	DEBUG_ASSERT(!InContainer());
	obj_offset_ = offset;
	}

	// for every page or marker in the node call the passed in function.
	template <typename F>
	zx_status_t ForEveryPage(F func, uint64_t skew) {
	return ForEveryPageInRange(this, func, offset(), end_offset(), skew);
	}

	// for every page or marker in the node call the passed in function.
	template <typename F>
	zx_status_t ForEveryPage(F func, uint64_t skew) const {
	return ForEveryPageInRange(this, func, offset(), end_offset(), skew);
	}

	// for every page or marker in the node in the range call the passed in function. The range is
	// assumed to be within the nodes object range.
	template <typename F>
	zx_status_t ForEveryPageInRange(F func, uint64_t start_offset, uint64_t end_offset,
	uint64_t skew) {
	return ForEveryPageInRange(this, func, start_offset, end_offset, skew);
	}

	// for every page or marker in the node in the range call the passed in function. The range is
	// assumed to be within the nodes object range.
	template <typename F>
	zx_status_t ForEveryPageInRange(F func, uint64_t start_offset, uint64_t end_offset,
	uint64_t skew) const {
	return ForEveryPageInRange(this, func, start_offset, end_offset, skew);
	}

	const VmPageOrMarker& Lookup(size_t index) const {
	canary_.Assert();
	DEBUG_ASSERT(index < kPageFanOut);
	return pages_[index];
	}

	VmPageOrMarker& Lookup(size_t index) {
	canary_.Assert();
	DEBUG_ASSERT(index < kPageFanOut);
	return pages_[index];
	}

	// A node is empty if it contains no pages or markers.
	bool IsEmpty() const {
	for (const auto& p : pages_) {
	if (!p.IsEmpty()) {
	return false;
	}
	}
	return true;
	}

	// Returns true if there are still allocated vm_page_t's owned by this node.
	bool HasNoPages() const {
	for (const auto& p : pages_) {
	if (p.IsPage()) {
	return false;
	}
	}
	return true;
	}

	private:
	template <typename S, typename F>
	static zx_status_t ForEveryPageInRange(S self, F func, uint64_t start_offset, uint64_t end_offset,
	uint64_t skew) {
	// Assert that the requested range is sensible and falls within our nodes actual offset range.
	DEBUG_ASSERT(end_offset >= start_offset);
	DEBUG_ASSERT(start_offset >= self->obj_offset_);
	DEBUG_ASSERT(end_offset <= self->end_offset());
	const size_t start = (start_offset - self->obj_offset_) / PAGE_SIZE;
	const size_t end = (end_offset - self->obj_offset_) / PAGE_SIZE;
	for (size_t i = start; i < end; i++) {
	if (!self->pages_[i].IsEmpty()) {
	zx_status_t status = func(&self->pages_[i], self->obj_offset_ + i * PAGE_SIZE - skew);
	if (unlikely(status != ZX_ERR_NEXT)) {
	return status;
	}
	}
	}
	return ZX_ERR_NEXT;
	}

	fbl::Canary<fbl::magic("PLST")> canary_;

	uint64_t obj_offset_ = 0;
	VmPageOrMarker pages_[kPageFanOut];
	};

	class VmPageList;

	// Class which holds the list of vm_page structs removed from a VmPageList
	// by TakePages. The list include information about uncommitted pages and markers.
	class VmPageSpliceList final {
	public:
	VmPageSpliceList();
	VmPageSpliceList(VmPageSpliceList&& other);
	VmPageSpliceList& operator=(VmPageSpliceList&& other_tree);
	~VmPageSpliceList();

	// Pops the next page off of the splice.
	VmPageOrMarker Pop();

	// Returns true after the whole collection has been processed by Pop.
	bool IsDone() const { return pos_ >= length_; }

	DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(VmPageSpliceList);

	private:
	VmPageSpliceList(uint64_t offset, uint64_t length);
	void FreeAllPages();

	uint64_t offset_;
	uint64_t length_;
	uint64_t pos_ = 0;

	VmPageListNode head_ = VmPageListNode(0);
	fbl::WAVLTree<uint64_t, ktl::unique_ptr<VmPageListNode>> middle_;
	VmPageListNode tail_ = VmPageListNode(0);

	friend VmPageList;
	};

	class VmPageList final {
	public:
	VmPageList();
	~VmPageList();

	VmPageList& operator=(VmPageList&& other);
	VmPageList(VmPageList&& other);

	void InitializeSkew(uint64_t parent_skew, uint64_t offset) {
	// Checking list_skew_ doesn't catch all instances of double-initialization, but
	// it should catch some of them.
	DEBUG_ASSERT(list_skew_ == 0);
	DEBUG_ASSERT(list_.is_empty());

	list_skew_ = (parent_skew + offset) % (PAGE_SIZE * VmPageListNode::kPageFanOut);
	}
	uint64_t GetSkew() const { return list_skew_; }

	DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(VmPageList);

	// walk the page tree, calling the passed in function on every tree node.
	template <typename F>
	zx_status_t ForEveryPage(F per_page_func) const {
	return ForEveryPage(this, per_page_func);
	}

	// walk the page tree, calling the passed in function on every tree node.
	template <typename F>
	zx_status_t ForEveryPageInRange(F per_page_func, uint64_t start_offset,
	uint64_t end_offset) const {
	return ForEveryPageInRange(this, per_page_func, start_offset, end_offset);
	}

	// walk the page tree, calling \|per_page_func\| on every page/marker and \|per_gap_func\| on every
	// gap.
	template <typename PAGE_FUNC, typename GAP_FUNC>
	zx_status_t ForEveryPageAndGapInRange(PAGE_FUNC per_page_func, GAP_FUNC per_gap_func,
	uint64_t start_offset, uint64_t end_offset) const {
	return ForEveryPageAndGapInRange(this, per_page_func, per_gap_func, start_offset, end_offset);
	}

	// Returns true if any pages or markers are in the given range.
	bool AnyPagesInRange(uint64_t start_offset, uint64_t end_offset) const {
	bool found_page = false;
	ForEveryPageInRange(
	[&found_page](const VmPageOrMarker* page, uint64_t offset) {
	found_page = true;
	return ZX_ERR_STOP;
	},
	start_offset, end_offset);
	return found_page;
	}

	// 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.
	const VmPageOrMarker* Lookup(uint64_t offset) const;
	VmPageOrMarker* Lookup(uint64_t offset);

	// Similar to `Lookup` but only returns `nullptr` if a slot cannot be allocated either due to out
	// of memory or due to offset being invalid.
	VmPageOrMarker* LookupOrAllocate(uint64_t offset);

	// Removes any page at \|offset\| from the list and returns it, or VmPageOrMarker::Empty() if none.
	VmPageOrMarker RemovePage(uint64_t offset);

	// Release every page in the in the page list and calls free_page_fn on each one, giving it
	// ownership. Any markers are cleared.
	template <typename T>
	void RemoveAllPages(T free_page_fn) {
	// per page get a reference to the page pointer inside the page list node
	auto per_page_func = [&free_page_fn](VmPageOrMarker* p, uint64_t offset) {
	if (p->IsPage()) {
	free_page_fn(p->ReleasePage());
	}
	*p = VmPageOrMarker::Empty();
	return ZX_ERR_NEXT;
	};

	// walk the tree in order, freeing all the pages on every node
	ForEveryPage(this, per_page_func);

	// empty the tree
	list_.clear();
	}

	// 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.
	template <typename T>
	void RemovePages(T per_page_fn, uint64_t start_offset, uint64_t end_offset) {
	ForEveryPageInRange<NodeCheck::CleanupEmpty>(this, per_page_fn, start_offset, end_offset);
	}

	// Returns true if there are no pages or markers in the page list.
	bool IsEmpty() const;

	// Returns true if the page list does not own any vm_page.
	bool HasNoPages() const;

	// Merges the pages in \|other\| in the range [\|offset\|, \|end_offset\|) into \|this\|
	// page list, starting at offset 0 in this list.
	//
	// For every page in \|other\| in the given range, if there is no corresponding page or marker
	// in \|this\|, then they will be passed to \|migrate_fn\|. If \|migrate_fn\| leaves the page in the
	// VmPageOrMarker it will be migrated into \|this\|, otherwise the migrate_fn is assumed to now own
	// the page. For any pages in \|other\| outside the given range or which conflict with a page in
	// \|this\|, they will be released given ownership to \|release_fn\|.
	//
	// The \|offset\| values passed to \|release_fn\| and \|migrate_fn\| are the original offsets
	// in \|other\|, not the adapted offsets in \|this\|.
	//
	// NOTE unlike MergeOnto, \|other\| will be empty at the end of this method.
	void MergeFrom(VmPageList& other, uint64_t offset, uint64_t end_offset,
	fbl::Function<void(vm_page*, uint64_t offset)> release_fn,
	fbl::Function<void(VmPageOrMarker*, uint64_t offset)> migrate_fn);

	// Merges this pages in \|this\| onto \|other\|.
	//
	// For every page (or marker) in \|this\|, checks the same offset in \|other\|. If there is no
	// page or marker, then it inserts the page into \|other\|. Otherwise, it releases the page and
	// gives ownership to \|release_fn\|.
	//
	// NOTE unlike MergeFrom, \|this\| will be empty at the end of this method.
	void MergeOnto(VmPageList& other, fbl::Function<void(vm_page*)> release_fn);

	// Takes the pages and markers in the range [offset, length) out of this page list.
	VmPageSpliceList TakePages(uint64_t offset, uint64_t length);

	uint64_t HeapAllocationBytes() const { return list_.size() * sizeof(VmPageListNode); }

	// Allow the implementation to use a one-past-the-end for VmPageListNode offsets,
	// plus to account for skew_.
	static constexpr uint64_t MAX_SIZE =
	ROUNDDOWN(UINT64_MAX, 2 * VmPageListNode::kPageFanOut * PAGE_SIZE);

	private:
	template <typename S, typename F>
	static zx_status_t ForEveryPage(S self, F per_page_func) {
	for (auto& pl : self->list_) {
	zx_status_t status = pl.ForEveryPage(per_page_func, self->list_skew_);
	if (unlikely(status != ZX_ERR_NEXT)) {
	if (status == ZX_ERR_STOP) {
	break;
	}
	return status;
	}
	}
	return ZX_OK;
	}

	// Calls the provided callback for every page in the given range. If the CleanupNodes template
	// argument is true then it is assumed the per_page_func may remove pages and page nodes will be
	// checked to see if they are empty and can be cleaned up.
	enum class NodeCheck : bool {
	Skip = false,
	CleanupEmpty = true,
	};
	template <NodeCheck NODE_CHECK = NodeCheck::Skip, typename S, typename F>
	static zx_status_t ForEveryPageInRange(S self, F per_page_func, uint64_t start_offset,
	uint64_t end_offset) {
	start_offset += self->list_skew_;
	end_offset += self->list_skew_;

	// Find the first node (if any) that will contain our starting offset.
	auto cur =
	self->list_.lower_bound(ROUNDDOWN(start_offset, VmPageListNode::kPageFanOut * PAGE_SIZE));
	if (!cur) {
	return ZX_OK;
	}

	// Handle scenario where start_offset begins not aligned to a node.
	if (cur->offset() < start_offset) {
	zx_status_t status = cur->ForEveryPageInRange(
	per_page_func, start_offset, ktl::min(end_offset, cur->end_offset()), self->list_skew_);
	auto prev = cur++;
	if constexpr (NODE_CHECK == NodeCheck::CleanupEmpty) {
	if (prev->IsEmpty()) {
	self->list_.erase(prev);
	}
	}
	if (unlikely(status != ZX_ERR_NEXT)) {
	if (status == ZX_ERR_STOP) {
	return ZX_OK;
	}
	return status;
	}
	}
	// Iterate through all full nodes contained in the range.
	while (cur && cur->end_offset() < end_offset) {
	DEBUG_ASSERT(start_offset <= cur->offset());
	zx_status_t status = cur->ForEveryPage(per_page_func, self->list_skew_);
	auto prev = cur++;
	if constexpr (NODE_CHECK == NodeCheck::CleanupEmpty) {
	if (prev->IsEmpty()) {
	self->list_.erase(prev);
	}
	}
	if (unlikely(status != ZX_ERR_NEXT)) {
	if (status == ZX_ERR_STOP) {
	return ZX_OK;
	}
	return status;
	}
	}
	// Handle scenario where the end_offset is not aligned to the end of a node.
	if (cur && cur->offset() < end_offset) {
	DEBUG_ASSERT(cur->end_offset() >= end_offset);
	zx_status_t status =
	cur->ForEveryPageInRange(per_page_func, cur->offset(), end_offset, self->list_skew_);
	if constexpr (NODE_CHECK == NodeCheck::CleanupEmpty) {
	if (cur->IsEmpty()) {
	self->list_.erase(cur);
	}
	}
	if (unlikely(status != ZX_ERR_NEXT)) {
	if (status == ZX_ERR_STOP) {
	return ZX_OK;
	}
	return status;
	}
	}
	return ZX_OK;
	}

	template <typename S, typename PAGE_FUNC, typename GAP_FUNC>
	static zx_status_t ForEveryPageAndGapInRange(S self, PAGE_FUNC per_page_func,
	GAP_FUNC per_gap_func, uint64_t start_offset,
	uint64_t end_offset) {
	uint64_t expected_next_off = start_offset;
	auto per_page_wrapper_fn = [&expected_next_off, end_offset, per_page_func, &per_gap_func](
	auto* p, uint64_t off) {
	zx_status_t status = ZX_ERR_NEXT;
	if (expected_next_off != off) {
	status = per_gap_func(expected_next_off, off);
	}
	if (status == ZX_ERR_NEXT) {
	status = per_page_func(p, off);
	}
	expected_next_off = off + PAGE_SIZE;
	// Prevent the last call to per_gap_func
	if (status == ZX_ERR_STOP) {
	expected_next_off = end_offset;
	}
	return status;
	};

	zx_status_t status = ForEveryPageInRange(self, per_page_wrapper_fn, start_offset, end_offset);
	if (status != ZX_OK) {
	return status;
	}

	if (expected_next_off != end_offset) {
	status = per_gap_func(expected_next_off, end_offset);
	if (status != ZX_ERR_NEXT && status != ZX_ERR_STOP) {
	return status;
	}
	}

	return ZX_OK;
	}

	fbl::WAVLTree<uint64_t, ktl::unique_ptr<VmPageListNode>> list_;
	// A skew added to offsets provided as arguments to VmPageList functions before
	// interfacing with list_. This allows all VmPageLists within a clone tree
	// to place individual vm_page_t entries at the same offsets within their nodes, so
	// that the nodes can be moved between different lists without having to worry
	// about needing to split up a node.
	uint64_t list_skew_ = 0;
	};

	#endif // ZIRCON_KERNEL_VM_INCLUDE_VM_VM_PAGE_LIST_H_