zircon/kernel/phys/lib/memalloc/algorithm.cc

// Copyright 2021 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 "algorithm.h"

#include <lib/fitx/result.h>
#include <lib/memalloc/range.h>
#include <lib/stdcompat/span.h>
#include <zircon/assert.h>

#include <algorithm>
#include <array>
#include <limits>

namespace memalloc {

constexpr uint64_t kMax = std::numeric_limits<uint64_t>::max();

namespace {

constexpr uint64_t GetLeft(const Range& range) { return range.addr; }

constexpr uint64_t GetRight(const Range& range) {
  return GetLeft(range) + std::min(kMax - GetLeft(range), range.size);
}

// Represents a 64-bit, unsigned integral interval, [Left(), Right()), whose
// inclusive endpoints may may range from 0 to UINT64_MAX -1.
//
// For arithmetic and overflow safety convenience, we take the right endpoint
// be exclusive, which is what disallows UINT64_MAX from being an endpoint.
// Though this limitation is unfortunate, it is not an issue in practice, as
// this type is used to represent a range of the physical address space and
// supported architectures in turn do not support addresses that high.
//
// The "empty" interval is represented as the only Interval with Left() ==
// Right(), which, by convention is taken to be rooted at 0.
class Interval {
 public:
  // Gives the empty interval.
  constexpr Interval() = default;

  // Gives the interval [left, right) when left < right, and the empty interval
  // otherwise.
  constexpr Interval(uint64_t left, uint64_t right)
      : left_(left >= right ? 0 : left), right_(left >= right ? 0 : right) {}

  constexpr Interval(const Range& range) : Interval(GetLeft(range), GetRight(range)) {}

  constexpr bool empty() const { return Left() == Right(); }

  constexpr uint64_t Left() const { return left_; }

  constexpr uint64_t Right() const { return right_; }

  constexpr bool IsAdjacentTo(Interval other) const {
    return Left() == other.Right() || other.Left() == Right();
  }

  constexpr bool IntersectsWith(Interval other) const {
    return !empty() && !other.empty() && Left() < other.Right() && Right() > other.Left();
  }

  // Returns the subrange before the intersection with another interval.
  constexpr Interval HeadBeforeIntersection(Interval other) const {
    ZX_DEBUG_ASSERT(IntersectsWith(other));
    return {Left(), std::max(Left(), other.Left())};
  }

  // Returns the subrange after the intersection with another interval.
  constexpr Interval TailAfterIntersection(Interval other) const {
    ZX_DEBUG_ASSERT(IntersectsWith(other));
    return {std::min(Right(), other.Right()), Right()};
  }

  constexpr void MergeInto(Interval other) {
    ZX_DEBUG_ASSERT((empty() || other.empty()) || IntersectsWith(other) || IsAdjacentTo(other));
    if (other.empty()) {
      return;
    }
    left_ = empty() ? other.left_ : std::min(Left(), other.Left());
    right_ = empty() ? other.right_ : std::max(Right(), other.Right());
  }

  constexpr Range AsRamRange() const {
    return {.addr = Left(), .size = Right() - Left(), .type = Type::kFreeRam};
  }

 private:
  uint64_t left_ = 0;
  uint64_t right_ = 0;
};

enum class EndpointType { kLeft, kRight };

struct Endpoint {
  const Range* range;
  EndpointType type;

  constexpr bool IsLeft() const { return type == EndpointType::kLeft; }

  constexpr uint64_t value() const {
    ZX_DEBUG_ASSERT(range);
    return IsLeft() ? GetLeft(*range) : GetRight(*range);
  }

  // Compares by value, giving left endpoints precedence.
  constexpr bool operator<(Endpoint other) const {
    return value() < other.value() || (value() == other.value() && IsLeft() && !other.IsLeft());
  }
};

// An array of counters indexed by Type.
class ActiveRanges {
 public:
  size_t& operator[](Type type) {
    uint64_t type_val = static_cast<uint64_t>(type);
    switch (type_val) {
      case ZBI_MEM_RANGE_RAM:
        return values_[0];
      case ZBI_MEM_RANGE_PERIPHERAL:
        return values_[1];
      case ZBI_MEM_RANGE_RESERVED:
        return values_[2];
      case kMinExtendedTypeValue ... kMaxExtendedTypeValue - 1:
        static_assert(kNumBaseTypes == 3);
        return values_[kNumBaseTypes + static_cast<size_t>(type_val - kMinExtendedTypeValue)];
    }
    // Normalize to kReserved if unknown.
    return (*this)[Type::kReserved];
  }

  // Gives the active range type with the highest relative precedence,
  // std::nullopt if there are no active ranges, or fitx::failed if
  // * two different extended types are active
  // * both an extended type and one of kReserved or kPeripheral are active.
  fitx::result<fitx::failed, std::optional<Type>> DominantType() {
    // First look through the base types in reverse-order of precedence (so
    // "last wins").
    std::optional<Type> active_base;
    for (Type type : {Type::kFreeRam, Type::kPeripheral, Type::kReserved}) {
      if ((*this)[type] > 0) {
        active_base = type;
      }
    }

    std::optional<Type> active_extended;
    for (uint64_t i = kMinExtendedTypeValue; i < kMaxExtendedTypeValue; ++i) {
      Type type = static_cast<Type>(i);
      if ((*this)[type] > 0) {
        // If there is a non-kFreeRam base type or another extended type
        // active, that's an error.
        if ((active_base && *active_base != Type::kFreeRam) || active_extended) {
          return fitx::failed();
        }
        active_extended = type;
      }
    }

    // Give an active extended type precedence, as we now know that it can only
    // carve out subranges of active free RAM.
    if (active_extended) {
      return fitx::ok(*active_extended);
    }
    if (active_base) {
      return fitx::ok(*active_base);
    }
    return fitx::ok(std::nullopt);
  }

 private:
  std::array<size_t, kNumBaseTypes + kNumExtendedTypes> values_ = {};
};

}  // namespace

const Range* RangeStream::operator()() {
  static constexpr auto at_end = [](const auto& ctx) { return ctx.it_ == ctx.ranges_.end(); };

  // Dereferencing a cpp20::span iterator returns a reference.
  constexpr auto to_ptr = [](auto it) -> const Range* { return &(*it); };

  // We want to take the lexicographic minimum among the ranges currently
  // pointed to by the context.
  auto state_it =
      std::min_element(state_.begin(), state_.end(), [](const auto& ctx_a, const auto& ctx_b) {
        // Take any non-'end' iterator to be strictly less than any 'end' one.
        if (at_end(ctx_a)) {
          return false;
        }
        if (at_end(ctx_b)) {
          return !at_end(ctx_a);
        }
        return *ctx_a.it_ < *ctx_b.it_;
      });
  if (state_it == state_.end() || at_end(*state_it)) {
    return nullptr;
  }
  return to_ptr(state_it->it_++);
}

void FindNormalizedRamRanges(RangeStream ranges, RangeCallback cb) {
  // Having sorted lexicographically on range endpoints (as RangeStream
  // does) is crucial to the following logic. With this ordering, given a range
  // of interest, the moment we come across a range disjoint from it, we know
  // that all subsequent ranges will similarly be disjoint. This allows us to
  // straightforwardly disambiguate the contiguous regions among
  // arbitrarily-overlapping ranges.

  // The current RAM range of interest. With each new RAM range we come across,
  // we see if it can be merged into the candidate and update accordingly; with
  // each new non-RAM range, we see if it intersects with the candidate and
  // truncate accordingly. Once we know that subsequent ranges are disjoint, we
  // know that the candidate is contiguous and we see if it meets our
  // constraints; otherwise we move onto the next one.
  Interval candidate;
  // Tracks the last contiguous range of memory that is the union of all
  // non-RAM types.
  Interval current_non_ram;
  for (const Range* range = ranges(); range != nullptr; range = ranges()) {
    Interval interval(*range);
    if (interval.empty()) {
      continue;
    }

    if (range->type == Type::kFreeRam) {
      // Check to see if this new RAM interval intersects with the current
      // non-RAM interval we're tracking. If they intersect, it would be at
      // the head of the new interval; if so, update the new interval to just
      // cover the tail.
      if (interval.IntersectsWith(current_non_ram)) {
        ZX_DEBUG_ASSERT(interval.HeadBeforeIntersection(current_non_ram).empty());
        interval = interval.TailAfterIntersection(current_non_ram);
        if (interval.empty()) {
          continue;
        }
      }

      // Merge the new RAM range into the current candidate if possible.
      if (candidate.IntersectsWith(interval) || candidate.IsAdjacentTo(interval)) {
        candidate.MergeInto(interval);
      } else {
        // Found new, disjoint RAM interval. The candidate is guaranteed to not
        // intersect with any subsequent ranges. Emit and move on.
        if (!candidate.empty() && !cb(candidate.AsRamRange())) {
          return;
        }
        candidate = interval;
      }
    } else {
      // Check to see if the candidate RAM intersects with this new non-RAM
      // interval. If it does, emit the pre-intersection head and then update
      // the candidate as the post-intersection tail.
      if (candidate.IntersectsWith(interval)) {
        Interval before = candidate.HeadBeforeIntersection(interval);
        if (!before.empty() && !cb(before.AsRamRange())) {
          return;
        }
        candidate = candidate.TailAfterIntersection(interval);
      }

      if (current_non_ram.IntersectsWith(interval) || current_non_ram.IsAdjacentTo(interval)) {
        current_non_ram.MergeInto(interval);
      } else {
        current_non_ram = interval;
      }
    }
  }

  // There are no more ranges. Since we compared each new RAM interval against the
  // the current non-RAM interval and each new non-RAM interval against the
  // candidate, refitting as we went, we can be sure that the remaining
  // candidate is disjoint from the remaining non-RAM interval (% emptiness).
  ZX_DEBUG_ASSERT(candidate.empty() || current_non_ram.empty() ||
                  !candidate.IntersectsWith(current_non_ram));
  if (!candidate.empty()) {
    cb(candidate.AsRamRange());
  }
}

fitx::result<fitx::failed> FindNormalizedRanges(RangeStream ranges, cpp20::span<void*> scratch,
                                                RangeCallback cb) {
  if (ranges.empty()) {
    return fitx::ok();
  }

  // This algorithm relies on creating a sorted array of endpoints. For every
  // range, we need two endpoints, each of which we represent with two words.
  {
    static_assert(std::alignment_of_v<void*> % std::alignment_of_v<Endpoint> == 0);
    static_assert(sizeof(Endpoint) == 2 * sizeof(void*));
    const size_t min_size_bytes = FindNormalizedRangesScratchSize(ranges.size()) * sizeof(void*);
    ZX_ASSERT_MSG(scratch.size_bytes() >= min_size_bytes,
                  "scratch space must be at least 4*sizeof(void*) times the number of ranges "
                  "(%zu) in bytes: expected >= %zu bytes; got %zu bytes",
                  ranges.size(), min_size_bytes, scratch.size_bytes());
  }

  cpp20::span<Endpoint> endpoints{reinterpret_cast<Endpoint*>(scratch.data()), 2 * ranges.size()};
  for (size_t i = 0; i < ranges.size(); ++i) {
    const Range* range = ranges();
    ZX_DEBUG_ASSERT(range);
    endpoints[2 * i] = {range, EndpointType::kLeft};
    endpoints[2 * i + 1] = {range, EndpointType::kRight};
  }
  std::sort(endpoints.begin(), endpoints.end());

  // The following algorithm is simple, but rather subtle. It works as follows.
  //
  // We iterate through endpoints sorted by value and maintain counters that
  // gives the number of the original ranges that are 'active' at this point in
  // time: if we see a left endpoint, the associated counter is incremented; if
  // we see a right endpoint, it is decremented. We also maintain the the type
  // and start value of the normalized range we are currently building up.
  //
  // After processing each endpoint of a specific value, we take stock of the
  // counters: every positive counter corresponds to a collection of active
  // ranges of that associated type. If there are active ranges, let TYPE be
  // the most dominant among them (i.e., with the highest relative precedence):
  // then we are either in the process of building up a normalized TYPE range
  // or have just started to; if the former, then carry on; if the latter, it
  // is time to emit the previous normalized range we had been building up, as
  // we have just found its end. If all counters are zero, we are no longer
  // building up a normalized range and should clear the tracked start and type.
  ActiveRanges counters;
  std::optional<Type> curr_type;
  uint64_t curr_start = endpoints.front().value();
  uint64_t curr_value = curr_start;

  // Processes an "event", given by seeing a new active, normalized range type.
  // If std::nullopt, there are no active ranges at this time.
  auto process_event = [&](std::optional<Type> active_type) -> bool {
    // Still building up the same range.
    if (active_type == curr_type) {
      return true;
    }

    // If we have been building up a (non-empty) normalized range of a
    // different type, emit it.
    ZX_DEBUG_ASSERT(curr_start <= curr_value);
    if (curr_type && curr_start < curr_value) {
      if (!cb({.addr = curr_start, .size = curr_value - curr_start, .type = *curr_type})) {
        return false;
      }
    }
    curr_start = curr_value;
    curr_type = active_type;
    return true;
  };

  for (size_t i = 0; i < endpoints.size();) {
    curr_value = endpoints[i].value();
    do {
      const Endpoint& endpoint = endpoints[i];
      ZX_DEBUG_ASSERT(endpoint.range);
      const Type type = endpoint.range->type;
      if (endpoint.IsLeft()) {
        counters[type]++;
      } else {
        ZX_DEBUG_ASSERT(counters[type] > 0);
        counters[type]--;
      }
      ++i;
    } while (i < endpoints.size() && endpoints[i].value() == curr_value);

    auto result = counters.DominantType();
    if (result.is_error()) {
      return result.take_error();
    }
    if (!process_event(std::move(result).value())) {
      return fitx::ok();
    }
  }
  // There should be no active ranges tracked now, normalized or otherwise.
  ZX_DEBUG_ASSERT(!curr_type);
  ZX_DEBUG_ASSERT(counters.DominantType().is_ok());
  ZX_DEBUG_ASSERT(!counters.DominantType().value());
  return fitx::ok();
}

}  // namespace memalloc