Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
230f3175c5b1cc0af9106fa3b6f6104ad5adbff4
[simgrid.git] / src / kernel / lmm / maxmin.cpp
1 /* Copyright (c) 2004-2019. The SimGrid Team. All rights reserved.          */
2
3 /* This program is free software; you can redistribute it and/or modify it
4  * under the terms of the license (GNU LGPL) which comes with this package. */
5
6 #include "src/kernel/lmm/maxmin.hpp"
7 #include "src/surf/surf_interface.hpp"
8 #include "xbt/backtrace.hpp"
9
10 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_maxmin, surf, "Logging specific to SURF (maxmin)");
11
12 double sg_maxmin_precision = 0.00001; /* Change this with --cfg=maxmin/precision:VALUE */
13 double sg_surf_precision   = 0.00001; /* Change this with --cfg=surf/precision:VALUE */
14 int sg_concurrency_limit   = -1;      /* Change this with --cfg=maxmin/concurrency-limit:VALUE */
15
16 namespace simgrid {
17 namespace kernel {
18 namespace lmm {
19
20 typedef std::vector<int> dyn_light_t;
21
22 int Variable::Global_debug_id   = 1;
23 int Constraint::Global_debug_id = 1;
24
25 System* make_new_maxmin_system(bool selective_update)
26 {
27   return new System(selective_update);
28 }
29
30 int Element::get_concurrency() const
31 {
32   // Ignore element with weight less than one (e.g. cross-traffic)
33   return (consumption_weight >= 1) ? 1 : 0;
34   // There are other alternatives, but they will change the behaviour of the model..
35   // So do not use it unless you want to make a new model.
36   // If you do, remember to change the variables concurrency share to reflect it.
37   // Potential examples are:
38   // return (elem->weight>0)?1:0;//Include element as soon  as weight is non-zero
39   // return (int)ceil(elem->weight);//Include element as the rounded-up integer value of the element weight
40 }
41
42 void Element::decrease_concurrency()
43 {
44   xbt_assert(constraint->concurrency_current >= get_concurrency());
45   constraint->concurrency_current -= get_concurrency();
46 }
47
48 void Element::increase_concurrency()
49 {
50   constraint->concurrency_current += get_concurrency();
51
52   if (constraint->concurrency_current > constraint->concurrency_maximum)
53     constraint->concurrency_maximum = constraint->concurrency_current;
54
55   xbt_assert(constraint->get_concurrency_limit() < 0 ||
56                  constraint->concurrency_current <= constraint->get_concurrency_limit(),
57              "Concurrency limit overflow!");
58 }
59
60 void System::check_concurrency() const
61 {
62   // These checks are very expensive, so do them only if we want to debug SURF LMM
63   if (not XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug))
64     return;
65
66   for (Constraint const& cnst : constraint_set) {
67     int concurrency       = 0;
68     for (Element const& elem : cnst.enabled_element_set) {
69       xbt_assert(elem.variable->sharing_weight > 0);
70       concurrency += elem.get_concurrency();
71     }
72
73     for (Element const& elem : cnst.disabled_element_set) {
74       // We should have staged variables only if concurrency is reached in some constraint
75       xbt_assert(cnst.get_concurrency_limit() < 0 || elem.variable->staged_weight == 0 ||
76                      elem.variable->get_min_concurrency_slack() < elem.variable->concurrency_share,
77                  "should not have staged variable!");
78     }
79
80     xbt_assert(cnst.get_concurrency_limit() < 0 || cnst.get_concurrency_limit() >= concurrency,
81                "concurrency check failed!");
82     xbt_assert(cnst.concurrency_current == concurrency, "concurrency_current is out-of-date!");
83   }
84
85   // Check that for each variable, all corresponding elements are in the same state (i.e. same element sets)
86   for (Variable const& var : variable_set) {
87     if (var.cnsts.empty())
88       continue;
89
90     const Element& elem    = var.cnsts[0];
91     int belong_to_enabled  = elem.enabled_element_set_hook.is_linked();
92     int belong_to_disabled = elem.disabled_element_set_hook.is_linked();
93     int belong_to_active   = elem.active_element_set_hook.is_linked();
94
95     for (Element const& elem2 : var.cnsts) {
96       xbt_assert(belong_to_enabled == elem2.enabled_element_set_hook.is_linked(),
97                  "Variable inconsistency (1): enabled_element_set");
98       xbt_assert(belong_to_disabled == elem2.disabled_element_set_hook.is_linked(),
99                  "Variable inconsistency (2): disabled_element_set");
100       xbt_assert(belong_to_active == elem2.active_element_set_hook.is_linked(),
101                  "Variable inconsistency (3): active_element_set");
102     }
103   }
104 }
105
106 void System::var_free(Variable* var)
107 {
108   XBT_IN("(sys=%p, var=%p)", this, var);
109   modified_ = true;
110
111   // TODOLATER Can do better than that by leaving only the variable in only one enabled_element_set, call
112   // update_modified_set, and then remove it..
113   if (not var->cnsts.empty())
114     update_modified_set(var->cnsts[0].constraint);
115
116   for (Element& elem : var->cnsts) {
117     if (var->sharing_weight > 0)
118       elem.decrease_concurrency();
119     if (elem.enabled_element_set_hook.is_linked())
120       simgrid::xbt::intrusive_erase(elem.constraint->enabled_element_set, elem);
121     if (elem.disabled_element_set_hook.is_linked())
122       simgrid::xbt::intrusive_erase(elem.constraint->disabled_element_set, elem);
123     if (elem.active_element_set_hook.is_linked())
124       simgrid::xbt::intrusive_erase(elem.constraint->active_element_set, elem);
125     int nelements = elem.constraint->enabled_element_set.size() + elem.constraint->disabled_element_set.size();
126     if (nelements == 0)
127       make_constraint_inactive(elem.constraint);
128     else
129       on_disabled_var(elem.constraint);
130   }
131
132   var->cnsts.clear();
133
134   check_concurrency();
135
136   xbt_mallocator_release(variable_mallocator_, var);
137   XBT_OUT();
138 }
139
140 System::System(bool selective_update) : selective_update_active(selective_update)
141 {
142   XBT_DEBUG("Setting selective_update_active flag to %d", selective_update_active);
143
144   if (selective_update)
145     modified_set_ = new kernel::resource::Action::ModifiedSet();
146 }
147
148 System::~System()
149 {
150   Variable* var;
151   Constraint* cnst;
152
153   while ((var = extract_variable())) {
154     auto demangled = simgrid::xbt::demangle(typeid(*var->id).name());
155     XBT_WARN("Probable bug: a %s variable (#%d) not removed before the LMM system destruction.", demangled.get(),
156              var->id_int);
157     var_free(var);
158   }
159   while ((cnst = extract_constraint()))
160     cnst_free(cnst);
161
162   xbt_mallocator_free(variable_mallocator_);
163   delete modified_set_;
164 }
165
166 void System::cnst_free(Constraint* cnst)
167 {
168   make_constraint_inactive(cnst);
169   delete cnst;
170 }
171
172 Constraint::Constraint(void* id_value, double bound_value) : bound(bound_value), id(id_value)
173 {
174   id_int = Global_debug_id++;
175
176   remaining           = 0.0;
177   usage               = 0.0;
178   concurrency_limit   = sg_concurrency_limit;
179   concurrency_current = 0;
180   concurrency_maximum = 0;
181   sharing_policy      = s4u::Link::SharingPolicy::SHARED;
182
183   lambda     = 0.0;
184   new_lambda = 0.0;
185   cnst_light = nullptr;
186 }
187
188 Constraint* System::constraint_new(void* id, double bound_value)
189 {
190   Constraint* cnst = new Constraint(id, bound_value);
191   insert_constraint(cnst);
192   return cnst;
193 }
194
195 void* System::variable_mallocator_new_f()
196 {
197   return new Variable;
198 }
199
200 void System::variable_mallocator_free_f(void* var)
201 {
202   delete static_cast<Variable*>(var);
203 }
204
205 Variable* System::variable_new(resource::Action* id, double sharing_weight, double bound, int number_of_constraints)
206 {
207   XBT_IN("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)", this, id, sharing_weight, bound, number_of_constraints);
208
209   Variable* var = static_cast<Variable*>(xbt_mallocator_get(variable_mallocator_));
210   var->initialize(id, sharing_weight, bound, number_of_constraints, visited_counter_ - 1);
211   if (sharing_weight)
212     variable_set.push_front(*var);
213   else
214     variable_set.push_back(*var);
215
216   XBT_OUT(" returns %p", var);
217   return var;
218 }
219
220 void System::variable_free(Variable* var)
221 {
222   remove_variable(var);
223   var_free(var);
224 }
225
226 void System::expand(Constraint* cnst, Variable* var, double consumption_weight)
227 {
228   modified_ = true;
229
230   // Check if this variable already has an active element in this constraint
231   // If it does, substract it from the required slack
232   int current_share = 0;
233   if (var->concurrency_share > 1) {
234     for (Element& elem : var->cnsts) {
235       if (elem.constraint == cnst && elem.enabled_element_set_hook.is_linked())
236         current_share += elem.get_concurrency();
237     }
238   }
239
240   // Check if we need to disable the variable
241   if (var->sharing_weight > 0 && var->concurrency_share - current_share > cnst->get_concurrency_slack()) {
242     double weight = var->sharing_weight;
243     disable_var(var);
244     for (Element const& elem : var->cnsts)
245       on_disabled_var(elem.constraint);
246     consumption_weight = 0;
247     var->staged_weight = weight;
248     xbt_assert(not var->sharing_weight);
249   }
250
251   xbt_assert(var->cnsts.size() < var->cnsts.capacity(), "Too much constraints");
252
253   var->cnsts.resize(var->cnsts.size() + 1);
254   Element& elem = var->cnsts.back();
255
256   elem.consumption_weight = consumption_weight;
257   elem.constraint         = cnst;
258   elem.variable           = var;
259
260   if (var->sharing_weight) {
261     elem.constraint->enabled_element_set.push_front(elem);
262     elem.increase_concurrency();
263   } else
264     elem.constraint->disabled_element_set.push_back(elem);
265
266   if (not selective_update_active) {
267     make_constraint_active(cnst);
268   } else if (elem.consumption_weight > 0 || var->sharing_weight > 0) {
269     make_constraint_active(cnst);
270     update_modified_set(cnst);
271     // TODOLATER: Why do we need this second call?
272     if (var->cnsts.size() > 1)
273       update_modified_set(var->cnsts[0].constraint);
274   }
275
276   check_concurrency();
277 }
278
279 void System::expand_add(Constraint* cnst, Variable* var, double value)
280 {
281   modified_ = true;
282
283   check_concurrency();
284
285   // BEWARE: In case you have multiple elements in one constraint, this will always add value to the first element.
286   auto elem_it =
287       std::find_if(begin(var->cnsts), end(var->cnsts), [&cnst](Element const& x) { return x.constraint == cnst; });
288   if (elem_it != end(var->cnsts)) {
289     Element& elem = *elem_it;
290     if (var->sharing_weight)
291       elem.decrease_concurrency();
292
293     if (cnst->sharing_policy != s4u::Link::SharingPolicy::FATPIPE)
294       elem.consumption_weight += value;
295     else
296       elem.consumption_weight = std::max(elem.consumption_weight, value);
297
298     // We need to check that increasing value of the element does not cross the concurrency limit
299     if (var->sharing_weight) {
300       if (cnst->get_concurrency_slack() < elem.get_concurrency()) {
301         double weight = var->sharing_weight;
302         disable_var(var);
303         for (Element const& elem2 : var->cnsts)
304           on_disabled_var(elem2.constraint);
305         var->staged_weight = weight;
306         xbt_assert(not var->sharing_weight);
307       }
308       elem.increase_concurrency();
309     }
310     update_modified_set(cnst);
311   } else
312     expand(cnst, var, value);
313
314   check_concurrency();
315 }
316
317 Variable* Constraint::get_variable(const Element** elem) const
318 {
319   if (*elem == nullptr) {
320     // That is the first call, pick the first element among enabled_element_set (or disabled_element_set if
321     // enabled_element_set is empty)
322     if (not enabled_element_set.empty())
323       *elem = &enabled_element_set.front();
324     else if (not disabled_element_set.empty())
325       *elem = &disabled_element_set.front();
326     else
327       *elem = nullptr;
328   } else {
329     // elem is not null, so we carry on
330     if ((*elem)->enabled_element_set_hook.is_linked()) {
331       // Look at enabled_element_set, and jump to disabled_element_set when finished
332       auto iter = std::next(enabled_element_set.iterator_to(**elem));
333       if (iter != std::end(enabled_element_set))
334         *elem = &*iter;
335       else if (not disabled_element_set.empty())
336         *elem = &disabled_element_set.front();
337       else
338         *elem = nullptr;
339     } else {
340       auto iter = std::next(disabled_element_set.iterator_to(**elem));
341       *elem     = iter != std::end(disabled_element_set) ? &*iter : nullptr;
342     }
343   }
344   if (*elem)
345     return (*elem)->variable;
346   else
347     return nullptr;
348 }
349
350 // if we modify the list between calls, normal version may loop forever
351 // this safe version ensures that we browse the list elements only once
352 Variable* Constraint::get_variable_safe(const Element** elem, const Element** nextelem, int* numelem) const
353 {
354   if (*elem == nullptr) {
355     *numelem = enabled_element_set.size() + disabled_element_set.size() - 1;
356     if (not enabled_element_set.empty())
357       *elem = &enabled_element_set.front();
358     else if (not disabled_element_set.empty())
359       *elem = &disabled_element_set.front();
360     else
361       *elem = nullptr;
362   } else {
363     *elem = *nextelem;
364     if (*numelem > 0) {
365       (*numelem)--;
366     } else
367       return nullptr;
368   }
369   if (*elem) {
370     // elem is not null, so we carry on
371     if ((*elem)->enabled_element_set_hook.is_linked()) {
372       // Look at enabled_element_set, and jump to disabled_element_set when finished
373       auto iter = std::next(enabled_element_set.iterator_to(**elem));
374       if (iter != std::end(enabled_element_set))
375         *nextelem = &*iter;
376       else if (not disabled_element_set.empty())
377         *nextelem = &disabled_element_set.front();
378       else
379         *nextelem = nullptr;
380     } else {
381       auto iter = std::next(disabled_element_set.iterator_to(**elem));
382       *nextelem = iter != std::end(disabled_element_set) ? &*iter : nullptr;
383     }
384     return (*elem)->variable;
385   } else
386     return nullptr;
387 }
388
389 static inline void saturated_constraints_update(double usage, int cnst_light_num, dyn_light_t& saturated_constraints,
390                                                 double* min_usage)
391 {
392   xbt_assert(usage > 0, "Impossible");
393
394   if (*min_usage < 0 || *min_usage > usage) {
395     *min_usage = usage;
396     XBT_HERE(" min_usage=%f (cnst->remaining / cnst->usage =%f)", *min_usage, usage);
397     saturated_constraints.assign(1, cnst_light_num);
398   } else if (*min_usage == usage) {
399     saturated_constraints.emplace_back(cnst_light_num);
400   }
401 }
402
403 static inline void saturated_variable_set_update(ConstraintLight* cnst_light_tab,
404                                                  const dyn_light_t& saturated_constraints, System* sys)
405 {
406   /* Add active variables (i.e. variables that need to be set) from the set of constraints to saturate
407    * (cnst_light_tab)*/
408   for (int const& saturated_cnst : saturated_constraints) {
409     ConstraintLight& cnst = cnst_light_tab[saturated_cnst];
410     for (Element const& elem : cnst.cnst->active_element_set) {
411       // Visiting active_element_set, so, by construction, should never get a zero weight, correct?
412       xbt_assert(elem.variable->sharing_weight > 0);
413       if (elem.consumption_weight > 0 && not elem.variable->saturated_variable_set_hook.is_linked())
414         sys->saturated_variable_set.push_back(*elem.variable);
415     }
416   }
417 }
418
419 template <class ElemList>
420 static void format_element_list(const ElemList& elem_list, s4u::Link::SharingPolicy sharing_policy, double& sum,
421                                 std::string& buf)
422 {
423   for (Element const& elem : elem_list) {
424     buf += std::to_string(elem.consumption_weight) + ".'" + std::to_string(elem.variable->id_int) + "'(" +
425            std::to_string(elem.variable->value) + ")" +
426            (sharing_policy != s4u::Link::SharingPolicy::FATPIPE ? " + " : " , ");
427     if (sharing_policy != s4u::Link::SharingPolicy::FATPIPE)
428       sum += elem.consumption_weight * elem.variable->value;
429     else
430       sum = std::max(sum, elem.consumption_weight * elem.variable->value);
431   }
432 }
433
434 void System::print() const
435 {
436   std::string buf = std::string("MAX-MIN ( ");
437
438   /* Printing Objective */
439   for (Variable const& var : variable_set)
440     buf += "'" + std::to_string(var.id_int) + "'(" + std::to_string(var.sharing_weight) + ") ";
441   buf += ")";
442   XBT_DEBUG("%20s", buf.c_str());
443   buf.clear();
444
445   XBT_DEBUG("Constraints");
446   /* Printing Constraints */
447   for (Constraint const& cnst : active_constraint_set) {
448     double sum            = 0.0;
449     // Show  the enabled variables
450     buf += "\t";
451     buf += cnst.sharing_policy != s4u::Link::SharingPolicy::FATPIPE ? "(" : "max(";
452     format_element_list(cnst.enabled_element_set, cnst.sharing_policy, sum, buf);
453     // TODO: Adding disabled elements only for test compatibility, but do we really want them to be printed?
454     format_element_list(cnst.disabled_element_set, cnst.sharing_policy, sum, buf);
455
456     buf += "0) <= " + std::to_string(cnst.bound) + " ('" + std::to_string(cnst.id_int) + "')";
457
458     if (cnst.sharing_policy == s4u::Link::SharingPolicy::FATPIPE) {
459       buf += " [MAX-Constraint]";
460     }
461     XBT_DEBUG("%s", buf.c_str());
462     buf.clear();
463     xbt_assert(not double_positive(sum - cnst.bound, cnst.bound * sg_maxmin_precision),
464                "Incorrect value (%f is not smaller than %f): %g", sum, cnst.bound, sum - cnst.bound);
465   }
466
467   XBT_DEBUG("Variables");
468   /* Printing Result */
469   for (Variable const& var : variable_set) {
470     if (var.bound > 0) {
471       XBT_DEBUG("'%d'(%f) : %f (<=%f)", var.id_int, var.sharing_weight, var.value, var.bound);
472       xbt_assert(not double_positive(var.value - var.bound, var.bound * sg_maxmin_precision),
473                  "Incorrect value (%f is not smaller than %f", var.value, var.bound);
474     } else {
475       XBT_DEBUG("'%d'(%f) : %f", var.id_int, var.sharing_weight, var.value);
476     }
477   }
478 }
479
480 void System::lmm_solve()
481 {
482   if (modified_) {
483     XBT_IN("(sys=%p)", this);
484     /* Compute Usage and store the variables that reach the maximum. If selective_update_active is true, only
485      * constraints that changed are considered. Otherwise all constraints with active actions are considered.
486      */
487     if (selective_update_active)
488       lmm_solve(modified_constraint_set);
489     else
490       lmm_solve(active_constraint_set);
491     XBT_OUT();
492   }
493 }
494
495 template <class CnstList> void System::lmm_solve(CnstList& cnst_list)
496 {
497   double min_usage = -1;
498   double min_bound = -1;
499
500   XBT_DEBUG("Active constraints : %zu", cnst_list.size());
501   /* Init: Only modified code portions: reset the value of active variables */
502   for (Constraint const& cnst : cnst_list) {
503     for (Element const& elem : cnst.enabled_element_set) {
504       xbt_assert(elem.variable->sharing_weight > 0.0);
505       elem.variable->value = 0.0;
506     }
507   }
508
509   ConstraintLight* cnst_light_tab = new ConstraintLight[cnst_list.size()]();
510   int cnst_light_num              = 0;
511   dyn_light_t saturated_constraints;
512
513   for (Constraint& cnst : cnst_list) {
514     /* INIT: Collect constraints that actually need to be saturated (i.e remaining  and usage are strictly positive)
515      * into cnst_light_tab. */
516     cnst.remaining = cnst.bound;
517     if (not double_positive(cnst.remaining, cnst.bound * sg_maxmin_precision))
518       continue;
519     cnst.usage = 0;
520     for (Element& elem : cnst.enabled_element_set) {
521       xbt_assert(elem.variable->sharing_weight > 0);
522       if (elem.consumption_weight > 0) {
523         if (cnst.sharing_policy != s4u::Link::SharingPolicy::FATPIPE)
524           cnst.usage += elem.consumption_weight / elem.variable->sharing_weight;
525         else if (cnst.usage < elem.consumption_weight / elem.variable->sharing_weight)
526           cnst.usage = elem.consumption_weight / elem.variable->sharing_weight;
527
528         elem.make_active();
529         resource::Action* action = static_cast<resource::Action*>(elem.variable->id);
530         if (modified_set_ && not action->is_within_modified_set())
531           modified_set_->push_back(*action);
532       }
533     }
534     XBT_DEBUG("Constraint '%d' usage: %f remaining: %f concurrency: %i<=%i<=%i", cnst.id_int, cnst.usage,
535               cnst.remaining, cnst.concurrency_current, cnst.concurrency_maximum, cnst.get_concurrency_limit());
536     /* Saturated constraints update */
537
538     if (cnst.usage > 0) {
539       cnst_light_tab[cnst_light_num].cnst                 = &cnst;
540       cnst.cnst_light                                     = &cnst_light_tab[cnst_light_num];
541       cnst_light_tab[cnst_light_num].remaining_over_usage = cnst.remaining / cnst.usage;
542       saturated_constraints_update(cnst_light_tab[cnst_light_num].remaining_over_usage, cnst_light_num,
543                                    saturated_constraints, &min_usage);
544       xbt_assert(not cnst.active_element_set.empty(),
545                  "There is no sense adding a constraint that has no active element!");
546       cnst_light_num++;
547     }
548   }
549
550   saturated_variable_set_update(cnst_light_tab, saturated_constraints, this);
551
552   /* Saturated variables update */
553   do {
554     /* Fix the variables that have to be */
555     auto& var_list = saturated_variable_set;
556     for (Variable const& var : var_list) {
557       if (var.sharing_weight <= 0.0)
558         DIE_IMPOSSIBLE;
559       /* First check if some of these variables could reach their upper bound and update min_bound accordingly. */
560       XBT_DEBUG("var=%d, var.bound=%f, var.weight=%f, min_usage=%f, var.bound*var.weight=%f", var.id_int, var.bound,
561                 var.sharing_weight, min_usage, var.bound * var.sharing_weight);
562       if ((var.bound > 0) && (var.bound * var.sharing_weight < min_usage)) {
563         if (min_bound < 0)
564           min_bound = var.bound * var.sharing_weight;
565         else
566           min_bound = std::min(min_bound, (var.bound * var.sharing_weight));
567         XBT_DEBUG("Updated min_bound=%f", min_bound);
568       }
569     }
570
571     while (not var_list.empty()) {
572       Variable& var = var_list.front();
573       if (min_bound < 0) {
574         // If no variable could reach its bound, deal iteratively the constraints usage ( at worst one constraint is
575         // saturated at each cycle)
576         var.value = min_usage / var.sharing_weight;
577         XBT_DEBUG("Setting var (%d) value to %f\n", var.id_int, var.value);
578       } else {
579         // If there exist a variable that can reach its bound, only update it (and other with the same bound) for now.
580         if (double_equals(min_bound, var.bound * var.sharing_weight, sg_maxmin_precision)) {
581           var.value = var.bound;
582           XBT_DEBUG("Setting %p (%d) value to %f\n", &var, var.id_int, var.value);
583         } else {
584           // Variables which bound is different are not considered for this cycle, but they will be afterwards.
585           XBT_DEBUG("Do not consider %p (%d) \n", &var, var.id_int);
586           var_list.pop_front();
587           continue;
588         }
589       }
590       XBT_DEBUG("Min usage: %f, Var(%d).weight: %f, Var(%d).value: %f ", min_usage, var.id_int, var.sharing_weight,
591                 var.id_int, var.value);
592
593       /* Update the usage of contraints where this variable is involved */
594       for (Element& elem : var.cnsts) {
595         Constraint* cnst = elem.constraint;
596         if (cnst->sharing_policy != s4u::Link::SharingPolicy::FATPIPE) {
597           // Remember: shared constraints require that sum(elem.value * var.value) < cnst->bound
598           double_update(&(cnst->remaining), elem.consumption_weight * var.value, cnst->bound * sg_maxmin_precision);
599           double_update(&(cnst->usage), elem.consumption_weight / var.sharing_weight, sg_maxmin_precision);
600           // If the constraint is saturated, remove it from the set of active constraints (light_tab)
601           if (not double_positive(cnst->usage, sg_maxmin_precision) ||
602               not double_positive(cnst->remaining, cnst->bound * sg_maxmin_precision)) {
603             if (cnst->cnst_light) {
604               int index = (cnst->cnst_light - cnst_light_tab);
605               XBT_DEBUG("index: %d \t cnst_light_num: %d \t || usage: %f remaining: %f bound: %f  ", index,
606                         cnst_light_num, cnst->usage, cnst->remaining, cnst->bound);
607               cnst_light_tab[index]                  = cnst_light_tab[cnst_light_num - 1];
608               cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index];
609               cnst_light_num--;
610               cnst->cnst_light = nullptr;
611             }
612           } else {
613             cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage;
614           }
615           elem.make_inactive();
616         } else {
617           // Remember: non-shared constraints only require that max(elem.value * var.value) < cnst->bound
618           cnst->usage = 0.0;
619           elem.make_inactive();
620           for (Element& elem2 : cnst->enabled_element_set) {
621             xbt_assert(elem2.variable->sharing_weight > 0);
622             if (elem2.variable->value > 0)
623               continue;
624             if (elem2.consumption_weight > 0)
625               cnst->usage = std::max(cnst->usage, elem2.consumption_weight / elem2.variable->sharing_weight);
626           }
627           // If the constraint is saturated, remove it from the set of active constraints (light_tab)
628           if (not double_positive(cnst->usage, sg_maxmin_precision) ||
629               not double_positive(cnst->remaining, cnst->bound * sg_maxmin_precision)) {
630             if (cnst->cnst_light) {
631               int index = (cnst->cnst_light - cnst_light_tab);
632               XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p "
633                         "\t cnst_light_tab: %p usage: %f remaining: %f bound: %f  ",
634                         index, cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab, cnst->usage, cnst->remaining,
635                         cnst->bound);
636               cnst_light_tab[index]                  = cnst_light_tab[cnst_light_num - 1];
637               cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index];
638               cnst_light_num--;
639               cnst->cnst_light = nullptr;
640             }
641           } else {
642             cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage;
643             xbt_assert(not cnst->active_element_set.empty(),
644                        "Should not keep a maximum constraint that has no active"
645                        " element! You want to check the maxmin precision and possible rounding effects.");
646           }
647         }
648       }
649       var_list.pop_front();
650     }
651
652     /* Find out which variables reach the maximum */
653     min_usage = -1;
654     min_bound = -1;
655     saturated_constraints.clear();
656     int pos;
657     for (pos = 0; pos < cnst_light_num; pos++) {
658       xbt_assert(not cnst_light_tab[pos].cnst->active_element_set.empty(),
659                  "Cannot saturate more a constraint that has"
660                  " no active element! You may want to change the maxmin precision (--cfg=maxmin/precision:<new_value>)"
661                  " because of possible rounding effects.\n\tFor the record, the usage of this constraint is %g while "
662                  "the maxmin precision to which it is compared is %g.\n\tThe usage of the previous constraint is %g.",
663                  cnst_light_tab[pos].cnst->usage, sg_maxmin_precision, cnst_light_tab[pos - 1].cnst->usage);
664       saturated_constraints_update(cnst_light_tab[pos].remaining_over_usage, pos, saturated_constraints, &min_usage);
665     }
666
667     saturated_variable_set_update(cnst_light_tab, saturated_constraints, this);
668
669   } while (cnst_light_num > 0);
670
671   modified_ = false;
672   if (selective_update_active)
673     remove_all_modified_set();
674
675   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
676     print();
677   }
678
679   check_concurrency();
680
681   delete[] cnst_light_tab;
682 }
683
684 /** @brief Attribute the value bound to var->bound.
685  *
686  *  @param var the Variable*
687  *  @param bound the new bound to associate with var
688  *
689  *  Makes var->bound equal to bound. Whenever this function is called a change is  signed in the system. To
690  *  avoid false system changing detection it is a good idea to test (bound != 0) before calling it.
691  */
692 void System::update_variable_bound(Variable* var, double bound)
693 {
694   modified_  = true;
695   var->bound = bound;
696
697   if (not var->cnsts.empty())
698     update_modified_set(var->cnsts[0].constraint);
699 }
700
701 void Variable::initialize(resource::Action* id_value, double sharing_weight_value, double bound_value,
702                           int number_of_constraints, unsigned visited_value)
703 {
704   id     = id_value;
705   id_int = Global_debug_id++;
706   cnsts.reserve(number_of_constraints);
707   sharing_weight    = sharing_weight_value;
708   staged_weight     = 0.0;
709   bound             = bound_value;
710   concurrency_share = 1;
711   value             = 0.0;
712   visited           = visited_value;
713   mu                = 0.0;
714   new_mu            = 0.0;
715
716   xbt_assert(not variable_set_hook.is_linked());
717   xbt_assert(not saturated_variable_set_hook.is_linked());
718 }
719
720 int Variable::get_min_concurrency_slack() const
721 {
722   int minslack = std::numeric_limits<int>::max();
723   for (Element const& elem : cnsts) {
724     int slack = elem.constraint->get_concurrency_slack();
725     if (slack < minslack) {
726       // This is only an optimization, to avoid looking at more constraints when slack is already zero
727       if (slack == 0)
728         return 0;
729       minslack = slack;
730     }
731   }
732   return minslack;
733 }
734
735 // Small remark: In this implementation of System::enable_var() and System::disable_var(), we will meet multiple times
736 // with var when running System::update_modified_set().
737 // A priori not a big performance issue, but we might do better by calling System::update_modified_set() within the for
738 // loops (after doing the first for enabling==1, and before doing the last for disabling==1)
739 void System::enable_var(Variable* var)
740 {
741   xbt_assert(not XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug) || var->can_enable());
742
743   var->sharing_weight = var->staged_weight;
744   var->staged_weight  = 0;
745
746   // Enabling the variable, move var to list head. Subtlety is: here, we need to call update_modified_set AFTER
747   // moving at least one element of var.
748
749   simgrid::xbt::intrusive_erase(variable_set, *var);
750   variable_set.push_front(*var);
751   for (Element& elem : var->cnsts) {
752     simgrid::xbt::intrusive_erase(elem.constraint->disabled_element_set, elem);
753     elem.constraint->enabled_element_set.push_front(elem);
754     elem.increase_concurrency();
755   }
756   if (not var->cnsts.empty())
757     update_modified_set(var->cnsts[0].constraint);
758
759   // When used within on_disabled_var, we would get an assertion fail, because transiently there can be variables
760   // that are staged and could be activated.
761   // Anyway, caller functions all call check_concurrency() in the end.
762 }
763
764 void System::disable_var(Variable* var)
765 {
766   xbt_assert(not var->staged_weight, "Staged weight should have been cleared");
767   // Disabling the variable, move to var to list tail. Subtlety is: here, we need to call update_modified_set
768   // BEFORE moving the last element of var.
769   simgrid::xbt::intrusive_erase(variable_set, *var);
770   variable_set.push_back(*var);
771   if (not var->cnsts.empty())
772     update_modified_set(var->cnsts[0].constraint);
773   for (Element& elem : var->cnsts) {
774     simgrid::xbt::intrusive_erase(elem.constraint->enabled_element_set, elem);
775     elem.constraint->disabled_element_set.push_back(elem);
776     if (elem.active_element_set_hook.is_linked())
777       simgrid::xbt::intrusive_erase(elem.constraint->active_element_set, elem);
778     elem.decrease_concurrency();
779   }
780
781   var->sharing_weight = 0.0;
782   var->staged_weight  = 0.0;
783   var->value          = 0.0;
784   check_concurrency();
785 }
786
787 /* /brief Find variables that can be enabled and enable them.
788  *
789  * Assuming that the variable has already been removed from non-zero weights
790  * Can we find a staged variable to add?
791  * If yes, check that none of the constraints that this variable is involved in is at the limit of its concurrency
792  * And then add it to enabled variables
793  */
794 void System::on_disabled_var(Constraint* cnstr)
795 {
796   if (cnstr->get_concurrency_limit() < 0)
797     return;
798
799   int numelem = cnstr->disabled_element_set.size();
800   if (not numelem)
801     return;
802
803   Element* elem = &cnstr->disabled_element_set.front();
804
805   // Cannot use foreach loop, because System::enable_var() will modify disabled_element_set.. within the loop
806   while (numelem-- && elem) {
807
808     Element* nextelem;
809     if (elem->disabled_element_set_hook.is_linked()) {
810       auto iter = std::next(cnstr->disabled_element_set.iterator_to(*elem));
811       nextelem  = iter != std::end(cnstr->disabled_element_set) ? &*iter : nullptr;
812     } else {
813       nextelem = nullptr;
814     }
815
816     if (elem->variable->staged_weight > 0 && elem->variable->can_enable()) {
817       // Found a staged variable
818       // TODOLATER: Add random timing function to model reservation protocol fuzziness? Then how to make sure that
819       // staged variables will eventually be called?
820       enable_var(elem->variable);
821     }
822
823     xbt_assert(cnstr->concurrency_current <= cnstr->get_concurrency_limit(), "Concurrency overflow!");
824     if (cnstr->concurrency_current == cnstr->get_concurrency_limit())
825       break;
826
827     elem = nextelem;
828   }
829
830   // We could get an assertion fail, because transiently there can be variables that are staged and could be activated.
831   // And we need to go through all constraints of the disabled var before getting back a coherent state.
832   // Anyway, caller functions all call check_concurrency() in the end.
833 }
834
835 /* @brief update the weight of a variable, and enable/disable it.
836  * @return Returns whether a change was made
837  */
838 void System::update_variable_weight(Variable* var, double weight)
839 {
840   xbt_assert(weight >= 0, "Variable weight should not be negative!");
841
842   if (weight == var->sharing_weight)
843     return;
844
845   int enabling_var  = (weight > 0 && var->sharing_weight <= 0);
846   int disabling_var = (weight <= 0 && var->sharing_weight > 0);
847
848   XBT_IN("(sys=%p, var=%p, weight=%f)", this, var, weight);
849
850   modified_ = true;
851
852   // Are we enabling this variable?
853   if (enabling_var) {
854     var->staged_weight = weight;
855     int minslack       = var->get_min_concurrency_slack();
856     if (minslack < var->concurrency_share) {
857       XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack %i, with weight %f and concurrency"
858                 " share %i",
859                 minslack, weight, var->concurrency_share);
860       return;
861     }
862     XBT_DEBUG("Enabling var with min concurrency slack %i", minslack);
863     enable_var(var);
864   } else if (disabling_var) {
865     // Are we disabling this variable?
866     disable_var(var);
867   } else {
868     var->sharing_weight = weight;
869   }
870
871   check_concurrency();
872
873   XBT_OUT();
874 }
875
876 void System::update_constraint_bound(Constraint* cnst, double bound)
877 {
878   modified_ = true;
879   update_modified_set(cnst);
880   cnst->bound = bound;
881 }
882
883 /** @brief Update the constraint set propagating recursively to other constraints so the system should not be entirely
884  *  computed.
885  *
886  *  @param cnst the Constraint* affected by the change
887  *
888  *  A recursive algorithm to optimize the system recalculation selecting only constraints that have changed. Each
889  *  constraint change is propagated to the list of constraints for each variable.
890  */
891 void System::update_modified_set_rec(Constraint* cnst)
892 {
893   for (Element const& elem : cnst->enabled_element_set) {
894     Variable* var = elem.variable;
895     for (Element const& elem2 : var->cnsts) {
896       if (var->visited == visited_counter_)
897         break;
898       if (elem2.constraint != cnst && not elem2.constraint->modified_constraint_set_hook.is_linked()) {
899         modified_constraint_set.push_back(*elem2.constraint);
900         update_modified_set_rec(elem2.constraint);
901       }
902     }
903     // var will be ignored in later visits as long as sys->visited_counter does not move
904     var->visited = visited_counter_;
905   }
906 }
907
908 void System::update_modified_set(Constraint* cnst)
909 {
910   /* nothing to do if selective update isn't active */
911   if (selective_update_active && not cnst->modified_constraint_set_hook.is_linked()) {
912     modified_constraint_set.push_back(*cnst);
913     update_modified_set_rec(cnst);
914   }
915 }
916
917 void System::remove_all_modified_set()
918 {
919   // We cleverly un-flag all variables just by incrementing visited_counter
920   // In effect, the var->visited value will no more be equal to visited counter
921   // To be clean, when visited counter has wrapped around, we force these var->visited values so that variables that
922   // were in the modified a long long time ago are not wrongly skipped here, which would lead to very nasty bugs
923   // (i.e. not readibily reproducible, and requiring a lot of run time before happening).
924   if (++visited_counter_ == 1) {
925     /* the counter wrapped around, reset each variable->visited */
926     for (Variable& var : variable_set)
927       var.visited = 0;
928   }
929   modified_constraint_set.clear();
930 }
931
932 /**
933  * Returns resource load (in flop per second, or byte per second, or similar)
934  *
935  * If the resource is shared (the default case), the load is sum of resource usage made by
936  * every variables located on this resource.
937  *
938  * If the resource is not shared (ie in FATPIPE mode), then the load is the max (not the sum)
939  * of all resource usages located on this resource.
940  */
941 double Constraint::get_usage() const
942 {
943   double result              = 0.0;
944   if (sharing_policy != s4u::Link::SharingPolicy::FATPIPE) {
945     for (Element const& elem : enabled_element_set)
946       if (elem.consumption_weight > 0)
947         result += elem.consumption_weight * elem.variable->value;
948   } else {
949     for (Element const& elem : enabled_element_set)
950       if (elem.consumption_weight > 0)
951         result = std::max(result, elem.consumption_weight * elem.variable->value);
952   }
953   return result;
954 }
955
956 int Constraint::get_variable_amount() const
957 {
958   return std::count_if(std::begin(enabled_element_set), std::end(enabled_element_set),
959                        [](const Element& elem) { return elem.consumption_weight > 0; });
960 }
961 }
962 }
963 }