kernel/vm/vm_page_list.cpp - zircon/ - 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

 #include <vm/vm_page_list.h>

 #include <err.h>
 #include <fbl/alloc_checker.h>
 #include <inttypes.h>
 #include <ktl/move.h>
 #include <trace.h>
 #include <vm/pmm.h>
 #include <vm/vm.h>
 #include <vm/vm_object_paged.h>
 #include <zircon/types.h>

 #include "vm_priv.h"

 #define LOCAL_TRACE MAX(VM_GLOBAL_TRACE, 0)

 namespace {

 inline uint64_t offset_to_node_offset(uint64_t offset) {
     return ROUNDDOWN(offset, PAGE_SIZE * VmPageListNode::kPageFanOut);
 }

 inline uint64_t offset_to_node_index(uint64_t offset) {
     return (offset >> PAGE_SIZE_SHIFT) % VmPageListNode::kPageFanOut;
 }

 inline void move_vm_page_list_node(VmPageListNode* dest, VmPageListNode* src) {
     // Called by move ctor/assignment. Move assignment clears the dest node first.
     ASSERT(dest->IsEmpty());

     for (unsigned i = 0; i < VmPageListNode::kPageFanOut; i++) {
         vm_page* page = src->RemovePage(i);
         if (page) {
             dest->AddPage(page, i);
         }
     }
 }

 } // namespace

 VmPageListNode::VmPageListNode(uint64_t offset)
     : obj_offset_(offset) {
     LTRACEF("%p offset %#" PRIx64 "\n", this, obj_offset_);
 }

 VmPageListNode::~VmPageListNode() {
     LTRACEF("%p offset %#" PRIx64 "\n", this, obj_offset_);
     canary_.Assert();

     for (__UNUSED auto p : pages_) {
         DEBUG_ASSERT(p == nullptr);
     }
 }

 vm_page* VmPageListNode::GetPage(size_t index) {
     canary_.Assert();
     DEBUG_ASSERT(index < kPageFanOut);
     return pages_[index];
 }

 vm_page* VmPageListNode::RemovePage(size_t index) {
     canary_.Assert();
     DEBUG_ASSERT(index < kPageFanOut);

     auto p = pages_[index];
     if (!p) {
         return nullptr;
     }

     pages_[index] = nullptr;

     return p;
 }

 zx_status_t VmPageListNode::AddPage(vm_page* p, size_t index) {
     canary_.Assert();
     DEBUG_ASSERT(index < kPageFanOut);
     if (pages_[index]) {
         return ZX_ERR_ALREADY_EXISTS;
     }
     pages_[index] = p;
     return ZX_OK;
 }

 VmPageList::VmPageList() {
     LTRACEF("%p\n", this);
 }

 VmPageList::~VmPageList() {
     LTRACEF("%p\n", this);
     DEBUG_ASSERT(list_.is_empty());
 }

 zx_status_t VmPageList::AddPage(vm_page* p, uint64_t offset) {
     uint64_t node_offset = offset_to_node_offset(offset);
     size_t index = offset_to_node_index(offset);

     if (node_offset >= VmObjectPaged::MAX_SIZE) {
         return ZX_ERR_OUT_OF_RANGE;
     }

     LTRACEF_LEVEL(2, "%p page %p, offset %#" PRIx64 " node_offset %#" PRIx64 " index %zu\n", this, p, offset,
                   node_offset, index);

     // lookup the tree node that holds this page
     auto pln = list_.find(node_offset);
     if (!pln.IsValid()) {
         fbl::AllocChecker ac;
         ktl::unique_ptr<VmPageListNode> pl =
             ktl::unique_ptr<VmPageListNode>(new (&ac) VmPageListNode(node_offset));
         if (!ac.check()) {
             return ZX_ERR_NO_MEMORY;
         }

         LTRACEF("allocating new inner node %p\n", pl.get());
         __UNUSED auto status = pl->AddPage(p, index);
         DEBUG_ASSERT(status == ZX_OK);

         list_.insert(ktl::move(pl));
         return ZX_OK;
     } else {
         return pln->AddPage(p, index);
     }
 }

 vm_page* VmPageList::GetPage(uint64_t offset) {
     uint64_t node_offset = offset_to_node_offset(offset);
     size_t index = offset_to_node_index(offset);

     LTRACEF_LEVEL(2, "%p offset %#" PRIx64 " node_offset %#" PRIx64 " index %zu\n", this, offset, node_offset,
                   index);

     // lookup the tree node that holds this page
     auto pln = list_.find(node_offset);
     if (!pln.IsValid()) {
         return nullptr;
     }

     return pln->GetPage(index);
 }

 bool VmPageList::RemovePage(uint64_t offset, vm_page_t** page_out) {
     DEBUG_ASSERT(page_out);

     uint64_t node_offset = offset_to_node_offset(offset);
     size_t index = offset_to_node_index(offset);

     LTRACEF_LEVEL(2, "%p offset %#" PRIx64 " node_offset %#" PRIx64 " index %zu\n", this, offset, node_offset,
                   index);

     // lookup the tree node that holds this page
     auto pln = list_.find(node_offset);
     if (!pln.IsValid()) {
         return false;
     }

     // free this page
     auto page = pln->RemovePage(index);
     if (page) {
         // if it was the last page in the node, remove the node from the tree
         if (pln->IsEmpty()) {
             LTRACEF_LEVEL(2, "%p freeing the list node\n", this);
             list_.erase(*pln);
         }

         *page_out = page;
         return true;
     } else {
         return false;
     }
 }

 void VmPageList::FreePages(uint64_t start_offset, uint64_t end_offset) {
     // Find the first node with a start after start_offset; if start_offset
     // is in a node, it'll be in the one before that one.
     auto start = --list_.upper_bound(start_offset);
     if (!start.IsValid()) {
         start = list_.begin();
     }
     // Find the first node which is completely after the end of the region. If
     // end_offset falls in the middle of a node, this finds the next node.
     const auto end = list_.lower_bound(end_offset);

     list_node list;
     list_initialize(&list);

     // Visitor function which moves the pages from the VmPageListNode
     // to the accumulation list.
     auto per_page_func = [&list](vm_page*& p, uint64_t offset) {
         list_add_tail(&list, &p->queue_node);
         p = nullptr;
         return ZX_ERR_NEXT;
     };

     // Iterate through all nodes which have at least some overlap with the
     // region, freeing the pages and erasing nodes which become empty.
     while (start != end) {
         auto cur = start++;
         cur->ForEveryPage(per_page_func, start_offset, end_offset);
         if (cur->IsEmpty()) {
             list_.erase(cur);
         }
     }

     pmm_free(&list);
 }

 size_t VmPageList::FreeAllPages() {
     LTRACEF("%p\n", this);

     list_node list;
     list_initialize(&list);

     size_t count = 0;

     // per page get a reference to the page pointer inside the page list node
     auto per_page_func = [&](vm_page*& p, uint64_t offset) {

         // add the page to our list and null out the inner node
         list_add_tail(&list, &p->queue_node);
         p = nullptr;
         count++;
         return ZX_ERR_NEXT;
     };

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

     // return all the pages to the pmm at once
     pmm_free(&list);

     // empty the tree
     list_.clear();

     return count;
 }

 bool VmPageList::IsEmpty() {
     return list_.is_empty();
 }

 VmPageSpliceList VmPageList::TakePages(uint64_t offset, uint64_t length) {
     VmPageSpliceList res(offset, length);
     const uint64_t end = offset + length;

     // If we can't take the whole node at the start of the range,
     // the shove the pages into the splice list head_ node.
     while (offset_to_node_index(offset) != 0 && offset < end) {
         vm_page_t* page;
         if (RemovePage(offset, &page)) {
             res.head_.AddPage(page, offset_to_node_index(offset));
         }
         offset += PAGE_SIZE;
     }

     // As long as the current and end node offsets are different, we
     // can just move the whole node into the splice list.
     while (offset_to_node_offset(offset) != offset_to_node_offset(end)) {
         ktl::unique_ptr<VmPageListNode> node = list_.erase(offset_to_node_offset(offset));
         if (node) {
             res.middle_.insert(ktl::move(node));
         }
         offset += (PAGE_SIZE * VmPageListNode::kPageFanOut);
     }

     // Move any remaining pages into the splice list tail_ node.
     while (offset < end) {
         vm_page_t* page;
         if (RemovePage(offset, &page)) {
             res.tail_.AddPage(page, offset_to_node_index(offset));
         }
         offset += PAGE_SIZE;
     }

     return res;
 }

 VmPageSpliceList::VmPageSpliceList() : VmPageSpliceList(0, 0) {}

 VmPageSpliceList::VmPageSpliceList(uint64_t offset, uint64_t length)
     : offset_(offset), length_(length) {
 }

 VmPageSpliceList::VmPageSpliceList(VmPageSpliceList&& other)
     : offset_(other.offset_), length_(other.length_),
       pos_(other.pos_), middle_(ktl::move(other.middle_)) {
     move_vm_page_list_node(&head_, &other.head_);
     move_vm_page_list_node(&tail_, &other.tail_);

     other.offset_ = other.length_ = other.pos_ = 0;
 }

 VmPageSpliceList& VmPageSpliceList::operator=(VmPageSpliceList&& other) {
     FreeAllPages();

     offset_ = other.offset_;
     length_ = other.length_;
     pos_ = other.pos_;
     move_vm_page_list_node(&head_, &other.head_);
     move_vm_page_list_node(&tail_, &other.tail_);
     middle_ = ktl::move(other.middle_);

     other.offset_ = other.length_ = other.pos_ = 0;

     return *this;
 }

 VmPageSpliceList::~VmPageSpliceList() {
     FreeAllPages();
 }

 void VmPageSpliceList::FreeAllPages() {
     // Free any pages owned by the splice list.
     while (!IsDone()) {
         auto page = Pop();
         if (page) {
             pmm_free_page(page);
         }
     }
 }

 vm_page* VmPageSpliceList::Pop() {
     if (IsDone()) {
         DEBUG_ASSERT_MSG(false, "Popped from empty splice list");
         return nullptr;
     }

     const uint64_t cur_offset = offset_ + pos_;
     const auto cur_node_idx = offset_to_node_index(cur_offset);
     const auto cur_node_offset = offset_to_node_offset(cur_offset);

     vm_page* res;
     if (offset_to_node_index(offset_) != 0
             && offset_to_node_offset(offset_) == cur_node_offset) {
         // If the original offset means that pages were placed in head_
         // and the current offset points to the same node, look there.
         res = head_.RemovePage(cur_node_idx);
     } else if (cur_node_offset != offset_to_node_offset(offset_ + length_)) {
         // If the current offset isn't pointing to the tail node,
         // look in the middle tree.
         auto middle_node = middle_.find(cur_node_offset);
         if (middle_node.IsValid()) {
             res = middle_node->RemovePage(cur_node_idx);
         } else {
             res = nullptr;
         }
     } else {
         // If none of the other cases, we're in the tail_.
         res = tail_.RemovePage(cur_node_idx);
     }

     pos_ += PAGE_SIZE;
     return res;
 }
	// 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

	#include <vm/vm_page_list.h>

	#include <err.h>
	#include <fbl/alloc_checker.h>
	#include <inttypes.h>
	#include <ktl/move.h>
	#include <trace.h>
	#include <vm/pmm.h>
	#include <vm/vm.h>
	#include <vm/vm_object_paged.h>
	#include <zircon/types.h>

	#include "vm_priv.h"

	#define LOCAL_TRACE MAX(VM_GLOBAL_TRACE, 0)

	namespace {

	inline uint64_t offset_to_node_offset(uint64_t offset) {
	return ROUNDDOWN(offset, PAGE_SIZE * VmPageListNode::kPageFanOut);
	}

	inline uint64_t offset_to_node_index(uint64_t offset) {
	return (offset >> PAGE_SIZE_SHIFT) % VmPageListNode::kPageFanOut;
	}

	inline void move_vm_page_list_node(VmPageListNode* dest, VmPageListNode* src) {
	// Called by move ctor/assignment. Move assignment clears the dest node first.
	ASSERT(dest->IsEmpty());

	for (unsigned i = 0; i < VmPageListNode::kPageFanOut; i++) {
	vm_page* page = src->RemovePage(i);
	if (page) {
	dest->AddPage(page, i);
	}
	}
	}

	} // namespace

	VmPageListNode::VmPageListNode(uint64_t offset)
	: obj_offset_(offset) {
	LTRACEF("%p offset %#" PRIx64 "\n", this, obj_offset_);
	}

	VmPageListNode::~VmPageListNode() {
	LTRACEF("%p offset %#" PRIx64 "\n", this, obj_offset_);
	canary_.Assert();

	for (__UNUSED auto p : pages_) {
	DEBUG_ASSERT(p == nullptr);
	}
	}

	vm_page* VmPageListNode::GetPage(size_t index) {
	canary_.Assert();
	DEBUG_ASSERT(index < kPageFanOut);
	return pages_[index];
	}

	vm_page* VmPageListNode::RemovePage(size_t index) {
	canary_.Assert();
	DEBUG_ASSERT(index < kPageFanOut);

	auto p = pages_[index];
	if (!p) {
	return nullptr;
	}

	pages_[index] = nullptr;

	return p;
	}

	zx_status_t VmPageListNode::AddPage(vm_page* p, size_t index) {
	canary_.Assert();
	DEBUG_ASSERT(index < kPageFanOut);
	if (pages_[index]) {
	return ZX_ERR_ALREADY_EXISTS;
	}
	pages_[index] = p;
	return ZX_OK;
	}

	VmPageList::VmPageList() {
	LTRACEF("%p\n", this);
	}

	VmPageList::~VmPageList() {
	LTRACEF("%p\n", this);
	DEBUG_ASSERT(list_.is_empty());
	}

	zx_status_t VmPageList::AddPage(vm_page* p, uint64_t offset) {
	uint64_t node_offset = offset_to_node_offset(offset);
	size_t index = offset_to_node_index(offset);

	if (node_offset >= VmObjectPaged::MAX_SIZE) {
	return ZX_ERR_OUT_OF_RANGE;
	}

	LTRACEF_LEVEL(2, "%p page %p, offset %#" PRIx64 " node_offset %#" PRIx64 " index %zu\n", this, p, offset,
	node_offset, index);

	// lookup the tree node that holds this page
	auto pln = list_.find(node_offset);
	if (!pln.IsValid()) {
	fbl::AllocChecker ac;
	ktl::unique_ptr<VmPageListNode> pl =
	ktl::unique_ptr<VmPageListNode>(new (&ac) VmPageListNode(node_offset));
	if (!ac.check()) {
	return ZX_ERR_NO_MEMORY;
	}

	LTRACEF("allocating new inner node %p\n", pl.get());
	__UNUSED auto status = pl->AddPage(p, index);
	DEBUG_ASSERT(status == ZX_OK);

	list_.insert(ktl::move(pl));
	return ZX_OK;
	} else {
	return pln->AddPage(p, index);
	}
	}

	vm_page* VmPageList::GetPage(uint64_t offset) {
	uint64_t node_offset = offset_to_node_offset(offset);
	size_t index = offset_to_node_index(offset);

	LTRACEF_LEVEL(2, "%p offset %#" PRIx64 " node_offset %#" PRIx64 " index %zu\n", this, offset, node_offset,
	index);

	// lookup the tree node that holds this page
	auto pln = list_.find(node_offset);
	if (!pln.IsValid()) {
	return nullptr;
	}

	return pln->GetPage(index);
	}

	bool VmPageList::RemovePage(uint64_t offset, vm_page_t** page_out) {
	DEBUG_ASSERT(page_out);

	uint64_t node_offset = offset_to_node_offset(offset);
	size_t index = offset_to_node_index(offset);

	LTRACEF_LEVEL(2, "%p offset %#" PRIx64 " node_offset %#" PRIx64 " index %zu\n", this, offset, node_offset,
	index);

	// lookup the tree node that holds this page
	auto pln = list_.find(node_offset);
	if (!pln.IsValid()) {
	return false;
	}

	// free this page
	auto page = pln->RemovePage(index);
	if (page) {
	// if it was the last page in the node, remove the node from the tree
	if (pln->IsEmpty()) {
	LTRACEF_LEVEL(2, "%p freeing the list node\n", this);
	list_.erase(*pln);
	}

	*page_out = page;
	return true;
	} else {
	return false;
	}
	}

	void VmPageList::FreePages(uint64_t start_offset, uint64_t end_offset) {
	// Find the first node with a start after start_offset; if start_offset
	// is in a node, it'll be in the one before that one.
	auto start = --list_.upper_bound(start_offset);
	if (!start.IsValid()) {
	start = list_.begin();
	}
	// Find the first node which is completely after the end of the region. If
	// end_offset falls in the middle of a node, this finds the next node.
	const auto end = list_.lower_bound(end_offset);

	list_node list;
	list_initialize(&list);

	// Visitor function which moves the pages from the VmPageListNode
	// to the accumulation list.
	auto per_page_func = [&list](vm_page*& p, uint64_t offset) {
	list_add_tail(&list, &p->queue_node);
	p = nullptr;
	return ZX_ERR_NEXT;
	};

	// Iterate through all nodes which have at least some overlap with the
	// region, freeing the pages and erasing nodes which become empty.
	while (start != end) {
	auto cur = start++;
	cur->ForEveryPage(per_page_func, start_offset, end_offset);
	if (cur->IsEmpty()) {
	list_.erase(cur);
	}
	}

	pmm_free(&list);
	}

	size_t VmPageList::FreeAllPages() {
	LTRACEF("%p\n", this);

	list_node list;
	list_initialize(&list);

	size_t count = 0;

	// per page get a reference to the page pointer inside the page list node
	auto per_page_func = [&](vm_page*& p, uint64_t offset) {

	// add the page to our list and null out the inner node
	list_add_tail(&list, &p->queue_node);
	p = nullptr;
	count++;
	return ZX_ERR_NEXT;
	};

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

	// return all the pages to the pmm at once
	pmm_free(&list);

	// empty the tree
	list_.clear();

	return count;
	}

	bool VmPageList::IsEmpty() {
	return list_.is_empty();
	}

	VmPageSpliceList VmPageList::TakePages(uint64_t offset, uint64_t length) {
	VmPageSpliceList res(offset, length);
	const uint64_t end = offset + length;

	// If we can't take the whole node at the start of the range,
	// the shove the pages into the splice list head_ node.
	while (offset_to_node_index(offset) != 0 && offset < end) {
	vm_page_t* page;
	if (RemovePage(offset, &page)) {
	res.head_.AddPage(page, offset_to_node_index(offset));
	}
	offset += PAGE_SIZE;
	}

	// As long as the current and end node offsets are different, we
	// can just move the whole node into the splice list.
	while (offset_to_node_offset(offset) != offset_to_node_offset(end)) {
	ktl::unique_ptr<VmPageListNode> node = list_.erase(offset_to_node_offset(offset));
	if (node) {
	res.middle_.insert(ktl::move(node));
	}
	offset += (PAGE_SIZE * VmPageListNode::kPageFanOut);
	}

	// Move any remaining pages into the splice list tail_ node.
	while (offset < end) {
	vm_page_t* page;
	if (RemovePage(offset, &page)) {
	res.tail_.AddPage(page, offset_to_node_index(offset));
	}
	offset += PAGE_SIZE;
	}

	return res;
	}

	VmPageSpliceList::VmPageSpliceList() : VmPageSpliceList(0, 0) {}

	VmPageSpliceList::VmPageSpliceList(uint64_t offset, uint64_t length)
	: offset_(offset), length_(length) {
	}

	VmPageSpliceList::VmPageSpliceList(VmPageSpliceList&& other)
	: offset_(other.offset_), length_(other.length_),
	pos_(other.pos_), middle_(ktl::move(other.middle_)) {
	move_vm_page_list_node(&head_, &other.head_);
	move_vm_page_list_node(&tail_, &other.tail_);

	other.offset_ = other.length_ = other.pos_ = 0;
	}

	VmPageSpliceList& VmPageSpliceList::operator=(VmPageSpliceList&& other) {
	FreeAllPages();

	offset_ = other.offset_;
	length_ = other.length_;
	pos_ = other.pos_;
	move_vm_page_list_node(&head_, &other.head_);
	move_vm_page_list_node(&tail_, &other.tail_);
	middle_ = ktl::move(other.middle_);

	other.offset_ = other.length_ = other.pos_ = 0;

	return *this;
	}

	VmPageSpliceList::~VmPageSpliceList() {
	FreeAllPages();
	}

	void VmPageSpliceList::FreeAllPages() {
	// Free any pages owned by the splice list.
	while (!IsDone()) {
	auto page = Pop();
	if (page) {
	pmm_free_page(page);
	}
	}
	}

	vm_page* VmPageSpliceList::Pop() {
	if (IsDone()) {
	DEBUG_ASSERT_MSG(false, "Popped from empty splice list");
	return nullptr;
	}

	const uint64_t cur_offset = offset_ + pos_;
	const auto cur_node_idx = offset_to_node_index(cur_offset);
	const auto cur_node_offset = offset_to_node_offset(cur_offset);

	vm_page* res;
	if (offset_to_node_index(offset_) != 0
	&& offset_to_node_offset(offset_) == cur_node_offset) {
	// If the original offset means that pages were placed in head_
	// and the current offset points to the same node, look there.
	res = head_.RemovePage(cur_node_idx);
	} else if (cur_node_offset != offset_to_node_offset(offset_ + length_)) {
	// If the current offset isn't pointing to the tail node,
	// look in the middle tree.
	auto middle_node = middle_.find(cur_node_offset);
	if (middle_node.IsValid()) {
	res = middle_node->RemovePage(cur_node_idx);
	} else {
	res = nullptr;
	}
	} else {
	// If none of the other cases, we're in the tail_.
	res = tail_.RemovePage(cur_node_idx);
	}

	pos_ += PAGE_SIZE;
	return res;
	}