kernel/vm/include/vm/page_source.h

// 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

#pragma once

#include <fbl/intrusive_double_list.h>
#include <fbl/intrusive_wavl_tree.h>
#include <fbl/mutex.h>
#include <fbl/ref_counted.h>
#include <fbl/ref_ptr.h>
#include <kernel/event.h>
#include <kernel/lockdep.h>
#include <kernel/mutex.h>
#include <vm/page.h>
#include <vm/vm.h>
#include <zircon/types.h>

// A page source has two parts - the PageSource and the PageSourceCallback. The
// PageSource is responsible for generic functionality, mostly around managing
// the lifecycle of page requests. The PageSourceCallback is responsible for
// actually providing the pages.
//
// The synchronous fulfillment of requests is fairly straightforward, with
// direct calls from the vm object to the PageSource to the PageSourceCallback.
//
// For asynchronous requests, the lifecycle is as follows:
//   1) A vm object requests a page with PageSource::GetPage
//   2) PageSource starts tracking the request's PageRequest and then
//      forwards the request to PageSourceCallback::GetPageAsync.
//   3) The caller waits for the request with PageRequest::Wait
//   4) At some point, whatever is backing the callback provides pages
//      to the vm object (e.g. with VmObjectPaged::SupplyPages).
//   5) The vm object calls PageSource::OnPagesSupplied, which signals
//      any PageRequests that have been fulfilled.
//   6) The caller wakes up and queries the vm object again, by which
//      point the request page will be present.

class PageRequest;

// A simple page_request struct for use by the PageSourceCallback implementation.
typedef struct page_request {
    list_node_t node;
    uint64_t offset;
    uint64_t length;
} page_request_t;

// Object which provides pages to a vm_object.
class PageSource : public fbl::RefCounted<PageSource> {
public:
    PageSource();
    virtual ~PageSource();

    // Sends a request to the backing source to provide the requested page.
    //
    // Returns ZX_OK if the request was synchronously fulfilled.
    // Returns ZX_ERR_SHOULD_WAIT if the request will be asynchronously
    // fulfilled. The caller should wait on |req|.
    // Returns ZX_ERR_NEXT if the PageRequest is in batch mode and the caller
    // can continue to add more pages to the request.
    // Returns ZX_ERR_NOT_FOUND if the request cannot be fulfilled.
    zx_status_t GetPage(uint64_t offset, PageRequest* req,
                        vm_page_t** const page_out, paddr_t* const pa_out);

    // Called to complete a batched PageRequest if the last call to GetPage
    // returned ZX_ERR_NEXT.
    //
    // Returns ZX_ERR_SHOULD_WAIT if the PageRequest will be fulfilled after
    // being waited upon.
    // Returns ZX_ERR_NOT_FOUND if the request will never be resolved.
    zx_status_t FinalizeRequest(PageRequest* node);

    // Updates the request tracking metadata to account for pages [offset, len) having
    // been supplied to the owning vmo.
    void OnPagesSupplied(uint64_t offset, uint64_t len);

    // Detaches the source. All future calls into the page source will fail. All
    // pending read transactions are aborted. Pending flush transactions will still
    // be serviced.
    void Detach();

    // Closes the source. All pending transactions will be aborted and all future
    // calls will fail.
    void Close();

protected:
    // Synchronously gets a page from the backing source.
    virtual bool GetPage(uint64_t offset,
                         vm_page_t** const page_out, paddr_t* const pa_out) = 0;
    // Informs the backing source of a page request. The callback has ownership
    // of |request| until the async request is cancelled.
    virtual void GetPageAsync(page_request_t* request) = 0;
    // Informs the backing source that a page request has been fulfilled. This
    // must be called for all requests that are raised.
    virtual void ClearAsyncRequest(page_request_t* request) = 0;
    // Swaps the backing memory for a request. Assumes that |old|
    // and |new_request| have the same type, offset, and length.
    virtual void SwapRequest(page_request_t* old, page_request_t* new_req) = 0;

    // OnDetach is called once no more calls to GetPage/GetPageAsync will be made. It
    // will be called before OnClose and will only be called once.
    virtual void OnDetach() = 0;
    // After OnClose is called, no more calls will be made except for ::WaitOnEvent.
    virtual void OnClose() = 0;

    virtual zx_status_t WaitOnEvent(event_t* event) = 0;

private:
    fbl::Canary<fbl::magic("VMPS")> canary_;

    mutable DECLARE_MUTEX(PageSource) page_source_mtx_;
    bool detached_ TA_GUARDED(page_source_mtx_) = false;
    bool closed_ TA_GUARDED(page_source_mtx_) = false;

    // Tree of pending_request structs which have been sent to the callback. The list
    // is keyed by the end offset of the requests (not the start offsets).
    fbl::WAVLTree<uint64_t, PageRequest*> outstanding_requests_ TA_GUARDED(page_source_mtx_);

#ifdef DEBUG_ASSERT_IMPLEMENTED
    // Tracks the request currently being processed (only used for verifying batching assertions).
    PageRequest* current_request_ TA_GUARDED(page_source_mtx_) = nullptr;
#endif // DEBUG_ASSERT_IMPLEMENTED

    // Sends a read request to the backing source, or queues the request if the needed
    // region has already been requested from the source.
    void RaiseReadRequestLocked(PageRequest* request) TA_REQ(page_source_mtx_);

    // Wakes up the given PageRequest and all overlapping requests.
    void CompleteRequestLocked(PageRequest* head) TA_REQ(page_source_mtx_);

    // Removes |request| from any internal tracking. Called by a PageRequest if
    // it needs to abort itself.
    void CancelRequest(PageRequest* request) TA_EXCL(page_source_mtx_);

    friend PageRequest;
};

// Object which is used to make delayed page requests to a PageSource
class PageRequest : public fbl::WAVLTreeContainable<PageRequest*>,
                    public fbl::DoublyLinkedListable<PageRequest*> {
public:
    // If |allow_batching| is true, then a single request can be used to service
    // multiple consecutive pages.
    explicit PageRequest(bool allow_batching = false)
        : allow_batching_(allow_batching) {}
    ~PageRequest();

    // Returns ZX_OK on success or ZX_ERR_INTERNAL_INTR_KILLED if the thread was killed.
    zx_status_t Wait();

    DISALLOW_COPY_ASSIGN_AND_MOVE(PageRequest);

private:
    // PageRequests passed to GetPage may or may not be initialized. offset_ must be checked
    // and the object must be initalized if necessary.
    void Init(fbl::RefPtr<PageSource> src, uint64_t offset);

    const bool allow_batching_;

    // The page source this request is currently associated with.
    fbl::RefPtr<PageSource> src_;
    // Event signaled when the request is fulfilled.
    event_t event_;
    // PageRequests are active if offset_ is not UINT64_MAX. In an inactive request, the
    // only other valid field is src_.
    uint64_t offset_ = UINT64_MAX;
    // The total length of the request.
    uint64_t len_ = 0;

    // Keeps track of the size of the request that still needs to be fulfilled. This
    // can become incorrect if some pages get supplied, decommitted, and then
    // re-supplied. If that happens, then it will cause the page request to complete
    // prematurely. However, page source clients should be operating in a loop to handle
    // evictions, so this will simply result in some redundant read requests to the
    // page source. Given the rarity in which this situation should arise, it's not
    // worth the complexity of tracking it.
    uint64_t pending_size_ = 0;

    // List node for overlapping requests.
    fbl::DoublyLinkedList<PageRequest*> overlap_;

    // Request struct for the PageSourceCallback
    page_request_t read_request_;

    uint64_t GetEnd() const {
        // Assert on overflow, since it means vmobject made an out-of-bounds request.
        uint64_t unused;
        DEBUG_ASSERT(!add_overflow(offset_, len_, &unused));

        return offset_ + len_;
    }

    uint64_t GetKey() const { return GetEnd(); }

    friend PageSource;
    friend fbl::DefaultKeyedObjectTraits<uint64_t, PageRequest>;
};