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