blob: 60b8864c1e16cced5808bf13930e160fbe45e75e [file] [log] [blame] [edit]
// 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
#include <lib/fit/defer.h>
#include <kernel/owned_wait_queue.h>
#include <kernel/scheduler_internal.h>
#include <ktl/algorithm.h>
#include <ktl/type_traits.h>
#include "kernel/scheduler.h"
// PiOperation is an inner class of Scheduler and the base class of each of the
// various PI operations we need to implement. Its primary jobs are:
//
// 1) Provide accessors abstract the distinction between a thread and an owned
// wait queue when working with templated methods who operate on an UpstreamType
// and a TargetType, where each type might be either a Thread or an
// OwnedWaitQueue.
// 2) Implement the common PI handler responsible for obtaining the proper
// locks, and removing/re-inserting a target from/to its container while
// updating the targets dynamic scheduling parameters.
// 3) Do all of this using CRTP instead of lambdas, allowing us to preserve
// our static annotations all of the way through the operation instead of
// needing to dynamically assert that we hold certain capabilities throughout
// the operation.
template <typename Op, typename TargetType>
class Scheduler::PiOperation {
protected:
PiOperation(TargetType& target) TA_REQ(target.get_lock()) : target_(target) {}
static void AssertEpDirtyState(const Thread& thread, SchedulerState::ProfileDirtyFlag expected)
TA_REQ(thread.get_lock()) {
thread.scheduler_state().effective_profile().AssertDirtyState(expected);
}
static SchedTime& GetStartTime(Thread& thread) TA_REQ(thread.get_lock()) {
return thread.scheduler_state().start_time_;
}
static SchedTime& GetFinishTime(Thread& thread) TA_REQ(thread.get_lock()) {
return thread.scheduler_state().finish_time_;
}
static SchedDuration& GetTimeSliceNs(Thread& thread) TA_REQ(thread.get_lock()) {
return thread.scheduler_state().time_slice_ns_;
}
static SchedTime GetStartTime(const Thread& thread) TA_REQ(thread.get_lock()) {
return thread.scheduler_state().start_time_;
}
static SchedTime GetFinishTime(const Thread& thread) TA_REQ(thread.get_lock()) {
return thread.scheduler_state().finish_time_;
}
static SchedDuration GetTimeSliceNs(const Thread& thread) TA_REQ(thread.get_lock()) {
return thread.scheduler_state().time_slice_ns_;
}
// OwnedWaitQueues do not need to bother to track the dirty or clean state of
// their implied effective profile. They have no base profile (only inherited
// values) which gets turned into an effective profile by the
// EffectiveProfileHeper (see below) during a PI interaction. We can get away
// with this because OWQs:
//
// 1) Cannot exist in any collections where their position is determined by effective profile
// (otherwise we would need to remove and re-insert the node in the collection during an
// update).
// 2) Cannot contribute to a scheduler's bookkeeping (because OWQs are not things which get
// scheduled).
//
static void AssertEpDirtyState(const OwnedWaitQueue& owq,
SchedulerState::ProfileDirtyFlag expected) TA_REQ(owq.get_lock()) {
}
static SchedTime& GetStartTime(OwnedWaitQueue& owq) TA_REQ(owq.get_lock()) {
return owq.inherited_scheduler_state_storage()->start_time;
}
static SchedTime& GetFinishTime(OwnedWaitQueue& owq) TA_REQ(owq.get_lock()) {
return owq.inherited_scheduler_state_storage()->finish_time;
}
static SchedDuration& GetTimeSliceNs(OwnedWaitQueue& owq) TA_REQ(owq.get_lock()) {
return owq.inherited_scheduler_state_storage()->time_slice_ns;
}
static SchedTime GetStartTime(const OwnedWaitQueue& owq) TA_REQ(owq.get_lock()) {
return owq.inherited_scheduler_state_storage()->start_time;
}
static SchedTime GetFinishTime(const OwnedWaitQueue& owq) TA_REQ(owq.get_lock()) {
return owq.inherited_scheduler_state_storage()->finish_time;
}
static SchedDuration GetTimeSliceNs(const OwnedWaitQueue& owq) TA_REQ(owq.get_lock()) {
return owq.inherited_scheduler_state_storage()->time_slice_ns;
}
inline void HandlePiInteractionCommon() TA_REQ(chainlock_transaction_token, target_.get_lock());
TargetType& target_;
const SchedTime mono_now_{CurrentTime()};
};
namespace {
// Notes about ComputeEffectiveProfile and the EffectiveProfileHelper:
//
// Threads contain internal storage which holds their "effective profile", the
// combination of their base profile and all of their inherited profile
// pressure, as well as set of dirty/clean flags.
//
// Owned wait queues don't have quite the same arrangement. They themselves
// have no base profile, and their effective profile is really only the their
// inherited deadline profile (if any), or the total of their inherited fair
// weight (if there is no inherited deadline). They do not explicitly maintain
// storage for their effective profile.
//
// When we get to this point in profile propagation, however, we need to be able
// to compute 3 things:
//
// 1) The effective profile of the target node before recomputing it because of
// the change in profile pressure.
// 2) The effective profile of the target node after recomputing it because of
// the change in profile pressure (note that this is the same for OWQs, but
// not threads)
// 3) The effective profile of the upstream node which gave rise to the change
// in target profile pressure.
//
// For threads, we can just access the reference to the current effective
// profile when we need to know. The non-templated Thread version of
// HandlePiCommon can latch the old ep into a local variable before recomputing,
// and pass the reference to both the old and new profiles to the injected
// callback. Likewise, if a thread is the upstream node and an operation needs
// to know the effective profile of the upstream node, a reference to the
// thread's internal storage is all which is needed.
//
// OWQs are a bit more problematic as they don't have internal storage to
// reference. We actually need to compute what the effective profile is based
// on the current IPVs, and store that result somewhere. We would rather not
// perform this calculation when we don't have to, and we would also rather not
// copy a thread's effective profile into local stack allocated storage if we
// don't have to.
//
// This starts to become an issue in the operations themselves, whose node types
// are templated to keep the logic consistent even when the nodes involved are
// different combinations of Thread and OWQ. In particular, when an operation
// captures the `upstream` member in a lambda callback, we cannot simply call
// `upstream.effective_profile()` to fetch a reference to internal storage (OWQs
// don't have any), nor do we want to copy the thread's internal storage to a
// local EP instance when we could have used a const reference to the thread's
// internal storage instead.
//
// The ComputeEffectiveProfile function and EffectiveProfileHelper class (below)
// help out with this situation. ComputeEffectiveProfile defines the logic for
// determining what an OWQ's effective profile is based on its IPVs. It is used
// in the OWQ specific version of HandlePiCommon to provide the old/new ep
// arguments to the callback.
//
// For local lambda captures, we use the EffectiveProfileHelper. The Thread
// specialized version just stores the pointer (something the compiler was going
// to cache in a register anyway), while the OWQ version actually allocates
// storage and uses ComputeEffectiveProfile to populate that storage when
// needed.
//
SchedulerState::EffectiveProfile ComputeEffectiveProfile(const OwnedWaitQueue& owq)
TA_REQ(owq.get_lock()) {
SchedulerState::EffectiveProfile ep{};
DEBUG_ASSERT(owq.inherited_scheduler_state_storage() != nullptr);
const SchedulerState::WaitQueueInheritedSchedulerState& iss =
*owq.inherited_scheduler_state_storage();
if (iss.ipvs.uncapped_utilization > SchedUtilization{0}) {
DEBUG_ASSERT(iss.ipvs.min_deadline > SchedDuration{0});
ep.discipline = SchedDiscipline::Deadline;
ep.deadline = SchedDeadlineParams{
ktl::min(Scheduler::kThreadUtilizationMax, iss.ipvs.uncapped_utilization),
iss.ipvs.min_deadline};
} else {
// Note that we cannot assert that the total weight of this OWQ's IPVs has
// dropped to zero at this point. It is possible that there are threads
// still in this queue, just none of them have inheritable profiles.
ep.discipline = SchedDiscipline::Fair;
ep.fair.weight = iss.ipvs.total_weight;
}
return ep;
}
template <typename T>
class EffectiveProfileHelper;
template <>
class EffectiveProfileHelper<Thread> {
public:
EffectiveProfileHelper(const Thread& thread) TA_REQ(thread.get_lock())
: effective_profile_ref_{thread.scheduler_state().effective_profile()} {}
const SchedulerState::EffectiveProfile& operator()(void) const { return effective_profile_ref_; }
private:
const SchedulerState::EffectiveProfile& effective_profile_ref_;
};
template <>
class EffectiveProfileHelper<OwnedWaitQueue> {
public:
EffectiveProfileHelper(const OwnedWaitQueue& owq) TA_REQ(owq.get_lock())
: effective_profile_{ComputeEffectiveProfile(owq)} {}
const SchedulerState::EffectiveProfile& operator()(void) const { return effective_profile_; }
private:
const SchedulerState::EffectiveProfile effective_profile_;
};
template <typename T>
EffectiveProfileHelper(const T&) -> EffectiveProfileHelper<T>;
// Definition of the ThreadBaseProfileChanged operation. Used to update a
// thread's effective profile and position in its container at the start of a
// base profile update operation, regardless of whether or not the target thread
// is currently blocked or currently assigned to a scheduler.
//
// Later on, if the thread happens to be an upstream member of a PI graph whose
// target is either an OwnedWaitQueue or another thread, the
// UpstreamThreadBaseProfileChanged operation will be triggered to handle the
// downstream target of the graph.
class ThreadBaseProfileChangedOp
: public Scheduler::PiOperation<ThreadBaseProfileChangedOp, Thread> {
public:
using Base = Scheduler::PiOperation<ThreadBaseProfileChangedOp, Thread>;
ThreadBaseProfileChangedOp(Thread& target) TA_REQ(target.get_lock())
: Base{target}, has_ever_run_{target.state() != thread_state::THREAD_INITIAL} {}
void UpdateDynamicParams(const SchedulerState::EffectiveProfile& target_old_ep,
const SchedulerState::EffectiveProfile& target_new_ep,
SchedTime virt_now)
TA_REQ(chainlock_transaction_token, target_.get_lock()) {
// When the base profile of a thread was changed by a user, we treat it like
// a yield in order to avoid any attempts by a user to game the system to
// get more bandwidth by constantly changing the base profile of their
// thread(s).
//
// The exception to this is if the thread has been created, but has never
// run before. In this situation, we simply make the thread eligible to run
// right now.
if (!has_ever_run_) {
GetStartTime(target_) = SchedTime{0};
GetFinishTime(target_) = SchedTime{0};
} else if (target_new_ep.IsFair()) {
GetStartTime(target_) = virt_now;
GetFinishTime(target_) = virt_now;
} else {
DEBUG_ASSERT(target_new_ep.IsDeadline());
// TODO(johngro): use the `now` time latched at the start of ThreadBaseProfileChanged instead?
GetStartTime(target_) = SchedTime{current_mono_time()} + target_new_ep.deadline.deadline_ns;
GetFinishTime(target_) = GetStartTime(target_) + target_new_ep.deadline.deadline_ns;
}
GetTimeSliceNs(target_) = SchedDuration{0};
}
void DoOperation() TA_REQ(chainlock_transaction_token) {
// We held this lock at construction time and should never drop any locks
// during our object's lifetime. We should be able to simply Mark that we
// hold it now instead of using a full Assert.
target_.get_lock().MarkHeld();
// The base profile of this thread has changed. While there may or may not be
// something downstream of this thread, we need to start by dealing with
// updating this threads static and dynamic scheduling parameters first.
AssertEpDirtyState(target_, SchedulerState::ProfileDirtyFlag::BaseDirty);
HandlePiInteractionCommon();
}
private:
const bool has_ever_run_;
};
// Definition of the UpstreamThreadBaseProfileChange operation. Called when a
// thread in a graph whose target is either an OwnedWaitQueue or a different
// Thread changes its base profile in order update the target's new effective
// profile, position in container, and dynamic scheduling parameters.
//
template <typename TargetType>
class UpstreamThreadBaseProfileChangedOp
: public Scheduler::PiOperation<UpstreamThreadBaseProfileChangedOp<TargetType>, TargetType> {
public:
UpstreamThreadBaseProfileChangedOp(const Thread& upstream, TargetType& target)
TA_REQ(upstream.get_lock(), target.get_lock())
: Base{target}, upstream_{upstream} {}
void UpdateDynamicParams(const SchedulerState::EffectiveProfile& target_old_ep,
const SchedulerState::EffectiveProfile& target_new_ep,
SchedTime virt_now) TA_REQ(target_.get_lock()) {
// TODO(johngro): What is the proper fair policy here? Typically, we
// penalize threads which are changing profiles to make sure there is no way
// for them to game the system and gain any bandwidth via artificial
// amplification. We don't _really_ want to be punishing threads who are
// having their parameters changed as a result of upstream base profile
// changes, esp if folks start to allow cross process PI.
//
// For now, to keep things simple, we just penalize the target_ thread the
// same way that we penalize any other thread. Basically, don't write code
// where you block a thread behind another thread and then start to change
// its profile while blocked.
if (target_new_ep.IsFair()) {
GetStartTime(target_) = virt_now;
GetFinishTime(target_) = virt_now;
GetTimeSliceNs(target_) = SchedDuration{0};
} else {
DEBUG_ASSERT(target_new_ep.IsDeadline());
GetStartTime(target_) = Base::mono_now_ + target_new_ep.deadline.deadline_ns;
GetFinishTime(target_) = GetStartTime(target_) + target_new_ep.deadline.deadline_ns;
GetTimeSliceNs(target_) = SchedDuration{0};
}
}
void DoOperation() TA_REQ(chainlock_transaction_token) {
// We held these locks at construction time and should never drop any locks
// during our object's lifetime. We should be able to simply Mark that we
// hold them now instead of using a full Assert.
upstream_.get_lock().MarkHeld();
target_.get_lock().MarkHeld();
// The base profile of a thread upstream of this target node has changed. We need to
// do the following:
//
// 1) Recompute the target's effective profile.
// 2) Handle any bookkeeping updates for the scheduler's state, if the target
// is a thread which is either RUNNING or READY, and therefore has a
// scheduler assigned to it.
// 3) Handle any updates to the target's dynamic scheduling parameters (eg,
// start time, finish time, time slice remaining)
if constexpr (ktl::is_same_v<Thread, TargetType>) {
DEBUG_ASSERT(&upstream_ != &target_);
}
AssertEpDirtyState(target_, SchedulerState::ProfileDirtyFlag::InheritedDirty);
AssertEpDirtyState(upstream_, SchedulerState::ProfileDirtyFlag::Clean);
Base::HandlePiInteractionCommon();
}
private:
using Base = Scheduler::PiOperation<UpstreamThreadBaseProfileChangedOp<TargetType>, TargetType>;
using Base::AssertEpDirtyState;
using Base::GetFinishTime;
using Base::GetStartTime;
using Base::GetTimeSliceNs;
using Base::target_;
const Thread& upstream_;
};
// Definition of the Join operation. Called when a new edge is added connecting
// the target of one PI graph (the upstream node) to a different PI graph.
//
template <typename UpstreamType, typename TargetType>
class JoinNodeToPiGraphOp
: public Scheduler::PiOperation<JoinNodeToPiGraphOp<UpstreamType, TargetType>, TargetType> {
public:
JoinNodeToPiGraphOp(const UpstreamType& upstream, TargetType& target)
TA_REQ(upstream.get_lock(), target.get_lock())
: Base{target}, upstream_{upstream} {}
void UpdateDynamicParams(const SchedulerState::EffectiveProfile& target_old_ep,
const SchedulerState::EffectiveProfile& target_new_ep,
SchedTime virt_now)
TA_REQ(chainlock_transaction_token, target_.get_lock()) {
// See DoOperation for why it is ok to simply Mark instead of Assert here.
upstream_.get_lock().MarkHeld();
const EffectiveProfileHelper upstream_ep{upstream_};
// If our upstream node is fair, then we have nothing more to do in the
// common path. Our target_'s effective profile has already been updated
// appropriately, and no changes to the target_'s dynamic deadline scheduling
// parameters needs to be done (since new pressure from a fair thread
// currently has no effect on deadline utilization). Any scheduler specific
// side effects will be handled by the active thread path (below) if the
// target_ is an active thread.
if (upstream_ep().IsFair()) {
return;
}
// Our upstream node is not a fair node, therefore it must be a deadline node.
// In addition, no matter what it was before, our target_ node must now be a
// deadline node.
DEBUG_ASSERT(upstream_ep().IsDeadline());
DEBUG_ASSERT(target_new_ep.IsDeadline());
if (target_old_ep.IsFair()) {
// If the target_ has just now become deadline, we can simply transfer the
// dynamic deadline parameters from upstream to the target_.
GetStartTime(target_) = GetStartTime(upstream_);
GetFinishTime(target_) = GetFinishTime(upstream_);
GetTimeSliceNs(target_) = GetTimeSliceNs(upstream_);
} else {
// The target_ was already a deadline thread, then we need to recompute the
// target_'s dynamic deadline parameters using the lag equation.
// Compute the time till absolute deadline (ttad) of the target_ and
// upstream threads.
const SchedDuration target_ttad = (GetFinishTime(target_) > mono_now_)
? (GetFinishTime(target_) - mono_now_)
: SchedDuration{0};
const SchedDuration upstream_ttad = (GetFinishTime(upstream_) > mono_now_)
? (GetFinishTime(upstream_) - mono_now_)
: SchedDuration{0};
const SchedDuration combined_ttad = ktl::min(target_ttad, upstream_ttad);
GetFinishTime(target_) = ktl::min(GetFinishTime(target_), GetFinishTime(upstream_));
GetStartTime(target_) = GetFinishTime(target_) - target_new_ep.deadline.deadline_ns;
const SchedDuration new_tsr = GetTimeSliceNs(target_) + GetTimeSliceNs(upstream_) +
(target_new_ep.deadline.utilization * combined_ttad) -
(target_old_ep.deadline.utilization * target_ttad) -
(upstream_ep().deadline.utilization * upstream_ttad);
// Limit the TSR. It cannot be less than zero nor can it be more than the
// time until the absolute deadline of the new combined thread.
//
// TODO(johngro): If we did have to clamp the TSR, the amount we clamp by
// needs to turn into carried lag.
GetTimeSliceNs(target_) = ktl::clamp<SchedDuration>(new_tsr, SchedDuration{0}, combined_ttad);
GetFinishTime(target_) = ktl::min(GetFinishTime(target_), GetFinishTime(upstream_));
GetStartTime(target_) = GetFinishTime(target_) - target_new_ep.deadline.deadline_ns;
}
}
void DoOperation() TA_REQ(chainlock_transaction_token) {
// We held these locks at construction time and should never drop any locks
// during our object's lifetime. We should be able to simply Mark that we
// hold them now instead of using a full Assert.
upstream_.get_lock().MarkHeld();
target_.get_lock().MarkHeld();
if constexpr (ktl::is_same_v<UpstreamType, TargetType>) {
DEBUG_ASSERT(&upstream_ != &target_);
}
AssertEpDirtyState(target_, SchedulerState::ProfileDirtyFlag::InheritedDirty);
AssertEpDirtyState(upstream_, SchedulerState::ProfileDirtyFlag::Clean);
Base::HandlePiInteractionCommon();
}
private:
using Base = Scheduler::PiOperation<JoinNodeToPiGraphOp<UpstreamType, TargetType>, TargetType>;
using Base::AssertEpDirtyState;
using Base::GetFinishTime;
using Base::GetStartTime;
using Base::GetTimeSliceNs;
using Base::mono_now_;
using Base::target_;
const UpstreamType& upstream_;
};
// Definition of the Split operation. Called when an upstream node has its
// downstream edge removed, splitting it from the PI graph it was a member of
// and becoming the target of a new graph in the process.
//
template <typename UpstreamType, typename TargetType>
class SplitNodeFromPiGraphOp
: public Scheduler::PiOperation<SplitNodeFromPiGraphOp<UpstreamType, TargetType>, TargetType> {
public:
SplitNodeFromPiGraphOp(const UpstreamType& upstream, TargetType& target)
TA_REQ(upstream.get_lock(), target.get_lock())
: Base{target}, upstream_{upstream} {}
void UpdateDynamicParams(const SchedulerState::EffectiveProfile& target_old_ep,
const SchedulerState::EffectiveProfile& target_new_ep,
SchedTime virt_now)
TA_REQ(chainlock_transaction_token, target_.get_lock()) {
// During construction, we statically required that we were holding
// upstream_.get_lock(). It should be OK to Mark it as held here.
upstream_.get_lock().MarkHeld();
const EffectiveProfileHelper upstream_ep{upstream_};
// Was the target_ node a fair node? If so, there is really nothing for us
// to do here.
if (target_old_ep.IsFair()) {
return;
}
DEBUG_ASSERT(target_old_ep.IsDeadline());
if (target_new_ep.IsFair()) {
// If target_ node is mono_now_ a fair node, then the upstream_ node must have been
// a deadline node. This split operation is what caused the target_ node to
// change from deadline to fair, all of the deadline pressure must have been
// coming from the upstream_ node. Assert all of this.
DEBUG_ASSERT(upstream_ep().IsDeadline());
DEBUG_ASSERT(target_old_ep.deadline.capacity_ns == upstream_ep().deadline.capacity_ns);
DEBUG_ASSERT(target_old_ep.deadline.deadline_ns == upstream_ep().deadline.deadline_ns);
// Give the dynamic deadline parameters over to the upstream_ node.
GetStartTime(upstream_) = GetStartTime(target_);
GetFinishTime(upstream_) = GetFinishTime(target_);
GetTimeSliceNs(upstream_) = GetTimeSliceNs(target_);
// Make sure that our fair parameters have been reset. If we are
// an active thread, we will mono_now_ re-arrive with our new parameters.
GetStartTime(target_) = SchedTime{0};
GetFinishTime(target_) = SchedTime{1};
GetTimeSliceNs(target_) = SchedDuration{0};
} else {
// OK, the target_ node is still a deadline node. If the upstream_ node
// is a fair node, we don't have to do anything at all. A fair node
// splitting off from a deadline node should not change the deadline
// node's dynamic parameters. If the upstream_ fair node is a thread, it is
// going to arrive in a new scheduler queue Real Soon Now, and have new
// dynamic parameters computed for it.
//
// If _both_ nodes are deadline nodes, then we need to invoke the lag
// equation in order to figure out what the new time slice remaining and
// absolute deadlines are.
if (upstream_ep().IsDeadline()) {
// Compute the time till absolute deadline (ttad) of the target_.
const SchedDuration target_ttad = (GetFinishTime(target_) > mono_now_)
? (GetFinishTime(target_) - mono_now_)
: SchedDuration{0};
// Figure out what the uncapped utilization of the combined thread
// _would_ have been based on the utilizations of the target_ and
// upstream_ nodes after the split. It is important when scaling
// timeslices to be sure that we divide by a utilization value which
// is the sum of the two (mono_now_ separated) utilization values.
const SchedUtilization combined_uncapped_utilization =
target_new_ep.deadline.utilization + upstream_ep().deadline.utilization;
// If the upstream_ node's time till absolute deadline is zero, there
// is no need to compute its time slice remaining right mono_now_; we
// would just end up capping it to zero anyway.
//
// TODO(johngro): this changes when carried lag comes into the picture.
if (GetFinishTime(upstream_) <= mono_now_) {
GetTimeSliceNs(upstream_) = SchedDuration{0};
} else {
// Looks like we need to compute this value after all.
const SchedDuration upstream_ttad = GetFinishTime(upstream_) - mono_now_;
const SchedDuration new_upstream_tsr =
upstream_ep().deadline.utilization *
((GetTimeSliceNs(target_) / combined_uncapped_utilization) + upstream_ttad -
target_ttad);
// TODO(johngro): This also changes when carried lag comes into
// play.
GetTimeSliceNs(upstream_) = ktl::max(new_upstream_tsr, SchedDuration{0});
}
// TODO(johngro): Fix this. Logically, it is not correct to
// preserve the abs deadline of the target_ after the split. The
// target_'s bookkeeping should be equivalent to the values which
// would be obtained by joining all of the threads which exist
// upstream_ of this node together. Because of this, our new target_
// finish time should be equal to the min across all finish times
// immediately upstream_ of this node.
//
// Now handle the target_ node. We preserve the absolute deadline of
// the target_ node before and after the split, so we need to
// recompute its start time so that the distance between the
// absolute deadline and the start time is equal to the new relative
// deadline of the target_.
GetStartTime(target_) = GetFinishTime(target_) - target_new_ep.deadline.deadline_ns;
// The time till absolute deadline of the pre and post split target_
// remains the same, so the ttad contributions to the timeslice
// remaining simply drop out of the lag equation.
//
// Note that fixed point division takes the precision of the
// assignee into account to provide headroom in certain situations.
// Use an intermediate with the same fractional precision as the
// utilization operands before scaling the non-fractional timeslice.
const SchedUtilization utilization_ratio =
target_new_ep.deadline.utilization / combined_uncapped_utilization;
const SchedDuration new_target_tsr = GetTimeSliceNs(target_) * utilization_ratio;
// TODO(johngro): once again, need to consider carried lag here.
GetTimeSliceNs(target_) = ktl::max(new_target_tsr, SchedDuration{0});
}
}
}
void DoOperation() TA_REQ(chainlock_transaction_token) {
// We held these locks at construction time and should never drop any locks
// during our object's lifetime. We should be able to simply Mark that we
// hold them now instead of using a full Assert.
upstream_.get_lock().MarkHeld();
target_.get_lock().MarkHeld();
if constexpr (ktl::is_same_v<UpstreamType, TargetType>) {
DEBUG_ASSERT(&upstream_ != &target_);
}
AssertEpDirtyState(target_, SchedulerState::ProfileDirtyFlag::InheritedDirty);
AssertEpDirtyState(upstream_, SchedulerState::ProfileDirtyFlag::Clean);
Base::HandlePiInteractionCommon();
}
private:
using Base = Scheduler::PiOperation<SplitNodeFromPiGraphOp<UpstreamType, TargetType>, TargetType>;
using Base::AssertEpDirtyState;
using Base::GetFinishTime;
using Base::GetStartTime;
using Base::GetTimeSliceNs;
using Base::mono_now_;
using Base::target_;
const UpstreamType& upstream_;
};
} // namespace
// Handle all of the common tasks associated with each of the possible PI
// interactions. The outline of this is:
//
// 1) If the target is an active thread (meaning either running or runnable),
// we need to:
// 1.1) Enter the scheduler's queue lock.
// 1.2) If the thread is active, but not actually running, remove the target
// thread from its scheduler's run queue.
// 1.3) Now update the thread's effective profile.
// 1.4) Apply any changes in the thread's effective profile to its scheduler's
// bookkeeping.
// 1.5) Update the dynamic parameters of the thread.
// 1.6) Either re-insert the thread into its scheduler's run queue (if it was
// READY) or adjust its schedulers preemption time (if it was RUNNING).
// 1.7) Trigger a reschedule on the thread's scheduler.
// 2) If the target is either an OwnedWaitQueue, or a thread which is not
// active:
// 2.1) Recompute the target's effective profile, adjust the target's position
// in it's wait queue if the target is a thread which is currently
// blocked in a wait queue.
// 2.2) Recompute the target's dynamic scheduler parameters.
template <typename Op, typename TargetType>
inline void Scheduler::PiOperation<Op, TargetType>::HandlePiInteractionCommon() {
if constexpr (ktl::is_same_v<TargetType, Thread>) {
SchedulerState& ss = target_.scheduler_state();
if (const cpu_num_t curr_cpu = ss.curr_cpu_; curr_cpu != INVALID_CPU) {
DEBUG_ASSERT_MSG((target_.state() == THREAD_RUNNING) || (target_.state() == THREAD_READY),
"Unexpected target_ state %u for tid %" PRIu64 "\n", target_.state(),
target_.tid());
Scheduler& scheduler = *Get(curr_cpu);
Guard<MonitoredSpinLock, NoIrqSave> queue_guard{&scheduler.queue_lock_, SOURCE_TAG};
scheduler.ValidateInvariants();
scheduler.AssertInScheduler(target_);
const SchedulerQueueState& sqs = target_.scheduler_queue_state();
// Notes about transient states and bookkeeping.
//
// RUNNING threads are always expected to have an assigned CPU, to be
// "active" (contributing to a scheduler's total weight/utilization), and
// to not have any transient state.
//
// READY threads may have an assigned CPU, but some other combination of
// the other factors.
//
// Typically, a READY thread will be active and have no transient state.
// This means that it is waiting in a queue to be scheduled, and will be
// accounted for in its scheduler's bookkeeping. It needs to:
//
// 1) Be removed from its queue (because its position is about to change)
// 2) have its old effective profile be removed from bookkeeping.
// 3) Update its EP.
// 4) have its new effective profile be added to bookkeeping.
// 5) Be re-inserted into the proper run queue.
//
// If a READY thread's transient state is "rescheduling", however, then it
// has been removed from its scheduler's run queue (it is about to become
// scheduled), but it has not had its EP removed from bookkeeping. We do
// not want to remove or re-insert the thread into any queue, but we do
// need to maintain its scheduler's bookkeeping.
//
// Finally, the thread could have a transient state of "migrating" or
// "stolen". In this case, it has both been removed from its old
// scheduler bookkeeping and its run queues. We just need to update its
// effective profile, which will be properly accounted for in its new
// scheduler when it finally arrives there.
if (target_.state() == THREAD_READY) {
if (sqs.transient_state == SchedulerQueueState::TransientState::None) {
DEBUG_ASSERT(sqs.active);
scheduler.EraseFromQueue(&target_);
} else {
DEBUG_ASSERT(!sqs.run_queue_node.InContainer());
}
} else {
// The target_ thread's state is RUNNING. Make sure to update its TSR
// before we update either the dynamic parameters, or the scheduler's
// Running threads should always be "active", and have no transient state.
DEBUG_ASSERT(sqs.active &&
(sqs.transient_state == SchedulerQueueState::TransientState::None));
const SchedDuration actual_runtime_ns = mono_now_ - ss.last_started_running_;
const SchedDuration scaled_actual_runtime_ns = ss.effective_profile().IsDeadline()
? scheduler.ScaleDown(actual_runtime_ns)
: actual_runtime_ns;
ss.runtime_ns_ += actual_runtime_ns;
const SchedDuration new_tsr = (ss.time_slice_ns_ <= scaled_actual_runtime_ns)
? SchedDuration{0}
: (ss.time_slice_ns_ - scaled_actual_runtime_ns);
ss.time_slice_ns_ = new_tsr;
if (EffectiveProfile& cur_ep = ss.effective_profile_; cur_ep.IsFair()) {
cur_ep.fair.normalized_timeslice_remainder =
new_tsr / ktl::max(cur_ep.fair.initial_time_slice_ns, SchedDuration{1});
};
ss.last_started_running_ = mono_now_;
scheduler.start_of_current_time_slice_ns_ = mono_now_;
}
// Go ahead and update the effective profile.
const EffectiveProfile old_ep = ss.effective_profile();
target_.RecomputeEffectiveProfile();
const EffectiveProfile& new_ep = ss.effective_profile();
// If the thread is active, deal with its scheduler's bookkeeping.
if (sqs.active) {
if (old_ep.IsFair()) {
scheduler.weight_total_ -= old_ep.fair.weight;
--scheduler.runnable_fair_task_count_;
} else {
scheduler.UpdateTotalDeadlineUtilization(-old_ep.deadline.utilization);
--scheduler.runnable_deadline_task_count_;
}
if (new_ep.IsFair()) {
scheduler.weight_total_ += new_ep.fair.weight;
++scheduler.runnable_fair_task_count_;
} else {
scheduler.UpdateTotalDeadlineUtilization(new_ep.deadline.utilization);
++scheduler.runnable_deadline_task_count_;
}
}
DEBUG_ASSERT(scheduler.weight_total_ >= SchedWeight{0});
DEBUG_ASSERT(scheduler.total_deadline_utilization_ >= SchedUtilization{0});
// static_cast<Op*>(this)->UpdateDynamicParams(old_ep, new_ep, scheduler.virtual_time_);
static_cast<Op*>(this)->UpdateDynamicParams(old_ep, new_ep, scheduler.virtual_time_);
// OK, we are done updating this thread's state, as well as most of its
// scheduler's state. The last thing to do is to either put the thread
// back into the proper run queue (if it is READY and active), or to
// adjust the preemption time for the scheduler (if this thread is
// actively running)
if (target_.state() == THREAD_READY) {
if (sqs.transient_state == SchedulerQueueState::TransientState::None) {
scheduler.QueueThread(&target_, Placement::Adjustment);
}
} else {
DEBUG_ASSERT(target_.state() == THREAD_RUNNING);
scheduler.target_preemption_time_ns_ =
scheduler.start_of_current_time_slice_ns_ + scheduler.ScaleUp(ss.time_slice_ns_);
}
// We have made a change to this scheduler's state, we need to trigger a
// reschedule operation as soon as we can.
RescheduleMask(cpu_num_to_mask(ss.curr_cpu_));
scheduler.ValidateInvariants();
} else {
// We are dealing with a target_ which is a non-active thread (it has no
// scheduler assigned). If the thread is blocked in a wait queue, update
// its position in the wait queue while also updating its effective
// profile. Otherwise, simply update its effective profile. Once that is
// all done, update the dynamic parameters of the target_ using the
// callback provided by the specific operation.
SchedulerState::EffectiveProfile old_ep = ss.effective_profile_;
if (WaitQueue* wq = target_.wait_queue_state().blocking_wait_queue_; wq != nullptr) {
// Note that to update our position in the WaitQueue this thread is
// blocked in, we need to holding that wait queue's lock. (It has to be
// a WaitQueue and not an OwnedWaitQueue, or the PI operation's target_
// would be the final OWQ, not the blocked Thread.)
//
// This should always be the case. We need to holding the entire PI
// chain during PI propagation. That said, this is pretty much an
// impossible thing to represent using static annotations, so we need to
// fall back on a dynamic assert here instead. We know that we are
// holding the thread locked (because of all of the static annotations),
// so we can use the token that is currently locking the thread's lock
// to verify that the WaitQueue is both locked, and part of the same
// locked chain that this operation owns and is currently locking the
// thread.
wq->get_lock().AssertHeld();
wq->UpdateBlockedThreadEffectiveProfile(target_);
} else {
target_.RecomputeEffectiveProfile();
}
static_cast<Op*>(this)->UpdateDynamicParams(old_ep, ss.effective_profile_, SchedTime{0});
}
} else {
static_assert(ktl::is_same_v<TargetType, OwnedWaitQueue>,
"Targets of PI operations must either be Threads or OwnedWaitQueues");
SchedulerState::EffectiveProfile old_ep{ComputeEffectiveProfile(target_)};
static_cast<Op*>(this)->UpdateDynamicParams(old_ep, old_ep, SchedTime{0});
}
DEBUG_ASSERT_MSG(SchedTime st = GetStartTime(target_);
st >= 0, "start_time %ld\n", st.raw_value());
DEBUG_ASSERT_MSG(SchedTime ft = GetFinishTime(target_);
ft >= 0, "finish_time %ld\n", ft.raw_value());
}
void Scheduler::ThreadBaseProfileChanged(Thread& thread) {
ThreadBaseProfileChangedOp op{thread};
op.DoOperation();
}
template <typename TargetType>
void Scheduler::UpstreamThreadBaseProfileChanged(const Thread& upstream, TargetType& target) {
UpstreamThreadBaseProfileChangedOp op{upstream, target};
op.DoOperation();
}
template <typename UpstreamType, typename TargetType>
void Scheduler::JoinNodeToPiGraph(const UpstreamType& upstream, TargetType& target) {
JoinNodeToPiGraphOp op{upstream, target};
op.DoOperation();
}
template <typename UpstreamType, typename TargetType>
void Scheduler::SplitNodeFromPiGraph(const UpstreamType& upstream, TargetType& target) {
SplitNodeFromPiGraphOp op{upstream, target};
op.DoOperation();
}
template void Scheduler::UpstreamThreadBaseProfileChanged(const Thread&, Thread&);
template void Scheduler::UpstreamThreadBaseProfileChanged(const Thread&, OwnedWaitQueue&);
template void Scheduler::JoinNodeToPiGraph(const Thread&, Thread&);
template void Scheduler::JoinNodeToPiGraph(const Thread&, OwnedWaitQueue&);
template void Scheduler::JoinNodeToPiGraph(const OwnedWaitQueue&, Thread&);
template void Scheduler::JoinNodeToPiGraph(const OwnedWaitQueue&, OwnedWaitQueue&);
template void Scheduler::SplitNodeFromPiGraph(const Thread&, Thread&);
template void Scheduler::SplitNodeFromPiGraph(const Thread&, OwnedWaitQueue&);
template void Scheduler::SplitNodeFromPiGraph(const OwnedWaitQueue&, Thread&);
template void Scheduler::SplitNodeFromPiGraph(const OwnedWaitQueue&, OwnedWaitQueue&);