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