// 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_VM_ADDRESS_REGION_ENUMERATOR_H_
#define ZIRCON_KERNEL_VM_INCLUDE_VM_VM_ADDRESS_REGION_ENUMERATOR_H_

#include <assert.h>
#include <stdint.h>
#include <zircon/types.h>

#include <ktl/optional.h>
#include <ktl/type_traits.h>
#include <vm/vm_address_region.h>

enum class VmAddressRegionEnumeratorType : bool {
  // If the enumeration will never be paused then both regions and mappings can be yielded.
  UnpausableVmarOrMapping = false,
  // If the enumeration supports pausing then only mappings will be yielded. This is necessary to
  // ensure forward progress.
  PausableMapping = true,
};

// Helper class for performing enumeration of a VMAR. The enumeration type is a template to help
// statically prevent misuse and enforce unique return types. Although this is intended to be
// internal, it is declared here for exposing to unit tests.
//
// The purpose of having a stateful enumerator is to have the option to not need to hold the aspace
// lock over the entire enumeration, whilst guaranteeing forward progress and termination. If the
// vmar is modified whilst enumeration is paused (due to dropping the lock or otherwise) then it is
// not well defined whether the enumerator will return any new mappings. However, the enumerator
// will never return DEAD mappings, and will not return mappings in ranges it has already
// enumerated.
//
// Except between calls to |pause| and |resume|, the vmar should be considered immutable, and
// sub-vmars and mappings should not be modified.
template <VmAddressRegionEnumeratorType Type>
class VmAddressRegionEnumerator {
 public:
  // This requires the vmar lock to be held over the lifetime of the object, except where explicitly
  // stated otherwise.
  VmAddressRegionEnumerator(VmAddressRegion& vmar, vaddr_t min_addr, vaddr_t max_addr)
      TA_REQ(vmar.lock())
      : min_addr_(min_addr),
        max_addr_(max_addr),
        vmar_(vmar),
        itr_(vmar_.subregions_.IncludeOrHigher(min_addr_)) {}

  struct NextResult {
    using RegionOrMapping =
        ktl::conditional_t<Type == VmAddressRegionEnumeratorType::PausableMapping, VmMapping,
                           VmAddressRegionOrMapping>;
    RegionOrMapping* region_or_mapping;
    uint depth;
  };

  // Yield the next region or mapping, or a nullopt if enumeration has completed. Regions are
  // yielded in depth-first pre-order. The regions are yielded as raw pointers, which are guaranteed
  // to be valid since the lock is held. It is the callers responsibility to keep these pointers
  // alive, by upgrading to RefPtrs or otherwise, if they want to |pause| and drop the lock.
  ktl::optional<NextResult> next() TA_REQ(vmar_.lock()) {
    if constexpr (Type == VmAddressRegionEnumeratorType::PausableMapping) {
      ASSERT(!state_.paused_);
    }
    ktl::optional<NextResult> ret = ktl::nullopt;
    while (!ret && itr_.IsValid() && itr_->base() < max_addr_) {
      auto curr = itr_++;
      AssertHeld(curr->lock_ref());
      DEBUG_ASSERT(curr->IsAliveLocked());
      VmAddressRegion* up = curr->parent_;

      if (curr->is_mapping()) {
        VmMapping* mapping = curr->as_vm_mapping().get();

        DEBUG_ASSERT(mapping != nullptr);
        AssertHeld(mapping->lock_ref());
        // If the mapping is entirely before |min_addr| or entirely after |max_addr| do not run
        // on_mapping. This can happen when a vmar contains min_addr but has mappings entirely
        // below it, for example.
        if ((mapping->base() < min_addr_ && mapping->base() + mapping->size() <= min_addr_) ||
            mapping->base() > max_addr_) {
          continue;
        }
        ret = NextResult{mapping, depth_};
      } else {
        VmAddressRegion* vmar = curr->as_vm_address_region().get();
        DEBUG_ASSERT(vmar != nullptr);
        AssertHeld(vmar->lock_ref());
        if constexpr (Type == VmAddressRegionEnumeratorType::UnpausableVmarOrMapping) {
          ret = NextResult{vmar, depth_};
        }
        if (!vmar->subregions_.IsEmpty()) {
          // If the sub-VMAR is not empty, iterate through its children.
          itr_ = vmar->subregions_.begin();
          depth_++;
          continue;
        }
      }
      if (depth_ > kStartDepth && !itr_.IsValid()) {
        AssertHeld(up->lock_ref());
        // If we are at a depth greater than the minimum, and have reached
        // the end of a sub-VMAR range, we ascend and continue iteration.
        do {
          itr_ = up->subregions_.UpperBound(curr->base());
          if (itr_.IsValid()) {
            break;
          }
          up = up->parent_;
        } while (depth_-- != kStartDepth);
        if (!itr_.IsValid()) {
          // If we have reached the end after ascending all the way up,
          // break out of the loop.
          break;
        }
      }
    }
    return ret;
  }

  // Pause enumeration. Until |resume| is called |next| may not be called, but the vmar lock is
  // permitted to be dropped, and the vmar is permitted to be modified.
  void pause() TA_REQ(vmar_.lock()) {
    static_assert(Type == VmAddressRegionEnumeratorType::PausableMapping);
    ASSERT(!state_.paused_);
    // Save information of the next iteration we should return.
    if (itr_.IsValid()) {
      // Per comment on |itr_|, we could be at a VmAddressRegion or a VmMapping. However, a
      // VmAddressRegion (or a VmMapping with a base below min_addr_) is only possible if we have
      // just constructed the enumerator, or just called |resume| (without calling |next|). We do
      // not track specifically if we have called |next| or not, but we do know that if depth_ is
      // not kStartDepth, then |next| must have been called. Using the depth_ heuristic we have at
      // least a chance of detecting incorrect enumerations with the following assert.
      DEBUG_ASSERT((itr_->is_mapping() && itr_->base() >= min_addr_) || depth_ == kStartDepth);
      // Is possible that the object extends only partially into our enumeration range. As such we
      // cannot just record its base() as the point to resume iteration, but need to clip it with
      // |min_addr_| to ensure we do not iterate backwards or outside of our requested range.
      state_.next_offset_ = ktl::max(min_addr_, itr_->base());
      state_.region_or_mapping_ = itr_.CopyPointer();
    } else {
      state_.next_offset_ = max_addr_;
      state_.region_or_mapping_ = nullptr;
    }
    state_.paused_ = true;
  }

  // Resume enumeration allowing |next| to be called again.
  void resume() TA_REQ(vmar_.lock()) {
    static_assert(Type == VmAddressRegionEnumeratorType::PausableMapping);
    ASSERT(state_.paused_);
    if (state_.region_or_mapping_) {
      AssertHeld(itr_->lock_ref());
      if (!itr_->IsAliveLocked()) {
        // Generate a new iterator that starts at the right offset, but back at the top. The next
        // call to next() will walk back down if necessary to find a mapping.
        min_addr_ = state_.next_offset_;
        itr_ = vmar_.subregions_.IncludeOrHigher(min_addr_);
        depth_ = kStartDepth;
      } else {
        DEBUG_ASSERT(&*itr_ == &*state_.region_or_mapping_);
      }
      // Free the refptr. Note that the actual destructors of VmAddressRegionOrMapping objects
      // themselves do very little, so we are safe to potential invoke the destructor here.
      state_.region_or_mapping_.reset();
    } else {
      // There was no refptr, meaning itr_ was already not valid, and should still not be valid.
      ASSERT(!itr_.IsValid());
    }
    state_.paused_ = false;
  }

  // Expose our backing lock for annotation purposes.
  Lock<Mutex>& lock_ref() const TA_RET_CAP(vmar_.lock_ref()) { return vmar_.lock_ref(); }

 private:
  struct PauseState {
    bool paused_ = false;
    vaddr_t next_offset_ = 0;
    fbl::RefPtr<VmAddressRegionOrMapping> region_or_mapping_;
  };
  struct NoPauseState {};

  using StateType = ktl::conditional_t<Type == VmAddressRegionEnumeratorType::PausableMapping,
                                       PauseState, NoPauseState>;
  StateType state_;
  vaddr_t min_addr_;
  const vaddr_t max_addr_;
  static constexpr uint kStartDepth = 1;
  uint depth_ = kStartDepth;
  // Root vmar being enumerated.
  VmAddressRegion& vmar_;
  // This iterator represents the object at which |next| should use to find the next item to return.
  // Regardless of the kind of enumerator this might be a reference to either a VmAddressRegion or
  // a VmMapping. Although PausableMapping only yields VmMappings, it may still need to have its
  // itr_ point to a VmAddressRegion at the point of construction, or after a |resume|.
  // An invalid itr_ therefore represents no next object, and means enumeration has finished.
  RegionList<VmAddressRegionOrMapping>::ChildList::iterator itr_;
};

#endif  // ZIRCON_KERNEL_VM_INCLUDE_VM_VM_ADDRESS_REGION_ENUMERATOR_H_