1 /* Copyright (c) 2004-2015. The SimGrid Team.
2 * All rights reserved. */
4 /* This program is free software; you can redistribute it and/or modify it
5 * under the terms of the license (GNU LGPL) which comes with this package. */
7 /* \file callbacks.h */
9 #include "xbt/sysdep.h"
11 #include "xbt/mallocator.h"
12 #include "maxmin_private.hpp"
14 #include <stdio.h> /* sprintf */
16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_maxmin, surf,
17 "Logging specific to SURF (maxmin)");
19 typedef struct s_dyn_light {
23 } s_dyn_light_t, *dyn_light_t;
25 double sg_maxmin_precision = 0.00001;
26 double sg_surf_precision = 0.00001;
28 static void *lmm_variable_mallocator_new_f(void);
29 static void lmm_variable_mallocator_free_f(void *var);
30 #define lmm_variable_mallocator_reset_f ((void_f_pvoid_t)NULL)
31 static void lmm_update_modified_set(lmm_system_t sys,
32 lmm_constraint_t cnst);
33 static void lmm_remove_all_modified_set(lmm_system_t sys);
34 static int Global_debug_id = 1;
35 static int Global_const_debug_id = 1;
37 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var);
38 static XBT_INLINE void lmm_cnst_free(lmm_system_t sys,
39 lmm_constraint_t cnst);
41 static void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr);
42 static void lmm_enable_var(lmm_system_t sys, lmm_variable_t var);
43 static int lmm_can_enable_var(lmm_variable_t var);
44 static void lmm_disable_var(lmm_system_t sys, lmm_variable_t var);
45 static int lmm_concurrency_slack(lmm_constraint_t cnstr);
46 static int lmm_cnstrs_min_concurrency_slack(lmm_variable_t var);
48 static void lmm_check_concurrency(lmm_system_t sys);
50 inline void lmm_decrease_concurrency(lmm_constraint_t cnstr){
51 xbt_assert(cnstr->concurrency_current>0);
52 cnstr->concurrency_current--;
55 inline void lmm_increase_concurrency(lmm_constraint_t cnstr){
56 if(++cnstr->concurrency_current > cnstr->concurrency_maximum)
57 cnstr->concurrency_maximum=cnstr->concurrency_current;
58 xbt_assert(cnstr->concurrency_limit<0 || cnstr->concurrency_current<=cnstr->concurrency_limit,"Concurrency limit overflow!");
61 void lmm_check_concurrency(lmm_system_t sys){
65 lmm_constraint_t cnst;
67 if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
69 xbt_swag_foreach(_cnst, &(sys->constraint_set)) {
70 cnst = (lmm_constraint_t) _cnst;
72 if(cnst->concurrency_limit<0)
74 xbt_swag_foreach(_elem, &(cnst->element_set)) {
75 elem = (lmm_element_t)_elem;
76 if (elem->variable->weight > 0)
79 //We should have staged variables only if conccurency is reached
80 xbt_assert(elem->variable->staged_weight==0 || (cnst->concurrency_limit>0 && cnst->concurrency_limit < concurrency+elem->variable->concurrency_share),"should not have staged variable!");
83 xbt_assert(cnst->concurrency_limit<0 || cnst->concurrency_limit >= concurrency,"concurrency check failed!");
84 xbt_assert(cnst->concurrency_current == concurrency, "concurrency_current is out-of-date!");
90 lmm_system_t lmm_system_new(int selective_update)
92 lmm_system_t l = NULL;
94 s_lmm_constraint_t cnst;
96 l = xbt_new0(s_lmm_system_t, 1);
99 l->selective_update_active = selective_update;
100 l->visited_counter = 1;
102 XBT_DEBUG("Setting selective_update_active flag to %d",
103 l->selective_update_active);
105 xbt_swag_init(&(l->variable_set),
106 xbt_swag_offset(var, variable_set_hookup));
107 xbt_swag_init(&(l->constraint_set),
108 xbt_swag_offset(cnst, constraint_set_hookup));
110 xbt_swag_init(&(l->active_constraint_set),
111 xbt_swag_offset(cnst, active_constraint_set_hookup));
113 xbt_swag_init(&(l->modified_constraint_set),
114 xbt_swag_offset(cnst, modified_constraint_set_hookup));
115 xbt_swag_init(&(l->saturated_variable_set),
116 xbt_swag_offset(var, saturated_variable_set_hookup));
117 xbt_swag_init(&(l->saturated_constraint_set),
118 xbt_swag_offset(cnst, saturated_constraint_set_hookup));
120 l->variable_mallocator = xbt_mallocator_new(65536,
121 lmm_variable_mallocator_new_f,
122 lmm_variable_mallocator_free_f,
123 lmm_variable_mallocator_reset_f);
128 void lmm_system_free(lmm_system_t sys)
130 lmm_variable_t var = NULL;
131 lmm_constraint_t cnst = NULL;
134 while ((var = (lmm_variable_t) extract_variable(sys))) {
136 ("Variable %p (%d) still in system when freing it: this may be a bug",
138 lmm_var_free(sys, var);
141 while ((cnst = (lmm_constraint_t) extract_constraint(sys)))
142 lmm_cnst_free(sys, cnst);
144 xbt_mallocator_free(sys->variable_mallocator);
148 static XBT_INLINE void lmm_variable_remove(lmm_system_t sys, lmm_variable_t var)
153 lmm_element_t elem = NULL;
155 XBT_IN("(sys=%p, var=%p)", sys, var);
158 //TODOLATER Can do better than that by leaving only the variable in only one element_set, call lmm_update_modified_set, and then remove it..
159 if(var->cnsts_number)
160 lmm_update_modified_set(sys, var->cnsts[0].constraint);
162 for (i = 0; i < var->cnsts_number; i++) {
163 elem = &var->cnsts[i];
165 lmm_decrease_concurrency(elem->constraint);
166 xbt_swag_remove(elem, &(elem->constraint->element_set));
167 xbt_swag_remove(elem, &(elem->constraint->active_element_set));
168 nelements=xbt_swag_size(&(elem->constraint->element_set));
170 make_constraint_inactive(sys, elem->constraint);
171 //Check if we can enable new variables going through the constraints where var was.
173 lmm_on_disabled_var(sys,elem->constraint);
176 var->cnsts_number = 0;
180 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var)
183 lmm_variable_remove(sys, var);
184 xbt_mallocator_release(sys->variable_mallocator, var);
187 static XBT_INLINE void lmm_cnst_free(lmm_system_t sys,
188 lmm_constraint_t cnst)
190 /* xbt_assert(xbt_swag_size(&(cnst->element_set)), */
191 /* "This list should be empty!"); */
192 make_constraint_inactive(sys, cnst);
196 lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id,
199 lmm_constraint_t cnst = NULL;
200 s_lmm_element_t elem;
202 cnst = xbt_new0(s_lmm_constraint_t, 1);
204 cnst->id_int = Global_const_debug_id++;
205 xbt_swag_init(&(cnst->element_set),
206 xbt_swag_offset(elem, element_set_hookup));
207 xbt_swag_init(&(cnst->active_element_set),
208 xbt_swag_offset(elem, active_element_set_hookup));
210 cnst->bound = bound_value;
211 cnst->concurrency_maximum=0;
212 cnst->concurrency_current=0;
213 //TODO MARTIN Maybe a configuration item for the default cap concurrency?
214 cnst->concurrency_limit=100;
216 cnst->sharing_policy = 1; /* FIXME: don't hardcode the value */
217 insert_constraint(sys, cnst);
222 void lmm_constraint_concurrency_limit_set(lmm_constraint_t cnst, int concurrency_limit)
224 cnst->concurrency_limit = concurrency_limit;
227 void lmm_constraint_concurrency_maximum_reset(lmm_constraint_t cnst)
229 cnst->concurrency_maximum = 0;
232 int lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst)
234 return cnst->concurrency_maximum;
237 void lmm_constraint_shared(lmm_constraint_t cnst)
239 cnst->sharing_policy = 0;
242 /** Return true if the constraint is shared, and false if it's FATPIPE */
243 int lmm_constraint_sharing_policy(lmm_constraint_t cnst)
245 return (cnst->sharing_policy);
248 /* @brief Remove a constraint
249 * Currently this is dead code, but it is exposed in maxmin.h
250 * Apparently, this call was designed assuming that constraint would no more have elements in it.
251 * If this is not the case, assertion will fail, and you need to add calls e.g. to lmm_shrink before effectively removing it.
253 XBT_INLINE void lmm_constraint_free(lmm_system_t sys,
254 lmm_constraint_t cnst)
256 xbt_assert(!xbt_swag_size(&(cnst->active_element_set)),"Removing constraint but it still has active elements");
257 xbt_assert(!xbt_swag_size(&(cnst->element_set)),"Removing constraint but it still has elements");
258 remove_constraint(sys, cnst);
259 lmm_cnst_free(sys, cnst);
262 static void *lmm_variable_mallocator_new_f(void)
264 lmm_variable_t var = xbt_new(s_lmm_variable_t, 1);
265 var->cnsts = NULL; /* will be created by realloc */
269 static void lmm_variable_mallocator_free_f(void *var)
271 xbt_free(((lmm_variable_t) var)->cnsts);
275 lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id,
277 double bound, int number_of_constraints)
279 lmm_variable_t var = NULL;
282 XBT_IN("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)",
283 sys, id, weight, bound, number_of_constraints);
285 var = (lmm_variable_t) xbt_mallocator_get(sys->variable_mallocator);
287 var->id_int = Global_debug_id++;
288 var->cnsts = (s_lmm_element_t *) xbt_realloc(var->cnsts, number_of_constraints * sizeof(s_lmm_element_t));
289 for (i = 0; i < number_of_constraints; i++) {
290 var->cnsts[i].element_set_hookup.next = NULL;
291 var->cnsts[i].element_set_hookup.prev = NULL;
292 var->cnsts[i].active_element_set_hookup.next = NULL;
293 var->cnsts[i].active_element_set_hookup.prev = NULL;
294 var->cnsts[i].constraint = NULL;
295 var->cnsts[i].variable = NULL;
296 var->cnsts[i].value = 0.0;
298 var->cnsts_size = number_of_constraints;
299 var->cnsts_number = 0;
300 var->weight = weight;
301 var->staged_weight = 0.0;
303 var->concurrency_share = 1;
305 var->visited = sys->visited_counter - 1;
308 var->func_f = func_f_def;
309 var->func_fp = func_fp_def;
310 var->func_fpi = func_fpi_def;
312 var->variable_set_hookup.next = NULL;
313 var->variable_set_hookup.prev = NULL;
314 var->saturated_variable_set_hookup.next = NULL;
315 var->saturated_variable_set_hookup.prev = NULL;
318 xbt_swag_insert_at_head(var, &(sys->variable_set));
320 xbt_swag_insert_at_tail(var, &(sys->variable_set));
322 XBT_OUT(" returns %p", var);
326 void lmm_variable_free(lmm_system_t sys, lmm_variable_t var)
328 remove_variable(sys, var);
329 lmm_var_free(sys, var);
332 double lmm_variable_getvalue(lmm_variable_t var)
338 void lmm_variable_concurrency_share_set(lmm_variable_t var, short int concurrency_share)
340 var->concurrency_share=concurrency_share;
343 double lmm_variable_getbound(lmm_variable_t var)
348 void lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
351 lmm_element_t elem = NULL;
355 for (i = 0; i < var->cnsts_number; i++) {
356 elem = &(var->cnsts[i]);
357 if (elem->constraint == cnst) {
364 XBT_DEBUG("cnst %p is not found in var %p", cnst, var);
370 XBT_DEBUG("remove elem(value %f, cnst %p, var %p) in var %p",
371 elem->value, elem->constraint, elem->variable, var);
373 /* We are going to change the constraint object and the variable object.
374 * Propagate this change to other objects. Calling here before removing variable from not active elements (inactive elements are not visited)
376 lmm_update_modified_set(sys, cnst);
377 //Useful in case var was already removed from the constraint
378 lmm_update_modified_set(sys, var->cnsts[0].constraint); // will look up element_set of this constraint, and then each var in the element_set, and each var->cnsts[i].
380 if(xbt_swag_remove(elem, &(elem->constraint->element_set)) && var->weight>0)
381 lmm_decrease_concurrency(elem->constraint);
383 xbt_swag_remove(elem, &(elem->constraint->active_element_set));
384 elem->constraint = NULL;
385 elem->variable = NULL;
388 var->cnsts_number -= 1;
390 //No variable in this constraint -> make it inactive
391 if (xbt_swag_size(&(cnst->element_set)) == 0)
392 make_constraint_inactive(sys, cnst);
394 //Check maxconcurrency to see if we can enable new variables
395 lmm_on_disabled_var(sys,elem->constraint);
398 lmm_check_concurrency(sys);
401 void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
402 lmm_variable_t var, double value)
404 lmm_element_t elem = NULL;
410 if(var->weight>0 && lmm_concurrency_slack(cnst)==0){
412 lmm_disable_var(sys,var);
413 for (i = 0; i < var->cnsts_number; i++)
414 lmm_on_disabled_var(sys,var->cnsts[i].constraint);
416 var->staged_weight=weight;
417 xbt_assert(!var->weight);
420 xbt_assert(var->cnsts_number < var->cnsts_size, "Too much constraints");
422 elem = &(var->cnsts[var->cnsts_number++]);
425 elem->constraint = cnst;
426 elem->variable = var;
430 xbt_swag_insert_at_head(elem, &(elem->constraint->element_set));
431 lmm_increase_concurrency(elem->constraint);
434 xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set));
436 if(!sys->selective_update_active) {
437 make_constraint_active(sys, cnst);
438 } else if(elem->value>0 || var->weight >0) {
439 make_constraint_active(sys, cnst);
440 lmm_update_modified_set(sys, cnst);
441 //TODOLATER: Why do we need this second call?
442 if (var->cnsts_number > 1)
443 lmm_update_modified_set(sys, var->cnsts[0].constraint);
446 lmm_check_concurrency(sys);
449 void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
450 lmm_variable_t var, double value)
455 lmm_check_concurrency(sys);
457 for (i = 0; i < var->cnsts_number; i++)
458 if (var->cnsts[i].constraint == cnst)
461 if (i < var->cnsts_number) {
462 if (cnst->sharing_policy)
463 var->cnsts[i].value += value;
465 var->cnsts[i].value = MAX(var->cnsts[i].value, value);
466 lmm_update_modified_set(sys, cnst);
468 lmm_expand(sys, cnst, var, value);
470 lmm_check_concurrency(sys);
473 lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t /*sys*/,
477 if (num < var->cnsts_number)
478 return (var->cnsts[num].constraint);
483 double lmm_get_cnst_weight_from_var(lmm_system_t /*sys*/,
487 if (num < var->cnsts_number)
488 return (var->cnsts[num].value);
493 int lmm_get_number_of_cnst_from_var(lmm_system_t /*sys*/,
496 return (var->cnsts_number);
499 lmm_variable_t lmm_get_var_from_cnst(lmm_system_t /*sys*/,
500 lmm_constraint_t cnst,
501 lmm_element_t * elem)
504 *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->element_set));
506 *elem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->element_set.offset);
508 return (*elem)->variable;
513 //if we modify the swag between calls, normal version may loop forever
514 //this safe version ensures that we browse the swag elements only once
515 lmm_variable_t lmm_get_var_from_cnst_safe(lmm_system_t /*sys*/,
516 lmm_constraint_t cnst,
517 lmm_element_t * elem,
518 lmm_element_t * nextelem,
522 *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->element_set));
523 *numelem = xbt_swag_size(&(cnst->element_set))-1;
532 *nextelem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->element_set.offset);
533 return (*elem)->variable;
538 void *lmm_constraint_id(lmm_constraint_t cnst)
543 void *lmm_variable_id(lmm_variable_t var)
548 static XBT_INLINE void saturated_constraint_set_update(double usage,
550 dyn_light_t saturated_constraint_set,
553 xbt_assert(usage > 0,"Impossible");
555 if (*min_usage < 0 || *min_usage > usage) {
557 XBT_HERE(" min_usage=%f (cnst->remaining / cnst->usage =%f)", *min_usage, usage);
558 saturated_constraint_set->data[0] = cnst_light_num;
559 saturated_constraint_set->pos = 1;
560 } else if (*min_usage == usage) {
561 if(saturated_constraint_set->pos == saturated_constraint_set->size) { // realloc the size
562 saturated_constraint_set->size *= 2;
563 saturated_constraint_set->data = (int*) xbt_realloc(saturated_constraint_set->data, (saturated_constraint_set->size) * sizeof(int));
565 saturated_constraint_set->data[saturated_constraint_set->pos] = cnst_light_num;
566 saturated_constraint_set->pos++;
570 static XBT_INLINE void saturated_variable_set_update(
571 s_lmm_constraint_light_t *cnst_light_tab,
572 dyn_light_t saturated_constraint_set,
575 /* Add active variables (i.e. variables that need to be set) from the set of constraints to saturate (cnst_light_tab)*/
576 lmm_constraint_light_t cnst = NULL;
578 lmm_element_t elem = NULL;
579 xbt_swag_t elem_list = NULL;
581 for(i = 0; i< saturated_constraint_set->pos; i++){
582 cnst = &cnst_light_tab[saturated_constraint_set->data[i]];
583 elem_list = &(cnst->cnst->active_element_set);
584 xbt_swag_foreach(_elem, elem_list) {
585 elem = (lmm_element_t)_elem;
586 //Visiting active_element_set, so, by construction, should never get a zero weight, correct?
587 xbt_assert(elem->variable->weight > 0);
588 if ((elem->value > 0))
589 xbt_swag_insert(elem->variable, &(sys->saturated_variable_set));
594 void lmm_print(lmm_system_t sys)
596 void *_cnst, *_elem, *_var;
597 lmm_constraint_t cnst = NULL;
598 lmm_element_t elem = NULL;
599 lmm_variable_t var = NULL;
600 xbt_swag_t cnst_list = NULL;
601 xbt_swag_t var_list = NULL;
602 xbt_swag_t elem_list = NULL;
603 char print_buf[1024];
604 char *trace_buf = (char*) xbt_malloc0(sizeof(char));
607 /* Printing Objective */
608 var_list = &(sys->variable_set);
609 sprintf(print_buf, "MAX-MIN ( ");
611 xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
612 strcat(trace_buf, print_buf);
613 xbt_swag_foreach(_var, var_list) {
614 var = (lmm_variable_t)_var;
615 sprintf(print_buf, "'%d'(%f) ", var->id_int, var->weight);
617 xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
618 strcat(trace_buf, print_buf);
620 sprintf(print_buf, ")");
622 xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
623 strcat(trace_buf, print_buf);
624 XBT_DEBUG("%20s", trace_buf);
625 trace_buf[0] = '\000';
627 XBT_DEBUG("Constraints");
628 /* Printing Constraints */
629 cnst_list = &(sys->active_constraint_set);
630 xbt_swag_foreach(_cnst, cnst_list) {
631 cnst = (lmm_constraint_t)_cnst;
633 elem_list = &(cnst->element_set);
634 sprintf(print_buf, "\t");
636 xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
637 strcat(trace_buf, print_buf);
638 sprintf(print_buf, "%s(",(cnst->sharing_policy)?"":"max");
640 xbt_realloc(trace_buf,
641 strlen(trace_buf) + strlen(print_buf) + 1);
642 strcat(trace_buf, print_buf);
643 xbt_swag_foreach(_elem, elem_list) {
644 elem = (lmm_element_t)_elem;
645 sprintf(print_buf, "%f.'%d'(%f) %s ", elem->value,
646 elem->variable->id_int, elem->variable->value,(cnst->sharing_policy)?"+":",");
648 xbt_realloc(trace_buf,
649 strlen(trace_buf) + strlen(print_buf) + 1);
650 strcat(trace_buf, print_buf);
651 if(cnst->sharing_policy)
652 sum += elem->value * elem->variable->value;
654 sum = MAX(sum,elem->value * elem->variable->value);
656 sprintf(print_buf, "0) <= %f ('%d')", cnst->bound, cnst->id_int);
658 xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
659 strcat(trace_buf, print_buf);
661 if (!cnst->sharing_policy) {
662 sprintf(print_buf, " [MAX-Constraint]");
664 xbt_realloc(trace_buf,
665 strlen(trace_buf) + strlen(print_buf) + 1);
666 strcat(trace_buf, print_buf);
668 XBT_DEBUG("%s", trace_buf);
669 trace_buf[0] = '\000';
670 xbt_assert(!double_positive(sum - cnst->bound, cnst->bound*sg_maxmin_precision),
671 "Incorrect value (%f is not smaller than %f): %g",
672 sum, cnst->bound, sum - cnst->bound);
675 XBT_DEBUG("Variables");
676 /* Printing Result */
677 xbt_swag_foreach(_var, var_list) {
678 var = (lmm_variable_t)_var;
679 if (var->bound > 0) {
680 XBT_DEBUG("'%d'(%f) : %f (<=%f)", var->id_int, var->weight, var->value,
682 xbt_assert(!double_positive(var->value - var->bound, var->bound*sg_maxmin_precision),
683 "Incorrect value (%f is not smaller than %f",
684 var->value, var->bound);
686 XBT_DEBUG("'%d'(%f) : %f", var->id_int, var->weight, var->value);
693 void lmm_solve(lmm_system_t sys)
695 void *_var, *_cnst, *_cnst_next, *_elem;
696 lmm_variable_t var = NULL;
697 lmm_constraint_t cnst = NULL;
698 lmm_element_t elem = NULL;
699 xbt_swag_t cnst_list = NULL;
700 xbt_swag_t var_list = NULL;
701 xbt_swag_t elem_list = NULL;
702 double min_usage = -1;
703 double min_bound = -1;
705 if (!(sys->modified))
708 XBT_IN("(sys=%p)", sys);
711 * 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.
715 selective_update_active ? &(sys->modified_constraint_set) :
716 &(sys->active_constraint_set);
718 XBT_DEBUG("Active constraints : %d", xbt_swag_size(cnst_list));
719 /* Init: Only modified code portions: reset the value of active variables */
720 xbt_swag_foreach(_cnst, cnst_list) {
721 cnst = (lmm_constraint_t)_cnst;
722 elem_list = &(cnst->element_set);
723 //XBT_DEBUG("Variable set : %d", xbt_swag_size(elem_list));
724 xbt_swag_foreach(_elem, elem_list) {
725 var = ((lmm_element_t)_elem)->variable;
726 if (var->weight <= 0.0)
732 s_lmm_constraint_light_t *cnst_light_tab = (s_lmm_constraint_light_t *)xbt_malloc0(xbt_swag_size(cnst_list)*sizeof(s_lmm_constraint_light_t));
733 int cnst_light_num = 0;
734 dyn_light_t saturated_constraint_set = xbt_new0(s_dyn_light_t,1);
735 saturated_constraint_set->size = 5;
736 saturated_constraint_set->data = xbt_new0(int, saturated_constraint_set->size);
738 xbt_swag_foreach_safe(_cnst, _cnst_next, cnst_list) {
739 cnst = (lmm_constraint_t)_cnst;
740 /* INIT: Collect constraints that actually need to be saturated (i.e remaining and usage are strictly positive) into cnst_light_tab. */
741 cnst->remaining = cnst->bound;
742 if (!double_positive(cnst->remaining, cnst->bound*sg_maxmin_precision))
745 elem_list = &(cnst->element_set);
746 xbt_swag_foreach(_elem, elem_list) {
747 elem = (lmm_element_t)_elem;
748 /* 0-weighted elements (ie, sleep actions) are at the end of the swag and we don't want to consider them */
749 if (elem->variable->weight <= 0)
751 if ((elem->value > 0)) {
752 if (cnst->sharing_policy)
753 cnst->usage += elem->value / elem->variable->weight;
754 else if (cnst->usage < elem->value / elem->variable->weight)
755 cnst->usage = elem->value / elem->variable->weight;
757 make_elem_active(elem);
758 simgrid::surf::Action *action = static_cast<simgrid::surf::Action*>(elem->variable->id);
759 if (sys->keep_track && !action->is_linked())
760 sys->keep_track->push_back(*action);
763 XBT_DEBUG("Constraint '%d' usage: %f remaining: %f ", cnst->id_int, cnst->usage, cnst->remaining);
764 /* Saturated constraints update */
766 if(cnst->usage > 0) {
767 cnst_light_tab[cnst_light_num].cnst = cnst;
768 cnst->cnst_light = &(cnst_light_tab[cnst_light_num]);
769 cnst_light_tab[cnst_light_num].remaining_over_usage = cnst->remaining / cnst->usage;
770 saturated_constraint_set_update(cnst_light_tab[cnst_light_num].remaining_over_usage,
771 cnst_light_num, saturated_constraint_set, &min_usage);
772 xbt_assert(cnst->active_element_set.count>0, "There is no sense adding a constraint that has no active element!" );
777 saturated_variable_set_update( cnst_light_tab,
778 saturated_constraint_set,
781 /* Saturated variables update */
784 /* Fix the variables that have to be */
785 var_list = &(sys->saturated_variable_set);
787 xbt_swag_foreach(_var, var_list) {
788 var = (lmm_variable_t)_var;
789 if (var->weight <= 0.0)
791 /* First check if some of these variables could reach their upper
792 bound and update min_bound accordingly. */
794 ("var=%d, var->bound=%f, var->weight=%f, min_usage=%f, var->bound*var->weight=%f",
795 var->id_int, var->bound, var->weight, min_usage,
796 var->bound * var->weight);
797 if ((var->bound > 0) && (var->bound * var->weight < min_usage)) {
799 min_bound = var->bound*var->weight;
801 min_bound = MIN(min_bound, (var->bound*var->weight));
802 XBT_DEBUG("Updated min_bound=%f", min_bound);
807 while ((var = (lmm_variable_t)xbt_swag_getFirst(var_list))) {
811 //If no variable could reach its bound, deal iteratively the constraints usage ( at worst one constraint is saturated at each cycle)
812 var->value = min_usage / var->weight;
813 XBT_DEBUG("Setting %p (%d) value to %f\n", var, var->id_int, var->value);
815 //If there exist a variable that can reach its bound, only update it (and other with the same bound) for now.
816 if (double_equals(min_bound, var->bound*var->weight, sg_maxmin_precision)){
817 var->value = var->bound;
818 XBT_DEBUG("Setting %p (%d) value to %f\n", var, var->id_int, var->value);
821 // Variables which bound is different are not considered for this cycle, but they will be afterwards.
822 XBT_DEBUG("Do not consider %p (%d) \n", var, var->id_int);
823 xbt_swag_remove(var, var_list);
827 XBT_DEBUG("Min usage: %f, Var(%d)->weight: %f, Var(%d)->value: %f ",
828 min_usage, var->id_int, var->weight, var->id_int, var->value);
831 /* Update the usage of contraints where this variable is involved */
832 for (i = 0; i < var->cnsts_number; i++) {
833 elem = &var->cnsts[i];
834 cnst = elem->constraint;
835 if (cnst->sharing_policy) {
836 //Remember: shared constraints require that sum(elem->value * var->value) < cnst->bound
837 double_update(&(cnst->remaining), elem->value * var->value, cnst->bound*sg_maxmin_precision);
838 double_update(&(cnst->usage), elem->value / var->weight, sg_maxmin_precision);
839 //If the constraint is saturated, remove it from the set of active constraints (light_tab)
840 if(!double_positive(cnst->usage,sg_maxmin_precision) || !double_positive(cnst->remaining,cnst->bound*sg_maxmin_precision)) {
841 if (cnst->cnst_light) {
842 int index = (cnst->cnst_light-cnst_light_tab);
843 XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p \t cnst_light_tab: %p usage: %f remaining: %f bound: %f ",
844 index,cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab, cnst->usage, cnst->remaining, cnst->bound);
845 cnst_light_tab[index]=cnst_light_tab[cnst_light_num-1];
846 cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index];
848 cnst->cnst_light = NULL;
851 cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage;
853 make_elem_inactive(elem);
855 //Remember: non-shared constraints only require that max(elem->value * var->value) < cnst->bound
857 make_elem_inactive(elem);
858 elem_list = &(cnst->element_set);
859 xbt_swag_foreach(_elem, elem_list) {
860 elem = (lmm_element_t)_elem;
861 if (elem->variable->weight <= 0) break; //Found an inactive variable -> no more active variables
862 if (elem->variable->value > 0) continue;
864 cnst->usage = MAX(cnst->usage, elem->value / elem->variable->weight);
866 //If the constraint is saturated, remove it from the set of active constraints (light_tab)
867 if(!double_positive(cnst->usage,sg_maxmin_precision) || !double_positive(cnst->remaining,cnst->bound*sg_maxmin_precision)) {
868 if(cnst->cnst_light) {
869 int index = (cnst->cnst_light-cnst_light_tab);
870 XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p \t cnst_light_tab: %p usage: %f remaining: %f bound: %f ",
871 index,cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab, cnst->usage, cnst->remaining, cnst->bound);
872 cnst_light_tab[index]=cnst_light_tab[cnst_light_num-1];
873 cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index];
875 cnst->cnst_light = NULL;
878 cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage;
879 xbt_assert(cnst->active_element_set.count>0, "Should not keep a maximum constraint that has no active element! You want to check the maxmin precision and possible rounding effects." );
883 xbt_swag_remove(var, var_list);
886 /* Find out which variables reach the maximum */
889 saturated_constraint_set->pos = 0;
891 for(pos=0; pos<cnst_light_num; pos++){
892 xbt_assert(cnst_light_tab[pos].cnst->active_element_set.count>0, "Cannot saturate more a constraint that has no active element! You may want to change the maxmin precision (--cfg=maxmin/precision:<new_value>) because of possible rounding effects.\n\tFor the record, the usage of this constraint is %g while the maxmin precision to which it is compared is %g.\n\tThe usage of the previous constraint is %g.", cnst_light_tab[pos].cnst->usage, sg_maxmin_precision, cnst_light_tab[pos-1].cnst->usage);
893 saturated_constraint_set_update(
894 cnst_light_tab[pos].remaining_over_usage,
896 saturated_constraint_set,
900 saturated_variable_set_update( cnst_light_tab,
901 saturated_constraint_set,
904 } while (cnst_light_num > 0);
907 if (sys->selective_update_active)
908 lmm_remove_all_modified_set(sys);
910 if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
914 xbt_free(saturated_constraint_set->data);
915 xbt_free(saturated_constraint_set);
916 xbt_free(cnst_light_tab);
921 /** \brief Attribute the value bound to var->bound.
923 * \param sys the lmm_system_t
924 * \param var the lmm_variable_t
925 * \param bound the new bound to associate with var
927 * Makes var->bound equal to bound. Whenever this function is called
928 * a change is signed in the system. To
929 * avoid false system changing detection it is a good idea to test
930 * (bound != 0) before calling it.
933 void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
939 if (var->cnsts_number)
940 lmm_update_modified_set(sys, var->cnsts[0].constraint);
945 int lmm_concurrency_slack(lmm_constraint_t cnstr){
952 //FIXME MARTIN: Replace by infinite value std::numeric_limits<int>::(max)(), or something better within Simgrid?
953 if(cnstr->concurrency_limit<0)
956 if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
957 xbt_swag_foreach(_elem, &(cnstr->element_set)) {
958 elem = (lmm_element_t)_elem;
959 if (elem->variable->weight <= 0) break; //Found an inactive variable
963 slack=cnstr->concurrency_limit-concurrency;
964 xbt_assert(slack>=0,"concurrency slack should not be negative!");
968 return cnstr->concurrency_limit - cnstr->concurrency_current;
972 /** \brief Measure the minimum concurrency slack across all constraints where var is involved
974 * \param The variable to check for
977 int lmm_cnstrs_min_concurrency_slack(lmm_variable_t var){
979 //FIXME MARTIN: Replace by infinite value std::numeric_limits<int>::(max)(), or something better within Simgrid?
980 int slack,minslack=666;
981 for (i = 0; i < var->cnsts_number; i++) {
982 slack=lmm_concurrency_slack(var->cnsts[i].constraint);
984 //This is only an optimization, to avoid looking at more constraints when slack is already zero
985 //Disable it when debugging to let lmm_concurrency_slack catch nasty things
986 if(!slack && !XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug))
996 /* /Check if a variable can be enabled
998 * Make sure to set staged_weight before, if your intent is only to check concurrency
1000 int lmm_can_enable_var(lmm_variable_t var){
1001 return var->staged_weight>0 && lmm_cnstrs_min_concurrency_slack(var)>=var->concurrency_share;
1005 //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.
1006 //A priori not a big performance issue, but we might do better by calling lmm_update_modified_set within the for loops (after doing the first for enabling==1, and before doing the last for disabling==1)
1008 void lmm_enable_var(lmm_system_t sys, lmm_variable_t var){
1013 xbt_assert(lmm_can_enable_var(var));
1014 lmm_check_concurrency(sys);
1016 var->weight = var->staged_weight;
1017 var->staged_weight = 0;
1019 //Enabling the variable, move to var to list head. Subtility is: here, we need to call lmm_update_modified_set AFTER moving at least one element of var.
1021 xbt_swag_remove(var, &(sys->variable_set));
1022 xbt_swag_insert_at_head(var, &(sys->variable_set));
1023 for (i = 0; i < var->cnsts_number; i++) {
1024 elem = &var->cnsts[i];
1025 xbt_swag_remove(elem, &(elem->constraint->element_set));
1026 xbt_swag_insert_at_head(elem, &(elem->constraint->element_set));
1027 lmm_increase_concurrency(elem->constraint);
1029 if (var->cnsts_number)
1030 lmm_update_modified_set(sys, var->cnsts[0].constraint);
1032 lmm_check_concurrency(sys);
1035 void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){
1039 xbt_assert(!var->staged_weight,"Staged weight should have been cleared");
1040 //Disabling the variable, move to var to list tail. Subtility is: here, we need to call lmm_update_modified_set BEFORE moving the last element of var.
1041 xbt_swag_remove(var, &(sys->variable_set));
1042 xbt_swag_insert_at_tail(var, &(sys->variable_set));
1043 if (var->cnsts_number)
1044 lmm_update_modified_set(sys, var->cnsts[0].constraint);
1045 for (i = 0; i < var->cnsts_number; i++) {
1046 elem = &var->cnsts[i];
1047 xbt_swag_remove(elem, &(elem->constraint->element_set));
1048 xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set));
1050 xbt_swag_remove(elem, &(elem->constraint->active_element_set));
1052 lmm_decrease_concurrency(elem->constraint);
1056 var->staged_weight=0.0;
1058 lmm_check_concurrency(sys);
1061 /* /brief Find variables that can be enabled and enable them.
1063 * Assuming that the variable has already been removed from non-zero weights
1064 * Can we find a staged variable to add?
1065 * If yes, check that none of the constraints that this variable is involved in is at the limit of its concurrency
1066 * And then add it to active variables
1068 void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr){
1071 if(cnstr->concurrency_limit<0)
1075 xbt_swag_foreach(elem, &(cnstr->element_set)) {
1077 //active variables are checked to see if we already reached the maximum (SHOULD NOT HAPPEN BECAUSE WE SHOULD HAVE JUST DEACTIVATED ONE)
1078 if (elem->variable->weight > 0){
1080 xbt_assert(elem->variable->staged_weight==0.0,"Staged weight should have been reset");
1081 } else if (elem->variable->staged_weight>0 )
1083 //Found a staged variable
1084 //TODOLATER: Add random timing function to model reservation protocol fuzziness? Then how to make sure that staged variables will eventually be called?
1085 if(lmm_can_enable_var(elem->variable)){
1086 lmm_enable_var(sys,elem->variable);
1091 xbt_assert(concurrency<=cnstr->concurrency_limit,"Concurrency overflow!");
1092 if(concurrency==cnstr->concurrency_limit)
1096 lmm_check_concurrency(sys);
1100 /* \brief update the weight of a variable, and enable/disable it.
1101 * @return Returns whether a change was made
1103 void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var,
1108 xbt_assert(weight>=0,"Variable weight should not be negative!");
1110 if (weight == var->weight)
1113 int enabling_var= (weight>0 && var->weight<=0);
1114 int disabling_var= (weight<=0 && var->weight>0);
1116 XBT_IN("(sys=%p, var=%p, weight=%f)", sys, var, weight);
1120 //Are we enabling this variable?
1122 var->staged_weight = weight;
1123 minslack=lmm_cnstrs_min_concurrency_slack(var);
1125 XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack %i, with weight %f", minslack, weight);
1128 XBT_DEBUG("Enabling var with min concurrency slack %i", minslack);
1129 lmm_enable_var(sys,var);
1130 } else if (disabling_var){
1131 //Are we disabling this variable?
1132 lmm_disable_var(sys,var);
1137 lmm_check_concurrency(sys);
1143 double lmm_get_variable_weight(lmm_variable_t var)
1148 void lmm_update_constraint_bound(lmm_system_t sys,
1149 lmm_constraint_t cnst,
1153 lmm_update_modified_set(sys, cnst);
1154 cnst->bound = bound;
1157 int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst)
1159 return xbt_swag_belongs(cnst, &(sys->active_constraint_set));
1162 XBT_INLINE lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t
1165 return (lmm_constraint_t)xbt_swag_getFirst(&(sys->active_constraint_set));
1168 XBT_INLINE lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t
1173 return (lmm_constraint_t)xbt_swag_getNext(cnst, (sys->active_constraint_set).offset);
1176 #ifdef HAVE_LATENCY_BOUND_TRACKING
1177 XBT_INLINE int lmm_is_variable_limited_by_latency(lmm_variable_t var)
1179 return (double_equals(var->bound, var->value, var->bound*sg_maxmin_precision));
1184 /** \brief Update the constraint set propagating recursively to
1185 * other constraints so the system should not be entirely computed.
1187 * \param sys the lmm_system_t
1188 * \param cnst the lmm_constraint_t affected by the change
1190 * A recursive algorithm to optimize the system recalculation selecting only
1191 * constraints that have changed. Each constraint change is propagated
1192 * to the list of constraints for each variable.
1194 static void lmm_update_modified_set_rec(lmm_system_t sys,
1195 lmm_constraint_t cnst)
1199 //TODOLATER: Why lmm_modified_set has been changed in git version 2392B5157...? Looks equivalent logically and less obvious..
1201 xbt_swag_foreach(_elem, &cnst->element_set) {
1202 lmm_variable_t var = ((lmm_element_t)_elem)->variable;
1203 s_lmm_element_t *cnsts = var->cnsts;
1205 /* No need to update variables that are not active (because we made sure that also variables in the process of being disabled are still in the active element set of the original constraint given as argument) */
1208 for (i = 0; var->visited != sys->visited_counter
1209 && i < var->cnsts_number ; i++) {
1210 if (cnsts[i].constraint != cnst
1211 && !xbt_swag_belongs(cnsts[i].constraint,
1212 &sys->modified_constraint_set)) {
1213 xbt_swag_insert(cnsts[i].constraint, &sys->modified_constraint_set);
1214 lmm_update_modified_set_rec(sys, cnsts[i].constraint);
1217 //var will be ignored in later visits as long as sys->visited_counter does not move
1218 var->visited = sys->visited_counter;
1222 static void lmm_update_modified_set(lmm_system_t sys,
1223 lmm_constraint_t cnst)
1225 /* nothing to do if selective update isn't active */
1226 if (sys->selective_update_active
1227 && !xbt_swag_belongs(cnst, &sys->modified_constraint_set)) {
1228 xbt_swag_insert(cnst, &sys->modified_constraint_set);
1229 lmm_update_modified_set_rec(sys, cnst);
1233 /** \brief Remove all constraints of the modified_constraint_set.
1235 * \param sys the lmm_system_t
1238 static void lmm_remove_all_modified_set(lmm_system_t sys)
1241 //We cleverly un-flag all variables just by incrementing sys->visited_counter
1242 //In effect, the var->visited value will no more be equal to sys->visited counter
1243 //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 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).
1244 if (++sys->visited_counter == 1) {
1245 /* the counter wrapped around, reset each variable->visited */
1247 xbt_swag_foreach(_var, &sys->variable_set)
1248 ((lmm_variable_t)_var)->visited = 0;
1250 xbt_swag_reset(&sys->modified_constraint_set);
1254 * Returns total resource load
1256 * \param cnst the lmm_constraint_t associated to the resource
1259 * This is dead code, but we may use it later for debug/trace.
1261 double lmm_constraint_get_usage(lmm_constraint_t cnst) {
1263 xbt_swag_t elem_list = &(cnst->element_set);
1265 lmm_element_t elem = NULL;
1267 xbt_swag_foreach(_elem, elem_list) {
1268 elem = (lmm_element_t)_elem;
1269 /* 0-weighted elements (ie, sleep actions) are at the end of the swag and we don't want to consider them */
1270 if (elem->variable->weight <= 0)
1272 if ((elem->value > 0)) {
1273 if (cnst->sharing_policy)
1274 usage += elem->value * elem->variable->value;
1275 else if (usage < elem->value * elem->variable->value)
1276 usage = elem->value * elem->variable->value;