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