src/surf/maxmin.cpp

   1 /* Copyright (c) 2004-2014. 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 #include "xbt/sysdep.h"
   8 #include "xbt/log.h"
   9 #include "xbt/mallocator.h"
  10 #include "maxmin_private.hpp"
  11 #include <stdlib.h>
  12 #include <stdio.h>              /* sprintf */
  13 #include <math.h>
  14 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_maxmin, surf,
  15                                 "Logging specific to SURF (maxmin)");
  16
  17 typedef struct s_dyn_light {
  18   int *data;
  19   int pos;
  20   int size;
  21 } s_dyn_light_t, *dyn_light_t;
  22
  23 XBT_EXPORT_NO_IMPORT(double) sg_maxmin_precision = 0.00001;
  24
  25 static void *lmm_variable_mallocator_new_f(void);
  26 static void lmm_variable_mallocator_free_f(void *var);
  27 #define lmm_variable_mallocator_reset_f ((void_f_pvoid_t)NULL)
  28 static void lmm_update_modified_set(lmm_system_t sys,
  29                                     lmm_constraint_t cnst);
  30 static void lmm_remove_all_modified_set(lmm_system_t sys);
  31 static int Global_debug_id = 1;
  32 static int Global_const_debug_id = 1;
  33
  34 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var);
  35 static XBT_INLINE void lmm_cnst_free(lmm_system_t sys,
  36                                      lmm_constraint_t cnst);
  37
  38 lmm_system_t lmm_system_new(int selective_update)
  39 {
  40   lmm_system_t l = NULL;
  41   s_lmm_variable_t var;
  42   s_lmm_constraint_t cnst;
  43
  44   l = xbt_new0(s_lmm_system_t, 1);
  45
  46   l->modified = 0;
  47   l->selective_update_active = selective_update;
  48   l->visited_counter = 1;
  49
  50   XBT_DEBUG("Setting selective_update_active flag to %d\n",
  51          l->selective_update_active);
  52
  53   xbt_swag_init(&(l->variable_set),
  54                 xbt_swag_offset(var, variable_set_hookup));
  55   xbt_swag_init(&(l->constraint_set),
  56                 xbt_swag_offset(cnst, constraint_set_hookup));
  57
  58   xbt_swag_init(&(l->active_constraint_set),
  59                 xbt_swag_offset(cnst, active_constraint_set_hookup));
  60
  61   xbt_swag_init(&(l->modified_constraint_set),
  62                 xbt_swag_offset(cnst, modified_constraint_set_hookup));
  63   xbt_swag_init(&(l->saturated_variable_set),
  64                 xbt_swag_offset(var, saturated_variable_set_hookup));
  65   xbt_swag_init(&(l->saturated_constraint_set),
  66                 xbt_swag_offset(cnst, saturated_constraint_set_hookup));
  67
  68   l->variable_mallocator = xbt_mallocator_new(65536,
  69                                               lmm_variable_mallocator_new_f,
  70                                               lmm_variable_mallocator_free_f,
  71                                               lmm_variable_mallocator_reset_f);
  72
  73   return l;
  74 }
  75
  76 void lmm_system_free(lmm_system_t sys)
  77 {
  78   lmm_variable_t var = NULL;
  79   lmm_constraint_t cnst = NULL;
  80
  81   while ((var = (lmm_variable_t) extract_variable(sys))) {
  82     XBT_WARN
  83         ("Variable %p (%d) still in LMM system when freing it: this may be a bug",
  84          var, var->id_int);
  85     lmm_var_free(sys, var);
  86   }
  87
  88   while ((cnst = (lmm_constraint_t) extract_constraint(sys)))
  89     lmm_cnst_free(sys, cnst);
  90
  91   xbt_mallocator_free(sys->variable_mallocator);
  92   free(sys);
  93 }
  94
  95 static XBT_INLINE void lmm_variable_disable(lmm_system_t sys, lmm_variable_t var)
  96 {
  97   int i;
  98   int n;
  99
 100   lmm_element_t elem = NULL;
 101
 102   XBT_IN("(sys=%p, var=%p)", sys, var);
 103   sys->modified = 1;
 104
 105   n = 0;
 106   for (i = 0; i < var->cnsts_number; i++) {
 107     elem = &var->cnsts[i];
 108     xbt_swag_remove(elem, &(elem->constraint->element_set));
 109     xbt_swag_remove(elem, &(elem->constraint->active_element_set));
 110     if (!xbt_swag_size(&(elem->constraint->element_set)))
 111       make_constraint_inactive(sys, elem->constraint);
 112     else {
 113       if (n < i)
 114         var->cnsts[n].constraint = elem->constraint;
 115       n++;
 116     }
 117   }
 118   if (n) {
 119     var->cnsts_number = n;
 120     lmm_update_modified_set(sys, var->cnsts[0].constraint);
 121   }
 122
 123   var->cnsts_number = 0;
 124   XBT_OUT();
 125 }
 126
 127 static void lmm_var_free(lmm_system_t sys, lmm_variable_t var)
 128 {
 129
 130   lmm_variable_disable(sys, var);
 131   xbt_mallocator_release(sys->variable_mallocator, var);
 132 }
 133
 134 static XBT_INLINE void lmm_cnst_free(lmm_system_t sys,
 135                                      lmm_constraint_t cnst)
 136 {
 137 /*   xbt_assert(xbt_swag_size(&(cnst->element_set)), */
 138 /*         "This list should be empty!"); */
 139   make_constraint_inactive(sys, cnst);
 140   free(cnst);
 141 }
 142
 143 lmm_constraint_t lmm_constraint_new(lmm_system_t sys, void *id,
 144                                     double bound_value)
 145 {
 146   lmm_constraint_t cnst = NULL;
 147   s_lmm_element_t elem;
 148
 149   cnst = xbt_new0(s_lmm_constraint_t, 1);
 150   cnst->id = id;
 151   cnst->id_int = Global_const_debug_id++;
 152   xbt_swag_init(&(cnst->element_set),
 153                 xbt_swag_offset(elem, element_set_hookup));
 154   xbt_swag_init(&(cnst->active_element_set),
 155                 xbt_swag_offset(elem, active_element_set_hookup));
 156
 157   cnst->bound = bound_value;
 158   cnst->usage = 0;
 159   cnst->shared = 1;
 160   insert_constraint(sys, cnst);
 161
 162   return cnst;
 163 }
 164
 165 void lmm_constraint_shared(lmm_constraint_t cnst)
 166 {
 167   cnst->shared = 0;
 168 }
 169
 170 int lmm_constraint_is_shared(lmm_constraint_t cnst)
 171 {
 172   return (cnst->shared);
 173 }
 174
 175 XBT_INLINE void lmm_constraint_free(lmm_system_t sys,
 176                                     lmm_constraint_t cnst)
 177 {
 178   remove_constraint(sys, cnst);
 179   lmm_cnst_free(sys, cnst);
 180 }
 181
 182 static void *lmm_variable_mallocator_new_f(void)
 183 {
 184   lmm_variable_t var = xbt_new(s_lmm_variable_t, 1);
 185   var->cnsts = NULL; /* will be created by realloc */
 186   return var;
 187 }
 188
 189 static void lmm_variable_mallocator_free_f(void *var)
 190 {
 191   xbt_free(((lmm_variable_t) var)->cnsts);
 192   xbt_free(var);
 193 }
 194
 195 lmm_variable_t lmm_variable_new(lmm_system_t sys, void *id,
 196                                 double weight,
 197                                 double bound, int number_of_constraints)
 198 {
 199   lmm_variable_t var = NULL;
 200   int i;
 201
 202   XBT_IN("(sys=%p, id=%p, weight=%f, bound=%f, num_cons =%d)",
 203           sys, id, weight, bound, number_of_constraints);
 204
 205   var = (lmm_variable_t) xbt_mallocator_get(sys->variable_mallocator);
 206   var->id = id;
 207   var->id_int = Global_debug_id++;
 208   var->cnsts = (s_lmm_element_t *) xbt_realloc(var->cnsts, number_of_constraints * sizeof(s_lmm_element_t));
 209   for (i = 0; i < number_of_constraints; i++) {
 210     var->cnsts[i].element_set_hookup.next = NULL;
 211     var->cnsts[i].element_set_hookup.prev = NULL;
 212     var->cnsts[i].active_element_set_hookup.next = NULL;
 213     var->cnsts[i].active_element_set_hookup.prev = NULL;
 214     var->cnsts[i].constraint = NULL;
 215     var->cnsts[i].variable = NULL;
 216     var->cnsts[i].value = 0.0;
 217   }
 218   var->cnsts_size = number_of_constraints;
 219   var->cnsts_number = 0;
 220   var->weight = weight;
 221   var->bound = bound;
 222   var->value = 0.0;
 223   var->visited = sys->visited_counter - 1;
 224   var->mu = 0.0;
 225   var->new_mu = 0.0;
 226   var->func_f = func_f_def;
 227   var->func_fp = func_fp_def;
 228   var->func_fpi = func_fpi_def;
 229
 230   var->variable_set_hookup.next = NULL;
 231   var->variable_set_hookup.prev = NULL;
 232   var->saturated_variable_set_hookup.next = NULL;
 233   var->saturated_variable_set_hookup.prev = NULL;
 234
 235   if (weight)
 236     xbt_swag_insert_at_head(var, &(sys->variable_set));
 237   else
 238     xbt_swag_insert_at_tail(var, &(sys->variable_set));
 239
 240   XBT_OUT(" returns %p", var);
 241   return var;
 242 }
 243
 244 void lmm_variable_free(lmm_system_t sys, lmm_variable_t var)
 245 {
 246   remove_variable(sys, var);
 247   lmm_var_free(sys, var);
 248 }
 249
 250 double lmm_variable_getvalue(lmm_variable_t var)
 251 {
 252   return (var->value);
 253 }
 254
 255 double lmm_variable_getbound(lmm_variable_t var)
 256 {
 257   return (var->bound);
 258 }
 259
 260 /* Replace the content of elem_a with elem_b. The content of elem_b is cleared. */
 261 static void renew_elem_entry(lmm_element_t elem_a, lmm_element_t elem_b)
 262 {
 263     elem_a->constraint = elem_b->constraint;
 264     elem_a->variable   = elem_b->variable;
 265     elem_a->value      = elem_b->value;
 266
 267     /* If elem_b is in the element_set swag, register the new element to the swag. */
 268     if (xbt_swag_remove(elem_b, &(elem_b->constraint->element_set))) {
 269       if (elem_a->variable->weight)
 270         xbt_swag_insert_at_head(elem_a, &(elem_a->constraint->element_set));
 271       else
 272         xbt_swag_insert_at_tail(elem_a, &(elem_a->constraint->element_set));
 273     }
 274
 275     if (xbt_swag_remove(elem_b, &(elem_b->constraint->active_element_set))) {
 276       if (elem_a->variable->weight)
 277         xbt_swag_insert_at_head(elem_a, &(elem_a->constraint->active_element_set));
 278       else
 279         xbt_swag_insert_at_tail(elem_a, &(elem_a->constraint->active_element_set));
 280     }
 281
 282     elem_b->constraint = NULL;
 283     elem_b->variable   = NULL;
 284     elem_b->value      = 0;
 285 }
 286
 287 void lmm_shrink(lmm_system_t sys, lmm_constraint_t cnst,
 288                 lmm_variable_t var)
 289 {
 290   lmm_element_t elem = NULL;
 291   int found = 0;
 292
 293   int i;
 294   for (i = 0; i < var->cnsts_number; i++) {
 295     elem = &(var->cnsts[i]);
 296     if (elem->constraint == cnst) {
 297       found = 1;
 298       break;
 299     }
 300   }
 301
 302   if (!found) {
 303     XBT_DEBUG("cnst %p is not found in var %p", cnst, var);
 304     return;
 305   }
 306
 307   sys->modified = 1;
 308
 309   XBT_DEBUG("remove elem(value %f, cnst %p, var %p) in var %p",
 310       elem->value, elem->constraint, elem->variable, var);
 311
 312
 313
 314   /* We are going to change the constraint object and the variable object.
 315    * Propagate this change to other objects. Calling here (not after
 316    * modification) is correct? */
 317   lmm_update_modified_set(sys, cnst);
 318   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].
 319
 320
 321
 322   /* now var->cnsts[i] is not necessary any more */
 323
 324   xbt_swag_remove(elem, &(elem->constraint->element_set));
 325   xbt_swag_remove(elem, &(elem->constraint->active_element_set));
 326   elem->constraint = NULL;
 327   elem->variable = NULL;
 328   elem->value = 0;
 329
 330
 331
 332   /* We do not want to have an empty element entry before the last entry. So,
 333    * plug up the hole with the last one. */
 334   if (i < var->cnsts_number - 1)
 335     renew_elem_entry(&var->cnsts[i], &var->cnsts[var->cnsts_number - 1]);
 336
 337   var->cnsts_number -= 1;
 338
 339
 340   if (xbt_swag_size(&(cnst->element_set)) == 0)
 341     make_constraint_inactive(sys, cnst);
 342 }
 343
 344 void lmm_expand(lmm_system_t sys, lmm_constraint_t cnst,
 345                 lmm_variable_t var, double value)
 346 {
 347   lmm_element_t elem = NULL;
 348
 349   sys->modified = 1;
 350
 351   xbt_assert(var->cnsts_number < var->cnsts_size, "Too much constraints");
 352
 353   elem = &(var->cnsts[var->cnsts_number++]);
 354
 355   elem->value = value;
 356   elem->constraint = cnst;
 357   elem->variable = var;
 358
 359   if (var->weight)
 360     xbt_swag_insert_at_head(elem, &(elem->constraint->element_set));
 361   else
 362     xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set));
 363   if(!sys->selective_update_active) {
 364     make_constraint_active(sys, cnst);
 365   } else if(elem->value>0 || var->weight >0) {
 366     make_constraint_active(sys, cnst);
 367     lmm_update_modified_set(sys, cnst);
 368     if (var->cnsts_number > 1)
 369       lmm_update_modified_set(sys, var->cnsts[0].constraint);
 370   }
 371 }
 372
 373 void lmm_expand_add(lmm_system_t sys, lmm_constraint_t cnst,
 374                     lmm_variable_t var, double value)
 375 {
 376   int i;
 377   sys->modified = 1;
 378
 379   for (i = 0; i < var->cnsts_number; i++)
 380     if (var->cnsts[i].constraint == cnst)
 381       break;
 382
 383   if (i < var->cnsts_number) {
 384     if (cnst->shared)
 385       var->cnsts[i].value += value;
 386     else
 387       var->cnsts[i].value = MAX(var->cnsts[i].value, value);
 388     lmm_update_modified_set(sys, cnst);
 389   } else
 390     lmm_expand(sys, cnst, var, value);
 391 }
 392
 393 lmm_constraint_t lmm_get_cnst_from_var(lmm_system_t /*sys*/,
 394                                                   lmm_variable_t var,
 395                                                   int num)
 396 {
 397   if (num < var->cnsts_number)
 398     return (var->cnsts[num].constraint);
 399   else
 400     return NULL;
 401 }
 402
 403 double lmm_get_cnst_weight_from_var(lmm_system_t /*sys*/,
 404                                                          lmm_variable_t var,
 405                                                          int num)
 406 {
 407   if (num < var->cnsts_number)
 408     return (var->cnsts[num].value);
 409   else
 410     return 0.0;
 411 }
 412
 413 int lmm_get_number_of_cnst_from_var(lmm_system_t /*sys*/,
 414                                                lmm_variable_t var)
 415 {
 416   return (var->cnsts_number);
 417 }
 418
 419 lmm_variable_t lmm_get_var_from_cnst(lmm_system_t /*sys*/,
 420                                      lmm_constraint_t cnst,
 421                                      lmm_element_t * elem)
 422 {
 423   if (!(*elem))
 424     *elem = (lmm_element_t) xbt_swag_getFirst(&(cnst->element_set));
 425   else
 426     *elem = (lmm_element_t) xbt_swag_getNext(*elem, cnst->element_set.offset);
 427   if (*elem)
 428     return (*elem)->variable;
 429   else
 430     return NULL;
 431 }
 432
 433 void *lmm_constraint_id(lmm_constraint_t cnst)
 434 {
 435   return cnst->id;
 436 }
 437
 438 void *lmm_variable_id(lmm_variable_t var)
 439 {
 440   return var->id;
 441 }
 442
 443 static XBT_INLINE void saturated_constraint_set_update(double usage,
 444                                                       int cnst_light_num,
 445                                                       dyn_light_t saturated_constraint_set,
 446                                                       double *min_usage)
 447 {
 448   xbt_assert(usage > 0,"Impossible");
 449
 450   if (*min_usage < 0 || *min_usage > usage) {
 451     *min_usage = usage;
 452     // XBT_HERE(" min_usage=%f (cnst->remaining / cnst->usage =%f)", *min_usage, usage);
 453     saturated_constraint_set->data[0] = cnst_light_num;
 454     saturated_constraint_set->pos = 1;
 455   } else if (*min_usage == usage) {
 456     if(saturated_constraint_set->pos == saturated_constraint_set->size) { // realloc the size
 457       saturated_constraint_set->size *= 2;
 458       saturated_constraint_set->data = (int*) xbt_realloc(saturated_constraint_set->data, (saturated_constraint_set->size) * sizeof(int));
 459     }
 460     saturated_constraint_set->data[saturated_constraint_set->pos] = cnst_light_num;
 461     saturated_constraint_set->pos++;
 462   }
 463 }
 464
 465 static XBT_INLINE void saturated_variable_set_update(
 466     s_lmm_constraint_light_t *cnst_light_tab,
 467     dyn_light_t saturated_constraint_set,
 468     lmm_system_t sys)
 469 {
 470   lmm_constraint_light_t cnst = NULL;
 471   void *_elem;
 472   lmm_element_t elem = NULL;
 473   xbt_swag_t elem_list = NULL;
 474   int i;
 475   for(i = 0; i< saturated_constraint_set->pos; i++){
 476     cnst = &cnst_light_tab[saturated_constraint_set->data[i]];
 477     elem_list = &(cnst->cnst->active_element_set);
 478     xbt_swag_foreach(_elem, elem_list) {
 479       elem = (lmm_element_t)_elem;
 480       if (elem->variable->weight <= 0)
 481         break;
 482       if ((elem->value > 0))
 483         xbt_swag_insert(elem->variable, &(sys->saturated_variable_set));
 484     }
 485   }
 486 }
 487
 488 void lmm_print(lmm_system_t sys)
 489 {
 490   void *_cnst, *_elem, *_var;
 491   lmm_constraint_t cnst = NULL;
 492   lmm_element_t elem = NULL;
 493   lmm_variable_t var = NULL;
 494   xbt_swag_t cnst_list = NULL;
 495   xbt_swag_t var_list = NULL;
 496   xbt_swag_t elem_list = NULL;
 497   char print_buf[1024];
 498   char *trace_buf = (char*) xbt_malloc0(sizeof(char));
 499   double sum = 0.0;
 500
 501   /* Printing Objective */
 502   var_list = &(sys->variable_set);
 503   sprintf(print_buf, "MAX-MIN ( ");
 504   trace_buf = (char*)
 505       xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 506   strcat(trace_buf, print_buf);
 507   xbt_swag_foreach(_var, var_list) {
 508         var = (lmm_variable_t)_var;
 509     sprintf(print_buf, "'%d'(%f) ", var->id_int, var->weight);
 510     trace_buf = (char*)
 511         xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 512     strcat(trace_buf, print_buf);
 513   }
 514   sprintf(print_buf, ")");
 515   trace_buf = (char*)
 516       xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 517   strcat(trace_buf, print_buf);
 518   XBT_DEBUG("%20s", trace_buf);
 519   trace_buf[0] = '\000';
 520
 521   XBT_DEBUG("Constraints");
 522   /* Printing Constraints */
 523   cnst_list = &(sys->active_constraint_set);
 524   xbt_swag_foreach(_cnst, cnst_list) {
 525         cnst = (lmm_constraint_t)_cnst;
 526     sum = 0.0;
 527     elem_list = &(cnst->element_set);
 528     sprintf(print_buf, "\t");
 529     trace_buf = (char*)
 530         xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 531     strcat(trace_buf, print_buf);
 532     sprintf(print_buf, "%s(",(cnst->shared)?"":"max");
 533     trace_buf = (char*)
 534       xbt_realloc(trace_buf,
 535       strlen(trace_buf) + strlen(print_buf) + 1);
 536     strcat(trace_buf, print_buf);
 537     xbt_swag_foreach(_elem, elem_list) {
 538       elem = (lmm_element_t)_elem;
 539       sprintf(print_buf, "%f.'%d'(%f) %s ", elem->value,
 540               elem->variable->id_int, elem->variable->value,(cnst->shared)?"+":",");
 541       trace_buf = (char*)
 542           xbt_realloc(trace_buf,
 543                       strlen(trace_buf) + strlen(print_buf) + 1);
 544       strcat(trace_buf, print_buf);
 545       if(cnst->shared)
 546   sum += elem->value * elem->variable->value;
 547       else
 548   sum = MAX(sum,elem->value * elem->variable->value);
 549     }
 550     sprintf(print_buf, "0) <= %f ('%d')", cnst->bound, cnst->id_int);
 551     trace_buf = (char*)
 552         xbt_realloc(trace_buf, strlen(trace_buf) + strlen(print_buf) + 1);
 553     strcat(trace_buf, print_buf);
 554
 555     if (!cnst->shared) {
 556       sprintf(print_buf, " [MAX-Constraint]");
 557       trace_buf = (char*)
 558           xbt_realloc(trace_buf,
 559                       strlen(trace_buf) + strlen(print_buf) + 1);
 560       strcat(trace_buf, print_buf);
 561     }
 562     XBT_DEBUG("%s", trace_buf);
 563     trace_buf[0] = '\000';
 564     xbt_assert(!double_positive(sum - cnst->bound),
 565                 "Incorrect value (%f is not smaller than %f): %g",
 566                 sum, cnst->bound, sum - cnst->bound);
 567   }
 568
 569   XBT_DEBUG("Variables");
 570   /* Printing Result */
 571   xbt_swag_foreach(_var, var_list) {
 572         var = (lmm_variable_t)_var;
 573     if (var->bound > 0) {
 574       XBT_DEBUG("'%d'(%f) : %f (<=%f)", var->id_int, var->weight, var->value,
 575              var->bound);
 576       xbt_assert(!double_positive(var->value - var->bound),
 577                   "Incorrect value (%f is not smaller than %f",
 578                   var->value, var->bound);
 579     } else {
 580       XBT_DEBUG("'%d'(%f) : %f", var->id_int, var->weight, var->value);
 581     }
 582   }
 583
 584   free(trace_buf);
 585 }
 586
 587 void lmm_solve(lmm_system_t sys)
 588 {
 589   void *_var, *_cnst, *_cnst_next, *_elem;
 590   lmm_variable_t var = NULL;
 591   lmm_constraint_t cnst = NULL;
 592   lmm_element_t elem = NULL;
 593   xbt_swag_t cnst_list = NULL;
 594   xbt_swag_t var_list = NULL;
 595   xbt_swag_t elem_list = NULL;
 596   double min_usage = -1;
 597   double min_bound = -1;
 598
 599   if (!(sys->modified))
 600     return;
 601
 602   XBT_IN("(sys=%p)", sys);
 603
 604   /*
 605    * Compute Usage and store the variables that reach the maximum.
 606    */
 607   cnst_list =
 608       sys->
 609       selective_update_active ? &(sys->modified_constraint_set) :
 610       &(sys->active_constraint_set);
 611
 612   XBT_DEBUG("Active constraints : %d", xbt_swag_size(cnst_list));
 613   /* Init: Only modified code portions */
 614   xbt_swag_foreach(_cnst, cnst_list) {
 615         cnst = (lmm_constraint_t)_cnst;
 616     elem_list = &(cnst->element_set);
 617     //XBT_DEBUG("Variable set : %d", xbt_swag_size(elem_list));
 618     xbt_swag_foreach(_elem, elem_list) {
 619       var = ((lmm_element_t)_elem)->variable;
 620       if (var->weight <= 0.0)
 621         break;
 622       var->value = 0.0;
 623     }
 624   }
 625
 626   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));
 627   int cnst_light_num = 0;
 628   dyn_light_t saturated_constraint_set = xbt_new0(s_dyn_light_t,1);
 629   saturated_constraint_set->size = 5;
 630   saturated_constraint_set->data = xbt_new0(int, saturated_constraint_set->size);
 631
 632   xbt_swag_foreach_safe(_cnst, _cnst_next, cnst_list) {
 633         cnst = (lmm_constraint_t)_cnst;
 634     /* INIT */
 635     cnst->remaining = cnst->bound;
 636     if (cnst->remaining == 0)
 637       continue;
 638     cnst->usage = 0;
 639     elem_list = &(cnst->element_set);
 640     xbt_swag_foreach(_elem, elem_list) {
 641       elem = (lmm_element_t)_elem;
 642       /* 0-weighted elements (ie, sleep actions) are at the end of the swag and we don't want to consider them */
 643       if (elem->variable->weight <= 0)
 644         break;
 645       if ((elem->value > 0)) {
 646         if (cnst->shared)
 647           cnst->usage += elem->value / elem->variable->weight;
 648         else if (cnst->usage < elem->value / elem->variable->weight)
 649           cnst->usage = elem->value / elem->variable->weight;
 650
 651         make_elem_active(elem);
 652         ActionPtr action = static_cast<ActionPtr>(elem->variable->id);
 653         if (sys->keep_track && !action->is_linked())
 654           sys->keep_track->push_back(*action);
 655       }
 656     }
 657     XBT_DEBUG("Constraint Usage '%d' : %f", cnst->id_int, cnst->usage);
 658     /* Saturated constraints update */
 659
 660     if(cnst->usage > 0) {
 661       cnst_light_tab[cnst_light_num].cnst = cnst;
 662       cnst->cnst_light = &(cnst_light_tab[cnst_light_num]);
 663       cnst_light_tab[cnst_light_num].remaining_over_usage = cnst->remaining / cnst->usage;
 664       saturated_constraint_set_update(cnst_light_tab[cnst_light_num].remaining_over_usage,
 665         cnst_light_num, saturated_constraint_set, &min_usage);
 666       cnst_light_num++;
 667     }
 668   }
 669
 670   saturated_variable_set_update(  cnst_light_tab,
 671                                   saturated_constraint_set,
 672                                   sys);
 673
 674   /* Saturated variables update */
 675
 676   do {
 677     /* Fix the variables that have to be */
 678     var_list = &(sys->saturated_variable_set);
 679
 680     xbt_swag_foreach(_var, var_list) {
 681       var = (lmm_variable_t)_var;
 682       if (var->weight <= 0.0)
 683         DIE_IMPOSSIBLE;
 684       /* First check if some of these variables have reach their upper
 685          bound and update min_usage accordingly. */
 686       XBT_DEBUG
 687           ("var=%d, var->bound=%f, var->weight=%f, min_usage=%f, var->bound*var->weight=%f",
 688            var->id_int, var->bound, var->weight, min_usage,
 689            var->bound * var->weight);
 690       if ((var->bound > 0) && (var->bound * var->weight < min_usage)) {
 691         if (min_bound < 0)
 692           min_bound = var->bound;
 693         else
 694           min_bound = MIN(min_bound, var->bound);
 695         XBT_DEBUG("Updated min_bound=%f", min_bound);
 696       }
 697     }
 698
 699
 700     while ((var = (lmm_variable_t)xbt_swag_getFirst(var_list))) {
 701       int i;
 702
 703       if (min_bound < 0) {
 704         var->value = min_usage / var->weight;
 705         XBT_DEBUG("Setting %p (%d) value to %f\n", var, var->id_int, var->value);
 706       } else {
 707         if (min_bound == var->bound) {
 708           var->value = var->bound;
 709           XBT_DEBUG("Setting %p (%d) value to %f\n", var, var->id_int, var->value);
 710         }
 711         else {
 712           XBT_DEBUG("Do not consider %p (%d)\n", var, var->id_int);
 713           xbt_swag_remove(var, var_list);
 714           continue;
 715         }
 716       }
 717       XBT_DEBUG("Min usage: %f, Var(%d)->weight: %f, Var(%d)->value: %f ",
 718              min_usage, var->id_int, var->weight, var->id_int, var->value);
 719
 720
 721       /* Update usage */
 722
 723       for (i = 0; i < var->cnsts_number; i++) {
 724         elem = &var->cnsts[i];
 725         cnst = elem->constraint;
 726         if (cnst->shared) {
 727           double_update(&(cnst->remaining), elem->value * var->value);
 728           double_update(&(cnst->usage), elem->value / var->weight);
 729           if(cnst->usage<=0 || cnst->remaining<=0) {
 730             if (cnst->cnst_light) {
 731               int index = (cnst->cnst_light-cnst_light_tab);
 732               XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p \t cnst_light_tab: %p ",
 733                   index,cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab);
 734               cnst_light_tab[index]=cnst_light_tab[cnst_light_num-1];
 735               cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index];
 736               cnst_light_num--;
 737               cnst->cnst_light = NULL;
 738             }
 739           } else {
 740             cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage;
 741           }
 742           make_elem_inactive(elem);
 743         } else {
 744           cnst->usage = 0.0;
 745           make_elem_inactive(elem);
 746           elem_list = &(cnst->element_set);
 747           xbt_swag_foreach(_elem, elem_list) {
 748                 elem = (lmm_element_t)_elem;
 749             if (elem->variable->weight <= 0) break;
 750             if (elem->variable->value > 0) continue;
 751             if (elem->value > 0)
 752               cnst->usage = MAX(cnst->usage, elem->value / elem->variable->weight);
 753           }
 754           if (cnst->usage<=0 || cnst->remaining<=0) {
 755             if(cnst->cnst_light) {
 756               int index = (cnst->cnst_light-cnst_light_tab);
 757               XBT_DEBUG("index: %d \t cnst_light_num: %d \t || \t cnst: %p \t cnst->cnst_light: %p \t cnst_light_tab: %p ",
 758                   index,cnst_light_num, cnst, cnst->cnst_light, cnst_light_tab);
 759               cnst_light_tab[index]=cnst_light_tab[cnst_light_num-1];
 760               cnst_light_tab[index].cnst->cnst_light = &cnst_light_tab[index];
 761               cnst_light_num--;
 762               cnst->cnst_light = NULL;
 763             }
 764           } else {
 765             cnst->cnst_light->remaining_over_usage = cnst->remaining / cnst->usage;
 766           }
 767         }
 768       }
 769       xbt_swag_remove(var, var_list);
 770     }
 771
 772     /* Find out which variables reach the maximum */
 773     min_usage = -1;
 774     min_bound = -1;
 775     saturated_constraint_set->pos = 0;
 776     int pos;
 777     for(pos=0; pos<cnst_light_num; pos++)
 778       saturated_constraint_set_update(
 779           cnst_light_tab[pos].remaining_over_usage,
 780           pos,
 781           saturated_constraint_set,
 782           &min_usage);
 783
 784     saturated_variable_set_update(  cnst_light_tab,
 785                                     saturated_constraint_set,
 786                                     sys);
 787
 788   } while (cnst_light_num > 0);
 789
 790   sys->modified = 0;
 791   if (sys->selective_update_active)
 792     lmm_remove_all_modified_set(sys);
 793
 794   if (XBT_LOG_ISENABLED(surf_maxmin, xbt_log_priority_debug)) {
 795     lmm_print(sys);
 796   }
 797
 798   xbt_free(saturated_constraint_set->data);
 799   xbt_free(saturated_constraint_set);
 800   xbt_free(cnst_light_tab);
 801   XBT_OUT();
 802 }
 803
 804 /* Not a O(1) function */
 805
 806 void lmm_update(lmm_system_t sys, lmm_constraint_t cnst,
 807                 lmm_variable_t var, double value)
 808 {
 809   int i;
 810
 811   for (i = 0; i < var->cnsts_number; i++)
 812     if (var->cnsts[i].constraint == cnst) {
 813       var->cnsts[i].value = value;
 814       sys->modified = 1;
 815       lmm_update_modified_set(sys, cnst);
 816       return;
 817     }
 818 }
 819
 820 /** \brief Attribute the value bound to var->bound.
 821  *
 822  *  \param sys the lmm_system_t
 823  *  \param var the lmm_variable_t
 824  *  \param bound the new bound to associate with var
 825  *
 826  *  Makes var->bound equal to bound. Whenever this function is called
 827  *  a change is  signed in the system. To
 828  *  avoid false system changing detection it is a good idea to test
 829  *  (bound != 0) before calling it.
 830  *
 831  */
 832 void lmm_update_variable_bound(lmm_system_t sys, lmm_variable_t var,
 833                                double bound)
 834 {
 835   sys->modified = 1;
 836   var->bound = bound;
 837
 838   if (var->cnsts_number)
 839     lmm_update_modified_set(sys, var->cnsts[0].constraint);
 840 }
 841
 842
 843 void lmm_update_variable_weight(lmm_system_t sys, lmm_variable_t var,
 844                                 double weight)
 845 {
 846   int i;
 847   lmm_element_t elem;
 848
 849   if (weight == var->weight)
 850     return;
 851   XBT_IN("(sys=%p, var=%p, weight=%f)", sys, var, weight);
 852   sys->modified = 1;
 853   var->weight = weight;
 854   xbt_swag_remove(var, &(sys->variable_set));
 855   if (weight)
 856     xbt_swag_insert_at_head(var, &(sys->variable_set));
 857   else
 858     xbt_swag_insert_at_tail(var, &(sys->variable_set));
 859
 860   for (i = 0; i < var->cnsts_number; i++) {
 861     elem = &var->cnsts[i];
 862     xbt_swag_remove(elem, &(elem->constraint->element_set));
 863     if (weight)
 864       xbt_swag_insert_at_head(elem, &(elem->constraint->element_set));
 865     else
 866       xbt_swag_insert_at_tail(elem, &(elem->constraint->element_set));
 867
 868     if (i == 0)
 869       lmm_update_modified_set(sys, elem->constraint);
 870   }
 871   if (!weight)
 872     var->value = 0.0;
 873
 874   XBT_OUT();
 875 }
 876
 877 double lmm_get_variable_weight(lmm_variable_t var)
 878 {
 879   return var->weight;
 880 }
 881
 882 void lmm_update_constraint_bound(lmm_system_t sys,
 883                                             lmm_constraint_t cnst,
 884                                             double bound)
 885 {
 886   sys->modified = 1;
 887   lmm_update_modified_set(sys, cnst);
 888   cnst->bound = bound;
 889 }
 890
 891 int lmm_constraint_used(lmm_system_t sys, lmm_constraint_t cnst)
 892 {
 893   return xbt_swag_belongs(cnst, &(sys->active_constraint_set));
 894 }
 895
 896 XBT_INLINE lmm_constraint_t lmm_get_first_active_constraint(lmm_system_t
 897                                                             sys)
 898 {
 899   return (lmm_constraint_t)xbt_swag_getFirst(&(sys->active_constraint_set));
 900 }
 901
 902 XBT_INLINE lmm_constraint_t lmm_get_next_active_constraint(lmm_system_t
 903                                                            sys,
 904                                                            lmm_constraint_t
 905                                                            cnst)
 906 {
 907   return (lmm_constraint_t)xbt_swag_getNext(cnst, (sys->active_constraint_set).offset);
 908 }
 909
 910 #ifdef HAVE_LATENCY_BOUND_TRACKING
 911 XBT_INLINE int lmm_is_variable_limited_by_latency(lmm_variable_t var)
 912 {
 913   return (double_equals(var->bound, var->value));
 914 }
 915 #endif
 916
 917
 918 /** \brief Update the constraint set propagating recursively to
 919  *  other constraints so the system should not be entirely computed.
 920  *
 921  *  \param sys the lmm_system_t
 922  *  \param cnst the lmm_constraint_t affected by the change
 923  *
 924  *  A recursive algorithm to optimize the system recalculation selecting only
 925  *  constraints that have changed. Each constraint change is propagated
 926  *  to the list of constraints for each variable.
 927  */
 928 static void lmm_update_modified_set_rec(lmm_system_t sys,
 929                                         lmm_constraint_t cnst)
 930 {
 931   void* _elem;
 932
 933   xbt_swag_foreach(_elem, &cnst->element_set) {
 934     lmm_variable_t var = ((lmm_element_t)_elem)->variable;
 935     s_lmm_element_t *cnsts = var->cnsts;
 936     int i;
 937     for (i = 0; var->visited != sys->visited_counter
 938              && i < var->cnsts_number ; i++) {
 939       if (cnsts[i].constraint != cnst
 940           && !xbt_swag_belongs(cnsts[i].constraint,
 941                                &sys->modified_constraint_set)) {
 942         xbt_swag_insert(cnsts[i].constraint, &sys->modified_constraint_set);
 943         lmm_update_modified_set_rec(sys, cnsts[i].constraint);
 944       }
 945     }
 946     var->visited = sys->visited_counter;
 947   }
 948 }
 949
 950 static void lmm_update_modified_set(lmm_system_t sys,
 951                                     lmm_constraint_t cnst)
 952 {
 953   /* nothing to do if selective update isn't active */
 954   if (sys->selective_update_active
 955       && !xbt_swag_belongs(cnst, &sys->modified_constraint_set)) {
 956     xbt_swag_insert(cnst, &sys->modified_constraint_set);
 957     lmm_update_modified_set_rec(sys, cnst);
 958   }
 959 }
 960
 961 /** \brief Remove all constraints of the modified_constraint_set.
 962  *
 963  *  \param sys the lmm_system_t
 964  */
 965 static void lmm_remove_all_modified_set(lmm_system_t sys)
 966 {
 967   if (++sys->visited_counter == 1) {
 968     /* the counter wrapped around, reset each variable->visited */
 969         void *_var;
 970     xbt_swag_foreach(_var, &sys->variable_set)
 971       ((lmm_variable_t)_var)->visited = 0;
 972   }
 973   xbt_swag_reset(&sys->modified_constraint_set);
 974 }
 975
 976 /**
 977  *  Returns total resource load
 978  *
 979  *  \param cnst the lmm_constraint_t associated to the resource
 980  *
 981  */
 982 double lmm_constraint_get_usage(lmm_constraint_t cnst) {
 983    double usage = 0.0;
 984    xbt_swag_t elem_list = &(cnst->element_set);
 985    void *_elem;
 986    lmm_element_t elem = NULL;
 987
 988    xbt_swag_foreach(_elem, elem_list) {
 989          elem = (lmm_element_t)_elem;
 990      /* 0-weighted elements (ie, sleep actions) are at the end of the swag and we don't want to consider them */
 991      if (elem->variable->weight <= 0)
 992        break;
 993      if ((elem->value > 0)) {
 994        if (cnst->shared)
 995          usage += elem->value * elem->variable->value;
 996        else if (usage < elem->value * elem->variable->value)
 997          usage = elem->value * elem->variable->value;
 998      }
 999    }
1000   return usage;
1001 }
1002
1003