Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Adding test for SURF concurrency feature
[simgrid.git] / 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 }