// Copyright 2022 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_COMPRESSOR_H_
#define ZIRCON_KERNEL_VM_INCLUDE_VM_COMPRESSOR_H_

#include <ktl/optional.h>
#include <ktl/variant.h>
#include <vm/vm_page_list.h>

class VmCompression;

// The VmCompressor represents a single instance of a compression operation that can be performed
// with a minimal locking protocol between a VMO page owner, and the compressor. There are two
// different actors that may access and interact with the compressor:
//  1. The owner of the VmCompressor instance.
//  2. The holder of the lock to the VMO that owns the temporary reference from this VmCompressor.
//
// The temporary reference exists to allow for the, hopefully unlikely, scenario where another
// thread wants access to the page whilst compression is in progress, and it works as follows:
//
//  * With the VMO lock held, a vm_page_t in a page list is replaced with the temporary reference
//     of the VmCompressor.
//
// At this point the VmCompressor owns the vm_page_t, but the VMO owns the temporary reference. From
// here any reference to a VMO or the VMO lock refers to the owner of the temporary reference.
//
//  * With the VMO lock *not* held the data in the page is compressed resulting in success or
//   failure.
//
// During this process the VMO lock was not held, allowing another thread to lookup this page and
// find the temporary reference. If the temporary reference is found it can treat it like any other
// compressed reference and decompress it. Decompression of the temporary reference does not have
// to synchronize on the compression attempt, rather it can just copy page (since the compressor
// does not modify it).
//
// Decompression is free to read the page, knowing it cannot be changed, due to holding the VMO
// lock. This is because for the original thread to progress after performing the compress step it
// must.
//
//  * Acquire the VMO lock, see if the temporary reference is still there, and resolve any success
//    or failure of the compression.
//
// In this case if the temporary reference is still there then it is replaced with the compression
// result (either a compress reference if it succeed, or the original page again if it failed).
//
// As we are holding the VMO lock we know that either the temporary reference is there, and we hold
// the lock, so no one else can be using it, or the temporary reference is not there and so it must
// have been returned, and so no on else can be using it. Therefore the compressor can be reset.
//
// In order to know that the temporary reference is no longer in use we require that it not move
// between slots in the page list (or between different page lists). This represents the one time
// where a compressed reference must be eagerly decompressed even if the data is not being accessed.
//
//
// This process of using a temporary reference that can resolve to performing a parallel copy
// provides some important properties:
//  1. Requesting a page blocks either on decompression, or a memcpy, but never compression.
//  2. Compression is performed on an owned page, and not on a page still in the VmPageList,
//     ensuring that the compression algorithm does not have to tolerate mutations during
//     compression.
class VmCompressor {
 public:
  ~VmCompressor();
  using CompressedRef = VmPageOrMarker::ReferenceValue;

  struct FailTag {};
  struct ZeroTag {};
  using CompressResult = ktl::variant<CompressedRef, ZeroTag, FailTag>;

  // Arms the compressor, ensuring the backup page is allocated. This must be called prior to
  // |Start|.
  zx_status_t Arm();

  // Start the compression process. Gives ownership of the page to the compressor, and returns the
  // temporary compression reference that should be installed in the page list in its place.
  // |Arm| must be called prior to calling |Start|.
  CompressedRef Start(vm_page_t* page);

  // Perform compression. |Start| must have been called prior, and this may be called without any
  // other locks held.
  // See VmCompression::Compress for an explanation of the |CompressResult| type.
  CompressResult Compress();

  // Indicates that the temporary reference is no longer in use, and the compressor is now able to
  // be re-armed.
  void Finalize();

  // Convenience method to free unused compressed references returned from |Compress|. A reference
  // from |Compress| might be unused if, after reacquiring locks, a race has occurred and the
  // compression result is stale.
  void Free(CompressedRef ref);

  // Return the temporary reference, indicating it is no longer in use.
  void ReturnTempReference(CompressedRef ref);

  // Returns whether there is an active compression attempt in progress or not.
  bool IsIdle() const { return state_ == State::Ready || state_ == State::Finalized; }

  // Tests whether the supplied reference is the temporary reference from this compressor.
  bool IsTempReference(CompressedRef ref) const { return ref.value() == temp_reference_; }

  // Returns whether the temporary reference is currently in use or not. This is different IsIdle,
  // as compression could be in progress, but the temporary reference already returned due to a
  // race.
  //
  // Calling this has the same locking requirements as the |spare_page_| member, whether either the
  // compressor needs to be idle, or the VMO lock must be held.
  bool IsTempReferenceInUse() const { return using_temp_reference_; }

 private:
  // Let the compression system be a friend to call the constructor.
  friend VmCompression;
  VmCompressor(VmCompression& compressor, uint64_t temp_ref)
      : compressor_(compressor), temp_reference_(temp_ref) {}

  // Reference to the owning compression system.
  VmCompression& compressor_;
  // The value given to us that represent our temporary reference to hand out.
  const uint64_t temp_reference_;

  enum class State {
    // The compressor has been armed and is ready to start compression. The temporary reference has
    // not been given out, and all fields may be mutated.
    Ready,
    // The temporary reference has been given out and page_ is non-null. using_temp_reference_ and
    // spare_page_ will only read/written from the VmCompression coordinator at request of someone
    // who holds the VMO lock.
    Started,
    // Using temp_reference_ and spare_page_ may be read/written via VmCompression, similar to the
    // Started state, and also by us, provided we hold the VMO lock.
    Compressed,
    // Compression has completed, no fields are valid, and needs to be re-armed.
    Finalized,
  };
  // Begin in the Finalized state to require Arm to be called initially.
  State state_ = State::Finalized;

  // Has no load bearing functionality and is only used for assertion checking. Ownership
  // permissions are the same as for spare_page.
  bool using_temp_reference_ = false;

  // The page we are compressing, owned by us.
  // In the Started and Compressed states this field, and the underlying data it points to, are
  // read-only.
  vm_page_t* page_ = nullptr;

  // In the unlikely event that the temporary reference needs to be turned back into a page we may
  // not be able to perform an allocation. Therefore a spare page is kept around that we can copy
  // to. As there is only one temporary reference, only one page is needed, and is refreshed in the
  // Arm step.
  // In the Started and Compressed states this field is wholly owned, for reads and writes, by the
  // holder of the VMO lock.
  vm_page_t* spare_page_ = nullptr;
};

#endif  // ZIRCON_KERNEL_VM_INCLUDE_VM_COMPRESSOR_H_