X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/f3f4deb470c034b299c734c200ed62306f068662..929bbf2f78b5c0151713d61bf5b163943b8b9343:/src/surf/maxmin.cpp diff --git a/src/surf/maxmin.cpp b/src/surf/maxmin.cpp index a7e963987c..703762ad8b 100644 --- a/src/surf/maxmin.cpp +++ b/src/surf/maxmin.cpp @@ -6,6 +6,7 @@ /* \file callbacks.h */ #include "maxmin_private.hpp" +#include "xbt/backtrace.hpp" #include "xbt/log.h" #include "xbt/mallocator.h" #include "xbt/sysdep.h" @@ -24,21 +25,10 @@ double sg_maxmin_precision = 0.00001; /* Change this with --cfg=maxmin/precision double sg_surf_precision = 0.00001; /* Change this with --cfg=surf/precision:VALUE */ int sg_concurrency_limit = -1; /* Change this with --cfg=maxmin/concurrency-limit:VALUE */ -static void *lmm_variable_mallocator_new_f(); -static void lmm_variable_mallocator_free_f(void *var); -#define lmm_variable_mallocator_reset_f ((void_f_pvoid_t)nullptr) -static void lmm_update_modified_set(lmm_system_t sys, lmm_constraint_t cnst); -static void lmm_remove_all_modified_set(lmm_system_t sys); static int Global_debug_id = 1; -static int Global_const_debug_id = 1; +int s_lmm_constraint_t::Global_debug_id = 1; -static inline void lmm_cnst_free(lmm_system_t sys, lmm_constraint_t cnst); - -static void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr); -static void lmm_enable_var(lmm_system_t sys, lmm_variable_t var); static int lmm_can_enable_var(lmm_variable_t var); -static void lmm_disable_var(lmm_system_t sys, lmm_variable_t var); -static int lmm_concurrency_slack(lmm_constraint_t cnstr); static int lmm_cnstrs_min_concurrency_slack(lmm_variable_t var); static inline int lmm_element_concurrency(lmm_element_t elem) @@ -68,18 +58,18 @@ static inline void lmm_increase_concurrency(lmm_element_t elem) if(cnstr->concurrency_current > cnstr->concurrency_maximum) cnstr->concurrency_maximum= cnstr->concurrency_current; - xbt_assert(cnstr->concurrency_limit<0 || cnstr->concurrency_current<=cnstr->concurrency_limit, + xbt_assert(cnstr->get_concurrency_limit() < 0 || cnstr->concurrency_current <= cnstr->get_concurrency_limit(), "Concurrency limit overflow!"); } -static void lmm_check_concurrency(lmm_system_t sys) +void s_lmm_system_t::check_concurrency() { // 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; void* cnstIt; - xbt_swag_foreach(cnstIt, &(sys->constraint_set)) + xbt_swag_foreach(cnstIt, &constraint_set) { lmm_constraint_t cnst = (lmm_constraint_t)cnstIt; int concurrency = 0; @@ -95,18 +85,19 @@ static void lmm_check_concurrency(lmm_system_t sys) { lmm_element_t elem = (lmm_element_t)elemIt; // We should have staged variables only if concurrency is reached in some constraint - xbt_assert(cnst->concurrency_limit < 0 || elem->variable->staged_weight == 0 || + xbt_assert(cnst->get_concurrency_limit() < 0 || elem->variable->staged_weight == 0 || lmm_cnstrs_min_concurrency_slack(elem->variable) < elem->variable->concurrency_share, "should not have staged variable!"); } - xbt_assert(cnst->concurrency_limit < 0 || cnst->concurrency_limit >= concurrency, "concurrency check failed!"); + 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) void* varIt; - xbt_swag_foreach(varIt, &(sys->variable_set)) + xbt_swag_foreach(varIt, &variable_set) { lmm_variable_t var = (lmm_variable_t)varIt; @@ -129,15 +120,15 @@ static void lmm_check_concurrency(lmm_system_t sys) } } -static inline void lmm_variable_remove(lmm_system_t sys, lmm_variable_t var) +void s_lmm_system_t::var_free(lmm_variable_t var) { - XBT_IN("(sys=%p, var=%p)", sys, var); - sys->modified = 1; + XBT_IN("(sys=%p, var=%p)", this, var); + modified = 1; // TODOLATER Can do better than that by leaving only the variable in only one enabled_element_set, call - // lmm_update_modified_set, and then remove it.. + // update_modified_set, and then remove it.. if (not var->cnsts.empty()) - lmm_update_modified_set(sys, var->cnsts[0].constraint); + update_modified_set(var->cnsts[0].constraint); for (s_lmm_element_t& elem : var->cnsts) { if (var->sharing_weight > 0) @@ -148,183 +139,114 @@ static inline void lmm_variable_remove(lmm_system_t sys, lmm_variable_t var) int nelements = xbt_swag_size(&(elem.constraint->enabled_element_set)) + xbt_swag_size(&(elem.constraint->disabled_element_set)); if (nelements == 0) - make_constraint_inactive(sys, elem.constraint); + make_constraint_inactive(elem.constraint); else - lmm_on_disabled_var(sys, elem.constraint); - } - - // Check if we can enable new variables going through the constraints where var was. - // Do it after removing all elements, so the first disabled variables get priority over those with smaller requirement - for (s_lmm_element_t& elem : var->cnsts) { - if (xbt_swag_size(&(elem.constraint->disabled_element_set))) - lmm_on_disabled_var(sys, elem.constraint); + on_disabled_var(elem.constraint); } var->cnsts.clear(); - lmm_check_concurrency(sys); + check_concurrency(); + xbt_mallocator_release(variable_mallocator, var); XBT_OUT(); } -static void lmm_var_free(lmm_system_t sys, lmm_variable_t var) -{ - lmm_variable_remove(sys, var); - xbt_mallocator_release(sys->variable_mallocator, var); -} - -lmm_system_t lmm_system_new(bool selective_update) +s_lmm_system_t::s_lmm_system_t(bool selective_update) { s_lmm_variable_t var; s_lmm_constraint_t cnst; - lmm_system_t l = new s_lmm_system_t(); - - l->modified = 0; - l->selective_update_active = selective_update; - l->visited_counter = 1; - - XBT_DEBUG("Setting selective_update_active flag to %d", l->selective_update_active); + modified = 0; + selective_update_active = selective_update; + visited_counter = 1; - xbt_swag_init(&(l->variable_set), xbt_swag_offset(var, variable_set_hookup)); - xbt_swag_init(&(l->constraint_set), xbt_swag_offset(cnst, constraint_set_hookup)); + XBT_DEBUG("Setting selective_update_active flag to %d", selective_update_active); - xbt_swag_init(&(l->active_constraint_set), xbt_swag_offset(cnst, active_constraint_set_hookup)); + xbt_swag_init(&variable_set, xbt_swag_offset(var, variable_set_hookup)); + xbt_swag_init(&constraint_set, xbt_swag_offset(cnst, constraint_set_hookup)); - xbt_swag_init(&(l->modified_constraint_set), xbt_swag_offset(cnst, modified_constraint_set_hookup)); - xbt_swag_init(&(l->saturated_variable_set), xbt_swag_offset(var, saturated_variable_set_hookup)); - xbt_swag_init(&(l->saturated_constraint_set), xbt_swag_offset(cnst, saturated_constraint_set_hookup)); + xbt_swag_init(&active_constraint_set, xbt_swag_offset(cnst, active_constraint_set_hookup)); - l->variable_mallocator = xbt_mallocator_new(65536, - lmm_variable_mallocator_new_f, - lmm_variable_mallocator_free_f, - lmm_variable_mallocator_reset_f); + xbt_swag_init(&modified_constraint_set, xbt_swag_offset(cnst, modified_constraint_set_hookup)); + xbt_swag_init(&saturated_variable_set, xbt_swag_offset(var, saturated_variable_set_hookup)); + xbt_swag_init(&saturated_constraint_set, xbt_swag_offset(cnst, saturated_constraint_set_hookup)); - l->solve_fun = &lmm_solve; - - return l; + keep_track = nullptr; + variable_mallocator = xbt_mallocator_new(65536, s_lmm_system_t::variable_mallocator_new_f, + s_lmm_system_t::variable_mallocator_free_f, nullptr); + solve_fun = &lmm_solve; } -void lmm_system_free(lmm_system_t sys) +s_lmm_system_t::~s_lmm_system_t() { - lmm_variable_t var = nullptr; - lmm_constraint_t cnst = nullptr; - - if (sys == nullptr) - return; - - while ((var = (lmm_variable_t) extract_variable(sys))) { - int status; - char* demangled = abi::__cxa_demangle(typeid(*var->id).name(), 0, 0, &status); + lmm_variable_t var; + lmm_constraint_t cnst; - XBT_WARN("Probable bug: a %s variable (#%d) not removed before the LMM system destruction.", demangled, + while ((var = extract_variable())) { + auto demangled = simgrid::xbt::demangle(typeid(*var->id).name()); + XBT_WARN("Probable bug: a %s variable (#%d) not removed before the LMM system destruction.", demangled.get(), var->id_int); - xbt_free(demangled); - lmm_var_free(sys, var); + var_free(var); } - while ((cnst = (lmm_constraint_t) extract_constraint(sys))) - lmm_cnst_free(sys, cnst); + while ((cnst = extract_constraint())) + cnst_free(cnst); - xbt_mallocator_free(sys->variable_mallocator); - delete sys; + xbt_mallocator_free(variable_mallocator); } -static inline void lmm_cnst_free(lmm_system_t sys, lmm_constraint_t cnst) +void s_lmm_system_t::cnst_free(lmm_constraint_t cnst) { - make_constraint_inactive(sys, cnst); + make_constraint_inactive(cnst); delete cnst; } -lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id, double bound_value) +s_lmm_constraint_t::s_lmm_constraint_t(void* id_value, double bound_value) { - lmm_constraint_t cnst = nullptr; s_lmm_element_t elem; - cnst = new s_lmm_constraint_t(); - cnst->id = id; - cnst->id_int = Global_const_debug_id++; - xbt_swag_init(&(cnst->enabled_element_set), xbt_swag_offset(elem, enabled_element_set_hookup)); - xbt_swag_init(&(cnst->disabled_element_set), xbt_swag_offset(elem, disabled_element_set_hookup)); - xbt_swag_init(&(cnst->active_element_set), xbt_swag_offset(elem, active_element_set_hookup)); - - cnst->bound = bound_value; - cnst->concurrency_maximum=0; - cnst->concurrency_current=0; - cnst->concurrency_limit = sg_concurrency_limit; - cnst->usage = 0; - cnst->sharing_policy = 1; /* FIXME: don't hardcode the value */ - insert_constraint(sys, cnst); - - return cnst; -} - -int lmm_constraint_concurrency_limit_get(lmm_constraint_t cnst) -{ - return cnst->concurrency_limit; -} - -void lmm_constraint_concurrency_limit_set(lmm_constraint_t cnst, int concurrency_limit) -{ - xbt_assert(concurrency_limit<0 || cnst->concurrency_maximum<=concurrency_limit, - "New concurrency limit should be larger than observed concurrency maximum. Maybe you want to call" - " lmm_constraint_concurrency_maximum_reset() to reset the maximum?"); - cnst->concurrency_limit = concurrency_limit; -} - -void lmm_constraint_concurrency_maximum_reset(lmm_constraint_t cnst) -{ - cnst->concurrency_maximum = 0; -} - -int lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst) -{ - xbt_assert(cnst->concurrency_limit<0 || cnst->concurrency_maximum<=cnst->concurrency_limit, - "Very bad: maximum observed concurrency is higher than limit. This is a bug of SURF, please report it."); - return cnst->concurrency_maximum; -} - -void lmm_constraint_shared(lmm_constraint_t cnst) -{ - cnst->sharing_policy = 0; -} - -/** Return true if the constraint is shared, and false if it's FATPIPE */ -int lmm_constraint_sharing_policy(lmm_constraint_t cnst) -{ - return (cnst->sharing_policy); + id = id_value; + id_int = Global_debug_id++; + xbt_swag_init(&enabled_element_set, xbt_swag_offset(elem, enabled_element_set_hookup)); + xbt_swag_init(&disabled_element_set, xbt_swag_offset(elem, disabled_element_set_hookup)); + xbt_swag_init(&active_element_set, xbt_swag_offset(elem, active_element_set_hookup)); + + remaining = 0.0; + usage = 0.0; + bound = bound_value; + concurrency_limit = sg_concurrency_limit; + concurrency_current = 0; + concurrency_maximum = 0; + sharing_policy = 1; /* FIXME: don't hardcode the value */ + + lambda = 0.0; + new_lambda = 0.0; + cnst_light = nullptr; } -/* @brief Remove a constraint - * Currently this is dead code, but it is exposed in maxmin.hpp - * Apparently, this call was designed assuming that constraint would no more have elements in it. - * If not the case, assertion will fail, and you need to add calls e.g. to lmm_shrink before effectively removing it. - */ -inline void lmm_constraint_free(lmm_system_t sys,lmm_constraint_t cnst) +lmm_constraint_t s_lmm_system_t::constraint_new(void* id, double bound_value) { - xbt_assert(not xbt_swag_size(&(cnst->active_element_set)), "Removing constraint but it still has active elements"); - xbt_assert(not xbt_swag_size(&(cnst->enabled_element_set)), "Removing constraint but it still has enabled elements"); - xbt_assert(not xbt_swag_size(&(cnst->disabled_element_set)), - "Removing constraint but it still has disabled elements"); - remove_constraint(sys, cnst); - lmm_cnst_free(sys, cnst); + lmm_constraint_t cnst = new s_lmm_constraint_t(id, bound_value); + insert_constraint(cnst); + return cnst; } -static void *lmm_variable_mallocator_new_f() +void* s_lmm_system_t::variable_mallocator_new_f() { return new s_lmm_variable_t; } -static void lmm_variable_mallocator_free_f(void *var) +void s_lmm_system_t::variable_mallocator_free_f(void* var) { delete static_cast(var); } -lmm_variable_t lmm_variable_new(lmm_system_t sys, simgrid::surf::Action* id, double sharing_weight, double bound, - int number_of_constraints) +lmm_variable_t s_lmm_system_t::variable_new(simgrid::surf::Action* id, double sharing_weight, double bound, + int number_of_constraints) { - XBT_IN("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)", sys, id, sharing_weight, bound, number_of_constraints); + XBT_IN("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)", this, id, sharing_weight, bound, number_of_constraints); - lmm_variable_t var = (lmm_variable_t)xbt_mallocator_get(sys->variable_mallocator); + lmm_variable_t var = (lmm_variable_t)xbt_mallocator_get(variable_mallocator); var->id = id; var->id_int = Global_debug_id++; var->cnsts.reserve(number_of_constraints); @@ -333,7 +255,7 @@ lmm_variable_t lmm_variable_new(lmm_system_t sys, simgrid::surf::Action* id, dou var->bound = bound; var->concurrency_share = 1; var->value = 0.0; - var->visited = sys->visited_counter - 1; + var->visited = visited_counter - 1; var->mu = 0.0; var->new_mu = 0.0; var->func_f = func_f_def; @@ -346,18 +268,18 @@ lmm_variable_t lmm_variable_new(lmm_system_t sys, simgrid::surf::Action* id, dou var->saturated_variable_set_hookup.prev = nullptr; if (sharing_weight) - xbt_swag_insert_at_head(var, &(sys->variable_set)); + xbt_swag_insert_at_head(var, &variable_set); else - xbt_swag_insert_at_tail(var, &(sys->variable_set)); + xbt_swag_insert_at_tail(var, &variable_set); XBT_OUT(" returns %p", var); return var; } -void lmm_variable_free(lmm_system_t sys, lmm_variable_t var) +void s_lmm_system_t::variable_free(lmm_variable_t var) { - remove_variable(sys, var); - lmm_var_free(sys, var); + remove_variable(var); + var_free(var); } double lmm_variable_getvalue(lmm_variable_t var) @@ -375,54 +297,9 @@ double lmm_variable_getbound(lmm_variable_t var) return (var->bound); } -void lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var) -{ - auto elem_it = std::find_if(begin(var->cnsts), end(var->cnsts), - [&cnst](s_lmm_element_t const& x) { return x.constraint == cnst; }); - if (elem_it == end(var->cnsts)) { - XBT_DEBUG("cnst %p is not found in var %p", cnst, var); - return; - } - s_lmm_element_t& elem = *elem_it; - - sys->modified = 1; - - XBT_DEBUG("remove elem(value %f, cnst %p, var %p) in var %p", elem.consumption_weight, elem.constraint, elem.variable, - var); - - /* We are going to change the constraint object and the variable object. - * Propagate this change to other objects. Calling here before removing variable from not active elements - * (inactive elements are not visited) - */ - lmm_update_modified_set(sys, cnst); - //Useful in case var was already removed from the constraint - lmm_update_modified_set(sys, var->cnsts[0].constraint); // will look up enabled_element_set of this constraint, and - //then each var in the enabled_element_set, and each var->cnsts[i]. - - if (xbt_swag_remove(&elem, &(elem.constraint->enabled_element_set))) - lmm_decrease_concurrency(&elem); - - xbt_swag_remove(&elem, &(elem.constraint->active_element_set)); - elem.constraint = nullptr; - elem.variable = nullptr; - elem.consumption_weight = 0; - - var->cnsts.pop_back(); - - //No variable in this constraint -> make it inactive - if (xbt_swag_size(&(cnst->enabled_element_set))+xbt_swag_size(&(cnst->disabled_element_set)) == 0) - make_constraint_inactive(sys, cnst); - else { - //Check maxconcurrency to see if we can enable new variables - lmm_on_disabled_var(sys, elem.constraint); - } - - lmm_check_concurrency(sys); -} - -void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, double consumption_weight) +void s_lmm_system_t::expand(lmm_constraint_t cnst, lmm_variable_t var, double consumption_weight) { - sys->modified = 1; + modified = 1; //Check if this variable already has an active element in this constraint //If it does, substract it from the required slack @@ -435,11 +312,11 @@ void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, dou } //Check if we need to disable the variable - if (var->sharing_weight > 0 && var->concurrency_share - current_share > lmm_concurrency_slack(cnst)) { + if (var->sharing_weight > 0 && var->concurrency_share - current_share > cnst->get_concurrency_slack()) { double weight = var->sharing_weight; - lmm_disable_var(sys,var); + disable_var(var); for (s_lmm_element_t const& elem : var->cnsts) - lmm_on_disabled_var(sys, elem.constraint); + on_disabled_var(elem.constraint); consumption_weight = 0; var->staged_weight=weight; xbt_assert(not var->sharing_weight); @@ -460,24 +337,24 @@ void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, dou } else xbt_swag_insert_at_tail(&elem, &(elem.constraint->disabled_element_set)); - if (not sys->selective_update_active) { - make_constraint_active(sys, cnst); + if (not selective_update_active) { + make_constraint_active(cnst); } else if (elem.consumption_weight > 0 || var->sharing_weight > 0) { - make_constraint_active(sys, cnst); - lmm_update_modified_set(sys, cnst); + make_constraint_active(cnst); + update_modified_set(cnst); //TODOLATER: Why do we need this second call? if (var->cnsts.size() > 1) - lmm_update_modified_set(sys, var->cnsts[0].constraint); + update_modified_set(var->cnsts[0].constraint); } - lmm_check_concurrency(sys); + check_concurrency(); } -void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, double value) +void s_lmm_system_t::expand_add(lmm_constraint_t cnst, lmm_variable_t var, double value) { - sys->modified = 1; + modified = 1; - lmm_check_concurrency(sys); + 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), @@ -494,21 +371,21 @@ void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst, lmm_variable_t var, //We need to check that increasing value of the element does not cross the concurrency limit if (var->sharing_weight) { - if (lmm_concurrency_slack(cnst) < lmm_element_concurrency(&elem)) { + if (cnst->get_concurrency_slack() < lmm_element_concurrency(&elem)) { double weight = var->sharing_weight; - lmm_disable_var(sys,var); + disable_var(var); for (s_lmm_element_t const& elem2 : var->cnsts) - lmm_on_disabled_var(sys, elem2.constraint); + on_disabled_var(elem2.constraint); var->staged_weight=weight; xbt_assert(not var->sharing_weight); } lmm_increase_concurrency(&elem); } - lmm_update_modified_set(sys, cnst); + update_modified_set(cnst); } else - lmm_expand(sys, cnst, var, value); + expand(cnst, var, value); - lmm_check_concurrency(sys); + check_concurrency(); } lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t /*sys*/, lmm_variable_t var, unsigned num) @@ -532,23 +409,23 @@ int lmm_get_number_of_cnst_from_var(lmm_system_t /*sys*/, lmm_variable_t var) return (var->cnsts.size()); } -lmm_variable_t lmm_get_var_from_cnst(lmm_system_t /*sys*/, lmm_constraint_t cnst, lmm_element_t * elem) +lmm_variable_t s_lmm_constraint_t::get_variable(lmm_element_t* 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) - *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->enabled_element_set)); + *elem = (lmm_element_t)xbt_swag_getFirst(&enabled_element_set); if (*elem == nullptr) - *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set)); + *elem = (lmm_element_t)xbt_swag_getFirst(&disabled_element_set); } else { //elem is not null, so we carry on - if(xbt_swag_belongs(*elem,&(cnst->enabled_element_set))){ + if (xbt_swag_belongs(*elem, &enabled_element_set)) { //Look at enabled_element_set, and jump to disabled_element_set when finished - *elem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->enabled_element_set.offset); + *elem = (lmm_element_t)xbt_swag_getNext(*elem, enabled_element_set.offset); if (*elem == nullptr) - *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set)); + *elem = (lmm_element_t)xbt_swag_getFirst(&disabled_element_set); } else { - *elem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->disabled_element_set.offset); + *elem = (lmm_element_t)xbt_swag_getNext(*elem, disabled_element_set.offset); } } if (*elem) @@ -559,14 +436,13 @@ lmm_variable_t lmm_get_var_from_cnst(lmm_system_t /*sys*/, lmm_constraint_t cnst //if we modify the swag between calls, normal version may loop forever //this safe version ensures that we browse the swag elements only once -lmm_variable_t lmm_get_var_from_cnst_safe(lmm_system_t /*sys*/, lmm_constraint_t cnst, lmm_element_t * elem, - lmm_element_t * nextelem, int * numelem) +lmm_variable_t s_lmm_constraint_t::get_variable_safe(lmm_element_t* elem, lmm_element_t* nextelem, int* numelem) const { if (*elem == nullptr) { - *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->enabled_element_set)); - *numelem = xbt_swag_size(&(cnst->enabled_element_set))+xbt_swag_size(&(cnst->disabled_element_set))-1; + *elem = (lmm_element_t)xbt_swag_getFirst(&enabled_element_set); + *numelem = xbt_swag_size(&enabled_element_set) + xbt_swag_size(&disabled_element_set) - 1; if (*elem == nullptr) - *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set)); + *elem = (lmm_element_t)xbt_swag_getFirst(&disabled_element_set); }else{ *elem = *nextelem; if(*numelem>0){ @@ -576,24 +452,19 @@ lmm_variable_t lmm_get_var_from_cnst_safe(lmm_system_t /*sys*/, lmm_constraint_t } if (*elem){ //elem is not null, so we carry on - if(xbt_swag_belongs(*elem,&(cnst->enabled_element_set))){ + if (xbt_swag_belongs(*elem, &enabled_element_set)) { //Look at enabled_element_set, and jump to disabled_element_set when finished - *nextelem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->enabled_element_set.offset); + *nextelem = (lmm_element_t)xbt_swag_getNext(*elem, enabled_element_set.offset); if (*nextelem == nullptr) - *nextelem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set)); + *nextelem = (lmm_element_t)xbt_swag_getFirst(&disabled_element_set); } else { - *nextelem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->disabled_element_set.offset); + *nextelem = (lmm_element_t)xbt_swag_getNext(*elem, disabled_element_set.offset); } return (*elem)->variable; }else return nullptr; } -void *lmm_constraint_id(lmm_constraint_t cnst) -{ - return cnst->id; -} - void *lmm_variable_id(lmm_variable_t var) { return var->id; @@ -631,13 +502,13 @@ static inline void saturated_variable_set_update(s_lmm_constraint_light_t* cnst_ } } -void lmm_print(lmm_system_t sys) +void s_lmm_system_t::print() { std::string buf = std::string("MAX-MIN ( "); void* _var; /* Printing Objective */ - xbt_swag_t var_list = &(sys->variable_set); + xbt_swag_t var_list = &variable_set; xbt_swag_foreach(_var, var_list) { lmm_variable_t var = (lmm_variable_t)_var; buf = buf + "'" + std::to_string(var->id_int) + "'(" + std::to_string(var->sharing_weight) + ") "; @@ -649,7 +520,7 @@ void lmm_print(lmm_system_t sys) XBT_DEBUG("Constraints"); /* Printing Constraints */ void* _cnst; - xbt_swag_t cnst_list = &(sys->active_constraint_set); + xbt_swag_t cnst_list = &active_constraint_set; xbt_swag_foreach(_cnst, cnst_list) { lmm_constraint_t cnst = (lmm_constraint_t)_cnst; double sum = 0.0; @@ -704,7 +575,7 @@ void lmm_print(lmm_system_t sys) } } -void lmm_solve(lmm_system_t sys) +void s_lmm_system_t::solve() { void* _cnst; void* _cnst_next; @@ -712,15 +583,15 @@ void lmm_solve(lmm_system_t sys) double min_usage = -1; double min_bound = -1; - if (not sys->modified) + if (not modified) return; - XBT_IN("(sys=%p)", sys); + XBT_IN("(sys=%p)", this); /* Compute Usage and store the variables that reach the maximum. If selective_update_active is true, only constraints * that changed are considered. Otherwise all constraints with active actions are considered. */ - xbt_swag_t cnst_list = sys->selective_update_active ? &(sys->modified_constraint_set) : &(sys->active_constraint_set); + xbt_swag_t cnst_list = selective_update_active ? &modified_constraint_set : &active_constraint_set; XBT_DEBUG("Active constraints : %d", xbt_swag_size(cnst_list)); /* Init: Only modified code portions: reset the value of active variables */ @@ -758,12 +629,12 @@ void lmm_solve(lmm_system_t sys) make_elem_active(elem); simgrid::surf::Action *action = static_cast(elem->variable->id); - if (sys->keep_track && not action->is_linked()) - sys->keep_track->push_back(*action); + if (keep_track && not action->is_linked()) + keep_track->push_back(*action); } } XBT_DEBUG("Constraint '%d' usage: %f remaining: %f concurrency: %i<=%i<=%i", cnst->id_int, cnst->usage, - cnst->remaining,cnst->concurrency_current,cnst->concurrency_maximum,cnst->concurrency_limit); + cnst->remaining, cnst->concurrency_current, cnst->concurrency_maximum, cnst->get_concurrency_limit()); /* Saturated constraints update */ if(cnst->usage > 0) { @@ -777,12 +648,12 @@ void lmm_solve(lmm_system_t sys) } } - saturated_variable_set_update( cnst_light_tab, saturated_constraint_set, sys); + saturated_variable_set_update(cnst_light_tab, saturated_constraint_set, this); /* Saturated variables update */ do { /* Fix the variables that have to be */ - xbt_swag_t var_list = &(sys->saturated_variable_set); + xbt_swag_t var_list = &saturated_variable_set; void* _var; lmm_variable_t var = nullptr; xbt_swag_foreach(_var, var_list) { @@ -896,24 +767,29 @@ void lmm_solve(lmm_system_t sys) &min_usage); } - saturated_variable_set_update(cnst_light_tab, saturated_constraint_set, sys); + saturated_variable_set_update(cnst_light_tab, saturated_constraint_set, this); } while (cnst_light_num > 0); - sys->modified = 0; - if (sys->selective_update_active) - lmm_remove_all_modified_set(sys); + modified = 0; + if (selective_update_active) + remove_all_modified_set(); if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) { - lmm_print(sys); + print(); } - lmm_check_concurrency(sys); + check_concurrency(); delete[] cnst_light_tab; XBT_OUT(); } +void lmm_solve(lmm_system_t sys) +{ + sys->solve(); +} + /** \brief Attribute the value bound to var->bound. * * \param sys the lmm_system_t @@ -923,38 +799,28 @@ void lmm_solve(lmm_system_t sys) * Makes var->bound equal to bound. Whenever this function is called a change is signed in the system. To * avoid false system changing detection it is a good idea to test (bound != 0) before calling it. */ -void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var, double bound) +void s_lmm_system_t::update_variable_bound(lmm_variable_t var, double bound) { - sys->modified = 1; + modified = 1; var->bound = bound; if (not var->cnsts.empty()) - lmm_update_modified_set(sys, var->cnsts[0].constraint); -} - -int lmm_concurrency_slack(lmm_constraint_t cnstr){ - //FIXME MARTIN: Replace by infinite value std::numeric_limits::(max)(), or something better within Simgrid? - if(cnstr->concurrency_limit<0) - return 666; - - return cnstr->concurrency_limit - cnstr->concurrency_current; + update_modified_set(var->cnsts[0].constraint); } /** \brief Measure the minimum concurrency slack across all constraints where the given var is involved */ -int lmm_cnstrs_min_concurrency_slack(lmm_variable_t var){ +int lmm_cnstrs_min_concurrency_slack(lmm_variable_t var) +{ int minslack = std::numeric_limits::max(); for (s_lmm_element_t const& elem : var->cnsts) { - int slack = lmm_concurrency_slack(elem.constraint); - - //This is only an optimization, to avoid looking at more constraints when slack is already zero - //Disable it when debugging to let lmm_concurrency_slack catch nasty things - if (not slack && not XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) - return 0; - - if(minslack>slack) - minslack=slack; + int slack = elem.constraint->get_concurrency_slack(); + if (slack < minslack) { + // This is only an optimization, to avoid looking at more constraints when slack is already zero + if (slack == 0) + return 0; + minslack = slack; + } } - return minslack; } @@ -967,41 +833,43 @@ int lmm_can_enable_var(lmm_variable_t var){ } //Small remark: In this implementation of lmm_enable_var and lmm_disable_var, we will meet multiple times with var when -// running lmm_update_modified_set. -//A priori not a big performance issue, but we might do better by calling lmm_update_modified_set within the for loops +// running sys->update_modified_set. +// A priori not a big performance issue, but we might do better by calling sys->update_modified_set within the for loops // (after doing the first for enabling==1, and before doing the last for disabling==1) -void lmm_enable_var(lmm_system_t sys, lmm_variable_t var){ - xbt_assert(lmm_can_enable_var(var)); +void s_lmm_system_t::enable_var(lmm_variable_t var) +{ + xbt_assert(not XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug) || lmm_can_enable_var(var)); var->sharing_weight = var->staged_weight; var->staged_weight = 0; - // Enabling the variable, move to var to list head. Subtlety is: here, we need to call lmm_update_modified_set AFTER + // Enabling the variable, move to var to list head. Subtlety is: here, we need to call update_modified_set AFTER // moving at least one element of var. - xbt_swag_remove(var, &(sys->variable_set)); - xbt_swag_insert_at_head(var, &(sys->variable_set)); + xbt_swag_remove(var, &variable_set); + xbt_swag_insert_at_head(var, &variable_set); for (s_lmm_element_t& elem : var->cnsts) { xbt_swag_remove(&elem, &(elem.constraint->disabled_element_set)); xbt_swag_insert_at_head(&elem, &(elem.constraint->enabled_element_set)); lmm_increase_concurrency(&elem); } if (not var->cnsts.empty()) - lmm_update_modified_set(sys, var->cnsts[0].constraint); + update_modified_set(var->cnsts[0].constraint); - //When used within lmm_on_disabled_var, we would get an assertion fail, because transiently there can be variables + // When used within on_disabled_var, we would get an assertion fail, because transiently there can be variables // that are staged and could be activated. - //Anyway, caller functions all call lmm_check_concurrency() in the end. + // Anyway, caller functions all call check_concurrency() in the end. } -void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){ +void s_lmm_system_t::disable_var(lmm_variable_t var) +{ xbt_assert(not var->staged_weight, "Staged weight should have been cleared"); - // Disabling the variable, move to var to list tail. Subtlety is: here, we need to call lmm_update_modified_set BEFORE - // moving the last element of var. - xbt_swag_remove(var, &(sys->variable_set)); - xbt_swag_insert_at_tail(var, &(sys->variable_set)); + // Disabling the variable, move to var to list tail. Subtlety is: here, we need to call update_modified_set + // BEFORE moving the last element of var. + xbt_swag_remove(var, &variable_set); + xbt_swag_insert_at_tail(var, &variable_set); if (not var->cnsts.empty()) - lmm_update_modified_set(sys, var->cnsts[0].constraint); + update_modified_set(var->cnsts[0].constraint); for (s_lmm_element_t& elem : var->cnsts) { xbt_swag_remove(&elem, &(elem.constraint->enabled_element_set)); xbt_swag_insert_at_tail(&elem, &(elem.constraint->disabled_element_set)); @@ -1014,7 +882,7 @@ void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){ var->sharing_weight = 0.0; var->staged_weight=0.0; var->value = 0.0; - lmm_check_concurrency(sys); + check_concurrency(); } /* /brief Find variables that can be enabled and enable them. @@ -1024,9 +892,9 @@ void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){ * If yes, check that none of the constraints that this variable is involved in is at the limit of its concurrency * And then add it to enabled variables */ -void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr){ - - if(cnstr->concurrency_limit<0) +void s_lmm_system_t::on_disabled_var(lmm_constraint_t cnstr) +{ + if (cnstr->get_concurrency_limit() < 0) return; int numelem = xbt_swag_size(&(cnstr->disabled_element_set)); @@ -1040,17 +908,15 @@ void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr){ lmm_element_t nextelem = (lmm_element_t)xbt_swag_getNext(elem, cnstr->disabled_element_set.offset); - if (elem->variable->staged_weight>0 ){ + if (elem->variable->staged_weight > 0 && lmm_can_enable_var(elem->variable)) { //Found a staged variable //TODOLATER: Add random timing function to model reservation protocol fuzziness? Then how to make sure that //staged variables will eventually be called? - if(lmm_can_enable_var(elem->variable)){ - lmm_enable_var(sys,elem->variable); - } + enable_var(elem->variable); } - xbt_assert(cnstr->concurrency_current<=cnstr->concurrency_limit,"Concurrency overflow!"); - if(cnstr->concurrency_current==cnstr->concurrency_limit) + xbt_assert(cnstr->concurrency_current <= cnstr->get_concurrency_limit(), "Concurrency overflow!"); + if (cnstr->concurrency_current == cnstr->get_concurrency_limit()) break; elem = nextelem; @@ -1058,13 +924,13 @@ void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr){ //We could get an assertion fail, because transiently there can be variables that are staged and could be activated. //And we need to go through all constraints of the disabled var before getting back a coherent state. - //Anyway, caller functions all call lmm_check_concurrency() in the end. + // Anyway, caller functions all call check_concurrency() in the end. } /* \brief update the weight of a variable, and enable/disable it. * @return Returns whether a change was made */ -void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var, double weight) +void s_lmm_system_t::update_variable_weight(lmm_variable_t var, double weight) { xbt_assert(weight>=0,"Variable weight should not be negative!"); @@ -1074,9 +940,9 @@ void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var, double wei int enabling_var = (weight > 0 && var->sharing_weight <= 0); int disabling_var = (weight <= 0 && var->sharing_weight > 0); - XBT_IN("(sys=%p, var=%p, weight=%f)", sys, var, weight); + XBT_IN("(sys=%p, var=%p, weight=%f)", this, var, weight); - sys->modified = 1; + modified = 1; //Are we enabling this variable? if (enabling_var){ @@ -1088,15 +954,15 @@ void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var, double wei return; } XBT_DEBUG("Enabling var with min concurrency slack %i", minslack); - lmm_enable_var(sys,var); + enable_var(var); } else if (disabling_var){ //Are we disabling this variable? - lmm_disable_var(sys,var); + disable_var(var); } else { var->sharing_weight = weight; } - lmm_check_concurrency(sys); + check_concurrency(); XBT_OUT(); } @@ -1106,28 +972,13 @@ double lmm_get_variable_weight(lmm_variable_t var) return var->sharing_weight; } -void lmm_update_constraint_bound(lmm_system_t sys, lmm_constraint_t cnst, double bound) +void s_lmm_system_t::update_constraint_bound(lmm_constraint_t cnst, double bound) { - sys->modified = 1; - lmm_update_modified_set(sys, cnst); + modified = 1; + update_modified_set(cnst); cnst->bound = bound; } -int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst) -{ - return xbt_swag_belongs(cnst, &(sys->active_constraint_set)); -} - -inline lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t sys) -{ - return (lmm_constraint_t)xbt_swag_getFirst(&(sys->active_constraint_set)); -} - -inline lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys, lmm_constraint_t cnst) -{ - return (lmm_constraint_t)xbt_swag_getNext(cnst, (sys->active_constraint_set).offset); -} - /** \brief Update the constraint set propagating recursively to other constraints so the system should not be entirely * computed. * @@ -1137,53 +988,48 @@ inline lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t sys, lmm_con * A recursive algorithm to optimize the system recalculation selecting only constraints that have changed. Each * constraint change is propagated to the list of constraints for each variable. */ -static void lmm_update_modified_set_rec(lmm_system_t sys, lmm_constraint_t cnst) +void s_lmm_system_t::update_modified_set_rec(lmm_constraint_t cnst) { void* _elem; - //TODOLATER: Why lmm_modified_set has been changed in git version 2392B5157...? Looks equivalent logically and less obvious.. xbt_swag_foreach(_elem, &cnst->enabled_element_set) { lmm_variable_t var = ((lmm_element_t)_elem)->variable; for (s_lmm_element_t const& elem : var->cnsts) { - if (var->visited == sys->visited_counter) + if (var->visited == visited_counter) break; - if (elem.constraint != cnst && not xbt_swag_belongs(elem.constraint, &sys->modified_constraint_set)) { - xbt_swag_insert(elem.constraint, &sys->modified_constraint_set); - lmm_update_modified_set_rec(sys, elem.constraint); + if (elem.constraint != cnst && not xbt_swag_belongs(elem.constraint, &modified_constraint_set)) { + xbt_swag_insert(elem.constraint, &modified_constraint_set); + update_modified_set_rec(elem.constraint); } } //var will be ignored in later visits as long as sys->visited_counter does not move - var->visited = sys->visited_counter; + var->visited = visited_counter; } } -static void lmm_update_modified_set(lmm_system_t sys, lmm_constraint_t cnst) +void s_lmm_system_t::update_modified_set(lmm_constraint_t cnst) { /* nothing to do if selective update isn't active */ - if (sys->selective_update_active && not xbt_swag_belongs(cnst, &sys->modified_constraint_set)) { - xbt_swag_insert(cnst, &sys->modified_constraint_set); - lmm_update_modified_set_rec(sys, cnst); + if (selective_update_active && not xbt_swag_belongs(cnst, &modified_constraint_set)) { + xbt_swag_insert(cnst, &modified_constraint_set); + update_modified_set_rec(cnst); } } -/** \brief Remove all constraints of the modified_constraint_set. - * - * \param sys the lmm_system_t - */ -static void lmm_remove_all_modified_set(lmm_system_t sys) +void s_lmm_system_t::remove_all_modified_set() { - // We cleverly un-flag all variables just by incrementing sys->visited_counter - // In effect, the var->visited value will no more be equal to sys->visited counter + // We cleverly un-flag all variables just by incrementing visited_counter + // In effect, the var->visited value will no more be equal to visited counter // To be clean, when visited counter has wrapped around, we force these var->visited values so that variables that // were in the modified a long long time ago are not wrongly skipped here, which would lead to very nasty bugs // (i.e. not readibily reproducible, and requiring a lot of run time before happening). - if (++sys->visited_counter == 1) { + if (++visited_counter == 1) { /* the counter wrapped around, reset each variable->visited */ - void *_var; - xbt_swag_foreach(_var, &sys->variable_set) + void *_var; + xbt_swag_foreach(_var, &variable_set) ((lmm_variable_t)_var)->visited = 0; } - xbt_swag_reset(&sys->modified_constraint_set); + xbt_swag_reset(&modified_constraint_set); } /** @@ -1197,16 +1043,17 @@ static void lmm_remove_all_modified_set(lmm_system_t sys) * * \param cnst the lmm_constraint_t associated to the resource */ -double lmm_constraint_get_usage(lmm_constraint_t cnst) { +double s_lmm_constraint_t::get_usage() const +{ double usage = 0.0; - xbt_swag_t elem_list = &(cnst->enabled_element_set); + const_xbt_swag_t elem_list = &enabled_element_set; void* _elem; xbt_swag_foreach(_elem, elem_list) { lmm_element_t elem = (lmm_element_t)_elem; if (elem->consumption_weight > 0) { - if (cnst->sharing_policy) + if (sharing_policy) usage += elem->consumption_weight * elem->variable->value; else if (usage < elem->consumption_weight * elem->variable->value) usage = std::max(usage, elem->consumption_weight * elem->variable->value); @@ -1215,9 +1062,10 @@ double lmm_constraint_get_usage(lmm_constraint_t cnst) { return usage; } -int lmm_constraint_get_variable_amount(lmm_constraint_t cnst) { +int s_lmm_constraint_t::get_variable_amount() const +{ int usage = 0; - xbt_swag_t elem_list = &(cnst->enabled_element_set); + const_xbt_swag_t elem_list = &enabled_element_set; void *_elem; xbt_swag_foreach(_elem, elem_list) {