-namespace simgrid {
-namespace kernel {
-namespace lmm {
-
-typedef std::vector<int> dyn_light_t;
-
-int Variable::next_rank_ = 1;
-int Constraint::next_rank_ = 1;
-
-System* make_new_maxmin_system(bool selective_update)
-{
- return new System(selective_update);
-}
-
-int Element::get_concurrency() const
-{
- // Ignore element with weight less than one (e.g. cross-traffic)
- return (consumption_weight >= 1) ? 1 : 0;
- // There are other alternatives, but they will change the behavior of the model..
- // So do not use it unless you want to make a new model.
- // If you do, remember to change the variables concurrency share to reflect it.
- // Potential examples are:
- // return (elem->weight>0)?1:0;//Include element as soon as weight is non-zero
- // return (int)ceil(elem->weight);//Include element as the rounded-up integer value of the element weight
-}
-
-void Element::decrease_concurrency()
-{
- xbt_assert(constraint->concurrency_current_ >= get_concurrency());
- constraint->concurrency_current_ -= get_concurrency();
-}
-
-void Element::increase_concurrency()
-{
- constraint->concurrency_current_ += get_concurrency();
-
- if (constraint->concurrency_current_ > constraint->concurrency_maximum_)
- constraint->concurrency_maximum_ = constraint->concurrency_current_;
-
- xbt_assert(constraint->get_concurrency_limit() < 0 ||
- constraint->concurrency_current_ <= constraint->get_concurrency_limit(),
- "Concurrency limit overflow!");
-}
-
-void System::check_concurrency() const
-{
- // These checks are very expensive, so do them only if we want to debug SURF LMM
- if (not XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug))
- return;
-
- for (Constraint const& cnst : constraint_set) {
- int concurrency = 0;
- for (Element const& elem : cnst.enabled_element_set_) {
- xbt_assert(elem.variable->sharing_penalty_ > 0);
- concurrency += elem.get_concurrency();
- }
-
- for (Element const& elem : cnst.disabled_element_set_) {
- // We should have staged variables only if concurrency is reached in some constraint
- xbt_assert(cnst.get_concurrency_limit() < 0 || elem.variable->staged_penalty_ == 0 ||
- elem.variable->get_min_concurrency_slack() < elem.variable->concurrency_share_,
- "should not have staged variable!");
- }
-
- xbt_assert(cnst.get_concurrency_limit() < 0 || cnst.get_concurrency_limit() >= concurrency,
- "concurrency check failed!");
- xbt_assert(cnst.concurrency_current_ == concurrency, "concurrency_current is out-of-date!");
- }
-
- // Check that for each variable, all corresponding elements are in the same state (i.e. same element sets)
- for (Variable const& var : variable_set) {
- if (var.cnsts_.empty())
- continue;
-
- const Element& elem = var.cnsts_[0];
- int belong_to_enabled = elem.enabled_element_set_hook.is_linked();
- int belong_to_disabled = elem.disabled_element_set_hook.is_linked();
- int belong_to_active = elem.active_element_set_hook.is_linked();
-
- for (Element const& elem2 : var.cnsts_) {
- xbt_assert(belong_to_enabled == elem2.enabled_element_set_hook.is_linked(),
- "Variable inconsistency (1): enabled_element_set");
- xbt_assert(belong_to_disabled == elem2.disabled_element_set_hook.is_linked(),
- "Variable inconsistency (2): disabled_element_set");
- xbt_assert(belong_to_active == elem2.active_element_set_hook.is_linked(),
- "Variable inconsistency (3): active_element_set");
- }
- }
-}
-
-void System::var_free(Variable* var)
-{
- XBT_IN("(sys=%p, var=%p)", this, var);
- modified_ = true;
-
- // TODOLATER Can do better than that by leaving only the variable in only one enabled_element_set, call
- // update_modified_set, and then remove it..
- if (not var->cnsts_.empty())
- update_modified_set(var->cnsts_[0].constraint);
-
- for (Element& elem : var->cnsts_) {
- if (var->sharing_penalty_ > 0)
- elem.decrease_concurrency();
- if (elem.enabled_element_set_hook.is_linked())
- simgrid::xbt::intrusive_erase(elem.constraint->enabled_element_set_, elem);
- if (elem.disabled_element_set_hook.is_linked())
- simgrid::xbt::intrusive_erase(elem.constraint->disabled_element_set_, elem);
- if (elem.active_element_set_hook.is_linked())
- simgrid::xbt::intrusive_erase(elem.constraint->active_element_set_, elem);
- int nelements = elem.constraint->enabled_element_set_.size() + elem.constraint->disabled_element_set_.size();
- if (nelements == 0)
- make_constraint_inactive(elem.constraint);
- else
- on_disabled_var(elem.constraint);
- }
-
- var->cnsts_.clear();
-
- check_concurrency();
-
- xbt_mallocator_release(variable_mallocator_, var);
- XBT_OUT();
-}
-
-System::System(bool selective_update) : selective_update_active(selective_update)
-{
- XBT_DEBUG("Setting selective_update_active flag to %d", selective_update_active);
-
- if (selective_update)
- modified_set_ = new kernel::resource::Action::ModifiedSet();
-}
-
-System::~System()
-{
- Variable* var;
- Constraint* cnst;
-
- while ((var = extract_variable())) {
- auto demangled = simgrid::xbt::demangle(var->id_ ? typeid(*var->id_).name() : "(unidentified)");
- XBT_WARN("Probable bug: a %s variable (#%d) not removed before the LMM system destruction.", demangled.get(),
- var->rank_);
- var_free(var);
- }
- while ((cnst = extract_constraint()))
- cnst_free(cnst);
-
- xbt_mallocator_free(variable_mallocator_);
- delete modified_set_;
-}
-
-void System::cnst_free(Constraint* cnst)
-{
- make_constraint_inactive(cnst);
- delete cnst;
-}
-
-Constraint::Constraint(resource::Resource* id_value, double bound_value) : bound_(bound_value), id_(id_value)
-{
- rank_ = next_rank_++;
-
- remaining_ = 0.0;
- usage_ = 0.0;
- concurrency_limit_ = sg_concurrency_limit;
- concurrency_current_ = 0;
- concurrency_maximum_ = 0;
- sharing_policy_ = s4u::Link::SharingPolicy::SHARED;
-
- lambda_ = 0.0;
- new_lambda_ = 0.0;
- cnst_light_ = nullptr;
-}
-
-Constraint* System::constraint_new(resource::Resource* id, double bound_value)
-{
- Constraint* cnst = new Constraint(id, bound_value);
- insert_constraint(cnst);
- return cnst;
-}
-
-void* System::variable_mallocator_new_f()
-{
- return new Variable;
-}
-
-void System::variable_mallocator_free_f(void* var)
-{
- delete static_cast<Variable*>(var);
-}
-
-Variable* System::variable_new(resource::Action* id, double sharing_penalty, double bound, size_t number_of_constraints)
-{
- XBT_IN("(sys=%p, id=%p, penalty=%f, bound=%f, num_cons =%zu)", this, id, sharing_penalty, bound,
- number_of_constraints);
-
- Variable* var = static_cast<Variable*>(xbt_mallocator_get(variable_mallocator_));
- var->initialize(id, sharing_penalty, bound, number_of_constraints, visited_counter_ - 1);
- if (sharing_penalty > 0)
- variable_set.push_front(*var);
- else
- variable_set.push_back(*var);
-
- XBT_OUT(" returns %p", var);
- return var;
-}
-
-void System::variable_free(Variable* var)
-{
- remove_variable(var);
- var_free(var);
-}
-
-void System::variable_free_all()
-{
- Variable* var;
- while ((var = extract_variable()))
- variable_free(var);
-}
-
-void System::expand(Constraint* cnst, Variable* var, double consumption_weight)
-{
- modified_ = true;
-
- // Check if this variable already has an active element in this constraint
- // If it does, subtract it from the required slack
- int current_share = 0;
- if (var->concurrency_share_ > 1) {
- for (Element& elem : var->cnsts_) {
- if (elem.constraint == cnst && elem.enabled_element_set_hook.is_linked())
- current_share += elem.get_concurrency();
- }
- }
-
- // Check if we need to disable the variable
- if (var->sharing_penalty_ > 0 && var->concurrency_share_ - current_share > cnst->get_concurrency_slack()) {
- double penalty = var->sharing_penalty_;
- disable_var(var);
- for (Element const& elem : var->cnsts_)
- on_disabled_var(elem.constraint);
- consumption_weight = 0;
- var->staged_penalty_ = penalty;
- xbt_assert(not var->sharing_penalty_);
- }
-
- xbt_assert(var->cnsts_.size() < var->cnsts_.capacity(), "Too much constraints");
-
- var->cnsts_.resize(var->cnsts_.size() + 1);
- Element& elem = var->cnsts_.back();
-
- elem.consumption_weight = consumption_weight;
- elem.constraint = cnst;
- elem.variable = var;
-
- if (var->sharing_penalty_) {
- elem.constraint->enabled_element_set_.push_front(elem);
- elem.increase_concurrency();
- } else
- elem.constraint->disabled_element_set_.push_back(elem);
-
- if (not selective_update_active) {
- make_constraint_active(cnst);
- } else if (elem.consumption_weight > 0 || var->sharing_penalty_ > 0) {
- make_constraint_active(cnst);
- update_modified_set(cnst);
- // TODOLATER: Why do we need this second call?
- if (var->cnsts_.size() > 1)
- update_modified_set(var->cnsts_[0].constraint);
- }
-
- check_concurrency();
-}
-
-void System::expand_add(Constraint* cnst, Variable* var, double value)
-{
- modified_ = true;
-
- check_concurrency();
-
- // BEWARE: In case you have multiple elements in one constraint, this will always add value to the first element.
- auto elem_it =
- std::find_if(begin(var->cnsts_), end(var->cnsts_), [&cnst](Element const& x) { return x.constraint == cnst; });
- if (elem_it != end(var->cnsts_)) {
- Element& elem = *elem_it;
- if (var->sharing_penalty_)
- elem.decrease_concurrency();
-
- if (cnst->sharing_policy_ != s4u::Link::SharingPolicy::FATPIPE)
- elem.consumption_weight += value;
- else
- elem.consumption_weight = std::max(elem.consumption_weight, value);
-
- // We need to check that increasing value of the element does not cross the concurrency limit
- if (var->sharing_penalty_) {
- if (cnst->get_concurrency_slack() < elem.get_concurrency()) {
- double penalty = var->sharing_penalty_;
- disable_var(var);
- for (Element const& elem2 : var->cnsts_)
- on_disabled_var(elem2.constraint);
- var->staged_penalty_ = penalty;
- xbt_assert(not var->sharing_penalty_);
- }
- elem.increase_concurrency();
- }
- update_modified_set(cnst);
- } else
- expand(cnst, var, value);
-
- check_concurrency();
-}
-
-Variable* Constraint::get_variable(const Element** elem) const
-{
- if (*elem == nullptr) {
- // That is the first call, pick the first element among enabled_element_set (or disabled_element_set if
- // enabled_element_set is empty)
- if (not enabled_element_set_.empty())
- *elem = &enabled_element_set_.front();
- else if (not disabled_element_set_.empty())
- *elem = &disabled_element_set_.front();
- else
- *elem = nullptr;
- } else {
- // elem is not null, so we carry on
- if ((*elem)->enabled_element_set_hook.is_linked()) {
- // Look at enabled_element_set, and jump to disabled_element_set when finished
- auto iter = std::next(enabled_element_set_.iterator_to(**elem));
- if (iter != std::end(enabled_element_set_))
- *elem = &*iter;
- else if (not disabled_element_set_.empty())
- *elem = &disabled_element_set_.front();
- else
- *elem = nullptr;
- } else {
- auto iter = std::next(disabled_element_set_.iterator_to(**elem));
- *elem = iter != std::end(disabled_element_set_) ? &*iter : nullptr;
- }
- }
- if (*elem)
- return (*elem)->variable;
- else
- return nullptr;
-}
-
-// if we modify the list between calls, normal version may loop forever
-// this safe version ensures that we browse the list elements only once
-Variable* Constraint::get_variable_safe(const Element** elem, const Element** nextelem, int* numelem) const
-{
- if (*elem == nullptr) {
- *numelem = enabled_element_set_.size() + disabled_element_set_.size() - 1;
- if (not enabled_element_set_.empty())
- *elem = &enabled_element_set_.front();
- else if (not disabled_element_set_.empty())
- *elem = &disabled_element_set_.front();
- else
- *elem = nullptr;
- } else {
- *elem = *nextelem;
- if (*numelem > 0) {
- (*numelem)--;
- } else
- return nullptr;
- }
- if (*elem) {
- // elem is not null, so we carry on
- if ((*elem)->enabled_element_set_hook.is_linked()) {
- // Look at enabled_element_set, and jump to disabled_element_set when finished
- auto iter = std::next(enabled_element_set_.iterator_to(**elem));
- if (iter != std::end(enabled_element_set_))
- *nextelem = &*iter;
- else if (not disabled_element_set_.empty())
- *nextelem = &disabled_element_set_.front();
- else
- *nextelem = nullptr;
- } else {
- auto iter = std::next(disabled_element_set_.iterator_to(**elem));
- *nextelem = iter != std::end(disabled_element_set_) ? &*iter : nullptr;
- }
- return (*elem)->variable;
- } else
- return nullptr;
-}