[kernel][vm] Add ability to take runs of pages from VmPageList
This functionality will be used in a subsequent pager change.
Test: k ut vmpl
Change-Id: Ifd54a8fe0a226e1cbfe622e41ca6ab42a06a5613
diff --git a/kernel/vm/include/vm/vm_page_list.h b/kernel/vm/include/vm/vm_page_list.h
index 1ba1eb3..d569923 100644
--- a/kernel/vm/include/vm/vm_page_list.h
+++ b/kernel/vm/include/vm/vm_page_list.h
@@ -101,6 +101,40 @@
vm_page* 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.
+class VmPageSpliceList final {
+public:
+ VmPageSpliceList();
+ VmPageSpliceList(VmPageSpliceList&& other);
+ VmPageSpliceList& operator=(VmPageSpliceList&& other_tree);
+ ~VmPageSpliceList();
+
+ // Pops the next page off of the splice. If the next page was
+ // not commited, returns null.
+ vm_page* 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();
@@ -190,10 +224,16 @@
zx_status_t AddPage(vm_page*, uint64_t offset);
vm_page* GetPage(uint64_t offset);
- zx_status_t FreePage(uint64_t offset);
+ // Removes the page at |offset| from the list. Returns true if a page
+ // was present, false otherwise. If |page| is non-null, returns the
+ // physical page in it, otherwise frees the page.
+ bool RemovePage(uint64_t offset, vm_page** page);
size_t FreeAllPages();
bool IsEmpty();
+ // Takes the pages in the range [offset, length) out of this page list.
+ VmPageSpliceList TakePages(uint64_t offset, uint64_t length);
+
private:
fbl::WAVLTree<uint64_t, ktl::unique_ptr<VmPageListNode>> list_;
};
diff --git a/kernel/vm/vm_object_paged.cpp b/kernel/vm/vm_object_paged.cpp
index 489c003..64ecde0 100644
--- a/kernel/vm/vm_object_paged.cpp
+++ b/kernel/vm/vm_object_paged.cpp
@@ -681,7 +681,7 @@
// iterate through the pages, freeing them
// TODO: use page_list iterator, move pages to list, free at once
while (start < end) {
- page_list_.FreePage(start);
+ page_list_.RemovePage(start, nullptr);
start += PAGE_SIZE;
}
@@ -839,7 +839,7 @@
// iterate through the pages, freeing them
// TODO: use page_list iterator, move pages to list, free at once
while (start < end) {
- page_list_.FreePage(start);
+ page_list_.RemovePage(start, nullptr);
start += PAGE_SIZE;
}
} else if (s > size_) {
diff --git a/kernel/vm/vm_page_list.cpp b/kernel/vm/vm_page_list.cpp
index 74bdf26..e43330b 100644
--- a/kernel/vm/vm_page_list.cpp
+++ b/kernel/vm/vm_page_list.cpp
@@ -19,6 +19,30 @@
#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_);
@@ -73,8 +97,8 @@
}
zx_status_t VmPageList::AddPage(vm_page* p, uint64_t offset) {
- uint64_t node_offset = ROUNDDOWN(offset, PAGE_SIZE * VmPageListNode::kPageFanOut);
- size_t index = (offset >> PAGE_SIZE_SHIFT) % VmPageListNode::kPageFanOut;
+ uint64_t node_offset = offset_to_node_offset(offset);
+ size_t index = offset_to_node_index(offset);
LTRACEF_LEVEL(2, "%p page %p, offset %#" PRIx64 " node_offset %#" PRIx64 " index %zu\n", this, p, offset,
node_offset, index);
@@ -101,8 +125,8 @@
}
vm_page* VmPageList::GetPage(uint64_t offset) {
- uint64_t node_offset = ROUNDDOWN(offset, PAGE_SIZE * VmPageListNode::kPageFanOut);
- size_t index = (offset >> PAGE_SIZE_SHIFT) % VmPageListNode::kPageFanOut;
+ 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);
@@ -116,9 +140,9 @@
return pln->GetPage(index);
}
-zx_status_t VmPageList::FreePage(uint64_t offset) {
- uint64_t node_offset = ROUNDDOWN(offset, PAGE_SIZE * VmPageListNode::kPageFanOut);
- size_t index = (offset >> PAGE_SIZE_SHIFT) % VmPageListNode::kPageFanOut;
+bool VmPageList::RemovePage(uint64_t offset, vm_page_t** 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);
@@ -126,7 +150,7 @@
// lookup the tree node that holds this page
auto pln = list_.find(node_offset);
if (!pln.IsValid()) {
- return ZX_ERR_NOT_FOUND;
+ return false;
}
// free this page
@@ -138,10 +162,15 @@
list_.erase(*pln);
}
- pmm_free_page(page);
+ if (!page_out) {
+ pmm_free_page(page);
+ } else {
+ *page_out = page;
+ }
+ return true;
+ } else {
+ return false;
}
-
- return ZX_OK;
}
size_t VmPageList::FreeAllPages() {
@@ -177,3 +206,117 @@
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;
+}
diff --git a/kernel/vm/vm_unittest.cpp b/kernel/vm/vm_unittest.cpp
index cd73775..52c10fd 100644
--- a/kernel/vm/vm_unittest.cpp
+++ b/kernel/vm/vm_unittest.cpp
@@ -1038,6 +1038,180 @@
END_TEST;
}
+// Basic test that checks adding/removing a page
+static bool vmpl_add_remove_page_test() {
+ BEGIN_TEST;
+
+ VmPageList pl;
+ vm_page_t test_page{};
+ pl.AddPage(&test_page, 0);
+
+ EXPECT_EQ(&test_page, pl.GetPage(0), "unexpected page\n");
+
+ vm_page* remove_page;
+ EXPECT_TRUE(pl.RemovePage(0, &remove_page), "remove failure\n");
+ EXPECT_EQ(&test_page, remove_page, "unexpected page\n");
+
+ END_TEST;
+}
+
+// Tests taking a page from the start of a VmPageListNode
+static bool vmpl_take_single_page_even_test() {
+ BEGIN_TEST;
+
+ VmPageList pl;
+ vm_page_t test_page{};
+ vm_page_t test_page2{};
+ pl.AddPage(&test_page, 0);
+ pl.AddPage(&test_page2, PAGE_SIZE);
+
+ VmPageSpliceList splice = pl.TakePages(0, PAGE_SIZE);
+
+ EXPECT_EQ(&test_page, splice.Pop(), "wrong page\n");
+ EXPECT_TRUE(splice.IsDone(), "extra page\n");
+ EXPECT_NULL(pl.GetPage(0), "duplicate page\n");
+
+ vm_page* remove_page;
+ EXPECT_TRUE(pl.RemovePage(PAGE_SIZE, &remove_page), "remove failure\n");
+ EXPECT_EQ(&test_page2, remove_page, "unexpected page\n");
+
+ END_TEST;
+}
+
+// Tests taking a page from the middle of a VmPageListNode
+static bool vmpl_take_single_page_odd_test() {
+ BEGIN_TEST;
+
+ VmPageList pl;
+ vm_page_t test_page{};
+ vm_page_t test_page2{};
+ pl.AddPage(&test_page, 0);
+ pl.AddPage(&test_page2, PAGE_SIZE);
+
+ VmPageSpliceList splice = pl.TakePages(PAGE_SIZE, PAGE_SIZE);
+
+ EXPECT_EQ(&test_page2, splice.Pop(), "wrong page\n");
+ EXPECT_TRUE(splice.IsDone(), "extra page\n");
+ EXPECT_NULL(pl.GetPage(PAGE_SIZE), "duplicate page\n");
+
+ vm_page* remove_page;
+ EXPECT_TRUE(pl.RemovePage(0, &remove_page), "remove failure\n");
+ EXPECT_EQ(&test_page, remove_page, "unexpected page\n");
+
+ END_TEST;
+}
+
+// Tests taking all the pages from a range of VmPageListNodes
+static bool vmpl_take_all_pages_test() {
+ BEGIN_TEST;
+
+ VmPageList pl;
+ constexpr uint32_t kCount = 3 * VmPageListNode::kPageFanOut;
+ vm_page_t test_pages[VmPageListNode::kPageFanOut] = {};
+ for (uint32_t i = 0; i < kCount; i++) {
+ pl.AddPage(test_pages + i, i * PAGE_SIZE);
+ }
+
+ VmPageSpliceList splice = pl.TakePages(0, kCount * PAGE_SIZE);
+ EXPECT_TRUE(pl.IsEmpty(), "non-empty list\n");
+
+ for (uint32_t i = 0; i < kCount; i++) {
+ EXPECT_EQ(test_pages + i, splice.Pop(), "wrong page\n");
+ }
+ EXPECT_TRUE(splice.IsDone(), "extra pages\n");
+
+ END_TEST;
+}
+
+// Tests taking the middle pages from a range of VmPageListNodes
+static bool vmpl_take_middle_pages_test() {
+ BEGIN_TEST;
+
+ VmPageList pl;
+ constexpr uint32_t kCount = 3 * VmPageListNode::kPageFanOut;
+ vm_page_t test_pages[VmPageListNode::kPageFanOut] = {};
+ for (uint32_t i = 0; i < kCount; i++) {
+ pl.AddPage(test_pages + i, i * PAGE_SIZE);
+ }
+
+ constexpr uint32_t kTakeOffset = VmPageListNode::kPageFanOut - 1;
+ constexpr uint32_t kTakeCount = VmPageListNode::kPageFanOut + 2;
+ VmPageSpliceList splice = pl.TakePages(kTakeOffset * PAGE_SIZE, kTakeCount * PAGE_SIZE);
+ EXPECT_FALSE(pl.IsEmpty(), "non-empty list\n");
+
+ for (uint32_t i = 0; i < kCount; i++) {
+ if (kTakeOffset <= i && i < kTakeOffset + kTakeCount) {
+ EXPECT_EQ(test_pages + i, splice.Pop(), "wrong page\n");
+ } else {
+ vm_page* remove_page;
+ EXPECT_TRUE(pl.RemovePage(i * PAGE_SIZE, &remove_page), "remove failure\n");
+ EXPECT_EQ(test_pages + i, remove_page, "wrong page\n");
+ }
+ }
+ EXPECT_TRUE(splice.IsDone(), "extra pages\n");
+
+ END_TEST;
+}
+
+// Tests that gaps are preserved in the list
+static bool vmpl_take_gap_test() {
+ BEGIN_TEST;
+
+ VmPageList pl;
+ constexpr uint32_t kCount = VmPageListNode::kPageFanOut;
+ constexpr uint32_t kGapSize = 2;
+ vm_page_t test_pages[VmPageListNode::kPageFanOut] = {};
+ for (uint32_t i = 0; i < kCount; i++) {
+ uint64_t offset = (i * (kGapSize + 1)) * PAGE_SIZE;
+ pl.AddPage(test_pages + i, offset);
+ }
+
+ constexpr uint32_t kListStart = PAGE_SIZE;
+ constexpr uint32_t kListLen = (kCount * (kGapSize + 1) - 2) * PAGE_SIZE;
+ VmPageSpliceList splice = pl.TakePages(kListStart, kListLen);
+
+ vm_page* page;
+ EXPECT_TRUE(pl.RemovePage(0, &page), "wrong page\n");
+ EXPECT_EQ(test_pages, page, "wrong page\n");
+ EXPECT_FALSE(pl.RemovePage(kListLen, &page), "wrong page\n");
+
+ for (uint64_t offset = kListStart; offset < kListStart + kListLen; offset += PAGE_SIZE) {
+ auto page_idx = offset / PAGE_SIZE;
+ if (page_idx % (kGapSize + 1) == 0) {
+ EXPECT_EQ(test_pages + (page_idx / (kGapSize + 1)), splice.Pop(), "wrong page\n");
+ } else {
+ EXPECT_NULL(splice.Pop(), "wrong page\n");
+ }
+ }
+ EXPECT_TRUE(splice.IsDone(), "extra pages\n");
+
+ END_TEST;
+}
+
+// Tests that cleaning up a splice list doesn't blow up
+static bool vmpl_take_cleanup_test() {
+ BEGIN_TEST;
+
+ paddr_t pa;
+ vm_page_t* page;
+
+ zx_status_t status = pmm_alloc_page(0, &page, &pa);
+ ASSERT_EQ(ZX_OK, status, "pmm_alloc single page");
+ ASSERT_NONNULL(page, "pmm_alloc single page");
+ ASSERT_NE(0u, pa, "pmm_alloc single page");
+
+ page->state = VM_PAGE_STATE_OBJECT;
+ page->object.pin_count = 0;
+
+ VmPageList pl;
+ pl.AddPage(page, 0);
+
+ VmPageSpliceList splice = pl.TakePages(0, PAGE_SIZE);
+ EXPECT_TRUE(!splice.IsDone(), "missing page\n");
+
+ END_TEST;
+}
+
// Use the function name as the test name
#define VM_UNITTEST(fname) UNITTEST(#fname, fname)
@@ -1079,3 +1253,13 @@
// runs the system out of memory, uncomment for debugging
//VM_UNITTEST(pmm_oversized_alloc_test)
UNITTEST_END_TESTCASE(pmm_tests, "pmm", "Physical memory manager tests");
+
+UNITTEST_START_TESTCASE(vm_page_list_tests)
+VM_UNITTEST(vmpl_add_remove_page_test)
+VM_UNITTEST(vmpl_take_single_page_even_test)
+VM_UNITTEST(vmpl_take_single_page_odd_test)
+VM_UNITTEST(vmpl_take_all_pages_test)
+VM_UNITTEST(vmpl_take_middle_pages_test)
+VM_UNITTEST(vmpl_take_gap_test)
+VM_UNITTEST(vmpl_take_cleanup_test)
+UNITTEST_END_TESTCASE(vm_page_list_tests, "vmpl", "VmPageList tests");
