zircon/kernel/vm/page_source.cpp - fuchsia - Git at Google

 // Copyright 2018 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 <fbl/auto_lock.h>
 #include <kernel/lockdep.h>
 #include <ktl/move.h>
 #include <lib/console.h>
 #include <trace.h>
 #include <vm/page_source.h>

 #define LOCAL_TRACE 0

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

 PageSource::~PageSource() {
     LTRACEF("%p\n", this);
     DEBUG_ASSERT(detached_);
     DEBUG_ASSERT(closed_);
 }

 void PageSource::Detach() {
     canary_.Assert();
     LTRACEF("%p\n", this);
     Guard<fbl::Mutex> guard{&page_source_mtx_};
     if (detached_) {
         return;
     }

     detached_ = true;

     // Cancel read requests (which everything for now)
     while (!outstanding_requests_.is_empty()) {
         auto req = outstanding_requests_.pop_front();
         LTRACEF("dropping request with offset %lx\n", req->offset_);

         // Tell the clients the request is complete - they'll fail when they try
         // asking for the requested pages again after failing to find the pages
         // for this request.
         CompleteRequestLocked(req);
     }
     OnDetach();
 }


 void PageSource::Close() {
     canary_.Assert();
     LTRACEF("%p\n", this);
     // TODO: Close will have more meaning once writeback is implemented
     Detach();

     Guard<fbl::Mutex> guard{&page_source_mtx_};
     if (!closed_) {
         closed_ = true;
         OnClose();
     }
 }

 void PageSource::OnPagesSupplied(uint64_t offset, uint64_t len) {
     canary_.Assert();
     LTRACEF_LEVEL(2, "%p offset %lx, len %lx\n", this, offset, len);
     uint64_t end;
     bool overflow = add_overflow(offset, len, &end);
     DEBUG_ASSERT(!overflow); // vmobject should have already validated overflow

     Guard<fbl::Mutex> guard{&page_source_mtx_};
     if (detached_) {
         return;
     }

     // The first possible request we could fulfill is the one with the smallest
     // end address that is greater than offset. Then keep looking as long as the
     // target request's start offset is less than the supply end.
     auto start = outstanding_requests_.upper_bound(offset);
     while (start.IsValid() && start->offset_ < end) {
         auto cur = start;
         ++start;

         // Calculate how many pages were supplied to this request by finding the start and
         // end offsets of the operation in this request.
         uint64_t req_offset, req_end;
         if (offset >= cur->offset_) {
             // The operation started partway into this request.
             req_offset = offset - cur->offset_;
         } else {
             // The operation started before this request.
             req_offset = 0;
         }
         if (end < cur->GetEnd()) {
             // The operation ended partway into this request.
             req_end = end - cur->offset_;

             uint64_t unused;
             DEBUG_ASSERT(!sub_overflow(end, cur->offset_, &unused));
         } else {
             // The operation ended past the end of this request.
             req_end = cur->len_;
         }

         DEBUG_ASSERT(req_end >= req_offset);
         uint64_t fulfill = req_end - req_offset;

         // If we're not done, continue to the next request
         if (fulfill < cur->pending_size_) {
             cur->pending_size_ -= fulfill;
             continue;
         } else if (fulfill > cur->pending_size_) {
             // This just means that part of the request was decommitted. That's not
             // an error, but it's good to know when we're tracing.
             LTRACEF("%p, excessive page count\n", this);
         }

         LTRACEF_LEVEL(2, "%p, signaling %lx\n", this, cur->offset_);

         // Notify anything waiting on this page
         CompleteRequestLocked(outstanding_requests_.erase(cur));
     }
 }

 zx_status_t PageSource::GetPage(uint64_t offset, PageRequest* request,
                                 vm_page_t** const page_out, paddr_t* const pa_out) {
     canary_.Assert();
     ASSERT(request);
     offset = fbl::round_down(offset, static_cast<uint64_t>(PAGE_SIZE));

     Guard<fbl::Mutex> guard{&page_source_mtx_};
     if (detached_) {
         return ZX_ERR_NOT_FOUND;
     }

     if (GetPage(offset, page_out, pa_out)) {
         return ZX_OK;
     }

     // Check if request is initialized and initialize it if it isn't (it can be initialized
     // for batch requests).
     if (request->offset_ == UINT64_MAX) {
         request->Init(fbl::RefPtr<PageSource>(this), offset);
         LTRACEF_LEVEL(2, "%p offset %lx\n", this, offset);
     }

 #ifdef DEBUG_ASSERT_IMPLEMENTED
     ASSERT(current_request_ == nullptr || current_request_ == request);
     current_request_ = request;
 #endif // DEBUG_ASSERT_IMPLEMENTED

     bool send_request = false;
     zx_status_t res;
     if (request->allow_batching_) {
         // If possible, append the page directly to the current page. Else have the
         // caller try again with a new request.
         if (request->offset_ + request->len_ == offset) {
             request->len_ += PAGE_SIZE;

             // Assert on overflow, since it means vmobject is trying to get out-of-bounds pages.
             uint64_t unused;
             DEBUG_ASSERT(request->len_ >= PAGE_SIZE);
             DEBUG_ASSERT(!add_overflow(request->offset_, request->len_, &unused));

             bool end_batch = false;
             auto node = outstanding_requests_.upper_bound(request->offset_);
             if (node.IsValid()) {
                 uint64_t cur_end = request->offset_ + request->len_;
                 if (node->offset_ <= request->offset_) {
                     // If offset is in [node->GetOffset(), node->GetEnd()), then we end
                     // the batch when we'd stop overlapping.
                     end_batch = node->GetEnd() == cur_end;
                 } else {
                     // If offset is less than node->GetOffset(), then we end the batch
                     // when we'd start overlapping.
                     end_batch = node->offset_ == cur_end;
                 }
             }

             if (end_batch) {
                 send_request = true;
                 res = ZX_ERR_SHOULD_WAIT;
             } else {
                 res = ZX_ERR_NEXT;
             }
         } else {
             send_request = true;
             res = ZX_ERR_SHOULD_WAIT;
         }
     } else {
         request->len_ = PAGE_SIZE;
         send_request = true;
         res = ZX_ERR_SHOULD_WAIT;
     }

     if (send_request) {
         RaiseReadRequestLocked(request);
     }

     return res;
 }

 zx_status_t PageSource::FinalizeRequest(PageRequest* request) {
     LTRACEF_LEVEL(2, "%p\n", this);
     DEBUG_ASSERT(request->offset_ != UINT64_MAX);

     Guard<fbl::Mutex> guard{&page_source_mtx_};
     if (detached_) {
         return ZX_ERR_NOT_FOUND;
     }

     RaiseReadRequestLocked(request);
     return ZX_ERR_SHOULD_WAIT;
 }

 void PageSource::RaiseReadRequestLocked(PageRequest* request) {
     LTRACEF_LEVEL(2, "%p %p\n", this, request);
     // Find the node with the smallest endpoint greater than offset and then
     // check to see if offset falls within that node.
     auto overlap = outstanding_requests_.upper_bound(request->offset_);
     if (overlap.IsValid() && overlap->offset_ <= request->offset_) {
         // GetPage guarantees that if offset lies in an existing node, then it is
         // completely contained in that node.
         overlap->overlap_.push_back(request);
     } else {
         request->pending_size_ = request->len_;

         list_clear_node(&request->read_request_.node);
         request->read_request_.offset = request->offset_;
         request->read_request_.length = request->len_;

         GetPageAsync(&request->read_request_);
         outstanding_requests_.insert(request);
     }
 #ifdef DEBUG_ASSERT_IMPLEMENTED
     current_request_ = nullptr;
 #endif // DEBUG_ASSERT_IMPLEMENTED
 }

 void PageSource::CompleteRequestLocked(PageRequest* req) {
     // Take the request back from the callback before waking
     // up the corresponding thread.
     ClearAsyncRequest(&req->read_request_);

     while (!req->overlap_.is_empty()) {
         auto waiter = req->overlap_.pop_front();
         waiter->offset_ = UINT64_MAX;
         event_signal(&waiter->event_, true);
     }
     req->offset_ = UINT64_MAX;
     event_signal(&req->event_, true);
 }

 void PageSource::CancelRequest(PageRequest* request) {
     canary_.Assert();
     Guard<fbl::Mutex> guard{&page_source_mtx_};
     LTRACEF("%p %lx\n", this, request->offset_);

     if (request->offset_ == UINT64_MAX) {
         return;
     }

     if (static_cast<fbl::DoublyLinkedListable<PageRequest*>*>(request)->InContainer()) {
         LTRACEF("Overlap node\n");
         // This node is overlapping some other node, so just remove the request
         auto main_node = outstanding_requests_.upper_bound(request->offset_);
         ASSERT(main_node.IsValid());
         main_node->overlap_.erase(*request);
     } else if (!request->overlap_.is_empty()) {
         LTRACEF("Outstanding with overlap\n");
         // This node is an outstanding request with overlap, so replace it with the
         // first overlap node.
         auto new_node = request->overlap_.pop_front();

         new_node->overlap_.swap(request->overlap_);
         new_node->offset_ = request->offset_;
         new_node->len_ = request->len_;
         new_node->pending_size_ = request->pending_size_;

         list_clear_node(&new_node->read_request_.node);
         new_node->read_request_.offset = request->offset_;
         new_node->read_request_.length = request->len_;

         outstanding_requests_.erase(*request);
         outstanding_requests_.insert(new_node);

         SwapRequest(&request->read_request_, &new_node->read_request_);
     } else if (static_cast<fbl::WAVLTreeContainable<PageRequest*>*>(request)->InContainer()) {
         LTRACEF("Outstanding no overlap\n");
         // This node is an outstanding request with no overlap
         outstanding_requests_.erase(*request);
         ClearAsyncRequest(&request->read_request_);
     }

     request->offset_ = UINT64_MAX;
 }

 void PageSource::Dump() const {
     Guard<fbl::Mutex> guard{&page_source_mtx_};
     printf("page_source %p detached %d closed %d\n", this, detached_, closed_);
     for (auto& req : outstanding_requests_) {
         printf("  req [%lx, %lx) pending %lx overlap %lu\n",
                req.offset_, req.GetEnd(), req.pending_size_, req.overlap_.size_slow());
     }
 }

 PageRequest::~PageRequest() {
     if (offset_ != UINT64_MAX) {
         src_->CancelRequest(this);
     }
 }

 void PageRequest::Init(fbl::RefPtr<PageSource> src, uint64_t offset) {
     DEBUG_ASSERT(offset_ == UINT64_MAX);
     len_ = 0;
     offset_ = offset;
     src_ = ktl::move(src);
     event_ = EVENT_INITIAL_VALUE(event_, 0, EVENT_FLAG_AUTOUNSIGNAL);
 }

 zx_status_t PageRequest::Wait() {
     zx_status_t status = src_->WaitOnEvent(&event_);
     if (status != ZX_OK) {
         src_->CancelRequest(this);
     }
     return status;
 }

 static int cmd_page_source(int argc, const cmd_args* argv, uint32_t flags) {
     if (argc < 2) {
         printf("not enough arguments\n");
     usage:
         printf("usage:\n");
         printf("%s dump <address>\n", argv[0].str);
         return ZX_ERR_INTERNAL;
     }

     if (!strcmp(argv[1].str, "dump")) {
         reinterpret_cast<PageSource*>(argv[2].u)->Dump();
     } else {
         printf("unknown command\n");
         goto usage;
     }

     return ZX_OK;
 }

 STATIC_COMMAND_START
 #if LK_DEBUGLEVEL > 0
 STATIC_COMMAND("vm_page_source", "page source debug commands", &cmd_page_source)
 #endif
 STATIC_COMMAND_END(ps_object)
	// Copyright 2018 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 <fbl/auto_lock.h>
	#include <kernel/lockdep.h>
	#include <ktl/move.h>
	#include <lib/console.h>
	#include <trace.h>
	#include <vm/page_source.h>

	#define LOCAL_TRACE 0

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

	PageSource::~PageSource() {
	LTRACEF("%p\n", this);
	DEBUG_ASSERT(detached_);
	DEBUG_ASSERT(closed_);
	}

	void PageSource::Detach() {
	canary_.Assert();
	LTRACEF("%p\n", this);
	Guard<fbl::Mutex> guard{&page_source_mtx_};
	if (detached_) {
	return;
	}

	detached_ = true;

	// Cancel read requests (which everything for now)
	while (!outstanding_requests_.is_empty()) {
	auto req = outstanding_requests_.pop_front();
	LTRACEF("dropping request with offset %lx\n", req->offset_);

	// Tell the clients the request is complete - they'll fail when they try
	// asking for the requested pages again after failing to find the pages
	// for this request.
	CompleteRequestLocked(req);
	}
	OnDetach();
	}


	void PageSource::Close() {
	canary_.Assert();
	LTRACEF("%p\n", this);
	// TODO: Close will have more meaning once writeback is implemented
	Detach();

	Guard<fbl::Mutex> guard{&page_source_mtx_};
	if (!closed_) {
	closed_ = true;
	OnClose();
	}
	}

	void PageSource::OnPagesSupplied(uint64_t offset, uint64_t len) {
	canary_.Assert();
	LTRACEF_LEVEL(2, "%p offset %lx, len %lx\n", this, offset, len);
	uint64_t end;
	bool overflow = add_overflow(offset, len, &end);
	DEBUG_ASSERT(!overflow); // vmobject should have already validated overflow

	Guard<fbl::Mutex> guard{&page_source_mtx_};
	if (detached_) {
	return;
	}

	// The first possible request we could fulfill is the one with the smallest
	// end address that is greater than offset. Then keep looking as long as the
	// target request's start offset is less than the supply end.
	auto start = outstanding_requests_.upper_bound(offset);
	while (start.IsValid() && start->offset_ < end) {
	auto cur = start;
	++start;

	// Calculate how many pages were supplied to this request by finding the start and
	// end offsets of the operation in this request.
	uint64_t req_offset, req_end;
	if (offset >= cur->offset_) {
	// The operation started partway into this request.
	req_offset = offset - cur->offset_;
	} else {
	// The operation started before this request.
	req_offset = 0;
	}
	if (end < cur->GetEnd()) {
	// The operation ended partway into this request.
	req_end = end - cur->offset_;

	uint64_t unused;
	DEBUG_ASSERT(!sub_overflow(end, cur->offset_, &unused));
	} else {
	// The operation ended past the end of this request.
	req_end = cur->len_;
	}

	DEBUG_ASSERT(req_end >= req_offset);
	uint64_t fulfill = req_end - req_offset;

	// If we're not done, continue to the next request
	if (fulfill < cur->pending_size_) {
	cur->pending_size_ -= fulfill;
	continue;
	} else if (fulfill > cur->pending_size_) {
	// This just means that part of the request was decommitted. That's not
	// an error, but it's good to know when we're tracing.
	LTRACEF("%p, excessive page count\n", this);
	}

	LTRACEF_LEVEL(2, "%p, signaling %lx\n", this, cur->offset_);

	// Notify anything waiting on this page
	CompleteRequestLocked(outstanding_requests_.erase(cur));
	}
	}

	zx_status_t PageSource::GetPage(uint64_t offset, PageRequest* request,
	vm_page_t** const page_out, paddr_t* const pa_out) {
	canary_.Assert();
	ASSERT(request);
	offset = fbl::round_down(offset, static_cast<uint64_t>(PAGE_SIZE));

	Guard<fbl::Mutex> guard{&page_source_mtx_};
	if (detached_) {
	return ZX_ERR_NOT_FOUND;
	}

	if (GetPage(offset, page_out, pa_out)) {
	return ZX_OK;
	}

	// Check if request is initialized and initialize it if it isn't (it can be initialized
	// for batch requests).
	if (request->offset_ == UINT64_MAX) {
	request->Init(fbl::RefPtr<PageSource>(this), offset);
	LTRACEF_LEVEL(2, "%p offset %lx\n", this, offset);
	}

	#ifdef DEBUG_ASSERT_IMPLEMENTED
	ASSERT(current_request_ == nullptr \|\| current_request_ == request);
	current_request_ = request;
	#endif // DEBUG_ASSERT_IMPLEMENTED

	bool send_request = false;
	zx_status_t res;
	if (request->allow_batching_) {
	// If possible, append the page directly to the current page. Else have the
	// caller try again with a new request.
	if (request->offset_ + request->len_ == offset) {
	request->len_ += PAGE_SIZE;

	// Assert on overflow, since it means vmobject is trying to get out-of-bounds pages.
	uint64_t unused;
	DEBUG_ASSERT(request->len_ >= PAGE_SIZE);
	DEBUG_ASSERT(!add_overflow(request->offset_, request->len_, &unused));

	bool end_batch = false;
	auto node = outstanding_requests_.upper_bound(request->offset_);
	if (node.IsValid()) {
	uint64_t cur_end = request->offset_ + request->len_;
	if (node->offset_ <= request->offset_) {
	// If offset is in [node->GetOffset(), node->GetEnd()), then we end
	// the batch when we'd stop overlapping.
	end_batch = node->GetEnd() == cur_end;
	} else {
	// If offset is less than node->GetOffset(), then we end the batch
	// when we'd start overlapping.
	end_batch = node->offset_ == cur_end;
	}
	}

	if (end_batch) {
	send_request = true;
	res = ZX_ERR_SHOULD_WAIT;
	} else {
	res = ZX_ERR_NEXT;
	}
	} else {
	send_request = true;
	res = ZX_ERR_SHOULD_WAIT;
	}
	} else {
	request->len_ = PAGE_SIZE;
	send_request = true;
	res = ZX_ERR_SHOULD_WAIT;
	}

	if (send_request) {
	RaiseReadRequestLocked(request);
	}

	return res;
	}

	zx_status_t PageSource::FinalizeRequest(PageRequest* request) {
	LTRACEF_LEVEL(2, "%p\n", this);
	DEBUG_ASSERT(request->offset_ != UINT64_MAX);

	Guard<fbl::Mutex> guard{&page_source_mtx_};
	if (detached_) {
	return ZX_ERR_NOT_FOUND;
	}

	RaiseReadRequestLocked(request);
	return ZX_ERR_SHOULD_WAIT;
	}

	void PageSource::RaiseReadRequestLocked(PageRequest* request) {
	LTRACEF_LEVEL(2, "%p %p\n", this, request);
	// Find the node with the smallest endpoint greater than offset and then
	// check to see if offset falls within that node.
	auto overlap = outstanding_requests_.upper_bound(request->offset_);
	if (overlap.IsValid() && overlap->offset_ <= request->offset_) {
	// GetPage guarantees that if offset lies in an existing node, then it is
	// completely contained in that node.
	overlap->overlap_.push_back(request);
	} else {
	request->pending_size_ = request->len_;

	list_clear_node(&request->read_request_.node);
	request->read_request_.offset = request->offset_;
	request->read_request_.length = request->len_;

	GetPageAsync(&request->read_request_);
	outstanding_requests_.insert(request);
	}
	#ifdef DEBUG_ASSERT_IMPLEMENTED
	current_request_ = nullptr;
	#endif // DEBUG_ASSERT_IMPLEMENTED
	}

	void PageSource::CompleteRequestLocked(PageRequest* req) {
	// Take the request back from the callback before waking
	// up the corresponding thread.
	ClearAsyncRequest(&req->read_request_);

	while (!req->overlap_.is_empty()) {
	auto waiter = req->overlap_.pop_front();
	waiter->offset_ = UINT64_MAX;
	event_signal(&waiter->event_, true);
	}
	req->offset_ = UINT64_MAX;
	event_signal(&req->event_, true);
	}

	void PageSource::CancelRequest(PageRequest* request) {
	canary_.Assert();
	Guard<fbl::Mutex> guard{&page_source_mtx_};
	LTRACEF("%p %lx\n", this, request->offset_);

	if (request->offset_ == UINT64_MAX) {
	return;
	}

	if (static_cast<fbl::DoublyLinkedListable<PageRequest>>(request)->InContainer()) {
	LTRACEF("Overlap node\n");
	// This node is overlapping some other node, so just remove the request
	auto main_node = outstanding_requests_.upper_bound(request->offset_);
	ASSERT(main_node.IsValid());
	main_node->overlap_.erase(*request);
	} else if (!request->overlap_.is_empty()) {
	LTRACEF("Outstanding with overlap\n");
	// This node is an outstanding request with overlap, so replace it with the
	// first overlap node.
	auto new_node = request->overlap_.pop_front();

	new_node->overlap_.swap(request->overlap_);
	new_node->offset_ = request->offset_;
	new_node->len_ = request->len_;
	new_node->pending_size_ = request->pending_size_;

	list_clear_node(&new_node->read_request_.node);
	new_node->read_request_.offset = request->offset_;
	new_node->read_request_.length = request->len_;

	outstanding_requests_.erase(*request);
	outstanding_requests_.insert(new_node);

	SwapRequest(&request->read_request_, &new_node->read_request_);
	} else if (static_cast<fbl::WAVLTreeContainable<PageRequest>>(request)->InContainer()) {
	LTRACEF("Outstanding no overlap\n");
	// This node is an outstanding request with no overlap
	outstanding_requests_.erase(*request);
	ClearAsyncRequest(&request->read_request_);
	}

	request->offset_ = UINT64_MAX;
	}

	void PageSource::Dump() const {
	Guard<fbl::Mutex> guard{&page_source_mtx_};
	printf("page_source %p detached %d closed %d\n", this, detached_, closed_);
	for (auto& req : outstanding_requests_) {
	printf(" req [%lx, %lx) pending %lx overlap %lu\n",
	req.offset_, req.GetEnd(), req.pending_size_, req.overlap_.size_slow());
	}
	}

	PageRequest::~PageRequest() {
	if (offset_ != UINT64_MAX) {
	src_->CancelRequest(this);
	}
	}

	void PageRequest::Init(fbl::RefPtr<PageSource> src, uint64_t offset) {
	DEBUG_ASSERT(offset_ == UINT64_MAX);
	len_ = 0;
	offset_ = offset;
	src_ = ktl::move(src);
	event_ = EVENT_INITIAL_VALUE(event_, 0, EVENT_FLAG_AUTOUNSIGNAL);
	}

	zx_status_t PageRequest::Wait() {
	zx_status_t status = src_->WaitOnEvent(&event_);
	if (status != ZX_OK) {
	src_->CancelRequest(this);
	}
	return status;
	}

	static int cmd_page_source(int argc, const cmd_args* argv, uint32_t flags) {
	if (argc < 2) {
	printf("not enough arguments\n");
	usage:
	printf("usage:\n");
	printf("%s dump <address>\n", argv[0].str);
	return ZX_ERR_INTERNAL;
	}

	if (!strcmp(argv[1].str, "dump")) {
	reinterpret_cast<PageSource*>(argv[2].u)->Dump();
	} else {
	printf("unknown command\n");
	goto usage;
	}

	return ZX_OK;
	}

	STATIC_COMMAND_START
	#if LK_DEBUGLEVEL > 0
	STATIC_COMMAND("vm_page_source", "page source debug commands", &cmd_page_source)
	#endif
	STATIC_COMMAND_END(ps_object)