src/surf/maxmin.cpp

   1 /* Copyright (c) 2004-2015. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   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. */
   6
   7 /* \file callbacks.h */
   8
   9 #include "xbt/sysdep.h"
  10 #include "xbt/log.h"
  11 #include "xbt/mallocator.h"
  12 #include "maxmin_private.hpp"
  13 #include <stdlib.h>
  14 #include <stdio.h>              /* sprintf */
  15 #include <math.h>
  16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_maxmin, surf,
  17                                 "Logging specific to SURF (maxmin)");
  18
  19 typedef struct s_dyn_light {
  20   int *data;
  21   int pos;
  22   int size;
  23 } s_dyn_light_t, *dyn_light_t;
  24
  25 double sg_maxmin_precision = 0.00001;
  26 double sg_surf_precision   = 0.00001;
  27
  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;
  36
  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);
  40
  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);
  47
  48 static void lmm_check_concurrency(lmm_system_t sys);
  49
  50 inline void lmm_decrease_concurrency(lmm_constraint_t cnstr){
  51   xbt_assert(cnstr->concurrency_current>0);
  52   cnstr->concurrency_current--;
  53 }
  54
  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!");
  59 }
  60
  61 void lmm_check_concurrency(lmm_system_t sys){
  62   void* _cnst;
  63   void* _elem;
  64   lmm_element_t elem;
  65   lmm_constraint_t cnst;
  66   int concurrency;
  67   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
  68
  69     xbt_swag_foreach(_cnst, &(sys->constraint_set)) {
  70       cnst = (lmm_constraint_t) _cnst;
  71       concurrency=0;
  72       if(cnst->concurrency_limit<0)
  73         continue;
  74       xbt_swag_foreach(_elem, &(cnst->element_set)) {
  75         elem = (lmm_element_t)_elem;
  76         if (elem->variable->weight > 0)
  77           concurrency++;
  78         else {
  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!");
  81             }
  82       }
  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!");
  85     }
  86
  87   }
  88 }
  89
  90 lmm_system_t lmm_system_new(int selective_update)
  91 {
  92   lmm_system_t l = NULL;
  93   s_lmm_variable_t var;
  94   s_lmm_constraint_t cnst;
  95
  96   l = xbt_new0(s_lmm_system_t, 1);
  97
  98   l->modified = 0;
  99   l->selective_update_active = selective_update;
 100   l->visited_counter = 1;
 101
 102   XBT_DEBUG("Setting selective_update_active flag to %d",
 103          l->selective_update_active);
 104
 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));
 109
 110   xbt_swag_init(&(l->active_constraint_set),
 111                 xbt_swag_offset(cnst, active_constraint_set_hookup));
 112
 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));
 119
 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);
 124
 125   return l;
 126 }
 127
 128 void lmm_system_free(lmm_system_t sys)
 129 {
 130   lmm_variable_t var = NULL;
 131   lmm_constraint_t cnst = NULL;
 132
 133
 134   while ((var = (lmm_variable_t) extract_variable(sys))) {
 135     XBT_WARN
 136         ("Variable %p (%d) still in  system when freing it: this may be a bug",
 137          var, var->id_int);
 138     lmm_var_free(sys, var);
 139   }
 140
 141   while ((cnst = (lmm_constraint_t) extract_constraint(sys)))
 142     lmm_cnst_free(sys, cnst);
 143
 144   xbt_mallocator_free(sys->variable_mallocator);
 145   free(sys);
 146 }
 147
 148 static XBT_INLINE void lmm_variable_remove(lmm_system_t sys, lmm_variable_t var)
 149 {
 150   int i;
 151   int nelements;
 152
 153   lmm_element_t elem = NULL;
 154
 155   XBT_IN("(sys=%p, var=%p)", sys, var);
 156   sys->modified = 1;
 157
 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);
 161
 162   for (i = 0; i < var->cnsts_number; i++) {
 163     elem = &var->cnsts[i];
 164     if(var->weight>0)
 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));
 169     if (!nelements)
 170       make_constraint_inactive(sys, elem->constraint);
 171   //Check if we can enable new variables going through the constraints where var was.
 172     else
 173       lmm_on_disabled_var(sys,elem->constraint);
 174   }
 175
 176   var->cnsts_number = 0;
 177   XBT_OUT();
 178 }
 179
 180 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var)
 181 {
 182
 183   lmm_variable_remove(sys, var);
 184   xbt_mallocator_release(sys->variable_mallocator, var);
 185 }
 186
 187 static XBT_INLINE void lmm_cnst_free(lmm_system_t sys,
 188                                      lmm_constraint_t cnst)
 189 {
 190 /*   xbt_assert(xbt_swag_size(&(cnst->element_set)), */
 191 /*         "This list should be empty!"); */
 192   make_constraint_inactive(sys, cnst);
 193   free(cnst);
 194 }
 195
 196 lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id,
 197                                     double bound_value)
 198 {
 199   lmm_constraint_t cnst = NULL;
 200   s_lmm_element_t elem;
 201
 202   cnst = xbt_new0(s_lmm_constraint_t, 1);
 203   cnst->id = id;
 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));
 209
 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;
 215   cnst->usage = 0;
 216   cnst->sharing_policy = 1; /* FIXME: don't hardcode the value */
 217   insert_constraint(sys, cnst);
 218
 219   return cnst;
 220 }
 221
 222 void lmm_constraint_concurrency_limit_set(lmm_constraint_t cnst, int concurrency_limit)
 223 {
 224   cnst->concurrency_limit = concurrency_limit;
 225 }
 226
 227 void lmm_constraint_concurrency_maximum_reset(lmm_constraint_t cnst)
 228 {
 229   cnst->concurrency_maximum = 0;
 230 }
 231
 232 int lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst)
 233 {
 234   return cnst->concurrency_maximum;
 235 }
 236
 237 void lmm_constraint_shared(lmm_constraint_t cnst)
 238 {
 239   cnst->sharing_policy = 0;
 240 }
 241
 242 /** Return true if the constraint is shared, and false if it's FATPIPE */
 243 int lmm_constraint_sharing_policy(lmm_constraint_t cnst)
 244 {
 245   return (cnst->sharing_policy);
 246 }
 247
 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.
 252  */
 253 XBT_INLINE void lmm_constraint_free(lmm_system_t sys,
 254                                     lmm_constraint_t cnst)
 255 {
 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);
 260 }
 261
 262 static void *lmm_variable_mallocator_new_f(void)
 263 {
 264   lmm_variable_t var = xbt_new(s_lmm_variable_t, 1);
 265   var->cnsts = NULL; /* will be created by realloc */
 266   return var;
 267 }
 268
 269 static void lmm_variable_mallocator_free_f(void *var)
 270 {
 271   xbt_free(((lmm_variable_t) var)->cnsts);
 272   xbt_free(var);
 273 }
 274
 275 lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id,
 276                                 double weight,
 277                                 double bound, int number_of_constraints)
 278 {
 279   lmm_variable_t var = NULL;
 280   int i;
 281
 282   XBT_IN("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)",
 283           sys, id, weight, bound, number_of_constraints);
 284
 285   var = (lmm_variable_t) xbt_mallocator_get(sys->variable_mallocator);
 286   var->id = id;
 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;
 297   }
 298   var->cnsts_size = number_of_constraints;
 299   var->cnsts_number = 0;
 300   var->weight = weight;
 301   var->staged_weight = 0.0;
 302   var->bound = bound;
 303   var->concurrency_share = 1;
 304   var->value = 0.0;
 305   var->visited = sys->visited_counter - 1;
 306   var->mu = 0.0;
 307   var->new_mu = 0.0;
 308   var->func_f = func_f_def;
 309   var->func_fp = func_fp_def;
 310   var->func_fpi = func_fpi_def;
 311
 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;
 316
 317   if (weight)
 318     xbt_swag_insert_at_head(var, &(sys->variable_set));
 319   else
 320     xbt_swag_insert_at_tail(var, &(sys->variable_set));
 321
 322   XBT_OUT(" returns %p", var);
 323   return var;
 324 }
 325
 326 void lmm_variable_free(lmm_system_t sys, lmm_variable_t var)
 327 {
 328   remove_variable(sys, var);
 329   lmm_var_free(sys, var);
 330 }
 331
 332 double lmm_variable_getvalue(lmm_variable_t var)
 333 {
 334   return (var->value);
 335 }
 336
 337
 338 void lmm_variable_concurrency_share_set(lmm_variable_t var, short int concurrency_share)
 339 {
 340   var->concurrency_share=concurrency_share;
 341 }
 342
 343 double lmm_variable_getbound(lmm_variable_t var)
 344 {
 345   return (var->bound);
 346 }
 347
 348 void lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
 349                 lmm_variable_t var)
 350 {
 351   lmm_element_t elem = NULL;
 352   int found = 0;
 353
 354   int i;
 355   for (i = 0; i < var->cnsts_number; i++) {
 356     elem = &(var->cnsts[i]);
 357     if (elem->constraint == cnst) {
 358       found = 1;
 359       break;
 360     }
 361   }
 362
 363   if (!found) {
 364     XBT_DEBUG("cnst %p is not found in var %p", cnst, var);
 365     return;
 366   }
 367
 368   sys->modified = 1;
 369
 370   XBT_DEBUG("remove elem(value %f, cnst %p, var %p) in var %p",
 371       elem->value, elem->constraint, elem->variable, var);
 372
 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)
 375    */
 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].
 379
 380   if(xbt_swag_remove(elem, &(elem->constraint->element_set)) && var->weight>0)
 381     lmm_decrease_concurrency(elem->constraint);
 382
 383   xbt_swag_remove(elem, &(elem->constraint->active_element_set));
 384   elem->constraint = NULL;
 385   elem->variable = NULL;
 386   elem->value = 0;
 387
 388   var->cnsts_number -= 1;
 389
 390   //No variable in this constraint -> make it inactive
 391   if (xbt_swag_size(&(cnst->element_set)) == 0)
 392     make_constraint_inactive(sys, cnst);
 393   else {
 394     //Check maxconcurrency to see if we can enable new variables
 395     lmm_on_disabled_var(sys,elem->constraint);
 396   }
 397
 398   lmm_check_concurrency(sys);
 399 }
 400
 401 void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
 402                 lmm_variable_t var, double value)
 403 {
 404   lmm_element_t elem = NULL;
 405   double weight;
 406   int i;
 407
 408   sys->modified = 1;
 409
 410   if(var->weight>0 && lmm_concurrency_slack(cnst)==0){
 411     weight=var->weight;
 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);
 415     value=0;
 416     var->staged_weight=weight;
 417     xbt_assert(!var->weight);
 418   }
 419
 420   xbt_assert(var->cnsts_number < var->cnsts_size, "Too much constraints");
 421
 422   elem = &(var->cnsts[var->cnsts_number++]);
 423
 424   elem->value = value;
 425   elem->constraint = cnst;
 426   elem->variable = var;
 427
 428
 429   if (var->weight){
 430     xbt_swag_insert_at_head(elem, &(elem->constraint->element_set));
 431     lmm_increase_concurrency(elem->constraint);
 432   }
 433   else
 434     xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set));
 435
 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);
 444   }
 445
 446   lmm_check_concurrency(sys);
 447 }
 448
 449 void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
 450                     lmm_variable_t var, double value)
 451 {
 452   int i;
 453   sys->modified = 1;
 454
 455   lmm_check_concurrency(sys);
 456
 457   for (i = 0; i < var->cnsts_number; i++)
 458     if (var->cnsts[i].constraint == cnst)
 459       break;
 460
 461   if (i < var->cnsts_number) {
 462     if (cnst->sharing_policy)
 463       var->cnsts[i].value += value;
 464     else
 465       var->cnsts[i].value = MAX(var->cnsts[i].value, value);
 466     lmm_update_modified_set(sys, cnst);
 467   } else
 468     lmm_expand(sys, cnst, var, value);
 469
 470   lmm_check_concurrency(sys);
 471 }
 472
 473 lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t /*sys*/,
 474                                                   lmm_variable_t var,
 475                                                   int num)
 476 {
 477   if (num < var->cnsts_number)
 478     return (var->cnsts[num].constraint);
 479   else
 480     return NULL;
 481 }
 482
 483 double lmm_get_cnst_weight_from_var(lmm_system_t /*sys*/,
 484                                                          lmm_variable_t var,
 485                                                          int num)
 486 {
 487   if (num < var->cnsts_number)
 488     return (var->cnsts[num].value);
 489   else
 490     return 0.0;
 491 }
 492
 493 int lmm_get_number_of_cnst_from_var(lmm_system_t /*sys*/,
 494                                                lmm_variable_t var)
 495 {
 496   return (var->cnsts_number);
 497 }
 498
 499 lmm_variable_t lmm_get_var_from_cnst(lmm_system_t /*sys*/,
 500                                      lmm_constraint_t cnst,
 501                                      lmm_element_t * elem)
 502 {
 503   if (!(*elem))
 504     *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->element_set));
 505   else
 506     *elem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->element_set.offset);
 507   if (*elem)
 508     return (*elem)->variable;
 509   else
 510     return NULL;
 511 }
 512
 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,
 519                                      int * numelem)
 520 {
 521   if (!(*elem)){
 522     *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->element_set));
 523     *numelem = xbt_swag_size(&(cnst->element_set))-1;
 524   }else{
 525     *elem = *nextelem;
 526     if(*numelem>0){
 527      (*numelem) --;
 528     }else
 529       return NULL;
 530   }
 531   if (*elem){
 532     *nextelem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->element_set.offset);
 533     return (*elem)->variable;
 534   }else
 535     return NULL;
 536 }
 537
 538 void *lmm_constraint_id(lmm_constraint_t cnst)
 539 {
 540   return cnst->id;
 541 }
 542
 543 void *lmm_variable_id(lmm_variable_t var)
 544 {
 545   return var->id;
 546 }
 547
 548 static XBT_INLINE void saturated_constraint_set_update(double usage,
 549                                                       int cnst_light_num,
 550                                                       dyn_light_t saturated_constraint_set,
 551                                                       double *min_usage)
 552 {
 553   xbt_assert(usage > 0,"Impossible");
 554
 555   if (*min_usage < 0 || *min_usage > usage) {
 556     *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));
 564     }
 565     saturated_constraint_set->data[saturated_constraint_set->pos] = cnst_light_num;
 566     saturated_constraint_set->pos++;
 567   }
 568 }
 569
 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,
 573     lmm_system_t sys)
 574 {
 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;
 577   void *_elem;
 578   lmm_element_t elem = NULL;
 579   xbt_swag_t elem_list = NULL;
 580   int i;
 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));
 590     }
 591   }
 592 }
 593
 594 void lmm_print(lmm_system_t sys)
 595 {
 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));
 605   double sum = 0.0;
 606
 607   /* Printing Objective */
 608   var_list = &(sys->variable_set);
 609   sprintf(print_buf, "MAX-MIN ( ");
 610   trace_buf = (char*)
 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);
 616     trace_buf = (char*)
 617         xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 618     strcat(trace_buf, print_buf);
 619   }
 620   sprintf(print_buf, ")");
 621   trace_buf = (char*)
 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';
 626
 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;
 632     sum = 0.0;
 633     elem_list = &(cnst->element_set);
 634     sprintf(print_buf, "\t");
 635     trace_buf = (char*)
 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");
 639     trace_buf = (char*)
 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)?"+":",");
 647       trace_buf = (char*)
 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;
 653       else
 654           sum = MAX(sum,elem->value * elem->variable->value);
 655     }
 656     sprintf(print_buf, "0) <= %f ('%d')", cnst->bound, cnst->id_int);
 657     trace_buf = (char*)
 658         xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 659     strcat(trace_buf, print_buf);
 660
 661     if (!cnst->sharing_policy) {
 662       sprintf(print_buf, " [MAX-Constraint]");
 663       trace_buf = (char*)
 664           xbt_realloc(trace_buf,
 665                       strlen(trace_buf) + strlen(print_buf) + 1);
 666       strcat(trace_buf, print_buf);
 667     }
 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);
 673   }
 674
 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,
 681              var->bound);
 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);
 685     } else {
 686       XBT_DEBUG("'%d'(%f) : %f", var->id_int, var->weight, var->value);
 687     }
 688   }
 689
 690   free(trace_buf);
 691 }
 692
 693 void lmm_solve(lmm_system_t sys)
 694 {
 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;
 704
 705   if (!(sys->modified))
 706     return;
 707
 708   XBT_IN("(sys=%p)", sys);
 709
 710   /*
 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.
 712    */
 713   cnst_list =
 714       sys->
 715       selective_update_active ? &(sys->modified_constraint_set) :
 716       &(sys->active_constraint_set);
 717
 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)
 727         break;
 728       var->value = 0.0;
 729     }
 730   }
 731
 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);
 737
 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))
 743       continue;
 744     cnst->usage = 0;
 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)
 750         break;
 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;
 756
 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);
 761       }
 762     }
 763     XBT_DEBUG("Constraint '%d' usage: %f remaining: %f ", cnst->id_int, cnst->usage, cnst->remaining);
 764     /* Saturated constraints update */
 765
 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!" );
 773       cnst_light_num++;
 774     }
 775   }
 776
 777   saturated_variable_set_update(  cnst_light_tab,
 778                                   saturated_constraint_set,
 779                                   sys);
 780
 781   /* Saturated variables update */
 782
 783   do {
 784     /* Fix the variables that have to be */
 785     var_list = &(sys->saturated_variable_set);
 786
 787     xbt_swag_foreach(_var, var_list) {
 788       var = (lmm_variable_t)_var;
 789       if (var->weight <= 0.0)
 790         DIE_IMPOSSIBLE;
 791       /* First check if some of these variables could reach their upper
 792          bound and update min_bound accordingly. */
 793       XBT_DEBUG
 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)) {
 798         if (min_bound < 0)
 799           min_bound = var->bound*var->weight;
 800         else
 801           min_bound = MIN(min_bound, (var->bound*var->weight));
 802         XBT_DEBUG("Updated min_bound=%f", min_bound);
 803       }
 804     }
 805
 806
 807     while ((var = (lmm_variable_t)xbt_swag_getFirst(var_list))) {
 808       int i;
 809
 810       if (min_bound < 0) {
 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);
 814       } else {
 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);
 819         }
 820         else {
 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);
 824           continue;
 825         }
 826       }
 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);
 829
 830
 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];
 847               cnst_light_num--;
 848               cnst->cnst_light = NULL;
 849             }
 850           } else {
 851             cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage;
 852           }
 853           make_elem_inactive(elem);
 854         } else {
 855           //Remember: non-shared constraints only require that max(elem->value * var->value) < cnst->bound
 856           cnst->usage = 0.0;
 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;
 863             if (elem->value > 0)
 864               cnst->usage = MAX(cnst->usage, elem->value / elem->variable->weight);
 865           }
 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];
 874               cnst_light_num--;
 875               cnst->cnst_light = NULL;
 876             }
 877           } else {
 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." );
 880           }
 881         }
 882       }
 883       xbt_swag_remove(var, var_list);
 884     }
 885
 886     /* Find out which variables reach the maximum */
 887     min_usage = -1;
 888     min_bound = -1;
 889     saturated_constraint_set->pos = 0;
 890     int pos;
 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,
 895           pos,
 896           saturated_constraint_set,
 897           &min_usage);
 898         }
 899
 900     saturated_variable_set_update(  cnst_light_tab,
 901                                     saturated_constraint_set,
 902                                     sys);
 903
 904   } while (cnst_light_num > 0);
 905
 906   sys->modified = 0;
 907   if (sys->selective_update_active)
 908     lmm_remove_all_modified_set(sys);
 909
 910   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
 911     lmm_print(sys);
 912   }
 913
 914   xbt_free(saturated_constraint_set->data);
 915   xbt_free(saturated_constraint_set);
 916   xbt_free(cnst_light_tab);
 917   XBT_OUT();
 918 }
 919
 920
 921 /** \brief Attribute the value bound to var->bound.
 922  *
 923  *  \param sys the lmm_system_t
 924  *  \param var the lmm_variable_t
 925  *  \param bound the new bound to associate with var
 926  *
 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.
 931  *
 932 */
 933 void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
 934     double bound)
 935 {
 936   sys->modified = 1;
 937   var->bound = bound;
 938
 939   if (var->cnsts_number)
 940     lmm_update_modified_set(sys, var->cnsts[0].constraint);
 941 }
 942
 943
 944
 945 int lmm_concurrency_slack(lmm_constraint_t cnstr){
 946
 947   int slack;
 948   int concurrency=0;
 949   void* _elem;
 950   lmm_element_t elem;
 951
 952   //FIXME MARTIN: Replace by infinite value std::numeric_limits<int>::(max)(), or something better within Simgrid?
 953   if(cnstr->concurrency_limit<0)
 954     return 666;
 955
 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
 960       concurrency++;
 961     }
 962
 963     slack=cnstr->concurrency_limit-concurrency;
 964     xbt_assert(slack>=0,"concurrency slack should not be negative!");
 965     return slack;
 966   }
 967
 968   return  cnstr->concurrency_limit - cnstr->concurrency_current;
 969
 970 }
 971
 972 /** \brief Measure the minimum concurrency slack across all constraints where var is involved
 973  *
 974  * \param The variable to check for
 975  *
 976  */
 977 int lmm_cnstrs_min_concurrency_slack(lmm_variable_t var){
 978   int i;
 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);
 983
 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))
 987       return 0;
 988
 989     if(minslack>slack)
 990       minslack=slack;
 991   }
 992
 993   return minslack;
 994 }
 995
 996 /* /Check if a variable can be enabled
 997  *
 998  * Make sure to set staged_weight before, if your intent is only to check concurrency
 999  */
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;
1002 }
1003
1004
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)
1007
1008 void lmm_enable_var(lmm_system_t sys, lmm_variable_t var){
1009
1010   int i;
1011   lmm_element_t elem;
1012
1013   xbt_assert(lmm_can_enable_var(var));
1014   lmm_check_concurrency(sys);
1015
1016   var->weight = var->staged_weight;
1017   var->staged_weight = 0;
1018
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.
1020
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);
1028   }
1029   if (var->cnsts_number)
1030     lmm_update_modified_set(sys, var->cnsts[0].constraint);
1031
1032   lmm_check_concurrency(sys);
1033 }
1034
1035 void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){
1036   int i;
1037   lmm_element_t elem;
1038
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));
1049
1050     xbt_swag_remove(elem, &(elem->constraint->active_element_set));
1051
1052     lmm_decrease_concurrency(elem->constraint);
1053   }
1054
1055   var->weight=0.0;
1056   var->staged_weight=0.0;
1057   var->value = 0.0;
1058   lmm_check_concurrency(sys);
1059 }
1060
1061 /* /brief Find variables that can be enabled and enable them.
1062  *
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
1067  */
1068 void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr){
1069
1070   lmm_element_t elem;
1071   if(cnstr->concurrency_limit<0)
1072     return;
1073
1074   int concurrency=0;
1075   xbt_swag_foreach(elem, &(cnstr->element_set)) {
1076
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){
1079       concurrency++;
1080       xbt_assert(elem->variable->staged_weight==0.0,"Staged weight should have been reset");
1081     } else if (elem->variable->staged_weight>0 )
1082       {
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);
1087           concurrency++;
1088         }
1089       }
1090
1091     xbt_assert(concurrency<=cnstr->concurrency_limit,"Concurrency overflow!");
1092     if(concurrency==cnstr->concurrency_limit)
1093       break;
1094   }
1095
1096   lmm_check_concurrency(sys);
1097
1098 }
1099
1100 /* \brief update the weight of a variable, and enable/disable it.
1101  * @return Returns whether a change was made
1102  */
1103 void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var,
1104                                double weight)
1105 {
1106   int minslack;
1107
1108   xbt_assert(weight>=0,"Variable weight should not be negative!");
1109
1110   if (weight == var->weight)
1111     return;
1112
1113   int enabling_var=  (weight>0 && var->weight<=0);
1114   int disabling_var= (weight<=0 && var->weight>0);
1115
1116   XBT_IN("(sys=%p, var=%p, weight=%f)", sys, var, weight);
1117
1118   sys->modified = 1;
1119
1120   //Are we enabling this variable?
1121   if (enabling_var){
1122     var->staged_weight = weight;
1123     minslack=lmm_cnstrs_min_concurrency_slack(var);
1124     if(minslack==0){
1125       XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack %i, with weight %f", minslack, weight);
1126       return;
1127     }
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);
1133   } else {
1134     var->weight=weight;
1135   }
1136
1137   lmm_check_concurrency(sys);
1138
1139   XBT_OUT();
1140   return;
1141 }
1142
1143 double lmm_get_variable_weight(lmm_variable_t var)
1144 {
1145   return var->weight;
1146 }
1147
1148 void lmm_update_constraint_bound(lmm_system_t sys,
1149                                             lmm_constraint_t cnst,
1150                                             double bound)
1151 {
1152   sys->modified = 1;
1153   lmm_update_modified_set(sys, cnst);
1154   cnst->bound = bound;
1155 }
1156
1157 int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst)
1158 {
1159   return xbt_swag_belongs(cnst, &(sys->active_constraint_set));
1160 }
1161
1162 XBT_INLINE lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t
1163                                                             sys)
1164 {
1165   return (lmm_constraint_t)xbt_swag_getFirst(&(sys->active_constraint_set));
1166 }
1167
1168 XBT_INLINE lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t
1169                                                            sys,
1170                                                            lmm_constraint_t
1171                                                            cnst)
1172 {
1173   return (lmm_constraint_t)xbt_swag_getNext(cnst, (sys->active_constraint_set).offset);
1174 }
1175
1176 #ifdef HAVE_LATENCY_BOUND_TRACKING
1177 XBT_INLINE int lmm_is_variable_limited_by_latency(lmm_variable_t var)
1178 {
1179   return (double_equals(var->bound, var->value, var->bound*sg_maxmin_precision));
1180 }
1181 #endif
1182
1183
1184 /** \brief Update the constraint set propagating recursively to
1185  *  other constraints so the system should not be entirely computed.
1186  *
1187  *  \param sys the lmm_system_t
1188  *  \param cnst the lmm_constraint_t affected by the change
1189  *
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.
1193  */
1194 static void lmm_update_modified_set_rec(lmm_system_t sys,
1195                                         lmm_constraint_t cnst)
1196 {
1197   void* _elem;
1198
1199   //TODOLATER: Why lmm_modified_set has been changed in git version 2392B5157...? Looks equivalent logically and less obvious..
1200
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;
1204     int i;
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) */
1206     if(var->weight<=0)
1207       break;
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);
1215       }
1216     }
1217     //var will be ignored in later visits as long as sys->visited_counter does not move
1218     var->visited = sys->visited_counter;
1219   }
1220 }
1221
1222 static void lmm_update_modified_set(lmm_system_t sys,
1223                                     lmm_constraint_t cnst)
1224 {
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);
1230   }
1231 }
1232
1233 /** \brief Remove all constraints of the modified_constraint_set.
1234  *
1235  *  \param sys the lmm_system_t
1236  *
1237  */
1238 static void lmm_remove_all_modified_set(lmm_system_t sys)
1239 {
1240
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 */
1246         void *_var;
1247     xbt_swag_foreach(_var, &sys->variable_set)
1248       ((lmm_variable_t)_var)->visited = 0;
1249   }
1250   xbt_swag_reset(&sys->modified_constraint_set);
1251 }
1252
1253 /**
1254  *  Returns total resource load
1255  *
1256  * \param cnst the lmm_constraint_t associated to the resource
1257  *
1258  *
1259  * This is dead code, but we may use it later for debug/trace.
1260  */
1261 double lmm_constraint_get_usage(lmm_constraint_t cnst) {
1262    double usage = 0.0;
1263    xbt_swag_t elem_list = &(cnst->element_set);
1264    void *_elem;
1265    lmm_element_t elem = NULL;
1266
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)
1271        break;
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;
1277      }
1278    }
1279   return usage;
1280 }
1281
1282