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 lmm_system_t lmm_system_new(int selective_update)
  62 {
  63   lmm_system_t l = NULL;
  64   s_lmm_variable_t var;
  65   s_lmm_constraint_t cnst;
  66
  67   l = xbt_new0(s_lmm_system_t, 1);
  68
  69   l->modified = 0;
  70   l->selective_update_active = selective_update;
  71   l->visited_counter = 1;
  72
  73   XBT_DEBUG("Setting selective_update_active flag to %d",
  74          l->selective_update_active);
  75
  76   xbt_swag_init(&(l->variable_set),
  77                 xbt_swag_offset(var, variable_set_hookup));
  78   xbt_swag_init(&(l->constraint_set),
  79                 xbt_swag_offset(cnst, constraint_set_hookup));
  80
  81   xbt_swag_init(&(l->active_constraint_set),
  82                 xbt_swag_offset(cnst, active_constraint_set_hookup));
  83
  84   xbt_swag_init(&(l->modified_constraint_set),
  85                 xbt_swag_offset(cnst, modified_constraint_set_hookup));
  86   xbt_swag_init(&(l->saturated_variable_set),
  87                 xbt_swag_offset(var, saturated_variable_set_hookup));
  88   xbt_swag_init(&(l->saturated_constraint_set),
  89                 xbt_swag_offset(cnst, saturated_constraint_set_hookup));
  90
  91   l->variable_mallocator = xbt_mallocator_new(65536,
  92                                               lmm_variable_mallocator_new_f,
  93                                               lmm_variable_mallocator_free_f,
  94                                               lmm_variable_mallocator_reset_f);
  95
  96   return l;
  97 }
  98
  99 void lmm_system_free(lmm_system_t sys)
 100 {
 101   lmm_variable_t var = NULL;
 102   lmm_constraint_t cnst = NULL;
 103
 104
 105   while ((var = (lmm_variable_t) extract_variable(sys))) {
 106     XBT_WARN
 107         ("Variable %p (%d) still in  system when freing it: this may be a bug",
 108          var, var->id_int);
 109     lmm_var_free(sys, var);
 110   }
 111
 112   while ((cnst = (lmm_constraint_t) extract_constraint(sys)))
 113     lmm_cnst_free(sys, cnst);
 114
 115   xbt_mallocator_free(sys->variable_mallocator);
 116   free(sys);
 117 }
 118
 119 static XBT_INLINE void lmm_variable_remove(lmm_system_t sys, lmm_variable_t var)
 120 {
 121   int i;
 122   int nelements;
 123
 124   lmm_element_t elem = NULL;
 125
 126   XBT_IN("(sys=%p, var=%p)", sys, var);
 127   sys->modified = 1;
 128
 129   //TODOLATER Can do better than that by leaving only the variable in only one enabled_element_set, call lmm_update_modified_set, and then remove it..
 130   if(var->cnsts_number)
 131       lmm_update_modified_set(sys, var->cnsts[0].constraint);
 132
 133   for (i = 0; i < var->cnsts_number; i++) {
 134     elem = &var->cnsts[i];
 135     if(var->weight>0)
 136       lmm_decrease_concurrency(elem->constraint);
 137     xbt_swag_remove(elem, &(elem->constraint->enabled_element_set));
 138     xbt_swag_remove(elem, &(elem->constraint->disabled_element_set));
 139     xbt_swag_remove(elem, &(elem->constraint->active_element_set));
 140     nelements=xbt_swag_size(&(elem->constraint->enabled_element_set)) +
 141               xbt_swag_size(&(elem->constraint->disabled_element_set));
 142     if (!nelements)
 143       make_constraint_inactive(sys, elem->constraint);
 144   //Check if we can enable new variables going through the constraints where var was.
 145     else
 146       lmm_on_disabled_var(sys,elem->constraint);
 147   }
 148
 149   var->cnsts_number = 0;
 150   XBT_OUT();
 151 }
 152
 153 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var)
 154 {
 155
 156   lmm_variable_remove(sys, var);
 157   xbt_mallocator_release(sys->variable_mallocator, var);
 158 }
 159
 160 static XBT_INLINE void lmm_cnst_free(lmm_system_t sys,
 161                                      lmm_constraint_t cnst)
 162 {
 163   make_constraint_inactive(sys, cnst);
 164   free(cnst);
 165 }
 166
 167 lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id,
 168                                     double bound_value)
 169 {
 170   lmm_constraint_t cnst = NULL;
 171   s_lmm_element_t elem;
 172
 173   cnst = xbt_new0(s_lmm_constraint_t, 1);
 174   cnst->id = id;
 175   cnst->id_int = Global_const_debug_id++;
 176   xbt_swag_init(&(cnst->enabled_element_set),
 177                 xbt_swag_offset(elem, enabled_element_set_hookup));
 178   xbt_swag_init(&(cnst->disabled_element_set),
 179                 xbt_swag_offset(elem, disabled_element_set_hookup));
 180   xbt_swag_init(&(cnst->active_element_set),
 181                 xbt_swag_offset(elem, active_element_set_hookup));
 182
 183   cnst->bound = bound_value;
 184   cnst->concurrency_maximum=0;
 185   cnst->concurrency_current=0;
 186   //TODO MARTIN Maybe a configuration item for the default cap concurrency?
 187   cnst->concurrency_limit=100;
 188   cnst->usage = 0;
 189   cnst->sharing_policy = 1; /* FIXME: don't hardcode the value */
 190   insert_constraint(sys, cnst);
 191
 192   return cnst;
 193 }
 194
 195 void lmm_constraint_concurrency_limit_set(lmm_constraint_t cnst, int concurrency_limit)
 196 {
 197   cnst->concurrency_limit = concurrency_limit;
 198 }
 199
 200 void lmm_constraint_concurrency_maximum_reset(lmm_constraint_t cnst)
 201 {
 202   cnst->concurrency_maximum = 0;
 203 }
 204
 205 int lmm_constraint_concurrency_maximum_get(lmm_constraint_t cnst)
 206 {
 207   return cnst->concurrency_maximum;
 208 }
 209
 210 void lmm_constraint_shared(lmm_constraint_t cnst)
 211 {
 212   cnst->sharing_policy = 0;
 213 }
 214
 215 /** Return true if the constraint is shared, and false if it's FATPIPE */
 216 int lmm_constraint_sharing_policy(lmm_constraint_t cnst)
 217 {
 218   return (cnst->sharing_policy);
 219 }
 220
 221 /* @brief Remove a constraint
 222  * Currently this is dead code, but it is exposed in maxmin.h
 223  * Apparently, this call was designed assuming that constraint would no more have elements in it.
 224  * If this is not the case, assertion will fail, and you need to add calls e.g. to lmm_shrink before effectively removing it.
 225  */
 226 XBT_INLINE void lmm_constraint_free(lmm_system_t sys,
 227                                     lmm_constraint_t cnst)
 228 {
 229   xbt_assert(!xbt_swag_size(&(cnst->active_element_set)),"Removing constraint but it still has active elements");
 230   xbt_assert(!xbt_swag_size(&(cnst->enabled_element_set)),"Removing constraint but it still has enabled elements");
 231   xbt_assert(!xbt_swag_size(&(cnst->disabled_element_set)),"Removing constraint but it still has disabled elements");
 232   remove_constraint(sys, cnst);
 233   lmm_cnst_free(sys, cnst);
 234 }
 235
 236 static void *lmm_variable_mallocator_new_f(void)
 237 {
 238   lmm_variable_t var = xbt_new(s_lmm_variable_t, 1);
 239   var->cnsts = NULL; /* will be created by realloc */
 240   return var;
 241 }
 242
 243 static void lmm_variable_mallocator_free_f(void *var)
 244 {
 245   xbt_free(((lmm_variable_t) var)->cnsts);
 246   xbt_free(var);
 247 }
 248
 249 lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id,
 250                                 double weight,
 251                                 double bound, int number_of_constraints)
 252 {
 253   lmm_variable_t var = NULL;
 254   int i;
 255
 256   XBT_IN("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)",
 257           sys, id, weight, bound, number_of_constraints);
 258
 259   var = (lmm_variable_t) xbt_mallocator_get(sys->variable_mallocator);
 260   var->id = id;
 261   var->id_int = Global_debug_id++;
 262   var->cnsts = (s_lmm_element_t *) xbt_realloc(var->cnsts, number_of_constraints * sizeof(s_lmm_element_t));
 263   for (i = 0; i < number_of_constraints; i++) {
 264     var->cnsts[i].enabled_element_set_hookup.next = NULL;
 265     var->cnsts[i].enabled_element_set_hookup.prev = NULL;
 266     var->cnsts[i].disabled_element_set_hookup.next = NULL;
 267     var->cnsts[i].disabled_element_set_hookup.prev = NULL;
 268     var->cnsts[i].active_element_set_hookup.next = NULL;
 269     var->cnsts[i].active_element_set_hookup.prev = NULL;
 270     var->cnsts[i].constraint = NULL;
 271     var->cnsts[i].variable = NULL;
 272     var->cnsts[i].value = 0.0;
 273   }
 274   var->cnsts_size = number_of_constraints;
 275   var->cnsts_number = 0;
 276   var->weight = weight;
 277   var->staged_weight = 0.0;
 278   var->bound = bound;
 279   var->concurrency_share = 1;
 280   var->value = 0.0;
 281   var->visited = sys->visited_counter - 1;
 282   var->mu = 0.0;
 283   var->new_mu = 0.0;
 284   var->func_f = func_f_def;
 285   var->func_fp = func_fp_def;
 286   var->func_fpi = func_fpi_def;
 287
 288   var->variable_set_hookup.next = NULL;
 289   var->variable_set_hookup.prev = NULL;
 290   var->saturated_variable_set_hookup.next = NULL;
 291   var->saturated_variable_set_hookup.prev = NULL;
 292
 293   if (weight)
 294     xbt_swag_insert_at_head(var, &(sys->variable_set));
 295   else
 296     xbt_swag_insert_at_tail(var, &(sys->variable_set));
 297
 298   XBT_OUT(" returns %p", var);
 299   return var;
 300 }
 301
 302 void lmm_variable_free(lmm_system_t sys, lmm_variable_t var)
 303 {
 304   remove_variable(sys, var);
 305   lmm_var_free(sys, var);
 306 }
 307
 308 double lmm_variable_getvalue(lmm_variable_t var)
 309 {
 310   return (var->value);
 311 }
 312
 313
 314 void lmm_variable_concurrency_share_set(lmm_variable_t var, short int concurrency_share)
 315 {
 316   var->concurrency_share=concurrency_share;
 317 }
 318
 319 double lmm_variable_getbound(lmm_variable_t var)
 320 {
 321   return (var->bound);
 322 }
 323
 324 void lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
 325                 lmm_variable_t var)
 326 {
 327   lmm_element_t elem = NULL;
 328   int found = 0;
 329
 330   int i;
 331   for (i = 0; i < var->cnsts_number; i++) {
 332     elem = &(var->cnsts[i]);
 333     if (elem->constraint == cnst) {
 334       found = 1;
 335       break;
 336     }
 337   }
 338
 339   if (!found) {
 340     XBT_DEBUG("cnst %p is not found in var %p", cnst, var);
 341     return;
 342   }
 343
 344   sys->modified = 1;
 345
 346   XBT_DEBUG("remove elem(value %f, cnst %p, var %p) in var %p",
 347       elem->value, elem->constraint, elem->variable, var);
 348
 349   /* We are going to change the constraint object and the variable object.
 350    * Propagate this change to other objects. Calling here before removing variable from not active elements (inactive elements are not visited)
 351    */
 352   lmm_update_modified_set(sys, cnst);
 353   //Useful in case var was already removed from the constraint
 354   lmm_update_modified_set(sys, var->cnsts[0].constraint); // will look up enabled_element_set of this constraint, and then each var in the enabled_element_set, and each var->cnsts[i].
 355
 356   if(xbt_swag_remove(elem, &(elem->constraint->enabled_element_set)))
 357     lmm_decrease_concurrency(elem->constraint);
 358
 359   xbt_swag_remove(elem, &(elem->constraint->active_element_set));
 360   elem->constraint = NULL;
 361   elem->variable = NULL;
 362   elem->value = 0;
 363
 364   var->cnsts_number -= 1;
 365
 366   //No variable in this constraint -> make it inactive
 367   if (xbt_swag_size(&(cnst->enabled_element_set))+xbt_swag_size(&(cnst->disabled_element_set)) == 0)
 368     make_constraint_inactive(sys, cnst);
 369   else {
 370     //Check maxconcurrency to see if we can enable new variables
 371     lmm_on_disabled_var(sys,elem->constraint);
 372   }
 373
 374   lmm_check_concurrency(sys);
 375 }
 376
 377 void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
 378                 lmm_variable_t var, double value)
 379 {
 380   lmm_element_t elem = NULL;
 381   double weight;
 382   int i;
 383
 384   sys->modified = 1;
 385
 386   if(var->weight>0 && lmm_concurrency_slack(cnst)==0){
 387     weight=var->weight;
 388     lmm_disable_var(sys,var);
 389     for (i = 0; i < var->cnsts_number; i++)
 390       lmm_on_disabled_var(sys,var->cnsts[i].constraint);
 391     value=0;
 392     var->staged_weight=weight;
 393     xbt_assert(!var->weight);
 394   }
 395
 396   xbt_assert(var->cnsts_number < var->cnsts_size, "Too much constraints");
 397
 398   elem = &(var->cnsts[var->cnsts_number++]);
 399
 400   elem->value = value;
 401   elem->constraint = cnst;
 402   elem->variable = var;
 403
 404
 405   if (var->weight){
 406     xbt_swag_insert_at_head(elem, &(elem->constraint->enabled_element_set));
 407     lmm_increase_concurrency(elem->constraint);
 408   }
 409   else
 410     xbt_swag_insert_at_tail(elem, &(elem->constraint->disabled_element_set));
 411
 412   if(!sys->selective_update_active) {
 413     make_constraint_active(sys, cnst);
 414   } else if(elem->value>0 || var->weight >0) {
 415     make_constraint_active(sys, cnst);
 416     lmm_update_modified_set(sys, cnst);
 417     //TODOLATER: Why do we need this second call?
 418     if (var->cnsts_number > 1)
 419       lmm_update_modified_set(sys, var->cnsts[0].constraint);
 420   }
 421
 422   lmm_check_concurrency(sys);
 423 }
 424
 425 void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
 426                     lmm_variable_t var, double value)
 427 {
 428   int i;
 429   sys->modified = 1;
 430
 431   lmm_check_concurrency(sys);
 432
 433   for (i = 0; i < var->cnsts_number; i++)
 434     if (var->cnsts[i].constraint == cnst)
 435       break;
 436
 437   if (i < var->cnsts_number) {
 438     if (cnst->sharing_policy)
 439       var->cnsts[i].value += value;
 440     else
 441       var->cnsts[i].value = MAX(var->cnsts[i].value, value);
 442     lmm_update_modified_set(sys, cnst);
 443   } else
 444     lmm_expand(sys, cnst, var, value);
 445
 446   lmm_check_concurrency(sys);
 447 }
 448
 449 lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t /*sys*/,
 450                                                   lmm_variable_t var,
 451                                                   int num)
 452 {
 453   if (num < var->cnsts_number)
 454     return (var->cnsts[num].constraint);
 455   else
 456     return NULL;
 457 }
 458
 459 double lmm_get_cnst_weight_from_var(lmm_system_t /*sys*/,
 460                                                          lmm_variable_t var,
 461                                                          int num)
 462 {
 463   if (num < var->cnsts_number)
 464     return (var->cnsts[num].value);
 465   else
 466     return 0.0;
 467 }
 468
 469 int lmm_get_number_of_cnst_from_var(lmm_system_t /*sys*/,
 470                                                lmm_variable_t var)
 471 {
 472   return (var->cnsts_number);
 473 }
 474
 475 lmm_variable_t lmm_get_var_from_cnst(lmm_system_t /*sys*/,
 476                                      lmm_constraint_t cnst,
 477                                      lmm_element_t * elem)
 478 {
 479
 480   if (!(*elem)) {
 481     //That is the first call, pick the first element among enabled_element_set (or disabled_element_set if enabled_element_set is empty)
 482     *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->enabled_element_set));
 483     if (!(*elem))
 484       *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set));
 485   }  else {
 486     //elem is not null, so we carry on
 487     if(xbt_swag_belongs(*elem,&(cnst->enabled_element_set))){
 488       //Look at enabled_element_set, and jump to disabled_element_set when finished
 489       *elem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->enabled_element_set.offset);
 490       if (!(*elem))
 491   *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set));
 492     } else {
 493       *elem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->disabled_element_set.offset);
 494     }
 495   }
 496   if (*elem)
 497     return (*elem)->variable;
 498   else
 499     return NULL;
 500 }
 501
 502 //if we modify the swag between calls, normal version may loop forever
 503 //this safe version ensures that we browse the swag elements only once
 504 lmm_variable_t lmm_get_var_from_cnst_safe(lmm_system_t /*sys*/,
 505                                      lmm_constraint_t cnst,
 506                                      lmm_element_t * elem,
 507                                      lmm_element_t * nextelem,
 508                                      int * numelem)
 509 {
 510   if (!(*elem)){
 511     *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->enabled_element_set));
 512     *numelem = xbt_swag_size(&(cnst->enabled_element_set))+xbt_swag_size(&(cnst->disabled_element_set))-1;
 513     if (!(*elem))
 514       *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set));
 515   }else{
 516     *elem = *nextelem;
 517     if(*numelem>0){
 518      (*numelem) --;
 519     }else
 520       return NULL;
 521   }
 522   if (*elem){
 523     //elem is not null, so we carry on
 524     if(xbt_swag_belongs(*elem,&(cnst->enabled_element_set))){
 525       //Look at enabled_element_set, and jump to disabled_element_set when finished
 526       *nextelem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->enabled_element_set.offset);
 527       if (!(*nextelem))
 528   *nextelem = (lmm_element_t) xbt_swag_getFirst(&(cnst->disabled_element_set));
 529     } else {
 530       *nextelem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->disabled_element_set.offset);
 531     }
 532     return (*elem)->variable;
 533   }else
 534     return NULL;
 535 }
 536
 537 void *lmm_constraint_id(lmm_constraint_t cnst)
 538 {
 539   return cnst->id;
 540 }
 541
 542 void *lmm_variable_id(lmm_variable_t var)
 543 {
 544   return var->id;
 545 }
 546
 547 static XBT_INLINE void saturated_constraint_set_update(double usage,
 548                                                       int cnst_light_num,
 549                                                       dyn_light_t saturated_constraint_set,
 550                                                       double *min_usage)
 551 {
 552   xbt_assert(usage > 0,"Impossible");
 553
 554   if (*min_usage < 0 || *min_usage > usage) {
 555     *min_usage = usage;
 556     XBT_HERE(" min_usage=%f (cnst->remaining / cnst->usage =%f)", *min_usage, usage);
 557     saturated_constraint_set->data[0] = cnst_light_num;
 558     saturated_constraint_set->pos = 1;
 559   } else if (*min_usage == usage) {
 560     if(saturated_constraint_set->pos == saturated_constraint_set->size) { // realloc the size
 561       saturated_constraint_set->size *= 2;
 562       saturated_constraint_set->data = (int*) xbt_realloc(saturated_constraint_set->data, (saturated_constraint_set->size) * sizeof(int));
 563     }
 564     saturated_constraint_set->data[saturated_constraint_set->pos] = cnst_light_num;
 565     saturated_constraint_set->pos++;
 566   }
 567 }
 568
 569 static XBT_INLINE void saturated_variable_set_update(
 570     s_lmm_constraint_light_t *cnst_light_tab,
 571     dyn_light_t saturated_constraint_set,
 572     lmm_system_t sys)
 573 {
 574   /* Add active variables (i.e. variables that need to be set) from the set of constraints to saturate (cnst_light_tab)*/
 575   lmm_constraint_light_t cnst = NULL;
 576   void *_elem;
 577   lmm_element_t elem = NULL;
 578   xbt_swag_t elem_list = NULL;
 579   int i;
 580   for(i = 0; i< saturated_constraint_set->pos; i++){
 581     cnst = &cnst_light_tab[saturated_constraint_set->data[i]];
 582     elem_list = &(cnst->cnst->active_element_set);
 583     xbt_swag_foreach(_elem, elem_list) {
 584       elem = (lmm_element_t)_elem;
 585       //Visiting active_element_set, so, by construction, should never get a zero weight, correct?
 586       xbt_assert(elem->variable->weight > 0);
 587       if ((elem->value > 0))
 588         xbt_swag_insert(elem->variable, &(sys->saturated_variable_set));
 589     }
 590   }
 591 }
 592
 593 void lmm_print(lmm_system_t sys)
 594 {
 595   void *_cnst, *_elem, *_var;
 596   lmm_constraint_t cnst = NULL;
 597   lmm_element_t elem = NULL;
 598   lmm_variable_t var = NULL;
 599   xbt_swag_t cnst_list = NULL;
 600   xbt_swag_t var_list = NULL;
 601   xbt_swag_t elem_list = NULL;
 602   char print_buf[1024];
 603   char *trace_buf = (char*) xbt_malloc0(sizeof(char));
 604   double sum = 0.0;
 605
 606   /* Printing Objective */
 607   var_list = &(sys->variable_set);
 608   sprintf(print_buf, "MAX-MIN ( ");
 609   trace_buf = (char*)
 610       xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 611   strcat(trace_buf, print_buf);
 612   xbt_swag_foreach(_var, var_list) {
 613   var = (lmm_variable_t)_var;
 614     sprintf(print_buf, "'%d'(%f) ", var->id_int, var->weight);
 615     trace_buf = (char*)
 616         xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 617     strcat(trace_buf, print_buf);
 618   }
 619   sprintf(print_buf, ")");
 620   trace_buf = (char*)
 621       xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 622   strcat(trace_buf, print_buf);
 623   XBT_DEBUG("%20s", trace_buf);
 624   trace_buf[0] = '\000';
 625
 626   XBT_DEBUG("Constraints");
 627   /* Printing Constraints */
 628   cnst_list = &(sys->active_constraint_set);
 629   xbt_swag_foreach(_cnst, cnst_list) {
 630   cnst = (lmm_constraint_t)_cnst;
 631     sum = 0.0;
 632     //Show  the enabled variables
 633     elem_list = &(cnst->enabled_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     //TODO: Adding disabled elements only for test compatibility, but do we really want them to be printed?
 657     elem_list = &(cnst->disabled_element_set);
 658     xbt_swag_foreach(_elem, elem_list) {
 659       elem = (lmm_element_t)_elem;
 660       sprintf(print_buf, "%f.'%d'(%f) %s ", elem->value,
 661               elem->variable->id_int, elem->variable->value,(cnst->sharing_policy)?"+":",");
 662       trace_buf = (char*)
 663           xbt_realloc(trace_buf,
 664                       strlen(trace_buf) + strlen(print_buf) + 1);
 665       strcat(trace_buf, print_buf);
 666       if(cnst->sharing_policy)
 667         sum += elem->value * elem->variable->value;
 668       else
 669         sum = MAX(sum,elem->value * elem->variable->value);
 670     }
 671
 672     sprintf(print_buf, "0) <= %f ('%d')", cnst->bound, cnst->id_int);
 673     trace_buf = (char*)
 674         xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 675     strcat(trace_buf, print_buf);
 676
 677     if (!cnst->sharing_policy) {
 678       sprintf(print_buf, " [MAX-Constraint]");
 679       trace_buf = (char*)
 680           xbt_realloc(trace_buf,
 681                       strlen(trace_buf) + strlen(print_buf) + 1);
 682       strcat(trace_buf, print_buf);
 683     }
 684     XBT_DEBUG("%s", trace_buf);
 685     trace_buf[0] = '\000';
 686     xbt_assert(!double_positive(sum - cnst->bound, cnst->bound*sg_maxmin_precision),
 687                 "Incorrect value (%f is not smaller than %f): %g",
 688                 sum, cnst->bound, sum - cnst->bound);
 689   }
 690
 691   XBT_DEBUG("Variables");
 692   /* Printing Result */
 693   xbt_swag_foreach(_var, var_list) {
 694   var = (lmm_variable_t)_var;
 695     if (var->bound > 0) {
 696       XBT_DEBUG("'%d'(%f) : %f (<=%f)", var->id_int, var->weight, var->value,
 697              var->bound);
 698       xbt_assert(!double_positive(var->value - var->bound, var->bound*sg_maxmin_precision),
 699                   "Incorrect value (%f is not smaller than %f",
 700                   var->value, var->bound);
 701     } else {
 702       XBT_DEBUG("'%d'(%f) : %f", var->id_int, var->weight, var->value);
 703     }
 704   }
 705
 706   free(trace_buf);
 707 }
 708
 709 void lmm_solve(lmm_system_t sys)
 710 {
 711   void *_var, *_cnst, *_cnst_next, *_elem;
 712   lmm_variable_t var = NULL;
 713   lmm_constraint_t cnst = NULL;
 714   lmm_element_t elem = NULL;
 715   xbt_swag_t cnst_list = NULL;
 716   xbt_swag_t var_list = NULL;
 717   xbt_swag_t elem_list = NULL;
 718   double min_usage = -1;
 719   double min_bound = -1;
 720
 721   if (!(sys->modified))
 722     return;
 723
 724   XBT_IN("(sys=%p)", sys);
 725
 726   /*
 727    * 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.
 728    */
 729   cnst_list =
 730       sys->
 731       selective_update_active ? &(sys->modified_constraint_set) :
 732       &(sys->active_constraint_set);
 733
 734   XBT_DEBUG("Active constraints : %d", xbt_swag_size(cnst_list));
 735   /* Init: Only modified code portions: reset the value of active variables */
 736   xbt_swag_foreach(_cnst, cnst_list) {
 737   cnst = (lmm_constraint_t)_cnst;
 738     elem_list = &(cnst->enabled_element_set);
 739     //XBT_DEBUG("Variable set : %d", xbt_swag_size(elem_list));
 740     xbt_swag_foreach(_elem, elem_list) {
 741       var = ((lmm_element_t)_elem)->variable;
 742       xbt_assert(var->weight > 0.0);
 743       var->value = 0.0;
 744     }
 745   }
 746
 747   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));
 748   int cnst_light_num = 0;
 749   dyn_light_t saturated_constraint_set = xbt_new0(s_dyn_light_t,1);
 750   saturated_constraint_set->size = 5;
 751   saturated_constraint_set->data = xbt_new0(int, saturated_constraint_set->size);
 752
 753   xbt_swag_foreach_safe(_cnst, _cnst_next, cnst_list) {
 754   cnst = (lmm_constraint_t)_cnst;
 755     /* INIT: Collect constraints that actually need to be saturated (i.e remaining  and usage are strictly positive) into cnst_light_tab. */
 756     cnst->remaining = cnst->bound;
 757     if (!double_positive(cnst->remaining, cnst->bound*sg_maxmin_precision))
 758       continue;
 759     cnst->usage = 0;
 760     elem_list = &(cnst->enabled_element_set);
 761     xbt_swag_foreach(_elem, elem_list) {
 762       elem = (lmm_element_t)_elem;
 763       xbt_assert(elem->variable->weight > 0);
 764       if ((elem->value > 0)) {
 765         if (cnst->sharing_policy)
 766           cnst->usage += elem->value / elem->variable->weight;
 767         else if (cnst->usage < elem->value / elem->variable->weight)
 768           cnst->usage = elem->value / elem->variable->weight;
 769
 770         make_elem_active(elem);
 771         simgrid::surf::Action *action = static_cast<simgrid::surf::Action*>(elem->variable->id);
 772         if (sys->keep_track && !action->is_linked())
 773           sys->keep_track->push_back(*action);
 774       }
 775     }
 776     XBT_DEBUG("Constraint '%d' usage: %f remaining: %f ", cnst->id_int, cnst->usage, cnst->remaining);
 777     /* Saturated constraints update */
 778
 779     if(cnst->usage > 0) {
 780       cnst_light_tab[cnst_light_num].cnst = cnst;
 781       cnst->cnst_light = &(cnst_light_tab[cnst_light_num]);
 782       cnst_light_tab[cnst_light_num].remaining_over_usage = cnst->remaining / cnst->usage;
 783       saturated_constraint_set_update(cnst_light_tab[cnst_light_num].remaining_over_usage,
 784         cnst_light_num, saturated_constraint_set, &min_usage);
 785       xbt_assert(cnst->active_element_set.count>0, "There is no sense adding a constraint that has no active element!" );
 786       cnst_light_num++;
 787     }
 788   }
 789
 790   saturated_variable_set_update(  cnst_light_tab,
 791                                   saturated_constraint_set,
 792                                   sys);
 793
 794   /* Saturated variables update */
 795
 796   do {
 797     /* Fix the variables that have to be */
 798     var_list = &(sys->saturated_variable_set);
 799
 800     xbt_swag_foreach(_var, var_list) {
 801       var = (lmm_variable_t)_var;
 802       if (var->weight <= 0.0)
 803         DIE_IMPOSSIBLE;
 804       /* First check if some of these variables could reach their upper
 805          bound and update min_bound accordingly. */
 806       XBT_DEBUG
 807           ("var=%d, var->bound=%f, var->weight=%f, min_usage=%f, var->bound*var->weight=%f",
 808            var->id_int, var->bound, var->weight, min_usage,
 809            var->bound * var->weight);
 810       if ((var->bound > 0) && (var->bound * var->weight < min_usage)) {
 811         if (min_bound < 0)
 812           min_bound = var->bound*var->weight;
 813         else
 814           min_bound = MIN(min_bound, (var->bound*var->weight));
 815         XBT_DEBUG("Updated min_bound=%f", min_bound);
 816       }
 817     }
 818
 819
 820     while ((var = (lmm_variable_t)xbt_swag_getFirst(var_list))) {
 821       int i;
 822
 823       if (min_bound < 0) {
 824   //If no variable could reach its bound, deal iteratively the constraints usage ( at worst one constraint is saturated at each cycle)
 825         var->value = min_usage / var->weight;
 826         XBT_DEBUG("Setting %p (%d) value to %f\n", var, var->id_int, var->value);
 827       } else {
 828   //If there exist a variable that can reach its bound, only update it (and other with the same bound) for now.
 829       if (double_equals(min_bound, var->bound*var->weight, sg_maxmin_precision)){
 830           var->value = var->bound;
 831           XBT_DEBUG("Setting %p (%d) value to %f\n", var, var->id_int, var->value);
 832         }
 833         else {
 834     // Variables which bound is different are not considered for this cycle, but they will be afterwards.
 835           XBT_DEBUG("Do not consider %p (%d) \n", var, var->id_int);
 836           xbt_swag_remove(var, var_list);
 837           continue;
 838         }
 839       }
 840       XBT_DEBUG("Min usage: %f, Var(%d)->weight: %f, Var(%d)->value: %f ",
 841              min_usage, var->id_int, var->weight, var->id_int, var->value);
 842
 843
 844       /* Update the usage of contraints where this variable is involved */
 845       for (i = 0; i < var->cnsts_number; i++) {
 846         elem = &var->cnsts[i];
 847         cnst = elem->constraint;
 848         if (cnst->sharing_policy) {
 849     //Remember: shared constraints require that sum(elem->value * var->value) < cnst->bound
 850           double_update(&(cnst->remaining),  elem->value * var->value, cnst->bound*sg_maxmin_precision);
 851           double_update(&(cnst->usage), elem->value / var->weight, sg_maxmin_precision);
 852     //If the constraint is saturated, remove it from the set of active constraints (light_tab)
 853           if(!double_positive(cnst->usage,sg_maxmin_precision) || !double_positive(cnst->remaining,cnst->bound*sg_maxmin_precision)) {
 854             if (cnst->cnst_light) {
 855               int index = (cnst->cnst_light-cnst_light_tab);
 856               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  ",
 857       index,cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab, cnst->usage, cnst->remaining, cnst->bound);
 858               cnst_light_tab[index]=cnst_light_tab[cnst_light_num-1];
 859               cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index];
 860               cnst_light_num--;
 861               cnst->cnst_light = NULL;
 862             }
 863           } else {
 864             cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage;
 865           }
 866           make_elem_inactive(elem);
 867         } else {
 868     //Remember: non-shared constraints only require that max(elem->value * var->value) < cnst->bound
 869           cnst->usage = 0.0;
 870           make_elem_inactive(elem);
 871           elem_list = &(cnst->enabled_element_set);
 872           xbt_swag_foreach(_elem, elem_list) {
 873       elem = (lmm_element_t)_elem;
 874       xbt_assert(elem->variable->weight > 0);
 875       if (elem->variable->value > 0) continue;
 876       if (elem->value > 0)
 877         cnst->usage = MAX(cnst->usage, elem->value / elem->variable->weight);
 878           }
 879     //If the constraint is saturated, remove it from the set of active constraints (light_tab)
 880           if(!double_positive(cnst->usage,sg_maxmin_precision) || !double_positive(cnst->remaining,cnst->bound*sg_maxmin_precision)) {
 881             if(cnst->cnst_light) {
 882               int index = (cnst->cnst_light-cnst_light_tab);
 883               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  ",
 884       index,cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab, cnst->usage, cnst->remaining, cnst->bound);
 885               cnst_light_tab[index]=cnst_light_tab[cnst_light_num-1];
 886               cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index];
 887               cnst_light_num--;
 888               cnst->cnst_light = NULL;
 889             }
 890           } else {
 891             cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage;
 892             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." );
 893           }
 894         }
 895       }
 896       xbt_swag_remove(var, var_list);
 897     }
 898
 899     /* Find out which variables reach the maximum */
 900     min_usage = -1;
 901     min_bound = -1;
 902     saturated_constraint_set->pos = 0;
 903     int pos;
 904     for(pos=0; pos<cnst_light_num; pos++){
 905       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);
 906       saturated_constraint_set_update(
 907           cnst_light_tab[pos].remaining_over_usage,
 908           pos,
 909           saturated_constraint_set,
 910           &min_usage);
 911   }
 912
 913     saturated_variable_set_update(  cnst_light_tab,
 914                                     saturated_constraint_set,
 915                                     sys);
 916
 917   } while (cnst_light_num > 0);
 918
 919   sys->modified = 0;
 920   if (sys->selective_update_active)
 921     lmm_remove_all_modified_set(sys);
 922
 923   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
 924     lmm_print(sys);
 925   }
 926
 927   xbt_free(saturated_constraint_set->data);
 928   xbt_free(saturated_constraint_set);
 929   xbt_free(cnst_light_tab);
 930   XBT_OUT();
 931 }
 932
 933
 934 /** \brief Attribute the value bound to var->bound.
 935  *
 936  *  \param sys the lmm_system_t
 937  *  \param var the lmm_variable_t
 938  *  \param bound the new bound to associate with var
 939  *
 940  *  Makes var->bound equal to bound. Whenever this function is called
 941  *  a change is  signed in the system. To
 942  *  avoid false system changing detection it is a good idea to test
 943  *  (bound != 0) before calling it.
 944  *
 945 */
 946 void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
 947     double bound)
 948 {
 949   sys->modified = 1;
 950   var->bound = bound;
 951
 952   if (var->cnsts_number)
 953     lmm_update_modified_set(sys, var->cnsts[0].constraint);
 954 }
 955
 956
 957
 958 int lmm_concurrency_slack(lmm_constraint_t cnstr){
 959
 960   xbt_assert(xbt_swag_size(&(cnstr->enabled_element_set))==cnstr->concurrency_current,"concurrency_current is not up to date!");
 961
 962   //FIXME MARTIN: Replace by infinite value std::numeric_limits<int>::(max)(), or something better within Simgrid?
 963   if(cnstr->concurrency_limit<0)
 964     return 666;
 965
 966   return  cnstr->concurrency_limit - cnstr->concurrency_current;
 967 }
 968
 969 /** \brief Measure the minimum concurrency slack across all constraints where var is involved
 970  *
 971  * \param The variable to check for
 972  *
 973  */
 974 int lmm_cnstrs_min_concurrency_slack(lmm_variable_t var){
 975   int i;
 976   //FIXME MARTIN: Replace by infinite value std::numeric_limits<int>::(max)(), or something better within Simgrid?
 977   int slack,minslack=666;
 978   for (i = 0; i < var->cnsts_number; i++) {
 979     slack=lmm_concurrency_slack(var->cnsts[i].constraint);
 980
 981     //This is only an optimization, to avoid looking at more constraints when slack is already zero
 982     //Disable it when debugging to let lmm_concurrency_slack catch nasty things
 983     if(!slack   && !XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug))
 984       return 0;
 985
 986     if(minslack>slack)
 987       minslack=slack;
 988   }
 989
 990   return minslack;
 991 }
 992
 993 /* /Check if a variable can be enabled
 994  *
 995  * Make sure to set staged_weight before, if your intent is only to check concurrency
 996  */
 997 int lmm_can_enable_var(lmm_variable_t var){
 998   return var->staged_weight>0 && lmm_cnstrs_min_concurrency_slack(var)>=var->concurrency_share;
 999 }
1000
1001
1002 //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.
1003 //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)
1004
1005 void lmm_enable_var(lmm_system_t sys, lmm_variable_t var){
1006
1007   int i;
1008   lmm_element_t elem;
1009
1010   xbt_assert(lmm_can_enable_var(var));
1011
1012   var->weight = var->staged_weight;
1013   var->staged_weight = 0;
1014
1015   //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.
1016
1017   xbt_swag_remove(var, &(sys->variable_set));
1018   xbt_swag_insert_at_head(var, &(sys->variable_set));
1019   for (i = 0; i < var->cnsts_number; i++) {
1020     elem = &var->cnsts[i];
1021     xbt_swag_remove(elem, &(elem->constraint->disabled_element_set));
1022     xbt_swag_insert_at_head(elem, &(elem->constraint->enabled_element_set));
1023     lmm_increase_concurrency(elem->constraint);
1024   }
1025   if (var->cnsts_number)
1026     lmm_update_modified_set(sys, var->cnsts[0].constraint);
1027
1028   lmm_check_concurrency(sys);
1029 }
1030
1031 void lmm_disable_var(lmm_system_t sys, lmm_variable_t var){
1032   int i;
1033   lmm_element_t elem;
1034
1035   xbt_assert(!var->staged_weight,"Staged weight should have been cleared");
1036   //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.
1037   xbt_swag_remove(var, &(sys->variable_set));
1038   xbt_swag_insert_at_tail(var, &(sys->variable_set));
1039   if (var->cnsts_number)
1040     lmm_update_modified_set(sys, var->cnsts[0].constraint);
1041   for (i = 0; i < var->cnsts_number; i++) {
1042     elem = &var->cnsts[i];
1043     xbt_swag_remove(elem, &(elem->constraint->enabled_element_set));
1044     xbt_swag_insert_at_tail(elem, &(elem->constraint->disabled_element_set));
1045
1046     xbt_swag_remove(elem, &(elem->constraint->active_element_set));
1047
1048     lmm_decrease_concurrency(elem->constraint);
1049   }
1050
1051   var->weight=0.0;
1052   var->staged_weight=0.0;
1053   var->value = 0.0;
1054   lmm_check_concurrency(sys);
1055 }
1056
1057 /* /brief Find variables that can be enabled and enable them.
1058  *
1059  * Assuming that the variable has already been removed from non-zero weights
1060  * Can we find a staged variable to add?
1061  * If yes, check that none of the constraints that this variable is involved in is at the limit of its concurrency
1062  * And then add it to enabled variables
1063  */
1064 void lmm_on_disabled_var(lmm_system_t sys, lmm_constraint_t cnstr){
1065
1066   lmm_element_t elem;
1067   if(cnstr->concurrency_limit<0)
1068     return;
1069
1070   int concurrency=cnstr->concurrency_current;
1071   xbt_swag_foreach(elem, &(cnstr->disabled_element_set)) {
1072
1073     if (elem->variable->staged_weight>0 )
1074       {
1075   //Found a staged variable
1076   //TODOLATER: Add random timing function to model reservation protocol fuzziness? Then how to make sure that staged variables will eventually be called?
1077   if(lmm_can_enable_var(elem->variable)){
1078     lmm_enable_var(sys,elem->variable);
1079     concurrency++;
1080   }
1081       }
1082
1083     xbt_assert(concurrency<=cnstr->concurrency_limit,"Concurrency overflow!");
1084     if(concurrency==cnstr->concurrency_limit)
1085       break;
1086   }
1087
1088   lmm_check_concurrency(sys);
1089
1090 }
1091
1092 /* \brief update the weight of a variable, and enable/disable it.
1093  * @return Returns whether a change was made
1094  */
1095 void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var,
1096              double weight)
1097 {
1098   int minslack;
1099
1100   xbt_assert(weight>=0,"Variable weight should not be negative!");
1101
1102   if (weight == var->weight)
1103     return;
1104
1105   int enabling_var=  (weight>0 && var->weight<=0);
1106   int disabling_var= (weight<=0 && var->weight>0);
1107
1108   XBT_IN("(sys=%p, var=%p, weight=%f)", sys, var, weight);
1109
1110   sys->modified = 1;
1111
1112   //Are we enabling this variable?
1113   if (enabling_var){
1114     var->staged_weight = weight;
1115     minslack=lmm_cnstrs_min_concurrency_slack(var);
1116     if(minslack==0){
1117       XBT_DEBUG("Staging var (instead of enabling) because min concurrency slack %i, with weight %f", minslack, weight);
1118       return;
1119     }
1120     XBT_DEBUG("Enabling var with min concurrency slack %i", minslack);
1121     lmm_enable_var(sys,var);
1122   } else if (disabling_var){
1123     //Are we disabling this variable?
1124     lmm_disable_var(sys,var);
1125   } else {
1126     var->weight=weight;
1127   }
1128
1129   lmm_check_concurrency(sys);
1130
1131   XBT_OUT();
1132   return;
1133 }
1134
1135 double lmm_get_variable_weight(lmm_variable_t var)
1136 {
1137   return var->weight;
1138 }
1139
1140 void lmm_update_constraint_bound(lmm_system_t sys,
1141                                             lmm_constraint_t cnst,
1142                                             double bound)
1143 {
1144   sys->modified = 1;
1145   lmm_update_modified_set(sys, cnst);
1146   cnst->bound = bound;
1147 }
1148
1149 int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst)
1150 {
1151   return xbt_swag_belongs(cnst, &(sys->active_constraint_set));
1152 }
1153
1154 XBT_INLINE lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t
1155                                                             sys)
1156 {
1157   return (lmm_constraint_t)xbt_swag_getFirst(&(sys->active_constraint_set));
1158 }
1159
1160 XBT_INLINE lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t
1161                                                            sys,
1162                                                            lmm_constraint_t
1163                                                            cnst)
1164 {
1165   return (lmm_constraint_t)xbt_swag_getNext(cnst, (sys->active_constraint_set).offset);
1166 }
1167
1168 #ifdef HAVE_LATENCY_BOUND_TRACKING
1169 XBT_PUBLIC(int) lmm_is_variable_limited_by_latency(lmm_variable_t var)
1170 {
1171   return (double_equals(var->bound, var->value, var->bound*sg_maxmin_precision));
1172 }
1173 #endif
1174
1175
1176 /** \brief Update the constraint set propagating recursively to
1177  *  other constraints so the system should not be entirely computed.
1178  *
1179  *  \param sys the lmm_system_t
1180  *  \param cnst the lmm_constraint_t affected by the change
1181  *
1182  *  A recursive algorithm to optimize the system recalculation selecting only
1183  *  constraints that have changed. Each constraint change is propagated
1184  *  to the list of constraints for each variable.
1185  */
1186 static void lmm_update_modified_set_rec(lmm_system_t sys,
1187                                         lmm_constraint_t cnst)
1188 {
1189   void* _elem;
1190
1191   //TODOLATER: Why lmm_modified_set has been changed in git version 2392B5157...? Looks equivalent logically and less obvious..
1192
1193   xbt_swag_foreach(_elem, &cnst->enabled_element_set) {
1194     lmm_variable_t var = ((lmm_element_t)_elem)->variable;
1195     s_lmm_element_t *cnsts = var->cnsts;
1196     int i;
1197     for (i = 0; var->visited != sys->visited_counter
1198              && i < var->cnsts_number ; i++) {
1199       if (cnsts[i].constraint != cnst
1200           && !xbt_swag_belongs(cnsts[i].constraint,
1201                                &sys->modified_constraint_set)) {
1202         xbt_swag_insert(cnsts[i].constraint, &sys->modified_constraint_set);
1203         lmm_update_modified_set_rec(sys, cnsts[i].constraint);
1204       }
1205     }
1206     //var will be ignored in later visits as long as sys->visited_counter does not move
1207     var->visited = sys->visited_counter;
1208   }
1209 }
1210
1211 static void lmm_update_modified_set(lmm_system_t sys,
1212                                     lmm_constraint_t cnst)
1213 {
1214   /* nothing to do if selective update isn't active */
1215   if (sys->selective_update_active
1216       && !xbt_swag_belongs(cnst, &sys->modified_constraint_set)) {
1217     xbt_swag_insert(cnst, &sys->modified_constraint_set);
1218     lmm_update_modified_set_rec(sys, cnst);
1219   }
1220 }
1221
1222 /** \brief Remove all constraints of the modified_constraint_set.
1223  *
1224  *  \param sys the lmm_system_t
1225  *
1226  */
1227 static void lmm_remove_all_modified_set(lmm_system_t sys)
1228 {
1229
1230   //We cleverly un-flag all variables just by incrementing sys->visited_counter
1231   //In effect, the var->visited value will no more be equal to sys->visited counter
1232   //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).
1233   if (++sys->visited_counter == 1) {
1234     /* the counter wrapped around, reset each variable->visited */
1235   void *_var;
1236     xbt_swag_foreach(_var, &sys->variable_set)
1237       ((lmm_variable_t)_var)->visited = 0;
1238   }
1239   xbt_swag_reset(&sys->modified_constraint_set);
1240 }
1241
1242 /**
1243  *  Returns total resource load
1244  *
1245  * \param cnst the lmm_constraint_t associated to the resource
1246  *
1247  *
1248  * This is dead code, but we may use it later for debug/trace.
1249  */
1250 double lmm_constraint_get_usage(lmm_constraint_t cnst) {
1251    double usage = 0.0;
1252    xbt_swag_t elem_list = &(cnst->enabled_element_set);
1253    void *_elem;
1254    lmm_element_t elem = NULL;
1255
1256    xbt_swag_foreach(_elem, elem_list) {
1257    elem = (lmm_element_t)_elem;
1258      if ((elem->value > 0)) {
1259        if (cnst->sharing_policy)
1260          usage += elem->value * elem->variable->value;
1261        else if (usage < elem->value * elem->variable->value)
1262          usage = elem->value * elem->variable->value;
1263      }
1264    }
1265   return usage;
1266 }
1267
1268 void lmm_check_concurrency(lmm_system_t sys){
1269   void* _cnst;
1270   void* _elem;
1271   lmm_element_t elem;
1272   lmm_constraint_t cnst;
1273   int concurrency;
1274
1275   //These checks are very expensive, so do them only if we want to debug SURF LMM
1276   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
1277
1278     xbt_swag_foreach(_cnst, &(sys->constraint_set)) {
1279       cnst = (lmm_constraint_t) _cnst;
1280       concurrency=0;
1281
1282       xbt_swag_foreach(_elem, &(cnst->enabled_element_set)) {
1283   elem = (lmm_element_t)_elem;
1284   xbt_assert(elem->variable->weight > 0);
1285     concurrency++;
1286       }
1287
1288       xbt_swag_foreach(_elem, &(cnst->disabled_element_set)) {
1289   elem = (lmm_element_t)_elem;
1290   //We should have staged variables only if conccurency is reached in some constraint
1291   xbt_assert(cnst->concurrency_limit<0 || elem->variable->staged_weight==0 || lmm_cnstrs_min_concurrency_slack(elem->variable) < elem->variable->concurrency_share,"should not have staged variable!");
1292       }
1293
1294       xbt_assert(cnst->concurrency_limit<0 || cnst->concurrency_limit >= concurrency,"concurrency check failed!");
1295       xbt_assert(cnst->concurrency_current == concurrency, "concurrency_current is out-of-date!");
1296       xbt_assert(cnst->concurrency_current == xbt_swag_size(&(cnst->enabled_element_set)), "concurrency_current is out-of-date (2) !");
1297
1298     }
1299
1300   }
1301 }