blob: 1054b00f4707bd2c93f55b8c19e56010bb586208 [file] [log] [blame]
// Copyright 2024 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <zircon/assert.h>
#include <zircon/time.h>
#include <fbl/intrusive_wavl_tree.h>
#include <ffl/fixed.h>
namespace sched {
// Forward-declared; defined in <lib/sched/run-queue.h>
template <typename Thread>
class RunQueue;
// Fixed-point wrappers for cleaner time arithmetic when dealing with other
// fixed-point quantities.
using Duration = ffl::Fixed<zx_duration_t, 0>;
using Time = ffl::Fixed<zx_time_t, 0>;
// Flexible work weight.
// Gives a measure of priority for the flexible portion of a thread's work
// (i.e., that done on a best-effort basis all other required/firm work is
// accomplished).
// Weights should not be negative; however, the value is signed for consistency
// with Time and Duration, which are the primary types used in conjunction with
// FlexibleWeight. This is to make it less likely that expressions involving
// weights are accidentally promoted to unsigned.
using FlexibleWeight = ffl::Fixed<int64_t, 16>;
// The utilization factor of a thread's desired work, defined as the ratio
// between a thread's capacity (firm, flexible, or total) and its period.
// The 20bit fractional component represents the utilization with a precision
// of ~1us.
using Utilization = ffl::Fixed<int64_t, 20>;
// The parameters that specify a thread's activation period (i.e., the
// recurring cycle in which it is scheduled).
struct BandwidthParameters {
// The duration of the thread's activation period.
Duration period;
// The duration within a given activation period in which a thread is expected
// to complete its *required* work.
Duration firm_capacity;
// The weight of the flexible portion of a thread's work. Zero is equivalent
// to the thread not having flexible work to do, its total capacity being
// equal to its firm capacity.
FlexibleWeight flexible_weight;
// The scheduling state of a thread.
enum class ThreadState : uint8_t {
// The thread is in its initialed state and not yet schedulable.
// The thread is schedulable and not yet running.
// The thread is currently running (or selected to be run).
// The base thread class from which we expect schedulable thread types to
// inherit (following the 'Curiously Recurring Template Pattern'). This class
// manages the scheduler-related thread state of interest to this library.
template <typename Thread>
class ThreadBase {
constexpr ThreadBase(BandwidthParameters bandwidth, Time start)
: period_(bandwidth.period), //
firm_capacity_(bandwidth.firm_capacity), //
flexible_weight_(bandwidth.flexible_weight) {
ZX_DEBUG_ASSERT(bandwidth.period >= bandwidth.firm_capacity);
ZX_DEBUG_ASSERT(bandwidth.period > 0);
ZX_DEBUG_ASSERT(bandwidth.firm_capacity >= 0);
ZX_DEBUG_ASSERT(bandwidth.flexible_weight >= 0);
ZX_DEBUG_ASSERT(bandwidth.firm_capacity != 0 || bandwidth.flexible_weight != 0);
constexpr Duration period() const { return period_; }
constexpr Duration firm_capacity() const { return firm_capacity_; }
constexpr FlexibleWeight flexible_weight() const { return flexible_weight_; }
// The total proportion of the period in which the thread is expected to run
// in order to complete its required work.
constexpr Utilization firm_utilization() const { return firm_capacity() / period(); }
// The start of the thread's current activation period.
constexpr Time start() const { return start_; }
// The end of the thread's current activation period.
constexpr Time finish() const { return start_ + period_; }
// The cumulative amount of scheduled time within the current activation
// period.
constexpr Duration time_slice_used() const { return time_slice_used_; }
// Returns the scheduling state of the thread.
constexpr ThreadState state() const { return state_; }
// Sets the scheduling state of the thread.
void set_state(ThreadState state) { state_ = state; }
// Whether the thread is active at the provided time (i.e., whether that time
// falls within the current activation period).
constexpr bool IsActive(Time now) const { return start() <= now && now < finish(); }
// Reactivates the thread in a new activation period. If the provided time is
// before the current period ends, then the new period will naturally begin at
// the current's finish time; otherwise, the thread missed out on being
// reactivated along the current period boundary (e.g., due to having been
// blocked for an extended period of time) and the activation period will be
// reset starting at `now`.
constexpr void Reactivate(Time now) {
start_ = std::max(now, finish());
time_slice_used_ = Duration{0};
// Accounts for the time in which the thread was executed (as measured outside
// this library).
constexpr void Tick(Duration elapsed) { time_slice_used_ += elapsed; }
// Whether the thread is currently queued to be scheduled (in a RunQueue).
constexpr bool IsQueued() const { return run_queue_.node.InContainer(); }
// For access to `run_queue_` alone.
friend class RunQueue<Thread>;
Duration period_{0};
Duration firm_capacity_{0};
FlexibleWeight flexible_weight_{0};
Time start_{Time::Min()};
Duration time_slice_used_{0};
ThreadState state_ = ThreadState::kInitial;
// Encapsulates the state specific to the run queue.
struct RunQueueState {
fbl::WAVLTreeNodeState<Thread*> node;
// Minimum finish time of all the descendants of this node in the run queue.
// See RunQueue<Thread>::SubtreeMinFinishObserverTraits for the management
// and utility of this quantity.
Time subtree_min_finish{Time::Min()};
} run_queue_;
} // namespace sched