From 2db0630d598bd5bf5daa239297202b85e8ff0813 Mon Sep 17 00:00:00 2001 From: Martin Quinson Date: Sun, 1 Apr 2018 22:45:44 +0200 Subject: [PATCH 1/1] resource:: extract action_heap into its own class --- include/simgrid/kernel/resource/Action.hpp | 41 +++++++----- include/simgrid/kernel/resource/Model.hpp | 7 +- src/kernel/resource/Action.cpp | 77 ++++++++++++---------- src/kernel/resource/Model.cpp | 14 +--- src/surf/cpu_cas01.cpp | 2 +- src/surf/cpu_interface.cpp | 4 +- src/surf/cpu_ti.cpp | 20 +++--- src/surf/network_cm02.cpp | 29 ++++---- 8 files changed, 102 insertions(+), 92 deletions(-) diff --git a/include/simgrid/kernel/resource/Action.hpp b/include/simgrid/kernel/resource/Action.hpp index 34f05beb2b..874facf500 100644 --- a/include/simgrid/kernel/resource/Action.hpp +++ b/include/simgrid/kernel/resource/Action.hpp @@ -24,8 +24,30 @@ typedef boost::heap::pairing_heap>> heap_type; +typedef std::pair heap_element_type; +class XBT_PUBLIC ActionHeap : heap_type { + friend Action; + +public: + enum class Type { + latency = 100, /* this is a heap entry to warn us when the latency is payed */ + max_duration, /* this is a heap entry to warn us when the max_duration limit (timeout) is reached */ + normal, /* this is a normal heap entry stating the date to finish transmitting */ + unset + }; + + double top_date() const; + void insert(Action* action, double date, ActionHeap::Type type); + void update(Action* action, double date, ActionHeap::Type type); + void remove(Action* action); + Action* pop(); + bool empty() const { return heap_type::empty(); } +}; + /** @details An action is a consumption on a resource (e.g.: a communication for the network) */ class XBT_PUBLIC Action { + friend ActionHeap; + public: /* Lazy update needs this Set hook to maintain a list of the tracked actions */ boost::intrusive::list_member_hook<> modified_set_hook_; @@ -54,13 +76,6 @@ public: sleeping }; - enum class Type { - latency = 100, /* this is a heap entry to warn us when the latency is payed */ - max_duration, /* this is a heap entry to warn us when the max_duration limit (timeout) is reached */ - normal, /* this is a normal heap entry stating the date to finish transmitting */ - unset - }; - /** * @brief Action constructor * @@ -194,14 +209,12 @@ private: double last_update_ = 0; double last_value_ = 0; kernel::lmm::Variable* variable_ = nullptr; - Action::Type type_ = Action::Type::unset; - boost::optional heap_hook_ = boost::none; + + ActionHeap::Type type_ = ActionHeap::Type::unset; + boost::optional heap_hook_ = boost::none; public: - void heapInsert(double key, Action::Type type); - void heapRemove(); - void heapUpdate(double key, Action::Type type); - void heap_clear_handle(); + ActionHeap::Type get_type() const { return type_; } lmm::Variable* get_variable() const { return variable_; } void set_variable(lmm::Variable* var) { variable_ = var; } @@ -212,8 +225,6 @@ public: double get_last_value() const { return last_value_; } void set_last_value(double val) { last_value_ = val; } - Action::Type get_type() const { return type_; } - protected: Action::SuspendStates suspended_ = Action::SuspendStates::not_suspended; }; diff --git a/include/simgrid/kernel/resource/Model.hpp b/include/simgrid/kernel/resource/Model.hpp index e1faffb615..ad3e0cb17b 100644 --- a/include/simgrid/kernel/resource/Model.hpp +++ b/include/simgrid/kernel/resource/Model.hpp @@ -56,10 +56,7 @@ public: UpdateAlgo get_update_algorithm() const { return update_algorithm_; } /** @brief Get Action heap */ - heap_type& get_action_heap() { return action_heap_; } - - double actionHeapTopDate() const { return action_heap_.top().first; } - Action* actionHeapPop(); + ActionHeap& get_action_heap() { return action_heap_; } /** * @brief Share the resources between the actions @@ -95,7 +92,7 @@ private: Action::StateSet* running_action_set_ = new Action::StateSet(); /**< Actions in state SURF_ACTION_RUNNING */ Action::StateSet* failed_action_set_ = new Action::StateSet(); /**< Actions in state SURF_ACTION_FAILED */ Action::StateSet* done_action_set_ = new Action::StateSet(); /**< Actions in state SURF_ACTION_DONE */ - heap_type action_heap_; + ActionHeap action_heap_; }; } // namespace resource diff --git a/src/kernel/resource/Action.cpp b/src/kernel/resource/Action.cpp index f58569352e..39825370df 100644 --- a/src/kernel/resource/Action.cpp +++ b/src/kernel/resource/Action.cpp @@ -38,7 +38,7 @@ Action::~Action() get_model()->get_maxmin_system()->variable_free(get_variable()); /* remove from heap on need (ie, if selective update) */ - heapRemove(); + get_model()->get_action_heap().remove(this); if (modified_set_hook_.is_linked()) simgrid::xbt::intrusive_erase(*get_model()->get_modified_set(), *this); @@ -101,7 +101,7 @@ void Action::set_bound(double bound) get_model()->get_maxmin_system()->update_variable_bound(variable_, bound); if (get_model()->get_update_algorithm() == Model::UpdateAlgo::Lazy && get_last_update() != surf_get_clock()) - heapRemove(); + get_model()->get_action_heap().remove(this); XBT_OUT(); } @@ -119,7 +119,7 @@ void Action::set_max_duration(double duration) { max_duration_ = duration; if (get_model()->get_update_algorithm() == Model::UpdateAlgo::Lazy) // remove action from the heap - heapRemove(); + get_model()->get_action_heap().remove(this); } void Action::set_priority(double weight) @@ -129,7 +129,7 @@ void Action::set_priority(double weight) get_model()->get_maxmin_system()->update_variable_weight(get_variable(), weight); if (get_model()->get_update_algorithm() == Model::UpdateAlgo::Lazy) - heapRemove(); + get_model()->get_action_heap().remove(this); XBT_OUT(); } @@ -139,7 +139,7 @@ void Action::cancel() if (get_model()->get_update_algorithm() == Model::UpdateAlgo::Lazy) { if (modified_set_hook_.is_linked()) simgrid::xbt::intrusive_erase(*get_model()->get_modified_set(), *this); - heapRemove(); + get_model()->get_action_heap().remove(this); } } @@ -159,7 +159,7 @@ void Action::suspend() if (suspended_ != SuspendStates::sleeping) { get_model()->get_maxmin_system()->update_variable_weight(get_variable(), 0.0); if (get_model()->get_update_algorithm() == Model::UpdateAlgo::Lazy) { - heapRemove(); + get_model()->get_action_heap().remove(this); if (state_set_ == get_model()->get_running_action_set() && sharing_priority_ > 0) { // If we have a lazy model, we need to update the remaining value accordingly update_remains_lazy(surf_get_clock()); @@ -177,7 +177,7 @@ void Action::resume() get_model()->get_maxmin_system()->update_variable_weight(get_variable(), get_priority()); suspended_ = SuspendStates::not_suspended; if (get_model()->get_update_algorithm() == Model::UpdateAlgo::Lazy) - heapRemove(); + get_model()->get_action_heap().remove(this); } XBT_OUT(); } @@ -186,35 +186,6 @@ bool Action::is_suspended() { return suspended_ == SuspendStates::suspended; } -/* insert action on heap using a given key and a type */ -void Action::heapInsert(double key, Action::Type type) -{ - type_ = type; - heap_hook_ = get_model()->get_action_heap().emplace(std::make_pair(key, this)); -} - -void Action::heapRemove() -{ - type_ = Action::Type::unset; - if (heap_hook_) { - get_model()->get_action_heap().erase(*heap_hook_); - heap_hook_ = boost::none; - } -} -void Action::heap_clear_handle() -{ - heap_hook_ = boost::none; -} - -void Action::heapUpdate(double key, Action::Type type) -{ - type_ = type; - if (heap_hook_) { - get_model()->get_action_heap().update(*heap_hook_, std::make_pair(key, this)); - } else { - heap_hook_ = get_model()->get_action_heap().emplace(std::make_pair(key, this)); - } -} double Action::get_remains() { @@ -240,6 +211,40 @@ void Action::set_last_update() last_update_ = surf_get_clock(); } +double ActionHeap::top_date() const +{ + return top().first; +} +void ActionHeap::insert(Action* action, double date, ActionHeap::Type type) +{ + action->type_ = type; + action->heap_hook_ = emplace(std::make_pair(date, action)); +} +void ActionHeap::remove(Action* action) +{ + action->type_ = ActionHeap::Type::unset; + if (action->heap_hook_) { + erase(*action->heap_hook_); + action->heap_hook_ = boost::none; + } +} +void ActionHeap::update(Action* action, double date, ActionHeap::Type type) +{ + action->type_ = type; + if (action->heap_hook_) { + heap_type::update(*action->heap_hook_, std::make_pair(date, action)); + } else { + action->heap_hook_ = emplace(std::make_pair(date, action)); + } +} +Action* ActionHeap::pop() +{ + Action* action = top().second; + heap_type::pop(); + action->heap_hook_ = boost::none; + return action; +} + } // namespace surf } // namespace simgrid } // namespace simgrid diff --git a/src/kernel/resource/Model.cpp b/src/kernel/resource/Model.cpp index fab52e2bb5..7f8fff9fcf 100644 --- a/src/kernel/resource/Model.cpp +++ b/src/kernel/resource/Model.cpp @@ -23,14 +23,6 @@ Model::~Model() delete maxmin_system_; } -Action* Model::actionHeapPop() -{ - Action* action = action_heap_.top().second; - action_heap_.pop(); - action->heap_clear_handle(); - return action; -} - Action::ModifiedSet* Model::get_modified_set() const { return maxmin_system_->modified_set_; @@ -62,7 +54,7 @@ double Model::next_occuring_event_lazy(double now) continue; /* bogus priority, skip it */ - if (action->get_priority() <= 0 || action->get_type() == Action::Type::latency) + if (action->get_priority() <= 0 || action->get_type() == ActionHeap::Type::latency) continue; action->update_remains_lazy(now); @@ -93,7 +85,7 @@ double Model::next_occuring_event_lazy(double now) action->get_start_time(), min, share, action->get_max_duration()); if (min > -1) { - action->heapUpdate(min, max_duration_flag ? Action::Type::max_duration : Action::Type::normal); + action_heap_.update(action, min, max_duration_flag ? ActionHeap::Type::max_duration : ActionHeap::Type::normal); XBT_DEBUG("Insert at heap action(%p) min %f now %f", action, min, now); } else DIE_IMPOSSIBLE; @@ -101,7 +93,7 @@ double Model::next_occuring_event_lazy(double now) // hereafter must have already the min value for this resource model if (not action_heap_.empty()) { - double min = actionHeapTopDate() - now; + double min = action_heap_.top_date() - now; XBT_DEBUG("minimum with the HEAP %f", min); return min; } else { diff --git a/src/surf/cpu_cas01.cpp b/src/surf/cpu_cas01.cpp index 213ec2e655..2b42c2b7fb 100644 --- a/src/surf/cpu_cas01.cpp +++ b/src/surf/cpu_cas01.cpp @@ -200,7 +200,7 @@ CpuAction *CpuCas01::sleep(double duration) model()->get_maxmin_system()->update_variable_weight(action->get_variable(), 0.0); if (model()->get_update_algorithm() == kernel::resource::Model::UpdateAlgo::Lazy) { // remove action from the heap - action->heapRemove(); + model()->get_action_heap().remove(action); // this is necessary for a variable with weight 0 since such variables are ignored in lmm and we need to set its // max_duration correctly at the next call to share_resources model()->get_modified_set()->push_front(*action); diff --git a/src/surf/cpu_interface.cpp b/src/surf/cpu_interface.cpp index ceb797d26f..b6c3f2c812 100644 --- a/src/surf/cpu_interface.cpp +++ b/src/surf/cpu_interface.cpp @@ -22,9 +22,9 @@ namespace surf { void CpuModel::update_actions_state_lazy(double now, double /*delta*/) { - while (not get_action_heap().empty() && double_equals(actionHeapTopDate(), now, sg_surf_precision)) { + while (not get_action_heap().empty() && double_equals(get_action_heap().top_date(), now, sg_surf_precision)) { - CpuAction* action = static_cast(actionHeapPop()); + CpuAction* action = static_cast(get_action_heap().pop()); XBT_CDEBUG(surf_kernel, "Something happened to action %p", action); if (TRACE_is_enabled()) { Cpu* cpu = static_cast(action->get_variable()->get_constraint(0)->get_id()); diff --git a/src/surf/cpu_ti.cpp b/src/surf/cpu_ti.cpp index 7df39bf75d..90a5316a95 100644 --- a/src/surf/cpu_ti.cpp +++ b/src/surf/cpu_ti.cpp @@ -333,7 +333,7 @@ double CpuTiModel::next_occuring_event(double now) /* get the min next event if heap not empty */ if (not get_action_heap().empty()) - min_action_duration = actionHeapTopDate() - now; + min_action_duration = get_action_heap().top_date() - now; XBT_DEBUG("Share resources, min next event date: %f", min_action_duration); @@ -342,8 +342,8 @@ double CpuTiModel::next_occuring_event(double now) void CpuTiModel::update_actions_state(double now, double /*delta*/) { - while (not get_action_heap().empty() && actionHeapTopDate() <= now) { - CpuTiAction* action = static_cast(actionHeapPop()); + while (not get_action_heap().empty() && double_equals(get_action_heap().top_date(), now, sg_surf_precision)) { + CpuTiAction* action = static_cast(get_action_heap().pop()); XBT_DEBUG("Action %p: finish", action); action->finish(kernel::resource::Action::State::done); /* update remaining amount of all actions */ @@ -425,7 +425,7 @@ void CpuTi::apply_event(tmgr_trace_event_t event, double value) action.get_state() == kernel::resource::Action::State::not_in_the_system) { action.set_finish_time(date); action.set_state(kernel::resource::Action::State::failed); - action.heapRemove(); + model()->get_action_heap().remove(&action); } } } @@ -485,9 +485,9 @@ void CpuTi::update_actions_finish_time(double now) } /* add in action heap */ if (min_finish > NO_MAX_DURATION) - action.heapUpdate(min_finish, kernel::resource::Action::Type::unset); + model()->get_action_heap().update(&action, min_finish, kernel::resource::ActionHeap::Type::unset); else - action.heapRemove(); + model()->get_action_heap().remove(&action); XBT_DEBUG("Update finish time: Cpu(%s) Action: %p, Start Time: %f Finish Time: %f Max duration %f", getCname(), &action, action.get_start_time(), action.get_finish_time(), action.get_max_duration()); @@ -610,7 +610,7 @@ CpuTiAction::~CpuTiAction() if (action_ti_hook.is_linked()) simgrid::xbt::intrusive_erase(cpu_->action_set_, *this); /* remove from heap */ - heapRemove(); + get_model()->get_action_heap().remove(this); cpu_->set_modified(true); } @@ -623,7 +623,7 @@ void CpuTiAction::set_state(Action::State state) void CpuTiAction::cancel() { this->set_state(Action::State::failed); - heapRemove(); + get_model()->get_action_heap().remove(this); cpu_->set_modified(true); } @@ -632,7 +632,7 @@ void CpuTiAction::suspend() XBT_IN("(%p)", this); if (suspended_ != Action::SuspendStates::sleeping) { suspended_ = Action::SuspendStates::suspended; - heapRemove(); + get_model()->get_action_heap().remove(this); cpu_->set_modified(true); } XBT_OUT(); @@ -663,7 +663,7 @@ void CpuTiAction::set_max_duration(double duration) min_finish = get_finish_time(); /* add in action heap */ - heapUpdate(min_finish, Action::Type::unset); + get_model()->get_action_heap().update(this, min_finish, kernel::resource::ActionHeap::Type::unset); XBT_OUT(); } diff --git a/src/surf/network_cm02.cpp b/src/surf/network_cm02.cpp index fb07e6b583..ed03321f8e 100644 --- a/src/surf/network_cm02.cpp +++ b/src/surf/network_cm02.cpp @@ -159,9 +159,9 @@ LinkImpl* NetworkCm02Model::createLink(const std::string& name, double bandwidth void NetworkCm02Model::update_actions_state_lazy(double now, double /*delta*/) { - while (not get_action_heap().empty() && double_equals(actionHeapTopDate(), now, sg_surf_precision)) { + while (not get_action_heap().empty() && double_equals(get_action_heap().top_date(), now, sg_surf_precision)) { - NetworkCm02Action* action = static_cast(actionHeapPop()); + NetworkCm02Action* action = static_cast(get_action_heap().pop()); XBT_DEBUG("Something happened to action %p", action); if (TRACE_is_enabled()) { int n = action->get_variable()->get_number_of_constraint(); @@ -176,20 +176,20 @@ void NetworkCm02Model::update_actions_state_lazy(double now, double /*delta*/) } // if I am wearing a latency hat - if (action->get_type() == kernel::resource::Action::Type::latency) { + if (action->get_type() == kernel::resource::ActionHeap::Type::latency) { XBT_DEBUG("Latency paid for action %p. Activating", action); get_maxmin_system()->update_variable_weight(action->get_variable(), action->weight_); - action->heapRemove(); + get_action_heap().remove(action); action->set_last_update(); // if I am wearing a max_duration or normal hat - } else if (action->get_type() == kernel::resource::Action::Type::max_duration || - action->get_type() == kernel::resource::Action::Type::normal) { + } else if (action->get_type() == kernel::resource::ActionHeap::Type::max_duration || + action->get_type() == kernel::resource::ActionHeap::Type::normal) { // no need to communicate anymore // assume that flows that reached max_duration have remaining of 0 XBT_DEBUG("Action %p finished", action); action->finish(kernel::resource::Action::State::done); - action->heapRemove(); + get_action_heap().remove(action); } } } @@ -295,10 +295,15 @@ kernel::resource::Action* NetworkCm02Model::communicate(s4u::Host* src, s4u::Hos action->set_variable(get_maxmin_system()->variable_new(action, 0.0, -1.0, constraints_per_variable)); if (get_update_algorithm() == kernel::resource::Model::UpdateAlgo::Lazy) { // add to the heap the event when the latency is payed - XBT_DEBUG("Added action (%p) one latency event at date %f", action, action->latency_ + action->get_last_update()); - action->heapInsert(action->latency_ + action->get_last_update(), route.empty() - ? kernel::resource::Action::Type::normal - : kernel::resource::Action::Type::latency); + double date = action->latency_ + action->get_last_update(); + kernel::resource::ActionHeap::Type type; + if (route.empty()) + type = kernel::resource::ActionHeap::Type::normal; + else + type = kernel::resource::ActionHeap::Type::latency; + + XBT_DEBUG("Added action (%p) one latency event at date %f", action, date); + get_action_heap().insert(action, date, type); } } else action->set_variable(get_maxmin_system()->variable_new(action, 1.0, -1.0, constraints_per_variable)); @@ -472,7 +477,7 @@ void NetworkCm02Action::update_remains_lazy(double now) if ((get_remains_no_update() <= 0 && (get_variable()->get_weight() > 0)) || ((max_duration > NO_MAX_DURATION) && (max_duration <= 0))) { finish(Action::State::done); - heapRemove(); + get_model()->get_action_heap().remove(this); } set_last_update(); -- 2.20.1